基于TDMA的无冲突动态时隙分配算法

崔可嘉,孙 昕

(北京交通大学电子信息工程学院,北京100044)

基于TDMA的无冲突动态时隙分配算法

崔可嘉,孙 昕

(北京交通大学电子信息工程学院,北京100044)

针对分簇Ad Hoc网络中固定时隙分配算法信道资源浪费和竞争时隙分配算法传输延迟不固定的问题,提出一种基于时分多址接入的无冲突动态时隙分配算法。该算法根据网络负载动态调整帧长,即当网络负载增大时,增加帧长,提高信道利用率;当网络负载减小时,减少帧长,降低信道申请时延。仿真结果表明,与NEBS算法和时隙ALOHA算法相比,该算法可根据网络负载动态调整资源分配,从而提高系统的吞吐量。

时分多址;时隙分配算法;时隙回收算法;无冲突;Ad Hoc网络;吞吐量

1 概述

在Ad Hoc网络中,时隙分配算法控制信道资源的分配,直接影响系统的性能。时隙分配算法分为2类:基于竞争的分配算法和基于调度的分配算法[1]。

基于竞争的分配算法允许节点通过随机接入的方式争用时隙,典型的基于竞争的分配算法包括时隙ALOHA和CSMA/CA等[2-4]。尽管这类分配算法得到了广泛的应用,但由于其基于竞争的本质,当负载上升后,数据的传输时延难以得到保证,因此难以满足实时业务(如视频、语音等)的要求。

最典型的基于调度的分配算法是TDMA时隙分配算法。网络中各节点被分配一定数量的时隙,进行无冲突的数据传输,可以满足服务质量(QoS)的需求[5]。时隙分配算法控制资源的分配,直接影响系统吞吐量,是这类算法研究的重点[6-7]。

在文献[8]提出的NAMA算法中,各个节点拥有一个随机数种子,并以此计算哈希值(Hash),决定当前时隙的使用者。各个节点通过交换随机数种子,即可计算网络内所有节点在当前时隙的哈希值,实现无冲突地传输数据。但是NAMA算法仅能实现信道资源的均匀分配,未考虑到各个节点负载不平衡的情况,造成了信道资源的浪费。同时,在新节点加入网络时,由于其他节点尚未获得其随机数种子,可能引起持续的数据碰撞,导致新节点无法广播自身的随机数种子。

文献[9]提出的NEBS算法对NAMA算法进行了改进。NEBS算法中有3种时隙:基于竞争的NE时隙,用于各节点传输自身的NAMA随机数种子;基于无竞争的NA时隙,使用NAMA算法进行接入,用于各个节点申请数据传输D时隙;基于无竞争的D时隙,进行数据传输。各个节点在NE时隙使用随机接入协议,广播自身的NAMA随机数种子,解决了NAMA算法中有可能产生的持续碰撞。由于NEBS仅使用NAMA算法进行数据传输时隙的预约,因此可以很好地适应网络负载的变化。但是由于NA时隙以及NE时隙不能用于数据传输,它们将固定占用部分时隙,造成时隙资源的浪费。

在文献[10]提出的USAP算法中,每复帧中的帧数N和每帧中的时隙数M均为固定值,需要根据网络规模提前规划。每帧的第一个时隙为唯一的节点保留,用于发送控制信息预约时隙,因此帧数N需大于网络中的节点数。每帧中的时隙数M直接影响系统性能。若M取值过小,则大量时隙用于发送控制信息,造成了信道资源的浪费;若M取值过大,则导致预约时隙的延时过大。每帧中的时隙数M需要预先配置,很难取得最优值。这种算法的分配方式单一、不够灵活,难以应用于节点数较多、负载变化较大的网络。

针对固定帧长度的时隙分配算法,文献[11]将信道资源划分为等间隔的时隙块,然后使用二叉树块内均分法进行信道资源的均匀分配。但是,这种算法逻辑较为复杂,而且在多次划分后会产生不等间隔的小时隙块,这些时隙块不能单独分配给用户,造成了时隙资源的浪费。

