移动自组网MAC协议组网和业务调度算法研究*

赵天鹤，徐鹏杰，史秀秀



移动自组网MAC协议组网和业务调度算法研究*

赵天鹤1，徐鹏杰1，史秀秀2

（1 中国航天电子技术研究院空间电子工程中心 北京 100094；2 北京遥测技术研究所 北京 100094）

为满足无中心的移动自组网对多变网络拓扑、实时通信和网络规模可扩展的需求，提出一种网络建立时间短、时延短和信道利用率高的MAC协议策略。通过网络分簇组网算法建立健壮高效的组网模型，利用时隙动态复用算法实现基于竞争的TDMA接入协议，从而提高信道利用率和网络吞吐量。在NS2中对单簇20个节点作性能仿真，分析多种队形的网络拓扑以及端到端时延，并对固定TDMA和基于竞争的TDMA接入方式做了对比实验。仿真结果显示，各种拓扑结构的网络建立时间都很短，基于竞争的TDMA接入方式相比固定TDMA可获得更高的网络吞吐量和更短的端到端时延。

移动自组网；分簇组网；竞争的TDMA；短时延；高吞吐量

引 言

移动自组网由于能够满足军事应用需要的高抗毁性和抗干扰性而具有很大应用前景，但因终端能源受限、芯片内存有限、CPU处理能力有限等客观不利条件，实用化移动自组网的研究还是存在诸多困难。鉴于此，本文研究可提高网络规模、缩短网络建立时间的组网方法和可提高信道利用率、缩短端到端时延的接入方法。

由于自组织网节点传输距离有限，还有回避阻挡和抗毁的需求，因此数据包到达目的节点往往需要多跳。当网络规模增大时，数据包的转发会增多，转发所占用无线资源也会相应增多。除此之外，构建路由所需的开销也会随着网络规模的增大而增大，而无线网络的稳定性会随着网络规模的增大而减小。由于移动自组网的主要目的是为部队的战术级通信与指挥控制系统提供可靠的、便捷的、高效的、安全的通信链路，因此本文提出网络分簇组网算法，将中心控制结构与分布式控制结构相结合，适用于军事应用，同时提高了网络的可扩展性。

分布式调度广泛应用在移动自组网中，载波侦听多址接入CSMA（Carrier Sense Multiple Access）机制在重网络负载下会产生冲突，造成很大的端到端时延和很低的资源利用率[1]。而预约式TDMA的时帧被分为控制时隙和数据时隙[2]，有专门的控制信道，保证了低冲突概率[3]。现已有大量文献对TDMA接入方式进行研究和改进，文献[4]提出一种可提高时隙利用率的时隙分配算法，文献[5，6]提出一种自适应延迟指数算法提高网络在多种流量下的时延性能，文献[7]提出一种多权机制满足多个小时隙分配的带宽需求，提高了网络吞吐量和均衡性，文献[8]针对单跳自组网场景进行了网络平均吞吐量的评估。这些都是偏学术研究的，少有可以与实际工程接轨的研究成果。在研究固定TDMA接入方式时笔者体会到，在网络运行过程中，经常会遇到传输业务不平衡的情况，某些节点上的负载过重，而其他一些节点上却存在空闲的时隙资源，导致网络传输效率低下。本文针对移动自组网提出一种能够提高信道利用率和网络吞吐量的基于竞争的动态TDMA时隙分配算法，开发出实用化MAC协议，便于工程实现。

1 协议描述

1.1 网络分簇组网算法

在战术应用中，移动自组网的用户（节点单元）之间为了共同的作战任务而协同行动，节点的运动也通常围绕本地指挥员所在的节点展开。本文提出的网络分簇算法主要依据节点的任务特点，把执行同一个作战任务的节点划分到同一个簇内，将级别最高的节点作为簇头节点。簇单元也可以称为子网单元（以下简称子网）。

