多重群播重疊問題之最佳化

Abstract

由於電腦技術發展的相當迅速，在網路產生許多新興的多媒體應用，如視訊會議系統（video conference）、遠距教學（distance education）等應用。這些應用都須建構群播樹來做有效的傳輸。在本篇論文，我們考慮在網路上同時存在多組群播樹（即多組不同的群播應用）。我們的目標是找在頻寬的限制條件下，具有最小成本的多組群播樹的組合。此問題稱之為多重群播重疊問題。我們利用逐次改進的方式，提出兩個演算法來求解此多重群播問題。經由數值模擬的驗證，顯示本演算法極為有效。

As the rapid development of computer technology, there are many multimedia applications applied to network, such as video conference and distance education, etc. All of above applications need to construct the multicast tree for efficient transmission. In this thesis, we consider that there exist multiple multicast trees on the network simultaneously. This means that the network has multiple different multicast applications. Our objective is to find the multiple group multicastings for minimizing total cost under the bandwidth constraints. The problem is called as multi-group multicast packing（MGMP） problem. We propose two centralized algorithms for solving MGMP problem. The experimental results show that our algorithms are very efficient.