空間延遲/中斷容忍網絡的接觸圖路由研究綜述?

徐 雙,王興偉,黃 敏,張琳琳

1(東北大學 計算機科學與工程學院,遼寧 沈陽 110169)

2(東北大學 信息科學與工程學院,遼寧 沈陽 110819)

空間通信和組網技術的發展,為空間探索技術的發展開啟了新紀元[1].早期空間通信大多采用地球同步軌道(geo-synchronous orbit)衛星,利用彎管通信技術實現數據中繼轉發和廣播,難以完成連續的信息捕捉和傳輸[2].星上計算和處理能力的提高以及星際鏈路通信技術的發展,為空間通信和組網提供了重要的技術支撐[3].衛星通信具有覆蓋范圍廣、通信距離遠、傳輸容量大、對地面環境依賴性低等特點[4],在防災救災、緊急救援、全球導航定位、空間遙測等任務中發揮著重要作用[5].然而,衛星通信系統主要需要應對如下困難:(1)遠距離傳輸造成的長傳輸延遲;(2)通信鏈路易受干擾造成的高誤碼率;(3)復雜的空間環境以及節點移動造成的鏈路中斷;(4)特定于供應商的網絡基礎設施造成的網絡協議標準難以統一,特別是由此導致的網絡異構性;(5)星上設備存儲和處理能力有限,特別是維修困難[6].隨著空間通信需求的不斷增長,實現空間設備間類似于Internet的通信變得越來越重要[7].

延遲/中斷容忍網絡(delay/disruption tolerant network,簡稱 DTN)最初是由美國噴氣推進實驗室(Jet Propulsion Laboratory,簡稱JPL)為開發行星際互聯網(interplanetary Internet,簡稱IPN)而提出的一種網絡體系架構[8],后被廣泛應用于軍事作戰網絡、稀疏傳感網絡等地面網絡.DTN也是構建衛星網絡的可選方案[9],尤其是滿足低地球軌道星座系統間歇性連接的需要[10].DTN在傳輸層與應用層之間引入疊加層(overlay)[11],采用消息的“存儲-攜帶-轉發(store-carry-forward)”機制解決網絡中的間歇性連接、長傳輸延遲、高誤碼率等問題,適用于通信受延遲、帶寬、誤碼等嚴重影響的空間網絡[9].束協議(bundle protocol,簡稱BP)作為DTN協議的重要組成部分,提供了保管傳輸(custody transfer)、主動和被動式束分片(proactive and reactive bundle fragmentation)、滯后綁定(late binding)這些重要功能,為DTN網絡的實施提供了可能性[12].在BP中,采用束作為傳輸數據的基本單元,并通過匯聚層適配器實現與TCP、UDP、LTP(licklider transmission protocol)、藍牙等不同協議之間的匹配,從而使DTN能夠解決異構網絡互聯中存在的問題.

路由是 DTN必備的基本功能,旨在提高束的交付率并降低交付延遲[13].通常,路由是指路徑上的每個節點選擇最優相鄰節點轉發數據的復雜過程.Internet網絡主機在分發數據前,根據當前網絡拓撲和節點間連接信息計算最優的包轉發路徑,而DTN所采用的網絡狀態信息中還需包含接觸傳輸速率、節點存儲容量等.由于網絡狀態信息可能隨時間推移而變化,網絡轉發節點需要根據當前可用的網絡狀態信息判斷是否需要重新計算轉發路徑或仍沿先前路徑繼續轉發數據.Internet網絡狀態信息變化可被迅速地傳播,因此每個節點掌握的當前網絡狀態幾乎都是準確、一致的.而DTN連接具有間歇性,且信號傳播時延長,所以網絡狀態信息的一致性維護困難,網絡狀態信息具有滯后性.此外,數據包在轉發到相鄰節點前,可能需要長時間存儲在當前節點.

在機會性DTN(opportunistic DTN)中,節點具有移動性,節點間的接觸具有隨機性[14].因此,基于洪泛和概率的路由算法被廣泛應用在機會性DTN中[15-17].空間DTN節點彼此之間不斷相對運動,節點位置不斷變化,但節點運動軌跡的數學模型可預先建立,從而準確地計算出節點間的接觸機會[18],這類網絡被稱為確定性 DTN(deterministic DTN)[13].關于確定性DTN的路由分析研究工作可追溯到2003年,文獻[19]提出了采用時間演化圖表示網絡拓撲變化來研究最小成本路徑.2004年,文獻[20]根據節點運動的可預知性,提出了一個時空路由(space-time routing)框架,為每個節點構建由每個時隙間隔內的下一跳組成的時空路由表,給出了基于時空圖模型的路由算法.然而,上述兩種靜態路由算法依賴于地面上預計算的完整路徑以及分配這些路徑到網絡節點的及時性,缺乏對變化業務流和拓撲的響應.為解決上述問題,2008年,Burleigh提出了分布式的接觸圖路由(contact graph routing,簡稱CGR)算法.該算法利用網絡接觸的可預知性,采用啟發式算法動態計算出多條路徑,為空間DTN提供了一種有效的路由方案[21].文獻[22,23]評估了CGR、Epidemic和Prophet在空間DTN中的性能并指出,在拓撲信息可預知的空間網絡中,CGR具有較小的延遲和緩存消耗.此外,CGR已被多次成功地應用于 DTN的空間實測實驗[24].目前,CGR白皮書已被提交到國際空間數據系統咨詢委員會(Consultative Committee for Space Data Systems,簡稱 CCSDS)進行標準化,并重新標記為“調度感知束路由(schedule-aware bundle routing,簡稱 SABR)”[25].

本文第1節描述CGR的基本原理、相關術語和算法過程.第2節分析和總結CGR存在的問題和相應的改進方法.第3節介紹CGR的工程應用.第4節對比評估CGR算法在多層衛星網絡中的性能.第5節總結全文,對未來的研究方向進行展望.

1 CGR

1.1 基本原理

