引用本文
刘强, 郝琦, 欧阳峰. 基于定向天线的移动自组网接入控制协议[J]. 北京交通大学学报, 2017,41(2): 72-78.
LIU Qiang, HAO Qi, OUYANG Feng. A media access control protocol of MANETs based on directional antenna[J]. JOURNAL OF BEIJING JIAOTONG UNIVERSITY, 2017,41(2): 72-78.
Doi:10.11860/j.issn.1673-0291.2017.02.012  
Permissions
Copyright©2017, 《北京交通大学学报》编辑部
版权所有 © 2017 《北京交通大学学报》编辑部
基于定向天线的移动自组网接入控制协议
刘强1, 郝琦1, 欧阳峰2
1.北京交通大学 计算机与信息技术学院,北京100044
2.国家新闻出版广电总局 广播科学研究院,北京100866

第一作者:刘强(1980—),男,江苏南京人,讲师,博士.研究方向为移动自组网.email:liuq@bjtu.edu.cn.

收稿日期: 2016-08-04
基金: 国家自然科学基金(61572220)
摘要

移动自组网使用全向天线进行数据传输时,会产生信号干扰严重和网络收敛较慢等缺陷,为了克服这些缺陷,本文提出了一个基于定向天线的移动自组织网(MANETs)接入控制协议(DAND-MAC).本协议可以统一协调定向天线与全向天线同步工作,全向天线进行拓扑发现和邻居监控,定向天线用于链路建立和数据传输.详细分析了DAND-MAC协议系统结构、关键技术和核心算法,使用OPNET Modeler进行网络仿真建模.仿真结果表明:该协议相比传统的静态时隙分配协议和全向天线动态时隙分配协议,DAND-MAC在端到端延迟、吞吐量和时隙利用率等网络性能上有显著的提升.

关键词: 移动自组网; 定向天线接入控制协议; 无线资源管理; 定向天线
中图分类号:TP393.1 文献标志码:A 文章编号:1673-0291(2017)02-0072-07
A media access control protocol of MANETs based on directional antenna
LIU Qiang1, HAO Qi1, OUYANG Feng2
1.School of Computer and Information Technology, Beijing Jiaotong University,Beijing 100044, China
2.Academy of Broadcasting Science, State Administration of Press, Publication, Radio, Film and Television of China, Beijing 100866, China
Fund:National Natural Science Foundation of China (61572220)
Abstract

A dynamic media access control protocol named DAND-MAC(Directional Antenna Neighbor Discovery and Media Access Control) is presented,which is designed to operate in the link layer of Mobile Ad-hoc Networks(MANETs) based on directional antenna. Omnidirectional antenna and directional antenna can operate synchronously with the unified scheduling of this protocol.Omnidirectional antenna takes the charge of topology and neighbor discovery, while directional antenna processes to build the link and the transmit data. This paper describes the system structure, key techniques of DAND-MAC. The simulations are operated with OPNET Modeler. The simulation results show that the performance of DAND-MAC could increase significantly in end-to-end delay,throughput and the reusability of time slots,comparing with traditional static time slot allocation and dynamic time slot allocation based on omnidirectional antenna.

Keyword: mobile ad-hoc networks; directional antenna neighbor discovery and media access control protocol; radio resource management; directional antenna

随着计算机和无线通信技术的发展, 产生了具有无中心基站和支持多跳通信等特点移动自组织网络(MANETs)[1].它可以在任何时刻, 任何地点快速构建起一个通信网络, 在这个网络中每一个节点地位平等, 可以自由移动[2].同时网络中任何一个节点的损坏、移动和脱网, 均不会使整个网络瘫痪.由于这些特性, 移动自组网可以广泛的应用在战场通信和抢险救灾等领域.

近年来, MANETs的相关技术吸引了大量来自学术界和无线通信产业的关注, 有力推动了该技术的标准化和快速的商业化[3].为了提高移动自组网的链路容量和资源重用率, 定向天线技术也在移动自组网的领域得到广泛的研究和应用[2, 3, 4].

本文作者提出了DAND-MAC协议, 该协议是一种基于定向天线, 可协调定向天线和辅助全向天线协同工作的MANETs接入控制协议; 具有网络开销少、延迟低、时隙复用率和传输速率高的特点.

1 国内外研究现状

