基于最大完全子图与最小树形图的无线定向网络广播算法

钮金鑫

(中国西南电子技术研究所第二事业部, 成都 610036)

定向天线可将能量辐射至空间特定方向,因此可有效提升天线收发增益,增强接收信噪比,进而提升通信距离,提高通信系统的抗干扰性能,减小端到端路由跳数。基于定向天线的通信系统目前已广泛应用于5G通信[1-3]、车联网[4-11]、军事通信[12-13]等领域。

采用定向天线虽然可为通信系统带来较大增益,但会降低广播业务通信效率,主要体现在：节点采用全向天线发送消息,在其通信范围内的所有一跳邻居节点均可收到该消息,而采用定向天线后,只有波束覆盖范围内的邻居节点可收到消息,若要实现消息广播,中继节点需多次调整波束指向覆盖所有邻居节点,导致定向广播过程需要占用更多通信资源。因此,如何有效提升广播效率,节省通信资源是定向广播领域需要研究的关键问题。

现有关于广播算法的研究主要分为全向广播和定向广播两大类。全向广播研究起步较早,其中,文献[14-15]提出了基于连通支配集的广播算法,该算法以网络全局拓扑信息为输入,将连通支配集中的节点作为中继节点,实现全网广播。文献[16-17]以部分拓扑信息为输入,利用不同节点邻居集合的包含关系,以逐级扩散的方式指派部分节点作为中继节点实现全网广播。文献[18]提出自裁剪算法,以两跳范围内的拓扑信息为输入迭代选择中继节点。文献[19]提出了一种应用于矿山应急网络中的网状网路由协议。定向广播相关研究主要以全向广播为理论基础,将其扩展至定向通信场景,主要分为概率性广播及确定性广播两大类。概率性定向广播算法[20-21]以提升网络中所有节点的覆盖概率为目标,求解每个节点的转发概率,当概率超出门限值时节点在特定方向上转发消息。确定性定向广播算法通过指定中继节点的方式,将源节点产生的消息可靠发送至所有节点。文献[22]以全向网络的自裁剪算法为基础,将中继节点及其一跳邻居视为可被波束覆盖的节点,利用两跳邻居信息计算未覆盖节点集合,进而求解中继节点。文献[23-24]采用基于链路消减的广播算法,在给定扇区划分策略的条件下,利用两跳邻居信息计算中继节点。文献[25]提出了基于贪婪搜索及流言扩散机制的中继节点选择算法确保中继节点信息转发可覆盖全网节点。

车联网领域涉及定向广播的相关研究中,通常以给定道路模型作为先验条件,以基站作为中心节点,利用网络全局拓扑信息计算中继节点,根据道路方向确定信息传播方向[4-7]。文献[8]将所有节点分布区域划分为多个区,通过网络分区技术减少车联网中紧急消息传播冗余,提升分组递交率。文献[9]在考虑车辆距离、车辆密度、波束样式等因素的情况下分析了毫米波车联网的定向广播范围。文献[10]在车联网场景下提出了一种基于速率与位置信息的广播策略,用于改善端到端时延及分组递交率。文献[11]提出了一种基于位图的多跳广播协议降低消息转发时延和碰撞概率。但上述关于车联网的广播策略均未给出定向网络场景下的波束指向设置方法。

在部分定向网络接入协议的相关研究中提出了定向波束干扰避免策略,从而提升广播消息递交率。文献[26]研究了定向时分多址(time division multiple access,TDMA)网络中减小定向天线信息传播冲突的传输资源分配策略,提升了时隙利用率。文献[27]通过设计基于RTS(request to send)/CTS(clear to send)的接入机制,避免了多节点同时进行数据传输的波束重叠干扰问题。但上述研究仅给出如何避免波束干扰的策略,仍未提出如何设置定向波束指向从而提升传输效率。