CGR是一種分布式路徑計算方法,路徑上的每個節點一旦接收到束,則重新計算到達該束的目的節點的最佳路徑,從而確定當前節點的下一跳節點[26].CGR假定:(1)網絡具有拓撲預計算能力;(2)網絡中的每個節點能夠及時而準確地獲知全局網絡接觸信息和本地隊列占用情況;(3)網絡拓撲的變化頻率低于網絡節點配置信息的同步頻率[27];(4)不可預知的拓撲變化發生頻率低,節點失效彼此獨立發生[28].可預知的網絡拓撲變化作為節點配置信息,可以提前分發到網絡中的每個節點,而對于不可預知的拓撲變化,CGR依賴于網絡管理功能來更新被影響節點的配置.

接觸(contact)是指兩個 DTN節點之間建立通信鏈路的機會,由拓撲間隔內的所有可行接觸組成的時序列表稱為接觸計劃(contact plan,簡稱CP)[29].接觸計劃采用接觸消息(contact message)和范圍消息(range message)兩種類型的接觸計劃消息(contact plan message)表示[21,30].其中,接觸消息包含接觸的起始時刻、結束時刻、發送節點、接收節點和數據傳輸速率(B/s);范圍消息包含接觸的起始時刻、結束時刻、發送節點、接收節點、發送節點與接收節點間的距離(<1光秒).根據接觸計劃,每個節點可以在本地構建以任意其他節點為目的節點的有向無環圖,即接觸圖(contact graph),接觸圖的頂點對應于接觸,邊對應于束在節點上的存儲.接觸圖可用以下兩個鏈表表示:由所有以目的節點為接收節點的接觸消息派生出來的xmit對象鏈表,該鏈表封裝了接觸的起始時刻、結束時刻、發送節點和數據傳輸速率,鏈表中的對象根據接觸的結束時刻排序;由范圍消息得出的origin對象鏈表,該鏈表封裝了發送節點以及發送節點與目的節點間的當前距離.

圖1是一個由4個衛星節點組成的空間DTN網絡,節點A發送數據到節點D;表1是該網絡對應的接觸計劃,其中的每個表項描述兩節點之間接觸的起止時刻和數據傳輸速率[31].以表1中的接觸計劃為例,構建從節點A到節點D的接觸圖,結果如圖2所示[26].圖中添加了兩個概念頂點(notional vertice),分別為圖中的根頂點和終端頂點.前者表示從節點A到A的接觸,而后者表示從節點D到D的接觸,圖中其他頂點均為表1中有助于節點A發送數據到節點D的接觸.在圖2中進行路徑搜索,構建從發送節點A到目的節點D的路由列表(route list)[32].每次搜索都找出從根頂點開始到終端頂點結束的最低成本路徑,并將搜索到的路徑添加到節點的路由列表中.在進行下一次搜索之前,從接觸圖中刪除本次搜索到的路徑的初始接觸.重復以上過程,直到搜索不到路徑為止.從圖2中可以看出,從A到D共有3條可用路徑.

Fig.1 DTN network topology圖1 DTN網絡拓撲

Table 1 Contact plan list表1 接觸計劃列表

Fig.2 Contact graph from nodeAtoD圖2 從A到D的接觸圖

基于接觸圖的路由工作流程由接觸計劃生成、接觸計劃分發和路由計算這3個階段構成,如圖3所示[26].

Fig.3 Contact plan generation,distribution and utilization圖3 接觸計劃的生成、分發和利用

由于接觸計劃依賴于特定的網絡和通信平臺,因此將接觸計劃的生成過程從路由應用中解耦出來.在初始階段,空間任務操控中心根據網絡節點的通信系統屬性(如傳輸功率、調制機制、誤比特率、天線輻射方向等)和節點的軌道動力學特性(如位置、姿態等)確定接觸的可行性,構造接觸計劃[33];然后,由地面站將接觸計劃分發到網絡中的每個節點;最后,節點調用CGR,根據已知的接觸計劃生成到達目的節點的有效路徑.

1.2 相關術語

本節給出CGR相關術語的定義和計算公式,并在表2中列出本文中使用的變量符號及含義.

Table 2 Variable notations and definition表2 變量符號及含義

(1)合格路徑(well-formed routes):構成從源節點到目的節點的端到端路徑的接觸序列,該序列的第1個接觸為源節點與其相鄰節點間的接觸,后續接觸是前一個接觸的接收節點與其相鄰節點間的接觸,而最后一個接觸是以接收節點為目的節點的接觸.該路徑中不存在環路,即不存在兩個接觸的發送節點或接收節點相同的情況.

(2)失效時刻(expiration time):束的創建時刻與其生存時間(time-to-live)之和,即.

(3)單向光行時邊界(one-way light time(OWLT)margin):OWLT是光在兩節點間傳輸所需的時間,指代距離.OWLT邊界是束在任意兩節點間傳播時,節點間OWLT變化的最大增量.假設網絡中任意兩節點間距離變化的最大速率約為 67km/s,則初始距離為K光秒的兩節點間每秒增加的最大距離為67km.因此,數據從發送節點傳輸到接收節點所需的傳播時間不會超過(K+Q)s,其中,Q=(67×K)/30000.

(4)最后時刻(last moment):接觸發送束的最晚時刻,即保證束在截止時刻Tdeadline之前到達接收節點的最晚發送時刻.如果接觸的起始時刻在最后時刻之后,則該接觸的接收節點無法在之前接收到束.

(5)容量(capacity):接觸的數據傳輸速率與其持續時間的乘積,即

(6)估計容量消耗(estimated capacity consumption):假設匯聚層采用UDP/IP協議,則每個幀的開銷為100字節.每幀中可封裝的束的字節數等于幀的大小減去每幀的開銷.例如,Internet的最大傳輸單元大小為1 500字節,則每幀中束的最大字節數為1400=(1500-100).傳輸給定大小的束所需的幀數等于束的大小除以每幀中束的最大字節數的商向上取整.束的總開銷為每個幀的開銷乘以傳輸該束所需的幀數.束的估計容量消耗為束的大小與總開銷之和,即

(7)剩余容量(residual capacity):本地節點與鄰居節點間給定接觸的剩余容量是兩節點間不晚于給定接觸調度的所有接觸的容量之和減去優先級不低于發送束的所有待傳輸束的估計容量消耗之和,即

