王宝玺，文运丰，马鹏飞，扈 鹏

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

一种定向网络动态时分信道接入机制

王宝玺，文运丰，马鹏飞，扈 鹏

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

无人机编队飞行时，可由控制站作为中心，通过定向天线与无人机交换遥控遥测信息。提出一种适用于有中心定向网络的动态时分信道接入机制，在没有同步装置时，结合异步、同步2种邻居发现算法进行邻居发现。动态分配信道，对不同优先级业务提供服务质量（QoS）保障，提高时隙利用率；能够实现空间复用，解决定向天线存在的队列头阻塞问题，提高空间复用效率，很大程度上改善网络性能。在EXata网络仿真平台上进行了仿真验证，仿真结果表明，该算法能够有效提高网络吞吐量，降低时延。

定向网络；动态时隙分配；邻居发现；空间复用；队列头阻塞；网络仿真

0 引言

近年来，对于定向天线在无线网络中应用的研究越来越受到重视［1－3］，相对于全向天线，定向天线将传输能量集中在有限波束宽度的方向上，因此具有很多优势，具体表现为可以扩大通信范围，减少网络通信的跳数，降低延迟；降低发射功率；由于具有方向性，能够提高抗干扰、低截获的能力；提供空间复用能力。同时定向天线也带来一些问题，如新的隐藏终端、暴露终端、聋节点、邻居发现以及队列头阻塞的问题［4，5］。对于定向无线网络信道接入控制机制性能，学术界进行了广泛研究。重点主要集中在解决聋节点、邻居发现和空间复用等方面［2，6－9］。文献［6］提出了一种D-MAC定向信道接入协议，该机制基于IEEE 802.11 MAC协议。D-MAC协议使用全向—定向混合天线模式，假设网络内邻居节点的地址信息可知，而且全向天线与定向天线具有相同的天线增益。文献［9］提出一种基于忙音的定向接入机制，使用波束切换天线，利用RTS/CTS以及2个带外窄带忙音来避免冲突，并且增大空间复用率，从而提高网络容量。文献［10］提出一种纯定向的接入机制DTRA，节点通过3次握手完成邻居发现，并在预约时隙到来时发送数据。根据网络中的节点是否已经同步，可以将邻居发现算法分成2类：同步发现算法［11－13］和异步发现算法［14－17］。本文提出一种适用于有中心的定向网络信道接入机制（D-DTDMA），中心采用异步邻居发现，并为网络中业务进行动态时隙分配，提供区分优先级业务的QoS保证以及空间复用能力，解决定向网络队列头阻塞问题。

1 定向动态时分多址接入机制

1.1 D-DTDMA算法描述

本文使用理想的波束切换天线模型，将天线分为6个扇区，每个波束宽度均为60°，每次只有一个扇区可以进行通信，其余扇区方向天线增益与主瓣增益相比为可忽略的值。天线可以定向发送或接收，但是不能同时进行发送和接收。天线模型如图1所示。

图1 理想波束切换天线模型

该协议将时间分为若干不定长时帧，时帧分为中心邻居发现、普通邻居发现、业务请求、时隙分配和数据传输5个阶段。每个阶段分为很多子时隙，其中各阶段子时隙数可以根据实际情况进行动态配置。

为了提高网络性能并保证网络健壮，邻居发现阶段每隔一段时间进行一次。网络协议结构图如图2所示。

图2 定向网络结构示意

1.1.1 中心邻居发现阶段

中心邻居发现开始后，中心节点天线在每个扇区方向上停留（M＋1）个子时隙，M为扇区个数，每个子时隙长度为：

式中：tHoneIn为HoneIn帧的传输时间；ttrans为消息的传播时间；tguard为保护间隔。其他节点天线在每个扇区方向停留1个子时隙，等待接收HoneIn帧。

中心节点在每个子时隙开始时发送HoneIn帧，包括发送扇区号和剩余HoneIn帧个数x。收到HoneIn帧的节点停止搜索，并设定定时器长度为x∗t。HoneIn进程示意图如图3所示。

图3 HoneIn进程示意

节点A在S2方向收到中心节点扇区1发的HoneIn帧，停止搜索，并开启定时器T1；节点B也在某时刻收到HoneIn帧，停止搜索并开启定时器T2。

