基于蟻群優(yōu)化的組播路由算法研究.pdf

1、隨著Internet的不斷普及和多媒體通信技術的快速發(fā)展,特別是下一代互聯(lián)網(wǎng)的建設、研究和試商用,以及IPTV、視頻會議、視頻點播、遠程教學等多媒體應用迅速發(fā)展和普及,使得原來已經(jīng)存在的、龐大的數(shù)據(jù)流量成倍增長,據(jù)Cisco估計,2007至2012年間Internet流量會每兩年翻一番,這對Internet的健康發(fā)展帶來了嚴峻的挑戰(zhàn)。優(yōu)化網(wǎng)絡帶寬可滿足數(shù)據(jù)流量增長的需要,而IP組播通信技術是適用于一對多(或者多到多)的數(shù)據(jù)傳輸業(yè)務,已經(jīng)

2、成為研究實現(xiàn)優(yōu)化帶寬的一個重要手段。IP組播通信是由Steve Deering博士最初提出的一種網(wǎng)絡體系結構,可以將源節(jié)點數(shù)據(jù)流的副本以多路復用的方式發(fā)送到一組接收者。利用組播通信技術,源節(jié)點只需產(chǎn)生并發(fā)送一份數(shù)據(jù)流,經(jīng)過組播樹中路由器的復制和轉發(fā),將數(shù)據(jù)流傳送到一組目的節(jié)點。因此,與單播通信相比,組播通信可以極大地降低網(wǎng)絡資源的消耗,同時能夠減輕源節(jié)點的負擔,因而IP組播通信是目前實現(xiàn)多媒體組通信的最佳方式。
　　 針對組播和

3、組播路由算法的研究一直是學術界和工業(yè)界的研究熱點,其中,為滿足多媒體組通信對網(wǎng)絡QoS的要求,尋找一種簡單、高效、健壯的具有多約束條件的組播路由算法一直是網(wǎng)絡界致力研究但未完全解決的問題。在數(shù)學上,帶約束條件的組播路由問題被歸結為帶約束的Steiner樹問題,該問題已經(jīng)被證明是NP-Complete的,一般不能在多項式時間內(nèi)找到可行解,解決這類問題一般使用近似算法、啟發(fā)式算法等新型智能算法。隨著中國下一代互聯(lián)網(wǎng)示范工程CNGI的試商用,

4、以及電信網(wǎng)、廣播電視網(wǎng)和互聯(lián)網(wǎng)三網(wǎng)融合工作的啟動,這對IPTV、網(wǎng)絡視頻會議、網(wǎng)絡遠程教學等多媒體應用的推廣部署及應用具有非常積極的政策意義和推動作用,從而對組播和網(wǎng)絡服務質量(QoS)等產(chǎn)生了迫切需求,因此探索使用新型智能算法研究組播路由算法既有理論意義,也有現(xiàn)實意義。
　　 特別是隨著下一代互聯(lián)網(wǎng)為代表的新型、高性能網(wǎng)絡的部署,高性能組播路由算法將成為研究的難點和熱點問題,主要表現(xiàn)為動態(tài)、分層/聚合、分布式、高性能、低復雜度

5、的多QoS約束的組播路由問題。另外,在實際的網(wǎng)絡通信中,各個網(wǎng)絡節(jié)點的組播能力是受到限制的,如何既減少節(jié)點復制信息的數(shù)量,縮短處理信息的時間,有助于保證網(wǎng)絡的傳輸速度,又平衡各個節(jié)點的負載,這就引入了度約束(degree constrained)問題。通過對網(wǎng)絡節(jié)點給定度約束來管理節(jié)點的組播能力,并研究在有度約束情況下的組播路由問題,這在實際網(wǎng)絡中具有重要意義。
　　 蟻群算法是一種基于種群的模擬進化算法,由意大利的Marco

