低占空比WSN中一种低时延路由协议

李 林 徐 震* 陈良银 郑贵敏

1(武汉轻工大学电气与电子工程学院 湖北 武汉 430000)2(四川大学计算机学院 四川 成都 610064)



低占空比WSN中一种低时延路由协议

李 林1徐 震1*陈良银2郑贵敏1

1(武汉轻工大学电气与电子工程学院 湖北 武汉 430000)2(四川大学计算机学院 四川 成都 610064)

低占空比无线传感网络(LDC-WSN)可以有效地提高网络中节点的生存周期。但是它却带来一些额外的问题，如较长的等待时延等。另外，由于链路质量的原因，一些数据需要传输多次才能成功，这不仅浪费能量，而且导致较大的时延。为解决这些问题，提出一种新颖的路由算法LLR(low latency routing)，该算法先根据节点到汇聚节点的跳数进行分层，每一个节点均计算其到父节点的时延以及父节点到汇聚节点的时延，从而寻找一条到达汇聚节点的最低时延的传输路径。仿真结果表明，相对于ESL和LES算法，这种路由算法能更好地节省能量和降低时延。

无线传感网络 低占空比 时延

0 引 言

无线传感网络[1](WSN)由大量具有信息采集功能的节点组成，这些节点体积微小，将它们部署在需要检测的范围内，它们可以采集我们需要的信息并发送给汇聚节点。由于无线传感网络使用方便，价格低廉，因此被广泛应用在各行各业中，比如煤矿监控系统[2]、长链路型输电线路监测系统[3]、基于作物生长模型的WSN温室环境智能监控系统[4]等。

在无线传感网络中，大多数的节点都是采用电池供电，因此降低能耗以延长网络生存时间是无线传感网络设计的一个重要挑战。由于传感器节点更换电池比较困难，所以电池使用寿命直接影响整个传感器的寿命。传感器节点主要在感知、处理和通信三个方面消耗能量。其中通信消耗的能量是最多的，通信时节点主要分为四个状态：发送、接收、空闲、睡眠。其中睡眠状态下消耗的能量是最少的。因此在必要的时候让节点进入睡眠状态可以大大地节省节点的能量，延长整个网络的寿命。在MAC协议中加入睡眠机制，是一种行之有效的方法。在这种情况下，出现了低占空比无线传感网络。低占空比无线传感网络中，节点只在一个周期的一个或者几个特定的时隙苏醒，大部分时间处于睡眠状态，节点苏醒之后才能够接收、发送数据或者进行监听。实验证明监听所消耗的能力也是十分大的，它等同于传输数据时所消耗的能量[5]。而在睡眠的过程中，节点消耗的能量是非常小的。如典型的协议IEEE 802.15.4。这个协议中指出在一些不必要的时候可以关闭节点的天线，这样可以节省一些能量。

低占空比下的实时数据传输是影响节点能量的一个关键因素。MMSPEED[6]提出了一种多路径多速度的路由协议用来在一定程度上保证网络的链路质量。Myounggyu等提出了一种非对称链路下的MAC协议[7]，它在数据传输过程中，通过切换传输的模式来确保数据传输成功，减少传输次数，降低能量消耗。Fei等提出了一种新的工作调度表的构建方法[8]，它能够较好地解决低占空比条件下的延时问题。Zu等提出了一种能够有效解决时延的路由算法ESL[9]，它通过寻找备用节点来减少多次重传所带来的时延，一旦传输失败后，传输节点传输数据给备用节点，而不是重传，这样就减少低占空比下的等待时延。但是如果备选节点的链路质量都较低时，会造成传输次数增加，也会造成较大的延时。陈良银等人提出了一种LES算法[10]这种算法采用增加节点时隙的方式来减少时延，但由于时隙增加过多,导致能力过多消耗。为此我们提出了一种能够更好地解决时延问题的LLR路由算法。

LLR路由算法的核心思想是:源节点向汇聚节点传输数据时，先根据节点到汇聚节点的跳数将节点分为不同的层，相同跳数的节点位于同一层。传输数据时，数据沿着节点跳数减小方向的传输路径即为数据传输的最短路径，在这些最短路径中，我们需要找出传输时延最低的路径。在基于梯度的网络中，每一个节点均计算其到父节点的时延以及父节点到汇聚节点的时延，从而计算出每一层的各节点到汇聚节点的最低时延及其路径。

