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

摘 要:討論了拓撲控制的目標，利用隨機圖理論研究了無線傳感器網絡拓撲控制的模型及代表性算法;基于網絡結構的不同，分析和比較了無線傳感器網絡中各種拓撲控制機制的特征;深層剖析了無線傳感器網絡拓撲控制與連通、調度之間的關系;最后對拓撲控制亟待解決的問題進行了總結和展望。

關鍵詞:無線傳感器網絡; 拓撲控制; 隨機圖; 連通; 調度

中圖分類號:TP393文獻標志碼:A

文章編號:1001-3695(2009)09-3214-05

doi:10.3969/j.issn.1001-3695.2009.09.004

Survey of topology control in wireless sensor networks

GAN Cong-hui， ZHENG Guo-qiang， TANG Sheng-yu

(Electronic Information Engineering College， Henan University of Science Technology， Luoyang Henan 471003， China)

Abstract:As a vital supporting technology in WSNs， topology control can reduce redundancy and prolong network lifetime on the premise of network coverage and connectivity. This paper discussed the target of topology control， studied topology control models in WSNs and typical algorithms with the application of random graph theory， made comparative study of the characteristics of topology control mechanism on the basis of different classifications of network structure， and explored the relations among topology control， connectivity and scheduling in WSNs. Finally， it summarized the present situation and problems which still remained to be solved.

Key words:wireless sensor networks(WSNs); topology control; random graph; connectivity; scheduling

無線傳感器網絡(WSNs)是由隨機部署在監測區域內的大量體積微小，由計算、存儲、通信功能的傳感器節點組成，這些節點通過無線通信的方式形成多跳的自組織網絡[1]。WSNs集數據采集、數據處理和數據通信三大功能于一體，是21世紀最重要的技術之一，其巨大的應用價值和發展前景引起了軍事界、工業界和學術界的廣泛關注[2]。

WSNs的重要特征是資源受限，因此如何高效地利用網絡的有限資源來延長網絡壽命就成為研究WSNs的主要目標。拓撲控制作為WSNs重要的支撐技術，主要作用是在介質訪問控制層(MAC)和路由層之間，為減少通信干擾提高MAC協議效率提供基礎，為路由層提供足夠的路由更新信息;而路由表的變化反作用于拓撲控制機制，MAC層也可以為拓撲控制算法提供鄰居發現等消息。拓撲控制同時為網絡時間同步、數據融合及目標定位等關鍵技術提供支撐，因此良好的拓撲結構在WSNs中至關重要，成為實現有限資源利用最大化的必要條件。

目前，WSNs拓撲控制逐漸成為研究的熱點，但目前看來，對拓撲控制全方位的分析和評述還很少，尤其是對拓撲控制與連通、調度之間關系的研究大多局限在單方面或僅泛泛而談，沒有深層次挖掘三者間“點、線、面”的關系。本文的研究無疑為推動拓撲控制的進一步發展奠定了一定的基礎。

1 拓撲控制的目標

整體來說，WSNs拓撲控制的目標就是通過調整節點的發射功率、節點間的層次關系或工作狀態等技術來滿足網絡結構的需要或特定應用場景的要求。在保證一定的連通度和覆蓋的前提下，拓撲控制以提高能量使用效率、延長網絡生存時間為核心目標，同時兼顧降低網絡干擾、避免隱藏終端或暴露終端、提高網絡吞吐量等因素。

WSNs是與應用高度相關的，不同的應用系統對拓撲結構的要求不盡相同。從簡化路由、提高MAC協議效率來講，生成的拓撲應具備稀疏性和對稱性;從消息轉發的可達性和可擴展性的角度來講，拓撲應具備平面性和局部性;從實現節點間互相通信和健壯性的要求考慮，拓撲結構必須具備連通性和容錯性。另外，拓撲控制算法在執行報文交互時必然會消耗節點能量，而節點本身的計算能力、存儲能力和通信能力有限，算法復雜必然會帶來實現上的困難和物理成本的增加，所以在設計拓撲時要結合場景的實際需要，生成的拓撲應在稀疏性、對稱性、連通性等這些錯綜復雜的關系中折中，并結合算法本身的實現代價綜合考慮。

