運用動態(tài)規(guī)劃的智能衛(wèi)星集群星間通信路由算法 *

倫偉成，李 群，于芹章，張 燦

(1. 國防科技大學 系統(tǒng)工程學院, 湖南 長沙 410073； 2. 復雜系統(tǒng)仿真總體重點實驗室, 北京 100101)

智能衛(wèi)星是具有自主能力的一類人造衛(wèi)星，它能夠在盡可能減少地面指令的直接操控下獨立完成任務，如此可降低操作成本且節(jié)省通信資源。單個智能衛(wèi)星的能力有限，將多個智能衛(wèi)星編組為智能衛(wèi)星集群(Smart-Satellites-Swarm，SSS)則可以增強衛(wèi)星的多任務遂行能力和抗干擾能力，提高衛(wèi)星完成復雜航天任務的效率和成功率。以色列的SAMSON計劃[1]和美國的小行星探測計劃[2]都是典型的智能衛(wèi)星集群實例。

要促進從智能衛(wèi)星的“單體自主”向SSS的“群體智能”發(fā)展，必須使衛(wèi)星具備網(wǎng)絡化信息協(xié)同能力，在此基礎上建立有效的星間信息協(xié)同機制，讓SSS的成員衛(wèi)星可以借助星間鏈路進行通信以實現(xiàn)信息交互和任務協(xié)作，從而更好地完成那些對時效性、響應性、自主性都有較高要求的任務。為了達到前述目標，亟待解決智能衛(wèi)星集群的星間通信路由問題(Inter-satellite Communication Routing Problem of Smart-satellites-swarm，ICRPS)。ICRPS的核心是如何規(guī)劃數(shù)據(jù)從源衛(wèi)星傳到目的衛(wèi)星的合理路徑，使星間通信在時延等方面滿足任務要求。

星間通信路由問題可以在衛(wèi)星網(wǎng)絡的背景下進行研究，衛(wèi)星網(wǎng)絡的節(jié)點是衛(wèi)星、邊是星間鏈路。Xu等[3]提出了基于編碼的多路徑路由算法以應對多層衛(wèi)星網(wǎng)絡中的通信擁塞問題。Xie等[4]面向動態(tài)星間網(wǎng)絡提出了采用廣義領域搜索的星間路由算法。Huang等[5]采用梯級優(yōu)化設計方法來設計導航衛(wèi)星網(wǎng)絡的星間鏈路聯(lián)絡方案。Wang等[6]面向低軌衛(wèi)星通信網(wǎng)絡提出了基于軟件定義網(wǎng)絡架構的改進路由算法。尤啟迪等[7]針對面向衛(wèi)星網(wǎng)絡的空間信息快速回傳場景提出了多路徑快照聚合路由算法。Soret等[8]面向低軌元星座衛(wèi)星網(wǎng)絡提出了通過最小化軌道面間鏈路來自動分配路由的算法。Zhang等[9]面向低軌衛(wèi)星網(wǎng)絡提出了基于星間鏈路狀態(tài)信息的星上自動控制的路由算法。Roth等[10]針對雙低軌Walker星型星座設計了采用星間鏈路的兩層地理路由體制。梁俊等[11]針對軟件定義衛(wèi)星網(wǎng)絡提出了基于切比雪夫神經(jīng)網(wǎng)絡的智能路由策略。

上述算法主要針對傳統(tǒng)衛(wèi)星，在工作模式方面還是由地面的指控中樞預先規(guī)劃路由，且路由一旦確定便不再更改，衛(wèi)星在其中只能機械地收發(fā)數(shù)據(jù)，若將這些算法用于ICRPS，則無法發(fā)揮智能衛(wèi)星的自主性優(yōu)勢。

因此本文研究了一種適用于智能衛(wèi)星的星間通信路由算法，該算法基于動態(tài)規(guī)劃的思想，由各衛(wèi)星自主參與規(guī)劃路由，使其在規(guī)劃時能夠根據(jù)SSS現(xiàn)狀靈活調(diào)整路由，達到路由在數(shù)據(jù)傳送過程中持續(xù)動態(tài)更新的效果。

1 ICRPS概述