移动自组网中接入访问控制协议(Media Access Control, MAC)是其基础协议和支撑技术, 很大程度上决定了该网络的性能.

目前, MANETs接入控制协议一般可分为固定分配和动态分配两种模式.固定分配又可以分为时分多址接入(TDMA)、频分多址(FDMA)和码分多址接入(CDMA)等.动态分配协议主要分为竞争型接入、预约型接入和轮询型接入[5], 相应典型的协议有载波侦听多址接入协议(CSMA)、统一动态时隙分配协议(USAP)和基于轮询机制的接入控制协议(Polling_based MAC Protocol)等.不同的协议适用于不同的自组网业务类型和应用背景, 具体分析如表1所述.

表1 不同类型接入控制协议对比 Tab.1 Comparisons of different MAC protocols

在多节点重负载情况下, TDMA比CSMA效率更高、冲突较少, 因此在移动自组网中TDMA接入协议得到了广泛应用[6].国内外进行了大量针对预约型动态时隙分配的研究, 文献[7]提出了基于两跳之外时隙重用思想的统一时隙分配协议.在该协议中, 允许网络节点的时隙分配出现暂时性的冲突, 并提供了完备的冲突检测和解决方案.任何节点可以根据获取到的以本节点为中心两跳内的信息, 进行对空闲时隙的占用申请声明, 当该节点收到其他所有一跳邻居节点的确认后, 就能成功占用和使用该时隙.此后, 文献[8, 9]又进一步优化了USAP.相比固定时隙分配协议, USAP显著提高了网络资源利用率, 提高了整个网络的吞吐量.虽然USAP使移动自组网的性能得到了显著提升.但是它本身也具有明显的缺陷和不足:1)网络状态收敛速度特别慢, 无法适应复杂地形和拓扑变化相对剧烈的场景.2)每个节点状态信息更新不及时, 导致申请时隙冲突较多, 无形中增加了网络开销和延迟.3)节点间通信传输速率较低, 通信距离较近, 相互之间干扰较多.

随着近年来移动通信业务需求的快速增长, 传统自组网的这些缺陷也愈发明显, 性能逐步受到限制, 造成这种限制的主要因素就是传统移动自组网使用全向天线进行数据收发.

定向天线的使用可以有效的解决这一问题, 它可以为无线网络带来许多特性[10]:1)邻居节点间的干扰将大大减少, 从而提升邻居间和整个网络的在同一时刻的传输能力; 2)更高的定向增益和信噪比, 可以有更高的数据速率; 3)相同的发送功率下, 定向天线的通信距离能够极大的延长; 4)由于单跳传输距离的增加, 使得在源节点到目的节点之间距离一定的情况下, 数据包可以通过更少的转发次数从源节点转发达到目的节点, 从而减少数据包延迟.

文献[11]提出定向天线邻居发现协议(SAND Protocol)可以保证链路两端使用最合适的定向天线, 从而使节点间维护更高质量和更好鲁棒性的链路.但是该协议没有加入全向天线的支持, 导致邻居发现需要节点的定向天线进行扫描, 两次握手过程异常复杂, 不适合网络拓扑变化较快的应用场景.文献[12]提出了一个较快的邻居发现算法, 基于轮询机制的接入控制协议.但是该协议采用了随机接入的方式, 并不能保证每个节点探测到的拓扑结构与实际拓扑结构完全一致.

可以看出, 目前基于定向天线的MAC协议在收敛速度、邻居发现和资源重用等方面还存在诸多亟需改进的地方.

本文作者提出了一种基于定向天线的接入控制协议.该协议通过全向天线辅助, 可以快速地进行邻居发现和拓扑控制, 定向天线可以高效进行链路建立和数据传输.DAND-MAC既节省了定向天线的开销, 又可以保证节点可以快速地完成邻居发现和接入控制的任务.在相同能耗下, 本协议可以有效提高传输速度和通信距离, 提高整个网络的性能.

2 DAND-MAC协议设计

本文以加快网络收敛速度, 提高吞吐量为设计目标, 提出了DAND-MAC协议, 该协议包括邻居发现、链路建立、资源管理和冲突检测4个主要部分, 该协议具有高速的单播能力和一定的广播能力.同时, DAND-MAC不仅要协调全向天线和定向天线工作, 完成TDMA信道接入任务, 还要承担无线资源管理和邻居监控等功能.

