A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks

Wireless ad hoc networks have been widely used in many areas. In order to improve network performance, we often select a connected dominating set (CDS) as its virtual backbone to deal with routing-related tasks. The problem of finding a minimum CDS (MCDS) for 2-dimensional networks has been widely studied, whereas finding an MCDS in 3-dimensional networks draws more attention recently, because it can formulate the network environment more precisely. Since MCDS problem is proved to be NP-complete, lots of approximations were proposed in literature. Among those, the best approximation for MCDS in 3D network is 14.937 in [1]. However, their projection method during the approximation deduction process is incorrect, which overthrows its final bound completely. As a consequence, in this paper we will first propose a new projection method to overcome their problem, illustrate the cardinality upper bound of independent points in a graph (which will be used to analyze the approximation ratio), and then optimize the algorithms to select MCDS with prune techniques. The major technique we use is an adaptive jitter scheme, which solves the open question in this area.