基于lech協議的傳感器網絡分簇路由協議

無線無線通信技術、嵌入式技術和微信傳感器技術的快速發展和成熟，導致了大規模的微信傳感器網絡。無線傳感器網絡（無線傳感器網絡，簡稱無線傳感器網絡）可以組織得更多。雖然無線傳感器網絡與現有的無線自組織網絡有許多相似之處,但同時也存在很大差別,其中最顯著的便是由于無線傳感器網絡節點一般采取隨機一次性部署的方式,不同于無線自組織網絡節點通常具有持續的能量供應。無線傳感器網絡中節點的能量是由內置的電池提供,因此,整個傳感器網絡的生存期受到電池容量限制。為延長整個網絡的生存期和提高網絡的利用率,較好的途徑是尋找一種更好的節省網絡節點消耗能量的算法,而分簇正是為了解決這些問題引入對網絡分層方法的重要技術。分簇技術是實現上述目標的重要而有效的手段,分簇算法可以減少節點發送數據的距離和數據包碰撞次數,加之經過數據融合處理,減少發送數據的長度,從而極大地降低每個節點的能耗由于節點能量的限制,簇內節點與簇首的通信方式以及簇的拓撲結構決定了整個網絡能量的消耗速度。本文在分析現有分簇路由協議特點和不足的基礎上,提出了一種改進的能量優化的分簇路由協議。除采用了新的簇首競爭參數,同時又在簇首集合上構造了簇間多跳路由,通過多跳傳輸的方式減少直接與基站通信的簇首數量,從而可以進一步降低能量的開銷。1無線傳感器網絡的分簇算法分簇算法(ClusterAlgorithm)是無線傳感器網絡中實行分層路由所采用的一種重要方法。分簇的概念最早是在分組無線網中提出,主要是針對網絡中的節點進行層次劃分,若干個相鄰節點構成—個簇,然后每個簇內選舉一個簇頭(ClusterHeader),由簇頭節點管理和維護本簇范圍內節點,負責簇內節點通信,同時為簇間節點通信提供合適的路由信息,簇頭之間的連接構成上層骨干網,所有簇間通信都通過骨干網進行轉發。迄今為止,在無線自組網(WirelessAdHocNetwork)中已經提出較多的分簇算法用于實施層次路由協議,而無線傳感器網絡中的分簇算法正處于研究的階段。同無線自組網相比,無線傳感器網絡中的分簇算法更側重于保持網絡整體的能量消耗的均衡,避免出現熱點(Hotspot)問題,最大化地延長網絡的生存時間。在分簇的拓撲管理機制下,網絡中的節點分為簇頭節點和成員節點兩類。在每個簇內,根據一定的機制選取某個節點作為簇頭,用于管理和控制整個簇內成員節點,協調成員節點之間的工作,負責簇內信息的收集和數據的融合處理以及簇間轉發。1.1簇頭自組織的存LEACH協議的全稱是“低功耗自適應集群分層協議”(LowEnergyAdaptiveClusteringHierarchy),是分簇路由算法中一種專門用于無線傳感器網絡的分簇協議。采用動態分簇技術,使網絡中的所有節點輪換充當簇頭,以均衡網絡中的能量消耗,延長整個網絡的生命周期。在LEACH算法中,節點自組織成不同的簇,每個簇只有—個簇頭。所有非簇頭節點將自己的數據發給所屬簇的簇頭節點,為減少冗余數據的傳輸,簇頭節點在數據融合后將數據發送給遠方的基站接收器。這樣,每個非簇頭節點都只需要知道自己所屬簇的簇頭信息即可,簇頭也只需要維持很小的路由表,為了避免簇頭能量消耗過快,每個節點須輪流擔任簇頭。因此LEACH算法的實現分成若干輪,每一輪又可分成簇形成階段和簇傳輸階段,而簇傳輸階段遠遠長于簇形成階段。在簇形成階段,每一個還沒有擔任過簇頭的節點分別生成0～1之間的隨機數,如果生成的隨機數小于給定的閾值T(n),則選擇為簇首。這里T(n)的計算方法如下:T(n)={p1?p×[rmod(1/p)],0,n∈G其他(1)Τ(n)={p1-p×[rmod(1/p)],n∈G0,其他(1)其中:P是簇首在所有節點中所占的百分比,r是選舉輪數,G是第r輪之前尚未當過簇首的節點集合,n是表示某節點。一旦節點被選為簇頭后,就向外發送簇頭廣播信息。非簇頭節點根據根據收到的簇頭廣播信息的信號大小決定要加入哪個簇,并向決定加入的簇的簇頭發送加入簇的請求。簇頭在收到請求后將該節點加入自己的路由表并為每個節點設定一個TDMA定時消息,并且通知該簇中所有節點。此后的簇傳輸階段,這些分布式的節點即按照該TDMA時間表、以一跳式或多跳式的路由拓撲結構進行數據傳輸。每隔一定時問,整個網絡重新進入簇形成階段開始新一輪的簇頭選舉過程。LEACH算法是讓網絡中的節點自組織地形成簇,簇頭是隨機產生的,這種隨機產生的方式無法保證簇頭節點的合理分布。當簇頭節點位置比較集中時,簇的覆蓋區域將出現部分重疊的現象,網絡拓撲結構不夠優化;當簇頭分布在邊緣區域時,簇內節點到簇頭的距離將變大,使得簇的載荷也相應變大,而且簇頭選舉中沒有考慮節點剩余能量不均等的問題,使得有些能量較少的節點被選舉為簇頭,這就加速了節點的死亡,故不能有效地延長網絡生存周期。另外由于簇頭選舉的隨機性使得網絡的簇頭需要負擔的節點數不同,加重了個別簇頭節點的負擔,使得網絡的負載平衡程度下降,也降低了網絡壽命。1.2基于letch的算法LEACH-C(LEACH-centralized)和LEACH-F(LEACH-fixed)都是集中式的簇頭產生算法,由基站負責挑選簇頭。LEACH的簇頭由節點根據隨機數自主決定,沒有明確的數目和位置,而LEACH-C根據全局信息挑選簇頭,每個節點把自身地理位置和當前能量報告給基站。基站根據所有節點的報告計算平均能量,當前能量低于平均能量的節點不能候選簇頭。從剩余候選節點中選出合適數量和最優地理位置的簇頭集合是一個NP問題。基站根據所有成員節點到簇頭的距離平方和最小的原則,采用模擬退火(SimulatedAnnealing)算法解決該NP問題。最后,基站把簇頭集合和簇的結構廣播出去。LEACH-F也是在LEACH基礎上做了一些改變。簇的形成與LEACH-C一樣,同時,基站為每個簇生成一個簇頭列表,指示簇內節點輪流當選簇頭的順序。最大的優點就是無須每輪循環都構造簇,減少了構造簇的開銷。但是,LEACH-F并不適合真實的網絡應用,因為它不能動態處理節點的加入、失敗和移動。同時,它還增加了簇間的信號干擾。LEACH-E是分布式簇頭產生算法,針對LEACH沒有考慮節點的剩余能量情況而選擇簇頭的不足提出的。每個節點使用式(2)的概率來決定自己是否成為簇頭節點:p(Si)=min{Ei(r)Etotal(r)k,1}(2)p(Si)=min{Ei(r)Etotal(r)k,1}(2)其中,k是總簇頭數目,Ei(r)為節點i在第r輪的剩余能量,Etotal(r)=∑i=1N∑i=1ΝEi(r),為當前網絡的總能量。式(2)的改進,使剩余能量比較高的節點優先當選簇頭,避免了選擇剩余能量低的節點導致節點快速死亡的缺點,第一個死亡節點時間比LEACH稍有延長。PEGASIS(Power—EfficientGatheringinSensorInformationSystems)協議借鑒了LEACH中分簇算法的思想。根據節點的地理位置,采用貪婪算法將所有節點形成一條相鄰節點之間距離最短的鏈,這樣每個節點都能以最小功率發送數據,并且每輪只隨機選擇一個簇頭與基站通信,減少了數據通信量。但是PEGASIS算法需要知道每個節點地理位置信息,且信息傳輸有較大時延。還有一些針對能量高效利用的路由協議被提出,TEEN(ThresholdsensitiveEnergyEfficientsensorNetwork)協議是一個基于集群的路由協議,也是由LEACH發展而來的。TEEN和LEACH的實現機制非常相似,只是前者是響應型的,而后者屬于主動型傳感器網絡。EERP基本也和HEEN一樣,沒有從節點間能量的角度考慮。2改進的新算法2.1基于非均勻分簇的傳感器網絡路由目前針對LEACH算法改進研究主要是針對兩方面:①改進簇頭選擇算法;②簇間考慮利用多跳通信傳輸數據到Sink。針對上述的設計要求,本文分別對LEACH算法的簇頭選擇算法和數據傳輸方式做了改進,設計了一種新的基于非均勻分簇的傳感器網絡路由算法(EnergyOptimal-basedUnequalClusteringProtocol,EOUCP),其基本思想是在簇頭競爭過程中,同時考慮節點及其鄰居節點的剩余能量,提高對低能量節點的保護;成簇后對簇內活動節點進行調度,在不影響監測區域覆蓋率的情況下,讓一部分節點進入休眠狀態,既節約了節點能量,也減小了數據信息的冗余度,簇頭與匯聚點間通信采用多跳的路由方式,避免長距離傳輸造成能量浪費。2.2發射功率能耗計算網絡由N個隨機部署的傳感器節點組成,同時有以下假設:①傳感器網絡為高密度靜態網絡,基站部署在方形觀測區域A的外側,傳感器節點和基站部署后均不再發生位置移動,且基站唯一;②節點具備數據融合功能,每個傳感器節點都有一個唯一的標識(ID);③節點可以根據接收方距離的遠近自由調整其發射功率以節約能量消耗;④鏈路是對稱的。若己知發送方的發射功率,節點可以根據接收信號的強度計算出發送者到自己的近似距離。EOUCP算法采用與LEACH協議相同的無線通信模型。節點發射每比特的數據到距離為d的位置,消耗的能量有發射電路和功率放大功耗兩部分組成,即ETx(l,d)={lEelec+lεfsd,d<d0lEelec+lεmpd4,d≥d0(3)EΤx(l,d)={lEelec+lεfsd,d<d0lEelec+lεmpd4,d≥d0(3)其中,Eelec:表示發射電路的能耗。若傳輸距離小于閾值d0,功率放大損耗采用自由空間模型;當傳輸距離大于等于閾值d0時,采用多路徑衰減模型。ε、εmp分別為這兩種模型中功率放大所需的能量。節點接收l比特數據的能耗為:ERx(l)=lEelec。將k個長度為l比特的數據包融合的能耗為:ERx(l)=lkEDF.其中,EDF為融合單位比特數據所需的能量。2.3算法描述2.3.1多跳的傳播算法EOUCP是基于LEACH基本思想提出的改進算法,在簇的建立階段和穩定數據傳輸階段與傳統LEACH算法的過程大致相同,主要的思想體現在改進了簇頭的選擇過程和簇頭到Sink節點之間采用多跳的傳輸方式。EOUCP算法是一個分布式競爭算法,每個傳感器節點都參與競爭,使簇頭的分布更均勻合理。競爭的主要依據是節點的剩余能量和鄰居節點的平均剩余能量的比值,不再以式(1)中的閾值作為簇頭競爭的參數。在EOUCP協議中,規定每個節點需要保存一張鄰居表,以存儲器鄰居節點的相關信息,包括節點ID、剩余能量、距離等,見表1。2.3.2節點剩余能量的獲取考慮到LEACH中簇頭競爭存在的不足,EOUCP中將節點的剩余能量和鄰居節點的平均剩余能量的比值作為簇頭節點選擇的重要參數。算法開始時,基站先以給定的功率向全網發送廣播信號,節點根據接收到的信號強度計算出它到基站的距離d,由該距離值得到自己的競爭半徑Ri,計算如下:Ri=[cEresidualEˉˉˉ+(1?c)?ddmax?dminRi=[cEresidualEˉ+(1-c)?ddmax-dminRc(4)其中,0≤c≤1,c為控制取值范圍的參數,為常系數,用來調整網絡中節點能量和距離這兩個參數所占的大小。實驗中可選擇c=0和c=0.5,通過仿真比較,可以觀察到c取不同值時,簇頭數目與Rc之間的關系。當Rc固定時,c增大對應簇頭數目要多,這是因為c的增大導致候選簇首的競爭半徑變小,因此簇頭的數目增多。Eresidual為節點在第m輪運行時的剩余的能量,EˉˉˉEˉ為第m輪運行時簇內節點的平均能量。dmax和dmin代表節點到基站的距離的最大值和最小值。Rc代表節點的最大競爭半徑。每個節點將競爭半徑內的區域作為自己的競爭區域,將競爭區域內的所有其他節點看作是自己的鄰居。節點首先以半徑Ri廣播消息,這樣算法將簇頭覆蓋區域大小限制在半徑Ri的區域內,即在簇頭節點通信半徑Ri內的節點才能成為此簇類的成員,實現了地理分布上的均勻分簇。再根據鄰居節點發送的消息更新鄰居表,最后由式(5)得到其開始簇首競爭的時間tc。tc=μTEresidual/Eˉˉˉ(5)tc=μΤEresidual/Eˉ(5)其中,μ為分布在[0.9,l]的隨機實數,為常系數,在實驗時選取合適的常數值,用來調整節點剩余能量和簇內節點平均能量所占的比重,進而可以控制節點i開始競爭簇首時間的大小。由式(5)可知,當節點剩余能量較小時,其開始競爭簇首的時間tc變短,有效保護了當節點能量較低時避免成為簇頭而加劇其死亡的可能性。T代表事先規定的簇首競爭持續時間,EˉˉˉEˉ代表鄰居節點的平均剩余能量,Eresidual代表節點的剩余能量。若節點在競爭時刻到來之前已經收到鄰居節點的簇頭申明消息,則退出競爭并發送消息加入該簇。否則,節點統計鄰居中已加入簇的節點數并與閾值k(t)進行比較。當節點數小于閾值k(t)時,廣播消息宣布競爭成功。閾值k(t)的計算公式:k(t)=m(1-e-t/T),其中t代表當前時間,m代表全部鄰居節點數。閾值k(t)的推導過程簡要說明如下:因m代表全部鄰居節點總數目,節點統計鄰居中已加入簇的節點數必然要小于最大值m,所以閾值可設為m(1-α),其中α∈(0,1)。利用指數函數e-x特性,當x∈(0,1)時,e-x∈(0,1),即閾值k(t)=m(1-e-x),而μEresidual/Eˉˉˉ∈(0,1)μEresidual/Eˉ∈(0,1),所以可令μEresidual/EˉˉˉμEresidual/Eˉ來代替x,即有閾值等于m(1-e-μEresidual/);又有式(5)分析,可得閾值k(t)=m(1-e-t/T)。簇首競爭結束后,若節點有多個鄰居節點成為簇首,則加入距自己最近的簇以減少通信干擾,未加入簇的節點發送消息至剩余能量最大的鄰居節點,通過該鄰居節點成為其他簇的多跳成員。進入穩定運行階段后,簇內成員節點持續采集監測數據,傳與簇頭節點后發送到Sink節點。持續一段時間以后,整個網絡進入下一輪工作周期,重新選擇簇頭節點。2.4節點剩余能量和中轉口誤差設計該算法對簇頭與Sink之間的通信方式做進一步的改進,算法中簇頭利用權值來選擇下一跳路由。在數據傳輸階段,采用多跳傳輸,需要建立一棵以簇頭節點組成的樹,簇頭結點為Sink,在路由表建立的過程中不再考慮時間延遲的特點,將模型理想化,忽略其延遲時間。因為相對節點之間數據的傳輸和簇頭與Sink多跳通信時間來說,節點本身的路由建立時間非常短,要相差幾個數量級,同時在數據傳輸階段可以設定一較長時間,避免頻繁建簇的能耗。首先假設簇間多跳路由協議中,中繼簇頭收到的上一跳的數據間沒有冗余信息,并且來自不同簇的數據無法進一步融合,中繼簇頭只是簡單轉發來自其它簇頭的數據。網絡結構如圖1所示。如何從鄰居簇頭集合中選擇合適的下一跳路由是簇間路由策略的關鍵,文中假設通信采用自由空間模型,鏈路消耗的能耗與距離的平方d2呈線性關系。假設簇頭i有數據傳送,如果有中繼簇頭j幫助傳輸數據,則到Sink的消耗的鏈路能耗代價歸結為(J)2,ditoj2,與簇頭i直接將數據傳給BS的鏈路能耗代價,相比,只有滿足2+ditoj2<dtosink(i)2,中繼傳輸才能節省能量消耗。為了綜合考慮節點的剩余能量和鏈路的消耗代價最低,在選擇下一跳簇頭作為路由時,考慮到中繼節點的剩余能量和中繼轉發的鏈路消耗代價兩方面。引入定義如下:Wj=E(j)E_(r?1)+dtosink(i)2dtosink(j)2+ditoj2(6)Wj=E(j)E_(r-1)+dtosink(i)2dtosink(j)2+ditoj2(6)其中dtosink(i)、dtosink(j)為簇頭i,j到Sink的距離,ditoj為第i簇頭到第j簇頭的距離,E_(r-1)為上一輪的平均能量,E(j)是節點的剩余能量。簇頭i將它的鄰居簇頭j加入到鄰居簇頭集合中,并計算這些鄰居簇頭的權值Wj,然后從權值Wj>2的鄰居簇頭中選擇下一跳路由。依照權值大小的順序來選擇該簇頭的下一跳路由順序排列在下一跳路由表中。權值越大的簇頭優先被選擇為下一跳路由,若發現權值相等的情況則根據節點的ID大小來選擇下一跳路由,下一跳路由表在每輪形成簇頭后構建形成。考慮節點的存儲量有限,下一跳路由表中只放三個路由項,分別按照權值W的大小依順序存放在路由表中。例如:如圖2,在某一輪中簇頭節點3的路由表如表2中所示,該簇頭3會選擇簇頭6作為其下一跳的中繼簇頭。在實際工作過程中,有些簇頭可能擔任多個簇頭的中繼,這樣該簇頭的能量消耗較多,容易快速死亡,造成“熱點”出現。中繼簇頭引入一個合理的能量變化閾值ΔE。考慮到每個中繼節點要發送自己的數據和允許轉發兩個其鄰居簇頭節點的數據,所以實驗中設置ΔE為3倍的自己到Sink轉發數據的通信能耗,即ΔE=3(lεfsd2itosinkitosink2)。簇頭節點能量變化閾值ΔE的設置要根據節點的轉發能力來設置,與節點和sink間的通信能耗代價有關。當中繼節點能量超過ΔE時,向鄰居簇頭廣播一能量消息通知各鄰居簇頭不再作為中繼轉發數據。鄰居簇頭就會將路由表中這個路由項刪除。選擇路由表中下一個路由項作為下一跳路由。當中繼6的能量大于閾值時,發送一消息,簇頭3收到后就會將6的這個路由項刪除。而選擇1的路由項即簇頭節點9作為下一跳路由。如果路由表中的每一個路由項的能量變化都達到閾值ΔE,那么路由表就是空的,節點3就不能利用中繼轉發,而是自己將數據送至Sink節點。在路由選擇結束,簇頭節點組成了一棵以Sink為根節點的樹,數據沿著Sink的方向在邊上傳輸。3模擬實驗與性能分析3.1節點通信距離本文采用了與文獻中類似的場景,在100m×100m的矩形區域內隨機放置100個傳感器節點,Sink節點位于(150,50)處,所有節點的通信距離為20m。假設節點的初始能量均為2J,且原始數據產生速率均為1kb/s,每個節點發送或接收數據時,發射電路需要消耗的能量Eelec=50nJ/bit,功率放大器消耗的能量Efs=100pJ/(bit·d-2),簇頭融合數據消耗的能量Edf=50pJ/bit,信號放大器的放大倍數εmp=0.0013pJ/bit/m4,信號傳輸距離d0=87m,采樣周期10s。3.2算法在網絡剩余能量上的對比本文利用NS-2仿真平臺,選取了簇頭能耗、簇頭個數、網絡能耗、存活節點數等指標來比較LEACH算法和新算法的性能,并在不考慮外界破壞因素的前提下,當一個節點的能量等于零時,定義節點失效,同時定義第一個節點死亡時間為網絡生存期。圖3所示從試驗中隨機選取20輪,統計各輪中所有簇頭消耗的能量,結果可發現