空天地協同的邊緣云服務功能鏈動態編排方法

喬文欣，盧 昱，劉益岑，李志偉，3，李 璽

(1.陸軍工程大學 無人機工程系，河北 石家莊 050003；2.中國人民解放軍63660部隊，河南 洛陽 471000；3.空軍石家莊飛行學院 93413部隊，河北 石家莊 050003)

近年來，隨著衛星互聯網技術的高速發展，以及日益增長的空天資源需求，利用衛星網絡輔助地面無線網絡進行泛在接入，并構建空、天、地協同的融合網絡，已成為未來衛星互聯網發展的重要方向。其優勢在于能夠為人口稀疏地區提供遠距離通信以及應對災后應急通信需求[1]，并且有效擴展地面網絡覆蓋范圍，同時有利于與5G[2]、物聯網[3]和云計算等新技術新場景的融合應用。為了解決衛星網絡星上資源和計算能力有限的問題，研究者提出將包含移動邊緣計算(Mobile Edge Computing，MEC)的地面網絡、近地平臺和衛星網絡結合起來，構成空天地協同[4]的邊緣云(Space-Air-Terrestrial aided Mobile Edge Cloud，SAT-MEC)網絡系統，旨在將豐富的頻譜、計算和存儲資源協同控制和管理起來，以完成多樣化的地空聯合任務。同時，未來物聯網、云計算網絡等新網絡場景的快速發展，智能設備數量和用戶需求也隨之激增，如何將有限的計算、存儲和帶寬等網絡資源及服務資源充分利用起來，并在海量的終端數據上實現智能化管控，以獲得更高效且優質的網絡性能和服務質量，成為了一個重要的研究方向。

軟件定義網絡(Software-Defined Networking，SDN)和網絡功能虛擬化(Network Function Virtualization，NFV)等新型網絡技術的出現為解決該類多源異構網絡的管理和控制問題帶來了新的解決方案，將SDN/NVF應用于SAT-MEC網絡，對于提升網絡的性能表現和管理控制的靈活度，以及擴展邊緣計算網絡的應用范圍和場景都顯得至關重要[5]。隨著應用場景的擴展，如何在復雜且動態變化的網絡狀態下，滿足多樣化的用戶服務需求和業務需求成為研究的重難點之一[6]。在SDN/NFV架構下，將虛擬網絡功能(Virtualization Network Function，VNF)組件以邏輯鏈路的方式有序地組合成為一個服務功能鏈(Service Function Chain，SFC)，引導用戶流量依照一定的策略通過，對于SAT-MEC網絡的動態資源管理和多樣化服務質量提升是一個很好的技術途徑。

當前已有的一些關于空天地協同網絡的研究，其中大部分側重于體系架構設計[7-10]、路由路徑規劃[2]和通信、計算等網絡資源的分配問題[11-13]方面，對服務資源管理和服務質量優化的研究[14-16]相對較少。在體系架構設計方面，空天地協同網絡的概念和定義是隨著新型網絡技術和應用場景的發展而逐漸演進的。文獻[7]和文獻[8]分別提出了早期僅包含衛星和地面通信網絡的星地融合網絡系統的概念和定義，同時給出了對應的體系模型和應用場景。文獻[9]提出了一種無人機輔助的移動邊緣計算網絡架構，文獻[10]設計了一種包含衛星、空域平臺和地面通信系統的跨域多層協同網絡。可以看出，隨著5G、物聯網、云計算和邊緣計算等新型網絡技術的發展，空天地協同網絡的概念和定義也隨之不斷擴充和演進，研究側重于結合邊緣計算的空天地協同網絡，即SAT-MEC網絡；在路由路徑規劃方面，文獻[2]設計了利用SDN/NFV技術融合衛星網絡的未來5G網絡的架構，并提出了一種以網絡編碼的方式分流星地流量，使得其能夠實現在星地一體化環境下的多路徑路由分流；在通信和計算等網絡資源管理和優化方面，文獻[11]將低軌衛星作為邊緣計算節點為終端提供接入和計算服務，針對邊緣計算衛星用戶的計算和通信資源分配問題，考慮了網絡拓撲、可用通信資源和衛星相對運動狀態，提出一種基于廣度優先搜索的生成樹算法及計算路由路徑和調度通信資源。文獻[12]針對5G衛星網絡資源分配和管理問題，提出了基于SDN/NFV的網絡切片管理方案，以滿足不同應用場景和業務的服務質量需求。文獻[13]針對空天地協同網絡中的車聯網應用場景進行了研究，提出了一種分層的網絡架構，利用分級控制器對共享資源進行動態的管理，并且展望了提供定制化虛擬網絡服務、利用軟件定義網絡集中控制管理異構資源和如何保護軟件定義網絡控制器以及車聯網安全等開放性研究方向，但未進行深入探討。可以看出，上述研究多將空天網絡視為中繼網絡，即利用衛星網絡和近地平臺覆蓋范圍廣且可移動性強的優勢輔助地面網絡完成通信和計算等任務，但忽略了將任務和業務直接在空天網絡上處理的可行性，也未考慮如何將空天網絡的服務資源加以利用。

