Movement-Based Checkpointing and Message Logging for Recovery in MANETs

Mobile ad hoc networks (MANETs) are increasingly being employed for expanding the computing capabilities of existing cellular mobile systems and in the implementation of mobile computing grids. However, MANETs are susceptible to various transient as well as permanent failures and a fault tolerance technique is crucial in order to effectively utilize the constituent nodes as viable compute resources. Checkpointing and message logging based rollback recovery is a well established approach to provide fault tolerance in static and cellular mobile distributed systems; yet its use for achieving fault tolerance in MANETs is comparatively less explored. The existing recovery algorithms cannot be applied directly to MANETs due to their insufficiency in handling challenges like absence of static infrastructure, frequent node movement, constrained wireless bandwidth and limited stable storage. In this paper, we propose a checkpointing based rollback recovery protocol for clustered MANETs that determines the checkpointing frequency of a mobile node based on its mobility; thereby avoiding unnecessary checkpoints. The protocol uses a popular graph theoretic construct called connected dominating set to lower the communication overhead due to the recovery procedure. The findings of our scheme have been substantiated by the complexity analysis and simulation under varying network conditions.