基于蟻群算法的無線傳感器網(wǎng)絡(luò)能量有效路由算法研究*

童孟軍 ，俞 立，鄭立靜，董齊芬

(1.浙江工業(yè)大學(xué)信息工程學(xué)院，杭州 310032;2.杭州電子科技大學(xué)計算機學(xué)院，杭州 310018)

無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)［1］是繼Internet之后隨著無線通信技術(shù)、傳感器技術(shù)、微電子技術(shù)和分布信息處理技術(shù)發(fā)展起來的一種新興信息獲取技術(shù)。WSN綜合了嵌入式技術(shù)、傳感器技術(shù)、通信技術(shù)和分布式信息處理技術(shù)，能夠協(xié)作實時感知、監(jiān)測、采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境的信息，并對數(shù)據(jù)進行適當(dāng)?shù)奶幚硪垣@得精簡準(zhǔn)確的信息，并傳送給最終的用戶。

無線傳感器網(wǎng)絡(luò)由于節(jié)點能量有限，這給傳感器網(wǎng)絡(luò)路由協(xié)議的設(shè)計提出了巨大挑戰(zhàn)。將蟻群算法應(yīng)用于路由協(xié)議的設(shè)計中，利用蟻群算法的網(wǎng)絡(luò)分布式、個體簡單而群體智能表現(xiàn)出優(yōu)化等特點很好的均衡了網(wǎng)絡(luò)負載，延長了網(wǎng)絡(luò)壽命，近年來引起了中外研究人員的廣泛關(guān)注，已逐漸成為當(dāng)前無線傳感器網(wǎng)絡(luò)路由設(shè)計研究領(lǐng)域的熱點。

隨著各種智能算法的相繼出現(xiàn)，越來越多的學(xué)者將它們應(yīng)用于無線傳感器網(wǎng)絡(luò)路由協(xié)議的研究中，而螞蟻尋找食物的行為與網(wǎng)絡(luò)中節(jié)點尋找路由的過程十分相似，因此基于蟻群算法的傳感器網(wǎng)路由協(xié)議得到了大量的關(guān)注。文獻［2－3］給出了關(guān)于蟻群算法的概述性的介紹，基于蟻群的網(wǎng)絡(luò)路由協(xié)議的典型代表有Kassabalidis等人提出的AntNet算法［4］。然而 AntNet是面向有線網(wǎng)絡(luò)的，文章［5］對蟻群算法作了改進，提出了ACRA算法，文章［6］在DD算法的基礎(chǔ)上將蟻群優(yōu)化應(yīng)用到路由算法中，提出了ARAWSN算法，文章［7］在ACO算法的基礎(chǔ)上提出了一種基于預(yù)測模式的蟻群優(yōu)化算法，文章［8］提出了 AntHocNet算法，文章［9］提出了ARAMA 算法，ANSI［10］和 ARA［11］都是基于智能蟻群算法的按需路由協(xié)議。

本文將蟻群算法的特點與無線傳感器網(wǎng)絡(luò)路由設(shè)計的要求結(jié)合起來，對各蟻群路由算法的特點進行了研究和總結(jié)，在此基礎(chǔ)上提出了一種改進的適用于無線傳感器網(wǎng)絡(luò)的蟻群路由協(xié)議，實驗表明它表現(xiàn)出了更好的性能。

1 蟻群路由算法簡介

Marco Dorigo等人在1998年提出了AntNet協(xié)議［12］，在AntNet協(xié)議中，每個節(jié)點維護一張路由表和另外一張附加的表，這張附加表中包含著網(wǎng)絡(luò)螞蟻流量分布的信息，記錄著螞蟻經(jīng)過的節(jié)點。在路由表的每條表項中，記錄著目標(biāo)節(jié)點地址和到達目標(biāo)節(jié)點地址的下一跳的啟發(fā)式信息值。但是AntNet蟻群路由算法是應(yīng)用在有線網(wǎng)絡(luò)中的，由于它所帶來的良好的網(wǎng)絡(luò)路由性能吸引了國內(nèi)外研究學(xué)者在AntNet基礎(chǔ)上進行了廣泛的研究，大多無線自織網(wǎng)絡(luò)中的蟻群路由算法都是在AntNet協(xié)議基礎(chǔ)上發(fā)展而來的。

