Sk-Iterative: Um Algoritmo Guloso para Escalonamento Eficiente em Redes Sem Fio Densas sob o Modelo SINR

• Chrystopher N. Bravos UFPR
• Fábio Engel de Camargo UTFPR
• Flávio Assis UFBA
• Elias P. Duarte Jr. UFPR

DOI: https://doi.org/10.5753/wtf.2024.2312

Resumo

As redes sem fio, incluindo redes celulares e para Internet das Coisas, se tornaram infraestruturas críticas. Ao mesmo tempo, é possível perceber uma tendência de aumento da densidade dos dispositivos. O modelo Signal-to-Interference-plus-Noise Ratio (SINR) é bastante atraente, por permitir o chamado reuso espacial: transmissões simultâneas de múltiplos dispositivos na mesma área de cobertura. O modelo leva em conta as interferências cumulativas sofridas pelas transmissões concorrentes, para permitir que o escalonamento tenha o máximo de transmissões simultâneas. Como o problema do escalonamento em redes SINR é NP-difícil, o uso de heurísticas é essencial para resolvê-lo na prática. Este trabalho apresenta o algoritmo guloso Sk-Iterative para o escalonamento em redes SINR. O algoritmo escalona enlaces produzidos de acordo com a heurística conhecida como Down-to-Earth (DTE). O algoritmo foi implementado através de simulação. Resultados mostram sua eficiência em termos do tamanho dos escalonamentos produzidos, próximos do ótimo.

Referências

Cai, Z., Lu, M., and Georghiades, C. (2003). Topology-transparent time division multiple access broadcast scheduling in multihop packet radio networks. IEEE Transactions on Vehicular Technology, 52(4):970–984.

Camargo, F. E. D. and Duarte, E. P. (2021). A down-to-earth scheduling strategy for dense SINR wireless networks. In 10th Latin-American Symp. Dep. Computing (LADC).

Duarte, E., Garrett, T., Bona, L., et al. (2010). Finding stable cliques of planetlab nodes. In IEEE/IFIP Int. Conf. Dependable Systems & Networks (DSN), pages 317–322.

Duarte, E. P., Weber, A., and Fonseca, K. V. (2011). Distributed diagnosis of dynamic events in partitionable arbitrary topology networks. IEEE Transactions on Parallel and Distributed Systems, 23(8):1415–1426.

Duarte Jr, E. P., Rodrigues, L. A., Camargo, E. T., and Turchetti, R. C. (2023). The missing piece: a distributed system-level diagnosis model for the implementation of unreliable failure detectors. Computing, 105(12):2821–2845.

Duarte Jr, E. P., Santini, R., and Cohen, J. (2004). Delivering packets during the routing convergence latency interval through highly connected detours. In International Conference on Dependable Systems and Networks, 2004, pages 495–504. IEEE.

Duarte Jr, E. P. and Weber, A. (2003). A distributed network connectivity algorithm. In The Sixth International Symposium on Autonomous Decentralized Systems, 2003. ISADS 2003., pages 285–292. IEEE.

Fulber-Garcia, V., de Camargo, F. E., and Duarte, E. P. (2022). Sk-greedy: A heuristic scheduling algorithm for wireless networks under the sinr model. In 2022 11th Latin-American Symposium on Dependable Computing (LADC). ACM.

Fulber-Garcia, V., Engel, F., and Duarte, E. P. (2024). A genetic scheduling strategy with spatial reuse for dense wireless networks. International Journal of Hybrid Intelligent Systems, 20(1):41–55.

Goussevskaia, O. (2009). Efficiency of wireless networks: Approximation algorithms for the physical interference model. Foundations and Trends in Networking, 4(3):313–420.

Goussevskaia, O., Oswald, Y. A., and Wattenhofer, R. (2007). Complexity in geometric SINR. In MobiHoc '07. ACM Press.

Grossman, T. and Wool, A. (1997). Computational experience with approximation algorithms for the set covering problem. European Journal of Operational Research, 101(1):81–92.

Halldorsson, M. M. and Tonoyan, T. (2019). Plain SINR is enough! In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 127–136.

Huawei (2024). Receiver sensitivity. [link]. Acessado em 20/03/2024.

Jeanneau, D. et al. (2017). An autonomic hierarchical reliable broadcast protocol for asynchronous distributed systems with failure detection. JBCS, 23:1–14.

Kumar, N., Pathan, A.-S. K., Duarte, E. P., and Shaikh, R. A. (2015). Critical applications in vehicular ad hoc/sensor networks. Telecommunication Systems, 58:275–277.

Nassu, B. T., Nanya, T., et al. (2007). Topology discovery in dynamic and decentralized networks with mobile agents and swarm intelligence. In ISDA, pages 685–690.

Rappaport, T. S. (2002). Wireless communications: principles and practice. Prent. Hall.

Sgora, A., Vergados, D. J., and Vergados, D. D. (2015). A survey of TDMA scheduling schemes in wireless multihop networks. ACM Computing Surveys, 47(3):1–39.

Teng, Y. et al. (2019). Resource allocation for ultra-dense networks: A survey, some research issues and challenges. IEEE Comm. Surveys Tutorials, 21(3):2134–2168.