一種基于負載均衡的無線傳感器網絡節(jié)能分簇算法

1、一種基于負載均衡的無線傳感器網絡節(jié)能分簇算法姬寧,崔曉燕北京郵電大學自動化系,北京(100876摘要:由于無線傳感器節(jié)點的能量是有限的,如何延長節(jié)點和網絡的工作壽命成為一個很關鍵的問題。LEACH算法采用本地簇頭隨機輪轉機制將能量負載分擔給網絡中的所有傳感器節(jié)點,但是,簇頭選舉的隨機性和簇內節(jié)點數(shù)目的不均衡可能導致某些節(jié)點過快耗盡能量而死亡。本文提出了一種基于負載均衡的簇頭選舉方案,采用粒子群優(yōu)化(PSO算法先行分簇,然后考慮能量和距離再推舉出簇頭。仿真結果表明,該算法比LEACH更有效地平衡了能量消耗,并顯著延長了網絡的存活時間。關鍵詞:傳感器網絡,粒子群優(yōu)化,負載均衡,分簇中圖分類號:TN

2、929.51. 引言無線傳感器網絡是由大量傳感器節(jié)點通過無線通信技術自組織構成的網絡,它可以廣泛地應用于軍事、工業(yè)控制、環(huán)境監(jiān)測等諸多領域,尤其適合部署在環(huán)境惡劣和人員不易到達的場所。與傳統(tǒng)網絡不同,構成無線傳感器網絡的節(jié)點能量是有限的,且耗盡之后難以補充,所以,高效的利用節(jié)點能量,盡可能延長網絡的存活時間成為網絡協(xié)議設計的重要目標之一。研究表明,對于大規(guī)模的無線傳感器網絡,層次型分簇路由算法比平面路由算法具有更好的適應性和節(jié)能性1。近年來,研究人員提出了多種傳感器網絡的分簇算法7,其中比較典型的是W. Heinzelma等人提出的一種低功耗自適應分簇算法LEACH2。LEACH算法將各個節(jié)點

3、進行分簇,每個簇中有一個簇頭節(jié)點專門負責收集其成員的數(shù)據(jù)進行融合后發(fā)送給基站,由于簇頭必須消耗更多的能量來進行數(shù)據(jù)的處理和轉發(fā),LEACH通過隨機簇頭輪轉的方法使得各個節(jié)點輪流擔任簇頭的職責。盡管LEACH有效的節(jié)省了能量消耗,并充分考慮了數(shù)據(jù)的相關性,但是仍然存在一些不足:首先,它沒有考慮到節(jié)點分布的拓撲結構,可能距離很近的兩個節(jié)點同時成為簇頭,這樣,密集區(qū)域就被拆分為多個簇;其次,簇頭選舉的過程沒有考慮節(jié)點的能量問題,可能能量較低的節(jié)點被選為簇頭,會導致該節(jié)點過早的耗盡能量而死亡;第三,沒有考慮節(jié)點之間的距離,這種情況下簇內的能量消耗并不是最優(yōu)值。本文提出了一種基于負載均衡的分簇算法,利用

4、粒子群優(yōu)化算法(PSO進行分簇,使得每個簇內包含的節(jié)點數(shù)目相同,然后充分考慮距離和能量的因素選舉出簇頭,該算法能夠使各節(jié)點均衡地分擔負載,并有效降低了系統(tǒng)的能量消耗。2. 問題描述在實際的網絡環(huán)境中,節(jié)點并不是平均分布在整個區(qū)域的,隨機簇頭選舉算法的結果可能導致各個簇的規(guī)模相差很大,這就意味著節(jié)點密集區(qū)域的簇頭要承擔更多的數(shù)據(jù)處理和轉發(fā)任務,比稀疏節(jié)點區(qū)域的簇頭能量消耗要大得多,也就有可能因能量耗盡而過早的死亡。出于均衡負載的考慮,我們希望能將整個區(qū)域劃分成規(guī)模相等的若干個簇,每個簇內的節(jié)點數(shù)目相等。首先,我們作出以下假設:1 所有傳感器節(jié)點隨機分布在二維平面上,節(jié)點的各項參數(shù)均相同且能量有限

5、; 2 節(jié)點具有GPS 定位功能,能夠獲得自己的位置信息;3 節(jié)點控制器支持狀態(tài)切換功能,當節(jié)點空閑時可以轉入休眠狀態(tài)以節(jié)省能量; 4 為了避免多跳通信產生的延時和過多的能耗,這里采用單跳通信方式,即簇頭節(jié)點與基站之間直接通信。當區(qū)域劃分確定之后,我們希望能找到一個最合適的節(jié)點作為簇頭,使得簇內通信的能量消耗和簇頭基站之間通信的能量消耗之和最小。本文采用文獻2的通信模型。設兩節(jié)點間距離為d ,短距離通信情況即兩節(jié)點都在節(jié)點通信距離r 內的時候,能量消耗與2d 成正比。在節(jié)點通信距離r 以外的時候,能量消耗與4d 成正比。節(jié)點傳送l bit 數(shù)據(jù)到與之距離為d 的另一個節(jié)點所消耗能量表示為:24

6、,(,elec fs Tx elec mp lE l d d r E l d lE l d d r+<=+(1其中第一項lEelec 表示數(shù)據(jù)編碼、調制解調等過程消耗的能量,第二項則根據(jù)通信距離遠近選擇對應的無線發(fā)送方式消耗的能量。節(jié)點接收l bit 長度數(shù)據(jù)所消耗能量為:(Rx elec E l lE =(23. 基于PSO 優(yōu)化的分簇算法該算法分為兩大步驟,首先是利用PSO 算法進行區(qū)域劃分,將整個區(qū)域劃分成若干個相同規(guī)模的簇;第二步是在已劃分好的簇內根據(jù)節(jié)點的信息和能量選舉出最合適的節(jié)點作為簇頭節(jié)點。下面進行詳細介紹。3.1應用PSO 算法進行分簇文獻4提出了一種使用粒子群優(yōu)化算法

7、(PSO 來解決異構無線傳感器網絡分簇問題的方案,本文基于同樣原理針作了一些改動,解決了同構傳感器網絡均勻分簇的問題。假設共有N 個傳感器節(jié)點,準備將整個網絡劃分為M 個簇,則每個簇包含的節(jié)點數(shù)目為N/M。首先,我們使用PSO 優(yōu)化算法來確定一條區(qū)域分割線,使得分割線兩端的區(qū)域包含了相等的節(jié)點數(shù)目。分割線以如下形式表示:(,P x y =(3其中,(x,y表示位于分割線上的點的橫縱坐標,表示分割線與x 軸的夾角。 定義fitness 函數(shù)為如下形式:221122(Fitness c f N c f N =+(4其中,(1,2i c i =表示區(qū)域i 中的節(jié)點總數(shù),i f 由(5式決定,(1,2

8、ii M f i M= (5其中,i M 表示區(qū)域i 期望的簇頭節(jié)點數(shù)目,即希望通過分割使得該區(qū)域保留多少個簇頭節(jié)點。顯然,如果M 是偶數(shù),當區(qū)域1和2包含的簇頭節(jié)點數(shù)目相等時,121/2f f =。分簇算法描述:Step1:所有節(jié)點向基站發(fā)送ADV 報文,廣播自己的位置信息和能量信息;Step2:基站收到節(jié)點的ADV 報文,開始定義Q 個粒子用來執(zhí)行PSO 算法進行分簇; Step3:為Q 個粒子的參數(shù),x y 賦予隨機選取的值,由(3式可以確定各自代表的分割線,他們將整個區(qū)域分割成Q x 2個不同的子區(qū)域。由于基站得到了各個節(jié)點的位置信息,可以確定它們是否在某個區(qū)域內,也就可以得到相應的(

9、1,2i c i =值;Step4:將(1,2i c i =代入(4式可以得到Q 個不同的fitness 值,比較這Q 個值和上次搜索得到的最小fitness ,取最小值對應的粒子作為全局極值gd p ;比較單個粒子在之前的搜索過程中得到的fitness 值取最小的作為個體極值id p ,然后通過下式更新,x y :xid xid xid yid yid yid id id idX X v X X v X X v =+=+=+(6其中,xid yid X X 表示粒子的位置,id X 表示分割線的傾角,xid v ,yid v ,id v 分別表示粒子在,x y 三個維度上的搜索速度,它們由下

10、列等式決定,121212*(*(*(*(*(*(xid xid id xid gd xid yid yid id yid gd yid id id id id gd id v wv c rand p X c rand p X v wv c rand p X c rand p X v wv c rand p X c rand p X =+=+=+(7其中,rand(是介于(0,1之間的隨機數(shù)。1c ,2c 是學習因子,通常1c =2c =2。w 是權重因子,較大的權重因子使得粒子搜索新區(qū)域的力度更大,較小的權重因子使得粒子在當前區(qū)域進行細微的搜索。Step5:粒子得到新的,x y 后,代入(3式

11、轉入Step3的搜索過程,直至滿足fitness 值為0或者達到最大搜索次數(shù)時退出。理想情況下,當劃分結果達到最優(yōu)時,1122,c f N c f N =,(2式的值為0。也就是說,使得fitness 函數(shù)值近似為0的分割線將整個區(qū)域分割成兩個規(guī)模相等的子區(qū)域。Step6:當?shù)谝粭l區(qū)域分割線確定后,轉入Step2對兩個子區(qū)域再次分割,直到M 個簇被劃分完畢為止。3.2 基于能量和距離考慮的簇頭選舉算法文獻5研究了通信模型為(1(2時,單個簇與基站通信總能量消耗最小的滿足條件,即基站、簇頭、簇的質心在同一直線上。假設基站位置為(0,0,理想簇頭位置為(,CH CH x y ,簇內節(jié)點的位置為(,

12、i i x y ,簇內節(jié)點總數(shù)為n (包括簇頭,則有下列等式:11(,(,nniii i CH CH xyx y nn=(8其中,滿足下面關系:22113(1,2n ni i mp i i fs x y n n n =+= (9經過PSO 算法均勻分簇后,我們很容易得到簇內的節(jié)點數(shù)量,各節(jié)點的位置均可獲得,由(6、(7兩式可以計算出理想簇頭節(jié)點的位置(,CH CH x y ,那么,距離該點最近的節(jié)點應該被選為簇頭。但是,純粹的依靠位置信息來選舉簇頭存在著很大的弊病,某些位置的節(jié)點被選舉為簇頭的次數(shù)會遠遠高于其他節(jié)點,而位置比較偏僻的節(jié)點幾乎不可能成為簇頭節(jié)點,這就導致了一些節(jié)點很快死亡,與負載

13、均衡的目標背道而馳。所以,我們需要考慮節(jié)點剩余能量的因素,能量越小的節(jié)點成為簇頭的可能性應該越低3。假設節(jié)點i 的剩余能量為i E ,它與簇內總剩余能量的比值為1/ni i ii r E E=,設i d 為節(jié)點i 與理想簇頭節(jié)點的距離,則i d = ,定義函數(shù) 1(,ir i i i T d r d e =(10(,i i T d r 最小時對應的節(jié)點i 將被選舉為簇頭。由上式可以看出,0i r 時T ,這就避免了節(jié)點因為距離理想簇頭太近而被多次選舉為簇頭的情況。同時,T 與i d 成正比,各節(jié)點剩余能量相差不大時,距離理想簇頭節(jié)點較近的節(jié)點成為簇頭的幾率更大。當基站確定各個簇的區(qū)域范圍和簇頭

14、的選舉后,向節(jié)點廣播INFO 報文,告知他們所屬簇以及簇頭ID 的信息,然后簇間通信開始,該過程與LEACH 相同,不再贅述。4. 仿真實驗4.1仿真環(huán)境在仿真實驗中,無線傳感器網絡由N=100個具有GPS 定位功能的節(jié)點構成,節(jié)點隨機分布在(0,0至(100,100的方形區(qū)域內,基站的位置坐標是(0,0,每個節(jié)點的初始能量為2J 。這里采用(1(2式的通信模型,其中,發(fā)送和接收電路的功耗elec E = 50 nJ/bit ,無線覆蓋半徑r=25m ,fs =10pJ ,mp =0.0013pJ ,簇頭與節(jié)點總數(shù)的比值取5%,即M=5。本文采用ns2網絡仿真平臺6,PSO 算法中的相關參數(shù)值

15、分別為:學習因子1c =2c =2,最大迭代次數(shù)MAXITER=100,權重因子w 初始值為0.9,隨著迭代次數(shù)的增加隨下式而變化,(0.4*(/0.4w w MAXITER iter MAXITER =+(11其中,iter 是當前的迭代次數(shù)。為了測試算法的性能,將該算法與LEACH 進行比較,并使用以下兩種性能評價參數(shù):1網絡存活時間,從仿真開始到一定比例的節(jié)點死亡(存活節(jié)點數(shù)小于期望的簇頭數(shù)為止所經過的時間;2每單位能耗基站接收到的數(shù)據(jù)量。4.2仿真結果與分析圖1給出了使用PSO算法進行分簇的效果圖,很明顯,整個區(qū)域被分成了5個簇,每個簇內包含的節(jié)點數(shù)基本相同,很好的滿足了我們的預計目標。 圖1 經過PSO算法得到的分簇結果圖2給出了兩種算法的網絡存活時間比較,可以看出,本文提出的分簇算法比LEACH 具有更長的網絡生存時間。由于LEACH沒有考慮到節(jié)點能量和負載均衡的問題,導致了一些節(jié)點因過度消耗而很快死亡,而本文提出的算法則較好的平衡了各節(jié)點間的能耗,所以能有效的延長網絡生存期。圖3對兩種算法的能耗效率做了比較,在耗能相同的情