一种改进的动态TDMA时隙分配算法研究

秦 茜

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

一种改进的动态TDMA时隙分配算法研究

秦 茜

(中国电子科技集团公司第五十四研究所，河北 石家庄 050081)

针对移动自组织网络(Mobile Ad-Hoc Networks，MANET)对多节点场景的需求，在基于时分多址(Time Division Multiple Access,TDMA)固定时隙分配的基础上提出了一种改进的动态TDMA时隙分配算法。该算法根据节点数目的改变，通过针对不同的节点等级动态调整时隙分配策略，提高传输效率。对2种算法进行了对比仿真，仿真结果表明，改进的动态TDMA时隙分配算法更能适应节点数目不断变化的场景。

移动自组织网络；时分多址；时隙分配

0 引言

随着无线移动设备使用的普及率越来越高，无线移动通信网络的快速建网和性能优化成为通信领域亟待解决的重要问题。目前绝大多数无线移动设备之间都是通过服务商提供的固定设施来进行通信的，即使2个临近设备之间的通信也需要通过基站，一旦基站出现故障则整个网络将陷入瘫痪之中。为了避免这种情况的发生，MANET应运而生[1-3]。

MANET通常由一组带有无线收发装置的移动终端构成，是一种不需要基础设施支持的动态网络。这些移动终端除了完成传统网络终端所具有的收发功能外还担负着转发功能[4-5]。MANET的正常运行并不依赖于任何有特殊性的移动终端，并且当一些终端离开或加入网络时能够实现对网络的动态调整。

MANET灵活性强、覆盖范围大、系统容量高且有着高效自组织能力，可以适应军事通信中面临的复杂无线电环境，满足即使没有固定基础设施也能保证通信性能的要求，具有很好的应用前景[6-7]。

MAC协议作为MANET的关键技术之一，为MANET提供了必要的信道资源的分配功能与业务调度策略，确保了节点之间可以进行高质量的无线多跳通信[8]。MANET具有无中心、自组织、动态拓扑等各种不同于传统网络的特点，因此传统网络中使用的MAC协议无法直接应用到MANET中。多年来研究人员针对MANET提出了一些专用的MAC协议，这些都有各自的优缺点和适用范围，因此如何针对特定的需求选择和设计合适的MAC协议也就成为了研究的热点[9]。

为了配合多节点随机移动场景的需求，本文提出了一种改进的动态TDMA时隙分配算法，根据网络状态及拓扑结构动态划分节点等级，提高网络的传输效率并利用仿真软件对算法性能进行了仿真。

1 典型的动态TDMA时隙分配算法分析

目前主要的MANET的MAC协议可以分为3类：基于竞争的MAC协议、基于分配的MAC协议和混合的MAC协议[10]。

1.1 基于竞争的时隙分配算法

在基于竞争的MAC协议中，当节点有传输任务时，通常是通过自由竞争的方式占用信道。当同一时刻竞争同一个信道的节点数等于或大于2个时，就会出现冲突[11]。基于竞争的MAC协议可以在传输负载比较低的情况下运行良好。但是在传输负载很重时，基于竞争的MAC协议的性能就会非常不理想。随网络负载的增加，基于竞争的MAC协议的吞吐量性能如1所示[12]。

图1 基于竞争的MAC协议性能示意

1.2 基于分配的时隙分配算法

在基于分配的MAC协议中，首先将物理信道划分为较小的“段”，然后将这些“段”或动态或静态地分配给需要通信的节点，以此来避免冲突，根据网络通信流量最大限度地节省能量。

TDMA协议是一种常用的基于分配的MAC协议，其帧结构如图2所示。TDMA将时间划分成互不重叠的帧，然后将帧划分为互不重叠的时隙，将不同时隙与不同的节点ID(Identity)相对应。TDMA协议网络性能如图3所示，随着网络负载的增加，基于TDMA的MAC协议的吞吐量在达到饱和之后就不再有所增加。

图2 TDMA帧结构示意

图3 基于分配的MAC协议性能示意

1.3 混合的时隙分配算法

基于竞争的MAC协议与基于分配的MAC协议各有利弊，因此如何取长补短发挥2种协议各自优势同时又能尽量避免短板，这是MAC协议研究领域的挑战和热点。从PTDMA(Users-Probabilistic Time Division Multiple Access)混合协议[13]到混合TDMA/CMSA(Time Division Multiple Access/ Carrier Sense Multiple Access)协议[14]再到ADAPT(A Dynamically Self-Adjusting Protocol)协议[15]，都面临着同样的问题，即没有一个避免冲突的有效机制，因此都没有得到广泛的应用。

2 基于TDMA的固定时隙分配算法

在基于TDMA的固定时隙分配算法中，正常运行状态下每个节点将平均分配时隙，使系统具有最低延迟保障，保证数据发送的稳定性和时效性，其帧结构如图4所示。

图4 基于TDMA的固定时隙分配算法的帧结构

