A partition prediction algorithm for service replication in mobile ad hoc networks

Due to the mobility of nodes in ad hoc networks, network topology is dynamic and unpredictable, which leads to frequent network partitioning. This partitioning disconnects many nodes from the centralized server. Being aware of future partitioning can help to provide a continuous service availability for all mobile nodes. In this paper, we propose a partition prediction algorithm, based on: (i) the partition detection mechanism used by TORA routing protocol and (ii) the residual link lifetime of wireless links. The node that predicts network partitioning, demands the server node to replicate the service in the future separate partition before its disconnection. We propose also a scheme that describes how the service replicas are dynamically deployed in the network. Using linear time temporal logic, we show that whenever a partition is detected, then it has been predicted before. Our analysis of complexity shows that the proposed algorithm guarantee the service availability to each mobile node without incurring high cost.