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

1 無線傳感器網(wǎng)絡(luò)的拓撲控制

WSN網(wǎng)絡(luò)拓撲控制主要研究的問題是：在保證網(wǎng)絡(luò)覆蓋度和聯(lián)通性的前提下，設(shè)置或調(diào)整節(jié)點的發(fā)射功率，并按照一定的原則選擇合適的節(jié)點成為骨干節(jié)點，參與網(wǎng)絡(luò)中數(shù)據(jù)的處理和傳輸，達到優(yōu)化網(wǎng)絡(luò)拓撲結(jié)構(gòu)的目的，其首要的設(shè)計目標是通過高效使用能量使網(wǎng)絡(luò)生命期最大化。

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

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

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

2  TopDisc算法

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

為了確定網(wǎng)絡(luò)中的骨干節(jié)點，TopDisc算法采用的是貪婪算法。具體分為兩種類型：三色法和四色法。

2.1 三色法

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

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

(2)黑色是骨干節(jié)點(簇頭節(jié)點)，負責響應(yīng)拓撲發(fā)現(xiàn)請求；

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

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

(1)初始節(jié)點被標記為黑色，并向網(wǎng)絡(luò)廣播拓撲發(fā)現(xiàn)請求；