為了求解ICRPS，需要基于SSS建立智能衛(wèi)星集群網(wǎng)絡(Network of Smart-Satellites-Swarm，NSSS)：將SSS各成員抽象為節(jié)點，成員之間存在的星間鏈路抽象為邊，邊的權值就是星間鏈路的長度；從而把ICRPS轉換為求解NSSS的兩個節(jié)點間的最優(yōu)路徑。

不過，ICRPS尋求的最優(yōu)路徑要滿足時延最短而非長度最短。時延是指數(shù)據(jù)從源衛(wèi)星傳送到目的衛(wèi)星所需的時間，ICRPS主要考慮以下兩種時延：

1)發(fā)送時延，指從發(fā)送數(shù)據(jù)的第一個比特算起到其最后一個比特發(fā)送完畢所需的時間[12]，等于數(shù)據(jù)長度與發(fā)送速率之商；

2)傳播時延[12]，指電信號傳播星間鏈路長度的距離所需的時間，等于星間鏈路長度與電信號傳播速率(約等于光速)之商。

因NSSS的節(jié)點處在不斷運動中，節(jié)點間時延和鏈路連通性也在不斷發(fā)生變化[11]，故NSSS其實屬于動態(tài)網(wǎng)絡；但在某個具體時刻NSSS又是靜態(tài)網(wǎng)絡，因為衛(wèi)星在此時刻的位置是固定的?？紤]到NSSS的這種二元特性，結合智能衛(wèi)星的自主性，采用動態(tài)規(guī)劃策略求解ICRPS，分多個階段規(guī)劃SSS成員星間通信的路由，在每一階段中把NSSS作靜態(tài)網(wǎng)絡處理，各階段的NSSS整合起來又是隨時間變化的動態(tài)網(wǎng)絡。

采用圖論的表示方法[13]，將NSSS記作(V,A)，V表示節(jié)點集(即衛(wèi)星集合)，A表示邊集(即星間鏈路集合)，節(jié)點數(shù)記為|V|=n，再構造NSSS的鄰接矩陣Q=(qij)n×n，qij的賦值規(guī)則如式(1)所示。

(1)

為便于表達，規(guī)定：衛(wèi)星vi、節(jié)點vi和vi這三種表達是等價的；邊和星間鏈路含義相通；邊權值和星間鏈路長度含義相通。

包含vi和vj的衛(wèi)星對能否建立星間鏈路(簡稱“建鏈”)取決于是否同時滿足以下兩個條件：

1)衛(wèi)星對彼此可見，要求地心到衛(wèi)星對連線的直線距離hL大于地球強電離層高度hI與地球半徑RE之和，即

hL>hI+RE

(2)

2)衛(wèi)星對可以互相通信，要求vi對于vj的俯仰角θi在vi的天線掃描范圍之內(nèi)且vj對于vi的俯仰角θj在vj的天線掃描范圍之內(nèi)，即

(3)

式中，γi,min和γj,min分別表示vi和vj的天線掃描范圍的下限，γi,max和γj,max表示上限。

衛(wèi)星對若能建鏈，便可以進行通信，此時其星間鏈路的長度就等于衛(wèi)星之間的直線距離。

作為智能衛(wèi)星，SSS各成員可以采用文獻[14]中的方法根據(jù)軌道根數(shù)計算其他成員在慣性坐標系的位置，進而在考察是否滿足式(2)和式(3)所示條件的基礎上得到當前時刻的NSSS。在必要時，SSS將通過地面站上注星歷等方式保證計算的準確性。

2 星間通信路由靜態(tài)規(guī)劃算法

2.1 算法描述

星間通信路由靜態(tài)規(guī)劃算法借鑒了Dijkstra算法[15]的思想，用于求解某一具體時刻的靜態(tài)NSSS上一條以vb為起點、ve為終點的時延最短路徑。

設vi,vj∈V，定義有向鏈表Pj(vi)表示從vj到vi的路徑(未必最優(yōu))，Pj(vi)的長度記作Lj(vi)，Pj(vi)的節(jié)點數(shù)記作|Pj(vi)|，從而構造函數(shù)Tj(vi)描述數(shù)據(jù)傳輸?shù)目倳r延：

