基于Quorum的低占空比WSNs最优延迟可靠路由算法

张长森 胡宇鹏 陈鹏鹏

(河南理工大学计算机科学与技术学院 河南 焦作 454000)



基于Quorum的低占空比WSNs最优延迟可靠路由算法

张长森 胡宇鹏 陈鹏鹏

(河南理工大学计算机科学与技术学院 河南 焦作 454000)

在无线传感器网络中，异步低占空比技术可以极大地降低能耗，但是由于节点的低占空比唤醒会造成极大的端到端数据时延。针对这个问题提出一种基于Quorum的异步自适应低占空比路由算法ORDA(Optimal-Reliable delay routing algorithm for low duty cycle WSNs based on Quorum)，将异步占空比网络和实际链路模型相结合，在异步占空比网络中节点在不同时刻的邻居发现延迟也在不断变化。首先为每个节点根据网络负载选择自身的Quorum类型，并利用Quorum特性来计算邻居节点的重叠时隙个数；然后根据链路质量进一步计算出这一跳范围内邻居节点间的成功转发预期值，并在即将唤醒的节点中选择更可靠的节点转发数据。仿真实验证明，该算法不仅能够降低端到端延迟，而且能获得很好的转发成功率。

无线传感器网络 低占空比 延迟 Quorum 链路质量

0 引 言

无线传感器网络WSN综合了无线通信技术、传感器技术、嵌入式技术和分布式信息处理技术，是目前国际上前沿热点研究领域。在WSN中，传感器节点往往由于体积小、能量有限以及在实际应用过程中的环境因素等影响而不易更换电池，因此能量是WSN中的珍贵资源。低占空比WSN能够高效地减少节点的能耗，可扩展性强，而且容易实现。然而低占空比会导致很严重的邻居发现延迟[1]。

占空比是无线传感器网络中一种节省能量的技术。在低占空比网络中，节点保持唤醒很短一段时间，其余大部分时间都处于休眠状态。在异步占空比无线传感器网络中，节点的低占空比唤醒将导致邻居发现延迟随时间的改变而改变，即在不同时刻两个邻居节点间的发现延迟是时变的[2,3]。

在WSNs中，多跳数据路由已经受到越来越多的关注，很多不同的路由算法被设计用来优化WSNs网络的性能。例如基于地理位置的路由GPSR中[4]，节点知道自己的地理位置，数据包发送时节点选择距离最远的邻居节点转发，以此来达到最小跳数传输。文献[5]提出的ExOR能够在很大程度上提高数据包转发率，但是由于其以全网链路状态为基础，因此网络中每个节点需要定期向全网广播自己邻接链路的ETX值，带来较大的网络负担。这几种方法都是在假定一跳的传输延迟是静态固定的，对于低占空比无线传感器网络是不适用的[6]。

在另外的一些路由协议中，路由路径是随时间改变的。文献[7]介绍了一种动态路由机制DSF，综合考虑了包发送率、端到端时延和能量消耗。虽然表现出了良好的性能，但是工作在同步占空比下，需要消耗大量能量来用于节点的时钟同步。文献[8]中提出的DESS算法是基于链路质量较好的网络，为了减少数据包传输延迟，每次重传都是选择最早醒来的节点作为中继节点。其不足之处在于WSN中链路质量往往是不稳定的，因此最先醒来的节点可能是链路质量差的节点。

在本文之前的工作中，提出一种非对称Quorum的邻居发现机制。实验表明，Quorum-based协议是最适合用于解决异步、自适应WSN的协议。因此本文利用基于Grid Quorum的方法，设计一种在异步占空比WSN网络中的最优可靠延迟路由算法ORDA。该算法能够解决以上文献中提出的路由算法中存在的诸多缺陷。采用Quorum机制可以在保证网络连通性的前提下使节点能够根据之前的网络负载来自适应选择不同的Quorum唤醒时隙，以此来减少信息量少的节点的唤醒时隙数；在异步占空比网络中，可以避免全网节点时间同步所带来的能耗；在选择下一跳节点时综合考虑了邻居发现延迟和数据发送成功转发预期(链路质量)。

