beacon时槽什么意思

IEEE802.15.4支持高速实时数据传送算法

卜翔;章韵;陈建新

【摘要】WiththepromotionoftheInternetofThings,low-powerhigh-

802.15.

4isastandardoflow-powercommunications,butfewstudiesonhigh-

otsolvetheproblemwheremore

thanvendevicesrequiretime-nsitivervices,andthedelay

comethe

limitations,badontheEGSA,maximizetheavailableContentionFree

Period(CFP),

furtherenhanceefficiency,theCFPisdividedintomultiplesmalltimeslots

whichareallocatedunderEarliestDeadlineFirst(EDF)schedulingpolicy.

Performanceanalysisrevealsthatdelayconstraintsareguaranteed

efficientlyandthebandwidthutilizationisimprovedsignificantly.%随

着物联网应用的推广,出现了更多的低功耗高速率实时通信技术需求.IEEE

802.15.4是低功耗通信既定标准,但对高速实时传输研究较少.它不能解决多于七个

设备需要实时服务、时延约束小于超帧长度的问题.为了克服这些限制,文中在

EGSA算法基础上,最大化IEEE802.15.4中CFP,保留足够多的带宽资源用于实时

业务传输.为了进一步提高效率,把CFP分割成多个微小时隙,并使用最早截止时间

优先(EDF)策略分配这些微小时隙.性能分析显示这种策略可以严格遵循时延约束条

件,并可以提高带宽利用率.

【期刊名称】《计算机技术与发展》

【年(卷),期】2013(000)003

【总页数】5页(P14-18)

【关键词】IEEE802.15.4;保护时槽;实时性;调度;EDF

【作者】卜翔;章韵;陈建新

【作者单位】南京邮电大学，江苏南京210003;南京邮电大学，江苏南京

210003;南京邮电大学，江苏南京210003

【正文语种】中文

【中图分类】TP301.6

0引言

随着物联网应用的推广，出现了更多的低功耗高速率实时通信技术需求。如人体健

康生理参数实时监测、运动康复监测等;工业环境中水文、管道监测;基础设施如桥

梁、楼宇建筑等质量监测。这类应用采用低功耗无线通信技术，要求以高频率周期

性采集数据(如大于20Hz)，从而对低功耗实时通信技术提出新的挑战。

IEEE802.15.4协议是用于低速率、低功耗无线通信既定标准［1］，主要定义了

物理层(PHY)和媒体接入控制层(MAC)两个规范。MAC中定义了超帧结构，将通

信时间划分为活跃和不活跃两个部分。在不活跃期间，节点进入休眠状态以节省能

量。活跃期间划分为三个阶段:信标发送时段、竞争访问时段(ContentionAccess

Period，CAP)和无竞争访问时段(ContentionFreePeriod，CFP)。其中CAP时

段用于非实时应用需求，而CFP时段主要用于有延时约束的实时业务需求。为了

支持多节点实时通信，CFP分为多个保护时槽(GuaranteedTimeSlot，GTS)，

每个用户节点可以使用一个或多个GTS来发送具有延时要求的实时业务［2］。

因而如何分配GTS是IEEE802.15.4支持满足延时约束的关键。

Koubaa等研究了GTS分配的带宽利用率［3～5］。他们提出一种称为i-GAME

［4］的IEEE802.15.4MAC协议GTS分配机制调度算法，根据网络各节点的数

据传输量情况和时延期限要求等信息实现网络中不同节点对同一信标周期中相同

GTS的共享，即动态分配GTS的时隙给不同的节点。该算法重点解决了网络带宽

利用率和时延问题。Na等提出了一种称为GSA［6］的IEEE802.15.4MAC协议

GTS分配机制调度算法，该算法根据星型网络中各节点的时延期限和负载情况进

行GTS动态分配，重点解决网络中端与端的时延问题。Cheng等提出了一个简单

的方法，把CFP时段分割成16个小时隙(minitimeslot，mTS)，有效地提高了

