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

Technische Samenvatting: Multi-objective Cluster Head Selectie in Underwater Wireless Sensor Networks

Probleemformulering
Dit artikel behandelt het Multi-objective Cluster Head Selection (MOCHS) probleem in Underwater Wireless Sensor Networks (UWSNs). Bestaande clusteringmethoden vertrouwen vaak op lokale indicatoren of gescalariseerde scores die er niet in slagen de collectieve servicereffecten van een geselecteerde Cluster Head (CH) verzameling of de inherente afweging tussen servicecapaciteit en CH-belasting te vatten. De auteurs formuleren MOCHS als een per ronde uitgevoerd, bi-objectief optimalisatieprobleem. De twee conflicterende doelstellingen zijn:

1. Verwachte Gewogen Servicecapaciteit: Het maximaliseren van de waarschijnlijkheid dat levende sensorknooppunten gegevens naar de sink kunnen leveren via haalbare multi-hop akoestische paden via de geselecteerde CH's.
2. Operationele Belasting: Het minimaliseren van de totale kosten (energie en operationele last) die gepaard gaan met het selecteren en exploiteren van de gekozen CH's.

Het probleem wordt beperkt door netwerktopologie, de betrouwbaarheid van akoestische verbindingen, resterende energie en CH-geschiktheid. Cruciaal is dat de auteurs CH-selectie niet behandelen als een eenmalige lokale beslissing, maar als een herhaald proces waarbij huidige beslissingen de resterende energie en toekomstige haalbaarheid beïnvloeden.

Methodologie
De voorgestelde aanpak, LA-MOCHS (Lifetime-Aware Multi-Objective Cluster-Head Selection), integreert graaftheorie, submodulaire optimalisatie en evolutionaire algoritmen.

1. Graafgebaseerde Invloedsherformulering:
   De auteurs herformuleren het service-doel als een "invloed-stijl" gewogen dekkingfunctie over een probabilistische communicatiegraaf. In dit model fungeert een geselecteerde CH-verzameling als een 'seed set', en een knooppunt wordt "bediend" als het een CH kan bereiken via een levend akoestisch pad, en die CH succesvol kan uplinken naar de sink.

   • Theoretische Fundering: Het artikel bewijst dat onder deze herformulering de verwachte service-doelstelling genormaliseerd, monotoon en submodulair is over de verzameling van geschikte CH-kandidaten. Deze structurele eigenschap verbindt UWSN CH-selectie met invloedmaximalisatie en subset-selectieproblemen.

2. LA-MOCHS Algoritme:
   LA-MOCHS is een receding-horizon Pareto evolutionair framework dat is ontworpen om het per ronde uitgevoerde MOCHS-probleem op te lossen terwijl de levensduur van het netwerk behouden blijft. Het werkt in twee gekoppelde lagen:

   • Outer Loop (Receding-Horizon Deployment): In elke ronde wordt de huidige netwerkstatus geobserveerd, een Pareto-archief van haalbare CH-configuraties gegenereerd, en één configuratie geïmplementeerd. De netwerkstatus (energie, topologie) wordt vervolgens bijgewerkt voor de volgende ronde.
   • Inner Loop (Per-Round Solver): Een Pareto-gebaseerde evolutionaire subset-selectie solver zoekt naar diverse niet-gedomineerde CH-configuraties. Belangrijke componenten zijn:
     • Adaptieve Anchor Selectie: Past dynamisch het aantal referentie-subsets aan op basis van de grootte van de geschikte verzameling en het evaluatiebudget.
     • Two-Stage Evaluation Allocation: Alloceert het computationele budget eerst om anchors te verkennen en focust vervolgens op veelbelovende regio's.
     • Greedy Warm-Starting: Initialiseert de zoektocht met deterministische haalbare oplossingen (bijv. beste singleton, greedy service maximalisatie) om referentiepunten te bieden.
     • Feasibility-Aware Mutatie: Zorgt ervoor dat nakomelingen-oplossingen voldoen aan de CH-cardinaliteit en clustering-haalbaarheidsbeperkingen (bereikbaarheid van lid-naar-CH).

