Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance

Sookyoung Lee, Mohamed Younis, Meejeong Lee

Research output: Contribution to journalArticlepeer-review

103 Scopus citations


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.

Original languageEnglish
Pages (from-to)1-19
Number of pages19
JournalAd Hoc Networks
Issue numberPA
StatePublished - 1 Jan 2015

Bibliographical note

Publisher Copyright:
© 2014 Elsevier B.V. All rights reserved.


  • 2-Vertex connectivity
  • Fault tolerance
  • Network partitioning
  • Relay node placement
  • Topology repair
  • Wireless sensor networks


Dive into the research topics of 'Connectivity restoration in a partitioned wireless sensor network with assured fault tolerance'. Together they form a unique fingerprint.

Cite this