潘成勝，梁芷銘，石懷峰，3，孔志翔，3

（1.大連大學(xué)通信與網(wǎng)絡(luò)重點實驗室，遼寧大連 116622；2.大連大學(xué)信息工程學(xué)院，遼寧大連 116622；3.南京理工大學(xué)自動化學(xué)院，南京 210094）

0 概述

隨著互聯(lián)網(wǎng)的快速發(fā)展，我國網(wǎng)民數(shù)量截至2019年6 月已突破8 億［1］。由于我國通信設(shè)施建設(shè)水平處于國際領(lǐng)先地位，且衛(wèi)星發(fā)射數(shù)量逐年增多，目前衛(wèi)星在軌數(shù)已超過200顆，而傳統(tǒng)衛(wèi)星網(wǎng)絡(luò)設(shè)計完成投入使用后，其硬件升級更新迭代的成本巨大，難以滿足提升衛(wèi)星性能與降低升級難度與成本的網(wǎng)絡(luò)需求。文獻(xiàn)［2-3］通過將傳統(tǒng)衛(wèi)星網(wǎng)絡(luò)與網(wǎng)絡(luò)虛擬化技術(shù)相結(jié)合，從硬件中解耦出各種網(wǎng)絡(luò)功能需求，以解決衛(wèi)星上硬件模塊更新困難的問題。為增強這種抽象虛擬化對衛(wèi)星的改進(jìn)，相關(guān)研究認(rèn)為服務(wù)功能鏈（Service Function Chain，SFC）可以更好地提升空間信息網(wǎng)絡(luò)性能，即衛(wèi)星將接收到的服務(wù)請求中所用到的模塊功能抽象為虛擬網(wǎng)絡(luò)功能（Virtual Network Function，VNF），并將其串聯(lián)起來編排為一個有序的鏈?zhǔn)郊蠘?gòu)成服務(wù)功能鏈。

目前，針對SFC 的編排可分為構(gòu)建與映射2 個步驟。在構(gòu)建過程中將接收到的服務(wù)請求按照既定的策略進(jìn)行處理，而在映射過程中則需要考慮以下3 種情況：從通信資源方面考慮，需要最小化傳輸鏈路與衛(wèi)星間及層間的跳數(shù)；從內(nèi)存及計算資源方面考慮，由于衛(wèi)星負(fù)載及處理能力有限，需要合理利用衛(wèi)星上的資源；從鏈路健壯性方面考慮，應(yīng)有效解決衛(wèi)星節(jié)點動態(tài)失效問題［4-5］。文獻(xiàn)［6］提出一種禁忌搜索算法的SFC 部署算法，通過設(shè)置禁忌表在全網(wǎng)中搜索服務(wù)功能最優(yōu)的部署位置，但該算法僅考慮了資源利用率情況。文獻(xiàn)［7］采用一種面向VNF 環(huán)境的服務(wù)功能管理機(jī)制，主要通過維特比算法在候選節(jié)點中選擇部署開銷最小的服務(wù)功能，以降低部署成本，但該方法缺乏對通信資源消耗的考慮。

然而，以上研究未能對通信資源、計算資源消耗進(jìn)行整體優(yōu)化。針對該問題，本文構(gòu)建一種適用于空間信息網(wǎng)絡(luò)的抽象模型。該模型在空間信息網(wǎng)絡(luò)中動態(tài)拓?fù)湫纬煽煺盏幕A(chǔ)上，利用流量縮放因子及VNF 間的相互依附關(guān)系對服務(wù)請求構(gòu)建出合理的SFC。為解決SFC 映射過程中產(chǎn)生的隨機(jī)失效、路由規(guī)劃不合理以及資源實例碎片化等問題，本文提出一種最小資源消耗映射算法，以最小資源消耗為目標(biāo)形成SFC 映射路徑，最終得到SFC 構(gòu)建與映射間的最優(yōu)解決方案。

1 空間信息網(wǎng)絡(luò)拓?fù)淠Ｐ?/h2>