该进程结束后，进入Hello-Reply阶段，如图4所示。当邻居节点收到第1个Hello帧，任意选择一个时隙应答Reply帧，包括自身节点号和通信扇区号。节点B、D同时选择时隙1进行应答，则碰撞（用阴影表示）；而节点A、C分别选择时隙0和时隙s应答。第1轮Hello-Reply结束后，中心节点发现节点A、C。在第2轮中，中心节点Hello帧中包括已发现的A、C节点号，这使得B、D在第2轮入网的概率增大。

图4 Hello-Reply过程示意

之后在剩余M－1个扇区方向都重复上述过程。因此完成Hello-Reply过程的时间为：

式中，tHello和tReply分别为Hello时隙和Reply时隙的持续时间。

1.1.2 普通邻居发现阶段

在中心邻居发现过程中，各节点使用TPSN算法［18］以中心节点时间为基准进行全网络时间同步。因此普通邻居发现阶段可以使用同步发现算法使其他各个节点完成相互发现，记录自身与其他节点的通信扇区图。将本阶段分为（N－1）∗M个子时隙，其中N为网络中总节点数，M为每个节点天线的扇区数。该阶段接收节点天线方向和发送节点天线方向始终相反，如图5所示。

图5 同步算法天线扫描示意

各节点根据自身节点号依次进行邻居发现。在每次扫描时隙开始时，发送节点按照预定的方向序列发送发现消息，而其他节点根据规定在各方向上等待发现消息。当接收到发现消息后，将发送节点的节点号和通信扇区号存入链表。

1.1.3 业务申请阶段

该阶段分为（N－1）个子时隙，中心节点根据邻居发现结果，可以得知其他节点的方向。其他节点计算自身要发送数据的优先级和数量，根据节点号在自身相应时隙中向中心节点发送请求，包括自身节点号和业务的目的节点号，业务的优先级和数量，以及自身与其他节点的通信扇区表。中心节点则将天线对准相应节点，等待接收请求。

若节点需要退网，则在自身时隙到来时，发送退网请求，中心节点在时隙分配阶段应答退网请求，则退网成功。

1.1.4 时隙分配阶段

时隙分配阶段在网络时帧的分配时隙内完成，该阶段分为（N－1）个时隙。在该阶段内，中心节点根据请求链表中存储的网络中各节点的时隙请求、业务优先级信息，对本网络时帧中的数据子时隙进行分配，为网络中的各优先级业务提供QoS保障，并且根据网络节点通信扇区表计算空间复用情况，分配方法见1.2节。数据子时隙分配完毕后，中心节点将网络中节点总数量、当前网络时帧内数据子时隙的总数量及各节点的时隙分配情况等信息写入数据时隙分配帧，中心节点在每个邻居节点对应时隙到来时，将天线对准该节点，发送业务时隙分配结果。

1.1.5 数据发送阶段

网络中的各无人机节点在接收到中心无人机节点广播的数据时隙分配帧后，从数据时隙分配帧中获取当前网络时帧内的总数据子时隙数及自身分配到的数据子时隙信息。各无人机节点等待自身分配到的数据子时隙到来时向网络中的其他无人机节点发送自身的数据分组。此阶段可进行空间复用。各个数据子时隙内的数据分组传输完成后，当前网络时帧结束。由于邻居发现阶段开销很大，因此，本机制中设置每隔一段时间才进行一次邻居发现。

1.1.6 队列头阻塞问题

使用定向天线会有队列头阻塞的问题，即由于网络层业务队列采用的是先进先出的模式来进行发送，对于全向天线，这种方式是可以接受的，但是对于定向天线模式，则会造成头阻塞问题。这是因为定向天线，某些方向上的信道可用，而其他方向不可用，如果队列中的第一个数据包的发送方向被阻塞，即使之后的数据包的发送方向可用，也不能进行发送。如图6所示，节点A与B、C、D进行通信。节点A的业务队列中顺序排列着发送给节点B、C、D的数据包。如果节点B和节点E正在通信，节点A必须等到节点B和节点E的通信完毕之后才可以发送。对于全向网络，这种机制是合理的，因为节点A发送的数据可能会影响到节点B和节点E之间的通信。但是在定向天线网络中，节点A可以先安排向节点C发送数据，而不需要等待节点B通信完成，从而增加空间复用，提高系统容量，减小时延。

图6 队列头阻塞问题

若解决该问题，可以在很大程度上提高网络中空间复用的效率，从而进一步改善网络性能。在本文提到的机制中，提出了一种解决头阻塞问题的方案：在业务申请时隙中，各节点查询自身网络队列中的业务，将自身要发送的数据和在队列中的顺序发送给中心节点。中心节点计算空间复用时，可以轮询各个节点的请求，若当前各节点队列队首数据包均不满足空间复用条件，则查询下一个包是否满足，依次类推直到找到能够进行空间复用或到最后一个包为止。

