Connected Dominating Sets in Wireless Networks with Different Transmission Ranges

Abstract

Since there is no fixed infrastructure or centralized management in wireless ad hoc networks, a Connected Dominating Set (CDS) has been proposed as the virtual backbone. The CDS of a graph representing a network has a significant impact on an efficient design of routing protocols in wireless networks. This problem has been studied extensively in Unit Disk Graphs (UDG), in which each node has the same transmission range. However, in practice, the transmission ranges of all nodes are not necessary equal. In this paper, we model a network as a disk graph and introduce the CDS problem in disk graphs. We present three constant approximation algorithms to obtain a minimum CDS of a given network. These algorithms can be implemented as distributed algorithms. Furthermore, we show the size relationship between a maximal independent set and a CDS as well as the bound of the maximum number of independent neighbors of a node in disk graphs. The theoretical analysis and simulation results are also presented to verify our approaches.