我们定义有个节点基于跳频技术在个频点（12…f）上组成一个最多跳的自组织网络。跳频通信中正确接收跳频信号的前提条件是收发双方实现跳频图案同步，本文选用基于时间信息的同步字头法作为跳频同步方法，即采用基于TOD（Time of Day）的跳频同步法实现自同步，发送方利用同步头把自己的时间信息TOD发送给接收方，接收方通过接收对方的TOD信息来修改本地TOD使之与发送方时间上保持一致，从而实现跳频同步。本文采用的TOD同步法具有同步时间快、同步概率高和随机性好的特点。各个子网的组网流程如图1所示，时隙分配分为五个阶段，如图2所示。

图1 各子网组网流程

图2 时隙分配图

图3 第一阶段时隙分配

首先上层下达组网指令后进入第一阶段，在数据传输过程中为了防止刚收到数据就要立刻发送的情况，故在第一阶段开始后预留11的空闲时隙，设簇头节点在每个频点上发送时长为s，用来发送组网TOD同步信息帧。为保证接收，在个频点上循环发送次，一共是s××。设第一阶段共发送TOD时长为12，则12=s××。其他节点处于同步扫描状态，在没收到过TOD的情况下，在每一个频点接收s×，个频点上循环接收。这样保证当发送节点在个频点每s循环发送时，接收节点在s×内能找到与发送频点对应的频点，且当两个节点之间只在某个频点上可通而在其他频点不通时，保证在12中可以收听到发送节点。第一阶段时隙分配如图3所示。

第一阶段结束后，所有的一跳节点已经收到簇头发送的TOD并完成同步，第二阶段要使得所有的节点完成同步。从一跳节点开始到–1跳节点依次发送TOD给下一跳节点。同第一阶段一样，设每个节点需要12的时隙发送TOD，同时每一跳的节点数不确定，故采取考虑最大节点数的固定时隙分配，以节点号0~–1为索引，为每一跳可能存在的0~–1号节点依次分配12，即×12=22。同样，为了防止在12中刚收到TOD包，又要立刻发送TOD的特殊情况，在每一跳节点发送TOD之前预留21的空闲。至此，第二阶段一共需要的时间为：(子网最大节点数×12+21)×最大跳数，即(×12+21)×=(22+21) ×。第二阶段时隙分配如图4所示。

经过前两个阶段，子网内所有节点已完成时间同步，第三阶段要从最大跳数处开始广播自己的路由信息，使得簇头节点可获得子网内所有节点的在线情况。本阶段的路由信息只是当前所有的在线节点，不包括节点之间的连接关系。由于已经完成同步，每个在线节点的跳频规律完全一致，所以之后的组网帧只需在每个频点上发送一次即可。从最大跳数的节点开始，可能存在的0~–1号节点依次占30的时隙广播路由信息帧（RI），每一跳节点收集上一跳节点的路由信息，合并后加上自己本节点的路由信息，作为自己的RI内容发送。第三阶段时隙分配如图5所示。

图4 第二阶段时隙分配

图5 第三阶段时隙分配

第四阶段簇头节点将全部节点的在线信息广播出去，每个节点都可以得到全部节点的路由信息。

以上过程是通过MAC层产生数据包并控制时隙分配完成每个节点的时间同步，并获知所在子网内在线节点的情况，然而每个节点的连接情况未知，还不能直接进行业务发送，所以组网的快速路由阶段是通过增加路由包发送的频率，快速建立起整个网络的拓扑。路由层作为独立运行路由算法的部分，单独用一个线程来完成。

上述网络分簇组网算法的伪代码如表1所示。

表1 网络分簇组网算法的伪代码

1.2 时隙动态复用算法

固定TDMA接入方式在网络运行过程中经常会遇到传输业务不平衡的情况，即在某些节点上的负载过重，甚至出现拥塞导致分组丢失，而其他一些节点上却存在空闲的时隙资源，大大降低了信道利用率，为此我们引入带竞争的TDMA时隙分配方法。整个时隙帧分为信令子帧、迟入网TOD与路由信息子帧和业务信息子帧。各部分的时隙分配如图6所示。

图6 带竞争的TDMA时隙分配

