基于梯度的異構WSNs非均勻分簇路由協議

張文柱，孫瑞華，高 鵬，孔維鵬

(西安建筑科技大學 信息與控制工程學院，西安 710055)

E-mail:srh_xauat@163.com

1 引 言

為滿足我國城市化建設的發展需求，充分利用城市地下空間資源，需要加快城市地下綜合管廊的建設[1].然而城市地下綜合管廊管線種類多樣，設備繁雜，采用傳統人工巡檢和維護等方式會存在智能化水平不足、工作效率低下、運營成本偏高等問題，因此建立完善的綜合管廊環境監測系統是十分必要的[2].

無線傳感器網絡WSNs(Wireless Sensor Networks)是由大量部署在監測區域內的、具有無線通信與計算能力的微小、廉價傳感器節點，通過自組織方式構成的，能根據環境自主完成指定任務的分布式智能化網絡系統.其被廣泛應用于戰場監視、環境監測、智慧農業和目標追蹤等領域[3，4].傳感器節點部署區域環境復雜，能量受限，在大規模無線傳感器網絡中，存在網絡能耗不均衡，網絡壽命較短等問題[5].因此研究適用管廊環境的節能高效的數據傳輸策略，均衡網絡能耗，延長網絡生命周期成為WSNs路由協議研究的關鍵.

為了均衡網絡能耗，緩解“能量熱區”問題，許多路由協議被提出.LEACH(Low Energy Adaptive Clustering Hierarchy)協議[6]最早采用分簇算法，節點輪流擔任簇首并通過單跳方式與Sink節點通信.但是容易造成簇首節點分布不均、能量較低等問題.Qing等[7]提出DEEC協議，引入剩余能量因子，避免了能量較低節點擔任簇首.但是沒有考慮節點位置影響，可能會造成簇首節點分布不均勻.黃利曉等[8]提出了LEACH-improved路由協議，對簇首選舉閾值進行了改進,保證了節點能量負載的均衡性.Fu等[9]引入模糊邏輯推理的方式，綜合節點剩余能量、通信半徑、鄰居節點的數量和節點的計算能力進行簇首選舉，仿真表明該方法可以有效均衡網絡能耗.但是以上算法只是通過改善簇首選舉方法降低網絡能耗，并沒有解決“能量熱區”問題.

Soro等[10]針對“能量熱區”問題，首次提出不均等分簇路由協議UCS，根據簇首期望轉發負荷調整成簇規模，解決了不同簇首間的負載均衡問題.Lin等人[11]提出EEREG路由協議，劃分網絡分區，計算簇首最優競爭半徑，在延長網絡壽命的同時均衡了全網能量消耗.李雙雙等[12]引入群體智能優化算法PMBA優化簇首選舉，建立多基站傳輸機制，緩解了“能量熱區”問題.然而，上述路由算法大多適用于長寬差距不大的監測環境，針對管廊狹長環境適用性較差.為此，周志鑫等[13]提出LEACH-HC協議，采用選舉簇首與固定簇首混合部署策略；余修武等[14]針對深井環境提出UCRP協議，根據距離因子、剩余能量因子和鄰居節點個數計算簇首競爭半徑，有效降低節點能量開銷.

綜上所述，學者們提出了大量改進的路由協議，在長寬差距不大的典型應用環境中取得了很好的效果，但是由于應用背景不同，路由算法間的通用性較低，管廊中傳感器節點異構性較強，適用管廊等狹長應用背景的路由協議較少.本文針對綜合管廊環境特點和應用需求，提出了一種基于梯度的異構無線傳感器網絡非均勻分簇路由協議GUCRP(Gradient-Based Unequal Clustering Routing Protocol)，將網絡進行虛擬梯度分區，計算每一梯度最優簇數，根據節點能量異構性計算簇首競爭半徑，形成非均勻分簇；綜合剩余能量因子和距離因子選取下一跳路由,最終達到均衡網絡能耗，改善“能量熱區”問題，延長網絡壽命的目的.

2 網絡與能耗模型

2.1 網絡模型

綜合管廊是一種長帶狀分布的空間，可以將其簡化為一個L×M的矩形區域(L?M).假設傳感器網絡由N個隨機部署的傳感器節點組成，模型具體描述如下：1)Sink節點位于管廊外側，計算能力不受限制，有持續的能量供應.2)節點初始能量不同，周期性傳輸數據.3)節點位置一旦部署不再改變，可以通過定位算法獲悉自身位置.4)節點可以感知自身剩余能量，并對數據進行融合.5)節點無線發射功率可自主調控.

建立基于梯度的路由協議，需對網絡進行分區設計，具體步驟如下：

網絡部署階段，所有節點初始梯度值IG設置為0.

1.Sink節點廣播一條包含跳數值HC的信息Imessage給其鄰居節點，初始HC為0.

2.鄰居節點接收Imessage后，更新自身梯度值IG(IG=HC+1),更新后的IG替換Imessage中的HC值并將此消息繼續廣播給鄰居節點.

3.收到新消息的節點繼續更新自身梯度值，并重復步驟3繼續向下傳遞，直至網絡中所有節點設置完畢.

所有節點不重復接收消息，自身梯度值一旦設置將不再更改.最終整個網絡內的傳感器節點依據自身梯度值，構建梯度路由模型，如圖1所示.

2.2 能耗模型

在無線傳感器網絡中，傳感器節點的能量主要消耗在感知、傳輸和處理數據過程中，其中數據傳輸能耗占比最大[15].根據發送端與接收端的距離，無線傳感器網絡信道模型可以分為兩種：自由空間模型和多徑衰減模型.本文中能耗模型如圖2所示.

節點發送kbit數據消耗的能量為：

(1)

接收kbit數據消耗的能量為：

Erx(k，d)=kEelec(k)

(2)

式中：Eelec表示發送電路或接收電路發送或接收1bit數據的能耗；εfs和εamp表示放大器特性常數；d表示傳輸距離；d0表示傳輸距離閾值,計算如下：

(3)

圖2 能耗模型Fig.2 Energy consumption model

3 GUCRP路由協議

本文提出的GUCRP路由協議包括網絡初始化、簇首選舉和數據傳輸三個階段.

3.1 網絡初始化階段

網絡初始化階段，監測區域被劃分為k個梯度單元，各梯度單元區域的面積集合為S,則S={S1,S2,S3，…，Sk}.為了達到更好的網絡性能，從最小化相鄰梯度單元數據傳輸能耗出發，計算最佳梯度單元個數.

假設每一輪梯度i中簇首節點ni所承擔的平均數據傳輸量為Dai，可得到下式：

(4)

其中:Si代表梯度i區域面積；ρ代表節點密度；δ代表數據融合率；a代表每一個傳感器節點的數據包大小；ci代表梯度i中簇首數量.

設梯度i單元中，簇首節點發送數據的平均能耗為ECH(i),可得：

ECH(i)=Dai(Eelec+εampdA4)

(5)

其中：dA代表相鄰兩梯度單元中簇首節點間的平均距離.

假設節點服從均勻分布，相鄰兩梯度單元之間簇首的平均距離dA可以表示如下：

(6)

結合式(4)、式(5)、式(6)可得梯度i中簇首節點的數據總傳輸能耗為：

(7)

為了最小化數據傳輸能耗，ECH應取最小值.對ECH求解關于k的一階導數，可得：

(8)

令式(8)等于0，可得：

(9)

3.2 簇首選舉階段

3.2.1 簇首競選

對分布式分簇策略而言，簇首的選擇至關重要.簇首節點不僅需要轉發簇成員節點采集的信息，還需要承擔簇間信息中繼任務，相比簇成員節點會消耗更多能量.GUCRP路由協議在簇首選擇階段，綜合考慮節點的剩余能量因子和距離因子，使剩余能量最高的節點擔任最終簇首.首先采用式(10)計算出節點競選簇首的概率.

(10)

在分布式路由算法中，獲取精確的全網平均剩余能量信息較為困難且會造成信息冗余，耗能增加.因此采用估算法統計全網平均剩余能量，如式(11)所示：

(11)

式(11)中：Eini代表全網初始總能量；Eround代表每一輪消耗的能量[7]；r為當前輪次.

計算出簇首競選概率后，引入閾值函數作為簇首節點競選的門限值，如式(12)所示.

(12)

式(12)中：pi為節點ni競選簇首的概率；r為當前輪數；G是1/pi輪中未被選舉為簇首節點的集合.

初始階段節點ni在(0,1)區間產生一個隨機數與閾值函數門限值比較，決定是否當選候選簇首節點；入選為候選簇首節點后通過簇首競爭半徑建立鄰居表信息，根據剩余能量因子確定最終簇首節點.簇首節點競選成功后廣播FinalHead_msg,其余節點接收到消息后回復QuitHead_msg,選舉結束.

3.2.2 簇首競爭半徑

為了緩解“能量熱區”問題，GUCRP協議從均衡網絡能耗角度出發，提出了不均等分簇路由協議，采用基于梯度的路由對網絡進行均等劃分，使靠近Sink節點的區域形成更多的分簇分散大量的數據轉發任務.

為了均衡相鄰梯度單元中簇首數據傳輸量，令Dai=Da(i+1)，可得：

(13)

同時，梯度1單元中簇首數量可以由式(14)得出：

c1=kfρS1

(14)

kf為梯度1中簇首所占百分比.

通過式(13)、式(14)計算出各梯度中簇首的最佳數量后，引入簇首競爭半徑求解最終簇首競爭半徑.

假設網絡中傳感器節點均為同構，則在同一梯度中形成的若干分簇大小規模均相等.設Ri為梯度i中簇首的競爭半徑，可得：

(15)

結合式(13)和式(15)可得出Ri和Ri+1之間的關系，如下所示：

(16)

而在本文提出的異構網絡中，傳感器節點分為普通節點和高級節點.為了均衡網絡能耗，在同一梯度中由高級節點擔任簇首的簇成簇規模要大于普通節點擔任簇首的簇成簇規模，即高級節點的簇首競爭半徑大于普通節點的簇首競爭半徑.

假設E0代表普通節點的初始能量，μ代表高級節點占總節點數的百分比，α代表高級節點超出普通節點能量的百分比.網絡中所有傳感器節點的初始總能量可以被表示為：

ET=ρS(1-μ)E0+ρSμ(1+α)E0=ρS(1+αμ)E0

(17)

式(17)表明，在異構網絡中實質上可以認為有ρS(1+αμ)個初始能量為E0的普通節點.

在同構網絡中，梯度i單元中傳感器節點的個數可以表示為ρSi，單個傳感器節點的覆蓋范圍為1/ρ，因此在梯度i單元中簇首的平均覆蓋范圍可以被表示為：

(18)

由公式(17)可得，在異構網絡中，梯度i單元中傳感器節點的個數增加了(1+αμ)倍.單個傳感器節點的覆蓋范圍為1/ρ(1+αμ)，梯度i中簇首的平均覆蓋范圍表示如下：

(19)

因此，梯度i中普通節點擔任簇首和高級節點擔任簇首所形成的簇首加權平均覆蓋范圍表示如下：

(20)

根據式(19)、式(20)，可以得出在異構網絡中普通節點和高級節點的簇首競爭半徑，表示如下：

(21)

3.3 數據傳輸階段

GUCRP協議數據傳輸采用單跳與多跳相結合的方式.根據梯度分區，梯度1單元中節點的下一跳是Sink節點，節點采集到的數據直接發送給Sink節點，其他梯度節點通過多跳方式傳輸數據.假設節點ni是梯度i(1

步驟 1.ni從相鄰靠近Sink節點的i-1梯度單元中隨機選擇ωci-1個簇首節點作為下一跳候選簇首節點NEXT_Htentative，并建立候選簇首節點集合SCH.其中ω是(0,1)之間的隨機數.

步驟 2.ni與集合SCH中的候選簇首節點交換路由信息，獲取剩余能量和距離信息，并通過式(22)、式(23)計算候選簇首節點集合SCH中各簇首節點的代價函數Cost(i，j)，如下所示：

(22)

(23)

式中：ej代表候選節點的剩余能量；e0代表節點的初始能量；dis(ni,nj)代表節點i到j的距離；dis(ni,BS)和dis(nj,BS)分別代表節點i和j到Sink節點的距離.

最終節點ni選擇代價最小的候選簇首節點作為最終下一跳簇首節點NEXT_Hfinal.

3.4 GUCRP協議整體流程

按照GUCRP協議規定，網絡初始化階段Sink節點向全網播報一條報文消息，其中包含網絡的梯度分區值，每一梯度的最佳分簇值，同構網絡中簇首節點的競爭半徑以及異構網絡中高級節點和普通節點擔任簇首時的競爭半徑.接收到此消息后所有節點進入分簇階段.簇首具體選舉過程如算法1所示.

算法1.

1.start

2.p←rand(0,1)

3.ifp

4.n←TCH，計算簇首競爭半徑R

5. 廣播CompeteHead_msg(ID,IG,Re)

6.else

7.n進入階段Sleeping

8.EXIT

9.endif

10.當節點a收到CompeteHead_msg

11.計算n和a之間的距離d(n,a)

12.ifd(n,a)

13.a←Nn_CH

14.end if

15.ifNn_CH=NULLthen

16.n←FinalCH

17. EXIT

18.else

19.Remax(Ren,Rea)，?a∈Nn_CH←FinalCH

20. EXIT

21.FinalCH廣播FinalHead_msg

22.end

簇首選舉成功后，非簇首節點根據簇首節點廣播信號強度，計算簇首節點與自身之間的距離，最終根據距離因子，選取最近的簇首入簇.進入數據傳輸階段，簇首節點依據代價函數選取下一跳路由進行數據傳輸.在數據傳輸階段為了避免信道沖突，簇首節點采用時分多址技術(TDMA)為不同的簇成員節點分配時隙，簇成員節點只在所分配的時隙內傳遞數據，其余時間處于睡眠狀態.GUCRP協議的流程圖如圖3所示.

圖3 GUCRP協議流程圖Fig.3 GUCRP protocol flow chart

4 仿真實驗及性能分析

4.1 仿真參數設置

實驗采用MATLAB R2016a仿真軟件進行仿真測試，設置兩種方案：從網絡壽命、網絡能耗、吞吐量三個方面將GUCRP協議與DEEC協議、OCRP協議[16]、LEACH-HC協議進行比較分析，驗證GUCRP協議的有效性；改變網絡中的節點密度，驗證協議的擴展性.

參考符合城市綜合管廊的特殊環境，仿真環境設置為1000×10的長方形區域，具體仿真參數設置如表1所示.

GUCRP協議仿真實驗時，公式(21)中權重因子γ=0.3和β=0.7.

4.2 仿真結果分析

4.2.1 網絡有效性分析

本文以節點的平均剩余能量作為網絡能耗的評價標準，網絡壽命是衡量算法有效性的重要指標.本文以節點死亡數量隨網絡運行時間的變化來衡量網絡壽命.

表1 仿真參數Table 1 Simulation parameters

一般情況下，節點的平均剩余能量越大說明網絡的生命周期越長.圖4為4種協議的節點平均剩余能量隨網絡運行輪數增長的變化情況.可以直觀得出，剛開始時GUCRP協議的節點剩余能量較低，但隨著網絡運行輪數的增長，GUCRP協議的節點平均剩余能量明顯大于其他3種協議.這是因為GUCRP協議建立基于梯度的不均等分簇路由協議，在網絡初始化階段需要消耗部分能量傳遞初始化消息，在后期網絡拓撲趨于穩定后能耗減小.由于采用了最優分簇思想，優化簇首選舉策略，OCRP和GUCRP協議的能量消耗曲線隨時間增長緩慢下降.同時隨著輪數的增加，網絡中生存節點數量變少，當節點被選為簇首時，所需要轉發的數據負擔逐漸變小，4種協議的能量消耗率逐漸變低.這表明GUCRP協議可以有效延長網絡的生命周期.

圖4 節點平均剩余能量隨時間變化圖Fig.4 Graph of node average remaining energy over time

圖5 節點死亡數量隨時間變化圖Fig.5 Graph of node deaths over time

圖6 網絡吞吐量Fig.6 Network throughput

圖5為4種協議死亡節點數量隨網絡運行輪數增長變化的情況.FND(First Node Death)代表第一個節點陷入死亡，如圖5所示DEEC協議、LEACH-HC協議、OCRP協議、GUCRP協議出現FND時間分別為321輪、376輪、509輪、692輪.這表明GUCRP協議通過對網絡進行分區劃分最優簇數，根據節點能量異構性[16]進行不均等分簇，優化簇首選舉機制，更好的均衡了網絡能耗，避免了單個節點因過度耗能而過早死亡的現象.另外，由于“熱區”問題的存在，DEEC協議隨時間增長死亡節點數量增速加快；同時LEACH-HC協議采用混合分簇策略，在固定簇首的能量耗盡之后，網絡中出現節點突發大量死亡現象；而OCRP協議和GUCRP協議節點的死亡速度相對均衡.由于GUCRP協議采用非均勻分簇方法均衡不同簇首間的能量消耗，因此在網絡生存時間和穩定性方面優于其他3種協議.

網絡吞吐量是指Sink節點在整個網絡生命周期內接收到的數據量，可以直觀反映網絡的整體性能.

圖6為在網絡生命周期內，Sink節點接收到的數據包變化情況.GUCRP協議的網絡吞吐總量分別是其他3種協議的1.58倍、1.34倍和1.07倍.DEEC 協議在生命周期內的吞吐量最小，LEACH-HC協議和OCRP協議的網絡吞吐量相差較大，這是因為兩者都采用均勻分簇思想，數據傳輸機制大致相像，但LEACH-HC協議中包含部分固定簇首，能量過早耗盡后即陷入死亡.GUCRP協議在數據傳輸階段，通過基于梯度的不均等分簇策略，不均等分簇策略均衡節點能耗，延長了網絡生命周期，提升了網絡的整體吞吐量.

4.2.2 網絡的擴展性分析

為進一步檢驗算法的性能，保持網絡環境和仿真參數不變，改變網絡中節點密度，將節點數量取值區間設為[100,300]，從網絡平均能量消耗和網絡吞吐量方面進行仿真分析.

圖7 網絡平均能量消耗Fig.7 Network average energy consumption

隨著節點數量的增多網絡中節點密度逐漸增大.圖7為改變網絡中節點密度后，GUCRP協議和DEEC、LEACH-HC、OCRP協議的網絡平均能耗圖.從圖中可以看出，GUCRP協議和OCRP協議相較于其他兩種協議相對較穩定，在不同節點密度的網絡環境中網絡能耗呈緩慢增長的趨勢.這是由于隨著節點密度的增加，網絡中傳輸的數據包變大，所消耗的能量增加，GUCRP和OCRP協議充分考慮節點的剩余能量，對簇首節點進行優化分配，最大限度地保證了網絡的連通性和均衡性，使網絡能耗最小化.

圖8展示了不同節點密度條件下四種協議的網絡吞吐量變化情況，從圖中可以得出，隨著節點密度的增加，DEEC協議網絡吞吐量增長速度慢于其他三種協議.這是因為隨著節點密度的增加，數據傳輸過程中產生了數據沖突，造成了更多的能耗，影響了整體吞吐量.與此同時伴隨著節點密度的增加，簇首選舉過程中的傳輸延遲逐漸增大，LEACH-HC、OCRP和GUCRP協議的網絡吞吐量增長率逐步降低，由于GUCRP事先劃分了路由分區，采用最優分簇策略，受此因素影響較小.

圖8 網絡吞吐量Fig.8 Network throughput

5 結 論

針對管廊監測系統中無線傳感器網絡節點能量受限，長距離傳輸引發“能量熱區”，導致網絡生命周期較短問題，提出了一種基于梯度的異構無線傳感器網絡非均勻分簇路由協議GUCRP.GUCRP首先對網絡進行分區，計算各梯度最優分簇和能量異構節點的競爭半徑，靠近Sink節點區域的簇首節點競爭半徑較小，以此均衡不同梯度中的能量消耗，改善“能量熱區”問題；同一梯度單元中高級節點簇首競爭半徑大于普通節點，避免了能量較低節點過早陷入死亡.在數據傳輸過程綜合考慮下一跳節點的剩余能量和節點位置，保證數據傳輸的通信代價最小，降低網絡能耗.仿真結果表明該算法能有效均衡了網絡能耗，延長了網絡的生存周期.