1 系统模型

1.1 网络模型

假设网络中有N个同构的传感器节点，传感器节点分为两种类型：簇首和簇成员节点。每个节点都有两种状态：活跃和休眠状态。当一个节点处于活跃状态时，它可以感知周围的环境、接收和发送数据包。当一个节点处于休眠状态时，会把除了用于唤醒的计时器之外的所有功能模块全部关闭[9]。一个节点只有在处于唤醒状态时才能接收数据包。所有节点之间不需要时间同步，同时具有一定的数据缓存能力。

网络规模足够大，而且密度较高，区域没有边界效应；除sink节点外所有节点均同构；节点具有位置感知模块，能够感知自身的相对位置信息；数据突发性较强，数据流量不高，发生碰撞概率不大；数据包长度较小，因而忽略传播时延和处理时延。

1.2 Grid Quorum机制

本文选择文献[10]中提出的基于质数网格的Quorum能量节省模型，Quorum分为两种：A-Quorum和S-Quorum。假定网络中所有节点会根据网络的拥塞情况、通信量和时延要求等自适应地选择不同的Quorum类型，以此来实现非对称性。

2 最优延迟可靠路由算法

在异步低占空比无线传感器网络中，两个节点间的邻居发现延迟是随时间改变而改变的。本文采用文献[13]中的方法计算动态的邻居发现延迟。最优延迟可靠路由算法ORDA分为三个过程：邻居发现、计算重叠时隙和成功转发预期值。

2.1 邻居发现

假定网格不采用时间同步，根据网络模型可知，簇首节点之间、簇首节点与成员节点必须保证能够邻居发现，而成员节点之间则不必相互发现。在文献[12]中已经证明在质数Quorum中任意两个节点无论是分别采用A-Quorum和S-Quorum，还是均采用S-Quorum，在有限个时隙内一定能够完成邻居发现，如图1所示[11]。

图1 邻居发现示意图

(1)

(2)

其中，Ti和Tj分别为节点i和j的时隙长度。

2.2 计算重叠时隙

在本文中，网络中的节点根据网络负载自适应选择Quorum类型。当节点检测到网络负载较大，超过预先设置的一个阈值时，表示节点目前的通信量较大，因此采用S-Quorum选择唤醒工作时隙；否则节点采用A-Quorum选择唤醒工作时隙。

在每轮的初始阶段中，每个节点更新自身的邻居节点集和邻居节点唤醒时隙集，然后计算邻居节点集中的所有邻居节点与自身节点在一个周期内的重叠时隙个数。

节点A与节点B1、B2的重叠时隙个数计算过程如下：

图2 节点的唤醒时隙图

由图2可知，节点A的唤醒时隙是{0，1，2，4，7}，节点B1的唤醒时隙为{0，3，6}，节点B2的唤醒时隙是{1,4,6,7,8}。

节点B1在开始阶段向节点A发送一个消息数据包，包含节点B1的唤醒时隙{0，3，6}。节点A接收消息数据包后，可知节点A和B1的重叠时隙只有一个:{0}。同理，节点A和B2的重叠唤醒时隙有三个：{1，4，7}。

2.3 最优延迟可靠路由选择

本文提出的最优延迟可靠路由算法中，算法包含两部分，分别为邻居发现时延和成功转发预期值。当发送节点在有数据需要发送时，首先计算在该时刻所有邻居节点中比发送节点等级更低的节点作为候选转发节点，根据唤醒的先后和在一个周期内成功转发预期值来选择出最终转发节点。

2.3.1 在一个周期内能够成功转发的预期值

