Posicionamento de infraestruturas de comunicação em redes veiculares: algoritmos para a maximização da área da rede Delta

Página do item simplificado
dc.contributor.advisorSarubbi, João Fernando Machry
dc.contributor.advisorLatteshttp://lattes.cnpq.br/2555714512247868
dc.contributor.authorSilveira, Vinícius Henrique
dc.contributor.authorLatteshttp://lattes.cnpq.br/4041302252444881
dc.contributor.refereeSarubbi, João Fernando Machry
dc.contributor.refereeMartins, Flávio Vinicius Cruzeiro
dc.contributor.refereeMenezes, Gustavo Campos
dc.date.accessioned2026-08-12T23:35:50Z
dc.date.available2026-08-12T23:35:50Z
dc.date.issued2026-06-09
dc.description.abstractO problema de posicionamento de infraestruturas em redes veiculares ad hoc (VANETs) consiste em determinar a localização de Roadside Units (RSUs) para maximizar a conectividade sob restrições de implantação. Abordagens tradicionais avaliam a conectividade de forma binária, desconsiderando a duração da conexão ao longo da viagem. A métrica Delta permite uma avaliação mais abrangente ao relacionar a fração do tempo de conexão dos veículos (ρ1) com a fração de veículos atendidos (ρ2). Neste trabalho, o problema é abordado pela maximização da área sob essa curva, considerando um número fixo de RSUs. Para sua resolução, são desenvolvidos um algoritmo guloso e um algoritmo baseado na metaheurística GRASP, cujos resultados são comparados com os obtidos pelo modelo exato resolvido via CPLEX. Os resultados mostram que ambos os algoritmos alcançam soluções ótimas em instâncias pequenas. Para uma instância realística de mobilidade veicular urbana, ambos os algoritmos produzem soluções equivalentes em todos os cenários avaliados. Experimentos sobre uma instância sintética com distribuição de tráfego mais uniforme revelam que o algoritmo baseado na metaheurística GRASP supera o algoritmo guloso na maioria dos cenários, com ganhos de até 5,10%, sugerindo que a diversificação proporcionada pelo GRASP é mais eficaz em cenários com múltiplas regiões promissoras.
dc.description.abstractotherThe placement of communication infrastructure in Vehicular Ad Hoc Networks (VANETs) consists of determining the location of Roadside Units (RSUs) to maximize connectivity under deployment constraints. Traditional approaches evaluate connectivity in a binary manner, disregarding its duration throughout the trip. The Delta metric provides a more comprehensive evaluation by relating the fraction of travel time during which vehicles remain connected (ρ1) to the fraction of vehicles that achieve this connectivity level (ρ2). In this work, the problem is addressed by maximizing the area under this curve, considering a fixed number of RSUs. A greedy algorithm and a GRASP-based metaheuristic algorithm are developed, and their results are compared against those obtained by the exact model solved using CPLEX. Results show that both algorithms achieve optimal solutions in small instances. For a realistic urban vehicular mobility instance, both algorithms produce equivalent solutions across all evaluated scenarios. Experiments on a synthetic instance with more uniform traffic distribution reveal that the GRASP-based metaheuristic algorithm outperforms the greedy algorithm in most scenarios, with gains of up to 5.10%, suggesting that the diversification provided by GRASP is more effective in scenarios with multiple promising regions.
dc.identifier.urihttps://repositorio.cefetmg.br//handle/123456789/2899
dc.language.isopt
dc.publisherCentro Federal de Educação Tecnológica de Minas Gerais
dc.publisher.countryBrasil
dc.publisher.departmentDepartamento de Computação
dc.publisher.initialsCEFET-MG
dc.subjectProgramação heurística
dc.subjectAlgoritmos genéticos
dc.subjectModelos matemáticos
dc.titlePosicionamento de infraestruturas de comunicação em redes veiculares: algoritmos para a maximização da área da rede Delta
dc.typeTrabalho de Conclusão de Curso da Graduação

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Imagem de Miniatura
Nome:
Posicionamento de infraestruturas de comunicação em redes veiculares.pdf
Tamanho:
3.2 MB
Formato:
Adobe Portable Document Format
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.39 KB
Formato:
Item-specific license agreed to upon submission
Descrição:
Baixar

Coleções

Engenharia de Computação (Belo Horizonte - Nova Gameleira)