6、Dorigo于1991年在其博士論文中首先提出,并將其成功的應用于求解旅行商TSP問題。蟻群算法能夠通過群體之中個體之間的相互作用解決優(yōu)化問題,從而可以克服利用傳統(tǒng)方法加以解決某些優(yōu)化問題所經(jīng)常遇到的無法求解或求解極其復雜等困難。其基本原理在于:螞蟻在尋找食物過程中,雖然開始時單個螞蟻的路徑是雜亂無章的,但是螞蟻通過相互交流信息,最后總能找到蟻巢與食物之間的最短路徑。這種能力是靠其在所經(jīng)過的路上留下一種信息素來實現(xiàn)的。螞蟻在一條路上前進

7、時會留下一定量的信息素,信息素的強度會隨著時間的推移會逐漸揮發(fā)消失,后來的螞蟻選擇該路徑的概率與當時這條路徑上信息素強度成正比。對于一條路徑,選擇它的螞蟻越多,則在該路徑上螞蟻所留下的信息素強度就越大,而更大的信息素強度則會吸引更多的螞蟻,從而形成一種正反饋,通過這種正反饋,螞蟻最終可以發(fā)現(xiàn)最短路徑,以后大部分的螞蟻都會走此路徑。
　　 隨著Internet上分布式多媒體應用對QoS的需求日益增長,QoS路由作為實現(xiàn)QoS需求的

8、關鍵技術之一,也越來越得到研究人員的重視。將蟻群算法應用于研究受限組播路由,可以解決包括帶寬、延時、包丟失率和最小花費等約束條件在內(nèi)的QoS組播路由問題及度約束組播路由問題,是當前網(wǎng)絡組播路由優(yōu)化領域的一個研究熱點。
　　 本論文就是使用蟻群優(yōu)化這一啟發(fā)式算法,研究提出了幾種解決帶約束條件的組播路由問題的新型蟻群算法,包括度約束環(huán)境下的組播路由算法和多QoS約束環(huán)境下的組播路由算法兩個方面。論文的主要學術貢獻可歸納如下:

9、　　 1)針對度約束組播路由問題,利用蟻群算法的正反饋機制設計了一種基于樹的蟻群算法NAH。在NAH算法中,螞蟻按照一定的概率選擇一條鏈路加入組播子樹,然后檢查加入點的度約束情況,如果該點的度約束情況達到飽和,則螞蟻以后不再選取與該點連接的鏈路。仿真實驗表明,相比現(xiàn)有的AH算法,NAH算法能在更短的時間內(nèi)找到最優(yōu)解,而且顯著地降低了空間復雜度,NAH算法的總空間復雜度為o(M×N),而AH算法的總空間復雜度為o(M×N×n),運算速度

10、也明顯加快。
　　 2)將交叉熵算法和蟻群算法相結合,設計了一個求解多QoS約束組播路由問題的新型蟻群算法。該算法將多QoS約束的組播路由問題表示成適用于交叉熵算法求解的數(shù)學模型,利用螞蟻代理的概念,給出了基于交叉熵的蟻群算法求解多QoS約束組播路由問題時的執(zhí)行步驟。通過將蟻群算法與具有完備數(shù)學基礎的交叉熵算法相結合,交叉熵算法隨機機制的優(yōu)點保證了求解的規(guī)模和尋找解的范圍足夠大,從而可以顯著提高最優(yōu)解的質量,而且在運算速度、可擴

11、展性等方面均優(yōu)于傳統(tǒng)蟻群算法。
　　 3)根據(jù)蟻群算法開始收斂速度慢的情況,針對多QoS約束的組播路由問題,設計了一個基于地理位置感知的蟻群優(yōu)化算法。該算法將地理位置信息引入蟻群算法,螞蟻在尋路時可以使用位置信息以獲得更準確的路徑選擇。在此基礎上,借鑒地理位置感知的思想,提出了“方向因子”的概念,并基于方向因子提出了一個改進的多QoS約束組播路由蟻群算法MACA。該算法采用了組成員節(jié)點驅動的方式構建組播樹,并在概率轉移函數(shù)中加入