張培穎/ZHANG Peiying，王超/WANG Chao，吳勝/WU Sheng

（1.中國石油大學(xué)（華東），中國 青島 266580；2.北京郵電大學(xué)，中國 北京 100876）

(1.China University of Petroleum (East China), Qingdao 266580, China;2.Beijing University of Posts and Telecommunications, Beijing 100876, China)

衛(wèi)星網(wǎng)絡(luò)通信是地面通信的重要補(bǔ)充和延伸，它可以為地面用戶提供更加廣闊的信號(hào)覆蓋范圍，而且不易遭受自然災(zāi)害影響，具有較高的靈活性和可靠性。與中軌（MEO）/高軌（GEO）衛(wèi)星網(wǎng)絡(luò)相比，低軌（LEO）衛(wèi)星網(wǎng)絡(luò)還具有通信延遲低、路徑損耗小，以及真正意義上的全球覆蓋等優(yōu)勢，因而，LEO衛(wèi)星通信網(wǎng)絡(luò)體系的建設(shè)具有重大價(jià)值。目前，世界各國越來越重視空間資源的開發(fā)與利用，LEO衛(wèi)星通信系統(tǒng)有望成為新的競爭目標(biāo)。

延遲/中斷容忍網(wǎng)絡(luò)（DTN）是一種面向消息的覆蓋層網(wǎng)絡(luò)體系結(jié)構(gòu)。通過在傳輸層之上集成一個(gè)Bundle層，DTN協(xié)議實(shí)現(xiàn)了應(yīng)用層和Bundle層單元的存儲(chǔ)和運(yùn)輸。空間網(wǎng)絡(luò)通信缺少端到端連接，因此鏈路延遲大、鏈路頻繁通斷并且誤碼率高。DTN具有適應(yīng)長延遲以及中斷頻繁的鏈路特性。DTN中輸入流量與輸出流量的速率往往存在巨大差異，雙向速率比可達(dá)1 000：1。另外，因?yàn)镈TN經(jīng)常部署在惡劣環(huán)境下，所以信息不能有效傳達(dá)到目的地，這導(dǎo)致接收端的信噪比和誤碼率等性能均不理想。常見的光通信網(wǎng)絡(luò)中誤碼率可達(dá)10-15～10-12，深空通信系統(tǒng)中僅能達(dá)到10-1，所以深空通信是DTN的一個(gè)主要應(yīng)用場景。DTN采用“存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)”的通信方式，當(dāng)源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間沒有直接相連的鏈路時(shí)，消息會(huì)被封裝成束并暫存在源節(jié)點(diǎn)；當(dāng)源節(jié)點(diǎn)與相鄰節(jié)點(diǎn)之間建立鏈路時(shí)，消息會(huì)被傳輸給相鄰節(jié)點(diǎn)，相鄰節(jié)點(diǎn)又會(huì)擇機(jī)將消息傳輸給下一跳節(jié)點(diǎn)，直至最終把消息傳遞給目的節(jié)點(diǎn)。由此可見，DTN適用于難以形成穩(wěn)定端到端鏈路以及高延遲的通信環(huán)境中，能夠有效適應(yīng)空間網(wǎng)絡(luò)的特點(diǎn)。

1 路由算法簡介

路由是空間網(wǎng)絡(luò)與DTN必備的基礎(chǔ)功能，高效的路由算法可以提升數(shù)據(jù)的交付效率，減少能量損耗與成本，并降低通信延遲。本節(jié)介紹了DTN與LEO衛(wèi)星網(wǎng)絡(luò)的代表性路由算法，并總結(jié)了它們主要的技術(shù)特點(diǎn)。

1.1 DTN路由算法

依據(jù)算法特性，我們可以將DTN路由算法分為基于轉(zhuǎn)發(fā)、復(fù)制、效用、編碼和社會(huì)關(guān)系的路由算法五大類，表1概括了每一類算法的主要特征與優(yōu)缺點(diǎn)。

▼表1 DTN路由算法分類總結(jié)

下面我們舉例說明不同特征DTN路由算法的典型代表。需要注意的是，一種DTN路由算法可能兼具多種特征。

（1）基于轉(zhuǎn)發(fā)的DTN路由算法

