移动Ad Hoc网络混合检查点策略

A Hybrid Checkpointing Strategy for Mobile Ad Hoc Networks

考虑到移动Ad Hoc网络无固定中心节点、多跳路由和资源有限等特点,基于分簇移动Ad Hoc网络结构,提出了一种结合同步和异步检查点技术的混合检查点策略,即同簇终端检查点必须保持同步,而异簇终端检查点保持独立.首先讨论了混合检查点模型及其正确性准则.然后,基于簇内及簇间检查点依赖图,讨论了不同类型检查点清除规则.最后,给出了相应的检查点及回滚恢复算法,并证明了回滚恢复的正确性.所提出的混合检查点策略既能避免同簇进程级联回滚所引起的资源浪费、又能避免异簇终端之间过多跨簇消息传递及减少无线通信延迟.实验结果表明,与单纯的同步及异步检查点策略相比,所提出的检查点策略是一种综合考虑移动Ad Hoc网络各种资源约束的较好折中方案,且具有恢复时间短、对簇头依赖小、灵活性好等优点.

Considering the features of mobile Ad Hoe networks such as lack of center nodes,multihops routing and limited resources,a hybrid checkpointing strategy combining synchronous checkpointing and asynchronous checkpointing is suggested for clustering-based Ad Hoc networks.Namely,the checkpoints in the same cluster must keep synchronous,while the checkpoints in different clusters are independent.Firstly,a hybrid checkpointing model and its correctness criteria are discussed.Then,the elimination rules of different kinds of checkpoints are suggested based on the intra-cluster and inter-cluster checkpoint dependency graphs.Finally,the algorithms of checkpointing and rollback recovery are given,and the correctness of recovery is proved.The proposed strategy can not only avoid resource waste due to cascading rollback among the processes in the same clusters,but also avoid too much message transmission among the processes in different clusters,to reduce the wireless communication delay largely.Experiment results show that,comparing with the pure synchronous and pure asynchronous checkpointing methods,the proposed hybrid checkpointing strategy is a flexible and good trade-off scheme taking all kinds of resource constraints of Ad Hoc networks into account,and has the advantages such as short recovery time,less dependence on cluster heads.