蟻群優化和能量有效的Ad Hoc路由協議

摘 要：為了延長Ad Hoc網絡的生存周期，提出了一種基于蟻群優化和能量有效的Ad Hoc網絡多路徑動態路由算法ACOERA。該算法根據路徑的有效能量率進行路由選擇，路徑建立后通過蟻群優化算法動態收集路徑信息，并對路由表進行更新。仿真結果表明，該算法能有效延長網絡生存時間，增強通信網絡的自適應能力。

關鍵詞：蟻群算法； 路由； 能量； Ad Hoc

中圖分類號：TN915-34; TP393-34文獻標識碼：A文章編號：1004-373X(2011)19-0049-03

Ant Colony Optimization and Energy Efficient Ad Hoc Routing Protocol

ZHAO Xiao-hua， CHEN Hui

(Shaanxi College of Communication Technology， Xi’an 710018， China)

Abstract： In order to prolong the life cycle of Ad Hoc network， a multi-path dynamic routing algorithm ACOERA based on ant colony optimization and energy efficient is presented. The algorithm selected route according to the effective energy rate， and the route was updated through dynamic path information collected by the ant colony optimization algorithm after the path was established. Simulation results show that the algorithm can prolong the network lifetime effectively and enhance the adaptive capacity of the communication network.

Keywords： ant colony algorithm; routing; energy; Ad Hoc

0 引 言

路由算法是網絡傳輸的關鍵技術，無線移動自組網(Mobile Ad Hoc Networks，MANETs)是一種具有臨時快速自動組網能力的新型網絡，這種網絡不存在固定基礎設施，拓撲結構變化頻繁，并且所有節點地位平等，可作為路由轉發節點。為此，開發一種較好的動態路由協議將成為Ad Hoc網絡設計的關鍵。

蟻群算法最早由意大利學者M.Dorigo引入，它是對自然界螞蟻的尋徑方式進行模似而得出的一種仿生算法。螞蟻在運動過程中，能夠在它所經過的路徑上留下一種稱之為外激素(pheromone)的物質進行信息傳遞，螞蟻通過感知這種物質，以此指導自己的運動方向。因此由大量螞蟻組成的蟻群集體行為便表現出一種信息正反饋現象，即某一路徑上走過的螞蟻越多，則后來者選擇該路徑的概率就越大。

在移動Ad Hoc網絡中，節點的能量是有限的，并且動態變化，這些都給路由協議的設計帶來了很大的挑戰，移動節點需要采用電池一類的可耗盡能源來提供電源，而且每個節點都要充當路由器的功能，若某些節點由于能量耗盡而停止工作，就可能導致整個網絡的分裂。在目前的技術水平下，電池容量難以大幅度提高，所以要通過有效設計合理的路由協議來延長節點的生存時間和網絡的整體壽命，具有非常重要的意義。

本文提出了一種螞群優化和能量有效的路由算法(Ant Colony Optimization and Energy Efficient Routing Algorithm，ACOERA)，重點研究了在采用蟻群優化算法進行路由維護的過程中，對節點的剩余能量進行有效的平衡，提高了路由可靠性，延長了網路壽命。

1 ACOERA算法設計

1.1 ACOERA算法模型

根據蟻群算法的基本模型，結合對節點能量和傳輸路徑平均能量的考慮，本文提出如下算法模型。

節點i的有效能量Ei:Ei(t)=Ei_current(t)Ei_max

(1) 節點i在t時刻的有效能量是節點i當前時刻的能量與最大能量的比值。

節點i與節點j之間的能量有效率:Eei，j(t)=[Ei(t)+Ej(t)]#8226;λ

(2) 節點i與j之間的有效能量率是兩個節點的有效能量之和與節點間能量系數λ之積。

節點i與j之間的能量系數λ(0>λ>1)表示兩個相鄰節點剩余能量的平衡狀態;λ的取值根據如下決定：

路徑有效能量率表示從源節點到目的節點間路徑上所有相鄰節點之間的有效能量率之積。Eepath(t)=γ#8226;∏Eei，j

(3)式中:i，j表示從源節點到目的節點間路徑上所有相鄰節點;γ表示平滑系數，0<γ≤1。

