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

浩慶波，徐巖

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

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

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

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

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

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

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

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

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

2 基于進化算法的組播路由算法

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

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

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

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

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

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

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

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

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