韩雨涝,陈三清

(攀枝花学院数学与计算机学院,四川 攀枝花 617000)



一个适于结构健康监测的WSN能量高效动态路由协议*

韩雨涝*,陈三清

(攀枝花学院数学与计算机学院,四川 攀枝花 617000)

针对结构健康监测无线传感器网络应用中,网络生命期不足的问题,提出一种低占空比网络下能量高效动态路由协议EEDRP(Energy Efficient Dynamic Routing Protocol),该协议利用邻居节点剩余能量和链路质量动态确定转发集,通过基于转发集活动时隙预测的数据包重传机制,解决了因链路不可靠导致数据传输失败问题。最后,通过仿真对协议进行了验证,结果表明:该协议在保证数据收集低延迟和可靠性前提下,有效延长了网络生命期,满足结构健康监测应用要求。

无线传感器网络;网络生命期;重传机制;结构健康监测;占空比

结构健康监测[1-8]是一种无线传感器网络应场景,如在研究工作中针对土遗址形变监测[7]。这类场景常处于野外恶劣环境下,节点能量得不到及时更新,而应用要求监测周期较长,使得网络生命期最大化成为此类应用急需解决的问题。考虑到兴趣事件发生具有稀疏性特点,通常将无线传感器网络通信节点置于低占空比工作模式下[9-10],能有效延长节点寿命,产生的问题是数据得不到及时转发,同时由于无线链路可靠性低,导致数据收集的可靠性和延时性性能低下,而结构健康分析是建立在数据收集的可靠性和低延迟基础之上。

最近的一些研究工作,保证了低占空比无线传感网络下数据收集具有优良QoS保障。其中,FLOOD协议是无线传感器网络种一种经典的路由协议,源节点将数据以广播形式向周围处于活动状态的邻居节点发送,直到数据包到达Sink节点,或者到达预先设定的最大跳数,存在的主要问题是资源浪费。文献[11]通过构建路由树,根据节点在树中的深度构成交错的活动/睡眠调度,降低了数据传输延迟,但未考虑因链路不可靠导致传输失败产生 的延迟。文献[12]利用无线网络的广播特性,将机会路由用于低占空比的无线传感器网络中,有效的提高了数据传输的可靠性,降低了传输延迟,但机会路由利用了接收节点性能多样性特点,如果节点部署不够密集,同时唤醒的节点数量非常有限,导致机会路由的性能大大降低。文献[13]提出一种多管道调度协议(RMS),有效的保证了数据传输的可靠性和低延迟性,但节点调度的分配需要大量的通信和计算开销。另外,单纯以链路质量作为度量选择转发集,容易导致部分节点因频繁使用而能量枯竭。针对上述研究存在的问题,本文提出EEDRP协议,主要创新点在于:提出了一种休眠调度模型,均衡了节点间能量消耗,大大提高了网络生命期。其次,对于不可靠链路导致的数据传输失败问题,不像在ETX和DESS中,发送节点向固定一个节点发送数据,数据包的传输有很大延迟,在本文中使用了基于转发集节点活动时隙预测的数据包重传机制,有效的降低了数据传输延迟。

1 网络模型和问题描述

1.1 网络模型

①假定网络所有节点随机均匀分布,具有相同通信半径R、初始能量E,并且时钟同步。

②无线传感器网络表示为G=(V,E,Q,W)。其中,V表示网络节点集;E表示网络链路集;Q表示链路质量集,链路(i,j)的链路质量表示为pi,j,假定网络中所有节点间链路质量已经确定;W表示节点的工作调度集,节点i的工作调度wi由0、1组成的字符串表示,其中,i∈[1,|V|]。

(1)式中:iID为节点i的标识,Xi,n表示在工作周期T的所有时隙中,节点i第n个活动状态时隙所处位置,如Xi,3=8,表示节点i的第3个活动状态时隙处于第8个时隙位置;占空比调节参数C控制所有节点占空比。如对节点i,当iID=3,C=5,假定周期T内时隙数为20,通过式(1)计算,节点i仅在第3、8、13、18时隙处于活动状态,在其余时隙,均处于休眠状态,所以该节点工作调度w3表示为(00100001000010000100)。

