Joint Computation and Communication Cooperation for Energy-Efficient Mobile Edge Computing 论文笔记

本文研究了移动边缘计算(MEC)中计算卸载(computation offloading)的优化问题。在边缘网络中如何分配用户的计算任务可以使整体耗电量最小?本文针对 User - Helper - AP 三点式模型求解这个问题的最优解。通过构建一个线性规划问题和一个非线性规划问题来分别解可分割任务和不可分割任务的最优耗电量,并使用拉格朗日乘子法和 KKT 条件等方法求出结果,以达到节约设备用电的目的。这篇文章没有什么特别的亮点,仅仅是 LP 问题的一个应用。

1 Introduction

介绍 User - Helper - AP 三点式 MEC 模型。

2 System Model

构建所提出的模型。

待计算任务的长度为L,分别分配给三点设备。User 自己计算叫本地计算,让 Helper 帮忙叫计算协作,让 AP 帮忙叫通信协作。

2.A 时间槽

该模型共有4段时间槽,对应模型4个阶段。

2.B 计算卸载的传输能耗

计算卸载就是将 User 自己的任务卸载给别人帮忙计算。

利用香农定理,得到了信道传输最大速率,该速率乘以对应时间槽时长就是总传输数据量。由各阶段传输功率和时长,得到传输过程的能耗。

User 传 AP 的过程由 Helper 辅助传输,叫做 DF relay。根据参考文献结论,得到该传输过程总共传输的数据长度。

2.C 计算能耗

给出了三台设备在此过程中各自的计算能耗。

因为恒频计算优于变频计算,因此计算频率指定为恒定值。

AP处的计算能耗不考虑,因为不 care 它耗多少电,因此它将以最高频率定频运算。

3 Problem Formulation

该章节构建了一个线性规划问题 P1 和一个非线性规划问题 P2,使得该模型传输的能耗最小(不考虑AP能耗)。P1 对应 partial offloading(可切割问题,可以协作计算),P2 对应 binary loading(不可切割问题,只能一台设备计算)。

3.A 可行性分析

限定 task 的最大比特长度。

4 Optimal Solution to P1

引入辅助变量 E,消去 P,将 P1 问题转化成 P1.1 问题。

Lemma 1 证明该问题是凸问题。然后用拉格朗日乘子法得到函数 L,进而得到对偶函数 g,让 g 由下往上逼近 L,以此得到 L 的下界。

Lemma 2 的结论保证了 g 不会因消息长度过大而趋向于负无穷,无法从下定界。基于该结论,问题进一步转化为 D1.1。

由于符合 Slater 条件, P1.1 和 D1.1 有强对偶性,因此通过求解 D1.1 来得到最优解。

4.A 对偶函数 g 的推导

将 L 函数拆分成互不影响的最优化问题问题 (31) - (35),分别求解即可。不等式约束的最优化问题,构造拉格朗日函数,使用 KKT 条件进行求解,得到 E、τ、l 的最优解。

Remark 1 指明,上述最优解中在某些条件下,τiτ_ilal_a 最优解不是唯一值。我们将两项置为0,以此来评估对偶函数 g。但是这会导致这个解对于问题 P1.1 不可行或非最优,因此在 4.C 中讨论该问题。

4.B 计算 λ & μ 最优解来最大化 g

由于对偶函数 g 通常是凹的、不可微的,因此使用基于次梯度的方法(如椭球法)来求解 λ 和 μ 的最优值。具体过程没说,不太懂。

4.C P1 问题的最优原始解

通过用已求出的各变量最优解带入原来的 P1 或 P1.1 问题,得到新的 LP 问题,用该问题来求解 τiτ_ilal_a 的最优解。

最后用 Table 1 算法展示了求解 P1 问题的全过程,并根据结果提出一些见解:

  • 持续时间 T 变大时,用户更喜欢在 User 本地计算。
  • 信道功率增益 h01h_{01} 变强时,卸载功率 P1opt1P_1^{opt1} 增加,用户更喜欢将更多任务卸载到 Helper 进行计算协作。
  • P2opt1P_2^{opt1} 取决于 h01h_{01}h0h_0P3opt1P_3^{opt1}h1h_1 增加而增加。
    通过这些见解可以设计实验。

5 Optimal Solution to P2

P2 问题相对简单,因为 binary offloading 只需一台设备计算,只要分别计算三台设备的能耗并进行比较即可。

5.A

本地计算模式可直接得出结果。

计算协作模式(to Helper)是一个单变量优化问题,用二分法即可解得。

通信协作模式(to AP)是多变量优化,与 P1 问题同法解得。

6 Numerical Results

用对比法对比各种方法效果。分别针对 partial offloading、binary offloading 两种情况,设计本地计算、计算协作、通信协作、三点协作几种方式进行实验。

实验分别研究了时间 T 对任务最大长度的影响、T 对平均能量消耗的影响、任务长度 L 对平均能量消耗的影响、User 到 Helper 距离对平均能量消耗的影响。

7 Conclusion

计算与通信三点协作方式最优。

未来仍待解决的问题:

  • 尽管只考虑了三点式作业,但可以推广到更一般的情况。但如何有效地将多个 Helper 和 User 配对,以及如何有效设计多用户计算卸载和协作中继仍是困难的问题,需进一步研究。
  • 本文旨在减少总能量消耗,因此采用集中分配。但 Helper 有自身利益,如何采用激励措施激励 Helper 参与计算是一个值得考虑的问题。

参考

[1]MEC笔记-概述
[2]什么是计算卸载?
[3]Relay Channel - WikiPedia
[4]非线性规划 - WikiPedia
[5]凸优化学习:对偶
[6]KKT条件介绍
[7]拉格朗日乘子法(Lagrange Multiplier) 和KKT条件
[8]次导数 次梯度 小结