An Algorithm for Constructing Strongly Connected Dominating and Absorbing Sets in Wireless Networks with Unidirectional Links

It is effective to construct a strongly connected dominating and absorbing set (SCDAS) instead of a virtual backbone network in a wireless network with unidirectional links. However, there exist few studies on the strongly connected dominating and absorbing sets in wireless networks. In this paper, we propose an addition-based localized heuristic algorithm for constructing a SCDAS in a wireless network. The algorithm can obtain a small SCDAS with a constant approximation ratio through three executive phases. Theoretical analysis demonstrates the correctness of our algorithm.