第一部分为声明子帧RTS（Request To Send），用于声明节点业务情况，每个节点分配R时隙；第二部分为应答子帧CTS（Clear To Send），用于回应收到的RTS，返回两跳之内所有节点的业务情况，每个节点分配C时隙；第三部分为迟入网TOD与路由信息子帧，主要用于维持全网的跳频同步，使迟入网节点能够加入网络以及路由表的更新，每个节点分配L时隙；第四部分为业务信息子帧，用于传输各种类型的业务数据，每个节点分配D时隙。其中，第一、二部分为固定分配时隙，而第三、四部分时隙为动态复用时隙。

带竞争的TDMA时隙分配方法也是一种基于固定TDMA的动态时隙分配算法，其简化后的时帧结构如图7所示。

图7 带竞争的TDMA简化时帧结构

一个完整的时帧由三个子帧组成，分别是声明子帧、应答子帧和信息子帧。每个子帧都分为个时隙，从0到–1编号，分别与0~–1号节点相对应。其中，前两个控制子帧分别用于交换信息，信息子帧用来传输数据业务。我们称节点(0≤≤–1)为数据时隙(0≤≤–1)的主节点，数据时隙为节点的主时隙。

对于时帧中每个时隙的分配方式有以下规定：①每个子帧的第号时隙固定分配给第号节点，其中前两个控制子帧的时隙不能被复用，即声明子帧和应答子帧的第号时隙只能给第号节点发送控制信息；②当某节点有数据业务需要发送时，该节点一定可以在主时隙发送数据，其他节点都不能竞争该时隙；③当某节点没有数据业务需要发送时，其他节点可以竞争它的主时隙，由这些节点中优先级最高者获得该时隙的使用权；④只有在本帧的声明子帧中声明了有数据需要发送的节点才可使用它的主时隙发送数据，只有其中声明了优先业务或者较大业务量的节点才能参与竞争本帧中的其他空闲时隙。本文的竞争机制在提高了时隙利用率的同时也避免了节点间收发冲突。

如果某节点需要发送数据，则在声明子帧中的固定分配时隙发送一个RTS分组，其他时候该节点均处于侦听状态。由于所有节点都只在自己的固定分配时隙发送RTS，因此节点之间不会发生冲突。RTS分组中包括该节点的节点号，另外，若该节点业务量较大或者业务优先级高，还需将RTS中的标志位置1。经过声明过程从时隙l到时隙的第一轮侦听，各节点都可以知道有哪些活跃节点以及竞争节点。在应答子帧中，所有在声明阶段收到RTS的节点把获得的节点信息综合后封装进一个CTS，然后各节点在应答子帧中的固定分配时隙发送CTS，节点不发送CTS时都处于侦听状态。在对应答子帧的各时隙进行了第二轮侦听之后，各节点综合从RTS和CTS分组获得的信息，就可以得到所有活跃节点和竞争节点的信息。若某节点是活跃节点，则在应答阶段过后，它首先可以在该帧的主时隙发送数据。对于有重业务或重路由的节点，除了主时隙以外，还要设法竞争更多的时隙。在声明阶段和应答阶段接收的信息使它获得了活跃节点和其他竞争节点的信息以及可竞争时隙。网络中每个节点都存有这样一个优先级表，竞争过程就是对优先级表的查找过程。对于每个可竞争时隙，节点将自己的优先级与其他竞争节点的优先级相比较，若发现自己的优先级最高，则可占用该时隙，一旦节点占用了某个时隙，其他节点就不能抢占该时隙，这样可以保证高优先级节点能够优先竞争到时隙。这里的优先级表在当前宽带自组织网络里面，根据节点的优先级以及业务的优先级综合得到。各活跃节点在各自分配到的时隙发送信息，在其他时隙中接收信息；下一帧开始，网络中各节点又从声明阶段开始重复以上过程。

2 仿真与实现

本文使用NS2网络仿真软件对两种队形的拓扑结构和网络建立时间进行了仿真，并对竞争TDMA和固定TDMA时隙分配算法的端到端时延、丢包率和吞吐量进行性能对比。搭建了20个无线节点的仿真模型，通过表2的仿真环境完成本文提出的MAC协议仿真。

