移动云计算^[1]是一种将云计算^[2]与移动互联网^[3]相融合的新技术，受到了国内外学者的广泛关注。在移动云计算中，用户可以将移动应用迁移到云端来改善其移动终端处理能力弱、存储空间小以及电池续航时间短等性能缺陷^[4]。云端可根据移动用户的需求来分配VM^[5]，并由这些VM为用户提供相应的服务。然而，大量的移动应用在云端执行，必然会增加网络拥塞，影响用户的效用^[6]。因此，如何合理管理移动云计算的VM是值得研究的课题。

目前，已有多个文献对移动云计算中的VM管理问题进行了研究。文献[7]根据合作博弈提出了一种协作式的资源分配方案，在该方案下，云提供商通过判断是否加入协作的方式来最大化效用。文献[8]考虑云端与移动终端的来回延时，提出了一种最优的云资源分配策略。文献[9]基于拍卖机制提出了一种VM动态调度策略(VMdynamic scheduling,VMDS)，该策略可根据用户的需求灵活地为用户分配计算资源。然而，上述方法都是从云提供商效用最大的角度来设计VM的分配，并没有考虑业务量引起网络拥塞对用户效用造成的影响，因此，很难同时实现云提供商和用户的效用最大化，不能较好地运用于移动云计算系统。

针对该问题，本文首先采用Stackelberg博弈模型对移动云计算中的VM管理问题进行分析，在用户效用函数中考虑业务量引起网络拥塞所造成的影响，并证明了纳什均衡点的存在性和唯一性。然后给出了最优的静态价格及分配，并利用粒子群算法搜索最优的动态价格及分配。最后通过仿真验证了所提算法及策略的有效性。

1 系统模型

图 1给出了移动云计算中VM调度的网络模型，与文献[10]类似，云提供商通过M个小区向用户提供VM。假设云提供商的带宽为${{c}_{L}}$，其提供的VM类型均相同，且每个VM产生的数据量为aKbit/s。假设小区i的带宽为${{c}_{i}}$，其服务的用户数为${{n}_{i}}$，该小区内的用户订购VM的价格为${{p}_{i}}$。用户只能通过其所在小区获取VM，小区i中的用户j订购的VM数量为${{x}_{ij}}$。

根据上述假设，可定义小区i中的用户j的效用函数：

${{F}_{ij}}({{x}_{ij}})={{w}_{i}}\log(1+{{x}_{ij}})-{{p}_{i}}{{x}_{ij}}-\frac{1}{{{c}_{i}}-a{{X}_{i}}}-\frac{1}{{{c}_{L}}-aX}$

(1)

式中，${{w}_{i}}>0$为收益常数；${{X}_{i}}=\sum\limits_{j=1}^{{{n}_{i}}}{{{x}_{ij}}}$；$X=\sum\limits_{i=1}^{M}{{{X}_{i}}}$。

从式(1)可以看出，用户订购的VM越多，则产生的数据量越大，相应的延时越大，拥塞成本越高。当云提供商确定每个小区的VM价格${{p}_{i}}$后，用户选择相应的策略来最大化其自身收益。

$\max {{F}_{ij}}({{x}_{ij}},x_{-ij}^{*},{{p}_{i}})={{F}_{ij}}(x_{ij}^{*},x_{-ij}^{*},{{p}_{i}})$

(2)

式中，${{x}_{-ij}}$表示小区i中除用户j以外的其他用户订购VM的数量。

云提供商的效用函数：

$L(p)=\sum\limits_{i=1}^{M}{{{p}_{i}}{{X}_{i}}}=\sum\limits_{i=1}^{M}{{{p}_{i}}}\sum\limits_{j=1}^{{{n}_{i}}}{{{x}_{ij}}}$

(3)

式中，$p=({{p}_{1}},{{p}_{2}},\cdots,{{p}_{M}})$表示云提供商出售VM的价格策略。本文的目标是通过价格策略来控制小区中的VM订购数量，同时实现云提供商和用户的效用最大化。