综上所述,现有关于定向广播的研究主要集中于在定向组网场景下如何选择中继节点,对于中继节点的波束指向计算及广播效率提升方面还存在局限性,主要体现在：确定性定向广播算法虽然可以通过中继节点选择保证全网覆盖性,但未说明中继节点如何计算波束指向,无法保证中继节点通过较少的转发次数覆盖全网所有节点;车联网定向广播依据基站提供的全局网络信息及道路模型寻找中继节点及计算波束指向,适用场景受限。

若要提升定向广播效率,使用较少转发次数覆盖网络中所有节点,需联合考虑以下两点：①波束指向计算,即如何选择波束指向能够使单个波束尽量覆盖较多节点,提升传输效率;②中继节点选择,即如何选择中继节点,能够使网络中所有中继节点的转发次数之和尽量小,提升全网广播效率。

现提出一种基于最大完全子图与最小树形图的无线定向网络广播算法(maximum complete subgraph and minimum arborescence based directional broadcasting algorithm,MCSMA)。MCSMA算法适用于分布式定向组网场景。算法首先根据最大完全子图理论给出覆盖节点数量最多的波束指向计算方法,然后利用最小树形图理论求解中继节点及其波束指向,最终达到减小消息转发次数,提升广播效率的目的。

1 场景模型

考虑图1所示的分布式定向网络。网络中各节点装配波束自适应天线,可任意设置波束指向(如自适应相控阵天线,可通过装配多副天线实现全空域覆盖)。天线波束覆盖范围为锥形区域[17],波束宽度为θ,定向传输范围为d。对于节点u、v,若节点v在节点u的传输覆盖范围内,则称v为u的一跳邻居节点。位于v传输范围内、u传输范围外的节点为u的两跳邻居节点。在时分多址接入框架下,源节点采用天线的定向模式向邻居节点发送数据,邻居节点采用天线的全向模式(或通过多副定向天线同时辐射的方式)接收数据,并可通过全向模式获取两跳邻居信息[22-23,28]。

图1 场景示意图

在分布式网络场景下,各节点无法获取网络全局拓扑信息。为便于描述波束指向,每个节点将自身所处位置作为坐标原点,将水平面作为xy平面,将垂直于水平面向上的方向作为z轴方向,如图2所示。以节点u所在位置为原点按上述方法构建的坐标系,定义为节点u的波束指向坐标系。

图2 波束指向坐标系

2 问题描述

考虑如图3(a)所示的通信场景,源节点u需将消息广播至网络中其他节点。若u按图3(b)所示方式选择错误的中继节点r,或中继节点r按图3(c)所示方式选择错误的波束指向,均可能增加消息转发次数。只有联合考虑中继节点选择及波束指向计算,才能达到减小消息转发次数、提升广播效率的目的,如图3(d)所示。

图3 定向广播问题说明示意图

全向网络中,寻找最优中继节点集合可建模为最小连通支配集求解问题,即使在获得全局网络拓扑信息的条件下,该问题仍为NP完全问题[18]。相比于全向网络,定向网络除需寻找最优中继节点集合外,还需求解最优波束指向保证通过少量波束覆盖多数节点,求解复杂度进一步增加。此外,分布式组网场景下节点无法直接获得全局拓扑信息,获取全局最优广播策略难度较大。因此,需通过设计启发式算法求解能够减少消息转发次数的高效定向广播方案。

从以下两方面出发获得高效定向广播方案：①利用最大完全子图理论,通过一跳邻居节点位置信息求解最优波束指向,使单个波束能够覆盖最多数量的邻居节点,提升覆盖效率;②以波束指向计算方法为基础,利用最小树形图理论,通过两跳邻居信息确定中继节点集合及对应波束指向,减少广播过程中的消息转发次数。

3 MCSMA算法

3.1 基于最大完全子图的波束指向算法

基于最大完全子图的波束指向算法目的是求解能够覆盖最多邻居节点的波束指向,通过较少波束覆盖所有邻居节点。算法将源节点与邻居节点之间的链路建模为平面图的顶点,在夹角小于波束宽度的链路对应的顶点之间添加边,形成无向图。通过求解无向图的最大完全子图,获得夹角小于波束宽度的最大链路集合,该集合对应的所有邻居节点均可被源节点产生的单个波束覆盖,进一步根据邻居节点位置信息确定波束指向,达到单个波束覆盖多个邻居节点的目的。

