Том 26, номер 1, 2019 г., Стр. 33-54

УДК 519.6:519.147
Галиев Ш. И., Хорьков А. В.
О числе и расположении сенсоров для многократного покрытия ограниченной части плоскости

Аннотация:
Предложена методика определения числа сенсоров, их расположения и нахождения приближённых нижних оценок количества сенсоров для многократного покрытия произвольного ограниченного выпуклого замкнутого множества с непустой внутренностью на плоскости. Задача многократного покрытия рассмотрена при наличии ограничений на минимально возможные расстояния между сенсорами, а также при отсутствии таких ограничений. Для решения указанных задач строятся задачи 0–1 линейного программирования (ЛП). Используется эвристический алгоритм решения построенных задач 0–1 ЛП больших размерностей. Приведены результаты численных расчётов, и для некоторых частных случаев выявлено, что найденные числа сенсоров нельзя уменьшить.
Табл. 1, ил. 3, библиогр. 42.

Ключевые слова: сенсорные сети, многократное покрытие, $k$-кратное покрытие, $k$-покрытие кругами заданного радиуса, число сенсоров для мониторинга заданной области, расположение сенсоров.

DOI: 10.33048/daio.2019.26.609

Галиев Шамиль Ибрагимович ¹
Хорьков Александр Владимирович ¹
1. Казанский национальный исследовательский технический университет им. А. Н. Туполева,
ул. К. Маркса, 10, 420011 Казань, Россия
е-mail: sh.galiev@mail.ru, aLex22fcrk@yandex.ru

Статья поступила 7 февраля 2018 г.
После доработки — 22 октября 2018 г.
Принята к публикации 28 ноября 2018 г.

Литература

[1] Алдын-оол Т. А., Ерзин А. И., Залюбовский В. В. Покрытие плоской области случайно распределенными сенсорами // Вестн. НГУ. Сер. Математика, механика, информатика. 2010. Т. 10, 4. C. 7–25.

[2] Астраков С. Н., Ерзин А. И. Построение эффективных моделей покрытия при мониторинге протяженных объектов // Вычисл. технологии. 2010. Т. 17, № 1. С. 26–34.

[3] Брусов В. С., Пиявский С. А. Вычислительный алгоритм оптимального покрытия плоских областей // Журн. вычисл. математики и мат. физики. 1971. Т. 11, № 2. С. 304–312.

[4] Галиев Ш. И., Карпова М. А. Оптимизация многократного покрытия ограниченного множества кругами // Журн. вычисл. математики и мат. физики. 2010. Т. 50, № 7. С. 757–769.

[5] Галиев Ш. И., Хорьков А. В. Многократные покрытия кругами равностороннего треугольника, квадрата и круга // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 6. С. 5–28.

[6] Еремеев А. В., Заозёрская Л. А., Колоколов А. А. Задача о покрытии множества: сложность, алгоритмы, экспериментальные исследования // Дискрет. анализ и исслед. операций. 2009. Т. 7, № 2. С. 22–46.

[7] Кузюрин Н. Н. О сложности построения асимптотически оптимальных покрытий и упаковок // Докл. РАН. 1998. T. 363, № 1. С. 11–13.

[8] Сигал И. Х., Иванова А. П. Введение в прикладное дискретное программирование: модели и  вычислительные алгоритмы. М.: Физматлит. 2002. С. 240.

[9] Хачай М. Ю., Поберий М. И. Вычислительная сложность и аппроксимируемость серии геометрических задач о покрытии // Тр. ин-та математики и механики УРО РАН. 2012. Т. 18, № 3. С. 247–260.

[10] Ammari H. M. Challenges and opportunities of connected $k$-covered wireless sensor networks. Berlin; Heidelberg: Spinger-Verl. 2009. P. 342.

[11] Andersen T., Tirthapura S. Wireless sensor deployment for 3D coverage with constraints // Proc. 6th Int. Conf. Networked Sensing Systems. Pittsburg, 2009. P. 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). published at www.ceur-ws.org. 2017. P. 67–72.

