基于TDMA的空中自组网MAC层资源调度算法研究

张子东，宋志群，刘玉涛，段啸寒，于子婷

(中国电子科技集团公司 第54研究所，石家庄 050081)

0 引言

空中移动无线自组织网络是一个新的研究领域，其基本思路是在空中的节点通过多跳的方式，远距离传输控制信息及数据信息从而达到远距离通信的目的[1]。在一定范围内的航空飞行器之间相互转发控制指令信息，交换各自的飞行状态、感知信息等数据，并自动连接，以建立一个移动自组网(MANET[2]，mobile ad hoc network)。空中组网具有组网灵活扩展且无需网络基础设施等优势，在航空通信中有着广阔的发展前景。其具备的自组织、自恢复、高动态、低时延等特点可以满足高空无线通信的特定需求，是高空通信的重要发展方向，也是现代无线通信的重要组成部分[3]。

近些年针对空中自组网的媒体接入控制(MAC，media access control)协议研究较少，其中文献[4]是无中心节点的分布式时分多址(TDMA，time division multiple access)协议，各个节点使用分配的时隙进行数据传输。文献[5]的无冲突MAC协议(CF-MAC，collision free media access control)通过载波监听控制时隙的分配。文献[6]通过规定不同节点有不同优先级占用时隙，但是没有考虑不同时隙的不同业务需求。文献[7]提出的自组织时分多址接入协议(ESTDMA，evolutionary self-organized time division multiple access)可以通过对闲置时隙的二次预约合理的分配时隙。但是二次分配也会导致传输失败增多使网络时延难以控制。文献[8]设计的并发传输MAC协议(CTMAC，concurrent transmission media access control)通过载波监听与随机退避机制。虽然可以提高TDMA协议的信道利用率，但是随之而来的便是吞吐量的降低以及时延的增大。优先级竞争时分多址(P-TDMA，priority-based time division multiple access)协议[9]本质上是动态时隙分配算法，但是却融合了静态时隙分配的特点，构造了一种特殊的帧结构，避免了多节点的冲突碰撞问题。P-TDMA 协议的缺点是没有到考虑不同节点业务量不同。且混合分配模式在不同业务量下网络性能不稳定。

TDMA[10]协议的基本思想是将时间分割为帧的形式，每一帧将不同的信息储存在不同的时隙之中，每个用户通过算法被分配不同的时隙[11]。在不同时隙发送数据就表示发送的时间是何时，即数据传输的等待时延。传输时延主要受时隙分配结果、无线传输时延、处理时延以及总帧长大小等因素的影响[12]。目前常见的TDMA时隙分配方法主要包含两种：静态分配法与动态分配法。静态分配法是给每个节点分配一定数量的时隙来保证数据发送与接收的及时性，拥有稳定的时延；动态分配法则是根据不同节点的需求不同，动态调整时隙的分配数量，提高时隙的利用率，以此来适应更大规模的网络。本文采用的混合分配法综合了静态分配与动态分配两种分配方式的优点具有更高的网络效率。

针对高空高动态远距离通信的场景，现有多跳TDMA协议存在的时延过大、吞吐量不足等问题。本文结合定向天线的通信特点，参考P-TDMA协议算法设计了一种基于TDMA的定向分布式资源调度算法(M-TDMA，mix time division multiple access)。本文设计的M-TDMA算法有如下改进创新：1)设计了一种基于拓扑的邻居节点分配算法，根据动态变化的节点拓扑信息，寻找各个节点的邻居节点，按照点号依次为每个在网节点分配时隙。由于定向自组网是根据时隙对来通信，在网节点固定分并不适用，因此采用邻居节点固定分策略。并通过静态分配与动态分配相结合的混合模式，提升了网络吞吐量；2)静态分配策略：为各个节点设置时延保障静态时隙以应对突发的业务需求，引入分配系数，分配系数随节点空闲时隙的数量变化进行动态调整，以此来均衡静态与动态分配的的时隙数量有效降低了传输时延；3)动态分配策略：在业务优先级的基础上设计节点流量预测算法，MAC层识别业务信息量不同，首先根据流量预测算法，通过历史周期的邻居节点业务量大小，预测本周期业务量大小，从而给不同业务需求的节点分配不同数量的时隙。随后动态分配时隙数量，当预测到节点有大量业务需求时，优先将空闲时隙分给预测业务量大的节点传输业务，剩余时隙分配给其它低业务量节点。节点分配的时隙数量随着调度周期进行动态变化，最后根据业务优先级算法，为各优先级的业务分配不同数量的时隙。