2 基于隨機圖理論的拓撲模型與控制算法

2.1 拓撲模型

隨機圖理論在信息科學中被廣泛地應用，UDG、RNG和MST等都是基于隨機圖理論的經典拓撲模型，很多的拓撲結構都是在它們的基礎上演變而來的。從連通和抗干擾的角度對拓撲模型進行分類，如圖1所示。

1)單位圓圖(UDG)

假定網絡中N個節點構成了二維平面中的節點集V，所有節點都以最大功率工作時所生成的拓撲稱為UDG (unit disk graph) 。若所有節點最大的傳輸范圍為1，無線節點在平面中就構成了一個UDG，當且僅當圖中每對節點間的歐氏距離dis(u，v)≤1時，兩個節點之間才有鏈路相連。UDG的連通性是網絡能夠提供的最大連通性，因此，任何拓撲控制算法生成的拓撲都是UDG的子圖[3] 。

2)準規則單位圓圖(QUDG)

假設V、R是兩個空間平面的節點集，且VR，設參數d∈[0，1]，則對稱的歐氏圖(V， E)被稱為以d為參數的準規則單位圓圖(QUDG)。圖中對任意α，β∈V，若|αβ|≤d，則(α，β)∈E;若|αβ|>1，則(α，β)E。在實際應用中，節點的發射功率會因為硬件或環境等各種原因而變化，所以QUDG是比UDG更接近實際的拓撲模型[4]。

未經拓撲控制算法處理的UDG是非平坦的，非平坦圖邊的非頂點交叉現象將給信道帶來干擾。為了對其作平面化處理，簡化拓撲結構，許多UDG的近似子圖算法被提了出來[5]。其中最具代表性的有Gabriel圖(GG)、相關鄰近圖(RNG)和最小生成樹(MST)。

3)Gabriel圖(GG)

在二維歐氏空間中，V為節點集，w，u，v∈V，w≠u≠v。連接GG中任意兩個節點u和v，則以邊d(u，v)為直徑、通過節點u和v的圓內不包含其他任何節點。如果(dis(u，v))2≤min((dis(w，u))2+(dis(w，v))2)，w≠u≠v，則說明d(u，v)為GG的一條邊。在傳輸功率正比傳輸距離的平方時，GG是最節能的拓撲模型。

4)相關鄰近圖(RNG)

在二維歐氏空間中，V為節點集，任意兩個節點間的邊長小于或等于u、v分別與其他任意一節點的距離的最大值，即歐氏距離dis(u，v)≤max(dis(w，u)， dis(w，v))，w，u，v∈V，w≠u≠v。若d(u，v)為RNG的一條邊，則在分別以點u或v為圓心，以dis(u，v)為半徑的兩個圓R1和R2的交集I內不能有其他節點[6] ，如圖2所示。RNG是由GG產生的，RNG稀疏程度和連通性均介于MST與GG之間，優于MST，且沖突干擾優于GG，易于用分布式算法構造。

5)最小生成樹(MST)

MST是保持圖連接所需的滿足最小權值的鏈路子集。MST是RNG的子圖，其特征是連通但不形成回路，任意兩個節點均可以相互通信。每個節點出現在樹上，鏈路總長度最小。構造MST有兩種主要算法，即Kruskal和Prim算法。Kruskal算法總是選擇剩余權值最小的邊加入最小生成樹;Prim算法則通過任意將節點加入最小生成樹，同時僅將權值更小的邊加入。

6)其他常用的拓撲模型

