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

Resumen Técnico: Selección de Cabezas de Clúster Multiobjetivo en Redes de Sensores Inalámbricos Subacuáticos

Formulación del Problema
Este artículo aborda el problema de la Selección de Cabezas de Clúster Multiobjetivo (MOCHS, por sus siglas en inglés) en Redes de Sensores Inalámbricos Subacuáticos (UWSNs). Los métodos de agrupamiento existentes suelen depender de indicadores locales o puntuaciones escalares que no logran capturar el efecto de servicio colectivo de un conjunto de Cabezas de Clúster (CH) seleccionadas o el compromiso inherente entre la capacidad de servicio y la carga de la CH. Los autores formulan el MOCHS como un problema de optimización bi-objetivo por ronda. Los dos objetivos en conflicto son:

1. Capacidad de Servicio Ponderada Esperada: Maximizar la probabilidad de que los nodos sensores vivos puedan entregar datos al sumidero a través de rutas acústicas de múltiples saltos factibles vía las CH seleccionadas.
2. Carga Operativa: Minimizar el costo total (energía y carga operativa) asociado con la selección y operación de las CH elegidas.

El problema está restringido por la topología de la red, la fiabilidad del enlace acústico, la energía residual y la elegibilidad de la CH. Crucialmente, los autores tratan la selección de la CH no como una decisión local de un solo paso, sino como un proceso repetido donde las decisiones actuales influyen en la energía residual y la viabilidad futura.

Metodología
El enfoque propuesto, LA-MOCHS (Lifetime-Aware Multi-Objective Cluster-Head Selection), integra la teoría de grafos, la optimización submodular y los algoritmos evolutivos.

1. Reformulación de Influencia Basada en Grafos:
   Los autores reformulan el objetivo de servicio como una función de cobertura ponderada de "estilo influencia" sobre un grafo de comunicación probabilístico. En este modelo, un conjunto de CH seleccionado actúa como un conjunto semilla, y un nodo es "servido" si puede alcanzar una CH a través de una ruta acústica viva, y esa CH puede realizar con éxito el enlace ascendente hacia el sumidero.

   • Fundamento Teórico: El artículo demuestra que, bajo esta reformulación, el objetivo de servicio esperado es normalizado, monótono y submodular sobre el conjunto de candidatos elegibles para CH. Esta propiedad estructural conecta la selección de CH en UWSN con los problemas de maximización de la influencia y de selección de subconjuntos.

2. Algoritmo LA-MOCHS:
   LA-MOCHS es un marco evolutivo de Pareto de horizonte rodante diseñado para resolver el problema MOCHS por ronda mientras preserva la vida útil de la red. Opera en dos capas acopladas:

   • Bucle Externo (Despliegue de Horizonte Rodante): En cada ronda, se observa el estado actual de la red, se genera un archivo de Pareto de configuraciones de CH factibles y se despliega una configuración. El estado de la red (energía, topología) se actualiza antes de la siguiente ronda.
   • Bucle Interno (Solucionador por Ronda): Un solucionador de selección de subconjuntos basado en Pareto busca configuraciones de CH diversas y no dominadas. Los componentes clave incluyen:
     • Selección de Anclaje Adaptativo: Ajusta dinámicamente el número de subconjuntos de referencia basándose en el tamaño del conjunto elegible y el presupuesto de evaluación.
     • Asignación de Evaluación de Dos Etapas: Asigna el presupuesto computacional primero para sondear los anclajes y luego para enfocarse en regiones prometedoras.
     • Arranque en Caliente Greedy (Codicioso): Inicializa la búsqueda con soluciones deterministas factibles (por ejemplo, el mejor elemento único, maximización de servicio greedy) para proporcionar puntos de referencia.
     • Mutación Consciente de la Factibilidad: Asegura que las soluciones descendientes satisfagan las restricciones de cardinalidad de la CH y de factibilidad de agrupamiento (alcanzabilidad miembro-a-CH).

Contribuciones Clave
El artículo realiza cinco contribuciones primarias:

1. Formulación del Problema: Define el MOCHS como un problema de optimización bi-objetivo que captura explícitamente el compromiso entre la capacidad de servicio esperada y la carga de la CH, evitando la la la escala de valores (scalarization).
2. Reformulación Basada en Teoría de Grafos: Interpreta el efecto de servicio de un conjunto de CH como una función de cobertura de servicio de extremo a extremo probabilística inducida por la comunicación acústica subacuática de múltiples saltos.
3. Prueba Teórica: Demuestra que el objetivo de servicio esperado es una función de conjunto normalizada, monótona y submodular, proporcionando una base teórica para el uso de la optimización de subconjuntos de estilo influencia.
4. Desarrollo de Algoritmo: Propone LA-MOCHS, un solucionador consciente de la vida útil que combina anclaje adaptativo, asignación de presupuesto de dos etapas, arranque en caliente greedy y mutación consciente de la factibilidad.
5. Validación Empírica: Realiza simulaciones de vida útil de bucle cerrado y comparativas de ronda única para demostrar que el método mejora la vida útil de la red al preservar configuraciones factibles a lo largo de rondas repetidas.

Resultados Experimentales
Los autores evaluaron LA-MOCHS contra diez líneas de base (incluyendo EPOL, POMC, NSGA-II, SPEA2 y MOEA/D) a través de varios tamaños de red (50 a 500 nodos) y reglas de despliegue.

• Vida Útil de Bucle Cerrado: LA-MOCHS demostró la preservación de vida útil media más consistente entre los solucionadores operativamente completos. Logró la mejor ronda de muerte de medio nodo (HND) no censurada en siete de los ocho escenarios probados.
• Factibilidad vs. Calidad de Ronda Única: Un hallazgo crítico es que la ventaja de LA-MOCHS no proviene de un frente de Pareto de ronda única uniformemente superior (medido por Hipervolumen o IGD). De hecho, algunas líneas de base produjeron archivos más densos o de mayor calidad en rondas aisladas. Sin embargo, esas líneas de base a menudo terminaban prematuramente debido a condiciones de "no factibilidad" (agotamiento de CH viables).
• Mecanismo: La mejora en la vida útil surge de un comportamiento de despliegue consciente de la carga. LA-MOCHS evita selecciones de CH excesivamente agresivas que agotan la energía o la factibilidad en las primeras rondas, manteniendo así un estado de red viable para las rondas subsiguientes.

Significancia y Reivindicaciones
El artículo afirma que la principal significancia de LA-MOCHS radica en su capacidad para cerrar la brecha entre las restricciones físicas de las UWSN y la optimización estructural de grafos. Al aprovechar la naturaleza submodular del objetivo de servicio y emplear una estrategia de horizonte rodante, el método prioriza la viabilidad a largo plazo sobre la maximización de servicio inmediata y agresiva.

Los autores declaran modestamente que LA-MOCHS no es un optimizador de vida útil global offline que maximice directamente métricas como HND o LND como un único objetivo. En cambio, es un solucionador de horizonte rodante que resuelve repetidamente el compromiso entre servicio y carga por ronda. Su éxito se atribuye a la interacción entre la búsqueda de subconjuntos informada por grafos, la construcción de archivos conscientes de la carga y el proceso de despliegue de horizonte rodante, que colectivamente previenen la partición prematura de la red o el agotamiento de los nodos. El trabajo sugiere que, para las UWSNs, la calidad de un frente de Pareto de una sola ronda es menos crítica que la relevancia de despliegue de la configuración seleccionada para estados futuros de la red.