基于全局贪心的有向传感器网络覆盖算法

摘要：针对分布式贪心算法(DGreedy)以传感器节点的剩余能量为优先级，节点处理顺序没有考虑相邻节点间的关系对网络覆盖率的影响，从而影响覆盖率的不足，在此提出了一种新的有向传感器网络覆盖算法。基于全局贪心的原则，以节点一重覆盖区域面积的大小为优先级，优先确定一重覆盖区域面积最大的传感器节点方向，从而保证传感器网络的一重覆盖区域面积更大，重叠覆盖区域较少。对比实验结果表明，该算法能有效提高覆盖率。
关键词：有向传感器网络；全局贪心；一重覆盖；Matlab

0 引言
    覆盖问题是无线传感器网络的一个基本问题，是近年来该领域的研究热点。目前多数覆盖控制的研究成果都是基于满足全向性感知模型的传感器进行的，但在实际应用中，许多有向传感器，如视频传感器，已被广泛应用于无线多媒体传感器网络中。与基于满足全向性感知模型的无线传感器网络相比，有向传感器网络的覆盖问题更复杂，是该领域的一个重要研究方向。
    Ma等首先提出了有向传感器网络的概念，设计了一种有向传感器感知模型，并研究了有向传感器网络的覆盖完整性问题。文献等都采用了基于虚拟势场的思想进行有向传感器网络覆盖控制。陶丹等在文献中设计了一种方向可调的感知模型，并以此为基础首先提出了基于虚拟势场的有向传感器网络覆盖增强算法，通过引入“质心”的概念，将有向传感器用质心点代替，并将有向传感器网络的覆盖问题转化为质心分布问题，质心点在虚拟力的作用下运动，消除感知盲区和重叠区。传统基于虚拟势场的有向传感器网络覆盖增强算法只判断和调整方向，节点的调整量为固定值，针对这一问题，黄帅等在文献中利用虚拟力与角度调整量间的关系，根据虚拟力的大小改变节点的角度调整量，提高了网络的调整效率。但是，以上基于虚拟势场思想的无线传感器网络覆盖方法，每个节点均需计算多个相邻节点的合力，节点受力随转动过程不断变化，使得算法较复杂；且节点根据力矢量的大小和方向进行转动，转动角度取值过小会增加调整时间，取值过大则会引起频繁的计算和传感方向的反复调整，且因合力未必为0，可能导致调整过程中角度往复震荡。文献提出了一种分布式贪心算法(DGreedy)，以传感器节点的剩余能量为优先级，每个传感器基于局部贪心原则选择工作方向，使传感器网络覆盖尽可能大的区域。但是，DGreedy算法受传感器节点处理顺序影响较大，以剩余能量为优先级的方法没有考虑节点问覆盖区域的相互影响，从而影响整个网络的覆盖率。
    本文基于全局贪心原则，提出了一种有向传感器网络覆盖算法。以节点各方向下一重覆盖区域的大小为优先级，优先确定一重覆盖区域面积最大的传感器节点方向，保证了传感器网络的一重覆盖区域面积更大，重叠覆盖区域较少。对比实验验证了本文算法的有效性。

1 覆盖算法
1．1 DGreedy算法
    分布式贪心算法DGreedy由程卫芳等人提出，并应用于有向传感器网络覆盖中。DGreedy假设传感器节点不同方向的感应范围互不重叠，4个可选方向的传感器节点示例如图1所示，图中Si,j表示第i个传感器的第j个方向。文中还假定所有传感器节点具有相同的结构。给每个传感器分配一个彼此不同的优先级，并定义Gi,j表示节点Si的第J个方向上，没有被更高级的感应邻居所覆盖的面积。

    DGreedy算法具体描述如下：
   
1．2 改进的DGreedy算法
    DGreedy算法每个传感器以局部贪心的原则确定工作方向，只要感应邻居间的覆盖消息能准确传递，就能在有限时间内终止。但是，传感器的决策顺序，即优先级对最终的覆盖效果有极大的影响，文中以传感器剩余能量为优先级，但以剩余能量为优先级的处理顺序没有考虑覆盖区域面积的影响，因此并不一定能保证传感器的覆盖区域面积最大。同时，文中没有考虑孤立传感器或优先级最高的传感器的传感方向，如图2(a)所示S1～S5五个传感器，假设它们的剩余能量，即优先级从高到低，则S1的传感方向最先被确定，由于S1的优先级最高，其它传感器的存在对它没有影响，此时S1的传感方向可以是4个可选方向中的任意一个；由于S1～S4四个节点互不为邻居，且它们的优先级均高于S5，同理S2～S4的传感方向也可以是4个可选方向中的任意一个，若S1～S4最终选择的方向如图2(a)所示，此时S5的4个可选方向中，均存在重叠区域，显然应选择重叠区域最小的S5,2方向。

    本文传感器节点以全局贪心的思想确定工作方向，以传感器节点的最大一重覆盖区域面积大小为优先级，最大一重覆盖区域的定义与DGreedy算法中的Gi,j类似，即节点与邻居间没有重叠的区域，某一节点在某方向上的一重覆盖区域面积越大，则该节点和方向越先被确定。如图2(a)所示，S1～S4四个节点在一个方向上与S5均有重叠覆盖区域，以S1为例，S1存在一个方向为完一重覆盖，因此拥有最高优先级；同理，S2～S4拥有与S1相同的优先级。因此S1～S4的传感方向最先被确定，且选择的方向均为完全一重覆盖方向，如图2(b)所示，此时S5的4个可选方向中，均为完全一重覆盖，可依据固定顺序或指向覆盖区域中心等原则，选择其中任一方向。显然，图2(b)的覆盖效果好于图2(a)。
    改进的Greedy算法描述如下：

   

2 实验及分析
    下面通过模拟实验评估本文算法的性能，所有实验都用Matalb 7．4．0实现。实验中设定监测区域大小为边长500 m的正方形，不同数目的有向传感器节点随机部署在监测区域中，传感器的覆盖角度为α=90°，传感器可选方向数为P=4，传感半径Rs=60 m。比较了本文算法、DGreedy算法及传感器随机选择工作方向的随机算法Random算法的性能。

    当节点个数N=50时，3种算法的覆盖效果如图3所示，图中的圆形表示每个节点的可能覆盖范围，灰色扇形表示每个节点的实际覆盖区域，颜色越深，表示覆盖重叠数越多。很显然，Random算法的覆盖结果中重叠覆盖区域最多，因此覆盖率最低，本文算法覆盖率最高。不同传感器节点数目时，3种算法的覆盖率如图4所示。由于本文算法每次都取一重覆盖区域面积最大的传感器节点及其传感方向，使得整个网络的一重覆盖率较高，多重覆盖率较低；DGreedy算法以剩余能量为优先级，选取一重覆盖区域面积最大的方向，但优先级最高的节点所选方向不一定是所有节点中一重覆盖区域面积最大的方向，因此覆盖率较本文算法有所降低；Random算法节点的覆盖方向随机产生，重叠覆盖区域最多，因此覆盖率最低。

3 结语
    有向传感器由于传感范围有限，其覆盖问题比基于全向感知模型的传感器覆盖更复杂。有向传感器的覆盖问题，就是按某种原则选择每个传感器的工作方向，以减少重叠覆盖区域，增加一重覆盖区域。本文以传感器最大一重覆盖区域面积作为优先级，以全局贪心原则确定传感器的工作方向，旨在调度传感器的工作方向以覆盖尽可能大的区域。通过仿真实验，与DGreedy算法和Random算法进行比较，验证了本文有向传感器网络覆盖增强算法的有效性。