Conference
Version
T. Calamoneri, A.F. Clementi, E. Fusco, R. Silvestri
Abstract
We consider static ad-hoc wireless networks where nodes have the same initial battery charge and they may dynamically change their transmission range at every time slot. When a node v transmits with range r(v) , its battery charge is decreased by Beta x r(v)^2, where Beta >0 is a fixed constant. The goal is to provide a range assignment schedule that maximizes the number of broadcast operations from a given source (this number is denoted as the length of the schedule). This maximization problem, denoted as Max LifeTime, is known to be NP-hard and the best algorithm yields worst-case approximation ratio Theta(log n), where n is the number of nodes of the network. We consider random geometric instances formed by selecting $n$ points independently and uniformly at random from a square of side length sqrt{n} in the Euclidean plane. We first present an efficient algorithm that constructs a range assignment schedule having length, with high probability, not smaller than 1/12 of the optimum. We then design an efficient distributed version of the above algorithm where nodes initially know $n$ and their own position only. The resulting schedule guarantees the same approximation ratio achieved by the centralized version thus obtaining the first distributed algorithm having provably-good performance for this problem.
PDF Files