Abstract
Wireless sensor networks have been widely deployed in the last decades to provide various services, like environmental monitoring or object tracking. Such a network is composed of a set of sensor nodes which are used to sense and transmit collected information to a base station. To achieve this goal, two properties have to be guaranteed: (i) the sensor nodes must be placed such that the whole environment of interest (represented by a set of targets) is covered, and (ii) every sensor node can transmit its data to the base station (through other sensor nodes). In this paper, we consider the Minimum Connected k-Coverage (MCkC) problem, where a positive integer \(k \ge 1\) defines the coverage multiplicity of the targets. We propose two mathematical programming formulations for the MCkC problem on square grid graphs and random graphs. We compare them to a recent model proposed by Rebai et al. (Comput Oper Res 59:11–21, 2015). We use a standard mixed integer linear programming solver to solve several instances with different formulations. In our results, we point out the quality of the LP-bound of each formulation as well as the total CPU time or the proportion of solved instances to optimality within a given CPU time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bonsma, P. (2012). Max-leaves spanning tree is APX-hard for cubic graphs. Journal of Discrete Algorithms, 12, 14–23.
Chakrabarty, K., Iyengar, S. S., Qi, H., & Cho, E. (2002). Grid coverage for surveillance and target location in distributed sensor networks. IEEE Transactions on Computers, 51(12), 1448–1453.
Das B, Bharghavan V (1997) Routing in ad-hoc networks using minimum connected dominating sets. In Communications, ICC ’97 Montreal, towards the knowledge millennium (Vol. 1, pp. 376–380). IEEE
Fan N, Watson J (2012) Solving the connected dominating set problem and power dominating set problem by integer programming. In Combinatorial Optimization and Applications: 6th International Conference (COCOA), Springer, Lecture Notes in Computer Science (Vol. 7402, pp. 371–383). https://doi.org/10.1007/978-3-642-31770-5_33.
Fourer, R., Gay, D. M., & Kernighan, B. W. (1993). AMPL: A modeling language for mathematical programming. Danvers: The Scientific Press (now an imprint of Boyd & Fraser Publishing Co.).
Fujie, T. (2003). An exact algorithm for the maximum leaf spanning tree problem. Computers & Operations Research, 30(13), 1931–1944.
Fujie, T. (2004). The maximum-leaf spanning tree problem: Formulations and facets. Networks, 43(4), 212–223.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York: W. H. Freeman & Co.
Gavish, B. (1982). Topological design of centralized computer networks-formulations and algorithms. Networks, 12(4), 355–377.
Gendron, B., Lucena, A., da Cunha, A. S., & Simonetti, L. (2014). Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem. INFORMS Journal on Computing, 26(4), 645–657.
Gonçalves, D., Pinlou, A., Rao, M., & Thomassé, S. (2011). The domination number of grids. SIAM Journal on Discrete Mathematics, 25(3), 1443–1453.
Guha, S., & Khuller, S. (1998). Approximation algorithms for connected dominating sets. Algorithmica, 20(4), 374–387.
IBM-ILOG (2014) IBM ILOG CPLEX 12.6 reference manual. http://www-01.ibm.com/support/knowledgecenter/SSSA5P_12.6.0/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html. Accessed 24 June 2018.
Ke, W., Liu, B., & Tsai, M. (2011). The critical-square-grid coverage problem in wireless sensor networks is NP-Complete. Computer Networks, 55(9), 2209–2220. https://doi.org/10.1016/j.comnet.2011.03.004.
Lucena, A., Maculan, N., & Simonetti, L. (2010). Reformulations and solution algorithms for the maximum leaf spanning tree problem. Computational Management Science, 7(3), 289–311.
Miller, C. E., Tucker, A. W., & Zemlin, R. A. (1960). Integer programming formulation of traveling salesman problems. Journal of ACM, 7(4), 326–329.
Rebai, M., Le Berre, M., Snoussi, H., Hnaien, F., & Khoukhi, L. (2015). Sensor deployment optimization methods to achieve both coverage and connectivity in wireless sensor networks. Computers & Operations Research, 59, 11–21.
Rebai, M., Afsar, H. M., & Snoussi, H. (2016). Exact methods for sensor deployment problem with connectivity constraint in wireless sensor networks. International Journal of Sensor Networks (IJSNET), 21(3), 157–168. https://doi.org/10.1504/IJSNET.2016.078324.
Reich, A. (2016). Complexity of the maximum leaf spanning tree problem on planar and regular graphs. Theoretical Computer Science, 626(C), 134–143.
Reis, M., Lee, O., & Usberti, F. (2015). Flow-based formulation for the maximum leaf spanning tree problem. Electronic Notes in Discrete Mathematics, 50, 205–210.
Roveti DK (2001) Choosing a humidity sensor: A review of three technologies. http://www.sensorsmag.com/sensors/humidity-moisture/choosing-a-humidity-sensor-a-review-three-technologies-840. Accessed 24 June 2018.
Wang X, Xing G, Zhang Y, Lu C, Pless R, Gill C (2003) Integrated coverage and connectivity configuration in wireless sensor networks. In: Proceedings of the 1st international conference on embedded networked sensor systems, SenSys’03 (pp. 28–39). ACM
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Elloumi, S., Hudry, O., Marie, E. et al. Optimization of wireless sensor networks deployment with coverage and connectivity constraints. Ann Oper Res 298, 183–206 (2021). https://doi.org/10.1007/s10479-018-2943-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-018-2943-7