基于SAW-DPDP方法的ad hoc網(wǎng)絡(luò)節(jié)點重要性分析

譚 冕， 趙 靜

(陸軍勤務(wù)學(xué)院軍事物流系， 重慶 401331)

節(jié)點重要度的排序具有重要意義，因為無線ad hoc網(wǎng)絡(luò)節(jié)點的拓?fù)浣Y(jié)構(gòu)不同，重要度大的節(jié)點能夠在更大程度上影響網(wǎng)絡(luò)的結(jié)構(gòu)與功能，優(yōu)先對重要度大的節(jié)點進(jìn)行攻擊，會導(dǎo)致網(wǎng)絡(luò)性能下降更快，故蓄意攻擊通常按照節(jié)點重要度進(jìn)行排序，并按由大到小的順序進(jìn)行攻擊。對節(jié)點重要度的研究有利于保護(hù)網(wǎng)絡(luò)，并提高網(wǎng)絡(luò)的抗毀性，這在戰(zhàn)場或其他惡劣的通信環(huán)境中顯得尤為重要。由于實際應(yīng)用的迫切需求，節(jié)點的重要度排序問題已成為研究熱點。

任卓明等[1]基于節(jié)點度和聚集系數(shù)等局部信息對網(wǎng)絡(luò)節(jié)點進(jìn)行了重要性度量分析，仿真實例證明了此方法對大規(guī)模網(wǎng)絡(luò)的有效性；于會等[2]提出了“逼近立項排序法”的多屬性決策方法，利用節(jié)點的多個指標(biāo)對節(jié)點的重要性進(jìn)行度量，并將其數(shù)值作為節(jié)點的屬性，其具有良好的擴展性；韓忠明等[3]為解決面向結(jié)構(gòu)洞節(jié)點的節(jié)點排序問題，采用基于ListNet的排序?qū)W習(xí)方法吸收網(wǎng)絡(luò)約束系數(shù)、效率、PageRank值等7個度量指標(biāo)，選擇出的節(jié)點具有較高的傳播能力；段東立等[4]建立了一個可調(diào)負(fù)載重分配級聯(lián)失效模型，以此提出考慮級聯(lián)失效局域信息的節(jié)點重要性指標(biāo)，并重點分析了動力學(xué)特征下節(jié)點的演化機理；劉建強等[5]提出了基于節(jié)點疏遠(yuǎn)方法來評價網(wǎng)絡(luò)節(jié)點重要性，該方法合理疏遠(yuǎn)了節(jié)點的關(guān)聯(lián)邊，并選擇能體現(xiàn)全局和局部信息的通信效率和聚集系數(shù)作為度量。

上述研究都是基于網(wǎng)絡(luò)所有節(jié)點的重要性進(jìn)行分析的，并沒有考慮會造成ad hoc網(wǎng)絡(luò)分割的關(guān)鍵節(jié)點[6]。由于ad hoc網(wǎng)絡(luò)中的拓?fù)浣Y(jié)構(gòu)具有不確定性，有的節(jié)點度大，有的節(jié)點是“橋梁”節(jié)點，有的節(jié)點處于中間位置，因此單一的評估方法無法合理評估節(jié)點對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的影響。為了準(zhǔn)確判斷節(jié)點的重要性，筆者針對現(xiàn)有的一些重要性評價指標(biāo)不夠全面的缺點，先用簡單加權(quán)(Simple Additive Weighting，SAW)的方法整合節(jié)點的度、聚集系數(shù)等局部信息，以及介數(shù)中心性、接近中心性等全局信息，然后用分布式分割探測算法(Distributed Partition Detection Protocol，DPDP)判斷網(wǎng)絡(luò)中存在的關(guān)鍵節(jié)點，通過對節(jié)點重要性的綜合排序有效判斷對拓?fù)湄暙I(xiàn)更大的節(jié)點。

1 方法

1.1 基于節(jié)點重要度排序的抗毀性攻擊策略

通信網(wǎng)絡(luò)節(jié)點面對的攻擊方式有隨機攻擊(Random Attack,RD)和蓄意攻擊2種。其中：隨機攻擊是指敵方不能獲知我方通信網(wǎng)絡(luò)精確信息時進(jìn)行的攻擊，這種節(jié)點攻擊方式具有隨機性，成本高且效率低，尤其是以ad hoc網(wǎng)絡(luò)形式組網(wǎng)時，分布式的結(jié)構(gòu)能夠有效應(yīng)對隨機攻擊；蓄意攻擊是指敵方可以獲取相對精確的節(jié)點信息，并能夠以一定的攻擊策略對節(jié)點實施的攻擊行為，相對于隨機攻擊，其效果更明顯，依據(jù)收集的通信節(jié)點拓?fù)湫畔⒌亩嗌?，可以分為局部信息下的蓄意攻擊和全局信息下的蓄意攻擊?/p>