1 系统模型与问题描述

1.1 网络模型

假设无线传感网络由n个普通节点和一个汇聚节点组成。每一个节点都装备全向天线，且所有的节点有相同的传输范围。网络拓扑用函数G=(V,E)表示，其中V表示网络中节点的集合，E表示连接传感器节点间链路的集合。若传感器节点A和B在彼此通信范围内，则可以认为节点A、B可以相互通信。

1.2 延迟模型

如果节点A与节点B可以在物理上进行正常通信，则可用lij表示节点i和节点j之间的一条链路。所有的链路均包含3个属性。

(1) 传输时间t， t表示成功传输一次数据包节点所消耗的时间，其中包括信号编码以及无线传输所需要的时间。

(2) 链路质量q， q表示节点使用这条链路将数据包一次传输成功的概率。

(3) 最大传输次数r， r表示发送数据包的节点最多可传输r次，否则会将数据包丢弃。

定义1等待时延Sij(t)：节点i在t时刻有一个数据包需要传输给节点j，从节点i准备传输数据包到节点j苏醒并准备接收之间的时间为等待时延。

(1)

定义2期望传输成功率Eqij(r)：节点i在向节点j传输数据时，节点j在r次传输过程中收到数据的概率：

(2)

定义3期望传输时延ESij(r)：节点i在向节点j传输数据时，节点j在r次传输过程中收到数据的期望时延。在低占空比的条件下，数据下次传输需要等到下一个周期节点苏醒时。在本文中简记为d(i,j)。即：S(k)=S1+(r-1)T。

(3)

在图1所示的基于链路质量的数据传输模型中，期望传输成功率Eqij(r)越低，则丢包率越高，传输次数越多，这不仅浪费能量，而且大大增加了传输时延。我们定义一个传输成功率阈值δ，作为传输路径选择的一个控制参数。在低占空比无线传感网络中，当链路lij满足Eqij(r)≥δ时，认为传输是成功的，无需再次传输。只有链路qij满足Eqij(r)≥δ时，该条链路才可作为传输候选链路。所以我们需要计算节点S到节点Ai的传输成功率EqSAi(r)。并将各条传输链路的传输成功率与阈值相比较，选出期望传输成功率高于阈值传输路径{SA1,SA2,…}。

图1 基于链路质量的数据传输模型

1.3 问题描述

无线传感网络中，数据从许多源节点采集并上传到汇聚节点。网络中的节点依据BFS算法由各节点到汇聚节点的跳数分成不同的层，跳数相同的节点位于同一层。在传输数据时，无线传感网络中的数据沿着节点跳数减小的方向传输，此时传输路径所包含的节点数目最少，为最短传输路径。如图2所示，源节点A的信息需要经过一个N层的网络到达汇聚节点S。由于传输路径p(A,S)={A→B2→C1→…→M1→N1→S}中每层只有一个节点，所以源节点A到汇聚节点S的最短传输路径为p(A,S)。

图2 网络传输模型

要使低占空比传感网络能够满足实时QOS需求，本文在基于传输成功率阈值的基础上寻找最低时延的传输路径，以此来降低节点发送数据的等待时延。图2中，源节点A要发送数据给汇聚节点S，传输路径有若干条，要使端到端的延时最低，可以将问题转化为基于传输成功率阈值的基础上，如何从这些最短路径中寻找出一条时延最低的传输路径。该问题可以用式(4)-式(6)描述。

Eqij(r)≥δ ∀lij∈p(A,S)

(4)

min hop[p(A,S)]

(5)

min d(A,S)

(6)

其中：p(A,S)表示源节点A到汇聚节点S之间的传输路径；d(A,S)表示源节点A传输数据到汇聚节点S的等待时延。

针对这个问题，下面将提出一种行之有效的时延控制方法。

2 算法设计

在图3中的网络拓扑中，为了寻找从节点Ni到汇聚节点S的最低时延dmin(Ni,S)的传输路径，具体实现方法为：先将网络中的节点根据其到汇聚节点S的跳数分层，相同跳数的节点位于同一层。从汇聚节点S的下一跳节点开始，每一个节点Mi均计算其与父节点之间链路的期望传输成功率，若满足阈值δ，则计算出它到汇聚节点S的最低时延dmin(Mi,S)及其传输路径pmin(Mi,S)并储存。其最低时延dmin(Mi,S)为节点Mi到其父节点的时延与其父节点到汇聚节点S的最低时延之后的最小值。level n上的节点Ni到汇聚节点S的最低时延dmin(Ni,S)为节点Ni到其上一层level (n-1)上节点Qi的传输时延与节点Qi到汇聚节点S的最低时延与之和的最小值。

