Том 22, номер 4, 2015 г., Стр. 21–34

УДК 519.7
Ерзин А. И., Шабельникова Н. А.
О плотности покрытия полосы одинаковыми секторами

Аннотация:
Исследуется задача построения наименее плотного регулярного покрытия полосы с использованием одинаковых секторов, которая возникает при проектировании сенсорных сетей. Предложены три модели покрытия, и проведён их сравнительный анализ, что позволило, в частности, получить оценку сверху на минимальную плотность покрытия полосы секторами.
Табл. 1, ил. 6, библиогр. 21.

Ключевые слова: регулярное покрытие, минимизация плотности, сенсорная сеть.

DOI: 10.17377/daio.2015.22.475

Ерзин Адиль Ильясович ^1,2
Шабельникова Наталья Андреевна ¹
1. Институт математики им. С. Л. Соболева
пр. Коптюга, 4, 630090 Новосибирск, Россия 
2. Новосибирский гос. университет
ул. Пирогова, 2, 630090 Новосибирск, Россия
e-mail: adilerzin@math.nsc.ru, kriagell@gmail.com

Статья поступила 12 февраля 2015 г.
Исправленный вариант — 13 мая 2015 г.

Литература

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

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

[3] Астраков С. Н., Ерзин А. И. Сенсорные сети и покрытие полосы эллипсами // Вычисл. технологии. 2013. Т. 18, № 2. С. 3–11.

[4] Астраков С. Н., Ерзин А. И., Залюбовский В. В. Сенсорные сети и покрытие плоскости кругами // Дискрет. анализ и исслед. операций. 2009. Т. 16, № 3. С. 3–19.

[5] Ерзин А. И. Сенсорные сети и наименее плотные покрытия // Прикл. математика и фундамент. информатика. 2014. № 1. С. 89–97.

[6] Тот Л. Ф. Расположения на плоскости, на сфере и в пространстве. М.: Физматлит, 1958. 365 с.

[7] Ai J., Abouzeid A. A. Coverage by directional sensors in randomly deployed wireless sensor networks // J. Comb. Optim. 2006. Vol. 11, No. 1. P. 21–41.

[8] Cardei M., Wu J., Lu M. Improving network lifetime using sensors with adjustable sensing ranges // Int. J. Sens. Netw. 2006. Vol. 1, No. 1/2. P. 41–49.

[9] Deshpande N., Shaligram A. Energy saving in WSN with directed connectivity // Wireless Sens. Netw. 2013. Vol. 5, No. 6. P. 121–126.

[10] Erzin A. I., Astrakov S. N. Covering a plane with ellipses // Optimization. 2013. Vol. 62, No. 10. P. 1357–1366.

[11] Erzin A., Shabelnikova N. Optimal regular covering of the plane with equal sectors // Proc. 20th Conf. of the Int. Fed. Oper. Res. Soc. (IFORS 2014) (Barcelona, Spain, July 13–18, 2014). Barcelona: IFORS, 2014. P. 69.

[12] Erzin A. I., Shabelnikova N. A. Covering a plane with equal sectors // Proc. V Int. Conf. “Optimization and applications” (OPTIMA–2014), (Petrovac, Montenegro, Sept. 28 – Oct. 4, 2014). Moscow: VC RAN, 2014. P. 64–65.

[13] Fan G., Jin S. Coverage problem in wireless sensor network: а survey // J. Netw. 2010. Vol. 5, No. 9. P. 1033–1040.

[14] Guvensan M. A., Yavuz A. G. On coverage issues in directional sensor networks: A survey // Ad Hoc Netw. 2011. Vol. 9, No. 7. P. 1238–1255.

[15] Han X., Cao X., Lloyd E. L., Shen Ch.-Ch. Deploying directional sensor networks with guaranteed connectivity and coverage // 5th Ann. IEEE Commun. Soc. Conf. Sensor, Mesh and Ad Hoc Communications and Networks (San Francisco, USA, June 16–20, 2008). Piscataway, USA: IEEE, 2008. P. 153–160.

[16] Ismailescu D., Kim B. Packing and covering with centrally symmetric convex disks // Discrete Comput. Geom. 2014. Vol. 51, No. 2. P. 495–508.

[17] Liu L., Zhang X., Ma H. Exposure-path prevention in directional sensor networks using sector model based percolation // IEEE Int. Conf. Communications (Dresden, June 14–18, 2009). Piscataway: IEEE, 2009. P. 274–278.

[18] Nguyen N. D., Zalyubovskiy V. V., Ha M. Th., Le T. D., Choo H. Energy-efficient models for coverage problem in sensor networks with adjustable ranges // Ad Hoc. Sens. Netw. 2012. Vol. 16, No. 1–3. P. 1–28.

[19] Sengupta S., Das S., Nasir M. D., Panigrahi B. K. Multi-objective node deployment in WSNs: In search of an optimal trade-off among coverage, lifetime, energy consumption, and connectivity // Eng. Appl. Artif. Intell. 2013. Vol. 26, No. 1. P. 405–416.

[20] Wang W., Srinivasan V., Wang B., Chua K.-Ch. Coverage for target localization in wireless sensor networks // IEEE Trans. Wireless Communications. 2008. Vol. 7, No. 2. P. 667–676.

[21] Zalyubovskiy V. V., Erzin A. I., Astrakov S. N., Choo H. Energy-efficient area coverage by sensors with adjustable ranges // Sensors. 2009. Vol. 9, No. 4. P. 2446–2460.