基于TDMA和定向天线的无线Mesh网络广播技术

王 浩，吴礼华，周鹏程

(1.武汉第二船舶设计研究所，湖北 武汉 430000;2.武汉大学 电子信息学院，湖北 武汉 430000)

0 引言

无线Mesh网络[1]是一种特别的多跳无中心的自组织无线网络，广播在无线Mesh网络中是一种非常重要的通信方式，用于信息的全网发放，被广泛应用于应急和军事通信网络中。

目前传统无线Mesh网络广播过程大都是基于全向天线[2]结构与CSMA接入协议设计的[3]，但因为全向天线的能量不集中、消息冗余和冲突再加上CSMA接入方式的退避等待，导致广播过程中存在时延大、可靠性和信道利用率不高等问题。

许多学者对基于定向天线的广播算法展开研究，例如TREE-BASED算法[4]较好地减少了冗余，TDMA-NNI算法[5]采用预约广播包转发以避免冲突，BSRN算法[6]是基于概率和邻居信息的混合算法，提高了广播的可靠性。但他们都只针对某一性能指标进行改善，本文在微时隙划分的时分复用基础上采用适合多接口定向天线的空分复用，去优化广播的可靠性、时延、耗时及冗余率等性能指标，以提高广播过程的综合性能。

1 应用场景分析

随着信息化发展，在各种应急场景下，对于可快速部署的无线Mesh网络广播的应用急剧增加。图 1为某应用场景视图，此类场景中上级组织对下级组织广播实时命令消息，应具有较高的优先级，而下级节点之间又相互通信，节点间的距离较大且节点数量繁多。故在此类场景下的无线Mesh网络广播需考虑到以下几点：网络展开迅速、鲁棒性强、延时可控、较远的通信距离与较高的传输速率、传输可靠性有保障、成本较低。

目前使用较多的无线Mesh网络广播是基于全向天线的，采用CSMA接入协议，其优势在于时隙和信道的利用率较高，但CSMA的退避等待延时不可控会使广播的延时不确定性很大，这对于一些应急场景是很致命的。全向天线因为辐射范围广、功率不集中导致其传输距离和传输速率不够，且因为多节点使用全向天线发送消息会有较大的消息冗余和消息冲突，这些都会使广播过程的性能受到影响。

图1 应用场景视图Fig.1 Application scenario

本文采用TDMA接入协议结合定向天线，虽然在一些文献中提出这种组合以在原有基础上减少等待延时并提高通信距离和传输速率，但是因为TDMA只是按照规划地为各节点分配时隙，没考虑到实际场景，信道和时隙利用率不高。在邻居发现的时候，因为定向天线扇区波束较窄，邻居发现采用的轮流扫描一周的模式，天线的对准以及邻居发现的速度和完整性没有得到保障。

因此，采取微时隙划分的TDMA和在微时隙基础上使用的多接口定向天线。定向天线的多个接口同时工作实现空分复用以提高邻居发现速度，对各接口的天线进行更加精确地微时隙分配以避免冲突。在信道分配中对各网络节点和信道进行优先级划分，按需分配时隙和信道以提高其利用率。

2 基于多接口定向天线的邻居发现

2.1 多接口的定向天线

传统广播过程中使用的一般是全向天线，可以较为迅速地广播信息，但是由于全向天线辐射范围广，天线功率全向散布，能量不够集中，故其单跳传输距离不远。此外，多节点通过全向天线发布消息的时候会造成较大的消息冗余与消息冲突。定向天线虽然可以提升传输距离和传输速率，但是多个发送天线同时向一个接收天线发送消息时的冲突问题与天线扫描耗时问题也未得到较好的解决。

定向天线分为自适应阵列天线[7]与多波束转换天线[8]，前者设计天线精确度更高，可跟踪目标移动，但无线Mesh网络中节点相对静止，无需精确地跟踪节点位置，并且阵列天线结构复杂、成本较高，其兼容性不强。多波束转换天线使用多个并行的波束将节点四周覆盖，需要通信时切换到对应扇区即可，天线结构较简单，成本低，兼容性强。

本文在传统的多波束转换天线的基础上，为每个节点物理层配置多个接口，每个接口都有完整的协议栈，独立工作互不影响，其模型如图 2所示。采用多接口定向天线并结合TDMA可实现在空分复用的基础上进行时分，在后文对每个时隙结合角度划分到微时隙，以确保天线对准，一定范围内只有一个节点的多接口天线在不同的方向发送hello包，有效避免了冲突问题的同时提升了天线扫描速度。

图2 定向天线结构Fig.2 Structure of directional antenna

定向天线每个终端节点配置M个接口，每个接口控制N根天线，共配置K=M*N根定向天线。K根天线均匀覆盖360°范围。每根天线指向的波束角度是不变的，K的数值越大，则天线波束角度越小，能量越集中。

