Fault-tolerant relay deployment for k node-disjoint paths in wireless sensor networks
Brown, Kenneth N.
Sreenan, Cormac J.
Institute of Electrical and Electronics Engineers (IEEE)
Ensuring that wireless sensor networks (WSNs) are robust to failures requires that the physical network topology will offer alternative routes to the sinks. This requires sensor network deployments to be planned with an objective of ensuring some measure of robustness in the topology, so that when failures occur that routing protocols can continue to offer reliable delivery. Our contribution is a solution that enables fault-tolerant WSN deployment planning by judicious use of a minimum number of additional relay nodes. A WSN is robust if at least one route to a sink is available for each remaining sensor node after the failure of up to k-1 nodes. In this paper, we define the problem for increasing WSN reliability by deploying a number of additional relay nodes to ensure that each sensor node in the initial design has k node-disjoint paths to the sinks. We present GRASP-ARP, a centralised offline algorithm to be run during the initial topology design to solve this problem. We have implemented this algorithm and demonstrated in simulation that it improves the efficiency of relay node placement for k node-disjoint paths compared to the most closely related published algorithms.
Wireless sensor networks , Network deployment planning , Relay placement , Node-disjoint paths , Relays , Network topology , Algorithm design and analysis , Fault tolerance , Fault tolerant systems , Topology , Telecommunication network topology
Sitanayah, L., Brown, K. N. and Sreenan, C. J. (2011) 'Fault-tolerant relay deployment for k node-disjoint paths in wireless sensor networks', 2011 IFIP Wireless Days (WD), Niagara Falls, ON, Canada, 10-12 October, (6 pp). doi: 10.1109/WD.2011.6098176
© 2011 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.