梁富伟， 裘华东

(1.上海邦德职业技术学院信息中心，上海200444;2.国网浙江省电力有限公司，杭州310012)

0 引言

目前，移动云计算(Mobile Cloud Computing，MCC)技术正在迅猛发展，且正在对移动设置的运行产生巨大影响。移动云计算可以改善应用执行性能，通过将来自移动用户的计算任务迁移至云服务器执行的方式来降低移动用户能耗［1］。这使移动用户可以从计算密集型应用中获得利益，避免应用在局部设备上执行的能源损耗。移动用户通过计算卸载将任务上传至云端服务器执行取代本地执行的方式改善移动电源能耗。计算卸载还可以使得云端资源得到更加充分的利用［2-3］。

一些文献利用博弈理论研究移动云计算。文献［4］中考虑了一种多资源提供者环境，它们相互协作向移动用户提供服务，并通过博弈论的方式共享得到的收益。文献［5］中为了降低移动云计算中服务端和用户端能耗，设计了一种基于拥塞博弈的优化框架，使每个用户作为一个博弈者进行相互博弈，最终使得用户选择进行计算卸载的服务器。文献［6］中在移动云计算中设计了一种嵌套式两阶段博弈算法，移动用户以最小化能耗和服务响应时间为目标，并得到了优化解。文献［7］中设计了一种非集中式博弈算法，通过用户间的自组织得到了最优的计算卸载决策。以上研究的不足在于，均忽略了用户在计算卸载过程中对于有限无线信道资源的共享，也未考虑用户间在计算卸载时的相互影响。

本文考虑的是多竞争用户在共享信道下的计算卸载决策优化问题，共享信道在多用户上传应用时以动态的时槽分配方式进行，每个用户的信道质量各不相同，传输速率也不相同。由于用户应用具有截止时间约束，共享信道的竞争将对用户计算卸载决策产生关键影响。该系统被建模为一个非合作博弈问题，用户以最小化能耗为目标，同时满足应用的截止时间。过多用户选择计算卸载时，单个用户的传输速率将下降，导致无法满足时间约束。设计了一种高斯赛德尔算法对非合作博弈进行了求解，并总能求解得到博弈的Nash均衡解。

1 系统模型

移动云计算环境的计算卸载模型如图1所示，n个移动用户可以通过一个共享通信信道以计算卸载方式向云端提交应用。

如表1所示为对相关符号的说明。

表1 符号说明

用户Um，m∈{1，2，…，n}，以四无组(Jm，Lm，Rm，)进行定义，具体含义是:

Jm=(Dm，Bm)，Dm表示为了执行任务Jm需要的CPU周期数量，Bm表示为了远程执行任务用户Um需要上传至云端的比特数;

