無線傳感器網絡中的拓撲控制

 收稿日期：2008-01-16；

修回日期：2008-03-24

基金項目：國家自然科學基金資助項目(60704046 60725312)；遼寧省工業通信與控制系統重點實驗室資助項目



作者簡介：卞永釗（1976-），男，博士研究生，主要研究方向為無線傳感器網絡的網絡管理、拓撲控制(bian_yz@sia.cn)；

于海斌（1964-），男，研究員，博導，主要研究方向為智能控制系統、網絡化技術等;

曾鵬（1976-），男，研究員，碩導，主要研究方向為協議工程、無線傳感器網絡.

(1.中國科學院 沈陽自動化所 沈陽110016; 2.中國科學院 研究生院 北京100039)

摘要：拓撲控制是無線傳感器網絡研究中的核心問題之一，它對于提高網絡生存周期、降低通信干擾、提高MAC和路由協議、保證網絡連通和覆蓋質量、提高網絡服務等具有重要意義。闡述了拓撲控制技術研究的進展，首先描述了拓撲控制及其方法、評價標準，然后從平面網絡、層次型網絡拓撲控制介紹了一些代表性的研究工作，并指出了這些工作存在的不足，最后總結了研究現狀中存在的問題以及拓撲控制研究的發展方向。

關鍵詞：無線傳感器網絡; 拓撲控制； 功率控制； 支配集； 成簇算法

中圖分類號：TP309

文獻標志碼：A

文章編號：1001-3695(2008)10-3128-06

Topology control for wireless sensor networks

BIAN Yong-zhao1，2 YU Hai-bin ZENG Peng1

(1.Shenyang Institute of Automation Chinese Academy of Sciences Shenyang 110016 China;

2.Graduate School Chinese Academy of-Sciences Beijing 100039 China)

Abstract:Topology control is one of the fundamental problems in wireless sensor networks. It is of great importance for prolonging network lifetime reducing radio interference increasing the efficiency of MAC and routing protocols ensure the-qua-lity of connecting and coverage increasing the network services and so on. This paper described the topology control problem and its methods criterion of estimation firstly then made an introduction of representative research efforts from two aspects homogeneous and non-homogeneous networks respectively and pointed out the defects of those efforts. Finally summarized existing problems open issues and research trends.

Key words：wirelss sensor networks(WSN); topology control; transmit power control; dominating set; clustering algorithm

0引言

無線傳感器網絡是一種新興的網絡，一般具有大規模、自組織、隨機部署、環境復雜、傳感器節點資源有限、網絡拓撲經常發生變化的特點[1]。無線傳感器網絡的這些特點決定了拓撲控制在無線傳感器網絡研究中的重要作用，同時這些特點也使得它的拓撲控制研究具有挑戰性。首先，拓撲控制是一種重要的節能技術；其次，拓撲控制保證網絡覆蓋的質量和連通質量；另外拓撲控制能夠降低通信干擾、提高MAC協議和路由協議的效率，為數據融合提供拓撲基礎；拓撲控制能夠提高網絡的容量、可靠性、可擴展性等其他性能。總之拓撲控制對網絡性能具有重大的影響，因而對它研究具有十分重要的意義。

本文提到的拓撲控制是指控制網絡拓撲結構，網絡拓撲結構由活動節點的子集和進行直接通信的活動鏈路決定。拓撲控制算法以圖G=(V，E)代表網絡。其中：V是網絡中所有節點的集合，當且僅當v1與v2之間有直接通信時，邊(v1，v2)∈EV2存在，將它變換到圖T＝(VT，ET)，可以得到VT∈V，ET∈E。

圖G代表原始網絡，為了能從圖G計算出變化后的圖T，拓撲控制算法有以下幾種常用的方法：

a)減少活動節點的數量(VTV)。例如可以利用網絡的冗余部署特性，周期性地關閉剩余能量較少的節點，激活其他節點來代替被關閉的節點。

b)可以控制活動鏈路集或鄰節點集。如果無須使用網絡中的所有鏈路，那么可以剔除一些鏈路，將通信限制在重要鏈路中。

如果網絡是同構的，即平面網絡，控制節點的鄰節點集只需不與某些節點通信即可。在無線傳感器網絡中選擇鄰節點最適合的方法就是控制節點的信號發射范圍，也就是采用功率控制或者采用自適應的功率調整方法。圖1和2給出了原始的網絡拓撲和功率控制之后的拓撲結構。

拓撲控制也可以采用第二種方法，即重新安排活動鏈路或鄰節點，形成一個層次型的網絡拓撲結構，并假設處于上層的節點具有特殊的功能。

如選擇某些節點作為骨干節點，只保持骨干節點之間的連接，其他節點的連接都指向骨干節點，所以骨干節點就形成了一個支配集(dominating set)：子集DV，V中的所有節點要么在D中，要么是節點d∈D的單跳鄰節點(v∈V:v∈D∨d∈D:(v，d)∈E)。支配集節點之間相互通信以及支配集與其鄰節點之間可以進行通信，這樣能夠保證網絡的連通性。

