ZigBee網(wǎng)絡(luò)拓?fù)淇梢暬佻F(xiàn)算法研究

任珍文，石繁榮

(1.西南科技大學(xué)國防科技學(xué)院，四川 綿陽 621010；2.西南科技大學(xué)信息工程學(xué)院，四川 綿陽 621010)

ZigBee網(wǎng)絡(luò)拓?fù)淇梢暬佻F(xiàn)算法研究

任珍文1，石繁榮2

(1.西南科技大學(xué)國防科技學(xué)院，四川 綿陽 621010；2.西南科技大學(xué)信息工程學(xué)院，四川 綿陽 621010)

基于ZigBee的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)在網(wǎng)絡(luò)性能分析、網(wǎng)絡(luò)節(jié)點部署、節(jié)點壓力測試、安全監(jiān)控等方面起著重要作用。但是在拓?fù)浣Y(jié)構(gòu)可視化時，由于網(wǎng)絡(luò)拓?fù)鋱D可視化模型會出現(xiàn)點覆蓋、邊交叉和圖形擁塞，導(dǎo)致算法復(fù)雜度高、耗時陡增，影響可視化效果。為了解決以上問題，并滿足實時在線顯示需求，提出了一種基于坐標(biāo)變換-虛擬節(jié)點模型的ZigBee Tree-Star型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化再現(xiàn)算法。該算法能夠自適應(yīng)節(jié)點變化。在節(jié)點數(shù)量較少時，層次算法模型對節(jié)點進行布局規(guī)劃；當(dāng)節(jié)點數(shù)量較多時，虛擬節(jié)點模型對布局進行擴展延伸。該算法對ZigBee網(wǎng)絡(luò)管理具有較高的參考價值。試驗表明，該算法所需時間復(fù)雜度與空間復(fù)雜度低，可解決大量邊交叉導(dǎo)致的布局混亂問題，并能適應(yīng)ZigBee網(wǎng)絡(luò)大規(guī)模節(jié)點的實時可視化需求。

無線傳感器網(wǎng)絡(luò)； 物聯(lián)網(wǎng)； ZigBee； 網(wǎng)絡(luò)拓?fù)洌?虛擬節(jié)點； 可視化； 網(wǎng)絡(luò)仿真

0 引言

將網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化再現(xiàn)用于遠程監(jiān)視或復(fù)雜網(wǎng)絡(luò)測控，是無線傳感器網(wǎng)絡(luò)領(lǐng)域的研究熱點之一。該方法具有最大限度保證監(jiān)控區(qū)域安全、提高管控效率與降低成本、迅速定位異常位置等優(yōu)點。

在拓?fù)浒l(fā)現(xiàn)算法中，大都采用Internet 控制報文協(xié)議(Internet control message protocal,ICMP)或底層鏈路協(xié)議發(fā)現(xiàn)網(wǎng)絡(luò)連接設(shè)備的互聯(lián)關(guān)系[1-2]。目前，ZigBee無線傳感器網(wǎng)絡(luò)的有效網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化再現(xiàn)算法仍然較少，常見的有復(fù)雜網(wǎng)絡(luò)社區(qū)劃分模型、Kamada和Kawai提出的能量模型(KK模型)、DH Kim布局算法(DH模型)、Fruchterman和Reingold提出的彈力模型(FR算法)[3]。這些算法能適用于芯片布線、集成器件排列等應(yīng)用場景，但具有算法復(fù)雜、耗時長、拓?fù)渚€交叉等缺點，應(yīng)用于ZigBee網(wǎng)絡(luò)拓?fù)鋄4]實時可視化再現(xiàn)的效果不太理想。

本文提出了基于坐標(biāo)變換的ZigBee Tree-Star型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化再現(xiàn)算法，能夠?qū)崟r檢測網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)變化，并進行可視化建模；提出的虛擬父節(jié)點模型，解決了繪圖界面擁擠、無序、交叉等問題。

1 拓?fù)湫畔⒉杉?/h2>

1.1 ZigBee節(jié)點組網(wǎng)

ZigBee協(xié)議棧是ZigBee協(xié)議的具體實現(xiàn)，采用分層模型并定義相關(guān)協(xié)議層。ZigBee協(xié)議由應(yīng)用層、網(wǎng)絡(luò)層、數(shù)據(jù)鏈路層和物理層構(gòu)成[5]。

