基于改進蟻群算法的無線傳感器網絡的路由優化

沙娓娓，劉增力

（1. 昆明理工大學 信息工程與自動化學院，云南 昆明 650500；2. 昆明理工大學 民航學院，云南 昆明 650500）

0 引言

無線傳感器網絡：指利用無線通信的方法，將微型傳感器節點（被感知對象的內部、附件之中）組成多跳自組織網絡，在環境監測、國家安全以及軍事偵察等相關領域得以普遍應用[1]。傳感器節點由電池提供能量，同時具有數量多、體積小等特點，一旦完成部署，即難以繼續補充能量。所以在設計無線傳感器網絡路由協議時，要充分考慮節點能量問題，以延長網絡生存周期達到傳輸大量數據的要求[2]。

Dorigo針對TSP的問題，提出全新的模擬進化算法——蟻群優化算法[3]。與此同時隨著該算法的應用，有效解決指派、調度以及旅行商等各類優化組合問題[4]。

Kassabalidis等潛心多年研究，結合蟻群算法，提出Ant-Net算法[5]，該算法中螞蟻主要可分為兩大類：其一是具有收集節點信息作用的前向螞蟻；其二為返回螞蟻，將前向螞蟻收集的信息，反饋在路由表之中。

Schoonderwoerd R等人通過概率選擇和更新路徑的方式，提出ABC算法[6]，此算法中螞蟻從源節點到達目的節點后就死亡，同時更新路由表。文獻[7]基于 DD算法[8]提出一種全新的算法——ARAWSN，有助于改善能耗問題，可找到源節點到目的節點間最短的路徑。

本文提出IARA這一全新優化的算法，在源節點選擇下一跳節點，兼顧了節點的能量、傳輸方向、節點間距離等因素，通過改進的信息素更新公式、啟發函數、選擇概率這三個方面，不僅降低了節點能耗，同時有助于延長網絡生存周期。

1 無線傳感器網絡通信的能耗模型

在能耗模型方面，本文考慮選擇同文獻[9]的模型，將k bit的數據發送到d節點時，可用如下公式表示這一過程消耗的能量。

此時接收節點消耗能量：

融合數據消耗能量：

式（1）～（3）中：elecE、ampE、fuseE分別指發送和接收、傳輸放大以及融合數據等單元功耗，如果傳輸距離較大，則通常建議選擇運用多路徑衰減模型，相反的如果較小，則一般運用自由能量模型。

2 改進的WSN蟻群路由算法描述

在具體設計 WSN路由時，應充分考慮到無線傳感器網絡節點的特殊性，即其能量有限。針對這一問題，本文緊扣“有效性”這一原則，充分考慮下一跳節點的能量參數以及實際傳輸距離、方向等問題，使蟻群在自動尋優的同時，也具有能量感知意識。

2.1 路徑概率選擇

從路徑探索的角度出發，非常有必要結合某種概率訪問周圍節點：而從路徑尋優這一層面分析，為避免局部最優解，在訪問時節點時，如果僅以概率為基礎，其獲得的最優解并非都有意義[10]。因此，引入傳輸方向參數，改進后的轉移概率公式如下：

式（4）中，表示第k只螞蟻從節點i向節點j轉移的概率；用于表示k可通信節點集合，如果其通信節點并非可允許的節點，那么此時概率應等于0；這里τij、ηij分別表示信息素濃度、啟發函數，兩者的權重值分別為α、β。假設α值較大，則對應的信息素濃度發揮的作用相對較大，換言之即螞蟻會以已經走過的路徑為主，彼此間具有較強的協同能力；相反的如果β值較大，則對應說明啟發函數可發揮更大的作用，此時以未探索過的節點為主，換言之即螞蟻具有較強的探索能力，可探索新節點。θ為下一跳節點 next,源節點 source和目的節點destination的夾角；γ為定義的常量，指明了傳輸方向對節點路由選擇的影響程度。

如圖1所示，即為θ的示意圖，通過該圖可充分說明，假設θ越小，那么對應的d1+d3越小，傳輸方向越接近于節點next到destination節點的連線方向，且

圖1 傳輸方向Fig.1 Direction of communication

2.2 本地啟發函數

