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

Technical Summary: Multi-objective Cluster Head Selection in Underwater Wireless Sensor Networks

Problem Formulation
This paper addresses the Multi-objective Cluster Head Selection (MOCHS) problem in Underwater Wireless Sensor Networks (UWSNs). Existing clustering methods often rely on local indicators or scalarized scores that fail to capture the collective service effect of a selected Cluster Head (CH) set or the inherent trade-off between service capability and CH burden. The authors formulate MOCHS as a per-round, bi-objective optimization problem. The two conflicting objectives are:

1. Expected Weighted Service Capability: Maximizing the probability that alive sensor nodes can deliver data to the sink through feasible multi-hop acoustic paths via selected CHs.
2. Operational Burden: Minimizing the total cost (energy and operational load) associated with selecting and operating the chosen CHs.

The problem is constrained by network topology, acoustic link reliability, residual energy, and CH eligibility. Crucially, the authors treat CH selection not as a one-shot local decision but as a repeated process where current decisions influence residual energy and future feasibility.

Methodology
The proposed approach, LA-MOCHS (Lifetime-Aware Multi-Objective Cluster-Head Selection), integrates graph theory, submodular optimization, and evolutionary algorithms.

1. Graph-Based Influence Reformulation:
   The authors reformulate the service objective as an "influence-style" weighted coverage function over a probabilistic communication graph. In this model, a selected CH set acts as a seed set, and a node is "served" if it can reach a CH via a live acoustic path, and that CH can successfully uplink to the sink.

   • Theoretical Foundation: The paper proves that under this reformulation, the expected service objective is normalized, monotone, and submodular over the set of eligible CH candidates. This structural property connects UWSN CH selection to influence maximization and subset selection problems.

2. LA-MOCHS Algorithm:
   LA-MOCHS is a receding-horizon Pareto evolutionary framework designed to solve the round-wise MOCHS problem while preserving network lifetime. It operates in two coupled layers:

   • Outer Loop (Receding-Horizon Deployment): At each round, the current network state is observed, a Pareto archive of feasible CH configurations is generated, and one configuration is deployed. The network state (energy, topology) is then updated before the next round.
   • Inner Loop (Per-Round Solver): A Pareto-based evolutionary subset-selection solver searches for diverse non-dominated CH configurations. Key components include:
     • Adaptive Anchor Selection: Dynamically adjusts the number of reference subsets based on the eligible set size and evaluation budget.
     • Two-Stage Evaluation Allocation: Allocates computational budget first to probe anchors and then to focus on promising regions.
     • Greedy Warm-Starting: Initializes the search with deterministic feasible solutions (e.g., best singleton, greedy service maximization) to provide reference points.
     • Feasibility-Aware Mutation: Ensures offspring solutions satisfy CH cardinality and clustering feasibility constraints (member-to-CH reachability).

Key Contributions
The paper makes five primary contributions:

1. Problem Formulation: Defines MOCHS as a bi-objective optimization problem that explicitly captures the trade-off between expected service capability and CH burden, avoiding scalarization.
2. Graph-Theoretic Reformulation: Interprets the service effect of a CH set as a probabilistic end-to-end service coverage function induced by multi-hop underwater acoustic communication.
3. Theoretical Proof: Proves that the expected service objective is a normalized, monotone, and submodular set function, providing a theoretical basis for using influence-style subset optimization.
4. Algorithm Development: Proposes LA-MOCHS, a lifetime-aware solver that combines adaptive anchoring, two-stage budget allocation, greedy warm-starting, and feasibility-aware mutation.
5. Empirical Validation: Conducts closed-loop lifetime simulations and single-round benchmarks to demonstrate that the method improves network lifetime by preserving feasible configurations over repeated rounds.

Experimental Results
The authors evaluated LA-MOCHS against ten baselines (including EPOL, POMC, NSGA-II, SPEA2, and MOEA/D) across various network sizes (50 to 500 nodes) and deployment rules.

• Closed-Loop Lifetime: LA-MOCHS demonstrated the most consistent half-lifetime preservation among operationally complete solvers. It achieved the best non-censored half-node-death (HND) round in seven out of eight tested settings.
• Feasibility vs. Single-Round Quality: A critical finding is that LA-MOCHS's advantage does not stem from uniformly superior single-round Pareto-front quality (measured by Hypervolume or IGD). In fact, some baselines produced denser or higher-quality archives in isolated rounds. However, those baselines often terminated early due to "no-feasible" conditions (running out of viable CHs).
• Mechanism: The lifetime improvement arises from burden-aware deployment behavior. LA-MOCHS avoids overly aggressive CH selections that deplete energy or feasibility in early rounds, thereby maintaining a viable network state for subsequent rounds.

Significance and Claims
The paper claims that the primary significance of LA-MOCHS lies in its ability to bridge the gap between physical UWSN constraints and structural graph optimization. By leveraging the submodular nature of the service objective and employing a receding-horizon strategy, the method prioritizes long-term feasibility over immediate, aggressive service maximization.

The authors modestly state that LA-MOCHS is not an offline global lifetime optimizer that directly maximizes metrics like HND or LND as a single objective. Instead, it is a receding-horizon solver that repeatedly solves the per-round service-burden trade-off. Its success is attributed to the interaction between graph-informed subset search, burden-aware archive construction, and the receding-horizon deployment process, which collectively prevent premature network partitioning or node exhaustion. The work suggests that for UWSNs, the quality of a single-round Pareto front is less critical than the deployment-relevance of the selected configuration for future network states.