关于“资源分配”的知识储备

---

异构网络

• 定义
  异构网络(Heterogeneous Network）是一种类型的网络，其是由不同制造商生产的计算机，网络设备和系统组成的，大部分情况下运行在不同的协议上支持不同的功能或应用。
• 举例说明
  连接Win系统电脑，Linux系统电脑和ios系统电脑的局域网络便是异构网络

---

系统异构和异构统计

• 系统异构：指的是由于硬件、网络连接、功耗等方面的差异，各参与方在存储、计算能力、通信性能等方面存在差异。
• 统计异构：指的是客户端生成和收集的非独立同分布（non-IID）数据

用户调度

• 在传统的蜂窝通信中，用户调度是用于解决上行资源短缺的有效方法，主要有轮询调度、比例公平调度以及随机调度等。
• 在无线分布式学习系统中，考虑到上行通信资源有限，用户调度也可以用来缓解模型参数上传带来的通信压力，即在每一轮模型训练中，只选择部分终端参与模型汇聚。

---

联邦学习

• 联邦学习指的是将训练数据保存在智能终端，通过终端之间的协作来训练一个共享的机器学习模型。
• 联邦学习允许客户端基于本地数据训练模型，并将模型更新的部分上传到中央服务器进行聚合，避免了海量原始数据的传输，有效保护了用户隐私。
  参考：《Machine Learning for Wireless Communication: An Overview》

---

深度学习模型部署

• 深度学习项目开发流程可以大致总结为三个步骤: 模型离线训练、模型优化压缩和模型部署/SDK输出 (对应下面的offline过程)

  参考： 训练好的深度学习模型是怎么部署的

• 现阶段 app 上使用的深度学习主要有两种模式：

  1. Online 方式
  • 定义：首先在移动端做初步预处理，然后把数据传到服务器进行预测后返回移动端。
  • 优点：部署相对简单，现成的框架（tensorflow, pytorch, keras, caffe，theano，mxnet) 做下封装就可以直接拿来用；使用服务器进行计算，性能强，能够处理比较大的模型
  • 缺点：必须使用网络，而且展示效果依赖网速，不适合实时性要求高的应用。
    
  2. Offline 方式

  • 定义：根据硬件的性能选择模型，在服务器训练得到模型，在手机上进行预测的过程。[服务器上训练的模型怎么传到手机端呢，涉及诸多通信资源分配问题]

  • 优点：不需要使用网络，可以保护隐私

  • 缺点：计算的性能、耗时等取决于移动端的性能，有些模型只能使用CPU，精度可能会有影响，无法进行类似云端的大规模分布式训练；移动端部署相对较麻烦，需要针对移动端进行优化；大模型耗费大量的资源（计算、内存、存储、电）。

  参考： 智云视图的回答

---

“传统资源分配”和“基于DL的资源分配”

• 传统资源分配

    对于传统的资源分配，通常是在有限通信资源（频谱、能源等）下进行建模的，目的皆在提高系统性能，例如最大化吞吐量或最小化干扰。通常情况下，通过数学规划处理这些优化问题。然而，很多情况下，我们没有精确的系统模型，或者优化问题的最优解过于复杂，无法通过传统方法获得。
    具体而言，在许多情况下，无线通信的优化问题往往是非凸的，因此容易陷入局部最优。处理非凸问题的典型方法是将其转化为凸问题，但这可能会降低准确性。另一方面，由于无线信道的复杂性，我们通常无法通过信道估计得到准确的CSI。此外，基于传统方法，计算过程过于复杂，难以应用于实际场景。

