Delay-Optimal Distributed Edge Computing in Wireless Edge Networks
Howard Yin 2021-01-17 06:14:01 论文笔记边缘计算分布式计算贪心算法
@inproceedings{gongDelayOptimalDistributedEdge2020,
title = {Delay-{{Optimal Distributed Edge Computing}} in {{Wireless Edge Networks}}},
booktitle = {{{IEEE INFOCOM}} 2020 - {{IEEE Conference}} on {{Computer Communications}}},
author = {Gong, Xiaowen},
year = {2020},
month = jul,
pages = {2629--2638},
publisher = {{IEEE}},
address = {{Toronto, ON, Canada}},
doi = {10.1109/INFOCOM41043.2020.9155272},
isbn = {978-1-72816-412-0},
language = {en}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
2
3
4
5
6
7
8
9
10
11
12
13
# 要解决的问题
使用无线连接的边缘计算设备执行分布式并行计算，最小化执行分布式算法的延迟
- computation allocation：将分布式算法的工作负载分配到边缘设备，优化分配方案
- communication scheduling：优化设备间通信的规划方案
- 无线通信有干扰（在本文中指的是一条无线信道内同一时刻智能有一个设备在发消息）
- 不同无线设备数据率不同
- 选择运行分布式算法的设备，优化选择方案
# 主要贡献
- 提出了一种基于无线连接设备的分布式并行计算框架，并在此框架下建模研究了边缘设备的computation allocation和communication scheduling问题
- 本文的研究过程为优化计算-通信协同设计提供了一些有用的见解
- 用模拟验证了算法的性能
# 相关研究和不足点
- 边缘计算考虑了任务卸载到一个边缘服务器的情况而没有考虑卸载到多个边缘设备的情况
- 边缘计算在低延迟视频服务中的应用（视频推理、VR/AR）
- 设备将计算任务卸载到边缘服务器
- 边缘缓存
- 学习推断用户需要的内容缓存之
- 边缘服务器合作缓存网络
- 分布式计算没有考虑分布式设备连接不稳定的情况，许多研究都没有考虑任务卸载到多个设备时的调度问题
- 网络对计算的影响
- 执行分布式计算的网络吞吐量
- 网络和计算联合设计以提高吞吐量或减小延迟
- 在某些分布式计算框架下的并流调度
- 无线网络调度：很少有对延迟性能方面的研究
- 大多数研究关注无线网络的吞吐量
- 许多研究关注无线网络的the total utility of data flows in the network which depends on the throughput
# 系统建模
最小化执行分布式算法的延迟
# 计算
# 基本概念
- 分布式算法：一个算法能被拆解成许多独立的部分，互相独立地运行，最后汇总得到结果
- 计算：获取一些数据作为输入，基于输入数据执行一些指令，最后产生一些数据作为输出
- 不可分布式执行的计算：将其他计算的输出作为输入（或其输出用于其他计算的输入）的计算
# 建模
- 假定有一系列分布式计算设备组成的集合N，i∈N是其中的一个设备
- 假定一个可以被分割成分布式计算过程的算法的总计算量为w，它可以分割成一系列计算量wi,i∈N，∑i∈Nwi=w
- 一个分布式计算的执行过程包括：
- computation0：分割分配，i=0表示用于分割分配计算量的设备
- computationi,i∈N：分布式执行
- computationN+1：汇总，i=N+1表示用于汇总结果的设备
- 假定最开始的分割分配过程和最后的汇总过程计算量为0：w0=wN+1=0
# 通信
# 基本概念
- 通信：将上一个计算的结果交给下一个计算作为输入的过程
- forward communications：将分割后的各部分计算（computation0的输出）传输到各分布式计算设备上执行（computationi,i∈N的输入）
- backward communications：将各分布式计算设备上的输出传输到computationN+1作为输入进行汇总
# 建模
- 假定计算量和通信量互相独立，互不影响
- 所有分布式设备的信道均是无线连接
- 只有没有互相干扰的信道才能同时传输数据
- 只考虑单跳无线连接的情况，每个边缘设备都能通过无线直连其他设备
- 网络受到完全干扰的约束：同一时刻智能有一个节点在传输数据
- 计算速率和传输速率已知（在执行算法前预先估计），进而计算延迟和传输延迟已知
- 无线通信有一个统一的中心控制器协调（比如无线AP），因此没有抢占和干扰
# 优化目标：算法延迟
- 算法延迟：在满足限制条件的情况下执行分布式算法中的计算和传输过程所耗费的总时间
- 优化目标：优化边缘节点i∈N上的计算负载的分配方法wi,i∈N，并规划节点间的无线通信方案，以最小化算法延迟
# 求解
- 研究最优通信调度的结构特性
- 研究任意通信调度算法上的最优计算负载分配方式
- 在上一步研究的基础上反过来评价通信调度算法
# 最优通信调度的结构特性
- 网络可以打断任何一个通信过程转而执行其他通信过程
# 最优通信调度方法必要条件
- 非抢占式
- 打断传输抢占信道不会改变传完信息的时间
- 本文的优化目标（算法的延迟）使得优化结果依赖于最长的的那条信号的传输时间
- 让所有的forward communications在全部backward communications之前完成的通信调度方法是最优的
- 这么做给执行计算的过程留了更多时间
- forward communications过程和backward communications过程之间最好没有空闲
- 显而易见，同时只有一个设备能发消息，所有设备消息传完即算法结束，因此数据传输总量一定，越空闲最后的传输时间越长
- 计算时间很长时forward communications过程和backward communications过程间的空闲不可避免
# 最优的计算量分配算法
- 尽可能多地往工作节点分配计算量，使计算都能在最后一个forward communication结束前完成
- 最后一个forward communication结束时若还有计算没有分配完，那就尽可能多地往工作节点分配计算量，使得计算都能在第一个backward communication开始前完成
- 最后一个forward communication结束时若还有计算没有分配完，那就尽可能多地往工作节点分配计算量，使得计算都能在第一个backward communication开始后完成
（算法不能理解，感觉像是贪心？）
# 最优的通信分配算法
定义和条件：
- 节点所处理的总的计算量=发完forward communication后到开始发送backward communication之间的时间×节点算力
- 所有任务的计算量相同
最优的通信分配算法的优化问题可转化为：
规划backward communications使得在第一个backward communication开始前系统所处理的总的计算量达到最大（为什么？然后再按照计算时间反推forward communications的时间规划？）
# 节点的算力相同，通信延迟不同
如果所有节点的算力相同，通信延迟不同，那就按照通信延迟降序规划backward communications过程
- 延迟长的先发backward communication，延迟短的后发backward communication
- 理解：
- 节点的算力相同时，要尽可能地提升计算时间
- 一个节点在发backward communication时，其他没发backward communication的节点的时间都算在计算时间里面
- 节点发完backward communication之后就不算计算时间了
- 所以要尽量让节点慢一点发完backward communication
- 因此让backward communication时间长的节点先发，以让尽可能多的节点在尽可能长的时间算入计算时间
# 节点的通信延迟相同，算力不同
如果所有节点的通信延迟相同，算力不同，那就按照算力升序规划backward communications过程
- 算力小的先发backward communication，算力大的后发backward communication
- 理解：
- 原理同上一节相同
- 让算力大的节点尽可能多的计入计算时间
# 节点的通信延迟不同，算力不同
精确算法是遍历所有可能的backward communication规划方案，此遍历过程本质是遍历工作节点的所有排列顺序，时间复杂度O(n!)。
本文提出了一个基于贪心的近似算法，有点复杂，先搁置。
# 最优的节点选择算法
显然，应该有优先选择算力大的和延迟小的节点执行任务（这个显然在文中分析的很详细）：
- 节点的算力相同，通信延迟不同时，优先选通信延迟小的执行任务
- 节点的通信延迟相同，算力不同时，优先选算力大的执行任务
当节点的通信延迟和算力都不同时，要遍历所有选择方案时间复杂度为O(2N)。本文提出了一个基于贪婪的选择方法：
- 一个空集
- 每次都从未选择的节点里面选一个最能降低算法延迟的节点放入 （什么意思？何谓之“最能降低算法延迟”？）
- 直到没有这样的节点存在
We will analyze the performance of this algorithm in terms of its approximation ratio in our future work.
# 思考
本文所设定的场景非常完美：
- 本文所构建的系统结构非常简单：
- 所有子任务的计算量相同
- 无线信道只有一个（正常情况确实如此）
- 无线连接没有断线和失败的情况（本文距离考虑这个问题还很远）
- 无线设备通信速率恒定不变（网络信号很好，设备也不移动）
- 本文所构建的系统结构具有上帝视角：
- 所有无线设备的通信延迟已知（可由协议探测估计得到）
- 所有无线设备的算力已知
- 所有任务的计算量已知
- 所有任务在所有无线设备上的运行时间已知
最后使得这个问题变成了一个简单的对一堆时间片的规划问题，直接用贪心求近似解就行了，非常符合奥卡姆剃刀原则，在此场景下构建的算法也足够简单，甚至不需要公式推导，还有很强的普适性
从工程角度看本文所构建的系统：
- 本文所考虑的体系并不是“云计算中心-边缘服务器-终端”这样的结构，而是“请求方-控制节点-工作节点”这样的结构
- 这种结构最典型的应用就是在数据量大到一个机器内存不下的情况下进行数据分析（如MapReduce大数据分析）
- 只有在传输数据耗时比计算耗时小很多的时候这种计算方式才有用武之地（少量数据大量计算）
- 本文很适合物联网领域，尤其是有大量数据存在大量边缘端、而中心节点需要查询聚合的场景。在这种场景下，所谓“边缘端”可能是许许多多的有较强存储能力的终端设备或传感器，由于边缘计算中减少网络流量的考虑，它们在收集到数据后不会立即发送到云端，而是建立本地数据库，当云端需要数据时再查询和发送。
| 结构 | 云计算中心-边缘服务器-终端用户 | 云计算中心-控制节点-工作节点 |
|---|---|---|
| 云端 | 云计算中心 | 云计算中心 |
| 边缘端 | 边缘服务器 | 控制节点+工作节点 |
| 终端 | 终端用户 | 无 |
| 服务请求发起方 | 终端用户 | 云计算中心 |
| 服务请求处理方 | 云计算中心或边缘服务器 | 控制节点和工作节点 |
| 主要数据存储位置 | 云计算中心 | 工作节点 |
| 数据流向 | 1个请求↓1个终端用户 1个请求↓1个边缘服务器 1个响应↓1个云计算中心 1个响应↓1个边缘服务器 1个响应↓1个终端用户 | 1个请求↓1个云计算中心 M个请求↓M个控制节点 N个结果↓N个工作节点 M个汇总结果↓M个控制节点 1个汇总结果↓1个云计算中心 |
- 基于无线连接边缘设备的研究在“云计算中心-边缘服务器-终端”的网络结构下没有用武之地
- 用本文所讲的无线方式连接那些用于提供服务的边缘服务器，感觉可以但没必要。不是移动设备、没有多跳、还不考虑能源问题（表明至少有电线供能），那直接在电源线旁边加条网线和路由组成LAN就好，没必要用无线这种本来就有很多麻烦问题的手段进行连接。
感觉还行：
- 没有感觉还行的研究方向，感觉往哪深入都与本文的研究方向很远
感觉不太行：
- 网络传输速率不断波动的情况？
- 没有上帝视角的情况？
- 无线设备多跳连接的情况？
- 计算速率不能确定的情况？设备经常增减的情况？
- 任务的计算量如何确定？