.png){kind=icon}
.png){kind=icon}
Return
Efficient Optimization Algorithm for Virtual Backbone in Wireless Sensor Networks by Removing Redundant Dominators
.png){kind=icon}
PRE
AI
DOI：10.1109/TNSM.2025.3606864.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Wireless sensor networks (WSNs) often utilize virtual backbones (VBs) to optimize routing and reduce energy consumption. The effectiveness of this optimization largely depends on the size of the VB, with smaller VBs offering better performance. In WSNs, VBs are typically modeled as connected dominating sets (CDSs) within unit disk graphs (UDGs). However, existing approximation algorithms for constructing the minimum connected dominating set (MCDS) often introduce redundant dominators, leading to inflated CDSs. To tackle this issue, in this article, we propose a general CDS optimization algorithm named OP-CDS, designed specifically to minimize redundancies. Theoretical analysis shows that the size of the optimized CDS is bounded by alpha & sdot;opt+delta-k+1 , where alpha & sdot;opt+delta represents the upper bound of the unoptimized CDS, and k denotes the number of OP-CDS iterations. Additionally, extensive simulations demonstrate that OP-CDS can effectively optimize the CDS generated by state-of-the-art algorithms with minimal time consumption.
Keywords:
Approximation algorithms
Wireless sensor networks
Optimization
Upper bound
Classification algorithms
Redundancy
Energy consumption
Electronic mail
Storms
Simulation
Virtual backbone
connected dominating set
redundant dominator
wireless sensor network
approximation algorithm
Journal
IF:
5.4
Papers:
520
Citations:
9.2K