WSN中基于改進蟻群的能量優化路由算法

蔣占軍,周 濤,楊永紅

(蘭州交通大學 電子與信息工程學院,蘭州 730070)

0 概述

無線傳感器網絡(Wireless Sensor Network,WSN)由大量的微型節點組成,其依靠微電池供電,組網靈活、成本較低,廣泛應用于野外監測、抗震救災等場景中。然而,大部分節點分布在荒野地區,一般情況下無法及時更換[1],一旦節點損壞,將對網絡產生重大影響,特別是當關鍵節點因能量耗盡而失效時,會出現“熱點”問題,網絡的連通性被破壞而進入癱瘓狀態。因此,降低節點能耗、優化網絡路由,從而延長網絡壽命是亟待解決的一個問題。

針對上述問題,國內外專家學者對原有的路由協議提出許多優化方案。然而,與傳統的路由協議相比,WSN通過節點間的主動探索來完成通信任務,但節點的計算和存儲能力有限,只能存儲相鄰節點的路由信息。生物智能算法因其能有效地完成WSN中的分簇與路徑規劃任務而受到廣泛關注。其中最具有代表性的是基于蟻群優化(Ant Colony Optimization,ACO)的WSN路由算法,其利用蟻群的智能功能高效地在復雜的網絡拓撲中找到最優路徑。此外,ACO具有正反饋、分布式并行計算機制和魯棒性強等特點,在WSN中易于實現。因此,研究人員通常使用ACO來解決WSN路由中的能量利用問題。

ARA(Ant-based Routing Algorithm)[2]是最早將ACO應用到移動自組織網絡中的被動式多路徑路由算法。該算法通過減少數據包類型,在節點信息素低于某個閾值時進入休眠模式以節約能量,但節點間存在不必要的網絡開銷和時延。IARA(Improved Ant-based Routing Algorithm)[3-4]對ARA中的冗余鄰居節點進行篩選,采用角度因子和距離因子限制搜索方向,避免無關路徑的產生,但該算法的節點計算復雜度高、收斂速度慢。LEACH-VA(Low-Energy Adaptive Clustering Hierarchy Voronoi Algorithm)[5]是一種基于分層結構的路由協議算法,其純粹利用幾何關系改進螞蟻包的數據結構和信息素更新規則,在簇內運用多跳的路由方式進行傳輸,引入尋徑螞蟻收集跳數信息以及所經路徑對其他路徑的負反饋條件,綜合多方面因素規劃路由,得到全局最優解。但是,LEACH-VA算法存在頻繁的動態分簇,導致能量浪費。ARAMA(Ant Routing Algorithm for Mobile Ad-hoc)[6]利用梯度值對節點中的路由表進行更新,其缺點是在大型網絡中,隨著每個螞蟻的記憶列表變長,節點間傳輸螞蟻包的能耗會增加。EEABR(Energy-Efficient Ant-Base Routing)[7]將節點平均能量水平與螞蟻經過的跳數引入ACO的信息素增量公式中,并在節點上將螞蟻攜帶的信息進行融合,可減少節點傳輸的數據量。但是,EEABR在螞蟻靠近Sink節點等較為密集的區域時存在頻繁的數據轉發,若單純通過加減運算進行更新,其結果不夠準確且消耗的能量較多。此外,由于螞蟻包中只存放2條節點ID信息,易形成螞蟻環路,不利于全網能量均衡。IEEABR(Improved Energy-Efficient Ant-Base Routing)[8]在設計報文時,分別定義了2類螞蟻的數據結構,將鄰居節點的剩余能量引入螞蟻路徑的鏈路啟發信息公式中,減少在尋路過程中選擇能量較小的下一跳節點概率。在信息素更新公式方面,IEEABR的尋徑螞蟻與回退螞蟻使用不同的更新公式,引導后來的螞蟻選擇能量較大的鄰居作為下一跳。IEEABR的缺點在于ACO中的信息素更新是一個正反饋過程,螞蟻完成最短路徑的搜索后會聚集在該路徑上,造成最佳路徑節點能量耗盡而過早死亡,而非最佳路徑的信息素濃度釋放量不斷減小。同時,隨著時間推移,該算法會導致路徑荒廢但節點能量充足。

