能耗约束的无线传感器网络的目标覆盖和路由分配研究*

陆星家,陈志荣

(宁波工程学院理学院,浙江 宁波 315211)



能耗约束的无线传感器网络的目标覆盖和路由分配研究*

陆星家*,陈志荣

(宁波工程学院理学院,浙江 宁波 315211)

针对现有目标覆盖算法未充分考虑能量消耗和路由分配的不足,提出一种基于目标覆盖的能耗约束路由分配算法,该算法能够确保所有目标被完全覆盖,并降低数据传输能耗。首先,通过贪婪启发式策略获取最大集合覆盖。然后在集合覆盖基础上,通过协同进化机制对网络生存周期和时延等目标进行评价。利用适应度评估、轮盘赌选择、交叉、变异和记忆等进化机制改良目标的可行解。实验结果表明,提出的算法可以降低基于路由分配的目标覆盖算法的能量消耗,延长网络生存周期,降低网络传输时延。

无线传感器网络;目标覆盖;路由分配;能耗约束;最大集合覆盖算法;协同进化机制

无线传感器网络(WSN)是指具有一定自主性,能够从环境中收集数据,同时发送到数据处理中心的自组织网络。无线传感器网络通常是由许多小的,独立的和能量有限的传感器节点构成[1]。随着无线传感器网络技术的不断完善,其在军事和民用领域也有广泛的应用,如动物栖息地监测,地震预报,车辆跟踪系统和医疗保健等。在以上应用环境中,无线传感器使用自带电源感知目标,如果其电量耗尽,节点将停止工作,因此如何降低无线传感器网络的能量消耗,延长网络生存期一直是其研究的重点。

目标覆盖是无线传感器网络的核心应用,该问题指传感器节点感知进入网络监测范围的目标,并将感知数据传输到数据中心的过程。覆盖模型最早是由Cardei提出,该问题已被证明是一个NP-Hard问题[2]。非相交覆盖集和相交覆盖集是目标覆盖最主要的两种研究方法:其中非相交覆盖集指节点的覆盖范围没有重叠;相交覆盖集指节点覆盖范围可以重叠。Cardei利用相交覆盖集和Lingo线性规划模块对其优化,限制了实际场合中的应用[2]。Zobra利用相交和非相交覆盖集研究目标覆盖,两种方法对比发现,使用相交覆盖集可以有效地延长网络覆盖时间[3]。Chaudhry利用进化算法研究了传感器节点的布设问题,进而优化网络的数据传输[4]。林祝亮提出一种基于粒子群算法的无线传感器网络布局优化方案[5],该算法主要针对节点在区域中的布局问题展开研究,如果节点位置调整后依然存在较多的感知重叠区域,仍然会产生不必要的能耗;顾晓燕在林祝亮的基础上,通过感知范围调整减少感知盲区和重叠区,首先研究传感器节点的布置,然后调整节点的感知范围,但是未能考虑传感器节点之间的相互通讯[6]。Sengupta利用多目标进化算法研究目标覆盖问题,通过与NSGA-II和CPLEX算法的对比研究,但是其目标覆盖算法未采用相交覆盖集,因此缺乏与其他算法对比的依据[7]。

传感器网络的能耗不仅包括目标覆盖能耗,也包括数据传输的能耗,但是其能耗优先级低于目标覆盖。Fonoage M研究无线传感器网络在数据传输时的拥塞问题,但未考虑拥塞问题对节点能耗的影响[8]。Heinzelman提出的LEACH算法采用层次聚类的方法传输数据,采用随机选举的方法获得簇头,其提出的节点能耗模型被广泛采用,但LEACH算法未考虑目标覆盖问题[9]。Deng J提出基于能耗的多跳-直接的路由算法,通过将传输路径的分割成多条路径降低网络能耗,但是该算法的前提是网络节点分布稠密[10]。Jin W在此基础上研究了网络传输跳数与能耗的关系[11]。侯惠峰提出基于地理信息的无线传感器网络路由算法采用分布式的路由决策[12]。Marta研究了多Sink点下的静态网络的能耗问题,通过多Sink节点克服网络数据传输过程的分区问题[13]。Olariu研究了无线传感器网络能耗的变化与覆盖范围之间的变化规律,探讨了网络传输中的能量漏洞问题,提出如果节点传输范围和Sink节点固定,能量漏洞将无法避免[14]。

