AODV带宽估计和链路稳定度的QoS扩展研究

孙小强，蔡茂国，陈剑勇，梁荣坚

(深圳大学计算机与软件学院，广东深圳518060)

目前对于Ad Hoc网络可以通过加入带宽、时延和链路稳定度等进行QoS保证。AVAODV［1］利用节点接收到邻居节点发送HELLO分组的机制进行链路稳定度的计算，但对链路稳定度并没有进行考虑。文献［2］介绍了一种基于令牌传送机制以及融入CDMA的混合令牌码分区多路接入(Token－Code Division Multiple Access)的MAC协议，模拟实验结果表明所提出的MAC机制能够有效地减少分组时延及缩小队列长度。SQAODV协议［3］在AODV协议加入带宽估计和链路稳定度选项，利用节点接收邻居节点广播RREQ分组的功率估计链路稳定度。CLQ－AODV协议［4］采用计算MAC层信道空闲时间比率估算节点剩余带宽，对AODV协议进行了带宽需求和时延要求的扩充。Xiaoxia Huang针对VANETS提出了一种有关节点不相关的多路径路由协议［5］，在文献［1］中有对节点不相关性优缺点的论述。QAODV_BC［6］路由协议采用了带宽估计、业务流接入控制和链路稳定度选项改进AODV协议的QoS性能。

AODV协议［7］是Ad Hoc网络一种比较成熟的按需距离向量路由算法，并且是一种支持“尽力而为”的路由协议，因此存在一些方面的不足［6］。首先，AODV协议在路由寻找的过程中，仅把跳数作为路径选择的依据。只考虑跳数会导致在节点发送报文时有可能带宽不足而使路由不断重启、丢包率过大或者时延过大。其次，AODV协议在进行路由寻找时，源节点只对首次接收到的RREP(路由回复)分组进行响应，对后到的路由请求分组直接丢弃，并没有考虑后到的RREP分组可能包含链路稳定度更好的路径。AVAODV协议中采用链路稳定度方法克服了上述AODV协议的一些缺点，QVAODV协议在AVAODV协议的基础上增加了带宽估计选项，采用链路稳定度与带宽估计相结合的方法来提高Ad Hoc网络传输多媒体数据的性能，并且还解决了AODV协议源节点只对首次到达的RREP分组进行响应的缺点。

1 QoS参数的计算

1.1 带宽的计算

带宽估计在研究Ad Hoc网络QoS性能时是一个很重要的参数。带宽估计一般指两个节点之间可用于数据传输的最大吞吐量。带宽估计会受到节点碰撞、空闲信道占用比率和回退时间等方面的影响［8－9］。AVAODV协议只考虑链路稳定度，而没有考虑带宽估计的因素。目前无线带宽估计有以下两种检测机制:一是测量MAC层的信道空闲率［3－4，6］;二是测量网络层单位时间的吞吐量。

由于QVAODV协议MAC层采用IEEE802.11协议，可以采用计算信道忙闲比的方法来计算节点的可利用带宽。在QVAODV协议采用将一段时间划分成m个相同的时间段，每隔一个时间段观察MAC层信道是否空闲，空闲信道个数记为n，节点的剩余带宽为

上述的带宽估计方法存在一个缺点，就是用过去一段时间的带宽来代替未来时间的带宽，得到的带宽可能不准确。为了解决这个问题，平滑处理剩余带宽，即

式中:B0=0.5b0;Bi表示节点在i时刻的剩余带宽;Bi－1表示节点在i－1时刻的剩余带宽;bi表示节点在i时刻由式(1)得到的剩余带宽;C表示节点在i时刻的最大带宽。

1.2 链路稳定度的计算

QVAODV协议中计算某条链路的链路稳定度首先需计算相邻节点的链路稳定度，得到该条链路所有相邻节点的链路稳定度之后，便可以计算这条链路的链路稳定度，具体计算过程参见文献［1］。根据上述计算链路稳定度方法来计算各个备选路径的链路稳定度，选择链路稳定度好并且满足带宽需求的路径作为最优路径。

2 QVAODV路由协议的实现

