Design and Analysis of Minimum-Weighted Connected Capacitated Vertex Cover Algorithms for Link Monitoring in...

Wireless sensor networks (WSNs) are the backbone of IoT-enabled smart manufacturing, environmental monitoring, and industrial automation. However, their broadcast nature makes communication links vulnerable to eavesdropping, routing manipulation, and denial-of-service attacks. Strategically placing monitor nodes to check each link is an effective approach to protect against attacks, but energy, connectivity, and capacity constraints should be considered while picking monitor nodes. In this paper, we tackle the Minimum-Weighted Connected Capacitated Vertex Cover (MWCCVC) problem, which minimizes monitoring costs, ensures backbone connectivity, and adheres to per-node capacity constraints. Unlike prior works that consider weighted vertex cover, connectivity constraints, or capacitated variants separately, the proposed MWCCVC model jointly integrates all three dimensions within a single vertex cover-based monitoring framework. We first provide a Branch-and-Bound (B&B) solver with linear programming relaxation bounds and constraint-based pruning strategies that produces optimum solutions. Three constructive greedy heuristics (GD, GR, GW) and two hybrid genetic algorithms (HGA, HGA-v2) that combine parameterized greedy decoders with evolutionary search are proposed; all methods guarantee full edge coverage, induced-subgraph connectivity, and max-flow-validated capacity feasibility. Tests on 130 small, 160 medium, and 19 large benchmark instances show that HGA matches B&B optima on every small instance, beats the time-limited B&B by 6.6% on medium instances, where the percentage is computed based on the relative difference in average total weight with respect to B&B, and stays the best on large graphs with up to 1000 nodes. The HGA-v2 tries to balance the quality and speed, with only a 3.1% difference at 10× faster execution.