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

關鍵詞：蟻群算法； 路由； 能量； 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 引 言

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

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

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

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

1 ACOERA算法設計

1.1 ACOERA算法模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.2 ACOERA算法規(guī)則

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

規(guī)則1：當源節(jié)點需要發(fā)送數(shù)據到目的節(jié)點，檢查節(jié)點的路由表，如果存在到目的節(jié)點的路由，選擇概率最大的路由發(fā)送，否則，參考規(guī)則2。

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

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

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

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

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

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

2 ACOERA路由協(xié)議的仿真與分析

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

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

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

2.1 實驗參數(shù)

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

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

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

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

2.2 實驗結果

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

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

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

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

參 考 文 獻

［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］.北京：國防工業(yè)出版社，2008.