基于蟻群優化的無線傳感器網絡路由算法

收稿日期：2014－05－13

基金項目：塔里木大學校長基金（TDZKSS201319）。

作者簡介：鄔歡歡(1982-)，男，新疆阿拉爾人，碩士，講師，主要研究方向: 無線傳感器網絡、分布式信息處理。

摘要：路由技術是無線傳感器網絡（WSNs）的關鍵技術。基于蟻群優化的無線傳感器網絡路由算法具有蟻群算法的自組織、正反饋和并行性的特點，在構造WSNs的最優路由時有很好的性能。介紹了蟻群算法的數學模型，著重從啟發因子的構建方式上描述了當前典型的基于蟻群的路由算法，并比較分析了這些算法的特點及存在問題，在此基礎上給出了設計啟發因子的方法，為進一步研究提供了一些解決思路。

關鍵詞：無線傳感器網絡； 路由算法； 蟻群優化

中圖分類號：TP393文獻標識碼：A文章編號：2095-2163（2014）03-0067-03

Ant Colony Optimization-based Routing Algorithm in Wireless Sensor Networks

WU Huanhuan， ZHANG Ren

(College of Information Engineering， Tarim University， Alar Xinjiang 843300， China)

Abstract：Routing technology is pivotal in the architecture of wireless sensor networks(WSNs). The routing algorithm based ACO(Ant Colony Optimization) has good performance in WSNs，for its server advantages，such as robustness，positive feedback，distributed computing and parallelism. The paper presents analysis of the mathematical model of ant colony algorithm， mainly from the construction method of heuristic factor describes the current typical routing algorithm based on ant colony algorithm.After doing research on typical algorithms，the paper compares their performance，presents a method of designing inspiration factor，and points out some research issues.

Key words：WSNs; Routing Algorithm; ACO

0引言

無線傳感器網絡（wireless sensor networks，WSNs）的應用主要集中在小數據量的低速報文傳送上，但隨著近年物聯網產業的飛速發展，WSNs作為物聯網中主要的信息感知方式，在一些新業務的拓展應用中也需要對實時數據和高速數據源實現可靠的傳輸支持，這就對無線傳感器的網絡能耗提出了更高要求，所以節能研究還有廣闊的探討空間。路由協議是無線傳感器網絡節能研究的重要發展方向，而蟻群優化算法（Ant Colony Optimization)則是由Dorigo M［1］等專家提出的一種基于種群的啟發式仿生優化算法，并且具有自組織、正反饋和并行性等優點。經分析可知，該算法尤其適合于解決無線傳感器網絡的動態路由問題［2-4］。

1蟻群算法的數學模型

將無線傳感器網絡抽象成一個加權圖G=（V，A），其中V是節點的集合，每一個節點具有能量，網絡位置，通信半徑；A為各節點之間邊的集合，每一條邊賦予一定的權重值。利用蟻群算法來求解圖中節點之間最優或次優路徑，在算法的運算中主要展現三個規則，現論述如下：

（1）螞蟻在運動過程中，根據各條路徑上的信息素量和路徑的啟發信息計算狀態轉移概率。在t時刻螞蟻k由節點i轉移到節點j的概率Pkij(t)如式(1)所示。

Pkij(t)=［τij(t)］α·［ηij(t)］β∑l∈Nk(i)［τij(t)］α·［ηij(t)］βj∈Nk(i)

0jNk(i)(1)

其中，τij(t)是信息素值，Nk(i)表示螞蟻k下一步允許選擇的節點，而且是沒有路過的節點；α和β分別是反映信息素軌跡強度和啟發因子相應重要程度的調節參數。

（2）ηij(t)是啟發因子，其構建方式為蟻群算法的優化目標。這里用節點i到節點j之間的距離dij構建，計算方法為dij=(xi-xj)2+(yi-yj)2，則啟發因子的表達式為：ηij(t)=1/dij。在算法中螞蟻會找到一條信息素值最大，距離最短的路徑。

