李 勁，周繼鵬

（暨南大學(xué) 信息科學(xué)技術(shù)學(xué)院，廣東 廣州510632）

0 引 言

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

1 相關(guān)工作

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

MTPR［5］路由算法根據(jù)路徑的總能量消耗進(jìn)行路由選擇。路徑的能量消耗為，路徑上所有節(jié)點(diǎn)為完成數(shù)據(jù)轉(zhuǎn)發(fā)所需的能量之和。選擇具有最小能量消耗的路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)，但是由于沒(méi)有考慮節(jié)點(diǎn)的剩余能量，所以MTPR在達(dá)成最小路徑能耗時(shí)并不能保證節(jié)點(diǎn)的生存時(shí)間得以延長(zhǎng)。MMBCR［6］路由算法為了延長(zhǎng)節(jié)點(diǎn)的生存期，將節(jié)點(diǎn)剩余能量作為路由選擇標(biāo)準(zhǔn)，選擇具有最大剩余能量的路徑完成數(shù)據(jù)轉(zhuǎn)發(fā)。在路由發(fā)現(xiàn)過(guò)程中，選出路徑上剩余能量最小的節(jié)點(diǎn)，將其剩余能量作為路徑的剩余能量。路徑剩余能量越大說(shuō)明路徑的生存期越長(zhǎng)。MDR［7］路由算法引入能量消耗速率，根據(jù)時(shí)下節(jié)點(diǎn)的能量消耗速率和剩余能量預(yù)測(cè)節(jié)點(diǎn)的生存時(shí)間，以路徑上節(jié)點(diǎn)的最小生存時(shí)間作為路徑的生存時(shí)間，選擇具有最大生存時(shí)間的路徑進(jìn)行數(shù)據(jù)轉(zhuǎn)發(fā)。但是能量消耗速率并不能準(zhǔn)確得出，而且根據(jù)當(dāng)前能量消耗速率來(lái)預(yù)測(cè)可能會(huì)出現(xiàn)較大誤差。

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

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

2 路由算法

2.1 網(wǎng)絡(luò)模型

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

每個(gè)節(jié)點(diǎn)維護(hù)一張信息素表，用以記錄當(dāng)前鏈路的信息素。如表1為節(jié)點(diǎn)u的信息素表，其中以目的節(jié)點(diǎn)為關(guān)鍵字，vd代表節(jié)點(diǎn)u經(jīng)過(guò)鄰居v到達(dá)d的信息素。

表1 節(jié)點(diǎn)信息素表

2.2 路由發(fā)現(xiàn)

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

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

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

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

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

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

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

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

上述路由發(fā)現(xiàn)的一般過(guò)程可描述為：

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

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

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

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

2.3 路由維護(hù)

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

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

當(dāng)數(shù)據(jù)包轉(zhuǎn)發(fā)過(guò)程中檢測(cè)到鏈路中斷，并且節(jié)點(diǎn)信息素表中沒(méi)有可用鏈接。首先由路由失敗節(jié)點(diǎn)產(chǎn)生Fant進(jìn)行局部路由發(fā)現(xiàn)。為了將局部Fant約束在源路徑周圍，可限制Fant的TTL域，節(jié)點(diǎn)設(shè)置定時(shí)器，一定時(shí)間內(nèi)沒(méi)有收到Bant則標(biāo)記路由失敗，通知所有受到影響的源節(jié)點(diǎn)重新進(jìn)行路由發(fā)現(xiàn)。

3 仿真實(shí)驗(yàn)

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

圖1 仿真結(jié)果1

4 結(jié)束語(yǔ)

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

［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，F(xiàn)rederick 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，F(xiàn)ukuhito 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.