基于进化算法的无线传感器网络任播路由算法*

顾云丽,徐 昕,张嫣娟

(1.南京信息工程大学江苏省网络监控中心,南京 210044;2.南京信息工程大学计算机与软件学院,南京 210044)

无线传感器网络WSN(Wireless Sensor Networks)常用于军事、海洋、气象环境、森林火警监测,其网络范围往往大于一般无线网络。由于网络规模较大,为改善性能(如网络生存期和流量分布等),需在WSN中部署多个基站,并采用多源多基站任播模式MMAP(Multi-source Multi-Sink Anycast Pattern)。即从传感器节点产生的监测数据分组可以传输给任一基站。

任播(anycast)是IPv6中定义的一种新型通信服务,其服务是将数据分组传送到具有任播地址标识的任意一个或多个接口处。传统任播路由协议是将数据分组发送至最优基站。而在WSN中,有学者采用的是基于路由权重随机选择策略[1]WRS(Weighted Random Selection)的任播路由技术,即监控节点根据至各基站的任播路径的路由权重,将监控数据分组分散传输到各个基站处。该策略可以缓解单条路径承载过多传输任务,导致部分节点过早耗尽能量的问题。

任播路由领域相对比较新颖,关于WSN任播路由协议的重要研究成果目前还不是太多,主要如下:Lenders[2]等人根据势场理论提出一种基于密度的无线网络任播路由协议;Flury[3]等学者证明在WSN中指定任播组和源节点所生成的信息树中寻找最小传输总能耗是一个NP完全问题,作者在文中给出一个分布式的近似算法来解决该难题;Ashraf[4]提出Any-MAC协议,通过改善路由级冗余,减少传输延迟;Kim等[5]学者将睡眠-唤醒机制引入MAC任播路由;Hadi等[6]学者研究编码转发策略和固定比率合并机制,设计了一个最小能量路由协议的联合优化算法;Kostin等[7]学者研究移动传感器和移动多Sink路由方案,方案基于扩展环搜索、传感器节点维护反应模式和路由状态信息等算法思想;Gao[8]等学者为解决森林环境监测数据分组的传输延迟问题,提出一种可充电WSN的任播路由协议,其算法主要思想是通过禁忌搜索算法建立至每一个基站的端到端时延最小的任播路径;Yerra[9]搭建三维马尔可夫模型,从而能够更准确地观察中继节点的传输效率、传输时延等关键性能指标;刘文博[10]将任播路由应用于水下传感网络。也有学者将k-任播应用到WSN中以达到均衡能耗提高网络生存期的目的。Wang[11]提出一种分布式地理WSN的k-任播路由协议(GKAR);Gao[12]借用WSN的广播特点以节省传输能耗(即k条路径尽量共用相同链路的算法思想)。

以往学者往往将网络生存期作为路由选择的重要判据,但却较少有学者将路由健壮性也作为路由选择的参考因素之一。在WSN中,无线链路经常临时性失效,监测数据分组有可能不能正常到达目的地,从而导致能耗(重传能耗)和端对端时延增加,这使得以往有些学者所提出的路由算法的实际性能可能达不到其所述性能指标。因此,本文将路由健壮性及网络生存期两方面因素都作为路由判据,并实验分析该算法的性能。

1 网络模型及问题描述

本文,WSN抽象视为连通图G(V,E)。其中,V为传感器节点集合,E为节点间通信链路集合。本文标记:A为任播地址;G(A)为共享A的任播通信组成员集合(即基站集合),G(A)⊆V;N为集合V的节点数目;M为集合G(A)组员数目,T为集合E的链路数目。

WSN往往用来监控其覆盖范围内若干指定目标,该目标附近节点往往需定期汇报监测数据至任一基站。这些发送节点集合标记为S,L为S中节点数目。

由于WSN节点能量受限且往往难于更换电池,一旦有节点耗尽能量,可能会导致网络分割,即某些区域无节点负责监测和转发分组,从而被认定为网络失效。本文定义网络生存期为第1个节点耗尽能量。因此,我们设计的路由算法不仅要节能,还要保证各节点能耗要均衡,从而最大化网络生存期。所以,发送节点将监测数据分组不能仅发送至最优基站,还需根据各个基站的路由权重,将数据随机发送给相应基站(WRS策略[1])。设发送节点s∈S至M个基站(G(A))都有一条任播路径,即节点s共有M条任播路径,表示如下:

Ps={Ps1,Ps2,…,PsM}

