面向环境监测的WSN中基于定向传输的高能效路由算法*

马忠彧,马宏锋,彭琳茹,李祥林

(1.兰州工业学院电子信息工程学院,兰州 730050;2.甘肃省资源环境科学数据工程技术研究中心,兰州 730000;3.甘肃省资源环境信息化工程实验室,兰州 730050)

将带有大量中继节点的WSN用于环境监测中的主要目的之一是评估异常活动影响并预警。能耗是限制WSN在环境监测中应用和扩展的关键因素,而路由协议设计成为解决Qos(即能耗、网络生命周期、网络可扩展性和包开销等)相关问题的有力突破点[1]。节点的随机部署、网络的动态拓扑和面向应用的异类需求(可扩性、可靠性、能效、资源管理等)使我们在设计面向环境监测的WSN路由协议的过程中具有相当挑战性。

现有文献中,根据协议的功能和参数,面向环境监测的WSN路由协议可分为平面路由分层路由和支持地理位置的路由[2]。平面路由进一步分为主动路由(表驱动)、被动路由(按需驱动)和混合路由。主动路由是节点根据已有的路由表向汇聚(Sink)节点传输数据,常见该类协议主要有目标序列距离向量(DSDV)协议、优化链路状态路由(OLSR)协议、低能耗自适应分簇路由协议(LEACH)、功率有效收集传感信息系统协议(PEGASIS);被动路由协议中,节点在数据传输需求时才建立路由信息,常见的被动路由协议有动态源路由协议(DSR)、自适应按需距离路由协议(AODV)、按需多播路由协议(ODMRP)、基于分簇的路由协议(CBRP)[3]。

表1列出了现有文献中改进能效的路由协议。

为了解决表1中的问题并满足资源环境监测中的可靠性、能效、最短路由、时延、通信开销和资源管理等需求,本文提出了一种基于定向传输的能量感知路由协议DTERP(Directional Transmission-based Energy aware Routing Protocol)路由协议以同时优化多项目标,该协议智能运用PEGASIS算法和动态源路由DSR算法并通过创建发送节点的信任列表来保证网络的可靠性,同时利用方向传输的概念来最低程度的减小传输节点间距离。JPDORP也引入了高速缓存,当有节点突发传输且它又不在之前建立的置信列表中,必有其他节点接收到该节点数据包,这会破坏现有路由。为了解决该问题,本文提出的协议在每轮中首先创建一个基于节点分配参数的置信表。此外,JPDORP协议综合运用遗传算法(GA)和细菌觅食优化(BFO)算法来确定能效最优的路径。我们将本文提出的JPDORP协议和PEGASIS、DSR、LEACH和ERP协议在误比特率、时延、能耗和吞吐量方面进行性能对比。结果表明本文算法不仅在能效方面的性能优势突出,而且在误比特率和端到端时延方面也有一定增益。

1 系统模型

假定网络是在二维区域中随机部署有限个同构传感器节点,且其初始能量为ei(ei>0)。任意量节点可通信的条件是二者的剩余能量均大于或等于能量阈值。我们使用网络仿真和理论分析中经常用到的文献[10]中的路损模型。我们用文献[3]中的公式计算距离为dist的节点之间的接收功率:

Pr(dist)=Pi×(disti/dist)α

(1)

式中:Pi表示离发送节点距离为dist处的接收信号功率,α(2≤α≤6)表示路损指数。此外,我们在系统中做出以下约束:①节点的发送功率由自身可以按需调节,且接收信号强度(RSS)计算容易;②数据包的发送和接收都是基于定向天线的;③节点与其地理位置;④节点知道自身邻居节点;⑤每个节点都能知道各自的北向参考方向。

2 提出的算法

