基于终端直通通信的多用户计算卸载资源优化决策

李余，何希平，唐亮贵

（1.重庆工商大学 计算机科学与信息工程学院，重庆 400067； 2.重庆市检测控制集成系统工程实验室（重庆工商大学），重庆 400067）（∗通信作者电子邮箱liyu@ctbu.edu.cn）

基于终端直通通信的多用户计算卸载资源优化决策

李余1，2*，何希平1，2，唐亮贵1，2

（1.重庆工商大学 计算机科学与信息工程学院，重庆 400067； 2.重庆市检测控制集成系统工程实验室（重庆工商大学），重庆 400067）（∗通信作者电子邮箱liyu@ctbu.edu.cn）

随着计算密集和时延敏感类应用的激增，移动边缘计算（MEC）被提出应用在网络边缘为用户提供计算服务。针对基站（BS）端边缘服务器计算资源有限以及网络边缘用户远距离计算卸载的时延较长等问题，提出了基于终端直通（D2D）通信的多用户计算卸载资源优化决策，将D2D融入MEC网络使用户以D2D方式直接卸载任务到相邻用户处执行，从而能够进一步降低卸载时延和能耗。首先，以最小化包括时延和能耗的系统计算总开销为优化目标，建模多用户计算卸载和多用户计算资源分配的联合优化问题；然后，将求解该问题看作是一个D2D配对过程，并提出基于稳定匹配的低复杂度的多用户计算卸载资源优化决策算法；最后，迭代求解D2D卸载的优化分配决策。通过理论证明分析了所提算法的稳定性、最优性和复杂度等特性。仿真结果表明，所提算法相较于随机匹配算法能够有效降低10%～33%的系统计算总开销，并且其性能非常接近最优的穷举搜索算法。可见，所提基于D2D卸载的决策有利于改善时延和能耗开销性能。

移动边缘计算；终端直通通信；计算卸载；资源分配；稳定匹配

0 引言

随着第五代移动通信（Fifth Generation， 5G）的发展和商用，越来越多的移动应用，如物联网、增强现实、视频流处理等，不仅需要高速数据传输并且要求强大计算资源的时延敏感的新应用正在迅速被普及［1］。为了能够支持这些对计算资源和时延有特殊需求的应用，移动边缘计算（Mobile Edge Computing， MEC）应运而生。MEC是一种相当有潜力的新兴5G服务方案，主要利用用户邻近的无线网络边缘设施或者大量的用户端设备协作，代替远端云计算来执行大量的通信和计算服务［2］。与云计算相比，MEC能够在网络边缘，即无线接入网端提供与云计算相当的能力，从而使用户能够以较近的距离卸载其计算任务，实现低时延且灵活的计算和通信扩展服务［1-2］。

针对用户计算任务的卸载问题，大多数研究都集中于基于边缘服务器的MEC网络资源管理，即在考虑无线通信和移动计算准则下，用户可将计算任务卸载至网络边缘高速的计算服务器［3］。该方式下的计算卸载模型可划分为二元卸载和部分卸载两大类。在二元卸载方案中，用户的计算任务要么全部在本地执行要么全部卸载到边缘服务器执行。Wang等［4］利用图着色算法设计了一种联合二元计算卸载和通信资源分配的卸载决策。而在部分卸载方案中，用户的计算任务可分割开来，一部分留在本地执行，一部分卸载到边缘服务器执行。Ren等［5］建立了部分卸载模型分段的最优化问题，并基于最优数据分割策略中分段的结构提出了联合通信和计算资源分配的最优化算法。MEC网络中仅利用边缘服务器的计算卸载，不管是采用哪种卸载模型，虽然能够使移动网络的计算性能在一定程度上得到提升，但基站（Base Station， BS）端边缘服务器有限的计算资源并不能保持一直足以支持其覆盖范围内的所有移动设备；而且由于用户在网络中分布的随机性，尤其是对于分布在小区边缘的用户而言，基站端的边缘服务器与用户之间的距离可能会较远，从而导致较长的卸载时延［6］。为了弥补MEC网络中的这些不足，将允许终端之间无需经过基站而直接进行通信的终端直通（Device-to-Device， D2D）融入MEC网络，利用D2D通信辅助用户计算任务卸载是一个值得关注的解决方案。