图3 基于梯度的数据传输模型

图3中， 汇聚节点S一直处于工作状态，第一层level 1上的节点Bj向汇聚节点S传输数据的等待时延为0。对于第二层level 2上的节点Ci，若传输链路qBjCi满足EqBjCi(r)≥δ，则节点Ci传输到汇聚节点的最低时延为：

dmin(S,Ci)=min{d(S,Bj)+d(Bj,Ci)}=dmin(Bj,Ci)

其中{d(S,Bj)+d(Bj,Ci)}表示节点Ci传输到level 1层上的节点Bj的时延与节点Bj到汇聚节点S的时延之和，这个最小值即为最低时延值。pmin(S,Ci)表示传输数据达到最低时延的传输路径。这样可以计算出level 2上所有节点到汇聚节点S的时延。第三层level 3上的节点Di，若传输链路qCjDi满足EqCjDi(r)≥δ,则节点Di到汇聚节点S的最低时延为：

dmin(Di,S)=min{dmin(S,Cj)+d(Cj,Di)}

以此类推，可以计算出位于level n上的节点Ni，若传输链路qQjNi满足EqQjNi(r)≥δ，令dmin(Ni,S)={dmin[S,Qi]+d[Qj,Ni]}，Qi表示节点Ni的父节点。

这样就可以计算出节点Ni传输数据到汇聚节点S的最低等待时延dmin(Ni,S)。

算法LLR路由算法

Input：网络拓扑G=(V,E)，汇聚节点S，S∈V。

Output: 一个 MLD树(时延最低的树：储存各节点到汇聚节点的最低期望传输时延及相对应的传输路径)。

TMLD=(VMLD,EMLD)

/*第一步: 将网络中的节点分层*/

1.以汇聚节点S为根，通过BFS算法，将所有的节点V分成level 0,level 1,level 2,…,level l这l层

2.VMLD←{S}，EMLD←∅，DS(连通子集)←{S}

3.for m←1 to l do

/*第二步: 找到最低时延的传输路径*/

4.CD(侯选连通子集)←level m{u|u∈N(v),v∈DS}

5.for any node u∈CD do

if 节点u与父节点w之间链路的期望传输成功率满足δ寻找p(u,s)←节点u到节点s的最短传输路径

∀vm∈DS,ifp(u,s)is{u→w→s},thend(u,s)=d(u,w)+d(w,s)

计算d(u,s)←在所找到的最短传输路径p(u,c)中计算节点u到汇聚节点s的期望传输时延

找出pmin(u,s)←比较各条传输路径的期望传输时延d(u,s)，找出最低时延dmin(u,s)及对应的传输路径

/*第三步: 把u加入DS，并让w成为父节点,构造MLD树*/

6.while CD≠∅ do

u←节点u及其dmin(u,s),u∈CD

DS←DS∪{u}

EMLD←the edges in pmin(u,s)

w←parent node of u in pmin(u,s)

VMLD←VMLD∪{u}∪{w}

CD←CD(w)

7.return TMLD

图4中，网络分为四层。假设源节点D1有一个数据包需要发送到汇聚节点S。每一个节点均计算其到父节点之间链路的期望传输成功率，若满足阈值δ，再计算不同层上的节点到汇聚节点的最低传输时延并存储对应的传输路径。

图4 基于梯度的模拟数据传输模型

1) 对于第一层上的节点Bi，EqSB1(r)≥δ，EqSB2(r)≥δ，EqSB3(r)≥δ，EqSB4(r)≥δ。

dmin(S,B1)=dmin(S,B2)=dmin(S,B3)=dmin(S,B4)=0

2) 对于第二层上的节点Ci，以节点C3为例，节点C3的父节点为B1、B2。EqB1C3(r)≤δ，EqB2C3(r)≥δ。

则令d=dmin(S,C3)=dmin(S,B1)+d(B1,C3)，所以节点C3传输数据到汇聚节点的最低时延dmin(S,C3)为d。因此最佳传输路径pmin(S,C3)为{C3→B1→S}。

