李 勁，周繼鵬

（暨南大學 信息科學技術學院，廣東 廣州510632）

0 引 言

與傳統(tǒng)路由算法相比，Ad Hoc網絡路由算法的設計面臨著網絡拓撲動態(tài)變化、帶寬受限、移動終端有限的可用資源等新問題的挑戰(zhàn)?？紤]到節(jié)點能量的有限性，為了避免由于節(jié)點能量耗盡而導致整個網絡的癱瘓，本文提出一種基于蟻群優(yōu)化 （ACO）的Ad Hoc路由算法，較之現有的能量有效路由算法在路由發(fā)現和數據轉發(fā)階段都具有優(yōu)勢。將路徑長度和節(jié)點剩余能量同時作為路由選擇標準，并采用多路徑的數據轉發(fā)，在減少能量耗費的同時平衡了網絡負載，以期延長網絡的生存時間。

1 相關工作

對于Ad Hoc網絡，延長節(jié)點電池能量的使用時間是一個關鍵問題。傳統(tǒng)的路由算法如 AODV［2］、DSR［3］和TORA［4］選擇最短路徑進行數據轉發(fā)，并不關注節(jié)點的能量問題。這樣的路由選擇往往會導致處于最短路徑上的節(jié)點能量消耗更快，從而加速了能量耗盡節(jié)點的產生，不利于延長網絡的生存期。為了改善傳統(tǒng)路由算法的能量限制問題，文獻 ［5－11］提出了若干能量有效的Ad Hoc路由算法，以下介紹其中具有代表性的幾種算法。

MTPR［5］路由算法根據路徑的總能量消耗進行路由選擇。路徑的能量消耗為，路徑上所有節(jié)點為完成數據轉發(fā)所需的能量之和。選擇具有最小能量消耗的路徑進行數據轉發(fā)，但是由于沒有考慮節(jié)點的剩余能量，所以MTPR在達成最小路徑能耗時并不能保證節(jié)點的生存時間得以延長。MMBCR［6］路由算法為了延長節(jié)點的生存期，將節(jié)點剩余能量作為路由選擇標準，選擇具有最大剩余能量的路徑完成數據轉發(fā)。在路由發(fā)現過程中，選出路徑上剩余能量最小的節(jié)點，將其剩余能量作為路徑的剩余能量。路徑剩余能量越大說明路徑的生存期越長。MDR［7］路由算法引入能量消耗速率，根據時下節(jié)點的能量消耗速率和剩余能量預測節(jié)點的生存時間，以路徑上節(jié)點的最小生存時間作為路徑的生存時間，選擇具有最大生存時間的路徑進行數據轉發(fā)。但是能量消耗速率并不能準確得出，而且根據當前能量消耗速率來預測可能會出現較大誤差。

基于Aco的路由算法是一種有效的、自適應的路由算法。Aco利用集群智能模仿自然界中真實蟻群的覓食過程。文獻 ［1］中實驗證明螞蟻具有搜索從蟻穴到食物間最短路徑的集體尋優(yōu)特性，這是由于螞蟻會在所經過的路徑上留下一種稱之為信息素的易揮發(fā)物質，而且螞蟻更傾向于朝著信息素濃度高的方向移動，這使得螞蟻在群體層次上呈現為一種正反饋現象，路徑越短，信息素濃度越高，選擇該路徑的概率更大。在Aco路由算法中，Ant是由節(jié)點獨立產生的特殊分組，用來測試到一指定節(jié)點的路徑，ant從源節(jié)點到目的節(jié)點的過程中收集路徑信息，在到達目的節(jié)點后按原路徑返回源節(jié)點，并根據收集到的路徑信息更新源節(jié)點到目的節(jié)點信息素，路徑質量越高信息素越高。每個節(jié)點維護一張信息素表，節(jié)點根據信息素進行路由選擇，既可以貪婪選擇信息素最高的路徑，也可從不同路徑中概率選擇，即信息素越高選擇該路徑的概率越大。路由選擇的隨機性使得到同一目的節(jié)點的數據可分散在不同路徑上，越高質量路徑上的數據包越多，達到網絡負載的平衡。現有Aco路由算法可分為：先應式的路由算法，Accelerated Ants Routing［12］中節(jié)點定期產生ant，不需要為ant指定目的節(jié)點，ant在網絡中漫游的過程中收集信息 （跳數、時延等），利用其更新經過節(jié)點到源節(jié)點的信息素；反應式的路由算法，在PERA［13］中，ant由節(jié)點按需產生，用于尋找到某個目的節(jié)點的路徑，ant的轉發(fā)不利用信息素信息，而是向目的節(jié)點廣播，路由發(fā)現過程中形成多條路徑，但數據包只貪婪轉發(fā)至信息素最高的路徑；混合式的路由算法，ARA［14］和 AntHocNet［15］具有反應式的路徑構造和先應式的路徑維護，ant在節(jié)點需要建立到目的節(jié)點的路徑時產生，中間節(jié)點根據信息素表概率轉發(fā)ant，當沒有目的節(jié)點信息素時將ant廣播至所有鄰居，在ant到達目的節(jié)點后按原路徑返回源節(jié)點完成信息素更新，路徑建立后通過周期性的產生ant維護現有路徑，文獻 ［16］在此基礎上引入地理位置信息輔助路由過程。

