Multi-objective Cluster Head Selection in Underwater Wireless Sensor Networks: An Influence Maximization Perspective with Adaptive Evolutionary Optimization

Résumé technique : Sélection de chefs de grappes multi-objectifs dans les réseaux de capteurs sans fil sous-marins

Formulation du problème
Cet article traite du problème de la sélection de chefs de grappes multi-objectifs (MOCHS - Multi-objective Cluster Head Selection) dans les réseaux de capteurs sans fil sous-marins (UWSN). Les méthodes de regroupement existantes reposent souvent sur des indicateurs locaux ou des scores de scalarisation qui ne parviennent pas à capturer l'effet de service collectif d'un ensemble de chefs de grappes (CH - Cluster Heads) sélectionnés, ni le compromis inhérent entre la capacité de service et la charge des CH. Les auteurs formulent le MOCHS comme un problème d'optimisation bi-objectif par cycle. Les deux objectifs conflictuels sont :

1. Capacité de service pondérée attendue : Maximiser la probabilité que les nœuds capteurs vivants puissent acheminer les données vers le puits (sink) via des chemins acoustiques multi-sauts réalisables via les CH sélectionnés.
2. Charge opérationnelle : Minimiser le coût total (énergie et charge opérationnelle) associé à la sélection et à l'exploitation des CH choisis.

Le problème est contraint par la topologie du réseau, la fiabilité des liaisons acoustiques, l'énergie résiduelle et l'éligibilité des CH. Crucialement, les auteurs considèrent la sélection des CH non pas comme une décision locale ponctuelle, mais comme un processus répété où les décisions actuelles influencent l'énergie résiduelle et la faisabilité future.

Méthodologie
L'approche proposée, LA-MOCHS (Lifetime-Aware Multi-Objective Cluster-Head Selection), intègre la théorie des graphes, l'optimisation sous-modulaire et les algorithmes évolutionnaires.

1. Reformulation par influence basée sur les graphes :
   Les auteurs reformulent l'objectif de service en une fonction de couverture pondérée de type « influence » sur un graphe de communication probabiliste. Dans ce modèle, un ensemble de CH sélectionnés agit comme un ensemble de semences (seed set), et un nœud est considéré comme « servi » s'il peut atteindre un CH via un chemin acoustique actif, et que ce CH peut transmettre avec succès vers le puits.

   • Fondement théorique : L'article prouve que, sous cette reformulation, l'objectif de service attendu est normalisé, monotone et sous-modulaire sur l'ensemble des candidats CH éligibles. Cette propriété structurelle relie la sélection de CH dans les UWSN à l'optimisation de l'influence et aux problèmes de sélection de sous-ensembles.

2. Algorithme LA-MOCHS :
   LA-MOCHS est un cadre évolutionnaire de Pareto à horizon fuyant conçu pour résoudre le problème MOCHS par cycle tout en préservant la durée de vie du réseau. Il opère selon deux couches couplées :

   • Boucle externe (Déploiement à horizon fuyant) : À chaque cycle, l'état actuel du réseau est observé, une archive de Pareto des configurations de CH réalisables est générée, puis une configuration est déployée. L'état du réseau (énergie, topologie) est ensuite mis à jour avant le cycle suivant.
   • Boucle interne (Solveur par cycle) : Un solveur de sélection de sous-ensembles basé sur Pareto recherche des configurations de CH non dominées et diverses. Les composants clés incluent :
     • Sélection d'ancres adaptative : Ajuste dynamiquement le nombre de sous-ensembles de référence en fonction de la taille de l'ensemble éligible et du budget d'évaluation.
     • Allocation d'évaluation en deux étapes : Alloue le budget de calcul d'abord pour sonder les ancres, puis pour se concentrer sur les régions prometteuses.
     • Initialisation par stratégie gloutonne (Greedy Warm-Starting) : Initialise la recherche avec des solutions déterministes réalisables (ex: meilleur singleton, maximisation gloutonne du service) pour fournir des points de référence.
     • Mutation sensible à la faisabilité : Garantit que les solutions offspring respectent les contraintes de cardinalité des CH et de faisabilité du regroupement (accessibilité membre-vers-CH).

Contributions clés
L'article présente cinq contributions principales :

1. Formulation du problème : Définit le MOCHS comme un problème d'optimisation bi-objectif qui capture explicitement le compromis entre la capacité de service attendue et la charge des CH, évitant ainsi la scalarisation.
2. Reformulation par la théorie des graphes : Interprète l'effet de service d'un ensemble de CH comme une fonction de couverture de service probabiliste de bout en bout induite par la communication acoustique sous-marine multi-sauts.
3. Preuve théorique : Prouve que l'objectif de service attendu est une fonction d'ensemble normalisée, monotone et sous-modulaire, fournissant une base théorique pour l'utilisation de l'optimisation de sous-ensembles de type influence.
4. Développement de l'algorithme : Propose LA-MOCHS, un solveur sensible à la durée de vie qui combine l'ancrage adaptatif, l'allocation de budget en deux étapes, l'initialisation gloutonne et la mutation sensible à la faisabilité.
5. Validation empirique : Réalise des simulations de durée de vie en boucle fermée et des tests de référence sur un seul cycle pour démontrer que la méthode améliore la durée de vie du réseau en préservant des configurations réalisables au fil des cycles.

Résultats expérimentaux
Les auteurs ont évalué LA-MOCHS par rapport à dix bases de comparaison (incluant EPOL, POMC, NSGA-II, SPEA2 et MOEA/D) à travers diverses tailles de réseaux (50 à 500 nœuds) et règles de déploiement.

• Durée de vie en boucle fermée : LA-MOCHS a démontré la préservation la plus constante de la demi-durée de vie parmi les solveurs opérationnellement complets. Il a obtenu le meilleur cycle de non-décès de moitié des nœuds (HND - half-node-death) dans sept des huit configurations testées.
• Faisabilité vs Qualité par cycle : Une conclusion critique est que l'avantage de LA-MOCHS ne provient pas d'une qualité de front de Pareto uniformément supérieure par cycle (mesurée par l'hypervolume ou l'IGD). En fait, certaines bases de comparaison produisent des archives plus denses ou de meilleure qualité lors de cycles isolés. Cependant, ces bases se terminent souvent prématurément en raison de conditions de « non-faisabilité » (épuisement des CH viables).
• Mécanisme : L'amélioration de la durée de vie provient d'un comportement de déploiement sensible à la charge. LA-MOCHS évite les sélections de CH trop agressives qui épuisent l'énergie ou la faisabilité dans les cycles initiaux, maintenant ainsi un état de réseau viable pour les cycles suivants.

Signification et affirmations
L'article affirme que la principale signification de LA-MOCHS réside dans sa capacité à combler le fossé entre les contraintes physiques des UWSN et l'optimisation structurelle des graphes. En exploitant la nature sous-modulaire de l'objectif de service et en employant une stratégie à horizon fuyant, la méthode privilégie la faisabilité à long terme plutôt qu'une maximisation immédiate et agressive du service.

Les auteurs déclarent modestement que LA-MOCHS n'est pas un optimiseur de durée de vie globale hors ligne qui maximise directement des métriques comme le HND ou le LND comme un objectif unique. C'est plutôt un solveur à horizon fuyant qui résout de manière répétée le compromis service-charge par cycle. Son succès est attribué à l'interaction entre la recherche de sous-ensembles informée par le graphe, la construction d'archives sensibles à la charge et le processus de déploiement à horizon fuyant, qui empêchent collectivement le partitionnement prématuré du réseau ou l'épuisement des nœuds. Le travail suggère que pour les UWSN, la qualité du front de Pareto d'un cycle unique est moins critique que la pertinence du déploiement pour les états futurs du réseau.