基于蟻群算法的能量均衡多路徑路由算法的研究*

童孟軍，關華丞

(杭州電子科技大學計算機學院，杭州310018)

無線傳感網 WSN(Wireless Sensor Networks)[1－3]是新一代的傳感器網絡，由于其集成了傳感器和無線網絡技術，因而具有非常廣泛的應用前景，對人類的生活和生產也將產生深遠的影響。無線傳感網通常具有能量有限的節點，節點數目龐大且無法及時補充，所以節約并均衡節點的能量消耗，最大限度的延長網絡生存時間，是無線傳感網的主要設計目標之一[4]。對于類似AOMDV[5]這類的多路徑路由協議，一直選擇相同的路徑進行數據的轉發，將導致路徑中部分節點的能量過早耗盡，而節點的失效又造成網絡分割，嚴重影響網絡的生存時間。如何能根據網絡當前的實際情況，進行數據包的轉發，從而做到整個網絡更好的負載均衡?；谙伻核惴╗6－9]ACO(Ant Colony Optimization)的路由協議，通過螞蟻包的發送，每個節點可以獲悉網絡當前實際情況，根據信息素概率公式選擇下一跳，非常適合設計這種能量負載均衡的多路徑路由協議?；谙伻核惴ǖ臒o線傳感網路由協議是目前國內外研究的熱點之一。本文以蟻群算法為切入點，在分析各類蟻群多路徑路由協議的基礎上，提出一種基于蟻群算法的能量均衡多路徑路由協議ABMR(Ant-Based Multipath Routing)，并通過仿真及實驗對此協議的性能進行了分析。

1 基于蟻群算法的路由協議

蟻群算法來源于螞蟻覓食的優化方式。蟻群系統ACS(Ant Colony System)是分布式的生物系統，螞蟻們之間協作幫助能完成單個個體所難以完成的艱巨任務，體現了生物的群體智能性。螞蟻從居住的地方去出發尋找食物的時候，會在經過的路徑上釋放一種叫信息素的化學物質。螞蟻們相互之間能感知到這種叫信息素的化學物質，后面的螞蟻會沿著信息素濃度高的路徑前進。信息素這種化學物質會隨著時間的變化而揮發，結果是距離短的路徑上的信息素濃度也變得越來越多，另外的路徑信息素就會越來越少。最終，螞蟻們通過相互合作會找到最優路徑。無線傳感網中的路由也一樣，需要發送數據的節點通過釋放類似螞蟻的路由搜索包到目的節點，類似螞蟻的路由搜索包從目的節點返回，最終形成一條源節點到目的節點的路由。

文獻[10]提出了適用于有線網絡的AntNet協議，第一次在網絡路由表的建立過程中使用了蟻群算法，也是迄今為止最成功的基于蟻群算法的路由協議之一。在AntNet協議中，使用了前向螞蟻和后向螞蟻的概念，前向螞蟻根據路由表中的啟發式信息值來概率選擇下一跳，并且把經過的節點放到前向螞蟻頭部中。前向螞蟻到達目的節點后，完成使命，對應轉換成一個后向螞蟻，后向螞蟻按照前向螞蟻經過的路徑返回，在經過的每個鏈路上釋放信息素。

文獻[11]中提出的ARA算法是最早的將蟻群算法應用于無線移動自組織網絡的按需多路徑算法。路由的建立是依靠前向螞蟻和后向螞蟻來實現。ARA開銷比較小，只需用發送螞蟻包的ID(序列號)，目的地址和源地址，另外路徑維護的時候，也不用發送螞蟻包，只需用在發送數據包的時候進行信息素更新就可以了，信息素在目的節點的鏈路上和到源節點的鏈路上都進行信息素的更新，另外進行定時的信息素揮發。

文獻[12]提出了ARAMA協議。ARAMA定義梯度(grade)的概念，這個值由后向螞蟻返回的途中進行計算并保存在節點中。梯度的計算公式依賴前向螞蟻收集的能量等鏈路信息。當中間節點收到一個后向螞蟻的時候，要根據螞蟻包中的路徑梯度值進行信息素更新，后向螞蟻包經過的鏈路信息素增加，另外鏈路信息素揮發。揮發的目的是為了節點更快的忘記老的路徑。數據發送的時候，是沿著最佳路徑發送，這樣就不用在路徑上進行切換。當最佳路徑被破壞時，馬上可以用另外的路徑來進行數據的發送。

與ARA和ARAMA不同，文獻[13]中提到的IEEABR是一個主動式的路由協議，網絡初始化時，每個節點隨機的向Sink節點發送一個前向螞蟻。后向螞蟻返回時，中間節點根據后向螞蟻中攜帶的信息素參數以及距離Sink節點的跳數對后向螞蟻經過的鏈路進行信息素更新，后向螞蟻到達源節點后就死亡。數據包根據概率選擇公式，選擇較好的路徑進行轉發。值得注意的是，IEEABR采用累加的方式進行信息素更新，這樣的策略容易陷入局部最優，使個別路徑上的節點過早的死亡，從而對整體的網絡壽命和通信能力產生不利影響。

在文獻[14]中Di Caro等人提出了AntHocNet協議，AntHocNet協議是一種基于蟻群算法的多路徑混合式路由協議。該協議的路由發現按需進行，而路徑維護則主動完成。這個路由協議有四個主要的過程:按需路徑建立、隨機數據發送、主動路徑維護和探索和處理失效的鏈路。

