We use cookies to improve your experience with our site.

移动边缘计算中基于分布式博弈论的设备到设备环境下的任务卸载

Distributed Game-Theoretical D2D-Enabled Task Offloading in Mobile Edge Computing

  • 摘要: 1、研究背景
    随着5G和其他网络技术的快速发展,人脸识别、自然语言处理和互动游戏等终端设备已经涉及到计算密集型和延迟关键型应用。由于硬件限制,移动设备的电池寿命和计算资源通常是有限的。移动边缘计算被认为是一种有前途的分布式计算范式,它利用边缘节点的计算能力来降低计算成本和提高服务质量。在移动边缘计算中,由于边缘节点的计算能力和无线信道以及云的计算能力由卸载用户共享,移动用户需要决定是将任务卸载到边缘节点、云,还是利用设备到设备(D2D)技术或其本地设备来处理任务,这提出了基本的任务卸载问题。最近,一些工作只考虑无线信道竞争的影响,而不考虑边缘节点之间的卸载,这可能会改变卸载决策。此外,大多数提出的任务卸载策略是集中的,中心节点需要收集所有用户信息,并通过计算控制全局任务卸载策略,这不仅使得中心节点计算复杂度大,还会导致用户隐私泄露。从移动用户的角度来看,当他们找到更好的方法来卸载任务时,集中式策略可能无法满足所有用户的需求。例如,用户可能不愿意改变最初的卸载决策,尤其是当改变后的决策比先前的决策花费更多时。如今,许多卸载策略没有利用边缘节点的潜在计算资源,如D2D技术,从而将用户的任务卸载到没有任务要卸载的空闲移动设备上,这将有效地降低了用户的总成本。
    2、目的
    我们目标是寻求高效的方法来解决多用户任务卸载问题,同时考虑边缘节点之间的卸载,无线信道中的竞争,D2D技术实现的边缘节点的潜在计算资源,本地计算与云计算,且需满足用户对延迟的要求。满足更加真实,复杂的移动边缘计算中的任务卸载的场景,帮助实现所有用户快速的决策任务卸载方式且有效的降低总的时间与能量的消耗。
    3、方法
    我们首先证明了集中式优化问题是NP难问题,然后将任务卸载问题描述为一个多用户势博弈,该博弈总是具有纳什均衡性质并且在有限的步骤内达到纳什均衡,并找到势函数。然后,我们提出了一个分布式D2D任务卸载算法来帮助用户选择能够达到纳什均衡和满足用户可接受延迟的卸载方法。根据一些策略不覆盖重叠信道和边缘节点的用户可以在同一决策时隙中同时更新卸载策略,又提出并行用户选择算法(PUS)加快该过程的收敛达到纳什均衡。我们利用代价函数的两个参数来表示延迟和能量的权重,并满足各自的条件。基于三个真实数据集,分别考虑有/无D2D链路和云计算两种模型,对提出的算法进行比较性的研究。
    4、结果
    基于真实数据实验,对于收敛性,随机20名用户在有/无D2D链路和云计算两种模型中,其策略在算法10-15次循之后不再发生改变。
    在实验中发现,利用PUS算法选择可更新策略用户时,相对于随机选择一位用户,以及选择使得势函数最大的用户允许更新的方式,总能以最快的速度使势博弈达到纳什均衡。例如:当使用第一组数据探究30名用户算法收敛执行次数时,利用PUS的MUUO算法平均执行17.82602次,而BUAU平均30.42878次,DGTO平均35.02738次,BRUO平均50.26601次,其他因素探究中迭代次数均保持这样的趋势MUUO 在探究总消耗的影响时,发现MUUO仍能接近最优算法COTO的结果,例如:当用户数量为60,COTO的总消耗为594.744,而BUAU的总消耗为662.901,MUUO的总消耗为713.955,DGTO总消耗743.666,BRUO的总消耗为786.203,RTO的总消耗为807.312,其他情况具有同样的趋势。在探究带宽的影响时,当带宽从1到10MHZ时,在存在D2D链路和云计算时,BRUO算法的总消耗从780.2367下降到136.2661,在不存在D2D链路和云计算时,总消耗从807.425下降到403.201。所以带宽的增加可以降低总消耗。当D2D链路数量从相对用户数从10%增加到100%时,卸载到空闲设备的占比从0.25到0.45.
    5、结论
    采用提出的算法达到纳什均衡时的循环次数最低,循环次数排序为MUUOCOTO。且总消耗随着带宽的增加与D2D链路的增加而下降,随着每单位数据的所需CPU周期增加而增大。结果发现提出的PUS算法不仅能最快的使任务卸载达到纳什均衡,且能使其得到总消耗接近最优的算法结果。
    我们发现D2D链路的增多使得系统的总消耗降低,所以未来发现边缘节点的隐藏设备并使其加入任务卸载中是降低总消耗的一个有效的方法。且在本研究中,由于用户是自私的,可以在任务卸载中考虑出一种激励机制,让用户既能将任务卸载到其他空闲设备,也能将本身的空闲设备供其他用户卸载任务,这也将降低系统的总消耗。

     

    Abstract: Mobile Edge Computing (MEC) has been envisioned as a promising distributed computing paradigm where mobile users offload their tasks to edge nodes to decrease the cost of energy and computation. However, most of the existing studies only consider the congestion of wireless channels as a crucial factor affecting the strategy-making process, while ignoring the impact of offloading among edge nodes. In addition, centralized task offloading strategies result in enormous computation complexity in center nodes. Along this line, we take both the congestion of wireless channels and the offloading among multiple edge nodes into consideration to enrich users' offloading strategies and propose the Parallel User Selection Algorithm (PUS) and Single User Selection Algorithm (SUS) to substantially accelerate the convergence. More practically, we extend the users' offloading strategies to take into account idle devices and cloud services, which considers the potential computing resources at the edge. Furthermore, we construct a potential game in which each user selfishly seeks an optimal strategy to minimize its cost of latency and energy based on acceptable latency, and find the potential function to prove the existence of Nash equilibrium (NE). Additionally, we update PUS to accelerate its convergence and illustrate its performance through the experimental results of three real datasets, and the updated PUS effectively decreases the total cost and reaches Nash equilibrium.

     

/

返回文章
返回