無線傳感器網(wǎng)絡拓撲控制研究

摘要:隨著無線傳感器網(wǎng)絡的廣泛應用，傳感器節(jié)點的部署環(huán)境也更加復雜，網(wǎng)絡性能受到很大影響，通過優(yōu)化拓撲結(jié)構(gòu)，最大化利用節(jié)點有限資源成為拓撲控制研究的重要內(nèi)容，網(wǎng)絡拓撲控制在延長網(wǎng)絡生命周期、節(jié)約節(jié)點資源、降低網(wǎng)絡干擾等方面發(fā)揮著重要的作用，它能夠提高路由協(xié)議和MAC協(xié)議的效率，為數(shù)據(jù)融合、時間同步和目標定位等很多方面提供基礎。設計實現(xiàn)一種高效的拓撲控制機制已成為無線傳感器網(wǎng)絡的研究重點，該文中主要是針對現(xiàn)有的部分拓撲控制算法進行了分析和比較。

關鍵詞:無線傳感器網(wǎng)絡;拓撲控制;功率控制;分簇控制

中圖分類號:TP393文獻標識碼:A 文章編號:1009-3044(2009)36-10195-03

Research on Topology Control for Wireless Sensor Networks

HUANG Hu， ZHANG Yu-ting， FANG Mu-yun

(School of Computer Science， Anhui University of Technology， Ma'anshan 243002， China)

Abstract: With the extensive application of wireless sensor network， deployment environment of sensor nodes is also more complex， network performance has been greatly affected， maximize the use of the limited resources of the node by topology optimization become an important study of topology control， network topology control has played an important role in extending the network life cycle， saving the node resources， reducing network interference， it can improve the routing protocol and MAC protocol efficiency and provide the basis for data fusion， time synchronization and targeting， etc.. designed to achieve a efficient topology control mechanism for wireless sensor networks has become the focus of the study， this paper is mainly directed against the existing part of the topology control algorithm is analyzed and compared.

Key words: wireless sensor networks; topology control; power control; clustering control

無線傳感器網(wǎng)絡作為一種新型的網(wǎng)絡信息獲取系統(tǒng)，在民用、軍事等領域具有極其廣闊的應用前景，其具有規(guī)模大、自組織、隨機部署、環(huán)境復雜、傳感器節(jié)點資源有限、網(wǎng)絡拓撲經(jīng)常變化等特點[1]。這些特點使得拓撲控制和網(wǎng)絡能量消耗成為挑戰(zhàn)性的研究課題，同時，也決定了拓撲控制在無線傳感器網(wǎng)絡研究中的重要作用。拓撲控制的缺失一方面將導致網(wǎng)絡中所有節(jié)點都會以最大傳輸功率工作，降低了網(wǎng)絡的生命周期及網(wǎng)絡吞吐率;另一方面，在生成的網(wǎng)絡拓撲中將存在大量的鏈路，從而導致網(wǎng)絡拓撲信息量大，路由計算復雜，浪費了寶貴的計算資源。因此，需要研究無線傳感器網(wǎng)絡中的拓撲控制問題，在維持拓撲的某些全局性質(zhì)的前提下，通過各種節(jié)能措施延長網(wǎng)絡生命周期，提高網(wǎng)絡吞吐量，降低網(wǎng)絡干擾，節(jié)約節(jié)點資源，彌補節(jié)點失效的影響，為路由協(xié)議提供基礎。

1 拓撲控制實現(xiàn)的目標

拓撲控制的研究是指在保證一定的網(wǎng)絡連通度和覆蓋度的前提下，以延長網(wǎng)絡生命周期為主要目標，兼顧通信干擾、網(wǎng)絡延遲、負載均衡、簡單性、可靠性、可擴展性等其他性能，從而形成優(yōu)化的網(wǎng)絡拓撲結(jié)構(gòu)[2]。拓撲控制需要實現(xiàn)的目標主要有以下幾點:

1) 連通度:無線傳感器網(wǎng)絡一般規(guī)模較大，傳感器節(jié)點所獲取的數(shù)據(jù)通常以多跳的方式傳送至匯聚節(jié)點，這就要求拓撲控制必須保證網(wǎng)絡的連通性。如果至少要去掉k個節(jié)點才能使網(wǎng)絡不連通，就稱其為k-連通。拓撲控制要保證網(wǎng)絡至少是1-連通的。

