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