• 基于DL的资源分配

  基于DL的资源分配分为两类：

  • 一类是将优化问题视为“黑盒”，只关注机器学习从输入到输出的映射，而不知道信道状态；
    ①与传统算法相比，可以应用ML来降低计算复杂度。
    ②强化学习是另一种有效的资源分配方法，可以通过适当的奖励设计直接处理目标。通过强化学习，系统的智能体(agent)可以根据对状态空间(state space)的观察来学习找到最佳动作，以最大化其长期奖励(reward)。对于资源分配问题，动作就是资源分配决策，奖励与设计目标有关，例如平均延迟、系统成本、资源利用率等。并且基于学习模型，系统可以找到最优的分配通信资源的策略。
  • 另一类是将机器学习与现有算法相结合以加速优化。

参考：《Machine Learning for Wireless Communication: An Overview》

---

任务卸载决策、资源约束下的任务分配、存在优先级的任务调度/卸载

决策变量为 $x_{i,j,r}=1$，表示任务 $i$ 在计算节点 $j$ 上第 $r$ 个处理。

• 任务卸载决策

  定义：
    边缘计算旨在减轻网络负载、分担终端计算任务，而任务的卸载决策则是基础，包括何时卸载、静止/动态、确定任务是否卸载、卸载收益等
  
  数学模型：
    ① 独立任务的卸载或分配，可看作 $x_{1,j,1}$ 的 0/1 决策问题，如上图所示，即确定任务是否分配至节点 $j$；
    ② 多个独立任务的卸载或分配，可看作 $x_{i,j,1}$ 的 0/1 决策问题，即任务 $i$ 和节点 $j$ 的匹配问题，以实现负载均衡；
    ③ 如果计算节点特定时间内最多只能处理一个任务时，可看作 $x_{i,j,r}$ 的 0/1 决策问题，即任务-节点匹配和节点上的任务排序问题

  独立任务的模型分配是否也可以看成$x_{1,j,1}$ 的 0/1 决策问题，即确定任务是否分配 第$j$个模型
  
  常见算法：
    排队模型、状态转移方程

• 资源约束下的任务分配

  定义：
    由于计算系统的计算、存储、带宽、电池电量等资源有限，将有限资源作为约束条件给出调度优化模型，更符合现实。
  
  数学模型：
    如上图所示，资源约束可表示为 ${\Sigma }_i\left({\Sigma }_r{x}_{i,j,r}\right)\cdot a_{i,j}⩽A_j$, 如图 2 所示, 其中 ${\Sigma }_r{x}_{i,j,r}=1$ 表示任务 $i$ 分配至节点 $j,a_{i,j}$ 表示任务 $i$ 占用的某类资源量, $A_j$ 表示节点 $j$ 该资源总量。
  
  常见算法：
    传统算法：贪婪算法、回溯搜索算法、Benders分解、匈牙利算法、凸优化
    智能算法：遗传算法、共生生物搜索算法、深度强化学习

• 存在优先级的任务调度/卸载

  定义：
    为了加快计算进程，将分布式计算系统中的复杂任务分割为多个子任务形成任务流，进而分配到处
  理器上并行处理。由于部分任务的计算需要前序任务的结果数据，任务间存在优先约束关系，可利用有向无环图 DAG (directed acyclic graph)抽象和建模工作流，图节点代表子任务，节点间连线代表子任务间的优先约束关系。
  
  数学模型：
    如上图所示，任务间优先约束表示为 $EST(j)⩽CT(i),\forall i\to j$, 其中 $EST(j)$ 表示任务 $j$ 可开始处理的最早时间, $CT(i)$ 表示任务 $i$ 的完成时间, $i\to j$ 表示任务 $i$ 到 $j$ 存在优先约束。
  
  常见算法：
    启发式算法：启发式方法主要分为列表调度、聚类和任务复制 3 类。列表调度方法按优先级排列任务，然后从待调度的任务中选择最高优先级的任务分配给合适的处理器；聚类方法将任务聚类，直到类别数与处理器数相等。任务复制将传输数据量大的任务复制到多个处理器上处理，进而降低时延
    智能算法：力争全局的优化性能，例如遗传算法、粒子群算法等

参考：《边缘计算资源分配与任务调度优化综述 》

---

启发式算法

参考：启发式算法

---