无线传感器网络覆盖算法研究

李小龙　段　雪　徐增敏

摘要：立足于无线传感器网络中的覆盖问题，分类总结近年来提出的覆盖算法，详细讨论了一些典型的无线传感器网络覆盖算法。

关键词：无线传感器网络覆盖

中图法分类：TP393

文献标识码：A

0引言

节点调度和密度控制是节约网络能量、延长网络生存时间的一种有效办法。本文立足于无线传感器网络中的覆盖问题，分类总结了近年来提出的覆盖算法，并详细讨论了一些典型的无线传感器网络覆盖算法。

1覆盖算法的分类

1.1确保完全覆盖的覆盖算法和不能确保完全覆盖的覆盖算法。假设部署在目标区域的传感节点组成的传感器网络能够完全覆盖目标区域。根据执行了算法之后处于活动状态的节点能否完全覆盖目标区域，把节点调度覆盖算法分为：确保完全覆盖的覆盖算法和不能确保完全覆盖的覆盖算法。前者适用于灾难救助、军事监测等对安全程度要求较高的应用领域，后者适用于环境感知、森林火灾监测等对安全程度要求较低的应用领域。前者又可分为1－覆盖和K－覆盖(K≥2)，属于K－覆盖的覆盖算法确保所有的监测目标或监测点同时都被K个不同的传感器节点所覆盖。

1.2集中式的覆盖算法和分布式的覆盖算法。根据算法实施策略来分，把覆盖算法分为：集中式的覆盖算法和分布式的覆盖算法。前者需要将整个网络的全局信息发送给一个处理节点，由处理节点单独执行完算法之后，将控制信息发送给网络中的每一个节点，因此仅适用于小型的传感器网络，不具备良好的扩展性。而后者通过利用局部信息，由邻近区域内节点之间的协作共同完成，可适用于大型的传感器网络。

1.3确保网络连通性的覆盖算法和不考虑网络连通性的覆盖算法。根据网络连通性来分，把覆盖算法分为：确保网络连通性的覆盖算法和不考虑网络连通性的覆盖算。文献已经证明，如果网络中的所有节点同构，且节点的感知模型为圆形区域感知模型，当通信半径大于或者等于2倍的传感半径时，完全覆盖目标区域的节点集构成的传感器网络一定是连通网络。然而，当通信半径小于2倍的传感半径时，不能保证网络的连通性。在不考虑通信半径与传感半径之间的关系时，确保网络连通性的覆盖算法能够保证在任意时刻，处于活动状态下的节点构成的网络是连通网络，因此收集到的传感数据能够发送到汇聚节点。

1.4依赖于节点位置信息的覆盖算法和不依赖于节点位置信息的覆盖算法。根据是否利用位置信息，把覆盖算法分为：依赖于节点位置信息的节点调度覆盖算法和不依赖于节点位置信息的覆盖算法。现有的定位技术由于硬件成本、能耗以及误差范围的限制，难以保证每个节点获得自身精确的物理位置，因此，倚赖于节点位置信息的覆盖算法可能会因为节点不能获取到准确的位置信息，导致难以达到预定的覆盖效果。

1.5基于轮次的覆盖算法和基于分组的覆盖算法。根据算法在网络生存时间内的执行次数来分，把覆盖算法分为：基于轮次的覆盖算法和基于分组的覆盖算法。基于轮次的覆盖算法要求传感器节点在每一轮的开始执行一次算法，按照某种竞争机制从所有节点中选择若干个节点作为活动节点，这种算法在传感器网络的生存时间内执行了多次。而基于分组的覆盖算法在传感器节点部署后仅执行一次，通过分组将所有传感器节点划分到若干个组内，在算法完成之后，依次调度每一组的传感器节点作为活动节点。

2典型的覆盖算法分析

2.1位置无关的覆盖算法算法属于不依赖于节点位置信息的分布式覆盖算法。该算法仅适用于圆形区域感知模型，且节点的传感半径与通信半径相等的情况。各个节点根据如下信息判断自身的传感任务是否可由邻居节点完成：1－Hop内的邻居节点，以及这些邻居节点的1－Hop邻居节点。当节点判断自身为冗佘节点，就可以关闭自身节点的传感单元进入休眠状态。

优点：①不依赖于节点的位置信息；②关闭冗余节点之后，不降低原有的覆盖率。

缺点：①只适用于圆形区域感知模型，不适用于不规则的节点感知模型：②只适用于节点的传感半径与通信半径相等的情况；③绝大部分的冗余节点都不能满足上述判断条件，因此不能进入休眠状态；④没有考虑网络的连通性。

2.2连通的随机调度覆盖算法算法属于一种不依赖于节点位置信息的基于分组的分布式覆盖算法。算法分4步完成。第1步，将所有的传感器节点分为K组，每个传感器节点随机取1到K中的某个值i，并将自身分配到第i组。第2步，每个节点获取到汇聚节点的最小跳数。汇聚节点首先向邻居节点广播包含了到汇聚节点最小跳数的消息，最小跳数的初始值为0。所有节点将记录到汇聚节点的最小跳数，同时忽略具有较大跳数的消息。然后将跳数值加1，并转发给邻居节点。通过这种方法，传感器网络中的所有节点能够记录下到汇聚节点的最小跳数。第3步，各个节点向邻居节点广播消息，其中包括自身的ID，到汇聚节点的最小跳数以及组号等信息。第四步，通过分配一些必要节点到某些组内，使每个节点能够在所属的分组内建立一条到汇聚节点的最短路径来构造连通网络。分组i内的各个节点(不妨假设为A，它的最小跳数为n)首先判断在自身邻近区域内的下游节点(下游节点是最小跳数为n-1的节点)是否有节点属于分组i，如果没有，则节点A从这些节点中任选一个，并将它同时划分到分组i，以确保节点A从第n跳到第n-1跳是连通的，依此类推，从而建立一条A到汇聚节点的最短路径。在执行完第4步之后，显然分组i构成的子网络是连通的。在算法完成之后，依次调度每一组的传感器节点作为活动节点。

优点：①不依赖于节点的位置信息；②适用于不规则感知模型：③确保了在任意时刻网络的连通性；(4)算法在节点的生命周期内仅执行了一次，节约了能量。

缺点：①各个分组内的节点分布不均匀，覆盖效果较差；②维持分组连通时额外加入到分组内的节点较多。

3总结

本文立足于无线传感器网络中的覆盖问题，分类总结了近年来提出的覆盖算法，并详细讨论了一些典型的无线传感器网络覆盖算法。