Parallel Algorithms for Multinode Allocation in IoT Networks

• Paulo Zimpel UFMS
• Luiz Xavier UFMS
• Murilo Táparo UFMS / UFGD
• Samuel Ferraz UFMS
• Bianca Dantas UFMS
• Ricardo Santos UFMS

DOI: https://doi.org/10.5753/sscad.2026.35004

Resumo

O Problema de Alocação de Multiplos Nós em redes da Internet das Coisas é um problema de otimização que consiste em atribuir tarefas a subconjuntos de nós da rede, respeitando suas restrições. À medida que a escala da rede e as demandas de alocação aumentam, a exploração das soluções torna-se inviável, motivando o uso de abordagens heurísticas e paralelas. A heurística Demand-Index Multinode Allocation (DI-MNA) foi originalmente proposta para reduzir o custo computacional do processo de alocação obtendo soluções competitivas sob múltiplas restrições. Este artigo apresenta abordagens paralelas da heurística DI-MNA direcionadas a arquiteturas de CPU e GPU. Os resultados experimentais demonstram a eficácia das estratégias de paralelização propostas na redução do custo temporal da DI-MNA, preservando a qualidade das alocações resultantes.

Referências

Chapman, B., Jost, G., and Van Der Pas, R. (2007). Using OpenMP: portable shared memory parallel programming. MIT press.

Cook, S. (2012). Cuda Programming. Elsevier.

Dagum, L. and Menon, R. (1998). OpenMP: an industry standard api for shared-memory programming. IEEE Computational Science and Engineering, 5(1):46–55.

Garland, M., Le Grand, S., Nickolls, J., Anderson, J., Hardwick, J., Morton, S., Phillips, E., Zhang, Y., and Volkov, V. (2008). Parallel computing experiences with CUDA. IEEE micro, 28(4):13–27.

Genitrini, A. and Pépin, M. (2021). Lexicographic unranking of combinations revisited. Algorithms, 14(3).

Muhamad, W. N. W., Dimyati, K., Javed, M. A., Sarnin, S. S., and Ametefe, D. S. (2023). Survey of resources allocation techniques with a quality of service (QoS) aware in a fog computing environment. Computers, Materials and Continua, 76(1):1291–1308.

Ruskey, F. (2003). Combinatorial Generation. University of Victoria.

Savaglio, C., Ganzha, M., Paprzycki, M., Bădică, C., Ivanović, M., and Fortino, G. (2020). Agent-based internet of things: State-of-the-art and research challenges. Future Generation Computer Systems, 102:1038–1053.

Táparo, M., Dantas, B., and Santos, R. (2024). Multi-node allocation heuristics for iot applications. In 2024 XIV Brazilian Symposium on Computing Systems Engineering (SBESC), pages 1–6. IEEE.

Zahoor, S. and Mir, R. N. (2021). Resource management in pervasive internet of things: A survey. Journal of King Saud University - Computer and Information Sciences, 33(8):921–935.