（3）在每只螞蟻走完一步或完成對所有節點的遍歷后，要對所經過節點的信息素進行更新。其表達式為：τij(t+1)=(1-ρ)τij(t)+Δτij(t)。這里，信息素的揮發系數ρ∈［0，1］，1-ρ表示信息素殘留系數，Δτij(t)表示在本次循環中螞蟻在路徑上留下的信息素增量，計算方法為：Δτij(t)=Q/L，其中，Q為本次循環螞蟻所留信息素的總量，L為螞蟻k在本次循環經過路徑總和。

基于蟻群優化算法的無線傳感器路由協議，大多是從啟發因子構建及信息素更新方式等方面進行改進，尋找到較優的路徑進行數據的轉發，以達到降低節點能耗的目標。國內外研究人員已提出許多優秀的算法和協議，下面就目前WSNs中基于蟻群優化的路由協議，分析不同優化策略的實現算法。

2基于蟻群優化的路由算法

基本蟻群算法中的啟發因子ηij(t)關注的是節點間距離，為了設計能量有效的傳感器網絡路由，研究者對啟發因子進行了設計優化，使其能夠反映尋路過程中的節點能量變化情況，并使其對路徑的選擇發生影響。

2.1平面路由改進算法

平面路由中各節點具有相同的功能和平等的角色，數據傳輸通過多節點的多跳路由協作轉發完成。基于蟻群的路由選擇是在網絡中尋找源節點到目標節點之間的較優傳輸路徑，從而均衡網絡節點的能量消耗。參見文獻［5］中即將節點能量作為轉移概率規則啟發因子，具體如式(2)所示。讓螞蟻尋找能量較高的鄰居節點進行下一跳傳輸，并設計了路徑評價函數，在信息素更新時代入，從而加強剩余能量較高的路徑節點的影響和作用。

ηij(t)=1(E0-ej)∑n∈Nk(i)(E-en)-2（2）

其中，E0為節點初始能量，ei為節點當前能量。第3期鄔歡歡，等：基于蟻群優化的無線傳感器網絡路由算法智能計算機與應用第4卷

還有將節點剩余能量和傳輸跳數結合［6-7］的方式來構建啟發函數。在文獻［6］算法中，將螞蟻分為兩類，一類是由源節點出發的尋徑螞蟻，一類是由匯聚節點（sink）回溯到源節點的回退螞蟻。尋徑螞蟻按照轉移概率隨機選擇下一跳節點，其中啟發因子ηij(t)構建如式(3)所示。回退螞蟻則執行信息素更新，更新時將路徑上的節點跳數、平均能量、最小能量引入信息素更新公式求解，權衡了能量水平和跳數水平的組合影響。

ηij(t)=1(1-ej/E0)λ(1-(ΔH+1)/Hi)（3）

式中，ΔH表示節點i與鄰節點j之間的跳數差值，Hi表示節點i距離sink節點的跳數，λ為權重系數，λ取值越大則給予能量更多權重。

文獻［8］考慮了無線信道質量對數據傳輸的影響。網絡中通信質量較差的鏈路，需要多次重發才能成功，如此即耗費了節點能量。該算法基于節點能量以及信道質量來構造啟發函數，如式(4)所示。

［ηij(t)］β=［1(E0-ej)］υa+［C(e)］υb（4）

式中，C(e)為鏈路(vi，vj)的信道質量函數，采用實際信道中的誤幀率或誤比特率來衡量；υa和υb分別表示路徑長度與信道質量的權重因子。算法在信息素更新規則里也考慮了信道質量的情況，選擇了剩余能量較高、信道質量較好的路徑進行數據的路由轉發，有效降低了數據傳輸功耗。

2.2LEACH的改進算法

低能量自適應分簇路由（Low-Energy Adaptive Clustering Hierarch，LEACH）是典型的層次型路由協議，一般包括簇頭產生、簇的形成和穩定數據通信三個階段［9］。基于蟻群的LEACH改進算法結合了分簇算法和蟻群算法的各自優點，有些算法延用了LEACH的分簇思想，有些算法設計了新的分簇方法，但在數據傳輸階段，許多算法［10-11］通過簇間多跳路由來保證節點間的負載平衡，基于蟻群優化算法，通過搜索簇間最優數據傳輸路徑，降低了簇頭節點的能量消耗，并延長了網絡生命周期。

