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

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

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

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