基于延遲約束的組播路由算法與仿真研究.pdf

1、隨著網(wǎng)絡(luò)技術(shù)的進步和Intemet的迅速普及，網(wǎng)絡(luò)正以前所未有的速度發(fā)展；然而，在網(wǎng)絡(luò)規(guī)模進一步擴大，信息流量迅速增加的同時，網(wǎng)絡(luò)已經(jīng)變得非常擁擠，在這樣的背景下，組播技術(shù)誕生了。組播是一種有效的支持多點通信的機制，它通過使一個或多個組播源，只把數(shù)據(jù)分組發(fā)送給特定的組播組來節(jié)約網(wǎng)絡(luò)中的資源；因此，組播這種通信方式可以有效的解決如交互游戲、IP電話、視頻點播、視頻會議、遠(yuǎn)程教育等需要占用大量網(wǎng)絡(luò)資源的多媒體業(yè)務(wù)。組播技術(shù)的核心是組播路由技

2、術(shù)：其中，帶延遲約束的組播路由技術(shù)因為對網(wǎng)絡(luò)中的實時業(yè)務(wù)具有非常重要的意義，所以已經(jīng)引起了人們的廣泛關(guān)注；該問題的主要目標(biāo)是建立覆蓋所有組播組成員，并保證端到端傳輸延遲的組播樹。帶延遲約束的組播路由問題，從源節(jié)點數(shù)量上可分為點到多點(one-to-many)帶延遲約束的組播路由問題和多點到多點(many-to-many)帶延遲約束的組播路由問題。
　　 本文對上述兩個問題進行了介紹，并對每個問題提出了相應(yīng)的算法；這兩個算法都源于

3、蟻群算法。在眾多智能優(yōu)化算法之中，蟻群算法因其健壯性、靈活性、魯棒性和富于建設(shè)性而備受推崇。此外，蟻群的正反饋性和協(xié)同性，使之可以用于分布式環(huán)境；其隱含的并行性更是使之較為適合于分布式算法的設(shè)計。因此，本文中的算法均借鑒了基本蟻群算法的部分有益思路，并在其基礎(chǔ)上進行了擴展和改進，使算法更加適合于解決相應(yīng)的問題。
　　 點到多點帶延遲約束的組播路由問題的特點是，在整個組播通信的過程中，只有一個源節(jié)點；該問題常被歸結(jié)為最小耗費的約束

4、斯坦立樹(Steiner Tree)問題，通過求解Steiner最小樹來得到相應(yīng)的組播樹。該問題已被證明是NP完全問題，不存在多項式時間的解法；近年來，出現(xiàn)了大量優(yōu)秀的算法思想，這使得人們對NP完全問題的研究不斷深入。為了更好的解決組播路由問題，前人已經(jīng)提出了很多集中式算法，但是在真實的網(wǎng)絡(luò)環(huán)境中，集中式算法的實現(xiàn)往往具有較大的局限性；本文在第4章中，提出了一個動態(tài)優(yōu)化的分布式組播路由算法。該算法利用蟻群思想解決組播路由問題，由于不同代

5、的螞蟻之間可以通過信息素來實現(xiàn)間接通信，而信息素又是一種可以反映環(huán)境變化的媒介質(zhì)；因此，算法能夠根據(jù)網(wǎng)絡(luò)環(huán)境的變化及時做出調(diào)整。結(jié)合拓?fù)渖善鳟a(chǎn)生的網(wǎng)緒拓?fù)溥M行仿真實驗，實驗結(jié)果表明：通過螞蟻一代代的進化，算法可以找到一棵滿足延遲約束，并且耗費盡可能小的組播樹。
　　 隨著多媒體技術(shù)的發(fā)展，出現(xiàn)了許多包括多個源節(jié)點和多個目的節(jié)點的實時業(yè)務(wù)應(yīng)用，如交互游戲等。這類應(yīng)用對應(yīng)的組播路由問題被稱為多點到多點帶延遲約束的組播路由問題?？梢?/p>

6、通過為所有的源節(jié)點和目的節(jié)點建立一棵（或僅僅少數(shù)幾棵）組播樹，使得多個源節(jié)點共同使用此組播樹傳輸數(shù)據(jù)分組來解決此類問題。這種形式的組播樹被稱為共享樹；共享樹結(jié)構(gòu)的優(yōu)點在于只有樹上的路由器才需要維持組成員信息，因此，路由器所需存儲的狀態(tài)信息的數(shù)量和組播樹的總耗費都相對較小。中心選擇是建立共享樹時所需要解決的一個重點和難點問題；前人對于該問題的研究往往局限于對單個中心進行選擇；但是，因為單中心共享樹在延遲方面的缺陷明顯，所以已經(jīng)有越來越多的