本文提出一種基于服務(wù)功能鏈映射的空間信息網(wǎng)絡(luò)抽象模型，具體如圖1 所示。中地球軌道（Medium Earth Orbit，MEO）層具有工作壽命長與仰角度良好等特點，在空間信息網(wǎng)絡(luò)的構(gòu)成中發(fā)揮重要作用。將在MEO 層通信范圍內(nèi)的低軌衛(wèi)星稱為在足印以內(nèi)，選擇一顆在低地球軌道（Low Earth Orbit，LEO）層中覆蓋時間最長的MEO 衛(wèi)星成為控制者，起到控制與轉(zhuǎn)發(fā)功能，一顆MEO 層衛(wèi)星可與足印范圍中的LEO 層衛(wèi)星形成集群并加以管控［8-10］。但由于空間信息網(wǎng)絡(luò)的高動態(tài)特性，MEO 層衛(wèi)星所在的足印區(qū)域內(nèi)LEO 衛(wèi)星會發(fā)生變化，導(dǎo)致MEOLEO 間的集群關(guān)系發(fā)生改變。因為同步地球軌道（Geostationary Earth Orbit，GEO）層具有對地靜止的特性，且模型中所有衛(wèi)星節(jié)點均對其可見，所以其可作為制定決策的控制者對網(wǎng)絡(luò)整體進(jìn)行管控，并對鏈路中出現(xiàn)MEO-LEO 的集群改變進(jìn)行調(diào)整，以保證服務(wù)請求質(zhì)量。這種分布式管控模型可有效緩解頻繁調(diào)用GEO 造成傳輸時延增大所帶來的缺陷，同時也保證了整個通信環(huán)境的穩(wěn)定性。

圖1 空間信息網(wǎng)絡(luò)抽象模型Fig.1 Abstract model of spatial information network

本文提出的空間信息網(wǎng)絡(luò)抽象模型工作流程如下：

步驟1當(dāng)GEO 層收到服務(wù)請求后，為降低衛(wèi)星上資源碎片化的消耗對其進(jìn)行拆分處理，抽象成一連串的有序SFC 并形成流表，準(zhǔn)備下發(fā)到LEO/MEO 層衛(wèi)星以響應(yīng)服務(wù)請求。

步驟2在GEO 層上生成的流表下發(fā)到各MEO-LEO 集群中并利用MEO 進(jìn)行調(diào)配，按照流表策略在相應(yīng)衛(wèi)星上虛擬出所需功能，以完成映射任務(wù)。其中：MEO 衛(wèi)星負(fù)責(zé)轉(zhuǎn)發(fā)與LEO 的調(diào)配工作，針對衛(wèi)星間的高動態(tài)性，若在某一時刻下的快照中衛(wèi)星的生命周期不滿足服務(wù)需求（LEO 即將脫離MEO 的足印區(qū)域），則需要MEO 關(guān)注并調(diào)配當(dāng)前LEO 周圍的其他LEO 對服務(wù)功能角色進(jìn)行補充；若當(dāng)前MEO 衛(wèi)星足印中沒有可以滿足服務(wù)的LEO 衛(wèi)星，則向GEO 衛(wèi)星發(fā)出申請，并查找其他可部署的MEO-LEO 集群以滿足服務(wù)請求。

步驟3LEO 接收到指令后按照流表要求完成SFC 映射以響應(yīng)服務(wù)請求。流表需要安全、穩(wěn)定以及可靠的約束條件，先保證鏈路的穩(wěn)定性，再考慮資源消耗以及傳輸效率的情況。

2 服務(wù)功能鏈的編排

服務(wù)功能鏈的提出是為了提供一個靈活、功能配置可拓展、面向?qū)ο笈c可重構(gòu)的一種網(wǎng)絡(luò)服務(wù)［11］。本文提出的SFC 編排設(shè)計思路如下：首先以流量縮放因子與VNF 之間的相互依附關(guān)系為約束原則，以降低衛(wèi)星上以及衛(wèi)星間通信資源開銷為目標(biāo)對SFC進(jìn)行構(gòu)建，為SFC 映射找到最小資源開銷路由策略奠定基礎(chǔ)；其次考慮到星上拓?fù)涞母邉討B(tài)性，采用基于A*算法的本文算法進(jìn)行SFC 映射，匹配出可得到最小資源開銷的路由策略。

2.1 虛擬網(wǎng)絡(luò)功能的流量縮放因子及依附關(guān)系

