IEEE802.15.4标准的自适应GTS调度机制

杨鹏飞,王申涛,文玉强,赵 林

(重庆通信学院 信息工程系,重庆 400035)

IEEE802.15.4标准的自适应GTS调度机制

杨鹏飞,王申涛,文玉强,赵 林

(重庆通信学院 信息工程系,重庆 400035)

介绍了IEEE 802.15.4协议的GTS调度机制。基于现有的IEEE802.15.4MAC协议，提出了一种针对传输时延和公平性问题的自适应GTS调度(Adaptive GTS Allocation,AGA)算法。建立相应的自适应GTS仿真模型，对GTS算法的性能进行评估，并用网络演算理论对GTS进行理论分析。结果表明，提出的GTS调度机制在传输时延和公平性上明显优于现有的GTS调度方案。

IEEE802.15.4；保障时隙；时延；自适应；公平性

0 引言

无线个域网(Wireless Personal Area Networks，WPANs)是以一个人的工作区为中心进行无线连接的无线网络，最近新兴的短程、低速率无线设备使得无线个域网发展迅速[1]。对此，IEEE组织针对低速率无线个人区域网(Low-Rate Wireless Personal Area Network,LRWPAN)制定了IEEE802.15.4标准。

IEEE802.15.4标准以超低的复杂性、低成本、低能耗和低速率为出发点，为廉价、便携和可移动的设备提供低速率无线连接[2]。为了支持重复性低延迟应用所需的时延敏感数据传输，IEEE 802.15.4提供保障时隙(Guaranteed Time Slot，GTS)机制对一个超帧内的时隙进行分配，从而完成时延敏感数据帧的传输。IEEE802.15.4标准使用先来先服务[3]的GTS分配机制，无法灵活地应对网络工作负载和应用需求。虽然专用带宽可以保证数据传输的可靠性和性能,但专用资源的滥用也导致其他传输的冲突，某些节点还会出现饥饿现象。

1 IEEE802.15.4MAC协议

IEEE802.15.4标准定义了低速无线个域网(Low Rate-Wireless Personal Networks，LR-WPANs)的物理层和MAC层[2]，包含2种介质接入模式：信标使能模式(beacon-enabled mode)和非信标使能模式(nonbeacon-enabled mode)[4]。在非信标使能模式下，设备使用CSMA/CA机制竞争访问信道；在信标使能模式下，设备除了使用CSMA/CA机制外，还提供了自由竞争的保障时隙(Guaranteed Time Slot，GTS)信道接入方式来实现时延敏感数据的传输。本文着重IEEE802.15.4的信标使能模式，图1为IEEE802.15.4信标使能模式的超帧结构。

图1 IEEE802.15.4标准的超帧结构

在信标使能模式下，PAN协调器周期性产生信标，2个连续的信标及其之间的时隙即为超帧，超帧分为活跃期和非活跃期：在活跃期，PAN协调器和设备之间可以互相通信；在非活跃期，PAN中所有节点进入休眠模式，停止通信[4]。超帧的持续时间为15 ms到245 s，超帧长度(Beacon Interval，BI)和超帧活跃期长度(Superframe Duration,SD)由2个参数来确定：信标参数(Beacon Order，BO)和超帧参数(Superframe Order，SO)，BO决定超帧的长度，SO决定超帧中活跃期的长度。BI和SD定义如下：

BI=aBaseSuperframeDuration*2BO,0≤BO≤14，

(1)

SD=aBaseSuperframeDuration*2SO,0≤SO≤BO≤14。

(2)

活跃期被分为16个时隙，它由3部分组成：信标、竞争访问时段(Contention Access Period，CAP)和非竞争访问时段(Contention Free Period，CFP)[5]。在CAP中，设备使用时隙CSMA/CA机制接入信道，CAP主要负责传输对时延要求不高的数据帧和MAC命令帧。

