A fault-tolerant relay placement algorithm for ensuring k vertex-disjoint shortest paths in wireless sensor networks
| dc.contributor.author | Sitanayah, Lanny | |
| dc.contributor.author | Brown, Kenneth N. | |
| dc.contributor.author | Sreenan, Cormac J. | |
| dc.contributor.funder | Science Foundation Ireland | en |
| dc.contributor.funder | Higher Education Authority | en |
| dc.date.accessioned | 2019-11-07T12:45:04Z | |
| dc.date.available | 2019-11-07T12:45:04Z | |
| dc.date.issued | 2014-07-24 | |
| dc.date.updated | 2019-11-07T12:39:01Z | |
| dc.description.abstract | 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. Our contribution is a solution that enables fault-tolerant WSN deployment planning by judicious use of a minimum number of additional relays. A WSN is robust if at least one route with an acceptable length to a sink is available for each sensor node after the failure of any nodes. In this paper, we define the problem for increasing WSN reliability by deploying a number of additional relays to ensure that each sensor node in the initial design has k length-bounded vertex-disjoint shortest paths to the sinks. To identify the maximum k such that each node has k vertex-disjoint shortest paths, we propose Counting-Paths and its dynamic programming variant. Then, we introduce GRASP-ARP, a centralised offline algorithm that uses Counting-Paths to minimise the number of deployed relays. Empirically, it deploys 35% fewer relays with reasonable runtime compared to the closest approach. Using network simulation, we show that GRASP-ARP’s designs offer a substantial improvement over the original topologies, maintaining connectivity for twice as many surviving nodes after 10% of the original nodes have failed. | en |
| dc.description.sponsorship | Higher Education Authority (Irish Higher EducationAuthority PRTLI-IV research program through the NEMBES project); Science Foundation Ireland (CTVR project (SFI CSET 10/CE/I1853)) | en |
| dc.description.status | Peer reviewed | en |
| dc.description.version | Accepted Version | en |
| dc.format.mimetype | application/pdf | en |
| dc.identifier.citation | Sitanayah, L., Brown, K. N. and Sreenan, C. J. (2014) 'A fault-tolerant relay placement algorithm for ensuring k vertex-disjoint shortest paths in wireless sensor networks', Ad Hoc Networks, 23, pp. 145-162. doi: 10.1016/j.adhoc.2014.07.003 | en |
| dc.identifier.doi | 10.1016/j.adhoc.2014.07.003 | en |
| dc.identifier.endpage | 162 | en |
| dc.identifier.issn | 1570-8705 | |
| dc.identifier.issn | 1570-8713 | |
| dc.identifier.journaltitle | Ad Hoc Networks | en |
| dc.identifier.startpage | 145 | en |
| dc.identifier.uri | https://hdl.handle.net/10468/8972 | |
| dc.identifier.volume | 23 | en |
| dc.language.iso | en | en |
| dc.publisher | Elsevier | en |
| dc.relation.project | info:eu-repo/grantAgreement/SFI/SFI Centre for Science Engineering and Technology (CSET)/10/CE/i853/IE/CSET CTVR: Centre for Communications Value-chain Research 2nd term funding/ | en |
| dc.rights | © 2014 Elsevier B.V. All rights reserved. This manuscript version is made available under the CC BY-NC-ND 4.0 licence. | en |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/ | en |
| dc.subject | Wireless sensor networks | en |
| dc.subject | Network deployment planning | en |
| dc.subject | Relay placement | en |
| dc.subject | Vertex-disjoint paths | en |
| dc.title | A fault-tolerant relay placement algorithm for ensuring k vertex-disjoint shortest paths in wireless sensor networks | en |
| dc.type | Article (peer-reviewed) | en |