文獻［12］從能量預測的角度，提出了路由協議，即LEACH-ACA協議。協議中設計了能量預測函數，具體為：Ej(t)=Ej-kC，其中，Ej為節點的剩余能量，k為在t時刻前，節點被選中的次數；C為節點轉發一次數據所需的能量，由此構造螞蟻的轉移概率如式(5)所示。

Pkij(t)=［τij(t)］α·［ηij(t)］β∑l∈Nk(i)［τij(t)］α·［ηij(t)］β×Ej(t)Eavgj∈Nk(i)

0jNk(i)（5）

式中，Eavg為所有節點預測能量的平均值。LEACH-ACA協議在螞蟻搜索下一跳時，考慮了節點預期的能量消耗，避免節點過早死亡。

文獻［13］提出了一種負載均衡路由方案（ACOLBR）。在成簇階段綜合考慮了節點的度及其剩余能量進行簇頭的選舉，簇內采用了最小生成樹算法構造簇成員到簇頭節點的路由，簇間則采用了改進的蟻群算法，生成一條最優傳輸路徑。蟻群算法中的啟發因子綜合了能量、距離、帶寬等多個因素的影響，如式(6)所示。

ηij(t)=I［Ej(t)］λ1［d(i，j)］λ2·［1n∑np=1XpB(p)］λ3（6）

其中，0＜I≤1，數據的重要程度越強，I值越大。Ej(t)表示被選節點vj在t時刻剩余能量。d(i，j)為節點vi與vj之間的距離，λ1、λ2和λ3為權重系數。Xi表示節點vi和節點vj在第p次交互的節點狀態信息的信息量，算法中取為固定值。B(p)表示此刻的帶寬。

在LEACH算法基礎上，文獻［14］提出了LEACH-ACANEW算法，引入Dirichlet圖單元的區域劃分，并基于節點剩余能量、網絡平均剩余能量及平均消耗能量的關系對LEACH的閾值函數加以改進，完成簇的建立。在數據通信過程中，考量了節點傳輸速率Tr對節點之間距離d(i，j)和數據處理時延ti的相應影響，設計了啟發因子，如式(7)所示。

ηij(t)=1Ej+Tr×ti×(μ1+μ2(［d(i，j)］))（7）

式中，Ej為節點j在以往過程中消耗的能量，μ1，μ2為相關參數。將啟發因子代入螞蟻轉移概率公式，螞蟻會選擇下一跳鄰居簇頭節點j，節點j將具有如下性質：已消耗的能量較少，數據處理的時延較低，與節點i的通信距離較短。LEACH-ACANEW算法在減少節點能量消耗和延長網絡生命周期方面表現了較好的性能，但在網絡負載均衡方面還需較深入的改進。

另有一些文獻從多個角度構建了啟發因子，如基于路由代價模型［15］，使用節點的地理位置信息［16-17］，基于節點剩余能量的多路徑機制［18-19］，調整節點的發射功率［20］等，都分別設計了能量有效的無線傳感器網絡路由算法。

3問題與對策

綜上所述，基于蟻群的WSN路由算法圍繞節能的目標，分別著眼于不同的側重點改進了啟發因子，各條件之間的度量操作包括最小/最大性、可乘性和可加性等。有些算法結合了多個條件之間的關系，有的算法只關注了能量的影響，這些算法表現出了明確的優勢，但也存在一些問題，對其分析如下：

（1） 多數算法中的仿真模型為100米~200米的范圍，傳感器節點個數有限，若節點個數上升至數百個，則路由算法的運行是否會增加網絡的通信開銷，路由表的更新策略如何設計，并且隨著網絡規模的擴大，對于蟻群算法固有的易陷入局部最優和收斂速度較慢等缺點應該如何克服，以上這些問題都需要更為深入的探討。

（2） 各路由算法在建立網絡模型時，應適當考慮面向應用的實際環境，分析傳感器網絡中各限制條件之間的影響，以及利用蟻群算法正反饋的機制，對滿足約束條件的路徑進行加強，從而達到優化目標。當然，隨著約束條件增多，路由算法的復雜程度也會增加。

（3） 蟻群算法中的規則公式存在參數影響因子，這些參數的取值對算法運行的結果影響很大，一般是通過實驗確定，獲得一個經驗上的取值。基于蟻群的路由算法仿真過程中，應對各參數的取值范圍進行測試分析，以提高算法的魯棒性，使路由協議的擴展性更好。

