On the number and arrangement of sensors for~the~multiple covering of bounded plane~domains

Sh. I. Galiev ; A. V. Khorkov

Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 1, pp. 33-54.

Résumé

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. Tab. 1, illustr. 3, bibliogr. 42.

Détail

Mots-clés : wireless sensor network, multiple covering, $k$-fold covering, $k$-covering with circles of given radius, number of sensors for monitoring of given area, arrangement of sensors.

Bibliographie

[1] T. A. Aldyn-ool, A. I. Erzin, V. V. Zalyubovskiy, “The coverage of a planar region by randomly deployed sensors”, Vestn. NGU, Ser. Mat. Mekh. Inform., 10:4 (2010), 7–25 (Russian) | Zbl

[2] S. N. Astrakov, A. I. Erzin, “Construction of efficient covering models in the monitoring of extended objects”, Vychisl. Tekhnol., 17:1 (2010), 26–34 (Russian)

[3] V. S. Brusov, S. A. Piyavskii, “A computational algorithm for optimally covering a plane region”, USSR Comput. Math. Math. Phys., 11:2 (1971), 17–27 | DOI

[4] Sh. I. Galiev, M. A. Karpova, “Optimization of multiple covering of a bounded set with circles”, Comput. Math. Math. Phys., 50:4 (2010), 721–732 | DOI | MR | Zbl

[5] Sh. I. Galiev, A. V. Khorkov, “Multiple circle coverings of an equilateral triangle, square, and circle”, Diskretn. Anal. Issled. Oper., 22:6 (2015), 5–28 (Russian) | MR | Zbl

[6] A. V. Eremeev, L. A. Zaozerskaya, A. A. Kolokolov, “The set covering problem: Complexity, algorithms, and experimental investigations”, Diskretn. Anal. Issled. Oper., Ser. 2, 7:2 (2009), 22–46 (Russian) | MR

[7] N. N. Kuzyurin, “On the complexity of asymptotically optimal coverings and packing”, Dokl. Math., 58:3 (1998), 345–346 | MR | Zbl

[8] I. Kh. Sigal, A. P. Ivanova, Introduction to Applied Discrete Programming: Models and Computational Algorithm, Fizmatlit, M., 2002 (Russian)

[9] M. Yu. Khachai, M. I. Poberii, “Computational complexity and approximability of a series of geometric covering problems”, Proc. Steklov Inst. Math., 284, Suppl. 1 (2014), S87–S95 | MR | Zbl

[10] Ammari H. M., Challenges and opportunities of connected $k$-covered wireless sensor networks, Spinger-Verl., Berlin–Heidelberg, 2009, 342 | MR

[11] Andersen T., Tirthapura S., “Wireless sensor deployment for 3D coverage with constraints”, Proc. 6th Int. Conf. Networked Sensing Systems (Pittsburg, 2009), 78–81

[12] Astrakov S. N., “Coverings of sets with restrictions on the arrangement of circles”, Proc. VIII Int. Conf. Optimization and Applications, OPTIMA-2017 (Petrovac, Montenegro), 2017, 67–72 www.ceur-ws.org

[13] Aziz N. A. A., Aziz K. A., Ismail W. Z. W., “Coverage strategies for wireless sensor networks”, World Acad. Sci., Eng. Technology Int. J. Electron. Commun. Eng., 3:2 (2009), 145–159

[14] Bertsimas. D., Vohra. R., “Rounding algorithms for covering problems”, Math. Program., 80 (1998), 63–89 | MR | Zbl

[15] Caprara A., Fischetti M., Tóth P., “A heuristic method for the set covering problem”, Oper. Res., 47 (1999), 730–743 | DOI | MR | Zbl

[16] Erzin A., Astrakov S., “Min-density stripe covering and applications in sensor networks”, Lect. Notes Comput. Sci., 6784, 2011, 152–162 | DOI | MR

[17] Fejes Tóth G., “Multiple packing and covering of the plane with circles”, Acta Math. Acad. Sci. Hungar., 27:1–2 (1976), 135–140 | DOI | MR | Zbl

[18] Fejes Tóth G., “Thinnest covering of circle by eight, nine and ten congruent circles”, Comb. Comput. Geom., 52 (2005), 361–376 | MR | Zbl