另一種與支配集相關但略有不同的思想就是將網絡劃分成簇(clusters)。簇是包括原始網絡中所有節點的節點集的子集，每個簇中有簇首(cluster heads)，它是簇的代表，每個簇內的節點距離簇首一般只有一跳。如果使簇的數量最小，就相當于尋找最大獨立集(independent set)(存在子集CV，使v∈V-C:c∈C:(v，c)∈E，且C中沒有兩個節點在邊E-c1，c2∈C:(c1，c2)E上相交)。在這樣的分簇型的網絡中，簇首負責與簇內節點之間的通信，同時簇間連接也是通過簇首的通信來實現的，這樣就可以保證整個網絡的連通性。圖3和4給出了采用骨干節點控制和簇結構控制之后的拓撲結構。

1拓撲控制的評價標準

拓撲控制要保證在一定的網絡連通質量和覆蓋質量的前提下，一般以延長網絡生存周期為主要目標，兼顧通信干擾、網絡延遲、負載均衡、可靠性、可擴展性等其他性能，形成一個優化的拓撲結構。無線傳感器網絡是與應用相關的，不同的應用其設計目標不盡相同，采用的拓撲結構控制手段也不盡相同。以下提出一般拓撲控制算法的幾個評價指標。

1)連通性拓撲控制不能使連通圖G變成非連通圖。也就是說，如果G中的節點u與v之間有一條(可能是多跳)路徑，那么在T中也應該有這樣一條路徑(顯然，不一定是同一條路徑)。如果至少要去掉k個節點才能使網絡不連通，那么就稱網絡是k-連通的，或者網絡的連通度為k。拓撲控制要保證網絡是連通的(即至少1-連通)，這是拓撲控制的基本要求。

2）覆蓋率覆蓋率可以看成是對傳感器服務質量的度量。覆蓋問題可以分為區域覆蓋、點覆蓋和柵欄覆蓋[2]。區域覆蓋研究對目標區域的覆蓋(監測)問題；點覆蓋研究對一些離散的目標點的覆蓋問題；柵欄覆蓋研究運動物體穿越網絡部署區域被發現的概率問題。相對而言，對區域覆蓋的研究較多。如果目標區域中的任何一點都被k個傳感器節點監測，就稱網絡是k-覆蓋的，或者稱網絡的覆蓋度為k。一般要求目標區域的每一個點至少被一個節點監測，即1-覆蓋。

3）吞吐量化簡后的網絡拓撲結構應該能夠支持與原始網絡相似的通信量，尤其是在有大量突發事件時。設目標區域是一個凸區域，每個節點的吞吐率為λ bps。在理想情況下有下面的關系式[3]：

λ≤(16AW/πΔ2L)(1/nr)bps

其中：A是目標區域的面積；W是節點的最高傳輸速率；π是圓周率；Δ是大于0的常數；L是源節點到目的節點的平均距離；n是節點數；r是理想球狀無線電發射模型的發射半徑。由此可以看出，減小發射半徑或減小工作網絡的規模，在節省能量的同時可以在一定程度上提高網絡的吞吐能力。

4)魯棒性當在原始圖G中的鄰近關系發生變化時(如節點運動、失效或無線信道特性發生變化)，一些節點的拓撲信息可能會發生變化。顯然魯棒的拓撲結構只需進行少量的調整就可以避免對本地節點重新組織而造成整個網絡的波動。

5）算法總開銷對于資源有限的節點來說，算法本身的開銷應該小一些，如附加信息少、計算量小；另外分布式實現也是一個必要條件。

在當前的無線傳感器網絡中，連通性、覆蓋性和擴展因子可能是除了必不可少的分布式性質和低開銷量之外的拓撲控制算法最重要的特性。除此之外，拓撲控制還要考慮網絡的生存周期、網絡中的干擾和競爭、延遲、拓撲性質、負載均衡等其他方面，拓撲控制的各種設計目標之間有著復雜的關系，這些關系也是拓撲控制研究的重要內容。

2平面網絡中的拓撲控制——功率控制

在平面網絡中，所有的節點都是同構的，具有同樣的硬件、同樣的能力，完成同樣的任務。在平面網絡中拓撲控制最基本的方法是控制與一個節點通信的鄰節點集。而這個問題與控制節點的發射功率有著密切的關系，所以一般稱為功率控制。

目前，對平面網絡的拓撲控制研究方法主要分為兩類：a)概率分析的方法，在節點按照某種概率密度分布的情況下，計算使拓撲滿足某些性質(一般是連通性、覆蓋率)所需要的最小發射功率和最小鄰節點個數；b)計算幾何方法，以某些幾何結構為基礎構建網絡拓撲，以滿足某些性質。

2.1概率分析方法