(8)可用機會(plausible opportunity):剩余容量不小于發送束的估計容量消耗的接觸.

(9)可用路徑(plausible route):由可用傳輸機會組成的合格路徑,且路徑上每個接觸開始傳輸束的時刻先于最后時刻.最后一個接觸的截止時刻為束的失效時刻,而其余每個接觸的截止時刻為每個接觸的結束時刻.

(10)收回時刻(forfeit time):可用路徑上所有接觸的最早結束時刻.

(11)網絡距離(network distance):可用路徑的網絡距離是指束沿著該路徑從源節點轉發到目的節點所經過的中間節點數,即跳數.

(12)被排除的相鄰節點(excluded neighbor):本地節點的相鄰節點中拒絕托管發送到給定目的節點的束的相鄰節點.

(13)關鍵束(critical bundles):必須且應盡快投遞到目的節點的束.關鍵束將被插入到所有可用路徑對應的輸出隊列中,而非關鍵束僅被插入到所有可用路徑中收回時刻最早的路徑所對應的輸出隊列中.

(14)轉發延遲(forwarding latency):節點接收、排隊以及發送束所用的時間,使用束大小的2倍除以接觸的數據發送速率估算,即.

1.3 算法過程

CGR利用可預知的接觸計劃消息獲取網絡拓撲,不需要預測或發現過程[34].CGR的處理過程如圖4所示.首先,節點根據接收到的接觸消息和范圍消息生成接觸圖;之后,執行接觸檢查過程(contact review procedure,簡稱CRP),根據生成的接觸圖計算出可用來轉發束的相鄰節點列表;最后,通過轉發決策過程(forwarding decision procedure,簡稱FDP)選擇下一跳節點.

Fig.4 Three processing steps of CGR algorithm圖4 CGR算法的3個處理步驟

接觸圖構建完成后,節點通過CGR-CRP過程和CGR-FDP過程實現路徑計算與束轉發的流程如下.

輸入:B,CP.

輸出:將B插入到相應的輸出隊列.

算法的第2行～第39行是節點根據接觸計劃執行路徑計算的過程.

· 第2行將每次迭代的目的節點加入到被排除的相鄰節點集合中,以防止路由環路的產生.

· 第4行～第6行計算通過每個接觸發送束的最晚時刻:如果該時刻早于當前時刻或接觸的起始時刻,則跳過此接觸.

· 第8行～第11行表示當前目的節點為束的目的節點時,更新路徑收回時間;當接觸的發送節點為本地節點時,計算束的估計容量消耗和接觸剩余容量.

· 第14行～第 23行是當接觸剩余容量大于束的估計容量消耗時,判斷當前目的節點與本地節點的相鄰節點間的從屬關系以及路徑收回時間與束的投遞時間的大小關系,決定是否更新束的交付時間、路徑距離和路徑列表.

· 第28行～第 34行是當接觸的發送節點既不是本地節點也不是排除節點時,更新路徑收回時刻、當前目的節點、路徑網絡距離等,并遞歸調用CGR-CRP過程.

算法的第40行～第50行是根據束的重要性將其插入到輸出隊列的過程,其中,第41行、第42行表示束是關鍵束時,將其復制并插入到本地節點的所有可用相鄰節點對應的輸出隊列中;第 44行、第 45行表示束是普通束時,從本地節點的所有可用相鄰節點中選出最早收回的相鄰節點,將束插入到該節點所對應的輸出隊列中.

2 CGR的改進

自2008年CGR首次提出以來,很多研究都致力于CGR的功能完善和應用.圖5是CGR的發展簡史[26].2009年,IETF(Internet Engineering Task Force)發布了CGR文檔[35];2010年,CGR文檔被更新為IETF互聯網草案[30];2011年,Segui等人[24]提出了增強CGR(enhanced CGR,簡稱ECGR),把最早到達時刻(earliest-arrival-time)作為路徑選擇度量值,并使用標準的 Dijkstra算法選擇路徑;2012年,Birrane等人提出了擴展塊 CGR(CGR-extension block,簡稱 CGR-EB),以增加數據包報頭開銷為代價來降低中間節點的計算開銷[28];2014年,Fraire等人提出了緩存CGR(cache-CGR,簡稱 C-CGR),以最大程度地減少CGR的執行次數[36];同年,Bezirgiannidis等人提出了最早傳輸機會CGR(CGR-earliest transmission opportunity,簡稱CGR-ETO),引入節點隊列信息,以改善CGR應對網絡狀態變化的能力[37],并在文獻[38]中提出了超額預訂管理(overbooking management)機制,以提高低優先級束的交付率.

Fig.5 Brief history of CGR圖5 CGR簡史

關于擁塞控制(congestion control),文獻[39-41]相繼提出了預測容量消耗(predictive capacity consumption,簡稱PCC)[39]、基于本地信息的擁塞控制[40]、路徑感知CGR(path-aware CGR,簡稱PA-CGR)和多圖CGR(multigraph CGR,簡稱MG-CGR)[41]等多種改進方法.2016年,Burleigh等人為了實現確定性DTN和機會性DTN路由機制的統一,提出了機會CGR(opportunistic CGR,簡稱OCGR)[31].2017年,時文豐等人在CGR中引入了接觸異常處理機制,提高了CGR應對接觸失效的能力[42].

2.1 算法收斂性

保證路由算法的收斂性需要滿足兩個特性:不存在路由環路、不存在持續震蕩.在路徑選擇中采用單調遞增(或遞減)的度量指標,可以保證路由的收斂性[24].CGR采用最早收回時刻作為路徑選擇度量指標,以最大程度地減少傳輸機會的浪費.然而,最早收回時刻不是一個單調遞增(或遞減)的度量指標,不能保證路徑選擇過程中始終不會出現路由環路和震蕩.為此,文獻[24]提出了ECGR算法,用最早到達時刻代替最早收回時刻,并使用標準的 Dijkstra算法進行路徑選擇.最早到達時刻滿足全局單調遞減的特性,因而可以避免路由環路和持續震蕩的產生.此外,Dijkstra算法計算開銷小,且可用于構建多播樹.上述功能改善已經成為 CGR核心功能的一部分,在JPL開發的星際覆蓋網絡(interplanetary overlay network,簡稱ION)仿真平臺中得以實現[43].

