一种固定分配与动态竞争结合的MAC层协议算法

秦 茜，宋志群，刘玉涛

(中国电子科技集团公司第五十四研究所，河北 石家庄050081)

一种固定分配与动态竞争结合的MAC层协议算法

秦 茜，宋志群，刘玉涛

(中国电子科技集团公司第五十四研究所，河北 石家庄050081)

为提升移动自组织 (MANET)网络效率，动态时分多址 (TDMA)时隙分配算法已经成为MANET网络的研究热点之一。提出了一种新颖的固定分配与动态竞争结合的媒体访问控制 (MAC)层协议算法。该算法能在保证基本话音通信需求的基础上，根据不同业务特点动态调整时隙，保证网络对空闲时隙资源竞争使用的效率。仿真结果表明，相对于固定分配时隙算法，该算法大幅度提高了MANET网络的效率。

MANET网络;TDMA协议;MAC协议

0 引言

MANET网络作为一种无中心节点的移动通信网络，自20世纪70年代被提出后，就因其无需固定基础设施支持、组网快速和灵活等特点而一直受到广泛关注，尤其是在战术通信、抢险救灾、大型集会等突发性和临时性场合中得到应用［1］。其中，MAC协议处于MANET网络协议栈的底层，控制着节点接入共享无线信道的方式与获得信道资源的多少，MAC层的性能高低直接影响着MANET网络的整体性能。

MAC协议主要解决2个问题:①如何将频谱划分为不同的信道;② 如何将不同的信道分配给不同的节点［2］。研究这2个问题最佳组合的最终目的是在保证MANET网络间终端正常通信的前提下，尽可能地提高网络的吞吐量。按照信道分配方式的不同，MANET网络现有的MAC协议可以分为3类:基于分配的MAC协议、基于竞争的MAC协议和混合MAC协议［3］。

目前，基于分配的MAC协议一般采用同步通信方式［4］。这类协议不能根据节点业务需求变化动态调整分配方案，导致资源浪费，实用性较差;基于竞争的MAC协议通常采用异步通信模式，当节点有数据要传输时，节点自由竞争并在竞争成功的情况下占用信道，因此存在冲突较多、吞吐量小和时隙浪费严重等问题;混合MAC协议在节点需要发送数据时，才分配给其所需时隙，数据发送完毕，节点取消对时隙的占用，信道利用率得以提高，但也存在一些不足，如空闲时隙的利用率低等［5］。

为了提高MANET网络的端到端吞吐量，本文提出了一种新的混合式MAC协议，即固定分配与动态竞争结合的MAC层协议。既保证每个节点都至少拥有一个固定的时隙，又能够根据业务传输的需求对升级了的节点竞争空闲时隙，实现对空闲时隙的充分利用。

1MANET网络MAC协议

1．1 基于分配的MAC协议

基于分配的MAC协议采用同步通信模式，时隙与节点的映射决定了一个节点在其特定时隙内允许访问的信道。该类协议在中等到繁重的传输载荷条件下运行良好，但信道时隙化导致在轻传输载荷条件下的时延相对于竞争协议较大。常见的基于分配的协议包括5步预留协议(FPRP)［6］、空间时分多址协议(STDMA)［7］和统一时隙分配协议(USAP)［8］等。

基于分配的 MAC协议主要有频分多址(FDMA)、时分多址(TDMA)和码分多址(CDMA)。FDMA实现简单，但是频带利用率低，抗干扰能力差，尤其是在节点高速运动的网络中产生的多普勒效应对它造成的影响非常大;CDMA要求发送方与接收方必须保持严格的同步，传输时延和强烈的时延起伏使得实现精确定时十分困难;TDMA将不同的时隙分配给不同的用户，是一种目前比较常用的战术数据链多址接入方式，但是目前的MAC算法在网络规模大、节点数量多和数据业务负载高时，由于所采用的时隙与帧结构较长导致网络延迟大，接入延时较长。

1．2 基于竞争的MAC协议

