基于磷蝦群算法的無線傳感器網絡QoS任播路由算法*

徐 昕，顧云麗，張嫣娟

（1.南京信息工程大學江蘇省網絡監控中心，南京210044；2.南京信息工程大學計算機與軟件學院，南京210044）

基于磷蝦群算法的無線傳感器網絡QoS任播路由算法*

徐 昕1，2*，顧云麗1，2，張嫣娟2

（1.南京信息工程大學江蘇省網絡監控中心，南京210044；2.南京信息工程大學計算機與軟件學院，南京210044）

無線傳感器網絡多約束QoS任播路由問題是一個NP難題，提出一種基于磷蝦群算法的優化策略來解決該路由問題。該算法采用適應度函數和全局最優個體位置更新方法來尋找無線傳感器網絡中滿足多QoS約束的最優任播路由，并加入遺傳繁殖機制中的交叉與變異操作以加快優化速度。實驗驗證了該算法的有效性，實驗數據表明相比較粒子群優化算法，該算法在算法效率和可擴展性性能上具有較好的性能；具有較快的收斂速度，從而適用于對路由選擇有時延敏感的網絡。

無線傳感器網絡；路由算法；磷蝦群算法；任播

磷蝦群算法KH（Krill Herd Optimization）是近年來由Gandomi［1］提出的一種新型的元啟發式群體智能優化算法。該算法的主要思想是模仿磷蝦個體在食物位置和磷蝦群密度等因素影響下的移動過程，因此具有在連續空間的非線性優化性能。

磷蝦群算法提出后，收到一些學者的極大關注并應用于各個科研領域。Deng［2］采用磷蝦群算法優化移動服務共享組合問題；針對損耗和饋線超載等問題，Rostami［3］通過磷蝦群算法優化電動汽車充電負荷；Younesi［4］采用磷蝦群算法優化永磁同步電機的轉速和轉矩控制器參數，以盡量減少穩定狀態下速度跟蹤誤差；Sultana［5］研究關于磷蝦群算法在配電網電容器中的優化應用。在應用中，有學者還對磷蝦群算法進行了改進。如Mukherjee［6］提出一種混沌磷蝦群算法，并用來最優化處理無功優化調度電力系統問題；王磊［7］構造一種啟發式二次對立搜索算子以提高磷蝦群算法的全局探索能力；Fattahi［8］提出一種模糊磷蝦群算法，該算法可以動態地調節每一輪探索過程中磷蝦的探索范圍；Bulatovic［9］對磷蝦群算法中交叉因子進行改進從而加快尋優速度，并將其應用在四連桿結構優化設計問題中。

由于磷蝦群算法比較新穎，以往的研究主要集中在工程優化領域中。本文嘗試將磷蝦群算法應用到無線傳感器網絡WSN（Wireless Sensor Networks）多約束QoS任播路由領域中。

WSN節點能量受限于有限電源（電池），節點傳輸能力較弱，監控范圍較大。因此，為了節能和能耗均衡等目的，在WSN中往往部署多個基站（Sink），節點可以根據路由狀況將監測信息任播（Anycast）至任一基站處。WSN往往對路由能耗、傳輸時延等有服務質量QoS（Quality of Service）約束，這種多約束路由問題是一個NP難題［10］。以往有學者采用遺傳算法、蟻群算法、粒子群算法等智能算法解決多約束QoS網絡路由問題［11-13］，本文嘗試采用磷蝦群算法來解決多約束QoS路由問題。

1 問題描述

WSN拓撲結構抽象表示為連通圖G（V，E）。其中，V為所有傳感器節點的集合，共N個節點，E為節點間有向通信鏈路的集合。本文標記：A為某任播地址；G（A）為共享A的通信組成員集合（即Sink節點集合）；Ai為G（A）中第i個組員；M為G（A）組員數目。為保證監測數據分組能安全迅速到達任一Sink，本文規定發送節點s需同時向k個Sink進行傳輸，因此需尋找k條任播路徑。

