徐 震，杨 蕾，周 龙

(武汉轻工大学 电气与电子工程学院，湖北 武汉430023)

低占空比无线传感网络中端到端的时延路由协议设计

徐 震，杨 蕾*，周 龙

(武汉轻工大学 电气与电子工程学院，湖北 武汉430023)

低占空比无线传感网络可以有效地提高网络中节点的生存周期。但是它却带来一些额外的问题，如较长的等待延时等。另外，由于链路质量的原因，一些数据需要多次传输才能成功，这不仅增加能量消耗，而且导致较大的时延问题。为解决这些问题，笔者提出了一种新颖的算法(DEtoERA)，通过计算不同传输模式下的时延和传输成功率选出最佳传输方式，在满足延时要求的情况下节省能量。仿真结果表明，相对于ESL算法，这种算法能更好地节省能量和降低时延。

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

1 引言

无线传感器网络( Wireless Sensor Network， WSN)是由部署在监测区域的大量体积小、成本低、具有无线通信、传感、数据处理的传感器节点通过自组织方式组成的一种网络。无线传感器节点通常由电池供电，传感网络大多部署在人烟稀少或是人类无法到达的地区，这给节点更换电池变得尤为困难。为解决这个关键问题，需要降低节点的能量消耗，使之获得更长的网络生命周期[1]。然而，在环境监测预警系统等很多诸如此类应用中，对信息的采集实时性要求较高。因此，针对此类无线传感网络应用进行网络协议设计时，需要综合考虑能量和时延两种因素。

为了降低传感节点的能量消耗，一种有效的节能方法是使节点尽可能多地进入睡眠模式。Crossbow公司的数据[2]表明，如果节点一直保持在活跃模式下只能存活 100～120 h，而在1%的占空比下工作，其寿命可达一年以上。因此，低占空比 WSN 可以克服节点能量消耗问题，满足长期监测应用的需求。然而，由于每个节点的周期性睡眠，会产生较长的延迟，因为发送节点必须等到它的邻居节点醒来才能转发数据包，这段等待时间被称为等待时延。等待时延由设定的占空比周期决定。等待时延在低占空比WSN的端到端时延中占了主导。而且如果永远选择最先苏醒的网络节点作为转发节点，可能导致其与被选节点间的链路质量差，从而消耗更多的能量，所以在进行低占空比无线传感器网络路由算法设计时，需要综合考虑能量和时延两种因素。

低占空比下的实时数据传输问题已经引起许多学者的关注，文献[3][4][5][6]提出了一些问题的解决方案。文献[3]针对链式网络和树状网络，分别利用动态规划和免疫遗传算法通过增加节点的工作时隙以满足端到端时延的约束。文献[4]提出了一种利用2跳邻居信息动态切换的实时路由协议框架来实现任意端到端之间的实时数据传输。文献[5]提出了一种能够有效解决时延的路由算法ESL，它通过寻找备用节点来减少多次重传所带来的时延，一旦传输失败后，传输节点传输数据给备用节点，而不是重传，这样就减少低占空比下的等待延时，但是如果备选节点的链路质量都较低时，会造成传输次数增加，也会造成较大的延时。文献[6]等人提出了一种LES算法这种算法采用增加节点时隙的方式来减少延时，但由于时隙增加过多,导致能力过多消耗。为此，本文提出了一种DEtoERA算法，该算法能够更好地解决低占空比网络中的时延问题。

2 系统模型

2.1 模型假设

(1)整个网络中所有节点时间是同步的。

(2)节点的工作调度表都是周期性的，一个工作周期被划分成许多的时隙，每个时隙的持续时间是相同的。每一个时隙持续的时间长度能够发送一个数据包或者接收一个探针包。由于数据包比探针包大很多，如果接收节点成功的接收了数据包，那么它能够成功接收探针包。

(3)节点间的链路质量基本保持不变。

(4)如果一个节点没有数据需要传输，那么它在一个工作周期内只苏醒一次；但是如果它有数据需要传输，它可以在一个周期内苏醒多次。

(5)在传输数据时，无线传感网络中的数据沿着节点跳数减小的方向传输。

2.2 节点工作调度表的建立

节点工作调度表由上而下从sink节点开始建立，建立好工作调度表之后，该节点会将其工作调度表广播到整个网络。节点和邻居共享其工作调度表。节点在更新其工作调度表之后会通知所有邻居节点，在确定其所有邻居节点都知道新的工作调度表后，该节点会在下一次苏醒时启动新的工作调度表。

2.3 数据传输模型

无线传感网络中，传感器节点依据BFS(Breadth First Search)算法由各节点到汇聚节点的跳数分成不同的层，跳数相同的节点位于同一层。传输数据包时，无线传感网络中的数据沿着节点跳数减小的方向传输，此时传输路径所包含的节点数目最少，为最短传输路径。图1为一个简易的数据传输模型，节点A为源节点，假设在WA时刻节点A有一个数据包需要发送给sink节点，它需要通过其邻居节点B, C, D中继转发来完成数据包的传输。则节点A需要从传输路径PAB, PAC, PAD中选择一条来传输数据。

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

