3 拓撲維護研究現狀

　　目前專門的拓撲維護技術研究還比較少，但相關研究結果表明優化的拓撲維護能有效地節省能量并延長網絡生命周期，同時保持網絡的基本屬性覆蓋或連通。本節中，根據拓撲維護決策器所選維護策略將現有的拓撲維護技術分為基于角色輪換、基于拓撲重構和混合的拓撲維護。

　　3.1 基于角色輪換的拓撲維護

　　基于角色轉換的拓撲維護技術，通過輪換節點的角色來對拓撲進行維護。節點的角色可以從多方面描述，如睡眠/工作、簇頭/非簇頭、協調器/非協調器等，且節點的角色可以相互轉換。目前研究中，輪換的節點角色主要有兩種，一種是簇頭/非簇頭。它通過輪換簇內簇頭節點來均衡簇內能量消耗，優化局部網絡拓撲結構。LEACH是一種典型的角色輪換拓撲維護算法，通過概率隨機輪換簇頭，使網絡中節點等概率擔任簇頭，有效地節省節點能量。

　　另一種節點角色輪換為睡眠/工作，它通過調度那些未參與通信的網絡節點進入睡眠狀態來節約能量，實現延長網絡生命周期的目的。如SPAN通過維護組成骨干基礎架構的節點來保持網絡的連通和轉發能力。MESH-CDS中，最大獨立集中節點故障時，通過轉換節點角色來修復最大獨立集并維護一個連通的骨干網絡。此外，CCP通過對節點角色的輪換維護網絡拓撲的覆蓋和連通，它是一種典型和有重要影響的基于角色轉換的拓撲維護協議。其基本思想主要是通過保持一個足夠大的工作節點子集來維護網絡k-覆蓋。

　　在該算法中，每個節點扮演兩個角色，即睡眠節點或工作節點。每個節點利用ks-覆蓋規則和接收其鄰居節點的HELLO報文信息來進行本地決策以確定是否需要進行角色輪換。

　　CCP能夠將網絡配置到指定的覆蓋度與連通度，并通過角色輪換來維護網絡的覆蓋和連通，其可靈活地應用于不同的網絡環境。但是，CCP 需要較為精確的位置信息，并且當發射半徑小于感知半徑的2倍時，不能保證網絡的連通性。

　　由上可見，基于角色輪換的技術通過調度那些未參與通信的網絡節點進入睡眠狀態或選擇剩余能量多的節點擔任簇頭來維護網絡連通和覆蓋。睡眠節點或非簇頭節點消耗的能量很小，且它們比工作節點或簇頭節點的數量大得多，所以網絡的能量消耗性能十分優越。而且，通常算法僅需要局部信息，通過本地進行決策，計算復雜度低。然而，基于角色輪換的拓撲維護技術僅從局部對網絡進行維護，不能從網絡的整體出發，導致整個網絡拓撲非最優甚至不連通。

　　3.2 基于拓撲重構的拓撲維護

　　基于拓撲構建的拓撲維護技術通常周期性調用拓撲構建過程或專用的維護算法來重構網絡的拓撲。如DKM協議，當節點密度| SNS | k 時運行拓撲維護過程，有效地恢復和維護網絡的k -連通。SMSS算法中，當節點u 發現某個節點m 失效時，它將檢查m 是否為它確定的鄰節點，如果是，重新運行拓撲控制算法來維護網絡拓撲結構。

　　EETMS算法中，一旦網絡發現故障節點，觸發拓撲維護過程，并最終構建一個能量有效的局部拓撲，且其鏈路長度之和最小。EETMS 是一種典型的專門用于拓撲維護的基于拓撲重構的技術。其思想是僅利用直接的鄰居節點來響應拓撲維護過程，且節點將大部分能量花在用來估量網絡連通和尋找最小能量拓撲，而不是用于轉發數據。

　　EETMS 算法首先提出了一個判斷網絡連通的標準。在一個二維的歐幾里得空間里，網絡拓撲用一個圖G（V， E） 表示，其中V 為節點集，節點個數為n .E 為所有邊e（i， j）的集合，其中e（i， j） 表示節點i 和j 彼此互為鄰居。則網絡拓撲可用圖G 的鄰接矩陣A 表示，且矩陣的每個元素ai， j可表示為：

　　接下來，令，如果對于任意的i， j s 有， 0 i j s ，則圖G（V， E） 連通。因此，維護算法通過計算si， j 來構建一個連通的拓撲。當網絡運行中發現故障節點u ，觸發拓撲維護過程。此時故障節點u 的鄰居集為u ，節