0 概述

虚拟现实(Virtual Reality，VR)和增强现实(Augmented Reality，AR)技术能够帮助用户在各类应用中获得更好的体验，如医生利用VR技术可以重复地模拟手术以寻找最佳手术方案，消费者借助AR技术可以在商场中实时查看各类产品信息。VR任务中对用户视野的3D实时渲染以及AR任务中对真实场景的实时识别均为计算密集型任务，由于用户终端计算性能有限，因此需要在远程云服务器上完成此类任务。然而，移动终端和远程云服务器之间带宽有限且网络不稳定，当终端发起与远程云服务器之间的大量实时数据传输时，网络延时会对应用效果造成较大影响。

在5G时代，移动基站可以作为边缘云计算节点取代远程云服务器的部分功能。相较于远程云服务器，边缘云计算节点到用户终端物理距离更近。一方面，边缘云计算节点到用户终端具有更高的传输速度；另一方面，由于物理距离近，因此可以对某些特定场景下的应用做更细致的优化。例如，同一个VR场景中的多个用户所需要渲染的视野图像都来自同一个虚拟世界建模，为这几个用户渲染的图像往往存在冗余，文献[1]针对此类冗余进行了优化，显著提升了VR应用的实时响应性能。

在一些AR应用中同样也存在着类似的冗余。以AR导航为例，在一个边缘云计算节点附近的AR导航用户往往具有非常相似的周边环境，那么在AR识别过程中，多个导航用户对环境的识别任务就会存在冗余。因此，如何利用这样的冗余来减少边缘云节点的计算量，提升整体的用户体验，成为一个有待研究的问题。

本文介绍基于缓存的AR性能优化方法，包括任务请求处理、边缘节点组织和缓存管理等方面的优化。在此基础上，对可部署资源有限场景下优化用户时延的问题进行数学建模，进而针对中小规模和大规模场景分别提出IDM和LDM算法，并通过实验验证算法性能。

1 相关工作

本节介绍计算卸载、移动AR/VR应用、服务缓存放置和边缘计算资源管理等方面的相关工作。

在计算卸载方面，学者针对卸载内容、卸载时机、卸载方法等进行了大量研究^[2-4]。WANG等人将边缘节点网络抽象成一个图结构，研究对于给定的基站集合如何放置单独的边缘节点，从而使一个节点服务于多个基站，以尽可能地均衡负载并降低访问时延^[5]。本文将边缘节点网络抽象成一个自组织并定时同步的网络，关注当多个用户都卸载到同一个边缘云网络时可能存在冗余计算的问题。在此基础上，研究在原基站添加边缘节点功能的部署问题，在总部署代价有限的情况下，通过安排新增边缘节点的计算资源量以降低用户时延。

笔者着眼于边缘计算背景下移动AR应用的性能优化。在此之前，也有类似基于云计算的研究工作^[6]，例如：Glimpse通过缓存机制提升了识别准确率，使用触发帧选择的方法降低了无线传输时延^[7]；面向指纹识别设计的VisualPrint系统方案仅上传图像中最不同的特征，从而在低带宽的情况下对AR任务进行卸载^[8]。类似于AR，VR也是边缘计算的杀手级应用，在此方面，LI等人设计了MUVR系统，在多用户的边缘云上对3D渲染的冗余任务进行优化，提升了应用性能^[1]。本文根据AR和边缘计算节点的共同点做了进一步的优化：AR的环境识别与请求发出的位置密切相关，而被分配到的边缘计算节点往往也与请求发出的位置距离不远，因此，针对这样特定的环境，本文使用缓存来进行计算冗余消减，从而有效减少传输和计算开销。

当多个服务器在处理相似的内容时，使用缓存就可以避免不必要的重复处理。关于如何放置服务缓存的问题，之前的一些工作调研内容包括视频缓存到服务器的最优分配方案、减少数据传输量的最优缓存位置、在稠密蜂窝网络中的动态服务缓存等^[9-11]。本文研究在基站具有边缘计算能力的场景下如何部署计算缓存的边缘服务器和分配有限的资源，从而使用户获得时延更低的使用体验。

在边缘云中，资源管理对于服务质量和系统效率有着重要作用。目前，学者主要对资源分配和任务调度进行研究，包括均衡网络节点负载以优化应用性能、动态适应环境变化、基于层次架构的启发式负载分配算法、最小化总的加权服务响应时间的在线任务分配与调度算法等^[12-14]。考虑到直接为基站增加边缘计算功能可以避免单独部署边缘节点的较大开销，本文研究在可部署代价有限的情况下如何分配可部署的计算资源，从而使用户时延降到最低。

因为移动增强现实(Mobile AR，MAR)是在现实世界情境下应用的，所以快速准确的物体识别成为能够将虚拟世界与真实世界互相融合的关键环节^[15]。现有物体识别方法包括传统方法^[16-18]和基于深度卷积神经网络的方法^[19-20]。训练深度卷积神经网络是目前较为流行的方法，但是要达到一定的精度需要不小的计算代价。Chameleon系统通过多节点协作，在计算资源投入和物体识别精度上取得了很好的权衡^[19]。Focus系统通过使用简单的卷积神经网络构建近似索引，加快了对数据集的吸收和查询^[20]。本文关注AR识别请求与其物理位置之间的关系，以缓存的方式对物体识别进行加速。

2 问题描述

本节介绍基于缓存的冗余消减系统模型，对用户请求时延、用户轨迹预处理和节点部署做形式化表述，将问题聚焦于已知用户请求轨迹且部署总代价有限的情况下，如何为基站部署边缘节点的计算资源，以取得最低的平均时延，并证明此问题是NP-Complete的。

2.1 基于缓存的冗余消减 2.1.1 节点缓存

本文考虑在一个城市中多个部署边缘计算功能的基站协作进行AR识别的场景。当一个移动终端需要发起任务请求时，它会寻找距离自己最近的基站并将任务相关数据传送出去。基站收到这样的请求后，首先会检查相关数据是否已经被计算过。如果自己计算过，则直接返回计算结果；如果在其他节点计算过，则将请求重定向到缓存所在节点，由缓存所在节点返回计算结果；如果没有计算过，则在当前节点进行计算并把结果缓存在当前节点中，并通知所有其他节点。

为避免冗余计算，本文设置缓存为全局式的，即在整个城市中任意一个位置的请求都只会被计算一次。一次典型的基于缓存的AR任务执行过程如图 1所示。

