基于蟻群優化的列車WSNs非均勻分簇路由算法*

杭 超,李 剛,2,3,李德倉

(1.蘭州交通大學 機電技術研究所，甘肅 蘭州 730070；2.甘肅省物流及運輸裝備信息化工程技術研究中心，甘肅 蘭州 730070；3.甘肅省物流與運輸裝備行業技術中心，甘肅 蘭州 730070)

0 引 言

為了保障列車運行安全，在列車上建立完備的安全監測系統是十分有必要的[1,2]。相比現有的有線列車監測系統，無線監測系統受環境干擾小，系統成本低等優勢。無線傳感器網絡(wireless sensor networks,WSNs)作為物聯網技術中的重要一部分，已經滲透到人們生活和生產的各個領域中[3]。它是一種由大量尺寸微小、價格低廉的傳感器節點通過無線自組織分布式網絡，一般采用能量有限的電池供電。

WSNs的能耗問題一直以來是各國學者關注的焦點，采用合適的路由協議能降低網絡能耗，提高數據傳輸效率。相比平面路由，分簇路由在數據傳輸、網絡能耗均勻方面更能體現其優越性。LEACH[4]作為一種最經典的均勻分簇路由，通過隨機選舉簇首，沒有考慮節點能量和通信距離等因素，導致靠近基站附近節點能耗過大而過早失效，產生能量“熱區”問題從而限制網絡壽命。因此，美國學者[4]首次提出關于非均勻分簇的思想。在國內，李成法等人[5]提出了EEUC路由算法。算法能一定程度上能緩解網絡能量“熱區”問題，但該算法沒有考慮到簇間數據傳輸路徑的實際狀況。在此基礎上人們開始研究簇間通信路徑最優化的問題。蟻群優化(ant colony optimization，ACO)[6]算法作為一種經典的群體智能算法，Gunes M等人[7]最早將ACO算法應用在移動自組織網絡路由中;文獻[8]提出的基于蟻群優化的非均勻分簇路由ACOUC算法，考慮了帶寬和傳輸時延等因素對選擇簇間路由的影響；文獻[9,10]都采用蟻群理論分別對EEABR算法進行改進，算法各方面性能得到極大地提升;文獻[11]在路徑傳輸中考慮的因素比較全面，但在簇頭選舉上評判條件比較單一，容易導致簇首能耗偏大。

根據列車長帶狀網絡結構特性，本文提出了一種基于改進蟻群優化算法的列車WSNs非均勻分簇路由(improved ant colony optimization algorithm based uneven clustering routing，IACO-UCR)協議來均衡網絡能耗，實現數據傳輸的高效性和可靠性，提高網絡生命周期。

1 系統模型

列車狹長的外形決定了部署在列車上的WSNs拓撲結構為長帶狀。網絡中按節點功能主要可分為普通傳感器節點和基站，為提高對列車關鍵零部件和重點區域信息的準確性和全面性，本文中的WSNs節點采用人為方式進行布置如圖1。

圖1 節點布置

1.1 網絡模型

假設在列車監測區域內布置著N個傳感器節點，并滿足以下條件：

1)監測區域中節點的位置是固定的；

2)基站布置在列車端部，能量和計算能力不受限制；

3)傳感器節點都是同構型，并具有唯一的編號(ID)；

4)節點能根據距離調整自身收發功率。

1.2 無線通信能耗模型

無線通信能耗由接、發收模塊電路能耗兩部分組成。節點發送l數據能耗

(1)

節點接收l數據能耗

ERx=lEelec

(2)

2 IACO-UCP協議

IACO-UCP協議先建立非均勻分簇，然后通過基于蟻群算法的最優簇間路徑將數據傳輸至基站。

2.1 簇首選取策略

熵權法[12]在解決多屬性的決策問題中體現出客觀性強、置信度高。其主要思想為：利用信息熵計算各指標的熵權，然后對各指標的權重進行修正，最終得到較為客觀的指標權重。本文引入熵權法來客觀地反映候選簇首指標的權重，從而來客觀選舉簇首。

2.1.2 指標分析

在WSNs中，評價候選簇首能否成為最終簇首要從多方面考慮，通過多指標的綜合評判使結果更具客觀性。本文將從節點的能量、通信距離、中心位置度和相對密度等因素來考慮，并引入能量優先概念，即能量因素的優先級要高于其他因素。定義fmn表示在簇首競爭半徑范圍內的第m個節點的第n個指標的函數。

1)通信距離

由系統能耗模型可知，通信距離與能耗成正比。定義候選簇首到基站距離和網絡中節點到基站的最大距離比值fm2