4結束語

在今后的研究中，路由算法還需要進一步考慮數據融合和QoS等問題。如基于壓縮感知的數據融合算法；面向數據可靠與節能、冗余與延遲之間平衡的QoS路由；以及利用粒子群算法、蟻群算法、遺傳算法等智能算法進行融合求解的WSN路由協議。

參考文獻：

［1］DORIGO M，MANIEZZO V，COLOMI A．The ant system：optimization by a colony of cooperating agents［J］．IEEE Transactions on Systems Man＆Cybernetics B，1996，26(2)：29-41．

［2］LI Hongsheng，LIU Sumin，HU Bing．Design ofnode power management in WSN based on ant colony algorithm［C］//Proc．ofinternational Conference on Networks security ，Wireless communication and trustedcomputing．Washington D．C．，USA：IEEE Computer society ，2009：739-743．

［3］SELCUK O，DERVIS K．Routing in wireless sensor networks using ant colony optimization ［C］//Proceedings of the First NASA/ESA Conference on Adaptive Hardware and Systems. Istanbul，Turkey，2006：401-404．

［4］CAMILO T，CARRETO C，SILVA J s，et a1．An energy-efficient ant-based routing algorithm for wireless sensor networks［C］//International Workshop on Ant Colony Optimization and Swarm Intelligence，2006．Brussels：Springer Verlag，2006：49-59．

［5］尚興宏，錢煥延，高德民．基于改進蟻群優化算法的無線傳感器網絡路由研究［J］．傳感器與微系統，2012，31（9）：36-38．

［6］楊大鵬．基于蟻群優化的能量均衡自適應路由算法［J］．海軍航空工程學院學報，2013，28（1）：90-94．

［7］OKDEM S，KARABOGA D．Routing in wireless sensor networks using ant colony optimization［C］//NASA/ESAConference on Adaptive Hardware and Systems，2006．Istanbul：IEEE，2006：401-404．

［8］李虎雄，張克旺．基于蟻群優化的無線傳感器網絡路由優化算法［J］．西北工業大學學報，2012，30（3）：356-360．

［9］武海艷，宮娜娜，胡愛娜．基于分簇的無線傳感器網絡路由協議［J］．計算機系統應用，2013，22（3）：148-152．

［10］張曉偉．蟻群優化的傳感器網絡路由算法［J］．計算機仿真，2011，28（3）：263-266．

［11］胡彧，王靜．基于蟻群算法的LEACH協議研究［J］. 傳感技術學報，2011，24（5）：747-751．

［12］廖明華，張華，謝建全．基于蟻群算法的WSN能量預測路由協議［J］．計算機工程，2012，38（3）：88-90．

［13］畢俊蕾，李致遠．使用蟻群優化的WSNs負載均衡路由方案［J］．計算機工程與應用，2011，47（18）：80-84．

［14］姬文燕，史長瓊，鄒杰．基于蟻群的區域簇頭選擇路由算法［J］．長沙理工大學學報（自然科學版），2012，9（2）：75-80．

［15］陳鳳超，李融林．基于路由代價的無線傳感器網絡蟻群路由算法［J］．華南理工大學學報（自然科學版），2011，39（5）：36-43．

［16］孫穎．基于蟻群算法的能量均衡傳感器網地理信息路由［J］．沈陽大學學報（自然科學版）2012，24（2）：57-61．

［17］RAHMAN M A，AGHAEIL R G，SADDIKL A E，et al．M-IAR：biologically inspired routing protocol for wireless multimedia sensor networks［C］//Proceedings of the International Conference on Instrumentation and Measurement Technology，Canada，2008：1777-2221．

［18］王敏，李士寧，李志剛．基于蟻群算法的WSN多路徑負載均衡路由［J］．計算機工程，2011，37（14）：1-4．

［19］童孟軍，關華丞．基于蟻群算法的能量均衡多路徑路由算法的研究［J］．傳感技術學報，2013，26（3）：425-434．

［20］黃曼，程良倫．基于蟻群優化的WSN功率自適應路由算法［J］．計算機工程，2012，38（1）：102-104．