AntHocNet的優點是路由發現時找到了多路徑，這樣可以減少路由發現的頻率，主要缺點查找到的多路徑是相交多路徑，因此一個節點的斷開可能引起多條路徑的失效，路由維護過程需要有大量的螞蟻，另外，每個節點保存著一張它所有可達目的節點的路由表，對于規模大的網絡AntHocNet并不太適合。

文獻[15]提出了DAR(Distributed Ant Routing)協議，DAR是一種按需的蟻群路由協議，和主動式路由相比較，可以減少開銷，減少節點的能量消耗。在DAR協議中，前向螞蟻只關心交叉節點的情況，選擇下一跳時，只使用信息素值。后向螞蟻從目的節點返回時候，在返回的鏈路上只釋放常量值的信息素。節點根據信息素概率選擇下一跳發送數據。DAR協議的螞蟻保存所有經過節點的ID，適用于不大的網絡，同時網絡收斂較慢，有時候也容易導致局部最優。

文獻[16]提出了HOPNET協議，它是一種混合式路由協議，協議把網絡分成多個區域，在區域內部采用主動的路由方式，在區域之間，采用蟻群的按需路由協議。由于區域不是很大，所以區域內部的主動式路由協議，開銷也不會很大。通過這種方式，HOPNET在網絡規模比較大的時候，能表現出比較好的優勢。

在文獻[17]中，S．Misra等人在 AntHocNet基礎上提出了EAAR協議。該協議在信息素更新公式上考慮了到目的節點的最小跳數和能量。文獻[18]研究表明，信息素更新公式如果只用跳數作為參數，是很不合理的。優先選用了到目的節點跳數少的路徑，路徑上跳數是少了，有可能節點之間距離長，信號強度小，連接松散，容易導致網絡分割。另外節點之間距離增加，也會導致數據發送消耗的能量大幅度提高[19]。EAAR協議在進行多路徑判斷的時候，需要把符合條件的螞蟻都保存在螞蟻訪問列表中，其中包括螞蟻包訪問過的所有節點ID，如果符合條件的螞蟻包多的話，節點的內存開銷和多路徑的計算消耗也會比較大。

文獻[20]提出了一種基于信息素擴散模型蟻群算法的路由協議DBACRA。該協議分為實際和虛擬兩種信息素，一起來引導螞蟻包和數據包進行目的性路徑搜索。實際信息素是后向螞蟻從目的節點返回的時候，釋放在鏈路上的信息素。前向螞蟻可以通過虛擬信息素和實際信息素的引導到達目的節點。但由于虛擬信息素是通過擴散的方法來進行傳播的，在網絡移動和網絡比較大的時候，虛擬信息素也很容易陷入環路。

前面所說的一些多路徑路由協議，很多都沒有考慮到能量因素，如果按照傳統的蟻群算法，找到最優路徑，最后所有的流量幾乎都會集中到一條路徑上，而無線傳感網的節點能量受限，這樣就會導致這條路徑上的節點很快死亡，因此這類協議不能很好的直接應用于無線傳感網中。有些協議，雖然考慮到了各個路徑上的剩余能量，但沒有考慮到各個路徑所消耗的能量的速度。有些協議，沒有考慮到數據在傳感網的網絡擁塞情況。綜合考慮以上這些因素，結合蟻群算法，本文提出了基于蟻群算法的能量均衡多路徑路由協議ABMR，ABMR在信息素更新方式、信息素更新公式和蟻群多路徑形成方面進行了改進和創新。

2 蟻群算法的能量均衡多路徑路由協議

本文基于無線傳感網節點的能量有限的特點，提出一種基于蟻群算法的多路徑協議，記為ABMR協議。在該協議中，采用了一種新的多路徑生成的機制，在信息素更新公式上綜合考慮了路徑的能量消耗速度、路徑上剩余的最小能量、距離目的節點Sink的跳數和路徑的擁塞程度，這樣信息素更新公式更加合理。當源節點需要發送數據但沒有到目的節點的路由信息時，通過廣播發送前向螞蟻到目的Sink節點，目的節點生成對應的后向螞蟻，后向螞蟻按照前向螞蟻的路徑返回到源節點，后向螞蟻返回的時候在鏈路上釋放信息素。傳統的信息素的更新方式，在一個路徑上釋放的信息素會越來越多，造成這個路徑上的數據越來越多，不能自動到達網絡負載均衡。ABMR協議對信息素更新方式進行了改進，節點每次收到一個后向螞蟻，都重新對鏈路上信息素值進行計算，而不是傳統的信息素的累加更新方式，這樣的話，數據包在網絡上的分布會更均勻。每個節點根據后向螞蟻釋放的信息素采用概率路由選擇的方法發送數據，概率路由選擇策略使得數據均衡發布，最后導致自動的網絡負載均衡，提高了整個網絡的壽命。

2．1 路由發現

