基于蟻群系統的WSN 能量均衡多路徑路由協議

肖 鋮，孫子文

（江南大學 物聯網工程學院，江蘇 無錫214122）

0 引 言

隨著無線傳感器網絡 （wireless sensor networks，WSN）的規模逐步增大，頻繁的網絡通信極易造成通信路徑擁堵、節點能量耗盡等問題。而合理有效的路由協議是解決這些問題的關鍵因素。因此，設計一種能量均衡、網絡擁塞程度低的路由協議成為無線傳感器網絡研究的目標之一［1］。

蟻群算法是一種仿生啟發式群智算法，因其具有分布式、自組織、正反饋等系統特性，常用在解決無線傳感器網絡路由等組合優化問題上。作為蟻群算法的一個重要分支，蟻群系統 （ant colony system，ACS）是對AS （ant system）算法改進的蟻群算法，在避免局部最優解、加快收斂速度等方面性能有一定提升，算法過程包括偽隨機狀態轉移規則、局部信息素更新和全局信息素更新3 個階段［2］。文獻 ［3，4］分別將ACS 算法、AS 蟻群算法與博弈論方法和模糊推理方法相結合，以提高路由路徑的質量，降低網絡能耗。然而，博弈論、模糊推理等方法的引入，加大了節點的計算處理時間，易帶來網絡擁塞等問題。基于蟻群優化和能量路由的思想，文獻 ［5－8］提出關于WSN 的蟻群算法能量路由協議。其中文獻 ［5，6］在典型路由協議EEABR （energy efficient ant－based routing）上進行了改進，EEABR 協議是一種針對WSN 的約束特點的主動式能量有效蟻群路由算法，通過人工螞蟻搜索能量高效且最短的路徑來最大地延長網絡生命期［9］。然而，作為單路徑路由方式，其難以有效地解決能量均衡和網絡擁塞等問題。文獻 ［10］中提到的AOMDV 協議是為減少路由發現頻次并降低因路徑故障而引起的丟包率的多路徑路由協議，但這類路由協議缺少對節點能量約束方面的考慮且一直選擇相同的路徑進行數據轉發，易導致路徑中的部分節點能量過早耗盡，影響網絡生命期，因此，不太適用于WSN 環境。文獻 ［11］提出一種適于WSN 的多路徑路由協議MACS （multipath routing based on ant colony system），MACS協議是基于ACS蟻群算法的多路徑路由，但多路徑的建立沒有考慮路徑的能量狀態，對網絡的能量效率提高不明顯，同時也存在未能充分利用多路徑進行數據發送的問題。

在這些研究基礎上，為有效解決無線傳感器網絡能量均衡和網絡擁塞問題，采用ACS蟻群算法，本文提出一種多路徑路由協議 （ACS based wireless sensor networks multi－path routing protocol，ACSBMR）。一方面，該協議在ACS蟻群算法基礎上對信息素更新方式和啟發式策略進行改進，并構建路徑綜合評價函數，對路由路徑進行擇優篩選；另一方面，多路徑建立可有效解決單路徑路由在節點能耗分布不均、負載不均衡等方面的不足，有利于延長網絡生命期［12］。通過NS2 仿真平臺驗證了該協議的可行性，仿真結果表明，其滿足一定的路由性能指標，并達到了設計的目的。

1 網絡模型

以中小規模靜態無線傳感器網絡為研究對象，將其建模為具有加權系數的雙向連通圖G＝ （V，E），其中，V＝｛vi｜i＝1，2，…，n｝表示n 個節點的集合，E＝ ｛（vi，vj）｜1≤i≤n，1≤j≤n，i≠j｝表示任意相鄰節點i、j之間的節點鏈路集合，源節點到目的節點的路由路徑是由多個有序的帶加權因子的節點鏈路組成。設網絡中有一源節點v1和目的節點vn，v1到vn的所有路由路徑的集合用P表示，其第k條路由路徑記為Pk（Pk∈P），則Pk是由集合E中的部分元素按一定先后次序排列組成。無線傳感器網絡的網絡層次結構自下而上可以分為物理層、數據鏈路層、網絡層、傳輸層、應用層這橫向五層，各層次協議間存在縱向管理機制，路由協議位于網絡層，網絡層的工作機制通常需要其它底層技術的支持［13］。

