舒堅，王啟寧，劉琳嵐

（1.南昌航空大學(xué)軟件學(xué)院，江西 南昌 330063；2.南昌航空大學(xué)信息工程學(xué)院，江西 南昌 330063）

1 引言

無人機是空天地一體化信息網(wǎng)絡(luò)的重要組成部分，因其靈活性、高速移動性和低成本特性得到了廣泛應(yīng)用[1]。集群組網(wǎng)技術(shù)是無人機領(lǐng)域的一項關(guān)鍵技術(shù)。如圖1 所示，無人機自組網(wǎng)是一種不完全依賴地面控制站且在需要時構(gòu)建的快速移動自組織網(wǎng)絡(luò)[2]。由于無人機的高速移動和稀疏分布使網(wǎng)絡(luò)連通性無法保證，符合機會網(wǎng)絡(luò)不一定存在完整通信路徑的基本假設(shè)[3]。針對無人機自組網(wǎng)的機會特性，設(shè)計有效的鏈路預(yù)測算法，推斷無人機間產(chǎn)生連接的概率，認(rèn)識其網(wǎng)絡(luò)演化規(guī)律，可為上層路由協(xié)議提供支撐[4-5]。

圖1 無人機自組網(wǎng)

目前，鏈路預(yù)測方法可分為基于相似性的鏈路預(yù)測方法、基于似然分析的鏈路預(yù)測方法和基于機器學(xué)習(xí)的鏈路預(yù)測方法。

基于相似性的鏈路預(yù)測方法又分為基于節(jié)點屬性相似性的鏈路預(yù)測方法和基于網(wǎng)絡(luò)結(jié)構(gòu)相似性的鏈路預(yù)測方法。前者利用節(jié)點間屬性的相似程度對節(jié)點間關(guān)系進行分析，后者則利用共同鄰居（CN,common neighbor）、Katz、Jaccard 等指標(biāo)[6]進行分析。Ismail 等[7]提出一種混合 CN、Adamic-Adar、Jaccard 等指標(biāo)的鏈路預(yù)測方法，使用時間序列模型預(yù)測以上指標(biāo)隨時間變化的規(guī)律。Chuan 等[8]在文獻[7]的基礎(chǔ)上，考慮節(jié)點屬性相似度，提出一種基于隱狄利克雷分配的混合相似性指標(biāo)。Rafiee 等[9]為了更好地融合多個指標(biāo)，引入聚類系數(shù)懲罰不同相似性指標(biāo)的影響?；谙嗨菩缘逆溌奉A(yù)測通過人工設(shè)定的有限特征集反映網(wǎng)絡(luò)特性，難以應(yīng)對非線性網(wǎng)絡(luò)特征關(guān)系的表征問題，隨著網(wǎng)絡(luò)規(guī)模的增加，僅使用相似性作為鏈路預(yù)測的依據(jù)已無法滿足復(fù)雜網(wǎng)絡(luò)的研究需求。

基于似然分析的鏈路預(yù)測方法通過最大化網(wǎng)絡(luò)似然計算每個節(jié)點產(chǎn)生連接的可能性[6]。Pan 等[10]基于哈密頓函數(shù)的預(yù)定義框架計算網(wǎng)絡(luò)連接概率，根據(jù)新增鏈路的條件概率評價連接產(chǎn)生的可能性。Pech 等[11]根據(jù)相鄰節(jié)點的線性求和展開得到最優(yōu)似然矩陣的解析解作為節(jié)點間存在鏈路的可能性，同時適用于有向含權(quán)網(wǎng)絡(luò)?；谒迫环治龅逆溌奉A(yù)測方法時間復(fù)雜度較高，且實際網(wǎng)絡(luò)中存在鏈路丟失、偽造鏈路等噪聲數(shù)據(jù)，通過似然分析法難以全面考慮復(fù)雜的網(wǎng)絡(luò)環(huán)境。

基于機器學(xué)習(xí)的鏈路預(yù)測方法能夠提取更復(fù)雜的網(wǎng)絡(luò)特征[12]。Wang 等[13]使用半監(jiān)督的深度模型對網(wǎng)絡(luò)進行表征，能夠同時提取網(wǎng)絡(luò)局部信息和全局信息。Pan 等[14]使用自編碼器、變分自編碼器分別對網(wǎng)絡(luò)進行嵌入，再由生成器預(yù)測網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。Li 等[15]通過循環(huán)神經(jīng)網(wǎng)絡(luò)實現(xiàn)圖嵌入，根據(jù)交互鄰近度判斷節(jié)點對產(chǎn)生連接的概率。Chen 等[16]在文獻[15]的基礎(chǔ)上構(gòu)建了基于編碼解碼結(jié)構(gòu)的通用鏈路預(yù)測框架。

