Volume 22, No 4, 2015, P. 21-34

UDC 519.7
Erzin A. I., Shabelnikova N. A.
About density of a covering of a strip with identical sectors

Abstract:
We study the problem of constructing a regular covering of a strip of the least density with the identical sectors that arises in design of wireless sensor networks. Three coverage models are proposed and the comparative analysis was performed that allowed us to obtain, in particular, an upper bound on the minimum density of a covering of a strip with sectors.
Tab. 1, ill. 6, bibliogr. 21.

Keywords: regular coverage, minimization of density, sensor networks.

DOI: 10.17377/daio.2015.22.475

Adil I. Erzin ^1,2
Natalia A. Shabelnikova ¹
1. Sobolev Institute of Mathematics
4 Koptyug Ave., 630090 Novosibirsk, Russia
2. Novosibirsk State University
2 Pirogov St., 630090 Novosibirsk, Russia
e-mail: adilerzin@math.nsc.ru, kriagell@gmail.com

Received 12 February 2015
Revised 13 May 2015

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.

[2] S. N. Astrakov and A. I. Erzin, Construction of efficient coverage models in the monitoring of extended objects, Vychisl. Tekhnol., 17, No. 1, 26–34, 2012.

[3] S. N. Astrakov and A. I. Erzin, Sensor networks and strip covering with ellipses, Vychisl. Tekhnol., 18, No. 2, 3–11, 2013.

[4] S. N. Astrakov, A. I. Erzin, and V. V. Zalyubovskiy, Sensor networks and covering of plane by discs, Diskretn. Anal. Issled. Oper., 16, No. 3, 3–19, 2009.

[5] A. I. Erzin, Sensor networks and the least dense covers, Prikl. Mat. Fundam. Inform., No. 1, 89–97, 2014.

[6] L. F. Toth, Lagerungen in der Ebene auf der Kugel und im Raum, Springer- Verl., Berlin, 1953. Translated under the title Raspolozheniya na ploskosti, na sfere i v prostranstve, Gos. Izdatel’stvo Fiz.-Mat. Lit., Moscow, 1958.

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

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

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

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

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

[12] A. I. Erzin and N. A. Shabelnikova, Covering a plane with equal sectors, in Proc. V Int. Conf. Optim. Methods Appl. “Optimization and applications”, Petrovac, Montenegro, Sept. 28 – Oct. 4, 2014, pp. 64–65, Dorodnicyn Comput. Cent. RAS, Moscow, 2014.

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

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

[15] X. Han, X. Cao, E. L. Lloyd, and Ch.-Ch. Shen, Deploying directional sensor networks with guaranteed connectivity and coverage, in 5th Annual IEEE Commun. Soc. Conf. Sens., Mesh and Ad Hoc Commun. Netw., San Francisco, USA, June 16–20, 2008, pp. 153–160, IEEE eXpress Conf. Publ., Piscataway, 2008.

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

[17] L. Liu, X. Zhang, and H. Ma, Exposure-path prevention in directional sensor networks using sector model based percolation, in IEEE Int. Conf. on Commun., Dresden, Germany, June 14–18, 2009, pp. 274–278, IEEE eXpress Conf. Publ., Piscataway, 2009.

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

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

[20] W. Wang, V. Srinivasan, B. Wang, and K.-Ch. Chua, Coverage for target localization in wireless sensor networks, IEEE Trans. Wirel. Commun., 7, No. 2, 667–676, 2008.

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