1.1.1 局部信息下的蓄意攻擊策略

如果敵方只能獲取通信節(jié)點的連邊關(guān)系時，可選擇度中心 (Degree Centrality,DC)[7]為指標(biāo)發(fā)起攻擊。在當(dāng)前策略下，節(jié)點的重要性表現(xiàn)為中心性，意味著節(jié)點通過與其他節(jié)點連邊數(shù)量的多少體現(xiàn)重要性，連邊數(shù)量越多則越重要，對拓?fù)浣Y(jié)構(gòu)的影響力越大。

若當(dāng)前網(wǎng)絡(luò)存在任意節(jié)點i，其排序關(guān)系可用歸一化度中心指標(biāo)DC(i)來表示，其計算公式為

(1)

式中：Ni為節(jié)點i的鄰居數(shù)；N為網(wǎng)絡(luò)的節(jié)點數(shù)。

1.1.2 全局信息下的蓄意攻擊策略

1) 基于節(jié)點介數(shù)方法的攻擊策略。當(dāng)敵方能夠獲取我方全局的拓?fù)湫畔r，可選擇基于節(jié)點介數(shù)作為評估指標(biāo)。介數(shù)中心性(Betweenness Centrality,BC)[8]認(rèn)為：網(wǎng)絡(luò)中經(jīng)過一個節(jié)點的最短路徑數(shù)越多，則這個節(jié)點就越重要，其排序關(guān)系可表示為

(2)

2) 基于節(jié)點接近中心性方法的攻擊策略。當(dāng)敵方能夠獲取節(jié)點與網(wǎng)絡(luò)中其他節(jié)點平均距離的信息時，可選擇基于節(jié)點接近中心性 (Closeness Centrality,CC)[9]的攻擊策略。要使得節(jié)點i接近中心性CC(i)數(shù)值較大，則需使節(jié)點i與其他節(jié)點的平均距離di較小，其計算公式分別為

(3)

(4)

式中：dij為節(jié)點i和j之間的最短路徑長度。

1.1.3 攻擊策略流程

攻擊策略流程如下：

1) 歸類、分析掌握的搜救通信節(jié)點信息；

2) 選擇具體的攻擊策略和范圍；

3) 根據(jù)是否有保護(hù)節(jié)點的措施和攻擊的強度，判斷節(jié)點是否失效；

4) 若節(jié)點失效，則刪除該節(jié)點及連邊；

5) 當(dāng)攻擊策略刪除了網(wǎng)絡(luò)所有節(jié)點或者當(dāng)前攻擊范圍內(nèi)的節(jié)點，則停止攻擊，否則回到步驟2)。

1.2 考慮關(guān)鍵節(jié)點的攻擊策略

假設(shè)圖G=(V,E) 是一個雙向的網(wǎng)絡(luò)，其中V={v1,v2,…,vN}，是網(wǎng)絡(luò)中所有節(jié)點vi(i=1,2,…,N)的集合，|V|=N;E={e1,e2,…,em}?V×V，是節(jié)點間邊ej(j=1,2,…,m)的集合，|E|=m。

無線ad hoc網(wǎng)絡(luò)節(jié)點在功能上是平等的，但存在部分節(jié)點對整個網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)影響較大，如：作為2個獨立子網(wǎng)唯一通道的節(jié)點，當(dāng)該節(jié)點失效時，網(wǎng)絡(luò)將分化成2個子網(wǎng)絡(luò)，極大地影響網(wǎng)絡(luò)連通性，此類節(jié)點可稱為關(guān)鍵節(jié)點。介數(shù)中心性最大的節(jié)點有可能是關(guān)鍵節(jié)點，但上述攻擊策略沒有明確指出這類節(jié)點，敵方若能夠檢測出關(guān)鍵節(jié)點且加以攻擊，則對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)造成更大的威脅；我方若對關(guān)鍵節(jié)點進(jìn)行保護(hù)，則可以增強網(wǎng)絡(luò)抗分割的能力。

1.2.1 基于SAW的節(jié)點重要性判斷方法

SAW方法作為多準(zhǔn)則決策(Multi-Criteria Decision-Making,MCDM)的重要方法之一，能夠從多角度綜合評估，進(jìn)而為最優(yōu)決策的選擇提供參考。

分別選擇局部和全局拓?fù)湫畔⒅笜?biāo)進(jìn)行關(guān)鍵節(jié)點的檢測。局部拓?fù)湫畔ǘ戎行男院途奂禂?shù)；全局拓?fù)湫畔ń閿?shù)中心性和接近中心性。其中：度中心性主要考慮節(jié)點影響鄰居的數(shù)量，節(jié)點度越大，則該節(jié)點越重要；聚集系數(shù)主要考慮鄰居節(jié)點間的可替代性，替代性越差，則地位越重要[10]；介數(shù)中心性認(rèn)為網(wǎng)絡(luò)中經(jīng)過一個節(jié)點的最短路徑數(shù)越多，則這個節(jié)點就更重要；網(wǎng)絡(luò)中節(jié)點與其他節(jié)點的平均距離的倒數(shù)定義為接近中心性，其值越大，則意味著該節(jié)點的信息能更快地傳播出去。

基于上述因素的考慮，通過SAW的方法融合度中心性、聚集系數(shù)、介數(shù)中心性和接近中心性這4個重要性屬性，并通過在多因素之間的參數(shù)調(diào)節(jié)，最終得到想要的重要性數(shù)值，加權(quán)后的節(jié)點重要性為

NI(i)=k1[DC(i)×F(Ci)]+k2CC(i)+k3BC(i)，

(5)

式中：k1、k2、k3為調(diào)節(jié)權(quán)重，且k1+k2+k3=1，0≤k1,k2,k3≤1；Ci為節(jié)點i的聚集系數(shù)，其計算公式為

(6)

其中Ei為節(jié)點i與鄰居節(jié)點間的連邊數(shù)量；F(Ci)為Ci的函數(shù)，其計算公式為

F(Ci)=10-Ci。

(7)

1.2.2 基于DPDP的關(guān)鍵節(jié)點檢測方法

在得到所有節(jié)點的重要性數(shù)值后，需要進(jìn)一步分析網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，找出ad hoc網(wǎng)絡(luò)可能出現(xiàn)的關(guān)鍵節(jié)點。

關(guān)鍵節(jié)點的檢測方法選擇李建東等[11]提出的DPDP方法，即

Ni-Mi≥2。

(8)

式中：Mi為基本回路度，即節(jié)點i經(jīng)過不同鄰居節(jié)點對的基本回路總數(shù)。當(dāng)節(jié)點i滿足式(8)時，該節(jié)點就是關(guān)鍵節(jié)點。

基本回路度Mi=∑Ci(j,k)。鄰居節(jié)點對及基本回路如圖1所示。

當(dāng)計算出網(wǎng)絡(luò)存在的關(guān)鍵節(jié)點后，需要對NI(i)進(jìn)行如下修正：

(9)

式中：ω為附加值。

因為0≤NI(i)≤1，修正后關(guān)鍵節(jié)點會處于優(yōu)先攻擊的序列中。若同為關(guān)鍵節(jié)點，則會按照局部、全局拓?fù)湫畔⒎治龀鲫P(guān)鍵節(jié)點中最有價值的節(jié)點，故使用該攻擊策略可以有效識別出ad hoc網(wǎng)絡(luò)中關(guān)鍵節(jié)點的重要性，并按照順序進(jìn)行有效打擊。

2 抗毀測度

無線ad hoc網(wǎng)絡(luò)抗毀性是指節(jié)點遭到攻擊后拓?fù)浣Y(jié)構(gòu)被破壞的難易程度，需要根據(jù)研究的內(nèi)容合理選擇抗毀性指標(biāo)。本文假定由搜救人員組成的ad hoc網(wǎng)絡(luò)遭受打擊后信息傳輸無法得到保障，搜救活動受阻，故選擇能夠連通最大通信區(qū)域的連通系數(shù)和可以考察網(wǎng)絡(luò)連通性好壞的網(wǎng)絡(luò)效率作為抗毀性指標(biāo)。

從通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)角度看，重要度高的關(guān)鍵節(jié)點很容易被優(yōu)先列入打擊目標(biāo)。節(jié)點的重要性往往也體現(xiàn)在該節(jié)點被移除之后對網(wǎng)絡(luò)的破壞性，因此為進(jìn)一步比較節(jié)點間的重要性，通過刪除節(jié)點的方法進(jìn)行衡量。引入連通系數(shù)S作為抗毀測度，其計算公式為

