戰(zhàn)術(shù)移動點對點Ad-Hoc作戰(zhàn)單元拓撲重構(gòu)

蔣馥蔚，王葉群，李艷福，趙尚弘

(空軍工程大學信息與導航學院軍事航空通信重點實驗室，西安 710071)

地面戰(zhàn)術(shù)移動點對點Ad-Hoc作戰(zhàn)單元，是一種分布式終端直通(device to device,D2D)網(wǎng)絡(luò)[1]，節(jié)點依據(jù)作戰(zhàn)需求攜帶武器裝備，遂行具體作戰(zhàn)任務(wù)，往往有固定的執(zhí)行路徑與活動范圍，不能隨意移動位置，單元內(nèi)節(jié)點之間由于地形或障礙物的因素，網(wǎng)絡(luò)分割及節(jié)點脫網(wǎng)時有發(fā)生。保持網(wǎng)絡(luò)拓撲的完整性，是保證信息有效傳輸?shù)那疤?，已有的對于多跳網(wǎng)絡(luò)拓撲控制與優(yōu)化的研究，主要從鏈路控制的角度出發(fā)，通過節(jié)點發(fā)送功率控制的手段重新構(gòu)建網(wǎng)絡(luò)拓撲，如文獻[2]在區(qū)分信息流類別的基礎(chǔ)上，通過調(diào)整節(jié)點功率，從而實現(xiàn)節(jié)點加邊控制的方法來重構(gòu)拓撲；文獻[3-4]通過控制節(jié)點功率選擇路徑，文獻[5-6]考慮網(wǎng)絡(luò)整體業(yè)務(wù)效率，采用功率控制與業(yè)務(wù)重路由等方式提高傳輸有效性。文獻[7]采用自適應(yīng)人工免疫算法，設(shè)計層次型拓撲結(jié)構(gòu)來優(yōu)化網(wǎng)絡(luò)功耗，延長網(wǎng)絡(luò)壽命。這些研究，均沒有考慮當拓撲連通的關(guān)鍵節(jié)點因遮擋而脫網(wǎng)或相鄰節(jié)點超出節(jié)點最大覆蓋范圍時，單純使用調(diào)整功率的方式很難或無法修復拓撲連通性。

基于此，現(xiàn)提出，隨著地面D2D節(jié)點的移動，空中無人機中繼主要用來輔助地面網(wǎng)絡(luò)的關(guān)鍵節(jié)點通信，使網(wǎng)絡(luò)拓撲保持完整，因此稱空中無人機中繼為拓撲機器人節(jié)點，暫不考慮移動速率等因素，使拓撲機器人節(jié)點與地面網(wǎng)絡(luò)呈相對靜止狀態(tài)，拓撲機器人節(jié)點監(jiān)視地面網(wǎng)絡(luò)拓撲，優(yōu)化及重構(gòu)拓撲。當?shù)孛婀?jié)點由于遮擋或損毀等因素脫網(wǎng)時，拓撲機器人節(jié)點調(diào)整相對位置，維持拓撲完整性。

1 相關(guān)研究

關(guān)于無人機中繼的D2D網(wǎng)絡(luò)的研究所考慮的場景，如圖1所示，空中無人機中繼是靜止盤懸的狀態(tài)以代替地面基站[8]，或者地面節(jié)點是靜止狀態(tài)，從中繼部署、中繼信道選擇、節(jié)點能量優(yōu)化等角度，主要關(guān)注網(wǎng)絡(luò)資源分配[9-10]，而對于地面節(jié)點與空中節(jié)點都需要移動推進，過程中拓撲連通情況的保持，尚未引起關(guān)注。

圖1 拓撲機器人中繼的地面分布式Ad-Hoc作戰(zhàn)單元

現(xiàn)有的對多跳網(wǎng)絡(luò)拓撲控制與優(yōu)化的研究，主要從鏈路控制的角度出發(fā)，通過加邊減邊以及業(yè)務(wù)重路由等方式提高傳輸有效性?，F(xiàn)提出的拓撲機器人補盲的方式，是一種節(jié)點控制算法，通過調(diào)整拓撲機器人的相對位置，使處于冗余位置的拓撲機器人移動來重構(gòu)網(wǎng)絡(luò)拓撲，改善網(wǎng)絡(luò)連通性。中繼部署算法的拓撲機器人與地面節(jié)點是異構(gòu)的關(guān)系，拓撲機器人對拓撲的監(jiān)視，是對地面分布式節(jié)點的相對位置的一種集中管理，可以對網(wǎng)絡(luò)連通關(guān)鍵點進行重要性量化，以有效優(yōu)化網(wǎng)絡(luò)拓撲。

