1 容错性的研究

    1．1 容错的定义

    “容错”原是计算机系统设计技术中的一个概念。容错(fault—tolerance)就是容忍错误的简称，是指设备的一个或多个关键部分发生故障时，能够自动地进行检测与诊断，并采取相应措施，保证设备维持其规定功能，或用牺牲性能来保证设备在可接受范围内继续工作。

    1．2 容错技术的发展

    容错技术近2O年发展很快。首先在先进的计算机中实现，例如航天飞行控制、人造卫星、潜艇导航、空中交通管制、银行业务管理等领域，都要求计算机成年累月连续无故障地工作，从而促进了容错计算机的迅速发展。目前世界上已有上百家计算机公司推出了容错计算机。容错计算机的平均故障间隔时间MTBF可达15年一2O年。1986年9月，美国国家科学基金委员会和IEEE控制系统学会联合举办的一次专题讨论会上，国际控制界52位著名专家汇聚于美国Santa Clara大学，讨论控制科学的发展及当前面临的挑战，容错控制FTC(Fauh Tolerance Contro1)被列为当今和未来的七个挑战性课题之一。同年，张翰英教授发表论文，提出在我国“必须加速发展实用性容错系统”的研究。此后，周东华、程一、葛建华、胡寿松等又将容错技式样用工夫动态系统及传感器失效的研究。1997年，IFAC故障诊断与安全性委员会主席Patton教授撰写了容错控制的综述文章。目前，容错技术的研究已经有了很大的发展，并取得了许多重要研究成果。随着计算机的广泛应用和智能结构、智能材料与人工智能的发展，容错技术必将得到更快的发展和更广泛的应用。

2 移动计算环境

    随着移动通信和Intemet技术的发展，以及便携式终端设备的普及，用户要求更大范围地移动，希望能在任何时间、任何地点，可以通过便携式移动设备很方便地访问网络资源，得到所需要的服务；不仅是到另外一个地方，甚至在移动过程中仍然能够保持网络连接、同时使用户访问不受移动漫游、切换带来的干扰。这就出现了移动计算。

    2．1 移动计算的定义

    移动计算=分布Stag技术+移动通信+数据库。

    移动计算是一个全新的概念，是随移动通信、无线网络、Internet、数据库、分布式计算等技术发展而新兴起的技术，已成为重要的前沿领域。移动计算是基于无线通信技术和便携式移动计算设备的分布式计算模式。移动网络与无线网络经常联系在一起，但是仍有区别，移动网络很可能是有线的，而无线网络很可能是固定的。其关系图如图l所示：

图1 移动网络与无线网络的关系

    2．2 移动计算环境的组成

    移动计算环境通常由固定网络、移动网络、无线通信、笔记本电脑／PDM手机以及移动着的用户构成。它是传统的固定网络分布计算环境利用了先进无线通信技术后的扩充，也就是说，移动计算的解决方案应该包括有线和无线两个方面。

    如图2所示，我们考虑一个包含许多移动终端，用户(Mc)和一些静态主机，即基站(Bs)或者叫做移动支持基站(MSS)的移动计算系统。各基站通过静态的有线网络相互连接。有线网络在提供可靠的信息传输过程中必然会产生一定的延迟，但是时间不长。基站覆盖的地理范围称为“单元(cel1)”。移动终端只有在某个基站的范围之内时才能与基站通信，主机可以移动到相邻的单元，例如，随时都可能跨区切换，因此，由于相邻单元信道的不可用性，主机与基站之间断接的可能性总是存在的。

图2 移动计算环境的典型体系结构

