摘要：针对无线传感器网络（WSN）中存在节点剩余能量不足而导致的路由失效问题，提出一种基于低占空比的汇聚树机会路由算法CTOR在CTOR中，首先根据网络的传输质量需求确定路由候选节点集；然后，节点以广播方式向所有候选节点传输数据包，收到数据包的候选节点再以一定概率转发该数据包，转发成功的候选节点即为选定的路由节点概率的引进保证了高数据传输质量与轻网络负载；同时，网关节点发送时间同步控制信息以达到全网时间同步的目的；节点根据固定占空比进行休眠切换，以减少节点的能量消耗，延长网络的生存周期仿真实验表明，基于低占空比的协议可有效地避免网络空洞问题，延长网络的生存周期；同时，机会性的转发可以有效地提高数据包的成功接收率，降低网络的丢包率
关键词：无线传感器网络； 时间同步； 占空比； 机会路由； 转发概率
中图分类号：TP393 文献标志码：A
0引言
在无线传感网[1]（Wireless Sensor Network，WSN）中，节点一般由电池供电，而多数情况下，目标监测区域为敌对环境或难以到达，致使电池的频繁更换不现实因此，能量是WSN中最为珍贵的资源同时，节点的计算能力和带宽资源也是非常有限的因此，如何利用传感网的有限资源为应用提供服务质量（Qaulity of Service，QoS）保障是WSN的研究热点
WSN中的路由协议负责将源节点感知的数据通过网络转发到Sink节点，其中包括寻找合适的下一跳节点和保证数据的正确转发在WSN中，由于节点的能量有限且一般没有能量的补充，因此，路由协议必须是能源有效的；同时，WSN中节点数量众多，规模可观，故路由协议同时必须具备可扩展性和鲁棒性目前针对无线网络的特点已经提出了多种路由协议，如文献[2]中提出的洪泛路由协议，该协议算法简单，不需要维护网络拓扑，鲁棒性强，但是容易造成数据内爆和数据重复，能量消耗过大，不适用于能量有限的传感器网络文献[3]提出了基于协商的能量自适应路由（Sensor Protocols for Information via Negotiation，SPIN），该协议可以有效地克服洪泛的缺点，但是该协议在每次发送数据包前都需要发送检测数据包，开销和延迟都较大，不适合大规模的网络汇聚树路由协议 （Collection Tree Protocol，CTP）[4]是典型的数据汇聚路由协议，通过将目的节点设为树根，以期望传输值 （Expected Transmissions，ETX）[5]作为路由梯度，将普通监测节点加入到汇聚树中，从而为节点建立一条到目的节点的确定的路径[6]虽然CTP是以链路质量作为选路的标准，但是这种确定性的父节点选择在链路状态不稳定的无线网络中可能会导致某一节点负载过重，能量消耗过大；同时会导致大量的数据包丢失，而数据包丢失后，发送节点会启动重传机制，导致丢包情况加剧，从而影响网络的性能针对无线链路的广播、不稳定特性以及确定性路由的缺点，MIT首次提出了机会路由ExOR[7]机会路由充分利用了无线网络的广播和链路不确定特性，通过向多个候选节点同时发送，机会性地选择下一跳转发节点，可以有效地提高传输质量，提高网络吞吐量随后国内外关于机会路由又开展了深入的研究[8-12]ExOR的不足就在于扩展性不强，缺乏转发节点间协调机制，数据包重复概率高
机会路由中影响路由性能的一个重要因素就是数据的重复发送，如何进行候选节点之间的协调成为设计机会路由必须要考虑的问题目前主要有控制包应答模式协调机制[7， 13-15]和无协调方式[16-17]本文提出一种满足给定传输率的概率协调方法，可以在有效减少重复包个数的同时保证网络的传输率
除此之外，针对野外环境监测的传感器网络来说，可能短时间内节点的监测数据不会发生剧烈的变化，那么节点适当地降低采集频率，间歇性地关闭射频模块，即为网络中的节点加入休眠调度机制，以此来延长网络生存周期
本文针对以上提出的问题，以野外环境监测为应用背景，结合休眠调度机制，充分利用网络的广播特性，提出了基于低占空比的机会汇聚树路由协议： CTOR （Collection Treebased Opportunistic Routing with Low Duty Cycle）
1CTOR协议描述
假设传感器监测节点和网关节点随机部署在大范围的野外区域，节点和网关的位置未知，那么在网络的最初阶段就是确定网络中数据流的方向，方向确定后，节点需要通过广播的方式向候选节点集发送数据，候选节点集通过一定的概率协调来保证数据的可靠传输因此，CTOR协议可以分为三部分：确定方向过程、机会路由过程和休眠调度过程
1.1确定方向过程
网关节点广播寻找数据包来为网络中的节点确定网关的方向，网关的一跳邻居节点收到该数据包后，记录下自己距离网关的跳数，然后转发该数据包当一个节点收到多个数据包时，只将跳步数最小的邻居节点加入自己的候选节点集中，具体如算法FD（Find Direction）中描述这一过程结束后，节点都会确定一个到网关的最小跳数和通向网关的一个或者多个邻居节点，从而也就确定了网络中数据流的方向
假设网关节点发送的寻找数据包为Find_packet，由该包被转发次数hop和转发节点集合Forwarder_list组成，寻找数据包转发上限由变量max_hop表示对于任意节点v来说，距离网关D的距离由distance表示，候选节点集合为CF
1.2机会路由过程
在野外大规模应用中，由于网络中的节点定期休眠，节点在工作期间将存储的监测信息集中发送，所以保证数据包的传输质量是路由协议的首要目标在CTOR中，路由部分主要包括计算期望传输次数，通过转发概率确定转发节点节点在向候选节点集发送数据包时，根据链路质量计算出期望传输次数H，然后发送数据包H次，保证至少有一个候选节点会收到数据包收到数据包的转发节点并不是都会进行转发，而是计算一个转发概率p，根据概率进行转发，以此来减少重复包的个数
假设网络要达到的成功传输率为Δ，节点u距离网关跳数为i，因为要保证传输成功率Δ，则每跳的成功传输率至少为Δ1i节点候选节点个数为k，节点u和候选节点j的链路失败概率为pj，至少有一个节点收到数据则表明传输成功，传输次数H的计算如下所示：
节点将数据包广播H次后，节点的多个候选邻居节点会收到数据包，为了减少重复包的次数，并不是所有的转发节点都会转发该数据包，而是以概率p转发假设现有多个节点收到数据包，需保证至少有一个节点转发该数据包，则
通过以上计算，可以得出节点的转发次数和转发概率，在保证了一定成功传输率的情况下，减少了重复包
1.3休眠调度过程
在采用机会路由保证数据成功传输的同时，在CTOR中，结合休眠调度机制来减少空闲侦听的消耗，首先需要实现的就是网络中节点的时间同步控制，然后节点根据固定的占空比进行休眠工作
1.3.1时间同步
网络中的节点可以分为根节点和非根节点两种类型
当根节点收到发送的同步包的命令后，立即发送同步包，并按周期T连续广播发送n个包；
当非根节点接收到数据包时，判断该包的类型，如果是时间同步控制包，则触发上层事件，让上层调整定时器，达到同步效果，同时以自身节点为时间同步源节点，以周期T连续广播发送数据包
由于每个节点震荡晶体的不同，所以导致即使已经时间同步的节点在工作一段时间后，也会出现不同程度的时间偏差，这时，就需要及时调整节点状态，再次进行时间同步操作假设当节点运行t时间后，节点的时间偏差会影响节点和其他节点的通信，那么每隔t时间，由根节点发起同步命令包，以广播的方式再次发送同步命令包如图1所示的是时间同步和休眠调度模块流程
1.3.2避免广播风暴策略
由于同步包都是广播发送，非根节点在接收到同步包后，需要再次转发，这样会造成数据包大量重复传输，甚至环路，称为广播风暴针对这种情况，当非根节点收到同步包后，只对第一个同步包进行处理，对之后的同步包不做处理；同时把接收到的同步包的下标值记录下来，并以此下标加1的方式向外广播发送同步包；直到下标号大于设定的阈值n，该方式既能避免广播风暴，又可以尽可能地向全网广播同步信息
1.3.3休眠调度机制
在传感器节点的多个模块中，收发模块的侦听消耗大部分的电量，所以本文的休眠调度机制主要就是收发模块的打开和关闭
在完成时间同步过程后，节点根据固定占空比切换休眠、工作模式节点在休眠阶段关闭射频模块，只采集数据，并将数据放在存储模块当节点进入工作阶段后，和周围的节点进行通信，将存储的数据利用汇聚树协议发送到网关节点
1.3.4异步休眠调度
随着网络规模的增大，全网时间同步比较困难，且时间同步后的更新维护也会增大网络的消耗，不利于长时间的网络应用本节主要讨论异步情况下休眠调度机制的实现
假设节点在一个周期内工作时间为Tbusy，休眠时间为Tsleep，在网络初始阶段，节点向邻居节点发送包含自身工作时间的时间数据包，数据包中包含该节点发送该数据包时已经工作的时长t，邻居节点收到该数据包后，记录收到数据包时自身已工作的时间treceive，将时间t、treceive作为邻居节点的附加信息保存到邻居表中，假设节点从休眠状态转到工作状态需要向邻居节点发送更新工作时间包，同时查询邻居节点的工作状态因此，对于发送节点来说，它可以根据tlocal-treceive+t来估计邻居节点当前的工作状态，其中tlocal为发送节点发送时已工作的时间发送节点通过这一标准，剔除候选节点集中已经休眠或者即将休眠的邻居节点，保证数据包在节点异步休眠情况下可以成功地发送到邻居节点
2仿真实验与分析
为了有效分析CTOR对于网络性能的提高，本文利用Java仿真器对不同网络规模下CTOR的性能和ExOR、SOAR[15]、CTP的性能进行对比
实验在300m×300m的区域中随机部署监测节点，节点的个数从200递增到450，节点的传输范围为40m，网关的传输范围为60m，网络的运行时间以时间槽（slot）为单位，其中CTOR在网络运行时间内共休眠200个时间槽假设在CTOR协议中，网络需要达到的成功传输率Δ为95%，任意两个节点间的链路的成功概率在60%到80%之间
图2和图3所示的是在ExOR、SOAR和CTP的最高重传上限为3，CTOR的平均重传次数为3的情况下，不同规模网络的生存周期和网络的成功传输率
在图2中，当节点个数小于300时， CTOR的生存时间明显大于CTP、ExOR和SOAR；当网络中节点在300到400范围内时，采用CTOR和CTP的网络生存时间相差不大，但是随着节点个数的继续增大，CTOR的生存时间还是逐渐延长，而CTP却呈现出下降的趋势这是因为CTOR转发节点的确定是机会的，避免了频繁使用固定的转发节点而造成的路由空洞而从整体上比较，ExOR和SOAR的生存时间小于CTP和CTOR，这是由于ExOR采用的是应答包协调机制，控制包的发送和侦听需要消耗额外的能量；SOAR虽然采用最短路径附近的邻居节点作为候选转发节点，减少了应答包协调带来的额外开销，但是会导致固定链路上负载过重，易出现路由空洞，从而网络整体生存时间减少；CTOR采用概率的方式进行协调转发，在减少寻找最短路径和应答机制带来的额外开销的同时，可以有效避免单条链路负载过重而造成的路由空洞问题
从图3可以看出，CTOR的多链路同时传输使得网络的成功传输率不仅在各种网络规模下都优于CTP，而且相对稳定ExOR和SOAR的成功传输率虽然高于CTP，但是整体上低于CTOR，主要原因是CTOR可以根据所选择转发节点的链路质量动态地计算重传次数，达到网络期望的成功传输率
图4和图5主要是CTP在不同的重传上限下，网络的生存时间和成功传输率如图3所示，在平均重传次数为3的情况下，CTOR的成功传输率可以达到95%左右，在图5中，随着重传次数的增大，网络的成功传输率也随之增大，相应的如图4所示，网络的生存时间也随着重传次数的增大而减小
以上仿真实验结果表明，CTOR可以有效地弥补CTP成功传输率低、经典机会路由生存时间短等不足之处，同时采用固定占空比的工作方式，在提高成功传输率的同时能有效地延长网络生存时间
3结语
本文提出了一种适用于高质量传输需求的无线传感网路由协议——CTOR在CTP路由协议的基础上，结合机会路由，充分利用无线网络的广播特性，弥补了CTP确定性路由在不稳定网络环境中的不足；同时，采用概率的方式确定转发节点，在保证网络期望成功传输率的前提下，最大限度地减少了重复包；避免了转发节点之间发送协调信息所带来的额外开销，节省了能量实验结果分析表明，CTOR同CTP相比，可以有效地提高数据包的成功传输率；同ExOR，SOAR等机会路由相比，可以延长网络的生存周期CTOR结合了确定性路由和机会路由的优点，使协议在链路环境不稳定的网络中也可以有效地运行
我们的下一步工作就是解决如何在非时间同步情况下实现休眠调度，使得在大规模的网络中有效地进行全网休眠调度，增加协议的可扩展性，减少能耗，提高全网的利用率
参考文献：
[1]孙利民.无线传感器网络[M].北京：清华大学出版社， 2005.
[2]HAAS Z J， HALPERN J Y， LI L. Gossipbased Ad Hoc routing[J]. IEEE/ACM Transactions on Networking， 2006， 14（3）： 479-491.
[3]KULIK J， HEINZELMAN W， BALAKRISHNAN H. Negotiationbased protocols for disseminating information in wireless sensor networks[J]. Wireless Networks， 2002， 8（2/3）： 169-185.
[4]GNAWALIi O， FONSECA R， JAMIESON K， et al. Collection tree protocol [C]// Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems. New York： ACM， 2009： 1-14.
[5]de COUTO D S J， AGUAYO D， BICKET J， et al. A highthroughput path metric for multihop wireless routing[J]. Wireless Networks， 2005， 11（4）： 419-434.
[6]雷鸣， 冯驰. 基于 TinyOS 的无线传感器网络数据汇聚协议研究[D].哈尔滨：哈尔滨工程大学，信息与通信工程学院，2009.
[7]BISWAS S， MORRIS R. ExOR： opportunistic multihop routing for wireless networks[C]// SIGCOMM 05： Proceedings of the 2005 Conference on Applications， Technologies， Architectures， and Protocols for Computer Communications. New York： ACM， 2005： 133-144.
[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. New York： ACM， 2011： 181-192.
[9]LAUFER R， VELLOSO P B， VIEIRA L F M， et al. PLASMA： a new routing paradigm for wireless multihop networks [C]// INFOCOM 2012： Proceedings of the 2012 IEEE International Conference on Computer Communications. Piscataway： IEEE， 2012： 2706-2710.
[10]WU J， WANG Y. Social featurebased multipath routing in delay tolerant networks [C]// INFOCOM 2012： Proceedings of the 2012 IEEE International Conference on Computer Communications. Piscataway： IEEE， 2012： 1368-1376.
[11]CHAU C K， GIBBENS R J， HANCOCK R E， et al. Robust multipath routing in large wireless networks [C]// INFOCOM 2011： Proceedings of the 2011 IEEE International Conference on Computer Communications. Piscataway： IEEE， 2011： 271-275.
[12]BASALAMAH A， KIM S M， GUO S， et al. Link correlation aware opportunistic routing [C]// INFOCOM 2012： Proceedings of the 2012 IEEE International Conference on Computer Communications. Piscataway： IEEE， 2012： 3036-3040.
[13]ZORZI M， RAO R R. Geographic random forwarding （GeRaF） for Ad Hoc and sensor networks： multihop performance [J]. IEEE Transactions on Mobile Computing， 2003， 2（4）： 337-348.
[14]ZORZI M， RAO R R. Geographic random forwarding （GeRaF） for Ad Hoc and sensor networks： energy and latency performance[J]. IEEE Transactions on Mobile Computing， 2003， 2（4）： 349-365.
[15]ROZNER E， SESHADRI J， MEHTA Y， et al. SOAR： Simple opportunistic adaptive routing protocol for wireless mesh networks [J]. IEEE Transactions on Mobile Computing， 2009， 8（12）： 1622-1635.
[16]CHACHULSKI S， JENNINGS M， KATTI S， et al. Trading structure for randomness in wireless opportunistic routing [M]. New York： ACM， 2007.
[17]NASSR M S， JUN J， EIDENBENZ S J， et al. Scalable and reliable sensor network routing： performance study from field deployment[C]// INFOCOM 2007： Proceedings of the 26th IEEE International Conference on Computer Communications. Piscataway： IEEE， 2007： 670-678.