(4)

式中，c是電信號在星間鏈路中的傳播速度(下同)，dT表示數(shù)據(jù)的一次發(fā)送時延。則算法追求的最優(yōu)即等價于Tb(ve)最小。

將vj到vi的最優(yōu)路徑的時延記作Dj(vi)，定義集合Sb表示為規(guī)劃從vb出發(fā)的最優(yōu)路徑而考察過的所有節(jié)點。初始時，對?vi∈V，令Pb(vi)=[vb,vi](采用中括號表示鏈表，以區(qū)別于集合)，Dj(vi)=0，Sb={vb}。算法的具體流程如算法1所示，其中運算符⊕表示將符號后的元素添加到符號前的鏈表末尾。

算法1 星間通信路由靜態(tài)規(guī)劃算法

2.2 算法有效性分析

本節(jié)將證明算法1的有效性。

前述證明否定了算法結束時有vt∈Sb或vt∈V-Sb，于是vt∈?，因此并不存在比P#更優(yōu)的P*，從而推翻假設，證明算法1有效。

□

3 求解ICRPS的動態(tài)規(guī)劃算法

3.1 基本算法描述

哥哥茫然地不知道說什么。這時祖父進來了。看了翠姨的熱度，又感謝了我的母親，對我哥哥的降臨，感到榮幸。他說請我母親放心吧，翠姨的病馬上就會好的，好了就嫁過去。

因此，本節(jié)在算法1的基礎上，設計一種基于動態(tài)規(guī)劃求ICRPS可行解的算法2?？紤]到智能衛(wèi)星搭載的宇航級芯片的性能可達400 MIPS[16](今后還會變得更快)，則相比于傳送時延，其路由規(guī)劃的耗時可以忽略不計，所以衛(wèi)星將其規(guī)劃路由的具體時刻的NSSS作為靜態(tài)網(wǎng)絡處理而采用算法1推算其到目的衛(wèi)星的路由(算法2第6至7行)?？梢?，采用算法2求出的路由具有時間屬性，路由的每一段路徑都是前驅衛(wèi)星在其規(guī)劃路由時刻到后繼衛(wèi)星的最優(yōu)路徑，這種最優(yōu)是針對特定時刻的，不同的規(guī)劃時刻可能會得到不同的最優(yōu)路由。

算法2 求解ICRPS的動態(tài)規(guī)劃算法

3.2 面向數(shù)據(jù)分段傳送的算法擴展

受網(wǎng)絡協(xié)議等因素的限制，星間鏈路一次傳輸?shù)臄?shù)據(jù)長度往往是有限的，過大的數(shù)據(jù)將被拆分為若干數(shù)據(jù)子段以時分復用的方式分別傳送，而且兩次傳送之間還存在一個空時隙，所以衛(wèi)星在發(fā)送每一個數(shù)據(jù)子段時都必須重新規(guī)劃當前時刻的路由。

設需要一個長度為lT的數(shù)據(jù)從vb傳送到ve，星間鏈路一次傳輸?shù)淖畲髷?shù)據(jù)長度為lm?？紤]有l(wèi)T/lm=p，p+1,…,lr，則需要將原數(shù)據(jù)拆分為p+1個數(shù)據(jù)子段(若lr=0則拆分為p個數(shù)據(jù)子段)，前p個數(shù)據(jù)子段長度為lm，第p+1個數(shù)據(jù)子段長度為lr?；诖?，針對前述分段不連續(xù)傳送的情況將算法2擴展為算法3。

算法3 面向數(shù)據(jù)分段傳送的路由算法

4 ICRPS的仿真建模

4.1 智能衛(wèi)星Agent的行為模型

在ICRPS的仿真中，一個仿真時刻要同時處理多個智能衛(wèi)星諸如計算星間鏈路、收發(fā)數(shù)據(jù)、規(guī)劃路由等多種行為。為此，采用基于Agent的建模與仿真(Agent-Based Modeling and Simulation，ABMS)方法[17]，建立智能衛(wèi)星Agent(Smart Satellite Agent，SSA)模型，以刻畫智能衛(wèi)星的自主性與行為并發(fā)性。

在ICRPS仿真中，存在三種角色的SSA：源衛(wèi)星、目的衛(wèi)星、中轉衛(wèi)星。目的衛(wèi)星只要接收其他衛(wèi)星發(fā)送的數(shù)據(jù)即可。

圖1 源衛(wèi)星的行為流程Fig.1 Action process of source satellite

中轉衛(wèi)星vα的行為流程如圖2所示。中轉衛(wèi)星通過設置中轉任務列表(Transfer Task List，TTL)來處理多數(shù)據(jù)子段，每接收到一個數(shù)據(jù)子段便將其加入TTL中。TTL采用先進先出策略，若TTL非空，則調(diào)取排在第1位的數(shù)據(jù)子段為其規(guī)劃路由從而將其發(fā)送出去。

在圖2中，中轉衛(wèi)星也受規(guī)劃有效時間ΔT′的約束，如果超過ΔT′仍不能建鏈，則數(shù)據(jù)傳送中斷，需要生成傳送中斷信息，然后以本星為源衛(wèi)星、vb為目的衛(wèi)星，采用算法3規(guī)劃路由將傳送中斷信息反饋給vb，由vb根據(jù)任務時效性決定是否重新傳送。如果中轉衛(wèi)星收到其他衛(wèi)星發(fā)來的傳送中斷信息，將優(yōu)先處理這些信息。當然，傳送中斷信息也面臨傳送失敗的風險，必要時可以借助地面站來傳送。

圖2 中轉衛(wèi)星的行為流程Fig.2 Action process of relaying satellite

在Agent建模時，每一個SSA都被賦予上述三種角色的行為，在具體的仿真場景中各SSA根據(jù)自己被分配的角色而采取相應的行為。

4.2 ICRPS仿真的調(diào)度算法

算法4的關鍵是為SSA設置延遲。延遲是指實體停留在進程中的某一點不再向前移動，延遲結束時實體所在的位置就是復活點——進程繼續(xù)推進的起點。延遲分為兩類：無條件延遲是指預先確定延遲持續(xù)的時間，到時間后自動結束延遲；條件延遲是指事先無法確定何時結束延遲，必須等到滿足某些條件后進程才能繼續(xù)。例如空時隙屬于無條件延遲，TTL為空時屬于條件延遲。

5 仿真實驗與分析

5.1 實驗設計

選擇體系效能分析仿真(System-of-systems Effectiveness Analysis Simulation，SEAS)平臺來建立SSA模型，采用ABMS方法對ICRPS進行仿真實驗。

算法4 SSA仿真調(diào)度算法

表1 SSS類型

取γi,min=γj,min=20°，γi,max=γj,max=60°[18]，hI=120 km[19]，RE=6 378.137 km。數(shù)據(jù)長度為2 048 000 bit，設星間鏈路一次傳輸?shù)淖畲髷?shù)據(jù)長度為51 200 bit，即源衛(wèi)星需要分40次發(fā)送長度為51 200 bit的數(shù)據(jù)子段。衛(wèi)星發(fā)送數(shù)據(jù)的速率為100 kbit/s，空時隙為0.1 s，規(guī)劃有效時間ΔT′=1 min。仿真開始時刻為格林尼治時間2019年9月19日0時0分2秒，持續(xù)時間為2 min，步長為1 ms。

5.2 實驗結果分析

5.2.1 實驗結果分類

將ICRPS仿真實驗可能出現(xiàn)的結果劃分為圖3所示分類樹中實線框標識的7種類型，據(jù)此對10 620個實驗結果進行分類，如表2所示。

圖3 實驗結果的分類樹Fig.3 Classification tree of experiment results

可見，在相同的星間鏈路參數(shù)下不同SSS的實驗結果并不相同。中軌衛(wèi)星組成的SSS-3任意兩個成員之間的數(shù)據(jù)傳送都能夠正點連續(xù)完成，沒有任何推遲或中斷，因為中軌衛(wèi)星高度較大，姿態(tài)更加靈活，更易滿足建立星間鏈路的條件。

表2 實驗結果分類統(tǒng)計

