Abstract
由於目前網路上的應用，如視訊會議，視訊隨選以及遠距教學等等，都需要將視訊信號在即時內傳送到多個目的端。其中一個方法是在來源端將信號複製多份，然後往各個目地端各送一份，這樣會發生在同一條通訊線路上有多份相同的信號，在頻寬的使用上顯然非常沒有效率。所以，我們只有在群播樹的分支點才將信號複製多份並往其下的分支傳送；可是，群播群中的各個接收端可能有不同的頻寬，所能接收的信號量亦不相同，若是能提早在前面的分支點就得知其下的接收端的頻寬，分支點就只送出適量的信號，這樣就可以不浪費網路的頻寬。因此在本篇論文中，為了配合網路上群播群中各個接收端可能有不同頻寬的要求，我們將視訊信號以階層式的編碼方法分成數層，第一層包含著這個視訊信號的最基本信號；如果我們只接收到第一層的信號，便只能看到最低品質的畫面；隨著接收到更高層的信號，我們將可以得到較高品質的畫面。而網路上的節點可以動態的加入或離開群播的連線，所以我們的問題就是當有節點要求加入群播的行列時，便要去找一條最佳的路徑讓該節點加入已存在的群播樹。我們提出最小的額外花費(MAC)及最短路徑的額外花費(SP-MAC)來選擇 又快，花費又少的路徑。在我們的模擬中，將這兩種演算法與已被提出的最短路徑演算法(shortest path)，動態貪心演算法(dynamic greedy)來做比較，在變化多種參數下，會發現我們提出的兩種演算法，表現的都比較佳。In this paper, the dynamic multicast routing problem fordistributing hier-archically encoded video data is studied. Thevideo signal is encoded hierar- chically into a number of layerswith the first layer containing the essentialinformation suchthat the least capable receivers can reconstruct the videosignal with lower quality. Each of the higher layers containsinformation which can further enhance the quality of thevideo signal. The cost associatedwith a network link isdependent on the number of layers of video signal it iscarrying.The nodes in the network may be allowed to join or leave themulti- cast connection dynamically for some networkapplications. The problem is to find a path to attach a nodewhich wishes to join the multicast connection to the existingmulticast tree such that certain performance measure is opti-mized. Two heuristic algorithms, namely, minimum additionalcost (MAC) and shortest path minimum additional cost (SP-MAC)algorithms are proposed for this problem. The performances ofthe proposed algorithms are compared with those of themodified shortest path and dynamic greedy algorithms byextensivesimulations. Our results show that the proposedalgorithms outperform the modified shortest path and dynamicgreedy algorithms for wide ranges of various parameters.