2 Stackelberg博弈问题的求解 2.1 纳什均衡

根据Stackelberg博弈，当云提供商和用户的策略达到纳什均衡后，云提供商和用户都不能通过单方面改变自己的策略来提高效用。因此，云提供商为了最大化效用理性的制定价格策略，用户也会对云提供商的价格策略做出理性反应来确保其效用最大化。根据文献[11]，可通过确定纳什均衡点的存在性和唯一性的方式来证明系统可同时实现云提供商和用户的效益最大化。为了确定纳什均衡点的存在且唯一，首先对给定的VM价格$ {{p}_{i}}$下，小区i中用户j的最优VM订购数量进行分析。

由于用户之间是非合作的，且相互独立，因此根据式(1)可得：

$\begin{align} & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{G}_{ij}}({{x}_{ij}})=\\ & \frac{\partial {{F}_{ij}}({{x}_{ij}})}{\partial {{x}_{ij}}}=\frac{{{w}_{i}}}{1+{{x}_{ij}}}-{{p}_{i}}-\frac{a}{{{({{c}_{i}}-a{{X}_{i}})}^{2}}}-\frac{a}{{{({{c}_{L}}-aX)}^{2}}} \\ \end{align}$

(4)

且对于小区i中的$\forall j\in \text{ }\!\!\{\!\!\text{ 1,2,}\cdots,{{n}_{i}}\text{ }\!\!\}\!\!\text{ }$有：

$\frac{{{\partial }^{2}}{{F}_{ij}}({{x}_{ij}})}{\partial x_{ij}^{2}}=-\frac{{{w}_{i}}}{{{(1+{{x}_{ij}})}^{2}}}-\frac{2{{a}^{2}}}{{{({{c}_{i}}-a{{X}_{i}})}^{3}}}-\frac{2{{a}^{2}}}{{{({{c}_{L}}-aX)}^{3}}}<0$

(5)

根据式(5)可知，${{G}_{ij}}({{x}_{ij}})$是单调递减函数，因此在超平面${{X}_{i}}={{c}_{i}}$上${{x}_{ij}}$为非负时${{F}_{ij}}({{x}_{ij}})$是严格凹函数。由式(4)可知，当${{x}_{ij}}\to \infty $时，${{G}_{ij}}({{x}_{ij}})<0$，因此，在给定小区i中的VM价格${{p}_{i}}$后，该小区内用户j的最佳VM订购数量$x_{ij}^{*}$存在且唯一。

由于纳什均衡点存在且唯一，根据文献[11]，将纳什均衡点作为VM的价格和订购数量，就能同时最大化用户和云提供商的效用。根据文献[9]，云计算系统中的VM调度可分为静态和动态两种情况，因此本文分别针对这两种情况来计算最优的VM价格及分配。

2.2 最优静态价格及分配

在实际生活中，用户订购VM的数量${{x}_{ij}}>0$。为了保证式(1)的纳什均衡为正值，令${{x}_{ij}}=0$时，${{G}_{ij}}({{x}_{ij}})>0$，则有：

$ {{p}_{i}}<{{w}_{i}}-\frac{a}{c_{i}^{2}}-\frac{a}{c_{L}^{2}} $

(6)

根据文献[12]，系统可为每个用户预分配的带宽为c，则小区i的带宽为${{c}_{i}}={{n}_{i}}c$，云提供商的带宽为${{c}_{L}}=\sum\limits_{i=1}^{M}{{{c}_{i}}}$，则有：

${{p}_{i}}<{{w}_{i}}-\frac{a}{{{({{n}_{i}}c)}^{2}}}-\frac{a}{{{\left(\sum\limits_{i=1}^{M}{{{n}_{i}}c} \right)}^{2}}}$

(7)