(1)

Ps中的M条任播路径路由权重Ws表示为{ws1,ws2,…,wsM}。S中各发送节点的任播路径集合P表示如下:

P={P1,P2,…,PL}

(2)

P的路由权重集合W表示如下:

W={W1,W2,…,WN}

(3)

设节点s∈S为某一源节点,单位时间需汇报至基站的次数是ns;每次汇报至基站的数据分组大小为us。由于采用WRS策略,即s根据路由权重从M条至各基站的任播路径中随机选择一条作为传输路径。设任播路径Psj∈P,Psj是指源节点s至基站j的路径,路径权重设为wsj,则路径Psj单位时间将为源节点s承担wsjnsus大小的数据传输任务。设节点传输速率为τ,wsjnsus大小的数据所需传输时间tv为wsjnsus/τ(不考虑分组在节点内排队等待时间等)。

节点的状态可分为正在发送分组,或正在接收分组(包括串听),或空闲等待状态。设节点v∈Psj,则节点v需为任播路径Psj发送数据量为Nsuswsj。节点v还可能属于同一源节点其他任播路径,或者其他发送节点为源节点的任播路径,因此节点v单位时间发送数据量Dv计算如下:

(4)

因此,节点v单位时间内处于发送状态的时间tvs为:

tvs=Dv/τ

(5)

由此可得,节点v单位时间能耗Ev为:

Ev=tvsEdelivery+(1-tvs)Eidle

(6)

式中:Edelivery为节点处于传输状态时单位时间能耗;Eidle为节点处于空闲等待或接收状态时单位时间能耗。接收能耗与空闲等待能耗往往相差不大,本文简化为视为相同。

学者在设计WSN路由算法时往往以网络生存期最大化为优化目标。如图1中,S1和S2为发送节点,各需汇报u大小数据分组至基站;A1、A2和A3为基站。S1的任播路径集合P1=(P11P12)。P11=S1-n1-A1;P12=S1-n2-n3-A2。S2的任播路径集合P2=(P23P21)。P23=S2-n4-n5-A3;P21=S2-n1-A1。由图1可以看出,S1的P12与S2的P23是无交叉路径,而P11和P21是最短路径。但为最大化网络生存期,发送节点不能只采用一条任播路径(最短路径或无交叉路径)。而是根据WRS策略,将数据流分散到各条任播路径上。图1中,为最大化网络生存期,显然应设置P1路由权重W1={w11w12}={0.666 0.333};而P2的W2=(w23w21)=(0.666 0.333)。即S1将0.666u分组通过路径P12汇报至A2,将0.333u分组通过路径P11汇报至A1,S2也依此处理。

图1 网络示意图

但WSN还会因环境等因素常常出现无线链路临时性失效现象。失效会导致节点有额外的重传能耗,路径有额外的重传时延。因此,这些学者所提出的路由算法的实际传输时延和传输能耗可能达不到其设计性能(后文将以图1数据说明)。

设fi为链路ei出现故障的概率,本文设定链路的故障彼此之间是完全独立的事件。本文还设定,中间节点不保存其转发的数据分组,即若传输任务失败需路径源节点重新发送丢失的分组。

设路径Psj∈P,Psj单位时间内路径出现故障的概率rsj计算如下:

(7)

(8)

(9)

由此,我们可得,节点v的单位时间实际能耗如下:

(10)

节点v寿命Lv计算如下:

(11)

式中:Einit是节点的初始能量。

由于链路e∈E,可能在P中多条任播路径中出现,即,链路e的失效会造成P中多条任播路径数据分组的丢失,计算如下:

(12)

经过简化,Fe为:

(13)

可得,使用链路e∈E,导致任播路径数据分组丢失率如下:

(14)

我们设计的任播路由算法,其算法设计目标之一是最大化网络生存期。即

(15)

式中:式中变量是P和W,即任播路径集合及其路由权重向量。

(16)

该优化问题记为

(17)

分组丢失会导致节点传输能耗增加,从而影响网络生存期。如图1,若忽略数据分组丢失问题,如前文所述,为最大化网络生存期,P1路由权重W1={w11w12}={0.666 0.333};而P2的W2={w23w21}={0.666 0.333}。 但实际由于重传能耗问题的引入(设各链路故障概率为0.1),根据式(15)可得:W1=W2={0.643 0.357}。分析如下:由式(12),可知S1-A2路径的数据丢失率为0.271,0.643u的数据分组在S1-A2路径实际上需要传递0.882u;同理,可得S2-A3路径,S1加上S2至A1路径的实际数据流为0.882u,即各任播路径上各节点能耗均衡(相等),网络生存期最大。由此可知,忽略对路由健壮性问题的讨论,导致有些学者所提出的路由算法的网络生存期性能可能达不到其所述性能指标。

