基于NOMA的超密集MEC网络任务卸载和资源分配方案

绳韵，许晨，郑光远

研究与开发

基于NOMA的超密集MEC网络任务卸载和资源分配方案

绳韵1,2，许晨2，郑光远3

（1.华北电力大学电气与电子工程学院，北京 102206；2.北京邮电大学人工智能学院，北京 100876；3.华南理工大学电子与信息学院，广东 广州 510641）

为了提高移动边缘计算（mobile edge computing，MEC）网络的频谱效率，满足大量用户的服务需求，建立了基于非正交多址接入（non-orthogonal multiple access，NOMA）的超密集MEC系统模型。为了解决多个用户同时卸载带来的严重通信干扰等问题，以高效利用边缘服务器资源，提出了一种联合任务卸载和资源分配的优化方案，在满足用户服务质量的前提下最小化系统总能耗。该方案联合考虑了卸载决策、功率控制、计算资源和子信道资源分配。仿真结果表明，与其他卸载方案相比，所提方案可以在满足用户服务质量的前提下有效降低系统能耗。

移动边缘计算；非正交多址接入；任务卸载；资源分配

0 引言

随着各种智能设备和网络服务的迅速发展，人脸识别、自动驾驶、虚拟现实等智能应用越来越普及。这些应用无一例外地需要庞大的计算资源对数据进行实时处理。然而，由于设备物理尺寸和电池容量受限，一般的智能设备无法提供强大的计算能力满足这些应用的需求。为了应对这一挑战，欧洲电信标准化协会于2014年提出了移动边缘计算（mobile edge computing，MEC）的概念，旨在无线网络边缘侧（如基站、无线接入点等）部署具有强大计算能力的服务器就近为用户提供所需的服务[1]。借助MEC，用户可以将自己的计算任务卸载到边缘服务器上执行，从而降低任务的计算时延、减少用户的能耗，并满足用户的服务质量（quality of service，QoS）要求[2-3]。然而，随着移动终端数量的指数级增长，由于频谱资源有限，传统的蜂窝MEC网络无法满足大规模用户同时卸载的服务需求。

超密集网络（ultra-dense network，UDN）和非正交多址接入（non-orthogonal multiple access，NOMA）是未来无线网络中提高频谱利用率和系统吞吐量的两种新兴技术[4-5]。UDN的基本原理是在宏蜂窝内部署小基站，不同小小区通过复用宏小区的信道资源提升网络的频谱利用率[6]。由于同层干扰和跨层干扰的存在，如何有效地进行干扰管理和资源分配在超密集网络中是非常重要的。子信道分配是超密集网络中进行干扰管理的重要手段。不同于传统的正交多址接入（orthogonal multiple access，OMA）技术，NOMA技术通过功率域复用，在发送端使用叠加编码的方式使多个用户占用相同的频域/时域资源进行信号传输，然后在接收端采用串行干扰消除（successive interference cancellation，SIC）技术识别不同用户的信号[7]，以获得更高的频谱效率和更大的系统吞吐量。近年来，许多研究已经证明了NOMA和超密集网络的结合在提升频谱效率和系统吞吐量方面的优势[8-9]。

目前，已存在一些工作研究了NOMA和MEC技术的融合。文献[4]将NOMA技术应用在MEC网络的上行和下行链路，并证明了NOMA技术的引入可以进一步降低卸载过程的时延和能耗。文献[10]提出了一种联合计算卸载和资源分配的方案以实现任务执行时延的最小化。文献[11]提出了一种联合优化传输功率、传输时间分配和任务卸载分区的方案，达到最小化用户总能耗的目的。关于MEC和超密集网络的结合，文献[5]设计了计算卸载机制使设备的总能耗最小化。文献[12]综合考虑了任务执行时间和能量消耗，提出了一个任务虚拟机匹配算法。最近也有一些工作研究了基于超密集网络中的NOMA-MEC系统[13-15]。文献[13]研究了超密集网络中NOMA-MEC系统的资源分配问题，以最小化系统总开销为目标，联合优化了用户分簇、发射功率和计算资源分配。文献[14]考虑了一种两层的异构网络，用户可以通过NOMA技术将计算任务卸载到宏基站或者小基站执行，并提出了一种高效的边缘卸载决策算法最小化计算成本。以最大化系统能效为目标，文献[15]研究了基于NOMA的MEC在超密集网络中的用户接入、传输功率和计算资源分配的联合优化问题。