1 自组网MAC协议

1.1 MAC协议原理

MAC层协议作为无线通信的基础，在无线网络通信中起着至关重要的作用，通过分配各个节点无线信道资源，在提升传输效率的基础上保障公平性。对传输时延、网络吞吐量等网络性能指标起着关键性作用[13]。随着现代无线自组织网络规模越来越大，服务质量 (QoS，quality of service)指标的保证显得愈发关键，如何更好地进行资源调度是MAC协议研究的热点之一[14-22]。

通常MAC协议多采用集中式的调度方式，通过交互整个网络拓扑的节点信息，根据节点优先级不同分配不同的时隙，并使用中心节点广播分配时隙。但由于高空环境下通信距离远，网络拓扑动态变化快，又有高带宽的传输需求，需要采用定向天线。而定向天线同一时刻需要点对点收发波束朝向一致才可以通信，集中式协议不适用。因此只能使用无中心节点的分布式时隙分配方法[23]。这种方法不需要中心节点的参与，只通过部分节点的信息交互就可以完成网络时隙的合理分配。

1.2 帧结构设计

本文M-TDMA算法有3种帧类型，分别为邻居发现帧、预约帧和数据帧。分别对应邻居发现、预约、数据传输3个阶段。邻居发现帧用于实现节点之间的波束对准及网络同步，预约帧用于实现节点间的分布式业务预约，数据帧用于业务传输。算法的时隙结构如图1所示。其中SYN为邻居发现帧，DATA为数据帧，R1、R2为预约帧。每个调度周期有4个邻居发现帧可以进行4次邻居发现。一个周期内各种帧的帧长与数量如表1所示。一个调度周期总共1 s。调度周期包含的各帧信息如下：

图1 M-TDMA算法时隙结构

表1 帧长设计

1)邻居发现帧的长度。4个邻居发现帧帧长为10 ms。

2)预约帧的长度。R1与R2长度相同，本文设计为1.5 ms。

3)数据帧的长度。由于数据时隙数量较多，每个数据帧长度不能超过10 ms否则将会无空余时隙设置预约帧，本文数据帧长为5 ms。

预约帧结构如图2所示，当节点入网后，MAC层有数据需要传输，此时节点通过预约帧发送请求信息，其携带的信息有数据大小、优先级节点ID、邻居节点信息等。接收节点收到其他节点发送的预约帧后，将预约帧内容汇总储存并在预约确认帧中发出反馈。预约确认帧结构与预约帧相同，二者使得全网邻居信息互通。本文每个预约帧长度均为1.5 ms，由预约时隙R1、预约确认时隙R2和保护间隔组成。R1时隙和R2时隙长度相同。每个预约帧中的发送节点对互相绑定，两个节点互为目的节点。保护间隔长度约占预约帧总长度的10%，用以确保节点收到R1后能够有充足时间解调并计算时隙资源，最终将结果附在R2中发出。

图2 预约帧结构

数据阶段，节点间按照上个预约阶段的预约结果进行数据传输。在一个数据时隙进行信息交互的两个节点分别为发送数据节点和接收数据节点，二者已经在之前的预约阶段互相确定。在数据传输过程通信双方的收发天线按照邻居发现的结果相互对准。为保证协议层数据的正确接收，数据帧应预留一定的长度间隔作为保护间隔，用于补偿远距离数据的传输时延。剩余的时隙根据物理层帧结构进行灵活改动，设计为一个或多个时隙，并根据需求发送至一个或多个目的节点。

2 资源调度算法

2.1 MAC协议资源调度算法

