Abstract: 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+19nk) 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.