基于含時網絡數據的衛星網絡模體識別方法研究

胡博仁　裴忠民　羅章凱　丁杰

摘要： 鑒于開展衛星網絡局部結構研究是理解網絡性質的重要手段，考慮星間鏈路天線可見性約束等條件，提出了一種基于含時網絡數據的衛星網絡模體識別方法，建立了從TLE文件輸入到子結構識別輸出的模體識別流程。以GPS衛星網絡的三節點三邊模體識別為例，結果發現在短時段內衛星天線最大掃描范圍與具有特殊結構意義的三角形M4子圖濃度呈正相關。

關鍵詞： 衛星網絡；模體識別；子圖濃度

中圖分類號： TP393；TP399 文獻標識碼： A

On Motif Counts Method of Satellite Network Based on Temporal Network Data

HU Borena， PEI Zhongmina，LUO Zhangkaia，DING Jieb

（a. Science and Technology on Complex Electronic System Simulation Laboratory;b. Department of Electronics and Optical Engineering， Space Engineering University， Beijing? 101416，China）

Abstract：Conducting research on the local structure of satellite networks is an important means to understand the nature of networks. Considering the visibility constraints of inter-satellite link antennas， a satellite network motif counts method based on temporal network data is proposed， and a motif counts process is established from TLE file input to substructure identification output; taking the three-node three-edge motif counts of GPS satellite network as an example， we found that in a short period of time maximum scanning range of the satellite antenna was positively correlated with the concentration of the triangular M4 subgraph with special structural significance.

Keywords： satellite network; motif counts; subgraph concentration

0 引言

近年來，隨著信息技術和航天技術的不斷發展，在軌衛星數目的增加造成了衛星網絡節點密集化及網絡結構復雜度的提高。從空間資源高效利用和確保網絡安全運行的角度出發，開展衛星網絡結構特性分析具有重要意義。復雜網絡作為網絡科學的重要分支，通過研究結構特性和組織方式來探索和理解復雜系統的結構、行為和功能，為衛星網絡研究提供了有力的方法支持。廣大學者通過復雜網絡的相關理論對衛星網絡進行了深入的研究。武健等[1]基于復雜網絡理論和灰色關聯度分析方法，提出了網絡微觀層面的衛星節點重要度評估指標。朱林等[2]綜合節點介數、節點緊密度和節點距離對衛星網絡節點重要性的貢獻，提出了穩態衛星網絡節點重要性評估方法。王瑩[3]提出了衡量衛星通信網絡整體結構性能的衛星移動通信網約束連通度指標，重點在于度量節點間滿足約束條件的可用路徑。林琪等[4]基于衛星網絡拓撲特征，包括度分布、平均最短路徑和網絡直徑等，提出了衛星網絡綜合效能評估方法。

目前，運用復雜網絡理論對衛星網絡進行結構分析和研究時，多從網絡的整體結構特性出發，如網絡連通度、度分布等，或注重節點或邊的屬性，如節點重要性評估，鮮有衛星網絡局部結構相關的研究。然而局部結構作為網絡結構分析的中尺度視角，與衛星網絡結構的微觀、宏觀分析角度同樣重要，有時局部結構特征能更好地揭示網絡結構與功能的內在關系。模體概念最早于2002年由Milo等[5]提出，定義為網絡中重復出現的局部子圖結構。如靜態三節點有向圖共有圖1中13種，其中某一種子圖在網絡中多次出現，且滿足{P，U，D，N}[5]條件，即可稱之為模體。

Martí Rosas-Casals等[6]對歐洲電網的結構穩定性進行研究，發現相對于分散的去中心化連接模式，四節點三邊規模的星型模體數量增加會加劇網絡的脆弱性。Paul Schultz等[7]提出是否存在某種網絡模體能提高電網結構穩定性的問題，發現彎路模體（Detours motifs）在提高網絡穩定性上具有重要作用，三角形模體即為最簡單的彎路模體（見圖2）。孫曉偉[8]以引文網絡、合作網絡和作者引用網絡的三階網絡模體為研究對象，挖掘論文和作者間引用、合作關系的演化規律。

