TD―ASD调度算法在ZigBee网络中的应用研究

摘 要：由于无线信道的广播特性，无线网络中任一节点发送的无线信号都可能被其通信范围内的其它节点接收。因此，当同一地理区域范围内的节点同时传输信号时，会形成相互干扰，从而导致信号无法正确接收。有效协调多个簇共享无线信道资源，避免冲突发生是ZigBee簇树网络面临的关键问题之一，直接影响无线资源的使用效率、网络吞吐和时延等重要性能。针对这一问题，提出基于时分的自适应SD（TD-ASD）调度算法。理论分析和仿真结果证明，TD-ASD算法可以运用在ZigBee网络中，并且在不同输入业务条件下，与传统ZigBee算法相比，该算法提高了系统吞吐量，降低了网络工作负载和端到端的平均延迟。

关键词：无线网络；TD-ASD；ZigBee簇树网络；NS2

DOIDOI：10.11907/rjdk.151352

中图分类号：TP393

文献标识码：A 文章编号：1672-7800（2015）007-0172-04

0 引言

物联网是在无线通信技术基础上发展起来的一种新型网络架构，其感知层涵盖了多种不同类型的异构网络[1]，这些网络之间大多通过无线通信技术传输信息，ZigBee网络就是其中之一。感知设备作为物联网采集感知信息的终端工具，通过网络接口向核心网传输信息，实现人与人、人与物、物与物之间的沟通和对话，实现智能化管理和认知。ZigBee网络一直致力于充当这一过程的可靠平台[2]。在当前专利和技术时代，要在物联网标准方面获得成功，必须加快物联网感知层建设，尤其着重加快ZigBee网络的研究和应用。ZigBee网络在生产、生活中的作用和地位越来越重要，对ZigBee网络进行研究，具有重要的理论和实际意义。

1 ZigBee无线通信技术

1.1 ZigBee简介

ZigBee[3]是近年来兴起的一种网络容量大、节点体积小、低功耗、低成本、低数据传输速率的新型双向无线网络通信技术，是一种介于BlueTooth技术和无线标记之间的技术方案。ZigBee技术是由ZigBee联盟在IEEE 802.15.4标准基础上研发制定的有关组网、应用和安全方面的无线网络通信技术。

1.2 ZigBee MAC层协议

ZigBee的MAC协议支持信标使能模式和信标不使能模式。在信标使能模式下[4]，协调器周期性广播信标帧，节点通过信标帧来同步到协调器上。BI（Beacon Interval，信标间隔）定义了两个连续的信标帧之间的时间间隔。它包括一个活动时期和一个非活动时期，活动期称为超帧，并分成16个相等的时隙，帧的发送和接收只能在该时间段内进行，非活动期是可选的，节点在此时期会进入休眠模式。超帧结构如图1所示。

图1 超帧结构

BI和SD由两个参数决定，BO（Beacon Order，信标阶数）和SO（Superframe Order，超帧阶数），其中信标间隔定义如下：BI=aBaseSuperframeDuration*2BOsymbols（1）

其中，0≤BO≤14。超帧活动时间的长度，定义如下：

SD=aBaseSuperframeDuration*2SOsymbols（2）

其中，0≤SO≤BO≤14 ，aBaseSuperframeDuration表示超帧的最小长度。它是一个固定值，为960个符号数。假设物理层的调制方式使得一个符号为4bit，传输速率为最高速率250kbps，那么一个超帧活动长度为则相当于9604[]250103=15.36ms。当物理层调制方式和传输速率确定后，BI、SD值虽然代表符号数，但与时间长度值可以互相换算。本文将B☢I、SD值等符号数直接作为时间长度值使用。

1.3 ZigBee簇树网络存在的问题

在ZigBee簇树形拓扑网络中，拥有子节点的协调器和路由器，它们要发送信标帧，使得子节点跟踪其父节点（与前文父设备通用）的信标，实现父子节点之间的通信。因此，可能出现在某子设备的射频接收范围内有两个或者两个以上的父设备同时发送信标帧（或者数据帧），而且都使用同一信道，必然产生碰撞。子设备无法收到正确的信标帧，也就无法同步到父节点，无法和父节点通信，使得网络无法正常工作。特别是当节点传输数据量很大时，此情况就更加常见。因此，各个父节点必须正确选择自己超帧活动部分的时间，使之不与邻近父节点的超帧活动时间冲突。

2 TD-ASD调度算法

2.1 传统的TD-ASD调度算法

在传统的TD-ASD调度算法中，路由器节点加入网络成为父节点后，其SD值为设置的初始值。当其簇内网络流量发生变化时，这个初始值可能不太适合变化，使得网络性能降低。当簇内网络流量变大时，可以增加SD的长度，使节点有更长的时间和父节点进行通信；反之，则缩短SD的长度。也就是说，协调器根据每个簇流量的变化情况动态调整SD值。这样增加了网络的自适应性，仿真结果也证明如此增大了吞吐量。

