Efficient distributed topology control in 3-dimensional wireless networks

Distributed topology control mechanisms for 3-dimensional settings are of considerable interest for automated network configuration in diverse applications including structural monitoring networks and underwater networks. The 3-D CBTC technique proposed by Bahramgiri et al. [7] has a complexity of O(d(3) log d), where d represents the average number of neighbors per node. We present two efficient alternatives. The first is a heuristic based on 2-D orthographic projections that provides excellent performance in practice, but is theoretically not guaranteed to produce a connected network. The second is a more rigorous approach based on spherical Delaunay triangulation (SDT). Both have significantly better running times that scale as O(d log d). Our simulation results indicate that network topologies generated based on the SDT algorithm have substantially lower average node degree and average transmission power level compared to the original network for random deployments.