本文在IEEABR算法的基礎上,提出一種增強型的能量優化路由算法E-EEABR。在尋找下一跳節點時綜合距離帶、搜索角度和距離因子3個因素選取下一跳節點,利用激勵策略使最優路徑周圍的剩余能量充足,并通過跳數較少的節點來均衡負載過重的“熱”節點的傳輸任務。此外,采用一種含能量因子的偽隨機比例規則策略優化概率轉移函數,降低“熱”節點失效的概率,以增強算法的尋優能力。

1 蟻群算法原理

ACO算法是指WSN中的源節點通過發送人工螞蟻來模擬自然界中的螞蟻。人工螞蟻在尋找食物的過程中,通過分泌高濃度的信息素來吸引更多的螞蟻加入到尋徑路徑中,然后利用算法的正向反饋機制找出一條到達食物的最優路徑。在ACO算法中,螞蟻分為尋徑螞蟻和回退螞蟻2類。螞蟻尋徑原理如圖1所示。

圖1 螞蟻尋徑示意圖Fig.1 Schematic diagram of ant path finding

假設在WSN尋徑的初始階段,節點個數為m,螞蟻個數為n,尋徑螞蟻k從源節點出發,通過式(1)所示的狀態概率轉移公式選擇下一跳節點。式(2)表示螞蟻k對下一跳節點的期望值,一般來講,距離dij(見式(3))越小,螞蟻對下一跳的期望值越大。尋徑螞蟻通過彼此間的自主探索,在經過多個節點后抵達Sink節點,然后在Sink節點消亡,生成回退螞蟻?；赝宋浵佈刂畔⑺貪舛茸畲蟮穆窂交氐皆垂濣c,完成一次尋徑過程。在該過程中,各路徑在初始化時被賦予了相同的信息素濃度τij(t)=C且其會以一定的速度揮發。在回退螞蟻返回更新的信息素時,各路徑由于自身距離、剩余能量等因素存在差異,導致計算的信息素增量也不相同,得到較優解的路徑擁有的信息素濃度更高,吸引更多的螞蟻,而剩余路徑的信息素則不斷揮發。ACO的這種正反饋機制使得螞蟻可以不斷探索最優路徑。

(1)

(2)

(3)

目前,蟻群算法基本模型有3種,其信息素更新策略各不相同,主要差別在于Δτij(t)求法不同[9]。本文采用蟻量(Ant-Quantity,AQ)模型,按照式(4)～式(6)進行信息素更新,使路徑上的每個節點都能生成一個相應的路由表,其中包含該節點到下一跳節點的相應信息。

τij(t+n)=(1-ρ)τij(t)+Δτij(t)

(4)

(5)

(6)

2 ACO的作用

在ACO算法中,螞蟻根據信息素濃度、能量等啟發式信息來規劃最優路徑[10]。將ACO應用到WSN中是為了利用ACO的自組織性、正反饋性和魯棒性等,降低路由過程中的能量消耗[11]。在WSN中引入ACO的原因主要有以下4點:

1)節點能量有限

WSN中的節點能量、存儲容量有限,運算資源相對匱乏,在設計WSN路由協議時,需優先考慮路由過程中的節點能耗與負載均衡問題。將ACO引入到WSN路由中,利用其群體智能特征可自主地尋找最優路徑,節省節點能量,平衡網絡負載。此外,ACO算法簡單,更容易實現。

2)自組織網絡

WSN的傳感器節點通過飛機播撒的方式投放到野外環境中,隨機性強且各節點之間無固定的中心,需根據野外環境、拓撲規則以及路由算法,在無人監管的條件下,自主生成一個網絡,完成各項任務。ACO中的螞蟻通過正向反饋原則逐步探索,獲取最優路徑。在尋徑螞蟻找到最優路徑后,會吸引更多的螞蟻參與到該路徑中,可以在得到最優路徑的同時,提高節點能量的利用率。

3)網絡結構的動態性

