skip to main content
10.1145/1132905.1132927acmconferencesArticle/Chapter ViewAbstractPublication PagesmobihocConference Proceedingsconference-collections
Article

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

Published: 22 May 2006 Publication History

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]
L. Bao and J. J. Garcia-Luna-Aceves. A new approach to channel access scheduling for ad hoc networks. In ACM MobiCom '01: Proceedings of the 7th annual international conference on Mobile computing and networking pages 210--221, New York, NY, USA, 2001. ACM Press.
[5]
L. Breslau, D. Estrin, K. Fall, S. Floyd, J. Heidemann, A. Helmy,P. Huang, S. McCanne,K. Varadhan, Y. Xu, and H. Yu. Advances in network simulation. IEEE Computer 33(5):59--67, May 2000.
[6]
I. Chlamtac and A. Farag. Making transmission schedules immune to topology changes in multi-hop packet radio networks.IEEE/ACM Transactions on Networking 2(1):23--29,1994.
[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]
J. Grnkvist. Assignment methods for spatial reuse TDMA. In ACM MobiHoc '00: Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing pages 119--124, Piscataway, NJ, USA, 2000. IEEE Press.
[10]
M. Gruteser and D. Grunwald. Enhancing location privacy in wireless lan through disposable interface identifiers: a quantitative analysis.In WMASH '03: Proceedings of the 1st ACM international workshop on Wireless mobile applications and services on WLAN hotspots pages 46--55, New York, NY, USA, 2003. ACM Press.
[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]
J. Hill, R. Szewczyk, A. Woo, S. Hollar, D. Culler, and K. Pister. System architecture directions for network sensors. In Proc. Int. Conf. Architectural Support for Programming Languages and Operating Systems (ASPLOS)Cambridge,MA,November 2000.
[13]
B. Hull, K. Jamieson, and H. Balakrishnan. Mitigating congestion in wireless sensor networks. In SenSys '04: Proceedings of the 2nd international conference on Embedded networked sensor systems pages 134--147, New York,NY,USA,2004.ACM Press.
[14]
S. S. Kulkarni and M. U. Arumugam. TDMA service for sensor networks.In ICDCSW '04: Proceedings of the 24th International Conference on Distributed Computing Systems Workshops - W7: EC (ICDCSW'04)pages 604--609,Washington,DC,USA, 2004.IEEE Computer Society.
[15]
M.Luby.Removing randomness in parallel computation without processor penality. Journal of Computer and System Sciences 47(2):250--286,Oct. 1993.
[16]
T.Moscibroda and R.Wattenhofer. Coloring Unstructured Radio Networks.In 17th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Las Vegas, Nevada, USA July 2005.
[17]
S. Parthasarathy and R. Gandhi. Distributed algorithms for coloring and domination in wireless ad hoc networks. In FSTTCS pages 447--459, 2004.
[18]
R. K. Patro and B. Mohan. Mobile agent based TDMA slot assignment algorithm for wireless sensor networks. In International Conference on Information Technology: Coding and Computing (ITCC'05) -Volume II pages pp.663--667,2005.
[19]
J. Polastre, J. Hill, and D. Culler. Versatile low power media access for wireless sensor networks. In ACM SenSys '04: Proceedings of the 2nd international conference on Embedded networked sensor systems pages 95--107, New York, NY, USA, 2004. ACM Press.
[20]
S. Ramanathan. A unified framework and algorithms for (T/F/C)DMA channel assignment in wireless networks. In IEEE INFOCOM pages 900--907, 1997.
[21]
I. Rhee, A. Warrier, M. Aia, and J. Min. Z-MAC: a hybrid MAC for wireless sensor networks. In SenSys'05: Proceedings of the 3rd international conference on Embedded networked sensor systems pages 90--101, New York, NY, USA, 2005. ACM Press.
[22]
R. Rozovsky and P. R. Kumar. SEEDEX: a MAC protocol for ad hoc networks.In ACM MobiHoc '01: Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing pages 67--75, New York, NY, USA, 2001. ACM Press.
[23]
T. Salonidis and L. Tassiulas. Distributed dynamic scheduling for end-to-end rate guarantees in wireless ad hoc networks. In ACM MobiHoc '05: Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing pages 145--156, New York, NY, USA, 2005. ACM Press.
[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]
G. Zhou, T. He, S. Krishnamurthy, and J. A. Stankovic. Impact of radio irregularity on wireless sensor networks.In MobiSys '04: Proceedings of the 2nd international conference on Mobile systems, applications, and services pages 125--138, New York, NY, USA, 2004. ACM Press.
[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]
C.Zhu and M. S. Corson. A five-phase reservation protocol (fprp)for mobile ad hoc networks. Wireless Networks 7(4):371--384, 2001.

Cited By

View all
  • (2023)A Comparative Review on Channel Allocation and Data Aggregation Techniques for Convergecast in Multichannel Wireless Sensor NetworksDecision Intelligence Solutions10.1007/978-981-99-5994-5_29(321-331)Online publication date: 15-Dec-2023
  • (2022)Survey on MAC Protocol of Mobile Ad hoc Network for Tactical Data Link System2022 International Conference on Information Technology Systems and Innovation (ICITSI)10.1109/ICITSI56531.2022.9971025(134-137)Online publication date: 8-Nov-2022
  • (2021)Mobile Cloud Computing and Wireless Sensor Networks: A review, integration architecture, and future directionsIET Networks10.1049/ntw2.1201310:4(141-161)Online publication date: 10-Mar-2021
  • Show More Cited By

Index Terms

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

      Recommendations

      Comments

      Information & Contributors

      Information

      Published In

      cover image ACM Conferences
      MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing
      May 2006
      378 pages
      ISBN:1595933689
      DOI:10.1145/1132905
      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]

      Sponsors

      Publisher

      Association for Computing Machinery

      New York, NY, United States

      Publication History

      Published: 22 May 2006

      Permissions

      Request permissions for this article.

      Check for updates

      Author Tags

      1. medium access control
      2. network performance
      3. wireless sensor networks

      Qualifiers

      • Article

      Conference

      MobiHoc06
      Sponsor:

      Contributors

      Other Metrics

      Bibliometrics & Citations

      Bibliometrics

      Article Metrics

      • Downloads (Last 12 months)36
      • Downloads (Last 6 weeks)6
      Reflects downloads up to 20 Feb 2025

      Other Metrics

      Citations

      Cited By

      View all
      • (2023)A Comparative Review on Channel Allocation and Data Aggregation Techniques for Convergecast in Multichannel Wireless Sensor NetworksDecision Intelligence Solutions10.1007/978-981-99-5994-5_29(321-331)Online publication date: 15-Dec-2023
      • (2022)Survey on MAC Protocol of Mobile Ad hoc Network for Tactical Data Link System2022 International Conference on Information Technology Systems and Innovation (ICITSI)10.1109/ICITSI56531.2022.9971025(134-137)Online publication date: 8-Nov-2022
      • (2021)Mobile Cloud Computing and Wireless Sensor Networks: A review, integration architecture, and future directionsIET Networks10.1049/ntw2.1201310:4(141-161)Online publication date: 10-Mar-2021
      • (2020)Median Access Control Protocols for Sensor Data Collection: A ReviewIEEE Access10.1109/ACCESS.2020.30193928(160078-160098)Online publication date: 2020
      • (2020)Energy Management Techniques for WSNs (1): Duty-Cycling ApproachWireless Sensor Networks10.1007/978-3-030-29700-8_4(109-258)Online publication date: 26-Jan-2020
      • (2019)A Scheduling for Slotted-CSMA-based Wireless Mesh Networks to Reduce Delivery DelayJournal of Information Processing10.2197/ipsjjip.27.11727(117-124)Online publication date: 2019
      • (2019)Exploiting Concurrency for Opportunistic Forwarding in Duty-Cycled IoT NetworksACM Transactions on Sensor Networks10.1145/332249615:3(1-33)Online publication date: 30-May-2019
      • (2019)Network Management of Multicluster RT-WiFi NetworksACM Transactions on Sensor Networks10.1145/328345115:1(1-26)Online publication date: 10-Feb-2019
      • (2019)IPBMWireless Networks10.1007/s11276-019-01992-x25:5(2769-2787)Online publication date: 1-Jul-2019
      • (2018)Medium access control in wireless sensor networksInternational Journal of Information and Communication Technology10.5555/3201939.320194112:3-4(246-270)Online publication date: 1-Jan-2018
      • Show More Cited By

      View Options

      Login options

      View options

      PDF

      View or Download as a PDF file.

      PDF

      eReader

      View online with eReader.

      eReader

      Figures

      Tables

      Media

      Share

      Share

      Share this Publication link

      Share on social media