资源调度算法包括时隙预约、业务量统计、时隙排布三部分，业务量统计用于确定本次调度分配的时隙数量，随后根据业务量统计的结果进行预约，预约过程使用时隙排布策略以确保时隙的均匀分配。

资源调度算法流程为：首先进行节点初始化，随后的时隙请求阶段，节点根据缓存的时隙需求，在对应时隙发送请求并接受其他节点的请求信息。在响应阶段，节点依据之前阶段的节点信息，与自身时隙状态整合汇总，通过本文的资源调度算法分配时隙。最后进入数据发送阶段，各个节点根据资源调度算法分配的时隙发送数据。本文具体算法基本流程如图3所示。

图3 MAC协议算法流程

2.2 业务量统计策略

图4 流量预测示意图

(1)

(2)

节点根据邻居节点的预测流量大小，对可分配时隙按比例进行划分，历史业务量大的节点会分配更多的时隙，业务量小的节点会分配相对较少的时隙。此时由于分配比例系数与分配时隙总数无法整除可能会产生一定的时隙余量，将剩余时隙统一分配给预测业务量最大的节点。由于网络拓扑的动态变化，当有新节点入网时，会分配一定比例的时隙。由于节点时隙分配比例是周期变化的，对于每个节点来说，时隙的分配是公平的。最后给不同优先级的业务划分不同的时隙数目xi，业务优先级越高分配时隙越多业务发送越快信道等待时延越低。业务量统计策略流程如图5所示。

图5 业务量统计流程

2.3 时隙预约策略

两个节点之间的时隙分配通过预约时隙对，即预约时隙R1和预约时隙R2实现，如下为数据时隙分配过程，节点A和节点B互为邻居业务传输节点。节点A为R1发送节点，节点B为R2发送节点。

2.3.1 节点A时隙预约步骤

步骤1：节点A在进入自己的预约时隙后发送预约帧R1。节点A查看自己的缓存中是否有数据等待发送至节点B，如果需要预约数据时隙，则计算需要的时隙数，在预约帧R1中填充需要的时隙和本节点在数据阶段的空闲时隙表。发送预约帧R1后，转至步骤2。

步骤2：节点A持续收听信道，如果能够正确接收预约确认帧R2，则说明在预约时隙节点A与节点B成功的进行了信息交互。节点A读取预约确认帧R2中节点B回复的成功分配的时隙和数据时隙编号，在下一个数据阶段，节点A将在数据时隙向节点B发送数据。同时节点A查看节点B是否有时隙需求。如果节点B有数据时隙需求，则读取节点B的数据时隙需求和数据时隙号。在下一个数据阶段，节点B将在这些数据时隙向节点A发送数据，在这些时隙节点A将切换为对节点B的接收状态。

2.3.2 节点B时隙预约步骤

步骤1：在进入预约时隙后持续收听信道。若接收到节点A发送的R1，则查看节点A是否申请分配数据时隙，若申请数据时隙，则查看需求的时隙数量，节点B根据自己的空闲时隙情况，安排尽可能符合需求的时隙。若节点A发送的R1帧中没有申请分配数据时隙，则节点B根据自己缓存中待发数据的情况判断是否需要申请数据时隙以及计算需要申请的数据时隙的数目，然后读取预约帧R1中节点A的空闲时隙情况，同时根据自身的空闲时隙情况安排尽可能符合需求的时隙。

步骤2：进入步骤2，节点B发送预约帧R2，告知节点A成功分配的数据时隙数目和数据时隙编号。时隙预约示意图如图6所示。

图6 时隙预约示意图

2.4 时隙排布策略

当确定要分配的时隙数后，将确定分配的时隙排布到互相预约的两个节点的空闲时隙交集中。时隙排布需要考虑的因素是时延抖动。抖动越大，说明通信网络越不稳定。为了降低时延抖动，需实现均匀间隔的时隙分配。本文采用贪心算法(又称贪婪算法)：在对问题求解时，总是做出在当前看来的最好选择。即不从整体最优上加以考虑，所做出的仅是某种意义上的局部最优解。贪心算法不是对所有问题都能得到最优解，但针对许多问题，能产生整体最优解或者是整体最优解的近似解。分配时隙时采用贪心策略，只需考虑下个时隙与上个已分时隙的时隙间隔，而无需考虑整个时隙表的排布。