ZigBee節(jié)點一般可分為3種類型：ZigBee協(xié)調(diào)器、ZigBee路由器和ZigBee終端。1個ZigBee網(wǎng)絡(luò)只能有1個協(xié)調(diào)器，但可以有多個路由器和終端。協(xié)調(diào)器負(fù)責(zé)組建、管理和控制1個ZigBee網(wǎng)絡(luò)，并收集信息；路由器能夠路由并采集信息；終端只能采集信息。ZigBee協(xié)調(diào)器和路由器可稱為全功能設(shè)備(full function device,FFD)，ZigBee終端也可稱為簡化功能設(shè)備(reduced function device,RFD)[6]。

ZigBee無線傳感器網(wǎng)由多個ZigBee節(jié)點通過無線信道互聯(lián)而成。它支持星型、樹狀和網(wǎng)狀這3種類型的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。其中，星型與樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)較為常用[6-7]。

1.2 網(wǎng)絡(luò)拓?fù)湫畔⒉杉?/h3>

網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的實時構(gòu)建，需要及時獲取父子節(jié)點之間的關(guān)聯(lián)關(guān)系。在ZigBee無線傳感器網(wǎng)絡(luò)中，除了協(xié)調(diào)器節(jié)點外，其他節(jié)點都有父節(jié)點。所有節(jié)點的關(guān)聯(lián)信息在其上線時都將通過無線方式主動發(fā)送給協(xié)調(diào)器節(jié)點，并由協(xié)調(diào)器節(jié)點通過串口轉(zhuǎn)發(fā)給上位機，最后由上位機提取有效的關(guān)聯(lián)信息來動態(tài)構(gòu)建網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖[8-9]。

ZigBee節(jié)點上電后會自主尋找并加入網(wǎng)絡(luò)。某些節(jié)點可能由于傳輸距離﹑環(huán)境影響等因素而失去連接。因此，需要針對節(jié)點上線和下線分別進行設(shè)計。在子節(jié)點上線時，除了協(xié)調(diào)器節(jié)點以外的節(jié)點都會上傳16位的父節(jié)點短地址信息到遠程控制臺，以通知某父節(jié)點其子節(jié)點上線；在子節(jié)點下線時，則由該子節(jié)點的父節(jié)點上傳該下線節(jié)點的信息。數(shù)據(jù)幀結(jié)構(gòu)如圖1所示。

圖1 數(shù)據(jù)幀結(jié)構(gòu)圖

Fig.1 Structure of data frame

2 虛擬節(jié)點拓?fù)湓佻F(xiàn)算法

本文以二維坐標(biāo)變換為基礎(chǔ)，設(shè)計了一種ZigBee Tree-Star型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化再現(xiàn)算法，并依托坐標(biāo)變換，提出了該算法模型。

2.1 坐標(biāo)變換模型

設(shè)η1,η2,…,ηk和ζ1,ζ2,…，ζk均為V的基，并設(shè)ζi在η1,η2,…,ηk中的坐標(biāo)為(c1i,c2i,…,cki)，則有如下矩陣C：

(1)

式中：C為從η1,η2,…,ηk到ζ1,ζ2,…,ζk的過渡矩陣。這2個基之間的關(guān)系為：

(ζ1,ζ2,…,ζk)=(η1,η2,…,ηk)C

(2)

由式(2)可得:

α=(η1,η2,…,ηk)x=(ζ1,ζ2,…,ζk)y=

(η1,η2,…,ηk)Cy

(3)

式中：x為V中向量a在η1,η2,…,ηk中的坐標(biāo)；y為V中向量a在ζ1,ζ2,…,ζk中的坐標(biāo)。

由式(2)、式(3)可得如下坐標(biāo)變換：

(4)

在二維坐標(biāo)系中，C可被看作是坐標(biāo)繞z軸旋轉(zhuǎn)θ后的結(jié)果。設(shè)(a,b,0)為ζ1,ζ2,…,ζk中的坐標(biāo)。在基坐標(biāo)系(通常以繪圖窗口作為基準(zhǔn))下，假設(shè)父節(jié)點坐標(biāo)為(pX,pY)，子節(jié)點坐標(biāo)為(cX,cY)，父子坐標(biāo)連線與父親坐標(biāo)軸夾角為θ，則有：