3) 对于第三层上的节点D1，节点D1的父节点为节点C3、C4。EqC3D1(r)≥δ，EqC4D1(r)≥δ。

则令d1=dmin(S,C3)+d(C3,D1)，令d2=dmin(S,C4)+d(C4,D1)，假设d1≤d2，所以节点C3传输数据到汇聚节点的最低时延dmin(S,D1)为d1。因此最佳传输路径pmin(S,D1)为{D1→C3→B1→S}。

3 仿真实验与性能评价

在本节，我们将通过仿真实验来验证LLR路由算法的各项性能，将其各项性能指标与其他算法来对比分析。由于LLR路由算法是基于ESL算法的，且LES和ESL算法在延时和节能上拥有很好的性能，是低占空比传感网络中典型的算法，所以在仿真过程中我们主要与LES和ESL算法比较。

3.1 评价方法

对于LLR路由算法，我们主要从以下两个方面来评估它的性能。

(1) 数据多跳传输的时延：在无线传感网络中，节点间数据传输是分层的，在这里我们主要考虑从源节点经多跳传输到汇聚节点的时延。

(2) 网络的生存周期:从仿真开始到网络中节点因能量耗尽而被废弃的节点的数量超过30%(此时整个网络的性能非常差，可以认为整个网络接近瘫痪)所持续的时间。

3.2 仿真实验参数

美国明尼苏达大学双城分校Tian He教授的实验室做项目研究时，对基于MicaZ/TinyOS平台的链路质量做了大量研究，发现阈值取为0.8最合理，所以仿真中我们取用经验值0.8[12]。若实际用途中对数据包的到达率要求低时，可以降低阈值。仿真平台参数设置如表1所示。

表1 仿真平台参数

3.3 不同参数对算法性能的影响

在这一节中，将在不同节点数量，不同占空比的条件下对LLR路由算法的平均时延和网络生命周期进行仿真。并将仿真结果与LES和ESL算法进行比较，仿真中，每次只改变一个参数，其余参数保持默认值。

低占空比无线传感网络中，数据传输的期望传输时延与节点的数量有着很大的关系。节点数量越多，可选路径越多，时延越低。

图5显示了三种算法的平均期望时延随着节点数量变化的变化曲线。由仿真结果可知，随着节点数量的增加，平面内建立的链路越多，传输的可选路径越多，所以平均期望传输时延越小。LLR路由算法通过计算出各条路径的期望传输时延来选出从源节点到汇聚节点的时延最低的一条传输路径。而ESL和LES算法仅找出下一跳的最佳传输路径以此来减少传输时延，没有考虑整条路径的传输时延，所以相对其他两种算法，LLR路由算法的时延明显较低。例如：当节点数量为300时，ESL和LES的平均时延为601 s和583 s，而LLR路由算法的延时仅为480 s，因此LLR路由算法能够减少数据传输时延，最好的情况下减少了近20%。

图5 节点数量和平均时延

低占空比的条件下，传输时延与节点的占空比有着很大的关系，占空比越大，传输时延越小。

图6显示了三种算法的期望传输时延随着节点占空比变化的变化曲线。由仿真结果可知，不同占空比下，相对于LES和ESL算法，LLR路由算法的平均传输时延最低。例如：当节点占空比为1%的情况下，LLR路由算法的平均时延为530 s，而LES和ESL算法的平均时延为676 s和636 s。因此LLR路由算法可以更好地解决低占空比无线传感网络中的时延问题。

图6 节点占空比和平均时延

在低占空比无线传感网络中，网络的生命周期随着节点占空比的增大而减小，占空比越高，节点的寿命越短。

图7显示了三种算法的节点生命周期随着节点占空比变化的变化曲线。根据仿真结果可以看出，网络的生命周期随着节点占空比的增大而减少，在相同占空比下，LLR路由算法的生命周期略长。例如：当节点占空比为1%时，LES和ESL算法的网络生命周期3×106s和3.6×106s，而LLR路由算法的生命周期为4×106s。这是因为LES算法采用增加时隙的方式来减少时延，这会造成不必要的能量损耗会降低网络的生命周期，所以生命周期最短。ESL算法采用寻找候选节点的传输的方式，但这种方式一旦遇到较低的链路质量时，重传次数增大，浪费较多的能量，而且时延较高。而LLR路由算法是在在传输链路质量满足期望传输成功率的基础上找出一条到达汇聚节点的最低时延的传输路径，这样可以在保证时延较低的基础上最大地节省能量，所以LLR路由算法更能延长网络的寿命。

