基于改進灰狼優化算法的無線傳感器網絡路由協議*

安葳鵬，邵一帆

(河南理工大學計算機科學與技術學院，河南 焦作454003)

無線傳感器網絡(Wireless Sensor Network，WSN)是由部署在特定監測區域內的大量微型傳感器節點構成的自組織網絡系統[1]，各節點通過無線通信方式將它們監測到的環境參數或特定數據以單跳或多跳的方式傳輸給一個或多個數據接收器。 無線傳感器網絡可應用于多種復雜的環境，通常傳感器節點由電池供電，且節點的存儲容量有限，處理能力低，在大多數應用環境中能源裝置不便于更換。因此對于解決無線傳感器網絡節點能耗問題，設計低功耗路由協議以降低無線傳感器網絡整體能耗，延長網絡生存時間具有深遠意義[2-4]。

為了解決無線傳感器網絡能耗問題，Lindsey S等人在LEACH 協議[5]的基礎上改進并提出了PEGASIS(Power-Efficient Gathering in Sensor Information Systems)協議[6-9]，該協議主要用貪心算法將所有的節點連接成一條單鏈，并由基站隨機選取簇頭，使數據從鏈兩端開始傳遞到簇頭，再由簇頭將信息發送給基站，雖然該協議在延長節點壽命，平衡節點能耗上起到一定效果，但仍存在很多缺點:易因局部最優而產生長鏈；單鏈路傳輸對通信質量的要求很高，當網絡規模增大時，會增加網絡時延，不適用于對實時性要求高的環境；一旦有節點死亡，則會導致整個網絡癱瘓，魯棒性差。

針對上述問題，文獻[10]提出TTEMR 協議，它將網絡構造成雙層樹型多鏈路結構，分鏈和鏈頭鏈均通過啟發式算法優化，并對網絡孤立點進行樹型結構化處理，降低了數據傳遞路徑長度，但TTEMR協議需要構造樹型結構，計算量較大，且數據傳輸時對于一些節點接收融合數據的能耗過大，易導致其過早死亡。 文獻[11]提出PEGASIS-I 協議，將區域進行劃分，并在子區域內生成通信路由樹，由樹根與基站直接通信，有效降低數據傳輸延遲。 文獻[12]提出PEGASIS-C 協議，它也是將區域進行劃分，采用多跳路由進行數據通信，既減少數據鏈長度，又降低出現“長鏈”的概率；近些年，一些學者將群智能算法[13-17]引入到無線傳感器路由協議中，通過群智能算法動態選擇簇頭，均衡整個網絡能耗。 文獻[18]提出一種基于改進灰狼優化算法的分簇路由協議，有效延長了網絡生存周期，但簇頭節點與基站之間的單跳信息傳輸，導致簇頭節點能量消耗過快，從而使整體網絡能耗不均。 文獻[19]提出一種基于灰狼優化器的集中式分簇路由協議，該協議簇頭節點在中繼選擇階段并非都能找到下一跳路由節點，因此，同樣面臨簇頭與基站直接通信問題，從而導致網絡能耗不均。

為了延長無線傳感器網絡生存周期，本文在PEGASIS 的基礎上采用分區的思想，主要是通過有效區域劃分的方式進行局部小范圍建鏈，這種分區建鏈的方法能避免整體成鏈產生長鏈以及在數據傳輸時由于網絡傳輸效率降低而加大節點能耗；此外，通過改進灰狼優化算法，使得簇頭選擇更加合理有效，在均衡網絡能耗方面更加高效、節能。

1 PEGASIS 分簇路由協議模型與設計

1.1 網絡模型

假設一個傳感器網絡由n個隨機部署的傳感器節點構成，用Si表示第i個節點，相應的節點集合為{S1，S2，…，Sn}。 該傳感器網絡具有以下性質:①所有節點具有相同初始特性，隨機分布在監測區域且位置不變；②節點之間都可以互相通信，也可以與基站直接進行通信；③基站是固定的，能量沒有限制且能量可以滿足監測區域能量需要；④節點能量有限且消耗完才會死亡。

1.2 能量模型

