基于改進BIRCH的雙簇首WSN能耗優(yōu)化研究*

羅擎憶,張 江,張 晶,3,4,王健敏

(1.昆明理工大學(xué)信息工程與自動化學(xué)院，云南 昆明 650500; 2.中國船舶集團有限公司第七〇五研究所昆明分部，云南 昆明 650102;3.云南梟潤科技服務(wù)有限公司，云南 昆明 650500; 4.昆明理工大學(xué)云南省人工智能重點實驗室，云南 昆明 650500;5.云南省農(nóng)村科技服務(wù)中心，云南 昆明 650021)

1 引言

隨著無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)的不斷發(fā)展，其結(jié)構(gòu)設(shè)計愈加成熟，應(yīng)用場景也隨之日益豐富。然而，由于其部署場景的復(fù)雜性、節(jié)點終端規(guī)模的限制性，一旦部署完成，為其進行能量補充以及更換的難度和成本將十分巨大。針對這個問題，許多研究人員對初始固定能源環(huán)境下，無線傳感器網(wǎng)絡(luò)的能耗均衡以及能耗優(yōu)化問題進行了研究。

Heinzelman等[1]于2000年提出了被廣泛學(xué)習(xí)和研究的LEACH(Low Energy Adaptive Clustering Hierarchy)協(xié)議。LEACH協(xié)議中，遠離匯聚節(jié)點的簇首節(jié)點可能會因為長期保持遠距離數(shù)據(jù)傳輸而致使自身能量過早耗盡，導(dǎo)致網(wǎng)絡(luò)分割；此外，LEACH算法僅考慮節(jié)點之間的距離，未考慮簇首節(jié)點的能量狀態(tài)，若剩余能量較低的節(jié)點被選取為簇首節(jié)點，該節(jié)點會加速死亡，從而導(dǎo)致整個網(wǎng)絡(luò)生存時間縮減。

針對以上問題，學(xué)界發(fā)展了很多衍生算法來進一步優(yōu)化和提升。其中一種思路是：由于不同簇與匯聚節(jié)點的距離不同，在多跳網(wǎng)絡(luò)中，距離匯聚節(jié)點較近的簇首需要額外承擔(dān)更多數(shù)據(jù)轉(zhuǎn)發(fā)能耗[2]。為了避免因此出現(xiàn)的“熱點”問題，眾多基于距離變量的不均勻分簇協(xié)議被提出，該類分簇方法保證與匯聚節(jié)點距離較近的簇首能夠?qū)⒏嗟哪芰坑糜跀?shù)據(jù)轉(zhuǎn)發(fā)。

之后，Li等[3]使用BIRCH(Balanced Iterative Reducing and Clustering using Hierarchies)聚類方法來改進LEACH協(xié)議，提出了LEACH-B算法。利用BIRCH聚類算法將整個無線傳感器網(wǎng)絡(luò)劃分為若干個子域。由于BIRCH算法可以從多個維度進行劃分，由此得到的子域相比傳統(tǒng)分簇方法所劃分的節(jié)點簇更加精準[4]。然而，他們的簇首選擇僅僅考慮了單個子簇內(nèi)部節(jié)點的能量剩余情況，沒有對不同子簇之間通信能耗水平進行進一步的分析和約束。

石美紅等[5]在雙簇首的劃分上與前者有著不同的思路，他們將傳統(tǒng)簇首節(jié)點的通信職責(zé)一分為二：其一為內(nèi)部通信簇首，用于接收子簇內(nèi)非簇首節(jié)點所采集的數(shù)據(jù)并進行數(shù)據(jù)融合；其二為外部通信簇首，用于進行簇內(nèi)數(shù)據(jù)發(fā)送和多跳網(wǎng)絡(luò)的數(shù)據(jù)轉(zhuǎn)發(fā)。通過將簇首的能量消耗進行分割，降低了單一簇首的能量消耗速率，使之與子簇內(nèi)非簇首節(jié)點的能耗速率進一步接近[5]。但是，在進行簇首選擇時，他們只考慮了子簇內(nèi)部節(jié)點位置和剩余能量的影響，沒有從傳感器網(wǎng)絡(luò)的宏觀層面上對子簇的劃分進行分析。

本文在文獻[3,5]工作的基礎(chǔ)上，提出一種基于改進BIRCH聚類的雙簇首不均勻分簇算法—DHUCB (Dual Head Uneven Clustering based on BIRCH)。本文算法主要有以下創(chuàng)新點：

(1)采用改進的BIRCH算法從節(jié)點的剩余能量、節(jié)點距匯聚節(jié)點的距離、節(jié)點之間的距離3個維度對節(jié)點進行分簇，而不是僅僅從節(jié)點間距和剩余能量進行劃分。以此將節(jié)點劃分為基于距離向量的不均勻子簇。

(2)在進行雙簇首選取時，同樣使用上述3個維度進行選取概率計算，并分別使用獨立的概率計算公式，使內(nèi)外簇首能夠根據(jù)工作特性進一步降低子簇內(nèi)部能耗。

(3)使用概率隊列機制，從簇首選取概率和內(nèi)外通信簇首距離兩方面對簇首進行選取——而不是直接使用概率最高的簇首——以保證雙簇首策略選取函數(shù)的準確性。

最后，通過數(shù)據(jù)融合方法，從成簇的整個過程對子簇內(nèi)部能耗進行處理。經(jīng)實驗驗證，與文獻[3,5]相比，在不同規(guī)模的傳感器節(jié)點部署區(qū)域和不同規(guī)模的傳感器節(jié)點數(shù)量環(huán)境中，本文算法在網(wǎng)絡(luò)生命周期延長和節(jié)點能耗均衡的目標上，均有一定的提高。

2 系統(tǒng)模型

2.1 網(wǎng)絡(luò)模型

本文中的無線傳感器網(wǎng)絡(luò)具有N個節(jié)點并部署在M*M大小的平面上，模型中僅考慮具有通信功能的節(jié)點。其他相關(guān)網(wǎng)絡(luò)模型約束為：

假設(shè)1所有節(jié)點的初始狀態(tài)相同，即具有相同電池容量，傳輸單位數(shù)據(jù)至單位距離所消耗的能量相同，計算單位數(shù)據(jù)的能耗相同；

假設(shè)2所有節(jié)點在系統(tǒng)中的任意一個階段都不接受外部能量輸入；

假設(shè)3系統(tǒng)中僅有一個匯聚節(jié)點，該節(jié)點的能量不做限制；

假設(shè)4系統(tǒng)中的所有節(jié)點(包括匯聚節(jié)點)的物理位置在整個生命周期中不發(fā)生改變。

2.2 能量消耗模型

本文所使用的能量消耗模型與文獻[6-8]的相同。如圖1所示，當(dāng)系統(tǒng)傳輸kbit數(shù)據(jù)時，數(shù)據(jù)發(fā)送端的能量消耗為傳輸電路消耗和信號放大器的消耗；數(shù)據(jù)接收端的能量消耗為接收電路消耗。

Figure 1 Communication model圖1 通信模型

圖1中，ETX(k,d)為數(shù)據(jù)發(fā)送端的能耗，ERX(k)為數(shù)據(jù)接收端的能耗，Eelec為單位數(shù)據(jù)在發(fā)送電路上傳輸單位距離的能耗，εmp為單位數(shù)據(jù)在放大電路上傳輸單位距離的能耗。假定數(shù)據(jù)發(fā)送端與接收端的距離為d。定義一個閾值:

(1)

若通信半徑r

Table 1 Experimental simulation parameters表1 實驗仿真參數(shù)

由圖1所示模型可知，數(shù)據(jù)發(fā)送端發(fā)送kbit的數(shù)據(jù)至d距離的能耗為：

ETX(k,d)=Eelec(d)+Eamp(l,d)=

(2)

數(shù)據(jù)接收端接收kbit數(shù)據(jù)的能耗為：ERX(k)=k·Eelec。

本文中所使用的數(shù)據(jù)融合模型為任意子簇內(nèi)的數(shù)據(jù)均被壓縮到nbit，每次消耗能量EDA。

3 算法實現(xiàn)

DHUCB算法分為3個階段：(1)簇的劃分，通過改進的BIRCH聚類進行節(jié)點劃分，將整個無線傳感器網(wǎng)絡(luò)基于距離向量劃分成簇內(nèi)節(jié)點數(shù)不一的子簇；(2)簇首的選取，通過簇內(nèi)節(jié)點剩余能量、簇內(nèi)節(jié)點相對位置以及簇內(nèi)節(jié)點相對匯聚節(jié)點的位置計算出內(nèi)外通信簇首的概率隊列，之后根據(jù)內(nèi)外簇首距離確定簇首；(3)數(shù)據(jù)傳輸，對內(nèi)通信簇首接收并融合非簇首節(jié)點采集到的數(shù)據(jù)。然后由外部通信簇首將這些數(shù)據(jù)通過多跳網(wǎng)絡(luò)發(fā)送到基站。

3.1 簇的劃分

3.1.1 聚類特征

BIRCH算法利用聚類特征對不同簇的信息進行約束。其基本定義如下所示：

(3)

將其聚類特征CF定義為三元組(三維向量)CF={N,Σl,Σs},其中，N即為該簇的節(jié)點數(shù)，矢量

(4)

為各節(jié)點屬性的線性和，標量

(5)

為各節(jié)點屬性的平方和，xni為某個子簇中第n個節(jié)點的第i維屬性。

由上述定義，可以推出定理1如下所示：

定理1設(shè)CF1={N1,Σl1,Σs1},CF2={N2,Σl2,Σs2}分別代表2個獨立的聚類特征，將這2個聚類特征進行合并，合并后的聚類特征為:

CF1+CF2={N1+N2,Σl1+Σl2,Σs1+Σs2}

(6)

即聚類特征具有可加性。該定理的證明見文獻[4]。

基于聚類特征，本文推導(dǎo)出如下統(tǒng)計量及距離：

質(zhì)心為:

(7)

半徑為:

(8)

直徑為:

(9)

其中，半徑ρ是簇內(nèi)節(jié)點到簇質(zhì)心的平均距離，δ是簇內(nèi)2節(jié)點之間的平均距離，他們都可以反映簇內(nèi)節(jié)點的緊密程度。

(10)

3.1.2 聚類特征樹

傳統(tǒng)的聚類特征樹(以下稱CF樹)有3個主要參數(shù)：枝平衡因子β、葉平衡因子λ和空間閾值τ。其中，β約束枝節(jié)點內(nèi)子樹節(jié)點的數(shù)量，λ約束葉節(jié)點內(nèi)子樹節(jié)點的數(shù)量，τ約束樣本內(nèi)所有CF樹的最大半徑。

在常規(guī)BIRCH算法中，空間閾值τ是常量，即，傳感器網(wǎng)絡(luò)中所有分簇的最大半徑ρ的限定是一致的。然而，在多跳網(wǎng)絡(luò)中，靠近匯聚節(jié)點的簇首會更多地進行數(shù)據(jù)轉(zhuǎn)發(fā)。若對網(wǎng)絡(luò)內(nèi)所有子簇大小加以相同的散布約束，那么距離匯聚節(jié)點較近的外部通信簇首的能耗將會顯著增大。針對這一現(xiàn)象，本文引入動態(tài)空間閾值的概念。

初始條件下，CF樹的1個節(jié)點內(nèi)僅包含內(nèi)外通信簇首，包含2個網(wǎng)絡(luò)節(jié)點，即τ0=2。預(yù)估下一階段插入到CF樹中節(jié)點的數(shù)量為:

(11)

根據(jù)上一階段已插入的節(jié)點數(shù)量和預(yù)估本階段將要插入的節(jié)點數(shù)量，求出本階段的一個空間閾值備選值為:

(12)

利用半徑ρ與Nc的關(guān)系，使用最小二乘線性回歸估計出下一階段網(wǎng)絡(luò)中CF樹節(jié)點的最大半徑ρc+1的值，由此定義如下膨脹系數(shù)：

(13)

使用貪心法找出密度最大的葉節(jié)點：對CF樹按路徑進行遍歷，自頂向下找出包含子節(jié)點最多的葉節(jié)點后，計算該節(jié)點中距離最近的2個子節(jié)點之間的距離dmin。

與普通的單元樹不同，CF樹的節(jié)點為多元節(jié)點，即CF樹的存儲單元為包含一個至多個傳感器節(jié)點的子簇。由定理1可知，CF樹具有線性可加性，那么，當(dāng)從樹節(jié)點向其內(nèi)部元節(jié)點觀察時，有如下定義：

定義3CF樹中任意節(jié)點中所包含的每一個傳感器節(jié)點定義為一個元項E=[CFi,Si]。其中，CFi表示該節(jié)點上第i個子簇的聚類特征，Si表示指向該節(jié)點的第i個子節(jié)點的指針。

定義4本文中，CF樹的高度為H，節(jié)點Ph,i為CF樹第h層的第i個節(jié)點。其中，P1,i為第1層的第i個葉節(jié)點，PH,1為根節(jié)點。Nh,i為Ph,i內(nèi)元項的數(shù)目，Eh,i,j為節(jié)點Ph,i的第j個元項。

由定義3和定義4得到任意元項Eh,i,j(h>1)的指針所指向的子節(jié)點為：

(14)

3.1.3 CF樹的構(gòu)造

初始的CF樹為空樹。通過計算節(jié)點聚類特征的方式得到節(jié)點添加到CF樹的具體路徑。未加入CF樹的節(jié)點從該路徑插入到CF樹中。其形成過程如下如下：

步驟1初始化。初始化CF樹為空樹，此時樹的高度為0。

選擇簇直徑δ作為簇大小的散布統(tǒng)計量，以dic作為簇間距值。

步驟2從最優(yōu)路徑插入。確定當(dāng)前需要插入的子簇C(單個節(jié)點也認為是一個子簇)，計算其聚類特征信息。從根節(jié)點開始，逐層計算子簇C與CF樹內(nèi)任意一個子節(jié)點中的所有元項Eh,j,i(i=1,2,…,Nh,j)之間的距離，選出與子簇C距離最近的元項Eh,i,j*，他的指針所指向的子節(jié)點為:

(15)

記錄下步驟2中每層與子簇C距離最近的節(jié)點，所有節(jié)點依次連接，可以得到最優(yōu)插入路徑：

I=I1,I2,…,IH-1=

PH-1,iH-1,PH-2,iH-2,…,P1,i1

(16)

此路徑長度為H-1。轉(zhuǎn)步驟3。

①若N1,i1<λ，則N1,i1=N1,i1+1，轉(zhuǎn)步驟5。

②若N1,i1=λ，分裂葉節(jié)點P1,i1，選出其內(nèi)部距離最大的2個元項xα,xβ，以這2個元項為基礎(chǔ)按dic劃分余下元項，構(gòu)成新的葉節(jié)點P1,i1和P1,i1+1，把原葉節(jié)點P1,i′(i′>i1)向后置為P1,i′+1，同時更新新葉節(jié)點的聚類特征和N1,i1、N1,i′+1的值，轉(zhuǎn)步驟4。

(1)若Nh′,ih′<β，轉(zhuǎn)步驟5

(2)若Nh′,ih′=β，參照N1,i1=λ的情況分裂Ph′,ih′:

①若h′

②若h′=H，即Ph′,ih′是根節(jié)點，則上述分裂得到的新節(jié)點置為PH,1、PH,2，再為這2個節(jié)點添加一個新的父節(jié)點PH+1,1，此時NH+1,1=2且H=H+1；若待插入子簇C=?，則結(jié)束構(gòu)造，輸出CF樹，否則轉(zhuǎn)步驟2。

(1)若h′=H，路徑到達根節(jié)點：

①若待插入子簇C=?，則結(jié)束構(gòu)造，輸出CF樹；

②否則轉(zhuǎn)步驟2。

(2)若h′

3.1.4 簇的選取

本文中，由于需要對CF樹的構(gòu)造進行實時更新，其最大高度為：

H′=log2(N+1)

選取CF樹所有葉節(jié)點作為分簇結(jié)果，以得到對整個簇內(nèi)的節(jié)點最為充分的劃分。

3.2 簇首的選取

在簇首選擇階段，本文從每個簇中選擇2個簇首——一個是內(nèi)部通信簇首，用于聚合簇內(nèi)非簇首節(jié)點所采集的數(shù)據(jù)并進行數(shù)據(jù)融合；另一個是外部通信簇首，用于將內(nèi)部數(shù)據(jù)通過多跳網(wǎng)絡(luò)傳輸?shù)絽R聚節(jié)點，以及傳輸多跳網(wǎng)絡(luò)中其他子簇的數(shù)據(jù)。

簇首的選擇基于以下4個約束條件：節(jié)點的剩余能量、節(jié)點與匯聚節(jié)點的距離、節(jié)點與簇內(nèi)其他節(jié)點的距離、2個簇首之間的距離。

首先，對節(jié)點的剩余能量進行考察，保證子簇中能量較高的節(jié)點有更高的概率被選為簇首。由式(2)，數(shù)據(jù)發(fā)送端發(fā)送數(shù)據(jù)消耗的能量與發(fā)送端和接收端的距離d呈正相關(guān)，則在任意子簇內(nèi)，距離匯聚節(jié)點越近的節(jié)點發(fā)送數(shù)據(jù)至匯聚節(jié)點所消耗的能量越少，因此對匯聚節(jié)點與傳輸節(jié)點的距離進行考慮。簇內(nèi)數(shù)據(jù)傳輸所消耗的能量主要由以下2部分構(gòu)成——(1)節(jié)點將數(shù)據(jù)傳遞至內(nèi)部通信簇首的能量；(2)2個簇首之間傳遞數(shù)據(jù)的能量。因此，將子簇內(nèi)各節(jié)點之間的距離和2個簇首之間的距離納入衡量范圍。

(17)

(18)

(19)

(20)

使用上述式(18)～式(20)對式(17)中的變量進行進一步補充后，對式中的權(quán)衡常數(shù)因子{Qi}(i=1,2,3)的作用描述如下：

首先，對于內(nèi)部通信簇首，節(jié)點剩余能量與簇內(nèi)節(jié)點平均剩余能量的關(guān)系為關(guān)鍵因素，因此對其賦予最高的權(quán)值，設(shè)置Q1=0.5。節(jié)點與簇內(nèi)其他節(jié)點的距離會顯著影響數(shù)據(jù)收集所消耗的能量，所以賦給該參數(shù)以較高的權(quán)重，即Q2=0.4。但是,對于簇內(nèi)通信，內(nèi)部通信簇首節(jié)點不與匯聚節(jié)點進行直接的數(shù)據(jù)傳輸，因此子簇內(nèi)節(jié)點與匯聚節(jié)點的距離在選擇內(nèi)部通信簇首時所占的比重較小，設(shè)置Q3=0.1。

其次，對于外部通信簇首，同樣需要有較高的剩余能量。由于需要進行遠距離傳輸，其能量消耗更甚于簇外通信簇首，因此賦予其權(quán)重為Q1=0.65。外部通信節(jié)點將數(shù)據(jù)傳輸?shù)絽R聚節(jié)點，因此，該節(jié)點與匯聚節(jié)點的距離占有較大權(quán)重，賦予Q2=0.35。而它與簇內(nèi)其他節(jié)點的距離不會對外部通信能量消耗造成大的影響，相對賦予較小的權(quán)值Q3=0.05。

Figure 2 Communication cluster head election queue圖2 通信簇首選取隊列

算法1簇首選取

輸入：內(nèi)部簇首概率隊列cur(q_i)，外部簇首概率隊列cur(q_o)。

輸出：內(nèi)部通信簇首IDid_i,外部通信簇首id_o。

步驟1cur(q_i) = 1,cur(q_o)=1;

步驟2

if(cur(q_i)→next== null &&cur(q_o)→next== null)

cur(q_i) = 1,cur(q_o)=1;

id_i= *cur(q_i),id_o= *cur(q_o);exit

elsegoto步驟3

步驟3d_io=dist(*cur(q_i),*cur(q_o));

步驟4 if(d_io

id_i= *cur(q_i),id_o= *cur(q_o);exit

else

goto步驟5;

步驟5

dist_ei=dist(*cur(q_i),coc(i));

dist_eo=dist(*cur(q_o),coc(i));/*coc(centerofcluster)*/

if(dist_ei≤dist_eo)

cur(q_o) =cur(q_o)→next;

else

cur(q_i) =cur(q_i)→next;

goto步驟2。

上述簇首選取過程最大限度地保證了內(nèi)外通信簇首之間的距離小于簇內(nèi)節(jié)點的平均通信距離，即保證了內(nèi)外通信簇首數(shù)據(jù)傳輸時所消耗的能量小于單簇首方案所消耗的距離。

3.3 數(shù)據(jù)傳輸

經(jīng)過3.2節(jié)的簇首選取后，匯聚節(jié)點向各子簇內(nèi)的節(jié)點發(fā)送控制信息，包括向各個子簇發(fā)送簇首節(jié)點選取結(jié)果、向各個子簇發(fā)送其內(nèi)部數(shù)據(jù)傳輸?shù)臅r分多址TDMA(Time Division Multiple Access)方案、決定每一個外部通信簇首向外傳輸數(shù)據(jù)的下一跳地址。具體方案在本節(jié)進行討論。

數(shù)據(jù)傳輸分為2個階段：簇內(nèi)數(shù)據(jù)傳輸階段和簇間數(shù)據(jù)傳輸階段。

簇內(nèi)數(shù)據(jù)傳輸?shù)倪^程中，在每一個TDMA周期內(nèi)，子簇內(nèi)節(jié)點收集環(huán)境中的數(shù)據(jù)，并在屬于它的時間片內(nèi)將數(shù)據(jù)傳輸給內(nèi)部通信簇首。內(nèi)部通信簇首將收集到的信息進行融合，并將融合數(shù)據(jù)發(fā)送給外部通信簇首。所有節(jié)點都完成一輪傳輸后，簇內(nèi)數(shù)據(jù)傳輸階段完成。

在前一階段結(jié)束后，開始進行簇間數(shù)據(jù)傳輸階段。外部通信簇首所傳輸?shù)臄?shù)據(jù)包括2個部分：(1)自身子簇內(nèi)收集的信息；(2)其他外部通信簇首所發(fā)送的多跳數(shù)據(jù)?；诖厥椎奈恢茫鋽?shù)據(jù)傳輸可能采取單跳傳輸也可能采取多跳傳輸。匯聚節(jié)點按照一定次序要求外部通信簇首發(fā)送數(shù)據(jù)。被選中簇首基于以下原則決定采用何種傳輸策略：

(21)

當(dāng)采取多跳傳輸時，采用以下方法選擇下一跳目標：

(1)選取多個候選傳輸節(jié)點，這些節(jié)點滿足如下條件：

①候選節(jié)點與匯聚節(jié)點的距離小于該節(jié)點與匯聚節(jié)點的距離；

②候選節(jié)點與該節(jié)點的距離小于d0。

(2)候選節(jié)點選擇完畢后，使用式(22)來選擇下一跳目標：

(22)

本文中，η和φ分別取2和1。α的值由式(23)決定：

(23)

(24)

經(jīng)過上述算法，本文構(gòu)建了一種基于改進BIRCH聚類的雙簇首傳輸方案，其框架如圖3所示。

Figure 3 Algorithm framework圖3 算法框架

該方案有以下幾個優(yōu)點：(1)BIRCH聚類是多維聚類，能夠?qū)⒐?jié)點的不同信息均納入到聚類因素中；(2)BIRCH聚類為不均勻聚類，在添加距離因子后，可以控制不同距離下子簇的大小，避免出現(xiàn)“熱點”問題；(3)相較于傳統(tǒng)的主副簇首策略和內(nèi)外簇首策略，使用簇首選取隊列保證了單輪次中簇首節(jié)點能量消耗的降低；(4)減少了數(shù)據(jù)傳輸過程中的能量消耗。本文算法的時間復(fù)雜度為O(N2)，N為網(wǎng)絡(luò)節(jié)點數(shù)量。

4 實驗仿真

實驗環(huán)境為Matlab 2016a軟件，在1臺主頻為2.2 GHz的Intel?CoreTMi7 CPU,16 GB RAM的機器。采用了多種方式與文獻[3,5]中的OCMR、LEACH-B算法進行對比，以測試本文算法在提升無線傳感器網(wǎng)絡(luò)WSN生命周期、均衡網(wǎng)絡(luò)能耗上的表現(xiàn)。同時，也對實驗結(jié)果進行了分析，以驗證實驗結(jié)果與理論分析是否一致。

本文的仿真參數(shù)如表1所示。

4.1 算法評價過程及指標

為了盡可能減小數(shù)據(jù)的隨機性對算法性能穩(wěn)定性的影響，本文的所有實驗均進行了50輪節(jié)點隨機坐標分布的仿真實驗,取其均值作為仿真實驗結(jié)果。通過與對比算法在首節(jié)點死亡輪次(FND)、半數(shù)節(jié)點死亡輪次(HND)和最終節(jié)點死亡輪次(LND)3個指標上的表現(xiàn)進行比較，綜合網(wǎng)絡(luò)能量消耗趨勢對比，說明本文算法在提升網(wǎng)絡(luò)生命周期和節(jié)點能耗均衡性能上的效果。

4.2 仿真實驗結(jié)果

4.2.1 存活節(jié)點數(shù)隨通信輪次的變化

如表1所示，在進行仿真時，本文設(shè)置了3組不同的參數(shù)值。其中，仿真網(wǎng)絡(luò)1與仿真網(wǎng)絡(luò)2的部署區(qū)域大小以及匯聚節(jié)點位置不同，并且這2個參數(shù)的變化尺度均以100 m為基準，其他參數(shù)均一致，設(shè)為對照組A；仿真網(wǎng)絡(luò)2與仿真網(wǎng)絡(luò)3除節(jié)點數(shù)量不同外，其他參數(shù)均一致，設(shè)為對照組B。后續(xù)對比將以這2個對照組作為基準。

圖4a～圖4c分別展示了3個仿真網(wǎng)絡(luò)在不同參數(shù)值下，存活節(jié)點數(shù)隨通信輪次的變化趨勢。

文獻[9]指出，在存活節(jié)點數(shù)-通信輪次圖中，存活節(jié)點的變化趨勢對于評估網(wǎng)絡(luò)能耗的均衡性具有重要的指導(dǎo)意義，從出現(xiàn)第1個死亡節(jié)點開始，若存活節(jié)點的變化曲線斜率越大，則表示該曲線所代表的算法所實現(xiàn)的能耗均衡效果越好。

Figure 4 Live nodes vs.communication rounds in different simulations圖4 不同仿真網(wǎng)絡(luò)中存活節(jié)點-通信輪次圖

觀察對照組A，相對于對比算法，DHUCB所代表的曲線的平均斜率明顯大于對比算法的。此外，如表2所示，在半數(shù)節(jié)點死亡輪次的對比上，相較于對比算法，DHUCB算法的平均數(shù)值更接近于首個節(jié)點死亡的輪次。即本文算法的半數(shù)節(jié)點死亡速率更快。這2點均說明本文算法具有較好的能量均衡性。

如表2所示，對照組A中的2個對照項的仿真結(jié)果中，本文所述的DHUCB算法在首個節(jié)點死亡和半數(shù)節(jié)點死亡2個指標上的表現(xiàn)均優(yōu)于對比算法。說明在不同大小的節(jié)點部署區(qū)域內(nèi)，本文算法均達到了延長網(wǎng)絡(luò)生命周期的目的。

Table 2 Experimental results of control group A表2 對照組A實驗結(jié)果

觀察對照組B，在節(jié)點數(shù)量不同的前提下，與對照組A的實驗結(jié)果相似，本文的DHUCB算法在曲線平均斜率、半數(shù)節(jié)點死亡輪次和首節(jié)點死亡輪次關(guān)系的表現(xiàn)上依舊優(yōu)于對比算法，即在不同節(jié)點數(shù)的無線傳感器網(wǎng)絡(luò)中，本文算法均能表現(xiàn)出較好的能量均衡性。

同樣，如表3所示，在節(jié)點數(shù)量不同的前提下，本文算法在首個節(jié)點死亡和半數(shù)節(jié)點死亡2個指標上的表現(xiàn)依舊優(yōu)于對比算法。說明在不同節(jié)點數(shù)量的WSN中，本文算法均達到了減少能量消耗的目的。此外，在節(jié)點數(shù)量增大的情況下，本文算法首個節(jié)點死亡輪次縮短的比例要明顯小于2個對比算法的。這說明隨著節(jié)點數(shù)量的增大，本文算法依舊達到了延長網(wǎng)絡(luò)生命周期的目的。

4.2.2 剩余能量隨通信輪次的變化

由4.2.1節(jié)所得出的結(jié)論，本文所述的DHUCB算法在減少能量消耗方面的表現(xiàn)應(yīng)優(yōu)于對比算法。本節(jié)將從各個參數(shù)組下的對照組的剩余能量隨通信輪次變化的情況對該結(jié)論進行驗證。同時，同文獻[10]所述，本文所述的無線傳感器網(wǎng)絡(luò)生命周期定義為從網(wǎng)絡(luò)起始狀態(tài)到首個節(jié)點死亡出現(xiàn)的輪次所含的周期。

觀察對照組A，即從圖5a和圖5b所示的仿真能耗可以發(fā)現(xiàn)，在2組對照實驗中，在首個節(jié)點死亡之前，DHUCB算法的剩余能量均優(yōu)于對比算法的。相對于仿真網(wǎng)絡(luò)1，由于仿真網(wǎng)絡(luò)2擴大了部署區(qū)域，3個算法的能耗水平均有所提高，但DHUCB相對對比算法在能耗水平表現(xiàn)上依然有不小的優(yōu)勢。

觀察對照組B，即圖5b和圖5c所示的仿真能耗可以發(fā)現(xiàn)，在2組對照實驗中，在首個節(jié)點死亡之前，DHUCB算法的剩余能量依舊優(yōu)于對比算法的。相對于仿真網(wǎng)絡(luò)2，由于仿真網(wǎng)絡(luò)3的節(jié)點數(shù)量增加，系統(tǒng)通信能耗隨之增加，3個算法的能耗水平均有所提高，但是DHUCB相對對比算法在能耗水平表現(xiàn)上依然有不小的優(yōu)勢。

Figure 5 Network residual energy vs.communication rounds in different simulations圖5 不同仿真網(wǎng)絡(luò)中剩余能量-通信輪次圖

4.2.3 網(wǎng)絡(luò)能耗隨傳輸距離的變化

對比算法LEACH-B和OCMR采用的都是均勻分簇的策略，即各個子簇中的最大節(jié)點數(shù)約束是固定的。由于本文算法和對比算法均使用多跳網(wǎng)絡(luò)進行數(shù)據(jù)傳輸和轉(zhuǎn)發(fā)，相對于距匯聚節(jié)點較遠的簇首節(jié)點來說，距離匯聚節(jié)點較近的外部通信簇首承擔(dān)額外的數(shù)據(jù)轉(zhuǎn)發(fā)能耗的概率較大，成為所謂的“熱點”。節(jié)點自身能耗加大，造成網(wǎng)絡(luò)整體能耗的不均衡。本文采用了3.1.2節(jié)所述的動態(tài)空間閾值策略，使得子簇中的最大節(jié)點數(shù)和子簇與匯聚節(jié)點的距離線性相關(guān)，子簇中簇首用于簇內(nèi)數(shù)據(jù)傳輸?shù)哪芰恳哺吔诰€性相關(guān)。

Table 3 Experimental results of control group B表3 對照組B的實驗結(jié)果

Figure 6 Distance-Energy consumption per round圖6 距離-單輪通信能耗

圖6所描述的是仿真網(wǎng)絡(luò)1在某一通信輪次中不同算法的簇首能耗隨節(jié)點到匯聚節(jié)點距離的變化情況。同時，加入單個非簇首節(jié)點能耗與簇首能耗進行對比。

由圖6可知，本文算法的簇首能耗隨節(jié)點到匯聚節(jié)點距離的增長速率在3個算法中是最小的。這說明在一定程度上，本文算法相較于對比算法減輕了網(wǎng)絡(luò)中不同區(qū)域簇首的能耗差異，部分解決了均勻網(wǎng)絡(luò)的“熱點”問題。此外，將簇首能耗與單個非簇首節(jié)點的能耗進行對比。本文算法的簇首節(jié)點能耗與非簇首節(jié)點能耗的差距在3個算法中是最小的，進一步說明本文算法在能耗均衡性上的效果較好。

4.2.4 算法計算能耗對比

在評價算法能耗時，算法本身的計算能耗也占據(jù)了較大的比重。若算法在執(zhí)行能耗上進行了優(yōu)化，但算法本身的運行能耗增加，則整個算法的整體能耗反而可能增大。由文獻[11]可知，嵌入式軟件的算法級能耗計算公式為：

EA=(∑i(Bi×Ni)+Ti+Si)×L+Ej

(24)

其中，Bi為指令i的基本能耗；Ni為指令i的執(zhí)行次數(shù)；Ti為時間復(fù)雜度，Si為空間復(fù)雜度；L為軟件的運行時間，Ei為算法中的其他能耗。在本文的評估中，不考慮機器性能的差異，可以將L設(shè)置為1，其他能耗包括DHUCB算法額外計算的內(nèi)外簇首間的距離，計算出如表4所示的能耗數(shù)據(jù)。

從表4(由于3個算法的復(fù)雜度對于最終的能耗影響是一致的，因此進行總計時略去)可以看出，本文算法與對比算法的計算能耗基本處于同一水平。在進行能耗優(yōu)化的同時，沒有明顯增大算法的計算能耗。

4.3 實驗小結(jié)

由上述仿真實驗結(jié)果可知，本文DHUCB算法在不同節(jié)點數(shù)、不同節(jié)點部署區(qū)域情況下，均能達到優(yōu)于對比算法的能耗均衡能力，且能耗減少效果較好，基本達到了前述章節(jié)的理論分析所推導(dǎo)的關(guān)于網(wǎng)絡(luò)生命周期延長效果和節(jié)點能耗均衡的結(jié)果，并在一定程度上減輕了“熱點問題”。在解決上述問題的同時，本文算法計算能耗未明顯增大，本節(jié)的論述驗證了本文算法的有效性。

5 結(jié)束語

本文提出的基于改進BIRCH聚類的雙簇首不均勻分簇算法從節(jié)點的剩余能量、節(jié)點距匯聚節(jié)點的距離、節(jié)點之間的距離3個維度對節(jié)點進行分簇，對成簇過程中的數(shù)據(jù)維度進行了多方面的約束和分析。在此基礎(chǔ)上，構(gòu)建出一種基于四維信息的簇內(nèi)雙簇首的數(shù)據(jù)傳輸模型,并使用簇首隊列的簇首選取模式以保證本模型在能耗優(yōu)化上的穩(wěn)定性，達到WSN的能耗均衡和生命周期提升的目的。經(jīng)實驗驗證，在不同規(guī)模的傳感器節(jié)點部署區(qū)域和不同規(guī)模的傳感器節(jié)點數(shù)量環(huán)境中，本文算法相較于OCMR、LEACH-B算法在網(wǎng)絡(luò)生命周期和節(jié)點能耗均衡上，均有一定的提高。

Table 4 Algorithm energy consumption表4 算法能耗對比 nJ