0 引 言
無線傳感器網(wǎng)絡(Wireless Sensor Networks，WSN)是由任意散落在被監(jiān)測區(qū)域內(nèi)大量傳感器節(jié)點以自組織形式構成的網(wǎng)絡，并通過網(wǎng)絡將監(jiān)測數(shù)據(jù)傳送到接收站進行處理。通過隨機投放的方式，眾多傳感器節(jié)點被密集部署于監(jiān)控區(qū)域。這些傳感器節(jié)點集成有傳感器、數(shù)據(jù)處理單元和通信模塊，它們通過無線信道相連，自組織地構成網(wǎng)絡系統(tǒng)。傳感器節(jié)點間有良好的協(xié)作能力，通過局部的數(shù)據(jù)交換來完成全局任務。通過網(wǎng)關、傳感器網(wǎng)絡還可以連接到現(xiàn)有的網(wǎng)絡設施上(如Internet、移動通信網(wǎng)絡等)，從而將采集到的信息傳回給遠程的終端用戶使用。隨著微電子技術、通信技術和計算機技術的飛速發(fā)展，WSN在軍事和民用各個領域都得到廣泛應用，其應用潛力巨大，已成為目前通信領域的研究熱點。
1 無線傳感器網(wǎng)絡的拓撲控制
WSN網(wǎng)絡拓撲控制主要研究的問題是：在保證網(wǎng)絡覆蓋度和聯(lián)通性的前提下，設置或調整節(jié)點的發(fā)射功率，并按照一定的原則選擇合適的節(jié)點成為骨干節(jié)點，參與網(wǎng)絡中數(shù)據(jù)的處理和傳輸，達到優(yōu)化網(wǎng)絡拓撲結構的目的，其首要的設計目標是通過高效使用能量使網(wǎng)絡生命期最大化。
WSN中拓撲控制可以分為兩個研究方向：功率控制和層次拓撲結構控制。功率控制機制調整網(wǎng)絡中每個節(jié)點的發(fā)射功率，保證網(wǎng)絡連通，在均衡節(jié)點中直接鄰居數(shù)目(單跳可達鄰居數(shù)目)的同時，降低節(jié)點之間的通信干擾。層次拓撲控制是利用分簇思想，使網(wǎng)絡中的部分節(jié)點處于激活狀態(tài)，成為簇頭節(jié)點。由這些簇頭節(jié)點構建一個連通的網(wǎng)絡來處理和傳輸網(wǎng)絡中的數(shù)據(jù)，并定期或不定期地重新選擇簇頭節(jié)點，以均衡網(wǎng)絡中節(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，因此降低能耗的關鍵是降低網(wǎng)絡內(nèi)的通信流量，使更多的節(jié)點在更長時間段處于休眠狀態(tài)。為了大幅度降低無線通信模塊的能量消耗，可以考慮依據(jù)一定的機制選擇部分節(jié)點作為骨干節(jié)點，這些節(jié)點的通信模塊處于打開狀態(tài)，而其他非骨干節(jié)點的通信模塊處于關閉。在這種機制下，節(jié)點被分為骨干節(jié)點和非骨干節(jié)點兩類，骨干節(jié)點對非骨干節(jié)點進行管轄。這類算法將網(wǎng)絡分為相連的區(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é)點剩余能量作為分簇結構的構建依據(jù)，對剩余能量較少的節(jié)點賦予一定的約束，使之成為普通節(jié)點，從而均衡網(wǎng)絡電量負載，解決網(wǎng)絡中部分低電量節(jié)點擔任骨干節(jié)點而導致的能耗問題，有效延長網(wǎng)絡生命期。仿真實驗結果證明了該算法的有效性。
2 TopDisc算法
在TopDisc算法中，首先由初始節(jié)點發(fā)出拓撲發(fā)現(xiàn)請求，通過廣播該請求消息來確定網(wǎng)絡中的骨干節(jié)點，并結合這些骨干節(jié)點中鄰居節(jié)點的信息形成網(wǎng)絡拓撲的近似拓撲。在這個近似拓撲形成以后，為了減小算法本身引起的網(wǎng)絡通信量，只有骨干節(jié)點才對初始節(jié)點的拓撲發(fā)現(xiàn)請求作出相應的響應。
為了確定網(wǎng)絡中的骨干節(jié)點，TopDisc算法采用的是貪婪算法。具體分為兩種類型：三色法和四色法。
2.1 三色法
在三色算法中，節(jié)點可以處于三種不同狀態(tài)。在TopDisc算法中，分別用白色、黑色、灰色三種顏色表示：
(1)白色是尚未被發(fā)現(xiàn)的節(jié)點，或者說是沒有接收到任何拓撲發(fā)現(xiàn)請求的節(jié)點；
(2)黑色是骨干節(jié)點(簇頭節(jié)點)，負責響應拓撲發(fā)現(xiàn)請求；
(3)灰色是普通節(jié)點，至少被一個標記為黑色的節(jié)點覆蓋，即黑色節(jié)點的鄰居節(jié)點。
在開始階段，所有節(jié)點都被標記為白色，算法由一個初始節(jié)點發(fā)起，算法結束后所有節(jié)點都將被標記為黑色或者灰色(假設整個網(wǎng)絡拓撲是連通的)。Top-Disc使用兩種啟發(fā)式方法，使得每個新的黑色節(jié)點都盡可能多地覆蓋還沒有被覆蓋到的節(jié)點：一種是節(jié)點顏色標記方法；另一種是節(jié)點轉發(fā)拓撲發(fā)現(xiàn)請求時會故意延時一段時間，延時時間的長度反比于該節(jié)點與發(fā)送拓撲發(fā)現(xiàn)請求到該節(jié)點之間的距離。具體算法過程如下：
(1)初始節(jié)點被標記為黑色，并向網(wǎng)絡廣播拓撲發(fā)現(xiàn)請求；
(2)當白色節(jié)點收到來自黑色節(jié)點的拓撲發(fā)現(xiàn)請求時，將被標記為灰色，并在延時時間tWB后繼續(xù)廣播拓撲發(fā)現(xiàn)請求。tWB反比于它與黑色節(jié)點之間的距離。
(3)當白色節(jié)點收到來自灰色節(jié)點的拓撲發(fā)現(xiàn)請求時，將在等待時間tWG后標記為黑色，但如果在等待期間，又收到來自黑色節(jié)點的拓撲發(fā)現(xiàn)請求時，則優(yōu)先標記為灰色；同樣，等待時間反比于該白色節(jié)點與灰色節(jié)點之間的距離。不管節(jié)點被標記為灰色還是黑色，都將在完成顏色標記之后繼續(xù)廣播拓撲發(fā)現(xiàn)請求；
(4)所有已經(jīng)被標記為黑色或者灰色的節(jié)點，都將忽略其他節(jié)點的拓撲發(fā)現(xiàn)請求。
為了使每個新的黑色節(jié)點都盡可能多地覆蓋還沒有被覆蓋的節(jié)點，TopDisc采用反比于節(jié)點之間距離的轉發(fā)延時機制。理想情況下，節(jié)點的覆蓋范圍是半徑為無線電發(fā)射半徑的圓。于是，單個節(jié)點所能夠覆蓋的節(jié)點數(shù)目正比于其覆蓋面積和局部節(jié)點部署密度。對于一個正在轉發(fā)拓撲發(fā)現(xiàn)請求的節(jié)點，它所能夠覆蓋的新節(jié)點(還沒有被任何節(jié)點覆蓋)則正比于它的覆蓋面積與已經(jīng)覆蓋的面積之差。
2.2 四色法
為了增大簇之間的間隔，減少重疊區(qū)域，TopDisc算法還提出了四色法。節(jié)點可以處于四種不同的狀態(tài)，分別用白色、黑色、灰色和深灰色表示。前三種顏色代表的含義與三色法相同，增加的深灰色表示節(jié)點收到過拓撲發(fā)現(xiàn)請求，但不被任何標記為黑色的節(jié)點覆蓋。
在初始階段，所有節(jié)點被標記為白色，算法由一個初始節(jié)點發(fā)起，算法結束后所有節(jié)點都將被標記為黑色或灰色(假設整個網(wǎng)絡拓撲是連通的，注意最終沒有標記為深灰色的節(jié)點)。詳細過程描述如下：
(1)初始節(jié)點被標記為黑色，并向網(wǎng)絡廣播拓撲發(fā)現(xiàn)請求；
(2)當白色節(jié)點收到來自黑色節(jié)點的拓撲發(fā)現(xiàn)請求時，將標記為灰色，并在延時時間tWB后繼續(xù)廣播拓撲發(fā)現(xiàn)請求。tWB反比于它與黑色節(jié)點之間的距離；
(3)當白色節(jié)點收到來自灰色節(jié)點的拓撲發(fā)現(xiàn)請求時，將標記為深灰色并繼續(xù)廣播拓撲發(fā)現(xiàn)請求，然后等待一段時間tWG(同樣與距離成反比)。如果在等待期間收到來自黑色節(jié)點的拓撲發(fā)現(xiàn)請求時，則改變?yōu)榛疑�，否則它自己成為黑色；
(4)當白色節(jié)點收到來自深灰色節(jié)點的拓撲發(fā)現(xiàn)請求時，等待一段時間(同樣與距離成反比)。如果在等待期間，收到來自黑色節(jié)點的拓撲發(fā)現(xiàn)請求時，則改變?yōu)榛疑�，否則它自己變?yōu)楹谏V播拓撲發(fā)現(xiàn)請求；
(5)所有已經(jīng)被標記為黑色或者灰色的節(jié)點，都將忽略其他節(jié)點的拓撲發(fā)現(xiàn)請求。
與三色法相比，四色法形成的簇數(shù)目更少，簇與簇之間的重疊區(qū)域也更小。但是可能形成一些孤立的標記為黑色的節(jié)點不覆蓋任何灰色節(jié)點。雖然三色法和四色法形成的黑色節(jié)點數(shù)目相當，但四色法中傳輸?shù)臄?shù)據(jù)量要少一些。
TopDisc算法利用圖論中的經(jīng)典算法，提出了一種有效方法來構建網(wǎng)絡的近似拓撲，是分簇算法中的經(jīng)典算法。它是一種只需要利用局部信息，且完全分布時可擴展的網(wǎng)絡拓撲控制算法。但也存在需要改進的地方，如算法開銷偏大；沒有考慮節(jié)點剩余電量的信息。
3 Power-balanced TopDisc算法
WSN中節(jié)點轉發(fā)數(shù)據(jù)的耗能模型如下所述。
傳感器節(jié)點發(fā)射r比特數(shù)據(jù)包所消耗的能量為：
Pt(r，d)=r(a1+a2dn) (1)
式中：d為兩節(jié)點之間的距離；a1是與距離無關的量，包括發(fā)射電路所耗能量等；a2是與距離有關的量；n為路徑損耗指數(shù)，通常取2～4之間。
傳感器節(jié)點接收r比特數(shù)據(jù)包所消耗的能量為：
Pr(r)=rβ (2)
式中：β盧為接收能量系數(shù)。
傳感器節(jié)點將2個數(shù)據(jù)流r1和r2融合成一個數(shù)據(jù)包r的耗能為：
Pa(r1+r2，r)=r(r1+r2-r) (3)
式中：r為數(shù)據(jù)融合系數(shù)。
從式(1)～式(3)可以看出，若剩余能量較少的節(jié)點仍然承擔著較重的轉發(fā)任務，那么就很可能導致該節(jié)點過早死亡，從而影響網(wǎng)絡生命時間的延續(xù)。所以，在構建無線傳感器網(wǎng)絡拓撲時，節(jié)點應選擇剩余能量多的節(jié)點作為數(shù)據(jù)轉發(fā)的主要節(jié)點，而剩余能量較少的節(jié)點作為數(shù)據(jù)源節(jié)點，這樣將有效解決由于負載過大而過早死亡的問題。
為便于描述和分析，作如下假設：
(1)每個節(jié)點都具有相同的最大發(fā)射功率，其覆蓋范圍是半徑為R的圓形區(qū)域，且可通過調節(jié)發(fā)射功率以適應其覆蓋范圍內(nèi)不同距離節(jié)點的通信；
(2)每個節(jié)點都能夠獲得自身的剩余能量，有一定的存儲空間來存放鄰居節(jié)點信息；
(3)忽略真實環(huán)境中存在障礙物等影響通信質量的因素，確保所有的數(shù)據(jù)包都能夠可靠傳輸。
考慮節(jié)點電量均衡因素，在TopDisc四色法的步驟(3)中，對tWG進行修正，公式為：
twG=a1／d+a2／p (4)
式中：d為節(jié)點之間的距離；p為當前節(jié)點剩余的電量；a1和a2為預設參數(shù)。對tWG進行修正后得到Power-balanced TopDise算法。
Power-balanced TopDise算法的合理性可以由圖1說明。圖1(a)為TopDisc算法的分簇結果；圖1(b)為Power-balanced TopDise算法的分簇結果。其中，電量為80的節(jié)點為初始節(jié)點。初始節(jié)點發(fā)出拓撲發(fā)現(xiàn)請求到電量為20的節(jié)點變?yōu)榛疑⒗^續(xù)廣播拓撲發(fā)現(xiàn)請求。電量為30和90的節(jié)點同時收到拓撲發(fā)現(xiàn)請求。在Power-balanced TopDisc算法中，電量為90的節(jié)點先于電量為30的節(jié)點變?yōu)楹谏�，即成為骨干�?jié)點(簇頭節(jié)點)。
經(jīng)過上述基于電量均衡的Power-balanced TopDisc算法處理后，剩余能量較少的節(jié)點將不再擔當骨干節(jié)點，有利于延長網(wǎng)絡的生命周期，從而實現(xiàn)均衡耗能。
4 性能分析和實驗
為評估Power-balanced TopDise算法的性能，采用軟件進行多次仿真試驗，以所獲得的分簇結構作為主要性能指標，并與TopDisc算法進行比較。
仿真模擬配置如下：假設有400個節(jié)點隨機地部署在一個400×400的正方形平面區(qū)域內(nèi)；每個節(jié)點的剩余能量為1～100的隨機值。由TopDisc算法和Power-balanced TopDisc算法所生成的分簇結構分別如圖2和圖3所示。
對于該WSN，TopDisc算法得到的分簇結果是骨干節(jié)點平均電量為51；Power-balanced TopDisc算法得到的分簇結果是骨干節(jié)點平均電量為56。由于Power-balanced TopDisc算法生成的分簇結構考慮了節(jié)點的剩余電量，因而它使得剩余能量較少的節(jié)點成為普通節(jié)點，節(jié)省了擔當骨干節(jié)點耗費的能量，從而延長了整個網(wǎng)絡的生命周期。
5 結 語
在此，提出一種基于電量均衡的Power-balancedTopDisc算法，該算法考慮了節(jié)點中剩余電量的多少，對節(jié)點賦予一定的約束，讓剩余能量較多的節(jié)點擔當骨干節(jié)點，承擔數(shù)據(jù)轉發(fā)任務，保證了低電量節(jié)點不會因轉發(fā)過多數(shù)據(jù)而過早失效，從而延長整個網(wǎng)絡的生命期，實驗結果證明了該算法的有效性。