一种改进的移动自组织网多路径路由协议
2016-12-16李旭仇颂清彭进霖王聪
李旭， 仇颂清， 彭进霖， 王聪
(1.北京交通大学 电子信息工程学院, 北京 100044; 2.北京跟踪与通信技术研究所, 北京 100092)
一种改进的移动自组织网多路径路由协议
李旭1， 仇颂清1， 彭进霖2， 王聪1
(1.北京交通大学 电子信息工程学院, 北京 100044; 2.北京跟踪与通信技术研究所, 北京 100092)
在移动自组网中，相比于单路径路由协议，多路径路由协议通过建立和维护多条备用路径，可以有效地减小通信中断的概率，降低端到端的时延。然而，目前对备用路径数目的分析方法不适合于复杂多变的无线自组网络传输环境，而且现有多路径路由协议难以满足混合业务中不同业务对传输质量的不同要求。为解决上述问题，对单路径与多路径路由协议进行建模研究，分析维护备用路径数目参量对多路径路由协议性能的影响；基于此建模分析的结论，提出一种面向业务的多路径路由协议，根据不同业务的服务质量(QoS)需求，综合考虑跳数、平均连接度、最小带宽等参数，选择针对本业务QoS需求的最优路径。仿真结果表明，调整权值系数，数据类业务的投递率最多可提高25%，语音类业务的平均时延可减少10%～20%，证明该协议针对不同业务能选择性地带来时延、可靠性、可用带宽等性能的提升。
计算机系统结构； 移动自组网； 多路径路由协议； 多路径路由协议； 服务质量
0 引言
在移动自组网中，由于节点移动速度较快、网络拓扑变化剧烈、传输环境干扰较大等原因，通信链路中断的概率较大。如果使用单路径路由协议在链路每次发生中断时重新寻路，则会由于多次寻路而带来较大时延，严重影响通信质量。使用多路径路由协议能有效地解决这个问题，减小复杂的无线环境对数据传输造成的影响。多路径路由协议在寻路过程中建立多条路径，在信息传输过程中可以选择其中的一条或者多条路径传输数据，是基于单路径路由协议的扩展。当一条路径发生中断时，数据可以通过其他的备用路径进行传输，从而有效减小信息传输中断的概率，同时避免由于单一路径中断造成的多次寻路过程，有效降低端到端时延。
现有的多路径路由协议包括按需多径距离矢量路由(AOMDV)[1]、多径源路由(MSR)[2]、按需距离矢量备份路由(AODV-BR)[3]、分裂多径路由(SMR)[4]、缓存多径路由(CHAMP)[5]等。其中，AOMDV协议是一种较为完善的多路径路由协议，其主要思想是在路由发现过程中建立和维护多条路径，并选择其中一条作为通信的主路径，其余的则作为备用路径，在传输数据时，如果主路径发生故障，可启用备用路径进行通信。
AOMDV等多路径路由协议可以有效地降低端到端时延，提高通信服务质量。但目前对多路径路由协议的研究存在许多不足。备用路径数目、环境节点密度、发包速率、包长度等参量对协议的性能有着重要的影响，特别是维护备用路径的数目，极大程度上制约着多路径路由协议的性能改进情况，影响了多路径路由协议的适用场景。然而，目前缺乏对于备用路径数目参量的有效判断机制，美国Pham等[6]此前通过简化条件，从分析两次寻路时间间隔的角度出发探讨多路径的最优路径数目。然而该方法主要基于传输环境比较稳定、干扰较小的情况进行分析，未能体现出多路径路由协议的优势，也不适合传输环境多变的移动自组网络。
目前AOMDV等多路径路由协议将路径跳数作为寻路和选路的主要判断依据，难以满足移动自组网中混合业务传输的服务质量(QoS)需求。然而，随着传输业务的多样化，如何满足业务的传输需求成为路由协议改进的一个重要方向。业务的QoS需求指标大体可分为时延、可靠性、带宽、能量等方面。对于单路径路由，目前已经提出多种针对业务QoS需求的路由协议。文献[7]提出基于时延约束的QoS路由，应用于语音、视频等对时延敏感的业务，主要方法是用定时器记录探测包的累积时延，然后选取满足时延要求的路由。文献[8]提出基于带宽约束的QoS路由，应用于对带宽要求较严的业务，协议在建立路由时充分考虑节点的带宽信息，选择有效带宽较大的节点建立路由，以满足业务的带宽需求。然而上述面向业务需求的QoS路由是基于单路径路由协议提出的，并未涉及多路径路由。文献[9]在传统AODV协议的基础上根据负载情况和跳数扩展多路径，文献[10]则综合考虑网络负载和干扰因素对AOMDV协议进行改进，都达到了降低平均开销和平均丢包率的目的，但依旧无法针对业务的特性作适合具体业务的路由选择。
针对上述问题，本文首先对单路径路由协议AODV与多路径路由协议AOMDV的性能进行建模，分析维护备用路径的数目对协议性能的影响；然后利用该建模分析的结论，基于AOMDV协议提出一种面向业务的多路径路由协议(A-AOMDV)，综合考虑时延、带宽、连接度等多个参数的影响，建立和选择适合于不同业务QoS需求的最优路径，以满足不同业务的需求。
1 单路径与多路径路由协议的建模分析
根据相交性，多路径路由可分为3种方式：节点分离、链路分离和相交。节点分离多路径，是指各条路径除源节点和目的节点之外没有其他共用节点。链路分离多路径是指各条路径没有共用的链路，但可能共用节点。相交多路径是指各条路径间既可能共用节点，又可能共用链路。本文讨论的AOMDV和A-AOMDV均为节点分离多路径协议。
本节分别建立单路径路由协议AODV和多路径路由协议AOMDV的端到端传输时延模型，分析维护备用路径数目对多路径路由协议性能的影响。
在建模过程中进行如下假设：
1)一条端到端的k跳路径由k段点到点的链路构成，每段链路的中断概率满足独立同分布，设中断概率为p，则每段链路有效的概率为q=1-p. 只有路径的所有链路都有效才能确保路径有效，那么该路径有效的概率为qk；
2)设每段链路的传输时延为T1，则该路径的端到端传输时延Tk满足Tk=kT1；
3)设多路径路由协议首选路径跳数为m，备用路径按路由表顺序排列，跳数分别为k2,k3,…,km，所有路径失效后重新寻路得到的路径跳数为h. 由于传输时延与路径跳数呈正比关系，应优先维护跳数较少的路由，满足k1≤k2≤k3≤…≤km≤h.
4)新路径的端到端传输时延Th满足Th=hT1. 寻路过程通过源节点向目的节点发送路由请求(RREQ)分组并获取路径上节点回复的路由应答(RREP)分组来实现路由更新，路径的最远节点即为目的节点，所以寻路时间为RREQ分组从源节点到达目的节点和RREP分组从目的节点到达源节点的时间总和。令s为寻路过程中RREQ和RREP分组传递的总跳数，则s=2h，寻找新路径用时Ts=2Th.
下面分别考虑单路径路由协议和多路径路由协议的端到端传输时延：
对于单路径路由协议，端到端的传输时延包含两部分：一部分是首选k1跳路径有效时的传输时延；另一部分是该条路径失效时，寻路找到h跳新路径并用该路径传输数据的时延(Ts+Th)。则单路径路由协议端到端传输时延平均值Tu表达式为
Tu=qk1Tk1+(1-qk1)(Ts+Th),
将Tk1=k1T1，Th=hT1和Ts=2Th代入，得
Tu=qk1k1T1+3(1-qk1)hT1.
(1)
对多路径路由协议，端到端传输时延Tm由3部分构成，第1部分TA是之前维护的首选k1跳路径有效时的传输时延，其路径有效的概率为qk1，则
TA=qk1Tk1=qk1k1T1.
(2)
第2部分TBm是当该首选路径失效时，利用其他多条备用路径传输的时延，则
TBm=(1-qk1)qk2Tk2+(1-qk1)(1-qk2)qk3Tk3+…+
(1-qk1)(1-qk2)…(1-qkm-1)qkmTkm=
(3)
第3部分TCm是所有维护路径都失效时寻路找到h跳新路径并用该路径传输数据的时延，大小为(Ts+Th)，概率为(1-qk1)(1-qk2)…(1-qkm). 则
TCm=(1-qk1)(1-qk2)…(1-qkm)(Ts+Th)+
(4)
综上，多路径路由协议端到端时延为Tm=TA+TBm+TCm，将TA、TBm、TCm代入得
(5)
单路径和多路径路由协议的端到端时延差值为
σm=Tu-Tm.
(6)
下面根据增加维护路径对传输时延改善的程度来讨论m的合适取值，将维护路径数量从m-1增加到m，改善的时延差Δm=σm-σm-1，将(1)式、(5)式、(6)式代入，得
Δm=Tm-1-Tm=
(7)
现用Δm与单路径路由协议端到端时延Tu的比值ηm来表征改善程度，即
ηm=Δm/Tu=
(8)
按照假设3随机构建1 000组不同的正整数序列(k1,k2,k3,…,km,h),并选取不同的中断概率p对η进行仿真，并对1 000组结果取平均值，得到η与m和p的关系如图1所示。
图1 中断概率和维护路径数目对传输时延改善的影响Fig.1 Effects of outage probability and the number of maintenance paths on the improvement of transmission delay
从图1中可看出，对于合理的中断概率条件0
2 面向业务的多路径路由协议
2.1 业务的QoS需求
业务的QoS需求指标包括时延、可靠性(丢包率)、带宽等多个方面。3GPP[11]在TS22.105规范中从业务的QoS角度出发，将移动网络业务分为4大类，即会话类、流媒体类、交互类和后台类。每一类业务又包括音频、视频、数据等若干子类。不同类型的业务具有不同的QoS需求，如话音、可视电话等会话类业务对时延敏感，要求时延控制在250 ms内，而对可靠性要求较低；数据类业务则对可靠性要求严格，需要较低的丢包率，而对时延则没有严格的要求。表1列出了一些主要应用的业务特征及QoS需求。
表1 主要应用的业务特征及QoS需求
2.2 协议设计目标和思路
本文提出的A-AOMDV协议主要针对不同业务的QoS需求，综合考虑多个指标，建立和选择针对本业务最优的路径来传输业务流，从而克服传统路由算法只根据某一项指标选路，不适合用于传输混合业务这一局限性，真正实现面向业务需求的目标。
本协议的主要设计思路为，在建路过程中建立源节点到目的节点的多条不相交路径，每条路径都有衡量自身服务质量的多个QoS参数。不同业务根据各自的QoS需求，选择适合本业务的最优路径进行传输。当所有备用路径都失效时，则重新寻路。
2.3 参数定义
在A-AOMDV协议中，将业务的QoS需求归结为3方面：时延、可靠性和可用带宽。现为每条路径添加跳数D、平均连接度R、最小带宽B3个服务质量参数，以分别衡量时延、可靠性和可用带宽，并定义路径整体服务质量L来表征具体某种业务的QoS需求。根据前面建模分析的结论，对每种QoS需求，将端到端之间的所有路径按照L的大小进行排序，只维护排序靠前的3条路径。修改后的路由表单元结构如图2所示。
图2 修改的路由表单元结构Fig.2 Unit structure of modified routing table
2.3.1 跳数D→时延
在多跳无线网络中，路径时延很大程度上取决于源节点到目的节点的跳数。跳数越大，时延越大。所以，我们将源节点到目的节点的跳数D作为衡量路径时延的参数。
2.3.2 平均连接度R→可靠性
路径上节点的连接度是路径可靠性的最好度量。一般来说，节点的邻居数越大，则连接度越高，路径中断概率越小，路径也就越可靠，丢包率也越低。节点通过接收邻居周期性广播的Hello消息可以得知自身邻居连接情况，也就是该节点的连接度。我们用路径上所有节点的平均连接度R作为衡量路径可靠性的参数：
(9)
式中：N为该路径上的节点数；Ci为路径上第i个节点的连接度，即节点i的邻居个数。
2.3.3 最小带宽B→可用带宽
在多跳无线网络中，路径可用带宽的大小取决于该路径上所有节点的最小带宽。节点的等待队列中等待发送的数据包个数越多，可用的排队空间越小，该节点可用带宽越小。将路径上所有节点的最小带宽B作为衡量路径可用带宽的参数：
B=min{Qmax-Qi},
(10)
式中：Qmax为路径上节点可发送数据包队列的最大长度，现假设其为固定值；Qi为路径中节点i等待发送的数据包队列长度。
2.3.4 路径整体服务质量L
L=|αD+βB+γR|ρ,
(11)
式中：ρ为修正因子；α、β、γ分别为跳数D、最小带宽B和平均连接度R的权值，满足α+β+γ=1，由用户指定并添加到包头结构中，可以根据不同的业务进行调整。比如：数据业务对可靠性要求较高，应将R所对应的权值γ提高；语音业务对时延和带宽要求较大，则可将D、B所对应的权值α、β作适当提高。
需要注意的是，为平衡3个服务质量参数所占的比重，应根据具体的应用场景使用修正因子ρ来调整3个服务质量参数的权值。
2.4 路由协议的实现过程
2.4.1 数据转发过程
当源节点从应用层接收数据包时，首先根据目的地址查找路由表有无到其目的节点的有效路由，如果有则根据数据包包头中用户指定的权值α、β、γ计算每条路径的整体服务质量L，选择适合于本业务的最优路径；如果没有则触发寻路过程。
2.4.2 寻路过程
1)源节点广播RREQ包，包结构中添加跳数、经过的所有节点的邻居节点数总和(用以计算平均连接度)、所有节点中最小的可用等待队列长度3种寻路信息。修改后的RREQ包结构如图3所示，其中，灰色处为协议添加的信息，路径所有节点的邻居数总和简称为邻居节点数，所有节点中最小的可用等待队列长度表示为最小带宽。
图3 修改的RREQ分组Fig.3 Modified RREQ packet
2)中间节点接收到该RREQ包时：
①首先建立或更新到源节点的反向路由：
a.如果没有到源节点的反向路径则建立新的反向路径；
b.如果有到源节点的反向路径，且接收的RREQ包中携带的3种寻路信息中有一项或多项优于已存在的反向路径的3个服务质量参数(跳数、可用等待队列长度、路径节点邻居数总和)，则接收作为备用路径；
②更新该RREQ包中的信息，继续广播。
3)当目的节点或到目的节点有效路由的中间节点接收到该RREQ包时，回复RREP包，包结构中同样添加3种寻路信息。修改后的RREP包结构如图4所示，其中，灰色处为协议添加的信息，路径所有节点的邻居数总和简称为邻居节点数，所有节点中最小的可用等待队列长度表示为最小带宽。
4)中间节点接收到该RREP分组：
图4 修改的RREP分组Fig.4 Modified RREP packet
①建立或更新到目的节点的反向路由；
②更新该RREP中的信息；
③查寻路由表，寻找到源节点的最优路径，继续转发该RREP包
5)源节点接收多个RREP包，建立到目的节点的多条路径。
3 仿真与分析
3.1 仿真环境与场景参数
利用NS2仿真软件对改进后的协议A-AOMDV进行仿真，并与原始的AOMDV协议进行比较分析。底层协议为IEEE 802.11协议，实验平台是Fedora 8.0. 由于网络中节点的移动性会造成网络拓扑的动态变化，而网络拓扑的动态变化会对路由协议的性能造成严重的影响。主要通过改变节点的最大移动速率，对比分析改进后的协议性能。
具体的仿真场景参数设置如表2所示。
表2 仿真场景参数
由于对协议的改进主要是为了满足不同业务的QoS需求，所以分别选择最具有代表性的数据类业务和语音类业务进行仿真分析。
在仿真结果分析中，选择平均时延、投递率和控制开销3个指标来评估协议的性能。
3.2 仿真分析
3.2.1 数据类业务仿真结果分析
数据类业务对可靠性要求较高，主要关注投递率的提升，所以应当相应的增大平均连接度R所对应的权值。本部分对数据类业务的投递率、平均时延和控制开销进行了仿真，结果如图5～图7所示。
图5 数据类业务在不同移动速度下的投递率Fig.5 Delivery rate of data service at different speed
图6 数据类业务在不同移动速度下的平均时延Fig.6 Average delay of data service at different speed
图7 数据类业务在不同移动速度下的控制开销Fig.7 Control overhead of data service at different speed
由图5可以看到，传输数据类业务时，A-AOMDV协议可以有效提高分组投递率。因为在为业务选择传输路径时，AOMDV协议只考虑端到端跳数，A-AOMDV协议则更侧重于路径可靠性。通过增大平均连接度R所对应的权值，从多条路径中选择可靠性最高的路径传输业务，可以提高分组的投递率。在一定的范围内，当节点的移动速率越高，A-AOMDV协议在分组投递率方面优化越明显。
从图6和图7中可以看到A-AOMDV和AOMDV协议的平均时延和控制开销占比曲线存在交叉，但从整体趋势而言两者较为接近，说明协议改进没有对时延和控制开销产生太大影响。
3.2.2 语音类业务仿真结果分析
语音类业务主要关注时延的减少和可用带宽的增加，应当相应的增大跳数D和最小带宽B所对应的权值。本部分对语音类业务的投递率、平均时延和控制开销进行了仿真，结果如图8～图10所示。
图8 语音类业务不同移动速度下的投递率Fig.8 Delivery rate of voice service at different speed
图9 语音类业务不同移动速度下的平均时延Fig.9 Average delay of voice service at different speed
图10 语音类业务不同移动速度下的控制开销Fig.10 Control overhead of voice service at different speed
由图9可以看到，当传输语音类业务时，相比于AOMDV协议， A-AOMDV协议可以有效地降低分组的平均时延。因为在为语音类业务选择传输路径时， A-AOMDV协议综合考虑端到端的跳数、路径的最小带宽两个方面的QoS需求，从所建立的多条路径中选择综合性能较好的路径来传输业务，不仅考虑端到端的最短路径，同时尽可能避免网络拥塞，因此可以有效地降低分组平均时延。
图8和图10曲线的接近拟合反映A-AOMDV协议没有影响语音业务的分组投递率和控制开销。
3.2.3 仿真分析总结
通过对数据类业务和语音类业务进行仿真，对比原AOMDV协议和改进后的A-AOMDV协议在投递率、平均时延、控制开销3个方面的性能指标，可以看到：改进的A-AOMDV协议在传输数据类业务时，可以在不过分影响分组时延和控制开销的前提下有效提高投递率；当传输语音类业务时，则能在保持AOMDV协议投递率和控制开销的基础上大幅降低分组时延。在仿真中，选择最具有代表性的两类业务。对于其他类的业务可以相应调整3个服务质量参数的权值来满足各自的QoS需求。
4 结论
针对移动自组织网，本文首先对单路径路由协议和多路径路由协议进行建模比较，分析维护备用路径的数目对多路径路由协议性能的重要影响。然后从寻路和选路的角度出发，基于AOMDV协议提出一种能适用于传输具有不同QoS需求的混合业务的多路径路由协议A-AOMDV。该协议针对不同业务的QoS需求，综合考虑时延、可靠性和可用带宽3个参数来选择最优路径。最后通过仿真与AOMDV协议进行对比，对改进后协议的投递率、时延、控制开销等方面的性能进行验证，结果证明该协议针对不同业务能选择性地带来时延、可靠性、可用带宽等性能的提升。该协议最大的特点是针对业务需求对多路径路由协议进行改进，不仅能有效减小移动自组网网络拓扑动态变化等因素对通信质量造成的影响，同时能够很好地适应于多种业务共存的场景，达到了面向业务需求的目的。
References)
[1] Araghi T K, Zamani M, Mnaf A B A. Performance analysis in reactive routing protocols in wireless mobile ad hoc networks using DSR, AODV and AOMDV[C]∥International Conference on Informatics and Creative Multimedia. Kuala Lumpur, Malaysia: IEEE, 2013.
[2] Hu Q L, Huang Q Y, Han B, et al. MSR: A novel MPLS-like secure routing protocol for mobile ad hoc networks[C]∥International Conference on Networks Security, Wireless Communications and Trusted Computing. Wuhan, Hubei, China: IEEE, 2009: 129-132.
[3] Rao M, Singh N. Quality of service enhancement in MANETs with an efficient routing algorithm[C]∥IEEE International Advance Computing Conference. Gurgaon, New Delhi, India: IEEE, 2014: 381-384.
[4] Li L Y, Wu M Q, Chen Z Q, et al. Analysis and optimization of multipath routing protocols based on SMR[C]∥2nd International Conference on Signal Processing Systems. Dalian, Liaoning, China: IEEE, 2010: 205-209.
[5] Valera A, Seah W K G, Rao S V. Cooperative packet caching and shortest multipath routing in mobile ad hoc networks[C]∥22nd Annual Joint Conference of the IEEE Computer and Communications. San Francisco, CA, US:IEEE, 2003:260-269.
[6] Pham P, Perreau S. Multi-path routing protocol with load balancing policy in mobile ad hoc network[C]∥4th International Workshop on Mobile and Wireless Communications Network. Stockholm, Sweden: IEEE, 2002: 48-52.
[7] Aldosari F M, Alradady F. Localized QoS routing with end-to-end delay guarantees[C]∥Tenth International Conference on Information Technology: New Generations. Las Vegas, NV, US: IEEE Computer Society, 2013: 464-472.
[8] Du K M, Yang Y H. A QoS routing for maximum bandwidth in ad hoc networks[C]∥2010 Second International Conference on Future Networks. Sanya, Hainan, China: IEEE, 2010: 343-345.
[9] 王洁, 李明明, 刘建生, 等. 基于优先级AODV的扩展多路径路由协议研究[J]. 软件导刊, 2015,14(5): 158-161. WANG Jie, LI Ming-ming, LIU Jian-sheng, et al.Research on extended multipath routing protocol based on priority AODV[J]. Software Guide, 2015, 14(5): 158-161. (in Chinese)
[10] 尚硕. 无线Mesh网络多路径路由协议研究[D]. 长春：吉林大学, 2015. SHANG Shuo. Research on multipath routing protocol in wireless mesh network[D]. Changchun: Jilin University, 2015. (in Chinese)
[11] 3GPP. TS22.105 Technical specification group services and system aspects: services and service capabilities(Release 8)[S]. Valbonne, France: 3GPP, 2007.
An Improved Multi-path Routing Protocol in Mobile Ad Hoc Network
LI Xu1， QIU Song-qing1， PENG Jin-lin2， WANG Cong1
(1.School of Electronic and Information Engineering, Beijing Jiaotong University, Beijing 100044, China; 2.Beijing Institute of Tracking and Telecommunication Technology, Beijing 100092, China)
Multi-path routing protocol can effectively reduce the probability of communication interrupt and end-to-end delay by establishing and maintaining multiple alternate paths in mobile ad-hoc network. The current analysis methods of the number of alternate paths are unavailable for the complex wireless ad-hoc network transmission environment. The existing multipath routing protocols can’t meet the requirements of mixed services. In order to solve the above-mentioned problems, the models for single-path and multi-path routing protocols are established to analyze the effect of the number of alternate paths on the performance of multi-path routing protocol. An application-oriented ad hoc on-demand multipath distance vector (A-AOMDV) is proposed, in which many parameters, such as hop, average connectivity, minimum bandwidth and so on, are considered, and the best path is selected for any service. The simulated result shows that the delivery rate of data service can be increased by 25% and the average delay of voice service can be reduced by 10%～20% by adjusting the weights of parameters. The proposed protocol can selectively improve the properties of delay, reliability and available bandwidth for different services.
computer system architecture; mobile ad-hoc network; multi-path routing protocol; A-AOMDV; quality of service
2016-04-08
国家自然科学基金项目(61371068)；国家“863”计划项目(2015AA01A705)；国家科技支撑计划项目(2014BAK02B04)； 中央高校基本科研业务费专项资金项目(2014JBZ002)
李旭(1970—)，女，教授，博士生导师。E-mail: xli@bjtu.edu.cn； 仇颂清(1991—)，男，硕士研究生。E-mail: 14120111@bjtu.edu.cn
TN915.04
A
1000-1093(2016)11-2022-07
10.3969/j.issn.1000-1093.2016.11.009
