多节点共享保障时隙分配策略*

范书瑞,闫 伸,高 蒙

(河北工业大学信息工程学院,天津 300401)



多节点共享保障时隙分配策略*

范书瑞*,闫 伸,高 蒙

(河北工业大学信息工程学院,天津 300401)

在现代工业无线网络中,IEEE 802.15.4标准以其独特的低功耗、低成本特点被广泛应用。IEEE 802.15.4可以提供最低0.006%的占空比,最大限度降低功耗,同时提供的保障时隙GTS机制为节点提供了实时服务保障。然而,在为大规模节点提供保障时,IEEE 802.15.4提供的GTS机制缺乏灵活性,只能为有限节点提供实时保障服务。本文针对这一问题提出一种多节点共享保障时隙分配策略,允许多个数据流在满足延迟需求前提下,共享同一个GTS减少带宽浪费。分析表明,多节点共享的保障时隙分配策略与普通分配方法相比,可有效提高带宽利用率。

工业无线网络;保障时隙分配;实时服务;带宽利用率

近年来,无线网络技术快速发展,在实时性和可靠性方面取得进步,为其在工业的应用提供了可能。在传感层采用无线措施是实现工业环境下物联网的关键,现在主流的工业无线网络技术主要解决现场通信问题。目前由IEC TC65推出的WirelessHART[1]、美国仪表系统与自动化协会ISA推出的ISA100.11a[2]和我国自主研发的WIA-PA[3]标准形成三足鼎立的局面。IEEE802.15.4标准则以其技术的合理性和先进性的统一,被广泛应用于以上3个工业标准中。文献[4]采用自触发采样策略减少网络利用和能耗损耗的同时,确保了网络性能。文献[5]针对能量敏感问题设计了模型预测控制,确保WSN鲁棒性。这些也都证明IEEE802.15.4适用于现代工业网络控制系统。

IEEE802.15.4可以提供最低0.006%(1/214)的占空比,最大限度降低功耗,同时提供的GTS机制为节点提供了一种实时服务保障,满足对时间敏感场合的应用,可预测每个应用节点的最糟糕性能。信标使能模式下,PAN协调器周期性的发送信标帧同步网络,对请求实时保障的节点分配GTS。超帧最多可以分配7个GTS形成CFP阶段,因此享用GTS保障的节点就不能超过7个,其余节点使用CSMA/CA协议竞争使用CAP阶段。文献[6]采用网络演算方法研究有限的时隙资源分配,提高可享受保障服务的节点数,是一种最糟糕情况下的确定性能分析方法。文献[7]对时隙CSMA/CA机制建模进行了分析,但是当高优先级节点较多时,依然不能避免CSMA/CA机制本身不可预测的弊端。为了满足有严格传输时延期限要求场合的应用,文献[8]提出自适应调整占空比的方法,文献[9]提出保障时隙调度算法,这种两种算法都需要设备节点掌握网络全局信息,在网络参数改变时应变力较差。文献[10]提出一种多信标的超帧提高带宽利用率,文献[11]提出的时分信标调度TDBS(Time Division Beacon Scheduling)根据负载大小改变信标帧BI发送间隔,并且文献[12]对TDBS的系统容量进行了分析,实际上就是改变了超帧结构,需要全局设备节点同步调整。

对大规模节点提供保障时,GTS机制缺乏灵活性,只能为有限节点提供实时保障服务。本文介绍一种共享GTS策略,允许多个数据流在满足延迟需求前提下,共享同一个GTS。同时通过减少GTS带宽浪费提高CFP利用,CFP长度最小化使得CAP最大化。共享GTS的关键就是分析给定数据流共享确定时隙的可调度性,并且不需要单独考虑数据流周期信息,而是采用了一种更一般的到达曲线描述达到流量,是基于网络演算的一种描述。

1 保障时隙带宽利用与分配

IEEE 802.15.4在PAN协调器同步的星型拓扑基础上,通过子协调器可以扩展出簇结构网络,用于组建大规模传感采集网络。设定每个网络节点i产生数据流Fi,受限于到达曲线ai(t)=bi+rit,其中bi是最大猝发数据大小,ri是平均到达速率,Di表示Fi的最大延迟需求。采用Fspec,i=(bi,ri,Di)表示数据流Fi。