在WSNs中，无线链路的一跳传输是不可靠的。因此在寻找最短链路时间路径时必须考虑一跳传输失败的情况，一旦发送失败，发送节点则需要等到两个节点的下一个重叠时隙内才能继续发送数据。若两个节点在一个周期内只有一个重叠时隙，则需要等待一整个周期之后才能再次发送；即使两个节点有多个重叠时隙，若重叠时隙间隔较大，同样会造成较大的延迟。为了解决这个问题，本文根据两个节点之间的重叠时隙个数和无线链路质量，提出一个周期内两个节点成功转发预期值Ei,j，用来表示在链路(i,j)上，节点i成功将数据发送给节点j的预期。成功转发预期值就是两个节点在一个周期内转发数据的所有可能情况之和，预期值越大，表明在一个周期内能够重传的次数越多，能够成功转发的可能性越大。

(3)

则节点A在一个周期内能够成功转发的期望延迟为EA,B：

(4)

根据以上公式可以看出，两个节点间的成功转发预期值既考虑到了两个节点间的重叠时隙个数，即两个节点间能够转发数据的时隙数，又考虑到了两个节点间的链路质量。因而对于网络链路质量低的网络，能够在降低传输延迟的同时选择更可靠的节点作为中继节点。

举例说明：

例如簇首节点A和B2、成员节点B1分别采用图2中(a)、(b)、(c)中的唤醒时隙。由2.2节可知，节点A和B1在一个周期内的重叠时隙有{0}，节点A和B2在一个周期中有重叠时隙{1，4，7}。节点A和B1、B2之间的链路质量分别为P1和P2。

因此节点A在一个周期内成功向节点B2发送数据的成功转发的期望为EA,B2：

2.3.2 最优延迟可靠路由选择

在最优延迟可靠路由(ORDA)选择中，所有传感器节点都维护两个关于邻居节点的集合，即邻居节点集Ni和邻居节点唤醒时隙集NWi。用2.1节中的方法将无线传感器网络构建为一个有向图G=(V,E,C)。在全网初始阶段，∀(i,j)∈E，计算在t0时刻C={Δi,j(t0)|(i,j)∈E}。

节点的邻居节点集Ni和邻居节点唤醒时隙集NWi更新过程如下：

在网络初始化阶段，每个节点在网络运行前根据网络负载自适应地在一个n×n的Quorum中选择自己在本轮运行中的唤醒时隙Wi。包含sink节点在内的所有节点将自身的节点等级设置为0，sink节点在一跳范围内发送一个节点等级数据包，包含一个节点等级Node Level=1、发送节点ID和发送节点的唤醒时隙集Wsink。一跳范围内的所有节点ni接收到等级数据包后，根据数据包中的Node Level来更新自身的节点等级。将sink的ID和唤醒时隙集Wsink分别加入节点ni的邻居节点集Ni和邻居节点唤醒时隙集NWi中，然后将节点等级Node Level加1，以及节点ni的ID和唤醒时隙集Wi替换数据包中原有的信息，并在一跳范围内转发出去。

若一个节点ni接收到多个数据包时，将所有数据包中最小的节点等级Node Level设置为自身的等级，并按照以上过程更新自身信息。对于其他接收到的数据包，若发送节点ID没有在邻居节点集中，则节点仅将发送节点ID和发送节点唤醒时隙集分别加入自身的邻居节点集Ni和邻居节点唤醒时隙集NWi；否则，节点ni丢弃该数据包，以此来避免数据包重复发送。

最优延迟可靠路由选择过程：

根据邻居节点唤醒时隙集NWi中候选转发节点与发送节点ni的重叠时隙个数和时隙标号，利用2.3.1节中介绍的成功转发期望来计算在一个周期内节点能够成功转发的期望，假设为Ei,j、Ei,a和Ei,s。成功转发预期值E越大，表示根据两个节点间的链路质量，在一个周期当中可以转发的次数越多，能够成功转发的可靠性更高。

Input:Ni,NWi

Output:CNi

Forj=1 tondo

ifnj∈Nithen

if NodeLevel(nj) < NodeLevel(ni)

then

CNi←nj

calculateEi,jformnitonjin one period using equation (4)

end if

end if

end for

returnCNj

Input:CNi

Output:the optimal and reliable forwarding node opl

min1←∞

min2←∞

Number1←0

Number2←0

forj=1 tondo

ifnj∈CNithen

Number1←nj

Number2←nj

end if

end if

end for

