1、第七章 無線傳感器網絡的拓撲控制技術l拓撲控制技術概述拓撲控制技術概述l拓撲控制意義拓撲控制意義l拓撲控制的設計目標拓撲控制的設計目標l功率控制技術功率控制技術l典型的層次型拓撲控制方法典型的層次型拓撲控制方法l拓撲控制中的休眠調度技術拓撲控制中的休眠調度技術路由層拓撲管理/控制MAC層拓撲控制技術是無線傳感器網絡中的基本問題。動態變拓撲控制技術是無線傳感器網絡中的基本問題。動態變化的拓撲結構是無線傳感器網絡最大特點之一，因此拓化的拓撲結構是無線傳感器網絡最大特點之一，因此拓撲控制策略在無線傳感器網絡中有著重要的意義。目前，撲控制策略在無線傳感器網絡中有著重要的意義。目前，在網絡協議分層中沒有

2、明確的層次對應拓撲控制機制，在網絡協議分層中沒有明確的層次對應拓撲控制機制，但大多數的拓撲算法是部署于介質訪問控制層（但大多數的拓撲算法是部署于介質訪問控制層（MAC）和路由層（和路由層（Routing）之間，它為路由層提供足夠的路由）之間，它為路由層提供足夠的路由更新信息更新信息i，反之，路由表的變化也反作用于拓撲控制機，反之，路由表的變化也反作用于拓撲控制機制，制，MAC層可以提供給拓撲控制算法鄰居發現等消息。層可以提供給拓撲控制算法鄰居發現等消息。拓撲控制技術概述向上提供信息向上提供信息觸發算法運行觸發算法運行拓撲控制的概念與意義概念拓撲控制（topology control）是一種協調

3、節點間各自傳輸范圍的技術，用以構建具有某些期望的全局特性（如，連通性）的網絡拓撲結構，同時減少節點的能耗或增加網絡的傳輸能力。 網絡拓撲：由傳輸媒體互連所形成的網絡節點的物理連接結構意義1、減少節點的通信負載，提高通信效率；2、減少網絡耗能，延長網絡壽命；3、輔助路由協議；拓撲控制的研究方向WSN中拓撲控制可以分為兩個研究方向：功率控制和層次拓撲結構控制。功率控制機制調整網絡中每個節點的發射功率，保證網絡連通，在均衡節點中直接鄰居數目(單跳可達鄰居數目)的同時，降低節點之間的通信干擾。層次拓撲控制是利用分簇思想，使網絡中的部分節點處于激活狀態，成為簇頭節點。由這些簇頭節點構建一個連通的網絡來處

4、理和傳輸網絡中的數據，并定期或不定期地重新選擇簇頭節點，以均衡網絡中節點的能量消耗。拓撲控制的評價指標連通性 在沒有拓撲算法前，兩個節點之間存在k條路徑，那么使用拓撲算法后，這兩個節點中也應該有存在k條路徑。覆蓋性 覆蓋問題中，最重要的因素是網絡對物理世界的感知能力。吞吐量 化簡后的網絡拓撲結構應該能夠支持與原始網絡相似的通信量。擴展性（網絡容量） 減少數據傳輸節點所能影響的鄰居節點的數量,減少節點通信的傳輸范圍,可以有效減小網絡中的沖突域,從而降低通信沖突的概率。相反，網絡中的沖突就越多,節點通信也就更容易發生數據丟包或重傳現象。魯棒性 網絡發生變化時，一些節點可能會變化它們的拓撲信息，顯然

5、，魯棒的拓撲結構只需要進行少量的調整，這樣可以避免對本地節點的重新組織而造成整個網絡的波動。實現拓撲控制的手段1、在保證網絡的連通性與覆蓋性的情況下，控制節點的發射距離，減少發射功耗，同時減少分組沖突的可能性，減少協議不必要的開銷；2、盡可能讓多的節點進行休眠，降低功耗；3、數據融合，減少分組的冗余。拓撲控制的應用效果拓撲控制的分類基于位置的拓撲控制算法-鄰近圖基本思想 設所有節點都使用最大發射功率發射時形成的拓撲圖G，按照一定的鄰居判別條件q求出該圖的鄰近圖G，最后G中的每個節點以自己所鄰近的最遠通信節點來確定發射功率。 經典的鄰近圖算法RNG、GG、DG、YG、MST、DRNG、DLMST

