About Journal 
Editorial Board
Publishing Ethics
Author Guide 
Submission
Prepare Your Manuscript
Peer review
Archive
Editorial Board
Publishing Ethics
Author Guide
Submission Prepare Your ManuscriptPeer review
Archive
English version:
Journal of Applied and Industrial Mathematics, 2019, 13:1, 43-53
Volume 26, No 1, 2019, P. 33-54
UDC 519.6:519.147
Sh. I. Galiev and A. V. Khorkov
On the number and arrangement of sensors for the multiple covering of bounded plane domains
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.
Tab. 1, illustr. 3, bibliogr. 42.
Keywords: 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.
DOI: 10.33048/daio.2019.26.609
Shamil I. Galiev 1
Alexander V. Khorkov 1
1. Tupolev Kazan National Research Technical University,
10 Karl Marks Street, 420011 Kazan, Russia
e-mail: sh.galiev@mail.ru, aLex22fcrk@yandex.ru
Received February 7, 2018
Revised October 22, 2018
Accepted November 28, 2018
References
[1] T. A. Aldyn-ool, A. I. Erzin, and V. V. Zalyubovskiy, The coverage of a planar region by randomly deployed sensors, Vestn. NGU, Ser. Mat. Mekh. Inform., 10, No. 4, 7–25, 2010 [Russian].[2] S. N. Astrakov and A. I. Erzin, Construction of efficient covering models in the monitoring of extended objects, Vychisl. Tekhnol., 17, No. 1, 26–34, 2012 [Russian].
[3] V. S. Brusov and S. A. Piyavskii, A computational algorithm for optimally covering a plane region, Zh. Vychisl. Mat. Mat. Fiz., 11, No. 2, 304–312, 1971 [Russian]. Translated in USSR Comput. Math. Math. Phys., 11, No. 2, 17–27, 1971.
[4] Sh. I. Galiev and M. A. Karpova, Optimization of multiple covering of a bounded set with circles, Zh. Vychisl. Mat. Mat. Fiz., 50, No. 4, 757–769, 2010 [Russian]. Translated in Comput. Math. Math. Phys., 50, No. 4, 721–732, 2010.
[5] Sh. I. Galiev and A. V. Khorkov, Multiple circle coverings of an equilateral triangle, square, and circle, Diskretn. Anal. Issled. Oper., 22, No. 6, 5–28, 2015 [Russian].
[6] 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, No. 2, 22–46, 2000 [Russian].
[7] N. N. Kuzyurin, On the complexity of asymptotically optimal coverings and packing, Dokl. Akad. Nauk, 363, No. 1, 11–13, 1998 [Russian]. Translated in Dokl. Math., 58, No. 3, 345–346, 1998.
[8] I. Kh. Sigal and A. P. Ivanova, Introduction to Applied Discrete Programming: Models and Computational Algorithm, Fizmatlit, Moscow, 2002 [Russian].
[9] M. Yu. Khachai and M. I. Poberii, Computational complexity and approximability of a series of geometric covering problems, Tr. Inst. Mat. Mekh., 18, No. 3, 247–260, 2012 [Russian]. Translated in Proc. Steklov Inst. Math., 284, Suppl. 1, S87–S95, 2014.
[10] H. M. Ammari, Challenges and Opportunities of Connected $k$-Covered Wireless Sensor Networks: From Sensor Deployment to Data Gathering, Springer, Heidelberg, 2009 (Stud. Comput. Intell., Vol. 215).
[11] T. Andersen and S. Tirthapura, Wireless sensor deployment for 3D coverage with constraints, Proc. 6th Int. Conf. Networked Sensing Syst., Pittsburgh, USA, June 17–19, 2009, pp. 78–81, IEEE, Piscataway, 2009.
[12] S. N. Astrakov, Coverings of sets with restrictions on the arrangement of circles, in Optimization and Applications (Proc. VIII Int. Conf. Optim. Methods Appl., Petrovac, Montenegro, Oct. 2–7, 2017), pp. 67–72, RWTH Aachen Univ., Aachen, 2017 (CEUR Workshop Proc., Vol. 1987). Available at http://ceur-ws.org/Vol-1987 (accessed Nov. 15, 2018).
[13] N. A. A. Aziz, K. A. Aziz, and W. Z. W. Ismail, Coverage strategies for wireless sensor networks, Int. J. Electron. Commun. Eng., 3, No. 2, 145–159, 2009.
[14] D. Bertsimas and R. Vohra, Rounding algorithms for covering problems, Math. Program., 80, No. 1, 63–89, 1998.
[15] A. Caprara, M. Fischetti, and P. Toth, A heuristic method for the set covering problem, Oper. Res., 47, No. 5, 730–743, 1999.
[16] A. I. Erzin and S. N. Astrakov, Min-density stripe covering and applications in sensor networks, in Computational Science and Its Applications — ICCSA 2011 (Proc. 2011 Int. Conf. Comput. Sci. Its Appl., Santander, Spain, June 20–23, 2011), Pt. III, pp. 152–162, Springer, Heidelberg, 2011 (Lect. Notes Comput. Sci., Vol. 6784).
[17] G. Fejes Tóth, Multiple packing and covering of the plane with circles, Math. Acad. Sci. Hungar., 27, No. 1–2, 135–140, 1976.
[18] G. Fejes Tóth, Thinnest covering of a circle by eight, nine, or ten congruent circles, in Combinatorial and Computational Geometry, pp. 361–376, Cambridge Univ. Press, New York, 2005 (Math. Sci. Res. Inst. Publ., Vol. 52).
[19] Sh. I. Galiev and M. S. Lisafina, Linear models for the approximate solution of the problem of packing equal circles into a given domain, Eur. J. Oper. Res., 230, 505–514, 2013.
[20] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979. Translated under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Mir, Moscow, 1982.
[21] N. G. Hall and D. S. Hochbaum, A fast approximation algorithm for the multicovering problem, Discrete Appl. Math., 15, No. 1, 35–40, 1986.
[22] A. Hawbani, X. F. Wang, N. Husaini, and S. Karmoshi, Grid coverage algorithm & analysis for wireless sensor networks, Netw. Protoc. Algorithms, 6, No. 4, 65–81, 2014.
[23] A. Heppes and H. Melissen, Covering a rectangle with equal circles, Period. Math. Hung., 34, No. 1–2, 65–81, 1997.
[24] D. S. Hochbaum and W. Maass, Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM, 32, No. 1, 130–136, 1985.
[25] C. F. Huang and Y. C. Tseng, A survey of solutions to the coverage problems in wireless sensor networks, J. Internet Technol., 6, No. 1, 1–8, 2005.
[26] J. E. Kim, J. Han and C. G. Lee, Optimal 3-coverage with minimum separation requirements for ubiquitous computing environments, Mob. Netw. Appl., 556–570, 2009.
[27] S. Krotoszynski, Covering a disk with smaller disks, Stud. Sci. Math. Hung., 28, No. 3–4, 277–283, 1993.
[28] S. Kumar, T. H. Lai, and J. Balogh, On $k$-coverage in a mostly sleeping sensor network, in Proc. 10th Annu. Int. Conf. Mob. Comput. Netw., pp. 144–158, ACM, New York, 2004.
[29] N. Megiddo and K. J. Supowit, On the complexity of some common geometric location problems, SIAM J. Comput., 13, No.1, 182–196, 1984.
[30] H. Melissen, Loosest circle coverings of an equilateral triangle, Math. Mag., 70, No. 2, 118–124, 1997.
[31] J. B. M. Melissen and P. C. Schuur, Improved coverings of a square with six and eight equal circles, Electron. J. Comb., 3, No. 1/R32, 1–10, 1996. Available at http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r32 (accessed Nov. 20, 2018).
[32] J. B. M. Melissen and P. C. Schuur, Covering a rectangle with six and seven circles, Discrete Appl. Math., 99, No. 1–3, 149–156, 2000.
[33] K. J. Nurmela, Covering a circle by congruent circular discs, Prepr. Helsinki Univ. Technol., Helsinki Univ. Technol., Helsinki, 1998.
[34] K. J. Nurmela, Conjecturally optimal coverings of an equilateral triangle with up to 36 equal circles, Exp. Math., 9, No. 2, 241–250, 2000.
[35] K. J. Nurmela and P. R. J. Östergård, Covering a square with up to 30 equal circles, Res. Rep. 62, Helsinki Univ. Technol., Helsinki, Finland, 2000. Available at http://www.tcs.hut.fi/old/reports/A62abstract.html (accessed Nov. 20, 2018).
[36] A. Suzuki and Z. Drezner, The minimum number equitable radius location problems with continuous domain, Eur. J. Oper. Res., 195, No. 1, 17–30, 2009.
[37] T. Tabirca, L. T. Yang, and S. Tabirca, Smallest number of sensors for $k$-covering, Int. J. Comput. Commun. Control, 8, No. 2, 312–319, 2013.
[38] T. Tarnai and Zs. Gáspár, Covering a square by equal circles, Elem. Math., 50, 167–170, 1995.
[39] S. Umetani and M. Yagiura, Relaxation heuristics for the set covering problem, J. Oper. Res. Soc. Jpn., 50, No. 4, 350–375, 2007.
[40] B. Wang, Coverage problems in sensor networks: A survey, J. ACM Comput. Surv., 43, No. 4, 167–170, 2011.
[41] S. Yang, F. Dai, M. Cardei, J. Wu, and F. Patterson, On connected multiple point coverage in wireless sensor networks, Int. J. Wirel. Inf. Netw., 13, No. 4, 289–301, 2006.
[42] N. Yeasmin, $k$-coverage problems and solutions in wireless sensor networks: A survey, Int. J, Comput. Appl., 100, No. 17, 1–6, 2014.
