TDM MAC protocol design and implementation for wireless mesh networks

ABSTRACT

We present the design, implementation, and evaluation of a Time Division Multiplex (TDM) MAC protocol for multi-hop wireless mesh networks using a programmable wireless platform. Extensive research has been devoted to optimal scheduling algorithms for multi-hop wireless networks assuming a perfect TDM MAC protocol. However, the problem of designing and implementing such a protocol has not received due attention. We introduce a design framework that addresses the three main challenges that comprise this problem: (i) How to calibrate and optimize the TDM MAC protocol parameters given a wireless platform, (ii) how to achieve network-wide synchronization with high accuracy, minimal overhead, and most importantly, bounded delay, and (iii) how to integrate the synchronization algorithm with the TDM MAC protocol state machine using minimal hardware resources. We apply our design framework to our platform and evaluate the resulting TDM MAC protocol through controlled experiments in a wireless mesh testbed. The results demonstrate the protocol's ability to provide fairness and graceful performance degradation under packet losses and multi-hop traffic patterns that arise in mesh network deployments.

REFERENCES

• 1: ECMA 368, High Rate Ultra Wideband PHY and MAC standard, 2007.
• 2: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 3: Kameswari Chebrolu , Bhaskaran Raman , Nilesh Mishra , Phani Kumar Valiveti , Raj Kumar, Brimon: a sensor network system for railway bridge monitoring, Proceeding of the 6th international conference on Mobile systems, applications, and services, June 17-20, 2008, Breckenridge, CO, USA [doi>10.1145/1378600.1378603]
• 4: Jeremy Eric Elson , Deborah L. Estrin, Time synchronization in wireless sensor networks, University of California, Los Angeles, 2003
• 5: 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]
• 6: Anand Kashyap , Samrat Ganguly , Samir R. Das, A measurement-based approach to modeling link capacity in 802.11-based wireless networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287883]
• 7: Miklós Maróti , Branislav Kusy , Gyula Simon , Ákos Lédeczi, The flooding time synchronization protocol, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031501]
• 8: D. Mills. Internet time synchronization: The network time protocol. IEEE Transactions on Communications, 39: 1482--1493, 1991.
• 9: M. Neufeld, J. Fifield, C. Doerr, A. Sheth, and D. Grunwald. SoftMAC: - Flexible Wireless Research Platform. In HotNets, College Park, MD, USA, Nov. 2005.
• 10: R. Patra, S. Nedevschi, S. Surana, A. Sheth, L. Subramanian, and E. Brewer. WiLDNet: Design and Implementation of High Performance WiFi Based Long Distance Networks. In Proc. NSDI, Cambridge, MA, USA, Apr. 2007.
• 11: Lili Qiu , Yin Zhang , Feng Wang , Mi Kyung Han , Ratul Mahajan, A general model of wireless interference, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287874]
• 12: Bhaskaran Raman , Kameswari Chebrolu, Design and evaluation of a new MAC protocol for long-distance 802.11 mesh networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080847]
• 13: Ananth Rao , Ion Stoica, An overlay MAC layer for 802.11 networks, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067185]
• 14: K. Romer, P. Blum, and L. Meier. Time Synchronization and Calibration in Wireless Sensor Networks. Book chp., Handbook of Wireless Sensor Networks, Wiley Series on Parallel and Distributed Computing, 2005.
• 15: A. Rowe, R. Mangharan, and R. Rajkumar. Rt-link: A Time-Synchronized Link Protocol for Energy-Constrained Multi-hop Wireless Networks. In Proc. IEEE SECON, San Diego, CA, USA, Jun. 2006.
• 16: A. Sharma, M. Tiwari, and H. Zheng. MadMac: Building a Reconfigurable Radio Testbed Using Commodity 802.11 Hardware. In IEEE Workshop on Networking Technologies for Software Defined Radio (SDR) Networks, Portland, OR, USA, Nov. 2006.
• 17: USCG Navigation Counter GPS page. http://www.navcen.uscg.nil/gps/default.html.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Data communications
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Design, Experimentation, Measurement, Performance