一個無線傳感器網絡的物理層和網絡層之間的跨層設計模型如圖1所示，通過這個模型可以獲取節點之間的距離信息和節點隊列長度。圖中節點的隊列長度Queue＿len從MAC層獲得，而由物理層的信號接收功率Pr與節點間的距離d 成反比關系的原理，利用雙徑無線傳播模型 （two ray ground）計算出d，如式 （1）所示

式中：Pt和Pr——信號發送、接收功率；Gt和Gr——發送、接收端天線增益；ht和hr——發送、接收端天線高度；L——系統損耗 （默認值1）。

圖1 跨層設計模型

2 ACSBMR路由算法

2.1 路由發現

2.1.1 報文信息表示

ACSBMR 算法中用到的螞蟻包有兩種：前向螞蟻Fant和后向螞蟻Bant，其報文格式分別如圖2、圖3所示，報文各個參數及涵義見表1。

圖2 Fant報文格式

圖3 Bant報文格式

表1 Fant和Bant報文參數

表1中，TTL值的設置是為了防止前向螞蟻在網絡中無限地循環下去而浪費網絡資源，前向螞蟻每經過一個節點，TTL值就減1；當其值減為0時，節點就把此前向螞蟻包丟棄，不再對其進行轉發。

在傳感器網絡進行無線通信時，為了獲知與維護鄰居節點間的連通關系，每個節點需要周期性地發送Hello包來更新鄰居節點，同時將相應的鄰居節點信息保存在各自的鄰居表Table中。Hello包的報文格式和Table結構分別如圖4、圖5所示，二者的各個參數及涵義見表2。

圖4 Hello包報文格式

圖5 Table結構

表2 Hello包報文和Table結構參數

表2中，Hello包的發送周期可以根據網絡場景的穩定性進行設置，對于節點不移動的靜態網絡場景，各個節點的鄰居關系相對穩定，其Hello包的發送周期可以大一點。本文設定Hello包的發送周期為5s，若超過10s沒有收到某鄰居節點發送的Hello包，則代表這個鄰居已經死亡，應將這個鄰居節點從鄰居表Table中刪除。

2.1.2 偽隨機狀態轉移規則

源節點產生m 個前向螞蟻，這些螞蟻根據偽隨機規則進行下一跳節點的選擇直至到達目的節點。設第k 個前向螞蟻當前所在節點為i，下一跳鄰居節點為j，則節點j的選擇規則如式 （2）所示

其中

式中：q是均勻分布在 ［0，1］區間的一個隨機數，前向螞蟻每次選擇下一跳節點時都由算法隨機產生，q0（0≤q0≤1）為常數；pij是選擇節點j 作為下一跳的概率；Nki表示節點i的鄰居節點集合；τir和ηir分別表示節點鏈路 （i，r）上信息素值和啟發式函數值；α、β分別表示信息素值和啟發式函數權重因子；Tuba表示禁忌表。在前向螞蟻k 選擇下一跳節點之后，當前節點i也加入到Tuba中。

啟發式函數的引入可以提高算法的收斂速度，啟發式函數ηij的定義如式 （4）所示

式中：dij和lj——相鄰節點i、j之間的通信距離和下一跳鄰居節點j 的隊列長度，可通過調用網絡跨層設計模型中的相關信息獲得；D 和L——節點屬性中的最大通信半徑和最大隊列長度；λ （0≤λ≤1）為可調參數，作為dij和lj的比例因子。這里啟發式函數作為概率選擇的輔助，同時權衡節點距離和隊列長度，通信距離和隊列長度越小的鄰居節點作為下一跳節點可能性越大。

2.1.3 局部信息素更新

在前向螞蟻搜索路由路徑過程中，為擴大路徑搜索空間，使后面的前向螞蟻能夠探索更多的較優路徑，可以通過對節點鏈路進行局部信息素更新的方式來取得一定效果。當前向螞蟻從節點i轉移到下一跳節點j 時，對節點鏈路（i，j）上的信息素τij重新計算。信息素更新規則如式 （5）所示

式中：Ω＝τ0／dij，τ0為相鄰節點鏈路初始信息素，dij為節點i、j之間的通信距離；ξ （0≤ξ≤1）為局部信息素揮發系數。