从现有的研究工作中看，部分研究者对超密集网络中NOMA-MEC系统的任务卸载和资源分配联合优化进行了研究，然而忽略了子信道资源的高效分配问题。在超密集网络中，信道资源分配是一种降低干扰、提高频谱效率和能效的重要手段。在NOMA-MEC超密集网络中，多个用户同时进行任务卸载会产生严重的干扰，从而造成传输时延的增加和发射功率的浪费，影响用户的服务体验。而信道资源分配是一种降低干扰、提高频谱效率和能效的重要手段。此外，在基于NOMA的异构MEC网络中，卸载决策和用户间的计算资源竞争会影响信道分配方案的设计，这比传统的NOMA异构网络[8-9]更具有挑战性。因此，本文提出了一种联合任务卸载和多维度资源分配的优化方案，综合考虑了任务卸载决策、用户功率控制、计算资源和子信道资源分配，在满足用户QoS的前提下最小化系统能耗。本文的主要贡献如下。

（1）构建了一个基于NOMA的超密集MEC网络，其中每个小基站都部署一个MEC服务器并使用NOMA技术服务其相关用户。之后，本文提出了一个联合任务卸载决策、功率控制、计算资源和子信道资源分配的优化问题，在保证每个任务QoS的前提下最小化所有用户的能耗。

（2）由于所提优化问题是一个混合整数非线性规划，属于NP难问题，无法在多项式时间内获得最优解，因此本文将原混合问题解耦为多个子问题，并提出一个基于迭代优化算法的解决方案，获得原问题的近似最优解。

（3）通过模拟仿真实验，将提出的方案与不同的卸载方案和正交接入方案进行了对比。仿真结果表明，与其他卸载方案相比，本文所提方案可以实现更低的系统能耗，并且能够以较低的复杂度获得接近穷举方案得到的结果。

1 系统模型与问题描述

图1 基于NOMA的超密集MEC系统模型

1.1 通信模型

1.2 计算模型

（1）本地计算

相应能量消耗为：

（2）边缘计算

上传过程中的能耗为：

能耗为：

1.3 问题描述

本文以最小化用户总能耗为目标，联合考虑任务卸载决策、功率控制、计算资源和子信道资源分配，同时保证每个任务的服务质量要求。优化问题描述为：

式（11）是一个混合整数非线性规划问题，它涉及二元变量和连续变量，且目标函数是非凸的。此外，卸载决策与资源分配的耦合使得问题更具挑战性。一般情况下无法在多项式时间复杂度内获得该问题的最优解。因此，本文使用块坐标下降法将原问题解耦为资源分配子问题和卸载决策子问题[16]，通过迭代求解这两个子问题直到目标值收敛，即可获得原问题的近似解。

2 联合任务卸载和资源分配的优化方案

本节提出了一种联合任务卸载和资源分配的方案，通过迭代求解资源分配和卸载决策两个子问题，得到所提问题的联合解。

2.1 资源分配

式（12）也是一个涉及二元变量和连续变量的混合整数非线性规划问题，且目标函数是非凸的，不同优化变量之间具有强耦合性。为了解决该问题，将其解耦为两个子问题，即计算资源分配问题，以及联合子信道分配和功率控制问题，通过解决这两个子问题获得式（12）的解。

2.1.1 计算资源分配

由式（5）～式（9）可知，分配给用户的计算资源越多，任务执行过程中花费的时间越少，那么在总时延约束不变的条件下，留给任务上传的时间越长，则用户的上传能耗越小[17]。因此，从计算资源分配的角度出发，能耗优化问题可以表述为最小化每个小基站服务的卸载用户的任务执行时延，即：

相应地，可以得到每个任务的最小上传速率要求为：

2.1.2 子信道分配

给定计算资源分配条件下，原问题（12）可以转化为如下通信资源分配问题：

对于每一个小基站，其效用函数可以定义为服务的所有卸载用户能耗总和的倒数：

两个小基站交换它们匹配的子信道，同时保持其他小基站匹配不变。交换阻塞对定义如下。

上述定义表明，如果一个交换匹配批准通过，那么所有参与此次交换匹配的小基站和子信道的效用值不会降低，且至少有一个参与者的效用值会提高。

基于上述定义，本文提出了一种基于交换匹配的子信道分配和功率控制算法。首先，将每个小基站随机匹配一个子信道，得到一个初始匹配结果。在交换匹配过程中，随机选择两个小基站，并临时交换它们匹配的子信道，其他小基站的匹配保持不变。然后对两个子信道上的用户执行功率控制，得到基站和子信道的效用值。这两个小基站形成交换阻塞对，则执行交换操作。交换匹配过程持续进行，直到不存在交换阻塞对，最终获得双边交换稳定的匹配结果。

2.1.3 功率控制