WSN中的節點由于能量耗盡或不能及時更換,導致部分節點死亡,加上通信環境和應用場景的變化等因素,使得WSN的拓撲結構會經常發生變化,ACO利用其本身的魯棒性,能夠很好地應對這一情況。在網絡拓撲發生變化時,螞蟻采用啟發式的路徑搜索方式,及時做出調整并再次尋找最優路徑,其適應性較好且反應速度較快。

4)多跳傳輸

多跳傳輸是通過多個節點的協助轉發到達Sink節點,這種通信方式能夠有效地利用全網絡資源,盡可能以低能耗、短時延在復雜的拓撲中找到最優路徑。在多跳傳輸的過程中,如何選擇合適的下一跳節點是路由算法中影響能耗的一個重要問題。在WSN中引入ACO算法,可以根據節點信息素、剩余能量等因素來進行決策,經過多輪執行后,逐漸接近最優路徑,減少尋找最優路徑的時間和能耗,平衡網絡負載。

3 E-EEABR算法

3.1 網絡距離帶和搜索角度

在經典的蟻群算法中,螞蟻下一步的轉移由狀態轉移概率函數決定,該函數取決于下一跳節點對螞蟻的啟發作用和信息素濃度,而信息素濃度的使用導致在尋徑后期易陷入局部最優路徑[9]。此外,無線傳感器節點數量巨大且隨機分布,節點會因能量耗盡而失效,同時會有新節點加入通信過程中,使得WSN的網絡拓撲經常性發生變動。因此,若螞蟻在尋找下一跳節點時沒有明確的目的,則既浪費了節點能量又延長了尋徑時間[10]。為了充分利用有限的節點能量和當前的信息素濃度,在蟻群路由優化算法中引入距離帶的概念[11],優化螞蟻尋找下一跳節點的方式,避免節點的盲目轉發,其原理如圖2所示。

圖2 距離帶示意圖Fig.2 Schematic diagram of distance band

在圖2中,假設處于n層的節點i為源節點,它在選擇下一跳節點時,限定只能選擇當前層n或鄰近層n-1、n+1內的節點,則其鄰近節點只有節點A～節點F和節點j。按照上述規則,節點i的下一跳節點只能選擇鄰近層節點,即節點A～節點F和節點j,而不能選擇節點G,即將遠離源節點i的節點排除出去。同時,該方法可減少螞蟻向Sink節點轉移的跳數和能耗。由于節點A距離Sink節點較遠,節點i下一跳的重點選擇對象集中在節點B、節點C、節點D、節點E、節點F和節點j。

然而,依靠距離帶只能決定下一跳節點的選擇區域,并不能確定最佳路徑的方向。現有的蟻群優化算法在選取下一跳節點時,并沒有考慮該節點是否靠近Sink節點,導致尋徑螞蟻有時會選擇與Sink節點相反的方向,產生無關路徑,浪費節點能量。因此,在距離帶的基礎上引入搜索角度的概念,具體原理如圖3所示。

圖3 搜索角度示意圖Fig.3 Schematic diagram of search angle

本文通過計算源節點i到Sink節點的連線與源節點i到下一跳節點連線的夾角,結合角度因子和距離因子來確定最佳路徑方向。搜索角度一般限制在0°～90°,θ越小表示螞蟻從源節點i到Sink節點的距離越接近直線,在尋徑過程中,節點越靠近源節點i到Sink節點間的直線,能量消耗越少,則其成為下一跳節點的概率越大。從圖2可以看出,0°<θ1<θ2<θ3<θ4<90°,其中,θ1最小表示節點j成為下一跳節點的可能性最大。

3.2 改進的路徑啟發函數

雖然上述方案能夠精確引導螞蟻尋找下一跳節點,但是當多個候選節點的角度和距離相差不大時,節點之間會出現回旋式跳轉以及能耗不均等問題。尤其是Sink節點附近的“熱”節點相比其他位置的節點,更容易因負載過重而導致出現能量“熱區”。當這些節點的能量耗盡后,網絡的連通性被嚴重破壞,出現“熱點”問題,使網絡進入癱瘓狀態。“熱點”問題的出現在一定的程度上降低了ACO自身的搜索速度和收斂速度,網絡的生存周期也受到影響[12]。

