下载掌阅APP，畅读海量书库
立即打开
本节提出了一种基于移动边缘计算的动态服务迁移算法，该算法包括三个过程：首先，通过李雅普诺夫优化方法对边缘服务器的存储队列进行优化；然后，利用采样平均近似（Sampling Average Approximation,SAA）算法近似未来效用；最后，利用马尔可夫近似算法最大化系统效用。
在式（1-16）描述的优化问题中，所有服务器的存储约束限制 C1.1使得不同时隙的服务部署决策互相耦合。此外，系统效用包括运营商效用以及服务处理开销两部分，它们的内在关联性使问题难以解耦。为了解决上述问题，本章利用李雅普诺夫优化方法来确保服务部署决策满足约束条件 C1.1。通过引入虚拟队列，李雅普诺夫优化能够在队列稳定性和系统效用最大化之间权衡。服务器k的动态服务队列可以表示如下：
其中，队列长度 Q k ( t )表示时隙 t 服务器 k 的过载数据量，变量Δ D k ( t )表示时隙 t 服务器 k 的吞吐量。本章通过使队列 Q k ( t )保持稳态来满足优化问题中的约束条件C1.1，二次李雅普诺夫函数定义如下：
二次李雅普诺夫函数可以被视为队列偏差的标量度量。为了维持队列稳态，引入李雅普诺夫漂移函数：
式（1-16）中的优化问题可以转化为李雅普诺夫在线优化问题，描述如下：
SAA算法基于蒙特卡洛采样，用于解决多时隙随机问题。在每个时隙里，SAA算法基于当前的用户位置生成一定数量的随机游走场景，对于每个场景，服务器掌握用户的移动轨迹，在具备该先验知识的前提下，可以做出最优的服务部署决策，得到未来的服务处理开销。经过多次循环，取期望值作为近似得到的服务处理开销。基于采样平均近似的效用近似算法流程如算法1.1所示。
算法1.1 基于采样平均近似的效用近似算法
输入 用户及服务器位置，服务请求信息
输出 未来服务处理开销的期望值
生成一定数量的用户随机移动场景；
for 每个场景 do
服务器获取用户的全局移动轨迹并将其作为先验知识；
服务器求解李雅普诺夫在线优化问题；
服务器根据最优服务部署决策获得未来服务处理开销；
end for
传统的SAA算法直接选择具有最佳近似性能的策略作为最终解决策略。但是，随机样本的偶然性可能导致SAA算法的性能产生很大差异。因此，本章构建的模型仅利用SAA算法来近似预期的系统效用。
将算法1.1中估计的服务处理开销代入李雅普诺夫在线优化模型，利用马尔可夫近似模型动态部署服务请求数据。优化目标表示为如下函数：
引入log-sum-exp凸函数将上述函数做如下等价定义：
其中，参数β为正常数。根据log-sum-exp凸函数的性质， J β ( ξ ( t ))可近似为李雅普诺夫在线优化问题的解，其误差表示如下：
由此可知当参数β趋近于无穷时，误差为0。设服务部署决策被选择的概率为 p ξ ，式（1-20）中的优化问题可以被等价转化为如下马尔可夫模型：
上述问题的Karush-Kuhn-Tucker（KKT）条件如下：
最优服务部署决策概率分布可以通过式（1-26）计算。