RTS表示每个时隙的保障带宽,RkTS表示分配了k个时隙GTS的保障带宽:

RkTS=k·RTS

(1)

需要考虑的主要问题就是对N个数据流Fspec,i=(bi,ri,Di)的请求节点,如何公平的分配k个时隙。在保证网络中设备节点传输时延界限要求的情况下,N个数据流共享k个时隙的GTS,必须满足2个条件[12]:

条件1:

(2)

条件2:

Di,max≤Di,∀1≤i≤N

条件1表示到达速率ri的总和不能超过k个时隙完整带宽,条件2表示为每个数据流Fi分配的GTS延迟界限不能超过最大延迟需求。

1.1 专用GTS带宽利用

考虑一个数据流Fi=(bi,ri,Di),对节点i分配ki个时隙的GTS,带宽利用率定义为:

(3)

(4)

可分配的最小带宽是由单个时隙提供的RTS,节点i要求分配ki个时隙的GTS,则GTS提供的保障带宽和节点i的到达速率ri满足:

(ki-1)·RTS

(5)

从式(1)、式(3)和式(5)可得:

(6)

所以,最小带宽利用界限为[11]:

(7)

从图1可以看出,分配一个时隙的GTS利用率最低。这是由于数据流的到达速率只是占用了不可分割带宽RTS的很小一部分。所以考虑到达速率比较低的WSN中,在满足数据流延迟要求的前提下,可以与其他节点共享时隙。

图1 GTS带宽最小利用率

1.2 提高带宽利用的共享GTS分配

N个数据流总到达速率小于或等于GTS保障带宽,就可以共享一个GTS。而主要问题是,在每个信标间隔BI间寻找适当的时隙分配调度,使为每个数据流提供的保障带宽大于或等于它们的到达速率。循环调度RRS为GTS提供了一个比较平等的共享方式,为所有数据流提供了一个无任何差别的相同数目的保障带宽。每个数据流到达速率需要共享的GTS小于平均GTS时RRS有效。N个数据流Fspec,i=(bi,ri,Di),i=1,…,N平均分配k个时隙的多个GTS,则:

(8)

各个数据流的到达速率一致时,平均共享GTS比较有效。共享GTS的每个数据流都要满足式(2),与WSN中每个传感器采用相同采样速率的情况比较一致。为了简便且不失一般性,分析一个时隙的数据流分配。原因有2点:WSN中的数据流产生速率比较低;单个时隙分配更能反映i-GAME方法。

根据共享GTS分配的定义,N个数据流Fspec,i=(bi,ri,Di),i=1,…,N分配k个时隙的GTS利用率:

(9)

GTS中单个数据流的利用率:

(10)

与专用分配一个时隙一致,共享GTS分配的到达速率ri≤RTS。问题简化为,对k个时隙长的CFP,平均分配共享GTS,其中k≤N。在这种情况下,CFP长度不能超过7个时隙,因为最多可以分配7个GTS,每个GTS长度是1个时隙。

2 共享GTS分配举例

假定IEEE802.15.4簇网络中,PAN协调器设定超帧结构BO=SO=0,相应的BI=SD=15.36 ms,TSlot=0.96 ms和RTS=9.38 kbit/s。

对于速率是R,延迟时间为T的速率-延迟服务曲线一般描述为:

βR,T(t)=R·(t-T)+

(11)

对于n个时隙GTS提供的保障带宽是Rn,延迟时间是Tn,可知提供的速率-延迟服务曲线是:

βRn,Tn(t)=Rn·(t-Tn)

(12)

(13)

保障服务的等待时间:

Tn=BI-n·Tslot

(14)

可得n个时隙GTS的延迟上界

(15)

2.1 1个节点调度实例

设定节点A产生数据流FA受限到达曲线aA(t)=0.4+3tkbit,向PAN协调器发送GTS分配请求的流量规格是Fspec,A=(400 bit,3 kbit/s,150 ms)。PAN协调器根据资源现状决定是否接受数据流FA请求。根据式(13)和(14)可得保障带宽Rn=9.38 kbit/s和等待时间Tn=BI-nTslot=14.40 ms。单时隙GTS提供的服务曲线:

如图2描述了节点A的GTS分配和它的服务曲线。采用式(15),PAN协调器根据Fspec,A可以计算单个时隙的延迟保障边界:

同时单个时隙分配的保障带宽9.38 kbit/s大于到达速率3 kbit/s。式(2)中的条件得到满足,因此对数据流分配单个时隙。节点A使用了GTS的部分带宽,根据式(9)可以计算利用率rA/RTS=31.98%。

图2 一个节点的单个时隙分配

2.2 2个节点调度实例

在节点A基础上,节点B产生数据流FB,按规格要求Fspec,B=(400 bits,3 kbit/s,150 ms)申请分配GTS。

采用循环调度共享一个时隙,在每个信标间隔BI间交替变化两个数据流,如图3(a)。图3(b)对节点A和节点B采用另外一种不同于循环调度的方式,虽然保障带宽没有变化,但改变了服务曲线。最大的等待延迟变成3BI-TS=45.12 ms,此时FA,max=FB,max=130.41 ms也可以满足式(2)中的2个条件。图3(c)描述了每个数据流对应的服务曲线,其中分配时隙2BI-TS=29.76 ms,节点A速率bA=3 kbit/s,节点B速率bB=3 kbit/s。

图3 两个节点的单个时隙分配

2.3 3个节点的调度实例

在节点A和节点B的基础,节点C产生数据流Fc,按规格要求Fspec,c=(400 bit,3 kbit/s,150 ms)申请分配GTS。根据循环调度,计算为每个数据流提供的服务曲线β3node,1TS(t)=3.12·(t-45.12)+,如图4(a)。每个数据流的延迟边界分别是:

DA,max=DB,max=DC,max=173.33 ms≥150 ms

虽然到达速率总和低于保障带宽3+3+3<9.38,但节点B和C的延迟不能保障,不能与节点A共享一个时隙。

DA,max=DB,max=DC,max=92.8 ms≤150 ms

采用2个时隙可以满足3个数据流需求。

图4(c)描述了每个数据流对应的服务曲线,其中分配时隙2BI-2TS=28.80 ms,节点A速率bA=3 kbit/s,节点B速率bB=3 kbit/s,节点C速率bC=3 kbit/s。

图4 3个节点的时隙分配

3 共享GTS延迟界限分析

本文采用扩展CFP长度,循环调度计算相应服务曲线的分析方法。

采用循环调度寻求N个数据流共享k个时隙的服务曲线,其中k≤N,并且数据流Fi的到达曲线ri≤RTS。每个超帧的GTS最多7个,因此k≤7。因为采用平等共享GTS的循环调度策略,所有数据流共享GTS的βi(t)等价于速率-延迟服务曲线βR,T(t)。分两种情况分析:

k=N时类似专用分配,采每个节点都有自己的时隙。每个节点延迟界限Di可以通过式(15)计算。

k

(16)

T=p·BI+q·Tslot

(17)

其中p∈N表示与服务延迟相关的信标间隔数,q∈Z-表示从延迟中减去的时隙数。

对于k≤7和N≥1得:

(18)

