摘 　要： 多點組播是指一個源點傳送信息到多個目的節(jié)點，它是網(wǎng)絡(luò)支持多媒體業(yè)務(wù)的關(guān)鍵技術(shù)之一。以服務(wù)質(zhì)量(QoS)指標(biāo)中的帶寬和時延為優(yōu)化選路準(zhǔn)則，提出了一種受限的組播路由算法，仿真結(jié)果證明了該算法的有效性。
　　關(guān)鍵詞： 網(wǎng)絡(luò) 組播 路由
　　通信網(wǎng)絡(luò)在進入90年代后，向著綜合業(yè)務(wù)的方向發(fā)展。在傳統(tǒng)的數(shù)據(jù)網(wǎng)絡(luò)中，路由所需考慮的僅是可連接性^[1]，路由算法在尋找最優(yōu)(短)路徑時采用單一的指標(biāo)，如跳數(shù)或時延。新出現(xiàn)的多媒體通信帶來了多點組播的需求，即未來的計算機網(wǎng)絡(luò)應(yīng)該能夠提供例如電視會議、視頻點播等具有點對多點的業(yè)務(wù)要求。而這種網(wǎng)絡(luò)應(yīng)該支持范圍廣泛的服務(wù)質(zhì)量(QoS)需求，確定路由需要相當(dāng)復(fù)雜的模型來描述網(wǎng)絡(luò)，即路由的優(yōu)化指標(biāo)要包括時延、帶寬、丟失率等。
　　近年來，各國學(xué)者開始在這方面探索，提出了一些快速有效的算法。如：基于最短路徑的Dijkstra算法^[2]，即計算源點到各目的點的最短路徑；另一類是求最小網(wǎng)絡(luò)代價(NC)的應(yīng)用斯坦利(Steiner)樹路由算法^[3]，即計算組播樹(Multicast tree)，使其在任意一對源和目的節(jié)點之間都存在通路，并使其代價(cost)最小。
　　本文使用改進的受限Steiner樹路由算法，構(gòu)造樹型路由結(jié)構(gòu)來實現(xiàn)多點通信(multicast或MC)。這是由于基于樹實現(xiàn)有效MC路由具有以下兩個優(yōu)點：(1)分組以并行方式沿著樹枝發(fā)送到不同的信宿；(2)網(wǎng)絡(luò)中需要傳送的復(fù)制分組最小，而且分組的復(fù)制只是在樹叉處進行。在QoS的參數(shù)中，本文選取最小化占用鏈路總帶寬和滿足端到端的時延限制為優(yōu)化準(zhǔn)則。
1 受限組播路由的算法
1.1 網(wǎng)絡(luò)模型
　　一個網(wǎng)絡(luò)可以表示為圖G(V，E)；其中V是頂點的集合，包括n個頂點；E是邊的集合，包括m條邊。每條邊e∈E具有兩個參數(shù)：C(e)和D(e)，C(e)是邊e上的正實數(shù)代價函數(shù)，D(e)是e上的正整數(shù)時延函數(shù)。在給定信源S和信宿集合D條件下，給定允許延遲極限Δ，構(gòu)造根為S，覆蓋所有信宿節(jié)點的受限Steiner樹，滿足條件v∈D，樹上路徑(i，j)的延遲小于Δ，即：如果P(i、j)是樹上從i到j(luò)的路徑，那么對v∈D滿足：
　　Σ_e∈PD(i、j)＜Δ　　　　(1)
　　在滿足式(1)的條件下，
　　Σ_e∈PC(e)最小?！　　　?2)
1.2 算法實現(xiàn)機理
　　由于網(wǎng)絡(luò)中的Steiner問題屬于圖論中的NP完備問題^[4]，即，一般地說，最優(yōu)算法無法在多項式時間內(nèi)完成。因此，用啟發(fā)式算法可降低算法難度，而在性能上逼近理論算法。由于構(gòu)造最小生成樹(MST)相對簡單，因此常用的是MST啟發(fā)式算法。
　　本文通過改進Prim算法^[2]來求解MST問題。Prim算法的基本思想為：假定G＝(V，E)是連通圖，T是G上MST中邊的集合。算法從U＝{S}(S為源點)，T＝Φ開始，重復(fù)執(zhí)行下列操作：在所有u∈U、v∈{V－U}的邊(u、v)∈E中找一條權(quán)值最小的邊(u₀、v₀)并入集合T，同時u₀并入U，直到U＝V為止，則T為G的MST。
　　改進算法的基本思想是：首先利用Dijkstra第k最短路徑算法，計算從源節(jié)點到目的節(jié)點以時延為優(yōu)化準(zhǔn)則的路徑，并將所求的路徑中最大的時延與Δ比較，若該值比Δ大則表明限制條件太苛刻，可令Δ等于該值。然后以cost最小為首要優(yōu)化目標(biāo)，用Prim算法求出圖G的MST樹。用Prim算法每生成一條邊(i、j)時，就計算由S到該邊的累計時延Σ_e∈PD(i、j)、若Σ_e∈PD(i、j)≤Δ，則用Prim算法繼續(xù)尋找下一條邊。否則令該邊對應(yīng)的cost(i、j)為∞，并且將j(i∈U、j∈{V－U})仍保留在原來集合中。當(dāng)用Prim算法完成一次全局搜索后，再對那些仍保留在{V－U}集合中的點重新進行全局搜索(除開前次讓cost(i、j)為∞的i點外)，尋找符合時延條件的新邊。當(dāng)U中已包含全部組播目標(biāo)節(jié)點Di后，算法結(jié)束。
1.3 算法的實現(xiàn)過程
　　可采用一個整型二維數(shù)組a[MAX][3]來表示在構(gòu)造最小生成樹U，{V－U}和權(quán)值cost的變化。其中數(shù)組的第一列a[][0]放生成樹的頂點集合U中的各頂點，初始值為源點s；第二列a[][1]放頂點集合{V－U}中的各頂點；第三列a[]^[2]放{V－U}到U所構(gòu)成的邊的最小權(quán)值。同時，采用二維數(shù)組mat[MAX][MAX]來存儲圖的鄰接矩陣，矩陣(i、j)對應(yīng)的值就是邊(i、j)上的cost值。開始對a[MAX][3]的初始化可表示為：
　　a[i][0]＝1；
　　if(i＝＝1)
　　a[i][1]＝0；
　　else
　　a[i][1]＝i;
　　a[i][2]＝mat[1][i];
　　然后按前面所述的改進Prim算法來搜索MST。具體實現(xiàn)過程可以用C語言編程實現(xiàn)。其流程圖如圖1所示。這里設(shè)Δ是合理的時延限制值，且整個網(wǎng)絡(luò)有n個節(jié)點。

　　本文提出的算法兼顧了滿足時延限制和代價最小兩個QoS要求，仿真結(jié)果也證明了該算法在力求代介最小的前提下，能根據(jù)組播應(yīng)用時延的限制要求，快速有效地構(gòu)造組播樹，有較強的實時性。
參考文獻
1 Gupta S. On routing in ATM networks、modeling and performance evaluation of ATM Technology.North－Holland:Elsevier Science Publisher B.V、1993:229～239
2 劉振宏，蔡茂誠譯.組合最優(yōu)化.北京：清華大學(xué)出版社，1998
3 Hwang F K、Richards D S.Steiner tree problems.IEEE Networks、1992;22(1):55～89
4 M.R.Garey and D.S.Johnson、Computers and Intractability:A Guide to the Theory of NP－Completeness. San Francisco、CA:Freeman、1979