王慧嬌，張華成，黃廷磊

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

一種基于TopDisc的WSNs拓?fù)淇刂扑惴?

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

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

針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)(WSNs)中無(wú)線(xiàn)信號(hào)動(dòng)態(tài)波動(dòng)變化時(shí)引起網(wǎng)絡(luò)鏈路不穩(wěn)定和覆蓋范圍變小的問(wèn)題，提出了一種基于TopDisc的WSNs拓?fù)淇刂扑惴?。該算法通過(guò)引入拓?fù)淇刂茀?shù)控制網(wǎng)絡(luò)拓?fù)鋬?yōu)化以適應(yīng)無(wú)線(xiàn)信號(hào)變化，給出了拓?fù)鋭?chuàng)建過(guò)程，對(duì)算法進(jìn)行了仿真實(shí)驗(yàn)。仿真結(jié)果表明：改進(jìn)的拓?fù)淇刂扑惴軌蛱嵘齏SNs對(duì)復(fù)雜無(wú)線(xiàn)電環(huán)境的適應(yīng)能力，提高了資源利用率和鏈路可靠性。

TopDisc算法；無(wú)線(xiàn)傳感器網(wǎng)絡(luò)；拓?fù)淇刂?；拓?fù)淇刂茀?shù)

0 引 言

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

在TopDisc算法思想的基礎(chǔ)上，本文提出了一個(gè)WSNs拓?fù)淇刂扑惴ǎㄟ^(guò)設(shè)置拓?fù)淇刂茀?shù)用于管理網(wǎng)絡(luò)拓?fù)涞男纬?，并在層次型拓?fù)浒l(fā)現(xiàn)組織方面進(jìn)行改進(jìn)。

1 TopDisc算法概述與分析

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

2 改進(jìn)的TopDisc拓?fù)淇刂扑惴?/h2>

2.1 算法描述

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

1)G是自由樹(shù)；

2)G中任意兩個(gè)頂點(diǎn)由唯一一條路徑相連；

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

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

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

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

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

算法的目標(biāo)是從起始節(jié)點(diǎn)出發(fā)，該節(jié)點(diǎn)作為自由樹(shù)的根，構(gòu)建整個(gè)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，算法具體步驟如下：

1)起始節(jié)點(diǎn)發(fā)布拓?fù)浒l(fā)現(xiàn)廣播信息；

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

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

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

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

2.2 拓?fù)湫纬蛇^(guò)程

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

圖1 拓?fù)湫纬蛇^(guò)程與參數(shù)影響下的拓?fù)渥兓疐ig 1 Process of topology formation and topology change under influence of parameters

當(dāng)控制參數(shù)變小后，網(wǎng)絡(luò)發(fā)生變化從根節(jié)點(diǎn)A′簇開(kāi)始向外擴(kuò)散，覆蓋范圍變大，B′簇向邊緣變小。虛線(xiàn)是參數(shù)變化后改變的邊，在每一輪拓?fù)浒l(fā)現(xiàn)過(guò)程中，簇內(nèi)的邊都最接近SFM值，簇之間的邊都最接近Rs值，根據(jù)給出的網(wǎng)絡(luò)可靠性分析，通過(guò)這兩個(gè)參數(shù)準(zhǔn)確地把握拓?fù)涞逆溌房煽啃裕煌瑫r(shí)這兩個(gè)參數(shù)也可以作為控制簇內(nèi)和簇間的覆蓋范圍的變量，提高網(wǎng)絡(luò)拓?fù)涞撵`活性和適應(yīng)能力。

3 算法仿真與性能分析

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

圖2 TopDisc算法仿真場(chǎng)景Fig 2 Simulation scenario of TopDisc algorithm

圖3 改進(jìn)算法仿真場(chǎng)景Fig 3 Simulation scenario of improved algorithm

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

表1 改進(jìn)效果評(píng)測(cè)表Tab 1 Evaluation table of improvement effect

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

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

4 結(jié)束語(yǔ)

拓?fù)淇刂剖菍?shí)現(xiàn)WSNs應(yīng)用的基礎(chǔ)技術(shù)之一。本文在TopDisc算法機(jī)制的基礎(chǔ)上給出了一種改進(jìn)的拓?fù)浒l(fā)現(xiàn)算法。該算法利用無(wú)線(xiàn)鏈路的相關(guān)參數(shù)形成拓?fù)?，?duì)比TopDisc算法，本算法建立的網(wǎng)絡(luò)分簇質(zhì)量高，對(duì)無(wú)線(xiàn)電環(huán)境變化適應(yīng)能力強(qiáng)，死亡節(jié)點(diǎn)恢復(fù)速度快同時(shí)提高了系統(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ú)線(xiàn)傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61163059)；廣西可信軟件重點(diǎn)實(shí)驗(yàn)室資助項(xiàng)目(KX201204)

TP 393

A

1000—9787(2014)10—0115—03

王慧嬌(1976-)，女，遼寧鐵嶺人，博士研究生，副教授，碩士生導(dǎo)師，主要從事無(wú)線(xiàn)傳感器網(wǎng)絡(luò)、無(wú)線(xiàn)Mesh網(wǎng)絡(luò)、智能計(jì)算等研究。