A constraint programming approach to the additional relay placement problem in wireless sensor networks
Loading...
Files
Accepted version
Date
2013-11
Authors
Quesada, Luis
Brown, Kenneth N.
O'Sullivan, Barry
Sitanayah, Lanny
Sreenan, Cormac J.
Journal Title
Journal ISSN
Volume Title
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
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. 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.
Description
Keywords
Constraint optimisation problems , Wireless sensor networks , Network deployment planning , Relay placement , Network robustness , Relays , Wireless sensor networks , Network topology , Cloning , Programming , Topology , Robustness
Citation
Quesada, 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.157
Link to publisher’s version
Copyright
© 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.