基于自適應剩余能量閾值的WSN蟻群路由算法

王恭, 孫銘陽, 孫匯陽, 張葉, 滕子銘

1.東北電力大學 自動化工程學院, 吉林 吉林 132012; 2.北京電子科技學院 密碼科學與技術系, 北京 100070;3.吉林大學 通信工程學院, 吉林 長春 130012

無線傳感器網絡(wireless sensor network,WSN)是一系列具有通信、計算和感知的傳感器節點所組成的無線網絡,可以在特定條件下為用戶提供數據的收集、計算和傳輸。在實際的應用中,WSN中的節點在工作時,主要依靠自身電池提供有限的能量,不合理的網絡開銷會導致節點過早死亡。因此在選取節點之間通信最優路徑的同時,如何降低網絡開銷,延長網絡生命周期成為近年來研究WSN性能的重要內容。

蟻群算法是由Dorigo等[1]提出的仿生尋優算法,該算法具有正反饋和較強的魯棒性等特點,在解決路徑規劃問題時效果較好。基于該算法的蟻群路由算法被提出后,引發各方學者的廣泛關注。

文獻[2]利用模糊邏輯選擇信道,根據節點的剩余能量與到基站的距離將網絡劃分成不相等的簇,預先粗略篩選下一跳節點,從而在算法收斂速度上有一定優勢,但因為模糊邏輯的不確定性,容易使算法陷入局部最優。文獻[3]在選擇簇頭時,利用EPO算法查找簇頭到匯聚節點間的最優路徑。文獻[4]將部署節點的區域劃分為不同層級,根據博弈論模型選擇簇頭,該算法有效提高網絡生命周期,但尋優效果不理想。文獻[5]通過鄰居節點提供到達目的節點需要的網絡開銷的預估值,遞增地計算出到達目的節點所需的所有路由成本,最終篩選出最優解。文獻[6]利用分段更新規則優化信息素更新公式,但從全局的角度來看容易使網絡陷入局部最優。

文獻[7]將蟻群算法與鯨魚算法相結合,將具有最大適應度值的路徑作為最優路徑。文獻[8]利用數據聚合來提高節點能量利用率,通過評估節點剩余能量與匯聚節點的位置來確定最佳路由。文獻[9]將蟻群劃分為引導層螞蟻和普通層螞蟻,在設計上加強引導層螞蟻對匯聚節點的吸引力,充分發揮了不同層螞蟻在搜索過程中的協作優勢,避免陷入局部最優解。文獻[10]將群集和多跳路由技術相結合,同時利用動態選取法引入休眠節點，從而平衡網絡中節點能量,提高網絡生命周期時間。文獻[11]利用雙子蟻群沿預定方向進行聯合搜索,提高算法搜索效率,但網絡生命周期較短。

綜上所述,現有蟻群路由算法及其優化算法在大型光伏發電系統狀態監控中存在容易陷入局部最優、網絡生命周期較短等問題。針對這些實際問題,本文提出了一種基于自適應剩余能量閾值的WSN蟻群路由算法(an adaptive threshold of remaining energy based ant colony routing algorithm,ATRE-ARA)。通過優化自適應閾值、設置信息素上限和下限,提高信息素的準確性,平衡算法的局部和全局搜索能力。同時改進信息素啟發函數,引入搜索角和下一跳節點距離,避免數據在節點間發生回旋,提高算法尋優效率,減少節點網絡開銷,延長網絡生命周期。

1 系統模型

1.1 數學模型

本文將WSN描述為一個無向加權圖G,如(1)式所示。

G=(V,E)

(1)

其中頂點V表示為網絡中所有節點的集合,如(2)式所示。

V={v1,v2,…,vr,vs,…,vn}

(2)

E為節點間所有鏈路的集合,如(3)式所示。

E={e12,e13,…,ers,…,ejk}

(3)

假設d(r,s)表示節點r到節點s的距離,R為節點間有效通信距離,且節點r和節點s之間的鏈路為ers,分別由公式(4)和(5)表示。

C為WSN中所有可能存在鏈路的節點集合,如(6)式所示。

crs=c(vr,vs)∈C

(6)

確定在網絡中任意兩節點之間是否存在有效鏈路,可以用公式(7)表示。

(7)

節點r和節點s存在有效鏈路時,表示為1,否則為0。假設網絡中有且僅有1個匯聚節點z,z∈V。W為網絡中源節點的集合,如公式(8)所示。

W={w1,w2,…,wr,ws,…,wn-1}∈V-{z}

(8)

1.2 能耗模型

在WSN中,除匯聚節點外,其余網絡中各節點的初始能量為有限值。在節點發送和接收數據時都會損耗自身能量。本文采用的無線電能耗模型[12]如圖1所示。

圖1 無線電能耗模型

當節點發射數據包a時,能量損耗發生在信號發射和信號放大2個階段。信號發射階段的能耗由數據包a的大小決定,信號放大階段的能耗主要由發射器和接收器之間的距離d(r,s)決定。

接收器在接收數據時的能量損耗由數據包a的大小決定。Etx(a)r為發射器發射能量消耗值,Erx(a)s為接收器接收能量消耗值,具體能量損耗如公式(9)～(10)所示。

(9)

Erx(a)s=Eelec×a

(10)

Eelec為每傳輸1 bit數據所消耗的能量,Eεfs和Eεamp分別代表數據包a在自由空間模型與多徑衰減模型中發射1 bit數據功放所消耗的能量。d0為d(r,s)的距離閾值,如(11)式所示。通過公式可知,發射器發射能量消耗值Etx(a)r隨距離d(r,s)變大而增加。計算(9)式中Etx(a)r的值時,當d(r,s)

(11)

2 ATRE-ARA路由優化算法

由于傳統的蟻群路由算法存在局部節點能量開銷較大和數據在節點間返復回旋等問題,導致網絡生命周期較短和算法容易陷入局部最優。針對以上問題,本文在現有蟻群路由算法的基礎上,提出改進的蟻群路由算法,通過改進信息素更新公式,引入自適應閾值和搜索角,設置信息素上限值和下限值,可以有效降低數據在節點間的回旋,提高全局尋優能力,平衡全局網絡能耗,延長網絡生命周期。

2.1 改進信息素更新策略

算法每次迭代后,路徑上的信息素值都會更新,傳統的蟻群算法在更新信息素時沒有對信息素值進行限制。在算法初期,容易出現因局部路徑信息素值過大或過小,而導致陷入局部最優解。本文通過改進已有信息素公式,設置信息素上限值Tmax和信息素下限值Tmin,提高選擇其他路徑的概率。防止在算法迭代初期,因局部路徑信息素差值過大,陷入局部最優,增加了算法搜索全局最優的能力。改進的信息素公式如(12)式所示。

Ta+1(r,s)=

(12)

δ=ρ(1+lg(n))

(13)

Ta(r,s)為螞蟻a儲存在節點r和節點s路徑上的信息素濃度值或信息素值,信息素濃度存儲在鄰居列表中。ΔTa(r,s)為螞蟻a留在節點r和節點s之間的信息素增量,δ為自適應信息素蒸發系數,如(13)式所示。n為節點路由數,ρ為基本蟻群算法中的信息素蒸發系數,ρ∈ (0, 1)。路由數n的大小與自適應信息素蒸發系數δ正相關。

2.2 改進信息素增量公式

基本蟻群算法在計算信息素增量ΔTa(r,s)時,利用數據包a途徑距離的長度作為衡量信息素增量的標準,即

(14)

式中：Ma為螞蟻a經過所有節點的集合；La為數據包a途經路徑長度,Q為常量。當La值越大時,ΔTa(r,s)值越小,路徑上的信息素Ta(r,s)越小,從而影響數據包a選擇下一跳節點s的概率。傳統的蟻群算法在計算信息素增量時,沒有考量節點剩余能量,容易造成局部節點網絡開銷過大,導致節點過早死亡,影響網絡生命周期。

為進一步提高ΔTa(r,s)的準確性,本文在基礎蟻群算法的基礎上,引入下一跳節點剩余能量Es及其剩余能量的閾值E0,并重新定義信息素增量公式,如(15)式所示。

(15)

式中：Eini是節點初始能量；Es為下一跳節點s的剩余能量；E0為Es的閾值。Efd是前向數據包a所途徑的節點剩余能量之和,即

(16)

Eavg和Emin分別為節點平均剩余能量和最小能量,如(17)～(18)式所示。

式中：Er為節點r剩余能量；Ha為前向數據包a當前跳數。

通過(15)式推導得出,當Eavg>Emin時,Efd值越大,所對應路徑的ΔTa(r,s)值越大。在計算ΔTa(r,s)時,引入Efd可以平衡全局網絡節點剩余能量,提高前向數據包a在計算下一跳概率公式時，選擇剩余能量較多節點的概率。

