基于Spark的PageRank算法優(yōu)化及其軍事應用研究

劉振宇，李欽富，曾 操,李 鵬

(1.西安電子科技大學，陜西 西安 710071；2.中國電子科技集團公司電子科學研究院，北京 100041)

0 引 言

在現(xiàn)代軍事戰(zhàn)爭中，軍事通信網(wǎng)絡模型規(guī)模龐大且復雜多樣，各種電子通信加密手段使得獲取的通信信息有很大的虛假性和隱蔽性，同時各種新型作戰(zhàn)模式使得重要作戰(zhàn)目標很難被發(fā)現(xiàn)，所以從復雜的軍事網(wǎng)絡中找到核心的軍事目標是本文的目的和初衷。軍事通信網(wǎng)絡也是一種網(wǎng)絡模式，所以尋找重要目標的核心就是從軍事網(wǎng)絡圖譜中尋找重要度較高的節(jié)點，而PageRank算法就是一種用于度量互聯(lián)網(wǎng)絡網(wǎng)頁重要性的網(wǎng)絡圖譜節(jié)點重要度排名算法。2009年Sayyadi等人提出了FutureRank算法，考慮到了時間和已有PageRank值[1]，但是虛假消息對FutureRank的影響較大，預測排名相關度較低。劉大有等人提出了不需要當前PageRank值的權威網(wǎng)絡，但是權威網(wǎng)絡要求消息真實可靠，不適用于具有隱蔽消息的場景[2]。為了增強運算速率，劉記云等人提出了運用MapReduce進行PageRank值的計算[3]，但是MapReduce分布式并行計算本身不適合具有聯(lián)系性的數(shù)據(jù)進行迭代運算。PageRank算法被廣泛運用于社交、搜索引擎排名等方面[4]，雖然李政等人通過添加中心度來分析節(jié)點對于軍事電子通信信息傳播的影響[5]，但是只增強了通信站等通信中介的重要性，沒有考慮通信節(jié)點在圖譜中的真實性和可靠性?；谝陨喜蛔?，本文提出了一種綜合時間、目標位移、權威等因素，針對軍事通信網(wǎng)絡中虛假性和隱蔽性目標的改進加權的MilitaryRank算法。

1 軍事通信網(wǎng)絡及目標重要度評估

軍事通信網(wǎng)絡和互聯(lián)網(wǎng)絡一樣，都可以表示為節(jié)點間的鏈接網(wǎng)絡，包含了點與邊之間的聯(lián)系，由于軍事目標的指揮層次和功能區(qū)分不盡相同，各種新型的分布式作戰(zhàn)模式和網(wǎng)絡戰(zhàn)等作戰(zhàn)方式層出不窮，所以節(jié)點在不同網(wǎng)絡圖譜中或同一網(wǎng)絡圖譜的不同位置具有不同重要性[5]，對敵方關鍵節(jié)點的打擊具有重要意義，如何綜合考慮時間、通信數(shù)量和權威性影響從而從軍事通信網(wǎng)絡中排除虛假節(jié)點的干擾找到核心節(jié)點，成為軍事通信中的重要問題。

不同軍事網(wǎng)絡模型具有不同的拓撲結(jié)構(gòu)，復雜的網(wǎng)絡拓撲中存在著不同分工的節(jié)點，對關鍵節(jié)點的打擊能有效的破壞通信網(wǎng)絡[6]。PageRank值的引入可以體現(xiàn)出在電子通信系統(tǒng)中節(jié)點的重要性，要在作戰(zhàn)時間內(nèi)找出權威性最高的節(jié)點，同時由于敵方大量的通信的欺騙，所以我們給出幾項假設進行驗證：

(1)時間上越新的消息重要性越大，發(fā)出新消息的節(jié)點可能對戰(zhàn)場的影響力越大。

(2)無論是新消息還是老消息，消息引起的軍事目標的位置變化越大，那么這個消息就越重要，發(fā)出這個消息的節(jié)點的權威性就越高。

