移动边缘计算网络中联合无线多播的服务功能链部署算法

王侃，赵楠，李军怀，王怀军

（1.西安理工大学计算机科学与工程学院，陕西 西安 710048；2.大连理工大学信息与通信工程学院，辽宁 大连 116024）

1 引言

5G 移动通信系统以其灵活性和高效性为用户提供了超高吞吐量和超低时延的服务体验[1]。作为5G 的关键技术，网络功能虚拟化（NFV,network function virtualization）和移动边缘计算（MEC,mobile edge computing）已得到学术界和工业界的广泛关注[2-3]。不同于传统网络通过部署专门硬件来实现网络功能，NFV 将软硬件解耦，通过在商用服务器上部署虚拟网络功能，构造面向各类业务需求的、将虚拟网络功能有序排列的服务功能链（SFC,service function chain），为用户提供差异化和定制化的服务[2]。MEC 将部分或全部网络功能卸载到靠近用户的边缘网络，将显著提升服务的时延和吞吐量性能，有效降低核心网的业务拥塞[3]。

NFV 和MEC 相互补充，通过在边缘网络的基站中部署虚拟网络功能，可使用户就近接受网络服务，从而增强了网络管理的灵活性和可伸缩性[4]。然而，与云接入网（C-RAN,cloud radio access network）等集中式网络架构相比，边缘网络中SFC部署问题将面临如下特有挑战。

1) 与集中式网络架构中的云计算服务器不同，MEC 服务器的计算容量和存储容量通常受限[5-7]；单个MEC 服务器只能部署SFC 中的部分网络功能。如何协同利用受限的MEC 服务器资源，进行虚拟网络功能的有序部署，对SFC 部署算法带来设计上的挑战。

2) 与核心网中SFC 部署不同，边缘网络中SFC的部署不仅涉及数据流在基站与基站之间基于有线链路的服务路径选择，而且需考虑执行完最后一项网络功能后，数据流经基站到用户的无线链路传输。

因此，基于上述挑战，边缘网络SFC 部署问题面临的关键技术包括服务路径选择技术和无线链路干扰消除技术。首先，针对实时服务请求，服务路径选择表示引导数据流依次通过能够支持SFC中网络功能的服务基站。其次，由于无线链路的广播特性，在执行完SFC 的最后一项网络功能后，数据流经基站到用户的无线链路存在相互干扰；利用正交频谱资源分配或波束成形技术以消除用户间干扰，是边缘网络SFC 部署问题的另一项关键技术。如何针对差异化的用户需求和有限的网络资源，设计低开销的、基于干扰消除的边缘网络SFC部署算法，已成为学术界和工业界的研究热点。

已有研究工作通常关注端到端的、面向用户的SFC 部署方案[8-11]，在网络资源受限的约束下，实现虚拟网络功能到MEC 服务器的有效映射，优化用户的服务体验。文献[8]研究了边缘网络中SFC的服务迁移问题，基于用户随机游走模型，考虑了迁移代价和时延约束，提出了一种在线服务迁移算法，以最小化用户的服务中断概率。同样基于用户运动模型，文献[9]研究了面向内容缓存服务的最短路由路径的SFC 部署问题，将最短路径问题建模为一个整数线性规划（ILP,integer linear programming）问题，提出了一种低复杂度的启发式算法。基于软件定义的边缘网络，文献[10]同时考虑了用户的业务体验和服务的可靠性需求，研究了端到端时延约束下系统的吞吐量优化问题，利用多路径路由策略保障服务的可靠性，并利用主对偶方法找到每条可行路径的分配带宽。基于单路径路由策略，文献[11]同时考虑了节点处理容量和链路带宽约束，研究了最小化数据流开销的SFC 映射问题。综上所述，已有的SFC 部署方案通常是面向用户的，为每个用户部署一条专用的、定制化的SFC。然而，随着内容提供业务（例如，视频、音乐和文件）的持续增长，边缘网络中的流行内容会被多个用户重复下载[12-13]，此时，若对具有相同内容请求的多个用户均部署定制化的SFC，不仅会增大边缘网络中数据流的开销，造成业务拥塞，而且会导致额外的MEC 服务器功耗开销。因此，研究基于内容分组的SFC 部署算法具有重要理论意义和现实价值。