與傳統網絡的QoS需求略有不同，WSN由于節點受能量限制，其路由的重要指標之一是節省能耗。而且，WSN路由還要盡量保證能耗均衡，這是由于一旦有節點快速耗盡能量，該節點區域將無節點負責監測和轉發分組，從而導致網絡分割；由于WSN節點傳輸能力較弱，要求能在低能耗以及不穩定的網絡情況下仍能提供安全可靠的數據傳輸。除此以外，WSN往往用于軍事、環境監控，因此還要求數據具有時效性，對網絡傳輸延遲有著嚴格的要求，超時傳送到Sink節點的數據將毫無意義，甚至成為擾亂信息影響整個系統監測。

本文WSN路由QoS衡量體系設定為：節點能耗E，路徑剩余能量比C，端對端時延D，分組丟失率L和路徑延遲抖動J。討論如下：

①節點能耗

傳輸監測數據分組至Sink處導致路徑上各節點能耗E計算如下：

式中，E[p(s,Ai)]是路徑p(s,Ai)上各節點能耗之和。而

式中，Es是節點t傳輸監測分組的能耗，Er是節點t接收監測分組的能耗。在此不討論節點串聽和空閑等待能耗（即便沒有監聽數據分組傳輸任務，這部分能耗仍然需要消耗）。發送和接收k比特數據的能耗計算如下：

其中，n為衰減指數，本文設定為2；d為發送節點與接收節點之間的距離；節點發送分組時，需要放大訊號發送，其能耗參數記為Eamp；發送或接收分組時在電路運作方面有一定的能耗，記為Eelec。

②路徑剩余能量比

在WSN中，有些節點會出現能耗過快的現象，從而使得網絡生存期較短（網絡生存期定義為到第一個節點失效的時間）。為避免或減輕該現象，本文采用路徑剩余能量比指標C來盡量減少對能量較低的節點的使用。

其中，E(t)是節點t當前剩余能量，Einit(t)是節點t的初始能量。本文設置能量比低于閾值C′的節點只參與到自己主動發起的監測數據匯報至Sink的傳輸任務，但不再參與到其他節點發起的分組轉發任務中。

③端對端時延

傳輸監測數據分組到達Sink的端對端時延D計算如下：

式中，D[p(s,Ai)]是分組在路徑p(s,Ai)上各節點的時延。而

式中，Ds(t)是監測分組在節點t的傳輸時延；Dq(t)是監測分組在節點t的排隊等待時延。

④分組丟失率

在WSN中，往往由于無線鏈路質量問題導致數據傳輸失敗。除此以外還存在隱終端問題（hidden terminal problems）的傳遞碰撞導致分組傳遞失敗。

傳輸監測數據分組到達Sink的分組丟失率計算如下：

式中，L[p(s,Ai)]是路徑p(s,Ai)上分組丟失率。

式中，L(t)是在節點t的分組丟失率。

⑤延遲抖動

傳輸監測分組至Sink處延遲抖動J計算如下：

式中，路徑p(s,Ai)的延遲抖動J[p(s,Ai)]計算如下：

其中，J（l）是鏈路l的延遲抖動。

將WSN多約束QoS任播路由問題轉化為一個最優化數學問題。優化目標是在滿足以約束條件下尋找到能耗最小的優化目標。

將上述多約束優化問題轉化為如下無約束優化問題：

其中，

式中，C′，D′，L′和J′分別是路徑剩余能量比、端對端時延、分組丟失率和延遲抖動的QoS約束值；ω0，ω1，ω2，ω3，ω4是歸一化系數，取值范圍在[0,1]。

由于f0，…，f4等值計量單位不一致，數值之間差距較大，為方便給出各自的權值系數，采用最小-最大規范化方法將各自的實驗值映射到[0,1]區間，如f0被映射到f0'的計算過程如下：

由此，優化問題轉為

Minimize：

2 磷蝦群算法優化