带宽利用率(下文中将该算法称为16-mTS)［7］。Xia等通过给设备提供不同的优

先级提出了一个自适应实时GTS分配算法(ART-GAS)［8］。Li等引入“正规访

问延迟”参数，并提出延时分类GTS传输算法(Delay-Category-GTS，DCGTS)

［9］，提高了紧急节点的传输速率。

文献［10］分析并比较了当前典型的无线传感器网络MAC协议的主要机制及实

时性。文献［11］提出一种基于路由转发树的时隙调度算法(ATSA)，根据节点的

数据量大小来分配节点每轮需要的时隙。文献［12］提出了一种基于时隙预留的

多信道实时MAC协议。该协议在响应流媒体查询之前，事先建立一条从源节点到

汇聚节点的时隙预留流路径，从而最小化数据包在每一次转发时的信道接入时延。

文献［13］在GTS的先来先服务调度策略的基础上，提出一种基于时延优先级的

GTS分配算法。

上述研究考虑的延时约束通常都要大于一个帧长，而对于延时约束要求比较严格的

应用，如体域网里高速运动、实时生理参数监测等，数据采集速率高达几十Hz，

前面GTS分配算法不适用了。基于此，文献［14］提出了一种EGSA算法，通过

最大化CFP和进一步把GTS划分为更短的时隙，来支持多节点周期性高延时约束

应用。EGSA主要解决多节点、同周期、高实时任务传输，但并不适合多节点不同

周期的高实时任务传送。因而文中主要解决多节点、不同周期高实时任务传送，满

足体域网或物联网中异类传感器高速率、实时数据采集和发送。

1问题描述

1.1IEEE802.15.4协议介绍

IEEE802.15.4MAC协议为解决无线通信网络的时延问题，提供了一种比较好的

解决方案。但在某些实际的应用中，IEEE802.15.4MAC协议的实时性能存在一

定的局限性。协议中GTS分配机制采用先来先服务(first-come-first-rved，

FCFS)的调度算法，很难满足一些实时性传输的时间限制要求，且在一个信标周期

中，最多分配7个GTS，即在同一信标周期中，利用GTS进行传输的设备节点数

目受限，很难满足大型网络的要求。

如图1超帧结构中，超帧(SD)和活跃期(BI)分别表示为:

其中，SO表示超帧序列值，BO表示信标序列值，并且0≤SO≤BO≤14。IEEE

802.15.4标准定义最小超帧长度aBaSuperframeDuration为960符号。在

2.4GHz频率下，每个符号4比特。所以当SO=BO=0时，超帧最小长度480字

节，持续时间为15.36毫秒。

图1IEEE802.15.4帧结构

1.2问题定义

文中考虑在IEEE802.15.4信标使能的无线传感器网络中，1个协调器节点和m

个设备节点组成星型拓扑结构网络。每个设备节点周期性地给协调器节点发送长度

一定的数据。每个设备节点的周期性任务用元组Ni=(ai，Si，Ei，Ti，di)表示，

其中ai表示第i个节点ID，Si表示采集数据的起始时间，Ei表示结束采集数据的

时间，Ti表示采集数据的周期，di表示采集数据的发送期限。每个设备节点数据

发送任务记为一个事务，表示为transaction(addr，stime，dtime)。其中addr

表示执行事务的节点的地址，stime表示事务开始时间，dtime表示事务的截止时

间。根据Ni可以计算出每个节点的事务列表。于是，文中把该问题模型记为(B，

{Ni|0≤i＜m})。

在本系统中，做以下假定:

(1)B/r＜＜Ti＜tBI，其中r表示数据传送速率(在2.4GHz频率时为250kbps)，

即所有节点采集数据的周期远远大于数据发送所耗时间，小于信标间隔期;

(2)di=Ti，时延期限等于采集周期，即节点采集的数据需要在它的下一次采集前

发送;

(3)本系统为软实时系统，容忍偶尔的超时错误，数据发送失败造成的后果并不严

重。

于是，文中需要解决的问题为:在系统(B，{Ni|0≤i＜m})中，设计一种时隙分配和

调度算法，使得系统具有较高的调度成功率和带宽利用率。

2实时调度算法

2.1EGSA算法

EGSA算法解决了同类设备高速数据传送的调度算法，主要采用如下策略:

(1)最大化CFP。

在超帧的不活跃期间，PAN网络中的设备之间不通信，数据不能传送。而不活跃

期间又是由SO和BO决定的。为了支持高速数据传输，在EGSA中令SO=BO，

从而可以提供更多的带宽用于实时通信。

同样，CAP主要给没有时延要求的应用使用。在本系统中，每个的节点传送数据

都需要满足一定的时延要求，所以在超帧结构中，CAP的长度需要尽可能得小。

如果CAP过大，会使许多节点在过长的CAP期间因为无法传送数据而超时。

EGSA提出了最小化CAP的方法。

IEEE802.15.4规定CAP最小长度aMinCAPLength为440符号(在2.4GHz频

率为220字节)。但CAP的末端必须与TS边界对齐。把超帧起始的信标帧与紧随

后的CAP记作，则的最小长度为:

其中DBeacon表示信标帧的长度，DTS表示标准时隙长度。由于文中提出了新

的时隙分配和调度方法，所以信标帧结构也对IEEE802.15.4标准做了改变，

DBeacon计算详见2.4节。

(2)将CFP划分成更小的时隙。

若将一个较大时隙分配给一个节点独享，即使在该节点不需要传送数据时，也不能

将时间让给其它需要传送数据的节点使用。这就降低了系统的调度成功率和带宽利

用率。所以把CFP划分成尽可能短的时隙。在本系统中，节点发送一个固定长度

为B的数据包。EGSA定义了小时隙(mTS)，每个mTS的长度为

其中DIFS表示帧间隔(IFS)的长度。当B不大于aMaxSIFSFrameSize18字节时，

DIFS取短帧间空隙最小时间aMinSIFSPeriod为12符号(2.4GHz时为6字节);当

B大于18字节时，DIFS取长帧间空隙最小时间aMinLIFSPeriod为40符号

(2.4GHz时为20字节)。

从而CFP划分成多个连续的小时隙mTS，即有

其中KTS表示CFP占用的标准时隙个数，0≤Δ＜DmTS，表示CFP分割后剩余

下的长度。

表示CFP能够分割的mTS的个数。

在分割CFP时按照从后往前顺序，把Δ长度的剩余留在CFP头部，紧挨着前面的

CAP，如图2所示。

用Di，mTS表示第i个mTS的起始位置，有

利用这种方法，CFP段可以分隔成多个微小时隙，便于支持多节点高速数据传输。

图2mTS分割示意图

2.2算法设计

在EGSA算法中，由于所有节点都具有相同的任务和发送周期，因而mTS分配采

用轮循机制。但当多个节点任务周期不同时候，就不能简单采用轮循方式来调度多

个节点任务。文中在EGSA基础上，提出一种改进的调度策略mGSA，采用最早

截止时间优先(EarliestDeadlineFirst，EDF)算法，根据任务截止时间来给所有节

点分配mTS。

每个mTS从当前需要传送的事务中选择一个截止时间最早的事务，如果有多个截

止时间相同的事务，再从中选择起始时间最早的事务，将该mTS分配给它进行传

送。如果当前没有需要传送的事务，则该mTS空闲。

同样也会出现传送事务没有分配到mTS而被舍弃的情况。本系统为软实时系统，

容忍丢弃个别传送事务，但是要求保证尽可能高的调度成功率。

EDF算法本质上是一个贪心策略。可以证明，如果有一组任务可以调度(所有的数

据都在截止时间之前发送)，那么EDF算法一定可以满足。如果一批任务不能全部