拓撲機器人調(diào)整相對位置的依據(jù)，便是要找到網(wǎng)絡(luò)連通關(guān)鍵點。評價網(wǎng)絡(luò)連通關(guān)鍵點的常用方法，就是找到網(wǎng)絡(luò)中對連通性影響最大的節(jié)點，即節(jié)點重要度的方法來度量。歷年來研究節(jié)點重要度所演化的算法，已有的有節(jié)點刪除法、介數(shù)法、收縮法、模型分析方法等，以節(jié)點連接度、節(jié)點間最短路徑等作為度量指標；考慮節(jié)點之間的相互作用，文獻[11-12]提出了評價矩陣、貢獻矩陣來得出節(jié)點重要度排序。在已有算法的基礎(chǔ)上，考慮節(jié)點連通重要性，從是否割點、節(jié)點度值及信息流傳輸效率衡量，分別反映了節(jié)點分裂影響度，局部重要性與全局重要性。并按照預防性拓撲重構(gòu)與修復性拓撲重構(gòu)兩個方面來設(shè)計拓撲機器人重構(gòu)拓撲算法。

2 節(jié)點重要度計算

2.1 理論基礎(chǔ)

定義網(wǎng)絡(luò)圖中，節(jié)點集合分別為任務(wù)節(jié)點集合V，拓撲機器人節(jié)點集合R，連接拓撲機器人邊的集合L，任務(wù)節(jié)點之間邊的集合M，因此設(shè)圖G=(V,R,L,M)是一個無自環(huán)的無向網(wǎng)絡(luò)，網(wǎng)絡(luò)中總的節(jié)點數(shù)量n=n(V)+n(R)。

2.1.1 定義1 鄰接矩陣

設(shè)分布式網(wǎng)絡(luò)G的鄰接矩陣用E(G)=(aij)n×n表示，考慮雙向通信鏈路，其中aij表示節(jié)點i和節(jié)點j之間的連通情況，若i和j之間存在鏈路，則aij=1，否則aij=0。G是無向圖，E(G)是對稱矩陣。

2.1.2 定義2 節(jié)點鄰域

節(jié)點最大發(fā)送功率所覆蓋的區(qū)域稱為節(jié)點鄰域，用Rmax(vi)=G[Nmax(vi),Emax(vi)]表示，其中Nmax(vi)為落入節(jié)點vi鄰域內(nèi)的節(jié)點集合，Emax(vi)為節(jié)點vi鄰域拓撲的鏈路集合。

2.1.3 定義3 節(jié)點度值

節(jié)點的度值digi與節(jié)點重要度的關(guān)系很大，當前節(jié)點對相鄰節(jié)點的影響力可以通過節(jié)點度值來反映，節(jié)點度值是指與當前節(jié)點直接互聯(lián)的節(jié)點數(shù)目。節(jié)點度值越大，該節(jié)點對其相鄰節(jié)點的影響越大。節(jié)點領(lǐng)域的節(jié)點數(shù)量，是節(jié)點工作在最大發(fā)送功率下的節(jié)點度值。

2.1.4 定義4 割點及連通度

節(jié)點vi是割點，或稱關(guān)節(jié)點，當存在不同于vi的2個頂點vu、vω，使得vi在每一條由vu到vω的路上。存在V-{vi}的一個劃分V-{vi}=U∪W，其中U∩W=?，使得?vu∈U,?vi∈V滿足vi在每一條由vu到vω的路上。當關(guān)節(jié)點vi失效時，必然會造成網(wǎng)絡(luò)分裂。沒有關(guān)節(jié)點的連通圖稱為重連通圖。圖的連通度定義為，至少移除k個頂點才能破壞圖的連通性，則該圖的連通度為k。用數(shù)學描述為：設(shè)V′是V中任一非空真子集，若圖G連通而G[V-V′]不連通，則稱V′是G的點割集。最小點割集中頂點的個數(shù)就是圖G的連通度κ(G)。

2.1.5 定義5 節(jié)點重要度貢獻矩陣

網(wǎng)絡(luò)中的節(jié)點總數(shù)為n，〈k〉為節(jié)點的平均度值,若節(jié)點vi的度為digi,則該節(jié)點將重要度的digi/〈k〉2貢獻給每一個相鄰節(jié)點。將所有節(jié)點對其相鄰節(jié)點的重要度貢獻比例值用矩陣的形式表示出來，便是節(jié)點重要度貢獻矩陣，即

HIC=

(1)

