John Heidemann / Papers / Contention Analysis of MAC Protocols that Count

Contention Analysis of MAC Protocols that Count
Affan A
USC/Information Sciences Institute

Citation

Affan A. Syed and John Heidemann. Contention Analysis of MAC Protocols that Count. Proceedings of the Fifth ACM International Workshop on UnderWater Networks (WUWNet) (Woods Hole, Massachusetts, USA, Sep. 2010), 2:1–2:8. [DOI] [PDF] [alt PDF]

Abstract

The key aspect in the design of any contention-based medium access control (MAC) protocol is the mechanism to measure and resolve simultaneous contention. Generally, terrestrial wireless MACs can only observe success or collision of a contention attempt through carrier sense. An implicit estimate of the number of contenders occurs through repeated observation and changing back-off contention window. Recent work in underwater MAC protocols suggest there it is possible to directly count the number of contenders by exploiting the spatio-temporal uncertainty inherent to high-latency underwater acoustic medium. Prior work has shown how to use counting in underwater MACs, and how to optimize contention windows in radio MACs. In this paper, we quantify bounds to convergence time for MAC protocols employing exact contender counting. We show that perfect countingallows contention to converge quickly, independent of network density, with an asymptotic limit of 3.6 contention rounds on average. We confirm this analysis with simulation of a specific underwater MAC protocol, and suggest the opportunity for the results to generalize for any radio-based MACs that estimate contenders.

Bibtex Citation

@inproceedings{Syed10a,
  author = {Syed, Affan A. and Heidemann, John},
  title = {Contention Analysis of MAC Protocols that Count},
  booktitle = {Proceedings of the Fifth ACM International Workshop on UnderWater Networks ({WUWNet}) },
  year = {2010},
  sortdate = {2010-09-01},
  project = {ilense, snuse, ortun, cisoft},
  jsubject = {sensornet_high_latency},
  publisher = {ACM},
  address = {Woods Hole, Massachusetts, USA},
  month = sep,
  pages = {2:1--2:8},
  jlocation = {johnh: pafile},
  keywords = {t-lohi, analysis, queueing theory, limit},
  doi = {10.1145/1868812.1868814},
  myorganization = {USC/Information Sciences Institute},
  copyrightholder = {ACM},
  copyrightterms = {
  	Permission to make digital or hard
   	copies of portions of this work for personal or
   	classroom use is granted without fee provided that
   	the copies are not made or distributed for profit or
   	commercial advantage and that copies bear this
   	notice and the full citation on the first page in
   	print or the first screen in digital
   	media. Copyrights for components of this work owned
   	by others than ACM must be honored. Abstracting with
   	credit is permitted. 
   	otherwise, to republish, to post on servers, or to
   	redistribute to lists, requires prior specific
   	permission and/or a fee. Send written requests for
   	republication to ACM Publications, Copyright &
   	Permissions at the address above or fax +1 (212)
   	869-0481 or email permissions@acm.org.},
  url = {https://ant.isi.edu/%7ejohnh/PAPERS/Syed10a.html},
  pdfurl = {https://ant.isi.edu/%7ejohnh/PAPERS/Syed10a.pdf},
  slidesurl = {https://ant.isi.edu/%7ejohnh/PAPERS/Syed10a_talk.pdf}
}

Copyright

Permission to make digital or hard copies of portions of this work for personal or classroom use is granted without fee provided that the copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page in print or the first screen in digital media. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Send written requests for republication to ACM Publications, Copyright & Permissions at the address above or fax +1 (212) 869-0481 or email permissions@acm.org.
Copyright © by John Heidemann