ABMR是一個混合多路徑路由協議，路由建立的時候是反應式路由協議，也就是按需路由協議，路由建立后，是主動路由協議，定期發送前向螞蟻。當源節點S需要向目的節點d發送數據時，需要查看路由信息，如果這個時候沒有到達目的節點的路由，就需要開始廣播發送前向螞蟻，需要發送的數據進行緩存。如果有到達目的節點的路由，就可以直接進行數據發送。源節點廣播前向螞蟻，標記為(這里一個螞蟻代表了一個控制報文)，。由于初始階段是廣播螞蟻，s節點的每個鄰居將收到的一個副本，記為．k(“．k”這個符號代表的是編號——單個廣播包的第k個副本表示為)，經過下一跳之后，下一個鄰居節點將收到(K，l是整數)，由于這些廣播螞蟻包是同一個源節點在同一個時刻產生的，我們稱它們為同類螞蟻，同類螞蟻有相同的源節點地址和序列號。每個前向螞蟻包的任務是找到一條連接s和d的路徑。在源節點和目的節點之間的每個中間節點，單播或者廣播前向螞蟻，這取決于當前的節點是否有到目的節點d的路由信息，沒有路由信息就廣播發送前向螞蟻，有路由信息的話，就按照信息素概率選擇公式單播發送前向螞蟻，式(1)是前向螞蟻信息素概率選擇公式:

當一個節點收到第一個前向螞蟻，馬上會把螞蟻轉發出去，同時第一個螞蟻的一些信息被保存在螞蟻訪問列表中(螞蟻訪問列表的結構在3．4節中有詳細介紹)。后面收到的前向螞蟻，如果收到的是和前面不同類的螞蟻，節點可以把這類前向螞蟻轉發出去。對于源節點的鄰居節點，只接收從源節點直接發出的前向螞蟻，也就是拒絕接收螞蟻頭部包含另外節點ID的那些前向螞蟻。節點如果收到的是相同類型的前向螞蟻，時延、跳數和能量可能比前面的螞蟻包都要差，如果都被丟棄，中間節點到目的節點就只能形成單路徑，不能發揮蟻群算法的優勢。因此，為了減少網絡中螞蟻傳播的開銷，節點收到一個同類螞蟻，先要進行環路的判斷，即前向螞蟻頭部攜帶的節點有沒有包含節點本身，如果形成環路，就直接丟棄這個螞蟻，否則按照下面同類螞蟻的多路徑判斷規則，形成源節點到目的節點的多路徑，具體步驟如下:

第1步:先要判斷新收到的同類螞蟻和螞蟻訪問列表中已有的同類螞蟻的第一跳是否一樣，這個第一跳也就是離開源節點后的第一節點。如果第一個節點不一樣，將新收到螞蟻的時延dnew和跳數hnew與螞蟻訪問列表中同類螞蟻的時延dsim和跳數hsim 相比較，只要 dnew＜λddsim且 hnew＜λhhsim，就接收新來的前向螞蟻。本文規定λh為1．5，λd為2.5，可以根據不同的網絡環境來進行調整。

第2步:如果新收到的前向螞蟻的第一跳和螞蟻訪問列表中保存的其中任一個同類螞蟻的第一跳一樣，就要判斷新收到的前向螞蟻的入鏈路是否和螞蟻訪問列表中的同類螞蟻一樣。如果入鏈路不一樣，也就是上一跳不一樣，只要dnew＜λddsim且hnew＜λhhsim，就接收新來的前向螞蟻。本文規定 λh為1.5，λd為2．5，可以根據不同的網絡環境來進行調整。

第3步:如果新收到的前向螞蟻的入鏈路與第一跳和節點中保存的同類螞蟻一樣，只有hnew＜hsim，才接收新來的螞蟻。

通過這個方法，可以使得螞蟻探索路徑時獲得多條路徑，在數據發送的時候，如果一個鏈路出現故障，可以通過另外的鏈路發送出去。同時，多路徑有助于網絡的能量和負載均衡。

采用前面的螞蟻包發送方法，到達目的節點d的前向螞蟻有一定的數量，每個前向螞蟻按次序保存了路徑上所經過的所有節點ID。但無線傳感網本身環境比較復雜，考慮到網絡擁塞和時延問題，為了減少一些不必要的浪費，有些到達目的節點“太遲”的前向螞蟻，目的節點作丟棄處理，不往回發送后向螞蟻。在目的節點收到第一個到達的前向螞蟻之后，會針對這類前向螞蟻，設置一個等待時間，超過這個等待時間到達的這類前向螞蟻，就被丟棄，不作任何處理。等待時間的計算公式見式(2)。后面介紹前向分組結構的時候會看到，前向螞蟻分組里攜帶了從源節點s出發的那個時間，這樣端到端的時延Ts－d就會很容易得到。Cd是個參數，可以根據網絡環境進行適當調整。

在Td這段時間內，就像圖1里顯示的一樣，目的節點收到了一個前向螞蟻(Forward Ant)，就將前向螞蟻轉換成對應的一個后向螞蟻(Backward Ant)，后向螞蟻將沿著前向螞蟻走過的路徑返回到源節點s。如果由于下一跳節點發生了異常情況，例如由于節點的位置發生了改變，那么這個后向螞蟻將被丟棄。當后向螞蟻從一個編號為j的節點移動到編號為i的節點時，需要對節點i進行信息素更新，節點i更新或建立目的節點為d的路由信息，這個路由信息的下一跳就是j。式(3)為信息素更新公式:

圖1 前向螞蟻和后向螞蟻經過的路徑