上文只是描述链路失效造成的重传能耗后果,除此以外,还会造成传递时延额外增加、节点计算和路由资源浪费等。因此,我们所设计的任播路由算法也要尽可能减少链路的数据分组丢失概率。该优化问题描述如下:

(18)

为方便讨论,式(17)记为:

(19)

3 多目标进化算法优化

由上文可知,我们的优化目标不仅是网络生存期,还要包括路由健壮性。即我们优化的目标如下:

(20)

(21)

显然,这两个目标往往存在冲突,常常无法同时取得最优值。设图1中链路S1-n1和S2-n1的故障率为0.1,而其余链路故障率为0,显然S1(S2)将其所有监测数分组传送至A2(A3),此时链路故障率最低。但为了最大化网络生存期,S1(S2)还需将部分数据分组传送至A1。该多目标优化问题是一个NP完全问题[5],即该问题无法给出一个有限多项式解。对于这种多目标路由优化问题,以往学者有采用多目标进化算法解决类似问题[13-14],因此本文采用多目标进化算法解决该问题。

如前文所述,单个节点的能耗计算和单条链路导致任播路径分组丢失率的计算的算法复杂度分别为O(N)和O(N3/2),对节点的计算能力要求不是太高。但是式(20)和式(21)的多目标优化问题是NP完全问题,为了节省节点能耗、降低对节点计算能力的要求,本文将优化计算问题迁移到基站。即网络初始化时,由基站完成优化计算并返回结果给各节点。当有拓扑结构等信息发生改变时,由基站重新计算并返回给各节点。基于上述策略,可以缓解节点能耗等问题。

解决多目标优化问题常见的方法有加权和方法和Pareto解方法等。加权和方法需要人为给各目标设定权值,难于掌握;目前比较流行的Pareto 最优概念的进化算法,得出的结果往往是一组(而不是一个)均匀分布的在Pareto前沿的Pareto占优解。

针对这一点,我们设网络生存期单目标优化最优值:

(22)

又设路由健壮性单目标优化最优值:

(23)

我们可以将原多目标优化问题改为如下单目标问题:

(24)

因此,可将原多目标问题转成3个单目标问题,而且无需人为给定权值。

进化算法具体流程如下:

4 实验与仿真

网络仿真设置在一个矩形区域内;N个节点随机均匀分布,每个节点至少有3条链路;基站数目M=3;发送能耗是接收(空闲等待)能耗的3倍;各条链路的故障率都设为0.01;发送节点数目T为网络节点数(N)的50%,各发送节点单位时间内需发送数据分组大小相同,次数相同(us=256b,Ns=1)。

图2 迭代次数与优化值

由图2可以看出,当设置迭代次数为25时,EA-NL以及AR-EA的种群还没有完全收敛,适应度值仍然有较大的波动。当迭代次数为95时,EA-NL与AR-EA已经收敛,即已计算出最优路径和权值,说明AR-EA算法有效。从图2中可以看出,AR-EA在迭代次数为80时基本保持平稳,种群平均适应值为0.873;而对于EA-NL,由于其实验优化目标仅仅是网络生存期,而参与比较的却是网络生存期与数据分组丢失率的综合值,因此其优化结果并不理想。而且,由后文实验可知,网络生存期与路由健壮性两者性能优化往往冲突,随着迭代次数增加,EA-NL的性能反而有一些降低。

图3(a) 数据分组丢失数与网络生存期(N=30)

设网络节点数N=30,以传统任播路由协议(即发送节点将其监测的全部数据汇报至最优基站,本文标记为Anycast)为对照算法,分析AR-EA的路由健壮性和网络生存期,结果如图3(a)所示。

由图3(a)可知,AR-EA在网络生存期和路由健壮性两个性能上都明显优于Anycast。这是由于AR-EA在路由策略安排上,采用了WRS策略;而Anycast只采用最优路径这一个单一路径,其选择范围只是WRS策略的一个子集,而AR-EA的路由权重设置可以更好地在网络生存期和网络健壮性上做出权衡。在图3(a)中,还可以看出,网络生存期和路由健壮性这两个性能在较大区间内是优化冲突的。

