Ad Hoc网络中一种支持QoS的TDMA MAC协议*

张 浪,李大双,毛建兵,景中源

(中国电子科技集团公司第三十研究所,四川成都610041)

Ad Hoc网络中一种支持QoS的TDMA MAC协议*

张 浪,李大双,毛建兵,景中源

(中国电子科技集团公司第三十研究所,四川成都610041)

在Ad Hoc网络中MAC接入协议对整个网络性能起着至关重要的作用。目前提出的一些MAC协议大部分都从提高网络整体吞吐量及降低时延的角度出发,而针对每个业务的QoS需求、接入时隙抖动等具体的问题考虑不足。针对此问题,提出了一种新的基于业务需求的TDMA MAC协议。将数据段和控制段巧妙地设计为交叉形式,并在数据时隙分配算法中采用二叉树分组选择的方法,避免了在多时隙接入情况下各时隙之间的抖动。引入业务优先级制度,在时隙分配算法中通过接入时延代价等参数来体现,能够满足相应的QoS需求。

自组网 动态TDMA 介质访问控制协议 公平性

0 引 言

Ad Hoc网络是一种分布式、自组织的无线网络。在特定区域内只需要布置无线通信终端即可组成无线网络进行通信,并不需要固定基础通信设施的支持。因此在军事通信、抢险救灾等场合有重要的应用价值[1]。MAC(Media Access Control)协议是Ad Hoc网络协议的重要组成部分,其优劣性将直接影响到整个Ad Hoc网络的性能。

虽然目前针对TDMA MAC动态时隙分配的算法很多,但大多数协议都是从提高网络整体吞吐量以及降低时延两方面进行考虑,而对每个业务而言,缺乏更加细致的控制,很少考虑到时隙抖动、QoS需求[2]等具体问题。

在文献[3]中,Peng等人提出了一种时隙分配算法P-TDMA,使用优先级来竞争占用邻域内空闲时隙,能够提高时隙利用率。不过其所选时隙位置分布具有很大随机性,导致在多时隙情况下时隙之间抖动很大,并不能满足实时性精确度要求较高的业务。在文献[4]中Kanzakid等提出的E-ASAP协议,该协议在ASAP上进行了改进,可以根据节点邻域情况对帧长进行伸缩,尽可能提高时隙利用率。不过当节点间业务量不对称时,也会造成资源浪费。

为了解决上述问题,设计了一种新的基于业务需求的时隙分配协议M-ASAP(Modified Adaptive TDMA Slot Assignment Protocol),可以针对每个具体业务动态改变帧长,并支持QoS。

1 M-ASAP算法

1.1 时帧结构

M-ASAP时帧结构如图1所示,每个时帧由M个子帧组成,且M的值必须是2的幂值,这是基于方便实现时隙周期长度伸缩的考虑。每个子帧包括控制段和数据段两部分,每个控制段又分为N个控制微时隙,每个数据段也分为N个数据时隙。

图1 时帧结构Fig.1 Frame structure

控制微时隙和数据时隙的周期都是一个时帧,而将控制段与数据段设计为交叉形式的主要原因是为了避免时隙间抖动,将在1.3节中进行详细分析。

1.2 控制段

如图1所示一个时帧中共有M×N个控制微时隙,每个节点固定分配一个控制微时隙,周期为一个时帧,因此同一个网络中最多可容纳M×N个节点。控制微时隙固定分配后,不进行复用。

MAC控制消息格式如图2所示,控制段主要包括3方面信息的交互。这些交互信息在MAC控制消息中分别通过“时隙申请”、“邻居时隙分配信息”、“冲突通知”3个字段进行传输。

图2 MAC控制消息格式Fig.2 Format of MAC control message

“时隙申请”,用于发送本节点的时隙资源预约申请。当申请的时隙为空闲时隙时,节点可立即占用发送数据信息,不过如果在一个时帧的侦听期内有任何邻居节点回复冲突,则节点放弃使用,申请失败。如果申请的时隙需要其他节点释放,则发送申请后侦听一个时帧,如一个时帧后未收到任何冲突回复则占用,否则申请失败。如果申请失败,节点会随机退避一定时间后再次申请,如多次申请均失败则认为此时网络负载较大放弃时隙申请。

“邻居时隙分配信息”,用于发送本节点的一跳邻居时隙分配信息。节点收到每个一跳邻居的时隙分配信息后,便可知晓本节点两跳邻域范围内所有邻居的时隙分配信息。如发现冲突则在“冲突通知”中发送相应通知。本节点如需申请时隙资源,也需要通过这些收集到的邻居时隙分配信息来选择可用的时隙。