对于那些需要专用带宽进行传输的设备，IEEE802.15.4标准提供了CFP时段进行低时延传输[6]。CFP的长度和GTS的调度由PAN协调器负责。CFP的长度取决于请求GTS分配的设备数量和超帧的现有可用容量，如果超帧内有足够空间，PAN协调器最多可以一次性调度7个GTS[7]。

设备若需要新的GTS调度来进行数据传输，则会在CAP时段向PAN协调器发送GTS请求命令，PAN协调器收到GTS请求后首先会检查当前超帧中是否有足够容量[8]。IEEE802.15.4标准使用一个固定的定时器来限制GTS的使用时间。设备由PAN协调器分配的GTS一旦在2*n个超级帧的时间内没有使用，PAN协调器就会收回分配给这些设备的GTS带宽[9]。n的定义如下：

(3)

2 自适应GTS调度方案

本节提出了一个针对时延和公平性的IEEE802.15.4自适应GTS调度方案。如图2所示，GTS的调度由PAN协调器控制，发生在星型网络拓扑结构中。星形拓扑结构的通信方式是集中式的，即每个加入该网络的设备若想要与其他设备之间通信就必须将其数据发送给 PAN协调器，协调器再分派数据给其他的目标设备[10]。PAN协调器通过周期性的发送信标帧以保障周围设备的GTS描述符的更新，它最多可以跟255个设备进行通信。

图2 WPAN中的星型拓扑结构

理想的GTS分配方案应该能较好地预估GTS传输设备的未来行为，PAN协调器通过预测信道情况，将GTS资源调度给有需求的设备，并回收先前已分配但现已不再使用的GTS资源。本文提出的自适应GTS调度方案有2个阶段：分类阶段和GTS调度阶段。在分类阶段，PAN协调器将根据最近的GTS使用反馈情况动态地将优先级分配给各个设备，对于那些需要PAN协调器更多注意的设备，PAN协调器将分配给它们更高的优先级；在GTS调度阶段，GTS按优先级非递减的顺序分配给各个设备，对于那些优先级较低且需要GTS进行数据传输的设备，使用饥饿避免机制保障设备的数据传输。在这里定义2个术语：GTS状态和非GTS状态。如果一个设备在CAP时段已发出GTS请求或正通过调度GTS向PAN协调器传输数据，则称其在GTS状态(GTS hit)；反之，则称其在非GTS状态(GTS miss)。

2.1 设备分类阶段

在这个阶段,每个设备适应性地被划分为一个状态,并根据过去的GTS的使用反馈情况动态地分配一个优先级。假设WPAN中有N个设备，有M+1(0,1，…,M)个优先级动态的分配给N个设备。设备的优先级编号越大，则其GTS调度的优先级越低。分配给设备n的优先级编号记作Prin，则0≤Prin≤M。在自适应GTS方案中，优先级较高的设备短期预计将有更多的通信量，从而在之后的超帧中有更高的概率来传输它们的数据[11]。设备的状态和优先级编号由PAN协调器确定，PAN协调器对设备的状态和优先级的控制是基于动态分支预测和控制网络拥塞的加性增，乘性减(Additive Increase Multiplicative Decrease，AIMD)算法，并做了一些改进，具体情况如下：

① 状态转换：如图3所示，在改进GTS方案中，所有设备被分为4个通信量等级，4个流量等级的设备分别对应4个状态，即高通信量(High Heavy，HH),较高通信量(Low Heavy，LH),较低通信量(High Light，HL)和低通信量(Low Light，LL)，这4个状态的通信量等级顺序为HH>LH>HL>LL。初始状态下，所有的设备都为LL状态。每个超帧结束时，PAN协调器检查所有设备的GTS使用情况，之后决定设备的状态。设备状态的转换如图3中实线和虚线所示，实线和虚线分别代表GTS状态和非GTS状态。如状态图标所示，更频繁使用GTS的设备有更大概率处于HH、LH这样的高通信量状态。而通过连续的GTS请求和GTS调用，LL状态的设备也可以升至更高流量状态。