(3)

式中d(m,BS)為候選簇首節點到基站的距離，dmax為網絡的所有節點中到基站的最遠距離。

2)中心位置度

表示候選簇首節點與競爭半徑范圍內節點的聚集程度。中心位置度表達式如下

(4)

式中xm,ym分別為候選簇首的橫坐標和縱坐標;xj,yj分別為競爭半徑范圍內鄰居節點的橫坐標和縱坐標。

3)節點相對密度

在競爭半徑范圍內，節點相對密度是指候選簇首節點密度與最大節點密度之比值來表示，鄰居節點數量越多，簇首節點接收和發送信息時的能耗就越少

(5)

式中D(m)為節點m的當前密度，Dmax(m)為網絡中節點m的最大密度。

2.1.3 熵權法確定指標權重

1)對評價指標進行歸一化處理

(6)

2)計算指標熵權值

(7)

(8)

式中En為第n個指標的熵權值，Pmn為第m個節點中的第n個指標在其所屬節點的所有指標下的特征比重。

3)各指標的權重確定

(9)

2.1.4 簇首確定

引入節點能量因素來綜合評判節點，評判值最大的即為簇首

(10)

式中Eres，Einit分別為節點m的當前剩余能量和初始能量。

2.2 競爭半徑

由于網絡中存在能量“熱區”問題，為解決這種現象，采取非均勻分簇的思想，對簇群的進行合理設計來均勻網絡能耗。根據距離、能量和節點密度因素來確定競爭半徑R0

R0=

(11)

式中c1和c2為權重因子，c1+c2=1；dmin為網絡中節點到匯聚節點的最小距離；Emin為節點最低的工作能量；N0為競爭半徑內的鄰居節點數，N為節點數；Rmax為最大競爭半徑。

2.3 簇的形成

簇首完成選舉后，在全網廣播其自身信息，在競爭半徑范圍內的成員節點根據接收到信號強度選擇距離最近的簇首加入。簇首接收到其他簇首節點發出的信息來建立相鄰簇首列表。簇內成員節點根據TDMA 時隙表直接向簇首發送數據，簇間通過蟻群優化建立的最優多跳路徑進行數據傳輸。

2.4 采用改進ACO算法的簇間路由

將傳統的ACO算法運用于WSNs簇間傳輸路徑問題上,能增強路徑搜索的魯棒性[13,14]，但會出現不足：一是容易陷入局部最優解；二是沒有考慮到各節點的剩余能量，會使最優路徑因個別能量較低的節點過早失效，而影響該路徑正常工作。對于只依靠信息素濃度來選擇螞蟻的下一跳不足，在選擇策略中引進了決策因子，充分考慮到節點能量、距離和搜索方向等因素。

2.4.1 改進選擇策略

本文對最優路徑的選擇策略提出了如下改進

(12)

(13)

式中Dt(i,j)為引入的決策因子作為路徑選擇的判斷依據，Zk(i)為螞蟻k在節點i上的下一跳節點集合。q為前向螞蟻選擇下一跳節點時，分配給下一跳節點在區間[0,1]上隨機生成的數；若q≤q0選擇Dt(i,j)值最大的節點，反之，則根據式(13)選擇下一跳節點。參數q0體現了尋求最優路徑和探尋新路徑的相對重要性，提高ACO算法的全局搜索能力。決策因子由信息素濃度τt(i,j)和啟發因子ηt(i,j)兩部分構成

Dt(i,j)=ατt(i,j)+βηt(i,j)

(14)

式中α，β分別為τt(i,j)和ηt(i,j)的權重因子。

傳統的ACO算法考慮的因素比較單一，引入能量、距離和角度因素。節點剩余能量能避免信息素高的路徑不會因為其中某個節點能量的耗盡導致整條路徑傳輸數據中斷；路徑長度能防止出現信息素高且距離長的路徑被選中，造成不必要的能量浪費；搜索方向角度[15]能引導數據向正向傳輸，即朝著基站方向，有利于減少數據轉發次數達到節能。證明角度、距離和能耗的關系。如圖2所示，可以推出距離、角度和能耗的關系，即當兩個節點角度相同時，距離越小的，能耗能耗就越小；當兩節點距離相同時，角度越小的，能耗也越小。

圖2 節點間的角度

為了均衡網絡能耗，本文對啟發信息進行改進

ηt=a1Ep(j)+a2Dp(i,j)+a3Ap(j,i,BS)

(15)

