DRAND: distributed randomized TDMA scheduling for wireless ad-hoc networks

ABSTRACT

This paper presents a distributed implementation of RAND, a randomized time slot scheduling algorithm, called DRAND. DRAND runs in O(δ) time and message complexity where δ is the maximum size of a two-hop neighborhood in a wire-less network while message complexity remains O(δ), assuming that message delays can be bounded by an unknown constant.DRAND is the first fully distributed version of RAND. The algorithm is suitable for a wireless network where most nodes do not move,such as wireless mesh networks and wireless sensor networks.We implement the algorithm in TinyOS and demonstrate its performance in a real testbed of Mica2 nodes. The algorithm does not require any time synchronization and is shown to be effective in adapting to local topology changes without incurring global overhead in the scheduling.Because of these features, it can also be used even for other scheduling problems such as frequency or code scheduling (for FDMA or CDMA) or local identifier assignment for wireless networks where time synchronization is not enforced.

REFERENCES

• 1: CC1000 Low Power FSK transceiver, Chipcon Corporation.
• 2: WiMedia Alliance,MBOA Wireless MAC Specification for High Rate Wireless Personal Area Networks (WPANs),Specification Draft.
• 3: ZigBee Alliance, IEEE 802.15.4, ZigBee standard.
• 4: Lichun Bao , J. J. Garcia-Luna-Aceves, A new approach to channel access scheduling for Ad Hoc networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.210-221, July 2001, Rome, Italy [doi>10.1145/381677.381698]
• 5: Lee Breslau , Deborah Estrin , Kevin Fall , Sally Floyd , John Heidemann , Ahmed Helmy , Polly Huang , Steven McCanne , Kannan Varadhan , Ya Xu , Haobo Yu, Advances in Network Simulation, Computer, v.33 n.5, p.59-67, May 2000 [doi>10.1109/2.841785]
• 6: Imrich Chlamtac , András Faragó, Making transmission schedules immune to topology changes in multi-hop packet radio networks, IEEE/ACM Transactions on Networking (TON), v.2 n.1, p.23-29, Feb. 1994 [doi>10.1109/90.282605]
• 7: B.Crow,I.Widjaja,J.G.Kim,and P.Sakai.IEEE 802.11 wireless local area networks.IEEE Communications Magazine 35(9):116--126, 1997.
• 8: S. Gandham, M. Dawande, and R. Prakash. Link scheduling in sensor networks:Distributed edge coloring revisited. In IEEE INFOCOM 2005.
• 9: Jimmi Grönkvist, Assignment methods for spatial reuse TDMA, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 10: Marco Gruteser , Dirk Grunwald, Enhancing location privacy in wireless LAN through disposable interface identifiers: a quantitative analysis, Proceedings of the 1st ACM international workshop on Wireless mobile applications and services on WLAN hotspots, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941326.941334]
• 11: T. Herman and S. Tixeuil. A distributed TDMA slot assignment algorithm for wireless sensor networks. In Proceedings of the First Workshop on Algorithmic Aspects of Wireless Sensor Networks (AlgoSensors'2004)number 3121 in Lecture Notes in Computer Science, pages 45--58, Turku, Finland, July 2004. Springer-Verlag.
• 12: Jason Hill , Robert Szewczyk , Alec Woo , Seth Hollar , David Culler , Kristofer Pister, System architecture directions for networked sensors, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.93-104, November 2000, Cambridge, Massachusetts, United States
• 13: Bret Hull , Kyle Jamieson , Hari Balakrishnan, Mitigating congestion in wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031512]
• 14: Sandeep S. Kulkarni , Mahesh (Umamaheswaran) Arumugam, TDMA Service for Sensor Networks, Proceedings of the 24th International Conference on Distributed Computing Systems Workshops - W7: EC (ICDCSW'04), p.604-609, March 23-24, 2004
• 15: Michael Luby, Removing randomness in parallel computation without a processor penalty, Journal of Computer and System Sciences, v.47 n.2, p.250-286, Oct. 1993 [doi>10.1016/0022-0000(93)90033-S]
• 16: Thomas Moscibroda , Roger Wattenhofer, Coloring unstructured radio networks, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1073977]
• 17: S. Parthasarathy and R. Gandhi. Distributed algorithms for coloring and domination in wireless ad hoc networks. In FSTTCS pages 447--459, 2004.
• 18: Ranjeet Kumar Patro , Balamurugan Mohan, Mobile Agent Based TDMA Slot Assignment Algorithm for Wireless Sensor Networks, Proceedings of the International Conference on Information Technology: Coding and Computing (ITCC'05) - Volume II, p.663-667, April 04-06, 2005 [doi>10.1109/ITCC.2005.201]
• 19: Joseph Polastre , Jason Hill , David Culler, Versatile low power media access for wireless sensor networks, Proceedings of the 2nd international conference on Embedded networked sensor systems, November 03-05, 2004, Baltimore, MD, USA [doi>10.1145/1031495.1031508]
• 20: S. Ramanathan, A Unified Framework and Algorithm for (T/F/C)DMA Channel Assignment in Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.900, April 09-11, 1997
• 21: Injong Rhee , Ajit Warrier , Mahesh Aia , Jeongki Min, Z-MAC: a hybrid MAC for wireless sensor networks, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098929]
• 22: R. Rozovsky , P. R. Kumar, SEEDEX: a MAC protocol for ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501426.501427]
• 23: Theodoros Salonidis , Leandros Tassiulas, Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062709]
• 24: W. Ye, J. Heidemann, and D. Estrin. An energy-efficient mac protocol for wireless sensor networks. In Proceedings of the IEEE Infocom pages 1567--1576, New York, NY, USA,June 2002. USC/Information Sciences Institute, IEEE.
• 25: Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990081]
• 26: C. Zhu and M. Corson. An evolutionary-TDMA scheduling protocol (E-TDMA) for mobile ad hoc networks. In Proc. of Advanced Tel ecommunications and Information Distribution Research Program (ATIRP)March, 2000.
• 27: Chenxi Zhu , M. S. Corson, A Five-Phase Reservation Protocol (FPRP) for Mobile Ad Hoc Networks, Wireless Networks, v.7 n.4, p.371-384, 08/01/2001 [doi>10.1023/A:1016683928786]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
medium access control, network performance, wireless sensor networks