将请求同一内容的用户划分到一组，设计面向内容的SFC 部署算法，使该组所有用户共享一条SFC，可有效降低系统数据流开销和功耗开销。然而，与核心网不同，边缘网络无线信道的广播特性使同一内容到多个用户的多播传输存在相互干扰。基于正交频谱资源分配，文献[14]提出了一种两阶段协作多播机制，以降低系统传输功耗，并增强系统覆盖率。首先，利用随机几何理论，采用基于平均接收信号强度的选择合并技术，分析了基站传输功耗和系统传输功耗的相互关系；其次，提出了一种基于扇形环结构的移动中继部署方案，进而推导了基于期望覆盖率的最优基站传输功耗的表达式。基于波束成形技术，文献[15]将请求同一内容的用户进行组划分，形成多播组，对组内所有用户发送相同的数据符号，从而有效节省了无线频谱资源，并降低了数据流开销。文献[16]研究了C-RAN 中运营商的收益优化问题，同时考虑了高带宽和低时延2 种典型5G 业务，针对高带宽的内容提供业务，利用波束成形技术实现组内用户干扰抑制；针对低时延业务，利用正交频谱资源消除用户间干扰。同样基于C-RAN，文献[17]研究了基于混合时间尺度的内容缓存服务，利用协作多播技术以抑制组内用户干扰，综合考虑系统功耗和用户吞吐量需求等约束，以最大化系统的长期收益。综上所述，针对面向内容的无线多播技术的研究通常只考虑内容从接入基站到用户的无线传输这一环节。然而，与云计算服务器相比，MEC 服务器的存储和计算资源通常受限，单个接入基站只能部署SFC 中的部分功能。因此，基于内容分组，引导数据流依序通过多个服务基站，服务路径规划需联合考虑基站之间的有线链路和接入基站到用户的无线链路，构造“第一个服务基站→第二个服务基站→…→最后一个服务基站（接入基站）→用户”的端到端服务路径。

本文主要的研究工作如下。

1) 面向内容提供服务，建立边缘网络中联合无线多播的SFC 部署模型。最大化系统中数据流开销和功耗开销，并满足链路带宽约束、处理容量约束、吞吐量需求约束、SFC 部署序列约束、波束向量与信号处理功能的耦合约束，以及最大发射功率约束。综合考虑数据流、服务器功能维护功耗、服务器功能服务功耗和无线传输功耗这4 种系统开销，建立波束成形设计和SFC 部署的联合优化问题。该问题是一个NP（non-deterministic polynomial）难问题，很难找到多项式时间求解算法。

2) 利用拉格朗日对偶分解技术，将原优化问题转化为2 个独立子问题。利用基于Lp范数惩罚项的连续凸近似算法，将ILP 项式的SFC 部署问题松弛为一个线性规划（LP,linear programming）问题，并给出了原问题和松弛问题的最优解等价性证明；利用路径跟随技术，将非凸波束向量优化问题转化为一系列凸子问题，并给出了算法的单调性分析。

3) 仿真结果表明，本文算法具有良好收敛性能。将本文算法与最优单播SFC 部署算法和随机多播SFC 部署算法进行对比，验证了本文算法的有效性。

2 系统模型

在边缘网络中，通过在基站的MEC 服务器中部署NFV 技术，基站不仅能提供基带处理单元（BBU,base-band unit）功能，而且可支持缓存、计算、防火墙和网络地址转换等多种虚拟网络功能。考虑一个多基站部署的边缘网络，基站集合表示为N={1,2,…,N}，如图1 所示。基站之间通过X2+链路实现互联，同时每个基站配置I根天线和一个商用服务器。边缘网络中分布K个用户，用集合K={1,2,…,K}表示。假设所有用户均请求内容提供服务，并将请求同一内容的用户分配到同一多播组。多播组用集合M={1,2,…,M}表示，而多播组m的所属用户集合用 G(m)表示。

图1 多基站部署的边缘网络

2.1 SFC 模型和容量约束

