最短路径路由算法的扩展_最短路径路由算法具体步骤

　　摘要：本文主要从QoS度量的可乘性、最小性两个方面对最短路径路由算法进行扩展，从而找出了最可靠、最宽的路径。并通过MATLAB6.1进行了实例仿真。 　　关键词：QoSR；最短路；最可靠线路；最宽线路；Dijkstra
　　中图分类号：TP311文献标识码：A文章编号：1009-3044(2007)18-31642-01
　　Extensions of the shortest-path algorithm
　　SHENG Hong-yan
　　(Institute of Physics & Electronic Engineering,Ludong University,Yantai 264025,China)
　　Abstract:This paper aims at giving an extensions of the shortest-path algorithm to get the most reliable path or the widest path by considering the multiplicity and the minimum of QoS, then a example is computed using the proposed algorithm.
　　Key words:quality of services routing;shortest path;most reliable path;widest path;dijkstra
　　
　　1 引言
　　
　　随着多媒体技术的飞速发展，Internet上出现了非传统数据通信的应用，如IP电话、视频会议、视频点播、电子商务等。现有的尽力传送的internet无法运载对网络资源和服务有特定要求的通信。QoS(Quality of Service)致力于解决这个问题。
　　网络研究主要通过两个途径提高QoS：一个是节点控制；另一个是网络控制。节点控制的策略包括流量整形、节点缓冲区管理、队列调度等。网络控制通过对路由的控制来提高网络的性能，所以QoSR（QoS-based Routing）成为解决服务质量问题的一项关键技术。其目标是为进入网络的数据流（业务）选择满足其服务质量要求的路径，同时保证网络资源的有效利用。本文主要从可靠性、带宽两个方面对最短路径算法做一些扩展。
　　
　　2 最短路径路由
　　
　　最短路径路由是一项有多种应用形式并被广泛使用的技术。如L-S算法、OSPF协议等。它的基本思想是：建立一个子网赋权图 ，图中的每个节点 代表一台路由器；每条边 代表一条通信线路；边上的权值 用于衡量路径长度的，可以是跳数、物理距离、带宽、平均流量、通信开销、队列长度、传输延迟以及是多因素的一个函数。为了在一对给定的路由器之间选择一条路由路径，路由算法只需在图中找到这对节点之间的最短路径即可。Dijkstra算法是计算图中两个节点之间最短路径的经典算法。
　　定义1 加权图的邻接矩阵
　　设G(V,E)是一个加权的无向图，每条边都赋与一个数，V={v0,v1,…,vn}，则G的邻接矩阵A=(aij)n×n，其中
　　aij=wij, 若（vi,vj)∈E，且wij是它的权0, 若i=j∞,若(vi,vj)?埸E
　　Dijkstr算法的基本思想：是生长一棵以v0为根的最短路树，在这棵树上每一顶点与根之间的路径皆为最短路径。
　　Dijkstra算法步骤[1]：
　　S：具有永久标号的顶点集；
　　V：图的顶点集；
　　L(v) ：顶点v的标记；
　　f(v)：顶点v的父亲，用以确定最短路径链；
　　(1)输入加权图的邻接矩阵A=(aij)n×n；
　　(2)l(v0)← 0,?坌v≠v0,l(v)←∞,S←{v0},u←v0；
　　(3)?坌v∈ S=V-S,若l(v)＞l(u)+w(u,v)则l(v)←l(u)+w(u,v),f(v)=u；
　　(4)设v"是使l(v)取最小值的S中的顶点，令S ←S∪{v"},u←v" ；
　　(5)若S≠?�，转(3)；否则，停止。
　　使用该算法的路由协议有一个缺点：在选择路由时，即使源端到目标端之间存在“更好的”路径，只要不是最短路径也不会使用，这可能会导致某些线路空闲而另外一些线路繁忙甚至拥塞。
　　3 最可靠路径路由[2]
　　文件传输、电子邮件、web访问和远程登录等应用对于可靠性有很严格的要求，任何一位都不允许被错误递交。为了实现这个目标，通常的做法是，发送方计算每个分组的校验和，接受方验证此校验和。然而，数据流在传输的过程中，可以通过选择一条最可靠的线路来满足这类应用所要求的服务质量。
　　定义2 最可靠路径
　　定义3 加权图的邻接矩阵
　　设G(V,E)是一个加权的无向图，每条边都赋与一个数，V={v0,v1,v2...vn}，则G的邻接矩阵M=(mij)n×n，其中
　　mij=wij，若(vi,vj)∈E，则wij是它的权0， 若i=j(vi,vj)?埸E
　　最可靠路由的思想与求最短路径的思想是相同的，所以将最短路径的算法稍作修改后即可：
　　S：具有永久标号的顶点集；
　　V：图的顶点集；
　　l(v)：顶点v的标记；
　　f(v)：顶点v的父亲，用以确定最可靠路径链；
　　(1)输入加权图的邻接矩阵M=(mij)n×n；
　　(2) l(v0)←1,?坌v≠v0,l(v)←0,S←{v0},u←v0；
　　(3) ?坌v∈ S=V-S,若l(v)＜l(u)×w(u,v)则l(v)←l(u)×w(u,v),f(v)=u；
　　(4)设 v"是使l(v)取最大值的S中的顶点，令S ←S∪{v"},u←v" ；
　　(5)若S≠?� ，转(3)；否则，停止。
　　
　　4 最宽路径路由
　　
　　带宽是网络发展的真正瓶颈。首先，电话、视频会议，视频点播等多媒体应用对带宽有很高的要求，如果带宽太低，将会引起画像质量差以及马赛克现象。其次，在网络互联中，各个子网所允许的带宽是不同的，但是低带宽的链路决定了网络的整体性能，而且往往会引起拥塞。因此，在进行路由时，为了满足数据流的带宽要求和尽量避免拥塞现象，选择一条瓶颈带宽最大的路径。
　　定义4 瓶颈带宽[3]
　　当然，求最宽路径的思想与最短路径路由是一致的，所以将最短路径的算法稍作修改后，即可求最宽路径：
　　S：具有永久标号的顶点集；
　　V：图的顶点集；
　　l(v)：顶点v的标记；
　　f(v)：顶点v的父亲，用以确定最宽路径链；
　　(1)输入加权图的邻接矩阵M=(mij)n×n；
　　(2) l(v0)← ∞,?坌v≠v0,l(v)←0,S←{v0},u←v0；
　　(3) ?坌v∈ S=V-S,若l(v)＜min{l(u),w(u,v)}则l(v)←min{l(u),w(u,v)},f(v)=u"；
　　(4)设v"是使l(v)取最大值的S中的顶点，令S ←S∪{v"},u←v"；
　　(5)若S≠?�，转(3)；否则，停止。
　　
　　5 实例仿真
　　
　　图1是本文仿真的网络拓扑图，每条边用（distance，reliability，bandwidth）表示，其中的元素分别代表链路的距离、可靠性和可用带宽。用MATLAB6.1进行仿真的结果如下：(1)、通过最短路算法，得出一棵以 为出发点的最短路树如图2：
　　图1 网络拓扑
　　其中， a到a,b,c,d,e,f,g,h各顶点的最短距离分别为2,7,1,3,6,9,12
　　图2 最短路树
　　(2)通过最可靠路由算法，可得一棵以a为出发点的最可靠路树如图3：
　　a到b,c,d,e,f,g,h各顶点的最大可靠度分别为0.3,0.6,0.5,0.12,0.36,0.4201.8
　　(3)、通过最宽路径路由算法，得到一棵以 为出发点的最宽路树如图4：
　　图3 最可路靠树 图4 最宽路树
　　a到b,c,d,e,f,g,h各顶点的最大瓶颈带宽分别为7,7,4,7,4,6,5
　　
　　6 结束语
　　
　　本文主要是从QoS度量的可乘性、最小性两个方面对最短路径路由进行扩展，从而可以找出最可靠、最宽的路径，这样可以为满足应用的某一单方面的服务要求提供一条最优的路径。此路径也可作为一个备选路径，根据应用的要求来决定的。一般来讲，应用都是要求满足多方面的服务要求，但是寻找一条满足两个或多个服务质量要求的可行路径是多约束优化问题，属于NP完全问题。目前，许多研究者使用智能算法对这类问题求解，并取得很好的成果。
　　
　　参考文献：
　　[1]龚劬.图论与网络最优化算法.重庆大学出版社.
　　[2]Srinivas Vegesna.IP服务质量.人民邮电出版社,2001.8.
　　[3]Andrew S.Tanenbaum.计算机网络.清华大学出版社,2004.8.
　　[4]崔勇,吴建平.互联网络服务质量路由算法研究综述.软件学报,2002(4).
　　注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文