基于深度圖嵌入的無人機自組網鏈路預測

舒堅，王啟寧，劉琳嵐

（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 提取不同時刻嵌入矩陣中隱含的時序特征，實現對下一時刻網絡連接的預測，并結合實現過程分析了預測方法的時間復雜度。

隨著網絡規模的增加，在無人機自組網中進行鏈路預測的計算效率將面臨挑戰。下一步工作可通過引入圖神經網絡算法，提升模型的嵌入效果，從而降低預測模型的樣本規模，提高訓練效率。