On self-stabilization of multi point relays for connected dominating set in adhoc networks

Recently, Adjih proposed a source independent multipoint relay (MPR) based localized construction for small sized connected dominating set (CDS). This MPR-based CDS does not need any knowledge of global network topology, which makes it attractive to the applications in mobile adhoc networks for providing routing backbone. In this work we introduce a reverse selection heuristics and provided self-stabilization (SS) to MPR-based CDS algorithm. This SS-MPR-CDS provides tolerance to SS-MPR-CDS based virtual backbone from transient changes in topology. Our SS-MPR-CDS algorithm stabilizes with complexity of O(n.¿
³
) moves, where ¿ is maximum degree of node.