一种基于圆心角覆盖度的无线传感器网络节点休眠资格判断方法

摘要

本发明公开了一种基于圆心角覆盖度的无线传感器网络节点休眠资格判断方法，该方法通过计算邻居节点对本节点感知区域的覆盖度，来判断本节点是否冗余。在圆心角覆盖策略中通过调整约束距离不断增加邻居节点数目来提高覆盖度，只利用局部节点的信息，大大降低了计算的复杂度。尤其当网络允许一定程度的覆盖空洞时，与传统的休眠资格判断方法相比，本方法可以关闭更多的冗余节点，获得更长的网络生存时间。同时，本方法还适用于由感知半径不同的节点构成的异构网络。因此，本方法实用性更高，应用范围更广。

说明书

技术领域

本发明涉及一种应用于无线传感器网络的节点休眠资格判断方法，更特别地说，是指一种能够根据节点间距离和网络覆盖要求采用圆心角覆盖度进行调节的节点休眠资格判断方法。 

背景技术

随着微机电系统和无线通信技术的发展，无线传感器网络(WSN)得到了越来越广泛的关注和研究。无线传感器网络是一个由大量廉价的传感器节点组成的无线自组织网络。每个传感器节点由计算单元、存储单元、传感单元和无线通信单元等构成。该无线传感器网络依据节点传感半径是否相同可以分为同构网络和异构网络。 

无线传感器网络是一种新型的Ad hoc网络，由于成本和体积等因素的限制，单个传感器节点的处理能力、通信能力以及电池能量等资源极为有限，需要与距离较远的基站进行频繁通信。但是，由于传感器节点个数多、分布区域广，而且部署区域环境复杂，有些区域甚至人员不能到达，因而要对节点再次补充能源会非常困难。 

为了延长整个网络的生存期，同时不影响网络的性能，通常使用的方法是部署大量的节点，再通过对节点进行调度，关闭冗余节点，减少能量消耗，达到提高服务质量并延长网络寿命的目的。要解决的问题主要有：①在节能上如何使尽可能少的节点处于工作状态；②在网络覆盖上如何确保每个待观测点都至少在一个传感器节点的感知范围内；③在连通性上如何使工作的节点集合和基站保持连通。这些问题的解决能够使整个传感器网络以最小的能量代价来监测给定目标，从而达到延长网络生存期的目的。 

发明内容

针对传统的复杂度高、能耗大的区域覆盖节点休眠资格判断方法，本发明提出了一种基于圆心角覆盖度的无线传感器网络节点休眠资格判断方法。该方法将邻居节点对区域的覆盖转换为对节点圆心角的覆盖，计算角度在[0，2π]内的各个圆心角被覆盖的度数，从而得出节点感知区域被覆盖的度数，由此进行节点休眠资格判断。在不允许空洞的情况下，将距离小于节点感知半径的邻居节点的区域覆盖转换成圆心角覆盖；当允许空洞时，可以扩大有影响的邻居节点范围，增加参与计算的邻居节点个数，从而关闭更多的冗余节点，获得更长的网络生存时间。 

本发明的一种基于圆心角覆盖度的无线传感器网络节点休眠资格判断方法，采用圆心角覆盖策略来获得任意节点在同构网络或者异构网络中的覆盖度，其中圆心角覆盖策略为： 

步骤3-1，在无线传感器网络中建立平面坐标系，即节点u的坐标记为u(x_u，y_u)，第一邻居节点v₁的坐标为v₁(x_v1，y_v1)，则节点u与节点v₁的距离表示为 $d_{u-v1}=\sqrt{{(x_u-x_{v1})}^2+{(y_u-y_{v1})}^2};$

步骤3-2，节点u与第一邻居节点v₁的感知区域相交区域对应交点A的圆心角∠v₁uA，对于同构网络，依据垂径定理及三角关系式，有 对于异构网络，依据余弦定理，有 

步骤3-3，以逆时针方向为正方向，两个节点之间连线的圆心角 且∠v₁ux的取值范围为[0，2π)； 

