Energy efficiency has recently become one of the most critical issues in
routing of ad-hoc networks. We consider the following two relevant optimization
formulations: (1) a previously known Power Assignment problem seeking to
minimize the total power assigned to all nodes subject to given network topology
requirement such as strong connectivity, symmetric connectivity and (multi)broadcast
and (2) a newly introduced Network Lifetime problem seeking for a schedule
of power assignments with the maximum time span such that each power assignment
satisfies given network topology requirement and the total amount of energy used
by each node v does not exceed its initial battery supply.
For the Power Assignment problem with transmission power requirements given by
an arbitrary directed graph, we present asymptotically optimal O(log
n)-approximation algorithms for strong connectivity, symmetric connectivity, and
broadcast. For symmetric connectivity in the metric (or Euclidean) case with
power requirement p(u,v)= ||u,v||^{kappa}/e(u), where ||u,v|| is the Euclidean
distance, kappa is a constant between 2 and 5 and e(u) is the power efficiency
of the transmission node u, we present a simple constant-factor approximation
algorithm.
For the Network Lifetime problem we give the first approximation algorithms
based on the PTAS for packing linear programs of Garg and Konemann. The
approximation ratio for each case of the Network Lifetime problem is equal to
the approximation ratio of the corresponding Power Assignment problem with
non-uniform transmission efficiency.
Joint work with S. Kapoor (IIT-Chicago), A. Olshevsky (Georgia Tech), and A.
Zelikovsky (Georgia State)