空間DTN網絡CGR路由算法綜述

張博文 ，姚秀娟

（1.中國科學院國家空間科學中心北京100190；2.中國科學院大學北京100049）

伴隨著通信技術的發展，通信場景愈發豐富，出現了許多新興網絡，包括空間通信網絡、傳感器網絡、移動車載網、戰術通信網、鄉村通信網絡等。與傳統網絡環境相比，這些場景的網絡環境有著時延大、傳輸誤碼率高、端到端連接狀態不穩定等特點。2003年，IRTF（Internet Research Task Force）的下屬組 織 DTNRG（Delay Tolerant Networking Research Group）提出了 DTN（Delay Tolerant Network）網絡協議以解決此類問題[1]。DTN網絡協議在傳輸層與應用層之間添加了捆綁層（Bundle Layer），并采用存儲-轉發的路由機制，通過將數據存儲在當前節點等待的方式來應對網絡中斷問題[2-3]。

2008年，美國航空航天局NASA基于DTN網絡提 出 了 CGR（Contact Graph Routing）路 由 算 法[4]。CGR路由算法利用空間網絡節點的周期性，通過各傳輸節點已知的接觸計劃（Contact Plan）生成接觸圖（Contact Graph），再根據生成的接觸圖決定數據的傳輸路徑。CGR路由算法因其占用存儲資源和計算資源較少的優勢，成為了空間網絡通信領域的研究熱點[5-7]。然而CGR路由算法在路徑選擇、計算傳輸時間等方面還存在著一些待改進的問題，仍有進一步優化的空間[8-11]。

文中將簡要介紹CGR路由算法的實現原理以及CGR路由算法的優缺點。針對該算法存在的問題介紹和分析3種基于CGR路由算法做出的改進算法：ECGR路由算法、CGR-ETO路由算法以及CGREB路由算法。通過分析比較這3種改進算法的優缺點以及應用場景對這3種算法做出評估。最后對CGR路由算法的發展做出展望。

1 CGR路由算法

CGR路由算法是由美國航空航天局NASA噴氣推進實驗室針對空間通信網絡具有周期性和確定性的特點所提出。該算法通過通信節點間鏈路的預先規劃以及周期性，根據網絡中各節點之間的接觸計劃生成接觸圖。當通信節點有消息發送時，CGR算法將分析這個接觸圖并計算出生成下一跳節點的集合，然后在集合中選擇傳輸路徑。當數據到達下一跳節點時，CGR算法將在下一跳節點繼續運行這個流程[12-15]。與其他路由算法相比，CGR路由算法可以有效利用空間通信網絡節點間的通信機會。

CGR路由算法的整體流程如圖1所示。CGR算法首先通過接觸計劃生成接觸圖。接觸計劃信息分為兩個部分，接觸信息（Contact Message）與距離信息（Range Message）。接觸信息用來描述給定時間間隔內兩個節點間的數據傳輸速率。每個接觸信息包含以下內容：開始UTC時間、終止UTC時間、發送節點、接收節點以及發送節點到接收節點的計劃傳輸速率。距離信息用來描述給定時間間隔內兩個節點間的距離。每個距離信息包含以下內容：開始UTC時間、終止UTC時間、發送節點、接收節點以及發送節點到接收節點的預期距離。

圖1 CGR路由算法流程圖

每個節點根據完整的接觸計劃建立自己的接觸圖數據結構，接觸圖在每個節點本地建立，并對每個其它節點建立兩個鏈表xmit列表以及origin列表：xmit列表，每個列表包括接觸開始時間，接觸停止時間，發送節點號和數據傳輸速率，列表數據通過所有接收節點為節點的接觸信息得到。xmit列表通過接觸開始時間進行排序。origin列表，每個列表包括發送節點號與該節點到節點的當前距離，列表數據通過距離信息得到[16-17]。

一旦生成了接觸圖，CGR路由算法會分為兩部分流程，分別為接觸檢查過程（CGR-CRP）和消息轉發過程（CGR-FBP）。表1展示了這兩個流程中所使用的變量。CRP的流程通過檢查節點D的xmit列表中每一個接觸信息m對接觸信息m的開始時間、預計消耗容量等參數進行判定，如果參數符合要求則可將節點D加入到可轉發節點列表中。表2列出了CGR-CRP流程的偽代碼。

表1 CGR路由算法變量定義

