计算卸载作为移动边缘计算（MEC）研究的热点问题之一，是实现用户低延时通信的一项重要技术。由于通信资源的有限性，任务的完成时间难以保证。在本文中，我们将非正交多址接入技术（NOMA）应用到MEC系统中，并提出了一个联合计算卸载和资源分配问题，以最大限度的提高系统卸载收益。首先，我们将资源分配问题分解为联合子信道和用户传输功率分配问题（JSPA），并利用用匹配联盟方法和二分法解决该问题。然后，基于资源分配的结果，我们提出了一种计算卸载决策算法，以获取最优的任务卸载方案。通过与其它方案相比，本文所提出的方案能够显著的提高系统的卸载收益。
1.引言
随着物联网的迅速发展，各种新兴移动应用程序呈现爆炸式增长。然而，移动设备(UE)的计算资源有限，不能支持这些应用程序高能耗的密集计算。为了解决上述挑战，移动边缘计算在更靠近UE的网络边缘提供移动设备所需的服务和云端计算能力，减少了端到端的延迟[1]。
在MEC网络中，采用正交多址接入（OMA）技术进行数据卸载已有了广泛的研究[2]。最近的研究发现，与正交多址（OMA）技术相比，非正交多址（NOMA）技术作为第五代网络的关键技术，使多个无线设备利用相同的子信道同时进行计算卸载，从而显著提高频谱利用效率和卸载效率。考虑到NOMA的优势，将NOMA应用到MEC中可以在降低能耗和时延方面获取更多的收益[3-4]。
在[3]中，研究了NOMA-MEC系统的计算卸载和数据内容缓存问题，提出了块连续上界极小方法，以实现所有用户的最小完成时延。在[4]中，作者考虑了多用户NOMA-MEC网络，提出了一种二分搜索迭代算法，以达到最小的任务延迟，降低算法复杂性。
上述的[3-4]主要是集中在单小区网络，将NOMA技术应用到多小区网络引起了越来越多的关注。[5]设计了一种高效的移动边缘计算卸载决策算法，以分析执行延迟和能耗之间的权衡。但是作者没有考虑由于时间和能耗的数量级不同而产生的冲突问题。[6]对任务的计算卸载、本地计算资源分配和NOMA传输的持续时间进行联合优化，以尽量减少智能终端完成所有任务的总能量消耗。[5]和[6]均没有考虑子信道的分配问题，导致用户无法选择他们偏好的子信道，降低了系统的性能。
基于上述观察结果，在本文，我们将NOMA技术应用于多小区多用户的MEC网络中，实现系统卸载收益的最大化。与上述工作不同的是，文献[3-4]只考虑了单小区的情况，文献[5-6]忽略了子信道的分配问题。我们工作的主要贡献如下：
针对超密集网络，我们提出了基于NOMA的联合资源分配与计算卸载问题，以最大化系统卸载收益。
我们将非凸的系统卸载收益最大化问题分解为两个子问题：资源分配问题和计算卸载决策问题。
我们用匹配博弈、值近似方法和二分法解决资源分配问题，并提出了一种计算卸载决策算法解决计算卸载决策问题。

表1 关键符号

    任务n的数据大小
    完成任务n所需要的CPU周期数
    用户n的上传功率


    总带宽
    任务n通过子信道c上传到MEC服务器m的信道增益
    任务n卸载到边缘服务器m
    任务n占用子信道c
    用户n的计算能力
    取决于CPU芯片体系结构的系数
    共享子信道c的用户集合


图1  系统模型

2.系统模型和问题形成
如图1所示，我们考虑了一个有N个移动设备（UE）和M个基站（BS）的MEC系统。UE集和BS集用符号可以分别表示为，。系统的总带宽为B，将其划分为C个正交的子信道，表示为。每个UE都有一个计算任务要完成，并且每个任务都是原子不可分的，其任务既可以在本地执行，也可以卸载到边缘服务器执行。我们分别从本地计算模型、通信模型和卸载模型三个方面建立系统模型。为了便于阅读，表1概括了本文中所使用的关键符号。
A.本地计算模型
我们用二元组来表示用户的任务，其中[bits]表示任务的数据量，表示完成任务所需的工作量。和的值可以通过程序分析器获得。我们定义二进制变量来表示任务的卸载决策。表示将任务卸载到边缘服务器m执行，否则任务在本地执行。
对于，我们在本地执行任务，表示用户n的本地计算能力，则执行任务的总时间可以计算为，

