无线多媒体传感器网络多路径路由协议综述*

吴 笛， 董淑福， 康巧燕， 赵亚金

(1.空军工程大学 信息与导航学院，陕西 西安 710077；2.北京军区空军司令部 网管中心，北京 100038)

0 引 言

无线多媒体传感器网络(wireless multimedia sensor networks,WMSNs)是在无线传感器网络(WSNs)的基础上引入了图像、声音、视频等多媒体信息感知和处理功能，可广泛应用于环境监测、交通监控、医疗卫生等领域[1]。WMSNs对所传输多媒体信息的服务质量(QoS)性能指标十分敏感，因此，有效保障多媒体信息的QoS传输并尽量节省网络能量是WMSNs实用化的关键[2]。

根据数据传输过程使用路径的多少，可分为单路径路由和多路径路由。传统的单路径路由协议如DSR[3]，AODV[4]，EAQR[5]，REAR[6]等，会造成某单一路径因为频繁进入工作状态而能量消耗过大，导致该路径上部分节点因电池耗尽而使该路径失效；而重新发现路由会对网络的传输时延和数据传输的可靠性带来影响，无法确保多媒体信息的传输质量。而多路径路由策略通过在源节点和目的节点间建立并维护多条传输路径以提高通信的可靠性，在多路径之间根据特定的代价函数选择优化的路径进行数据传输，或根据数据不同的优先级选择不同的QoS路径以提供QoS保障和实现网络负载平衡，非常符合WMSNs路由协议设计的需求。

1 多路径路由协议的分类

多路径路由协议(multipath routing protocol，MRP)可根据路径的相交性可分为相交路径与不相交路径，相比相交路径，不相交路径各条路径间更为独立，彼此干扰较小，现有的很多方法可以很容易地找到多条不相交路径[7，8]。根据多路径数据传输的方式可分为主从路径与非主从路径。

主从路径是指在同一时刻仅使用一条最优路径传输数据，其余为备用路径；非主从路径是指同一时刻使用多条路径同时传输数据。相比主从路径，非主从路径改变了只有主路径失效才启用从路径传输数据的状况，在提高可靠性的同时提高网络吞吐量[9，10]。

根据多路径建立时机和数据传输技术，本文将MRP分为三类：主动式MRP、响应式MRP和编码式MRP。1)主动式MRP：在数据传输之前就根据节点能量和链路质量，通过广播路由信息建立和维护多条从源节点到目的节点的路径，所有数据都通过这些已发现的多路径进行传输。优点：提高数据传输的可靠性和实时性，减少路径失效后路由重新建立的时间;缺点：建立、维护多径路由开销大，资源要求高。2)响应式MRP：只有当数据需要传输的时候，源节点才在网络中发起路由查找过程。数据传输过程中，每一个中间节点根据本地信息动态选择需要转发的下一跳节点，直到数据到达目的节点。优点：无需维护路由信息，节省能量，下一跳节点选择的随机性有利于实现网络负载平衡;缺点：数据传输前需计算路由，导致时延较大。3)编码式MRP：将待传输数据通过编码技术分散到多条路径进行传输，在目的节点通过译码和数据融合恢复原数据。优点：无需拷贝多份数据传输，节省能量，可靠性、安全性好;缺点：数据接收端存在报文乱序现象。

2 主动式MRP

主动式MRP预先维护网络中从一个节点到其他节点的所有路由信息，从而实现快速路由，适用于规模较小且动态性不强的WMSNs。典型的主动式MRP包括：HREEMR，REEM，SAR，SCMR等。

2.1 HREEMR协议