在服務資源管理和優化方面，現有的研究大多采用經典的精確求解算法[14]和啟發式算法[15-16]進行求解。文獻[14]考慮到不同服務和業務資源需求，以及空天節點具備移動性的特點，將問題建模為一個混合整數線性規劃問題，提出了基于移動感知的聯合服務部署和路由方法，并利用優化問題求解器在小規模場景下進行了仿真實驗。相比于靜態路由方法，顯著降低了服務成本和端到端時延，但針對大規模場景下的求解效率有待提升。文獻[15]設計了一種基于SFC的可重構服務框架，考慮了空天地網絡架構下的VNF映射和服務路由問題，設計了車聯網場景下的服務功能部署方法，采用了一種節點特征和資源均衡的啟發式貪婪算法進行求解。文獻[16]在星地協同網絡架構下提出了一種橫向多域服務功能鏈編排框架，利用多域控制器協同控制的方法來協調域內與域間的SFC編排，并設計了一種啟發式服務功能鏈映射算法。啟發式算法的計算效率較高，收斂速度相對較快，但存在得不到全局最優解的風險。同時，由于空天地網絡規模與所承載數據流量、類型的不斷增長，利用傳統的精確算法和一般啟發式算法解決SAT-MAC網絡服務功能鏈動態編排問題時，可能面臨計算復雜度高、收斂速度慢和易陷入局部最優等問題。在線優化算法雖然適用于動態場景且學習效率高，但依賴于網絡全局信息感知，且學習過程對通信資源的消耗較大。量子機器學習(Quantum Machine Learning，QML)是將經典機器學習算法與量子計算相結合形成的新興研究領域，其利用量子計算高并行與加速顯著的特性來提升傳統算法的運算效率和求解精度，目前已在量子優化、量子分類、量子聚類、量子降維和量子深度學習算法等領域產生了一些研究成果[17]。在量子優化方面，文獻[18]將可重構網絡資源的動態監測過程建模為0-1動態規劃問題，并提出了一種改進的量子遺傳算法來尋求監測代理部署問題的近似最優解，能夠以較低通信代價完成資源信息收集并更新部署，明顯優于同類算法。因此，對于SAT-MEC網絡的服務功能鏈動態編排求解中存在的計算量大且規模大等問題，考慮采用高并行的QML算法來處理計算耗時的路徑選擇優化過程，以提高SFC編排方法的整體效率和求解精度。

為此，針對SAT-MEC網絡中的SFC動態編排問題，筆者設計了一種SAT-MEC網絡場景下結合QML的SFC動態編排方法。首先，提出SAT-MEC網絡的SFC動態編排模型，將其建模為以最小化端到端時延為優化目標的經典整數線性規劃(Integer Linear Programming，ILP)模型；在此基礎上，將服務功能鏈動態編排過程中的路徑選擇問題轉化為基于開放量子隨機行走的隱馬爾可夫(Open Quantum Random Walk based Hidden Markov Model，OQRW-HMM)模型；最后，采用一種量子回溯解碼(Quantum Backtrack Decoding，QBD)方法對模型進行求解，并驗證其有效性和效率。

1 系統模型和問題描述

1.1 SAT-MEC網絡場景下的SFC動態編排

如圖1所示，筆者提出了一種SAT-MEC網絡場景下的服務功能鏈動態編排架構。其中，圖1左部為SAT-MEC網絡虛擬化的過程，描述了將空天地協同組成的底層物理網絡資源通過網絡虛擬化技術抽象為虛擬網絡資源的過程。物理結構層面，底層物理網絡可以分為空、天、地三個層面，分別為低軌道(Low Earth Orbit，LEO)衛星組成的空間網絡層、無人機組成的近地平臺層以及由核心云數據中心、分布式邊緣云數據中心和移動邊緣云設備組成的地面網絡層。由于衛星覆蓋范圍相對較廣，可認為衛星節點對當前地面網絡實現全范圍覆蓋，無人機節點為部分覆蓋，上述三層網絡之間采用無線通信的方式實現連通。