2.1 系统结构

DAND-MAC协议的物理层由一个全向天线和n个具有扇形增益的定向天线组成, 扇形角度为α , 则满足

n=2πα(1)

全向天线进行拓扑控制和数据广播, 定向天线进行链路建立和数据单播, GPS进行全球定位和同步授时, 协议的系统结构如图 1所示.

图1 DAND-MAC协议系统结构Fig.1 System structure of DAND-MAC protocol

2.2 关键技术和核心算法

DAND-MAC是在无线资源的动态管理和时隙一跳外复用思想的基础上, 引入定向天线空分技术后设计的.在DAND-MAC协议运行过程中, 时间被分为多个连续重复的时元(Epoch), 全向天线信道和定向天线信道分别具有不同的时元结构.

2.2.1 邻居发现

在移动自组网中, 每个节点的位置都允许不断的变化.因此, 每个节点需要及时获取正确的邻居状态信息.DAND-MAC协议使用全向天线完成网络中邻居发现和广播任务, 如图 2所示.

图2 全向信道时元结构Fig.2 Circle of OMNI channel

在邻居发现帧中, 每个节点拥有一个固定时隙来发送自己的HELLO包.包中有源节点ID(OID)、源节点的位置坐标( Ox, Oy, Oh).当该节点的一跳邻居接收到HELLO包后, 会根据自己的位置信息( Selfx, Selfy, Selfh)和收到的源节点信息, 计算出与源节点使用定向天线通信时的方位角α 和俯仰角β , 如图 3和图 4所示.

图3 定向天线方位角计算示意图Fig.3 Azimuth calculation of the directional antenna

图4 定向天线俯仰角计算示意图Fig.4 Pitch calculation of the directional antenna

计算方法如下

α=arctanOy-SelfyOx-Selfx(2)β=arctanOh-SelfhOx-Selfx2+Oy-Selfy2(3)

此外, 广播时隙可以用来发送网络层路由信息等广播业务.

2.2.2 链路建立

本文假设定向天线具有极窄或者近似于零的波束宽度, 发送节点发送的信息只能被它的目的节点接收, 在这种情况下, DAND-MAC的时隙分配算法可用图论中的边着色来解决, 移动自组网着色示意图如图5所示.

图5 移动自组网着色示意图Fig.5 Mobile ad-hoc network coloring schemes

边着色的思想来对链路进行时隙分配, 对每条链路进行着色, 以此来表示时隙被分配给对应链路.如图 5所示, 圆圈代表移动节点, 每条边上的数字代表图论中不同的着色编号, 对应DAND-MAC协议中该条链路申请的时隙号.一个节点不能有多于一个标记相同颜色的链路.由于定向天线的空间分隔性, 一跳外的链路可以用相同的颜色着色, 实现时隙的一跳复用, 从而大大增强网络容量.这意味着给一个节点的链路着色, 要受到该节点其他链路颜色和该链路目的节点的每个链路着色的约束, 且移动自组网拓扑图不存在环边, 存在 N个移动节点的图, 必有 Δ(G)< N根据图论中的VIZING定理[13]

Δ(G)≤χ'G≤Δ(G)+1(4)

因此, 当数据时隙数 M满足N≤M, 当采用合适的时隙分配算法, 就可以满足, 在最极端情况下, 每个节点最少也能分配一个数据时隙.

如图 6所示, 每个节点分有一个固定的用于建立链路的时隙(B-Slot).对于最大支持 N节点的网络, 拥有N个B-Slot, 并且每个B-Slot又由 N个微时隙组成, 每个节点占用自己B-Slot的第K个微时隙与K节点进行建链操作.数据帧有M个数据时隙(Data-Slot), 每个Data-Slot分为两段, 当节点A和节点B占用Data-Slot通信时, 前一段由节点A向节点B发送数据, 后一段, 由节点B向节点A发送数据, 当节点A、B业务量相差较大时, 前后两段也可以由同一节点单向占用.

图6 定向信道时元结构Fig.6 Circle of directional channel

2.2.3 资源管理

DAND-MAC协议资源管理分为时隙申请和时隙释放两个部分.时隙申请过程和时隙释放过程, 通过节点双方占用建链时隙交互BLReq、BLResp、RSReq和RSResp数据包来完成.数据包所含主要字段如表2所示.

