基于最小跳數(shù)的星座網(wǎng)絡(luò)拓?fù)淇箽苑治?/h1>

2023-10-11 03:50:14孫景云張國(guó)亭

無(wú)線電通信技術(shù)訂閱 2023年5期 收藏

關(guān)鍵詞：介數(shù)網(wǎng)絡(luò)拓?fù)?/a>星座

孫景云,張國(guó)亭,柳 震,王 進(jìn)

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

0 引言

單顆衛(wèi)星對(duì)地球的覆蓋能力有限,但多顆不同軌道的衛(wèi)星可組成星座,并通過(guò)在衛(wèi)星節(jié)點(diǎn)間建立星間鏈路實(shí)現(xiàn)互聯(lián)互通,為全球范圍內(nèi)用戶提供全覆蓋、全實(shí)時(shí)服務(wù)。衛(wèi)星所處空間環(huán)境復(fù)雜多變,通信鏈路易被干擾,當(dāng)星座網(wǎng)絡(luò)拓?fù)渲械墓?jié)點(diǎn)和鏈路發(fā)生隨機(jī)故障或遭受蓄意損毀,會(huì)造成節(jié)點(diǎn)受損、鏈路中斷,進(jìn)而影響星座服務(wù)效能。上述故障對(duì)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化以及對(duì)周圍節(jié)點(diǎn)和鏈路的影響,是本文分析研究的重點(diǎn)。

關(guān)于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性分析,國(guó)內(nèi)外均有相關(guān)研究。文獻(xiàn)[1]給出抗毀性定義和測(cè)度,總結(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]對(duì)比非全連通網(wǎng)絡(luò)與全連通網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)差異,提出基于最短路徑數(shù)的抗毀性評(píng)估算法,以網(wǎng)絡(luò)中節(jié)點(diǎn)之間的最短路徑數(shù)的長(zhǎng)度和條數(shù)作為核心考察指標(biāo),來(lái)評(píng)估網(wǎng)絡(luò)的抗毀性能。網(wǎng)絡(luò)抗毀性本質(zhì)在于節(jié)點(diǎn)間存在可替代途徑,文獻(xiàn)[3-4]以網(wǎng)絡(luò)自然連通度為測(cè)度,將復(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ò)可靠性、抗毀性評(píng)估轉(zhuǎn)化為跳面節(jié)點(diǎn)可靠性及跳面間關(guān)聯(lián)性進(jìn)行求解,并給出定量計(jì)算的數(shù)學(xué)解析式。文獻(xiàn)[6]將跳面節(jié)點(diǎn)法應(yīng)用到衛(wèi)星網(wǎng)絡(luò)中,根據(jù)衛(wèi)星網(wǎng)絡(luò)高動(dòng)態(tài)、周期性的特點(diǎn),對(duì)跳面節(jié)點(diǎn)法進(jìn)行了改進(jìn),提高了對(duì)相似拓?fù)浣Y(jié)構(gòu)的區(qū)分度。這些網(wǎng)絡(luò)拓?fù)淇箽阅Ｐ透饔衅鋫?cè)重點(diǎn),也各有局限性。文獻(xiàn)[7]提出區(qū)域級(jí)網(wǎng)絡(luò)拓?fù)淇箽栽u(píng)估算法,衡量不同區(qū)域受到攻擊的程度。文獻(xiàn)[8]定義了復(fù)雜網(wǎng)絡(luò)冗余度并對(duì)網(wǎng)絡(luò)抗毀性進(jìn)行量化,通過(guò)刪除節(jié)點(diǎn)評(píng)估節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)的重要程度。

文獻(xiàn)[9]從網(wǎng)絡(luò)面臨的威脅類型出發(fā),可以分為隨機(jī)失效和蓄意損毀兩種失效類型。文獻(xiàn)[10]提出無(wú)標(biāo)度網(wǎng)絡(luò)可以有效應(yīng)對(duì)隨機(jī)失效帶來(lái)的影響,而對(duì)于蓄意損毀卻十分脆弱。因此,研究星座網(wǎng)絡(luò)拓?fù)淇箽?也可以從節(jié)點(diǎn)重要性角度來(lái)進(jìn)一步研究[11]。評(píng)估節(jié)點(diǎn)重要性比較常用的方法有[12]:度中心性,以節(jié)點(diǎn)的連接數(shù)作為測(cè)度指標(biāo);接近中心性,以節(jié)點(diǎn)靠近網(wǎng)絡(luò)中心的程度判斷節(jié)點(diǎn)重要性;介數(shù)中心性,以節(jié)點(diǎn)/鏈路作為其中兩個(gè)節(jié)點(diǎn)之間最短路徑的橋梁的次數(shù)作為刻畫節(jié)點(diǎn)重要性的指標(biāo)。

