战术移动点对点Ad-Hoc作战单元拓扑重构

蒋馥蔚，王叶群，李艳福，赵尚弘

(空军工程大学信息与导航学院军事航空通信重点实验室，西安 710071)

地面战术移动点对点Ad-Hoc作战单元，是一种分布式终端直通(device to device,D2D)网络[1]，节点依据作战需求携带武器装备，遂行具体作战任务，往往有固定的执行路径与活动范围，不能随意移动位置，单元内节点之间由于地形或障碍物的因素，网络分割及节点脱网时有发生。保持网络拓扑的完整性，是保证信息有效传输的前提，已有的对于多跳网络拓扑控制与优化的研究，主要从链路控制的角度出发，通过节点发送功率控制的手段重新构建网络拓扑，如文献[2]在区分信息流类别的基础上，通过调整节点功率，从而实现节点加边控制的方法来重构拓扑；文献[3-4]通过控制节点功率选择路径，文献[5-6]考虑网络整体业务效率，采用功率控制与业务重路由等方式提高传输有效性。文献[7]采用自适应人工免疫算法，设计层次型拓扑结构来优化网络功耗，延长网络寿命。这些研究，均没有考虑当拓扑连通的关键节点因遮挡而脱网或相邻节点超出节点最大覆盖范围时，单纯使用调整功率的方式很难或无法修复拓扑连通性。

基于此，现提出，随着地面D2D节点的移动，空中无人机中继主要用来辅助地面网络的关键节点通信，使网络拓扑保持完整，因此称空中无人机中继为拓扑机器人节点，暂不考虑移动速率等因素，使拓扑机器人节点与地面网络呈相对静止状态，拓扑机器人节点监视地面网络拓扑，优化及重构拓扑。当地面节点由于遮挡或损毁等因素脱网时，拓扑机器人节点调整相对位置，维持拓扑完整性。

1 相关研究

关于无人机中继的D2D网络的研究所考虑的场景，如图1所示，空中无人机中继是静止盘悬的状态以代替地面基站[8]，或者地面节点是静止状态，从中继部署、中继信道选择、节点能量优化等角度，主要关注网络资源分配[9-10]，而对于地面节点与空中节点都需要移动推进，过程中拓扑连通情况的保持，尚未引起关注。

图1 拓扑机器人中继的地面分布式Ad-Hoc作战单元

现有的对多跳网络拓扑控制与优化的研究，主要从链路控制的角度出发，通过加边减边以及业务重路由等方式提高传输有效性。现提出的拓扑机器人补盲的方式，是一种节点控制算法，通过调整拓扑机器人的相对位置，使处于冗余位置的拓扑机器人移动来重构网络拓扑，改善网络连通性。中继部署算法的拓扑机器人与地面节点是异构的关系，拓扑机器人对拓扑的监视，是对地面分布式节点的相对位置的一种集中管理，可以对网络连通关键点进行重要性量化，以有效优化网络拓扑。

拓扑机器人调整相对位置的依据，便是要找到网络连通关键点。评价网络连通关键点的常用方法，就是找到网络中对连通性影响最大的节点，即节点重要度的方法来度量。历年来研究节点重要度所演化的算法，已有的有节点删除法、介数法、收缩法、模型分析方法等，以节点连接度、节点间最短路径等作为度量指标；考虑节点之间的相互作用，文献[11-12]提出了评价矩阵、贡献矩阵来得出节点重要度排序。在已有算法的基础上，考虑节点连通重要性，从是否割点、节点度值及信息流传输效率衡量，分别反映了节点分裂影响度，局部重要性与全局重要性。并按照预防性拓扑重构与修复性拓扑重构两个方面来设计拓扑机器人重构拓扑算法。

2 节点重要度计算

2.1 理论基础

定义网络图中，节点集合分别为任务节点集合V，拓扑机器人节点集合R，连接拓扑机器人边的集合L，任务节点之间边的集合M，因此设图G=(V,R,L,M)是一个无自环的无向网络，网络中总的节点数量n=n(V)+n(R)。

2.1.1 定义1 邻接矩阵

设分布式网络G的邻接矩阵用E(G)=(aij)n×n表示，考虑双向通信链路，其中aij表示节点i和节点j之间的连通情况，若i和j之间存在链路，则aij=1，否则aij=0。G是无向图，E(G)是对称矩阵。

2.1.2 定义2 节点邻域

节点最大发送功率所覆盖的区域称为节点邻域，用Rmax(vi)=G[Nmax(vi),Emax(vi)]表示，其中Nmax(vi)为落入节点vi邻域内的节点集合，Emax(vi)为节点vi邻域拓扑的链路集合。

2.1.3 定义3 节点度值

节点的度值digi与节点重要度的关系很大，当前节点对相邻节点的影响力可以通过节点度值来反映，节点度值是指与当前节点直接互联的节点数目。节点度值越大，该节点对其相邻节点的影响越大。节点领域的节点数量，是节点工作在最大发送功率下的节点度值。

2.1.4 定义4 割点及连通度