Belangrijkste Bijdragen
Het artikel levert vijf primaire bijdragen:

1. Probleemformulering: Definieert MOCHS als een bi-objectief optimalisatieprobleem dat expliciet de afweging tussen verwachte servicecapaciteit en CH-belasting vastlegt, zonder gebruik te maken van scalarisatie.
2. Graaf-theoretische Herformulering: Interpreteert het service-effect van een CH-verzameling als een probabilistische end-to-end service dekkingfunctie geïnduceerd door multi-hop onderwater akoestische communicatie.
3. Theoretisch Bewijs: Bewijst dat de verwachte service-doelstelling een genormaliseerde, monotone en submodulaire verzamelfunctie is, wat een theoretische basis biedt voor het gebruik van invloed-stijl subset optimalisatie.
4. Algoritme Ontwikkeling: Stelt LA-MOCHS voor, een lifetime-aware solver die adaptieve anchoring, two-stage budgetallocatie, greedy warm-starting en feasibility-aware mutatie combineert.
5. Empirische Validatie: Voert closed-loop lifetime simulaties en single-round benchmarks uit om aan te tonen dat de methode de levensduur van het netwerk verbetert door haalbare configuraties over opeenvolgende ronden te behouden.

Experimentele Resultaten
De auteurs hebben LA-MOCHS geëvalueerd tegen tien baselines (waaronder EPOL, POMC, NSGA-II, SPEA2 en MOEA/D) over verschillende netwerkgroottes (50 tot 500 knooppunten) en deployment regels.

• Closed-Loop Levensduur: LA-MOCHS vertoonde de meest consistente behoud van de helft van de levensduur (half-lifetime preservation) onder operationeel volledige solvers. Het behaalde de beste non-censored half-node-death (HND) ronde in zeven van de acht geteste instellingen.
• Haalbaarheid vs. Single-Round Kwaliteit: Een cruciale bevinding is dat het voordeel van LA-MOCHS niet voortkomt uit een uniform superieure single-round Pareto-front kwaliteit (gemeten door Hypervolume of IGD). In feite produceerden sommige baselines dichtere of kwalitatief betere archieven in geïsoleerde ronden. Echter, die baselines werden vaak vroegtijdig beëindigd door "geen-ha Barbare" condities (het opraken van levensvatbare CH's).
• Mechanisme: De verbetering in levensduur komt voort uit belasting-bewust deployment gedrag. LA-MOCHS vermijdt te agressieve CH-selecties die energie of haalbaarheid in vroege ronden uitputten, waardoor een levensvatbare netwerkstatus voor volgende ronden behouden blijft.

Significantie en Claims
Het artikel claimt dat de primaire significantie van LA-MOCHS ligt in het vermogen om de kloof te overbruggen tussen fysieke UWSN-beperkingen en structurele graafoptimalisatie. Door gebruik te maken van de submodulaire aard van de service-doelstelling en een receding-horizon strategie toe te passen, geeft de methode prioriteit aan lange-termijn haalbaarheid boven onmiddellijke, agressieve service maximalisatie.

De auteurs stellen bescheiden dat LA-MOCHS geen offline globale lifetime optimizer is die direct metrieken zoals HND of LND als een enkel objectief maximaliseert. In plaats daarvan is het een receding-horizon solver die herhaaldelijk de per-ronde service-burden afweging oplost. Het succes wordt toegeschreven aan de interactie tussen graaf-geïnformeerde subset zoektocht, burden-aware archief constructie, en het receding-horizon deployment proces, die gezamenlijk voortijdige netwerkpartitionering of knooppuntuitputting voorkomen. Het werk suggereert dat voor UWSNs de kwaliteit van een single-round Pareto front minder kritiek is dan de deployment-relevantie van de gekozen configuratie voor toekomstige netwerkstatussen.