(3)通信目標在一定時間內(nèi)并非發(fā)出消息越多就越重要，消息數(shù)量符合一定的冪率分布，不符合分布的數(shù)量過大消息的節(jié)點應予以限制。

(4)消息的內(nèi)容無法獲得，但可以知道消息的加密情況，加密度越高的消息那么重要性也隨之增加。

(5)接收消息的單位，接收到的消息數(shù)量越少，位置變化快，那么這個單位的機動性就越高，威脅性也隨之增高，更需要引起關注。

2 改進的PageRank重要軍事目標排序算法

2.1 軍事通信網(wǎng)絡通信權威性

本文中引用鏈接網(wǎng)絡中含有兩類節(jié)點即通信單位節(jié)點以及通信消息節(jié)點，由于虛假通信的干擾，虛假信號源可能會發(fā)布大量的虛假信號來進行迷惑敵方，通信節(jié)點的權威不能通過發(fā)送消息的多少來表示，所以需要根據(jù)指揮單位發(fā)出的通信消息的結(jié)果來判斷通信節(jié)點權威性，即根據(jù)接收單位接收到消息后的行為來判別發(fā)送方的權威性，虛假信號源的消息對接收單位的行為不會有影響，但是真正指揮者即便真假消息混合發(fā)送也會有一部分信息對接受方產(chǎn)生影響，此時虛假消息對發(fā)送方的權威性影響不大。我們定義權威矩陣之前需要先定義影響力。

(1)

(2)

(3)

(4)

由此我們可以定義出發(fā)送單位的權威性公式R=diag(Map×Mpa×Mad)和消息單位的權威公式R′=diag(Mpa×Mad)，為了防止出現(xiàn)某些點權威性過大，我們使用相對權威性，通信節(jié)點Pi和消息節(jié)點Pj的相對權威性分別是Ri/R和Rj/R′

2.2 軍事通信時間權重

在軍事通信中時間要素是一項很重要的要素，越靠近當前作戰(zhàn)時間的消息就越有價值，越晚收到的消息在時間上就比之前收到的消息重要，因此給通信消息加上時間權重，使得時間越近的消息權重就越高。

w(Pi)=PRlast(Pi)*Ti

(6)

式(6)中

式(7)中ts是固定值，Tn是當前迭代次數(shù)。獲得每個網(wǎng)頁的時間反饋權值之后，針對同一個網(wǎng)頁，我們可以計算出各個入鏈的相對時間反饋權值。

式(8)中O(Pj)是網(wǎng)頁Pi的入鏈集合，將Wt加入到PageRank算法中，那么Pi的入鏈Pj會根據(jù)Pi的時間權重為Pi分配PR值，即如果Pi是Pj出度中時間較新的節(jié)點，Pj就會分配給Pi較大的時間權威值。這樣就可以有效的提升新通信節(jié)點的PR值，同時可以在消息節(jié)點與通信節(jié)點共存的網(wǎng)絡圖譜中凸顯出通信節(jié)點的重要性。

2.3 抑制虛假軍事通信節(jié)點

軍事通信網(wǎng)絡圖譜不同于傳統(tǒng)互聯(lián)網(wǎng)網(wǎng)頁關系圖譜，通信節(jié)點之間有各種業(yè)務規(guī)則，不同的通信節(jié)點等級有不同的通訊消息數(shù)量級別，越重要的部門通信量也就會越多，所以某些通訊節(jié)點數(shù)量過多或者過少都屬于不正常情況，有可能是敵方的虛假通信干擾。參謀單位或者通信衛(wèi)星匯集各個分指揮中心的數(shù)據(jù)，進行分析后進行上報，并根據(jù)上級決策，對各個分域進行指揮，屬于信息量交換最大的地方。各分域指揮中心負責本分域的情報處理和下達，屬于信息交換次大的地方。下屬各個師到單兵，雖然分工和只能不同導致通信消息數(shù)量不一致，但是隨著人員數(shù)量的減少，信息交換的數(shù)量也屬于一個可變范圍，最后單兵信息的上傳和接收遠遠小于各個上級部門。綜合以上信息，雖然現(xiàn)在部隊已經(jīng)不是完全按照“三三制”原則，并且部隊編制較為復雜，但是大規(guī)模節(jié)點下整體符合冪率分布特點[7]。