2.2 計算開銷

CGR路徑上的每個中間節點重新計算束的最優轉發路徑,以應對網絡狀態的變化.重計算在給算法帶來靈活性的同時,也增加了算法的計算開銷.為了解決此問題,文獻[28,34]提出了 CGR-EB,將計算出的路徑信息和用于路徑計算的接觸圖信息編碼到束的擴展塊中,傳輸到下游節點.下游節點進行如下路徑有效性驗證.

首先,根據當前節點的接觸計劃檢查下一跳接觸的穩定性.

· 如果下一跳接觸不穩定,則重新執行CGR來計算新的路徑,并根據新路徑更新CGR的擴展塊.

· 如果接觸是穩定的,則驗證接觸傳輸速率和容量是否在容錯范圍內:

? 如果誤差超出了容錯范圍,則重新執行CGR來計算新的路徑,并根據新路徑更新CGR的擴展塊;

? 否則,可選擇進行一跳掃描來查找是否存在到達指定的下一跳節點的更快路徑,如果存在,則采用較快的接觸轉發束.

繼續重復上述過程,檢測后續幾個接觸的穩定性.

CGR-EB僅當接觸穩定性驗證失效時才重新執行CGR,不需要在每個中間節點都執行復雜的CGR路由計算.與執行CGR相比,驗證路徑有效性的計算開銷小,因此,CGR-EB更加適合節點資源受限的網絡環境.此外,當編碼路徑有效時,可使用多種成本函數重新搜索潛在的較優路徑,既不必擔心產生路由環路,又避免了預計算路徑為當前次優路徑的情況.最后,利用束攜帶并傳播路徑信息可以為擁塞預測和拓撲同步提供可用的信息.受CGR-EB算法的啟發,文獻[44]提出了一種基于 CGR的源路由算法,由源節點根據已知的接觸計劃和節點緩沖區占用率計算束的轉發路徑,并將所得路徑編碼在包頭中供中間節點使用.該方法以傳輸成本為代價,降低了中間節點的計算開銷.

雖然CGR-EB算法和基于CGR的源路由算法采用路徑編碼的方式減少了調用CGR的次數,但同時也增加了每個束的報頭開銷.文獻[36]提出的 C-CGR在減少 CGR執行次數的同時,保留了本地擁塞避免的特性.C-CGR將每個目的節點對應的當前節點的下一跳相鄰節點記錄到本地緩存區中.當有束到達時,本地節點先查找緩存區中是否存在與此束的目的節點對應的下一跳相鄰節點.

· 如果不存在,則調用CGR為此束計算可用的下一跳相鄰節點,并將計算出的下一跳節點記錄到本地緩存區中.

· 如果查找到了對應的下一跳相鄰節點,則判斷相應接觸的容量和結束時刻是否有效:如果接觸失效,則調用CGR計算新的下一跳節點,并更新本地緩存區中目的節點對應的下一跳相鄰節點信息;如果接觸可用,則僅需更新接觸的剩余容量信息.

在最壞情況下,C-CGR的計算開銷與CGR相同;在分片密集型DTN中,C-CGR的計算開銷明顯低于CGR.

2.3 預測準確性

雖然 CGR、ECGR、CGR-EB和C-CGR均采用動態轉發決策策略,但它們可能使用的是已經過時或不能反映當前網絡狀態的接觸信息.這是因為空間網絡接觸調度雖然具有規律性,但仍然存在由不利的天氣條件或概率性動態參數(如排隊延遲)等擾亂預定網絡接觸調度的情況,因此需要改進路由算法以應對網絡接觸調度規律變化等問題.文獻[37]提出了 CGR-ETO算法,引入最早傳輸機會(由排隊延遲和鏈路中斷確定)作為路由計算的度量指標,并使用接觸計劃更新協議(contact plan update protocol,簡稱CPUP)傳播網絡特征和參數變化信息,從而提高了延遲預測的準確度.然而,CGR-ETO僅考慮本地節點的排隊延遲,無法應對所選路徑下游節點以及下游鏈路的性能瓶頸.文獻[45]提出了基于統計預測的多跳節點排隊延遲預測方法,提高了投遞時間預測的準確性.但此方法依賴于節點間信息的定期交互,增加了額外的網絡信息交互開銷.而文獻[46]提出了增強 CGRETO(enhanced CGR-ETO),既將所考慮的排隊延遲范圍由本地節點擴展到路徑上的所有節點,又避免了額外的信息交互開銷.增強CGR-ETO將ETO的值作為參數值編碼到節點接觸信息中,本地節點根據獲取的接觸信息計算路徑上所有節點的隊列長度,而不使用任何類似于 CPUP的傳播機制.該方法在提高投遞時間預測準確性的同時,避免了節點間狀態信息交互的昂貴代價.

2.4 超額預訂管理

由于接觸持續時間和數據傳輸速率有限,因此接觸容量有限.雖然CGR在轉發束之前檢查接觸剩余容量的可用性,但在剩余容量的計算中,只考慮了隊列中優先級不低于轉發束的束所需消耗的容量,因此在轉發較高優先級的束時,CGR通過忽略低優先級的束來保證高優先級束的轉發.如果接觸已經被低優先級的束完全預訂了,則在轉發高優先級的束時,低優先級的束將錯過其接觸,造成接觸超額認購(contact oversubscription)[47].CGR采用后驗方式處理接觸超額認購,即一旦已經錯過接觸的束的有效時間到期(一般為接觸的結束時刻),則重新轉發這些束.這種后驗方法雖然健壯,但效率不高.文獻[38]提出了一種先驗方法,即超額預訂管理,改善 CGR性能.在超額預定管理中,用總剩余容量評估接觸可用性,計算總剩余容量時,不區分束的優先級而綜合考慮隊列中所有束所需消耗的容量.當出現超額認購時,首先轉發引發超額認購的高優先級的束,然后立即轉發錯過接觸的低優先級束.此外,文獻[38]指出,最早傳輸機會與超額預定管理能夠實現優勢互補,極大地改善了CGR路由決策的性能.這兩項改進均已被CGR的官方版所采納,并在ION中得以實現[43].

