ad_hoc网络中基于链路稳定度的qos路由协议

2010， 46 （32）Computer Engineering and Applications计算机工程与应用 1引言 无线自组网 （Ad hoc） 是一种在没有无线基础设施下， 使 用无线多跳中继方式运行的网络。由于具有较高的灵活性、 移动性、 自组织以及随时随地接入等特点， Ad hoc网络已经 广泛应用于紧急救灾， 智能通信、 环境监测等各种军用和民用 领域。随着音频、 视频等多媒体业务的增加， 传统的Ad hoc 路由协议已经不能满足QoS需求。因此， 研究提供带宽、 延时 等QoS保障的路由协议， 对改善Ad hoc网络QoS性能有非常 重要的意义。 目前， Ad hoc网络的QoS路由协议一般通过加入带宽或 延时等 QoS 信息来提供 QoS 保障。Q_AODV 协议 1是在 AODV 基础上对路由表以及路由请求 RREQ 和路由回复 RREP报文进行扩充， 附加QoS信息来实现QoS路由。文献2 比较了含有扩展Hello协议信息的Q_AODV_HELLO和不含 扩展Hello协议信息的Q_AODV协议的性能。QoS-OLSR协 议3从支持QoS的角度对OLSR进行了扩展， 改进了MPR的 选取方法， 同时也利用 MPR 达到了接入允许控制的目的。 CEDAR4是一种基于动态选举核心节点的QoS路由协议， 使 稳定且带宽资源丰富的链路在网络上广泛传播， 不稳定或带 宽资源贫乏的链路信息只在本地传播。S.Chen5提出了基于 “票证” 探询的多路径QoS路由协议TBR， 避免搜索路由时产 生广播风暴。QRME协议6采用移动预测思想， 利用GPS提供 的位置和移动信息， 建立稳定且满足QoS需求的路径。 AODV协议是一种按需路由协议， 同时具备了DSDV和 DSR协议的优点7。但AODV协议在传输多媒体数据时还存 在一些不足， 如只把跳数作为选择最佳路由的依据， 忽略了传 输路径的稳定度； 其次， AODV协议没有考虑到建立的路径是 否满足业务带宽需求； 在发现路由时， 中间节点和目的节点只 把首次接收到的请求分组 （RREQ） 作为它的逆向路径进行广 播或回复， 而把后收到同一请求分组全部丢弃， 忽略了到后收 到请求分组还可能包含更稳定的路径。针对AODV协议的不 足， 提出了基于链路稳定度的QoS路由协议SQAODV， 以提 高Ad hoc网络传输多媒体数据时的整体性能。 2QoS参数的估计 2.1带宽的计算 带宽保证是QoS的一个重要方面。如果节点传输的业务 流的带宽超过了链路的承载能力， 必然导致链路层的丢包。 节点剩余带宽的估计主要有两种方案。方案一是节点统 计在网络层或MAC层接收到的数据分组的个数。由于节点 Ad hoc网络中基于链路稳定度的QoS路由协议 梁荣坚， 蔡茂国， 张立海 LIANG Rong-jian， CAI Mao-guo， ZHANG Li-hai 深圳大学 计算机与软件学院， 广东 深圳 518060 Department of Computer Science and Software Engineering， Shenzhen University， Shenzhen， Guangdong 518060， China E-mail： boy201 LIANG Rong-jian， CAI Mao-guo， ZHANG Li-hai.Link stable QoS routing protocol for Ad hoc network.Computer Engi- neering and Applications， 2010， 46 （32） ： 105-107. Abstract：This stable link QoS routing protocol SQAODV is proposed based on AODV.It can satisfy the band width con- straint， estimate the stable parameter by the received packet power， and choose the most stable and QoS path from several paths in the destination node in the routing detected process.Simulation results show that the performance of SQAODV is better than AODV in packed delivery ratio， average peer-to-peer delay and routing cost. Key words：stable routing； Quality of Service （QoS） ； Ad hoc 摘要： 在AODV的基础上提出了一种基于链路稳定度的QoS路由协议SQAODV。该协议通过带宽约束和链路稳定度的估计， 在路径发现过程中， 从到达目的节点的多条路径中选择一条最稳定且满足QoS需求的路径返回源节点提供QoS保证。仿真的实 验结果表明， 改进后的SQAODV协议， 在分组到达率和数据平均传输延时方面的性能都有改善。 关键词： 稳定性路由； 服务质量； 移动自组网 DOI： 10.3778/j.issn.1002-8331.2010.32.029文章编号： 1002-8331 （2010） 32-0105-03文献标识码： 中图分类号： TP393 基金项目： 国家自然科学基金 （the National Natural Science Foundation of China under Grant No.60602066） 。 作者简介： 梁荣坚 （1985-） ， 男， 硕士生， 主要研究领域： 无线移动自组网； 蔡茂国 （1966-） ， 男， 教授， 硕士生导师， 主要研究领域： 无线移动自组网， 人脸识别； 张立海 （1984-） ， 男， 硕士生， 主要研究领域： 无线传感器网络。 收稿日期： 2009-03-27修回日期： 2009-05-25 105 Computer Engineering and Applications计算机工程与应用2010， 46 （32） 和其他节点公用物理信道， 节点需要在网络层或MAC层利用 Hello协议收集其一跳范围内邻居节点的带宽。节点实际占 用的带宽等于其一跳邻居节点收发的数据分组大小的总和8。 方案二是在统计信道空闲的时间。如果MAC层是采用TD- MA协议9， 用空闲时序的个数计算剩余带宽。如果MAC层 是采用802.11协议， 利用节点信道忙闲的时间比计算节点的 剩余带宽。 以上两种方案都有一个共同的缺点它们都用过去一 段时间的带宽代替未来一段时间的带宽， 预测出的带宽都不 是很准确， 这是因为带宽是不断变化的。两种实现方法也各 有优缺点。方案一的实现相对简单， 但增加了路由的开销； 方 案二实现比较复杂， 但不会增加额外的开销。本文采用方案 二来计算信道的带宽， 并采用了线性递减模型使带宽参数平 滑变化： Bi=(1-)*Bi-1+*bi（1） 其中，Bi表示节点在第i时刻的剩余带宽，Bi-1表示节点在i-1 时刻剩余带宽，bi表示节点在第i时刻从链路层获取的剩余带 宽。是(01)区间内可调的权值。 2.2稳定系数的计算 Ad hoc网络在修复断裂路由时需要很大的代价， 因此选 择稳定度高的路径进行数据传输对提高网络的性能有很重要 的意义。稳定系数计算的方法有很多种7， 本文利用节点接收 到邻居节点广播的RREQ分组的功率估计链路稳定度。设S 为源节点， D为目的节点。Si为路径上第i个中间节点， 源节 点通过路由请求建立的路径 path 可以表示为(SS1S2 SiSjD)。 第i条链路的稳定度： Si= Preceive-Pthreshold Psend (ipath)（2） 路径path的稳定度： Spath= i Si(ipath)（3） 其中，Psend表示节点发送数据分组的信号强度。一般来说， Psend和Pthreshold是一个常数。根据公式 （2） 可知节点接收的功 率越大， 稳定度就越高。 3SQAODV路由协议 节点在广播发现路由的分组时， 由于节点间存在信道竞 争的问题， 节点只利用首次收到的请求分组RREQ建立的路 由并不一定是最稳定且满足QoS需求的路径。本文分别对中 间节点和目的节点收到路由请求分组RREQ的处理进行如下 优化。 3.1中间节点的路径优化策略 在AODV协议中， 当中间节点收到了第一个请求路径的 分组RREQ就建立逆向路由， 并广播RREQ分组。该节点收 到其他邻居节点转发的重复RREQ分组就直接丢弃。例如， 图1中S为源节点， D为目的节点。S发起路径请求， 广播路由 请求分组RREQ， 由于信道竞争的原因， 中间节点C可能首先 收到来自F的转发， 即C首先建立逆向路径SAFC， C还会收到 E和B的转发， 就直接丢弃。在移动几率和各个节点负载相同 的情况下， 路径SEC在稳定方面和传输延时方面都要比SAFC 好， 因为SEC的跳数要比SAFC小， 且A和F移出S和C的通信 范围的几率更高。 针对以上情况， SQAODV协议在收到重复的RREQ不是 简单丢弃。而是对比新收到的分组建立的路径是否比已建立 的路由更稳定。如果是， 即用后收到的 RREQ 更新路由表。 否则， 丢弃重复的RREQ。在节点收到多个重复的RREQ， 只 对第一次收到且满足QoS需求的请求分组RREQ进行转发， 而后收到的RREQ只用作更新路由表。当分组传输目的节点 时， 前面的路径可能因为收到更稳定的路径改变了， 但对于满 足业务流的需求并没有影响， 因为路径上的节点保持的稳定 度是大于或等于实际路径的稳定度。 3.2目的节点最优路径的选择 在AODV协议中， 目的节点收到请求分组RREQ时， 同样 只对收到第一个请求分组进行处理， 后到达的重复RREQ直 接丢弃， 忽略了后到达分组可能包含更稳定的路径。 SQAODV在目的节点设立一个路由回复的定时器。在 第一个路径请求分组到达目的节点后， 暂不发送回复分组 RREP， 启动一个前向路径回复定时器， 并等待和暂存来自其 他路径的请求分组RREQ。当定时器到期后从暂存的几条路 径中选择最稳定的路径回复源节点。当目的节点已经收到一 定数目n的路径而定时器还没有超时， 即向源节点发送路由 回复分组RREP， 并撤销定时器， 而无需等待到定时器到期再 发送RREP分组。如果目的节点向源节点在发送了回复分组 RREP后， 还收到来自邻居节点的重复请求分组RREQ则不再 处理。 3.3SQAODV协议的路由过程 SQAODV协议需要对路由表和路由请求分组进行扩展， 在路由表中和RREQ分组中增加两项， 分别记录业务流带宽 需求Breq和路径上各节点稳定度的乘积。 当源节点S需要向目的节点D发送数据而S路由表中没 有有效路径时， 源节点S便启动路由发现过程。设S需要的带 宽为Breq。首先， 源节点 S 向邻居节点广播路由请求分组 RREQ， 中间节点i第一次收到该分组， 便判断节点本自身的剩 余带宽Bi是否满足条件BiBreq， 如果满足条件， 在节点的路 由表中添加一条路由记录并记录路径稳定度， 同时向其邻居 节点转发RREQ分组； 如果第一次收到RREQ且节点剩余带 宽不满足带宽需求便丢弃RREQ分组。如果中间节点不是第 一次收到该分组且满足业务QoS需求， 就判断新收到的路径 是否比已有的路径更稳定。如果是用新路径则更新路由表， 否则丢弃分组。为了避免环路的出现， 中间节点只对第一次 接收到的请求分组RREQ进行转发， 后收到的均不再转发。 目的节点在第一次收到路径请求分组RREQ时， 立即启 动一个定时器。在定时器还没有到期前， 目的节点还会收到 来自其他路径的请求分组RREQ， 目的节点把收到的路径保 存下来， 如果定时器到期或者收到路径到达一定的数目n时， 目的节点在收到的路径中选择最稳定的路径， 向源节点发送 A F SE C D B 图1中间节点收到请求分组的处理 106 2010， 46 （32） 梁荣坚， 蔡茂国， 张立海： Ad hoc网络中基于链路稳定度的QoS路由协议 路由回复分组RREP。源节点在收到路由回复分组后便可以 利用该路径向目的节点发送数据了。 4仿真实验结果和性能分析 4.1仿真实验场景 在Linux操作系统下， 采用NS-2.33仿真平台对SQAODV 协议进行仿真模拟。地形设置为1 000 m1 000 m的平面网 络， 节点个数50个， MAC协议采用IEEE 802.11 DCF， 信号的 传播方式是双径地面反射模型 （two-ray） 。节点的最大通信范 围为250 m， 信道带宽为2 Mb/s。数据分组的长度为512 Byte， 仿真的时间为200 s。以恒定的CBR比特流模拟节点的实时 业务。为了验证SQAODV协议的性能， 仿真了相同条件下的 AODV协议作为参照对比。 4.2性能参数的选择 （1） 分组到达率： 用来衡量目的节点成功接收源节点发送 数据包情况。目的节点接收到数据包的个数/源节点发送数 据包的个数。 （2） 平均端到端延时： 指单位数据包从源节点到目的节点 所需要的时间。（目的节点接收到数据包的时间-源节点发送 数据包的时间） /源节点发送数据包的个数。 （3） 路由开销： 用来衡量路由查找和路由维护引起的额外 开销。发送和转发的路由控制包个数/接收到的数据包个数。 4.3仿真实验结果 由于SQAODV协议考虑了业务数据流的QoS需求和链 路的稳定度， 在发现路径过程中， 对中间节点选择路径进行优 化， 并从目的节点多条路径中选择最稳定的路径来传输数据， 从图2和图3看来， SQAODV协议的分组到达率和传输延时 的网络性能都优于AODV协议。 在图4中， 由于SQAODV协议在请求分组和回复分组增 加了带宽和链路稳定度等QoS信息， SQAODV协议的路由开 销略高于AODV协议。另外， 由于SQAODV协议加入带宽参 数的限制， 当网络业务繁忙时， 有些业务可能因为找不到满足 QoS的路径而不能接入。 5结论 通过在路由请求分组中加入带宽参数的限制和链路稳定 度信息， 使源节点找到满足业务QoS需求且比较稳定的路径； 通过对节点收到路由请求分组的处理机制进行优化， 从目的 节点收到的多条路径中选择最稳定的路径用于传输数据， 减 少了路径断裂的概率， 从而延长了路径的平均寿命。仿真实 验结果表明， 改进后的 SQAODV 协议虽然路由开销略有增 加， 但在数据传输延时和分组的到达率方面都有改善， 在一定 程度上提高了Ad hoc网络传输多媒体数据的性能。 在Ad hoc网络中， 多媒体数据传输是一个复杂而综合性 的问题。要利用高稳定性的路由来获得更好的QoS性能， 还 需要进行更为深入的研究。 参考文献： 1 Perkins C E， Royer E M， Das S R.Quality of service for ad hoc on-demand distance vector routingS.Draft-perk in s-ma- net-aodv qos-02.txt， IETF Internet Draft， 2003： 1-37. 2 de Renessse R， Ghassemian M， Friderikos V， et al.QoS enabled routing in mobile Ad hoc networksC/Fifth IEE International Conference on 3G Mobile Communication Technologies， 2004： 678-682. 3 Boukhalfa.QoS support in a MANET based on OLSR and CBQC/IEEE， Sixth International Conference， April 2007： 22-28. 4 Sinha P， Sivakumar R， Bharghavan V.CEDAR： A core-extraction distributed ad hoc routing algorithmC/IEEE IN FOCOM 99， New York， 1999： 1454-1465. 5 Chen Shi-gang， Nahrstedt K