图3 改进GTS算法中设备的状态转移图

在原有IEEE802.15.4规范中，新设备想要使用GTS进行数据传输，需要在高优先级设备使用GTS传输结束后再等待2n个超级帧的时间才能对GTS进行重新调用。这种被动解除GTS资源的调动方案会导致低通信量状态的设备长时间无法调用GTS资源。通过应用改进的GTS方案，低通信量状态的设备可以通过发送GTS请求将设备提升至高通信量状态，有效避免此类情况的发生。

② 优先级分配：通过使用上面的状态图，PAN协调器可以监视设备最近的传输行为，并将按通信量对设备进行适当地分类。可以对图3中的状态图进行进一步的修改，使得每个设备可以进行GTS优先级的动态分配，充分利用GTS资源。设备优先级编号的管理取决于传输反馈和设备的通信量等级状态，维持设备优先级编号的细节如下。

与纯粹地使用AIMD算法的优先级分配机制相比，本文方案提供了多层次的AIMD算法可以随时更新设备的优先级编号，编号的更新取决于设备的通信量等级状态。一方面，高优先级设备如果临时中断GTS的使用，它将会降格为较低优先级；另一方面，如果一个低优先级的设备开始请求GTS服务来传输数据,其优先级将大大提升，PAN协调器会为其尽快提供GTS服务，可以有效避免如低优先级的设备无法获取GTS调度的现象。本文优先级分配重点是设备否有连续的数据通过GTS进行传输。此方案对于连续传输数据的设备有利，但对于已闲置一段时间的设备，可认为其不需要GTS服务，从而降低此类设备的优先级。

由图3可知，如果设备n在HH状态一直使用GTS服务然后偶然间停止使用GTS，它的优先级编号Prin会增加1。一旦设备n在接下来的超帧中继续请求GTS服务，且其传输的数据是连续的，设备n增加的优先级数目会以指数方式减半，这样设备n的优先级可以迅速的“恢复”。假设有设备k在LL状态下，若其进行连续的GTS数据传输，优先级就会如设备n一般迅速的提升。但是，若设备k只进行了一次GTS传输，随后停止传输数据，设备k的优先级的降级会比设备n快得多。为设备进行分类可以防止低优先级设备无法进行GTS传输，同时在高通信量等级的设备偶然终端通信时维持GTS服务的稳定。

2.2 GTS调度阶段

在PAN协调器管理下，WPAN中所有设备的GTS调度优先级分配在设备分类阶段已经完成。接下来，在GTS调度阶段，GTS资源被调度给各个设备。调度标准是基于各设备的优先级编号，超帧长度和超帧中GTS容量。GTS调度算法如程序1所示。

程序1 DEVICE SCHEDULING

① 假设WAPN中有N个设备,

②P={Pri1,Pri2,… ,PriN},

③Th=MRBO其中M和R为常数,

④ while GTS容量未过载do,

⑤ 寻找设备k，Prik∈P是集合P中最小值,

⑥ ifPrik≤Ththen,

⑦ 设备k在当前超帧中进行GTS调度,

⑧ 将Prik从集合P中移除,

⑨ else,

⑩ break,

假设WPAN中有N个设备，P为N个设备的优先级编号的集合。在程序1中，PAN协调器首先检查GTS容量是否过载，超帧中GTS容量赢满足一下两个要求：① 提供GTS服务的GTS时隙数目最多为7。② CAP最小长度为aMinCAPLength，总GTS时长的增加不会导致CAP长度小于aMinCAPLength。

如果满足以上要求，GTS容量就没有过载。假设有足够GTS资源来容纳更多的设备，则执行5～11行的WHILE循环。在WHILE循环的每次迭代中，选出P中最小值(设备k的优先级编号)Prik，比较Prik与动态阈值Th的大小。Th定义如下：

Th=MRBO，

(1)

式中，M为最大优先级编号，R为常数且0

这里给出阈值Th是考虑到λ的通信量负荷。当通信量负荷较轻即大多数设备优先级编号较高时，没有必要为设备分配太多GTS资源。这种情况下将太多专用带宽用于GTS传输会导致资源浪费，甚至影响系统的总体性能。因此此时应将GTS带宽转移到基于竞争机制的CAP时段。为此，PAN协调区必须检测GTS通信量并使用阈值Th取消不必要的GTS调度。由式(1)可知，Th的值由M、R和BO决定。随着信标间隔的增大，设备请求GTS调度的概率也会相应增加。基于优先级分配机制，请求GTS调度的设备即使只进行一次GTS调度请求，它们也会分配到较小的优先级编号。为了不将稀缺的GTS资源分配给那些极少发送GTS调度请求的设备，需要更精确的阈值。这种情况下，Th的值应远小于M。而当超帧长度BI较小时，Th的值可以增大，设备选择的限制可以更加宽松。基于上述论证，若Prik≤Th(程序第6行)，则在当前超帧中调度GTS给设备k。

3 性能分析

本节中，建立了一个GTS的仿真模型来对提出的自适应GTS调度(AGA)算法进行评估。仿真遵循IEEE802.15.4MAC协议的规范，并进行数学分析验证。为了不失普遍性的考虑，进行了以下假设来降低仿真模型的复杂度：① 只考虑GTS业务量；② 不考虑GTS重传的事例；③ 只接受用于上行业务的传输GTS。

在仿真模型中，采用星型拓扑结构，网络中有10个设备其中1个为PAN协调器。每次仿真运行10 000个BI(即49 152 s)。每个设备的分组到达都为泊松分组到达，到达频率为λ。分别考虑业务量大和业务量小的2种业务类型，λh和λl分别对应以上2种情况的到达频率。仿真中，设λh=0.3/s,λl=0.1/s。因为IEEE802.15.4标准为低速率无线通讯协议，所以在基于802.15.4标准的WPAN中λ的取值是合理的。设业务量大的设备数目与所有设备数目的比值为v。表1为仿真模型的输入参数。

表1 主要仿真参数

至于输出量，分组平均等待时间为AGA算法中的一个重要指标。此外，使用公平指数F(分组等待次数)来衡量不同状态的设备的公平性。F定义为：

(2)

式中，N为网络中设备的总数量，Wi为设备i的分组平均等待时间。在式(2)中，0≤F≤1。当所有设备的平均等待次数相近时，F值趋近于1。反之，若Wi的值差别较大，F值趋近于1。因此F值越大，表明设备在获得GTS带宽上就越公平，饥饿现象就越不可能发生。

图4和图5为AGA方案和原802.15.4标准中，v(业务量大的设备数占总设备数的百分比)对分组平均等待时间和公平性的影响。

图4 平均等待时间

图5 GTS调度的公平性

由图4可知，在原有GTS算法中，随着v的增加，平均等待时间显著增加。这是因为原GTS算法的GTS调度遵循先进先服务的原则，无法处理快速增加的负载。原GTS算法中，平均等待时间增加是因为业务量大的设备长期占据GTS的结果。另一方面，提出的改进的GTS算法，它的平均等待时延要远小于原GTS算法。

图5中公平性曲线可以进一步解释为什么原GTS算法的平均等待时间迅速增加。图5表明当80%≤v≤90%时，原IEEE802.15.4算法中会出现严重的不公平现象，即大多数GTS资源被分配给了业务量大的设备，业务量小的设备可能会发生饥饿现象。但是改进的GTS算法可以将平均等待时间维持在一个较小的值，并为所有设备提供更加公平的GTS传输。

4 结束语

在IEEE802.15.4标准的WPAN网络中，为提高信标使能模式下GTS调度机制的性能，针对时延和公平性提出了一个新的GTS调度算法。改进了原有的FCFS调度算法，将节点按优先级进行分配，优先级大小由AIMD算法决定，避免某些节点长时间占用信道，影响传输公平性。仿真结果表明，该改进算法提高了GTS调度算法的公平性，降低了传输时延。

