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

陳輝，高巖

（安徽理工大學(xué)計算機(jī)科學(xué)與工程學(xué)院，安徽淮南 232001）

0 概述

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

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

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

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

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

1 網(wǎng)絡(luò)與能耗模型

1.1 無線傳感器網(wǎng)絡(luò)的層次結(jié)構(gòu)

無線傳感器網(wǎng)絡(luò)的結(jié)構(gòu)模型如圖1 所示，成員節(jié)點(diǎn)通過單跳通信方式與主簇頭通信，主簇頭或副簇頭通過多跳通信方式與基站通信。由于傳感器節(jié)點(diǎn)通常處于不便于經(jīng)常更換電池的地方，因此對傳感器網(wǎng)絡(luò)進(jìn)行能耗優(yōu)化是整個網(wǎng)絡(luò)長期穩(wěn)定運(yùn)行的必要前提［20-21］。

圖1 無線傳感器網(wǎng)絡(luò)層次結(jié)構(gòu)Fig.1 Wireless sensor networks architecture

本文的無線傳感器網(wǎng)絡(luò)模型假設(shè)［22］如下：

1）網(wǎng)絡(luò)區(qū)域由m個傳感器節(jié)點(diǎn)和1 個基站組成，傳感器節(jié)點(diǎn)均勻分布在N×M的區(qū)域內(nèi)；

2）網(wǎng)絡(luò)區(qū)域內(nèi)沒有障礙物和噪聲干擾，基站能量充足；

3）每個節(jié)點(diǎn)的電池容量、存儲能力、通信的范圍、感知范圍相同；

4）傳感器節(jié)點(diǎn)是靜止的，且信息接收節(jié)點(diǎn)能基于接收信號強(qiáng)度計算出與信息發(fā)射節(jié)點(diǎn)的距離。另外，節(jié)點(diǎn)無線發(fā)射功率可控，節(jié)點(diǎn)可以根據(jù)需要調(diào)整自身發(fā)射功率。

1.2 能耗模型

本文算法NCDH 的所有通信過程均采用文獻(xiàn)［23］的通信模型，節(jié)點(diǎn)接收或發(fā)送信息，節(jié)點(diǎn)的發(fā)射模塊或者接收模塊都會消耗能量。

傳感器節(jié)點(diǎn)發(fā)送b比特的信息能耗如下：

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

設(shè)簇內(nèi)有n個成員節(jié)點(diǎn)，則簇頭節(jié)點(diǎn)收到成員節(jié)點(diǎn)長度為l的信息進(jìn)行信息融合的能耗為：

其中：ED為簇頭節(jié)點(diǎn)融合單位bit 所消耗的能量。

1.3 網(wǎng)絡(luò)區(qū)域模型

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

圖2 遠(yuǎn)區(qū)網(wǎng)絡(luò)啟用副簇頭后的通信方式Fig.2 Communication mode with secondary cluster headers

圖3 網(wǎng)絡(luò)區(qū)域劃分Fig.3 The network area division

網(wǎng)絡(luò)區(qū)域劃分完畢后根據(jù)文獻(xiàn)［24］計算出最優(yōu)網(wǎng)絡(luò)子區(qū)個數(shù)和簇頭競爭半徑。求解|f(k)|的最小值可得出網(wǎng)絡(luò)的最優(yōu)分區(qū)個數(shù)k，f(k)的表達(dá)式如式（4）所示：

其中：M為遠(yuǎn)區(qū)網(wǎng)絡(luò)的長度。

若在遠(yuǎn)區(qū)網(wǎng)絡(luò)區(qū)域i中，區(qū)域的面積為Si，簇頭競爭半徑為Ri，區(qū)域簇頭個數(shù)為ci，則可以得出：

設(shè)q(i)為區(qū)域i的簇頭節(jié)點(diǎn)負(fù)擔(dān)的平均數(shù)據(jù)流量，則可得到式（7）：

其中：ρ為節(jié)點(diǎn)密度；a是數(shù)據(jù)融合率；q為每個節(jié)點(diǎn)的數(shù)據(jù)包大??；ci為子區(qū)i的簇的數(shù)量；k為區(qū)域個數(shù)；i為遠(yuǎn)區(qū)網(wǎng)絡(luò)子區(qū)域編號。

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

結(jié)合式（6）和式（8）可得出區(qū)域i+1 的簇競爭半徑：

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

2 NCDH 算法

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

2.1 簇頭競選

2.1.1 主簇頭競選

以文獻(xiàn)［25］為基礎(chǔ)對主簇頭競選閾值公式改進(jìn)，如式（10）所示：

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