④能量消耗模型:假定节点在休眠时隙,能量消耗忽略不计,只考虑节点接收和发送数据的能量消耗。为了进一步简化我们的能量模型,参考文献[14],本文只考虑发送数据对节点能耗的影响。又参考文献[15],网络节点呈随机均匀分布,源节点数据包经多跳发送Sink节点,可认为发送数据总能耗与发送节点到Sink节点的跳数成正比。定义一跳范围内节点发送一个数据包平均能耗为Ehop,则源节点发送数据包到Sink能耗如式(2)所示。

E=Ehop·hop

(2)

1.2 问题描述及目标

本文针对结构健康监测应用,提出了一种低占空比无线传感器网络下动态路由协议EEDRP,旨在均衡网络节点能耗,最大化网络生命期,同时保证数据收集的可靠性和低延迟性,满足结构健康监测应用的实际需要。

2 SLQE链路度量

先前算法[11-13,16]在确定下一跳节点链路度量时,仅考虑了链路质量,容易导致一些链路质量好的节点,由于连续多次发送数据,过早能量耗尽,影响网络生命期。本文给出一种链路度量SLQE(Sum of Link Quality and Energy),该度量在选择下一跳节点时,考虑了节点的剩余能量,有效的均衡了网络节点能量消耗,增加了网络生命期。节点i与其下一跳节点j链路度量,定义为:

(3)

式中:pi,j表示链路(i,j)的链路质量;Ni为节点i的下一跳邻居节点集;Ej为节点j的剩余能量;E表示节点的初始能量;β为用于平衡链路质量和剩余能量在度量中的比例。

3 EEDRP协议设计和实现

EEDRP协议在设计和实现过程中面临挑战主要有两个方面:首先,如何有效均衡节点间能量消耗,避免热点节点过早死亡,最大化网络生命期。其次,对于网络运行过程中存在不可靠链路,如何降低数据丢包率,保证数据传输的可靠性。针对上述挑战,本文首先提出一种休眠调度模型,使得节点工作在一种低占空比模式下,同时利用邻居节点剩余能量和链路质量动态确定转发集,通过基于转发集活动时隙预测的数据包重传机制,解决了因链路不可靠导致数据传输失败问题。EEDRP协议分为协议初始化阶段和协议运行阶段两部分。为了保证网络信息(拓扑、剩余能量)的实时更新,需每隔一段时间Tinitial进行初始化。

3.1 初始化阶段

在初始化阶段,节点均处于唤醒状态,完成路由前期的一些准备工作,包含如下3个子阶段。

①确定网络节点分层

根据节点到Sink节点的跳数,将网络节点划分为以Sink为中心,跳数由小到大的分层。具体步骤为:假定网络中共|V|个节点,Sink节点广播HM(Hop Message)包,HM包含当前节点距离Sink节点跳数hop的消息。网络内某节点接收到第1个HM包后,经历时间段T1=2 s,选择该时间段内所有HM包中跳数最小的,将该包中跳数hop更新为hop+1,并将该值作为当前节点的层数,继续广播更新后的HM包,最后直至网络中的|V|个传感器节点均获得自身所在网络的层数,假定最终形成q+1层的网络分层图,其层数依次表示为:L0,L1,…,Lq。其中,L0表示Sink节点所在的层数,即第0层;距离Sink节点u跳的节点的层数,表示为Lu,即第u层。如图1表示一个矩形部署的5层的网络分层图。

图1 网络分层图

②确定节点下一跳邻居表

表1 节点i下一跳邻居表结构

其中,节点ID为节点i的邻居节点标识;链路质量和SLQE值为节点i与邻居节点形成链路的链路质量和链路度量。确定节点下一跳邻居表过程为:首先每个节点广播NDM(Neighbor Discovery Message)包,NDM包含发送节点的ID、剩余能量以及距离Sink节点的跳数hop。当节点i收到一个节点j的NDM包后,若节点j到Sink节点比自身到Sink节点的跳数hop小,则认定节点j作为自己的下一跳节点,然后将jID和Ej值保存到自己的下一跳邻居表j的对应表项中。节点i的所有下一跳节点,构成了自身的下一跳节点集Ni。最后,通过式(1),计算每个邻居节点的工作调度w,并通过式(3),计算每个邻居节点的链路度量。最终形成了如表1所示的下一跳邻居表。

③确定节点转发集

节点转发集大小k影响着网络数据转发率、延迟和以及网络生命期。为了保证转发率和低延迟性能,k不能太小,同时又考虑到节点多次发送数据产生过多能耗,结合后面仿真验证,在这里我们取k为4。执行过程为:将每个节点下一跳邻居表按SLQE度量值降序排序,取前k个最大SLQE值对应的节点,作为当前节点的转发集节点。

