ZigBee網絡拓撲可視化再現算法研究

任珍文，石繁榮

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

ZigBee網絡拓撲可視化再現算法研究

任珍文1，石繁榮2

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

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

無線傳感器網絡； 物聯網； ZigBee； 網絡拓撲； 虛擬節點； 可視化； 網絡仿真

0 引言

將網絡拓撲結構可視化再現用于遠程監視或復雜網絡測控，是無線傳感器網絡領域的研究熱點之一。該方法具有最大限度保證監控區域安全、提高管控效率與降低成本、迅速定位異常位置等優點。

在拓撲發現算法中，大都采用Internet 控制報文協議(Internet control message protocal,ICMP)或底層鏈路協議發現網絡連接設備的互聯關系[1-2]。目前，ZigBee無線傳感器網絡的有效網絡拓撲結構可視化再現算法仍然較少，常見的有復雜網絡社區劃分模型、Kamada和Kawai提出的能量模型(KK模型)、DH Kim布局算法(DH模型)、Fruchterman和Reingold提出的彈力模型(FR算法)[3]。這些算法能適用于芯片布線、集成器件排列等應用場景，但具有算法復雜、耗時長、拓撲線交叉等缺點，應用于ZigBee網絡拓撲[4]實時可視化再現的效果不太理想。

本文提出了基于坐標變換的ZigBee Tree-Star型網絡拓撲結構可視化再現算法，能夠實時檢測網絡拓撲結構變化，并進行可視化建模；提出的虛擬父節點模型，解決了繪圖界面擁擠、無序、交叉等問題。

1 拓撲信息采集

1.1 ZigBee節點組網

ZigBee協議棧是ZigBee協議的具體實現，采用分層模型并定義相關協議層。ZigBee協議由應用層、網絡層、數據鏈路層和物理層構成[5]。

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

ZigBee無線傳感器網由多個ZigBee節點通過無線信道互聯而成。它支持星型、樹狀和網狀這3種類型的網絡拓撲結構。其中，星型與樹型網絡拓撲結構較為常用[6-7]。

1.2 網絡拓撲信息采集

網絡拓撲結構的實時構建，需要及時獲取父子節點之間的關聯關系。在ZigBee無線傳感器網絡中，除了協調器節點外，其他節點都有父節點。所有節點的關聯信息在其上線時都將通過無線方式主動發送給協調器節點，并由協調器節點通過串口轉發給上位機，最后由上位機提取有效的關聯信息來動態構建網絡拓撲結構圖[8-9]。

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

圖1 數據幀結構圖

Fig.1 Structure of data frame

2 虛擬節點拓撲再現算法

本文以二維坐標變換為基礎，設計了一種ZigBee Tree-Star型網絡拓撲結構可視化再現算法，并依托坐標變換，提出了該算法模型。

2.1 坐標變換模型

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

(1)

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

(ζ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中的坐標；y為V中向量a在ζ1,ζ2,…,ζk中的坐標。

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

(4)

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

(5)

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

2.2 層次節點模型建立

在ZigBee網絡中，協調器用M表示；路由節點用Rk1表示，k1∈N+，k1≤65 534；終端節點用Ek2表示,k2∈N+，k2≥65 534,k1+k2≤65 535。

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

圖2 父、子節點區域覆蓋關系圖

2.3 層次節點坐標模型

在ZigBee Tree-Star網絡中，網絡拓撲關聯的最小單位是互為父子關系的2個節點，除終端節點外的其他節點都可能是父節點，除協調器外的其他節點都可能有父節點。假設節點B為節點A的子節點，節點A坐標為(xa,ya)，節點B坐標為(xb,yb)，且假設(xa,ya)、(xb,yb)為已知。在此算法中，子節點以父節點為圓心，在其外部按照層次結構逆時針旋轉擴張，兩者相對關系如圖3所示。

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

圖3 父、子節點關系圖

當網絡層次加深時，3層(網絡深度為3)網絡拓撲結構如圖4所示。

圖4 三層網絡拓撲結構圖

設O(0,0)為ZigBee網絡拓撲結構相對于繪圖窗口的基坐標系原點，則節點B、節點C在這個網絡中的坐標分別為B(xb,yb)、C(xc,yc)。節點B坐標為：

(6)

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

(7)

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

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

(8)

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

由以上推導，可得2個互為父子關系以及互為爺孫關系節點的坐標關系。在ZigBee網絡結構中，所有節點之間的關系都可以通過這2種坐標關系來計算。

2.4 虛擬節點模型

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

圖5 子節點分布圖

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

圖6 虛擬化父節點示意圖

3 拓撲可視化算法實現

3.1 算法實現

為了對節點之間的關聯信息進行描述，采用結構體NodeRelation作為數據結構、macAddr作為每個節點的唯一的身份識別號碼。當子節點上線時，子節點需要置parentAddr，表明自己的父節點地址；當子節點掉線時，父節點需要置lostChildAddr，表明子節點失去聯系。

本文算法對從串口模塊收取的信息進行分析并解析?？傮w算法思想如下。以子節點作為遞歸更新拓撲信息到ZigBee網絡拓撲樹的協調器根節點。若收到協調器上線信息，在繪圖窗口中構造協調器節點并位于中心。若收到子節點上線的信息，根據parentAddr查找對應的父節點索引，由其父節點出發，計算該子節點在繪圖窗口中的邏輯坐標并繪圖。若收到子節點下線的信息，根據lostChildAddr查找到失去聯系的子節點的索引，在數據結構中抹去該子節點記錄，同時在繪圖窗口中擦除該子節點。

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

3.2 試驗測試效果

前期開發的基于ZigBee的無線傳感器網絡測試平臺，采用ZigBee芯片CC2530，并自主設計傳感網絡硬件及其軟件；以計算機作為上位機，對傳感器采集的數據進行處理與顯示；ZigBee協調器節點收集傳感節點信息后，通過串口傳送至上位機進行數據處理。

試驗環境包含了1個協調器、3個路由器和14個終端。當所有節點上線時，該ZigBee網絡拓撲結構如圖7所示。

圖7 ZigBee網絡拓撲結構圖

由圖7可知，協調器節點進行了兩次虛擬化。當有節點掉線時，繪圖窗口也能響應并更新。通過試驗，驗證了該算法的有效性和可靠性。

理論分析表明，該算法針對ZigBee Tree-Star型網絡進行了特殊設計，具有優秀的時間復雜度和空間復雜度，更有利于設備實現網絡管理。

4 結束語

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

[1] 王張超,張彥,張德棟,等.一種改進的網絡拓撲發現算法及實現[J].鐵路計算機應用,2017(5):47-52.

[2] 朱海濱.網絡拓撲發現技術探析[J].網絡安全技術與應用,2017(3):26-27.

[3] 吳向成.基于ZigBee的無線傳感網絡拓撲分析[J].江漢大學學報(自然科學版),2016(3):253-256.

[4] 李運佳.鏈路層網絡拓撲自動發現算法研究[J].軟件導刊,2016(2):57-59.

[5] 賈百韜,艾中良.多域網絡邏輯拓撲布局算法研究[J].軟件,2017(1):93-97.

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

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

[8] 梁晟,萬羊所.基于節點屬性的啟發式網絡拓撲圖布局算法[J].計算機工程與應用,2016(20):122-126.

[9] 王珍,康琳,單洪,等.基于隨機幾何的網絡拓撲密度控制模型研究[J].計算機應用研究,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

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

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

TH39；TP391.9

A

10.16086/j.cnki.issn1000-0380.201712020