基于邻居表查询的ZigBee多播路由算法

白乐强，王佳林，张士宏

（沈阳建筑大学 信息与控制工程学院，辽宁 沈阳 110168）

ZigBee是一种开放性的低功耗、低成本、低数据速率、低复杂度、低分本、自组织的新型短距离无线通信技术［1］，是基于IEEE802.15.4标准的个域网协议［2］.ZigBee采用IEEE802.15.4制定的物理层（PHY）和媒体访问控制层（MAC）制定的标准，ZigBee的高层标准采用ZigBee联盟制定的网络层（NWK）、应用层（APL）等.ZigBee设备可以分为ZigBee协调器（ZC）、ZigBee路由（ZR）、ZigBee终端设备 （ZED）等三种.由于ZigBee网络是自组织网络，每个路由节点对于整个网络通信的可靠性都起到关键性作用，工作方式不当造成的节点失效会造成网络的部分瘫痪，所以改进ZigBee传输算法是提高ZigBee网络可靠性的有效方法.

文献［3］提出多播树传动比算法 ，该算法是量化了多播树的成本，考虑无线多播信道的链路质量，以及无线多播的特点提出的一种算法.文献［4］提出的网型多播算法是一种考虑到节约能量的无线传感器算法.针对节点移动的无线传感网络文献［5］提出了智能多播路由器发现机制的移动多播，文献［6］提出了本地树更改多播协议.对于实时性文献［7］提出了实时多跳无线多播路由算法，这些算法都适用于Ad-hoc形式网络，不能直接在WSN中应用，因为这些算法都是对于高存储高计算节点来设计的，文献［8］提出适用于ZigBee网络的多播算法、Z-CAST路由算法.然而Z-CAST算法是根据树形结构路由表转发原理基础上进行信息的传送，在提高使用节点能量优化方面没有进行考虑.

本文在Z-Cast算法基础上，针对转发多播信息过程中转发节点的浪费问题提出了ZigBee邻居多播路由算法（ZNMR）.该算法综合考虑目的节点的位置及规模来选择转发路径，对不同形式的多播组采用不同的路由算法，算法计算量小，适用于ZigBee网络多播信息的发送.

1 模型的建立

1.1 分布式地址分配

ZigBee网络同其他无线传感器网络主要的不同之处在于其采用地址分配方式，它给每个潜在父节点提供一个有限的网络地址子块.整个网络的地址在一个特定的网络内是唯一的，由一个父节点分配给它的子节点.分配方案由分布式算法根据一系列网络自定义参数确定，网络协调者决定了整个网络的最大子设备数.每个设备有一个相关的深度，表示只使用父子链路传输的一个帧到达ZigBee协调器，必须经过的最少跳数.其中协调者自身的连接深度为0，其直接子设备为1.ZigBee协调器首先根据需要规定3个参数：网络的最大深度nwkMaxDepth（Lm），一个父节点可以有的子节点最大个数的值nwkMaxChildren（Cm）和一个父节点可以有的路由器子节点的最大个数nwkMaxRouters（Rm），其中Cm 应大于等于Rm，这样就可以保证协调器或者路由器可以连接至少Cm-Rm个终端节点.网络深度为d的路由节点所能分配的地址空间Cskip（d）满足公式（1）

如果一个父节点它的深度是d，它的地址是Aparent，那么第n个子路由节点的地址如公式（2）：

而它的第n个子节点地址如公式（3）：

一个Cskip（d）值大于0的父节点设备必须接收子节点设备，根据子节点设备是否具有路由器功能，并给它们分配不同的地址.一个父节点给它的第一个路由功能子节点设备分配一个地址1，大于它自己的地址.ZigBee协调器为每一个ZigBee设备分配了一个固定的ID.并且每一个ZigBee节点不仅记录了父节点与子节点ID，而且记录了自己一跳邻居节点的ID.

1.2 ZigBee网络转发模型

Z-Cast的树形路由算法是根据父子关系进行信息转发，不需要路由选择，如图1所示，图中S为信息源节点，N3、N5、N6、N8、N10、N11为目的节点，ZC为协调器，信息从S向外转发.转发过程如虚线箭头所示，S通过N1、N2将信息发送给协调器，协调器再根据目的地址发送给子路由，最终信息到达目的节点.

图1 树形路由算法的信息转发路径选择示意图Fig.1 Schematic diagram of Tree routing algorithm forwarding path selection