圖1右部為抽象出來的網絡拓撲圖及服務功能鏈編排過程，上層有發出請求生成的SFC信息與當前網絡拓撲實時狀態信息匯總到服務功能SFC資源鏈分配控制層，由服務功能鏈資源分配控制層通過API對網絡拓撲中的VNF映射、流量路由和虛擬化資源進行靈活動態的管理。部分地面網絡節點和天空網絡節點上部署VNFs以實現服務功能鏈。依照不同用戶提出的服務請求，可以對服務功能鏈資源進行動態編排和調整。

SFC-1、SFC-2、SFC-3、SFC-4分別代表4個不同服務功能鏈請求和相應的任務資源提供策略，SFC-2和SFC-4的流量經過了空天網絡節點所承載的VNF。此時，空天網絡節點具有兩個主要作用，一是平衡流量負載，當地面網絡某些路由節點發生流量擁塞時，可利用空天節點進行傳輸以減輕流量負載；二是縮短邏輯傳輸距離，減少端到端傳輸跳數。車聯網通信場景下，假設有兩個服務請求SFC-1和SFC-2，源節點為車載服務器，目的節點為地面服務器，其流量需要按順序依次通過VNF1-VNF2-VNF4-VNF5，以滿足所需的服務需求。通常情況下，SFC-1路徑可以經過地面節點N1-N2-N4-N5到達終點完成通信，但地面節點發生流量擁塞時，則包含空中節點的SFC-2路徑途徑節點N1-N7-N8-N5同樣可以完成通信并滿足服務需求。海上網絡通信場景下，假設有兩個服務請求SFC-3和SFC-4，源節點為海上船舶服務器，目的節點為地面服務器，其流量需要按順序通過VNF2-VNF4，SFC-3路徑經過地面節點N1-N2-N3-N4到達終點完成通信，SFC-4路徑則通過空中節點N7-N8到達終點。可以看出，SFC-4路徑借助于空中節點顯著地減少了路徑跳數，更適用于偏遠稀疏地區的通信接入和網絡服務需求。

相比于常規地面邊緣云網絡系統，結合了空天地網絡的邊緣云系統在平衡網絡負載和優化傳輸路徑方面具備更多優勢，但由于空天節點的高移動性特點，也使得SFC編排和資源分配問題的難度隨之增加。因此需要建立服務功能鏈動態編排模型，并設計更加高效的算法來對模型進行求解。

圖1 SAT-MEC網絡場景下的SFC動態編排示意圖

1.2 邊緣云SFC動態編排問題描述

為便于表達和分析，將定義一個SAT-MEC網絡系統。

(2)服務請求R：假設一組給定的虛擬網絡服務請求R=(E，F，D，Td)，對于每個服務請求r∈R，E是請求所屬的邊緣云，F是一組預先定義順序的VNFs序列，D和Td為服務請求的時延需求和持續時間。

研究的服務功能鏈動態編排問題可以描述為：假設給定一個底層物理網絡G=(N，L)和一組新的服務請求R。對于每個動態到達的服務請求，關鍵在于如何將VNF映射到合適的邊緣云節點和核心云節點上，并引導用戶流量有序通過部署VNFs的節點，且在滿足計算、帶寬和時延等約束的情況下，使得當前請求所在網絡端到端時延最小。

2 整數線性規劃模型

SAT-MEC網絡場景與移動邊緣云場景類似，對于通信服務的時延要求較高，因此將端到端時延作為網絡優化目標。所涉及主要符號及描述見表1。

表1 主要符號及描述

在1.2節的基礎上，將空天地協同的邊緣云服務功能鏈動態編排問題描述為ILP模型，優化目標為最小化端到端時延，同時滿足資源約束和用戶請求約束，優化目標及約束條件的表達式如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

其中，式(1)為端到端時延最小化的目標函數，為VNF節點處理時延和鏈路傳輸時延之和；式(2)和式(3)分別表示VNF映射約束和虛擬鏈路映射約束，保證一對一的映射關系；式(4)和式(5)分別代表路徑選擇和時延，使其滿足請求所需的VNFs和時延約束；式(6)和式(7)是邊緣云容量和鏈路容量約束，確保映射的SFC資源需求不超過底層邊緣云節點和鏈路的資源限制；式(8)為鏈路持續時間約束，確保連接空天節點的鏈路可持續時間滿足請求的生命周期。上述ILP模型描述的SFC動態編排問題是NP-hard的，使用現有優化求解器很難找到合適的多項式時間內的求解算法，一般啟發式算法和在線優化算法也無法同時滿足SAT-MEC網絡SFC動態編排的計算效率需求與通信資源約束。因此，為提高當前大規模場景下的近似最優解求解效率，筆者提出一種基于QML的解決方法，旨在借助量子算法并行計算能力來解決求解效率問題。

