🔢 mathematics

Joint Service Placement and Resource Optimization in Hierarchical Edge-Cloud Networks

Este artigo propõe uma estrutura de otimização conjunta para redes hierárquicas de IoT em borda-nuvem que aborda simultaneamente o posicionamento de serviços, a cooperação borda-nuvem, o descarregamento de tarefas e a alocação de largura de banda para minimizar a latência ponta a ponta e os custos do sistema, utilizando técnicas de relaxação e aproximação convexa sucessiva para resolver o problema resultante de programação não linear inteira mista não convexa.

Autores originais: Vo Phi Son, Van-Dinh Nguyen, Minh-Tuong Nguyen, Tuan-Vu Truong, Toan D. Gian, Dinh Thai Hoang, Diep N. Nguyen, Symeon Chatzinotas

Publicado 2026-05-26

📖 6 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Vo Phi Son, Van-Dinh Nguyen, Minh-Tuong Nguyen, Tuan-Vu Truong, Toan D. Gian, Dinh Thai Hoang, Diep N. Nguyen, Symeon Chatzinotas

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine uma cidade movimentada onde milhões de pessoas (dispositivos IoT) precisam realizar tarefas instantaneamente — como pedir comida, jogar um jogo ou monitorar sua saúde. Nessa cidade, existem dois tipos de cozinhas: cafés de bairro locais (Servidores de Borda) e uma massiva cozinha industrial central (a Nuvem).

O artigo que você forneceu trata de como operar a "rede de cozinhas" dessa cidade para que todos recebam seus pedidos rapidamente, sem que o sistema colapse ou que a cidade fique sem dinheiro.

Aqui está a decomposição do problema e da solução, usando analogias simples:

O Problema: Uma Cozinha Caótica

Em uma rede hierárquica de Borda-Nuvem, as coisas ficam muito bagunçadas rapidamente:

O Problema do Cardápio (Posicionamento de Serviços): Os cafés de bairro têm espaço limitado nas prateleiras. Eles não podem estocar todos os ingredientes (serviços) para todos os pratos possíveis. Se um cliente quiser um prato que o café não tem, ele terá que esperar a cozinha central enviá-lo ou pedir a um café vizinho. Decidir quais ingredientes manter nas prateleiras é difícil.
O Problema da Entrega (Descarga de Tarefas): Quando um pedido chega, quem o cozinha? O micro-ondas do próprio cliente (dispositivo local)? O café local? O café de um vizinho? Ou a grande cozinha central? Se todos enviarem seus pedidos para a cozinha central, os caminhões de entrega ficam presos no trânsito (latência). Se todos forem para um único café pequeno, esse café se esgota.
O Problema de Custos: Manter um café aberto, estocar ingredientes e pagar pelos caminhões de entrega custa dinheiro. Se você mudar o cardápio com muita frequência (instalando e desinstalando serviços constantemente), desperdiça uma fortuna em taxas de configuração.

O Objetivo: Os autores querem encontrar o equilíbrio perfeito para fazer duas coisas acontecerem simultaneamente:

Velocidade: Levar a "comida" ao cliente o mais rápido possível.
Economia: Manter o custo total de operação da rede baixo.

A Solução: Um Plano de Gestão em Duas Etapas

Os autores perceberam que tentar resolver tudo de uma vez é como tentar planejar um ano inteiro de cardápios enquanto simultaneamente se prepara uma única refeição. É complicado demais. Então, eles dividiram isso em duas escalas de tempo diferentes:

1. O Plano de Longo Prazo (A "Estratégia do Cardápio")

Prazo: Isso ocorre raramente (por exemplo, uma vez por dia ou semana).
A Ação: O sistema decide quais serviços instalar em quais servidores.
A Analogia: Pense nisso como o gerente do café decidindo quais ingredientes estocar nas prateleiras para a próxima semana. Eles observam os hábitos do bairro e decidem: "Precisamos manter o forno de pizza aqui, mas não precisamos da estação de sushi". Eles também decidem quais cafés devem ajudar uns aos outros (cooperação Borda-Borda) e quais devem depender da grande cozinha (cooperação Borda-Nuvem).
Por quê? Isso garante que a rede seja estável. Você não quer mudar todo o cardápio toda vez que um cliente entra.

2. O Plano de Curto Prazo (O "Recebedor de Pedidos")

Prazo: Isso ocorre constantemente (a cada poucos segundos).
A Ação: Uma vez que o cardápio está definido, o sistema decide como lidar com os pedidos atuais.
A Analogia: Um cliente entra. O gerente olha para o tráfego atual, a velocidade dos caminhões de entrega e a energia da equipe. Eles decidem: "Ok, como o forno de pizza está ocupado, vamos enviar este pedido específico para o café vizinho", ou "Vamos dividir este pedido: cozinhar a massa aqui, enviar o molho para a nuvem". Eles também decidem quanto largura de banda (espaço no caminhão de entrega) dar a cada cliente.
Por quê? Isso se adapta ao caos em tempo real, como uma repentina enxurrada de clientes ou um engarrafamento na estrada.

