【作者】 陈骏坚；

【导师】 李腊元；

【作者基本信息】 武汉理工大学 ， 机械设计及理论， 2006， 博士

【摘要】 网络服务质量路由（Quality of Service Routing）是计算机网络理论研究的重要领域，随着网络的发展和网络应用的快速增长，对网络路由提出了更高的要求，为解决解决在Internet网上传输语音、视频等数据时所遇到的带宽变化、数据丢失、延迟、抖动等QoS问题。本文对基于Internet网的QoSR问题的理论及技术进行研究。 本文提出了一种扩展的Dijkstra算法，该算法可找到QoS参数的极限值，能解决一些QoSR问题，并对该算法进行了复杂性分析与比较。 蚂蚁算法作为探索类算法在近几年逐步得到推广和应用，在研究蚂蚁算法后，本文提出了一种新型的蚂蚁算法，并保留蚂蚁算法的信息素概念，该算法对经典蚂蚁算法做了3个方面的根本改进，它们是： 1．摒弃蚂蚁算法中概率方式的转移模式，采用确定方式的转移模式； 2．摒弃一群蚂蚁的探路模式，采用一只蚂蚁的探路模式； 3．蚂蚁在探索路径时，总是沿着信息素最小的路径前进。 通过实际编程和计算，证实了新型的蚂蚁算法能解决QoSR问题，能找到较优QoSR或最优QoSR。经过对该算法的分析，发现其时间复杂性与蚂蚁移动的步数成线性关系。 本文在研究新型蚂蚁算法后，证明了在一个连通的有限网络中，采用该算法，蚂蚁经过有限步移动后，可到达网络中的任意一个结点。这个结论也证明了新型蚂蚁算法算法有初始的QoSR解。本文对新型蚂蚁算法的最优性、简单性、鲁棒性、收敛性、灵活性5种性能指标进行定性分析。分析结果表明该算法具有优良的性能特征。本文研究了该算法时间复杂性与蚂蚁移动步数之间的关系，得出结论是新型蚂蚁算法的计算时间开销与蚂蚁移动步数成线性关系。本文研究了蚂蚁移动步数与QoSR解的关系，得出结论是在蚂蚁移动MLog₂N步后，就能寻找到较优的QoS路由，有时能寻找到最优的QoS路由。本文对该算法的时间复杂性进行定量分析，最终得到的结论是新型蚂蚁算法的时间复杂性为0（N³Log₂N）。并与有关的QoSR算法的时间复杂性进行比较，结果表明该算法的时间复杂性较优。 本文在研究新型蚂蚁算法理论的基础上，进一步对新型蚂蚁算法的鲁棒性进行实际计算与研究，结果证实新型蚂蚁算法具有鲁棒性。更多还原

【Abstract】 Quality of Service Routing(QoSR) research is very important in network theory research. Due to network developing and application increasing, network routing has been needed more standards and demands. In order to solve QoS problem that voice and video can’t be transferred effectively in Internet because there are delay, jitter, lost data, bandwidth. The paper study QoSR Theory and Technology based on Internet.This paper presents an extended Dijkstra algorithm. It can find out the limit of each QoS parameter constrained and can solve some QoSR problem. This paper analysies and comparies time complexity of the extended Dijkstra algorithm.As a search algorithm, ant colony algorithm has been used recent years more and more. After studying ant colony algorithm, this paper presents a new ant algorithm and reserves pheromone concept. Comparing with ant colony algorithm, the new ant algorithm is grandly upgraded in three fields. It include:1. Giving up the transfer method of probability and select the transfer method of inevitability.2. Giving up search path method of a colony of ants and select search path method of an ant.3. When an ant search path, It always go forward along a less pheromone path. After programmed and calculated, the paper confirms the new ant algorithm cansolve the problem of QoSR. It can find out a good QoS route or the best QoS route. After analyzing the algorithm, we can find that there is a linear relation between the algorithm time complexity and the number of ant’s moving step.After studying the new ant algorithm, this paper prove that the ant can reach at each node of connection network After the ant moves finite step by this algorithm. This result still proves that the new ant algorithm has an initialization QoSR solution. The paper studies a relation between the algorithm time complexity and the number of ant’s moving step. The result is that there is a linear relation between the algorithm time complexity and the number of ant’s moving step. The paper studies a relation between the number of ant’s moving step and QoSR solution. The result is that this algorithm can find out a good QoSR and sometimes find out the best QoSR after an更多还原