為了避免敵方的通信欺騙，將通信量遠遠多于該等級正常冪律分布下通訊量的節(jié)點定義為通信欺騙點。我們需要先定義通信節(jié)點的消息量，由于樹形拓撲結(jié)構(gòu)是一種分級的集中控制結(jié)構(gòu)，是典型的傳統(tǒng)軍事通信網(wǎng)絡的拓撲結(jié)構(gòu)，這種拓撲結(jié)構(gòu)與一般的指揮控制關系相一致，因此廣泛存在于現(xiàn)有的軍事通信網(wǎng)絡中[6]。根據(jù)軍事通信網(wǎng)絡的樹形拓撲結(jié)構(gòu)，找到某點的最長入度鏈長度，找到最小消息單位即單兵設為基準消息量，進行回歸分析，求出回歸曲線。

y=k-bx

(9)

再對偏離最大最小閾值的通信消息量進行回歸分析，判斷該節(jié)點的通信量是否符合回歸方程，越不符合回歸方程，給予該節(jié)點的權重越小。

式(10)中μ是回歸曲線的計算值，x是將通信節(jié)點消息數(shù)量帶入回歸方程所得值，比回歸曲線大過多或者小過多的點都定義為無價值點，所以加權中給予較小權重，由于某一級作戰(zhàn)單位的通訊量應當在一定范圍內(nèi)，可以求出各個作戰(zhàn)級別的正態(tài)分布曲線，根據(jù)實際通信量和該點理論通信量差給予一定的權重限制，從而排除了過大通信量節(jié)點的欺騙信號和過小通信量的無用信號。

2.4 通信節(jié)點行動力加權

若調(diào)整余弦相似度小于閾值,本文閾值設為0.5，則判斷為正常目標進行下一步行動力加權計算：

式(13)中行動力d即一定時間內(nèi)的通信節(jié)點的位置變化量或網(wǎng)絡IP位置變化，dmax是戰(zhàn)場作戰(zhàn)范圍。

2.5 軍事通信節(jié)點的重要程度

綜合權威向量，時間權重，數(shù)量影響及行動力變化多方面考慮的MilitaryRank公式為：

適用于軍事電子通信的PageRank優(yōu)化算法，當觀察者查看一個消息時，會根據(jù)出鏈節(jié)點的時間反饋值、通信量反饋值以及行動力變化，綜合通信節(jié)點和消息節(jié)點的相對權威性來決定查看下一個通信單位。因此能有效避免某些虛假通信節(jié)點的干擾以及更大幾率的找到通信較少但影響較大的隱蔽節(jié)點。

3 仿真試驗分析

3.1 試驗條件

3.1.1 試驗環(huán)境及重要參數(shù)

本試驗的環(huán)境：(1)大數(shù)據(jù)平臺環(huán)境：三節(jié)點大數(shù)據(jù)平臺CDH2.4，單節(jié)點256G內(nèi)存，linux，CentOS7

(2)單機環(huán)境：單核，2G內(nèi)存 ，Linux， CentOS7

試驗參數(shù)：加權PageRank公式阻尼系數(shù)0.85，抑制虛假節(jié)點的線性回歸曲線分析b=-1.9，k=6.4，迭代終止條件e=0.01，每個節(jié)點的初始PageRank值設為1。

圖1 冪率分布的線性回歸分析

3.1.2 仿真目標關系圖譜

我們選用了社區(qū)發(fā)現(xiàn)中常用的LFR-benchmark仿真網(wǎng)絡數(shù)據(jù)集按照冪律分布進行網(wǎng)絡生成，并在網(wǎng)絡中相連節(jié)點間添加消息節(jié)點，根據(jù)消息節(jié)點所在的社區(qū)在一定范圍內(nèi)隨機生成時間和位置數(shù)據(jù)，同時根據(jù)已知網(wǎng)絡模擬出軍事通信網(wǎng)絡節(jié)點名稱形成仿真數(shù)據(jù)。圖2為構(gòu)造的軍事通信網(wǎng)絡圖譜：

