Conference Publication Details
Mandatory Fields
Quesada, Luis; Brown, Kenneth N.; O’Sullivan, Barry; Sitanayah, Lanny; Sreenan, Cormac J.
IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI)
A Constraint Programming Approach to the Additional Relay Placement Problem in Wireless Sensor Networks
Optional Fields
Constraint optimisation problems Wireless sensor networks Network deployment planning Relay placement Network robustness Relays Wireless sensor networks Network topology Cloning Programming Topology Robustness
Washington DC, USA
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.
Grant Details
Science Foundation Ireland
Grant No. 08/CE/I523.