隨著VNF 技術(shù)的逐漸成熟，一些功能從硬件實現(xiàn)中解放出來以節(jié)約迭代升級成本，實現(xiàn)通過軟件定義的方式處理業(yè)務(wù)需求逐漸成為一種發(fā)展趨勢［7］。在執(zhí)行網(wǎng)絡(luò)請求處理的過程中，一條服務(wù)請求對應(yīng)一條SFC，而每條SFC 由源節(jié)點、有序的VNF以及目的節(jié)點組合而成。若要處理一條SFC 請求，則需通過相應(yīng)網(wǎng)絡(luò)資源構(gòu)建出這些虛擬功能模塊，再按照一定的策略映射到網(wǎng)絡(luò)當(dāng)中，才能保證提供可靠而穩(wěn)定的服務(wù)［12-14］。

虛擬網(wǎng)絡(luò)功能基于其特性按照一定的比率放大或縮小經(jīng)過的數(shù)據(jù)流，本文稱其為流量縮放因子ω。在此假設(shè)一個前提：為了避免流性能的退化，不可將流拆分成多條進(jìn)行傳輸。

圖2 說明了流量縮放因子對構(gòu)建SFC 的影響。其中：S與D分別為源節(jié)點與目的節(jié)點，M1、M2、M3均為空間信息網(wǎng)絡(luò)中的衛(wèi)星節(jié)點；N1與N2為抽象出的VNF，N1的流量縮放因子為2，即由其功能屬性會導(dǎo)致經(jīng)過的數(shù)據(jù)流放大2 倍，N2的流量縮放因子為0.5，則會使經(jīng)過的數(shù)據(jù)流縮小1/2，空心圓圈表示該衛(wèi)星節(jié)點僅作為跳轉(zhuǎn)節(jié)點未使用虛擬功能；服務(wù)請求為a個單位的數(shù)據(jù)流大小，橫向箭頭表示鏈路，縱向箭頭表示生成抽象，鏈路上數(shù)字表示當(dāng)前鏈路中的數(shù)據(jù)流大小。從圖2 可以看出，通過分別將流量縮放因子較大的VNF 與縮放因子較小的VNF 放在構(gòu)建的服務(wù)功能鏈末尾與鏈?zhǔn)?，可降低傳輸過程中帶寬資源的壓力。與此同時，還需考慮到在SFC 構(gòu)建時VNF 間的相互依附關(guān)系，需將有上下文聯(lián)系的VNF放在一起考慮，比如加密與解密是不可調(diào)換順序的功能，不能為降低通信資源壓力而破壞這種相互依附關(guān)系。因此，整體關(guān)注SFC 的構(gòu)建可達(dá)到降低鏈路通信資源開銷的目的。

圖2 流量縮放因子對帶寬的影響Fig.2 Effect of traffic scaling factor on bandwidth

2.2 建模分析

本文將空間信息網(wǎng)絡(luò)抽象為無向圖P(U，E)的形式，其中，V表示網(wǎng)絡(luò)中所有提供處理能力的衛(wèi)星節(jié)點集合，對于每個衛(wèi)星節(jié)點u∈U，E表示所有衛(wèi)星間的物理鏈路集合，每條鏈路e∈E。B(u1，u2)表示帶寬，ζ=(γ1，γ2，…，γn)表示VNF 資源集合，γu，m表示衛(wèi)星上節(jié)點u存在網(wǎng)絡(luò)虛擬功能為m的虛擬資源類型，單顆衛(wèi)星可抽象出多類資源，用C(v)表示衛(wèi)星節(jié)點的計算資源容量。

當(dāng)系統(tǒng)接收到服務(wù)請求f進(jìn)入到網(wǎng)絡(luò)中時，用E表示經(jīng)過空間網(wǎng)絡(luò)中物理節(jié)點u1，u2的服務(wù)請求路徑：

若衛(wèi)星上節(jié)點針對接收的服務(wù)請求f進(jìn)行處理時產(chǎn)生一條多跳路徑，其中跳轉(zhuǎn)可能在衛(wèi)星節(jié)點間發(fā)生，也可能在一顆衛(wèi)星抽象出的不同虛擬功能間發(fā)生。用f(i，u′)表示服務(wù)請求f經(jīng)過i次跳轉(zhuǎn)后在物理節(jié)點u′的位置上，假設(shè)共有N跳，i∈[1，N]，則有：

