research-article

Open access

DeepGANTT: A Scalable Deep Learning Scheduler for Backscatter Networks

Authors:

Daniel F. Perez-Ramirez,

Carlos Pérez-Penichet,

Nicolas Tsiftes,

Magnus BomanAuthors Info & Claims

IPSN '23: Proceedings of the 22nd International Conference on Information Processing in Sensor Networks

Pages 163 - 176

https://doi.org/10.1145/3583120.3586957

Published: 09 May 2023 Publication History

All formats PDF

Abstract

Novel backscatter communication techniques enable battery-free sensor tags to interoperate with unmodified standard IoT devices, extending a sensor network’s capabilities in a scalable manner. Without requiring additional dedicated infrastructure, the battery-free tags harvest energy from the environment, while the IoT devices provide them with the unmodulated carrier they need to communicate. A schedule coordinates the provision of carriers for the communications of battery-free devices with IoT nodes. Optimal carrier scheduling is an NP-hard problem that limits the scalability of network deployments. Thus, existing solutions waste energy and other valuable resources by scheduling the carriers suboptimally. We present DeepGANTT, a deep learning scheduler that leverages graph neural networks to efficiently provide near-optimal carrier scheduling. We train our scheduler with optimal schedules of relatively small networks obtained from a constraint optimization solver, achieving a performance within 3% of the optimum. Without the need to retrain, our scheduler generalizes to networks 6 × larger in the number of nodes and 10 × larger in the number of tags than those used for training. DeepGANTT breaks the scalability limitations of the optimal scheduler and reduces carrier utilization by up to compared to the state-of-the-art heuristic. As a consequence, our scheduler efficiently reduces energy and spectrum utilization in backscatter networks.

References

[1]

Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton. 2016. Layer Normalization. In Proc. Advances in Neural Information Processing Systems (NIPS) 2016 Deep Learn. Symp.NIPS. arXiv:1607.06450

[2]

Rajarshi Bhattacharyya, Archana Bura, Desik Rengarajan, Mason Rumuly, Srinivas Shakkottai, Dileep Kalathil, Ricky K. P. Mok, and Amogh Dhamdhere. 2019. QFlow: A Reinforcement Learning Approach to High QoE Video Streaming over Wireless Networks. Proc Int. Symp. Mobile Ad Hoc Netw. Comput. (MobiHoc), 251–260. arxiv:1901.00959

Digital Library

[3]

Christopher M Bishop and Nasser M Nasrabadi. 2006. Pattern recognition and machine learning. Springer.

Digital Library

[4]

Bluetooth SIG. 2021. Bluetooth Core Specification 5.3.

[5]

Hanjun Dai, Elias B. Khalil, Yuyu Zhang, Bistra Dilkina, and Le Song. 2017. Learning Combinatorial Optimization Algorithms over Graphs. In Proc. Advances Neural Inf. Process. Syst. (NIPS), Vol. 2017-Decem. Neural information processing systems foundation, 6349–6359. arxiv:1704.01665

[6]

Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. In Proc. Advances in Neural Inf. Process. Syst. (NeurIPS). NeurIPS, 3844–3852. arxiv:1606.09375

[7]

Simon Duquennoy, Atis Elsts, Beshr Al Nahas, and George Oikonomou. 2017. TSCH and 6TiSCH for Contiki: Challenges, Design and Evaluation. In 2017 13th International Conference on Distributed Computing in Sensor Systems (DCOSS). 11–18. https://doi.org/10.1109/DCOSS.2017.29

[8]

Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2020. Benchmarking Graph Neural Networks. Technical Report. arxiv:2003.00982

[9]

Joshua Ensworth and Matthew S. Reynolds. 2015. Every smart phone is a backscatter reader: Modulated backscatter compatibility with Bluetooth 4.0 Low Energy (BLE) devices. In Proc. Ann. Conf. RFID. IEEE.

[10]

Federico Ferrari, Marco Zimmerling, Lothar Thiele, and Olga Saukh. 2011. Efficient network flooding and time synchronization with Glossy. In Proc. 10th ACM/IEEE Int. Conf. Information Processing in Sensor Networks. 73–84.

[11]