在式(3)中，H是當前節點i到達目的節點d的跳數，這個值可以從后向螞蟻的visitednode字段里得到。Ts－i是源節點到當前節點的時延，Eavg是從源節點s到目的節點已經消耗的平均能量，從后向螞蟻包中得到。Min值是后向螞蟻所經過的所有節點中，剩余能量最小的節點的能量值。在式(3)的信息素更新公式中，Eavg反應了整個鏈路的能量消耗情況，Eavg值大，說明這個鏈路上能量消耗多，也就是能力消耗速度快，可能這個鏈路上的節點承受了比較多的數據發送任務，所以在以后的路由選擇過程中，這些路由上的節點應盡可能少承擔數據轉發任務。Min反應了一條鏈路的瓶頸情況，具有瓶頸的鏈路也應當盡可能少的承擔數據發送任務。這樣有助于延長節點和網絡的壽命。有時候一個節點的提前死亡，會導致整個網絡的分割，特別是在有些移動場景，當一個提前死亡的節點剛好移動到整個網絡兩個部分的連接處，這時候一個死亡的節點，就會導致網絡的分割或一段時間的分割。H是當前節點i到達目的節點d的跳數，數據包盡可能沿著跳數少的路徑到達目的節點，H值小，后向螞蟻在鏈路上釋放的信息素的值也大，數據包選擇這個鏈路的概率也大。Ts－i是后向螞蟻包到達當前節點的時間減去后向螞蟻包攜帶的從源節點發出的時間，也就是前向螞蟻包從源節點到目的節點的時間的時延加上后向螞蟻包到當前節點的時延。一般來說，所需要傳輸延時小的路徑要優于傳輸延時大的路徑。傳輸延時大的路徑，有可能網絡在這個部分的傳輸任務比較重，負載比較大，有可能會進入擁塞狀態，所以盡可能的往這些地方少發數據和螞蟻包，根據式(3)在這些鏈路上釋放的信息素也會相對的少些。k1，k2，k3和k4是以上4個參數的系數，在各個不同的網絡環境，通過調節各個系數，來適應網絡的環境。

2．2 數據發送

通過螞蟻的發送，在各個節點建立了路由信息，一旦有后向螞蟻返回，源節點中保存在緩沖區里的數據就可以通過螞蟻建立起來的路由發送出去。數據發送是以概率發送的方法進行，所有的節點收到需要轉發的數據包后，按照式(4)進行選擇發送:

在式(4)中，β2是一個參數因子，可以調節鏈路信息素對數據轉發的影響，β2值越大，信息素值越大的鏈路，被選中轉發的數據的概率就越大，也就是“好的鏈路“使用頻率會更高，可以根據具體的使用環境進行調整。本文中β2是一個大于等于1的值。發送數據多的鏈路，可能會比較擁擠，發送時間變長，能量消耗也會比較多，鏈路上節點的剩余能量減少，通過信息素的自動更新，數據會自動往剩余能量多和數據少的路徑上發送，最后做到整個網絡的負載均衡。

路由表中信息素的揮發是周期性進行的。τ為時間周期，信息素揮發公式如式(5)所示:

在式(5)中，ρ的范圍是0到0．05之間。

2．3 路由維護和鏈路故障

節點在數據發送的時候，需要進行路由維護，一般發送N個數據報后發送一個前向螞蟻或者定時發送前向螞蟻。ABMR采用定時發送前向螞蟻的方式，當節點開始發送數據后，定時產生一個前向螞蟻。定時發送前向螞蟻的時間間隔，可以根據節點的移動速度和網絡情況來進行設定，本文暫時設為5 s。但是否發送這個前向螞蟻，需要根據路由表中各個鏈路上的剩余的信息素大小和螞蟻訪問列表的長度來決定，如果各個鏈路上最大的剩余信息素已經小于某個門限值，且螞蟻訪問列表的長度小于一個上限值，就可以發送前向螞蟻，這樣也可以保證網絡中的前向螞蟻是異步發送。同樣的，源節點收到一個后向螞蟻，也可以根據上述的方法來決定是否發送前向螞蟻。如果剩余信息素足夠大或者螞蟻訪問列表大于上限值，可以重新定時發送。信息素的門限值可以設定為原始值的30%，當然這個值可以調整。螞蟻訪問列表的上限值，可以根據整個網絡的節點規模數和節點內存大小來確定，本文后面的仿真實驗設置為總節點數的20%。

為了避免相同路徑上的節點重復發送前向螞蟻，當一個節點收到一個前向螞蟻時，需要把發送前向螞蟻的定時器清零，重新進行計時。經過這樣的處理，源節點到目的節點之間的正在進行數據發送的中間節點，如果有前向螞蟻經過，把收到的前向螞蟻發出去，把節點自己產生的前向螞蟻延遲后再發送，就可以減少自己螞蟻包的發送數量，減輕網絡的開銷。

路由維護時候，前向螞蟻的發送有單播和廣播兩種方式，發送單個前向螞蟻的時候，按照信息素概率選擇公式，只是對原有的路徑進行信息素的更新。廣播發送螞蟻的方式有10%的概率，發送廣播包有兩個方面的原因:一方面，發送單播包，只會對已有的路徑進行信息素的更新，但不能搜尋新的路徑(特別是在節點移動或有節點能量消耗掉的情況下)，這可能會導致原來的路由失效。另一方面發送廣播包，既可以搜尋新的路徑，又可以避免陷入局部最優。廣播包發送到鄰居的時候，鄰居節點可能也沒有路由信息，這時候鄰居節點會繼續發送廣播包。但考慮到這樣會很快在整個網絡中進行洪泛，開銷會很大，所以對這樣的廣播包進行了限制，本文把這些廣播螞蟻的TTL值設置為2(這個值可以根據環境變化)，就是說兩跳后還沒發現路由，就把螞蟻包刪除。采用跳數限制的機制，是因為考慮到新路徑一般是在當前路徑附近