[19] Galiev Sh. I., Lisafina M. S., “Linear models for the approximate solution of the problem of packing equal circles into a given domain”, Eur. J. Oper. Res., 230 (2013), 505–514 | DOI | MR | Zbl

[20] Garey M. R., Jonson D. S., “Computers and intractability”, A guide to the theory of NP-completeness, W. H. Freeman, San Francisco, 1979 | MR | Zbl

[21] Hall N., Hochbaum D. A., “A fast approximation algorithm for the multicovering problem”, Discrete Appl. Math., 15 (1989), 35–40 | DOI | MR

[22] Hawbani A., Wang X. F., Husaini N., Karmoshi S., “Grid coverage algorithm analysis for wireless sensor networks”, Netw. Protocols Algorithms, 6:4 (2014), 65–81

[23] Heppes A., Melissen H., “Covering a rectangle with equal circles”, Period. Math. Hungar., 34 (1997), 65–81 | DOI | MR | Zbl

[24] Hochbaum D. S., Maass W., “Approximation schemes for covering and packing problems in image processing and vlsi”, J. ACM, 32:1 (1985), 130–136 | DOI | MR | Zbl

[25] Huang C. F., Tseng Y. C., “A survey of solutions to the coverage problems in wireless sensor networks”, J. Internet Technology, 6:1 (2005), 1–8

[26] Kim J. E., Han J., Lee C. G., “Optimal 3-coverage with minimum separation requirements for ubiquitous computing environments”, Mobile Netw. Appl., 2009, 556–570 | DOI

[27] Krotoszynski S., “Covering a disk with smaller disks”, Studia Sci. Math. Hungar., 28:3–4 (1993), 277–283 | MR | Zbl

[28] Kumar S., Lai T. H., Balogh J., “On $k$-coverage in a mostly sleeping sensor network”, Proc. ACM MobiCom., 2004, 144–158

[29] Megiddo N., “On the complexity of some common geometric location problems”, SIAM J. Comput., 13 (1984), 182–196 | DOI | MR | Zbl

[30] Melissen J. B. M., “Loosest circle coverings of an equilateral triangle”, Math. Mag., 70 (1997), 119–125 | DOI | MR

[31] Melissen J. B. M., Schuur P. C., “Improved coverings of a square with six and eight equal circles”, Electron. J. Comb., 3:R32 (1996), 10 | MR | Zbl

[32] Melissen J. B. M., Schuur P. C., “Covering a rectangle with six and seven circles”, Discrete Appl. Math., 99 (2000), 149–156 | DOI | MR | Zbl

[33] Nurmella K. J., Covering a circle by congruent circular discs, Preprint, Departament of Computer Sciences and Engineering. Helsinki Univ. Technology, 1998

[34] Nurmella K. J., “Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles”, Exp. Math., 9 (2000), 241–250 | DOI | MR

[35] Nurmella K. J., Östergard P. R. J., Covering a square with up to 30 equal circles, Res. Rep. A62, Lab. Technology Helsinki Univ., 2000 www.tcs.hut.fi/Publications/reports | MR

[36] Suzuki A., Drezner Z., “The minimum number equitable radius location problems with continuous domain”, Eur. J. Oper. Res., 2009, 17–30 | DOI | MR | Zbl

[37] Tabirca T., Yang L. T., Tabirca S., “Smallest number of sensors for $k$-covering”, Int. J. Comput. Commun., 8 (2013), 312–319 | DOI

[38] Tarnai T., Gáspár Zs., “Covering a square by equal circles”, Elem. Math., 50 (1995), 167–170 | MR | Zbl

[39] Umetani S., Yagiura M., “Relaxation heuristics for the set covering problem”, J. Oper. Res. Soci. Jap., 50:4 (2007), 350–375 | MR | Zbl

[40] Wang B., “Coverage problems in sensor networks: a survey”, J. ACM Comput. Surv. (CSUR), 43 (2011), 167–170

[41] Yang S., Dai F., Cardei M., Wu J., “On connected multiple point coverage in wireless sensor networks”, Int. J. Wireless Inform. Netw., 13:4 (2006), 289–301 | DOI

[42] Yeasmin N., “$k$-Coverage problems and solutions in wireless sensor networks: a survey”, Int. Jo. Comput. Appl., 100:17 (2014), 1–6