HREEMR(highly-resilient,energy-efficient multipath routing)协议[11]是在DD(directed diffusion)协议的基础上提出的，其最大的特点就是不需要周期性泛洪就能恢复从源节点到汇聚节点的数据传输路径。其核心思想是：建立从源节点到汇聚节点的多条路径，数据通过主路径传输，一旦主路径失效，就从多条备用路径中选择最优的路径作为新的主路径继续传输数据。该协议减少了路径重新建立的开销，降低了延迟，并且针对多路径建立提出了2种不同的算法：不相交多路径和缠绕多路径。在不相交多路径中，强制选择互不相交的路径可能导致备选路径和主路径相去甚远，增加能量的消耗;而缠绕多路径并不要求所有路径没有相交的节点，而是附属于主路径，作为主路径上某些节点或一段节点的冗余支路和备份。

在HREEMR协议基础上，Wang Xinhua等人提出一种可靠高效的能量感知多路径[12](reliable and energy effcient multipath ,REEM)路由协议。基站广播信息使得每个节点都能维护一个邻居节点表，表内包括节点剩余能量、通信半径、数据转发概率等，依靠邻居节点表信息建立多条传输路径。能量感知的路径选择策略有利于实现数据传输路径的低能耗，有效延长网络生存时间。此外，曹啸等人针对视频流传输，提出一种基于改进蚁群多路径路由[13]算法(ant colony-based multipath routing algorithm,ACMRA)，以寻找具有多种优先级的路径集，对重要性不同的视频数据进行相应路径的选择，在网络和视频传输性能上得到很大的提升。

2.2 SAR协议

SAR (sequential assignment routing)协议[14]以基于路由表驱动的多路径方式满足网络低能耗和鲁棒性要求。为了在每个源节点和汇聚节点之间生成多条路径，需要维护多个树的结构，汇聚节点的有效传输半径内所有一跳节点都以自己为根向外生长，树干(即多路径)的选择需要满足一定QoS要求(如时延、丢包率等)，接着每条路径选择某棵树将信息返回给汇聚节点建立多条路径。SAR协议确保了容错和故障恢复的便捷以及提供了QoS保证，但维护每个传感器节点的路由表和状态的开销较大。类似的还有N-to-1协议[15]，该协议采用基于树形的结构，将目的节点作为树根，实现N-to-1的多路径传输模型。SCMR(secure cluster-based multipath routing)协议[16]在N-to-1协议的基础上采用分层结构，保证数据的有效聚合并利用簇头节点的高能量特性，在簇头间使用多路径传输多媒体数据，提高数据传输的可靠性。

3 响应式MRP

响应式MRP在数据分组要发送时选择路由，节点无需维护路由信息表，适用于动态性较强的WMSNs。典型的响应式MRP包括:TPGF,MMSPEED,CDMS,AMCMR等。

3.1 TPGF协议

协议[17]是一种两质相基于地理信息的贪婪转发(two-phase geographic greedy forwarding,TPGF)路由算法，针对多媒体信息量大的特点，可以找到多条路径来传输数据，并且绕开空洞区域，较好地解决了网络能量负载平衡问题。该协议执行时分为路径查找和路径优化2个阶段。在路径查找过程中，TPGF协议选出的邻居节点可以比当前节点距离汇聚节点更远，这样就能够避免局部最小化问题。在路径优化过程中，采用基于标签的优化来消除路径上的环路。将协议算法执行多次，即可以找到多条路径，并且每条新路径都会绕开已用过的节点。由于该协议是纯地理信息路由，在选择下一跳节点时不用消耗太多信息交换所产生的能量，满足传感器节点能量受限的特性；缺点是没有考虑网络能耗问题,且提供的QoS保障单一。

此外，Wang Zijian提出的多路径间无碰撞路由协议EECA[18](energy efficient collision aware)，该协议根据节点通信半径限制多路径间各节点的距离，保证多路径间通信干扰最小化，提高链路数据传输性能；GEAMS(geographic energy-aware multipath stream-based)路由协议[19]采用智能贪婪转发算法和后退标记思想通过建立多路径承载数据流，确保了能量均衡和低时延传输。

3.2 MMSPEED协议

