基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)路由算法

收稿日期：2014－05－13

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

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

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

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)； 路由算法； 蟻群優(yōu)化

中圖分類號：TP393文獻(xiàn)標(biāo)識碼：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引言

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

1蟻群算法的數(shù)學(xué)模型

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

（1）螞蟻在運動過程中，根據(jù)各條路徑上的信息素量和路徑的啟發(fā)信息計算狀態(tài)轉(zhuǎn)移概率。在t時刻螞蟻k由節(jié)點i轉(zhuǎn)移到節(jié)點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下一步允許選擇的節(jié)點，而且是沒有路過的節(jié)點；α和β分別是反映信息素軌跡強(qiáng)度和啟發(fā)因子相應(yīng)重要程度的調(diào)節(jié)參數(shù)。

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

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

基于蟻群優(yōu)化算法的無線傳感器路由協(xié)議，大多是從啟發(fā)因子構(gòu)建及信息素更新方式等方面進(jìn)行改進(jìn)，尋找到較優(yōu)的路徑進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)，以達(dá)到降低節(jié)點能耗的目標(biāo)。國內(nèi)外研究人員已提出許多優(yōu)秀的算法和協(xié)議，下面就目前WSNs中基于蟻群優(yōu)化的路由協(xié)議，分析不同優(yōu)化策略的實現(xiàn)算法。

2基于蟻群優(yōu)化的路由算法

基本蟻群算法中的啟發(fā)因子ηij(t)關(guān)注的是節(jié)點間距離，為了設(shè)計能量有效的傳感器網(wǎng)絡(luò)路由，研究者對啟發(fā)因子進(jìn)行了設(shè)計優(yōu)化，使其能夠反映尋路過程中的節(jié)點能量變化情況，并使其對路徑的選擇發(fā)生影響。

2.1平面路由改進(jìn)算法

平面路由中各節(jié)點具有相同的功能和平等的角色，數(shù)據(jù)傳輸通過多節(jié)點的多跳路由協(xié)作轉(zhuǎn)發(fā)完成?；谙伻旱穆酚蛇x擇是在網(wǎng)絡(luò)中尋找源節(jié)點到目標(biāo)節(jié)點之間的較優(yōu)傳輸路徑，從而均衡網(wǎng)絡(luò)節(jié)點的能量消耗。參見文獻(xiàn)［5］中即將節(jié)點能量作為轉(zhuǎn)移概率規(guī)則啟發(fā)因子，具體如式(2)所示。讓螞蟻尋找能量較高的鄰居節(jié)點進(jìn)行下一跳傳輸，并設(shè)計了路徑評價函數(shù)，在信息素更新時代入，從而加強(qiáng)剩余能量較高的路徑節(jié)點的影響和作用。

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

其中，E0為節(jié)點初始能量，ei為節(jié)點當(dāng)前能量。第3期鄔歡歡，等：基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)路由算法智能計算機(jī)與應(yīng)用第4卷

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

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

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

文獻(xiàn)［8］考慮了無線信道質(zhì)量對數(shù)據(jù)傳輸?shù)挠绊?。網(wǎng)絡(luò)中通信質(zhì)量較差的鏈路，需要多次重發(fā)才能成功，如此即耗費了節(jié)點能量。該算法基于節(jié)點能量以及信道質(zhì)量來構(gòu)造啟發(fā)函數(shù)，如式(4)所示。

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

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

2.2LEACH的改進(jìn)算法

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

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

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

0jNk(i)（5）

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

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

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

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

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

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

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

另有一些文獻(xiàn)從多個角度構(gòu)建了啟發(fā)因子，如基于路由代價模型［15］，使用節(jié)點的地理位置信息［16-17］，基于節(jié)點剩余能量的多路徑機(jī)制［18-19］，調(diào)整節(jié)點的發(fā)射功率［20］等，都分別設(shè)計了能量有效的無線傳感器網(wǎng)絡(luò)路由算法。

3問題與對策

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

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

（2） 各路由算法在建立網(wǎng)絡(luò)模型時，應(yīng)適當(dāng)考慮面向應(yīng)用的實際環(huán)境，分析傳感器網(wǎng)絡(luò)中各限制條件之間的影響，以及利用蟻群算法正反饋的機(jī)制，對滿足約束條件的路徑進(jìn)行加強(qiáng)，從而達(dá)到優(yōu)化目標(biāo)。當(dāng)然，隨著約束條件增多，路由算法的復(fù)雜程度也會增加。

（3） 蟻群算法中的規(guī)則公式存在參數(shù)影響因子，這些參數(shù)的取值對算法運行的結(jié)果影響很大，一般是通過實驗確定，獲得一個經(jīng)驗上的取值?；谙伻旱穆酚伤惴ǚ抡孢^程中，應(yīng)對各參數(shù)的取值范圍進(jìn)行測試分析，以提高算法的魯棒性，使路由協(xié)議的擴(kuò)展性更好。

4結(jié)束語

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

參考文獻(xiàn)：

［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ìn)蟻群優(yōu)化算法的無線傳感器網(wǎng)絡(luò)路由研究［J］．傳感器與微系統(tǒng)，2012，31（9）：36-38．

［6］楊大鵬．基于蟻群優(yōu)化的能量均衡自適應(yīng)路由算法［J］．海軍航空工程學(xué)院學(xué)報，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］李虎雄，張克旺．基于蟻群優(yōu)化的無線傳感器網(wǎng)絡(luò)路由優(yōu)化算法［J］．西北工業(yè)大學(xué)學(xué)報，2012，30（3）：356-360．

［9］武海艷，宮娜娜，胡愛娜．基于分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議［J］．計算機(jī)系統(tǒng)應(yīng)用，2013，22（3）：148-152．

［10］張曉偉．蟻群優(yōu)化的傳感器網(wǎng)絡(luò)路由算法［J］．計算機(jī)仿真，2011，28（3）：263-266．

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

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

［13］畢俊蕾，李致遠(yuǎn)．使用蟻群優(yōu)化的WSNs負(fù)載均衡路由方案［J］．計算機(jī)工程與應(yīng)用，2011，47（18）：80-84．

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

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

［16］孫穎．基于蟻群算法的能量均衡傳感器網(wǎng)地理信息路由［J］．沈陽大學(xué)學(xué)報（自然科學(xué)版）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多路徑負(fù)載均衡路由［J］．計算機(jī)工程，2011，37（14）：1-4．

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

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