More Web Proxy on the site http://driver.im/

research-article

Self-synchronizing properties of CSMA wireless multi-hop networks

Authors:

Olivier Dousse,

Patrick ThiranAuthors Info & Claims

SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems

Pages 71 - 82

https://doi.org/10.1145/1811039.1811048

Published: 14 June 2010 Publication History

Abstract

We show that CSMA is able to spontaneously synchronize transmissions in a wireless network with constant-size packets, and that this property can be used to devise efficient synchronized CSMA scheduling mechanisms without message passing. Using tools from queuing theory, we prove that for any connected wireless networks with arbitrary interference constraints, it is possible to implement self-synchronizing TDMA schedules without any explicit message passing or clock synchronization besides transmitting the original data packets, and the interaction can be fully local in that each node decides when to transmit next only by overhearing its neighbors' transmissions. We also provide a necessary and sufficient condition on the emergence of self-synchronization for a given TDMA schedule, and prove that such conditions for self-synchronization can be checked in a finite number of steps for a finite network topology.

References

[1]

M. Alicherry, R. Bhatia, and L. Li. Joint channel assignment and routing for throughput optimization in multi-radio wireless mesh networks. In Proc. ACM MobiCom, page 72. ACM, 2005.

Digital Library

[2]

F. Baccelli and Z. Liu. On a class of stochastic recursive sequences arising in queueing theory. The Annals of Probability, pages 350--374, 1992.

[3]

P. Bjorklund and P. Di Yuan. Resource optimization of spatial TDMA in ad hoc radio networks: A column generation approach. In Proc. IEEE INFOCOM, 2003.

[4]

G. Brar, D. Blough, and P. Santi. Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In Proc. ACM MobiCom, page 13. ACM, 2006.

Digital Library

[5]

E. Callaway, P. Gorday, L. Hester, J. Gutierrez, M. Naeve, B. Heile, and V. Bahl. Home networking with IEEE 802.15.4: a developing standard for low-rate wireless personal area networks. IEEE Communications Magazine, 40(8):70--77, 2002.

Digital Library

[6]

O. Dousse. Revising buffering in multi-hop CSMA/CA wireless networks. In Proc. Secon, pages 580--589, San Diego CA, June 2007.

[7]

M. Durvy and P. Thiran. A packing approach to compare slotted and non-slotted medium access control. In Proc. IEEE INFOCOM, 2006.

[8]

S. Ganeriwal, R. Kumar, and M. Srivastava. Timing-sync protocol for sensor networks. In Proc. ACM Sensys, pages 138--149. ACM, 2003.

Digital Library

[9]

D. Lucarelli and I. Wang. Decentralized synchronization protocols with nearest neighbor communication. In Proc. ACM Sensys, pages 62--68. ACM, 2004.

Digital Library

[10]

P. Marbach, A. Eryilmaz, and A. Ozdaglar. Achievable rate region of csma schedulers in wireless networks with primary interference constraints. In Proc. IEEE CDC, 2007.

[11]

R. Mirollo and S. Strogatz. Synchronization of pulse-coupled biological oscillators. SIAM Journal on Applied Mathematics, 50(6):1645--1662, 1990.

Digital Library

[12]

A. Mutazono, M. Sugano, and M. Murata. Evaluation of robustness in time synchronization for sensor networks. In Proc. Bionetics'07, pages 89--92, 2007.

[13]

R. Nelson and L. Kleinrock. Spatial TDMA -- a collision-free multihop channel access protocol. IEEE Trans. Comm., 33(9):934--944, 1985.

[14]

T. Park, T. Kim, J. Choi, S. Choi, and W. Kwon. Throughout and energy consumption analysis of IEEE 802.15.4 slotted CSMA/CA. IEEE Electronics Letters, 41(18):1017, 2005.

[15]

B. Raman and K. Chebrolu. Revisiting MAC design for an 802.11-based mesh network. In Proc. 3rd Workshop on Hot Topics in Networks (HotNets-III), 2004.

[16]

I. Rhee, A. Warrier, M. Aia, J. Min, and M. Sichitiu. Z-MAC: a hybrid mac for wireless sensor networks. IEEE/ACM Trans. Networking, 16(3):511--524, 2008.

Digital Library

[17]

I. Rhee, A. Warrier, J. Min, and L. Xu. DRAND: distributed randomized TDMA scheduling for wireless ad--hoc networks. In Proc. ACM MobiHoc, page 201. ACM, 2006.

Digital Library

[18]

L. Roberts. ALOHA packet system with and without slots and capture. ACM SIGCOMM Computer Communication Review, 5(2):28--42, 1975.

Digital Library

[19]

