基于信息素擴散模型蟻群算法的無線傳感網路由研究*

鮑 榮，潘 浩，董齊芬，俞 立，邵 磊

(浙江工業大學信息工程學院，杭州 310023)

無線傳感網是指由部署在監測區域內大量的廉價微型傳感器節點通過無線通信方式形成的一個多跳自組織網絡系統。與傳統的移動自組織網絡不同，無線傳感網中每個節點的能量十分有限，且大規模節點的能量補充通常較為困難，故有必要研究一種能量高效的路由算法，使數據傳輸選擇最優路徑的同時，能延長網絡的生命周期［1］。無線傳感網發展至今，已提出許多路由協議。如LEACH協議［2］、Gossiping協議［3］、PEGASIS 協議［4］等，但這些協議對動態網絡的適應性并不理想。

近年來，仿生學最優尋解算法受到廣泛關注，如，粒子群優化算法［5］源于鳥群覓食行為，具有易實現、收斂快等特點，但容易陷入局部最優;差分進化算法［6］是基于群體進化的啟發式搜索技術，魯棒性較強、收斂快，但也存在局部優化較弱的缺點;蜂群算法［7］把每個蜜蜂都看做一個智能體，通過蜂群個體協同作用達到群體智能的效果。然而，這些尋優算法由于自身算法模型的局限，在路徑優化方面的適用性不強。當前，普遍認為將蟻群算法［8］應用到無線傳感網路由協議中是較為可行有效的。文獻［9］提出一種基于蟻群的多路徑路由算法，通過負荷平衡機制達到平衡節點能耗的目的，提高了能量效率。文獻［10］提出一種最優能量消耗蟻群路由算法，通過能量最佳分配機制使得節點能耗降低，延長了網絡生存周期。文獻［11］的EEABR協議將節點能量水平和傳輸距離引入信息素更新公式。文獻［12］根據路徑上最低的能量水平來評估信息素增量。與其它路由算法相比，基于蟻群算法的無線傳感網路由協議有以下優點［13］:(1)自適應性好;(2)魯棒性強;(3)支持多路徑;(4)具有局部/全局優化能力;(5)易與其它算法相結合。但目前大多數的蟻群路由算法具有一定的局限性，或沒有考慮螞蟻的反向傳輸，導致傳輸時延加大，或沒有考慮動態網絡的情況。

本文對基于蟻群算法的路由協議進行了深入研究，提出一種能量高效的基于信息素擴散模型的蟻群路由優化算法(Diffusion-based Ant Colony Routing Algorithm，DBACRA)。該算法由實際和虛擬兩種信息素共同指引路由包與數據包進行偏向性的路徑搜索，并考慮節點剩余能量以平衡全網的能耗，從而延長整個網絡的生命周期。最后，通過TOSSIM仿真驗證該路由協議的有效性及能耗、時延及網絡壽命等方面的性能。

1 預備知識

1.1 蟻群算法概述

蟻群算法［8］(Ant Colony Algorithm，ACA)由意大利學者Dorigo等人提出，其靈感來源于自然界中螞蟻群體覓食尋徑行為:螞蟻隨機搜索蟻穴周圍區域，當一只螞蟻找到食物源，它會在回程中留下一種稱為信息素的揮發性分泌物，其他螞蟻可根據其濃度決定尋食路徑。對于一條路徑，經過的螞蟻越多，則信息素濃度越大，從而吸引更多螞蟻，形成一種正反饋，使得螞蟻最終可以發現最短路徑。

近年來，蟻群算法被廣泛應用于路由算法中，以下介紹一種基于基本蟻群的路由算法。

1.2 基本蟻群路由算法數學模型

基本蟻群路由算法(Basic Ant Colony Routing Algorithm，BACRA)中，人工螞蟻模擬真實螞蟻，通過信息素量與能量啟發因子權衡，尋找最優路徑。

源節點創建前向螞蟻，該螞蟻按照如式(1)所示的概率選擇下一跳節點，并記錄沿途節點。

前向螞蟻到達目的節點后，轉換為后向螞蟻并原路返回。當節點i接收從節點j發送的后向螞蟻時，節點i所有通信路徑的信息素進行揮發，揮發完成后，后向螞蟻在其經過的路徑上釋放信息素:

其中，

式中，是揮發完成螞蟻釋放信息素后，該節點的信息素量，ρ是信息素的揮發率，且 0＜ρ≤1。Δτij是后向螞蟻釋放的信息素量，w是調整信息素釋放量的權值。是從節點i經節點j到達目的節點d鏈路代價，標識路徑長短的跳數。

在無線傳感網中，節點失效、新節點加入或節點移動都會造成網絡拓撲結構的動態變化，而BACRA算法易陷入局部最優解，且傳輸時延長，因此不能適應這種變化。因此，本文提出DBACRA算法，該算法在解決這種局限性的同時，有效減少節點能耗，延長生命周期。

2 改進的蟻群優化算法——DBACRA算法

該算法在BACRA算法基礎上引入實際信息素和虛擬信息素的概念，從擴散模型、路由優化和數據傳輸三方面進行改進。人工螞蟻結合實際信息素、虛擬信息素及能量信息來尋找最優路徑，并能更新實際信息素的分布。虛擬信息素基于擴散模型，能快速反映網絡的動態。由于虛擬信息素不斷擴散開來，具有不可靠性，故數據包的傳輸僅根據實際信息素和能量來選擇路徑。

2.1 擴散模型

建立信息素的擴散模型是可行的，且有利于路由信息的分享。擴散模型是指網絡中所有節點在其生命周期內不斷廣播路由信息及其剩余能量值。任意節點j構造的擴散消息包應包含一張表:目的節點d、到達該目的節點的最佳信息素以及節點j的剩余能量。其中，最佳信息素的計算如式(4)所示:

當節點i接收到節點j廣播的擴散包時，更新鄰居表中該鄰居節點j的能量值。若沒有節點j，則將其加入到鄰居表。然后，計算節點i經過鄰居節點j到達目的節點d的引導信息素，即綜合考慮最佳信息素和鏈路代價得出的信息素:

式中，為節點i到節點j的鏈路代價，可用跳數表示。由于由擴散過程得到，具有不可靠性，故依賴于的引導信息素也具有不可靠性，故將其更新到虛擬信息素中:

路由系統剛啟動時，由目的節點擴散固定的信息素值，經幾輪擴散后，整個網絡將形成信息素的初始分布，即建立路由梯度。文獻［10］發現蟻群路由算法在高動態網絡中性能較差，在初始狀態下前向螞蟻缺乏可用信息，導致收斂較慢。本文改進的蟻群算法結合擴散模型，有利于在初始狀態指導前向螞蟻的偏向性搜索，故能快速適應動態變化的網絡。

考慮到擴散過程帶有通信開銷，而無線通信的能耗遠大于計算能耗，因此本文采用定時和事件觸發的方式來選擇發送時機，以減少擴散消息的數量。最近一次擴散消息的發送時間以及包含的信息素值和能量值都會被記錄。一旦間隔上次擴散達一定時間，或者當前最佳信息素值或能量值的變化量超過預設的閾值，都會觸發擴散行為。擴散過程還可用于檢測通信鏈路的狀況，能及時反映出網絡結構的動態變化。當節點i連續長時間未接收到節點j的擴散消息，可認為通信鏈路(i，j)存在問題，或嘗試修復，或踢除其鄰居關系。

2.2 路由優化

類似于基本蟻群路由算法，源節點發送前向螞蟻，但前向螞蟻在選擇下一跳節點時應兼顧虛擬信息素，使得系統可以快速啟動，并更好地適應網絡拓撲和能量水平的動態變化，如式(7)所述。當前向螞蟻到達目的節點后，則原路返回并更新實際信息素，與基本蟻群路由的更新過程相同。

目的節點d的鄰居節點i因擴散過程的作用，總是接收到由d擴散的固定量的信息素，并在路由系統啟動時得到與虛擬信息素等值的實際信息素。隨著路由優化過程的不斷迭代，人工螞蟻會在節點i上播撒實際信息素，使實際信息素的濃度超過虛擬信息素。于是，實際信息素將被選為最佳信息素，并繼續擴散開來，影響外圍節點的虛擬信息素。

2.3 數據傳輸