(5)

式中：(cInPX,cInPY,φ)為子節(jié)點在父節(jié)點坐標(biāo)系下的坐標(biāo)。

2.2 層次節(jié)點模型建立

在ZigBee網(wǎng)絡(luò)中，協(xié)調(diào)器用M表示；路由節(jié)點用Rk1表示，k1∈N+，k1≤65 534；終端節(jié)點用Ek2表示,k2∈N+，k2≥65 534,k1+k2≤65 535。

繪圖時，規(guī)劃每個父節(jié)點下第一層可以掛載的子節(jié)點數(shù)。父節(jié)點A與其第一層子節(jié)點B連線長度為Rk。B又作為其他節(jié)點的父節(jié)點，其子節(jié)點第一層連線長度為Rk+1。父、子節(jié)點區(qū)域覆蓋關(guān)系如圖2所示。

圖2 父、子節(jié)點區(qū)域覆蓋關(guān)系圖

2.3 層次節(jié)點坐標(biāo)模型

在ZigBee Tree-Star網(wǎng)絡(luò)中，網(wǎng)絡(luò)拓?fù)潢P(guān)聯(lián)的最小單位是互為父子關(guān)系的2個節(jié)點，除終端節(jié)點外的其他節(jié)點都可能是父節(jié)點，除協(xié)調(diào)器外的其他節(jié)點都可能有父節(jié)點。假設(shè)節(jié)點B為節(jié)點A的子節(jié)點，節(jié)點A坐標(biāo)為(xa,ya)，節(jié)點B坐標(biāo)為(xb,yb)，且假設(shè)(xa,ya)、(xb,yb)為已知。在此算法中，子節(jié)點以父節(jié)點為圓心，在其外部按照層次結(jié)構(gòu)逆時針旋轉(zhuǎn)擴張，兩者相對關(guān)系如圖3所示。

圖3(a)描述了父、子節(jié)點個數(shù)比為1∶1的位置關(guān)系，這是最小的單元。在實際ZigBee網(wǎng)絡(luò)中，1個父節(jié)點可能與多個子節(jié)點交互，可能是如圖3(b)所示的1∶4關(guān)系。尤其對于ZigBee協(xié)調(diào)器，其不僅是網(wǎng)絡(luò)的建立者，而且是每個加入網(wǎng)絡(luò)的ZigBee節(jié)點在搜尋可用網(wǎng)絡(luò)時的首選接入點。故1個ZigBee協(xié)調(diào)器可以有多個子節(jié)點(路由器或者終端)。在此算法中，為了避免網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)線交叉，采用了以父節(jié)點為圓心、其他節(jié)點圍繞圓心按照2.1節(jié)計算得出的θ作為旋轉(zhuǎn)角度依次排列的結(jié)構(gòu)，即圖3(b)所示的子節(jié)點在父節(jié)點周圍分布規(guī)律。

圖3 父、子節(jié)點關(guān)系圖

當(dāng)網(wǎng)絡(luò)層次加深時，3層(網(wǎng)絡(luò)深度為3)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖4所示。

圖4 三層網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

設(shè)O(0,0)為ZigBee網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)相對于繪圖窗口的基坐標(biāo)系原點，則節(jié)點B、節(jié)點C在這個網(wǎng)絡(luò)中的坐標(biāo)分別為B(xb,yb)、C(xc,yc)。節(jié)點B坐標(biāo)為：

(6)

式中：R1為節(jié)點B到原點的距離；θ1為節(jié)點B到原點連線與x軸夾角。

(7)

式中：R2為節(jié)點B到節(jié)點C的距離；θ2為節(jié)點B到節(jié)點C連線與節(jié)點B到原點連線的夾角。

相對于基坐標(biāo)系，由式(5)～式(7)，可得C(xc,yc)的坐標(biāo)為：

(8)

式中：θ′為θ2與θ1之差。

由以上推導(dǎo)，可得2個互為父子關(guān)系以及互為爺孫關(guān)系節(jié)點的坐標(biāo)關(guān)系。在ZigBee網(wǎng)絡(luò)結(jié)構(gòu)中，所有節(jié)點之間的關(guān)系都可以通過這2種坐標(biāo)關(guān)系來計算。