文献[12-13]提出的算法针对USAP算法不灵活的缺陷进行了改进。它们以二进制指数增加帧长,调节信道资源的分配。但是这些算法并没有帧长减少机制。新入网节点只能在每帧的第一时隙接入网络,不断增长的帧将导致新节点接入网络的时延增大。同时,过长的帧中存在未分配时隙,降低了信道利用率。

针对网络环境的特点和上述算法的不足,本文提出了一种基于TDMA的无冲突动态时隙分配算法。算法根据网络负载动态调整帧长,调节固定分配时隙和动态分配时隙所占的比例,以解决固定帧长算法不够灵活的问题。

2 算法描述

2.1 复帧结构

对网络环境进行了如下假设:

(1)数据碰撞是导致传输失败的唯一原因;

(2)每个节点拥有各自唯一的ID,且ID号从1开始连续递增;

(3)网络内部节点总数固定,节点可能频繁出入网,且负载不平衡;

(4)网络内有中心,且中心节点与其他各节点均在一跳范围内。中心节点的ID号为1。

在本文算法中,一个复帧包含n个固定帧,n应不小于分簇Ad Hoc网络中的节点数量。一个帧包含k(1≤k≤MAX_SLOT)个不固定时隙,k随网络负载动态调整。MAX_SLOT为每帧最大的时隙数,随着MAX_SLOT的增加,可以对信道资源进行更细致的划分;但是在高负载情况下,若每帧时隙数过大,会导致时隙申请的时延增大。因此,需要根据实际情况设置MAX_SLOT的取值。复帧结构如图1所示。

图1 复帧结构

本文算法中包含2类信令:控制信令和数据信令。控制信令有2种:一般节点的时隙申请信令和中心节点的时隙分配信息信令。每帧包含2个部分:固定分配时隙部分和动态分配时隙部分。每帧的第1时隙为固定分配时隙,第1帧的第1时隙固定分配给中心节点,用于发送时隙分配信息信令,第i帧的第1时隙固定分配给ID号为i的节点,用于发送数据信令或时隙申请信令;每帧的第2～k时隙由簇内中心节点根据网络负载动态分配给各个节点。

文献[9]中的NEBS算法将时隙分为控制信令时隙和数据时隙,控制信令时隙专门用于传输控制信令,不可进行数据信令的传输;同理,在数据时隙不能进行控制信令的传输。本文算法不再做这种划分,除第1帧的第1时隙用于时隙分配信息信令的传输,其他时隙均可传输控制信令或数据信令。当无需传输控制信令时,控制信令时隙的存在会降低时隙利用率;而当节点需要申请时隙时,本文算法可使用节点拥有的任何时隙进行传输控制信令,降低了时隙申请的时延。

2.2 时隙分配流程

时隙分配流程包括2个部分:一般节点申请时隙和中心节点授予时隙。

当网络负载上升时,1个复帧中的1个时隙不能满足数据传输的需求,数据在节点内部的缓存队列中缓存。当缓存队列长度L小于等于帧数n时,节点发送队列中的数据;当缓存队列长度L大于帧数n时,节点将向中心节点发送时隙申请信令,请求中心节点额外分配时隙。申请的时隙数s为:

在收到时隙申请信令后,中心节点判断是否满足时隙授予条件,若时隙数量k未达到最大时隙数MAX_SLOT,则中心节点根据申请时隙数增加每帧中时隙的个数,将这些时隙分配给该节点,并更新时隙分配表;若时隙数量k已经达到最大时隙数MAX_SLOT,则中心节点进行优先级抢占。在1帧1时隙,中心节点发送时隙分配信息信令,各个节点收到后,进行时隙分配信息的同步,确定自身的发送时隙。图2给出了一个时隙分配的例子,网络中共包含5个节点,1个复帧内包含5个帧。

图2 时隙分配举例