無線傳感網環境復雜，節點在數據發送過程中，有可能會失去和鄰居的聯系，造成鏈路故障。和很多協議類似，ABMR協議也采用了hello機制，鄰居之間定時發送hello報文。通過hello報文相互發送，可以發現這個鄰居還是否可達，就可以判斷和這個鄰居的鏈路是否出現了故障。當然節點本身有故障的話，也需要主動通知鄰居，使得和它相鄰的節點能及時發現鏈路故障。

當節點發現和一個鄰居的鏈路出現故障，節點要把這個鄰居的相關信息從鄰居表和路由表中刪除。在刪除鏈路故障的鄰居之前，節點首先要做個判斷，將要被刪除的鄰居節點是否是自己到達目的節點的唯一下一跳，如果是唯一的下一跳，就需要給其他的鄰居發送鏈路故障通告?；蛘哌@個鄰居節點不是到目的節點的唯一下一跳，但通過查看信息素，這條路由是最佳路由，也需要給其他的鄰居發送故障通告。在前向螞蟻的發送過程中，本地節點需要保存自己的“上一跳”，也就是把前向螞蟻發給自己的節點地址，這個時候發送鏈路故障通告，只需要發送給自己的“上一跳”就可以，不需要廣播，這樣可以減少開銷。收到鏈路故障通告的節點，按照上面的方法，同樣進行處理。

當節點由于數據包發送失敗而知道鏈路故障，并且沒有另外的路徑用于發送數據包，節點開始本地修復路由，這個機制和AODV有點類似。但有區別的是，為了減少網絡消耗，這兒的修復螞蟻不是廣播，而是根據鄰居數量，連續發送幾個路由修復螞蟻，當然這些路由修復螞蟻包有最大跳數限制(本文的跳數限制為3)。在發出第一個修復螞蟻后，節點同時開始計時，如果在計時期結束沒有收到后向修復螞蟻，節點斷定沒有到目的節點的路徑，節點會丟棄緩存需要發送的數據，同時按照上面講的方法，向它的“上一跳”發送鏈路故障通告。

2．4 ABMR報文格式

在ABMR協議的報文結構中，前向螞蟻需要保存該它已經訪問過的所有節點ID，也就是把所有訪問過的節點放在visitednode字段。在利用概率公式在鄰居表中選擇下一跳時，該字段做為禁忌表。也就是說只有存在于鄰居表中，且不存在于visitednode中的節點，才有可能成為下一跳。雖然visitednode字段增加了前向螞蟻包的長度，但是避免了產生環路和邊緣節點丟包的情況，同時后向螞蟻也是通過visitednode字段中的節點順序返回源節點。

圖2是前向螞蟻報文格式。其中，Type是數據包類型，這里該字段值為前向螞蟻的類型;Src_address是產生前向螞蟻的源節點的地址;Seqno是源節點生成前向螞蟻時候的序列號，每個新生成的前向螞蟻的序列號都不一樣，收到前向螞蟻的節點就可以用＜Src_address，seqno＞這個標志來判斷是否收到了同類的螞蟻包。Esum是螞蟻訪問過的節點已經消耗的能量總和，每個節點收到一個前向螞蟻后，需要把本節點已經消耗的能量加上去。Esum用于計算信息素。Src_timeh這個字段記錄了從源節點出發的時間。TTL是螞蟻生存時間段，表明螞蟻在網絡中的壽命。目的主要有兩個，一方面可以限制螞蟻的搜索范圍，另一方面是防止螞蟻無限制的在網絡中兜圈子，因而白白浪費網絡資源。每經過一個中間節點，就把TTL值減1。當TTL值為零時，就丟棄這個螞蟻。visitednode字段保存該前向螞訪問過的所有節點ID。

圖2 前向螞蟻報文格式

前向螞蟻到達目的節點后就自己消亡，符合條件的前向螞蟻，就生成相應的后向螞蟻。后向螞蟻的報文格式如圖3所示。其中，Type字段為后向螞蟻包類型;Eavg是從源節點s到目的節點已經消耗的平均能量，由目的節點計算并賦值。Eavg通過前向螞蟻中的Esum除以VisitedNode中的節點個數得到，Eavg用于信息素更新公式中。Emin是后向螞蟻所經過路徑上能量最小節點的能量值，Src_time是這個后向螞蟻對應的前向螞蟻從源節點發出的時間。visitednode是從前向螞蟻傳遞過來的前向螞蟻所走過的路徑，后向螞蟻沿著這個路徑原路返回源節點，返回的過程中更新每條鏈路上的信息素。后向螞蟻均按式(3)對鏈路上的信息素值進行更新。后向螞蟻和前向螞蟻有個區別，那就是后向螞蟻沒有了TTL字段，主要的原因是后向螞蟻已經攜帶了路徑信息visitednode，如果按照路徑信息，后向螞蟻的下一跳不可達，后向螞蟻就自己作丟棄處理，所以也就不用TTL字段。到了源節點，后向螞蟻完成任務，被丟棄。

圖3 后向螞蟻報文格式

