Page 248 - 《软件学报》2020年第11期

于冲 等:基于二跳共同邻居的无人机群体网络演化算法 3563

2 无人机协同网络演化算法

无人机群体在实现编组、避障、进行群体作战的过程中,需要进行频繁的信息交换.由于无人机群体应用
的特殊性,在其工作中不断面临敌方的干扰与攻击,部分无人机会因此失效而脱离群体.所以,时刻保障无人机
群体通信网络结构的可靠,是我们研究的重中之重.链路预测的思想是,利用网络中已知的节点属性或者网络拓
扑结构信息来预测网络中尚未产生连接的两个节点间产生连接的可能性 [19] ,这为无人机群体协同的路由路径
选择问题提供了新的解决思路.因此,我们提出一种基于链路预测方法的无人机群体网络演化模型,为无人机群
体的协同控制提供有效的通信保障.

2.1 网络布局
本文假设无人机同构,每一架无人机被赋予唯一的编号作为标示.定义无人机节点的通信半径为 R,如果两
个无人机节点间的距离小于等于 R,则两者可以直接进行通信;否则,两者需要通过多跳传输进行通信.使用 p i 表
示无人机 i 所处的位置,那么无人机节点 i 的空间邻居集可以表示为 n i ={j:||p i −p j ||≤R}.存在于 n i 中的节点具备
与节点 i 建立连接的基本条件.由于无人机群体的应用遍布了各个领域,为了拓展模型的可用性,我们设计无人
机节点随机分布在三维立体空间中,区域的边长为 L,节点总数为 N.
无人机群体的工作模式分为集中式和自组织式两种.工作在集中式模式下的无人机群体拥有一个控制中
心,该控制中心通常由处于集群核心位置上的无人机担任.在执行任务的过程中,所有无人机将采集获取的信息
上传至控制中心,控制中心对所有数据进行聚融、分析并做出决策,对集群进行统一调度调配.与集中式模式最
大的区别是,工作在自组织式模式下的集群并不需要控制中心.对于无人机个体而言,它只需要时刻与它邻近的
无人机进行信息交换与协同控制,以保证集群在局部上的收敛,进而保障整个集群的稳定.由于集中式集群工作
模式中存在控制中心,当控制中心失效以后,整个集群处于瘫痪状态,这将给通信网络的可靠带来很大的危害.
因此,我们设定本文中的无人机集群工作在自组织式工作模式下.
本文所提出的无人机群体通信网络的 LPTCN 演化算法包含网络初始化与网络维护两个部分.下面我们将
针对这两个部分分别进行介绍.
2.2 网络初始化

我们使用图论来描述网络的演化过程,首先定义 (, )Gv ε 表示初始网络,在网络演化伊始,我们从无人机节点

集合 v 中随机选取 m 0 个节点构成集合 v ,作为网络初始节点,并在此 m 0 个节点之间随机产生 n 0 条连边构成集

合 ε ,作为网络的初始连接.对于任意属于集合 v 的节点 i 来说,其邻居节点集合可以表示为
N = { j ∈ v :|| p − i p j ||≤ R } .
i

在网络演化过程中, ,v ε 中不断有新的元素加入,直至网络初始化结束.演化过程中,节点的加入与连边的选
择可以描述为以下两个步骤:

(1) 网络扩充:随机生成初始网络 (, )Gv ε 之后,每次从 {:ii v∈ ∩∉ } v 中随机选取一个节点 x,添加到集合
i

v 中.

(2) 选择连接概率:新加入的节点 x 与 v 中现有节点形成 m 条新的连边,连接概率与节点之间的二跳共同
邻居数目成正比.
T C _( , )y x
P , xy = (7)
∑ T C _( , )z x
∈
zN x
我们之所以选择二跳共同邻居作为衡量节点连接概率的依据,是因为二跳共同邻居数目越多意味着两个
节点的相似性越高,两者之间产生连接的可能性也就越大,同时也表示该节点能够为新加入节点提供更强的保
护力.新加入的节点选择相似度高、保护能力强的节点进行连接,有利于提升网络整体的可靠性与稳定性.
2.3 网络维护
通信网络的初步形成并不意味着我们的工作就到此结束,在执行任务的过程中,通信网络结构会发生变化