改进多路径基础票QOS路由算法研究与应用

摘 要:QOS路由协议算法效率的高低直接影响到网络的路径传输、负载平衡、洪泛控制,如何一次性发现满足QOS路由是网络技术领域的一个重要的课题。本文通过对传统基础票路由算法机制的分析设计出改进多路径组播基础票路由,通过实例验证与分析证明该算法在一次性发现满足qos路由方面要优于其他算法。

关键词:多路径基础票 路由 设计

中图分类号:TP39 文献标识码:A 文章编号:1007-3973 (2010) 01-051-02

1多路径基础票QOS路由概述

QOS路由协议是一种单播多路径传输协议,源头节点与目的节点之间存在着多条路径,本节将针对在MTBP协议修改的基础上提出一种新的多路径多棵树组播QOS路由协议SMCBP(Super Multi Path Card Based Probing Routing Protocol),这种新的协议借助了TBP、MTBP协议和IMB令牌环协议,协议中采用了“带等级(权值)的令牌”,这种处理思想的目的是尽最大的可能减少广播开销,降低洪泛,但考虑到无线自组通信网络中跳跃数目最少的路径不一定满足QOS要求,故废除TBP中找寻不满足QOS要求路径的权值少于一定值时将拥有“红牌”,最大权值赋予“绿牌”,权值一般者赋予“蓝牌”,被授予“红牌”的节点的带宽和即时数据请求将被暂停,留下的资源以保证最大可能地找到多条满足QOS要求的路径。MTBP采用按需路由协议的方式建立路由,以链路带宽作为QOS参数,在限制洪泛的前提下,通过一次路由发现过程,能够在源、目的节点间建立若干条不相交的路径,可以平衡负载从而延长网络的生存时间。而SMTBP则借助“GPS公网”对其节点的即时状况实时报告并且评估,结合“GPS公网”的实时状态和限制泛洪的前提下一次性发现满足QOS路由,同时保证节点有多路径传输、负载平衡、限制洪泛、控制开销。

2改进多路径组播基础票QOS路由SMCBP概要设计

SMCBP多路径QOS路由协议中引入了“蓝牌”节点/路径,这种蓝牌节点/路径称为SMCBP多路径QOS路由协议中的备份节点/路径,本文研究的无线自组通信网络SMCBP多路径QOS路由协议还将蓝票节点暂存到特定的区域,对“蓝牌”路径的权值与最大权值进行对比进行排序,逐级给出备份节点/路径,当“绿牌”路径的权值在降低时,SMCBP可以通过“GPS公网”模块获取即时的状态,同时在被选节点种搜寻合适的“蓝牌”节点/路径作为新的“绿牌”节点/路由,其过程如下图1所示。

图1SMCBP多路径QOS路由角色变换备份机制

3SMCBP多路径QOS路由算法详细设计

3.1探针与角色转换的路由发现过程

本文采用的是先“探针”后“授牌”的处理方式,图2中显示,基于探针与角色转换获得的“绿牌”路由是:S-2-4-7-A,备份路径(“蓝牌”路径)是:S-3-6-8-A,此时被抛弃的路径是S-5。其过程是:以S为出发节点通过探针发现节点3、节点5、节点2是其邻节点,其中S-3、S-5和S-2的权值分别是3.12、2.90和2.93,以S-3的权值最大,s-5的权值最小,所以抛弃s-5,对节点5暂时授予“红牌”;紧接对节点3和节点2重复前面的步骤发现3的邻节点为6,2的邻节点为4所以S-3-6和S-2-4都为备份节点/路径,但是S-2-4的权值为6.34大于S-3-6的权值4.12,此步骤给路径:S-2-4授予“绿牌”,而s-3-6授予“蓝牌”;此时节点4有5和7邻节点,由于4-5的权值为1.61小于4-7的权值2.12,所以还是选择节点7授予绿牌,新的路径为S-2-4-7,最后还发现7只有1邻节点A,而且A是目标节点,于是给节点A授予绿牌,采用类似的方法处理S-3-6-8-A,最终得出结论为:S-2-4-7-A为此时的可靠路由,S-3-6-8-A为备份路由。前面已经提及到目的节点A在完成探针路径确认与分组后,SMCBP协议可以沿着网络中建立好的反向路由发送响应分组,在有效的备份路由和确定路由中可以根据其路径的逆向路径到达源节点,使其在网内的邻节点个数至少大于,其中是无线自组通信网络此时的节点数目,通过激活并调度被抛弃节点来获取活跃路由的成功率在62.19%左右。