研究人員針對無線傳感器網絡的特點提出了幾何隨機圖理論。假設網絡采用單位圓盤圖模型(unit disk graph，UDG)以及在給定面積為A的區域內節點是均勻分布的，這個假設模型正好對應于幾何隨機圖理論。

文獻[4]采用了一種基于幾何隨機圖的類似算法來確定圖是k-連通的概率表達式，如果節點的發射功率大到足以保證圖的最小度數至少為k(概率很大)，那么有大量節點的圖就是k-連通的。Bettstetter利用這個結論推導出了一個圖中最小節點度的概率公式:

P(G是連通的) ≈1-∑k-1l=0(ρπr2)l/l!·e-ρπr2

(1)

其中：r為節點的發射半徑；ρ為節點的密度(假設節點在給定區域內均勻分布)。

Li等人[5]也研究過k-連通問題，提出了當發射半徑r在k＞0時滿足nπr2≥ln n+(2k-1) ln ln n-2 ln k+2α且n足夠大時，節點數為n的網絡(k+1)連通的概率至少是ee-α。

如果網絡中的節點并不是均勻分布的，尤其是稀疏網絡，那么幾何隨機圖理論就無法應用，但是研究人員對此也做了一些工作。Santi等人[6]假設n個節點(節點數固定，也可能變化)在d維部署區域R＝[0，l]d內隨機均勻部署，對于節點密度ρ=n/ld沒有限制，他們的目標是使所有節點都具有最小半徑發射半徑r，使得到的圖是連通的。

對一維d=1的情況，可以證明，如果rn≥2l ln l，那么圖是連通的概率很高；如果rn≤l ln l，圖是非連通的概率很高。對于d=2，3的情況，給出了如下結論：

對于某常數k＞0，設rdl=kld ln l，r=r(l)＜＜l和n=n(l)＞＞1。如果k＞d×2d dd/2(或k=d×2ddd/2及r=r(l)＞＞1)，那么圖是連通的概率很高。

設r=r(l)＜＜l和n=n(l)＞＞1。如果f d∈O(ld)，那么圖是非連通的概率很高。

還有其他一些平面網絡的研究結果，Kubisch等人[7]描述了兩種將鄰節點數控制在一定數量內的分布式算法，并通過仿真實驗評價了它們的性能。Liu等人[8]研究了關于節點有不同最大發射范圍的問題，得到了非連接的信息，采用了一個分布式拓撲結構控制算法來最小化最大功率，保持了每個節點的可達性。Royer等人[9]研究了功率控制和移動性的關系，功率控制與Ad hoc路由協議之間的相互作用，即Ad hoc按需距離矢量(AODV)的性能，證明了不存在最優密度，但是密度會隨著節點的運動而增大。當前大部分研究把功率控制看做與網絡中其他層是無關的。Cruz等人[10]研究了跨層問題，提出了一個結合連接調度表和功率控制的算法。

2.2計算幾何方法

如果能夠獲得節點之間的距離或它們的相對位置的信息，那么可以有效地實現將網絡拓撲變得稀疏。利用計算幾何方法構建鄰近圖的方法能夠實現拓撲控制。經常使用的幾何結構有以下幾種：

a)最小生成樹(MST)。文獻[11]提出了一種基于本地信息的最小生成樹的構造法，其思想是每個節點會收集它的鄰節點，然后構造(如使用prim算法)這些節點的最小生成樹，將能量代價作為連接權重(代價相同的連接由加入的節點表示符作為間斷符來區分)。下一步的關鍵就是在化簡后的拓撲中保留這些對應于最小生成樹中直接鄰節點的邊。這種構造法保持了原圖的連通性，而且每個節點的最大度數是6。它能限制雙向連接，也比較容易加入功率控制。而且，平均節點度數比較小，接近理論界限。

b)Gabriel圖(Gabriel graph，GG)。在傳輸功率正比傳輸距離的平方時，GG是最節能的拓撲。MST是GG的子圖，GG也滿足連通性。 在文獻[12]中介紹了GG的分布式構造法。一個節點必須要對于它的所有鄰節點都測試邊的圈定義是否還成立，如果所有的節點都與它們的鄰節點的位置相交換，那么這是很容易做到的。

c)相關鄰近圖（relative neighbor graph，RNG），很容易用本地算法實現。如果原始圖G是連通的，那么它也是連通的。其稀疏程度在MST和GG之間，連通性也在MST和GG之間，優于MST，沖突干擾優于GG，是兩者的折中。RNG易于用分布式算法構造。

Li等人[13]提出的DRNG和DLMST是兩個具有代表性的基于鄰近圖理論的算法。基于鄰近圖的功率控制算法的基本思想是：設所有節點都是用最大發射功率發射時形成的拓撲圖G，按照一定的鄰居判別條件求出該圖的鄰近圖G′，每個節點以自己所鄰近的最遠節點來確定發射功率。DRNG是基于有向RNG的，DLMST是基于有向局部MST的。DRNG和DLMST能夠保證網絡的連通性，在平均功率和節點度等方面具有良好的性能。

