一种移动云计算计算卸载算法及其仿真研究

2019-04-02刘静

实验室研究与探索 2019年2期

刘静

(1. 苏州健雄职业技术学院软件与服务外包学院, 江苏太仓 215411; 2. 苏州大学计算机科学与技术学院, 江苏苏州 215006)

0 引言

随着智能手机的快速普及，越来越多的新型移动应用，如人脸识别、自然语言处理、交互式游戏以及增强现实等正进入社会生活的方方面面。这类移动应用通常为典型的资源紧俏型应用，需要密集型计算和高能耗。由于物理大小的限制，移动设备通常在计算资源和电池容量上是受限的。这种在移动设备上资源需求紧俏与资源受限的矛盾为未来移动平台的发展带来了挑战[1]。

移动云计算可以将资源丰富且计算能力更强的云扩展至资源受限的移动设备端以增强移动设备的处理能力，以解决移动设备资源受限的问题[2]，模型如图1所示。尽管如此，设计综合性能可靠的移动云计算系统仍是一项巨大挑战，其中关键之一是如何在移动设备用户间实现高效的计算卸载机制。影响移动云计算性能的关键因素之一是无线访问的效率[3]。因此会出现多个移动用户同步通过无线信道进行计算卸载，它们之间势必会出现相互干扰，从而降低数据传输的速率，这将导致低效的计算卸载和数据传输时间的延长。此时，对于移动用户而言，计算卸载至云端将是得不偿失的。

图1 移动云计算

本文提出了一种移动云计算中的基于博弈的计算卸载算法。博弈论是设计分布式算法的有效框架，它使得系统中的移动设备用户可以自组织的形成相互满意的计算卸载决策。自组织特征将自治性引入移动云计算系统中，有助于简化云计算复杂中心化的管理策略(即：多方移动用户的信息收集与计算卸载调度)。同时，由于不同的移动设备隶属于不同的个体，它们追求的目标也不相同，博弈论可以分析立足于自身兴趣的多移动设备用户间的相互影响，并推导出兼容的计算卸载机制，使得没有任一移动用户有动机偏离于当前策略。

1 相关研究

当前计算卸载算法设计方面的工作多集中于单移动设备用户环境。如文献[4]中设计了一种最小化能耗的任务调度算法，文献[5]中设计的随机无线信道的能效最优移动云计算调度框架，文献[6]中针对移动任务设计的协作式任务执行框架，以及文献[7]中提出基于李雅普诺夫(Laypunov)优化法设计的动态计算卸载能耗优化算法。然而，以上工作并未做到真正的能耗优化，如局部调度时的中央处理器(Central Processing Unit, CPU)时钟频率控制，以及计算卸载至云端时的传输功率分配问题。文献[8]中虽考虑了能耗与应用完成时间的同步优化，但所涉及的是独立任务集类型，任务间不存在顺序依赖，且未考虑计算卸载决策时的资源分配。文献[9]中利用遗传算法来搜索云端和移动终端计算资源联合执行应用的全局最优解，重点研究了任务迁移的选择问题。

部分文献在多移动设备用户环境下解决计算卸载问题。文献[10]中研究了多用户共享无线网络带宽的场景，设计了一种集中式启发式遗传算法用于求解移动云计算性能最大化问题。文献[11]中考虑了用户移动模型，提出了一种集中式贪婪算法求解多用户计算卸载问题。文献[12]提出一种集中式调度算法在拥有延时需求的多用户间实现了最优化通信和计算资源分配。然而，以上的集中式计算卸载算法均要求所有移动用户发送自身信息(即无线信道增益和计算任务大小)至一个中心实体(即云端)，然后通过该实体决定具体的计算卸载策略。文献[13]中对能耗和时间进行了联合优化，通过集中式调算策略的制定可以实现最优解。文献[14]对能耗进行了最小化优化，从移动终端硬件出发，进行能耗优化。文献[15]中提出一种临近闲置移动终端作为卸载目标的分布式博弈算法，仿真出一种最优结果。不同的是，本文将提出一种非中心式的博弈算法，它可以使每个移动设备用户在局部作出计算卸载决策，这有助降低云端的控制和信号开销。

2 系统模型

2.1 通信模型

无线访问基站s可以是一个无线网络访问点，或蜂窝网中的宏单元基站，可用于管理移动设备的上传/下载通信链路。令an∈0,1表示移动用户n的计算卸载决策，an=1 表明移动用户n选择通过无线信道将任务卸载至云端计算，an=0表明移动用户n选择在其局部设备上执行任务。给定所有用户的决策集a=a1,a2,...,aN，N为用户个数，根据香农定律可以计算移动用户n进行计算卸载时的数据传输速率为

(1)

2.2 计算模型

考虑每个移动设备用户n拥有一个计算任务In=Bn,Dn，可在局部移动设备上计算，也可通过计算卸载至云端进行计算。Bn为计算任务In的计算输入数据量，Dn为完成计算任务In需要的CPU周期数量。以下讨论在局部计算和云端计算时的能耗与处理时间模型。

