太陽能補給的線性WSN路由算法研究

呂安琪，李翠然，謝健驪，張澤鵬

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

隨著交通工具多元化、高速化與智能化，其運行安全備受關注[1-2]。做好交通運營環境安全監測勢在必行。無線傳感器網絡(Wireless Sensor Network, WSN)具有自組織性及定位等功能，適用于交通運營環境監測。然而，在交通運營復雜監測環境下，WSN中的傳感器節點感知和通信的能量主要來自自身配置的電池且電池不易更換[3]。而在大規模WSN中傳感器節點通過多跳的方式將數據傳輸至匯聚節點，轉發數據量大的傳感器節點能量消耗大，造成網絡能耗不均衡的現象[4]。此外，網絡中傳感器節點對冗余數據的傳輸，會增加傳感器節點能量負擔[5]。以上情況均會影響WSN生存周期，限制無線傳感器網絡實際應用。

針對傳感器節點能量受限與WSN生存周期短的問題[6]，研究者們從網絡拓撲變化[7]、路由協議[8-9]等方面著手進行大量研究。文獻[10]中，遺傳算法被引入WSN，首先節點根據能效聚類，然后以網絡覆蓋率與節點剩余能量為輸入參數，采用遺傳算法選擇簇頭節點，從而達到減少通信開銷、降低節點能耗的目標。文獻[11]中，提出混合能量高效分布式集群算法，以均衡網絡簇頭節點分布，延長網絡生存周期為目標。文獻[12]中，提出基于自組織映射的能量聚類WSN路由協議，首先通過權值訓練與重組形成高能量簇，然后將高能量節點與低能量節點組合均衡簇能量，從而達到延長網絡生存周期的目標。文獻[13]提出動態超循環策略及能量效率數據收集協議，通過調度集群任務達到降低節點能耗與延長網絡生存周期的目標。

以上算法均可有效延長WSN生存周期，但其算法復雜度高，不適用于部署在鐵路沿線的線性WSN。相比之下，文獻[14]提出的基于節點間相關性的能量有效分簇路由協議的復雜度低，其利用節點位置相關性與節點剩余能量，選擇出分布均勻的簇首節點，從而達到均衡節點能耗延長網絡生存周期的目標。文獻[15]針對部署于鐵路沿線的線性WSN，提出組數據算法，其中傳感器節點均勻部署且均勻分簇，相距K個距離的簇頭節點形成一條傳輸路徑，網絡中有K條路徑同時傳輸數據，該算法可有效地降低節點能耗、延長網絡生存周期。此外，隨著硬件的發展，能量采集技術已被引入WSN 中[16]。

針對傳感器節點能量受限與網絡生存周期短的問題，本文首先結合鐵路沿線狹長的特點，對節點部署模型進行研究。然后介紹基于太陽能補給的協同數據傳輸策略，提出節能路由選擇算法并對算法進行說明。最后通過仿真驗證算法性能。

1 節點部署模型

假設WSN中的節點具有如下性質[17]：

(1)節點初始能量相同為E0，匯聚節點(Sink node)能量不受限，數據傳輸過程中，僅考慮節點發送、接收數據的能量消耗；

(2)每個節點在單位監測面積(m2)上產生數據為b0(bit/round)，數據均需被發送至Sink node；

(3)傳感器節點采用有向半圓布爾感知模型；

(4)節點感知半徑可調，通信半徑為dt。

無線傳感器網絡用于監測交通運營環境，設L表示監測區域長度，W表示監測區域寬度，節點均勻部署于監測區域兩側，D表示同側相鄰節點間直線距離，不同側相鄰節點水平距離為D/2，節點部署模型見圖1。

圖1 節點部署模型

圖1中，沿著列車運行方向視圖，監測區域可劃分為左側和右側。設SRi表示監測區域右側節點，感知半徑為Rr；SLi表示監測區域左側節點，感知半徑為Rl。令Rl≤Rr，Sink node部署于右側，兩側傳感器節點從Sink node處開始獨立編號。根據左右兩側節點感知半徑、監測區間長度與寬度的關系，節點部署模型可分為三種情形，見圖2。

圖2 WSN冗余感知示意

Case1：當max(Rr，Rl)

Case2：當max(Rr，Rl)≥W，min(Rr，Rl)≤W且D/2≥W，D/2≤Rr時，相鄰節點SR1與SR2感知區域發生重疊，相交于點A(xA,yA)，且yA≤W。節點部署模型見圖2(b)。

Case3：當min(Rr，Rl)≥W，且D/2>Rr時，節點部署模型見圖2(c)，節點SR1與SR2感知區域不重疊。

感知半徑Rl為

Rl=

( 1 )

在保證監測區域全覆蓋條件下，使用自適應半徑方法使各種節點部署情形下的冗余覆蓋面積最小化，同側節點感知半徑保持一致。當兩側節點感知半徑滿足式(1)時，監測區域全覆蓋。

定義：冗余覆蓋比例B為冗余面積與監測區域面積的比值，其表達式見式(2)。B值越小，則用于冗余數據傳輸的能量越小。

( 2 )

2 能量模型與數據傳輸策略

2.1 能耗模型

節點采用典型的能量消耗模型[18]，發送、接收數據的能量消耗為

ET=Eelec+ε·dα

( 3 )

ER=Eelec

( 4 )

式中：ET為節點發送1 bit數據消耗能量；ER為節點接收1 bit數據消耗能量；Eelec為發射電路消耗能量；d0=(εfs/εamp)1/2為距離閾值，當數據傳輸距離d

2.2 能量采集模型

本文通過在傳感器節點處配置太陽能電池板的方式采集太陽能，并通過儲能裝置存儲能量，對節點提供能量補給。太陽能補給方案在補給能量的同時也存在一定的技術局限性，例如，太陽能具有不穩定性，會受時間周期、地理位置、氣象變化等條件的影響，并且太陽能電池轉換效率η僅在10%～25%之間等[19-20]。針對其局限性，研究太陽輻照度較小時的WSN能量補給。設太陽輻照度為F，mW/cm2，太陽能電池板面積為SH，cm2，儲能裝置容量為E=E0。WSN以周期性方式進行數據采集與傳輸，從網絡開始運行至出現第一個節點能量耗盡的時長為網絡生存周期，單位為round。1個round表示所有節點將單次采集到的數據均傳輸至Sink node的時長。設1個round時長為T，單位為s，則在1個round內儲存能量EH為

( 5 )

設傳感器節點進行能量補給時的充電功率恒定為PS，則在1個round內傳感器節點可補充能量Ep為

( 6 )

2.3 數據傳輸策略

基于太陽能補給的協同數據傳輸策略見圖3，圖中各變量含義見表1。

圖3 協同數據傳輸策略流程

表1 變量符號及含義

數據傳輸示意圖見圖4。

圖4 數據傳輸示意

當Rr=Rl時，進行雙側傳輸，見圖4(a)，當EremEthn時節點關閉充電模式。

當Rr>Rl時，初始時進行雙側傳輸，當ErermEth時，切換至單側傳輸，見圖4(b)，SRi將數據發送到左側對應的SLi，再由左側傳感器節點進行數據傳輸。當Ererm>Ethn或Erelm≤Eth時切換回雙側傳輸。

在華為績效考核體系里，多數部門都會硬性分配績效A/B/C的考核比例。就算全部門全年表現都很好，也不可避免有人要被評為“C”。

3 節能路由選擇算法

3.1 節點層次化聚類

定義：傳感器節點至Sink node的數據傳輸方向為正方向，節點i正方向上的節點稱為節點i的前向節點，其反方向上的節點稱為節點i的后向節點。

網絡依據預設標準能耗值Estand對節點進行層次化聚類。層次化聚類從Sink node開始執行，距離Sink node越近的層次等級越高，轉發數據量越大。標準能耗值為所有節點能耗上限值，用于確定轉發節點。數據雙側傳輸時標準能耗可選取值見式( 7 )，其中i≤?dt/D」；數據單側傳輸時標準能耗可選取值見式( 8 )，其中i≤?(dt2-W2)1/2/D+1」;di,Sink為節點i到節點Sink node的通信距離;kr=b0·π·Rr2/2為右側節點單次感知數據量;kl=b0·π·Rl2/2為左側節點單次感知數據量。

EBCi=「L/D+1-i?·kr·(ET+ER)=

( 7 )

( 8 )

節點層次化聚類過程描述如下：Sink node將預設標準能耗值及其節點信息反向發布至其通信范圍內的傳感器節點，接收到信息的傳感器節點參與轉發節點競爭。參與競爭的傳感器節點計算將自身與其所有后向節點的感知數據發送至發布信息的節點所需能量，所需能量值小于預設標準能耗值且與其差值最小的節點競選成為轉發節點；之后，再由轉發節點重復上述操作搜索下一個轉發節點。相鄰轉發節點之間的傳感器節點與正方向上的轉發節點構成一個層次。轉發節點用于收集本層中所有節點數據，接收下一層轉發節點發送的數據，并將所有數據發送至上一層轉發節點。當轉發節點編號大于「L/D?-?dt/D」時，節點層次化完成。節點層次化過程見圖5。

圖5 節點層次化示意

3.2 協同數據傳輸策略下的路由選擇過程

本節基于層次聚類思想提出節能路由選擇算法。數據雙側傳輸時，左側路由與右側一致。其中節點標記0表示節點可參與轉發節點競選；節點標記1表示節點不可參與轉發節點競選；節點標記2表示節點不可參與轉發節點競選，只能將數據發送至對側對應節點，消耗能量Ed。路由選擇過程步驟如下：

Step1數據雙側傳輸，節點標記均為0，預設標準能耗值Estand=EBCi。基于節點層次化聚類確定轉發節點并得到路徑生成樹，算法如表2所示。轉發節點標記更新為1，數據傳輸過程中當轉發節點剩余能量最小值小于Eath時停止數據傳輸，進入Step2。

表2 路徑生成樹算法

Step2返回Step1直至無法形成路由，當Rr=Rl時進入Step3；當Rr>Rl&ErermEth時，進入Step4；當Rr>Rl&Erelm≤Eth時，進入Step5。

Step3節點標記均更新為0并開啟充電模式，Estand更新為EBC1，重新建立路由；當Erem>Ethn時，節點關閉充電模式，返回Step1；當Erem=0時，網絡結束運行。

Step4左側節點標記均更新為0，右側節點標記均更新為2，切換至單側傳輸，節點開啟充電模式，Estand更新為ESC1，重新建立路由；當Ererm≥Ethn&Erelm>Eth時，節點關閉充電模式，返回Step1；當Erelm≤Eth時，進入Step5。

3.3 算法復雜度

基于節點層次化聚類得到路徑生成樹，算法如表2所示，結合節點協同數據傳輸策略得到節能路由選擇算法，如表3所示。

根據表2、表3可知，節能路由選擇算法的時間復雜度由轉發節點競爭過程和算法循環次數決定，對應的時間復雜度分別為T1(n)=O(f(n))和T2(n)=O(g(n))，其中，n表示問題規模，O(f(n))表示計算函數復雜度，f(n)表示轉發節點競爭過程,g(n)表示函數循環過程，則算法時間復雜度T(n)=T1(n)·T2(n)=O(f(n)·g(n))。轉發節點競爭中需遍歷節點數目固定，不受變量L影響，故T1(n)=O(1)；算法循環次數與相鄰轉發節點編號差值相關，編號差值呈緩慢增大趨勢，設第一個編號差為M，則T2(n)=O(n/M)=O(n)，節能路由選擇算法復雜度T(n) =T1(n)·T2(n)=O(n)。

表3 節能路由選擇算法

3.4 算法性能分析

節能路由選擇算法中能量閾值Eath與Eth相關，當Estand=EBCi時，網絡進行i次路由搜索。各路由中能耗最大節點構成能耗線性方程組，如式(9)所示，各路由運行后節點剩余能量均為Eth，為理想狀態。

( 9 )

式中：Ea,b為第a條路由中能耗最大的節點在第b條路由中的能耗；ti為第i條路由的運行輪次，得到Eath為

Eath=E0-Tm·EBCi

(10)

式中：Tm=min(t1,t2,…,ti)。當EBCi=EBC1時，Eath與Eth應滿足式(11)，得到Eth≤E0/2。Ethn如式(12)所示。若右側節點能量先耗盡，則Eth最佳值Eth1如式(13)所示；若左側節點能耗先耗盡，Eth最佳值Eth2如式(14)所示,故Eth如式(15)所示。

(11)

(12)

(13)

(14)

(15)

當EPRl，EP滿足式(18)時，網絡可持續運行。

(16)

(17)

(18)

4 仿真分析

使用MATLAB軟件對所提出的節能路由選擇算法進行仿真分析，仿真參數[21]如表4所示。

表4 仿真參數

監測區域長度L=1 km時，三種情形下的冗余覆蓋比例B隨Rr與D的增大而先減小后增大，見圖6。各情形下B最小時對應最佳部署，節點部署參數如表5所示，N為傳感器節點數目，三種情形下Eth保持一致。

表5 最佳部署參數

圖6 冗余覆蓋比例變化圖

監測區域長度L=1 km時，在不同情形(Case1、 Case2、 Case3)，不同預設標準能耗下，支持網絡持續運行的最小太陽輻照度f見圖7。

圖7 最小太陽輻照度f隨Estand變化圖

圖7中各情形下f變化趨勢一致，先隨Estand的增大而快速減小，后隨Estand的增大而緩慢增加。三種情形下f的最小仿真值分別為：0.332、0.825、1.125 mW/cm2，大小關系為：Case3>Case2>Case1，Case1對太陽輻射度要求最低。隨監測區域長度L增長，三種情形下對應的f平穩增長，見圖8，增長率關系為：Case1

圖8 最小太陽輻照度f隨L變化圖

當L=1 km、f=0.25 mW/cm2時，網絡無法持續運行，三種情形下的網絡生存周期預測值與仿真值見圖9。圖中生存周期預測值略低于仿真值，Case1的網絡生存周期最長，Case3的網絡生存周期最短。

當f=0.25 mW/cm2、f=0 mW/cm2(無太陽輻照)時，隨L增長，各情形下的網絡生存周期逐漸縮短，見圖10。對比可見，同種情形下節點具有能量補給可以延長網絡生存周期，但隨L增長網絡生存周期延長量降低；網絡生存周期關系為：Case1>Case2>Case3。

圖9 網絡生存周期隨Estand變化圖

圖10 網絡生存周期隨L變化圖

由以上分析可見，節點部署模型為Case1時網絡生存周期最佳，故以此模型進行后續對比仿真。文獻[14]中算法的網絡結構與本文相似，文獻[15]中算法的應用場景與本文一致，故將所提出的節能路由選擇算法與能量有效分簇算法[14]和組數據算法[15]進行性能對比。在各算法中節點均具有太陽能補給的情況下，支持網絡持續運行的最小太陽輻照度f見表6。其中能量有效分簇算法對f的要求高于組數據算法，本文算法對f的要求最低。隨L增長三種算法對f的要求均逐漸增高，且本文算法對應的f增長率最低。可見本文算法可以降低網絡持續運行時對太陽輻照度的要求。

表6 最小太陽輻照度對比

當f=0.25 mW/cm2與f=0 mW/cm2時，三種算法對應網絡生存周期見圖11。隨L增長網絡生存周期逐漸縮短，其中本文算法對應網絡生存周期高于其他兩種算法，組數據算法對應網絡生存周期最低。這是因為組數據傳輸算法基于均勻分簇進行多路徑傳輸增加了數據傳輸距離，增大了能耗；而能量有效分簇算法中簇頭節點能耗均衡性低于本文算法。

圖11 網絡生存周期對比圖

5 結論

針對傳感器節點能量受限與網絡生存周期短問題，本文在對網絡路由算法進行研究的同時將太陽能補給技術引入到網絡中，使傳感器節點能量補給過程與路由選擇過程相融合，高效利用采集到的太陽能。然后，基于層次聚類思想提出節能路由選擇算法，采取限制節點能耗的方式均衡節點能耗，延長太陽能采集時間，從而有效地降低網絡持續運行時對太陽輻照度的要求并延長網絡生存周期。

仿真結果驗證了本文算法在提高網絡生存周期方面的有效性。進一步分析發現，隨L增長網絡生存周期延長量減小，且本文算法與能量有效分簇算法性能差距縮小，即L增長會降低能量補給效果、限制路由算法性能，下一步將針對此問題展開研究。