表2 数据包主要字段及其含义 Tab.2 Main meaning of the fields in packets

当ID为 i的节点向ID为 j的节点发起时隙申请时.节点 i占用第i个B-Slot的第j个微时隙的前一半时间给节点j发送Build_Link_Requset(BLReq).BLReq包含了本节点当前时刻Data-Slot的占用情况和该节点期望申请的Data-Slot数量 S1; 当节点 j收到这个来自节点 i的BLReq包后, 节点j立刻占用第i个B-Slot的第j个微时隙的后一半时间返回给节点i一个Build_Link_Response(BLResp) , BLResp包含节点 j当前的时隙占用情况和期望申请的Data-Slot数量 S2.至此, 两个节点均知道了双方时隙占用情况, 双方用同一种策略从共同的空闲时隙中选择 (S1+S2)个时隙.

当空闲数量足够成功申请(S1+S2)个时隙时, 节点i占用前S1个空闲时隙, 节点j占用后S2 个空闲时隙.当空闲时隙只剩S(S< S1+Sj)个时, 由于每个数据传输时隙分为两部分, 该链路两个节点申请到半个时隙的个数Yi 和Yj分配策略如下:

X1=⌊S1∑k=12Sk·2S(5)X2=⌊S2∑k=12Sk·2S(6)Y1=1, X1=02S-1, X1=2SX1, 其他(7)Y2=1, X2=02S-1, X2=2SX2, 其他(8)

业务量减少, 节点占用时隙数远大于实际需求数或者当业务压力繁重, 需要为高优先级节点提供更多时隙时, 节点可以动态释放时隙, 以便于其他业务繁忙的节点占用时隙.

当节点 i和节点j之间的链路需要释放时隙时, 节点 i占用第i个B-Slot的第j个微时隙的前一半时间给节点j发送一个RSReq, RSReq包含了本节点当前时刻Data-Slot的占用情况和该节点期望释放的Data-Slot数量 S1, 当节点j收到这个来自节点i的RSReq后, 节点j立刻占用第i个B-Slot的第j个微时隙的后一半时间返回给节点i一个自己RSResp, RSResp包含节点 j当前的时隙占用情况和自己期望申请的Data-Slot数量 S2.双方用同一种策略从共同的占用时隙中选择 (S1+S2)个时隙释放.

2.2.4 冲突检测

在本算法中, 当节点需要建立链路或申请释放时隙时, 双方会交互各自最新的时隙占用表, 因此只要数据包没有丢失, 就不会出现类似与USAP算法的相关冲突.唯一需要注意的是Build_Link包丢失的情况.

当从源节点到目的节点发起建立链路的BLReq丢失时, 目的节点没能收到BLReq默认源节点本时元内没有申请新的时隙, 并且不返回自己的BLResp.源节点没能接收到目的节点返回的BLResp, 也认为此次申请失败, 双方各自信息依然符合实际状态, 冲突在一帧内可以被消除, 如图 7所示.

图7 BLReq丢失时冲突解决方案Fig.7 Collision resolved method when BLReq lost

当从源节点到目的节点发起建立链路的BLReq成功到达, 但返回的BLResp丢失时, 源节点默认申请失败, 而目的节点默认申请成功, 这时会发生冲突.目的节点在该循环内要监测源节点是否使用其申请的时隙, 如果没有用, 则在该循环内链路申请的时隙是都不能使用的, 包括网内其他一跳链路也不能用.同时在下一帧, 源节点声明在上次循环内与目的节点申请的时隙失败, 目的节点收到后释放冲突的时隙.至此, 冲突可在两帧内解决, 如图8所示.

图8 BLResp丢失时冲突解决方案Fig.8 Collision resolved method when BLResp lost

3 仿真与性能分析
3.1 仿真模型

在OPNET仿真平台中, 将本文介绍的DAND-MAC协议分别与标准USAP协议和传统的静态时隙分配协议(TDMA)进行对比.仿真场景均为32个移动节点随机分布在100 km × 100 km的区域内, 每个节点的一跳通信距离为15 km, 底层数据速率2 000 kbps.其他物理层参数均保持一致.本文对网络延迟、吞吐量和时隙复用率等网络性能仿真的拓扑如图 9所示, 图中圆点为移动终端节点, 节点周围的小圈代表节点的小组定向天线, 节点间的连线代表两个节点间加载了通信业务.