閥板開關柄設計：采用1m長的角鋼（規(guī)格為40＊40＊5）作為閥板開關柄，開關柄與閥板主板通過焊接連在一起，在開關柄末端進行開孔，孔徑為20mm，末端孔通過綁定尼龍繩并引至沉箱頂預留鋼筋處。在沉箱進水控制時，只需要操作人員站在沉箱頂拉緊或放松尼龍繩，即可進行沉箱進水控制。

圖2 LFR仿真網(wǎng)絡通信節(jié)點圖譜

3.2 試驗流程

實驗流程如圖3所示：

圖3 基于Hadoop平臺的軍事Military PageRank算法總體框架

(1)初始化階段用LFR-benchmark方法構(gòu)造仿真網(wǎng)絡社區(qū)，并根據(jù)社區(qū)數(shù)據(jù)向網(wǎng)絡中添加消息節(jié)點并隨機生成時間等特征信息。

(2)軍事網(wǎng)絡節(jié)點重要度排序Military PageRank階段首先初始化轉(zhuǎn)移概率矩陣并設置PageRank初值和迭代終止值。然后根據(jù)每個節(jié)點周圍節(jié)點的時間和位置等特征進行軍事網(wǎng)絡加權的PageRank計算，計算得出新的PageRank值。最后與原先的PageRank值進行比較判斷收斂并輸出結(jié)果。

(3)數(shù)據(jù)可視化階段將排序后的重要節(jié)點信息添加到圖數(shù)據(jù)庫中并進行可視化展現(xiàn)。

3.3 時間復雜度分析

軍事通信中往往需要從大量的通信節(jié)點中找出關鍵目標，現(xiàn)代戰(zhàn)爭中電子通信復雜，各種干擾和隱蔽信號繁多，因此構(gòu)成包含通訊單位和消息在內(nèi)的超大規(guī)模圖譜，傳統(tǒng)的計算方式不能高效快速的分析出結(jié)果。我們使用大數(shù)據(jù)組件HDFS、Hbase進行數(shù)據(jù)存儲，Spark進行調(diào)用數(shù)據(jù)計算，運用圖數(shù)據(jù)庫Neo4j進行部分可視化，Spark是基于內(nèi)存的編程模型，它可以把中間的迭代過程不放在磁盤中，直接數(shù)據(jù)不落地在內(nèi)存中執(zhí)行，極大的提高了它的執(zhí)行速度。試驗中上萬節(jié)點數(shù)據(jù)以及千萬條邊數(shù)據(jù)在單機環(huán)境下需要分鐘級運行時間，在大數(shù)據(jù)平臺環(huán)境下只需要秒級運算時間，符合軍事上實時性的要求。

在迭代計算中，相比于傳統(tǒng)MapReduce方式每次迭代都要與HDFS進行一次交換而言，Spark運用DAG編程模型將多個MapReduce簡化為一個Spark作業(yè)。隨后將作業(yè)切分成多個Stage并通過Shuffle進行數(shù)據(jù)傳遞，中間數(shù)據(jù)以RDD(Resilient Distributed Dataset)形式分布式存儲在slave節(jié)點中，與HDFS之間只需要一次讀寫操作，運行時間節(jié)約60%以上。在不同數(shù)量節(jié)點下的PageRank運算時間如圖4。

圖4 相同節(jié)點下運算時間比較

3.4 目標重要度排名結(jié)果

針對軍事領域電子通信的特殊性，將軍事通信優(yōu)化的PageRank算法結(jié)果與傳統(tǒng)PageRank算法和進行比較，針對軍事電子通信的虛假性和隱蔽性特點，不斷修改時間、通信量和行動力的比重值，提高挖掘軍事通信重要節(jié)點的準確率。最終從復雜網(wǎng)絡圖譜中求出不同權重下對隱蔽目標查找，虛假目標排除，以及重要信息節(jié)點排序的不同結(jié)果。

