我的开题报告.doc

燕 山 大 学本科毕业设计（论文）开题报告课题名称： 基于最短路径问题的自适应路由选择算法研究 学院（系）： 信息科学与工程学院 年级专业： 通信工程3班 学生姓名： 刘震 指导教师： 田澈 完成日期： 2014-03-22 一、综述本课题国内外研究动态，说明选题的依据和意义最短路径问题一直是计算机科学、运筹学、地理信息科学等学科的一个研究热点。国内外大量专家学者对此问题进行了深入研究。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。他们在空间复杂度、时间复杂度、易实现性及应用范畴等方面各具特色。现在的研究热点，一时针对实际应用中的网络特征进行限制。在统一的时间复杂度的基础上尽可能地提高算法的运行效率;二是针对网络特征进行限制，如果要求网络中的边具有整数权值等，以便采用基数等数据结构设计算法的运行结构；三是采用有损算法，如限制范围搜索、限定方向搜索及限制几何图层次递归搜索；四是采用拓扑层次编码路径视图进行部分实例化编码存储；五是采用并行算法，为并行计算服务。最短路径问题旨在寻找图(由节点和路径组成的)中两个节点之间的最短路径 最短路径不仅可以指一般地理意义上的距离最短，还可以是其他的度量，如时间、费用、线路容量等 无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径路由算法，路由算法决定网络中分组迅速到达信宿的最短路径(shortest path，SP) 经典的最短路径路由算法主要有 Floyd 算法、Dijkstra 算法等 近年来，人们开始尝试将蚁群算法等智能搜索算法引入到最短路径问题的求解中来，取得了一定的成果，这些算法是目前多数系统解决最短路径问题采用的理论基础。随着网络资源与网络需求的同步增长,如何实时地进行网络拥塞控制,如何根据具体情况进行动态的路由选择,就显得尤为重要。二、研究的基本内容，拟解决的主要问题 大量搜集、阅读有关自适应路由选择算法研究的资料、专著，了解、掌握计算机通信网中路由选择算法的发展及现状。研究路由选择算法的工作原理、特点及其在计算机通信网中的应用。研究网络拓扑图，确定最优路由算法。掌握通信网的基本功能原理。搜集、查阅资料，掌握链路状态路由选择算法的工作原理、特点及其在计算机通信网中的应用。自学MATLAB仿真语言的一种版本，用MATLAB对典型的基于最短路径问题的自适应路由选择算法进行设计与仿真，并对其数据及性能指标进行分析。三、研究步骤、方法及措施（一）确定算法选用Dijkstra算法进行研究。基本原理：Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。步骤S集合中U集合中1选入A，此时S=此时最短路径AA=0以A为中间点，从A开始找U=AB=2 AG=6A到其它U中的顶点=发现AB=2权值为最短2选入B，此时S=此时AA=0 AB=2以B为中间点，从AB=2这条最短路径开始找U=ABC=9ABE=4AB其它U中的顶点=发现ABE=4权值为最短3选入E，此时S=此时最短路径AA=0，AB=2，ABE=4以E为中间点，从ABE=4这条最短路径开始找U=AEF=6AEG=5（比上面A G短）AE其它U中的顶点=发现AEG=5权值为最短 AEF=6权值为最短4选入G,此时S=此时AA=0，AB=2ABE=4，ABG=5以G为中间点，从ABEG=5这条最短路径开始找U=AEGH=9AEG其它U中的顶点=发现AEGH=9权值为最短5选入F,此时S=此时ABEF=6 以F为中间点，从ABEF=6这条最短路径开始找U=AEFC=9AEFH=8(比上面AH短)发现AEFH=8权值最短 AEFC=9权值最短6选入C，此时S= 以C为中间点，从ABEFC=9这条最短路径开始找U=AEFCD=127选入H,此时S= 以H为中间点，从ABEFH=8这条最短路径开始找U=ABEFHD=10（比上面AD短）发现ABEFHD=10权值最短8选入D,此时S=此时为最短路径U集合已空，查找完毕（二）确定仿真语言选用MATLAB作为仿真语言四、研究工作进度 第14周 查阅资料，读专著，分析原理，完成开题报告及文献综述第58周 确定仿真方案，自学语言，设计编程第912周 编写程序，仿真，分析数据，完成中期考核报告、第1318周 调试程序，分析数据，验收程序，写论文第1718周 写论文，答辩五、主要参考文献1. Andrews等.计算机网络（第四版）. 北京：清华大学出版社：296-2992.王立宇等. MATLAB与通信仿真. 北京：人民邮电出版社： 2-383.丁建立,陈增强,袁著社 基于自适应蚂蚁算法的动态最优路由选择 控制与决策 第18卷第6期4.钱志军,OSPF 动态路由协议中的路由计算D.大庆石油学院,20075. 姜彬、施志刚 求最短路径问题的自适应路由遗传优化算法的设计与实现 南京工程学院学报(自然科学版) 2012-06-156.王恒青、宋如敏 最短路径算法Dijkstra算法在路由选择中的应用 科技信息(学术研究) 2008年32期： 15-327.蒋腾飞 网络最短路径问题应用研究 南京邮电大学 2013-04-018.王恒青、宋如敏 最短路径算法Dijkstra算法在路由选择中的应用 科技信息(学术研究) 2008年32期9.施培港Dijkstra最短路径算法的实现及优化A;中国地理信息系统协会第三次代表大会暨第七届年会论文集C;2003年10.邹亮; 徐建闽 基于遗传算法的动态网络中最短路径问题算法 计算机应用 2005年4月11.周正等，智能蚂蚁算法及其在电信网动态路由优化中的应用，电信科学，1998年11月：101312.刘代波 最短路径优化算法的研究与实现 电子科技大学 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-21214.ZHANFB.Three Fastest Shortest Path Algorithmson Real Road Networds J. Journalof Geographic Informationand DecisionAnalysis,1997,1(1