2) 覆蓋度:覆蓋度可以看作對傳感器網(wǎng)絡服務質(zhì)量的度量。覆蓋度問題可以分為區(qū)域覆蓋、點覆蓋和柵欄覆蓋。如果目標區(qū)域中任意一個點均在k個傳感器節(jié)點的傳輸范圍內(nèi)，就稱網(wǎng)絡是k覆蓋的。一般要求目標區(qū)域至少是1-覆蓋的。

3) 吞吐量:吞吐量是指網(wǎng)絡承載數(shù)據(jù)傳輸?shù)哪芰?，尤其是在有大量?shù)據(jù)出現(xiàn)時，吞吐量是影響網(wǎng)絡通信能力的因素之一。設計目標區(qū)域是一個凸區(qū)域，每個節(jié)點的吞吐率為λ bits/s，在理想情況下吞吐量如式(1)所示[3]。

(1)

其中A是目標區(qū)域面積，W是節(jié)點的最高傳輸速率，Π是圓周率，△是大于0的常數(shù)，L是源節(jié)點到目標節(jié)點的平均距離，n是節(jié)點數(shù)，r是理想狀態(tài)下的發(fā)射半徑。由此可以看出，通過減小發(fā)射半徑或減小網(wǎng)絡規(guī)模，在節(jié)省能量的同時可以在一定程度上提高網(wǎng)絡的吞吐能力。

4) 網(wǎng)絡生命周期:網(wǎng)絡生命周期的定義有多種，一般將網(wǎng)絡生命周期定義為直到死亡節(jié)點的百分比低于某個閾值的持續(xù)時間。也可以通過對網(wǎng)絡的服務質(zhì)量的度量來定義網(wǎng)絡的生命期。

此外，拓撲控制還要考慮如均衡負載、簡單性、可靠性、可擴展性等其他方面。拓撲控制的各種設計目標之間的關系錯綜復雜，因此，這些關系的研究也是拓撲控制研究的重點。

2 拓撲控制的研究現(xiàn)狀

目前無線傳感器網(wǎng)絡拓撲控制的研究主要集中在功率控制和分簇控制，并相繼提出了多種多樣、側(cè)重點不同的拓撲控制算法，旨在從影響無線傳感器網(wǎng)絡性能的因素入手，有針對性的設計實現(xiàn)拓撲結(jié)構(gòu)的優(yōu)化策略。拓撲控制算法主要有以下幾種，如圖1所示。

2.1 功率控制

功率控制策略主要從兩方面進行研究，一是基于節(jié)點的度，二是基于圖論中的鄰近圖。功率控制通過動態(tài)調(diào)整發(fā)送節(jié)點的發(fā)射功率，在保證一定通信質(zhì)量的前提下盡量降低信號發(fā)射功率，使得節(jié)點的能量消耗最小，延長整個網(wǎng)絡的生命周期。

2.1.1 基于節(jié)點度策略

節(jié)點的度數(shù)是指距離該節(jié)點一跳的鄰居節(jié)點的數(shù)量。基于節(jié)點度策略的基本思想是:給定節(jié)點度的上限和下限，節(jié)點動態(tài)的調(diào)整自身的發(fā)射功率，使得節(jié)點的度落在上限和下限之間?；诠?jié)點度的算法利用局部信息來調(diào)整鄰接點之間的連通性，從而保證整個網(wǎng)絡的連通性。LMA(Local mean algorithm)算法[4] 是基于節(jié)點度的經(jīng)典算法，它是一種周期性的算法，具體步驟如下:

①初始狀態(tài)所有節(jié)點以相同發(fā)射功率Pt定期廣播一個包含自身ID的LifeMsg消息。

②若節(jié)點收到LifeMsg消息，則發(fā)送一個響應消息LifeAckMsg，該消息包含所應答的LifeMsg消息中的節(jié)點ID。

