Network Lifetime and Power Assignment in Ad-Hoc Wireless Networks
 

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)