將服務(wù)請求中所需的虛擬網(wǎng)絡(luò)功能γ部署到空間信息網(wǎng)中的物理節(jié)點u上，則有：

針對服務(wù)請求f中考慮到的網(wǎng)絡(luò)虛擬功能之間的依附關(guān)系，用“＞”表示VNF 間調(diào)用的先后順序，γa＞γb表示虛擬網(wǎng)絡(luò)功能γb依附γa，需要先處理γa后再處理γb，則有：

這種依附關(guān)系具有傳遞性，例如γa＞γb且γb＞γc，則γa＞γc。

用ratio(γ)表示網(wǎng)絡(luò)虛擬功能類型為γ的流量縮放因子，定義分別代表服務(wù)請求f流入和流出節(jié)點u時對流量大小影響的比率：

若存在依附關(guān)系γa＞γb，需將a放在b后進(jìn)行部署，且有如下約束條件：

costi表示VNF 的通信資源開銷，當(dāng)僅存在一個VNF 時，costi=ωi=ratio(γ)。若處理式（6）這種相互依附關(guān)系的VNF 后，對于后續(xù)沒有與自身存在依附關(guān)系的虛擬網(wǎng)絡(luò)功能個體或集群，則需要將γa放在γb前，且存在以下約束：

其中，(1-ratioa)/costa＜(1-ratiob)/costb，將(1-ratioa)/costa看作γa的屬性，其值越小則在SFC 中的擺放位置越靠前。

考慮到減小衛(wèi)星上VNF 部署實例的碎片化，針對SFC 中的待映射VNF，有且僅有一次被部署到衛(wèi)星節(jié)點上：

考慮到實際傳輸時負(fù)載均衡且符合物理實際，對于任意一顆衛(wèi)星，待處理所需的計算資源總和需小于該衛(wèi)星節(jié)點實際最大值：

同理，所有服務(wù)請求f部署到衛(wèi)星節(jié)點所需的通信資源總和應(yīng)小于該物理節(jié)點所能提供的最大帶寬傳輸能力，應(yīng)滿足：

為了能夠更細(xì)粒度地利用衛(wèi)星上資源，衛(wèi)星節(jié)點u上的虛擬網(wǎng)絡(luò)功能可被多條服務(wù)請求申請使用：

為了最小化空間信息網(wǎng)絡(luò)中衛(wèi)星節(jié)點的計算資源與通信資源，并提高服務(wù)請求接收率，將目標(biāo)函數(shù)設(shè)置為：

2.3 SFC 映射的問題描述

A*尋路是在Dijskra 算法的基礎(chǔ)上增加預(yù)測函數(shù)演變而來，通過對其選擇合理的搜索方向逐漸向目標(biāo)節(jié)點靠近，從而找到最短路徑。

其中，f(s，e)表示從起始點s經(jīng)過當(dāng)前節(jié)點x到目的節(jié)點e所需的總開銷，g(s，x)表示從起始點s到當(dāng)前節(jié)點x產(chǎn)生的實際通信開銷，h(x，e)表示從當(dāng)前節(jié)點x到目的節(jié)點e的開銷評價。

為了使源節(jié)點s找到目的節(jié)點e的路徑最短，以μ(x)作為約束h(x，e)的權(quán)值，使其小于等于實際開銷可控制算法搜索目標(biāo)節(jié)點范圍，當(dāng)其值大于1 時可使算法增大預(yù)測函數(shù)權(quán)重以有效增大搜索范圍，且在周圍節(jié)點不具備部署能力時可快速跳出局部最優(yōu)限制。

衛(wèi)星間通信開銷g(s，x)包括鏈路丟包率、通信資源占用比率以及鏈路間時延，本文將通過綜合這些數(shù)據(jù)加權(quán)對后繼節(jié)點進(jìn)行計算。

