無線傳感器網絡中lech協議的分析

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