高效无线传感器网络强k—栅栏覆盖节能算法(2)

　　如果说带状监控区域M是强k栅栏覆盖的，那么区域M内至少存在k条由传感器节点的感知圆盘彼此相接形成的不相交的传感栅栏。图1是一个强2栅栏覆盖的示意图，其中灰色节点的感知圆盘形成了两条强栅栏，入侵者沿任意穿越路径通过带状区域M时，至少会被2个传感器节点感知。图中①和②是两条不同方向的穿越路径，而③和④不是穿越路径。

　　1.2强栅栏覆盖的节能问题

　　在无线传感器节点随机部署的条件下，为了保证带状监控区域中能够形成强栅栏覆盖，必须进行高密度部署。但是随机部署方式无法保证无线节点的分布是绝对均匀的，因此监控区域中构建的栅栏内也会出现节点疏密程度不一的情况，如果栅栏中的节点都工作在最大感知半径状态（感知功率最大），那么栅栏中节点密集区段的平均能耗就偏高。如图2所示，节点A、B、C、D、E、F、G、H构成一条传感栅栏，其中DEFG区段节点的分布较为密集，如果将节点D、E、F、G的感知圆盘调整到图中虚线圈所示的大小，则传感栅栏依然贯通，且栅栏的能耗会明显降低。可见，栅栏中节点疏密程度的不均性为其能耗提供了较大的压缩空间。

　　3强k栅栏覆盖的节能算法

　　由于强k栅栏覆盖最小能耗问题是NPhard的，因此，需要给该问题设计一个多项式时间近似算法，求得该问题的次优解。本章针对该问题提出了一个前向节点相关的启发式算法HARPN。如果带状监控区域是强k栅栏覆盖的，若每条栅栏的能耗取到最小值，则k栅栏覆盖的能耗一定最小，所以强k栅栏覆盖最小能耗问题可以转化为求每条栅栏的最小能耗问题，这里说的最小值均指次优解。

　　3.1节能理论分析

　　由于栅栏中节点密集区段具有较大的能耗压缩空间，因此，在保证栅栏传感链路连通的情况下，通过降低栅栏中节点的感知功率能有效降低监控区域中栅栏覆盖网络的能耗。

　　定义8栅栏边。强栅栏中任意两个相邻的无线传感器节点构成一条栅栏边。显然，一条栅栏是由若干条栅栏边首尾相接构成的。

　　定义9节能增益。若无线节点的感知功率减小后，其感知圆盘仍能和栅栏中两个相邻节点的感知圆盘相交，那么将该节点最大感知功率与减小后感知功率的差称为该节点的节能增益。

　　在本文中，无线节点的能耗模型为E=μr2，其中：r为感知半径；μ为能量消耗系数，是常数[12]。本文的研究工作只考虑传感器节点传感模块的能耗，暂不考虑通信、计算等其他能耗。

　　3.3HARPN算法描述

　　为了实现带状监控区域内无线节点能耗的均衡性，HARPN算法按照轮次进行，每个轮次分三个阶段：强k栅栏形成阶段、感知功率调整阶段和工作阶段。在每轮次的强k栅栏形成阶段，要综合考虑节点的剩余能量、工作的轮次数以及栅栏中节点个数等因素，既要保证网络能耗的均衡性，又要使形成强k栅栏覆盖的节点尽可能少。HARPN算法中轮次的详细步骤如下：

　　步骤1

　　本轮次开始，在监控区域M中形成一个强k栅栏的网络覆盖，并将生成的每条栅栏存入栅栏队列barrierList中。

　　步骤2

　　若barrierList中元素个数>0，执行步骤3；否则执行步骤9。

　　步骤3

　　从barrierList中取出一个栅栏b，执行步骤4。