2.1 中间节点转发路由请求分组的优化

在AODV协议中，节点接收到RREQ分组后，便会建立或更新没有有效序列号的前一跳的路由。然后节点判断最近PATH_DISC_TIME(路由寻找时间)内是否接收到相同源节点ID(序列号)与相同RREQ_ID(路由请求序列号)的RREQ分组，如果已收到相同源节点ID与相同RREQ_ID的RREQ分组，节点会将后到的RREQ分组直接丢掉。AODV采用这种中间节点转发RREQ分组的策略并没有考虑后到RREQ分组所在路径的链路稳定度可能会高于先到路径的链路稳定度。由于AODV协议采取这种直接丢弃后到RREQ分组的方法，直接影响了AODV协议的性能。

在QVAODV协议中，根据带宽估计和链路稳定度的情况来决定是否对RREQ分组进行转发。虽然AVAODV协议也采用了链路稳定度选项对RREQ分组转发进行了优化，便仅仅考虑链路稳定度并不能适应数据流带宽需求的动态性变化。QVAODV路由协议只有在中间节点满足RREQ带宽要求并且链路稳定度不小于规定阈值时，才将中间节点添加到备选路径中，RREQ分组才会被该中间节点转发，否则丢弃该RREQ分组。这样的处理策略保证了所选路径的稳定性及高效性，提高了Ad Hoc网络传输数据分组的性能。

2.2 最优路径的选择

在AODV协议中，源节点只对首次到达的RREP分组进行响应，而对后到RREP分组采取丢弃的策略，有可能忽略后到RREP分组所在路径的链路稳定度可能会更好。QVAODV路由协议对于后到RREP分组采取不直接丢弃的方法，并且判断它的链路稳定度是否比路由表中相同目的节点的链路稳定度大且更新次数不超过设定好的阈值。当Ad Hoc网络传输数据分组时，可能会由于后到RREP分组所在路径链路稳定度更好而发生改变，但对于正在传送数据分组的业务流需求来说并没有什么影响，相反会由于链路稳定度的提高而使网络性能更好。

2.3 QVAODV 具体路由实现过程［1］

为了使QVAODV协议能够正常运行，需要对AODV协议的RREQ分组、RREP分组、BROADCAST_ID(RREQ广播分组缓存)、AODV_RT_ENTRY(AODV路由表项)及AODV_NEIGHBOR(AODV邻接表项)进行扩充，需要扩充的分组选项如表1和表2所示。

表1 AODV RREQ与RREP需要扩充的选项

表2 AODV广播分组缓存、路由表项与邻接表项需要扩充的选项

在QVAODV协议中，QVAODV RREQ分组比AODV RREQ分组增加了3个选项，分别是AHV选项、BREQ选项和备选路径节点ID序列，其中AHV表示链路稳定度，BREQ表示带宽需求。相应地，QVAODV RREP也增加了相同的3个选项。QVAODV RT_ENTRY比原先的AODV RT_ENTRY增加了AHV选项、BREQ选项和COUNT选项，COUNT选项表示目的节点收到RREP的个数。QVAODV BROADCAST_ID比原来的AODV BROADCAST_ID增加了COUNT_FORWARD选项，用来保存中间节点接收到RREQ分组的次数，如果超过了一定次数，则丢弃该RREQ分组。QVAODV_NEIGHBOR比 AODV_NEIGHBOR增加了COUNT_HELLO字段，用来保存邻居节点成功接收到HELLO分组的个数。相比较AVAODV协议而言，QVAODV协议的RREQ分组和RREP分组分别增加了BREQ带宽需求选项，以适应中间节点动态变化的可用带宽，并且QVAODV协议的 RT_ENTRY选项也比AVAODV协议增加了BREQ选项和COUNT选项。