磷蝦群算法是近年來根據磷蝦個體的群集行為提出的一種啟發式算法。在磷蝦群整體遷移過程中，每個個體磷蝦都在一定范圍內受到相鄰磷蝦的吸引或排斥。以磷蝦個體的位置為設計變量，給定適應度函數，磷蝦群算法從而可以在多維搜索空間尋找食物（優化值）。

根據磷蝦的位置移動變化情況，其算法的主要步驟如下：

①趨光性群集運動

在種群中，每只磷蝦的移動使得整個磷蝦群的位置時時刻刻都在發生變化。磷蝦i的移動方向將受到其鄰近磷蝦、最優個體以及種群排斥效應的影響。磷蝦i的移動向量計算如下：

式中，Vmax是磷蝦群體最大引導速度；表示磷蝦i的上一次位置變化；ωn是權值，取值在［0，1］之間。為鄰近磷蝦個體對磷蝦i的誘導方向向量；為群體最優個體對磷蝦i的誘導方向向量，其計算分別如下：

其中，Ni是鄰近磷蝦個體的數量；fi，fj，fworst和fbest分別是磷蝦i，磷蝦j，當前最差和最好的目標函數值；Xi和Xj分別是磷蝦i和磷蝦j的位置；ξ是取值在［0，1］之間的隨機值；I和Imax分別是算法當前和最大迭代次數。

②覓食行為

磷蝦i的覓食行為描述如下：

式中，Fi為磷蝦i覓食導致的位置變化；ωx為權值；Vf為覓食速度；βi為磷蝦i覓食方向向量。

③隨機游動行為

磷蝦i的隨機游動行為描述如下：

式中，Dmax為磷蝦個體最大擴散速度；δ為隨機方向向量。

④位置更新

式中，Zi為磷蝦i的位置矢量，Δt為時間間隔。

算法中，對網絡中所有節點編碼，將從源節點到任播組組員的一條路徑序列編碼設為一個可行解。設任播組員數目為M，源節點至組員Ai共有j條可行路徑，其中第k條路徑（解）表示為Pik，該解是一個數字序列。因此，至組員Ai的解為向量Pi=(Pi1,Pi1,…,Pij)。由此可知，算法解集空間是一個M維的向量空間P1,P2,…,PM。如圖1中，路徑P11=S-n1-n2-n3-n4-n5-A1可以編碼表示為0-1-2-3-4-5-11，P12=S-n6-n7-n3-n4-n5-A1可以編碼表示為0-6-7-3-4-5-11，向量P1=(P11,P12)，算法解集空間為(P1,P2)。

初始磷蝦群（初始解）可通過圖的深度優先搜索算法隨機產生，即將隨機找到的Np條從源節點到任播組員的路徑（解）作為磷蝦群的初始位置。

圖1 交叉和變異示意圖

為加快優化速度提高優化能力，磷蝦群算法還將遺傳繁殖機制應用到優化過程中，主要包括交叉和變異兩個操作。

①交叉操作

磷蝦個體以一定概率同挑選出的優秀個體進行交叉操作，操作如下：

式中，crossover（）表示交叉操作；Xgood是挑選出的優秀個體。

②變異操作

磷蝦個體以一定概率基因變異，操作如下：

以圖1為示意圖舉例說明交叉和變異操作。設已尋找到任播路徑P11=S-n1-n2-n3-n4-n5-A1，P21=S-n6-n7-n3-n8-n9-A2，如圖中黑線所示，通過交叉可以生成任播路徑P22=S-n1-n2-n3-n8-n9-A2，P12=S-n6-n7-n3-n4-n5-A1，如圖中紅虛線所示。任播路徑P21通過變異操作可以生成任播路徑P23=S-n6-n7-n10-n8-n9-A2。

算法具體流程如下：

輸入：網絡結構圖G=（V，E）；k值；最大擴散速度Dmax，時間間隔Dt，最大迭代次數Imax；權值ω0,…ω4,ωn和ωx；發送和接k比特數據的能耗分別為ES和Er；種群規模NP。

Step 1 通過圖的深度優先搜索算法隨機產生的Np條路徑，編碼生成解集空間；

Step 2 計算每個磷蝦的適應度，確定當前最優個體；

