无线传感器网络低复杂度覆盖算法研究

中国船舶重工集团公司第七一六研究所 庄 强

无线传感器网络低复杂度覆盖算法研究

中国船舶重工集团公司第七一六研究所 庄 强

无线传感器网络的应用基础是网络覆盖，传感节点能量有限、存储及运算能力受限等特点决定了覆盖算法的低复杂度。本文通过研究若干邻居节点对某一节点的覆盖情况，判定该节点是否为冗余节点，提出了低复杂度覆盖算法。

无线传感器网络；低复杂度；覆盖算法；邻居节点

1 引言

无线传感器网络是伴随无线通信、嵌入式传感器技术以及分布式信息处理技术的发展而新兴的一种信息获取技术[1]。网络覆盖是无线传感器网络的应用基础，它体现了无线传感器网络对物理世界的感知能力，网络覆盖算法的优劣直接影响着网络的感知质量。覆盖控制问题，就是在节点所携能量、计算、存储能力和网络通信带宽等资源受到严重约束的条件下，通过对网络中传感器节点进行优化部署和合理调度等手段，有效地利用传感器网络极其有限的节点资源，最后达到改善传感器网络监控服务质量的目的[2]。

2 低复杂度算法

目前，有关判定节点是否为冗余节点的覆盖算法主要有Perimeter Pruning算法和CNNN算法[3]。CNNN算法的复杂度相比Perimeter Pruning算法有一定程度的降低，我们在此基础上进一步降低算法复杂度，以更好的满足传感节点低运算能力、低能耗的要求。

2.1 算法原理

为了便于研究，我们参照CNNN算法做如下定义：节点的邻居节点集合为

根据CNNN算法，只有在节点有近邻节点的情况下，它才有可能成为冗余节点。

如图1所示，三个圆分别表示节点v、u的覆盖圆及节点v的二倍感知半径圆，即远邻节点所在范围的最大值。已知节点v的覆盖圆被近邻节点u的覆盖圆覆盖了一部分，那么只需要考察节点v的覆盖圆未被覆盖的部分ADBE，即弧ADB和弧AEB所围成的区域的覆盖情况。能够覆盖上述区域的节点一定是v的邻居节点，而且这些节点一定位于以v为圆心、以为半径的圆的一定范围内。

图1 近邻节点覆盖情况

如图2所示，扇形HAu和扇形FBu分别以点A、点B为圆心、以为半径，其中H为线段vA的延长线与大圆的交点，F为线段vB的延长线与大圆的交点。由几何知识可以证明，由弧Hu、弧Fu和弧HJF所围成的范围HuFJH，其中的节点不能覆盖到ADBE区域；而由弧Hu、弧Fu和弧HKF所围成的范围HuFKH，其中的节点可以覆盖到ADBE区域。因此，只需要考察HuFKH范围内的节点对ADBE区域的覆盖情况，即可完成节点v是否为冗余节点的判定。HuFKH区域的面积是u与v的距离函数，即。假设无线传感节点均匀分布，则HuFKH区域内节点的数量与它的面积成正比。

图2 能覆盖ADBE区域的节点的范围

如图3所示，在邻居节点u覆盖的前提下，在HuFKH范围内选择一个节点w，它必能覆盖ADBE区域的一部分。在节点w的覆盖下，ADBE区域的未被覆盖的区域变得更小。图4中的图形LGw是以Lv为直径、LG为半径的扇形，图形MIw是以Mv为直径、MI为半径的扇形。然后继续考察ADBE区域其余部分的覆盖情况，也就是只需要考察HuFMwLH区域内的节点，其中表示方位。由于HuFMwLH区域的面积比HuFKH区域的面积更小，则需要考察的节点的数量也相应的减小了，从而进一步降低算法的复杂度。

图3 第2个节点覆盖情况

同理，在节点u、w覆盖的前提下，在HuFMwLH范围内找到第三个节点，它必能覆盖ADBE区域内未被覆盖的一部分。接下来再考察余下的覆盖部分的覆盖情况，则需要考察更小的范围内的节点，算法的复杂度会更进一步降低。以此类推，直到v的覆盖范围被完全覆盖、判定v是冗余节点，或遍历相关范围内的所有节点后判定v不是冗余节点，算法结束。

2.2 算法描述

（1）初始状态时，每个节点在距离自己的范围内广播一个HELLO消息，消息包括本节点ID号和地理位置信息。每个节点随机等待一段时间后再广播，以免多个节点同时广播HELLO消息造成信道冲突和信息丢失；

（2）每个节点收到其他节点的HELLO消息后，建立邻居节点信息表，包括邻居节点的方位、距离，并区分出近邻节点和远邻节点；

（3）节点判断是否有距离为0的节点，如果有，则自己为冗余节点，结束；

（4）节点如果没有近邻节点，或邻居节点总数小于3，则自己不是冗余节点，结束；

（5）节点选择一个距离自己最近的节点，考察该邻居节点对自己的覆盖圆的覆盖情况，根据上述算法原理，再在确定范围内选择第二个邻居节点，继续考察第二个节点对自己的覆盖情况，这样依此类推直到完全覆盖为止，则判定节点为这冗余节点，否则不是冗余节点，程序结束。

算法流程图如图4所示。

图4 算法流程图

3 结束语

本文研究了无线传感器网络覆盖算法的复杂度问题，通过分析Perimeter Pruning算法和CNNN算法的原理，认为算法复杂度可以进一步降低，因而提出了一种低复杂度的覆盖算法。本文提出的低复杂度覆盖算法比另两种算法的复杂度有明显的降低。但是，算法对网络模型过于理想化，没有考虑到实际中的障碍、噪声和实际通信距离的影响，今后的工作中将解决上述问题。

[1]孙利民,李建中,陈渝,等无线传感器网络[M].北京：清华大学出版社,2005

[2]赵大胜.无线传感器网络广播与节点休眠算法中的节能覆盖问题研究[D].武汉:华中科技大学,2005.