節點i由節點j轉發到目的節點d的轉移概率為:Pi，j(t)=[τdj(t)]α#8226;[ηdj(t)]β∑s∈Ni[τds(t)]α#8226;[ηds(t)]

(4)式中：Ni表示節點i可供選擇的鄰居節點集合;τsj(t)表示t時刻節點i到目的節點d的路由中節點j作為下一跳路徑(i，j)上的信息素值；ηdj(t)表示節點i到經由節點j到目的節點d的啟發式值，該啟發式值為j到d跳數的倒數；α為信息素啟發因子，表明螞蟻對信息素較大路徑選擇的傾向性；β為跳數啟發因子，表明螞蟻對跳數較少的路徑選擇的傾向性。

節點i的轉移概率滿足下式:∑j∈NiPdj=1

(5) 在t+Δt時刻，當前節點i經由j節點到目的節點d的路徑上信息素按照式(6)進行更新。τdj(t+Δt)=(1－ρ)τdj(t)+ρΔτdj

(6)式中：ρ∈［0，1］表示信息素揮發系數，用以限制信息素的無限增加；j表示當前節點的相鄰節點。

信息素增量Δτdj是在最近Δt時間內當前節點到目的節點d的路由中，選擇節點j為下一跳路徑上的信息素增量，按照式(7)進行計算。Δτdj=λ1Eepath+λ2Dj#8226;Q

(7)式中：λ1，λ2表示權重因子;Q為信息素強度；Dj表示從節點j到目的節點的跳數。

1.2 ACOERA算法規則

在本算法中根據蟻群算法的特點，定義了向前螞蟻Fant和返回螞蟻Bant以及路由維護螞蟻Mant，路由錯誤螞蟻Eant。

規則1：當源節點需要發送數據到目的節點，檢查節點的路由表，如果存在到目的節點的路由，選擇概率最大的路由發送，否則，參考規則2。

規則2：如果源節點沒有到達目的節點的路由，節點發出Fant，每個Fant保存途經的路徑、路徑能量率，轉發延遲等信息。

規則3：每個Fant有最大跳數限制，如果到達最大跳數仍然沒有到達目的節點，則從當前節點轉換到Bant返回源節點，更新反向路由，雖然這些路由沒有到達目的節點，但是也可以為以后到其他節點的數據傳輸提供路由。

規則4：當Fant螞蟻到達目的節點，目的節點保存Fant的跳數、延遲，建立Bant沿著反向路徑返回源節點，建立正向路由，并且根據式(6)更新路徑上的信息素。

規則5：當目的節點收到多個來自同一源節點但正向路徑不同的Fant時，檢查每個Fant的路徑跳數、延時和路徑能量率信息，如果有其中一項信息優于之前收到的Fant中的信息時，保留該路徑，創建Bant，根據規則4，返回源節點。從而建立多條備用路徑。

規則6：節點按每個HELLO_INTERVAL間隔向相鄰節點發出Mant螞蟻，如果節點在2個HELLO_INTERVAL間隔沒有收到相鄰節點發出的Mant螞蟻，認為相鄰節點的路徑已經斷開，將該路徑的信息素設置為0，啟動路由維護機制。

規則7：當節點啟動路由維護機制，創建Emat，根據節點的路由表通知其他相鄰節點刪除到失效節點的路由。源節點發送數據時，檢查有沒有備用路由，如果存在，選擇概率最大的路由發送，否則，根據規則1，重新創建路由。

2 ACOERA路由協議的仿真與分析

為了驗證ACOERA協議的有效性，本文對ACOERA協議進行了仿真實驗，實驗平臺采用NS2，在仿真實驗中主要分析算法使用后的網絡生存周期發生的變化和平均端到端時延。目的是驗證使用蟻群算法和能量約束的有效性。

網絡生存時間表示網絡中第一個節點能量耗盡的時間，可以衡量網絡中節點能量消耗的平衡性。

節點的端到端延時表示從源節點發送分組到目的節點的平均傳輸時間，主要反映了源節點到目的節點路由的效率。

2.1 實驗參數

