A Distributed Evolutionary algorithm for detecting minimum vertex cuts for wireless ad hoc and sensor networks

DAĞDEVİREN O. , Akram V. , Farzan A.

JOURNAL OF NETWORK AND COMPUTER APPLICATIONS, cilt.127, ss.70-81, 2019 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 127
  • Basım Tarihi: 2019
  • Doi Numarası: 10.1016/j.jnca.2018.10.009
  • Sayfa Sayıları: ss.70-81


A minimum vertex cut (MVC) of a graph G is the smallest subset of vertices whose removal creates at least two disconnected group of other vertices. Detecting nodes in MVCs in wireless ad hoc and sensor networks (WASNs) provides valuable information about their robustness and critical parts. There is a wide variety of central algorithms that find or estimate MVCs of graphs, but to the best of our knowledge the existing distributed algorithms can only estimate the cardinality of MVCs, or k, from local neighborhood information. Regardless of the fact that MVCs remain unknown in these algorithms, local estimation of k may produce wrong values, far from the real k. We propose a distributed algorithm, which uses an adapted meta heuristic method, to detect the nodes in MVCs. In the proposed algorithm, all nodes find their available paths to the sink (root node) and determine the minimum subset of nodes that their failure disconnects all detected paths. The smallest detected sets by the nodes will be MVCs of the WASN. Besides finding the union of MVCs with up to 89% average accuracy, the testbed and simulation results show that the correct detection ratio of k in the proposed algorithm is up to 37% more than the existing distributed algorithms.