★中国科学技术大学 倪宏秋，谈海生

★华为云郑子木

1　边缘计算中的在线智能

随着大数据、IoT和人工智能等技术的蓬勃发展，网络边缘设备所产生的数据量开始快速增长，以云和数据中心为核心的集中式处理模式将无法快速处理边缘设备所产生的海量数据。在该背景下，传统的云计算场景中存在的实时性差、带宽受限制、无法保证数据安全和隐私以及能耗高等问题也变得越来越突出。因此，为了解决或缓解这些问题，更好地为用户提供服务，云计算的一个必然趋势是将计算资源靠近数据源与用户部署，就近提供低延迟、高安全、低成本云边端协同计算服务，这就是边缘计算。据预测，未来超过50%的数据需要在网络边缘侧计算和存储。

边缘计算在自动驾驶、工业制造、IoT等领域的应用场景复杂多样。同时，可以看到，在边缘计算的重要应用场景，如移动计算中，用户、计算任务、计算数据往往在线到达，这种在线到达的特点表现在它们的存在、到达的时间以及次序都是几乎不可预测的。此外，移动计算设备所处的网络环境与其能连接的边缘计算服务器的计算环境也随着时间和地点动态变化。而边缘计算应用场景的一个显著特点是低延迟要求。我们需要能够实时做出决策，并且这些决策方案必须尽可能简洁，以便能够轻松部署在异构且分布式的边缘节点上。这要求在处理动态到达的用户、任务和数据时，能够快速响应并执行相应的计算，以满足实时性和效率的要求。因此，在线模型和在线智能是边缘计算的固有需要。

2　边缘计算在线解决方案

近几年，本实验室团队一直致力于边缘计算的在线解决方案的设计、分析与实现，并通过深入研究和充分利用三种核心思路，取得了令人鼓舞的初步成果。

首先，本团队积极探索了基于在线近似算法的方法，以提供最差情况下的性能保证。这一思路涵盖了云边端协同在线任务分配和调度、在线协作存储、在线协流调度等关键领域。我们的研究成果包括云边端协同在线动态存储和云边端在线任务与数据流调度，为实现高效的在线边缘计算奠定了坚实的基础。

其次，本团队专注于基于在线深度增强学习的方法，以更好地利用现有数据资源。这一思路涉及高能效动态虚拟机管理、5G异构网络链路协同调度以及深度学习计算模型的调度等关键问题。本团队研究已经实现了计算与网络资源的在线管理、模型在线调度和计算优化，为提升边缘计算的效能提供了有力支持。

最后，本团队以在线博弈思维为指导，考虑了多方利益博弈。这一思路引领了团队在网络资源拥塞博弈、云边竞争在线定价以及多信道网络中的信道汇合策略等领域取得了重要突破。本团队已经开展了在线定价与博弈、网络资源拥塞博弈等研究，为构建更具竞争力和协同性的在线边缘计算环境提供了新的思路。

以下，本文将通过简要介绍边缘计算中云边端协同中的几个关键技术的代表性工作，向大家阐述相关模型、算法和实现。

3　协同计算

在边缘计算的背景下，计算卸载（即将工作负载从移动设备传输到边缘云）是云边端协同中的主要问题之一。在计算卸载问题中，需要决策用户设备卸载哪些任务、卸载的任务分配到何处以及服务器中每个任务按什么顺序执行等子问题。一个最佳的卸载解决方案必须合理利用异构资源，满足不同的用户需求，能处理复杂的网络环境，同时还需要考虑用户的移动性和任务的依赖性。计算卸载问题将直接影响用户端的服务质量，因此设计适合的计算卸载算法对边缘云与移动设备之间的有效协调至关重要。

移动设备到边缘云的计算卸载流程主要体现在3个部分，如图1所示，即移动设备、通信链路和边缘云。具体而言，移动设备负责划分应用程序，得到相应的卸载方案；通信链路负责上传分区的传输，主要受带宽、连接性和设备移动性的影响；边缘云的服务器负责平衡服务器负载，以实现最大的服务效率和系统吞吐量。

3.1　在线任务分配与调度模型

在计算卸载问题中，任务的分配和调度问题是至关重要的。

任务分配问题指的是：任务经过划分后，需要将任务从终端设备分配到边缘服务器。分配任务时，需要结合任务的计算成本、任务与服务器之间的传输成本、边缘服务器的情况等因素生成分配策略，按照分配策略将任务分配到最合适的边缘服务器上进行计算。

