Maximizing the Number of Broadcast Operations in Static Random Geometric Ad-Hoc Networks

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 β×r(v)2 where β> 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 , is known to be -hard and the best algorithm yields worst-case approximation ratio Θ(logn), where n is the number of nodes of the network [5]. We consider random geometric instances formed by selecting n points independently and uniformly at random from a square of side length 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.