基于最小跳數的星座網絡拓撲抗毀性分析

孫景云,張國亭,柳 震,王 進

(1.北京跟蹤與通信技術研究所,北京 100094;2.中國航天科工集團第三研究院,北京 100071)

0 引言

單顆衛星對地球的覆蓋能力有限,但多顆不同軌道的衛星可組成星座,并通過在衛星節點間建立星間鏈路實現互聯互通,為全球范圍內用戶提供全覆蓋、全實時服務。衛星所處空間環境復雜多變,通信鏈路易被干擾,當星座網絡拓撲中的節點和鏈路發生隨機故障或遭受蓄意損毀,會造成節點受損、鏈路中斷,進而影響星座服務效能。上述故障對網絡拓撲結構的變化以及對周圍節點和鏈路的影響,是本文分析研究的重點。

關于網絡拓撲結構抗毀性分析,國內外均有相關研究。文獻[1]給出抗毀性定義和測度,總結了傳統圖論中的網絡抗毀性指標,如網絡韌性度、完整度、連通度等,但上述指標從全局角度出發,未考慮拓撲內部節點與鏈路直接的關聯。文獻[2]對比非全連通網絡與全連通網絡拓撲結構差異,提出基于最短路徑數的抗毀性評估算法,以網絡中節點之間的最短路徑數的長度和條數作為核心考察指標,來評估網絡的抗毀性能。網絡抗毀性本質在于節點間存在可替代途徑,文獻[3-4]以網絡自然連通度為測度,將復雜網絡特征譜與抗毀性建立聯系,度量網絡抗毀性能。文獻[5]提出跳面節點法,根據某一節點到達其他節點的跳數劃分跳面,將網絡可靠性、抗毀性評估轉化為跳面節點可靠性及跳面間關聯性進行求解,并給出定量計算的數學解析式。文獻[6]將跳面節點法應用到衛星網絡中,根據衛星網絡高動態、周期性的特點,對跳面節點法進行了改進,提高了對相似拓撲結構的區分度。這些網絡拓撲抗毀性模型各有其側重點,也各有局限性。文獻[7]提出區域級網絡拓撲抗毀性評估算法,衡量不同區域受到攻擊的程度。文獻[8]定義了復雜網絡冗余度并對網絡抗毀性進行量化,通過刪除節點評估節點對網絡的重要程度。

文獻[9]從網絡面臨的威脅類型出發,可以分為隨機失效和蓄意損毀兩種失效類型。文獻[10]提出無標度網絡可以有效應對隨機失效帶來的影響,而對于蓄意損毀卻十分脆弱。因此,研究星座網絡拓撲抗毀性,也可以從節點重要性角度來進一步研究[11]。評估節點重要性比較常用的方法有[12]:度中心性,以節點的連接數作為測度指標;接近中心性,以節點靠近網絡中心的程度判斷節點重要性;介數中心性,以節點/鏈路作為其中兩個節點之間最短路徑的橋梁的次數作為刻畫節點重要性的指標。

本文以局部網絡為分析對象,重點研究網絡拓撲中某些節點受損或鏈路中斷對其他節點及網絡的影響。對于Walker星座,其網絡拓撲對稱,度中心性和接近中心性不適用于節點重要性評價指標,介數中心性可以直觀描述節點/鏈路對最短路徑數的影響?？紤]到衛星發射與維護的高額成本,進行網絡拓撲結構抗毀性的分析評估對星座規劃設計、運維管控、健康管理均具有重要意義。

1 星座網絡拓撲建模

每個衛星設計4條星間鏈路,包括前后兩條同軌衛星鏈路和左右兩條異軌衛星鏈路?？紤]Walker星座,網絡拓撲用G表示。星座網絡拓撲示意圖如圖1所示。

(a) 衛星節點建鏈關系 (b) 星座網絡拓撲圖1 星座網絡拓撲示意圖Fig.1 Constellation network topology diagram

定義1鄰接矩陣

以星座中衛星節點作為網絡拓撲G中的點,以星間鏈路作為網絡拓撲G中的邊,則與網絡拓撲G相對應的鄰接矩陣A可以表示為:

(1)

式中:Vi(i=1,2,…,N)表示星座中的衛星節點,N為星座中衛星數目,aij表示衛星Vi與Vj之間鏈路連接情況(i,j=1,2,…,N),aij=1表示鏈路連通,aij=0則表示鏈路中斷。鄰接矩陣A為對稱矩陣,由于衛星自身與自身之間不存在星間鏈路,因此鄰接矩陣A的對角元素均為0。

鄰接矩陣具有以下性質,可用于判斷網絡拓撲的連通性和穩健性[13-14]:

性質1設A是N階圖G的鄰接矩陣,N≥3,令R=A+A2+…+AN-1,則圖G連通的充分必要條件是矩陣R中每個元素均不為零。

2 最小跳數路由算法

每條路徑的權值為1時,最短路徑算法等效于最小跳數算法。衛星網絡拓撲結構呈二維網格狀,在異軌和同軌星間鏈路傳播時延相差不大的情況下,可將跳數作為最優路徑的主要衡量指標[15]。

從源節點到目的節點,跳數最小時,所有可能經過的節點和鏈路的集合,定義為最小跳數路由區域。如圖2(a),當源節點與目的節點處于同一條軌道面或異軌同一位置時,最小跳數路由區域為一條線;如圖2(b),當源節點與目的節點不處于同一條軌道且不同位置時,最小跳數路由區域為一個矩形區域[16]。

(a) 線形區域

最小跳數可以由最小跳數路由區域中長與寬的和來表示:

K=PD+QD,

(2)

式中:PD(PD≥0)為軌道面距離,QD(QD≥0)為軌道內位置距離。

3 節點/鏈路重要性分析

定義2節點/鏈路介數

介數定義為網絡中經過某個節點的/鏈路的最小跳路徑數目與網絡中最小跳路徑總數的比值。節點介數和鏈路的介數定義分別為[17]:

(3)

式中:σst表示從源節點Vs到目的節點Vt的最小跳路徑總數量,σst(Vi)表示從節點Vs～Vt且經過節點Vi的最小跳路徑數量,σst(Eij)表示從節點Vs～Vt且經過鏈路Eij的最小跳路徑數量。采用鄰接矩陣對節點/鏈路介數進行計算,得到:

(4)

式中:Kst表示從源節點Vs到目的節點Vt的最小跳數,同理,Ksi表示從節點Vs～Vi的最小跳數,Kit表示從節點Vi～Vt的最小跳數,Kjt表示從節點Vj～Vt的最小跳數。得到:

Kst=Ksi+Kit=Ksi+Kjt+1。

(5)

在最小跳數路由區域中,根據信息流向將流入節點的鏈路數目定義為入度,將流出節點的鏈路數目定義為出度,節點(非源節點或目的節點)介數為流入節點的鏈路介數之和,同時等于流出節點鏈路介數之和。源節點和目的節點的介數為1。得到如下公式:

(6)

圖3為一個3×2(軌道面距離為3,軌道內位置距離為2)的最小跳數路由區域,Vs為源節點,Vt為目的節點,根據介數定義,得到各節點/鏈路介數。圖中,圓圈內數值表示各節點介數,鏈路旁數值表示各鏈路介數。考慮某節點受損或鏈路中斷對周圍節點和鏈路的影響。

圖3 節點/鏈路介數示意圖Fig.3 Node/Link intermediate diagram

推論1若某個節點受損,則與其相連的鏈路介數為0。

證明:若某個節點損壞,則此節點的介數為0,即WV=0。由式(6)得到:

(7)

推論2若某節點(非源節點或目的節點)流出節點的鏈路介數和為0,則此節點與流入此節點的鏈路介數均為0。

(8)

因此,得到此節點介數為0,且流入節點的鏈路介數均為0。

4 仿真及結果分析

衛星網絡拓撲類似于網格結構,其動態特性主要來自如下幾方面:① 衛星節點受損或鏈路受干擾中斷導致星座網絡拓撲的改變;② 同軌星間鏈路比較穩定,而異軌星間鏈路在靠近極區時因距離、指向角度變化劇烈而中斷,又在飛出極區后重新建鏈;③ 網絡中某些節點或鏈路擁塞導致衛星網絡不可用。以上均可歸結為節點受損和鏈路中斷兩種情況。