除了上面討論過的幾種模型外，Yao圖(YG)、Voronoi tessellation(VT)和Delaunay triangulation(DT)也是常用的模型。YG分很多扇區，節點在扇區內選擇最近的鄰居進行通信，具有簡單的分布式結構，節點的度較高;VT首先識別網絡冗余節點，然后計算出可被關閉的冗余節點，最后由工作節點構建覆蓋集;DT中點集V的一個三角剖分T只包含Delaunay邊，具有最大化最小角、惟一性(任意四點不能共圓)等特性。

2.2 拓撲控制算法

基于鄰近圖的功率控制算法是拓撲算法中非常重要的一類，其基本思想是假設傳感器節點以最大的發射功率發射時形成的拓撲結構G，按照一定的鄰居判斷條件得出G的鄰近圖G′，每個節點又以與相距自己最遠的鄰居節點之間的距離來確定其發射功率，從而在建立起一個連通網絡的同時使能量消耗最低。關于WSNs的基于鄰近圖的拓撲控制算法已有一些代表性的研究，較為典型的算法有直接相關鄰近圖(DRNG)和直接本地最小生成樹(DLMST)[7]，兩者分別是以RNG和MST為理論基礎的拓撲算法。

DRNG是一種基于方位信息的RNG分布式算法。DRNG算法思想是若節點u和v的距離dis(u，v)小于節點u的發射半徑Ru，而且不存在節點i同時滿足w(u，i)< w(u，v)，w(i，v)< w(u，v)和dis(i，v)≤Ri時，則認為v是u的鄰居節點。其中w表示權重，如圖3所示。

DLMST算法實質上等價于求解可達鄰居子圖的最小生成樹。首先節點u確定自己可達鄰居子圖G，然后將u與所有可達鄰居的邊所對應的權重函數w(u，v)排序，從小到大依次取出w(u，v)對應的邊，直到u與G中每個節點均可以直接或間接連通，而與u直接連通的鄰居節點構成u的鄰居節點集。

為了實現拓撲控制，在DRNG和DLMST算法中節點需要獲取有關鄰居節點的一些信息，因此在算法初期有鄰居節點信息收集階段，每個節點以自己最大的發射功率廣播包含ID和位置信息的Hello消息，每個節點根據接收到的Hello消息來確定自己的可達鄰居集合N。

DRNG和DLMST充分考慮到了網絡的連通性，并對節點間的邊進行必要的增刪操作使優化后的拓撲保持雙向連通。另外，在平均功率和節點度等方面兩者也具有較好的性能。

3 拓撲控制機制

WSNs拓撲結構具有稠密部署的特點，在拓撲控制之前，所有節點以最大發送功率工作。這樣，一方面會造成網絡中每個節點的無線信號覆蓋的節點數目過多，使無線信號沖突頻繁，直接影響到傳感器節點的無線通信質量，降低整個網絡的吞吐率;另一方面，節點有限的能量將被無線通信模塊快速消耗，降低了網絡的壽命;同時，在生成的網絡拓撲中將存在大量的邊，從而導致網絡拓撲信息量過大，路由計算復雜，浪費寶貴的計算資源。因此，在保證網絡強連通和覆蓋的前提下通過一定的拓撲控制降低節點的發送功率，避免節點之間無線信道的頻繁沖突，減少網絡拓撲信息，從而降低節點能耗、提高網絡吞吐量，有效地延長了網絡壽命[8]。

目前，圍繞拓撲機制進行的相關研究大致分為兩類:a)通過控制節點睡眠或活動狀態來控制活動節點數量;b)通過控制某些鏈路的使用狀態來減少通信鏈路的數量。從路由的方面考慮，網絡拓撲應保持全局連通，使任意兩個傳感器節點間存在可通信鏈路。為了實現數據轉發過程中節點或區域的能量平衡，網絡中能量相對充足的節點間的鏈路在路由時被優先選擇。從MAC協議效率角度來看，網絡拓撲的連通冗余度過高，節點的信號覆蓋范圍可能過大，會造成隱藏或暴露終端問題，從而引發數據通信碰撞，繼而導致數據重傳或串擾及其帶來的不必要的能耗。具體來說，拓撲控制機制可以從平面網絡、支配集和分簇的網絡結構三方面分別討論，如圖4所示。