在初始状态下,中心节点在1帧1时隙发送时隙分配信息信令,其余节点各拥有20%的信道资源。当3号节点的负载上升,20%的信道资源不能满足传输需求。假设在3帧1时隙时,3号节点的队列长度达到12,根据式(1),它将向中心节点申请2个时隙。在收到时隙申请信令后,中心节点将时隙2和时隙3分配给3号节点,并将每帧时隙数k增加到3,此时帧结构尚未变化。中心节点在下一复帧的1帧1时隙广播新的时隙分配表,各个节点收到新的时隙分配表后,根据其内容更新本地的时隙信息,此时,帧结构发生变化,3号节点可以在每帧的2时隙、3时隙和3帧1时隙发送数据,3号节点拥有73.3%的信道资源。

2.3 时隙回收流程

本文算法可以对未使用的时隙进行回收,减少帧长度,以保证信道资源的高效利用。在时隙分配之后,中心节点将持续监听各个已分配时隙的使用情况,并以复帧(n帧)为单位统计各个节点未使用的时隙数count。在一个复帧结束后,中心节点首先根据监听结果,计算各个节点需回收的时隙数m。需回收的时隙数m为:

然后,中心节点删除时隙分配表中被回收的时隙,并更新每帧时隙数k,最后,中心节点在1帧1时隙发送时隙分配信息信令,其他节点该信令后,进行时隙分配信息的同步。图3给出了一个时隙回收的例子。

图3 时隙回收举例

网络中有5个节点,每复帧包含5个帧。在初始状态下,每帧包含3个时隙,2时隙和3时隙分配给2号节点。在第1复帧中,2号节点在1帧2时隙、2帧3时隙、3帧3时隙和5帧2时隙发送数据,使用时隙数为4,未使用时隙数为7。根据式(2),中心节点应回收2号节点的一个时隙。在第2复帧中,中心节点在1帧1时隙发送新的时隙分配信息信令,各个节点收到后更新帧结构。更新后,每帧包含2个时隙,第1时隙为固定分配时隙,第2时隙供2号节点使用。在时隙回收前,一复帧共包含15个时隙, 2号节点拥有73.3%的信道资源;时隙回收后,一复帧共包含10个时隙,2号节点拥有60%的信道资源。与文献[12-13]相比,本文算法对未使用时隙进行动态回收,使时隙申请得到更快的响应,提高了信道利用率。

2.4 优先级机制

文献[8-13]中的算法均无优先级机制。当网络总负载较大时,各个节点将采用平均分配的方式获取信道资源。在这种情况下,业务的服务质量(QoS)无法得到保障。在本文算法中,时隙申请遵循优先级机制,当网络负载较大时,仅为低优先级节点保留固定分配部分的信道资源,保证低优先级节点不会因为无法申请到信道而“饿死”;高优先级节点将占用大部分信道资源,保证业务的服务质量。

各个节点的优先级在规划网络时配置,在申请时隙时,各个节点声明自身的优先级,以便中心节点进行时隙分配。当每帧的时隙数量k达到最大可分配时隙数MAX_SLOT时,中心节点不能分配新的时隙。这时对于高优先级节点发起的时隙申请,中心节点将遍历整个时隙分配表,寻找最低优先级节点占有的时隙,并将该时隙分配给高优先级节点;对于低优先级节点发起的时隙申请,中心节点将不再响应,低优先级节点可在若干复帧后再次发起时隙申请。

3 算法性能分析

归一化吞吐量(时隙利用率)是衡量时隙分配算法性能的重要指标。对于本文算法,当网络内负载不平衡或网络中节点数较多时,由于固定分配算法的存在,将造成一定信道资源的浪费。考虑最极端的一种情况:网络内部仅有一个节点有数据发送,分配给其他节点的固定时隙均无法得到利用。在这种情况下,归一化吞吐量S应为:

其中,k为时隙数量;n为每复帧中的帧数,由网络中的最大节点数决定。表1给出了n为20和100时,数量k与归一化吞吐量S的对应关系。

表1 时隙数量与归一化吞吐量的对应关系

随着时隙数量k的上升,固定分配时隙所占的比例逐渐降低,有效减少了由于负载不平衡造成的资源浪费。网络中的节点数对归一化吞吐量S影响不大。

