More Web Proxy on the site http://driver.im/

research-article

Distributed Reliable and Energy-Efficient Scheduling for LR-WPANs

Authors:

Tim Van Der Lee,

Georgios Exarchakos,

Sonia Heemstra De GrootAuthors Info & Claims

ACM Transactions on Sensor Networks (TOSN), Volume 16, Issue 4

Article No.: 32, Pages 1 - 20

https://doi.org/10.1145/3399805

Published: 25 August 2020 Publication History

Abstract

Pervasiveness of wireless networks drives the heterogeneity and density of devices in a vast diversity of environments. To achieve high reliability and low energy consumption while enabling pervasiveness is inherently a resource allocation problem. In low-rate wireless personal area networks, multi-frequency time-division multiple access methods are identified as compelling solutions to resource allocation via scheduling transmissions in time and frequency. This work presents the TREE (TRaffic-aware Energy Efficient) algorithm, an adaptive and distributed scheduling algorithm, designed to provide high reliability in terms of packet reception ratio while optimizing the energy consumption of each device. This algorithm schedules communications according to the packets in the queue and short-memory performance. Decisions are made locally, and low-interference scheduling emerges at the network level. TREE is an adaptive threshold-based model that allocates more network resources (e.g., timeslots) when the communication queue size crosses a threshold and frees resources if the resource was underutilized. Implemented over IEEE-802.15.4-TSCH and extensively tested in simulation and on real deployments up to 81 devices, the algorithm is compared to MSF, Alice, and Orchestra, the state of the art in time-slotted channel hopping scheduling. Results highlight a high reliability regarding packet reception ratio and a lower energy consumption compared to the state of the art.

References

[1]

Bluetooth. n.d. Traditional Profile Specifications. Retrieved June 5, 2020 from https://www.bluetooth.com/specifications/profiles-overview/.

[2]

IEEE. 2012. IEEE Standard for Local and Metropolitan Area Networks—Part 15.4: Low-Rate Wireless Personal Area Networks (LR-WPANs) Amendment 1: MAC Sublayer. IEEE Std 802.15.4e-2012 (Amendment to IEEE Std 802.15.4-2011). IEEE, Los Alamitos, CA.

[3]

2015. ZigBee Specification. Technical Specification 05-3474-21. Zigbee Alliance. https://zigbeealliance.org/wp-content/uploads/2019/12/docs-05-3474-21-0csg-zigbee-specification.pdf.

[4]

N. Accettura, E. Vogli, M. R. Palattella, L. A. Grieco, G. Boggia, and M. Dohler. 2015. Decentralized traffic aware scheduling in 6TiSCH networks: Design and experimental evaluation. IEEE Internet of Things Journal 2, 6 (Dec. 2015), 455--470.

[5]

Cedric Adjih, Emmanuel Baccelli, Eric Fleury, Gaetan Harter, Nathalie Mitton, Thomas Noel, Roger Pissard-Gibollet, et al. 2015. FIT IoT-LAB: A large scale open experimental IoT testbed. In Proceedings of the 2015 IEEE 2nd World Forum on Internet of Things (WF-IoT’15). IEEE, Los Alamitos, CA, 459--464.

Digital Library

[6]

Christian Blum and Xiaodong Li. 2008. Swarm intelligence in optimization. In Swarm Intelligence. Springer, 43--85.

[7]

Eric Bonabeau, Guy Theraulaz, and Jean-Louis Deneubourg. 1996. Quantitative study of the fixed threshold model for the regulation of division of labour in insect societies. Proceedings of the Royal Society of London, Series B: Biological Sciences 263, 1376 (1996), 1565--1569.

[8]

Tengfei Chang, Malisa Vucinic, Xavier Vilajosana, Simon Duquennoy, and Diego Dujovne. 2018. 6TiSCH Minimal Scheduling Function (MSF). Internet-Draft draft-ietf-6tisch-msf-01. IETF Secretariat. http://www.ietf.org/internet-drafts/draft-ietf-6tisch-msf-01.txt.

[9]

T. Chang, T. Watteyne, Q. Wang, and X. Vilajosana. 2016. LLSF: Low latency scheduling function for 6TiSCH networks. In Proceedings of the 2016 International Conference on Distributed Computing in Sensor Systems (DCOSS’16). 93--95.

[10]