我们使用文献[7]中的能耗模型，计算任务在本地执行时的能耗，


B.通信模型
本文使用NOMA技术，使多个卸载用户可以同时共享一个子信道进行卸载。我们将共享同一子信道的卸载用户分为一组，并且组内用户有干扰，组间用户无干扰。表示共享子信道c的卸载用户集合。不失一般性，我们将同一组中用户的信道增益递减排列，表示组中用户按其到基站之间的信道增益递减排列的顺序。根据NOMA的原理，每个基站按顺序的依次解码信道增益高的设备信号，并将未解码的设备信号作为干扰信号。用户n通过子信道c上传到边缘服务器m的信噪比SINR计算为：

根据香农公式，设备n通过子信道c将任务上传到边缘服务器m的速率计算为：


C.卸载模型
任务n通过子信道c上传到MEC服务器m的时间和能耗分别为：


任务n在MEC服务器m计算的时间为：

那么用户n卸载任务的总时延为：

D.问题形成
我们的目标是通过联合优化无线资源分配和计算卸载策略来最大化系统的卸载收益。系统的卸载收益函数可以定义为：

其中，当用户在本地执行时，系统的卸载收益为0。因此最大化系统卸载收益的优化问题可以定义为：

 





3.联合资源分配和计算卸载方案
为了解决混合整数非凸问题p，在本节我们提出了联合资源分配和任务卸载决策的方案。我们将问题P解耦为资源分配问题和任务卸载问题，目标函数（10a）重写为：

其中 
划分为两个具有依赖关系的子问题：
1）固定卸载策略O，对通信资源进行分配，由于等式（11）右侧的第一项为常数，因此资源的分配问题定义为：


其中
2）固定通信资源分配的值，进行计算卸载决策，计算卸载问题定义为：


通过交替优化子问题和，最终获取问题P的解。
3.1 资源分配问题
将等式（12）右侧的第一项作为通信资源分配问题的目标函数，通信资源分配问题具体可以表示为：


子问题仍然是一个非凸问题，我们将该问题分解为子信道分配问题和上传功率分配问题。
3.1.1子信道的分配问题
对于固定的上传功率，子信道分配问题可以定义为：


在上传功率固定的情况下，我们将该问题建模为匹配博弈的过程。由于有C个子信道，因此我们定义联盟集合为，并且满足，，。其中，表示共享子信道i的用户集合。为卸载的用户总数，卸载的用户集合表示为。
当共享同一子信道的用户数量较大时，会增加用户间的干扰，进而增加了系统开销。因此我们需要设计一个有效的匹配博弈方案来增加系统的总收益。
首先，我们将匹配博弈定义为一个三元组，其中表示玩家集合，即卸载到边缘服务器的用户集；是玩家所获取的回报函数，我们将目标函数（16）*-1作为回报函数；表示联盟集合。对于联盟，表示联盟所带来的总收益。

由于每个用户对于不同的联盟都有不同的偏好程度，因此我们为每个用户定义偏好关系。用户根据定义的偏好关系，在任意两个联盟之间进行比较选择。用户偏好关系定义为：

这表示当用户n在的总收益大于在中的总收益时，用户n更想加入联盟。其中表示卸载用户n的偏好。根据用户偏好，我们建立用户对每个联盟的偏好列表。每个卸载用户都可以根据其偏好关系，决定加入一个联盟或离开一个联盟。对于转换联盟的规则，我们可以定义为：


算法1: 基于匹配博弈的子信道分配
输入: 卸载策略O; 上传功率P; 迭代次数

输出: 子信道分配策略 D
1: 初始化UEs的偏好列表 
  2: 根据 ,初始化联盟集合
  3: 
