基于lech算法的無線傳感器網(wǎng)絡(luò)分簇路由機制研究

基于lech算法的無線傳感器網(wǎng)絡(luò)分簇路由機制研究

作為一種新的獲取和處理形式，無線傳感器網(wǎng)絡(luò)（無線傳感器網(wǎng)絡(luò)，簡稱wsd）已成為國內(nèi)外的研究熱點。由于工作環(huán)境和自身構(gòu)造所限,WSN網(wǎng)絡(luò)傳感器節(jié)點的計算、通信能力及能量都十分有限,對于節(jié)點的更換和充電也較難實現(xiàn)。因此,盡量減少節(jié)點能耗、延長網(wǎng)絡(luò)生存時間已成為WSN網(wǎng)絡(luò)協(xié)議及傳輸機制研究的一個主要目標。網(wǎng)絡(luò)中的數(shù)據(jù)傳輸是靠路由協(xié)議來控制管理的,無線傳感器網(wǎng)絡(luò)具有與傳統(tǒng)網(wǎng)絡(luò)不同的特點,且與應(yīng)用高度相關(guān),傳統(tǒng)路由協(xié)議不能有效地用于無線傳感器網(wǎng)絡(luò)。WSN路由協(xié)議負責(zé)在基站節(jié)點和其余節(jié)點間可靠地傳輸數(shù)據(jù)。由于WSN與應(yīng)用高度相關(guān),單一的路由協(xié)議不能滿足各種應(yīng)用需求,因而人們研究了眾多的路由協(xié)議,其中LEACH(Low-EnergyAdaptiveClusteringHierarchy)協(xié)議是由美國麻省理工學(xué)院的J.Heinzelman等人提出的一種低功耗自適應(yīng)分層算法,對該算法的分析研究及其改進有著重要的應(yīng)用價值。1第一階段:初始和穩(wěn)定階段LEACH算法將WSN中的所有節(jié)點分為若干簇,每個簇選舉一個首領(lǐng),簡稱簇頭。算法操作時使用了“輪”的概念,每一輪由初始化和穩(wěn)定工作兩個階段組成。在初始化階段,算法隨機地選取節(jié)點作為簇頭,簇頭向所有節(jié)點廣播此消息,其它節(jié)點根據(jù)接收信號的強弱加入就近的簇,并通知相應(yīng)的簇頭;在穩(wěn)定階段,簇頭節(jié)點接收簇中其它節(jié)點發(fā)送的數(shù)據(jù),并將這些數(shù)據(jù)進行必要的融合,然后發(fā)送給基站節(jié)點。在本輪工作結(jié)束之后,網(wǎng)絡(luò)將進入初始化和穩(wěn)定工作的下一輪新的工作周期。1.1性確保節(jié)點成為簇頭的概率,算法b初始化工作階段,對簇頭的選擇是LEACH協(xié)議關(guān)鍵的任務(wù),LEACH采用閾值的方式,即每個節(jié)點產(chǎn)生一個0～1之間的隨機數(shù),如果這個數(shù)小于閾值T(n),則該節(jié)點向周圍節(jié)點廣播它是簇頭的消息。T(n)的計算公式為:T(n)={p1?p(rmod(1/p))0n∈G?其他.(1)Τ(n)={p1-p(rmod(1/p))n∈G?0其他.(1)式中:p是簇頭占所有節(jié)點的百分比,即節(jié)點當(dāng)選簇頭的概率;r是目前進行的輪數(shù);G是最近1/p輪中還未當(dāng)選過簇頭的節(jié)點集合。從公式(1)知,當(dāng)選過簇頭的節(jié)點在接下來的1/p輪循環(huán)中將不能成為簇頭;剩余節(jié)點當(dāng)選簇頭的閾值T(n)增大,節(jié)點產(chǎn)生小于T(n)的隨機數(shù)的概率隨之增大,所以節(jié)點當(dāng)選簇頭的概率增大。p值決定了每輪產(chǎn)生的簇頭數(shù)量,在實際應(yīng)用中,最佳p值的確定是十分困難的,與網(wǎng)絡(luò)規(guī)模和節(jié)點密度等因素有關(guān)。另外,T(n)沒有考慮能量因素,這種算法必須基于兩個前提假設(shè)才能達到每個節(jié)點平均耗費能量的預(yù)期目標:1)每個節(jié)點初始能量均等;2)每個節(jié)點擔(dān)任簇頭期間耗費的能量均等。然而,由于每個簇的大小以及簇頭到基站的距離不一樣,前提假設(shè)(2)不符合現(xiàn)實情況。1.2基于letch-h的動態(tài)分簇算法基于LEACH協(xié)議分層的思想,研究人員提出了一些新的改進算法,如LEACH-F(LEACH-Fixed)和LEACH-C(LEACH-Centralized)算法,這兩種算法與LEACH算法的不同在于挑選簇頭的方式。LEACH算法是由節(jié)點根據(jù)某個閾值自主決定是否當(dāng)選簇頭,稱為分布式簇頭選擇算法;而LEACH-F和LEACH-C是由基站基于整個網(wǎng)絡(luò)信息集中挑選簇頭,稱為集中式簇頭選擇算法。LEACH-F算法中,在初始階段根據(jù)節(jié)點的初始能量,將WSN中的所有節(jié)點分為幾個固定的簇,基站為每一個簇分配一個簇頭列表,每個簇在每一輪結(jié)束后,根據(jù)簇頭列表指示簇內(nèi)節(jié)點輪流充當(dāng)簇頭的順序。當(dāng)簇形成以后,整個簇結(jié)構(gòu)就不再發(fā)生變化,簇內(nèi)節(jié)點根據(jù)簇頭列表依次成為簇頭。LEACH-F最大的優(yōu)點就是無需每輪循環(huán)都構(gòu)造簇,減少了構(gòu)造簇的開銷,其缺點是LEACH-F不能動態(tài)處理節(jié)點的加入、死亡和移動等情況。借助LEACH-F考慮初始因素的思想以及LEACH動態(tài)分簇的思想,針對兩者的不足,提出了將節(jié)點初始能量因素考慮進來的LEACH-EI(EnergyInitializationCluster-HeadSelection)算法,LEACH-EI將節(jié)點初始能量因素考慮進來,改進了T(n)的計算公式,其公式為:T(n)={p1?p(rmod(1/p))En?cEn?i0n∈G?其他.(2)Τ(n)={p1-p(rmod(1/p))En-cEn-in∈G?0其他.(2)式中:En-c表示節(jié)點的當(dāng)前能量;En-i表示節(jié)點的初始能量。改進后的公式(2)使能量消耗比例較低的節(jié)點優(yōu)先當(dāng)選簇頭。然而,公式(2)有一個缺陷,即當(dāng)網(wǎng)絡(luò)運行相當(dāng)長一段時間后,所有節(jié)點的當(dāng)前能量En-c都變得很低,那么閾值T(n)就會變小,所有節(jié)點成為簇頭的概率都大大降低,每輪當(dāng)選的簇頭數(shù)量減少,終將導(dǎo)致網(wǎng)絡(luò)能量耗費不均衡,網(wǎng)絡(luò)生命周期縮短的局面。LEACH-C算法根據(jù)全局信息挑選簇頭,可以有效解決LEACH在每輪挑選簇頭時不能確定簇頭個數(shù)和地理位置的不足。采用LEACH-C算法的WSN中,每個節(jié)點把自身地理位置和當(dāng)前能量報告給基站,基站根據(jù)所有節(jié)點的報告計算平均能量,當(dāng)前能量低于平均能量的節(jié)點不能成為候選簇頭。基于LEACH-C的思想,針對LEACH-EI的不足,提出了可有效解決網(wǎng)絡(luò)能耗不均衡問題,進而延長網(wǎng)絡(luò)生命周期的LEACH-EA(EnergyAverage)算法,其閾值計算公式T(n)為:T(n)={p1?p(rmod(1/p))En?cEav0n∈G?其他.(3)Τ(n)={p1-p(rmod(1/p))En-cEavn∈G?0其他.(3)式中En-c表示節(jié)點的當(dāng)前能量,Eav表示每一輪結(jié)束后的節(jié)點平均能量。2協(xié)議模擬分析2.1接收方無線裝置能耗仿真LEACH協(xié)議及其改進算法LEACH-EI,LEACH-EA算法所采用的能量模型均為第一順序無線電模型,如圖1所示。在此模型中,如果接收器、發(fā)送器之間的距離d小于某個臨界值d0,則使用自由空間模型(FreeSpaceModel,記為fs);如果接收器、發(fā)送器之間的距離d大于某個臨界值d0,則使用多路衰減模型(MultiPathModel,記為mp)。這個臨界值d0定義如下:d0=4πL√hrhtλ.(4)d0=4πLhrhtλ.(4)式中,L表示傳輸損耗,hr表示接收天線高度,ht表示發(fā)送天線高度,λ表示波長。在文獻中,公式(4)的參數(shù)取值分別為:L=1(表示無傳輸損耗),hr=ht=1.5m,無線電頻率取914MHz,計算d0≈86.2m,本文取無線電頻率為2.4GHz,則λ=(3×108)/(2.4×109)m,計算得d0≈125.6m.當(dāng)發(fā)送方傳輸數(shù)據(jù)到接收方時,使用公式(5)計算其能耗:ET(k,d)=ET?e(k)+ET?a(k,d)={kEe+kεfsd2kEe+kεmpd4d＜d0；d≥d0.(5)EΤ(k,d)=EΤ-e(k)+EΤ-a(k,d)={kEe+kεfsd2d＜d0；kEe+kεmpd4d≥d0.(5)式中:k表示傳輸數(shù)據(jù)比特數(shù),ET(k,d)表示發(fā)送方傳輸k-bit數(shù)據(jù)所消耗的能量,ET-e(k)表示發(fā)送裝置消耗能量,ET-a(k,d)表示發(fā)送端信號放大器消耗能量,Ee表示電子能耗,εfs表示采用自由空間傳播模型(fs)的系數(shù),εmp表示多路衰減模型(mp)的能量系數(shù)。相應(yīng)的,接收方無線裝置的能耗為:ER(k)=ER?e(k)=kEe.(6)ER(k)=ER-e(k)=kEe.(6)式中:ER(k)表示接收方接收k-bit數(shù)據(jù)所消耗的能量,即接收方無線裝置的能耗ER-e(k)。本文中協(xié)議仿真采用仿真工具Matlab,仿真場景如下:假設(shè)有100個傳感器節(jié)點隨機分布在一個介于(x=0,y=0)與(x=100,y=100)的區(qū)域內(nèi)。每個節(jié)點都擁有相同的初始能量E0=0.5J,且能量無法補充,基站位置為(50,50),p=0.05(節(jié)點成為簇頭的概率)。根據(jù)能量模型,數(shù)據(jù)融合消耗的能量記為EDA=5×10-9J,最大循環(huán)輪數(shù)rmax=5000輪,公式(5),(6)中取ER?e(k)=ET?e(k)=k*Ee=50×10?9J?εfs=10×10?12J/(bit?m2)?εmp=0.0013×10?12J/(bit?m4).ER-e(k)=EΤ-e(k)=k*Ee=50×10-9J?εfs=10×10-12J/(bit?m2)?εmp=0.0013×10-12J/(bit?m4).2.2剩余節(jié)點的確定借助Matlab仿真工具,通過編寫Matlab程序,實現(xiàn)對LEACH算法,LEACH-EA算法和LEACH-EI算法的仿真比較。仿真過程如下:1)根據(jù)仿真環(huán)境的設(shè)置,每一輪都要對100個節(jié)點進行分簇,并選擇不同的節(jié)點成為簇頭,同時為非簇頭節(jié)點選擇自己所屬的簇。通過每一輪的篩選簇頭過程,可以將能量較高的節(jié)點選為簇頭,避免由于能量消耗不均勻而影響網(wǎng)絡(luò)生命周期。2)每一輪運行過程中,都要判斷是否有死亡節(jié)點,并將每一輪的剩余節(jié)點數(shù)保存為文件表。由于網(wǎng)絡(luò)運行過程中并不一定每一輪都會有節(jié)點死亡,因此有些輪的剩余節(jié)點數(shù)是相同的。3)根據(jù)剩余節(jié)點文件表,選出剩余節(jié)點不同的輪。由于三種算法的不同,可以通過該過程,成功記錄每一種算法在運行過程中剩余節(jié)點不同的輪數(shù)。4)比較網(wǎng)絡(luò)生命周期。在無線傳感器網(wǎng)絡(luò)中,對網(wǎng)絡(luò)生命周期有不同的計算標準:將第一個節(jié)點的死亡時間作為網(wǎng)絡(luò)生命周期;將50%的節(jié)點死亡時間作為網(wǎng)絡(luò)生命周期;將節(jié)點全部死亡的時間作為網(wǎng)絡(luò)生命周期。根據(jù)剩余節(jié)點文件表,按照網(wǎng)絡(luò)周期的不同計算方法,選出節(jié)點死亡1%、50%和100%的輪。仿真流程圖,如圖2所示。2.3網(wǎng)絡(luò)生命周期參數(shù)采用Matlab仿真平臺,根據(jù)仿真過程中的數(shù)據(jù),對仿真結(jié)果加以分析。LEACH-EI和LEACH-EA在運行完5000輪后,還有剩余節(jié)點,因此選擇95%的節(jié)點死亡時間作為網(wǎng)絡(luò)生命周期的參數(shù)。表1是在Matlab仿真平臺上,采用不同的網(wǎng)絡(luò)生命周期作為參數(shù),得出的在100m×100m范圍的網(wǎng)絡(luò)中,當(dāng)節(jié)點死亡1%,50%,95%時所經(jīng)過的輪數(shù)。圖3是經(jīng)過一次仿真測試后,LEACH,LEACH-EA,LEACH-EI剩余節(jié)點數(shù)對比圖,每個節(jié)點的初始能量為0.5J.剩余節(jié)點數(shù)表明了隨著時間的推移,仍然存活的節(jié)點的總數(shù),該參數(shù)是體現(xiàn)路由協(xié)議是否屬于能源有效性協(xié)議的一個重要指標。由圖3可知,當(dāng)輪數(shù)r≤2500的時候,LEACH-EI仍然存活的節(jié)點數(shù)大于LEACH和LEACH-EA。當(dāng)輪數(shù)r≤2500≤3500的時候,LEACH-EA和LEACH-EI存活節(jié)點數(shù)基本相同,r≥3500時LEACH-EI存活節(jié)點數(shù)比LEACH-EA少。圖4是經(jīng)過仿真測試后,根據(jù)仿真過程繪制的三種算法的網(wǎng)絡(luò)生命周期柱狀圖。分析圖4可知,如果以節(jié)點死亡1%和50%的時間作為衡量網(wǎng)絡(luò)生命周期的參數(shù),LEACH和LEACH-EA網(wǎng)絡(luò)生命周期大致相同,LEACH-EI稍有提高;如果以節(jié)點死亡95%的時間作為網(wǎng)絡(luò)生命周期的參數(shù),則LEACH-EA和LEACH-EI分別比LEACH提高了大約227%和139%,LEACH-EA比LEACH-EI提高了大約33.2%.3不同網(wǎng)絡(luò)模型網(wǎng)絡(luò)的matlab仿真筆者在LEACH協(xié)議的基礎(chǔ)上,