得益于自然語言處理的發(fā)展，DeepWalk[17]、LINE（large-scale information network embedding）[18]、Node2vec[19]等基于隨機游走的網(wǎng)絡(luò)表征方法被提出。Dai 等[20]通過對抗訓(xùn)練方法增強了DeepWalk等圖嵌入方法的泛化性和穩(wěn)健性。Du 等[21]改進了skip-gram 模型，可增量訓(xùn)練產(chǎn)生變化的部分節(jié)點。

上述研究表明，采用機器學(xué)習(xí)的方法在復(fù)雜網(wǎng)絡(luò)的鏈路預(yù)測研究中具有顯著優(yōu)勢，但是在圖中直接進行機器學(xué)習(xí)具有局限性，通過圖嵌入技術(shù)將其映射至低維的向量空間后，可具有豐富靈活的計算方式。本文提出一種基于深度圖嵌入的無人機自組網(wǎng)鏈路預(yù)測方法，其流程如圖2 所示，采用時序化圖嵌入模型（CGEM,chronological graph embedding model）將一組網(wǎng)絡(luò)快照中的空間結(jié)構(gòu)特征和上下文語義特征進行嵌入，再使用長短期記憶（LSTM,long short-term memory）網(wǎng)絡(luò)提取嵌入向量中的時序特征，預(yù)測無人機自組網(wǎng)的鏈路。

圖2 基于深度圖嵌入的鏈路預(yù)測方法流程

本文主要創(chuàng)新點如下。

1) 提出時序化圖嵌入模型表征無人機自組網(wǎng)，通過時序化采樣捕獲無人機自組網(wǎng)結(jié)構(gòu)特征，采用對抗訓(xùn)練提取目標(biāo)節(jié)點的上下文語義特征。

2) 提出一種離散化采樣方法，基于線性概率計算采樣間隔，以提高采樣效率。

2 問題定義

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

表1 符號及描述

2.1 無人機自組網(wǎng)

本節(jié)針對無人機自組網(wǎng)的靈活性、高速移動性等特點，對原始網(wǎng)絡(luò)數(shù)據(jù)進行量化。當(dāng)某一節(jié)點處于鄰居節(jié)點的通信范圍時，將產(chǎn)生一條有向的連接，該連接顯示節(jié)點間建立了有效的通信鏈路。為描述網(wǎng)絡(luò)的動態(tài)性，本文采用離散的網(wǎng)絡(luò)快照G={G1,G2,…,GT}表示無人機集群的動態(tài)網(wǎng)絡(luò)數(shù)據(jù)。將每個快照表示為G t={Vt,Et}。連接所代表的通信鏈路是單向的，具有相應(yīng)的權(quán)重，連接的細(xì)粒度表示為eij=[v i,vj,wij]，其中，vi和vj分別代表節(jié)點i和節(jié)點j，wij代表該連接的權(quán)重。

網(wǎng)絡(luò)的結(jié)構(gòu)特征隱含于所有無人機在某一時刻呈現(xiàn)的拓?fù)潢P(guān)系中；在一段時間內(nèi)無人機將進行多次信息傳遞，信息所流經(jīng)的路徑由不同無人機節(jié)點組成，上下文語義特征隱含于該路徑上節(jié)點與鄰居間的關(guān)系中；網(wǎng)絡(luò)隨時間的演化導(dǎo)致結(jié)構(gòu)特征與上下文語義特征不斷變化，網(wǎng)絡(luò)的時序特征隱含于數(shù)據(jù)不斷變化所形成的序列中。本文根據(jù)以上3 種特征進行鏈路預(yù)測。

2.2 鏈路預(yù)測

給定一組長度為N的網(wǎng)絡(luò)快照序列，St?1= {Gt?N,…,Gt?1},St?1?G，鏈路預(yù)測的目標(biāo)為學(xué)習(xí)一個可以將序列St?1映射到Gt的預(yù)測函數(shù)P。

無人機自組網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)隨時間不斷變化。如圖3 所示，從序列St?1中提取網(wǎng)絡(luò)結(jié)構(gòu)的演化規(guī)律，預(yù)測下一時刻的網(wǎng)絡(luò)結(jié)構(gòu)Gt。

圖3 無人機自組網(wǎng)中鏈路預(yù)測

3 數(shù)據(jù)預(yù)處理與時序化圖嵌入

為更好地提取無人機自組網(wǎng)的拓?fù)溲莼?guī)律，本文提出時序化圖嵌入模型CGEM 對預(yù)處理后的無人機自組網(wǎng)進行表征。

3.1 數(shù)據(jù)預(yù)處理

無人機自組網(wǎng)是一種有向含權(quán)圖，需要將節(jié)點間的相對位置轉(zhuǎn)化為權(quán)重信息?？紤]信息傳輸時的損耗，本文根據(jù)節(jié)點間的距離d(i,j)和當(dāng)前無人機的最大通信半徑Di計算權(quán)重。權(quán)重計算式為

