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 [5]. We consider random geometric instances formed by selecting n points independently and uniformly at random from a square of side length root 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.
Maximizing the number of broadcast operations in static random geometric ad-hoc networks / Calamoneri, Tiziana; Andrea, Clementi; Fusco, EMANUELE GUIDO; Silvestri, Riccardo. - STAMPA. - 4878:(2007), pp. 247-259. (Intervento presentato al convegno 11th International Conference on Principles of Distributed Systems tenutosi a Guadeloupe, GUADELOUPE nel DEC 17-20, 2007) [10.1007/978-3-540-77096-1_18].
Maximizing the number of broadcast operations in static random geometric ad-hoc networks
CALAMONERI, Tiziana;FUSCO, EMANUELE GUIDO;SILVESTRI, RICCARDO
2007
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 [5]. We consider random geometric instances formed by selecting n points independently and uniformly at random from a square of side length root 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.