在基于NFV 技术的边缘网络中，每项内容提供服务可映射为一条端到端的SFC 部署，即“第一个服务基站→第二个服务基站→…→最后一个服务基站（接入基站）→用户”的端到端服务路径。在多播组m中，任一数据流在被基站天线发送到用户之前，需遍历SFC 的每一项网络功能。分别用和表示该条SFC 中第一和最后一项功能，则可用来描述该条SFC。多播组m的任一数据流需起源于（例如，图1 中的内容1 和内容2 的MEC 服务器)，依序遍历 F(m)中其他功能，最终以（例如，图1 中部署BBU1和BBU2的MEC 服务器）终止服务。如图1 所示，边缘网络中部署了2 条基于内容提供服务的SFC，每个数据流需依次遍历缓存功能、计算功能和信号处理功能，最终由基站无线传输到终端用户。

2.2 多播模型

与协同多点传输（CoMP,coordinated multiple-point transmission）[15-20]技术不同，本文假设每个基站在自己的天线组内独立进行多播波束成形，对每个基站分配正交的频谱资源，从而有效消除了小区间干扰。基于单天线CoMP 技术，文献[18-19]提出了宏分集协同多点传输（MD-CoMP,macro diversity coordinated multi-point transmission）概念，将小区频率复用因子设为1，通过对同小区用户分配正交频谱资源，以消除小区内干扰。因此，用户所受干扰为来自其他基站簇的小区间干扰。本文没有考虑基站之间的CoMP，这是因为，若考虑CoMP，则每个用户将选择多个接入基站，本文考虑的单服务路径规划问题将成为一个多服务路径规划问题，进一步增大优化问题的求解难度。定义每个基站的无线频谱带宽为B，则用户k从基站n处得到的接收信号信干噪比（SINR,signal to interference plus noise ratio）Γk,n为

2.3 问题描述

一方面，为最小化SFC 路径中的数据流开销，每条SFC 的功能应集中部署在尽可能少的MEC 服务器中，然而受限于MEC 服务器的处理容量，同一SFC 的不同功能往往部署到不同的基站，这将不可避免地增大数据流开销。另一方面，不仅基站的发送天线带来无线传输功耗开销，MEC 服务器的功能维护和功能服务也将导致服务器功耗开销。系统开销应综合考虑数据流开销和功耗开销。因此，可将系统总开销C定义为

其中，η为平衡数据流开销和功耗开销的折中系数，Pf,n为基站n维护功能f的功耗，为基站为多播组m提供功能的服务功耗。式(10)中，系统开销分别为数据流开销、服务器功能维护功耗开销、服务器功能服务功耗开销和无线传输功耗开销。首先，相邻2 个网络功能之间的数据传输将导致数据流开销；为实现SFC 的有序部署，每个基站需为多播组的服务请求提供网络功能，将导致功能维护开销和功能服务开销。上述3 种功耗发生在边缘网络的MEC服务器中或基站之间的有线链路中。其次，为实现端到端（从边缘网络基站到多播用户）的数据传输，多播组的任一数据流需遍历SFC 中的每一项网络功能，最终到达用户的所属服务基站，使用波束成形等信号处理，通过无线多播的方式到达用户。因此，无线传输功耗发生在无线多播环境中服务基站到多播用户的最后一跳中。4 种系统开销的关系如图1 所示。

为最小化SFC 部署的系统开销，节省边缘网络资源，将优化问题 P0描述如下。

观察 P0可得，波束成形和基站间的SFC 部署之间存在如下折中关系。

1) 基站之间的SFC 部署将决定用户的接入基站选取。边缘网络的SFC 部署将规划边缘网络到用户的端到端服务路径，从而为每个用户选取一个接入基站，以无线传输方式完成数据流到用户的最后一跳。若只优化基站之间的SFC 部署开销，不考虑用户的接入基站选取，将导致无线传输功耗开销过高。

2) 用户的接入基站选取将影响基站之间的SFC 部署。作为SFC 部署的最后一个服务节点，用户的接入基站将数据流经无线空口传输到用户。同时，接入基站的位置将影响上一个服务基站的选取，从而依次逆序影响其他所有服务基站的选取。因此，若只考虑波束成形算法的无线传输功耗，不考虑用户的接入基站选取，将导致基站之间SFC 部署开销过高。

因此，无线传输的波束成形和基站之间的SFC部署存在折中关系，需联合优化。

3 算法设计