本文基于ACO路由算法提出一種能量有效的Ad Hoc路由算法EANT?；贏CO的EANT較之現有的能量有效路由算法在路由發(fā)現和數據轉發(fā)階段都具有優(yōu)勢。以MMBCR為例，在路由發(fā)現階段，EANT借助信息素表獲得所有可能路徑，比MMBCR洪泛的方式更加有效和節(jié)能；在數據轉發(fā)階段，EANT利用概率轉發(fā)形成多路徑的數據傳輸，比MMBCR唯一路徑的方式更好地平衡了網絡負載，更多節(jié)點的參與延長了節(jié)點的生存時間，減緩了能量耗盡節(jié)點的出現。EANT在完成信息素更新時，綜合了路徑跳數和節(jié)點剩余能量，路徑跳數越少，相同數據量轉發(fā)所耗費的能量也就越少，路徑總能量消耗越低則信息素越高；由路徑上所有節(jié)點的平均剩余能量和其中的最小剩余能量決定路徑的能量水平，優(yōu)先選擇節(jié)點剩余能量的多的節(jié)點參與數據轉發(fā)。

2 路由算法

2.1 網絡模型

將Ad Hoc網絡抽象為一個有向圖G＝ （V，E）。其中V是所有移動節(jié)點的有限集合，E是無線鏈路的有限集合。鏈路 （u，v）∈L表示節(jié)點v在節(jié)點u的傳輸范圍內，v是u的鄰居節(jié)點，u可以向v進行數據傳輸，N （u）表示節(jié)點u的鄰居集合，E（u）表示節(jié)點u的剩余能量。

每個節(jié)點維護一張信息素表，用以記錄當前鏈路的信息素。如表1為節(jié)點u的信息素表，其中以目的節(jié)點為關鍵字，vd代表節(jié)點u經過鄰居v到達d的信息素。

表1 節(jié)點信息素表

2.2 路由發(fā)現

路由發(fā)現過程參考了AntHocNet［15］中的一些架構，但與AntHocNet［15］在本質上有著功能性的不同。路由發(fā)現是按需的，當源節(jié)點信息素表中沒有目的節(jié)點的信息時，由源節(jié)點產生前向螞蟻Fant進行路由發(fā)現。Fant分組結構如下所示，其中源節(jié)點和ID唯一確認了一個Fant，節(jié)點可丟棄重復接收的Fant以避免回路產生，List域記錄了Fant經過的所有節(jié)點，TTL限制了Fant的跳數。

源節(jié)點 ID 目的節(jié)點List TTL

源節(jié)點將Fant廣播至所有鄰居節(jié)點，中間節(jié)點在收到Fant后，或是廣播至所有鄰居，或是按照式 （1）選擇唯一鄰居轉發(fā)。若中間節(jié)點信息素表中沒有目的節(jié)點信息，則將Fant轉發(fā)至所有鄰居，否則將概率轉發(fā)Fant。

式 （1）為節(jié)點u選擇鄰居v為下一跳的概率，其中d為目的節(jié)點，N （u）為節(jié)點u的鄰居集合，Φvd為u經v到達的d信息素，γ為放大系數。根據式 （1），若Φvd越大則節(jié)點u選擇v為下一跳的概率越大。γ較大時，概率大部分集中在信息素較大的鏈路上，Fant的探測性較小，反之可以使Fant具有較大探測性。

