MICE: Algoritmo de escalonamento para redes sem fio baseado no modelo antiferromagnético de Ising

• Nilton Guedes Duarte UFRJ
• José Ferreira de Rezende UFRJ

DOI: https://doi.org/10.5753/sbrc.2018.2443

Resumo

Algoritmos de acesso ao meio compartilhado para redes sem fio que levam em conta o tamanho da fila dos enlaces ganharam destaque recentemente. Neste artigo, propomos um algoritmo distribuído de escalonamento de enlaces baseado no modelo físico de Ising para o antiferromagnetismo. Esse modelo foi adaptado, por outro trabalho, para considerar o tamanho das filas e utilizar a dinâmica de Glauber para minimizar a energia capturada pelo modelo. Neste trabalho, propomos a inclusão do campo externo do modelo de Ising para evitar que o algoritmo fique preso em pontos de mínimos locais da função de energia. Além disso, é proposto um algoritmo adicional para transformar o resultado obtido pelo modelo em um escalonamento viável. Os resultados demonstram um bom desempenho no controle do tamanho das filas em comparação aos algoritmos existentes.

Referências

Bissacot, R. and Cioletti, L. (2010). Phase transition in ferromagnetic ising models with non-uniform external magnetic elds. Journal of Statistical Physics, 139(5):769–778.

Jiang, L., Leconte, M., Ni, J., Srikant, R., and Walrand, J. (2012). Fast mixing of parallel glauber dynamics and low-delay csma scheduling. IEEE Transactions on Information Theory, 58(10):6541–6555.

Kwak, J., Lee, C. H., and Eun, D. Y. (2016). A high-order markov-chain-based scheduling algorithm for low delay in csma networks. IEEE/ACM Transactions on Networking, 24(4):2278–2290.

Ni, J., Tan, B., and Srikant, R. (2010). Q-csma: Queue-length based csma/ca algorithms for achieving maximum throughput and low delay in wireless networks. In 2010 Proceedings IEEE INFOCOM, pages 1–5.

Rhee, I., Warrier, A., Min, J., and Xu, L. (2009). Drand: Distributed randomized tdma scheduling for wireless ad hoc networks. IEEE Transactions on Mobile Computing, 8(10):1384–1396.

Tassiulas, L. and Ephremides, A. (1992). Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Transactions on Automatic Control, 37(12):1936–1948.

Wang, Y. and Xia, Y. (2017a). I-csma: A link scheduling algorithm for wireless networks based on ising model. IEEE Transactions on Control of Network Systems, PP(99):1–1.

Wang, Y. and Xia, Y. (2017b). Improving the queue size and delay performance with the i-csma link scheduling algorithm. Computer Networks, 122(Supplement C):105 – 119.

Xue, D., Ekici, E., Ibrahim, R., and Youssef, M. (2017). A novel queue-length-based csma algorithm with improved delay characteristics. Computer Networks, 122(Supplement C):56 – 69.