平面網絡的功率控制算法除了上面兩類基本類型之外，研究人員也提出了一些其他算法，如分布式公共功率協議COMPOW[14]，K-NEIGH協議[15]等。

分布式公共功率協議COMPOW。簡單地將功率控制與路由協議相結合的解決方案。其基本思想是：所有的傳感器節點使用同樣的發射功率，在保證網絡連通的前提下，將功率最小化。COMPOW在各個功率層上建立路由表，在功率Pi層上，通過使用功率Pi交換HELLO消息建立路由表RTPi，所有可達節點都是路由表中的表項。COMPOW選擇最小的發射功率Pcom，使得RTPcow和RTPmax具有相同的表項。其中Pmax是最大發射功率。于是整個網絡都使用公共的發射功率Pcom。在節點分布均勻的情況下，COMPOW具有較好的性能，但是一個相對孤立的節點會導致所有的節點使用很大的發射功率。另外這個理論雖然實現起來相對簡單，但是它需要保留所有潛在節點的路由表，這一點使得它基本上不適合無線傳感器網絡。

K-NEIGH協議的思想是使每個節點的鄰節點數保持k個或接近于k個。這個協議是分布式的，基于節點間的距離是估計的，而且需要總量為2｜V｜的信息交換量。這種方法是節點用大發射功率發布它們的信標，收集它們觀察到的鄰節點的信息，按距離對鄰節點進行分類，并計算能夠互相到達的k個最近的鄰節點，這樣每個節點用最小的發射功率就能到達剛才計算的所有鄰節點。在這個協議的設計中，需要注意的是要等待足夠長的時間隨機地喚醒節點，以及適當解決潛在的非對稱鏈路的問題。

3層次型網絡中的拓撲控制結構

研究無線傳感器網絡拓撲結構的另一種方法是在網絡節點中形成一種層次關系，構成一個層次型的網絡。目前主要有兩種研究手段，即采用支配集的層次型網絡和采用分簇結構的層次型網絡。

3.1采用支配集的層次型網絡

在網絡中選出一些虛擬骨干節點組成虛擬骨干網，這些節點又叫做支配集，即如果V中所有節點或在D中，或是某個節點d∈D的單跳鄰節點(v∈V:v∈D∨d∈D:(v，d)∈E)，這里D就是支配集。而這個支配集在某種程度上應該盡量小，這也是最小支配集問題(minimum dominating set，MDS)。

文獻[16]介紹了兩種集中式的例子。a)生成樹結構。主要思想是像生成樹型結構一樣構造支配集，迭代地給樹加入舊節點和邊，直到所有的舊節點都被覆蓋為止。這個算法用節點的顏色來表示：白色節點表示沒有被處理，黑色節點屬于支配集，灰色節點表示受控集。b)先構造一個不一定連通的支配集，然后在下一個階段，把集合內的所有節點連接在一起。把非連通的支配集連通起來也叫做尋找斯坦納樹(Steiner tree)問題。

生成樹的分布式算法可以由文獻[17]介紹的分布式算法來實現。從本質上來說，就是所有灰色節點發現它們的兩跳鄰節點，并確定每個節點能夠得到的最大收益，然后分布式地選擇最大收益，就可以確定下一個黑色節點了。

TopDisc(topology discovery)算法[18]來源于圖論的思想，是基于最小支配集問題的經典算法。它利用顏色區分節點狀態，解決骨干網拓撲結構的形成問題。在TopDisc 算法中，由網絡中的一個節點啟動發送用于發現鄰節點的查詢消息，查詢消息攜帶發送節點的狀態信息。隨著查詢消息在網絡中傳播，TopDisc 算法依次為每個節點標記顏色。最后，按照節點顏色區分出骨干網節點，并通過反向尋找查詢消息的傳播路徑在骨干網節點之間建立通信鏈路。每個骨干網節點管理與自己相鄰的普通節點。

TopDisc 算法中提出了兩種具體的節點狀態標記辦法，分別稱為三色算法和四色算法。這兩種算法的區別在于尋找骨干網節點的標準不一樣，所以最后形成的拓撲結構也有所不同。

3.2采用簇結構的層次型結構

前面介紹了通過把一些節點作為骨干節點形成支配集，把層次結構引入了網絡。另一種形成層次結構的想法是把一些節點標記為具有特殊的功能，如控制其鄰節點等，這樣就形成了簇，這個具有特殊功能的節點就叫做簇首。這種分簇方法的優點與骨干節點類似，但是更著重于本地資源的優化使用，能夠屏蔽網絡高層的動態特性，使高層協議更具有可擴展性，另外簇首還能夠進行本地數據融合、壓縮任務。

