适用于飞行自组网的闲置时隙预约TDMA 协议

陆 毅，符杰林，仇洪冰，林基明，李燕龙，3

（1.桂林电子科技大学认知无线电与信息处理教育部重点实验室，广西桂林 541004；2.桂林电子科技大学卫星导航与位置感知重点实验室，广西桂林 541004；3.桂林电子科技大学电子电路国家级实验教学示范中心，广西桂林 541004）

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 协议需采用较短的帧长，此时竞争开销不可忽视，将会对网络的吞吐性能造成影响。

随机退避中的退避时间TBO为[0，K)中的一个随机整数乘以退避单位（Backoff Unit，BU）。根据文献［14］可知，在n个节点参与竞争且每个节点在[0，K)中等概率选择随机整数的情况下，某一闲置时隙能被成功使用的概率P为：

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

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

图1 在不同n 与K 下的竞争成功率计算结果Fig.1 Calculation results of competition success rate under different n and K

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

表1 在不同帧长与每帧时隙下的竞争开销占比Table 1 The proportion of contention overhead under different frame lengths and different time slots per-frame

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

式（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］的相关理论对帧长进行设置。

图2 ISR-TDMA 协议的帧结构Fig.2 Frame structure of ISR-TDMA protocol

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

2.2 时隙申请策略

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

图3 节点的时隙申请流程Fig.3 Time slot application procedure of the node

2.3 闲置时隙感知

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

图4 闲置时隙感知流程Fig.4 Procedure of idle time slot sensing

2.4 闲置时隙预约与使用

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

图5 闲置时隙预约与使用流程Fig.5 Procedure of reservation and use of idle time slot

3 仿真分析

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

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

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

表2 仿真参数设置Table 2 Simulation parametes setting

3.1 退避参数的选择

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

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

图6 退避参数对吞吐量的影响Fig.6 Impact of backoff parameters on throughput

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 的额外开销最少，但其网络吞吐量最高。

图7 3 种协议的信道利用率对比Fig.7 Comparison of channel utilization of three protocols

图8 3 种协议的网络吞吐量对比Fig.8 Network throughput comparison of three protocols

3.2.2 平均时延

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

图9 3 种协议的高优先级业务平均时延对比Fig.9 Comparison of average delay of high priority services of three protocols

图10 3 种协议的低优先级业务平均时延对比Fig.10 Comparison of average delay of low priority services of three protocols

4 结束语

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