【本文转自互联网，仅供大家参考，如需引用请联系原作者】
摘要：网络覆盖作为无线传感器网络中的一个基本问题，反映了网络提供的“感知”服务质量，可以使无线传感器网络的空间资源得到优化分配，进而更好地完成环境感知、信息获取和有效传输的任务。本文立足于无线传感器网络的覆盖问题，分类总结了近年来提出的各种覆盖问题的思想和有代表性的研究成果，着重讨论了一些典型的无线传感器网络覆盖算法。最后总结并分析了目前无线传感器网络覆盖亟待解决的问题，并展望了其未来的发展方向。
关键词：计算机系统结构；无线传感器网络；网络覆盖；能量有效性；覆盖算法
0 引言
近年来，无线传感器网络[18]的发展引起了国内外业界人士极大的关注，其应用环境通常是由廉价的传感器节点组成的，而每个节点均有采集、存储和处理信息的能力，并且能和其邻居节点通过无线链路保持通信。覆盖问题是无线传感器网络配置首先面临的基本问题，因为传感器节点可能任意布置在某个监测区域，它反映了无线传感器网络在该区域的监测以及跟踪状况。而今，随着无线传感器网络应用的普及以及研究角度的深入，覆盖问题被赋予了不同的理论模型[1]，有些甚至在计算机几何里[16]就能找到与其相关的解决方案。尽管这些办法并不能直接应用到无线传感器网络中，但是研究这些问题有助于让读者建立相关的理论背景。
近年来，已有一些国内外学者开展了无线传感器网络优化覆盖控制方面[4,5,11]的研究工作，并取得了一定的进展。本文综述了近年来在这一领域所取得的研究成果。第1 节分析了无线传感器网络覆盖控制问题面临的挑战，即性能评价标准。在第2 节中对现有覆盖控制算法进行了分类。第3 节详细介绍和讨论了一些典型的覆盖控制协议算法。第4 节进行了全文总结以及展望未来。
1 覆盖问题考虑的因素
无线传感器网络规模大，且节点的能量、通信以及计算能力有限，因此在研究无线传感器网络的覆盖问题时，需要考虑以下几方面的内容：
1）节点的部署方式
在无线传感器网络中，节点的部署方式一般分为两类，即随机部署和计划部署。在随机部署条件下，某个区域内的节点数量、感知半径要满足一定的关系才能组成性能优越的网络。
MAO YC[23]等人解决了在没有节点位置的情况下，如何保证能量有效并使网络达到连通性覆盖的问题，基于构建连通支配集CDS 的Rule K 算法，作者提出了一种与节点位置无关网络连通性覆盖协议LICCP，并且通过实验仿真，证明了LICCP 协议能够在较长时间内能量有效地提供高质量的网络覆盖以及保证网络的连通性。
2）节点感知范围和通信范围
在无线传感器网络中，网络覆盖由节点的感知范围决定，而网络的连通性则由节点的通信范围所决定。JIANG J[20]等人以设计同时满足“覆盖要求”（工作节点必须能完全覆盖目标区域）以及“连通性要求”（工作节点组成的网络必须连通）的最小节点集为目标，提出了一种基于目标区域Voronoi 划分的集中式近似算法（centralized Voronoi tessellation，简称CVT），用于计算完全覆盖目标区域所需要的近似最小节点集。实验仿真表明，CVT 和一种基于最小生成树（MST）算法的性能无论在时间复杂性还是连通覆盖集大小方面都优于已有的贪婪算法。
3）能量有效性
由于无线传感器网络节点硬件平台资源有限以及网络节点数目巨大，并且实际应用环境条件复杂且没有条件对“失效”节点进行电池更换，因此，如何节约各节点有限的电池能量并且尽可能延长整个网络的生存周期已经成为无线传感器网络一项重要的性能指标。LIFM[10]等人在功率控制方面提出了对网络能量有效性的改善，通过降低发送端节点的发射功率来减少邻居节点的数目，从而节省网络中与之通信不相关节点的接收能量消耗，达到减少网络整体能耗的目的。
4）算法特征
覆盖控制算法分为集中式和分布式，集中式算法指由拥有网络全局信息的管理者对网络中的所有节点进行统一管理和监控，这对管理者的计算、存储以及通信能力有很强的要求。
而分布式算法是指网络中的节点根据自身拥有的局部信息来进行局部计算和控制。对于分布式算法，SHEN B[29]等人分析了无线传感器网络分簇路由机制，着重从簇头的产生、簇的形成和簇的路由角度系统地描述了当前典型的分簇路由算法，并比较和分析了这些算法的特点和适用情况。最后结合当前研究现状，指出分簇路由算法未来的研究重点。
5）传感器节点的移动性
在一些传感器网络中，节点具有移动能力[3,14]，而节点的移动将会导致网络拓扑的变化，因此，势必会对网络的覆盖产生较大的影响。WANG Y[27]等人提出了一种可扩展与高效的、适用于移动自组织网络的路由算法，即分簇覆盖的节点位置信息辅助路由算法（CLAR），该算法在路由建立所需时长、路由代价、平均时延及数据包冲突等参数上表现优良。同时，算法保持低平均时延、高数据包到达率、低控制开销以及低路由寻找次数等优势。
6）网络动态性
在一些特殊的环境里，如运动目标监测覆盖、网络动态覆盖等，需要网络的覆盖协议与算法需要考虑节点具体的运动能力、网络整体或是传感目标运动等网络动态特征。AMUTHANANMARAN[2]等人提出了在一个随机的传感器网络区域覆盖进程的一维路径分析路径覆盖并且获取无线传感器网络的追踪数值。作者利用一种高效的算法找到最大攻破的支持路径，由于传感器网络由大量的随机部署的传感器节点形成，收集了合作节点的感知数据，最后将结果发送到最终用户。
2 无线传感器网络覆盖分类
2.1 配置方式分类按照无线传感器网络节点不同配置方式，即节点是否需要知道自身位置信息，我们可以将无线传感器网络中的覆盖问题分为确定性覆盖、随机覆盖两大类，下面逐一对这两类覆盖控制类型加以总结。
1）确定性覆盖
如果无线传感器网络状态相对固定或是其环境已知，就可以根据预先配置的节点位置确定网络拓扑情况或增加关键区域的传感器节点密度，这种情况被称为确定性覆盖问题。典型的确定性覆盖有确定性区域/点覆盖、基于网格（grid）的目标覆盖和确定性网络路径/目标覆盖3 种类型。
区域覆盖往往出现在气候监测、森林防火等应用场景中。可以这样定义区域覆盖：给定一个区域，要求在任意时刻传感器网络可监控到该区域的所有子区域。而K-区域覆盖[17]是指要求该区域的所有子区域被至少K 个传感器所监控。如图1 所示，实心点表示选中的传感器，周围虚线表示其覆盖范围。
2）随机覆盖
在许多实际自然环境中，由于网络情况不能预先确定且多数确定性覆盖模型[7]会给网络带来对称性与周期性特征，从而掩盖了某些网络拓扑的实际特性，再加上无线传感器网络自身的拓扑复杂多变，导致采用确定性覆盖在实际应用中具有很大的局限性，不能适用于战场等危险或其他环境恶劣的场所。因此，我们需要进一步对节点随机分布在传感区域而预先没有得到自身位置的情况进行讨论，这正是随机覆盖所要解决的问题。目前，无线传感器网络的随机覆盖已成为一个热点问题，并且将这类问题具体分为随机节点覆盖和动态网络覆盖[12]
两类。
2.2 相关应用属性分类
1）节能覆盖
由于无线传感器网络中传感器节点自身体积较小、电池能量资源有限，如何保证大规模网络环境下传感器节点能量的有效使用就成为需要关注的一项重要研究内容，它直接影响到整个网络生存时间能否充分延长。如文献[9]所述，在维持一个无线传感器的覆盖度在一个特定应用水平条件下，保持只有一部分节点在任何时间是活跃的来节省能量的问题。并且提出了两个分布式覆盖服务协议，即NCP（基于邻居的覆盖协议）和GCP（基于网格的覆盖协议），确定其中所需关闭的覆盖度多余的节点。
2）栅栏覆盖
栅栏覆盖往往出现在边境入侵监测应用场景中，给定一个狭长区域，假如所有可能横越该狭长区域的路径都被至少一个传感器覆盖，那么这个区域就是被栅栏覆盖的。同理，当要求有至少K 个传感器来覆盖横越路线时，称之为K-栅栏覆盖。文献[17]采取的措施极大攻破路径并且制定传感器网络设计问题作为几何的问题，提出了一种改善的多项式时间算法来计算上述一个给定的传感器网络举措。同时，作者在给定的传感器配置上提出了一种几何变换，这带来了最大攻破对局部最优——在这个意义上说造成攻破是我们可以得到的最好的保持开始配置完整性的拓扑结构。如图2 所示，实心点以及周边虚线圆分别表示激活传感器及其覆盖范围。3）连通性覆盖降低能耗以延长网络生存时间是无线传感器网络设计中的一个重要挑战，在传感器节点高密度部署的环境中，在保证网络性能的前提下，仅将最少量的节点投入活跃工作状态，而将其余节点投入低功耗的睡眠状态，是一种节约系统能量的有效方法。同时需要满足“覆盖要求”（工作节点必须能够完全覆盖目标区域）和“连通性要求”（工作节点组成的通信网络必须是连通的）的最小节点集合。文献[20]设计了一种基于目标区域Voronoi 划分的集中式近似算法（centralized Voronoi tessellation，简称CVT），用于计算完全覆盖目标区域所需要的近似最小节点集。实验仿真结果表明，CVT+MST 算法的性能不论在时间复杂性或者连通覆盖集大小方面都优于已有的贪婪算法。
3 典型的无线传感器网络覆盖算法
3.1 连通性覆盖
文献[23]解决在没有节点位置信息的情况下，如何能量有效地保证网络连通性覆盖的问题。分析了节点覆盖与区域覆盖之间的关系，并给出了节点覆盖等于区域覆盖的充分必要条件。根据分析结果，基于构建连通支配集CDS 的Rule K 算法，提出了一种与节点位置无关网络连通性覆盖协议LICCP。在LICCP 协议中，每个节点根据本地节点密度选择合适的通信范围，利用Rule K 算法选出的工作节点提供高质量的网络连通性覆盖。实验结果表明，LICCP 协议能够在较长时间内能量有效地提供高质量的网络覆盖，并保证网络的连通性。
3.2 边缘覆盖
文献[6]调查的标准决定一个节点是否冗余，作者提出了一种改进的方法来确定一个传感器节点的感知范围能否被它的邻居节点所覆盖，特别是对于边界上的传感器节点。而且提出了一种大规模的传感器网络环境中，基于密度控制的改进的边缘覆盖算法（EPCDC）。实验仿真结果表明该算法在关闭工作节点的数目方面优于PEAS 算法以及Jiang 算法，因此延长了网络的生存周期.
3.3 暴露穿越
暴露穿越[19]覆盖同时属于随机节点覆盖和栅栏覆盖的类型。如前所述，目标暴露（targetexposure）的覆盖模型同时考虑时间因素和节点对于目标的“感应强度”因素，更为符合实际环境中，运动目标由于穿越网络时间增加而“感应强度”累加值增大的情况。
4 结论及展望
覆盖问题是无线传感器网络中非常重要的问题之一，它不仅涉及到网络的服务质量，而且对网络中的其他问题的研究产生很大的影响。由于无线传感器网络资源有限、拓扑结构动态复杂，因此，在研究覆盖的问题时，需要考虑这些特点，针对不同的应用场景，对无线传感器网络的覆盖问题进行深入研究。本文对近年来提出的一些覆盖机制进行了总结，可以看出由于对应用场景的针对性较强，这些覆盖机制或多或少在能量有效性、计算复杂度、通信开销以及工程实现方面存在着一定的不足之处。而随着新的无线传感器网络模型的诞生，网络可能会出现具有更多不同的应用要求和规模，节点通信、计算和感知能力也会变得更加的多样化。
未来的无线传感器网络覆盖问题的研究工作将会集中在以下几个方面：1）能量有效性，在无线传感器网络中，尽管现有的覆盖机制已经对能量的有效性进行了相当对的研究，但它目前仍然是主要问题之一，它直接决定了网络的生存时间，并且还是估计覆盖机制的一个重要指标；2）引入移动节点，目前移动覆盖机制尤其是事件监测机制的研究工作仍处在起步阶段，如何通过设计更为完善的节点移动控制机制，从而进一步提高事件监测率，将成为覆盖问题的一个研究热点；3）网络管理，覆盖信息是网络中的重点管理对象之一，将覆盖机制与不同的网络管理模型相结合，将成为下一步覆盖机制研究的趋势。
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 理论计算机科学 』 → 无线传感器网络中的覆盖与算法研究
(订阅本版)
2010/11/2 9:58:00
新浪微博
无线传感器网络中的覆盖与算法研究
