TY - GEN
T1 - A constraint programming approach to the additional relay placement problem in wireless sensor networks
AU - Quesada, Luis
AU - Brown, Kenneth N.
AU - O'Sullivan, Barry
AU - Sitanayah, Lanny
AU - Sreenan, Cormac J.
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
KW - Constraint optimisation problems
KW - network deployment planning
KW - Network robustness
KW - relay placement
KW - wireless sensor networks
UR - https://www.scopus.com/pages/publications/84897734690
U2 - 10.1109/ICTAI.2013.157
DO - 10.1109/ICTAI.2013.157
M3 - Conference proceeding
AN - SCOPUS:84897734690
SN - 9781479929719
T3 - Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
SP - 1052
EP - 1059
BT - Proceedings - 25th International Conference on Tools with Artificial Intelligence, ICTAI 2013
T2 - 25th IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2013
Y2 - 4 November 2013 through 6 November 2013
ER -