A constraint programming approach to the additional relay placement problem in wireless sensor networks

dc.contributor.authorQuesada, Luis
dc.contributor.authorBrown, Kenneth N.
dc.contributor.authorO'Sullivan, Barry
dc.contributor.authorSitanayah, Lanny
dc.contributor.authorSreenan, Cormac J.
dc.contributor.funderScience Foundation Irelanden
dc.date.accessioned2019-11-06T16:58:45Z
dc.date.available2019-11-06T16:58:45Z
dc.date.issued2013-11
dc.date.updated2019-11-06T16:51:23Z
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. Determining whether a network is k-robust is an NP-complete problem. We develop a Constraint Programming (CP) approach for solving this problem which outperforms a Mixed-Integer Programming (MIP) model on larger problems. A network can be made robust by deploying extra relay nodes, and we extend our CP approach to an optimisation problem 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.statusPeer revieweden
dc.description.versionAccepted Versionen
dc.format.mimetypeapplication/pdfen
dc.identifier.citationQuesada, L., Brown, K. N., Sullivan, B. O., Sitanayah, L. and Sreenan, C. J. (2013) 'A Constraint Programming Approach to the Additional Relay Placement Problem in Wireless Sensor Networks', 2013 IEEE 25th International Conference on Tools with Artificial Intelligence, Herndon, VA, USA, 4-6 Nov. pp. 1052-1059. doi: 10.1109/ICTAI.2013.157en
dc.identifier.doi10.1109/ICTAI.2013.157en
dc.identifier.eissn2375-0197
dc.identifier.endpage1059en
dc.identifier.isbn978-1-4799-2972-6
dc.identifier.issn1082-3409
dc.identifier.startpage1052en
dc.identifier.urihttps://hdl.handle.net/10468/8967
dc.language.isoenen
dc.publisherInstitute of Electrical and Electronics Engineers (IEEE)en
dc.relation.projectinfo:eu-repo/grantAgreement/SFI/SFI Centre for Science Engineering and Technology (CSET)/08/CE/I1523/IE/CSET CTVR: Centre for Telecommunications Value-Chain Research (CTVR)/en
dc.relation.urihttps://ieeexplore.ieee.org/document/6735368
dc.rights© 2013 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.en
dc.subjectConstraint optimisation problemsen
dc.subjectWireless sensor networksen
dc.subjectNetwork deployment planningen
dc.subjectRelay placementen
dc.subjectNetwork robustnessen
dc.subjectRelaysen
dc.subjectWireless sensor networksen
dc.subjectNetwork topologyen
dc.subjectCloningen
dc.subjectProgrammingen
dc.subjectTopologyen
dc.subjectRobustnessen
dc.titleA constraint programming approach to the additional relay placement problem in wireless sensor networksen
dc.typeConference itemen
Files
Original bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
2013_ICTAI.pdf
Size:
350.65 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
License bundle
Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
2.71 KB
Format:
Item-specific license agreed upon to submission
Description: