基于lech算法的無線傳感器網絡分簇路由機制研究

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