该问题是凸优化问题，可利用凸优化工具直接求解[18]。因此，可以利用SCA算法迭代解决式（26）获得原式（22）的解[23]。

2.1.4 资源分配算法

通过求解上述两个子问题（式（17）和式（22）），得到最终的任务卸载用户的资源分配算法，见算法1。

算法1 任务卸载用户的资源分配算法

1）计算资源分配

4）通过式（15）得到计算资源分配结果

5）通过式（16）计算最小数据速率要求

6）end for

7）end for

8）联合子信道分配和功率控制

10）交换匹配过程

11）Repeat

17） end if

18） end for

19） end for

20）until 没有交换阻塞对存在

引理1 每次交换操作后，系统能耗降低。

定理1 算法1在有限次交换匹配过程中收敛。

证明 因为用户数量有限，所以计算资源分配过程的循环次数也有限。算法1的收敛性主要取决于交换匹配过程。根据引理1，每次交换操作后，系统的总能耗都会降低。此外，由于有限的通信和计算资源，系统能耗是有界的。因此，算法1在有限次迭代后必然会收敛。

2.2 卸载决策优化

2.3 联合优化方案

本节提出一个联合任务卸载和资源分配算法，见算法2。

算法2 联合任务卸载和资源分配算法

1）Repeat

2）通过表1计算任务卸载用户的能耗

3）通过式（27）更新用户的卸载决策

4）until 没有用户改变自身卸载决策

3 仿真分析

本节通过仿真验证所提联合优化算法的性能，仿真参数见表1。假设一个半径为1 000 m的宏小区，小小区随机分布在该区域中。小基站的数量为4～8个，子信道数量为4个，并假设每个基站的计算能力可以满足关联用户的计算需求。为了限制同信道干扰，降低硬件复杂度和处理时延，假设每个NOMA簇包含2个用户，每个小基站分配一个子信道[24]。详细仿真参数设置见表1，这些参数是根据现有研究[5,25]设置的。在仿真中，将所提出的基于NOMA的任务卸载和资源分配方案（NOMA-task offloading and resource allocation，N-TORA）与其他4种方案的能耗性能进行了比较。为了便于理解，对文献[3，26-27]中的对比方案和其他基准方案进行了说明，如下所示：

（1）全部本地执行方案（entire local processing，ELP）：每个用户的任务都在本地执行，即ELP方案。

（2）全部MEC执行方案[3]（entire MEC processing，EMP）：结合文献[3]中的EMP方案，即所有用户的任务都卸载到关联基站上执行，通过算法1获得发射功率、计算资源和子信道分配的结果。

（3）基于OMA的任务卸载和资源分配方案[26]（OMA-task offloading and resource allocation，O-TORA）：为了研究子信道分配对系统性能的影响，将所提N-TORA方案与文献[26]中的方案进行了对比。文献[26]中用户通过正交频分多址接入方式将任务卸载到关联基站上，即每个小小区的带宽平均分配给关联用户。

（4）联合功率控制和子信道分配的任务卸载和资源分配方案[27]（joint power allocation and sub-channel assignment-task offloading and resource allocation，JPS-TORA）：由于复杂度较高，在仿真中很难通过穷举算法找到最优的任务卸载和子信道分配方案，因此，采用文献[27]中的联合功率控制和子信道分配算法获得最优的子信道，并结合所提出的任务卸载和资源分配方案以实现全局最优解。

表1 仿真参数

图2为总能耗与算法2的迭代次数的关系。从图2可以看出，随着小基站数量的增加，总能耗也逐渐增加。此外，随着迭代次数的增加，系统能耗会逐渐降低并最终收敛于一个定值。图2中收敛所需的迭代次数为2次，说明所提N-TORA方案的收敛速度是非常快的。

图2 总能耗与迭代次数关系

图3 总能耗与小基站数量关系

图4为不同算法下所有用户的总能耗与任务最大容忍时延的关系。由图4可知，随着任务时延要求放宽，能耗逐渐降低。这是因为随着任务卸载传输时间延长，发射功率要求降低，从而减小了任务上传过程中的能耗。此外，所提N-TORA方案在节约能耗方面具有明显优势。

图5为子信道数量不同时，总能耗与小基站数量的关系。由图5可知，随着小基站数量的增加，总能耗是逐渐增加的。另外，子信道数量减少会导致系统总能耗增大，这是因为当子信道较少时，占用同一子信道的小小区数量增加，导致严重的小区间干扰，进而增加了卸载过程的能耗。

图4 总能耗与任务最大容忍时延关系

图5 总能耗与小基站数量关系

图6 总能耗与输入数据大小关系

图7 卸载用户比例与输入数据大小的关系

4 结束语