其中：l(s，x)表示鏈路丟包率，鏈路丟包率增加表示當(dāng)前鏈路段擁塞，若達(dá)到閾值表示該段鏈路不具備映射條件，需要重新進(jìn)行路由分配；b(s，x)表示通信資源占用比率，其反映鏈路通信資源使用情況；d(s，x)表示時延，其包括排隊時延、處理時延以及傳播時延；α、β、τ（賦權(quán)參數(shù)）在算法中以1∶1∶1 進(jìn)行調(diào)配，實際可根據(jù)服務(wù)需求特點適當(dāng)調(diào)節(jié)，且α+β+τ=1。

開銷預(yù)測函數(shù)h(x，t)是由待選衛(wèi)星x與其相鄰衛(wèi)星t的星間通信開銷平均值，以及經(jīng)過加權(quán)處理后的衛(wèi)星間歐幾里得距離得出，具體如式（15）所示：

其中：開銷預(yù)測函數(shù)若要達(dá)到效果必須小于實際開銷結(jié)果；λ為衛(wèi)星間鏈路帶寬占用率，表示衛(wèi)星間鏈路傳輸擁塞情況；考慮傳輸距離也是傳播時延產(chǎn)生的條件，用des(x，t)表示衛(wèi)星間歐幾里得距離，且其值越小傳輸距離越短，通信所用延遲時間越短，即可得到開銷預(yù)測函數(shù)h(x，t)。

2.4 服務(wù)功能鏈的映射算法

本文提出一種空間信息網(wǎng)絡(luò)服務(wù)功能鏈映射算法，選擇映射路徑時可通過預(yù)測函數(shù)對衛(wèi)星節(jié)點的選取進(jìn)行評價分析，并根據(jù)服務(wù)需求通過減小預(yù)測函數(shù)的權(quán)值來加快搜索范圍收斂速度，或為了獲得全局最優(yōu)解，增大權(quán)值范圍跳出局部最優(yōu)，算法的具體步驟如下：

本文統(tǒng)計針對當(dāng)前快照中衛(wèi)星上資源抽象出的虛擬功能種類，判斷此衛(wèi)星能否滿足服務(wù)請求，open表中存放的都是待處理的衛(wèi)星節(jié)點，通過對當(dāng)前節(jié)點以及周圍相鄰節(jié)點F 值的計算與比較，將當(dāng)前開銷最小的點q標(biāo)記為父節(jié)點，再計算父節(jié)點q周圍的節(jié)點開銷并進(jìn)行比較，經(jīng)過迭代計算持續(xù)更新在搜索中找到更優(yōu)秀開銷的節(jié)點作為父節(jié)點，并最終得到SFC 映射路徑輸出。

本文采用一種可以避免出現(xiàn)重路由情況發(fā)生的策略［15-17］，每當(dāng)算法搜索過程中出現(xiàn)候選節(jié)點與下一跳衛(wèi)星鏈路通信斷開的情況時，為避免發(fā)生重路由會立刻反饋至MEO/GEO 衛(wèi)星，并同時生成新的服務(wù)功能鏈映射路徑。針對節(jié)點失效計算時原路徑上局部節(jié)點失效的問題，本文可從鏈路通信斷開處的節(jié)點進(jìn)行填補以更新出新的路徑策略。

3 實驗結(jié)果與分析

3.1 仿真實驗參數(shù)設(shè)置

本文仿真實驗配置環(huán)境如下：使用配置為64 位Ubuntu操作系統(tǒng)，Intel?CoreTMi7-3770 CPU@3.40 GHz處理器，16 GB 內(nèi)存的PC 機(jī)上運行，使用編程語言Python3.6 在JetBrains PyCharm 2018.1.4 x64 平臺編寫。

OPNET 軟件可模擬空間信息網(wǎng)絡(luò)中衛(wèi)星拓?fù)湟约靶l(wèi)星對于VNF 的抽象，其中三顆GEO 位于對地靜止軌道，經(jīng)度為0°，東經(jīng)120°，西經(jīng)120°。MEO、LEO 分別參照Odyssey 與Iridium 分布，衛(wèi)星仿真參數(shù)如表1所示。

表1 衛(wèi)星仿真參數(shù)Table 1 Satellite simulation parameters

為盡可能還原空間信息網(wǎng)絡(luò)中的運行情況，本文模擬出以下3 種情況：

