定向自组网中基于连通支配集优化的信息共享算法*

程 帅，徐任晖，彭来献，张 磊，杨曜旗

（陆军工程大学，江苏 南京 210007）

0 引言

无线自组织网络通常采用全向传输方式进行通信，因为相比于定向传输固有的隐藏节点、耳聋、暴露节点等问题[1]，全向传输拥有更加简单的控制协议。但是在远距离、大容量通信时通常采用定向传输方式，这是由于定向传输在相同的发射功率时拥有更远的传输距离和更高的空分复用率，能够有效减小被监听、定位的概率，增大网络容量[1]。无线自组织网络中的信息共享是每个节点都将自己所拥有的信息传播到其他节点的行为，以此来完成节点对网络环境的协同感知[2]。此类信息共享问题也称为全到全广播（All-to-All Broadcasting）或流言传播（Gossiping）问题[3]。在时延敏感型的网络中，节点需要将通过传感器采集到的信息快速进行分发，因而需要努力减小信息在共享过程的时延。由于所有节点需要并行地进行消息的分发和转发，对定向传输的调度方法和分发策略等问题提出了严峻的挑战。本文以定向传输无线自组网的信息共享为背景，研究在配备了单波束定向天线的通信节点所构成的无线网络中，高效完成共享战场态势信息的方案。

无线自组网中解决全到全的广播问题时，最简单的是通过泛洪（Flooding）的方式进行消息的广播分发[4]，这在规模较小的网络中是一种简单可行的信息共享方式。但随着网络规模的扩大，由于移动无线自组网固有的动态性和不可预测性[5]，泛洪的方式将会产生严重的接入冲突以及信息转发过程中的冗余传输问题，致使信息共享的性能下降，造成大量的带宽浪费和较高的通信时延。当前，为解决定向传输背景下的信息共享，主要是改造典型的UxDMA[6]、JazzyMAC[7]、ROMA[8]等定向MAC 协议[9]，使其能够完成信息共享。但此类算法不能完全消除冗余传输，没有充分利用定向传输的优势，导致网络的性能难以提升，信息共享的时效性仍然较差。

因此，如果要高效地完成信息共享，必须建立起有效的控制机制和传播策略，充分利用定向传输的空分复用特点，改善信息共享的性能。因而本文从空分复用率、冗余传输控制、调度机制3 个方面进行研究。连通支配集可以有效解决无线自组网中的冗余传输和拓扑维护等方面的问题[10-12]。但是当前对连通支配集的研究大多是基于全向网络的，其策略大多以减小支配集节点数目为目标，从而降低对网络管理的复杂度。本文将连通支配集技术应用于信息共享业务，提出了一种应用于单波束定向自组网中的无冲突调度算法——单波束最深搜索树（Maximum Depth Search Tree with Single Beam，MDST-SB）算法。该算法通过充分利用定向传输的空分复用特性，加强传输过程中的冗余控制，提高了信息共享的效率。

论文其他部分组织结构如下：第1 部分介绍了本文的基本通信模型和假设；第2 部分阐述了MDST-SB 算法的流程和算法分析；第3 部分给出了算法的仿真结果以及对照比较；第4 部分为总结部分，给出了现有研究的总结和后续研究方向。

1 系统模型

1.1 节点模型

在有N个节点的无线网络中，V表示网络所有节点的集合，任意节点vi∈V={x1,x2,…,xN}均存在一个的随机位置Location(vi)=(xi,yi)，其中xi表示其横坐标，yi表示其纵坐标。同时，每个节点都拥有一个可表示其身份的唯一ID，且Id(vi)=i。

1.2 通信模型

为简化分析，本文中的通信节点均采用最大通信距离为rmax的单波束定向天线，节点vi和vj的距离可以通过下面公式计算：

当dij≤rmax且天线指向相互对准后才能进行通信。

在信道资源使用方面，本文通过将时间划分为大小相等且为tslot的时间片，即时隙。并以时隙为单位对网络节点的通信状态进行调度，在一个时隙内节点只能处于发送或接收状态之一。

1.3 定长分组传输模型