之后将分配情况发送给各节点后，各节点根据分配情况，首先将包从队列取出，并在MAC层重新组成新的队列，使其可以解决头阻塞，尽量的满足空间复用，提高网络吞吐量。

由上述讨论可知，D-DTDMA具有以下优势：

①组网协议根据网络中节点的业务需求自适应的调整网络时帧的长度，能够有效提高时隙利用率；

②中心节点根据网络中各节点业务的优先级完成网络时帧中数据子时隙的动态分配，能够为网络中的不同优先级业务提供QoS保障；

③提供业务空间复用能力，提高网络吞吐量，改善网络性能；

④支持节点的入网和退网，能够满足网络规模动态变化的需求；

⑤解决了队列头阻塞问题，提高空间复用效率，进一步改善网络性能。

1.2 D-DTDMA时隙分配算法

中心节点在遍历请求链表后，计算业务请求的优先级和数量，根据以下算法进行区分优先级的数据时隙动态分配［19，20］。

①设置最大总数据时隙数以及各优先级最大数据时隙数，避免某一时帧过长，若有节点入网，会使得其入网时间变长。其中高优先级可分配的时隙数多于低优先级。这样既可保证高优先级业务的QoS，又能保证低优先级业务能够发送，兼顾公平性。

②计算总请求时隙数和各优先级时隙数，并分别与相应最大时隙数对比，选择其中小的为可分配的时隙数。若可分配的总时隙数大于各优先级可分配时隙数之和，则将剩余时隙按照优先级从高到低依次分配给各优先级。

③首先分配优先级高的业务时隙。判断当请求等于实际可分配的时隙数时，则按照请求的情况依次分配。若请求多于实际可分配的时隙数时，则首先给每个请求的节点分配一个时隙，保证其在本时帧中能够发送数据。再将剩余的时隙按照概率分配给各请求节点。

④同时根据通信扇区表判断是否有其他节点业务能够进行并发。判断标准为：若发送节点与并发发送节点在接收节点或并发接收节点的同一扇区，同时接收节点与并发接收节点在发送节点或并发传输节点的同一扇区，则不可并发，否则可以发起并发。

⑤之后再以同样方法分配其他优先级的数据时隙。

2 EXata网络建模仿真

EXata［21］是一款能够产生连接真实网络及应用的网络仿真软件，拥有一套综合体系工具来对有线及无线网络进行精确建模和预测。

2.1 仿真场景设置

仿真场景采用笛卡尔坐标系，仿真区域为水平35 km×35 km。设置各节点的传输距离为50 km，采用静态路由，传输层采用UDP协议，物理层采用DSSS模型，数据传输速率为2Mbps。仿真业务使用CBR，业务优先级由高到低分别为2、1、0，数据包长度为2 048 bytes。定向接入机制设置70个数据时隙。优先级2、1、0的业务可分配的最大时隙数分别为40、20、10。带宽为2 Mbps。仿真场景如图7所示。

图7 定向网络仿真场景

2.1.1 优先级业务仿真

场景如图7所示，节点1为中心节点，节点2～7每隔一段时间向节点1发送数据。节点2、3的业务为高优先级（优先级2）；节点4、5的业务为中优先级（优先级1）；节点6、7的业务为低优先级（优先级0）。网络性能与业务速率的关系仿真如图8和图9所示。

图8 网络吞吐量与业务速率关系

图9 端到端时延与业务速率关系

仿真结果表明，低负载时各优先级吞吐量和时延相差不大。随着网络负载量增加，在发包速率为10 Packets/s时，低优先级业务首先达到饱和，但是由于中、高优先级业务还没有达到饱和，因此剩余时隙可以分给低优先级业务进行传输；网络负载继续增加到18 Packets/s时，中优先级业务达到饱和，但高优先级业务未饱和，此时首先将剩余时隙分配给中优先级业务，而低优先级业务所分配到的时隙减少，吞吐量开始下降直至其饱和吞吐量。同理当网络负载逐渐增加到23 Packets/s，高优先级业务趋于饱和，剩余时隙逐渐减少，中优先级业务时隙减少，吞吐量也逐渐下降直至饱和。各优先级饱和吞吐量与设计的机制中为各优先级业务固定分配的时隙数有关。因此该接入机制能够提供不同优先级的QoS保证。

