面向无人机网络的媒体接入控制协议

杨茂保，徐利亚，葛明珠，陈 希，舒长兴

(1.九江学院电子商务学院，江西 九江 332005；2.九江学院信息科学与技术学院，江西 九江 332005；3.九江学院信息技术中心，江西 九江 332005；4.软件工程国家重点实验室，武汉大学计算机学院，湖北 武汉 430072)

0 引言

无人机是一种可以自主飞行不需人为操作的飞行器，在军用和民用领域有广泛用途，如森林火灾监测[1]，灾害救援[2]，无线网络中继[3]， 增加网络容量[4]等。尽管单无人机系统已经使用了很多年，但是多无人机系统与单无人机系统相比有很多优势。而多无人机系统面临的一个重要挑战就是它们之间的通信[5-7]，包括无人机之间的通信，以及无人机与基站之间的通信。在某些场景中，通信链路可能长达几百公里，这样的远距离通信链路可能会导致：1)低服务质量，信号质量和通信距离成反比，远距离链路将导致更高的丢包率。2)信道利用率低，远距离引起较大的信号传播延迟，对于高速网络来说这种延迟不能被忽略。传统网络协议设计时，单信道通常只允许单个信号进行传输，这种方式在传播延迟较大时将引起很大的浪费。

针对近距离无线网络设计的MAC协议，如802.11系列，不能被直接应用于这种远距离链路场景中。载波侦听/冲突避免(CSMA/CA)通过侦听信道是否空闲来决定数据发送与否，这种方式在远距离链路中需要花费较大的时间开销，且容易出现隐藏终端等问题。文献[8—9]通过修改802.11无线网卡，将之用到远距离网络中，但实验证明这并不是一个理想的选择[10]。与竞争型协议相比，预约型MAC协议通常通过集中调度以一定的代价可以提供相对较好的网络服务质量，如Jang等[11]提出了一种基于TDMA的可靠航空通信的协议LBTM，Temel等[12]提出一种根据地理位置来动态分配时隙的方法，Araghizadeh等[13]根据距离远近为传感器节点设计了一种公平的接入方案。另外，现在更多的研究侧重于混合式协议或者跨层协议设计，以此获得更好的网络性能。Cai等[14]利用全双工以及多包接收技术，设计了一种针对无人机自组织网络的MAC协议，而Alshbatat等[15]则混合利用全向天线和定向天线，提出了一种无人机网络的自适应MAC协议。但这些协议都没有考虑传播延迟对网络的影响，设计的MAC协议也基本忽略传播延迟。

针对上述问题，需要一个更合适的MAC协议来改善具有远距离链路的无人机网络的通信问题，本文主要侧重于传播延迟不可忽略的无线MAC协议设计与优化。

1 系统模型

1.1 网络模型

本文考虑的场景包括一个基站以及若干无人机组成的无线网络。无人机随机均匀分布，且都接入全球导航卫星系统(GNSS)。GNSS可以提供时钟同步以及地理位置信息服务。无人机搜集数据后传输给基站，基站负责接入调度。假设在某一时刻，无人机个数为M，mi表示编号为i的无人机。基站和无人机的最大通信范围都为Dmax，当无人机和基站的距离小于Dmax时，无人机可以请求接入并进行通信。另外，无人机和基站之间进行视距通信，并且通信信道为理想信道，即不存在因为信道状况而导致的丢包问题。

1.2 数据流模型

本节介绍无人机数据流产生模型。上层应用产生数据包后排队进入一个数据缓存区供数据链路层调度，假设缓存区容量为Cbuf，即缓存区最多可以保存Cbuf个数据包。当缓存区满时，再产生的数据包将被丢弃。

2 MAC协议

2.1 MAC协议框架

本文采用动态时分复用的方法设计MAC协议。如图1所示，时间被划分为帧，每一帧包含若干时隙，我们定义一个时隙为最小的通信时间单位。假设在一个时隙内，可以成功发送或者接收一个数据包。

每一帧包括两部分：控制域和数据传输域。在控制域，无人机如果有数据要发送，则发送请求包，向基站申请时隙资源。在基站收到所有请求包后，发送一个广播信息包，用于确认以及指示数据区域的时隙分配情况。在数据传输域，无人机按照基站的分配信息在所在的时隙发送数据包。

图1 MAC帧结构Fig.1 Frame Structure

假设每一帧的长度为Lf，每一帧包含N个时隙，那么每个时隙的长度Ls就是Lf/N。控制区域和数据区域的时隙数分别是Nc和Nd。当mi有数据要发送时，向基站申请nreq,i个时隙，nreq,i是当前数据缓存区中的数据包个数。