Gunes等人提出的ARA(ant colony based routing algorithm)算法［13］是最早的將ACO算法應(yīng)用于移動自組織網(wǎng)絡(luò)的算法。在ARA中，路由表的每條表項也包含著用于計算選擇下一跳概率的信息素值，這個信息素的量隨著時間的流逝而逐漸揮發(fā)。路由表中的信息素值減小到一定的閾值以下后節(jié)點進入到休眠模式。在路由發(fā)現(xiàn)階段，ARA同樣使用前向螞蟻和后向螞蟻共兩種螞蟻來進行路由建立操作。ARA的路由維護過程不需要特殊的數(shù)據(jù)包，而是在數(shù)據(jù)傳輸過程中進行的。如果源節(jié)點收到一個路由失敗通知，它就重啟動一個路由發(fā)現(xiàn)過程。ARA的缺點是不適合大規(guī)模的網(wǎng)絡(luò)并且不提供回路檢測。

O.Hossein和T.Saadawi等人在2004年提出了ARAMA(ant routing algorithm for mobile ad hoc networks)協(xié)議［14］，它是一個主動式的路由協(xié)議。在其他的ACO路由協(xié)議中，前向螞蟻的主要任務(wù)是收集路徑信息。而在ARAMA中，前向螞蟻不僅關(guān)心跳數(shù)信息，還收集所經(jīng)過的路徑上的鏈路的信息比如節(jié)點能量和隊列延遲的大小等。ARAMA定義梯度(grade)的概念，這個值由后向螞蟻返回的途中進行計算并保存在節(jié)點中。后向螞蟻在返回源節(jié)點的過程中，使用梯度值對節(jié)點中的路由表進行更新，以一定的信息素更新策略對信息素進行更新。文章中作者指出，路由發(fā)現(xiàn)和維護的代價通過控制前向螞蟻的產(chǎn)生速率來減小，但并沒有指出在動態(tài)變化的拓撲環(huán)境中怎樣去控制這個數(shù)據(jù)產(chǎn)生速率。

Di Caro等人在2005年提出了AntHocNet協(xié)議［15］，這個協(xié)議結(jié)合了AntNet和ARA兩個協(xié)議的優(yōu)點，表現(xiàn)出更加優(yōu)秀的性能。在AntHocNet中，人工螞蟻維護著一個節(jié)點列表，記錄著它訪問過的所有節(jié)點。源節(jié)點發(fā)出前向螞蟻，如果一段時間后如果收到了所有后向螞蟻，則稱之為一個螞蟻路由周期結(jié)束。如果在計時期結(jié)束沒有收到后向螞蟻，節(jié)點向它所有的鄰居廣播鏈路失效信息，然后鄰居節(jié)點啟動按需路由發(fā)現(xiàn)過程。AntHocNet協(xié)議是一種混合式路由協(xié)議，但路由維護過程需要有大量的螞蟻，另外，每個節(jié)點保存著一張它所有可達目的節(jié)點的路由表，所以，對于規(guī)模大的網(wǎng)絡(luò)AntHocNet并不太適合。

Laura Rosati等人在2008年提出DAR(Distributed Ant Routing)協(xié)議［16］，它是一種按需的路由協(xié)議，相對于主動式路由，它可以減少路由時的網(wǎng)絡(luò)負載。前向螞蟻只負責(zé)收集關(guān)于交叉節(jié)點的ID信息，它在使用概率公式計算選擇下一跳節(jié)點的概率時只使用信息素值作為參數(shù)。而后向螞蟻在返回過程途中只釋放常量值的信息素值。在DAR中，每個路由節(jié)點中路由表都是隨機的:下一跳節(jié)點是依據(jù)概率值的大小進行選擇的。這個概率值是通過以前螞蟻走過時留下的信息素進行計算的。但是DAR算法要讓螞蟻記錄經(jīng)過的節(jié)點，不適用于大型網(wǎng)絡(luò)，同時也容易陷入局部最優(yōu)解，網(wǎng)絡(luò)的收斂速度也不快。

無線傳感器網(wǎng)絡(luò)路由設(shè)計的指標(biāo)之一就是盡可能的節(jié)省能量，延長網(wǎng)絡(luò)壽命。上述蟻群路由算法中，在帶有記憶功能的前向螞蟻中存儲著它訪問過的所有節(jié)點的ID值，而在大型的無線傳感器網(wǎng)絡(luò)中，節(jié)點數(shù)量往往是成千上萬甚至更多，導(dǎo)致螞蟻的記憶列表越來越長，螞蟻包的大小隨之增大，節(jié)點間傳輸螞蟻包帶來的能耗加劇，網(wǎng)絡(luò)壽命減少。文章［17］提出一種能量高效的蟻群路由協(xié)議EEABR協(xié)議，該算法的螞蟻包只保存兩個最近訪問記憶列表的ID值。同時在每個節(jié)點中增加一個記錄發(fā)送和接收螞蟻包的列表，每個記錄保存著螞蟻的上一跳節(jié)點，下一跳的轉(zhuǎn)發(fā)節(jié)點，螞蟻ID以及生存時間值。實驗證明，EEABR協(xié)議有效地減少了網(wǎng)絡(luò)中節(jié)點的能耗，延長了網(wǎng)絡(luò)的壽命，但是EEABR算法也存在著很多不足，包括螞蟻報文設(shè)計、螞蟻路徑概率選擇、信息素更新公式以及信息素揮發(fā)機制等方面都有可改進之處，本文在EEABR協(xié)議的基礎(chǔ)上進行研究并改進，提出了改進的基于蟻群算法的能量有效路由協(xié)議IEEABR。實驗證明該算法延長了網(wǎng)絡(luò)壽命和提高了能量有效性。

