基于進(jìn)化算法的下一代網(wǎng)絡(luò)QoS組播路由算法

浩慶波，徐巖

（曲阜師范大學(xué)網(wǎng)絡(luò)信息中心，山東濟(jì)寧，273100）

1 網(wǎng)絡(luò)模型

組播路由是將發(fā)送者和多個(gè)接收者之間實(shí)現(xiàn)點(diǎn)對(duì)多點(diǎn)的信息傳輸技術(shù)。組播路由技術(shù)的使用，能夠降低網(wǎng)絡(luò)出現(xiàn)擁塞的可能性，從而提高數(shù)據(jù)在網(wǎng)絡(luò)中的傳輸效率。組播路由技術(shù)是以數(shù)據(jù)源節(jié)點(diǎn)為根節(jié)點(diǎn)，依據(jù)網(wǎng)絡(luò)結(jié)構(gòu)和數(shù)據(jù)傳輸約束在多個(gè)目的節(jié)點(diǎn)之間構(gòu)建組播路由樹，以完成組播數(shù)據(jù)的傳輸。通常我們借助于斯泰納(Steiner)問題對(duì)組播路由問題進(jìn)行研究。在Steiner問題中，求解其最小樹MST(Minimum Steiner Tree,MST)的過(guò)程即是求解最小的組播樹的過(guò)程。

為更為直觀的描述組播路由問題，我們使用有向賦權(quán)圖G = ( V,E) 描述計(jì)算機(jī)網(wǎng)絡(luò)，其中V表示網(wǎng)絡(luò)節(jié)點(diǎn)集，E表示通信鏈路集。在通信網(wǎng)絡(luò)中，我們對(duì)每一條通信鏈路 Vi都定義三個(gè)加權(quán)值進(jìn)行描述，其中均為正實(shí)數(shù)。Bij表示節(jié)點(diǎn)i與節(jié)點(diǎn) j之間鏈路的帶寬，Cij則表示節(jié)點(diǎn)i與節(jié)點(diǎn) j之間鏈路傳輸數(shù)據(jù)的代價(jià)，Cij值的大小也反映出該鏈路資源的使用情況；Dij表示節(jié)點(diǎn)i與節(jié)點(diǎn) j之間鏈路的傳輸延時(shí)。為簡(jiǎn)化網(wǎng)絡(luò)模型，假設(shè)網(wǎng)絡(luò)中每?jī)蓚€(gè)節(jié)點(diǎn)的雙向鏈路權(quán)值相等，即。且網(wǎng)絡(luò)中每?jī)蓚€(gè)節(jié)點(diǎn)最多存在一條連通鏈路。

組播問題即為花費(fèi)最小代價(jià)將數(shù)據(jù)從源節(jié)點(diǎn)s∈V發(fā)送到一組多個(gè)目的節(jié)點(diǎn) D ?V-{s}。組播樹為,其中。可知組播路由樹滿足如下幾個(gè)條件：

從源節(jié)點(diǎn)s到所有目的節(jié)點(diǎn)d∈D的所有路徑中，最小帶寬為組播樹T的帶寬

從源節(jié)點(diǎn)s到目的節(jié)點(diǎn)d∈D的所有路徑中，最大延時(shí)為組播樹T的延時(shí)

帶寬和延時(shí)是網(wǎng)絡(luò)中最為主要的評(píng)價(jià)參數(shù)。現(xiàn)規(guī)定B為組播樹T的最小帶寬約束，Δ為組播樹T的最大延時(shí)，則組播樹T需滿足：

組播路由樹的尋找方法通常是采用例如SPH算法，KPP算法等啟發(fā)式的方法。啟發(fā)式算法存在運(yùn)算復(fù)雜度過(guò)大，收斂性能差等問題。

2 基于進(jìn)化算法的組播路由算法

2.1 基于蟻群算法優(yōu)化的組播路由算法

