無線傳感器網絡(Wireless Sensor Networks，WSN)是由任意散落在被監測區域內大量傳感器節點以自組織形式構成的網絡，并通過網絡將監測數據傳送到接收站進行處理。通過隨機投放的方式，眾多傳感器節點被密集部署于監控區域。這些傳感器節點集成有傳感器、數據處理單元和通信模塊，它們通過無線信道相連，自組織地構成網絡系統。傳感器節點間有良好的協作能力，通過局部的數據交換來完成全局任務。通過網關、傳感器網絡還可以連接到現有的網絡設施上(如Internet、移動通信網絡等)，從而將采集到的信息傳回給遠程的終端用戶使用。隨著微電子技術、通信技術和計算機技術的飛速發展，WSN在軍事和民用各個領域都得到廣泛應用，其應用潛力巨大，已成為目前通信領域的研究熱點。

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

WSN網絡拓撲控制主要研究的問題是：在保證網絡覆蓋度和聯通性的前提下，設置或調整節點的發射功率，并按照一定的原則選擇合適的節點成為骨干節點，參與網絡中數據的處理和傳輸，達到優化網絡拓撲結構的目的，其首要的設計目標是通過高效使用能量使網絡生命期最大化。

WSN中拓撲控制可以分為兩個研究方向：功率控制和層次拓撲結構控制。功率控制機制調整網絡中每個節點的發射功率，保證網絡連通，在均衡節點中直接鄰居數目(單跳可達鄰居數目)的同時，降低節點之間的通信干擾。層次拓撲控制是利用分簇思想，使網絡中的部分節點處于激活狀態，成為簇頭節點。由這些簇頭節點構建一個連通的網絡來處理和傳輸網絡中的數據，并定期或不定期地重新選擇簇頭節點，以均衡網絡中節點的能量消耗。WSN中，節點的無線通信模塊處于發送狀態下功耗最高，接收狀態和空閑狀態下功耗次之，休眠狀態下功耗最低。例如，目前用于WSN的主流傳感器Berkeley Motes，其通信模塊處于發送狀態的功耗為60 mW，接收狀態和空閑狀態的功耗均為12 mW，休眠狀態的功耗為0.03 mW，其功耗比達到2 000：400：1，因此降低能耗的關鍵是降低網絡內的通信流量，使更多的節點在更長時間段處于休眠狀態。為了大幅度降低無線通信模塊的能量消耗，可以考慮依據一定的機制選擇部分節點作為骨干節點，這些節點的通信模塊處于打開狀態，而其他非骨干節點的通信模塊處于關閉。在這種機制下，節點被分為骨干節點和非骨干節點兩類，骨干節點對非骨干節點進行管轄。這類算法將網絡分為相連的區域，稱為分簇算法。

在層次拓撲控制方面，已經提出的算法有Deb的TopDisc(Topology Discory)拓撲發現算法、Santi的改進GAF(Geographical Adaptive Fidelity)分簇算法、Heinzelman的LEACH(LOW Energy AdaptiveChlstering Hierarchy)算法和Younis的HEED算法等。

在此，以經典的基于最小支配集理論TopDisc算法為研究對象。通過考慮節點電量的剩余情況，得到Power-balanced TopDisc算法。該算法將節點剩余能量作為分簇結構的構建依據，對剩余能量較少的節點賦予一定的約束，使之成為普通節點，從而均衡網絡電量負載，解決網絡中部分低電量節點擔任骨干節點而導致的能耗問題，有效延長網絡生命期。仿真實驗結果證明了該算法的有效性。

2  TopDisc算法

在TopDisc算法中，首先由初始節點發出拓撲發現請求，通過廣播該請求消息來確定網絡中的骨干節點，并結合這些骨干節點中鄰居節點的信息形成網絡拓撲的近似拓撲。在這個近似拓撲形成以后，為了減小算法本身引起的網絡通信量，只有骨干節點才對初始節點的拓撲發現請求作出相應的響應。

為了確定網絡中的骨干節點，TopDisc算法采用的是貪婪算法。具體分為兩種類型：三色法和四色法。

2.1 三色法

在三色算法中，節點可以處于三種不同狀態。在TopDisc算法中，分別用白色、黑色、灰色三種顏色表示：

(1)白色是尚未被發現的節點，或者說是沒有接收到任何拓撲發現請求的節點；

(2)黑色是骨干節點(簇頭節點)，負責響應拓撲發現請求；

(3)灰色是普通節點，至少被一個標記為黑色的節點覆蓋，即黑色節點的鄰居節點。

在開始階段，所有節點都被標記為白色，算法由一個初始節點發起，算法結束后所有節點都將被標記為黑色或者灰色(假設整個網絡拓撲是連通的)。Top-Disc使用兩種啟發式方法，使得每個新的黑色節點都盡可能多地覆蓋還沒有被覆蓋到的節點：一種是節點顏色標記方法；另一種是節點轉發拓撲發現請求時會故意延時一段時間，延時時間的長度反比于該節點與發送拓撲發現請求到該節點之間的距離。具體算法過程如下：

(1)初始節點被標記為黑色，并向網絡廣播拓撲發現請求；