3.1 平面網絡的拓撲控制

平面網絡結構是WSNs中最簡單的一類拓撲結構，其所有節點的地位相同、功能對等，每個節點均包含相同的MAC、路由、管理等協議。平面網絡拓撲結構較為簡單、易維護，具有較好的健壯性。平面網絡沒有中心管理節點，所以節點都能夠與sink通信，數據包通過一跳或多跳轉發至sink，通常其拓撲是通過功率控制或網內節點協同啟發機制來產生。功率控制機制的思想是調整網絡中傳感器節點的發射功率，在保證網絡連通和均衡節點的單跳可達鄰居數目的同時，降低節點間的無線通信干擾。網內節點協同啟發機制的思想是節點根據自身周邊環境的變化進行自主控制以及與鄰居節點進行交互的機制，當有通信要求時能夠及時自動醒來并喚醒鄰居節點，形成數據轉發的拓撲結構。下面介紹平面網絡拓撲控制的典型算法。

1)COMPOW算法

COMPOW算法[9]是一種典型功率控制算法。該算法中節點采用同構方式，所有節點具有統一的傳輸功率，并且該功率是能確保整體網絡連通的最小功率。雖然最小傳輸功率在降低能耗的同時提升了網絡容量、減少了通信干擾，但也約束了COMPOW的適用范圍，尤其當網內節點分布不均勻時節點被迫使用較大功率，這也是該算法的致命弱點。

2)K-Negih算法

K-Negih算法[10]是一種典型的基于鄰居集合和距離估測技術的分布式算法。K-Negih算法思想是節點首先以最大功率廣播ID，并根據接收到的廣播報文運用距離估測技術進行由近至遠的排序，因而確定K個最近節點置入鄰居集，最后交互鄰居集合，對單向鏈接實施刪除或增加以滿足鏈接的雙向對稱性。K-Negih算法具有連通性、節點度受限、算法執行簡單等良好特性。

3)RM算法

Rodoplu等人[11]提出了一種基于閉包圖的功率分配算法RM，它是一種基于節點地理位置信息的拓撲算法。算法思想是在每個節點周圍確定一個稱做enclosure的區域，在enclosure區域中的節點稱為該節點的真正鄰居。通過計算轉發區域和衡量轉發代價，以低能耗實現網絡連通。RM算法是一種強連通、稀疏性、低能耗的高效拓撲算法，但是算法本身的計算復雜度較高，給網絡帶來較大的開銷。

4)CBTC算法

LI Li 等人 [12]提出了基于方向的拓撲控制算法CBTC。該算法的思想是節點首先發送Hello消息，并收集其他節點的回復信息;然后節點獨立調節發射功率，以保證在每α角度內至少有一個鄰居節點;最后刪除冗余鏈路以維持拓撲的對稱性。該算法能達到全局連通、對稱性、節點度受限等特點的拓撲，但CBTC未能對低能耗節點采取保護措施，忽略了節點在路由中的能耗不平衡問題。

5)STEM算法

STEM算法是一種典型的啟發式拓撲控制方法，采用低占空比的節點喚醒機制，并使用監聽和數據通信雙信道。算法思想是節點周期性地進入監聽階段，探測是否有鄰居節點要發送數據，當其想與其他節點通信時，就作為主動節點先向目標節點發送喚醒包，然后再進行通信。STEM算法節點的喚醒速度能滿足應用的需要，可以適用于類似環境監測等應用，但該算法在實際應用中需在節點的睡眠周期、部署密度以及通信延遲等之間進行權衡。

6)連通性覆蓋問題

網絡連通性覆蓋問題常常是與網絡拓撲相互聯系的，其所解決的是如何保證監測區域內所有節點形成的監測范圍可以滿足應用要求，同時節點都可以向sink轉發數據，而不會產生網絡分割。WSNs許多的重要的技術如拓撲控制、目標定位目標跟蹤等都是依賴于網絡有效的連通性覆蓋范圍。網絡連通性覆蓋控制的主要思想是利用節點的冗余性，通過節點狀態轉換、密度控制等機制，在不影響網絡連通和覆蓋的條件下讓一部分節點處于活動狀態，承擔數據采集轉發等任務，使另一部分節點處于睡眠狀態，以減少網絡能量開銷。Zhang Hong-hai等人[13]提出當節點密度有限時，節點通信半徑r需不小于節點感應距離d的兩倍，即r≥2d是連通性覆蓋的充分必要條件。Xue Feng等人[14]證明了在k-覆蓋和k-連通情況下，且r≥2d時，一個凸區域的k階覆蓋必然包含k-連通。Gao Yong等人[15]證明了如果要覆蓋某個節點的整個監測區域，該節點需要3~5個一跳的鄰居節點。

3.2 分簇網絡的拓撲控制

在WSNs中，為了節約無線通信模塊的能耗，可以將網絡拓撲劃分為相連的簇區域，并依據一定的機制選擇部分節點作為骨干節點。骨干節點的通信模塊處于工作狀態，并由其構建連通網絡來處理和傳輸數據，讓非骨干節點處于睡眠狀態并屬于骨干節點管理，從而大幅度降低空閑狀態時偵聽對節點能量的消耗，進而延長網絡壽命。分簇算法融合了聚類管理的理念，彌補了空閑狀態節點無謂能耗過高的缺陷。分簇的網絡拓撲有利于分布式算法的應用，適合大規模部署的網絡。LEACH、HEED等都是很具代表性的分簇拓撲算法。

1)LEACH算法

LEACH是一種很重要的分簇算法，許多拓撲控制的分簇算法都是在LEACH [16]的基礎上改進的。算法先選簇頭后劃分區域，節點周期性地輪換充當簇頭來實現網絡的負載均衡。LEACH算法中，節點產生[0，1]的隨機數，若隨機數小于閾值T，則宣布自己成為簇頭，普通節點選擇離其最近的簇頭并加入該簇頭管轄的區域。未被選為簇頭的節點隨著時間的推移，能量比簇頭愈顯充足，成為簇頭的可能性就越大。

LEACH輪換選舉簇頭，易保證網絡獲取統一的能量分布，且集中、周期地采集數據，因此其非常適合要求連續監控的應用系統。但簇頭的選擇沒有考慮節點的地理位置信息，且需要較為嚴格的時間同步，更致命的是LEACH不能保證簇頭均勻分布，這可能直接會影響骨干網的形成。

2)HEED算法

基于LEACH的缺陷，LEACH的改進算法HEED [17]應運而生。HEED算法思想是綜合考慮剩余能量和簇內通信代價兩級因素周期性地通過迭代的方法實現分簇。HEED用最小平均可達功率(AMRP)作為某個節點被選為簇頭時的簇內通信代價的度量。

HEED不依賴于網絡的規模，有效地改善了LEACH簇頭可能分布不均的缺陷。HEED通過O(1)次迭代實現分簇，迭代每一步的時間要足夠長，使得節點能夠收到來自鄰居節點的消息。每個節點要確定在一簇范圍內的鄰居節點的集合，計算并廣播AMRP，計算自己成為臨時簇頭的初始概率。雖然，HEED考慮了負載均衡和擴展性，但其執行不依賴時間同步可能會嚴重影響分簇的質量。

3)GAF算法

GAF[18]是一種基于地理位置的分簇算法，該算法思想是首先將事件區域劃分為若干虛擬網格，節點依據自身所處的位置加入相應的格內，然后定期在格內選取簇頭。簇頭節點始終保持清醒狀態，非簇頭節點進入睡眠狀態。節點在休眠狀態過后會再次與本格內其他節點交換信息來重選簇頭，簇頭通常由節點產生的定時隨機值決定。由于簇頭的選取具有一定的隨機性，方格邊長的選取必須能使相鄰兩格內任意節點可直接通信。GAF顯著降低了節點偵聽能耗，但僅適用于網絡數據流量較小的場景。另外，GAF對GPS的依賴也會使節點部署受到限制。

