分布式交互仿真中容错和实时技术研究

论文摘要

仿真一般指利用相似原理，通过一定的模型对目标对象进行模拟，以了解目标对象特性的方法。仿真系统自产生以来，经历了从SIMNET、DIS、ALSP到HLA的发展历程，并在国防、经济、社会领域得到广泛应用。随着目前仿真系统规模的扩大，仿真时间的延长，仿真系统的可靠性却没有增强，分布式仿真中任务的实时问题也没有解决，而仿真系统在国民经济中担任的重要角色亟待这些问题的解决。目前在流行的HLA和复杂系统仿真中，容错研究很少，而且基本上是沿用了分布式系统的容错方法，没有与仿真系统的特性结合起来，一定程度上影响仿真系统的执行效率。有研究对仿真系统做了实时扩展，但是方案一般建立在具体的仿真架构上，不具备通用性。论文针对分布式交互仿真中的容错和实时问题进行了具体研究。首先，从三种不同的容错手段对分布式仿真容错进行了研究：●Replica方法，Replica方法通过冗余多个副本，能够解决系统的Fail-stop和Byzantine错误，解决方案具有普适性。我们给出replica容错的系统框架，并采用Byzantine quorum系统实现对副本的读写和一致性操作，并对M-Grid系统的实用化进行数值分析；●检查点卷回的方法，检查点的方法一直是容错的传统方法。首先对检查点方法的概况进行介绍，比较各种检查点算法的特点，研究了乐观时间推进机制中动态检查点设置算法，在已有的自适应乐观检查点算法的相关研究基础上，提出异步检查点和强制检查点结合的方案，并且建立概率模型对强制检查点周期的优化设置进行分析，得出周期最优化的充要条件；●动态Passive-backup方法，Replica和检查点卷回的容错方式，要么需要较多的冗余资源，要么恢复过程较长，不能够满足仿真预测预警系统的实时性要求。为此结合因果记录和主副备份的方法，利用仿真中时序特性，提出一种新颖的动态备份容错方法，不需要附加消息、无错进程不需卷回，重复计算过程短，而且容错协议一定条件下可扩展为容忍f个并发错误，并解决单节点失效的问题。理论分析证明了恢复算法能够保证整个仿真系统的状态一致性，实验数据表明其与检查点算法相比无错运行代价小，恢复时间短。除仿真系统容错之外，论文对仿真系统实时加强进行了研究：●介绍了HLA仿真中邦元克隆技术的产生及目前发展，讨论了克隆技术与仿真分支的关系，提出利用博弈理论对仿真分支进行剪枝。在此基础之上，结合目前的HLA数据分发规则给出仿真系统的克隆和剪枝框架，使得剪枝与克隆技术实用化，实验结果证明剪枝能有效减少次要仿真分支，因此能够加速仿真进程，该方法适用于需要实时获得结果的仿真预报系统。●实时系统的调度算法需要考虑实时和容错两个方面，目前主副备份的方法是实时调度的主要途径，副版本作为一种资源冗余的手段，容错的同时占用了相当多的系统资源，为了最大挖掘系统的计算资源潜力，减轻副本对系统任务接收率的影响，本文结合副本重载与主副重载的技术，提出重载度的概念，通过对实时任务重载度的计算和分析，给出基于重载度，以最小时间片占有率为启发函数的实时容错调度算法。实验结果表明，与原有单一重载方法相比，启发式算法有着较好的性能提升。算法的复杂度为O（nm2），可以广泛应用于系统的实时和容错调度。●为了提高系统在网络延迟和网络分区情况下的实时及容错特性，针对连续状态和离散状态系统使用Hermite插值和马尔科夫随机状态转移矩阵来预测数据，从而减少网络异常对仿真系统的影响，在连续系统，小步长的情况下实验证明是有效的。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• §1.1 仿真平台的发展方向和特点
• 1.1.1 仿真系统发展历程
• 1.1.2 Agent平台下的复杂系统仿真
• §1.2 仿真系统容错机制需求
• §1.3 仿真容错相关研究概况
• §1.4 文章的主要贡献与创新
• §1.5 文章的主要结构
• 第二章 分布式仿真环境下的容错架构
• §2.1 仿真系统结构仿真系统基本框架
• 2.1.1 仿真系统的错误类型
• §2.2 错误的检测
• 2.2.1 错误检测配置
• 2.2.2 基于虚拟令牌环的错误检测算法
• §2.3 错误的处理方法与对策
• 2.3.1 错误的处理
• §2.4 仿真系统的容错架构和QUORUM算法
• 2.4.1 采用Replica的HLA容错架构
• 2.4.2 基于检查点技术的容错架构
• 2.4.3 Replica读写算法
• 2.4.4 Quorum系统
• 2.4.5 Quorum系统基本特征
• 2.4.6 Byzantine Quorum系统设计
• 2.4.7 Byzantine Quorum的几个性能指标
• 2.4.8 b-mask quorum系统的负载和可靠度计算
• 2.4.9 几种常见的quorum系统
• 2.4.10 分布式仿真中容错quorum的选择
• §2.5 本章小结
• 第三章 仿真时间推进算法以及检查点方式容错
• §3.1 仿真时间推进算法
• 3.1.1 第一代保守算法
• 3.1.2 第二代保守时间推进算法
• §3.2 乐观时间推进算法
• §3.3 卷回容错算法
• 3.3.1 记录方式的容错
• 3.3.2 检查点方式容错
• §3.4 目前仿真恢复算法的现状
• §3.5 自适应的检查点周期设置算法
• 3.5.1 检查点间隔动态优化算法
• 3.5.2 计算interval的方法
• LVT（e）)值的估计'>3.5.3 Pr(△_LVT（e）)值的估计
• §3.6 自适应的检查点间隔算法
• 3.6.1 系统模型和定义
• 3.6.2 考虑卷回的情况检查点的设置
• 3.6.3 考虑容错机制的检查点设置
• 3.6.4 两种概率分布讨论
• §3.7 乐观时间推进机制下的容错协议
• 3.7.1 乐观机制下系统的错误模型
• 3.7.2 乐观机制下的容错协议
• §3.8 层次化恢复算法的方案
• 3.8.1 网关路由选择
• 3.8.2 层次化的邦元结构体系
• 3.8.3 异构恢复协议在层次化结构中的实现
• 3.8.4 目前层次化恢复算法存在的问题
• §3.9 本章小结
• 第四章 PASSIVE-BACKUP动态容错研究
• §4.1 系统模型和框架
• 4.1.1 基本假设
• 4.1.2 副本更新与心跳机制
• 4.1.3 动态副本配置
• 4.1.4 副本更新频率的设定
• 4.1.5 动态副本放置策略
• §4.2 容错恢复过程和协议
• 4.2.1 数据结构
• 4.2.2 协议正确性证明
• §4.3 容错度为F的扩展
• §4.4 恢复协议对乐观机制的扩展
• §4.5 容错协议性能比较
• §4.6 本章小结
• 第五章 仿真系统的负载均衡及重构
• §5.1 HLA仿真中的邦元克隆和迁移
• 5.1.1 相关研究
• §5.2 邦元迁移
• §5.3 联邦迁移设计
• 5.3.1 迁移协议
• §5.4 本章小结
• 第六章 基于剪枝技术的仿真实时加强
• §6.1 仿真决策分支问题
• 6.1.1 仿真分支树形结构的生成
• §6.2 剪枝算法
• 6.2.1 α,β剪枝算法
• 6.2.2 节点的排序
• 6.2.3 仿真流程的控制与表现（用户的参与）
• 6.2.4 博弈树的剪枝程序
• §6.3 分支克隆的控制和管理
• 6.3.1 HLA规则中的数据订购和分发
• 6.3.2 递归区分算法（Recursive Division Solution）
• §6.4 HLA仿真框架
• §6.5 实验
• §6.6 本章小结
• 第七章 实时容错调度研究
• §7.1 任务模型和系统假设
• 7.1.1 任务重载方式定义
• 7.1.2 重载度的定义及静态分析
• §7.2 任务时间槽占有期及动态分析
• 7.2.1 调度启发函数定义:
• 7.2.2 控制条件（调度允许条件）
• 7.2.3 启发式调度MSO算法（Minimal Slot Occupy Algorithm）
• §7.3 模拟试验与算法比较
• §7.4 本章小结
• 第八章 基于状态预测的仿真实时容错增强
• §8.1 系统模型
• 8.1.1 仿真实时任务集的定义
• 8.1.2 仿真的主要模型分析
• 8.1.3 状态预测方法
• 8.1.4 仿真预测数据的验证
• 8.1.5 实时容错解决方案
• 8.1.6 仿真系统框架
• §8.2 模拟试验
• §8.3 本章小结
• 结束语
• 致谢
• 参考文献
• 作者在学期间发表的学术论文与成果