On Calculating Stable Connected Dominating Sets Based on Link Stability for Mobile Ad Hoc Networks

Abstract

In amobile ad hoc network (MANET), routing based on aconnected dominating set (CDS) has been recognized as a promising approach. This is because as long as topological changes in a MANET do not affect its CDS, there is no need to reconfigure its CDS, which makes the routing tables in its CDS still valid. Due to the dynamic nature and the limited battery power of the mobile nodes, communication links between two nodes may break frequently. Such a phenomenon may destroy the structure of CDS, thus making reconfiguration of CDS unavoidable. Reconfiguring a CDS will result in high overheads caused by its re-computation and heavy information exchanges among the participating nodes. Therefore, a more stable CDS will directly lead to the performance improvement of the whole MANET. In this study, an efficient distributed algorithm is proposed that can establish a stable CDS by keeping a node with many weak links from being selected as a member of CDS. Computer simulations show that the CDSs generated by the proposed CDS-forming algorithm are more stable than those generated by other CDS-forming algorithms.