相比電力網絡和論文引文網絡等靜止網絡，衛星網絡具有動態高時變、網絡數據獲取難等特點，進行衛星網絡局部子圖結構研究具有一定的難度。本文旨在為衛星網絡結構分析中引入中尺度的模體角度，提出一種基于含時網絡數據的衛星網絡模體識別方法，解決衛星網絡模型建立、網絡數據構建和動態模體識別過程中條件不清晰、數據量大等問題。該研究對于揭示衛星網絡局部結構與整體性質之間的關系有著一定的意義，為衛星網絡局部結構研究提供了方法借鑒和技術參考。

1 基于含時網絡數據的衛星網絡模體識別方法

識別衛星網絡中頻繁出現的局部高階子結構，需考慮網絡的動態時變性并自行構建衛星網絡數據。針對上述問題，本文提出了一種基于含時網絡數據的衛星網絡模體識別方法，流程如圖3所示。借助STK和Matlab等軟件，建立仿真衛星網絡模型，設置網絡節點之間的連接條件；生成包含時間屬性的衛星網絡數據；使用動態模體識別算法進行子圖計數并計算子圖濃度等指標，以此來進行衛星網絡結構分析。

1.1 建立衛星網絡模型

本文研究的衛星網絡，以衛星星座為主體，泛指由存在于近地空間的衛星節點和地面段的地面站節點組成，節點之間以星間鏈路和星地鏈路兩種形式建立連接，用于信息傳輸和星座業務實現的網絡系統，如圖4所示。

下載Celestrak網站的衛星星歷（TLE）文件，導入STK，建立近地空間的衛星星座模型，或者根據軌道六參數，確定衛星的軌道和位置。衛星網絡中的地面站節點設置與具體衛星系統類型有關，如衛星導航系統的地面段包括主控站、注入站和監測站。查閱資料得到站點的經度、緯度信息，建立地面站點，或查詢STK自帶地面站庫，直接添加。

衛星網絡中的邊包括星地鏈路和星間鏈路，根據衛星網絡實際運行情況，結合簡化假設，設置模型中邊的連接準則。星間鏈路的建立條件包括[9]：幾何可視條件、天線可視條件和傳輸距離條件。星間鏈路天線可見性的約束條件[9]：

1.2 構建衛星網絡數據

含時網絡[1011]在復雜網絡模型的基礎上，加入了時間維度，用（V，E，t）表示，其中t代表網絡連邊的發生時刻，主要用來刻畫離散時間內網絡連邊斷續存在的情形。比如在衛星網絡進行數據傳輸時，A和B之間的連邊僅在進行數據傳輸時存在，數據傳輸結束后，連邊也隨之消失。只在A、B之間建立一條連邊已無法描述節點相互作用時刻變化的特點。

網絡的動態變化具體表現為邊數量的增減或節點數量的增減，而衛星網絡的節點數量通常不發生變化，邊的數量隨時間不斷變化。用三元組（u，v，t）表示衛星網絡中的連邊，u表示邊起點，v表示邊終點，t表示u和v在t時刻處于連接狀態。

Matlab與STK互聯之后，可以調取衛星節點和地面站節點的相關數據，包括某時刻下，衛星之間的距離和衛星的高程，衛星與地面站是否滿足幾何可見性約束等。依據衛星網絡模型中邊的連接準則并進行條件判斷之后，獲取某一時間段內的網絡三元組邊數據，完成衛星網絡數據的構建。

1.3 識別衛星網絡模體

網絡模體識別是網絡模體研究的重點和難點之一。經典的模體識別算法[12]主要是面向靜態網絡，生成若干個與實證網絡節點數和節點的度序列相同的隨機網絡；在實證網絡和隨機網絡中搜索某一規模的子圖，將同構的子圖歸為一類；比較每一類子圖在實證網絡和隨機網絡中的出現次數以確定其統計意義，從而確定是否為網絡模體。常用的靜態網絡模體識別工具包括MFinder[13]，FANMOD[14]，MODA[15]和NemoMap[16]等。

衛星網絡是具有時變性的動態網絡。面向動態網絡的模體識別算法包括基于流模型的StreaM[17]和Massive Streaming Data Analytics[18]，SNAP（Stanford Network Analysis Project）框架下的Motifs in temporal networks 動態模體識別抽樣算法[19]和oDEN算法[20]等。

