Self-Stabilizing Virtual Backbone Construction in Selfish Wireless Ad-Hoc Networks

Self-Stabilizing Virtual Backbone Construction in Selfish Wireless Ad-Hoc Networks

Abstract

Self-stabilization is a key property of fault-tolerant distributed computing systems. A self-stabilizing algorithm ensures that the system eventually converges to a legitimate configuration from arbitrary initializations without any external intervention, and it remains in that legitimate configuration as long as no transient fault occurs. In wireless ad-hoc networks, a connected dominating set is the graph-theoretic counterpart of a virtual backbone. In this paper, we propose two distributed self-stabilizing algorithms for approximate minimum connected dominating set construction with provable perturbation-proof property in the sense that the legitimate configuration of the system corresponds to a Nash equilibrium (NE). Our first algorithm, namely MCDSpf, always results in an NE configuration regardless of the specifics of the nodes’ utility functions, while the configurations reached in our second algorithm, called MCDSpf*, are NE only if the selfish nodes explicitly prefer to be out of the virtual backbone. MCDSpf* suits in particular for scenarios with multiple legitimate configurations, while MCDSpf always gives rise to a unique configuration. Both algorithms increase accessibility, reduce the number of update messages during convergence, and stabilize with minimum changes in the topological structure. However, the underlying assumption in both MCDSpf and MCDSpf* algorithms is that the nodes do not deviate from the rules of the system during convergence to a legitimate configuration. We propose a third algorithm, called sMIS, which also relaxes this assumption. The simulation results show that our algorithms outperform comparable schemes in terms of stabilization time and the number of state transitions.

References