分布式智能系统中多微目标资源调度算法解析

### 分布式智能系统中多微目标资源调度算法解析 #### 1. 单微目标与单资源关联 在分布式智能系统的任务执行中，单微目标与单资源关联是一个基础的调度问题。其核心思想是，每个分配到资源 \(r_i\) 的作业 \(a_n\) 会在本地广播一个报价 \(Q_n^i\)，其他作业若要取代该作业，就必须满足这个报价。 资源会主动与邻域共享其所了解的每个作业的可能成功情况，同时，分配到资源的作业也会发送其报价。例如，在时间戳 \(T'\) 时创建了作业 \(a_3\)，资源会再次主动广播可能的成功情况。由于之前的报价交换，作业 \(a_3\) 了解取代作业 \(a_1\) 的条件，随后作业 \(a_1\) 会取代作业 \(a_2\)，作业 \(a_2\) 会取代资源 \(r_3\) 上的空闲作业。 这里的报价 \(Q_n^i\) 被称为销售报价，因为作业 \(a_x\) 若要从作业 \(a_n\) 处获得资源 \(r_i\)，就需要支付这个虚拟价格。成功在这个情境下等同于虚拟货币。销售报价意味着，如果作业 \(a_n\) 释放其资源 \(r_i\)，受益作业 \(a_x\) 必须补偿损失，计算公式如下： - 若作业 \(a_n\) 不迁移到其他资源，报价为：\(Q_n^i = P_n^i\) - 若作业 \(a_n\) 可以迁移到替代资源 \(r_{i'}\)，报价为：\(Q_n^i = P_n^i - \max_{i'}\{P_n^{i'}\}\) - 若作业 \(a_n\) 需要从提供作业 \(a_{n'}\) 处赎回替代资源 \(r_{i'}\)，报价为：\(Q_n^i = P_n^i - \max_{i'}\{P_n^{i'} - Q_{n'}^{i'}\}\) 作业 \(a_n\) 收到报价后，需要判断其当前的成功是否大于在资源 \(r_{i'}\) 上的可能成功。可能成功由成功 \(P_n^{i'}\) 减去成本 \(Q_{n'}^{i'}\) 得到，即：\(P_n^{i',red} = P_n^{i'} - Q_{n'}^{i'}\) 然而，这种方法本身无法实现我们期望的解决方案，因为它不支持将多个微目标分组到一个资源上。因此，需要对 PQB - 调度算法进行扩展以应对这一挑战。 #### 2. 多微目标与单资源分配 计算系统范围内微目标的最优分组是一个难题，在将 PQB - 调度算法应用于这种情况时，存在两个普遍挑战和两个问题。 ##### 2.1 普遍问题 - **问题 1：单微目标成功对组组成的依赖性**：多个微目标在单个资源上执行的成功是该组内单个微目标成功的总和。但单个微目标的成功依赖于组的组成。例如，作业 \(a_1\) 和作业 \(a_2\) 共享资源 \(r_1\) 时，通常 \(P_{a_1\subseteq\{a_1,a_2\}}^1 \neq P_{a_1}^1\)，这是由于资源共享导致的。 - **问题 2：使用本地知识和算法创建组**：有两种对立的方法可以考虑。一种是作业自行形成组，另一种是构建所有可能的组合，只执行成功最高的组内的微目标。乍一看，动态分组似乎更可取，因为软件实例的数量随微目标数量线性增加，而所有可能组合的数量呈指数增长。但由于我们选择的本地知识和本地算法的限制，动态分组很难实现。 ##### 2.2 PQB - 调度问题 - **问题 1：分组拆分的考虑**：在 PQB - 调度方法中计算报价时，必须考虑组的拆分。例如，SC3 正在观察事件 1 和 2，SC1 和 SC2 无法同时观察这两个事件。最佳解决方案是事件 1 由 SC1 观察，事件 2 由 SC2 观察，事件 3 由 SC3 观察。因此，计算的报价必须考虑事件 1 和 2 的分离，否则负责观察事件 3 的作业将无法购买 SC3，这会使搜索空间呈指数级增加。 - **问题 2：资源上剩余组部分的考虑**：计算报价时，还必须考虑留在资源上的组的部分。例如，SC2 正在观察事件 1 和 2，最佳解决方案是事件 1 由 SC1 观察，事件 2 和 3 由 SC2 观察。因此，计算的报价必须考虑事件 1 和 2 的分离，以及作业 \(a_1\) 观察事件 2 留在 SC2 上的情况。否则，负责观察事件 3 的作业将无法购买 SC2。 这些问题可以用以下公式进行形式化描述： - 假设组 \(g\) 正在分配资源 \(i\)，若组 \(g\) 离开资源 \(r_i\)，取代作业必须补偿组 \(g\) 的损失：\(Q_g^i = P_g^i\) - 若组 \(g\) 的子组 \(g_{sub}\) 可以拆分到其他资源 \(r_{i'}\) 上，报价为：\(Q_g^i = P_g^i - \max_{i',g_{sub}}\{\sum_{i'}(P_{g_{sub}}^{