2.5 擁塞控制

擁塞問題可以定義為試圖發送比接觸或節點緩沖區可承載數據量要多的數據,因此,網絡中的接觸容量限制和過多的業務量都可能會引起擁塞.CGR通過維護本地節點接觸的剩余容量信息來避免使用本地擁塞鏈路轉發數據的情況.這種僅考慮本地接觸剩余容量而忽略后續路徑接觸容量及中間節點存儲能力的方式可能會引起不必要的業務量反彈效應[41],因此,文獻[39]提出了PCC算法.PCC既可以作為DTN流量控制方案,也可以作為DTN拓撲同步方法.它將節點生成的源與目的節點間的可行路徑及路徑上每個接觸的剩余容量信息封裝到數據包頭部中,中間節點根據接收的數據包頭部信息和異步反饋消息完成本地接觸圖更新、容量預測和路由決策.PCC雖然通過利用相鄰節點間的信息交互改善了本地節點的知識處理能力,但所需的包頭部開銷非常大.

文獻[41]提出了PA-CGR和MG-CGR兩種擁塞避免方法,并提出了基于可預知的接觸計劃和業務量的線性規劃模型,作為分析和對比DTN擁塞感知機制的基準.PA-CGR算法利用接觸計劃中已包含的接觸容量信息,推測路徑容量(路徑容量由路徑上剩余容量最小的接觸決定),并根據路徑容量和本地接觸的剩余容量進行路由決策.PA-CGR提高了接觸計劃中網絡拓撲信息的利用率,擴展了CGR的擁塞避免特性.與PCC相比,包頭部開銷減小了,但包投遞率降低了.MG-CGR利用確定性DTN中接觸計劃和業務量的可預知性以及線性規劃模型構建擁塞避免路由架構.MG-CGR與CGR、PCC和PA-CGR最大的區別在于,MG-CGR利用線性規劃模型為每個節點定制特定的接觸計劃,然后,每個節點根據特定的接觸計劃采用CGR-EB進行路由計算和轉發.對于業務量可預知的確定性DTN,MG-CGR性能逼近線性規劃模型的上限,而對于業務量隨機的情況,PCC的性能最好.

此外,針對地球觀測衛星網絡這類數據生成和資源預留均由任務操控制中心管理的空間 DTN,文獻[48]提出了全局路徑感知CGR(global path-aware CGR,簡稱GPA-CGR),即在接觸圖生成階段,基于可預知的拓撲信息和業務量全局視圖采用演化算法生成無擁塞的接觸計劃,并分發給網絡中的每個節點.每個節點基于接收到的接觸計劃,應用CGR-EB計算數據包轉發路徑.鑒于GPA-CGR依賴于可預測的業務量生成接觸計劃,處理不可預測業務、拓撲變化以及業務量預測誤差的能力有限,文獻[48]在GPA-CGR中引入了容量計算誤差余量,并分發次優備份接觸計劃到網絡中的所有節點以防網絡突發事件的發生.

除了上述工作以外,文獻[40]改進了CGR-ETO的轉發決策機制,提出了基于本地信息的擁塞控制機制.該機制充分利用了 CGR的多路徑計算能力,將次優路徑作為備用路徑,通過隊列出隊/入隊速率和束的最早傳輸時刻預測網絡狀態.如果將束沿著最優路徑轉發會造成傳輸隊列擁塞,則利用備用路徑轉發該束來避免擁塞發生.

2.6 機會性擴展

目前,DTN路由方案呈現二分性,即確定性DTN路由方案和隨機性DTN路由方案彼此相互獨立.為了給出一個適合所有DTN環境的統一路由方案,文獻[31]提出了基于CGR的OCGR算法.與CGR相比,OCGR算法不僅擴展了接觸計劃,而且在轉發決策過程中引入了束交付置信度.在 OCGR中,接觸計劃由預定接觸(scheduled contact)、發現接觸(discovered contact)和預測接觸(predicted contact)組成.預定接觸通過接觸計劃調度得出,發現接觸由節點實時發現,預測接觸則依據發現接觸的歷史信息進行預測.預定接觸和發現接觸的置信度為 1,而預測接觸的置信度由發現接觸日志信息推導得出.OCGR定義路徑的置信度為路徑中所有接觸的置信度的乘積,并根據路徑的置信度確定束的交付置信度.OCGR的研究仍處于起步階段,其性能尚未超過其他機會路由算法,但一般認為,此改進是可行的[31].

2.7 異常處理

空間DTN網絡所處網絡環境復雜,接觸易受電磁波干擾、鄰頻干擾等影響而意外中斷,網絡節點可能遭遇攻擊、能量耗盡、天線故障等而失效,造成網絡拓撲意外變化.CGR基于準確的接觸計劃進行路由決策,缺少應對節點或鏈路異常的能力.文獻[42]在CGR中引入了應對接觸意外中斷的策略,提高了CGR處理接觸異常的能力.該機制首先根據接觸上連續發生束重傳的次數判斷鏈路是否發生意外中斷;一旦檢測到接觸中斷,則將接觸失效信息通告給所有節點,與此同時,激活接觸失效探測機制發送探測束檢測接觸是否恢復;如果接觸恢復,則將接觸恢復消息下發給所有節點;節點接收到接觸失效或恢復消息后更新本地接觸圖,重新計算路徑.

3 CGR工程應用