在基于竞争的MAC协议中，当节点需要传输数据时，就对信道发起竞争，并在竞争成功后占用该信道;如果竞争失败则根据所采用的退避算法修改下次竞争的时间或者概率。典型的基于竞争的MAC协议有载波监听多址接入(CSMA)［9］协议、避免冲突的多路访问(MACA)［10］协议和无线局域网的分布式协调功能(IEEE 802．11 DCF)协议等。

该类MAC协议的性能主要由其采用的竞争机制所决定，这其中包括信道竞争方式和退避算法等。该类MAC协议可以在低传输载荷下运行良好，具有信道利用率高、碰撞次数少以及分组传输时延小等特点。随着传输载荷的增大，会导致碰撞次数增多，协议性能下降。在传输载荷很重的时候，竞争协议可能会随着信道利用率下降而变得非常不稳定。这就很有可能导致分组传输时延呈指数形式增大，甚至网络服务的崩溃。

1．3 混合类MAC协议

混合协议能够保持所组合的协议的优点又能避免其缺陷，在传输载荷轻的时候表现为基于竞争的协议性能，而在传输载荷重的时候近似表现为基于分配的协议性能。典型的协议有基于优先级的时分多址协议(PTDMA)［11］、混合 TDMA/CSMA［12］和动态自适应媒体访问控制(ADAPT)［1 3］等。

为了解决基于竞争与基于分配的MAC协议在不同网络环境下应用受限的问题，融合了基于竞争和基于分配的混合MAC协议被提了出来。基于竞争和基于分配是2种明显不同的机制，所以如何在混合2种机制时取得最优化的效果成了难题。

主流的混合类MAC协议都基于TDMA协议并引入了 CSMA技术和请求发送/清除发送(RTS/ CTS)握手机制［14］。混合类 MAC协议的帧结构中总会包含竞争阶段和发送阶段。显然，混合类MAC协议的设计难题就是如何在竞争阶段使得节点高效的竞争空闲时隙，以及在发送阶段如何更新己分配时隙。

2 固定分配与动态竞争结合的MAC层协议

2．1 协议原理

由于单一的固定时隙分配与动态竞争时隙分配算法各自均存在不足，为此，基于竞争理论，利用2种算法的优点，克服各自的缺点，提出了一种固定与动态竞争相组合的MAC层协议。该协议的帧结构为:每个帧的时隙由2部分组成:一部分称为控制时隙，用于时隙的竞争与预约;另一部分时隙是数据时隙，用于已分配预约成功后数据的传送，2部分一一搭配组成一组称为一个时隙。这种帧结构的设计有利于节点在竞争阶段高效地竞争空闲时隙，以及在发送阶段更快地更新时隙分配信息。该协议基本思想为:网络中的每个节点固定分配得到一个时隙，然后将网络传输需求大的节点进行升级，使得其具有格外竞争更多时隙的权利。这样就可以实现在保证常规的语音通信任务的条件下，灵活高效地分配剩余时隙资源。帧结构的设计如图1所示。

图1 协议帧结构

2．2 协议算法步骤

2．2．1 固定时隙分配阶段

将一帧划分为2部分，一部分用于固定分配，即采用固定分配策略为网络中的每个节点分配一个固定时隙，主要承担常规的语音通信任务，重点是保证其低延时性能，而且固定时隙数根据当前活动节点的数目进行调整。

在该阶段，节点开机之后的时隙申请和时隙分配功能，通过接收来自其他节点的控制时隙信息，进行分析和处理，进而控制终端节点在合适的时刻发送信令信息。其输入是来自其他节点的控制时隙的信令信息，输出对这些信息的处理结果，信息格式相同，同时输出还包括在哪个时隙进行发送。

2．2．2 时隙动态竞争阶段

根据网络层的监控，对于有高业务传输需求的节点，设计将该类节点进行升级，定义高优先级，并设计其额外竞争更多的帧周期中的空闲时隙，用于支持高数据率传输和高服务质量等级需求。最后，当传输结束后，释放此阶段占用的时隙，以供其他传输所用。