该算法有两个问题，一是即使目的节点是信息源的邻居节点，多播信息也会根据父子逻辑关系，经过多跳才到达目的节点.二是该多播方法会消耗过多路由，尤其是Lm较小的节点.ZigBee邻居多播路由算法针对这两个问题进行了改进.信息源在转发信息之前首先给自己的邻居节点发送目的地址判断信息，邻居节点根据自己的邻居表来判断周围是否存在目的节点，根据存在情况选择是否接受信息源节点信息并转发.如图2所示，S将信息转发给N1、N4，两节点分别将信息转发给N3、N5.N5没有直接将信息转发给目的节点N6，而是转发给邻居节点中目的节点较多的N7节点，如此做可以节约转发路由数量及转播跳数，提高了网络的转发效率.

图2 ZigBee邻居多播路由算法的多播信息转发路径选择示意图Fig.2 Schematic diagram of ZigBee neighbor multicast routing algorithm forwarding path selection

2 ZigBee邻居多播路由算法

ZigBee邻居多播路由算法定义一个转发优先级参数ForwardingLevel，ForwardingLevel初始化为-1.ForwardingLevel是一个整数，表示信息源节点一跳邻居节点的邻居表中未接受信息的目的节点的数量，目的节点越多Forwarding Level值越大，最大值为该节点一跳邻居节点数量，即该节点邻居节点都为目的节点，最小为0即没有目的节点.信息源转发多播信息之前首先比较本节点的邻居表，将信息转发给一跳邻居节点本身就是目的节点的节点，这些节点做出标记表示已接收该多播信息，以免重复接收信息.然后信息源所有一跳邻居节点根据ID从小到大开始确定转发优先级，开始寻找优先级最大转发节点.

信息源确认一跳邻居节点的邻居表中未接受信息的目的节点数量，记为ForwardingLevel.若邻居表中无目的节点或目的节点都已接受该组多播信息则ForwardingLevel为0.当信息源确认过所有邻居节点优先级，选取ForwardingLevel最大的节点作为转发节点.若两个节点优先级相同则根据ID进行判断，ID小的优先级比ID大的优先级高.信息源其他一跳邻居节点Forwarding Level不变，以供信息源再次挑选转发节点时使用.

当转发节点准备发送信息时，首先从信息源接受信息，然后将多播信息发送给未接受信息目的节点.转发节点将信息转发给所有邻居表中的目的节点后，该节点转发优先级ForwardingLevel置0，不再作为转发节点.信息源重新计算Forwarding Level大于0的信息源一跳邻居节点转发优先级，选择新的转发节点.直到信息源所有一跳邻居节点ForwardingLevel都为0，该信息源节点转发信息完毕，将自身的转发优先级Forwarding Level置0.根据ID从小到大在已接受信息的目的节点中重新寻找新的节点作为信息源，直到网络中所有目的节点都已经收到信息，该组多播信息发送完毕.ZigBee邻居多播路由算法流程图如图3所示.

图3 ZigBee邻居多播路由算法流程图Fig.3 Flow chart of ZigBee neighbor multicast routing algorithm

3 数据仿真及分析

本文采用MATLAB平台进行仿真，对ZigBee邻居多播路由算法的可行性进行仿真以及对结果进行分析，在200m×200m的空间内随机生成50到200个ZigBee节点，按一定的比例从中产生目的节点.每个节点的最大传输范围为40m，节点能容纳最大子节点数Cm为6，节点深度Lm为4，并且所有节点都是稳定的.模型运行时假设物理层与数据链路层都正常工作.对ZCAST算法和ZigBee邻居多播路由算法进行试验.

试验选取了50、75、100、125、150、175和200七种ZigBee节点数量规模的网络场景，其中随机各选择10%～50%比例节点作为目的节点，在随机生成场景的前提下，两种算法对随机选择信息源节点与选择ZigBee协调器（ZC）作为源节点两种情况进行仿真，每种场景仿真100次，统计仿真结果来求取平均值，取得的数据如表1～表4.

表1 目的节点比例为20%信息源随机选取结果Table 1 Results of destination node ratio is 20%and the source is selected randomly

表2 节点数量为100信息源随机选取结果Table 2 Results of the number of nodes is 100and the source is selected randomly

表3 目的节点比例为20%信息源选取ZC结果Table 3 Results of destination node ratio is 20%and the source is ZC

