Auctions and resource allocation in edge computing with mobility

Autor(es)

João Paulo Francisco da Silva

• Tipo de documento: Dissertação de Mestrado
• Imprenta: Campinas, SP.
• Instituição: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Data de defesa: 2023-09-11

Membros da banca

Rafael Crivellari Saliba Schouery; Daniel de Angelis Cordeiro

• Orientador: Rafael Crivellari Saliba Schouery; Luiz Fernando Bittencourt

Resumo

A Computação em Borda é um paradigma computacional cujo objetivo é trazer recursos computacionais para mais próximo dos usuários, potencialmente reduzindo a latência das aplicações. Nesse contexto, a alocação de recursos é um desafio, uma vez que os recursos estão distribuídos na borda da rede e a demanda por recursos é dinâmica, principalmente devido à mobilidade dos usuários que requisitam estes recursos. Neste trabalho, propomos dois mecanismos de leilão sequenciais e à prova de estratégia para alocação de recursos na borda da rede considerando a mobilidade dos usuários. O primeiro mecanismo é um algoritmo guloso para Problema das Mochilas Múltiplas Multidimensionais. Já o segundo, denominado como \textit{2-Fases}, é um mecanismo dividido em duas partes em que, na primeira, temos um algoritmo guloso para o Problema da Mochila Multidimensional, e na segunda usamos um algoritmo de fluxo em redes. Também modelamos um mecanismo de leilão baseado em Vickrey-Clarke-Groves (VCG) para o problema de alocação em Computação em Borda, onde a função objetivo é maximizar o bem-estar social. Escolhemos um mecanismo de leilão da literatura para comparar com os que modelamos neste trabalho e, em seguida, os avaliamos por meio de simulações e um conjunto de dados de linhas de ônibus de São Paulo - Brasil, visando simular a mobilidade dos usuários solicitando recursos na borda da rede. Os resultados mostram que os mecanismos atingem valores próximos do ótimo, e também conseguem alocar recursos aos usuários de forma que eles tenham uma baixa latência, mesmo em cenários de mobilidade (AU)

• Processo FAPESP: 21/06282-4 - Teoria dos Jogos Algorítmica aplicada a alocação e precificação de recursos na Computação de Borda
• Beneficiário: João Paulo Francisco da Silva
• Modalidade de apoio: Bolsas no Brasil - Mestrado