2 IEEABR路由協(xié)議

在EEABR協(xié)議的基礎(chǔ)上，針對該算法的前向和后向螞蟻包都用相同的數(shù)據(jù)結(jié)構(gòu)會帶來不必要的冗余問題，本文分開定義這兩種螞蟻包，這樣就能避免不必要的能量消耗。

前向螞蟻的數(shù)據(jù)包結(jié)構(gòu)如圖1所示。其中，hp_type是數(shù)據(jù)包類型，使用它來判斷是不是一只螞蟻包，pkt_src_是螞蟻產(chǎn)生的源地址，seqno代表著一個節(jié)點生成的前向螞蟻的序列號，螞蟻源地址與序列號的組合＜pkt_src_，seqno＞唯一標(biāo)識一只螞蟻，node_nbr是一個地址數(shù)組，用于記錄要發(fā)送前向螞蟻的當(dāng)前節(jié)點的所有鄰居地址，節(jié)點進行概率選擇下一跳時，把node_nbr作為禁忌表，這樣可以避免螞蟻走回頭路并且減少了環(huán)路出現(xiàn)的可能性。Esum是目前為止前向螞蟻走過的路徑上節(jié)點的消耗的能量值之和，Emin是目前為止前向螞蟻走過的路徑上節(jié)點的最小能量值，lenFromSrc指當(dāng)前螞蟻走過的路徑的長度，用節(jié)點跳數(shù)表示，TTL表示生存時間。

圖1 前向螞蟻數(shù)據(jù)包結(jié)構(gòu)

后向螞蟻的數(shù)據(jù)包結(jié)構(gòu)如圖2所示。其中，phe_value代表信息素更新值，由Sink節(jié)點計算并賦值，由后向螞蟻在返回過程中攜帶，用于信息素更新公式的計算。pkt_dst_表示此后向螞蟻要到達的目的節(jié)點，lenFromSrc代表著后向螞蟻離開Sink節(jié)點的路徑長度，從1開始累計。

圖2 后向螞蟻數(shù)據(jù)包結(jié)構(gòu)

由于螞蟻包不再記錄已訪問過的節(jié)點ID，這樣就需要在每個節(jié)點中建立一個螞蟻訪問列表，用于記錄訪問過該節(jié)點的螞蟻。在節(jié)點代理類IeeAbr中增加一個visitedAnts的鏈?zhǔn)筋惖闹羔?

LinkList*visitedAnts;

其中LinkList是一個鏈?zhǔn)筋?，它的類結(jié)構(gòu)如圖3所示。

圖3 LinkList類結(jié)構(gòu)圖

本文保留EEABR協(xié)議里的用于建立和維護鄰居關(guān)系的Hello包。這樣每個節(jié)點都必須保存一個鄰居表，用于記錄鄰居信息。

鄰居表項數(shù)據(jù)結(jié)構(gòu)如圖4所示。其中，nb_addr是鄰居節(jié)點的地址，energy是鄰居節(jié)點的剩余能量值，通過hello包來主動式的更新。pheromone值是當(dāng)前節(jié)點到此鄰居節(jié)點的鏈路上的信息素值，它的初始值我們定義為一個常量值STARTUP_PHEROMONE，在節(jié)點的代理類中，它是個靜態(tài)常量，值為1，隨著時間的推移，信息素會以一定的策略進行揮發(fā)。hops是從鄰居到達Sink節(jié)點的跳數(shù)值，初始為一個較大常量值BIG_CONSTANT_HOPS，本協(xié)議中定為9999，代表著這個鄰居還不能轉(zhuǎn)發(fā)數(shù)據(jù)包，我們定義鄰居表項中hops字段值小于BIG_CONSTANT_HOPS值的鄰居為有效鄰居，當(dāng)一個節(jié)點收到一只后向螞蟻時，則更新鄰居表中相應(yīng)hops的值。其中，last_update_time是最后一次更新這個表項的時間值。

