EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Miray Kol iD, Ege Erberk Uslu iD, Zuleyha Akusta Dagdeviren iD, Orhan Dagdeviren iD

Sensors · 29.04.2026 · 26 (9) · 2752

DOI: 10.3390/s26092752 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Sensors, online erschienen am 29.04.2026. Verfasst von Miray Kol und 3 weiteren Autor:innen. Beteiligte Einrichtung: Department of Computer Engineering, Ege University, Izmir 35100, Turkey. Die Arbeit wurde bisher 3-mal zitiert (Crossref) und nennt 63 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Amateur Radio Digital Communications.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Schlagwörter

Stichwörter der Autor:innen

graph theoryinternet of thingslink monitoringnetwork securitywireless sensor networks

Autor:innen und Institutionen

  • Department of Computer Engineering, Ege University, Izmir 35100, Turkey.

ORCID-Profile: Miray Kol, Ege Erberk Uslu, Zuleyha Akusta Dagdeviren, Orhan Dagdeviren

Förderung

  • Amateur Radio Digital Communications

Zitieren

APA

Kol, M., Uslu, E. E., Dagdeviren, Z. A., & Dagdeviren, O. (2026). Design and Analysis of Minimum-Weighted Connected Capacitated Vertex Cover Algorithms for Link Monitoring in IoT-Enabled WSNs. Sensors, 26(9), 2752. https://doi.org/10.3390/s26092752

Vancouver

Kol M, Uslu EE, Dagdeviren ZA, Dagdeviren O. Design and Analysis of Minimum-Weighted Connected Capacitated Vertex Cover Algorithms for Link Monitoring in IoT-Enabled WSNs. Sensors. 2026;26(9):2752. doi:10.3390/s26092752

BibTeX
@article{Kol2026,
  author = {Kol, Miray and Uslu, Ege Erberk and Dagdeviren, Zuleyha Akusta and Dagdeviren, Orhan},
  title = {Design and Analysis of Minimum-Weighted Connected Capacitated Vertex Cover Algorithms for Link Monitoring in IoT-Enabled WSNs},
  journal = {Sensors},
  year = {2026},
  volume = {26},
  number = {9},
  pages = {2752},
  doi = {10.3390/s26092752}
}
Kostenlos starten →