N. Salem and J. Hubaux. A fair scheduling for wireless mesh networks. In Proc. WiMesh, 2005.

[20]

S. Singh, P. Acharya, U. Madhow, and E. Belding-Royer. Sticky CSMA/CA: Implicit synchronization and real-time QoS in mesh networks. Ad Hoc Networks, 5 (6):744--768, 2007.

Digital Library

[21]

L. Tassiulas and S. Sarkar. Maxmin fair scheduling in wireless networks. In Proc. IEEE INFOCOM, volume 2, pages 763--772, 2002.

[22]

K. Xu, O. Dousse, and P. Thiran. Self-synchronizing Properties of CSMA Wireless Multi-hop Networks (Technical Report).http://infoscience.epfl.ch/record/147917/files/XuDT10.pdf.

Cited By

Chen TGhaderi JRubenstein DZussman GRubenstein DChen TGhaderi JZussman G(2018)Maximizing Broadcast Throughput Under Ultra-Low-Power ConstraintsIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2018.280518526:2(779-792)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2805185
Chen TGhaderi JRubenstein DZussman GMarkopoulou AFaloutsos MSekar VKostic D(2016)Maximizing Broadcast Throughput Under Ultra-Low-Power ConstraintsProceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies10.1145/2999572.2999608(457-471)Online publication date: 6-Dec-2016
https://dl.acm.org/doi/10.1145/2999572.2999608
Charpentier MBartos RLi Y(2010)Interaction patterns for resilient intermittently-connected static sensor networks2010 - MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE10.1109/MILCOM.2010.5680441(581-586)Online publication date: Oct-2010
https://doi.org/10.1109/MILCOM.2010.5680441

Index Terms

Self-synchronizing properties of CSMA wireless multi-hop networks
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Networks

Recommendations

Self-synchronizing properties of CSMA wireless multi-hop networks
Performance evaluation review

We show that CSMA is able to spontaneously synchronize transmissions in a wireless network with constant-size packets, and that this property can be used to devise efficient synchronized CSMA scheduling mechanisms without message passing. Using tools ...
Starvation mitigation through multi-channel coordination in CSMA multi-hop wireless networks
MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing

Existing multi-channel protocols have been demonstrated to significantly increase aggregate throughput compared to single-channel protocols. However, we show that despite such improvements in aggregate throughput, existing protocols can lead to flow ...
Fairness in multi-hop wireless backhaul networks: a dynamic estimation approach
QShine '08: Proceedings of the 5th International ICST Conference on Heterogeneous Networking for Quality, Reliability, Security and Robustness

In this work, we consider the problem of fairness for Transit Access Points (TAP) in multi-hop wireless backhaul networks. Existing approaches are not practical due to the requirement for modifications to the MAC layer or queueing operations of TAPs, or ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systems

June 2010

398 pages

ISBN:9781450300384

DOI:10.1145/1811039

General Chair:
Vishal Misra
Columbia University, USA
,
Program Chairs:
Paul Barford
University of Wisconsin-Madison, USA
,
Mark Squillante
IBM T.J. Watson Research Center, USA

ACM SIGMETRICS Performance Evaluation Review Volume 38, Issue 1
Performance evaluation review
June 2010
382 pages
ISSN:0163-5999
DOI:10.1145/1811099
Issue’s Table of Contents

Copyright © 2010 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that 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. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMETRICS '10

Sponsor:

SIGMETRICS

SIGMETRICS '10: ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems

June 14 - 18, 2010

New York, New York, USA

Acceptance Rates

Overall Acceptance Rate 459 of 2,691 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
307
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen TGhaderi JRubenstein DZussman GRubenstein DChen TGhaderi JZussman G(2018)Maximizing Broadcast Throughput Under Ultra-Low-Power ConstraintsIEEE/ACM Transactions on Networking (TON)10.1109/TNET.2018.280518526:2(779-792)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1109/TNET.2018.2805185
Chen TGhaderi JRubenstein DZussman GMarkopoulou AFaloutsos MSekar VKostic D(2016)Maximizing Broadcast Throughput Under Ultra-Low-Power ConstraintsProceedings of the 12th International on Conference on emerging Networking EXperiments and Technologies10.1145/2999572.2999608(457-471)Online publication date: 6-Dec-2016
https://dl.acm.org/doi/10.1145/2999572.2999608
Charpentier MBartos RLi Y(2010)Interaction patterns for resilient intermittently-connected static sensor networks2010 - MILCOM 2010 MILITARY COMMUNICATIONS CONFERENCE10.1109/MILCOM.2010.5680441(581-586)Online publication date: Oct-2010
https://doi.org/10.1109/MILCOM.2010.5680441

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents