Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networks
In this paper we show that the CSMA IEEE 802.11 protocol (Wifi) provides packet access delays asymptotics in power law. This very feature allows us to specify optimal routing via polynomial algorithm while the general case is NP-hard.
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2005-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3375/pdf |
| _version_ | 1797270644885291008 |
|---|---|
| author | Philippe Jacquet Amina Meraihi Naimi Georgios Rodolakis |
| author_facet | Philippe Jacquet Amina Meraihi Naimi Georgios Rodolakis |
| author_sort | Philippe Jacquet |
| collection | DOAJ |
| description | In this paper we show that the CSMA IEEE 802.11 protocol (Wifi) provides packet access delays asymptotics in power law. This very feature allows us to specify optimal routing via polynomial algorithm while the general case is NP-hard. |
| first_indexed | 2024-04-25T02:07:33Z |
| format | Article |
| id | doaj.art-aa648fc19c9141a78e4cf8940a78d78f |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:07:33Z |
| publishDate | 2005-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-aa648fc19c9141a78e4cf8940a78d78f2024-03-07T14:30:52ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502005-01-01DMTCS Proceedings vol. AD,...Proceedings10.46298/dmtcs.33753375Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networksPhilippe Jacquet0Amina Meraihi Naimi1Georgios Rodolakis2École polytechniqueÉcole polytechniqueÉcole polytechniqueIn this paper we show that the CSMA IEEE 802.11 protocol (Wifi) provides packet access delays asymptotics in power law. This very feature allows us to specify optimal routing via polynomial algorithm while the general case is NP-hard.https://dmtcs.episciences.org/3375/pdfprotocol performancepower lawdelay routingmobile ad hoc networks[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds][info.info-dm] computer science [cs]/discrete mathematics [cs.dm][math.math-co] mathematics [math]/combinatorics [math.co][info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| spellingShingle | Philippe Jacquet Amina Meraihi Naimi Georgios Rodolakis Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networks Discrete Mathematics & Theoretical Computer Science protocol performance power law delay routing mobile ad hoc networks [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| title | Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networks |
| title_full | Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networks |
| title_fullStr | Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networks |
| title_full_unstemmed | Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networks |
| title_short | Performance of binary exponential backoff CSMA in WiFi and optimal routing in mobile ad hoc networks |
| title_sort | performance of binary exponential backoff csma in wifi and optimal routing in mobile ad hoc networks |
| topic | protocol performance power law delay routing mobile ad hoc networks [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-cg] computer science [cs]/computational geometry [cs.cg] |
| url | https://dmtcs.episciences.org/3375/pdf |
| work_keys_str_mv | AT philippejacquet performanceofbinaryexponentialbackoffcsmainwifiandoptimalroutinginmobileadhocnetworks AT aminameraihinaimi performanceofbinaryexponentialbackoffcsmainwifiandoptimalroutinginmobileadhocnetworks AT georgiosrodolakis performanceofbinaryexponentialbackoffcsmainwifiandoptimalroutinginmobileadhocnetworks |