一種基于TopDisc的WSNs拓撲控制算法*

王慧嬌，張華成，黃廷磊

(1.中國科學院 電子學研究所，北京100080;2.桂林電子科技大學 計算機科學與工程學院, 廣西 桂林 541004)

一種基于TopDisc的WSNs拓撲控制算法*

王慧嬌1,2，張華成2，黃廷磊1

(1.中國科學院 電子學研究所，北京100080;2.桂林電子科技大學 計算機科學與工程學院, 廣西 桂林 541004)

針對無線傳感器網絡(WSNs)中無線信號動態波動變化時引起網絡鏈路不穩定和覆蓋范圍變小的問題，提出了一種基于TopDisc的WSNs拓撲控制算法。該算法通過引入拓撲控制參數控制網絡拓撲優化以適應無線信號變化，給出了拓撲創建過程，對算法進行了仿真實驗。仿真結果表明：改進的拓撲控制算法能夠提升WSNs對復雜無線電環境的適應能力，提高了資源利用率和鏈路可靠性。

TopDisc算法；無線傳感器網絡；拓撲控制；拓撲控制參數

0 引 言

無線傳感器網絡(WSNs)有著廣泛的應用，如遠程環境監控、目標跟蹤、事件檢測等。由于WSNs中節點的能量、帶寬限制等，滿足覆蓋和連通性則變得非常重要。拓撲控制是WSNs的重要研究問題，其目標是在保證覆蓋質量和連通質量的前提下，通過降低通信干擾、延長網絡生命周期、提高系統吞吐能力和MAC協議的效率提高網絡的可擴展性，從而形成一個優化的拓撲結構[1]。目前，WSNs的拓撲控制方法主要分為兩大類：基于覆蓋度的方法和基于連通性的方法[2]。基于覆蓋度的方法中較為典型的層次型網絡的睡眠調度算法有GAF[3],LEACH[4],TopDisc[5]等；非層次型網絡的睡眠調度算法典型的有PEAS[6],CCP[7]等。基于連通性的方法主要采用功率調控機制，較為典型的算法有DRNG/DLSS[8],LMA/LMN[9]等。

在TopDisc算法思想的基礎上，本文提出了一個WSNs拓撲控制算法，通過設置拓撲控制參數用于管理網絡拓撲的形成，并在層次型拓撲發現組織方面進行改進。

1 TopDisc算法概述與分析

TopDisc算法是由Deb B等人提出的一種基于圖論中的最小支配集問題的層次型分簇拓撲控制機制，利用無線的廣播特性，通過顏色標記來區分節點狀態，解決骨干網絡的拓撲形成問題。算法提出了三色法和四色法兩個具體節點標記方法[6]。兩種算法都是利用顏色標記理論找到簇頭節點，利用與傳輸距離呈反比的延時，使得一個黑色節點(即簇頭節點)覆蓋更大的區域，最終快速將密布的無線游離節點形成分簇，并在簇頭之間建立樹型結構。但該算法構建的層次型網絡靈活性不強，鏈路需要廣播和反向查詢，重復執行開銷大[10]，延時時間與邊的長度呈線性關系，并且沒有冗余，造成無線信號波動時容易造成鏈路不穩定，使得網絡的可靠性和吞吐率不高。

2 改進的TopDisc拓撲控制算法

2.1 算法描述

拓撲發現過程分為三個主要階段：簇頭節點發出拓撲發現請求、拓撲發現請求在網絡中傳播、覆蓋節點響應拓撲請求。按照此過程，網絡中的節點分為四色：黑色、灰色、白色、深灰色，其定義與四色法中的相似。同時用無向圖G=(V，E)表示WSNs，G中的節點分布在二維平面內,V={V0，V1,…，Vn}是拓撲圖中節點的集合，E是拓撲圖中邊的集合，圖G具有如下屬性：

1)G是自由樹；

2)G中任意兩個頂點由唯一一條路徑相連；

3)G是連通的，且|E|=|V|-1，從E中去掉任何邊后得到的圖都是非連通的；

4)G是無回路的，且|E|=|V|-1，G是無回路的，但添加任何邊到E中后得到的圖會產生回路。

在給定頻率、調制模式和數據長度情況下，無線信號達到閾值場強(Rs)時通信成功率為q，如果每條邊都達到Rs，則網絡中一灰色節點的成功率為qk(k為根到該灰色節點的跳數)。Rs定義為當無線信號能實現整個網絡成功率達到p的鏈路質量所需要的場強，一個白色節點收到廣播信息后將該信息場強和閾值Rs比較后，決定是否改變顏色和轉發廣播信息，Rs根據應用環境噪聲等因素計算得到，將Rs作為算法中的網絡拓撲控制參數。

