一種基于計算資源度的星間路由協議

蘇安,劉乃金,*,陳清霞,向雪霜,劉佳

1.錢學森空間技術實驗室,北京 100094 2.航天東方紅衛星有限公司,北京 100094

1 引言

近年來,隨著低軌衛星與5G(第五代移動通信,the fifth generation of mobile communications system)的火熱發展,衛星互聯網(IoSat,Internet of Satellite)逐漸成為空間網絡的新范式,如圖1所示[1,2]。衛星互聯網中的一個重要因素是路由協議,由于衛星動態、鏈路中斷和按需組網這類特殊行為的存在,傳統的地面網絡模型不能完全適用于衛星互聯網[3-5]。

圖1 衛星互聯網示意

隨著用戶需求與任務復雜度的不斷增加,單個衛星節點的能力和資源逐漸達到飽和態,已不能滿足日益增長的任務要求。例如,遙感產品生產節點可提供的能力對任務調度有著重大影響,其中,服務能力的指標通常有:CPU計算能力、內存剩余容量、當前節點任務狀態等。根據衛星中心報告,中國14顆中高分辨率光學衛星月產數據量將近PByte級別,即單星已達日產GByte級別,但中國目前要實現單星在軌實時圖像處理難度較大[6]。目前,現有大多數衛星均采用彎管方式進行數據傳輸,大量遙感數據還需要被卸載到處理能力強的地面站中,由算力資源強的地面中心提供集中式計算服務。上述方法通信開銷大、計算時延高,難以應對時延敏感類型業務。因此,面向未來海量數據的快速處理需求,星間協同計算不僅能顯著提升計算時效性,而且能大大降低地面站計算模式帶來的通信成本。

隨著“東數西算”等國家戰略部署的推進,計算和網絡的融合成為趨勢。在算力網絡的初步探索中,形成了由算力服務層、算力資源層、算力路由層、網絡資源層和算網編排管理層的新型算力感知架構。而算力路由是算力網絡中的關鍵技術,依據對網絡、計算、存儲等多種資源和服務的感知,將算力信息加入到“計算+網絡”這類范式的新型路由表中。最終實現感知業務請求,以及網絡和計算的聯合路由計算,按需實現業務調度策略[7-9]。在衛星互聯網的發展中,星載計算資源作為提供服務的主要載體,具備數量大、分布廣、異構等特點,面向當前日益繁多的空間計算資源,結合“計算+網絡”的架構思維,實現星載算力資源的靈活調用、協同處理,滿足衛星互聯網應用的需求[10,11]。

2 相關工作

關于“在網絡層構建算力信息感知的路由算法,實現利用多星提升協同計算效能”的早期研究中,為構建穩定的拓撲結構進行組網,相關學者基于衛星運行周期的路由算法本質上依靠衛星周期性運行的特點,將運行周期劃分為離散時間片,并在時間片內建立靜態拓撲結構,以達到網絡層與衛星星座動態隔離的目的[12,13]。這類算法提供了解決衛星高動態性對網絡拓撲影響的解決思路,但難以支持星上時延敏感型任務卸載與處理。針對衛星動態性問題,有學者提出基于網絡中節點實時獲取的拓撲信息構建分布式路由算法,這類算法雖然提高了鏈路利用率,但存在算法復雜度高,難以在星上實現等劣勢[14-17]。針對算法復雜度問題,Jia Min等人將SDN思想與LEO單軌道衛星網絡相結合,基于SDN的深度優先搜索和Dijkstra算法提升計算效率和計算結果可靠性,突破了傳統衛星網絡架構的性能限制[18]。Yang等人設計了具有收斂能力的路由協議和采用TDMA控制的鏈路層協議,通過仿真表明該方法適用于微納衛星星座場景[19]。但上述研究依舊未對算力信息進行充分考量。

也有學者提出將衛星網絡建模為移動自組織網絡(MANET)來解決時延敏感型任務中低軌衛星高移動性的影響[20-21]。其中優化鏈路狀態路由協議(optimized link state routing,OLSR)作為移動自組織網絡中的一種典型主動式路由協議,該協議的主要優勢在于網絡中每個節點都可以利用MPR(multipoint relay)機制定期檢索網絡狀態來估計當前拓撲(如圖2所示)。此類研究的思路是根據不同的組網環境與要求,提出協議變體來滿足組網需求。主要表現在針對能量、帶寬、鏈路穩定性和QoS需求等不同指標來改進MPR選擇算法和路由選擇算法[22]。Yan等人從OLSR出發提出了基于鏈路穩定性的Sat-OLSR協議,通過在選舉和路由算法中添加鏈路穩定度來適應衛星場景的高動態性[23]。其中,Huang等人在研究中從鏈路持續時間出發,利用節點的三維態勢信息來預測鏈路存在的時長,從而在不增加節點數量的情況下提升了算法的分組投遞率并且降低了時延[24]。Ali Moussaoui等人在研究中提出了兩個新指標:節點穩定性和節點的保真度來選舉穩定的MPR節點和拓撲,并且保證了相關QoS指標[25]。上述研究雖然解決了移動性問題,但針對衛星網絡中鄰近網絡節點的算力信息利用率尚淺。

圖2 有無MPRs選擇泛洪對比

綜上所述,現有文章對于計算資源與衛星動態性聯合考慮的研究較少,本文基于移動自組織網絡中OLSR協議,通過引入計算資源度和鏈路生存時間,提出了一種多資源度考量的星間路由協議。

3 系統模型

3.1 網絡模型

在本節中將介紹所考慮的網絡模型。單層LEO衛星網絡由多個軌道高度相同,軌道傾角不同的Walker-Delta星座組成,衛星網絡用有權無向圖G(S,E)表示,其中S={s1,s2,…sN}表示衛星節點集合,E={lij|?i∈S,?j∈S}。每個衛星維護四條星間鏈路,分別為同軌道的兩條,以及相鄰軌道的兩條。任務卸載模型如圖3所示,在低軌衛星中存在不同計算資源度的衛星。衛星節點隨機產生/獲取空間任務,以產生任務的衛星節點為任務發起節點。計算任務請求從任務發起節點到地面站傳輸路徑中,如果傳輸路徑的中間衛星節點能滿足計算需求,則直接在中間節點完成計算。

圖3 任務卸載模型

文章提出的基于計算資源感知的星間路由協議,就是面向計算任務請求,尋找一條或多條高計算資源度的卸載路徑,提升計算卸載的概率,從而降低任務完成時延,提升服務質量。

3.2 計算資源度評估模型

計算資源度考慮指標有:

1)CPU計算能力:可記為Capi單位為cycles/s,主要由CPU數量,CPU核心數以及CPU主頻來評估。

2)內存容量:可記為Memi,單位為MByte。

3)節點負載狀況:可由下式表征:

(1)

Taski,Tasktotal分別代表當前節點在規定時間j尚未完成的任務數量和需要完成的總任務數量。根據綜合負載冗余率的計算方法,加入計算資源度后,量化節點計算能力的公式為:

Scomputing=α1×(0.95-OC)×Capi+

α2×(0.95-OM)×Memi-α3×Load

(2)

式中:OC、OM分別代表CPU和內存此時的占用率,并且設置95%為CPU和內存利用率的閾值。在獲取CPU、內存占用率時,為避免出現瞬時高峰,此處占用率值取3s內的一個平均值。系數α1,α2,α3是根據CPU、內存和負載程度,對節點參加任務卸載以及對計算資源度的影響而在系統初始化時給定的權重值。其中α1+α2+α3=1。

3.3 任務計算時延模型

衛星si需要計算的子任務集群Ω={T1,T2,…Tj},式中Tj∈Ω(j

(3)

式中:Bs代表星間信道可用帶寬;N0代表背景高斯白噪聲;Pr代表卸載任務時發射功率,并可由下式[26]表達。

(4)

式中:Pt,Gt,Gr代表信號發射功率、信號發射增益系數和信號接收增益系數;R為發射端和接收端距離;λ為載波波長。

所以,任務計算時延在一跳內可由下式[27]表示:

(5)

(6)

式中:n為從任務發起星到最終完成星間協同計算卸載所需的跳數。

4 基于計算資源度的路由協議

為提高星間協同計算效能,提出了在OLSR協議的基礎上,通過修改包格式、MPR選擇算法和路由更新算法,設計基于計算資源感知的星間路由協議。通過該路由協議可為任務請求尋找一條或多條高計算資源度的卸載路徑,從而降低任務完成時延,提升服務質量。

在OLSR協議中,HELLO包的Willingness字段用來表示節點參與MPR節點選取的意愿。Willingness字段的取值(記為wo)范圍是從0到7的整數,其中wo= 0表示從不參選MPR,wo=7表示總是選為MPR。在原版協議中,大多數節點處于default狀態,即wo= 3。TC包的ANSN字段代表通告的鄰居序列號,每當節點檢測到其通告的鄰居集合中的變化時,該序列號遞增。Advertised Neighbor Address字段包含鄰居節點的主地址,始發節點的通告鄰居的所有主地址都放在TC消息中。

OLSR基本工作流程如圖4所示,節點會定期通過HELLO消息的泛洪感知周圍節點信息,并且根據HELLO消息的更新而更新鄰居表,并以此為基礎進行MPR選擇算法。節點在執行MPR選擇算法后,根據TC消息定期更新拓撲表,通過節點拓撲表信息,逐步計算路由表。

圖4 OLSR協議工作流程

4.1 包格式修改

文中提出的路由協議,首先基于標準化的HELLO包和TC包,分別在包頭字段和包內字段中引入了計算資源度(computing resource degree),并在HELLO包的保留字段中加入了CPU可用率和內存可用率兩個字段,因此節點的計算資源相關信息就會隨著HELLO包泛洪至相鄰節點,具體HELLO包修改字段具體如圖5加深顏色部分所示。對于標準的TC包,包內字段原為鄰居節點信息,現將鄰居節點所對應的計算資源度加入包內字段,使得節點與節點所對應的計算資源度可以通過TC包的轉發而使鄰居節點得知,進而為之后的路由計算提供支撐。TC包修改字段具體如圖6加深顏色部分所示。

圖5 HELLO包格式

圖6 TC包格式

4.2 MPR節點選擇算法

文中提出的路由協議,基于原有的Willingness 字段,結合計算資源度參數,綜合計算MPR 節點選擇意愿值fcom[28]:

(7)

式中:wo為Willingness字段值;ws為計算資源度Scomputing歸一化為1至7后的整數。在MPR選擇算法中,根據式(7)計算出各個節點的最終意愿值fcom后,優先選擇fcom的節點作為MPR,其次選擇兩跳節點唯一可達的一跳節點作為MPR。具體步驟如算法1所示。

算法1.MPR選擇算法

輸入:N1(j),N2(j)

輸出:MPR集合M(j)

1:計算N1(j)和N2(j)的連接度D(y);

2:計算N1(j)and N2(j)的計算資源度S(y);

3:首先將 N1(j)中意愿值fcom=7的一跳節點加入M(j)中;

4:while1

將N1(j)中唯一連接兩跳節點的一跳節點加入M(j)中并將該兩跳節點從N2(j)中刪除;

5: while N2(j)非空Do

將剩余兩跳節點所連接一跳節點中有最大

D(y)的節點加入M(j)中;

6: if多個一跳節點D(y)相同

將其中具有最大S(y)值的一跳節點加入

到M(j)中;并將該一跳節點所覆蓋的兩

跳節點從N2(j)中刪除

7: end if

8: until N2(j)為空

9: end while

10:end while

算法1中,N1為任務發起節點的一跳鄰居集合、N2為任務發起節點的兩跳鄰居集合、M代表MPR節點集合、D代表經一跳節點可到達兩跳節點的數量(即連接度)、S代表上文定義的節點計算資源度。

4.3 路由表更新算法

路由表是根據鄰居表(一跳和兩跳鄰居)和拓撲表的信息計算出來的。為了避免對已經接收和處理的消息重新處理,每個節點需要維護一個Duplicate Set(重復集),該集合由多個Duplicate Tuple(D_ADDR,D_SEQ_NUM,D_RETRANSMITTED,D_IFACE_LIST,D_TIME)組成,其中,D_ADDR是消息的發起者地址,D_SEQ_NUM是消息的消息序列號,D_RETRANSMITTED是指示消息是否已被重傳的布爾值,D_IFACE_LIST是已在其上接收消息的接口的地址列表,D_TIME指定元組到期和必須被刪除的時間。為建立拓撲表,MPR節點負責周期性廣播拓撲控制(TC)包,在提出的路由協議更新算法中,TC包在遵循原生協議中的默認轉發的前提下,會記錄每條鏈路的計算資源度,如圖7所示。

圖7 TC包轉發流程

在OLSR協議中,使用最短路徑算法(Dijkstras算法)來尋找超過兩跳的路徑。為了在路徑選擇中引入計算資源度而不只是連接度,提出了Djikstras 算法的修改版本來在拓撲表的所有節點對(MPR 節點)之間找到可以滿足“邊傳邊算”的節點。具體步驟如算法2所示。

算法2.路由表計算

輸入:一跳鄰居表,兩跳鄰居表,拓撲表

輸出:路由表

1:刪除路由表中原有條目

2:以對稱鄰居(h=1)作為目標節點開始添加新的路由條目,目的地址和下一跳地址均為鄰居地址地址。

3:查找路由表中跳數h最小且計算資源度權值最大的目的節點A,此時在拓撲表中查找通過A是否能到達其他節點B,一旦發現則建立新的路由表項,將新的路由表項中的目的節點設置為B,將下一跳地址設置為A,并將跳數距離設為h+1,并更新新的累計計算資源度。

4:重復步驟3,直到所有節點遍歷完成,無新節點加入路由表項。

END

5 仿真結果

為了評估提出方案的效率,本節首先對提出的MPR改進算法與原生協議進行對比;然后,對星間協作計算和卸載到地面計算的業務處理時延進行對比;最后,對比在不同算力情況下對于業務的承載能力。仿真參數如表1所示。

表1 仿真參數表

fi,s,fi,g代表衛星與地面段的計算頻率。

5.1 MPR選擇算法改進效果

文中提出的路由協議,首先基于標準化的HELLO包和TC包,分別在包頭字段和包內字段中引入了計算資源度(Computing Resource Degree),并在HELLO包的保留字段中加入了CPU可用率和內存可用率兩個字段,因此節點的計算資源相關信息就會隨著HELLO包泛洪至相鄰節點,具體HELLO包修改字段如圖6所示。

圖8顯示了標準MPR選擇算法和所提出的MPR選擇算法的性能對比。為了提升數據的可信性,在不同組網規模中都經過大量次數仿真,并對數據取均值。結果表明,在所提出的衛星模型下,文中提出的MPR選擇改進算法比標準MPR選擇算法和在減少泛洪節點數量上有一定的優勢,這是因為其在選擇作為泛洪的節點時引入了連接度的概念來減少冗余,而文中MPR選擇算法過程在此基礎上引入了評估計算資源度進一步根據需求去除冗余。可以看到,隨著組網規模的增大

圖8 MPR改進算法效果圖

圖9 任務處理時延與跳數變化關系

5.2 任務處理時延與跳數變化關系

仿真結果如下,本節針對傳輸跳數對任務處理時延的影響作出分析。隨著任務在星間傳輸跳數的增長,地面云計算和星間協同計算的任務處理時延總體呈上升趨勢。由于地面云計算需要將任務卸載至地面,因此隨著跳數的增長,星間鏈路的傳輸時延與傳播時延是影響地面云計算方案的主要因素。當從任務發起星卸載到地面所需要的傳輸跳數為2～8跳時,地面云計算性能要優于星間協同計算。首先,在將任務下行至地面的跳數小于完成星間協同計算的跳數的情況下,地面云計算有更小的傳輸時延,且在地面云服務器高算力支持下,任務計算時延更小;其次,星間協同計算需要根據周邊衛星節點所能提供的服務情況,決定卸載任務所需的跳數,通常,周邊衛星節點所能提供更高的算力支撐時,所需的跳數越小。

當卸載任務所需跳數進一步加大時(意味著任務發起星距離目的地面站更遠時),星間協同計算開始體現優勢。隨著跳數的增加,星間協同計算可以在任務尚未卸載至地面時,完成任務的計算。如圖所示,在給定條件下,星間協同計算的傳輸時延和計算時延分別穩定在80ms和120ms左右。但此時,隨著傳播跳數的增大,地面云計算所需的傳輸時延以接近每跳增加20ms的速率增大。因此,在任務發起星有足夠的跳數來發現周圍可完成任務卸載的節點時,星間協同計算方案更優。

5.3 星間協同計算與地面云計算任務處理時延性能對比分析

仿真結果如圖10所示,星間協同計算的任務處理時延性能優于地面云計算。一方面,隨著任務數據量的增大,由于星間多跳傳輸和星地長距離鏈路的傳輸,地面云計算傳輸時延顯著增加,并且占據任務處理時延中88%的時間;另一方面,在低任務數據量時,地面云計算的高算力性能可以彌補數據傳輸帶來的時延差距,但隨著數據量的增大,這種差距逐漸增大,具體體現在計算時延的增速在26ms/MByte,而傳輸時延增速在66ms/MByte。由圖可知,當數據量從0MByte增至5MByte時,星間協同計算任務處理性能提升效果從31.541%逐漸降低至15%左右,這是因為在設計的網絡中,單個衛星節點所能提供最大的算力僅能完成任務的20%,即單個衛星承擔卸載任務的能力會影響星間協同計算的性能。綜上,星間協同計算相比于地面云計算更容易滿足低時延需求的業務。

圖10 星間協同計算和地面云計算任務處理時延對比

5.4 多種卸載策略算法試驗性能比較

本小節比較本文所提出基于計算資源度的星間卸載算法(ISOA-CRD,inter satellite offloading algorithm based on computing resource degree)與加權輪轉算法(WRR)和隨機動態算法(Pick-KX)的時延性能,仿真結果如圖11所示。

圖11 多種算法時延性能對比

如圖可知:當任務數據量小于1.5MByte時,各算法差異并不明顯;當任務數據量大于2MByte時,隨著任務數據量的增加,本文提出的算法的時延明顯低于其他3種算法。例如:在仿真中當數據量達到5MByte時,本文所提出的算法時延為380ms,相較于WRR 算法(754.08ms)降低了49.6%、Pick-KX算法(670.72ms)降低了43.3%。

這是因為WRR算法根據衛星的計算性能強弱來進行映射,但由于不考慮網絡中拓撲關系,因此對高并發的任務響應性能較差;Pick-KX雖然隨機地將任務卸載至鄰近衛星,但由于其并不考慮鄰近衛星計算性能,所以也有一定的局限。本文所提出的基于計算資源度的卸載策略綜合考慮了節點計算能力與網絡拓撲關系,因此可以有效的降低任務處理時延。

6 結論

傳統組網協議存在無法感知鄰居節點算力資源情況的問題,難以做到高效、系統性和快速地完成卸載任務。文中提出了一種基于計算資源度的星間路由協議,通過引入節點計算資源度來感知周邊組網節點的算力、CPU、內存和負載等情況,并且根據該參數修改MPR選擇算法與路由表更新算法。通過仿真評估,所提算法在組網節點泛洪和任務計算時延方面有一定優勢。后續的研究工作將進一步豐富衛星組網場景,考慮高動態鏈路對于協議的影響。