A constraint programming approach to the additional relay placement problem in Wireless Sensor Networks
No Thumbnail Available
Files
Accepted version
Date
2015-04-02
Authors
Sitanayah, Lanny
Brown, Kenneth N.
O'Sullivan, Barry
Sreenan, Cormac J.
Quesada, Luis
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Published Version
Abstract
A 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.
Description
Keywords
Constraint optimisation problem , Network deployment planning , Relay placement , Node disjoint paths , Wireless sensor networks
Citation
Quesada, 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-8
Copyright
© 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-8