SSS-1和SSS-2的實驗結果絕大多數(shù)都全程無通路，因為其中包含的低軌衛(wèi)星高度較低，很多情況下與其他低軌衛(wèi)星或中軌衛(wèi)星并不可見或無法通信，遂不能直接建鏈。事實上，在SSS-2中，甚至有20顆衛(wèi)星(編號為6、8、9、11、19、20、22、23、30、31、33、34、42、44、45、47、55、56、58、59)與其他所有成員在2 min內(nèi)都不能建鏈。

SSS-1的結果更能反映衛(wèi)星軌道對星間路由的影響：870次正點連續(xù)傳送都發(fā)生在中軌衛(wèi)星之間；55次推遲連續(xù)發(fā)送和14次傳送推遲后中斷都在低軌衛(wèi)星之間；2 601次全程無通路中沒有一次發(fā)生在中軌衛(wèi)星之間。

不過，圖3中的“無法建鏈”僅表示從仿真開始后1 min以內(nèi)無法建鏈，并不意味著衛(wèi)星對之間永遠不能建鏈，例如SSS-2的0號成員與3號成員在仿真開始后3.094 min才成功建鏈，超過了1 min的規(guī)劃有效時間。

上述結果都是基于5.1節(jié)中的星間鏈路參數(shù)取值，并不是所有軌道類型的衛(wèi)星在這些參數(shù)約束下都表現(xiàn)良好，hI、γi,min、γj,min、γi,max、γj,max、ΔT′等參數(shù)對低軌衛(wèi)星的建鏈及規(guī)劃結果的影響遠大于對中軌衛(wèi)星的影響。如何設置相關參數(shù)以避免出現(xiàn)數(shù)據(jù)傳送失敗及中斷是一個重要的問題，僅在路由算法層面是不足以解決的，需要對衛(wèi)星本身進行改進，例如增大衛(wèi)星天線掃描范圍[20]、衛(wèi)星姿態(tài)機動、改變衛(wèi)星星座構型甚至衛(wèi)星軌道。這種改進需要符合實際，不能為了追求高效能而隨意放寬約束。

5.2.2 路由跳數(shù)分布

10 620個實驗中有5 109個衛(wèi)星對完成全部40個數(shù)據(jù)子段的傳送，因每個數(shù)據(jù)子段都對應一個路由，共得到204 360個有效路由，這些路由跳數(shù)的分布如圖4所示。

(a) SSS-1

(b) SSS-2

(c) SSS-3圖4 有效路由跳數(shù)分布直方圖Fig.4 Histograms of normal routing hops

SSS-1和SSS-3的有效路由跳數(shù)分布在結構上相似，都是跳數(shù)為1和2的路由占絕大多數(shù)，在5.2.3節(jié)將介紹何時出現(xiàn)跳數(shù)為3的路由，而出現(xiàn)跳數(shù)大于1的路由則說明即使中軌衛(wèi)星之間也會有無法直接通信的情況。

SSS-2的有效路由則出現(xiàn)了1到11這幾種跳數(shù)，全部25 760個有效路由的跳數(shù)均值為3.683 54，跳數(shù)為1的路由只占14%。如前所述，低軌衛(wèi)星較難直接建鏈，所以SSS-2成員之間直接通信的占比明顯小于SSS-1和SSS-3，多數(shù)衛(wèi)星對的星間通信還需通過中轉衛(wèi)星來完成。

5.2.3 路由的改變

按衛(wèi)星對間傳送不同數(shù)據(jù)子段的路由是否有變化可以對圖3中的第2、3、5、6種結果類型分別進一步細分，如圖5所示。

基于圖5對表2中的部分實驗結果進行二次分類，其結果如表3所示。表3中3-2型和6-2型的結果都不為零，說明采用算法3能夠在星間通信中斷的情況下重新恢復路由；而表3中3-1列和6-1列的結果都為零則表明不存在傳送中斷后恢復但路由不變的情況，因為中斷前后的NSSS并不相同。

圖5 實驗結果的二次分類Fig.5 Further classifications of experiment results

表3 實驗結果的二次分類統(tǒng)計