為有效地解決Sink節點附近“熱”節點的失效問題,本文采用一種激勵策略,篩選出能量較低且距離較遠的“熱”節點,并禁止其加入到傳輸路徑中。同時,把剩余的能量充足且距Sink節點較近的節點加入到傳輸路徑中,以均衡“熱”節點的平均剩余能量,延長網絡的生存時間。該策略的主要原理如圖4所示。

圖4 激勵策略示意圖Fig.4 Schematic diagram of incentive strategy

(7)

假設D、E、Sink節點處在網絡節點能量傳輸負載過重的“熱區”中,并且節點D和節點E是利用距離帶、搜索角度和距離因子篩選出來的距離Sink節點最近的“熱”節點,當節點D、節點E與Sink節點的距離較近時,會存在能耗不均和回旋式跳轉等問題。

圖5 節點激勵值更新示意圖Fig.5 Schematic diagram of incentive value update of node

從上述分析可以得出,本文提出的激勵值策略與原始ACO算法通過信息素濃度與啟發函數的大小進行交流相比,螞蟻更傾向于更新短路徑上的信息。同時,該策略使得螞蟻之間的交流除了依靠信息素之外,還會參考訪問過的節點信息,從而能夠平衡Sink節點周圍的整體能量水平,促進螞蟻之間的交流,加快算法的收斂速度。

為更好地利用激勵值,避免由于“熱”節點的失效而出現網絡空洞現象,引導螞蟻更趨向于Sink節點,本文提出的優化信息素啟發公式如下:

Ωi,Sink=di,j+dj,Sink

(8)

(9)

3.3 狀態轉移公式改進

在WSN路徑建立的初始階段,各路徑信息素和啟發函數的作用區分不明顯,導致信息素對路徑建立的作用很小,尋徑螞蟻難以在短時間內搜索到一條到Sink節點的最優路徑。大多數現有的改進算法在確定下一跳節點的概率時,只考慮源節點與候選節點的距離以及信息素濃度2個方面,并沒有考慮候選節點的剩余能量大小、是否與Sink節點同徑等因素,造成長度較短且剩余能量充足的路線被大量螞蟻頻繁訪問,節點能量損耗嚴重,失效節點數目增多[13]。

針對上述問題,本文引入一個含能量因子的偽隨機比例(見式(10)和式(11))估測策略來優化狀態轉移公式[14],使得螞蟻能夠在算法初期各路徑信息素和啟發信息作用不明顯的情況下,快速集中到概率最大的路徑上,提高算法的收斂速度。同時,平衡最優路徑上節點能量較少但螞蟻頻繁訪問的節點的能耗,延長網絡壽命,避免算法出現過早停滯的現象[15]。

(10)

(11)

其中,q是尋徑螞蟻在選擇下一跳節點之前產生的一個隨機數,且q∈(0,1],q0∈[0,1],α、β、γ分別是信息素濃度、啟發函數和能量影響因子的權重系數,其數值越大,說明該項被重視的程度越高,Ei(t)表示源節點i的剩余能量,Ej(t)表示候選節點j的剩余能量。若螞蟻在當前節點產生的隨機數q滿足q≤q0,則選擇[τij(t)]α[ηij(t)]β[κij(t)]γ最大的節點作為下一跳,否則按照式(12)選擇下一跳。

(12)

在改進的狀態轉移函數中,尋徑螞蟻在尋找下一跳節點時,首先根據距離帶和搜索角的規則,對源節點附近的節點進行篩選,然后考慮下一跳節點的信息素濃度、剩余能量等影響因素。通過上述兩個步驟,進一步優化節點概率選擇,避免網絡延時、不必要的能耗和局部最優等問題。尋徑螞蟻能夠根據自身位置與下一跳節點之間的關系進行自適應調節,使得下一跳能量充足且距離Sink節點較近的節點加入到螞蟻的最優路徑中,避免由于最優路徑上節點負載過重導致出現網絡癱瘓的問題。

3.4 信息素更新規則改進

尋徑螞蟻從源節點出發到達Sink節點后,Sink節點會根據尋徑螞蟻包攜帶的信息,計算螞蟻經過的路徑長度以及路徑中的信息素濃度,并將計算結果反饋給回退螞蟻,完成信息素更新。當回退螞蟻到達源節點后,一次完整的螞蟻包收發過程結束,同時算法完成一次路由優化,源節點將回退螞蟻消亡并生成新的尋徑螞蟻進行下一輪的路徑尋優,如此重復循環此過程,直至達到算法設置的最大迭代次數,找到最優路徑[16]。

然而,從ACO的生物特性上講,螞蟻的信息素更新是一個正反饋過程,螞蟻在完成最短路徑搜索后,利用釋放的信息素吸引大量螞蟻加入此路徑,造成該最“佳”路徑的節點能量耗盡而過早死亡[17]。此外,從算法運行的角度來講,傳統ACO的信息素采用累加的方式,不斷地增加上一輪找到的最優路徑上的信息素濃度,導致算法容易陷入局部最優,而不是全局最優。特別地,對于Sink節點附近分布比較密集的“熱”節點來講,雖然它們的信息素濃度以一定的速度揮發,但信息素增加次數高于揮發量[18],且網絡節點的能量充足。此時,距離Sink節點最近的非最佳路徑會成為螞蟻進行下一跳的最佳路徑。同時,源節點到Sink節點的路徑上還存在能耗不均、網絡全局活躍度低等問題,而在Sink節點附近的“熱區”內,存在路由跳數較多、節點間隔較小的路徑,影響Δτk的準確性[19]。

本文利用節點能量與平均能量的偏離值作為信息素增量公式的參考因子。當偏離值較大時,增加的信息素會相應地減少,使得回退螞蟻能夠自適應地進行調整,避免源節點在發送下一輪螞蟻包時加入到能量相差過大的路徑中。具體計算過程如下:

τij(t)=(1-ρ)×τij(t)+Δτij(t)

(13)

(14)

其中,Fdk表示尋徑螞蟻的能量消耗,σk(s)表示回退螞蟻k從Sink節點回到源節點時,源節點的能量es與路徑平均能量Eavg k的偏離值,σk(s)的計算過程如下:

σk(s)=(es-Eavg k)2

(15)

信息素函數的增量計算如下:

(16)

通過對信息素公式進行優化,使得通過路徑上節點剩余能量較大時積累的信息素增多[20],從而有效避免路徑上能量較少的節點因負載過重而失效,同時提高對非最佳路徑的信息素補償,有效地解決全局網絡的能量均衡問題。

4 算法流程

4.1 具體實現步驟

本文E-EEABR算法的具體實現步驟如下:

步驟1初始化各項參數。在t=0時刻,設置節點的初始能量為E0,初始信息素濃度τij(0)=0,迭代次數為N=0,允許最大迭代次數為Nmax。

步驟3螞蟻按照k=k+1搜尋路線。

步驟6判斷螞蟻是否到達Sink節點,即k

步驟7繼續執行步驟1～步驟6,直到k只螞蟻都能到達Sink節點。

步驟8判斷區域內螞蟻可能經過的路徑,如果有螞蟻,則利用式(13)和式(14)進行信息素更新。

4.2 改進的E-EEABR算法流程

本文改進的E-EEABR算法流程如圖6所示。

圖6 E-EEABR算法流程Fig.6 Procedure of E-EEABR algorithm

5 仿真結果與分析

本文在Matlab 2016a環境下進行仿真,并將E-EEABR算法與IEEABR算法、IARA算法進行對比。為了確保仿真結果的穩定性與可靠性,取多次仿真結果的平均值,并分別從路徑平均跳數、節點平均能量消耗、網絡能耗方差、網絡生命周期4個方面驗證E-EEABR算法的有效性。本文使用First-order Radio Model(FRM)能量傳輸模型。仿真參數設置如表1所示,傳感器節點在100 m×100 m區域內隨機分布,螞蟻遍歷次數Nmax=30。

表1 仿真參數設置Table 1 Simulation parameter settings

5.1 路徑平均跳數

