基于灰狼算法的無線網絡組播路由優(yōu)化*

(中國西南電子技術研究所，成都 610036)

0 引 言

組播路由問題實際上就是在給定的網絡拓撲下，設定源節(jié)點和目的節(jié)點，找出包含源和目的節(jié)點的一顆組播樹，并且組播樹滿足約束條件(如鏈路帶寬)，使組播樹的開銷最短[1-2]。相關學者的大量研究已經證明了組播路由問題是一個NPC(Non-deterministic Polynomial Complete)問題，該問題通常無法直接求得最好結果[3]。在前人研究工作中，早期研究人員側重于尋找組播樹的最短路徑，提出了一些基于數學的優(yōu)化方法，例如Lu等人[4]提出了基于最小生成樹的動態(tài)貪婪算法,通過該算法產生的多播樹的性能在合理的范圍之內。這些算法基本上只針對一種QoS約束，應用面較窄。國內外學者結合實際問題，常用一些元啟發(fā)式算法來求解，以得到一個較優(yōu)的近似解，例如遺傳算法(Genetic Algorithm，GA)、粒子群算法(Particle Swarm Optimization，PSO)等。Chakraborty等人[5]采用了差分進化算法解決了無線網絡中多通道情況下的最小代價組播樹的構造問題。文獻[6]提出一種時延敏感網絡下的組播路由算法，通過預處理子圖的方式降低計算復雜度，并且縮短組播路徑的計算時間。文獻[7]基于圖論方案建模網絡拓撲，提出了一種基于局部鄰居信息感知的分布式組播路由算法，并通過真實示例分析驗證該算法能夠取得良好的性能。文獻[8]以最小化多個組播樹在共享鏈路上的組播路由時延為目標，提出了一種基于最短路徑樹的組播路由算法,致力于降低智能電網應用中多條組播消息同時傳輸的時延。文獻[9]提出了一種在滿足帶寬約束條件下以最小化能量消耗為目標的組播路由算法，減少維護組播路徑狀態(tài)信息的開銷，并設計休眠算法關閉未參與組播路由的節(jié)點。目前這類進化算法已經成為求解QoS組播路由問題最主要的研究方向。

本文提出了一種基于模擬灰狼群體狩獵行為的啟發(fā)式算法，即灰狼優(yōu)化算法(Gray Wolf Optimization，GWO)[10]，該算法將種群中的個體通過適應度進行排序，選出適應度最好的3個個體，所有個體都向著最優(yōu)的3個灰狼個體方向進化，通過數次迭代，能夠獲得一個接近最優(yōu)解的結果。GWO適用性很強，可以應用到很多不同問題上。本文將該算法做了一定改進，以適用于二進制的編碼方式。同時，基于一種個體變異的思想，在GWO狩獵策略執(zhí)行結束后，對所有個體執(zhí)行變異策略，一定程度上增強了算法的全局搜索性能。仿真結果表明，相比于遺傳算法，本文提出的基于灰狼優(yōu)化算法的組播路由策略能夠得到一棵開銷更小的組播樹;并且遺傳算法優(yōu)化結果波動較大，算法穩(wěn)定性較差，而本文提出的灰狼優(yōu)化算法穩(wěn)定性更強，同時算法的時間復雜度并沒有增加，充分說明了本文提出的灰狼優(yōu)化算法的高效性。

1 系統模型

本文研究由V個節(jié)點構建的多跳無線網絡，節(jié)點集合定義為V={1,2,…,V}，所有連通節(jié)點之間鏈路集合定義為E={1,2,…,E}。該無線網絡的拓撲可以視作一個無向帶權連通圖G=(V,E)，其中e(x,y)∈E表示網絡節(jié)點x與網絡節(jié)點y之間的連通鏈路。網絡中的節(jié)點均需要維護本節(jié)點與一跳鄰居節(jié)點的鏈路連通狀態(tài)，并通告其他網絡節(jié)點，使得全部網絡節(jié)點能夠實時獲得網絡拓撲圖G=(V,E)的信息。

