无线传感网络覆盖算法的研究进展

徐会彬

无线传感网络覆盖算法的研究进展

徐会彬

（湖州师范学院 信息工程学院，浙江 湖州 313000）

为了进一步研究无线传感网络(WSNs)应用中的传感节点覆盖问题，对相关技术性能和研究进展进行了阐述：对WSN进行多维分类，给出全覆盖、部分覆盖的概念；着重分析近年来具有代表性的部分覆盖技术及其优缺点，并从覆盖度、节点分布特性、节点类型以及网络拓扑结构4个方面进行比较分析；最后，总结出部分覆盖技术的未来可能的研究策略与突破方向。

无线传感网；网络分类；全覆盖；部分覆盖；覆盖度

0 引言

无线传感网络（wireless sensor networks, WSNs）由大量的传感节点构成，且通过这些节点观察或测量环境[1]，或者检测事件的发生，再将感测数据传输至基站（信宿）[2]。依据节点部署类型、部署策略、网络结构、节点移动、所需的覆盖类型以及感测模型，可将WSNs划分为不同的类型，即静态[3]、移动的[4]、混合[5]以及移动机器人[6-7]等，如图1所示。在静态的WSNs(S-WSNs)中，所部署的节点均是静态；相反，如果所有节点是移动的，则称为移动WSN（M-WSN）；若既有静态的，也有移动节点，则称为混合（H-WSN）。机器人能够携带静态节点，而不是静态节点，则称为无线传感和机器人网络（WSRN）。

依据节点的分布类型，可将WSN划分为随机WSN[8]和确定性WSN[9]。在有些环境中，如灾难区域，相比于决定性部署，随机部署传感节点更便利。

若依据WSN结构，可将WSN划分为平坦结构和簇结构。相比平坦结构，簇结构更简单，更利于数据传输[10]。

图1 WSNs的分类

移动是影响WSN覆盖的另一个因素[11]。所谓移动是指部署后节点改变了自己的位置。无意移动会导致覆盖空洞[12]；相反，有意移动可以提高覆盖率、连通率，甚至提高网络寿命[13]。

覆盖是WSN应用的基础。所谓覆盖是指利用部署的传感节点感测兴趣区域的每点信息。因此，也将覆盖称为服务质量（quality of service, QoS）。同时，覆盖也可据类型和等级进行划分。

尽管可以预设传感节点的位置进而获取高的覆盖率，但是，多数应用区域是偏远且危险的。在这种情况下，只能随机部署传感节点。然而，随机部署传感节点难以保持覆盖率。导致覆盖率低的另一个原因是传感节点失效，如能耗殆尽或硬件问题。一旦节点失效，就会形成覆盖空洞。

本文在分析WSN的分类基础上，讨论覆盖问题并进行分类；然后着重分析了部分覆盖技术，并将具有代表性的技术进行比较。

1 WSN覆盖问题的研究工作

目前，研究人员从不同角度讨论了覆盖问题。有些研究人员面向SWSN提出了基于能效的覆盖算法，而有些研究人员面向MWSN，从维持连接和延长网络寿命的角度提出覆盖算法。图2对目前有关覆盖问题的研究工作的视角进行了归类。

有些研究人员从移动和静态角度讨论覆盖问题，如图2最外层所示。也有部分研究人员从移动模型、连通和寿命、应用、感测模型和覆盖类型讨论覆盖问题。

图2 现存覆盖问题的研究工作

图3 覆盖分类

1.1 全覆盖问题

1.2 部分覆盖问题

1.2.1 Point覆盖

Point覆盖又可分为Focused 覆盖和Target覆盖。在有些应用中，如污染监测，靠近某事件的区域覆盖比远区域覆盖具有更高的优先权，这类覆盖称为Focused 覆盖（F-Coverage）[15]。在文献[15]中，作者提出了2个定位自部署算法，即贪婪优先（greedy advance, GA）和贪婪-旋转-贪婪算法（greedy-rotation-greedy, GRG）。这2个算法使用等边三角形棋盘形布置（equilateral triangle tessellation）最大化兴趣区域的覆盖率，并维持网络连通率。这2个算法对节点失败具有很强的鲁棒性。然而GRG并没有保证最大覆盖半径。

