Ad Hoc网络动态时隙分配的混合MAC协议研究与仿真

赵　龙，李弘扬，叶　宁，唐　剑，刘　晖

(1.沈阳航空航天大学 民用航空学院，辽宁 沈阳 110136; 2.东北大学 计算机科学与工程学院，辽宁 沈阳 110819；3.空军工程大学 信息与导航学院，陕西 西安 710043; 4.空军764军事代表室，天津 300210)



Ad Hoc网络动态时隙分配的混合MAC协议研究与仿真

赵龙1，李弘扬2，叶宁2，唐剑3，刘晖4

(1.沈阳航空航天大学 民用航空学院，辽宁 沈阳 110136; 2.东北大学 计算机科学与工程学院，辽宁 沈阳 110819；3.空军工程大学 信息与导航学院，陕西 西安 710043; 4.空军764军事代表室，天津 300210)

摘要：针对Ad Hoc网络的节点具有移动性，信道具有多跳共享性的特点，提出动态时隙分配的混合媒体接入控制(media access control，MAC)协议，协议包括时隙分配和时隙竞争2个阶段。在时隙分配阶段，采用静态分配和动态调整相结合的方式，在为每个节点分配固有时隙的基础上，将不共享信道的节点时隙动态地分配给通信节点；在时隙竞争阶段，通过在子帧中设置不同优先级，在不参与通信节点的主时隙中，数据传输子帧被分成实时业务竞争阶段和非实时业务竞争阶段，竞争成功的节点在这个时隙传输数据，提高优先业务节点的接入概率。采用NS2网络模拟软件进行仿真，结果表明，所提混合MAC协议提高了系统的分组投递率，降低了实时业务的平均时延，协议能够充分利用信道空间复用性，减少竞争，提高接入效率，适合Ad Hoc网络。

关键词：Ad Hoc网络；时隙分配；优先级；媒体接入控制(MAC)协议

0引言

Ad Hoc网络的多跳共享信道使得其媒体接入控制(media access control，MAC)协议成为研究难点[1]。混合MAC协议凭借其带宽资源利用率高、能够满足不同任务时延需求的优点成为研究热点。但是，现有的MAC协议都没有考虑Ad Hoc网络无线信道多跳共享的特点，没有针对不同业务类型进行的区分服务。

针对不同的信道接入方式，Ad Hoc网络的MAC协议分为以下3类[2]：基于竞争机制的MAC协议；基于调度机制的MAC协议和混合类MAC协议。基于竞争的MAC协议采用竞争方式接入无线信道，竞争信道失败，则根据选择的退避算法决定下次竞争信道的时间和概率[3]，如退避算法[4]和竞争信道[5]的方式等；基于调度机制的MAC协议根据选择的调度机制为网络中的每个节点分配不同的时隙调度方案，在一帧内给每一个节点都分配一些时隙，同时保证这个节点至少在其中一个分配时隙传输信息时不受其他节点的干扰[6]。为了解决竞争类与调度类MAC协议的局限性，提出了混合接入策略，它们具有竞争类和调度类协议的特点。动态自适应媒体接入控制协议(a dynamical self-adjusting media access control protocol，ADAPT)协议[6]在固定时分多址(time division multiple access，TDMA)的基础上增加了载波监听多路访问/冲突避免(carrier sense multiple access with collision avoidance，CSMA/CA)竞争机制。改进的自适应广播(evolution of adaptive broadcast，E-ABROAD)协议[7]在数据发送之前，节点首先竞争时隙，在时隙竞争过程中节点的控制分组只在自己的时隙中发送，不会产生冲突。但这类协议还存在一些问题：节点竞争失败的概率随着网络负载而增大；协议没有对不同的业务实现差别服务，对于Ad Hoc网络中有实时性要求业务的传输需求不能够很好地满足，影响了协议的广泛使用。

