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

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

1 引言

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

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

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

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

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

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

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

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

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

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

2 系統(tǒng)模型

2.1 網(wǎng)絡模型

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

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

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

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

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

2.2 能量消耗模型

本文所使用的能量消耗模型與文獻[6-8]的相同。如圖1所示，當系統(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ù)融合模型為任意子簇內的數(shù)據(jù)均被壓縮到nbit，每次消耗能量EDA。

3 算法實現(xiàn)

DHUCB算法分為3個階段：(1)簇的劃分，通過改進的BIRCH聚類進行節(jié)點劃分，將整個無線傳感器網(wǎng)絡基于距離向量劃分成簇內節(jié)點數(shù)不一的子簇；(2)簇首的選取，通過簇內節(jié)點剩余能量、簇內節(jié)點相對位置以及簇內節(jié)點相對匯聚節(jié)點的位置計算出內外通信簇首的概率隊列，之后根據(jù)內外簇首距離確定簇首；(3)數(shù)據(jù)傳輸，對內通信簇首接收并融合非簇首節(jié)點采集到的數(shù)據(jù)。然后由外部通信簇首將這些數(shù)據(jù)通過多跳網(wǎng)絡發(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設CF1={N1,Σl1,Σs1},CF2={N2,Σl2,Σs2}分別代表2個獨立的聚類特征，將這2個聚類特征進行合并，合并后的聚類特征為:

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

(6)

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

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

質心為:

(7)

半徑為:

(8)

直徑為:

(9)

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

(10)

3.1.2 聚類特征樹

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

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

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

(11)

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

(12)

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

(13)

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

與普通的單元樹不同，CF樹的節(jié)點為多元節(jié)點，即CF樹的存儲單元為包含一個至多個傳感器節(jié)點的子簇。由定理1可知，CF樹具有線性可加性，那么，當從樹節(jié)點向其內部元節(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內元項的數(shù)目，Eh,i,j為節(jié)點Ph,i的第j個元項。

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

(14)

3.1.3 CF樹的構造

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

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

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

步驟2從最優(yōu)路徑插入。確定當前需要插入的子簇C(單個節(jié)點也認為是一個子簇)，計算其聚類特征信息。從根節(jié)點開始，逐層計算子簇C與CF樹內任意一個子節(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。轉步驟3。

①若N1,i1<λ，則N1,i1=N1,i1+1，轉步驟5。

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

(1)若Nh′,ih′<β，轉步驟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=?，則結束構造，輸出CF樹，否則轉步驟2。

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

①若待插入子簇C=?，則結束構造，輸出CF樹；

②否則轉步驟2。

(2)若h′

3.1.4 簇的選取

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

H′=log2(N+1)

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

3.2 簇首的選取

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

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

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

(17)

(18)

(19)

(20)

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

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

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

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

算法1簇首選取

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

輸出：內部通信簇首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。

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

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

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

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

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

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

(21)

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

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

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

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

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

(22)

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

(23)

(24)

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

Figure 3 Algorithm framework圖3 算法框架

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

4 實驗仿真

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

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

4.1 算法評價過程及指標

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

4.2 仿真實驗結果

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

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

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

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

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

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

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

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

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

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

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

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

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

觀察對照組B，即圖5b和圖5c所示的仿真能耗可以發(fā)現(xiàn)，在2組對照實驗中，在首個節(jié)點死亡之前，DHUCB算法的剩余能量依舊優(yōu)于對比算法的。相對于仿真網(wǎng)絡2，由于仿真網(wǎng)絡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)絡中剩余能量-通信輪次圖

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

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

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

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

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

由圖6可知，本文算法的簇首能耗隨節(jié)點到匯聚節(jié)點距離的增長速率在3個算法中是最小的。這說明在一定程度上，本文算法相較于對比算法減輕了網(wǎng)絡中不同區(qū)域簇首的能耗差異，部分解決了均勻網(wǎng)絡的“熱點”問題。此外，將簇首能耗與單個非簇首節(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為時間復雜度，Si為空間復雜度；L為軟件的運行時間，Ei為算法中的其他能耗。在本文的評估中，不考慮機器性能的差異，可以將L設置為1，其他能耗包括DHUCB算法額外計算的內外簇首間的距離，計算出如表4所示的能耗數(shù)據(jù)。

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

4.3 實驗小結

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

5 結束語

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

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