再观察AR-EA算法的可扩展性。在上一个实验基础上,设置不同网络规模(区域不变,基站数M不变,节点数N=30,90,150),观察各算法路由健壮性和网络生存期,结果如图3(a)、图3(b)、图3(c)所示。

图3(b) 数据分组丢失数与网络生存期(N=90)

图3(c) 数据分组丢失数与网络生存期(N=150)

由图3(a)、图3(b)、图3(c),可以看出,随着网络规模增大,在基站数量不变的情况下,发送节点数增加,任播路径平均长度增加,从而导致Anycast与AR-EA的数据分组丢失率相应增加、网络寿命相应减少。但AR-EA由于采用了WRS策略,网络生存期和路由健壮性这两个性能仍然优于Anycast,而且随着网络规模的增大,这种优势将更加明显(可供选择的任播路径数的增加)。

5 结语

以往学者在研究WSN任播路由算法时,往往较多关注节点能耗问题,对网络路由健壮性问题关注较少。而WSN的无线链路往往比较脆弱,从而导致重传能耗、传输延迟等问题。因此,本文提出一种基于进化算法的WSN任播路由算法。该算法的优化目标是网络生存期和路由健壮性两个目标,并通过多目标进化算法寻找到两者的最佳适应值。实验数据证明,相比较基于单目标优化(网络生存期)的任播路由算法,所提算法的网络生存期及路由健壮性两个性能的综合优化值较优;相比较传统单路径任播路由算法,所提算法的网络生存期、路由健壮性和可扩展性较优。

[1] Xuan D,Jia W,Zhao W,et al. A Routing Protocol for Anycast Messages[J]. IEEE Transactions on Parallel and Distributed Systems,2000,11(6):571-588.

[2] Lenders V,May M,Plattner B. Density-Based Anycast:A Robust Routing Strategy for Wireless Ad Hoc Networks[J]. IEEE/ACM Transactions on Networking,2008,16(4):852-863.

[3] Flury R,Wattenhofer R. Anycast and Multicast Routing for Mesh and Sensor Networks[C]//Proc of INFOCOM’07. 2007:946-954.

[4] Ashraf F,Vaidya N H,Kravets R H. Any-MAC:Extending any Asynchronous MAC with Anycast to Improve Delay in WSN[C]//Proc of SECON 2011. 2011:19-27.

[5] Kim J,Lin X,Shroff N B. Optimal Anycast Technique for Delay-Sensitive Energy-Constrained Asynchronous Sensor Networks[J]. IEEE/ACM Transactions on Networking,2011,19(2):484-497.

[6] Hadi F,Ahmed S,Minhas A A. Wireless-Powered Cooperative Energy Aware Anycast Routing in Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2016,12(11).

[7] Kostin A E,Fanaeian Y,Al-Wattar H. Anycast Tree-Based Routing in Mobile Wireless Sensor Networks with Multiple Sinks[J]. Wireless Networks,2016,22(2):579-598.

[8] Gao D,Liu Y,Zhang F. Anycast Routing Protocol for Forest Monitoring in Rechargeable Wireless Sensor Networks[J]. International Journal of Distributed Sensor Networks,2013,6:1-14.

[9] Yerra R V P,Kiran M P R S,Pachamuthu R. Reliability and Delay Analysis of Slotted Anycast Multi-Hop Wireless Networks Targeting Dense Traffic IoT Applications[J]. IEEE Communications Letters,2015,19(5):727-730.

[10] 刘文博,王涛. 基于水压的水下传感网络的选播路由协议[J]. 传感器学报,2016,29(12):1899-1904.

[11] Wang X,Wang J,Lu K,et al. GKAR:A Novel Geographick-Anycast Routing for Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2013,24(5):916-925.

[12] Gao D,Lin H,Liu X. Routing Protocol fork-Anycast Communication in Rechargeable Wireless Sensor Networks[J]. Computer Standards and Interfaces,2016,43:12-20.

[13] Su S,Yu H,Wu Z. An Efficient Multi-Objective Evolutionary Algorithm for Energy-Aware QoS Routing in Wireless Sensor Network[J]. International Journal of Sensor Networks,2013,13(4):208-218.

[14] Murugeswari R,Radhakrishnan S,Devaraj D. A Multi-Objective Evolutionary Algorithm Based QoS Routing in Wireless Mesh Networks[J]. Applied Soft Computing,2016,40:517-525.