本文研究了基于NOMA的超密集MEC网络中以能耗最小化为目标的任务卸载和资源分配问题。为了在保证每个任务的QoS的要求下，最小化所有用户的能耗，本文联合优化了卸载决策、发射功率、计算资源和子信道资源分配。由于该优化问题是一个混合整数非线性问题，通常无法在多项式时间内得到最优解，因此，本文将原问题解耦为卸载决策和资源分配两个子问题，并提出了一种高效迭代优化方案获得原问题的近似解。仿真结果表明，与其他基准方案相比，所提方案能够实现更低的系统能耗，并且以较低的复杂度获得接近穷举方案的结果。在未来，可将目前的工作扩展到协同计算场景，允许用户的任务可以由不同的MEC服务器协同执行。此外，笔者还将考虑MEC服务器的缓存能力，通过预先缓存多个用户所需的数据库或程序节约系统的通信和计算资源。

[1] MACH P, BECVAR Z. Mobile edge computing: a survey on architecture and computation offloading[J]. IEEE Communications Surveys & Tutorials, 2017, 19(3): 1628-1656.

[2] MAO Y Y, YOU C S, ZHANG J, et al. A survey on mobile edge computing: the communication perspective[J]. IEEE Communications Surveys & Tutorials, 2017, 19(4): 2322-2358.

[3] ZHAO J H, LI Q P, GONG Y, et al. Computation offloading and resource allocation for cloud assisted mobile edge computing in vehicular networks[J]. IEEE Transactions on Vehicular Technology, 2019, 68(8): 7944-7956.

[4] DING Z G, FAN P Z, POOR H V. Impact of non-orthogonal multiple access on the offloading of mobile edge computing[J]. IEEE Transactions on Communications, 2019, 67(1): 375-390.

[5] FENG S M, ZHANG R, XU W, et al. Multiple access design for ultra-dense VLC networks: orthogonal vs non-orthogonal[J]. IEEE Transactions on Communications, 2019, 67(3): 2218-2232.

[6] LI J, CHU S F, SHU F, et al. Contract-based small-cell caching for data disseminations in ultra-dense cellular networks[J]. IEEE Transactions on Mobile Computing, 2019, 18(5): 1042-1053.

[7] ABU MAHADY I, BEDEER E, IKKI S, et al. Sum-rate maximization of NOMA systems under imperfect successive interference cancellation[J]. IEEE Communications Letters, 2019, 23(3): 474-477.

[8] ZHANG Q, LUO K, WANG W, et al. Joint C-OMA and C-NOMA wireless backhaul scheduling in heterogeneous ultra dense networks[J]. IEEE Transactions on Wireless Communications, 2020, 19(2): 874-887.

[9] QIN Z J, YUE X W, LIU Y W, et al. User association and resource allocation in unified NOMA enabled heterogeneous ultra dense networks[J]. IEEE Communications Magazine, 2018, 56(6): 86-92.

[10] WU Y, NI K J, ZHANG C, et al. NOMA-assisted multi-access mobile edge computing: a joint optimization of computation offloading and time allocation[J]. IEEE Transactions on Vehicular Technology, 2018, 67(12): 12244–12258.

[11] PAN Y J, CHEN M, YANG Z H, et al. Energy-efficient NOMA-based mobile edge computing offloading[J]. IEEE Communications Letters, 2019, 23(2): 310-313.

[12] SENG S M, LUO C Q, LI X, et al. User matching on blockchain for computation offloading in ultra-dense wireless networks[J]. IEEE Transactions on Network Science and Engineering, 2021, 8(2):1167-1177.

[13] LI L X, CHENG Q Q, TANG X, et al. Resource allocation for NOMA-MEC systems in ultra-dense networks: a learning aided mean-field game approach[J]. IEEE Transactions on Wireless Communications, 2021, 20(3):1487-1500.

[14] NOURI N, ABOUEI J, JASEEMUDDIN M, et al. Joint access and resource allocation in ultradense mmWave NOMA networks with mobile edge computing[J]. IEEE Internet of Things Journal, 2020, 7(2): 1531-1547.

[15] SENG S M, LI X, JI H, et al. Joint access selection and heterogeneous resources allocation in UDNs with MEC based on non-orthogonal multiple access[C]//Proceedings of 2018 IEEE International Conference on Communications Workshops. Piscataway: IEEE Press, 2018: 1-6.

[16] LI Y, XU G C, GE J Q, et al. Jointly optimizing helpers selection and resource allocation in D2D mobile edge computing[C]//Proceedings of 2020 IEEE Wireless Communications and Networking Conference. Piscataway: IEEE Press, 2020: 1-6.

