鐵路監(jiān)測WSN網絡的非均勻優(yōu)化分簇算法

呂安琪， 李翠然， 謝健驪， 段寶峰

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

目前高速鐵路列車的時速已高達350 km/h，在確保高速列車安全運行方面，軌旁環(huán)境監(jiān)測系統(tǒng)已至關重要。無線傳感器網絡WSN(Wireless Sensor Network)具有部署簡單、維護成本低、組網靈活、中繼轉發(fā)等特點，在軌道兩側部署基于WSN的環(huán)境監(jiān)測系統(tǒng)可以高效、可靠地采集環(huán)境數(shù)據，從而對列車運行做出正確的防護措施。鐵路環(huán)境的特殊性使鐵路沿線部署的WSN網絡呈線型結構，同時由于WSN節(jié)點只能由電池供電，由此產生了“能量空洞”現(xiàn)象[1]，即網絡以多跳的方式進行信息傳輸，隨著跳數(shù)的增多，信息累積量增大，靠近Sink節(jié)點的普通WSN節(jié)點能耗大，其電能過早耗盡而導致網絡中斷的現(xiàn)象。如何構建合理的節(jié)點部署模型，有效降低甚至避免“能量空洞”現(xiàn)象，是鐵路沿線WSN部署研究亟待解決的關鍵問題。

關于線型WSN網絡中的“能量空洞”問題，已有大量研究成果。ZHANG等[2]提出一種基于信息融合的數(shù)據傳輸機制，通過控制信息粒度對原始數(shù)據進行不同程度的信息融合，從而減少傳輸數(shù)據量，節(jié)省傳感器網絡能量；劉安豐等[3]提出一種基于能量效率的高效節(jié)點部署算法，在已知網絡規(guī)模和節(jié)點感知距離的情況下，可求出最佳中繼節(jié)點部署和節(jié)點最優(yōu)傳輸距離；文獻[4]通過節(jié)點休眠機制調整路由算法，從而提高網絡的能量利用率、可靠性以及實時性；在文獻[5]提出的能耗均衡算法中，采用了改進粒子群策略，對WSN中繼節(jié)點的位置進行尋優(yōu)，均衡了節(jié)點能耗；文獻[6]以軌道交通為背景，提出基于布朗圓盤和Voronoi圖的幾何算法，通過建立兩棵傳感器樹形結構得到理想拓撲結構，延長網絡壽命，提高網絡性能。

上述文獻中，多假設節(jié)點隨機分布，并不適用于實際的監(jiān)測環(huán)境。文獻[7]中以WSN節(jié)點的線性、均勻部署為前提，以節(jié)點轉發(fā)信息的能量消耗和能量平衡作為約束條件，采用非線性方法建立了一種線性WSN網絡調度策略以平衡節(jié)點能量消耗。王楠等[8]提出了一種等距分組多跳路由算法，建立了能耗數(shù)學模型，通過優(yōu)化數(shù)據傳輸方式延長了網絡壽命。文獻[9]以鐵路環(huán)境為依托，通過非均勻分區(qū)方式調整各區(qū)內的節(jié)點數(shù)目，以達到均衡節(jié)點能耗和延長網絡壽命的目標?；谏鲜鲅芯砍晒?，本文著重從鐵路環(huán)境的監(jiān)測應用角度出發(fā)，全面地考慮了直線軌道、弧線軌道監(jiān)測區(qū)域內的節(jié)點非均勻優(yōu)化分簇與部署，以簇頭負載均衡度和簇頭能耗平衡度為計算依據，確定了簇的大小和簇頭的優(yōu)化位置。仿真測試表明，所提算法在均衡簇頭節(jié)點能耗和提高網絡通信效率方面性能較優(yōu)，有效地解決了“能量空洞”問題，延長了監(jiān)測網絡生命周期。

1 節(jié)點部署模型

針對鐵路環(huán)境監(jiān)測，以直線軌道和弧線軌道監(jiān)測為具體應用場景，需對WSN節(jié)點部署模型展開分析。本文給出的假設條件：設軌道長度為L(直線或弧線長度)，節(jié)點感知半徑為r，簇的數(shù)目為k，分別為c1,c2,…,ck。網絡中節(jié)點類型分為2類，即簇頭節(jié)點CH(Cluster Head)與簇成員節(jié)點CM(Cluster Member)，節(jié)點部署方式有:

(1) 直線軌道部署 首先是初始化CM節(jié)點位置。CM節(jié)點沿直線軌道單側部署，節(jié)點間距相等且小于2r，見圖1(a)，CM節(jié)點監(jiān)測信息的采集。采用非均勻分簇算法(見下文)將監(jiān)測區(qū)域劃分為不同的簇，并通過仿真篩選出合適的CH節(jié)點位置，見圖1(b)，CH節(jié)點位置坐標記為ci(i=1,…,k)，用于接收、處理和轉發(fā)簇內CM節(jié)點采集到的信息；di為第i個簇的覆蓋距離。CM節(jié)點將采集的數(shù)據發(fā)送至本地CH節(jié)點，本地CH將信息融合后傳輸至相鄰CH，通過多跳、轉發(fā)方式就可將信息傳輸至用于連接外網的匯聚節(jié)點Sink，即c1→…→ck→Sink。

(2) 弧線軌道的分簇部署 CM節(jié)點沿弧線半徑R軌道單側等距部署，且相鄰CM間的直線距離小于2r，見圖2(a)。同樣通過仿真非均勻分簇算法(見下文)即可篩選出合適的CH節(jié)點位置，見圖2(b)中，O表示圓心，R為弧線軌道半徑，θi(i=1,…,k)為第i個簇的圓心角，弧線軌道WSN中的信息傳輸方式與直線軌道相同,(x,y)為傳感器節(jié)點坐標。

2 非均勻分簇算法

2.1 算法設計

假設WSN網絡中的CM節(jié)點具有如下性質[10]：

(1) CM節(jié)點同構，每個節(jié)點在單位時間內產生lbits數(shù)據，且均需發(fā)送至Sink節(jié)點；

(2) 節(jié)點具有相同的初始能量E0，僅考慮節(jié)點發(fā)送、接收數(shù)據的能量消耗，而感知與處理數(shù)據的能量消耗忽略不計，且不考慮數(shù)據傳送時數(shù)據的沖突和重傳；

(3) 節(jié)點間通信距離等于實際部署中兩節(jié)點間的直線距離。

節(jié)點采用典型的能量消耗模型[11]，發(fā)送、接收數(shù)據的能量消耗分別為

( 1 )

ER=lEelec

( 2 )

式中:ET為節(jié)點發(fā)送lbits數(shù)據消耗的能量;ER為節(jié)點接收lbits數(shù)據消耗的能量;α取值為 2時采用自由空間模型或α取值為4時采用多徑衰減信道模型;d0為區(qū)分兩種模型的距離閾值;d為收、發(fā)兩端的距離;Eelec為發(fā)射電路消耗的能量;εfs為自由空間信道模型功率放大系數(shù)；εamp為多徑衰減信道模型功率放大系數(shù)。

在需要監(jiān)測的鐵路沿線(直線軌道或弧線軌道)等距部署CM節(jié)點，以均衡CH單位時間能耗為優(yōu)化目標，對監(jiān)測區(qū)域進行非均勻分簇，且所分簇間不發(fā)生重疊(即前一個簇的末端是下一個簇的始端)，并根據簇的覆蓋距離確定CH位置。非均勻分簇算法的執(zhí)行步驟為

Step1沿待監(jiān)測的軌道沿線等距部署CM節(jié)點。

Step2初始化簇1和簇2的相關參數(shù)(簇頭節(jié)點位置坐標c1、c2，簇的覆蓋距離d1、d2)。

Step3計算CH的位置坐標ck，k=3,4, …。

2.2 直線軌道的節(jié)點分簇

在直線軌道節(jié)點部署圖1(b)中，令ai為第i個CH節(jié)點與第i+1個CH節(jié)點間的傳輸距離，表示為

ai=ci+1-cii=1,2,…

( 3 )

當給定相鄰CM節(jié)點間的傳輸距離D時，則第i個簇內的CM節(jié)點數(shù)目Ni(取整后)計算為

Ni=di/D+0.5i=1,2,…

( 4 )

節(jié)點c1在一輪數(shù)據采集周期Tc內的能量消耗E1包括2部分，即接收d1區(qū)域數(shù)據的能耗Er1和傳輸數(shù)據至c2的能耗Et1,E1為

( 5 )

節(jié)點c2的單位周期能耗E2包括3部分，即接收d1區(qū)域數(shù)據的能耗、接收d2區(qū)域數(shù)據的能耗和傳輸數(shù)據至c3的能耗,E2為

( 6 )

當k=3,4, …時，節(jié)點ck的單位周期能耗為

( 7 )

當各CH節(jié)點的能耗滿足式( 8 )時，WSN網絡能耗達到均衡

E1=E2=…=Ek

( 8 )

根據式( 3 )～式( 8 )，可得到CH節(jié)點的位置坐標遞推式為

( 9 )

直線軌道情形下的節(jié)點非均勻分簇部署約束條件為

(10)

2.3 弧線軌道的節(jié)點分簇

在弧線軌道節(jié)點部署圖2(b)中，令hi為第i個簇對應的弧長，表示為

(11)

假設θci為第i個簇內的簇頭節(jié)點與初始點對應的圓心角，ai為弧線軌道上節(jié)點ci與節(jié)點ci+1間的直線傳輸距離，計算為

(12)

為相鄰CM節(jié)點間的弧線距離H為

H=2πR[2arcsin(D/2R)/360°]

(13)

則第i個簇內的CM節(jié)點數(shù)目Ni(取整后)計算為

Ni=?hi/H+0.5i=1,2,…

(14)

當各CH節(jié)點的能耗滿足式( 8 )時，WSN網絡能耗達到均衡。由此得到CH節(jié)點對應的圓心角遞推式為

(15)

假設弧線軌道的圓心坐標用(R, 0)表示，簇邊界坐標為(xi,yi)，CH節(jié)點坐標為(xci,yci)，其間的函數(shù)關系可表示為

(16)

弧線軌道情形下節(jié)點非均勻分簇部署約束條件為

(17)

繼而給出網絡生存周期和網絡效率的定義。

定義1網絡生存周期 網絡中第1個節(jié)點死亡的時間(節(jié)點壽命)。

定義2網絡效率 網絡壽命與網絡內CH節(jié)點數(shù)目的比值。

假設WSN網絡中的節(jié)點初始能量為E0，CH節(jié)點ci的單位時間能耗為Ei，則節(jié)點ci的壽命ti和網絡生存周期T分別為

ti=E0/Eii=1,2,…

(18)

T=min{ti}i=1,2,…

(19)

文中引入了簇頭負載均衡度B與簇頭能耗平衡度BH這2個參量，分別表示為

(20)

(21)

3 仿真分析

本節(jié)利用Matlab工具對提出的節(jié)點非均勻分簇部署算法進行仿真評估。具體仿真參數(shù)見表1[12]。

在直線軌道情形下，仿真得到了50組滿足式( 8 )CH節(jié)點能量均衡條件的數(shù)據，記為(ck， ∑di)。CH節(jié)點的能耗波動趨勢見圖3(a)。其中，x軸為數(shù)據組編號，1～50；y軸為對應組號的數(shù)據，即CH節(jié)點的位置；z軸為CH節(jié)點的單位時間能耗。能量等高線見圖3(b)，可見第37～50組的CH節(jié)點能耗波動最大且能耗最高，第1～14組的CH節(jié)點能耗波動次之且能耗較高；第31～36組的CH節(jié)點能耗波動較小且能耗中等；第15～30組的CH節(jié)點能耗波動最小且能耗最低。不同數(shù)據組的B/BH值見圖3(c)，進一步篩選出較優(yōu)的數(shù)據組。

表1 仿真參數(shù)

在篩選數(shù)據組時，先考慮CH節(jié)點能耗及其波動，再綜合考慮B/BH這2個參數(shù)值，由此得到較好的數(shù)據組號為16，17，20，24和28?？蓮囊陨?組數(shù)據中任取一組數(shù)據構建WSN網絡模型，以下仿真使用的是第28組數(shù)據，對應的(ck，∑di)取值為：(160，180)，(420，440)，(567，580)，(686，700)，(786，820)，(870，920)和(942，1000)，得到的節(jié)點優(yōu)化部署模型見圖4。在綠色圓點與紅色加號重合的位置，可將該CM節(jié)點設定為CH節(jié)點，此時無需再另行放置CH節(jié)點。

