基于深度图嵌入的无人机自组网链路预测

舒坚，王启宁，刘琳岚

（1.南昌航空大学软件学院，江西 南昌 330063；2.南昌航空大学信息工程学院，江西 南昌 330063）

1 引言

无人机是空天地一体化信息网络的重要组成部分，因其灵活性、高速移动性和低成本特性得到了广泛应用[1]。集群组网技术是无人机领域的一项关键技术。如图1 所示，无人机自组网是一种不完全依赖地面控制站且在需要时构建的快速移动自组织网络[2]。由于无人机的高速移动和稀疏分布使网络连通性无法保证，符合机会网络不一定存在完整通信路径的基本假设[3]。针对无人机自组网的机会特性，设计有效的链路预测算法，推断无人机间产生连接的概率，认识其网络演化规律，可为上层路由协议提供支撑[4-5]。

图1 无人机自组网

目前，链路预测方法可分为基于相似性的链路预测方法、基于似然分析的链路预测方法和基于机器学习的链路预测方法。

基于相似性的链路预测方法又分为基于节点属性相似性的链路预测方法和基于网络结构相似性的链路预测方法。前者利用节点间属性的相似程度对节点间关系进行分析，后者则利用共同邻居（CN,common neighbor）、Katz、Jaccard 等指标[6]进行分析。Ismail 等[7]提出一种混合 CN、Adamic-Adar、Jaccard 等指标的链路预测方法，使用时间序列模型预测以上指标随时间变化的规律。Chuan 等[8]在文献[7]的基础上，考虑节点属性相似度，提出一种基于隐狄利克雷分配的混合相似性指标。Rafiee 等[9]为了更好地融合多个指标，引入聚类系数惩罚不同相似性指标的影响。基于相似性的链路预测通过人工设定的有限特征集反映网络特性，难以应对非线性网络特征关系的表征问题，随着网络规模的增加，仅使用相似性作为链路预测的依据已无法满足复杂网络的研究需求。

基于似然分析的链路预测方法通过最大化网络似然计算每个节点产生连接的可能性[6]。Pan 等[10]基于哈密顿函数的预定义框架计算网络连接概率，根据新增链路的条件概率评价连接产生的可能性。Pech 等[11]根据相邻节点的线性求和展开得到最优似然矩阵的解析解作为节点间存在链路的可能性，同时适用于有向含权网络。基于似然分析的链路预测方法时间复杂度较高，且实际网络中存在链路丢失、伪造链路等噪声数据，通过似然分析法难以全面考虑复杂的网络环境。

基于机器学习的链路预测方法能够提取更复杂的网络特征[12]。Wang 等[13]使用半监督的深度模型对网络进行表征，能够同时提取网络局部信息和全局信息。Pan 等[14]使用自编码器、变分自编码器分别对网络进行嵌入，再由生成器预测网络的拓扑结构。Li 等[15]通过循环神经网络实现图嵌入，根据交互邻近度判断节点对产生连接的概率。Chen 等[16]在文献[15]的基础上构建了基于编码解码结构的通用链路预测框架。

得益于自然语言处理的发展，DeepWalk[17]、LINE（large-scale information network embedding）[18]、Node2vec[19]等基于随机游走的网络表征方法被提出。Dai 等[20]通过对抗训练方法增强了DeepWalk等图嵌入方法的泛化性和稳健性。Du 等[21]改进了skip-gram 模型，可增量训练产生变化的部分节点。

上述研究表明，采用机器学习的方法在复杂网络的链路预测研究中具有显著优势，但是在图中直接进行机器学习具有局限性，通过图嵌入技术将其映射至低维的向量空间后，可具有丰富灵活的计算方式。本文提出一种基于深度图嵌入的无人机自组网链路预测方法，其流程如图2 所示，采用时序化图嵌入模型（CGEM,chronological graph embedding model）将一组网络快照中的空间结构特征和上下文语义特征进行嵌入，再使用长短期记忆（LSTM,long short-term memory）网络提取嵌入向量中的时序特征，预测无人机自组网的链路。

图2 基于深度图嵌入的链路预测方法流程

本文主要创新点如下。

1) 提出时序化图嵌入模型表征无人机自组网，通过时序化采样捕获无人机自组网结构特征，采用对抗训练提取目标节点的上下文语义特征。

2) 提出一种离散化采样方法，基于线性概率计算采样间隔，以提高采样效率。

2 问题定义

文中所涉及的符号及描述如表1 所示。

表1 符号及描述

2.1 无人机自组网

本节针对无人机自组网的灵活性、高速移动性等特点，对原始网络数据进行量化。当某一节点处于邻居节点的通信范围时，将产生一条有向的连接，该连接显示节点间建立了有效的通信链路。为描述网络的动态性，本文采用离散的网络快照G={G1,G2,…,GT}表示无人机集群的动态网络数据。将每个快照表示为G t={Vt,Et}。连接所代表的通信链路是单向的，具有相应的权重，连接的细粒度表示为eij=[v i,vj,wij]，其中，vi和vj分别代表节点i和节点j，wij代表该连接的权重。

网络的结构特征隐含于所有无人机在某一时刻呈现的拓扑关系中；在一段时间内无人机将进行多次信息传递，信息所流经的路径由不同无人机节点组成，上下文语义特征隐含于该路径上节点与邻居间的关系中；网络随时间的演化导致结构特征与上下文语义特征不断变化，网络的时序特征隐含于数据不断变化所形成的序列中。本文根据以上3 种特征进行链路预测。

2.2 链路预测

给定一组长度为N的网络快照序列，St−1= {Gt−N,…,Gt−1},St−1⊆G，链路预测的目标为学习一个可以将序列St−1映射到Gt的预测函数P。

无人机自组网的网络结构随时间不断变化。如图3 所示，从序列St−1中提取网络结构的演化规律，预测下一时刻的网络结构Gt。

图3 无人机自组网中链路预测

3 数据预处理与时序化图嵌入

为更好地提取无人机自组网的拓扑演化规律，本文提出时序化图嵌入模型CGEM 对预处理后的无人机自组网进行表征。

3.1 数据预处理

无人机自组网是一种有向含权图，需要将节点间的相对位置转化为权重信息。考虑信息传输时的损耗，本文根据节点间的距离d(i,j)和当前无人机的最大通信半径Di计算权重。权重计算式为

其中，γ(i,j)为信噪比，信噪比越大，节点间产生的链路越稳定。通过计算各节点间的权重得到邻接矩阵，随着网络规模和时间跨度的增加，数据量不断增长，若仍然采用邻接矩阵表示网络将面临维数灾难问题。图嵌入技术可对复杂网络进行降维，且能更加灵活地表示节点与连接。因此，本文构建时序化图嵌入模型对无人机自组网进行表征。

3.2 时序化图嵌入模型

通过图嵌入模型可将无人机自组网的特征映射至低维向量空间，降低预测的复杂性。无人机自组网节点间的交互表现为节点对的连接和断开，其内部交互关系[22]到节点嵌入向量关系的转化如图4所示，向量空间中保持连接的节点彼此靠近。

图4 内部交互关系到节点嵌入向量关系的转化

由于无人机自组网的拓扑变化较快，仅在某一时刻进行图嵌入无法反映无人机自组网内部真实的交互关系。CGEM 在一组长度为N的快照序列St上进行嵌入，该过程实际上是在寻找一个从网络G到嵌入矩阵的映射，其中表示第i个快照序列形成的嵌入矩阵，由网络中全部节点的嵌入向量组成，即。

嵌入向量ui是网络中节点vi在向量空间中的映射。网络中节点vi与vj建立连接时，连边eij=1，连边的权重决定连接的紧密程度。在向量空间中通过ui与uj之间的距离dij表示vi与vj的交互关系，将dij表示为

其中，fdis是计算ui和uj之间距离的函数，dij越小节点vi与vj连接的概率越大，dij越大节点vi与vj连接的概率越小。本文通过随机采样获取快照序列St中的共现对{(vi,v j)|eij=1}，最小化向量空间中的距离dij，得到嵌入矩阵。

