一种星地融合网络动态服务迁移重构方法
2022-05-10乔文欣李雄伟倪祥龙陈立伟
乔文欣，卢 皓，李雄伟，倪祥龙，陈立伟
(1.陆军工程大学 石家庄校区，河北 石家庄 050003；2.北京航天飞行控制中心，北京 100094；3.北京空间信息中继传输技术研究中心，北京 100094；4.电子信息系统复杂电磁环境效应国家重点实验室，河南 洛阳 471003)
0 引言
随着微小卫星系统与互联网技术的飞速发展，融合地面网络和卫星网络覆盖空、天、地、海和深空等自然环境，能够提供全天候无缝高速网络接入的星地融合网络逐渐成为当前产业界和学术界研究的重要领域之一[1]。通过与SDN/NFV[2](Software Defined Networking/Network Function Virtualization)、5G[3]、边缘计算[4]和物联网[5]等新型网络技术的结合，更赋予了星地融合网络高效便捷的管理控制能力和灵活可拓展的网络服务支持[6]。在星地融合网络架构下，按照实际用户业务需要和服务需求提供差异化的独立网络切片，或部署相应的虚拟网络功能(Virtual Network Function,VNF)，其目的都是利用有限的网络资源或服务资源来满足多样化的用户业务需求和服务需求，以获取更佳的网络资源配置与服务体验。然而，星地融合网络自身所具备的网络拓扑动态性，以及用户业务请求和任务需求随态势实时变化的特点，都使得一次性的资源部署及优化策略与动态变化的网络状态不再适配，从而导致网络性能恶化、用户服务质量体验下降和网络运维成本增加等情况发生。例如，卫星节点或用户节点移动可能导致传输链路质量下降或连接中断，使得原有端到端传输路径不能正常工作。所以，当星地融合网络的网络状态和用户需求的动态性严重影响到业务流量传输或服务部署质量时，需要寻找新的调整方法来保持流量传输和服务质量。
针对上述问题，将原有服务节点上部署的虚拟网络功能通过在线迁移或重新实例化的方式，迁移到资源更充足或路径更合理的新服务节点所在位置，然后按照新位置引导业务流量按照新的服务路径传输，能够在一定程度上缓解负载不均衡和服务质量下降等问题[7-8]。这种调整方式被称为服务迁移与重构，目前在移动边缘网络[9-11]、物联网[12]和雾计算[13]等领域有着许多相关研究，但在多源异构且动态性强的星地融合网络中，其研究还处于起步阶段。不同于一般网络框架，星地融合网络的动态性主要源于内部网络结构变化和外部用户需求变化两方面因素。内部网络结构变化包括卫星节点和地面MEC节点的移动性、节点和链路的新增或失效等因素；外部用户需求变化包括用户节点移动导致业务和服务请求接入位置移动，业务和服务的请求类型和质量要求发生变化等因素。因此，如何在保证网络服务质量的同时，为星地网络用户提供连续且可靠的高质量网络服务和业务支持，是当前星地融合网络研究的关键挑战之一。
目前，国内外学者对星地融合网络服务迁移重构相关问题的研究已取得了一定的成果。文献[12]建立了卫星智能城市车辆联网场景下的计算资源地理迁移模型，通过雾节点感知道路状态和车辆情况，并提出了一种基于资源定价的车辆路径选择方案，其主要创新在于不同需求情况下的定价策略算法，但在迁移策略计算效率方面略显不足。文献[14]提出了一种基于天基的在轨服务体系架构，能够根据实时上下行流量变化进行动态业务迁移，以优化迁移节点时延和能量消耗为目标，建立了天基边缘云服务迁移模型并进行仿真验证，但服务迁移对象和范围仅针对卫星节点及其上的在轨服务，未考虑星地节点之间的迁移问题。文献[15]研究了空天网络场景下的通信服务动态资源分配和重配置问题，将机上用户资源分配问题建模为多周期广义分配问题，并提出了一种深度Q学习控制框架优化资源分配和重配置方法。文献[16-17]考虑车辆联网场景的动态性，研究了空天地协同的车辆联网场景下的在线动态VNF映射和调度问题，提出了2种基于禁忌搜索算法的VNF映射和重调度算法，能够有效获得近似最优VNF迁移方案。综上，虽然当前已有一些学者从不同的角度对星地融合网络及相似网络架构的迁移重构问题进行了研究，但其针对性和优化效果略显不足，需要进一步深入探讨。
为此，本文重点研究了星地融合网络架构下内外部网络环境动态性导致的服务迁移重构问题。首先，给出以节点移动性和用户需求变化为主要触发因素的服务迁移重构基本步骤，并将其中的迁移位置和路径选择问题建模为一个经典整数线性规划问题；然后，提出了一种基于模糊量子遗传算法的动态服务迁移重构(Fuzzy Logic Quantum Genetic Algorithm Based Dynamic Service Migration and Reconfiguration,FQGA-SR)方法，利用其量子编码和并行计算的优势进行优化决策求解；最后，对所提算法的有效性和效率进行了仿真实验验证。
1 问题描述
星地融合网络服务迁移重构过程如图1所示。星地融合网络的基本结构包含由卫星网络、无人平台和地面网络组成的3层平面网络结构，以及地面管理控制中心和GEO卫星控制器组成的2层控制结构。假设LEO卫星边缘节点和地面边缘节点都具备一定算力和存储资源，可以根据部署策略承载多种VNFs，能够为用户提供高速网络接入、边缘侧服务支持、数据中继和链路回程。同时，无人机节点和卫星节点都拥有通信中继和链路回程能力，由于无人机受能源和荷载限制，暂不考虑将无人机节点作为承载VNF的边缘节点，仅承担中继转发功能。卫星网络平面中的卫星节点通过定向无线通信链路互相连接，包括微波、激光、6G通信中的毫米波和自由空间光学链路等，因而支持高速数据传输。
图1上方为星地融合网络用户提出服务请求的基本过程，当前服务提供的对象为可移动车辆终端用户，车载终端用户从人口密集型核心城区由西向东驶向偏远地区，该车辆用户执行任务所需求的服务功能链为有顺序的网络功能VNF-1，VNF-2和VNF-3。
图1 星地融合网络服务迁移重构过程Fig.1 Service migration and reconfiguration process of satellite-terrestrial integrated network
车辆用户移动前，由于周围具备临近地面边缘接入点，能够提供充足的边缘算力与服务支撑，从而通过网络功能路径(Service Function Path,SFP)SFP1(N3-N1-N2)到达目的节点N4，并分别由地面边缘节点N3，N1和N2承载服务功能VNF-1，VNF-2和VNF-3。
车辆用户移动至偏远地区后，此时失去地面边缘节点的接入支持和服务支持，管理控制平面根据实时网络状态信息和车辆用户服务请求，运行服务迁移和重构算法得出最优迁移位置和迁移路径。例如，将地面边缘节点N3上的VNF-1迁移至卫星边缘节点N9上，将N1上的VNF-2迁移至卫星边缘节点N7上，迁移路径按照最短路径进行。迁移后用户车辆的数据流量按照SFP2(N9-N7-N2)到达目的节点N4，以满足车辆用户的通信需求和服务需求，并保持通信和服务的连续性及可靠性。
本文研究的重点是通过服务迁移和重构算法为VNF迁移找到合适的迁入位置，以及在满足约束限制的情况下，最小化迁移成本，优化服务迁移路径。
2 服务迁移重构模型构建
2.1 系统模型
假设当前星地融合网络中地面边缘节点和卫星边缘节点的数量已知且固定，网络用户和卫星节点可随时间变化而移动，各个节点和链路之间的连接状态和资源状态可通过SDN/NFV全局状态感知能力获取，即网络拓扑状态和网络资源状态可知。不同用户对网络服务请求的服务需求和资源需求到达呈一定规律。
① 底层物理网络模型
② 服务请求
表1 主要符号及定义Tab.1 Main notations and definitions
服务请求部署状态和物理网络资源使用情况随时间变化而变化，利用SDN/NFV集中控制功能可以获取当前时刻的网络状态，每个边缘节点所能承载的用户服务请求数与当前剩余资源和用户请求数有关。
2.2 优化目标
考虑到用户端到端时延是影响服务体验最重要的性能指标之一，可将时延作为服务迁移问题的优化目标。除了数据传输过程产生的端到端时延，服务迁移过程会在原有时延的基础上产生额外时延，因此需要作为迁移成本另外考虑。
因此，星地融合网络中的服务迁移和重构问题的优化目标可以定义为：在保证服务连续性的同时，最小化端到端时延和迁移成本。下面给出端到端时延和迁移成本的公式化描述，以及服务迁移和重构问题的优化目标及约束条件。
① 端到端时延
端到端时延的计算为用户服务请求到达边缘接入点，用户数据通过网络传输并依次通过服务路径中的服务功能所在节点，完成所有服务功能所产生的时延，主要包括传播时延Dp、传输时延Dtr和处理时延Dpr三部分，可表示为：
D(t)=Dp(t)+Dtr(t)+Dpr(t)，
(1)
式中，传播时延主要与星地、星间链路的物理长度Dis(fk,fv)有关，计算公式如下：
(2)
(3)
(4)
② 迁移成本
迁移成本指的是星地融合网络的服务迁移过程中，因执行迁移动作所产生的额外运营成本和开销。由于本文所关注的重点在于用户和卫星节点移动性所引发的服务迁移，在此仅考虑单个VNF进行迁移和重构的情况。每进行一次服务迁移，所产生的迁移成本主要包括在迁入节点位置实例化新VNF所花费的成本，以及迁移路径选择所产生的额外时延。当服务迁移动作所经过的路由节点越多、路径可用带宽越小，则所产生的迁移成本越高、业务因迁移导致的中断时间越长，不利于用户服务体验。与此同时，迁移路径所经过的节点可用路由跳数替代，迁移成本的计算可以用迁移路径跳数导致的额外传播时延和迁移路径带宽相关的额外传输时延衡量。由于实例化新VNF所花费成本与迁移位置无关，因此仅考虑额外时延，则迁移成本Mc可表示为：
(5)
2.3 问题建模
当星地融合网络中内外部环境变化触发服务迁移条件时，采用服务迁移和重构优化模型求解最优服务迁移策略，主要为迁入节点和迁移路径的选择问题。考虑网络用户的服务体验及运营成本，将最小化端到端时延和迁移成本作为优化目标，可表示为：
minCm(t)=min[w1D(t)+w2Mc(t)]，
(6)
s.t.∑Msu(ni,fk)≤1 , ∀ni∈Nsn,fk∈Fs，
(7)
(8)
(9)
(10)
Msu(ni,fk)={0,1}，∀ni∈Nsn,fk∈Fs，
(11)
(12)
式(6)为优化问题的目标函数，其目的是获得端到端时延和迁移成本最小的最优迁移位置和迁移路径，其中w1和w2分别为端到端时延D(t)和迁移成本Mc(t)的修正系数，用于动态调整不同服务对时延和迁移成本的不同需求。式(7)～式(12)为约束条件，主要考虑底层物理网络资源限制与服务迁移需求之间的均衡。其中，式(7)和式(8)保证一个服务迁入节点和链路最多只能映射到一个底层物理节点和链路上；式(9)保证服务迁入节点的计算资源需求不超过所映射到的底层节点计算资源容量；式(10)保证服务迁移链路的带宽资源需求不超过所映射到的底层链路带宽资源容量；式(11)利用布尔变量表示该底层节点是否被选为当前服务部署节点，1为部署，0为否；式(12)同上，代表该底层链路是否被选为服务请求虚拟链路，1为映射，0为否。
3 算法设计及描述
由模型可知，服务迁移重构优化问题是一个整数线性规划(Integrated Linear Programming，ILP)问题，即最优迁入节点决策和迁移路径选择问题。考虑到卫星节点和用户的动态性及移动性，该问题的求解空间较为庞大。经典的精确求解、启发式求解和元启发式求解算法在一定程度上都具有局限性，不适用于大规模离散状态空间问题[18]。经典遗传算法是一种随机启发式搜索算法，与精确求解算法相比，该算法效率较高，且其中交叉和变异步骤具有随机性，在一定程度上能够避免算法陷入局部最优，但过大的随机性设置会使求解空间变大、求解效率降低。量子遗传算法是在经典遗传算法的基础上，将量子算法中量子叠加态能够并行计算以加速求解过程的优势，作用于种群编码方式和进化策略，进一步提升遗传算法原有的求解效率和全局寻优能力。而且，该算法能够弥补染色体组合交叉和变异随机性带来的求解空间过大、求解困难的缺陷，在文献中已展示出良好的性能表现，能够在较小种群规模下，快速收敛到全局最优解。
因此，选择采用量子机器学习与传统算法结合的模式，提出了一种基于模糊逻辑(Fuzzy Logic，FL)和量子遗传算法(Quantum Genetic Algorithm,QGA)的服务迁移优化算法。将对所提算法的基本步骤进行详细阐述，并给出算法的伪码，为算法的仿真实验验证给出铺垫。
3.1 基本步骤
基于模糊量子遗传算法的服务迁移重构(FQGA-SR)算法的基本步骤如下。
3.1.1 建立最短路径矩阵S
首先，建立FQGA-SR算法的输入矩阵S，用于表示底层网络Gsn内任意两底层节点间的关联关系，矩阵S的第i行和第j列代表节点ni和节点nj之间所部署SFC的最小时延。利用k-Dijkstra算法计算两节点间的最短路径，得到矩阵S。
3.1.2 FQGA-SR算法初始化
初始化种群及个体，设观测序列个数为Xc，量子比特概率空间为Niche，染色体量子比特编码长度为K和种群规模为M。利用量子比特编码的方式构造初始种群及个体，采用量子叠加态形式表达染色体，能够在保持种群规模的前提下，大幅提升种群基因型的多样性。
(13)
3.1.3 子种群进化
模糊逻辑算法以隶属度的形式将离散数据模糊化，能够用单一模糊集合定义离散概率函数，以便高效获取较为准确的输出结果。因此，利用模糊逻辑算法来描述包含概率幅的量子比特编码的种群和个体，有助于获取子种群的进化。令H1表示子种群中|1〉与量子比特编码数目K之间的比值，可表示为：
(14)
可将适应度函数Fit(Xc)表示为Fit(Xc)=[Obj]-1，Obj为当前优化目标，即最小化端到端时延和迁移成本。根据适应度函数定义H2，用于衡量当前与适应度密切相关的程度，则H2可表示为：
(15)
式中，Fit*(Xb)为当前适应度最高的值。
将H1和H2分别量化为c1级和c2级，其基本取值范围为[0,1]。通过输入H1和H2得到量子旋转门相位Δθ和变异概率Pm。
3.1.4 量子旋转门和变异的自适应调整策略
利用量子旋转门相位变换和变异操作实现染色体更新，令算法具备扩展能力和探索能力，从而保证算法能够快速收敛。通过调整量子旋转门相位Δθ和变异概率Pm来调节H1和H2，实现。假设R为一个正实数，若H1 3.1.5 量子变异操作 按照FQGA-SR算法的基本步骤，将底层网络Gsn、迁移需求R和染色体量子比特编码长度K，以及种群规模M作为输出，可利用FQGA算法得到最优迁移策略Xb，则Xb={x1,x2,…,xi,…,xK}代表服务迁移后的节点承载VNF状态，其中xi代表VNFf∈F部署在底层节点ni∈Nsn上。 为方便理解，FQGA-SR算法主要步骤伪代码如下。算法将服务迁移问题分为2个部分：迁入节点选择阶段和最短迁移路径选择阶段。其中，第3行用于获取最短路径矩阵S，第4行用于初始化FQGA的模型参数，第5～9行是种群进化过程，第10～13行是FQGA的变异过程。 FQGA-SR算法输入 底层物理网络Gsn,服务请求Gs,种群规模M,染色体长度K,进化迭代次数T输出 最优迁移策略Xb1 foreach服务请求s∈Gsdo2 ifIsRequestSatisfied(Gsn,Gs) then3 利用k-Dijkstra算法计算最短路径,并获取最短路径矩阵S4 根据式(13)初始化量子基因种群,获取N(0)5 while(t 另外，基于FQGA的迁移策略优化算法运行在星地融合网络的控制平面上，通过GEO卫星控制器实时收集全网状态信息，并结合地面管理控制中心的云计算中心及边缘节点算力，能够快速有效地得到最优迁移决策，实现VNF迁移并为迁入节点和相关链路重新分配网络资源，以完成服务迁移重构步骤。 为评估所提算法在星地融合网络服务迁移优化问题中的有效性和性能表现，本文建立了仿真实验平台进行验证。仿真实验在Intel Core i7-10710U CPU @3.3 GHz、16 GB RAM的主机上运行，采用Matlab 2018b与STK 11联合仿真实验，用于模拟卫星星座组网和地面网络连接状态信息。 通过STK和Matlab联合仿真模拟星地融合网络中卫星网络运行情况，获取卫星节点各个时刻的可见性，星地、星间链路的可持续时间，以及地面节点卫星过顶情况等。设置星地融合网络架构下的服务功能链重构场景，服务迁移仿真参数设置如表2所示，地面设置1个核心云节点、15个地面边缘节点(MEC节点)、3个LEO卫星边缘节点(LEO节点)，星地、星间及地面链路连接情况随LEO卫星节点运行变化而变化。 表2 仿真参数设置Tab.2 Simulation parameters setting 在上述网络拓扑下，单位时间内到达的SFC请求服从泊松分布，服务请求到达率λ为[0.05,0.2]，每个SFC包含[2,6]个VNFs，生存时间为[30,80]ms，每个VNFs所产生的处理时延为[120,200]ns。上述仿真参数服从各自取值范围的随机分布，实验结果以10次重复实验取平均值。 综合考虑算法收敛性、端到端时延、服务重构成功率和算法运行时间4个性能指标，本文将所提基于模糊量子遗传算法的服务迁移重构方法(FQGA-SR)与SEC-SM算法[14]、TS-MAPSCH算法[16]和MGA算法[13]进行比较，以证明所提算法的有效性及性能表现。 算法收敛性比较如图2所示。可以看出，所提出的FQGA-SR算法以最快的速度收敛到稳定状态，大约在迭代次数达到58左右趋于稳定；TS-MAPSCH和SEC-SM算法速度其次，都在迭代次数200左右趋于稳定；MGA算法收敛速度较慢，在280次左右。同时，所提FQGA-SR算法和TS-MAPSCH算法在端到端总时延的优化结果方面表现较好。分析其原因，FQGA-SR算法引入了量子染色体编码和量子交叉过程，大大地提升了计算效率，因而求解效果最好。而MGA算法采用传统染色体编码方式，在动态网络需求和大规模问题空间下求解较为困难，并且为了避免收敛到局部最优，需要牺牲求解速度来提高求解精度，所以收敛速度较慢。 图2 算法收敛性比较Fig.2 Comparison of algorithm convergence 图3为不同流量负载状态下，端到端时延随服务请求数量变化的示意图，其中图3(a)和图3(b)分别为流量负载60%和90%的状态。 (a) 流量负载60% (b) 流量负载90%图3 端到端时延比较Fig.3 Comparison of end-to-end delay 可以看出，所提FQGA-SR算法求得的优化结果较MAG算法、TS-MAPSCH算法和SEC-SM算法表现更好。其中，基于遗传算法的MGA算法收敛速度稍慢，因此波动幅度比其余算法稍大；SEC-SM算法的节点选择主要依赖于最短路径算法，未充分考虑资源状态，所以部署结果端到端时延表现稍差。整体来看，随着服务请求数量的增加，网络中的剩余资源不断减少，后续到达的服务请求部署和迁移受一定影响，端到端时延的数值稍显增加。对比图3(a)和图3(b)，在流量负载达到90%时，网络中剩余可用资源较少，可迁移和部署的节点及链路选择余地较小，因而端到端时延整体相对增加。 图4(a)和图4(b)分别为服务重构请求到达率λ=0.05和λ=0.2时，服务重构成功率随重构请求数量变化的情况。 由图4(a)可以看出，请求成功率FQGA-SR算法整体表现最优，在重构请求达到250时，仍能保持0.847的服务重构成功率；其次为MGA算法和TS-MAPSCH算法，最后为SEC-SM算法，其成功率仅为0.765。分析其原因，所提FQGA-SR算法充分考虑了节点移动性和当前网络拓扑状态，因而能够更好地做出迁移重构决策，MGA算法和TS-MAPSCH算法同属于启发式算法，而SEC-SM算法考虑的触发因素主要为流量变化情况，对网络拓扑状态变化感知不明显，所以效果较差。对比图4(a)和图4(b)可知，随着服务重构请求到达率提升至λ=0.2，4种算法的服务重构成功率都随之下降，且MGA算法表现略优于TS-MAPSCH算法。分析其原因，重构成功率下降是由于迁移重构算法在应对到达密度较高的服务请求时，可能面临节点和链路被占用，计算和带宽资源还未释放的情况，所以其重构成功率较低；而MGA算法表现略优，是由于基于遗传算法的MGA算法在应对较大求解空间规模时，其全局求解能力和求解效率略优于基于禁忌算法的TS-MAPSCH算法。 图5显示了不同流量负载下的算法运行时间，随着流量负载逐渐增加，各算法运行时间也随之增加。仿真设置在流量负载40%～90%。显然，所提FQGA-SR算法平均运行时间远低于MGA算法、TS-MAPSCH算法和SEC-SM算法。以90%负载为例，FQGA-SR算法的平均运行时间为2.27 s，MGA算法、TS-MAPSCH算法、SEC-SM算法分别为4.38,5.15和6.89 s，前者相比于后3种算法的运行时间分别提升了48%,55%和67%。分析其原因，FQGA-SR算法利用量子叠加原理加速计算，能够快速决策出迁移重构方案，计算效率远高于其余3种算法；MGA算法在求解空间较大的情况下计算效率相对高于其余2种算法，但此时得到的解可能不是全局最优解。 图5 算法运行时间比较Fig.5 Comparison of algorithm running time 针对星地融合网络服务迁移重构优化决策问题，在考虑用户需求动态性和网络拓扑结构移动性的基础上，设计了一种端到端时延及迁移成本最小化的联合优化模型，并结合模糊逻辑和量子遗传算法对模型进行了求解。实验结果表明，本文提出的FQGA-SR算法在收敛性、有效性和网络性能方面具有良好的表现，能够有效地提升迁移重构优化部署效率。
3.2 算法描述
4 仿真实验及分析
4.1 参数设置
4.2 结果分析
5 结束语