目前多数混合类MAC协议通过监听主用户是否使用信道来发现主用户的信道空闲，其他用户竞争该信道的使用权。文献[8]提出的基于融合CSMA和TDMA公平共享队列的混合MAC协议提高了资源利用率，降低了时延。文献[9]根据节点竞争概率和节点数量设计竞争和传输协议。文献[10]提出的多信道MAC协议，能够为并发通信提供高的吞吐量。文献[11]提出的基于聚类的混合MAC协议保证Ad Hoc网络中信道的稳定性。文献[12]提出的支持TDMA和CSMA的MAC协议，保证安全信息在控制信道中安全可靠传输。文献[13]使用单中继信道和双中继信道在瑞利衰落信道中保证信息快速可靠传输。文献[14]利用链接访问开销、多信道隐藏终端、频谱移动性提出节能的混合MAC协议。

由于Ad Hoc网络信道多跳共享，具有空间复用性，其无线Ad Hoc网络拓扑图如图1所示。两跳以外的节点，例如灰色和黑色节点(见图1)，通信互不干扰，无论主用户是否使用，从空间复用的角度看，相距两跳以上的节点，都会在监听阶段发现该信道空闲，继而竞争使用权，带来竞争开销。为避免此类不必要的竞争，本文算法在动态时隙分配阶段，对此类信道进行二次分配，提高协议效率。

图1　无线Ad Hoc网络拓扑图Fig.1　Wireless Ad Hoc network topology

空间复用节点的查找通过交换两跳信息得到，动态时隙分配采用心跳与触发机制相结合的方式，心跳周期进行，周期值根据网络的动态性确定。当黑色节点进入到灰色节点通信范围时，触发相应分配时隙的调整。

在竞争阶段，活跃节点竞争非活跃节点的时隙，通过在子帧中设置不同优先级，根据不同业务对实时性的要求调整参与空闲时隙竞争的节点，提高优先业务节点的接入概率，保证不同时延要求业务的服务质量。

本文创新点：在时隙分配阶段，对Ad Hoc网络的共享信道中当前不参与通信节点的主时隙进行二次分配，在不产生干扰的情况下提高信道利用率；在时隙竞争阶段，提出针对不同实时性要求业务的时隙竞争帧结构，调整参与共享信道中当前不参与通信节点主时隙竞争的节点，既能保证实时性业务的需求，又能保证信道竞争的公平性。

1动态时隙分配的混合MAC协议

1.1总体设计

与传统的有线网及无线局域网不同，Ad Hoc网络最大的特点是节点的对等性以及广播信道是多跳共享性的。节点是否竞争信道成功只与两跳范围内节点有关，与两跳范围外节点无关。为了提高Ad Hoc网络的空间复用能力，提出一种动态时隙分配的混合MAC协议，其总体设计如图2所示。

图2　协议总体设计Fig.2　Overall design of the protocol

在动态时隙分配阶段，每个节点都有其固有的发送时隙。当节点有消息要发送时，在时隙竞争阶段告知其共享信道范围之内的邻居节点。通过时隙竞争阶段，每个节点可以知道共享信道范围内的活跃节点。将不共享信道的节点时隙动态分配给活跃节点使用，以此提高时隙资源的利用率。

在基于业务优先级的时隙竞争阶段，对于共享信道中当前不参与通信节点的主时隙，对时延要求较高的业务具有优先占用的权利，并且不同节点占用优先级不同。空闲时隙按照优先分配规则分配给时延要求等级最高的节点中占用优先级最高的节点，以此来保证网络中的实时业务能够接受较好的服务。

1.2动态时隙分配算法

该算法一帧结构包括3个子帧，分别是一跳传输子帧、两跳传输子帧以及数据传输子帧。一跳和两跳传输子帧交换一跳和两跳之内节点的信息。在数据传输子帧，节点在各自分配的时隙采用混合MAC协议的方式进行时隙的竞争和数据的传输。