3.3 支配集網絡的拓撲控制

節點的無線通信模塊的能耗占節點總能耗的絕大部分，基于此，盡可能地減少冗余廣播是降低節點能耗的重要方法。如何在廣播信息能夠覆蓋網內所有節點的前提下使參與廣播的節點的數目最少，于是就引出了WSNs中另外一類拓撲問題——構造最小連通支配集(MCDS)。

3.3.1 MCDS的構造

構造MCDS一般有兩種方法:a)基于刪除冗余節點法(DRN)。首先生成最大連通的子集，然后逐一地刪除節點，直到再刪除節點就不能滿足網絡連通性為止。b)基于最大獨立集法。先產生規模為mis(G)的最大獨立集(MIS)，然后添加節點，直到實現連通，從而形成規模為cds(G)的連通支配集(CDS)?；贒RN的算法復雜度相對較低，但構造的CDS沒有明確上界;基于MIS的算法復雜度較高，但能獲得明確上界的CDS。

3.3.2 代表性算法

Wu Jie算法的基本思想是首先生成一個較大的CDS，然后采用修剪去除冗余節點。節點發送信令學習網絡中的兩跳拓撲結構信息，生成存在冗余的CDS，然后根據一定的規則去除CDS的冗余節點。該算法只利用了局部信息，具有較好的擴展性。ZKY算法也是一種典型的CDS的構造算法。算法思想是采用節點編號的組合作為節點的權值，其目的是減小CDS的規模，刪除具有較小度的節點而保留較大度的節點。

考慮到無線網絡的特點，每個節點偵聽到的通信信道狀態是不同的。距離上鄰近的鏈路如果同時傳輸數據，可能會造成干擾導致信號碰撞。在WSNs中，設計一個高效的拓撲控制算法應考慮到干擾對拓撲造成的影響，并將干擾降低到最小程度。Jain等人分析了干擾對無線多跳網絡性能的影響，將網絡中的干擾進行建模，得出了計算網絡最優吞吐量的上下限方法[19]。He Yan-xiang等人 [20]提出了減少干擾的次優最小連通支配集的骨干網絡拓撲算法(I-CDS)，算法構建了一個連通支配集，而且該連通支配集有效地減少了網絡干擾，并討論了干擾對網絡拓撲造成的影響。若區域內有n個節點m條鏈路，則I-CDS算法具有O(n)的消息復雜度和O(m+n)的時間復雜度。

3.4 拓撲控制算法的比較

由于WSNs網絡依賴于應用，節點的硬件結構呈現多樣性特征，許多的協議和標準也不統一，不同的應用對底層網絡的拓撲控制的要求也不盡相同，很難直接評判拓撲算法的優劣，只能根據實際應用的需要權衡選擇?；谝陨蠈Ω鞣N拓撲算法的討論和分析，從節點密度、復雜度等指標上進行比較，結果如表1所示。

4 拓撲控制與調度、連通之間的關系

在WSNs中，拓撲控制與調度、連通三者是相互緊密聯系的，并通過不同的方式共同完成WSNs的既定功能。如何利用有限的能量最大化網絡壽命是WSNs的核心問題。為達到這個目標，就需要綜合考慮能量有效和負載均衡，合理化網絡能量分配，而拓撲控制、調度和連通三者共同作用是能夠實現這一目標的重要途徑。

