1.4.2 基于采样平均近似的未来效用估计

SAA算法基于蒙特卡洛采样，用于解决多时隙随机问题。在每个时隙里，SAA算法基于当前的用户位置生成一定数量的随机游走场景，对于每个场景，服务器掌握用户的移动轨迹，在具备该先验知识的前提下，可以做出最优的服务部署决策，得到未来的服务处理开销。经过多次循环，取期望值作为近似得到的服务处理开销。基于采样平均近似的效用近似算法流程如算法1.1所示。

算法1.1 基于采样平均近似的效用近似算法

输入 用户及服务器位置，服务请求信息

输出 未来服务处理开销的期望值

生成一定数量的用户随机移动场景；

for 每个场景 do

服务器获取用户的全局移动轨迹并将其作为先验知识；

服务器求解李雅普诺夫在线优化问题；

服务器根据最优服务部署决策获得未来服务处理开销；

end for

传统的SAA算法直接选择具有最佳近似性能的策略作为最终解决策略。但是，随机样本的偶然性可能导致SAA算法的性能产生很大差异。因此，本章构建的模型仅利用SAA算法来近似预期的系统效用。