式(1)中：δij為貢獻分配參數(shù)，當兩個節(jié)點(vi，vj)直接相連時值為1，否則值為0；對角線上的1為每個節(jié)點對自身的重要度貢獻比例值；HICij為節(jié)點j對節(jié)點i的重要度貢獻比例值，可以看出重要度貢獻比例值越大的節(jié)點，其對相鄰節(jié)點的影響也越大。鄰接矩陣與HIC具有相同的結(jié)構(gòu)，HIC是網(wǎng)絡(luò)鄰接矩陣的一個映射，其規(guī)則為

(2)

2.1.6 定義6 節(jié)點效率

2.1.7 定義7 節(jié)點重要度評價矩陣

用度來構(gòu)建節(jié)點之間的重要度關(guān)聯(lián)，用節(jié)點傳輸貢獻率標識節(jié)點在網(wǎng)絡(luò)信息傳輸中的位置，可以得到重要度評價矩陣HE為

HE=

(3)

2.2 節(jié)點重要度評價的算法設(shè)計

(4)

計算出的網(wǎng)絡(luò)中的最重要節(jié)點就是對網(wǎng)絡(luò)連通性及網(wǎng)絡(luò)信息傳輸起到關(guān)鍵作用的節(jié)點，一旦該節(jié)點失效，會引起網(wǎng)絡(luò)分裂，造成網(wǎng)絡(luò)性能較大的下降。考慮節(jié)點連通重要性，從是否割點、節(jié)點度值及信息流傳輸效率衡量，分別反映了節(jié)點分裂影響度，局部重要性與全局重要性。從節(jié)點重要度定義來看，節(jié)點的重要度貢獻及節(jié)點效率都是小于1的歸一化參量，而割點權(quán)值賦值2，可見，割點是拓撲優(yōu)化時首先考慮的關(guān)鍵節(jié)點。當網(wǎng)絡(luò)中有多個割點時，才需要對連通關(guān)鍵點依據(jù)該公式重新計算關(guān)鍵點，若只有一個割點，只需要比較拓撲機器人的重要度以確定移動重要度最小的拓撲機器人。若網(wǎng)絡(luò)中沒有割點，維持拓撲現(xiàn)狀。

3 基于拓撲機器人的網(wǎng)絡(luò)拓撲重構(gòu)算法

要進行拓撲重構(gòu)，拓撲機器人要能夠判斷在當前拓撲中的關(guān)鍵節(jié)點以及脫網(wǎng)節(jié)點。拓撲機器人周期性發(fā)送拓撲探測消息，收集網(wǎng)絡(luò)拓撲，步驟如下。

(1)基于割點判定，預防性拓撲重構(gòu)。通過深度優(yōu)先算法，發(fā)現(xiàn)網(wǎng)絡(luò)割點，并計算節(jié)點重要度，進行重要度排序。在進行預防性重構(gòu)時，重要度最小的拓撲機器人節(jié)點需要判斷自身局部冗余度，通過一跳鄰域確定自身不是割點，兩跳鄰域確定自身移動后不會帶來新的割點。

(2)基于拓撲探測響應(yīng)周期的延遲，進行斷點判定，修復性拓撲重構(gòu)。在進行修復性重構(gòu)時，設(shè)定拓撲機器人節(jié)點在5個周期未收到某節(jié)點的響應(yīng)，即認為該節(jié)點已脫網(wǎng)，需要啟動修復性重構(gòu)算法，修復性重構(gòu)依然要計算拓撲機器人的重要度排序，并判斷自身移動不會帶來新的網(wǎng)絡(luò)分裂，再移動去修復拓撲。當節(jié)點大面積失效時，需要按算法多次移動多個拓撲機器人節(jié)點。拓撲重構(gòu)流程如圖2所示。

圖2 拓撲重構(gòu)流程圖

4 實驗分析

從兩個方面分別進行實驗分析，介紹依據(jù)節(jié)點重要度對拓撲機器人進行位置調(diào)整所帶來的網(wǎng)絡(luò)抗毀性能的提升的衡量方法，網(wǎng)絡(luò)節(jié)點故障數(shù)與拓撲機器人數(shù)量之間的關(guān)系的表現(xiàn)形式。

4.1 預防性重構(gòu)抗毀性分析及節(jié)點重要度計算

對于割點對抗毀性造成的影響，適用聚合度來衡量，表達式為

(5)