在基于TDMA的固定时隙分配算法中，各个节点均能够平均地得到时隙，这在对传输效率需求不高的情况下，其延时性能以及节点的抗冲突性能都呈现良好的状况。但是当节点数量逐渐增加，并相应地对网络的传输效率提出更高的需求时，基于TDMA的固定时隙分配算法并不能良好地适应这样的动态场景。因此有必要提出一种新的TDMA时隙分配协议，能够根据节点数目动态地调整这些参数的方法。

3 改进的动态TDMA时隙分配算法

3.1 协议原理

在本文提出的改进算法里，一级节点为高等级节点，二级节点为低等级节点。一级节点通过基于TDMA的固定时隙分配算法来分配得到可固定使用的TDMA时隙，二级节点则没有固定的时隙可用，通过定期检测共享TDMA时隙是否可用来及时地占用空闲时隙进行通信。并且定期检测的频率根据其邻居中二级节点的个数来进行动态调整。本文协议流程如图5所示。

移动节点的等级划分时刻遵循着一个根本原则，即每一个二级节点在一跳范围内至少有一个一级节点。这意味在一条路由上，信息的传输过程大致可以进行这样的描述。每个二级节点是路由可达的，但是不会被选为转发节点，只有一级节点有机会被选为路由转发节点，这就形成了由一级节点组成的高容量的虚拟主干覆盖网络，如图6所示。

图5 本文协议流程

图6 MANET的2层结构设计示意

因此，当一个二级节点产生的数据包需要传输到比较远的目的地时，数据包在它的第一跳可以达到一级节点，从而通过高传输速率的主干网络上的路由到达目的节点。该主干网络适合用户数据包和MANET控制包的数据传输和延迟。因为每个一级节点在每一个帧周期都有一个分配给它的循环TDMA时隙，它通常既可以传输它产生的数据又可以传递来自其他节点的数据，每个功能都可以保持低延迟。

3.2 时隙帧结构的设计

根据本文提出的算法的工作原理，对帧结构进行了特定的设计，不同于传统的TDMA帧结构，本文提出的改进算法对应的传输帧由信令间隔、竞争间隔和数据间隔3部分组成，如图7所示。每个一级节点在每个帧周期内均会占有一个TDMA信令时隙，作为网络中节点控制同步、时隙分配以及控制其他行为的信道，且每个信令时隙均在数据间隔内对应一个可用的数据发送时隙，作为每个节点的传输业务数据的信道。一级节点通过基于TDMA的固定时隙分配算法可以使得每个节点在数据间隔获得至少一个固定的TDMA时隙，以便其进行大数据量的传输。二级节点则没有固定的专用TDMA时隙，而是在需要传输的时候通过CSMA/CA(Carrier Sense Multiple Access with Collision Avoidance)机制在竞争间隔获得TDMA时隙来传输。

图7 帧结构的设计

由于帧结构的设计中，用于给一级节点分配的可以固定循环使用的TDMA时隙数量是有限的，因此改进的动态TDMA时隙分配算法通过超额的一级节点降为二级节点，来平衡不断升级的节点数量。同时，如果一个二级节点发起一个大容量同步数据流，那么它就可以很容易地晋升为一级节点，从而获取一个可循环使用的TDMA时隙。随着二级节点数量增大，为了保持二级节点信道访问正常运行，分配给每个二级节点的二级节点访问信道必须愈来愈小。因此本文提出的改进的动态TDMA时隙分配算法可以将二级节点访问信道灵活地切割成更小的时间段。

4 仿真与分析

4.1 仿真环境及参数设置

为了测试本文提出协议的合理性和性能，采用与基于TDMA的固定时隙分配算法进行对比的方式，分析2种算法在传输层时延和端到端吞吐量的仿真数据。仿真的具体参数设置如表1所示。

表1 仿真场景参数值

参数名称参数值环境尺寸/km通信距离/km仿真时间/s节点最大移动速率/(km/h)20×2021080

4.2 仿真结果与分析

4.2.1 传输层时延

2种时隙分配算法的传输层时延变化曲线如图8所示。从图8可知，在基于TDMA的固定时隙分配算法中，在节点数量达到10时传输层时延一直在1 s以下，但是在节点数量超过10之后，延迟急剧增加；在改进的动态TDMA时隙分配算法中，其传输层时延并没有明显的改变。这主要是由于基于TDMA的固定时隙分配算法是注重公平性的策略，而本文提出的新算法由于更加注重效率，所以在部分固定时隙的基础上加入了动态分配时隙策略，大幅度减少了等级高的节点的传输层时延。

图8 2种算法的传输层时延对比

4.2.2 端到端吞吐量

基于TDMA的固定时隙分配算法与本文提出的改进的动态TDMA时隙分配算法的端到端吞吐量对比结果如图9所示。

图9 2种算法的端到端吞吐量对比