Matthias Fey and Jan E. Lenssen. 2019. Fast Graph Representation Learning with PyTorch Geometric. In Proc. ICLR Workshop Representation Learn. Graphs Manifolds.

[12]

Kai Geissdoerfer and Marco Zimmerling. 2021. Bootstrapping Battery-free Wireless Networks: Efficient Neighbor Discovery and Synchronization in the Face of Intermittency. In (NSDI’21). 439–455.

[13]

Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. 2017. Neural Message Passing for Quantum Chemistry. Proc. 34th Int. Conf. Mach. Learn. (ICML) 3 (apr 2017), 2053–2070. arxiv:1704.01212

[14]

Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. 2008. Exploring Network Structure, Dynamics, and Function using NetworkX. In Proceedings of the 7th Python in Science Conference, Gaël Varoquaux, Travis Vaught, and Jarrod Millman (Eds.). Pasadena, CA USA, 11 – 15.

[15]

William L Hamilton. 2020. Graph representation learning. Vol. 14. Morgan & Claypool Publishers.

[16]

William L. Hamilton, Rex Ying, and Jure Leskovec. 2017. Inductive Representation Learning on Large Graphs. In Proc. Advances Neural Inf. Process. Syst. (NIPS), Vol. 2017-Decem. Neural information processing systems foundation, 1025–1035.

[17]

Essia Hamouda, Nathalie Mitton, and David Simplot-Ryl. 2011. Reader Anti-collision in dense RFID networks with mobile tags. In 2011 IEEE International Conference on RFID-Technologies and Applications. 327–334. https://doi.org/10.1109/RFID-TA.2011.6068657

[18]

Mehrdad Hessar, Ali Najafi, and Shyamnath Gollakota. 2018. NetScatter: Enabling Large-Scale Backscatter Networks. In NSDI’18. USENIX.

[19]

Josiah Hester and Jacob Sorber. 2017. The Future of Sensing is Batteryless, Intermittent, and Awesome. In Proc. 15th ACM Conf. on Embedded Netw. Sensor Syst. (Delft, Netherlands) (SenSys ’17). Association for Computing Machinery, New York, NY, USA, Article 21, 6 pages. https://doi.org/10.1145/3131672.3131699

Digital Library

[20]

Nguye Van Huynh, Dinh Thai Hoang, Dusit Niyato, Ping Wang, and Dong In Kim. 2018. Optimal Time Scheduling for Wireless-Powered Backscatter Communication Networks. IEEE Wireless Commun. Lett. 7 (2018), 820–823.

[21]

IEEE. 2016. IEEE Standard for Low-Rate Wireless Networks –Amendment 2: Ultra-Low Power Physical Layer.

[22]

Vikram Iyer et al.2016. Inter-Technology Backscatter: Towards Internet Connectivity for Implanted Devices. ACM, 356–369. https://doi.org/10.1145/2934872.2934894

Digital Library

[23]

Furqan Jameel, Ruifeng Duan, Zheng Chang, Aleksi Liljemark, Tapani Ristaniemi, and Riku Jantti. 2019. Applications of backscatter communications for healthcare networks. IEEE Network 33, 6 (2019), 50–57.

Digital Library

[24]

Y. Karimi, A. Athalye, S. R. Das, P. M. Djurić, and M. Stanaćević. 2017. Design of a backscatter-based Tag-to-Tag system. In 2017 IEEE International Conference on RFID (IEEE RFID). 6–12. https://doi.org/10.1109/RFID.2017.7945579

[25]

Bryce Kellogg et al.2014. Wi-Fi Backscatter: Internet Connectivity for RF-powered Devices. In Proc. Special Interest Group Data Commun. (SIGCOMM). ACM, New York, NY, USA, 607–618. https://doi.org/10.1145/2619239.2626319

Digital Library

[26]

Bryce Kellogg et al.2016. Passive Wi-Fi: Bringing Low Power to Wi-Fi Transmissions. In Proc. Symp. Networked Syst. Des. Implementation (NSDI). NSDI, 151–164.

[27]

Diederik P Kingma and Jimmy Lei Ba. 2015. Adam: A Method For Stochastic Optimization. In Proc. Int. Conf. Learn. Representations (ICLR). arxiv:1412.6980v9