數據包的傳輸根據實際信息素來選擇下一跳節點，其概率如式(1)所述，但式中的參數α和β可以與路由優化過程有所不同，即根據數據傳輸的需要來權衡實際信息素和剩余能量的重要性。

隨著數據傳輸的不斷進行，目的節點周圍區域承受的通信流量較大，使外圍節點的能量水平顯著大于目標附近的節點，這就可能導致數據包偏向于朝相反方向進行傳遞。雖然可通過更多的螞蟻來加大信息素濃度差，但其通信開銷較大。由于數據傳輸本身存在概率選擇，且其傳輸服務的質量可為路由提供參考，因此本文在DBACRA算法的基礎上提出帶有獎懲機制的DBACRA-PP算法(DBACRA with Premium-Penalty)，根據傳輸情況對實際信息素進行獎懲，從而優化路由。當某條通信路徑的數據流量每達到一定額度就給與其獎勵，這使得目的節點附近獲得較多獎勵，更有利于吸引數據朝目的節點傳遞。此外，當某條通信鏈路不穩定，出現較多丟包時，可對其實際信息素采取適當懲罰。這種獎懲機制只需付出較小的計算開銷，就能使得數據傳輸服務支持路由的更新。

3 仿真實驗與結果分析

為了驗證本文所提路由算法的性能，在TinyOS操作系統中分別實現BACRA協議、DBACRA協議、DBACRA-PP協議以及CTP協議。CTP協議［14］是無線傳感網中較為常用的路由協議，它是基于樹的，為網絡節點提供到根節點的全力的，任意傳播的傳輸機制。本文的仿真環境采用TOSSIM平臺，可以支持大規模的網絡仿真。為使仿真服務更貼近真實環境，加載斯坦福大學Meyer圖書館的噪聲數據，從而模擬出射頻噪聲及節點間的相互干擾［15］。

仿真采用100個節點，使其均勻隨機地分布在100×100單位區域內。節點最大傳輸距離約為20個單位。假設源節點與目的節點具有充足的能量供應，分別位于正方形區域的左下角與右上角。其他節點的初始能量為10 000單位，發送和接收一個消息消耗5單位。源節點每隔1s產生一個數據包，仿真持續到出現第一個能量耗盡的節點，并將該持續時間定義為網絡生命周期。本實驗中，其余參數選取如下:α=2，β=4，ρ=0.9，η=0.2(經過多次實驗對比，當取得這些參數時系統性能較好);獎懲機制的獎勵與懲罰的比例均為5%。假設源節點在發送數據前，已成功完成20次螞蟻迭代，隨后每30個數據包發送一個前向螞蟻，其仿真性能如表1所示(表中數據均由50次仿真結果取平均值獲得)。

表1 路由算法性能比較

由表1可看出，DBACRA協議的生命周期相比BACRA協議提高12%，在端到端的平均時延方面也顯著縮短了15%。平均能耗指傳輸一個數據包需要消耗的全網能量?？梢?，DBACRA協議由于平均時延大大縮短而使平均能耗減少了10%左右。DBACRA-PP協議與DBACRA協議相比，在生命周期方面的優勢較明顯，可見獎懲機制具有一定的路由優化能力。與CTP協議的比較可看出，CTP協議在平均時延和能耗方面有著顯著優勢，這是因為其路徑優化沒有考慮能量因素，易收斂于局部路徑。這會導致其快速耗盡少數節點的能量，故生命周期僅為蟻群算法的一半?？紤]到算法差別較大，下面不再與CTP協議作仿真對比。

進一步，研究初始螞蟻的迭代次數對蟻群路由協議性能的影響。圖1給出了不同初始螞蟻情況下的平均時延。初始螞蟻越少，改進協議的平均時延與BACRA協議就相差越大。這是由于改進協議的擴散模型可以快速建立路由梯度，而BACRA協議需多次迭代后才能優化信息素的分布。值得注意的是，DBACRA-PP協議相比DBACRA協議只有略微的優勢，但在初始螞蟻較少時效果較明顯。

圖1 不同數量初始螞蟻下的平均時延比較