每个节点在一跳传输子帧中都有自己的主时隙，当节点有数据要发送时，首先会在一跳传输子帧的对应时隙发送claim分组，其他节点处于侦听状态。在两跳传输子帧阶段，节点将在一跳传输子帧阶段接收到的claim分组打包成 transport分组，并将分组在两跳传输子帧中转发出去，在两跳传输子帧后，各个节点都知道其两跳范围内的活跃节点以及其业务的优先级等级。

一跳传输子帧和两跳传输子帧接收到的消息使网络中所有节点知道了两跳范围之内能够共享信道的活跃节点，共享信道范围内的所有节点的主时隙都不能被复用。非共享信道节点的主时隙按照优先级分配给活跃节点使用，我们称这些时隙为该节点的备选时隙。

时隙的分配在共享信道内有消息要发送的节点之间展开，并且采用不同优先级分配策略完成时隙竞争。所有备选时隙按照顺序轮询计算对于各个活跃节点的优先级，每个时隙都分配给优先级最高的活跃节点使用。

各活跃节点对可用时隙的优先级根据活跃节点距离以该可用时隙为主时隙的节点的跳数、活跃节点的业务量、活跃节点两跳之内节点数量(连接度)、活跃节点已经拥有的时隙数、活跃节点与以该可用时隙为主时隙的节点的接触机会和业务的实时性等因素决定。将各个判决因素归一化，设优先级判定系数为W，计算公式为

W=phah+ppap+pcac+psas+pdad

(1)

W值越大的活跃节点优先级越高，共享信道范围之内优先级最高的活跃点被分配到此时隙。由于每个节点都能知道共享信道节点对于各个时隙的W值，因此，不会产生2个互相干扰节点占用同一时隙的情况，不会产生干扰。

时隙分配过程中，按照时隙顺序依次循环计算每个时隙的优先级情况，这样可以根据每个节点的业务情况和已经占用的时隙情况动态改变分配优先级，以此保证服务质量和分配公平性。

设置以上时隙分配算法的优势：各个活跃节点能最大限度地复用时隙而没有冲突，时隙利用率高；在网络负载较高时，节点仍可以进行时隙的复用。

1.3时隙竞争算法

为了保障实时性业务的需求，在新的协议中，活跃节点对共享信道当前不参与通信节点的主时隙进行竞争，数据传输子帧结构如图3所示。

图3　数据传输子帧结构Fig.3　Structure of data transmission sub frame

时隙竞争过程如下。

1)节点在自己分配到的时隙中有数据要发送时，节点在侦听阶段与目的节点进行请求发送/清除发送(requesttosend/cleartosend,RTS/CTS)交互，其他节点处于侦听阶段，交互成功，节点在传输阶段发送数据。

2)在侦听阶段一直处于侦听的节点如果有数据发送，并且在侦听阶段没有侦听到RTS/CTS交互，传输阶段重构为实时性业务竞争阶段和非实时业务传输阶段。具有实时性业务要传输的节点在实时性业务竞争阶段竞争信道，竞争成功的节点在实时性业务传输阶段进行实时性业务的传输，竞争失败进行退避。

3)如果在实时性业务竞争阶段没有控制分组发送，此时将实时性业务传输阶段重构为非实时业务竞争阶段和非实时业务传输阶段。非实时业务传输的节点均在非实时业务竞争阶段竞争，竞争成功的节点在非实时业务传输阶段进行数据的传输，竞争失败进行退避。

在实时性业务竞争阶段以及非实时业务竞争阶段，每一阶段均有B个时间段构成，在每一个时间段，节点由W个微时隙组成，节点采用基于队列长度的载波监听多路访问(queue-lengthbasedcarriersensemultipleaccess,Q-CSMA)竞争机制进行信道的竞争，基本思想是节点的业务优先级越高，其退避的时间越短。如在实时性业务竞争阶段，有实时性业务要传输的节点在选择微时隙进行信道的占用的过程中，节点依据(2)式进行微时隙的选择。

