Approximation Two Independent Sets Based Connected Dominating Set Construction Algorithm for Wireless Sensor Networks

摘要

In WSNs (Wireless Sensor Networks), an optimized way of prolonging the networks lifetime and flooding packets is to find the minimum CDS (Connected Dominating Set). In this study, a new method called ATISA (Approximation Two Independent Sets based Algorithm) for constructing CDS is proposed. The ATISA has three stages. The first stage is constructing a connected set CS (connected set) and the second stage is constructing a connected dominating set CDS and the third stage is pruning the redundant dominators of CDS. The performance ratio of ATISA is approximately (9.67+19n_k) when the number of nodes is bigger enough and the message complexity is O(n). Compared with some famous CDS construction algorithms, ATISA constructs the CDS with the smallest size.