[1] Gutierrez J A.On the use of IEEE 802.15.4 to Enable Wireless Sensor Networks in Building Automation[C]∥IEEE International Symposium on Personal,Indoor and Mobile Radio Communications,2004:295-301.

[2] Zhang X.15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-rate Wireless Personal Area Networks (WPANs)[C]∥ Ansi/ieee,Standard 80,2006:110-115.

[3] Kishimoto Y,Kato S.Optimization of IEEE 802.15.4: Overview,Theoretical Study and Simulation[J].International Journal of Information & Communication Technology,2014,(1):412-418.

[4] Koubaa A,Alves M,Tovar E.IEEE 802.15.4 for Wireless Sensor Networks: A Technical Overview[J].IPP-Hurray Group,2008,39(1):169-204.

[5] Callaway E,Gorday P,Hester L,et al.Home Networking with IEEE 802.15.4: a Developing Standard for Low-rate Wireless Personal Area Networks[J].Communications Magazine IEEE,2002,40(8):70-77.

[6] Salman N,Rasool I,Kemp A H.Overview of the IEEE 802.15.4 Standards Family for Low Rate Wireless Personal Area Networks[C]∥ International Symposium on Wireless Communication Systems,IEEE,2010:701-705.

[7] De Nardis L,Benedetto M D.Overview of the IEEE 802.15.4/4a Standards for Low Data Rate Wireless Personal Data Networks[C]∥ Positioning,Navigation and Communication,2007.Wpnc’07.Workshop on,IEEE,2007:285-289.

[8] Yoo S,Kim D,Pham M L,et al.Scheduling Support for Guaranteed Time Services in IEEE 802.15.4 Low Rate WPAN[C]∥ IEEE International Conference on Embedded & Real-time Computing Systems & Applications,IEEE,2005:400-406.

[9] 802.15.4-2003 IEEE Standard for Information Technology-Part 15.4:Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-rate Wireless Personal Area Networks (LR-WPANs)[S],2003.

[10]Baronti P,Pillai P,Chook V W C,et al.Wireless Sensor Networks: A Survey on the State of the Art and the 802.15.4 and ZigBeestandards[J].Computer Communications,2007,30(7):1655-1695.

[11]Lu G,Krishnamachari B,Raghavendra C S.Performance Evaluation of the IEEE 802.15.4 MAC for Low-rate Low-power Wireless Networks[C]∥ IEEE International Conference on Performance,Computing,and Communications，2004:701-706.

Adaptive GTS Allocation with Latency and Fairness Considerations for IEEE 802.15.4

YANG Peng-fei,WANG Shen-tao,WEN Yu-qiang,ZHAO Lin

(Information Engineering Department of Chongqing CommunicationsInstitute,Chongqing400035,China)

This paper mainly describes the GTS mechanism in IEEE802.15.4 standard.Based on the existing IEEE 802.15.4 MAC protocol,an adaptive GTS allocation scheme is proposed with the consideration of low-latency and fairness.The simulation model and mathematical model of GTS mechanism are established to evaluate the performance of the adaptive GTS allocation scheme.Results show that the proposed GTS scheme outperforms the existing IEEE802.15.4 GTS scheme.

IEEE802.15.4;Guaranteed Time Slot;delay；arrival rate；burst size

10.3969/j.issn.1003-3114.2017.01.15

杨鹏飞,王申涛,文玉强，等.IEEE802.15.4标准的自适应GTS调度机制[J].无线电通信技术,2017,43(1):60-64.

2016-09-26

杨鹏飞(1991—)，男，硕士研究生，主要研究方向：无线传感器网络。王申涛(1980—)，男，硕士，主要研究方向：移动Ad Hoc网络。

TN92

A

1003-3114(2017)01-60-5