路徑跳數可以反映算法中螞蟻尋找最優路徑的能力。圖7給出3種算法平均路徑跳數的變化趨勢。可以看出,IEEABR、IARA和E-EEABR算法分別在第25跳、第18跳和第13跳時達到收斂,說明E-EEABR算法相比其他2種算法,能夠降低數據包的丟失率,提高數據的傳輸效率。

圖7 路徑平均跳數對比Fig.7 Comparison of average hop counts of paths

5.2 節點平均能量消耗

網絡生存周期與總能量消耗成反比,網絡節點的總能耗越小,網絡生存周期越長。圖8給出3種算法的節點平均能量消耗的仿真結果?？梢钥闯?E-EEABR算法的節點平均能量消耗最少,這是因為該算法在計算下一跳節點的轉移概率之前,采用含能量因子的偽隨機比例規則策略對下一跳節點進行篩選,避免了對無關路徑的搜索,減少冗余節點的網絡開銷和能量的傳輸損耗。IEEABR算法和IARA算法在選擇下一跳節點時重點關注與下一跳節點的距離以及剩余能量的大小,導致螞蟻在尋徑時產生大量的無關路徑,增大節點能量的損耗[20]。

圖8 節點平均能量消耗對比Fig.8 Comparison of average energy consumption of nodes

5.3 網絡能耗方差

在WSN中,由于節點隨機分布、環境復雜多樣,因此網絡區域內各節點能耗也不盡相同。對于新部署的網絡或者某些由于大量節點失效而必須重新部署的區域,必須要考慮整體節點的均衡程度。能耗方差常用來反映WSN整體節點的均衡情況,網絡能耗的方差越小,表示網絡區域內的能耗越均衡。本文從E-EEABR的30輪遍歷結果中隨機抽取10輪的節點總能量損耗,然后對3種算法的能耗方差進行對比,結果如圖9所示。

圖9 網絡能耗方差對比Fig.9 Comparison of variance of network energy consumption

可以看出,E-EEABR算法的方差最小,其主要原因是另外2種算法在尋找下一跳時,可能會選擇那些距離較遠且與最優路徑偏差較大的節點,導致大量無關路徑產生,能量損耗較大。此外,IEEABR和IARA算法采用累加的信息素更新方式,螞蟻尋徑過程經常陷入局部最優,能耗均衡性差,而E-EEABR算法中的螞蟻在尋找下一跳節點時,綜合考慮候選節點的剩余能量、距Sink節點的偏離角度等因素,并在信息素更新公式中添加σk(s),當下一跳節點與最優路徑相差較大時,可以及時修正該節點的信息素濃度,優化路徑上節點能量與跳數的關系,在一定程度上均衡網絡能耗。

5.4 網絡生存周期

將網絡區域內的節點數量從100遞增到500,每次增加100個。定義首個節點死亡的時間為網絡生存周期,網絡生存周期的結果對比如圖10所示。可以看出,當節點數量一定時,E-EEABR算法出現首個節點死亡的時間比其他2種算法晚,說明其對網絡的生存周期有延長作用。這是因為E-EEABR算法改進了信息素公式,對最優路徑上的節點進行了篩選。同時,E-EEABR算法的首個節點死亡的時間波動幅度不大,其網絡擴展性和魯棒性較好,而其他2種算法沒有對運行路徑上的低能節點采取維護措施,導致首個節點的死亡時間提前,網絡生存周期縮短。

圖10 網絡生存周期對比Fig.10 Comparison of network lifetime

6 結束語

本文在EEABR算法的基礎上,提出改進蟻群的能量優化路由算法E-EEABR。綜合考慮距離帶、搜索角度和距離因子3個因素,精確選取下一跳路由,利用激勵策略均衡負載過重的“熱”節點的傳輸任務,通過偽隨機比例規則優化概率轉移函數,增強算法的尋優能力。仿真結果表明,E-EEABR算法能夠有效均衡全局網絡能耗,延長網絡生存周期。然而,本文的仿真環境設置較為理想化,未考慮其他因素,如針對Sink節點的逐跳回溯追蹤攻擊等的影響,下一步可對WSN的安全機制進行研究,以提高傳輸可靠性。