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

王慧嬌，張華成，黃廷磊

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

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

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

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

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

TopDisc算法；無線傳感器網(wǎng)絡；拓撲控制；拓撲控制參數(shù)

0 引 言

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

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

1 TopDisc算法概述與分析

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

2 改進的TopDisc拓撲控制算法

2.1 算法描述

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

1)G是自由樹；

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

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

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

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

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

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

算法的目標是從起始節(jié)點出發(fā)，該節(jié)點作為自由樹的根，構(gòu)建整個網(wǎng)絡的拓撲結(jié)構(gòu)，算法具體步驟如下：

1)起始節(jié)點發(fā)布拓撲發(fā)現(xiàn)廣播信息；

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

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

4)當白色節(jié)點收到深灰色節(jié)點廣播信息，若RSS≥Rs,則等待Tdelay=|RSS-SFM|·tD時間后發(fā)送廣播信息，如果在此時間內(nèi)收到黑色節(jié)點的信息，則變?yōu)榛疑?否則,變?yōu)楹谏?，變色后立刻發(fā)送廣播信息；

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

2.2 拓撲形成過程

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

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

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

3 算法仿真與性能分析

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

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

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

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

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

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

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

4 結(jié)束語

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

[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] 孫利民,李建中,陳 渝,等.無線傳感器網(wǎng)絡[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-)，女，遼寧鐵嶺人，博士研究生，副教授，碩士生導師，主要從事無線傳感器網(wǎng)絡、無線Mesh網(wǎng)絡、智能計算等研究。