P. Chaporkar and S. Sarkar. 2008. Stable scheduling policies for maximizing throughput in generalized constrained queueing systems. IEEE Transactions on Automatic Control 53, 8 (Sept. 2008), 1913--1931.

[11]

Glenn Daneels, Bart Spinnewyn, Steven Latré, and Jeroen Famaey. 2018. ReSF: Recurrent low-latency scheduling in IEEE 802.15.4e TSCH networks. Ad Hoc Networks 69, Supplement C (Feb. 2018), 100--114.

[12]

Marc Domingo-Prieto, Tengfei Chang, Xavier Vilajosana, and Thomas Watteyne. 2016. Distributed PID-based scheduling for 6TiSCH networks. IEEE Communications Letters 20, 5 (2016), 1006--1009.

[13]

M. Dorigo and T. Stutzle. 2004. Ant Colony Optimization. Bradford Company, Scituate, MA.

[14]

Marco Dorigo and Mauro Birattari. 2010. Ant Colony Optimization. Springer.

[15]

A. Dunkels, B. Gronvall, and T. Voigt. 2004. Contiki—A lightweight and flexible operating system for tiny networked sensors. In Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks. 455--462.

Digital Library

[16]

Simon Duquennoy, Beshr Al Nahas, Olaf Landsiedel, and Thomas Watteyne. 2015. Orchestra: Robust mesh networks through autonomously scheduled TSCH. In Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems (SenSys’15). ACM, New York, NY, 337--350.

Digital Library

[17]

Jeremy Elson, Lewis Girod, and Deborah Estrin. 2002. Fine-grained network time synchronization using reference broadcasts. ACM SIGOPS Operating Systems Review 36, SI (2002), 147--163.

[18]

Saurabh Ganeriwal, Ram Kumar, and Mani B. Srivastava. 2003. Timing-sync protocol for sensor networks. In Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. ACM, New York, NY, 138--149.

[19]

Rodrigo Garces and J. J. Garcia-Luna-Aceves. 2000. Collision avoidance and resolution multiple access for multichannel wireless networks. In Proceedings of the 19th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’00), Vol. 2. IEEE, Los Alamitos, CA, 595--602.

[20]

Simon Garnier, Jacques Gautrais, and Guy Theraulaz. 2007. The biological principles of swarm intelligence. Swarm Intelligence 1, 1 (2007), 3--31.

[21]

P. Giaccone, E. Leonardi, and D. Shah. 2007. Throughput region of finite-buffered networks. IEEE Transactions on Parallel and Distributed Systems 18, 2 (Feb. 2007), 251--263.

Digital Library

[22]

Y. Gu, W. Saad, M. Bennis, M. Debbah, and Z. Han. 2015. Matching theory for future wireless networks: Fundamentals and applications. IEEE Communications Magazine 53, 5 (May 2015), 52--59.

Digital Library

[23]

Walter J. Gutjahr and Marion S. Rauner. 2007. An ACO algorithm for a dynamic regional nurse-scheduling problem in Austria. Computers 8 Operations Research 34, 3 (2007), 642--666.

[24]

Magnús M. Halldórsson and Tigran Tonoyan. 2017. Universal framework for wireless scheduling problems. arxiv:1705.10104

[25]

I. Holyer. 1981. The NP-completeness of edge-coloring. SIAM Journal on Computing 10, 4 (Nov. 1981), 718--720.

[26]

Ren-Hung Hwang, Chih-Chiang Wang, and Wu-Bin Wang. 2017. A distributed scheduling algorithm for IEEE 802.15. 4e wireless sensor networks. Computer Standards 8 Interfaces 52 (2017), 63--70.

[27]

Seohyang Kim, Hyung-Sin Kim, and Chongkwon Kim. 2019. ALICE: Autonomous link-based cell scheduling for TSCH. In Proceedings of the 2019 18th ACM/IEEE International Conference on Information Processing in Sensor Networks (IPSN’19). IEEE, Los Alamitos, CA, 121--132.

Digital Library

[28]

P. R. Kumar and S. P. Meyn. 1995. Stability of queueing networks and scheduling policies. IEEE Transactions on Automatic Control 40, 2 (Feb. 1995), 251--260.

[29]

T. van der Lee, G. Exarchakos, and A. Liotta. 2017. Distributed TSCH scheduling: A comparative analysis. In Proceedings of the 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC’17). 3517--3522.

[30]

