🔢 mathematics

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

Cet article propose un cadre d'optimisation conjointe pour les réseaux IoT hiérarchiques edge-cloud qui traite simultanément le placement des services, la coopération edge-cloud, le délestage des tâches et l'allocation de la bande passante afin de minimiser la latence de bout en bout et les coûts du système, en utilisant des techniques de relaxation et d'approximation convexe successive pour résoudre le problème de programmation non linéaire mixte en nombres entiers non convexe qui en résulte.

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

Publié 2026-05-26

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

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

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez une ville animée où des millions de personnes (appareils IoT) doivent accomplir des tâches instantanément, comme commander de la nourriture, jouer à un jeu ou surveiller leur santé. Dans cette ville, il existe deux types de cuisines : des cafés de quartier locaux (serveurs de périphérie) et une immense cuisine industrielle centrale (le Cloud).

Le document que vous avez fourni traite de la manière de gérer ce « réseau de cuisines » de la ville afin que chacun reçoive sa commande rapidement, sans que le système ne s'effondre ni que la ville ne manque d'argent.

Voici la décomposition du problème et de la solution, en utilisant des analogies simples :

Le Problème : Une Cuisine Chaotique

Dans un réseau hiérarchique de périphérie et de cloud, les choses deviennent rapidement désordonnées :

Le Problème du Menu (Placement des services) : Les cafés de quartier ont un espace d'étagère limité. Ils ne peuvent pas stocker chaque ingrédient (service) possible pour chaque plat. Si un client souhaite un plat que le café ne possède pas, il doit attendre que la cuisine centrale l'envoie ou demander à un café voisin. Décider quels ingrédients garder sur les étagères est difficile.
Le Problème de la Livraison (Délégation des tâches) : Lorsqu'une commande arrive, qui la cuisine ? Le micro-ondes du client (appareil local) ? Le café local ? Le café d'un voisin ? Ou la grande cuisine centrale ? Si tout le monde envoie ses commandes à la cuisine centrale, les camions de livraison sont bloqués dans les embouteillages (latence). Si tout le monde se tourne vers un seul petit café, celui-ci s'épuise.
Le Problème des Coûts : Maintenir un café ouvert, stocker des ingrédients et payer les camions de livraison coûte de l'argent. Si vous changez le menu trop souvent (en installant et désinstallant constamment des services), vous gaspillez une fortune en frais de mise en place.

L'Objectif : Les auteurs souhaitent trouver l'équilibre parfait pour réaliser deux choses simultanément :

Vitesse : Livrer la « nourriture » au client aussi rapidement que possible.
Économies : Maintenir le coût total de fonctionnement du réseau bas.

La Solution : Un Plan de Gestion en Deux Étapes

Les auteurs ont réalisé que tenter de résoudre tout d'un coup revient à essayer de planifier un an de menus tout en cuisinant un seul repas. C'est trop compliqué. Ils ont donc décomposé le problème en deux échelles de temps différentes :

1. Le Plan à Long Terme (La « Stratégie du Menu »)

Cadre temporel : Cela se produit rarement (par exemple, une fois par jour ou par semaine).
L'Action : Le système décide quels services installer sur quels serveurs.
L'Analogie : Imaginez le gérant du café décidant quels ingrédients stocker sur les étagères pour la semaine à venir. Il observe les habitudes du quartier et décide : « Nous devons garder le four à pizza ici, mais nous n'avons pas besoin du poste à sushi. » Il décide également quels cafés doivent s'entraider (coopération périphérie-périphérie) et lesquels doivent compter sur la grande cuisine (coopération périphérie-cloud).
Pourquoi ? Cela assure la stabilité du réseau. Vous ne voulez pas changer l'intégralité du menu à chaque fois qu'un client entre.

2. Le Plan à Court Terme (Le « Preneur de Commandes »)

Cadre temporel : Cela se produit constamment (toutes les quelques secondes).
L'Action : Une fois le menu établi, le système décide comment traiter les commandes actuelles.
L'Analogie : Un client entre. Le gérant observe le trafic actuel, la vitesse des camions de livraison et l'énergie du personnel. Il décide : « D'accord, puisque le four à pizza est occupé, envoyons cette commande spécifique au café voisin », ou « Divisons cette commande : cuisinons la pâte ici, envoyons la sauce au cloud ». Il décide également quelle bande passante (espace dans le camion de livraison) attribuer à chaque client.
Pourquoi ? Cela s'adapte au chaos en temps réel, comme une soudaine affluence de clients ou un embouteillage sur la route.

Comment Ils Ont Résolu les Mathématiques

Les mathématiques derrière cela sont incroyablement difficiles (décrites comme de la « programmation non linéaire mixte en nombres entiers non convexe »). En langage courant, c'est un puzzle où vous devez choisir entre des options « Oui/Non » (installer ce service ou non ?) et des options « Combien » (quelle bande passante ?) simultanément, alors que les règles changent constamment.