“冲突通知”,主要包括两类冲突的通知。第一类是本节点发现的两跳邻域内正在使用的数据时隙的冲突;第二类是新的时隙申请可能会造成的冲突。

1.3 数据段

首先分析一下目前大部分协议中存在的时隙抖动问题。如图3所示,为一种使用得较多的帧结构(如P-TDMA、USAP[5]),暂将其命名为传统帧结构。如果网络中某节点需求多个时隙,在网络有可用资源时能够得到满足。但它们的时隙具体位置往往是随机分布的,因此时隙之间的抖动性会很严重。如图4所示,为一时帧中选择2个时隙时,其抖动情况(设定N为10,每个控制微时隙0.1 ms,每个数据时隙1 ms)。

图3 传统帧结构Fig.3 Traditional frame structure

图4 传统帧结构中的抖动情况Fig.4 Jitter of traditional frame structure

针对上述抖动问题,M-ASAP中通过两处巧妙设计避免了时隙间的抖动。第一处是在帧结构中,将数据时隙和控制微时隙间插分布,并将所有数据时隙分为N个组,每组有M个时隙。如图5所示,第K组时隙由每个子帧中的第K个数据时隙联合组成。第二处在时隙分配算法中,每次分配只会在一个分组中进行。

图5 数据时隙分组结构Fig.5 Group structure of data slot

在数据时隙分配算法中,通过上述两处设计完全可以保证所选时隙间的严格周期性。在一次分配算法的执行中即便选择了最多的M个时隙(周期为一个子帧长),所选择的时隙也间隔均匀的分布在各个子帧中,如图6所示(子帧长度假定为11 ms),没有时隙抖动现象。而如果选择的不是最小周期,则有二叉树分配原则来保障其严格的周期性,因此也不会有时隙抖动。

图6 M-ASAP中最小帧长时隙分布Fig.6 Slot distribution of M-ASAP in minimal frame length condition

下面介绍二叉树映射及分配方法。M为2的幂值,因此可以将这样一组时隙构建成一棵二叉树[6]。以第1组为例,设定M为8,N为4,其二叉树结构图如图7所示。将二叉树结点用标签(x,y)进行标示[7]:x为周期标示(为了叙述方便,周期32代表一个时帧长度);y为其在相应周期内位置标示。

二叉树上的结点实际上是特定时隙资源的集合,不同的结点代表不同的集合。如图7所示最底层结点周期为32,各自对应一个具体数据时隙,各自的y值为其在时帧中的具体位置标号。如(32, 17)代表时帧中第17个数据时隙。第三层结点周期为16,在每时帧中包含两个数据时隙。如(16,1)包含(32,1)和(32,17)两个结点对应的数据时隙。第二层结点周期为8。同理如结点(8,1)包括了(32, 1)(32,9)(32,17)(32,25)所对应的4个具体数据时隙。最高层结点(4,1)包含该组中的所有数据时隙,周期为4。

图7 二叉树与数据时隙对应关系Fig.7 Correspondence between binary tree and data slot

通过上述映射可见,无论选择二叉树中哪一层结点,都能保障其严格的周期性,不会出现抖动。

在选择用于申请的时隙时,优先选择组号较小的数据分组,这样可以保证尽可能多的二叉树高层次资源空闲以供后续选择。

1.4 时隙选取算法

每个节点可以有多个业务请求,根据需求为每个业务选定一个优先级。每个业务通过下面4步来选出可用于申请的时隙资源。设定M为8,N为4。

1)建立4组空闲二叉树,将2跳邻域节点和自己的时隙分配信息,填充到二叉树上。如被占用,则在对应结点上标记并存储相应业务的优先级,以及占用该结点的业务数。

2)在二叉树上对某一结点a而言,如果另外一个结点b包含的时隙资源和该结点包含的时隙资源至少有一个相同时,定义结点b为结点a的亲属结点。如图7所示结点(16,1)的亲属结点包括(32, 1)(32,17)(8,1)(4,1)。

定义t为结点的自身代价,具体含义为假设所有亲属结点都没被占用,仅仅结点自己被占用时,业务申请该结点所需要付出的代价。如图8所示,结点占用(16,1)的代价即为自身代价。如果该结点有多个业务占用,则其最终值t为每个业务t值之和。

定义T为结点的占用代价,T和t的区别在于,实际上在二叉树中,对于某一结点而言其亲属结点往往都不会是空的。在这种情况下,占用该结点的代价就不仅仅是t了。如图8所示,如果需要占用(8,5)结点,则其代价不仅是与现有的(8,5)结点占有者冲突,而且也会和其子结点(16,5)的占有者冲突,因为他们对应的具体时隙资源有重叠部分。因此二叉树结点T值为所有亲属结点t值及自己的t值之和。