SPEED协议[20]通过非确定地理转发(nondeterministic geographic forwarding,NGF)算法，负责选出满足传输速率要求的下一跳节点，但全网只维持一个服务速率，不适用于WMSNs中多种数据流的传输，而MMSPEED(multi-path and multi-SPEED)协议[21]能够提供多种全网速度和差异化的QoS，并且在传输数据时采用多条路径来满足业务的可靠性。协议采用基于本地估计的多径转发，即每个节点根据本地的差错估计和到邻居节点的距离，独立选出多个转发节点，具体过程为：每一个节点i估算出数据包成功传输的概率P，再结合业务端到端到达率要求R估算出需要的转发路径数量N，节点i从邻居节点中不断选出到达概率较大的节点作为转发节点，直到满足数据总到达率TRP>R。Darabi Saeed在MMSPEED协议基础上提出multimedia-aware MMSPEED协议[22]，该协议针对视频数据通过编码后具有重要性的不同采用区分优先级的多径传输，提高了视频传输的质量,并延长了网络生存时间。

3.3 CMDS协议

CMDS(cluster-based multipath delivery scheme)协议[23]继承了层次路由协议的特点，在分簇时采用基于节点ID和能量的分簇算法，在数据发送阶段，簇头节点将簇内成员节点数据聚集融合之后，根据一定概率在簇头间使用多路径将数据传给汇聚节点。与传统LEACH协议相比，簇头节点通过多跳的多路径方式传送数据，避免簇头和汇聚节点间采用大功率的一跳通信，有效降低和均衡了节点能耗，延长了网络生存时间。此外，Agrakhed Jayashree提出一种基于簇的自适应多路径路由 (cluster-based adaptive multi-constraint multipath routing,AMCMR)协议[24]，根据区域的节点、链路质量动态成簇，数据传输时汇聚节点通过泛洪路由请求消息，簇头节点收到请求消息后选择合适的路径反向转发路由应答消息，汇聚节点收到应答消息后，多路径得以建立。

4 编码式MRP

针对WMSNs中节点资源受限、通信易失效的弱点，编码式MRP将编码技术与多路径数据传输相结合，适用于较高可靠性要求的WMSNs。典型的编码式MRP包括:EQSR,NCE-ReInform协议等。

4.1 EQSR协议

EQSR协议[25]是一种基于区分服务的多路径QoS路由协议，该协议的核心思想是通过多路径来提高带宽，通过将数据流分为实时性和非实时性两类。在传输过程中，将实时性数据通过分片编码的方式分散到时延低、链路质量高的多条路径中进行传输，而将非实时性数据以同样的方式分散到性能较次的多条路径中进行传输，具体模型如图1所示。

图1 EQSR区分服务多路径模型图

该协议根据链路代价函数建立质量不同传输多路径，之后源节点采用FEC前向纠错编技术，将k个原始数据包经过冗余编码后生成n个数据包(n>k)，再根据编码包中的数据类型将n个包分散到不同链路质量的多路径中传输，在接收端只要至少收到任意k个线性无关的编码数据包就可以通过译码算法还原出原始数据。典型的多优先级多路径协议还包括Zhang Lin提出的视频流路由协议MPMPS[26](multi-priority multi-path selection)；Wang Xiao-ming等人[27]采用高效的队列管理算法，通过编码方式利用多路径合理调度视频流、音频流、实时数据以及非实时数据。此类路由提供了QoS时延保障并有效扩展了带宽，安全性好；缺点是数据的编码/解码比较耗能，数据流的同步和抖动又成为一个新的复杂的问题。

4.2 NCE-ReInform协议

ReInform(reliable information forwarding using multiple paths)协议[28]采用多路由和随机转发机制来保证信息传输的可靠和路由负载平衡，但是没有关注如何减少节点能量损耗，冗余数据容易造成网络拥塞并且没有考虑其它QoS约束。Cherian M等人[29]改进了ReInform协议，在每个节点加入一个队列模型，节点相当于调度器，根据数据包的类别区分服务，将数据分散到不同的路径中，有利于缓解拥塞。