已經有多種DTN開源仿真平臺,包括DTN2、ION、Postellation、IBR-DTN、JDTN和ONE等[49].其中,DTN2由加利福尼亞大學采用C和C++語言編程實現,主要包含的路由協議有靜態路由、洪泛路由、延遲容忍鏈路狀態路由(delay tolerant link state routing,簡稱DTLSR)和基于概率的Prophet路由等[50].ION是由JPL實驗室針對空間網絡開發的軟件平臺,采用C語言實現,支持Linux、Solaris、OS/X、FreeBSD、VxWorks、RTEMS等平臺,路由采用CGR[51].Postellation是由Viagenie使用C語言開發的,支持IPv4和IPv6[52].IBR-DTN是由布倫瑞克工業大學基于C++語言開發的,支持Openwrt、Ubuntu、Android、MacOS等系統,其路由模塊主要包括靜態連接路由、基于發現的路由、傳染路由、洪泛路由和Prophet路由[53].JDTN是由思科開發的基于Java語言實現的平臺,支持Android等移動平臺[54].ONE是由Ker?nen等人基于Java語言設計的機會DTN路由仿真平臺,主要支持DirectDelivery、Epidemic、Maxprop、Prophet、Spary and Wait等路由協議[55].在上述仿真平臺中,CGR主要在 ION中實現,而 ION多用于仿真由有限節點組成的小規模空間 DTN.為了補充 CGR的研究評估手段,Berlati等人已將CGR移植到ONE上,打破了基于小規模網絡測試評估CGR性能的局面[56].

多項空間實驗被相繼展開,以驗證DTN范型和CGR的有效性.根據實測實驗開展的時間先后順序,我們簡要介紹以下4個實驗,如圖6所示.在2008年10月進行的為期27天的深度撞擊網絡(deep impact network,簡稱DINET)實驗中,順利接收到了來自火星的292張圖片[57];2009年7月,美國國家航空航天局(National Aeronautics and Space Administration,簡稱NASA)在國際空間站(International Space Station,簡稱ISS)上開始DTN范式實驗,并于2016年5月在ISS上正式運行[58];2010年11月,塞薩斯德謨克里特大學等多個研究單位共同開始了為期3年半的空間數據路由器(space-data router,簡稱 SDR)項目,驗證了 CGR有助于空間科學數據的分發[59];2011年～2013年期間,日本宇宙航空研究開發機構(Japan aerospace exploration agency,簡稱JAXA)與NASA聯合完成了DTN技術測試,證實了在航天器中使用DTN與CGR是可行的[60].

Fig.6 Conducted real test experiments圖6 已開展的實測實驗

3.1 深度撞擊網絡

DINET是為測試DTN協議(如BP、CGR等)實施的深空飛行驗證實驗[61].在該實驗中,將ION軟件上載到深度撞擊飛行器中,同時,在地面多臺計算機上安裝 ION軟件模擬地球、火星和火衛一(phobos),從而構建一個火星-地球通信的虛擬場景.深度撞擊飛行器作為中繼路由,實現火星與地球之間的數據傳遞.DINET的網絡系統組成如圖7所示[57].

· 7號節點表示深度撞擊飛行器,是網絡中唯一沒有被放置在JPL實驗室的節點.

· 節點2、節點4、節點8和節點16模擬地球表面的通信系統.

· 節點3、節點6和節點12模擬火星表面的通信系統.

· 節點5、節點10和節點20模擬火衛一表面的通信系統[7].

· 節點8、節點12和節點20模擬終端節點.其中,節點12和節點20生成圖像文件,節點8接收和顯示圖像文件.

· 節點2、節點3和節點5分別模擬地球、火星和火衛一通信系統與深度撞擊號之間的中間接口系統.

· 節點4、節點6、節點10模擬終端節點和地面系統間的路由器.

· 節點16表示實驗中用于分析和檢測實驗數據的管理系統[62].

Fig.7 DINET system components圖7 DINET的系統組成

該實驗模擬了火星和火衛一表面探測節點將采集的圖像通過深度撞擊飛行器傳回地面的過程.圖中的每個帶箭頭的虛線表示DTN網絡接觸序列;中間接口系統與實驗操作中心之間帶箭頭的實藍線表示用于連接實驗設備的局域網.圖中節點6和節點10之間的鏈路為節點12和節點20之間的數據傳輸提供備用路徑.經過近一個月的測試,CGR性能表現良好,實驗中發現的漏洞也已經在高版本的ION中得以解決.

3.2 國際空間站

自2009年起,NASA在ISS上開展了多項DTN驗證實驗.2009年7月的第1個實驗是通過數據中繼衛星系統(data relay satellite system,簡稱 TDRSS)下載位于 ISS上的商業通用生物處理設備(commercial generic bioprocessing apparatus 5,簡稱CGBA-5)中的圖像文件[63].圖像文件從ISS傳輸到位于亨茨維爾的馬歇爾航天中心,然后轉發到位于科羅拉多大學波爾得分校的有效載荷操作控制中心.雖然此次部署的 CGBA拓撲復雜度并不足以充分發揮CGR的作用,但其成功部署,使ISS運營團隊更加確信DTN將成為ISS通信技術的重要組成部分[64].2012年,NASA和歐洲航天局(European Space Agency,簡稱ESA)模擬了在軌飛行器上的宇航員遠程控制行星表面探測器的場景[65].ISS上的指揮官Williams成功地借助DTN協議發送遠程控制命令,遠程“駕駛”位于歐洲太空操作中心的小型樂高(Lego)機器人[66].該實驗證明了使用 DTN通信基礎設施從在軌航天器向地面機器人發送命令以及接收從機器人發回的數據的可行性.

3.3 空間數據路由器

由于空間數據收集中心和學術研究機構與衛星間的可通信時間有限,而且空間數據收集中心與學術研究機構間缺乏高效的通信機制,因此空間數據分發面臨龐大數據量、時效性和連續性的制約,常常造成空間數據未能被有效及時地利用[59].為此,歐盟委員會資助成立空間數據路由器項目,旨在建立一個基于 DTN的空間數據開發架構,從數據量、及時性和連續性方面改進空間數據的分發.該項目的構想如圖8所示[67]:利用DTN疊加層和 CGR進行路由決策,一旦接收到空間任務數據,就直接轉發給研究機構等感興趣的終端用戶.該項目評估了CGR在空間任務地面段的適用性,證實了CGR有助于空間數據的高效分發[60].

Fig.8 Space data dissemination based on SDR圖8 基于SDR的空間數據分發

3.4 JAXA/NASA DTN測試