[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. 2009. Vol. 3, No. 2. P. 145–159.

[14] Bertsimas. D., Vohra. R. Rounding algorithms for covering problems // Math. Program. 1998. Vol. 80. P. 63–89.

[15] Caprara A., Fischetti M., Tóth P. A heuristic method for the set covering problem // Oper. Res. 1999. Vol. 47. P. 730–743.

[16] Erzin A., Astrakov S. Min-density stripe covering and applications in sensor networks // Lect. Notes Comput. Sci. 2011. Vol. 6784. P. 152–162.

[17] Fejes Tóth G. Multiple packing and covering of the plane with circles // Acta Math. Acad. Sci. Hungar. 1976. Vol. 27, No. 1–2. P. 135–140.

[18] Fejes Tóth G. Thinnest covering of circle by eight, nine and ten congruent circles // Comb. Comput. Geom. 2005. Vol. 52. P. 361–376.

[19] Galiev Sh. I., Lisafina М. S. Linear models for the approximate solution of the problem of packing equal circles into a given domain // Eur. J. Oper. Res. 2013. Vol. 230. P. 505–514.

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

[21] Hall N., Hochbaum D. A. A fast approximation algorithm for the multicovering problem // Discrete Appl. Math. 1989. Vol. 15. P. 35–40.

[22] Hawbani A., Wang X. F., Husaini N., Karmoshi S. Grid coverage algorithm & analysis for wireless sensor networks // Netw. Protocols Algorithms. 2014. Vol. 6, No. 4. P. 65–81.

[23] Heppes A., Melissen H. Covering a rectangle with equal circles // Period. Math. Hungar. 1997. Vol. 34. P. 65–81.

[24] Hochbaum D. S., Maass W. Approximation schemes for covering and packing problems in image processing and vlsi // J. ACM. 1985. Vol. 32, No. 1. P. 130–136.

[25] Huang C. F., Tseng Y. C. A survey of solutions to the coverage problems in wireless sensor networks // J. Internet Technology. 2005. Vol. 6, No. 1. P. 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. P. 556–570.

[27] Krotoszynski S. Covering a disk with smaller disks // Studia Sci. Math. Hungar. 1993. Vol. 28, No. 3–4. P. 277–283.

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

[29] Megiddo N. On the complexity of some common geometric location problems // SIAM J. Comput. 1984. Vol. 13. P. 182–196.

[30] Melissen J. B. M. Loosest circle coverings of an equilateral triangle // Math. Mag. 1997. Vol. 70. P. 119–125.

[31] Melissen J. B. M., Schuur P. C. Improved coverings of a square with six and eight equal circles // Electron. J. Comb. 1996. Vol. 3 R32. P. 10 (electronic).

[32] Melissen J. B. M., Schuur P. C. Covering a rectangle with six and seven circles // Discrete Appl. Math. 2000. Vol. 99. P. 149–156.

[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. 2000. Vol. 9. P. 241–250.

[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.

[36] Suzuki A., Drezner Z. The minimum number equitable radius location problems with continuous domain // Eur. J. Oper. Res. 2009. P. 17–30.

[37] Tabirca T., Yang L. T., Tabirca S. Smallest number of sensors for $k$-covering // Int. J. Comput. Commun. 2013. Vol. 8. P. 312–319.

[38] Tarnai T., Gáspár Zs. Covering a square by equal circles // Elem. Math. 1995. Vol. 50. P. 167–170.

[39] Umetani S., Yagiura M. Relaxation heuristics for the set covering problem // J. Oper. Res. Soci. Jap. 2007. Vol. 50, No. 4. P. 350–375.

[40] Wang B. Coverage problems in sensor networks: a survey // J. ACM Comput. Surv. (CSUR). 2011. Vol. 43. P. 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. 2006. Vol. 13, No. 4. P. 289–301.

[42] Yeasmin N. k-Coverage problems and solutions in wireless sensor networks: a survey // Int. Jo. Comput. Appl. 2014. Vol. 100, No. 17. P. 1–6.