TY - JOUR
T1 - Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance
AU - Lee, Sookyoung
AU - Younis, Mohamed
AU - Lee, Meejeong
N1 - Funding Information:
This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and Future Planning ( 2013R1A1A3004374 ). This work is also supported by the National Science Foundation , award # CNS 1018171 .
Publisher Copyright:
© 2014 Elsevier B.V. All rights reserved.
PY - 2015/1/1
Y1 - 2015/1/1
N2 - Wireless sensor network (WSN) applications, especially those serving in inhospitable environments such as battlefield reconnaissance, are susceptible to large-scale damage which usually causes simultaneous failure of multiple collocated sensors and gets the network divided into disjoint partitions. In order to prevent the WSN from being inoperative, restoring the overall network connectivity is crucial. Furthermore, it may be desirable to make the repaired network topology resilient to future single node failures caused by aftermath. In this paper, we present an effective strategy for achieving such recovery goal by establishing a bi-connected inter-partition topology while minimizing the maximum path length between pairs for partitions and deploying the least count of relay nodes (RNs). Finding the optimal number and position of RNs is NP-hard and we thus pursue heuristics. The proposed Connectivity Restoration with Assured Fault Tolerance (CRAFT) algorithm strives to form the largest inner simple cycle or backbone polygon (BP) around the center of the damaged area where no partition lies inside. RNs are then deployed to connect each outer partition to the BP through two non-overlapping paths. We analyze the properties of CRAFT mathematically and validate its performance through extensive simulation experiments. The validation results show that CRAFT yields highly connected topologies with short inter-partition paths while employing fewer RNs than competing schemes.
AB - Wireless sensor network (WSN) applications, especially those serving in inhospitable environments such as battlefield reconnaissance, are susceptible to large-scale damage which usually causes simultaneous failure of multiple collocated sensors and gets the network divided into disjoint partitions. In order to prevent the WSN from being inoperative, restoring the overall network connectivity is crucial. Furthermore, it may be desirable to make the repaired network topology resilient to future single node failures caused by aftermath. In this paper, we present an effective strategy for achieving such recovery goal by establishing a bi-connected inter-partition topology while minimizing the maximum path length between pairs for partitions and deploying the least count of relay nodes (RNs). Finding the optimal number and position of RNs is NP-hard and we thus pursue heuristics. The proposed Connectivity Restoration with Assured Fault Tolerance (CRAFT) algorithm strives to form the largest inner simple cycle or backbone polygon (BP) around the center of the damaged area where no partition lies inside. RNs are then deployed to connect each outer partition to the BP through two non-overlapping paths. We analyze the properties of CRAFT mathematically and validate its performance through extensive simulation experiments. The validation results show that CRAFT yields highly connected topologies with short inter-partition paths while employing fewer RNs than competing schemes.
KW - 2-Vertex connectivity
KW - Fault tolerance
KW - Network partitioning
KW - Relay node placement
KW - Topology repair
KW - Wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=84908117957&partnerID=8YFLogxK
U2 - 10.1016/j.adhoc.2014.07.012
DO - 10.1016/j.adhoc.2014.07.012
M3 - Article
AN - SCOPUS:84908117957
VL - 24
SP - 1
EP - 19
JO - Ad Hoc Networks
JF - Ad Hoc Networks
SN - 1570-8705
IS - PA
ER -