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，表明子节点失去联系。

本文算法对从串口模块收取的信息进行分析并解析。总体算法思想如下。以子节点作为递归更新拓扑信息到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