任务调度问题指的是：当一定数量的计算任务被卸载到边缘服务器或云服务器上后，需要设计服务器上的调度算法来决定任务队列中任务的计算顺序。另外，在满足更优化的成本的情况下，调度策略中存在将当前服务器上的任务迁移到其他服务器的可能。

在一个边缘计算系统中，由于任务以任意时间、次序在线到达，任务的信息在其到达前不可知；并且有若干异构边缘服务器，它们执行同一任务时间各异；同时，网络中也散布着诸多移动设备，移动端到服务器间的任务上传和下载的网络时延差异很大，更增加调度的不确定性。这些都为解决这一难题增添了挑战。

图1 边缘计算架构图

对此，文章定义了一个如下的在线任务分配与调度模型：首先在边缘云系统中，共有k个异构边缘云服务器，表示为K={s1,s2,...,sk}，每一个服务器对部分移动应用提供服务。其中，边缘云服务器集合K中包含距离较远，但是具有强大处理能力的远程云服务器。任务被表示为J={j1,j2,...}，其中，任务集J中的每一个任务都是原子性的和不可分割的。rj表示为任务j发布的时间，当任务发布后，终端设备就会将任务分配给边缘云服务器，并且当任务分配后，不会迁移到别的服务器上，由此，无须考虑任务迁移所带来的成本。当任务j分配到服务器s_k后，任务在服务器上的处理时间表示为p_kj。任务的响应时间指的是任务发布到任务完全结束之间的时间。对于任务j和服务器s_k之间，设定一个时延敏感度w_kj，如果任务无法被分配到服务器上，则设定w值为无穷大。加权响应时间指的是时延敏感度与响应时间的乘积。

3.2　在线任务分配与调度算法

为解决在线计算卸载问题，基于上述系统模型，以最小化总加权响应时间为目标，本实验室团队设计了一个在线的、考虑任务上传和下载时延的计算卸载问题的通用模型，并提出了第一个在线近似算法OnDisc算法，该算法研究了一种不需要考虑任务到达规律的在线任务分配与调度方案。

在调度策略上，OnDisc算法中的优化目标加权响应时间的权重由任务对时延的敏感度所决定。调度算法遵循着最高剩余密度优先的原则，该算法被称为最高剩余密度优先算法，可以避免服务器上的任务频繁切换。当所有任务都具有相同的权重w时，HRDF策略即等同于最短剩余时间优先策略。

在分配策略上，OnDisc基于贪婪的思想，根据加权延迟增量最小在线分配，期望使分配动作对总剩余加权密度的贡献最小。

OnDisc算法在速度增强模型中具有可扩展性，本团队证明了在速度增强模型下，OnDisc具有常数的竞争比。同时，本团队也基于Google集群数据（包含120,000个任务）进行了大规模模拟，证明了集中式或分布式OnDisc均能显著减少任务的平均响应时间。

可见，该提案模型非常通用化，算法设计简洁，易于分布式部署，具有良好的理论性能保证，并有基于真实数据。

4　协同存储

移动边缘缓存利用了边缘服务器提供的存储资源，是MEC的使用案例之一。边缘服务器附近的移动设备可以通过无线接入的方式访问边缘服务器。由于边缘服务器距离移动设备更近，移动设备可以将其任务或文件缓存在附近的边缘服务器上，这样不仅扩展了本地移动设备的能力，还能够避免远程服务器与缓存连接的网络节点之间的重复传输。而且，随着存储成本的降低，在无线边缘端部署缓存变得性价比更高。

在边缘计算场景中，多缓存问题是研究的重点。在边缘计算场景中的缓存问题中，给定一个由K个插槽（页）和一组文件组成的缓存。当请求在线到达，且所请求的文件在缓存中时，代价为0。否则，必须花费一定的获取代价将文件获取到缓存中。与远程云数据中心相比，边缘服务器的存储能力是有限的，因此只能在每个边缘服务器上部署部分文件，并且边缘服务器上的文件会以一定的策略进行更新，以便更好地服务在线请求。

4.1　支持关联及旁路的多缓存在线协作机制

在数据、服务在何处存储这个方向，本团队研究了支持关联及旁路的多缓存在线协作机制。

