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

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

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

0 引 言

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

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

根據(jù)列車長帶狀網(wǎng)絡(luò)結(jié)構(gòu)特性，本文提出了一種基于改進(jìn)蟻群優(yōu)化算法的列車WSNs非均勻分簇路由(improved ant colony optimization algorithm based uneven clustering routing，IACO-UCR)協(xié)議來均衡網(wǎng)絡(luò)能耗，實(shí)現(xiàn)數(shù)據(jù)傳輸?shù)母咝院涂煽啃?，提高網(wǎng)絡(luò)生命周期。

1 系統(tǒng)模型

列車狹長的外形決定了部署在列車上的WSNs拓?fù)浣Y(jié)構(gòu)為長帶狀。網(wǎng)絡(luò)中按節(jié)點(diǎn)功能主要可分為普通傳感器節(jié)點(diǎn)和基站，為提高對列車關(guān)鍵零部件和重點(diǎn)區(qū)域信息的準(zhǔn)確性和全面性，本文中的WSNs節(jié)點(diǎn)采用人為方式進(jìn)行布置如圖1。

圖1 節(jié)點(diǎn)布置

1.1 網(wǎng)絡(luò)模型

假設(shè)在列車監(jiān)測區(qū)域內(nèi)布置著N個(gè)傳感器節(jié)點(diǎn)，并滿足以下條件：

1)監(jiān)測區(qū)域中節(jié)點(diǎn)的位置是固定的；

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

3)傳感器節(jié)點(diǎn)都是同構(gòu)型，并具有唯一的編號(hào)(ID)；

4)節(jié)點(diǎn)能根據(jù)距離調(diào)整自身收發(fā)功率。

1.2 無線通信能耗模型

無線通信能耗由接、發(fā)收模塊電路能耗兩部分組成。節(jié)點(diǎn)發(fā)送l數(shù)據(jù)能耗

(1)

節(jié)點(diǎn)接收l數(shù)據(jù)能耗

ERx=lEelec

(2)

2 IACO-UCP協(xié)議

IACO-UCP協(xié)議先建立非均勻分簇，然后通過基于蟻群算法的最優(yōu)簇間路徑將數(shù)據(jù)傳輸至基站。

2.1 簇首選取策略

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

2.1.2 指標(biāo)分析

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

1)通信距離

由系統(tǒng)能耗模型可知，通信距離與能耗成正比。定義候選簇首到基站距離和網(wǎng)絡(luò)中節(jié)點(diǎn)到基站的最大距離比值fm2

(3)

式中d(m,BS)為候選簇首節(jié)點(diǎn)到基站的距離，dmax為網(wǎng)絡(luò)的所有節(jié)點(diǎn)中到基站的最遠(yuǎn)距離。

2)中心位置度

表示候選簇首節(jié)點(diǎn)與競爭半徑范圍內(nèi)節(jié)點(diǎn)的聚集程度。中心位置度表達(dá)式如下

(4)

式中xm,ym分別為候選簇首的橫坐標(biāo)和縱坐標(biāo);xj,yj分別為競爭半徑范圍內(nèi)鄰居節(jié)點(diǎn)的橫坐標(biāo)和縱坐標(biāo)。

3)節(jié)點(diǎn)相對密度

在競爭半徑范圍內(nèi)，節(jié)點(diǎn)相對密度是指候選簇首節(jié)點(diǎn)密度與最大節(jié)點(diǎn)密度之比值來表示，鄰居節(jié)點(diǎn)數(shù)量越多，簇首節(jié)點(diǎn)接收和發(fā)送信息時(shí)的能耗就越少

(5)

式中D(m)為節(jié)點(diǎn)m的當(dāng)前密度，Dmax(m)為網(wǎng)絡(luò)中節(jié)點(diǎn)m的最大密度。

2.1.3 熵權(quán)法確定指標(biāo)權(quán)重

1)對評(píng)價(jià)指標(biāo)進(jìn)行歸一化處理

(6)

2)計(jì)算指標(biāo)熵權(quán)值

(7)

(8)

式中En為第n個(gè)指標(biāo)的熵權(quán)值，Pmn為第m個(gè)節(jié)點(diǎn)中的第n個(gè)指標(biāo)在其所屬節(jié)點(diǎn)的所有指標(biāo)下的特征比重。

3)各指標(biāo)的權(quán)重確定

(9)

2.1.4 簇首確定

引入節(jié)點(diǎn)能量因素來綜合評(píng)判節(jié)點(diǎn)，評(píng)判值最大的即為簇首

(10)

式中Eres，Einit分別為節(jié)點(diǎn)m的當(dāng)前剩余能量和初始能量。

2.2 競爭半徑

由于網(wǎng)絡(luò)中存在能量“熱區(qū)”問題，為解決這種現(xiàn)象，采取非均勻分簇的思想，對簇群的進(jìn)行合理設(shè)計(jì)來均勻網(wǎng)絡(luò)能耗。根據(jù)距離、能量和節(jié)點(diǎn)密度因素來確定競爭半徑R0

R0=

(11)

