Practical synchronization techniques for multi-channel MAC

ABSTRACT

Researchers have proposed many wireless MAC protocols such as [20], [8], [25], [24], [6], and [17] which exploit frequency-agile radios and multiple available channels to increase network through-put. These protocols usually only require each node to have one radio. By carefully coordinating the frequency hopping of different nodes, different node pairs can use multiple channels simultaneously. In [17], Mo et al classified these protocols into four generalized categories and compared their performances through both analysis and simulation. They found that the Parallel Rendezvous family of protocols has the best overall performance by removing the bottleneck of a single control channel. These protocols show good promise for use with multi-hop networks because these networks suffer from self-interference and traditional MAC protocols using only one channel often fail to provide satisfactory throughput. However, we are not aware of any implemented Parallel Rendezvous multi-channel MAC protocols. We argue one major reason is that existing proposals such as McMAC[17] and SSCH[6] have not thoroughly considered a practical aspect of the design essential for a working implementation, namely: synchronization. Through an exploration including an implementation exercise on hardware, we show that synchronization for multi-channel MAC protocols is a non-trivial problem. We designed and implemented a synchronization mechanism specifically for this purpose and show that it has tackled the problem of synchronizing one-hop neighbor pairs effectively, thereby paving the way for efficient multi-channel MAC protocols.

REFERENCES

• 1: Polarizone Technologies Sdn. Bhd. (600204-U). SDR Design Bench http://www.polarizone.com/.
• 2: Emmanuelle Anceaume and Isabelle Puaut. Performance evaluation of clock synchronization algorithms. Technical Report RR-3526, INRIA, 1998.
• 3: Chipcon AS. CC2420 2.4 GHz IEEE 802.15.4/ZigBee-ready RF Transceiver Data Sheet (rev. 1.3) http://www.chipcon.com/files/ CC2420 Data Sheet 1 3.pdf.
• 4: Chipcon AS. CC2500 Single Chip Low Cost Low Power RF Transceiver http://www.chipcon.com/files/CC2500 data sheet 1 1.pdf.
• 5: Chipcon AS. http://http://www.chipcon.com/.
• 6: Paramvir Bahl , Ranveer Chandra , John Dunagan, SSCH: slotted seeded channel hopping for capacity improvement in IEEE 802.11 ad-hoc wireless networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023742]
• 7: Jean-Marc Berthaud, Time synchronization over networks using convex closures, IEEE/ACM Transactions on Networking (TON), v.8 n.2, p.265-277, April 2000 [doi>10.1109/90.842147]
• 8: J. Chen, S. Sheu, and C. Yang. A new multichannel access protocol for ieee 802.11 ad hoc wireless lans. In PIMRC, volume 3, pages 2291--2296, 2003.
• 9: UC Berkeley EECS 150 Components and Design Techniques for Digital Systems. Data sheets for calinx /calinx2 http://www-inst.eecs.berkeley.edu/.cs150/sp06/Documents.php, 2006.
• 10: Jeremy Elson , Lewis Girod , Deborah Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060304]
• 11: Saurabh Ganeriwal , Ram Kumar , Mani B. Srivastava, Timing-sync protocol for sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958508]
• 12: Simon Haykin, Adaptive filter theory (3rd ed.), Prentice-Hall, Inc., Upper Saddle River, NJ, 1996
• 13: Wing-Chung Hung, K.L. Eddie Law, and A. Leon-Garcia. A Dynamic Multi-Channel MAC for Ad-Hoc LAN. In Proc. 21st Biennial Symposium on Communications, pages 31--35, Kingston, Canada, June 2002.
• 14: Atheros Communications Inc. Atheros AR5002G 802.11b/gWLAN solution http://www.atheros.com/.
• 15: Miklos Maroti, Branislav Kusy, Gyula Simon, and Akos Ledeczi. The Flooding Time Synchronization Protocol. Technical Report TR No.: ISIS-04-501, Institute for Software Integrated Systems, Vanderbilt University, 2004.
• 16: David L. Mills. Internet time synchronization: The network time protocol. In Zhonghua Yang and T. Anthony Marsland (Eds.), Global States and Time in Distributed Systems, IEEE Computer Society Press. 1994.
• 17: Jeonghoon Mo , Hoi-Sheung Wilson So , Jean Walrand, Comparison of multi-channel MAC protocols, Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 10-13, 2005, Montréal, Quebec, Canada [doi>10.1145/1089444.1089480]
• 18: Joseph Polastre , Robert Szewczyk , David Culler, Telos: enabling ultra-low power wireless research, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 19: Kay Romer, Philipp Blum, and Lennart Meier. Time synchronization and calibration in wireless sensor networks, October, 2005.
• 20: Jungmin So and Nitin H. Vaidya. A multi-channel mac protocol for ad hoc wireless networks. Technical report, UIUC, 2003.
• 21: IEEE Computer Society. ANSI/IEEE Std 802.11 1999 Edition (R2003) Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications.
• 22: IEEE Computer Society. IEEE 802.15.4: Wireless Medium Access Control (MAC) and Physical Layer (PHY) Specifications for Low-Rate Wireless Personal Area Networks (LR-WPANs), 2003.
• 23: The TinyOS Project. http://webs.cs.berkeley.edu/tos/.
• 24: A. Tzamaloukas and J. Garcia-Luna-Aceves. Channel-hopping multiple access with packet trains for ad hoc networks. In In Proc. IEEE Mobile Multimedia Communications (MoMuC '00), Tokyo, 2000.
• 25: Asimakis Tzamaloukas and J. J. Garcia-Luna-Aceves. Channel-hopping multiple access. In ICC (1), pages 415--419, 2000.
• 26: Maxim Integrated Products Inc. Sunnyvale California USA. Max2820, max2820a,max2821, max2821a 2.4ghz 802.11b zero-if transceivers data sheet rev. 04/2004, 2004.
• 27: S.-L. Wu , C.-Y Lin , Y.-C. Tseng , J.-P. Sheu, A New Multi-Channel MAC Protocol with On-Demand Channel Assignment for Multi-Hop Mobile Ad Hoc Networks, Proceedings of the 2000 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '00), p.232, December 07-07, 2000
• 28: Shih-Lin Wu, Yu-Chee Tseng, Chih-Yu Lin, and Jang-Ping Sheu. A Multi-channel MAC Protocol with Power Control for Multi-hop Mobile Ad Hoc Networks. The Computer Journal, 45:101--110, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
clock drift, medium access control, multi-channel MAC, protocol, recursive least squares (RLS), time synchronization, wireless