式(5)中：S為由圖G的若干頂點構(gòu)成的集合，若G-S是不連通的，則稱S為圖G的一個頂點割；|S|為這個頂點割中頂點的數(shù)目。將C(G)記為圖G的所有頂點割組成的集合。圖G-S的連通分支數(shù)被記為w(G-S)，圖G-S的最大連通分支的節(jié)點數(shù)記為τ(G-S)。最大分支頂點數(shù)越多，連通分支越少，割點越少，一個圖的聚合度i(G)越大，那么它所對應(yīng)網(wǎng)絡(luò)的抗毀性越強。當|S|=0時，w=1，τ=N，網(wǎng)絡(luò)中節(jié)點越多，抗毀性越強。

圖3 存在割點和預防性重構(gòu)后的網(wǎng)絡(luò)拓撲

表1 節(jié)點重要度計算及排序

若不考慮割點權(quán)值，計算出最重要的節(jié)點是節(jié)點v3，而節(jié)點v3失效并不會帶來網(wǎng)絡(luò)分裂，對于連通性而言，影響不如割點v6。找到節(jié)點重要度最小的拓撲機器人v7，v7的兩跳領(lǐng)域拓撲連通，移動后不會帶來新的割點；移動至離當前位置最近的預防性重構(gòu)位置，連接{v6,v5,v9}來估計修復后的抗毀度，如圖3(b)所示，此時網(wǎng)絡(luò)不再有割點，因此，w=1最大連通分支頂點數(shù)為τ=9，重構(gòu)網(wǎng)絡(luò)抗毀度為i=9,抗毀性增量為Δi=9-2.5=6.5，因此機動拓撲機器人節(jié)點v7來進行預防性重構(gòu)可以提高網(wǎng)絡(luò)抗毀性。

4.2 重構(gòu)前后性能比較

對網(wǎng)絡(luò)節(jié)點故障數(shù)比較多，拓撲機器人移動修復網(wǎng)絡(luò)連通性的性能測試，需要結(jié)合網(wǎng)絡(luò)仿真來驗證。使用NS-3網(wǎng)絡(luò)模擬軟件對拓撲重構(gòu)算法性能進行仿真測試，仿真環(huán)境為地面任務(wù)節(jié)點數(shù)100個，非均勻分布在400 km×400 km的范圍內(nèi)，地面節(jié)點視距通信半徑為最大8 km,節(jié)點鏈路由于地形以及建筑物遮擋等因素會發(fā)生中斷，空中拓撲機器人節(jié)點5個，每個節(jié)點覆蓋半徑最大為100 km,拓撲機器人之間可以實現(xiàn)視距通信，地空鏈路仰角對地空鏈路連通性的影響暫不考慮。仿真中應(yīng)用層采用CBR數(shù)據(jù)流，每個報文512 Byte，設(shè)置300個數(shù)據(jù)流，通過設(shè)置不同的節(jié)點運動場景，采用多次仿真求平均值的方式，對比了在拓撲重構(gòu)前后網(wǎng)絡(luò)性能的變化情況，采用分組成功投遞率作為分析的依據(jù)。分組成功投遞率反映網(wǎng)絡(luò)處理和傳輸數(shù)據(jù)的能力。其定義為：在應(yīng)用層，目的節(jié)點接收到的分組數(shù)與源節(jié)點發(fā)送的分組數(shù)之比。

由圖4(a)可以看出，拓撲機器人在網(wǎng)絡(luò)沒有故障時，預防性重構(gòu)網(wǎng)絡(luò)拓撲，重構(gòu)后的分組成功投遞率一直保持在較高水平，而重構(gòu)前，隨著發(fā)包速率的增加，網(wǎng)絡(luò)負載較重時, 拓撲中關(guān)鍵點成了數(shù)據(jù)傳輸業(yè)務(wù)的瓶頸, 使網(wǎng)絡(luò)發(fā)生擁塞, 大量分組無法成功到達目的節(jié)點, 投遞率快速減少。網(wǎng)絡(luò)拓撲結(jié)構(gòu)在重構(gòu)算法的作用下逐漸趨于均衡, 為路由的優(yōu)化選擇和負載均衡分配提供較好的基礎(chǔ), 提高了通信效率, 優(yōu)化了網(wǎng)絡(luò)性能。

圖4 發(fā)包速率和網(wǎng)絡(luò)故障數(shù)對分組成功投遞率的影響

圖4(b)仿真中發(fā)包速率為1個數(shù)據(jù)包/s, 可以看到，當網(wǎng)絡(luò)中的故障數(shù)較少時，重構(gòu)前后的分組成功投遞率都較高，這是由于網(wǎng)絡(luò)中存在拓撲機器人節(jié)點，少量故障對拓撲連通性破壞不明顯，關(guān)鍵點發(fā)生故障的概率也較小，隨著網(wǎng)絡(luò)故障數(shù)的增加，分組成功投遞率快速減少，這是由于網(wǎng)絡(luò)中出現(xiàn)大量故障時, 關(guān)鍵節(jié)點的故障概率也隨之增大, 對拓撲連通性破壞嚴重, 使網(wǎng)絡(luò)中可用路由減少, 造成生存下來的路徑傳輸質(zhì)量和效率下降, 導致成功到達目的節(jié)點的分組數(shù)急劇減少。拓撲重構(gòu)策略通過拓撲機器人節(jié)點的移動修復拓撲故障并對拓撲結(jié)構(gòu)進行優(yōu)化, 為上層協(xié)議的高效運行提供了保障, 使網(wǎng)絡(luò)性能得到了有效的恢復, 增強了網(wǎng)絡(luò)的抗毀性。

研究并未考慮時延、節(jié)點相對速度、信道容量、能耗等其他因素，主要關(guān)注點在拓撲連通性的保持上，為了驗證拓撲機器人對拓撲重構(gòu)的可靠性與有效性，與現(xiàn)有的鏈路控制算法對比，理論上可以推測出，當處于最大發(fā)射功率的條件下，所有的加邊算法都無法繞過遮擋進行網(wǎng)絡(luò)拓撲重構(gòu)，當節(jié)點發(fā)生故障時，也無法超出節(jié)點鄰域加邊重構(gòu)。而本文算法在考慮最大發(fā)射功率的前提下，通過增加冗余拓撲機器人節(jié)點，來監(jiān)視拓撲，改善連通，與鏈路控制的加邊算法結(jié)合，可以有效節(jié)約能量，提高網(wǎng)絡(luò)抗毀性。

為了與鏈路控制算法進行對比，按照文獻[2]中的抗毀性定義，網(wǎng)絡(luò)中正常傳遞信息的信息流條數(shù)會隨著通信實體的不斷損毀而減少，因此其信息流抗毀度為網(wǎng)絡(luò)中連通節(jié)點對與損毀節(jié)點總數(shù)的比值，也就是分組成功投遞率隨著網(wǎng)絡(luò)故障數(shù)的變化關(guān)系。文獻[2]中的綜合抗毀度f，當各種信息流具有相同的權(quán)值時，反映的便是網(wǎng)絡(luò)的分組成功投遞率隨網(wǎng)絡(luò)故障數(shù)的變化關(guān)系，在本文算法相同的仿真前提條件下，不設(shè)置拓撲機器人節(jié)點，采用文獻[7]中的DABC算法，進行多次仿真取平均，得到如圖4(b)中所示結(jié)果。本文算法結(jié)果是多次仿真取平均，因此曲線較文獻[7]的仿真結(jié)果6平滑，但得到的抗毀度取值區(qū)間與文獻[7]的仿真結(jié)果6一致，當節(jié)點損毀比率達到20%時，其對應(yīng)隨機攻擊抗毀性能f處于區(qū)間[0.4,0.6]，即分組成功投遞率低于60%，而本文算法分組成功投遞率可接近80%，DABC算法分組成功投遞率明顯低于本文算法。這是由于加邊算法無法獲得超出節(jié)點領(lǐng)域的節(jié)點進行加邊連接，而本文算法通過拓撲機器人節(jié)點冗余獲得拓撲結(jié)構(gòu)更大的靈活性，除損壞節(jié)點無法通信外，存留節(jié)點均可重新建立連接，因此帶來更好的抗毀性能。

5 結(jié)論

為提高地面戰(zhàn)術(shù)移動Ad-Hoc作戰(zhàn)單元的拓撲抗毀性，增加拓撲機器人來監(jiān)視網(wǎng)絡(luò)拓撲，對連通關(guān)鍵節(jié)點從網(wǎng)絡(luò)分裂影響度、鄰居斷鏈影響度、最短路徑中斷影響度來綜合定義，計算節(jié)點重要度，機動重要度最小的拓撲機器人節(jié)點來重構(gòu)與修復網(wǎng)絡(luò)拓撲，仿真結(jié)果表明了拓撲機器人對網(wǎng)絡(luò)抗毀性能的提升。研究并未考慮時延、能耗、冗余代價等與增加拓撲機器人對網(wǎng)絡(luò)性能影響相關(guān)的其他變量，下一步，考慮拓撲機器人部署方法給地面移動Ad-Hoc作戰(zhàn)單元帶來更多性能提升，如最小化時延、最小化能量等指標，開展更多相關(guān)研究。