Abstract
We propose a method for determining the number of sensors, their arrangement, and approximate lower bounds for the number of sensors for the multiple covering of an arbitrary closed bounded convex area in a plane. The problem of multiple covering is considered with restrictions on the minimal possible distances between the sensors and without such restrictions. To solve these problems, some 0–1 linear programming (LP) problems are constructed.We use a heuristic solution algorithm for 0–1 LP problems of higher dimensions. The results of numerical implementation are given and for some particular cases it is obtained that the number of sensors found can not be decreased.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
T. A. Aldyn-Ool, A. I. Erzin, and V. V. Zalyubovskiy, “The Coverage of a Planar Region with Randomly Deployed Sensors,” Vestnik NGU, Ser.Mat. Mekh. Inform. 10 (4), 7–25 (2010).
S. N. Astrakov and A. I. Erzin, “Construction of Efficient Covering Models in the Monitoring of Extended Objects,” Vychisl. Tekhnol. 17 (1), 26–34 (2012).
H. M. Ammari, Challenges and Opportunities of Connected k-Covered Wireless Sensor Networks: From Sensor Deployment to Data Gathering (Springer, Heidelberg, 2009).
T. Andersen and S. Tirthapura, “Wireless Sensor Deployment for 3D Coverage with Constraints,” in Proceedings of 6th International Conference on Networked Sensing Systems (Pittsburgh, USA, June 17–19, 2009) (IEEE, Piscataway, 2009), pp. 78–81.
S. N. Astrakov, “Coverings of Sets with Restrictions on the Arrangement of Circles,” in Optimization and Applications: Proceedings of VIII International Conference on Optimization Methods and Applications OPTIMA-2017 (Petrovac, Montenegro, October 2–7, 2017) (CEUR Workshop Proc., Vol. 1987), pp. 67–72 [Available at http://ceur-ws.org/Vol-1987 (accessed November 15, 2018)].
N. A. A. Aziz, K. A. Aziz, and W. Z.W. ‘Ismail, “Coverage Strategies forWireless Sensor Networks,” Intern. J. Electron. Commun. Eng. 3 (2), 145–159 (2009).
A. I. Erzin and S. N. Astrakov, “Min-Density Stripe Covering and Applications in Sensor Networks,” in Computational Science and Its Applications—ICCSA 2011: Proceedings of 2011International Conference on Computer Sciences and Its Application (Santander, Spain, June 20–23, 2011), Vol. III (Springer, Heidelberg, 2011), pp. 152–162.
A. Hawbani, X. F. Wang, N. Husaini, and S. Karmoshi, “Grid Coverage Algorithm & Analysis for Wireless Sensor Networks,” Netw. Protocols Algorithms 6 (4), 65–81 (2014).
D. S. Hochbaum and W. Maass, “Approximation Schemes for Covering and Packing Problems in Image Processing and VLSI,” J. ACM32 (1), 130–136 (1985).
C. F. Huang and Y. C. Tseng, “A Survey of Solutions to the Coverage Problems in Wireless Sensor Networks,” J. Internet Technol. 6 (1), 1–8 (2005).
J. E. Kim, J. Han, and C. G. Lee, “Optimal 3-Coverage with Minimum Separation Requirements for Ubiquitous Computing Environments,” Mobile Netw. Appl. 556–570 (2009).
S. Kumar, T. H. Lai, and J. Balogh, “On k-Coverage in a Mostly Sleeping Sensor Network,” in Proceedings of 10th Annual International Conference on Mobile Computer Networks, ACM MobiCom 2004 (ACM, New York, 2004), pp. 144–158.
T. Tabirca, L. T. Yang, and S. Tabirca, “Smallest Number of Sensors for k-Covering,” Internat. J. Comput. Commun. Control 8 (2), 312–319 (2013).
B. Wang, “Coverage Problems in Sensor Networks: A Survey,” J. ACM Comput. Surveys 43 (4), 167–170 (2011).
S. Yang, F. Dai, M. Cardei, J. Wu, and F. Patterson, “On Connected Multiple Point Coverage in Wireless Sensor Networks,” Intern. J. Wireless Inform.Netw. 13 (4), 289–301 (2006).
N. Yeasmin, “k-Coverage Problems and Solutions in Wireless Sensor Networks: A Survey,” Internat. J. Comput. Appl. 100 (17), 1–6 (2014).
V. S. Brusov and S. A. Piyavskii, “A Computational Algorithm for Optimally Covering a Plane Region,” Zh. Vychisl. Mat. Mat. Fiz. 11 (2), 304–312 (1971) [USSR Comput.Math. Math. Phys. 11 (2), 17–27 (1971)].
G. Fejes Tóth, “Multiple Packing and Covering of the Plane with Circles,” Acta Math. Acad. Sci. Hungar. 27 (1–2), 135–140 (1976).
G. Fejes Tóth, “Thinnest Covering of a Circle by Eight, Nine, or Ten Congruent Circles,” in Combinatorial and Computational Geometry (Cambridge Univ. Press, New York, 2005), pp. 361–376.
A. Heppes and H. Melissen, “Covering a Rectangle with Equal Circles,” Period. Math. Hungar. 34 (1–2), 65–81 (1997).
S. Krotoszyčski, “Covering a Disk with Smaller Disks,” Studia Sci. Math. Hungar. 28 (3–4), 277–283 (1993).
H. Melissen, “Loosest Circle Coverings of an Equilateral Triangle,” Math. Mag. 70 (2), 118–124 (1997).
J. B. M. Melissen and P. C. Schuur, “Improved Coverings of a Square with Six and Eight Equal Circles,” Electron. J. Combin. 3 (1/R32), 1–10 (1996) [Available at http://www.combinatorics.org/ojs/index.php/ eljc/article/view/v3i1r32 (accessed November 20, 2018)].
J. B. M. Melissen and P. C. Schuur, “Covering a Rectangle with Six and Seven Circles,” Discrete Appl. Math. 99 (1–3), 149–156 (2000).
K. J. Nurmela, Covering a Circle by Congruent Circular Discs, Preprint. Department of Computer Sciences and Engineering (Helsinki Univ. Technol., Helsinki, 1998).
K. J. Nurmela, “Conjecturally Optimal Coverings of an Equilateral Triangle with Up To 36Equal Circles,” Exp. Math. 9 (2), 241–250 (2000).
K. J. Nurmela and P. R. J. Östergård, “Covering a Square with up to 30Equal Circles,”Res.Rep. 62 (Helsinki Univ. Technol.,Helsinki, Finland, 2000) [see http://www.tcs.hut.fi/old/reports /A62abstract.html (accessed November 20, 2018)].
A. Suzuki and Z. Drezner, “The Minimum Number Equitable Radius Location Problems with Continuous Demand,” European J. Oper. Res. 195 (1), 17–30 (2009).
T. Tarnai and Zs. Gáspár, “Covering a Square by Equal Circles, Elem.Math. 50, 167–170 (1995).
Sh. I. Galiev and M. A. Karpova, “Optimization of Multiple Covering of a Bounded Set with Circles,” Zh. Vychisl.Mat. Mat. Fiz. 50 (4), 757–769 (2010) [Comput.Math. Math. Phys. 50 (4), 721–732 (2010)].
Sh. I. Galiev and A. V. Khorkov, “Multiple Circle Coverings of an Equilateral Triangle, Square, and Circle,” Diskretn. Anal. Issled. Oper. 22 (6), 5–28 (2015).
A.V. Eremeev, L. A. Zaozerskaya, and A. A. Kolokolov, “The Set Covering Problem: Complexity,Algorithms, and Experimental Investigations,” Diskretn. Anal. Issled. Oper. Ser. 2, 7 (2), 22–46 (2000).
N. N. Kuzyurin, “On the Complexity of Asymptotically Optimal Coverings and Packing,” Dokl. Akad. Nauk 363 (1), 11–13 (1998) [Dokl.Math. 58 (3), 345–346 (1998)].
M. Yu. Khachai and M. I. Poberii, “Computational Complexity and Approximability of a Series of Geometric Covering Problems,” Trudy Inst. Mat. Mekh. 18, No. 3, 247–260, 2012 [Proc. Steklov Inst. Math. 284 (Suppl. 1), S87–S95 (2014)].
M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979; Mir,Moscow, 1982).
N. Megiddo and K. J. Supowit, “On the Complexity of Some Common Geometric Location Problems,” SIAM J. Comput. 13 (1), 182–196 (1984).
I. Kh. Sigal and A. P. Ivanova, Introduction to Applied Discrete Programming: Models and Computational Algorithm (Fizmatlit, Moscow, 2002) [in Russian].
Sh. I. Galiev and M. S. Lisafina, “Linear Models for the Approximate Solution of the Problem of Packing Equal Circles into a Given Domain,” European J. Oper. Res. 230, 505–514 (2013).
D. Bertsimas and R. Vohra, “Rounding Algorithms for Covering Problems,” Math. Program. 80 (1), 63–89 (1998).
A. Caprara, M. Fischetti, and P. Tóth, “AHeuristicMethod for the Set Covering Problem,” Oper. Res. 47 (5), 730–743 (1999).
N. G. Hall and D. S. Hochbaum, “A Fast Approximation Algorithm for the Multicovering Problem,” Discrete Appl.Math. 15 (1), 35–40 (1989).
S. Umetani and M. Yagiura, “Relaxation Heuristics for the Set Covering Problem,” J. Oper. Res. Soc. Japan 50 (4), 350–375 (2007).
Author information
Authors and Affiliations
Corresponding authors
Additional information
Russian Text © Sh.I. Galiev, A.V. Khorkov, 2019, published in Diskretnyi Analiz i Issledovanie Operatsii, 2019, Vol. 26, No. 1, pp. 33–54.
Rights and permissions
About this article
Cite this article
Galiev, S.I., Khorkov, A.V. On the Number and Arrangement of Sensors for the Multiple Covering of Bounded Plane Domains. J. Appl. Ind. Math. 13, 43–53 (2019). https://doi.org/10.1134/S199047891901006X
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S199047891901006X