Min-Energy Broadcast with Hitch-hiking

Abstract: 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^2 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. All the results hold for Unicast as well.

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)^kappa, where d(u,v) the Euclidean distance between u and v and kappa 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.

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 -> R+, and a source s in V. The output consists of a permutation tau = v1, v2, ..., vn of V with v_1 = s and power assignment p(v) of every vertex v. For every 1 <=i < j <= n, define q(vi,vj) = p(vi)/c(vi,vj). An output is feasible if for every j > 1 we have sum_{i=1}^{j-1} q(vi,vj) >= 1. The objective is to minimize sum_{i=1}^n p(vi).

Event Topic

Discrete Applied Math Seminar