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

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

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

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

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

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

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

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

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

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

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

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