本文以局部網(wǎng)絡(luò)為分析對(duì)象,重點(diǎn)研究網(wǎng)絡(luò)拓?fù)渲心承┕?jié)點(diǎn)受損或鏈路中斷對(duì)其他節(jié)點(diǎn)及網(wǎng)絡(luò)的影響。對(duì)于Walker星座,其網(wǎng)絡(luò)拓?fù)鋵?duì)稱,度中心性和接近中心性不適用于節(jié)點(diǎn)重要性評(píng)價(jià)指標(biāo),介數(shù)中心性可以直觀描述節(jié)點(diǎn)/鏈路對(duì)最短路徑數(shù)的影響?？紤]到衛(wèi)星發(fā)射與維護(hù)的高額成本,進(jìn)行網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)抗毀性的分析評(píng)估對(duì)星座規(guī)劃設(shè)計(jì)、運(yùn)維管控、健康管理均具有重要意義。

1 星座網(wǎng)絡(luò)拓?fù)浣?/h2>

每個(gè)衛(wèi)星設(shè)計(jì)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ù)銰相對(duì)應(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為對(duì)稱矩陣,由于衛(wèi)星自身與自身之間不存在星間鏈路,因此鄰接矩陣A的對(duì)角元素均為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中每個(gè)元素均不為零。

2 最小跳數(shù)路由算法

每條路徑的權(quán)值為1時(shí),最短路徑算法等效于最小跳數(shù)算法。衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)呈二維網(wǎng)格狀,在異軌和同軌星間鏈路傳播時(shí)延相差不大的情況下,可將跳數(shù)作為最優(yōu)路徑的主要衡量指標(biāo)[15]。

從源節(jié)點(diǎn)到目的節(jié)點(diǎn),跳數(shù)最小時(shí),所有可能經(jīng)過(guò)的節(jié)點(diǎn)和鏈路的集合,定義為最小跳數(shù)路由區(qū)域。如圖2(a),當(dāng)源節(jié)點(diǎn)與目的節(jié)點(diǎn)處于同一條軌道面或異軌同一位置時(shí),最小跳數(shù)路由區(qū)域?yàn)橐粭l線;如圖2(b),當(dāng)源節(jié)點(diǎn)與目的節(jié)點(diǎn)不處于同一條軌道且不同位置時(shí),最小跳數(shù)路由區(qū)域?yàn)橐粋€(gè)矩形區(qū)域[16]。

(a) 線形區(qū)域

最小跳數(shù)可以由最小跳數(shù)路由區(qū)域中長(zhǎng)與寬的和來(lái)表示:

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)過(guò)某個(gè)節(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)過(guò)節(jié)點(diǎn)Vi的最小跳路徑數(shù)量,σst(Eij)表示從節(jié)點(diǎn)Vs～Vt且經(jīng)過(guò)鏈路Eij的最小跳路徑數(shù)量。采用鄰接矩陣對(duì)節(jié)點(diǎn)/鏈路介數(shù)進(jìn)行計(jì)算,得到:

(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ù)之和,同時(shí)等于流出節(jié)點(diǎn)鏈路介數(shù)之和。源節(jié)點(diǎn)和目的節(jié)點(diǎn)的介數(shù)為1。得到如下公式:

(6)

圖3為一個(gè)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)受損或鏈路中斷對(duì)周圍節(jié)點(diǎn)和鏈路的影響。

圖3 節(jié)點(diǎn)/鏈路介數(shù)示意圖Fig.3 Node/Link intermediate diagram

推論1若某個(gè)節(jié)點(diǎn)受損,則與其相連的鏈路介數(shù)為0。

證明:若某個(gè)節(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),其動(dòng)態(tài)特性主要來(lái)自如下幾方面:① 衛(wèi)星節(jié)點(diǎn)受損或鏈路受干擾中斷導(dǎo)致星座網(wǎng)絡(luò)拓?fù)涞母淖?② 同軌星間鏈路比較穩(wěn)定,而異軌星間鏈路在靠近極區(qū)時(shí)因距離、指向角度變化劇烈而中斷,又在飛出極區(qū)后重新建鏈;③ 網(wǎng)絡(luò)中某些節(jié)點(diǎn)或鏈路擁塞導(dǎo)致衛(wèi)星網(wǎng)絡(luò)不可用。以上均可歸結(jié)為節(jié)點(diǎn)受損和鏈路中斷兩種情況。

4.1 節(jié)點(diǎn)受損或鏈路中斷對(duì)周圍節(jié)點(diǎn)/鏈路的影響

當(dāng)有節(jié)點(diǎn)受損或鏈路中斷時(shí),可根據(jù)推論1、推論2正向/反向更新各節(jié)點(diǎn)/鏈路介數(shù)。

