Name
Title | ||
|---|---|---|
Practical Scheduling Algorithms for Concurrent Transmissions in Rate-adaptive Wireless Networks |
Abstract | ||
|---|---|---|
Optimal scheduling for concurrent transmissions in rate-nonadaptive wireless networks is NP-hard. Optimal scheduling in rate-adaptive wireless networks is even more difficult, because, due to mutual interference, each flow's throughput in a time slot is unknown before the scheduling decision of that slot is finalized. The capacity bound derived for rate-nonadaptive networks is no longer applicable either. In this paper, we first formulate the optimal scheduling problems with and without minimum per-flow throughput constraints. Given the hardness of the problems and the fact that the scheduling decisions should be made within a few milliseconds, we propose two simple yet effective searching algorithms which can quickly move towards better scheduling decisions. Thus, the proposed scheduling algorithms can achieve high network throughput and maintain long-term fairness among competing flows with low computational complexity. For the constrained optimization problem involved, we consider its dual problem and apply Lagrangian relaxation. We then incorporate a dual update procedure in the proposed searching algorithm to ensure that the searching results satisfy the constraints. Extensive simulations are conducted to demonstrate the effectiveness and efficiency of the proposed scheduling algorithms which are found to achieve throughputs close to the exhaustive searching results with much lower computational complexity. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/INFCOM.2010.5462013 | INFOCOM |
Keywords | Field | DocType |
optimisation,long-term fairness,np-hard,network throughput,rate-adaptive wireless network,data communication,radiofrequency interference,optimal scheduling,proposed scheduling algorithm,lagrangian relaxation,practical scheduling algorithms,concurrent transmission,better scheduling decision,mutual interference,radio networks,computational complexity,decision scheduling,optimal scheduling problem,constrained optimization problem,dual problem,concurrent transmissions,practical scheduling algorithm,minimum per-flow throughput constraint,high network throughput,rate adaptive wireless networks,scheduling decision,dual update procedure,adaptive scheduling,np hard,scheduling algorithm,wireless networks,wireless network,interference,scheduling,wireless communication,exhaustive search,throughput,constraint optimization,search algorithm,satisfiability,computational modeling | Fixed-priority pre-emptive scheduling,Mathematical optimization,Fair-share scheduling,Computer science,Two-level scheduling,Maximum throughput scheduling,Rate-monotonic scheduling,Dynamic priority scheduling,Earliest deadline first scheduling,Round-robin scheduling,Distributed computing | Conference |
ISSN | ISBN | Citations |
0743-166X | 978-1-4244-5836-3 | 11 |
PageRank | References | Authors |
0.82 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhe Yang | 1 | 184 | 9.77 |
| lin x cai | 2 | 2956 | 220.61 |
| Wu-Sheng Lu | 3 | 296 | 24.90 |