t值计算公式定义为:

其中,P为该二叉树结点占有者优先级的对应值,优先级越高其值越大。如果占用者等级高于或等于申请业务等级,则其P值会被设定为一个极大值。L为该二叉树结点所在层级的对应值,层级越高其值越大。

图8 二叉树结点选取Fig.8 Selection of binary tree node

3)定义D为申请时延代价,其含义为本次业务需求未能得到满足带来的时延,其计算公式定义为:

其中,P为本次业务优先级的对应值,L为欲申请资源在二叉树上层级的对应值。

4)将第二步计算出的所有T值进行比较,选出最小的T值结点。假定该值为Tmin,再将Tmin与第三步计算出的D值进行比较。设定一个参数a,如果a×D值大于Tmin值,则将该二叉树结点确定为欲申请的资源对象,在下一次控制消息中申请。否则选取失败,无可用资源。a是一个0到2的数字,其值越大则高等级业务越容易占有资源。

2 算法的分析

2.1 算法分析

每个节点可以有多个业务,且可对应不同的优先级。并通过设定优先级数、业务数、每节点总体业务量大小、a值大小,能适应不同QoS需求情形。相比传统协议而言,每个节点有多个业务资源分配,因此在控制信息交互时,开销可能会略有增加。不过在宽带通信条件下,增加的这点开销对吞吐量和时延等指标的影响都很小,而且相比于获得的QoS效果而言这点牺牲也是值得的。

针对传统帧协议中存在的时隙抖动问题,采用了控制段、数据段交叉分布的帧结构,再结合二叉树时隙分配方式,能实现帧内和帧间的严格周期性,避免了时隙抖动,且没有增加任何开销。

2.2 算法仿真

通过与P-TDMA协议的仿真对比,分析协议性能。其中P-TDMA协议使用动态优先级列表(动态列表较静态列表性能更高[8])。

采用Opnet进行仿真,场景及参数设定:M取值为8,N取值为4,a取值为0.75,优先级数为3,每节点可接入业务数为3。选取16个节点随机分布在70 km×70 km的范围内,每个节点通信距离为10 km,平均一跳邻居数为3,平均两跳邻居数为8。通信带宽设定为1 Mb/s。两协议周期均选定为88 ms,控制开销部分均为8 ms。

如图9所示,1 Mb/s业务量理论上为网络负载饱和业务量。在低于1 Mb/s时,两协议均能完全满足业务需求。此时P-TDMA时延小于M-ASAP,这是因为前者只使用自己的主时隙,能快速接入,而后者需要申请时隙,且有可能会有申请冲突。

图9 接入时延vs.负载Fig.9 Access delay vs load

在负载大于1 Mb/s后,P-TDMA的时延越来越大,这是因为主时隙已不能满足需求,需竞争额外的空闲时隙,但资源总是有限的,负载越大时延当然也会越大。M-ASAP中,随着负载增大,时隙冲突也增大,因此时延也会略微有增加。当负载增大到时隙资源无法满足时,低等级业务会被丢弃,因此获得传输机会的业务的时延不会有明显增加。

如图10所示,低负载情况下,所有业务均能获得足够的资源发送。而当负载超过饱和值后,MASAP较P-TDMA明显能获得更大的吞吐量。因为P-TDMA是根据优先级列表对空闲时隙进行竞争,然而某一邻域内空闲时隙很可能没有被任何节点申请成功,导致资源浪费。而M-ASAP不同,在业务量很大的情况下,任何一个邻域内任何一个时隙资源至少都有一个业务在使用。因此在大负载情况下,M-ASAP明显可以获得更好的吞吐量。

图10 吞吐量vs.负载Fig.10 Throughput vs load

此处业务3即优先级为最高等级的业务。在仿真中,将总体业务量大小相同的3个等级业务随机分布在网络中各节点上,观察业务3发送率随负载变化情况。如图11所示,可明显看出P-TDMA中业务3发送率在负载大于饱和值后不断下降,那是因为协议没有考虑QoS,在业务量较大时,每个等级业务获得额外时隙的机会是相等的。而M-ASAP中则是优先满足高等级业务,因此在业务3的业务量大小没有超过网络容量极限时可以得到几乎100%的发送率。

如图12所示,我们在仿真中随机取出有2个时隙需求的业务,观察其两个时隙间的时间间隔。横轴“接入时间”为该业务获得的数据时隙发送时间,而“接入间隔”为本次数据时隙发送时间与上次发送时间之间的间隔。