圖4 鄰居表項結(jié)構(gòu)圖

在IEEABR協(xié)議中，如果中間節(jié)點r收到一只sant，如果這只螞蟻不在它的visitedAnts列表中，則這個節(jié)點按式(1)計算選擇下一跳的節(jié)點概率:

其中，Pk(r，s)是前向螞蟻k在傳輸?shù)倪^程中從節(jié)點r選擇移動到s節(jié)點的概率大小，τ(r，s)是存儲在節(jié)點r的路由表中的鏈路(r，s)上的信息素值的大小，η(s)是節(jié)點r到節(jié)點s的鏈路上啟發(fā)式信息，即人工螞蟻釋放的信息素濃度，Nr代表螞蟻包中的node_nbr節(jié)點地址數(shù)組，本文對η(s)的含義做了改進，如式(2)所示:

其中Einit為傳感器節(jié)點能量初始值，E(s)為節(jié)點s的剩余能量，Einit－E(s)是節(jié)點消耗的能量值。從公式可以看出節(jié)點能量消耗較小的鄰居節(jié)點更容易成為下一跳節(jié)點，有利于平衡網(wǎng)絡(luò)能量消耗，延長網(wǎng)絡(luò)壽命。

在EEABR協(xié)議中，前向螞蟻在從源節(jié)點到Sink節(jié)點的傳輸過程中，并沒有對路徑上的信息素進行更新，而Jing Yang等人［18］在研究中發(fā)現(xiàn)，如果前向螞蟻在每一跳轉(zhuǎn)發(fā)過程中也對鏈路的信息素進行更新，則會使算法的快速收斂取得更佳的效果。在本文的IEEABR協(xié)議中，前向螞蟻與后向螞蟻均按式(3)對鏈路上的信息素值進行更新:

其中ΔTk(r，s)對于前向螞蟻和后向螞蟻計算方法不同。對于前向螞蟻，它的任務(wù)主要是收集路徑上的信息，找到一條到達Sink節(jié)點的最佳路徑。在IEEABR協(xié)議中，前向螞蟻的ΔTk按式(4)進行計算:

其中Emin是前向螞蟻k從源節(jié)點到當(dāng)前節(jié)點所走過的路徑上的節(jié)點能量最小值，E(s)是鄰居節(jié)點s的剩余能量值，Eavg是螞蟻k從源節(jié)點到當(dāng)前節(jié)點所走過的路徑上的節(jié)點消耗能量的平均值，k1，k2，k3分別代表以上三部分能量的權(quán)值，從式(4)中看出，前向螞蟻k在具有能量瓶頸的路徑上釋放的信息素較少，并且在計算時考慮到了當(dāng)前鄰居的節(jié)點能量值大小，以引導(dǎo)后來的螞蟻將能量較大的鄰居作為下一跳，同時還從全局的角度考慮了螞蟻搜尋路徑上能量消耗情況，從算法的整體性能上來看，它有利于均衡網(wǎng)絡(luò)能量消耗，延長網(wǎng)絡(luò)平均壽命。對于后向螞蟻，ΔTk(r，s)按式(5)進行信息素的更新:

其中Bdk是后向螞蟻k經(jīng)過的路徑長度，用節(jié)點跳數(shù)來表示。k4，k5系數(shù)，代表E(s)與Bdk的權(quán)值，反映這兩個變量的相對重要性。ΔTk參考［17］，由Sink進行計算，ΔTk的計算如式(6)所示:

其中Einit為節(jié)點能量初始值，F(xiàn)dk代表前向螞蟻所訪問的節(jié)點數(shù)。每當(dāng)Sink收到一只前向螞蟻時就計算此值并放到相應(yīng)的新生成的后向螞蟻的phe_value字段中。

最后Sink節(jié)點釋放前向螞蟻并把后向螞蟻發(fā)送給源節(jié)點。后向螞蟻在返回的途中，按式(3)和式(5)對所經(jīng)過的每個節(jié)點進行信息素的更新。后向螞蟻在返回過程中，不僅考慮到路徑長度，還考慮到當(dāng)前下一跳鄰居的能量值。對于離Sink節(jié)點較近的節(jié)點，后向螞蟻在其鄰居的鏈路上釋放較多的信息素，可以加速蟻群算法的收斂。同樣，當(dāng)前鄰居節(jié)點能量的因素可以平衡網(wǎng)絡(luò)消量消耗，避免能量較小的節(jié)點由于過多的轉(zhuǎn)發(fā)螞蟻而導(dǎo)致快速死亡，可以有效延長傳感器網(wǎng)絡(luò)的平均壽命。

3 IEEABR路由算法流程

