无线传感器网络覆盖控制算法分析

张永棠　罗先录　周富肯

摘 要：网络覆盖算法直接影响无线传感器网络“感知”服务质量。文章根据传感器网络覆盖控制理论，对WSN的覆盖问题进行了归纳与总结，建立了WSN研究框架，从生存时间、部署策略、通信协议和组网等问题对无线传感器网络的覆盖控制策略和算法进行详细分析。

关键词：无线传感器网络；算法；网络通信；覆盖控制；信息安全

中图分类号：TP393 文献标识码：A

Abstract：Network coverage algorithm for wireless sensor network directly affects the perception quality of service.The according to the sensor network coverage control theory，on the WSN coverage problem were summed up and summarized，establishes the framework for WSN research，from the survival time，deployment strategy，communication protocol and network of wireless sensor network coverage control strategies and algorithms were analyzed in detail.

Keywords：wireless sensor networks；algorithm；network communication；covering control；information security

1 引言（Introduction）

由于无线传感器网络（WSN）节点具备体积小、成本低廉、可无线通信以及有自组织能力等特点，使得其在环境恶劣以及无人值守场合具有很高应用价值。作为一种新兴网络，WSN目前仍存在许多亟待解决的问题，例如节能、部署覆盖、路由规划、定位、自组织和协同性等[1]。其中覆盖方法对传感器网络的生存时间、部署策略、通信协议和组网等问题的解决具有十分重要的影响。

由于传感器和应用场景千变万化，实际应用中传感器网络的覆盖问题需要考虑很多方面。通过网络传感器节点配置以及路由选择等手段来优化WSN资源分配，改善网络的感知、监视、传感和通信等各种服务[2]。目前，WSN的覆盖控制策略已经有多种，下面对无线传感器网络的覆盖控制策略和算法进行详细分析。

2 WSN覆盖控制算法（WSN overlay control

algorithm）

基于传感器网络覆盖控制理论和覆盖控制问题描述，建立了WSN研究框架，如图1所示。依照该框架，可以发现现有覆盖控制策略所研究的问题存在很大差异，例如监测目标（区域）、节点能力（是否可移动）、节点感知模型和信息协同处理、实现方案的约束和先决条件（精确定位、时间同步），导致解决的方案和手段也千差万别。

2.1 最大流覆盖

考虑监控区域中有一组位置已知的目标点（targets），足够数量的传感器节点（sensors）随机地部署在区域内，节点将自身所能监控的目标点信息通过无线方式传输至集中处理节点（central processing node），由集中处理节点根据所收集的信息利用最大流的研究方法，对网络中的节点进行分组，使组群之间相互独立，并能完全监控区域中的目标点。在任何时刻都只有一个组群处于工作状态，各组群循环工作并保证在任何时刻都能监控到目标点，从而达到资源的合理利用。通过合适算法确定分组的最大个数，可以更加有效地优化网络资源，延长WSN的工作时间。

在将问题转换成寻求最大流问题后，提出一个启发式的算法MC-MIP来计算顶点Y2处所能获得的最大流及节点分组。如图2中分组为C1={S1，S3}，C2={S2}。

2.2 最坏/最佳覆盖

考虑一片随机部署有传感器节点的区域，从该区域的一点到另一点，如何选择路径使其被WSN网络节点监控到的几率最小/大，则为最坏/最佳覆盖问题。

定义：设一条连接起点和终点的路径P，则裂缝（Breach）定义为P到任意节点的欧氏距离的最小值；支持（Support）定义为P到其最近节点的欧氏距离的最大值。

最坏/最佳覆盖问题转变为在区域中寻找“最大裂缝路径（Maximal Breach Path）”和“最大支持路径（Maximal Support Path）”[3]，如图3所示。采用计算几何中的Voronoi图[4]和Delaunay三角形来完成对最大裂缝路径和最大支持路径的构建和查找。可见，最坏/最佳覆盖问题解决了实际应用中路径跟踪问题。

2.3 集成覆盖与连接

为了验证WSN覆盖与连接性的关系，设RC为通信距离，RS为传感距离，证明：（1）对于1-覆盖的区域，当RC≥2RS时，区域内的节点完全连接；（2）对于KS-覆盖的区域，当RC≥2RS时，区域内的节点为KS-连接。

考虑两个相邻节点存在虚拟的“引力”或“斥力”，在虚拟力的作用下，两个节点可以相互靠近或者远离。若在监控区域中存在两个相邻的节点Si与Sj，其间距为dij，当dij>dth时，其中dth为相邻节点的最佳间距，则Si与Sj表现为引力；当dij

图4表明利用VFA算法可以有效地改善由于节点随机分布所带来的覆盖不均，满足各种应用场合的覆盖需求。

2.4 信息覆盖

将环境参数（光强、声强和温度等）的变化考虑成场，利用场理论以及概率论研究在随机部署、不可移动的大规模WSN中综合周边节点的采集数据的基础上得出监控盲点的环境信息，是一类信息覆盖问题。如图5所示，中间“☆”处没有任何节点可以监控到，然而可以通过综合周边部署的节点监控数据，根据场的分布和概率论得出“☆”处的环境信息θ。

如图5所示，“●”为传感器节点，设图中传感器对环境的检测值分别为Sk，k为节点编号，节点k与☆处的距离分别为dk，假设环境信息θ随距离衰减，衰减系数为α（α>0），则在距离d处环境信息为θ/d。由于在实际监测中存在噪声nk，则有

通过周边节点的监测信息Sk，根据上式以及概率估计算法可以得出“☆”处的环境信息。记不大于预先设定值A的概率为Pr（A），若Pr（A）≥ε（0≤ε≤1），则称“☆”处可以被其周边的K个节点信息覆盖（记为（K，ε）-覆盖）。

当K=1时，即为简单的圆盘覆盖；当K>1时，信息覆盖不仅仅是K个圆盘覆盖的组合。可见，信息覆盖扩大了原先的覆盖范围，更好的对监测区域实行监控。

3 结论（Conclusion）

WSN如何对区域进行监控是在WSN进入工作阶段之前必须考虑的问题，网络覆盖控制作为WSN实施过程中的一个基本问题，反映了网络所能提供的“感知”服务质量[5]。本文根据近年来的覆盖控制研究成果，对WSN的覆盖问题进行了归纳与总结，提出了研究WSN覆盖问题时所需关注的各个方面，并详细介绍了无线传感器网络算法。WSN的覆盖控制依然存在许多亟待解决的问题。例如，现有的WSN覆盖控制策略主要集中在解决简单传感模型下的覆盖控制，对于节点感知存在方向差异的情况的研究，仍然是一个比较复杂的难题。

参考文献（References）

[1] 任彦，张思东，张宏科.无线传感器网络中覆盖控制理论与算法[J].软件学报，2006（3）：422-433.

[2] 曹峰，刘丽萍，王智.能量有效的无线移动传感器网络部署[J].信息与控制， 2006（2）：147-153.

[3] 王燕莉，安世全.无线传感器网络的覆盖问题研究[J].传感技术学报，2005，18（2）：307-312.

[4] 任彦，张思东，张宏科.无线传感器网络三维空间最佳覆盖路由协议[J].电子学报， 2006（2）：306-311.

作者简介：

张永棠（1981-），男，硕士，副教授，系统分析师.研究领域：光通信与传感器网络应用.

罗先录（1973-），男，硕士，副教授，系统分析师.研究领域：软件与网络安全.

周富肯（1982-），男，硕士，讲师.研究领域：网络安全.