可以看到，CGR-CRP流程的作用是得到能夠轉發數據包的鄰居節點的集合，然后通過CGR最佳路徑選擇標準來選擇路徑并進行轉發。如果是在地球軌道衛星通信環境，最佳路徑選擇標準應為數據包傳輸延遲最小路徑。如果是在深空通信環境，通信機會遠比幾分鐘或是幾小時的傳輸延遲要重要得多，數據包要在自身生存時間內到達目的地，最佳路徑應將最早失效時間作為路徑選擇標準，將接觸效用最大化。

在結束CRP流程后，消息傳輸進入FBP流程。此時，可轉發節點列表ProxNodes中的每個節點都是可以轉發數據包的相鄰節點，可通過其中一個節點將數據包向目的節點轉發。表3列出了CGR-FBP流程的偽代碼。完成了CRP和FBP流程后數據包將轉發到下一節點，CGR路由算法將在下一跳節點繼續運行整個流程。

表2 CGR-CRP偽代碼

表3 CGR-FBP偽代碼

通過上述的CGR路由算法流程可以看到，CGR路由算法是一種基于先驗知識的DTN網絡路由算法。這種路由算法在周期性應用場景中比其他類型的路由算法要更少地占用存儲資源以及計算資源。但是，CGR路由算法仍有一些問題亟待解決，例如：在路徑選擇算法中并未考慮路由環路的情況；計算傳輸時間時未計入數據包的排隊延遲；傳輸路徑選擇算法計算量較大。為此，出現了許多基于CGR路由算法的改進算法致力于對CGR路由算法做出進一步的優化。

2 CGR路由算法改進

2.1 ECGR路由算法

為了提升CGR路由算法的安全性，避免路由環路及路由震蕩現象的發生，文獻[18]在CGR路由算法的基礎上提出了ECGR（Enhanced Contact Graph Routing）路由算法[18]。ECGR路由算法與CGR路由算法相比，主要作出了以下兩點的改進：1）在深空通信場景下，將最佳路徑選擇標準由最早失效時間改為最早到達時間（Earliest Arrival Time）；2）在路徑選擇中使用Dijkstra最短路徑算法。

CGR路由算法中并沒有考慮到路由算法的安全性問題，由于CGR路由算法采用的路徑選擇標準是傳輸數據包的最早失效時間，而數據包的最早失效時間并不是單調遞增或單調遞減的度量單位，所以CGR路由算法可能會產生路由環路以及路由震蕩的情況。在ECGR路由算法中用最早到達時間代替最早失效時間作為最佳路徑選擇標準正是因為最早到達時間為單調遞減度量單位，能夠保證不會產生路由環路以及路由震蕩。此外，選擇最早到達時間作為路徑選擇標準可以在路徑選擇過程中使用Dijkstra最短路徑算法。使用Dijkstra最短路徑算法可以有效地減少時間復雜度。根據文獻，CGR路由算法的時間復雜度為O（V!），而ECGR路由算法的時間復雜度為O（VE+V2logV）。

ECGR路由算法解決了CGR路由算法中存在的路由算法安全性問題，有效阻止了路由環路以及路由震蕩現象的發生。當前ECGR路由算法已經加入到CGR路由算法的最新方案中。

2.2 CGR-EB路由算法

文獻[19]基于減少節點計算量的考慮提出了CGR-EB路由算法。CGR-EB路由算法在CGR路由算法的基礎上增加了擴展塊編排到數據包里[19-20]。

CGR-EB路由算法中將網絡的路徑信息作為擴展塊編排到數據包里，在數據包的傳輸過程中節點根據擴展塊信息對本地節點信息進行驗證。如果信息沒有發生變化，則不需要重新對消息轉發路徑進行計算，擴展塊會被省略，節點處理數據包的方式與CGR路由算法中相同。只有當發現接觸發生變化時節點才會重新計算路徑。CGR-EB算法有效地在資源受限的環境中減少了路由路徑選擇計算的復雜度，從而減少了節點的計算量。

