下载掌阅APP，畅读海量书库
立即打开
边缘计算是一种优化云-边-端资源分布的范式，从本质上来说它也是一种调度或者决策范式。结合前面提出的四个方向，我们依次分析其调度定义。在计算卸载中，边缘设备或者边缘用户需要决定是否需要卸载，以及卸载的比例，而边缘服务器也需要具体分配资源，达到高效的边缘协同；在服务缓存中，云数据中心需要将各类计算密集型的服务缓存到边缘服务器，为用户提供就近服务，即需要决策服务类别、服务数量、服务放置的位置；在边缘智能中，同样需要决策任务卸载方案、CNN模型类别、网络带宽分配；在视频分析中，需要确定视频编码的码率、分辨率或帧率、推理模型等。然而，由于边缘网络的动态性、用户的移动性、设备的异构性等原因，确定性策略很难取得高效的性能，进而衍生出一系列基于预测或学习的方法。本节简要介绍三种代表性方法：深度强化学习、赌博机算法和李雅普诺夫优化。
强化学习（Reinforcement Learning, RL）是机器学习的范式和方法论之一，用于描述和解决agent与环境交互中，通过学习策略以实现特定目标的问题。强化学习也是一种学习如何从状态映射到行为以获取最大累积奖励的学习机制，通过环境给予的奖励来不断优化状态-行为的对应关系。强化学习具有以下三个特点：（1）延迟反馈而非即时反馈，即只有当动作执行之后才能得到反馈；（2）具有明显的时间序列性质；（3）级联效应，即当前动作会影响后续状态。我们分别用
S
，
A
，
R
表示强化学习三个要素，即状态空间，动作空间和奖赏函数。显然，状态只是环境的一部分抽象，而不是全部，否则便可在上帝视角决策；动作定义了agent的行为，通常来说是状态的具体映射或概率分布；奖赏函数是一个标量的反馈信号，表示agent在某一时刻的好坏。如图4-13所示，状态
S
t
下执行动作
A
t
，获得奖赏
R
t
，并将状态转移至下一个状态
S
t
+1
，依次执行，直至任务执行完成或者达到最大决策轮数。“
S
→
A
”为一组状态-动作映射，强化学习的目标是将每一个状态
S
t
，映射到未来
N
个时隙内取得最大累积奖赏
或累积折扣奖赏
对应的那个动作
A
t
或者动作概率分布。
图4-13 序列化决策过程
边缘计算场景下的决策与强化学习的特点高度契合。以计算卸载为例，状态为从边缘网络下可获得的整合信息，如历史网络吞吐量、任务规模、队列状态等；动作为卸载决策，即卸载比例，当存在多个边缘服务器时，还需决策卸载的目标服务器；奖励为执行该决策获得的时延和能耗减少值。当且仅当被卸载任务完成，才能评估当前动作的好坏；由于任务是持续而非集中到来，因而需要将时间划分成多个时隙，在每个时隙确定卸载策略，具备时间序列性质；若当前卸载决策操作不当，如过度卸载，可能会导致网络拥塞，服务器待执行队列冗长，进而影响下一个状态。
如图4-14所示，agent在状态和动作之间的映射通常采用深度神经网络（DNN）来表示，agent根据当前状态，给出对应的动作，动作执行完毕得到即时奖励，并将状态转移至下一状态。显然，越是完整准确的状态，agent越能给出高效的动作。如在计算卸载中，精准的网络吞吐量估计能显著减少网络拥塞的情况，给定任务分布或者到来模式也有利于决策。然而，这些信息往往是未知的，故强化学习只能不断地从历史数据中学习最佳策略。在很多场景下，状态空间和动作空间往往是指数级别的，而试错的代价又十分昂贵，因而大部分研究都是将训练工作部署在服务器端，并通过数据增强或者仿真的办法来采集策略网络的训练样本。
图4-14 强化学习决策过程
赌博机算法在不确定的场景中做出实时决策，具有简单高效的特点，在很多方面具有广泛的应用，如根据用户的点击以及用户的历史信息为用户推送感兴趣的内容，实时地调整商量价格来最大化利润，动态地调整投资方案来最大化回报。赌博机算法其实是强化学习在决策选择上的一个分支，其主要用于权衡以下两者：①利用（exploitation）：基于已知最好策略，选取已知具有较高回报的item（贪婪、短期回报）；②探索（exploration）：不考虑之前的策略，探索潜在的高回报的策略。极端情况下，每次都选择已有策略最优的，或者每次随机选择一个策略，显然都不能达到最优，因而需要对这两者进行折中，其中常见的方法有Epsilon-Greedy算法、汤普森采样算法以及UCB（upper confidence bound）算法。赌博机算法通常需要量化一个核心问题：错误的选择到底有多大的遗憾？能不能少一些遗憾？所以便有了衡量赌博机算法的一个指标： 累积遗憾 R A （ T ）。公式为
式中，
t
表示轮数；
r
表示回报；
表示
T
轮的期望最大收益；
表示
T
轮臂选择带来的收益。
边缘计算中，每一个决策选项可认为是一个臂（arm），决策者并不知道每个决策能带来的收益分布，因而需要在不断的探索和利用中最大化累积收益。以服务缓存为例，云中心并不知道每种策略的收益，然而固定缓存策略可能无法满足移动用户的需求，导致用户体验下降；而每次随机策略可能会导致昂贵的服务迁移和服务重新部署代价，因而需要在不断的探索和利用中找到平衡，优化决策过程。
李雅普诺夫优化是指使用李雅普诺夫函数优化动态系统，广泛用于控制理论以确保不同形式的系统稳定性。通常来说，任意时刻的系统状态由多维向量表述，李雅普诺夫函数是多维状态的非负标量。当系统向着不好的状态移动时（负方向），函数被界定为增长。该优化机制通过执行使李雅普诺夫函数向负方向漂移为零的动作来实现系统稳定性。简单来说，对于一个所创建的队列，队列中的每个元素代表某个时刻下的表现，如时延或者能耗，队列的稳定性有利于减少性能波动，而李雅普诺夫优化正是用于保证队列的稳定性。
边缘计算中，由于设备的异构性、网络的波动性，应用在每个处理过程中产生的性能表现都不尽相同，显然用户更倾向于能提供稳定性能的系统。以计算卸载为例，边缘设备能量有限，因而要避免能量在某一刻过度消耗，导致后续过程中任务请求失败，有效的办法便是在给定预算下，稳定单位时间内的能量消耗。消耗能量的步骤包括本地处理和数据传输，李雅普诺夫优化机制通过控制权衡本地处理和数据传输，维持能量消耗的稳定性。同样也可以建立时延队列，通过控制计算卸载力度来实现每个时隙任务执行的延迟程度，保证用户的QoE。