若x_v1＞x_u且y_v1＞y_u时，则调整∠v₁ux＝∠v₁ux+π； 

若x_v1＜x_u且y_v1＞y_u时，则调整∠v₁ux＝∠v₁ux+π； 

若x_v1＞x_u且y_v1＜y_u时，则调整∠v₁ux＝∠v₁ux+2π； 

步骤3-4，交点A与节点u形成的圆心角记为∠Aux，且∠Aux＝∠v₁ux-∠v₁uA，标志位Flag＝0； 

交点B与节点u形成的圆心角为∠Bux，且∠Bux＝∠v₁ux+∠v₁uB，标志位Flag＝1； 

若∠v₁ux＜∠v₁uA时，则调整∠Aux＝∠Aux+2π； 

若∠v₁ux+∠v₁uA＞2π时，则调整∠Bux＝∠Bux-2π； 

步骤3-5，依据步骤3-1至步骤3-4对节点u的其他邻居节点进行圆心角计算，则有：第四邻居节点v₄与节点u的感知区域相交点C和D形成的圆心角分别记为∠Cux、∠Dux；第六邻居节点v₆与节点u的感知区域相交点E和F形成的圆心角分别记为∠Eux、∠Fux； 

步骤3-6，将步骤3-4和步骤3-5中获得的圆心角组成一个角度集合OAS{∠Aux，∠Bux，∠Cux，∠Dux，∠Eux，∠Fux}，然后对该角度集合依据从小到大的顺序排列，从而得到有序数组Angles； 

在初始时，每一个圆心角所对应的覆盖度均为0；则有，在有序数组Angles中的各圆心角所对应的覆盖度组成的数组记为ACD； 

步骤3-7，遍历有序数组Angles中的各圆心角元素，当遍历到第i个角度时，若此角度的标志位Flag＝0，则不对该圆心角进行处理； 

若Flag＝1，则从第i个角度向前查找同一个邻居节点上的另一个交点对应的圆心角，若未询到该圆心角，则从有序数组Angles中的最后一个圆心角元素向前查找，直到获得同一个邻居节点上的另一个交点对应的圆心角；从第i个角度开始遍历时，途经每个圆心角就使得覆盖度要加“1”； 

若Flag＝1，则从第i个角度向前查找同一个邻居节点上的另一个交点对应的圆心角，若获得同一个邻居节点上的另一个交点对应的圆心角，从第i个角度开始遍历时，途经每个圆心角就使得覆盖度要加“1”； 

步骤3-8，以覆盖度数组ACD中的最小值作为节点u的感知区域被覆盖的度数CDu。 

在本发明的在同构网络中基于圆心角覆盖度的休眠资格判断策略为： 

步骤1-1，对于任意节点u，获取其所有的邻居节点，放入邻居集Nu中； 

步骤1-2，遍历任意节点u的邻居集Nu中的所有邻居节点，提取出与任意节点u的距离在约束距离D_初(0，d₀)范围内的所有邻居节点，放入约束邻居集CNu中； 

其中，约束距离D_初(0，d₀)中的右边界值d₀等于感知半径r，即D_初(0，r)； 

步骤1-3，依据圆心角覆盖策略，计算出约束邻居集CNu中的邻居节点对任意节点u感知区域的覆盖度CDu(简称为邻-节覆盖度CDu)； 

步骤1-4，判断该邻-节覆盖度CDu是否满足同构网络覆盖度K_同对任意节点u感知区域的覆盖度要求；若满足，则判定任意节点u为冗余节点，使任意节点u进入休眠状态；若不满足转入步骤1-5； 

步骤1-5，当同构网络不允许覆盖空洞存在时，任意节点u保持工作状态；当同构网络允许覆盖空洞存在时，转入步骤1-6； 

步骤1-6，调整约束距离D_调(0，d₁)，且d₁＝d₀+Δd；若 则表明约束邻居集CNu中的邻居节点范围已超过同构网络允许空洞的最大范围，任意节点u保持工作状态； 

