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
Ön\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.
Research partially supported by the European Union under the Project IP-FP6-015964 AEOLUS.