其中，γ(i,j)為信噪比，信噪比越大，節(jié)點間產(chǎn)生的鏈路越穩(wěn)定。通過計算各節(jié)點間的權(quán)重得到鄰接矩陣，隨著網(wǎng)絡(luò)規(guī)模和時間跨度的增加，數(shù)據(jù)量不斷增長，若仍然采用鄰接矩陣表示網(wǎng)絡(luò)將面臨維數(shù)災(zāi)難問題。圖嵌入技術(shù)可對復(fù)雜網(wǎng)絡(luò)進行降維，且能更加靈活地表示節(jié)點與連接。因此，本文構(gòu)建時序化圖嵌入模型對無人機自組網(wǎng)進行表征。

3.2 時序化圖嵌入模型

通過圖嵌入模型可將無人機自組網(wǎng)的特征映射至低維向量空間，降低預(yù)測的復(fù)雜性。無人機自組網(wǎng)節(jié)點間的交互表現(xiàn)為節(jié)點對的連接和斷開，其內(nèi)部交互關(guān)系[22]到節(jié)點嵌入向量關(guān)系的轉(zhuǎn)化如圖4所示，向量空間中保持連接的節(jié)點彼此靠近。

圖4 內(nèi)部交互關(guān)系到節(jié)點嵌入向量關(guān)系的轉(zhuǎn)化

由于無人機自組網(wǎng)的拓?fù)渥兓^快，僅在某一時刻進行圖嵌入無法反映無人機自組網(wǎng)內(nèi)部真實的交互關(guān)系。CGEM 在一組長度為N的快照序列St上進行嵌入，該過程實際上是在尋找一個從網(wǎng)絡(luò)G到嵌入矩陣的映射，其中表示第i個快照序列形成的嵌入矩陣，由網(wǎng)絡(luò)中全部節(jié)點的嵌入向量組成，即。

嵌入向量ui是網(wǎng)絡(luò)中節(jié)點vi在向量空間中的映射。網(wǎng)絡(luò)中節(jié)點vi與vj建立連接時，連邊eij=1，連邊的權(quán)重決定連接的緊密程度。在向量空間中通過ui與uj之間的距離dij表示vi與vj的交互關(guān)系，將dij表示為

其中，fdis是計算ui和uj之間距離的函數(shù)，dij越小節(jié)點vi與vj連接的概率越大，dij越大節(jié)點vi與vj連接的概率越小。本文通過隨機采樣獲取快照序列St中的共現(xiàn)對{(vi,v j)|eij=1}，最小化向量空間中的距離dij，得到嵌入矩陣。

時序化圖嵌入模型如圖5 所示。在時序化采樣階段，選取一個初始快照Gt?N，按順序向后劃定一組長度為N的快照序列St?1。在Gt?N中選取初始節(jié)點v0作為游走路徑的起始節(jié)點，下一跳節(jié)點的選取概率根據(jù)節(jié)點間的權(quán)重比例計算，如式(4)所示。

根據(jù)P(v i|vi?1)隨機選取下一跳節(jié)點，權(quán)重wij越大被選中的概率越大，當(dāng)節(jié)點出度為0 或到達快照Gt?1時停止采樣。時序化采樣在快照序列中進行多次游走，最終將得到多條不同長度的游走路徑。

為提取節(jié)點間的關(guān)系映射，在游走路徑中設(shè)置滑動窗口，逐一選取目標(biāo)節(jié)點和上下文節(jié)點，形成一系列代表鄰近關(guān)系的共現(xiàn)對。如圖5 所示，當(dāng)v3為目標(biāo)節(jié)點且窗口值為3 時，所形成的共現(xiàn)對從左到右分別為 (v3,v0),(v3,v1),(v3,v4),(v3,v2)。

圖5 時序化圖嵌入模型

使用嵌入模型將以上關(guān)系映射至低維向量空間，向量間的關(guān)系代表了節(jié)點在空間中聯(lián)系的緊密程度。嵌入向量為

其中，u i,uj分別為節(jié)點i,j的嵌入向量，將向量視為一階矩陣，ujT為uj的轉(zhuǎn)置。若節(jié)點i,j在實際網(wǎng)絡(luò)中距離較近，當(dāng)且僅當(dāng)向量u i,uj相近，即的值接近1 時，嵌入損失 Lemb降低。通過最小化嵌入損失，得到節(jié)點的嵌入向量。

由于無人機集群間的通信不完全依賴基站進行傳輸，因此網(wǎng)絡(luò)數(shù)據(jù)的傳輸需經(jīng)過多跳轉(zhuǎn)發(fā)實現(xiàn)，而多次傳輸過程中會產(chǎn)生數(shù)據(jù)丟失現(xiàn)象，從而使收集到的網(wǎng)絡(luò)數(shù)據(jù)存在噪聲。為了提高嵌入模型的泛化性和穩(wěn)健性，CGEM 采用對抗訓(xùn)練正則化來降低模型對噪聲的敏感度，對抗訓(xùn)練算法在3.4 節(jié)介紹。

3.3 采樣分析

