摘 要： 提出一種基于蟻群算法的無線傳感器網(wǎng)絡(luò)按需多路節(jié)能路由算法。該算法綜合了蟻群優(yōu)化算法和AODV路由協(xié)議的思想,，通過螞蟻并行地在源節(jié)點和目的節(jié)點之間建立多路徑路由,，提高了網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膶崟r性、延長了整個網(wǎng)絡(luò)的生命期,。仿真結(jié)果表明,，該算法與多種群蟻群優(yōu)化路由算法,、基本蟻群算法相比，在整個網(wǎng)絡(luò)的生命期和節(jié)能方面效果顯著,。
關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò),；路由；蟻群算法,；多路節(jié)能
隨著無線通信技術(shù),、電子技術(shù)、傳感器技術(shù)和微電系統(tǒng)的飛速發(fā)展,，無線傳感器網(wǎng)絡(luò)的研究越來越受到人們的重視,。傳感器網(wǎng)絡(luò)是由部署在觀測環(huán)境內(nèi)的大量微型傳感器節(jié)點通過無線通信方式組成的一種無線網(wǎng)絡(luò)。組成傳感器網(wǎng)絡(luò)的節(jié)點包括傳感器和匯聚節(jié)點(Sink),。傳感器節(jié)點的能量十分有限,，并且在部署后難以再次補(bǔ)充能量，因此傳感器網(wǎng)絡(luò)存在嚴(yán)重的能量約束問題[1],。
參考文獻(xiàn)[2]提出一種無線傳感器網(wǎng)絡(luò)AODV(Ad hoc On-Dernand Distance Vector)路由協(xié)議改進(jìn)方案,，通過改進(jìn)RREQ協(xié)議幀，使節(jié)點的剩余能量值參與到路徑中,，優(yōu)化RREQ洪泛傳播,。但該算法是基于單路徑數(shù)據(jù)傳輸，沒有考慮節(jié)點的負(fù)載狀況,，節(jié)點容易產(chǎn)生擁塞,，導(dǎo)致數(shù)據(jù)包的重傳或數(shù)據(jù)丟失的情況。參考文獻(xiàn)[3]提出了一種基于蟻群優(yōu)化的路由算法ARAWSN(ACO-Based Routing Algorithm for Wireless Sensor Networks),，該算法在定向擴(kuò)散協(xié)議的基礎(chǔ)上,，通過搜尋螞蟻以廣播的方式在網(wǎng)絡(luò)中擴(kuò)散建立起源節(jié)點到目的節(jié)點的多條路徑的路由表。利用蟻群算法的轉(zhuǎn)移概率的方式來進(jìn)行路徑的選擇,，從而平衡網(wǎng)絡(luò)中節(jié)點能量的消耗。該算法建立了所有到目的節(jié)點的路徑,，存在很大的冗余,，影響網(wǎng)絡(luò)的實時性，且在路由建立過程中采用洪泛的方式導(dǎo)致網(wǎng)絡(luò)的路由開銷比較大,。參考文獻(xiàn)[4]綜合考慮了均衡傳輸能量消耗和節(jié)點剩余能量,，提出了多種群蟻群優(yōu)化路由算法MACO(Multi Ant Colony Optimization)。該算法優(yōu)化了基本蟻群算法的螞蟻前向移動的選擇概率模型,，同時利用多種群獲得多條優(yōu)化路徑,。但該算法需要進(jìn)行多次迭代，且可能陷入局部最優(yōu)解,，影響網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膶崟r性,。
針對上述路由算法及其存在的不足,，本文提出了基于蟻群算法的無線傳感器網(wǎng)絡(luò)按需多路節(jié)能路由算法MP-ACA(On-demand Multi-path and Power-saving Ant Colony Algorithm)。該算法結(jié)合蟻群算法和AODV路由協(xié)議,，能夠在源節(jié)點和目的節(jié)點之間建立起多條鏈路不相關(guān)路由,，并改善了蟻群算法在無線傳感器網(wǎng)絡(luò)中查找路由的多次迭代的策略，有效地減少了擁塞頻率,、降低了路由的開銷,，同時均衡了節(jié)點的能量開銷，延長了網(wǎng)絡(luò)的生命周期,。
1 蟻群算法簡介
1.1 基本蟻群算法原理
蟻群算法[5]ACA(Ant Colony Algorithm)是一種模擬昆蟲王國中螞蟻群體智能行為的仿生優(yōu)化算法,，其基本原理可大致描述如下:自然界螞蟻會在所經(jīng)過的路徑上釋放一定的信息素，后來的螞蟻會根據(jù)信息素強(qiáng)度來選擇路徑,，信息素強(qiáng)度越大的路徑被選擇的概率越大,，于是就形成了一種正反饋機(jī)制，最終螞蟻會選擇信息素最大的最短路徑,。蟻群算法通過釋放“人工螞蟻”來模擬自然螞蟻的行為以完成上述的選優(yōu)過程,。
1.2 蟻群算法
根據(jù)螞蟻覓食的基本原理，科學(xué)家們設(shè)計了尋找最優(yōu)路徑的蟻群算法,，其主要步驟為：
2 按需多路節(jié)能路由算法設(shè)計
針對無線傳感器網(wǎng)絡(luò)數(shù)據(jù)多跳傳輸,、節(jié)點能量有限等特性，本文對基本蟻群算法和MACO算法進(jìn)行改進(jìn),，并結(jié)合AODV路由協(xié)議,，賦予螞蟻新的特性和路徑搜索方式。下面介紹本文研究中使用的相關(guān)定義,。
定義1：從源節(jié)點到目的節(jié)點的路徑搜索螞蟻稱作前向螞蟻,，它執(zhí)行路徑搜索功能，并建立反向信息素表,。
定義2：前向螞蟻到達(dá)目的節(jié)點后,，從目的節(jié)點返回到源節(jié)點的螞蟻稱作后向螞蟻，它執(zhí)行信息素更新功能,，并建立路由表,。
定義3：前向螞蟻在路徑搜索過程中，到達(dá)某一節(jié)點后建立的指向源節(jié)點的路由表稱作反向信息素表,，該表包括源節(jié)點,、下一個節(jié)點、反向節(jié)點信息素τ(j,，i),。
2.1 算法設(shè)計思想
MP-ACA算法在Ant-Net算法[6]的基礎(chǔ)上，將螞蟻分為前向螞蟻和后向螞蟻。為了實現(xiàn)不同節(jié)點的能量消耗均衡,，MP-ACA算法中,，將前向螞蟻要訪問的節(jié)點的剩余能量作為影響信息素濃度的一個參數(shù),。MP-ACA算法通過m只前向螞蟻同時獨(dú)立地進(jìn)行路徑搜索,，并建立反向信息素表。當(dāng)每個前向螞蟻到達(dá)目的節(jié)點時,，它們將立即轉(zhuǎn)化成一個后向螞蟻,，后向螞蟻根據(jù)反向信息素表反向回到源節(jié)點后一次路由建立完畢,，建立起信息素路由表以代替?zhèn)鹘y(tǒng)的網(wǎng)絡(luò)節(jié)點路由表，并采用一種新的信息素規(guī)則進(jìn)行信息素更新,。同時MP-ACA算法在極大-極小蟻群算法[7]上將各條路徑上的信息素濃度限制在[τmin,，τmax]之間，τmin可以有效地避免算法停滯,，τmax避免某條路徑上的信息素遠(yuǎn)大于其他路徑,，使所有的螞蟻都集中到同一條路徑上面，限制算法的擴(kuò)散,。在MP-ACA算法中,，前向螞蟻轉(zhuǎn)移規(guī)則、信息素更新規(guī)則詳細(xì)設(shè)計如下,。
2.2 前向螞蟻轉(zhuǎn)移規(guī)則
為了均衡網(wǎng)絡(luò)中節(jié)點的能量消耗,，MP-ACA算法在蟻群算法的基礎(chǔ)上，新加入兩節(jié)點間的剩余能量因子改進(jìn)前向螞蟻轉(zhuǎn)移規(guī)則,。改進(jìn)后的算法在螞蟻尋找最短路徑的同時受到了節(jié)點能量消耗的限制,。MP-ACA算法中處于節(jié)點i的螞蟻k選擇下一節(jié)點j進(jìn)行訪問的概率pkij使用以下公式確定：
式中，W( j)是節(jié)點j的剩余能量,；JK(i)代表了位于節(jié)點i的前向螞蟻k允許訪問的鄰居節(jié)點集合,。在這里定義滿足以下兩個要求的節(jié)點j將會屬于JK(i):(1)節(jié)點j還未被螞蟻k訪問；(2)節(jié)點j比前一節(jié)點i距離目的節(jié)點更近,，且距離源節(jié)點更遠(yuǎn),。
MP-ACA算法采用改進(jìn)的轉(zhuǎn)移規(guī)則，簡化了MACO算法使得MP-ACA更適用于無線傳感器網(wǎng)絡(luò),。同時前向螞蟻在尋找路徑的同時受到了節(jié)點能量消耗的限制,，平衡了節(jié)點的能量消耗。
2.3 信息素更新規(guī)則
如果節(jié)點i,，j是前向螞蟻k選擇路徑上的相鄰節(jié)點，當(dāng)每個前向螞蟻到達(dá)目的節(jié)點時,，它們將通過式(5),、式(6)來調(diào)節(jié)。對前向螞蟻到達(dá)目的節(jié)點后立即轉(zhuǎn)化成一個后向螞蟻,，并且它將沿著反向信息素表回到源節(jié)點,。中間節(jié)點收到后向螞蟻時,，將按照式(5)、式(7)更新相鄰節(jié)點信息素強(qiáng)度,。
MP-ACA算法改進(jìn)了MACO算法信息素更新規(guī)則,，可以加快搜索路徑的速度，提高網(wǎng)絡(luò)數(shù)據(jù)傳輸?shù)膶崟r性,，同時更進(jìn)一步平衡了網(wǎng)絡(luò)節(jié)點的能量消耗,。
2.4 MP-ACA算法步驟
(1)初始化時，Sink節(jié)點跳數(shù)設(shè)置為0,，其他節(jié)點跳數(shù)設(shè)置為100,。Sink節(jié)點在全網(wǎng)范圍內(nèi)廣播跳數(shù)廣播報文，該報文包括數(shù)據(jù)包類型,、距Sink節(jié)點跳數(shù),、剩余能量和源地址。該報文初始值為：跳數(shù)為0,，源地址為0,。中間節(jié)點收到該報文后，保存報文中節(jié)點的地址,、跳數(shù)和能量狀態(tài),。如果收到的報文中跳數(shù)小于節(jié)點自身的跳數(shù)，則將自身的跳數(shù)設(shè)置為報文中的跳數(shù)加1,，并轉(zhuǎn)發(fā)自己新的跳數(shù)信息和能量信息的報文,，否則不廣播。 節(jié)點在轉(zhuǎn)發(fā)該報文的過程中收集,、存儲鄰居節(jié)點相關(guān)信息,，最終在全網(wǎng)內(nèi)建立了到Sink節(jié)點的跳數(shù)信息。
(2)路徑搜索初始時,，賦予每條路徑上相等數(shù)量的初始信息素τ0,，本文設(shè)置為信息素濃度下限τmin。
(3)路徑搜索開始時,，m只前向螞蟻從源節(jié)點S處出發(fā),，前向螞蟻所要攜帶的信息有:源節(jié)點ID號、目的節(jié)點ID號,、節(jié)點i到節(jié)點j的信息素強(qiáng)度τ(i,，j)、經(jīng)過節(jié)點的剩余能量的總和以及當(dāng)前總跳數(shù),。
(4)位于節(jié)點i的前向螞蟻k,，依據(jù)轉(zhuǎn)移規(guī)則從相鄰的下一跳節(jié)點集合中選擇一個節(jié)點，并根據(jù)式(5)、式(6)更新路徑上信息素強(qiáng)度,。
(5)當(dāng)中間節(jié)點j收到來自鄰居節(jié)點的螞蟻節(jié)點時：①更新前向螞蟻搜索包跳數(shù)h(i)=h(i)+1,，i∈[1，m],。如果前向螞蟻沒有到達(dá)目的節(jié)點,，且h<hmax，則轉(zhuǎn)入下一步,，否則丟棄該數(shù)據(jù)包,；②檢查自己是否比節(jié)點i距離目的節(jié)點更近，且距離源節(jié)點更遠(yuǎn),。若是,，轉(zhuǎn)入下一步，否則簡單丟棄,；③然后檢查是否已收到同一目的節(jié)點前向螞蟻搜索包,。若是，則此節(jié)點只接收最早到達(dá)而且信息素最大的前向螞蟻搜索包,，將其余的丟棄,。當(dāng)前向螞蟻從節(jié)點i到達(dá)節(jié)點j后，根據(jù)前向螞蟻所攜帶的信息值建立到源節(jié)點的反向點信息素表,，跳轉(zhuǎn)到第(4)步,。
(6)當(dāng)每個前向螞蟻到達(dá)目的節(jié)點時，它們將立即轉(zhuǎn)化成一個后向螞蟻,，并且它將沿著反向信息素表回到源節(jié)點,。中間節(jié)點收到后向螞蟻數(shù)據(jù)包時，按照式(5),、式(7)將更新相鄰節(jié)點信息素強(qiáng)度,，并建立到目的節(jié)點的路由表，路由表是一個三元組包括：目的節(jié)點,、下一個節(jié)點,、信息素。
(7)后向螞蟻到達(dá)源節(jié)點后路由建立完畢,。
2.5 網(wǎng)絡(luò)的維護(hù)
在無線傳感器網(wǎng)絡(luò)中,，節(jié)點的故障和能量的耗盡都將導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化，這使得路由維護(hù)顯得十分重要,。路由斷路和節(jié)點能量的消耗是路由維護(hù)中必須解決的兩個關(guān)鍵問題,。
(1)路由斷路。當(dāng)中間節(jié)點發(fā)現(xiàn)路徑不通或收到路由斷路的消息后,，它首先根據(jù)斷路的路徑信息刪除自己對應(yīng)的路由表條目,，然后查詢可能性路由表條目,，看是否能找到到達(dá)同一目的地的其他路徑,。如果有,，則根據(jù)路由表中信息素最大的條目作為最優(yōu)的路徑進(jìn)行通信；如果沒有到達(dá)對應(yīng)目的地的可選路徑后,，即向其他節(jié)點繼續(xù)發(fā)送路由斷路消息,。當(dāng)源節(jié)點在通信完成前收到路由斷路消息后，如果沒有到目的地的其他路徑,，則將發(fā)起新的路徑探索過程,，直到通信完成。
(2)節(jié)點能量的消耗,。為了不頻繁地重建路由表,，節(jié)省能量，MP-ACA算法根據(jù)每個節(jié)電的剩余能量自動更新路由表,，這樣就使得節(jié)點的能耗盡可能保持平衡,。節(jié)點能量每下降10%，節(jié)點就會向周圍節(jié)點廣播自己的剩余能量,，收到廣播的節(jié)點用式(8)更新路由表：
為了分析改進(jìn)方案的性能,，這里選用了以下2個典型參數(shù):(1)接收到數(shù)據(jù)包的平均時延(End to End Average Delay)，單位為s,；(2)能量不為零的節(jié)點數(shù)目(Number of Nodes),。
3.1 接收到數(shù)據(jù)包的平均延時
圖1反映了三種算法網(wǎng)絡(luò)傳輸數(shù)據(jù)的平均傳輸延時隨時間的變化關(guān)系。由圖可知,，各算法的時延呈現(xiàn)先降后增的趨勢,，主要是由于網(wǎng)絡(luò)剛建立時，節(jié)點需要建立路由表,，然后時延呈下降趨勢,。網(wǎng)絡(luò)運(yùn)行一段時間后，由于網(wǎng)絡(luò)中部分節(jié)點死亡,，導(dǎo)致路由的重建,，致使時延呈上升趨勢?？偟膩碚f,，MP-ACA的平均傳輸延時要小于MACO和ACA的平均傳輸延遲，主要是因為在MACO和ACA其路由是通過多次迭代而建立起來的,，需要的時間長,，從而增加了網(wǎng)絡(luò)延時。
3.2 能量不為零的節(jié)點數(shù)目
圖2反映了三種算法在整個網(wǎng)絡(luò)時間內(nèi)能量不為零的節(jié)點數(shù)目隨時間的變化關(guān)系,。由圖可知,，節(jié)點一直運(yùn)行到110 s的時候,，三種算法下有效的節(jié)點數(shù)目都為總的節(jié)點數(shù)目，但隨著時間的推移,，由于ACA算法沒有考慮到節(jié)點剩余能量的情況,，造成了某些節(jié)點耗能不均衡而過早的能量耗盡。與MACO算法相比,，MP-ACA由于減少了路由過程節(jié)點能量的消耗,，性能有了一定的提高。
蟻群算法作為一種新的仿生優(yōu)化算法,，具有分布計算,、信息正反饋和啟發(fā)式搜索等特點。本文在對現(xiàn)有無線傳感器網(wǎng)絡(luò)蟻群改進(jìn)路由算法的基礎(chǔ)上,，改進(jìn)了現(xiàn)有路由算法路徑搜索方式,，很好地權(quán)衡了路由收斂速度與網(wǎng)絡(luò)生命周期的相互制約關(guān)系。同時將其應(yīng)用在無線傳感器網(wǎng)絡(luò)中進(jìn)行路由選擇,，對于提高無線傳感器網(wǎng)絡(luò)的網(wǎng)絡(luò)效率,、延長網(wǎng)絡(luò)的生存周期具有很高的應(yīng)用價值。
參考文獻(xiàn)
[1] 李建中,，李金寶,，石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問題與進(jìn)展[J].軟件學(xué)報,，2003,，14(10):1717-1727.
[2] 劉雯雯，馬銳,，許海濱.均衡無線傳感器網(wǎng)絡(luò)能耗的AODV改進(jìn)方案[J].計算機(jī)工程,，2008，34(22)：143-147.
[3] 梁華為,，陳萬明,，李帥，等.一種無線傳感器網(wǎng)絡(luò)蟻群優(yōu)化路由算法[J].傳感器技術(shù)學(xué)報,，2007,，20(11):2450-2455.
[4] 黎劍兵，鄭巍.無線傳感器網(wǎng)絡(luò)多種群蟻群優(yōu)化路由算法[J].計算機(jī)應(yīng)用研究,，2009,，7(26):2686-2690.
[5] GUNES M， SORGES U,， BOUAZIZ I. IARA-the-ant-colony based routing algorithm for MANETS[C]. International Conference on Parallel Processing Workshops(ICPPW’02). 2002:79-85.
[6] KASSABALIDIS I,， El-SHARKAWI M A， MARKS R J. Swarm intelligence for routing in communication networks [J]. Global Telecommunications,， 2001,，6(6):3613-3617.
[7] STUTZLE T,， HOOSH H. Max-Min ant systems[J]. Future Generation Computer Systems， 2000,，16(19):889-914.
[8] 于斌,，孫斌，溫暖,，等．NS2與網(wǎng)絡(luò)模擬[M]．北京：人民郵電出版社,，2007.