Uniform[0,W-1]

(2)

(2)式中：Ti表示节点i进行信道竞争时选择的微时隙号；b表示节点缓冲队列长度；qi(t)表示任务的实时性，qi(t)∈[1,10]，即把业务的优先级情况分成10个不同等级，业务优先级越高值越大；Uniform[0,W-1]表示在一个时间段的W个时隙中节点占用的时隙号。从(2)式可以看出，节点业务优先级越高，其占用信道的时间越早，即占用信道的概率越大。对于非实时业务竞争阶段同实时性业务竞争阶段一样，采用Q-CSMA机制进行信道的竞争。

2数据仿真及分析

在NS2仿真系统中，对动态时隙分配混合MAC协议性能进行仿真测试。在仿真的过程中，分别采用不同的MAC协议，并对不同MAC协议的结果进行对比分析。

在仿真过程中，设置10个节点随机分布在1 000m×1 000m的范围内，仿真参数设置如下：网络规模为1 000m×1 000m；节点个数为10；传输数据类型为不变比特速率(constantbitrate,CBR)及文件传输协议(filetransferprotocol,FTP)；数据载荷为64Byte；通信半径为200m；路由协议选择无线自组网按需平面距离向量路由协议(AdHocon-demanddistancevectorrouting,AODV)；无线通信模型为TwoRayGround；仿真时间为20s；通信对数为5；通信带宽为2Mbit/s。

仿真过程中采用节点分组投递率、平均延时和时隙利用率等性能指标来衡量网络性能。

1)时延(单位：s)：接收端成功接收数据分组的时间和发送端发送数据分组的时间之差，时延通常由发送时延、传输时延和处理时延3部分组成。当网络发生拥塞或碰撞时，时延会相应地增大。平均端到端的时延表示为

(3)

(3)式中：Packet_number表示网络中总的传输数据的个数；(endtime-starttime)i表示传输的第i个数据包从源节点到目的节点所用的时间。

2)分组投递率(单位：%)：目的节点接收到的分组数与发送节点产生的分组数之比，能够反映网络能够支持的最大吞吐量。网络传输、处理数据的能力是衡量有效性、完整性、正确性和可靠性的重要指标。分组投递率表示为

(4)

(4)式中Receive表示所有目的节点收到的数据包；Source表示所有发送节点发送的数据包。

3)时隙占用率(单位：%)：每个节点的时隙占用率等于该节点占用的时隙数目与帧长的比值。

网络分组投递率随网络负载变化的对比情况如图4所示。从图4a中看出，在网络负载很小时，各个协议的分组投递率都比较高，随着网络负载的不断增加，各个协议的分组投递率都开始下降，但是动态时隙分配的混合MAC协议下降得比较缓慢。

由于动态时隙分配的混合MAC协议采用动态时隙分配，在网络负载较低和较高时，均能够很好地进行时空间复用。因此，其分组投递率都比较高，不会出现严重的下降现象。

图4b是动态时隙分配的混合MAC协议中的实时性业务和非实时业务随着发包率的增加，分组投递率的变化情况。可以看出，2种业务的分组投递率随着发包率的增加都下降，然而实时性业务的分组投递率下降的速度明显小于非实时业务的，这是因为动态时隙分配的混合MAC协议在分配信道的时候，实时性业务有优先竞争到信道的权利，所以在网络负载加重的情况下，非实时业务竞争到信道的概率很小。

平均延时随网络负载变化的趋势如图5所示。从图5a可以看出，对于每种协议，随着网络负载的增大，时延都变大。

动态时隙分配的混合MAC协议在网络负载较轻时，由于节点在时隙分配阶段和时隙竞争阶段都可以对时隙进行竞争，因此，平均时延近似ADAPT协议，随着网络负载的不断增加，由于在动态时隙分配阶段，时隙可以无冲突地进行竞争，因此，节点可以选择多个时隙发送数据包，丢包率小于ADAPT协议的丢包率，因此，平均延时小于ADAPT协议的平均时延。