[28]

Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In Proc. 5th Int. Conf. Learn. Representations (ICLR). ICLR. arxiv:1609.02907

[29]

P. Levis, T. Clausen, J. Hui, O. Gnawali, and J. Ko. 2011. The Trickle Algorithm. Retrieved Feb. 2023 from https://www.rfc-editor.org/rfc/rfc6206

[30]

Zhuwen Li, Qifeng Chen, and Vladlen Koltun. 2018. Combinatorial optimization with graph convolutional networks and guided tree search. In Proc. Advances in Neural Inf. Process. Syst. (NeurIPS). 539–548.

[31]

Vincent Liu et al.2013. Ambient Backscatter: Wireless Communication out of Thin Air. In Proc. Special Interest Group Data Commun. (SIGCOMM). ACM, 39–50. https://doi.org/10.1145/2486001.2486015

Digital Library

[32]

Jerry Ma and Denis Yarats. 2021. On the adequacy of untuned warmup for adaptive optimization. In Proc. of the AAAI Conf. Artificial Intelligence, Vol. 35. 8828–8836.

[33]

A. Y. Majid, M. Jansen, G. O. Delgado, K. S. Yildirim, and P. Pawełłzak. 2019. Multi-hop Backscatter Tag-to-Tag Networks. In Proc. Int. Conf. Comput. Commun. (INFOCOM). IEEE, 721–729. https://doi.org/10.1109/INFOCOM.2019.8737551

Digital Library

[34]

Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, and Ambuj Singh. 2020. Learning Heuristics over Large Graphs via Deep Reinforcement Learning. In Proc. 34th Conf. Neural Inf. Process. Syst. (NIPS). arxiv:1903.03332

[35]

Kevin P Murphy. 2012. Machine learning: a probabilistic perspective. MIT press.

Digital Library

[36]

Nicholas Nethercote, Peter J. Stuckey, Ralph Becket, Sebastian Brand, Gregory J. Duck, and Guido Tack. 2007. MiniZinc: Towards a standard CP modelling language. In Lecture Notes in Computer Science, Vol. 4741 LNCS. Springer Verlag, 529–543. https://doi.org/10.1007/978-3-540-74970-7_38

[37]

P. V. Nikitin, S. Ramamurthy, R. Martinez, and K. V. S. Rao. 2012. Passive tag-to-tag communication. In Proc. Int. Conf. RFID (RFID). IEEE, 177–184. https://doi.org/10.1109/RFID.2012.6193048

[38]

George Oikonomou, Simon Duquennoy, Atis Elsts, Joakim Eriksson, Yasuyuki Tanaka, and Nicolas Tsiftes. 2022. The Contiki-NG open source operating system for next generation IoT devices. SoftwareX 18 (2022), 101089. https://doi.org/10.1016/j.softx.2022.101089

[39]

Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, and et al.2019. PyTorch: An Imperative Style, High-Performance Deep Learning Library. In Proc. Advances Neural Inf. Process. Syst., H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (Eds.). Curran Associates, Inc., 8024–8035.

[40]

Carlos Pérez-Penichet, Frederik Hermans, Ambuj Varshney, and Thiemo Voigt. 2016. Augmenting IoT networks with backscatter-enabled passive sensor tags. In Proc. Annu. Int. Conf. Mobile Comput. Netw. (MOBICOM). ACM, 23–27. https://doi.org/10.1145/2980115.2980132

Digital Library

[41]

Carlos Pérez-Penichet, Dilushi Piumwardane, Christian Rohner, and Thiemo Voigt. 2020. A Fast Carrier Scheduling Algorithm for Battery-free Sensor Tags in Commodity Wireless Networks. In Proc. Int. Conf. Comput. Commun. (INFOCOM). IEEE, 994–1003. https://doi.org/10.1109/infocom41043.2020.9155241

Digital Library

[42]

Laurent Perron and Vincent Furnon. 2019. OR-Tools. https://developers.google.com/optimization/

[43]