JAXA與NASA通過半真實半模擬的空間延遲/中斷環境,測試了DTN技術的可行性以及CCSDS文件傳輸協議(CCSDS file delivery protocol,簡稱CFDP)、Bundle流服務(Bundle streaming service,簡稱BSS)和CGR的有效性.該測試分為 4個不同的測試階段[68],見表3.第 1階段主要是在開始正式測試之前驗證網絡連接性和DTN基本功能;第2階段通過模擬飛行器的運行場景驗證DTN功能;第3階段在真實的數據中繼實驗衛星(data relay test satellite,簡稱DRTS)空間鏈路環境下驗證DTN功能;第4階段通過DRTS空間鏈路連接ISS上的DTN節點與JAXA航空中心的DTN節點來驗證DTN的功能.為了證實在長距離延遲和中斷環境中CGR的可行性,采用了一個典型的深空中繼通信場景,如圖9所示.該場景由 1個任務操作中心(mission operation center,簡稱MOC)、1個行星表面探測車(rover)、1個DRTS衛星、2個行星中繼軌道衛星(ROP1和ROP2)和2個地面站(GT1和 GT2)組成[69].Rover采集生成的數據通過 DRTS、ROP1、ROP2、GT1和 GT2傳輸到 MOC.測試中將 ION部署在所有節點上,并利用 CGR動態查找最佳路由.為了更加真實地模擬實際通信環境中的鏈路延遲和中斷,在測試中加入DRTS衛星和兩個地面站之間的實際傳播延遲和處理延遲以及通過延遲模擬器模擬的DRTS衛星與ROP1和ROP2之間3 600s的往返延遲.此外,通過開關射頻鏈路,模擬由無線電干擾和雨衰引起的不可預測中斷以及由航天器間不可視引起的可預測中斷,并通過增加或減小射頻電平大小,模擬實際降雨的衰減水平.測試結果顯示,CGR能夠實現傳輸路徑的自動選擇,成功地完成了圖像文件的傳輸.

Table 3 JAXA/NASA DTN test items表3 JAXA/NASA DTN測試內容

Fig.9 JAXA DTN test topology圖9 JAXA的DTN測試拓撲

4 性能評估

本文將CGR應用到由GEO/MEO/LEO組成的多層衛星網絡中,從拓撲處理策略、路由跳數、路徑延遲、故障處理和擁塞控制等5個方面對比分析了CGR與多層衛星路由算法(multi-layered satellite routing algorithm,簡稱MLSR)[70]的性能.MLSR根據GEO衛星和MEO衛星的覆蓋范圍將MEO衛星和LEO衛星分組,并根據分組關系變化劃分時隙,GEO衛星和MEO衛星為組管理者,負責網絡狀態信息維護和路由表計算.鑒于采用ION仿真大規模多層衛星網絡所需的硬件成本高,本文選用支持CGR的ONE平臺作為多層衛星網絡模擬器來對比評估兩種路由算法性能.由于ONE中不包含衛星節點的運動模型,我們采用STK構建多層衛星網絡拓撲結構,分析并生成其星間連接、距離、星下點軌跡等數據,導入到 ONE中進行仿真.ONE模擬器的主要參數設置見表4.

Table 4 Main parameter settings of ONE表4 ONE主要參數設置

所用的多層星座參數見表5,其中,GEO衛星軌道位于赤道上方,MEO衛星和LEO衛星則分別采用傾斜軌道和極軌道.仿真中,將36顆LEO衛星編號為0～35,12顆MEO衛星編號為36～47,3顆GEO衛星編號為48～50.

Table 5 Main parameters of satellite constellation表5 衛星星座主要參數

4.1 時隙分布

本文以24h為系統周期,分別按照CGR和MLSR的拓撲處理策略,將多層衛星網絡的一個系統周期劃分為多個時隙,結果如圖10和圖11所示.

Fig.10 MLSR slot distribution圖10 MLSR時隙分布

Fig.11 CGR slot distribution圖11 CGR時隙分布

圖10為按照MLSR的拓撲處理策略劃分時隙的結果,多層星座的一個系統周期被劃分為4 972個時隙,時隙間隔大多分布在60s以內,最短時隙間隔長度為1s,最長為122s.圖11為按照CGR的拓撲處理策略劃分時隙的結果,其時隙總數為59個,均勻分布在7 100s以內,最短時隙間隔長度為439s,最長為7 038s.原因在于,MEO衛星與LEO衛星之間的組間關系頻繁變化,造成MLSR一個系統周期內的時隙數量較大;而CGR采用星間接觸的最大連通時間為單位劃分時隙,時隙數量少.過短的時隙間隔導致路由算法可能不收斂,而過多數量的時隙導致需要大量空間來存儲相關狀態信息,給星上資源有限的衛星節點帶來挑戰.

4.2 跳數和延遲

假設地面站以編號為 0的LEO衛星為接入衛星,分別向編號為 1～50的衛星節點發送數據包,統計MLSR和CGR求得的路徑延遲和路由跳數,結果如圖12所示.可以看出,CGR求得的路徑延遲比MLSR略小,但也存在部分路徑延遲大于 MLSR的情況.原因在于,CGR可以充分利用長時隙間隔內的所有鏈路進行數據傳輸,MLSR只能通過短時隙間隔內始終連通的鏈路傳輸數據.但由于MLSR綜合考慮了傳播延遲、處理延遲和隊列延遲,而 CGR只考慮了鏈路容量限制沒有考慮排隊延遲,因此當節點緩存隊列中數據包較多時,CGR的路徑延遲略大于MLSR.

Fig.12 Hops and delay圖12 跳數和延遲

