Near Optimal Multicriteria Spanner Constructions in Wireless Ad-Hoc Networks

This paper studies asymmetric power assignments for which the induced communication graph is a good spanner of the Euclidean graph, induced on the wireless nodes V, while the total energy is minimized. We propose two spanner models: distance and energy. We consider a random wireless ad-hoc network with |V| = n nodes distributed uniformly and independently in a unit square. For the first model, we propose an approximation algorithm, which constructs a power assignment so that the induced network is an O ((1 + alpha)(n-m)/m log n + alpha)-spanner of G_v with high probability, such that the total energy is at most betaldrm+2 times the optimum, for any alpha > 1, beta ges 1 + 2/(alpha-1), and any positive integer m les n in O(mn²) time. For the second model, we develop a power assignment such that the resulting network is a 2-spanner with a total energy of at most O(log n) times the optimum in O(n⁴ log n) time. We also analyze a power assignment developed and show it is a low cost good k-fault resistant spanner. To the best of our knowledge, these are the first provable theoretic results for low cost spanners in wireless ad-hoc networks.