Lm=(表示每个CPU周期的能耗表示若用户Um决定局部执行任务，即无需上传至云端执行，任务执行每秒需要的CPU周期;

Rm=(表示无线传输功耗，rm表示用户Um独立使用信道时的无线数据上传速率;

为了简化描述，定义 βm=Bm/rm，Φm=

每个用户Um拥有一个决策变量am，am=0表示用户决定在局部设备上执行任务，am=1表示用户通过算卸载任务至云端执行。对于云服器，令fs表示服务器计算功耗，且假设云端的服务器计算功耗不作为系统瓶颈，即云端拥有足够资源执行用户上传的任务。

用户的计算卸载问题可理解为一个顺序的迭代过程，在每次迭代中，每个用户Um将当前的决策am传输至云端控制器，然后控制器向用户提供反馈，即按当前决策可获得的任务响应时间。接下来，用户更新决策，直到达到均衡状态。最后执行任务的计算卸载和任务处理。本质上，云端控制器将收集用户参数，然后这个多用户的博弈过程，并在均衡状态时终止，使得用户能够按照均衡点的策略进行计算卸载。

1.1 局部处理

若用户Um决定在局部设备上执行任务，应用文献［8］中的能耗模型，局部任务执行产生的能耗和时间分别为:

1.2 远程处理

若用户Um决定将任务计算卸载至远程云端处理，则需同时考虑无线通信模型和云服务器执行的能耗和时延。

考虑所有用户共享同一无线通信信道上传任务，假设现有m个用户进行任务上传，共享时槽以轮询方式进行。不考虑损耗，假设用户按β1≤β2≤…≤βm顺序进行排序，用户Um的上传时间为Toffm。用户Um完成数据传输后，用户Um+1继续与剩余用户共享通信信道。假设用户任务上传时间远大于通信时槽，则:

式中，ηm+1表示用户Um完成数据传输后共享信道上传任务的用户数量，则1/ηm+1表示每个用户的标准化数据传输速率。因此，

则式(1)表明对于一个上传用户Um(即am=1)，有:

表示通过无线信道上传数据时的能耗，可计算功耗与上传时间的乘积:

云服务器执行:假设一旦任务上传至一个云服务器，不存在时延即执行任务，即拥塞发生在共享通信信道上而发生在云服务器上。用户Um在服务器上的执行时间为:

则总的远程执行时间和总的远程执行能耗分别为:

通过考虑用户Um的决策变量am，可以找到总的响应时间和能耗分别为:

2 优化目标

移动云计算环境中，中心调度器需要为所有用户决定决策变量am，使得总体能耗达到最小，同时确保所有用户的响应时间约束，即求解以下最优化问题(Optimization Problem，OPT):

结合式(2)、(6)和(8)，目标函数可重写为:

3 算法设计

由于移动云计算不存在中心调度器，因此，移动用户需要以自身为中心，根据其代价函数决定任务在局部执行或计算卸载至云端执行。换言之，各用户Um自己设置策略am，用户之间是非合作利益个体，以下利用博弈方法对该场景进行研究。

模型中，每个用户旨在最小化执行功耗。用户Um的目标可建模为:令a－m=(a1，…，am－1，am+1，…，an)表示除用户Um之外的所有用户的计算卸载决策集，那么，给定a－m，用户Um将根据以下优化问题的解设置其决策变量am∈{0，1}:

式(8)表明目标函数仅取决于am，且实际上，最优决策解am=1，由于此时不存在用户Um拥有局部执行能耗。然而此时响应时间约束无法得到满足。因此，mOPT是一个带有非无效解的优化问题。

以下定义Nash均衡。假设存在一个矢量a*=，使得对于每个用户Um，给定mOPT的解为则a*称为Nash均衡。

为了度量Nash均衡的有效性，引入调和率PoA概率［9］，定义为一个Nash均衡的最差全局代价与集中式全局最优代价之比。

为了寻找Nash均衡，提出一种高斯赛德尔算法［10］，第一步随机选择 a=(a1，a2，…，an)，ai={0，1}作为初始点。多种情况下，初始点是不可行解(不满足时间约束)。那么，在每次迭代中，随机选择用户Um，并求解在给定a时mOPT问题的最优解。如果mOPT的最优解不同当前决策值am，则设置am为新的最优解;否则，随机选择另一用户继续执行该过程。该迭代过程执行至没有任一用户决策变量发生改变为止，即表明算法到达Nash均衡点［11-12］。

高斯赛德尔算法-寻找Nash均衡点算法如下:

1.Procedure FindNashEquilibrium

2. sort users so that

3. randomly pick a binary vector a=(a1，a2，…，an)

4.NE=FALSE

5.S=

6. form=1→ndo

7. ifam=1 then

8. addmto the setS

9. end for

10. while NE=FALSE do

11.N={1，2，…，n}

12. fork=1→ndo

13.m←arandomly picked number from the setN

14.xopt←solution of(mOPT)for userUm

15. ifxopt≠amthen

16.am←xopt

17. ifxopt=0 then

18. removemfrom the setS

19. else

20. addmto the setS

21. goto line 27

22. else

23. removeifrom the setN

24. if|N|=0 then

25.NE=TRUE

26. return a

27. end for

28. endwhile

4 Nash均衡存在性

本节证明在同质和半同质环境下Nash均衡的存在性［13-14］。定义

则可以重写mOPT为:

定义1 MCC系统为半同质的，当且仅当:

在初始决策am=0时执行算法1，在每次迭代中，下一个拥有最小β值的用户被选择求解mOPT’问题，即:用户按β值递增的顺序按序遍历。当算法执行遇到一个用户由于其时间约束而不选择计算卸载或所有决定选择计算卸载时，算法即终止，且已经到达一个Nash均衡。

假设用户Uk+1为算法在迭代k+1时所选择的下一用户，由于算法仍未终止，则有Sk={1，2，…，k}且

定理1 如果用户Uk+1在迭代k+1时决定选择计算卸载，且j∈Sk，则对于任一j＜k+1，j∈Sk+1。

证明 在该定理条件下，有:

利用式(11)和半同质定义，可以得到:

由于用户Uk+1选择计算卸载，即Φk+1≤0，则有Φj≤Φk+1≤0。

定理2 如果用户Uk+1在迭代k+1时不选择计算卸载，则对于任一j＞k+1，用户Uj也无法计算卸载。

证明 在迭代k+1时，对于任一用户j＞k+1，有aj=0且:

因此，式(11)表明:

由于用户Uk+1无法满足时间约束，则Φk+1＞0，因此，Φj≥Φk+1＞0。

定理1和定理2表明算法中任一用户决策的改变均不会同步导致其他用户决策的改变。因此，当算法终止时，没有任一用户将改变当前决策，即达到Nash均衡解。

定义2 MCC系统为同质的，当且仅当:

βi=βjand τi=τj，i，j∈ {1，2，…，n}

由于同质系统也是半同质系统，那么，Nash均衡可同上的方法找到。

5 仿真实验

为了评估博弈模型的有效性［15］，通过仿真实验分析了算法的收敛时间、Nash均衡点处的能耗两个方面的性能。仿真结果显示算法在同质和半同质环境下总能收敛于Nash均衡点。为了进行多场景实验，随机生成了多个实验配置，每个实验配置以不同的初始决策量进行多次实验，并取其均值。所有配置中，参数均以随机均衡分布形式产生。请求的CPU周期D随机分布于区间［1，10］Gcycles，输入数据量B处于［0.42，42］Mb，信道数据传输速率r处于［6.4，64］Mb/s，局部计算功耗fl随机分布在0.5、0.8和1(单位:giga CPU cycles/s)之间，云服务器计算功耗fs设置为100 giga CPU cycles/s，数据传输功耗Pt处于［0.75，1］W，局部能耗vl等于Pl/fl，局部执行功耗Pl随机分布在20、22.5和25 W间。

图2显示了算法得到的Nash均衡点的数量。可以看出，均衡点的数量随着用户数量的增加而增加，与预期一致。对于较少的用户数量(12个用户以下)，均衡点的数量基本随用户数量呈线性增加，而随后均衡点的变化则更加剧烈。

图2 Nash均衡数量

图3显示了平均和最大博弈收敛的迭代次数(时间)，基本与用户数量呈线性增加，这表明基于博弈的计算卸载决策求解机制与问题的增加扩展性较好。

图3 迭代次数

图4显示了平均卸载率，定义为卸载至云端执行的数量与总用户数量之比，以及显示了卸载率的最大值与最小值。可以看出，随着用户数量的增加，均衡点处成比例的更少的用户会选择终止卸载，这是由于信道能力为常量，因此，远程执行延时会随着用户比例的增加而增加的原因导致的。

图4 计算卸载率

图5显示了算法得到的能耗情况。可以看出，本文的计算卸载算法的能耗代价基本小于基准算法的能耗，这是由于本文算法在确保满足时间约束的同时，在优化使用共享信道的同时，可以使用户更加合理的自主决策计算卸载，降低在局部执行应用的自身能耗。而文献［6］中重点对执行延迟进行了优化，文献［7］中则未考虑共享信道的多用户争用情况，这使得多用户同步计算卸载对于优化目标是得不偿失的。

图5 标准能耗代价情况

6 结语

移动云计算中，用户可以通过计算卸载将应用上传至云端执行，降低局部执行能耗。然而，由于共享通信信道下，多竞争用户上传应用时势必会导致应用执行延时。为了解决时间约束下优化执行能耗的计算卸载决策问题，设计了一种基于非合作博弈算法，以用户最小化自身能耗为目标，通过一种高斯赛德尔方法对博弈的Nash均衡进行了求解。仿真结果表明，算法总能收敛于Nash均衡点处，且能够在满足时间约束的情况下降低执行能耗。