IEEABR算法在EEABR算法上做了較大的改動，算法的具體過程可以描述為:

(1)在協(xié)議運行初始階段，先進行hello包的廣播，建立起節(jié)點與其鄰居的之間一個相互關(guān)系，初始時每個具有鄰居關(guān)系的鏈路上的信息素設(shè)置為1;

(2)對于每一個非Sink節(jié)點生成各自的第一只前向螞蟻并選擇按概率選擇公式下一跳進行發(fā)送，各個節(jié)點上螞蟻生成的獨立且同步進行的，每只螞蟻的生成時間都由隨機數(shù)生成器來控制;

(3)每個中間節(jié)點收到IEEABR數(shù)據(jù)包之后進行判斷，報文類型有三種，分別是IeeAbrTYPE_HELLO、IeeAbrTYPE_SANT和IeeAbrTYPE_BANT;

(4)如果是類型IeeAbrTYPE_HELLO，則表明這是鄰居發(fā)來的信息，先判斷當(dāng)前節(jié)點是否已經(jīng)有當(dāng)前鄰居的信息，如果沒有，將此鄰居信息加入鄰居表，否則對鄰居表項內(nèi)容進行更新處理;

(5)如果節(jié)點收到一只前向螞蟻，即類型Iee-AbrTYPE_SANT，節(jié)點判斷是否達到Sink節(jié)點，如果已到達Sink節(jié)點，則生成后向螞蟻并讓前向螞蟻死亡，如果沒有到達Sink節(jié)點，說明當(dāng)前節(jié)點是中間節(jié)點，此前向螞蟻需要進行下一跳的轉(zhuǎn)發(fā)。如果TTL的生命期還沒到，則隨機生成一個0到1間數(shù)，如果小于0.001，則從有效鄰居中均等概率隨機選擇下一跳進行轉(zhuǎn)發(fā)，否則按式(1)計算概率選擇下一跳鄰居節(jié)點。然后對前向螞蟻各字段的信息進行更新并將它加入到當(dāng)前節(jié)點的螞蟻訪問列表，根據(jù)式(3)和式(4)對鄰居表信息素進行更新，轉(zhuǎn)發(fā)前向螞蟻，轉(zhuǎn)到步驟(3);

(6)前向螞蟻到達Sink節(jié)點后生成相應(yīng)的后向螞蟻并死亡。節(jié)點收到一只后向螞蟻，即類型為Iee-AbrTYPE_BANT，首先判斷是否到達源節(jié)點，如果沒有到達源節(jié)點，則更新后向螞蟻信息，并按式(3)和式(5)對鏈路信息素進行更新，按記錄下的前向螞蟻的反向路徑轉(zhuǎn)發(fā)到下一跳，然后刪除鄰居表中相應(yīng)前向螞蟻的記錄，轉(zhuǎn)到步驟(3)。如果回到源節(jié)點，則表示螞蟻已經(jīng)成功找到一條從源節(jié)點到目的Sink節(jié)點的一條路徑，從節(jié)點的螞蟻訪問列表中刪除相應(yīng)前向螞蟻的記錄，后向螞蟻死亡，轉(zhuǎn)步驟(7)。

(7)節(jié)點判斷是否發(fā)送前向螞蟻，如果是，則轉(zhuǎn)向步驟(2)，否則結(jié)束。

4 改進的IEEABR路由算法仿真實驗

4.1 IEEABR協(xié)議在NS2環(huán)境下的添加

本實驗搭建環(huán)境是WindowsXP SP2+cygwin+NS2.29，改進的IEEABR協(xié)議源代碼是用C++實現(xiàn)的，包括:

將 ieeabr文件夾拷貝到 ～ /ns－allinone－2.29/ns－2.29目錄下。然后修改相應(yīng)的文件:

完成后，打開 cygwin，進入到 ns－allinone－2.29 s－2.29目錄下，依次運行 touch common/packet.cc和make兩個命令，上文所有添加或修改過的.cc文件都將會被重新編譯。編譯成功結(jié)束后IEEABR協(xié)議就添加到了NS2里。EEABR源代碼的添加方法類似。

4.2 IEEABR協(xié)議的仿真實驗