6、、DLSS DRNG與DLSS算法第一步:每個節點以最大的發射功率廣播HELLO信息，該信息至少包括：節點ID號、最大的發射功率、自身的位置。節點在收到HELLO信息后，確定了自己可以達到的鄰居集合。第二步：DRNG以各自的鄰居算法確定鄰居集合，DRNG以與它節點最近的鄰居節點選擇優先；而DLSS最小化了圖中所有邊的最大能量消耗, 并取單跳距離的節點作為其鄰居節點。第三步確定鄰居節點后，將發射半徑調整到最遠鄰居節點的距離，進一步通過對拓撲圖的邊進行增刪，使網絡達到雙向連通。鄰近圖算法仿真結果對比基于鄰居的拓撲控制算法基于節點度數（鄰居）的算法LMA、LMN、LINT、LILTLMA(local

7、 mean algorithm)-本地平均算法 給定節點度的上限和下限,動態地調整節點發射功率,使節點的度數始終維持在度數的上限和下限之間.這種算法利用局部信息來調整相鄰節點的連通性,從而在保證網絡連通的同時使得節點間的鏈路具有一定的冗余性和擴展性。LMN(local mean of neighbors algorithm)-本地鄰居平均算法 與LMA不一樣的地方是，LMN的鄰居節點的數目依據于所有鄰居的鄰居節點數求平均值作為自己的鄰居節點數。仿真結果顯示,這種策略在保證網絡連通的同時,通過少量的局部信息使網絡性能達到了一定程度的優化.但是,這兩種算法缺乏嚴格的理論推導.層次型拓撲結構控制 層

8、次型拓撲結構產生背景 傳感器節點在無線通信模塊在空閑狀態與收發狀態下的能耗相當，因此只有關閉其節點的無線通信模塊才能真正有效的降低非工作能耗。層次分簇就是在這一背景下產生的。層次型拓撲控制的思想與關鍵技術關鍵技術 層次分簇算法的核心是如何選擇簇頭集合，并把剩余的節點劃分到已經產生簇頭集合中。分簇的基本思想 通過簇首對簇內節點間的相關信息融合及轉發機制減少數據的傳輸量和距離,進而降低通信能量,達到網絡節能的目的。WSN中不同拓撲下的數據傳輸方式 LEACH LEACH不是一個單純的路由協議 ，它提供了一個包括分群、路由、MAC和物理層的完整的無線傳感網絡的協議框架，也可以說是一個分層路由的體系結

9、構。 LEACH協議是眾多分層協議參考的模型，稱為經典。LEACHLEACHLEACH LEACH概述 LEACH算法是一種分布式、自組織的分簇協議。運行LEACH協議的無線傳感器網絡會隨機選擇一些節點成為簇頭，并令所有節點周期性地輪換成為簇頭，使整個網絡的能量負載達到均衡。在LEACH協議中，簇頭節點將來自其成員節點的數據進行壓縮聚合，然后將聚合后的數據通過單跳的方式直接發送給基站節點，大大減小了整個網絡中的數據交換量，使得總體能耗有了大幅度的下降。LEACH算法的假設 基站是固定的而且遠離傳感器節點 網絡中的傳感器節點都是同型傳感器節點而且能量受限的 每個節點都有能力和基站通信 節點沒有位

10、置信息 對稱二進制信道 簇首可以進行數據融合LEACHLEACH工作流程工作流程 簇頭選擇算法1、確定最優簇頭數目；2、計算每個節點成為簇頭的概率； 相關參數：全網的節點數、簇 頭數目、能量評估（單節點與 全網）、當前的循環數。目的：確保所有節點大致在相同時刻耗盡 能量而停止工作， 延長網絡的生 命周期。1、簇頭進行數據融合，減少冗余數據量；2、在MAC層中使用了TDMA、CSMA、CDMA 等機制來共同處理簇內與簇間的沖突問題；3、采用選舉簇頭算法，保證WSN能量消耗平均負載到各節點上；4、采用層次路由，路由路徑選擇比較簡單，不需要存儲很大的路 由信息。LEACHLEACH優點優點LEACH

11、LEACH缺點缺點1、簇頭選舉隨機性很強，可能會出現簇頭集中在某一個區域的現象，造成簇頭分布不均勻。LEACHLEACH缺點缺點2、信息的融合和傳輸都是通過簇頭節點來進行，造成了簇頭節點能量消耗過快的問題；3、發射機和接收機必須嚴格遵守時隙的要求，避免在時間上互相重疊，然而，維持時間同步又增加了一些額外的信令通信量。節點的時間表可能會需要較大的存儲器。4、LEACH要求節點之間和節點與Sink點之間都能進行直接通信，網絡的擴展性差，對于大規模網絡而言，節點直接進行通信需要消耗大量的能量。并且采用單跳路由方式，增加了交換數據的能量。LEACHLEACH適用場合適用場合LEACH適用于周期性信息報

