0 概述

飞行自组网(Flying Ad-Hoc Networks，FANets)是一种由多个飞行器以自组织形式构成的无中心网络^[1]。在电力巡检、侦察打击与森林火警等小规模无人飞行器(Unmanned Aerial Vehicle，UAV)集群应用场景中^[2-3]，为满足飞行器间协同编队的飞行要求，FANets通过提供较低时延使得飞行器间能够实时了解彼此位置，以保持队形并避免碰撞^[4]。此外，为了能使操作人员了解现场情况并做出决策，FANets应具备较高的吞吐能力，且允许负责感知任务的飞行器回传数据量较大的感知数据。

介质访问控制(Medium Access Control，MAC)协议主要解决节点间高效使用信道传输数据的问题，对时延、网络吞吐量等性能指标有重要的影响^[5]。在网络负载较重的情况下，固定分配时分多址接入(Time Division Multiple Access，TDMA)协议在时延及吞吐量方面的性能均优于CSMA协议^[6-7]，更适用于有较多数据需要传输的FANets场景。文献[8]提出一种采用分布式时隙分配方案的TDMA协议，网络节点通过局部信息交换与协同完成时隙分配，不需要中心节点的参与，且在完成时隙分配后，节点可一直使用分配的固有时隙进行数据传输。文献[9]对文献[8]提出的时隙分配方法进行改进，并提出一种CF-MAC协议。该协议在发送时隙占用申请前先进行载波监听，降低多个节点在同一个时隙发送申请时发生冲突的几率。然而，当固定分配TDMA协议存在节点在已分配的时隙上没有数据需要传输时，将会造成时隙浪费，且该时隙被称为闲置时隙，而过多的闲置时隙将会导致信道利用率的降低。文献[10]根据节点ID计算每个节点使用非固有时隙的优先级，当一个时隙闲置时，优先级最高的节点可以使用该时隙发送数据，这样虽然允许其他节点使用未被使用的时隙，但仅简单地根据节点ID计算优先级而未考虑节点的实际传输需求，可能会出现优先级最高的节点也没有数据需要传输的情况，从而造成闲置时隙不能被合理使用。文献[11]提出的ESTDMA采用基于概率发送的时隙二次分配策略，当出现闲置时隙时，有数据传输需求的节点将以一定概率发送RTR帧与目的节点握手，则目的节点能够接收数据并应答CTR帧。ESTDMA是一种拓扑透明的TDMA协议，该协议在进行时隙分配时不考虑网络拓扑，且出现时隙分配冲突的几率较大^[12]。虽然二次分配策略可在时隙冲突情况下使节点以竞争方式尝试使用时隙，但无法保证节点一定能够成功传输，且与固定分配TDMA协议相比，其传输过程的可控性较差且不利于实现低时延传输。文献[13]设计的CTMAC在固定分配TDMA的基础上引入载波监听与随机退避机制，允许节点以竞争的方式使用闲置时隙。当一个时隙开始后，除了时隙所属节点外的其他所有数据传输节点将对信道进行监听，若监听期间信道一直保持空闲状态，则表明时隙所属节点并未使用该时隙进行数据传输，其他存在数据传输的节点将进行随机退避，并在退避结束后尝试使用该时隙进行数据传输。

文献[13]虽然可在一定程度上提高固定分配TDMA协议的信道利用率，但是随机退避机制将会增加时间开销，特别是当TDMA的帧长较短时，时间开销无法忽略不计，对网络的吞吐性能造成影响。此外，当参与竞争的节点数量较多时，信道的使用冲突几率将会增加，冲突的加剧将造成闲置时隙无法被成功使用。这些问题限制了以竞争方式使用闲置时隙的方法对信道利用率及网络吞吐性能的提升。为此，本文设计一种能够高效使用闲置时隙的TDMA协议——ISR-TDMA。该协议通过在帧结构中加入随机数字段，用预约协商的方式代替退避竞争，使节点可以无冲突地使用闲置时隙，从而降低闲置时隙使用的开销，有效提升信道利用率与网络吞吐性能。

1 问题描述与分析

闲置时隙的存在降低了固定分配TDMA协议的信道利用率及网络吞吐性能。通过引入载波监听与随机退避机制竞争使用闲置时隙，这在一定程度上提高了信道利用率，但当参与竞争的节点较多时，将面临与竞争类MAC协议类似的问题，即竞争的加剧使得闲置时隙无法被成功使用。此外，为了满足低传输时延的要求，TDMA协议需采用较短的帧长，此时竞争开销不可忽视，将会对网络的吞吐性能造成影响。