③每個節(jié)點發(fā)送LifeMsg消息時，先檢查已接收到的LifeMsg消息，利用這些消息統(tǒng)計出自己的鄰居節(jié)點數(shù)NodeResp。

④如果NodeResp小于鄰居節(jié)點數(shù)下限NodeMinTresh，則節(jié)點在這輪發(fā)送中按式(2)調(diào)整發(fā)射功率;如果NodeResp大于或等于鄰居節(jié)點數(shù)上限NodeMaxTresh，則節(jié)點按式(3)調(diào)整發(fā)射功率。

(2)

(3)

式中Bmax、Bmin、Ainc、Adoc是四個動態(tài)調(diào)節(jié)參數(shù)，在一定幅度內(nèi)調(diào)節(jié)發(fā)射功率。LMA算法的優(yōu)點在于簡單、網(wǎng)絡節(jié)點易于部署，僅利用局部信息確定節(jié)點發(fā)射功率。不過其預先設定的調(diào)節(jié)參數(shù)和節(jié)點度值的上下限將直接影響算法性能，需綜合考慮。此外，其單一的度值區(qū)間使得無法較好的適應動態(tài)變化的拓撲特性。

2.1.2 基于鄰近圖策略

基于鄰近圖的功率控制策略是指所有節(jié)點使用最大發(fā)射功率形成拓撲圖G，然后根據(jù)某種規(guī)則得到G的鄰近圖G'，最后G'中節(jié)點以自己所鄰接的最遠節(jié)點調(diào)整發(fā)射功率。Li等人提出了一種基于本地最小生成樹結(jié)構(gòu)的拓撲控制算法LMST(Local minimum spanning tree)[5]。該算法是一種典型的基于鄰近圖的功率控制算法，通過確定一個節(jié)點為中心節(jié)點，將其鄰居節(jié)點包含進來，構(gòu)成一個鄰接點集合圖，在此圖中利用最小生成樹算法計算出其所有鄰接點中與此中心節(jié)點只有一跳距離的節(jié)點，將其設為鄰居節(jié)點，然后將中心節(jié)點的發(fā)射功率設置為到達所有一跳鄰接點中距離中心點最遠節(jié)點的功率。具體步驟如下:

1) 信息收集，節(jié)點u定期以最大發(fā)射功率發(fā)送HELLO消息，從而獲取自身鄰居節(jié)點集合N并構(gòu)成鄰居子圖。

2) 拓撲建立，節(jié)點u依據(jù)Prim算法構(gòu)造本地最小生成樹結(jié)構(gòu)T。

3) 確定發(fā)射功率，節(jié)點依據(jù)構(gòu)造的本地最小生成樹結(jié)構(gòu)確定自身發(fā)射功率。

LMST能有效的降低節(jié)點傳輸功率，減小了節(jié)點之間競爭通信干擾，且保持了原圖的連通性，而且每個節(jié)點的最大度值為6，其平均節(jié)點度數(shù)也比較小，接近理論界限，能有效的進行局部拓撲的修復。但LMST未考慮拓撲結(jié)構(gòu)的健壯性，無法滿足路由協(xié)議能耗均衡的要求。

2.2 分簇控制策略

在傳感器網(wǎng)絡中，傳感器節(jié)點的無線通信模塊在空閑狀態(tài)時的能量消耗和在收發(fā)狀態(tài)下相當，所以在節(jié)點空閑時關閉通信模塊能大幅降低無線通信的能量開銷，從而降低節(jié)點能耗，延長網(wǎng)絡生命周期。層次型拓撲控制正是基于此種考慮，依據(jù)一定的機制選擇某些節(jié)點作為骨干節(jié)點，打開其通信模塊，并關閉非骨干節(jié)點的通信模塊，由骨干節(jié)點構(gòu)成一個連通網(wǎng)絡負責網(wǎng)絡數(shù)據(jù)的轉(zhuǎn)發(fā)。此種控制機制的關鍵技術(shù)是分簇，如何將網(wǎng)絡合理的劃分成相連的區(qū)域成為首要考慮的問題。經(jīng)典的分簇算法有:LEACH、GAF和TopDisc等。

