面向可靠性优化设计的分布式系统资源分配研究

摘要

可靠性定义了系统在一段时间内能够持续正常工作的能力，是系统设计中的一个重要指标，而提高系统可靠性往往会造成系统资源消耗的增加。为了在保障系统长时间可靠运行的同时，达到可靠性增长与资源消耗的平衡，自上个世纪六十年代开始，系统可靠性优化设计作为一个热点研究课题吸引了众多的科研工作者的关注。随着系统规模的增大和复杂性的提升，如何优化系统可靠性变得更为重要，难度也逐步增加。
　　 本文研究课题来源于国家自然科学基金重大项目“大型分布式软件系统的行为监控与可信演化”。与传统系统可靠性优化相比，分布式系统可靠性保障措施产生了改变，从而产生了新的可靠性优化问题。首先，分布式系统规模较大，通常采用多层系统结构表示，如何为多层结构系统合理分配冗余资源成为一个新的难题。其次，分布式系统可靠性无法完全通过传统的测试方式保障，为了提高组件的可靠性，分布式系统中常采用监控机制对组件进行动态替换，如何通过资源分配对基于监控的系统进行可靠性优化也是一大难题。针对分布式系统可靠性优化设计中出现的新问题，本文从多层冗余分配和监控资源分配两方面入手，针对优化系统可靠性设计的目标，研究了多层系统冗余分配算法，多目标的监控资源分配方法以及组件保障策略可选的系统资源分配。现将论文的主要研究内容和成果概括如下：
　　 ①对系统可靠性的评估方法，基于资源分配的可靠性优化模型及算法进行了综述。总结了系统可靠性的多种表示方法及相应的应用场合，归纳了单个组件可靠性及系统可靠性的多种评估方法。对现有的基于资源分配的可靠性优化问题进行了分类总结，重点对冗余分配问题和测试资源分配问题的研究现状进行了分析，并对常用的优化算法，包括精确方法和各种启发式算法进行了分析比较。
　　 ②研究了多层结构系统冗余分配问题，根据多层冗余系统的复杂性，提出了新的系统编码方式，并改进了相应的冗余度分配算法。首先，分析了代价约束下通过多层冗余分配达到可靠性优化的问题模型，研究了该分配问题编码和最优解搜索的难点。然后，针对已有分层编码方式的缺点，采用二维数组的方式对多层冗余系统的结构进行编码。在此基础上，使用改进的模因算法搜索冗余系统的最优解，在模因算法中采用了基于二维数组的交叉变异算子和基于随机漫步策略的局部搜索算子。最后，通过与其它多层冗余分配算法的比较实验验证了该算法的有效性：采用二维编码方式，算法多次运行的稳定性得到了提高；局部搜索策略提高了算法的全局搜索能力，能够获得更好的近优解。
　　 ③针对分布式系统松耦合和动态配置的特点，提出采用监控资源分配达到系统可靠性提高和资源优化的目的，研究了多目标监控资源分配问题和相应算法。为了建立监控资源分配模型，首先建立了监控策略下的系统的可靠性模型；其次分析了监控机制的两种不同代价；再次选择了系统可靠性约束下最小化监控代价的多目标监控资源分配模型。针对该模型，采用基于第二代非支配排序方法和随机漫步局部搜索策略的改进模因算法搜索问题的平衡解集。最后，将监控资源分配模型及算法应用于多层系统中。通过实验验证了监控资源分配的必要性和在可靠性优化中的作用，分析了监控资源分配随系统时间变化的规律，并将所采用的模因算法与若干种已有多目标方法进行了比较，解集的覆盖率和超体积指标结果表明：针对监控资源分配问题，改进算法无论在最优解还是解的多样性方面都有更好的效果。
　　 ④为了弥补系统中单一的资源配置方案的不足，本文提出了对可选的监控资源和冗余资源同时进行选择分配的资源分配方案，建立了面向可靠性约束的多目标资源分配模型并改进了相应算法。针对单层和多层系统，分别分析了组件保障性措施可选的系统可靠性与代价模型，并建立了面向可靠性约束的多目标资源分配模型。在现有组件冗余策略可选的编码机制基础上，采用了新的三元组编码方式表示组件对保障措施的选择以及相应的冗余度和监控频率，改进了模因算法中的遗传算子和局部搜索算子使其能够对三元数组进行操作。通过实验验证了：策略可选的资源分配方案不仅包含单纯的冗余资源或监控资源分配方案，而且在环境条件变化时能为系统提供了更多的资源配置方法。将改进模因算法与已有三元组编码遗传算法进行了比较，结果显示：改进模因算法在解空间的搜索广度和最优解选择上效果更好。