国内外较多的学者分别研究了无线传感器网络的目标覆盖以及数据传输过程中的能耗问题,但是并未根据应用场合考虑两者间的关系,在无线传感器网络的主要应用中,目标覆盖是优先考虑的问题,即在保证目标覆盖能耗的前提下考虑网络传输的能耗。彭铎等在LEACH协议的基础上,提出一种非均匀分簇路由协议对簇间负载进行分析,但未考虑簇间重叠问题[15]。冯亚超等对PEADG(Power Efficient Algorithm for Data Gathering)协议进行优化,但是未结合目标覆盖[16]。Akhtar等对网状无线传感器网络的能耗和路由问题进行研究,但其传感器网络节点只考虑均匀分布[17]。

本文针对节点感知距离可调的无线传感器网络,提出一种基于协同进化算法,利用相交集覆盖目标,平衡目标覆盖和数据传输的节点能耗。首先通过相交集覆盖目标,通过贪心算法优化覆盖集的调度,提高节点的电量利用率和目标覆盖质量;然后在保证目标覆盖的前提下,利用协同进化算法优化数据传输路径和网络时延,进一步减少传输节点的能耗,降低网络能耗,延长网络寿命。

1 目标覆盖

目标覆盖,即寻找最优的目标覆盖组合,通过调度不同相交集或不相交集,延长网络的生存周期。在目标覆盖中,由于节点直接覆盖目标,因此可以忽略目标覆盖过程的数据传输时延。

1.1 节点定义

传感器节点通常被部署在一个两维空间,每个传感器需要获取部署后的节点的经纬度。通过节点的经纬度可以计算任意两个传感器节点之间欧几里德距离。假设每个传感器节点使用全方向天线,即一个传感器节点发射的信号可以在任何角度上接收。由于传感器节点的空间距离较近,不会受到地球曲率的影响,不需要转化为曲面距离。

图1 无线传感器网络的目标覆盖

图1中有3个传感器节点和10个需要覆盖的目标。S1号节点在第一时间段覆盖10个目标,如果下一时间段是S2号节点,或者S3号节点覆盖10个目标,则构成一个非相交覆盖集;如果下一时间段是S1号、S3号节点覆盖,则产生相交覆盖集。在S1号节点覆盖10个目标时,S2号、S3号节点处于休眠状态,功耗可以忽略。图2显示3个节点的通信过程,2号节点发送数据包,1号节点和3号节点接受数据包,3号节点接收到数据包之后,继续广播发送数据。1号节点如果在广播范围内没有后续节点,将不转发数据包。

图2 无线传感器网络的节点通信

定义1 节点的能耗模型,节点的能量消耗与传输数据、感知目标的距离有关[8,15],节点传输数据、接收数据和感知目标的能耗分别是Et、Er和Es,k表示传输数据的位数,Eelec和εamp表示传感器节点的数据处理和信号发射系数,Esen表示传感器节点的感知系数,d表示节点间距离。

(1)

定义2 网络传输时延模型,D(s0,si)表示从s0节点传输到si节点的时间延迟。主要包括每个节点在传输数据时的数据排队延时dq,传输延迟dt和广播延迟dp,n(s0,si)表示数据传输起始节点s0到数据处理节点si的转发跳数。

(2)

1.2 最大覆盖集

给定一组含有m个传感器节点S={s1,s2,…,sm}和n个目标集合R={r1,r2,…,rn}的集合。si∈C表示节点属于目标覆盖集合。最大覆盖集算法的目标函数如式(3),求p的最大值,xij=1表示第i节点能够覆盖第j目标。约束条件1表示i节点分配的覆盖时间不能超过1,即每个节点覆盖目标的最大时长为p,约束条件2表示在网络生存期内,任意时刻至少有一个传感器节点能够覆盖所有目标。

(3)

wherexij=0,1(xij=1if∀si∈Sj)

由于在式(3)没有明确的最小时间间隔,我们在式(3)中引入最小时间间隔Δt,即目标覆盖的最短时间单位,同时引入节点能耗si(e),式(3)转变为式(4)。

(4)

wherexij=0,1(xij=1if∀si∈Sj)