本實驗對IEEABR與EEABR這兩個協(xié)議的性能進行了仿真實驗對比，節(jié)點的通信半徑為20m，基站位置為(0，0)，其他節(jié)點位置隨機播撒，節(jié)點數(shù)目和場景區(qū)域大小將隨不同的實驗而變化。本文使用First-order Radio Model［19］能量傳輸模型，發(fā)送功率txPower為0.7W，接收功率 rxPower為 0.4W，設(shè)置發(fā)送和接收電路工作時消耗的能量Eelec為50nJ/bit，設(shè)置放大器工作時消耗的能量εamp為10pJ/bit/m2，數(shù)據(jù)融合時電路的功耗為5nJ/bit。節(jié)點初始能量為2J，為保證仿真過程的順利進行，我們將基站的能量單獨設(shè)為100J。數(shù)據(jù)流使用CBR流，數(shù)據(jù)包大小為256Byte，使用cbrgen工具生成數(shù)據(jù)流文件，仿真時間為200s。使用gnuplot工具進行畫圖。

(1)網(wǎng)絡(luò)能量消耗

網(wǎng)絡(luò)生存時間的長短與網(wǎng)絡(luò)消耗的總能量成反比，消耗越少的能量其網(wǎng)絡(luò)生存的時間就越長。網(wǎng)絡(luò)消耗的總能耗又與每個節(jié)點的平均能耗息息相關(guān)。

本文定義節(jié)點平均能量消耗為模擬時間之內(nèi)消耗能量總量與節(jié)點數(shù)目之比，這里進行兩組實驗，第一組實驗場景按100～500不同節(jié)點數(shù)目進行比較，節(jié)點數(shù)目從100～500每次增加100個節(jié)點，網(wǎng)絡(luò)節(jié)點隨機安置在800 m×600 m的矩形區(qū)域內(nèi)，節(jié)點部署好之后靜止或作小量移動。為了減小隨機性帶來的影響，不同節(jié)點數(shù)目場景下分別進行50次實驗并取平均值，實驗結(jié)果如圖5所示。第二組實驗查看節(jié)點平均能耗隨時間上升的情況，選取300個節(jié)點的網(wǎng)絡(luò)，在場景大小為600 m×600 m的正方形區(qū)域中隨機部署進行仿真實驗，所有節(jié)點都是靜止。實驗重復(fù)進行50次并取平均值，節(jié)點平均能耗隨時間變化的實驗結(jié)果如圖6所示。

圖5 節(jié)點平均能耗隨節(jié)點數(shù)量變化圖

圖6 節(jié)點平均能耗隨仿真時間變化圖

從圖5可以很明顯地看出，IEEABR協(xié)議比EEABR協(xié)議在單個節(jié)點平均能耗上性能有了較大的提高。特別地，當(dāng)節(jié)點數(shù)目為300時，模擬時間結(jié)束后IEEABR協(xié)議的節(jié)點平均能耗比EEABR減少近26%。圖6中，時間小于50s時，EEABR的節(jié)點平均能量消耗小于IEEABR協(xié)議，這是可以理解的，因為IEEABR的前向螞蟻攜帶著節(jié)點的鄰居表，在開始階段收發(fā)前向螞蟻報文的開銷比EEABR協(xié)議要大，但隨著時間的進行，模擬時間大于60之后，EEABR的節(jié)點平均能耗增長速度明顯大于IEEABR協(xié)議，這是因為，IEEABR協(xié)議的每只前向螞蟻攜帶了上一跳節(jié)點的所有鄰居節(jié)點，選擇下一跳時避免選擇兩個節(jié)點生命的鄰居部分，這樣就一定程度上避免了路由環(huán)路的發(fā)生，同時驅(qū)使前向螞蟻向更遠的地方搜索，快速找到Sink節(jié)點，增加了算法的收斂速度，從而減少了網(wǎng)絡(luò)中的前向螞蟻的數(shù)量，所以節(jié)點平均能量消耗相對較小。

(2)能量有效性

本文中，能量有效性定義為從開始到模擬完成之后這段時間里Sink節(jié)點接收到的數(shù)據(jù)包總數(shù)與能量消耗總量的比值。能量有效性也是評價協(xié)議性能的重要指標(biāo)之一，為了對比 IEEABR協(xié)議和EEABR協(xié)議的能量有效性，實驗場景選取傳感器節(jié)點為100～500的網(wǎng)絡(luò)，每次節(jié)點增加100，節(jié)點隨機放置在800m*600m的矩形區(qū)域內(nèi)，仿真時間為200s，其他場景設(shè)置和參數(shù)與上文描述相同。每次實驗重復(fù)50次并取平均值，實驗結(jié)果如圖7所示。

圖7 能量有效性隨節(jié)點數(shù)目變化圖