ReInform协议数据的冗余增大了网络的负担，故在WMSNs中采用将随机网络编码(random network coding,RNC)与多路径数据传输相结合的NCE-ReInform协议[30]，以增加计算开销为代价减小数据报文的传输量，减少为保证期望可靠性所需的多路径数量。假设每份报文为达到期望可靠性需要的路径数为N，ReInform协议中，传送h份不同报文需要h×N条路径，而NCE-ReInform协议通过网络编码将多份数据编码生成相互无关的m份数据沿多路径传输，接收端收到一部分线性无关的编码数据就能恢复原始数据。根据概率统计，m小于h×N，这样减少了对单份数据的依赖性和所需的总路径数，降低了通信能耗。网络编码与FEC思想上相似，但网络编码允许中间节点对数据进行再次编码，以降低编码数据包之间的线性相关性，提高接收端的解码成功率。

5 WMSNs的MRP分析

WMSNs多路径路由协议根据不同的QoS需求来设计，使用的机制不同，具体面向的应用也各有特点。本文从9个方面进行了总结，如表1所示。

表1 WMSNs的MRP特点比较

6 结束语

WMSNs多路径路由研究已成为当前研究热点，随着研究的进一步深入，设计者应着重考虑以下几个方面：1)设计服务感知的多路径路由以支持多QoS保障；2)采用高效的编码技术、数据融合机制等优化多路径；3)完善的多路径路由安全机制；4)考虑无线信道的广播特性造成多路径间的通信干扰。

参考文献:

[1] AlNuaimi M,Sallabi F,Shuaib K.A survey of wireless multime-dia sensor networks:Challenges and solutions[C]∥International Conference on Innovations in Information Technology (IIT),2011:191-196.

[2] Ehsan S,Hamdaoui B.A survey on energy-efficient routing techniques with QoS assurances for wireless multimedia sensor networks[J].Communications Surveys & Tutorials,2012,14(2):265-278.

[3] Maltz D.On-demand routing in multi-hop wireless Ad-Hoc networks[D].Pittsburgh,PA:Carnegie Mellon University,2001.

[4] Perkings C E,Royer E M.Ad Hoc on-demand distance vector routing[C]∥ Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications,New Orleans,LA,1999:90-100.

[5] Akkaya K,Younis M.An energy-aware QoS routing protocol for wireless sensor networks[C]∥Proceedings of IEEE Workshops on Distributed Computing System,Washington:IEEE Computer Society,2003:710-715.

[6] Yao Lan,Wen Wenjing,Gao Fuxiang,et al.A real-time and energy aware QoS routing protocol for multimedia wireless sensor networks[C]∥Proc of IEEE WCICA,Washington DC:IEEE Computer Society,2008:3321-3326.

[7] Qu Zhaoyang,Ren Weiwei,Wang Qianchun.A new node-disjoint multi-path routing algorithm of wireless Mesh network[C]∥Computer,Mechatronics,Control and Electronic Engineering(CMCE),Changchun,China,2010:1-3.

[8] Ding Yong,Yang Yang,Xiao Li.Multi-path routing and rate allocation for multi-source video on-demand streaming in wireless mesh networks[C]∥IEEE INFOCOM,Shanghai,China,2011:2051-2059.

[9] Zhang Weiyi,Tang Jian,Wang Chonggang,et al.Reliable adaptive multipath provisioning with bandwidth and differential delay constraints[C]∥IEEE INFOCOM,San Diego,CA,United States,2010:14-19.

[10] Nissler Mattias,Gotzhein Reinhard.Performance evaluation of multi-path routing in reservation-based wireless networks[C]∥Proceedings of the 12th ACM International Conference on Mode-ling,Analysis and Simulation of Wireless and Mobile Systems,2009:268-273.

[11] Ganesan D,Govindan R,Shenker S,et al.Highly-resilient,energy-efficient multi-path routing in wireless sensor networks[J].Mobile Computing and Communications Review,2002,5(4):10-24.

[12] Wang Xinhua,Che Changming,Li Ming.Reliable multi-path routing protocol in wireless sensor networks[C]∥ Proceedings of the 2010 International Conference on Parallel and Distributed Computing,Applications and Technologies,2010:289-294.