图9 仿真拓扑结构Fig.9 Topological graph of simulation

在此基础上, 对网络加载相同负载的IP业务流进行了多组仿真.分别对时隙复用率、吞吐量、丢包率和延迟等网络性能参数进行了对比.

时隙复用率 η计算方法如下

η=∑i=1NOSNiMmax(9)

式中:N为网络中节点数; OSNi为第i个节点用的时隙数量; Mmax为一个时元中数据时隙的总数.

同时, 对不同数量的扇形天线, 即每个扇形天线角度大小对协议性能的影响也进行了仿真和分析, 如图 10所示, 图10中粗线代表节点移动轨迹.

图10 仿真拓扑结构节点移动轨迹Fig.10 Movement path of topological graph

3.2 仿真结果及分析

1)端到端延迟.对DAND-MAC、USAP和传统TDMA协议网络加载128 kbps的IP业务流时, 全局端到端延迟的统计如图11所示.DAND-MAC协议最初需要根据业务量来计算并分配时隙数量, 因此刚加载业务时延迟出现了一定的抖动, 但很快变趋于稳定, 且明显小于0.2 s.USAP也加载128 kbps的IP业务流时, 端到端延迟也随着缓存队列的增长而增长, 最终收敛在0.5 s左右, TDMA协议无法对时隙重用, 因此每个节点分配到的时隙有限, 当TDMA协议也加载128 kbps的IP业务流时, 业务量远大于节点发送能力, 缓存队列不断增长, 直到缓存耗尽, 端到端延迟约为5.5 s, 与DAND-MAC协议有明显差距.

图11 DAND-MAC、USAP和TDMA协议全局端到端延迟Fig.11 End to end delay of DAND-MAC, USAP and TDMA

2)业务投递.对网络加载128 kbps的IP业务流时, DAND-MAC、USAP和传统TDMA业务投递情况的统计, 包括源节点发送量和目的节点接收量如图12所示.DAND-MAC和USAP协议只在时隙尚未分好时, 发送量和接收量有短暂的不吻合, 而TDMA由于能力限制, 在网络中出现大量因为无法及时发送而被抛弃的数据, 接收量远小于发送量.

图12 DAND-MAC、USAP和TDAM业务投递率对比Fig.12 Delivery rate of DAND-MAC, USAP and TDMA

3)吞吐量.对DAND-MAC、USAP和传统TDMA协议的吞吐量对比如图13所示.TDMA吞吐量约600 kbps, USAP略好于TDMA, 吞吐量达到了750 kbps, DAND-MAC性能明显好于USAP和TDMA, 网络整体吞吐量极大提升, 达到了900 kbps以上.

图13 DAND-MAC、USAP和TDMA协议吞吐量Fig.13 Throughput of DAND-MAC, USAP and TDMA

4)时隙复用率.对DAND-MAC、USAP和传统TDMA协议时隙复用率如图14所示.因为TDMA协议是静态的将所有时隙平均分给每一个节点, 所以其时隙复用率始终为1, USAP时隙复用率略好于传统TDMA, 而DAND-MAC协议支持一跳外的时隙重用, 在此仿真场景下, 统计每个节点时隙占用情况, 并根据式(9), 计算可得 η≈5, 和仿真结果基本吻合.

图14 DAND-MAC、USAP和TDMA协议时隙复用率Fig.14 Slot reuse rates of DAND-MAC, USAP and TDMA

5)定向天线角度的影响.对DAND-MAC协议受扇形天线角度大小影响的性能表现如图15所示.分别测试在随机移动场景下, 加载600 kbps业务量时, 10° 、15° 、30° 扇形天线正确接收的统计情况如图15所示的扇形角越大, 每次受到的干扰越严重, 但是受到干扰频率越低; 相反, 扇形角越小, 在移动过程中每次收受的干扰越轻微, 受到干扰的频率会相应增加.

图15 DAND-MAC性能受扇形天线角大小影响Fig.15 Influence of antenna’ s angle

4 结语

1)本文作者就移动自组网接入控制协议的现状, 分析了当前协议所存在的不足.引入定向天线技术, 设计了一个支持一跳外时隙重用的移动自组网接入控制协议DAND-MAC.

