無線傳感器網(wǎng)絡中基于負載均衡的分布式定向分簇算法

簇是無線傳感器網(wǎng)絡（無線傳感器網(wǎng)絡）算法研究的主要方向之一。與平面路由算法相比，分簇算法具有更好的擴展性和適應性，適合于無線傳感器網(wǎng)絡的應用特點。基于簇中節(jié)點的基本思想，將網(wǎng)絡劃分為幾個邏輯區(qū)域，這些區(qū)域稱為“簇”。每個簇通常由一個簇頭節(jié)點（clert）和幾個集群中的成員節(jié)點（clert）組成。集群中所有成員節(jié)點僅與簇中節(jié)點溝通。集群節(jié)點負責收集來自簇中節(jié)點的數(shù)據(jù)，并通過數(shù)據(jù)整合和數(shù)據(jù)壓縮來傳輸數(shù)據(jù)。本文提出一種基于負載均衡的分布式定向分簇算法(distributedanddirectedclusteringalgorithm,DDC).該算法有效解決了在分簇條件下網(wǎng)絡中節(jié)點負載不均衡的問題,并最大程度地延長了網(wǎng)絡的生命周期.DDC算法的核心思想是利用文獻的分簇思想,基于節(jié)點的當前能量水平對網(wǎng)絡進行分割,以獲得適當?shù)木W(wǎng)絡節(jié)點分區(qū),并在分區(qū)中基于節(jié)點負載能力選取簇頭,從而達到網(wǎng)絡中各節(jié)點能量均衡消耗的目的.為此,DDC算法引入了兩個重要參量:節(jié)點能量預評估因子和節(jié)點負載能力預評估因子.這兩個參量用來衡量節(jié)點的當前能量水平及節(jié)點在某一輪中的負載能力水平,并基于分區(qū)的信息預估計實現(xiàn),這保證了DDC算法的分布式特性.由于在確定節(jié)點負載能力時考慮了其發(fā)送數(shù)據(jù)包到Sink節(jié)點的能量消耗,這使得分區(qū)所選取的簇頭呈現(xiàn)向Sink節(jié)點靠攏的特征,特別是在網(wǎng)絡中節(jié)點能量一致的情況更加明顯.因此,我們稱DDC算法是一種向Sink節(jié)點靠攏的定向分簇算法.1基于heed的分布式能量成簇算法在無線傳感器網(wǎng)絡中,LEACH是最早提出的分簇路由協(xié)議之一.它的基本思想是通過等概率的隨機循環(huán)選擇簇頭,將整個網(wǎng)絡負載平均分配到每個傳感器節(jié)點中,從而達到降低網(wǎng)絡能量消耗、延長網(wǎng)絡生命周期的目的.它的成簇思想對后來發(fā)展出的很多分簇路由協(xié)議影響深遠.文獻提出的TEEN采用與LEACH類似的成簇算法,只是在數(shù)據(jù)傳輸階段使用不同的策略,即將數(shù)據(jù)傳輸分為主動型和響應型兩類,并通過在協(xié)議中設置硬、軟兩個閾值,以減少發(fā)送數(shù)據(jù)的次數(shù),從而延長網(wǎng)絡生命.文獻提出的HEED是一種完全分布式成簇算法,它通過節(jié)點間交互動態(tài)產(chǎn)生簇頭,并在簇頭選取過程中考慮了節(jié)點的剩余能量,但算法的控制開銷比較大.文獻提出的DCHS在成簇過程中也考慮了能量因素,利用節(jié)點的當前能量和節(jié)點的初始能量的比例來影響閾值,從而使能量比例消耗低的節(jié)點優(yōu)先當選簇頭,但是,仍然沒有解決網(wǎng)絡負載的均衡性.文獻借鑒了LEACH的分簇思想,提出了PEGASIS算法,從嚴格意義上來講,它并不是真正的分簇算法,它的簇就是一條基于地理位置的鏈.文獻是一種較典型的集中式分簇算法,它利用CBR(case-basedreasoning)技術(shù)在基站完成分簇,產(chǎn)生適當?shù)拇財?shù),并在每輪結(jié)束時根據(jù)簇的相似度來決定是否需要重組,從而節(jié)省每輪重新成簇的開銷.以上算法雖然都能較好地符合無線傳感器網(wǎng)絡路由協(xié)議的設計要求和特點,但這些算法對網(wǎng)絡初始能量的異構(gòu)性和節(jié)點負載的均衡性考慮不夠,在實際應用中存在一定的局限性.文獻提出的SEP協(xié)議雖然考慮了網(wǎng)絡節(jié)點初始能量可能不一致問題,但該算法僅考慮網(wǎng)絡中存在兩種初始能量的問題,因而仍然無法解決實際網(wǎng)絡中節(jié)點初始能量分布的隨機性.文獻基于SEP協(xié)議的設計思想針對一般性的多級異構(gòu)網(wǎng)絡提出了一種分布式能量有效成簇算法,但算法對網(wǎng)絡節(jié)點的平均能量的估計比較粗糙,而且處理多級異構(gòu)的算法相對復雜.2基于負載平衡的分布式向量分布模式算法2.1節(jié)點能耗模型假定在M×M的區(qū)域隨機分布了N個傳感器節(jié)點,如圖1所示.并給出如下假設條件:1)網(wǎng)絡中節(jié)點一旦部署,節(jié)點的地理位置便可確定(可通過節(jié)點定位技術(shù)或GPS實現(xiàn));2)網(wǎng)絡中各節(jié)點的發(fā)送功率級別可調(diào);3)網(wǎng)絡中各節(jié)點的初始能量相同或不同,節(jié)點可獲取自身的當前能量.論文采用文獻的能量模型,節(jié)點能耗包括3部分:發(fā)送數(shù)據(jù)能耗ETx、接收數(shù)據(jù)能耗ERx、數(shù)據(jù)融合能耗EDA.其能量計算公式如式(1)所示.{EΤx(l,d)={lEelec+lξfsd2,d<dthresh,lEelec+lξmpd4,d>dthresh,ERx(l,d)=lEelec?EDA(l)=lEDA?(1)其中,l是節(jié)點發(fā)送或接收數(shù)據(jù)的比特數(shù);Eelec是發(fā)送電路和接收電路消耗的能量,在這個模型里面兩者相等;EDA是簇頭進行數(shù)據(jù)融合時消耗的能量;ξmp和ξfs是信號放大器的放大倍數(shù);dthresh為距離閾值.2.2第r輪負載能力評估在分簇算法中,網(wǎng)絡中各節(jié)點的負載能力,是有效控制網(wǎng)絡負載均衡的重要依據(jù).在DDC算法中,為了有效評價節(jié)點在每一輪中的負載能力,我們提出了節(jié)點的負載能力預評估因子的概念.定義1.節(jié)點負載能力預評估因子:設在第r輪,具有N個節(jié)點的無線傳感器網(wǎng)絡被分割成k個區(qū)域,對任意分區(qū)t(1≤t≤k)的集合T(t,r)中有C(t,r)個節(jié)點.則對網(wǎng)絡中任意節(jié)點i(i∈T(t,r))在第r輪的負載評估因子為lbf(i,r)=(1-Epc(i,r)E(i,r)),(2)其中Epc(i,r)是假設節(jié)點i在第r輪的分區(qū)t中擔任簇首時預估能耗.其能耗主要包括接收分區(qū)中各成員節(jié)點數(shù)據(jù)所消耗的能量、根據(jù)相關性進行數(shù)據(jù)融合所消耗的能量以及將數(shù)據(jù)傳送到Sink節(jié)點所消耗的能量.這個預估能耗可根據(jù)式(1)計算可得.式(2)表明,節(jié)點的當前能量越大,擬擔任簇首的預估能耗越少,則其負載能力預評估因子值就越大,相應的該節(jié)點負載能力就越強.2.3節(jié)點初始量水平在DDC算法中,為了實現(xiàn)對網(wǎng)絡中各節(jié)點能量水平的評價,我們提出了一種局部的基于分區(qū)的節(jié)點能量預評估因子來衡量網(wǎng)絡中各節(jié)點的能量水平.下面給出其定義:定義2.節(jié)點能量預評估因子.設在第r-1輪,任意節(jié)點i的初始能量為E0(i,r-1),具有N個節(jié)點的無線傳感器網(wǎng)絡被分割成k個區(qū)域,對任意分區(qū)t(1≤t≤k)的集合T(t,r-1)中有C(t,r-1)個節(jié)點.則對網(wǎng)絡中任意節(jié)點i(i∈T(t,r-1))在第r輪的能量預評估因子為:ef(i,r)={E0(i,r)1ΝΝ∑i=1E0(i,r),r=1；E0(i,r-1)-Ep(i,r-1)1C(t,r-1)∑j∈Τ(t,r-1)(E0(i,r-1)-Ep(i,r-1)),r>1；(3)其中,Ep(i,r-1)為節(jié)點i在第r輪所消耗的預估能量,根據(jù)式(1)可得.式(3)表明,當r=1時(首輪),節(jié)點i的初始能量因子ef(i,r)是節(jié)點i的初始能量與網(wǎng)絡平均能量1ΝΝ∑i=1E0(i,r)的比值,在網(wǎng)絡初始能量不同的情況下,ef(i,r)的值越大,則表示節(jié)點的初始量水平越高;而當網(wǎng)絡初始能量相同時,ef(i,r)的值為1,表明網(wǎng)絡中各節(jié)點的能量水平相同.當r>1時,節(jié)點i的能量預評估因子ef(i,r)的計算不再依賴于網(wǎng)絡平均能量,而是通過對節(jié)點i在前一輪(即第r-1輪)所屬分區(qū)的平均能量1C(t,r-1)∑j∈Τ(t,r-1)(E0(i,r-1)-Ep(i,r-1))來計算.顯然,ef(i,r)值越大,表明節(jié)點在本分區(qū)的能量水平越高.這種僅僅利用前一輪的分區(qū)信息來獲取下一輪節(jié)點的能量預評估因子,可以有效保證DDC算法的分布式特性.2.4分散算法2.4.1ddosc算法中的最優(yōu)簇頭理論在DDC算法中,我們利用文獻的分簇思想對網(wǎng)絡中的節(jié)點進行分割,即根據(jù)式(4)給定的閾值進行網(wǎng)絡分割.Τ(n)={Ρ1-Ρ[rmod(1/Ρ)],n∈G,0,其他,(4)其中P是所有節(jié)點中簇頭所占的百分比(即節(jié)點當選簇頭的概率),r是當前的輪數(shù),G是最近1/P輪中還未當選過簇頭的節(jié)點的集合.未成為簇頭的節(jié)點根據(jù)接收到廣播信號的強弱來決定加入哪個簇頭節(jié)點,實現(xiàn)對網(wǎng)絡的預分簇,從而達到對網(wǎng)絡節(jié)點進行區(qū)域分割的目的.但在分割的基礎上應充分考慮網(wǎng)絡的能量均衡性,即在分割的各區(qū)域內(nèi)盡可能包含高能量節(jié)點,從而使得各區(qū)域的能量消耗均衡.根據(jù)文獻中最優(yōu)簇頭數(shù)理論,我們設在M×M的平面內(nèi)均勻分布N個傳感器節(jié)點,則網(wǎng)絡的最優(yōu)簇頭數(shù)為kopt=√Ν√2π√ξfsξmpΜd2toBS.(5)因此,在等概率的情況下,網(wǎng)絡中各節(jié)點成為簇頭的最優(yōu)概率為:Ρopt=koptΝ.(6)考慮到網(wǎng)絡能量消耗的均衡性,應盡可能增加當前能量水平高的節(jié)點出任簇頭的概率.我們將能量水平評估因子引入網(wǎng)絡的簇頭輪轉(zhuǎn)過程,以調(diào)節(jié)節(jié)點的輪轉(zhuǎn)周期,讓當前能量高的節(jié)點獲得更多機會出任簇頭:Ρ(i,r)=Ρoptef(i,r);(7)Τr(i)=1Ρoptef(i,r).(8)式(7)和式(8)分別是節(jié)點i在第r輪出任簇首的概率及其輪轉(zhuǎn)周期.顯然,對節(jié)點i而言,能量越高,其出任簇頭的概率越大,簇頭輪轉(zhuǎn)周期越短.同時,我們分析P(i,r)的數(shù)學期望值并由式(8)和式(3)可得:E(#CΗ)=Ν∑i=1Ρ(i,r)=Ν∑i=1Ρoptef(i,r)=ΡoptΝ∑i=1ef(i,r)=ΡoptΝ=kopt.(9)式(9)表明在引入能量評估因子ef(i,r)后,網(wǎng)絡優(yōu)化簇頭數(shù)kopt仍然可以得到保證.因此,DDC算法在每一輪中基于式(4)對網(wǎng)絡進行分割時,根據(jù)節(jié)點能量預評估因子對節(jié)點擔任簇頭的輪轉(zhuǎn)周期進行調(diào)整.設在第r輪中節(jié)點i的能量預評估因子為ef(i,r),則節(jié)點i提前或滯后進入集合G的輪數(shù)為rounds(i,r)=1p-1ef(i,r)p=(1-1ef(i,r))1p.(10)式(10)表明,當節(jié)點i的能量預評估因子值大于1時,rounds(i,r)的值大于0,即該節(jié)點可以提前rounds(i,r)進入集合G;當節(jié)點i的能量預評估因子值等于1時,節(jié)點i的當前輪轉(zhuǎn)狀態(tài)不變;當節(jié)點i的能量預評估因子值小于1時,rounds(i,r)的值小于0,即該節(jié)點滯后|rounds(i,r)|進入集合G.因此,該調(diào)整方法可以有效保證每輪分割過程中各分區(qū)能量的均衡性.2.4.2分區(qū)設置時節(jié)點能量均衡通過預分簇對網(wǎng)絡節(jié)點進行區(qū)域分割后,在各分區(qū)中選舉合適的簇頭節(jié)點是有效實現(xiàn)網(wǎng)絡負載均衡的重要手段.在分簇算法中,簇頭承擔接收分區(qū)內(nèi)各成員節(jié)點發(fā)送的數(shù)據(jù)包,并根據(jù)相關性進行數(shù)據(jù)融合處理,然后再發(fā)送到Sink節(jié)點.相對于成員節(jié)點,簇頭節(jié)點每輪消耗的能量要大得多.因此,在分區(qū)中選擇一個具有良好負載能力的節(jié)點擔任簇頭,有利于網(wǎng)絡負載的均衡.設在第r輪中,任意分區(qū)t(1≤t≤k)的節(jié)點集合T(t,r)中有C(t,r)個節(jié)點.則分區(qū)中出任簇頭的節(jié)點j必須滿足以下條件:j∈G且lbf(j,r)=maxi∈Τ(t,r)(lbf(i,r)).(11)式(11)條件實際上是保證在分區(qū)中擁有最大負載能力的節(jié)點來出任簇頭,從而使分區(qū)中節(jié)點能量能均衡消耗.2.4.3打造控制消息DDC算法是一種基于負載均衡的分布式成簇算法,它通過利用節(jié)點的能量評估因子和節(jié)點的負載能力預評估因子來實現(xiàn)網(wǎng)絡中各節(jié)點的能量均衡消耗,進一步維持網(wǎng)絡的穩(wěn)定性.在DDC算法中我們定義了節(jié)點的4種狀態(tài):1)未定義狀態(tài)(undefined,UN).節(jié)點每一輪開始時的初始狀態(tài);2)區(qū)頭節(jié)點(areahead,AH).網(wǎng)絡分割時各分區(qū)產(chǎn)生的預定義簇頭節(jié)點;3)簇頭節(jié)點(clusterhead,CH).4)從節(jié)點(slavenode,SN).隸屬于各簇頭的節(jié)點.同時,還定義了3種控制消息:1)區(qū)頭聲明消息(AH_MSG)2)從節(jié)點加入消息(ADD_MSG)3)從簇頭選定消息(CH_MSG)DDC算法的每一輪包括3個階段:1)節(jié)點分割階段.在每一輪開始時,每個節(jié)點選取一個介于0和1之間的隨機數(shù),并根據(jù)式(4)給定的閾值,決定自己是否成為區(qū)頭(AH),若是,則向所有節(jié)點廣播聲明區(qū)頭消息(AH_MSG);否則,從已收到的各區(qū)頭聲明消息中選取距自己最近的區(qū)頭,并向其發(fā)送加入消息(ADD_MSG).經(jīng)過一段時間后,每個區(qū)頭都擁有一定數(shù)量的成員節(jié)點(SN).在這個階段,利用區(qū)頭實現(xiàn)了對網(wǎng)絡節(jié)點的分割.2)節(jié)點成簇階段.在網(wǎng)絡節(jié)點分割完畢后,每個區(qū)頭節(jié)點從收到的ADD_MSG消息中提取各從節(jié)點的當前能量和坐標,根據(jù)式(2)計算各從節(jié)點的負載能力評估因子,并根據(jù)式(11)選取本分區(qū)的簇頭節(jié)點(CH).然后根據(jù)式(3)重新計算分區(qū)中各節(jié)點的能量預評估因子,并將其包含在CH_MSG消息中發(fā)送給各從節(jié)點.若選取的簇頭節(jié)點就是區(qū)頭節(jié)點,則區(qū)頭將自己狀態(tài)設為簇頭節(jié)點(CH);否則,將自己的狀態(tài)設置為從節(jié)點,并將所依附的簇頭節(jié)點設為已選取的簇頭節(jié)點.各從節(jié)點收到來自本分區(qū)的CH_MSG消息后,若CH_MSG消息中指定的簇頭ID與自己相符,則從節(jié)點將自己狀態(tài)更新為簇頭節(jié)點(CH);否則,將自己所依附的簇頭節(jié)點設為CH_MSG消息中指定的簇頭節(jié)點.3)數(shù)據(jù)傳輸階段.節(jié)點成簇階段完成后,各從節(jié)點開始向本節(jié)點所依附的簇頭節(jié)點發(fā)送數(shù)據(jù)包.節(jié)點在本輪數(shù)據(jù)傳輸完成后,根據(jù)式(10)對自身的輪轉(zhuǎn)狀態(tài)進行調(diào)整.下面我們給出DDC算法中任意節(jié)點i在第r輪的一般成簇算法.算法1.節(jié)點i在第r輪成簇算法.3基于算法的仿真實驗在本節(jié),主要利用仿真實驗對算法的性能進行分析和評價.仿真實驗采用文獻所使用的通信能量模型,并設定主要參數(shù)如表1所示:場景A.節(jié)點的初始能量相同,即設定每個節(jié)點的初始能量為2J,網(wǎng)絡初始總能量為200J.場景B.節(jié)點的初始能量在[1J,3J]區(qū)域內(nèi)隨機分布,但網(wǎng)絡的初始總能量為200J.基于算法比較的公平性,分別在這兩種仿真場景下對LEACH算法、LEACH-LBF算法、DCHS算法、DCHS-LBF算法及DDC算法進行了仿真.其中,LEACH-LBF算法和DCHS-LBF算法是基于lbf因子對LEACH和DCHS的改進算法.3.1算法性能對比網(wǎng)絡生命周期是衡量算法能量有效性的重要依據(jù).在分簇算法中,網(wǎng)絡生命周期主要體現(xiàn)在成簇穩(wěn)定期(即從網(wǎng)絡開始運行到第1個節(jié)點死亡時持續(xù)的輪數(shù)),成簇穩(wěn)定期越長,則網(wǎng)絡能量有效性越好.根據(jù)仿真場景A和B(Sink節(jié)點位于(50m,250m))得到算法的網(wǎng)絡生命周期圖(如圖2～4所示):由圖2～4可知,在場景A和B下,LEACH-LBF性能較原算法均沒有明顯改善,但DCHS-LBF算法較原算法改善明顯,這是由于DCHS算法考慮了節(jié)點剩余能量的結(jié)果.由于場景B并不符合LEACH的理想條件(節(jié)點初始能量相同),因此,在場景B下,LEACH的第1節(jié)點死亡時持續(xù)的輪數(shù)比在場景A下降低了30%;同樣,DCHS算法也存在類似情況.相對LEACH算法和DCHS算法,DDC算法的生命周期得到了顯著提高,而且在場景B下表現(xiàn)更為明顯.為了更好對算法性能進行比較,我們通過改變Sink節(jié)點的位置(X=50m,Y=150～550m)來分析算法的生命周期的變化情況(如圖5～7所示).從圖5～7可知,在場景A和B下,LEACH-LBF和DCHS-LBF算法在不同位置中的生命周期均優(yōu)于原算法;LEACH和DCHS在不同位置下的生命周期場景A中要明顯優(yōu)于場景B,這表明這兩個算法不適用于初始能量不同的場合;而DDC算法在兩種場景中優(yōu)勢明顯.3.2能量消耗對比顯然,網(wǎng)絡負載越均衡,節(jié)點在每輪中消耗的能量就越均勻,其生命周期就越長.根據(jù)場景A和B(Sink節(jié)點位于(50m,250m)