借助GNSS，mi可以获取当前的地理位置坐标，那么其与基站之间的距离di也可以计算出来，相应地，信号传播延迟ti也可以根据距离di和无线电传播速度c计算出来。

2.2 网络初始化

基站在控制域周期性地广播接入信息，当一架无人机进入基站的通信范围并收到基站的接入信息时，向基站发送一个接入请求，包含认证信息。一旦收到来自无人机的接入请求，基站会在下一个控制区域回复一个ACK包。无人机成功接受ACK包后，接入过程完成。接入过程至少需要N+Nc个时隙，而发送数据则至少在两帧之后。

2.3 时间重用机制

远距离链路较大的传播延迟使得时间重用成为可能，可使多个信号在同一竞争域内并发进行传输。图2描述了时间重用的基本思想。有两个节点，nodei和nodej同时向基站BaseStation发送数据。由于两节点与基站的距离不一样，两个同一时间点发送的数据包到达基站的时间也就不一样，这样基站可无冲突地接收到两个数据包。而传统MAC协议设计时通常假设是同一竞争域内只有一个数据包可以传输，这就意味着可以通过这种方式提高网络吞吐量。

图2 时间重用Fig.2 Temporal Reuse

3 时隙分配方法

无人机在传输数据之前会收到来自基站的分配信息包，分配信息包指定了特定的无人机在特定时隙传输数据。为了避免信号冲突以及最大化网络吞吐量，有必要研究基站的时隙分配策略。

由于每一帧被划分为若干时隙，并且每一个时隙只可以发送或接收一个数据包，我们定义一个M×N维的分配矩阵A，A指定了一帧内的时隙如何分配给竞争节点。如果mi在第j个时隙内可以传输一个数据包，那么矩阵A中的元素ai,j等于1，否则ai,j等于0。

通过矩阵A和P，便可以计算出各个数据包到达基站的时间，同样可以用一个M×N的0-1矩阵来表示，假设该矩阵为B。如果B中的元素bi,j等于1，则表示在第j个时隙收到了来自mi的数据包；反之bi,j等于0，则第j个时隙没有收到来自mi的数据包。

3.1 无冲突

3.2 吞吐量

3.3 吞吐量最大化

本文的目标是无信号冲突条件下最大化系统吞吐量，可以形式化如下：

(1)

式中，i∈{1,2,…,Mk}，k∈{1,2,…,K}，j∈{1,2,…,N}，τ是任意一帧的索引。

约束条件(2)限定在接收端一个时隙内最多只有一个数据包到达，以此来满足无冲突的要求。约束条件(3)限定分配给mi的时隙不超过它申请的时隙个数。约束条件(4)和(5)限制了ai,j,k的值，如果ai,j,k等于1，那么mi可以在第k帧的第j个时隙内发送一个数据包，反之如果ai,j,k等于0则不能。其中(5)限定mi在一帧的最后pi个时隙不能发送数据，因为在这段时间内发送的数据包将在下一帧内到达基站，可能会产生信号冲突。约束条件(6)和(7)表明了bi,j,k的取值范围，可以从约束条件(4)和(5)中推导出来。

3.4 时隙分配算法

任意K个时间帧内的吞吐量最大化问题是一个典型的在线算法问题，往往得不到最优解，所以本节中将问题简化为计算一帧内可接收到的最大数据量，并提出相应的时隙分配算法。

3.4.1 理论分析

首先把问题重新形式化为如下形式：

(8)

式中，ai,j和bi,j是矩阵A和B中的元素，M是申请时隙的无人机个数，N是数据域内的时隙数。

给定pi，根据(12)和(13)，假设ai,*=(ai,1,…,ai,N-pi,0,…,0)，bi,*=(0,…,0,bi,pi+1,…,bi,N)。由(14)，可以得到ai,*=(bi,pi+1,…,bi,N,0,…,0)以及bi,*=(0,…,0,ai,1,…,ai,N-pi)，那么目标函数(8)可以转换为

(15)

从式(15)中很容易地可以发现在无冲突情况下发送的数据包数量等于接收到的数据包数量。那么可以把问题转化为：

(16)

(21)

3.4.2 时隙分配算法

当Bj=1,i>Mp时，吞吐量达到最大，也就是在第(Mp+1)到第N个时隙基站都能接收到数据包。由此提出一个时隙分配算法实现时隙分配，同时该算法能保证分配的公平性。

算法1 时隙分配算法输入:信号传播延迟矩阵P输出:时隙分配矩阵A1:对P进行排序,得到非递减矩阵P'=(p'1,p'2,…,p'M)2:计算可用的时隙个数,nSlotNum=N-p'13:设置一个数组ArraySlotNum,保存分配给每个节点的时隙数4:while nSlotNum>0 do //把可用时隙分配给竞争节点5:for i=1;i0 then7:ArraySlotNum[i]++;8:nSlotNum--;9:else10:nSlotNum--;11:endif12:endfor13:endwhile14:得到最小传播延迟Mp=p'115:for i=1;i