为保证传输时延，为每个节点分配的时隙与下个时隙的间隔不能过长。为减小时延抖动，相邻两个时隙的间隔数相对固定。由于时隙表的开始部分存在邻居发现帧，邻居发现帧会带来时延，剩余部分只存在预约帧，而预约帧有释放的可能，所以两种情况应分别考虑。算法时隙排布流程如图7(a)所示，其中LAST_NUM为上一次分配的时隙号。S为第一个空闲时隙号T为时隙分配步进即每间隔T个时隙分一个时隙，N为所需分配时隙数。例如T=7时，隔7个数据时隙排布一个时隙。MAXNUM为时隙表数据时隙总数，若业务需求时隙数较少，则使时隙平均分配在总时隙表中。例如只需4个时隙时，时隙分配步进为：

图7 时隙排布策略流程及结果

(MAXNUM/4)-1

(3)

按照上述策略，节点分配时隙的结果如图7(b)所示，其中灰色时隙为依据时隙排布策略所分配的时隙。

3 仿真与分析

3.1 仿真原理及参数

使用软件Visual Studio进行仿真代码实现，使用Matlab对仿真数据进行处理与分析。通过对算法的时延、吞吐量等性能指标进行优化并与STDMA、P-TDMA等典型协议进行性能对比，由此对M-TDMA算法性能进行验证。主要仿真参数如表2所示。

表2 仿真参数设置

两跳传输时延仿真首先输入业务的发送节点和接收节点。根据时隙分配算法，计算出各节点的时隙表。通过产生一个随机数作为起始时隙，从起始时隙的下一个时隙开始搜寻时隙表，如果时隙表中该时隙的发送节点和业务发送节点相同，该时隙的接收节点与业务接收节点相同，则说明数据会在该时隙发出。如果该时隙不是数据发送时隙，则继续寻找。从起始时隙向后寻找发送时隙的过程即传输时延增加的过程，每过一个时隙，则传输时延增加一个时隙的时长。找到发送时隙后，则返回总时长即为传输时延。

多跳传输时延的计算为两跳传输时延的多次调用。多跳传输时延的输入为业务路径。产生随机数作为起始时隙，首先计算第1跳的传输时延，得出结果后，将第1跳传输时延的发时隙作为第2跳传输时延计算的起始时隙，继续进行第2跳传输时延的计算。整条业务路径的传输时延依次叠加，得出总的传输时延。

在数据传输过程中由于在空中组网节点的网络拓扑结构变化较快，为保证QoS，通常MAC层仿真的多跳时延通常不能大于1 s，否则将会导致接收端丢包。仿真在统计接收数据包数量占总发送数据包的百分比即为丢包率。每一帧的最大数据载荷是固定的，节点之间有效数据的传输是通过数据时隙完成，通过计算在链路数据传输中使用的数据时隙总数即可计算出仿真数据传输过程的吞吐量大小。

3.2 仿真结果与分析

为了评估M-TDMA算法的性能，分别从分配系数、网络节点个数、数据发送速率等方面进行仿真分析。其中分配系数是对M-TDMA算法进行优化；不同网络节点个数与发送速率是用于对比M-TDMA与STDMA和P-TDMA三种算法的性能差异。通过网络平均传输时延、网络吞吐量、网络丢包率等性能指标对算法进行优化与分析。为了更好地验证M-TDMA 算法性能，本文进行100次调度周期仿真并取平均值进行结果分析。

3.2.1 不同拓扑场景与分配系数优化

在节点高动态场景下，网络的拓扑形式多样化，图8为3种典型的网络拓扑状态，通过分别对比在3种不同拓扑下一跳至十跳的时延大小来验证M-TDMA算法的网络拓扑环境适用性。

图8 3种不同网络拓扑图