在算法迭代過程中,考慮到全局網絡能量逐漸減小,閾值E0需要隨節點剩余能量降低而改變,提出自適應函數,如公式(19)所示。

(19)

ω為常數,ω∈ (1, 10)。N為算法迭代次數。由(19)式推導得出,E0隨N增加而遞減,通過更新閾值E0大小,可以有效提高ΔTa(r,s)的準確性。

2.3 信息素啟發函數

蟻群算法中的下一跳概率公式主要由2個關鍵部分組成:備選路徑上的信息素濃度T(r,s)和信息素啟發函數η(r,s)。信息素濃度反映算法在不斷迭代后評判路徑優劣的標準,而信息素啟發函數反映網絡中節點的局部情況。傳統的蟻群算法只考慮下一跳節點剩余能量對信息素啟發函數的影響。而在實際情況中,剩余能量較多的節點往往遠離匯聚節點,單一利用節點剩余能量計算出的信息素啟發函數可靠性不高,最終影響下一跳概率公式的準確率。本文在傳統蟻群算法的基礎上,綜合考慮了下一跳節點剩余能量和節點r到下一跳節點s的距離,改進信息素啟發函數,如(20)式所示。

(20)

式中：Eini為節點初始能量；Es為節點s剩余能量。λ1和λ2分別代表(20)式中2項的權重值,且λ1+λ2=1。參數μ是調整搜索角θ與d(r,s)的權重。θ是節點r到匯聚節點的連線和節點r到節點s的連線的夾角,具體如圖2所示。

圖2 搜索角

d(r,s1),d(r,s2),d(r,s3)分別為節點r到節點s1,s2,s3的距離,θ1和θ2分別是s1和s2到節點r與匯聚節點的搜索角。當角度θ相等時,距離d(r,s)越大,該路徑上的信息素啟發函數值越小;當距離d(r,s)相等時,搜索角度越小,該路徑上的信息素啟發函數值越大。

在算法初期,由于網絡中各節點剩余能量充沛,能量因素對信息素啟發函數影響較小,改進后的算法通過引入搜索角θ和下一跳節點距離d(r,s)對搜尋路徑進行限制,有效減少數據在節點間返復傳輸,降低能量損耗,提高網絡生命周期。

3 改進算法的流程

在WSN中,除匯聚節點外的節點定期向周圍的鄰居節點發送1個數據包,本文將其定義為前向螞蟻a。前向螞蟻a從源節點出發,通過計算下一跳概率公式選擇下一跳節點并更新經過的路徑和節點的信息素濃度,同時前向螞蟻a訪問過的鄰居節點都會以節點標識的形式存儲在鄰居列表中。當前向螞蟻a到達匯聚節點時,匯聚節點接收前向螞蟻a的數據,隨即生成后向螞蟻,利用信息素公式并把計算后的信息素存儲在后向螞蟻中,將數據沿原路徑返回源節點。一次完整的數據收發過程,標志著一次源節點到匯聚節點的信息素更新完畢,隨即算法進行新一輪數據收發過程,算法步驟如下所示。

step 1 建立隨機節點分布圖并初始化各項參數,其中初始迭代次數為0,最大迭代次數為Nmax。

step 2 算法迭代次數加1。每一波次出動m只螞蟻隨機部署在M個節點上,且每只螞蟻將經過的節點信息存儲在鄰居列表中。

step 3 螞蟻a在節點r,利用下一跳概率公式,選擇下一跳節點,如(21)式所示。

(21)

式中：T(r,s)為節點r到節點s路徑上的信息素濃度；η(r,s)是信息素啟發函數。α和β分別代表信息素和啟發函數的重要程度。

step 4 記錄螞蟻a經過的節點源地址和序列號,并記錄節點的剩余能量、平均能量和最小能量等信息。

step 5 判斷當前節點是否為匯聚節點,若未到達則繼續執行step 2,否則執行step 6。

step 6 當前向螞蟻a到達匯聚節點后,隨即死亡并生成后向螞蟻a′沿原路徑返回。

step 7 后向螞蟻a′利用(12)式和(15)式更新沿途信息素。

step 8 后向螞蟻a′到達源節點后,標志本次迭代結束,隨即重復step 2,螞蟻開始下次尋優,直至迭代次數N=Nmax,算法終止。

4 實驗仿真與結果分析

為驗證改進算法的有效性,本文對改進后的ATRE-ARA算法進行仿真實驗,并與現有的經典蟻群算法進行對比,通過實驗得出相應的數據和曲線,以評價本文算法性能。

4.1 實驗環境及相關參數