3 路由协议设计

如上图1所示，这里有四个节点A, B, C, D。取周期T为100，他们的苏醒时刻分别为WA、WB、WC、WD，圆圈下面的整数表示节点的工作时隙， 链路上面的数字表示链路质量。只有链路质量高于阈值θ，该条链路才存在。因为每个节点在一个周期内只有一个工作时隙，为避免延迟过大，设定重传不能超过2次。图1所示的模型中有三种传输方法：

1、A到B，期望传输成功率和时延期望值分别为：

2、A到C，期望传输成功率和时延期望值分别为：

3、A到D，期望传输成功率和时延期望值分别为：

本文所要解决的问题是如何用较少的节点能量消耗来满足端到端的延迟约束要求。根据传输能耗研究[9]，链路质量反应了数据传输的能量消耗成本。该问题可以转换为一个优化问题，目标是节点增加最少数量的工作时隙slot_num，约束条件是端到端延迟dij满足给定的时延约束Δ。该优化问题可以用式(1)(2)(3)(4)描述。

Φ+Ψ=1

(1)

ETRij≥θ

(2)

min(Φ*EDRij+Ψ*100/ETRij)

(3)

min(slot_num)

(4)

式(1)和(2)表明我们需要综合考虑期望传输成功率和期望时延这两个因素来选出一条最优路径。期望传输成功率因素会优先选择链路质量好的路径，而期望时延因素优先选择等待时延最低的路径，两者在目标实现上可能会存在冲突。为此我们根据具体的网络环境分别给期望传输成功率和期望时延分配不同的权重Φ和Ψ。在式(2)中，如果选定的传输方式的期望传输时延小于这个阈值，则需要增加节点苏醒时隙。但是一味地增加时隙，会导致节点的能量过多地消耗，降低节点的寿命，因此尽量少地增加时隙。

在图1所示的传输模型中，节点A在上一层节点中有B, C和D，链路LAB，LAC和LAD对应的期望传输成功率分别为0.78，0.94和0.88，对应的时延期望值分别为80.76，97.74和107.67。三条传输路径的时延期望值均满足式(2)中的约束条件。根据式(4)三条路径的计算结果分别为1.19，1.11和0.92，取最大值，即可得出这三条传输路径中的最优选择。

将选中路径的期望传输时延与期望传输时延阈值进行比较。若期望传输时延高于阈值，则需要增加时隙，增加时隙之后，节点在一个周期内可以苏醒2次，传输过程中的等待时延就会大大降低，数据的传输时延也会大大的降低。

在节点C的一个周期T上增加一个时隙。如图2所示。

图2 增加时隙后的传输模型

增加时隙后：

增加一个时隙之后，传输时延由原来的80.76降为现在的15.76。此时，由于节点在一个周期内苏醒2次，则三个周期最多可以传输6次。我们可以进行多次传输，这样可以增大期望传输成功率，减少丢包率。因此，增加一个时隙能够很好的解决低占空比无线传感网络中的时延问题。DEtoERA路由算法：见表1所示：

据调查，全市3个规模为100亩左右的粮食家庭农场，稻麦两熟一年纯收入约8-12万元，家庭农场盈利能力明显高于普通农户。而部分流转面积在200亩左右，以经营秧草、蔬菜、花木等设施农业为主的农地合作社，盈利能力比以种粮为主的家庭农场还要更高些，除通过项目获得国家财政补助外，其经营性收入每亩地每年可净赢利1500元左右。

表1 DEtoERA路由算法

输入：无线网络模型G=(V，E)；权重系数Φ，Ψ；阈值Δ．输出：最低时延传输路径Rmin．1．以汇聚节点S为根，通过BFS算法将节点V进行分层；2．从源节点A开始，计算其到邻居节点的EDRij和ETRij；3．排除不满足传输成功率阈值的传输路径；if(ETRij<θ)删除该Pij；4．计算每条路径的优化函数：Φ∗EDRij+Ψ∗ETRij，取最小值获得最优传输路径；5．对于选出的路径Pij，if(EDRij>Δ)，增加一个时隙slot，重新计算路径时延是否满足阈值，如果满足约束条件则停止增加时隙；6．最低时延传输路径Pmin为最终的传输路径。

4 仿真实验与性能评价

在本节，我们将通过仿真实验来验证DEtoERA算法的各项性能，通过各项性能指标将其与ESL算法来对比分析。

4.1 评价方法

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

(1)数据单跳传输时延：在无线传感网络中，节点间数据传输是沿跳数逐渐减少的方向，本文主要考虑数据传输到下一跳节点的时延。