2.2.1 LEACH(Low energy adaptive clustering hierachy)算法

2000年Heinzelman等人提出了第一個無線傳感器網(wǎng)絡分簇算法LEACH[6]，它的執(zhí)行過程是周期性的，每輪循環(huán)分為簇的建立階段和穩(wěn)定的數(shù)據(jù)通信階段。在簇的建立階段，相鄰節(jié)點動態(tài)成簇，隨機產(chǎn)生簇頭節(jié)點;在通信階段，簇內(nèi)節(jié)點把數(shù)據(jù)發(fā)送給簇頭節(jié)點，然后由簇頭節(jié)點進行數(shù)據(jù)融合并發(fā)送給匯聚節(jié)點。由于簇頭節(jié)點要完成數(shù)據(jù)融合并與匯聚節(jié)點通信等工作，量消耗相比簇內(nèi)節(jié)點較大，所以其簇頭節(jié)點的選舉必須是動態(tài)的，以均衡網(wǎng)絡能量，延長網(wǎng)絡的生命周期。

LEACH算法中簇頭選舉過程如下:節(jié)點產(chǎn)生一個0～1之間的隨機數(shù)，如果這個數(shù)小于閾值T(n)，則發(fā)布消息公告自己成為簇頭;在一輪循環(huán)中，如果節(jié)點已當選過簇頭，則把T(n)設置為0，以保證節(jié)點不會再次當選為簇頭;對于未當選過簇頭的節(jié)點，則將以T(n)概率當選;隨著當選過簇頭的節(jié)點數(shù)增加，剩余節(jié)點當選簇頭的T(n)隨之增大，節(jié)點產(chǎn)生小于T(n)的隨機數(shù)的概率隨之增大，所以節(jié)點當選簇頭的概率增大。當只剩下一個節(jié)點未當選時，T(n)=1，表示這個節(jié)點一定當選。T(n)可用公式(4)表示:

(4)

其中，P是簇頭在所有節(jié)點中所占的比例，r是選舉輪數(shù)，rmod(1/P)代表這一輪循環(huán)中當選過簇頭的節(jié)點個數(shù)，G是這輪循環(huán)中未當選過簇頭的節(jié)點集合。

LEACH算法只是對簇頭的選舉進行了說明，沒有解決在隨機選取簇頭過程中可能發(fā)生的網(wǎng)絡分割問題，某個節(jié)點在其覆蓋范圍內(nèi)可能沒有可用的簇頭。另外該算法需要較為嚴格的時間同步，也不能保證簇頭均勻分布，也未考慮節(jié)點的地理位置、節(jié)點的剩余能量以及節(jié)點的加入和死亡、外界環(huán)境的干擾等諸多問題。

2.2.2 GAF(Geographical adaptive fidelity)算法

Xu[7]等人在文獻中提出了一種基于地理位置的分簇算法GAF，該算法把監(jiān)測區(qū)域劃分為虛擬單元格，將節(jié)點按地理位置信息歸入相應的單元格;在各單元格中定期選舉一個節(jié)點為簇頭，使其處于活動狀態(tài)，其他節(jié)點則進入睡眠狀態(tài)。

GAF算法的執(zhí)行分為兩個階段，第一階段是劃分虛擬單元格。根據(jù)節(jié)點的位置信息和通信半徑，將網(wǎng)絡區(qū)域劃分成若干虛擬單元格，假設節(jié)點的通信半徑為R，正方形虛擬單元格區(qū)域邊長為r，為了保證相鄰兩個單元格內(nèi)的任意節(jié)點能相互通信，需要滿足公式(5)所示關系:

(5)