满足(部分数据因为超时而丢弃)，那么EDF满足的任务最多。这就是EDF算法最

优的体现。EDF算法的缺点在于需要对每个任务的截止时间做计算并动态地调整

优先级，需要消耗一定的系统资源。

2.3算法实现

由于所有节点都是周期性地采集数据并发送，并且参数都是已知的，所以mTS的

分配可以采用离线调度算法。而采用EDF的时隙调度算法需要消耗较多的系统资

源和能量，于是把该调度算法运行在基站节点上。基站节点在每个信标间隔期之前

先计算好当前超帧中mTS的分配方法，再在超帧开始的信标帧中附带该信息;设备

节点在信标帧中获取自己被分配到的mTS序号列表，计算出mTS的起始时间，

到达该时间时便可以发送数据。

为了实现该调度算法，首先定义两个优先权队列SQ和DQ。队列中是按照优先级

排列的事务(transaction)，其中SQ中的事务是按起始时间排列的，DQ中的事务

是按截止时间排列的。

图3说明了DQ的创建过程，以及使用EDF算法选取最早截止时间的事务的方法。

该算法流程并没有将所有事务加入DQ中排队，而只将时隙开始前的事务入队，

节约了内存空间。协调器节点在每个信标间隔期之前都要调用KmTS次该过程，

为KmTS个时隙选择一个节点，然后在广播的信标帧中附带各个时隙分配信息。

图3EDF算法实现

2.4实施方案

本节考虑实时通信调度算法实施的解决方案。mGSA算法只对IEEE802.15.4标

准做细小的改变，并且不影响已经存在的协议。由于改进的算法不再分配GTS，

而是划分成更小的mTS，所以需要对信标帧结构中的GTS信息子域做相应的修改。

首先，在信标帧中使用一个标识位指示是否使用mGSA。在GTS信息子域第一个

字节的GTS描述域结构中，第3～6位是保留位。于是，使用第3位作为mGSA

标识位(如图4-a)。当该位为0时，按照IEEE802.15.4标准分配GTS;当该位为1

时，使用mGSA算法分配mTS。

图4mGSA信息域

当使用mGSA调度算法时，信标帧中需要附带mTS的分配信息。mGSA算法将

该信息添加在信标载荷中。如图4-b所示，起始4个字节表示mTS的个数，后面

紧跟节点地址列表，每个地址2字节，第i个地址就表示第i个mTS分配给该地

址的节点。当地址为0xFFFF时，表示该mTS不分配给任何节点。于是，信标帧

的长度为:

其中MAC帧头、超帧描述域、GTS描述域、帧校验共占12字节;mTS计数占4

字节;地址列表占2KmTS字节。

至此，已有足够的条件可以确定mTS的个数KmTS。首先选取最大的KTS(1

≤KTS≤15)，使式(5)成立。此时得到最长的CFP时段。再将KTS代入式(6)便可

得到KmTS。将KmTS填入mTS计数域，并调用EDF算法计算每个mTS分配

的节点地址，填入地址列表中。于是信标帧构造完成，协调器节点将其广播出去。

设备节点在信标帧中获取自己被分配到的mTS序号列表，计算出mTS的起始时

间，到达该时间时便可以发送数据。

3性能分析

本节分析动态实时调度算法的性能，并与i-GAME和16-mTS进行比较。考虑在

系统(B，{Ni|0≤i＜m})中，B=23字节，网络中共有20个节点周期性发送数据。

根据周期不同，可以分外四组，周期分别为20、25、30、35ms。

在WindowsXPSP3平台下，使用C++编程对3种算法仿真，分别得到它们在

SO取不同值时的调度成功率(见图5)和带宽利用率(见图6)。i-GAME和16-mTS

的调度成功率和带宽利用率基本符合2.3节的分析。利用mGSA算法，时延约束

得到了有效的保证，带宽利用率也得到了显著的提高。

图5调度成功率比较

图6带宽利用率比较