2)第3节从网络端到端延迟、业务投递率、吞吐量、时隙复用率和定向天线波束角度大小对网络影响5个方面对协议性能进行了对比和分析.仿真结果表明, DAND-MAC协议相比传统TDMA协议, 使得网络延迟降低90%, 网络吞吐量从550 kbps提升到900 kbps左右, 时隙利用率等性能也显著的提升, 根据仿真结果, 还进一步分析了定向天线波束角度对网络性的影响.

对于DAND-MAC协议, 目前还有一些因素未能考虑, 需要进行更进一步研究.接下来需要进一步优化时隙分配所占的开销, 提高申请或释放时隙的速度, 并且在保证效率的基础上支持更多数量的入网节点.

The authors have declared that no competing interests exist.

参考文献
[1] PERKINS C E. Ad hoc networking[M]. Boston: Addison-Wesley Professional, 2008. [本文引用:1]
[2] SWAMINATHAN A, NONEAKER D L, RUSSELL H B. The design of a channel-access protocol for a wireless ad hoc network with sectored directional antennas[J]. Ad Hoc Networks, 2012, 10(3): 284-298. [本文引用:2]
[3] BAZAN O, JASEEMUDDIN M. A survey on mac protocols for wireless adhoc networks with beam forming antennas[J]. Communications Surveys &Tutorials, 2012, 14(2): 216-239. [本文引用:2]
[4] 程楠, 刘志敏, 王继新. Ad Hoc网络TDMA 分布式动态时隙算法[J]. 计算机应用研究, 2005, 22(1): 222-225.
CHENG Nan, LIU Zhimin, WANG Jixin. TDMA-based distributed dynamic slot algorithm for Ad hoc networks[J]. Application Research of Computers, 2005, 22(1): 222-225. (in Chinese) [本文引用:1]
[5] 刘骁祖. 自组织网络MAC层随机接入设计与FPGA实现[D]. 成都: 电子科技大学, 2015.
LIU Xiaozu. Design and implementation with FPGA on rand om access in ad hoc networks MAC layer[D]. Chengdu: University of Electronic Science and Technology of China, 2015. (in Chinese) [本文引用:1]
[6] 陈曦, 张世祥, 田万勇, 等. 战术数据链时隙分配协议综述[J]. 电子科技, 2013, 26(4): 165-168.
CHEN Xi, ZHANG Shixiang, TIAN Wanyong, et al. A survey of slot assignment protocols for tactical data links[J]. Electronic Sci& Tech, 2013, 26(4): 165-168. (in Chinese) [本文引用:1]
[7] YOUNG C D. USAP: A unifying dynamic distributed multichannel TDMA slot assignment protocol[C]. Proceedings of IEEE MILCOM, 1996, 1: 235-239. [本文引用:1]
[8] YOUNGC D. USAP multiple access: dynamic resource allocation for mobile multihop multichannel wireless networking[C]. Proceedings of IEEE MILCOM, 1999, 1: 271-275. [本文引用:1]
[9] YOUNGC D. USAP multiple broadcast access: transmitter-and receiver-directed dynamic resource allocation for mobile, multihop, multichannel, wireless networking[C]. Proceedings of IEEE MILCOM, 2000, 1: 549-553. [本文引用:1]
[10] 王洋. 基于定向天线的无线Ad Hoc网络协议研究[D]. 上海: 上海交通大学, 2013.
WANG Yang. Research on wireless Ad Hoc network protocols using directional antenna[D]. Shanghai: Shanghai Jiao Tong University, 2013. (in Chinese) [本文引用:1]
[11] MURAWSKI R, FELEMBAN E, EKICI E, et al. Neighbor discovery in wireless networks with sectored antennas[J]. AD HOC Networks, 2012, 10(1): 1-18. [本文引用:1]
[12] JAKLLARI G, LUO W, KRISHNAMURTHY S V. An integrated neighbor discovery and mac protocol for ad hoc networks using directional antennas[J]. IEEE Transactions on Wireless Communications, 2007, 6(3): 1114-1124. [本文引用:1]
[13] DIESTEL R. Graph theory[J]. Mathematical Gazette, 2000, 173(1): 82-131. [本文引用:1]