节点vi是割点，或称关节点，当存在不同于vi的2个顶点vu、vω，使得vi在每一条由vu到vω的路上。存在V-{vi}的一个划分V-{vi}=U∪W，其中U∩W=Ø，使得∀vu∈U,∀vi∈V满足vi在每一条由vu到vω的路上。当关节点vi失效时，必然会造成网络分裂。没有关节点的连通图称为重连通图。图的连通度定义为，至少移除k个顶点才能破坏图的连通性，则该图的连通度为k。用数学描述为：设V′是V中任一非空真子集，若图G连通而G[V-V′]不连通，则称V′是G的点割集。最小点割集中顶点的个数就是图G的连通度κ(G)。

2.1.5 定义5 节点重要度贡献矩阵

网络中的节点总数为n，〈k〉为节点的平均度值,若节点vi的度为digi,则该节点将重要度的digi/〈k〉2贡献给每一个相邻节点。将所有节点对其相邻节点的重要度贡献比例值用矩阵的形式表示出来，便是节点重要度贡献矩阵，即

HIC=

(1)

式(1)中：δij为贡献分配参数，当两个节点(vi，vj)直接相连时值为1，否则值为0；对角线上的1为每个节点对自身的重要度贡献比例值；HICij为节点j对节点i的重要度贡献比例值，可以看出重要度贡献比例值越大的节点，其对相邻节点的影响也越大。邻接矩阵与HIC具有相同的结构，HIC是网络邻接矩阵的一个映射，其规则为

(2)

2.1.6 定义6 节点效率

2.1.7 定义7 节点重要度评价矩阵

用度来构建节点之间的重要度关联，用节点传输贡献率标识节点在网络信息传输中的位置，可以得到重要度评价矩阵HE为

HE=

(3)

2.2 节点重要度评价的算法设计

(4)

计算出的网络中的最重要节点就是对网络连通性及网络信息传输起到关键作用的节点，一旦该节点失效，会引起网络分裂，造成网络性能较大的下降。考虑节点连通重要性，从是否割点、节点度值及信息流传输效率衡量，分别反映了节点分裂影响度，局部重要性与全局重要性。从节点重要度定义来看，节点的重要度贡献及节点效率都是小于1的归一化参量，而割点权值赋值2，可见，割点是拓扑优化时首先考虑的关键节点。当网络中有多个割点时，才需要对连通关键点依据该公式重新计算关键点，若只有一个割点，只需要比较拓扑机器人的重要度以确定移动重要度最小的拓扑机器人。若网络中没有割点，维持拓扑现状。

3 基于拓扑机器人的网络拓扑重构算法

要进行拓扑重构，拓扑机器人要能够判断在当前拓扑中的关键节点以及脱网节点。拓扑机器人周期性发送拓扑探测消息，收集网络拓扑，步骤如下。

(1)基于割点判定，预防性拓扑重构。通过深度优先算法，发现网络割点，并计算节点重要度，进行重要度排序。在进行预防性重构时，重要度最小的拓扑机器人节点需要判断自身局部冗余度，通过一跳邻域确定自身不是割点，两跳邻域确定自身移动后不会带来新的割点。

(2)基于拓扑探测响应周期的延迟，进行断点判定，修复性拓扑重构。在进行修复性重构时，设定拓扑机器人节点在5个周期未收到某节点的响应，即认为该节点已脱网，需要启动修复性重构算法，修复性重构依然要计算拓扑机器人的重要度排序，并判断自身移动不会带来新的网络分裂，再移动去修复拓扑。当节点大面积失效时，需要按算法多次移动多个拓扑机器人节点。拓扑重构流程如图2所示。

图2 拓扑重构流程图

4 实验分析

从两个方面分别进行实验分析，介绍依据节点重要度对拓扑机器人进行位置调整所带来的网络抗毁性能的提升的衡量方法，网络节点故障数与拓扑机器人数量之间的关系的表现形式。

4.1 预防性重构抗毁性分析及节点重要度计算

对于割点对抗毁性造成的影响，适用聚合度来衡量，表达式为

(5)

式(5)中：S为由图G的若干顶点构成的集合，若G-S是不连通的，则称S为图G的一个顶点割；|S|为这个顶点割中顶点的数目。将C(G)记为图G的所有顶点割组成的集合。图G-S的连通分支数被记为w(G-S)，图G-S的最大连通分支的节点数记为τ(G-S)。最大分支顶点数越多，连通分支越少，割点越少，一个图的聚合度i(G)越大，那么它所对应网络的抗毁性越强。当|S|=0时，w=1，τ=N，网络中节点越多，抗毁性越强。

图3 存在割点和预防性重构后的网络拓扑

表1 节点重要度计算及排序

若不考虑割点权值，计算出最重要的节点是节点v3，而节点v3失效并不会带来网络分裂，对于连通性而言，影响不如割点v6。找到节点重要度最小的拓扑机器人v7，v7的两跳领域拓扑连通，移动后不会带来新的割点；移动至离当前位置最近的预防性重构位置，连接{v6,v5,v9}来估计修复后的抗毁度，如图3(b)所示，此时网络不再有割点，因此，w=1最大连通分支顶点数为τ=9，重构网络抗毁度为i=9,抗毁性增量为Δi=9-2.5=6.5，因此机动拓扑机器人节点v7来进行预防性重构可以提高网络抗毁性。