蟻群算法(Ant Colony Optimization)是基于種群的一種模擬進(jìn)化算法，由Dorigo等人首先提出。借助于蟻群算法對(duì)組播路由算法進(jìn)行優(yōu)化，簡(jiǎn)稱OQMRA算法，步驟如下：⑴首先對(duì)網(wǎng)絡(luò)進(jìn)行初始化，即對(duì)網(wǎng)絡(luò)中的相關(guān)信息素進(jìn)行賦值初始化。對(duì)每一個(gè)節(jié)點(diǎn)鏈路(Bij,Cij,Dij)，進(jìn)行初始化賦值。定義每條鏈路邊(i，j)的信息濃度，并初始化信息濃度值r。⑵根據(jù)需求從源節(jié)點(diǎn)釋放出M只螞蟻進(jìn)行探路，螞蟻按照規(guī)則進(jìn)行路徑選擇，即每只螞蟻都執(zhí)行步驟(3)。⑶首先確定螞蟻?zhàn)约核?jié)點(diǎn)的臨近節(jié)點(diǎn)集合，然后從中隨機(jī)選擇一個(gè)節(jié)點(diǎn)，按照重復(fù)應(yīng)用狀態(tài)選擇規(guī)則選取行走路徑。當(dāng)螞蟻選擇路徑并行走成功后，依據(jù)局部更新規(guī)則對(duì)螞蟻所選擇的路徑信息素進(jìn)行更新。⑷對(duì)每一只螞蟻都重復(fù)執(zhí)行步驟(3)，直至M只螞蟻都更新完路徑信息素。⑸當(dāng)所有螞蟻都完成路徑選擇后，根據(jù)M只螞蟻選擇的路徑選取全局最優(yōu)路徑，即代價(jià)最小的路由路徑。依據(jù)全局更新規(guī)則更新全局路徑信息素。⑹重復(fù)執(zhí)行直到達(dá)到迭代次數(shù)的要求為止，根據(jù)結(jié)果獲得最優(yōu)路徑。

OQMRA的算法特點(diǎn)：⑴在OQMRA算法中，若螞蟻數(shù)量M值過(guò)小，則產(chǎn)生的信息素不能夠反映出選取路由的行為；反之，若M的值過(guò)大則會(huì)加重網(wǎng)絡(luò)負(fù)擔(dān)并導(dǎo)致網(wǎng)絡(luò)性能惡化。依據(jù)經(jīng)驗(yàn)，通常定義M的值等于網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)N。⑵根據(jù)算法描述，不難計(jì)算出OQMRA算法的初始化復(fù)雜度為 O (N2?W)；每只螞蟻的MST的復(fù)雜度為 D (X ?M?N2)，更新 r(t)的復(fù)雜度為O(X ?M?N2)，其中W為網(wǎng)絡(luò)頂點(diǎn)數(shù)，N為節(jié)點(diǎn)數(shù)，X為循環(huán)代數(shù)；OQMRA算法的總復(fù)雜度為

2.2 基于粒子群算法優(yōu)化的組播路由算法

粒子群算法，也稱粒子群優(yōu)化算法（Particle Swarm Optimization, PSO）是一種具有收斂快、精度高等優(yōu)點(diǎn)的新的進(jìn)化算法。粒子群算法之所以也被稱為鳥群覓食算法，其算法的實(shí)質(zhì)就是模擬鳥群尋找食物的遷徙過(guò)程。在粒子群算法中，使用粒子群中每個(gè)粒子的運(yùn)動(dòng)方向來(lái)模擬鳥群中鳥兒的飛行方向，使用粒子每次移動(dòng)變換的距離來(lái)模擬鳥兒的飛行速度。粒子群算法需要依靠粒子群的群體協(xié)作進(jìn)行最優(yōu)化選擇，其實(shí)質(zhì)是一種并行化的優(yōu)化算法。

影響粒子群優(yōu)化算法精度的關(guān)鍵在于算法的適應(yīng)度函數(shù)。通過(guò)適應(yīng)度函數(shù)計(jì)算粒子群中每個(gè)粒子的適應(yīng)度值，適應(yīng)度值是評(píng)判該粒子是否為最優(yōu)解的關(guān)鍵指標(biāo)。粒子群中每個(gè)粒子都知道當(dāng)前群體的最優(yōu)位置（即當(dāng)前群體中最優(yōu)適應(yīng)度值粒子的位置）和局部最優(yōu)位置（即該粒子最優(yōu)適應(yīng)度值的位置）。粒子群中所有粒子依據(jù)群體最優(yōu)位置和局部最優(yōu)位置更新自己的移動(dòng)方向和速度，從而確定粒子新的適應(yīng)度值和位置信息。

