S.S. Ravi
Topology control problems are concerned with the assignment of power values to nodes of an ad hoc network so that the power assignment leads to a graph topology satisfying some specified properties. We consider such problems under several optimization objectives, including minimizing the maximum power and minimizing the total power. We present a general approach that leads to a polynomial algorithm for minimizing the maximum power for a class of graph properties, called monotone properties. Problems involving the minimization of total power are known to be NP-complete even for simple graph properties. We present a general approach that leads to approximation algorithms for minimizing the total power for some monotone properties. Examples of approximation algorithms developed using this approach for several monotone graph properties (e.g. 2-node-connected, bounded diameter) will be presented.
This ongoing research is being carried out jointly with Sven Krumke (ZIB, Berlin), Errol Lloyd (University of Delaware), Rui Liu (University of Delaware), Madhav Marathe (Los Alamos National Laboratories) and Ram Ramanathan (BBN).