2.1.2 全局缓存

要实现全局缓存，就需要全局节点通过一定方式保持同步。在本文构建的冗余消减模型中，全局节点自组织地形成一棵最小生成树(Minimum Spanning Tree，MST)，每个节点只需要和父子节点周期性地发送保活报文即可维持此结构的正常运行。当节点离开或失效时，其父子节点就可以检测到，子节点直接连接到失效节点的父节点上。若根节点失效，则从根节点的子节点中随机选取一个作为根节点。在每个节点中维护一张如表 1所示的缓存表，以保存符合某些特征的数据是否已经被计算过并缓存至所在的节点。节点接收到新的请求时，会先查询这张表以获取缓存信息。若没有缓存，节点经过计算生成新缓存之后，它会通知其父子节点递归地更新所有节点的缓存表，具体过程如图 2所示。

2.2 请求时延

由于信号随着距离增加而衰减，因此基站的服务范围通常情况下是一个以基站为圆心的圆。本文设基站的有效服务距离为$ r $，即在半径$ r $内的用户都可以接收到该基站的有效服务。同样地，位于基站覆盖范围内的用户在收发数据时也会受到距离的影响，考虑到坐标是一个多维信息，因此，用向量来表示用户与基站的位置，使用函数$ {\rm{dist}}(\boldsymbol{x}, \boldsymbol{y}) $来表示两个坐标向量x与y的距离。

AR识别任务往往是一个计算密集型任务，因此，一个边缘服务器所具有的CPU核心数、主频以及GPU时钟速度、内存总线容量等计算资源参数对于AR任务的效率起到重要作用。考虑到相关参数往往是整数，本文把计算资源抽象为一个正整数$ c $。

在AR识别请求中，输入的数据通常为图像视频信息。不同设备、不同用户在进行AR识别时分辨率和图像大小往往各不相同，因此，定义变量$ s $表示请求的数据量大小。

对于一个位置为y且计算资源量为$ c $的边缘服务器，当它收到一个来自位置x且数据量为$ s $的请求时，其请求时延可能出现以下两种情况：

1) 若请求数据已在服务器的缓存表中，则可以直接获取计算结果，此时用户时延包括数据传输时延与获取结果时延两部分。数据传输时延表示为$ \mu s \cdot {\rm{dist}}(\boldsymbol{x}, \boldsymbol{y}) $，时延与数据量、距离成正比，其中，$ \mu $为比例系数。获取结果时延定义为一个较小的常量$ \eta $，因为获取计算结果时，无论是返回本地结果还是返回其他服务器结果，开销都很小。

2) 若请求数据不在服务器的缓存表中，则节点需要先对请求数据进行处理并缓存，然后将缓存结果返回给用户，此过程的时延包括数据传输时延和数据处理时延。数据传输时延与上一种情况相同，为$ \mu s \cdot {\rm{dist}}(\boldsymbol{x}, \boldsymbol{y}) $。数据处理时延定义为$ \lambda \cdot \frac{s}{c} $，即处理时延与任务量成正比，与计算资源量成反比，其中，$ \lambda $为比例系数。

2.3 用户轨迹

对现有基站和云服务器的数据进行分析，得到AR用户的历史轨迹数据集$ U=\left\{X, S\right\} $，其中，X为所有请求的位置信息，$ X = \{ {\boldsymbol{x}_1}, {\boldsymbol{x}_2}, \cdots , {\boldsymbol{x}_n}\} $，S为所有请求的任务量，$ S=\{{s}_{1}, {s}_{2}, \cdots , {s}_{n}\} $。数据集包含$ n $个请求，按照时间先后顺序排序，第$ i $个请求的发出位置为$ {\boldsymbol{x}_i} $，数据量为$ {s}_{i} $。

此外，通过对历史AR用户识别任务数据进行分析，可以得到识别任务结果重用的相关信息。本文将相互之间可以重用识别结果的请求称为同一类别，从而可以得到$ \kappa \times n $的分类矩阵K，其中，总类别数为$ \kappa $，矩阵元素取值为：

