[1] Ma Wenyu, Yan Feng, Zuo Xuzhou, Xia Weiwei, et al. Coordinate-free k-coverage hole detection algorithmin wireless sensor networks [J]. Journal of Southeast University (English Edition), 2019, 35 (1): 8-15. [doi:10.3969/j.issn.1003-7985.2019.01.002]

Copy

Coordinate-free k-coverage hole detection algorithmin wireless sensor networks()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

35

Issue:

2019 1

Page:

8-15

Research Field:

Information and Communication Engineering

Publishing date:

2019-03-30

Info

Title:

Coordinate-free k-coverage hole detection algorithmin wireless sensor networks

Author(s):

Ma Wenyu¹;  Yan Feng¹;  Zuo Xuzhou²;  Xia Weiwei¹;  Shen Lianfeng¹

¹National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China
²School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China

Keywords:

k-coverage hole detection;  k-coverage;  wireless sensor networks

PACS:

TN915

DOI:

10.3969/j.issn.1003-7985.2019.01.002

Abstract:

For wireless sensor networks, a simple and accurate coordinate-free k-coverage hole detection scheme is proposed. First, an algorithm is presented to detect boundary cycles of 1-coverage holes. The algorithm consists of two components, named boundary edge detection and boundary cycle detection. Then, the 1-coverage hole detection algorithm is extended to k-coverage hole scenarios. A coverage degree reduction scheme is proposed to find an independent covering set of nodes in the covered region of the target field and to reduce the coverage degree by one through sleeping those nodes. Repeat the 1-coverage hole detection algorithm and the higher order of coverage holes can be found. By iterating the above steps for k-1 times, the boundary edges and boundary cycles of all k-coverage holes can be discovered. Finally, the proposed algorithm is compared with a location-based coverage hole detection algorithm. Simulation results indicate that the proposed algorithm can accurately detect over 99% coverage holes.

References:

[1] Huang C, Tseng Y. The coverage problem in a wireless sensor network[J]. Mobile Networks and Applications, 2005, 10(4): 519-528.
[2] Ma H C, Kumar Sahoo P, Chen Y W. Computational geometry based distributed coverage hole detection protocol for the wireless sensor networks[J].Journal of Network and Computer Applications, 2011, 34(5): 1743-1756. DOI:10.1016/j.jnca.2011.06.007.
[3] Tong B, Tavanapong W. On discovering sensing coverage holes in large-scale sensor networks, TR 06-03[R]. Ames, USA: Computer Science, Iowa State University, 2006.
[4] Qiu C, Shen H, Chen K. An energy-efficient and distributed cooperation mechanism for k-coverage hole detection and healing in WSNs[C]//2015 IEEE International Conference on Mobile Ad Hoc and Sensor Systems. Dallas, USA, 2015:73-81. DOI: 10.1109/mass.2015.115.
[5] Dai G, Chen L, Zhou B, et al. Coverage hole detection algorithm based on Voronoi diagram in wireless sensor network [J]. Journal of Computer Applications, 2015, 35(3):620-623.
[6] Li W, Zhang W. Coverage hole and boundary nodes detection in wireless sensor networks[J].Journal of Network and Computer Applications, 2015, 48:35-43. DOI:10.1016/j.jnca.2014.10.011.
[7] Niculescu D. Positioning in ad hoc sensor networks[J].IEEE Network, 2004, 18(4): 24-29. DOI:10.1109/mnet.2004.1316758.
[8] Bejerano Y. Simple and efficient k-coverage verification without location information [C]//2008 IEEE INFOCOM. Phoenix, USA, 2008: 897-905. DOI: 10.1109/infocom.2008.67.
[9] Bejerano Y. Coverage verification without location information[J]. IEEE Transactions on Mobile Computing, 2012, 11(4): 631-643. DOI:10.1109/tmc.2011.85.
[10] Qiu C X, Shen H Y. A delaunay-based coordinate-free mechanism for full coverage in wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(4): 828-839. DOI:10.1109/tpds.2013.134.
[11] Zhang C, Zhang Y C, Fang Y G. Localized algorithms for coverage boundary detection in wireless sensor networks[J]. Wireless Networks, 2009, 15(1):3-20. DOI:10.1007/s11276-007-0021-1.
[12] Kasbekar G S, Bejerano Y, Sarkar S. Generic coverage verification without location information using dimension reduction[J]. ACM Transactions on Networking, 2012, 20(6):1991-2004. DOI:10.1109/tnet.2012.2190620.
[13] Ma W, Yan F, Zuo X, et al. Coverage hole detection algorithm without location information in wireless sensor networks[C]//2017 International Conference on Computer and Communications. Chengdu, China, 2017:357-361.
[14] Tahbaz-Salehi A, Jadbabaie A. Distributed coverage verification in sensor networks without location information[J]. IEEE Transactions on Automatic Control, 2010, 55(8):1837-1849. DOI:10.1109/tac.2010.2047541.
[15] Yan F, Vergne A, Martins P, et al. Homology-based distributed coverage hole detection in wireless sensor networks[J]. ACM Transactions on Networking, 2015, 23(6):1705-1718. DOI:10.1109/tnet.2014.2338355.
[16] Wang X, Xing G, Zhang Y, et al. Integrated coverage and connectivity configuration in wireless sensor networks[C]//2013 International Conference on Embedded Network Sensor Systems. New York, USA, 2003:28-39.
[17] Mistry H P, Mistry N H. RSSI based localization scheme in wireless sensornetworks:A survey[C]//2015 International Conference on Advanced Computing and Communication Technologies. Haryana, India, 2015:647-652.

Memo

Memo:

Biographies: Ma Wenyu(1994—), female, graduate; Yan Feng(corresponding author), male, doctor, associate professor, feng.yan@seu.edu.cn.
Foundation item: The National Natural Science Foundation of China(No.61601122, 61471164, 61741102).
Citation: Ma Wenyu, Yan Feng, Zuo Xuzhou, et al.Coordinate-free k-coverage hole detection algorithm in wireless sensor networks[J].Journal of Southeast University(English Edition), 2019, 35(1):8-15.DOI:10.3969/j.issn.1003-7985.2019.01.002.

Common functions