節點調度是WSNs拓撲控制重要的研究方向，是在一定的時間階段和空間范圍內只使一部分節點保持工作狀態，而使另一部分節點進入睡眠狀態，其根本目的是節省空閑偵聽時的能耗。非層次調度中每個節點均不屬于某個簇，節點根據自己所能獲得的信息，獨立地控制自己在工作狀態與睡眠狀態之間的轉換;層次型網絡節點調度是由簇頭節點組成骨干網絡，讓其他節點進入睡眠狀態。通常情況下，節點在沒有獲悉興趣數據和承擔數據轉發任務時并不關閉通信模塊，而節點的通信模塊在空閑狀態仍然會偵聽無線信道的占用情況和探測興趣數據的傳遞需求，空閑狀態的能耗與節點在收發狀態時相當，覆蓋冗余也造成了很大的能量浪費，所以，只有使節點進入睡眠狀態才能大幅度地降低網絡的能量消耗。相對整體網絡而言，節點調度只能從微觀層面上進行控制，哪些區域需要較多的工作節點采集、處理信息，哪些區域保持較少的工作節點就能完成任務，只使用節點調度顯然是不能夠很好地解決問題。如此勢必會造成資源不足或資源嚴重浪費的不平衡現象，這時就需要采用拓撲控制策略從全局方面控制某些區域鏈路的使用狀態，從而形成一個良好的網絡拓撲結構。

為了有效地實現節點間的相互通信，要求網絡生成的拓撲本身必須保證連通性。非層次型網絡節點需要獲知鄰居節點是否處于活動狀態或當節點發生丟包現象時需要向鄰居節點發送求救信息，所以要求拓撲具有連通性;層次型網絡節點需要節點輪流工作，必然存在轉發節點睡眠，繼而要重新建立路由，所以拓撲的連通性也是實現這一過程的必要條件。傳感器節點的鄰居節點太少，會造成消息可達率過低，出現較多沒有鄰居節點的偽孤立點，降低了網絡的連通性和容錯能力，增加了網絡分割的可能;若鄰居節點過多，則會造成信息的大量冗余，增加網絡的干擾，帶來通信負擔和計算資源的浪費，從而違背節約能量的初衷。因此，通常要根據實際需要選取合適的節點連通度。另外，高冗余性也是WSNs的主要特點之一，節點部署密度大，節點連通度高，數據冗余度大，部分節點采集的數據與全局節點采集的數據效果相差不大。同時，激活所有節點容易造成大量的網絡擁塞，一方面造成數據丟失，另一方面使得收集到的數據由于延遲過大而失去意義。所以，需要使用有效的拓撲控制技術來消除不必要的冗余數據，保證滿足應用需求的數據被傳送到基站，減少網絡擁塞的出現，并盡可能地將工作平均分配給各個節點，以平衡網絡的能量分布，從而達到提高能效、延長網絡壽命的目的。

WSNs是資源受限網絡，為了提高有限資源的有效性和可靠性，網內鏈路上的通信業務要分布均勻，避免在薄弱鏈路上有太大的業務密度。網絡需要通過有效的睡眠調度來控制節點的狀態轉換，緩解網絡干擾，使中間節點能夠高效地傳送上行鏈路和下行鏈路上的數據。同時，還需要利用拓撲控制算法控制網絡宏觀狀態，并實現節點間的可靠連接和負載均衡，以降低網絡不必要的能量消耗。設計者要根據實際應用場景在調度、連接與拓撲控制間平衡地作出選擇，將點、線、面有機結合，共同作用形成節能高效的拓撲結構，如圖5所示。

5 結束語

拓撲控制是實現WSNs有限資源高效利用的關鍵技術，其算法的評價標準取決于算法的效率。高效的算法應同時表現在降低單位節點傳輸數據的能耗和降低算法本身的實現成本兩個方面。雖然WSNs的拓撲控制技術已經取得了一定的進展，出現了一些代表性的算法，并且研究領域和覆蓋面也在逐步擴大，但拓撲控制算法目前還處于理論研究或實驗模擬階段，離應用于實際尚有一定的距離。目前對拓撲控制的研究大多過于理想化，沒有充分考慮實際的網絡環境，對算法的收斂速度、節點移動的影響、追加節點數目的預測、節點精確位置信息的確定、三維空間區域部署等方面均有待深入考慮，特別是需要多種機制相結合[21]，探索更接近現實環境的拓撲控制技術，增強建立在模型基礎上的理論分析的說服力，這些也是WSNs拓撲控制進一步的研究方向。

