对无线传感器网络感知能力动态调整算法研究

摘　要：为了增强无线传感器网络的监测质量和提高网络可靠性，通常将传感器节点大规模、高密度地部署在感兴趣的目标区域内，这就导致网络中大量节点的覆盖区域相互交迭。这种覆盖冗余会直接导致采集、传输数据的冗余以及信道的干扰，从而导致不必要的能量消耗，提出了一种传感半径的动态调整算法，在保证网络覆盖性的前提下，通过对节点传感半径的调整，来降低网络的覆盖冗余，从而大大减少冗余数据采集和传输所造成的能量浪费和网络冲突。仿真结果证明算法取得了良好的效果。

关键词：传感半径；覆盖冗余；动态调整
1 引言
1.1 网络模型
　　假设个传感器节点和一个Sink节点随机分布在一个的二维正方形区域内，并假设该传感器网络具有如下性质：
* 节点同构，各节点具有相同的计算、通信能力和初始能量水平，且节点能量不能再补充。其中Sink节点例外，它的计算、通信能力和能量不受限制；
* 节点间的通信是相互的。节点A能够与B通信，则B也可以与A通信；
* 节点具有相同的最大感知范围，且感知范围能够自调整；
* 节点能获知其位置信息。感知节点可以利用定位算法或 GPS方式获知自己所在的位置；
1.2 感知模型
　　采用无线传感器网络研究中常用的二元感知模型(Binary sensing model)即在二维平面上，传感器节点的覆盖范围是一个以节点为圆心，半径为的圆形区域称为传感器节点的“感知圆盘(Sensing Disk)”。称为传感器节点的传感半径，假设节点的坐标为。在二元感知模型中，对于平面上任意一点，节点检测到点处发生的事件的概率为
     
2 传感器感知能力动态调整算法
2.1 算法相关定理
　　节点集，若区域内的任一点都不能被内的节点所感知到，则这样的区域称为的覆盖盲区。可以注意到，覆盖盲区有两种类型闭合型与开放型，若组成开放型盲区区域的圆弧之间有交点，则交点也称为盲区顶点。
　　若一个节点的感知圆的某段圆弧被其任何一个邻居节点的感知圆包含，则称这段圆弧为约束圆弧，否则称为自由圆弧。
　　【定理1】有一圆心为半径为的圆和顶点为的凹曲边形，设为到的最大距离，即，若满足，则圆必覆盖该凹曲边形区域。
　　证明：欲证圆覆盖凹曲边形，只需证明圆覆盖顺次连接的相邻顶点所形成的n多边形。设点为n多边形内的任意一点，连接并延长则必交的一边于点,记该条边为，如下图所示。在内易知，又因所以，因此，从而凹曲边形内任意一点到圆心的距离均不大于圆半径，即该圆覆盖凹曲边形，定理得证。
【定理2】若有盲区区域均是传感器节点的邻居集的闭合型覆盖盲区，其顶点分别为，，，， 且是的感知圆内的所有闭合型盲区，节点的传感半径等于其最大传感半径，为节点到，，，的最大距离。如果的感知圆不存在自由圆弧，则的传感半径在由调整为的过程中不会产生集合的覆盖盲区。
　　证明：因的感知圆不存在自由圆弧，易知在的感知圆内必不存在的邻居集的开放型覆盖盲区区域部分，则的感知圆内仅存在闭合型盲区区域，由定义4可知均为凹曲边形。又由定理1可知，当
　　时，的感知圆覆盖，
　　时，的感知圆覆盖，
　　时，的感知圆覆盖。
　　又因
　　
　　　
　　故当时必覆盖，即在的传感半径在由改变为的过程中不会产生的覆盖盲区。定理得证。
2.2 传感器感知能力动态调整算法描述
　　(一)算法思想概述
　　节点首先根据邻居信息判断其感知圆是否具有自由圆弧，若具有自由圆弧，则传感半径保持不变，仍为最大传感半径，以尽可能多的覆盖其邻居集的覆盖盲区区域。若不存在自由圆弧，则计算节点所有邻居节点感知圆在该节点感知圆内彼此两两相交所构成的交点的集合，将集合中交点的被覆盖次数判断盲区顶点和普通交点，若不存在盲区顶点，则邻居节点能够完全覆盖感知区域，此时，传感半径可以调整为零，否则说明感知圆内包含有邻居集的闭合型盲区,可根据定理2对传感半径进行调整。
　　(二)算法步骤
　　具体算法步骤如下：
　　1) 首先查询邻居节点集NBS的信息，获得所有邻居节点的圆心坐标、当前传感半径等。
　　2) 检查邻居节点的个数 是否小于1，若是则转步骤7，否则转3。
　　3) 依照判断是否存在自由圆弧的算法判断该节点的感知圆是否存在自由圆弧，若存在则转到步骤7，否则转到4。
　　4) 计算所有邻居节点的感知圆在本圆内的交点，若不存在交点，即转到步骤6；否则，转到5。
　　5) 从第4步中获取的交点集合中按查找本圆内盲区顶点集合HolePointsList，若不存在，则转步骤6；若存在，则找出离该节点最远的点到该点的距离d，传感半径调整为，转步骤7；其中为误差控制参数，以免去因误差导致的覆盖盲区。
　　6) 将节点传感半径调整为零。因此时节点的感知范围区域已被邻居所覆盖。
　　7) 算法结束。
2.3 邻居集的选取
　　在传感器感知能力动态调整算法中定义传感器节点A的邻居节点集为，其中为B到A的距离，为A的最大传感半径，为邻居范围控制因子。在进行传感半径调整时，要保证算法中节点的邻居的感知圆和本节点的感知圆是非相离关系，因为相离关系的两个节点不会相互影响到对方的覆盖范围，则只需保证其邻居到该节点的距离不大于该节点2倍最大传感半径，即的取值应满足下式：
       