3 OQRW-HMM算法

3.1 OQRW-HMM模型建模

在SFC動態編排問題中，對于每條確定的服務請求所需的VNFs選擇合適的節點實例化，并使得流量依次通過，遍歷所需服務功能形成服務功能鏈以滿足用戶的服務請求，這個過程就是服務功能鏈路徑選擇過程。其中，每個服務功能最匹配的實例化位置屬于當前系統中不可見的狀態，需要通過觀測已知狀態來推測其最可能的情況，因而具備隱馬爾可夫特性。同時，由于空天節點具有移動性，且用戶需求為動態到達的情況下，網絡系統的狀態規模巨大，使得傳統HMM方法無法在有限時間內獲得可行解，因而考慮利用QML并行計算的特點提升求解效率。其中，OQRW算法[19]是QML領域中開放量子系統的一個經典模型，能夠以有向完全圖的形式描述量子態的演化與轉移過程，之后通過觀測量子態的演化以推測出最大可能的行走路徑，該模型的優勢在于將約束條件下量子回溯解碼的過程以并行方式計算，能夠大幅提高問題的求解效率。因此，將采用OQRW-HMM模型來對服務功能鏈編排問題中的服務功能鏈路徑選擇過程進行建模并求解。首先，將服務功能鏈路徑選擇過程用OQRW-HMM狀態轉移模型描述，之后通過基于OQRW-HMM的QBD算法以回溯解碼給定觀測序列的方式，找出與之匹配的最大可能隱藏狀態序列，即當前SFC需求所對應的SFC最優服務路徑。

圖2 量子隱馬爾可夫模型的狀態轉移

(1)I={|i〉}為有限隱藏狀態集，{|i〉}i∈N為Hc的標準正交基，在這里隱藏狀態是由于服務功能實例化的位置未知導致的。當I={|1〉}時代表VNFvx映射到節點ni；I={|0〉}時，則未映射到節點ni；

(2)K?T為T步行走時的觀測狀態空間，{|oj〉}j∈N為觀測狀態k∈K?T的標準正交基。當oj={|1〉}j∈N時，代表VNFvx為服務類型u∈U，oj取0則為否；

(5)Π={π1，k，πM}表示初始狀態的集合，πi為VNFvx映射到節點ni時的初始狀態。

3.2 量子回溯解碼

為了確定OQRW-HMM模型中最大可能的隱藏狀態序列，在初始化QORW-HMM模型的基礎上，采用QBD方法以回溯解碼觀測信息的方式對模型進行求解，主要步驟如下：

(9)

其中，觀測序列o1o2…oT為請求中VNFs組成的SFC序列，則T為VNFs的個數。

(10)

(3) 使用交換算子，為避免空間坍縮，將交換算子I?I?S作用于H?Hc?K?T，得到Dn(π)：

(11)

(12)

(5) 重復步驟(1)～(4)，直至行走T步，回溯記錄的局部最優路徑以獲取最大可能隱藏狀態序列的跡，由此得出當前服務請求對應的最大可能路徑。

依據上述主要步驟，對基于OQRW-HMM的QBD算法流程進行描述，如算法1所示。

算法1基于OQRW-HMM的QBD算法。

① for eachr(E，F，D，Td)∈Rdo

② for each stepi= 1：Tdo

③ ifIsResAva(k，i，R，P) then

④ 利用式(10) 計算觀測狀態空間K?T

⑦ 更新剩余資源 ResAva(k，i，R，P)

⑧ end if

⑨ 將交換算子I?I?S作用于H?HC?K?T

⑩ if IsResAva(i，j，R，P) then

在服務請求路徑選擇過程中，假設底層網絡節點數為n，到達的服務功能鏈長度為m，通過T步量子行走回溯解碼最大跡，得到近似最優路徑，則所提算法的時間復雜度為O(Tm)，在算法效率和運行時間方面明顯優于一般啟發式算法。

4 仿真結果與分析

由于量子計算機和量子算法的研究和發展仍處于初級階段，使得QML等量子算法的具體實現和驗證面臨缺少通用量子計算平臺的困難，目前絕大多數QML算法選擇通過理論證明和仿真實驗驗證的方式檢驗其有效性，能夠在一定程度上說明量子算法的計算優越性[17]。