若 则转入步骤1-7； 

d₁为调整后的右边界值； 

Δd为区域扩张的步长，通常可取$\mathrm{\Delta d}=\frac{r}{10};$

toler表示同构网络允许的空洞占感知区域的百分比，在本发明中可设置为15％～30％； 

步骤1-7，依据调整后的约束距离D_调(0，d₁)，重新获取任意节点u的约束邻居集CNu，则任意节点u的约束邻居集更新为CNu＝{v₁，v₄，v₆}，转入步骤1-3，直到已判定出任意节点u进入休眠状态或者保持工作状态。 

在本发明的异构网络中基于圆心角覆盖度的休眠资格判断策略为： 

步骤2-1，初始化任意节点u的覆盖度调整变量CDPlus＝0； 

对于任意节点u获取其所有的邻居节点，放入邻居集Nu中，并从邻居集Nu中选取第一个邻居v； 

步骤2-2，计算任意节点u与其第一个邻居v之间的距离d_u-v；用ru表示任意节点u在异构网络中的感知半径，rv表示第一个邻居v的感知半径； 

步骤2-3，若ru＜rv且d_u-v＜rv-ru时，表明任意节点u的感知区域包含在第一个邻居v的感知区域中，则将任意节点u的覆盖度调整变量CDPlus增加1，即CDPlus＝CDPlus+1； 

步骤2-4，若ru≥rv或d_u-v≥rv-ru且满足 时，表明第一个邻居v对任意节点u的感知区域有部分覆盖，则将第一个邻居v记录到约束邻居集CNu中； 

步骤2-5，从邻居集Nu中选取下一个邻居节点，重复步骤2-2到步骤2-4，直到邻居集Nu中的所有节点处理完毕； 

步骤2-6，依据圆心角覆盖策略，计算约束邻居集CNu对任意节点u的邻-节覆盖度CDu； 

步骤2-7，依据覆盖度调整变量CDPlus对邻-节覆盖度CDu做出调整，即CDu_调＝CDu+CDPlus； 

步骤2-8，判断调整后的邻-节覆盖度CDu_调是否满足异构网络对覆盖度的要求；若满足，则判定任意节点u为冗余节点，使任意节点u进入休眠状态；若不满足，则使任意节点u保持工作状态。 

本发明基于圆心角覆盖度的无线传感器网络节点休眠资格判断方法存在有如下优点： 

①本方法只需要利用周围邻居节点的信息，与CCP和Huang的方法相比，大大降低了计算复杂度。 

②本方法不仅可用于传感半径相同的传感器节点构成的同构网络，还可用于传感半径不相同的传感器节点构成的异构网络。 

③当网络不允许覆盖空洞时，本方法与CCP和Huang方法一样，是判断节点冗余的充分条件。当允许空洞时，本方法可以识别出更多的冗余节点，减少能耗，为传感器网络赢得更长的网络生存时间。 

④本方法适用于对不同区域有不同的覆盖度要求的应用。 

附图说明

图1是本发明中同构网络任意节点与其邻居节点之间的感知区域构形图。 

图1A是本发明中调整约束距离后的同构网络任意节点与其邻居节点之间的感知区域构形图。 

图2是本发明中异构网络任意节点与其邻居节点之间的感知区域构形图。 

图3是本发明中任意节点与其约束邻居集中的邻居节点之间的感知区域构形图。 

图4是本发明中圆心角查找方法的示意图。 

具体实施方式

下面将结合附图和实施例对本发明做进一步的详细说明。 

本发明采用圆心角覆盖策略来获得任意节点在同构网络或者异构网络中的覆盖度。 

(一)在同构网络中基于圆心角覆盖度的休眠资格判断策略 

步骤1-1，对于任意节点u，获取其所有的邻居节点，放入邻居集Nu中； 

步骤1-2，遍历任意节点u的邻居集Nu中的所有邻居节点，提取出与任意节点u的距离在约束距离D_初(0，d₀)范围内的所有邻居节点，放入约束邻居集CNu中； 