12、告，對延時不敏感。網絡布設范圍小，所有節點到sink的距離可以認為相等。實際應用：博物館的文物保護檢測LEACHLEACH改進改進LEACH-MH算法：相比LEACH協議，在數據穩定傳輸階段，采用簇頭多跳傳輸，增強網路的擴展性，已減少單個簇頭的能量消耗，但多跳又造成了多跳的路由選擇的耗能。LEACHLEACH改進改進LEACH-COOP算法：相比LEACH協議，引入了協同節點，在最后數據融合后，發送數據到sink節點時，采用群內選擇好的協同節點發送，以減少由于原LEACH協議中存在的由于群首節點分布不均勻造成的通信傳輸消耗大的問題。1、如何實現時間同步？2、要實現CDMA技術必須物理層支持DS

13、SS（直接擴頻序列）； 在高斯信道中當傳輸系統的信噪比下降時，可用增加系統傳輸帶寬B的辦法來保持信道容量C的不變。3、如何進行全網的能量評估？4、簇頭是否可靠與sink節點通信？5、實現睡眠與喚醒的計算 ttotal=toperation+tawaken+ttransmit; 還有很多實際問題LEACHLEACH實際的應用實際的應用HEED算法HEED-Hybrid Energy-Efficient Distributed clustering混合能量高效分布式分簇算法HEED產生背景 HEED是在LEACH算法簇頭分布不均勻這一問題基礎上而作出對LEACH協議分簇算法的改進，它以簇內平均可達

14、能量（AMRP）作為衡量簇內通信成本的標準。HEED 算法的實質 在LEACH算法基礎上，重點修改了選舉簇頭的算法。在全網時間同步的基礎上, 將節點根據當前剩余能量占初始能量的比例p 劃分為若干“等級”, 等級較高的節點率先公布自己為簇頭, 而等級較低的節點在收到簇頭廣播后加入這個簇。如果節點的剩余能量降為初始能量的1%就被除去競選簇頭的資格。 ),/max(minmaxPEECPresidentprobHEED分簇算法HEED分簇依據： 注：Cprob和Pmin是整個網絡統一的參量，合適的參數可以有效地增加算法的收斂性。Eresident/Emax代表節點剩余能量與初始化能量的百分比。 HE

15、ED協議主要依據主、次兩個參數, 分別反應能耗狀況和節點的通信代價,通過將能耗平均分布到整個網絡來延長網絡生命周期。 主參數-依賴于剩余能量,用于隨機選取初始簇頭集合, 具有較多剩余能 量的節點將有較大的概率暫時成為簇頭, 而最終該節點是否一 定是簇頭取決于剩余能量是否比周圍節點多得多。 次參數-依賴于簇內通信代價, 用于確定落在多個簇范圍內的節點最終 屬于那個簇, 以及平衡簇頭之間的負載。),/max(minmaxPEECPresidentprobHEED與LEACH分簇對比主要改進 在簇頭選擇中考慮了節點的剩余能量, 并以主從關系引入多個約束條件。實驗結果表明, HeeD分簇速度更快, 能

16、產生更加分布均勻的簇頭、更合理的網絡拓撲。LEACH簇頭分布HEED簇頭分布HEED的優缺點HEED的優點 HEED綜合地考慮了生存時間、可擴展性和負載均衡，對節點的分布更均勻。HEED的缺點 雖然考慮了節點分布的問題，但對于sink節點的附近節點的能耗過快消耗的問題還是沒有解決。還有進行能耗檢測與交換能耗信息的時候會造成很大的開銷，而且HEED算法是周期性更換簇頭的，所以能耗是相當可觀的。GAF算法 GAF - Geographical Adaptive FidelityGAF是一種基于地理位置為依據的分簇算法 GAF核心思想在各數據到數據目的地之間存在有效通路的前提下，盡量減少參與數據傳輸的節點數，從而減少用于數據包偵聽和能量開銷。GAF算法分析 GAF算法過程 第一階段： 劃分虛擬單元格 劃分根據：1、節點的位置；2、節點的通信半徑； GAF算法過程 第二階段： 選擇簇頭節點 三種狀態： 初始階段：發現 成為簇頭：活動 競爭失?。核?/p>