通过算法1,我们创建一个节点个数为N(500)的随机部署网络,网络区域范围为1 000 m2,该算法的第4步中我们计算所有节点与其邻居节点之间的距离d,并与距离阈值th进行比较,这样当相邻节点之间的距离d小于阈值th时,节点之间才能通过网络链接,通过算法1我们可以建立一个连通网络。算法1描述了区域为1 000×1 000网络、覆盖集为1的网络中的节点部署方法。

算法1 网络拓扑创建算法步骤1 设置网络长度和宽度：Length=1000，Width=1000；设置网络节点数：N=Total＿Nodes；网络参数初始化：Counter=1；Cov＿set=[]；步骤2 forn=1，n<=N，n++； xlocation(n)=1000∗Random；ylocation(n)=1000∗Random； Node．name(n)=Counter；Counter=Counter+1；Endfor步骤3 fori=1，i<=N，i++； Cov＿counter=2； Forj=1，j<=N，j++； IfI！=j d=(xi-xj)2+(yi-yj)2； Th=network．width∗20100； If(d<=Th) Cov＿set(i，1)=i； Cov＿set(i，Cov＿counter)=j；Cov＿counter=Cov＿counter+1； Endif Endif EndforEndfor

算法2 路径搜索算法：fori=1，i<=Network．simulation．rounds，i++ Source=Initialize．Source； Source．Id=Node．name(source)； Path=[]； Pathelement=2； Path[1]=Source Source．Packet．count=1000； Destination．Id=Node．name(Destination)； Current＿cov＿set＿source=Cov＿set(source．Id，：) dest＿found=0；possible＿nodes=[]； While(dest＿found！=1) Foreachallnincurrent＿cov＿set If(x(alln)>xlocation(Source．Id)&&(x(alln)-xloc(Destination．Id)<0 Possible＿nodes[possiblenoedcount]=alln； Possiblenodecount+=1； Endif Endfor Selection=possiblenodecount∗Random； Possible＿Nodes=[]；Path(Pathelement)=selected＿Node；Endfor

算法2负责建立用于数据传输的路由算法(路径搜索),在节点的最大覆盖集中选择最优路径。如果源节点和目的节点在同一个网络覆盖集中,则进行数据传输的,否则进行路径搜索。

JPDORP协议是基于PEGASIS与DSR联合优化的路由协议JPDORP(Joint PEGASIS-DSR Optimized Routing Protocol),更好的融合运用主动路由和被动路由。当节点主动发送数据却不再高速缓存中,其他的节点势必会收到该节点发送的数据包,这有损于在用路由。解决该问题的一个方法是节点在接收到数据包时检查任意节点,这可能会有一些时延。因此,JPDORP算法在每轮首次时创建一个基于节点参数分配的置信列表。每轮都对置信列表进行更新,这样经过若干轮后,对于置信列表中的节点不再检查,以避免不必要的时延。

图1给出了本文算法的流程图,当源节点想向目的节点发送数据时,源节点先计算自己距离所有邻居节点的距离,并将数据发送给距离小于等于距离阈值且方向与到目的节点方向一致的邻居节点。随后,仅在第1轮仿真中将与目的节点方向上一致的所有节点添加到源节点信任列表中。每当需要新的数据传输时,且仅向在置信列表中找到的那些节点进行数据传输。由于节点是在初始阶段创建置信列表,将置信列表存储在高速缓存中后便于后续数据传输。路由缓存的置信列表创建方法如算法3所示。

图1 协议流程图

算法3 路由缓存置信列表创建算法(JPDORP)步骤1 PC=1；步骤2 Fori=1，i<=N，i++ ΔH=∑j=1EA+ET+ERN；(2) If(EAi+ETi+ERi>ΔH) RoutingdistortionpossibleNodes(PC)=i；PC=PC+1； EndifEndfor步骤4 Initializetransfer； Packet．count=1000；步骤5 D=find(Packet．sender．Id)==RoutingdistortionpossibleNodes)步骤6 if(isempty(d)) AcceptPacket；Else RejectPacket；Endif；

我们认为每个节点在信任列表中出现一次。为寻找用于建立置信列表的最优置信值,算法4提出了基于GA和BFO融合的优化算法。GA算法基于ER&ET优化节点一致性。每个节点必须通过算法4步骤1中给出的适应度函数。

算法4 基于GA和BFO融合的置信值优化算法：步骤1 f=(1-ETi+ERiN∗rand)(3)步骤2 Fori=1：N Ifround(f)==1 NodeisacceptedforBFOfitnesscheck GAlist(Gaa)=I；Gaa=Gaa+1； Trust＿value=0； Endif Endfor步骤4 tr=0步骤5 ForeachKinGAlist g=1-ETk-∑Nl=1ETNæèççöø÷÷(4) Ifg>0， New＿trust=Rand tr=tr+1； Node＿trust(tr)=Node＿trust(tr)+New＿trust．EndForeach

3 仿真分析与性能评估

本节中将从误比特率、吞吐量和时延等方面对本文协议和传统协议(即PRP协议、DSR协议、LEACH协议、OD-PRRP协议)进行对比。节点业务以512 byte/s的恒定速率产生。数据包大小为100,每个网络场景的仿真时间为200 s,也是将数据包传输到目的节点的传输时间。网络节点数为500个,图2给出了本文的仿真平台模型,模型综合运用了PEGASIS(主要是PEGASIS方向传输特性)和DSR协议(主要是DSR协议的缓存特性),同时还融合运用了GA和BFO优化技术,仿真中用到的参数如表2所示。

图2 仿真模型

名称缩写取值仿真区域长度Length1000仿真区域宽度Width1000数据包发送能耗ET数据包接搜能耗ER节点聚集能量EA网络类型GPS节点个数Nnum100～500网络分配NA随机网络覆盖NCO(x2-x1)2+(y2-y1)2网络缓存NCADSR缓存网络路由NR基于PEGASIS

3.1 传感器节点数量变化场景中的性能参数对比

(1)端到端时延

时延表示数据包从源节点到目的节点所经历的时间,包括发送时延、排队时延、传播时延和处理时延。随着网络中节点数量的不断增加,网络时延也不断增加。图3给出了不同网络节点数量下各算法的端到端时延,从图中可以看出随着网络节点的不断增加,只有OD-PRRP协议的端到端时延呈稳步增加趋势。而且,JPDORP协议在时延方面的性能要优于LEACH、DSR、PEGASIS和OD-PRRP协议。

图3 端到端时延对比图

(2)误比特率

图4表明DSR相对其他对比协议在误比特率方面大幅降低。而本文提出的JPDORP算法在误比特率方面要优于PRP协议、OD-PRRP协议和LEACH协议。这是因为本文JPDORP算法通过建立传输节点置信列表,降低的数据传输碰撞机会和误码率。

图4 误比特率对比图

(3)能量消耗

发送数据的能耗公式为:

ETx(k,d)=Eelec·k+Camp·k·d2,d>1

接收数据的能量消耗为:

ERx(k)=Eelec·k

k表示发送的数据量,d表示两个节点之间的距离,Eelec表示传输单位比特内的所消耗的能量。数据传输的总能耗为:Etotal=∑ERx+∑ETx。

图5 能耗对比图

从图5可以看出:PRP和本文提出的JPDORP协议在节能方面的性能要优于DSR协议、LEACH协议和OD-PRRP协议,且即使网络节点数量增加,本文提出的JPDORP算法的能耗几乎是稳定的。因此,在网络能耗方面,JPDORP协议性能最优。

(4)吞吐量

如图6所示,LEACH协议要优于其他协议,DSR协议也要优于PRP、JPDORP、OD-PRRP协议,PRP,PORP和OD-PRRP在吞吐量方面的性能相似。

图6 吞吐量对比图

3.2 算法综合性能评估

假定有n个算法,A1、A2…An,设选择评估这些算法的参数个数为m个,我们可以使用以下矩阵:

为比较这种算法,首先必须对矩阵Q进行标准化[11-12]。之所以要进行标准化是因为:①一致评价所有参数;②统一索引表示算法参数;③设置各参数最大正常值;④使评分与单位无关;

将上述求解步骤应用于Q,我们得到的矩阵Q′如下:

通过上述计算,可得各对比路由算法(DSR、LEACH、PEGASIS、OD-PRRP、JPDORP)的评分情况为:DSR得分=13.72;LEACH得分=4.86;PEGASIS得分=6.83;OD-PRRP得分=8.89;JPDORP得分=16.91。

4 小结

本文提出了一种基于DSR和PEGASIS的混合优化路由协议,采用了基于主动路由协议和被动路由协议的缓存和定向传输技术,仿真结果表明在能效一致的情况下本文所提出的协议JPDORP在端到端传输时延和误比特率方面有显著优势。同时本文也对现有的PEGASIS协议、LEACH协议、DSR协议、OD-PRRP协议和本文提出的JPDORP协议进行对比分析,结果表明本文算法在误比特率、吞吐量、能耗和端到端时延方面都有显著优势。该方法可用于高可靠、高能效、长网络生命周期、低端到端时延的安全战场监视、栖息地监测、水环境监测网络。

[1] 简玉梅,张韩飞,高飞. 一种基于Agent自信度的簇间多跳路由协议[J]. 传感技术学报,2017,30(1):126-132.

[2] 戴志强,严承,武正江. 一种新的无线传感器网络非均匀分簇双簇头算法-PUDCH算法[J]. 传感技术学报,2016,29(12):1912-1918.

[3] Jain A,Reddy B V R. A Novel Method of Modeling Wireless Sensor Network Using Fuzzy Graph and Energy-Efficient Fuzzy Basedk-Hop Clustering Algorithm[J]. Wireless Personal Communication,2015,82(1):157-181.

[4] Liu J,Luo X G,Zhang X M. Job Scheduling Model for Cloud Computing Based on Multi-Objective Genetic Algorithm[J]. International Journal of Computer Science Issues,2013,10(3):134-139.

[5] Kanzaki A,Nose Y,Hara T. Dynamic Route Construction Based on Measured Characteristics of Radio Propagation in Wireless Sensor Networks[J]. International Journal of Advanced Computer Technology,2012,2(3):85-98.

[6] Kim Y D,Cho K R,Cho H S. A Cross-Layer Channel Access and Routing Protocol for Medical-Grade QoS Support in Wireless Sensor Networks[J]. Wireless Personal Communication,2014,77(1):309-328.

[7] Jung M,Han K,Cho J. Advanced Verification on WBAN and Cloud Computing for u-Health Environment[J]. Multimedia Tools Applications,2015,74(16):6151-6168.

[8] Shin K,Kim S. Predictive Routing for Mobile Sinks in Wireless Sensor Networks:A Milestone-Based Approach[J]. Journal of Supercomputing,2012,62(3):1519-1536.

[9] Yadav A,Singh Y N,Singh R. Cross Layer Design for Power Control and Link Availability in Mobile Adhoc Networks[J]. International Journal of Computers Communications and Control,2015,7(3):127-143.

[10] Michael Cheffena. Empirical Path Loss Models for Wireless Sensor Network Deployment in Snowy Environments[J]. IEEE Antennas and Wireless Propagation Letters,2017,16(1):2877-2880.

[11] Brar G S,Singh R P. A Quality Computation Model for Software Architecture[J]. International Journal of Computational and Applied Mathematics,2011,25(6):38-42.

[12] Liu Y,Ngu A H,Zeng L Z. QoS Computation and Policing in Dynamic Web Service Selection[C]//Proc 13th Int World Wide Web Conf. Alternate Track Papers Posters(WWW Alt),New York,NY,USA,2004,66-73.