.png){kind=icon}
.png){kind=icon}
Return
A Distributed Evolutionary algorithm for detecting minimum vertex cuts for wireless ad hoc and sensor networks
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jnca.2018.10.009.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Minimum vertex cut
Imperialist competitive algorithm
Evolutionary algorithms
Distributed algorithms
k-connectivity
Fault tolerance
Reliability
Wireless ad hoc and sensor networks
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
8
Papers:
3.6K
Citations:
1.1W