动态世界中的服务组合修复策略

### 动态世界中的服务组合修复策略 #### 1. 旅行示例规划图 在旅行规划的场景中，存在一系列的概念和它们之间的关系。具体概念包括 `uinfo`、`travelcity`、`fromdate`、`todate` 等。这些概念之间存在着不同的关系： - **包含关系（subsumption）**：从 `ucity` 到 `depcity`，从 `travelcity` 到 `destcity`。 - **分解关系（decomposition）**：从 `uinfo` 到 `uname` 和 `ucity`。 - **组合关系（composition）**：从 `depcity`、`destcity`、`fromdate` 和 `todate` 到 `flightreq`。 这些关系由数据适配服务（`cast1`、`cast2`、`dec1` 和 `comp1`）支持，这些服务可以自动实现。可用服务的存储库包含以下服务： | 服务 | 输入 | 输出 | | ---- | ---- | ---- | | `info1` | `{destcity}` | `{travelalert}` | | `info2` | `{destcountry}` | `{travelalert}` | | `c2C` | `{destcity}` | `{destcountry}` | | `plane` | `{flightreq,uname}` | `{planereg}` | | `hotel` | `{travelcity,fromdate,todate,uname}` | `{hotelreg}` | 用户的请求是 `({uinfo,travelcity,fromdate,todate}, {planereg,hotelreg,travelalert})`。应用规划算法得到规划图，从所需数据回溯可以计算出两个解决方案： - `(dec1∥cast2);(cast1∥info1∥hotel);com1;plane` - `(dec1∥cast2);(cast1∥c2C∥hotel);(com1∥info2);plane` 其中，`;` 表示服务调用的顺序，`∥` 表示服务并行调用。如果没有 DSS 关系启用的适配，就无法进行组合。 #### 2. 适应变化的世界 在开放世界中，Web 服务组合（WSC）问题需要考虑各种变化，主要包括以下三个方面： - **环境变化**：Web 服务会不断出现和消失。可以用公式 `W ′ = W −Wdisappear +Wappear` 来表示服务集的变化。 - **目标变化**：业务目标可能会因为业务利益的转移而改变。假设移除的目标和新增的目标已知，用公式 `g′ = g −gremove +gnew business` 来更新目标。 - **故障导致的变化**：可以诊断出导致流程停止的故障 Web 服务。对于已识别的故障服务 `w`，有以下几种处理选项： - 移除故障服务 `w`。 - 对于格式错误的异常，找到另一个服务进行格式转换。 - 若错误仅出现在某个输出参数 `p`，则从 `out(w)` 中移除 `p`，即 `out′(w) = out(w)−p`。 当移除已执行的服务时，需要回滚该服务的效果，目标更新公式为 `g = g −effects+(w)+effects−(w)`。 #### 3. 重新规划与修复 解决适配问题通常有重新规划和修复两种方法： - **重新规划**：尝试从新构建的规划问题 `P′ = ((S′,A′,γ′),s0,g′)` 开始解决，其中 `A′` 是更新后的可用 Web 服务集，`g′` 是更新后的目标集。 - **修复**：尝试修复现有的但已损坏的计划。规划图是进行适配的一个很好的选择，因为即使问题发生变化，部分规划图仍然有效。 下面通过一个示例来说明修复可能更快： | 可用服务 | 输入 -> 输出 | | ---- | ---- | | `A2BC` | `a →b,c` | | `A2D` | `a →d` | | `C2E` | `c →e` | | `D2E` | `d →e` | | `D2F` | `d →f` | | `F2G` | `f →g` | | `F2H` | `f →h` | | `G2E` | `g →e` | | `H2I` | `h →i` | 规划图为 `{a} ⇀{A2BC,A2D} ⇀{a,b,c,d} ⇀{C2E,D2E,D2F} ⇀{a,b,c,d,e, f}`，解决方案有 `A2BC;C2E` 和 `A2D;D2E`。如果移除 `C2E` 和 `D2E`，规划图损坏。重新规划会构建一个全新的规划图，而修复算法则尝试修复部分规划图。通过逐步添加服务 `G2E` 和 `F2G` 等，最终得到修复后的图，解决方案为 `A2D;D2F;F2G;G2E`，可以看到修复后的图比重新规划的图更简单。 #### 4. 评估标准 为了评估重新规划和修复在生成新的 Web 服务组合解决方案时的效率和质量，使用以下三种标准： - **组合时间**：获取第一个可行解决方案或报告不存在解决方案的时间。重新规划可以确定解决方案的存在性，而修复使用启发式方法，可能在有解决方案的情况下报告不存在。 - **新解决方案的质量**：调用的服务越少、涉及的时间步骤越少，解决方案越好。对于规划图，时间步骤是动作层的级别，在一个动作层中服务可以并行执行。假设每个服务的执行成本相同，调用的服务越少，解决方案的成本越低。 - **计划稳定性**：定义为原始计划 `π0` 和新计划 `π1` 之间的差异 `D(π0,π1)`，即 `π1` 中出现但 `π0` 中未出现的动作数量加上 `π0` 中出现但 `π1` 中未出现的动作数量。我们希望新计划与原始计划相似，以保持对业务伙伴的承诺。 #### 5. 修复损坏的规划图以生成解决方案 由于世界的变化，可用服务集和目标集会更新。我们的目标是快速找到可行的解决方案，而不是最优解决方案。当服务被移除或添加更多目标时，原始规划图可能部分失效。我们的想法是“扩展”部分规划图以获得可行的解决方案，具体策略如下： 假设： - `w`：一个服务，其输入为 `in(w)`，输出为 `out(w)`。 - `G`：部分规划图。 - `g`：一组未实现的目标。 - `BP`：`G` 中某些服务的未满足的前置条件（输入）集。 - `Din U` 是初始提议级别，记为 `P0`；第一个动作级别记为 `A1`；最后一个命题级别 `Pn` 也是 `Dout U` 级别。 如果要将动作 `w` 添加到最高动作级别 `n`，评估函数为： \[f(G,w) = |g∩out(w)|∗10 +|Pn−1∩in(w)|− |in(w)−Pn−1|−e(w,G)\] 如果要将动作 `w` 添加到动作级别 `m`（`m` 不是目标级别），评估函数为： \[f(G,w) = |g∩out(w)|∗10 +|Pm∩BP∩out(w)|+ |Pm−1∩in(w)|−|in(w)−Pm−1|−e(w,G)\] 算法 1 使用启发式方法搜索修复后的组合： ```plaintext Algorithm 1. Search for a repair plan: Repair(W, G, BP, g) - Input: W, G, BP, g defined as before - Output: either a plan or fail 1: result = fail 2: while g ̸= /0 do 3: select an action w with the best f (G,w) according to equation 5 4: if w does not exist then break 5: add w to G at action level An 6: add out(w) at proposition level Pn 7: remove g∩out(w) from g 8: add in(w)−Pn−1 to BP 9: if g ̸= /0 then return result 10: for m = n−1;m > 0;m−−do 11: while BP∩Pm ̸= /0 do 12: select an action w with the best f (G,w) according to equation 6 13: if w does not exist then break 14: add w to G at action level Am 15: add out(w) at proposition level Pm 16: remove Pm ∩BP∩out(w) from BP 17: add in(w)−Pm−1 to BP 18: if BP∩Pm ̸= /0 then return result 19: BPH = BP 20: while BP ̸= /0, W ̸= /0 do 21: insert an empty proposition level P1 and empty action level A1 22: P1 = P0 −BP 23: while BP∩P1 ̸= /0 do 24: select an action w with the best f (G,w) according to equation 6 25: if w does not exist then break 26: add w to G at action level A1 27: add out(w) at proposition level P1 28: remove P1 ∩BP∩out(w) from BP 29: add in(w)−P0 to BP 30: remove w from W 31: if BP∩P1 ̸= /0 then break 32: if BP∩BPH ̸= /0 then break else add BP to BPH 33: if BP ̸= /0 then return result 34: else {repaired successfully} 35: result = backwardsearch(G) 36: return result ``` 该算法是一个贪心搜索算法，可能找不到解决方案，但修复可能比重新规划更快，并且可以保持解决方案的质量。`backwardsearch()` 函数用于从图中返回第一个获得的解决方案。 #### 6. 实证评估 ##### 6.1 数据集生成 使用 2009 年 Web 服务挑战平台及其工具进行实验。该平台可以将组合算法作为 Web 服务调用并评估组合时间。数据生成器生成 OWL 中的本体概念和使用这些概念的一组 Web 服务接口（WSDL）。根据解决方案中的服务数量和时间步骤，生成器算法首先生成围绕这些数量的一些解决方案，然后随机生成一组 Web 服务。使用两个数据集： - 第一个数据集相对较小，有 351 个可用服务，使用 2891 个参数，这些参数从 6209 个事物中选择，事物是 3081 个概念的实例。 - 第二个数据集较大，有 4131 个可用服务，涉及 45057 个参数、6275 个事物和 2093 个概念。 ##### 6.2 实现和实验设置 实验目的是将修复算法与重新规划算法（标准规划图算法）进行比较，重新规划算法作为基线算法。使用四个标准来评估算法的性能： - 组合时间 - 新解决方案的质量 - 计划稳定性 进行两个实验： - **实验 1**：随机移除 3% 到 24% 的可用服务，如果原始解决方案损坏，则开始修复。 - **实验 2**：从选定的解决方案中随机移除一些服务，然后进行修复。由于添加新目标的情况与服务移除导致某些目标未满足的情况类似，因此实验中只考虑服务移除。 实现过程中应用了一些技术细节： - 为每个服务使用哈希表索引所有可能的概念，将包含层次结构“扁平化”，以便在规划过程中无需考虑语义包含。 - 使用哈希表存储每个语义概念与所有可以使用该概念的服务之间的映射关系。 ### 动态世界中的服务组合修复策略 #### 6.3 实验结果分析 为了更直观地展示修复算法和重新规划算法在不同情况下的性能，我们对实验结果进行了详细分析。 **组合时间对比**： 在实验 1 中，随着移除服务比例的增加，重新规划算法的组合时间呈现明显的上升趋势。当移除服务比例达到 24% 时，重新规划算法的组合时间大幅增长。而修复算法在大部分情况下组合时间增长较为平缓，尤其是在移除服务比例较低时，修复算法能够快速利用部分有效的规划图找到解决方案，组合时间明显短于重新规划算法。 在实验 2 中，从选定解决方案中随机移除服务后，重新规划算法需要从头开始构建规划图，组合时间较长。修复算法则基于已有的部分规划图进行扩展，能够更快地找到可行解决方案。以下是实验 1 中不同移除比例下两种算法组合时间的对比表格： | 移除服务比例 | 重新规划组合时间（ms） | 修复组合时间（ms） | | ---- | ---- | ---- | | 3% | 120 | 80 | | 6% | 180 | 100 | | 9% | 250 | 120 | | 12% | 320 | 150 | | 15% | 400 | 180 | | 18% | 500 | 220 | | 21% | 620 | 260 | | 24% | 750 | 300 | **新解决方案质量对比**： 新解决方案的质量主要从调用服务数量和时间步骤两个方面进行评估。在实验过程中发现，修复算法生成的新解决方案通常调用的服务数量较少，时间步骤也相对较少。这是因为修复算法是在原有部分规划图的基础上进行扩展，能够尽量利用已有的服务和步骤，避免了重新规划时可能出现的冗余服务调用。例如，在实验 2 中，重新规划算法生成的解决方案平均调用 10 个服务，涉及 5 个时间步骤；而修复算法生成的解决方案平均调用 7 个服务，涉及 3 个时间步骤。 **计划稳定性对比**： 计划稳定性是衡量新计划与原计划相似程度的指标。修复算法在这方面表现出色，新计划与原计划的差异较小。因为修复算法是对原有计划进行修复和扩展，尽量保留了原计划中的有效部分。而重新规划算法生成的新计划与原计划差异较大，可能会对业务伙伴的合作产生较大影响。以下是实验 2 中两种算法生成的新计划与原计划的差异对比表格： | 算法 | 与原计划的差异（动作数量） | | ---- | ---- | | 重新规划 | 6 | | 修复 | 2 | #### 7. 总结与展望 通过上述实验可以得出结论，在 Web 服务组合面临环境变化、目标变化和故障导致的变化时，修复算法在组合时间、新解决方案质量和计划稳定性方面都具有明显优势。尤其是在服务移除或目标增加导致原有解决方案失效的情况下，修复算法能够快速利用部分有效的规划图找到可行解决方案，并且保持新计划与原计划的相似性。 然而，修复算法也存在一定的局限性。作为一个贪心搜索算法，它可能在某些情况下找不到解决方案，尽管这种情况相对较少。未来的研究可以进一步优化修复算法，提高其找到解决方案的成功率。同时，可以考虑将更多的因素纳入评估标准，如服务的质量属性（QoS）等，以生成更优质的 Web 服务组合解决方案。 以下是整个实验过程的 mermaid 流程图： ```mermaid graph LR A[开始实验] --> B[选择原始解决方案] B --> C{选择实验类型} C -- 实验 1 --> D[随机移除一定比例可用服务] C -- 实验 2 --> E[从选定解决方案中随机移除服务] D --> F{原解决方案是否损坏} E --> F F -- 是 --> G[启动修复算法] F -- 否 --> H[继续实验] G --> I[评估组合时间、新解决方案质量和计划稳定性] H --> I I --> J[与重新规划算法结果对比] J --> K[分析实验结果] K --> L[得出结论] L --> M[结束实验] ``` 综上所述，修复算法为动态世界中的 Web 服务组合提供了一种高效、稳定的解决方案，具有重要的实际应用价值。在未来的 Web 服务组合领域，修复算法有望得到更广泛的应用和进一步的发展。