進行鏈路預(yù)測時，越接近待預(yù)測時刻的網(wǎng)絡(luò)快照信息越重要。當(dāng)網(wǎng)絡(luò)快照數(shù)較多時，游走得到的路徑較長，導(dǎo)致CGEM 的訓(xùn)練時間延長。為解決這一問題，本文提出一種離散化采樣法優(yōu)化時序化采樣過程，在每一次采樣結(jié)束后根據(jù)概率公式計算下一跳采樣間隔。

離散化采樣在選取下一跳節(jié)點時，不一定在連續(xù)的網(wǎng)絡(luò)快照中進行，下一跳節(jié)點所在快照的時間刻度tc+k大于當(dāng)前節(jié)點所在快照的時間刻度tc，即tc+k>t c,k∈N*，k為采樣間隔。本文給出2 種概率計算式作為下一跳網(wǎng)絡(luò)快照的選擇依據(jù)，分別根據(jù)線性函數(shù)和指數(shù)函數(shù)計算概率分布。

線性概率下采樣間隔的計算式為

其中，tc為當(dāng)前快照所對應(yīng)的時間刻度，tc+k為下一跳將要選取的網(wǎng)絡(luò)快照所對應(yīng)的時間刻度，P(k)為k的選取概率。

如果快照序列長度N較長，需增加靠近待預(yù)測時刻網(wǎng)絡(luò)快照的選取概率，此時可根據(jù)式(7)計算指數(shù)概率下的采樣間隔。

其中，exp(?)是以自然常數(shù)e 為底的指數(shù)函數(shù)。線性概率和指數(shù)概率下采樣間隔與選取概率的關(guān)系如圖6 所示。采樣間隔越大被選取的概率越大，指數(shù)概率相對線性概率的這一趨勢更顯著。

圖6 采樣間隔與選取概率的關(guān)系

快照序列長度N=100、250、500 時，基于線性概率和指數(shù)概率的離散化采樣對AUC（area under the receiver operating characteristic curve）的影響情況如圖7 所示。

圖7 不同離散化采樣方式下的AUC 對比

當(dāng)N=100時，基于指數(shù)概率比基于線性概率的離散化采樣獲得的AUC 分值高，但此時2 種離散化采樣的效果都較差；當(dāng)N=250時，基于線性概率比基于指數(shù)概率的離散化采樣獲得的AUC 分值較高，原因在于基于指數(shù)概率的離散化采樣丟失了較多的樣本，導(dǎo)致模型缺乏對網(wǎng)絡(luò)細(xì)節(jié)的表征；當(dāng)N=500時，2 種離散化采樣的效果基本相同，原因在于快照序列長度過長時，早期網(wǎng)絡(luò)快照的結(jié)構(gòu)對預(yù)測結(jié)果的影響較小。

3.4 訓(xùn)練及優(yōu)化

對抗訓(xùn)練方法使模型的局部趨于平滑，不僅增加了模型的泛化能力，而且降低了噪聲對圖嵌入模型表征能力的影響。本文將對抗訓(xùn)練方法引入CGEM，以解決連續(xù)對抗擾動無法直接應(yīng)用到離散化網(wǎng)絡(luò)數(shù)據(jù)中的問題[20]。

對抗訓(xùn)練方法通過向原始嵌入中加入對抗擾動來提升模型的穩(wěn)健性，為防止加入的噪聲過大，采用自適應(yīng)尺度指標(biāo)和基于L2范數(shù)的擾動上限來規(guī)范對抗擾動項。對抗擾動為

其中，L 表示模型嵌入的損失，嵌入結(jié)果加入對抗擾動使模型的損失最大化，且限制該擾動所造成的損失保持在限定值ε內(nèi)，ε根據(jù)實際情況確定。采用快速梯度下降法[20]訓(xùn)練對抗擾動項，擾動的更新式為

其中，Δg為當(dāng)前的截斷梯度，||Δg||2為梯度的二范數(shù)，用于限制擾動。梯度為

其中，為當(dāng)前訓(xùn)練中截斷梯度傳播的模型參數(shù)，用于限制擾動項的大小，當(dāng)梯度變化較大時擾動項相對較小，從而保證添加的對抗擾動盡量減少對CGEM 嵌入能力的影響。自適應(yīng)尺度指標(biāo)根據(jù)節(jié)點間的相似性確定，節(jié)點嵌入相似性越高自適應(yīng)尺度越小，從而抑制擾動的程度越大，降低對嵌入結(jié)果的影響。本文定義自適應(yīng)尺度為

其中，normalize(?)為正則化函數(shù)。節(jié)點間權(quán)重wij越大，代表無人機節(jié)點對之間的距離越小，自適應(yīng)尺度對擾動的約束越大。對抗訓(xùn)練正則化項定義為節(jié)點嵌入向量與自適應(yīng)對抗擾動的交叉熵

