Abstract | ||
---|---|---|
In this paper, a family of integer linear programs is formulated for performing collision free scheduling in Spatial-TDMA wireless mesh networks. We extend previous formulations for power aware STDMA scheduling to include discrete power transmission and multi-rate support via adaptive constellation selection. Despite the theoretical attractiveness of these (mixed) integer linear programs, STDMA scheduling problems are in general intractable (NP-hard problems). Thus, the practicality of providing optimal solutions is rather limited. To this end, we study approximation algorithms that are based on linear programming relaxation and randomized rounding. Based on these approximation algorithms we focus our study on the trade-off between optimality of the solution and feasibility. Conducted numerical investigations aim to vindicate the claim regarding the strength of randomized algorithms. In that respect the performance of the approximation algorithms under different scenarios, such as the number of active links and number of nodes in the mesh network, is investigated. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1109/VTCF.2006.245 | Montreal, Que. |
Keywords | DocType | ISSN |
integer programming,linear programming,radio links,scheduling,space division multiple access,time division multiple access,adaptive constellation selection,approximation algorithms,collision free scheduling,discrete power transmission,integer linear programs,link scheduling,multirate support,nonindependent randomized rounding,spatial-TDMA networks,wireless mesh networks | Conference | 1550-2252 |
ISBN | Citations | PageRank |
1-4244-0063-5 | 3 | 0.43 |
References | Authors | |
8 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Friderikos, V. | 1 | 34 | 2.58 |
Katerina P. Papadaki | 2 | 169 | 15.85 |
Wisely, D. | 3 | 10 | 2.54 |
A. Hamid Aghvami | 4 | 3 | 0.43 |