[13] 曹 啸,王汝传,黄海平,等.无线多媒体传感器网络视频流多路径路由算法[J].软件学报,2012,23(1):108-121.

[14] Sohrabi K.Protocols for self-organization of a wireless sensor network[J].IEEE Personal Communications,2000,7(5):16-27.

[15] Lou Wenjing.An efficient n-to-1 multipath routing protocol in wireless sensor networks[C]∥2nd IEEE International Confe-rence On Mobile Ad Hoc and Sensor Systems,Washington,2005:665-672.

[16] Almalkawi I T,Guerrero Zapata M.A secure cluster-based multipath routing protocol for WMSNs[J].Sensors,2011,11(4):4401-4424.

[17] Shu Lei,Zhang Yan.Geographic routing in wireless multimedia sensor networks[C]∥IEEE Proceeding of FGCN,Hainan:IEEE Communication Society,2008:68-73.

[18] Wang Zijian,Bulut E,Szymanski B K.Energy efficient collision aware multipath routing for wireless sensor networks[C]∥ Proceedings of the 2009 IEEE International Conference on Communications,2009:1-5.

[19] Samir Medjiah,Toufik Ahmed,Francine Krief.GEAMS:A geographic energy-aware multipath stream-based routing protocol for WMSNs[C]∥2009 Global Information Infrastructure Symposium,2009:1-8.

[20] He Tian,Stankovic John A.SPEED:A stateless protocol for real-time communication in sensor networks[C]∥Proceeding of International Conference on Distributed Computing Systems,Washington:IEEE Computer Society,2003:204-223.

[21] Felemban E.MMSPEED:Multipath multi-SPEED protocol for QoS guarantee of reliability and timeliness in wireless sensor networks[J].IEEE Transaction on Mobile Computing,2006,6:738-754.

[22] Darabi Saeed,Yazdani Nasser,Fatemi Omid.Multimedia-aware MMSPEED:A routing solution for video transmission in WMSNs[C]∥2008 2nd International Symposium on Advanced Networks and Telecommunication Systems,Mumbai,India,2008:1-3.

[23] Yang Jing,Xu Mai,Xu Jinfu.A cluster-based multipath delivery scheme For wireless sensor networks[C]∥IEEE Broadband Network & Multimedia Technology,2009:286-291.

[24] Agrakhed Jayashree,Biradar G S,Mytri V D.Cluster-based path constraint adaptive multipath routing protocol in WMSNs[C]∥9th IEEE and IFIP International Conference on Wireless and Optical Communications Networks,Indore,MP,India,2012:1-5.

[25] Yahya Bashir,Ben-Othman Jalel.An energy efficient and QoS aware multipath routing protocol for wireless sensor networks[C]∥IEEE 34th Conference on Local Computer Networks,Zurich:2009:93-100.

[26] Zhang Lin,Hauswirth M.Multi-priority multi-path selection for video streaming in wireless multimedia sensor networks[J].Lecture Notesin Computer Science on Ubiquitous Intelligence and Computing,2008,5061:439-452.

[27] Wang Xiaoming,Li Chengbo,Lu Junling.QoSPMR:QoS-aware and priority-based multipath routing algorithm for WMSNs[C]∥2012 Spring World Congress on Engineering and Technology,Xi’an,China,2012:1-5.

[28] Deb B,Bhatnagar S,Nath B.ReInForm:Reliable information forwarding using multiple paths in sensor networks[C]∥Proceeding of LCN’03,Washington:IEEE Computer Society,2003:406-415.

[29] Cherian M,Gopalakrishnan N.Multipath routing with novel pa-cket scheduling approach in wireless sensor networks[J].International Journal of Computer Theory and Engineering,2011,3(5):666-670.

[30] 李姗姗,廖湘科,朱培栋,等.基于网络编码的无线传感器网多路径传输方法[J].软件学报,2008,19(10):2638-2647.