在弧線軌道情形下，通過仿真得到了66組滿足式( 8 )CH節(jié)點能量均衡條件的數(shù)據組，以CH的位置坐標(xci,yci)及其圓心角來標記。CH節(jié)點的能耗波動趨勢見圖5(a)。由圖5(a)可看出，沿弧線軌道部署的WSN網絡幾乎達到了理想的CH能量均衡狀態(tài)，其中，第1～9組和第10～21組的CH能耗最小。再結合圖5(b)給出的B/BH參數(shù)值，篩選出的較優(yōu)數(shù)據組為第9組，對應CH坐標值為(2.4，140)，(20，399)，(37.4，545.7)，(55.9，666.5)，(74.3，767.5)，(92.3，854.5)和(109.4，929.2)，圓心角分別為2°、5.7°、7.8°、9.6°、11.1°、12.3°、13.4°，得到的節(jié)點優(yōu)化模型見圖5(c)。圖中標識與直線軌道模型中的相同，不再贅述。

為進一步評估文中所提出的非均勻優(yōu)化分簇算法部署效果，在相同簇數(shù)目情形下，不同算法構建的WSN網絡中的CH節(jié)點能耗、CH節(jié)點壽命和網絡效率分別見圖6～圖8。

圖6中，簇頭固定的非均勻分簇是指CH節(jié)點位于簇幾何中心；均勻分簇是指WSN網絡中各個簇的覆蓋距離相等；組數(shù)據傳輸是指將網絡中的節(jié)點分組，數(shù)據由多條鏈路同時傳輸[13]。由圖6可見，均勻分簇算法和組數(shù)據傳輸算法的節(jié)點能耗呈非均勻態(tài)勢，組數(shù)據傳輸算法的節(jié)點能耗遠低于均勻分簇算法；文中算法與簇頭固定的非均勻分簇算法的節(jié)點能耗呈均勻態(tài)勢，所提算法在直線和弧線軌道部署中的節(jié)點能耗均低于簇頭固定的非均勻分簇算法。分析可知，組數(shù)據傳輸算法雖然降低了某些節(jié)點能耗，但無法消除節(jié)點能耗不均衡的現(xiàn)象，本文提出的非均勻優(yōu)化分簇算法的節(jié)點能耗分布均勻且能耗低于組數(shù)據傳輸算法的最大節(jié)點能耗，具有較優(yōu)的性能。

非均勻優(yōu)化分簇算法在直線與弧線情況下的節(jié)點壽命相差無幾，仿真時會出現(xiàn)線條掩蓋現(xiàn)象，因此，圖7中選擇非均勻優(yōu)化分簇算法(直線)與其他算法進行對比。由于網絡生存周期或節(jié)點壽命僅與最早死亡節(jié)點的時間有關，非均勻優(yōu)化分簇算法的節(jié)點壽命最長，其次為簇頭固定的非均勻分簇和組數(shù)據傳輸算法，均勻分簇算法的網絡生存周期最短。

圖8中算法1～算法5分別對應簇頭固定的非均勻分簇、非均勻優(yōu)化分簇(直線)、非均勻優(yōu)化分簇(弧線)、均勻分簇和組數(shù)據傳輸算法。由圖8可明顯看出，非均勻優(yōu)化分簇算法的網絡效率最高，簇頭固定的非均勻分簇和組數(shù)據傳輸算法次之，均勻分簇算法性能最差。

4 結束語

為解決鐵路沿線WSN線性部署導致的“能量空洞”問題，本文提出了一種節(jié)點非均勻優(yōu)化分簇算法。算法以簇頭節(jié)點能耗、簇頭節(jié)點數(shù)目和簇成員節(jié)點數(shù)目之間的函數(shù)關系為基礎，構建了直線軌道、弧線軌道監(jiān)測區(qū)域內的節(jié)點非均勻優(yōu)化分簇模型，實驗結果表明，本文算法與簇頭固定的非均勻分簇、均勻分簇以及組數(shù)據傳輸算法相比，有效地降低了CH節(jié)點能耗、提高了網絡效率，延長了WSN監(jiān)測網絡的生存周期?？紤]到鐵路場景中相鄰站點間的距離較長，當簇數(shù)目增多時，算法性能會有所下降。下一步的研究將通過控制策略調整簇的覆蓋距離，并在鐵軌沿線每隔一定距離處增設匯聚節(jié)點Sink。此外，如何快速構建最優(yōu)的非均勻分簇是面向鐵路應用的關鍵，進一步的研究思路是根據不同站點間的鐵路軌道長度和類型(直線、弧線)，評估算法的時間復雜度，以滿足鐵路應用的監(jiān)測組網需求。