随机退避中的退避时间$ {T_{{\rm{BO}}}} $为[0, k]中的一个随机整数乘以退避单位(Backoff Unit，BU)。根据文献[14]可知，在n个节点参与竞争且每个节点在[0, k]中等概率选择随机整数的情况下，某一闲置时隙能被成功使用的概率P为：

$ P = n \times \sum\limits_{k = 0}^{K - 1} {\left( {\frac{1}{K} \times {{\left( {1 - \frac{{k + 1}}{K}} \right)}^{n - 1}}} \right)} $

(1)

式(1)说明当且仅有一个节点的随机整数取值为$ k $，而其余节点的随机整数取值均大于$ k $时，该闲置时隙才能被成功使用。

概率P的计算结果如图 1所示。从图 1可以看出：在$ K $不变的情况下，参与竞争的节点数$ n $越大，信道竞争越激烈，发生冲突的可能性变大，闲置时隙使用成功率变小；在$ n $不变的情况下，$ K $越大节点选择相同数值的可能性越小，发生冲突的几率越小，闲置时隙使用成功的概率则越大。

帧长对TDMA协议的平均时延有重要的影响，若实现数十毫秒甚至几毫秒级的平均时延，帧长也应取相似的长度^[15]。帧长取值较短时，竞争开销占比过大将会影响网络的吞吐性能。以IEEE 802.11的退避参数为参考依据^[16]，BU取值为20 μs，$ K $取值为32，则一个时隙中的竞争开销为0.62 ms。表 1给出了不同帧长及每帧时隙数下的竞争开销占比。由此可以看出，在帧长较短的情况下，竞争开销存在较大的占比。这说明竞争使用闲置时隙虽然在一定程度上增加了信道利用率，但降低了每个时隙实际能够发送的数据量，且网络吞吐量也会受到影响。

上述讨论基于以下假设：BU的长度大于或等于信号传播至节点最大通信距离处所需要的时间(最大传播时间)，但在BU小于最大传播时间的情况下，传输成功率未必会急剧下降^[17]。假设至少需要c个退避单位可使退避时间大于或等于最大传播时间，则式(1)可改写为：

$ P = n \times \sum\limits_{k = 0}^{K - 1} {\left( {\frac{1}{K} \times {{\left( {1 - \frac{{k + c}}{K}} \right)}^{n - 1}}} \right)} $

(2)

式(2)表明，若一个节点退避$ k $个单位，其余节点至少退避$ k+c $个单位，闲置时隙也可被成功使用，但此时竞争成功率会有所下降。由此可见，在帧长较短的情况下，可通过牺牲竞争成功率的方式降低竞争开销。

由上述分析可知，在采用短帧长的情况下，通过随机退避来竞争使用闲置时隙，以提高信道利用率和网络吞吐性能的做法存在局限性，即竞争成功率和竞争开销均对网络吞吐性能造成影响，这2个因素相互制约的关系限制了网络性能的改善。此外，随机退避并不能保证冲突不会发生，在发生冲突的情况下，闲置时隙不能成功传输数据，导致信道利用率的提升有限。因此，本文需要设计合理的闲置时隙使用机制，以较小的开销提高信道利用率及网络吞吐性能，更好地满足无人飞行器系统的要求。

2 协议设计

为提高闲置时隙的使用效率，减少额外开销，本文设计一种使用随机数预约的闲置时隙使用方案及相应的TDMA协议——ISR-TDMA。该协议以固定分配TDMA为基础，通过为每个节点固定分配时隙的方式，保证节点的基本通信能力，实现高优先级业务的低时延传输。节点在各自所分配的时隙中发送信息对闲置时隙的使用进行预约，并根据预约结果有序使用闲置时隙。与以竞争的方式使用闲置时隙相比，ISR-TDMA不存在闲置时隙使用冲突的情况，可以更充分地使用闲置时隙，且其还省去了随机退避的时间开销，增加了每个时隙可以传输的数据量，具有更高的吞吐量。

2.1 帧结构

图 2所示为ISR-TDMA协议的帧结构。一个ISR-TDMA帧由若干个时隙组成，为了避免由于传播时延不同而引起相邻时隙间的数据冲突，各时隙之间需要加上保护间隔。每个时隙由时隙信息(Slot Information，SI)和数据(Data)两个部分组成。SI主要用于节点间的协调以实现分布式时隙分配以及闲置时隙预约，Data用于数据传输。帧长是设计TDMA协议的一个重要参数，且对时延有重要影响。ISR-TDMA主要解决固定分配TDMA时隙浪费较为严重的问题，对于帧长并没有限制，可根据实际需要并结合文献[18]的相关理论对帧长进行设置。

