基于ZigBee的集群机器人网络路由算法

李跃　黄希玲　贾海瑞

摘要：集群机器人系统中使用ZigBee网络技术可实现有效的通信，但树形组网可能使部分节点过早耗尽电池能量，所以使用ZigBee技术的机器人系统中，ZigBee网络的路由算法是研究的关键问题。在重点研究了ZigBee协议网络层树型路由算法的基础上，提出了一种适用于机器人通信系统的路由算法（RACRS），改进算法中通过引入邻居表，考虑网络中的电池供电节点和持续供电节点，路由选择网络中的关键路径而尽量避开电池供电节点。仿真结果表明改进算法能有效节省网络中电池供电机器人网络节点的能量消耗，增强集群机器人系统中ZigBee网络的稳定性，最大化系统网络的生存时间。

关键词：集群机器人；无线传感器；ZigBee网络；通信协议

Abstract： Cluster robotic system using ZigBee network technology can achieve an effective communication， but some nodes may use up all the energy because of heavy transmissions. So in robot system using ZigBee technology， the key issue of the research on its network layer is routing algorithm. This paper focuses on the research into such an issue an analyzes the tree. Based on the above analysis， an improved routing algorithm which suitable the robot communication system is proposed（Routing Algorithm of Cluster Robotic System，RACRS）. The algorithm introduce the neighbor table and consider the battery-powered nodes and continuous power node， selecting the critical path in the network routing try to avoid the battery-powered node. The simulation results show that the improved algorithm can effectively save the battery-powered robot node energy consumption and the lifetime of the whole network was maximized in this improved algorithm.

Keywords： groups of robots； wireless sensor； ZigBee network； communications

0 引言

機器人技术作为信息技术和先进制造的典型代表和主要技术手段，已成为世界各国竞相发展的技术。随着社会生产技术的飞速发展，机器人的应用领域也不断扩展，从工业自动化到海洋资源的探索，乃至太空作业等领域。同时由多个机器人组成的集群系统通过协调、协作来完成单机器人无法或难以完成的工作是机器人发展的一个趋势，如流水线生产、编队巡逻、仓储运输、交通规划等应用领域[1]。分布式集群机器人系统具有高度的自规划、自组织特性，机器人的定位、协调与分析控制是应用研究的重点，实现这些功能，机器人之间和控制系统需要可靠地进行通信。无线通信技术能够增加机器人的活动范围和灵活性，使用ZigBee无线传感器网络技术组建无线网络，可在机器人系统中实现可靠的通信，显著提高机器人的工作效率[1]。

集群机器人系统控制方式分为集中式和分布式。集中式是有中心化的协调机构，控制效率比较高，但由于选择集中控制来解决所有机器人产生的冲突，需要增加一个主控制器，主控制器的工作负荷很大。而分布式控制不存在有任何中心控制器，由局部范围内的机器人实现协同控制。本文的研究基于混合式结构，混合式结构本质上是一种层次结构，上层的主控制器或领导机器人对下层的机器人只有部分控制能力。该方式可实现集中和分布式结构的互补，提高系统灵活性和协调效率[2]。本文针对混合式结构的集群机器人系统，提出了一种适用于集群机器人系统的ZigBee网络路由新算法（Routing Algorithm of Cluster Robotic System，RACRS）。该算法考虑了集群机器人系统的应用场所及其特点，提高了路由算法的效率，降低了网络中电池供电节点的能量消耗，延长了网络的生存时间和自适应能力，对集群机器人系统网络的组建具有指导意义。

1.ZigBee簇树组网及其路由算法

ZigBee技术是一种新兴的近距离、低复杂度、低功耗、低数据率、低成本的短距离无线通信标准。ZigBee技术以IEEE802.15.4协议作为其物理层和介质访问层（Medium Access Layer， MAC）的标准协议，网络层和应用接口层由ZigBee联盟定制[1]。ZigBee技术主要用于近距离无线连接，相对于现有的各种无线通信技术，ZigBee技术是具有最低功耗和最低成本的技术。ZigBee技术数据率的特点适合于承载数据流量较小的业务，被广泛的应用于工业控制、自动化等领域[3]。

1.1 ZigBee簇树型结构

IEEE802.15.4定义了两种物理设备，全功能设备（FFD）和精简功能设备（RFD）。FFD可以担任网络协调器，也能作为终端设备，可以与RFD或其他FFD通讯。RFD只能与FFD通讯，在网络中通常用作终端设备，实现非常简单，通常以电池供电，只需较少的资源和存储空间，成本比FFD低很多。ZigBee网络中，定义了三种逻辑设备类型：ZigBee协调器、ZigBee路由器和ZigBee终端设备。FFD可以实现ZigBee全部逻辑设备功能，RFD只能作为ZigBee终端设备[4]。

首先由ZigBee协调器构建整个网络，协调器进行信道扫描，选择一个未探测到的网络空闲信道，然后确定自己的16位网络地址、地址的PAN ID及网络的拓扑参数等，当各项参数设定好后，协调器便可以接受其他节点加入网络。加入ZigBee网络的节点通过MAC层提供的关联过程组成一棵逻辑树，当网络中的节点允许一个新节点通过它加入网络时，他们便形成了父子关系，父节点为子节点分配网络中唯一的16位网络地址。假设父节点最多可连接的子节点数为Cm，子节点中的最大路由器数为Rm，网络的最大深度为Lm，可以根据（1）式得到网络深度为d的父节点为其子节点分配的地址之间的偏移量Cskip（d），即：

当一个新的RFD子节点A通过Ap加入到网络中，Ap节点成为这个新节点的父节点，Ap使用（2）式为子节点A分配地址，即：

如果是新的FFD节点加入，它具有路由能力，所以父节点Ap使用（3）式为子节点A分配网络地址，即：

1.2簇树型路由算法

树型网络拓扑（Tree）路由算法中，节点根据目的节点的网络地址计算分组的下一跳，假设地址为A，深度为d的ZigBee路由节点收到目的节点地址为D的数据帧，路由节点首先通过（4）式判断该目的节点是否是它的后代节点，

如果目的节点是接收节点的后代节点，该数据帧将被转发给它的子节点N，依据（5）式可以确定将数据帧转发给其终端子节点或路由子节点

如果目的节点不是它的后代节点，则将数据帧沿着树型结构转发到父节点。

2.集群机器人系统

2.1 系统框架模型

对于固定通信节点和位置固定机器人，可以将固定通信节点环境模型预先标定为不变模型，而对于移动机器人，其通信环境模型是变化的。对于整个通信网络模型则是不变模型和可变模型的结合，属于动态模型（Dynamic Model，DM）[5]。对于固定通信节点或者具有通信能力的固定机器人设备模型，可以预先标定，采用持续电源为通信节点供电。而对于移动机器人，为了增强机器人的灵活性和活动范围，机器人ZigBee通信节点采用电池供电方式。由于ZigBee组网技术具有自适应能力，网络环境发生变化后，被断开连接的通信节点能够再次自动发起网络连接请求，再次和网络建立连接，该网络模型适用于混合分布式集群机器人系统的网络通信。

在工业生产和大型公共场所中，使用集群机器人系统可有效的提高生产效率，或更加便利的服务生活。在这样的应用环境中，部分机器人或通信节点位置固定，而其它机器人可以移动，它们和位置固定的机器人协同完成复杂的任务。该系统中机器人个体存在结构和功能上的差异，为有意识协作的异构集群机器人系统[6-9] [12]，如在商场中发生突发事故，需要有事故检测机器人，事故处理机器人等协同工作。该模型即是本文中研究的集群机器人系统的网络模型。

2.2 集群机器人系统中树型路由的问题

树型路由适用于节点静止或者移动较少的场合，属于静态路由，不需要路由表，节省存储资源，对于传输数据包的响应较快，在集群机器人系统中使用树型路由对机器人的定位非常不灵活，浪费大量的地址空间，并且路由效率低。如图1所示，图中C是网络的協调器节点，标号R1～R20的节点是FFD节点，RFD节点略去，持续电源供电的路由节点用粗实线表示，电池供电的路由节点用虚线表示。当路由节点R9与路由节点R16通信时，其路由是R9-R1-C-R4-R3-R10-R16，使用树路由转发数据需要6跳，但由图可知，节点R16在节点R9的直接通信范围内，因此R9可直接将数据发送发R16而无需其他节点转发，这样可提高路由效率。

集群机器人系统模型中，存在一定比例物理位置固定传感器节点，树型路由中没有考虑网络中的持续电源节点和电池供电节点的特点，将两类传感器节点同样处理，这样浪费了持续电源节点这一资源，同时频繁地使用电池供电的父节点转发数据时，会大量消耗节点的能量，降低网络的稳定性[10] [11]。如图1所示，网络中频繁地使用电池供电路由节点R4转发数据，容易使R4节点过早的消耗完电池能量。如果能够将互相在一跳范围内的持续电源节点间建立虚路由[13]，如图中虚直线所示，转发数据时就可尽可能的使用持续电源节点，避开电池供电节点，这样就减少了电池供电路由节点的数据转发量，节省了电池供电路由节点的能量，延长了系统网络的生存时间。