opl= min{Ei,min1,Ei,min2}

return opl

3 仿真实验以及性能分析

为了更好地证明ORDA算法对于网络性能的提高，在本节中将对不同规模下的ORDA的性能和ExOR[5]、DESS[8]的性能进行对比分析。实验参数如表1所示。每个节点随机地产生数据包。实验采用文献[14]中的无线损耗模型。在实验中，端到端延迟是指数据包从源节点发送到汇聚节点接收之间的时延。实验对比了不同参数下的算法性能，如不同的区域大小、节点密度和网络链路质量。仿真结果为每个实验在相同的参数下重复运行10遍。

表1 实验参数

图3给出了在相同的节点密度、不同网络区域大小下三种算法的平均端到端延迟。算法在矩形区域边长从100到300时，网络区域中节点数从200个依次增加来保证节点密度保持一致。从图3中可以明显看出，由于区域大小的增加导致端到端的距离增加，因而算法的端到端延迟随着区域的增加而增加，但算法ORDA始终优于ExOR和DESS。这是因为在算法ORDA中，节点选择下一跳中继节点时，始终从最先醒来两个候选邻居节点中选择最终下一跳节点。这样在区域增大的情况下，始终保持最优或次优的单跳邻居发现延迟。

图3 不同区域大小下的平均端到端延迟

在图4中，网络的区域大小保持不变，即200×200，但网络中的节点数不断增加，即网络中节点密度不断增大。从图4中可以看出，随着节点密度的增加，三种算法的平均端到端延迟不断降低。ORDA算法在节点数为500之前明显低于其他算法，之后ORDA算法和DESS算法比较接近。这是由于当节点密度小时，ORDA算法中节点会选择在一个周期内成功转发预期值大的作为下一跳，可以在降低每一跳延迟的基础上保证单跳的传输成功率，减少重传造成的延迟。而随着节点密度的增加，节点的邻居节点数增加，可以作为下一跳的中继节点增加，即使单次传输失败，重传造成的延迟不会太大，因而算法DESS渐渐接近ORDA。

图4 不同节点密度下的平均端到端延迟

无线网络的链路质量往往不稳定，因此对比了算法ORDA、ExOR和DESS在不同的网络链路质量下的时延性能，如图5所示。明显可知，算法ORDA在平均链路质量较低的网络中仍能保持远优于算法ExOR和DESS的端到端延迟。这是由于算法ORDA在选择中继节点时根据链路质量和重叠时隙个数计算出一个周期内两个节点能够成功转发的预期值，一直选择预期值最大的作为中继，因而在链路质量低的网络中能够提高转发成功率，减少延迟。当网络的链路质量超过0.9后，此时网络中的单跳转发成功率很高，因而基于最优链路的算法DESS更优。

图5 不同网络链路质量下的平均端到端延迟

图6显示了随着节点数的增加，三种算法的网络生存时间的变化。从整体上比较，算法ODRA和DESS在生存时间上都要低于算法ExOR。这是由于算法ExOR是一种以端到端最短路径的ETX值为基准的路由算法。但是仍能看出，算法ORDA的网络存活时间仍高于算法DESS。这是由于算法ORDA采用异步低占空比，没有全网同步所带来的网络负担，而且算法对所有节点进行分级，选择下一跳中继节点时一直从等级小于自身的邻居节点中寻找。

图6 网络中不同节点数量下的网络生存时间

4 结 语

在无线传感器网络中，最迫切的问题就是怎样在能量受限的情况下降低时延、提高网络传输效率等。本文针对异步低占空比WSNs，提出一种基于Quorum的最短延迟路由算法ORDA。根据Quorum的特性提出一种方法，根据重叠时隙个数和链路质量来计算数据包在一个周期内成功转发的预期值，以此来选择可靠性最高的节点中继。在减少网络传输延迟的同时，在数据传输过程中选择成功转发的预期值最大的节点作为中继节点，这样既减少了网络中数据包重传次数，又提高了节点间传输成功率。实验结果分析表明，算法ORDA相比于ExOR，虽然在节省能耗方面有不足，但是在减少传输延迟性能上远远优于ExOR。即使相对于算法DESS，算法ORDA不仅在网络延迟上更加高效，而且在链路质量低的网络中拥有更好的时延性能。下一步工作是解决基于Quorum机制的异步占空比WSNs中的自适应问题，使节点能够自适应地通过改变循环长度改变自身的占空比，以及如何将其运用到多汇聚节点的网络中，使得算法能够更加节能、更加切合实际应用场景。

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