这种天线有如下限制：

① 不同接口上的定向天线可以同时工作，相同接口上的定向天线同一时刻只能工作一根。

② 同一时刻天线只能处于三种工作状态中的一种，分别为发送状态、接收状态、空闲状态，处于空闲状态的扇区既不发送也不接收信号。

2.2 邻居发现过程

本文的邻居发现过程在MAC层实现，重新设计了天线扫描方式，采取了更适用于多接口和微时隙的空分复用模式，将定向天线的发现方式选择为规划型方式，解决了发送hello包冲突问题，并且加快了邻居发现速度。

邻居发现过程实现在MAC层，MAC层更有利于控制天线状态以及节点占用信道的顺序。为了防止天线收发消息冲突，故邻居发现时应满足以下几个条件：

① 定向天线波束宽度很窄，一对邻居节点天线波束夹角需要满足如下公式才能互相通信。

θ=(θ′+π)mod(2π),

其中，θ′是发送节点天线方向的夹角，θ是接收节点天线方向的夹角，即θ′与θ相差180°。

② 由于节点是半双工的，节点需要确定当前时隙自己的状态。一对邻居节点的天线同一时刻要分别处于一发一收状态，才能正常通信。

③ 同一时刻不能有多个邻居节点朝一个节点同一波束范围发消息，会产生碰撞。

2.3 天线扫描和时隙分配

相较传统定向天线在各方向都扫描的轮流扫描方式，本文重新设计的天线扫描方式，让物理层配置的多接口同时工作，提升扫描效率的同时避免了冲突。

为网络中N个节点各自分配一个时隙，每个节点的n个接口上分别配有m根天线，则可将每个时隙分为m个微时隙，多个接口同时工作，时隙分配如图 3所示。

图3 邻居发现时隙分配图Fig.3 Time slot distribution diagram of finding neighbors

扫描过程以第一个节点发送hello包为例：在第一个时隙T(Id1，n(1,2,3，…，n),m1(a))发送hello包，其中T(Idi，nj，mk(a))表示第i个节点的第j个接口的第k根天线，a表示当前天线的角度，例如在第四个时隙，第一个节点的所有接口上的第4根天线处于发送hello包状态，T(Id(2,3,4,…，N),n(1,2,3，…，n),m(a+π))处于接收hello状态，如图4所示，其中第一个节点的3个接口上4、9、14号天线处于发送hello包状态，其他节点的11,12号、1,2号以及6,7号天线处于接受hello包状态。在第一个节点的4号天线波束范围内，节点a的11,12号天线可接收到hello包，节点b的12号天线可接收到hello包。

同理，第5个时隙第一个节点所有接口上的第5根天线处于发送hello包状态，其余节点所有接口上与第一个节点工作天线相差180°的天线处于接收hello包状态。

按照此扫描方式，由于节点每个接口控制m根天线，因此每个节点需要分配m个时隙可将自己的hello包广播给周围节点。这种机制可以避免hello的冲突问题，并且多个方向的天线在同时工作，能有效提升了扫描的效率。

图4 定向天线扫描示意图Fig.4 Scanning diagram of directional antenna

3 节点分簇的分布式控制信道分配

无线Mesh网络是无中心节点控制的，广播过程一般采取洪泛机制，会产生大量的消息冗余，容易在多个节点向同一节点转发消息时发生冲突，并且信道是不考虑实际情况平均分配的，容易造成信道资源的浪费。本文通过着色算法构造规模较小的连通支配集结构，在此基础之上分簇，进行简化链路，最后对节点设置优先级，以安排节点天线工作状态切换与信道的按优先级分配。这样信道分配机制业务量多、优先级高的节点可以较早的进行工作状态切换并分配较多的信道资源，在此机制下，广播过程的时隙和信道利用率大大提升，并能根据节点的优先级安排工作状态切换。

3.1 选取连通支配集

本文采用改进的着色算法，选取部分节点来构成网络规模较小的连通支配集结构[9-12]。定向天线一般是半双工，且双方需要处于“一收一发”状态，所以本文采取基于定时器的连通支配集算法。通过节点的度设计定时器，利用定时器的优先级来控制各节点天线的工作状态切换时间，完成信息正常交互，并且只需要一跳邻居信息就可构造出规模较小的连通支配集结构。

3.2 控制信道分配

在已构成的连通支配集结构上将其划分为多个簇的集合，简化链路，仅保留独立集节点与连接集节点、普通节点与独立集节点间的链路。在多接口定向天线模型下，网关节点利用其一跳拓扑信息设置节点优先级，利用节点优先级在网关节点上完成簇间无冲突的信道分配过程，然后簇头节点根据其相邻网关节点的分配结果独立地完成簇内信道分配。

