Name
Abstract | ||
|---|---|---|
The Minimum-Energy Broadcast problem is to assign a transmission range to every station of an ad hoc wireless networks so that (i) a given source station is allowed to perform broadcast operations and (ii) the overall energy consumption of the range assignment is minimized. We prove a nearly tight asymptotical bound on the optimal cost for the Minimum-Energy Broadcast problem on square grids. We also derive near-tight bounds for the Bounded-Hop version of this problem. Our results imply that the best-known heuristic, the MST-based one, for the Minimum-Energy Broadcast problem is far to achieve optimal solutions (even) on very regular, well-spread instances: its worst-case approximation ratio is about @p and it yields @W(n) hops, where n is the number of stations. As a by product, we get nearly tight bounds for the Minimum-Disk Cover problem and for its restriction in which the allowed disks must have non-constant radius. Finally, we emphasize that our upper bounds are obtained via polynomial time constructions. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.tcs.2008.02.005 | Theor. Comput. Sci. |
Keywords | Field | DocType |
source station,range assignment,tight bound,optimal cost,overall energy minimization,ad hoc wireless networks,transmission range,disk cover,disk cover problem,grid wireless network,minimum-energy broadcast problem,optimal solution,bounded-hop version,minimum-disk cover problem,broadcast problem,tight asymptotical,polynomial time,upper bound,wireless network,ad hoc wireless network | Discrete mathematics,Wireless network,Combinatorics,Heuristic,Polynomial,Upper and lower bounds,Wireless ad hoc network,Circle packing,Time complexity,Mathematics,Grid | Journal |
Volume | Issue | ISSN |
399 | 1-2 | Theoretical Computer Science |
Citations | PageRank | References |
7 | 0.77 | 14 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tiziana Calamoneri | 1 | 511 | 46.80 |
| Andrea E. F. Clementi | 2 | 1168 | 85.30 |
| Miriam di Ianni | 3 | 144 | 17.27 |
| Massimo Lauria | 4 | 122 | 14.73 |
| Angelo Monti | 5 | 671 | 46.93 |
| Riccardo Silvestri | 6 | 1324 | 90.84 |