構建衛星網絡數據后，選用SNAP框架下面向大規模網絡數據的抽樣動態三節點模體識別算法，該算法適用于二節點三邊和三節點三邊的36種有向子圖計數，如圖6所示。由于網絡帶有時間屬性，引入時間參數δ，并定義δ衛星網絡模體：由具有時間屬性的邊組成的子圖，模體中的有向時空邊（帶時間戳）具有先后順序，受時間段δ約束，即連接關系均發生在時間段δ內，用數學表達式可表示為

其中，t1，t2，…為衛星網絡模體中的邊連接時刻。

本文建立的衛星網絡模型，衛星間連接和衛星與地面的連接均為無向邊，三節點三邊無向圖共4種（見圖7），需將算法識別的有向子圖轉換為無向子圖。

對無向衛星網絡數據進行模體識別時，有向圖中有帶環的子圖如M1，2，會出現重復計數的現象，使得計數結果多于實際無向圖，故不考慮。 SNAP框架下的temporal motifs 算法為提高識別速度運用了抽樣思想，使對應同一種無向子圖的有向子圖計數結果存在細微差別，故取有向圖計數結果的均值為無向圖計數結果，具體計算見公式（4）：

4種三節點三邊無向圖中，M1、M2、M3均為星型子圖，指單節點為中心節點，其他節點直接與中心節點相連構成的子圖，M4為三角形彎路子圖，有利于網絡結構的穩定，重點關注子圖M4的出現次數和子圖濃度。子圖濃度是指相同實驗條件下，同等子圖規模的某種子圖所占的比例，體現了網絡中同等規模不同連接模式子圖的分布情況，計算如式（5）所示。

其中，Ck為某子圖規模下第k個子圖結構的子圖濃度，Mk為第k個子圖的出現次數，該子圖規模下，共有N個異構子圖結構。

2 實例分析

以GPS為例，建立由空間在軌衛星和地面監測站組成的衛星網絡模型。GPS由空間段、地面段和用戶終端組成，本文不考慮用戶終端?？臻g段由30顆中軌道衛星組成。地面段包括主控站、監測站及注入站，主控站[21]主要是收集和處理監測站的觀測數據；監測站利用復雜的GPS接收機跟蹤從監測站上空經過的GPS衛星，收集導航信號、范圍測量數據和大氣數據等；注入站在衛星離開其作用范圍之前進行指令等信息注入。綜上，為簡化模型，故本文只考慮GPS衛星與監測站之間的信息傳輸，建立由空間段衛星節點和監測站節點組成的衛星網絡，且不考慮地面節點間的連接。在STK軟件中建立的16個GPS監測站點如圖8所示。

使用Celestrak網站的兩行根數（TLE）文件，構建GPS空間段。TLE文件的時間為2021年12月21日，導入STK軟件，衛星節點數量為30，地面站節點和衛星節點數目總和為46，3D示意如圖9所示。

設定節點間的連邊條件。某時刻下，若衛星間的距離lAB 滿足星間鏈路的幾何可見性約束及天線可見性約束，則認為衛星節點間建立了雙向連接，不考慮傳輸距離等因素的影響；某時刻下，若地面站節點與衛星節點滿足可見性約束，則認為建立了從衛星到地面站的雙向連接，不考慮時延和誤碼等因素。在星間鏈路建立時，天線可見性約束（見式（1））中的衛星天線最大掃描范圍αmax起關鍵作用，對網絡拓撲結構具有較大影響[22]。結合實際衛星網絡運行情況并考慮數據量規模等問題，設置實驗時長為86 400 s，時間步長為1 s，天線最大掃描范圍分別為30°，45°和60°，三種情況下的GPS衛星網絡邊數據，均以txt文件格式輸出，每一行皆為三元組（u，v，t），代表一條邊，輸出數據的情況如表1所示。

若忽視衛星與地面站之間的連接（簡稱為第1種情況），GPS衛星網絡將是一個獨立自主運行的系統?？紤]衛星網絡信息傳輸的時效性，時間參數δ取值為1s、2s、3s（三邊連接時間點的最大間隔不超過δs），三節點三邊無向圖子圖濃度統計結果如圖10、圖11和圖12所示，子圖濃度計算式如式（5）所示。

既考慮星間鏈路，又考慮星地鏈路（簡稱為第2種情況）時的結果如圖11、圖12所示。

由圖10、圖11和圖12可得：1）圖10、圖11和圖12所處情況下，天線最大掃描范圍都與M4子圖濃度呈正相關，αmax越大，衛星節點間的連接越多，全連通結構子圖的出現概率越大，M4子圖濃度越高，越有利于網絡的穩定。 2）αmax=30°和60°時，第2種情況的M4子圖濃度均高于第1種情況，說明在αmax值較小時，可以借助星地鏈路建立 “衛星－地面站－衛星”的三節點全連通結構；在αmax值較大時，衛星節點之間的聯系緊密，第1種情況下的網絡具有較高的連通度，增加星地鏈路之后，地面站同時與多個衛星建立連接，增加了三節點全連通結構的出現次數，提高了M4子圖濃度。3）按照三條邊的發生順序，M1和M2的邊路徑發生了一次轉換，而M3發生了兩次轉換，發現在第1種情況和第2種情況的不同αmax下，M1和M2總是具有相同的子圖濃度。在本文的衛星網絡模型中，受節點連接關系特性的影響，節點之間的連接在某一時間段內持續存在，使得邊路徑發生一次轉換的M1和M2同時出現并具有相同的出現次數。

3 結語

建立衛星網絡模型、構建衛星網絡數據和識別衛星網絡模體，提出了衛星網絡模體識別的一般方法，建立了從TLE文件輸入到子結構識別輸出的衛星網絡模體識別流程；以GPS衛星網絡的三節點模體識別為例進行了實證分析，結果表明：此方法基本可以實現衛星網絡三節點無向圖模體識別，子圖濃度分布受模型相關參數值的影響較大，短時段內天線最大掃描范圍與M4子圖濃度呈正相關。

本文提出的衛星網絡模體識別方法，包括如下不足：建立的衛星網絡模型較為簡單，特別是網絡在建立星間鏈路和星地鏈路時，考慮的相關約束和條件較少，假設較多；受動態網絡模體識別算法的影響，僅能識別三節點模體。下一步可以分析網絡遭受攻擊和損害情況下M4子圖濃度的變化情況，進行衛星網絡節點重要性評估和魯棒性評估等。

參考文獻：

[1]武健，劉新學，舒健生，等. 基于復雜網絡的衛星重要度評估[J]. 火力與指揮控制， 2014， 39（5）： 60－63.

WU J， LIU X X， SHU J S， et al. Satellite significance assessment based on complex network[J]. Fire Power and Command Control， 2014， 39（5）： 60－63.

[2]朱林，方勝良，胡卿，等.衛星時變拓撲網絡節點重要度評估方法[J].系統工程與電子技術，2017，39（6）：1274－1279.

ZHU L， FANG S L， HU Q， et al. Evaluation method of node significance of satellite time-varying topology network[J]. System Engineering and ElectronicTechnology，2017，39（6）：1274－1279.

[3]王瑩.衛星移動通信網若干理論和技術研究[D].武漢：華中科技大學，2008.

WANG Y.Research on theoretical and technical of satellite mobile communication network[D]. Wuhan： Huazhong University of Science and Technology，2008.

[4]林琪，李智.基于拓撲特征的衛星網絡效能評估[J].中南大學學報（自然科學版），2013，44（S2）：368－371.

LIN Q， LI Z. Evaluation of Satellite network performance based on topological characteristics[J]. Journal of Central South University（Natural Science Edition），2013，44（S－2）：368－371.

[5]MILO R， SHEN-ORR S， ITZKOVITZ N，et al. Network motifs：simple building blocks of complex networks[J]. Science， 298（5594）：824－827.

[6]CASALS M R， Corominas-Murtra B. Assessing european power grid reliability by means of topological measures[J]. OAI， 2009，121：527－537.

[7]PAUL S， JOBST H， KURTHS J，et al. Detours around basin stability in power networks[J].New Journal of Physics，2014，16（12）：125001.