假设一个ZigBee簇树网络中存在N个父节点，每个父节点都有（SD，BI），组成序列（SDi，BIi）1≤i≤n，对（SDi，BIi）1≤i≤n作如下处理：

BI′=BIaBaseSuperframeDuration=2BO，0≤BO≤14（3）

SD′=SDaBaseSuperframeDuration=2SO，0≤SO≤BO≤14（4）

通过以上处理可以得到序列（SD′i，BI′i）1≤i≤n，其中SD′、BI′分别为SD、BI的归一化值。

TD-ASD算法分分析、决策和执行3个阶段。其中，分析、决策阶段运行于协调器中，执行阶段运行于父节点（协调器除外）中。它通过修改节点通信流程使协调器掌握了网内每个节点接收范围内的父节点，然后利用图论中的顺序着色算法对父节点进行分组，结合TD-ASD算法得出新的调度，使网络工作在新的调度之下。 分析周期结束后，进入分析阶段。分析周期是指协调器收集每个簇簇内传输数据包个数信息的时间。当然，在此时间内，可ง能会有新的路由器节点加入这个网络，并成为父节点组成新的簇。但是对于分析周期结束后的时间点来说，可以看作网络拓扑是不变的。在本算法中，假设分析周期为numBI= 5个协调器信标帧（BI）时隙间隔，在此时间段内，所有父节点都将自己簇内的信息发送给协调器。

分析阶段结束后进入决策阶段。分析阶段结束后，协调器获取了n个簇簇内传输数据包个数的变化值（假设在此时间段内n个父节点的簇内信息都可以收到）、n个父节点的SD′、BI′值，根据TD-ASD算法决定是否改变SD′值和确定信标帧发送延迟时间。

该算法利用信标帧的载荷空间来指示SD′的调整和信标帧发送延迟，因此附加空间需要利用节点地址指明相关节点。利用一个字节的前4位表示需要使SD′除以2的节点数，用另外4位表示乘以2的节点数，用16个字节分别表述SD′除以2的节点（Group-1中的前4个）地址和乘以2的节点（Group-2中的前4个）地址。每个信标帧发送延迟时间归一化值的对数值占1个字节，同时Σ还需要3*（n-1）（假设网络共有n个父节点）个字节来表述节点号和信标帧发送延迟时间的归一化值。修改后的信标帧结构如图2所示。

图2 修改后的信标帧结构示意图

在执行阶段协调器将决策后的信息写入信标帧的载荷字段中，并传输该信标帧。

2.2 TD-ASD算法的改进和分析

从上述分析可以看出，传统的TD-ASD算法存在一定问题，解决这些问题需要对父节点进行分组，使得组内的节点不仅可以同时发送信标帧，还可以同时处于超帧的活动期。对父节点进行分组分为以下两个步骤：①协调器需要知道任一节点接收范围内的所有的父节点地址；②运用顺序着色算法对父节点进行分组。

在网络运行中，改进后的TD-ASD算法与传统的TD-ASD算法相比，在节点刚开始加入网络时，对连接请求帧进行了修改，加入父节点子域。在分析阶段，协调器除要处理统计簇内信息帧内的传输数据包个数外，还要处理统计的簇内节点接收范围内的父节点地址。在决策阶段，仍然按照簇内数据包个数来改变SD'值，然后按照协调器维持的数组H得到G0，后根据顺序着色算法对G0中父节点进行分组，将组内节点SD'的最大值作为整个组的SD'值，将组内节点BI'的最小值作为整个组的BI'值。之所以这样取值，目的在于提高吞吐量，求出每个分组信标帧发送延迟时间的归一化值。

最后，对信标帧进行重新组帧，因为每个父节点的SD′、BI′值都可能发生变化，每个值都要占据3个字节，而它们的对数值只占用一个字节。因为信标帧载荷有限，所以修改信标帧时主要采用对数值。具体组帧规则如图3所示。

图3 改进算法修改后的信标帧结构示意图

3 仿真

本文采用NS2的2.34版本作为仿真实验平台，该版本自带WPAN开放源码。首先在C++代码层自行设计实现TD-ASD算法和改进算法[5]，主要涉及IEEE802.15.4MAC层的P802_15_4mac.cc和P802_15_4mac.h代码文件，物理层的P802_15_4phy.cc文件，以及帧结构文件P802_15_4field.h。定义脚本中需要用到变量，具体如下：

为分析TD-ASD算法及其改进算法对网络性能的影响，采用吞吐量、工作负载和端到端的平均时延3个性能指标进行评估。

（1）网络吞吐量。指在一定时间段内，网络成功传输数据包的字节数。

平均网络吞吐量=网络成功传输数据包的字节数总时间