為了提高路由發現過程的效率，需要對前向螞蟻的延遲做一定約束處理。設第一個到達目的節點的前向螞蟻的端到端時延記為Ts－d（Ts－d可以從前向螞蟻包的報文格式中的起始時間得到）［14］。針對前向螞蟻的延遲問題，在目的節點設置一個等待時間Td如式 （6）所示

式中：系數Cd可根據網絡實際環境進行適當調整。對于第一個以及在Td內到達目的節點的前向螞蟻都轉化為相應的后向螞蟻，其它前向螞蟻則丟棄不作處理。

2.1.4 全局信息素更新

目的節點接收到前向螞蟻后，將搜索得到的路由信息進行一定處理后轉化為相應的后向螞蟻。后向螞蟻沿前向螞蟻的反向路徑返回至源節點，并對經過的節點鏈路進行一次全局信息素更新，更新規則如式 （7）所示

式中：ρ （0≤ρ≤1）是全局信息素揮發因子。Δτij為第k 條路徑上信息素增量，其表達式如式 （8）所示

式中：σ——信息素增強系數；E0——節點的初始能量；Ei——節點i的當前能量值；Pk——后向螞蟻返回至源節點對應的第k 條路徑；N——路徑Pk上的節點數；Emin和Eavg——路徑上的節點中的最小剩余能量和平均剩余能量。因此，Δτij綜合衡量了路徑上節點的能量瓶頸情況和能量均衡度，其值越大，說明路徑上節點能量均衡越好，而且所有節點的能量值也相對較高。

2.2 多路徑評價及數據發送

經過算法的路由發現過程，在源節點已形成n（n≤m）條可達目的節點的路由路徑。根據后向螞蟻中存儲的路由跳數信息和信息素信息，源節點對獲得的路由路徑按照路徑綜合評價函數Fitness（k）以衡量路徑質量水平，路徑綜合評價函數計算公式為式 （9）

式中：h（k）——第k條路徑的路由跳數，k＝1，2，…，n。通過計算路徑綜合評價函數值，源節點可通過建立多條路由路徑，以概率選擇的方式進行數據流發送。

第k條路徑發送數據包的概率R（k）表達式如式 （10）所示

式中：n代表所有路由路徑的數量。綜合評價函數Fitness（k）值越大，被選擇為發送路徑的概率就越大，即質量越好的路徑被選作發送數據的可能性越大，相應承擔的數據負載越多，這種方式在一定程度上有助于網絡能量資源消耗的均衡。隨著節點的啟發因子和節點鏈路上信息素濃度的不斷變化，Fitness（k）和R（k）的值也被不斷更新，數據流也隨之往質量較好的路徑上發送。

2.3 算法步驟

由于螞蟻數和算法的迭代次數需要視網絡環境而定，不適宜取固定值［15］，在本文路由算法中，源節點產生的螞蟻數m 和算法的迭代次數Nmax由網絡規模大小決定，其中m＝NNantss，Nmax＝NNiters；Ns表示網絡中節點的個數，Nants∈ ［0，1］和Niter∈ ［0，1］。算法的主要步驟歸納如下：

步驟1 初始化迭代次數Nmax和相鄰節點鏈路的起始信息素值τ0，并令當前迭代次數Nc＝0。

步驟2 在源節點處構造m 只前向螞蟻，每只螞蟻標記為k，k＝1，2，…，m。

步驟3 前向螞蟻k 根據偽隨機狀態轉移規則式 （2）選擇下一跳鄰居節點j。

步驟4 前向螞蟻k 根據局部信息素更新規則式 （5）對所選的節點鏈路上的信息素進行更新，并不斷重復直至目的節點。

步驟5 對于在Td時間內到達目的節點的前向螞蟻，將其轉化為后向螞蟻并根據全局信息素更新規則式（7）對反向路徑上的節點鏈路進行信息素更新，直至返回至源節點。

步驟6 如果算法滿足結束條件Nc＞Nmax，則跳到步驟7；否則Nc＝Nc＋1，并返回至步驟2。

步驟7 當所有后向螞蟻到達源節點后，根據式 （9）確定多條路由路徑。

步驟8 由最終確定的多條路由路徑，根據式 （10）以概率選擇方式進行數據發送。