其中，约束距离D_初(0，d₀)中的右边界值d₀等于感知半径r，即D_初(0，r)。 

参见图1所示，在一个同构的无线传感器网络中，任意节点u的邻居节点包括有第一邻居节点v₁、第二邻居节点v₂、第三邻居节点v₃、第四邻居节点v₄、第五邻居节点v₅、第六邻居节点v₆和第七邻居节点v₇，而与任意节点u的距离在(0，r)范围内的所有邻居节点只有第六邻居节点v₆，则将第六邻居节点v₆放入约束邻居集CNu中，即CNu＝{v₆}。 

步骤1-3，依据圆心角覆盖策略，计算出约束邻居集CNu中的邻居节点对任意节点u感知区域的覆盖度CDu(简称为邻-节覆盖度CDu)； 

参见图1所示，依据圆心角覆盖策略，计算出约束邻居集CNu＝{v₆}对节点u的感知区域的邻-节覆盖度CDu。 

步骤1-4，判断该邻-节覆盖度CDu是否满足同构网络覆盖度K_同对任意节点u感知区域的覆盖度要求；若满足，则判定任意节点u为冗余节点，使任意节点u进入休眠状态；若不满足转入步骤1-5； 

步骤1-5，当同构网络不允许覆盖空洞存在时，任意节点u保持工作状态；当同构网络允许覆盖空洞存在时，转入步骤1-6； 

步骤1-6，调整约束距离D_调(0，d₁)，且d₁＝d₀+Δd；若 则表明约束邻居集CNu中的邻居节点范围已超过同构网络允许空洞的最大范围，任意节点u保持工作状态； 

若 则转入步骤1-7； 

d₁为调整后的右边界值；Δd为区域扩张的步长，通常可取 toler表示同构网络允许的空洞占感知区域的百分比，在本发明中可设置为15％～30％； 

步骤1-7，依据调整后的约束距离D_调(0，d₁)，重新获取任意节点u的约束邻居集CNu，转入步骤1-3，直到已判定出任意节点u进入休眠状态或者保持工作状态。 

参见图1A所示，在调整后的约束距离D_调(0，d₁)下，任意节点u的约束邻居集更新为CNu＝{v₁，v₄，v₆}。 

(二)在异构网络中基于圆心角覆盖度的休眠资格判断策略 

步骤2-1，初始化任意节点u的覆盖度调整变量CDPlus＝0； 

对于任意节点u获取其所有的邻居节点，放入邻居集Nu中，并从邻居集Nu中选取第一个邻居v； 

步骤2-2，计算任意节点u与其第一个邻居v之间的距离d_u-v；用ru表示任意节点u在异构网络中的感知半径，rv表示第一个邻居v的感知半径； 

步骤2-3，若ru＜rv且d_u-v＜rv-ru时，表明任意节点u的感知区域包含在第一个邻居v的感知区域中，则将任意节点u的覆盖度调整变量CDPlus增加1，即CDPlus＝CDPlus+1； 

步骤2-4，若ru≥rv或d_u-v≥rv-ru且满足 时，表明第一个邻居v对任意节点u的感知区域有部分覆盖，则将第一个邻居v记录到约束邻居集CNu中； 

步骤2-5，从邻居集Nu中选取下一个邻居节点，重复步骤2-2到步骤2-4，直到邻居集Nu中的所有节点处理完毕； 

参见图2所示，在一个异构的无线传感器网络中，任意节点u的邻居节点包括有第一邻居节点v₁、第二邻居节点v₂、第三邻居节点v₃、第四邻居节点v₄、第五邻居节点v₅、第六邻居节点v₆和第七邻居节点v₇，而满足步骤2-3中的条件ru＜rv且d_u-v＜rv-ru的所有邻居节点只有第五邻居节点v₅，所以任意节点u的覆盖度调整变量CDPlus被调整为1，即CDPlus＝1。而满足步骤2-3中的条件 的邻居节点只有第一邻居节点v₁、第四邻居节点v₄和第六邻居节点v₆，所以任意节点u的约束邻居集CNu＝{v₁，v₄，v₆}。 