通過CGEM 得到網(wǎng)絡(luò)的嵌入后，即可直接使用分類器預(yù)測未來的網(wǎng)絡(luò)連接結(jié)構(gòu)。但此時存在以下問題：首先，使用CGEM 的嵌入向量進行鏈路預(yù)測僅考慮了動態(tài)網(wǎng)絡(luò)的結(jié)構(gòu)特征，忽略了網(wǎng)絡(luò)演化過程中的時序特征；其次，CGEM 只能嵌入網(wǎng)絡(luò)中短時間內(nèi)曾產(chǎn)生過連接的節(jié)點，不能反映長時間的網(wǎng)絡(luò)演化規(guī)律。因此，本文將借助LSTM 實現(xiàn)對無人機自組網(wǎng)的鏈路預(yù)測。

4 鏈路預(yù)測

本節(jié)采用LSTM 構(gòu)建預(yù)測模型，提取連續(xù)變化的嵌入矩陣中所隱含的時序特征。

4.1 模型的構(gòu)建

鏈路預(yù)測模型的目的是將CGEM 計算得到的嵌入矩陣進一步轉(zhuǎn)化為下一時刻的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。該模型分為LSTM 層和基于多層神經(jīng)網(wǎng)絡(luò)的解碼器層，經(jīng)過解碼器輸出下一時刻網(wǎng)絡(luò)的鄰接矩陣。

如圖8 所示，St?1為一組連續(xù)網(wǎng)絡(luò)快照所形成的序列，隨著窗口向后滑動產(chǎn)生一系列的網(wǎng)絡(luò)快照序列 {St?1,St,…}，通過CGEM 將其轉(zhuǎn)化為對應(yīng)的嵌入矩陣序列，下一步則按順序輸入LSTM 模型中提取網(wǎng)絡(luò)演化過程中的序列化特征，最終得到輸出序列 {ht,ht+1,…} 。每一個隱層結(jié)果經(jīng)過解碼器，將LSTM 層每一次輸出的結(jié)果ht解碼為下一時刻的網(wǎng)絡(luò)鄰接矩陣，完成對整網(wǎng)拓?fù)涞念A(yù)測。

圖8 基于LSTM 的鏈路預(yù)測模型

首先構(gòu)建用于提取網(wǎng)絡(luò)時變特征的 LSTM模型[16]，LSTM 單元由遺忘門、輸入門和輸出門組成。遺忘門決定將哪些信息從以前的單元格狀態(tài)中丟棄，因此輸入CGEM 的嵌入向量，同時輸入上一單元的輸出結(jié)果ht?1，Wf決定ht?1對輸入向量的影響，計算值越小對上一單元信息丟棄的越多。

遺忘門的計算式為

輸入門決定著應(yīng)該向當(dāng)前單元加入哪些新的信息。該門包含3 個部分：1) Sigmoid 層，用于計算it，it決定輸入將包含哪些信息，因此與遺忘門相同，不僅需要輸入嵌入向量還要輸入上一層的輸出ht?1；2) tanh 層，用于計算，生成候選狀態(tài)值向量，該層同樣根據(jù)嵌入向量和上一層輸出結(jié)果計算狀態(tài)值向量；3) 結(jié)合Sigmoid 層和tanh 層的結(jié)果得到Ct，Ct作為當(dāng)前需要記憶的信息，結(jié)合遺忘門和記憶層計算，遺忘門輸出值越大則上一單元輸入門的影響越大。

輸入門的計算式為

其中，⊙為哈達瑪積。結(jié)合遺忘門和輸入門，LSTM不僅可以提取長期的有效信息，還可以丟棄不需要的信息。而輸出門基于輸入門的輸出結(jié)果Ct，決定輸出給下一層單元的結(jié)果ht。

輸出門的計算式為

本文使用一個LSTM 單元學(xué)習(xí)時間依賴特征，根據(jù)實際情況改變LSTM 的單元數(shù)，增加單元使模型具有更好的時間序列處理能力，同時隨著單元數(shù)的增加會需要更多的數(shù)據(jù)對模型進行訓(xùn)練。得到最終的輸出層結(jié)果ht后，將其輸入解碼器單元進行解碼。解碼器由兩層的多層感知機（MLP,multilayer perceptron）組成，使用ReLU 作為第一層的激活函數(shù)，加速模型的收斂速度，得到輸出yd。第二層輸出層使用Sigmoid 作為激活函數(shù)，得到網(wǎng)絡(luò)在時刻t的網(wǎng)絡(luò)鄰接矩陣。

雙層神經(jīng)網(wǎng)絡(luò)的計算式為

至此完成對基于LSTM 的鏈路預(yù)測模型的構(gòu)建，其中模型的輸入為CGEM 的嵌入向量，LSTM單元負(fù)責(zé)學(xué)習(xí)網(wǎng)絡(luò)演化的時序特征，最終經(jīng)過解碼器輸出下一時刻的網(wǎng)絡(luò)鄰接矩陣，得到網(wǎng)絡(luò)全局的鏈路預(yù)測結(jié)果。

4.2 預(yù)測模型的訓(xùn)練