时序化图嵌入模型如图5 所示。在时序化采样阶段，选取一个初始快照Gt−N，按顺序向后划定一组长度为N的快照序列St−1。在Gt−N中选取初始节点v0作为游走路径的起始节点，下一跳节点的选取概率根据节点间的权重比例计算，如式(4)所示。

根据P(v i|vi−1)随机选取下一跳节点，权重wij越大被选中的概率越大，当节点出度为0 或到达快照Gt−1时停止采样。时序化采样在快照序列中进行多次游走，最终将得到多条不同长度的游走路径。

为提取节点间的关系映射，在游走路径中设置滑动窗口，逐一选取目标节点和上下文节点，形成一系列代表邻近关系的共现对。如图5 所示，当v3为目标节点且窗口值为3 时，所形成的共现对从左到右分别为 (v3,v0),(v3,v1),(v3,v4),(v3,v2)。

图5 时序化图嵌入模型

使用嵌入模型将以上关系映射至低维向量空间，向量间的关系代表了节点在空间中联系的紧密程度。嵌入向量为

其中，u i,uj分别为节点i,j的嵌入向量，将向量视为一阶矩阵，ujT为uj的转置。若节点i,j在实际网络中距离较近，当且仅当向量u i,uj相近，即的值接近1 时，嵌入损失 Lemb降低。通过最小化嵌入损失，得到节点的嵌入向量。

由于无人机集群间的通信不完全依赖基站进行传输，因此网络数据的传输需经过多跳转发实现，而多次传输过程中会产生数据丢失现象，从而使收集到的网络数据存在噪声。为了提高嵌入模型的泛化性和稳健性，CGEM 采用对抗训练正则化来降低模型对噪声的敏感度，对抗训练算法在3.4 节介绍。

3.3 采样分析

进行链路预测时，越接近待预测时刻的网络快照信息越重要。当网络快照数较多时，游走得到的路径较长，导致CGEM 的训练时间延长。为解决这一问题，本文提出一种离散化采样法优化时序化采样过程，在每一次采样结束后根据概率公式计算下一跳采样间隔。

离散化采样在选取下一跳节点时，不一定在连续的网络快照中进行，下一跳节点所在快照的时间刻度tc+k大于当前节点所在快照的时间刻度tc，即tc+k>t c,k∈N*，k为采样间隔。本文给出2 种概率计算式作为下一跳网络快照的选择依据，分别根据线性函数和指数函数计算概率分布。

线性概率下采样间隔的计算式为

其中，tc为当前快照所对应的时间刻度，tc+k为下一跳将要选取的网络快照所对应的时间刻度，P(k)为k的选取概率。

如果快照序列长度N较长，需增加靠近待预测时刻网络快照的选取概率，此时可根据式(7)计算指数概率下的采样间隔。

其中，exp(⋅)是以自然常数e 为底的指数函数。线性概率和指数概率下采样间隔与选取概率的关系如图6 所示。采样间隔越大被选取的概率越大，指数概率相对线性概率的这一趋势更显著。

图6 采样间隔与选取概率的关系

快照序列长度N=100、250、500 时，基于线性概率和指数概率的离散化采样对AUC（area under the receiver operating characteristic curve）的影响情况如图7 所示。

图7 不同离散化采样方式下的AUC 对比

当N=100时，基于指数概率比基于线性概率的离散化采样获得的AUC 分值高，但此时2 种离散化采样的效果都较差；当N=250时，基于线性概率比基于指数概率的离散化采样获得的AUC 分值较高，原因在于基于指数概率的离散化采样丢失了较多的样本，导致模型缺乏对网络细节的表征；当N=500时，2 种离散化采样的效果基本相同，原因在于快照序列长度过长时，早期网络快照的结构对预测结果的影响较小。

3.4 训练及优化

对抗训练方法使模型的局部趋于平滑，不仅增加了模型的泛化能力，而且降低了噪声对图嵌入模型表征能力的影响。本文将对抗训练方法引入CGEM，以解决连续对抗扰动无法直接应用到离散化网络数据中的问题[20]。

