基于能量均衡的最大化覆盖目标算法*

南书坡,冯乃勤

(1.河南师范大学新联学院,郑州 451464;2.河南师范大学计算机与信息工程学院,河南 新乡 453007)

基于能量均衡的最大化覆盖目标算法*

南书坡1*,冯乃勤2

(1.河南师范大学新联学院,郑州 451464;2.河南师范大学计算机与信息工程学院,河南 新乡 453007)

目标覆盖问题是无线传感网络WSNs(Wireless sensor networks)最重要的问题之一。每个目标至少被一个传感节点覆盖,为此提出基于能量均衡的最大化覆盖目标EMNL(Energy-balance-based Maximizing Network Lifetime)算法。EMNL算法将所有传感节点划分不同的传感节点覆盖区SC(Sensor Cover),致使每个SC能够维持对所有目标监测一个固定时间。通过有选择性选择一个SC活动,而其他SC休眠,进而提高能量利用率,延长了网络寿命。EMNL算法构建了不同不相邻SC,进而最大化网络寿命。最后,建立仿真环境,并进行性能仿真。此环境下的数据表明,在EMNL算法有效地扩延生存时间,也提升了覆盖率。

无线传感网;能量;目标覆盖;传感节点覆盖区;生存时间

近期,无线传感网络 WSNs(Wireless Sensor Networks)受到广泛关注。WSNs是由大量的微型、能量受限、低功耗的传感节点组成。这些传感节点具有感测数据、处理以及存储功能[1]。将这些传感节点部署于监测区域,如森林、战场。这些部署了传感节点的监测区域称为兴趣区域。在兴趣区域内,每个传感节点试着感测环境数据,然后再将数据传输管理中心。

为了实时地、无遗漏地监测环境,就需要保证传感节点对兴趣区域覆盖率的最大化。然而,由于传感节点存在硬件故障以及能耗问题,难以保证所有传感节点能正常工作。一旦传感节点能耗殆尽,它就无法工作,也无法感测数据,就出现覆盖空洞。因此,如何提高兴趣区域的覆盖率已成WSNs的研究热点[2-3]。

依据覆盖区域面积的不同,可将覆盖划分为点覆盖和区域覆盖。所谓点覆盖是指由一个单一的传感节点覆盖的区域,而区域覆盖是由一群传感节点共同覆盖的区域。然而,实际上,无论是点覆盖还是区域覆盖,均需要维持兴趣区域的覆盖率。

通常,WSNs覆盖要求是:以有限的能量对兴趣区域实施尽可能的连续监控。本文着重关注区域覆盖问题。将这些需要被覆盖的区域也称不目标覆盖区域,简称为目标覆盖[4-5]。换而言之,以目标覆盖为本文的研究对象,研究的目的在于对多个目标覆盖区域进行尽可能长时间的监控。

为了保存节点能量,传感节点通常具有活动和休眠两种状态。在活动状态时,传感节点实时监控环境,其将消耗大量能量。而在休眠状态,传感节点处于空闲状态,不消耗能量。

为了保证所有覆盖目标能够最大时间地覆盖,常采用的方法不是保证所有传感节点均在活动状态,而是选择一部分节点能够覆盖目标区域。这一部分节点称为传感节点覆盖区SC(Sensor Cover),它们的活动时间称为生存时间。因此,覆盖目标问题是就是保证这些SC在固定时间内工作,进而监控兴趣区域。所有SC的生存时间就是网络寿命。

目前,针对目标覆盖问题已进行了大量的研究工作[6-7]。文献[8]提出高能效启发式算法HEEH(High-Energy-Efficient Heuristic)。HEEH算法仅选择能量最多的传感节点构成不相邻的覆盖集,并最小化SC集,进而消除覆盖冗余问题。文献[9-10]也提出利用整数线性规划ILP(Integer Linear Programming)构建SC集。此外,文献[11]也提出基于权重的启发式算法WH(Weight-based Heuristic)。WH算法先选择剩余能量最高的节点构建SC,然后再优化。

为此,本文针对WSNs的目标覆盖问题,提出基于能量均衡的最大化覆盖目标EMNL(Energy-Balance-Based Maximizing Network Lifetime)算法。EMNL算法先将传感节点划分不同的传感节点覆盖区SC(Sensor Cover),致使每个SC覆盖所有目标一段时间,进而平衡网络能耗,提高网络寿命。实验数据表明,提出的EMNL算法有效地延长网络寿命,并增加覆盖率。

1 约束条件

假定在M×M区域内随机分布了n个覆盖目标T={t1,t2,…,tn}。为最大时间地监测这些覆盖目标,在整个M×M区域内随机部署m个传感节点,即S={s1,s2,…,sm}。其中,每个传感节点的传输半径为Rs。传感节点si的初始能量为bi。

此外,每个传感节点存在活动和休眠两种状态,它们可彼此切换。在活动状态,传感节点感测目标覆盖区域内的信息,而在休眠状态,传感节点不感测信息,进而保存能量。

此外,本文引用的标识符如表1所示。

定义1传感-目标覆盖关系矩阵Rm×n矩阵Rm×n中元素Rij的定义如式(1)所示:

(1)

定义2关键目标集CTS(Critical Target Set) 在整个覆盖目标集T内,若一覆盖目标内所有节点的能量和是最小的,则该覆盖目标称为CTS,定义如式(2)所示:

(2)

定义3关键节点CS(Critical Sensor) 若节点至少覆盖了一个CTS,则该传感节点就称为CS。

定义4传感节点覆盖区SC(Sensor Cover) 对于任意SC区Ck,它是由矩阵R的一系列行组成。致使,对于每一列j,至少在Ck内有一行i满足Rij=1。

定义5传感节点覆盖区SC的生存时间Ck的生存时间等于Ck内节点的最小电池供电时间,定义如式(3)所示:

(3)

定义6网络寿命L网络寿命就是所有SC的生存时间之和,定义如式(4)所示:

(4)

式中:|C|为网络内SC的个数。

为了更好地理解上述定义,举例说明。假定网络内存在4个传感节点s1、s2、s3以及s4,3个覆盖目标t1、t2、t3。此外,假定每个传感节点的初始能量均为1(bi=1)它们的矩阵R4×3定义如下:

t1t2t3

(5)

依据R4×3内的元素可知,传感节点s1覆盖t2、t3,即s1={t2,t3}。类似地,s2={t1,t2}、s3={t1,t3}、s4={t1,t3}。依据定义2可知,覆盖目标t2为CTS,因为只有t2只被两个节点覆盖,它的生存时间最低仅为2,相应地,传感节点s1、s2为CS节点。

2 EMNL算法

EMNL算法就是先计算CTS以及SC,然后再用它们构建SC。具体而言,当明确了CTS,就计算覆盖所有CTS的最小数的SC,而对于剩余未覆盖目标,就从剩余的传感节点集中寻找剩余能量最大的传感节点,然后再从这些节点中选择具有最大目标覆盖的节点。EMNL协议的目的就是选择传感节点,致使所有目标集都被覆盖。

首先,利用定义2、定义3计算CTS、SC。这两个集分别表示为Tcritical、Scritical。然后构建Ck。具体构建步骤如下:

(6)

构建Ck完整过程的伪代码如图1所示。

图1 算法1的伪代码

算法1中UB表示SC数。网络内m个传感节点它们的能量分别为{b1,b2,…,bm}和n个覆盖目标{t1,t2,…,tm}。而覆盖目标tj的最大覆盖时间为Uj,定义如式(7)所示:

(7)

现在,取网络寿命的上限,因此,UB的定义如式(8)所示:

UB=min{U1,U2,…,Un}

(8)

为了降低能耗,就是降低Ck集数。因此,利用最小化函数最小化Ck数。而最小化函数的伪代码过程如图2所示。

图2 算法2的伪代码

EMNL协议通过构建多个SC,致使每个SC覆盖整个目标,同时最大化网络寿命。仍以式(6)所示的矩阵R4×3为例。依据文献[8]所采用的算法HEEH仅产生一个CS,即C1={s1,s2},其网络寿命为1单元。而文献[11]所采用的算法WH,是选择最高能量的节点构建SC,它与HEEH算法产生相同的C1={s1,s2}。而EMNL算法产生一个CTS集t2,并且由传感节点s1、s2覆盖。最后,EMNL算法产生两个SC,分别为C1={s1,s3}、C2={s2,s4},并且网络寿命为2。

3 性能分析

3.1 仿真参数

本小节对EMNL算法进行仿真,分析EMNL算法的性能[12]。考虑200 m×200 m的网络区域,仿真参数表1所示。在性能分析过程中,选择平均SC规模、SC的生命周期、剩余能量、网络覆盖率作为性能指标。同是选择HEEH[8]和WH[11]两个算法作为参照。每次仿真独立重复100次,取平均值作为最终的实验数据。

表1 仿真参数

3.2 数值分析

首先,分析了SC的生存时间。图3显示了平均SC的生存时间随节点数的变化情况。依图3可知,生存时间随节点数的增加而下降,原因在于:节点数增加,相应地活动节点的比例也越大,最终,导致网络能耗增加。与HEEH和WH相比,EMNL算法的平均生存时间得到有效地提高。原因在于:EMNL能够有效构建SC,并平衡网络能耗,提高能量利用率。

图3 SC的生存时间

其次,分析了网络的剩余能量,数值结果如图4所示。图4的数据来自于仿真了7 200 s后网络的剩余能量。依图4可知,网络剩余能量随节点数的增加而呈下降趋势。与HEEH和WH算法相比,EMNL算法的剩余能量最多。原因在于EMNL算法能够有效地利用能量,平衡了能耗。