移动云计算网络中，用户越多，则小区分配到的带宽越大，故此假设小区带宽与该小区的用户数成正比，则有：$\frac{{{c}_{i}}}{{{c}_{k}}}=\frac{{{n}_{i}}}{{{n}_{k}}}$和${{c}_{L}}=\frac{\sum\limits_{k=1}^{M}{{{n}_{k}}}}{{{n}_{i}}}{{c}_{i}}$。理想情况下，用户订购的VM数量与小区带宽成正比，由于同一小区内用户的收益常数${{w}_{i}}$相同，因此同一小区内所有用户订购的VM数量一致，则有：${{x}_{ij}}=\frac{{{X}_{i}}}{{{n}_{i}}}$和$\frac{{{X}_{i}}}{{{X}_{k}}}=\frac{{{n}_{i}}}{{{n}_{k}}}$。由于$X=\sum\limits_{i=1}^{M}{{{X}_{i}}}$，则$X=\frac{\sum\limits_{k=1}^{M}{{{n}_{k}}}}{{{n}_{i}}}{{X}_{i}}$。再根据式(4)得：

${{p}_{i}}=\frac{{{n}_{i}}{{w}_{i}}}{{{n}_{i}}+{{X}_{i}}}-\frac{{{\alpha }^{2}}+1}{{{({{n}_{i}}c-a{{X}_{i}})}^{2}}}$

(8)

式中，$\alpha={{{n}_{i}}}/{\sum\limits_{k=1}^{M}{{{n}_{k}}}}\;$。对于小区i，根据式(3)可得：

${{L}_{i}}=\left[ \frac{{{n}_{i}}{{w}_{i}}}{{{n}_{i}}+{{X}_{i}}}-\frac{{{\alpha }^{2}}+1}{{{({{n}_{i}}c-a{{X}_{i}})}^{2}}} \right]{{X}_{i}}$

(9)

对式(9)求导可得：

$\frac{\partial {{L}_{i}}}{\partial {{X}_{i}}}=\frac{n_{i}^{2}{{w}_{i}}}{{{({{n}_{i}}+{{X}_{i}})}^{2}}}-\frac{({{\alpha }^{2}}+1)({{n}_{i}}c+a{{X}_{i}})}{{{({{n}_{i}}c-a{{X}_{i}})}^{3}}}$

(10)

令$\frac{\partial {{L}_{i}}}{\partial {{X}_{i}}}=0$，单位化带宽和VM产生的数据量，即c=1和a=1，则有：

$X_{i}^{*}={{n}_{i}}\frac{{{(n_{i}^{2}{{w}_{i}})}^{1/3}}-{{({{\alpha }^{2}}+1)}^{2}}}{{{({{\alpha }^{2}}+1)}^{2}}+{{(n_{i}^{2}{{w}_{i}})}^{1/3}}}$

(11)

将式(11)代入式(8)可得：

$p_{i}^{*}=\frac{w_{i}^{2/3}[{{\alpha }^{1/3}}+{{(n_{i}^{2}{{w}_{i}})}^{1/3}}]}{2n_{i}^{2/3}}-\frac{{{\alpha }^{1/3}}{{[{{\alpha }^{1/3}}+{{(n_{i}^{2}{{w}_{i}})}^{1/3}}]}^{2}}}{4n_{i}^{2}}$

(12)

2.3 最优动态价格及分配

在实际应用中，系统只能根据统计平均来给小区分配带宽^[10]，当用户订购VM的数量是实时变化时，即VM动态调度，由于系统无法实时的根据用户需求来分配带宽，导致系统给用户预分配的带宽与VM产生的数据量不成正比，很难直接求解出VM的最优价格。因此，本文考虑采用进化算法来搜索最优价格。

