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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Beldiceanu, N., Flener, P., & Lorca, X. (2008). Combining tree partitioning, precedence, and incomparability constraints. Constraints, 13(4), 459–489.
Boukerche, A., Pazzi, R.W.N., & Araujo, R.B. (2006). fault-tolerant wireless sensor network routing protocols for the supervision of contex-aware physical environments. Journal of Parallel and Distributed Computing, 66(4), 586–599.
Bredin, J.L., Demaine, E.D., Hajiaghayi, M., & Rus, D. (2005). Deploying sensor networks with guaranteed capacity and fault tolerance. In: Proc. 6th ACM Int’l Symp. Mobile Ad Hoc Networking and Computing (MobiHoc’05).
Chipara, O., He, Z., Xing, G., Chen, Q., Wang, X., Lu, C., Stankovic, J., & Abdelzaher, T. (2006). Real-time power-aware routing in wireless sensor networks. In: Proc. 14th IEEE Workshop Quality of Service (IWQoS’06).
Cormen, T.H., Stein, C., Rivest, R.L., & Leiserson, C.E. (2001). Introduction to algorithms, 2nd edn. McGraw-Hill higher education.
Feo, T.A., & Resende, M.G.C. (1989). A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8, 67–71.
Feo, T.A., & Resende, M.G.C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization, 6, 109–133.
Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., & Levis, P. (2009). Collection tree protocol. In: Proc. 7th ACM Conf. Embedded Networked Sensor Systems (SenSys’09).
Golovach, P.A., & Thilikos, D.M. (2011). Paths of bounded length and their cuts: Parameterized complexity and algorithms. Discrete Optimization, 8(1), 72–86.
Han, X., Cao, X., Lloyd, E.L., & Shen, C.C. (2010). Fault-tolerant relay node placement in heterogeneous wireless sensor networks. IEEE Transactions on Mobile Computing, 9(5), 643–656.
Junker, U. (2004). QUICKXPLAIN: Preferred explanations and relaxations for over-constrained problems. In: McGuinness, D.L., Ferguson, G. (eds) AAAI, AAAI Press/The MIT Press.
Lovász, L., Neumann-Lara, V., & Plummer, M. (1978). Mengerian theorems for paths of bounded length. Periodica Mathematica Hungarica, 9(4), 269–276.
Misra, S., Hong, S.D., Xue, G., & Tang, J. (2008). Constrained relay node placement in wireless sensor networks to meet connectivity and survivability requirements. In: Proc. 27th Ann. IEEE Conf. Computer Communications (INFOCOM’08).
Pu, J., Xiong, Z., & Lu, X. (2008). Fault-tolerant deployment with k-connectivity and partial k-connectivity in sensor networks. Wireless Communications and Mobile Computing, 9(7), 909–919.
Resende, M.G.C., & Ribeiro, C.C. (2002). Greedy randomized adaptive search procedures. In: Glover, F., Kochenberger, G. (eds) State of the Art Handbook in Metaheuristics, Kluwer Academic Publishers.
Sitanayah, L., Brown, K.N., & Sreenan, C.J. (2011). Fault-tolerant relay deployment for k node-disjoint paths in wireless sensor networks. In: Proc. 4th Int’l Conf. IFIP Wireless Days (WD’11), IEEE.
Xiao, Y., Thulasiraman, K., & Xue, G. (2006). Constrained shortest link-disjoint paths selection: A network programming based approach. IEEE Trans Circuits and Systems I: Regular Papers, 53(5), 1174–1187. doi:10.1109/TCSI.2006.869907.
Zeng, Y., Sreenan, C.J., Sitanayah, L., Xiong, N., Park, J.H., & Zheng, G. (2011). An emergency-adaptive routing scheme for wireless sensor networks for building fire hazard monitoring. Sensors, 11(3), 2899–2919.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Quesada, L., Sitanayah, L., Brown, K.N. et al. A constraint programming approach to the additional relay placement problem in wireless sensor networks. Constraints 20, 433–451 (2015). https://doi.org/10.1007/s10601-015-9188-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10601-015-9188-8