Como Eles Resolveram a Matemática

A matemática por trás disso é incrivelmente difícil (descrita como "programação não linear inteira mista não convexa"). Em português claro, é um quebra-cabeça onde você precisa escolher entre opções "Sim/Não" (instalar este serviço ou não?) e opções "Quanto" (quanto de largura de banda?) tudo ao mesmo tempo, e as regras continuam mudando.

Para resolver isso, os autores usaram um truque inteligente chamado Aproximação Convexa Sucessiva (SCA):

A Analogia: Imagine tentar caminhar por um caminho de montanha íngreme e irregular no escuro. É perigoso e difícil encontrar o fundo.
O Truque: Em vez de ver todo o caminho irregular, eles fingem que o caminho é uma encosta suave e gentil por alguns passos. Eles descem essa encosta suave, param, olham para o caminho real novamente e fingem que é uma nova encosta suave. Eles repetem esse processo, dando pequenos e seguros passos até chegar ao fundo (a solução ótima).
A Penalidade: Eles também adicionaram um sistema de "penalidade". Se a matemática sugerir um serviço meio instalado estranho (como 0,5 de um forno de pizza), o sistema adiciona uma multa pesada para forçar a decisão a ser um claro "Sim" (1) ou "Não" (0).

Os Resultados: Por Que Funciona Melhor

Os autores testaram seu método contra outras estratégias comuns (como atribuir clientes aleatoriamente aos cafés ou sempre enviar tudo para a nuvem).

Velocidade: Seu método reduziu significativamente o tempo que levou para obter resultados (latência). Foi muito mais rápido do que apenas enviar tudo para a nuvem ou usar atribuições aleatórias.
Custo: Economizou dinheiro evitando instalações de serviços desnecessárias e reduzindo a necessidade de transferências caras de dados na nuvem.
Estabilidade: Ao separar as decisões de longo prazo do "cardápio" das decisões de curto prazo dos "pedidos", o sistema não ficou sobrecarregado com mudanças constantes.

Resumo

Este artigo apresenta um sistema de gestão inteligente em duas camadas para redes IoT. Ele separa as decisões estratégicas (quais serviços manter onde) das decisões táticas (como rotear dados agora). Ao usar matemática avançada para aproximar o melhor caminho através de um labirinto complexo, os autores criaram um sistema que é mais rápido, mais barato e mais confiável do que métodos anteriores, garantindo que nossos dispositivos conectados recebam os serviços de baixa latência de que precisam sem quebrar o banco.

Resumo Técnico: Posicionamento Conjunto de Serviços e Otimização de Recursos em Redes Hierárquicas de Borda-Nuvem

Declaração do Problema
As redes de Internet das Coisas (IoT) auxiliadas por Computação em Borda-Nuvem Hierárquica (HECC) enfrentam desafios significativos no equilíbrio entre requisitos de baixa latência e custos do sistema. A dificuldade central reside na otimização conjunta do posicionamento de serviços (determinação de onde implantar serviços), associação de usuários, cooperação borda-borda e borda-nuvem, estratégias de descarga de tarefas e alocação de largura de banda. Essas decisões são complicadas por recursos computacionais heterogêneos, armazenamento limitado nos servidores de borda (ESs), mobilidade dinâmica dos usuários e condições instáveis de canais sem fio.

O problema é formulado como um problema de Programação Não Linear Mista Inteira (MINLP) não convexo. O objetivo é minimizar uma soma ponderada da latência total de ponta a ponta (e2e) e do custo monetário total do sistema (incluindo taxas de instalação, desinstalação, operação de serviços e solicitações à nuvem). O problema é classificado como NP-difícil devido ao forte acoplamento entre variáveis de decisão binárias (posicionamento de serviços, caminhos de descarga) e variáveis contínuas (alocação de largura de banda, partição de tarefas), tornando difícil até mesmo encontrar uma solução viável.

Metodologia
Para abordar a complexidade da formulação MINLP, os autores propõem um framework de otimização hierárquica que desacopla o problema em dois subproblemas operando em diferentes escalas de tempo:

Otimização de Longo Prazo (Posicionamento de Serviços e Cooperação): Executada em intervalos de tempo de longo prazo, este subproblema otimiza decisões binárias relativas ao posicionamento de serviços ( $g_s^k$ ), associação de usuários ( $\sigma_{m,s}^k$ ) e caminhos de cooperação borda-borda/borda-nuvem. Para lidar com as restrições binárias, os autores empregam um método de Aproximação Convexa Sucessiva (SCA) combinado com uma função de penalidade. As variáveis binárias são relaxadas para valores contínuos em $[0, 1]$ , e um termo de penalidade é adicionado à função objetivo para impor a convergência para valores binários (0 ou 1). A função de penalidade não convexa é aproximada iterativamente por um substituto convexo.
Otimização de Curto Prazo (Descarga de Tarefas e Alocação de Recursos): Executada em intervalos de tempo de curto prazo dentro do quadro de longo prazo, este subproblema otimiza variáveis contínuas: a porção de tarefas processadas localmente versus descarregadas ( $\phi$ ) e a alocação de largura de banda ( $b$ ). As variáveis binárias determinadas na fase de longo prazo são tratadas como parâmetros fixos. As restrições não convexas relacionadas à latência, energia e taxas de dados são convexificadas usando técnicas SCA, especificamente construindo aproximações côncavas de limite inferior para as funções de taxa e energia.

O algoritmo geral (Algoritmo 1) itera entre essas duas escalas de tempo. Se a otimização de curto prazo não atender aos requisitos de latência ou se chegarem novas solicitações de serviço, o sistema dispara uma reotimização da configuração de longo prazo.

Principais Contribuições

Framework de Otimização Unificado: O artigo apresenta um framework abrangente que otimiza conjuntamente o posicionamento de serviços, associação de usuários, cooperação borda-borda/borda-nuvem, descarga de tarefas e alocação de largura de banda. Diferentemente de trabalhos anteriores que frequentemente assumem serviços pré-instalados ou focam em otimização de escala de tempo única, esta abordagem integra estabilidade de longo prazo com adaptabilidade de curto prazo.
Transformação de Problema Novel: Os autores introduzem três lemas para simplificar o acoplamento complexo entre disponibilidade de serviços, conectividade e condições de transferência de tarefas. Esses lemas permitem a reformulação do MINLP não convexo original em uma forma mais tratável.
Algoritmos Iterativos Eficientes: Ao combinar SCA e técnicas baseadas em penalidade, o artigo desenvolve algoritmos (Algoritmo 2 para longo prazo e Algoritmo 3 para curto prazo) que garantem convergência para pelo menos um ótimo local. A complexidade é analisada, mostrando complexidade de tempo polinomial por iteração.
Modelagem Consciente de Custos: A função objetivo incorpora explicitamente custos monetários para implantação de serviços (instalação/desinstalação) e despesas operacionais, juntamente com a minimização de latência, fornecendo uma métrica de custo do sistema mais realista.

Resultados Numéricos
Simulações extensas foram conduzidas para avaliar o framework proposto contra vários esquemas de referência, incluindo Branch-and-Bound (BnB), Associação de Usuários Fixa/Aleatória, esquemas sem cooperação borda-borda ou borda-nuvem e taxas de descarga fixas.

Convergência: Os algoritmos propostos demonstram convergência rápida. O Algoritmo 2 (longo prazo) tipicamente converge dentro de 4-5 iterações, enquanto o Algoritmo 3 (curto prazo) mostra convergência estável mesmo com o aumento do tamanho da rede.
Desempenho vs. Referências: A abordagem proposta alcança desempenho dentro de 1-2% da solução ótima BnB, mas com complexidade computacional significativamente menor.
Impacto da Cooperação: Os resultados indicam que desabilitar a cooperação borda-borda ou borda-nuvem leva a aumentos de custo do sistema de 200-250% e latência e2e significativamente maior.
Benefícios da Otimização Conjunta: Esquemas que fixam taxas de descarga ou alocam largura de banda igual performam de forma subótima. A otimização conjunta proposta de descarga e alocação de largura de banda consistentemente produz a menor latência e2e.
Sensibilidade a Recursos: O aumento da taxa de processamento dos servidores de borda reduz a latência e os custos do sistema, permitindo mais processamento local, embora o framework proposto mantenha custos estáveis mesmo sob cargas de usuários variáveis em comparação com esquemas de associação fixa.

Significância e Alegações
O artigo afirma que sua principal significância reside em demonstrar a necessidade de posicionamento conjunto de serviços e alocação de recursos para aprimorar o desempenho e a eficiência do sistema em redes IoT auxiliadas por HECC. Argumenta que otimizar esses componentes separadamente ou ignorar a interação entre a configuração de serviços de longo prazo e a dinâmica de recursos de curto prazo leva a QoS subótima e custos inflados.

Os autores enfatizam que sua abordagem hierárquica equilibra efetivamente a estabilidade do sistema com a adaptabilidade a demandas em tempo real, abordando as limitações das abordagens existentes de duas escalas de tempo que frequentemente assumem atualizações infrequentes de posicionamento de serviços. Os resultados sugerem que o framework proposto é uma solução escalável e econômica para ambientes IoT dinâmicos e com recursos restritos, oferecendo uma alternativa robusta a solvers ótimos complexos como o BnB, enquanto supera esquemas de referência heurísticos ou estáticos.