第二階段是虛擬單元格中簇頭節(jié)點的選擇。節(jié)點周期性的進入睡眠和工作狀態(tài)，每個節(jié)點都可以處于發(fā)現(xiàn)、活動以及睡眠三種狀態(tài)。網(wǎng)絡初始化時，所有節(jié)點都處在發(fā)現(xiàn)狀態(tài)，并通過互發(fā)消息獲得同一單元格中其他節(jié)點的信息。然后每個節(jié)點為自身定時器設定一個隨機值Ta，一旦定時器超時，則節(jié)點發(fā)布消息宣布自己成為簇頭，如果在超時之前收到其他節(jié)點成為簇頭的消息，說明此次競爭失敗，轉(zhuǎn)而進入睡眠狀態(tài)。成為簇頭的節(jié)點為自己設定一個活動時間Tb，在Tb期間其他節(jié)點只能處于發(fā)現(xiàn)或睡眠狀態(tài)，當Tb超時后，簇頭節(jié)點重新回到發(fā)現(xiàn)狀態(tài)。

由于節(jié)點處于偵聽狀態(tài)也需要消耗大量能量，讓節(jié)點盡量處于睡眠狀態(tài)能有效降低能耗，GAF是較早采用這種方法的算法。但這種基于地理位置進行分簇的算法對傳感器節(jié)點要求較嚴格，另外，GAF基于平面模型，節(jié)點間距離的鄰近并不表明可以直接通信，也未考慮到節(jié)點的剩余能量問題。

3 結(jié)束語

目前，無線傳感器網(wǎng)絡拓撲控制研究已經(jīng)有了初步的進展，一方面在研究自身特性的基礎上借鑒了ad hoc網(wǎng)絡的寶貴經(jīng)驗及成果，另一方面針對傳感器網(wǎng)絡自身某一方面的特點，提出了多種側(cè)重點不同的拓撲控制算法，推動了無線傳感器網(wǎng)絡拓撲控制研究的進一步發(fā)展。但同時也要注意到各種算法所存在的局限性，現(xiàn)有的算法只是針對某一特性而設計，只解決傳感器網(wǎng)絡中特定方面所存在的問題，未對網(wǎng)絡的綜合性能進行全面的考慮，大多數(shù)算法還只停留在理論研究的階段，未能充分考慮到在實際應用中可能出現(xiàn)的諸多影響網(wǎng)絡性能的因素，比如，外界環(huán)境對無線通信的干擾及節(jié)點失效后如何動態(tài)調(diào)整拓撲結(jié)構(gòu)等。除了上述所介紹的功率控制和分簇控制外，現(xiàn)在已逐漸引入了與其他拓撲控制算法相結(jié)合的啟發(fā)式節(jié)點喚醒和睡眠機制。由于功率和分簇控制解決拓撲控制存在單一性，不能綜合解決多個問題，所以目前將這兩種機制結(jié)合在一起研究一種新的拓撲機制逐漸成為無線傳感器網(wǎng)絡拓撲控制一個新的研究方向。綜上所述，拓撲控制還需要進一步研究，以強調(diào)實際應用為基礎，多種機制相結(jié)合，綜合考慮網(wǎng)絡的整體性能將是拓撲控制新的發(fā)展趨勢。

參考文獻:

[1] Akyildiz IF，Su W，Sankarasubramanias Y et al.A survey on sensor networks[J].IEEE Communications Magazine，2002，40(8):102-114.

[2] 張學.無線傳感器網(wǎng)絡的拓撲控制[J].軟件學報，2007，4(18).

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

[4] Kubisch M，Karl H，Wolisz A et al.Distributed algorithm for transmission power control in wireless sensor network[A].In:Proc of IEEE WCNC 2003.New Orleans: Louisiana，2003(3):16-20.

[5] Li N，Hou J C，Sha L.Design and analysis of an MST-based topology control algorithm.In:Proc 12th Joint Conf on IEEE Computer and Communication Societies (INFOCOM 2003)[C]，San Francisco，CA.Apr.2003.

[6] Heinzelman W R，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications，2002，1(4):660-670.

[7] Xu Y，Heidemann J，Estrin D.Geography-informed energy conservation for ad hoc routing[A]，In:Proc 7th Annual Int'l Conf on Mobile Computing and Networking (MobiCOM)，Rom，Italy，2001(6):70-84.