基于蟻群算法的一種能量高效路由算法的研究
2009-01-01 00:00:00楊靖張新榮徐保國
計算機應用研究 2009年2期
（1.江南大學 通信與控制工程學院， 江蘇 無錫 214122；2.貴州大學 電氣工程學院， 貴陽 550003）
摘 要：為了達到在信息傳輸路徑上節能的目的，提出了一種基于蟻群算法的節能路由算法。該算法根據節點當前可用能量選擇下一跳節點，按照節點經過的人工螞蟻數選擇數據匯聚節點，最終達到能量均衡使用和降低通信量的目的。經仿真計算證明該算法能合理地選擇路由，節能效果明顯，進一步延長了網絡生存期。
關鍵詞：無線傳感器網絡；能量；蟻群算法；路由
中圖分類號：TP393 文獻標志碼：A
文章編號：10013695(2009)02051302
Research on energyefficient routing algorithm based on ant colony algorithm
YANG Jing1，2，ZHANG Xinrong1，XU Baoguo1
(1.School of Communication Control Engineering， Jiangnan University， Wuxi Jiangsu 214122， China；2.School of Electric Engineering， Guizhou University， Guiyang 550003， China)
Abstract:In order to reduce power consumption，this paper proposed an energyefficient routing algorithm，which based on ant colony algorithm(ACA).The algorithm balanced the energy of network by choosing next hop node according to actual energy of nodes， and decreased traffic by using data aggregation node. The simulation results show that the algorithm can choose rational routing， and can prolong network lifetime.
Key words:wireless sensor networks(WSNs); energy; ant colony algorithm(ACA); routing
0 引言
無線傳感器網絡由很多小型的、攜帶電池能量有限的傳感器節點構成，節點間通過無線多跳方式進行信息的傳送，它在軍事、醫療健康、環境監控等方面得到了應用[1，2]。在無線傳感器網絡中，傳感器節點通常工作在條件惡劣的環境中，能源不可替代，所以必須采取各種措施降低節點能耗，提高網絡生存期 [3，4]。本文從降低節點通信能量消耗的角度出發設計節能路由算法，借此達到提高網絡生存期的目的。
無線傳感器網絡中的路由協議通常可以分為基于地址的路由協議（addresscentric，AC）和基于數據的路由協議（datacentric，DC）兩種。文獻[5]中比較了基于AC的路由算法和基于DC的路由算法的性能，仿真結果表明基于DC的路由算法具有更好的性能。蟻群算法[6]最早由意大利學者M. Dorigo等人提出，具有自組織、分布式計算、正反饋的特點。文獻[7]介紹了蟻群算法在Ad hoc網中的應用。本文基于蟻群算法和DC路由算法的思想提出了一種能量高效匯聚路由算法（energyefficient convergence routing algorithm based on ant colony algorithm，EECRA），該算法具有可擴展性的特點，網絡生存期比典型算法更長。
算法基本思想：
a）人工螞蟻根據節點剩余能量選擇下一跳節點，可保證網絡中節點的能量能被均衡使用。
b）人工螞蟻使用網絡的局部信息，通過并行搜索建立到sink節點的最優路徑。
c）根據人工螞蟻經過某個節點的數目選擇數據融合節點，使路徑趨向匯合。通過在數據融合節點進行數據融合，達到降低通信量的目的。
d）算法中按小概率引入隨機搜索策略，防止算法過早收斂。
1 能量高效蟻群路由算法
1.1 網絡能耗模型
無線傳感器網絡中網絡生存期的長短與第一個失效節點的出現時間有關，而節點失效通常是由于節點能量耗盡而造成的。從文獻[8]可知，節點用于無線通信的能耗遠大于計算能耗，因此本文研究重點是通過設計合理的路由算法，達到降低節點能量消耗的目的。
節點間通信時采用文獻[3]中的模型計算通信能耗。當傳感器節點發射k bit信息，傳輸距離為d時，發射機消耗的能量為
ET(k，d)=ETx×k+Eamp×k×d2(1)
傳感器節點接收k bit信息時接收機消耗的能量為
ER(k)=ERx×k(2)
式中參數設置如表1所示。
表1 無線通信模型能量損耗參數
參數項參數值
ETx50 nJ/bit
ERx50 nJ/bit
Eamp100 pJ/bit#8226;m-2
1.2 算法模型
本文算法采用的是蟻圈模型，并對之進行了改進。算法中構造了兩種類型的人工螞蟻，即尋路螞蟻和返回螞蟻，兩種螞蟻分別執行不同的信息素更新公式。尋路螞蟻完成選擇下一跳節點的功能；返回螞蟻完成建立最終路由的功能。
搜索概率公式：
Pij(t)=(ταij(t)×ηβij)/（
ktabukταik(t)×ηαik），j∈tabuk0，otherwises.t.dix＞djx（3）
啟發因子：
ηij=C×Ej/dij; j為下一跳節點
0；otherwise
信息素調整公式：
τij(t，t+1)=(1-ρ)×τij(t)+Δτkij(t，t+1)（4）
尋路螞蟻信息素增量公式：
Δτk(i， j)=C1×Ej/dij（5）
返回螞蟻信息素增量公式：
Δτk(i， j)=C2×Ej/(×JNK)（6）
式（3）中Pij是下一跳搜索概率；式（4）中0≤ρ＜1是信息素消逝速率；式（5）中，Ej是節點j的當前能量；式（6）中為尋路螞蟻搜索到的路徑上的平均能量，JNK是尋找到的路由總跳數；節點物理距離dij=(xi-xj)2+(yi-yj)2。
1.3 算法規則
規則1 尋路螞蟻從源節點出發，每只螞蟻攜帶信息包括經過節點的剩余能量的總和及當前總跳數。
規則2 尋路螞蟻按式（3）選擇下一跳節點，按式（4）（5）更新路徑信息；返回螞蟻按式（4）（6）更新路徑信息。
規則3 對尋路螞蟻設定最大跳數限制，當尋路螞蟻達到跳數限制，且下一跳節點為非目的節點時轉變成返回螞蟻，返回螞蟻按原路徑返回，同時將路徑上的信息素更新為一個較小的值。
規則4 尋路螞蟻到達目的節點時自動轉換成返回螞蟻，返回螞蟻回到源節點時消失。
規則5 當人工螞蟻按算法規則無法找到下一跳節點時，自動回退至前一跳節點重新進行搜索。
規則6 當尋路螞蟻到達某個節點時，執行變異操作——即按小概率隨機選擇下一跳節點，以增加解的多樣性。
規則7 當按算法規則在最近三次搜索中的跳數相同時，該尋路螞蟻所在的源節點不再發出尋路螞蟻。
規則8 數據融合節點的選擇：如果一個節點的信息流入有兩個以上的分支，其為融合節點。
融合節點選擇如圖1所示。其中節點1、2為融合節點。
1.4 算法步驟
文中算法步驟用偽代碼表示如下：
begin
/*Initialization */
ηij=1/Ej，Nmax=50，τij=0.01，Δτ=0，Nc=1
while(termination condition unsatisfied)
{for(ant=1;ant≤m;ant++)
{將m只人工螞蟻放置在源節點上}
for(i=1;i≤n;i++)
{for (ant=1;ant≤m;ant++)
{尋路螞蟻按式（3）及規則6選擇下一跳節點}
人工螞蟻按規則2更新路徑信息}
if超過跳數限制
{尋路螞蟻變成返回螞蟻，返回螞蟻按規則3更新路徑上的信息素}
if滿足規則7
{該尋路螞蟻停止搜索，所在源節點不再發出尋路螞蟻；
if找到目的節點
{尋路螞蟻變成返回螞蟻，返回螞蟻按規則2更新路徑信息}}
Δτ=0
Nc=Nc+1}
按規則8找出數據融合節點
輸出最后結果
end
2 仿真研究
2.1 可擴展性
可擴展性仿真主要驗證當網絡拓撲發生變化時，算法是否仍能找到合適路由。
網絡規模及參數：節點按正方形網格的形式布置在100 m×100 m的區域中，節點間距離15 m，節點數36，有效通信距離15 m。螞蟻數為節點數減1，α=2，β=2，ρ=0.2，Q=20。網絡拓撲變化規定為在時間0.01～1 s內有5%的節點移動。
如圖2所示，本文算法在網絡拓撲發生變化時仍然能找到目的節點（26號節點）的合適路由，具有可擴展性的特點。
2.2 能耗
網絡規模及參數：節點隨機布置在100 m×100 m的區域中，節點數10～80，螞蟻數為節點數減1，α=2.5，β=2.5，ρ=0.2，Q=20，節點初始能量Es=1 J，通信半徑25 m，每個節點接收和發送的數據均為2 000 bit。仿真實驗均進行100次，然后取平均值作為最后結果進行比較。
隨機選擇一個節點作為源節點，其余的作為目的節點，然后分別測試本文算法、Dijkstra算法、GITDC[5]算法單次廣播通信的能量消耗。
能量消耗對比如圖3所示。從圖3可以看出，EECRA算法單次廣播能耗最少，節能效果較好。
2.3 網絡生存期
網絡生存期定義為從仿真開始到第一個節點能量耗盡時為止的時間。網絡規模及參數與能耗仿真相同。隨機選擇一個節點作為目的節點，其余的作為源節點，進行通信實驗。圖4為本文算法、Dijkstra算法、GITDC算法的網絡生存期的比較。
GITDC算法是性能較好的一種DC路由算法。從圖4可以看出本文算法比GITDC算法的網絡生存期在多數情況下略好，總體上優于其他兩種算法。
3 結束語
無線傳感器網絡中的路由算法應是節能的、以數據為中心的路由算法。本文采用蟻群算法和數據匯聚的策略去降低節點的通信能耗，提出了一種節能路由算法。從仿真結果可以看出，該算法在能耗、網絡生存期方面相比典型算法具有更好的性能。
參考文獻：
［1］
ARICI T，ALTUNBASAK Y.Adaptive sensing for environment monitoring using wireless sensor networks[C]//Proc of IEEE Wireless Communications and Networking Conference.2004:23502355.
[2]MAINWARING A，POLASTRE J，SZEWCZYK R，et al.Wireless sensor networks for habitat monitoring[C]//Proc of the 1st ACM Workshop on Wireless Sensor Networks and Applications.2002:8897.
[3]HEINZELMAN W R，CHANDRAKASAN A，BALAKRISHNAN H.Energyefficient communication protocol for wireless microsensor networks[C]//Proc of the 33rd Annual Hawaii International Conference on System Sciences.Hawaii:[s.n.]，2000:30053014.
[4]INTANAGONWIWAT C，GOVINDAN R，ESTRIN D，et al.Directed diffusion for wireless sensor networking[J].IEEE/ACM Trans on Networking，2003，11(1): 216.
[5]KRISHNAMACHARI B，ESTRIN D，WICKER S.Modelling datacentric routing in wireless sensor networks[C]//Proc of IEEE INFOCOM.2002:4249.
[6]COLORNI A，DORIGO M，MANIEZZO V.An investigation of some properties of an ant algorithm[C]//Proc of the Parallel Problem Solving from Nature Conference.Brussels， Belgium:Elsevier Publishing，1992:509520.
[7]HUSSEIN O，SAADAWI T.Ant routing algorithm for mobile Ad hoc networks (ARAMA)[C]//Proc of IEEE International Conference on Performance， Computing and Communications.2003:281290.
[8]ESTRIN D.Wireless sensor networks tutorial part IV:sensor network protocols[R].Mobicom: [s.n.]，2002:2328.