由圖12可知,通過編號為0的LEO衛星向編號為1～35的LEO衛星發送數據時,MLSR的路由跳數分布在2跳;CGR的路由跳數分別以30%的概率分布在1跳、2跳和3跳,而以10%的概率分布在4跳.當通過編號為0的LEO衛星向編號為36～47的MEO衛星發送數據時,MLSR的路由跳數以40%的概率分布在3跳,而以60%的概率分布在1跳;CGR的路由跳數以30%的概率分布在2跳,而以70%的概率分布在1跳.當通過編號為0的LEO衛星向編號為48～50的GEO衛星發送數據時,MLSR的路由跳數分布在2跳、3跳、4跳,CGR的路由跳數為4跳.此外,對比路由跳數和延遲的關系可知,當路由跳數增大時,兩種算法的路徑延遲并未出現大幅度增大的情況,僅在向 GEO 衛星發送數據時,路徑延遲大幅增大.原因在于,衛星網絡的路徑延遲主要取決于傳播延遲,MLSR僅以路徑延遲作為度量值指導選路過程,CGR同時考慮了路徑延遲和跳數兩個度量值,LEO衛星和GEO衛星間的傳輸距離遠,傳輸延遲長,導致路徑延遲大.

4.3 故障處理

衛星天線故障、能量耗盡或黑客攻擊等會造成衛星節點意外失效,使得經過失效節點的路徑無法繼續使用.本文假設編號為10、27和38的3顆衛星同時在第15s發生意外失效,失效時長為175s,統計分析該失效時間段內所有預計經過失效節點傳輸的數據包的投遞率,結果如圖13所示.由圖可知,隨著衛星節點失效時間的增加,CGR的包投遞率逐漸降低;而MLSR的包投遞率僅在節點失效剛發生后的較短時間內出現下降,之后迅速恢復到較高水平.原因在于,CGR的路徑計算所依據的是預知的接觸計劃,當節點失效發生后經過失效節點的最優路徑仍被用來繼續轉發數據包,致使大量數據包聚積在失效節點附近的鄰接節點中,引起數據包因生命周期失效或節點隊列溢出而被丟失,降低了數據包投遞率;而 MLSR具有節點失效處理能力,當節點失效發生后,其鄰接節點會主動發起拓撲更新及路由重計算,因此數據包可以避開失效節點進行轉發,減輕了節點失效對數據包傳輸的影響.

Fig.13 Packet delivery ratio under node failures圖13 節點失效時的數據包投遞率

4.4 擁塞控制

當網絡業務請求數量增多時,CGR最多選用3條路徑同時傳輸數據.分別統計當業務請求增多時采用CGR和MLSR傳輸業務請求的平均端到端延遲,結果如圖14所示.

Fig.14 Influence of traffic requests on end-to-end delay圖14 業務請求對端到端延遲的影響

由圖可知,CGR和MLSR的平均端到端延遲均隨業務請求數增加而增加,但CGR的平均端到端延遲增長幅度比MLSR要小.此外,在業務請求數量相同的情況下,CGR的平均端到端延遲明顯低于MLSR.原因在于,業務請求的增多會導致節點排隊延遲變長,使路徑的端到端延遲變大.而 CGR具有多路徑計算能力,在業務請求數量增加時,可以通過多條路徑進行業務傳輸,減小了節點上的排隊延遲,因此,CGR端到端延遲增長幅度比采用單路徑傳輸的MLSR要小.

5 總結與展望

空間DTN具有長延遲、高誤碼率、拓撲頻繁變化等特點,這些特點給空間DTN路由帶來嚴峻的挑戰.CGR為空間 DTN路由提供了一個切實可行的解決方案,受到了學術界的廣泛關注.本文根據現有文獻,給出了 CGR的基本原理、相關術語和算法過程,綜述了針對CGR的缺陷提出的改進方案和已部署的驗證CGR的空間飛行實驗,并在多層衛星網絡中對比評估了CGR的性能.在此基礎上,本文提出以下有待進一步研究的問題.

(1)CGR-EB和C-CGR分別采用路徑編碼和路徑緩存的方式降低了CGR的計算開銷,但是前者增加了包頭部開銷,而后者以緩存空間為代價.如何將CGR-EB和C-CGR相結合以進一步改善系統整體性能,是一個值得研究的問題.

(2)改進CGR,使其適用于隨機性DTN.雖然針對該問題,現有文獻已提出了OCGR,但性能較差,算法設計有待進一步改進.

(3)CGR在有效性和帶寬開銷上與當前的 Internet路由算法相當,但計算復雜度高.盡管這對于小規模簡單網絡來說不是問題,但對于復雜的大規模網絡則不可行.文獻[18]首次測試了CGR在小、中、大這3種規模時變網絡拓撲上的性能并指出,隨著節點間接觸數量和網絡節點數目的增加,CGR計算開銷顯著增長,每個束的轉發時間呈指數增長.因此,在CGR中引入劃域的思想,對于降低CGR計算開銷、完善其理論基礎具有重要的意義.

(4)路由協議在提高服務質量(quality of service,簡稱QoS)中扮演著重要的角色,而空間DTN中的QoS路由與QoS保障機制等研究仍處于發展的早期階段[71],因此,設計具有QoS保障能力的CGR是一個有待研究的問題.

(5)CGR采用接觸列表描述所有時間間隔內節點間的通信機會,對于同一時間段內相同源和目的節點間的上下行鏈路分別使用不同的接觸項描述[72].因此,當網絡規模擴大或網絡服務持續時間變長時,接觸計劃列表將變得非常大,降低了CGR算法效率.設計適用于大規模、長服務時間DTN的接觸計劃描述方法,對完善CGR理論基礎具有重要的意義.

(6)空間網絡配置更新困難、星上計算和處理能力有限、高異構性等特點,給空間組網技術的發展帶來了嚴峻的挑戰.將SDN(software defined networking)和NFV(network function virtualization)引入到空間網絡來設計新的網絡組網范式,是應對上述挑戰的有效途徑[73].引入 SDN,可以解耦控制平面和轉發平面,使空間網絡具有可編程性、靈活性和可重構的特點;引入NFV,能夠簡化網絡管理,促進資源共享、聚合動態分配[74,75].同時,引入上述兩種技術能夠實現空間網絡統一、靈活、細粒度的配置和管理,可以解決空間網絡靜態路由中因控制結構不靈活而無法滿足負載均衡、故障管理和網絡擴展的問題以及動態路由全網控制能力弱的問題,有效地權衡空間網絡路由靈活性和可控性.