假設源節(jié)點為s，組播目的節(jié)點集合為D={d1,d2,…,dJ}∈V-{s}。組播路由問題就是在給定的網絡拓撲G=(V,E)下，設定源節(jié)點s和目的節(jié)點集合D，找出包含源和目的節(jié)點的一顆組播樹GT=(VT,ET)，其中VT表示組播樹的點集合，ET表示組播樹的邊集合。

對于網絡中任意一個節(jié)點v∈V，定義節(jié)點度Ws(v)為該節(jié)點v在源節(jié)點s的組播樹參與的鏈路數。在資源受限的情況下，任意節(jié)點v∈V需滿足如下節(jié)點度約束：

(1)

式中：Tv,th表示節(jié)點v的節(jié)點度門限值。

對于網絡中任意一邊e(x,y)∈E，定義邊的帶寬bandwidth(e(x,y))和邊的開銷cost(e(x,y))兩種屬性。其中，邊的帶寬bandwidth(e(x,y))表示該鏈路e的最大業(yè)務承載能力，單位為Mb/s；開銷cost(e(x,y))的值為邊所連接兩個節(jié)點之間的距離。任意一條邊e(x,y)∈E，所用拓撲為在城際通信拓撲下的實際距離計算公式如下：

cost(e(x,y))=

(2)

Dlon=Rlonx-Rlony,

(3)

Dlat=Rlatx-Rlaty,

(4)

Rlonx=lonx×π/180°,

(5)

Rlony=lony×π/180°,

(6)

Rlatx=latx×π/180°,

(7)

Rlaty=laty×π/180°。

(8)

式中：lonx和latx分別為節(jié)點x的經度和緯度，lony和laty分別為節(jié)點y的經度和緯度；Rlatx和Rlaty的單位為rad；ER為地球的半徑，取值為6 371 km。latx和latx只用于計算e(x,y)的開銷，在網絡拓撲已知的前提下它是確定的。令源節(jié)點s的鏈路帶寬需求門限值為K，該源節(jié)點的組播樹中任意鏈路的帶寬均需要大于KMb/s，即

min{bandwidth(e(x,y))|e∈ET}≥K。

(9)

綜上，求解最小網絡開銷的組播路由樹的問題可建模為在網絡拓撲圖G=(V,E)中搜索目標組播路由樹GT=(VT,ET)，滿足源節(jié)點s與組播目的節(jié)點集合D={d1,d2,…,dJ}中的任意節(jié)點在拓撲子圖GT=(VT,ET)中均存在連通路徑，并使得∑e∈ETcost(e(x,y))的值最小，同時滿足節(jié)點度約束(1)和鏈路帶寬約束(9)。由于從源節(jié)點到多個目的節(jié)點之間存在鏈路耦合性，典型的單播最短路徑算法無法直接應用到求解組播樹的問題中，因此求解滿足上述條件的目標組播路由樹GT=(VT,ET)通常具有較高的復雜度。

2 基于灰狼優(yōu)化算法的組播路由策略

為了降低求解復雜度，本文采用灰狼優(yōu)化算法求解目標組播路由樹GT=(VT,ET)，解決資源受限的組播路由問題?；诨依莾?yōu)化算法的組播路由策略流程如圖1所示。

圖1 基于灰狼優(yōu)化算法的組播路由策略流程圖

Step1 確定網絡參數。通過讀取本節(jié)點實時維護的鏈路連通狀態(tài)信息，確定優(yōu)化目標和約束條件。

Step2 建立網絡拓撲。建立拓撲圖G=(V,E)，計算并賦值每條邊上的開銷cost(e(x,y))，帶寬bandwidth(e(x,y))等屬性。

