Vinicius Fulber-Garcia
ABSTRACT
Recent advances in networking technologies such as massive Internet-of-Things and 6G-and-beyond cellular networks indicate a trend towards increasingly dense wireless communications. A wireless communication channel is a shared medium that demands access control, such as proper transmission scheduling. The SINR model can improve the performance of ultra-dense wireless networks by taking into consideration the effects of interference to allow multiple simultaneous transmissions in the same coverage area. However, finding the shortest schedule in wireless networks under the SINR model is an NP-hard problem. In this work, we present a greedy heuristic algorithm to solve that problem. The proposed solution, called Sk-Greedy (Stochastic k Greedy) algorithm produces a complete transmission schedule optimizing size, with the purpose of increasing the number of simultaneous transmissions (i.e., spatial reuse) thus allowing devices to communicate as frequently as possible. Simulation results are presented, including comparisons of Sk-Greedy with the optimal algorithm. Results confirm that the solution requires short execution times to produce near-optimal schedules.
- Fahad Al-dhelaan, Pengjun Wan, and Huaqiang Yuan. 2016. A New Paradigm for Shortest Link Scheduling in Wireless Networks: Theory and Applications. In Wireless Algorithms, Systems, and Applications. Spring, China, 24–36.Google Scholar
- Mohamed Sofiane Batta, Saad Harous, Lemia Louail, and Zibouda Aliouat. 2019. A Distributed TDMA Scheduling Algorithm for Latency Minimization in Internet of Things. In IEEE International Conference on Electro Information Technology. IEEE, 108–113.Google ScholarCross Ref
- Douglas M. Blough, G. Resta, and P. Santi. 2010. Approximation Algorithms for Wireless Link Scheduling With SINR-Based Interference. IEEE/ACM Transactions on Networking 18, 6 (2010), 1701–1712.Google ScholarDigital Library
- Gurashish Brar, Douglas M. Blough, and Paolo Santi. 2006. Computationally Efficient Scheduling with the Physical Interference Model for Throughput Improvement in Wireless Mesh Networks. In Annual International Conference on Mobile Computing and Networking. ACM, 2–13.Google Scholar
- Yuchao Chang, Xiaobing Yuan, Baoqing Li, Dusit Niyato, and Naofal Al-Dhahir. 2018. A joint unsupervised learning and genetic algorithm approach for topology control in energy-efficient ultra-dense wireless sensor networks. IEEE Communications Letters 22, 11 (2018), 2370–2373.Google ScholarCross Ref
- Mostafa Zaman Chowdhury, Md. Shahjalal, Shakil Ahmed, and Yeong Min Jang. 2020. 6G Wireless Communication Systems: Applications, Requirements, Technologies, Challenges, and Research Directions. IEEE Open Journal of the Communications Society 1 (2020), 957–975.Google ScholarCross Ref
- José Carlos da Silva and Flávio Assis. 2019. A distributed algorithm to schedule TSCH links under the SINR model. Design Automation for Embedded Systems 23, 1 (2019), 21–39.Google ScholarDigital Library
- Fábio Engel and Elias Duarte. 2021. A Down-to-Earth Scheduling Strategy for Dense SINR Wireless Networks. In Latin-American Symposium on Dependable Computing. SBC, 1–6.Google Scholar
- Olga Goussevskaia, Yvonne Anne Oswald, and Rogert Wattenhofer. 2007. Complexity in Geometric SINR. In ACM Int. Symp. Mobile Ad Hoc Networking and Computing. ACM, 100–109.Google Scholar
- Olga Goussevskaia, Yvonne-Anne Pignolet, and Roger Wattenhofer. 2010. Efficiency of Wireless Networks: Approximation Algorithms for the Physical Interference Model. Now Foundations and Trends.Google Scholar
- Fengxian Guo, F. Richard Yu, Heli Zhang, Xi Li, Hong Ji, and Victor C. M. Leung. 2021. Enabling Massive IoT Toward 6G: A Comprehensive Survey. IEEE Internet of Things Journal 8, 15 (2021), 11891–11915.Google ScholarCross Ref
- Magnús M. Halldórsson and Roger Wattenhofer. 2019. Wireless Network Algorithmics. Springer International Publishing, 141–160.Google Scholar
- Denis Jeanneau, Luiz A Rodrigues, Luciana Arantes, and Elias P Duarte Jr. 2017. An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detection. Journal of the Brazilian Computer Society 23, 1 (2017), 1–14.Google ScholarCross Ref
- Neeraj Kumar, Al-Sakib Khan Pathan, Elias P Duarte, and Riaz Ahmed Shaikh. 2015. Critical applications in vehicular ad hoc/sensor networks. Telecommunication Systems 58, 4 (2015), 275–277.Google ScholarDigital Library
- Nhat X. Lam, Tien Tran, Min Kyung An, and Dung T. Huynh. 2015. A note on the complexity of minimum latency data aggregation scheduling with uniform power in physical interference model. Theoretical Computer Science 569 (2015), 70–73.Google ScholarDigital Library
- Gyeongheon Lee and Joosang Youn. 2020. Group-based Transmission Scheduling Scheme for Building LoRa-based Massive IoT. In International Conference on Artificial Intelligence in Information and Communication. 583–586.Google Scholar
- A. V. Lotov and K. Miettinen. 2008. Visualizing the Pareto frontier. In Multiobjective optimization. Springer, 213–243.Google Scholar
- Shaohe Lv, Xiaodong Wang, and Xingming Zhou. 2010. Scheduling under SINR Model in Ad Hoc Networks with Successive Interference Cancellation. In IEEE Globecom. IEEE, 1–5.Google Scholar
- Ritesh Maheshwari, Shweta Jain, and Samir R. Das. 2008. A Measurement Study of Interference Modeling and Scheduling in Low-Power Wireless Networks. In ACM Conference on Embedded Network Sensor Systems. ACM, 141–154.Google ScholarDigital Library
- Renato EN Moraes, Welber WF dos Reis, Helder RO Rocha, and Daniel JC Coura. 2020. Power-efficient and interference-free link scheduling algorithms for connected wireless sensor networks. Wireless Networks 26, 5 (2020), 3099–3118.Google ScholarDigital Library
- Thomas Moscibroda and Roger Wattenhofer. 2006. The Complexity of Connectivity in Wireless Networks. In IEEE Computer and Communications Societies, Barcelona, Spain. IEEE, 1–13.Google Scholar
- Mohamed Saad. 2015. Wireless capacity maximization: A constrained genetic approach. In IEEE International Conference on Communications. 3855–3860.Google ScholarCross Ref
- Aggeliki Sgora, Dimitrios J. Vergados, and Dimitrios D. Vergados. 2015. A Survey of TDMA Scheduling Schemes in Wireless Multihop Networks. ACM Comput. Surv. 47, 3 (2015).Google Scholar
- Dongjin Son, Bhaskar Krishnamachari, and John Heidemann. 2006. Experimental Study of Concurrent Transmission in Wireless Sensor Networks. In The ACM Conference on Embedded Networked Sensor Systems. ACM, 237–250.Google Scholar
- Yinglei Teng, Mengting Liu, F Richard Yu, Victor CM Leung, Mei Song, and Yong Zhang. 2018. Resource allocation for ultra-dense networks: A survey, some research issues and challenges. IEEE Communications Surveys & Tutorials 21, 3 (2018), 2134–2168.Google ScholarCross Ref
- Rogerio C Turchetti and Elias P Duarte Jr. 2017. NFV-FD: Implementation of a failure detector using network virtualization technology. International Journal of Network Management 27, 6 (2017), e1988.Google ScholarCross Ref
- Curt M. White. 2015. Data Communications and Computer Networks: A Business User’s Approach (8 ed.). Cengage.Google Scholar
- Jiguo Yu, Baogui Huang, Xiuzhen Cheng, and Mohammed Atiquzzaman. 2016. Shortest link scheduling algorithms in wireless networks under the SINR model. IEEE Transactions on Vehicular Technology 66, 3 (2016), 2643–2657.Google ScholarCross Ref
Index Terms
- Sk-Greedy: A Heuristic Scheduling Algorithm for Wireless Networks under the SINR Model
Recommendations
Distributed multichannel MAC protocol for IEEE 802.11 ad hoc wireless LANs
The IEEE 802.11 standard supports several independent and equal-capacity communication channels, which can be shared simultaneously and accessed by mobile stations in existing wireless local area networks (WLANs). However, under the restriction of one ...
Distributed CSMA algorithms for link scheduling in multihop MIMO networks under SINR model
In this paper, we study distributed scheduling in multihop multiple-input-multiple-output (MIMO) networks. We first develop a "MIMO-pipe" model that provides the upper layers a set of rates and signal-to-interference-plus-noise ratio (SINR) requirements ...
A label-switching packet forwarding architecture for multi-hop wireless LANs
WOWMOM '02: Proceedings of the 5th ACM international workshop on Wireless mobile multimediaA router in wired network typically requires multiple network interfaces to act as a router or a forwarding node. In an ad-hoc multi-hop wireless network on the other hand, any node with a wireless network interface card can operate as a router or a ...
Comments