此外，研究人员也使用移动节点去获取F-Coverage。例如，文献[16]分析了利用机器人去修复覆盖空洞的性能，并提出基于运载的覆盖增强协议（carrier-based coverage augmentation protocol, CBCA）。CBCA通过机器人将静态节点移至失效节点的位置，进而弥补未被覆盖的位置。

Target覆盖是指对已知位置的静态目标进行连续覆盖。目前，研究人员针对S-WSN的Target覆盖进行大量的分析与讨论[17]。

在文献[18]中，作者利用移动特性去提高Target覆盖，并讨论了移动节点的移动策略，进而减少检测时延。同时，将移动节点和静态节点结合。此外，文献[19-20]分析了静态目标的问题，提出了光谱多尺度（spectral multiscale）覆盖算法。文献[21]分析了移动目标覆盖而不是静态目标覆盖，并提出了动态光谱多尺度覆盖（spectral multiscale coverage, SMC）算法。而文献[22]提出了基于移动节点的目标覆盖算法：移动节点调整自己位置去提高覆盖率，并向未覆盖的目标移动。

1.2.2 Path覆盖

Barrier覆盖更适合于入侵检测和边界监测应用[23-25]。在这类应用中，要求传感节点监测“腰带”（belt）区域。文献[25]提出基于虚力的-Barrier覆盖。该算法试图利用闭合的belt区域的节点数实现-Barrier覆盖，同时分析了该算法在静态边界比动态边界的收敛时间更低。此外，文献[26]提出了分布式动作协调算法，其利用移动节点提高Barrier覆盖的初始部署，随后保持静态。

Sweep覆盖是指要求周期性地监测一些点区域。例如，文献[27]作者讨论了预定兴趣点（points of interest, PoI）的Sweep覆盖问题。而文献[28]对此问题进行了扩展，在动态而不是静态POIs的H-WSN讨论了Sweep问题。此外，文献[29]提出巡逻点算法（patrol point algorithm, PPA）。同时，文献[30]提出了2个启发式算法，即MinExpand和OSweep。

文献[31]讨论了平台的线部Sweep覆盖，并提出基于移动节点的线Sweep的覆盖算法。此外，文献[32]提出了基于时限目标巡逻（time-constrained targets patrolling, TCTP）的算法。TCTP算法给每个目标分配一个权值，且移动节点依据它的权值巡逻监视每个目标。然而该算法的性能受到巡逻路径的影响。为此，文献[33]强调了文献[32]的不足，并提出基于时限权重的目标巡逻（TCWTP）机制。TCWTP算法构建了不止一条巡逻路径。

1.3 Trap覆盖

2 性能分析

接下来从覆盖度、特性（集中C、分布D）、传感节点类型（同构HM、异构HT）、移动（H）、混合（H）、机器人（R）以及网络拓扑（平坦（F）、簇（CL））等方面分析现存的部分覆盖相关的文献工作，如表1所示。

表1 现在的部分覆盖算法性能

续表1

3 结束语

本文首先分析了WSNs的分类，然后对WSNs的覆盖技术进行了讨论与分析。随后，对部分覆盖技术进行分类，并对各类型中具有代表性的技术进行分析和比较。通过本文分析可知，理想的部分覆盖技术应具有以下特点：采用分布式而非集中式；保证网络的连通；满足兴趣区域的覆盖要求；扩展性强。总之，目前国内外针对不同的WSNs应用场景提出较多的部分覆盖技术，但是在部分覆盖技术的研究领域中，仍有较多的问题需要解决，新的研究方向还有待发现。

[1] 唐林俊. 无线传感网络中部分覆盖与拟连通冗余节点的研究[J]. 传感技术学报, 2011, 24(6): 895-901.

[2] 班冬松, 温俊, 蒋杰, 等. 移动无线传感网络-栅栏覆盖的构建算法[J]. 软件学报, 2011, 22(9): 2089-2103.

[3] CARDEI M, THAI M T, LI Yingshu, et al. Energy-efficient target coverage in wireless sensor networks[EB/OL]. [2019-01-27]. http://www.cse.fau.edu/~mihaela/HTML/PAPERS/TCinfocom05.pdf.

[4] YANMAZ E, GUCLU H. Stationary and mobile target detection using mobile wireless sensor networks[EB/OL]. [2019-01-27]. https://mobile.aau.at/publications/yanmaz-2010-infocom-event-detection.pdf.

