A constraint programming approach to the additional relay placement problem in Wireless Sensor Networks

Simple item page
dc.contributor.authorSitanayah, Lanny
dc.contributor.authorBrown, Kenneth N.
dc.contributor.authorO'Sullivan, Barry
dc.contributor.authorSreenan, Cormac J.
dc.contributor.authorQuesada, Luis
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2019-01-31T15:05:17Z
dc.date.available2019-01-31T15:05:17Z
dc.date.issued2015-04-02
dc.date.updated2019-01-31T14:57:09Z
dc.description.abstractA Wireless Sensor Network (WSN) is composed of many sensor nodes which transmit their data wirelessly over a multi-hop network to data sinks. Since WSNs are subject to node failures, the network topology should be robust, so that when a failure does occur, data delivery can continue from all surviving nodes. A WSN is k-robust if an alternate length-constrained route to a sink is available for each surviving node after the failure of up to k-1 nodes. A WSN is strongly k-robust if there are k disjoint length-constrained routes to a sink for each node. Determining whether a network is k-robust is polynomial. However, determining whether a network is strongly k-robust is an NP-complete problem. We develop a Constraint Programming (CP) approach for deciding strongly k-robustness that outperforms a Mixed-Integer Programming (MIP) model on larger problems. A network can be made (strongly) robust by deploying extra relay nodes. We extend our CP approach to an optimisation approach by using QuickXplain to search for a minimal set of relays, and compare it to a state-of-the-art local search approach.en
dc.description.sponsorshipScience Foundation Ireland (10/CE/11853 and 12/RC/1289)en
dc.description.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationQuesada, L., Sitanayah, L., Brown, Kenneth N., O'Sullivan, B., Sreenan, C. J. (2015) 'A Constraint Programming Approach to the Additional Relay Placement Problem in Wireless Sensor Networks', Constraints, 20(4), pp. 433-451. doi: 10.1007/s10601-015-9188-8en
dc.identifier.doi10.1007/s10601-015-9188-8
dc.identifier.endpage451en
dc.identifier.issn1383-7133
dc.identifier.issued4en
dc.identifier.journaltitleConstraintsen
dc.identifier.startpage433en
dc.identifier.urihttps://hdl.handle.net/10468/7412
dc.identifier.volume20en
dc.language.isoenen
dc.publisherSpringeren
dc.relation.urihttps://link.springer.com/article/10.1007/s10601-015-9188-8
dc.rights© Springer Science+Business Media New York 2015. This is a post-peer-review, pre-copyedit version of an article published in Constraints. The final authenticated version is available online at: http://dx.doi.org/10.1007/s10601-015-9188-8en
dc.subjectConstraint optimisation problemen
dc.subjectNetwork deployment planningen
dc.subjectRelay placementen
dc.subjectNode disjoint pathsen
dc.subjectWireless sensor networksen
dc.titleA constraint programming approach to the additional relay placement problem in Wireless Sensor Networksen
dc.typeArticle (peer-reviewed)en
Files
Original bundle
Now showing 1 - 2 of 2
Thumbnail Image
Name:
9003_cp_relay-preprint.pdf
Size:
1013.2 KB
Format:
Adobe Portable Document Format
Description:
Author's original
Thumbnail Image
Name:
2014 Constraints.pdf
Size:
771.38 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Computer Science - Journal Articles
Insight Centre for Data Analytics - Journal Articles