3.集群机器人系统的ZigBee网络路由算法

3.1 邻居表定义

ZigBee网络中，具有路由能力的节点都有一个邻居表，并对其动态维护，每个节点在接收到信息包时，都要更新维护邻居表，邻居表中存储的是该节点的邻接节点的信息，邻接节点是指在直接通信范围内的节点。邻居表的结构如图2所示。邻居表的记录中有三个字段：ADDR是邻居节点地址；NodeType是邻居节点设备类型，区分节点是具有路由功能的FFD设备，还是不具有路由功能的RFD设备；PowerType是邻居节点的电源类型；DeadTime是邻居节点的确认时间。

3.2 构建关键路径

混合式异构集群机器人系统中，部分机器人或通信节点位置固定，这些路由节点使用持续电源供电。簇树型ZigBee网络组建完成后，由前文的分析可知，网络的稳定性较弱，路由选择有限，同时电池供电节点频繁的转发数据，会缩短网络时间。通过在簇树型网络中构建多条只包含电源供电节点的虚路由，如图2中的路由C-R1-R2-R3-R5、C-R7-R6、C-R1-R9-R16。其中R2与R3、R5与R6等互为邻居节点，两节点间可使用邻居表建立虚路由。簇树型网络组建过程中，路由节点可识别出自己的电源类型，当其加入网络时，发送节点信息到协调器节点，协调器记录该节点的信息，包括节点的电源类型，该节点邻居节点中的持续电源路由节点和电池供电路由节点。协调器构建带权有向图的邻接矩阵，并依据接收到的信息修改相应的邻接矩阵。当两个路由节点互为邻居节点时，设置其间的通信代价为0值或1值，其中0值表示起点为持续电源路由节点，即由持续电源路由节点转发数据；而值1表示起点为电池供电路由节点，即由电池供电路由节点转发数据。当两节点不是邻居节点时，设置通信代价为无穷大。此处的关键路径即为带权有向图中两顶点间的最短路径，由dijkstra算法可求得[10]。协调器将求得的每个持续电源路由节点到其它电源路由节点的最短路径发送给对应的持续电源节点记录。

3.3 RACRS算法

ZigBee簇树型网络使用邻居表引入虚连接，这样既保持了网络树型结构中的“地址-位置关系”，又可减少网络中电池供电节点的能量消耗。FFD节点转发数据时，如果下一跳节点不是目的结点，则转发数据节点采用新路由算法查找下一跳路由节点。路由算法具体如下：

（1）查找路由节点S邻居表。

（2）若邻居表中有目的节点D，则直接转发数据到目的节点D。

（3）若目的结点D是某个邻居节点N的后代节点，则转发数据到该邻居节点N。

（4）查找节点的关键路径，若目的节点是某条关键路径的节点，则使用该关键路径转发数据。

（5）若查找失败，则查找目的节点是否是关键路径中节点的后代节点，若是则使用该关键路径转发数据。

（6）邻居表中无合适的下一跳路由邻居节点，则使用DAAM树路由算法转发数据[3]。

3.4算法的使用范围与不足

RACRS算法用于持续电源路由节点占一定比例的ZigBee网络，当网络中持续电源节点比例增加时，网络中电池供电节点的路由节点负载相应的减少，当ZigBee网络中存在由持续电源节点组成的关键路由路径时，RACRS算法相比DAAM算法有明显的电池节点耗能减少。

改进的RACRS算法为了在网络中通过由持续电源节点组成的路径转发数据，可能会增加到目的结点的路由跳数，同时使得网络的局部流量增加。此外，如果ZigBee网络中无恰当的由持续电源组成的关键路径，则会使网络中个别电池供电节点的转发数据量增加，反而降低了网络的生存时间。针对以上问题将在下一步工作中深入研究。

4.算法分析与仿真

4.1 算法分析

改进算法中，只需要在网络结构发生变化时，相应的修改邻居表中节点信息，此时网络需要广播结构改变的信息，供其它节点记录该变化，同时需要发送加入节点的信息到协调器，需要少量控制分组的开销。分析網络结构的图1可知，在电源供电节点占有一定比例的网络中，可在网络中构建多条关键路径，通过改进后的算法使用关键路径转发数据，使得数据包到达目的节点的路由中包含的电池供电节点的数目小于或等于传统的树路由算法，降低了网络中电池供电节点的能量消耗。转发数据包时经过位置固定的持续电源传感器节点，避免了移动机器人在网络中地址变化带来的影响，可减少网络中数据包的丢失，增强了网络的稳定性。