表2 仿真环境

2.1 拓扑队形和网络建立时间

本节对协议描述中的网络进行了仿真，假设节点数=20，频点数=4，分别仿真了跳数=1和=8两种情况下的网络建立时间。当=1时，称为全通网络，表示的是节点之间的距离较近，任意两点都可以直接通信；当=8时，称为8跳网络，表示的是节点比较分散，最远的两个节点之间相互通信需要经过7个节点中转。图8为20节点全通网络和八跳网络的组网拓扑仿真结果。

在该仿真环境中，20个节点的数据队列长度为50，数据队列类型为优先级队列——PriQueue。仿真得到全通网络的建立时间为13.434s，八跳网络的建立时间为19.799s。从仿真结果可以看到，8跳网络的建立时间比全通网络略长，这是因为仿真时采用的路由协议是OLSR协议，组网过程中要在全网内广播路由信息以完成路由表的建立，8跳网络路由信息的广播速度要比全通网络慢一些，因此8跳网络的建立时间要长。

2.2 端到端时延

本节我们仿真比较固定TDMA接入算法和基于竞争的TDMA接入算法在8跳网络拓扑中的性能。假设每个时帧有250个时隙，时帧中每个节点发送RTS的时隙数R=1，CTS的时隙数C=1，每个节点的业务时隙数D=9。

图8 20无线节点全通网络和八跳网络组网拓扑仿真

端到端时延是指两个节点之间传输业务所需要的时间。为了比较基于竞争的和固定的TDMA接入算法节点的端到端时延，在8跳网络中分别应用两种接入算法，以10包/s的速率发送业务数据，统计接收端接收到全部10包业务数据的时延。业务源节点和业务目的节点的距离分别为1跳至8跳，仿真结果如图9所示。

图9 固定TDMA和基于竞争的TDMA接入算法的端到端时延仿真结果

从图9可以看出，固定TDMA接入算法的时延始终要大于基于竞争的TDMA接入算法，这是因为空闲时隙竞用机制发挥了作用，固定TDMA每个时帧（250个时隙）最多只能发送9包数据，剩余的一包数据需要等到下一个时帧才能发送，而基于竞争的TDMA可以在当前时帧通过竞用空闲时隙发送完成，所以时延要小于固定TDMA。随着业务源节点与目的节点跳数增加，时延差会逐渐累积，不断增大。

2.3 丢包率

本节统计了全通网络中基于竞争的和固定的TDMA接入算法在不同业务量下的丢包率。发送业务量从10包/s至1000包/s，基于竞争的和固定的TDMA接入算法的丢包率仿真结果如图10所示。

从图10可以看出，随着发送数据量的增加，两种接入算法的丢包率均不断增大，但固定TDMA接入算法的丢包率始终大于基于竞争的TDMA接入算法。

2.4 吞吐量

本节统计了全通网络中基于竞争的和固定的TDMA接入算法在不同业务量下的吞吐量。发送业务量从1包/s至100包/s，仿真结果如图11所示，固定TDMA接入算法每秒发送35个业务包时无丢包，而基于竞争的TDMA接入算法可以达到每秒发送50个业务包时无丢包，即基于竞争的TDMA接入算法的吞吐量性能更佳。

3 结束语

本文研究移动自组网MAC协议组网和业务调度算法，提出分簇组网算法和部分时隙动态复用算法，在信道利用率和网络吞吐量得到提高的同时降低了丢包率和端到端时延。其中，分簇组网算法结合了中心控制结构和分布控制结构，提高了网络的可扩展性，更适合于军事应用；部分时隙动态复用算法允许重业务节点竞争其他节点的空闲时隙，提高了网络吞吐量和传输效率。在NS2网络仿真软件中仿真了单簇20个节点的网络规模，并对端到端时延、丢包率和网络吞吐量做了对比仿真，结果显示本文提出的协议算法可以有效地降低丢包率和端到端时延，提高网络吞吐量和信道利用率。

