无线传感器网络覆盖算法综述

陈晓东

摘要：无线传感器网络（WSN）是由大量微型，廉价和低功耗传感器节点组成的网络，这些节点之间通过无线通信多跳中继，相互协作完成应用程序任务并将感知数据转发到中央采集汇聚节点。无线传感器广泛应用于环境检测，栖息地检测，精细农业甚至军事领域。无线传感器网络一个很重要的问题是覆盖问题，覆盖问题主要分为三类，分别是区域覆盖，目标覆盖以及栅栏覆盖，下文分别对此三类覆盖方式做一个综述。

关键词：WSN；覆盖算法；节点调度

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2019）06-0023-02

1 无线传感器网络覆盖算法

1.1 目标覆盖

目标覆盖是针对监测区域内某些特定的目标进行监测，又称为点覆盖，如图1所示，为了保证覆盖质量，通常需要每一个监测对象被最少一个传感器节点所感知，目标覆盖的主要应用领域在于军事领域。

（1）Saint_Louis[1]提出了一种基于权重的遗传算法，该论文解决了传感器节点集合最大化问题，从文献中分析了一些经典算法，并且提出了一个全新的集中式的思路，新算法的名称称为基于权重的贪婪算法，通过将传感器节点分为多个集合，并且保证每个集合满足完全覆盖，基于权重的贪婪算法的目标是从分区中最大化集合个数从而延长整体的网络寿命。但是算法的分区选择有些难度，并且由于算法是集中式的，扩展性不够好，并且时间复杂度有些高。

（2） Manju[2]提出了一种新的节能启发式方法，可以在不同时间段对传感器进行调度，不同非相交传感器节点集合有助于最大化网络生存周期。首先，作者的启发式算法可以识别出所有关键目标也就是最少被覆盖的目标，以及关键节点，也就是覆盖关键目标的节点。关键目标由最少的傳感器节点覆盖，将会是最先未被覆盖的，有效的利用关键节点将会延长网络寿命，作者尝试寻找使用最少的传感器数量来覆盖迷宫集合以至于关键目标可以被覆盖更长时间。由于算法使用的非相交的集合，因此和那些使用可以存在重叠的传感器集合相比，会有更少的集合数量。

（3） Babacar[3]提出了一种贪心集合的算法来解决目标覆盖问题，该贪心算法将节点集合分为相交和不相交两种。将传感器划分为最大数量的集合覆盖，并通过连续激活这些集合来安排传感器活动，在网络生命周期的某个时刻，只有一个子集被激活，属于该子集的所有传感器负责检测目标，所有其他传感器处于休眠状态，直到它们所属的集合被激活。该算法可以有效延长整体生存周期，但是贪心算法并不一定是最优解，并且此论文并未有给出令人信服的证明。

1.2 区域覆盖

区域覆盖，通常又称为面积覆盖，是在满足无线传感器网络连通性下的前提下，考虑如何用更少的传感器数量来监测更大的覆盖面积，图2所示。理想情况下，应该使得监测区域内的每个点都可以被至少一个传感器感知。

1） PEAS算法

PEAS[4]算法是一种简单的协议，通过大量经济，短寿命的传感器来构建一个长寿命的传感器网络。PEAS通过保持一组必要的传感器工作并将其余传感器置于睡眠模式来延长整体覆盖寿命，不时唤醒休眠节点，探测周边环境并且替换失败的传感器节点。因为PEAS协议是每个节点都有自主检测能力，其实可以认为它是基于分布式的一种协议，因为扩展性算是该算法的一个优点，并且每个节点检测方式比较简单，容易扩展，时间复杂度也很低，然而该算法也有其弊端，那就是有些节点可能会过度使用，导致提前将能量耗尽，因而影响整体覆盖效果。

2） SPAN算法

SPAN[5]算法是一种用于多跳ad hoc无线网络的节能技术，可在不显著降低网络容量或连接性的情况下降低能耗。SPAN是一种基于分布式的算法，其中节点在是否休眠做出本地决策，或者作为协调器加入骨干网络。每个节点的决策基于如果它苏醒的话，有多少邻居节点可以从之获取好处。SPAN算法的核心创新就是提出了骨干网络，并且通过对骨干网络的选择节省能量，并且延长整体网络寿命。SPAN算法的缺点是，因为骨干网络需要承担更多的转发数据的任务，显然需要消耗更多的能量，进而影响整体网络覆盖质量。