2.1.2 空间复用仿真

仿真场景如图7，设置2～6号节点以一定速率向中心节点1发送数据，节点7向节点6发送数据，其中节点7可分别与节点3、4、5实现资源复用。仿真并与不进行空间复用的机制对比结果如图10所示。

图10 空间复用与无复用的机制对比

仿真结果表明，本文设计的定向网络接入机制可以提供空间复用能力，有效地提高了网络性能。由图10（a）可知，无空间复用时，该接入机制饱和吞吐量大概为1.8Mbps，信道利用率为90%；而有空间复用时，由于当节点3、4、5向节点1发送数据时，节点7可以共用同一时隙向节点6发送，因此吞吐量可以超过2 Mbps，信道利用率大于100%。理想情况下，每个数据时隙都可以允许2对节点同时传输，因此，理想饱和吞吐量为无复用时的2倍。而由于可以复用，业务获得信道接入的概率增大，则在队列中等待的时间变小，从而也使得时延变小。

2.1.3 头阻塞问题仿真

针对上述提出的队列头阻塞问题，本文的定向网络接入机制提出了解决方案，并对该方案进行了仿真验证。场景设置如图7，业务配置为节点2～7以10 Packets/s速率向中心节点1发送数据，节点7变速率分别向节点5、6发送数据。仿真结果如图11所示。

图11 头阻塞问题仿真结果

仿真结果表明，解决头阻塞问题之后，网络吞吐量和时延性能均有改善。这是由于虽然节点7向节点5发送数据时可以和节点3、4并发，向节点6发送数据时可以和节点3、4、5并发，但是由于节点7的数据队列中数据包的目的节点依次为节点1、节点5和节点6。而向节点1发包的同时，其他节点没有能进行并发的业务，因此，节点7需要等到向节点1发完数据之后才能依次向节点5、6发包，这就导致了一定的资源浪费，降低网络性能。解决头阻塞问题后，节点7检测到头包不满足并发条件时，可以查找之后的包是否可以并发，将队列中的包取出重新排队发送，从而提高空间复用的效率，改善网络性能。

3 结束语

本文提出的算法综合异步邻居发现和同步邻居发现算法，实现在无同步装置情况下尽可能快地进行邻居发现。信道时隙分配可根据网络中的业务需求，利用较小的控制开销，动态调节时帧长度，在有突发业务时，保证较大的网络吞吐量和较小的平均时延；提供业务空间复用能力，并解决定向网络存在的头阻塞问题，极大地提高了网络吞吐量，改善网络性能；在支持不同优先级业务QoS的同时，保证一定的发送公平性；可以支持多节点的无冲突入网退网。

该项研究可以提高定向网络的传输效率，改善网络性能，对于组网技术发展具有指导和验证的意义；可以提高飞行器编队的高效协同组网能力，实现空战向基于战场信息共享网络的多机协同作战模式的转变，为天空地一体信息化作战体系及现代网络中心战的实现提供新概念、新技术和新方法。

［1］ 丁艳荣.基于定向和全向天线的混合式无线Ad hoc网络中MAC协议的研究［D］.长沙：国防科学技术大学，2011.

［2］ RAGHAVENDRA S C S.Capacity Bounds for Ad-Hoc Networks Using Directional Antennas［C］∥IEEE Inter-national Conference on Communications，Anchorage Alaska.USA，2003：349－352.

［3］ WANG Yang，LIU Bo，GUI Lin.Adaptive Scan-based A-synchronous Neighbor Discovery in Wireless Networks U-sing Directional Antennas［C］∥Wireless Communications and Signal Processing（WCSP），International Conference on.2013：1－6.

［4］ 郝 东.无线Ad Hoc网络定向接入与空间复用机制设计［D］.北京：北京邮电大学，2013，15－17.

［5］ VINAY K，SAMEER T，ABU-GHAZALEH N.Avoiding Head of Line Blocking in Directional Antenna［C］∥Proc. of the 29th IEEE International Conf.on Local Computer Networks，2004：1－8.

［6］ KO Y，SHANKARKUMAR V，VAIDYA N H.Medium Ac-cess Control Protocols Using Directional Antennas in Adhoc Networks［C］∥IEEE INFOCOM 2000，2000：13－21.

［7］ RAMANATHAN R.On the Performance of Ad Hoc Net-works with Beam forming Antennas［C］∥The Second ACM Symposium on Mobile Ad Hoc Networking and Com-puting（MobiHoc＇01），Long Beach，CA，USA，2001：95－105.