(2)

计算能耗为:

(3)

根据式(2)和(3)，可以计算局部计算时以处理时间和能耗衡量的计算开销为：

(4)

(2) 云计算模型。对于云计算方法，移动设备用户n将卸载其计算任务In至云端，云端将负责执行用户的计算任务。计算卸载将为移动用户n计算再来由于通信无线访问传输数据至云端的时间与能耗方面的开销。根据前文的通信模型，可以计算移动设备用户n卸载输入数据大小为Bn的传输时间(下标中引入off表示卸载，上标c表示开销，下同)与能耗分别为：

(5)

(6)

(7)

根据式(5)～(7)，可以计算云端执行时以处理时间和能耗衡量的计算开销为:

(8)

根据通信模型和计算模型可知，移动用户间的计算卸载决策是相互关联的。若过多移动用户同步选择将任务通过无线信道计算卸载至云端，势必会导致严重干扰和低数据传输率。当移动用户n的数据率Rn(a)较低时，计算卸载时无线访问会带来较高能耗和较长的传输时间。此时，将任务进行在移动设备上局部执行将更加有利，可以避免云端计算的过长处理时间和高能耗。以下将引入博弈方法求解实现多移动用户的计算卸载决策问题。

3 计算卸载博弈

3.1 博弈形式化

考虑一个计算卸载周期内多个移动设备用户间的分布式计算卸载决策问题，令a-n=a1,…，an-1,an+1,…，aN为除用户n之外所有其他用户的计算卸载策略。给定其他用户的决策a-n，用户n选择合适的策略an∈{0,1}(即：局部计算或云计算)，最小化能耗与处理时间组成的计算开销，即：

∀n∈N

根据式(4)、(8)，计算得到移动用户n的代价函数为

(9)

将以上优化问题形式化为博弈模型G=N,{An}n∈N,{Vn}，移动用户N为博弈者集合，An={0,1} 为用户n的博弈策略集合。以下称博弈G为分布式计算卸载博弈，并引入纳什(Nash)均衡概念。

(10)

∀an∈An,n∈N

Nash均衡具有自适应的稳定属性，它使得用户在均衡处可以实现相互满意的解，没有用户有动机偏离该均衡。

3.2 博弈性质

以下研究分布式计算卸载博弈中Nash均衡的存在性，先引入最优回应的概念。

定义2给定其他博弈者的策略a-n，博弈者n的策略a*n∈An是最优回应，如果：

(11)

根据式(10)和(11)，可以看出，处于Nash均衡时，所有用户的策略对于其他用户的策略均是相互最优回应。基于最优回应概率，可以得到以下分布式计算卸载博弈的属性。

推论1给定分布式计算卸载博弈中其它移动用户的策略a-n，用户n的最优回应可由以下阈值策略得到：

(12)

式中，阈值

(13)

(1) 同质无线访问情形。若无线信道为同质的，则对于任意用户n,m∈N，PmHm=PnHn=K。这表明所有移动用户拥有相同信道条件，与基站分配相同传输功率。然而，不同用户拥有不同阈值Ln，即在计算能力和任务方面是异质的。

对于同质无线访问，对移动设备用户集N进行排序，使得L1/K≥L2/K≥…≥LN/K，得到以下结论。

推论2对于同质无线访问的分布式计算卸载博弈，若存在一个非空可获利移动用户组S⊆N，使得S≤Li/K+1,i∈S，且对于S⊂N，S>Li/K,j∈NS，则用户i∈S的策略an=1，其他用户j∈NS的策略aj=0组成的策略集为一个Nash均衡。

证明根据式(12)，对于一个用户i∈S，其接收的干扰为：

(14)

根据推论1可知，执行策略an=1为最优回应。类似地，对于用户j∈NS，可知执行策略aj=0为最优回应。由于所有用户都相互执行最优回应策略，故所提策略集即为Nash均衡。

例如：对于4个用户L1/K,L2/K,L3/K,L4/K=5,4,3,2，可获得的用户组S=1,2,3。当L1/K≥0时，可以通过算法1构造可获利用户组。

定理1对于同质无线访问的分布式计算卸载博弈总存在一个Nash均衡。具体地，所有用户n∈N当L1/K<0时，执行策略an=0即为一个Nash均衡。当L1/K≥0时，通过算法1构造一个可获利用户组S≠φ，则用户i∈S的策略an=1，其他用户j∈NS的策略aj=0组成的策略集为一个Nash均衡。

证明给定满足L1/K≥L2/K≥…≥LN/K排序的移动用户集，若L1/K<0，易知可获利用户组S=φ。此时，所有用户n∈N执行策略an=0为最优回应，即一个Nash均衡。

