Conference
Version
T. Calamoneri, A.E.F. Clementi, A. Monti, G. Rossi, R. Silvestri
Abstract
The min energy broadcast problem consists in assigning transmission ranges to the nodes of an ad-hoc (wireless) network in order to guarantee a directed spanning tree from a given source node and, at the same time, to minimize the energy consumption (i.e. the cost) yielded by the range assignment. Min energy broadcast is known to be \np-hard. We provide the first analytical results for this problem on random instances. Namely, we consider random-grid networks where nodes are chosen independently at random from the set of $n$ points of a n^{1/2} x n^{1/2} square grid in the plane. The probability of the existence of a node at a given point of the grid does depend on that point, that is, the probability distribution can be non-uniform. \noindent By using information-theoretic arguments, we prove a lower bound (1-epsilon)/(n pi) on the cost of any feasible solution for this problem. Then, we provide an efficient solution of cost not larger than 1.1204/(n pi) and that uses a logarithmic number of different transmission ranges. A major challenge in this topic is the development of efficient distributed algorithms. To this aim, we first derive a very simple solution that uses only one positive range value (having the same asymptotical order of the connectivity threshold) and it has cost not larger than 8n. Then, we show how this solution can be converted into an efficient protocol where nodes initially know n and their own position only. The energy load is well balanced and, at the same time, the work complexity (i.e. the energy due to all message transmissions of the protocol) is equivalent to the cost of the centralized version, so it is only a constant factor larger than the optimum. The approximation quality of our distributed solution is also experimentally tested.
PDF Files