1）使用OpenStack 模擬服務(wù)請求需求生成衛(wèi)星上VNF 并管理，VNF 仿真參數(shù)如表2 所示。

表2 VNF 仿真參數(shù)Table 2 VNF simulation parameters

2）使用OpenDaylight 控制器對衛(wèi)星拓?fù)溥M(jìn)行控制管理，采用Openflow 生成模擬服務(wù)請求的流，從而實現(xiàn)流量經(jīng)由虛擬機(jī)生成VNF。

3）預(yù)設(shè)每條服務(wù)請求包含的VNF 數(shù)量不確定，并服從［3，10］的均勻分布，接收的服務(wù)請求服從［100，300］的泊松分布［18-19］。

3.2 算法對比分析

實驗將本文算法與隨機(jī)映射RAND 算法以及離線布局OMD［20］算法在統(tǒng)一網(wǎng)絡(luò)環(huán)境中進(jìn)行仿真分析比較。由于映射的開銷主要源自于滿足服務(wù)需求時達(dá)成功能實現(xiàn)的計算資源和內(nèi)存資源的消耗，以及在通過算法構(gòu)建鏈路時路徑中產(chǎn)生的通信資源消耗。為最小化映射開銷，本文通過流量縮放因子及VNF 間相互依附關(guān)系構(gòu)建出一條合理的SFC，利用SFC 的構(gòu)建來降低在衛(wèi)星間和層間通信時通信資源的消耗，再通過本文算法找到SFC 映射的最佳路徑，以減少衛(wèi)星上資源碎片化與計算內(nèi)存資源的開銷。

總資源消耗表示在某一快照中滿足服務(wù)請求下，各個節(jié)點計算資源、通信資源以及內(nèi)存資源的使用情況。由于衛(wèi)星的處理能力主要由CPU 計算資源體現(xiàn)，因此在綜合考慮消耗多種資源的情況下，統(tǒng)一將CPU 占用50%，其他資源平均分配。如圖3 所示，隨著任務(wù)請求數(shù)增加，本文算法可在預(yù)測函數(shù)中進(jìn)行快速擇優(yōu)，以滿足高并發(fā)情況下的服務(wù)支持，且本文算法的總資源消耗率較RAND 算法、OMD 算法分別平均降低27%和6%。

圖3 3 種算法的總資源消耗率對比Fig.3 Comparison of total resource consumption rate of three algorithms

在處理請求時延方面，本文算法同樣有穩(wěn)定的收斂趨勢，隨著SFC 任務(wù)請求數(shù)的不斷增加，并發(fā)業(yè)務(wù)量提高依舊可以表現(xiàn)出良好的處理能力。圖4 指標(biāo)反映了本文算法對于服務(wù)請求、構(gòu)建鏈路的路由選擇效率以及擁塞情況的處理能力，且所得結(jié)果顯示在高并發(fā)環(huán)境下，本文算法具有最小的處理請求時延結(jié)果，較OMD 算法處理時延平均降低了19%。因此，隨著并發(fā)業(yè)務(wù)量增多，本文算法可更快找到SFC 映射解決方案。

圖4 3 種算法的處理請求時延對比Fig.4 Comparison of processing request delay of three algorithms

4 結(jié)束語

本文提出一種適用于SFC 快速構(gòu)建與映射的空間信息網(wǎng)絡(luò)抽象模型。該模型根據(jù)流量縮放因子及VNF 間的相互依附關(guān)系構(gòu)建出合理的SFC，并針對SFC 映射過程中的隨機(jī)失效等問題，提出一種服務(wù)功能鏈優(yōu)化算法。仿真結(jié)果表明，該算法可在較高的并發(fā)服務(wù)請求下，有效減小請求處理時延、降低映射時的總資源消耗，滿足網(wǎng)絡(luò)功能服務(wù)需求。下一步將采用神經(jīng)網(wǎng)絡(luò)算法對本文空間信息網(wǎng)絡(luò)模型進(jìn)行優(yōu)化，通過調(diào)整各層空間中GEO、MEO、LEO 的數(shù)量得到最優(yōu)部署方案，在降低空間部署成本的同時顯著提高空間網(wǎng)絡(luò)服務(wù)請求速率。