式中c1和c2為權(quán)重因子，c1+c2=1；dmin為網(wǎng)絡(luò)中節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的最小距離；Emin為節(jié)點(diǎn)最低的工作能量；N0為競爭半徑內(nèi)的鄰居節(jié)點(diǎn)數(shù)，N為節(jié)點(diǎn)數(shù)；Rmax為最大競爭半徑。

2.3 簇的形成

簇首完成選舉后，在全網(wǎng)廣播其自身信息，在競爭半徑范圍內(nèi)的成員節(jié)點(diǎn)根據(jù)接收到信號(hào)強(qiáng)度選擇距離最近的簇首加入。簇首接收到其他簇首節(jié)點(diǎn)發(fā)出的信息來建立相鄰簇首列表。簇內(nèi)成員節(jié)點(diǎn)根據(jù)TDMA 時(shí)隙表直接向簇首發(fā)送數(shù)據(jù)，簇間通過蟻群優(yōu)化建立的最優(yōu)多跳路徑進(jìn)行數(shù)據(jù)傳輸。

2.4 采用改進(jìn)ACO算法的簇間路由

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

2.4.1 改進(jìn)選擇策略

本文對最優(yōu)路徑的選擇策略提出了如下改進(jìn)

(12)

(13)

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

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

(14)

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

傳統(tǒng)的ACO算法考慮的因素比較單一，引入能量、距離和角度因素。節(jié)點(diǎn)剩余能量能避免信息素高的路徑不會(huì)因?yàn)槠渲心硞€(gè)節(jié)點(diǎn)能量的耗盡導(dǎo)致整條路徑傳輸數(shù)據(jù)中斷；路徑長度能防止出現(xiàn)信息素高且距離長的路徑被選中，造成不必要的能量浪費(fèi)；搜索方向角度[15]能引導(dǎo)數(shù)據(jù)向正向傳輸，即朝著基站方向，有利于減少數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)達(dá)到節(jié)能。證明角度、距離和能耗的關(guān)系。如圖2所示，可以推出距離、角度和能耗的關(guān)系，即當(dāng)兩個(gè)節(jié)點(diǎn)角度相同時(shí)，距離越小的，能耗能耗就越小；當(dāng)兩節(jié)點(diǎn)距離相同時(shí)，角度越小的，能耗也越小。

圖2 節(jié)點(diǎn)間的角度

為了均衡網(wǎng)絡(luò)能耗，本文對啟發(fā)信息進(jìn)行改進(jìn)

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

(15)

式中a1,a2,a3分別為權(quán)衡節(jié)點(diǎn)能量，距離和搜索方向參數(shù)對啟發(fā)信息的影響程度，a1+a2+a3=1。Ep(j)為節(jié)點(diǎn)j的能量評(píng)價(jià)參數(shù)，由節(jié)點(diǎn)j的當(dāng)前剩余能量Er(j)與全網(wǎng)剩余平均Er,avg的比值

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

(16)

式中Dp(i,j)為路徑(i,j)長度的評(píng)價(jià)參數(shù)

(17)

式中A(j,i,BS)為節(jié)點(diǎn)i至基站的連線與節(jié)點(diǎn)i至節(jié)點(diǎn)j連線之間的角度評(píng)價(jià)參數(shù)

(18)

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

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

(19)

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

P=ρ×(1-Ei/Einit)

(20)

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

(21)

式中ρ，Q分別為默認(rèn)的信息素?fù)]發(fā)系數(shù)和信息素增量。

2.4.3 全局更新信息素

當(dāng)所有前向螞蟻完成路徑搜索后抵達(dá)基站，基站開始對搜索到的路徑進(jìn)行分析?；旧a(chǎn)后向螞蟻按原路返回，并對該路徑上的信息素進(jìn)行全局更新，其中Qmax為默認(rèn)信息素最大值

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

(22)

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

圖3 簇間路徑搜索流程

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 仿真參數(shù)設(shè)置

為了驗(yàn)證IACO-UCR性能，采用在MATLAB實(shí)驗(yàn)平臺(tái)下進(jìn)行仿真，與LEACH,EEUC和ACOUC進(jìn)行比較，具體參數(shù)設(shè)置：監(jiān)測區(qū)域面積為400 m×3 m，基站位置為(0,1.5)，節(jié)點(diǎn)數(shù)為400，節(jié)點(diǎn)初始能量為0.5 J，數(shù)據(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 仿真結(jié)果與分析

由圖4(a)可知LEACH算法的簇首能量消耗最大，這是由于該算法在簇首選舉是隨機(jī)的，而且簇首直接與基站通信，導(dǎo)致消耗大量能量。EECU算法的簇首能量消耗次之，因?yàn)镋EUC算法在簇間數(shù)據(jù)傳輸時(shí)沒有根據(jù)路徑的信息而進(jìn)行動(dòng)態(tài)調(diào)整。本文的IACO-UCR算法簇首能耗略低于ACOUC算法，這是由于IACO-UCR算法在簇頭選舉中，充分考慮到通信距離、中心位置度、相對密度和能量各項(xiàng)指標(biāo)對節(jié)點(diǎn)成為簇首的影響，再建立簇間路由時(shí)充分考慮能量、距離和位置角度等相關(guān)因素以保證路徑最優(yōu)。

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

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

圖4 仿真結(jié)果

4 結(jié) 論

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