表3中路由改變的實驗結果共計421個，它們的路由變化類型可以大致分為7種，如圖6所示。類型1、2、3(圖6中三者部分點線完全重合)見于SSS-1和SSS-3的中軌衛(wèi)星對路由的變化。圖4(a)和圖4(c)中所有跳數(shù)為3的數(shù)據(jù)子段路由都出現(xiàn)在類型1所代表的衛(wèi)星對路由中。類型3表示路由改變但跳數(shù)不變，僅見于跳數(shù)為2的路由。

圖6 路由變化類型Fig.6 Types of routing changes

類型4、5、6、7(圖6中類型6和類型7的部分點線完全重合)見于SSS-2的低軌衛(wèi)星對的路由變化，其跳數(shù)有的由大變小(類型5)，有的由小變大(類型6、7)，還有先增后減(類型4)。類型7是無中斷傳送的路由，其跳數(shù)變化幅度相對較小，而類型4、5、6都是中斷后恢復的路由，其跳數(shù)變化幅度較大。

圖7和圖8分別展示了上述7種變化路由及不變路由(類型8)的狹義時延和廣義時延。狹義時延是指發(fā)送時延與傳輸時延之和。廣義時延是指狹義時延加上其他形式的時延，主要有兩種：排隊時延是指數(shù)據(jù)為等待排在其之前的數(shù)據(jù)都發(fā)送完而耗費的時間；中斷時延是指數(shù)據(jù)等待中斷的星間鏈路恢復而耗費的時間。如圖7所示，狹義時延與跳數(shù)的變化趨勢幾乎一致，表明二者存在相關性。

圖7 典型路由的狹義時延Fig.7 Simple delays of typical routings

圖8 典型路由的廣義時延Fig.8 General delays of typical routings

廣義時延的變化如圖8所示，呈現(xiàn)以下規(guī)律：

1)數(shù)據(jù)子段1的廣義時延總等于狹義時延，此后隨著數(shù)據(jù)子段序號增大，其廣義時延一般會隨之遞增，因為越靠后的數(shù)據(jù)子段經(jīng)歷的排隊時延越大，如類型2、8；

2)規(guī)律1建立在所有數(shù)據(jù)子段路由的前兩個衛(wèi)星(即源衛(wèi)星及其后繼衛(wèi)星)都相同的前提下，若源衛(wèi)星的后繼衛(wèi)星改變，則排隊時延將從頭算起，就會出現(xiàn)類型1、3所示的廣義時延起伏變化的情況(圖8中類型1的部分點線被類型2、3遮擋)；

3)相比于無中斷傳送時跳數(shù)增加對廣義時延的影響(類型7)，中斷時延對廣義時延的影響程度更大，類型4、5、6的路由中斷時延甚至超過了一些數(shù)據(jù)子段的廣義時延。

路由變化的原因可以分為兩類：

1)數(shù)據(jù)連續(xù)傳送中存在時延更短的路由：包括類型1中跳數(shù)由3變?yōu)?、類型3中跳數(shù)由9變?yōu)?，及類型2的路由變化；

2)原星間鏈路失效，重新規(guī)劃路由：包括類型2、5、6、7，及類型1中跳數(shù)由2變?yōu)?、類型3中跳數(shù)由6變?yōu)?1。

不過，類型5所示的路由變化表明，原因2導致的路由變化并不必然使狹義時延增大，時延變短的路由變化也不一定是原因1造成的。

6 結論

本文在提出求解ICRPS的動態(tài)規(guī)劃算法的基礎上，結合智能衛(wèi)星所特有的自主性，將智能衛(wèi)星建模為Agent，并為基于智能衛(wèi)星Agent的ICRPS仿真設計了調(diào)度算法。借助SEAS平臺對三種SSS內(nèi)部成員之間的路由進行了仿真實驗，實驗結果表明，本文研究的算法可以有效解決不同SSS下的路由問題。不過，對實驗結果分析發(fā)現(xiàn)，路由規(guī)劃的結果受到SSS體系架構和硬件層面因素的深刻影響，如SSS星座構型和衛(wèi)星軌道，以及星間鏈路的數(shù)據(jù)傳輸能力等，如何優(yōu)化這些因素以提升SSS的效能將是今后的重要研究方向。