LEACH(low energy adaptive clustering hierarchy)[19]算法是一種自適應分簇算法，它的執行過程是周期性的，每輪循環分為簇的建立階段和穩定的數據通信階段。在簇的建立階段，相鄰節點動態地形成簇，隨機產生簇首；在數據通信階段，簇內節點把數據發送給簇首，簇首進行數據融合并把結果發送給匯聚節點。由于簇首需要完成數據融合、與匯聚節點通信等工作，能量消耗大，LEACH算法能夠保證各節點等概率地擔任簇首，使得網絡中的節點相對均衡地消耗能量。

GAF算法[20]是基于地理位置的拓撲算法，但是它沒有考慮節點的剩余能量，而是隨機地選擇節點作為簇首。該算法中的簇首承擔更多的數據處理和通信任務，消耗的能量相對較大，因此，簇首應該選擇剩余能量較多的節點。P.Santi等人[21]提出了一種GAF改進算法，他設計了兩種不同的簇首選擇機制，并詳細分析了簇首節點產生后的網絡運行方式，同時驗證了改進的GAF算法對網絡生存時間的影響。與GAF算法相比，GAF改進算法除了要求每個節點知道自己的ID以及屬于哪個單元格外，還要求同一單元格中的節點保持時間同步。GAF改進算法有兩種簇首選擇機制，即完全型簇首選擇算法和隨機型簇首選擇算法。虛擬單元格建立起來后，每個節點都知道自己所屬的虛擬單元格。節點根據已知本單元格相關信息的多少決定采取哪種簇首節點選擇機制。

HEED[22]的基本思想是：根據對作為第一因素的剩余能量和作為第二因素的簇內通信代價的綜合考慮，周期性地通過迭代的辦法實現分簇。HEED用最小平均可達功率(AMRP)作為當某個節點被選為簇首時的簇內通信代價的度量。

HEED不依賴于網絡的規模，通過O(1)次迭代實現分簇。迭代每一步的時間要足夠長，使得節點能夠收到來自鄰節點的消息。初始時，每個節點要確定在一跳范圍內的鄰節點的集合，計算并廣播AMRP，計算自己成為臨時簇首的初始概率CHp。

HEED綜合考慮了生存時間、可擴展性和負載均衡，對節點的分布和能力也沒有特殊要求，雖然HEED的執行并不依賴于同步，但是不同步卻會嚴重影響分簇的質量。

4層次型拓撲結構與功率控制相結合

層次型方法(骨干網節點控制、成簇控制)和平面網絡中功率控制都是影響無線網絡拓撲的有效方法。現在的一個研究方向就是將這兩種機制結合在一起。

1)基于引導信號的功率控制[23]

這是一種早期的方法，簇首用這種方法來進行功率控制，與在蜂窩網絡中進行的功率控制相類似。在建立初始的分簇結構之后，簇首在引導信號和數據通信中使用功率控制。如果基于這些引導信號，所有節點都加入了同一個簇，那么就可以使用引導信號功率控制來控制簇的成員。數據通信功率控制用于保證遠處節點的誤碼率足夠低以及對附近節點能高效地發送信息；它也能防止出現非常差的發射條件。功率控制的主要優點是它在簇首中是集中式的，這簡化了完全分布式的功率控制問題。

2)Ad hoc網絡設計算法

Ad hoc網絡設計算法(Ad hoc network design algorithm，ANDA)[24]允許簇首通過功率控制來控制簇的大小，并且導出了一些具體的規則以盡可能延長網絡的生存期。假設網絡的生存期主要由簇首決定，因為簇首負責收集、轉發感知信息，完成最主要的任務，能量消耗應該在簇首間均衡。

這個方法的基本假設是:a)普通節點和(預選出的)簇首的位置是已知的；b)通信量在普通節點間均勻分布；c)簇首的生存期與它的初始能量成正比，與crα+dn成反比。其中：r是簇首覆蓋區域的半徑；n是簇內成員的個數；α是路徑損耗系數；c、d是常數。算法的最佳目標是使所有簇首的生存期最長，或者相應地使簇首中的最小生存期最長。

這種求最大值的問題是一個優化問題，用決策變量來描述簇j中普通節點i的成員身份。其中也隱含著所需的發射半徑。對于靜態網絡來說，用一個簡單的貪婪算法就能求得最優解：將節點i分配給有最長生存期的簇首，對所有節點重復這一操作。對于動態網絡來說，需要一個額外的重新配置過程，而且無法保證求得的是最優解，但其實際性能還不錯。

3)CLUSTERPOW

前面討論了在節點分布均勻的情況下，COMPOW算法具有較好的性能，但是，一個相對孤立的節點會導致所有的節點使用很大的發射功率，所以在節點分布不均勻的情況下，它的缺點是明顯的。針對這種缺點，改進了COMPOW協議，提出了CLUSTERPOW協議[25]。它的基本思想是簡單地假設一組離散的發射功率值，如1、10、100 mW。在每個功率值處，簇都是獨立形成的，而且對于每個功率值都有單獨的路由表。如果用最小功率就能保證到達目的節點，那么就發送數據，一旦數據進入了包含目的節點的最小功率簇后，功率值就會被降低。在CLUSTERPOW中，分簇是隱含的，且無須任何簇首節點，分簇通過給定功率層的可達性來實現，分簇的層次由功率的層次數來實現，分簇是動態的、分布的。