實驗中參數設置如下：λ1=1，λ2=1，ρ=0.2，α=0.4，β=0.4， γ=0.4，Q=20，節點初始能量為70 J，發送和接收分組的功率消耗為660 mW和395 mW。

實驗場景采用100 m×100 m， 節點發送范圍為25 m，MAC層采用IEEE 802.11協議，發送速率為2 Mb/s，節點移動模型采用Random Waypoint移動模型，在仿真實驗中采用2個場景進行實驗，上述參數為兩個場景的公共參數。

場景一，用來分析網絡生存時間，節點從10~100變化，螞蟻數取為節點數-1，網絡拓撲變化在0.1~1 s內隨機變化。

場景二，用來分析端到端平均時延，仿真時間為450 s，節點最大移動速度為20 m/s，暫停時間為0 s，10 s，…，90 s，100 s，隨機產生8條CBR數據流，發送速率為4分組/s，每個分組為512 B。

2.2 實驗結果

圖1是本算法與文獻[1]中所描述的MTPR算法的性能比較，本算法明顯比MTPR算法的性能優越，這主要是MTPR算法的傳輸模型導致某些節點會過度消耗能量，使得網絡生存時間較短，隨著節點增加網絡生存時間延長。

圖1 網絡生存時間數據包端到端延時表示在網絡模擬中，源節點發送一個數據包被目的節點正確接收所需要的時間，平均端到端延時表示能接收到所有數據包的延時之和除以數據包的數目。從圖2可以看出，算法ACOERA的平均端到端兩個延時小于AODV算法，這主要有以下原因：第一，算法采用了蟻群優化算法，節點的路由效率較高，第二，采用了有效的路由維護機制，可以很快地在路徑失效的情況下重建路由。

圖2 平均端到端延時3 結 論

本算法基于蟻群算法并且充分考慮了節點剩余能量和相鄰節點剩余能量的關系，有較明顯的節能效果。節點采用多條備用路徑，在節點失效的情況下，提供可以替代的備用路由，因此可以提高路由效率。仿真實驗表明，算法在生存時間和傳輸效率上與其他算法有較明顯的優勢。

參 考 文 獻

［1］ TOH C K. Maximum battery life routing to support ubiquitous mobile computing in wireless Ad Hoc networks [J]IEEE Communications Magazine， 2001， 39 （6）： 138-147.

［2］ CARO G D， DORIGO M. AntNet: A mobile agents approach to adaptive routing [R] Belgium: Technical Report IRIDIA， 1997.

［3］ CAO Lijuan， DAHLBERG T， WANG Yu. Performance evaluation of energy efficient Ad Hoc routing protocols [C]//Proceedings of IEEE Performance， Computing， and Communications Conference， IPCCC 2007，26th IEEE International. [S.l.]: IEEE， 2007： 306-313.

［4］ KIM D， GARCIA-LUNA-ACEVES J， OBRACZKA K， et al. Routing mechanisms for mobile Ad Hoc networks based on the energy drain rate [J] IEEE Transactions on Mobile Computing， 2003， 2 （2）： 161-173.

［5］ SINGH S， WOO M， RAGHAVENDRA C. Power-aware routing in mobile Ad Hoc networks [C]//Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking MobiCom 98. New York， NY， USA： ACM Press， 1998： 181-190.

［6］ GUPTA N， DAS S R. Energy-aware on-demand routing for mobile Ad Hoc networks [C]//Proceedings of the 4th International Workshop on Distributed Computing， Mobile and Wireless Computing IWDC 02.London， UK： Springer-Verlag， 2002: 164-173.

［7］ MALEKI M， DANTU K， PEDRAM M. Lifetime prediction routing in mobile Ad Hoc networks [C]//IEEE Wireless Communications and Net working， WCNC 2003. New Orleans: IEEE， 2003： 1185-1190.

［8］ MALEKI M， DANTU K， PEDRAM M. Power-aware source routing protocol for mobile Ad Hoc networks [C]//Proceedings of the 2002 International Symposium on Low Power Electronics and Design ISLPED 02.New York， NY， USA： ACM Press， 2002: 72-75.

［9］ 方路平，劉世華.NS2網絡模擬基礎與應用［M］.北京：國防工業出版社，2008.