Step 3 根據磷蝦趨光性群集運動、覓食運動和隨機游動等行為（式（25）～式（29）），計算磷蝦個體位置變化；

Step 4 更新磷蝦群個體位置（式（30）），計算新的適應度值；

Step 5 分別按照概率α和β，執行交叉和變異操作，評估新產生磷蝦個體的適應度值；

Step 6 IfI＜ImaxI=I+1；goto Step 2.

Else 算法結束.

輸出：最優磷蝦個體對應的路徑（最優解）

4 實驗設計與分析

以粒子群算法作為對照算法來驗證本文所提算法的有效性及其效率。

4.1 對照算法介紹及算法性能比較分析

粒子群優化算法PSO（Particle Swarm Optimization）將每個個體看作是N維搜索空間中的一個沒有體積的微粒，該粒子的位置對應于優化問題在搜索空間的一個可行解。粒子在搜索空間中以一定的速度飛行，這個速度根據該粒子本身的飛行經驗和同伴的飛行經驗來動態調整。其第i個微粒表示為Xi=(xi1,xi2,…xiN)，其經歷過的最好位置記為pbest，群體中所有粒子經歷過的最好位置為gbest。

粒子群算法的主要思想是：在每一輪迭代中，（a）粒子根據加速因子更新自己的速度和位置；（b）對每個粒子，將它的適應值和它經歷過的最好位置pbest作比較，如果前者較好，則將其作為當前的最好位置pbest；（c）對每個粒子，將它的適應值和全局所經歷最好位置gbest的作比較，如果前者較好，則重新設置gbest的索引號。

由此可知，粒子群算法主要是通過不斷更新粒子的位置來尋優，這與磷蝦群算法在優化過程中有很大的相似之處（兩者在移動過程中，都以當前個體最優位置和全局最優位置作為其中一個參考對象）。

但粒子群算法對粒子移動的算法設計比較簡單，而磷蝦群算法的移動規則更加復雜且符合真實世界中磷蝦實際移動規律［1］；粒子群算法缺乏磷蝦群算法中覓食行為和隨機游動等操作；相比較磷蝦群算法，傳統粒子群算法沒有交叉和變異操作，算法比較簡單，因此在搜索解空間時，有時會出現粒子在全局最優解附近振蕩的現象，從而有時無法找到全局最優解。文獻［1］等其他文獻給出數十個算例證明磷蝦群算法優化效果優于傳統粒子群算法。

將粒子群算法應用到多約束QoS路由問題已有較多的研究成果［11-12］，本文仿真實驗比較磷蝦群算法在多約束QoS路由問題中的算法性能。

4.2 仿真實驗和分析

以圖1所示的網絡拓撲結構進行仿真實驗來評價本文算法有效性。

圖1中五元組(E,C,D,L,J)分別表示該節點的接收和傳輸能耗，剩余能量比，接收和傳輸時延，分組丟失率L和延遲抖動。QoS約束(C′,D′,L′,J′)設置為（3，35，0.4，20）。ω0，ω1，ω2，ω3，ω4設為0.2，初始磷蝦群為路徑P11，P21和P21。很顯然，初始路徑都無法滿足給定QoS要求。

源節點至任播組員路徑的(E,C,D,L,J)值和f[p(s,A)]值如表1所示。

表1 各路徑的(E,C,D,L,J)值和f[p(s,A)]值

由表1可知，路徑P22的適應度函數值最佳。以初始路徑P11，P21和P21為初始磷蝦種群，通過磷蝦群算法的交叉、變異和移動等操作，不斷尋找更佳f[p(s,A)]值，30輪迭代優化后，找到最優解P22=S-n1-n2-n3-n8-n9-A2。該路徑具有最佳適應度函數值且滿足給定QoS要求。