對較大的初始發射功率進行替換是很有用的。為了實現這個目標，在相關文獻中也描述了隧道式CLUSTERPOW協議。在這種情況下，為了避免無限地路由循環，必須將用于以最小功率進行路由的中間節點的地址也裝入數據分組中。

5其他一些啟發式算法

還有一些其他的拓撲控制算法，并不是嚴格地符合利用骨干節點/支配集計算或分簇原理的，它們都是通過打開或關閉某些節點來影響圖的拓撲結構。顯然，源節點和數據匯聚節點總是活動的。

1)基于地理位置的拓撲算法(GAF)

Xu等人在文獻[20]中提出了基于地理位置的拓撲算法，它的思想是將區域分成非常小的矩形，使每個矩形中的節點都能與相鄰矩形中的節點進行通信。如果某些節點滿足某些條件，那么這些節點從網絡的高層(如路由層)來看可以看做是等價的。當一個節點休眠時，可以激活它的等價節點來替代。

假設節點都知道它們自己的位置，所以這些節點能很容易地構成這樣的等效矩形，并在它們自己的矩形中確定節點。這些節點之間互相合作確定休眠模式，按順序參加路由協議。Xu等人證明了使用這種方案，Ad hoc路由協議的能量效率能被提高40％～60％。

2)STEM算法

在GAF(或其他有等價節點概念的方法)的基礎上，可以加入稀疏拓撲和能量管理(sparse topology and energy management)協議[26]。

STEM是節點喚醒算法，在STEM算法中，節點需要采用一種簡單而迅速的節點喚醒方式，保證網絡通信的暢通和較小的延遲。該算法又包括兩種不同的機制，即STEM-B和STEM-T。它使節點在整個生命周期中大多數時間內處于睡眠狀態。節點的睡眠周期、部署密度以及網絡的傳輸延遲之間有著密切的關系。GAF關閉節點，但是卻保持網絡的轉發容量；虛擬喚醒信道的STEM機制提高了能量效率，卻也增大了路徑建立的延遲。Schurgers等人[26]建議將這兩種方法結合起來，即把STEM算法應用于GAF算法中等價的節點集合之中。

3)可變的自適應拓撲算法(ASCENT)

加州大學洛杉磯分校的Cerpa等人[27]提出了一種著重于保證數據通路暢通的ASCENT算法。保留一定數量的節點作為路由節點，其余節點轉入休眠狀態，但是節點不僅根據附近節點的通信量來確定是否成為活動節點，還要考慮丟包率指標。如果某個節點發現丟包嚴重，就向鄰節點發出求救信息；收到求救信息的節點主動成為工作節點，幫助鄰節點轉發數據包。但是，ASCENT并不能保證網絡的連通性，因為它只是通過丟包率來判斷連通性的。事實上，當網絡不連通時，它是無法檢測和修復的。ASCENT也不能保證能量的均勻消耗。

節點可以關閉自己，但是必須周期性地進入被動狀態來監聽幫助請求。對網絡性能的監測依賴于拓撲控制，這是ASCENT算法區別于其他算法的地方，但是，它有大量需要優化的參數。

4)在傳感器覆蓋率的基礎上關閉節點

與傳統的Ad hoc網絡不同的是，對WSN來說，只保證網絡的連通性是不夠的。WSN的主要任務是感知和測量它周圍的環境。為了完成這項任務，無論是否需要連通性(可能是弱連通的)，觀測區域都必須被足夠多的節點覆蓋。通常，WSN的感測覆蓋率問題是一個很難解決的問題。

Tian等人[28]指出要關閉節點，就必須保證節點的感測覆蓋區域會由其他節點覆蓋。只有這樣的節點才有資格休眠一段時間。

假設節點知道它們的位置和它們的感測區域，在與它們的鄰節點交換信息后(如在循環的開始)，節點確定它自己的感測區域是否被它的鄰節點所覆蓋，這只是一個簡單的地理問題。如果是，節點就聲明它可以休眠，并通知它的鄰節點，然后進入休眠狀態。

如果所有可以休眠的節點同時進入休眠狀態并立即關閉自己，就有出現盲點的危險。如果兩個鄰節點均可以休眠，根據假設，它們認為另一個節點會保持活動(在另一邊剩余的未覆蓋區域會由其他更遠的節點覆蓋)，就會發生這種情況。為了避免這種情況，休眠資格的通告是用通用的隨機補償算法進行隨機延遲的。當節點接收到這樣的信息時，它從它的鄰節點列表中將這個很快要進入休眠狀態的節點刪除，并重新評估它自己的休眠資格。

