Self-stabilizing algorithm for high service availability in spite of concurrent topology changes in ad hoc mobile networks

Mobile nodes in ad hoc networks move freely and run out of battery power so quickly, which leads to frequent network partitioning. Network partitioning considerably reduces service availability when the server node is not in the same partition as the client nodes. In order to provide a continuous service availability for all mobile nodes, we propose a self-stabilizing algorithm that can tolerate multiple concurrent topological changes and can incur a cost of one server per long-lived connected component. By using (1) the time interval-based computations concept that distinguishes between disjoint and concurrent computations, and (2) Markov chain model, the proposed algorithm can within a finite time converge to a legitimate state even if topological changes occur during the convergence time. Our simulation results show that the algorithm can ensure very high service availability, and each node has a strong path to the server of its network component over 98% of the time.