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 {em 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, where unidirectional links are considered. To study the virtual backbone construction in disk graphs, we consider two problems: Strongly Connected Dominating Set (SCDS) and Strongly Connected Dominating and Absorbing Set (SCDAS). We propose a constant approximation algorithm and discuss its improvements for the SCDS problem . We also propose a heuristic for the SCDAS problem. Through extensive simulations, we verify our theoretical analysis and also demonstrate that the SCDS can be extended to form an SCDAS with marginal extra overhead.