基于轉(zhuǎn)發(fā)的DTN路由也稱為單副本轉(zhuǎn)發(fā)路由，即消息在傳輸過程中只復(fù)制產(chǎn)生一個(gè)副本?；谵D(zhuǎn)發(fā)的DTN路由算法僅占用少量網(wǎng)絡(luò)資源，網(wǎng)絡(luò)擁塞風(fēng)險(xiǎn)低，但唯一副本一旦丟失，消息傳輸任務(wù)就會(huì)失敗。

首次接觸算法[1]和直接交付算法[2]是最基本的基于轉(zhuǎn)發(fā)的DTN路由算法。前者是指攜帶消息的節(jié)點(diǎn)將消息轉(zhuǎn)發(fā)給首次相遇的節(jié)點(diǎn)；后者是指不經(jīng)過任何中轉(zhuǎn)節(jié)點(diǎn)的轉(zhuǎn)發(fā)，源節(jié)點(diǎn)直接將消息發(fā)送給目的節(jié)點(diǎn)。兩種算法不依賴于任何知識(shí)，邏輯過程簡單，但是局限性很大。

接觸圖路由算法[3]是由上述兩種算法衍生的DTN路由算法。在空間DTN，特別是LEO衛(wèi)星網(wǎng)絡(luò)中，衛(wèi)星運(yùn)動(dòng)軌跡往往是可以預(yù)測的。根據(jù)這一特性，算法可以將衛(wèi)星接觸信息轉(zhuǎn)化為路由圖，之后依據(jù)性能需求選擇轉(zhuǎn)發(fā)路徑。

（2）基于復(fù)制的DTN路由算法

基于復(fù)制的DTN路由也稱為多副本路由，即一條消息經(jīng)過多次復(fù)制分別儲(chǔ)存在多個(gè)節(jié)點(diǎn)中，通過增加節(jié)點(diǎn)接觸次數(shù)的方式來提升成功投遞概率。這樣一來，即使某些副本丟失，也可以確保消息被傳輸?shù)侥康墓?jié)點(diǎn)。但是復(fù)制過多的副本會(huì)消耗大量的網(wǎng)絡(luò)資源，容易造成網(wǎng)絡(luò)擁塞；少量副本的復(fù)制未給算法性能帶來明顯提升。

Epidemic算法[4]是典型的基于復(fù)制的DTN路由算法，它采用泛洪機(jī)制將消息發(fā)送到未持有該消息的每一個(gè)節(jié)點(diǎn)上。該算法本質(zhì)上是一種以大量網(wǎng)絡(luò)資源消耗為代價(jià)來換取更高投遞率的路由算法。噴射與等待（SaW）算法[5]是由Epidemic算法和直接交付算法結(jié)合而成的，有效解決了Epidemic算法副本數(shù)量不受限制的問題。該算法預(yù)先定義一個(gè)最大副本數(shù)max_cop，消息經(jīng)過一次復(fù)制后max_cop-1，直至max_cop=1時(shí)停止復(fù)制。

（3）基于效用的DTN路由算法

效用函數(shù)是實(shí)現(xiàn)基于效用的DTN路由算法的關(guān)鍵，它是指將用戶關(guān)注的某些網(wǎng)絡(luò)參數(shù)量化為效用函數(shù)，通過函數(shù)計(jì)算得到最優(yōu)的中轉(zhuǎn)節(jié)點(diǎn)。效用函數(shù)的參數(shù)權(quán)重在很大程度上影響著算法性能，常用參數(shù)包括節(jié)點(diǎn)歷史相遇次數(shù)、節(jié)點(diǎn)運(yùn)動(dòng)軌跡以及網(wǎng)絡(luò)資源等。

概率路由協(xié)議（PRoPHET）算法[6]和基于能量感知的概率路由協(xié)議（EA-PEoPHET）算法[7]是兩種基礎(chǔ)的基于效用的DTN路由算法：前者在Epidemic算法的基礎(chǔ)上引入了預(yù)測投遞概率，僅將消息發(fā)送給預(yù)測概率較高的下一跳節(jié)點(diǎn)；后者將節(jié)點(diǎn)剩余能量作為效用函數(shù)，僅選擇能量充足的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn)。

（4）基于編碼的DTN路由算法

