基于雙簇頭的WSNs 非均勻分簇路由算法

陳輝，高巖

（安徽理工大學計算機科學與工程學院，安徽淮南 232001）

0 概述

無線傳感器網絡（Wireless Sensor Networks，WSNs）由大量密集部署的傳感器節點組成［1］，通過節點間的相互協作，才能周期性地感知監控區域的狀況，并將監測數據傳輸到基站，因此傳感器節點之間的協作非常重要［2］。在分層網絡體系結構中，將網絡中的節點分成若干個簇，每個簇都指定一個簇頭［3］，簇頭負責收集并融合簇內成員節點的信息或轉發鄰居簇頭的信息，并將信息向基站方向傳遞。根據網絡的結構，簇頭通常使用單跳或多跳通信方式將數據發送到基站［4］。單跳傳輸意味著部分節點必須進行長距離通信，而長距離傳輸比短距離傳輸消耗更多的能量［5-6］，因此距離基站較遠的節點比距離基站近的節點消耗更多的能量，導致網絡的能量消耗不平衡，進而導致部分節點過早死亡，此問題可以通過使用多跳通信解決。但在多跳通信的網絡中，靠近基站的節點會出現過重的流量負載［7］，這樣易造成局部網絡擁塞，形成“熱區”問題［8］，導致網絡延遲增加、加速節點能耗，嚴重影響簇的生存周期和整個網絡的生存時間。因此，如何緩解和避免無線傳感器網絡“熱區”問題已成為研究的重點［9］。

為緩解“熱區”問題，許多路由算法被提出。低功耗自適應集簇分層型（Low Energy Adaptive Clustering Hierarchy，LEACH）協議［10］是最經典的基于單跳通信的分簇路由協議，在該協議中，簇頭節點隨機輪轉，節點以一種循環的方式來擔任簇頭并直接與基站通信，以達到均衡網絡負載的目的。但是，隨機選擇簇頭會引發簇頭分布不均勻、能量較低的節點也會被選取為簇頭，最終導致部分節點過早死忙。文獻［11］提出低功耗非均勻分簇路由（Energy-Efficient Uneven Clustering，EEUC）算法，該算法將路由通信方式分為簇內通信、簇頭與基站通信兩部分。簇內通信采用單跳通信，簇頭與基站的通信采用多跳的方式，避免了長距離數據傳輸造成的能量浪費。但是簇頭的選取方法類似LEACH 協議，容易導致簇頭分布不均勻。文獻［12］對EEUC 協議進行改進，提出一種改進型的EEUC 協議。該協議在簇頭競爭階段綜合考慮了節點的剩余能量、節點與基站的距離、鄰居節點的數目以及能耗速率，有效均衡了網絡能耗。但該算法適用于長寬差別不大的監測環境，針對狹長的環境適用性較差。

文獻［13］提出異構分簇路由（Distributed Energy-Efficient Clustering，DEEC）協議，通過引入節點剩余能量避免了低能量節點擔任簇頭節點，但沒有考慮到節點位置分布可能會造成簇頭節點分布不均勻。文獻［14］對LEACH 協議的閾值公式進行了改進，引入了節點剩余能量以及考慮了節點與基站之間的距離，增大了靠近基站的節點當選簇頭的機率。在節點競爭半徑的計算中引入了繼任以及前任能量消耗因子，使得競爭半徑的計算更加合理。雖然該算法能夠有效地均衡節點間的能耗，但是不適用于狹長型的網絡區域。文獻［15］在優化鏈路狀態路由算法的基礎上引入了多徑思想，通過路徑節點的剩余能量占比、節點的鄰居節點比例等因素對轉發路徑進行評估，并選擇最優路徑進行數據傳輸，但在中繼路由的選擇中只考慮了節點的能量因素。文獻［16］針對“熱區問題”提出一種基于梯度異構WSNs 非均勻分簇路由協議（Gradient-Based Unequal Clustering Routing Protocol，GURCP），通過虛擬梯度分區，根據節點能量計算簇頭競爭半徑，從而形成不均勻分簇，綜合節點的剩余能量和與中轉節點的距離選擇下一跳路由，最終達到均衡網絡能耗的目的，算法適用于狹長型的網絡區域。但是，協議在選擇簇頭階段只考慮了節點的能量因素，沒有考慮到節點的鄰居數量以及簇頭與中轉節點的相對距離。

此外，也有學者對簇內采用雙簇頭節點開展了研究。文獻［17］提出基于雙簇頭的多跳路由協議（Multihop Routing Protocol Based on Double Cluster-heads，MRDC）。該協議引入了副簇頭節點，在主簇頭選擇完畢后由主簇頭從成員節點中選擇剩余能量較大且距離自身較近的節點成為副簇頭，主簇頭將收集到的信息發送給副簇頭節點，由副簇頭節點進行轉發，從而減少主簇頭的能耗。但該協議中副簇頭長期工作會使網絡的整體能耗增加。文獻［18］提出一種基于副簇頭的移動自組織網絡分簇算法，在成簇階段選取權值最小的節點為副簇頭，副簇頭能夠分攤簇頭的通信負擔，必要時還可以獨立出來成為新的簇頭。該算法可以減少簇的重組次數，降低節點通信的丟包率，但副簇頭節點長期處于工作狀態中，而且頻繁進行簇內簇頭選舉也會消耗網絡能耗。文獻［19］提出一種基于非均勻劃分的自適應雙簇頭路由算法，在網絡初始化階段根據節點與基站的距離將網絡的區域進行不均勻劃分，并在靠近基站的簇內選舉產生副簇頭，幫助主簇頭分攤通信負擔。該算法可以均衡網絡節點的能量消耗，同時也延長了網絡的生存時間，但在副簇頭的選取上，只考慮了節點的能量因素，忽略了距離因素的影響，且副簇頭沒有設定啟動機制。

本文提出一種基于雙簇頭的非均勻分簇路由算法（Non-uniform Clustering Routing Algorithm Based on Double Cluster Heads，NCDH）。在網絡初始化階段將網絡區域劃分為若干子區域，根據節點所在的子區域面積計算簇頭競爭半徑，實現非均勻分簇。在簇頭選擇階段，綜合考慮節點的能量、節點與基站的距離、節點度等因素選擇主簇頭，副簇頭選擇除了考慮主簇頭選取應考慮的因素外，還需考慮與主簇頭的距離。在數據傳輸階段，簇頭節點根據自身的剩余能量以及擁塞情況決定是否啟用副簇頭，以緩解簇頭節點的壓力，從而延長簇的生存時間，最終達到均衡網絡能耗、改善“熱區”問題的目的。

1 網絡與能耗模型

1.1 無線傳感器網絡的層次結構

無線傳感器網絡的結構模型如圖1 所示，成員節點通過單跳通信方式與主簇頭通信，主簇頭或副簇頭通過多跳通信方式與基站通信。由于傳感器節點通常處于不便于經常更換電池的地方，因此對傳感器網絡進行能耗優化是整個網絡長期穩定運行的必要前提［20-21］。

圖1 無線傳感器網絡層次結構Fig.1 Wireless sensor networks architecture

本文的無線傳感器網絡模型假設［22］如下：

1）網絡區域由m個傳感器節點和1 個基站組成，傳感器節點均勻分布在N×M的區域內；

2）網絡區域內沒有障礙物和噪聲干擾，基站能量充足；

3）每個節點的電池容量、存儲能力、通信的范圍、感知范圍相同；

4）傳感器節點是靜止的，且信息接收節點能基于接收信號強度計算出與信息發射節點的距離。另外，節點無線發射功率可控，節點可以根據需要調整自身發射功率。

1.2 能耗模型

本文算法NCDH 的所有通信過程均采用文獻［23］的通信模型，節點接收或發送信息，節點的發射模塊或者接收模塊都會消耗能量。

傳感器節點發送b比特的信息能耗如下：

其中：Eelec為節點傳輸單位bit 所要消耗的能量；d為發送節點至目標節點的距離；d0為距離閾值，d0=為自由空間模型下電路的損耗系數；εa為多徑衰落信道模型下的電路損耗系數。傳感器節點接收b比特的信息能耗如下：

設簇內有n個成員節點，則簇頭節點收到成員節點長度為l的信息進行信息融合的能耗為：

其中：ED為簇頭節點融合單位bit 所消耗的能量。

1.3 網絡區域模型

為了均衡網絡的整體能耗，將網絡區域根據距離閾值TX_MAX 分為近區和遠區。當節點與基站的距離UNIT_BS≤TX_MAX 時，該區域定義為近區。在近區區域內來自網絡上游的信息包過多且處于與基站的有效通信范圍內，因此近區網絡節點可直接與基站通信，上級網絡隨機選擇該區域的高能量節點作為中轉節點。當節點與基站的距離大于TX_MAX時，該區域定義為遠區。為了延長簇生存時間，首要任務就是要解決簇頭能耗過高的問題。因此，在每一個簇內，除了設置一個負責簇內數據收集的簇頭外，還設置一個輔助簇頭轉發數據的節點。前者稱為主簇頭，后者稱為副簇頭。在啟用副簇頭后，主簇頭的主要任務是收集成員節點的信息，將其融合后轉發至副簇頭節點。副簇頭負責協助主簇頭接收轉發信息，將收集到的信息進行信息融合后發送給下一級網絡區域的轉發節點。遠區網絡節點的通信方式如圖2 所示，網絡區域劃分如圖3 所示。

圖2 遠區網絡啟用副簇頭后的通信方式Fig.2 Communication mode with secondary cluster headers

圖3 網絡區域劃分Fig.3 The network area division

網絡區域劃分完畢后根據文獻［24］計算出最優網絡子區個數和簇頭競爭半徑。求解|f(k)|的最小值可得出網絡的最優分區個數k，f(k)的表達式如式（4）所示：

其中：M為遠區網絡的長度。

若在遠區網絡區域i中，區域的面積為Si，簇頭競爭半徑為Ri，區域簇頭個數為ci，則可以得出：

設q(i)為區域i的簇頭節點負擔的平均數據流量，則可得到式（7）：

其中：ρ為節點密度；a是數據融合率；q為每個節點的數據包大小；ci為子區i的簇的數量；k為區域個數；i為遠區網絡子區域編號。

為了均衡相鄰兩區域的數據傳輸量，根據式（7），令q(i)=q(i+1)，得式（8）：

結合式（6）和式（8）可得出區域i+1 的簇競爭半徑：

根據式（9）可知距離基站近的區域簇競爭半徑較小，距離基站遠的區域簇競爭半徑較大。在經典的非均勻分簇方法中，每個簇頭節點的競爭半徑往往是由簇頭節點獨立計算得出，導致計算量增大；而通過區域劃分的方式進行非均勻分簇，簇頭節點的競爭半徑可直接通過其所在的分區以及前一分區簇頭的競爭半徑直接計算獲得，效率更高。

2 NCDH 算法

本文提出的NCDH 算法按照以輪為周期采集數據。每一輪由3 個階段組成，分別為主簇頭和副簇頭選取、簇的形成、簇間路由。

2.1 簇頭競選

2.1.1 主簇頭競選

以文獻［25］為基礎對主簇頭競選閾值公式改進，如式（10）所示：

其中：p為主簇頭在全網節點所占的比例；r為當前輪數；G為未當選簇頭節點的集合；e(i)=，Ei為節點的剩余能量；E0為節點的初始能量；f(i)=，m為節點個數；Nn為節點i的鄰居節點數目，是指在第r輪時節點i通信范圍R內可進行信息交互存活的節點；d(i)=1-，其中dt為節點i距基站的距離；dMAX=+TX_MAX 為節點所在區域的區域邊緣與基站的距離，其中：i（取值1，2，…，k）為節點所在的區域編號；M為網絡的區域長度；k為網絡區域的個數；C1、C2、C3為參數，且C1+C2+C3=1。網絡中遠區節點產生0～1 的隨機數，若隨機數<閾值T（n）則成為候選簇頭，加入候選集。若該節點為候選集中剩余能量最大值則競選成功，向區域廣播競選成功的消息；反之則進入休眠等待入簇通知。

改進閾值公式的理論依據：首先，由于簇頭的處理任務多，轉發任務重，若能量較低的節點當選簇頭會因能量消耗過快加速死亡，因此需要剩余能量高的節點當選簇頭，根據節點的能量水平選擇簇頭是最為重要的因素；其次，當簇頭節點處于的區域節點密集時，由能量消耗模型可知簇內的能耗會減少，因此根據節點的鄰居節點數量選擇簇頭可有效減少簇頭能耗；最后，簇頭節點與基站的距離直接影響數據傳輸的路徑長度，因此選擇合理的傳輸距離也是路由算法設計中的重要方面。在網絡的運行過程中，節點剩余能量、鄰居節點個數以及鄰居節點到基站的距離都較容易獲得，因此簇頭的競選過程是易于實現的。