在QVAODV路由协议中，若源节点需要向目的节点发送数据而源节点路由表中并不存在有效路由时，则启动路由寻找过程。从源节点发出RREQ分组，若遇到满足中间节点转发规则的节点则会被转发，如果RREQ分组被转发，中间节点ID会被记录到RREQ分组选项中，AHV值也会被更新。中间节点转发RREQ分组的规则:如果中间节点通过MAC层估计的带宽值大于等于RREQ分组所要求的带宽值并且满足原先AVAODV协议中间节点转发RREQ分组的判定条件，则中间节点转发RREQ分组，同时更新RREQ的AHV值，将转发节点的ID加入到RREQ分组中间节点序列中，并且将中间节点转发该RREQ分组的次数加1;否则，丢弃该 RREQ分组。QVAODV协议转发RREQ分组的规则比AVAODV协议增加了中间节点的剩余带宽是否大于等于RREQ的需求带宽判定选项。

源节点在第一次收到RREP分组时，建立相应的路由表项，将RREP分组的AHV值与BREQ值记录到路由表中，并且将路由表中的更新次数初始化为0。对于后到的RREP分组，则可以当作更新路由表项而不直接丢弃，是否丢弃还得看是否满足路由更新条件，并且采用更新次数来限制接收到的RREP分组个数。如果后到RREP分组的AHV值大于路由表中相同目的节点路由表项的AHV值且该路由表项的更新次数不大于15时，则更新该路由表项，同时将该路由表项的更新次数增加1;否则，将忽略后到RREP分组。

3 仿真实验结果与性能分析

利用 NS－2.35对 AODV协议、AVAODV协议和QVAODV协议的性能进行对比分析。

3.1 仿真实验场景

在Ubuntu 12.04操作系统下，采用NS－2.35仿真平台对QVAODV路由协议进行仿真模拟。仿真场景设置为1 000 m×1 000 m的大小，节点个数为25，随机布置在网络中，并且设置部分节点动态地移动，以模拟Ad Hoc动态环境。MAC层采用IEEE802.11协议，无线信道带宽为2 Mbit/s。节点的最大通信范围为250 m，数据分组大小为512 byte。仿真时间设置为800 s，业务流设置为CBR流，在本实验中有两条CBR流。为了验证QVAODV协议的性能，仿真了相同条件下的AODV协议和AVAODV协议进行参照对比。

3.2 性能评价

1)数据丢包率:(源节点发送数据分组的个数－目的节点正确接收到的分组个数)/源节点发送数据分组的个数。分组丢包率越低，数据分组成功传送到目的节点的比例越大。

2)平均路由开销:发送和转发的路由控制分组个数/目的节点接收到的数据分组。平均路由开销越小，路由协议效率越高。

3)平均端到端分组时延:所有数据分组从源节点到目的节点所花时间总和/目的节点成功接收到数据分组个数。端到端平均时延越小，数据传送所花费的时间越少。

3.3 实验结果分析

1)图1是AODV协议、AVAODV协议和QVAODV协议数据丢包率的比较，很明显可以看出，QVAODV协议比AODV协议数据丢包率要低很多，AVAODV协议和QVAODV协议的数据丢包率曲线几乎重叠在一起。实际上AVAODV协议与QVAODV协议的丢包率还是有差别的，由于图1的坐标轴刻度过大看不出两者的差异。为了更好地比较QVAODV协议与AVAODV协议的数据丢包率大小，特意将相同数据转发率下的AVAODV协议丢包率与QVAODV协议数据丢包率进行相减，得到的差值如果为正，则说明相同数据转发率下QVAODV协议数据丢包率要小于AVAODV协议数据丢包率。图2表示相减后得到的差值，由于QVAODV协议加入了带宽估计选项，相同数据发送速率下的QVAODV协议数据丢包率要比AVAODV协议要低些。

2)图3是AODV协议、AVAODV协议和QVAODV协议平均端到端分组时延的比较，可以看出，相同数据转发率下QVAODV协议的平均端到端分组时延要比AVAODV协议的平均端到端分组时延小。将AODV协议与QVAODV协议的平均端到端分组时延进行比较可以看出，数据转发率从360 kbit/s开始，QVAODV协议要明显比AODV协议的平均端到端分组时延小。