D2D通信利用蜂窝资源能够支持网络中用户间直接的数据传输［7］，基于此网络的大量移动设备在网络中心的辅助控制下不仅可实现数据转发和共享，还能够实现资源共享和计算卸载。网络中大量不同种类的设备，如物联网设备、智能手机、平板电脑等，它们多样化的计算能力以及复用增益可以被用来支持多种服务的协作计算任务执行［8］。事实上，通过用户间协作进行计算卸载时，卸载距离的明显减少是通常被忽视的一个关键。从无线通信角度考虑，发送距离短就能以较低的功率消耗获得较高的数据传输速率，从而当用户间短距离进行任务卸载时能够减少卸载时延和能量消耗［6］。考虑到D2D卸载的优势，研究者们逐渐对基于D2D通信辅助的卸载决策展开了研究。Hu等［9］在考虑D2D卸载方式的情况下，设计了一种基于序贯决策博弈的多用户计算卸载方法。Xing等［10］利用D2D将邻近用户当作协作计算的帮助者，通过联合最优化任务卸载、任务执行和结果下载时间来最小化计算卸载时延。Feng等［11］在考虑计算资源均衡的基础上，以最小化移动设备任务卸载开销为目标，提出利用凸函数差分的迭代算法来解决计算卸载和资源分配的优化问题。上述研究以及大多数D2D辅助的计算卸载决策，其算法的计算复杂度都非常高，并且优化目标以最小化时延为单一目标居多，但D2D设备的能耗也是需要考虑的重点，还有一些研究仅仅利用了D2D卸载的概念，设备间通信仍然采用蜂窝通信。考虑到以上问题，本文利用匹配理论设计了一种低复杂度的D2D通信辅助的多用户计算卸载资源优化决策。

本文将D2D通信与D2D卸载融入MEC网络形成D2D-MEC网络架构，在最小化系统计算总开销的基础上进一步降低用户的卸载时延和能耗。考虑多用户计算任务卸载场景，这些用户各自有一个独立的计算任务需要被执行，但由于其自身大量的中央处理器（Central Processing Unit， CPU）资源被计算任务的一部分或者其他应用所占用，需要卸载全部或已分割的部分计算任务到邻近的拥有闲置CPU资源的设备处执行。通过对计算任务在D2D传输和执行阶段的时延和能耗开销建模，以最小化包括时延和能耗的系统计算总开销为优化目标，将多用户计算任务卸载和多用户计算资源分配问题，建模为最小化系统计算总开销的整数规划问题。针对该问题，本文将多个用户的计算任务卸载和多个用户的计算资源分配看作是他们之间的相互匹配，利用稳定匹配给出了基于D2D通信的多用户计算卸载资源优化决策，以较低的复杂度实现了系统计算总开销最小化，提升用户体验。

1 系统模型

1.1 网络模型

本文考虑一个由宏蜂窝基站（BS）和多个移动用户（User Equipment， UE）组成的D2D-MEC系统，如图1所示。每个移动用户不仅能够与基站建立蜂窝通信链路，也能够与其他邻近的移动用户以D2D通信的方式建立D2D链路。基站配备了一个MEC服务器为较大的计算任务卸载提供相应的计算卸载服务，而某些移动用户较小的计算任务或者已分割的部分计算任务则可直接以D2D卸载的方式由邻近的移动用户提供计算卸载服务。为了降低计算卸载时延和能耗，避免因MEC服务器计算资源紧缺导致计算卸载拥堵，将邻近用户闲置的计算资源利用起来，可采用向邻近移动用户请求D2D卸载的方式执行计算任务卸载。事实上，可将提供闲置计算资源的D2D用户设备看作临时的多个分布式小型移动MEC站，以近距离的方式为用户提供卸载服务。当然这些D2D用户设备除了能够提供计算卸载服务以外，还能够提供传统的D2D协作通信及数据内容转发和共享等服务，只是针对本文所考虑的问题，文中仅分析了D2D用户设备的计算卸载能力。假设系统中有个需要请求D2D计算卸载的移动用户，用集合表示。这个移动用户均有一个独立的并且时延较为敏感的计算任务需要向邻近移动用户请求计算卸载服务。相应地，系统中有个相邻的有闲置计算资源能够提供D2D计算卸载服务的移动用户，用集合表示。为了避免复杂的信令交互并考虑到任务量较小，本文设定用户的计算任务只能卸载到一个相邻的用户，提供计算服务的用户也只会将其计算资源分配给一个请求卸载的用户为其提供服务。虽然此设定在请求用户多于服务用户时可能会使少数请求用户不能被立即分配服务用户，但相较于一对多、多对一或多对多D2D卸载而言，此设定下请求用户的任务不需要执行复杂的算法再进行分割，系统处理复杂度较低，并且还能避免多个任务在一个服务用户处排队等候使服务用户过载而造成卸载时延和能耗增加的情况。不失一般性，参考大多数移动边缘计算［12］和移动网络［13］的研究场景，为了分析的可行性并取得实用的结果，本文也采用半静态的计算卸载场景，即在通常的一个计算卸载时间周期（百毫秒级）内，移动用户集合和保持不变，而在两个或多个周期内可能会有所变化。