CGR-EB路由算法可以分為兩個階段，構造擴展塊以及路徑評估。構造擴展塊階段中，CGR-EB收集接觸圖中的數據包轉發路徑的數據，并將數據編碼成為擴展塊。表4列出了CGR-EB路由算法使用路由消息編碼的擴展塊信息。雖然接觸的距離信息也是CGR路由算法中一個重要的考慮因素，但它不作為擴展塊的一部分在網絡中轉發。路徑評估階段中，當一個節點接收到一個包含擴展塊的轉發消息時，它必須評估擴展塊內容的有效性，然后決定是否承認該路徑，以利于自己的路由計算。評估方法是通過比較增量誤差與每個節點所配置的閾值。如果誤差超過閾值，則節點上的接觸與正在評估的特定屬性的擴展塊中編碼的接觸不匹配。

CGR-EB路由算法擴展塊的信息驗證流程總結如下：1）根據當前節點的接觸計劃檢查下一節點的接觸是否可靠。如果不可靠，則執行CGR路由算法中的路徑選擇流程生成新的路徑，CGR擴展塊更改為新的路徑信息。2）如果接觸可靠，則對傳輸速率、預計容量消耗等信息進行驗證。同樣，如果信息存在太大差異，則執行CGR路由算法中的路徑選擇流程生成新的路徑，CGR擴展塊更改為新的路徑信息。將擴展塊編排到數據包里的改進使CGR-EB路由算法可以很大限度的減少計算的復雜度，更好地應對通信網絡環境中出現的異常狀況。

表4 CGR-EB擴展塊內容

2.3 CGR-ETO路由算法

文獻[21]針對CGR路由算法提出了一種基于最早傳輸機會的接觸圖路由算法（Contact Graph RoutingEarliestTransmission Opportunity，CGRETO）[21]。在CGR路由算法中假設數據包在接觸開始時立即發送，并沒有將數據包傳送的排隊延遲計算在內，而是假定消息可以在接觸的開始時刻立即發送。在CGR-ETO路由算法中，通過隊列信息，為每次接觸增加一個與優先級相關的ETO（Earliest Transmission Opportunity）參數從而更準確地計算數據包的傳輸時間。

ETO參數定義為按一定優先級轉發數據包的最早可行時間，ETO參數與數據包的優先級相關，不同優先級的數據包對應不同的ETO參數。ETO參數的取值范圍為開始接觸時間到結束接觸時間，不同優先級ETO參數的初始值都是開始接觸時間。在接觸圖的遍歷過程中，不同于CGR路由算法，CGR-ETO算法用ETO參數替代最早失效時間去計算最早到達時間。

當數據包在傳輸隊列中等待時，CGR-ETO算法會計算數據包的預計容量消耗，通過預計容量消耗除以傳輸速率計算得到數據包的預計傳輸時間。然后將該數據包的預計傳輸時間作為排隊延遲加到之前預計的ETO信息或當前時間上（以較晚者為準），所有等于或低于該數據包優先級的數據包ETO信息都會被更新。之后CGR-ETO路由算法會遍歷接觸計劃使用ETO信息來決定最優的消息傳輸路徑。

假如CGR-ETO算法在每次數據包轉發時都修改接觸計劃中的排隊延遲，將會對通信系統造成很大的計算成本。為了減少這種計算成本，CGR-ETO算法設置了接觸計劃更新閾值，閾值的表示方式為接觸持續時間的百分比。例如，如果接觸持續時間為1000 s，接觸計劃更新閾值設置為10%，則直到自上次計算以來ETO增加超過100秒本地節點才會重新計算最佳路線。

因為空間網絡環境中數據的傳輸時間和傳輸速率有限，所以CGR路由算法在每次節點間接觸所能傳輸的容量有限，存在接觸超額預定的問題。文獻[22]提出了基于CGR-ETO路由算法的超額預訂管理（Overbooking Management）去解決CGR路由算法中接觸超額預訂的問題[22]。CGR路由算法在每次接觸前會檢查是否有足夠的剩余容量，當轉發較高優先級的數據包時，因為數據包優先級的關系，會故意忽略優先級較低的捆綁包。如果接觸已經被低優先級數據包預訂，這就會導致接觸的超額預訂。

CGR-ETO改進算法中有別于CGR路由算法計算剩余容量時僅考慮具有相同或更高級的數據包，而是不考慮數據包的優先級計算接觸的總剩余容量，根據總剩余量大小，做出不同的數據包轉發決策。如果接觸的總剩余量為正數但小于預計容量消耗，屬于部分超額預訂。超額預訂處理機制為從最低優先級隊列中的最后一個數據包開始重新轉發。如果接觸的總剩余容量是負值，為全部超額預訂。超額預訂處理機制為從為接觸計劃的最后一個數據包開始重新轉發。