[2] Polastre J,Hill J,Culler D.Versatile low power media access for wireless sensor networks[C]//Proceedings of the 2nd international conference on Embedded networked sensor systems.ACM,2004:95-107.

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

[4] Karp B,Kung H T.GPSR:Greedy perimeter stateless routing for wireless networks[C]//Proceedings of the 6th annual international conference on Mobile computing and networking.ACM,2000:243-254.

[5] Biswas S,Morris R.ExOR:opportunistic multi-hop routing for wireless networks[J].ACM SIGCOMM Computer Communication Review.ACM,2005,35(4):133-144.

[6] 徐丹,陈晓江，黄骏杰，等.基于低占空比的机会汇聚树路由协议[J].计算机应用,2013,33(12):3394-3397.

[7] Hao J,Zhang B X,Mouftah H T.Routing protocols for duty cycled wireless sensor networks:A survey[J].IEEE Communications Magazine,2012,50(12):116-123.

[8] Lu G,Sadagopan N,Krishnamachari B,et al.Delay efficient sleep scheduling in wireless sensor networks[C]//24th Annual Joint Conference of the IEEE Computer and Communications Societies.IEEE,2005,4:2470-2481.

[9] 王俊美.低占空比无线传感器网络异步邻居发现算法研究[J].数字通信,2013,40(2):36-39.

[10] 陈良银,颜秉姝,张靖宇,等.移动低占空比传感网邻居发现算法[J].软件学报,2014,25(6):1352-1368.

[11] 杨璐.一种基于Quorum系统的异步传感网局部时间分配算法[J].东南大学学报:自然科学版,2013,43(1):6-11.

[12] 刘微姗,陈晓江，段任，等.DRAD:一种基于异步休眠调度的无线传感器网络数据收集协议[J].计算机工程与科学,2010,32(11):40-43，51.

[13] Lai S W,Ravindran B.Least-latency routing over time-dependent wireless sensor networks[J].Computers,IEEE Transactions on,2013,62(5):969-983.

[14] 王辛果,张信明,陈国良.时延受限切能量高效的无线传感网络跨曾路由[J].软件学报,2011,22(7):1626-1640.

OPTIMAL-RELIABLE DELAY ROUTING ALGORITHM FOR LOW DUTY CYCLE WSNS BASED ON QUORUM

Zhang Changsen Hu Yupeng Chen Pengpeng

(CollegeofComputerSienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

In wireless sensor networks,asynchronous duty cycle technique can significantly reduce energy consumption.However,a high end-to-end time delay is caused by low-duty-cycle networks.Therefore,an Optimal-Reliable delay routing algorithm for low duty cycle WSNs based on Quorum(ORDA) is proposed to solve the problem.This algorithm combines the asynchronous duty cycle networks with the actual link,and the neighbor discovery delay of each node is constantly changed at different time.Firstly,each node chooses its own quorum type according to the network load and calculates the overlapping time slots numbers of neighbor nodes by the quorum characteristics.Then,the expected value of successful forwarding between neighbor nodes is computed with the link quality,and the more reliable node is chosen as a forwarding node.The simulation experiments show that the algorithm can not only reduce the end-to-end delay,but also obtain a high forwarding success rate.

Wireless sensor network Low duty cycle Delay Quorum link quality

2015-08-04。国家自然科学基金项目(51174263)；教育部博士点基金项目(20124116120004);省部级项目(142300410144)。张长森，教授，主研领域：矿井监控与通信，无线传感器网络。胡宇鹏，硕士生。陈鹏鹏，硕士生。

TP393

A

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