图4　分组投递率随网络负载变化情况对比Fig.4　Comparison of Packet delivery ratio with the network load changes

图5　平均延时随着网络负载变化的对比Fig.5　Contrast of average delay as the network load changes

图5b是动态时隙分配的混合MAC协议中的实时性业务和非实时业务随着发包率的增加，平均延时的变化情况。可以看出，2种业务的平均延时随着发包率的增加都下降，然而实时性业务的平均延时变长的速度明显小于非实时业务。这是因为动态时隙分配的混合MAC协议在分配信道的时候，实时性业务有优先竞争到信道的权利。

3结束语

针对Ad Hoc网络的动态变化特性，提出混合式的MAC协议。该协议经过了动态时隙分配以及时隙竞争阶段对信道进行分配，能够最大限度复用信道。同时，在分配信道的时候，节点能够考虑业务的时延要求进行信道的分配，满足了时延要求较高的业务的需求。采用NS2网络模拟软件对所提出的动态时隙分配的混合MAC协议进行仿真测试，仿真结果表明，以该协议通信的网络分组投递率高、网络时延低，能有效提高网络利用率。

参考文献：

[1]MIAO X, CHUAN J, ZHANGA L. Development of Wireless Sensor Network for Dam Monitoring[J]. 2012,1(4): 256-262.

[2]ARIFUZZAMAN M, MATSUMOTO M, SATO T. An Intelligent Hybrid MAC With Traffic- Differentiation-Based QoS for Wireless Sensor Networks[J]. Sensors Journal, IEEE, 2013,13(6): 2391-2399.

[3]FENG Bing, HONG Shuangjun, WANG Zhen. IO-MAC: A novel hybrid MAC protocol with implicit ordering in WLANs[C]//Wireless Communications and Signal Processing (WCSP), 2014 Sixth International Conference.Hefei, China：[s.n.]，2014：1-5, 23-25.

[4]LIU Yi, YUEN Chau, CAO Xianghui, et al. Design of a Scalable Hybrid MAC Protocol for Heterogeneous M2M Networks[J].Internet of Things Journal, IEEE , 2014:1(1):99-111.

[5]BOOYSEN M J, ZEADALLY S, ROOYEN G. J. Survey of media access control protocols for vehicular ad hoc networks[J].IET Commun, 2011, 5(11): 1619-1631.

[6]WANG Fang, KANG Yu, TAN Xiaobin, et al. A hybrid MAC protocol for data transmission in Smart Grid[C]//Control Conference (CCC), 2014 33rd Chinese.Nanjing,China：[s.n.]，2014：8228-8233.

[7]SALMANI V, CHOU P H. Bin-MAC: A Hybrid MAC for Ultra-compact Wireless Sensor Nodes," in Distributed Computing in Sensor Systems (DCOSS)[C]//IEEE.2012 IEEE 8th International Conference on. New York: IEEE，2012: 158-165.

[8]PRIYA B，MANOHAR S S. CH-MAC: Congestion control hybrid MAC for wireless sensor network[C]//Computing, Communications and Networking Technologies (ICCCNT),2013 Fourth International Conference.Tiruchengode, India：[s.n.]，2013：1-6.

[9]LIU Yi, YUEN Chau, CHEN Jiming, et al. A scalable Hybrid MAC protocol for massive M2M networks[C]//IEEE.Wireless Communications and Networking Conference (WCNC),2013 IEEE. New York: IEEE，2013：250-255.

[10] DANG Duc Ngoc Minh, HONG Choong Seon. H-MMAC:A hybrid multi-channel MAC protocol for wireless ad hoc networks[C]//IEEE. Communications (ICC), 2012 IEEE International Conference. New York: IEEE，2012：6489-6493.

