移动自组网络中低成本容错回滚恢复技术

Journalof King Saud University沙特国王大学沙特国王大学学报www.ksu.edu.sawww.sciencedirect.com移动自组网中低开销的容错回滚恢复Parmeet Kaur Jaggia，*， Awadhesh Kumar Singhba印度诺伊达Jaypee信息技术学院计算机科学系b印度库鲁克舍特拉国立技术学院计算机工程系接收日期：2013年11月14日;修订日期：2014年2月4日;接受日期：2014年3月13日2015年6月18日在线发布摘要移动自组织网络（MANNETWORK）极大地增强了无线网络的性能消除对任何固定基础设施的需求。因此，这些正越来越多地用于扩展现有网络的计算能力或用于实现自治网络。移动计算网格。然而，移动自组织网络的脆弱性使得其组成节点容易发生故障，并且只有在以下情况下才能利用这些网络的计算潜力：是容错的。基于检查点的回滚恢复技术已被有效地用于静态和蜂窝移动系统中的容错，然而，现有的协议的实施，移动自组网是不简单的。本文提出了一种新的回卷恢复协议，用于处理移动自组网中的移动节点的故障，使用检查点和基于发送者的消息日志。所提出的协议利用现有的路由协议在网络中实现低开销的恢复机制。在一个节点上提出的恢复过程是完全无多米诺骨牌和异步的。该协议对移动自组网的动态特性具有较强的适应性;允许独立地执行分布式应用而不访问任何有线网格或蜂窝网络接入点。我们还提出了一个算法来记录一个consis- tent全球快照的移动自组网。2015作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。1. 介绍移动自组织网络（MANDO）已经广泛地增强了无线网络，因为它们消除了对任何固定基础设施的需要，以基站的形式*通讯作者。沙特国王大学负责同行审查路由器等。这些网络由在无线链路上通信而不受任何中央或固定管理的控制的节点形成。每个节点执行节点和路由器的双重角色。由于移动台具有自组织和快速部署的特性，因此它们经常被用于在昂贵或难以安装网络基础设施的地方进行通信，例如战场，搜索和救援或太空探索。此外，当前移动计算平台的计算能力超过了几年前的工作站。无线设备和网络的爆炸性和持续增长以及它们的广泛可用性提供了http://dx.doi.org/10.1016/j.jksuci.2014.03.0221319-1578年，作者。制作和主办：Elsevier B.V.代表沙特国王大学这是一篇基于CC BY-NC-ND许可证的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。制作和主办：Elsevier关键词自组网;移动骨干网;回滚恢复;检查点;消息记录;路由协议低开销的回滚恢复以实现容错403为理解和利用移动adhoc网络的计算潜力提供了一个推力。这些网络越来越多地与LAN/WAN场景协作用于并行处理系统，作为扩展现有网络（如蜂窝移动系统）的计算能力的手段，甚至用于实现移动网格计算系统（Darby，2010; Wang 等 人 ， 2006 年 ; Rao 等 人 ， 2006; Jipping ，2001）。各种轻量级的分布式应用程序可以在没有固定基础设施支持的情况下在移动ad hoc平台上成功执行。这些应用包括提供位置感知服务的移动代理;从多个MH收集的传感器数据的本地和协作处理，实时战斗场景中的地图更新等。其他应用包括协作移动游戏，互联车辆的上下文感知应用，生物信息学和其他科学应用;特别是在无法访问有线网络的偏远地区（Darby和Tzeng，2010）。具有高计算能力的智能电话以及膝上型计算机和个人数字助理（PDA）可以用于在火车、大学等中创建计算云。这样的云可以用于使用来自公共传感系统的环境数据、破解加密代码、除了参与科学项目外，还开发移动医疗保健和教育应用程序（ Buschin 等 人 ， 2012 年 ） 。 一 些 移 动 网 格 项 目 ， 如Akogrimo（2010），已经探索了移动网格概念的使用和实际应用，使得来自大量移动设备的空闲资源可以用于移动网格计算平台的开发。由于大量可行的实际应用，当前的移动计算平台越来越多地被用作可行的计算资源。然而，这种系统中的节点在其能力（诸如计算功率和电池功率）方面变化很大，并且可能易受不同类型的瞬时和永久故障的影响。 因此，设计用于在这些系统上执行的应用程序应该是容错的，以便它们可以在不访问任何有线网格或蜂窝网络接入点的情况下成功完成。检查点设置和回滚恢复已经被广泛且有效地用 于 为 静 态 以 及 动 态 环 境 中 的 分 布 式 系 统 提 供 容 错（Elnozahi等人，2002年）。检查点可以显著提高性能，因为它允许故障节点在恢复时从其最新保存的无错误状态恢复执行，从而避免了从一开始就重新启动作业执行的需要。相反，在没有执行检查点的情况下，一个节点的故障可能会导致一些其他节点也挂起执行，如果它们正在等待来自故障节点的中间结果的话。因此，进程失败可能导致严重的性能下降，甚至在没有检查点的情况下导致整个作业中止尽管存在用于静态分布式系统或蜂窝移动计算系统的许多检查点设置和回滚恢复协议，但是这些协议并不简单地适用于MANNET，因为它们提出了一些完全不同的挑战集。Ad hoc无线网络的特点是无线带宽、稳定存储、电池电量等资源有限。此外，缺乏固定的基础设施会给Ad hoc网络带来新的问题，例如自路由和高度不可预测的动态拓扑。传统的系统依赖于节点或基站收发器站上可用的稳定存储，用于保存恢复相关信 息 （ Prakash 和 Singhal ， 1996 年 ; Li 和 Shu ， 2005年;Tantikul和Manivannan，2005年）。另一方面，自组织环境缺乏这种有能力的站和承载可靠链路的大数据。移动自组织网络也有一个内在的可扩展性限制。随着网络规模的增加，ad hoc网络的性能迅速下降，因为一个大的网络与manderat结构的结果在长跳路径，这是容易发生链路中断。本文提出了一种检查点和回卷恢复协议，以提供在移动自组网的容错 我们考虑基于骨干的移动自组织网络，它 是 一 种 用 于 可扩 展 性 和 有 效 协 议 实现的分层网络（Rubin等人， 2004年）。这样的网络包括一些特定的具有骨干能力的节点（BCN），其具有强大的无线电并且在功能上比其他普通节点更通过动态地选择一些BCN充当骨干节点（BN）并在互连的相邻BN之间形成链路其他BCN和普通节点中的每一个都与一个BN相关联节点之间的通信使用骨干网，从而避免了长跳路径，提高了网络性能。节点通过它们所隶属的BN彼此通信。如果通信节点隶属于相同的BN，则路由是直接的。但是，如果它们位于远程位置，则使用网络中现有的路由协议基于位置的路由协议GOAFR+（Kuhn等人，2008年），已为目前的工作。它采用贪婪和脸路由的组合，以达到目的地使用他们的地理信息。然而，我们的恢复协议是独立的，可以集成到任何路由协议的人工智能。所提出的恢复协议已被设计来处理的MANET的动态拓扑结构和资源约束所带来的具体挑战。该协议利用了网络中已有的路由协议，不会给正常的进程执行增加很高的开销。该方案是一种跨层优化的应用，其中网络中现有的路由协议已被用于实现消息有效的检查点和恢复机制。骨干集群结构的使用提供了额外的可扩展性的协议。本文的贡献可以总结如下：（1）本文提出了一个检查点和回滚恢复协议，它不需要访问任何固定的主机或有线网络，因此适合于移动自组网。(2)检查点过程不需要控制消息，因为协议所需的控制信息是在应用程序消息上附带的。(3)恢复过程可能涉及几个控制消息;仅对网络施加低开销。 (4)尽管网络的拓扑是动态的，移动节点的快速和有效的恢复是可能的。即使移动节点在与其崩溃位置不同的位置恢复，其检查点和相关信息也可以使用网络骨干在网络中定位而没有太多延迟。404P.K. Jaggi，A.K. 辛格(5)还提供了构造系统的一致全局快照的算法。仿真实验已经进行了评估所提出的方案。本文的其余部分结构如下：第2节讨论了检查点和消息日 志 技 术 的 背 景 。 第 3 节 概 述 了 在 检 查 点 以 及 在MANNETWORK中的应用程序消息路由方面所做的相关工作。在第4节中描述了所提出的算法中使用的底层系统模型;解释了网络骨干的构造和假设的路由方法。随后，我们在第5节中介绍了基于消息日志的检查点算法和恢复协议。第6节描述了计算系统全局快照的算法。该方案与相关方案进行了比较，并在不同的应用消息流量和故障率下进行了仿真。比较性能分析见第7节。第8节结束介绍。2. 背景分布式执行的全局检查点形成为一组本地检查点，系统中的每个进程都有一个本地检查点。然而，在进程之间传递的消息在不同进程的检查点之间创建依赖性。(It可以注意到，在随后的讨论中，消息意味着应用消息，除非明确指定为控制消息）。因此，如果存在其接收事件被记录在某个进程的本地检查点中但其发送事件未被记录在任何进程的本地检查点中的消息，则任何给定的本地检查点集合可能不一致这样的消息是孤儿消息，并且形成为一组本地检查点（每个进程一个）的系统状态当且仅当它不包括任何孤儿消息时是一致的。协调检查点提供了一种构造分布式计算的一致全局检查点的直接方法（Elnozahi等人，2002年）。该技术要求系统中的进程在检查点设置时彼此同步，即，用于周期性地将它们的本地状态保存在稳定存储器上。要从崩溃故障中恢复，系统将回滚到其最新保存的一致全局状态，该状态由所有进程的检查点集组成。即使一个进程失败，多个进程也可能必须回滚到其最新的检查点，以便恢复一致的系统状态。此外，在稳定存储上记录一致的全局检查点需要进程之间的大量消息来同步它们的检查点活动。因此，协调的检查点会受到与检查点过程相关的高通信和同步开销的影响（Li和Shu，2005）。相反，独立或不协调的检查点方案允许进程以周期性间隔独立地获取其检查点，而没有进程之间的任何同步或消息传递（Elnozahi等人，2002年）。一个主要的缺点是，它可能会导致多米诺骨牌效应，这是一种情况下，一个进程的回滚可能会触发一个cas-caded回滚多个进程（兰德尔，1975年）。在最坏的情况下，多米诺骨牌效应可以将计算带到初始状态。此外，不协调的检查点设置可能导致进程处的无用检查点，即，检查站它不能是任何一致的全局状态的一部分。一组局部检查点形成一致全局状态的必要和充分条件是从zig-zag路径（z-路径）的结果中推导出来它要求不存在从本地检查点集合的任何检查点到另一个检查点的z路径。此外，如果检查点涉及Z形周期（zigzag cycle），则它永远不能成为任何一致全局检查点的一部分，即，检查点具有到其自身的z路径。进程p的第i个检查点称为Cp，i，在一个过程中第i个和第（i+1）个检查点之间的周期作为第i个检查点间隔。如果存在一个消息序列m1，m2，.，则存在一条从检查点Cp，i到检查点Cr，j的Z字形路径（Netzer and Xu，1995）。. m n（nP1），使得1. m1由进程p在Cp，i之后发送。2. 如果mk（16k6n）由进程q接收，则mk 1由q在接收mk之前或之后的相同或稍后的检查点间隔中发送。3. mn在Cr，j之前被进程r接收。图1a描绘了由于消息链m1，m2而导致的从Cp，i到Cr，j的因果路径，而图1b描绘了由于消息链m1，m2而导致的从Cp，i到Cr，j的非因果z路径;其中消息m2在相同的检查点间隔中在m1的接收之前由q曲折路径并不总是代表因果关系;因此，如果存在从C到自身的曲折路径，则检查点C可能涉及曲折循环。由于消息链m1，m2，m3，图1c中的进程p接收到m3完成了一个涉及Cr，j的z循环，其中m1在接收到m3之前发送，并且在进程p.已经证明了由局部检查点集合S构成的全局检查点是一致的当且仅当S中任意两个检查点之间不存在Z字形路径（包括从任意检查点到自身的Z字形循环）（Netzer and Xu，1995）。这也导致了这样的结果，即当且仅当C不涉及任何锯齿形周期时，检查点C可以属于一致的快照（Xu和Netzer，1993）。为了在线检测z循环，消息的发送者的依赖性信息需要在消息的接收者接收消息时对消息的接收者可用。然而，只有关于发送者在消息的因果过去中的依赖性的信息才当接收到消息时，在发送者处通过在发送消息之后接收消息而由于不可能通知非因果依赖性，因此不可能在线跟踪所有z路径（Allulli等人，2007），我们建议使用骨干网络来传播系统中的依赖性信息，通过将其附加应用程序消息。这种方法减少了无用检查点的数量，而无需任何额外的控制消息。另一种回滚恢复方法将检查点与消息日志记录结合起来，以实现对失败进程的异步恢复。在基于日志的回卷恢复中，非确定性事件的决定因素在无故障操作期间被记录到稳定存储器中。在恢复时，进程使用其检查点和记录的确定性来检查相应的非确定性事件。因此，通过将检查点设置与消息日志记录相结合，恢复过程可以准确地重建进程的故障前状态，即，超出最新检查点。变化低开销的回滚恢复以实现容错405M1M3M2ð Þð ÞCp，iCp，i+1pqrCp，ipqrpCp，iqrCp，i+1Cr，j-1Cr，jCr，j-1Cr，jCr，ja. 因果路径BZ路径C. Z循环图1检查点之间的路径在文献中已经描述了基于接收机的同步消息日志记录。其中，基于发送者的日志记录（Johnson等人， 1987）用发送方日志中的易失性日志记录代替了接收方的消息的悲观日志记录，从而大大降低了同步日志记录的无故障开销。消息保存在发送方的易失性存储器中，仅当发送方采用新的检查点时才传输到稳定存储器。3. 相关工作检查点和回卷恢复技术已被广泛用于有线和移动分布式系统中提供容错在文献中已经提出了各种协调的以及独立的检查点协议（Elnozahi等人，2002年）。任何检查点协议的目标都是以最小的检查点和通信开销在系统中实现一致的全局检查点。在失败时，进程应该能够恢复到与全局系统状态一致的无错误状态。由于协调检查点涉及到高同步和消息开销，作者已经研究了实现独立检查点技术的方法，以避免不受控制的回滚传播。Wang（1997）讨论了如何通过进程形成包含一组独立局部检查点的一致全局检查点的问题。作者定义了包含一组S检查点的最大和最小一致性全局检查点，并给出了 基 于 回 滚 依 赖 图 的 可 达 性 分 析 的 算 法 。 利 用 Wang（1995）的协议可以构造包含一组检查点的最大和最小一致全局检查点。Manivannan et al.（1997）中的工作精确地定义了哪些局部检查点可以包含在一致的全局检查点中。提出了一种算法来列出所有这些一致的全局检查点。Xu和Netzer（1993）的工作提出，一种自适应独立检查点算法，用于检测锯齿形周期，目的是减少回滚传播。如果一个进程接收到一个消息，使得它的当前检查点有一条通往发送者当前检查点的因果路径该进程在处理消息之前接受检查点。然而，使用该算法，每个局部检查点可能仍然不属于某个一致的检查点，并且在最坏的情况下可能发生多米 诺 骨 牌 效 应 。 准 同 步 检 查 点 算 法 （ Tantikul 等 人 ，2005）结合了协调和非协调检查点允许进程异步地采用检查点并且还消除无用检查点的方法。然而，他们的算法，像Xu和Netzer（1993）的工作一样，只跟踪在线的因果路径，而不检测非因果路径。最近的 工 作 ， 如 Allulli 等 人 ， （ 2007 ） 建 立 在 Netzer 和 Xu（ 1995 ） 、 Wang （ 1997 ， 1995 ） 、 Manivannan et al.（1997）、Xu和Netzer（1993）的早期工作基础上;但这些工作通过对检查点和消息模式进行限制来执行。Allulli等人（2007年）指出，如果不使用控制消息，就不可能在线检测非因果z循环。我们的协议优于早期的协议，因为它允许一小部分的非因果z周期被检测到，而不使用控制消息。此外，在每个进程中维护的进程间依赖性信息的大小是O N，其中N是骨干网的大小或网络中集群的数量，而O n，其中n是系统中主机的数量，如Xu和Netzer（1993）所使用的。此外，所有上面讨论的算法被设计为检测由静态有线或蜂窝移动网络中的进程采用的无用检查点。有线系统没有稳定存储的限制，具有高带宽的有线链路和固定的拓扑结构。不考虑在何处以及类似地，为蜂窝移动系统设计的回滚恢复方案假定以固定移动支持站的形式提供无限和静态支持（Prakash和Singhal，1996年; Li和Shu，2005年; Tantikul和Manivannan，2005年）。几乎每一个蜂窝移动系统的解决方案都将存储检查点和进程的消息日志的任务委托给MSS。这样的假设不能扩展到移动ad hoc环境，因此，adhoc网络的检查点和回滚恢复协议的设计是令人困惑的。这个问题最近在文献中受到关注。一个准同步检查点和悲观日志计划的ad-hoc无线网络中提出的男子等。（2008年）。在失败时，进程可以回滚到其最近的一致检查点，回滚过程不会导致多米诺效应。Ono和Higaki（2007）提出的检查点协议采用消息交换进行检查点设置。检查点的请求通过广播发送，并且同一消息携带移动节点的状态信息。在Juang和Liu（2002）的集群模型中，每个集群管理器维护一个依赖矩阵，其大小取决于系统中移动主机和集群的总数。Biswas和Neogy提出了一种基于簇的移动ad hoc网络的M1M2M1M2406P.K. Jaggi，A.K. 辛格（2012年）。移动节点利用它的邻居节点保存它的检查点，如果集群之间的节点的移动性超过预定义的阈值。该方案防止孤儿和丢失的消息。然而，这些协议都没有尝试减小要存储在主机处的恢复相关信息的大小。此外，恢复相关消息是广播的，导致高消息开销。一种新兴的未来计算范例是移动网格（MoG），即，涉及移动主机的计算网格，以允许用户访问网格并提供计算资源（Darby和Tzeng，2010; Wang等人，2006年; Rao等人，2006年）。移动设备既可以作为资源的提供者，也可以作为资源的接受者参与网格。MoG在无法接入有线电网、需要自主协作计算的情况下尤其有益。Darby和Tzeng（2010）提出了一种用于移动网格计算系统中检查点安排的分散式QoS感知中间件。每个移动主机（MH）将其检查点数据发送到一个所选择的相邻MH，并且还用作另一个相邻MH的检查点存储节点。作者证明了寻找全局最优检查点安排是NP完全的，因此，提出了QoS感知的算法，以构造有效的检查点安排。Darby和Tzeng（2010）的可靠性驱动（ReD）方法利用每个MH的链路的可靠性值来收敛到检查点布置。然而，ReD没有提供任何消息日志记录或维护进程间依赖关系的功能.因此，故障进程的检查点可以在恢复时从其“提供者”中检索，但无法计算系统的全局快照，因为没有进程间依赖关系的记录。相比之下，我们的算法跟踪进程间的依赖关系，并记录消息，以及，以便可以计算一致的全局快照。ReD方法假设进程将在其“提供者”的邻居节点处恢复。另一方面，我们的协议没有这样的限制，并允许一个进程在网络中的任何位置恢复，而不管它的最后一个检查点存储在哪里Rao等人（2006）提出了一种基于代理的协调检查点方案，该方案具有用于移动网格系统中故障恢复的悲观消息日志。移动主机在中间件上运行的各自代理上存储检查点。该方案无需移动主机的直接参与，能够回滚到最新的全局一致快照，从而减少了移动终端的处理和存储开销。然而，与我们的协议不同，Rao等人（2006）的解决方案依赖于代理，即，静态主机驻留在假定资源丰富的移动访问网格基础设施中间件上。已经观察到，现有的检查点设置和消息日志记录的方法中没有一种全面地解决ad hoc网络中的检查点设置节点所面临的所有问题。此外，这些方法遭受高消息开销，使得问题对有效解决方案的开发开放。提出的协议旨在提供一个回滚恢复协议，避免无用的检查点在进程中具有低的消息开销。该协议是可扩展的，由于集群骨干的系统架构和弹性的节点移动性。4. 系统模型动态移动骨干网用于实现网络节点之间的消息有效通信。这种网络的分层架构将具有优越处理和通信能力的骨干节点（BCN）与可能具有相对受限能力的普通节点（ON）组合。通过动态地选择BCN充当骨干节点（BN）并且在相邻BN之间形成链路以实现连接的骨干网络来形成虚拟骨干。剩余的节点（未选择的BCN和ON）通过执行聚类算法与BN关联并加入其组或聚类。Rubin等人（2004）将移动骨干网描述为移动自组织网络的可扩展性问题特征的解决方案，并且已经被广泛研究和使用（Srinivas等人，2009;Craparo等人，2011; Ju等人，2004; Pandey等人，2006; Juand Rubin，2005）.这种结构如图1所示。 24.1. 网络主干综合对于网络骨干选举，我们计算一个权重，W，为每个BCN的剩余能量，移动率和节点度的参数的基础上的BCN。BN节点选择方法优选具有较大权重的BCN，即，更高的能量、更低的迁移率和更高的节点度。设h为移动率，c为剩余能量，g为BCN的节点度。假设网络的大小为A，其中A表示操作区域的大小W/cg和W/1= h因此，W=k*（c * g/h）;其中k是等于网络大小的倒数的常数在文献中已经提出了许多骨干选举算法（Ju等人，2004;Pandey等人，2006; Ju和Rubin，2005; Wu和Li，1999）。我们适应选举算法称为MBN拓扑合成算法（Ju和Rubin，2005年）为我们的系统，因为它收敛于O（1）的时间和它的消息复杂度是O（1）每个节点的顺序。如果BCN需要为其邻近的BCN提供客户端覆盖，或需要增加BCN ON BN图2系统模型。低开销的回滚恢复以实现容错407在其相邻BN之间的连通性。BN将转换回BCN，如果它发现它不需要客户覆盖或本地连接。首先，BCN尝试在其1跳邻域中识别具有最高权重的BN以进行关联，并向其发送关联请求。如果没有相邻BN，则节点尝试与具有最高权重的相邻BCN（包括其自身）进行关联。每个节点向其邻居发送周期性信标消息。BCN将其权重和它所关联的BN的ID与周期性消息一起附加。每个节点（ON、BCN或BN）还在消息中包括其相邻BN的列表，并且因此与其邻居共享其完整的1跳邻域和2跳BN邻域知识。如果BCNx满足以下任何条件，则BCNx将其自身识别为BN：(1) BCNx在其未关联的BCN邻居中具有最高权重，或者BCNx已经接收到一个或多个关联请求。(2) 其BN邻居中的两个或更多个不直接连接（例如，BNy和BN z），并且BCN x在其BCN邻居（例如，BCNu）中具有最高权重，其可以连接那些BN，如图2所示。 3 a.(3) 其BN邻居中的至少一个（例如，BN y）和其BCN邻居中的一个（例如，BCN z）不直接或通过BN彼此连接，并且（i）BCN x在其可以连接y和z的所有BCN邻居中具有最高权重，并且（ii）节点x的BCN邻居（例如，BCN u）中没有一个可以直接连接到BN y和BCN z 的 BN 邻 居 中 的 至少一个 ， 如 图 11所示。 3 B.4.2. 网络中的路由移动自组网中的路由问题已经得到了广泛的研究。Royerand Toh（1999）和Boukercheet al.（2011）对ad hoc网络的路由协议进行了调查。路由协议分为按需路由协议和主动路由协议。路由选择由发送方仅在其具有要在按需协议中传输的分组时发起。相反地，对于主动路由协议，移动设备周期性地交换路由控制分组并更新它们的路由表。按需还是被动这种方法导致较少的控制分组并适应拓扑的变化，但是导致在分组可以被发送之前路由建立中的较长延迟。相比之下，主动协议需要维护路由表，独立于流量负载，因此当数据流量低于移动速率时可能会有很高的开销。在动态网络中，预先计算的路由也可能不正确，从而导致潜在的数据包丢失。因此，在大型网络中，主动协议的性能会下降。另一方面，虽然反应式协议提供了更好的可扩展性，但这些协议由于在路由发现过程中使用的广播方法而遭受广播风暴问题，从而导致冗余和冲突问题。一些反应式路由协议（Khamayseh等人，2011）已经努力通过限制在缓慢移动和低负载节点上的重新广播消息来减少广播问题的影响。地理路由或基于位置的路由在ad hoc环境中受到了相当大的关注。地理路由是特别感兴趣的，因为它不需要任何路由表，一旦目的地的位置是已知的，所有的操作都是严格的本地和独立的远程发生的拓扑变化。在该方法中，假设每个节点知道其自身及其网络邻居的位置（借助于定位系统）。此外，假定消息的源被告知目的地的位置。保证到达目的地的地理路由算法是基于面的，面是由平面网络子图的边分隔的连续区域。第一个保证交付的地理路由算法是Face Routing（Kranakis等人，1999; Bose和Morin，1999）。该协议沿着平面图的面行走，并沿着连接源和目的地的线前进。面路由已经与贪婪转发相结合，其中每个节点将待路由的消息转发到相对于目的地位于“最佳”位置的其邻居。 GOAFR+（Kuhn等人，2008）是贪婪路由和面路由的组合。该算法试图以贪婪的方式路由，如果它遇到局部极小值相对于到目的地的距离，它切换到面路由。定位移动节点有助于检查点和恢复成本，因此，所提出的协议利用了网络的路由协议。我们的方法使用GOAFR+路由消息的目的地节点不BNBNBN BNBCN xBN yBN zBCN uBCNx BCNz(a)（b）第（1）款图3网络主干合成。（a）BCN至BN的转化：条件2。（b）BCN到BN的转化：条件3BCN uBN y408P.K. Jaggi，A.K. 辛格与发送者在同一个集群中。检查点的方法都没有利用网络中的路由协议来有效地实现。一旦网络主干被合成，BN之间的互连可以被建模为图G（V，E）。对于基于位置的路由算法，网络图需要是平面的，即，没有交叉的边缘。平面图形以面为特征，面是由图形的边分隔的连续区域。一个加布里埃尔图（加布里埃尔和索卡尔，1969年）可以为了在单位圆盘图上实现平面性，Gabriel图可以在单位圆盘图上本地计算，因为网络节点可以通过仅检查其邻居的位置来当一个节点必须向另一个节点发送应用消息时，它将其发送到它所关联的BN。如果目的节点也在同一个集群中，BN将报文转发给目的节点，否则BN使用GOAFR+路由协议在骨干网中路由报文。当骨干网络中的节点接收到该消息时，它检查目的地节点是否在其集群内。如果没有，那么它再次使用GOAFR+路由消息，否则它将消息转发 到 目 的 地 节 点 。 可 以 注 意 到 ， 尽 管 已 经 假 设 了GOAFR+，但是所提出的检查点设置和恢复协议独立于底层路由协议。所提出的协议可以利用任何MANET路由协议与适当的适应。4.3. 故障模型由于移动台的特性以及无线链路的限制，移动环境受到限制。MH拥有有限的计算资源，例如处理器能力和存储容量。可用于MH的有效无线带宽也是有限的和动态的;取决于无线技术、共享无线链路的MH的数量等。这些特性影响MH的可用性和连接性。瞬态故障是移动环境中移动主机最容易发生的故障。瞬态故障的常见原因是电池功率的限制。我们假设MH（ON和BCN）的崩溃恢复模型，即，如果MH崩溃，它停止接收或发送消息，直到它的恢复完成。我们假设BN的故障频率低于ON。当一个BN发生故障时，另一个BCN从BCN转换为BN（由于第4.1节的规则）以保持主干连接。下一节中提出的算法有效地处理了BN5. 该算法该方案结合检查点和基于受控发送方的消息日志，提供了一个低开销的回滚恢复过程。5.1. 在BN基于发送者的日志记录要求进程将它们发送的消息记录在有限的易失性存储器中，因为接收者节点处的恢复进程可能需要从日志重放消息所提出的协议要求BN在其集群中的MH发送的任何消息之前将其记录在其易失性存储器中将其发送到目的地。由于由节点发送的消息通过BN路由，因此没有额外的通信开销用于在BN处记录它们然而，消息日志的大小要确定消息应该在发送方日志中存在的持续时间以及在此之后可以删除消息的持续时间因此，应用受控消息日志;其中在接收到接收方将不再需要该消息的信息时，从发送方BN的日志中删除该消息我们应用一个简单的策略，采用路由协议，其中一个节点发送一个确认（ACK），这些消息将永远不会被要求重新发送的。ack将是节点在最新群集检查点之前从发送方接收到的消息的最高序列号。这样的消息在其最近的检查点之前被节点接收，因此，将不需要由发送者在未来重新发送代替发送任何额外的ack消息，ack被捎带在从其BN路由到沿着与发送方相同的面定位的节点的任何后续应用消息上。任何BN，源或中间，沿路径的应用程序，阳离子消息可以附加确认的一些消息，sage较早收到的。在接收到该确认时，BN从其日志中删除该消息。在检查点设置时，BN将MH的易失性消息日志与其检查点一起在单次写入中传输定理基于受控发件人的邮件日志记录仅删除将来不会用于恢复的日志信息。证据我们用矛盾来证明这一点。假设从进程p发送到q的消息m在q发送了一个ack之后从p当进程q取得检查点C时，如图4所示，它以在前一检查点间隔中从某个进程p接收到的最新消息m'的序列号（例如SNqp）的形式发送ack在接收到确认时，p从其日志中移除m如果q失败，它将从最近的检查点状态重新开始执行。为了恢复到失败之前的状态，它需要在最近的检查点之后收到 的 消 息 。 这 些 消 息 的 序 列 号 和 ID 保 存 在 q 处 （ 在RCVD_LST中，如下一节所述）。来自p的这种消息的序列号（这里是m因此，m这与假设相矛盾。HpQC失效图4基于日志的消息记录。嗯低开销的回滚恢复以实现容错409hi5.2. 检查点考虑到集群网络的层次结构，可以在集群内部和集群之间使用不同的检查点技术。集群内的节点隶属于相同的BN，因此可以同步它们的检查点过程。在这种情况下，一组检查点（来自集群中的每个节点的一个检查点）形成集群的一致的本地检查点。群集的故障意味着其群集中的一个或多个节点的故障。此外，一组本地检查点（每个集群一个）形成全局检查点。然而，这是不可行的，以协调每个全球检查点，由于高度动态的性质，一个移动自组网，因此，检查点在每个集群是独立的。当且仅当任何一对本地检查点之间不存在任何群集间孤立消息时，全局检查点才是一致的。每个移动主机（MH），无论是ON还是BCN，都将其自身与BN相关联，用于在网络中路由应用消息。此外，该BN还用作主机为了在集群中采用本地检查点，BN向其簇中的节点广播take_chkpt消息。作为响应，每个MH将其检查点传输到BN（其也是其CSN），然后BN将检查点存储在其自己的稳定存储器中。集群处的本地检查点被周期性地获取，或者在集群中的某个MH接收到消息的情况下完成涉及发送方节点的z循环。当在集群中获取新的检查点时，MH的先前检查点从CSN处的稳定存储器中删除。集群之间的消息传递会在各个集群的检查点之间创建依赖关系。如果发送方的检查点涉及z循环，则进程接收到消息可能会使发送方进程处的检查点变得无用因此，为了检测涉及消息的发送者的检查点的z循环的形成，发送者的依赖性信息应该对接收者可用。该协议的目的是消除任何控制消息在检查点过程中，因此，MH节点的依赖性信息附加的应用程序消息。集群的进程间依赖性存储在最大大小为N的列表（即Dep_List）中的BN处，其中N是网络中BN的数量。此列表中BN的记录对应于它所依赖的BN。每个记录存储BN的ID和BN所依赖的检查点的索引。发送方BN将目的地的ID保存它为消息生成一个唯一的序列号，并将该序列号、它自己的id、它的Sent_list和它的Dep_List附加到消息中。沿着网络主干上从消息的源到目的地的路由，每个中间BN检查目的地节点是否与它关联。如果不是，它检查Sent_list是否包括与它关联的任何节点，在这种情况下，BN使用附加的Dep_List更新它自己的Dep_List（BN对公共记录取分量最大值，并添加不存在于它的Dep_list中的BN的记录）。它在转发消息之前从消息中的Sent_List中删除其成员。当消息到达目的地节点的BN时，BN在将消息发送到目的地MH之前通过使用附加到消息的Dep_list来更新其自己的Dep_listMH在接收到消息时将发送方节点的id和消息序列号保存所提出的方案可能无法防止所有无用的检查点，因为关于所有非因果依赖关系的信息可能无法通过该方法到达其预期目的地。已经证明，在不使用控制消息的情况下在线跟踪所有z循环是不可能的（Allulli等人，2007年）。我们的算法检测z-循环涉及因果关系以及非因果关系的依赖关系，在不同的进程检查点之间。仿真结果表明，该算法在不使用任何控制信息的情况下，最高可检测出34%的z圈。此外，该算法的性能随着网络流量的增加而提高。完整的检查点和消息日志算法将在下面介绍数据结构- 用于BNAff_Listi：与BNi关联的节点列表Dep_Listi（最大大小为N，其中N是网络中BN的数量）：该列表的每个记录存储BN的 id和BNi所依赖的检查点的索引。Sent_listi：已经在通信中向其发送消息的MH的列表BNiSent_Sender_agi：当BNi在CI中发送消息时，设置为1- 在MHRCVD_LSTkBN id;seq no：存储MHk在当前检查点间隔中从其接收到消息的BN的id和接收到的最新消息的序列号。CHKk：保存持有MHk检查点消息记录协议当到了在集群p中检查点的时候，BNp执行的在集群p中广播take_chkpt消息在接收到每个附属节点的检查点和RCVD_LST时，对于在先前检查点间隔中从某个集群q接收到的每个消息m，如果应用消息m然后将m的确认与m'否则向Q发送控制消息以确认M在从其BN接收take_chkpt消息时，集群中的每个节点MHk执行● 在BNp保存自己的检查点● 发送RCVD_LST至BNp● 设置CHKk=BNp当附属于BNp的MHi向附属于BNs的MHj发送应用消息时，由BNp● 将p和Dep_listp附加到m● 如果Sent_listp==1，则将Sent_listp附加到m● 使用GOAFR+的路线m●●410P.K. Jaggi，A.K. 辛格hi●2hi当BNs接收到去往MHj的 m时，BNs执行的动作● 如果MHjRAff_lists {如果（$k：m.Sent_list.MHk2Aff_lists）使用m更新Dep_Lists。_list从m中删除MHk。Sent_List Forwardm}} else if（MHj2Aff_lists）{使用m.Dep_list更新Dep_List如果（Dep_Listp [s]==CIs）{/* 消息完成一个Z字形循环 */获取一个新的检查点设置Sent_lists=0并清除Sent_lists}在MHj的消息日志中保存m将m转发到MHj}当MHj从BN p接收m时，由BNp执行的动作如果p RCVD_LST设置RCVD_LST j p;seqno=m。Seqnoelse拯救p; m： seqno在RCVD_LSTj中如果BN将其状态转换为BCN，它附属于一个新的BN，并将节点的消息日志传输到新的BN。新BN广播take_chkpt消息，使其附属节点在集群中取得本地检查点5.3. 移动主机移动主机的恢复过程是完全异步的，因为它不需要任何其他节点回滚，因此完全没有多米诺骨牌。我们认为，各种情况下的移动主机的恢复案例1：崩溃的节点恢复并从属于同一BN与失效MH的恢复相关数据在当前BN可用，因此不需要控制消息。情况2：故障节点在恢复时从属于不同的BN当前BN需要在故障之前从节点的CSN检索检查点。国阵控股的id节点的最新检查点MH k作为CHK k可用在节点自己的