算法1基于最大完全子图的波束指向算法。

执行对象：链路源节点u。

输出：u的指向列表。

步骤4计算图G1的最大完全子图对应的顶点集合为S。

步骤5计算节点u与集合S对应邻居节点间的最大距离rmax。

步骤6在u的指向坐标系内,将u与集合S对应所有节点的连线长度延长至rmax,计算集合S对应的所有节点按该方法处理后的坐标,并以所有处理后的坐标为对象,分别求解x、y、z坐标轴上的最小值和最大值,记为xmin、xmax、ymin、ymax、zmin、zmax。

步骤8在图G1的点集合中,去除波束指向覆盖范围内链路对应的顶点及与其向关联的边,重新执行步骤4,直至图G1为空图。

算法1中,步骤1用于计算节点与其一跳邻居节点之间链路的夹角;步骤2、步骤3根据节点与一跳邻居之间的链路夹角关系创建图G1;步骤4利用最大完全子图理论确定可被单个波束覆盖的最大邻居节点集合,任一求解最大完全子图的算法均可带入至步骤4;步骤5～步骤7用于在节点的指向坐标系中确定能够覆盖邻居数量最多的波束指向;步骤8用于迭代计算能够覆盖所有一跳邻居节点的波束指向。

3.2 MCSMA算法

以定向广播覆盖网络所有节点为约束条件,若要提升定向广播效率,需使源节点与所有中继节点的波束数量之和最小。MCSMA算法基本思想是将源节点与其一跳邻居节点建模为平面图的顶点,源节点至邻居节点的通信链路建模为二维平面图的有向边,将源节点指向邻居节点的波束内可覆盖节点总数量的倒数作为有向边的权值,利用两跳邻居信息及算法1求解以源节点为根节点,可到达所有一跳邻居且权值最小的有向树(即求解有向图的最小树形图),进而求得中继节点集合及对应指向,达到通过少量波束覆盖所有邻居节点的目的。MCSMA算法无需网络全局拓扑信息,仅需两跳邻居信息,适用于分布式网络。

算法2MCSMA算法。

执行对象：广播消息源节点或迭代过程产生的中继节点,用u表示。

输出：Ru、Pu、P′u。

步骤1初始化Ru、Pu、P′u为空集;若其他节点已指定u的指向,则将该指向加入Pu。

步骤5求解G2的最小树形图G′2。

步骤6G′2中,对于以u为起点的所有有向边e(u,v),若存在有向边e(v,m),则节点v为u选定的中继节点,更新Ru;有向边e(u,v)对应的波束指向为u的波束指向,更新Pu;以v为起点的有向边对应的波束指向为v的指向,更新P′u。

分布式网络中,任意节点均可能指定本节点为中继节点,并为本节点指定波束指向,因此算法2的步骤1用于初始化节点指向集合;步骤2～步骤4用于构建有向赋权图,节点与邻居之间的链路建模为图的有向边,根据算法1计算波束指向,根据波束覆盖范围内的节点数量确定边权值,覆盖节点数越多边权值越小;由于在步骤3中,源节点需以一跳邻居为对象执行算法1,因此该步骤需用到两跳邻居信息;步骤5、步骤6通过求解最小树形图确定节点自身的波束指向、中继节点集合、中继节点波束指向,由于最小树形图在有向图的所有树形图中权值最小,而权值越小,对应链路的波束指向覆盖的节点越多,因此利用最小树形图求解的中继节点及波束指向可达到用少量波束覆盖多数邻居节点的目的,节省广播过程中的信息转发次数

定理1图G2存在至少一个以算法2执行对象为根的最小树形图。

证明：另算法2执行对象为u。G2的顶点集合由u及其一跳邻居节点映射而成,u通过算法1计算得出的波束指向可覆盖u的所有一跳邻居节点,因此在图G2中,节点u到其他邻居之间必然存在一条由u指向邻居节点的有向边,故图G2中必然存在一个以u为根节点的最小树形图。