研究信息共享问题需要确定合理的分组传输模型，本文采用固定长度的分组。节点vi将需要共享的本地信息mi封装成长度为L的分组，分组在发送和转发的过程中不能被拆分和重组。节点发送/接收速率为s，满足L/s=tslot，即表示一个时隙节点只能发送/接收一个分组。

1.4 问题描述

信息共享过程可描述如下：在共享时刻开始之初，节点vi将需要共享的信息封装成固定长度的分组mi，此时vi所拥有的消息集合Mi={mi},i∈{1,2,3,…,N}。在信息共享过程中vi不断发送自己消息集合中或接收其他节点发送过来的消息，经过若干次通信后，所有节点均拥有其他节点的消息，即M1=M2=…=MN={m1,m2,…mN}。

如图1（a）所示，是4 个节点组成的网络。初始时刻，节点分别包含的消息集合可表示为：M1={m1},M2={m2},M3={m3},M4={m4}。第一时隙可能的传输情况是节点v1发送m1到v2，v4发送m4到v3。因此，第一时隙结束时节点的消息集合状态为M1={m1}，M2={m1,m2}，M3={m3,m4}，M4={m4}。过程中经过若干次通信后最终达到M1=M2=M3=M4={m1,m2,m3,m4}，即如图1（d）所示的所有节点均达到信息共享完成状态。

图1 固定长度的信息共享模型

在信息共享过程中减小信息共享时延需要重点关注的是两个方面：冗余传输和定向传输的空分复用。图1（c）展示了一种可能的冗余传输情况，在中间的某个时隙，v4向v2发送m4，由于v4并不知道在此之前v3已经向v2发送过m4，导致该时隙的传输冗余。此外，定向传输相对于全向传输，可以通过控制波束的宽度、方向以及发射功率等因素，尽量减少对其他节点的干扰。在规模更大的一些网络中，充分利用定向传输的空分复用的特点，可以增大同一时刻并发通信数目，加快信息共享速度。

无线网络中，一跳可达的网络场景具备较好的连通性。在此场景下，假设网络中节点数为N，每一个节点vi都可以直接将自己的信息发送给网络中的其他节点。因此，一次完整的信息共享网络中需要转发的报文数量为N(N-1)。而在本文的通信模型和分组传输模型下，一个时隙网络能够发送分组的数量最多不超过N/2。因此，一次信息共享需要消耗的时隙数为N(N-1)/N/2。

然而，现实环境下无线网络中的节点很难做到一跳可达。因此，无论采用什么样的组网方式和传播方案，在本文的系统模型下完成一次信息共享完成一次信息共享消耗的时隙数Ncomsume满足：

同时，信息共享过程中需要交互的报文数量N(N-1)和消耗的总时隙数Ncomsume满足如下关系：

式中，ni为时隙Slot=i时的网络节点可以传输分组的数量。因此，为了减少共享过程消耗的时隙数目即Ncomsume，需要尽量增大每个时隙可以进行传输报文的数量ni。所以该问题可以转化为求Ncomsume的近似最优解问题。

2 算法设计

MDST-SB 算法是一种静态网络下的链路调度算法，其过程主要分为连通支配集的构造和链路的贪心调度两个阶段。

首先，算法需要根据网络其他节点位置信息进行连通支配集的初步构造集合。在得到的构造集合中进行优化策略的筛选，删除次优的构造结果，得到最终的构造网络并确定支配集节点。接下来，算法以时隙为单位进行集中式的贪心调度，过程中分别记录各个节点不同时隙的调度状态。当网络再次有共享需求时只需将共享的数据封装成定长分组。并在约定的时刻开始按照既定通信序列进行调度即可完成信息共享。表1 列举了算法过程中使用的符号。

表1 主要符号说明

2.1 连通支配集的构造

连通支配集的构造分为3 步：邻接矩阵生成、最大深度搜索和负载及链路的优化。邻接矩阵生成是将实际网络抽象化处理并作为后续步骤的输入。最大深度搜索是以邻接矩阵为输入进行先深搜索的遍历。负载优化和链路优化将处理的结果进行进一步筛选和优化。