Fant到達目的節(jié)點后，由目的節(jié)點產生后向螞蟻Bant按Fant的原路徑返回源節(jié)點，Bant更新經過節(jié)點到目的節(jié)點的信息素。Bant的分組結構如下所示，其中List由Fant復制而來，Bant按照List中的節(jié)點路徑返回源節(jié)點，H為Bant經過的路徑長度即跳數，Emin為路徑最小剩余能量，即Bant經過節(jié)點中的最小節(jié)點剩余能量，Esum為路徑上節(jié)點剩余能量之和，H、Emin和Esum由目的節(jié)點分別初始化為0、∞和0。

源節(jié)點 目的節(jié)點 List H Emin Esum_____

Bant到達中間節(jié)點后，更新中間節(jié)點的信息素表。中間節(jié)點n在收到來自鄰居n－1的Bant后，節(jié)點n利用H、Emin和Eavg更新n信息素表中目的節(jié)點的信息素項，若沒有相關項則建立新的信息素表項，以目的節(jié)點為關鍵字，Bant的上游節(jié)點作為下一跳，根據Bant的跳數和路徑能量水平按照式 （2）、（3）更新信息素。本文將路徑跳數和路徑能量水平同時納入考量，路徑跳數越少，數據包轉發(fā)次數亦越少，則路徑消耗的總量能量越少；在考慮路徑上節(jié)點剩余能量時，綜合了剩余能量的最小值和平均值，路徑平均能量越多、路徑最小能量越大則路徑質量越高。式（3）反應了上述數量關系，路徑質量越高則信息素越高，其中α，β為相關系數，調整H、Emin和Eavg所占比重。

中間節(jié)點n完成信息素表更新后，按照式 （4）～ （6）更新Bant中的H、和Emin和Esum，其中E（n）為n的剩余能量。

上述路由發(fā)現的一般過程可描述為：

步驟1：源節(jié)點產生Fant并廣播至所有鄰居節(jié)點。

步驟2：中間節(jié)點在收到Fant后，根據Fant的源節(jié)點和ID確定是否重復接受，丟棄重復接收的Fant以避免回路和不必要負載的產生。

步驟3：中間節(jié)點按照式 （1）概率選擇Fant的下一跳節(jié)點，若信息素表中沒有目的節(jié)點的信息，則將Fant轉發(fā)至所有鄰居。

步驟4：Fant到達目的節(jié)點后，由目的節(jié)點產生Bant按照原路徑返回源節(jié)點，Bant在中間節(jié)點處按照式 （2）、（3）更新節(jié)點的信息素表，按照式 （4）～ （6）更新Bant中的相關項。Bant返回源節(jié)點后路由發(fā)現過程結束。

2.3 路由維護

在路由建立之后，數據包的轉發(fā)過程就可以對路由進行維護。如同AntHocNet［15］中，當一個數據包由源節(jié)點發(fā)往目的節(jié)點的過程中，經過的中間節(jié)點的信息素都會增加，同時沒有數據包經過的節(jié)點的信息素會以一定的速率揮發(fā)，其過程如式 （7）所示，其中δ為揮發(fā)速率δ∈ （0，0.5），Δ為每個數據包經過時增加的信息素。這樣的路由維護方式使得信息素迭代性的增加，只有在一段時間內都表現良好的路徑才能獲得較大的信息素。

節(jié)點根據信息素表概率轉發(fā)數據包。數據包同樣根據式 （1）所得概率選擇下一跳，較之Fant數據包轉發(fā)不需要較大的探測性，取較大的γ。

當數據包轉發(fā)過程中檢測到鏈路中斷，并且節(jié)點信息素表中沒有可用鏈接。首先由路由失敗節(jié)點產生Fant進行局部路由發(fā)現。為了將局部Fant約束在源路徑周圍，可限制Fant的TTL域，節(jié)點設置定時器，一定時間內沒有收到Bant則標記路由失敗，通知所有受到影響的源節(jié)點重新進行路由發(fā)現。

3 仿真實驗