根据图9(a)结果可知：链状拓扑由于结构简单且邻居节点数相对固定，因此时延最小，且当跳数增大时，时延上升最平稳；而网状与星状拓扑由于不同节点的邻居节点数差异较大，因此时延的变化较为抖动，但是单跳的平均时延仍在60 ms以内，符合单跳传输指标。综上所述本文的M-TDMA算法在不同的拓扑状态下网络传输性能良好。

图9 不同分配系数下网络时延对比图

分配系数RATTO的作用是：当节点的可用空闲时隙较少时，通过RATTO使节点分配的静态时隙减少、动态时隙增多，使得传输时延相对稳定。分配系数的优化是通过在星状网络拓扑下遍历分配系数，对比不同分配系数4跳传输路径的时延大小。RATTO越小代表在节点可用时隙较少时分配的静态时隙越少，W为参考静态时隙阈值，用来设定静态时隙数，在可用时隙足够时，通常为总时隙的10%即可满足静态时隙需求。NUM为节点最大可分配时隙数。最终分配静态时隙X为：

(4)

图9为分配系数RATTO不同时，节点间不同链路网络传输时延最大值、最小值以及平均值的变化对比图，RATTO取值为15%、20%、25%、30%、50%五种不同的策略。不同链路路径见表3所示。

表3 链路路径设置

按照策略5即将当前空闲时隙的一半进行静态分配，会导致先分配的节点静态时隙过多而后分配节点出现“饿死”的现象使得时延增大。按照策略1与策略2进行分配时，由于分配系数过小，分配的静态时隙过少，导致无法及时发送突发业务导致时延增大。策略3与策略4的效果较好，通过对比可知由于策略3的分配系数较小，静态时隙较少，应对突发业务能力不足，从而导致出现节点传输最大时延与最小时延的差值较大，即产生了时延抖动现象。策略4由于静态时隙相对充足，没有时延抖动现象，仿真效果最优。因此本文后续均采用策略4进行仿真。

3.2.2 不同网络节点数

在自组网的网络性能测试中，节点的数量是衡量MAC协议的负载能力的重要指标，对网络的性能起着关键的影响。本文针对不同的网络节点数，观测对比网络节点数为2，4，6，8，10，12，14，16，18，20时M-TDMA与STDMA、P-TDMA协议的性能差异。

图10为3种协议在不同节点数时网络传输时延对比，当节点增加时，网络的传输时延逐渐增大，这是因为在多节点的拓扑环境下节点的邻居节点增多，缓存数据增大使得传输时延提升。而STDMA由于是全向天线协议，当节点数量增多时可用时隙减少，当节点数达到14节点后产生明显的时延增大。P-TDMA算法由于其没有考虑节点的不同业务量大小，当节点增多时可用时隙减少时延增大加快，而M-TDMA协议独特的节点流量预测算法，可以有效减少高业务量需求的时延，传输时延最低。

图10 不同协议网络时延对比图

图11为3种不同协议的网络吞吐量随节点数增多的变化图。在节点数较少时，传输链路随着节点数增多而增多，3种协议的吞吐量都随着节点数的提升而提升。STDMA协议由于是全向天线协议，在8节点以上时，时隙数量减少，链路冲突几率增大导致吞吐量开始下降，而由于P-TDMA与M-TDMA协议是定向天线协议，通过空间复用实现同一个时隙多个链路同时发送数据，使得网络吞吐量可以随着节点的变多而增大。当网络节点数增大到16个以上时，时隙资源使用充分，节点间可用链路减少，各个协议的吞吐量均开始下降。并且M-TDMA由于使用混合分配模式，既有基于分配系数的静态时隙又可使用预约帧为节点获取更多的时隙资源发送数据，因此网络吞吐性能最好。

图11 不同协议网络吞吐量对比图