2.4 虛擬節(jié)點模型

根據(jù)2.3節(jié)中描述的節(jié)點層次關(guān)系，將每一層節(jié)點數(shù)限制為8個。繪圖時，1個父節(jié)點下最多可以有8個子節(jié)點。在ZigBee網(wǎng)絡(luò)中，父子節(jié)點的比例關(guān)系可能大于1∶8。本文提出了一種虛擬節(jié)點模型，即虛擬化父節(jié)點算法，解決了因繪圖界面子節(jié)點過多而導(dǎo)致的擁擠無序。

圖5 子節(jié)點分布圖

通過虛擬化父節(jié)點算法，1個父節(jié)點可以支持的1層子節(jié)點為7×8個。若繼續(xù)虛擬父節(jié)點，則子節(jié)點個數(shù)可以無限擴展。

圖6 虛擬化父節(jié)點示意圖

3 拓?fù)淇梢暬惴▽崿F(xiàn)

3.1 算法實現(xiàn)

為了對節(jié)點之間的關(guān)聯(lián)信息進行描述，采用結(jié)構(gòu)體NodeRelation作為數(shù)據(jù)結(jié)構(gòu)、macAddr作為每個節(jié)點的唯一的身份識別號碼。當(dāng)子節(jié)點上線時，子節(jié)點需要置parentAddr，表明自己的父節(jié)點地址；當(dāng)子節(jié)點掉線時，父節(jié)點需要置lostChildAddr，表明子節(jié)點失去聯(lián)系。

本文算法對從串口模塊收取的信息進行分析并解析?？傮w算法思想如下。以子節(jié)點作為遞歸更新拓?fù)湫畔⒌絑igBee網(wǎng)絡(luò)拓?fù)錁涞膮f(xié)調(diào)器根節(jié)點。若收到協(xié)調(diào)器上線信息，在繪圖窗口中構(gòu)造協(xié)調(diào)器節(jié)點并位于中心。若收到子節(jié)點上線的信息，根據(jù)parentAddr查找對應(yīng)的父節(jié)點索引，由其父節(jié)點出發(fā)，計算該子節(jié)點在繪圖窗口中的邏輯坐標(biāo)并繪圖。若收到子節(jié)點下線的信息，根據(jù)lostChildAddr查找到失去聯(lián)系的子節(jié)點的索引，在數(shù)據(jù)結(jié)構(gòu)中抹去該子節(jié)點記錄，同時在繪圖窗口中擦除該子節(jié)點。

用N表示節(jié)點數(shù)量，該算法需要對節(jié)點進行3次遍歷，因此算法時間復(fù)雜度為O(N)。在計算過程中需要保存N個節(jié)點的關(guān)聯(lián)信息，因此該算法的空間復(fù)雜度為S(N)。

3.2 試驗測試效果

前期開發(fā)的基于ZigBee的無線傳感器網(wǎng)絡(luò)測試平臺，采用ZigBee芯片CC2530，并自主設(shè)計傳感網(wǎng)絡(luò)硬件及其軟件；以計算機作為上位機，對傳感器采集的數(shù)據(jù)進行處理與顯示；ZigBee協(xié)調(diào)器節(jié)點收集傳感節(jié)點信息后，通過串口傳送至上位機進行數(shù)據(jù)處理。

試驗環(huán)境包含了1個協(xié)調(diào)器、3個路由器和14個終端。當(dāng)所有節(jié)點上線時，該ZigBee網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖7所示。

圖7 ZigBee網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

由圖7可知，協(xié)調(diào)器節(jié)點進行了兩次虛擬化。當(dāng)有節(jié)點掉線時，繪圖窗口也能響應(yīng)并更新。通過試驗，驗證了該算法的有效性和可靠性。

理論分析表明，該算法針對ZigBee Tree-Star型網(wǎng)絡(luò)進行了特殊設(shè)計，具有優(yōu)秀的時間復(fù)雜度和空間復(fù)雜度，更有利于設(shè)備實現(xiàn)網(wǎng)絡(luò)管理。

4 結(jié)束語

ZigBee技術(shù)作為近距離應(yīng)用、低復(fù)雜度、低功耗、低速率、低成本的雙向無線通信技術(shù)，有著廣闊的市場前景。為了更好地管理節(jié)點，發(fā)揮拓?fù)浣Y(jié)構(gòu)在網(wǎng)絡(luò)性能分析研究、網(wǎng)絡(luò)節(jié)點部署、節(jié)點壓力測試、安全測控等方面的重要作用，本文設(shè)計的ZigBee Tree-Star型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可視化再現(xiàn)算法，彌補了大規(guī)模節(jié)點在線時，拓?fù)淅L圖混亂與無序的不足，同時為客戶提供了生動的可視化界面。試驗測試表明，該算法高效、可靠，能動態(tài)捕捉節(jié)點上下線。該算法不僅可以應(yīng)用于ZigBee協(xié)議，而且對于其他Tree-Star型網(wǎng)絡(luò)也有較高的參考價值。

[1] 王張超,張彥,張德棟,等.一種改進的網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)算法及實現(xiàn)[J].鐵路計算機應(yīng)用,2017(5):47-52.

[2] 朱海濱.網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)技術(shù)探析[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用,2017(3):26-27.

[3] 吳向成.基于ZigBee的無線傳感網(wǎng)絡(luò)拓?fù)浞治鯷J].江漢大學(xué)學(xué)報(自然科學(xué)版),2016(3):253-256.

[4] 李運佳.鏈路層網(wǎng)絡(luò)拓?fù)渥詣影l(fā)現(xiàn)算法研究[J].軟件導(dǎo)刊,2016(2):57-59.

[5] 賈百韜,艾中良.多域網(wǎng)絡(luò)邏輯拓?fù)洳季炙惴ㄑ芯縖J].軟件,2017(1):93-97.

[6] 劉宏偉，石繁榮，陳雪冬.石英撓性加速度計在線測試與分析系統(tǒng)[J].自動化儀表，2017,38(3)：63-64.

[7] 黎冠,劉永濤,卜祥麗,等.基于ZigBee的超低功耗凍結(jié)井壁無線測溫系統(tǒng)[J].自動化儀表，2016,37(5)：44-45.

[8] 梁晟,萬羊所.基于節(jié)點屬性的啟發(fā)式網(wǎng)絡(luò)拓?fù)鋱D布局算法[J].計算機工程與應(yīng)用,2016(20):122-126.

[9] 王珍,康琳,單洪,等.基于隨機幾何的網(wǎng)絡(luò)拓?fù)涿芏瓤刂颇Ｐ脱芯縖J].計算機應(yīng)用研究,2017(1):170-172.

StudyontheZigBeeNetworkTopologyVisualizationReproductionAlgorithm

REN Zhenwen1,SHI Fanrong2

(1.School of National Defense Science and Technology，Southwest University of Science and Technology,Mianyang 621010,China;2.School of Information Engineering，Southwest University of Science and Technology,Mianyang 621010,China)

The network topology structure of ZigBee plays an important role in network performance analysis, network node deployment, node stress test and safety monitoring. Due to the large scale network , the point coverage, edge crossing and graphic congestion may occur in the visualization model of the network topology, thus the complexity and time consuming of algorithm would be increased, thus the effect of visualization is affected. To solve these problems and meet the real-time online display demand，a ZigBee Tree-Star WSN topologic visualization reproduction algorithm based on coordinate transformation virtual node model is proposed, which can adaptively change the nodes. The hierarchical algorithm models plan the layout of the nodes when the number of nodes is small. The virtual node model extends the layout when the number of nodes is large. This algorithm has also high reference value for ZigBee network management. Experiments show that this algorithm features less time and low spatial complexity, which can solve the problem of chaotic layout due to a large number of intersections, and adapt to the large-scale node online visualization requirements of ZigBee network.

WSN； Internet of things； ZigBee； Network topology； Virtual node； Visualization； Network simulation

修改稿收到日期:2017-07-13

國家自然科學(xué)基金資助項目(61601383、41604088、41604153)、國家重大科研儀器設(shè)備研制專項基金資助項目(41227802)

任珍文(1987—)，男，碩士，講師，主要從事網(wǎng)絡(luò)控制、智能信息處理與軟件開發(fā)等方向的研究，E-mail:rzw@unix8.net

TH39；TP391.9

A

10.16086/j.cnki.issn1000-0380.201712020