SI的结构由源ID、目的ID、时隙状态表与随机数字段4个部分组成。其中：源ID与目的ID用于标识数据包的收发双方；时隙状态表中记录了节点单跳邻居对时隙的使用情况，用于分布式时隙分配，并确认其他节点的时隙申请；随机数字段则用于闲置时隙的预约。

2.2 时隙申请策略

ISR-TDMA采用与CF-MAC^[9]类似的时隙申请策略，使用分布式时隙分配算法为节点获取一个时隙。节点周期性的发送SI来交换各自单跳邻居的时隙使用情况，图 3给出了节点进行时隙申请的具体流程。新入网节点首先侦听信道一个帧长的时间，接收网内节点发送的时隙占用表，构建自身的初始时隙占用表。在侦听一帧信道后，根据邻居节点发送的时隙占用表以及自身的时隙占用表，新入网节点可以获知附近节点对时隙的使用情况，选择与其他节点不会发生冲突的时隙作为候选时隙。候选时隙首次到来时新入网节点将发送SI，若只有一个新入网节点发送SI，则网内节点可以成功收到新入网节点的SI并更新自身时隙占用表，且添加新入网节点的信息；若有多个新入网节点发送SI，则网内节点由于SI冲突无法成功接收SI，且不会更新时隙占用表。在发送SI后，新入网节点将等待一个帧长的时间，在此期间内如果接收到的网内节点发送的SI的时隙占用表中均有新入网节点信息，则表明时隙申请没有发生冲突，新入网节点成功申请到时隙；若网内节点的时隙占用表中没有新入网节点的信息，表明时隙申请存在冲突，新入网节点需要重新选择时隙并进行申请。将节点成功申请到的时隙称为节点的主时隙，同时称节点为该时隙的主节点。

2.3 闲置时隙感知

图 4给出了闲置时隙感知流程。由此可知，在每个时隙开始后，无论主节点有无数据包需要传输，都要在时隙开始后传输SI。若主节点有数据包需要传输，则在目的地址字段填上接收节点的ID，否则填0。其他节点在收到SI后，根据目的节点ID数值即可判断当前时隙是否会被主节点用于传输数据。若有数据要传输，则主节点在发送SI后紧接着发送数据包；若没有数据包要传输，当前时隙就是一个闲置时隙，其他有数据包传输的节点将根据预约结果使用该时隙进行数据传输。

2.4 闲置时隙预约与使用

图 5给出了闲置时隙的预约与使用流程。由此可知，当一帧开始后，每个节点接收到其他节点发送的SI，读取并保存随机数字段中的数值。主时隙到来时，如果节点的数据包队列有一个以上的数据包需要传输，则生成一个随机整数填入SI中的随机数字段发送，否则将‒1填入随机数字段发送。当前帧结束时，需要使用闲置时隙的节点对保存的随机数进行排序，并获得自身的排名。在下一帧开始后，节点将根据此排名顺序使用闲置时隙。闲置时隙的预约与使用并不是在同一帧内完成的，例如节点在第$ i $帧根据自身队列情况判断是否需要使用闲置时隙，若需要则对第$ i+1 $帧的闲置时隙进行预约。而第$ i+1 $帧节点将根据第$ i $帧的预约结果有序使用闲置时隙，同时又根据具体情况决定是否对第$ i+2 $帧的闲置时隙进行预约。随机数预约方式通过节点间的信息交互协商完成闲置时隙的使用权分配，与随机退避方式通过竞争使用闲置时隙的做法相比，其仅需在SI中添加一个随机数字段，无需预留时间进行随机退避，减少了相关开销，提升了每个时隙实际可传输的数据量，从而提升网络吞吐量。此外，随机退避方式在感知到闲置时隙后立即尝试竞争使用闲置时隙，存在因多个节点同时尝试使用闲置时隙而产生冲突的可能性。随机数预约方式在闲置时隙产生前，已经由节点确定对闲置时隙的使用顺序，不存在闲置时隙使用冲突的可能，可以更高效地使用闲置时隙，并提升信道利用率。

3 仿真分析

实验使用OMNeT++对ISR-TDMA协议性能进行仿真分析。仿真场景由1个地面站节点及19架无人飞行器节点组成。为了保证每个节点都能接收到其他所有节点的SI，避免随机数排序结果不同，本文仅考虑节点间均可相互通信的单跳场景。在节点移动模型的选择上，编队飞行模型在网络仿真软件中较难实现，且相关研究多数采用随机游走(Random Walk，RW)模型^[19-20]，因此，本文也选择采用随机游走模型。

