Analytical bounds on broadcast with hitch-hiking in wireless ad-hoc networks

Recently, there have been papers indicating that the maximal ratio combiner device can result in energy savings in wireless ad hoc networks by using hitch-hiking. We study the min-energy broadcast with hitch-hiking problem, an idealized version of broadcast using hitch-hiking, a problem studied experimentally in the INFOCOM 2004 paper of Agarwal et al. min-energy broadcast with hitch-hiking captures the maximum savings one can achieve in broadcasting using maximal ratio combiners. We show that the optimum of the classical min-energy broadcast problem is at most O(log² n) times the optimum of min-energy broadcast with hitch-hiking, where n is the number of nodes in the networks. We show that this bound is tight up to a constant. In the special case when the nodes are on a line and the power requirement for node u to reach node v is d(u,v)^K where d(u,v) the Euclidean distance between u and v and K is the signal attenuation exponent, which is assumed to be in between 2 and 5, we show that the optimum of the min-energy broadcast problem is at most a constant times optimum of min-energy broadcast with hitch-hiking. We also show that min-energy broadcast with hitch-hiking is NP-Hard, and present approximation algorithms. A formal definition of min-energy broadcast with hitch-hiking is given below. The input consists of a complete directed graph G = (V, E) with power requirement function c: E rarr R ⁺, and a source s isin V. The output consists of a permutation T = < v₁, v₂,...., v_n > of V with v₁ = s and power assignment p(v) of every vertex v. For every 1 les i < j les n, define q(v_iv _j) = p(v_i)/c(v_iv_j). An output is feasible if for every j > 1 we have Sigmaⁿ _i=1 p(v_i)