模擬一個具有N個（N=100）節點的網絡，均勻分布在100 m×100 m的矩形區域內；節點傳輸半徑r=30 m；指定Sink（基站、任播組員），設置任播組員（Sink）數目M=6；設定任播時需向k個Sink匯報（k=2）；Eamp=100 pJ/（bit/m2），Eelec=50 nJ/bit；傳感器節點以參數λ=0.05的泊松分布匯報監測事件至任意k個Sink，監測數據分組大小為1 kbyte；QoS約束(C′,D′,L′,J′)設置為（10，20，0.3，30）。以基于傳統粒子群算法優化的多約束QoS路由算法作為對照算法，來評價本文算法的優化效率。

尋找滿足QoS約束條件的k條任播路徑，觀察適應度函數f[p(s,A)]的收斂情況。實驗結果如圖2所示。

圖2 適應度函數f[p(s,A)]與迭代次數

從圖2中可知，在約第60次迭代后，適應度函數f[p(s,A)]的平均值在連續迭代過程中幾乎沒有變化，表明算法已經收斂到最優路徑。從實驗結果看，相比較粒子群算法，本文算法適應度函數f[p(s,A)]值略微占優。這是由于相比較傳統粒子群算法，磷蝦群算法中磷蝦移動規則更加貼近實際磷蝦移動規律，磷蝦除群集運動以外，還有覓食行為和隨機游動行為，因此算法更加復雜。除此以外，磷蝦群算法還增加遺傳繁殖機制的交叉和變異操作，算法尋優能力較強，不易陷入局部最優。而且算法具有較快的收斂速度，從而在對路由選擇有時延敏感的網絡中具有更好的表現。

由于WSN往往規模很大，因此其路由算法應該具有較好的可擴展性。本文不斷調節網絡節點數目N（40-100），網絡矩形區域也相應調整。觀察不同網絡規模下適應度函數的值，結果如圖3所示。

由圖3可知，隨著網絡規模增大，兩者算法的適應度函數f(p(s,A))的值也隨之增長，增長曲線比較平穩。與粒子群算法相比，本文算法在不同網絡規模下都有較好的優化值。這是由于相比較傳統粒子群算法，磷蝦群算法在復雜問題下仍具有較好的全局尋優能力［1］，而傳統粒子群算法則較容易在陷入局部最優，從而影響其優化表現。

圖3 適應度函數f[p(s,A)]與節點數

以適應度函數f[p(s,A)]值在連續迭代中方差小于0.001為終止條件，本文繼續觀察不同網絡規模下所需優化時間，結果如圖4所示。

圖4 優化時間與節點數

由圖4可知，隨著網絡規模增大，兩者算法的優化時間也隨之增長。與傳統粒子群算法相比，磷蝦群算法在復雜問題環境下，仍具有較強的算法尋優能力和收斂速度［1］。因此，在不同網絡規模下，相比較粒子群算法，磷蝦群算法優化時間較占優。

5 結語

針對磷蝦群算法具有非線性優化的特點，提出一種基于磷蝦群算法優化的WSN多約束QoS任播路由算法。該算法采用適應度函數來尋找WSN中滿足QoS約束的最優任播路由，并加入遺傳繁殖機制中的交叉與變異操作以加快優化速度。實驗數據表明，相比較基于傳統粒子群算法的多約束QoS路由算法，本文算法在算法效率和可擴展性上占優。而且本文算法具有較快的收斂速度，從而在對路由選擇有時延敏感的網絡中具有較好的表現，但有時也有必要對其進行改進以避免早熟收斂。

［1］Gandomi A H，Alavi A H.Krill Herd：A New Bio-Inspired Optimization Algorithm［J］.Communications in Nonlinear Science and Numerical Simulation，2012，17（12）：4831-4845.

［2］Deng S，Huang L，Taheri J，et al.Mobility-Aware Service Composition in Mobile Communities［J］.IEEE Transactions on Systems，Man，and Cybernetics：Systems，2016，PP（99）：1-14.

［3］Rostami M A，Kavousi-Fard A，Niknam T.Expected Cost Minimization of Smart Grids With Plug-In Hybrid Electric Vehicles Using Optimal Distribution Feeder Reconfiguration［J］.IEEE Transactions on Industrial Informatics，2015，11（2）：388-397.

