Self-synchronizing properties of CSMA wireless multi-hop networks
Pages 71 - 82
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.
[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.
[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.
[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.
[9]
D. Lucarelli and I. Wang. Decentralized synchronization protocols with nearest neighbor communication. In Proc. ACM Sensys, pages 62--68. ACM, 2004.
[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.
[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.
[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.
[18]
L. Roberts. ALOHA packet system with and without slots and capture. ACM SIGCOMM Computer Communication Review, 5(2):28--42, 1975.
[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.
[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.
Index Terms
- Self-synchronizing properties of CSMA wireless multi-hop networks
Recommendations
Self-synchronizing properties of CSMA wireless multi-hop networks
SIGMETRICS '10: Proceedings of the ACM SIGMETRICS international conference on Measurement and modeling of computer systemsWe 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 computingExisting 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 ...
Contention in multi-hop wireless networks: model and fairness analysis
MSWiM '09: Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systemsIn multi-hop wireless networks with Carrier Sense Multiple Access (CSMA), unfairness may arise due to a number of reasons. A majority of the existing work focuses on fairness issues due to hidden terminals and the impact on backoff mechanisms. This ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2010398 pagesISBN:9781450300384DOI:10.1145/1811039- General Chair:
- Vishal Misra,
- Program Chairs:
- Paul Barford,
- Mark Squillante
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]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 14 June 2010
Published in SIGMETRICS Volume 38, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations3Total Citations
- 307Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in