摘要： 为解决最小生成树(MST)算法中的NP完全问题，使之适应实际网络环境的性能需求，提出一种寻求MST的分布式算法。该算法建立在MST性质的基础之上，利用数据融合逐步构建网络的MST。此过程不再需要传统洪泛连接信息，最多只需3×lbn次的信息交互，且去除了冗余信息。该算法具有收敛速度快、资源消耗低的特点。

关键词: 最小生成树, 分布式算法, 数据融合

Abstract: To resolve the NP-complete problem of Minimum Spanning Tree(MST) calculations and meet the performance requirements in actual network environment, a distributed algorithm for searching the MST is proposed. The algorithm is based on the characteristic of MST and utilizes data fusion to establish MST of the network gradually. The algorithm requires only 3×lbn times of information exchanges at most and removes off the redundant information without conventional flooding link-information. Therefore, it has the advantages of high convergence speed and low consumption of resources.

Key words: Minimum Spanning Tree(MST), distributed algorithm, data fusion

中图分类号: 

• TP312