从图9可以看出，基于TDMA的固定时隙分配算法由于不能动态适应节点数量的变化，对于节点数大于16之后的场景，其端到端的吞吐量急剧下降；相对于基于TDMA的固定时隙分配算法，本文提出的改进的动态时隙算法由于充分利用了固定时隙分配、动态时隙竞争的优点，引入动态分级原理应对节点数量的变化，针对不同等级的节点实时调整时隙分配策略，提高了传输效率。

5 结束语

目前，MANET的许多理论和技术仍处于探索阶段，但其巨大的潜能会得到人们越来越多的重视。本文在基于TDMA的固定时隙分配算法的基础上提出了一种改进的动态TDMA时隙分配算法，通过节点的动态分级和拓扑的2层结构，在保证基本业务质量的前提下，根据节点数量的增加，最大限度地满足大数量用户的通信需求。通过对比仿真可以看出，本文提出的改进的动态TDMA时隙分配算法大幅度地提高在大量节点的MANET场景中的网络效率。

[1] 王宝康，陈强.一种改进的Ad hoc网络中动态TDMA时隙分配方法[J].网络天地,2011(14):50-52.

[2] FU W,AGRAWAL D P.Capacity of Hybrid Wireless Mesh Networks with Random APS[J].IEEE Transactions on Mobile Computing,2013,12(1):136-150.

[3] BAI F,SADAGOPAN N,KRISHNAMACHARI B,et al.Modelling PathDuration Distributions in MANETS and Their Import on Reactive Routing Protocols[J].IEEE J,on Selected Areas in Communications,2004,22(7):1357-1373.

[4] DJENOURI D,KHELLADI L,BADACHE N.A Survey of Security Issues in Mobile Ad Hoc and Sensor Networks[J].IEEE Communications Surveys & Tutorials,2005,7(4):2-28.

[5] 刘进军，傅振宇，李涛,等.分布式TDMA网络的时隙设计技术[J].移动通信,2013(22):58-61.

[6] 赵志峰，赵曦滨，陈丹宁.多维MANET可靠性建模研究[J].计算机科学,2011(5):60-63.

[7] CAMP T,BOLENG J.A Survey of Mobility Models for Ad Hoc Network Research[J].Wireless Communication & Mobile Computing(WCMC),Special Issue on Mobile Ad Hoc Networking:Research,Trends and Applications,2002,2(5):483-502.

[8] 王英杰，刘觅，吴振华,等.无线Mesh网络的最大并发公平调度[J].北京邮电大学学报,2007,30(4):33-36.

[9] 岳鹏，王柯，郑杰.一种基于优先级的TDMA时隙接入算法[J].无线互联科技,2016(4):87-89.

[10] 刘庆刚.基于动态优先级表的TDMA时隙分配[J].通信技术,2013(7):44-46.

[11] 张扬，曾晓峰.一种基于分簇和概率函数的电力线通信MAC协议[J].武汉大学学报(工学版),2015,48(2):216-219.

[12] 李卫.Ad Hoc网络中的混合类MAC协议研究[D].长沙:国防科学技术大学,2008:5-9.

[13] EPHREMIDES A,MOWAFI O A.Analysis of A Hybrid Access Scheme for Buffered Users-Probabilistic Time Division[J].IEEE Transactions on Software Engineering,1982,8(1):52-61.

[14] SHARP B A,GRINDROD E A,CAMM D A.Hybrid TDMA/CSMA Protocol for Self Managing Packet Radio Networks[J].IEEE International Conference on Universal Personal Communications,1995(10):929-933.

[15] CHLAMTAC I,FARAGO A,MYERS A.D.ADAPT:A Dynamically Self-adjusting Media Access Control Protocol for Ad-Hoc Networks[J].Global Telecommunications Conference,1999(1):11-15.

ResearchonImprovedDynamicTDMASlotAllocationAlgorithm

QIN Qian

(The54thResearchInstituteofCETC,ShijiazhuangHebei050081,China)

On the basis of static allocation algorithm based on TDMA,an improved dynamic TDMA slot allocation algorithm is proposed,which suits the scenario of multiple nodes moving stochastically.This algorithm can adjust slot scheduling strategy for nodes with different priorities according to the number of slots,so that high transmission efficiency can be achieved.The contrast simulation between the two algorithms is done in this paper,from which it can be concluded that the improved dynamic TDMA slot allocation algorithm is more suitable for the scenario that number of nodes keeps changing.

MANET;TDMA;slot allocation

10.3969/j.issn.1003-3106.2017.12.01

秦茜.一种改进的动态TDMA时隙分配算法研究[J].无线电工程,2017,47(12):1-4.[QIN Qian.Research on Improved Dynamic TDMA Slot Allocation Algorithm[J].Radio Engineering,2017,47(12):1-4.]

TN911

A

1003-3106(2017)12-0001-04

2017-02-16

国家科技重大专项基金资助项目(2015ZX03004002-004);国家自然科学基金面上项目(61671179)。

秦茜女，(1988—)，助理工程师。主要研究方向：无线通信。