4:  for iter=1; ; iter++ do 
5:     从中随机选择用户n 
6:     用户n的联盟为 
7:     随机选择另一个联盟 
8:     if  then 
9:         
10:        
11:     else
12:          
13:     end if
14:  end for


根据用户偏好和联盟转换定义，我们在算法1设计了有效匹配博弈的算法来进行子信道的分配。首先根据用户的偏好关系，建立用户对每个联盟的偏好列表，再根据PreList, 创建初始的联盟集合（1-2行）。然后从卸载集合中随机选择一个用户n，用户n当前的联盟为，再随机选择另一个联盟（5-7行）。通过比较用户n在这两个联盟中的偏好，决定是否进行联盟转换。如果用户n更偏向于加入联盟，则进行联盟转换并对联盟集合进行更新（8-10行）。为了降低算法的时间复杂度，如果进行联盟转换，我们就将Count的值置为0；没有转换，则执行Count++操作。当Count=MaxCount时，即连着MaxCount次的迭代中都没有发生联盟转换，算法实现纳什均衡（11-13行）。
3.1.2上传功率的分配问题
对于固定的子信道分配，功率分配问题可以定义为：

  
其中，可以看出问题（20）是一个非凸问题。由于NOMA的传输方式，共享同一子信道的用户之前产生干扰，从而造成了用户之间上传功率的关联。因此我们需要找到干扰的一个近似值。根据约束，我们给出了可实现的上传功率上限值，可以获取近似干扰值：

由于其它用户造成的干扰值本身就是一个很小的值，因此近似后的值对子问题的结果不会产生较大的影响。问题（21）可以重写为，


其中， 。为了便于表示，我们将式（23）记为，并对（23）求一阶导。可得存在值，在区间上，函数单调递减，区间上，函数单调递增，从而获得功率分配问题的最优解。
算法2: 基于二分查找的上传功率分配
输入: 最大上传功率; 最小上传功率r; >0

输出: 上传功率分配策略 P*
1:  if do 
 2:      
3:  else
4:     while 
5:        
6:         if do
7:            
8:         else
9:             
10:         end if
11:     end while

12:  end if
根据以上所述，我们在算法2中提出了上传功率的分配方案。首先判断函数是否递，若递减，则获取当前功率分配的最优值（1-2行），否则使用二分查找的方式寻找最优值（4-11行）。
3.2计算卸载决策
对于给定的资源分配，我们对计算任务进行卸载决策，以获取最大的卸载收益。计算任务的卸载决策具体定义为：


令
在算法3中，我们提出了一种计算任务卸载决策算法，首先，根据效用函数(24)初始化所有任务的卸载决策变量，其中表示未卸载的用户集合（1行）。如果存在未卸载用户，选择将其卸载后系统效用值增加，则将其从集合中移除，加入卸载集合（3-8行）。如果存在卸载用户，将其从卸载集合移除后，系统的效用值增加，则将其从集合O*中移除，加入集合（9-14行）。直到不存在可以增加系统效用的移除或添加操作。

算法 3: 计算任务的卸载决策算法
输入: 资源分配结果 P, D, 

输出: 任务卸载策略集 O*
1:  初始化所有任务的卸载决策
 2:  repeat   
3:    if  then
4:       更新
5:        
6:    else
7:           
8:    end if
9:    if    then    
10:       更新
11:       