Pour résoudre ce problème, les auteurs ont utilisé une astuce ingénieuse appelée Approximation Convexe Successive (SCA) :

L'Analogie : Imaginez essayer de descendre un sentier de montagne escarpé et déchiqueté dans l'obscurité. C'est dangereux et difficile de trouver le bas.
L'Astuce : Au lieu de voir tout le chemin déchiqueté, ils font semblant que le chemin est une pente douce et lisse pendant quelques pas. Ils descendent cette pente lisse, s'arrêtent, regardent à nouveau le vrai chemin, et font semblant qu'il s'agit d'une nouvelle pente lisse. Ils répètent ce processus, en faisant de petits pas sûrs jusqu'à atteindre le bas (la solution optimale).
La Pénalité : Ils ont également ajouté un système de « pénalité ». Si les mathématiques suggèrent un service « mi-installé » étrange (comme 0,5 d'un four à pizza), le système ajoute une lourde amende pour forcer la décision à être un « Oui » clair (1) ou un « Non » (0).

Les Résultats : Pourquoi Cela Fonctionne Mieux

Les auteurs ont testé leur méthode contre d'autres stratégies courantes (comme assigner aléatoirement les clients aux cafés ou toujours envoyer tout vers le cloud).

Vitesse : Leur méthode a considérablement réduit le temps nécessaire pour obtenir des résultats (latence). Elle était beaucoup plus rapide que d'envoyer simplement tout vers le cloud ou d'utiliser des affectations aléatoires.
Coût : Elle a permis d'économiser de l'argent en évitant les installations de services inutiles et en réduisant le besoin de transferts de données cloud coûteux.
Stabilité : En séparant les décisions à long terme du « menu » des décisions à court terme des « commandes », le système n'a pas été submergé par des changements constants.

Résumé

Ce document présente un système de gestion intelligent à deux couches pour les réseaux IoT. Il sépare les décisions stratégiques (quels services garder où) des décisions tactiques (comment acheminer les données maintenant). En utilisant des mathématiques avancées pour approximer le meilleur chemin à travers un labyrinthe complexe, les auteurs ont créé un système plus rapide, moins cher et plus fiable que les méthodes précédentes, garantissant que nos appareils connectés obtiennent les services à faible latence dont ils ont besoin sans ruiner le budget.

Résumé Technique : Placement conjoint des services et optimisation des ressources dans les réseaux hiérarchiques Edge-Cloud

Énoncé du problème
Les réseaux de l'Internet des objets (IoT) assistés par le calcul Edge-Cloud hiérarchique (HECC) font face à des défis majeurs pour équilibrer les exigences de faible latence avec les coûts du système. La difficulté centrale réside dans l'optimisation conjointe du placement des services (déterminer où déployer les services), de l'association des utilisateurs, de la coopération edge-edge et edge-cloud, des stratégies de délestage des tâches et de l'allocation de la bande passante. Ces décisions sont complexifiées par des ressources de calcul hétérogènes, un stockage limité sur les serveurs edge (ES), une mobilité dynamique des utilisateurs et des conditions de canal sans fil instables.

Le problème est formulé comme un problème de programmation non linéaire mixte en nombres entiers (MINLP) non convexe. L'objectif est de minimiser une somme pondérée de la latence globale de bout en bout (e2e) et du coût monétaire total du système (incluant les frais d'installation, de désinstallation, d'exploitation des services et les frais de requête cloud). Le problème est classé comme NP-difficile en raison du couplage fort entre les variables de décision binaires (placement des services, chemins de délestage) et les variables continues (allocation de bande passante, partitionnement des tâches), rendant difficile même la recherche d'une solution réalisable.

Méthodologie
Pour répondre à la complexité de la formulation MINLP, les auteurs proposent un cadre d'optimisation hiérarchique qui découple le problème en deux sous-problèmes opérant à différentes échelles de temps :

Optimisation à long terme (Placement des services et coopération) : Exécutée sur des intervalles de temps à long terme, ce sous-problème optimise les décisions binaires concernant le placement des services ( $g_s^k$ ), l'association des utilisateurs ( $\sigma_{m,s}^k$ ) et les chemins de coopération edge-edge/edge-cloud. Pour gérer les contraintes binaires, les auteurs emploient une méthode d'Approximation Convexe Successive (SCA) combinée à une fonction de pénalité. Les variables binaires sont relâchées en valeurs continues dans $[0, 1]$ , et un terme de pénalité est ajouté à la fonction objectif pour imposer une convergence vers des valeurs binaires (0 ou 1). La fonction de pénalité non convexe est approximée de manière itérative par un substitut convexe.
Optimisation à court terme (Délestage des tâches et allocation des ressources) : Exécutée sur des intervalles de temps à court terme au sein du cadre à long terme, ce sous-problème optimise les variables continues : la portion des tâches traitées localement versus délestées ( $\phi$ ) et l'allocation de la bande passante ( $b$ ). Les variables binaires déterminées lors de la phase à long terme sont traitées comme des paramètres fixes. Les contraintes non convexes liées à la latence, à l'énergie et aux débits de données sont convexifiées à l'aide de techniques SCA, spécifiquement en construisant des approximations concaves de borne inférieure pour les fonctions de débit et d'énergie.

L'algorithme global (Algorithme 1) itère entre ces deux échelles de temps. Si l'optimisation à court terme ne parvient pas à satisfaire les exigences de latence ou si de nouvelles demandes de services arrivent, le système déclenche une ré-optimisation de la configuration à long terme.

Contributions clés

Cadre d'optimisation unifié : L'article présente un cadre complet qui optimise conjointement le placement des services, l'association des utilisateurs, la coopération edge-edge/edge-cloud, le délestage des tâches et l'allocation de la bande passante. Contrairement aux travaux antérieurs qui supposent souvent des services préinstallés ou se concentrent sur une optimisation à une seule échelle de temps, cette approche intègre la stabilité à long terme avec l'adaptabilité à court terme.
Nouvelle transformation du problème : Les auteurs introduisent trois lemmes pour simplifier le couplage complexe entre la disponibilité des services, la connectivité et les conditions de transfert des tâches. Ces lemmes permettent de reformuler le MINLP non convexe original en une forme plus traitable.
Algorithmes itératifs efficaces : En combinant la SCA et des techniques basées sur la pénalité, l'article développe des algorithmes (Algorithme 2 pour le long terme et Algorithme 3 pour le court terme) qui garantissent une convergence vers au moins un optimum local. La complexité est analysée, montrant une complexité temporelle polynomiale par itération.
Modélisation consciente des coûts : La fonction objectif intègre explicitement les coûts monétaires pour le déploiement des services (installation/désinstallation) et les frais d'exploitation, parallèlement à la minimisation de la latence, fournissant une métrique de coût système plus réaliste.

Résultats numériques
Des simulations extensives ont été menées pour évaluer le cadre proposé contre plusieurs schémas de référence, incluant Branch-and-Bound (BnB), l'association d'utilisateurs fixe/aléatoire, des schémas sans coopération edge-edge ou edge-cloud, et des taux de délestage fixes.

Convergence : Les algorithmes proposés démontrent une convergence rapide. L'Algorithme 2 (long terme) converge généralement en 4 à 5 itérations, tandis que l'Algorithme 3 (court terme) montre une convergence stable même lorsque la taille du réseau augmente.
Performance par rapport aux références : L'approche proposée atteint une performance dans une fourchette de 1 à 2 % de la solution optimale BnB, mais avec une complexité de calcul significativement plus faible.
Impact de la coopération : Les résultats indiquent que la désactivation de la coopération edge-edge ou edge-cloud entraîne des augmentations de coûts du système de 200 à 250 % et une latence e2e nettement plus élevée.
Avantages de l'optimisation conjointe : Les schémas qui fixent les taux de délestage ou allouent une bande passante égale se comportent de manière sous-optimale. L'optimisation conjointe proposée du délestage et de l'allocation de la bande passante produit systématiquement la latence e2e la plus faible.
Sensibilité aux ressources : L'augmentation du taux de traitement des serveurs edge réduit la latence et les coûts du système en permettant un traitement local plus important, bien que le cadre proposé maintienne des coûts stables même sous des charges d'utilisateurs variables par rapport aux schémas d'association fixes.

Signification et affirmations
L'article affirme que sa signification principale réside dans la démonstration de la nécessité d'un placement conjoint des services et d'une allocation des ressources pour améliorer les performances et l'efficacité du système dans les réseaux IoT assistés par HECC. Il soutient que l'optimisation séparée de ces composants ou l'ignorance de l'interaction entre la configuration des services à long terme et la dynamique des ressources à court terme conduit à une qualité de service (QoS) sous-optimale et à des coûts gonflés.

Les auteurs soulignent que leur approche hiérarchique équilibre efficacement la stabilité du système avec l'adaptabilité aux demandes en temps réel, répondant aux limitations des approches existantes à deux échelles de temps qui supposent souvent des mises à jour de placement de services peu fréquentes. Les résultats suggèrent que le cadre proposé est une solution évolutive et rentable pour des environnements IoT dynamiques et contraints en ressources, offrant une alternative robuste aux solveurs optimaux complexes comme BnB tout en surpassant les schémas de référence heuristiques ou statiques.