新型蚂蚁算法可达性证明与性能分析

网络服务质量路由是计算机网络理论研究的重要领域,它是下一代互联网的核心技术之一,新型蚂蚁算法作为探索类算法可用于解决QoSR问题.在研究新型蚂蚁算法后,证明了在一个连通的有限网络中,蚂蚁经过有限步移动后,可到达网络中的任意一个结点.对新型蚂蚁算法的最优性、简单性、鲁棒性、收敛性、灵活性等5种性能指标进行定性分析;对该算法的时间复杂性进行定量分析,并与有关算法进行比较.     

用新型蚂蚁算法求解QoSR问题

网络服务质量路由是计算机网络理论研究的重要领域，QoSR问题是一个NP完全问题．蚂蚁算法在近几年内逐步得到推广和应用，文中在研究蚂蚁算法后，保留蚂蚁算法的信息索概念，提出了一种新型的蚂蚁算法，即蚂蚁在寻找路径时，放弃按概率的方式跳转结点的寻路方式，采用按信息索较少的路径跳转结点的寻路方式，以解决QoSR问题．通过实际编程和计算，该算法能均匀搜索每条路径，对于单个参数约束，能很快达到最优解，对于多个参数约束，能找到最优解．经过对该算法的分析，其时间复杂性与蚂蚁跳转结点的次数是线性关系．     

新型蚂蚁算法时间复杂性与鲁棒性研究

在研究新型蚂蚁算法理论的基础上，进一步对新型蚂蚁算法的时间复杂性与鲁棒性进行实际计算与研究，研究出蚂蚁移动Mlog2N（M为边数，N为结点数）步后，能找到QoSR的较优解，该算法的时间复杂性为O（MNlog2N）．对该算法的鲁棒性进行分析，证实了在关键结点失效后，该算法仍能找到新的QoSR，并发现随着关键结点失效增多，再找到新的QoSR的QOS参数值急剧下降．     

用扩展Dijkstra算法求解QoS问题的极限值及路由

网络路由是网络研究的核心问题，随着网络的发展和网络应用的快速增长，对网络路由提出了更高的要求，网络服务质量路由QoSR(quality of service routing)的研究因此成为计算机网络的重要领域．文中提出了一种扩展的Dijkstra算法，以解决4类QoS参数约束的QoSR问题，该算法能找到每类参数约束的极限值，找到延时、抖动、带宽约束和可靠性约束的较优解，并对该算法进行了复杂性分析与比较，找到QoS参数的极限值对进一步采用探索类算法求解QoSR问题有着重要的意义．