螞蟻從節點i轉移到節點j的期望程度用啟發函數ijη表示。由于最初是針對TSP的問題而提出該算法，所以啟發函數并未充分考慮其它因素，僅以兩節點的距離為考量重點。而無線傳感器網絡，除應充分重視距離因素之外，還需綜合考慮諸如節點、鄰居節點剩余能量等多方面的問題。基于此，如式（6）所示，即為本文的啟發函數定義：

式（6）中，Ecurrent(j)為節點 i的鄰居節點 j當前剩余能量；Ni(k)表示集合節點i的鄰居節點集合；(k)為節點i所有鄰居節點的剩余能量。節點剩余能量與該節點是否會被選擇有直接的關系，節點的能量水平越低，被選擇的概率也會越低；dij表示的是節點i和節點j之間的距離。

2.3 信息素更新

螞蟻選擇下一跳節點時，會在經過路徑上釋放出信息素，從而形成并增加可用于引導后來螞蟻的信息素濃度。由改進后的公式可知，節點剩余能量越多的路徑上累積的信息素濃度也會越高，這樣有助于避免由于路徑（最短）的信息素濃度過大，而出現螞蟻過分集中的問題，有助于避免節點能量消耗過快。給出信息素更新公式如下：

其中：Lk為螞蟻k從源節點到目的節點所經過的路徑長度；λ為一個全局設定的常量； Ek_min、Ek_avg分別可用于表示螞蟻k經過路徑節點的最小能量、平均能量。如式（8）所示，綜合考慮了路徑中最小能量、平均能量以及路徑總長度這三個因素。假設在更新路徑信息素時，未充分考慮這一情況 ，僅以節點能量為依據，那么運用此算法，則路徑不一定最短。

2.4 IARA算法的實現

具體實現步驟如下：

（1）初始化。清空螞蟻路徑，初始化訪問標志，顯示為未訪問；在源節點中放m只螞蟻，同時設置為已訪問，此為路線的第一個節點，另外各節點的初始值均為常數，且包含同樣的信息素；信息素增量在初始時為0；

（2）Antnum等于0，即到達目的節點的螞蟻數為0；

（3）螞蟻數k等于0；

（4）通過計算求出節點間距離；

（5）運用（4）式計算轉移概率，并確定節點j，把螞蟻k轉移至此j，同時設置該節點為已訪問，除了要修改螞蟻節點的能量外，還應對應修改前一節點能量；

（6）如果有節點能量耗盡，則直接跳至（9），如果沒有則依據（7）進行；

（7）k等于k+1，對比該值與m大小，較小轉（5），否則轉（8）；

（8）判斷Antnum是否等于m，若兩者相等，即此時螞蟻都到目的節點，則轉（9），如果沒有則轉（3）；

（9）計算螞蟻經過的整個路徑的長度，比較得出最優路徑；

（10）如果通過計算，并未有節點耗盡能量，則根據式（7）、（8）進行信息素的全局更新后轉（2）執行；否則轉（11）；

（11）如上述循環結束，最終輸出結果。

3 仿真及結果分析

通過Matlab訪真、驗證IARA算法，在此基礎上對比分析了 ACO算法（文獻[3]），仿真范圍為100 m×100 m，并在這一范圍內播撒（隨機）50個節點，將設定目標節點（50,50）。

考慮到測試的方便性，本文中設螞蟻總數為50只，即等于節點個數；無線傳感器節點每次傳輸相同大小的數據包，參數初值為：α=1，β=2，γ=1，λ =1，rmax=50，每個節點初始能量為0.5J。

正如上文所述，引入本算法的目的，即在延長網絡使用時長的同時，最小化能量消耗。所以本文基于螞蟻群算法，提出IACA法，該法改進了相關參數，通過傳輸距離、節點能量、傳輸方向這三者的綜合考慮，從而找到理想的延長網絡生存時間的方法。因此，為了驗證算法的性能，對比ACO算法，具體體現在如下兩個方面：其一網絡節點能耗總量；其二死亡節點數。

3.1 節點能耗

本文中的網絡生存時間，由所有節點消耗的能量之和反映，假設能耗越大，那么其生存時間就會越短；也就是說，一定時間內消耗大量的能量，則其對應的網絡生存時間較短；相反的，如果能量消耗較小，則說明具有較長的生存時間，全網節點共計50個，每個節點的初始能量為0.5J，因此全網總能量為25J，圖2 IARA和ACO能量消耗對比圖。從圖2中可以看出，IARA和ACO分別在930、710輪時全網能量消耗殆盡。