步骤2-6，依据圆心角覆盖策略，计算约束邻居集CNu对任意节点u的邻-节覆盖度CDu； 

步骤2-7，依据覆盖度调整变量CDPlus对邻-节覆盖度CDu做出调整，即CDu_调＝CDu+CDPlus； 

步骤2-8，判断调整后的邻-节覆盖度CDu_调是否满足异构网络对覆盖度的要求；若满足，则判定任意节点u为冗余节点，使任意节点u进入休眠状态；若不满足，则使任意节点u保持工作状态。 

在本发明中，当确定了任意节点的约束邻居集之后，采用如下的圆心角覆盖策略来计算约束邻居集对任意节点的感知区域的覆盖度。 

(三)圆心角覆盖策略 

在本发明中，无线传感器网络为二维网络，其网络中的各个无线传感器(即节点)的坐标均采用二维坐标表示。以图1A为例，节点u的约束邻居集CNu包括第一邻居节点v₁、第四邻居节点v₄和第六邻居节点v₆，即CNu＝{v₁，v₄，v₆}。记节点u的坐标为u(x_u，y_u)，第一邻居节点v₁的坐标为v₁(x_v1，y_v1)，第四邻居节点v₄的坐标为v₄(x_v4，y_v4)，第六邻居节点v₆的坐标为v₆(x_v6，y_v6)。 

以节点u为圆心，以r或ru为感知半径，作节点u的圆域感知区域。 

以第一邻居节点v₁为圆心，以rv₁为感知半径，作第一邻居节点v₁的圆域感知区域。 

以第四邻居节点v₄为圆心，以rv₄为感知半径，作第四邻居节点v₄的圆域感知区域。 

以第六邻居节点v₆为圆心，以rv₆为感知半径，作第六邻居节点v₆的圆域感知区域。 

在各个节点的感知范围内，节点u与CNu中的邻居节点之间的感知区域构形图如图3所示。节点u的圆域感知区域与第一邻居节点v₁的圆域感知区域在边界上的交点有A点和B点；节点u的圆域感知区域与第四邻居节点v₄的圆域感知区域在边界上的交点有C点和D点；节点u的圆域感知区域与第六邻居节点v₆的圆域感知区域在边界 上的交点有E点和F点。在本发明中，采用圆心角覆盖策略解析邻居节点分别对节点u的感知区域的覆盖度的影响，从而判断出是否达到网络覆盖要求。 

在本发明中，圆心角覆盖策略包括有下列的执行步骤： 

步骤3-1，在无线传感器网络中建立平面坐标系，节点u的坐标记为u(x_u，y_u)，第一邻居节点v₁的坐标为v₁(x_v1，y_v1)，则节点u与节点v₁的距离表示为 $d_{u-v1}=\sqrt{{(x_u-x_{v1})}^2+{(y_u-y_{v1})}^2};$

步骤3-2，节点u与第一邻居节点v₁的感知区域相交区域对应交点A的圆心角∠v₁uA，对于同构网络，依据垂径定理及三角关系式，有 对于异构网络，依据余弦定理，有 

步骤3-3，以逆时针方向为正方向，两个节点之间连线的圆心角 且∠v₁ux的取值范围为[0，2π)； 

若x_v1＞x_u且y_v1＞y_u时，则调整∠v₁ux＝∠v₁ux+π； 

若x_v1＜x_u且y_v1＞y_u时，则调整∠v₁ux＝∠v₁ux+π； 

若x_v1＞x_u且y_v1＜y_u时，则调整∠v₁ux＝∠v₁ux+2π； 

步骤3-4，交点A与节点u形成的圆心角记为∠Aux，且∠Aux＝∠v₁ux-∠v₁uA，标志位Flag＝0； 

交点B与节点u形成的圆心角为∠Bux，且∠Bux＝∠v₁ux+∠v₁uB，标志位Flag＝1； 

