一种基于神经网络的最短路径树生成算法.docVIP

 n 一种基于神经网络的最短路径树生成算法# 屈鸿* （电子科技大学计算机科学与工程学院） 5 10 15 20 25 30 35 40 摘要：最短路径树的计算是一个典型的组合优化问题，长期以来吸引了很多学者的高度重 视。高效的最短路径树生成算法对高效络路由协议的实现和应用具有十分重要的科学价 值。在目前的网络路由协议中，大多数是利用经典的 Dijkstra 计算路由节点的最小路径树。 然而随着网络技术的快速发展，网络规模越来越大，路由节点和连接情况变的越来越复 杂，传统 Dijkstra 算法在这种情况下的效率显得不高。本文提出一种具有生物激励特征的神 经网络模型，并用之解决路由协议中最短路径树的计算问题。经实验和分析，我们发现， 这种新算法的计算开销仅仅取决于最短路径树中最长路径的大小，而与网络中连接链路的 个数无关。因此，特别适合结点多，连接复杂，结点间连接权值小的情况，如 ad-hoc、传感 器网络等。最后，通过模拟试验，对所提算法的效率做了比较。 关键词：最短路径树；神经网络；网络路由 中图分类号：TP 301.6 A neural network method for the computing of the shortest path tree Qu Hong (School of Computer Science and Engineering, University) Abstract: Shortest Path Tree (SPT) computing is a well-known optimization problem and has been studied by many authors in recent years. It is very important to a network used a link state routing protocol. Typically it is solved by using the famous Dijkstra’s algorithm, which would quickly provide a global optimization solution in most instances. However, as the problem scale increases, this method is inefficient and may consume a considerable amount of CPU time. This paper presents a novel biological neural network based algorithm for the computing of the Shortest Path Tree (SPT) in large scale systems. The computational complexity of our method is only related to the length of the shortest path, and is independent with the number links in the network. There are so many links in todays network. So, our method is very significant, especially in mobile ad-hoc and sensor networks. Simulation results show that the proposed method is more efficient then the Dijkstra’s in the larger scale systems. Key words: SPT; neural network; routing 0 引言 在现代的网络环境中，高速信息交换的需求愈来愈多，而网络结构也愈来愈复杂，因此 高速的路由机制是十分有必要的。路由包含两个方面，路由协议和路由算法。网络中各个节 点根据路由协议收集网络的链路信息，拥有网络链路信息的节点根据路由算法来确定选路情 况。在目前广泛使用的以链路状态为基础的路由协议中，比如最短路径优先(OSPF) [1-3]， 每条链路对应相应权值，各个路由器之间相互交换链路状态信息，因此每个路由器随时保存 整个网络中链路状态信息。路由器根据各个链路权值的大小，计算一个以自己作为根结点的 最短路径树(SPT)，然后根据这个最短路径树，确定自己路由表的内容。因此一个有效的计 算 SPT 的算法是解决路由问题的关键所在。 基金项目：教育部博士点新教师基金（20080