改進(jìn)閾值公式的理論依據(jù)：首先，由于簇頭的處理任務(wù)多，轉(zhuǎn)發(fā)任務(wù)重，若能量較低的節(jié)點(diǎn)當(dāng)選簇頭會因能量消耗過快加速死亡，因此需要剩余能量高的節(jié)點(diǎn)當(dāng)選簇頭，根據(jù)節(jié)點(diǎn)的能量水平選擇簇頭是最為重要的因素；其次，當(dāng)簇頭節(jié)點(diǎn)處于的區(qū)域節(jié)點(diǎn)密集時，由能量消耗模型可知簇內(nèi)的能耗會減少，因此根據(jù)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)數(shù)量選擇簇頭可有效減少簇頭能耗；最后，簇頭節(jié)點(diǎn)與基站的距離直接影響數(shù)據(jù)傳輸?shù)穆窂介L度，因此選擇合理的傳輸距離也是路由算法設(shè)計中的重要方面。在網(wǎng)絡(luò)的運(yùn)行過程中，節(jié)點(diǎn)剩余能量、鄰居節(jié)點(diǎn)個數(shù)以及鄰居節(jié)點(diǎn)到基站的距離都較容易獲得，因此簇頭的競選過程是易于實(shí)現(xiàn)的。

2.1.2 簇的形成

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

2.1.3 副簇頭的競選

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

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

其中：di為節(jié)點(diǎn)i與基站的距離；dC為簇頭與基站的距離。

當(dāng)副簇頭選舉完成后，網(wǎng)絡(luò)進(jìn)入運(yùn)行階段。簇頭向中轉(zhuǎn)節(jié)點(diǎn)通信時，會將自身信息打包發(fā)送給中轉(zhuǎn)節(jié)點(diǎn)，中轉(zhuǎn)節(jié)點(diǎn)記錄簇頭節(jié)點(diǎn)的信息。簇頭節(jié)點(diǎn)在網(wǎng)絡(luò)運(yùn)行期間根據(jù)自身狀態(tài)判斷是否啟用副簇頭。當(dāng)簇頭能量低于簇內(nèi)節(jié)點(diǎn)平均能量時，簇頭向副簇頭與中轉(zhuǎn)節(jié)點(diǎn)發(fā)送啟用信息，中轉(zhuǎn)節(jié)點(diǎn)修改路由表與副簇頭建立連接。另外，當(dāng)簇頭緩存區(qū)隊(duì)列長度達(dá)到擁塞閾值即節(jié)點(diǎn)的緩存隊(duì)列溢出時，簇頭也會啟用副簇頭以緩解網(wǎng)絡(luò)擁塞。

2.2 NCDH 簇間路由設(shè)計

NCDH 算法采用簇內(nèi)單跳通信，簇頭與基站之間采用多跳通信方式。為了使網(wǎng)絡(luò)的通信能耗降低，延長網(wǎng)絡(luò)的生存時間，簇頭下一跳節(jié)點(diǎn)應(yīng)當(dāng)具有較高的能量且距離簇頭較近。定義中轉(zhuǎn)函數(shù)Tran（i，j）：

其中：λ+μ=1；j為節(jié)點(diǎn)i的候選下一跳節(jié)點(diǎn)；Ej為節(jié)點(diǎn)j的剩余能量；D（i，j）為節(jié)點(diǎn)i與節(jié)點(diǎn)j的距離；Davg為節(jié)點(diǎn)i與其可到達(dá)下一跳節(jié)點(diǎn)的平均距離。當(dāng)下一跳節(jié)點(diǎn)的剩余能量越多，距離節(jié)點(diǎn)i越近時其中轉(zhuǎn)函數(shù)值越大。假設(shè)簇頭節(jié)點(diǎn)ni所在的網(wǎng)絡(luò)區(qū)域?yàn)閕，則該簇頭節(jié)點(diǎn)尋找下一跳中轉(zhuǎn)節(jié)點(diǎn)的步驟是：首先獲取下一跳區(qū)域能夠接收節(jié)點(diǎn)信息包的節(jié)點(diǎn)信息；然后分別計算與下一跳區(qū)域中轉(zhuǎn)節(jié)點(diǎn)的中轉(zhuǎn)函數(shù)值；最后選擇中轉(zhuǎn)函數(shù)值最大的節(jié)點(diǎn)作為簇頭的中轉(zhuǎn)節(jié)點(diǎn)。

NCDH 算法運(yùn)行流程如下：

步驟1基站廣播初始化信息，成員節(jié)點(diǎn)接收信息后開始劃分網(wǎng)絡(luò)區(qū)域，網(wǎng)絡(luò)近區(qū)節(jié)點(diǎn)直接與基站進(jìn)行通信。

步驟2網(wǎng)絡(luò)遠(yuǎn)區(qū)各子區(qū)間根據(jù)簇頭競選規(guī)則進(jìn)行簇頭選舉，簇頭選舉完成后，成員節(jié)點(diǎn)根據(jù)簇頭競爭半徑申請入簇。

步驟3成員節(jié)點(diǎn)入簇完成后簇頭節(jié)點(diǎn)為成員節(jié)點(diǎn)分配時隙。

步驟4簇內(nèi)成員節(jié)點(diǎn)根據(jù)式（11）選舉副簇頭節(jié)點(diǎn)。

步驟5簇頭節(jié)點(diǎn)獲取相鄰區(qū)域中轉(zhuǎn)節(jié)點(diǎn)信息，分別計算與它們的中轉(zhuǎn)函數(shù)，選取中轉(zhuǎn)函數(shù)最大的節(jié)點(diǎn)作為中轉(zhuǎn)節(jié)點(diǎn)。

步驟6網(wǎng)絡(luò)進(jìn)入穩(wěn)定運(yùn)行階段，簇頭在運(yùn)行期間監(jiān)控自身剩余能量和緩存區(qū)隊(duì)列長度是否到達(dá)啟用副簇頭的條件，若滿足任一條件則及時啟用副簇頭。

步驟7若簇內(nèi)副簇頭啟動，簇頭與中轉(zhuǎn)節(jié)點(diǎn)修改路由表與副簇頭建立通信。簇頭創(chuàng)建TDMA 時隙并將簇內(nèi)信息收集融合后發(fā)送給副簇頭后進(jìn)入休眠模式。副簇頭將信息中轉(zhuǎn)后進(jìn)入休眠模式等待下一時隙的到來。若副簇頭沒有啟用則繼續(xù)進(jìn)行步驟6。

步驟8每一輪結(jié)束后，轉(zhuǎn)向步驟2，開始新的一輪。

3 NCDH 算法的能耗分析

在NCDH 算法中，區(qū)域i中的簇頭需要接收本簇成員節(jié)點(diǎn)的信息，同時也需要轉(zhuǎn)發(fā)來自網(wǎng)絡(luò)上游區(qū)域的消息。若區(qū)域i的面積為Si，區(qū)域內(nèi)的節(jié)點(diǎn)密度為ρ，區(qū)域內(nèi)的簇頭數(shù)為ci，數(shù)據(jù)融合率為a，每個節(jié)點(diǎn)的數(shù)據(jù)包大小為q。那么每個簇頭需要收集簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)包個數(shù)為（ρ×a×q×Si）/ci，若網(wǎng)絡(luò)的最優(yōu)區(qū)域數(shù)為k，那么每個簇頭需要轉(zhuǎn)發(fā)數(shù)據(jù)包的數(shù)量為（ρ×a×q×Si）(k-i)/ci。

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

其中：Q2要遠(yuǎn)小于Q1；Eto_transfer1為單簇頭網(wǎng)絡(luò)中簇頭傳輸1 bit 數(shù)據(jù)至中轉(zhuǎn)節(jié)點(diǎn)的能耗；Eto_DCH為雙簇頭網(wǎng)絡(luò)中簇頭傳輸1 bit 數(shù)據(jù)至副簇頭的能耗；Eto_transfer2為雙簇頭網(wǎng)絡(luò)中副簇頭傳輸1 bit 數(shù)據(jù)至中轉(zhuǎn)節(jié)點(diǎn)的能耗。

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

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

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

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

表1 仿真參數(shù)設(shè)置Table 1 Simulation parameter setting

在仿真實(shí)驗(yàn)中，使用DEEC 算法、MRDC 算法及GURCP 作為對比算法，4 種算法的特點(diǎn)如表2所示。

表2 4 種算法的特點(diǎn)對比Table 2 Comparison of features of four algorithms

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

4.2 結(jié)果分析

4.2.1 網(wǎng)絡(luò)能量均勻程度

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

圖4 4 種算法的節(jié)點(diǎn)剩余能量等高線Fig.4 Contour of node residual energy of four algorithms

4.2.2 區(qū)域長度的影響

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

圖5 生存節(jié)點(diǎn)數(shù)量與網(wǎng)絡(luò)區(qū)域長度的關(guān)系Fig.5 Relationship between the number of surviving nodes and the length of network area

圖6 網(wǎng)絡(luò)剩余能量與網(wǎng)絡(luò)區(qū)域長度的關(guān)系Fig.6 Relationship between the network residual energy and the length of network area

4.2.3 網(wǎng)絡(luò)生命周期

為了驗(yàn)證本文算法中雙簇頭的有效性，以網(wǎng)絡(luò)剩余能量與網(wǎng)絡(luò)初始能量的比為切入點(diǎn)，在網(wǎng)絡(luò)區(qū)域?yàn)?00 m×30 m 的條件下比較NCDH 算法有副簇頭情況、無副簇頭情況與MRDC 算法雙簇頭時算法性能差異情況。圖7 為3 種算法的網(wǎng)絡(luò)剩余能量對比柱狀圖。

圖7 不同方案的網(wǎng)絡(luò)剩余能量對比Fig.7 Comparison of network residual energy of different schemes

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

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

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

圖8 為4 種方案的網(wǎng)絡(luò)剩余能量對比柱狀圖。從圖中可以得出，有能量閾值的路由方案要優(yōu)于只有擁塞閾值的路由方案。方案1 由于無擁塞閾值和能量閾值，副簇頭會一直處于工作狀態(tài)，因此會過多消耗網(wǎng)絡(luò)能量，網(wǎng)絡(luò)生存時間過短。而本文方案（方案4）的能量閾值和擁塞閾值可以適時地加入網(wǎng)絡(luò)，能夠分?jǐn)偞仡^的通信負(fù)擔(dān)，延長網(wǎng)絡(luò)的生存時間，這證明所提算法的閾值設(shè)定是有效的。

圖8 不同方案的網(wǎng)絡(luò)剩余能量對比Fig.8 Comparison of network residual energy of different schemes

網(wǎng)絡(luò)生存節(jié)點(diǎn)數(shù)量是衡量路由算法是否優(yōu)越的重要指標(biāo)。在網(wǎng)絡(luò)區(qū)域?yàn)?00 m×30 m 條件下，DEEC、MRDC、GURCP 以及NCDH 這4 種算法的網(wǎng)絡(luò)生存節(jié)點(diǎn)曲線圖如圖9 所示，表4 為4 種算法第1 個節(jié)點(diǎn)和50%節(jié)點(diǎn)死亡時間。

表4 4 種算法節(jié)點(diǎn)死亡時間比較Table 4 Comparison of node dead time of four algorithms

圖9 網(wǎng)絡(luò)生存節(jié)點(diǎn)隨時間的變化Fig.9 Network survival nodes varying with time

通過表4 和圖9 可知，NCDH 算法在網(wǎng)絡(luò)運(yùn)行周期內(nèi)生存節(jié)點(diǎn)數(shù)較多，這表明NCDH 算法通過劃分網(wǎng)絡(luò)區(qū)域進(jìn)行不均勻分簇，再通過優(yōu)化簇頭選舉，令副簇頭適時加入網(wǎng)絡(luò)以減少簇頭的能耗，可以有效均衡網(wǎng)絡(luò)能耗。DEEC 算法由于“熱區(qū)”問題的存在導(dǎo)致節(jié)點(diǎn)死亡數(shù)量隨網(wǎng)絡(luò)的運(yùn)行逐步增加，最終導(dǎo)致節(jié)點(diǎn)全部死亡。

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

圖10 為網(wǎng)絡(luò)剩余能量隨時間變化圖。在網(wǎng)絡(luò)運(yùn)行初期，NCDH 算法的剩余能量低于MRDC 算法，這是因?yàn)樵诰W(wǎng)絡(luò)運(yùn)行初期劃分網(wǎng)絡(luò)區(qū)域以及選舉簇頭和副簇頭時消耗了部分能量傳遞初始化消息，但是隨著運(yùn)行時間的增加，網(wǎng)絡(luò)剩余能量明顯高于其他3 種算法。在第701 輪時，NCDH 算法的剩余能量下降加快，這是因?yàn)榫W(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的狀態(tài)觸發(fā)了副簇頭的啟用條件，導(dǎo)致副簇頭與簇頭節(jié)點(diǎn)、中轉(zhuǎn)簇頭通信消耗了部分能量。由于采用了不均等分簇的方法，GURCP 算法與NCDH 算法的剩余能量隨著時間的增加下降緩慢。同時，隨著網(wǎng)絡(luò)運(yùn)行時間的增加，網(wǎng)絡(luò)中生存節(jié)點(diǎn)逐步減少，導(dǎo)致轉(zhuǎn)發(fā)數(shù)據(jù)量減少，在網(wǎng)絡(luò)運(yùn)行后期，4 種算法的剩余能量減少變緩。這表明NCDH 算法可以有效延長網(wǎng)絡(luò)生存時間。

圖10 網(wǎng)絡(luò)剩余能量與時間的關(guān)系Fig.10 Relationship between the network residual energy and time

4.2.4 網(wǎng)絡(luò)吞吐量

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

圖11 網(wǎng)絡(luò)吞吐量與時間的關(guān)系Fig.11 Relationship between the network throughput and time

5 結(jié)束語

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