燕 山 大 学
本科毕业设计（论文）文献综述
课题名称： 基于最短路径问题的自适应路由选择算法研究 学院（系）： 信息科学与工程学院 年级专业： 通信工程3班 学生姓名： 刘震 指导教师： 田澈 完成日期： 2014-03-22
一、课题国内外现状
随着计算机科学的发展，人们生产生活效率要求的提高，最短路径问题逐渐成为计算机科学、运筹学、地理信息科学等学科的一个研究热点。也正因为最短路径问题在实际生产生活中应用广泛，优化该算法和提高算法的求解效率具有重大的现实意义。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：确定起点的最短路径问题—即已知起始结点，求最短路径的问题；确定终点的最短路径问题—与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题；在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题；确定起点终点的最短路径问题—即已知起点和终点，求两结点之间的最短路径；全局最短路径问题—求图中所有的最短路径。用于解决最短路径问题的算法被称作最短路径算法。 国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。他们在空间复杂度、时间复杂度、易实现性及应用范畴等方面各具特色。现在的研究热点，一时针对实际应用中的网络特征进行限制。在统一的时间复杂度的基础上尽可能地提高算法的运行效率;二是针对网络特征进行限制，如果要求网络中的边具有整数权值等，以便采用基数等数据结构设计算法的运行结构；三是采用有损算法，如限制范围搜索、限定方向搜索及限制几何图层次递归搜索；四是采用拓扑层次编码路径视图进行部分实例化编码存储；五是采用并行算法，为并行计算服务。
路由选择协议的核心就是路由算法，即需要何种算法来获得路由表中的个项目。一个理想的路由算法应该具有如下特点。
（1）算法必须是正确的和完整的。这里，“正确”的含义是指沿着各路由表所指引的路由，分组一定能够最终到达目的网络和目的主机。 （2）算法在计算上应简单。路由选择的计算不应使网络通信量增加太多的额外开销。
（3）算法应能适应通信量和网络拓扑的变化，这就是说要有自适应性。
当网络中的通信量发生变化时，算法能自适应的改变路由以均衡个链路的负载。等某个或某些节点、链路发生故障不能工作，或者修理好了再投入运行时，算法也能及时的改变路由。有时称这种自适应性为“稳健性”（robustness）。
（4）算法应具有稳定性。在网络通信量和网络拓扑结构相对稳定的情况下，路由算法应收敛于一个可以接受的解，而不应使得出的路由不停的变化。
（5）算法应是公平的。路由选择算法应对所有用户（除了少数优先级高的用户）都是平等的。例如，若仅仅使某一对用户的端到端时延为最小，但却不考虑其他的广大用户，这就明显的不符合公平性的要求。 （6）算法应是最佳的。路由选择算法应当能够找出最好的路由，使得分组平均延时最小而网络的吞吐量最大。我们希望得到“最佳”的算法，但这并不是最重要的。对于某些网络，网络的可靠性有时要比最小的分组平均延时或最大吞吐量更加重要。因此，所谓“最佳”只能是相对于某一种特定要求下得出的较为合理的选择而已。 二、研究主要成果
随着计算机网络的飞速发展,相关的网络理论研究 也随之出现了一些新的热点:移动通信技术的普及推动了相关的移动路由算法及协议的研究,Ad2Hoc网络作为典型的由移动节点构成的网络,吸引了研究者的目光,文献就是一个Ad2Hoc网络中的单播/组播分布式路由协议,而文献中设计的单播分布式路由算法在Ad2Hoc网络中引入自适应机制,按照节点所维护的关于邻居变动信息和路由请求信息调节路由更新的周期和内容,仿真实验证明该协议的数据传输性能比目标序列距离矢量(Destination Sequence Distance Vector ,DSDV)协议要好。Ahmed Safwat和 Hossam Hassanein 通过模拟细胞网络的基本结构和操作,提出了虚拟基站(VirtualBasedSta2tions,VBS)路由算法,利用VBS基本框架建构协议的移动跟踪机制来寻找源节点到目的节点的路径,这种新的路由算法在数据包投递和路由开销方面都超过了已有的Ad2Hoc无线路由协议。
随着人工智能的发展,许多相关的技术开始应用在网络路由算法上,
如应用退火Hopfield神经网络算法,采用新的冷却机制进行MOSPF中的最短路径计算、用遗传算法解决QoS单播和组播路由问题、用Hopfield神经网络计算可以满足多种约束条件的QoS路径等。
最短路径问题旨在寻找图(由节点和路径组成的)中两个节点之间的最短路径． 最短路径不仅可以指一般地理意义上的距离最短，还可以是其他的度量，如时间、费用、线路容量等． 无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径路由算法，路由算法决定网络中分组迅速到达信宿的最短路径(shortest path，SP)． 经典的最短路径路由算法主要有 Floyd 算法、A*算法、Bellman-Ford、Topological Sort(拓扑排序)算法、Dijkstra 算法等． 近年来，人们开始尝试将蚁群算法、退火算法、遗传算法、贪心算法等智能搜索算法引入到最短路径问题的求解中来，取得了一定的成果，这些算法是目前多数系统解决最短路径问题采用的理论基础。 三、发展趋势：
传统的计算机互联网络路由理论把网络链路的权值看作静态的、不随时间变化的,这是不符合实际的。而将链路权值看作是随时间变化的函数能够更精确地描述计算机互联网络的运行状态。Orda和Rom基于Dijkstra算法理论研究了时间依赖的网络并应用于Internet网络的路由协议中,但是没有根本地解决时间依赖网络中的本质问题。我们从理论上证明了:传统的最短路径算法的理论基础,如Dijkstra算法,在时间依赖的网络中是不正确的。并且提出了时间依赖的网络模型、理论基础、求解最小时间路径的优化条件 和算法,并基于这些理论基础设计了混合型时间依赖网络中的分布式路由协议。
计算机互联网络不仅具有时间依赖性,而且它的链路权值、用户、拓扑结构都会产生很强的随机性,因此随机网络模型与理论能够更好地描述计算机互联网络的状态,目前国外已经开始研究随机网络中的路由算法，主要集中在用马尔可夫决策过程的应用上。我们在最短路径算法,尤其是随机网络最短路径算法的研究上已经具备了比较深厚的基础,在此基础上开展的相关算法到计算机网络路由协议移植的研究也已经取得了长足的进展。利用随机时间依赖网络模型与理论描述计算机互联网络
的时间依赖性、随机性,建立相应的模型、理论和算法,这是一个未被完全发掘的领域,需要更深入的研究。 四、存在问题
虽然对于最短路径问题有很多路由选择算法，但是每种算法都存在缺点。比如：Dijkstra算法优点：算法简明、能得到最优解。但是，缺点：效率低（特别是有时候不需要最优解）、运算中占用空间大。所以需要不断寻找跟好的算法来提高效率减小路由表的大小、减小维护路由表所需的机器资源和时间。 五、主要参考文献
[1]. Andrews等.计算机网络（第四版）. 北京：清华大学出版社：296-299 [2].王立宇等. MATLAB与通信仿真. 北京：人民邮电出版社： 2-38 [3].丁建立,陈增强,袁著社 基于自适应蚂蚁算法的动态最优路由选择 控制与决策 第18卷第6期
[4].钱志军,OSPF 动态路由协议中的路由计算[D].大庆石油学院,2007 [5]. 姜彬、施志刚 求最短路径问题的自适应路由遗传优化算法的设计与实现 南京工程学院学报(自然科学版) 2012-06-15
[6].王恒青、宋如敏 最短路径算法Dijkstra算法在路由选择中的应用 《科技信息(学术研究)》 2008年32期： 15-32
[7].蒋腾飞 网络最短路径问题应用研究 南京邮电大学 2013-04-01 [8].王恒青、宋如敏 最短路径算法Dijkstra算法在路由选择中的应用 《科技信息(学术研究)》 2008年32期
[9].施培港Dijkstra最短路径算法的实现及优化[A];中国地理信息系统协会第三次代表大会暨第七届年会论文集[C];2003年
[10].邹亮; 徐建闽 基于遗传算法的动态网络中最短路径问题算法 《计算机应用》 2005年4月
[11].周正等，智能蚂蚁算法及其在电信网动态路由优化中的应用，电信科学，
1998年11月：10—13
[12].刘代波 最短路径优化算法的研究与实现 电子科技大学 2012年3月
[13].YU E Yang . AnEfficient Implementation of Shortest Path Algorithm Basedon Dijkstra Algorithm [J]. Journal of Wuhan Technical University of SurveyingandMapping,1999,24(3):209-212
[14].ZHANFB.Three Fastest Shortest Path Algorithmson Real Road Networds [J]. Journalof Geographic Informationand DecisionAnalysis,1997,1(1):69282.
[15].John Harper, London G B. Method and System for accelerating route calculation link staterouting protocols[P] United States Patent 2006