［8］ CHOUDHURY R R，YANG X，VAIDYA N H，et al.Using Directional Antennas for Medium Access Control in Ad Hoc Networks［C］∥ACM MobiCom，New York，USA，2002：59－70.

［9］ HUANG Zhou-chuan，SHEN Chien-Chung，CHAVALIT S，et al.A Busy-tone Based Directional MAC Protocol for Ad Hoc Networks［C］∥IEEE MILCOM，California，2002：456－459.

［10］ ZHANGZ.Pure Directional Transmission and Reception Algorithms in Wireless Ad Hoc Networkswith Directional Antennas［C］∥IEEE ICC，2005：3 386－3 390.

［11］ VASUDEVAN S，KUROSE J，TOWSLEY D.On Neighbor Discovery in Wireless Networkswith Directional Antennas［C］∥The 24th Annual Joint Conference of the IEEE Computer and Communications Societies（INFO-COM2005），USA，2005：2 502－2 512.

［12］ ZHANG Zhen-sheng，LIBo.Neighbor Discovery in Mobile Ad hoc Self-Configuring Networkswith Directional Anten-nas：Algorithms and Comparisons［J］.IEEE Transactions on Wireless Communications，2008，7（5）：1 540－1 549.

［13］ LIU B，RONG B，HU R Q，etal.Neighbor Discovery Algo-rithms in Directional Antenna Based Synchronous and Asynchronous Wireless Ad Hoc Networks［C］∥Wireless Communications，IEEE，2013：106－112.

［14］ 赵瑞琴，刘增基.采用定向天线的MANET邻居发现算法研究［J］.天线与伺服技术，2006，32（4）：30－33.

［15］ 赵瑞琴，文爱军，刘增军，等.有效支持智能天线的MA-NET邻结点发现算法与分析［J］.西安电子科技大学学报，2007，34（3）：342－347.

［16］ ZHANGZ.Directional Transmission and Reception Algo-rithms in WLANs with Directional Antennas for QoSSup-port［C］∥IEEE Network，USA，2005：27－32.

［17］ FELEMBAN E.SAND：Sectored-Antenna Neighbor Dis-covery Protocol for Wireless Networks［C］∥7th IEEE SECOM，2010：l－9.

［18］ GANERIWAL S，KUMAR R，SRIVASTAVA M B.Timing-sync Protocol for Sensor Networks［C］∥Proceedings of First Int Conf on Embedded Networked Sensor Systems，Los Angeles，Califomia，2003：138－149.

［19］ 王宝玺，文运丰，马鹏飞，等.一种适用于自组织网的动态时隙分配算法［J］.无线电工程，2014，44（10）：47－51.

［20］ 常 扬，陈建民，马鹏飞.高速无人机网络MAC协议设计与性能分析［J］.无线电工程，2011，41（3）：23－26.

［21］ 商英俊，黄 伟，贾慧英.动态TDMA接入协议仿真分析［J］.无线电通信技术，2011，37（3）：23－25.

A Dynamic-TDMA MAC Mechanism for Directional Networks with a Central Node

WANG Baoxi，WEN Yunfeng，MA Pengfei，HU Peng
（The 54th Research Institute of CETC，Shijiazhuang Hebei 050081，China）

Using directional antennas，control station can act as a central node and exchange remote information with UAV fleet during the flight.The paper proposes a Dynamic TDMA（DDTDMA）MAC mechanism for directional networks without synchronous equipment，which combines asynchronous and synchronous neighbor discovery algorithms.DDTDMA implements a dynamic slotassignment algorithm，which provides QoS for traffics of different priorities，and has a high utilization of slot.It also realizes spatial reuse and solves the“headofline blocking”problem，obtaining a better network performance.Simulations on the Exata network simulation platform show that the algorithm can significantly increase the network throughput and reduce the delay.

directional network；dynamic slot assignment；neighbor discovery；spatial reuse；head-of-line blocking；network simu-lation

TN929.5

A

1003－3106（2015）09－0024－06

10.3969/j.issn.1003－3106.2015.09.07

王宝玺，文运丰，马鹏飞，等.一种定向网络动态时分信道接入机制［J］.无线电工程，2015，45（9）：24－29.

王宝玺男，（1990—），硕士研究生。主要研究方向：飞行器测控技术、移动自组网通信。

2015-05-20

国家部委基金资助项目。

文运丰男，（1966—），研究员。主要研究方向：遥控遥测通信、移动自组网。