參考文獻:

[1]ESTRIN D， GOVINDAN R， HEIDEMANN J， et al. Next century challenges: scalable coordinate in sensor network[C]//Proc of the 5th ACM/IEEE International Conference on Mobile Computing and Networking. Washington: ACM Press， 1999: 263-270.

[2]AKYILDIZ I F， SU Wei-lian， SANKARASUBRAMA NIAM Y， et al. A survey on sensor networks[J]. IEEE Communication Magazine， 2002，40(8):102-114.

[3]路綱，周明天，牛新征，等.無線網絡鄰近圖綜述[J].軟件學報，2008，19(4):888-991.

[4]LI Xiang-yang， SONG Wen-zhan， WANG Yu. Localized toplogy control for heterogeneous wireless sensor networks[J]. ACM Trans on Sensor Networks，2006， 2(1): 129-153.

[5]賀鵬，李建東.基于Delaunay三角剖分的Ad hoc網絡路由法[J].軟件學報，2006，17(5):1149-1156.

[6]郭慶勝，鄭春燕，胡華科. 基于鄰近圖的點群層次聚類方法的研究[J].測繪學報，2008，37(2):256-261.

[7]LI Ning， HOU J C. Topology control in heterogeneous wireless networks: problems and solutions[C]//Proc of the 23rd IEEE Confe-rence on Computer Communications. New York: IEEE Press， 2004:232-243.

[8]鄭國強，李建東.無線傳感器網絡MAC協議研究進展 [J].自動化學報，2008，34(3):306-313.

[9]NARAYANSWAMY 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.

[10]BLOUGH D， 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 Computing. New York: ACM Press， 2003:141-152.

[11]RODOPLU V， MENG T H. Minimum energy mobile wireless netwoks[J]. Selected Areas in Communications，1999， 17(8):1333-1344.

[12]LI Li， HALPERN J Y， BAHL P， et al. Analysis of a cone-based distributed topology control algorithm for wireless multi-hop networks[C]//Proc of the 20th ACM Symposium on Principles of Distributed Computing. New York:ACM Press， 2001:264-273.

[13]ZHANG Hong-hai， HOU J C. Maintaining sensing coverage and connectivity in large sensor networks[J]. Ad hoc Sensor Wireless Networks， 2005，1(3):89-124.

[14]XUE Feng， KUMAR P R. The number of neighbors needed for connectivity of wireless networks[J]. Wireless Networks， 2004， 10(2):169-181.

[15]GAO Yong， WU Kui， LI Fu-lu. Analysis on the redundancy of wireless sensor networks[C]//Proc of the 2nd ACM International Confe-rence on Wireless Sensor Networks and Applications. New York:ACM Press， 2003:108-114.

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

[17]YOUNIS O， FAHMY S. Distributed clustering in Ad hoc sensor networks:a hybrid energy-efficient approach[C]//Proc of the 23rd Annual Joint Conference on Computer and Communications Societies. 2004:46-63.

[18]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.

[19]JAIN K， PADHYE J， PADMANABHAN V， et al. Impact of interfe-rence on multihop wireless network performance [C]//Proc of the 9th Annual International Conference on Mobile Computing and Networking. New York:ACM Press， 2003:66-80.

[20]HE Yan-xiang， ZENG Yuan-yuan. Interference-aware topology control problem in wireless sensor networks[C]//Proc of the 6th International Conference on ITS Telecommunications Proceedings. 2006:969-972.

[21]鄭國強，李建東.用于多跳無線傳感器網絡的能量有效數據轉發協議[J].計算機科學，2007，34(8): 24-29.