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

3560 Journal of Software 软件学报 Vol.31, No.11, November 2020

[4]
制的启发性原则最早是由 Reynolds 提出的 ,该原则包括 3 部分内容:(1) 集群中心:始终试图与邻近的智能体
保持较近的距离.(2) 冲突避让:避免与邻近智能体发生碰撞.(3) 速度匹配:邻近的智能体尝试进行速度匹配.这
3 项原则通常也称成为聚合、分离和对齐原则.在此原则的基础上,无人机集群需要面临的主要问题是组队与躲
避障碍物.栅格法、神经网络方法和人工势场法是目前解决群体编组避障控制问题的主要办法 [5−7] .
无人机集群中控制方法的有效实施离不开彼此之间的信息交换,而在实际应用中,无人机之间的无线通信
存在诸多不确定因素的影响,例如无人机发射功率较低并且处理能力不足导致无人机的通信范围有限、无人机
移动性导致无人机网络的间歇连接和动态拓扑,这些问题的存在,无疑给无人机网络的体系结构设计、协议与
[8]
资源配置方案带来了挑战 .
为了解决上述问题,许多学者针对无人机的通信问题展开研究.文献[9]为了保障数据传输速率,同时延长无
人机网络的生命周期,提出了一种节能高效协作中继方案.此外,无人机可以被看作是飞行的机器人,因此许多
研究通过控制无人机的运动来达到优化网络性能的目的.在文献[10]中,fadlullah 等人提出了一种动态轨迹控制
算法,旨在提升无人机网络的吞吐量和延时.文献[11]对无人机网络和 D2D 通信网络共存的情况进行建模,并使
用随机几何学对无人机网络的覆盖概率和传输速率进行了推导.文献[12]在保证网络原有稀疏程度的条件下,
提出了一种网络规则化方法,可以将随机连通网络转换为规则网络,以提升网络的鲁棒性.文献[13]对无人机网
络的连通性进行了建模与分析,提出了一种基于无人机移动特性与通信信道特征的信任模型,推导得到网络的
物理连通概率和安全连通概率.
尽管现有研究对无人机集群的实现与应用起到了极大的推动作用,但在目前对无人机集群网络的研究中,
始终忽视了一个非常重要的问题.集群在执行任务过程中将面对诸多扰动,例如无人机功能失效、恶意攻击等
等.这些扰动将会造成集群网络结构的变化,严重时甚至会破坏无人机通信网络的完整度,导致集群中的信息传
输受阻.所以,构建面临扰动依然能够维持通信可靠的无人机网络,是一个值得研究的热点问题.文献[14]中指出,
链路预测方法可以用于分析已知节点之间、已知节点与未知节点之间、已知节点与未来节点之间的连接概率.
因此,本文致力于使用链路预测方法构建无人机群体通信网络,以解决群体工作过程中因节点失效而导致的网
络不可靠问题.
本文的主要工作可以归纳为以下几点:(1) 提出二跳共同邻居指标;(2) 提出考虑网络初始化与网络维护的
基于二跳共同邻居指标的链路预测(link prediction based on two-hop common neighbor,简称 LPTCN)网络演化
算法;(3) 从理论证明与实验验证两个角度证实了 LPTCN 网络演化算法的有效性.

1 二跳共同邻居

文献[15]的研究结果表明,复杂网络在随机故障之下的抗毁性与网络的非均匀性正相关.文献[16]指出:节
点间的相似性越强,节点间产生连边的概率越高,在相似性高的节点之间建立通信链路有助于提升网络性能.故
而使用网络非均匀性与结构相似性能够描述复杂网络的性质.在本节中,我们提出了二跳共同邻居指标,期望这
一指标能够同时刻画复杂网络非均匀性和结构相似性,为后续网络演化模型的构建提供基点.
1.1 二跳共同邻居定义

复杂网络中,节点的度值是反映网络非均匀性的指标之一.最大度值与最小度值的差值越大,意味着网络非
均匀性越强;相反,非均匀性越弱.共同邻居数目则是最常用的描述节点之间相似性的指标,它表示两个节点通
信范围重叠区域内存在的节点个数,反映了节点间在网络拓扑结构层面上的联系.考虑到上述两个指标各自的
特性,我们将两者进行结合,提出二跳共同邻居指标.
定义 1. 无人机集群网络可以用图 G(v,ε)进行描述,其中,v={1,2,…,n}代表集群中所有节点的集合,ε={(i,j)}
表示集群中所有通信连边的集合.对于任意节点 x,与它之间存在通信连边的所有节点构成集合 E x ={z:(x,z)∈ε},
我们将 E x 中所有节点与节点 y 的共同邻居数量总和称为节点 x 与节点 y 的二跳共同邻居.我们使用 C N_(z,y) 表示
节点 z 与节点 y 的共同邻居数目,T C_(x,y) 表示节点 x 与节点 y 的二跳共同邻居数目.那么根据二跳共同邻居的定
义,其数学表达为