若L1/K≥0，可通过算法1构造可获利用户组S≠φ。第1步，设置S=1，易知S=1≤L1/K+1，满足式(12)中的条件。第2步，2≤t≤N，定义S′=S∪t。若S′>Lt/K+1，则得到可获利用户组S=1,…,t-1，原因在于：①S满足S≤Lt-1/K+1(否则无法推进至步骤t)，这表明式(12)的条件是满足，即：S≤Lt-1/K+1≤…≤L1/K+1;② 由于S′=t>Lt/K+1，有S=t-1>Lt/K，这表明式(13)的条件是满足的，即：S>Lt/K≥…≥LN/K。由于算法1中步骤数上限为N，故必定可以得到可获利用户组S≠φ。

算法1寻找可获利用户组算法

1. Input:the set of ordered mobile device users withL1/K≥L2/K≥…≥LN/KandL1/K≥0

2. output:a beneficial cloud computing groupS

3. setS={1}

4. fort=2 toNdo

5. setS’=S∪{t}

6. if |S’|>Lt/K+1 then

7. stop and go to return

8. else setS=S’

9. end if

10. end for

11. return S

(2) 一般无线访问情形。若无线信道为异质的，则PmHm≠PnHn。由于移动设备用户拥有不同的传输功率Pn，信道增益Hn及阈值Ln，故不能应用同质环境中采用的方法。以下引入势博弈的概念进行求解。

(15)

则有：

(16)

(17)

以下通过说明分布式计算卸载博弈为势博弈的方式证明该博弈存在Nash均衡。具体地，定义势函数为：

(18)

IA为指标函数，若事件A为真，则IA=1，否则，IA=0。

定理2分布式计算卸载博弈为带有势函数式(18)的势博弈，总存在一个Nash均衡。

4 计算卸载博弈算法

本节设计分布式计算卸载博弈算法，如算法2所示，可用于实现分布式计算卸载博弈决策的Nash均衡解。

算法2分布式计算卸载博弈算法

1. Initialization:

2. Each mobile device usernchooses the computation decisionan(0)=1

3. end initialization

4. repeat for each usernand each decision slottin parallel

5. measure the interferenceμn(t)

6. compute the best response set △n(t)

7. if △n(t)≠? then

8. contend for the decision update opportunity

9. if win the decision update contention then

10. choose the decisionan(t+1)∈△n(t) for next slot

11. broadcast the RTU message to other users

12. else choose the original decisionan(t+1)=an(t) for next slot

13. end if

14. else choose the original decisionan(t+1)=an(t) for next slot

15. end if

16. until no RTU message are broadcasted forMconsecutive slots

4.1 算法设计

分布式计算卸载博弈使移动用户在计算任务执行前实现相互满意的决策，主要利用了博弈的有限改进属性，使得每个移动用户每次均可进行计算卸载决策的改进更新。具体地，可利用无线访问基站的同步时钟信号，考虑一个计算卸载决策中的时槽结构，每个决策时槽t包括两个部分：

(2) 决策更新。使每个移动用户在每个决策时槽中进行一次决策更新，以搜索博弈的有限改进属性。每个能够改进其计算性能的用户以分布式方式竞争决策更新机会。具体地，根据推论1，每个移动用户n首先基于度量干扰μnt计算其最优回应集为：

Δn(t)=

故若Δn(t)≠φ，即用户n可以改进，则用户n将竞争决策更新机会。否则，用户n将在下一决策时槽中维持当前策略不变，即ant+1=ant。对于决策更新，本文采用随机退避算法设置决策更新时长为τ*。

4.2 性能分析

本节讨论分布式计算卸载博弈算法的Nash均衡的有效性。由于算法可能产生多个Nash均衡，算法将随机选择一个Nash均衡(由于决策更新阶段用户是随机选择的)。基于博弈调和率PoA的概念，以量化最差Nash均衡与集中最优解的效率。令χ为算法产生的Nash均衡集，则PoA可定义为

5 数值仿真

首先考察算法得到的移动设备用户的计算代价Vn(a)的变化情况，如图2所示。可以看出，算法可以降低用户代价，并收敛于均衡解。为了证明收敛均衡为Nash均衡，进一步给出了算法中势函数Ψ(a)的变化，如图3所示。结果表明，博弈算法可以使得势函数到达最小值，而根据势函数属性可以断定该点即为Nash均衡。

图2 用户代价变化

图3 势函数值变化

图4 CPU周期数对总体代价的影响

图5 计算数据量对总体代价的影响

图6 总体代价

图7 算法迭代次数

为了评估分布式计算卸载算法的控制和信号开销，进一步观察了在移动设备与云端间进行信号控制信息交换的信号量，如图8所示。结果表明分布式计算卸载算法相对集中式算法可以降低89%的信号量，这是因为分布式算法中，单个移动用户仅在进行计算卸载决策更新时才进行信息交换(干扰度量和决策更新)。而集中式算法中，每个移动用户需要传输所有其局部参数至云端，包括传输功率、信道增益、背景干扰功耗、局部计算能力等。而分布式计算卸载算法仅在局部进行计算卸载决策。