EN|RU
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
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 Received February 7, 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. |
|
![]() |
|
© Sobolev Institute of Mathematics, 2015 | |
![]() |
|