[8]孫曉偉. 基于網絡模體的科學學數據研究[D].成都：電子科技大學，2019.

SUN X W. Scientific data research based on networkmotif[D]. Chengdu： University of Electronic Science and Technology of China，2019.

[9]高賀. 北斗導航系統星間鏈路分配方法研究[D].湖南：湖南大學，2018.

GAO H. Research on inter-satellite link allocation method of BDS[D]. Hunan： Hunan University，2018.

[10] 辜姣，郭龍，江健，等.多層網絡和含時網絡的相關問題研究[J].復雜系統與復雜性科學，2016，13（1）：58－63，67.

GU J， GUO L， JIANG J， et al. Research on related problems of multilayer networks andtemporal networks[J]. Complex Systems and Complexity Science，2016，13（1）：58－63，67.

[11] HOLME P， SARAMKI J. Temporal networks[J]. Physics Reports， 2012， 519（3）：97－125.

[12] 覃桂敏.復雜網絡模式挖掘算法研究[D]. 西安：西安電子科技大學， 2013.

QIN G M. Research on complex network pattern mining algorithm[D]. Xi′an： Xidian University， 2013.

[13] KASHTAN N， ITZKOVITZ S， MILO R， et al. Efficient sampling algorithm for estimating subgraph concentrations and detecting network motifs.[J]. Bioinformatics，2004，20（11）：1746－1758.

[14] WERNICKE S， RASCHE F. FANMOD： a tool for fast network motif detection[J]. Bioinformatics，2006，22（9）：1152－1153.

[15] SAEED O， FALK S， MASOUDI-NEJAD， et al. MODA： an efficient algorithm for network motif discovery in biological networks[J]. Genes & Genetic Systems，2009，84（5）：385－395.

[16] TIEN H， SOMADINA M， KIM W， et al. NemoMap improved motifcentric network motif discovery algorithm[J]. Advances in Science， Technology and Engineering Systems，2018，3（5）：186－199.

[17] SCHILLER B， JAGER S， HAMACHER K， et al. Strea m-a stream-based algorithm for counting motifs in dynamic graphs[C]// International Conference on Algorithms for Computational Biology. Mexico： Springer， Cham， 2015.

[18] EDIGER D， JIANG K， RIEDY J， et al. Massive streaming data analytics： a case study with clustering coefficients[C]// IEEE International Symposium on Parallel & Distributed Processing. Atlanta， Georgia，? USA： IEEE， 2010.

[19] ASHWIN P， AUSTIN R? B， JURE L. Motifs in temporal-networks[J].CoRR，2016，abs/1612.09259.

[20] SARPE I， VANDIN F. odeN： simultaneous approximation of multiple motif counts in large temporal networks[C]. Proceedings of the 30th ACM International Conference on Information & Knowledge Management， Virtual Event. Queensland， Australia： 2021： 1568－1577.

[21] 劉天雄.GPS全球定位系統由幾部分組成？[J].衛星與網絡，2012（4）：56－62.

LIU T X. How many parts does GPS system consist of？ [J]. Satellite and Network，2012（4）：56－62.

[22] 李朝瑞，孟新. 星座仿真中天線掃描范圍對系統的影響分析[C]//中國空間科學學會空間探測專業委員會第十九次學術會議論文集（下冊）.寧波， 2006，2：433－437.

LI C R， MENG X. Analysis of the influence of antenna scanning range on the system in constellation simulation[C]//Proceedings of the 19th Academic Conference of the Space Exploration Professional Committee of the Chinese Society of Space Sciences? 2. Ningbo， 2006， 2： 433－437.

（責任編輯 李 進）

收稿日期： 2022－04－07；修回日期：2022－06－20

基金項目： 復雜電子系統仿真重點實驗室基礎研究項目（DXZT-JC-ZZ-2020-001）

第一作者： 胡博仁（1999－），男，湖南寧鄉人，碩士研究生，主要研究方向為復雜網絡、系統科學。

通信作者： 裴忠民（1976－），男，山東濟寧人，博士，副研究員，主要研究方向為計算機科學與技術、系統科學。