[5] OZTURK C, KARABOGA D, GORKEMLI B. Probabilistic dynamic deployment of wireless sensor networks by artificial bee colony algorithm[J]. Sensors, 2011, 11(6): 6056-6065.

[6] CHANG C Y, CHANG C T, CHEN Y C, et al. Obstacle-resistant deployment algorithms for wireless sensor networks[J]. IEEE Transaction Vehicle Technology, 2014, 58(6): 2925-2941.

[7] MEI Yongguo, XIAN Changjiu, DAS S et al. Sensor replacement using mobile robots[J]. Computing Communication, 2016, 30(13): 2615-2626.

[8] AHMED N, KANHERE S S, JHA S. Probabilistic coverage in wireless sensor networks[EB/OL]. [2019-01-27]. https://www.researchgate.net/publication/221081089_Probabilistic_Coverage_in_Wireless_Sensor_Networks.

[9] JUANG P, OKI H, WANG Y. Energy-efficient computing for wildlife tracking:design tradeoffs and early experiences with zebranet[J]. SIGARCH Computing Architecture News, 2013, 30(5): 96-107.

[10] LIAO W H, KAO Y, WU R T. Ant colony optimization based sensor deployment protocol for wireless sensor networks[J]. Expert System Application, 2014, 38(6): 6599-6605.

[11] BARTOLINI N, CALAMONERI T, PORTA T L, et al. Mobile sensor deployment in unkown fields[EB/OL]. [2019-01-27]. https://www.researchgate.net/publication/224137107_Mobile_Sensor_Deployment_in_Unknown_Fields.

[12] LUO J, WANG D, ZHANG Q. Double mobility: coverage of the sea surface with mobile sensor networks[EB/OL]. [2019-01-27]. http://www4.comp.polyu.edu.hk/~csdwang/Publication/INFOCOM09-Double.pdf.

[13] RÖMER K, MATTERN F. The design space of wireless sensor networks[EB/OL]. [2019-01-27]. http://www.vs.inf.ethz.ch/publ/papers/wsn-designspace.pdf

[14] WU Yiwei, AI Chunyu, GAO Shan, et al. P-percent coverage in wireless sensor networks[EB/OL]. [2019-01-27]. https://grid.cs.gsu.edu/yli/papers/S-wasa08.pdf.

[15] LI X, FREY H, SANTORO N, et al. Focused-coverage by mobile sensor networks[EB/OL]. [2019-01-27]. http://people.scs.carleton.ca/~santoro/Reports/mass09.pdf.