由于系统只有快速地获得最优价格才能有效地执行VM分配，因此需要选择一种合适的进化算法来提高计算速度。对式(1)和式(3)分析后发现，用户首先根据VM的价格来计算最优的VM订购数量，云提供商再根据用户的VM订购数量调整VM的价格，如此反复，直到获得最优的价格策略。由于云提供商需要根据上一次循环中的VM价格和VM订购数量来决定下一次循环中的VM价格，因此可采用同时提供多种价格的方式来减少循环次数，提高计算速度。故此，本文采用可同时对多种价格进行迭代的粒子群算法来搜索最优价格。具体实现过程如下：

1)初始化粒子群中粒子的位置${{p}_{i}}(0)$和速度${{v}_{i}}(0)$；

2)根据${{p}_{i}}(0)$和式(4)计算每个粒子的最优VM订购数量${{x}_{ij}}(0)$；

3)将粒子的$\text{pbes}{{\text{t}}_{i}}$设置为个体最优位置，gbest设置为群体最优位置，即使得式(3)最大；

4)根据下式对每个粒子的位置进行更新：

$\begin{align} & {{v}_{i}}(t+1)=\omega {{v}_{i}}(t)+{{\upsilon }_{1}}\text{rand}()[\text{pbes}{{\text{t}}_{i}}(t)-{{p}_{i}}(t)]+\\ & \ \ \ \ \ \ \ \ \ \ \ {{\upsilon }_{2}}\text{rand}()[\text{gbest}(t)-{{p}_{i}}(t)] \\ \end{align}$

(13)

${{p}_{i}}(t+1)={{p}_{i}}(t)+{{v}_{i}}(t+1)$

(14)

式中，$\text{rand}()$为随机函数；$\omega$为惯性因子；${{\upsilon }_{1}}$和${{\upsilon }_{2}}$为正的加速常数；

5)根据每个粒子的${{p}_{i}}(t+1)$和式(4)获得最优的VM订购数量${{x}_{ij}}(t+1)$；

6)若$L[{{p}_{i}}(t+1)]>L[\text{pbes}{{\text{t}}_{i}}(t)]$，则$\text{pbes}{{\text{t}}_{t}}(t)={{p}_{i}}(t+1)$；

7)若$L[{{p}_{i}}(t+1)]>L[\text{gbest}(t)]$，则$\text{gbest}(t)={{p}_{i}}(t+1)$；

8)判断是否满足连续4次循环中的gbest相等，若满足，则返回步骤8)，否则返回步骤4)；

9)$(p_{i}^{*},x_{ij}^{*})=\text{gbest}$，算法停止。

上述算法在初始化粒子群中粒子的位置后，需要根据${{p}_{i}}(0)$和式(4)获得${{p}_{i}}(0)$才能获得初始的个体最优位置${{x}_{ij}}(0)$和群体最优位置$\text{pbes}{{\text{t}}_{i}}$，对应步骤2)和步骤3)。算法在一次循环计算中会对多种价格进行处理，并根据上一次循环得到的价格与用户订购VM的数量来计算新的价格，对应步骤4)。个体最优位置$\text{pbes}{{\text{t}}_{i}}$中的价格为个体价格，而VM订购数量为个体价格下最优的VM订购数量。群体最优位置gbest中的价格为群体最优价格，即当前循环中使得云提供商效用最大的价格。每次循环结束后，算法都能获得多种新的价格，然后通过步骤5)计算新价格下的最优VM订购数量，并根据步骤6)和步骤7)重新设置$\text{pbes}{{\text{t}}_{i}}$和gbest，直到获得最优的VM价格和订购数量为止。这种采用多初值搜索最优价格的方式实现简单、精度高且收敛速度快能较好的适应移动云计算环境。

本文VMPA策略中每个小区的VM价格都不同，系统可根据VM静态调度和VM动态调度，并利用上述方法来设计每个小区的VM价格，控制VM订购数量和网络拥塞，实现同时优化云提供商和用户效用的目标。

3 仿真结果与分析

