Name
Abstract | ||
|---|---|---|
This paper formally establishes that random access scheduling schemes, and, more specifically CSMA-CA, yields exceptionally good performance in the context of wireless multihop networks. While it is believed that CSMA-CA performs significantly worse than optimal, this belief is usually based on experiments that use rate allocation mechanisms which grossly underutilize the available capacity that random access provides. To establish our thesis we compare the max-min rate allocation achieved by CSMA-CA and optimal in multi-hop topologies and find that: (i) CSMA-CA is never worse than 16% of the optimal when ignoring physical layer constraints, (ii) in any realistic topology with geometric constraints due to the physical layer, CSMA-CA is never worse than 30% of the optimal. Considering that maximal scheduling achieves much lower bounds than the above, and greedy maximal scheduling, which is one of the best known distributed approximation of an optimal scheduler, achieves similar worst case bounds, CSMA-CA is surprisingly efficient. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1109/INFCOM.2010.5462253 | IEEE INFOCOM |
Keywords | Field | DocType |
max-min rate allocation,random access,physical layer,random access scheduling scheme,greedy maximal scheduling,optimal scheduler,wireless multi-hop network,use rate allocation mechanism,maximal scheduling,available capacity,physical layer constraint,approximation algorithms,schedules,throughput,protocols,topology,interference,resource allocation,resource management,csma ca,scheduling algorithm,network topology,scheduling,spread spectrum communication,lower bound | Approximation algorithm,Scheduling (computing),Computer science,Computer network,Network topology,Schedule,Physical layer,Resource allocation,Carrier sense multiple access with collision avoidance,Distributed computing,Random access | Conference |
Citations | PageRank | References |
1 | 0.35 | 12 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Apoorva Jindal | 1 | 306 | 15.79 |
| Ann Arbor | 2 | 1 | 0.35 |
| Konstantinos Psounis | 3 | 4042 | 222.36 |