问题 P0可规约为一个无容量约束设施选址（UFL,uncapacitatedutilitylocation）问题，而UFL问题已被证明是一个NP难问题[9]，因此，P0也是一个NP 难问题，很难找到多项式时间求解算法。通过观察所有约束，发现波束变量和功能部署变量只在式(7)相耦合。因此，本文采用拉格朗日对偶分解技术，通过将wm,n和解耦合，从而将 P0分解为2 个独立的子问题。

3.1 拉格朗日对偶分解

首先，引入拉格朗日对偶乘子λ={λm,n}，将式(7)叠加到 P0的目标函数，即

然而，P2和 P3均难以求解。首先，P2仍可规约为NP 难的UFL 问题；其次，尽管 P3的优化目标是一个凸函数，但式(9)是一个非凸约束。因此，本文提出基于惩罚项的SFC 部署算法和基于路径跟随播波束成形算法，分别求解 P2和 P3。

3.2 基于惩罚项的SFC 部署算法

因为 P2为一个ILP 问题，将 P2中的变量x、y和z松弛，则 P2将成为一个LP 问题。然而，P2通常和其LP 形式不等价，求解 P2对应的LP 问题无法确保其最优解为二进制变量。而求解ILP 问题通常采用分支定界法或割平面法[21-22]，计算复杂度较高，难以求解较大网络规模的SFC 部署问题。因此，本文采用基于Lp(0

其中，p∈(0,1)且ε为任意正数。由文献[11]可知，尽管式(18)的可行域已被松弛，但其最优解仍为二进制变量。因此，式(18)的最优值计算如下。

然后，根据Lp范数的上述性质，将一个基于Lp范数的惩罚项Pε(y)叠加到 P2的目标函数，并将变量松弛。则 P2可转化为

3.3 基于路径跟随的波束成形算法

3.4 计算复杂度分析

4 仿真分析

为验证本文算法的有效性，首先分别验证基于惩罚项的SFC 部署算法、基于凹函数近似的波束成形算法和次梯度方法的收敛性能。其次，将本文算法与文献[9]中的最优单播SFC 部署算法和文献[15]中的随机多播SFC 部署算法进行对比。文献[15]中并未考虑SFC 的最优部署，所以将文献[15]中的多播波束成形机制和SFC 的随机部署相结合。

本文采用的仿真工具是MATLAB R2014b，并使用了凸优化工具包CVX。网络模型为一个经典的六边形七小区蜂窝网络[15,25]，基站间隔设为200 m，每个基站配置10 根天线和5 MHz 频谱带宽，基站最大发射功率为46 dBm。针对信道模型，用户和基站之间的路径损耗模型为PL=32.45+10lgd，PL 单位为dB，d单位为m，小尺度衰落模型服从瑞利分布，对数阴影衰落设置为8 dB，信道热噪声功率谱密度为−174 dBm/Hz。针对内容缓存，使用U-vMOS 视频体验标准[12]的前5 种等级，假设系统存在5 种不同内容，其吞吐量需求分别为0.5 Mbit/s、1 Mbit/s、4 Mbit/s、5 Mbit/s 和10 Mbit/s；每个基站的MEC 服务器随机选取2 项内容进行缓存。针对内容缓存之外的其他功能，假设系统中存在6 项功能，每个MEC 服务器随机选取3 项功能，每项功能的处理容量服从5～15 Mbit/s 的随机均匀分布，每项功能的维护功耗和服务功耗服从1～4 W的均匀分布。针对有限链路，任意2 个基站之间的链路带宽服从10～50 Mbit/s 的均匀分布。

算法参数设置中，算法1 中次梯度方法的初始步长设为100，并按照0.4 的衰减系数逐次衰减；算法2 中，ε和σ的初始值分别设为0.01 和10，乘数因子o=0.8，ϱ=3。

图2 给出了不同折中系数η下的基于惩罚项的SFC 部署算法的收敛性能。设用户数为20，每个用户等概率请求一项内容服务，每项服务的SFC 中均包含4 项有序功能。为衡量算法性能，使用相邻两次 P2-Lp问题的最优解的范数差，即，作为性能指标。如图2 所示，在不同η设置下，本文算法均具有良好收敛性能，在迭代10 次之内达到稳定值。

图2 基于惩罚项的SFC 部署算法的收敛性能

图3 给出了不同折中系数η下的基于路径跟随的波束成形算法的收敛性能。设用户数为20，且等概率请求一项内容服务，每项服务的SFC 均包含4 项有序功能。因为该部分算法仅涉及了基站的波束成形设计，所以使用无线传输功耗作为性能指标。由图3 可看出，在不同η设置下，本文算法均在迭代15 次之内收敛，且功耗值单调递减。这也验证了3.3 节有关算法单调性分析的正确性。

图4 给出了不同折中系数η下的次梯度方法的收敛性能。用户数和SFC 的设置均与图2 和图3 一致。为公平衡量算法性能，克服η过大或过小对问题 P0的优化目标的影响，仅使用系统功耗开销作为性能指标。首先，由图4 可知，尽管次梯度方法相较于基于惩罚项的SFC 部署算法和基于路径跟随的波束成形算法的收敛性能较差，但均在迭代30次左右趋于稳定值。其次，与图3 相比，系统总功耗开销和无线传输功耗开销之间的差值表现为功能维护功耗开销和功能服务功耗开销。最后，随着η的增大，系统总功耗开销逐渐降低。这是因为原始优化问题 P0的优化目标为最小化系统开销，η的增大将使功耗开销的权重增大，数据流开销的权重减小，从而使最优值中的功耗部分降低。

图3 基于路径跟随的波束成形算法的收敛性能

图4 次梯度方法的收敛性能

图5 给出了不同折中系数η下算法1 功耗开销−数据流开销折中曲线。与图4 结论类似，当η=106时，可认为η趋近于无穷大，系统开销只考虑功耗开销，P0简化为功耗开销最小化问题，而算法1 成为功耗开销最小化算法。因此，优化目标中不考虑数据流开销，η=106时数据流开销超过了60 Mbit/s。在η=10−6时，可认为η趋近于无穷小，系统开销只考虑数据流开销，P0简化为数据流最小化问题，优化目标中不涉及功耗开销，故η=10−6时功耗开销达到105 W。图4 和图5 的结论为合理、灵活选择折中系数η提供了理论依据和经验参考。

图5 算法1 的功耗开销−数据流开销折中曲线

图6 给出了本文算法和比较算法在不同用户数下的系统总功耗性能。SFC 的设置均与图2～图4一致，η=103。由图6 可看出，本文算法性能优于最优单播SFC 部署算法。这是因为，若为每个用户独立分配一个波束向量，将显著增大基站的无线传输功耗，使系统总功耗提升。同时，在只考虑系统功耗开销时，随机多播SFC 部署算法的性能优于本文算法。这是因为，η=103时本文算法需折中考虑功耗开销和数据流开销，最优值中的数据流开销部分将导致功耗开销部分增大；而随机多播SFC 部署算法不需要考虑数据流开销。

图6 系统总功耗与用户数之间关系

图7 给出了本文算法和比较算法在不同用户数下的数据流开销性能。SFC 的设置均与图2～图4一致，η=103。如图7 所示，曲线呈分段线性的折线形式，这是因为，数据流开销需取U-vMOS 吞吐量需求的整数倍，无法像功率分配一样取任意连续值。在只考虑系统数据流开销时，最优单播SFC 部署算法的性能优于本文算法。这是因为，η=103时本文算法需折中考虑功耗开销和数据流开销，最优值中的功耗开销部分同样会导致数据流开销部分的增大；而最优单播SFC 部署算法不需要考虑功耗开销。

图7 系统数据流开销与用户数之间关系

5 结束语

本文提出了一种面向内容的联合无线多播的SFC 部署算法，建立了波束成形设计和SFC 映射的联合优化模型。利用拉格朗日对偶分解技术，将优化问题转化为SFC 部署和波束成形设计2 个独立子问题；利用基于Lp范数惩罚项的连续凸近似算法，将整数形式的SFC 部署问题松弛为一个等价线性规划问题，并给出了最优解的等价性证明；利用路径跟随技术，将非凸波束向量优化问题转化为一系列凸优化问题，并给出了算法单调性分析。仿真结果表明，所提算法在系统开销方面优于最优单播SFC 部署算法和随机多播SFC 部署算法。未来工作中，将进一步研究联合协作多播波束成形的多服务路径SFC 部署问题。

附录 定理1 证明