3） Node Self-scheduling算法

Node Self-scheduling[6]算法提出了一种节点调度方案，通过对冗余节点的感知覆盖进行识别，然后分配一种比正常活跃节点能耗更低的休眠模式，从而降低系统的整体能耗，从而提高系统的寿命，该算法从理论上完全保留原始传感器覆盖范围，并且可以在保证覆盖的同时维持一个比较低的冗余度，然后在节点判断是否休眠的过程中，容易出现多个节点同时休眠，导致出现覆盖黑洞的出现。

1.3 栅栏覆盖

栅栏覆盖主要是用来监测一个或多个运动目标穿越无线传感器网络的一种覆盖方式，传感器节点能够有效监测处于覆盖范围内的移动目标的运动轨迹[3]，如图3所示，和区域覆盖的不同在于它监测的主要目标是可移动的，不可确定的。

（1）谢欢[7]针对栅栏覆盖提出了一种最小化覆盖集合探测算法，该算法在概率感知模型的协同检测下研究目标检测问题，基于图论，提出一种最小化覆盖的，寻求用最小的激活节点实现一个强大的屏障，用来延长整体网络寿命。并且算法有较低的时间开销以及准确性可以得到较好的保证。但是算法的冗余度有些高，会导致使用过多的节点。

（2）冯全友[8]等人提出一种针对栅栏覆盖的分布式调度策略，首先将监测区域划分为垂直区域块，称之为切片，基于这种划分，作者将如何调度传感器满足栅栏覆盖并且实现最大化网络寿命周期问题称为屏障覆盖调度问题，并且作者们提出了对应的分布式算法，这个分布式算法有两个优点，低通信开销和低计算开销。并且十分适应于大规模网络。但是算法不太适应于覆盖面积比较不规则的场合，切片时比较难以划分。

2 结论

上文对无线传感器网络的三种覆盖方式作了一些简单概述，分析了其不同的特点以及应用场景，并且不同的覆盖方式也举了一些覆盖算法的例子。正是由于无线传感器网络覆盖方式的多样，才会有其广泛的应用以及研究价值，无线传感器网络覆盖技术已经越来越成为一种不可或缺的技术。

参考文献：

[1] Diop B ， Diongue D ， Thiare O . A weight-based greedy algorithm for target coverage problem in wireless sensor networks[C]// International Conference on Computer. IEEE， 2014.

[2] Kumar B ， Manju， ， Chand S . Maximising network lifetime for target coverage problem in wireless sensor networks[J]. IET Wireless Sensor Systems， 2016.

[3] Diop B ， Diongue D ， Thiare O . Managing Target Coverage Lifetime in Wireless Sensor Networks with Greedy Set Cover[C]// International Conference on Multimedia. IEEE， 2014.

[4] Ye F，Zhong G，Lu S，Zhang L.PEAS：A robust energy conserving protocol for long-lived sensor networks. Proceedings Internation Conference on Network Protocols（ICNP），Pairs，France，2002：200-201.

[5] Chen B，Jamieson K， Balakrishnan H，et al. SPAN：An energy efficient coordination algorithm for topology maintenance in ad-hoc wireless sensor networks[J].ACM Wireless Networks，2002，8（5）：481-494.

[6] Tian D ， Georganas N D . A node scheduling scheme for energy conservation in large wireless sensor networks[J]. Wireless Communications & Mobile Computing， 2010， 3（2）：271-290.

[7] Huan X ， Lin K ， Chaowei W ， et al. Minimal coverage set detecting algorithm for barrier coverage in wireless sensor networks[C]// IEEE International Conference on Network Infrastructure & Digital Content. IEEE， 2015.

[8] Ban D ， Feng Q ， Han G ， et al. Distributed Scheduling Algorithm for Barrier Coverage in Wireless Sensor Networks[C]// Third International Conference on Communications & Mobile Computing. IEEE Computer Society， 2011.

【通聯编辑：梁书】