[16] FALCON R, LI X, NAYAK A. Carrier-based coverage augmentation in wireless sensor and robot networks[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of IEEE 30th International Conference on Distributed Computing Systems Workshops. Genova, Italy: IEEE, 2015: 234-239.

[17] WANG Jianxin, LIU Ming, LU Mingming, et al. Target coverage algorithms with multiple sensing ranges in wireless sensor networks[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of 2010 Military Communications Conference. San Jose, CA: IEEE, 2010: 130-135.

[18] TAN Rui, XING Guoliang, WANG Jianping, et al. Collaborative target detection in wireless sensor networks with reactive mobility[EB/OL]. [2019-01-27]. https://www.ntu.edu.sg/home/tanrui/pub/mobidetect-IWQoS.pdf.

[19] MATHEW G, MEZIĆ I. Spectral multiscale coverage: a uniform coverage algorithm for mobile sensor networks[EB/OL]. [2019-01-27]. http://www.geoggy.net/resources/SMC_CDC09.pdf.

[20] MATHEW G, MEZIĆ I. Metrics for ergodicity and design of ergodic dynamics for multi-agent systems[J]. Physica D, 2013, 240(45): 432-442.

[21] MATHEW G, SURANA A, MEZIĆ I. Uniform coverage control of mobile sensor networks for dynamic target detections[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of the 49th IEEE Conference on Decision and Control. Atlanta, GA: IEEE, 2015: 7292-7299.

[22] LIAO Zhuofan, ZHANG Shigeng, CAO Jiannong, et al. Minimizing movement for target coverage in mobile sensor networks[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of the 32nd International Conference on Distributed Computing Systems Workshops. Macau, China: IEEE, 2012: 194-200.

[23] GHOSH A, DAS S K. Coverage and connectivity issues in wireless sensor networks: a survey[J]. Pervasive Mobile Computing, 2014, 4(3): 303-334。

[24] 范兴刚, 王超, 杨静静, 等. 一种基于选择框的有向K-栅栏构建算法[J]. 计算机学报, 2016, 39(5): 946-961.

[25] KONG Linghe, LIU Xuemei, LI Zhi, et al. Automatic barrier coverage formation with mobile sensor networks[EB/OL]. [2019-01-27]. http://wirelesslab.sjtu.edu.cn/~klh/2012AndBefore/KongICC2010BarrierCoverageFormation.pdf.

[26] CHENG T M, SAVKIN A V. Decentralized control of a mobile sensor network for deployment in corridor coverage[EB/OL]. [2019-01-27]. https://www.researchgate.net/publication/221042848_Decentralized_control_of_ a_mobile_sensor_network_for_deployment_in_corridor_coverage.

[27] LI Mo, CHENG Weifang, LIU Kebin, et al. Sweep coverage with mobile sensors[J]. IEEE Transactions on Mobile Computing, 2014, 10(11): 1534-1545.

[28] XI Min, WU Kui, QI Yong, et al. Run to potential: sweep coverage in wireless sensor networks[EB/OL]. [2019-01-27].https://dspace.library.uvic.ca/bitstream/handle/1828/2615/Run%20to%20potential%20Sweep%20coverage% 20in%20wireless%20sensor%20networks.pdf?sequence=1&isAllowed=y.

[29] CHU H C, WANG W K, LAI Y H. Sweep coverage mechanism for wireless sensor networks with approximate patrol times[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of the 7th International Conference on Ubiquitous Intelligence Computing and 7th International Conference on Autonomic Trusted Computing. Xi'an, China: IEEE, 2013: 82-87.

[30] DU Junzhao, LI Yawei, LIU Hui , et al. On sweep coverage with minimum mobile sensors[EB/OL]. [2019-01-27]. http://mail.tku.edu.tw/jingo/wireless/paper/4-30.pdf.

[31] GORAIN B, MANDAL P S. Line sweep coverage in wireless sensor networks[C]//The Institute of Electrical and Electronic Engineers（IEEE）. Proceedings of the 6th International Conference on Communication Systems and Networks. Bangalore, India: IEEE, 2014: 1-6.

[32] WU T L, CHANG C Y. Path construction and visit scheduling for targets by using data mules[J]. IEEE Transaction System, 2014, 44(10): 1289-1300.

[33] CHANG C Y, CHEN G. Time-constrained weighted targets patrolling mechanism in wireless mobile sensor networks[J]. IEEE Transaction System, 2015, 45(6): 901-914.

[34] BALISTER P, ZHENG Zizhan, KUMAR S, et al. Trap coverage: allowing coverage holes of bounded diameter in wireless sensor networks[EB/OL]. [2019-01-27]. https://www.memphis.edu/cs/santosh-kumar/papers/trap-coverage.pdf.

[35] CHEN J, LI J.Trapping mobile targets in wireless sensor networks: an energy-efficient perspective[J]. IEEE Transaction Vehicle Technology, 2013, 62(7): 3287-3300.

Research progress of partial coverage algorithm in wireless sensor networks

XU Huibin

（School of Information Engineering, Huzhou University, Huzhou, Zhejiang 313000, China）

In order to further study on the coverage of deployed sensors in the application of WSNs, the paper discussed the related technology and development: the multidimensional classification of WSNs was given, and the concepts of full coverage and partial coverage were introduced; then the existing representative partial coverage algorithms for WSNs were summarized with their advantages and disadvantages, and the four aspects of coverage degree, distribution characteristics, sensor types and network topology were comparatively analyzed; finally, the possible research direction and trends of partial coverage algorithms were prospected.

wireless sensor network; network classification; full coverage; partial coverage; coverage degree

P228

A

2095-4999(2019)04-0019-05

徐会彬.无线传感网络覆盖算法的研究进展[J].导航定位学报,2019,7(4): 19-23.（XU Huibin.Research progress of partial coverage algorithm in wireless sensor networks[J].Journal of Navigation and Positioning,2019,7(4): 19-23.）

10.16547/j.cnki.10-1096.20190404.

2019-03-03

湖州师范学院博士启动基金项目（RK24051）；湖州师范学院科研基金项目（KX24086）。

徐会彬，男（1982—），博士，讲师，研究方向为VANET安全技术/路由技术。