图10 固定TDMA和基于竞争的TDMA接入算法的丢包率仿真结果

图11 固定TDMA和基于竞争的TDMA接入算法的吞吐量仿真结果

移动自组网的高抗毁性和抗干扰性使其具有很大的军事应用前景，本文给出的组网过程和包含上下层数据传输在内的业务调度算法便于工程实现。

[1] LU K, WU D, QIAN Y, et al. Performance of an aggregation-based MAC protocol for high-data-rate ultrawideband ad- hoc networks[J]. IEEE Transactions on Vehicular Technology, 2007, 56(1): 312–321.

[2] IEEE computer society and ieee microwave theory and techniques society. IEEE standard for local and metropolitan area networks-Part 16: air interface for fixed and mobile broadband wireless access systems-amendment 2: physical and medium access control layers for combined fixed and mobile operation in licensed bands[S]. New York: IEEE, 2006.

[3] NEKRASOV P, FAKHRIEV D. Transmission of real-time traffic in TDMA multi-hop wireless ad-hoc networks[C]// IEEE International Conference on Communications, 2015: 6469–6474.

[4] ATTIA E O, AMIN A S, EI HENAWY H M. Novel IEEE 802. 16 mesh node architecture to achieve QoS in coordinated distributed mode[C]//14th International Conference on Advanced Communication Technology, 2012: 365–370.

[5] KHAINU P, KEERATIWINTAKORN P. An adaptive holdoff exponent approach for coordinated distributed scheduling in WiMAX mesh networks[C]//19th IEEE International Symposium on Intelligent Signal Processing and Communication Systems, 2011: 1–5.

[6] LAKANI S, GHAFFARIAN H, FATHY M, et al. A neighbor-based holdoff reduction scheme for distributed scheduling in wireless mesh networks[C]//6th IEEE International Conference on Wireless and Mobile Computing, Networking and Communications, 2010: 733–738.

[7] AGUSTININGSIH D R, TEKNIK F, ADRIANSYAH N M, et al. Performance analysis of coordinated distributed data scheduling schemes in wireless mesh network[C]//International Conference on Computer, Control, Informatics and Its Applications, 2013: 43–48.

[8] CHA J R, GO K C, KIM J H, et al. TDMA-based multi-hop resource reservation protocol for real-time applications in tactical mobile ad-hoc network[C]//IEEE Military Communications Conference, 2010: 1936–1941.

Research on networking and business scheduling algorithm of MAC protocol for mobile ad-hoc network

ZHAO Tianhe1, XU Pengjie1, SHI Xiuxiu2

（1. Space Electronic Engineering Center, China Academy of Aerospace Electronics Technology, Beijing 100094, China; 2. Beijing Research Institute of Telemetry, Beijing 100094, China）

This paper proposes a MAC protocol strategy with short networking time, low delay and high channel utilization to meet the requirements of variable network topology, real-time communication and scalability of network scale for a non-centered mobile ad-hoc network. Also a cluster networking algorithm to establish a robust and efficient networking model and a partial time slot dynamic multiplexing algorithm to implement a competition-based Time Division Multiple Access (TDMA) access protocol are proposed to improve the channel utilization and network throughput. In NS2 a performance simulation for a single cluster with 20 nodes is established, the multi-formation topology and the end-to-end delay are simulated, and a comparison experiment between fixed TDMA and competition-based TDMA is carried out. Simulation results show that the networking time of different several topologies are very short and the competition-based TDMA is capable to obtain a higher network throughput and a lower end-to-end delay.

Mobile ad-hoc; Cluster networking; Competition-based TDMA; Low end-to-end delay; High throughput

TN929

A

CN11-1780(2019)02-0015-07

基金项目：重大国防项目（无人作战平台快速动态自组网技术）

2019-01-19

2019-02-18

赵天鹤 1993年生，硕士，主要研究方向为无线通信网络。

徐鹏杰 1989年生，硕士，主要研究方向为无线通信网络协议。

史秀秀 1985年生，硕士，主要研究方向为无线通信数据链。