本节从算法的收敛速度、用户和云提供商的效用等方面对所提方案进行仿真分析。仿真模型参考图 1，设置1个云提供商，4个小区。部分其他参数设置如下：$\omega=0.1$，${{\upsilon }_{1}}=0.15$，${{\upsilon }_{2}}=0.15$，c=2和a=1。

图 2给出了在${{w}_{1}}\text{=}6$，${{n}_{1}}\text{=}8$；${{w}_{2}}\text{=}3$，${{n}_{2}}\text{=}4$；${{w}_{3}}\text{=}6$，${{n}_{3}}\text{=}4$；${{w}_{4}}\text{=}3$，${{n}_{4}}\text{=}8$的4种情况下，算法的收敛速度，图中采用VM的价格作为每代的评估标准。从图中可以看出：1)算法在40代后就能达到收敛，验证了算法能够确保所提方案有效地执行；2)小区中的用户数对VM价格几乎没有影响；3)小区中用户的收益常数越高，则VM价格越高。

图 3给出了${{w}_{i}}\text{=}6$时VM订购数与VM价格的关系：1)当VM的价格一定时，用户越多，则订购的VM越多；2)当小区中的用户数一定时，VM的价格越大，则用户订购的VM越少，验证了所提方案可通过VM的价格来控制VM订购数和网络拥塞。

图 4给出了VM订购数与用户数的关系：1)收益常数${{w}_{i}}$越大，则用户订购的VM数越多，这是因为收益常数越大，用户获得的效用越高，因此用户可通过适当多订购VM来提高效用；2)小区中的用户数越多，则小区分配到的带宽越大，当VM的价格一定时，VM订购数随着用户数的增加而增加，在这一过程中所提方案可保证$a{{X}_{i}}<{{c}_{i}}$，即小区中的平均数据量小于其带宽，不会引起网络拥塞。

图 5给出了${{w}_{i}}=3$时本文VMPA方案、VMDS方案以及VM价格固定方案(VMfixed price,VMFP)在云提供商效用方面的比较：1)3种方案中的云提供商效用随着用户数的增加而增加，这是因为用户数越大则订购的VM越多所造成的结果；2)本文VMPA方案的效用高于VMDS方案和VMFP方案，这是因为VMPA方案是采用主从博弈的方式获得最优的价格策略，能够最大化云提供商的效用；3)VMFP方案在p=1.5时的效用与VMPA方案较为接近，但是VMFP方案只能根据统计方式来制定价格策略，而VMPA方案可根据用户的需求随时调整价格策略，因此VMPA方案更能适应动态变化的移动云计算环境。

图 6给出了${{n}_{i}}\text{=8}$，${{w}_{i}}=3$时3种方案在用户效用方面的比较，为确保公平性，VMFP方案中的价格${{p}_{i}}=1.5$，从图中可以发现：1)当小区中的用户数一定时，用户效用随着VM订购数的增加而增加，当用户效用达到最大值后，再增加VM订购数，拥塞成本会急剧增加，使得用户效用下降；2)本文VMPA方案的用户效用高于另外两种方案，这是因为VMPA方案考虑了业务量引起网络拥塞对用户效用造成的影响。

4 结束语

本文对移动云计算中的VM管理问题进行了研究，结合Stackelberg博弈模型，提出了一种VMPA方案。仿真结果表明，本文VMPA方案能有效地均衡小区中VM的订购数，控制网络拥塞，与已有的方案相比，本文VMPA方案能同时满足云提供商和用户效用最大，在复杂的移动云计算环境中具有较好的应用前景。

虽然本文VMPA方案能有效地改善云提供商和用户的效用，但是动态变化的无线信道同样会对移动应用的性能造成影响。事实上，用户将移动应用迁移至云端执行后，其移动终端是处于空闲状态。因此，下一步将充分利用移动终端和云端的计算资源，考虑在动态变化的无线信道中，通过联合执行的方式来进一步改善移动应用的性能。