You are here

A Constraint Programming Approach to the Additional Relay Placement Problem in Wireless Sensor Networks

Authors: 

Luis Quesada, Lanny Sitanayah, Kenneth N. Brown, Barry O'Sullivan, Cormac J. Sreenan

Publication Type: 
Refereed Original Article
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.
Digital Object Identifer (DOI): 
10.1007/s10601-015-9188-8
ISSN: 
1383-7133
Publication Status: 
Published
Publication Date: 
05/04/2015
Journal: 
Constraints
Institution: 
National University of Ireland, Cork (UCC)
Project Acknowledges: 
Open access repository: 
No
Publication document: