鄢麗娟，張彥虎

(廣東松山職業(yè)技術(shù)學院計算機系，廣東 韶關(guān) 512126)

0 引 言

無線傳感器網(wǎng)絡是由數(shù)量龐大的傳感器節(jié)點以自組織、多跳的工作模式組建的網(wǎng)絡[1-2]。隨著“互聯(lián)網(wǎng)+”、物聯(lián)網(wǎng)和智慧城市的引入,無線傳感器網(wǎng)絡技術(shù)在各個領(lǐng)域已得到了充分的肯定和應用[3]?，F(xiàn)如今，無線傳感器網(wǎng)絡已廣泛應用于許多生活領(lǐng)域中，基本涵蓋了國防軍事、預報救災、環(huán)境監(jiān)測、醫(yī)療監(jiān)護、智能家居等多個領(lǐng)域[4-5]，具有非常廣泛而巨大的市場應用前景。無線傳感器網(wǎng)絡中存在的節(jié)點能量受限問題，對網(wǎng)絡性能和網(wǎng)絡壽命產(chǎn)生嚴重影響。設計穩(wěn)定且低能耗的無線路由協(xié)議對保障網(wǎng)絡通信、延長網(wǎng)絡壽命具有重要的意義[6-7]。

文獻[8]提出了一種基于最優(yōu)傳輸距離和K-means聚類的WSN分簇算法；文獻[9]提出了節(jié)點路由選擇與基站全局調(diào)節(jié)相結(jié)合的雙層規(guī)劃的跨層能耗均衡路由協(xié)議；文獻[10]提出了簇的能耗均衡的概念，但是僅以固定簇為單位，缺少整體網(wǎng)絡概念，限制了其應用；文獻[11]提出了一種綜合考慮單個節(jié)點傳輸能耗和總傳輸能耗的路徑規(guī)劃算法；文獻[12]提出了一種在保證能耗均衡的基礎上基于蟻群算法的無線傳感器路由改進算法。

本文從能量優(yōu)化的角度，針對LEACH協(xié)議分簇算法成簇機制導致的能耗不均衡問題，提出基于平均剩余能量的分簇路由算法LEACH-BAE。在簇頭選舉機制上，引入全域網(wǎng)絡節(jié)點平均剩余能量的概念[13]，以平均剩余能量為主要參數(shù)，選舉合適的簇頭，提出由基站在對全域節(jié)點情況了解的基礎上分析得出最佳簇頭位置及簇頭數(shù)量，可均衡網(wǎng)絡能耗，延長網(wǎng)絡的生存周期。

1 LEACH算法

LEACH(低功耗自適應聚簇分層協(xié)議)[14]是一種經(jīng)典、成熟的層次路由協(xié)議算法，此算法最早由Heinzelman提出[15]。其基本思想是采用輪流當簇頭的方式，每一輪主要的工作就是成簇和穩(wěn)定通信[16-17]。該算法的核心思路是減少節(jié)點與基站的直接通信的能耗，通過分層按簇進行數(shù)據(jù)融合提高數(shù)據(jù)處理效率，降低網(wǎng)絡能量損耗，延長整個網(wǎng)絡的生存時間[18]。

1)成簇。

在成簇階段，算法要實現(xiàn)2個功能：簇頭選舉和成員加入。其中簇頭選舉是整個算法的核心關(guān)鍵。在成簇過程中，每個節(jié)點首先按照預期的網(wǎng)絡簇頭百分比和其擔任過簇頭的次數(shù)，綜合設置出一個閾值T(n)，然后各個節(jié)點隨機產(chǎn)生一個[0，1]范圍之間的數(shù)，并與T(n)相比較，若某節(jié)點產(chǎn)生的隨機數(shù)小于預設的閾值T(n)，則該節(jié)點當選簇頭并同時向網(wǎng)內(nèi)節(jié)點廣播自己成為簇頭的消息[19-20]，閾值T(n)計算公式如下：

(1)

其中，p為預期的簇頭百分比(簇頭節(jié)點占所有節(jié)點的比例值)，r為當前輪數(shù)，G表示第r輪之前從沒有當選過簇頭的節(jié)點集合，假如某節(jié)點在此輪(r輪)前已多次擔任了簇頭工作，則將T(n)重置為0，這樣避免出現(xiàn)一些節(jié)點連續(xù)擔任簇頭的情況，實現(xiàn)了將能耗均衡分攤到每個節(jié)點的目標。

簇頭選舉完成后，其他非簇頭成員節(jié)點根據(jù)接收到的廣播信號強度，選擇信號強度最大的簇頭發(fā)送請求加入簇。

2)穩(wěn)定通信。

穩(wěn)定通信階段主要工作是數(shù)據(jù)傳輸。構(gòu)建成簇之后，簇內(nèi)節(jié)點將各自采集到的數(shù)據(jù)傳給簇頭節(jié)點，然后簇頭節(jié)點進行融合處理接收數(shù)據(jù)，再將融合的數(shù)據(jù)結(jié)果轉(zhuǎn)發(fā)給基站，完成該輪數(shù)據(jù)傳輸任務后，重回成簇階段進入下一輪工作。

LEACH算法有很多優(yōu)點，比如，每個節(jié)點公平競選簇頭，每一輪由不同的節(jié)點擔任簇頭，較好地均衡了網(wǎng)絡負載；簇頭對接收到的各個簇內(nèi)節(jié)點數(shù)據(jù)會進行數(shù)據(jù)融合處理，再轉(zhuǎn)發(fā)給基站，可以極大地精減冗余數(shù)據(jù)。但是，該算法同時存在一定的不足：

①簇頭分布不均勻[21]。LEACH協(xié)議采用隨機方式產(chǎn)生簇頭節(jié)點，可能會導致若干個簇頭距離太近甚至簇頭大面積集中在一個區(qū)域內(nèi)的情況，2個簇頭間隔太近或若干個簇頭集中在一個區(qū)域，會導致普通節(jié)點與簇頭節(jié)點通信的距離增加，從而造成區(qū)域內(nèi)能量消耗增大，簇頭節(jié)點數(shù)量分布不均勻的情況。

②無線傳感器網(wǎng)絡節(jié)點能量消耗不均衡。LEACH協(xié)議強調(diào)，網(wǎng)絡中每個節(jié)點在每一輪中都會輪流做一次簇頭，成功地將能量消耗分散在所有節(jié)點上，有利于整個網(wǎng)絡能量的節(jié)約，但是，這種均衡的做法未考慮到節(jié)點距離基站的遠近對能量消耗的影響。距離基站越遠的地方，節(jié)點因為需要將信息傳輸?shù)礁h的地方，其能量消耗相對距離簇頭或基站較近的節(jié)點而言，耗損也更快，即節(jié)點距離基站的遠近直接影響著其能量消耗的快慢。如果機械地使每個節(jié)點均勻輪流做簇頭，對距離較遠的節(jié)點而言，顯然是不公平的。

2 LEACH-BAE算法

針對上述LEACH協(xié)議的不足，本文提出一種改進的基于平均剩余能量的路由算法LEACH-BAE(Low Energy Adaptive Clustering Hierarchy-Base on Average Energy)。本算法在原LEACH協(xié)議的基礎上做適當?shù)母倪M，使其所產(chǎn)生的簇頭能更均勻地分布在全無線傳感器網(wǎng)絡范圍之內(nèi)，同時，簇頭選舉過程是在基站對全域網(wǎng)絡內(nèi)節(jié)點信息掌握的基礎上產(chǎn)生，簇頭的產(chǎn)生過程是基于全域能量消耗均衡的意圖作為主要指標進行衡量，即每次簇頭的產(chǎn)生要基于均衡全域網(wǎng)絡節(jié)點能量而進行，要避免甚至杜絕出現(xiàn)剩余能量低于全域節(jié)點平均剩余能量的節(jié)點做簇頭，防止因節(jié)點過早死亡而致使全域網(wǎng)絡過早癱瘓或消亡的情況。

為了能確保簇頭算法的正常運行，本文對普通節(jié)點和簇頭節(jié)點的數(shù)據(jù)結(jié)構(gòu)分別規(guī)劃如表1、表2所示。

表1 普通節(jié)點數(shù)據(jù)結(jié)構(gòu)

表2 簇頭節(jié)點數(shù)據(jù)結(jié)構(gòu)

為了能實現(xiàn)第一次網(wǎng)絡通信，需要在全域網(wǎng)絡范圍內(nèi)產(chǎn)生部分簇頭，使其收集全域網(wǎng)絡節(jié)點信息、傳輸控制指令及傳輸部分數(shù)據(jù)，此時，簇頭的產(chǎn)生采用傳統(tǒng)LEACH協(xié)議簇頭的產(chǎn)生方式，各節(jié)點產(chǎn)生一個隨機數(shù)，當隨機數(shù)小于T(n)時，該節(jié)點為簇頭，否則為普通節(jié)點。初始簇頭節(jié)點產(chǎn)生之后，向全域廣播自己成為簇頭，附近節(jié)點加入該簇，組成網(wǎng)絡。將全域網(wǎng)絡中所有節(jié)點的基本信息收集后發(fā)給基站，其中包括各節(jié)點的坐標、剩余能量等，基站獲取到全域節(jié)點信息之后，運行分析程序，根據(jù)全域網(wǎng)絡節(jié)點的實際分布情況，進行簇頭的分派。

2.1 最優(yōu)簇頭數(shù)量的確認

假定全域網(wǎng)絡的長和寬分別是wd、ht，一跳的距離為j1，且假定3個變量的單位統(tǒng)一，如圖1所示。為了避免簇頭扎堆產(chǎn)生，令新簇頭不會產(chǎn)生在所有已產(chǎn)生簇頭的j1范圍之內(nèi)。

圖1 節(jié)點一跳間距示意圖

如果在陰影區(qū)域內(nèi)出現(xiàn)簇頭A，則在以A為原點，j1為半徑的區(qū)域內(nèi)，不會產(chǎn)生第二個簇頭節(jié)點，其他的簇頭必定產(chǎn)生在該區(qū)域以外的位置，據(jù)此，只需求得完全覆蓋整個網(wǎng)絡區(qū)域需要多少個圓形陰影圖形就可獲得最優(yōu)簇頭數(shù)量，即可以通過公式(2)計算求得最優(yōu)簇頭數(shù)量：

(2)

對式(2)結(jié)果向下取整后得到的CNum即為最優(yōu)簇頭的數(shù)量，wd、ht分別為網(wǎng)絡區(qū)域的長和寬，j1為一跳的距離。

2.2 平均剩余能量

為了確保所選舉的簇頭節(jié)點的剩余能量大于全域節(jié)點的平均剩余能量EAvall，需要先求出EAvall的值，其運算過程為：

(3)

其中,ECi為節(jié)點Si的剩余能量，n為全網(wǎng)無線傳感器節(jié)點的數(shù)量。

2.3 簇頭選舉

2.3.1 首輪簇頭選舉

采用LEACH算法原理選舉首輪簇頭，初始簇頭將全域網(wǎng)絡節(jié)點的基本信息傳輸給基站，為基站進一步分析網(wǎng)絡節(jié)點的實際情況做準備，為全域網(wǎng)絡節(jié)點與基站建立一條通道和橋梁。

2.3.2 LEACH-BAE協(xié)議簇頭選舉

LEACH-BAE協(xié)議中除初始簇頭節(jié)點之外，其余的簇頭都是由基站根據(jù)全域網(wǎng)絡節(jié)點的實際情況進行分派的，在選擇簇頭時，使用的主要參數(shù)為全域網(wǎng)絡節(jié)點的剩余能量均值EAvall。

簇頭選舉實現(xiàn)的主要偽碼見算法1。

算法1簇頭選舉算法。

for k從1執(zhí)行到n

獲取隨機數(shù)i;

if(節(jié)點S(i)的剩余能量>平均剩余能量EAvall)

if(簇頭數(shù)量為0)

該節(jié)點S(i)為簇頭節(jié)點

else

計算該節(jié)點到第一個簇頭節(jié)點C(1)的距離mdis;

for c從簇頭1執(zhí)行到目前簇頭的個數(shù)

計算節(jié)點S(i)到簇頭C(c)的距離temp_dis;

if(temp_dis

則mdis的值設置為temp_dis;

end

end

if(mdis的值大于系統(tǒng)設定的dis)

該節(jié)點S(i)為簇頭節(jié)點;

end

end

k++;

end

if(簇頭數(shù)量為0>CNum)

break;

end

end

在算法1中，n為全區(qū)域內(nèi)節(jié)點的數(shù)量，S(i)為普通節(jié)點，C(c)為簇頭節(jié)點，CNum為最優(yōu)簇頭數(shù)量，EAvall為全域節(jié)點平均剩余能量。此算法循環(huán)n次，即全域網(wǎng)絡內(nèi)所有節(jié)點都有機會被抽取到作為備選簇頭節(jié)點，在算法中，依次做了簇頭數(shù)量是否達到最優(yōu)簇頭、剩余能量是否達到要求、與已產(chǎn)生的簇頭節(jié)點的間距是否符合要求等。

2.4 節(jié)點成簇階段

若各普通節(jié)點在接收到初始簇頭信息進行對比之后，發(fā)現(xiàn)自己不是簇頭節(jié)點，則獲取基站分配給自己的簇頭節(jié)點號C(i)、需要調(diào)整的發(fā)送頻率等信息，并在LEACH-BAE協(xié)議簇頭節(jié)點產(chǎn)生后，向周圍簇頭節(jié)點發(fā)出加入請求，確保該節(jié)點的簇頭能接收到加入簇頭C(i)的信息。

若節(jié)點對比后發(fā)現(xiàn)自己是簇頭節(jié)點，則接收基站發(fā)送的含有簇成員等信息的數(shù)據(jù)包，并設置自己為簇頭節(jié)點。

簇頭節(jié)點接收到普通節(jié)點的加入請求之后，將該節(jié)點標志為已加入，同時依據(jù)已接收的基站數(shù)據(jù)包中的簇成員信息，檢查屬于本簇的節(jié)點是否已全部加入，如果是，為所有簇成員分配時間片區(qū)并發(fā)送給簇成員，然后關(guān)閉組網(wǎng)，并向所有成員節(jié)點發(fā)送組網(wǎng)成功并退出組網(wǎng)的通知，進入數(shù)據(jù)傳輸環(huán)節(jié)。

2.5 數(shù)據(jù)傳輸階段

各普通節(jié)點在指定的時間片區(qū)發(fā)送收集的數(shù)據(jù)及自己的剩余能量等信息；簇頭節(jié)點接收數(shù)據(jù)并對數(shù)據(jù)融合處理后，將所收集的簇內(nèi)節(jié)點數(shù)據(jù)信息及各節(jié)點的能量剩余情況發(fā)送給基站；基站定期定時對全域的實際情況進行分析，計算出全域平均剩余能量，并分析實際情況指定簇頭及其簇成員，然后將信息發(fā)送給當前簇頭節(jié)點并要求重新組網(wǎng)；簇頭節(jié)點接收到重新組網(wǎng)的指令及新簇頭節(jié)點等信息后，向全域廣播相關(guān)信息，并進入下一輪的組網(wǎng)重構(gòu)。

3 仿真實驗及分析

本文在MATLAB R2016模擬仿真平臺上，基于算法在M×M區(qū)域的平面上進行模擬實驗，設M的值為100 m。使用模擬軟件在該區(qū)域內(nèi)隨機產(chǎn)生100個節(jié)點，部分關(guān)鍵參數(shù)設置為：節(jié)點的初始能量為0.02 J，數(shù)據(jù)包大小為4000 bit，控制包為32 bit，基站位于平面的中心位置；對LEACH-BAE協(xié)議和LEACH協(xié)議分別作了100次的實驗，對該100次的實驗數(shù)據(jù)進行對比分析。

1)簇頭數(shù)量。

通過100次實驗，每次運行1000輪，隨機抽取，得到250輪和1000輪以內(nèi)的2張簇頭數(shù)量對比圖，如圖2和圖3所示，通過圖形分析能直觀地得出：LEACH協(xié)議產(chǎn)生的簇頭數(shù)量波動幅度比較大，到后期會頻繁出現(xiàn)簇頭為1的情況；LEACH-BAE協(xié)議生成的簇頭相對比較穩(wěn)定，前期因使用隨機產(chǎn)生簇頭法生成簇頭，產(chǎn)生的簇頭數(shù)量比較多，后期系統(tǒng)會自動平衡各種因素，將簇頭的數(shù)量控制在合適的范圍之內(nèi)，同時，隨著存活節(jié)點的減少，簇頭節(jié)點的數(shù)量也會很明顯有規(guī)律地進行適當調(diào)整，達到更好節(jié)約能量的目的。其中LEACH方差為3.94，LEACH-BAE協(xié)議方差為2.36。在選舉的簇頭數(shù)量方面，LEACH-BAE協(xié)議的效果要優(yōu)于LEACH協(xié)議的算法。

圖2 250輪簇頭數(shù)量動態(tài)對比圖

圖3 1000輪簇頭數(shù)量動態(tài)對比圖

2)成簇情況。

原LEACH協(xié)議簇頭布局與LEACH-BAE協(xié)議簇頭布局對比：

在原LEACH協(xié)議中，因為在簇頭產(chǎn)生過程中，對未做過簇頭的節(jié)點采用隨機方式產(chǎn)生，可能會出現(xiàn)若干個簇頭節(jié)點集中在一起扎堆的情況，如圖4所示。因為簇頭節(jié)點要承擔與基站的通信，其能量消耗相對而言要比普通節(jié)點高很多，在圖4所示的2個圓形框選區(qū)域里產(chǎn)生分布的幾個簇頭距離太近，而個別節(jié)點的通信距離又太遠，造成全域節(jié)點能量消耗過快，有進一步提升改進的空間。

圖4 LEACH協(xié)議簇頭產(chǎn)生過于集中現(xiàn)象

在LEACH-BAE協(xié)議算法中，在簇頭產(chǎn)生的過程中加入了一個限定條件，即符合做簇頭條件且被系統(tǒng)選中擬產(chǎn)生的新簇頭，需要跟已經(jīng)確定為新一輪簇頭的所有節(jié)點做數(shù)據(jù)分析，如果該節(jié)點與已確定的簇頭列表中的任何一個簇頭的距離小于設定值dic，則該節(jié)點不能做簇頭。在這種條件下，系統(tǒng)中產(chǎn)生的所有簇頭節(jié)點，一定不會有若干個節(jié)點扎堆出現(xiàn)的情況，在一定程度上避免了過多的能量消耗，降低了全域網(wǎng)絡節(jié)點的能量耗損，增加了節(jié)點的存活時間。修正后的簇頭布局如圖5所示。

圖5 LEACH-BAE協(xié)議簇頭分布優(yōu)化效果圖

3)剩余能量。

本文對LEACH和LEACH-BAE協(xié)議所做的100次1000輪的測試中，將能被100整除輪次的剩余能量進行記錄，然后求100次的平均值，對比發(fā)現(xiàn)如圖6：LEACH-BAE協(xié)議相比LEACH協(xié)議，LEACH-BAE協(xié)議全域平均剩余能量要大于LEACH，其中前600輪次，LEACH-BAE協(xié)議的領(lǐng)先程度更多，600輪次之后，兩者的剩余能量差距逐漸減少，都趨向于0。

圖6 平均剩余能量對比折線圖

4)基站接收數(shù)據(jù)對比。

基站的接收數(shù)據(jù)對比如圖7所示，在前420輪，LEACH-BAE與LEACH發(fā)送的數(shù)據(jù)量基本相同，420輪之后，LEACH-BAE向基站發(fā)送的數(shù)據(jù)量保持高速增長的勢態(tài)，而LEACH算法的增長速度明顯放緩，說明改進算法LEACH-BAE的網(wǎng)絡吞吐量更大，其數(shù)據(jù)通信能力更強。

圖7 基站接收數(shù)據(jù)對比

4 結(jié)束語

LEACH-BAE算法對LEACH協(xié)議的簇頭選舉方式和簇間數(shù)據(jù)到達基站的傳輸方式實施了一定的改進，引入了全域網(wǎng)絡節(jié)點平均剩余能量的概念，并且在簇頭選舉的過程中，只有大于平均剩余能量，才有機會成為簇頭，雖然在算法中未考慮每個節(jié)點的公平性，但從整體而言，它能更好、更有效地將重負荷的簇頭節(jié)點的工作均衡地布置給更合適的節(jié)點，使整個網(wǎng)絡能量的耗散更加均衡，盡可能地使更多的節(jié)點生存更長的時間。通過仿真實驗對比，改進的LEACH-BAE算法在均衡全無線傳感器網(wǎng)絡節(jié)點能量消耗及延長網(wǎng)絡生存周期等方面具有較明顯的優(yōu)勢。