到達中間節點的前向螞蟻，如果符合條件可以轉發出去尋路，都需要在螞蟻訪問列表中保存。螞蟻訪問列表是一個鏈式結構，圖4其表項的結構。＜Src_address，seqno＞這個組合標志是用來判斷是否是同類的螞蟻包。F_hop是源節點到當前節點的第一跳，L_hop是當前節點的上一跳，也就是源節點到當前節點的最后一跳，這兩個標志主要是用于同類螞蟻的多路徑判斷規則。螞蟻訪問列表中的螞蟻沒有保存整個visitednode，這樣可以節省傳感器節點有限的資源。Hops是源節點到當前節點的跳數，Src_time和前向螞蟻中的意思一樣，記錄了從源節點出發的時間。Hops和Src_time一起用于同類螞蟻的多路徑判斷規則。TTL是螞蟻生存時間，當節點收到后向螞蟻的時候，把對應的前向螞蟻從螞蟻訪問列表中刪除，但如果對應的后向螞蟻在返回的路徑上丟失，就需要通過TTL字段定期刪除螞蟻訪問列表中對應的螞蟻，通過TTL字段可以定期把螞蟻訪問列表中無效的螞蟻刪除，避免無效的螞蟻包長時間占用節點寶貴的資源。

圖4 螞蟻訪問列表表項的結構

圖5是鄰居表結構圖，保存著鄰居節點的信息和到目的節點的路由信息素。Nei_addr是鄰居節點的地址，Nei_energy是鄰居節點當前的能量值。Hops是從目的節點到鄰居節點的距離，以跳數為單位，當剛開始建立鄰居表，沒有收到后向螞蟻的時候，Hops初始值為一個常量BIGGEST_HOPS，協議規定這個值為9999，表示這個鄰居還不能作為下一跳進行數據轉發，當節點收到一個后向螞蟻的時候，更新Hops字段里的值。當節點收到后向螞蟻的時候，就要根據式(3)計算信息素的值，在鏈路上釋放信息素，這個信息素的值就賦給了圖5里的Pheromone。Pheromone的初始值是零，前向螞蟻到一個節點，如果發現所有的鏈路都沒有信息素，就需要廣播前向螞蟻。每過一定的時間，Pheromone里的值就要進行揮發。最后，Last_update_time是節點最近更新這個鄰居表項的時間。

圖5 鄰居表結構圖

圖6是HELLO包的結構圖。其中Type表示數據包類型。Src_addr是發送HELLO包的鄰居節點的地址，Node_energy是鄰居節點當前的能量值。節點通過相互之間定期發送hello包，維護著節點之間的鄰居表信息，HELLO的發送時間間隔可以根據節點不同場景來進行設置，對于節點移動快的場景，HELLO的發送間隔可以小一點。本文設定HELLO的發送間隔時間為2 s，如果超過6 s沒有收到鄰居的HELLO包，就需要把這個鄰居節點從鄰居表中刪除。

圖6 HELLO包結構圖

2．5 算法描述

ABMR協議的具體算法步驟如下:

第1步:在協議運行初始階段，先進行hello包的廣播，建立起節點與其鄰居之間的相互關系，初始時每個具有鄰居關系的鏈路上的信息素設置為空;

第2步:需要發送數據的源節點，首先查看節點的路由信息表中有沒有到目的節點的路由信息，如果沒有路由信息，則廣播前向螞蟻，同時把發送的前向螞蟻保存到螞蟻訪問列表中。有路由信息，就可以直接按路由信息選擇下一跳進行發送;

第3步:如果中間節點是源節點的鄰居節點，只接收從源節點直接發出的前向螞蟻。中間節點收到一個前向螞蟻，如果TTL值的是1，就直接丟棄前向螞蟻。如果節點收到的是一個不同類螞蟻，先把螞蟻保存在螞蟻訪問列表，然后看看有沒有到目的節點的路由信息，如果有到目的節點的路由信息，按照式(1)概率選擇下一跳轉發出去，如果沒有路由信息，就廣播轉發前向螞蟻。如果節點收到的是同類螞蟻，先要判斷是否形成環路，形成環路的螞蟻要被丟棄，對于沒有形成環路的前向螞蟻，就要按照3．1路由發現里的多路徑判斷規則進行處理，符合條件的前向螞蟻保存到螞蟻訪問列表，按照前面的方法轉發出去，不符合條件的前向螞蟻，直接被丟棄。

第4步:目的節點如果收到第一個前向螞蟻，前向螞蟻就被刪除，生成對應的一個后向螞蟻，后向螞蟻沿著前向螞蟻所走過的路徑返回到源節點，同時目的節點開始定時計時。對于后面到達的前向螞蟻，如果在計時范圍內到達，前向螞蟻轉換成對應的一個后向螞蟻沿原路返回，超過計時范圍到達的前向螞蟻直接刪除，不作另外處理。

第5步:中間節點每收到一個后向螞蟻，刪除對應螞蟻訪問列表中保存的螞蟻，如果節點不是目的節點的鄰居節點，中間節點要按照式(3)計算信息素，在鏈路上釋放信息素。這樣，收到后向螞蟻的節點就有了到目的節點的路由信信息。如果節點是目的節點的鄰居節點，節點可以直接發送數據給目的節點，不用在鏈路上釋放信息素。

第6步:當源節點收到第一個后向螞蟻，馬上在鏈路上釋放信息素，建立到目的節點的路由信息表，刪除螞蟻訪問列表中保存的螞蟻，同時把緩存中的數據發送出去。數據報的發送通過式(4)來進行概率選擇。如果節點是目的節點的鄰居節點，不用進行公式概率選擇，可以通過鄰居表直接把數據發送目的節點。

3 仿真與分析