tj=Δt,ei=si(Esen·d·Δt)

目标覆盖即保证网络中所有目标都能够被传感器节点覆盖。

①目标覆盖转化为合取范式(CNF),CNF由分句和词构成,其中词是最基本的单位,词与词之间通过析取式连接(OR),分句由词构成,分句与分句之间通过合取式连接(AND)。

②根据目标覆盖的要求,即构建一个{c1}∧…∧{cj},其中j表示目标数量,在任意时刻k,每一个目标都要被覆盖,{c1}由{x11∨x21∨…∨xi1}组成。则该问题被转化为3-SAT问题,因此目标覆盖集是NP-Complete。根据目标覆盖的合取范式(CNF),提出覆盖集算法(算法1),传感器节点集S、目标集R作为输入,输出是覆盖集,首先建立节点和目标之间的距离矩阵,如果距离超过设定的阈值,即节点不能覆盖目标;然后构建每个目标被节点覆盖的链表,最后通过链表构建覆盖集。

算法1 覆盖集算法

输入:传感器集S={s1,s2,…,sm}和目标集R={r1,r2,…,rn}

输出: 相交覆盖集C={c1,c2,…,ck}

获取目标和节点之间的距离矩阵

构建 完全覆盖集合ck,并将ck添加到C中

算法1在目标覆盖集基础上,构建最大集合覆盖,其优化目标是使网络生存期最大,即满足式(4)。最大集合覆盖算法主要有ILP算法(IntegerLinearProgramming)和贪心算法,贪心算法具有收敛速度快的优势,因此在本文中选用贪心算法对最大集合覆盖进行优化,即首先选择能耗最小的{c1}∧…∧{cj}的覆盖集合,通过选择能耗不断递增的覆盖集合完成目标覆盖时长的最优方案。

算法2是基于贪心策略的最大覆盖集合算法,相交覆盖集C作为输入,输出是最大覆盖集序列,首先根据相交覆盖集的能耗选择能耗最小的覆盖集。当最小覆盖集cj节点电量耗尽,C删除cj中的节点。

算法2 最大覆盖集合算法

输入: 相交覆盖集C={c1,c2,…,ck}

输出: 覆盖集序列Seq={ct1,ct2,…,ctp}

While(1)

cj=argmin{c1,c2,…,ck}

If (si<(Esen·d·Δt),∃si∈cj)

ThenC=C-{cj}

Elsecj→Seq

EndWhile

1.3 实例分析

图3显示在100m×100m的区域内,10个Sensor和10个目标被随机部署,每个传感器节点的初始电量为100mAh,Esen=0.000 5,Δt的最小切换时间间隔为分钟。通过最大集合覆盖算法可以获得9个覆盖集,其中包含2个相交覆盖集合7个非相交覆盖集。

图4显示在9个覆盖集中,覆盖集的调用次序是{{s2},{s6},{s4},{s2,s7,s8},{s9},{s1,s2,s7},{s5},{s10},{s7}},当十个传感器节点的电量完全耗尽时,网络的生存周期是258h。

图3 目标覆盖集合(10个Sensors和10个目标)

图4 10个传感器节点覆盖能耗变化图

2 多路径分配

在节点完成目标覆盖之后,网络需要将采集的目标数据发送到数据处理中心。覆盖节点作为数据传输的起点,Sink节点作为数据传输的终点。无线传感器网络需要考虑目标覆盖,网络传输能耗以及传输时延。由于覆盖节点需要不断地调度以延长网络生命周期,因此,覆盖节点与数据中心间的数据链路也要相应地进行优化调度。在数据传输过程中,数据传输受到节点能耗和网络传播时延的影响。协同进化算法是一种多目标优化算法,该算法通过生成多个初始个体和进化机制改善解,相对与ILP、贪心算法而言,协同进化算法可以减少多个目标间的局部竞争,通过协同机制,保证解的全局最优性,提高算法的收敛速度。该算法包括5步骤:①染色体编码和初始化;②染色体选择;③杂交和突变;④可行解评价;⑤种群更新和记忆。

算法3 协同进化算法

输入: Ppop:产生初始种群

PGen:迭代次数

PC:设定解的上界和下界

Step 1: 染色体初始化:产生解。