Step3 初始化灰狼種群?；依欠N群規(guī)模定義為N；初始化第i個個體為二進制向量Li=[l1,l2,…,lM],li∈{0,1}，i=1,2,…,N，其中M的取值等于網絡拓撲中的總鏈路數|E|；算法最大迭代次數為Maxgen；初始化種群歷史最優(yōu)個體為best；其中，N個灰狼個體的所有M個元素均以均勻隨機的概率選擇0或1。

Step4 灰狼個體的節(jié)點度符合性檢測。對于任一灰狼個體Li=[l1,l2,…,lM]，根據網絡拓撲G=(V,E)，可以得到一個新拓撲GK=(VK,EK)，其中VK∈V,EK∈E。若新拓撲GK=(VK,EK)中存在任意節(jié)點v∈VK的節(jié)點度Ws(v)=∑y∈VK,y≠v,e(v,y)∈EKe(v,y)大于Tv,th，則將該灰狼個體中從這Tv維非零元素中隨機選擇Tv-Tv,th維元素重置為零，可以得到一個符合節(jié)點度約束的新拓撲GL=(VL,EL)。

Step5 灰狼個體適應值計算。通過適應度函數計算每個灰狼個體的適應度值。個體適應度值表示該灰狼個體對應的滿足約束條件的組播路徑(即組播生成樹)的鏈路開銷之和。如果不滿足源節(jié)點和任意目的節(jié)點連通，將個體適應度置為一個足夠大的值。在新拓撲GL=(VL,EL)上，去掉不滿足帶寬約束的鏈路后，如果GL=(VL,EL)滿足組播源節(jié)點到任意目的節(jié)點di∈D,i∈{1,2,…,J}均連通(即源到目的地至少有一條可達路徑)，則以組播源節(jié)點s為起點、EL中各邊上的開銷為權值，每個目的節(jié)點執(zhí)行1次Dijkstra算法，得到源到任意目的節(jié)點的最短路徑，用w(s,dj)表示，得到的J條源到目的地的最短路徑組合起來，去掉重復邊，可以得到一棵組播樹GT=(VT,ET)，VT∈V,ET∈E，VT表示組播樹中存在的所有節(jié)點的集合，ET表示組播樹中存在的所有邊的集合。灰狼個體Li的適應度計算函數為Fitness(L)=∑e∈ETcost(e)，計算得到組播樹GT的開銷，即為灰狼個體Li的適應度值。

Step6 個體適應度選優(yōu)。通過比較個體適應度，選出適應度值最優(yōu)、第二優(yōu)和第三優(yōu)的個體，分別賦值給α、β、δ。

Step7 灰狼狩獵行為。選擇α、β、δ個體作為參照目標，當代灰狼群體展開狩獵行為，更新每一個灰狼個體的參數。個體L的每一維li取值表示該目標組播樹中是否包含第i條鏈路，以α=[α1,α2,…,αM]為目標對灰狼個體L的每一條鏈路選取進行更新，具體步驟如下：

(10)

(11)

(12)

(13)

位置更新后得到新灰狼個體，完成一次灰狼個體的狩獵行為。

Step8 灰狼個體變異。以變異概率Pm對搜索后的每個個體的每一維進行變異操作。若更新后的種群中，當代最優(yōu)個體優(yōu)于種群歷史最優(yōu)個體，那么用該個體替換種群歷史最優(yōu)個體，否則保持不變。每一維的變異操作如下：

(14)

Step9 算法收斂判斷。判斷算法是否達到最大迭代次數Maxgen，滿足則算法結束，輸出歷史最優(yōu)個體best，以及對應的組播樹；否則轉到Step 4。

3 性能分析

本文所有實驗運行的軟硬件環(huán)境為：Windows 10 OS，Intel(R) Core(TM) i5-4210M CPU 2.6 GHz+8 GB RAM。所有算法采用Python 3.6 仿真。

3.1 仿真參數設置

為了驗證GWO算法在求解組播樹問題上的高效性，采用了4個不同的場景與遺傳算法進行對比，來說明本文GWO算法的收斂性更好，能夠得到更好的優(yōu)化結果。場景設置如下：