［4］Sultana S，Roy P K.Oppositional Krill Herd Algorithm for Optimal Location of Capacitor with Reconfiguration in Radial Distribution System［J］.International Journal of Electrical Power and Energy Systems，2016，74（2016）：78-90.

［5］Mukherjee A，Mukherjee V.Solution of Optimal Reactive Power Dispatch by chaotic Krill Herd Algorithm［J］.IET Generation，Transmission&Distribution，2015，9（15）：2351-2362.

［6］王磊，張漢鵬，張東寧.基于對立搜索和混沌變異的磷蝦覓食優化算法［J］.控制與決策，2015，30（9）：1617-1622.

［7］Fattahi E，Bidar M，Kanan H R.Fuzzy Krill Herd（FKH）：An Improved Optimization Algorithm［J］.Intelligent Data Analysis，2016，20（1）：153-165.

［8］Bulatovic R R，Miodragovic G，Boskovic M S.Modified Krill Herd（MKH）Algorithm and Its Application in Dimensional Synthesis of a Four-Bar Linkage［J］.Mechanism and Machine Theory，2016，95（2016）：1-21.

［9］EkbataniFard G H，Monsefi R，Akbarzadeh-T M R.A Multi-Objective Genetic Algorithm Based Approach for Energy Efficient QoS-Routing in Two-Tiered Wireless Sensor Networks［C］//Proc of the 5th IEEE International Symposium on Wireless Pervasive Computing，2010：80-85.

［10］Cheng L，Niu J，Cao J，et al.QoS Aware Geographic Opportunistic Routing in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2013，25（7）：1864-1875.

［11］Sun J，Fang W，Wu X，et al.QoS Multicast Routing Using a Quantum-Behaved Particle Swarm Optimization Algorithm［J］.Engineering Application of Artificial Intelligence，2011，24（1）：123-131.

［12］解志斌，于謙，沈斌，等.一種新的基于粒子群優化的雙簇頭分簇路由算法［J］.傳感技術學報，2013，26（8）：1135-1139.

［13］王鎮，劉學軍.WSN中基于蟻群算法的QoS路由協議［J］.傳感技術學報，2011，24（11）：1625-1631.

徐 昕（1975-），男，江蘇省南京市人，博士，南京信息工程大學計算機與軟件學院副教授，主要研究方向為無線傳感器網絡路由技術，xuxin@nuist.edu.cn；

顧云麗（1978-），女，江蘇省連云港人，博士，南京信息工程大學計算機與軟件學院講師，主要研究方向為無線傳感器網絡路由技術，guyunli@nuist.edu.cn。

A QoS Anycast Routing Algorithm for Wireless Sensor Networks Based on Krill Herd Optimization*

XU Xin1，2*，GU Yunli1，2，ZHANG Yanjuan2
（1.Jiangsu Engineering Center of Network Monitoring，Nanjing University of Information Science and Technology，Nanjing210044，China；2.College of Computer and Software，Nanjing University of Information Science and Technology，Nanjing210044，China）

Since the multiple constrained QoS anycast routing algorithm for wireless sensor networks（WSN）is a NP-complete problem，a routing algorithm based on krill herd optimization is proposed for this problem.By using the fitness function and updating the global best position in WSN，the proposed algorithm finds the optimal anycast routes which meet QoS constraints.Moreover，crossover and mutation operators in genetic reproduction mechanisms are adopted for accelerating optimization speed.Experimental results show that the algorithm is effective.In comparison with the optimization scheme based on particle swarm optimization，simulation experiments results show that the performances of efficiency and scalability of the proposed algorithm is better；the proposed algorithm has a faster convergence speed，thus it is especially applicable to the network which is delay-sensitive to route selection.

wireless sensor networks；routing algorithm；krill herd optimization；anycast

TP393

A

1004-1699（2016）12-1893-06

??6150P

10.3969/j.issn.1004-1699.2016.12.019

項目來源：南京信息工程大學大學生科技創新項目（201610300212）

2016-04-20修改日期：2016-07-28