平均时隙申请时延t是衡量动态时隙分配算法性能的另一项重要指标。时隙申请时延是指,从一般节点发送时隙申请信令到中心节点发送时隙分配信息信令的时间。平均时隙申请时延t应满足:

其中,k为时隙数量;n为每复帧中的帧数,由网络中的最大节点数决定。平均时隙申请时延t由时隙数量k和网络中最大节点数共同影响。综合式(3)和式(4),可得出以下结论:

(1)随时隙数量上升,吞吐量上升,平均时隙申请时延上升;

(2)随网络规模上升,吞吐量基本保持不变,平均时隙申请时延上升。

对于USAP等固定时隙分配算法,由于时隙数量k为固定值,需要预先定义,很难取得最优值。若时隙数量k过大,虽然可以获得较高的吞吐量,但是带来的负面影响是时隙申请时延上升,即吞吐量与时隙申请时延2项性能指标不可兼得。而本文算法可以随时调整时隙数量k的取值,当网络负载较小时,减少时隙数量,降低时隙申请时延;当网络负载较大时,增加时隙数量,提高吞吐量。

4 仿真结果与分析

利用Matlab软件对本文算法的归一化吞吐量性能进行了仿真。在仿真中,最大时隙数MAX_SLOT为100,每复帧中的帧数n与网络中的节点数量相等,各个节点数据包的到达相互独立。图4给出了在10个节点的网络中,本文算法、NEBS(1∶5∶7)算法[9]、时隙ALOHA算法和理论的G-S曲线。

图4 G-S曲线的对比

在NEBS算法中,每个帧中NE时隙与NA时隙的比为1∶7,NA时隙与D时隙的比为1∶5。在总负载G低于0.8时,本文算法和NEBS算法均接近理论值;随着总负载G的进一步上升,NEBS算法上升变慢,归一化吞吐量S最终稳定于0.83附近。这是由于NA时隙与D时隙的比为1∶5,每6个时隙中有一个时隙用来进行信道预约,因此归一化吞吐量最高仅能达到5/6。而在本文算法中,随着总负载G的上升,每帧时隙数变大,用于发送控制信令的时隙在所有时隙中的比例降低,当总负载G达到1.5时,归一化吞吐量S达到0.98以上。时隙ALOHA算法的归一化吞吐量S在总负载G为1时达到最大值,但仍然不足0.4,随着总负载G进一步上升,碰撞增多,归一化吞吐量S开始下降。

图5给出了在10个节点的网络中2种不同算法归一化吞吐量S随信道负载的变化曲线。在10个节点中,仅有一个节点有数据发送,其余节点皆处于空闲状态。通过控制该节点在不同时刻的包到达率来模拟网络负载动态变化的过程。

图5 归一化吞吐量随信道负载的变化曲线

在0～250时隙范围内,该节点的包到达率为0.9;在250～800时隙范围内,该节点的包到达率为0.5;在800～2 000时隙范围内,该节点的包到达率为0.25,在2 000时隙后,该节点的包到达率为0。

NAMA算法将信道资源平均分配,每个节点占用10%的信道带宽。当包到达率为0.9时,10%的信道带宽并不能满足传输需求,并且整个网络的归一化吞吐量仅为0.1。本文算法可以根据网络负载调整帧长,使帧结构适应当前负载,高效利用信道资源。

5 结束语

本文提出了一种基于TDMA的无冲突动态时隙分配算法。通过动态调整帧长来适应网络负载的变化,进行时隙的动态分配和回收。在低负载时,减少帧长,降低信道申请时延;在高负载时,增加帧长,提高信道利用率。仿真结果表明,本文算法实现了信道资源的高效利用;同时,由于本文算法采用无冲突的数据传输,当负载达到饱和后,吞吐量并不会下降。本文算法为如何高效合理利用时隙资源提供了参考,改善时延性能是下一步研究的重点。

[1] Czapski P P.A Survey:MAC Protocols for Applications of Wireless Sensor Networks[C]//Proc.of TENCON’06.[S.l.]:IEEE Press,2006:1-4.

