無線傳感器網(wǎng)絡(luò)中l(wèi)ech協(xié)議的分析

無線傳感器網(wǎng)絡(luò)中l(wèi)ech協(xié)議的分析

隨著計算機網(wǎng)絡(luò)技術(shù)、無線通信技術(shù)和電子技術(shù)的快速發(fā)展，無線傳感器網(wǎng)絡(luò)在世界范圍內(nèi)引起了越來越多的關(guān)注。在無線傳感器網(wǎng)絡(luò)中,傳感器節(jié)點由電池供電,大量傳感器節(jié)點通過飛機空中投放,人工布設(shè)等方式,部署在感知對象內(nèi)部或者附近。這些節(jié)點通過自組織的方式構(gòu)成無線網(wǎng)絡(luò),以協(xié)作的方式感知、采集和處理網(wǎng)絡(luò)覆蓋范圍內(nèi)特定的信息。由于傳感器節(jié)點的電源能量、計算能力和通信能力都非常有限,所以節(jié)能路由協(xié)議的設(shè)計,對無線傳感器網(wǎng)絡(luò)來說非常重要。許多節(jié)能的路由算法都是基于LEACH協(xié)議的基礎(chǔ)上進行設(shè)計的:LEACH-C算法是集中式的簇首產(chǎn)生算法。每輪開始時各個節(jié)點把自身位置和當前能量報告給基站,能量高于平均值的節(jié)點成為候選入簇首,然后采用模擬退火算法從候選節(jié)點中選出數(shù)量合適且位置最優(yōu)的節(jié)點成為簇首,最后基站把分簇結(jié)果廣播給每個節(jié)點。LEACH-C算法每輪選出的簇首數(shù)量穩(wěn)定且分布均勻,但它需要網(wǎng)絡(luò)的全局信息,可擴展性差。HeeD協(xié)議主要根據(jù)主、次兩個參數(shù),通過將能耗平均分布到整個網(wǎng)絡(luò)來延長網(wǎng)絡(luò)生存時間。其中簇首選擇的主參數(shù)依賴于剩余能量,用于隨機選取出簇首集合,具有較多剩余能量的節(jié)點將有較大的概率成為簇首;次參數(shù)依賴于簇內(nèi)通信代價,用于確定落在多個簇范圍內(nèi)的節(jié)點最終屬于哪個簇,以及平衡簇首間的負載。HeeD協(xié)議主要改進之處是在簇首的選擇中考慮了節(jié)點的剩余能量,并以主次關(guān)系引入了多個約束條件。HeeD協(xié)議分簇更快,能產(chǎn)生分布更加均勻的簇首、更合理的網(wǎng)絡(luò)拓撲。本文提出的算法結(jié)合節(jié)點的剩余能量和閥值來選擇簇首,在成簇時通過控制簇內(nèi)成員數(shù)來節(jié)約簇首的能量消耗,能很好地平衡全網(wǎng)節(jié)點的能量,延長網(wǎng)絡(luò)的生存時間。12.典型的集群協(xié)議分析1.1letch協(xié)議的主要內(nèi)容LEACH協(xié)議是一個典型的自適應(yīng)分簇協(xié)議,它采用“輪”的概念,每輪分為簇的建立和數(shù)據(jù)傳輸兩個階段。簇的建立階段:每個傳感節(jié)點隨機選擇一個0～1之間的值,如果小于給定的閾值T(n),則選擇為簇首。T(n)的計算方法如下:T(n)={P1?P×[rmod(1/P)],n∈G0,n?G(1)Τ(n)={Ρ1-Ρ×[rmod(1/Ρ)],n∈G0,n?G(1)其中:P為節(jié)點中成為簇頭的百分數(shù),r是當前的輪數(shù),G是在過去的1/P輪沒有被選擇為簇頭節(jié)點的集合,mod是求模運算符。一旦簇首被選定,它們便向周圍節(jié)點廣播這一信息,非簇首節(jié)點依據(jù)接收信號的強弱來選擇它所要加入的簇,并通知相應(yīng)的簇首節(jié)點,完成簇的建立。數(shù)據(jù)傳輸階段:節(jié)點周期性的采集監(jiān)測數(shù)據(jù),基于時分復(fù)用(TDMA)的方式發(fā)送給簇首,簇首在進行必要的數(shù)據(jù)聚集和融合之后,將處理過的數(shù)據(jù)發(fā)送到基站。數(shù)據(jù)傳輸持續(xù)一段時間后,整個網(wǎng)絡(luò)進入下一輪,不斷循環(huán)。LEACH協(xié)議使用了分布式算法,使得任務(wù)被分散到每個傳感器節(jié)點上,有效地減少了每個節(jié)點的負載,延長了傳感器網(wǎng)絡(luò)的生存時間。但LEACH協(xié)議還存在以下缺點:①每一輪都進行一次簇重組,帶來了大量的開銷。②根據(jù)公式(1)的簇首選舉策略選取簇首,可能造成簇首分布不均,簇內(nèi)成員個數(shù)差異較大,使得各簇首負載不均衡,造成個別簇首較早死亡。③簇內(nèi)的節(jié)點都直接與簇首通信,增加了簇首的能量消耗。④簇首也采用單跳的方式直接和基站通信,當網(wǎng)絡(luò)規(guī)模很大時,通信的范圍也很大,對于能量受限的傳感器網(wǎng)絡(luò)節(jié)點來說,加速了節(jié)點的能量消耗,降低了網(wǎng)絡(luò)的生存時間。1.2數(shù)據(jù)傳輸機制PEGASIS協(xié)議通過貪心算法把傳感節(jié)點組織成一條鏈,節(jié)點只與距離它最近的鄰居節(jié)點通信,并且每輪中只選一個節(jié)點作為領(lǐng)導(dǎo)節(jié)點與基站通信。當領(lǐng)導(dǎo)節(jié)點選定后,就采用令牌控制機制進行數(shù)據(jù)傳輸。首先將令牌傳遞給鏈兩端的端節(jié)點,端節(jié)點向鏈中的鄰節(jié)點發(fā)送數(shù)據(jù),鄰節(jié)點將自己的數(shù)據(jù)和接收到的數(shù)據(jù)進行數(shù)據(jù)融合處理,然后將融合后的數(shù)據(jù)再發(fā)送到下一個節(jié)點,最終由領(lǐng)導(dǎo)節(jié)點融合兩邊的數(shù)據(jù)并發(fā)送給基站。與LEACH協(xié)議相比,PEGASIS協(xié)議中的節(jié)點平均通信距離較短,也沒有簇的重構(gòu)開銷,通過數(shù)據(jù)融合減少了發(fā)送次數(shù),而且每一輪只有一個領(lǐng)導(dǎo)節(jié)點與基站通信,降低了能耗。但所有的傳感節(jié)點形成一條鏈,離領(lǐng)導(dǎo)節(jié)點較遠的節(jié)點在數(shù)據(jù)傳輸過程中會引起較大的延遲。2wob合同2.1打造多節(jié)點質(zhì)網(wǎng)在LEACH協(xié)議的基礎(chǔ)上,針對LEACH協(xié)議存在的缺點,結(jié)合PEGASIS協(xié)議優(yōu)點,本文從簇首選擇、簇的形成、簇間路由等方面進行了綜合改進。基本思想乃網(wǎng)絡(luò)運行時間仍以輪為基本單位進行分割,每輪進行簇首選擇和數(shù)據(jù)傳輸,每隔N輪為一個周期對全網(wǎng)進行一次簇重組;在選擇簇首時,首先計算出最優(yōu)簇頭數(shù),并根據(jù)網(wǎng)絡(luò)面積確定每個簇頭間的最短距離,然后結(jié)合能量因素和改進后的閥值確定初始簇首;在建簇時,每個簇由簇首控制簇內(nèi)節(jié)點數(shù),使其在最優(yōu)值,并且簇內(nèi)節(jié)點利用貪心算法成鏈;簇首間通過建立的層次路由樹選擇一條最優(yōu)路徑把數(shù)據(jù)傳送給基站;在傳輸數(shù)據(jù)時,每個周期的第一輪用初始簇首進行通信,之后每輪(根據(jù)改進后的閥值)選取鏈中節(jié)點剩余能量最大的節(jié)點作為鏈首,該鏈首也是本輪的簇首,傳輸數(shù)據(jù),直到下一個周期的簇重組。2.2具體描述2.2.1傳感節(jié)點的組成假定大量傳感器節(jié)點隨機分布在一個正方形的區(qū)域內(nèi);基站固定,且遠離傳感器網(wǎng)絡(luò)區(qū)域;所有傳感節(jié)點同構(gòu),具有全網(wǎng)唯一的ID號,并且能量受限,不可移動;節(jié)點可能通過單跳或者多跳的方式與基站通信;信道對稱,無線發(fā)射功率可調(diào)。2.2.2凝膠電液整合LEACH協(xié)議簇首節(jié)點分布不均,可能出現(xiàn)節(jié)點密集的地方簇首多,節(jié)點稀疏的地方簇首節(jié)點少,甚至部分節(jié)點可能沒有在任何簇內(nèi),這就造成網(wǎng)絡(luò)的不完全連通。另外節(jié)點密集處如果產(chǎn)生了多個簇首,收集到的數(shù)據(jù)也會產(chǎn)生冗余,造成能量的不合理消耗。因此,EBLP協(xié)議在選擇簇首時,首先計算出最優(yōu)簇首的個數(shù),然后根據(jù)網(wǎng)絡(luò)面積確定簇首間的最短距離,再結(jié)合公式(2)中改進后的閥值T(n)來選擇簇首。T(n)=P1?P[rmod(1/P)]×[En_currentEn_initial+(rs÷1P)(1?En_currentEn_initial)](2)Τ(n)=Ρ1-Ρ[rmod(1/Ρ)]×[En_currentEn_initial+(rs÷1Ρ)(1-En_currentEn_initial)](2)其中P、r、1/P和公式(1)里表示相同,En_current表示節(jié)點的當前能量,En_initial表示節(jié)點的初始能量,rs表示節(jié)點連續(xù)未當選簇首的輪數(shù)。一旦節(jié)點成為簇首,rs重置為0。改進后的閥值即考慮了能量因素,又可以動態(tài)的調(diào)整閥值,使一個在連續(xù)1/P輪中始終沒有當選過簇首的節(jié)點成為簇首的概率變大,平衡能量。下面通過數(shù)學(xué)推導(dǎo)考察如何確定最優(yōu)化的簇首個數(shù),定義分析時用到的變量:K為簇的個數(shù);Eelec是發(fā)送或接收單位信息所需能量;dtoCH簇內(nèi)成員節(jié)點到簇首節(jié)點的距離;dtoBS簇首節(jié)點到基站(BS)的距離;εfs簇成員與簇首通信時用的無線信號傳播參數(shù);εmp簇首與基站通信時用的無線信號傳播參數(shù);EDA數(shù)據(jù)融合單位信息所需的能量。簇首節(jié)點在一輪中所需能量ECH包括兩部分:接收(N/K-1)簇內(nèi)成員節(jié)點發(fā)送信息所需的能量以及與基站通信所需的能量:ECH=(N/K?1)Eelec+(Eelec+εmpE[d4toBS])ECΗ=(Ν/Κ-1)Eelec+(Eelec+εmpE[dtoBS4])簇內(nèi)單個成員節(jié)點在一輪中所需能量EnonCH僅包括其向簇首節(jié)點發(fā)送單位信息所需的能量:EnonCH=Eelec+εfsE[d2toCH]EnonCΗ=Eelec+εfsE[dtoCΗ2]那么整個簇在一輪中所需能量Ecluster包括一個簇首及(N/K-1)個簇成員所需能量:Ecluster=ECH+(N/K?1)EnonCHEcluster=ECΗ+(Ν/Κ-1)EnonCΗ所以整個網(wǎng)絡(luò)在一輪中所需能量Etotal為K個簇所需能量之和:Etotal=KEcluster=K(N/K?1)(Eelec+εfsE[d2toCH])+(NEelec+KεmpE[d4toBS])Etotal=ΚEcluster=Κ(Ν/Κ-1)(Eelec+εfsE[dtoCΗ2])+(ΝEelec+ΚεmpE[dtoBS4])即:Etotal≈2NEelec+NεfsE[d2toCH]+KεmpE[d4toBS](3)Etotal≈2ΝEelec+ΝεfsE[dtoCΗ2]+ΚεmpE[dtoBS4](3)模擬區(qū)域面積為A2,平均每個簇的面積為A2/K。由于每個簇實際為心簇首節(jié)點為中心的無線通信覆蓋區(qū)域,所以易求出圓內(nèi)任一點到加以圓心的距離的期望,進而求出E[d2toCHtoCΗ2].或者由積分知識可知:E[d2]=F/2π,又F=A2/K,可得E[d2toCHtoCΗ2]=A2/Kπ。E[d4toBStoBS4]與簇的個數(shù)K無關(guān),只與基站到模擬區(qū)域中心的距離有關(guān),用常量LBS表示,代入公式(3)有:Etotal≈2NEelec+NεfsA2/2Kπ+KεmpL4BS(4)Etotal≈2ΝEelec+ΝεfsA2/2Κπ+ΚεmpLBS4(4)對公式(4)中Etotal求導(dǎo),當導(dǎo)數(shù)為零時求得的K值使Etotal值最小,K的取值為:Kopt=NεfsA2/2πεmpL4BS??????????????√=N/2π?????√εfs/εmp??????√A/L2BS(5)Κopt=ΝεfsA2/2πεmpLBS4=Ν/2πεfs/εmpA/LBS2(5)由公式(5)可以看出,最優(yōu)簇首的個數(shù)只與網(wǎng)絡(luò)節(jié)點個數(shù)N,模擬區(qū)域邊長A,以及基站到模擬區(qū)域中心的距離LBS有關(guān)(εfs、εmp均為常量),可在網(wǎng)絡(luò)初始化時設(shè)置這幾個參數(shù)。2.2.3節(jié)點控制和執(zhí)行保護機制簇首選舉完成后,向其周圍節(jié)點發(fā)起簇首信號CH_MSG,周圍節(jié)點按照收到的CH_MSG信號的強弱向簇首發(fā)送請求加入信號JOIN_MSG,簇首根據(jù)節(jié)點加入信號的強弱控制簇內(nèi)節(jié)點使其在最優(yōu)值。如果同意加入,則向節(jié)點發(fā)送允許加入信號ALLOW_MSG,否則發(fā)送拒絕信號REJECT_MSG。每一個簇首收集這些應(yīng)答消息來進行簇的初始化,從簇首開始,和簇內(nèi)的節(jié)點利用貪心算法形成一條鏈。圖1和圖2對比了兩種算法的簇內(nèi)結(jié)構(gòu):2.2.4廣播一個短包由于基站遠離傳感器網(wǎng)絡(luò)區(qū)域,如果簇首與基站采用單跳通信,則能量損耗將采用多徑衰落模型,通信距離遠的節(jié)點能量消耗隨著通信距離的四次方增長,因此EBLP協(xié)議采用多跳通信減少與基站遠距離直接通信的簇首個數(shù),節(jié)約能耗。另外,本文算法還將簇首的剩余能量作為其是否當選為中繼節(jié)點的一個重要標準。簇首間層次路由樹的建立過程如下:①基站洪泛廣播一個短數(shù)據(jù)包,該包中包含有三種類型的信息:發(fā)送該包的節(jié)點ID、接收到該包時經(jīng)過的跳數(shù)(HOP_COUNT)和發(fā)送該包的節(jié)點的剩余能量(ENERGY)。初始情況下ID為基站,跳數(shù)設(shè)為0,能量設(shè)為∞。非簇首節(jié)點忽略這個數(shù)據(jù)包。②當簇首收到這樣一個短數(shù)據(jù)包后,修改這個包中的跳數(shù)值為HOP_COUNT+1,并和先前已存的跳數(shù)HOP_COUNTold作比較:如果HOP_COUNTold<HOP_COUNT+1,則簇首中已存的父節(jié)點ID不變;如果HOP_COUNTold>HOP_COUNT+1,則修改簇首中已存的父節(jié)點ID為發(fā)送該包的節(jié)點ID;如果HOP_COUNTold=HOP_COUNT+1,接著比較該簇首的能量ENERGY和包中存儲的節(jié)點的能量ENERGY’,如果ENERGY<ENERGY’,則修改簇首中已存的父節(jié)點ID為發(fā)送該包的節(jié)點ID,并把ENERGY’修改為ENERGY,否則簇首中已存的父節(jié)點ID不變。③經(jīng)過②的比較處理后再廣播給其它鄰近簇首節(jié)點。直到所有簇首都加入該樹為止,層次路由樹建立完成。2.2.5節(jié)點鏈的建立當簇內(nèi)結(jié)構(gòu)和簇間路由建立起來以后,就開始進行穩(wěn)定的數(shù)據(jù)傳輸。首先是簇內(nèi)數(shù)據(jù)傳輸:在簇內(nèi)利用建簇時形成的節(jié)點鏈,結(jié)合PEGASIS協(xié)議的令牌傳遞機制,每個周期的初始簇首把令牌先傳遞給節(jié)點鏈一端的端節(jié)點,從端節(jié)點開始,將收集到的數(shù)據(jù)和自身的剩余能量傳遞給鏈中的下一個鄰節(jié)點,鄰節(jié)點將收到數(shù)據(jù)與自身的采集的數(shù)據(jù)進行數(shù)據(jù)融合后,將數(shù)據(jù)和令牌發(fā)給它的下一個鄰節(jié)點,直到簇首。然后簇首再將令牌發(fā)給節(jié)點鏈的另一端的端節(jié)點,過程和上面一樣。簇首把從兩邊收到的數(shù)據(jù)融合后再轉(zhuǎn)發(fā)給父節(jié)點。本輪結(jié)束后,之后每一輪選取簇內(nèi)剩余能量最大的節(jié)點成為鏈首,也即當輪的簇首,直到下一個周期的簇重組。其次是簇間數(shù)據(jù)傳輸:層次路由樹中的中繼節(jié)點不進行數(shù)據(jù)融合,只進行數(shù)據(jù)轉(zhuǎn)發(fā),直至數(shù)據(jù)到達基站。網(wǎng)絡(luò)中節(jié)點在發(fā)送完數(shù)據(jù)后就進入休眠狀態(tài),以節(jié)省能量。2.3整合平臺-能量特性,有以下幾種方式EBLP協(xié)議的核心算法描述如下:①計算最優(yōu)簇首數(shù)CNopt。②根據(jù)簇首的個數(shù)計算簇首間的最短距離CHLmin。③對于每一個傳感節(jié)點:If(滿足小于T(n)&&與另一個簇首的距離大于CHLmin){向其它節(jié)點廣播成為候選簇首的消息CHcand_MSG;并加入候選簇首集合SETch_cand;If(同時收到別的節(jié)點發(fā)來的CHcand_MSG消息){比較其能量值,比自己能量大的節(jié)點加入集SETch_cand;}找出集合SETch_cand中能量最大的節(jié)點向其它節(jié)點廣播成為簇著的消息CH_MSG;并加入簇首集合SETch;If(集合SETch中節(jié)點數(shù)達到最優(yōu)簇首數(shù))轉(zhuǎn)到④;}④對于非簇首節(jié)點:If(收到消息CH_MSG){根據(jù)收到的消息信號的強弱向相應(yīng)的簇首發(fā)送加入簇的消息JOIN_MSG;}If(收到簇首允許加入簇的消息ALLOW_MSG){加入對應(yīng)的簇;}If(收到簇首拒絕加入簇的消息REJECT_MSG){嘗試加入其它的簇;}對于簇首節(jié)點:If(收到消息JOIN_MSG;){If(沒有達到簇成員的最大個數(shù))向?qū)?yīng)節(jié)點發(fā)送消息ALLOW_MSG;Else向?qū)?yīng)節(jié)點發(fā)送消息REJECT_MSG;}⑤每個簇內(nèi)用貪心算法使簇內(nèi)成員形成鏈,準備數(shù)據(jù)傳輸⑥用2.2.4小節(jié)的算法建立簇首間層次路由樹,開始傳輸數(shù)據(jù)。3eblp試驗性能本文采用的仿真工具是NS2,它是一種可擴展的、容易配置的和可編程的事件驅(qū)動網(wǎng)絡(luò)工具,其源代碼公開,提供開放的用戶接口。由于文中算法是在LEACH協(xié)議的基礎(chǔ)上進行改進,所以選擇了LEACH協(xié)議能夠適用的小型網(wǎng)絡(luò)來進行對比實驗。在100m×100m的區(qū)域內(nèi)隨機部署100個傳感器節(jié)點,基站位于坐標為(50,0)的位置。在無線傳感器網(wǎng)絡(luò)中,相對于數(shù)據(jù)無線發(fā)送接收來說,節(jié)點進行運算和儲存的能耗基本可以忽略不計,所以網(wǎng)絡(luò)的生存時間主要取決于數(shù)據(jù)傳輸。設(shè)定節(jié)點初始能量為0.25J,發(fā)送和接收數(shù)據(jù)能耗為50nJ/bit。為了將數(shù)據(jù)傳輸?shù)米銐蜻h,放大電路功耗為100pJ/bit·m2,數(shù)據(jù)融合的能耗為5nJ/bit。本文分別從存活節(jié)點個數(shù)、全網(wǎng)能量消耗和延遲三個方面進行了性能對比。圖4中LEACH協(xié)議在第386輪時第一個節(jié)點死亡,在678輪時全網(wǎng)節(jié)點死亡。PEGASIS協(xié)議在第780輪時第一個節(jié)點死亡,到1093輪時全網(wǎng)節(jié)點死亡。而本文提出的EBLP協(xié)議在794輪時第一個節(jié)點死亡,到1200輪時全網(wǎng)節(jié)點死亡?？?/p>