Tim van der Lee, Antonio Liotta, and Georgios Exarchakos. 2019. Interference graphs to monitor and control schedules in low-power WPAN. Future Generation Computer Systems 93 (April 2019), 111--120.

[31]

T. van der Lee, A. Liotta, and G. Exarchakos. 2018. Time-scheduled network evaluation based on interference. In Proceedings of the 2018 IEEE International Conference on Cloud Engineering (IC2E’18). 323--332.

[32]

Zne-Jung Lee, Shun-Feng Su, Chen-Chia Chuang, and Kuan-Hung Liu. 2008. Genetic algorithm with ant colony optimization (GA-ACO) for multiple sequence alignment. Applied Soft Computing 8, 1 (2008), 55--78.

Digital Library

[33]

Y. Li, X. Qi, M. Keally, Z. Ren, G. Zhou, D. Xiao, and S. Deng. 2013. Communication energy modeling and optimization through joint packet size analysis of BSN and WiFi networks. IEEE Transactions on Parallel and Distributed Systems 24, 9 (Sept. 2013), 1741--1751.

Digital Library

[34]

D. Liu, Y. Xu, L. Shen, and Y. Xu. 2016. Self-organising multiuser matching in cellular networks: A score-based mutually beneficial approach. IET Communications 10, 15 (2016), 1928--1937.

[35]

Chong Luo, Feng Wu, Jun Sun, and Chang Wen Chen. 2010. Efficient measurement generation and pervasive sparsity for compressive data gathering. IEEE Transactions on Wireless Communications 9, 12 (2010), 3728--3738.

Digital Library

[36]

M. Mavrovouniotis and S. Yang. 2014. Ant colony optimization with self-adaptive evaporation rate in dynamic environments. In Proceedings of the 2014 IEEE Symposium on Computational Intelligence in Dynamic and Uncertain Environments (CIDUE’14). 47--54.

[37]

Mohamed Mohamadi and Mustapha Reda Senouci. 2019. Scheduling algorithms for IEEE 802.15.4 TSCH networks: A survey. In Advances in Computing Systems and Applications, O. Demigha, B. Djamaa, and A, Amamra (Eds.). Springer International Publishing, Cham, Switzerland, 4--13.

[38]

Esteban Municio, Glenn Daneels, Mališa Vučinić, Steven Latré, Jeroen Famaey, Yasuyuki Tanaka, Keoma Brun, Kazushi Muraoka, Xavier Vilajosana, and Thomas Watteyne. 2018. Simulating 6TiSCH networks. Transactions on Emerging Telecommunications Technologies 30, 3 (2018), e3494.

Digital Library

[39]

Esteban Municio and Steven Latré. 2016. Decentralized broadcast-based scheduling for dense multi-hop TSCH networks. In Proceedings of the Workshop on Mobility in the Evolving Internet Architecture. ACM, New York, NY, 19--24.

Digital Library

[40]

K. Muraoka, T. Watteyne, N. Accettura, X. Vilajosana, and K. S. J. Pister. 2016. Simple distributed scheduling with collision detection in TSCH networks. IEEE Sensors Journal 16, 15 (Aug. 2016), 5848--5849.

[41]

Bilel Nefzi and Ye-Qiong Song. 2012. QoS for wireless sensor networks: Enabling service differentiation at the MAC sub-layer using CoSenS. Ad Hoc Networks 10, 4 (2012), 680--695.

Digital Library

[42]

M. R. Palattella, N. Accettura, M. Dohler, L. A. Grieco, and G. Boggia. 2012. Traffic aware scheduling algorithm for reliable low-power multi-hop IEEE 802.15.4e networks. In Proceedings of the 2012 IEEE 23rd International Symposium on Personal, Indoor, and Mobile Radio Communications (PIMRC’12). 327--332.

[43]

M. R. Palattella, T. Watteyne, Q. Wang, K. Muraoka, N. Accettura, D. Dujovne, L. A. Grieco, and T. Engel. 2016. On-the-fly bandwidth reservation for 6TiSCH wireless industrial networks. IEEE Sensors Journal 16, 2 (Jan. 2016), 550--560.

[44]

A. Pantelidou and A. Ephremides. 2009. The scheduling problem in wireless networks. Journal of Communications and Networks 11, 5 (Oct. 2009), 489--499.

[45]

