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

摘要：

最短路径树的计算是一个典型的组合优化问题，长期以来吸引了很多学者的高度重视。高效的最短路径树生成算法对高效络路由协议的实现和应用具有十分重要的科学价值。在目前的网络路由协议中，大多数是利用经典的Dijkstra计算路由节点的最小路径树。然而随着网络技术的快速发展，网络规模越来越大，路由节点和连接情况变的越来越复杂，传统Dijkstra算法在这种情况下的效率显得不高。本文提出一种具有生物激励特征的神经网络模型，并用之解决路由协议中最短路径树的计算问题。经实验和分析，我们发现，这种新算法的计算开销仅仅取决于最短路径树中最长路径的大小，而与网络中连接链路的个数无关。因此，特别适合结点多，连接复杂，结点间连接权值小的情况，如ad-hoc、传感器网络等。最后，通过模拟试验，对所提算法的效率做了比较。

关键词：最短路径树、神经网络、网络路由

分类号：TP301.6(计算技术、计算机技术)

资助基金：教育部博士点新教师基金200806141049

在线出版日期：2014-01-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：62-66