為了測試本文提出的多路徑蟻群算法應用到無線傳感網中的效果，本實驗對ABMR、AOMDV和AntHocNet協議的性能進行比較分析。本文對ABMR協議采用的仿真平臺是ubuntu10．04+NS2．34網絡仿真平臺。筆者實現了用于集成進NS2的ABMR代碼，包括ABMR報文格式數據結構和ABMR代理類的實現，并將其添加進 NS2仿真軟件。按照AntHocNet協議的功能，基本實現了這個協議，也添加到NS－2里面，用于和ABMR協議的性能分析比較。

3．1 仿真場景與參數設置

移動場景文件使用 CMU工具 setdest創建，SINK節點放在網絡中心位置，選用參數表如表1所示。數據流場景選用 CBR，由 CMU工具中的cbrgen．tcl創建，CBR流屬于固定速率比特流，方便在不同網絡拓撲或節點運動情況下比較性能。各項參數設置表如表2所示。

表1 移動場景參數表

表2 數據流參數表

為了便于研究協議能耗改進性能，能量的傳輸模型本文選用 First-order Ratio Model[19]，傳感器節點參數表如表3所示。ABMR協議里的蟻群路由參數如表4所示。

表3 傳感器無線節點的參數

表4 蟻群路由算法參數

3．2 性能分析

仿真實驗主要從投遞率、時延、路由開銷和能量有效性這幾個方面對幾個路由協議的性能進行比較分析。

圖7 分組投遞率與節點最大移動速度關系

三種協議分組投遞率與節點最大移動速度的關系如圖7所示。除了AOMDV協議以外，另外兩種協議的數據發送是采用多路徑概率發送機制，所以這兩個協議的投遞率都比AOMDV要高。AntHocNet雖然采用多路徑的隨機概率發送機制，但數據包會更多的往信息素多的鏈路上發送，數據包發送多的鏈路，信息素也會越來越多，最后一條“好”的路徑上，數據量會很多，這樣會造成局部鏈路的繁忙，導致丟包的概率上升，所以在移動速度慢的場景，AntHocNet在分組投遞率方面比ABMR要差點。AMBR由于采用更好的多路徑機制，信息素會根據路徑當前能量和負載情況實時進行調整，數據會更均衡的注入網絡中的各個路徑，最后導致自動的網絡負載均衡，各個路徑平均分攤網絡的流量，在數據流量比較大和節點移動速度快的時候，ABMR在這方面的性能表現的更優越。另外ABMR采用了更合理的鏈路故障恢復機制，當發現路由出現問題的時候，可以快速恢復路由，從而提高了數據的投遞率。所以在各種速度的移動場景下，ABMR協議的分組投遞率比另外兩個協議表現出更好的性能。

圖8顯示了幾種協議端到端平均時延與節點最大移動速度的關系，非常明顯，在延時方面，AntHocNet和ABMR要比AOMDV低不少。AntHocNet是盡量往時延最小的鏈路發送數據包，如果發包速度不快的話，AntHocNet這時候的時延有優勢。當隨著節點移動速度的加快，AMBR協議比另外兩個協議的延時更少。一方面AMBR采用的多路徑機制，到目的節點形成的路徑比另外兩個協議更多，每個鏈路上的信息素會根據路徑當前能量和負載情況實時進行調整，各個路徑平均分攤網絡的流量，在某個鏈路上擁塞的機會就比較少，而且節點在路由上有效的下一跳多的話，當節點快速移動的時候，選擇的機會更多。所以，在數據流量比較大和節點移動速度快的時候，ABMR相比另外協議，延遲有更多的優勢。另一方面，ABMR采用的鏈路故障恢復機制，當發現路由出現問題的時候，可以快速恢復路由，減少了數據包的盲目發送，相應的也減少了時延。當節點移動速度加快的時候，下一跳不可達的可能性會增大，數據包的丟失和路由的重新構建會增多，這種情況下，幾種種協議的時延都有增加的趨勢。

圖8 端到端平均時延與節點最大移動速度的關系

蟻群算法在投遞率和時延方面顯示了良好的性能，但取得這樣好的性能，需要有一定的成本和付出。從前面對ABMR協議的詳細介紹和分析里我們可以發現，為了適應網絡中節點的不斷移動和變化，ABMR在路由維護的時候需要定時發送一些前向螞蟻包，通過后向螞蟻對路由信息素進行實時的更新。從前面的實驗分析結果也可以看到，ABMR提高了數據的投遞率以及降低了時延，但定時螞蟻包的發送也增加了路由的開銷。本實驗中路由開銷是指，目的節點平均每收到一個數據包，所需要的控制包的個數。AntHocNet在路由維護的時候，也需要定時發送螞蟻包，和AntHocNet相比較，ABMR協議路由維護時候前向螞蟻的發送方式、多路徑機制、基于能量和負載的信息素更新機制和改進的鏈路維護機制，使得ABMR的路由開銷比AntHocNet要少。圖9說明了ABMR和AntHocNet的路由開銷要比AOMDV大，但ABMR的路由開銷又比AntHocNet要少一些。

圖9 路由開銷與節點最大移動速度的關系

圖10 平均能量消耗與最大移動速度關系

平均能量消耗表示目的節點收到一個數據包網絡所消耗的平均能量，收到一個數據包消耗的能量越小，說明網絡的能量有效性越高。AMBR采用的多路徑機制和鏈路故障恢復機制使得它在和AntHocNet協議的比較中勝出，另外ABMR的路由維護機制也使得ABMR可以發送更少的前向螞蟻，從而降低了平均能量消耗。隨著節點移動速度的增加，數據包的丟包率會提高，路由請求的次數也會變多，導致幾個協議的平均能量消耗也增多。當節點移動速度超過30 m/s的時候，幾個協議的平均能量消耗的速度快速遞增。