算法1中所有的操作都可以在多项式时间内完成，其中步骤4-13以及步骤15-20的循环操作的时间复杂度都是O(M×N)，那么该算法的时间复杂度也就是O(M×N)，M是竞争节点的个数，N是待分配的时隙个数。

3.4.3 吞吐量理论分析

分析网络在不同状态下的吞吐量，分网络饱和和网络不饱和两种情况。

网络饱和情况：饱和情况下，除由于信号传播延迟导致的时隙浪费，其他时隙都能接收到数据包，那么在K个帧内的吞吐量可以表示为：

(22)

由式(22)，可以得到

(23)

以及

(24)

式(23)和式(24)分别给出了网络饱和情况下吞吐量的上下界。

网络不饱和情况：网络不饱和情况下无人机可以传输所有的数据包，接收端还有时隙空闲，部分时隙没有数据包到达。这种情况下，根据数据流模型来计算吞吐量Thusa。

(28)

4 实验仿真

4.1 仿真环境

本文使用OMNeT++5.0对提出的MAC协议进行了仿真。协议主要实现了数据链路层和应用层的功能，应用层产生数据包，而数据链路层实现对数据包进行调度。关于数据流模型，假设数据缓存区容量Cbuf为20 000，并且对于任意i∈{1,2,…,M}，有λi=λ，μi=μ以及σi2=σ2。每个数据包的长度为4 096 bits，发送速率和接收速率均为100 Mbps。如果mi和基站的距离超过Dmax，两者失去连接，mi会清空缓存区，并且不能发送数据包。通过这种方法实现网络拓扑的动态变化

本文的方法与两种不同类型的MAC协议进行了对比，分别是基于竞争的IRSA(Irregular Repetition Slotted Aloha)以及动态时分多址接入D-TDMA(Dynamic Time Division Multiple Access)。IRSA利用干扰消除技术实现接收端的多包接收，相比传统的Aloha协议，可以成倍地提高吞吐量。D-TDMA由基站把时隙资源按需分配给竞争节点。主要比较了以下性能参数：1)吞吐量，单位时间内接收端接收到的数据包数量。吞吐量反映了信道的利用率。2)调度时间，每个包从进入数据缓存区到被调度离开节点的时间间隔，调度时间是体现服务质量的一个重要方面。

所有的仿真参数如表1所示。

表1 仿真参数Tab.1 Simulation Parameters

4.2 仿真结果

1)吞吐量

首先研究利用时空复用方法进行多数据包并发传输对吞吐量的影响。图3为吞吐量和节点个数之间的关系。当节点个数增加时，吞吐量也随之增加，而当节点个数到达70后，吞吐量趋于稳定，表明网络达到饱和。当节点个数不多时，本文的协议和其他两个协议性能相当，而当节点个数增加，系统达到饱和时，D-TDMA的吞吐量呈明显下降趋势，这是由于随着节点的增多，D-TDMA协议导致每个节点浪费的时隙也变多。而IRSA由于节点增多后，信号冲突加剧，吞吐量也急剧下降。

另外，我们改变数据流模型中的参数，改变数据包生成速率，观察对吞吐量的影响，结果如图4所示。可以发现，在网络饱和情况下，本文的协议和D-TDMA都能达到稳定的吞吐量，但本文提出的协议要比其他两种协议都具有更好的性能；而当网络不饱和情况下，本文提出的协议与其他两个协议的性能几乎一样。

从图3和图4我们可以发现网络饱和情况下，本文提出的MAC协议比其他协议都有更大的吞吐量，说明对于基站来说，可以接收到更多的数据包。而对于节点来说，网络达到饱和意味着丢包，用户体验的下降，我们通过观察调度时间来进行评价。

2)调度时间

图3 吞吐量与节点个数的关系Fig.3 Throughput V.S. Number of host number

图4 吞吐量与数据包生成间隔的关系Fig.4 Throughput V.S. Interval

图5 调度时间与节点个数的关系Fig.5 Scheduling time V.S. Number of host number

图6 调度时间与数据包生成间隔的关系Fig.6 Scheduling time V.S. Interval

5 结论

本文提出了面向无人机网络的MAC协议。该协议基于时间重用思想，利用较大的传播延迟使并发传输成为可能，通过这种方法提高了信道利用率和网络吞吐量。进一步提出了一种无冲突的时隙分配算法。仿真及实验结果表明，该协议的系统吞吐量优于动态TDMA和IRSA，特别是网络趋于饱和的情况下，符合理论分析结果，而调度时间优于动态TDMA，劣于IRSA。