摘要
多播通信是从一个源点同时向网络中的多个成员发送分组的通信服务 ,一个最小代价的多播路由算法是NP完全的 ,在时间敏感的应用中其运行时间是一个关键问题 .MPH(MinimumPathCostHeuristic)算法是一个著名的启发式最小代价多播路由算法 ,本文对该算法进行了理论分析和证明 ,并做了广泛的仿真实验 ,结果表明其时间复杂度是O(m2 n)而不是过去文献中所给出的O(m2 n +e) .
Multicasting is a communication service that allows a source to efficiently transmit copies of data packet to a set of destination nodes.The run time of multicast routing algorithm is a key problem in real time applications since finding a minimum cost multicast tree is NP-completeness.MPH(Minimum Path Cost Heuristic)algorithm is a famous heuristic solution to multicast routing.In this paper,we show that the O(nm2+e) time complexity of MPH in previous literatures is not correct by theory analysis and extensive simulation,where n is number of network nodes,m is number of destination nodes and e is number of network edges.Furthermore,a precise time bound O(nm2) is proposed.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2004年第10期1706-1708,共3页
Acta Electronica Sinica
基金
国家自然科学基金 (No .60 2 730 75)