Step 2: 染色体选择:验证解的可行性。

Step 3: 杂交和变异:随机选择位点,两个染色体进行基因交换,通过随机数在位点进行变异操作。

Step 4: 通过目标函数的评价,获取支配解。

Step 5: 存储记忆库:选择优良个体,保存到记忆库中。

Step 6: 更新:更新记忆库和种群。

Step 7: 判断是否满足迭代条件,如果不满足,进入Step 2,否则退出迭代。

相对于与面向数值解问题的进化算法,协同进化算法在产生染色体之后,需要检查染色体是否具有连通性,如果产生的染色体不具有从目标覆盖节点到数据处理中心的数据链路,即将该染色体作为非可行解,重新生成染色体。同时为了防止进化算法的退化,采用协同机制,只有可行解在t时刻的适应度(覆盖能耗、传输能耗(式(1))和时延(式(2)))超过t-1时刻的适应度时,才替换原有的染色体。

2.1 目标函数

目标覆盖和数据传输的目标函数如式(5)和(6)所示,其中式(5)主要包括目标覆盖的能耗;式(6)包括网络传输能耗和数据传输时延,其中网络传输能耗的优先级高于网络传输时延,因此,将网络时延作为式(6)的一个约束条件。在协同进化算法中,目标覆盖能耗(5)的优先级高于数据传输(6),在染色体中包含目标覆盖和数据传输可行解,目标覆盖解是数据传输解的支配解。

(5)

wherexij=0,1(xij=1if∀si∈Sj)

tj=Δt,ei=si(Esen·d·Δt)

(6)

wherexij=0,1(xij=1if∀si∈Uj)

tj=Δt,ei=si(2Eelec·kd+εampkd2)

minimize(D(s0,sk))ti

2.2 种群初始化

种群初始化首先需要建立网络路径的编码规则,由于路径选择问题中,不同路径的长度会存在差异,我们选择字符串编码。在初始化过程中,种群中染色体的个数为30,每个染色体代表一个解,需要判断解是否是可行解,即染色体是否具有可达性,如果是非可行解,丢弃解,重新初始化,直到获得可行解。

2.3 染色体选择

在获得可行解的种群之后,为了进一步进行解得杂交,需要选择不同的染色体,根据目标函数(5)和(6),我们采用轮盘赌策略选择染色体,对种群中的可行解进行评价。

(7)

染色体的适应度包括解的目标覆盖能耗、路由能耗和网络时延,其中目标覆盖能耗的优先级高于路由能耗,路由能耗优先级高于网络时延,p(i)表示每个染色体被选择的概率,适应度较高的染色体被选中的概率较大,被选中的染色体(Best)个数为偶数,以满足杂交操作的要求。

2.4 杂交和变异

在完成染色体的选择之后,对染色体进行杂交,两个染色体进行配对,然后在随机的位点断裂,相关交换各自的染色体片段。在进化算法中,杂交率一般设定为0.7～0.8范围。在完成染色体的杂交之后,可行解的随机位点发生变异,染色体的变异率为0.01。

2.5 协同进化

为了保证协同进化算法的收敛,防止子个体在下一次筛选过程中的退化,采用协同进化机制,将函数适应度较高的个体保存到记忆库(Memorypool)中。

3 实验与分析

本文首先对目标覆盖问题进行实验,实验平台是MATLAB7.0,IntelCore2 3.0GHz,传感器节点数据为25、35、45、55和65个,传感器节点位置符合二维均匀分布,目标节点为5、10、15个,Esen=5μJ/bit,k=10kbyte,仿真场景为300m×300m。

3.1 目标覆盖

图5显示节点感知范围Srange=40时,传感器节点从25到65时,网络生存期与目标覆盖的关系。随着覆盖目标的增多,覆盖节点的生存期逐渐减少。在传感器节点为55和65时,10个目标和15个目标的网络生存期较为接近,分别相差4小时和5小时,主要是由于能够覆盖目标的传感器数量较为接近。图6显示不同感应距离SR对覆盖节点生存期的影响,当SR=60时,覆盖节点的生存期最长,SR=40时,覆盖节点的生存期最短。网络生存期与感应距离的关系是随着节点感应距离的增大,覆盖节点的生存期逐渐增加。

