基于進化算法的下一代網絡QoS組播路由算法

浩慶波，徐巖

（曲阜師范大學網絡信息中心，山東濟寧，273100）

1 網絡模型

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

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

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

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

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

帶寬和延時是網絡中最為主要的評價參數。現規定B為組播樹T的最小帶寬約束，Δ為組播樹T的最大延時，則組播樹T需滿足：

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

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

2.1 基于蟻群算法優化的組播路由算法

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

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

2.2 基于粒子群算法優化的組播路由算法

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

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

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

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

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