改進協議和仿真均采用經典能耗模型。 式(1)ETX(k，d)表示傳感器節點發送kbits 到距離為d的鄰節點所消耗的能量，由發射電路損耗和功率放大損耗兩部分構成，式(2)表示接收kbits 數據的能量損耗，式(3)表示融合kbits 數據消耗的能量。

式中:d為傳輸距離，εfs和εamp分別是自由空間能量模型系數和衰減空間能量模型系數，Eelec表示發送或接收1 bit 數據消耗的能量，Efs表示融合1 bit 數據消耗的能量。

1.3 改進的PEGASIS 協議設計思路

改進的PEGASIS 協議采用分簇的方式，以固定的基站為圓心，在得到各節點的分布密度信息后在同心圓維度把監測區域劃分多個環帶，針對監測區域較大的問題，為減少節點遠距離傳輸能耗，在環帶分區基礎上，將監測區域繼續劃分為多個扇形區域，形成扇形環帶分區，每個子區域內的節點按位置分簇，每個分簇構造一條最優簇內鏈，在選舉簇內鏈的簇頭時，利用改進灰狼優化算法進行最優簇頭的選取；在后續迭代中，對權重進行動態更新，以便繼續對簇頭進行遴選；當各子區域完成建鏈并選出簇頭之后，最終將收集到的信息沿著分區內的簇頭鏈傳遞給基站。 改進PEGASIS 協議主要由分區、建鏈、選取簇頭、數據傳輸四個階段組成。

2 基于改進灰狼優化算法的PEGASIS協議

2.1 灰狼優化算法

灰狼優化算法(Grey Wolf Optimizer，GWO)[20]模擬了灰狼種群的捕食行為，將狼群搜捕獵物的過程類比為尋優過程，達到尋找最優解的目標，是一種典型的群智能優化算法。 已有一些學者將灰狼優化算法應用于無線傳感器網絡的優化問題中[21-23]，以狼群的位置表示傳感器節點的位置，獵物的最佳位置對應最優簇頭。

灰狼群體內有嚴格的等級制度，如圖1 所示。這種嚴格的社會等級劃分，能更好地進行狩獵，其狩獵過程可分為搜索包圍和狩獵。 在狩獵過程中，狼群的初始位置是隨機的，通過不斷搜索獵物，獲得最終獵物的位置。

圖1 狼群等級制度示意圖

①包圍獵物

捕獵時，灰狼要先得知獵物的位置然后包圍獵物，因此需要首先確定灰狼與獵物的距離，對這個過程進行數據建模，得到狼群個體與獵物距離的表達公式:

式中:t代表當前迭代次數，Xp(t)是算法在第t次迭代時獵物位置，X(t＋1)是第t＋1 次迭代時灰狼位置。H和C表示系數因子，其計算公式分別為:

式中:a是收斂因子，在整個迭代過程中從2 線性減小為0；r1和r2取[0，1]范圍內的隨機值。

②獵殺獵物

灰狼種群中，由于α、β和δ狼具有豐富的經驗，能對獵物位置做出更好的判斷，所以由它們領導狼群狩獵，此過程可以利用α、β和δ狼三者的位置來確定獵物所在的位置，達到尋優的目的。 在搜索所需獵物的時候，灰狼一般會先識別獵物然后將其包圍，在每次迭代的過程中，保留當前最好的三只灰狼，根據它們的位置信息更新其余狼的位置。 當獵物不再移動時，灰狼會通過攻擊來捕捉獵物。

由狼群狩獵機制可清晰得出，若要獲得獵物的準確位置，狼群先大致了解獵物位置以更新自身初始位置，根據α、β和δ狼的位置估算獵物位置。 而估算獵物位置的前提是需要知道α、β和δ狼與獵物的距離，α、β、δ狼根據它們與獵物的距離由式(6)計算下一刻的位置，第t＋1 次迭代時，獵物的位置如式(7)所示:

式中:Xα(t)、Xβ(t)和Xδ(t)分別是此刻α、β、δ狼的位置；H1、H2和H3，C1、C2和C3的計算方法如式(5)。

2.2 改進灰狼優化算法