图12为3种协议丢包率随节点个数变化的情况。随着节点数量增多，网络拓扑复杂度逐渐增大，由于网络节点高速动态变化，网络的传输路径难以稳定，网络的拥塞度提升，传输时延增大，导致丢包现象产生。随着节点的不断增多，丢包率也逐步提升。P-TDMA协议由于竞争分配机制，当节点数增大时，冲突概率增加使得出现网络堵塞，丢包率增大。而STDMA协议由于是全向天线协议没有空间复用，节点数增大时在一个调度周期内每个节点可用的数据时隙快速下降导致丢包率迅速上升。M-TDMA协议是定向协议，空间复用率高且使用混合资源分配模式，随着节点增多，由于分配系数的引入，协议的静态分配时隙随之减少可用时隙不会快速下降，有效改善了网络拥堵现象，丢包率相对较小。

图12 网络丢包率对比图

3.2.3 不同的数据发送速率

本文通过改变节点的数据发送速率来观察MAC协议在不同网络负载下的性能，依据前文仿真数据将节点数目设置为14，在星状拓扑下进行仿真。发送速率为100～1 000 kbps。

图13为3种MAC协议在数据发送速率增大时平均时延的变化图。数据发送速度在400 kbps以下时，各协议的传输时延为500 ms以内。P-TDMA协议由于未考虑不同节点的业务量大小不同，当传输速率在400 kbps以上时，大业务量节点的可用时隙减少，传输时延快速提升直至2.5 s左右。而STDMA协议的时延随着发送速率的提升增大，在700 kbps以上时出现网络拥塞，由于大量数据丢包，时延逐渐稳定。而M-TDMA协议由于考虑了不同节点的业务量不同，按照流量预测结果合理分配时隙并且通过分配系数的引入动态调整了可分配的动态时隙数量。使得网络平均时延相对较低。

图13 网络时延对比图

数据发送速率在100～1 000 kbps时3种协议的网络吞吐量变化情况如图14所示。随着数据发送速率的提升，所有协议的吞吐量均增大。STDMA协议的吞吐量小于数据发送速率，而定向MAC协议的吞吐量远大于数据发送速率。这是由于定向天线使得信道同时可以发送多条链路的数据，空间复用率增加，网络吞吐量不断提升。而相比于P-TDMA协议，本文设计的M-TDMA协议在数据发送速率达到1 000 kbps时，网络吞吐量可以达到4 Mbps以上。这是因为在网络负载增大时，节点通过流量预测算法动态调整不同节点分配的时隙数量，预测网络流量大的节点优先分配更多的时隙资源，吞吐量得以继续提升。而STDMA与P-TDMA协议在发送速率达到700 kbps后由于没有有效的资源动态调整策略，吞吐量不再提升，达到满负载状态。

图14 网络吞吐量对比图

图15对比了当数据发送速率提升时3种协议的丢包率变化情况。当数据发送速率增大时，3种协议的丢包率也不断增大，这是因为随着数据发送速率的增大网络负载变大，数据缓存区的等待数据增多，丢包率也随之增大。在100～300 kbps的发送速率时，3种协议丢包率控制在5%以内。当发送速率达到700 kbps时，P-TDMA协议由于没有分配系数均衡静态与动态时隙，导致可用时隙减少丢包率增大。而STDMA协议是全向天线MAC协议，过大的负载使得节点可用时隙减少，由于过长的排队时间，导致数据大量丢失丢包率增大。而M-TDMA算法由于分配系数存在，可用时隙减少时静态时隙会转化为动态时隙，可用时隙充足。且该算法根据预测各节点业务量大小，动态调整各节点分配的时隙数，排队时间缩短，数据丢包率降低，在1 000 kbps的速率时丢包率仍控制在20%以内，算法性能最好。

图15 网络丢包率对比图

4 结束语

近些年来随着无线自组网研究与应用的不断深入，MAC协议作为自组网关键的组成部分具有很重要的研究意义。本文在研究过程中针对高空中拓扑高动态变化的分布式定向自组网的特点，提出了一种基于TDMA的定向分布式资源调度算法M-TDMA，通过引入分配系数，有效均衡了动态与静态分配的效果；并通过流量预测算法对时隙进行合理的分配，有效改善了网络拥堵现象。仿真对比表明M-TDMA算法很好的应用于多节点高动态场景，有效减少了网络平均时延，并提升了网络吞吐量，提升了网络效率。