本文實驗環境采用Matlab R2016a搭建仿真平臺,仿真環境分別設置為100 m×100 m(環境1)和200 m×200 m(環境2)的正方形區域,內部部署100個節點。圖3～4分別為節點在環境1和環境2中的分布情況,其他仿真參數如表1所示。

圖3 環境1中節點分布圖

圖4 環境2中節點分布圖

表1 仿真實驗參數設置

4.2 最優路徑長度

最優路徑長度表明了各算法的尋優能力。在圖5～6中,ARA算法的最優路徑長度與改進算法相同,但路徑收斂速度低于改進算法;EEABR算法的最優路徑長度在2種實驗環境下均高于改進算法,收斂速度略快一些。這是因為ATRE-ARA算法在計算路徑信息素值時,引入了信息素上限值Tmax和信息素下限值Tmin,防止在算法迭代初期,因局部路徑信息素差值過大,陷入局部最優,增加了算法搜索全局最優的能力,但同時也降低了算法在尋優時的收斂速度。

圖5 環境1中路徑收斂曲線

圖6 環境2中路徑收斂曲線

表2 算法收斂性能對比表

表2為3種算法的具體性能對比,改進算法在不同環境中,相比EEABR最優路徑長度分別縮短了1.47%和1.59%。改進算法在2種環境下的迭代次數較EEABR算法多26次和4次,較ARA算法少27次和14次。

4.2.1 算法收斂后的節點能量分布情況

為繼續深入研究各算法在收斂后的節點能耗情況,選取3種算法在不同環境下的各節點所消耗能量情況進行對比,如圖7～8所示。由于本文提出的ATRE-ARA算法在計算信息素增量時,引入下一跳節點剩余能量的閾值E0,且閾值E0為自適應函數,隨算法不斷迭代而改變,通過更新閾值E0大小,可以有效提高信息素增量的準確性。

圖7 3種算法在環境1下的節點耗能情況

圖8 3種算法在環境2下的節點耗能情況

從圖7可知,在環境1中,隨著迭代次數的累積,網絡中的各節點能量開銷逐漸增加,2種對比算法的節點開銷明顯高于改進算法。其原因在于改進算法在迭代前期,通過引入搜索角和下一跳節點距離對搜尋路徑進行限制,明顯提高局部尋優能力,在加速算法收斂的同時,有效減少數據在節點間回旋,降低能量損耗。隨著全局網絡中的節點剩余能量逐漸降低,改進的信息素增量公式提高了選擇剩余能量較多的節點作為下一跳節點的概率,防止局部節點過早死亡,達到平衡全局網絡能量的目的。

由圖8可知,由于環境2中節點間距離較遠,數據傳輸開銷較大,故節點能量消耗明顯高于環境1中的節點。改進算法的網絡開銷均低于對比算法,與環境1中得出的結論一致。

4.2.2 算法收斂后的節點平均能量分布情況

為進一步驗證本文ATRE-ARA算法的網絡能耗性能,通過仿真實驗對比各算法在不同環境下的不同階段的平均節點能耗情況。

從圖9～10可以看出,隨著迭代次數的增加,各算法的節點平均能耗增加。本文提出的ATRE-ARA算法在2種環境下的不同階段,節點平均消耗能量均低于其余2種對比算法。且節點平均能耗在環境1和環境2中,改進算法相比ARA算法分別降低了15.12 %和11.68 %。

圖9 環境1中平均能耗與迭代次數

圖10 環境2中平均能耗與迭代次數

5 結 論

本文在深入研究典型蟻群路由算法的基礎上,提出了一種ATRE-ARA路由算法來解決WSN中節點能量分布不均衡、網絡生命周期較短和路由算法容易陷入局部最優等問題。通過優化信息素更新策略,在設置信息素濃度上限與下限的同時引入節點路由數作為平衡路徑信息素濃度的重要參考因素,防止算法陷入局部最優,增加了算法搜索全局最優的能力;改進信息素啟發函數和信息素增量公式,引入搜索角和下一跳節點距離,對搜尋方向和路徑進行限制,減少數據在節點間返復傳輸;將下一跳節點剩余能量的閾值設置為自適應函數,降低局部節點過早死亡的情況,平衡網絡中節點能量分布。通過仿真實驗的對比與分析,證明改進蟻群路由算法在兼顧全局搜索性能的同時有效延長了網絡生命周期。后續將側重研究三維空間中WSN的節點能量開銷及算法尋優問題,以提出適應更復雜環境下的路由算法。