图7 节点占空比和生命周期

4 结 语

本文对于低占空比无线传感网络存在的时延问题提出了一种LLR路由算法。该算法根据节点到汇聚节点的跳数将整个网络进行梯度分层，网络中的节点均计算其到父节点的时延以及父节点到汇聚节点的时延，通过比较节点到汇聚节点所有传输路径的时延，从而找出一条从源节点到达汇聚节点的最低时延的传输路径。仿真实验结果证明了LLR路由算法相比ESL和LES算法在低占空比无线传感网络中能更有效地降低时延。

[1] 孙利民,李建中,陈渝,等.无线传感网络[M].北京,清华大学出版社,2005.

[2] Guo Peng,Jiang Tao,Zhang Kui,et al.Energy-Efficient Miner Monitoring System with Duty-Cycled Wireless Sensor Networks[J].Hindawi Publishing Corporation,2012,8(2):1-9.

[3] 金山,崔文,金志刚.基于WSN技术油罐区消防报警调度系统的设计[J].计算机应用研究,2013,31(9):1-4.

[4] 胡夏芸,杨余旺,曹宏鑫,等.基于作物生长模型的WSN温室环境智能监控系统[J].计算机应用与软件,2014,31(7):97-100,190.

[5] Zhen Jiangli,Mo Li.Towards Energy-Fairness in Asynchronous Duty-Cycling Sensor Networks[J].ACM Transactions on Sensor Networks,2014,10(3):38-64.

[6] Felemban E,Lee C G,Ekici E,et al.Probabilistic QoS guarantee in reliability and timeliness domains in wireless sensor networks[C]//Infocom Joint Conference of the IEEE Computer & Communications Societies IEEE,2005:2646-2657.

[7] Myounggyu Won,Taejoon Park,Sang H,et al.A MAC Protocol for Low-Power Duty-Cycled Wireless Sensor Networks with Asymmetric Links[J].IEEE Comunication Letters,2014,18(5):809-811.

[8] Fei Yang,Isabelle Aug éBlum.Delivery ratio-maximized wakeup scheduling for ultra-low duty-cycled WSNs under real-time constraints[J].Computer Networks,2011,55(3):497-513.

[9] Zu Zhifan.Delay-Driven Routing for Low-Duty-Cycle Sensor Networks[J].International Journal of Distributed Sensor Networks,2013(2):178-179.

[10] 陈良银,王金磊,张靖宇,等.低占空比WSN中一种节点休眠调度算法[J].软件学报,2014,25(3):631-641.

[11] Liu R,Fan K,Sinha P.Locally scheduled packet bursting for data collection in wireless sensor networks[J].Ad Hoc Networks,2009,7(5):904-917.

[12] Gu B Y,He T.Data Forwarding in Extremely Low Duty-Cycle Sensor Networks with Unreliable Communication Links[C]//International Conference on Embedded Networked Sensor Systems,Sensys 2007,Sydney,Nsw,Australia,2007:973-974.

A LOW-LATENCY ROUTING PROCOTOL IN LOW-DUTY-CYCLE WSN

Li Lin1Xu Zhen1*Chen Liangyin2Zheng Guimin1

1(SchoolofElectricalandElectronicEngineering,WuhanPolytechnicUniversity,Wuhan430000,Hubei,China)2(SchoolofComputerScience,SichuanUniversity,Chengdu610064,Sichuan,China)

Low duty cycle wireless sensor networks (LDC-WSN) can improve the life of node in the network effectively. But it brings some additional problems, such as a long wait delay and so on. In addition, due to the quality of the link, some data need to be transmitted several times to be successful, not only a waste energy, but also lead to larger delay. In order to solve this problem, this paper proposes a low-latency routing (LLR) algorithm. The algorithm stratifies by node hops to sink node, and calculates the delay of each node to the parent node and parent node to sink node, in order to find the minimum time delay of transmission path to the sink node. The simulation results show that compared to the ESL and LES algorithm, this routing algorithm can better save energy and reduce delay.

Wireless sensor networks Low-duty-cycle Delay

2016-02-20。国家自然科学基金项目(61373091)。李林，学士，主研领域：无线传感网络。徐震，副教授。陈良银，副教授。郑贵敏，学士。

TP393

A

10.3969/j.issn.1000-386x.2016.11.018