當灰狼優化算法中對求解獵物位置的權重因子分配不合理時容易陷入局部最優，為了更好地應用于無線傳感器網絡，選出最合適的簇頭，針對傳感器節點特性，對獵物位置權重進行動態更新，提出一種改進的灰狼優化算法。 具體方法為，將無線傳感器節點看作灰狼個體，在設計灰狼優化算法適應度函數時，將影響WSN 生命周期的相關參數以不同權重關聯起來，找出灰狼群體中適應度值前三的灰狼個體，根據這三個個體的位置對獵物位置進行計算，所對應的獵物位置即為最優簇頭的位置。 在算法后續的迭代中，基于動態調整權重更新節點位置。

2.2.1 適應度函數設計

為了使設計的適應度函數更好地適用于無線傳感器，結合本文均衡節點能效，延長網絡生命周期的目標，對適應度函數的設計主要考慮節點耗能比、同一扇形環帶區域中節點間距離以及同一扇形區域中，相鄰扇形環帶中兩簇頭距離平方的期望三個因素。

①節點耗能比。 節點剩余能量Eres與初始能量E0的比值，記作Q，Q值越大，說明此節點能量消耗越均衡；

②同一扇形環帶區域中節點間距離。 即分別對應α、β、δ狼之間的距離，記作D；

③同一扇形區域中，相鄰扇形環帶中兩簇頭距離平方的期望，記作。

基于能量和位置因素，改進算法適應度函數為:

式中:f1、f2、f3是平衡傳感器節點耗能比、同一子區域節點間距離以及同一扇區相鄰子區域中簇頭間距離平方的期望的權重系數。

2.2.2 基于動態權重的灰狼優化算法

在算法開始執行時，由于獵物的位置是由狼群的初始位置決定，初始化過程應充分利用狼群的位置，考慮到節點沿著鏈路傳輸數據，故將節點間的相互距離轉換為相應的權重作為尋找獵物位置的初始權重因子。 獵物的初始位置為Xp(0)為:

式中:Xα(0)，Xβ(0)，Xδ(0)是α、β、δ狼的初始位置；Dα，β、Dβ，δ、Dδ，α分別表示α、β、δ狼間的距離；ωα、ωβ、ωδ分別表示初始狀態下，各灰狼間距離相對于獵物的初始權重。

在算法后續的迭代中，根據下式基于動態調整權重更新權重因子:

t＋1 次迭代后，獵物的位置更新為Xp(t＋1)，其中，Xα(t＋1)，Xβ(t＋1)，Xδ(t＋1)分別是α、β、δ狼在第t＋1 次迭代時的位置。

2.3 基于改進灰狼優化算法的PEGASIS 協議實現

在基于改進灰狼優化算法的PEGASIS 協議實現過程中，首先對網絡節點進行初始化，然后開始建鏈、選擇簇頭、數據傳輸等過程，反復迭代更新節點信息，將融合數據傳送給基站，直至網絡節點全部死亡，具體流程如圖2 所示。

圖2 改進PEGASIS 協議流程圖

2.3.1 網絡分區階段

當網絡節點被部署后，基站要確定隨機分布在監測區域內的節點的位置，此時，每個節點將自己的ID 信息和到基站的距離發送給基站。 以基站為中心建立直角坐標系，基站將整個監測區域看成以自身為圓心的圓形區域，在得到各節點的分布密度信息后把監測區域劃分為多個以基站為圓心的同心圓，每個圓環間距為Δd，各環間距Δd相等，即各環間距是均勻分布的。 此外，如果監測區域比較大，會出現子區域內由于傳輸距離遠導致節點與節點、節點與簇頭、簇頭與基站之間傳輸負荷大，易提前耗盡能量而死亡，針對此問題，在環帶分區的基礎上，以基站為圓心，將監測區域劃分扇形子區域，每個扇形子區域相隔的角度為θ(0°＜θ＜90°)，可以將整個圓形區域分成2π/θ個扇形子區域，并按逆時針進行編號。 如圖3 所示，形成扇形環帶分區，第一環帶內的節點，在扇形區域內建鏈，超出第一環帶的節點在扇形環帶區域內建鏈。