图2 探针与角色转换路由发现过程示意图

3.2 SMCBP多路径QOS路由分组的传递与备用路径的建立

可以把脱离无线自组通信网络的节点调度回来获取活跃路由的实用价值不高,而且存在着脱离节点无法调回的众多因素,本文还提出另外一种获取活跃路由的策略就是通过“GPS公网”获取所有节点之间的位置信息,同时获取即即时通信的源头节点和目的节点序列,查看这些节点之间是否可以直接通信并构筑可靠的“绿牌”路由,如果这些节点序列之间存在可靠“绿牌”路由的话,那么其他节点是否脱离网络都对此刻的通信没有影响,但是必须把脱离节点记录到脱离节点缓冲区内,以备后用。源节点通过一次路由发现过程建立了若干条不相交但目的节点都是A的活跃路径,同时中间节点也建立了若干条目的节点是A的备份路由。由于响应分组是采用探针分组建立的反向路由传播,所以SMCBP协议更能支持双向链路。

对于路由与数据传送响应分组回到源节点后,路由建立完成,开始传送数据分组,如果一定时间内源节点仍未收到响应分组,则开始新的路由请求过程。所有路由都有超时机制,若超时,则将路由标记为失效,释放带宽资源。此处假设节点8因为电力供应不足,而导致此时S到A的备份路由中断,显示出的节点8的带宽为0,TTL大于规定的允许范围,能量持续时间为:0,移动速度为无限大,那么此时可以激活节点5,并且把节点5调度到原来8的通信范围以内,并且通过“GPS公网模块”保证网络的连通可能。

3.3SMCBP路由维护

SMCBP协议设计了两种路由维护方法:借助“GPS公网”的位置信息和MTBP来启用备份路由和本地路由修复。假设节点N检测到与下一跳节点K间链路断裂,经由链路的路径失效时,报告失效的路由,同时节点N首先查找自身路由表中有无到达目的节点A的备份路由,如果存在备份路由,并且该备份路由处于有效状态,则删除失效的活跃路由,将备份路由标记为活跃路由替换失效路由,转发数据分组,如下图3和4所示。图4中由于节点2实效,原有的“绿牌”路由:S-2-5-K-A断裂,于是考虑“蓝牌”路径:S-3-6-7-A,此时结合“GPS公网”内邻节点表信息获取原来节点2的邻节点是S、5、6,此时可以暂时删除S-2、2-5、2-6这3条基本路经,把2变成灰色送入异常缓冲区。

图4 节点2实效导致“绿牌”路径断裂

4多路径组播QOS路由仿真分析

本文对无线自组通信网络多路径QOS组播路由内组播数与算法效率的仿真关系如图5所示,为了考察网络代价和呼叫成功率随着组播组数目大小的增加而产生的变化,网络负载和QoS的要求不发生过大的变化。在初始化阶段,网络负载设为33%, QoS的带宽要求设为4个单位(每个单位为512Kbps),时延位50毫秒到100毫秒的允许范围,无线自组通信网络内的各个节点最低保持连接时间为100秒,移动初始速度为15米/秒,证明本文的改进策略具有一定的可靠性。

参考文献:

[1] 赵志峰,郑少仁.Ad Hoc网络体系结构研究[J].电信科学,2001,17(1): 9-13.

[2] 张 品.网络中Qos路由问题的研究[D].博士论文.成都:电子科技大学,2004年11月.

[3] 李腊元,李春林.计算机网络技术(第2版)[M].北京:国防工业出版社,2004.7.