文档介绍:Ad hoc网络中一种新的路由选择算法
摘 要:提出了一种基于网络总时延最小的路由路径选择算法。该算法根据链路的时延来进行路由路径选择,从而达到网络总时延最小的目的。仿真表明,该算法可以动态调整网络路由路径,从而使网络总时延达到最小。??
关键词:Ad hoc; 路由路径;时延??
中图法分类号:TP393文献标识码:A
文章编号:1001―3695(2007)02―0316―02
移动Ad hoc网络(MANET)是指一组带有无线收发装置的移动节点组成的一个多跳的临时性的自组织系统。整个网络系统没有固定的基础设施,所有节点都是移动的,并且都可以动态方式动态地保持与其他节点的联系。??
由于节点移动、信道干扰和能源消耗等因素,Ad hoc网络的拓扑结构具有动态变化特性,这给高性能路由协议的设计带来很大的挑战。迄今为止,已有多个Ad hoc网络路由协议被用于Ad hoc网络,如AODV[1],DSDV[2]和DSR[3]。但是多数路由协议在路由选择时都是以跳数最少作为选择的依据。由于一条路径的带宽是有限的,当很多节点选择此路径作为路由路径时,将会造成网络拥塞,从而使网络时延加大。因此本文把时延作为评估参数,提出了一种新的路由选择算法。在本路由选择算法中,当路由协议发现
N条路径时[2],将以使网络总时延最小作为路由路径选择的依据。??
1 理论分析??
影响Ad hoc 网络性能参数有很多,主要有时延、分组丢失率等。但是笔者只选用了网络时延作为路由路径选择的依据,这是因为一条路径的时延容易获得,只需要一条路径两端的源目节点间发送检测分组即可得到。而其他参数很难用简单的方法实时测量到,如分组丢失率。所以时延具有最重要的实际意义[4],因此将时延作为路由选择的基准。??
我们设计路由选择算法的目标是使整个网络的性能达到最优化,在这里根据式(1),在M条路径中选择一条Fi最小的路径作为可选择的路由路径,即分组x所选择的路由路径为
对于Ad hoc网络中的单个节点来说,通信时延来源于排队时延、处理时延和传输时延等。对于单个数据包而言,处理时延和传输时延较为固定,而排队时延受网络的拥塞程度影响,变化较大。在排队论中,节点的接收和发送可以用马尔可夫M/M/1服务模型[7]分析。根据Little公式可知,数据包的平均时延符合以下关系:
在有线网络中,路由节点的接收和发送能力固定不变,而且互不影响。在Ad hoc网络中,节点的接收和发送共享相同的无线信道,相互影响。设节点的处理能力为B(接收和发送共享),那么μ=B-λ,所以数据包的平均时延关系式变为
根据上述分析,可以计算每条链路平均时延,据此就可选取其中使网络总时延最小的链路作为最终选择的路由路径。
2 算法描述??
在本文提出的基于网络总时延最小的路由路径选择算法执行时,只要建立合理的时延数学方程,如式(4)所示,就可以进行基于网络总时延最小的路由路径选择了。但是式(4)依赖于路径的有效带宽和固有流量。在Ad hoc网络中,它们都是动态变化且缺乏有效的办法来测量。因此在实际网络中,仅根据式(4)来进行路由选择是不可行的,式(4)仅可用