基于改進BIRCH的雙簇首WSN能耗優化研究*

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

2 系統模型

2.1 網絡模型

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

假設1所有節點的初始狀態相同，即具有相同電池容量，傳輸單位數據至單位距離所消耗的能量相同，計算單位數據的能耗相同；

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

假設3系統中僅有一個匯聚節點，該節點的能量不做限制；

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

2.2 能量消耗模型

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

Figure 1 Communication model圖1 通信模型

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

(1)

若通信半徑r

Table 1 Experimental simulation parameters表1 實驗仿真參數

由圖1所示模型可知，數據發送端發送kbit的數據至d距離的能耗為：

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

(2)

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

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

3 算法實現

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

3.1 簇的劃分

3.1.1 聚類特征

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

(3)

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

(4)

為各節點屬性的線性和，標量

(5)

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

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

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

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

(6)

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

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

質心為:

(7)

半徑為:

(8)

直徑為:

(9)

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

(10)

3.1.2 聚類特征樹

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

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

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

(11)

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

(12)

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

(13)

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

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

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

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

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

(14)

3.1.3 CF樹的構造

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

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

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

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

(15)

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

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

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

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

①若h′

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

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

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

②否則轉步驟2。

(2)若h′

3.1.4 簇的選取

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

H′=log2(N+1)

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

3.2 簇首的選取

在簇首選擇階段，本文從每個簇中選擇2個簇首——一個是內部通信簇首，用于聚合簇內非簇首節點所采集的數據并進行數據融合；另一個是外部通信簇首，用于將內部數據通過多跳網絡傳輸到匯聚節點，以及傳輸多跳網絡中其他子簇的數據。

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

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

(17)

(18)

(19)

(20)

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

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

其次，對于外部通信簇首，同樣需要有較高的剩余能量。由于需要進行遠距離傳輸，其能量消耗更甚于簇外通信簇首，因此賦予其權重為Q1=0.65。外部通信節點將數據傳輸到匯聚節點，因此，該節點與匯聚節點的距離占有較大權重，賦予Q2=0.35。而它與簇內其他節點的距離不會對外部通信能量消耗造成大的影響，相對賦予較小的權值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。

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

3.3 數據傳輸

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

數據傳輸分為2個階段：簇內數據傳輸階段和簇間數據傳輸階段。

簇內數據傳輸的過程中，在每一個TDMA周期內，子簇內節點收集環境中的數據，并在屬于它的時間片內將數據傳輸給內部通信簇首。內部通信簇首將收集到的信息進行融合，并將融合數據發送給外部通信簇首。所有節點都完成一輪傳輸后，簇內數據傳輸階段完成。

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

(21)

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

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

①候選節點與匯聚節點的距離小于該節點與匯聚節點的距離；

②候選節點與該節點的距離小于d0。

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

(22)

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

(23)

(24)

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

Figure 3 Algorithm framework圖3 算法框架

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

4 實驗仿真

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

本文的仿真參數如表1所示。

4.1 算法評價過程及指標

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

4.2 仿真實驗結果

4.2.1 存活節點數隨通信輪次的變化

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

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

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

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

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

如表2所示，對照組A中的2個對照項的仿真結果中，本文所述的DHUCB算法在首個節點死亡和半數節點死亡2個指標上的表現均優于對比算法。說明在不同大小的節點部署區域內，本文算法均達到了延長網絡生命周期的目的。

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

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

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

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

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

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

觀察對照組B，即圖5b和圖5c所示的仿真能耗可以發現，在2組對照實驗中，在首個節點死亡之前，DHUCB算法的剩余能量依舊優于對比算法的。相對于仿真網絡2，由于仿真網絡3的節點數量增加，系統通信能耗隨之增加，3個算法的能耗水平均有所提高，但是DHUCB相對對比算法在能耗水平表現上依然有不小的優勢。

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

4.2.3 網絡能耗隨傳輸距離的變化

對比算法LEACH-B和OCMR采用的都是均勻分簇的策略，即各個子簇中的最大節點數約束是固定的。由于本文算法和對比算法均使用多跳網絡進行數據傳輸和轉發，相對于距匯聚節點較遠的簇首節點來說，距離匯聚節點較近的外部通信簇首承擔額外的數據轉發能耗的概率較大，成為所謂的“熱點”。節點自身能耗加大，造成網絡整體能耗的不均衡。本文采用了3.1.2節所述的動態空間閾值策略，使得子簇中的最大節點數和子簇與匯聚節點的距離線性相關，子簇中簇首用于簇內數據傳輸的能量也更趨近于線性相關。

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

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

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

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

4.2.4 算法計算能耗對比

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

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

(24)

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

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

4.3 實驗小結

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

5 結束語

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

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