3.2 运行阶段

在网络运行的每个周期T内,节点按照各自转发集节点工作调度,将数据包通过逐层动态转发,最终发送到Sink节点,当在某一层节点因转发次数超过k,数据包被丢弃。具体步骤如下:

①构建排序转发集

构建转发集排序目的是为了保证网络中数据包传输的实时性。节点i计算转发集节点下一个活动状态时隙与自身活动状态时隙之差并取绝对值,将结果以升序排列,即得到节点i的排序后的转发集,表示为Si。

②运行过程

网络中每个节点按照排序后的转发集,将数据包逐层转发给下一跳节点,直至数据包发送到达Sink节点。其执行过程为:当网络中位于Lu层的节点i有数据包需发送时,初始化m=1,节点i向位于L(u-1)层的排序后的转发集中的第m个节点j发送数据包;节点j收到节点i的数据包后,判断自身是否为Sink节点,是则向节点i返回一个包含flag=1的ACK包,否则返回包含自身剩余能量和flag=0的ACK包;节点i判断自己是否收到j的ACK包,收到ACK包,进一步判断如果ACK包中flag=1,可知节点i的数据包已经成功发送到Sink节点,结束。如果节点i收到的ACK包中flag=0,可知节点j不是Sink节点,则节点i更新其下一跳邻居表中节点j的剩余能量,第Lu层的数据包发送结束,令Lu=L(u-1),进行下一层节点的数据包的转发;如果节点i未收到来自j的ACK包,则令m=m+1,定义max为最大转发次数,其数值等于转发集大小k,判断m<=max是否成立,是则转入发送节点下一次转发;否则,节点i发送数据包失败,数据包被丢弃,结束。执行过程如图2所示。

图2 协议运行图

4 网络性能分析

①源节点到Sink转发率

依据链路质量、休眠调度和转发集,第l层节点i,计算到l-1层一跳转发率HDR(Hop Delivery Ratio),如式(4)所示:

(4)

式中:m表示当前发送次数,k表示转发集大小。增加k,提高了一跳转发率,但这加剧了发送节点的能量开销。进一步分析可知,源节点s到Sink转发率(End Delivery Ratio),如式(5)所示:

(5)

假定平均链路质量达到0.6,k=4,由式(4)计算一跳转发成功率约为98%。当网络跳数为5跳时,源节点到Sink的转发率超过88%。

②源节点到Sink转发延迟

定义pl(i,j)为第l层节点i向l-1层转发集成功转发的前提下,转发集中前j-1个节点发送失败,而第j个节点发送成功的概率,可表示为式(6):

(6)

则源节点到Sink转发延迟EDT(End Delay Time),可表示为式(7):

(7)

式中:Δi,j为节点i和转发集中节点j下一活动时隙的时隙间隔数;π是节点一次成功发送数据包所需时间。

③源节点到Sink传输能耗

网络模型中,假定网络区域中节点均匀密集部署,且具有相同发射功率。依据本文能量消耗模型,当数据包沿多跳路径发送到Sink节点,所产生的能耗与发送节点到Sink节点的跳数成正比,能量消耗模型对应式(2),由于每一跳最多发送k次,则E∈[e·hop,k·e·hop],其中e表示发送一次数据所需能耗。

5 仿真结果及讨论

本节将通过java语言编写的模拟器仿真并分析协议的性能。每个时隙随机选择一个节点作为源节点发送数据包,经过多跳转发到达Sink节点,所有仿真数值均为40个随机场景结果的平均值。网络相关参数设置如表2所示。

表2 仿真参数

5.1 转发次数k对网络性能影响

在EEDRP协议中,为了分析转发次数k对网络数据包转发率、转发延迟和网络生命期的影响,我们将转发次数由2增加到5,网络中节点数目固定为500不变,仿真结果及讨论如下:

图3(a)显示了k对从源节点到Sink端到端平均转发率影响,从图中可以发现,随着k的增加,成功转发率增大。这是由于k增加后,转发集节点增多,最终成功传输到Sink节点的包越多。图3(b)是k对从源节点到Sink端到端平均转发延迟的影响,从图3可以看出,随着k的增加,通过转发集节点转发数据包的几率增加,使得每一跳转发延迟降低,最终降低了端到端平均延迟。图3(c)是k对网络生命期的影响。可以看出,随着k的增加,网络生命期呈减少趋势,这是由于节点发送次数增加,如果链路质量较差,需要多次发送,使得发送节点的能量消耗较大。另外,转发集节点越多,计算量和通信量越大,这些都影响着网络生命期。综上分析,k过小降低了数据传输的转发率,增加了数据传输的延迟。另一方面,随着k的增加,网络生命期呈现明显降低趋势。最终,结合结构健康监测应用对网络生命期要求较长的特点,同时综合网络的整体性能,选择k值为4。

图3

5.2 3种协议不同网络节点密度下性能比较

我们将网络节点数由300增加到600,固定部署区域大小不变,在3种协议EEDRP、FLOOD和RMS下,对源节点到Sink端到端平均转发率、平均延迟和平均网络生命期进行了比较。

图4(a)是3种协议下,节点端到端的数据包转发率分布情况。从图中可以发现,随着节点数量的增大,3种协议的平均转发率均呈增加趋势。这是由于部署区域固定,随着节点数量的增加,每个节点的周围处于活动状态节点增多,这增加了数据转发率。另外,RMS转发率性能稍微优于EEDRP,而这种两协议该性能要远远低于FLOOD。这是由于,FLOOD不管数据包转发的方向,向周围节点进行广播,这就极大的增加了数据包被转发给Sink节点的概率。RMS的转发率优于EEDRP,这是因为RMS在选择转发集时,选择链路质量最高的节点转发,而EEDRP中β=0.9,综合了链路质量和节点剩余能量,弱化了链路质量因素,使得转发率有一定程度降低。图4(b)是3种协议下网络节点端到端的数据包转发延迟分布情况。从图4可以发现,随着节点数量的增大,3种协议的转发延迟均呈递减趋势,FLOOD转发延迟要远优于其他两种协议,而RMS的转发延迟稍微优于EEDRP,原因与图4(a)情况类似,为避免篇幅冗长,在此略去。图4(c)是3种协议网络生命期比较情况。

图4

从图4可以发现,随着节点数量的增加,EEDRP和RMS的网络生命期呈现上升趋势,FLOOD逐渐降低。这是由于随着节点密度的增加,在EEDRP和RMS中,有更好链路质量的节点参与转发,而FLOOD中同时处于活动状态节点的增多,由于没有转发集的选择,使得一个节点的任意邻居节点有数据包要发送时,可能都要通过该节点,极大的降低了该节点的寿命,影响了整个网络的生命期。从图4还可以看出,对于任意一组节点数量固定的网络仿真,EEDRP网络生命期最高,且EEDRP和RMS的网络生命期要远远高于FLOOD。FLOOD网络生命期最低,这是由自身的洪泛特性决定的;EEDRP网络生命期高于RMS,这是由于,首先,RMS在初始化时,为每个节点都分配了最优的时隙,而这是以通信和计算开销为代价的,而EEDRP协议根据每个节点ID确定工作调度,不需要额外的通信开销。其次,EEDRP在选择转发集使用了参数β,考虑了下一跳节点剩余能量,从而均衡了节点间能量消耗,提高了网络生命期。

6 结论

本文针对结构健康监测无线传感器网络应用对网络生命期要求较高的特点,提出了一种低占空比网络下能量高效的动态路由协议EEDRP。仿真结果表明:相对于FLOOD和RMS,EEDRP具有最大的网络生命期,同时能满足结构健康监测应用所需转发率和延迟性能要求。

[1] Liu X,Cao J,Song W Z. Distributed Sensing for High-Quality Structural Health Monitoring using WSNs[J]. IEEE Transactions on Parallel Distributed Systems(TOPDS),2015,26(3):738-747.

[2] Sante R D. Fibre Optic Sensors for Structural Health Monitoring of Aircraft Composite Structures:Recent Advances and Applications[C]//Sensors,2015,15(8):18666-18713.

[3] 任小芳,贾栋,赵辉,等. 基于光纤Bragg光栅的古建筑结构健康监测技术研究[J]. 传感器技术学报,2015,28(1):34-38.

[4] 季赛,黄丽萍,孙亚杰. 面向无线传感结构健康监测的压缩感知方法研究[J]. 传感器技术学报,2013,26(12):1740-1746.