2.1.1 邻接矩阵生成

中心计算节点根据网络各个节点的位置信息生成邻接矩阵Φ，矩阵各个元素的值Φ(i,j)可由下公式确定：

2.1.2 支配集构造

中心节点将邻接矩阵Φ作为输入参数，进行先深搜索遍历，并根据遍历结果的深度信息不断更新目标结果集合R，当发现深度更大的搜索结果时清空R，并存入新的遍历结果，当深度信息相同时在R中追加遍历结果。支配集构造算法的程序伪代码如下：

输入：网络的邻接矩阵Φ

输出：临界矩阵的深度最大的遍历结果集合R

2.1.3 支配集优化筛选

该步骤是针对上一步的得到的集合R进行负载优化筛选和链路消耗筛选。

（1）负载优化筛选

负载优化筛选过程是针对R中的每一个结果r根据每个节点的度的偏差之和进行的筛选过程。节点的度越大其负载就越大。由于节点负载的不均衡将会限制算法的性能，因此，该筛选过程是一个均衡负载的过程。

遍历结果r的不均衡负载的度Δload(r)的计算公式如下：

式中：N是节点个数；Wnode(vi)是节点vi的负载不均衡度，其计算方法如下所示：

式中：de(vi)表示在遍历结果r中节点的度；ζ为修正系数，满足1 ＜ζ＜2。在本文的定长分组传输模型中，度数较大的节点在信息共享过程中担负的向其邻居转发分组的任务过重将会成为算法性能提升的瓶颈节点。因此，通过平均负载的方法能够较大程度分担过程中节点的工作量，增大并行通信数量的目的。经过负载不均衡度的计算后，得到更新集合R'=min{Δload(R)}。

当|R'|=1 即目标集合中只有一个遍历结果时。该集合中的拓扑就是最终求得的目标解。当|R'|≠1 时，进行链路消耗筛选过程。

（2）链路耗费筛选

链路耗费筛选的意义是从集合中选择整体链路耗费最小的拓扑，从而减少网络内可能的相互干扰。其筛选过程如下。

对于R'中的每一个构造拓扑r∈R'，求出其链路消耗总和：

式中，N为节点数目，Φr(i,j)为构造拓扑r对应的包含链路权重的邻接矩阵中第i行、第j列的元素值。则算法最优结果rbest表达式如下：

在rbest中，当且仅当de(vi)≠1 时vi属于支配集节点。至此，连通支配集节点划分和信息共享网络构造完毕。

2.2 通信序列计算

通信序列计算是程序P 对全网节点的信息共享每个以时隙为单位进行集中式的贪心调度的过程序列。过程中详细记录各个节点在每个时隙的天线指向、收发状态、期望收发数据等信息，并将其作为算法执行的依据。它的计算过程如下所述。

首先，根据rbest得到图的邻接矩阵Φbest。程序P 按照贪心原则不断迭代完成一次完整的信息共享过程。迭代完成得到总的时隙数N以及每个周期网络中各节点的通信序列，即每个时隙不同节点的收发状态以及与之通信的邻居节点。

这里需要两个概念进行说明，一个是N维向量α=(a1,a2,a3…aN)，另一个是节点的转发表项。N为网络中节点的个数，向量则表示一个时隙中网络节点的被占用状态。在每次迭代任务开始之前，需要α重新置0。过程中根据任务情况不断调整各个分量的值。当ai=1 时表示节点vi在该时隙已经有将要有通信任务，当ai≠1 表示节点vi在该时隙尚未被分配通信任务。节点的转发表是一个的广播表，初始时刻节点根据链路信息生成针对自己共享信息的广播表，在共享过程中每次接收/发送消息后都会不断更新转发表的内容。

程序P 按照贪心调度算法进行迭代，每次迭代可求出一个时隙网络节点的调度情况。贪心调度算法的具体流程如下：

输入：rbest对应的邻接矩阵Φbest

输出：调度序列Seq

下面以3 个点组成的简单网络为例简单说明通信序列的作用。如图2 所示，网络包含3 个节点v1、v2、v3。节点拥有独立的转发表，表的第一列Slot 为时隙标识，Dest 为定向天线指向的目标节点，State 为收发状态。