算法的權值W′=無線通信的RSS-理想信號的SFM(system fade margin，鏈路系統裕量)。無線通信的RSS等于距離權值W=Lbf=32.5+20lgf+20lgD，其中，Lbf為自由空間損耗,dB;D為距離,km;f為頻率,MHz。SFM使得兩個節點之間保持一個比較理想的連接狀態，多數應用場合的信號波動在一定時間內符合泊松分布并且浮動范圍也是有規律的，因此，網絡的SFM數值是可行的，在算法中將SFM作為網絡拓撲的參數。

等待延時和發送延時的時間單位記為tD，在算法中作為一個控制參數,tD將影響WSNs的節點度。為了提高網絡自愈能力，每個節點被拓撲發現標記以后不再響應廣播信息,但是通過廣播信息不斷收集RSS達標的周邊節點建立備用鄰居表，用于當前鏈路出現故障后建立備用鏈路。

算法的目標是從起始節點出發，該節點作為自由樹的根，構建整個網絡的拓撲結構，算法具體步驟如下：

1)起始節點發布拓撲發現廣播信息；

2)白色節點收到根節點或者黑色節點的廣播信息，若RSS≥Rs,則標記自己為灰色，根據Tdelay=|RSS-SFM|·tD時間延時轉發廣播信息；

3)當白色節點收到灰色節點的信息，若RSS≥Rs則標記自己為深灰色，然后轉發廣播信息，在Tdelay=|RSS-SFM|·tD時間內沒有收到黑色的節點廣播，則把自己標記為黑色節點;否則,標記為灰色；

4)當白色節點收到深灰色節點廣播信息，若RSS≥Rs,則等待Tdelay=|RSS-SFM|·tD時間后發送廣播信息，如果在此時間內收到黑色節點的信息，則變為灰色;否則,變為黑色，變色后立刻發送廣播信息；

5)在廣播信息過程中直接建立自由樹的邊，成為黑色或者灰色節點后不再響應其他節點信息，但是記錄若RSS≥Rs黑色節點信號按照|RSS-SFM|順序從小到大排列生成備用鏈路表。

2.2 拓撲形成過程

參數SFM控制每個簇的覆蓋范圍，與簇半徑呈反比；參數Rs控制簇之間的距離，與距離呈反比。圖1給出了算法的拓撲形成過程與控制參數SFM和Rs值變小后拓撲的變化。拓撲從根節點開始建立，算法目標建立一個min{w(E)}的自由樹，可以把問題規約為圖論的最小生成樹，根據算法在發送廣播信息的先后順序和等待延時采用貪心策略，每次廣播后信號最接近SFM值的節點最先發出信息標記周邊的白色節點，收到標記節點的信息后會按照和理想信號差距的降序加入備用鏈路表。

圖1 拓撲形成過程與參數影響下的拓撲變化Fig 1 Process of topology formation and topology change under influence of parameters

當控制參數變小后，網絡發生變化從根節點A′簇開始向外擴散，覆蓋范圍變大，B′簇向邊緣變小。虛線是參數變化后改變的邊，在每一輪拓撲發現過程中，簇內的邊都最接近SFM值，簇之間的邊都最接近Rs值，根據給出的網絡可靠性分析，通過這兩個參數準確地把握拓撲的鏈路可靠性；同時這兩個參數也可以作為控制簇內和簇間的覆蓋范圍的變量，提高網絡拓撲的靈活性和適應能力。

3 算法仿真與性能分析

為了驗證算法的性能，采用Matlab和C++進行實驗，實現仿真場景和算法仿真，并加入障礙物的干擾數據。設定在300 m×300 m的區域內，隨機地散布了100個節點，無干擾時節點之間極限距離是20 m，無線基礎帶寬50 kB，PER小于0.001距離，Rs為18 m，SFM距離為16 m，障礙物干擾能力設定為0～5 m，并且在場地內按照一定線路游離移動的應用背景，測試數據包是30 bytes。根節點(原算法和改進算法的起始點)在一個邊緣位置，圖2、圖3分別給出了算法改進前后的仿真場景圖。

圖2 TopDisc算法仿真場景Fig 2 Simulation scenario of TopDisc algorithm

圖3 改進算法仿真場景Fig 3 Simulation scenario of improved algorithm