[11] GAO Ning, TANG Lun, LI Shoujie, et al. A hybrid clustering-based MAC Protocol for Vehicular Ad Hoc Networks[C]//High Mobility Wireless Communications (HMWC), 2014 International Workshop.Shanghai, China：[s.n.]，2014：183-187.

[12] DANG Duc Ngoc Minh, DANG Hanh Ngoc, NGUYEN VanDung, et al. HER-MAC:A Hybrid Efficient and Reliable MAC for Vehicular Ad Hoc Networks[C]//IEEE. Advanced Information Networking and Applications (AINA), 2014 IEEE 28th International Conference. New York: IEEE，2014：186-193.

[13] MURAD Khalid, WANG Yufeng, RA In Ho, et al. Hybrid cooperative MAC protocol for wireless ad hoc networks[C]//Computing, Network-ing and Communications (ICNC), 2012 International Conference.Maui,Hawaii：[s.n.]，2012：1015-1019.

[14] ANAMALAMUDI S，JIN M.Energy-Efficient Hybrid CCC-Based MAC Protocol for Cognitive Radio Ad Hoc Networks[J].IEEE Systems Journal,2016,10(1):358-369.

DOI：10.3979/j.issn.1673-825X.2016.04.003

收稿日期：2016-02-29

修订日期：2016-06-15通讯作者：李弘扬1470619@stu.neu.edu.cn

基金项目：国家自然科学基金 (U14331156，1151002，61401079，61501038)；中国航天科技集团公司卫星应用研究院创新基金(2014-CXJJ-TX-11)；中央高校基本科研业务费专项资金(N120404003)

Foundation Items：The National Natural Science Foundation of China (U14331156，1151002，61401079，61501038); The China Aerospace Science and Technology Corporation Satellite Application Research Institute Innovation Fund(2014-CXJJ-TX-11); The Special Fundamental Research Fund for Central Universities (N120404003)

中图分类号：TN917.11

文献标志码：A

文章编号：1673-825X(2016)04-0456-06

作者简介：

赵龙(1977-)，男，辽宁新民人，讲师，博士，研究方向为卫星信号处理、卫星导航。E-mail: zhaolong@sau.edu.cn。

李弘扬(1991-)，男，黑龙江海伦人，硕士，研究方向为空间信息网资源分配。E-mail：1470619@stu.neu.edu.cn。

(编辑：王敏琦)

Research and simulation on a hybrid MAC protocol with dynamic slots allocation in Ad Hoc network

ZHAO Long1，LI Hongyang2，YE Ning2，TANG Jian3，LIU Hui4

(1. Shenyang Aerospace University, Civil Aviation Institute, Shenyang 110136, P.R. China;2. Northeastern University, School of Computer Science Engineering, Shenyang 110819，P.R. China;3. Air Force Engineering University, School of Information and Navigation, Xi’an 711043, P. R. China;4.The PLA military representative office of 764 factory, Tianjin 300210, P.R. China)

Abstract:According to the mobility of nodes, multi-hopping share of channels in Ad Hoc networks, hybrid MAC protocol with dynamic slots allocation is presented. The protocol includes two stages: slots allocation and slots competition. During the stage of slots allocation, we adopt the combination of static allocation and dynamic adjustment. On the basis of allocating inherent time slot of every node, dynamically allocate the time slots of nodes that do not share channels to the communication nodes; In the stage of competition, by means of setting different priorities in sub-frames, in the main slots of nodes that do not take part in communication, data transmission sub frames are divided into real time services competition stage and un-real time services competition stage, and nodes that compete successfully transmit data at this time slot to improve access probability of preferred business nodes. We simulate the proposed MAC protocol with NS2 network simulation software, and the result shows that the proposed hybrid MAC protocol improves the system packet delivery rate and reduces the average delay real time services. The protocol can improve service quality of real-time services and optimize the whole performance of network.

Keywords：Ad Hoc networks; allocation of time slots; priority; media access control(MAC) protocol