（2）网络工作负载。指在一定时间段内，网络传输数据包的字节数。

平均网络工作负载=网络传输数据包的字节数总时间

（3）端到端的平均时延。包括路由查找延时、数据包的等待延时以及传输延时。

端到端的平均时延=∑接收到数据包的时间-发送数据包的时间发送数据包的个数

本文实验中首先对不同输入业务条件下的原始ZigBee协议算法、TD-ASD算法和改进算法的吞吐量、工作负载和端到端的平均时延进行仿真[6]；仿真结束后，利用编写的AWK脚本在trace文件中提取数据；最后，利用gnuplot将仿真数据以图形的方式展现。

建好的网络场景如图4所示。通过每次调节发送CBR数据封包的时间间隔来调节整个网络输入流量负载，如eval＼＼$cbr_（$src） set interval_ $interval，选取（2，4，6，8，10，12，14，16）pkts/s 几个量来代表不同的输入负载。在每次仿真时，同时选取多对源节点和目的节点进行测试。

3.1 对吞吐量的影响

不同速率下，3种算法统计的平均吞吐量生成的曲线如图5所示。

从仿真结果可以看出，原始算法在低数据率区域能工作，而且吞吐量高于TD-ASD算法及其改进算法。这是因为在低速率区域，冲突率较低，而TD-ASD算法及其改进算法要求父节点不断地向协调器节点发送统计信息，增加网络的负担，影响吞吐量。但在高数据率区域，冲突大大增加，原始算法缺少相应的调度处理机制，很快就趋于饱和吞吐量。而TD-ASD算法及其改进算法采取相应的调度，使冲突率大大降低，即使要上传大量的簇内统计信息，仍然保持较高的吞吐量，最后维持在饱和值附近。

3.2 对工作负载的影响

对工作负载进行仿真，3种算法统计的平均工作负载生成的曲线图如图6所示。

综上可以看出，当数据发送速率比较低时，即网络输入业务量比较低时，应用TD-ASD算法及其改进算法使得网络工作负载加大；而当输入业务量比较大时，这两个算法的效果就比较明显½，此时数据包发送成功的概率提高，进而数据包的重传次数减少，工作负载降低。同时，TD-ASD算法和其改进算法曲线基本吻合，也就是说这两个算法对工作负载的影响相似。 3.3 对端到端的平均延迟的影响

对端到端平均延迟进行仿真，然后记录下当前网络发送和接收数据包的时间，可以得到平均延迟时间。不同速率下3种算法统计的平均延迟生成的曲线图，如图7所示。

图6 工作负载对比 图7 端到端延迟对比

从图7可以看出，原始算法在不同速率下的延迟增长是有规律的，这是因为网络拓扑是不变的，速率是线性增加的，那么延迟的增长必然呈现一定的规律性。TD-ASD算法及其改进算法延迟增长较慢，因为当速率增加时，各个簇都在不同的时间域上工作，没有发生冲突，只是簇内数据流量加大而已，延迟不会大幅度增加。特别是改进算法使延迟更小。

综上所述，TD-ASD算法及其改进算法确实增加了网络吞吐量、降低了工作负载和减小了延迟，提高了网络的性能，达到了MAC协议的目标。

4 结语

本文针对ZigBee簇树网络的MAC调度机制进行了研究，对簇间如何避免冲突进行了分析。探讨MAC调度机制存在的问题，分析了传统的TD-ASD调度算法，并提出了改进的自适应TD-ASD调度算法设计方案，通过软件仿真验证了其可行性和系统性能提高。

参考文献：

[1] ZigBee standards Organization，ZigBee document 053474r17： ZigBee speeifi-eation，veมrsion number r17[S].ZigBeeAlliance，2008.

[2] MOHAMMED I. BENAKILA，LAURENT GEORGE，SMAIN FEMMAM.A beacon cluster-tree construction approach for zigBee/IEEE802.15.4 Networks[C]. The Fourth International Conference on Mobile Ubiquitous Computing，Systems，Services and Technologies，2010.

[3] CASILARI E，FLOREZ-LARA A，CANO-GARCIA JM. Analysis of the scalability of hierarchical IEEE 802.15.4/Zigbee Networks[C]. The 3rd international conference on Scalable information systems，2008.

[4] 李晓维，徐勇军，任丰原.无线传感器网络技术[M].北京：北京理工大学出版社，2007.

[5] 陈泽云.无线传感器网络的定位算法和超帧调度机制的研究[D].杭州：浙江大学，2008.

[6] KOUBAA A，CUNHA A，ALVES M. A time division beacon scheduling mechanism for IEEE 802.15.4/Zigbee Cluster-Tree Wireless Sensor Networks[C]. In Proceedings of 19th Euromicro Conference on Real-Time Systems （ECRTS 2007），Pisa（Italy）， 2007.