Uma Estratégia Bioinspirada para Escalonamento em Redes Sem Fio sob o Modelo SINR
Resumo
A comunicação sem fio é hoje utilizada em larga escala. Novos avanços da tecnologia, como redes celulares 6G e Internet das coisas tendem a trazer ainda maior destaque e novos desafios, como densidades cada vez maiores. Um canal de comunicação sem fio é um meio compartilhado, que tem como um dos maiores desafios a interferência causada por transmissões simultâneas. Selecionar quais transmissões devem ocorrer simultaneamente, ou não, de maneira eficiente é conhecido como “problema do escalonamento”, um problema NP-Completo. Este trabalho apresenta uma heurística genética como solução para o problema do escalonamento em redes sem fio sob o modelo SINR. A heurística é especificada, avaliada por meio de experimentos, incluindo um teste de convergência e simulação para avaliar a sua capacidade em obter um escalonamento eficiente. Os resultados mostram que a solução proposta é capaz de produzir uma boa solução em tempo polinomial.
Referências
Al-dhelaan, F., Wan, P., and Yuan, H. (2016). A new paradigm for shortest link scheduling in wireless networks: Theory and applications. In Wireless Algorithms, Systems, and Applications.
Andrews, M. and Dinitz, M. (2009). Maximizing capacity in arbitrary wireless networks in the sinr model: Complexity and game theory. In INFOCOM, pages 1332-1340.
Batta, M. S., Harous, S., Louail, L., and Aliouat, Z. (2019). A distributed tdma scheduling algorithm for latency minimization in internet of things. In 2019 IEEE International Conference on Electro Information Technology (EIT), pages 108-113.
Blough, D. M., Resta, G., and Santi, P. (2010). Approximation algorithms for wireless link scheduling with sinr-based interference. IEEE/ACM Transactions on Networking, 18(6):1701-1712.
Brar, G., Blough, D. M., and Santi, P. (2006). Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In MobiCom, page 2-13. ACM.
Caprara, A., Toth, P., and Fischetti, M. (2000). Algorithms for the set covering problem. Annals of Operations Research, 98(1):353-371.
De Camargo, F. E. and Duarte, E. P. (2021). A down-to-earth scheduling strategy for dense sinr wireless networks. In 2021 10th Latin-American Symposium on Dependable Computing (LADC), pages 1-6.
Duarte Jr, E. P., Pozo, A. T., and Nassu, B. T. (2010). Fault diagnosis of multiprocessor systems based on genetic and estimation of distribution algorithms: a performance evaluation. International Journal on Artificial Intelligence Tools, 19(01):1-18.
Ergen, S. C. and Varaiya, P. (2010). Tdma scheduling algorithms for wireless sensor networks. Wireless Networks, 16(4):985-997.
Fulber-Garcia, V., dos Santos, C. R. P., Spinosa, E. J., and Duarte Jr, E. P. (2020). Mapeamento customizado de serviços de rede em múltiplos domínios baseado em heurísticas genéticas. In SBRC, pages 491-504. SBC.
Goussevskaia, O., Oswald, Y. A., and Wattenhofer, R. (2007). Complexity in geometric sinr. In Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '07, pages 100-109, New York, NY, USA. Association for Computing Machinery.
Goussevskaia, O., Pignolet, Y.-A., and Wattenhofer, R. (2010). Efficiency of Wireless Networks: Approximation Algorithms for the Physical Interference Model. Now Foundations and Trends.
Halldórsson, M. M. and Mitra, P. (2011). Wireless capacity with oblivious power in general metrics. In SODA, SODA '11, pages 1538-1548. SIAM.
Halldórsson, M. M. and Wattenhofer, R. (2019). Wireless Network Algorithmics, pages 141-160. Springer International Publishing, Cham.
Kar, A. K. (2016). Bio inspired computing - a review of algorithms and scope of applications. Expert Systems with Applications, 59:20-32.
Lam, N. X., Tran, T., An, M. K., and Huynh, D. T. (2015). A note on the complexity of minimum latency data aggregation scheduling with uniform power in physical interference model. Theoretical Computer Science, 569:70-73.
Lv, S., Wang, X., and Zhou, X. (2010). Scheduling under sinr model in ad hoc networks with successive interference cancellation. In 2010 IEEE Global Telecommunications Conference GLOBECOM 2010, pages 1-5.
Maheshwari, R., Jain, S., and Das, S. R. (2008). A measurement study of interference modeling and scheduling in low-power wireless networks. In The 6th ACM Conference on Embedded Network Sensor Systems, SenSys'08, pages 141-154.
Moscibroda, T. and Wattenhofer, R. (2006). The complexity of connectivity in wireless networks. In INFOCOM: 25th Annual Joint Conference of the IEEE Computer and Communications Societies, Barcelona, Spain.
Nassu, B. T., Duarte Jr, E. P., and Ramirez Pozo, A. T. (2005). A comparison of evolutionary algorithms for system-level diagnosis. In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 2053-2060.
Nelson, R. and Kleinrock, L. (1985). Spatial tdma: A collision-free multihop channel access protocol. IEEE Transactions on Communications, 33(9):934-944.
Saad, M. (2015). Wireless capacity maximization: A constrained genetic approach. In 2015 IEEE International Conference on Communications (ICC), pages 3855-3860.
Sgora, A., Vergados, D. J., and Vergados, D. D. (2015). A survey of tdma scheduling schemes in wireless multihop networks. ACM Comput. Surv., 47(3).
Son, D., Krishnamachari, B., and Heidemann, J. (2006). Experimental study of concurrent transmission in wireless sensor networks. In SenSys, pages 237-250. ACM.
White, C. M. (2015). Data Communications and Computer Networks: A Business User's Approach. Cengage, 8 edition.
Andrews, M. and Dinitz, M. (2009). Maximizing capacity in arbitrary wireless networks in the sinr model: Complexity and game theory. In INFOCOM, pages 1332-1340.
Batta, M. S., Harous, S., Louail, L., and Aliouat, Z. (2019). A distributed tdma scheduling algorithm for latency minimization in internet of things. In 2019 IEEE International Conference on Electro Information Technology (EIT), pages 108-113.
Blough, D. M., Resta, G., and Santi, P. (2010). Approximation algorithms for wireless link scheduling with sinr-based interference. IEEE/ACM Transactions on Networking, 18(6):1701-1712.
Brar, G., Blough, D. M., and Santi, P. (2006). Computationally efficient scheduling with the physical interference model for throughput improvement in wireless mesh networks. In MobiCom, page 2-13. ACM.
Caprara, A., Toth, P., and Fischetti, M. (2000). Algorithms for the set covering problem. Annals of Operations Research, 98(1):353-371.
De Camargo, F. E. and Duarte, E. P. (2021). A down-to-earth scheduling strategy for dense sinr wireless networks. In 2021 10th Latin-American Symposium on Dependable Computing (LADC), pages 1-6.
Duarte Jr, E. P., Pozo, A. T., and Nassu, B. T. (2010). Fault diagnosis of multiprocessor systems based on genetic and estimation of distribution algorithms: a performance evaluation. International Journal on Artificial Intelligence Tools, 19(01):1-18.
Ergen, S. C. and Varaiya, P. (2010). Tdma scheduling algorithms for wireless sensor networks. Wireless Networks, 16(4):985-997.
Fulber-Garcia, V., dos Santos, C. R. P., Spinosa, E. J., and Duarte Jr, E. P. (2020). Mapeamento customizado de serviços de rede em múltiplos domínios baseado em heurísticas genéticas. In SBRC, pages 491-504. SBC.
Goussevskaia, O., Oswald, Y. A., and Wattenhofer, R. (2007). Complexity in geometric sinr. In Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc '07, pages 100-109, New York, NY, USA. Association for Computing Machinery.
Goussevskaia, O., Pignolet, Y.-A., and Wattenhofer, R. (2010). Efficiency of Wireless Networks: Approximation Algorithms for the Physical Interference Model. Now Foundations and Trends.
Halldórsson, M. M. and Mitra, P. (2011). Wireless capacity with oblivious power in general metrics. In SODA, SODA '11, pages 1538-1548. SIAM.
Halldórsson, M. M. and Wattenhofer, R. (2019). Wireless Network Algorithmics, pages 141-160. Springer International Publishing, Cham.
Kar, A. K. (2016). Bio inspired computing - a review of algorithms and scope of applications. Expert Systems with Applications, 59:20-32.
Lam, N. X., Tran, T., An, M. K., and Huynh, D. T. (2015). A note on the complexity of minimum latency data aggregation scheduling with uniform power in physical interference model. Theoretical Computer Science, 569:70-73.
Lv, S., Wang, X., and Zhou, X. (2010). Scheduling under sinr model in ad hoc networks with successive interference cancellation. In 2010 IEEE Global Telecommunications Conference GLOBECOM 2010, pages 1-5.
Maheshwari, R., Jain, S., and Das, S. R. (2008). A measurement study of interference modeling and scheduling in low-power wireless networks. In The 6th ACM Conference on Embedded Network Sensor Systems, SenSys'08, pages 141-154.
Moscibroda, T. and Wattenhofer, R. (2006). The complexity of connectivity in wireless networks. In INFOCOM: 25th Annual Joint Conference of the IEEE Computer and Communications Societies, Barcelona, Spain.
Nassu, B. T., Duarte Jr, E. P., and Ramirez Pozo, A. T. (2005). A comparison of evolutionary algorithms for system-level diagnosis. In Proceedings of the 7th annual conference on Genetic and evolutionary computation, pages 2053-2060.
Nelson, R. and Kleinrock, L. (1985). Spatial tdma: A collision-free multihop channel access protocol. IEEE Transactions on Communications, 33(9):934-944.
Saad, M. (2015). Wireless capacity maximization: A constrained genetic approach. In 2015 IEEE International Conference on Communications (ICC), pages 3855-3860.
Sgora, A., Vergados, D. J., and Vergados, D. D. (2015). A survey of tdma scheduling schemes in wireless multihop networks. ACM Comput. Surv., 47(3).
Son, D., Krishnamachari, B., and Heidemann, J. (2006). Experimental study of concurrent transmission in wireless sensor networks. In SenSys, pages 237-250. ACM.
White, C. M. (2015). Data Communications and Computer Networks: A Business User's Approach. Cengage, 8 edition.
Publicado
23/05/2022
Como Citar
CAMARGO, Fábio Engel de; FULBER-GARCIA, Vinicius; DUARTE JR., Elias P..
Uma Estratégia Bioinspirada para Escalonamento em Redes Sem Fio sob o Modelo SINR. In: WORKSHOP DE GERÊNCIA E OPERAÇÃO DE REDES E SERVIÇOS (WGRS), 27. , 2022, Fortaleza.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 1-14.
ISSN 2595-2722.
DOI: https://doi.org/10.5753/wgrs.2022.223393.
