無人機集群網(wǎng)絡(luò)節(jié)點重要性的多屬性決策

左嘉嫻，華 翔

(1.西安工業(yè)大學(xué) 兵器科學(xué)與技術(shù)學(xué)院，西安 710021；2.西安工業(yè)大學(xué) 電子信息工程學(xué)院，西安 710021)

無人機集群網(wǎng)絡(luò)是一種特殊的復(fù)雜網(wǎng)絡(luò)，網(wǎng)絡(luò)中5%～10%的節(jié)點死亡失效時，會引起整個網(wǎng)絡(luò)的癱瘓[1]，尤其是網(wǎng)絡(luò)重要節(jié)點失效會引起整個網(wǎng)絡(luò)的級聯(lián)失效，因此對無人機集群網(wǎng)絡(luò)各節(jié)點的重要性進(jìn)行評估有著現(xiàn)實意義[2]。目前國內(nèi)外對于無人機集群網(wǎng)絡(luò)節(jié)點重要性評估的研究還處于起步階段。目前，諸多學(xué)者針對復(fù)雜網(wǎng)絡(luò)中各個節(jié)點的重要性評估的研究已經(jīng)有了初步進(jìn)展。但是大多采取單一屬性指標(biāo)，單個節(jié)點重要度指標(biāo)在網(wǎng)絡(luò)中進(jìn)行節(jié)點重要度評估時存在很大局限性，會忽略節(jié)點間的相關(guān)作用等因素，不夠全面，或者即使采取了多指標(biāo)評判也沒有深入考慮網(wǎng)絡(luò)全局。文獻(xiàn)[3]基于鄰接矩陣定義了節(jié)點重要度貢獻(xiàn)矩陣，將所有節(jié)點對鄰節(jié)點的重要度貢獻(xiàn)比例值用矩陣的形式表現(xiàn)出來，結(jié)果表明，此算法更適用于大型網(wǎng)絡(luò)的關(guān)鍵節(jié)點識別；文獻(xiàn)[4]考慮到在不同拓?fù)浣Y(jié)構(gòu)下鄰居節(jié)點對節(jié)點的影響程度不同，提出了主要考慮節(jié)點鄰居數(shù)量和與鄰居節(jié)點親密程度的節(jié)點重要性評估KI算法，結(jié)果表明，KI算法具有高準(zhǔn)確性，但是需要較多的網(wǎng)絡(luò)拓?fù)湫畔?；文獻(xiàn)[5]考慮到節(jié)點重要度與最優(yōu)路徑長度，最優(yōu)路徑數(shù)目及信息傳播率密切相關(guān)，提出將重要度傳輸矩陣作為節(jié)點重要性評估的重要依據(jù)；文獻(xiàn)[6]提出將節(jié)點冗余度作為唯一的評價指標(biāo)來評價網(wǎng)絡(luò)中各節(jié)點的重要性；文獻(xiàn)[7]依據(jù)網(wǎng)絡(luò)中節(jié)點與其一跳鄰節(jié)點與兩跳鄰節(jié)點范圍內(nèi)的關(guān)系提出了鄰接信息熵的概念，并將信息熵作為節(jié)點重要性評估的主要判據(jù)。基于以上考慮，文中提出了基于復(fù)雜網(wǎng)絡(luò)理論的無人機集群網(wǎng)絡(luò)節(jié)點重要性評估算法。

1 理論基礎(chǔ)

無人機集群網(wǎng)絡(luò)具有復(fù)雜的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，無人節(jié)點間通過自組織的方式進(jìn)行通信連接[8]。首先對無人機集群網(wǎng)絡(luò)進(jìn)行建模，一般表示為G(V,E)，其中G(·)為無向無權(quán)圖，V={v1,v2,v3,…,vn}為網(wǎng)絡(luò)節(jié)點集合，vi(i=1,2,…,n)為網(wǎng)絡(luò)中的單個節(jié)點，E={e1,e2,e3,…,em}為節(jié)點間的連邊，ei(i=1,2,…,m)為節(jié)點間相互通信的無線鏈路，n為節(jié)點個數(shù)，m為鏈路條數(shù)。對于無人機集群網(wǎng)絡(luò)，節(jié)點的重要性指標(biāo)包括度中心性、介數(shù)中心性、歸一化緊密度、節(jié)點相對重要性。

設(shè)復(fù)雜網(wǎng)絡(luò)中有n個節(jié)點，則節(jié)點vi的度中心性為

(1)

其中ki為節(jié)點vi的節(jié)點度。

網(wǎng)絡(luò)中不相鄰的節(jié)點vi和vj之間的最短路徑會途經(jīng)某些節(jié)點，某個節(jié)點vi被其他最短路徑經(jīng)過，則表示該節(jié)點在網(wǎng)絡(luò)中很重要，其重要性或影響力可用節(jié)點的介數(shù)來表征。節(jié)點vi的介數(shù)中心性為

CB(vi)=2Bi/[(n-1)(n-2)]，

(2)

其中Bi為節(jié)點介數(shù)。

節(jié)點vi的歸一化緊密度為

(3)

其中dij為節(jié)點vi到節(jié)點vj的距離。

節(jié)點vi的相對重要性為

(4)

其中μm(vi)為以節(jié)點為起點經(jīng)m個連邊回到節(jié)點vi的回路數(shù)目。

2 節(jié)點重要性綜合評估