对抗训练方法通过向原始嵌入中加入对抗扰动来提升模型的稳健性，为防止加入的噪声过大，采用自适应尺度指标和基于L2范数的扰动上限来规范对抗扰动项。对抗扰动为

其中，L 表示模型嵌入的损失，嵌入结果加入对抗扰动使模型的损失最大化，且限制该扰动所造成的损失保持在限定值ε内，ε根据实际情况确定。采用快速梯度下降法[20]训练对抗扰动项，扰动的更新式为

其中，Δg为当前的截断梯度，||Δg||2为梯度的二范数，用于限制扰动。梯度为

其中，为当前训练中截断梯度传播的模型参数，用于限制扰动项的大小，当梯度变化较大时扰动项相对较小，从而保证添加的对抗扰动尽量减少对CGEM 嵌入能力的影响。自适应尺度指标根据节点间的相似性确定，节点嵌入相似性越高自适应尺度越小，从而抑制扰动的程度越大，降低对嵌入结果的影响。本文定义自适应尺度为

其中，normalize(⋅)为正则化函数。节点间权重wij越大，代表无人机节点对之间的距离越小，自适应尺度对扰动的约束越大。对抗训练正则化项定义为节点嵌入向量与自适应对抗扰动的交叉熵

通过CGEM 得到网络的嵌入后，即可直接使用分类器预测未来的网络连接结构。但此时存在以下问题：首先，使用CGEM 的嵌入向量进行链路预测仅考虑了动态网络的结构特征，忽略了网络演化过程中的时序特征；其次，CGEM 只能嵌入网络中短时间内曾产生过连接的节点，不能反映长时间的网络演化规律。因此，本文将借助LSTM 实现对无人机自组网的链路预测。

4 链路预测

本节采用LSTM 构建预测模型，提取连续变化的嵌入矩阵中所隐含的时序特征。

4.1 模型的构建

链路预测模型的目的是将CGEM 计算得到的嵌入矩阵进一步转化为下一时刻的网络拓扑结构。该模型分为LSTM 层和基于多层神经网络的解码器层，经过解码器输出下一时刻网络的邻接矩阵。

如图8 所示，St−1为一组连续网络快照所形成的序列，随着窗口向后滑动产生一系列的网络快照序列 {St−1,St,…}，通过CGEM 将其转化为对应的嵌入矩阵序列，下一步则按顺序输入LSTM 模型中提取网络演化过程中的序列化特征，最终得到输出序列 {ht,ht+1,…} 。每一个隐层结果经过解码器，将LSTM 层每一次输出的结果ht解码为下一时刻的网络邻接矩阵，完成对整网拓扑的预测。

图8 基于LSTM 的链路预测模型

首先构建用于提取网络时变特征的 LSTM模型[16]，LSTM 单元由遗忘门、输入门和输出门组成。遗忘门决定将哪些信息从以前的单元格状态中丢弃，因此输入CGEM 的嵌入向量，同时输入上一单元的输出结果ht−1，Wf决定ht−1对输入向量的影响，计算值越小对上一单元信息丢弃的越多。

遗忘门的计算式为

输入门决定着应该向当前单元加入哪些新的信息。该门包含3 个部分：1) Sigmoid 层，用于计算it，it决定输入将包含哪些信息，因此与遗忘门相同，不仅需要输入嵌入向量还要输入上一层的输出ht−1；2) tanh 层，用于计算，生成候选状态值向量，该层同样根据嵌入向量和上一层输出结果计算状态值向量；3) 结合Sigmoid 层和tanh 层的结果得到Ct，Ct作为当前需要记忆的信息，结合遗忘门和记忆层计算，遗忘门输出值越大则上一单元输入门的影响越大。

输入门的计算式为

其中，⊙为哈达玛积。结合遗忘门和输入门，LSTM不仅可以提取长期的有效信息，还可以丢弃不需要的信息。而输出门基于输入门的输出结果Ct，决定输出给下一层单元的结果ht。