[2] IEEE.IEEE 802.11-1997 Wireless LAN Medium Access Control(MAC)and Physical Layer(PHY)Specifications [S].1997.

[3] 方 飞,毛玉明.时隙ALOHA二进制指数回退算法[J].计算机应用,2013,33(5):1203-1207.

[4] 徐圆圆,曾隽芳,刘 禹.基于Aloha算法的帧长及分组数改进研究[J].计算机应用,2008,28(3):588-590.

[5] 秦 勇,张 军,张 涛.TDMA时隙分配对业务时延性能的影响分析[J].电子学报,2009,37(10):2277-2283.

[6] 马 柯,俞能海,杨福荣.EASA:一种分簇Ad Hoc网络高效自适应TDMA时隙分配算法[J].电子学报, 2010,38(7):1678-1682.

[7] 任昊翔,郭达伟,邵凝宁,等.一种新型的无竞争的基于TDMA的MAC协议[J].传感技术学报,2013,26 (1):89-94.

[8] Bao Lichun,Garcia-Luna-Aceves J J.A New Approach to Channel Access Scheduling for Ad Hoc Networks [C]//Proc.of the 7th Annual International Conference on Mobile Computing and Networking.[S.l.]:ACM Press,2001:210-221.

[9] Sung P,Denh S.Dynamic Control Slot Scheduling Algorithms for TDMA Based Mobile Ad Hoc Networks [C]//Proc.of Military Communications Conference. [S.l.]:IEEE Press,2008:1-7.

[10] Young C D.USAP:A Unifying Dynamic Distributed Multichannel TDMA Slot Assignment Protocol[C]// Proc.of MILCOM’96.[S.l.]:IEEE Press,1996: 235-239.

[11] 李建勋,樊晓光,张 喆,等.基于优先级的TDMA动态时隙分配算法[J].计算机工程,2011,37(14): 288-290.

[12] Kanzaki A,Uemukai T,Hara T,et al.Dynamic TDMA Slot Assignment in Ad Hoc Networks[C]//Proc.of the 17th International Conference on Advanced Information Networking and Applications.[S.l.]:IEEE Press, 2003:330-335.

[13] Li Wei,WeiJibo,Wang Shan.An Evolutionary-Dynamic TDMA Slot Assignment Protocol for Ad Hoc Networks[C]//Proc.of Wireless Communications and Networking Conference.[S.l.]:IEEE Press,2007: 138-142.

编辑 任吉慧

Dynamic Slot Assignment Algorithm of Contention-avoid Based on TDMA

CUI Ke-jia,SUN Xin
(School of Electronic and Information Engineering,Beijing Jiaotong University,Beijing 100044,China)

Concerning the problem of resource waste in fixed assignment algorithm and uncertain transmission delay in contention assignment algorithm,a dynamic slot assignment algorithm of contention-avoid based on Time Division Multiple Address(TDMA)for clustered Ad Hoc network is proposed.The length of frame can be adapted to the net traffic.When the net traffic increases,the frame length increases to improve channel utilization;when the net traffic reduces,the frame length reduces to reduce the delay of accessing.It is proved by simulation results that the algorithm can increase throughput of the system,compared with NEBS and slot-ALOHA.

Time Division Multiple Address(TDMA);slot assignment algorithm;slot reuse algorithm;contentionavoid;Ad Hoc network;throughput

1000-3428(2014)10-0122-05

A

TP393

10.3969/j.issn.1000-3428.2014.10.024

北京交通大学校基金资助项目(2012JBZ015)。

崔可嘉(1988-),男,硕士研究生,主研方向:Ad Hoc网络,无线接入技术;孙 昕,教授。

2013-10-08

2013-11-26E-mail:ckjhljcy@126.com

中文引用格式:崔可嘉,孙 昕.基于TDMA的无冲突动态时隙分配算法[J].计算机工程,2014,40(10):122-126.

英文引用格式:Cui Kejia,Sun Xin.Dynamic Slot Assignment Algorithm of Contention-avoid Based on TDMA[J]. Computer Engineering,2014,40(10):122-126.