4.2 重构前后性能比较

对网络节点故障数比较多，拓扑机器人移动修复网络连通性的性能测试，需要结合网络仿真来验证。使用NS-3网络模拟软件对拓扑重构算法性能进行仿真测试，仿真环境为地面任务节点数100个，非均匀分布在400 km×400 km的范围内，地面节点视距通信半径为最大8 km,节点链路由于地形以及建筑物遮挡等因素会发生中断，空中拓扑机器人节点5个，每个节点覆盖半径最大为100 km,拓扑机器人之间可以实现视距通信，地空链路仰角对地空链路连通性的影响暂不考虑。仿真中应用层采用CBR数据流，每个报文512 Byte，设置300个数据流，通过设置不同的节点运动场景，采用多次仿真求平均值的方式，对比了在拓扑重构前后网络性能的变化情况，采用分组成功投递率作为分析的依据。分组成功投递率反映网络处理和传输数据的能力。其定义为：在应用层，目的节点接收到的分组数与源节点发送的分组数之比。

由图4(a)可以看出，拓扑机器人在网络没有故障时，预防性重构网络拓扑，重构后的分组成功投递率一直保持在较高水平，而重构前，随着发包速率的增加，网络负载较重时, 拓扑中关键点成了数据传输业务的瓶颈, 使网络发生拥塞, 大量分组无法成功到达目的节点, 投递率快速减少。网络拓扑结构在重构算法的作用下逐渐趋于均衡, 为路由的优化选择和负载均衡分配提供较好的基础, 提高了通信效率, 优化了网络性能。

图4 发包速率和网络故障数对分组成功投递率的影响

图4(b)仿真中发包速率为1个数据包/s, 可以看到，当网络中的故障数较少时，重构前后的分组成功投递率都较高，这是由于网络中存在拓扑机器人节点，少量故障对拓扑连通性破坏不明显，关键点发生故障的概率也较小，随着网络故障数的增加，分组成功投递率快速减少，这是由于网络中出现大量故障时, 关键节点的故障概率也随之增大, 对拓扑连通性破坏严重, 使网络中可用路由减少, 造成生存下来的路径传输质量和效率下降, 导致成功到达目的节点的分组数急剧减少。拓扑重构策略通过拓扑机器人节点的移动修复拓扑故障并对拓扑结构进行优化, 为上层协议的高效运行提供了保障, 使网络性能得到了有效的恢复, 增强了网络的抗毁性。

研究并未考虑时延、节点相对速度、信道容量、能耗等其他因素，主要关注点在拓扑连通性的保持上，为了验证拓扑机器人对拓扑重构的可靠性与有效性，与现有的链路控制算法对比，理论上可以推测出，当处于最大发射功率的条件下，所有的加边算法都无法绕过遮挡进行网络拓扑重构，当节点发生故障时，也无法超出节点邻域加边重构。而本文算法在考虑最大发射功率的前提下，通过增加冗余拓扑机器人节点，来监视拓扑，改善连通，与链路控制的加边算法结合，可以有效节约能量，提高网络抗毁性。

为了与链路控制算法进行对比，按照文献[2]中的抗毁性定义，网络中正常传递信息的信息流条数会随着通信实体的不断损毁而减少，因此其信息流抗毁度为网络中连通节点对与损毁节点总数的比值，也就是分组成功投递率随着网络故障数的变化关系。文献[2]中的综合抗毁度f，当各种信息流具有相同的权值时，反映的便是网络的分组成功投递率随网络故障数的变化关系，在本文算法相同的仿真前提条件下，不设置拓扑机器人节点，采用文献[7]中的DABC算法，进行多次仿真取平均，得到如图4(b)中所示结果。本文算法结果是多次仿真取平均，因此曲线较文献[7]的仿真结果6平滑，但得到的抗毁度取值区间与文献[7]的仿真结果6一致，当节点损毁比率达到20%时，其对应随机攻击抗毁性能f处于区间[0.4,0.6]，即分组成功投递率低于60%，而本文算法分组成功投递率可接近80%，DABC算法分组成功投递率明显低于本文算法。这是由于加边算法无法获得超出节点领域的节点进行加边连接，而本文算法通过拓扑机器人节点冗余获得拓扑结构更大的灵活性，除损坏节点无法通信外，存留节点均可重新建立连接，因此带来更好的抗毁性能。

5 结论

为提高地面战术移动Ad-Hoc作战单元的拓扑抗毁性，增加拓扑机器人来监视网络拓扑，对连通关键节点从网络分裂影响度、邻居断链影响度、最短路径中断影响度来综合定义，计算节点重要度，机动重要度最小的拓扑机器人节点来重构与修复网络拓扑，仿真结果表明了拓扑机器人对网络抗毁性能的提升。研究并未考虑时延、能耗、冗余代价等与增加拓扑机器人对网络性能影响相关的其他变量，下一步，考虑拓扑机器人部署方法给地面移动Ad-Hoc作战单元带来更多性能提升，如最小化时延、最小化能量等指标，开展更多相关研究。