输出门的计算式为

本文使用一个LSTM 单元学习时间依赖特征，根据实际情况改变LSTM 的单元数，增加单元使模型具有更好的时间序列处理能力，同时随着单元数的增加会需要更多的数据对模型进行训练。得到最终的输出层结果ht后，将其输入解码器单元进行解码。解码器由两层的多层感知机（MLP,multilayer perceptron）组成，使用ReLU 作为第一层的激活函数，加速模型的收敛速度，得到输出yd。第二层输出层使用Sigmoid 作为激活函数，得到网络在时刻t的网络邻接矩阵。

双层神经网络的计算式为

至此完成对基于LSTM 的链路预测模型的构建，其中模型的输入为CGEM 的嵌入向量，LSTM单元负责学习网络演化的时序特征，最终经过解码器输出下一时刻的网络邻接矩阵，得到网络全局的链路预测结果。

4.2 预测模型的训练

该链路预测模型的损失函数由预测损失 Lp、交叉熵损失 Lc和正则化项 Lreg组成，预测损失关注预测结果和真实值At间的差值，考虑无人机自组网的稀疏性及预测模型的过拟合问题，应关注真实所产生的连接而不是反向传播中不存在的连接。模型的预测损失为

其中，Z是由zi,j组成的矩阵；zi,j为约束值，用于调节稀疏网络环境中零元素对预测倾向的影响，避免出现预测结果全为零的情况。zi,j的计算式为

交叉熵损失关注的是预测结果相对真实值的误差，通过引入交叉熵损失 Lc可以进一步提取嵌入矩阵中的结构特征，如式(19)所示。

综上所述，结合预测损失和交叉熵损失，考虑到模型可能产生的过拟合问题，在最终目标函数中引入正则化项，通过计算模型各参数矩阵的L2范数之和作为最终的正则化项，越小参数矩阵越稀疏，从而防止过拟合。链路预测模型的目标函数为

其中，β和ρ为超参数。

4.3 时间复杂度分析

图嵌入过程中首先进行时序化采样。若网络中存在n个节点，每个节点循环采样R次，网络快照的输入序列长度为N，则时序化采样的时间复杂度为O(RNn)。设置形成共现对的窗口值为K，则生成共现对的时间复杂度为O((N−K+1)⋅(K− 1))=O(NK)，共有Nn条时序化采样序列，对每一个共现对执行一次优化，则训练嵌入向量的时间复杂度为O(EN2Kn)，其中，E为模型的执行轮次。由于在CGEM 中需要以一次未添加对抗扰动的优化过程进行初始化，因此E＞1，但E仍为一个较小的参数，多次实验显示E=2 为最佳执行轮次。K作为共现对的观测窗口通常也取较小的常数值。去掉其中较小的常量，CGEM 的时间复杂度为

本文使用基于线性概率分布的离散化采样，增加了采样间隔，使N在最优情况下等于K。由于游走和优化的过程支持并行计算，因此实际的计算速度更快。

与其他深度学习模型类似，基于深度学习的预测模型LSTM-Decoder 的复杂性取决于模型的权值，m1为LSTM 的单元数，m2为Decoder 层多层感知机的单元数，则时间复杂度为

同样地，模型可通过GPU 并行计算进行加速。因此，本文方法的时间复杂度为

本文在Intel i5-6850K 和GTX1080Ti 环境下进行实验，设定输入序列长度N=25 时，图嵌入模型平均耗时为89 ms，最大耗时为163 ms，最小耗时为54 ms；预测模型平均耗时为0.6 ms，最大耗时为1.3 ms，最小耗时为0.5 ms。综上可得，在无人机自组网中执行一次预测平均耗时为89.6 ms。

5 实验与分析

本文采用Ns-3 平台模拟无人机自组网，获取无人机集群在指定区域内执行任务的仿真数据。使用链路预测经典评价指标AUC、MAP（mean average precision）和Error Rate[16]验证本文模型。

5.1 实验设计

1) 实验数据集

