摘 要： 拓撲維護對無線傳感器網絡的運行至關重要，它旨在通過輪換節點角色、調用拓撲構建或維護算法來修復、重構當前的拓撲結構以提高網絡的生命周期。首先對拓撲維護進行了定義，描述了拓撲維護的設計目標，并設計了一個拓撲維護通用模型。然后闡述了拓撲維護技術的研究進展，并對其中有代表性的算法進行了比較分析。最后指出了目前拓撲維護研究中存在的問題及其發展趨勢。

　　無線傳感器網絡由于具有低功耗、低成本以及分布式和自組織等特點已被廣泛應用于軍事國防、工農業控制、環境監測、生物醫療和搶險救災等領域。通常，一個無線傳感器網絡由成百上千傳感器節點組成，每個節點具有感知當前環境、通過廣播與鄰近節點進行通信以及對收集的信息執行本地計算的能力。但是，這些能力對每個節點來說都很有限，尤其是節點的能量受限嚴重限制了網絡的生命周期，從而影響了網絡的服務質量和進一步應用。因此，近幾年來，許多研究人員對無線傳感器網絡的節能方面進行了大量的研究，從擁塞控制到數據壓縮，從睡眠調度到拓撲控制。目的是盡可能多的節省能量，最大化網絡生命周期。

　　拓撲控制作為無線傳感器網絡的一種關鍵節能技術，通常在保持網絡重要特性如連通和覆蓋的前提下改變、簡化或優化網絡的拓撲來節省能量。而且，拓撲控制形成的良好網絡拓撲能夠提高路由協議和MAC 協議的效率。然而，拓撲控制通常被視為一個單一過程，它并未包括對網絡拓撲的維護，這影響拓撲控制算法的分類。目前的分類都局限于如何構建網絡的拓撲結構，而忽略拓撲控制中的拓撲維護。

　　雖然對拓撲維護進行了簡單定義，并根據目標優化拓撲構建的時間將拓撲維護技術分為靜態、動態和混合拓撲維護。但文中并未對拓撲維護進行系統闡述，而對拓撲維護的定義又不嚴謹，對拓撲維護技術的分類也與當前研究現狀不符，因為現有研究中基本上沒有文中所提到的靜態和混合拓撲維護算法或協議。因此，為了更深入的對無線傳感器網絡中的拓撲維護技術進行研究，本文從拓撲維護定義及模型，拓撲維護設計目標，以及當前的研究現狀和存在的問題與發展方向等方面對拓撲維護進行了闡述。第1 節描述了無線傳感器網絡拓撲維護基礎，主要給出了拓撲維護全新的定義，并指出拓撲維護設計目標。第2 節設計了一個拓撲維護通用模型，并對模型中的觸發標準和維護策略進行了詳細描述。第3 節總結了目前有關拓撲維護研究工作，并進行了比較分析。第4 節分析了當前研究中的不足，并指出拓撲維護技術的發展方向。最后對全文進行了總結。

　　1 拓撲維護基礎

　　無線傳感器網絡拓撲控制由兩部分組成，即拓撲構建和拓撲維護。一旦建立起最初的網絡優化拓撲，網絡開始執行它所指定的任務。由于網絡任務所包含的每一個行為如感測、數據處理和傳輸等都需要消耗能量，因此隨著時間的推移，當前的網絡拓撲不再處于最優運行狀態，因此需要對其進行維護使其重新保持最優或接近最優狀態。

　　1.1 拓撲維護定義

　　無線傳感器網絡的拓撲控制可以看作一個重復的過程，如圖1 所示。首先，對所有無線傳感器網絡都有一個拓撲初始化階段。在該階段，每個節點用其最大發射功率發射來建立初始拓撲。在初始化階段后，通過運行不同的算法或協議來對初始拓撲進行優化，并最終構建一個優化拓撲，該階段稱之為拓撲構建。一旦拓撲構建階段建立起優化網絡拓撲，拓撲維護階段必須開始工作。

　　在拓撲維護階段，實時監測當前拓撲狀態，并在適當的時候觸發拓撲恢復或重構過程。從圖1 中可見，在網絡的生命周期內，拓撲維護周期運行，直到網絡死亡。目前，對拓撲維護進行定義的文獻很少，文獻［8］對拓撲維護進行了簡單定義，指出“拓撲維護是指當網絡當前工作的拓撲結構不是最優化的拓撲結構時，及時通過修復、切換或重構新的網絡拓撲，使網絡達到預先設定的性質，延長網絡的生命期”。

　　該定義沒有指出拓撲維護運行的時間、所采取的維護方式，特別是定義中提到使拓撲達到或接近最優以及達到預先設定的性質，卻沒有指出是哪個具體階段的最優或性質，因為隨著網絡的運行，網絡的最優狀態和性質也在發生變化。所以，本文對拓撲維護進行了比較嚴謹的定義，即拓撲維護是一個周期性的過程，在每個周期中它由不同的觸發標準（如時間，能量，節點故障等）觸發，通過盡可能多地輪換節點角色或重新運行拓撲構建過程或調用專用維護算法來修復或重構網絡拓撲，均衡網絡能量消耗，使新的拓撲成為當前最優或接近當前最優狀態，并最終延長網絡的生命周期。

　　1.2 設計目標

　　拓撲維護和其它傳感器網絡技術一樣，其主要目的是延長網絡的生命周期。此外，傳感器網絡被構建用來實現某些任務，如執行傳感和傳輸傳感數據，因此一個或多個服務質量目標如保持傳感覆蓋以及保持網絡連通等也通常被考慮。

　　而且，無線傳感器網絡的應用不同則導致其底層網絡的拓撲維護設計目標不同或目標優先次序不同。因此，本文接下來只介紹拓撲維護主要考慮的設計目標。

　　（1）網絡生命周期

　　網絡生命周期已經以不同方式被定義，如基于節點數、基于傳感覆蓋以及網絡連通以及可擴展的網絡生命周期。

　　拓撲維護是延長網絡生命周期十分有效的技術，如拓撲維護協議SPAN和CCP 通過關閉冗余節點并維持一個節點子集處于工作狀態來提高無線傳感器網絡的生命周期。然而，最大化網絡生命周期是一個十分復雜的問題，它一直是拓撲維護研究的主要目標。

　　（2）覆蓋和連通

　　覆蓋和連通是無線傳感器網絡拓撲維護的基本問題，拓撲維護在對原有的優化拓撲進行恢復、切換或重構的過程中，必須保持原有拓撲的覆蓋或連通。

　　（3）安全和故障容忍

　　拓撲維護過程中，一些傳感器節點由于能量耗盡、物理損壞或環境干擾可能會失靈或發生故障，而這些傳感器節點的失效并不影響拓撲維護的整體任務。如文獻［12］中提出一個故障容忍的自組織方法來維護一個覆蓋和連通的骨干網絡。此外，無線傳感器的實際應用中存在各種類型的惡意行為和攻擊［13］，因此，安全也是拓撲維護的一個重要目標。

　　（4）能量效率和收斂時間

　　與無線傳感器網絡其它功能一樣，拓撲維護算法必須是能量有效的。也就是說拓撲維護算法應該具有低的計算復雜度和低的報文開銷。此外，在拓撲維護過程中，當前的拓撲將被一個新的拓撲取代，因此在新拓撲被激活之間有一個轉換時間，該時間應該盡可能小。

　　（5）能量均衡和可擴展性

　　拓撲維護技術應該盡量在網絡的所有節點間均衡地分布能量消耗。另外，部署在興趣或目標區域的傳感器節點可能成百上千甚至上萬。拓撲維護協議或算法應該能在不同數量級節點的網絡中運行。

　　2 拓撲維護模型

　　目前，并沒有文獻對拓撲維護模型進行描述。為了更好的理解拓撲維護的運行過程及其特點，本文設計了一個通用的拓撲維護模型，如圖2 所示。從圖中可見，拓撲維護是一個周期的過程，每個周期中從網絡的當前拓撲開始，經過拓撲維護過程生成一個優化的拓撲，周期運行，直到網絡死亡。

　　從上圖可見，每個拓撲維護周期，經由觸發器和決策器。

　　其中觸發器主要根據設計的觸發標準如時間、能量或節點故障等來觸發拓撲維護過程。決策器用來選擇拓撲維護策略。

　　接下來對該模型進行詳細描述。

　　（1）觸發器

　　觸發器負責周期地觸發當前網絡拓撲的維護過程，其對拓撲維護的性能具有重要的影響。因為如果提前觸發，則由于頻繁運行拓撲維護協議或算法而消耗不必要的能量，而滯后觸發，則將導致網絡可能以次優甚至不連通狀態運行，降低甚至無法實現網絡的服務質量。常見的觸發標準有：

　　時間：網絡運行一段時間后觸發拓撲維護，該時間的大小通常是固定且預先定義，通常由一個定時器來完成。

　　SPAN基于時間來觸發網絡中協調器節點的更新過程，從而實現骨干網絡的拓撲維護。

　　能量：鑒于無線傳感器設備的能量限制，當節點的能量級別低于某個閾值時觸發拓撲維護是很有必要的。LPH算法中，當節點的剩余能量E（i）低于平均剩余能量Eavr 時，觸發簇內拓撲維護過程。CLTC算法中，當簇頭節點的能量降到門限值M 時，觸發簇內拓撲維護過程。而Poly算法中，當網絡的整體能量降低10%時觸發拓撲維護過程。

　　節點故障：當網絡中一個或一些節點故障時，觸發拓撲維護。如SMSS算法中，當節點u 發現某個節點m 故障時，它將檢查m 是否為其確定的鄰節點，如果是則重新運行拓撲構建算法來維護網絡拓撲結構。EETMS算法中，一旦網絡發現故障節點，觸發局部拓撲維護過程。

　　網絡密度：采用網絡的節點度或者一些重要節點的節點度來觸發拓撲維護過程。AFECA提出的自適應精度節能算法使用鄰居密度來觸發拓撲維護過程。

　　此外，這些觸發條件也可任意組合用來觸發拓撲維護過程，如基于能量和節點故障，或者時間和能量等。此外，其它的網絡參數也可作為觸發標準，如鏈路失效、頻繁丟包以及擁塞和長路由路徑等。

　　（2）決策器

　　決策器主要確定采用何種策略來維護當前的網絡拓撲結構，它是拓撲維護的核心。拓撲維護策略可以分為兩種，一種是基于角色輪換的拓撲維護策略，也就是說通過對網絡中節點的角色-如睡眠/工作、簇頭/非簇頭等進行切換來節約能量，實現延長網絡生命周期的目的。另一種是基于拓撲重構的拓撲維護策略，其實質是運行拓撲構建階段的算法或專門的拓撲維護算法與協議來維護網絡拓撲結構。

　　在基于角色輪換的拓撲維護策略中，首先要明確網絡中每個節點所能扮演的角色。每個節點的角色遷移與拓撲維護協議或算法特點和設計密切相關，確定節點所處角色的因素包括節點密度、位置、通信流量、丟包率、時間以及外部環境條件等。如節點當前為角色1，當某個事件發生，則節點進行相應測試以決定是否進入角色2還是繼續處于角色1.

　　而基于拓撲重構的拓撲維護策略中，主要是重新調用拓撲構建階段的算法或專門的拓撲維護算法。因此，調用算法的頻率是關鍵。一旦觸發器觸發拓撲維護過程，拓撲維護策略則應該綜合考慮網絡的相關性能，決定是否調用相關算法或協議，以均衡網絡能量消耗并最終延長網絡生命周期。

　　此外，決策器還可根據網絡運行情況在不同的階段采用不同的維護策略來維護當前的網絡拓撲結構。無論是基于角色轉換還是基于拓撲重構的拓撲維護技術，決策器還負責對生命周期的監測。也就是說，在網絡的生命周期內，決策器根據維護策略周期性地對網絡拓撲結構進行維護，而一旦網絡的生命周期結束，決策器停止維護過程，并宣告網絡死亡。

　　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 ，節點數u m .EETMS能夠維護網絡的連通，并確保鏈路長度之和最小。但算法中需要構建故障節點的鄰接矩陣，并根據該矩陣來計算網絡的連通。在高密度網絡中，需要大量的存儲空間和高的計算復雜度。此外，算法中并沒有描述故障節點檢測機制，無法知道拓撲維護算法的觸發頻率。

　　總之，基于拓撲重構的拓撲維護技術可能需要多次動態運行拓撲構建或維護算法，通常需要更多的時間和能量消耗。然而，拓撲構建過程在它每次運行時通常選擇最優或接近最優拓撲，從而導致生成比基于角色轉換拓撲維護技術更好的網絡拓撲結構。

　　3.3 混合的拓撲維護

　　混合的拓撲維護技術結合了基于角色輪換和拓撲重構的拓撲維護。該類拓撲維護技術周期性地采用節點角色轉換和拓撲重構策略。首先，混合的方法采用角色轉換的維護方法對網絡的局部拓撲進行維護，實現網絡一部分（如一個簇）的優化。隨著網絡的運行，作為數據轉發的骨干網絡能量消耗較快，造成網絡內的能量消耗不均衡，于是混合技術采用拓撲重構的維護技術來重構整個網絡的拓撲，兩種方法周期性地交替運行，有效地均衡網絡能量消耗。DFTM采用角色輪換的方法對局部拓撲進行維護，而采用拓撲重構的方法來對整個網絡拓撲進行維護。

　　可見，混合的拓撲維護技術可以使用基于節點角色輪換無法使用的資源，而且網絡持續的時間比基于拓撲重構方法要長，因為輪轉過程比一個完整的新構建過程消耗的能量少。但是，混合技術由于觸發條件的選擇，一個性能嚴重下降的拓撲可能持續很長一段時間，在它到達拓撲重構恢復點前，這將影響連通和覆蓋的服務水平。

　　3.4 拓撲維護算法分類

　　拓撲維護算法分類可以從許多方面來進行，如可以根據設計目標將拓撲維護分為確保覆蓋、連通的拓撲維護，故障容忍和安全的拓撲維護，能量消耗均衡的拓撲維護等。此外，很難將目前研究的設計目標和設計要素分開，導致分類可能并沒有精確地反映設計者的最初意圖。為了盡量避免該問題，本文根據第2 節設計的拓撲維護模型對現有的拓撲維護算法進行分類，如表1 所示。

　　4 存在的問題和發展趨勢

　　從以上可見，無線傳感器網路拓撲維護研究取得了一些成果，但其仍然存在一些問題。此外，隨著無線傳感器網絡的實際應用，如何確保拓撲維護的安全性以及如何有機地與其它層互相融合將是拓撲維護算法的主要發展方向。

　　（1）缺乏實際的拓撲維護實施

　　盡管許多研究機構致力于本文提到的拓撲維護技術研究，且許多的理論和基于仿真的證據表明拓撲維護算法或協議能有效減小網絡的能量消耗從而延長網絡的生命周期，但是迄今為止，很少有實際的網絡實施來證明拓撲維護事實上能被用于實現這些目標。

　　（2）未能量化拓撲維護頻率

　　拓撲維護算法要考慮拓撲重構產生的報文開銷和優化拓撲的質量之間的權衡，一般情況下，產生一個高質量的優化拓撲，就需要頻繁執行拓撲維護協議。另一方面，每一次執行拓撲維護協議將導致相當數量的報文開銷。目前，很少有研究仔細考慮兩者之間的權衡關系。

　　（3）安全的拓撲維護

　　目前的大部分拓撲維護協議通常假設傳感器部署在一個可信的、非敵對的環境中，并沒有考慮到節點內部或外部攻擊的影響。而無線傳感器的實際應用尤其是商業和軍事應用，存在各種類型的惡意行為和攻擊，對手可以利用使用的拓撲維護算法來對網絡發起攻擊。因此，必須采取相應的安全策略，提高拓撲維護算法的魯棒性，使其能防御各類攻擊。

　　（4）跨層的拓撲維護

　　無線傳感器網絡的生命期優化目標涉及從底層硬件到上層應用的所有環節， 因此僅通過拓撲構建甚至拓撲維護往往難以達到最理想效果，需要拓撲控制（構建與維護）與其它上下層協議緊密耦合協同。因此，拓撲維護的設計也必須兼顧各層協議的特點，以便在無線傳感器網絡體系結構中扮演好承上啟下的重要角色。

　　5 結論

　　本文對無線傳感器網絡拓撲維護研究現狀進行了綜述，并對當前研究中存在的普遍問題進行了分析和概括。從目前的研究現狀來看，拓撲維護研究主要以基于角色輪換和拓撲重構為主，已經提出了CCP、EETMS等算法。但目前的研究還存在模型理想化、缺乏實際的拓撲維護實施以及未能量化拓撲維護運行頻率和缺乏算法性能有效度量等問題。

　　總之，拓撲維護算法已經取得了初步的研究成果，但專門面向拓撲維護的研究還太少。而且，目前的研究未能考慮實際應用所面對的如環境地形、噪音干擾、惡意攻擊等諸多因素。可見，拓撲維護還有許多問題需要進一步研究，特別是需要探索面向實際應用的安全和跨層的拓撲維護技術。