2.4 改進算法應用場景比較與評估

通過上述3種改進算法的介紹，可以看到每種改進算法的側重點有所不同。CGR-EB路由算法與ECGR路由算法相比，在傳輸的數據包中加入了擴展塊，擴展塊只有在每次消息轉發路徑需要更改時才會被調用用來幫助通信系統選擇消息包轉發的最優路徑。通過引入擴展塊，CGR-EB路由算法處理每個數據包所調用路徑計算過程的次數降低，從而有效減少了每個通信節點對于轉發路徑選擇的計算量。此外，在端到端延遲以及投遞完成率這兩個指標上，增加擴展塊并不會帶來什么明顯的影響，CGREB路由算法與ECGR路由算法并沒有較大差別。

在傳輸數據量較少的場景下CGR-ETO路由算法無法體現其優勢。因為在數據量較少的情況下接觸計劃很少發生傳輸時間重疊的情況，從而很少出現排隊延遲的情況。但隨著通信網絡中傳輸數據量的增大，接觸計劃產生重疊的頻率也隨之增加，此時CGR-ETO路由算法的端到端延遲情況會明顯優于ECGR路由算法。此外，因為ECGR路由算法沒有考慮數據傳輸的排隊延遲無法充分利用通信鏈路，所以在通信網絡中傳輸數據量較大的情況下，ECGR的投遞完成率也不及CGR-ETO路由算法。然而CGR-ETO路由算法需要在每次轉發過程中重新計算接觸計劃中的排隊延遲，所以與ECGR路由算法相比CGR-ETO路由算法會給通信系統增加一定的計算量，具體增加的計算成本取決于不同場景下CGR-ETO路由算法設置的ETO參數更新閾值。

可以看到，CGR-ETO路由算法與CGR-EB路由算法較ECGR路由算法都有著更明確的應用方向。在通信網絡節點計算能力有限的條件下，與另外兩種路由算法相比CGR-EB路由算法將更加適合。當通信網絡節點計算能力強的情況下，使用CGR-ETO路由算法的消息傳輸表現將會優于其他兩種路由算法。

3 發展方向

CGR路由算法作為DTN網絡路由算法的研究熱點之一，在近些年也得到了長足的發展與進步。以上幾種改進算法使CGR路由算法在安全性、計算量和時間預估等方面都有所改善。但目前CGR路由算法在擁塞控制以及算法的實際應用場景這兩個方面還存在不足。下面將結合CGR路由算法的的特點，分析CGR路由算法在擁塞控制領域和應用場景仿真領域的發展。

1）路由算法中的擁塞控制方法

當前CGR路由算法還缺少對通信網絡的擁塞控制。與其他通信網絡環境相比，DTN網絡環境節點存儲空間以及計算能力有限，容易導致節點的剩余容量不足，從而影響到消息在網絡中的路徑選擇以及通信效率。因此，在CGR路由算法中加入節點擁塞控制機制，例如為節點預留緩存空間、當節點資源將要用盡時優先傳輸優先級較高的數據包、將節點信息轉發到資源較為充裕的其他節點上，從而避免通信網絡發生擁塞。

2）真實應用場景仿真

當前的CGR路由算法研究大多建立于虛擬的太空通信場景中，研究的CGR路由算法改進算法缺少對現實應用場景的仿真。隨著CGR路由算法研究的進一步深入，嘗試對當前太空中真實的網絡通信環境進行仿真，驗證CGR路由算法在真實DTN通信網絡中的效果以及可實施性，應當作為之后的研究重點之一。

4 結論

文中對CGR路由算法以及當前CGR路由算法的改進算法進行了分析和介紹，其中包括對路徑選擇做出改進使用最早到達時間替代最早失效時間的ECGR路由算法、考慮數據包排隊延遲并且提出超額預訂管理的CGR-ETO路由算法以及對路徑消息進行編碼生成擴展塊的CGR-EB路由算法。在通信網絡節點計算能力有限的條件下，CGR-EB路由算法優勢較為明顯。當通信網絡節點計算能力強的情況下，GR-ETO路由算法的消息傳輸表現最佳。本文在對CGR路由算法發展現狀做出總結的同時，也對該領域的未來發展方向進行了展望，指出CGR路由算法的擁塞控制以及在實際場景中的應用將會是未來的研究趨勢。