具体地说，对于有高业务传输需求的节点，若在一跳范围内的2个节点需要进行高服务质量等级业务传输，该算法可以很快地完成时隙预约，并在当前帧周期内就进行数据传输;若源节点和目的节点之间是多跳，高业务需求的源节点竞争的是2跳之内绝对可用的时隙，其过程是先在控制时隙预约下一帧的数据时隙使用权。当传输过程结束后，节点的高优先级权限取消，并且释放占用的额外时隙。具体流程如图2所示。

图2 协议流程

3 仿真与分析

3．1 仿真环境及参数设置

为了测试文章中提出的协议合理性和性能，采用与固定时隙分配算法进行对比的方式，分析2种算法在传输层时延和端到端吞吐量的仿真数据。仿真中，以7个节点为例，7个节点在多跳之内随机分布，并按照随机生成的移动路径进行动态移动，其拓扑结构如图3所示。仿真中设置的场景尺寸为4．5 km×3 km，节点的通信距离是2 km，场景中的节点个数是7，节点的最大移动速率是80 km/h，最大的中继次数为4，仿真时间为10 s。

图3 仿真场景拓扑

3．2 仿真结果与分析

3．2．1 传输层时延

2种时隙分配算法的平均时延变化曲线如图4所示。link1－1和link2－1是典型 TDMA固定时隙分配算法的时延数据，由于LINK 1是4跳，LINK 2 是2跳，因此2条时延数据线虽形状相同，但是收敛数值相差0．2 s。link1－2和 link2－2则是固定分配与动态竞争结合的MAC层协议的仿真数据。在该算法中，由于时隙的动态分配，占用时隙多的LINK 1的传输层时延与固定分配算法相比，下降了0．28 s，相对地，LINK 2占用的时隙数减少造成时延增大了0．7 s。从图4可知，随着时间的增加，2条路由的固定时隙分配算法的平均时延均保持不变，而文章中提出的混合式时隙分配算法的平均时延，由于LINK 1业务量大，节点级别高，时延降低，相反LINK 2的时延增大。这主要是由于固定时隙分配算法是注重公平性的策略，而文章中提出的新算法由于更加注重效率，所以在部分固定时隙的基础上加入了动态分配时隙策略，大幅度地减少了等级高的节点的平均时延。

图4 2种时隙分配算法的平均时延变化曲线

3．2．2 端到端吞吐量

固定时隙分配与本文提出的混合式时隙分配算法的端到端吞吐量对比结果如图5所示，link1－1和link2－1是典型TDMA固定时隙分配算法的吞吐量数据，2条线完全重合体现了该算法的公平性原则。link1－2和link2－2则是改进算法效率原则的体现，根据业务的大小将时隙更多地分配给业务量大或者业务更为重要的节点，在仿真中LINK 1上的业务量更大而且具有优先级，则将时隙更多地分配给LINK 1，相应地，LINK 2上所占用的时隙就相对减少。从图5可以看出，固定时隙分配算法由于不能动态适应业务的变化，2条路由上其端到端吞吐量是完全一样的，导致时隙浪费比较严重;相对于固定时隙分配算法，本文提出的时隙算法由于充分利用了固定时隙分配、动态时隙竞争的优点，引入动态分级原理对有突发业务的节点进行升级，通过调整空闲时隙给高等级节点，提高了传输效率。

图5 2种算法的端到端吞吐量对比

4 结束语

随着MANET网络技术的不断发展，MAC层协议算法的研究日新月异，本文在分析典型TDMA时隙分配算法的基础上，提出了一种新颖的混合式MAC层协议算法。算法根据不同业务的不同需求，动态调整时隙分配策略，在保证基本话音业务需求的前提下，最大限度地满足突发大业务量用户的通信需求。从仿真结果可以看出，本文提出的固定分配与动态竞争结合的MAC层协议算法实现了在基本兼顾公平的同时，大幅度地提高了MANET网络的效率。

［1］ 霍金海，王 钺，徐赞新，等．基于负载和优先级的MANET优化策略［J］．清华大学学报(自然科学版)，2012，52(9):1 270－1 274．

