空天地协同的边缘云服务功能链动态编排方法

乔文欣，卢 昱，刘益岑，李志伟，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网络服务功能链部署效率的提升。

在实际应用方面，由于量子计算领域仍属于新兴发展阶段，量子机器学习等量子算法的实现还面临许多现实问题和挑战，如缺少完备的量子计算理论框架与通用量子计算机设备等。但可以预见，随着量子计算机研制和量子态制备技术等领域的不断突破，未来量子算法的实验验证和实际运用也会得到进一步发展。