基于最小跳數(shù)的星座網(wǎng)絡(luò)拓?fù)淇箽苑治?/h1>
2023-10-11 03:50:14孫景云張國亭
無線電通信技術(shù) 2023年5期
孫景云,張國亭,柳 震,王 進(jìn)
(1.北京跟蹤與通信技術(shù)研究所,北京 100094;2.中國航天科工集團(tuán)第三研究院,北京 100071)
0 引言
單顆衛(wèi)星對地球的覆蓋能力有限,但多顆不同軌道的衛(wèi)星可組成星座,并通過在衛(wèi)星節(jié)點(diǎn)間建立星間鏈路實(shí)現(xiàn)互聯(lián)互通,為全球范圍內(nèi)用戶提供全覆蓋、全實(shí)時服務(wù)。衛(wèi)星所處空間環(huán)境復(fù)雜多變,通信鏈路易被干擾,當(dāng)星座網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)和鏈路發(fā)生隨機(jī)故障或遭受蓄意損毀,會造成節(jié)點(diǎn)受損、鏈路中斷,進(jìn)而影響星座服務(wù)效能。上述故障對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化以及對周圍節(jié)點(diǎn)和鏈路的影響,是本文分析研究的重點(diǎn)。
關(guān)于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性分析,國內(nèi)外均有相關(guān)研究。文獻(xiàn)[1]給出抗毀性定義和測度,總結(jié)了傳統(tǒng)圖論中的網(wǎng)絡(luò)抗毀性指標(biāo),如網(wǎng)絡(luò)韌性度、完整度、連通度等,但上述指標(biāo)從全局角度出發(fā),未考慮拓?fù)鋬?nèi)部節(jié)點(diǎn)與鏈路直接的關(guān)聯(lián)。文獻(xiàn)[2]對比非全連通網(wǎng)絡(luò)與全連通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)差異,提出基于最短路徑數(shù)的抗毀性評估算法,以網(wǎng)絡(luò)中節(jié)點(diǎn)之間的最短路徑數(shù)的長度和條數(shù)作為核心考察指標(biāo),來評估網(wǎng)絡(luò)的抗毀性能。網(wǎng)絡(luò)抗毀性本質(zhì)在于節(jié)點(diǎn)間存在可替代途徑,文獻(xiàn)[3-4]以網(wǎng)絡(luò)自然連通度為測度,將復(fù)雜網(wǎng)絡(luò)特征譜與抗毀性建立聯(lián)系,度量網(wǎng)絡(luò)抗毀性能。文獻(xiàn)[5]提出跳面節(jié)點(diǎn)法,根據(jù)某一節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的跳數(shù)劃分跳面,將網(wǎng)絡(luò)可靠性、抗毀性評估轉(zhuǎn)化為跳面節(jié)點(diǎn)可靠性及跳面間關(guān)聯(lián)性進(jìn)行求解,并給出定量計算的數(shù)學(xué)解析式。文獻(xiàn)[6]將跳面節(jié)點(diǎn)法應(yīng)用到衛(wèi)星網(wǎng)絡(luò)中,根據(jù)衛(wèi)星網(wǎng)絡(luò)高動態(tài)、周期性的特點(diǎn),對跳面節(jié)點(diǎn)法進(jìn)行了改進(jìn),提高了對相似拓?fù)浣Y(jié)構(gòu)的區(qū)分度。這些網(wǎng)絡(luò)拓?fù)淇箽阅Ｐ透饔衅鋫?cè)重點(diǎn),也各有局限性。文獻(xiàn)[7]提出區(qū)域級網(wǎng)絡(luò)拓?fù)淇箽栽u估算法,衡量不同區(qū)域受到攻擊的程度。文獻(xiàn)[8]定義了復(fù)雜網(wǎng)絡(luò)冗余度并對網(wǎng)絡(luò)抗毀性進(jìn)行量化,通過刪除節(jié)點(diǎn)評估節(jié)點(diǎn)對網(wǎng)絡(luò)的重要程度。
文獻(xiàn)[9]從網(wǎng)絡(luò)面臨的威脅類型出發(fā),可以分為隨機(jī)失效和蓄意損毀兩種失效類型。文獻(xiàn)[10]提出無標(biāo)度網(wǎng)絡(luò)可以有效應(yīng)對隨機(jī)失效帶來的影響,而對于蓄意損毀卻十分脆弱。因此,研究星座網(wǎng)絡(luò)拓?fù)淇箽?也可以從節(jié)點(diǎn)重要性角度來進(jìn)一步研究[11]。評估節(jié)點(diǎn)重要性比較常用的方法有[12]:度中心性,以節(jié)點(diǎn)的連接數(shù)作為測度指標(biāo);接近中心性,以節(jié)點(diǎn)靠近網(wǎng)絡(luò)中心的程度判斷節(jié)點(diǎn)重要性;介數(shù)中心性,以節(jié)點(diǎn)/鏈路作為其中兩個節(jié)點(diǎn)之間最短路徑的橋梁的次數(shù)作為刻畫節(jié)點(diǎn)重要性的指標(biāo)。
本文以局部網(wǎng)絡(luò)為分析對象,重點(diǎn)研究網(wǎng)絡(luò)拓?fù)渲心承┕?jié)點(diǎn)受損或鏈路中斷對其他節(jié)點(diǎn)及網(wǎng)絡(luò)的影響。對于Walker星座,其網(wǎng)絡(luò)拓?fù)鋵ΨQ,度中心性和接近中心性不適用于節(jié)點(diǎn)重要性評價指標(biāo),介數(shù)中心性可以直觀描述節(jié)點(diǎn)/鏈路對最短路徑數(shù)的影響?？紤]到衛(wèi)星發(fā)射與維護(hù)的高額成本,進(jìn)行網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性的分析評估對星座規(guī)劃設(shè)計、運(yùn)維管控、健康管理均具有重要意義。
1 星座網(wǎng)絡(luò)拓?fù)浣?/h2>
每個衛(wèi)星設(shè)計4條星間鏈路,包括前后兩條同軌衛(wèi)星鏈路和左右兩條異軌衛(wèi)星鏈路。考慮Walker星座,網(wǎng)絡(luò)拓?fù)溆肎表示。星座網(wǎng)絡(luò)拓?fù)涫疽鈭D如圖1所示。
(a) 衛(wèi)星節(jié)點(diǎn)建鏈關(guān)系 (b) 星座網(wǎng)絡(luò)拓?fù)鋱D1 星座網(wǎng)絡(luò)拓?fù)涫疽鈭DFig.1 Constellation network topology diagram
定義1鄰接矩陣
以星座中衛(wèi)星節(jié)點(diǎn)作為網(wǎng)絡(luò)拓?fù)銰中的點(diǎn),以星間鏈路作為網(wǎng)絡(luò)拓?fù)銰中的邊,則與網(wǎng)絡(luò)拓?fù)銰相對應(yīng)的鄰接矩陣A可以表示為:
(1)
式中:Vi(i=1,2,…,N)表示星座中的衛(wèi)星節(jié)點(diǎn),N為星座中衛(wèi)星數(shù)目,aij表示衛(wèi)星Vi與Vj之間鏈路連接情況(i,j=1,2,…,N),aij=1表示鏈路連通,aij=0則表示鏈路中斷。鄰接矩陣A為對稱矩陣,由于衛(wèi)星自身與自身之間不存在星間鏈路,因此鄰接矩陣A的對角元素均為0。
鄰接矩陣具有以下性質(zhì),可用于判斷網(wǎng)絡(luò)拓?fù)涞倪B通性和穩(wěn)健性[13-14]:
性質(zhì)1設(shè)A是N階圖G的鄰接矩陣,N≥3,令R=A+A2+…+AN-1,則圖G連通的充分必要條件是矩陣R中每個元素均不為零。
2 最小跳數(shù)路由算法
每條路徑的權(quán)值為1時,最短路徑算法等效于最小跳數(shù)算法。衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)呈二維網(wǎng)格狀,在異軌和同軌星間鏈路傳播時延相差不大的情況下,可將跳數(shù)作為最優(yōu)路徑的主要衡量指標(biāo)[15]。
從源節(jié)點(diǎn)到目的節(jié)點(diǎn),跳數(shù)最小時,所有可能經(jīng)過的節(jié)點(diǎn)和鏈路的集合,定義為最小跳數(shù)路由區(qū)域。如圖2(a),當(dāng)源節(jié)點(diǎn)與目的節(jié)點(diǎn)處于同一條軌道面或異軌同一位置時,最小跳數(shù)路由區(qū)域?yàn)橐粭l線;如圖2(b),當(dāng)源節(jié)點(diǎn)與目的節(jié)點(diǎn)不處于同一條軌道且不同位置時,最小跳數(shù)路由區(qū)域?yàn)橐粋€矩形區(qū)域[16]。
(a) 線形區(qū)域
最小跳數(shù)可以由最小跳數(shù)路由區(qū)域中長與寬的和來表示:
K=PD+QD,
(2)
式中:PD(PD≥0)為軌道面距離,QD(QD≥0)為軌道內(nèi)位置距離。
3 節(jié)點(diǎn)/鏈路重要性分析
定義2節(jié)點(diǎn)/鏈路介數(shù)
介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過某個節(jié)點(diǎn)的/鏈路的最小跳路徑數(shù)目與網(wǎng)絡(luò)中最小跳路徑總數(shù)的比值。節(jié)點(diǎn)介數(shù)和鏈路的介數(shù)定義分別為[17]:
(3)
式中:σst表示從源節(jié)點(diǎn)Vs到目的節(jié)點(diǎn)Vt的最小跳路徑總數(shù)量,σst(Vi)表示從節(jié)點(diǎn)Vs～Vt且經(jīng)過節(jié)點(diǎn)Vi的最小跳路徑數(shù)量,σst(Eij)表示從節(jié)點(diǎn)Vs～Vt且經(jīng)過鏈路Eij的最小跳路徑數(shù)量。采用鄰接矩陣對節(jié)點(diǎn)/鏈路介數(shù)進(jìn)行計算,得到:
(4)
式中:Kst表示從源節(jié)點(diǎn)Vs到目的節(jié)點(diǎn)Vt的最小跳數(shù),同理,Ksi表示從節(jié)點(diǎn)Vs～Vi的最小跳數(shù),Kit表示從節(jié)點(diǎn)Vi～Vt的最小跳數(shù),Kjt表示從節(jié)點(diǎn)Vj～Vt的最小跳數(shù)。得到:
Kst=Ksi+Kit=Ksi+Kjt+1。
(5)
在最小跳數(shù)路由區(qū)域中,根據(jù)信息流向?qū)⒘魅牍?jié)點(diǎn)的鏈路數(shù)目定義為入度,將流出節(jié)點(diǎn)的鏈路數(shù)目定義為出度,節(jié)點(diǎn)(非源節(jié)點(diǎn)或目的節(jié)點(diǎn))介數(shù)為流入節(jié)點(diǎn)的鏈路介數(shù)之和,同時等于流出節(jié)點(diǎn)鏈路介數(shù)之和。源節(jié)點(diǎn)和目的節(jié)點(diǎn)的介數(shù)為1。得到如下公式:
(6)
圖3為一個3×2(軌道面距離為3,軌道內(nèi)位置距離為2)的最小跳數(shù)路由區(qū)域,Vs為源節(jié)點(diǎn),Vt為目的節(jié)點(diǎn),根據(jù)介數(shù)定義,得到各節(jié)點(diǎn)/鏈路介數(shù)。圖中,圓圈內(nèi)數(shù)值表示各節(jié)點(diǎn)介數(shù),鏈路旁數(shù)值表示各鏈路介數(shù)。考慮某節(jié)點(diǎn)受損或鏈路中斷對周圍節(jié)點(diǎn)和鏈路的影響。
圖3 節(jié)點(diǎn)/鏈路介數(shù)示意圖Fig.3 Node/Link intermediate diagram
推論1若某個節(jié)點(diǎn)受損,則與其相連的鏈路介數(shù)為0。
證明:若某個節(jié)點(diǎn)損壞,則此節(jié)點(diǎn)的介數(shù)為0,即WV=0。由式(6)得到:
(7)
推論2若某節(jié)點(diǎn)(非源節(jié)點(diǎn)或目的節(jié)點(diǎn))流出節(jié)點(diǎn)的鏈路介數(shù)和為0,則此節(jié)點(diǎn)與流入此節(jié)點(diǎn)的鏈路介數(shù)均為0。
(8)
因此,得到此節(jié)點(diǎn)介數(shù)為0,且流入節(jié)點(diǎn)的鏈路介數(shù)均為0。
4 仿真及結(jié)果分析
衛(wèi)星網(wǎng)絡(luò)拓?fù)漕愃朴诰W(wǎng)格結(jié)構(gòu),其動態(tài)特性主要來自如下幾方面:① 衛(wèi)星節(jié)點(diǎn)受損或鏈路受干擾中斷導(dǎo)致星座網(wǎng)絡(luò)拓?fù)涞母淖?② 同軌星間鏈路比較穩(wěn)定,而異軌星間鏈路在靠近極區(qū)時因距離、指向角度變化劇烈而中斷,又在飛出極區(qū)后重新建鏈;③ 網(wǎng)絡(luò)中某些節(jié)點(diǎn)或鏈路擁塞導(dǎo)致衛(wèi)星網(wǎng)絡(luò)不可用。以上均可歸結(jié)為節(jié)點(diǎn)受損和鏈路中斷兩種情況。
4.1 節(jié)點(diǎn)受損或鏈路中斷對周圍節(jié)點(diǎn)/鏈路的影響
當(dāng)有節(jié)點(diǎn)受損或鏈路中斷時,可根據(jù)推論1、推論2正向/反向更新各節(jié)點(diǎn)/鏈路介數(shù)。
節(jié)點(diǎn)損毀時介數(shù)變化示意如圖4所示。圖中,節(jié)點(diǎn)VA受損,根據(jù)推論1得到與之相連的鏈路介數(shù)均為0,得到圖4(a)介數(shù)更新值。流出節(jié)點(diǎn)VB的鏈路介數(shù)值為0,根據(jù)推論2得到節(jié)點(diǎn)VB以及流入VB的鏈路介數(shù)值均為0,同理,可推導(dǎo)出節(jié)點(diǎn)VC以及流入VC的鏈路介數(shù)值均為0,介數(shù)值更新如圖4(b)所示。更新鄰接矩陣,根據(jù)鄰接矩陣性質(zhì),得到圖4(c)節(jié)點(diǎn)和鏈路的介數(shù)值。
(c) 更新路由區(qū)域介數(shù)值圖4 節(jié)點(diǎn)損毀時介數(shù)變化示意圖Fig.4 Intermediate value changing with some nodes damaged
單個節(jié)點(diǎn)受損或鏈路中斷,導(dǎo)致周圍節(jié)點(diǎn)/鏈路介數(shù)值增大;當(dāng)節(jié)點(diǎn)/鏈路介數(shù)值增大到1時,表示所有最小跳路徑都要經(jīng)過此節(jié)點(diǎn)/鏈路,因此,若此節(jié)點(diǎn)/鏈路損毀將導(dǎo)致在當(dāng)前區(qū)域內(nèi)最小跳路徑數(shù)為0。
4.2 節(jié)點(diǎn)受損或鏈路中斷對網(wǎng)絡(luò)的影響
考慮隨機(jī)受損和蓄意損毀兩種情況下節(jié)點(diǎn)受損或鏈路中斷對網(wǎng)絡(luò)的影響。其中,隨機(jī)受損情況下,隨機(jī)選取網(wǎng)絡(luò)中節(jié)點(diǎn)或鏈路,設(shè)置其狀態(tài)值;蓄意損毀情況下,根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)或鏈路重要程度進(jìn)行排序[18],優(yōu)先使重要度高的節(jié)點(diǎn)受損或鏈路中斷。以圖5網(wǎng)絡(luò)為例,分析不同情況下節(jié)點(diǎn)受損或鏈路中斷對網(wǎng)絡(luò)的影響。如圖5所示路由區(qū)域,共有11個軌道面,每個軌道面由6顆衛(wèi)星組成,衛(wèi)星編號如圖所示,節(jié)點(diǎn)1為源節(jié)點(diǎn),節(jié)點(diǎn)66為目的節(jié)點(diǎn)。根據(jù)式(3)計算各個衛(wèi)星節(jié)點(diǎn)介數(shù)值,節(jié)點(diǎn)2與節(jié)點(diǎn)65介數(shù)值最大為0.67。
圖5 11×6最小跳路由區(qū)域示意圖Fig.5 11×6 minimum hop routing area
選取不同節(jié)點(diǎn)受損,分析對其他節(jié)點(diǎn)的影響。如圖6所示。節(jié)點(diǎn)2(介數(shù)值0.67)受損對周圍節(jié)點(diǎn)介數(shù)值影響較大,節(jié)點(diǎn)2～11介數(shù)值變?yōu)?,節(jié)點(diǎn)12介數(shù)值變?yōu)?;節(jié)點(diǎn)20(介數(shù)值0.045)受損對周圍節(jié)點(diǎn)影響不大,節(jié)點(diǎn)19介數(shù)值變化最大,由0.093 1變化為0.055 8。
圖6 節(jié)點(diǎn)受損對其他節(jié)點(diǎn)介數(shù)值影響Fig.6 Influence of node damage on the intermediate value of other nodes
圖7為兩種仿真模式下受損衛(wèi)星數(shù)與最小跳路徑數(shù)變化曲線。蓄意損毀模式下,最少兩個衛(wèi)星節(jié)點(diǎn)受損,即導(dǎo)致在當(dāng)前路由區(qū)域中最小跳路徑數(shù)為0;隨機(jī)受損模式下,19個衛(wèi)星節(jié)點(diǎn)受損,才使得最小跳路徑數(shù)為0。
圖7 受損衛(wèi)星數(shù)與最小跳路徑數(shù)變化曲線Fig.7 Number of damaged satellites vs the number of minimum hop paths
圖8為兩種仿真模式下中斷鏈路數(shù)與最小跳路徑數(shù)變化曲線。蓄意損毀模式下,只需要選擇兩條鏈路中斷,即導(dǎo)致在當(dāng)前路由區(qū)域中最小跳路徑數(shù)為0;隨機(jī)受損模式下,則需要多條鏈路中斷,才能使得最小跳路徑數(shù)為0。
圖8 中斷鏈路數(shù)與最小跳路徑數(shù)變化曲線Fig.8 Number of intermediate links vs the number of minimum hop paths
5 結(jié)論
本文針對星座網(wǎng)絡(luò)拓?fù)涑识S網(wǎng)格特點(diǎn),基于最小跳數(shù)路由算法對星座網(wǎng)絡(luò)拓?fù)淇箽赃M(jìn)行了分析。通過鄰接矩陣性質(zhì)計算最小跳路由區(qū)域中節(jié)點(diǎn)和鏈路的介數(shù)值;通過介數(shù)值參數(shù)模型給出星座中節(jié)點(diǎn)/鏈路的重要性,并對比分析隨機(jī)受損和蓄意損毀模式下,部分節(jié)點(diǎn)/鏈路損毀對周圍節(jié)點(diǎn)的影響。從仿真結(jié)果可知,當(dāng)介數(shù)值最大的節(jié)點(diǎn)或鏈路受到蓄意損毀時,網(wǎng)絡(luò)中源節(jié)點(diǎn)到目的節(jié)點(diǎn)最小跳路徑數(shù)會發(fā)生急劇變化,這一結(jié)果對星座健康管理與運(yùn)維管控具有實(shí)際意義。
孫景云,張國亭,柳 震,王 進(jìn)
(1.北京跟蹤與通信技術(shù)研究所,北京 100094;2.中國航天科工集團(tuán)第三研究院,北京 100071)
0 引言
單顆衛(wèi)星對地球的覆蓋能力有限,但多顆不同軌道的衛(wèi)星可組成星座,并通過在衛(wèi)星節(jié)點(diǎn)間建立星間鏈路實(shí)現(xiàn)互聯(lián)互通,為全球范圍內(nèi)用戶提供全覆蓋、全實(shí)時服務(wù)。衛(wèi)星所處空間環(huán)境復(fù)雜多變,通信鏈路易被干擾,當(dāng)星座網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)和鏈路發(fā)生隨機(jī)故障或遭受蓄意損毀,會造成節(jié)點(diǎn)受損、鏈路中斷,進(jìn)而影響星座服務(wù)效能。上述故障對網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化以及對周圍節(jié)點(diǎn)和鏈路的影響,是本文分析研究的重點(diǎn)。
關(guān)于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性分析,國內(nèi)外均有相關(guān)研究。文獻(xiàn)[1]給出抗毀性定義和測度,總結(jié)了傳統(tǒng)圖論中的網(wǎng)絡(luò)抗毀性指標(biāo),如網(wǎng)絡(luò)韌性度、完整度、連通度等,但上述指標(biāo)從全局角度出發(fā),未考慮拓?fù)鋬?nèi)部節(jié)點(diǎn)與鏈路直接的關(guān)聯(lián)。文獻(xiàn)[2]對比非全連通網(wǎng)絡(luò)與全連通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)差異,提出基于最短路徑數(shù)的抗毀性評估算法,以網(wǎng)絡(luò)中節(jié)點(diǎn)之間的最短路徑數(shù)的長度和條數(shù)作為核心考察指標(biāo),來評估網(wǎng)絡(luò)的抗毀性能。網(wǎng)絡(luò)抗毀性本質(zhì)在于節(jié)點(diǎn)間存在可替代途徑,文獻(xiàn)[3-4]以網(wǎng)絡(luò)自然連通度為測度,將復(fù)雜網(wǎng)絡(luò)特征譜與抗毀性建立聯(lián)系,度量網(wǎng)絡(luò)抗毀性能。文獻(xiàn)[5]提出跳面節(jié)點(diǎn)法,根據(jù)某一節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的跳數(shù)劃分跳面,將網(wǎng)絡(luò)可靠性、抗毀性評估轉(zhuǎn)化為跳面節(jié)點(diǎn)可靠性及跳面間關(guān)聯(lián)性進(jìn)行求解,并給出定量計算的數(shù)學(xué)解析式。文獻(xiàn)[6]將跳面節(jié)點(diǎn)法應(yīng)用到衛(wèi)星網(wǎng)絡(luò)中,根據(jù)衛(wèi)星網(wǎng)絡(luò)高動態(tài)、周期性的特點(diǎn),對跳面節(jié)點(diǎn)法進(jìn)行了改進(jìn),提高了對相似拓?fù)浣Y(jié)構(gòu)的區(qū)分度。這些網(wǎng)絡(luò)拓?fù)淇箽阅Ｐ透饔衅鋫?cè)重點(diǎn),也各有局限性。文獻(xiàn)[7]提出區(qū)域級網(wǎng)絡(luò)拓?fù)淇箽栽u估算法,衡量不同區(qū)域受到攻擊的程度。文獻(xiàn)[8]定義了復(fù)雜網(wǎng)絡(luò)冗余度并對網(wǎng)絡(luò)抗毀性進(jìn)行量化,通過刪除節(jié)點(diǎn)評估節(jié)點(diǎn)對網(wǎng)絡(luò)的重要程度。
文獻(xiàn)[9]從網(wǎng)絡(luò)面臨的威脅類型出發(fā),可以分為隨機(jī)失效和蓄意損毀兩種失效類型。文獻(xiàn)[10]提出無標(biāo)度網(wǎng)絡(luò)可以有效應(yīng)對隨機(jī)失效帶來的影響,而對于蓄意損毀卻十分脆弱。因此,研究星座網(wǎng)絡(luò)拓?fù)淇箽?也可以從節(jié)點(diǎn)重要性角度來進(jìn)一步研究[11]。評估節(jié)點(diǎn)重要性比較常用的方法有[12]:度中心性,以節(jié)點(diǎn)的連接數(shù)作為測度指標(biāo);接近中心性,以節(jié)點(diǎn)靠近網(wǎng)絡(luò)中心的程度判斷節(jié)點(diǎn)重要性;介數(shù)中心性,以節(jié)點(diǎn)/鏈路作為其中兩個節(jié)點(diǎn)之間最短路徑的橋梁的次數(shù)作為刻畫節(jié)點(diǎn)重要性的指標(biāo)。
本文以局部網(wǎng)絡(luò)為分析對象,重點(diǎn)研究網(wǎng)絡(luò)拓?fù)渲心承┕?jié)點(diǎn)受損或鏈路中斷對其他節(jié)點(diǎn)及網(wǎng)絡(luò)的影響。對于Walker星座,其網(wǎng)絡(luò)拓?fù)鋵ΨQ,度中心性和接近中心性不適用于節(jié)點(diǎn)重要性評價指標(biāo),介數(shù)中心性可以直觀描述節(jié)點(diǎn)/鏈路對最短路徑數(shù)的影響?？紤]到衛(wèi)星發(fā)射與維護(hù)的高額成本,進(jìn)行網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性的分析評估對星座規(guī)劃設(shè)計、運(yùn)維管控、健康管理均具有重要意義。
1 星座網(wǎng)絡(luò)拓?fù)浣?/h2>
每個衛(wèi)星設(shè)計4條星間鏈路,包括前后兩條同軌衛(wèi)星鏈路和左右兩條異軌衛(wèi)星鏈路。考慮Walker星座,網(wǎng)絡(luò)拓?fù)溆肎表示。星座網(wǎng)絡(luò)拓?fù)涫疽鈭D如圖1所示。
(a) 衛(wèi)星節(jié)點(diǎn)建鏈關(guān)系 (b) 星座網(wǎng)絡(luò)拓?fù)鋱D1 星座網(wǎng)絡(luò)拓?fù)涫疽鈭DFig.1 Constellation network topology diagram
定義1鄰接矩陣
以星座中衛(wèi)星節(jié)點(diǎn)作為網(wǎng)絡(luò)拓?fù)銰中的點(diǎn),以星間鏈路作為網(wǎng)絡(luò)拓?fù)銰中的邊,則與網(wǎng)絡(luò)拓?fù)銰相對應(yīng)的鄰接矩陣A可以表示為:
(1)
式中:Vi(i=1,2,…,N)表示星座中的衛(wèi)星節(jié)點(diǎn),N為星座中衛(wèi)星數(shù)目,aij表示衛(wèi)星Vi與Vj之間鏈路連接情況(i,j=1,2,…,N),aij=1表示鏈路連通,aij=0則表示鏈路中斷。鄰接矩陣A為對稱矩陣,由于衛(wèi)星自身與自身之間不存在星間鏈路,因此鄰接矩陣A的對角元素均為0。
鄰接矩陣具有以下性質(zhì),可用于判斷網(wǎng)絡(luò)拓?fù)涞倪B通性和穩(wěn)健性[13-14]:
性質(zhì)1設(shè)A是N階圖G的鄰接矩陣,N≥3,令R=A+A2+…+AN-1,則圖G連通的充分必要條件是矩陣R中每個元素均不為零。
2 最小跳數(shù)路由算法
每條路徑的權(quán)值為1時,最短路徑算法等效于最小跳數(shù)算法。衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)呈二維網(wǎng)格狀,在異軌和同軌星間鏈路傳播時延相差不大的情況下,可將跳數(shù)作為最優(yōu)路徑的主要衡量指標(biāo)[15]。
從源節(jié)點(diǎn)到目的節(jié)點(diǎn),跳數(shù)最小時,所有可能經(jīng)過的節(jié)點(diǎn)和鏈路的集合,定義為最小跳數(shù)路由區(qū)域。如圖2(a),當(dāng)源節(jié)點(diǎn)與目的節(jié)點(diǎn)處于同一條軌道面或異軌同一位置時,最小跳數(shù)路由區(qū)域?yàn)橐粭l線;如圖2(b),當(dāng)源節(jié)點(diǎn)與目的節(jié)點(diǎn)不處于同一條軌道且不同位置時,最小跳數(shù)路由區(qū)域?yàn)橐粋€矩形區(qū)域[16]。
(a) 線形區(qū)域
最小跳數(shù)可以由最小跳數(shù)路由區(qū)域中長與寬的和來表示:
K=PD+QD,
(2)
式中:PD(PD≥0)為軌道面距離,QD(QD≥0)為軌道內(nèi)位置距離。
3 節(jié)點(diǎn)/鏈路重要性分析
定義2節(jié)點(diǎn)/鏈路介數(shù)
介數(shù)定義為網(wǎng)絡(luò)中經(jīng)過某個節(jié)點(diǎn)的/鏈路的最小跳路徑數(shù)目與網(wǎng)絡(luò)中最小跳路徑總數(shù)的比值。節(jié)點(diǎn)介數(shù)和鏈路的介數(shù)定義分別為[17]:
(3)
式中:σst表示從源節(jié)點(diǎn)Vs到目的節(jié)點(diǎn)Vt的最小跳路徑總數(shù)量,σst(Vi)表示從節(jié)點(diǎn)Vs～Vt且經(jīng)過節(jié)點(diǎn)Vi的最小跳路徑數(shù)量,σst(Eij)表示從節(jié)點(diǎn)Vs～Vt且經(jīng)過鏈路Eij的最小跳路徑數(shù)量。采用鄰接矩陣對節(jié)點(diǎn)/鏈路介數(shù)進(jìn)行計算,得到:
(4)
式中:Kst表示從源節(jié)點(diǎn)Vs到目的節(jié)點(diǎn)Vt的最小跳數(shù),同理,Ksi表示從節(jié)點(diǎn)Vs～Vi的最小跳數(shù),Kit表示從節(jié)點(diǎn)Vi～Vt的最小跳數(shù),Kjt表示從節(jié)點(diǎn)Vj～Vt的最小跳數(shù)。得到:
Kst=Ksi+Kit=Ksi+Kjt+1。
(5)
在最小跳數(shù)路由區(qū)域中,根據(jù)信息流向?qū)⒘魅牍?jié)點(diǎn)的鏈路數(shù)目定義為入度,將流出節(jié)點(diǎn)的鏈路數(shù)目定義為出度,節(jié)點(diǎn)(非源節(jié)點(diǎn)或目的節(jié)點(diǎn))介數(shù)為流入節(jié)點(diǎn)的鏈路介數(shù)之和,同時等于流出節(jié)點(diǎn)鏈路介數(shù)之和。源節(jié)點(diǎn)和目的節(jié)點(diǎn)的介數(shù)為1。得到如下公式:
(6)
圖3為一個3×2(軌道面距離為3,軌道內(nèi)位置距離為2)的最小跳數(shù)路由區(qū)域,Vs為源節(jié)點(diǎn),Vt為目的節(jié)點(diǎn),根據(jù)介數(shù)定義,得到各節(jié)點(diǎn)/鏈路介數(shù)。圖中,圓圈內(nèi)數(shù)值表示各節(jié)點(diǎn)介數(shù),鏈路旁數(shù)值表示各鏈路介數(shù)。考慮某節(jié)點(diǎn)受損或鏈路中斷對周圍節(jié)點(diǎn)和鏈路的影響。
圖3 節(jié)點(diǎn)/鏈路介數(shù)示意圖Fig.3 Node/Link intermediate diagram
推論1若某個節(jié)點(diǎn)受損,則與其相連的鏈路介數(shù)為0。
證明:若某個節(jié)點(diǎn)損壞,則此節(jié)點(diǎn)的介數(shù)為0,即WV=0。由式(6)得到:
(7)
推論2若某節(jié)點(diǎn)(非源節(jié)點(diǎn)或目的節(jié)點(diǎn))流出節(jié)點(diǎn)的鏈路介數(shù)和為0,則此節(jié)點(diǎn)與流入此節(jié)點(diǎn)的鏈路介數(shù)均為0。
(8)
因此,得到此節(jié)點(diǎn)介數(shù)為0,且流入節(jié)點(diǎn)的鏈路介數(shù)均為0。
4 仿真及結(jié)果分析
衛(wèi)星網(wǎng)絡(luò)拓?fù)漕愃朴诰W(wǎng)格結(jié)構(gòu),其動態(tài)特性主要來自如下幾方面:① 衛(wèi)星節(jié)點(diǎn)受損或鏈路受干擾中斷導(dǎo)致星座網(wǎng)絡(luò)拓?fù)涞母淖?② 同軌星間鏈路比較穩(wěn)定,而異軌星間鏈路在靠近極區(qū)時因距離、指向角度變化劇烈而中斷,又在飛出極區(qū)后重新建鏈;③ 網(wǎng)絡(luò)中某些節(jié)點(diǎn)或鏈路擁塞導(dǎo)致衛(wèi)星網(wǎng)絡(luò)不可用。以上均可歸結(jié)為節(jié)點(diǎn)受損和鏈路中斷兩種情況。
4.1 節(jié)點(diǎn)受損或鏈路中斷對周圍節(jié)點(diǎn)/鏈路的影響
當(dāng)有節(jié)點(diǎn)受損或鏈路中斷時,可根據(jù)推論1、推論2正向/反向更新各節(jié)點(diǎn)/鏈路介數(shù)。
節(jié)點(diǎn)損毀時介數(shù)變化示意如圖4所示。圖中,節(jié)點(diǎn)VA受損,根據(jù)推論1得到與之相連的鏈路介數(shù)均為0,得到圖4(a)介數(shù)更新值。流出節(jié)點(diǎn)VB的鏈路介數(shù)值為0,根據(jù)推論2得到節(jié)點(diǎn)VB以及流入VB的鏈路介數(shù)值均為0,同理,可推導(dǎo)出節(jié)點(diǎn)VC以及流入VC的鏈路介數(shù)值均為0,介數(shù)值更新如圖4(b)所示。更新鄰接矩陣,根據(jù)鄰接矩陣性質(zhì),得到圖4(c)節(jié)點(diǎn)和鏈路的介數(shù)值。
(c) 更新路由區(qū)域介數(shù)值圖4 節(jié)點(diǎn)損毀時介數(shù)變化示意圖Fig.4 Intermediate value changing with some nodes damaged
單個節(jié)點(diǎn)受損或鏈路中斷,導(dǎo)致周圍節(jié)點(diǎn)/鏈路介數(shù)值增大;當(dāng)節(jié)點(diǎn)/鏈路介數(shù)值增大到1時,表示所有最小跳路徑都要經(jīng)過此節(jié)點(diǎn)/鏈路,因此,若此節(jié)點(diǎn)/鏈路損毀將導(dǎo)致在當(dāng)前區(qū)域內(nèi)最小跳路徑數(shù)為0。
4.2 節(jié)點(diǎn)受損或鏈路中斷對網(wǎng)絡(luò)的影響
考慮隨機(jī)受損和蓄意損毀兩種情況下節(jié)點(diǎn)受損或鏈路中斷對網(wǎng)絡(luò)的影響。其中,隨機(jī)受損情況下,隨機(jī)選取網(wǎng)絡(luò)中節(jié)點(diǎn)或鏈路,設(shè)置其狀態(tài)值;蓄意損毀情況下,根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)或鏈路重要程度進(jìn)行排序[18],優(yōu)先使重要度高的節(jié)點(diǎn)受損或鏈路中斷。以圖5網(wǎng)絡(luò)為例,分析不同情況下節(jié)點(diǎn)受損或鏈路中斷對網(wǎng)絡(luò)的影響。如圖5所示路由區(qū)域,共有11個軌道面,每個軌道面由6顆衛(wèi)星組成,衛(wèi)星編號如圖所示,節(jié)點(diǎn)1為源節(jié)點(diǎn),節(jié)點(diǎn)66為目的節(jié)點(diǎn)。根據(jù)式(3)計算各個衛(wèi)星節(jié)點(diǎn)介數(shù)值,節(jié)點(diǎn)2與節(jié)點(diǎn)65介數(shù)值最大為0.67。
圖5 11×6最小跳路由區(qū)域示意圖Fig.5 11×6 minimum hop routing area
選取不同節(jié)點(diǎn)受損,分析對其他節(jié)點(diǎn)的影響。如圖6所示。節(jié)點(diǎn)2(介數(shù)值0.67)受損對周圍節(jié)點(diǎn)介數(shù)值影響較大,節(jié)點(diǎn)2～11介數(shù)值變?yōu)?,節(jié)點(diǎn)12介數(shù)值變?yōu)?;節(jié)點(diǎn)20(介數(shù)值0.045)受損對周圍節(jié)點(diǎn)影響不大,節(jié)點(diǎn)19介數(shù)值變化最大,由0.093 1變化為0.055 8。
圖6 節(jié)點(diǎn)受損對其他節(jié)點(diǎn)介數(shù)值影響Fig.6 Influence of node damage on the intermediate value of other nodes
圖7為兩種仿真模式下受損衛(wèi)星數(shù)與最小跳路徑數(shù)變化曲線。蓄意損毀模式下,最少兩個衛(wèi)星節(jié)點(diǎn)受損,即導(dǎo)致在當(dāng)前路由區(qū)域中最小跳路徑數(shù)為0;隨機(jī)受損模式下,19個衛(wèi)星節(jié)點(diǎn)受損,才使得最小跳路徑數(shù)為0。
圖7 受損衛(wèi)星數(shù)與最小跳路徑數(shù)變化曲線Fig.7 Number of damaged satellites vs the number of minimum hop paths
圖8為兩種仿真模式下中斷鏈路數(shù)與最小跳路徑數(shù)變化曲線。蓄意損毀模式下,只需要選擇兩條鏈路中斷,即導(dǎo)致在當(dāng)前路由區(qū)域中最小跳路徑數(shù)為0;隨機(jī)受損模式下,則需要多條鏈路中斷,才能使得最小跳路徑數(shù)為0。
圖8 中斷鏈路數(shù)與最小跳路徑數(shù)變化曲線Fig.8 Number of intermediate links vs the number of minimum hop paths
5 結(jié)論
本文針對星座網(wǎng)絡(luò)拓?fù)涑识S網(wǎng)格特點(diǎn),基于最小跳數(shù)路由算法對星座網(wǎng)絡(luò)拓?fù)淇箽赃M(jìn)行了分析。通過鄰接矩陣性質(zhì)計算最小跳路由區(qū)域中節(jié)點(diǎn)和鏈路的介數(shù)值;通過介數(shù)值參數(shù)模型給出星座中節(jié)點(diǎn)/鏈路的重要性,并對比分析隨機(jī)受損和蓄意損毀模式下,部分節(jié)點(diǎn)/鏈路損毀對周圍節(jié)點(diǎn)的影響。從仿真結(jié)果可知,當(dāng)介數(shù)值最大的節(jié)點(diǎn)或鏈路受到蓄意損毀時,網(wǎng)絡(luò)中源節(jié)點(diǎn)到目的節(jié)點(diǎn)最小跳路徑數(shù)會發(fā)生急劇變化,這一結(jié)果對星座健康管理與運(yùn)維管控具有實(shí)際意義。