如表1所示，改進算法的黑色節點增加，無邊緣黑色節點，脫離拓撲的節點數目很少，仿真持續障礙物運行的時候會發現相比原算法，改進算法黑色節點總數波動很小，變化位置比較明顯并且隨機，網絡對信號適應能力提高使得死亡節點的生存周期變短、數量減少。

表1 改進效果評測表Tab 1 Evaluation table of improvement effect

由于障礙物的干擾測試數據是一個動態范圍，并且會隨機引起一些節點從拓撲中斷開，形成死亡節點，原算法這些節點在需要下一次拓撲發現中會被恢復，改進算法在收發數據包過程中自動恢復，在下一次拓撲發現中會調整黑色節點的位置。系統的吞吐量比較如圖4所示。仿真的無線性能沒有改變，但是由于鏈路質量提高，數據傳輸成功率提高從而改進算法提高了網絡的吞吐量。

圖4 兩種算法的系統吞吐量比較Fig 4 Comparison of system throughput of two algorithms

4 結束語

拓撲控制是實現WSNs應用的基礎技術之一。本文在TopDisc算法機制的基礎上給出了一種改進的拓撲發現算法。該算法利用無線鏈路的相關參數形成拓撲，對比TopDisc算法，本算法建立的網絡分簇質量高，對無線電環境變化適應能力強，死亡節點恢復速度快同時提高了系統的吞吐量。

[1] Jardosh S,Ranjan P.Survey:Topology control for wireless sensor networks[C]∥Proceedings of ICSCN 2008,Madras,India:IEEE,2008:422-427.

[2] Li Mo,Li Zhenjiang,Vasilakos A V.A survey on topology control in wireless sensor networks:Taxonomy,comparative study,and open issues[J].Proceedings of IEEE,2013,101(12):2538-2556.

[3] Xu Y,Heidemann J,Estrin D.Geography-informed energy conservation for Ad Hoc routing[C]∥Proc of 7th Int’l Conf on Mobile Computing and Networking(MobiCom),New York,USA,2001:70-84.

[4] Heinzelman W R,Chandrakasan A P,Balakrishnan H.An energy-efficient communication protocol for wireless microsensor networ-ks[C]∥Proceedings of HICSS 2000,Washington,USA,2000:3005-3014.

[5] Deb B，Bhatnagar S，Nath B．A topology discovery algorithm for sensor networks with applications to network management[R]．DCS Technical Report,DCS-TR-411，Rutgers University，2001：26-30.

[6] Ye F,Zhong G,Cheng J,et al.PEAS:A robust energy conserving protocol for long-lived sensor networks[C]∥Proceedings of ICDCS,Rhode Island,USA, IEEE,2003:28-37.

[7] Xing G,Wang X,Zhang Y,et al.Integrated coverage and connectivity configuration for energy conservation in sensor networks[J].ACM Transactions on Sensor Networks (TOSN),2005,1(1):36-72.

[8] Li N,Hou J C.Topology control in heterogeneous wireless networks:Problems and solutions[C]∥Proceedings of INFOCOM,New York,USA,IEEE,2004:232-243.

[9] Kubisch M,Karl H,Wolisz A,et al.Distributed algorithms for transmission power control in wireless sensor networks[C]∥IEEE WCNC,2003,New Orleans,USA,IEEE,2003:558-563.

[10] 孫利民,李建中,陳 渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005.

A kind of WSNs topology control algorithm based on TopDisc*

WANG Hui-jiao1,2, ZHANG Hua-cheng2, HUANG Ting-lei1

(1.Institute of Electronics,Chinese Academy of Sciences,Beijing 100080,China;2.School of Computer Science and Engineering,Guilin University of Electronic Technology,Guilin 541004,China)

Aiming at problem that dynamic fluctuations of wireless signal in wireless sensor networks(WSNs) may cause problems that network link becomes unstable and coverage range becomes smaller,a kind of WSNs topology control algorithm based on TopDisc is put forward.Topology control parameters which control network topology optimization are introduced to adapt to change of wireless signal,process of topology constructing is given,simulation experiment of this algorithm is carried out.Results of simulation show that improved topology control algorithm can improve adaptability of WSNs to complex radio environment and utilization rate of resources and link reliability.

TopDisc algorithm；WSNs；topology control；topology control parameter

10.13873/J.1000—9787(2014)10—0115—03

2014—07—07

國家自然科學基金資助項目(61163059)；廣西可信軟件重點實驗室資助項目(KX201204)

TP 393

A

1000—9787(2014)10—0115—03

王慧嬌(1976-)，女，遼寧鐵嶺人，博士研究生，副教授，碩士生導師，主要從事無線傳感器網絡、無線Mesh網絡、智能計算等研究。