定理2分布式组网场景中,MCSMA算法可覆盖全网所有节点。

证明：源节点u执行算法2后,通过指定中继节点及其波束指向,可保证覆盖一跳传输范围内的所有节点。各中继节点以自身为算法2执行对象,继续计算下一级中继节点及指向,可保证源节点u两跳传输范围内的节点均被至少一个中继节点的一个波束指向覆盖。新生成的中继节点继续迭代执行算法2,可保证全网节点均被覆盖。

4 仿真分析

仿真过程设置天线波束宽度为30°。节点随机分布在500 m×500 m×500 m的三维区域内,定向天线传输范围为100 km。节点数量考察范围为3～20。仿真迭代次数设置为500。

为考察MCSMA算法在网络覆盖程度和广播效率方面的性能,采用以下两种方案作为对比方案。

(1)DSP(directional self-pruning)算法[22]。根据DSP算法确定中继节点。由于DSP算法未说明如何设置波束指向,因此仿真过程假定若源节点或中继节点发现未被波束覆盖的邻居节点,则直接将波束指向该邻居节点。

(2)DSP算法加入波束指向优化。以DSP算法为基础确定中继节点,当通过未被波束覆盖的邻居节点确定波束指向后,将波束内的所有节点均判定为已覆盖。

仿真过程通过考察源节点和中继节点的波束指向比对不同算法的覆盖情况,通过计算源节点和中继节点的波束数量比对不同算法的广播效率。

为考察不同算法的波束覆盖情况,设置节点数量为15,分布情况如图4所示。在该场景下, MCSMA算法、DSP算法、DSP算法加入波束指向优化的波束覆盖情况分别如图5～图7所示。可以看出,DSP算法中每个波束覆盖的节点数量较少,相比于DSP算法,MCSMA及加入波束指向优化后的DSP算法中的一个波束均可覆盖多个节点。MCSMA利用基于最大完全子图的波束指向设置算法可通过一个波束覆盖多个相近位置节点,因此覆盖效率最高,覆盖所有网络所有节点需要的波束总数最少。

红色圆点表示节点,每个红色圆点代表一个节点

红色圆点表示节点,每个红色圆点代表一个节点

红色圆点表示节点,每个红色圆点代表一个节点

红色圆点表示节点,每个红色圆点代表一个节点

在不同节点数量场景下,MCSMA算法、DSP算法、DSP算法加入波束指向优化3种算法所需的波束数量和中继数量分别如图8、图9所示。仿真过程取3种算法500次迭代的平均值作为仿真结果。如图8所示,DSP算法所需的波束数量最多,原因是DSP算法仅以未覆盖的邻居节点为中心确认波束指向,效率较低,随着网络节点数增加,所需的波束数量增长较快。MCSMA算法所需的波束数量最少,原因是MCSMA算法一方面利用最大完全子图理论计算能够覆盖多个邻居的波束指向,另一方面通过最小树形图理论选取能够用少量波束覆盖多数邻居的节点作为中继节点,减少源节点和中继节点在广播过程中产生的波束数量,提升了广播效率。如图9所示,相比于DSP算法,MCSMA算法产生更多中继节点,是因为MCSMA算法通过恰当选择中继节点及转发指向的方式,达到中继节点在广播过程所需的波束数量最低的目的,实现了高效定向广播。

图8 不同节点数场景下波束数量对比

图9 不同节点数场景下中继节点数量对比

5 结论

为提升无线定向网络广播效率,提出一种基于最大完全子图和最小树形图的定向广播算法。MCSMA算法首先利用最大完全子图理论计算波束指向,使单个波束覆盖的节点数量最大,然后利用最小树形图理论计算中继节点及其波束指向,减小定向广播过程中的消息转发次数。仿真结果表明,MCSMA算法在保证网络所有节点均被波束覆盖的约束下,通过中继节点选择及波束指向计算,可减少广播过程中的波束数量,提升广播效率。以MCSMA算法为基础,设计适用于分布式定向网络的广播协议作为后续研究问题。