從圖7中可以看出，IEEABR協(xié)議在節(jié)點數(shù)目不同情況的能量有效性均高于EEABR，特別地，在節(jié)點數(shù)目為200時，IEEABR協(xié)議的能量有效性比EEABR提高近28%。這是因為，EEABR協(xié)議在前向螞蟻搜尋路徑過程中出現(xiàn)環(huán)路的可能性遠高于IEEABR，由于環(huán)路時螞蟻就會被丟棄，導(dǎo)致節(jié)點需要發(fā)送更多的螞蟻去獲得最優(yōu)路徑，降低了搜索的效率，并且導(dǎo)致能量消耗增加。盡管IEEABR協(xié)議的前向螞蟻多加了一個鄰居表地址數(shù)組node_nbr，但從網(wǎng)絡(luò)整體能量消耗的有效性而言，IEEABR協(xié)議比EEABR協(xié)議更優(yōu)。另外，隨著網(wǎng)絡(luò)規(guī)模的擴大，兩個算法的能量有效性都在逐漸增加，當(dāng)在節(jié)點數(shù)目為300時，兩個算法的能量有效性都高于20%。這是因為，隨著網(wǎng)絡(luò)規(guī)模的擴大，節(jié)點密度增加，節(jié)點通信距離減小，節(jié)點間通信消耗的能量也隨之減少，所以能量消耗有效性增加。

(3)網(wǎng)絡(luò)生存時間

本文中，為了對比IEEABR和EEABR協(xié)議的網(wǎng)絡(luò)生命時間，我們進行了兩組實驗，分別采用第一個節(jié)點死亡時間和網(wǎng)絡(luò)生存節(jié)點個數(shù)作為網(wǎng)絡(luò)壽命的評價指標(biāo)進行考察對比。第一組實驗選取節(jié)點數(shù)目為100～500個節(jié)點的網(wǎng)絡(luò)，每次增加100個節(jié)點，在范圍800 m×600 m的矩形區(qū)域內(nèi)，所有節(jié)點都靜止。同樣地，不同節(jié)點數(shù)目的實驗各進行50次，最后取平均值。第一個節(jié)點死亡時間隨節(jié)點數(shù)目變化的情況如圖8所示。第二組實驗選取300個節(jié)點的網(wǎng)絡(luò)，傳感器節(jié)點隨機安置在一個800 m×600 m的矩形區(qū)域內(nèi)，網(wǎng)絡(luò)部署好之后所有節(jié)點都是靜止的，實驗重復(fù)進行50次，并取平均值。網(wǎng)絡(luò)生存節(jié)點個數(shù)隨模擬時間的變化情況如圖9所示。

圖8 第一個節(jié)點死亡時間隨節(jié)點數(shù)目變化圖

圖9 網(wǎng)絡(luò)生存節(jié)點個數(shù)隨時間變化圖

圖8很明顯地反映出在仿真過程中，IEEABR協(xié)議第一個節(jié)點的死亡時間要比EEABR晚。并且從圖中還可以看出，兩個算法在網(wǎng)絡(luò)規(guī)模小于300個節(jié)點的時候，隨著網(wǎng)絡(luò)規(guī)模的增加，網(wǎng)絡(luò)壽命都相應(yīng)延長，而在網(wǎng)絡(luò)結(jié)點個數(shù)大于300的時候，網(wǎng)絡(luò)壽命都相應(yīng)地減少。這是可以理解的，因為網(wǎng)絡(luò)規(guī)模過小，傳感器節(jié)點間的距離增加，數(shù)據(jù)傳輸所耗費的能量增加，網(wǎng)絡(luò)壽命減少。而如果網(wǎng)絡(luò)規(guī)模過大，則螞蟻找到一條源節(jié)點到Sink節(jié)點間路徑的時間增加，導(dǎo)致算法收斂速度減小，能耗隨之增加，同時節(jié)點密度增加后，廣播hello包的數(shù)量也增加，網(wǎng)絡(luò)能耗增加，網(wǎng)絡(luò)壽命減小。從圖9中可以看出，從開始到100 s時刻的這段時間里，IEEABR協(xié)議沒有節(jié)點死亡，而EEABR協(xié)議從70 s開始有節(jié)點持續(xù)死亡。IEEABR在時間170 s之后死亡節(jié)點將逐漸減少，生存節(jié)點總數(shù)基本維持在250個左右，而EEABR節(jié)點時間進行到170 s之后，生存節(jié)點個數(shù)將維持在240個左右。

5 結(jié)論

本文在大量研究無線傳感器網(wǎng)絡(luò)路由協(xié)議特點及蟻群算法理論的基礎(chǔ)上，對Carreto C.等提出的能量有效的蟻群路由算法(EEABR)進行了研究分析。針對EEABR協(xié)議在螞蟻報文設(shè)計、概率選擇及信息素更新等方面存在的不足，本文提出了基于EEABR的改進的能量有效的蟻群路由算法(IEEABR)。為了驗證改進算法是否適應(yīng)課題的要求，使用NS2開源軟件平臺對IEEABR和EEABR協(xié)議進行了仿真實驗，并做了大量的實驗比較和分析。經(jīng)過多組仿真實驗和分析，可以看出，無線傳感器網(wǎng)絡(luò)中采用改進的蟻群路由算法IEEABR協(xié)議，相比改進前的EEABR路由協(xié)議，網(wǎng)絡(luò)的性能有了很大的改善。