4 結束語

本文在分析各種蟻群路由協議的基礎上，提出了ABMR協議。ABMR協議在螞蟻數據包結構、信息素更新公式、信息素更新方式和多路徑建立機制等方面都作了進一步改進。

協議在信息素更新公式中綜合考慮了路徑的能量消耗速度、路徑上剩余的最小能量、和距離目的節點Sink的跳數和路徑的擁塞程度，這樣信息素更新公式更加合理。在信息素更新方式上，每次收到一個后向螞蟻，都徹底對鏈路上信息素值進行更新，而不是傳統的信息素的累加更新方式，這樣的話，數據包在網絡上的分布會更均勻。傳統的信息素的更新方式，在一個路徑上釋放的信息素會越來越多，造成這個路徑上的數據越來越多，不能到達網絡負載均衡。在多路徑建立機制方面，中間節點對同一源節點發來的前向螞蟻作了處理，可以在源節點與目的節點之間建立起多條路徑。在數據發送階段，概率路由選擇策略通過每條路徑不同的信息素值，把數據流量均衡的注入無線傳感網，使得數據均衡發布，最后導致自動的網絡負載均衡。減少數據的發送時延，提高數據的投遞率和網絡壽命。本文最后在NS－2仿真環境下對ABMR、AOMDV、AntHocNet協議進行仿真實驗，對結果進行評價和分析。仿真結果表明，ABMR協議在能量有效性和數據分組投遞率方面有了一定的提高，同時減小了分組端到端時延。

[1]李建中，高宏．無線傳感器網絡的研究進展[J]．計算機研究與發展，2008，45(1):1－15．

[2]Akyildiz I F，Su W L，et al．A Survey on Sensor Networks[J]．IEEE Communications Magazine，2002，40(10):2－116．

[3]Rahman K C．A Survey on Sensor Network[J]．Journal of Computer and Information，2010，1(1):76－87．

[4]Shafiullah G M，Amoakoh G A，Wolfs P J．A Survey of Energy-Efficient and Qos-Aware Routing Protocols for Wireless Sensor Metworks[G]//Novel Algorithms and Techniques in Telecommunications，Automation and Industrial Electronics．Springer Netherlands，2008:352－357．

[5]Marina M K，Das S R．Ad Hoc On-Demand Multipath Distance Vector Routing[J]．Wireless Coommunications and Mobile Computing，2006;6:969－988．

[6]Colorni A，Dorigo M，Maniezzo V．Distributed Optimization by Ant Colonies[C]//Proceedings of the 1st European Conference on Artificial Life．1991:134－142．

[7]Dorigo M．Optimization，Learning and Natural Algorithms[D]．Department of Electronics，Politecnico di Milano．1992．

[8]Dorigo M，Stutzle T．蟻群優化[M]．北京:清華大學出版社，2007:3－7．

[9]Dorigo M，Bonabeau E，Theraulaz G．Inspiration for Optimization from Social Insect Behavior[J]．Nature，2000，406(6):39－42．

[10]Di Caro G，Dorigo M．AntNet:Distributed Stigmergetic Control for Communication Networks[J]．Journal of Artificial Intelligence Research，1998，9(1):317－365．

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

[12]Hussein O，Saadawi T．Ant Routing Algorithm for Mobile Ad-Hoc Networks ARAMA[C]//Proceedingsofthe IEEE Performance Computing and Communications Conference(IPCCC)，2003:15－17．

[13]童孟軍，俞立，鄭立靜．基于蟻群算法的無線傳感器網絡能量有效路由算法研究[J]．傳感技術學報，2011，24(11):1632－1638．

[14]Di Caro，Ducatelle F，Gambardella L M．AntHocNet:An Adaptive Nature-Inspired Algorithm for Routing in Mobile Ad Hoc Networks[J]．European Transactions on Telecommunnications，2006，16(5):443－455．

[15]Laura R，Matteo B，Cgianluca R．On Ant Routing Algorithms in Ad Hoc Networks with Critical Connectivity[J]．Ad Hoc Network Journal，2008，6(6):827－859．

[16]Wang J，Osagie E，Thulasiraman P．HOPNET:A Hybrid Ant Colony Optimization Routing Algorithm for Mobile Ad Hoc Network[J]．Ad Hoc Networks，2009，7(4):690－705．

[17]Misra，Sanjay K Dhurandher，Mohammad S，et al．An Ant Swarm-Inspired Energy-Aware Routing Protocol for Wireless Ad-Hoc Networks[J]．The Journal of Systems and Software，2010，83(11):2188－2199．

[18]Ducatelle F，Di Caro G A，Gambardella L M．An Analysis of the Different Components of the AntHocNet Routing Algorithm[C]//ANTS’06 Proceedings of the 5th International Conference on Ant Colony Optimization and Swarm Intelligence，2006:37－48．

[19]Heinzelman W B，Chandrakasan A P，Balakrishnan H．An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J]．IEEE Transactions on Wireless Communications，2002，1(4):660－670．

[20]鮑榮，潘浩，董齊芬．基于信息素擴散模型蟻群算法的無線傳感網路由研究[J]．傳感技術學報，2011，24(11):1644－1648．