這個算法基于節點是冗余部署這一事實的；否則不可能有節點可以休眠。這是一個簡單而有效的方法，并且考慮了WSN的實際特性。

6存在的問題及進一步需要研究的內容

上面總結了當前無線傳感器網絡拓撲控制研究中最具代表性的工作，同時也指出了存在的問題。

1)拓撲控制定義問題

現在對拓撲控制還沒有一個清晰的定義，在文獻[29]中，P.Santi提出了一個非正式的定義：拓撲控制是為了生成一個具有某種屬性(如連通性)的網絡，協調網絡中的節點決定它們傳輸范圍的一種技術，同時能夠減少節點的能量消耗和(或)增加網絡的容量。作者區分了一般的節點節能技術、節點功率控制技術和拓撲控制技術的區別，同時又認為成簇技術是控制網絡拓撲的一種手段，因為成簇過程中節點的發射功率是固定的，所以成簇技術并不是一種拓撲控制技術。現在大多數人認為拓撲控制技術是在保證一定的網絡屬性(如連通性、覆蓋性等)的前提下，以延長網絡生存時間為目標，采用各種技術使網絡形成一個優化的網絡拓撲，功率控制和層次型網絡控制都是手段。但是如何衡量是優化的網絡呢？度量網絡的性能指標是什么？目前平面網絡的功率控制以及層次型網絡控制的研究一般都是獨立進行的，不同的應用可能有不同的優化目標，性能指標也不同，不太可能給出一個通用的定義。

2)拓撲控制在協議棧中的位置

拓撲控制與協議棧的其他層關系密切，與物理層、鏈路層、網絡層和傳輸層交互作用。由于無線傳感器網絡中的協議棧中的各層之間的界限也已經模糊，那么拓撲控制到底位于哪一層？傳統認為[29]拓撲控制位于MAC層之上、路由層之下，它與路由層、MAC層之間的關系最為密切；但是也有人認為拓撲控制分散在各層[30]，所有這些都給協議棧設計帶來了困難。因此拓撲控制與MAC、路由、數據融合、數據存儲以及數據傳輸等其他方面結合的研究極大拓寬了拓撲控制的研究領域。

3)缺乏對拓撲控制算法的有效度量

拓撲控制要提高網絡的各種性能，包括覆蓋質量、能量消耗、連通質量、干擾、延時、魯棒性等。但是目前還沒有對這些性能的有效度量的方法。一個實用的拓撲控制技術其實應該綜合考慮這些性能指標，但到目前為止還沒有這樣的研究。有人提出了網絡生存周期，但是網絡生存周期沒有一個統一的定義，實際上網絡生存周期是一個綜合的抽象的性能指標。如何有效地度量網絡的性能，也就是如何有效度量控制算法的性能，這些也是拓撲控制要研究的內容。

由此看來，無線傳感器網絡中的拓撲控制還有很多問題需要研究，這些問題構成了拓撲控制研究的內容，這些研究內容之間又是相互制約、密不可分的。

7結束語

本文簡要地描述了無線傳感器網絡拓撲控制的研究現狀以及其中存在的一些問題。現在拓撲控制研究的發展趨勢是以實際應用為背景，多種機制結合使用，強調網絡拓撲控制的自適應性和魯棒性，在保證網絡連通性和覆蓋度的前提下，提高網絡的通信效率，最大限度地節省能量來延長整個網絡的生存時間。但是目前的研究還普遍存在著模型過于理想化，對網絡性能的綜合考慮比較少，研究結果缺乏足夠的說服力，沒有考慮實際應用中的困難。拓撲控制還有許多問題有待進一步研究，特別是要根據實際應用情況探索更加實用的拓撲控制技術。以實際應用為背景、多種機制相結合、綜合考慮網絡各種性能將是拓撲控制研究的發展趨勢。

參考文獻：

[1]AKYILDIZ I F SU W SANKARASUBRAMANIAS Y，et al.A survey on sensor networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[2]THAI M T WANG F DU D Z. Coverage problems in wireless sensor networks:designs and analysis[J].International Journal of Sensor Networks 2008，3(3):191-200.

[3]GUPTA P KUMAR P R. The capacity of wireless networks[J].IEEE Trans on Information Theory，2000，46(2):388-404.

[4]BETTSTETTER C. On the minimum node degree and connectivity of a wireless multihop network[M]. Los Alamitos: IEEE Computer Society Press，2002:80-91.

[5]LI Xiang-yang WAN Peng-jun WANG Yu et al. Fault tolerant deployment and topology control in wireless networks[C]//Proc of the 4th ACM Symposium on Mobile Ad hoc Networking and Computing. New York:ACM Press，2003:117-128.

[6]SANTI P BLOUGH D M. The critical transmitting range for connectivity in sparse wireless Ad hoc networks[J].IEEE Trans on Mobile Computing 2003，2(1):25-39.

[7]KUBISCH M KARL H WOLISZ A，et al. Distributed algorithms for transmission power control in wireless sensor networks[C]//Proc of IEEE Wireless Communications and Networking(WCNC).New York: IEEE Press 2003:558-563.