图5 目标覆盖节点生存期

图6 目标覆盖集合示意图

3.2 路径分配

在路径选择中,针对不同数量目标m=5,m=10和m=15开展分析,节点间的通讯范围UR=60,节点的数据传输系数、天线的功率放大系数、初始电量、数据排队时延、广播时延以及处理时延如表1所示。

表1 无线传感器网络的传输系数

图7显示了25个传感器节点、5个目标覆盖和数据传输的过程,在第一时间段,目标覆盖算法选择节点(3,5)构成覆盖集,覆盖5个目标,然后通过数据链路将目标状态传输到Sink节点,随着(3,5)节点电量的不断下降,覆盖节点由(3,5)节点转变为(1,2,6)节点,目标覆盖算法不断进行覆盖集的调度,延长目标覆盖时间。

图7 路径分配(5个目标)

在完成目标覆盖之后,需要将目标的状态信息传输到Sink节点,通过协同进化算法选择传输能耗、传输时延较小的路径,传输能耗目标相对传输时延是支配集,即传输能耗的优先级高于传输时延。协同进化算法的杂交率为0.75,变异率为0.01,为了防止解的退化,采用记忆机制,保留优良个体。图8显示在切换目标覆盖节点之后,利用协同进化算法计算的新的目标传输路径。

图8 路径分配(5个目标)

图9 路径选择的收敛趋势(65个节点)

针对不同数量(5、10、15)目标,选择不同节点数量(25、35、45、55、65)的传感器网络进行网络生存期、网络实验的测试。图9显示了65个节点、15个目标条件下,协同进化算法的收敛情况,在2 500次迭代之后,数据的传输路径逐渐收敛到最优路径。

图10是不同节点数量的无线传感器网络的生存周期变化趋势图。网络的能耗随着节点数量的增加而延长,当目标数量为5时,网络的生存周期要高于目标数量为10和15时的生存期。图11显示了网络数据传输时延的变化趋势,节点数量从25增加到65时,网络的传输时延逐渐增加,主要是由于节点数量增长会造成传输路径的长度增加,进而造成了时延。同时为了验证本文算法对网络生存期和能耗的优化效果,将贪心-协同进化算法与ILP-协同进化算法进行对比,其中目标数量m=10,通讯范围UR=60,图12显示两种算法对网络生存期的影响趋势,采用贪心-协同进化算法优化后网络生存期要长于ILP-协同进化算法。

图10 网络生存期(25节点到65个节点)

图11 网络时延变化趋势

图12 两种算法的网络生存期对比

4 结论

本文提出了一个基于协同进化策略的无线传感器网络目标覆盖和路由选择算法。网络的生存期和网络传输延时实验结果表明,通过设定不同的感知范围和通信距离,可以延长网络的生存期,究其原因是感知范围和通信距离的扩大可以增加目标覆盖和数据传输节点的数量,进而增大网络的生存期。在数据传输中实验中,本文仅考虑固定Sink节点和数据的情况,在下一步工作中,通过引入时变数据和可变Sink节点,分析网络能耗的变化和数据传输时延。

[1] Akyildiz I F,Su W,Sankarasubramaniam Y,et al. Wireless Sensor Networks:A Survey[J]. Compututer Network,2002,38(4):393-422.

[2] Cardei M,Wu J. Energy-Efficient Coverage Problems in Wireless Ad-hoc Sensor Networks[J]. Computer Communications,2006,29(4):413-420.

[3] Zorbas D,Glynos D,Kotzanikolaou P,et al. Solving Coverage Problems in Wireless Sensor Networks Using Cover Sets[J]. Ad Hoc Networks,2010,8(4):400-415.

[4] Chaudhry S B,Hung V C,Guha R K,et al. Pareto-Based Evolutionary Computational Approach for Wireless Sensor Placement[J]. Engineering Applications of Artificial Intelligence,2011,24(3):409-425.

[5] 林祝亮,冯远静,俞立. 无线传感网络覆盖的粒子进化优化策略研究[J]. 传感技术学报,2009,22(6):873-877.

[6] 顾晓燕,孙力娟,郭剑. 一种无线传感器网络覆盖能耗平衡优化策略[J]. 传感技术学报,2010,23(11):1627-1632.