无人机集群移动模型参数设置如表2 所示。

表2 无人机集群移动模型参数

仿真数据格式如图9 所示，记录每个无人机节点的位置信息和获取数据的时间。

图9 仿真数据格式

无人机自组网是无人机集群在不完全依赖地面控制站且在需要时临时构建而成的快速移动自组织网络。通过NetAnim 可以观察到无人机自组网中无人机集群的分布。无人机集群按“狗仔队”移动模型[23]在区域内进行搜寻的可视化结果如图10 所示，状态分别为扇状扩散、覆盖搜索域和8 字盘旋。

图10 “狗仔队”移动模型下的无人机集群分布

网络快照连接数量如图11 所示。在0～1 500 s时，处于扫描阶段的无人机集群从起点出发向四周扩散，由于起始距离相对较近，此时网络中连接数较多且变化迅速；1 500 s 后，无人机集群不断扩散至覆盖目标空域，进入盘旋阶段，此时网络较稳定，连接数的变化较缓慢。

图11 网络快照连接数量

2) 实验场景设计

本文设置了3 组实验场景，具体描述如下。

实验1验证模型参数对实验结果的影响。设置快照序列长度分别为(100,150,200,…,450,500)，窗口滑动步长分别为(10,20,30,40,50)，两两组合进行实验，确定模型的最优快照序列长度和窗口滑动步长，并通过机械抽样法验证LSTM 模型的单元数对实验结果的影响。

实验2验证本文链路预测算法的有效性。将本文提出的CGEM-LSTM 链路预测方法与经典的CN 和 Katz 算法、基于节点嵌入的方法Node2vec[19]，以及基于图嵌入的方法DDNE（deep dynamic network embedding）[15]和E-LSTM-D[16]进行对比，验证本文链路预测方法的有效性。其中，基于相似性指标的链路预测方法以节点相似程度作为节点间产生连接的概率。为确保实验的合理性，所有对比实验都将在本文最佳模型参数的数据样本下进行实验。

实验3比较CGEM 与其他基于随机游走的图嵌入模型对无人机自组网的表征能力。通过逻辑回归分类器和本文提出的基于LSTM的链路预测模型对比DeepWalk[17]、LINE[18]、Node2vec、CGEM 这4 种嵌入方法的网络表征能力。

3) 评价指标

AUC 计算式为

其中，M为比较次数，M'为正例中所选边的分数大于反例中所选边分数的次数，M''为两者相等的次数。M'和M''越大，说明正例分数高于反例分数的概率越大，预测准确率越高。

MAP 计算式为

其中，AP 为P-R（precision-recall）曲线下的面积。

其中，节点vi和vj间有连接的集合表示为{ai,j=1}。MAP 用于衡量预测结果的精确性。

Error Rate 为错误的连接LNfalse占所有真实存在连接LNtrue的比例，与仅在两图中计算绝对不同连接的SumD 指标不同，Error Rate 考虑了真实存在的连接数。Error Rate 计算式为

5.2 实验结果与分析

5.2.1 实验1

模型的快照序列长度N和窗口滑动步长Δt对模型的预测精度和效率都有影响。序列中包含了一段时间内网络的拓扑演化情况，如果长度选取较长，在相同维度的嵌入向量中将缺失网络结构在细节上的表示；若选取的长度较短，相同维度下的嵌入向量则可能产生过拟合现象。窗口滑动步长决定了嵌入向量之间的差异，若步长较大，则所产生的向量将丢失网络演化的细粒度特征；反之则影响模型的执行效率。选取网络连接数变化较大的时段0～3 000 s，图12～图14 分别反映了窗口滑动步长Δt取{10,20,30,40,50}时，不同快照序列长度N对AUC、MAP、Error Rate 的影响情况。

图12 不同快照序列长度和窗口滑动步长下的AUC

图13 不同快照序列长度和窗口滑动步长下的MAP

图14 不同快照序列长度和窗口滑动步长下的Error Rate

