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

Sookyoung Lee, Mohamed Younis, Meejeong Lee

Research output: Contribution to journalArticlepeer-review

93 Scopus citations

Abstract

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
Volume24
Issue numberPA
DOIs
StatePublished - 1 Jan 2015

Keywords

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

Fingerprint

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