因为网络中各节点位置已知，所以可以根据节点的编号对天线指向进行定位。当Dest=-1 时，表示节点此时隙处于空闲状态。Dest=i且i=-1 时表示该节点的天线指向节点vi的方向。当State=0 时表示节点处于发射状态，State=1 时表示节点处于接收状态，同样当节点在该时隙不工作时相应的State=-1。

图2 P 程序构造的通信序列

当中心计算节点得到计算各节点的通信序列后，通过已有的通用的通信协议将通信序列进行全网的分发。

3 仿真分析

3.1 参数设置

为了保持网络的连通性本文将网络区域划分为面积相等的正方形网格，每个网格内只有一个节点在网格内随机分布。且每个节点均能够跟相邻网格内的节点通信。如图3 所示，以9 个节点组成的网络为例介绍拓扑构建思想。图3 中每个小的正方形代表边长为1 km 的正方形小区，每个网格内只有一个节点随机分布网格中。9 个网格共同组成一个大的通信区域。同时，节点的最大通信半径设置为2.9 km，以确保网络的连通性。其他仿真参数设置如下：时隙长tslot=8 ms；分组长度L=200 kB，通信速率s=2.5 Mb/s；网络节点数N=4,9,16,25,36,49。

图3 9 个节点的网络拓扑

为了确定算法的正确性，引入信息共享完成度的概念，η定义为：

式中：Nget表示接收到的不同的分组的个数；Nall为共享完成时应该接收到的分组的个数，且满足Nall=N-1，在数值上等于网络节点数减1。一次信息共享过程不同时隙节点不断收到其他节点传输来的报文，完成度不断增加。当接收到所有节点的报文时完成度为1。

3.2 实验结果与分析

3.2.1 算法的正确性验证

图4 展示了9 个节点下采用MDST-SB 算法时不同节点在一次信息共享过程中不同节点的信息共享完成度随时隙变化的折线图。

从第1 个时隙末开始，各个节点的完成度不断增长。8 号节点最早在第19 时隙接收完毕其他节点的共享分组，直到1 号节点最终接收完毕，共经历30 个时隙。完成度成阶梯状增长的原因是因为节点在完成度不增长的时段处于发送或不工作状态。只有在接收到一个新的分组后完成度才会随之增长。

图4 完成度的增长曲线

3.2.2 算法有效性验证

当节点的个数分别为4、9、16、25、36、9 时，UxDMA、JazzyMAC、ROMA 和MDST-SB 算法完成信息共享的时隙关系如图5 所示。其中，横坐标为节点的个数，纵坐标为耗费时隙数。由图5 可知，消耗的时隙数随节点数目的增长而增长。UxDMA、JazzyMAC、ROMA 算法的增长速度要远远快于MDST-SB 算法的增长速度。这是因为MDST-SB 调度算法充分利用了定向传输的空分复用特性增大网络中同时传输的报文数目并具有较好的冗余控制能力。而JazzyMAC 算法通过传递令牌的方式虽然能够避免链路冲突，但是限制了网络的空分复用率；UxDMA 算法只通过随机选择不同的链路组合进行调度，但是在转发分组的选择上并没有有效的控制手段；ROMA 算法通过随机的配对策略和优先级比较的收发方案，使其信息共享的效率难以提高。相比与UxDMA，MDST-SB 在时延上平均可降低42%。

图5 随机拓扑消耗时隙与节点数的关系

4 结语

本文提出了基于连通支配集的信息共享算法，该算法构造定向传输场景下的连通支配集，并通过均衡网络负载和减小网络链路耗费来提高共享性能和降低网络发射干扰，从而实现态势信息的快速共享。仿真分析表明，本文提出的算法相较于传统的基于UxDMA，JazzyMAC，ROMA 的信息共享算法从空分复用率、冗余传输控制、调度机制三个方面做出了优化，从而使性能有较大的提升。未来工作将主要关注算法在动态场景下的应用，提升算法在工程中的实用价值。