目录

文摘

英文文摘

1 绪 论

1.1 研究背景及意义

1.2 国内外研究现状

1.2.1 面向可靠性优化的多层系统冗余分配

1.2.2 面向可靠性优化的分布式系统监控资源配置

1.2.3 基于可选策略的可靠性优化与资源分配

1.3 主要研究内容

1.4 论文的组织结构

2 面向可靠性优化设计的资源分配研究综述

2.1 引言

2.2 系统可靠性模型及分析方法

2.2.1 系统可靠性模型

2.2.2 系统可用性模型

2.2.3 系统可靠性分析方法

2.3 面向可靠性优化设计的资源分配问题

2.3.1 面向可靠性优化设计的冗余分配

2.3.2 面向可靠性优化设计的测试资源分配

2.3.3 多状态系统资源分配与可靠性优化

2.3.4 多目标系统资源分配与可靠性优化

2.4 系统可靠性优化与资源分配算法

2.4.1 启发式算法

2.4.2 精确算法

2.4.3 其它近似方法

2.4.4 算法对比分析

2.5 本章小结

3 基于进化算法的多层系统冗余资源分配

3.1 问题的提出

3.2 多层系统冗余分配模型

3.2.1 多层串联系统结构

3.2.2 多层串联冗余系统结构

3.2.3 多层冗余系统可靠性分析

3.2.4 多层冗余系统代价分析

3.2.5 多层系统冗余分配问题模型

3.3 二维数组基因编码机制

3.3.1 传统分层基因编码机制

3.3.2 二维基因编码机制

3.3.3 二维编码机制的特点

3.4 基于二维数组编码的模因算法TDA-MA

3.4.1 TDA-MA算法框架

3.4.2 适应度函数

3.4.3 基于二维数组的个体初始化

3.4.4 基于二维数组的交叉与变异算子

3.4.5 基于随机漫步的局部搜索策略

3.5 实验过程与结果分析

3.5.1 实验设置

3.5.2 问题-A的实验结果与分析

3.5.3 问题-B的实验结果与分析

3.5.4 实验结果分析

3.6 本章小结

4 分布式系统监控资源多目标优化分配

4.1 问题的提出

4.1.1 传统可靠性保障机制

4.1.2 组件监控与替换机制

4.1.3 分布式冗余系统中的组件监控机制

4.2 单层系统监控资源分配问题模型

4.2.1 基于传统机制的组件可靠性分析

4.2.2 基于监控的冗余组件可靠性分析

4.2.3 分布式系统可靠性分析

4.2.4 监控代价分析

4.2.5 监控资源分配问题模型

4.3 多目标模因算法MOMA

4.3.1 MOMA算法框架

4.3.2 初始化与传统交叉变异算子

4.3.3 基于非支配排序的全局选择

4.3.4 基于随机漫步的局部搜索策略

4.4 多层系统监控资源分配

4.4.1 多层冗余系统监控资源分配模型

4.4.2 多层系统分配算法TDA-MOMA

4.5 实验过程与结果分析

4.5.1 单层系统实验设置

4.5.2 监控频率对系统可靠性的影响

4.5.3 单层系统实验结果分析

4.5.4 MOMA与单目标算法比较

4.5.5 MOMA与其它多目标优化算法比较

4.5.6 多层系统实验结果分析

4.5.7 实验结果分析

4.6 本章小结

5 基于可选可靠性优化策略的多目标资源分配

5.1 问题的提出

5.2 基于可选策略的单层系统资源分配

5.2.1 基于两种可选策略的可靠性模型

5.2.2 基于两种可选策略的代价模型

5.2.3 基于两种可选策略的资源分配模型

5.2.4 三元组编码方式

5.2.5 T-MOMA算法框架

5.2.6 三元组交叉和变异算子

5.2.7 三元组局部搜索算子

5.3 基于可选策略的多层系统资源分配

5.3.1 基于两种可选策略的的资源分配模型

5.3.2 改进的二维编码机制

5.3.3 T-TDA-MOMA算法框架

5.3.4 基于改进二维数组的种群初始化

5.3.5 基于改进二维数组的遗传算子

5.3.6 基于改进二维数组的局部搜索

5.4 实验过程与结果分析

5.4.1 实验设置

5.4.2 单层系统实验

5.4.3 多层系统实验

5.4.4 实验结果分析

5.5 本章小结

6 结论与展望

6.1 主要结论

6.2 后续工作展望

致谢

参考文献

附 录

A.作者在攻读博士学位期间发表的学术论文目录

B.作者在攻读博士学位期间参与的科研项目