表4 节点数量为100信息源选取ZC结果Table 4 Results of the number of nodes is 100and the source is ZC

图4 Z-Cast算法的信息转发路径选择图Fig.4 Z-Cast algorithm forwarding path selection

图5 ZigBee邻居多播路由算法的信息转发路径选择图Fig.5 ZigBee neighbor multicast routing algorithm forwarding path selection

图4、图5为100节点目的节点比为20%条件下随机生成的两算法的多播信息转发路径选择图，空心点表示ZigBee普通节点，十字节点表示目的节点，实心点表示转发节点，三角形表示信息源，坐标（100，100）的节点为ZigBee协调器，每一条黑色虚线表示节点之间传输信息.图4中信息源节点首先将信息发送给信息源的父节点，直到ZigBee协调器，协调器再将信息根据目的地址通过父子关系的路由节点转发给各目的节点.即使目的节点就在信息源附近，信息源也不会将信息直接发送给目的节点，这样对于整个网络的能量是一种浪费，而且每次新一组多播信息的发送都会使用Lm较小的路由节点，使上层路由过多的损耗，长期下去会影响网络可靠性.图5中ZigBee邻居多播路由算法使节点在转发信息之前进行判断，使信息呈放射状向整个网络的目的节点转发，每一次转发信息都有多个接收者，而且信息不必须经过协调器.这样转发不仅减少了转发节点，而且减少了Lm较小的路由的使用，提高了网络的可靠性.

由表1可以看出在目的节点比例为20%情况下，随着节点个数不断增加，两算法的转发节点都随之增加.但ZNMR算法转发节点明显少于Z-CAST算法，且节点越多ZNMR算法的优势越明显.由表2可以看出在目的节点数量确定而目的节点比例不断增加的情况下，ZNMR算法转发个数也少于Z-CAST算法.但是当目的节点比例很大时，该算法转发节点个数逐渐接近Z-CAST算法，这是因为许多较上层的路由节点也成为了目的节点，所以无论使用何种算法转发节点个数都没有明显差距.对比表1表3，表2表4可以看出当ZigBee协调器作为信息源转发信息时，两算法转发节点都有少量的减少，但由表3表4可以看出ZNMR算法仍然适用于该网络，即信息源位置的选取对于不同算法之间转发节点数量的影响是不大的.

4 结 论

本文基于邻居表查询和ZigBee分布式地址分配特点，结合传统的无线传感器多播路由算法提出了ZigBee邻居多播路由算法.采用MATLAB进行仿真，实验结果表明该算法减少了ZigBee多播路由转发节点，提高了多播算法效率，在节约能量方面有了很大改进.该算法对于大规模ZigBee网络多播信息发送是一个可改进的算法.

［1］ ZigBee Alliance.Document 053474r17ZigBee specification［S］.2008.

［2］ The LANMAN Standards Committee.IEEE Std 802.15.4TM-2003 ［S］.New York，USA：the Institute of Electrical and Electronics Engineers，2003.

［3］ Jung Y，Choi S，Hwang I，et al.Cost-Effective Multicast Routings in Wireless Mesh Networks［J］.Communications in Computer and Information Science，2011（262）PART 1：262-271.

［4］ Zeng G，Wang C，Xiao L.Grid Multicast：An Energy-Efficient Multicast Algorithm for Wireless Sensor Networks［C］.4th International Conference on Networked Sensing Systems，INSS 2007：267-274.

［5］ Lee H，Han S.Intelligent Multicast Router Discovery Mechanism in Mobile Multicast［C］.Advanced Industrial Conference on Telecommunications／Service Assurance with Partial and Intermittent Resources Conference／E-Learning on Telecommunications Workshop AICT／SAPIR／ELETE 2005：152-156.

［6］ Srinivasan T，Chandrasekar R，Vijaykumar V，et al.Localized Tree Change Multicast Protocol for Mobile Ad Hoc Networks［C］.Second International Conference on Wireless and Mobile Communications，ICWMC 2006.

［7］ Yi J，Poellabauer C.Real-Time Multicast for Wireless Multihop Networks ［J］. Computers and Electrical Engineering，2010（36）：313-327.

［8］ Gaddour O，KoubâaA，Cheikhrouhou O，et al.Z-Cast：A Multicast Routing Mechanism in ZigBee Cluster-Tree Wireless Sensor Networks［C］.IEEE 30th International Conference on Distributed Computing Systems Workshops 2010：171-179.