|Table of Contents|

[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()
无线传感器网络中无坐标信息的k-覆盖空洞检测算法
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
无线传感器网络中无坐标信息的k-覆盖空洞检测算法
Author(s):
Ma Wenyu1, Yan Feng1, Zuo Xuzhou2, Xia Weiwei1, Shen Lianfeng1
1National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China
2School of Information and Software Engineering, University of Electronic Science and Technology of China, Chengdu 610054, China
马文钰1, 燕锋1, 左旭舟2, 夏玮玮1, 沈连丰1
1东南大学移动通信国家重点实验室, 南京 210096; 2电子科技大学信息与软件工程学院, 成都 610054
Keywords:
k-coverage hole detection;  k-coverage;  wireless sensor networks
k-覆盖空洞检测;  k-覆盖;  无线传感器网络
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.
针对无线传感器网络, 提出了一种简单精确且无需坐标信息的k-覆盖空洞检测算法.首先, 提出一种1-覆盖空洞检测算法, 算法由边界线段检测和边界圆周检测2部分组成.然后, 扩展算法至k-覆盖空洞场景.通过在已被节点覆盖的目标区域内寻找一独立覆盖的节点子集, 并休眠该集合内的节点, 使得网络覆盖度减1.此后, 重复1-覆盖空洞检测算法, 发现更高阶的覆盖空洞.迭代上述步骤k-1次, 可以发现所有k-覆盖空洞的边界线段和边界圆周.最后, 将所提算法与基于坐标的覆盖空洞检测算法进行对比, 仿真结果显示, 所提算法可以精确检测99%以上的覆盖空洞.

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.
Last Update: 2019-03-20