图11 业务3发送率vs.负载Fig.11 Transmission probability of service 3 vs load

图12 接入间隔vs.接入时间Fig.12 Access interval vs access time

从图12中可观察到,尽管二者平均时间间隔都在44 ms左右,但P-TDMA的间隔时间相当不稳定,而M-ASAP中则是固定的44 ms间隔。这就是由1.3节中描述的传统帧结构中时隙抖动问题造成的,而M-ASAP的设计中解决了该问题。

3 结 语

针对Ad Hoc网络提出了一种新的基于业务需求的TDMA MAC协议。交叉形式的帧结构结合二叉树分组分配方法,避免了在多时隙接入情况下各时隙之间的抖动。并采用了业务优先级制度,满足QoS需求。仿真结果也表明,协议设计取得了较良好的效果,获得了较高的吞吐量和较低的接入时延,同时满足了实时性、QoS需求,克服了时隙抖动问题。不过文章仅仅在理论和仿真上对协议进行了分析,还需要进一步在实践中检验其性能。

[1] 候祥博,王一强,杨金政.移动Ad Hoc网络技术研究与应用[J].通信技术,2009,42(08):15-20.

HOU Xiang-bo,WANG Yi-qiang,YANG Jin-zheng. Mobile Ad Hoc Network Technology and Its Application [J].Communications Technology,2009,42(08):15-20.

[2] ZHANG Yun.The Research on QoS Model Design in Mobile Ad Hoc Networks[J].IntlJ.of Communications,Network and System Sciences,2012,05(11):720-723.

[3] 彭革新,谢胜利,陈彩云.一种基于固定TDMA的无冲突动态时隙算法[J].信息安全与保密通信, 2005(11):115-200.

PENG Ge-xin,XIE Sheng-li,CHEN Cai-yun.A Collision-Avoid Dynamic Slots Assignment Algorithm based on Fixed TDMA[J].Information Security and Communications Privacy,2005(11):115-120.

[4] A.Kanzaki,T.Hara,S.Nishio.An Adaptive TDMA Slot Assignment in Ad Hoc Networks[C]//Proceedings of the 2005 ACM symposium on Applied computing(ACM 2005).London,UK:IEEE,2005:160-165.

[5] C.D.Young.The Mobile Data Link(MDL)of the Joint Tactical Radio System Wideband Networking Waveform [C]//Proceedings of IEEE Military Communication Conference(MJLCOM 2006).Washington,D.C.USA: IEEE,2006:23-25.

[6] XU Ming-xia,ZHAO Min-jian,CHEN Jie,et al.Binary -tree-based Adaptive Slot Assignment Protocol for Ad hoc Networks[C]//Proceedings of International Conference on Global Mobile Congress(GMC 2006).Beijing, China:IEEE,2006:10-12.

[7] J.Gentian,N.Mike,R.Ram.A Framework for Frameless TDMA Using Slot Chains[C]//Proceedings of International Conference on Mobile Ad Hoc and Sensor Systems(MASS 2012).Las Vegas,NV,USA:IEEE, 2012:56-64.

[8] 吉彬,苏旸.基于哈希算法的动态TDMA时隙分配研究[J].通信技术,2012,45(08):47-49. JI Bin,SU Yang.Study on Dynamic TDMA Slots Assignment based on Hash Algorithm[J].Communications Technology,2012,45(08):47-49.

A TDMA MAC Protocol Supporting QoS in Ad Hoc Network

ZHANG Lang,LI Da-shuang,MAO Jian-bing,JING Zhong-yuan
(No.30 Institute of CETC,Chengdu Sichuan,610041,China)

In Ad Hoc network,MAC access protocol plays a crucial role in whole network performance. Current MAC protocols are mostly designed from the perspective of improving throughput and reducing time -delaying,but ignoring the specific problems of different businesses,such as QoS requirements and time slot jitter.Aiming at the problem,this paper proposes a novel TDMA MAC protocol based on business demands.The data section and control section are cleverly designed in crossed style,and adopts the binary tree method is adopted in the slot allocation algorithm,thus to avoid the jitter of between various time slots in multi-slot access.The QoS requirements are satisfied by introducing the system of business-priority grades,reflected by parameters such as time-delaying cost in the slot allocation algorithm.

Ad Hoc;dynamic TDMA;MAC protocol;QoS

TP393

A

1002-0802(2014)10-1162-05

10.3969/j.issn.1002-0802.2014.10.011

2014-07-13;

2014-08-20 Received date：2014-07-13;Revised date：2014-08-20