当SO较小时，时隙长度较小，取最小长度的CAP仍占用较多时隙，剩下可以调

度的时隙数较少，所以调度成功率和带宽利用率比较低;而当SO很大时，时隙长

度较大，由于CAP需要与时隙边界对齐，CAP至少要占用一个时隙的时间，CAP

持续时间逐渐增大，造成调度成功率和带宽利用率的降低。由图可见，调度成功率

和带宽利用率随着SO的增大，先增大后减小。

4结束语

文中提出一种IEEE802.15.4实时通信调度算法mGSA，主要解决星型拓扑结构多

节点高速率数据传输问题。在算法实现中，最大化IEEE802.15.4中CFP支持高

速实时数据传输，并把CFP分隔成比GTS更小的mTS单元，利用EDF算法，把

这些mTS单元分配给需要发送高速实时通信的节点。与EGSA算法不同，本算法

拓展了EGSA算法，使之能够支持多个具有不同周期的高速数据传输任务，来满

足实时任务的低延时约束条件。仿真结果表明，与iGame和16mTS算法比较，

本算法可以显著提高系统调度成功率和带宽利用率。并且该算法与标准完全兼容，

实现方便。后面工作中，将进一步从理论角度分析任务周期长度、节点数和延时约

束保证之间的关系，为高速实时数据传输应用奠定理论基础。

参考文献:

［1］802.15.4Standard:WirelessMedium

AccessControl(MAC)andPhysicalLayer(PHY)SpecificationsforLow-rate

WirelessPersonalAreaNetworks(WPANs)［S］.NewYork:IEEE，2003.

［2］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，

2005.

［3］KoubaaA，AlvesM，ocationanalysisinIEEE802.15.4

forreal-timewirelessnsornetworks［C］//Procof14thInternational

ofRhodes，

Greece:IEEE，2006.

［4］KoubaaA，AlvesM，TovarE.i-GAME:animplicitGTSallocation

mechanisminIEEE802.15.4fortime-nsitivewirelessnsornetworks［C］

//n，

Germany:IEEE，2006.

［5］KoubaaA，AlvesM，anddelaytrade-offoftheGTS

allocationmechanisminIEEE802.15.4forwirelessnsor

networks:rearcharticles［J］.CommunicationSystems，2007，

20(7):791-808.

［6］NaC，YangY，malGTSschedulingalgorithmfor

time-nsitivetransactionsinIEEE802.15.4networks［J］.Computer

Networks，2008，52(13):2543-2557.

［7］ChengLiang，BourgeoisG，Sallocation

schemeforIEEE802.15.4networkswithimprovedbandwidthutilization

［C］//ProcofISCIT＇:IEEE，2007:1143-1148.

［8］XiaFeng，HaoRuonan，CaoYang，-GAS:anadaptiveand

real-timeGTSallocationschemeforIEEE802.15.4［C］//ProcofAINTEC＇

k:ACM，2011:96-103.

［9］LiYueheng，JuMeiyan，YePengfei，ovedGTS

TransmissionAlgorithmforMarine-environmentMonitoringWSNSystems

［C］//ProcofArtificialIntelligenceandComputationalIntelligence-Third

n，China:Springer，2011:538-545.

［10］李洪峻，李迅，马宏绪.无线传感器网络MAC协议实时性研究［J］.计算

机工程，2009，35(23):78-80.

［11］丁海霞.传感器网络中一种实时的自适应时隙调度算法［J］.计算机工程与

应用，2010，46(22):110-116.

［12］黄志杰，李峰，高强.无线多媒体传感器网络实时MAC协议［J］.计算

机科学，2010，37(11):81-85.

［13］王磊.基于实时应用下IEEE802.15.4网络的研究和改进［D］.郑州:郑州大

学，2011.

［14］ChenJ，FerreiraL，icitGTSallocationalgorithmfor

IEEE802.15.4［C］//Procof2011IEEE16thConferenceonEmerging

Technologies＆:IEEE，2011:1-8.