Carlos Pérez-Penichet, Dilushi Piumwardane, Christian Rohner, and Thiemo Voigt. 2020. TagAlong: Efficient Integration of Battery-Free Sensor Tags in Standard Wireless Networks. In Proc. 19th ACM/IEEE Int. Conf. Inf. Process. Sensor Netw. (IPSN). Sydney, Australia. https://doi.org/10.1109/IPSN48710.2020.00020

[44]

Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2009. The graph neural network model. IEEE Trans. Neural Netw. 20, 1 (jan 2009), 61–80. https://doi.org/10.1109/TNN.2008.2005605

Digital Library

[45]

Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjing Wang, and Yu Sun. 2021. Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification. Technical Report. arxiv:2009.03509v5

[46]

Vamsi Talla, Mehrdad Hessar, Bryce Kellogg, Ali Najafi, Joshua R. Smith, and Shyamnath Gollakota. 2017. LoRa Backscatter: Enabling The Vision of Ubiquitous Connectivity. Proc. ACM Interact. Mob. Wearable Ubiquitous Technol. 1, 3, 105:1–105:24. https://doi.org/10.1145/3130970

Digital Library

[47]

Ambuj Varshney, Carlos Pérez-Penichet, Christian Rohner, and Thiemo Voigt. 2017. LoRea: A Backscatter Architecture That Achieves a Long Communication Range. In Proc. 15th ACM Conf. Embedded Netw. Sensor Syst. (Netherlands) (SenSys ’17). Association for Computing Machinery, New York, NY, USA, Article 50, 2 pages. https://doi.org/10.1145/3131672.3136996

Digital Library

[48]

Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Proc. Advances Neural Inf. Process. Syst. (NIPS), Vol. 2017-Decem. NIPS, 5999–6009.

[49]

Petar Veličković, Arantxa Casanova, Pietro Liò, Guillem Cucurull, Adriana Romero, and Yoshua Bengio. 2018. Graph attention networks. In Proc. 6th Int. Conf. Learn. Representations (ICLR). ICLR. arxiv:1710.10903

[50]

Natalia Vesselinova, Rebecca Steinert, Daniel F Perez-Ramirez, and Magnus Boman. 2020. Learning combinatorial optimization on graphs: A survey with applications to networking. IEEE Access 8 (2020), 120388–120416.

[51]

Oriol Vinyals, Google Brain, Meire Fortunato, and Navdeep Jaitly. 2015. Pointer Networks. In Proc. Advances Neural Inf. Process. Syst. (NIPS). 2692–2700.

[52]

Fangxin Wang, Cong Zhang, Feng Wang, Jiangchuan Liu, Yifei Zhu, Haitian Pang, and Lifeng Sun. 2019. Intelligent Edge-Assisted Crowdcast with Deep Reinforcement Learning for Personalized QoE. In Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), Vol. 2019-April. IEEE, 910–918. https://doi.org/10.1109/INFOCOM.2019.8737456

Digital Library

[53]

Anran Wang et al.2017. FM Backscatter: Enabling Connected Cities and Smart Fabrics. In NSDI’17. USENIX, 243–258.

[54]

T. Winter. 2012. RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks. Retrieved Oct. 2022 from https://www.rfc-editor.org/rfc/rfc6550

[55]

Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. 2021. A Comprehensive Survey on Graph Neural Networks. IEEE Trans. Neural Netw. 32, 1 (2021), 4–24. https://doi.org/10.1109/TNNLS.2020.2978386

[56]

L. Yang, J. Han, Y. Qi, C. Wang, T. Gu, and Y. Liu. 2011. Season: Shelving interference and joint identification in large-scale RFID systems. In Proc. Int. Conf. Comput. Commun. (INFOCOM). IEEE, 3092–3100. https://doi.org/10.1109/INFCOM.2011.5935154

[57]

Jiaxuan You, Rex Ying, and Jure Leskovec. 2019. Position-aware Graph Neural Networks. In Proc. 36th Int. Conf. Mach. Learn. (ICML). arxiv:1906.04817v2

[58]

H. Yue, C. Zhang, M. Pan, Y. Fang, and S. Chen. 2012. A time-efficient information collection protocol for large-scale RFID systems. In Proc. Int. Conf. Comput. Commun. (INFOCOM). IEEE, 2158–2166. https://doi.org/10.1109/INFCOM.2012.6195599

[59]