Sana Rekik, Nouha Baccour, Mohamed Jmaiel, Khalil Drira, and Luigi Alfredo Grieco. 2018. Autonomous and traffic-aware scheduling for TSCH networks. Computer Networks 135 (April 2018), 201--212.

[46]

M. Richart, J. Baliosian, J. Serrat, and J. Gorricho. 2016. Resource slicing in virtual wireless networks: A survey. IEEE Transactions on Network and Service Management 13, 3 (Sept. 2016), 462--476.

Digital Library

[47]

Elva J. H. Robinson, Nigel R. Franks, Samuel Ellis, Saki Okuda, and James A. R. Marshall. 2011. A simple threshold rule is sufficient to explain sophisticated collective decision-making. PLoS One 6, 5 (2011), e19981.

[48]

K. Ross and N. Bambos. 2004. Local search scheduling algorithms for maximal throughput in packet switches. In Proceedings of the 23rd Conference of the IEEE Communications Society (INFOCOM’04), Vol. 2. 1158--1169.

[49]

Z. Shelby, S. Chakrabarti, E. Nordmark, and C. Bormann. 2012. Neighbor Discovery Optimization for IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs). RFC 6775. RFC Editor.

[50]

J. Song, S. Han, A. Mok, D. Chen, M. Lucas, M. Nixon, and W. Pratt. 2008. WirelessHART: Applying wireless technology in real-time industrial process control. In Proceedings of the 2008 IEEE Real-Time and Embedded Technology and Applications Symposium. 377--386.

Digital Library

[51]

Ridha Soua and Pascale Minet. 2015. Multichannel assignment protocols in wireless sensor networks. Pervasive and Mobile Computing 16, PA (Jan. 2015), 2--21.

[52]

Ridha Soua, Pascale Minet, and Erwan Livolant. 2016. Wave: A distributed scheduling algorithm for convergecast in IEEE 802.15.4e TSCH networks. Transactions on Emerging Telecommunications Technologies 27, 4 (2016), 557--575.

Digital Library

[53]

Rodrigo Teles Hermeto, Antoine Gallais, and Fabrice Theoleyre. 2017. Scheduling for IEEE802.15.4-TSCH and slow channel hopping MAC in low power industrial wireless networks: A survey. Computer Communications 114 (Dec. 2017), 84--105.

[54]

Fabrice Theoleyre and Georgios Z. Papadopoulos. 2016. Experimental validation of a distributed self-configured 6TiSCH with traffic isolation in low power lossy networks. In Proceedings of the 19th ACM International Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems. ACM, New York, NY, 102--110.

[55]

Xavier Vilajosana, Kris Pister, and Thomas Watteyne. 2017. Minimal 6TiSCH Configuration. Internet Draft draft-ietf-6tisch-minimal-19. Internet Engineering Task Force. https://tools.ietf.org/html/draft-ietf-6tisch-minimal-19.

[56]

Q. Wang, X. Vilajosana, and T. Watteyne. 2018. 6TiSCH Operation Sublayer (6top) Protocol (6P). RFC 8480. RFC Editor.

[57]

T. Watteyne, S. Lanzisera, A. Mehta, and K. S. J. Pister. 2010. Mitigating multipath fading through channel hopping in wireless sensor networks. In Proceedings of the 2010 IEEE International Conference on Communications. 1--5.

[58]

Thomas Watteyne, Ankur Mehta, and Kris Pister. 2009. Reliability through frequency diversity: Why channel hopping makes sense. In Proceedings of the 6th ACM Symposium on Performance Evaluation of Wireless Ad Hoc, Sensor, and Ubiquitous Networks (PE-WASUN’09). ACM, New York, NY, 116--123.

Digital Library

[59]

T. Watteyne, J. Weiss, L. Doherty, and J. Simon. 2015. Industrial IEEE802.15.4e networks: Performance and trade-offs. In Proceedings of the 2015 IEEE International Conference on Communications (ICC’15). 604--609.

[60]

T. Winter, P. Thubert, A. Brandt, J. Hui, R. Kelsey, P. Levis, K. Pister, R. Struik, J. P. Vasseur, and R. Alexander. 2012. RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks. RFC 6550. RFC Editor. http://www.rfc-editor.org/rfc/rfc6550.txt.

Digital Library

[61]

Hyungsuk Won, Han Cai, Do Young Eun, Katherine Guo, Arun Netravali, Injong Rhee, and Krishan Sabnani. 2009. Multicast scheduling in cellular data networks. IEEE Transactions on Wireless Communications 8, 9 (2009), 4540--4549.

