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

作     者：Dagdeviren, Orhan Akram, Vahid Khalilpour Farzan, Ali 

作者机构：Ege Univ Int Comp Inst Izmir Turkey Islamic Azad Univ Comp Dept Shabestar Iran 

出 版 物：《JOURNAL OF NETWORK AND COMPUTER APPLICATIONS》 (网络与计算机应用杂志)

年 卷 期：2019年第127卷第Feb.期

页      面：70-81页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：TUBITAK (Scientific and Technical Research Council of Turkey) [113E470] 

主　　题：Minimum vertex cut Imperialist competitive algorithm Evolutionary algorithms Distributed algorithms k-connectivity Fault tolerance Reliability Wireless ad hoc and sensor networks 

摘      要：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.