在循环调度下,N个节点平等共享k个时隙的服务曲线(k

(19)

因此,对一个数据流Fi(ri≤R),平均共享延迟界限:

(20)

图5 共享GTS延迟界限

4 数值分析

通过举例比较共享GTS分配与专用GTS带宽利用。假定有10个数据流Fi(i=1,…,10),到达速率分别是1.25、1、0.5、1.25、1、0.5、1.25、1、0.5和1(单位kbit/s)。由于保障延迟主要依赖猝发数据的多少,假定所有数据流有相同的促发值bi=200 bit(i=1,…,10)。PAN协调器设定参数为BO=SO=0的网络,相应的BI=SD=15.36 ms,Tslot=0.96 ms和RTS=9.38 kbit/s。考虑3种情况:①数据流F1到F5采用专用GTS分配;②数据流F1到F5采用共享GTS分配;③数据流F1到F10采用共享GTS分配。

图6 专用与共享方法的GPS性能对比

5 结论

传统的GTS分配方法最多只能为7个节点提供性能保障服务,而为了保障网络节点比较多的采集网络中数据的实时传递,就必须采用一种灵活的分配策略。本文在IEEE802.15.4专用GTS分配机制研究的基础上,提出一种共享GTS分配策略。数值分析表明,对到达速率和缓冲数值较小的一类工业传感采集网络,在保证延迟需求的前提下,提高了带宽利用率。

[1] Osama Khader,Andreas Willig.An Energy Consumption Analysis of the WirelessHART TDMA Protocol[J].Computer Communications,2013,36:804-816.

[2]Nguyen Quoc Dinh,Dong-Sung Kim.Performance Evaluation of Priority CSMA-CA Mechanism on ISA100.11a Wireless Network[J].Computer Standards and Interface,2012,34(1):117-123.

[3]Liang Wei,Zhang Xiaoling,Xiao Yang,et al.Survey and Experiments of WIA-PA Specification of Industrial Wireless Network[J].Wireless Communications and Mobile Computing,2011,11(8):1197-1212.

[4]Tiberi U,Fischione C,Johansson K H.Energy-Efficient Sampling of Networked Control Systems over IEEE 802.15.4 Wireless Networks[J].Automatica,2013,49:712-724.

[5]Daniele Bernardini,Alberto Bemporad.Energy-Aware Robust Model Predictive Control Based on Noisy Wireless Sensors[J].Automatica,2012,48:36-44.

[6]Jurcik Petr,Koubaa Anis,Severino Ricardo,et al.Dimensioning and Worst-Case Analysis of Cluster-Tree Sensor Networks[J].ACM Transactions on Sensor Networks,2010,7(2):1-47.

[7]周明伟,樊晓平,刘少强.基于优先级的IEEE802.15.4 CSMA/CA建模与分析[J].传感技术学报,2009,22(3):422-426.

[8]胡倩,陈新.分簇无线传感器网络中密度感知的自适应占空比机制的研究[J].传感技术学报,2013,26(1):105-109.

[9]Chewoo Na,Yaling Yang,Amitabh Mishra.An Optimal GTS Scheduling Algorithm for Time-Sensitive Transactions in IEEE 802.15.4 Networks[J].Computer Networks,2008,52:2543-2557.

[10]Li-Chun Ko,Zi-Tsan Chou.A Novel Multi-Beacon Superframe Structure with Greedy GTS Allocation for IEEE 802.15.4 Wireless PANs[C]//IEEE Wireless Communications and Networking Conference.New York:Institute of Electrical and Electronics Engineers Inc.2007:2330-2335.

[11]Anis Koubaa,Andre Cunha,Mario Alves,et al.TDBS:a Time Division Beacon Scheduling Mechanism for Zigbee Cluster-Tree Wireless Sensor Networks[J].Real-Time Systems,2008,40(3):321-354.

[12]Anis Koubaa,Ma-Rio Alves,Eduardo Tovar.i-GAME:An Implicit GTS Allocation Mechanism in IEEE 802.15.4[C]//Proceedings 18th Euromicro Conference on Real-Time Systems(ECRTS’06).Dresden:IEEE Computer Society.2006:183-192.

范书瑞(1979-),男,讲师,博士,研究方向无线传感器网络和嵌入式系统,fansr@hebut.edu.cn。

GuaranteedTimeSlotsAllocationinMulti-NodeWirelessSensorNetworks*

FANShurui*,YANShen,GAOMeng

(School of Information Engineering,Hebei University of Technology,Tianjin 300401,China)

With unique characteristics of low power consumption and low cost,IEEE 802.15.4 standard is widely used in the modern industrial wireless networks.It can provide the lowest 0.006% of duty ratio to reduce power consumption,and offer real-time service for the node through the guarantee time slots(GTS)mechanism.However,IEEE 802.15.4 can only provide real-time guarantees service for certain nodes,which is lack of flexibility for large-scale networks.A shared security timeslot allocation policy by multi-node is present for overcome the shorting of special GTS allocation method,taking into account the traffic specifications and the delay requirements of the flows.The policy enables the use of a GTS by multiple nodes,and still ensure delay and bandwidth requirements.Numerical analysis clearly showed that,compared with the traditional method,the improvement of allocation policy can effectively improve the bandwidth utilization.

industrial wireless network;GTS allocation;real-time service;bandwidth utilization

项目来源:河北省自然科学青年基金项目(F2013202102);河北省科学研究与发展计划项目(11213566);国家级大学生创新创业训练计划立项项目(201310080009)

2014-01-02修改日期:2014-06-09

10.3969/j.issn.1004-1699.2014.07.021

TP273

:A

:1004-1699(2014)07-0976-06