$ {K_{ij}} = \left\{ \begin{array}{l} 1, 第 j个请求属于第 i个类别 \\ 0, 第 j个请求不属于第 i个类别 \end{array} \right. $

(1)

对于属于同一类别的识别请求，其识别目标往往是相同的，如同一个路口、同一家商店等，显然这样的请求属于且只会属于一个类别，即：

$ \sum\limits_{i = 1}^\kappa {{K_{ij}}} = 1{\rm{, }}\forall 1 \le j \le n $

(2)

对于每一个类别，系统会在最早的请求到来时计算一次，之后就可以直接返回缓存结果。考虑到每个类别第一次请求的特殊性，本文定义$ {g}_{i} $为第$ i $类中第一个到达的请求。而数据集按照时间先后顺序排序，因此，$ {g}_{i}=\underset{k:{K}_{ik}=1}{\mathrm{m}\mathrm{i}\mathrm{n}}k $，即第$ i $类中使得$ {K}_{ik}=1 $的$ k $最小者。

2.4 节点部署

根据收集到的用户轨迹信息，需要对边缘服务器节点部署位置进行决策。因为是在现有基站基础上新增功能，所以拥有候选基站位置集合$ L = \{ {\boldsymbol{l}_1}, {\boldsymbol{l}_2}, \cdots , {\boldsymbol{l}_m}\} $，并且可以认为这些基站覆盖了所有的请求位置，即对于任一请求位置，必定存在一个基站到它的距离小于等于$ r $，也即：

$ \mathop {{\rm{min}}}\limits_h \{ {\rm{dist}}({\boldsymbol{x}_j}, {\boldsymbol{l}_h})\} \le r, \forall {\boldsymbol{x}_j} \in X $

(3)

因此，需要决策的就是在各个节点上分配的计算资源量$ C=\{{c}_{1}, {c}_{2}, \cdots , {c}_{m}\} $($ \forall 1\le h\le m, {c}_{h}\in \mathbb{N} $，$ {c}_{i}=0 $表示此处不会部署边缘计算节点)。笔者希望在有限的部署代价之内尽可能提升用户体验，因此考虑了部署开销与用户时延。

部署开销指为每个候选基站要部署特定计算资源量所付出的代价。因为不同的基站位置不同，具体情况也不尽相同，所以用集合$ D=\{{d}_{1}, {d}_{2}, \cdots , {d}_{m}\} $ $ ({d}_{i}>0) $来表示在各基站部署单位计算资源所需代价，其中，$ {d}_{h} $表示在基站$ h $部署1个计算资源所需代价。为使部署开销处于可控范围内，设定：

$ \sum\limits_{h = 1}^m {{c_i}} {d_i} \le R $

(4)

其中，R为总部署代价上限。

2.5 总时延优化

请求平均时延应当尽可能地小，以提升用户体验。由于请求数量为常数，因此等价于让所有请求的总时延最小，本文将其定义为：

$ T = {T^{\rm{u}}} + {T^{\rm{c}}} $

(5)

其中，$ {T^{\rm{u}}} $为未命中缓存的总时延，$ {T^{\rm{c}}} $为命中缓存的总时延。

未命中缓存的总时延即$ K $中所有类别第一次计算耗时，因此，要对每个类别$ i $分别计算其第一次请求即$ {g}_{i} $的时延。当缓存未命中时，计算要在被请求的服务器本地完成，而被请求的服务器就是距离请求$ j $位置最近的部署了边缘服务器的基站，因此，基站序号为$ \mathop {{\rm{argmin}}}\limits_{h:{c_h} > 0} \{ {\rm{dist}}({\boldsymbol{x}_j}, {\boldsymbol{l}_h})\} $。根据2.2节，计算时延和数据传输时延分别可按照$ \lambda \cdot \frac{s}{c} $与$ \mu s \cdot {\rm{dist}}(\boldsymbol{x}, \boldsymbol{y}) $计算，如式(6)所示：

$ {T^{\rm{u}}} = \sum\limits_{i = 1}^\kappa {\sum\limits_{j:j = {g_i}} {\left( {\lambda \frac{{{s_j}}}{{{c_{\mathop {{\rm{argmin}}}\limits_{h:{c_h} > 0} \{ {\rm{dist}}({\boldsymbol{x}_j}, {\boldsymbol{l}_h})\} }}}} + \mu {s_j} \cdot \mathop {{\rm{min}}}\limits_{h:{c_h} > 0} {\rm{dist}}({\boldsymbol{x}_j}, {\boldsymbol{l}_h})} \right)} } $

(6)

命中缓存的总时延为同类别中第一次到达请求之后的请求时延之和，因此，需要计算各类别中所有序号大于$ {g}_{i} $的请求时延。根据2.2节，命中缓存的时延包括传输时延和获取结果时延，如式(7)所示：

$ {T^{\rm{c}}} = \sum\limits_{i = 1}^\kappa {\sum\limits_{j:{K_{ij}} = 1, j > {g_i}} {\left[ {\mu {s_j} \cdot \mathop {{\rm{min}}}\limits_{h:{c_h} > 0} \{ {\rm{dist}}({\boldsymbol{x}_j}, {\boldsymbol{l}_h})\} + \eta } \right]} } $

(7)

因此，所有请求总时延为：

$ T = \lambda \sum\limits_{i = 1}^\kappa {\frac{{{s_{{g_i}}}}}{{{c_{f\left( i \right)}}}}} + \mu \sum\limits_{j = 1}^n {{s_j}} \cdot \mathop {{\rm{min}}}\limits_{h:{c_h} > 0} \{ {\rm{dist}}({\boldsymbol{x}_j}, {\boldsymbol{l}_h})\} + \eta (n - \kappa ) $

(8)

本文的优化问题描述为问题1：

$ \begin{align} & \underset{C}{\mathop{\text{min}}}\, T \\ & \text{s}.\text{t}.\;\;\mathcal{C}1:\sum\limits_{h=1}^{m}{{{c}_{h}}}{{d}_{h}}\le R \\ & \;\;\;\;\;\;\;\;\mathcal{C}2:\underset{h:{{c}_{h}}>0}{\mathop{\text{min}}}\, \{\text{dist}({{\boldsymbol{x}}_{j}}, {{\boldsymbol{l}}_{h}})\}\le r, \forall {{\boldsymbol{x}}_{j}}\in X \\ & \;\;\;\;\;\;\;\;\mathcal{C}3:{{c}_{h}}\in \mathbb{N}, \forall 1\le h\le m \\ \end{align} $

(9)

其中，$ \mathcal{C}1 $表示有限的可部署资源，$ \mathcal{C}2 $表示每个请求位置附近距离$ r $内都存在一个边缘节点，从而确保所部署的边缘节点可以覆盖所有的请求位置，$ \mathcal{C}3 $表示可部署资源量为非负整数。

由于优化目标函数中的求最小值操作难度较大，因此本文考察原问题中的一种特殊情况，即所有基站均部署边缘节点的情况。修改优化问题$ 1 $的约束条件$ \mathcal{C}3 $，确保每个基站都有可用的计算资源，如式(10)所示：

$ \mathcal{C}3:{{c}_{h}}\in {{\mathbb{N}}_{+}}, \forall 1\le h\le m $

(10)

在此约束条件下，由2.4节所述，基站集合$ L $覆盖了所有请求，那么根据式(3)，约束条件$ \mathcal{C}2 $永远成立，同样地，$ f\left(i\right) $就变为与自变量$ C $无关的函数$ f\left( i \right)=\underset{h}{\mathop{\text{argmin}}}\, \{\text{dist}({{\boldsymbol{x}}_{{{g}_{i}}}}, {{\boldsymbol{l}}_{h}})\} $，则优化目标$ T $变为：

$ T=\lambda \sum\limits_{i=1}^{\kappa }{\frac{{{s}_{{{g}_{i}}}}}{{{c}_{f\left( i \right)}}}}+\mu \sum\limits_{j=1}^{n}{{{s}_{j}}}\cdot \underset{h}{\mathop{\text{min}}}\, \{\text{dist}({{\boldsymbol{x}}_{j}}, {{\boldsymbol{l}}_{h}})\}+\eta (n-\kappa ) $

(11)

式(11)中唯一与自变量$ C $相关的就是第1项，且只需决定$ {c}_{f\left(i\right)} $的取值。令$ {W_h} = \sum\limits_{i:f\left( i \right) = h} {{s_{{g_i}}}} $表示基站$ h $所收到的所有第一次请求任务量之和，$ F=\left\{f\right(i\left)\right|1\le i\le \kappa \} $表示所有类别中第一次到达的请求所指向的基站的集合，则对于不在集合$ F $中的基站$ h $确保$ {c}_{h}>0 $，这样即得到简化的优化问题，即问题2：

$ \begin{array}{*{35}{l}} \underset{C}{\mathop{\text{min}}}\, \sum\limits_{h\in F}{\frac{{{W}_{h}}}{{{c}_{h}}}} \\ \text{s}.\text{t}.\;\;\;\mathcal{C}1:\sum\limits_{h=1}^{m}{{{c}_{h}}}{{d}_{h}}\le R \\ \;\;\;\;\;\;\;\;\;\mathcal{C}3:{{c}_{h}}\in {{\mathbb{N}}_{+}}, \forall 1\le h\le m \\ \end{array} $

(12)

3 中小规模场景下的时延优化算法

针对一个城市，所研究的任务与位置密切结合的MAR应用场景往往局限于少数区域，如AR导航可能集中在一些特定的复杂路口或繁华的中心地带，AR商场购物可能集中在购物中心区域。在一个请求量较为稀疏的较小范围内，基站数量$ m $与最大代价$ R $都不至于太大，此时可以基于动态规划构造伪多项式算法求得问题$ 2 $的最优解，从而得到与问题$ 1 $最优解接近的解。

3.1 问题简化

根据上文分析，在从问题$ 1 $到问题$ 2 $的转化过程中，可以直接使所有基站都至少部署最低的计算资源量以简化优化目标函数，但需要对集合$ F $中的基站进行优化，所以，直接使不在$ F $中的所有基站计算资源量为最低即可，即令$ h\notin F $的$ {c}_{h} $为大于0的最小整数1，此处令：

$ {{c}_{h}}=1, \forall h\notin F $

(13)

设$ \left|F\right| $为$ F $集合中元素的个数，那么求解问题$ 2 $就只需要确定$ {c}_{h}(h\in F) $的值，上文定义了$ F=\left\{f\right(i\left)\right|1\le i\le \kappa \} $，但由于可能会有多个类别的第一次请求访问同一个基站，因此对$ F $中元素按照基站序号从小到大排序，得到$ F=\{{F}_{1}, {F}_{2}, \cdots , {F}_{\left|F\right|}\} $，$ {F}_{1}<{F}_{2}<\cdots <{F}_{\left|F\right|} $，那么$ {c}_{{F}_{u}} $就是基站$ {F}_{u} $所具有的计算资源量，$ {W}_{{F}_{u}} $就是基站$ {F}_{u} $接收到的所有第一次请求的任务总量。

由于分配给不在$ F $中的每个基站的计算资源量均为1，因此对于$ F $中基站的计算资源分配问题总的可付出代价就要从$ R $中去除，因此，新的可付出代价为$ {R}'=R-\sum\limits_{h\notin F}{{{d}_{h}}} $。

由此得到一个只需对$ {c}_{h}(h\in F) $进行决策的新问题，即问题3：

$ \begin{align} & \underset{C}{\mathop{\min }}\, \sum\limits_{u=1}^{\left| F \right|}{\frac{{{W}_{{{F}_{u}}}}}{{{c}_{{{F}_{u}}}}}} \\ & \text{s}\text{.t}\text{.}\;\; \mathcal{C}1:\sum\limits_{u=1}^{\left| F \right|}{{{c}_{{{F}_{u}}}}{{d}_{{{F}_{u}}}}\le {R}'} \\ & \;\;\;\;\;\;\mathcal{C}3:{{c}_{{{F}_{u}}}}\in {{\mathbb{N}}_{+}}, \forall 1\le u\le \left| F \right| \\ \end{align} $

(14)

其中，$ {W}_{{F}_{u}}>0, {d}_{{F}_{u}}>0, {R'}>0，\forall 1\le u\le \left|F\right| $。

3.2 最优子结构

观察发现问题$ 3 $具有最优子结构，即解为$ ({c}_{{F}_{1}}, {c}_{{F}_{2}}, \cdots , {c}_{{F}_{\left|F\right|}}) $，资源总量为$ {R'} $的问题$ 3 $的最优解可以由解为$ ({c}_{{F}_{1}}, {c}_{{F}_{2}}, \cdots , {c}_{{F}_{k}})(1\le k\le |F\left|\right) $资源总量为$ r(1\le r\le {R'}) $的规模更小的问题$ 3 $的最优解构造得到。本文用$ \left(\right|F|+1)\times ({R'}+1) $二维数组$ a $保存子问题的最优解($ {a}_{i, j} $表示解为$ ({c}_{{F}_{1}}, {c}_{{F}_{2}}, \cdots , {c}_{{F}_{i}}) $、资源总量为$ j $的子问题的最优解)，用二维数组$ p $保存子问题的最优解的值($ {p}_{i, j} $表示$ {a}_{i, j} $相应的最优解的值)。

对于$ {a}_{i, j} $与$ {p}_{i, j} $的子问题，可以将其理解为：有$ i $个基站分配总量为$ j $的资源，一个基站的资源量越大则其服务时延越低，本文目标是使它们的总服务时延最低，解$ ({c}_{{F}_{1}}, {c}_{{F}_{2}}, \cdots , {c}_{{F}_{i}}) $即为各基站资源的部署量。基于只有($ i-1 $)个基站的子问题，可以通过遍历所有可能的新加基站(即基站i)的数量，得到有$ i $个基站的问题的最优解，因此，有：

$ \begin{array}{l} {p_{i, j}} = \mathop {{\rm{min}}}\limits_{0 \le k{d_{{F_i}}} \le j} \left\{ {{p_{i - 1, j - k{d_{{F_i}}}}} + \frac{{{W_{{F_i}}}}}{k}} \right\}\\ 1 \le i \le \left| F \right|, 1 \le j \le R' \end{array} $

(15)

需要注意的是，所有的索引都从0开始计，$ {p}_{0, \cdot } $与$ {p}_{\cdot , 0} $、$ {a}_{0, \cdot } $与$ {a}_{\cdot , 0} $为特殊情况。此外，还约定当分母$ k=0 $时，$ \frac{{W}_{{F}_{i}}}{k}=0 $。

对于使式(18)取得最小值的$ k $，问题3的最优解可以直接通过在$ {a}_{i-1, j-k} $之后增加$ {c}_{j}=k $得到：

$ {a_{i, j}} = {a_{i - 1, j - k}} \cup \{ {c_j} = k\} , 1 \le i \le \left| F \right|, 1 \le j \le R' $

(16)

3.3 算法构造

问题3与普通非线性背包问题的不同之处在于，问题中除了决策变量以外，参数均为实数而非整数。但是对于中小规模的输入，可以通过将$ {d}_{{F}_{i}} $与$ {R'} $同乘以10、100或1 000再四舍五入取整得到一定精度的近似解。此过程不涉及算法核心问题，因此，算法设计中默认前述参数是已经通过相关操作取整过的参数。

本文通过设计动态规划算法IDM(Integral Delay Minimization)对上述问题进行求解，如算法1所示。首先对初始的特殊情况进行设置。对于$ m=0 $的子问题，问题$ 3 $中$ F $集合为空，解为空集，因此，目标函数值为0；对于$ m>0 $且$ R'=0 $的子问题，目标函数中每一项分母均为0，即此基站资源量为0，那么服务时延为$ \mathrm{\infty } $，故值初始化为$ \mathrm{\infty } $。然后按式(18)和式(19)所示的状态转移方程从小到大计算p的值，得到$ \left|F\right| $个解和资源量为$ {R'} $的问题$ 3 $最优解。最后对不在$ F $中基站的赋值，得到问题1的解。

算法1  IDM

输入  各基站位置集合L，各基站单位部署开销D，请求数据集$ U=\{X, S\} $，请求分类矩阵K，总部署代价上限$ R $

输出  计算资源分配方案$ C=\{{c}_{1}, {c}_{2}, \cdots , {c}_{m}\} $

计算各类别第一次请求序号$ {\mathrm{g}}_{\mathrm{i}}=\underset{\mathrm{k}:{\mathrm{K}}_{\mathrm{i}\mathrm{k}}=1}{\mathrm{m}\mathrm{i}\mathrm{n}}\mathrm{k}, \mathrm{ }\forall 1\le \mathrm{i}\le \mathrm{\kappa } $

构造最近可用基站查找函数$ \mathrm{f}\left(\mathrm{i}\right)=\underset{\mathrm{h}}{\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{i}\mathrm{n}}\left\{\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\right({\mathrm{x}}_{{\mathrm{g}}_{\mathrm{i}}}, {\mathrm{l}}_{\mathrm{h}}\left)\right\} $ $ (1\le \mathrm{i}\le \mathrm{\kappa }, {\mathrm{x}}_{{\mathrm{g}}_{\mathrm{i}}}\in \mathrm{X}) $

计算各基站第一次请求总任务量集合$ {{\rm{W}}_{\rm{h}}} = \sum\limits_{{\rm{i}}:{\rm{f}}\left( {\rm{i}} \right) = {\rm{h}}} {{{\rm{s}}_{{{\rm{g}}_{\rm{i}}}}}} , \forall 1 \le {\rm{h}} \le {\rm{m}}({{\rm{s}}_{{{\rm{g}}_{\rm{i}}}}} \in {\rm{S}}) $

构造第一次请求的基站集合$ \mathrm{F}=\left\{\mathrm{f}\left(\mathrm{i}\right)|1\le \mathrm{i}\le \mathrm{\kappa }\right\} $

对集合$ \mathrm{F} $中基站序号按照从小到大排序得到$ \mathrm{F}=\{{\mathrm{F}}_{1}, {\mathrm{F}}_{2}, \cdots , {\mathrm{F}}_{\left|\mathrm{F}\right|}\} $

计算动态规划问题的最大代价$ {\rm{R' = R - }}\sum\limits_{{\rm{h}} \notin {\rm{F}}} {{{\rm{d}}_{\rm{h}}}} $

构造$ \left(\right|\mathrm{F}|+1)\times ({\mathrm{R}}^{\mathrm{\text{'}}}+1) $的最优值二维数组$ \mathrm{p} $与最优解二维数组$ \mathrm{a} $

初始化$ {\mathrm{p}}_{0, \mathrm{j}}=0\mathrm{ }(\forall 0\le \mathrm{j}\le \mathrm{m}) $，$ {\mathrm{p}}_{\mathrm{i}, 0}=\mathrm{\infty }\mathrm{ }(\forall 1\le \mathrm{i}\le {\mathrm{R}}^{\mathrm{\text{'}}}) $

初始化$ {\mathrm{a}}_{0, \mathrm{j}}=\left\{\right\}\mathrm{ }(\forall 0\le \mathrm{j}\le \mathrm{m}) $

for i=1 to m do

for j=1 to $ \mathrm{R}\mathrm{\text{'}} $ do

$ {\rm{k}} = \mathop {{\rm{argmin}}}\limits_{0 \le {\rm{k}}{{\rm{d}}_{{{\rm{F}}_{\rm{i}}}}} \le {\rm{j}}} \left\{ {{{\rm{p}}_{{\rm{i}} - 1, {\rm{j}} - {\rm{k}}{{\rm{d}}_{{{\rm{F}}_{\rm{i}}}}}}} + \frac{{{{\rm{W}}_{{{\rm{F}}_{\rm{i}}}}}}}{{\rm{k}}}} \right\} $

$ {{\rm{p}}_{{\rm{i, j}}}} = {{\rm{p}}_{{\rm{i - 1, j - k}}{{\rm{d}}_{{{\rm{F}}_{\rm{i}}}}}}} + \frac{{{{\rm{W}}_{{{\rm{F}}_{\rm{i}}}}}}}{{\rm{k}}} $

$ {{\rm{a}}_{{\rm{i}}, {\rm{j}}}} = {{\rm{a}}_{{\rm{i}} - 1, {\rm{j}} - {\rm{k}}{{\rm{d}}_{{{\rm{F}}_{\rm{i}}}}}}} \cup \{ {{\rm{c}}_{\rm{j}}} = {\rm{k}}\} $

end for

end for

$ {\mathrm{a}}_{\mathrm{m}, {\mathrm{R}}^{\mathrm{\text{'}}}} $为问题$ 3 $的最优解

$ {\rm{C}} = {{\rm{a}}_{{\rm{m}}, {\rm{R'}}}} \cup \{ {{\rm{c}}_{\rm{h}}}{\rm{ = 1|h}} \notin {\rm{F}}, {\rm{1}} \le {\rm{h}} \le {\rm{m}}\} $

return $ \mathrm{C} $

3.4 时间复杂度分析

IDM算法的时间复杂度分析如下：计算$ {g}_{i} $复杂度为$ O\left(\kappa n\right) $，计算$ {W}_{h} $复杂度为$ O\left(\kappa m\right) $，构造集合$ F $复杂度为$ O\left(\kappa m\right) $，对集合$ F $进行排序复杂度为$ O\left(\kappa \mathrm{l}{\mathrm{b}}_{}\kappa \right) $，动态规划最大次数为$ O\left( {mR\sum\limits_{i = 1}^m {\frac{R}{{{d_{{F_i}}}}}} } \right) $。因此，IDM算法总时间复杂度为$ O\left( {\kappa n + \kappa m + \kappa {\rm{lb}}\;\kappa + mR\sum\limits_{i = 1}^m {\frac{R}{{{d_{{F_i}}}}}} } \right) \approx O\left( {\kappa n + mR\sum\limits_{i = 1}^m {\frac{R}{{{d_{{F_i}}}}}} } \right)$。由于IDM是一个伪多项式算法，因此该算法更适合在中小规模场景下求解。

4 大规模场景下的启发式算法

在一个用户终端密集、基站分布多的城市人流密集区域，数据集中的请求数量往往非常多，而基站数量也非常多，因此，总部署代价上限通常较高，这就导致动态规划算法会有很高的时间复杂度而不再适用，因此，本文研究大规模场景下的启发式算法。

4.1 大规模场景分析

大规模场景有如下特征：

1) 请求量大。小规模场景中请求稀疏，相应类别较少，而大规模场景中会存在很多用户在很多位置发起请求的情况，这也导致其具有请求类别多的特征。当请求数$ n $和类别数$ \kappa $较大时，算法1中为动态规划生成辅助变量过程中的时间复杂度$ O(\kappa n + \kappa m + \kappa {\rm{lb}}\;\kappa ) $就变得不可忽视。

2) 基站密集，代价上限高。在小规模场景下，由于请求不多，因此稀疏部署的基站足以满足用户需求。在大规模请求场景中，为保证用户体验的流畅性，往往会部署很多基站，而该区域总可用代价也会很高。IDM算法中动态规划的时间复杂度为$ O\left( {mR\sum\limits_{i = 1}^m {\frac{R}{{{d_{{F_i}}}}}} } \right) $，这在基站数$ m $和可用代价$ R $很大时是不可接受的。

因此，在大规模场景下，应选择在用户平均时延目标不降低太多的情况下时间复杂度较低的算法。经过观察可以发现，对于本文所研究的服务与位置紧密关联的AR识别任务，属于同一类别的任务往往是集中分布的，同类的任务集中在一个很小的区域中，而不同类的任务散布在整个区域中。IDM算法在寻找每个类别执行计算任务的基站时，对所有基站都进行了遍历，但实际上距离一个类别较远的基站基本上是不可能执行该类别的计算任务的，尤其是在大规模场景中，基站分布较为密集，一个类别的计算任务必然在其附近的基站执行。

根据以上分析可知，在寻找每个类别执行计算任务的基站时，并不需要遍历所有基站。同样地，在为每个基站决定其计算资源部署情况时，也并不需要遍历所有请求。那么，就可以把所有请求与基站按照空间分布进行切分，从而得到多个规模较小的子问题，对于每个子问题使用IDM算法求解后，再得到最终的解。

4.2 算法设计

考虑到子问题中的基站与请求应在空间上聚集在一起，因此本文通过聚类对原问题进行切分。因为数据规模较大且对聚类密度和层次没有特殊需求，所以本文选择具有线性时间复杂度的K-Means聚类算法。

通过构造启发式算法LDM(Large-scale Delay Minimization)来求解大规模场景下的问题，如算法2所示。对各个类别的请求计算它们的中心点，即同一类别所有请求位置坐标的均值，得到中心点集合$ A $。将中心点集合$ A $与基站集合$ L $取并集并使用K-Means聚类，得到具有ϕ个簇的聚类结果集合$ F $，其中每个簇$ {F}_{i} $包括该簇的请求集合$ {F}_{i}^{\mathrm{r}} $与该簇的基站集合$ {F}_{i}^{\mathrm{s}} $。据此，可以生成子问题的各基站位置集合$ {L'_i} $、各基站单位部署开销$ {D'_i} $、请求数据集$ {U'_i} $中的请求位置集合$ {X'_i} $、请求数据量集合$ {S'_i} $和请求分类矩阵$ {\boldsymbol{K'}_i} $。对于子问题的总部署代价上限$ {R'_i} $，直接按照当前簇的基站数量占全局基站数量的比例来分配，$ {R'_i}=\frac{\left|{F}_{i}^{\mathrm{s}}\right|}{m}R $。至此，$ \left( {{{L'}_i}, {{D'}_i}, {{U'}_i}, {{K'}_i}, {{R'}_i}} \right) $就形成了一个完整的子问题。

算法2  LDM

输入  各基站位置集合$ L $，各基站单位部署开销$ D $，请求数据集$ U=\{X, S\} $，请求分类矩阵K，总部署代价上限$ R $，聚类数量ϕ

输出  计算资源分配方案$ C=\{{c}_{1}, {c}_{2}, \cdots , {c}_{m}\} $

计算各类别中心点集合$ {\rm{A}} = \left\{ {{{\rm{a}}_{\rm{i}}} = \frac{{\sum\limits_{{\rm{j}}:{{\rm{K}}_{{\rm{ij}}}} = 1} {{{\rm{x}}_{\rm{j}}}} }}{{\sum\limits_{{\rm{j}} = 1}^{\rm{n}} {{{\rm{K}}_{{\rm{ij}}}}} }}|\forall 1 \le {\rm{i}} \le \kappa } \right\} $

对$ \mathrm{A}\bigcup \mathrm{L} $进行K-Means聚类，得到集合$ {\rm{F}} = \{ ({\rm{F}}_{\rm{i}}^{\rm{r}}, {\rm{F}}_{\rm{i}}^{\rm{s}})|1 \le {\rm{i}} \le \mathtt{ϕ} \} $。

初始化子问题集合$ \mathrm{P}=\mathrm{\varnothing } $

for all $ ({\mathrm{F}}_{\mathrm{i}}^{\mathrm{r}}, {\mathrm{F}}_{\mathrm{i}}^{\mathrm{s}})\in \mathrm{F} $ do

$ {{{\rm{L'}}}_{\rm{i}}}{\rm{, }}{{{\rm{D'}}}_{\rm{i}}}{\rm{, }}{{{\rm{U'}}}_{\rm{i}}} = \left\{ {{{{\rm{X'}}}_{\rm{i}}}{\rm{, }}{{{\rm{S'}}}_{\rm{i}}}} \right\}, {\rm{K'}} $ //根据$ {\mathrm{F}}_{\mathrm{i}}^{\mathrm{r}} $和$ {\mathrm{F}}_{\mathrm{i}}^{\mathrm{s}} $构造子问题

$ {\rm{R' = }}\frac{{\left| {{\rm{F}}_{\rm{i}}^{\rm{s}}} \right|}}{{\rm{m}}}{\rm{R}} $

$ {\rm{P}} = {\rm{P}} \cup \left\{ {\left( {{{{\rm{L'}}}_{\rm{i}}}{\rm{, }}{{{\rm{D'}}}_{\rm{i}}}{\rm{, }}{{{\rm{U'}}}_{\rm{i}}}{\rm{, }}{{{\rm{K'}}}_{\rm{i}}}{\rm{, }}{{{\rm{R'}}}_{\rm{i}}}} \right)} \right\} $

end for

for all $ {{\rm{P}}_{\rm{i}}} = \left( {{{{\rm{L'}}}_{\rm{i}}}{\rm{, }}{{{\rm{D'}}}_{\rm{i}}}{\rm{, }}{{{\rm{U'}}}_{\rm{i}}}{\rm{, }}{{{\rm{K'}}}_{\rm{i}}}{\rm{, }}{{{\rm{R'}}}_{\rm{i}}}} \right) \in {\rm{P}}\;{\rm{do}} $

if $ {{{{\rm{L'}}}_{\rm{i}}}} $不能覆盖请求集合$ {{{\rm{X'}}}_{\rm{i}}} $ then

将$ {\mathrm{P}}_{\mathrm{i}} $与其附近的基站进行合并

end if

end for

初始化子问题解的集合$ \mathrm{C}=\mathrm{\varnothing } $

for all P_i∈P do

使用IDM算法(算法1)求解P_i得到C_i

end for

$ {\rm{C}} = \bigcup\limits_{{\rm{i}} = 1}^{\left| {\rm{C}} \right|} {{{\rm{C}}_{\rm{i}}}} $

return $ \mathrm{C} $

上文2.4节中提到，在解原问题的时候有一个最基础的假设——所有基站应该能够覆盖所有的请求位置。如果切分得到的子问题不能满足这一条件，那么就无法使用IDM算法对子问题进行求解。因此，在得到子问题集合$ \mathcal{P} $之后，对各子问题进行检查，若存在基站不能覆盖所有请求的子问题，那么就对那些没有服务基站的请求进行搜索，查找距离它们最近的基站，将最近的基站所在子问题与当前子问题合并成为一个子问题。若被合并的子问题也不能满足覆盖条件，则递归地合并，直到满足覆盖条件为止。

经过覆盖条件检查与合并，对新的子问题可以分别使用IDM算法求解。由于子问题之间相互独立，因此可以并行化完成求解这一过程，从而进一步加快本文算法的运行速度。子问题的解$ \mathcal{C}_i $就是子问题$ \mathcal{P}_i $内部对它们基站资源分配量的赋值，经合并即为最终对全局基站的赋值C。

4.3 时间复杂度分析

假设大规模场景中基站、请求都是均匀分布的，那么平均每个子问题的基站数量、请求数量都是原问题的$ \frac{1}{\phi } $。据此分析如下：计算各类别中心点集合为$ O\left(n\right) $，K-Means聚类的时间复杂度为$ O(\kappa +m) $，构造子问题复杂度为$ O(n+m) $。检查子问题覆盖条件整体时间复杂度为$ O\left(\xi n\right) $，其中，$ \xi $为较小的常数。合并不满足覆盖条件的子问题为常数$ O\left(1\right) $。求解单个子问题时间复杂度为$ O\left( {\frac{{\kappa n}}{{{\phi ^2}}} + \frac{{\kappa m}}{{{\phi ^2}}} + \frac{\kappa }{\phi }lb\frac{\kappa }{\phi } + \frac{{mR}}{{{\phi ^2}}} \times } \right.\left. {\sum\limits_{i = 1}^{m/\phi } {\frac{R}{{\phi {d_{{F_i}}}}}} } \right) $，则ϕ个子问题总的时间复杂度为$ O\left( {\frac{{\kappa n}}{\phi } + } \right.\frac{{\kappa m}}{\phi } + \left. {\kappa {\rm{lb}}\frac{\kappa }{\phi } + \frac{{mR}}{{{\phi ^2}}}\sum\limits_{i = 1}^{m/\phi } {\frac{R}{{{d_{{F_i}}}}}} } \right) $。综上分析，顺序执行LDM的时间复杂度为$ O\left( {n + \kappa + m + \frac{{\kappa n}}{\phi } + \frac{{\kappa m}}{\phi } + \kappa {\rm{lb}}\frac{\kappa }{\phi } + \frac{{mR}}{{{\phi ^2}}}} \right.\left. {\sum\limits_{i = 1}^{m/\phi } {\frac{R}{{{d_{{F_i}}}}}} } \right) \approx O\left( {\frac{{\kappa n}}{\phi } + \frac{{mR}}{{{\phi ^2}}}\sum\limits_{i = 1}^{m/\phi } {\frac{R}{{{d_{{F_i}}}}}} } \right) $，相比于IDM的$ O(\kappa n + mR\sum\limits_{i = 1}^m {\frac{R}{{{d_{{F_i}}}}}} ) $，本文通过线性时间复杂度的操作，使得IDM的辅助参数计算部分效率提高了ϕ倍，动态规划部分效率提高了ϕ²倍以上。

5 实验与结果分析

本节分别模拟中小规模场景和大规模场景，对IDM算法和LDM算法进行实验分析，并使用直接均分和数值优化两种方法作为对比。直接均分法令所有$ m $个基站$ {c}_{h}{d}_{h}=\frac{R}{m} $，把总代价上限均分为$ m $份，这样基站$ h $的计算资源量为$ {c_h} = \left\lfloor {\frac{R}{{m{d_h}}}} \right\rfloor $，因为解必须为整数，所以此处进行了下取整。数值优化法通过数值方法迭代逼近原问题的最优解，但是无法得到整数解，可以一定程度上代表此问题的最优解。

5.1 实验设置

本节从研究场景和缓存模型两方面介绍模拟实验中的背景设置和相关参数。

5.1.1 研究场景

本文研究500 m$ \times $500 m的矩形区域，以坐标(0，0)为左下角，以坐标(500，500)为右上角。该区域中已部署基站，每个基站的有效服务半径为100 m。在区域中随机产生AR识别任务请求，任务可重用者为同一类别。因为同一类别往往产生位置相近，所以同一类别的请求坐标在区域中呈现标准差较小的高斯分布，这样同一类的请求就会在高斯分布的中心点附近集中分布，符合实际场景。此处设置标准差$ \sigma =5 $。不同类别的中心点在区域中均匀分布。考虑到实际场景中交付云计算的数据往往是图像，因此，设置随机生成的请求数据量范围为[1 MB，10 MB]，以表示图像的大小。在3.3节IDM算法设计中提到，在执行IDM算法之前应当对基站部署单位计算资源的开销进行四舍五入取整，因此，本文设置每个基站部署1个计算资源的开销为整数，在[1, 10]之间均匀分布。

5.1.2 缓存模型

对于本文的缓存模型：设置计算时延参数$ \lambda =500 $，即在具有1个计算资源的边缘服务器上计算1 MB的数据需要500 ms；设置传输时延参数$ \mu =1 $，即在距离基站1 m的位置向基站传输1 MB的数据耗时为1 ms；设置缓存命中后获取结果参数$ \eta =3 $，即当请求数据的计算结果已在缓存中时，基站从收到数据，到用户获取到计算结果耗时为3 ms。

5.2 中小规模场景下的实验结果

本节按照中小规模的场景对IDM算法进行实验测试。在此场景下，基站足以覆盖研究区域的大部分地区，但是较为稀疏，因此，设置基站数量为30个且在研究区域中均匀分布。由于场景中请求不会太密集，因此设置请求数量为500个。此外，由于各个类别的请求数量往往不相同，但单个类别的请求不会太多，因此设置每个类别的请求数量在[1, 10]之间均匀分布。部署的总代价上限为500。本文将以此为基础，改变一些变量观察算法性能。

首先研究请求数量对于平均时延的影响，如图 3所示。当请求数量较少时，请求可能集中地被少数基站处理，因此，直接均分会使很多不需要执行任务的基站分配到较多的资源，导致需要计算的基站资源减少，从而增加时延。之后随着请求数量提升，请求分布更趋均匀，基站的任务分配也更均衡，所以，时延会有下降趋势。IDM算法的平均时延始终与数值最优的平均时延非常相近，保持在常数级的差别，由此可以看出IDM算法对最优的逼近效果较好，对于请求数量的变化表现也很稳定。

在部署计算资源过程中，总代价上限会对整体系统性能造成较大影响。如图 4所示，随着总代价上限的提升，3种方法的平均时延均有所下降，而且不同部署策略之间的差异也会不断减小。这是因为当总代价上限提升时，各基站的计算资源逐渐充裕，由此部署策略对于总时延的影响也会减弱。可以看出，IDM算法从最开始的与数值最优略有差距，直到总代价上限为900时差距几乎消失，整个过程中两者的差距始终很小。

5.3 大规模场景下的实验结果

本节对大规模场景进行模拟，测试LDM算法的时延优化能力和执行时间。在1 000 m×1 000 m的矩形区域内进行研究。大规模场景中基站往往较为密集，所以将基站数量增加到了300个，是中小规模场景的10倍，仍然均匀分布在研究区域中。大规模场景中请求数量也会很多，因此，设置请求数量为5 000个。请求增多会带来类别的增加，但是每个类别中请求的数量往往不会有太多变化，因此，仍然设置每个类别的请求数量在[1, 10]之间均匀分布。由于请求数很多，部署资源时的总代价上限也随之提升，本文设置为5 000。此外，LDM算法本身有一个超参数ϕ用于调节子问题数量，设置为10。本文将以此为基础，变化一些参数观察算法性能。

考虑到请求数量是大规模场景中最重要的影响因素，因此本文研究在请求数量达到2 000以上的情况下，随着请求数量增加各部署算法平均时延的变化情况，如图 5所示。可以看出：直接均分法的平均时延上升极为缓慢，基本不变；LDM算法、IDM算法与数值最优的平均时延都在缓慢上升，增长也越来越缓慢；当请求数量越来越多时，LDM算法与数值最优的差距越来越小，不断逼近；在整个过程中，LDM算法的平均时延都与数值最优相差不多。由此可见，LDM算法更适用于存在大量请求的环境。

LDM算法虽然平均时延略高于IDM算法，但是算法运行时间远低于IDM算法。在大规模场景下，IDM算法处理5 000个请求的平均时延为1 852 ms，运行时间为384 s，而LDM算法完成同样的任务平均时延为1 696 ms，运行算法却只需7 s，其速度是IDM算法的54倍，而平均时延却只增加了9%，这无疑是值得的。如图 6所示：随着请求数量的增加，IDM算法运行时间显著增加，而LDM算法的运行时间却始终保持在非常低的水平。由此可见，LDM算法对于大规模密集场景牺牲了少量的平均时延优化效果，却带来了大幅的运行时间缩减。

6 结束语

本文以边缘计算为背景，研究基于冗余任务消减的AR性能优化方法，针对AR任务的冗余性，设计冗余消减的系统结构，包括节点本地缓存生成与管理、全局缓存同步等。以现有缓存系统为基础，对如何为基站部署边缘服务器的计算资源以最优化平均用户时延的问题进行建模，并借助动态规划的思想设计求解整数问题的IDM算法。中小规模场景下的实验结果表明，IDM的平均时延只比实数最优解增加5.85%。此外，对大规模场景进行分析，并借助分而治之的思想，使用K-Means聚类将原问题切分成多个子问题用LDM进行分别求解，以加快算法运行速度。实验结果表明，相比于IDM算法，LDM算法在平均时延只增加9.20%的情况下，运行时间下降了98.15%。下一步将以更准确的真实场景建模和online任务调度为出发点对本文算法进行优化。