本文改進蟻群路由算法具有能量高效、網(wǎng)絡(luò)負載均衡，魯棒性，正反饋性和分布式計算等優(yōu)點，已經(jīng)顯示出它在無線傳感器網(wǎng)絡(luò)路由方面的優(yōu)勢。

［1］Akyildiz Lf，Su W l，Sankarasubramaniam Y，et al.A Survey on Sensor Networks［J］.IEEE Communications Magazine，2002，40(8):102－114.

［2］Dorigo M，Birattari M，Stutzle T.Ant Colony Optimization:Artificial Ants as a Computational Intelligence Technique［J］.IEEE Computational Intelligence Magazine，2006，1(40):28－39.

［3］Blum C.Ant Colony Optimization:Introduction and Recent Trends［J］.Physics of Life Reviews，2005，2(4):353－373.

［4］Di Caro G，Dorigo M.AntNet:Distributed Stigmergetic Control for Communication Networks［J］.Journal of Artificial Intelligence Research，1998，9(1):317－365.

［5］耶剛強，梁彥，孫世宇.基于蟻群的無線傳感器網(wǎng)絡(luò)路由算法［J］.計算機應(yīng)用研究，2008，25(3):715－717.

［6］梁華為，陳萬明，李帥.一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法［J］.傳感技術(shù)學(xué)報，2007，20(11):2450－2455.

［7］黃如，苗澎，陳志華.基于預(yù)測模式蟻群優(yōu)化的傳感網(wǎng)節(jié)能路由機制［J］.傳感技術(shù)學(xué)報，2010，23(5):701－707.

［8］Di Caro，Ducatelle F，Gambardella L.AntHocNet:An Adaptive Nature-Inspired Algorithm for Routing in Mobile Ad Hoc Networks［M］.European Transactions on Telecommunnications，2005，16(5):443－455.

［9］Hussein O H，Saadawi M J，Lee M.Ant Routing Algorithm for Mobile Ad Hoc Networks(ARAMA)［J］.Phoenix，Arizona，2004:15－17.

［10］Rajagopalan S，Shen C.ASNI:A Unicast Routing Protocol for Mobile Ad Hoc Networks Using Swarm Intelligence［C］//Proceedings of the International Conference on Artificial Intelligence，Italy，2005:24－27.

［11］Mesut Gunes，Udo Sorges，Imed Bouazizi.ARA:The Ant-Colony Based Routing Algorithm for MANETs［C］//Proceedings fo the 2002 International Conference on Parallel Processing Workshops，Aachen，2002:79－85.

［12］Di Caro G，Dorigo M.AntNet:Distributed Stigmergetic Control for Communication Networks［J］.Journal of Artificial Intelligence Research，1998，9(1):317－365.

［13］Mesut Gunes，Udo Sorges，Imed Bouazizi.ARA:The Ant-Colony Based Routing Algorithm for MANETs［C］//Proceedings fo the 2002 International Conference on Parallel Processing Workshops，Aachen，2002:79－85.

［14］Hussein O H，Saadawi M J，Lee M.Ant Routing Algorithm for Mobile Ad Hoc Networks(ARAMA)［J］.Phoenix，Arizona，2004:15－17.

［15］Di Caro，Ducatelle F，Gambardella L.AntHocNet:An Adaptive Nature-Inspired Algorithm for Routing in Mobile Ad Hoc Networks［M］.European Transactions on Telecommunnications，2005，16(5):443－455.

［16］Laura R，Matteo B，Cgianluca.On Ant Routing Algorithms in Ad Hoc Networks with Critical Connectivity［R］.Ad Hoc Network Journal，2008，6(6):827－859.

［17］Camilo T，Carreto C，Silva J S，et al.An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks［C］//Proceedings of ANTS 2006－the 5th International Workshop on Ant Colony Optimization and Swarm Intelligence，Brusels，Belgium，2006:49－59.

［18］Yang J，Xu M，Zhao W.A Multipath Routing Protocol Based on Clustering and Ant Colony Optimization for Wireless Sensor Networks［Z］.SENSORS，2010，10(5):4521－4540.

［19］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Sensor Networks［J］.Proc of Hawaii International Conference on System Sciences，Washington DC，2000:175－187.