Energy-efficient broadcasting in wireless ad hoc networks
Di Yuan · 2005
Broadcasting in wireless ad hoc networks can use a virtual backbone formed by a connected dominating set (CDS). If nodes use constant and identical transmission power, energy-efficient broadcasting amounts to minimizing the size of the backbone (i.e., CDS cardinality). This is referred to as the minimum connected dominating set (MCDS) problem. We present two feasibility conditions, and show that each of the conditions is both sufficient and necessary for characterizing a CDS. The first condition yields an integer programming model, which allows us to compute an MCDS for networks of moderate size (up to 80 nodes in our experiments). The second condition leads to a class of distributed algorithms. We compare numerically the performance of this class of algorithms to that of a centralized algorithm, as well as to MCDS found using the integer programming model. Our performance evaluation suggests that the class of algorithms presented in this paper have a close-optimal performance. In addition, we highlight possible algorithm extensions to cope with timing and mobility issues.