4.1 節點受損或鏈路中斷對周圍節點/鏈路的影響

當有節點受損或鏈路中斷時,可根據推論1、推論2正向/反向更新各節點/鏈路介數。

節點損毀時介數變化示意如圖4所示。圖中,節點VA受損,根據推論1得到與之相連的鏈路介數均為0,得到圖4(a)介數更新值。流出節點VB的鏈路介數值為0,根據推論2得到節點VB以及流入VB的鏈路介數值均為0,同理,可推導出節點VC以及流入VC的鏈路介數值均為0,介數值更新如圖4(b)所示。更新鄰接矩陣,根據鄰接矩陣性質,得到圖4(c)節點和鏈路的介數值。

(c) 更新路由區域介數值圖4 節點損毀時介數變化示意圖Fig.4 Intermediate value changing with some nodes damaged

單個節點受損或鏈路中斷,導致周圍節點/鏈路介數值增大;當節點/鏈路介數值增大到1時,表示所有最小跳路徑都要經過此節點/鏈路,因此,若此節點/鏈路損毀將導致在當前區域內最小跳路徑數為0。

4.2 節點受損或鏈路中斷對網絡的影響

考慮隨機受損和蓄意損毀兩種情況下節點受損或鏈路中斷對網絡的影響。其中,隨機受損情況下,隨機選取網絡中節點或鏈路,設置其狀態值;蓄意損毀情況下,根據網絡中節點或鏈路重要程度進行排序[18],優先使重要度高的節點受損或鏈路中斷。以圖5網絡為例,分析不同情況下節點受損或鏈路中斷對網絡的影響。如圖5所示路由區域,共有11個軌道面,每個軌道面由6顆衛星組成,衛星編號如圖所示,節點1為源節點,節點66為目的節點。根據式(3)計算各個衛星節點介數值,節點2與節點65介數值最大為0.67。

圖5 11×6最小跳路由區域示意圖Fig.5 11×6 minimum hop routing area

選取不同節點受損,分析對其他節點的影響。如圖6所示。節點2(介數值0.67)受損對周圍節點介數值影響較大,節點2～11介數值變為0,節點12介數值變為1;節點20(介數值0.045)受損對周圍節點影響不大,節點19介數值變化最大,由0.093 1變化為0.055 8。

圖6 節點受損對其他節點介數值影響Fig.6 Influence of node damage on the intermediate value of other nodes

圖7為兩種仿真模式下受損衛星數與最小跳路徑數變化曲線。蓄意損毀模式下,最少兩個衛星節點受損,即導致在當前路由區域中最小跳路徑數為0;隨機受損模式下,19個衛星節點受損,才使得最小跳路徑數為0。

圖7 受損衛星數與最小跳路徑數變化曲線Fig.7 Number of damaged satellites vs the number of minimum hop paths

圖8為兩種仿真模式下中斷鏈路數與最小跳路徑數變化曲線。蓄意損毀模式下,只需要選擇兩條鏈路中斷,即導致在當前路由區域中最小跳路徑數為0;隨機受損模式下,則需要多條鏈路中斷,才能使得最小跳路徑數為0。

圖8 中斷鏈路數與最小跳路徑數變化曲線Fig.8 Number of intermediate links vs the number of minimum hop paths

5 結論

本文針對星座網絡拓撲呈二維網格特點,基于最小跳數路由算法對星座網絡拓撲抗毀性進行了分析。通過鄰接矩陣性質計算最小跳路由區域中節點和鏈路的介數值;通過介數值參數模型給出星座中節點/鏈路的重要性,并對比分析隨機受損和蓄意損毀模式下,部分節點/鏈路損毀對周圍節點的影響。從仿真結果可知,當介數值最大的節點或鏈路受到蓄意損毀時,網絡中源節點到目的節點最小跳路徑數會發生急劇變化,這一結果對星座健康管理與運維管控具有實際意義。