選取度中心性、介數(shù)中心性、歸一化緊密度、節(jié)點相對重要性等指標(biāo)進(jìn)行綜合評估。采用變異系數(shù)法為各個屬性指標(biāo)賦權(quán)。通過指標(biāo)變異系數(shù)計算，忽略指標(biāo)量綱的影響，可得各項指標(biāo)的差異程度。具體的算法流程如下：

① 節(jié)點屬性矩陣構(gòu)造

設(shè)無人機集群網(wǎng)絡(luò)中有n個待評價的無人機節(jié)點，對應(yīng)的重要節(jié)點方案集為{A1,A2,…,An}，有k個節(jié)點重要性評估指標(biāo)，即方案屬性有k種，文中k=4，構(gòu)造初始決策矩陣P，即

(5)

式中：Ai(fr)(i=1,2,…,n;r=1,2,3,4)為節(jié)點方案；fr(r=1,2,3,4)為方案屬性。

② 加權(quán)規(guī)范化矩陣構(gòu)造

采用變異系數(shù)法確定各個屬性指標(biāo)的歸一化權(quán)重向量wT=[w1,w2,w3,w4]，各項指標(biāo)的權(quán)重wi(i=1,2,3,4)為

(6)

其中Vi為第i項指標(biāo)的變異系數(shù)，且

(7)

③ 綜合評價指標(biāo)計算

根據(jù)初始化決策矩陣以及選取的度中心性、介數(shù)中心性、歸一化緊密度、節(jié)點相對重要性等指標(biāo)的權(quán)重，進(jìn)行綜合評價指標(biāo)計算，即

(8)

式中：M為決策系數(shù)矩陣；pij(i=1,2,…,n;j=1,2,3,4)為初始決策矩陣元素。

3 實驗分析

近年來，國內(nèi)外多采用ARPA網(wǎng)進(jìn)行網(wǎng)絡(luò)節(jié)點重要性分析[9]，為此文中采用ARPA網(wǎng)來驗證所提算法的有效性。ARPA網(wǎng)由21個節(jié)點和23條連邊構(gòu)成[10]，其拓?fù)浣Y(jié)構(gòu)如圖1所示[11]。其中vi(i=1，2，3,…,21)為網(wǎng)絡(luò)節(jié)點。

圖1 ARPA網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

將文中所提多屬性決策(Multiple Attribute Decision Making，MADM)算法與其他算法運用在ARPA網(wǎng)絡(luò)拓?fù)渖蟍12]，ARPA網(wǎng)節(jié)點重要性計算結(jié)果見表1。

表1 ARPA網(wǎng)各節(jié)點重要性

根據(jù)節(jié)點重要性計算結(jié)果，得到ARPA網(wǎng)前5個重要節(jié)點，見表2。

表2 ARPA網(wǎng)前5個重要節(jié)點

由表2可見，不同算法得到的ARPA網(wǎng)前5個重要節(jié)點不一致。定義前5個重要節(jié)點為vc,i(i=1,2,3,4,5)，按重要性對其進(jìn)行排序，排序結(jié)果依次為vc,1,vc,2,vc,3,vc,4,vc,5。為分析重要節(jié)點失效對網(wǎng)絡(luò)性能的影響，需對重要節(jié)點進(jìn)行刪除，以得出子圖數(shù)與子圖最大規(guī)模。重要節(jié)點有以下幾種刪除方式：① 刪除vc，1，記為方式1；② 刪除vc，1，vc，2，記為方式2；③ 刪除vc，1，vc，2，vc,3，記為方式3；④ 刪除vc，1，vc，2，vc,3，vc,4，記為方式4；⑤ 刪除vc，1，vc，2，vc,3，vc,4，vc,5，記為方式5。不刪除任何重要節(jié)點，記為方式0。

為比較不同算法在網(wǎng)絡(luò)重要節(jié)點識別上的性能差異，按以上幾種方式對重要節(jié)點進(jìn)行刪除，生成的子圖數(shù)與子圖最大規(guī)模如圖2所示。其中，子圖數(shù)表示網(wǎng)絡(luò)重要節(jié)點失效對網(wǎng)絡(luò)連通性的破壞情況，子圖最大規(guī)模表示網(wǎng)絡(luò)重要節(jié)點失效對網(wǎng)絡(luò)的分割情況。

從圖2可以看出，刪除前5個重要節(jié)點后，MADM算法對應(yīng)的子圖數(shù)較其他算法大，對應(yīng)的子圖最大規(guī)模較其他算法小。相較于其他方法，MADM算法計算得到的重要節(jié)點的失效對網(wǎng)絡(luò)連通性的破壞程度較大，對網(wǎng)絡(luò)的分割更為均勻。

圖2 子圖數(shù)與子圖最大規(guī)模

4 結(jié) 論

從局部網(wǎng)絡(luò)、全局網(wǎng)絡(luò)、節(jié)點相對重要性三個角度出發(fā)選取節(jié)點重要性評價指標(biāo)，采用變異系數(shù)法確定各項指標(biāo)權(quán)重，在ARPA網(wǎng)絡(luò)上對節(jié)點進(jìn)行定量的重要性排序。相較于信息熵算法、重要度評價矩陣算法、貢獻(xiàn)矩陣算法，MADM算法所選出的重要節(jié)點的失效對網(wǎng)絡(luò)連通性的破壞程度較大，對網(wǎng)絡(luò)的分割更為均勻，實現(xiàn)了對無人機集群網(wǎng)絡(luò)節(jié)點重要性的評估。有向有權(quán)網(wǎng)絡(luò)節(jié)點重要性評估、網(wǎng)絡(luò)中不同指標(biāo)間的關(guān)聯(lián)性有待進(jìn)一步研究。