On construction of virtual backbone in wireless ad hoc networks with unidirectional links
Since there is no fixed infrastructure in wireless ad hoc networks, virtual backbone has been proposed as the routing infrastructure to alleviate the broadcasting storm problem. The virtual backbone construction has been studied extensively in undirected graphs, especially in unit disk graphs, in which each node has the same transmission range. In practice, however, transmission ranges of all nodes are not necessarily equal. In this paper, we model such a network as a disk graph (DG), where unidirectional links are considered. To study the virtual backbone construction in DGs, we consider two problems: Strongly Connected Dominating Set (SCDS) and Strongly Connected Dominating and Absorbing Set (SCDAS). We propose a constant approximation algorithm and present its improvements for the SCDS problem. Based on the solutions of SCDS, we discuss how to maintain its constant approximation ratio for SCDAS and also propose an efficient heuristic. Through extensive simulations, we verify our theoretical analysis and demonstrate that the SCDS can be extended to form an SCDAS with a marginal extra overhead.
virtual backbone wireless ad hoc network disk graph strongly connected dominating set strongly connected dominating and absorbing set directed graph