图1 D2D-MEC系统模型Fig. 1 D2D-MEC system model

以上假设是合理的，因为有些用户自身可能不具备计算能力或者只具备较弱的计算能力，而计算任务通常又是时延敏感的，所以这些用户自身不能按时完成全部任务时，就会发起全部或者部分任务的计算卸载请求，而请求卸载的计算任务量可能是较小的。邻近的用户他们可能拥有较强的计算能力，在有多余闲置计算资源的情况下，以D2D方式帮助相邻的用户完成较小的计算任务量卸载是能够实现的。因为即使会消耗一些用户的计算和能量等资源，但可通过一些互惠或补偿手段使这些用户愿意分享自身的资源提供服务，例如：请求卸载的用户可向为他服务的用户分享他较强的存储资源或者以D2D方式分享他拥有的各种社会内容资源等。

1.2 通信模型

用户间的D2D卸载需利用D2D链路传输计算任务和计算结果，D2D通信在蜂窝网控制下采用正交频分多址接入方式接入无线信道［8］。因为信道状态估计等内容不是本文的研究重点，所以假设通过信令反馈，基站能够获取信道状态信息以及所有设备需要卸载的计算任务大小。基于自由空间传播路径损耗和瑞利衰落，请求计算卸载的用户和提供计算卸载服务的用户之间D2D链路的接收功率可表示为：

进一步地，用户i和用户j之间D2D链路可实现的数据速率表示为：

其中：W表示带宽；表示信道的加性高斯白噪声。

1.3 计算模型

1.3.1 任务传输阶段计算开销模型

1）时间开销模型。

用户i将计算任务的输入数据通过D2D通信传输到用户j，基于1.2节通信模型中用户i和用户j之间D2D链路可实现的数据速率，传输输入数据所消耗的传输时间可由式（3）计算：

2）能量开销模型。

除传输时间开销以外，由于用户通常是能量受限的，为了尽可能延长工作时间提升用户体验，用户所消耗的能量也需要被考虑。用户i以功率将输入数据通过D2D通信传输到用户j所消耗的能量取决于数据传输的时间，所以传输输入数据所消耗的传输能量可由式（4）计算：

综合式（3）～（4），任务传输阶段，用户i计算任务包括时间开销和能量开销的计算总开销为：

1.3.2 任务执行阶段计算开销模型

1）时间开销。

当用户i的计算任务成功传输到用户j后，用户j就会代替用户i执行相关的计算任务，不同用户拥有的计算能力可能是不同的，设用户j的计算能力，也即是CPU计算频率为，那么用户j计算接收到的计算任务所消耗的计算时间可由式（6）计算：

2）能量开销。

用户j计算接收到的计算任务会消耗自身能量，设是用户j执行计算任务时所需消耗的功率，其中是有效开关电容，根据文献［15］的实测结果，可设置为，是一个正常数［16］。那么用户j计算接收到的计算任务所消耗的计算能量可由式（7）计算：

综合式（6）～（7），任务执行阶段，用户i计算任务包括时间开销和能量开销的计算总开销为：

1.4 问题建模

本文考虑用户间以D2D方式进行计算任务卸载，为了使整个任务卸载过程中时延最小化的同时用户的能耗也最小，提升用户体验，以最小化整个系统中所有用户任务卸载过程中的计算总开销，即包含任务传输和任务执行阶段总的时间开销和能量开销为目标函数，建立以下线性的全局优化问题：

2 基于稳定匹配的计算卸载资源优化决策

2.1 匹配基础

定义2不存在阻塞对的匹配是稳定匹配。

