PACK: Path coloring based k-connectivity detection algorithm for wireless sensor networks

被引:15
作者
Dagdeviren, Orhan [1 ]
Akram, Vahid Khalilpour [1 ]
机构
[1] Ege Univ, Int Comp Inst, Izmir, Turkey
关键词
Wireless sensor networks; Network connectivity; k-connectivity detection; Distributed algorithms; Asynchronous algorithms; Fault tolerance; VERTEX CONNECTIVITY; AD HOC; POWER;
D O I
10.1016/j.adhoc.2017.06.005
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
A k-connected wireless sensor network (WSN) can tolerate failures on k-1 arbitrary nodes without loosing the connectivity between the remaining active nodes. Hence, the k value is one of the useful benchmarks that can help to measure the network reliability. Given that the nodes in a k-connected network has at least k disjoint paths to each other, we propose the path coloring based k-connectivity detection algorithm (PACK) that finds the k by counting the disjoint paths between the sink and all other nodes. The proposed algorithm has two Detection and Notification phases. In the Detection phase, all nodes find their disjoint paths to the sink and in the Notification phase the minimum detected path count, which determines the global k, is sent to the sink node. We theoretically prove that the detection range of our proposed algorithm is better than the existing distributed algorithms and uses fixed length messages with O(n Delta log(2)n) bit complexity and O(n) time complexity where n is the number of nodes and Delta is the maximum node degree. According to the comprehensive simulation results, the average correct detection ratio of proposed algorithm is more than 91% which is at least 2.3 times higher than the existing algorithms. (C) 2017 Elsevier B.V. All rights reserved.
引用
收藏
页码:41 / 52
页数:12
相关论文
共 46 条
[1]   A survey on sensor networks [J].
Akyildiz, IF ;
Su, WL ;
Sankarasubramaniam, Y ;
Cayirci, E .
IEEE COMMUNICATIONS MAGAZINE, 2002, 40 (08) :102-114
[2]  
Almasaeid HM, 2009, IEEE ICC, P195
[3]  
[Anonymous], P M AN ALG COMB
[4]  
Atay N., 2008, 8 INT WORKSH ALG FDN, V57, P35
[5]  
Atay N, 2010, SPRINGER TRAC ADV RO, V57, P35
[6]   A Distributed Fault-Tolerant Topology Control Algorithm for Heterogeneous Wireless Sensor Networks [J].
Bagci, Hakki ;
Korpeoglu, Ibrahim ;
Yazici, Adnan .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (04) :914-923
[7]  
Bai XL, 2008, MOBIHOC'08: PROCEEDINGS OF THE NINTH ACM INTERNATIONAL SYMPOSIUM ON MOBILE AD HOC NETWORKING AND COMPUTING, P401
[8]   Topological optimization of reliable networks under dependent failures [J].
Barrera, Javiera ;
Cancela, Hector ;
Moreno, Eduardo .
OPERATIONS RESEARCH LETTERS, 2015, 43 (02) :132-136
[9]   Deploying Sensor Networks With Guaranteed Fault Tolerance [J].
Bredin, Jonathan L. ;
Demaine, Erik D. ;
Hajiaghayi, Mohammad Taghi ;
Rus, Daniela .
IEEE-ACM TRANSACTIONS ON NETWORKING, 2010, 18 (01) :216-228
[10]   Distributed Connectivity Decomposition [J].
Censor-Hillel, Keren ;
Ghaffari, Mohsen ;
Kuhn, Fabian .
PROCEEDINGS OF THE 2014 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'14), 2014, :156-165