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

Sintesi Tecnica: Selezione Multi-obiettivo del Cluster Head in Reti di Sensori Wireless Sottomarini

Formulazione del Problema
Questo articolo affronta il problema della Selezione Multi-obiettivo del Cluster Head (MOCHS) nelle Reti di Sensori Wireless Sottomarini (UWSN). I metodi di clustering esistenti si affidano spesso a indicatori locali o punteggi scalari che non riescono a catturare l'effetto di servizio collettivo di un insieme di Cluster Head (CH) selezionati o il trade-off intrinseco tra capacità di servizio e carico del CH. Gli autori formulano il MOCHS come un problema di ottimizzazione bi-obiettivo per ogni round. I due obiettivi conflittuali sono:

1. Capacità di Servizio Pesata Attesa: Massimizzare la probabilità che i nodi sensore vivi possano consegnare i dati al sink attraverso percorsi acustici multi-hop fattibili tramite i CH selezionati.
2. Carico Operativo: Minimizzare il costo totale (energia e carico operativo) associato alla selezione e all'operatività dei CH scelti.

Il problema è vincolato dalla topologia della rete, dall'affidabilità del link acustico, dall'energia residua e dall'eleggibilità del CH. Fondamentalmente, gli autori trattano la selezione del CH non come una decisione locale istantanea, ma come un processo ripetuto in cui le decisioni attuali influenzano l'energia residua e la fattibilità futura.

Metodologia
L'approccio proposto, LA-MOCHS (Lifetime-Aware Multi-Objective Cluster-Head Selection), integra la teoria dei grafi, l'ottimizzazione submodulare e gli algoritmi evolutivi.

1. Riformulazione dell'Influenza Basata su Grafi:
   Gli autori riformulano l'obiettivo di servizio come una funzione di copertura pesata di tipo "influenza" su un grafo di comunicazione probabilistico. In questo modello, un insieme di CH selezionati agisce come un insieme di semi (seed set), e un nodo è "servito" se può raggiungere un CH tramite un percorso acustico vivo, e quel CH può trasmettere con successo verso il sink.

   • Fondamento Teorico: Il documento dimostra che, sotto questa riformulazione, l'obiettivo di servizio atteso è normalizzato, monotono e submodulare rispetto all'insieme dei candidati CH eleggibili. Questa proprietà strutturale collega la selezione dei CH nelle UWSN ai problemi di massimizzazione dell'influenza e di selezione di sottoinsiemi.

2. Algoritmo LA-MOCHS:
   LA-MOCHS è un framework evolutivo Pareto-basato a orizzonte scorrente (receding-horizon) progettato per risolvere il problema MOCHS per round preservando la durata della rete. Opera in due livelli accoppiati:

   • Ciclo Esterno (Deployment a Orizzonte Scorrente): Ad ogni round, viene osservato lo stato attuale della rete, viene generato un archivio Pareto di configurazioni CH fattibili e viene implementata una configurazione. Lo stato della rete (energia, topologia) viene quindi aggiornato prima del round successivo.
   • Ciclo Interno (Solver per Round): Un solver di selezione di sottoinsiemi basato su Pareto ricerca diverse configurazioni di CH non dominate. I componenti chiave includono:
     • Selezione Adattiva degli Anchor: Regola dinamicamente il numero di sottoinsiemi di riferimento in base alla dimensione dell'insieme eleggibile e al budget di valutazione.
     • Allocazione del Budget di Valutazione a Due Stadi: Alloca il budget computazionale prima per sondare gli anchor e poi per concentrarsi sulle regioni promettenti.
     • Warm-Starting Greedy: Inizializza la ricerca con soluzioni deterministiche fattibili (ad esempio, il miglior singolo elemento, massimizzazione greedy del servizio) per fornire punti di riferimento.
     • Mutazione Consapevole della Fattibilità: Garantisce che le soluzioni figlie soddisfino i vincoli di cardinalità del CH e di fattibilità del clustering (raggiungibilità membro-CH).

Contributi Chiave
Il documento presenta cinque contributi primari:

1. Formulazione del Problema: Definisce il MOCHS come un problema di ottimizzazione bi-obiettivo che cattura esplicitamente il trade-off tra capacità di servizio attesa e carico del CH, evitando la scalariizzazione.
2. Riformulazione Teoria-Grafica: Interpreta l'effetto di servizio di un insieme di CH come una funzione di copertura del servizio probabilistica end-to-end indotta dalla comunicazione acustica multi-hop sottomarina.
3. Dimostrazione Teorica: Dimostra che l'obiettivo di servizio atteso è una funzione di insieme normalizzata, monotona e submodulare, fornendo una base teorica per l'uso dell'ottimizzazione di sottoinsiemi di tipo influenza.
4. Sviluppo dell'Algoritmo: Propone LA-MOCHS, un solver consapevole della durata della vita che combina ancoraggio adattivo, allocazione del budget a due stadi, warm-starting greedy e mutazione consapevole della fattibilità.
5. Validazione Empirica: Conduce simulazioni del ciclo chiuso sulla durata della vita e benchmark a singolo round per dimostrare che il metodo migliora la durata della rete preservando le configurazioni fattibili attraverso i round ripetuti.

Risultati Sperimentali
Gli autori hanno valutato LA-MOCHS contro dieci baseline (tra cui EPOL, POMC, NSGA-II, SPEA2 e MOEA/D) attraverso varie dimensioni di rete (da 50 a 500 nodi) e regole di deployment.

• Durata del Ciclo Chiuso: LA-MOCHS ha dimostrato la conservazione più costante della mezza-durata (half-lifetime) tra i solver operativamente completi. Ha ottenuto il miglior round di non-censura della morte dei nodi (HND) in sette casi su otto impostazioni testate.
• Fattibilità vs Qualità del Singolo Round: Un risultato critico è che il vantaggio di LA-MOCHS non deriva da una qualità del fronte Pareto uniformemente superiore nel singolo round (misurata tramite Hypervolume o IGD). In effetti, alcune baseline hanno prodotto archivi più densi o di qualità superiore in round isolati. Tuttavia, tali baseline spesso terminavano prematuramente a causa di condizioni di "nessuna fattibilità" (esaurimento dei CH viabili).
• Meccanismo: Il miglioramento della durata deriva da un comportamento di deployment consapevole del carico. LA-MOx evita selezioni di CH eccessivamente aggressive che esauriscono l'energia o la fattibilità nei primi round, mantenendo così uno stato di rete vitale per i round successivi.

Significatività e Rivendicazioni
Il documento afferma che la principale significatività di LA-MOCHS risiede nella sua capacità di colmare il divario tra i vincoli fisici delle UWSN e l'ottimizzazione strutturale dei grafi. Sfruttando la natura submodulare dell'obiettivo di servizio e impiegando una strategia a orizzonte scorrente, il metodo privilegia la fattibilità a lungo termine rispetto alla massimizzazione immediata e aggressiva del servizio.

Gli autori dichiarano con modestia che LA-MOCHS non è un ottimizzatore globale offline che massimizza direttamente metriche come HND o LND come singolo obiettivo. È invece un solver a orizzonte scorrente che risolve ripetutamente il trade-off servizio-carico per ogni round. Il suo successo è attribuito all'interazione tra la ricerca di sottoinsiemi informata dal grafo, la costruzione di un archivio consapevole del carico e il processo di deployment a orizzonte scorrente, che collettivamente prevengono la partizione prematura della rete o l'esaurimento dei nodi. Il lavoro suggerisce che, per le UWSN, la qualità del fronte Pareto di un singolo round è meno critica della rilevanza del deployment per gli stati futuri della rete.