3)图4是AODV协议和QVAODV协议的平均路由开销比较，很明显可以看出，AODV协议的平均路由开销明显小于QVAODV协议的平均路由开销。从图5可以看出，QVAODV协议的平均路由开销要小于AVAODV协议的平均路由开销。

图1 数据丢包率的比较

图2 AVAODV与QVAODV数据丢包率差值

图3 平均端到端分组时延比较

图4 AODV与QVAODV平均路由开销比较

4 结语

QVAODV协议通过对AVAODV协议添加带宽估计选项以适应数据流带宽需求的动态性变化，并且针对AODV协议源节点只对首次到达的RREP分组进行响应的缺点进行了改进，源节点在一定的次数限制下选择链路稳定度最好与满足带宽需求的一条路径来进行数据分组的传输。仿真实验结果表明，QVAODV协议相比较AVAODV协议在数据丢包率、平均端到端分组时延和平均路由开销均有改进，尤其在平均端到端时延和平均路由开销方面效果显著。AODV协议与QVAODV协议在数据丢包率和平均端到端分组时延方面，QVAODV协议要明显好于AODV协议，尽管QVAODV协议的平均路由开销还远远大于AODV协议的平均路由开销。综上所述，所提出的QVAODV协议在Ad Hoc网络中性能表现优异，对于提高Ad Hoc网络数据传送性能有着重要的现实意义。

在实际Ad Hoc网络应用中由于节点是动态移动的，并且还要承担数据转发任务，如何降低节点的能量消耗［10］尤其重要，而且 Ad Hoc 网络还存在安全接入［11－12］的问题，非法节点的接入严重影响了Ad Hoc网络的QoS性能。因此，不仅需要考虑带宽估计和链路稳定度，而且还要考虑节点的能量限制、节点的安全接入等方面的因素。接下来准备结合节点的能量限制与节点的安全接入提出更好的带宽估计和链路稳定度算法。

图5 AVAODV与QVAODV平均路由开销比较

［1］ HOSSEN M，XIN Z，ZHENHUA L，et al.Jamming－resilient multipath routing［J］.IEEE Trans.Dependable And Secure Computing，2012，6(9):852－864.

［2］ LIU IS，FAMBIRAIT，XU H J.A hybrid token－CDMA MAC protocol forwireless Ad Hoc networks［J］.IEEE Trans.Mobile Computing，2008(5):557－560.

［3］梁荣坚，蔡茂国，张立海.Ad Hoc网络中基于链路稳定度的QoS路由协议［J］.计算机工程与应用，2010，46(32):105－107.

［4］陈丽芳，陈燕，徐白.基于跨层设计AODV的QoS扩展和仿真实现［J］.广西科学院学报，2011，27(3):221－227.

［5］ HUANG Xiaoxia，FANG Yuguang.Performance study of node－disjoint multipath routing in vehicular Ad Hoc networks［J］.IEEE Trans.Vehicular Technology，2009，58(4):1942－1950.

［6］梁荣坚.移动Ad Hoc网络QoS路由算法的研究［D］.深圳:深圳大学，2010.

［7］陈林星，曾曦，曹毅.移动Ad Hoc网络——自组织分组无线网络技术［M］.北京:电子工业出版社，2012.

［8］吴大鹏，武穆清，甄岩.移动自组织网络可用带宽估计方法研究进展［J］.通信学报，2010(4):103－115.

［9］ CHEIKH S，CLAUDE C，GUILLAUME C，et al.Bandwidth estimation for IEEE 802.11－based Ad Hoc networks［J］.IEEE Trans.Mobile Computing，2008(10):1228－1241.

［10］廖勇超.Ad Hoc网络节能问题研究［D］.长沙:中南大学，2009.

［11］ GANG X，CRISTIAN B，LIVIU I.A policy enforcingmechanism for trusted Ad Hoc networks［J］.IEEE Trans.Dependable and Secure Computing，2011(3):321－325.

［12］ YUDHVIR S，YOGESH C.Security and network performance evaluation of KK＇cryptographic technique inmobile Ad Hoc networks［C］//Proc.IEEE International Advance Computing Conference.［S.l.］:IEEE Press，2009:1152－1154.