圖3 扇形環帶區域劃分圖

2.3.2 網絡建鏈階段

分區結束后，網絡開始建鏈。 由于監測區域已完成分區，因此每個節點都有同區域標記和異區域標記兩個標記，各子區域相當于一個簇分別建鏈，以同處一個扇形區域中的節點為例，子區域內部成鏈時，設置同區域標記，對每個環帶子區域中的節點進行編號，計算每個節點的適應度值，遍歷每個節點路徑依次成鏈，形成多條鏈路，比較各鏈路長度，選擇最短的路徑作為初始鏈路。 子區域間成鏈時，設置異區域標記，在簇頭之間朝著基站方向形成一條簇頭鏈。 節點分布建鏈示意圖如圖4 所示。 當各分簇中節點數量小于3 時，由于節點數量過少導致無法建鏈或者建鏈無效，即在分區內節點無法成簇，此時將該區域的少量節點定義為孤立節點。 對于基站附近的孤立節點，為了避免延長節點通信路徑和數據逆傳，可直接與基站進行通信；對于遠離基站超出通信距離的孤立節點，向周圍發送廣播信息，同扇區靠近基站方向且距離該節點最近的帶有異區域標記節點做出響應，孤立節點根據響應與之建立通信連接，并將數據轉發給該節點。

圖4 區域內節點分布建鏈圖

2.3.3 選擇簇頭階段

在同一扇區的每個環帶子區域中，對于節點數少于3 的子區域，不進行建鏈和簇頭選擇，作為孤立節點對數據進行傳輸；對于節點數不少于3 的子區域，則按照改進的灰狼優化算法，先進行初始化操作，在未達到最大迭代次數前，執行循環，計算每個節點的適應度值，并對每個子區域中節點適應度值進行排序，排名前三的節點視為α、β、δ狼，更新獵物位置，由獵物位置映射到簇頭節點位置，獲得最優解，簇頭選擇結束。

通過改進灰狼優化算法選擇簇頭后，在后續過程，各分簇不是每輪傳輸過后都對簇頭進行更新，經過一段時間后，基站會將各子區域簇頭剩余能量Eres與初始能量E0的比值Eres/E0即節點耗能比Q，與設定的節點能量閾值Ethres做比較以決定簇頭的更新時間，因為隨著網絡能耗的增加，簇頭節點Eres/E0逐漸變小，故該閾值是可變的，且隨網絡節點能量消耗逐漸減小，在對其初值設定時大小應適中，若初始閾值過小，表明在簇頭剩余能量很少時才開始更換，難以均衡節點能量；若初始閾值過大，簇頭節點的更換會比較頻繁，這樣會加大網絡能耗。若Eres/E0不小于Ethres，則不更新簇頭節點和能量閾值，繼續進行下一輪數據傳輸；若Eres/E0小于Ethres，此時需要重新選擇簇頭并更新能量閾值。

2.3.4 數據傳輸階段

PEGASIS 協議的核心思想是使鏈中的每個節點將感知得到的信息沿著長鏈依次發送至鏈頭，隨后鏈頭節點將感知到的信息進行處理、融合轉發至基站。與傳統的鏈式協議不同的是，在信息傳輸的初始階段，首先每個子區域按照上兩節所述內容形成鏈路并選出簇頭，數據分別從鏈路的兩個端節點開始朝著簇頭方向傳遞，簇頭接收到簇內所有節點的數據之后，沿著簇頭鏈傳向離基站更近的下一子區域的簇頭，直至數據全部被基站接收。 如果子區域中出現節點死亡，則需要重新建立鏈路，然后繼續傳輸數據。 重復以上步驟，直到區域內所有節點能量耗盡。

3 仿真與性能分析

為驗證改進協議的性能，與PEGASIS、PEGASIS-C、TTEMR 進行比較，采用MATLAB 進行仿真。 仿真環境設置在半徑為150 m 的圓形區域中，監測區域內隨機均勻分布100 個節點，基站位于圓心，其坐標為(0，0)。 仿真環境參數設置如表1 所示。

表1 仿真環境參數設置

3.1 參數的選取