(2)网络寿命:从仿真开始到网络中节点因能量耗尽而被废弃的节点的数量超过30%所持续的时间。

4.2 仿真实验参数

表2 仿真平台参数

平台参数取值节点个数100个链路质量40%—95%节点周期100s节点时隙1s单次传输耗能1节点总能量50000

4.3 网络性能仿真评价

在不同占空比条件下对DEtoERA算法的传输时延和网络生命进行仿真模拟。

低占空比无线传感网络中，传输时延与节点的占空比有着很大的关系，占空比越大，则节点的工作时隙越多，传输时延越小。

图3 节点占空比和传输时延

图3显示了两种算法的延时期望随着节点占空比变化的变化曲线。由仿真结果可知，节点的占空比从 1%变化到 5%。随着占空比的增加，两种算法的平均端到端延迟均显著地降低，但DEtoERA算法的平均端到端时延一直保持最低，尤其是在占空比很低的情况下。

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

图4 节点占空比和网络寿命

图4显示了两种算法的网络寿命随着节点占空比变化的变化曲线。根据仿真结果可以看出，网络的生命周期随着节点占空比的增大而减少，但基于DEtoERA算法的网络寿命始终保持着优势，尤其是在占空比很低的情况下，这是因为ESL算法采用寻找备选节点传输的方式，但这种方式一旦遇到较低的链路质量时，重传次数增大，也浪费更多的能量。而DEtoERA算法在选出最优传输路径的基础上考虑是否需要增加时隙，这样可以在保证延时较低的基础上节省了能量，所以DEtoERA算法更能延长网络的寿命。

5 结束语

本文针对低占空比无线传感网络存在节能和时延问题提出了一种新颖的算法(DEtoERA)。该算法通过计算不同传输路径的期望时延和期望传输成功率来挑选出最佳传输方式，并在选出最佳传输方式的基础上考虑是否需要增加时隙减少延时。仿真实验结果表明本算法相比ESL算法能更好的节省能量和降低延时。

[1] 毕玉婷，陈 昕. 低占空比无线传感器网络能量感知路由算法[J].北京信息科技大学学报, 2012, 27(6): 93-98.

[2] Mote battery life calculator[EB/OL]. http://www.xbow.com/Support/wAppNotes.aspx,2013.01.05

[3] 李燕君，孙扬. 低占空比传感网的端到端延迟控制方法[J]. 中南大学学报(自然科学版),2013(7): 171-175 .

[4] 陈权，高宏. 低占空比无线传感器网络中基于动态切换的实时路由协议[J]. 通信学报,2015, 36(10): 224-234.

[5] Zuzhi Fan. Delay-Driven Routing for low-duty-cycle sensor networks[J]. International Journal of Distributed Sensor Networks,2013：1-11

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

[7] 段轶, 吴小兵, 陈贵海. 低占空比无线传感器网络中的动态数据传输协议[J]. 计算机研究与发展, 2011(s2):145-151

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

[9] Zhen Xu, Gao Lu. Energy-efficient and QoS-aware routing protocol for wireless sensor networks[C].In Proceedings of 7th International Symposium on Wireless and Pervasive Computing,2012:1-5.

[10] 刘娅,石雄. 基于高速公路的无线传感网络简单串行通信协议的设计[J]. 武汉工业学院学报, 2011,30(1): 52-54.

[11] Zuzhi Fan, Shi Bai, et al. Delay-bounded transmission power control for low-duty-cycle sensor networks[J]. IEEE Transactions on Wireless Communications, 2015,14(6): 3157-3170

[12] Zhong Shen, Hai Jiang, et al. Fast data collection in linear duty-cycled wireless sensor networks[J]. IEEE Transactions on Vehicular Technology, 2014,63(4):1951-1957

An energy saving and low-latency scheduling algorithm in low-duty-cycle WSN

XU Zhen , YANG Lei, ZHOU Long

(School of electrical and electronic engineering, Wuhan polytechnic university，Wuhan 430023, China)

Low duty cycle of wireless sensor networks can be effective to improve the life of node in the network. But it brings some problems, such as a longer waiting delay. In addition, as a result of the unreliable link quality, some data need to be transported for many times, so it is not only waste of energy, but also have a long time delay. To solve this problem, a novel algorithm (DEtoERA) by calculating of time delay of different transport modes and transfer rate to select the best transmission mode has been raising. Saving energy under the satisfying the requirement of time delay. The simulation results show that compared with the ESL algorithm, this algorithm can better save energy and reduce the delay.

wireless sensor networks; Low Duty Cycle; energy; delay

2016-10-15.

徐震(1974-)，博士，副教授，硕士生导师，E-mail:390667859@qq.com.

杨蕾(1979-)，博士，副教授，E-mail:31477715@qq.com.

国家自然科学基金(61373091)

2095-7386(2016)04-0073-05

10.3969/j.issn.2095-7386.2016.04.014

TP 393

A