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

　　摘要：为了进一步降低监测穿越行为的无线传感器网络强k栅栏覆盖的能耗，首先证明了强k栅栏覆盖最小能耗问题是NP难的，进而提出了一个节点感知功率可调的启发式节能算法HARPN。该算法根据栅栏中相邻节点的间距和前向节点的状态制定了4种节点感知半径的计算规则，再根据节点感知半径的大小确定节点的感知功率等级，在保证传感栅栏贯通的前提下，尽可能降低栅栏整体的能耗。理论分析和仿真实验表明，在相同的栅栏波动条件下，HARPN算法的适应性和稳定性更强，网络平均能耗约为Heuristic2算法的62%，网络的生存期进一步延长。

　　关键词：无线传感器网络；强k栅栏覆盖；NP难；启发式算法；节能

　　中图分类号：TP393.01

　　文献标志码：A

　　0引言

　　随着无线传感器网络（WirelessSensorNetwork，WSN）技术的不断进步，WSN的应用迅速渗透到许多领域，如在边境线上部署无线传感节点来监测非法越境者；在森林或易燃物品堆积场所周边部署无线传感器节点以监测火灾发生和火情蔓延情况；以及在敌营周边布设无线传感器节点来监视敌方的兵力部署和武器配备情况等[1]。这种通过在带状区域部署无线传感器节点来监测穿越该区域移动目标的技术被称为栅栏覆盖[2]，是无线传感器网络领域的一个研究热点。

　　栅栏覆盖的概念是由Gage[3]首次在机器人领域中提出的，Kumar等[1]首次给出了强栅栏和弱栅栏的定义，提出了一个判定监控区域是否被k栅栏覆盖的集中式算法，并推导出无线传感器节点随机部署的区域中存在弱k栅栏覆盖的临界条件。文献[4]推导出无线传感器节点随机部署的区域中存在强k栅栏覆盖的临界条件，并设计了一个在大规模无线传感器网络中搜索传感器栅栏的算法。文献[5]在证明基于概率感知模型的栅栏最小权重问题是NPhard问题的基础上，提出了一个有效构建最小权重k栅栏的近似算法（MinimumWeightBarrierAlgorithm，MWBA），来选择活动节点监测穿越行为。文献[6]在分析栅栏能耗和容错性的基础上，提出了一个容错k栅栏覆盖协议（AccumulationPointforBarrierCoverage，APBC），该协议能够很好地平衡节点能耗，延长网络的生命周期。文献[7]证明了在传感器节点移动能力有限的前提下，利用网格划分模型构建的1网格栅栏最小移动距离和问题是NPhard的，于是提出了构建1栅栏覆盖的近似算法——基准网格栅栏构建（ConstructingBaselineGridBarrier，CBGB）算法，进而设计了一个基于分治策略的k栅栏覆盖构建算法。文献[8]将移动模型引入到栅栏覆盖中，能够使用较少的节点以较高的概率发现入侵者。上述的这些研究工作，都要求无线传感器节点采用固定的传感半径进行工作，因此导致栅栏中节点的平均能耗过高。针对这一缺陷，文献[9]在证明感知功率分级可调的无线传感栅栏最小能耗是一个NPhard问题的基础上，提出了基于节点间距离的k栅栏最小能耗启发式算法Heuristic2，有效地降低了网络能耗，但该算法忽略了栅栏中节点分布疏密不均的客观事实，致使栅栏中相邻节点间距波动较大区段的节能效果明显低于其他区段。

　　本文针对感知功率分级可调的无线传感器强k栅栏覆盖网络中，节点间距波动较大区段能耗偏高的问题，提出了一个前向节点相关的启发式算法HARPN（HeuristicAlgorithmRelatingtothePreorderNodes）。该算法充分考虑了栅栏中节点间距波动的因素，根据栅栏中节点前向节点的感知半径确定节点的感知功率，算法的适应性和稳定性明显优于Heuristic2，网络的整体能耗进一步降低，生存时间更长。

　　1网络模型与问题描述

　　定义1感知圆盘。以传感器节点si∈S在监控区域M内的坐标（xi，yi）为圆心，以传感器的感知半径为半径的圆形区域称为该传感器的感知圆盘。若感知半径为0，节点感知模块休眠；否则，节点以l个感知功率等级中的某一个感知功率工作。

　　定义2穿越路径。起点和终点分别在监控区域M的两边，并将M分割成两个部分的任意曲线段称为穿越路径。

　　定义3入侵者。沿任意穿越路径穿过带状监控区域M的移动目标称为入侵者。

　　定义4强栅栏。由感知圆盘相叠或相切的传感器节点构成的一条连接监控区域两端的路径称为强栅栏，它使得穿越监控区域的入侵者至少被一个无线传感器感知。

　　定义5强k栅栏覆盖。如果入侵者沿着任意穿越路径通过监控区域M时，至少被k个无线传感器节点感知，则称该带状监控区域M是强k栅栏覆盖的。