該鏈路預(yù)測模型的損失函數(shù)由預(yù)測損失 Lp、交叉熵?fù)p失 Lc和正則化項 Lreg組成，預(yù)測損失關(guān)注預(yù)測結(jié)果和真實值A(chǔ)t間的差值，考慮無人機自組網(wǎng)的稀疏性及預(yù)測模型的過擬合問題，應(yīng)關(guān)注真實所產(chǎn)生的連接而不是反向傳播中不存在的連接。模型的預(yù)測損失為

其中，Z是由zi,j組成的矩陣；zi,j為約束值，用于調(diào)節(jié)稀疏網(wǎng)絡(luò)環(huán)境中零元素對預(yù)測傾向的影響，避免出現(xiàn)預(yù)測結(jié)果全為零的情況。zi,j的計算式為

交叉熵?fù)p失關(guān)注的是預(yù)測結(jié)果相對真實值的誤差，通過引入交叉熵?fù)p失 Lc可以進一步提取嵌入矩陣中的結(jié)構(gòu)特征，如式(19)所示。

綜上所述，結(jié)合預(yù)測損失和交叉熵?fù)p失，考慮到模型可能產(chǎn)生的過擬合問題，在最終目標(biāo)函數(shù)中引入正則化項，通過計算模型各參數(shù)矩陣的L2范數(shù)之和作為最終的正則化項，越小參數(shù)矩陣越稀疏，從而防止過擬合。鏈路預(yù)測模型的目標(biāo)函數(shù)為

其中，β和ρ為超參數(shù)。

4.3 時間復(fù)雜度分析

圖嵌入過程中首先進行時序化采樣。若網(wǎng)絡(luò)中存在n個節(jié)點，每個節(jié)點循環(huán)采樣R次，網(wǎng)絡(luò)快照的輸入序列長度為N，則時序化采樣的時間復(fù)雜度為O(RNn)。設(shè)置形成共現(xiàn)對的窗口值為K，則生成共現(xiàn)對的時間復(fù)雜度為O((N?K+1)?(K? 1))=O(NK)，共有Nn條時序化采樣序列，對每一個共現(xiàn)對執(zhí)行一次優(yōu)化，則訓(xùn)練嵌入向量的時間復(fù)雜度為O(EN2Kn)，其中，E為模型的執(zhí)行輪次。由于在CGEM 中需要以一次未添加對抗擾動的優(yōu)化過程進行初始化，因此E＞1，但E仍為一個較小的參數(shù)，多次實驗顯示E=2 為最佳執(zhí)行輪次。K作為共現(xiàn)對的觀測窗口通常也取較小的常數(shù)值。去掉其中較小的常量，CGEM 的時間復(fù)雜度為

本文使用基于線性概率分布的離散化采樣，增加了采樣間隔，使N在最優(yōu)情況下等于K。由于游走和優(yōu)化的過程支持并行計算，因此實際的計算速度更快。

與其他深度學(xué)習(xí)模型類似，基于深度學(xué)習(xí)的預(yù)測模型LSTM-Decoder 的復(fù)雜性取決于模型的權(quán)值，m1為LSTM 的單元數(shù)，m2為Decoder 層多層感知機的單元數(shù)，則時間復(fù)雜度為

同樣地，模型可通過GPU 并行計算進行加速。因此，本文方法的時間復(fù)雜度為

本文在Intel i5-6850K 和GTX1080Ti 環(huán)境下進行實驗，設(shè)定輸入序列長度N=25 時，圖嵌入模型平均耗時為89 ms，最大耗時為163 ms，最小耗時為54 ms；預(yù)測模型平均耗時為0.6 ms，最大耗時為1.3 ms，最小耗時為0.5 ms。綜上可得，在無人機自組網(wǎng)中執(zhí)行一次預(yù)測平均耗時為89.6 ms。

5 實驗與分析

本文采用Ns-3 平臺模擬無人機自組網(wǎng)，獲取無人機集群在指定區(qū)域內(nèi)執(zhí)行任務(wù)的仿真數(shù)據(jù)。使用鏈路預(yù)測經(jīng)典評價指標(biāo)AUC、MAP（mean average precision）和Error Rate[16]驗證本文模型。

5.1 實驗設(shè)計

1) 實驗數(shù)據(jù)集

無人機集群移動模型參數(shù)設(shè)置如表2 所示。

表2 無人機集群移動模型參數(shù)

仿真數(shù)據(jù)格式如圖9 所示，記錄每個無人機節(jié)點的位置信息和獲取數(shù)據(jù)的時間。

圖9 仿真數(shù)據(jù)格式

無人機自組網(wǎng)是無人機集群在不完全依賴地面控制站且在需要時臨時構(gòu)建而成的快速移動自組織網(wǎng)絡(luò)。通過NetAnim 可以觀察到無人機自組網(wǎng)中無人機集群的分布。無人機集群按“狗仔隊”移動模型[23]在區(qū)域內(nèi)進行搜尋的可視化結(jié)果如圖10 所示，狀態(tài)分別為扇狀擴散、覆蓋搜索域和8 字盤旋。

