1 简介

使用移动终端设备进行人脸识别，增强现实，语音识别等应用很普遍。他们共同面临的一个问题是这些应用都是高度时效性的，系统能够容忍的时延很小，这与它们普遍都是计算密集型产生冲突。最近出现的fog computing, cloudlets是该问题的一个解决方案。本文提出了另外一个解决方案，受到web cache的启发，将边缘与云作为一个cache模型。每个边缘服务器仅服务一个地理区域的终端设备。该解决方案对终端设备完全透明，即该技术不需要对终端设备作任何修改。

2 背景

图像识别通常分为三个步骤：提取要查询的图像的特征点，每个特征点对应一个用向量表示的特征子。对于每个待查询图像中的每个特征子，在所有训练图像的所有特征子中找到距离最近的一个。包含最多最近特征子的那个图像作为识别结果，当然，包含的特征子的数量要大于某个阈值。如果没有匹配特征子大于阈值的图像，则匹配失败。
关于orb特征提取与匹配：https://www.jianshu.com/p/420f8211d1cb
对于移动图像识别来说，上述过程都在云端执行，终端设备只负责上传图像，所以延迟可分为两部分：传输时延和计算时延。

Web Cache：
通过将部分网络内容放在距离用户比较近的边缘服务器上以降低用户的体感时延。
边缘计算：将图像识别比作一个web请求的过程，边缘设备负责提取图像的特征点和计算对应的特征子，将特征子传至云端进行匹配。

3 边缘缓存的理论分析

在边缘进行缓存的好处：一个边缘设备服务同一个区域内的终端设备，这些设备所获得的图像往往具有相似之处，它们查询的物体可能是相同的几个物体，通过缓存这些物体的特征，使得这些查询不需要提交给云端，可大大降低用户时延。
与Web Cache的不同之处：
Web Cache中查询一个请求(URI)是否命中所需要的计算量很小。图像识别中查询需要提取图像特征，通过预先训练好的模型找到对应物体，计算量较大。且模型的计算时间与cache的物体数量有关。cache越大，命中率当然越高，但命中时间也会提升，所以cache并不是越大越好。
此外，对于缺失率，即使要查询的图像中包含的物体在cache的模型里，cache也不一定能够识别出该物体，这取决于模型的精度。所以，命中率可以表示为：
P(recognized and cached) = P(recognized | cached) * P(cached)
通常P(recognized | cached)与cache大小有关，表示为recall(k)，其中k是cache模型能识别的物体数量，也就是cache大小，cache越大，模型出错的可能性就越高，recall(k)随k增大而降低。
图像识别中cache的延迟可表示为：
E(L) = f(k) + (1-recall(k)*P(cached)) * (Latency of Net + Latency of cloud)
k表示模型能识别的物体数量，反映了cache大小。
f(k)表示命中时间，随k增大而上升。
recall(k)P(cached)为命中率。
Latency of Net + Latency of cloud表示cache缺失时的时延。包括边缘到云的传输时延和云的计算时延。

4 Cachier设计

在每个边缘设备中加入一个cache大小控制模块，尽可能优化cache延迟，延迟的估计使用上述等式。

估计P(cached)：假定cache的淘汰策略为least frequently used item，P(cached)为出现频率前k个物体的出现频率之和。使用MAP(最大后验概率)，根据接收到的请求动态估计所有物体的出现概率以计算P(cached)。该步由图中的Distribution Estimator完成。
估计f(k)与recall(k)：通过离线的实验估计。对于不同的k，分别检测延迟与recall。
估计Latency of Net，Latency of cloud：通过观察缺失的样本延迟，在线实时估计。

5 进一步优化

• 估计物体出现频率时所使用的分布被记录在硬盘中，以便长期使用。
• 当发生一个缺失时，云端并不马上返回该缺失的图像对应物体的特征子，因为这些特征子可能存在于边缘设备中，只是没有在cache里而已，仅当边缘设备主动发出请求时云端才返回物体的特征子。
• 当发生一个缺失时，边缘设备将该查询图像的特征子发送给云端，同时将这些特征子记录在一个holding queue中，当另一个缺失发生且该查询图像的特征子与holding queue中的某些特征子表示同一个物体(如何判断？)，则不向云端发送该次查询。

6 实验

实验表明与没有cache相比，当查询图像分布呈现空间相关性时(某些图像出现频率明显高于其他图像，Zipf分布)，Cachier能够降低时延，且空间相关性越大(Zipf中的alpha越大)，延迟降低得越多。

7 未来的工作

• 可用在其他应用上，如语音识别。
• 当查询图像的分布发生剧烈变化时，Distribution Estimator不能快速响应这种变化。