對監測區域進行分區時，要考慮環間距Δd和θ對網絡生命周期的影響，它們直接影響改進協議在該實驗環境下的性能，監測區域中節點分布密度不同，最佳參數值的設置也不同，原則上區域面積越大，分環數應該越多，但并不是越多越好，當環數達到某一最優值后，繼續增加區域環數反而會降低網絡性能，其原因一方面是由于分環數越多則每個子區域內的節點數越少，不利于簇頭的最優選擇，其次，隨著環數的不斷增加，簇頭接收、聚合、轉發的能耗增量抵消了多跳導致的能耗增量，加速距離基站較近的簇頭節點的死亡；同時，跳數過多也會大大增加網絡延遲，影響網絡通信。 表2 是實驗設置的不同Δd和θ值，通過仿真對比確定最佳參數。 圖5 是Δd和θ相互映射下取不同值時網絡性能對比情況。通過對比圖可以得出:當Δd取50，θ取π/3 時，節點存活時間最長，網絡性能最佳。

圖5 不同參數下節點存活數對比柱狀圖

表2 參數Δd 和θ 的確定

3.2 鏈路對比

PEGASIS 采用鏈狀的路由結構，通過貪婪算法計算形成一條包含所有節點的長鏈，如圖6(a)所示。 而改進協議采用分區成鏈的方法，通過仿真測出該實驗環境下的環間距Δd和θ最優值，劃分網絡區域，在每個子區域中分別建立鏈路，如圖6(d)所示。 圖6 (b) 和 圖6 (c) 分 別 是TTEMR 和PEGASIS-C 的鏈路圖，相對于PEGASIS，二者基本解決了長鏈問題，但與改進協議相比較，TTEMR 需要構造樹型結構，計算量較大且數據傳輸時對于一些節點接收融合數據的能耗過大易導致其過早死亡；PEGASIS-C 雖然也進行了分區，但相比改進協議對鏈路的優化不明顯，而且區域內鏈路存在交叉鏈，增加了鏈路平均路徑長度，降低了傳輸效率。

圖6 不同協議鏈路圖

3.3 生存周期對比

以監測區域節點向基站發送一次數據為一輪，對比四種協議每輪存活節點數，從圖7 仿真結果可以看出，隨著輪數的增加，改進協議存活節點的數量比PEGASIS、TTEMR 和PEGASIS-C 更多，而且首節點死亡輪數和最后一個節點死亡輪數都有明顯的增加，這是由于改進協議通過多重分區形成了局部小范圍成簇，建鏈時有效避免了長鏈的產生，降低了節點遠距離通信的開銷，從而減少了節點能耗，延長了網絡整體生存時間。

圖7 節點生存周期對比圖

對四種協議網絡能耗進行對比，從圖8 仿真結果可以看出，隨著輪數的增加，迭代次數越來越多，改進協議的網絡能耗更加均衡，持續的輪次更多，除多重分區形成局部成簇縮短鏈長的原因，還有一個因素是改進協議在簇頭選擇時采用改進的灰狼優化算法，遴選出更合適的簇頭，降低了簇頭節點的能耗，縮小了網絡節點間的能耗差異，使能耗整體均衡分布，延長了網絡生存周期。

圖8 網絡剩余總能量對比圖

4 結束語

改進PEGASIS 協議在PEGASIS 的基礎上通過采用分區的思想進行有效分區，采取局部小范圍建鏈的方式，更好地避免整體成鏈產生的長鏈以及在數據傳輸時由于網絡傳輸效率降低而加大節點的能耗；此外，該協議通過改進灰狼優化算法對簇頭進行尋優，在后續迭代過程中對權重進行動態更新，使得簇頭選擇更加合理有效，在均衡網絡能效方面更加高效。 對改進協議的鏈路、存活節點數量以及網絡剩余能量這三項指標進行實驗對比，結果顯示均優于其他三種協議。 改進PEGASIS 協議在簇內節點建鏈階段，只是通過小范圍建鏈的方式宏觀減少長鏈的生成，并沒有對此過程進行很好的優化，在今后的工作中將在此方面開展深入研究。