本文中参与匹配的两个有限不相交的集合分别是卸载请求的用户集合和卸载服务的用户集合。在匹配过程中，请求用户和服务用户都需要依据效用函数建立对另一边集合的偏好序列。为匹配最佳的服务用户，中的请求用户会向其偏好序列中最高偏好的服务用户发起匹配请求，因服务用户对所有请求用户有它自己的一个偏好，所以接收到请求的服务用户会依据自己的偏好序列选择接收或拒绝该请求用户的请求。以此循环迭代进行匹配，在最终匹配结束时，请求用户和服务用户不可能同时存在比现在偏好更佳的其他对象，即不存在未匹配的请求用户和服务用户相较于当前的匹配对象，它们更愿意去打破当前的匹配使对方成为自己的匹配对象。

2.2 偏好序列的建立

要进行双边匹配，首先应根据用户的不同偏好建立双边用户的偏好序列，合理的排序规则是建立偏好序列的基础。当请求用户与不同服务用户进行配对时，由于他与不同服务用户之间通信距离不同且不同服务用户的计算能力也不同，那么不同配对会得到不同的计算总开销。同理，当服务用户与不同请求用户进行配对时，不同配对也会得到不同的计算总开销。本文的优化目标是最小化系统计算总开销，因此请求用户对服务用户的偏好，以及服务用户对请求用户的偏好，都以式（5）和式（8）之和的计算总开销为效用函数来衡量，也即是请求用户和服务用户以计算总开销的大小为排序依据来建立偏好序列：总开销越小，用户的偏好就越高，排序就越靠前。

2.3 多用户D2D计算卸载资源优化决策算法

当偏好序列建立完成以后，请求用户就会根据偏好序列向排在第一位的最高偏好的服务用户发起匹配请求，相对应的服务用户会根据自己的偏好序列作出选择。参考文献［18］中的稳定结婚问题，本文给出了基于稳定匹配的多用户D2D计算卸载资源优化决策，如算法1所示。

算法1 基于稳定匹配的多用户D2D计算卸载资源优化决策算法。

1）初始化：设置相关参数，建立所有未匹配的请求用户的列表集合，定义为

4） end for

7） end for

15） else

18） end if

19） else

20） 跳转至第9）步

21） end if

22） end for

23） end while

算法1的具体步骤如下：

a）初始化系统和用户各参数，建立所有未匹配的请求计算卸载的用户集合列表。

d）收到任务卸载请求的服务用户根据其偏好序列将发起请求的请求用户与当前匹配对象进行比较，如果服务用户更偏好发起请求的请求用户，则接受发起请求的请求用户拒绝当前匹配对象，该发起请求的请求用户从未匹配列表中移除，而被拒绝的匹配对象则会被加入未匹配列表中；反之如果服务用户更偏好当前匹配对象，则会维持当前匹配，拒绝发起请求的请求用户，而被拒绝的发起请求的请求用户会从自己的偏好序列中移除该服务用户，更新其偏好序列，如步骤12）～18）所示。

e）算法迭代进行，未被匹配的请求用户又会继续向当前偏好序列中最高偏好的服务用户提出新的任务卸载/匹配请求，直到与服务用户匹配成功或者其偏好序列中再无可发起请求的服务用户，如步骤8）～23）所示。

2.4 算法分析

下面对本文稳定匹配算法的稳定性、最优性和复杂度等特性进行详细分析。对于算法的收敛性，从算法1可知，当每一个请求用户已经成功匹配了合适的服务用户，或者已经被所有服务用户拒绝时，本文算法经过有限次迭代最终都会收敛形成稳定匹配。

2.4.1 匹配算法的稳定性

定理1匹配算法经过有限次迭代收敛时，得到的匹配是稳定的。

证明 根据定义2可知，没有阻塞对的匹配是稳定匹配。在匹配过程中，请求用户和服务用户均根据式（5）和式（8）之和计算偏好值，由于通信距离、任务大小和计算能力的不同，，；，，因此在建立偏好序列的过程中不存在阻塞个体，不同用户将偏好值按照从小到大排序所建立的偏好序列是完全序。假设在匹配中存在请求用户和服务用户，他们相互没有匹配但期望与对方匹配，表示为：。根据匹配原则，从算法1步骤11）可知，请求用户i曾经向服务用户j提出过匹配请求，但最终表明在算法结束时服务用户j拒绝了请求用户i当时的请求。并且从算法步骤12）～18）可知，服务用户j选择了另一个他更偏好的请求用户i，即，满足。上述分析表明匹配中不存在阻塞对，与假设矛盾，所以算法1的匹配算法结果是稳定的。

