能量平衡的無線傳感器網(wǎng)絡數(shù)據(jù)采集動態(tài)分簇算法

陳宏濱， 陳 琪

(桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

隨著互聯(lián)網(wǎng)時代的發(fā)展，物聯(lián)網(wǎng)在工業(yè)領域具有廣闊的應用前景[1]。由大量部署在監(jiān)測區(qū)域的傳感器節(jié)點互相通信組成的無線傳感器網(wǎng)絡是物聯(lián)網(wǎng)底層的重要技術(shù)形式。無線傳感器網(wǎng)絡中重要的應用之一是數(shù)據(jù)采集[2]，但是在一些應用場景如軍事基地等，傳感器節(jié)點的能量有限且不便于隨時進行補充，因此在無線傳感器網(wǎng)絡的數(shù)據(jù)采集過程中，能量使用效率是一個需要關(guān)注的問題。

在無線傳感器網(wǎng)絡中，通常節(jié)點數(shù)量較多且有些節(jié)點之間距離很遠，聚類傳感器節(jié)點是延長傳感器網(wǎng)絡壽命的重要方法之一[3]。聚類包括對傳感器節(jié)點進行分簇，然后從每個簇中選出一個簇頭，對每個節(jié)點的數(shù)據(jù)進行匯總，再將收集到的數(shù)據(jù)轉(zhuǎn)發(fā)給基站。因此，為了提高網(wǎng)絡的生存時間和剩余能量，分簇算法和簇頭節(jié)點的選擇變得越來越重要。在無線傳感器網(wǎng)絡中數(shù)據(jù)協(xié)議有很多，但基于聚類的分層路由協(xié)議由于提高了可擴展性而受到更多的關(guān)注。LEACH是經(jīng)典的低功耗自適應分簇算法[4]，但是簇頭的選擇僅考慮了概率因素，導致有些能量過低或位置偏遠的節(jié)點擔任簇頭，造成能量消耗不均衡，出現(xiàn)路由空洞[5]。在簇頭選舉方面，梁玉珠[6]設置基于節(jié)點剩余能量的時間退避機制，使得高能量節(jié)點更容易在簇頭選舉階段勝出，提出了由此保存簇頭的數(shù)量來實現(xiàn)全局能耗的均衡。謝雙雙等[7]依據(jù)節(jié)點距離[8]、密度及剩余能量3個方面進行簇頭選擇，解決了由簇頭因素導致的能量消耗不均衡問題。在分簇的有效方式方面，李彬等[9]以sink節(jié)點為原點劃分角幅度相等區(qū)域輔助分簇規(guī)則，但是簇頭的能量消耗會隨著距離的增加而增加。Wei等[10]根據(jù)節(jié)點到sink節(jié)點的距離來確定合適的簇的大小，提出一種分布式聚類算法，啟發(fā)了本研究考慮能量因素來確定合適簇的大小。當簇的規(guī)模較大時，單跳傳輸比多跳傳輸會消耗更多的能量[11]?？紤]到節(jié)點間通信的能量消耗、節(jié)點剩余能量、節(jié)點到sink節(jié)點的距離，Zhang等[12]采用單跳路由和多跳路由相結(jié)合的方式在簇頭之間進行數(shù)據(jù)傳輸，與LEACH算法對比，提高了數(shù)據(jù)傳輸效率與網(wǎng)絡生命周期，但多跳傳輸容易導致數(shù)據(jù)傳輸延遲。無線傳感器網(wǎng)絡中引入移動采集器，可避免簇頭間的多跳傳輸，是一種平衡終端節(jié)點負載，提高數(shù)據(jù)采集效率，延長網(wǎng)絡生存周期的有效方式[13-14]。Zhang等[15]基于節(jié)點密度分簇，使用移動采集器進行簇間數(shù)據(jù)采集，提出了一種分層路由與移動采集器相結(jié)合的算法，在節(jié)約能耗與數(shù)據(jù)采集效率之間有很好的折中效果。Zhao等[16]使用多個簇頭來平衡負載，提出一種分布式負載均衡聚類算法，但是當簇頭節(jié)點過多時，會失去節(jié)點分簇的意義。

本研究針對各簇節(jié)點數(shù)量不同、總剩余能量不同和節(jié)點采集數(shù)據(jù)的速率不同等因素研究基于能量均衡的動態(tài)分簇算法(energy balanced dynamic clustering algorithm，簡稱EBDCA)，主要創(chuàng)新點如下：在簇的初始形成階段，同時考慮節(jié)點的位置與距離因素，以及各簇總能量均衡的問題成簇，根據(jù)能量變化情況，采用動態(tài)分簇的策略調(diào)整分簇情況；在簇內(nèi)數(shù)據(jù)傳輸方式上，彈性考慮節(jié)點間距離與能量因素，并根據(jù)競爭函數(shù)值將節(jié)點數(shù)據(jù)進行分級傳輸，減少了簇內(nèi)通信消耗；在簇頭選舉方面，直接選用簇內(nèi)一級節(jié)點中剩余能量最高的節(jié)點作為簇頭，避免了距離簇中心很遠但剩余能量很大或者距離簇中心很近但剩余能量很小的節(jié)點成為簇頭。 從而維持了數(shù)據(jù)采集過程中網(wǎng)絡能量的動態(tài)平衡，延長了網(wǎng)絡生命周期。

1 系統(tǒng)模型

假設在一個正方形區(qū)域A中，均勻隨機部署n個靜態(tài)傳感器節(jié)點X={x1,x2,…,xn}，sink節(jié)點位于區(qū)域中心。為了方便研究簇間的能量平衡狀態(tài)，作如下假設：

1)各傳感器節(jié)點位置信息設定為已知，且初始能量不一致，數(shù)據(jù)采集速率隨機；

2)節(jié)點一經(jīng)部署不可移動且節(jié)點之間無障礙物；

3)節(jié)點之間的通信鏈路是雙向的、對稱的；

4)移動采集器搭載了太陽能電池，可以隨時進行能量補充。

1.1 網(wǎng)絡模型

采用分層的無線傳感器網(wǎng)絡模型。節(jié)點部署后均為靜止狀態(tài)，由一個移動采集器經(jīng)過各簇頭節(jié)點對簇內(nèi)數(shù)據(jù)進行采集，簇的大小根據(jù)節(jié)點的能量分布差異而有所不同。各級節(jié)點數(shù)量逐級遞減，節(jié)點數(shù)據(jù)逐級上傳，其中三級節(jié)點的數(shù)據(jù)上傳至二級節(jié)點中，二級節(jié)點的數(shù)據(jù)則上傳至一級節(jié)點，一級節(jié)點數(shù)據(jù)上傳至簇頭。傳感器網(wǎng)絡模型如圖1所示。

圖1 傳感器網(wǎng)絡模型

1.2 能耗模型

在傳感器網(wǎng)絡中，數(shù)據(jù)傳輸?shù)耐ㄐ胚^程往往是節(jié)點能耗產(chǎn)生的主要部分。使用與文獻[17]相同的能量模型，假設通信距離為d，根據(jù)發(fā)射機和接收機之間的距離與閾值d0的大小關(guān)系，分別采用自由空間信道(d2的能量耗散)和多路徑衰減信道(d4的能量耗散)，傳感器單元的能耗率取決于傳輸距離和數(shù)據(jù)大小。節(jié)點i發(fā)送m數(shù)據(jù)至距離為d的節(jié)點j的能耗ETX為

(1)

節(jié)點接收m數(shù)據(jù)所需能量消耗為

ERX=mEelec，

(2)

其中：Eelec為發(fā)送/接收1 bit數(shù)據(jù)的能量損耗；εfs為當d≤d0時發(fā)送電路的放大系數(shù)；εamp為當d>d0時發(fā)送電路的放大系數(shù)。

2 EBDCA描述

傳感器網(wǎng)絡中能量的平衡狀態(tài)會影響整個網(wǎng)絡的生命周期。EBDCA的基本思想就是根據(jù)競爭函數(shù)構(gòu)建能量均衡的簇并且根據(jù)能量平衡函數(shù)是否低于閾值來動態(tài)地調(diào)節(jié)分簇，使得網(wǎng)絡內(nèi)節(jié)點能耗動態(tài)的維持一個平衡狀態(tài)。

使用能量比值lb來表示各簇間的能量平衡狀態(tài)值，根據(jù)該比值與閾值l0的比較，判定該網(wǎng)絡是否處于能量平衡狀態(tài)：

(3)

其中：Emax為該網(wǎng)絡中最大總能量簇的能量值；Emin為該網(wǎng)絡中最小總能量簇的能量值。

在簇的構(gòu)建階段，以各簇頭為參考，節(jié)點根據(jù)競爭函數(shù)值選擇加入哪個簇，競爭函數(shù)fij動態(tài)考慮了節(jié)點的剩余能量以及距離因素：

(4)

其中：λ為競爭函數(shù)的權(quán)重因子；eres為節(jié)點的剩余能量；ditoj為該節(jié)點和簇頭之間的歐氏距離。

最佳簇頭個數(shù)kopt的計算式[6]為

(5)

其中：M為網(wǎng)絡覆蓋范圍的半徑；d為簇頭到sink的距離期望。

2.1 能量平衡動態(tài)分簇算法

K-means算法是一種簡單且經(jīng)典的基于距離的聚類算法，其簇頭節(jié)點有較好的形成簇的基礎。但K-means算法的k值不易確定，對于網(wǎng)絡的初始分簇個數(shù)k，參考文獻[18]計算網(wǎng)絡總數(shù)據(jù)量，除以單個節(jié)點最大數(shù)據(jù)承載量vmax，獲得初始分簇個數(shù)k。K-means算法的另一缺點是分簇僅考慮了距離因素，未考慮能量因素對分簇好壞的影響。在成簇階段使用由能量與距離因素構(gòu)成的競爭函數(shù)參與簇的形成，并依據(jù)能量平衡狀態(tài)動態(tài)控制簇的形成過程，以維持網(wǎng)絡的能量平衡狀態(tài)，延長網(wǎng)絡生存周期。設α、β為加入簇節(jié)點數(shù)量參數(shù)，具體算法描述如下：

1) 用K-means算法獲取k個簇頭的位置信息，將它們標記為C={Ch，i|i=1:k}。

2) 計算各簇頭到基站的距離期望，得到最優(yōu)簇頭數(shù)kopt，若k≠kopt，則將kopt的值賦給k, 回到步驟1)；若k=kopt，則簇頭選定成功。

3) 第一批節(jié)點選擇簇頭加入對應的簇：以選定簇頭為參考，著重考慮能量因素，計算普通節(jié)點到各簇頭的競爭函數(shù)f值。假設每個簇應有成員節(jié)點有s=n/k個，各簇頭吸收其競爭函數(shù)的前s/α個節(jié)點作為第一批吸收的簇成員節(jié)點。

4) 計算已形成的各簇的剩余能量，目前總剩余能量最高的簇的總能量記為Emax，其余各簇目前剩余能量記為Eres，Ci，各簇能量與剩余能量最高簇的能量比值記為li=Eres，Ci/Emax。

5) 若li≥l0，則簇頭Ch，i暫停一輪吸收新節(jié)點加入該簇；若liα)個節(jié)點吸收為新的簇成員。

6) 重復步驟4)、5)，直到所有節(jié)點均加入簇。

在算法中驗證k值是否為最佳kopt的計算需要已知簇頭節(jié)點坐標，所以要先進行k值的假設，得到簇頭信息再進行最佳k值的驗證。節(jié)點分為多輪加入相應簇頭成為簇成員。一方面為了便于對簇間能量平衡狀態(tài)進行評估，因此在第一輪使得更多的節(jié)點加入簇，且競爭函數(shù)賦予節(jié)點剩余能量更大的權(quán)重因子。另一方面為了便于動態(tài)調(diào)節(jié)分簇來維持簇間能量平衡，接下來輪次加入的節(jié)點數(shù)量將減到較小的比例，同時為了使得新加入的節(jié)點不會過于偏離簇中心，增加傳輸能耗，將賦予距離因素更大的權(quán)重因子。

首次成簇后，簇的規(guī)模在一定時間內(nèi)不再改變，整個網(wǎng)絡的節(jié)點進入穩(wěn)定工作階段，成員節(jié)點將采集到的數(shù)據(jù)通過多跳的方式發(fā)送至簇頭。但為了平衡整個網(wǎng)絡的能耗，每T0輪檢查一次各簇的能量平衡狀態(tài)，在滿足特定條件，即lb

2.2 簇內(nèi)節(jié)點數(shù)據(jù)分級算法

在進行簇內(nèi)數(shù)據(jù)傳輸時，將簇內(nèi)節(jié)點分為三級，采用單跳和多跳路由相結(jié)合的方式將節(jié)點數(shù)據(jù)上傳至簇頭節(jié)點。 由于單個簇僅有一個簇頭，若簇內(nèi)節(jié)點數(shù)據(jù)全部單跳上傳至簇頭節(jié)點，容易出現(xiàn)數(shù)據(jù)溢出的情況。本算法設置少量的一級節(jié)點作為簇頭的輔助節(jié)點，幫助緩解簇頭節(jié)點的負載壓力。在網(wǎng)絡覆蓋范圍較大時，會有一部分距離簇中心較遠的節(jié)點，在直接發(fā)送數(shù)據(jù)至輔助節(jié)點時會產(chǎn)生較大的能耗，為此，設置了一部分二級節(jié)點作為緩沖帶。而剩余那些剩余能量較低且距離簇中心較遠的節(jié)點則為三級節(jié)點，其數(shù)據(jù)通過多跳傳輸?shù)街链仡^，簇頭節(jié)點直接與移動采集器通信，最終將數(shù)據(jù)發(fā)送至sink節(jié)點。

1) 節(jié)點分級。均衡考慮距離與能量因素，計算競爭函數(shù)f的值。設a、b為節(jié)點比例的參數(shù)，將各簇內(nèi)f值位于前1/a的節(jié)點判定為簇的一級節(jié)點Ci,1；對尚未分級節(jié)點，將f值排在前1/b的節(jié)點判定為簇的二級節(jié)點Ci,2；剩余各簇內(nèi)未進行分級節(jié)點，則被判定為各簇的三級節(jié)點Ci,3。節(jié)點級別由高至低依次為Ch，i、Ci,1、Ci,2、Ci,3。

2) 下一跳節(jié)點的選擇。對于更低一級的各節(jié)點數(shù)據(jù)，均衡考慮能量與距離因素，從三級節(jié)點開始以節(jié)點為標準依次計算至上一級節(jié)點的競爭函數(shù)f值，選擇f值最大的作為下一跳傳輸節(jié)點，一級節(jié)點數(shù)據(jù)上傳至簇頭。

3) 將一級節(jié)點中剩余能量最高的節(jié)點更新為簇頭Ch，i。

由于通信階段的能耗與節(jié)點之間的距離成正比，更高一級的節(jié)點的通信負載更大，需要有更多的能量保證，因此在節(jié)點分級過程中計算節(jié)點的競爭函數(shù)值時，均衡考慮能量與距離因素。簇頭節(jié)點負責簇內(nèi)數(shù)據(jù)與移動采集器的通信，在能耗方面要求較高，各簇中一級節(jié)點的集中性較好，于是將簇頭更新為一級節(jié)點中剩余能量最高的節(jié)點。動態(tài)的環(huán)境導致節(jié)點能量使用效率不同，保持一級節(jié)點和簇頭的剩余能量對該簇節(jié)點的生存狀態(tài)有重要意義，本算法在每輪數(shù)據(jù)采集都會執(zhí)行一次節(jié)點分級算法。應當注意的是，一級節(jié)點的數(shù)量應該控制為較小的比例，因為過多的輔助節(jié)點會使得簇內(nèi)能量均衡但是整個簇的能耗過大。

2.3 算法步驟

在數(shù)據(jù)采集過程中，簇頭為路徑規(guī)劃的參考點，移動采集器根據(jù)最短路徑則與各簇頭節(jié)點進行通信。具體算法步驟如圖2所示。

圖2 算法步驟

由于節(jié)點設定初始能量不一致，為了獲得能量動態(tài)平衡的分簇，在分簇階段采用了“自頂向下”的方式，在節(jié)點分級階段采用“自底向上”的方式?！白皂斚蛳隆奔聪却_定簇頭位置再進行簇的形成。具體過程為先確定簇頭位置，再根據(jù)競爭函數(shù)值進行節(jié)點吸收入簇，通過對能量值的比較結(jié)果動態(tài)調(diào)節(jié)分簇進程，最終形成能量平衡的分簇?！白缘紫蛏稀奔丛诠?jié)點分級階段由低一級節(jié)點向更高一級節(jié)點進行路徑選擇，數(shù)據(jù)最終到達簇頭節(jié)點。移動采集器通過最短路徑[18]的方式遍歷簇頭，直接對簇頭節(jié)點數(shù)據(jù)進行采集并發(fā)送至sink節(jié)點。重新分簇的原則為：分簇成功后，每T0輪計算一次lb，若lb

3 仿真結(jié)果

本仿真在MATLAB R2018a環(huán)境下運行。在仿真實驗中，300個傳感器節(jié)點隨機均勻分布在1 km×1 km范圍內(nèi)，結(jié)果表現(xiàn)了進行2 000輪數(shù)據(jù)采集的性能。各節(jié)點的初始能量為1 J，數(shù)據(jù)生成速率隨機，節(jié)點初始能量不一致，Eelec為50×10-9J/bit，εfs為10×10-12J/bit，單個節(jié)點最大數(shù)據(jù)承載量vmax為8×104bit，α=3，β=10，a=8，b=3/5，T0=50。為了驗證EBOCA在能量平衡方面的優(yōu)越性，將EBDCA與經(jīng)典LEACH、HMDC[18]算法在數(shù)據(jù)量、簇能耗方差、死亡節(jié)點數(shù)、節(jié)點剩余能耗方差與死亡節(jié)點數(shù)乘積幾個方面進行比較。

圖3為節(jié)點采集的總數(shù)據(jù)量隨著采集輪數(shù)的變化。在同樣的初始條件下，EBDCA采集的數(shù)據(jù)量遠多于LEACH算法，略多于HMDC算法。由于EBDCA考慮的是網(wǎng)絡整體能量平衡，其性能優(yōu)勢會隨著采集輪數(shù)的增加而更加明顯。

圖3 節(jié)點采集的總數(shù)據(jù)量對比

圖4為各簇的能耗方差隨著數(shù)據(jù)采集輪數(shù)的變化。簇能耗方差很好地體現(xiàn)了各簇能耗與簇均能耗之間的偏離程度，簇能耗方差越小，表明整個網(wǎng)絡各簇的能量消耗越均衡。顯然EBDCA中簇能耗方差遠遠小于LEACH算法。在數(shù)據(jù)采集初始階段，EBDCA處于整個網(wǎng)絡能量的平衡調(diào)整階段，因此能耗方差略大與HMDC算法，但隨著數(shù)據(jù)采集輪數(shù)增加，整個網(wǎng)絡能量平衡的狀態(tài)趨于穩(wěn)定，EBDCA的簇能耗方差在絕大多數(shù)輪次都處于優(yōu)勢，浮動幅度相對穩(wěn)定，且遠小于HMDC與LEACH算法。

圖4 簇能耗方差對比

圖5為累計死亡節(jié)點數(shù)隨數(shù)據(jù)采集輪數(shù)的變化。LEACH、HMDC、EBDCA的第一個死亡節(jié)點分別出現(xiàn)在第100、110、400輪左右。而且，在數(shù)據(jù)采集進行到2000輪時，EBDCA的死亡節(jié)點數(shù)僅為LEACH算法的12.1%，HMDC算法的59.3%。由此可看出，EBDCA有效地延長了無線傳感器網(wǎng)絡的生命周期。

圖5 死亡節(jié)點數(shù)對比

圖6為節(jié)點剩余能量方差與死亡節(jié)點數(shù)乘積隨著數(shù)據(jù)采集輪數(shù)的對比。節(jié)點剩余能量方差很好地體現(xiàn)了無線傳感器網(wǎng)絡中各節(jié)點的能量狀態(tài)，節(jié)點剩余能量方差越小，各簇內(nèi)的能量平衡狀態(tài)越好。在一定的采集輪數(shù)下，死亡節(jié)點越少，整個網(wǎng)絡的能量平衡狀態(tài)越好。LEACH節(jié)點由于前期死亡節(jié)點數(shù)量較大，后期死亡節(jié)點數(shù)量會很小，在1 750輪后，剩余能量方差與死亡節(jié)點的乘積出現(xiàn)明顯下降趨勢。EBDCA的節(jié)點剩余能量方差與死亡節(jié)點乘積的值總是低于LEACH與HMDC算法。隨著采集輪數(shù)的增加，EBDCA的性能優(yōu)勢更加明顯。

綜上所述，EBDCA在保證一定數(shù)據(jù)采集量的前提下，很好地均衡了整個網(wǎng)絡的能量消耗，使得無線傳感器網(wǎng)絡的生命周期得到延長。

圖6 節(jié)點剩余能量方差與死亡節(jié)點數(shù)乘積對比

4 結(jié)束語

提出了一種基于能量平衡的傳感器網(wǎng)絡數(shù)據(jù)采集動態(tài)分簇算法，以能量為參考構(gòu)建能量平衡的分簇，并定期檢查平衡狀態(tài)，動態(tài)調(diào)整分簇。在簇內(nèi)節(jié)點分級進行數(shù)據(jù)傳輸時，同時考慮節(jié)點間距離與能量因素進行分級，使得簇內(nèi)節(jié)點能量消耗也處于一個更加均衡的狀態(tài)。仿真結(jié)果表明，與LEACH、HMDC算法相比，提出的EBDCA在保證一定的數(shù)據(jù)采集量前提下，簇間能耗更加均衡，存活節(jié)點的剩余能量分布更加均衡，網(wǎng)絡生命周期得到延長，且隨著數(shù)據(jù)采集輪數(shù)的增加，EBDCA的性能優(yōu)勢更加明顯。