其中1≤i≤m，1≤d≤n，k為該算法的迭代次數(shù)（k≥1）。為隨機(jī)數(shù)函數(shù)，生成[0，1]之間隨機(jī)數(shù)值。c1,c2為非負(fù)數(shù)。c1表示粒子自身的認(rèn)知系數(shù)，c2表示粒子的社會(huì)認(rèn)知系數(shù)。vmax為最大的運(yùn)動(dòng)速度，該值通常由用戶來(lái)設(shè)置，若vmax取值較大時(shí)利于全局范圍內(nèi)的搜索，但其搜索步伐過(guò)大容易錯(cuò)過(guò)最優(yōu)解。反之，若 vmax取值較小，搜索步伐較小，有利于局部范圍內(nèi)精細(xì)搜索，但易使算法困于局部最優(yōu)解。因此vmax的值需要根據(jù)問題經(jīng)驗(yàn)進(jìn)行設(shè)定。表示粒子前次運(yùn)動(dòng)的速度，使得每個(gè)運(yùn)動(dòng)的粒子在其搜索空間中能夠向各個(gè)方向進(jìn)行探索。為粒子自身的運(yùn)動(dòng)過(guò)程，粒子自身的運(yùn)動(dòng)過(guò)程其實(shí)質(zhì)就是該粒子認(rèn)知、探索的過(guò)程。則為某粒子學(xué)習(xí)其它粒子運(yùn)動(dòng)經(jīng)驗(yàn)的過(guò)程，粒子群的粒子借助該式分享運(yùn)動(dòng)經(jīng)驗(yàn)。若某個(gè)粒子沒有自身的運(yùn)動(dòng)過(guò)程，那么稱該粒子群為只存在社會(huì)部分模型。粒子群算法是借助于每個(gè)粒子間的互相協(xié)作來(lái)尋求最優(yōu)解的，若所有粒子缺乏自身認(rèn)知過(guò)程，那么該種粒子群就無(wú)法求解出問題域的全局最優(yōu)解，且容易使得算法陷于局部最優(yōu)解之中。

粒子群的算法步驟：⑴隨機(jī)初始化粒子群中每個(gè)粒子的相關(guān)信息，包括粒子運(yùn)動(dòng)速度和所處位置。⑵結(jié)合需要解決的實(shí)際問題，給出合適的適應(yīng)度值函數(shù)并算出粒子的相應(yīng)適應(yīng)度值。⑶更新粒子的局部最優(yōu)解：對(duì)比粒子此時(shí)的適應(yīng)度值和歷史局部最優(yōu)位置的適應(yīng)度值。若粒子此時(shí)的適應(yīng)度值大于該粒子歷史局部最優(yōu)位置的適應(yīng)度值，則更新該粒子的歷史局部最優(yōu)位置和適應(yīng)度值；反之，不進(jìn)行更新。⑷更新粒子群的全局最優(yōu)解：將全局最優(yōu)位置的適應(yīng)度值與粒子群中每個(gè)粒子的局部最優(yōu)位置適應(yīng)度值進(jìn)行比較，若某個(gè)粒子的適應(yīng)度值大于全局最優(yōu)適應(yīng)度值，則更新全局最優(yōu)位置和適應(yīng)度值。⑸根據(jù)粒子運(yùn)動(dòng)方向和速度，重新計(jì)算每個(gè)粒子的下一個(gè)所處位置和運(yùn)動(dòng)速度。⑹判斷是否滿足終止條件：若條件滿足，算法結(jié)束，否則，返回第（2）步。

粒子群算法在求解最優(yōu)解過(guò)程中具有魯棒性強(qiáng)、收斂速度快、求解質(zhì)量高等特點(diǎn)。但其在迭代過(guò)程中也容易陷入到局部最優(yōu)解，從而不能準(zhǔn)確找到全局最優(yōu)解[9]。