場景1：節(jié)點數49，邊數84，組播源節(jié)點：14，目的節(jié)點：{39,20,48,17}，帶寬約束為8 Mb/s，不滿足帶寬約束的鏈路為1條。算法種群規(guī)模都為20，迭代次數為100。

場景2：節(jié)點數53，邊數89，組播源節(jié)點：39，目的節(jié)點：{28,42,7,35,49}，帶寬約束為8 Mb/s，不滿足帶寬約束的鏈路為1條。算法種群規(guī)模都為20，迭代次數為100。

場景3：節(jié)點數58，邊數87，組播源節(jié)點：1，目的節(jié)點：{50,51,44,35,49}，帶寬約束為8 Mb/s，不滿足帶寬約束的鏈路為1條。算法種群規(guī)模都為20，迭代次數為100。

場景4：節(jié)點數145，邊數186，組播源節(jié)點：98，目的節(jié)點：{81,25,52,120,60}，帶寬約束為8 Mb/s，不滿足帶寬約束的鏈路為2條。算法種群規(guī)模都為20，迭代次數為100。

3.2 實驗結果分析

兩種算法都運行20次，計算在4個不同場景下的歷史最優(yōu)適應度的平均值、歷史最優(yōu)適應度的標準差，以及算法的平均運行時間，如表1所示。

表1 兩種算法結果對比

啟發(fā)式算法是隨機搜索的算法，具有一定的偶然誤差，通過運行多次，可以在統計學上得到較為準確的性能評估。適應度平均值AVG和適應度標準差STD的計算公式分別如下：

(15)

(16)

式中:N=20，xi表示每一次運算運行得到的最優(yōu)解。

圖2為兩種算法的歷史最優(yōu)適應度對比曲線。算法每次迭代過程中，產生一個當代種群最優(yōu)解，與歷史最優(yōu)解比較，如果比歷史最優(yōu)解好，則替換歷史最優(yōu)解；否則不保留。將GA和GWO分別運行20次，對每次求得的歷史最優(yōu)適應度取平均值，得到最終的歷史最優(yōu)適應度。

(a)場景1

圖3為兩種算法的平均適應度對比曲線。將GA和GWO分別運行20次，對每次求得的平均適應度取平均值，得到最終的平均適應度。

(a)場景1

通過對兩種算法運行結果的對比分析，可以得到以下結論：對于節(jié)點度約束和帶寬約束的組播路由問題，給定一個網絡拓撲與種群規(guī)模，迭代次數相同的情況下，本文提出的基于灰狼優(yōu)化算法的組播路由策略可以得到更好的優(yōu)化結果，能夠得到一棵開銷更小的組播樹。由于GA和GWO算法均是基于隨機搜索的啟發(fā)式算法，因此在算法迭代過程中容易出現性能波動。仿真結果表明，遺傳算法優(yōu)化結果波動較大，算法穩(wěn)定性較差；與遺傳算法相比，本文提出的基于灰狼優(yōu)化算法的組播路由策略穩(wěn)定性更強，同時算法的時間復雜度并沒有增加，充分說明了本文提出的基于灰狼優(yōu)化算法的組播路由策略的高效性。

4 結 論

針對無線網絡中資源受限的組播路由問題，考慮網絡節(jié)點的節(jié)點度限制和網絡鏈路的帶寬約束，以最小化組播路由開銷為目標，本文提出了一種二進制編碼方式的基于灰狼優(yōu)化算法的組播路由策略。在給定的網絡拓撲下，該策略可以迅速找到一棵包含源和目的節(jié)點的組播樹，使得開銷盡可能小。仿真結果表明，相比于遺傳算法，本文提出的基于灰狼優(yōu)化算法的組播路由策略能夠得到一棵開銷更小的組播樹，并且在相同的時間復雜下具有更強的算法穩(wěn)定性。