若∠v₁ux＜∠v₁uA时，则调整∠Aux＝∠Aux+2π； 

若∠v₁ux+∠v₁uA＞2π时，则调整∠Bux＝∠Bux-2π； 

步骤3-5，依据步骤3-1至步骤3-4对节点u的其他邻居节点进行圆心角计算，则有：第四邻居节点v₄与节点u的感知区域相交点C和D形成的圆心角分别记为∠Cux、∠Dux；第六邻居节点v₆与节点u的感知区域相交点E和F形成的圆心角分别记为∠Eux、∠Fux； 

在本发明中，为了方便叙述，∠Aux也称为交点A的圆心角，∠Bux也称为交点B的圆心角，∠Cux也称为交点C的圆心角，∠Dux也称为交点D的圆心角，∠Eux也称为交点E的圆心角，∠Fux也称为交点F的圆心角。 

∠Aux与∠Bux为同一个邻居节点对应的圆心角； 

∠Cux与∠Dux为同一个邻居节点对应的圆心角； 

∠Eux与∠Fux为同一个邻居节点对应的圆心角。 

步骤3-6，将步骤3-4和步骤3-5中获得的圆心角组成一个角度集合OAS{∠Aux，∠Bux，∠Cux，∠Dux，∠Eux，∠Fux}，然后对该OAS{∠Aux，∠Bux，∠Cux，∠Dux，∠Eux，∠Fux}依据从小到大的顺序排列，从而得到有序数组Angles； 

在初始时，每一个圆心角所对应的覆盖度均为0；则有，在有序数组Angles中的各圆心角所对应的覆盖度组成的数组记为ACD(简称为覆盖度数组)； 

步骤3-7，遍历有序数组Angles中的各圆心角元素，当遍历到第i个角度时，若此角度的标志位Flag＝0，则不对该圆心角进行处理； 

若Flag＝1，则从第i个角度向前查找同一个邻居节点上的另一个交点对应的圆心角，若未询到该圆心角，则从有序数组Angles中的最后一个圆心角元素向前查找，直到获得同一个邻居节点上的另一个交点对应的圆心角；从第i个角度开始遍历时，途经每个圆心角就使得覆盖度要加“1”； 

若Flag＝1，则从第i个角度向前查找同一个邻居节点上的另一个交点对应的圆心角，若获得同一个邻居节点上的另一个交点对应的圆心角，从第i个角度开始遍历时，途经每个圆心角就使得覆盖度要加“1”； 

在本发明中，第i个角度是指∠Aux、∠Bux、∠Cux、∠Dux、∠Eux和∠Fux中的之一。 

为了对步骤3-7的查找过程进行详细说明，请参见图4所示，图中，A点对应的圆心角∠Aux则为第i个角度，与∠Aux对应的同一个邻居节点的交点B的圆心角为∠Bux，则从该第i个角度向左(向前)方向进行查找，途经∠Fux圆心角后直到∠Bux，根据第一邻居节点v₁对节点u与交点A、B形成的区域有覆盖，因此∠Aux的覆盖度增加1(即ACD[i]＝ACD[i]+1，从而替换初始时的覆盖度)、∠Bux的覆盖度增加1、∠Fux的覆盖度增加1。 

步骤3-8，以覆盖度数组ACD中的最小值作为节点u的感知区域被覆盖的度数CDu。 

本发明的一种基于圆心角覆盖度的无线传感器网络节点休眠资格判断方法，该方法通过计算邻居节点对本节点感知区域的覆盖度，来判断本节点是否冗余。在圆心角覆盖策略中通过调整约束距离不断增加邻居节点数目来提高覆盖度，只利用局部节点的信息，大大降低了计算的复杂度。尤其当网络允许一定程度的覆盖空洞时，与传统的休眠资格判断方法相比，本方法可以关闭更多的冗余节点，获得更长的网络生存时间。同时，本方法还适用于由感知半径不同的节点构成的异构网络。因此，本方法实用性更高，应用范围更广。