无线传感器网络中双信道无信标实时路由协议

黄超

（广东技术师范学院计算机科学学院，广州　510665）

无线传感器网络中双信道无信标实时路由协议

黄超

（广东技术师范学院计算机科学学院，广州510665）

0　引言

无线传感器网络是由部署在监测区域内大量的传感器节点通过无线通信方式形成的一个多跳的自组织网络系统，可广泛应用在环境监测、国防军事、医疗健康以及抢险救灾等领域［1］。某些事件驱动的应用对无线传感器网络数据传输的实时性提出了较高要求，例如在森林防火等事件驱动应用中，火警事件的发生会使得网络中感知数据将瞬间剧增，产生的网络拥塞和冲突会增加感知信息的传输时延，导致异常高温信息无法实时有效地传送到监测中心。由此可见，事件驱动等高负载网络环境给无线传感器网络的实时性研究提出了更高的挑战。

现有的实时路由协议［2］主要采用传统的地理路由模式，使用周期性信标广播来建立邻居节点的位置、能量和延迟等相关信息的邻居表。尽管信标广播能够获取邻居节点的准确信息，但也带来一些不足：①能耗较高：额外的信标广播会耗费更多的能量；②通信开销较大：所有节点都需要定期广播信标，增加了网络通信开销；③邻居表信息利用率低：路由选择中往往只需从邻居表中选择一个或极少数节点参与路由转发，邻居表信息的利用率很低，而且保存大量未参与路由转发的邻居信息还会增加节点存储开销；④不适合动态性网络：当网络拓扑变化较强时，邻居表的准确度将降低，而为维护邻居表信息的准确性，节点需要更频繁地广播信标，增加能量消耗和网络延迟；⑤高负载网络中信标广播会加剧网络冲突；⑥网络节点大规模密集部署时，信标方式的上述不足将变得更加严重。因此，现有实时路由协议通常以牺牲能量来换取实时性保证，这与能量高效的首要设计目标存在直接矛盾。

为克服传统地理路由因邻居表信息不准确而导致能耗高，代价大的问题，研究人员提出了基于竞争的无信标转发［3］，它的基本思想是发送节点广播竞争请求，邻居节点接收到请求后根据自身状态来决定参与竞争的等待响应时间，只有等待响应时间最短的邻居竞争成为转发节点。基于竞争的无信标转发方式可以在没有邻居节点先验信息情况下，让节点以能耗低、开销小的方式选出下跳接收节点。在竞争选择转发节点的过程中，无信标转发不需要任何信标就可以获取所选定邻居的信息，如果能够将每次竞争所选择的节点信息保存到邻接表，就可以利用这些局部信息辅助实时路由决策。由此可见，通过无信标转发建立邻接表的方式可以完全克服信标方式能耗高、代价大的缺点。

基于上述想法，本文提出了双信道无信标实时路由协议 DBRR （Dual-channel Beaconless Real-time Routing），它的基本思想是在数据转发的初始阶段（即源节点第一个DATA包的发送），每个节点通过竞争机制选择其下跳转发节点，同时将已选中节点的信息保存在邻居表中；在后续的路由过程中，节点根据邻居表中是否有满足实时性要求的邻居节点，采用无信标转发和邻居表相结合的转发策略，使用单跳间的速率约束和延迟约束来满足端对端实时性要求。DBRR只有在邻居表中没有节点满足实时性要求时才发起竞争，选择新邻居作为转发节点并加入邻居表中，具有能耗低、开销小、邻居表信息利用率高等优点。此外，为缓解高负载网络拥塞和冲突，DBRR采用择数据信息和控制信息隔离传输的双信道并行传输方式，避免控制信息和数据信息的冲突，不仅可以节约能量，还可以减少网络数据的传输延迟，提高传递成功率，更好地满足高负载网络下的实时性需要。

1　相关工作

实时性是当前无线传感器网络服务质量究的重要内容。SPEED［4］采用无状态非确定地理转发的SNGF机制，优先选择满足速率要求且负载较轻的邻居节点作为下跳转发节点，为端对端路由提供软实时保证。MMSPEED［5］对SPEED进行了拓展，为多种业务提供区分服务支持以及实时性和可靠性保证。QGR［6］采用分级排队模型为图像传感器网络中周期性低带宽和事件驱动高带宽两类数据分配不同级别，以高优先级别保证事件驱动的图像信息传输的实时性和能量高效。PRTR［7］利用多路径传输方式缓解网络拥塞，为实时数据流提供更好的实时性传输。