Han Zhang, Wenzhong Li, Shaohua Gao, Xiaoliang Wang, and Baoliu Ye. 2019. ReLeS: A Neural Adaptive Multipath Scheduler based on Deep Reinforcement Learning. In Proc. Int. Conf. Comput. Commun. (INFOCOM), Vol. 2019-April. IEEE, 1648–1656. https://doi.org/10.1109/INFOCOM.2019.8737649

Digital Library

[60]

Pengyu Zhang, Colleen Josephson, Dinesh Bharadia, and Sachin Katti. 2017. FreeRider: Backscatter Communication Using Commodity Radios(CoNEXT ’17). ACM, Incheon, Republic of Korea, 389–401. https://doi.org/10.1145/3143361.3143374

Digital Library

Cited By

Siam SAhn HLiu LAlam SShen HCao ZShroff NKrishnamachari BSrivastava MZhang M(2024)Artificial Intelligence of Things: A SurveyACM Transactions on Sensor Networks10.1145/3690639Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.1145/3690639
Zou YNa XGuo XSun YHe Y(2024)Trident: Interference Avoidance in Multi-reader Backscatter Network via Frequency-space DivisionIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621258(1761-1770)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621258

Index Terms

DeepGANTT: A Scalable Deep Learning Scheduler for Backscatter Networks
1. Computing methodologies
  1. Artificial intelligence
    1. Planning and scheduling
  2. Machine learning
2. Networks
  1. Network types
    1. Cyber-physical networks
      1. Sensor networks

Recommendations

The Constrained Parallel-Machine Scheduling Problem with Divisible Processing Times and Penalties
Algorithmic Aspects in Information and Management
Abstract
We consider the constrained parallel-machine scheduling problem with divisible processing times and penalties (the CPS-DTP problem, for short). Specifically, given a set $M = {a_{1}, a_{2}, \dots, a_{m}}$ of m identical machines, and a set $J = {b_{1}, b_{2}, \dots, b_{n}}$ of n jobs, ... $_{}$ $_{}^{}$ $_{}^{}$ $_{}_{}$ $_{}_{}$ $_{}$ $_{}$ $_{}$ $_{}$ $_{}$ $_{}$ $_{}$
An iterated greedy algorithm with optimization of partial solutions for the makespan permutation flowshop problem

We present a new iterated greedy algorithm for the permutation flowshop problem under makespan objective.Our algorithm applies local search on partial solutions after the destruction phase.Our algorithm compares favorably with others from the literature ...
Profitable scheduling on multiple speed-scalable processors
SPAA '13: Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures

We present a new online algorithm for profit-oriented scheduling on multiple speed-scalable processors. Moreover, we provide a tight analysis of the algorithm's competitiveness. Our results generalize and improve upon work by Chan et al. [10], which ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

IPSN '23: Proceedings of the 22nd International Conference on Information Processing in Sensor Networks

May 2023

385 pages

ISBN:9798400701184

DOI:10.1145/3583120

Copyright © 2023 Owner/Author.

Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.

Sponsors

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 May 2023

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

IPSN '23

Sponsor:

SIGBED

IPSN '23: The 22nd International Conference on Information Processing in Sensor Networks

May 9 - 12, 2023

TX, San Antonio, USA

Acceptance Rates

Overall Acceptance Rate 143 of 593 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
455
Total Downloads

Downloads (Last 12 months)254
Downloads (Last 6 weeks)25

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Siam SAhn HLiu LAlam SShen HCao ZShroff NKrishnamachari BSrivastava MZhang M(2024)Artificial Intelligence of Things: A SurveyACM Transactions on Sensor Networks10.1145/3690639Online publication date: 30-Aug-2024
https://dl.acm.org/doi/10.1145/3690639
Zou YNa XGuo XSun YHe Y(2024)Trident: Interference Avoidance in Multi-reader Backscatter Network via Frequency-space DivisionIEEE INFOCOM 2024 - IEEE Conference on Computer Communications10.1109/INFOCOM52122.2024.10621258(1761-1770)Online publication date: 20-May-2024
https://doi.org/10.1109/INFOCOM52122.2024.10621258

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

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 Publication

Media

Figures

Other

Tables

View Table of Contents