(10)

式中：N′為最大連通片的節(jié)點數(shù)；N為初始節(jié)點數(shù)。僅考慮單點打擊時，分別計算移除一定比例節(jié)點后網(wǎng)絡(luò)的最大連通率。

為了方便對比，本文還選擇了另一種衡量指標(biāo)，即網(wǎng)絡(luò)效率，用以表示網(wǎng)絡(luò)連通性的好壞。如果網(wǎng)絡(luò)中節(jié)點被刪除后，則該節(jié)點與其鄰居的聯(lián)系也會斷掉。假設(shè)當(dāng)前網(wǎng)絡(luò)進(jìn)行節(jié)點刪除操作后，節(jié)點i的信息仍然能夠到達(dá)節(jié)點j，可能因為某些節(jié)點的刪除，導(dǎo)致節(jié)點i到達(dá)節(jié)點j的最短路徑長度dij增大，進(jìn)而可以推測出整個網(wǎng)絡(luò)的連通性可能有所降低，用1/dij表示節(jié)點i、j的連通效率，故網(wǎng)絡(luò)效率可表示為

(11)

式中：G為最大連通圖。

由式(11)可知：若ε=0，意味著網(wǎng)絡(luò)中的節(jié)點全部是孤立節(jié)點；ε=1，代表網(wǎng)絡(luò)連通性最好。本文通過刪除的方法對比分析網(wǎng)絡(luò)節(jié)點重要性攻擊策略的優(yōu)劣，需要計算網(wǎng)絡(luò)沒有遭受攻擊時的效率ε0和刪除了一定比例節(jié)點后的效率ε，則網(wǎng)絡(luò)效率的下降比例

(12)

顯然有，ε，e∈[0,1]。當(dāng)e=1時，意味著網(wǎng)絡(luò)效率為0；當(dāng)e=0時，則網(wǎng)絡(luò)效率不變。當(dāng)e的數(shù)值逐步變大時，意味著網(wǎng)絡(luò)效率逐步下降，以此可對重要性方法的準(zhǔn)確性進(jìn)行度量。

3 仿真分析

通過MALAB進(jìn)行仿真，考察不同攻擊策略對網(wǎng)絡(luò)連通系數(shù)的影響和對網(wǎng)絡(luò)效率下降比例的影響。

仿真的主要參數(shù)為：節(jié)點數(shù)N=36；節(jié)點刪除比例del=0.1∶0.1∶0.9；通信半徑R1=200，R2=100；仿真時長T=400；蒙特卡羅次數(shù)MC=50；關(guān)鍵節(jié)點附加值ω=1。仿真場景假設(shè)為500 m×500 m。通過合理選擇不同的通信半徑，使構(gòu)建的ad hoc網(wǎng)絡(luò)具有小世界網(wǎng)絡(luò)的特性。移動模型選擇基于關(guān)鍵位置的2D 隨機游走移動模型[12](2D Random Walk with Key Localization,2D RWKL)，該移動模型會根據(jù)遇險人員的位置信息展開一定區(qū)域范圍內(nèi)的搜索行動，具有一定的真實性。

由于生成的網(wǎng)絡(luò)模型具有隨機性，因此最后得到的圖形數(shù)據(jù)有一定的誤差，為了更好地表現(xiàn)趨勢，需要對得到的網(wǎng)絡(luò)連通系數(shù)、網(wǎng)絡(luò)效率下降比例進(jìn)行擬合。結(jié)合圖形的趨勢，選擇二階多項式進(jìn)行擬合，得到的和方差接近于0，具有較好的擬合效果。

3.1 不同攻擊策略對網(wǎng)絡(luò)連通系數(shù)的影響

圖2為不同攻擊策略對網(wǎng)絡(luò)連通系數(shù)的影響，可見：隨著刪除比例的增加，網(wǎng)絡(luò)連通系數(shù)近似于呈線性減小的趨勢。同時，不管是哪種攻擊策略，只要攻擊掉了相應(yīng)比例的節(jié)點，在計算連通效率時，若連通系數(shù)低于攻擊比例，說明此時必然已經(jīng)產(chǎn)生了“信息孤島”節(jié)點。不同攻擊策略對網(wǎng)絡(luò)連通系數(shù)的影響順序是：SAW-DPDP>BC>CC>DC>RD。