式中a1,a2,a3分別為權衡節點能量，距離和搜索方向參數對啟發信息的影響程度，a1+a2+a3=1。Ep(j)為節點j的能量評價參數，由節點j的當前剩余能量Er(j)與全網剩余平均Er,avg的比值

Ep(j)=Er(j)/Er,avg

(16)

式中Dp(i,j)為路徑(i,j)長度的評價參數

(17)

式中A(j,i,BS)為節點i至基站的連線與節點i至節點j連線之間的角度評價參數

(18)

2.4.2 采用局部和全局信息素相結合的混合更新方式

在前向螞蟻選擇完下一跳節點后并對這段路徑信息素進行局部更新。引入最大和最小信息素濃度閾值來限制信息素濃度的范圍，從而解決因信息素濃度過高或過低問題

(19)

式中p為信息素揮發系數，Δt為信息素更新的時間間隔，Δτ(i,j)為螞蟻釋放的信息素增量。文中考慮到路徑上的信息揮發系數與該路徑的長度與剩余能量的關系，從而來避免剩余能量低、距離長且信息度濃度高的路徑被選為最優路徑。因此，本文在計算P和Δτ(i,j)時引入距離和能量評價參數

P=ρ×(1-Ei/Einit)

(20)

Δτ=Q×(1-Ei/Einit)

(21)

式中ρ，Q分別為默認的信息素揮發系數和信息素增量。

2.4.3 全局更新信息素

當所有前向螞蟻完成路徑搜索后抵達基站，基站開始對搜索到的路徑進行分析。基站生產后向螞蟻按原路返回，并對該路徑上的信息素進行全局更新，其中Qmax為默認信息素最大值

τt+1(i,j)=(1-p×Δt)×τt(i,j)+Qmax

(22)

簇間路徑搜索流程如圖3所示。

圖3 簇間路徑搜索流程

3 仿真實驗與結果分析

3.1 仿真參數設置

為了驗證IACO-UCR性能，采用在MATLAB實驗平臺下進行仿真，與LEACH,EEUC和ACOUC進行比較，具體參數設置：監測區域面積為400 m×3 m，基站位置為(0,1.5)，節點數為400，節點初始能量為0.5 J，數據包大小為4 000 bit，εfs為10 pJ，εmp為0.001 3 pJ，Eelec為50 nJ/bit，EDA為5 nJ/bit，d0為87 m，Rmax為90 m，c1/c2為0.5/0.5。

3.2 仿真結果與分析

由圖4(a)可知LEACH算法的簇首能量消耗最大，這是由于該算法在簇首選舉是隨機的，而且簇首直接與基站通信，導致消耗大量能量。EECU算法的簇首能量消耗次之，因為EEUC算法在簇間數據傳輸時沒有根據路徑的信息而進行動態調整。本文的IACO-UCR算法簇首能耗略低于ACOUC算法，這是由于IACO-UCR算法在簇頭選舉中，充分考慮到通信距離、中心位置度、相對密度和能量各項指標對節點成為簇首的影響，再建立簇間路由時充分考慮能量、距離和位置角度等相關因素以保證路徑最優。

如圖4(b)所示，本文所提出的IACO-UCR算法的網絡生存周期明顯要優于其他算法。IACO-UCR大約在700輪左右開始第一個節點的死亡，而LEACH則在600輪左右時節點已經全部死亡了。EEUC,ACOUC的網絡生命周期分別為782,976輪。從而可得：IACO-UCR算法的網絡生存周期最長。

圖4(c)為隨著運行輪數的增加，網絡節點平均剩余能量的變化。由于LEACH算法是隨機輪選簇頭且采用單跳方式直接與基站通信，導致該算法網絡節點能耗在這三者中最大，網絡的生存周期最短。ACOUC比EEUC多大約200輪的生存時間。IACO-UCR算法在網絡運行輪數最大即網絡的壽命最長，表明了該算法能較好均衡網絡能耗，延長網絡生命周期。

圖4 仿真結果

4 結 論

對于WSNs應用在列車安全監測中，結合列車外形結構特點，本文提出了一種基于改進蟻群算法的列車WSNs非均勻分簇路由算法(IACO-UCR)。該算法在分簇階段充分考慮到節點的剩余能量、距離、密度和中心位置度等因素，在簇間通信路徑選擇上引入改進優化的蟻群算法來建立最優的路徑。由仿真實驗結果可知，IACO-UCR算法的節點存活數量和節點平均剩余能量，相比傳統的LEACH，EEUC和ACOUC算法都有明顯的提高。該算法雖然在實驗仿真環境下有良好的性能，但在實際工作環境中會存在較大差異，需要根據實際工況對算法進行合理的改進。