Improved Multi-criteria Spanners for Ad-Hoc Networks Under Energy and Distance Metrics

This paper studies the problem of topology control in random wireless ad-hoc networks through power assignment for n nodes uniformly distributed in a unit square. In particular, we are interested in asymmetric power assignments so that the induced communication graph has a good distance and energy stretch simultaneously, with additional optimization objectives: both minimizing the total energy consumption, interference level, hop-diameter, and maximizing the network lifetime. We present several power assignments with varying construction time complexity. The probability of our results converges to one as the number of network nodes, n, increases. To the best of our knowledge, these are the first results for spanner construction in wireless ad-hoc networks with provable bounds for both, energy and distance, metrics simultaneously.