12:    else
13:       
14:    end if
15:  until  &&
4.仿真实验
4.1 仿真参数设置
在本节中，我们进行了仿真实验以验证所提算法的准确性。在网络中我们部署了8个边缘服务器，边缘服务器均匀的位于中心为(0,0)，半径为600m的圆上。用户设备的数量，随机分布在网络覆盖的区域内。系统的总带宽B为10MHZ，每个子信道的带宽为1MHZ（10个子信道）。每个计算任务的大小为[5x104, 105]bits，用户设备的计算能力为1GHZ。我们设置边缘服务器的计算能力为5GHZ，用户最大的上传功率为30dBm，每个子信道的最大容量为6。为了评估我们提出算法的性能，我们将其与以下两种策略进行比较：
（1）基于OMA的卸载 ：采用正交多址的接入方式进行卸载。
（2）基于NOMA的全部卸载：在我们所考虑的NOMA-MEC系统中，所有的用户设备都选择将计算任务卸载到边缘服务器执行。
4.2 性能比较
图2验证了在不同用户数量下，算法1的收敛性。我们可以看出，当用户数量为20时，迭代12次即可收敛，当用户数量为50时，需迭代20次达到收敛。这是由于用户数量增加，导致该算法的搜索范围增加，进而使迭代次数增加。通过观察，对于不同的用户数目，算法1在迭代有限次后都能达到收敛状态，表明我们提出的算法可以很好的适应不同数量的用户，并具有较好的收敛性。

图2  UE数量对算法1迭代次数的影响
在图3中，描述了用户最大传输功率对平均系统收益的影响，并与基于OMA的卸载、基于NOMA的全部卸载这两种方案进行了对比。可以看出，这三种策略的平均系统收益都是随着最大传输功率的增加而增加。但是当传输功率增加到35dBm时，平均系统收益开始呈现下降的趋势。这是因为传输功率较大导致用户间的干扰增加。进而降低了系统收益。并且，与其它两种策略进行对比，我们提出的算法可以实现最大的系统收益。


图3  UEs的最大上传功率对系统收益的影响

为了分析不同的子信道容量对平均系统收益的影响，我们在图4中描述了子信道容量在范围[1,10]变化时，平均系统收益的变化情况。我们可以发现，随着子信道容量的增加，平均系统收益呈现递增的趋势。当子信道容量增加到一定值后，由于共享同一子信道的用户数增加，该子信道的干扰增加，导致平均系统收益的增长速度变慢。并且当子信道的容量从9增加到10后，基于NOMA的全部卸载方案的平均系统收益降低。

图4  子信道容量对系统收益的影响
5.结论
针对支持NOMA的超密集网络，本文提出了一种对无线资源管理和任务卸载决策的方案。通过优化无线资源管理（上传功率和信道分配）、任务卸载决策，最大化系统卸载收益。仿真结果表明，本文提出的方案比基于OMA的卸载以及基于NOMA的全部卸载收益更高，尤其是用户数量增加时，优势更加明显。在未来的工作中，为了更加符合实际场景，我们将进一步的考虑用户的移动性问题。
参考文献
[1]Mao Y ,  You C ,  Zhang J , et al. A Survey on Mobile Edge Computing: The Communication Perspective[J]. IEEE Communications Surveys & Tutorials, 2017, PP(99):1-1.
[2]Ning Z ,  Dong P ,  Kong X , et al. A Cooperative Partial Computation Offloading Scheme for Mobile Edge Computing Enabled Internet of Things[J]. IEEE Internet of Things Journal, 2019, 6(3):4804-4814.
[3]Luan N ,  Pham Q V ,  Nguyen T , et al. Joint Computational Offloading and Data-Content Caching in NOMA-MEC Networks[J]. IEEE Access, 2021, 9:12943-12954.
[4]Fang F ,  Xu Y ,  Ding Z , et al. Optimal Resource Allocation for Delay Minimization in NOMA-MEC Networks[J]. IEEE Transactions on Communications, 2020, PP(99):1-1.
[5]Xu C ,  Zheng G ,  X  Zhao. Energy-Minimization Task Offloading and Resource Allocation for Mobile Edge Computing in NOMA Heterogeneous Networks[J]. IEEE Transactions on Vehicular Technology, 2020:1.
[6]Wu Y ,  Shi B ,  Qian L P , et al. Energy-Efficient Multi-task Multi-access Computation Offloading Via NOMA Transmission for IoTs[J]. IEEE Transactions on Industrial Informatics, 2020, 16(7):4811-4822.
[7]Chen, Xu. Decentralized Computation Offloading Game for Mobile Cloud Computing[J]. IEEE Transactions on Parallel & Distributed Systems A Publication of the IEEE Computer Society, 2015.