圖10 “狗仔隊”移動模型下的無人機集群分布

網(wǎng)絡(luò)快照連接數(shù)量如圖11 所示。在0～1 500 s時，處于掃描階段的無人機集群從起點出發(fā)向四周擴散，由于起始距離相對較近，此時網(wǎng)絡(luò)中連接數(shù)較多且變化迅速；1 500 s 后，無人機集群不斷擴散至覆蓋目標(biāo)空域，進入盤旋階段，此時網(wǎng)絡(luò)較穩(wěn)定，連接數(shù)的變化較緩慢。

圖11 網(wǎng)絡(luò)快照連接數(shù)量

2) 實驗場景設(shè)計

本文設(shè)置了3 組實驗場景，具體描述如下。

實驗1驗證模型參數(shù)對實驗結(jié)果的影響。設(shè)置快照序列長度分別為(100,150,200,…,450,500)，窗口滑動步長分別為(10,20,30,40,50)，兩兩組合進行實驗，確定模型的最優(yōu)快照序列長度和窗口滑動步長，并通過機械抽樣法驗證LSTM 模型的單元數(shù)對實驗結(jié)果的影響。

實驗2驗證本文鏈路預(yù)測算法的有效性。將本文提出的CGEM-LSTM 鏈路預(yù)測方法與經(jīng)典的CN 和 Katz 算法、基于節(jié)點嵌入的方法Node2vec[19]，以及基于圖嵌入的方法DDNE（deep dynamic network embedding）[15]和E-LSTM-D[16]進行對比，驗證本文鏈路預(yù)測方法的有效性。其中，基于相似性指標(biāo)的鏈路預(yù)測方法以節(jié)點相似程度作為節(jié)點間產(chǎn)生連接的概率。為確保實驗的合理性，所有對比實驗都將在本文最佳模型參數(shù)的數(shù)據(jù)樣本下進行實驗。

實驗3比較CGEM 與其他基于隨機游走的圖嵌入模型對無人機自組網(wǎng)的表征能力。通過邏輯回歸分類器和本文提出的基于LSTM的鏈路預(yù)測模型對比DeepWalk[17]、LINE[18]、Node2vec、CGEM 這4 種嵌入方法的網(wǎng)絡(luò)表征能力。

3) 評價指標(biāo)

AUC 計算式為

其中，M為比較次數(shù)，M'為正例中所選邊的分?jǐn)?shù)大于反例中所選邊分?jǐn)?shù)的次數(shù)，M''為兩者相等的次數(shù)。M'和M''越大，說明正例分?jǐn)?shù)高于反例分?jǐn)?shù)的概率越大，預(yù)測準(zhǔn)確率越高。

MAP 計算式為

其中，AP 為P-R（precision-recall）曲線下的面積。

其中，節(jié)點vi和vj間有連接的集合表示為{ai,j=1}。MAP 用于衡量預(yù)測結(jié)果的精確性。

Error Rate 為錯誤的連接LNfalse占所有真實存在連接LNtrue的比例，與僅在兩圖中計算絕對不同連接的SumD 指標(biāo)不同，Error Rate 考慮了真實存在的連接數(shù)。Error Rate 計算式為

5.2 實驗結(jié)果與分析

5.2.1 實驗1

模型的快照序列長度N和窗口滑動步長Δt對模型的預(yù)測精度和效率都有影響。序列中包含了一段時間內(nèi)網(wǎng)絡(luò)的拓?fù)溲莼闆r，如果長度選取較長，在相同維度的嵌入向量中將缺失網(wǎng)絡(luò)結(jié)構(gòu)在細(xì)節(jié)上的表示；若選取的長度較短，相同維度下的嵌入向量則可能產(chǎn)生過擬合現(xiàn)象。窗口滑動步長決定了嵌入向量之間的差異，若步長較大，則所產(chǎn)生的向量將丟失網(wǎng)絡(luò)演化的細(xì)粒度特征；反之則影響模型的執(zhí)行效率。選取網(wǎng)絡(luò)連接數(shù)變化較大的時段0～3 000 s，圖12～圖14 分別反映了窗口滑動步長Δt取{10,20,30,40,50}時，不同快照序列長度N對AUC、MAP、Error Rate 的影響情況。

圖12 不同快照序列長度和窗口滑動步長下的AUC

圖13 不同快照序列長度和窗口滑動步長下的MAP

圖14 不同快照序列長度和窗口滑動步長下的Error Rate

從整體來看，在不同的快照序列長度和窗口滑動步長下，模型都具有較好的預(yù)測效果。當(dāng)快照序列長度N=250時，預(yù)測結(jié)果的AUC、MAP 和Error Rate 值相對較高，模型預(yù)測結(jié)果最優(yōu)。當(dāng)窗口滑動步長 Δt= {10,20,30}時，AUC 穩(wěn)定在0.98 以上，MAP 穩(wěn)定在0.9 以上，Error Rate 穩(wěn)定在1.0以下，且在Δt=10時模型表現(xiàn)最佳。綜合以上3 種評價指標(biāo)的實驗結(jié)果，本文確定快照序列長度為250，滑動窗口步長取10。

