一个低代价最短路径树算法

为了对最短路径树SPT（Shortest Path Tree）进行代价优化，提出了路径驱动的思想，主要是生成SPT时通过路径节点共享的方式来优化其总体代价。基于这个思想进行搜索过程优化，设计了一个路径节点驱动的低代价最短路径树算法LCSPT（Low—cost Shortest Path Tree Algorithm），这个算法生成的组播树在保证最短路径的同时降低了整个树的总体代价。仿真实验表明：LCSPT算法不但能正确地构造最短路径树，而且其构造的SPT总体代价与其它同类算法相比得到了最大限度的优化。

Low-cost Shortest Path Tree Algorithm

In order to optimize the cost of the shortest path tree(SPT),a path-driven idea is proposed.The path-driven idea means that the computing node optimizes the multicast tree cost by sharing link with those nodes which are in the path for the destination to the information source.Based on the idea and through improving the search procedure,a path-driven multicast routing algorithm of the low-cost shortest path tree(LCSPT) is presented.The LCSPT algorithm can establish and maintain a multicast tree which minimizes the total cost and simultaneously guarantees the shortest path for each receiver node.The two simulation results show that the LCSPT algorithm not only produces a SPT correctly but also has the best optimization performance among all the SPT algorithms.