3 仿真與分析

仿真采用WindowsXP＋Cygwin2.738＋ns2.35 平臺，通過多組不同仿真實驗結果取平均值來對本文路由算法進行評估與分析，并與AOMDV、EEABR 路由協議進行比較分析。

3.1 仿真場景與參數設置

所有仿真場景均在1000 m×1000 m 的平面區域內進行，為比較各路由協議在不同的節點密度下的性能，每個場景分別部署50／100／200／300／400個節點，數據流最大連接數依次為10／15／25／35／45，并在節點中隨機選取源節點和目的節點。每個場景的仿真時間為300s，節點通信范圍設置為100m，數據流采用cbr模型，由數據流生成工具cbrgen產生，數據分組大小為512Byte，數據流速率為4 packets／s，無線傳播方式為Propagation／TwoRayGround，能量模型為EnergyModel，節點發送一個包所需要的功耗txPower＝0.660 w，節點接收一個包所需要的功耗rxPower＝0.395w，MAC類型為Mac／802＿11，節點的最大隊列長度為50，節點的初始能量為20J。路由算法的具體參數設置見表3。

表3 ACSBMR算法參數

3.2 仿真結果及性能分析

考慮到本文路由算法以均衡網絡能量和減小網絡擁塞度為目標，仿真主要從能量效率、節點剩余能量標準差、端到端平均時延、網絡生命期這幾個方面對3種路由協議進行性能分析與比較。

能量效率定義為仿真過程中網絡平均每消耗1焦耳的能量，目的節點接收到的數據包大小 （Kbits）。從圖6中可以看出，隨著網絡節點數目的增加，網絡的負載能力更強，各個協議的能量效率都有一定的提高，但ACSBMR 協議比其它兩種協議的能量效率均要高25%左右。ACSBMR 協議對建立的多條路徑以概率選擇的方式進行路由，提高了對多路由路徑的利用效率，減少了因多次路由控制而引發的能量上的消耗，所以其能量效率相對較高。

圖6 能量效率

節點剩余能量標準差衡量的是仿真結束時所有節點剩余能量的分散程度，其值越大，說明路由協議的能量均衡性越差。從圖7 可以看出，在各個仿真場景結束時，ACSBMR 協議的節點剩余能量標準差比其它兩種協議都要小很多，且當節點數少于200個時，其剩余能量標準差變化相對平穩，說明ACSBMR 協議的能量均衡性相對較好。與AOMDV 協議不同的是ACSBMR 協議主要以單播路由方式進行節點間通信，減少了能量消耗，且在路徑選擇時考慮節點能量的均衡性，故ACSBMR 協議在節點剩余能量標準差方面的性能要好很多。而EEABR 協議是單路徑路由方式，在能量效率上主要考慮單條路徑的能量消耗情況，不利于能量的均衡。

圖7 節點剩余能量標準差

端到端平均時延是在數據包傳輸過程中從源節點到目的節點的平均時間差值。從圖8可以看出，隨著節點數目的增加，端到端平均時延隨之增加，其中AOMDV 和EEABR 協議明顯高于ACSBMR 協議，且在網絡節點數目不斷增加下，ACSBMR 協議仍能保持較小的時延增長率。這是由于ACSBMR 協議采用多路徑路由方式，各路徑根據路徑綜合評價函數以概率分配方式發送數據包，有利于減少網絡擁塞的發生，同時在啟發式函數中考慮節點隊列長度，優先選擇網絡接口隊列長度小的節點作為下一跳節點，避開了相對擁塞的節點。

圖8 端到端平均時延

網絡生命期定義為從仿真開始到第一個節點死亡 （即能量耗盡）的時間段。圖9的仿真結果顯示，隨節點數目的增加，各路由協議得到的網絡生命期變化不大，但ACSBMR 協議中第一個節點死亡時間要晚于AOMDV 和EEABR 協議。從圖上可以看出，ACSBMR 協議中的網絡生命期為150s左右，相對AOMDV 和EEABR 協議的分別提高了約50%和87.5%，這種提升對于延長網絡生命期具有重要意義。

圖9 網絡生命期

綜上仿真結果，由于在信息素更新中加入了節點能量均衡策略，同時數據傳輸以多路徑的形式完成，ACSBMR 協議能夠使節點能量得到均衡，進而延長網絡的生存期。

4 結束語

蟻群算法以其分布式計算、信息正反饋和啟發式搜索等系統特點，在無線傳感器網絡中的應用已很廣泛。本文將ACS蟻群算法的全局優化能力、多路徑路由方法以及能量均衡策略相結合，設計了一種無線傳感器網絡能量均衡多路徑路由協議ACSBMR。從路由發現所獲的路徑信息構造了路徑綜合評價函數，由此得到源節點與目的節點之間的多條優化路徑。在數據發送階段，根據各條路由路徑的不同路徑質量水平以概率分配方式選擇合適的路由路徑，把數據流量均衡地注入無線傳感器網絡，使得數據均衡地發送。仿真結果表明，ACSBMR 協議能夠實現無線傳感器網絡中均衡網絡能量和降低網絡擁塞的目的，進而延長網絡的生命期。

［1］Pantazis NA，Nikolidakis SA，Vergados DD.Energy－efficient routing protocols in wireless sensor networks：A survey ［J］.Communications Surveys ＆ Tutorials，2013，15 （2）：551－591.

［2］Saleem M，Di Caro GA，Farooq M.Swarm intelligence based routing protocol for wireless sensor networks：Survey and future directions ［J］.Information Sciences，2011，181 （20）：4597－4624.

［3］ZHAO Hong，HU Zhi，WEN Yingyou.ACS based differen－tiated service routing algorithm in wireless sensor network ［J］.Journal on Communications，2013，34 （10）：106－115（in Chinese）.［趙宏，胡智，聞英友.基于ACS的無線傳感器網絡區分服務路由算法［J］.通信學報，2013，34 （10）：106－115.］

［4］Rabelo RAL，Sobral JVV，Araujo HS，et al.An approach based on fuzzy inference system and ant colony optimization for improving the performance of routing protocols in wireless sensor networks［C］／／IEEE Congress on Evolutionary Computation，2013：3244－3251.

［5］Dominguez C，Cruz－Cortés N.Energy－efficient and locationaware ant colony based routing algorithms for wireless sensor networks［C］／／Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation.Dublin：ACM，2011：117－124.

［6］Zungeru AM，Seng KP，Ang LM，et al.Energy efficiency performance improvements for ant－based routing algorithm in wireless sensor networks［J］.Journal of Sensors，2013，2013（759654）：1－17.

［7］Jiang Xuepeng，Hong Bei.ACO based energy－balance routing algorithm for WSNs ［C］／／Proceedings of the First interna－tional conference on Advances in Swarm Intelligence.Beijing：Peking University，2010：298－305.

［8］Mahadevan V，Chiang F.iACO：A bio－inspired power efficient routing scheme for sensor networks ［J］.International Journal of Computer Theory and Engineering，2010，2 （6）：972－977.

［9］Mundada MR，Kiran S，Khobanna S，et al.A study on energy efficient routing protocols in wireless sensor networks ［J］.International Journal of Distributed and Parallel Systems，2012，3 （3）：311－330.

［10］Tekaya M，Tabbane N，Tabbane S.Multipath routing with load balancing and QoS in ad hoc network ［J］.IJCSNS international Journal of computer science and network security，2010，10 （8）：280－286.

［11］Ren Xiuli，Liang Hongwei，Wang Yu.Multipath routing based on ant colony system in wireless sensor networks［C］／／International Conference on Computer Science and Software Engineering.Wuhan：IEEE，2008：202－205.

［12］Kim S.An ant－based multipath routing algorithm for QoS aware mobile ad－hoc networks ［J］.Wireless Personal Communications，2012，66 （4）：739－749.

［13］Kiran M，Reddy GRM.Design and evaluation of load balanced termite：A novel load aware bio inspired routing protocol for mobile ad hoc network ［J］.Wireless Personal Communications，2014，75 （4）：2053－2071.

［14］Krishna PV，Saritha V，Vedha G，et al.Quality－of－serviceenabled ant colony－based multipath routing for mobile ad hoc networks［J］.IET Communications，2012，6 （1）：76－83.

［15］Mármol FG，Pérez GM.Providing trust in wireless sensor networks using a bio－inspired technique［J］.Telecommunication Systems，2011，46 （2）：163－180.