由于RACRS算法选择一条包含电池供电节点最少的路由来转发数据，部分路由可能会增加跳数，或使个别持续电源节点的数据流量增大，但在整个网络中，采用含有邻居表的RACRS算法，到达目的节点的平均路由跳数不超过传统的树路由算法[12]。

4.2 仿真结果分析

改进算法通过仿真实验和传统树路由算法进行了比较，重点是比较传输时网络中电池供电节点的总能耗以及网络的转发数据丢包率。仿真结果证明了改进算法的有效性。

仿真工具采用Omnett++4.2.2。网络覆盖面积为300×500，网络中路由节点数为100，网络协调器初始化Cm=6，Rm=4，Lm=5。仿真结果如图3所示。在图3中，分别列出了PSAR算法[2]和本文改进的RACRS算法相对应传统的树路由算法，网络中电池供电节点的总耗能减少率。由图可知改进的算法在引入邻居表记录，在路由的过程中考虑了持续电源节点作为转发节点，同时选择局部最小路由跳数的路径进行数据传输时，减少了网络中电池供电节点的能量消耗，能够最大化网络的生存时间。

如3.2中所述，网络中有新的持续电源供电节点加入时，节点发送信息到协调器，协调器将计算后的关键路径再发送给相应节点。在关键路径和移动机器人网络地址改变的时间段内，转发到原目的地址的数据包会丢失。图4说明了使用新算法后对网络丢包率的影响，实验结果表明使用新算法的网络丢包率在0.1%上下，小于网络丢包率的平均值。

5.结束语

本文提出了一种适用于分布式异构集群机器人系统的ZigBee网络路由算法——RACRS算法，当网络中电池供电节点的邻居节点在一条持续电源节点组成的关键路径中时，FFD节点可通过该邻居节点转发数据，从而减少电池供电节点转发数据的能耗，算法避免了动态查找路由的额外通信开销和对树路由的影响。理论分析和仿真结果显示，与DAAM算法相比，在合适的ZigBee网络中，RACRS算法在控制开销和减少网络能耗，延长网络生存等方面的性能表现整体更优。RACRS算法对未来的分布式异构集群机器人系统的网络构建具有指导意义。

参考文献：

[1]ZigBee Standards Organization. （2006）[S]. ZigBeespeci?-cation.

[2]Metin， T.， Ibrahim，K..PSAR：power-source-awarerouting in ZigBee Networks[J].Wireless Networks.（2012），18（6），635-651.

[3]Cho， D. H.， Song， J. H.，& Han， K. J. （2006）. An adaptive energysaving mechanism for the IEEE 802.15.4 lr-wpan[J]. Lecture Notesin Computer Science， 4138， 38–46

[4]Puccinelli， D.，Sifakis， E.，&Haenggi， M. （2006）. A cross-layerapproach to energy balancing in wireless sensor networks[J].Lecture Notes in Control and Information Sciences， 331， 309–324

[5]Boughanmi， N.，& Song， Y. （2008） A new routing metric forsatisfying both energy and delay constraints in wireless sensornetworks[J]. Journal of Signal Processing Systems， 51（2）， 137–143.

[6] P. Buck， T. Schmitt，and M. Beetz： Reliable multi-robot coordination using minimal communication and neural prediction[J].Springer-Verlag. Pages 36-51，2001.

[7] P. Iocchi， D. Nardi， M. Piaggio， and A. Sgorbissa： Distributed coordination in heterogeneous multi-robot systems[J]. Kluwer Academic. Pages 155-168，2003.

[8] I. Mas， S. Li， J. Acain， and C. Kitts： Entrapment/escorting and patrolling missions in multi-robot cluster space control[J].IEEE Press. Pp.5855-5861，2009.

[9] J. Mataric，S.Sukhatme， and H. Ostergaard： Multi-robot task allocation in uncertain environments[J].Kluwer Academic.pp. 255-263，2003.

[10]Yong Deng，Yuxin Chen，Yajuan Zhang， and S. Mahadevan. Short communication：FuzzyDijkstra algorithm for shortest path problem under uncertain environment[J].Elsevier Science. pp. 1231-1237，2012.

[11]李智軍，周晓，吕恬生.基于群体协作的分布式多机器人通信系统的设计与实现[J].机器人.2000，22（4）：300-304.

[12]吴军，徐昕，连传强，贺汉根.协作多机器人系统研究进展综述[J].智能系统学报.2011，6（1）：13-27.

[13]戚剑超，魏臻.ZigBee树型路由算法的改进[J].合肥工业大学学报.2010，33（4）：529-537.

基金项目：西南科技大学城市学院校级科研项目支助，编号：XCY14Z12。

作者简介：李跃，（1986.11-），男，汉，四川简阳人，硕士，研究方向：节能技术、人工智能。