网络中存在高优先级、低优先级两种业务，高优先级业务要求较低的时延，用于模拟协同及控制业务；而低优先级业务要求较高的吞吐量，用于模拟感知业务。无人飞行器分为高负载、低负载两类。高负载无人飞行器有高优先级、低优先级两类业务需要传输；低负载无人飞行器只有高优先级业务需要传输。地面站节点静止位于仿真场景最左侧的中部，仅有高优先级业务需要传输。

实验的主要仿真参数如表 2所示。高、低优先级业务产生的数据包个数均服从泊松分布。为保证对比的合理性，实验对CF-MAC、CTMAC与本文协议进行了适当修改，3种协议的帧长、时隙数、保护间隔均按照表 2给出的参数进行设定。此外，还为3种协议设计了优先级机制，当同时有高、低两种优先级的数据包需要发送时，优先发送高优先级数据包。

3.1 退避参数的选择

由前文可知，BU的长度未必要大于或等于信号最大传播时间。通过仿真来验证在参数合理的情况下，载波监听与随机退避机制也能为采用短帧结构的TDMA协议带来较高的吞吐量，同时也通过仿真寻找一个较为合适的参数，用于CTMAC协议与其他协议的对比实验。

图 6给出了高负载节点数分别为32和64时BU对网络吞吐量的影响，BU为0表示不采用载波监听与随机退避机制，仿真场景中信号的最大传播时间约为48 μs。可以看出，BU取较小值时，该机制对固定分配TDMA协议的吞吐量有一定提升。当BU较大时，竞争开销在整个时隙中的占比较大，单个时隙可传输的数据量变少，使得信道利用率的提升也无法引起吞吐量的增加，反而会降低吞吐量。当BU为1 μs、K取64时，吞吐量最高。后续仿真将使用该参数进行协议之间的对比分析。

3.2 协议仿真对比

仿真通过改变19架无人飞行器中高负载无人飞行器的数目，从信道利用率、网络吞吐量与平均时延3个方面对ISR-TDMA与CF-MAC^[9]、CTMAC^[11]进行对比分析。

3.2.1 信道利用率与网络吞吐量

图 7、图 8为3种协议的信道利用率和网络吞吐量的对比结果。从图 7、图 8可以看出，当高负载节点数较少时，ISR-TDMA、CTMAC可以使用闲置时隙传输数据，信道利用率均高于CF-MAC，并且因为这2个协议能使用更多的时隙传输数据，所以其吞吐量也高于CF-MAC。由于ISR-TDMA比CTMAC少了随机退避的开销，同时不存在竞争冲突，因此其信道利用率及网络吞吐量更高。随着高负载节点的增加，竞争的加剧使CTMAC协议的闲置时隙竞争成功率下降，其信道利用率逐渐接近CF-MAC，此时因为CTMAC存在随机退避开销，每个时隙可传输的数据量少于CF-MAC，所以其吞吐量反而要低于CF-MAC。当网络中多数节点均为高负载节点时，闲置时隙越来越少，3种协议的信道利用率逐渐接近。此时CF-MAC的额外开销最少，但其网络吞吐量最高。

3.2.2 平均时延

图 9、图 10分别为高、低优先级平均时延对比结果。由图 9可知，随着高负载节点数的变化，3种协议的高优先级业务平均时延的波动均较小，且均在6.5 ms左右，这是因为优先级机制保证了高优先级业务的优先传输，而仿真结果也说明固定分配TDMA协议通过采用短帧长的方式，在发包率适当的情况下可提供较低的平均时延。由图 10可知，当高负载节点较少时，CTMAC与ISR-TDMA可以使用闲置时隙传输数据，无需每个数据包都等到自身时隙到来时才能传输，它们的低优先级业务平均时延均优于CF-MAC，而由于SR-TDMA对闲置时隙的使用更充分，其低优先级业务平均时延低于CTMAC。在高负载节点较多的情况下，闲置时隙较少，每个节点基本都只能用自身时隙来传输数据，此时CF-MAC的吞吐量最高，而仅需花费较少的时间即可完成一个完整数据包的传输，其低优先级业务的平均时延低于其他2种协议。

4 结束语

本文设计一种基于闲置时隙预约机制的TDMA协议。该协议为每个节点固定分配一个时隙，以保证节点的基本通信能力，满足飞行器控制与协同业务的低时延传输需求，且允许高负载节点对下一帧出现的闲置时隙进行预约与使用。仿真结果表明，该协议可使协同与控制业务具有较低时延的同时，为感知业务提供较高信道利用率与网络吞吐量。下一步将采用自适应方法动态调整闲置时隙感知机制，以提高飞行自组网在重负载情况下的吞吐性能。