通過蟻群算法解決QoS組播路由問題

隨著網(wǎng)絡(luò)應(yīng)用越來越廣泛，在傳統(tǒng)的HTTP、FTP、E-mail等數(shù)據(jù)業(yè)務(wù)的基礎(chǔ)上增加了各種實(shí)時和多媒體業(yè)務(wù)。要滿足這些業(yè)務(wù)的需求，特別是要保證一些實(shí)時業(yè)務(wù)的帶寬、時延等特殊需求，僅以目前Internet中"盡最大努力交付"的服務(wù)是難以完成的。因此，組播技術(shù)的研究成為這個領(lǐng)域的熱點(diǎn)，同時也對于組播的服務(wù)質(zhì)量提出了更高的要求，QoS組播的需求已成為Internet相關(guān)技術(shù)的研究熱點(diǎn)。Qos組播路由技術(shù)是網(wǎng)絡(luò)支持QoS保證的關(guān)鍵技術(shù)之一，因此，高效的QoS組播路由算法就顯得至關(guān)重要。QoS（Quality of Service）服務(wù)質(zhì)量，是網(wǎng)絡(luò)的一種安全機(jī)制， 是用來解決網(wǎng)絡(luò)延遲和阻塞等問題的一種技術(shù)。 在正常情況下，如果網(wǎng)絡(luò)只用于特定的無時間限制的應(yīng)用系統(tǒng)，并不需要QoS,比如Web應(yīng)用，或E-mail設(shè)置等。但是對關(guān)鍵應(yīng)用和多媒體應(yīng)用就十分必要。當(dāng)網(wǎng)絡(luò)過載或擁塞時，QoS 能確保重要業(yè)務(wù)量不受延遲或丟棄，同時保證網(wǎng)絡(luò)的高效運(yùn)行。網(wǎng)絡(luò)資源總是有限的，只要存在搶奪網(wǎng)絡(luò)資源的情況，就會出現(xiàn)服務(wù)質(zhì)量的要求。服務(wù)質(zhì)量是相對網(wǎng)絡(luò)業(yè)務(wù)而言的，在保證某類業(yè)務(wù)的服務(wù)質(zhì)量的同時，可能就是在損害其它業(yè)務(wù)的服務(wù)質(zhì)量。例如，在網(wǎng)絡(luò)總帶寬固定的情況下，如果某類業(yè)務(wù)占用的帶寬越多，那么其他業(yè)務(wù)能使用的帶寬就越少，可能會影響其他業(yè)務(wù)的使用。因此，網(wǎng)絡(luò)管理者需要根據(jù)各種業(yè)務(wù)的特點(diǎn)來對網(wǎng)絡(luò)資源進(jìn)行合理的規(guī)劃和分配，從而使網(wǎng)絡(luò)資源得到高效利用。

遺傳算法GA（Genetic Algorithm）的特點(diǎn)在于具有搜索能力、潛在的并行性及較強(qiáng)的魯棒性，計(jì)算過程簡單，能很好地解決開發(fā)最優(yōu)解和探尋搜索空間的矛盾；蟻群算法（ant colony optimization, ACO），又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機(jī)率型算法。它由Marco Dorigo于1992年在他的博士論文中提出，其靈感于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。蟻群算法是一種模擬進(jìn)化算法，初步的研究表明該算法具有許多優(yōu)良的性質(zhì)。針對PID控制器參數(shù)優(yōu)化設(shè)計(jì)問題，將蟻群算法設(shè)計(jì)的結(jié)果與遺傳算法設(shè)計(jì)的結(jié)果進(jìn)行了比較，數(shù)值仿真結(jié)果表明，蟻群算法具有一種新的模擬進(jìn)化優(yōu)化方法的有效性和應(yīng)用價值。各個螞蟻在沒有事先告訴他們食物在什么地方的前提下開始尋找食物。當(dāng)一只找到食物以后，它會向環(huán)境釋放一種信息素，吸引其他的螞蟻過來，這樣越來越多的螞蟻會找到食物！有些螞蟻并沒有象其它螞蟻一樣總重復(fù)同樣的路，他們會另辟蹊徑，如果令開辟的道路比原來的其他道路更短，那么，漸漸，更多的螞蟻被吸引到這條較短的路上來。最后，經(jīng)過一段時間運(yùn)行，可能會出現(xiàn)一條最短的路徑被大多數(shù)螞蟻重復(fù)著。

將遺傳算法和蟻群算法用于QoS組播路由已經(jīng)取得較好的效果，但是缺點(diǎn)也很明顯。遺傳算法對于系統(tǒng)中的反饋信息利用不夠，在中后期往往做大量無謂的迭代，求最優(yōu)解的效率降低；蟻群算法則由于初期螞蟻的隨機(jī)活動使得前期信息素的更新較慢、求解速度慢，由于在后期容易早熟，而陷入局部最優(yōu)。

本文針對目前應(yīng)用蟻群算法解決NP完全問題的研究現(xiàn)狀，以基本蟻群算法為基礎(chǔ)，提出一種遺傳多蟻群融合算法（GAMAC_QoS）來解決QoS多約束組播路由問題，對多個約束QoS組播路由問題進(jìn)行了研究。利用基本蟻群算法的分布式和全局搜索能力，使信息素積累和更新收斂于最優(yōu)路徑上。

（3）初始種群生成

采用隨機(jī)方法從中選擇若干個個體組成初始種群，首先刪除不滿足QoS約束條件的節(jié)點(diǎn)以及與之相連的鏈路，再刪除不滿足帶寬要求的鏈路，得到一個新的精簡后的網(wǎng)絡(luò)拓?fù)洹?/p>

（4）選擇算子

采用個體最佳保留策略（最佳個體保留個數(shù)設(shè)置為2）與采用遺傳算法中運(yùn)用最廣的輪盤賭選擇機(jī)制執(zhí)行選擇功能。

（5）交叉算子

采用Davis順序交叉方法，先進(jìn)行常規(guī)的雙點(diǎn)交叉，再進(jìn)行維持原有相對訪問順序的巡回線路修改[5].具體交叉如下：

①隨機(jī)在父串上選擇一個交配區(qū)域，如兩父串選定為：

old1=12|3456|789

old2=98|7654|321

②將old2的交配區(qū)域加到old1的前面，將old1的交配區(qū)域加到old2的前面：

old1'=7654|123456789

old2'=3456|987654321

③依次刪除old1',old2'中與交配區(qū)相同的數(shù)碼，得到最終的兩子串：

new1=765412389

new2=345698721

（6）變異算子

采用逆轉(zhuǎn)變異法逆轉(zhuǎn)。如染色體（1-2-3-4-5-6）在區(qū)間2-3和區(qū)間5-6處發(fā)生斷裂，斷裂片段又以反向順序插入，于是逆轉(zhuǎn)之后的染色體變?yōu)椋?-2-5-4-3-6）。這里的進(jìn)化，是指逆轉(zhuǎn)算子的單方向性，只有經(jīng)逆轉(zhuǎn)后，適應(yīng)值有提高的才接受下來，否則逆轉(zhuǎn)無效。

2.2 GAMAC_QoS中的多蟻群算法規(guī)則

GAMAC_QoS算法定義了三種類型的螞蟻：

（1）全智能螞蟻。螞蟻按照傳統(tǒng)蟻群算法選擇規(guī)則選擇下一節(jié)點(diǎn)，此螞蟻稱為全智能螞蟻，簡稱為M1.

（2）非智能螞蟻。螞蟻不按照選擇規(guī)則來選擇路徑，而是隨機(jī)地選擇下一節(jié)點(diǎn)，此螞蟻稱為非智能螞蟻，簡稱為M2.引入非智能螞蟻是為了在算法陷入停滯時擴(kuò)大搜索空間。

（3）半智能螞蟻。在選擇下一節(jié)點(diǎn)時以δ概率按照全智能螞蟻的選擇策略選擇下一節(jié)點(diǎn)，以1-δ概率按照非智能螞蟻的選擇策略選擇下一節(jié)點(diǎn)，此螞蟻稱為半智能螞蟻，簡稱為M3.考慮到算法在陷入停滯的時候，前期的部分次優(yōu)解還是有價值的，因此引入半智能螞蟻是最大程度地利用之前的次優(yōu)解，增加搜索最優(yōu)解的成功率。

算法開始之時，螞蟻的初值全為智能螞蟻，數(shù)目為M,執(zhí)行蟻群算法。當(dāng)算法進(jìn)行到停滯狀態(tài)且比當(dāng)前的參考值差的時刻，全智能螞蟻發(fā)生變化，一部分轉(zhuǎn)變成非智能螞蟻，一部分轉(zhuǎn)變成半智能螞蟻，余下部分保持全智能螞蟻的性質(zhì)不變，其中半智能螞蟻由智能螞蟻和非智能螞蟻組成，引入?yún)?shù)δ（0<δ<1）來決定其組成比例。

（1）適應(yīng)值函數(shù)與遺傳算法的適應(yīng)值函數(shù)相同。

（2）路徑選擇策略[6].全智能螞蟻M1,其選擇策略為：

對于非智能蟻群M2,選擇前進(jìn)策略是不考慮任何信息素的反饋信息，隨機(jī)選擇下一節(jié)點(diǎn)，其前進(jìn)策略如下：

圖2表示網(wǎng)絡(luò)費(fèi)用與迭代次數(shù)的關(guān)系，目的節(jié)點(diǎn)為20個，從圖中可以看出，隨著迭代次數(shù)的增加，該算法比基本蟻群算法具有更快的收斂性，最終組播樹的費(fèi)用也更低，與參考文獻(xiàn)[7]算法相比收斂速度上相差無幾，但是最終最優(yōu)組播樹的費(fèi)用更低。

針對蟻群算法的特點(diǎn)進(jìn)行了改進(jìn)，將遺傳算法和蟻群算法相融合，并結(jié)合多蟻群的行為，提出了GAMAC_QoS組播路由算法。通過仿真實(shí)驗(yàn)證明，該算法相比于基本蟻群算法和參考文獻(xiàn)[7]算法，在多節(jié)點(diǎn)中尋找組播樹，具有更好的尋優(yōu)能力、可靠性更高，是一種解決QoS組播路由的有效算法。