2.4.2 匹配算法的最优性

定义3一个多目标函数的效用如果能在某种设定发生变化时得到提升，并且参与者也都同意这种变化，就是帕累托改进。如果在博弈匹配的过程中没有帕累托改进，那么当前的匹配结果就是弱帕累托最优［17］。

定理2所得匹配对于多用户D2D计算卸载资源优化是弱帕累托最优的。

证明在本文匹配算法中，下一个选择能够得到更好的效用时个体偏好序列的指针才会移动，但不论是什么匹配结果，个体都不能为了获取更好的效用而往回移动。假设存在匹配的帕累托改进：请求用户i与服务用户j匹配可以提高目标效用，即。如果在匹配中服务用户j未匹配，那么，也即是请求用户i与服务用户j愿意互相匹配形成阻塞对，但这与定理1证明的匹配是稳定的相矛盾。如果在匹配中服务用户j已经匹配了请求用户i，i使得服务用户j不能和i匹配。根据匹配原则可知，这表明i和i相比，i会让j得到的效用更差，那么j不会选择i进行匹配，则无法实现。综合以上分析可知，匹配没有帕累托改进，匹配是弱帕累托最优。

2.4.3 匹配算法的复杂度

建立偏好序列时，双边集合中的每一个用户都要计算另一边集合中每个用户的偏好值（计算总开销），因此建立偏好序列的计算复杂度为。升序排列偏好值得到偏好序列的计算复杂度为。进行匹配的过程中，每个请求用户最多向个服务用户发起匹配请求，那么个请求用户最多发起次请求，计算复杂度为。如果采用穷举（枚举）搜索法求解建立的优化问题，则需要枚举所有可能的配对，因此会出现的匹配结果总数（枚举次数）为dt！×dt！，计算复杂度为（dt！×dt！）；如果采用隐枚举法这种特殊的分支定界法求解建立的优化问题，相较于穷举搜索法，该方法通过分支定界能够减少枚举的次数，计算复杂度为；如果采用随机匹配法求解建立的优化问题，算法复杂度随服务用户数的增加线性增加，计算复杂度为。通过对以上不同方法的复杂度进行分析对比可知，本文稳定匹配算法的计算复杂度虽然略高于随机匹配法，但相较于穷举搜索法和隐枚举法明显更低，并且当参与个体越多时该优势越明显。

3 仿真结果与性能分析

通过仿真对基于稳定匹配的多用户D2D计算卸载资源优化决策算法的性能进行分析验证。考虑一个半径为100 m的区域，个具有独立计算任务的请求用户和个具有闲置计算资源的服务用户均匀分布在圆内。采用正交的信道资源，根据匹配的决策结果，一个请求用户的任务可以D2D通信的方式卸载到相应服务用户处执行。具体设置的关键仿真参数如表1［4，8，10］所示。

表1 仿真参数Tab. 1 Simulation parameters

本文以最小化系统计算总开销为优化目标来制定多用户D2D计算卸载资源优化决策，因此通过仿真不同情况下的系统计算总开销性能对本文算法进行分析。为了更加便于评估本文算法的有效性，选择以下两种算法分别作为上界和下界基准与本文算法进行比较：1）最优的穷举搜索算法，即通过枚举搜索所有可能的配对来选择最佳的进行匹配；2）随机匹配算法，顾名思义即随机选择两个用户进行匹配。另外还将本文算法与把所有任务都卸载到远端MEC服务器执行的MEC卸载决策进行了比较。考虑到仿真的随机性，所有仿真结果都是基于至少1 000次不同位置分布、不同任务大小和不同计算能力等条件的蒙特卡罗（Monte Carlo）随机实验平均值。

图2给出了通过本文算法得到的计算总开销随请求卸载用户数和服务用户数变化的情况。由图2明显可知，系统计算总开销随着请求卸载用户数（即任务数）和服务用户数的增加而增加。当请求卸载用户数一定即任务数一定时，增加服务用户数能够使相应数量的请求用户的任务得到执行，系统计算总开销增加。特别地，当服务用户数超过请求卸载用户数时，系统计算总开销逐渐降低。这是因为当有更多的服务用户出现时，意味着有更多的计算资源能够提供给请求用户进行选择，通过本文稳定匹配算法，可使双方选择到更好的匹配对象。当服务用户数一定时，同理分析可得。