3.4.1 隱蔽目標查找

將傳統(tǒng)的Pagerank算法與加權改進后(a=0.3,b=0.1,c=0.6)的Pagerank算法進行結(jié)果進行比對：

表1 傳統(tǒng)PageRank算法結(jié)果

表2 隱蔽目標PR值查找結(jié)果

圖5 隱蔽點的目標關系網(wǎng)絡

從圖5可以看出隱蔽目標的關系網(wǎng)絡相較整個網(wǎng)絡來說并不復雜，但是由于關系網(wǎng)絡較為簡單，出入度相對較少，所以傳統(tǒng)PageRank方法獲得的PR值會很低，經(jīng)過對隱蔽目標加權迭代后隱蔽目標的MilitaryRank值會升高，從而發(fā)現(xiàn)隱蔽性高的機動目標，但同時會降低固定位置或固定IP位置單位的排名。

3.4.2 虛假目標抑制

從圖5可以看出虛假目標的發(fā)送網(wǎng)絡相對復雜，接收網(wǎng)絡與真實信號源也有很大重疊，普通的PageRank方法無法分辨他的真實性，但是經(jīng)過虛假目標抑制的迭代之后，能明顯將其重要性降低。

表3 原始PageRank算法結(jié)果

表4 虛假目標排除結(jié)果

圖6 虛假目標發(fā)送網(wǎng)絡

3.4.3 重要鏈路排序

重要鏈路排序獲取迭代結(jié)果中標簽為消息的所有節(jié)點，并對其進行MilitaryRank排序，可以獲得較為重要的消息節(jié)點，該消息節(jié)點處于的位置就是關鍵鏈路，可以通過對關鍵鏈路的打擊來割裂目標集群之間的聯(lián)系或者對己方關鍵軍事鏈路進行保護。

表5 部分消息節(jié)點排序結(jié)果

3.5 結(jié)果分析

從試驗中可以看出隱蔽目標的關系網(wǎng)絡相較干擾點來說并不復雜，但是由于關系網(wǎng)絡較為簡單，出入度相對較少，所以傳統(tǒng)PageRank方法獲得的PR值會很低，經(jīng)過對隱蔽目標加權的MilitaryRank算法使隱蔽目標的排名升高，從而發(fā)現(xiàn)隱蔽性高的機動目標，但同時會降低固定位置或固定IP位置單位的排名。同時由于虛假目標的發(fā)送網(wǎng)絡十分復雜，接收網(wǎng)絡與真實信號源也有很大重疊，普通的PageRank方法無法分辨該類目標的真實性，但是經(jīng)過虛假目標抑制的迭代之后，能明顯將其重要性降低。從排序后的結(jié)果中選中標簽為消息類型的節(jié)點，并對其進行統(tǒng)計，可以獲得較為重要的消息節(jié)點，說明該消息節(jié)點處于的位置是關鍵的消息鏈路，從而通過對關鍵鏈路的打擊來割裂目標集群之間的聯(lián)系或者對己方關鍵軍事鏈路進行保護。

4 結(jié) 語

本文從軍事目標網(wǎng)絡的各項問題出發(fā)，在Pagerank算法的基礎上對軍事網(wǎng)絡目標的重要程度進行了研究，將時間、空間/IP位置、目標權威性與加權Pagerank算法結(jié)合，提出了適合軍事目標網(wǎng)絡的的網(wǎng)絡目標重要度評估算法。仿真結(jié)果表明，相比經(jīng)典的Pagerank算法，該算法能從網(wǎng)絡目標關系圖譜中更好的找到隱蔽點和排出虛假點的影響，同時能合理的分析不同消息鏈路的重要程度。但是由于本方法的Pagerank值是由各方面加權迭代計算獲得的，所以各部分的權重很難平衡，同時也不具備動態(tài)變化的功能。而且真正的軍事目標位置復雜多變，并非能完全獲得目標的位置變化，所以在未來的工作中將考慮如何在節(jié)點信息不全的情況下進行計算并且動態(tài)的調(diào)整構(gòu)成Pagerank值的各項權重比例。