本文提出的鏈路預(yù)測方法通過LSTM提取網(wǎng)絡(luò)的序列化特征，LSTM 的unit 決定了輸出隱層向量的維度。如圖15 所示，設(shè)置不同的unit 值進行預(yù)測，通過模型的AUC 及LOSS 最終確定unit=500。

圖15 不同unit 下的AUC 及LOSS

5.2.2 實驗2

由實驗1 可確定模型的最佳參數(shù)如下：快照序列長度N=250，窗口滑動步長=10。實驗2 的目的是衡量本文提出的基于CGEM 和LSTM 的鏈路預(yù)測方法與其他鏈路預(yù)測方法的性能。為確保實驗的合理性，所有對比實驗都將在本文最佳模型參數(shù)的數(shù)據(jù)樣本下進行實驗。對每組實驗進行40 次采樣，計算對應(yīng)的AUC、MAP 和Error Rate，實驗結(jié)果如圖16～圖18 所示。

圖16 在測試集中40 次采樣下的AUC

圖17 在測試集中40 次采樣下的MAP

圖18 在測試集中40 次采樣下的Error Rate

從圖 16～圖 18 可以看出，本文所提CGEM-LSTM 在AUC、MAP 和Error Rate 下都具有良好的表現(xiàn)，并且可以從圖中曲線的波動觀察到，本文方法在40 次采樣結(jié)果中相對其他方法更加平穩(wěn)。

表3 為40 次采樣結(jié)果的平均值。與同屬深度圖嵌入方法的DDNE 相比，本文方法的AUC 提高了2.77%，MAP 提高了14.07%，Error Rate 降低了1.39；與E-LSTM-D 相比，本文方法的AUC 提高了0.91%，MAP 提高了4.91%，Error Rate 降低了0.40。由此可見，本文方法的模型可較好地學(xué)習(xí)無人機自組網(wǎng)的拓?fù)溲莼?guī)律。

表3 鏈路預(yù)測效果對比

5.2.3 實驗3

設(shè)置快照序列長度為250，窗口滑動步長為10，選取網(wǎng)絡(luò)連接變化較頻繁的0～3 000 s 內(nèi)對模型的嵌入效果進行對比。通過邏輯回歸分類器對嵌入向量進一步處理，嵌入效果如表4 所示。

從表4 可以看出，CGEM 相對Node2vec 的鏈路預(yù)測結(jié)果較差，但CGEM 的MAP 和Error Rate值相對Node2vec 更好。從嵌入的原理來看，Node2vec需在每一個快照中進行游走得到節(jié)點序列，而CGEM則在一組網(wǎng)絡(luò)快照中進行游走，得到的節(jié)點序列相對Node2vec 較少，且算法執(zhí)行效率更高。CGEM 的Error Rate比LINE高0.62，但其AUC和MAP均高于LINE，其原因在于CGEM 引入了對抗訓(xùn)練方法，而邏輯回歸模型不能有效地對其所添加的噪聲進行擬合。綜合來看，CGEM 仍具有較好的嵌入效果。

表4 嵌入效果對比（邏輯回歸分類器）

通過LSTM 對嵌入向量進一步處理，嵌入效果如表5 所示。

表5 嵌入效果對比（LSTM）

從表5 可以看出，結(jié)合LSTM 進行鏈路預(yù)測時具有更好的評價效果，這表明模型對動態(tài)網(wǎng)絡(luò)的序列化特征進行提取是有意義的。對表4、表5 分析可得，本文提出的鏈路預(yù)測模型相對于其他基于隨機游走的鏈路預(yù)測模型具有較好的預(yù)測效果。

6 結(jié)束語

本文提出基于深度圖嵌入的無人機自組網(wǎng)鏈路預(yù)測方法。通過對無人機自組網(wǎng)內(nèi)部交互關(guān)系的分析構(gòu)建時序化圖嵌入模型，將網(wǎng)絡(luò)連接狀況轉(zhuǎn)化為節(jié)點嵌入向量間的距離關(guān)系。采用LSTM 提取不同時刻嵌入矩陣中隱含的時序特征，實現(xiàn)對下一時刻網(wǎng)絡(luò)連接的預(yù)測，并結(jié)合實現(xiàn)過程分析了預(yù)測方法的時間復(fù)雜度。

隨著網(wǎng)絡(luò)規(guī)模的增加，在無人機自組網(wǎng)中進行鏈路預(yù)測的計算效率將面臨挑戰(zhàn)。下一步工作可通過引入圖神經(jīng)網(wǎng)絡(luò)算法，提升模型的嵌入效果，從而降低預(yù)測模型的樣本規(guī)模，提高訓(xùn)練效率。