當(dāng)刪除比例為0.8、0.9時，不同攻擊策略下網(wǎng)絡(luò)連通系數(shù)的數(shù)值很接近，這是因為刪除比例過高導(dǎo)致現(xiàn)存最大連通片內(nèi)的節(jié)點數(shù)目很少，基本無法體現(xiàn)出不同方法的區(qū)別。

SAW-DPDP方法在仿真過程中，連通系數(shù)始終處于最低值，說明該方法能夠有效得出節(jié)點的重要程度。隨后按照得到的節(jié)點重要性排序進(jìn)行攻擊，相對于其他攻擊策略，SAW-DPDP能夠使連通系數(shù)最小，亦即將網(wǎng)絡(luò)分成多個“信息孤島”，且最大連通片包含的節(jié)點數(shù)最少，說明該方法有利于在這種場景中實現(xiàn)，可達(dá)到最佳效果，也驗證了方法的有效性。

RD即隨機攻擊策略，由于ad hoc網(wǎng)絡(luò)分布式的結(jié)構(gòu)，其連通系數(shù)最高，故可以有效應(yīng)對這種攻擊方法。

基于DC、RD方法的攻擊策略在連通系數(shù)上幾乎保持一致的水準(zhǔn)，這是因為完全以度為指標(biāo)進(jìn)行判斷的局部拓?fù)浞椒ㄔ诋?dāng)前網(wǎng)絡(luò)中不能體現(xiàn)出優(yōu)勢，因為每個節(jié)點的度數(shù)可能差距不大，且有多條路徑存在的可能。

基于CC方法可以通過計算節(jié)點與網(wǎng)絡(luò)中其他節(jié)點的距離表示重要性，而BC方法通過節(jié)點最短路徑數(shù)量描述其重要性。由圖2可知：BC的方法更適用于ad hoc網(wǎng)絡(luò)，能夠更精確地描述節(jié)點的重要性。

3.2 不同攻擊策略對網(wǎng)絡(luò)效率下降比例的影響

圖3為不同攻擊策略對網(wǎng)絡(luò)效率下降比例的影響，可見：隨著刪除比例的增加，網(wǎng)絡(luò)效率下降比例近似于呈線性增加的趨勢;當(dāng)刪除比例為0.9時，網(wǎng)絡(luò)效率下降比例接近于1，說明此時網(wǎng)絡(luò)效率幾乎為0，節(jié)點間的距離近似于無限大，當(dāng)前網(wǎng)絡(luò)全部是孤立節(jié)點，信息基本無法傳遞出去。不同攻擊策略對網(wǎng)絡(luò)效率下降比例的影響順序是：SAW-DPDP>CC>BC>DC>RD。

隨著刪除比例的增加，SAW-DPDP方法始終對網(wǎng)絡(luò)效能構(gòu)成較大威脅，網(wǎng)絡(luò)效率逐步下降，網(wǎng)絡(luò)效率下降比例逐步增大，說明該方法相對于其他方法能夠使最短路徑長度增大最快。

CC方法在網(wǎng)絡(luò)效率下降比例的影響序列為第二，在網(wǎng)絡(luò)連通系數(shù)的影響中排第三，這是因為CC方法計算網(wǎng)絡(luò)的中心性，即與計算網(wǎng)絡(luò)效率下降比例的評估方法同樣考察平均路徑長度的變化，故在抗毀測度指標(biāo)上表現(xiàn)較BC方法更好。

4 結(jié)論

筆者提出的SAW-DPDP方法通過多指標(biāo)的方式對ad hoc網(wǎng)絡(luò)中的節(jié)點進(jìn)行評分排序，用刪除法驗證其準(zhǔn)確性，在考慮網(wǎng)絡(luò)中關(guān)鍵節(jié)點對拓?fù)浣Y(jié)構(gòu)影響的情況下，對評分排序進(jìn)行一定的修正。綜合的方法中不僅有局部拓?fù)湫畔ⅲ布尤肓巳滞負(fù)湫畔⒅笜?biāo)[13]。仿真結(jié)果表明：SAW-DPDP方法由于綜合的元素較多，因此適用性較單一評估方法更強，且能夠有效判斷ad hoc網(wǎng)絡(luò)中的關(guān)鍵節(jié)點。但該方法也存在算法復(fù)雜度較高的問題。在未來的研究中還應(yīng)考慮對需要優(yōu)先保護(hù)的節(jié)點增強其防護(hù)性，以提高網(wǎng)絡(luò)的抗毀性[14]，或應(yīng)用于不同的真實網(wǎng)絡(luò)中。