图2 请求卸载和服务用户数对计算总开销的影响Fig. 2 Impact of number of request offloading user and number of service users on total computing overhead

对比了本文算法与两种基准算法的计算总开销随请求卸载和服务用户数的变化情况，如图3所示。

图3 三种算法的计算总开销对比Fig. 3 Comparison of total cost of three algorithms

从图3（a）、3（b）中均可以看出，本文基于稳定匹配的算法所得计算总开销非常接近最优的穷举搜索算法，并且远低于随机匹配算法。穷举搜索虽然能获得最优的性能，但其计算复杂度非常高，而本文算法能以较低的复杂度获得与之相近的性能。特别地，图3（a）中设置网络中存在4个服务用户（= 4），而请求卸载用户数是变化的；图3（b）中设置网络中存在4个请求卸载用户（），而服务用户数是变化的。很明显初始阶段不同算法随着用户数的增加计算总开销均会增加；当用户数超过4时，本文算法与穷举搜索算法的计算总开销均有所减小，这与图2所示结果一致，原因就不再赘述。而随机匹配算法由于随机选择匹配对象，所以即使有更多的可供选择的用户出现，其计算总开销也不会在超过4用户数时有所减小而是趋于平稳。

图4（a）、4（b）、4（c）分别给出了三种算法的计算总开销随卸载任务数据量、任务所需CPU周期数和服务用户CPU计算频率（计算能力）变化的情况。

图4 不同条件下三种算法的计算总开销Fig. 4 Total cost of three algorithms under different conditions

其中，网络设置有3个请求任务卸载的用户和4个服务用户，图4（a）中请求用户拥有相同的任务数据量，图4（b）中请求用户拥有相同的任务所需CPU周期数，图4（c）中服务用户拥有相同的CPU计算频率。可以看出，本文算法仍明显优于随机匹配算法，特别是任务量和计算能力不断增加时差距更大，且仍非常接近穷举搜索算法。另外明显可以看出，任务数据量或所需CPU周期数的增加，会使任务传输或执行阶段的时延和能耗增加，所以计算总开销随之增加；但服务用户CPU计算频率的增加能够缩短计算时延并减小计算能耗，因此计算总开销随之减小。

图5比较了D2D卸载和MEC卸载两种决策的各种开销随请求卸载用户数的变化情况。设置网络中请求卸载用户数与服务用户数相等，其中D2D卸载是指采用本文所述场景和卸载算法；MEC卸载是指将所有请求用户的任务都卸载到相距200 m～700 m较远的MEC服务器处执行，MEC服务器CPU计算频率为5 GHz。因为MEC服务器通常具备交流供电条件，所以MEC卸载决策执行计算任务时的能耗开销没有考虑，其他开销与D2D卸载同理计算可得。特别需要说明的是，在计算这两种决策的时延开销时，都是将每个用户的时延开销累加起来，没有考虑任务被同时处理的情况。

图5 不同卸载决策的开销Fig. 5 Costs of different offloading policies

从图5（a）中可以看出，D2D卸载决策的总开销、总时延开销和总能耗开销均低于MEC卸载决策，特别是随着请求卸载用户数的增加，这种差距也随之增大。从图5（b）中可以看出，无论哪种决策，任务传输阶段的总开销均大于任务执行阶段的总开销。此外，通过对比可以看出，由于MEC距离用户较远，所以任务传输阶段所消耗的时延和能耗均远远大于D2D卸载决策。而任务执行阶段，由于MEC的计算能力比单个服务用户高并且MEC决策未考虑能耗，所以任务执行阶段用户累加起来的时延小于D2D卸载决策总的时延和能耗开销。通过对比图5可知，虽然MEC卸载决策任务执行阶段的总开销性能优于D2D卸载决策，但其任务执行阶段的优势也并不能弥补任务传输阶段与D2D卸载决策之间产生的差距，所以出现了图5（a）中的D2D卸载决策在总开销、总时延开销和总能耗开销性能上均更优的结果。这也验证了D2D短距离通信的优势有利于减小用户计算任务卸载时延和能耗，特别是当同时有较多用户需要计算卸载服务时，可以在一定程度上减轻MEC拥堵，有效降低时延和能耗，提升用户体验。