Digital Library

Cited By

Vieira Junior IGranjal JCurado M(2025)Insights for metrics in assessing TSCH scheduling efficiencyInternet of Things10.1016/j.iot.2024.10144029(101440)Online publication date: Jan-2025
https://doi.org/10.1016/j.iot.2024.101440
Zhang YHuang HHuang QHan Y(2024)6TiSCH IIoT network: A reviewComputer Networks10.1016/j.comnet.2024.110759254(110759)Online publication date: Dec-2024
https://doi.org/10.1016/j.comnet.2024.110759
Chakraborty RHolm JPedersen TPopovski P(2023)Finding Representative Sampling Subsets in Sensor Graphs Using Time-series SimilaritiesACM Transactions on Sensor Networks10.1145/359518119:4(1-32)Online publication date: 11-May-2023
https://dl.acm.org/doi/10.1145/3595181
Show More Cited By

Index Terms

Distributed Reliable and Energy-Efficient Scheduling for LR-WPANs

Recommendations

Improving Spectral and Temporal Efficiency of Collocated IEEE 802.15.4 LR-WPANs

The number of frequency channels specified for IEEE 802.15.4 low-rate wireless personal area networks (LR-WPANs) does not suffice to operate a variety of collocated WPAN applications that the standard is targeting. To overcome this limit, we introduce ...
EDSF: Efficient Distributed Scheduling Function for IETF 6TiSCH-based Industrial Wireless Networks
Abstract
IETF 6TiSCH, which is composed of the IEEE802.15.4e and IPv6 RPL protocols, is a highly reliable and low-power industrial wireless network protocol stack. IEEE802.15.4e is the medium access control (MAC) layer protocol of the protocol stack—it ...
A Distributed TDMA Slot Scheduling Algorithm for Spatially Correlated Contention in WSNs
WAINA '13: Proceedings of the 2013 27th International Conference on Advanced Information Networking and Applications Workshops

In wireless sensor networks (WSNs) the communication traffic is often time and space correlated, where multiple nodes in a proximity start transmitting at the same time. Such a situation is known as spatially correlated contention. The random access ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Sensor Networks

ACM Transactions on Sensor Networks Volume 16, Issue 4

November 2020

311 pages

ISSN:1550-4859

EISSN:1550-4867

DOI:10.1145/3414039

Editor:
Yunhao Liu
Tsinghua University, China

Issue’s Table of Contents

Copyright © 2020 ACM.

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 25 August 2020

Accepted: 01 May 2020

Revised: 01 April 2020

Received: 01 May 2019

Published in TOSN Volume 16, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Eindhoven University of Technology (the Netherlands)
European Unions Horizon 2020 project INTER-IOT

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
187
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)2

Reflects downloads up to 18 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Vieira Junior IGranjal JCurado M(2025)Insights for metrics in assessing TSCH scheduling efficiencyInternet of Things10.1016/j.iot.2024.10144029(101440)Online publication date: Jan-2025
https://doi.org/10.1016/j.iot.2024.101440
Zhang YHuang HHuang QHan Y(2024)6TiSCH IIoT network: A reviewComputer Networks10.1016/j.comnet.2024.110759254(110759)Online publication date: Dec-2024
https://doi.org/10.1016/j.comnet.2024.110759
Chakraborty RHolm JPedersen TPopovski P(2023)Finding Representative Sampling Subsets in Sensor Graphs Using Time-series SimilaritiesACM Transactions on Sensor Networks10.1145/359518119:4(1-32)Online publication date: 11-May-2023
https://dl.acm.org/doi/10.1145/3595181
Biri ADa Forno RKuonen TMager FZimmerling MThiele L(2023)Hydra: Concurrent Coordination for Fault-tolerant NetworkingProceedings of the 22nd International Conference on Information Processing in Sensor Networks10.1145/3583120.3587047(219-232)Online publication date: 9-May-2023
https://dl.acm.org/doi/10.1145/3583120.3587047
Yaman Avan der Lee TIacca G(2023)Online distributed evolutionary optimization of Time Division Multiple Access protocolsExpert Systems with Applications10.1016/j.eswa.2022.118627211(118627)Online publication date: Jan-2023
https://doi.org/10.1016/j.eswa.2022.118627

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Media

Figures

Other

Tables

View Issue’s Table of Contents