图4 剩余能量

图5 覆盖率

最后,分析了EMNL算法的覆盖率,实验数据如图5所示。从图5可知,覆盖率随节点数增加而上升,原因很简单:节点越多,覆盖区域面积越多,最终覆盖率越高。此外,在节点数较低时,HEEH和WH算法的覆盖率极低,而EMNL算法达到97%。随着节点数的增加,HEEH和WH算法的覆盖率也逐渐升高,但仍低于EMNL算法的覆盖率。

4 总结

本文针对无线传感网络的覆盖问题,提出EMNL算法。EMNL算法从能量平衡角度,将传感节点划分不同的SC。在某一时刻,所有目标只由一个SC覆盖,而其他SC休眠,进而保存网络能量,提高网络寿命。实验数据也证实,与HEEH和WH算法相比,EMNL算法有效地降低能耗,提高了网络寿命。

[1] Rehman A,Abbasi A Z,Islam N,et al. A Review of Wireless Sensors and Networks Applications in Agriculture[J]. Compute Stand Interfaces,2014,36(2):263-270.

[2] Li Z,Wang N,Franzen A,et al. Practical Deployment of an In-Field Soil Property Wireless Sensor Network[J]. Compute Stand Interfaces,2014,36(2):278-287.

[3] Alcaraz C,Lopez J. Diagnosis Mechanism for Accurate Monitoring in Critical Infrastructure Protection[J]. Compute Stand Interfaces,2014,36(3):501-512.

[4] 付永生,李善平,周波. 无线传感网络中能量均衡的连通支配集算法[J]. 传感技术学报,2012,23(8):114-1145.

[5] Guha S,Khuller S. Approximation Algorithms for Connected Dominating Sets[J]. Algorithmica,2014,20(4):374-387.

[6] Yin B,Shi H,Shang Y. An Efficient Algorithm for Constructing a Connected Dominating Set in Mobile Ad Hoc Networks[J]. Journal of Parallel and Distributed Computing,2011,71(1):27-39.

[7] 张静,贾春福. 无线传感器网络基于权值的极小支配集路由算法[J]. 传感技术学报,2009,22(12):1784-1788.

[8] Manju A. High-Energy-First Heuristic for Energy Efficient Target Coverage Problem[J]. Int J Ad Hoc Sens Ubiquit Comput,2011,2(11):45-58.

[9] Wu J. Extended Dominating-Set-Based Routing in Ad Hoc Wireless Networks with Unidirectional Links[J]. IEEE Trans on Parallel and Distributed Systems,2012,13(9):866-881.

[10] 陈勤,朱韬,张旻. 基于域的分布式最小连通支配集启发式算法[J]. 计算机系统应用,2011,20(2):201-205.

[11] Mini S,Udgata S K,Sabat S L. Sensor Deployment and Scheduling for Target Coverage Problem in Wireless Sensor Networks[J]. IEEE Sensor Journal,2014,14(3):636-644.

[12] Orhan D,Kayhan E,Savio Tse. Semi-Asynchronous and Distributed Weighted Connected Dominating Set Algorithms for Wireless Sensor Networks[J]. Computer Standards and Interface,2015(42):143-156.

南书坡(1980-),男,汉,河南唐河人,硕士,讲师,研究方向为数据挖掘,人工智能。

Energy-Balance-BasedMaximizingNetworkLifetimeAlgorithminWirelessSensorNetworks*

NANShupo1*,FENGNaiqin2

(1.Xinlian College,Henan Normal University,Zhengzhou 451464,China;2.College of Computer and Information Engineering,Henan Normal University,Xinxiang He’nan 453007,China)

Target coverage problem is one of the important problems in wireless sensor network in which each target should be covered by at least one sensor. Therefore,EMNL(Energy-balance-based Maximizing Network Lifetime)algorithm is proposed. In EMNL,All the sensors are organized into different groups called sensor cover in such a way that each cover can monitor all the targets for a fixed duration. By keeping one sensor cover active at a time while others in sleep mode,sensors batteries can be used in efficient way. This helps in prolonging the network lifetime. EMNL algorithm proposes a new energy-efficient heuristic to schedule the sensors in different non-disjoint sensor covers which helps to maximize network lifetime. Finally,we construct simulation and analyze performance of EMNL algorithm. The simulation results show that EMNL algorithm outperforms than other algorithm in term of coverage ratio,and network lifetime.

wireless sensor networks;energy;target coverage;sensor cover;network lifetime

项目来源:河南省教育厅重点科研项目(14B520036)

2017-01-19修改日期:2017-05-24

TP393

:A

:1004-1699(2017)09-1401-04

10.3969/j.issn.1004-1699.2017.09.017