2.1.2 簇的形成

根據簇頭的競爭半徑計算式（9）可知：隨著簇頭與基站距離增大，簇頭的競爭半徑逐增大。節點競選簇頭成功后以自身競爭半徑廣播競選成功的消息，周圍節點接收到競選成功消息后向簇頭節點發送入簇請求，待簇頭節點同意請求后加入該簇。若節點接收到多個簇頭競選成功消息，則選擇距離較近的簇頭節點發送入簇請求。

2.1.3 副簇頭的競選

副簇頭的選取思想與主簇頭類似。首先，為了使副簇頭的能量高，應當選取節點剩余能量高的節點，節點的剩余能量越高，則選舉成功的概率越大。其次，為了降低節點的傳輸能耗，副簇頭應該靠近主簇頭且位于靠近基站的方向。當節點與簇頭的距離越小時，選舉成功的概率越高。成員節點入簇完成后，主簇頭向簇內成員節點廣播副簇頭選舉通知，成員節點根據式（11）計算自身的選舉閾值并向簇內廣播計算結果，若節點的選舉閾值為簇內最大值則向主簇頭發送競選成功消息，主簇頭記錄該節點的信息，副簇頭處于等待啟動狀態。

其中：α、β為參數且α+β=1；Ei為節點剩余能量；E0為節點的初始能量；di為節點i與簇頭的距離。為了使選取的副簇頭位于靠近基站的方向，定義節點的方向閾值Di表達式如下：

其中：di為節點i與基站的距離；dC為簇頭與基站的距離。

當副簇頭選舉完成后，網絡進入運行階段。簇頭向中轉節點通信時，會將自身信息打包發送給中轉節點，中轉節點記錄簇頭節點的信息。簇頭節點在網絡運行期間根據自身狀態判斷是否啟用副簇頭。當簇頭能量低于簇內節點平均能量時，簇頭向副簇頭與中轉節點發送啟用信息，中轉節點修改路由表與副簇頭建立連接。另外，當簇頭緩存區隊列長度達到擁塞閾值即節點的緩存隊列溢出時，簇頭也會啟用副簇頭以緩解網絡擁塞。

2.2 NCDH 簇間路由設計

NCDH 算法采用簇內單跳通信，簇頭與基站之間采用多跳通信方式。為了使網絡的通信能耗降低，延長網絡的生存時間，簇頭下一跳節點應當具有較高的能量且距離簇頭較近。定義中轉函數Tran（i，j）：

其中：λ+μ=1；j為節點i的候選下一跳節點；Ej為節點j的剩余能量；D（i，j）為節點i與節點j的距離；Davg為節點i與其可到達下一跳節點的平均距離。當下一跳節點的剩余能量越多，距離節點i越近時其中轉函數值越大。假設簇頭節點ni所在的網絡區域為i，則該簇頭節點尋找下一跳中轉節點的步驟是：首先獲取下一跳區域能夠接收節點信息包的節點信息；然后分別計算與下一跳區域中轉節點的中轉函數值；最后選擇中轉函數值最大的節點作為簇頭的中轉節點。

NCDH 算法運行流程如下：

步驟1基站廣播初始化信息，成員節點接收信息后開始劃分網絡區域，網絡近區節點直接與基站進行通信。

步驟2網絡遠區各子區間根據簇頭競選規則進行簇頭選舉，簇頭選舉完成后，成員節點根據簇頭競爭半徑申請入簇。

步驟3成員節點入簇完成后簇頭節點為成員節點分配時隙。

步驟4簇內成員節點根據式（11）選舉副簇頭節點。

步驟5簇頭節點獲取相鄰區域中轉節點信息，分別計算與它們的中轉函數，選取中轉函數最大的節點作為中轉節點。

步驟6網絡進入穩定運行階段，簇頭在運行期間監控自身剩余能量和緩存區隊列長度是否到達啟用副簇頭的條件，若滿足任一條件則及時啟用副簇頭。

步驟7若簇內副簇頭啟動，簇頭與中轉節點修改路由表與副簇頭建立通信。簇頭創建TDMA 時隙并將簇內信息收集融合后發送給副簇頭后進入休眠模式。副簇頭將信息中轉后進入休眠模式等待下一時隙的到來。若副簇頭沒有啟用則繼續進行步驟6。

步驟8每一輪結束后，轉向步驟2，開始新的一輪。

3 NCDH 算法的能耗分析

在NCDH 算法中，區域i中的簇頭需要接收本簇成員節點的信息，同時也需要轉發來自網絡上游區域的消息。若區域i的面積為Si，區域內的節點密度為ρ，區域內的簇頭數為ci，數據融合率為a，每個節點的數據包大小為q。那么每個簇頭需要收集簇內節點的數據包個數為（ρ×a×q×Si）/ci，若網絡的最優區域數為k，那么每個簇頭需要轉發數據包的數量為（ρ×a×q×Si）(k-i)/ci。

因此，在單簇頭網絡中，簇頭需要發送的數據包個數Q1=（ρ×a×q×Si）(k-i+1)/ci；在雙簇頭網絡中，簇頭需要轉發的數據包個數Q2=（ρ×a×q×Si）/ci，而此時副簇頭需要轉發的數據包個數Q1=（ρ×a×q×Si）(k-i+1)/ci。根據以上分析可以得出單簇頭網絡和雙簇頭網絡中區域i的網絡能耗E1和E2分別為：

其中：Q2要遠小于Q1；Eto_transfer1為單簇頭網絡中簇頭傳輸1 bit 數據至中轉節點的能耗；Eto_DCH為雙簇頭網絡中簇頭傳輸1 bit 數據至副簇頭的能耗；Eto_transfer2為雙簇頭網絡中副簇頭傳輸1 bit 數據至中轉節點的能耗。

由1.2 節中的能耗模型可知，節點的能耗隨著通信距離的增加而變大，由于NDCH 算法優化了簇間通信的距離，因此Eto_transfer2≤Eto_transfer1；另外，由于簇內通信的距離通常小于簇間通信的距離，因此Eto_DCH＜Eto_transfer1。通過式（14）與式（15）可以得出所提算法的雙簇頭網絡相對于單簇頭網絡的能耗并沒有明顯的增加，且NDCH 算法中副簇頭并非一直處于工作狀態，只有當簇頭能量低于能量閾值或陷入擁塞時，副簇頭才會被喚醒工作，因此NDCH 算法能夠有效防止因簇頭提前死亡導致的網絡“熱區”問題。

4 實驗結果與分析

4.1 仿真參數設置

為了驗證NCDH 算法的有效性，采用MATLAB R2019a 仿真軟件分別對網絡能量均勻程度、網絡區域長度對算法性能的影響、網絡生命周期和網絡吞吐量4 個方面進行了對比實驗，實驗序號分別記為E1、E2、E3、E4。在 式（10）中，C1、C2、C3分別取值0.3、0.3、0.4；在式（11）中，α、β分別取值0.8、0.2；在式（13）中，λ、μ分別取值0.4 和0.6。其余仿真實驗參數設置如表1 所示。

表1 仿真參數設置Table 1 Simulation parameter setting

在仿真實驗中，使用DEEC 算法、MRDC 算法及GURCP 作為對比算法，4 種算法的特點如表2所示。

表2 4 種算法的特點對比Table 2 Comparison of features of four algorithms

DEEC 算法是一種基于LEACH 改進的算法，在簇頭選舉階段綜合考慮了節點的剩余能量，避免了能量過低的節點當選簇頭的情況，在數據傳輸階段使用單跳傳輸方式與基站通信。MRDC 算法是一種基于LEACH 改進的雙簇頭算法，在副簇頭的選舉上綜合考慮了節點本身的剩余能量和距簇頭節點的距離，在數據傳輸階段使用多跳傳輸方式與基站通信。GURCP 算法是一種基于虛擬區域劃分的非均勻分簇算法，在簇頭節點的選舉上改進了LEACH 的閾值公式，加入了全網平均剩余能量，在數據傳輸階段使用多跳傳輸方式與基站通信。

4.2 結果分析

4.2.1 網絡能量均勻程度

在網絡節點數為400，網絡面積為800 m×30 m的情況下，在網絡運行1 000 輪后，DEEC、MRDC、GURCP 以及NCDH 算法的節點剩余能量等高線如圖4 所示。由圖4 可知，MRDC 算法的熱區問題比較突出，網絡剩余能量很不均勻。DEEC 算法由于采用單跳傳輸，因此能量消耗較快，遠離基站的區域，節點幾乎完全死亡。GURCP 算法中節點的剩余能量集中在0.20～0.34 J 之間，在靠近基站的區域形成了“熱區”，NCDH 算法的剩余能量集中在0.35～0.41 J 之間，這兩種算法能耗較為均勻，但NCDH 算法的均勻程度更好些。

圖4 4 種算法的節點剩余能量等高線Fig.4 Contour of node residual energy of four algorithms

4.2.2 區域長度的影響

為了探究網絡區域大小對4 種算法的影響，固定網絡區域的寬度為30 m，仿真輪數為1 000 輪，網絡區域長度從100 m 至1 000 m 依次增加。在1 000 輪后網絡的生存節點數量與網絡剩余能量分別如圖5、圖6 所示。當網絡的長度逐步增加時，4 種算法的生存節點數量和網絡剩余能量都在減少。但NCDH 算法減少的變化趨勢最緩慢，這是因為NCDH 算法采用了虛擬分區的方式進行分簇，優化了簇頭和副簇頭的選舉方式，且副簇頭不會一直處于工作狀態。DEEC 由于是單跳路由算法，難以適應狹長的網絡環境，因此生存節點數量快速減少。MRDC 算法采用副簇頭長期存在的工作方式使得網絡能量開銷增加，因此表現出剩余能量與生存節點數都下降的趨勢。GURCP 算法和NCDH 算法在網絡長度增加時表現較好，但是在長距離為1 000 m左右時，NCDH 算法由于采用雙簇頭的工作方式要明顯優于GURCP 算法，這說明NCDH 算法適合用于狹長的網絡環境。

圖5 生存節點數量與網絡區域長度的關系Fig.5 Relationship between the number of surviving nodes and the length of network area

圖6 網絡剩余能量與網絡區域長度的關系Fig.6 Relationship between the network residual energy and the length of network area

4.2.3 網絡生命周期

為了驗證本文算法中雙簇頭的有效性，以網絡剩余能量與網絡初始能量的比為切入點，在網絡區域為800 m×30 m 的條件下比較NCDH 算法有副簇頭情況、無副簇頭情況與MRDC 算法雙簇頭時算法性能差異情況。圖7 為3 種算法的網絡剩余能量對比柱狀圖。

圖7 不同方案的網絡剩余能量對比Fig.7 Comparison of network residual energy of different schemes

由圖7 可知，3 種算法運行至網絡剩余能量比為0.8 的時間大致相同，但是當運行的輪數逐漸增大時差距逐漸拉開，MRDC 算法隨著運行輪數的增加，剩余能量降低的速度越來越快，造成這種現象的原因主要是由于該算法副簇頭一直處于工作狀態，造成了不必要的能量消耗。另外，MRDC 算法在選舉簇頭以及副簇頭時對節點的自身因素考慮較少，而NCDH 算法在選舉簇頭時能夠選取更優質的節點作為簇頭，因此在NCDH 算法單簇頭的情況下網絡剩余能量下降的速度也更緩慢。NCDH 算法在使用雙簇頭方式時，通過設置副簇頭啟用時間有效避免了不必要的能量開銷，且副簇頭的出現也均衡了簇頭的通信負擔，因此在使用雙簇頭時網絡生存時間最長，這充分證明了NCDH 算法雙簇頭的有效性。

為了驗證本文閾值設定的有效性，設置了4 種對比方案，如表3 所示。

表3 4 種對比方案信息Table 3 Information of four comparison schemes

圖8 為4 種方案的網絡剩余能量對比柱狀圖。從圖中可以得出，有能量閾值的路由方案要優于只有擁塞閾值的路由方案。方案1 由于無擁塞閾值和能量閾值，副簇頭會一直處于工作狀態，因此會過多消耗網絡能量，網絡生存時間過短。而本文方案（方案4）的能量閾值和擁塞閾值可以適時地加入網絡，能夠分攤簇頭的通信負擔，延長網絡的生存時間，這證明所提算法的閾值設定是有效的。

圖8 不同方案的網絡剩余能量對比Fig.8 Comparison of network residual energy of different schemes

網絡生存節點數量是衡量路由算法是否優越的重要指標。在網絡區域為800 m×30 m 條件下，DEEC、MRDC、GURCP 以及NCDH 這4 種算法的網絡生存節點曲線圖如圖9 所示，表4 為4 種算法第1 個節點和50%節點死亡時間。

表4 4 種算法節點死亡時間比較Table 4 Comparison of node dead time of four algorithms

圖9 網絡生存節點隨時間的變化Fig.9 Network survival nodes varying with time

通過表4 和圖9 可知，NCDH 算法在網絡運行周期內生存節點數較多，這表明NCDH 算法通過劃分網絡區域進行不均勻分簇，再通過優化簇頭選舉，令副簇頭適時加入網絡以減少簇頭的能耗，可以有效均衡網絡能耗。DEEC 算法由于“熱區”問題的存在導致節點死亡數量隨網絡的運行逐步增加，最終導致節點全部死亡。

MRDC 算法引入雙簇頭方案解決了簇頭節點能耗過高的問題，但是雙簇頭自網絡運行開始就共存，導致網絡整體能耗增加，在運行到第1 034 輪后網絡中生存節點數量迅速減少。GURCP 算法與NCDH 算法的節點死亡速度相對均衡，由于NCDH 算法采用非均勻分簇并適時加入副簇頭均衡簇頭能耗，從而延長了簇的生存時間，在網絡生存時間上優于其他3 種算法。

圖10 為網絡剩余能量隨時間變化圖。在網絡運行初期，NCDH 算法的剩余能量低于MRDC 算法，這是因為在網絡運行初期劃分網絡區域以及選舉簇頭和副簇頭時消耗了部分能量傳遞初始化消息，但是隨著運行時間的增加，網絡剩余能量明顯高于其他3 種算法。在第701 輪時，NCDH 算法的剩余能量下降加快，這是因為網絡中簇頭節點的狀態觸發了副簇頭的啟用條件，導致副簇頭與簇頭節點、中轉簇頭通信消耗了部分能量。由于采用了不均等分簇的方法，GURCP 算法與NCDH 算法的剩余能量隨著時間的增加下降緩慢。同時，隨著網絡運行時間的增加，網絡中生存節點逐步減少，導致轉發數據量減少，在網絡運行后期，4 種算法的剩余能量減少變緩。這表明NCDH 算法可以有效延長網絡生存時間。

圖10 網絡剩余能量與時間的關系Fig.10 Relationship between the network residual energy and time

4.2.4 網絡吞吐量

圖11 為在網絡的生存周期內，基站接收到數據包的變化情況。NCDH 算法的網絡吞吐量分別是DEEC、MRDC、GURCP 算法的1.64 倍、1.36倍和1.08 倍。DEEC 算法的網絡吞吐量在生命周期內最小。MRDC 算法與GURCP 算法的網絡吞吐量相差較大，這是因為GURCP 算法采用了不均等分簇使網絡的生命周期有所增加，而MRDC 算法雖然采用雙簇頭的方案減少了簇頭的能耗，但是副簇頭一直存在，增加了網絡整體的能耗，使網絡的生命周期有所下降。NCDH 算法在網絡初期進行網絡區域劃分，副簇頭只有在滿足一定條件下才啟用，并且在不同區域副簇頭的啟用時間也可能不同，進而延長了網絡的生存時間，提升了網絡的整體吞吐量。

圖11 網絡吞吐量與時間的關系Fig.11 Relationship between the network throughput and time

5 結束語

針對無線傳感器網絡簇頭間能耗不均衡導致的“熱區”問題，本文提出一種基于雙簇頭的非均勻分簇路由算法，在路由初始化階段將網絡劃分為若干子區域，在雙簇頭選擇階段綜合考慮節點的剩余能量、節點到基站的距離、節點度等因素，優化網絡中簇頭的選擇。根據簇頭所在區域不同賦予簇頭不同的競爭半徑，使各簇頭的能耗更加均衡。在網絡運行階段，簇頭根據自身情況決定是否啟用副簇頭，緩解簇頭節點的壓力。實驗結果表明，該算法能有效均衡網絡能耗，解決網絡“熱區”問題，延長網絡的生存時間。下一步將考慮在真實場景（如隧道、礦井巷道等）中部署傳感器網絡，并探究實際場景中的干擾因素對路由算法的影響。