2．3 移动计算环境的特点

    移动计算作为分布式计算环境的一种新的发展趋势，．主要存在如下几个特点：

    (1)移动性。必须适应不同地点的连接请求，并且经常在移动时要求保持连接；在不同服务器覆盖范围之间移动，跨区切换比较常见。

    (2)低可靠性。由于其便携性和工作环境，移动计算可靠性较低，更容易受到干扰而出现网络故障。可能长时间发生网络断接，一些假设条件不同于传统的分布式系统。移动计算装置本身也有一些潜在的不安全因素，如碰撞、磁场干扰、易于遗失和失窃等。

    (3)不安全性。无线通信衰落、易受干扰、易被截获。

    (4)带宽有限性。从GSM 波特率9．6Kbps，GPRS 170Kbps到EDGE 384Kbps，3G 2Mbps，其带宽都远低于固定网络中的数据带宽。

    (5)位置相关性。移动意味着变化，从而导致位置的不断变换。而应用程序可能与位置相关，或者位置成为不透明因素。

    (6)电源能力有限。通过蓄电电池供电，但容量非常有限，一般只能2—5个小时，而计算密集型程序能耗更大，电源会更加紧张。

    (7)频繁断接性。移动计算机在移动过程中，一般不采用保持持续联网的工作方式，而是主动／被动地间歇性入网、断接和重接，甚至跨区切换。

    (8)非对称性。包括通信与资源安全乃至QoS的非对称性，访问的是地理上分布的节点。由于电源能力的限制，移动设备上的资源与功能是有限的。

    (9)复杂性。为支持移动性必须加入更多的功能并最终达到网络负载均衡；移动性也必然要求跨软、硬件平台的兼容性。 

3 移动计算容错性的研究

    与有线的固定环境相比，移动环境中的无线网络连接更加脆弱，移动主机可靠性更差，所以移动计算系统更应该需要实现错误恢复的机制。而且，容错移动计算系统的实现将极大地支持如账务处理、电子商务等重要的移动金融业务，移动游戏或分布式信息系统的访问等应用也可以从容错技术的发展中受益。

    然而，移动计算系统所处的无线网络性能较差，具有误码率高、带宽低、停产衰减不稳定等特性；同时网络性能变化很大，连接时断时续，加上网络中移动设备的移动变化进一步恶化网络环境，比如网络拓扑的变化、带宽等网络资源的变化，使得整个网络环境更加不稳定，这些都为移动计算的容错性提出了进一步的挑战。

    当前，针对移动计算环境的特点，人们提出了多种容错算法与技术田，本文将讨论其中比较成熟的两类移动容错技术，即基于检查点和消息日志的容错恢复技术与基于移动Agent的容错技术研究。

    3．1 基于检查点和消息日志的容错恢复

    随着分布式计算系统服务在移动环境中的扩展，很多支持分布式服务的算法经过修改都可用于移动计算系统。检查点恢复是分布式服务为系统提供的容错服务。分布式系统中有很多检查点和恢复策略翻，见表1。

表1 无线分布网络的检查点和日志策略

    然而，分布式系统的的检查点恢复机制并不能直接应用于移动环境。根据移动计算系统环境的特点，一个支持移动计算容错性的好的检查点算法应当考虑如下因素：

    (1)低带宽。因为无线网络带宽低、检查点机制不应当包含大量的系统消息或在一条应用消息中包含大量的额外信息。

    (2)有限空间。由于MC空间的有限性，MC携带的检查点要通过无线网络传给MSS。所以应该控制检查点的执行频率。

    (3)移动性处理。MC的移动性使得MC的恢复信息可能存储于多个MSS中。当一个MC出现故障时，应提供一个机制追踪并搜寻正确的恢复信息。

    (4)断接操作。MC与网络的频繁断接可能会影响MC之间对检查点或恢复的同步。

   以下是几种主要的无线分布网络的检查点和日志策略：

    CCP，协同检查点策略，需要系统中的所有进程协调检查点行为，需要大量的系统消息，不适用于低带宽的移动环境。

    SCP，同步检查点机制，只要求相关进程同步执行检查点，减少了协同消息的数量，但要保证严格的协同，即在执行检查点时要阻塞参与进程的正常计算。

    通过减少CCP和SCP的协作消息数量与参加协作的进程数量得到的CCP与SCP已经在移动计算中提出。

    CICP，基于通信模式的检查点策略利用一个独立的进程根据其通信状态的变化执行检查点，在移动环境中对这个策略进行了扩展。但是这个策略的检查点频率完全依赖于MC的通信模式，无法受控于MC。最坏的情况是MH对于第一条流出消息都要进行一次检查点行为，这是无线网络带宽无法实现的在CICP引入通信的检查点策略中，应用消息携带一个检查点序列号，使进程最终可以获得一致的检查点。实现了对该算法在移动环境中的扩展。

    但是如果考虑恢复的话，所有上述检查点策略都需要显示的协作以避免实时时钟问题。另外，由于进程要回滚到一组一致的检查点状态，故障后重计算的量也很大。

    支持异步恢复并减少重计算量的一个方法是消息日志。若有系统故障，在异步恢复中进程独立决定并回滚。另外回滚之后进程可以立即进行重计算而无需等待其它进程的协作消息。提出了在移动环境中基于悲观消息日志(PML，Pessimistic message logging)的异步恢复策略。然而，考虑到悲观消息日志要频繁地访问稳定存储器，这个方法仍不适应移动环境的特点。

    CML，随机消息日志，可以避免对稳定存储的频繁访问，但在应用消息中要携带大量的依赖信息，无法解决移动计算系统低网络带宽的问题。

    OML，乐观消息日志，提出的OML可以控制稳定日志的频率实现异步恢复，它使用一个很小的信息，vector clock可以检测到可能引起实时时钟问题的异常消息。文献中在此基础上进一步优化，提出移动计算系统中基于乐观消息日志的异步恢复策略，充分利用MSS的动态日志空间由MSS实现消息日志，MSS同时还负责依赖性的追踪，而MC只携带最少的信息，如此则MC的移动性将由MSS实现完整的追踪，其消息开销也比较小。此外，根据MH和MSS同时故障的可能性，策略通过选择一个合适的稳定日志记录频率还可以在一定程度上减少不正确的依赖产生的回滚开销。

  3.2 基于移动Agent的容错技术

    移动代理是指一个可以在网络上移动并执行确定功能的程序，也就是说移动代理可以在运行的一点挂起，移动到另一台机器并从挂起点继续运行。从这一方面上讲，它和检查点技术颇为相似。

    移动代理系统的研究涉及多方面的问题，其中移动代理的容错性能占据一个重要方面，移动代理在有线或无线网络上自行移动，网络节点内部程序的错误、网络节点的崩溃或离线、网络传输的延迟等无一不对代理的顺利执行构成威胁，移动代理的自主性、可移动性、交互性等自身特性使它的容错性能有别于传统的容错方案。

    现有几种的移动代理的容错模型多数是基于复制的。下面加以介绍：

    (1)检查点方法(Check Pointing Approach)如图3所示，当代理在库所执行时，它的初始代码存储在稳定存储器中，执行状态周期性地被存储到检查点，如果库所失效，代理将从稳定存储器中恢复。但在实际运行过程中，检查点需要将运行状态及时发送到库所存储位置，如果库所失效，则检查点方法无法恢复。这种方法只能处理到库所失效级。

图3 检查点容错原理图

    (2)Stefan Pleisch和Andr 6 Schiper提出的分类方法

    将多数模型分为基于暂态复制(temporal—replica—don—based)和基于空间复制(spatial—replication—based)两类。

    暂态复制基于检查点方法，但将备份保存在前一库所。如图4所示，P1监视P2和P2”，当库所P2发生故障时，P1将代理a2送至P2’继续执行。可见，暂态复制能够克服库所故障，如果库所处在不同的主机上还能克服主机故障。

图4 基于暂态复制的容错模型

    空间复制方法如图5所示，代理将每个阶段的执行结果全部复制到下一阶段的库所上，即使有一个库所失效，其它库所也收到了代理，也可以继续执行。通常每个阶段只有一个代理执行，这是由每个阶段的选举法则(voting protoco1)决定的。显然这种方法也能克服库所故障和主机故障。甚至在某种程度上能够克服拜占庭故障。