这个问题考虑这样一个场景：如图2中，有一组通过互联网连接的异构边缘服务器和远程云数据中心。开始时，每个边缘服务器都可以从远程云数据中心配置一些初始应用程序。对于到达边缘服务器s请求文件f的请求r，表示为r:=(s,f)。如果服务器s已经配置好了文件f，那么可以在本地为其提供服务并且无额外代价，如图中的请求r₁所示。如果应用程序不在服务器s上，那么可以选择将请求转发（Relay）到已经配置了文件f的附近的边缘服务器上进行处理，并需要花费转发代价，如图2中的请求r₂所示。也可以选择花费旁路（Bypass）代价执行旁路处理，直接绕过边缘服务器到远程云数据中心上，如图2中的请求r₃所示。此外，为了更好地服务后续请求，边缘服务器可能会从远程云数据中心获取（Fetch）某些特定的文件，并花费获取代价重新配置文件。如果服务器已经满了，还需要替换某些现有的文件以腾出空间，这时就需要去决定哪个文件f需要被存储以及应该何时被安装。基于这个问题，文章提出了Camul算法。

图2 移动边缘计算的典型示例

Camul算法是具有旁路和转发的多缓存上的渐近最优在线缓存算法。该算法将旁路、转发和获取成本全部考虑在内，在不牺牲命中率的情况下降低了总成本。它贪心地选择本地执行、关联或旁路，通过标记决策决定是否选择获取。本团队也基于Google数据集和Yahoo基准数据集进行了验证，证明了文章所提出的算法可以减少高达85%的访问开销。

4.2　支持延迟命中及旁路的在线缓存算法

在CDN和MEC等实际应用中，由于物理距离较长，从远程数据中心获取丢失文件的时延可能超过100ms，而两个连续文件请求的平均间隔时间可能低至1µs，例如，每秒有100万个文件请求。而在从远程数据中心检索丢失文件的期间，是无法立即处理该文件的后续请求的，因此不应该简单地将其视为命中。这种情况也不同于简单的未命中，因为在将文件获取到本地服务器后，请求可以作为命中。因此，我们称这种情况为延迟命中（Delayed Hit）。此外，传统的缓存模型假设所有丢失的文件在被访问之前都必须被获取并存储在本地缓存中，而在与云相关的应用程序场景中，文件请求可以直接发送到远程云，并在远程云提供服务，我们称之为旁路。

图3展示了基于云的系统中的在线文件缓存，其中有一个本地缓存服务器和多个远程数据中心，该系统具有文件未命中、命中、延迟命中和旁路的处理方式。X的第一个请求在T1到达，由于X未存储在缓存中，因此这是一次未命中，会从数据中心1获取X，并且由于获取延迟，X在时间T3之前不会在本地缓存中就绪。然后，对X的另一个请求在T2到达（T1<T2<T3），它将被放置在缓冲区并在T3服务，这是一个延迟命中。第3个X的请求在T3到达，这是一个命中。对于T4时到达的Y请求，我们选择直接旁路该请求，以避免缓存中的空间分配。

图3 CaLa算法示例

本提案也考虑了在延迟命中和旁路的情况下，设计合理的在线缓存算法，以最小化请求的平均响应时间。该问题的难点在于文件请求在线到达，文件之间的大小和获取延迟也可以任意，并且延迟命中的存在导致对一次文件未命中带来的损失难以估计。针对该问题，我们通过给每个文件设定未命中代价上界来确定文件权重，并调用支持权重的经典缓存模型，以处理文件大小和代价均不一致的情况。本团队证明了所设计的算法CaLa具有接近理论下界的竞争比，并且经过大规模实验验证，证明了CaLa相比当前最好算法可以减少32%的请求响应时间。

5　结束语

本文探讨了边缘计算领域中在线智能的重要性，旨在为读者提供一个深入了解的窗口。文章简要总结了边缘计算在线解决方案，并在之后的内容中更详细地介绍了本实验室团队在协同计算和协同存储方面的代表性成果。同时，如果您希望深入了解更多关于边缘计算、在线智能以及相关领域的知识，本团队专著《边缘计算理论与系统实践：基于CNCFKubeEdge的实现》可能会为您提供更多深入了解的机会。

作者简介：

倪宏秋（2000-），女，安徽人，博士生，现就读于中国科学技术大学计算机科学与技术学院，主要研究方向为边缘计算等。

谈海生（1981-），男，教授，博士生导师，现任教于中国科学技术大学，研究方向为网络算法与系统实现、边缘计算、工业互联网和AI Edge。

郑子木（1991-），男，广东人，主任工程师，博士，现就职于华为云，研究方向为边缘AI、多任务学习及AIoT。

摘自《自动化博览》2023年10月刊