无信标转发在能量效率和通信代价方面有较好优势。IGF［8］采用lazy binding思想来处理网络动态变化，它采用DRA扇形转发区域，候选转发节点根据自身离目标节点的增进距离以及剩余能量来决定竞争的等待响应时间。OGF［9］针对拓扑变化不剧烈的网络，提出了竞争机制和邻居表相结合的按需转发策略，但OGF邻居表只保存一个转发节点信息，没有充分利用每次选出的转发节点信息，也没有提供实时性保证。CBRR［10］基于包接收率模型，充分利用无信标转发和协作通信的优势，完全避免冗余探测包的使用，并通过等待响应时间设定、协作节点概率保证以及冗余数据包发送等方式实现单跳数据传输的可靠性保证。

IEEE 802.11［11］等单信道协议大多使用RTS/CTS握手机制来解决隐终端问题［12］，然而仅用握手机制不仅不能消除所有冲突，还会引起暴露终端问题，导致信道利用率下降。为克服单信道的不足，研究人员提出了双信道MAC协议来解决隐终端问题。DBTMA［13］通过BTs和BTr两个忙音信号 （Busy Tone）将收发状态通知邻节点，有效地减轻数据包的冲突。DUCHA［14］采用双信道和忙音解决了包括隐终端和暴露终端在内的若干问题，彻底避免数据包的冲突和重发；CORA［15］利用双信道通信模式降低信道竞争过程中数据碰撞和多播抑制概率；再使用最大感染球策略压缩蚁群寻路范围，降低网络寻路能耗。

2　双信道无信标实时路由协议（DBRR）

DBRR采用无信标转发和邻居表相结合的转发策略，使用单跳间的速率约束和延迟约束来满足端对端的实时性要求。DBRR将无线信道划分为控制子信道和数据子信道，采用ERTS（DRTS）-ECTS-DATA-ACK握手机制选择转发节点，控制子信道用于传递ERTS、DRTS和ECTS等控制帧，其中ERTS是在RTS的基础上增加了当前转发节点和目标节点的位置信息以及所要求的延迟约束，DRTS在ERTS的基础上再增加了有效邻居节点ID号，ECTS是在CTS的基础上增加了发送CTS节点的位置信息；数据子信道传输DATA和ACK等数据帧。DBRR通过双信道传输策略，不仅可以避免控制帧和数据帧的冲突，还可以并行传送控制帧和数据帧，减少延迟。

源节点和目标节点分别用S和D表示，d（i，j）表示节点i和j之间的欧氏距离，表示节点i和j之间的单跳延迟，Deadline（D）为目标节点D对数据的截止时刻，Rc为节点的通信半径。

邻居节点集NSi（Neighbor Set）：位于节点i通信范围内的节点集，即满足NS=｛j|d（i，j）≤R｝。

实时性速率SpeediD：满足实时性约束的速率，为节点i与目标节点D间的距离与当前截止剩余时间的比值，即SpeediD=d（i，D）/（Deadline（D）-Tnow），其中Tnow为当前时刻。

候选转发节点集FCSi：节点i的候选竞争节点集中满足实时性速率要求的节点集，即：

估计跳数HopiD：节点i到目标节点D的估计跳数，为节点i和目标节点D的距离与通信半径之比，即HopiD=d（i，D）/Rc。

延迟约束：无信标转发采用延迟约束来决定候选竞争节点能否参与竞争。若候选竞争节点的邻居表中存在一跳延迟不小于实时性单跳延迟DelayiD的邻居节点，则该候选节点可以参与竞争；否则，该候选节点将不能参与竞争。

此外，本文做出以下合理假设：①节点位置已知；②节点分配有唯一 ID；③节点装配有忙音（Busy Tone）；④节点的通信半径和初始能量均相同。

双信道并行传输的基本思想是：节点在数据子信道接收上跳节点发送的DATA包时，同时在控制信道中广播ERTS/DRTS选择新的下跳转发节点。

在IEEE 802.11中，RTS、CTS和ACK的帧长度分别为44bytes、38 bytes和38 bytes，假设DATA包的大小为data_size，控制子信道带宽为bw_control，数据子信道的带宽为bw_data。对于非源节点，双信道经过一轮RTS-CTS-DATA-ACK握手机制所需的时间T为：

由此可见，当控制信道和数据信道的带宽固定时，DATA包的大小是影响T的关键因素。假设总带宽为2Mbps，控制子信道带宽为0.4Mbps，数据子信道为1.6Mbps，则当DATA包大于300bytes时，数据信道传送DATA和ACK`的时间将大于控制信道中RTS和CTS的传送时间。以此可见，对于DATA较大的传送，双信道并行传输可以减少延时。

DBRR的转发策略与当前发送节点的邻接表密切相关：

（1）直接转发方式：当邻接表中有满足速率约束的有效邻居节点时，发送节点广播发送DRTS帧，只有与DRTS中有效邻居节点ID号相同的节点成为转发节点并在SIFS时间后发送ECTS；发送节点收到ECTS后，在数据子信道中向转发节点发送DATA包并发送忙音信号抑制其它候选节点参与转发竞争；同时转发节点在控制子信道中发起它的新一轮转发节点选择。

（2）无信标转发方式：当邻接表中没有有满足速率约束的有效邻居节点时，将采用延迟约束保证实时性。发送节点广播发送ERTS帧，如果候选竞争节点的邻接表为空，则该候选竞争节点将在Tlong时间后发送ECTS；若候选竞争节点的邻接表中存在满足延迟约束的邻居节点时，该候选竞争节点将在Tshort时间后发送ECTS；否则表明无满足实时性要求的竞争节点，丢弃DATA包。Tlong和Tshort的计算参照2.4。

竞争优先级函数是基于竞争无信标转发策略的关键，它决定了邻居节点的等待响应时间。优先级函数中的参数可根据应用的需要来设定，为满足实时性和能量高效的要求，本文综合考虑排队延迟、传播延迟和能量，建立增进距离、剩余能量、队列中排队包的数量以及随机数为参数的竞争函数：

其中pi为邻居节点的优先级；di为当前转发节点到目标节点的欧氏距离与节点与目标节点的欧氏距离之差；Rc为节点的通信半径；Ei和Et分别为节点的当前剩余能量和初始能量；qi和Qt分别为当前队列中排队包的数量和队列总大小；ri为0～1间的随机数；α、β、γ和η分别为距离、能量、队列和随机数的权值并且满足α+β+γ+η=1。

无信标转发策略中的短等待时间和长等待时间设置如下：

其中SIFS的值由802.11 DCF中定义为10μs。由（3）和（4）知，短等待响应时间Tshort不小于长等待响应时间Tlong。

本文采用与SPEED相似的延迟估计方法，由当前转发节点记录包进入队列的时间Tarrive和接收到ACK的时间TACK，当前单跳延迟即为TACK和Tarrive之差，另外单跳延迟还需要综合考虑历史单跳延迟的影响，因此单跳延迟定义如下：

邻居表是由节点在竞争转发资格的过程中动态建立，它用于保存每次竞争所选择的邻居节点信息。在数据转发的初始阶段，所有节点的邻居表都为空，在后续的转发过程中，只有节点的邻居表中没有满足速率约束的邻居时，才发起竞争选择新的转发节点，否则邻居表的大小保持不变。因此，邻居表的大小只与节点发起竞争的次数有关，所需的存储开销较小。

表1　一跳邻居表结构

一跳邻居表的结构如表1所示：其中Neighbor ID 和Neighbor Position的信息由下跳转发节点响应的ECTS稍带，节点间的一跳延迟OneHop Delay由当前转发节点依照2.5获得，Count记录该邻居已成为下跳转发节点的次数。

3　实验及结果

为验证协议在网络高负载环境下的性能，本文在J-Sim［16］平台上实现了DBRR和SPEED协议，J-Sim是由Java语言开发的一种开源的，基于组件的网络仿真环境。协议的评价性能指标包括：①传递成功率（Delivery Ratio）：指sink成功接收数据包的数量与源节点发送数据包总数的比值；②平均端到端延迟（Average End-To-End Delay）：指数据包从源节点传递到sink所平均耗费的时间；③平均能耗 （Average Consumption Energy）：指成功传递一个数据包所耗费的能量；④总通信代价 （Total Communication Cost）：指发送RTS/ ERTS/DRTS、CTS/ECTS、DATA、ACK以及Beacon等各类帧的总数量。

仿真策略是在一个200×200网络中部署200个节点，从网络右边任选两个节点作为目标节点，左边任取4个节点作为源节点；数据流采用CBR（Constant Bit Rate），无线信道总带宽2M，其中控制子信道为0.4M，数据子信道1.6M；节点初始能量100J，它的发送能耗、接收能耗和空闲能耗分别为 660mW、395mW 和35mW。考察协议在高负载网络中的性能，包括数据包产生速率和数据包大两组实验，其中数据包产生速率实验的DATA包大小为512bytes，数据包大小实验的CBR设定为20packets/s。

图1考察了DBRR和SPEED在数据包产生速率场景的性能。图1a显示，当CBR小于15时SPEED的成功率仍可保持90%以上，但当CBR继续增大时它的成功率将快速降低，当CBR为50时成功率已低于10%。这主要是因为网络冲突引起节点包的重发次数增多和网络拥塞，从而导致丢包率增加；相反，DBRR采用双信道传输，可以减少控制帧与数据帧的冲突，缓解网络拥塞，当CBR为40时，依然保持近100%的成功率，尽管CBR继续增大是成功率有所降低，但CBR 为50时成功率仍然接近70%。CBR引起的网络拥塞对端对端延迟的影响也很大，如图1b所示，SPEED的延迟在CBR高于20时快速增加，而DBRR的延迟尽管在CBR大于40时也增长较快，但明显低于SPEED；另外，DBRR的转发策略也对延迟的减少起到作用。由图1c知，当CBR低于20时，DBRR的平均能耗高于SPEED，原因在于DBRR的两个子信道都始终处于工作状态，所以能耗较大；当CBR高于20时，SPEED的成功率快速导致其平均能耗低于DBRR。值得注意的是，两种协议的平均能耗都呈先下降然后上升，是因为CBR较小时，网络负载较轻，节点休闲所耗费的能量占总耗能的比重也高，所以平均能耗较低；而当CBR增大时，节点传输所耗费的能量占总耗能的比重增加，平均能耗也提高；当CBR较大时，会加剧网络拥塞，不仅耗能更多的能量，还会引起成功率降低，所以此时平均能耗又降低。如图1d所示，由于DBRR始终广播DRTS 或ERTS选择转发节点，所以在CBR较低时，它的通信代价高于SPEED；但当CBR较大时，网络冲突增大会加剧网络拥塞，SPEED利邻居表单播发送的方式可能失效，需要重新广播RTS选择转发节点，所以此时SPEED的通信代价高于DBRR；当CBR高于40时，SPEED低于30%的的成功率表明节点在广播RTS后无法接收到CTS响应的概率增加，从而导致通信代价降低。

图1　数据包产生速率实验性能比较

图2　数据包大小实验性能比较

图2考察了DBRR和SPEED在数据包大小场景的性能。图2a显示，数据包的大小对DBRR的影响较小，即使数据包为1000bytes时，它的成功率仍然大于80%，原因在于DBRR采用双信道传输机制，使两个子信道中帧的冲突概率大大降低；数据包大小对SPEED的影响较大，当数据包大于500bytes时，SPEED的成功率快速下降，原因在于数据包越大，它与RTS、CTS和ACK等帧冲突的概率越高，导致丢包率升高以及延迟和能耗的增大。而图2b显示，当数据包小于300bytes时，DBRR的延迟高于SPEED，这与3.4.1中的分析相符合；但当数据包大于300bytes时，DBRR的延迟低于SPEED，这也是因为SPEED中数据帧与其他信息帧冲突高于DBRR。如图11c所示，当数据包小于300bytes时，DBRR的平均能耗在高于于SPEED，原因在于DBRR的两个信道都始终处于工作状态，所以能耗较大；但随着数据包大小的增大，SPEED的冲突加剧而使其平均能耗明显高于DBRR。图2d显示DBRR的通信代价高于SPEED，主要是因为始终广播DRTS或ERTS来选择转发节点。

上述仿真实验表明，DBRR的传递成功率和延迟要明显优于SPEED，而随着CBR和数据包大小的增加，DBRR在平均能耗和通信代价的性能也要好于SPEED，表明双信道传输机制对缓解因冲突引起的网络拥塞起到了有效的作用。

4　结语

本文为高负载无线传感器网络环境提出了一种双信道无信标实时路由协议DBRR。DBRR利用无信标转发方式建立节点邻接表，并根据邻接表的有效性采用速率约束和单跳延迟约束来保证数据传输的实时性。此外，DBRR利用双信道并行传输，完全避免控制帧和数据帧的冲突，可以有效缓提高的网络的能量效率和传输性能。

［1］I.Akyildiz，W.Su，E.Cayirci，Y.Sankarasubramaniam.Wireless sensor networks：A survey.Computer Networks，2002，3：393-422.

［

2］Y.Li，C.Chen，Y.Song，Z.Wang.Real-time qos support in wireless sensor networks：a survey.In Proceedings of seventh IFAC International Conference on Fieldbuses and nETworks in industrial and embedded systems，2007，11：373-380.

［3］J.Sanchez，P.Ruiz，R.Marin-Perez.Beacon-less geographic routing made practical：challenges，design guidelines，and protocols.Real-Time Systems，2009，47：85-91.

［4］T.He，J.Stankovic，C.Lu，T.Abdelzaher.A spatiotemporal communication protocol for wireless sensor networks.IEEE Transactions on Parallel Distributed Systems，2005，16：995-1006.

［5］E.Felemban，C.Lee，Ekici E.MMSPEED：multipath Multi-SPEED protocol for QoS guarantee of reliability and.Timeliness in wireless sensor networks.Mobile Computing，IEEE Transactions on Mobile Computing，2006，5：738-754.

［6］L.Savidge et al.QoS-based geographic routing for event-driven image sensor networks.In Broadband Networks 2005，2nd International Conference on，2005.

［7］Y.Xu，F.Ren，T.He.Real-time routing in wireless sensor networks：A potential field approach.ACM Transactions on Sensor Networks，vol.9：Article No.35，2013.

［8］T.He et al.，Robust and timely communication over highly dynamic sensor networks.Real-Time Systems，2007，37：261-289.

［9］D.Cheng，P.Varshney.On-demand geographic forwarding for data delivery in wireless sensor networks.Computer Communications，2007，30：2954-2967.

［10］黄超，王国利.无线传感器网络协作无信标可靠路由协议［J］.中山大学学报自然科学版，2013，52：39-44.

［11］IEEE.NSI/IEEE Std.802.11，1999 Edn.Part 11：wireless LANMedium Access Control（MAC）and Physical Layer（PHY）specifications.IEEE，1999.

［12］K.Kosek-Szott.A survey of mac layer solutions to the hidden node problem in ad-hoc networks.Ad Hoc Networks，2012，10：635-660.

［13］Z.Haas，J.Deng.Dual busy tone multiple access（dbtma）-a multipleaccess control scheme for ad hoc networks.IEEE Transactions on Communications，2002，50：975-985.

［14］H.Zhai，J.Wang，Y.Fang.DUCHA：A new dual-channel MAC protocol for multihop Ad hoc networks.IEEE Transaction on Wireless Communications，2006，5：3224-3233.

［15］刘逵，刘三阳，焦合华.一种蚁群策略的双信道传感器网络路由算法［J］.西安电子科技大学学报（自然科学版），2013，40：71-77.

［16］J-Sim simulator：http：//j-sim.cs.uiuc.edu/index.html.

Wireless Sensor Network；Real-Time Routing；Dual-Channel；Beaconless Forwarding

Dual-channel Beaconless Real-time Routing Protocol for Wireless Sensor Networks

HUANG Chao
（School of Computer Science，Guangdong Polytechnic Normal University，Guangzhou 501665）

1007-1423（2015）22-0011-07

10.3969/j.issn.1007-1423.2015.22.003

黄超（1978-），男，江西乐安人，博士，研究方向为无线传感器网络、物联网

2015-06-26

2015-08-05

针对事件驱动等应用中感知数据急剧增大的高负载网络环境，提出基于无信标转发的双信道实时路由协议DBRR，该协议采用采用竞争模式与邻居表相结合的转发策略，竞争模式在线地选择有效的转发节点，并使用双信道方式缓解高负载下的网络冲突。DBRR通过速率约束和单跳延迟约束来满足实时性，它邻居表信息是通过竞争和无线广播特性而不是信标广播方式获得。仿真结果表明，在高负载性网络中，DBRR在数据传输成功率、传输延迟、平均能耗和通信代价等方面均明显优于SPEED。

无线传感器网络；实时路由；双信道；无信标转发

广东高校优秀青年创新人才培养计划项目（No.2013LYM_0049）

Presents a dual-channel beaconless real-time routing protocol，called DBRR，for high-load wireless sensor networks（WSNs）.End-toend real-time requirements are fulfilled with speed or delay constraint at each hop through integrating the contention and neighbor table mechanisms.DBRR incorporates a dual-channel paradigm to alleviate packet collisions so as to lessen energy consumption and shorten end-to-end delay in high-load networks.Comprehensive simulations are carried out and show that DBRR outperform SPEED in terms of delivery ratio，end-to-end delay，energy efficiency and communication cost in high-load networks.