3.2 死亡節點數

能耗與死亡節點有一定關系，但是兩者又存在一定差異性。通過能耗量可充分說明在接收或者發送數據的消耗量，但是節點平均能耗與死亡節點數沒有必然的聯系，即死亡節點數不會單純因為節點平均能耗多而增多。假設僅少數節點消耗了能量，其它節點并未消耗或者基本沒有消耗能量，這種情況下死亡節點數較少，但是不可忽視的是極有可能死亡節點均處于關鍵路徑上，即使得整個網絡癱瘓，對應的其網絡生存的時間必然也會很短；假設由多個節點共同消耗節點能量，即屬于平均消耗，那么就算最后有很多死亡節點，也不易出現關鍵節點完全失效的問題，即相應的出現網絡癱瘓的機率也會較小，這樣一來，即有延長網絡生存時間的作用。從圖3中可以看出，IARA和ACO分別在930、710輪時全部節點死亡，因此IARA算法的生命周期比ACO要長，達到了預期的效果，證明了算法的有效性。

圖2 能量消耗Fig.2 Energy consumption

圖3 死亡節點數Fig.3 Nodes death

4 總結

本文基于無線傳感器網絡的特殊性，即節點能量少，引入具有健壯性、自組織性、自治性等優點的蟻群算法，提出改進的蟻群路由算法 IARA，在基本蟻群算法的基礎上綜合考慮了節點的能量、距離、傳輸方向等參數。仿真結果表明：通過該算法解決了無線傳感器網絡瓶頸問題，即能耗大、網絡生存時間短，形成了節能、快速的路由來滿足網絡使用需要。

[1] 段海濱. 蟻群算法及其應用[M]. 北京: 科學出版社2007:1389.DUAN H B, Ant colony algorithm and its application[M].Beijing: Science Press 2007: 1389.

[2] 陳宇, 等. 基于改進蟻群算法的無線傳感器網絡路由的研究[D]. 廣州: 華南理工大學, 2012.CHEN Y, et al. Research on routing of wireless sensor networks based on improved ant colony algorithm[D]. Guangzhou:South China University of Technology, 2012.

[3] Dorigo M, Gambardella L M. Ant colony system a cooperative learning approach to the travelling salesman problem[J].IEEE Transactions on Evolutionary Computation. 1997, 1(1): 53-66.

[4] Sim K M, Sun W H. Multiple ant-colony optimization for network routing[C]//Proceedings of the 1st International Symposium on Cyber Worlds, Washington DC, USA, 2001:277-281.

[5] Kassabalidis I, El-Sharkaw M A, Marks R J. Swarm intelligence for routing in communication networks[J]. Global telecommunications 2001, 6(6): 3613-3617.

[6] Schoonderwoerd R, Holland O, Bruten J, et al. Ants for load balancing in telecommunication networks[R]. Bristol: Hewlett Packard Lab, 1996. M. Goldfarb. Analog baseband IC for use in direct conversion W-CDMA receivers. IEEE.

[7] 梁華為, 陳萬明, 李帥, 等．一種無線傳感器網絡蟻群優化路由算法[J]. 傳感器技術學報, 2007, 20(11): 2450-2455.LIANG W H, CHEN W M, LI S et al. Ant colony optimization routing algorithm for Wireless Sensor Networks[J]. Journal of sensor technology, 2007, 20(11): 2450-2455.

[8] Intanagonmimwt C, Govindan R, Estrin D. Directed diffusion for wireless sensor networking[J]. IEEE/ACM Trans on Networking, 2003, 11(1): 2-16.

[9] Heinzelman W R. An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Trans on Wireless Communication, 2002, 1(4): 660-670.

[10] 滑楠, 史浩山, 高程, 等． 一種適用于無線傳感器網絡路由的改進蟻群算法[J]. 傳感技術學報, 2007, 20(7):1063-1069.HUA N, SHIH S, GAO C, et al. An improved ant colony algorithm for routing in Wireless Sensor Networks[J]. Journal of sensor technology, 2007, 20(7): 1063-1069.