4 结语

本文考虑D2D通信低时延、低能耗的优势，提出了一种基于D2D通信的多用户计算卸载资源优化决策算法。首先，通过任务传输和执行阶段建立的时延和能耗模型，将多个用户的计算卸载和多个用户的计算资源分配建模为最小化包括时延和能耗的计算总开销的最优化问题；然后，基于稳定匹配理论采用低复杂度的决策算法求解D2D卸载的优化分配。理论分析验证了本文算法的稳定性、最优性和复杂度等特性。仿真结果表明，本文算法在不同情况下的计算总开销都远小于随机匹配算法，有效降低了10%～33%，性能非常接近最优的穷举搜索算法，而且无论是总开销还是总时延和总能耗开销性能，均优于MEC卸载决策，用户间D2D卸载能够实现低时延、低能耗的体验。本文研究D2D卸载是基于提供计算资源的用户会得到相应补偿的设定，其实在实际应用场景中，用户在社会网络中所表现出的某些特性，如社会关系、偏好特性等，应该是需要被考虑的重点之一。未来将探究社会网络中用户的相关特性对D2D卸载的影响，设计考虑更加全面、性能更优的D2D卸载决策，提升用户体验。

[1] MAO Y Y， YOU C S， ZHANG J， et al. A survey on mobile edge computing： the communication perspective ［J］. IEEE Communications on Surveys and Tutorials， 2017， 19（4）： 2322-2358.

[2] HU Y C， PATEL M， SABELLA D， et al. Mobile edge computing： a key technology towards 5G： ETSI White Paper No. 11 ［R］. Sophia Antipolis： European Telecommunications Standards Institute， 2015： 1-15.

[3] YOU C S， HUANG K B， CHAE H， et al. Energy-efficient resource allocation for mobile-edge computation offloading ［J］. IEEE Transactions on Wireless Communications， 2017， 16（3）： 1397-1411.

[4] WANG C M， YU F R， LIANG C C， et al. Joint computation offloading and interference management in wireless cellular networks with mobile edge computing ［J］. IEEE Transactions on Vehicular Technology， 2017， 66（8）： 7432-7445.

[5] REN J K， YU G D， CAI Y L， et al. Latency optimization for resource allocation in mobile-edge computation offloading ［J］. IEEE Transactions on Wireless Communications， 2018， 17（8）： 5506-5519.

[6] KAI Y， WANG J Y， ZHU H L. Energy minimization for D2D-assisted mobile edge computing networks ［C］// Proceedings of the 2019 IEEE International Conference on Communications. Piscataway： IEEE， 2019： 1-6.

[7] MACH P， BECVAR Z， VANEK T. In-band device-to-device communication in OFDMA cellular networks： a survey and challenges ［J］. IEEE Communications Surveys and Tutorials， 2015， 17（4）： 1885-1922.

[8] HE Y H， REN J K， YU G D， et al. D2D communications meet mobile edge computing for enhanced computation capacity in cellular networks ［J］. IEEE Transactions on Wireless Communications， 2019， 18（3）： 1750-1763.

[9] HU G S， JIA Y J， CHEN Z C. Multi-user computation offloading with D2D for mobile edge computing ［C］// Proceedings of the 2018 IEEE Global Communications Conference. Piscataway： IEEE， 2018： 1-6.

[10] XING H， LIU L， XU J， et al. Joint task assignment and resource allocation for D2D-enabled mobile-edge computing ［J］. IEEE Transactions on Communications， 2019， 67（6）： 4193-4207.

[11] FENG J， ZHAO L Q， DU J B， et al. Computation offloading and resource allocation in D2D-enabled mobile edge computing ［C］// Proceedings of the 2018 IEEE International Conference on Communications. Piscataway：IEEE， 2018： 1-6.

[12] KO S W， HAN K F， HUANG K B. Wireless networks for mobile edge computing： spatial modeling and latency analysis ［J］. IEEE Transactions on Wireless Communications， 2018， 17（8）： 5225-5240.

[13] 张文柱，曹琲琲，余静华.移动边缘计算中一种多用户计算卸载方法［J］.西安电子科技大学学报，2020，47（6）：131-138.（ZHANG W Z， CAO B B，YU J H. Multi-user computation offloading approach for mobile edge computing ［J］. Journal of Xidian University， 2020， 47（6）： 131-138.）

