考慮群播成員變動性下之最低成本路由群播樹演算法

A Minimum Cost Multicast Routing Algorithm with the Consideration of Dynamic User Membership

葉榮耀(Jung-Yao Yeh)

指導教授 ： 林永松

國立臺灣大學/管理學院/資訊管理學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.01554

摘要

本研究的目的在於建立最小成本的的群播樹。跟一般群播樹建立演算法不同的是，
本問題的模型包含一組固定的群播接收者，而群組中的成員具有的變動性是以觀察而來
的活動機率d q 來含括。由於此模型是用來評估與預測群播樹所需的成本，所以不考慮節
點實際的加入跟退出。因為模型近似於史坦那樹問題，所以利用拉格蘭日鬆弛法來加快求解的過程。

關鍵字

拉格蘭日鬆弛法 ； 史坦那樹 ； 群播樹

並列摘要

In this thesis, we try to model the problem of constructing a multicast tree with minimum
cost. Unlike the other minimum cost multicast tree algorithms, this model consists of one
multicast group of fixed members. Each destination member d is dynamic and has a
probability of being active as d q which was gathered by observation over some period of time.
With the omission of node join/leave handling, this model is suitable for prediction and
planning purpose than for online maintenance of multicast trees. Lagrangean relaxation
method is applied to speed up the solution procedure.

並列關鍵字

Lagrangean relaxation ； Steiner tree problem ； Multicast

參考文獻

[1] F. K. Hwang, Steiner Tree Problems, Networks, pp. 55-89, 1992.

[2] M. L. Fisher, “The Lagrangian relaxation method for solving integer programming

problems”,Management Science, vol. 27, pp. 1-18, 1981.

[3] R. K. Ahuja, T. L. Magnanti, J. B. Orlin, Network Flows, pp.108-112, 1993.

[4] D. G. Luenberger, Linear and Nonlinear Programming, pp.88-90, 1984.