圖2表示三種路由協議運行過程中的時延變化情況。BACRA協議在啟動后迅速收斂，故時延下降較快，但仍顯著大于改進協議。在運行900s后，BACRA協議逐漸收斂于局部較優解，在縮短時延的同時，導致部分節點的能量快速消耗，運行時間縮短。改進協議能更好地適應全網能量的動態變化，故有較長的生命周期。DBACRA-PP協議由于采用獎懲機制降低了數據包反向傳遞的概率，故其傳輸時延比DBACRA協議稍好。

圖2 端到端傳輸時延的變化

4 結論

針對無線傳感網能量有限、動態變化的特點，本文提出一種基于蟻群算法的路由協議，采用信息素擴散模型，由實際和虛擬兩種信息素共同指引螞蟻和數據的偏向性路徑搜索。信息素的擴散有利于路由系統的快速啟動，并能及時適應網絡拓撲和能量水平的動態變化。另外，根據數據傳輸的情況對信息素采取適當的獎勵與懲罰，使得數據傳輸支持路由更新。經仿真驗證，改進協議具有較強的適應性，能較好地均衡全網能耗，有效延長整個網絡的生命周期。

［1］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proc.of the 33rd Annual Hawaii Int Conf.on System Sciences.Maui:IEEE Computer Society，2000:3005－3014.

［2］Jing Yang，Yi Lin，Weili Xiong，et al.Ant Colony-Based Multi-Path Routing Algorithm for Wireless Sensor Networks［C］//Proc.of the International Workshop on Intelligent Systems and Applications.Wuhan，2009:1－4.

［3］Hedetniemi S，Liestman A.A Survey of Gossiping and Broadcasting in Communication Networks［J］.Networks，1988，18(4):319－349.

［4］Lindsey S，Raghavendra C S.PEGASIS:Power-Efficient Gathering in Sensor Information Systems［C］//Proc.of the IEEE Aerospace Conf.Montana:IEEE Aerospace and Electronic Systems Society，2002:1125－1130.

［5］Jelmer van Ast，Robert Babuska，Bart De Schutter.Particle Swarms in Optimization and Control［C］//Proceedings of the 17th World Congress The International Federation of Automatic Control.Seoul，Korea，July 6－11，2008:5131－5136.

［6］Lopez C I L，van Willigenburg L G，van Straten G.Efficient DifferentialEvolution AlgorithmsforMuhimodalOptimalControl Problems［J］.Applied Soft Computing，2003，3(2):97－122.

［7］Liu Lu，Qi Luo，Junyong Liu，et al.An Improved Particle Swarm Optimization Algorithm［C］//Granular Computing，IEEE International Conference.2008:486－490.

［8］段海濱.蟻群算法原理及其應用［M］.北京:科學出版社，2005.

［9］Kalaavathi B，Madhavi S，VijayaRagavan S，et al.Review of ant based routing protocols for manet［C］//Proc.of the 2008 Int Conf on Computing，Communication and Networking.Thomas，2008:1－9.

［10］Wei Gao，Qinglin Sun，Zengqiang Chen.Optimal Energy Consumption in Wireless Sensor Networks by Using the Ant Colony Algorithm(ACA)［C］//Interational Conference on Computer and Communication Technologies in Agriculture Engineering.Chengdu，2010:189－192.

［11］Camilo T，Carreto C，Silva J，et al.An Energy-Efficient Ant-Based Routing Algorithm for Wireless Sensor Networks［C］//Proc.of the International Workshop on Ant Colony Optimization and Swarm Intelligence.Brussels，2006:49－59.

［12］王結太，許家棟，徐建城.基于蟻群優化算法的無線傳感器網絡路由協議［J］.系統仿真學報，2008，20(18):4898－4901.

［13］Colorni A，Dorigo M，Maniezzo V.Distributed Optimization by Ant Colonies［C］//Proc.of ECAL91-European Conference on Artificial Life.Paris，France:Elsevier Publishing，1991.134－142.

［14］Omprakash Gnawali，Rodrigo Fonseca，Kyle Jamieson，et al.Collection Tree Protocol［C］//Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems(SenSys)，2009.

［15］Philip Levis，Nelson Lee，Matt Welsh，et al.TOSSIM:Accurate and Scalable Simulation of Entire TinyOS Applications.Proc.of the First ACM Conference on Embedded Networked Sensor Systems.New York，2003:126－137.