戰術移動點對點Ad-Hoc作戰單元拓撲重構

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

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

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

基于此，現提出，隨著地面D2D節點的移動，空中無人機中繼主要用來輔助地面網絡的關鍵節點通信，使網絡拓撲保持完整，因此稱空中無人機中繼為拓撲機器人節點，暫不考慮移動速率等因素，使拓撲機器人節點與地面網絡呈相對靜止狀態，拓撲機器人節點監視地面網絡拓撲，優化及重構拓撲。當地面節點由于遮擋或損毀等因素脫網時，拓撲機器人節點調整相對位置，維持拓撲完整性。

1 相關研究

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

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

現有的對多跳網絡拓撲控制與優化的研究，主要從鏈路控制的角度出發，通過加邊減邊以及業務重路由等方式提高傳輸有效性。現提出的拓撲機器人補盲的方式，是一種節點控制算法，通過調整拓撲機器人的相對位置，使處于冗余位置的拓撲機器人移動來重構網絡拓撲，改善網絡連通性。中繼部署算法的拓撲機器人與地面節點是異構的關系，拓撲機器人對拓撲的監視，是對地面分布式節點的相對位置的一種集中管理，可以對網絡連通關鍵點進行重要性量化，以有效優化網絡拓撲。

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

2 節點重要度計算

2.1 理論基礎

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

2.1.1 定義1 鄰接矩陣

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

2.1.2 定義2 節點鄰域

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

2.1.3 定義3 節點度值

節點的度值digi與節點重要度的關系很大，當前節點對相鄰節點的影響力可以通過節點度值來反映，節點度值是指與當前節點直接互聯的節點數目。節點度值越大，該節點對其相鄰節點的影響越大。節點領域的節點數量，是節點工作在最大發送功率下的節點度值。

2.1.4 定義4 割點及連通度

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

2.1.5 定義5 節點重要度貢獻矩陣

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

HIC=

(1)

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

(2)

2.1.6 定義6 節點效率

2.1.7 定義7 節點重要度評價矩陣

用度來構建節點之間的重要度關聯，用節點傳輸貢獻率標識節點在網絡信息傳輸中的位置，可以得到重要度評價矩陣HE為

HE=

(3)

2.2 節點重要度評價的算法設計

(4)

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

3 基于拓撲機器人的網絡拓撲重構算法

要進行拓撲重構，拓撲機器人要能夠判斷在當前拓撲中的關鍵節點以及脫網節點。拓撲機器人周期性發送拓撲探測消息，收集網絡拓撲，步驟如下。

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

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

圖2 拓撲重構流程圖

4 實驗分析

從兩個方面分別進行實驗分析，介紹依據節點重要度對拓撲機器人進行位置調整所帶來的網絡抗毀性能的提升的衡量方法，網絡節點故障數與拓撲機器人數量之間的關系的表現形式。

4.1 預防性重構抗毀性分析及節點重要度計算

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

(5)

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

圖3 存在割點和預防性重構后的網絡拓撲

表1 節點重要度計算及排序

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

4.2 重構前后性能比較

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

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

圖4 發包速率和網絡故障數對分組成功投遞率的影響

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

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

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

5 結論

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