A novel approximation algorithm for minimum virtual backbone problem in wireless sensor networks using cooperative communication

The technologies of virtual backbone (VB) and cooperative communication (CC) are widely used to prolong the lifetime of wireless sensor networks (WSNs). A VB of a WSN using CC is usually modeled as an extended connected dominating set (ECDS), which is expected to be as small as possible. Since the minimum ECDS (MECDS) problem is NP-hard, some approximation algorithms had been proposed for finding MECDS, the best of which has a performance ratio (PR) of 120. In this paper, we propose a new approximation algorithm called CA-ECDS for the MECDS problem and evaluate the performance of CA-ECDS by theoretical analysis and simulation experiments. In the theoretical analysis, we prove the PR of CA-ECDS is 80, which is smallest at present. In the simulation experiments, we compare CA-ECDS with the state-of-the-art algorithms, and the results show that CA-ECDS outperforms other algorithms in terms of ECDS size.