[5] 俞姝颖,吴小兵. 陈贵海无线传感器网络在桥梁健康监测中的应用[J]. 软件学报,2015,26(6):1486-1498.

[6] Beutel J,Gruber S,Gubler S. The PermaSense Remote Monitoring Infrastructure[C]//International Snow Science Workshop Davos 2009. Switzerland. 2009:187-191.

[7] 陈晓江,房鼎益. PDHP:一个适于土遗址微环境监测的WSN 路由协议[J]. 计算机研究与发展,2011,48(增刊):223-229.

[8] Tie X,Venkataramani A,Balasubramanian A. R3:Robust Replication Routing in Wireless Networks with Diverse Connectivity Characteristics[C]//Proceedings of the 17th Annual International Conference on Mobile Computing and Networking,2011:181-192.

[9] Buettner M,Yee G V,Anderson E,et al. X-MAC:A Short Preamble MAC Protocol for Duty-Cycled Wireless Sensor Networks[J]. Sensys,2015,14(4):307-32.

[10] Xiao M,Wu J,Huang L. Time-Sensitive Utility-Based Single-Copy Routing in Low-Duty-Cycle Wireless Sensor Networks[C]//IEEE Transactions on Parallel Distributed Systems(TOPDS),2015,26(5):1452-1465.

[11] Gang Lu,Bhaskar Krishnamachari,Cauligi S Raghavendra. An Adaptive Energy-Efficient and Low-Latency MAC for Data Gathering in Wireless Sensor Networks[C]//Proceedings of the 18th International Parallel and Distributed Processing Symposium(IPDPS),2004. April 2004.

[12] Landsiedel O,Ghadimi E,Duquennoy S,et al. Low Power,Low Delay:Opportunistic Routing meets Duty Cycling[C]//Proceedings of the 11th ACM/IEEE International Conference on Information Processing in Sensor Networks(IPSN’12),Beijing,China,April 2012.

[13] Cao Y,Guo S,He T. Robust Multi-Pipeline Scheduling in Low-Duty-Cycle Wireless Sensor Networks[C]//Proc of IEEE Infocom. Orlando,2012:361-369.

[14] Gu Y,He T.Data Forwarding in Extremely Low Duty-Cycle Sensor Networks with Unreliable Communication Links[C]//Proc ACM SenSys,2007:321-334.

[15] Xiong S,Li J,Li M,et al. Multiple Task Scheduling for Low-Duty-Cycled Wireless Sensor Networks[C]//IEEE INFOCOM,2011.

[16] Cao Z,He Y,Ma Q,et al. L2:Lazy Forwarding in Low-Duty-Cycle Wireless Sensor Network[C]//IEEE/ACM Transactions on Networking.(TON),2015,23(3):922-930.

韩雨涝(1981-),男,陕西礼泉人,博士,讲师,主要研究领域为无线传感器网络协议设计,ylhan2008@126.com;

陈三清(1980-),男,湖北省广水市人,硕士,讲师,研究方向为移动互联网技术与应用。

An Energy Efficient Dynamic Routing Protocol in WSN forStructural Health Monitoring*

HAN Yulao*,CHEN Sanqing

(Department of mathematics and computer,Panzhihua university,Panzhihua Sichuan 617000,China)

With the shortage problem of network lifetime in wireless sensor network of structural health monitoring,this paper proposes a routing protocol EEDRP(Energy Efficient Dynamic Routing Protocol)in the low duty cycle network. The protocol dynamically works out a set of forwarding nodes by using neighbor nodes’ link quality and residual energy. At the same time,the protocol also solves the problem of data transmission failure caused by unreliable links by the data packet retransmission mechanism which is based on predicting active time slots of forwarding set. At last,a simulation platform was established to verify the protocol,the result showed that the protocol can prolong the network lifetime efficiently in the conditions of assuring reliability and low latency of data collection. Therefore it can meet the application requirements of structural health monitoring.

wireless sensor networks;network lifetime;retransmission mechanism;structural health monitoring;duty cycle

项目来源:国家科技支撑计划自助项目(2013BAK01B02);国家自然科学基金项目(61070176,61202393,61272461,61170218);陕西省教育厅科研计划项目(2011JG06);攀枝花市科技计划项目(2015CY-S-7)

2016-11-29 修改日期:2017-03-05

TP393

A

1004-1699(2017)07-1106-06

C:6150P

10.3969/j.issn.1004-1699.2017.07.023