Efficient Optimization Algorithm for Virtual Backbone in Wireless Sensor Networks by Removing Redundant Dominators

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 paper, 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 α∙opt+δ-k+1, where α∙opt+δ 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.