[page]
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算法描述如下:
[page]
当节点个数N=50时,3种算法的覆盖效果如图3所示,图中的圆形表示每个节点的可能覆盖范围,灰色扇形表示每个节点的实际覆盖区域,颜色越深,表示覆盖重叠数越多。很显然,Random算法的覆盖结果中重叠覆盖区域最多,因此覆盖率最低,本文算法覆盖率最高。不同传感器节点数目时,3种算法的覆盖率如图4所示。由于本文算法每次都取一重覆盖区域面积最大的传感器节点及其传感方向,使得整个网络的一重覆盖率较高,多重覆盖率较低;DGreedy算法以剩余能量为优先级,选取一重覆盖区域面积最大的方向,但优先级最高的节点所选方向不一定是所有节点中一重覆盖区域面积最大的方向,因此覆盖率较本文算法有所降低;Random算法节点的覆盖方向随机产生,重叠覆盖区域最多,因此覆盖率最低。
3 结语
有向传感器由于传感范围有限,其覆盖问题比基于全向感知模型的传感器覆盖更复杂。有向传感器的覆盖问题,就是按某种原则选择每个传感器的工作方向,以减少重叠覆盖区域,增加一重覆盖区域。本文以传感器最大一重覆盖区域面积作为优先级,以全局贪心原则确定传感器的工作方向,旨在调度传感器的工作方向以覆盖尽可能大的区域。通过仿真实验,与DGreedy算法和Random算法进行比较,验证了本文有向传感器网络覆盖增强算法的有效性。
『本文转载自网络,版权归原作者所有,如有侵权请联系删除』