由此，為檢驗所提算法的有效性和效率，選擇采用Matlab仿真環境進行對比實驗。物理網絡設置為：包含1個核心云節點，1個低軌道衛星邊緣云節點，15個邊緣云節點的網絡，其中地面和衛星邊緣云節點都可以連接到核心云節點，運行SFC編排算法的控制器部署在SAT-MEC網絡的核心云節點，假設低軌道衛星節點可完全覆蓋地面邊緣云網絡范圍。各節點和鏈路資源服從均勻分布，衛星節點設置參照文獻[4，20]，詳細仿真參數如表2所示。由于衛星節點的移動性，設低軌道節點的鏈路可持續時間服從[0，500]的均勻分布。假設一定時間內，到達的用戶SFC請求服從泊松分布，生存時間Td服從均值為100的指數分布，每個服務功能鏈中包含[1，4]個有序VNFs，IT資源和帶寬資源需求分別服從[1，5]范圍內的均勻分布。仿真實驗時間設置為1 000個時間單位，為避免隨機因素影響，取10次平均值。

表2 仿真參數設置

首先，將具備衛星邊緣云(LEO-MEC)節點輔助的SAT-MEC網絡與一般地面邊緣云(MEC)網絡進行對比。圖3為SAT-MEC和MEC的服務請求成功率隨用戶數量變化情況。為保證公平性，地面MEC節點資源量保持一致，LEO-MEC節點設置見表2。可以看出，SAT-MEC網絡的請求成功率要明顯高于MEC網絡，SAT-MEC網絡在用戶數量達到125時開始下降，MEC在用戶數量達到95時開始下降，提升了約31.6%。分析其主要原因，衛星節點能夠負擔部分地面流量，在一定程度上改善了擁塞現象，使得服務請求成功率上升。圖4為平均時延隨用戶數量變化情況。

從圖4可以看出，SAT-MEC的平均時延比MEC約低9.01%。分析其原因，雖然LEO-MEC節點的計算能力相對于地面MEC節點較弱，但前者更廣的覆蓋范圍使得端到端傳輸過程中經過的跳數更少，使得平均時延更低。

其次，將提出的OQRW-HMM算法與精確求解的MA-JSPR[14]算法、啟發式的SAGIN-Greedy[15]算法和Greedy-Ksp[16]算法進行分析比較。圖5為請求成功率隨流量負載變化情況，隨著流量負載增大，各算法的請求成功率逐漸下降，MA-JSPR和OQRW-HMM算法表現優于SAGIN-Greedy和Greedy-Ksp算法。分析其原因，SAGIN-Greedy和Greedy-Ksp算法在求解SFC路徑時得出的解為近似最優解，會導致獲取到的近似最優解使得系統整體資源利用率較低，在流量負載較大的情況下，請求成功率下降速度較快。圖6為平均時延隨流量負載變化情況，隨著流量負載增加，MA-JSPR算法求解的復雜度較高，使得時延迅速增加。OQRW-HMM算法平均時延比MA-JSPR、SAGIN-Greedy和Greedy-Ksp算法分別降低了約21.92%、29.57%和17.67%，整體表現較好。分析其原因，OQRW-HMM算法高并行計算的特性大大提升了部署效率，縮短了部署所需時間，使得網絡能夠在高流量負載的情況下保持較低的時延水平和較高的請求成功率。

圖3 用戶數量-請求成功率

圖5 流量負載-請求成功率

5 結束語

為了有效地提升空天地網絡的服務資源管理和優化效率，筆者研究了空天地協同的邊緣云網絡場景下服務功能鏈的動態編排問題，設計了SAT-MEC網絡的服務功能鏈編排架構和系統模型；在此架構下，以資源和服務請求為約束，最小化端到端時延為優化目標，將問題建模為一般整數線性規劃模型；利用量子機器學習并行計算的優勢，將服務功能鏈路徑選擇過程轉化為基于開放量子行走算法的隱馬爾可夫模型，并利用量子回溯解碼方法對模型進行求解；與傳統方法相比，筆者提出的動態編排方法能夠在滿足資源和服務請求約束的情況下，有效降低端到端平均時延，并保持較好的服務請求成功率，實現了SAT-MEC網絡服務功能鏈部署效率的提升。

在實際應用方面，由于量子計算領域仍屬于新興發展階段，量子機器學習等量子算法的實現還面臨許多現實問題和挑戰，如缺少完備的量子計算理論框架與通用量子計算機設備等。但可以預見，隨著量子計算機研制和量子態制備技術等領域的不斷突破，未來量子算法的實驗驗證和實際運用也會得到進一步發展。