Name
Title | ||
|---|---|---|
Maximizing the number of broadcast operations in static random geometric ad-hoc networks |
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 β × 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 MAX LIFETIME, is known to be NP-hard and the best algorithm yields worst-case approximation ratio Θ(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 √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. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-77096-1_18 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
algorithm yield,transmission range,approximation ratio,battery charge,resulting schedule,n point,broadcast operation,side length,efficient algorithm,log n,random geometric ad-hoc network,range assignment schedule,ad hoc network,distributed algorithm,ad hoc wireless network | Battery charge,Discrete mathematics,Binary logarithm,Wireless network,Broadcasting,Computer science,Distributed algorithm,Euclidean geometry,Wireless ad hoc network,Maximization,Distributed computing | Conference |
Volume | ISSN | ISBN |
4878 | 0302-9743 | 3-540-77095-X |
Citations | PageRank | References |
1 | 0.35 | 23 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tiziana Calamoneri | 1 | 511 | 46.80 |
| andrea e f clementi | 2 | 17 | 1.34 |
| Emanuele G. Fusco | 3 | 86 | 9.03 |
| Riccardo Silvestri | 4 | 1324 | 90.84 |