實驗是在NS2仿真平臺上完成的，仿真結果如圖1、2、3所示。從圖1中可以看出，無論節(jié)點的移動速度快慢，數據包成功接收所經過的平均跳數比MMBCR均有減少。圖2、3顯示能量耗盡節(jié)點出現的時間都有明顯推遲，進而說明網絡生存期更長。實驗結果與設計原理相符，由于在信息素更新中加入路徑能量水平，同時數據傳輸以多路徑的形式完成，能夠使節(jié)點能量的使用時間延長，進而延長網路的生存期。

圖1 仿真結果1

4 結束語

針對Ad Hoc網絡中移動設備有限能量的限制，提出了一種基于蟻群優(yōu)化的能量有效路由算法。較之以往的能量有效路由算法，采用了基于蟻群優(yōu)化算法的路由發(fā)現和多路徑的數據傳輸，避免了洪泛式的路由發(fā)現，減少了節(jié)點能量耗費，并通過有效的多路徑傳輸平衡了網絡負載。實驗結果證明，EANT路由算法在性能上優(yōu)于MMBCR，平均跳數有明顯減少，網絡生存期延長，蟻群優(yōu)化算法應用于Ad Hoc網絡是很有意義的。

［1］Marco Dorigo，Thomas Stutzle.Ant colony optimization ［J］.Computational Intelligence Magazine，2006，1 （4）：28－39.

［2］Charles E Perkins，Elizabeth M Belding－Royer，Samir Das.Ad－Hoc on－demand distance vector routing ［C］.New Orleans：Proceedings of IEEE WMCSA，1999.

［3］David B Johnson，David A Maltz.Dynamic source routing in Ad Hoc wireless networks ［C］.Norwell：The Kluwer International Series in Engineering and Computer Science，1996.

［4］Vincent D Park，Scott Corson M.A highly adaptive distributed routing algorithm for mobile wireless networks ［C］.Japan：Proceedings of IEEE INFOCOM，1997.

［5］Scott K，Bambos N.Routing and channel assignment for low power transmission in PCS ［C］.Massachusetts：5th IEEE International Conference on Universal Personal Communications，1996.

［6］Suresh Singh，Mike Woo.Power－aware routing in mobile Ad Hoc networks［C］.New York：Proceedings of the 4th Annual ACM／IEEE International Conference on Mobile Computing and Networking，1998.

［7］Dongkyun Kim，Obraczka K，Cano J C，et al.Power－aware routing based on the energy drain rate for mobile Ad Hoc networks［C］.Florida：Proceedings of the 11th International Conference on Computer Communications and Networks，2002.

［8］Anand Srinivas，Eytan Modiano.Finding minimum energy disjoint paths in wireless Ad Hoc networks ［J］.Wireless Networks，2005，11 （4）：401－417.

［9］Kwon S，Ness B Shroff.Energy－efficient interference－based routing for multi－h(huán)op wireless networks ［C］.Spain：25th IEEE INFOCOM，2006.

［10］Hassanein H，JING Luo.Reliable energy aware routing in wireless sensor networks ［C］.Columbia：IEEE Workshop DSSNS，2006.

［11］Shresta N.Reception awareness for energy conservation in Ad Hoc networks ［D］.Sydney：Macquarie University，2006：1－175.

［12］Hiroshi Matsuo，Kouichi Mori.Accelerated ants routing in dynamic networks［C］.Korea：Proceedings of the International Conference on Software Engineering Artificial Intelligence Networking and Parallel Distributed Computing，2001.

［13］John S Baras，Harsh Mehta.A probabilistic emergent routing algorithm for mobile Ad Hoc networks［C］.France：Proc of the Conference on Modeling and Optimization in Mobile Ad Hoc and Wireless Networks，2003.

［14］Mesut Gunes，Udo Sorges，Imed Bouazizi.ARA：The ant colony based routing algorithm for MANETS ［C］.Canada：31st International Conference Parallel Processing Workshops，2002.

［15］Gianni Di Caro，Frederick Ducatelle，Luca Maria Gambardella.AntHocNet：An adaptive nature－inspired algorithm for routing in mobile Ad Hoc networks ［J］.European Transactions on Telecommunications，2005，16 （5）：443－455.

［16］Daisuke Kadono，Tomoko Izumi，Fukuhito Ooshita，et al.An ant colony optimization routing based on robustness for Ad Hoc networks with GPSs ［J］.Ad Hoc Networks，2010，8（1）：63－76.