[7] Sengupta S,Das S,Nasir M,et al. An Evolutionary Multiobjective Sleep-Scheduling Scheme for Differentiated Coverage in Wireless Sensor Networks[J]. Systems,Man,and Cybernetics,Part C:Applications and Reviews,IEEE Transactions on,2012,42(6):1093-1102.

[8] Fonoage M,Cardei M,Ambrose A. A QoS Based Routing Protocol for Wireless Sensor Networks[C]//Performance Computing and Communications Conference(IPCCC),2010 IEEE 29th International. IEEE,2010:122-129.

[9] Heinzelman W R,Chandrakasan A,Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//System Sciences,Proceedings of the 33rd Annual Hawaii International Conference on.IEEE,2000,2:10-17.

[10] Deng J. Multi-hop/Direct Forwarding(MDF)for Static Wireless Sensor Networks[J]. ACM Trans Sens Netw,2009,5(4):1-25.

[11] Jin W,Jinsung C,Sungyoung L,et al. Hop-Based Energy Aware Routing Algorithm for Wireless Sensor Networks[J]. IEICE Transactions on Communications,2010,93(2):305-316.

[12] 侯惠峰,刘湘雯,于宏毅. 一种基于地理位置信息的无线传感器网最小能耗路由算法[J]. 电子与信息学报,2007(1):177-181.

[13] Marta M,Cardei M. Improved Sensor Network Lifetime with Multiple Mobile Sinks[J]. Pervasive and Mobile Computing,2009,5(5):542-555.

[14] Olariu S,Stojmenovic I. Design Guidelines for Maximizing Lifetime and Avoiding Energy Holes in Sensor Networks with Uniform Distribution and Uniform Reporting[C]//INFOCOM,2006:1-12.

[15] 彭铎,黎锁平,杨喜娟. 一种能量高效的无线传感器网络非均匀分簇路由协议[J]. 传感技术学报,2014,27(12):1687-1691.

[16] 冯亚超,贺康,杨红丽. 一种无线传感器网络数据收集协议的研究与优化[J]. 传感技术学报,2014,27(3):355-360.

[17] Akhtar A M,Nakhai M R,Aghvami A H. Power Aware Cooperative Routing in Wireless Mesh Networks[J]. Communications Letters,IEEE,2012,16(5):670-673.

陆星家(1979-),男,工学博士,宁波工程学院理学院讲师,美国俄亥俄州立大学(OSU)访问学者,主要研究方向为无线传感器网络,数据挖掘等,shlxj800@gmail.com;

陈志荣(1981-),女,理学博士,宁波工程学院理学院副教授,澳大利亚科廷大学访问学者,主要研究方向为智能系统,智能决策与分析,地理信息系统等,chenzr29@gmail.com。

Research of Energy Efficient Target Coverage and RoutingAssignment in Wireless Sensor Networks*

LUXingjia*,CHENZhirong

(School of Science,NingBo University of Technology,Ningbo Zhejiang 315211,China)

Due to the shortage of the existing target coverage algorithms in Wireless Sensor Networks(WSNs),it doesn’t consider the relationship between routing assignment,energy efficiency and target coverage. However,the robust algorithm doesn’t exist that considers the energy efficient routing assignment of WSNs dominated by targets coverage. We propose an energy efficient algorithm for target coverage and routing assignment that satisfy all the targets are covered completely. First,the maximum sets cover was constructed based on greedy heuristic strategy. Then,the proposed algorithm obtained the optimal path based on different cover sets and performed the co-evolution through operators such as fitness evaluation,wheel roulette,crossover,mutation,and memory mechanism. The lifetime and time delay of WSNs are also evaluated. The results showed that our algorithm extended the lifetime and decrease the time delay of WSNs.

wireless sensor networks;targets cover;routing assignment;energy efficiency;maximum set cover algorithm;Co-evolutionary mechanism

项目来源:国家自然科学基金项目(40901241);浙江省哲学社会科学规划基金项目(15NDJC077YB);宁波市软科学项目(2014A10013);浙江省公益技术应用研究计划项目(2015C31154)

C:6150P

10.3969/j.issn.1004-1699.2015.06.021

TP393.1

A

1004-1699(2015)06-0900-07

2015-02-07 修改日期:2015-05-12