[8]LIU Ji-lei LI Bao-chun. Distributed topology control in wireless sensor networks with asymmetric links[C]//Proc of IEEE Globecom Wireless Communications Symposium. San Francisco:[s.n.] 2003.

[9]ROYER E M，MELLIAR-SMITH P M，MOSER L E.An analysis of the optimum node density for Ad hoc mobile networks[C]//Proc of IEEE International Conference on Communications.Helsinki:[s.n.] 2001:857-861.

[10]CRUZ R L SANTHANAM A V. Optimal routing link scheduling and power control in multi-hop wireless networks[C]//Proc of the 22nd Annual Joint Conference on IEEE Computer and Communications Societies. New York: IEEE Press 2003:702-711.

[11]LI Ning，HOU J C，SHA L.Design and analysis of an MST-based topology control algorithm[J]. IEEE Trans on Wireless Communications 2005，4(3):1195-1206.

[12]KARP B KUNG H T. GPSR:greedy perimeter stateless routing for wireless networks[C]//Proc of the 6th International Conference on Mobile Computing and Networking. New York: ACM Press，2000:243-254.

[13]LI Ning HOU J C. Topology control in heterogeneous wireless networks:problems and solutions[C]//Proc of IEEE Conference on Computer Communications. New York:IEEE Press 2004:232-243.

[14]NARAYANASWAMY S KAWADIA V SREENIVAS R S，et al. Power control in Ad hoc networks: theory architecture algorithm and implementation of the COMPOW protocol[C]//Proc of European Wireless Conference. 2002:156-162.

[15]BLOUGH D M LEONCINI M RESTA G，et al. The K-neigh protocol for symmetric topology control in Ad hoc networks[C]//Proc of the 4th ACM International Symposium on Mobile Ad hoc Networking and Computing. New York: ACM Press 2003.

[16]GUBA S KHULLER S. Approximation algorithms for connected dominating sets[J].Algorithmica，1998，20(4):374-387.

[17]DAS B BHARGHAVAN V. Routing in Ad hoc networks using minimum connected dominating set[C]//Proc of International Conference on Communication(ICC). 1997:376-380.

[18]DEB B BHATNAGAR S NATH B. A topology discovery algorithm for sensor networks with applications to network management DCS-TR-441[R].Comden NJ:Rutgers University 2001.

[19]HEINZELMAN W R CHANDRASAN A BALAKRISHNAN H. An application-specific protocol architecture for wireless micro-sensor networks[J]. IEEE Trans on Wireless Communications 2002，1(4):660-670.

[20]XU Ya HEIDEMANN J ESTRIN D. Geography-informed energy conservation for Ad hoc routing[C]//Proc of the 7th Annual International Conference on Mobile Computing and Networking. New York: ACM Press 2001:70-84.

[21]SANTI P SIMON J. Silence is golden with probability:maintaining a connected backbone in wireless sensor networks[C]//Proc ofthe 1st European Workshop on Wireless Sensor Networks. Berlin:Springer，2004:106-121.

[22]YOUNIS O FAHMY S. HEED: a hybrid energy-efficient distributed clustering approach for Ad hoc sensor networks[J].IEEE Trans on Mobile Computing，2004，3(4):660-669.

[23]KWON T J GERLA M. Clustering with power control[C]//Proc of the 4th IEEE Military Communications Conference. Atlantic City:IEEE Press，1999:1424-1428.

[24]CHIASSERINIC F CHLAMTAC I MONTI P et al.Energy efficient design of wireless Ad hoc networks[C]//Proc of the 2nd IFIP Networking Conference. London: Spring-Verlag 2002:376-386.

[25]KAWADIA V KUMAR P R. Power control and clustering in Ad hoc networks[C]//Proc of the 22nd Ammual Joint Conference on IEEE Computer and Communications Societies. New York: IEEE Press，2003:459-469.

[26]SCHURGERS C TSIATSIS V GANERIWAL S et al. Topology management for sensor networks: exploiting latency and density[C]//Proc of the 3rd ACM International Symposium on Mobile Ad hoc Networking Colllputing. New York: ACM Press 2002:135-145.

[27]CERPA A ESTRIN D. ASCENT: adaptive self-configuring sensor networks topologies[J].IEEE Trans on Mobile Computing 2004，3:272-285.

[28]TIAN Di GEORGANAS N D. A coverage-preserving node scheduling scheme for large wireless sensor networks[C]//Proc of the 1st ACM Workshop on Wireless Sensor Networks and Applications. New York: ACM Press 2002:32-41.

[29]SANTI P. Topology control in wireless Ad hoc and sensor networks[J].ACM Computing Surveys 2005，37(2):164-194.

[30]KAWADIA V KUMAR P R. A cautionary perspective on cross-layer design[J].IEEE Wireless Communications，2005，12(1):3-11.