为保证节点正常通信，时隙分配需满足：① 每个节点的时隙不同于其一跳邻居范围节点分配的时隙。② 同一接口下的多条链路不能分配相同的时隙，不同接口下链路可以。③ 通信链路间至少分配一个双向时隙。

原始链路简化至控制信道着色后的过程如图5～图 8 所示，其中时隙分配因为链路是双向的，因此分配的时隙数目是着色数的两倍。根据着色矩阵，为节点分配时隙矩阵的规则如下：假如链路着色号C(u,v)=p,如果ID(u)ID(v)，则节点v占用2p-1时隙号发送，节点u占用2p-1时隙号接收；节点u占用2p时隙号发送，节点v占用2p时隙号接收。

图5 原始链路Fig.5 Original link

图6 进行连通支配集构建后的链路Fig.6 Link constructed by the connected dominating set

图7 进行简化后的链路Fig.7 Simplified link

图8 进行着色分配后的链路Fig.8 Link handled by coloring algorithm

原始链路中冗余和冲突较大，发现全网节点所需的时隙远超优化后链路。在已简化但未进行着色分配的链路下，一共有17个节点和16条链路，因为一个通信链路需要双向时隙，从1号节点开始到发现全网节点共需要32个时隙。在进行着色分配后的链路中，有5种着色号，只需要10个时隙即可覆盖全网。

在这种分配机制下，通信较多的网关节点和簇头节点会分配更多的时隙和信道，并根据着色矩阵进行时隙占用优先级分配，有效地提升了时隙复用率和信道的利用率。

4 仿真结果与分析

采用QualNet进行仿真，仿真节点为32个，参数如表1所示。

表1 仿真参数配置

图 9 ～图 13给出了本文的广播过程和TREE-BASED、TDMA-NNI和BSRN算法在多种指标下的仿真结果对比，可以看出本文广播过程具有较低的广播耗时和广播包冗余率，并且广播可靠性更高，节点数目越多，本文的广播算法优势更加明显。

图9 广播成功率对比Fig.9 Comparison of broadcast success rate

如图9所示，随着源广播节点数目增加，广播成功率也呈下降趋势。由于本文和DMA-NNI算法都是通过TDMA时隙分配方式，在广播消息前预约时隙，对链路进行清晰的信道划分，不会存在冲突问题，广播成功率较高。TDMA-NNI算法中给每条通信链路分配时隙，由于物理信道质量的影响，网络中每条通信链路都会存在一定数量的丢包，而本文广播过程通过分簇的方式只给有效的链路分配信道，因此广播成功率比 TDMA-NNI要高。

图10 平均转发节点比例对比Fig.10 Comparison of average ratio of forwarding nodes

如图10所示，本文选择出的转发节点个数最少，并且选择转发节点所花费的网络开销也更少。本文广播过程在构建连通支配集时只需要一跳邻居信息，并且在选择转发节点的过程中总是选择节点连接度最大的节点为转发节点，这样保证选择出来的转发节点个数最少。其他算法均出现重复转发，故耗时和转发比例较大。

图11 广播耗时对比Fig.11 Comparison of broadcast time consuming

如图11所示，本文提出的广播过程广播耗时最少，BSRN算法广播耗时最大。这是因为 BSRN算法在广播过程中会频繁的与邻居节点交换信息，根据邻居节点的广播成功率来动态指定节点的转发概率，增加了广播时延。当源广播节点数目较少时，TDMA-NNI比TREE-BASED算法广播耗时更少，这是因为TREE-BASED需要额外的开销选择控制节点。本文在选择转发节点的基础上进一步实现了信道复用，利用多接口定向天线的优势并行发送消息，提高了时隙复用率。此外，本文广播过程选择转发节点以及分簇，只给部分节点和链路分配时隙，减少了消息转发跳数也减少了消息转发数目，从而减少了广播耗时。

如图 12所示，本文广播过程的广播包冗余率最少,这是因为本文通过选择控制节点和分簇方式，获得广播消息的路径已经确定，簇内节点只能从簇头节点处获得广播消息，而簇头节点从其相邻的网关节点获得广播消息，广播消息的冗余量最少。

图12 广播包冗余率对比Fig.12 Comparison of broadcast packet redundancy rate

如图 13所示,相比较其他几种算法，本文提出的广播过程节点最大负载率最小。这是因为本文通过选择控制节点减少了广播消息的冗余，并且通过分簇的方式，约束了广播消息转发的路径，进一步减少了节点收到的广播消息总个数。

图13 节点最大负载率对比Fig.13 Comparison of node maximum load rate

5 结论

本文对传统无线Mesh广播过程进行改进，综合采用了多种现有研究中的方法以提升广播过程性能，定向天线有效减少消息冗余，微时隙划分可以避免使用定向天线会出现的消息冲突，相应也使用控制信道划分以提高TDMA的时隙利用率。仿真结果表明，这一技术有效提升了广播过程的效率，并可以实现广播中的按需分配。