［2］ 王英杰，刘 觅，吴振华，等．无线Mesh网络的最大并发公平调度［J］．北京邮电大学学报，2007，30(4): 33－36．

［3］ 李 勇，匡坤高，王 平，等．分布式自组织网络动态功率控制机制的研究与实现［J］．东南大学学报(自然科学版)，2011，41(2):296－300．

［4］ 罗正华，孟 源，苏文昊，等．基于无线自组织网MAC 的FPRP协议改进研究［J］．成都大学学报(自然科学版)，2015，34(2):152－155．

［5］ DHIRAJ S P，RAHUL G．A New Protocol Design for Location Based Ad-Hoc Networks［C］∥India:2015 InternationalConference on IndustrialInstrumentation and Control(ICIC)，2015:988－991．

［6］ ZHU C X，CORSON M S．A Five-Phase Reservation Protocol (FPRP)for Mobile Ad hoc Networks［C］∥America:Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies，1998:322－331．

［7］ NELSO R，KLEINROCK L．Spatial TDMA:A Collision-Free Multihop Channel Access Protocol［C］∥America: IEEE Trans．Communication，1985:934－944．

［8］ YOUNG C D．USAP:A UnifyingDynamicDistributed MultichannelTDMA SlotAssignmentProtocol［C］∥America:IEEE Conference on Military Communications，1996:235－239．

［9］ KLEINROCK L，TOBAGI F A．Packet Switching in Radio Channels:Part I-carrier Sense Multiple Access Modes and Their Throughput-delay Characteristics［C］∥America: IEEE Transition Communication，1975:1 400－1 416．

［10］KARN P．MACA-A NewChannelAccessMethodfor Packet Radio［C］∥ARRL/CRRL AmateurRadio9th Computer Networking Conference，1990:134－140．

［11］EPHRIMIDES A，MOWAFI O A．Analysis ofaHybrid Access Scheme for Buffered Users-probabilistic Time Division［C］∥IEEE Transactions on Software Engineering，IEEE，1982:52－61．

［12］SHARP B，GRINDROND E，CAMM D．Hybrid TDMA/ CSMA Protocol for Self-Managing Packet Radio Networks ［C］∥Tokyo:1995 Fourth IEEE International Conference on Universal Personal Communications，1995:929－933．

［13］CHLAMTAC I，FARAGOEA，MYERSA D，etal．ADAPT:A DynamicallySelf-AdjustingMediaAccess Control Protocol for Ad-hoc Networks［C］∥America: Global Telecommunications Conference，1999:11－15．

［14］罗 涛，赵 明，李静叶，等．认知无线电自组织网络MAC协议［J］．计算机学报，2013，36(7):1 337-1 348．

An Algorithm Combining Static Allocation with Dynamic Contention in MAC Protocol

QIN Qian，SONG Zhi-qun，LIU Yu-tao
(The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China)

In order to improve the MANET network efficiency，dynamic TDMA time slots assignment algorithm now becomes one of the hot research topics in MANET network．This paper proposes a new algorithm combining static allocation with dynamic contention in MAC protocol．Based on ensuring the basic communication requirements of users，this algorithm can adjust in dynamic mode the time slots according to different business characteristics，so that it can make efficient use of slot resource．The simulation results show that compared with the static allocation algorithm，the proposed algorithm can significantly improve the efficiency of MANET network．

MANET;TDMA protocol;MAC protocol

TN911

A

1003－3106(2017)02－0011－04

10．3969/j．issn．1003－3106．2017．02．03

秦 茜，宋志群，刘玉涛．一种固定分配与动态竞争结合的MAC层协议算法［J］．无线电工程，2017，47(2):11－14．

2016-11-04

通信网信息传输与分发技术重点实验室开放基金资助项目(EX156410046)。

秦 茜女，(1988—)，硕士研究生。主要研究方向:无线通信。

宋志群男，(1963—)，研究员。主要研究方向:无线通信。