[17] HAN S J, XU X D, FANG S S, et al. Energy efficient secure computation offloading in NOMA-based mMTC networks for IoT[J]. IEEE Internet of Things Journal, 2019, 6(3): 5674-5690.

[18] 吴柳青, 朱晓荣. 基于边-端协同的任务卸载资源分配联合优化算法[J]. 电信科学, 2020, 36(3): 42-52.

WU L Q, ZHU X R. Joint optimization algorithm for task offloading resource allocation based on edge-end collaboration[J]. Telecommunications Science, 2020, 36(3): 42-52.

[19] BANDO K. Many-to-one matching markets with externalities among firms[J]. Journal of Mathematical Economics, 2012, 48(1): 14-20.

[20] 崔静静. 非正交多址接入系统功率分配优化设计与性能分析[D]. 成都: 西南交通大学, 2018.

CUI J J. Power allocation optimization design and performance analysis of non-orthogonal multiple access system[D]. Chengdu: Southwest Jiaotong University, 2018.

[21] BODINE-BARON E, LEE C, CHONG A, et al. Peer effects and stability in matching markets[C]//Proceedings of International Symposium on Algorithmic Game Theory. [S.l.:s.n.], 2011.

[22] LI S L, TAO Y Z, QIN X Q, et al. Energy-aware mobile edge computation offloading for IoT over heterogenous networks[J]. IEEE Access, 2019(7): 13092-13105.

[23] PAPANDRIOPOULOS J, EVANS J S. SCALE: a low-complexity distributed protocol for spectrum balancing in multiuser DSL networks[J]. IEEE Transactions on Information Theory, 2009, 55(8): 3711-3724.

[24] ZHAO J J, LIU Y W, CHAI K K, et al. Spectrum allocation and power control for non-orthogonal multiple access in HetNets[J]. IEEE Transactions on Wireless Communications, 2017, 16(9): 5825-5837.

[25] WU W, ZHOU F H, HU R Q, et al. Energy-efficient resource allocation for secure NOMA-enabled mobile edge computing networks[J]. IEEE Transactions on Communications, 2020, 68(1): 493-505.

[26] TANG L R, HU H L. Computation offloading and resource allocation for the Internet of Things in energy-constrained MEC-enabled HetNets[J]. IEEE Access, 2020(8): 47509-47521.

[27] DI B Y, SONGL Y, LI Y H. Sub-channel assignment, power allocation, and user scheduling for non-orthogonal multiple access networks[J]. IEEE Transactions on Wireless Communications, 2016, 15(11): 7686-7698.

Task offloading and resource allocation in NOMA-based ultra-dense MEC networks

SHENG Yun1,2, XU Chen2, ZHENG Guangyuan3

1.School of Electrical and Electronic Engineering, North China Electric Power University, Beijing 102206, China 2.School of Artificial Intelligence, Beijing University of Posts and Telecommunications, Beijing 100876, China 3.School of Electronic and Information Engineering, South China University of Technology, Guangzhou 510641, China

In order to improve spectrum efficiency and meet the service demands of massive users, a non-orthogonal multiple access (NOMA)-based ultra-dense mobile edge computing (MEC) system was considered. In order to solve the serious communication interference caused by simultaneous offloading of multiple users and make efficient use of edge server resources, a joint task offloading and resource allocation scheme was proposed to minimize the system energy consumption while meeting the quality of service (QoS) of all users. Offloading decision, power control, computation resource and subchannel resource allocation were jointly considered in the proposed scheme. Simulations results show that the proposed scheme can efficiently lower system energy consumption compared to the other offloading schemes.

MEC, NOMA, task offloading, resource allocation

TN929.5

A

10.11959/j.issn.1000−0801.2022033

2021−10−12；

2022−02−09

许晨，chen.xu@bupt.edu.cn

国家自然科学基金资助项目（No.62071179）；北京市科技新星计划项目（No.Z191100001119124）；中央高校基本科研业务费专项资金资助项目（No.2019MS009）

The National Natural Science Foundation of China (No.62071179), The Beijing Nova Program of Science and Technology (No.Z191100001119124), The Fundamental Research Funds for the Central Universities (No.2019MS009)

绳韵（1998− ），女，华北电力大学电气与电子工程学院硕士生，主要研究方向为移动边缘计算网络中的资源管理。

许晨（1988− ），女，博士，北京邮电大学人工智能学院副研究员、博士生导师，主要研究方向为智能网络优化、协作通信与计算、未来移动通信系统。

郑光远（1996− ），男，华南理工大学电子与信息学院博士生，主要研究方向为移动边缘计算网络中的资源分配、能量管理和干扰管理。