[14] CHEN X. Decentralized computation offloading game for mobile cloud computing ［J］. IEEE Transactions on Parallel and Distributed Systems， 2015， 26（4）： 974-983.

[15] WEN Y G， ZHANG W W， LUO H Y. Energy-optimal mobile application execution： taming resource-poor mobile devices with cloud clones ［C］// Proceedings of the 2012 IEEE International Conference on Computer Communications. Piscataway： IEEE， 2012：2716-2720.

[16] TANG J H， TAY W P， WEN Y G. Dynamic request redirection and elastic service scaling in cloud-centric media networks ［J］. IEEE Transactions on Multimedia， 2014， 16（5）： 1434-1445.

[17] XU C， GAO C X， ZHOU Z Y， et al. Social network-based content delivery in device-to-device underlay cellular networks using matching theory ［J］. IEEE Access， 2017， 5： 924-937.

[18] GALE D， SHAPLEY L S. College admissions and the stability of marriage ［J］. The American Mathematical Monthly， 1962， 69（1）： 9-15.

Multi-user computation offloading and resource optimization policy based on device-to-device communication

LI Yu1，2*， HE Xiping1，2， TANG Lianggui1，2

（1.School of Computer Science and Information Engineering，Chongqing Technology and Business University，Chongqing400067，China；2.Chongqing Engineering Laboratory for Detection，Control and Integrated System（Chongqing Technology and Business University），Chongqing400067，China）

With the significant increase of computation-intensive and latency-intensive applications， Mobile-Edge Computing （MEC） was proposed to provide computing services for users at the network edge. In view of the limited computing resources of edge servers at the Base Stations （BSs） and the long latency of long-distance computation offloading of users at the network edge， a multi-user computation offloading and resource optimization policy based on Device-to-Device （D2D） communication was proposed. The D2D was integrated into MEC network to directly offload tasks to neighbor users for executing in D2D mode， which was able to further reduce offloading latency and energy consumption. Firstly， the joint optimization problem of multi-user computation offloading and multi-user computing resource allocation was modelled with the optimization objective of minimizing the total system computing cost including latency and energy consumption. Then， the solution of this problem was considered as a D2D pairing process， and the multi-user computation offloading and resource optimization policy algorithm was proposed based on stable matching. Finally， the optimization allocation policy of D2D offloading was solved iteratively. The characteristics such as stability， optimality and complexity of the proposed algorithm were analyzed by theoretical proof. Simulation results show that， the proposed algorithm can effectively reduce the total system computing cost by 10%-30% compared with the random matching algorithm，and the performance of the proposed algorithm is very close to the optimal exhaustive search algorithm， indicating that the proposed policy based on D2D offloading is helpful to improve latency and energy consumption performance.

Mobile Edge Computing (MEC); Device-to-Device (D2D) communication; computation offloading; resource allocation; stable matching

TP389.1

A

1001-9081（2022）05-1538-09

10.11772/j.issn.1001-9081.2021030458

2021⁃03⁃25；

2021⁃06⁃30；

2021⁃07⁃01。

国家自然科学基金资助项目（61901067）；重庆市自然科学基金资助项目（cstc2020jcyj⁃msxmX0339）；重庆市教育委员会科学技术研究项目（KJQN201900824）；重庆工商大学科研项目（1952002，1956011）。

李余（1989—），女，重庆人，副教授，博士，主要研究方向：终端直通通信、移动边缘计算、资源优化； 何希平（1968—），男，四川射洪人，教授，博士，主要研究方向：机器学习、数据分析处理、计算机视觉； 唐亮贵（1973—），男，重庆人，副教授，博士，CCF会员，主要研究方向：分布式智能计算、网络计算。

This work is partially supported by National Natural Science Foundation of China （61901067），Natural Science Foundation of Chongqing （cstc2020jcyj-msxmX0339）， Science and Technology Research Program of Chongqing Municipal Education Commission （KJQN201900824）， Science Research Program of Chongqing Technology and Business University （1952002， 1956011）.

LI Yu， born in 1989， Ph. D.， associate professor. Her research interests include device-to-device communication， mobile edge computing， resource optimization.

HE Xiping， born in 1968， Ph. D.， professor. His research interests include machine learning， data analysis and processing， computer vision.

TANG Lianggui， born in 1973， Ph. D.， associate professor. His research interests include distributed intelligent computing， network computing.