Fault-tolerant relay deployment based on length-constrained connectivity and rerouting centrality in wireless sensor networks

No Thumbnail Available
2012_EWSN.pdf(3.05 MB)
Accepted version
Sitanayah, Lanny
Brown, Kenneth N.
Sreenan, Cormac J.
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Journal Issue
Wireless Sensor Networks (WSNs) are prone to failures. To be robust to failures, the network topology should provide alternative routes to the sinks so when failures occur the routing protocol can still offer reliable delivery. We define l-CRC, a new centrality index which measures a node’s importance to connectivity and efficient delivery in the network. We then use this centrality index to concentrate on the most important nodes, providing alternative paths around the nodes with high centrality. Varying l-CRC allows us to trade off cost for robustness. We introduce GRASP-ABP, a local search algorithm for initial robust topology design. We evaluate the algorithm empirically in terms of the number of additional nodes it suggests and its runtime. We then evaluate the robustness of the designs against node failures in simulation, and we demonstrate that the centrality-based GRASP-ABP’s designs are able to offer reliable delivery, comparable to competitor algorithms, but with fewer additional relays and faster runtime.
Wireless sensor networks , Network deployment planning , Relay placement , Centrality
Sitanayah, L., Brown, K. N. and Sreenan, C. J. (2012) 'Fault-Tolerant Relay Deployment Based on Length-Constrained Connectivity and Rerouting Centrality', 9th European Conference, EWSN 2012, Trento, Italy, February 15-17, in Lecture Notes in Computer Science (LNCS, volume 7158), Springer Berlin Heidelberg, pp. 115-130. doi: 10.1007/978-3-642-28169-3_8
© Springer-Verlag Berlin Heidelberg 2012. This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: https://doi.org/10.1007/978-3-642-28169-3_8