節(jié)點(diǎn)損毀時(shí)介數(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í)介數(shù)變化示意圖Fig.4 Intermediate value changing with some nodes damaged

單個(gè)節(jié)點(diǎn)受損或鏈路中斷,導(dǎo)致周圍節(jié)點(diǎn)/鏈路介數(shù)值增大;當(dāng)節(jié)點(diǎn)/鏈路介數(shù)值增大到1時(shí),表示所有最小跳路徑都要經(jīng)過(guò)此節(jié)點(diǎn)/鏈路,因此,若此節(jié)點(diǎn)/鏈路損毀將導(dǎo)致在當(dāng)前區(qū)域內(nèi)最小跳路徑數(shù)為0。

4.2 節(jié)點(diǎn)受損或鏈路中斷對(duì)網(wǎng)絡(luò)的影響

考慮隨機(jī)受損和蓄意損毀兩種情況下節(jié)點(diǎn)受損或鏈路中斷對(duì)網(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)受損或鏈路中斷對(duì)網(wǎng)絡(luò)的影響。如圖5所示路由區(qū)域,共有11個(gè)軌道面,每個(gè)軌道面由6顆衛(wèi)星組成,衛(wèi)星編號(hào)如圖所示,節(jié)點(diǎn)1為源節(jié)點(diǎn),節(jié)點(diǎn)66為目的節(jié)點(diǎn)。根據(jù)式(3)計(jì)算各個(gè)衛(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)受損,分析對(duì)其他節(jié)點(diǎn)的影響。如圖6所示。節(jié)點(diǎn)2(介數(shù)值0.67)受損對(duì)周圍節(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)受損對(duì)周圍節(jié)點(diǎn)影響不大,節(jié)點(diǎn)19介數(shù)值變化最大,由0.093 1變化為0.055 8。

圖6 節(jié)點(diǎn)受損對(duì)其他節(jié)點(diǎn)介數(shù)值影響Fig.6 Influence of node damage on the intermediate value of other nodes

圖7為兩種仿真模式下受損衛(wèi)星數(shù)與最小跳路徑數(shù)變化曲線。蓄意損毀模式下,最少兩個(gè)衛(wèi)星節(jié)點(diǎn)受損,即導(dǎo)致在當(dāng)前路由區(qū)域中最小跳路徑數(shù)為0;隨機(jī)受損模式下,19個(gè)衛(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é)論

本文針對(duì)星座網(wǎng)絡(luò)拓?fù)涑识S網(wǎng)格特點(diǎn),基于最小跳數(shù)路由算法對(duì)星座網(wǎng)絡(luò)拓?fù)淇箽赃M(jìn)行了分析。通過(guò)鄰接矩陣性質(zhì)計(jì)算最小跳路由區(qū)域中節(jié)點(diǎn)和鏈路的介數(shù)值;通過(guò)介數(shù)值參數(shù)模型給出星座中節(jié)點(diǎn)/鏈路的重要性,并對(duì)比分析隨機(jī)受損和蓄意損毀模式下,部分節(jié)點(diǎn)/鏈路損毀對(duì)周圍節(jié)點(diǎn)的影響。從仿真結(jié)果可知,當(dāng)介數(shù)值最大的節(jié)點(diǎn)或鏈路受到蓄意損毀時(shí),網(wǎng)絡(luò)中源節(jié)點(diǎn)到目的節(jié)點(diǎn)最小跳路徑數(shù)會(huì)發(fā)生急劇變化,這一結(jié)果對(duì)星座健康管理與運(yùn)維管控具有實(shí)際意義。

猜你喜歡

介數(shù)網(wǎng)絡(luò)拓?fù)?/a>星座

基于通聯(lián)關(guān)系的通信網(wǎng)絡(luò)拓?fù)浒l(fā)現(xiàn)方法

網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2022年2期)2022-05-23 13:25:46

電子制作(2018年23期)2018-12-26 01:01:16

星座

健康女性(2017年3期)2017-04-27 21:34:31

勞斯萊斯古斯特與魅影網(wǎng)絡(luò)拓?fù)鋱D

汽車維修技師(2017年10期)2017-03-17 02:25:01

12星座之我愛洗澡

兒童故事畫報(bào)(2016年5期)2017-02-07 20:15:30

星座

都市麗人(2016年12期)2016-12-14 09:54:15

星座

都市麗人(2016年7期)2016-08-03 10:06:05

電測(cè)與儀表(2016年5期)2016-04-22 01:13:46

基于電氣介數(shù)的電力系統(tǒng)脆弱線路辨識(shí)

通信電源技術(shù)(2016年3期)2016-03-26 07:13:46

樹形網(wǎng)絡(luò)的平均介數(shù)*

網(wǎng)絡(luò)安全與數(shù)據(jù)管理(2014年3期)2014-11-10 07:09:48