基于編碼的DTN路由算法可以降低信息傳輸?shù)恼`碼率以及鏈路中斷概率?；诓脸幋a的協(xié)作魯棒轉(zhuǎn)發(fā)（CORE）算法[8]和CCFM算法[9]都是根據(jù)節(jié)點(diǎn)歷史相遇次數(shù)、平均相遇時(shí)間間隔和節(jié)點(diǎn)剩余資源量等參數(shù)計(jì)算消息發(fā)送的下一跳節(jié)點(diǎn)。區(qū)別在于前者將消息編碼成了若干小碼塊，后者直接對節(jié)點(diǎn)進(jìn)行編碼。二者有效提高了消息的傳輸效率。

（5）基于社會(huì)關(guān)系的DTN路由算法

基于社會(huì)關(guān)系的DTN路由算法可以看作基于效用的DTN路由算法的改進(jìn)版本。我們將基于社會(huì)關(guān)系的DTN路由算法與人類社會(huì)網(wǎng)絡(luò)進(jìn)行類比：將節(jié)點(diǎn)看作人，節(jié)點(diǎn)之間的聯(lián)系如同人與人之間的聯(lián)系，并通過社會(huì)學(xué)知識(shí)進(jìn)行路由選擇。Bubble算法[10]依據(jù)節(jié)點(diǎn)相遇次數(shù)劃分社區(qū)，先將消息發(fā)送到社區(qū)，之后再由社區(qū)發(fā)送給具體節(jié)點(diǎn)。在Bubble算法基礎(chǔ)上，文獻(xiàn)[11]使用效用函數(shù)對副本數(shù)量進(jìn)行控制，有效降低了網(wǎng)絡(luò)能耗。其他具有代表性的算法還有目前最優(yōu)（TBSF）算法[12]和改進(jìn)的目前最優(yōu)（TBSFMODI）算法[13]。

1.2 LEO衛(wèi)星網(wǎng)絡(luò)路由算法

LEO衛(wèi)星通信系統(tǒng)可以實(shí)現(xiàn)真正意義上的全球無縫覆蓋。現(xiàn)有LEO衛(wèi)星網(wǎng)絡(luò)路由算法的設(shè)計(jì)主要考慮用戶業(yè)務(wù)類型、服務(wù)需求以及網(wǎng)絡(luò)的負(fù)載均衡能力。依據(jù)算法實(shí)施場景與特點(diǎn)，可將它們分為基于AI的LEO路由算法、LEO衛(wèi)星多徑路由算法和多層衛(wèi)星路由算法。表2總結(jié)了具有代表性的LEO衛(wèi)星網(wǎng)絡(luò)路由算法。

▼表2 LEO衛(wèi)星網(wǎng)絡(luò)路由算法

1.3 局限性

DTN賦予了空間網(wǎng)絡(luò)更加靈活的組網(wǎng)方式，這使得衛(wèi)星網(wǎng)絡(luò)在惡劣環(huán)境下依舊能夠擁有強(qiáng)大的通信能力。不可忽視的是，DTN依舊面臨逐跳傳輸、能量有限和場景復(fù)雜等挑戰(zhàn)。上述DTN路由算法并沒有真正應(yīng)用到LEO衛(wèi)星通信網(wǎng)絡(luò)環(huán)境中。另外，現(xiàn)有的LEO衛(wèi)星網(wǎng)絡(luò)還面臨星上資源受限、計(jì)算復(fù)雜度高和數(shù)據(jù)包失序等挑戰(zhàn)。

2 基于DTN的LEO衛(wèi)星網(wǎng)絡(luò)路由技術(shù)

我們提出一種基于DTN的LEO衛(wèi)星網(wǎng)絡(luò)路由技術(shù)，該技術(shù)充分利用LEO衛(wèi)星的管理能力，以應(yīng)對空間通信中鏈路頻繁中斷、延遲高等問題，動(dòng)態(tài)調(diào)整復(fù)雜斷環(huán)境下的路由策略，確保消息在非正常情況下正常傳輸。

2.1 時(shí)間片劃分

拓?fù)浣Y(jié)構(gòu)變化是衛(wèi)星網(wǎng)絡(luò)的常見問題，通過劃分時(shí)間片將LEO衛(wèi)星網(wǎng)絡(luò)劃分為n個(gè)異構(gòu)拓?fù)洌J(rèn)在每一個(gè)時(shí)間片中衛(wèi)星網(wǎng)絡(luò)拓?fù)涫窍鄬潭ǖ模?，依次?jì)算不同時(shí)刻的路由路徑，這樣可以有效應(yīng)對LEO衛(wèi)星網(wǎng)絡(luò)拓?fù)鋷淼淖兓r(shí)間片劃分方法有等長時(shí)間劃分和非等長時(shí)間劃分兩種。等長時(shí)間劃分是將時(shí)間劃分為等長的多個(gè)時(shí)間片段，但在等長時(shí)間間隔內(nèi)，衛(wèi)星網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可能發(fā)生巨大變化，這會(huì)導(dǎo)致預(yù)設(shè)路由策略失效；因此，該方法缺乏靈活性。非等長時(shí)間劃分雖能解決網(wǎng)絡(luò)拓?fù)渥兓瘑栴}，但由于劃分的時(shí)間片段過多又給路由制定帶來了巨大計(jì)算量。因此，我們采取二者結(jié)合的方式對時(shí)間片進(jìn)行劃分。

假設(shè)T1時(shí)刻A與B連通，T2時(shí)刻A與B斷開。若在T1～T2時(shí)間段內(nèi)，網(wǎng)絡(luò)中只有此鏈路發(fā)生通斷變化，那么依據(jù)非等長時(shí)間劃分方式，T1～T2就是一個(gè)時(shí)間片，由此可能形成如圖1所示的時(shí)間片。

如圖1所示，LEO衛(wèi)星鏈路通斷可能會(huì)出現(xiàn)T4～T5較短的時(shí)間片段。在該時(shí)間片內(nèi)，只有1條鏈路發(fā)生通斷。雖然對網(wǎng)絡(luò)拓?fù)溆绊懖淮?，但帶來的路由?jì)算問題更讓人擔(dān)心。為此，將所劃分的時(shí)間片長度與Td比較，若時(shí)間片長度小于Td，則將該時(shí)間片段與上一時(shí)間片段合并，并在上一時(shí)間片段內(nèi)提前將此鏈路設(shè)置為斷開，如圖2所示。

▲ 圖1 低軌衛(wèi)星鏈路通斷時(shí)間片劃分

▲ 圖2 短時(shí)間片的合并

2.2 路由過程

依據(jù)時(shí)間片劃分原理，在不同時(shí)隙內(nèi)，LEO衛(wèi)星網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不同；而在同一時(shí)隙內(nèi)，我們可認(rèn)為LEO衛(wèi)星網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)基本不變。因此，當(dāng)LEO網(wǎng)絡(luò)中各衛(wèi)星軌道確定時(shí)，便可計(jì)算出一個(gè)周期內(nèi)的時(shí)隙劃分。時(shí)隙劃分工作可由地面控制中心完成，劃分后廣播給各衛(wèi)星進(jìn)行存儲(chǔ)?；诖朔桨福覀儍H需在時(shí)隙更新時(shí)重新計(jì)算路由?；贒TN的LEO衛(wèi)星網(wǎng)絡(luò)路由過程如圖3所示。

▲ 圖3 LEO衛(wèi)星網(wǎng)絡(luò)路由過程

2.3 擁塞控制

由于分時(shí)隙計(jì)算網(wǎng)絡(luò)路由，若在某時(shí)隙內(nèi)產(chǎn)生流量突發(fā)情況，則容易引起節(jié)點(diǎn)擁塞。為提高路由效率，我們有必要設(shè)計(jì)擁塞控制機(jī)制。

LEO衛(wèi)星主要負(fù)責(zé)地面網(wǎng)關(guān)接入以及大部分?jǐn)?shù)據(jù)傳輸業(yè)務(wù)，因此當(dāng)某一衛(wèi)星節(jié)點(diǎn)擁塞，那么多因該地區(qū)業(yè)務(wù)量大或流量突發(fā)。不同軌道衛(wèi)星的覆蓋區(qū)域不同，人們可依據(jù)該特性來增加業(yè)務(wù)量大的區(qū)域的衛(wèi)星數(shù)目，以共同完成路由任務(wù)，避免網(wǎng)絡(luò)擁塞。對于流量突發(fā)情況，可利用衛(wèi)星節(jié)點(diǎn)自身內(nèi)存數(shù)與最大緩存數(shù)的比值實(shí)現(xiàn)監(jiān)控，計(jì)算方式如公式（1）：

其中，mn代表節(jié)點(diǎn)當(dāng)前可用內(nèi)存資源，mmax代表節(jié)點(diǎn)最大內(nèi)存容量。假設(shè)節(jié)點(diǎn)擁塞判定的閾值為85%，當(dāng)βmen大于0.85時(shí)，就認(rèn)為當(dāng)前節(jié)點(diǎn)出現(xiàn)擁塞。本節(jié)點(diǎn)發(fā)送擁塞報(bào)告至分組內(nèi)管理者，管理者在自身存儲(chǔ)網(wǎng)絡(luò)拓?fù)渲袑⒃摀砣l(wèi)星設(shè)為不可達(dá)，重新計(jì)算路由并下發(fā)至組內(nèi)其他LEO衛(wèi)星，直至節(jié)點(diǎn)發(fā)送擁塞解除報(bào)告，再置其為可到達(dá)，并更新組內(nèi)路由。

2.4 性能評(píng)估

為驗(yàn)證所提方案性能，我們將其與一種多層衛(wèi)星路由（MLSR）算法[23]在時(shí)延方面進(jìn)行對比。MLSR算法是基于互聯(lián)網(wǎng)協(xié)議（IP）設(shè)計(jì)的，可以為每個(gè)衛(wèi)星分配獨(dú)特的邏輯地址。不同于本文所提方案，MLSR算法適用于由GEO、MEO、LEO組成的3層衛(wèi)星網(wǎng)絡(luò)。該算法將高層衛(wèi)星作為管理者，將底層衛(wèi)星進(jìn)行分組，實(shí)現(xiàn)分層的網(wǎng)絡(luò)拓?fù)湫畔⑹占?。?dāng)組內(nèi)衛(wèi)星發(fā)生變化時(shí)，該算法可以動(dòng)態(tài)更新路由表。由于該算法采用了集中式路由策略，當(dāng)有新的衛(wèi)星加入網(wǎng)絡(luò)或者有衛(wèi)星離開網(wǎng)絡(luò)時(shí)，路由表無法及時(shí)更新，因此缺乏自治能力。當(dāng)衛(wèi)星網(wǎng)絡(luò)中有流量突發(fā)情況發(fā)生時(shí)，算法性能急劇下降。

利用STK組建衛(wèi)星網(wǎng)絡(luò)模型，在OPNET中進(jìn)行仿真實(shí)驗(yàn)，我們得到了所提方案與MLSR算法在時(shí)延性能方面的比較結(jié)果，如圖4所示。

▲ 圖4 平均時(shí)延對比

由于數(shù)據(jù)包發(fā)送時(shí)間間隔較短，MLSR算法在組內(nèi)衛(wèi)星發(fā)生變化時(shí)需要重新更新路由，而且當(dāng)其他組內(nèi)的消息在經(jīng)過本組衛(wèi)星節(jié)點(diǎn)時(shí)，由于更新后的路由還未在整個(gè)衛(wèi)星網(wǎng)絡(luò)更新，所以消息在發(fā)送到該組內(nèi)時(shí)會(huì)導(dǎo)致跳數(shù)增加。因此，MLSR算法的平均時(shí)延較高而且抖動(dòng)較大。相反，由于本文所提方案重點(diǎn)考慮了LEO分組變化時(shí)隙，且分組信息發(fā)生變化時(shí)可以及時(shí)在整個(gè)衛(wèi)星網(wǎng)絡(luò)更新，所以獲得了相對較低的時(shí)延。

3 結(jié)束語

本文首先介紹LEO衛(wèi)星網(wǎng)絡(luò)與DTN的基本概念與特征，之后系統(tǒng)總結(jié)了LEO衛(wèi)星網(wǎng)絡(luò)與DTN代表性的路由算法，并指出它們的典型特征，最后提出一種DTN輔助的LEO衛(wèi)星網(wǎng)絡(luò)自主路由技術(shù)，并描述了該技術(shù)的路由策略與擁塞控制過程。

隨著天地一體化網(wǎng)絡(luò)建設(shè)與5G甚至是6G通信服務(wù)的部署，LEO衛(wèi)星網(wǎng)絡(luò)路由技術(shù)必將擁有廣闊的應(yīng)用空間與發(fā)展前景。人們需要根據(jù)差異化場景與用戶差異化服務(wù)質(zhì)量（QoS）需求設(shè)計(jì)來實(shí)現(xiàn)不同的LEO衛(wèi)星網(wǎng)絡(luò)路由算法。另外，人們需要拓展衛(wèi)星網(wǎng)絡(luò)路由技術(shù)的應(yīng)用范圍與環(huán)境，包括在LEO、MEO和GEO網(wǎng)絡(luò)中的應(yīng)用，研究多層衛(wèi)星結(jié)合的路由技術(shù)，同時(shí)采用多個(gè)指標(biāo)來測評(píng)路由技術(shù)效果。