　　当时，这时节点在传感器感知能力动态调整算法中考虑到了所有能对自己的最大覆盖范围能造成影响的节点，传感器感知能力动态调整算法可以充分利用邻居的信息，调整能得到最佳的效果。
　　当时，此时，部分节点的感知区域可以覆盖该节点感知区域的一部分，因为这部分节点不包含在该节点的邻居集内，会出现节点感知区域内实际上不存在盲区，但是节点会误认为其感知圆内存在盲区，传感半径调整后出现部分监测区域的重复覆盖现象，这时的调整效果不及。
　　实验结果显示，当时的调整效果最好，时的效果最差，产生大量不必要的冗余覆盖。
3 仿真与分析
　　 为了检验传感器感知能力动态调整算法的有效性，论文主要从调整效果、能量消耗和覆盖冗余度三个方面对算法进行了模拟实验和分析。首先对本文所用仿真程序做简单的介绍。
3.1 覆盖冗余度
　　覆盖冗余度是用来衡量监测区域中被传感器节点覆盖区域的覆盖次数。定义为区域中所有节点覆盖范围之和与区域中所有节点的覆盖范围的并集之比值。覆盖冗余度的计算公式为
   
　　其中，表示节点的覆盖范围， 覆盖冗余度反映了节点对监测区域覆盖的冗余程度，覆盖冗余度越低，节点利用率越高，反之节点利用率越低。
　　随机布置节点数N分别取{800，1000，1200，1300，1400}五个值时，节点最大传感半径从10变化到30时，调整前和调整后覆盖冗余度的对比情况。
　　
　　实验结果表明传感器感知能力动态调整算法前，网络的覆盖冗余度会随着最大传感半径的增大而急剧增大，加入传感器感知能力动态调整算法之后，网络的覆盖冗余度随着节点最大传感半径的增大而增大甚少，传感器感知能力动态调整算法应用在具有不同最大传感半径的传感器网络中，对覆盖冗余度的控制也能保持较好的成效。
3.2 能量消耗
　　本节只分析传感器节点的传感模块的能量消耗，暂时不考虑通信和计算的能耗。假设传感器节点的传感半径调整为零时认为该节点消耗能量也为零。传感器节点的感知模块的耗能与传感半径成正比，，为常量，可看作能量消耗系数。
　　所有节点的有效覆盖面积即所有节点的覆盖范围的并集为
         
　　则调整传感半径前，覆盖区域的平均能量消耗为
 
　　而调整传感半径后，覆盖区域的平均能量消耗为
   
　　前文已经证明，节点在传感半径调整的过程中不会产生盲区，所以传感半径调整前后，所有节点的有效覆盖面积在理论上是保持不变的。
　　表1列出了在的区域内随机布置800个节点，各个节点的最大传感半径为15m时，节点传感半径调整前后网络覆盖区域的平均能量消耗。
　　传感半径调整前后区域平均能量消耗统计
实验次数
调整前平均耗能
调整后平均耗能
1
3.6463
0.6875
2
3.6092
0.7189
3
3.6487
0.7054
4
3.6389
0.7311
从表中实验数据可以看出，传感半径调整后，平均能量消耗比原来减少了大约80%，说明传感器感知能力动态调整算法能够大大减少传感器节点的能量消耗。
4.小结
　　  针对无线传感器网络节点高密度随机部署时，网络的覆盖冗余度过大，大量冗余信息的被感知及其在网络中的传输，会极大浪费网络能量的特点，本文提出了一种能够保证网络覆盖的分布式传感器感知能力动态调整算法。各节点只根据其邻居节点的信息来调整自身的传感半径。算法侧重于保证网络的原始覆盖和连通，在此前提下，尽量减少网络的冗余覆盖，所以传感半径调整后对网络的路由协议的设计不会产生任何影响。

参考文献：
. IEEE Aerospace and Electronic Systems Magazine, 1994, 10(4): 102-113.