Self-synchronizing properties of CSMA wireless multi-hop networks

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

• Computer systems organization

  • Architectures

    • Distributed architectures

• Networks

  • Network architectures

  • Network properties

    • Network structure

  • Network types

    • Mobile networks

    • Wireless access networks