一种ZigBee无线传感器网络拓扑发现算法
第38卷
第4期
计算机工程2012年2月
、,01.38
No.4
Compu时Engineering
Febnlarv2012
・网络与通信・
文章■号t
l伽0_—猢(∞12)04._0呻7—03
文■撂识码:A
中田分奏号t11,393
一种ZigBee无线传感器网络拓扑发现算法
刘新宇。事兵,黄疆,瞻呜
f解放军理工大学指挥自动化学院.南京2lO007)
l叠:zjgBee无线传感器网络(wsN)不同于有线网络,由于无法直接现察到其网络结构和设备部署情况,因此不捌于对zigBcewsN进行管理和控制。为解决该问题.提出一种针对zigBeewsN的拓扑发现算法(zigBeeTopo),确定弼络中的活肤节点以及节点之问的相互关关朔:无线传感器弼络;zigB犯协议栈;网络拓扑;发现算法;可视化
系,设计wsN拓扑管理模块,实现zigB∞网络拓扑的可视化。测试结果表明,该算法能正确发现多种wsN拓扑。
T0pologyDiscoVeryAlgorithmforZigBee、virdessSensorNetwork
LIIJ
xiⅡ・yIl,UBi嘴,HUANG
Shan,C胍NMilIg
(InsIituteofcomm柚dAutomatlon,PLAunive作i‘y0fscielIce
andlkhnolog弘N删jng
2I0007.china)
IAkt噶ctl
Jl
c扑notd№ctly
ob∞n,c恤s帅cnIre
oftIlezjgB钟wl仲lesssensorNetwork(wsN)as山Bwirednelworks.Th“proMemmakes“
d潲cult协m粕唱e
andcontr0Ime
ZjgBecWSM丁osolveth妇p∞blem,adi靶ovedngZlgB∞wi他kss
scnsor
network
10pology出90nl量lmcaIled
zjgBeeTbpoi5p。Dposcd士0
dc塘咖ine
acclve
nctworknodes蛆dtIleir坨1ationshipByd雌igfIi“g出cwi陀ksss曲sorⅡetworks岫poIo科m蚰89e
module,itc锄make吐KzigB∞nc‘work婶oJogy”isibIe.Tcn咒sults
sIlow
tlIat曲sd90d血mc柚discovervariHyofwhIess姥nsor
network
topoJogiesconecⅡy
IKeywordslwi佗lesssensor№【work(wsN):zigB∞pmtocoIs雠k;ne嘶叫k‘叩oIogy;击scoveIydg耐tllrⅡ:Visu神iz撕on
∞I:10.3969/j.issn.1000-3428.201204.032
l概述
一层提供服务,服务可以分为2类:数据传输服务和管理控体积小而价格低的无线传癔器的重要性日益增长,它们制服务
要求共享一个平台。使彼此能够通信并且共享组件以降低成本。lEEE
80215
4标准描述了用于个人域联网器件的无线和
媒体访问控制协议。这些协议为了在一个专用无线芯片上的硬件的实现而定义。传感器网络界已经开始使用这些协议,这些芯片广泛应用于无线搏戏机控制器,环境、医疗和建筑口ⅢccⅡⅫ2*监测仪器,采暖通风传感器等方面”。J。
囝m¨川!”4杯准IEEE
802.15.4协议希望支持各种各样的应用,而许多应
用是与所用传感器当前的位置有关。例如,当一个仓库的某一;:≮嚣驴啪
个温虚传藤器发出报警信号时,希望从可视化界面上直接观圈I
zigBee协波投
察劐这是从数百个传感器中的哪个发出的,它位于哪层楼的IEEE
802.15.4物理层定义2种物理层标准,分别工作在
哪个位置,其反映的数值是多少。因此,本文通过设计并实不同频段,即868
MH棚15
MHz和2
4GHz。IEEE802.15.4
现一种无线传感器网拓扑发现算{击,自动检测出有关传感器MAc层使用载波多路侦听访问,碰撞避免(csMA,cA)机制控网络拓扑结构方面的情况,将其用可视化界面表示。
制信道的接入,它也可以提供信标帧的发送、同步和可靠服2
zigBee无线传●器阿络
务等服务”J
o
为了促进IEEE
802】5
4技术,厂商开发了802.15.4应用
zjgBee网络层主要有以下功能”J:(”加入和离开网络;程序接口(APplicationProgrammingInterface.API)。该API有(2)路由帧到目的节点;(3)发现和维持路由;(4)发现一跳邻居2个用途:(1)为使应用设计者直接使用无线芯片的特性;的节点;(5)存储邻居节点信息。
(2)通过高层库和规格参数使用该API,以更方便地提供自己2.2
zigBee节点奏垂
的较高层服务。zigBec是后者的一个重要实例。
一般将加载zigBec协议栈并具有zigBee功能的硬件称
2.1
zigBee协议柱
为zigBee节点。zigBee节点一般分为3种类型:zigBcc协zigBee技术是通过zigB∞协议栈实现的。zigBee协议
调器,zigBee路由器和zigBee终端”“。一个zigBee网络只栈采用分层模型并定义相关的协议层(见图】)。zigBee协议能有一个协调器,可以有多个路由器和终端。协调器负责组栈采用IEEE的80215.4标准作为其物理层(PhysicalLayeL
基盒疆目;扛苏省自然科学基金资助项目(BK20D9058)
PHY)和媒体接入控制层(Medja
Access
control,MAc)的标
柞者■介:划新字(1984一),男,硬士研究生,主研方向:无线传感
准.+zigBec联盟在此基础之上自行定义同络层和应用层”l。器陌络;李兵、黄疆,副教授;陈鸣t教授、博士生导师每层都通过服务接入点(serviceAccessPoint,sAP)接口为上
收●日囊:20Il-05-18
E・m蝴:∞orpius汕@gm函I
com
万方数据
计算机工程
建、管理和控制一个zigBee网络并收集信息;路由器能够路由信息和采集信息;终端只能采集信息。zlgBec协调器和路由器可以与其他类型的节点通信,面zigBee终端只与zigBee协调器或路由器通信,zigB∞终端之闻不能通信。zigBec{办调器和路由器也称为全功能设备fFuIl
FunctionDevice.FFD),
Function
Device,
2()12年2月20日
由圈3可见.星型两络和树型网络的拓扑结构与其生成树拓扑图帽同.而网状网络的生成树拓扑圈反映了该网络节点之间的父子关系结构。尽管它不是完整的网络拓扑阁,但反映出了该网络的核心结构。因此,通过监测拓扑生成树,能够观察到阿络中各个节点的状态,从而能够方便地管理和控制整个网络。下文中的zigBee网络拓扑结构就是zigBceM络生成埘打j扑
o
“
zigBee终端也称为简化功能设备(ReducedRFDP”。
2.3
zigBee节点越一方式
zigBee无线传感器网是由多个zigBee节点通过无线信
“¥j
道互联而成,它支持3种类型的网络拓扑结构星型、树状和网状(见图2)”。J。尽管图中的无线链路用线段表示,但事实上附近的节点都在其无线电波覆盖下,能否形成无线链路取
’
0●
/,,
N*瞎悱W#≈
决于网络中采用的路由算法。
o,mH“#E0机№啪II≈
●地胁悱∞Ⅻ
椠八。
a
a’址删结构生成树mIflf刑结构’E峨树
田3
妒—r弋吨
k
㈧星型结构
nj埘’“地竹
。州拽%阳
zilBet一靠生t■籀|卜
为得到zigBcc网络的拓扑结构,首先需要知道该网络巾的节点信息,即网络中有哪些括跃节点及其基本信息,其次j岳要知道网络中这些节点的相互关系。因此,本文设计的zigBee网络发现拓扑算法的基本思路是:设法从zlgBee协凋器获得网络中所有活跃节点的基本信息并将其放入到一个名为Nodes的数组中;然后遍历Nodes数组中的每个元索。
■2zIgB驿■●I拓扑螬■
在星型同络结构中.zigBcc协调器是整个网络的中心,它负责建立、管理和维护整个网络,所有其他节点都只能通过协调器加入网络,网络中的节点也只能和协调器进行通信。
在树型网络结构中,网络由z培Bee协调器初始化并建立.终端节点不仅可以通过协调器加入网络也可以通过路由器节点加入。节点只能和它的子节点或父节点通信,因此。在树型网络中一般采用分级路由选择镶略,例如cIustenT陀e路由算法”1。
网状网络结构是最一般的结构,其路由可自动建立和维护。网络中的节点地位平等。均可以与其通信范围内的所有节点直接通信。但由于一个节点在某时刻只能选择一条链路通信.不会形成路由环路,因此可以认为它仍是一种树型结构网络。
3
向zl曲ee网络发送命令询问每个存储节点的父节点地址.得
到父地址后,遍历数组找到节点地址与父地址相同的元索,并将父节点在数组中的索引值填写到该节点的“父节点在数组中的索引”字段中;得到zigBec网络中的所有节点以及父子关系后,通过可视化技术西出数组Nodes信息,从而得到zigBee网络拓扑图。
Nodes数组定义如下:
stⅢcI
NodesⅣ救姐中元素结构
NOdetypc.NodcAdd化ss:FathcrAddre蛄.FatherJndex:NodcP0sltiOn:
Ⅳ节点类型Ⅳ节点物理地址Ⅳ父节点物理地址Ⅳ父节点在数组中的索gⅣ节点在西图时的位置
zigB神同鳐拓扑发瑰算法
zigBee网络不同于有线网络,无法直接观察到整个网络
的蛆同情况和所形成的网络拓扑结构。若希望方便地管理和控制zi曲ee网络,则必须基于一定的拓扑发现算法用网络测量技术获取zigBce网络的拓扑结构。通过上述zigBee网络的组网过程和组网原理可知,无论是星型、树型或是网状网络,各种zlgBee网络都是由协调器初始化并建立的,zigBee路由器或终端既可通过协调器加入网络,也可以通过zigBee踏由器加入网络。如果A节点(路由器或终端)通过B节点(协调器或路由器)加入一个ZigBee网络,则称B节点为A节点的父节点,而A节点为B节点的子节点。按照这种关系,只要获取了zigBee网络节点之问的父子关系,就能够得到其生成树拓扑图。图3给出了图2网络的生威树拓扑图。该生成树拓扑反映了信息流动的路径.本文提出的拓扑发现算法是在实际无线传摩器同中通过获取节点之闻的关系信息,从而推断出谈生成树拓扑的方法。
zigBee网络拓扑发现算法(zigBecTopo)的伪代码如下:
Ⅳ定义节点数组
N0desInl:
Ⅳ获得同络中所有节点的基本信息并将其艘入刊Nodes披组中Ⅳ计算节点在西布的位置并在酉布上西出节点
GetAIINodes(Nodes)
Nodcs阶Node‘yp睁GeINodcnperj:
N0des叶No血Address=GetNodeAdd化x“J
在西布中的位置:
D值w(Nodes【lI】:
EndF0r
Ⅳ廿点类型Ⅳ节点地址
Nodes卧NodePosInon=根据萄布大小和书点的索引计算怙点
,/在茸布上商节点
万方数据
第38卷第4期划新字,李兵,黄珊。等:一种zigB睇无线传感器网络拓扑发现算法
99
Ⅳ爿断节点问的父子关熏,并在父子节点阃茸绕
zi2B∞协调器的相邻表中,因此可以通过在协调嚣中调用NodesRcIatiOn(Nodcs)z.st∽k中提供的API函数uanOulNetDis()得到网络中所有节I
点的信息。为确定网络的拓扑结构,需要知道网络中各个节For|-l
Io
nd0
点之问的父子关系。可以通过在网络节点中调用z・st孔k中慷得殳节点地址
的APl函数NLME-GetcoordshonAdd吖)得到父节点的物理Nodes|11.FacherAdd『ess=GetN0deFatherAdd(Nodcs【I】J:
地址。从而得到这些节点之间的父子关系。
Ⅳ判断数蛆中哪十节点是自己的父节点
根据上述操作.通过使用上述的zigB∞T0po算法设计了Forj=l协ndo
无线传感器嘲拓扑管理模块,实现了zigBee网络拓扑的可视IfNodesU】NodeAddfess=Node川】.Fa山erAddress:
情到父节点在敦组中的索引
化。图5显示该拓扑管理模块自动绘制的拓扑图,它与图4所示的网络实验环境完全相同,证明了本文算法的正确性。
Nodcs¨FI‘herIndex-j.
,/在每个节点和它的父节点之间置一条线表示父子关系
DrawLine(Nodes¨1.NodeP0sition,Nodes卟NodcPositjon);
Endlf卜一一r匝困卜圃
b
●
EndFor
E~=…}
・
e—恒匦回
EndFor
I…=4=.—1]
等=兰===爿
e
对zigBceTopo算法时间复杂性评估如下:GctAllNodes(Nodes)只有一个从l—n的循环,时间复杂度为^,NodesRelaLion(N0des)函数中有n个从1~n的循环,时间复杂度为矿,因此.zjgBceTopo算法的时间复杂度为矿。
4
zigBeeT0po算祛的实现及舅试
实验中使用一种实际的zjgBee无线传感器网络(wirelcss
sensorNetwork.wsN)系统,其核心芯片是cc2430。该芯片是TI公司生产的嵌入式zigBce应用的片上系统,内置的一5拓扑f曩曩块量录曲胃謦扣抖
zigB∞协议栈实现代码是TI公司推出的z—stackl6J。z-stack5结束语
提供了一组API函数,开发人员可以通过APl控制和管理zigBce无线传感器网络廉价、耗能低、易部署等特点使zigB∞网络节点t利用该系统搭建的zigB∞网络实验环境其具有广泛的应用前景。为方便管理和控制zigBee无线传如图4所示,使用Rs232串行线将z培Bee协调器与服务器感器月络,需要甩可视化方法显示网络拓扑,而显示无线网连接,服务器上运行用c#开发的无线传感器网络拓扑管理络拓扑的关键是发现网络拓扑。本文提出的zigBeeTopo算法模块。该模块能通过串口命令管理控制zigBcc无线传感器可确定网络活跃节点爰其相互关系。实验结果表明,该算法网络。该拓扑管理模块的核心是zigB∞Topo算法的实现和能够正确发现多种无线传感器网络拓扑。今后将研究开发具应用。
有更多功能的无线传感器朔络管理系统。
一
斗
参考文t
Ⅲ^U
◆
il】AkybdizI,su
wcilj柚.sankar撼ub脚n姗iam
A
survcy
on
“舭”∑M鸭配i舯.2002.
\
scnsor№【worbIJ】.腿E
c唧un耙ali仰s
ERs
232#
40(8】:102-114
【21李建中.李金宝,石胜飞.传摩器阿络及其数据管理的概念、问
置与进展fJ】软件学报,2003.14(!o】:1717-1727
13J事莎.刘三阳.冯海韩基于嘲格的无线传稿嚣网络节能路
由算法【JJ计算机工程.20II.37(9):144_146.
『4l
zigB∞A11I卸∞,Jnc—zigBeeSP∞inca60n2007[EB,0U.(2∞8-
05・26)hnp:m5hm
i∞ksjmcom.cr蚶18207470hmJ
【5J
IEEEⅢEESId802.15A2006w№lessMediumAoo%scon仃ol蛳dnysical
Layer
Sp睇i6∞Ij曲sforLow・俺钯W如lessPen伽al
AmNetworksIS】.2∞6
■4
z‘gBee一培赛■环壤
【6】李文仲,段明玉.zigB∞无线网络技术入门与实践fMJ北京:
实验环境包括了1个z培Bee协调器、3个zigBce路由北京航空航天大学出版社.20盯
器和4个zigBce终端。由于zigBee网络的节点信息存储在
编辑陆燕非
万方数据