从整体来看，在不同的快照序列长度和窗口滑动步长下，模型都具有较好的预测效果。当快照序列长度N=250时，预测结果的AUC、MAP 和Error Rate 值相对较高，模型预测结果最优。当窗口滑动步长 Δt= {10,20,30}时，AUC 稳定在0.98 以上，MAP 稳定在0.9 以上，Error Rate 稳定在1.0以下，且在Δt=10时模型表现最佳。综合以上3 种评价指标的实验结果，本文确定快照序列长度为250，滑动窗口步长取10。

本文提出的链路预测方法通过LSTM提取网络的序列化特征，LSTM 的unit 决定了输出隐层向量的维度。如图15 所示，设置不同的unit 值进行预测，通过模型的AUC 及LOSS 最终确定unit=500。

图15 不同unit 下的AUC 及LOSS

5.2.2 实验2

由实验1 可确定模型的最佳参数如下：快照序列长度N=250，窗口滑动步长=10。实验2 的目的是衡量本文提出的基于CGEM 和LSTM 的链路预测方法与其他链路预测方法的性能。为确保实验的合理性，所有对比实验都将在本文最佳模型参数的数据样本下进行实验。对每组实验进行40 次采样，计算对应的AUC、MAP 和Error Rate，实验结果如图16～图18 所示。

图16 在测试集中40 次采样下的AUC

图17 在测试集中40 次采样下的MAP

图18 在测试集中40 次采样下的Error Rate

从图 16～图 18 可以看出，本文所提CGEM-LSTM 在AUC、MAP 和Error Rate 下都具有良好的表现，并且可以从图中曲线的波动观察到，本文方法在40 次采样结果中相对其他方法更加平稳。

表3 为40 次采样结果的平均值。与同属深度图嵌入方法的DDNE 相比，本文方法的AUC 提高了2.77%，MAP 提高了14.07%，Error Rate 降低了1.39；与E-LSTM-D 相比，本文方法的AUC 提高了0.91%，MAP 提高了4.91%，Error Rate 降低了0.40。由此可见，本文方法的模型可较好地学习无人机自组网的拓扑演化规律。

表3 链路预测效果对比

5.2.3 实验3

设置快照序列长度为250，窗口滑动步长为10，选取网络连接变化较频繁的0～3 000 s 内对模型的嵌入效果进行对比。通过逻辑回归分类器对嵌入向量进一步处理，嵌入效果如表4 所示。

从表4 可以看出，CGEM 相对Node2vec 的链路预测结果较差，但CGEM 的MAP 和Error Rate值相对Node2vec 更好。从嵌入的原理来看，Node2vec需在每一个快照中进行游走得到节点序列，而CGEM则在一组网络快照中进行游走，得到的节点序列相对Node2vec 较少，且算法执行效率更高。CGEM 的Error Rate比LINE高0.62，但其AUC和MAP均高于LINE，其原因在于CGEM 引入了对抗训练方法，而逻辑回归模型不能有效地对其所添加的噪声进行拟合。综合来看，CGEM 仍具有较好的嵌入效果。

表4 嵌入效果对比（逻辑回归分类器）

通过LSTM 对嵌入向量进一步处理，嵌入效果如表5 所示。

表5 嵌入效果对比（LSTM）

从表5 可以看出，结合LSTM 进行链路预测时具有更好的评价效果，这表明模型对动态网络的序列化特征进行提取是有意义的。对表4、表5 分析可得，本文提出的链路预测模型相对于其他基于随机游走的链路预测模型具有较好的预测效果。

6 结束语

本文提出基于深度图嵌入的无人机自组网链路预测方法。通过对无人机自组网内部交互关系的分析构建时序化图嵌入模型，将网络连接状况转化为节点嵌入向量间的距离关系。采用LSTM 提取不同时刻嵌入矩阵中隐含的时序特征，实现对下一时刻网络连接的预测，并结合实现过程分析了预测方法的时间复杂度。

随着网络规模的增加，在无人机自组网中进行链路预测的计算效率将面临挑战。下一步工作可通过引入图神经网络算法，提升模型的嵌入效果，从而降低预测模型的样本规模，提高训练效率。