• Calendar

May 5, Wednesday
12:00 – 13:30

A power assignment is an assignment of transmission power to each of the nodes of a wireless network, so that the induced communication graph has some desired properties. The cost of a power assignment is the sum of the powers. The {em energy} of a transmission path from node $u$ to node $v$ is the sum of the squares of the distances between adjacent nodes along the path. For a constant $t >1$, an energy $t$-spanner is a graph $G'$, such that for any two nodes $u$ and $v$, there exists a path from $u$ to $v$ in $G'$, whose energy is at most $t$ times the energy of a minimum-energy path from $u$ to $v$ in the complete Euclidean graph.

We study the problem of finding a power assignment, such that (i) its induced communication graph is a `good' energy spanner, and (ii) its cost is `low'. We show that for any constant $t >1$, one can find a power assignment, such that its induced communication graph is an energy $t$-spanner, and its cost is bounded by some constant times the cost of an optimal power assignment (where the sole requirement is strong connectivity of the induced communication graph).

Based on joint work with Rom Aschner, Paz Carmi and Matya Catz.