Information Technology Journal1812-56381812-5646Asian Network for Scientific Information10.3923/itj.2010.864.876LiuZ. WangB. TangQ. 5201095In 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.]]>Hahn, B.H. and D.T. Valentine,20104th Edn.,Jeremy, B., D. Min, T. Andrew and C. Xiuzhen,20042004pp: 329-369pp: 329-369Adjih, C., P. Jacquet and L. Viennot,200512739Dai, F. and J. Wu,200415908920Raei, H., M. Sarram, F. Adibniya and F. Tashtarian,20082008pp: 695700Raei, H., M.A. Fathi, A. Akhlaghi and B. Ahmadipoor,20092009pp: 983988Alzoubi, K., P.J. Wan and O. Frieder,20022002pp: 38493855Zhou, K., L. Meng, Z. Xu, G. Li and J. Hua,20087694697Kim, D., Y. Wu, Y. Li, F. Zou and D.Z. Du,200920147157Alzoubi, K.M., P.J. Wan and O. Frieder,20022002pp: 157164Li, Y., M.T. Thai, F. Wang, C.W. Yi, P.J. Wang and D.Z. Du,20055927932Rai, M., S. Verma and S. Tapaswi,20092009pp: 106111Thai, M.T., F. Wang, D. Liu, S. Zhu and D.Z. Du,20076721730Thai, M.T., R. Tiwari and D.Z. Du,2008710981109Funke, S., A. Kesselman, U. Meyer and M. Segal,20062444453Guha, S. and S. Khuller,199820374387Stojmenovic, I., M. Seddigh and J. Zunic,2002131425Feng, W., M.T. Thai and D. Ding-Zhu,2009812301237Wu, J. and H. Li,19991999pp: 714Wu, J., W. Lou and F. Dai,200655334347Jie, W., D. Fei and Y. Shuhui,200857702715Jie, W. and D. Fai,2006511881200Wang, Y., W. Wang and X.Y. Li,200617681693Xie, R., D. Qi, Y. Li and J.Z. Wang,20099427437Yingchang, X., X. Kai, C. Wei, E.K. Park and R. Shmuel,20092009Shuhui, Y., W. Jie and D. Fei,20081916011613Zeng, Y., X. Jia and Y. He,20062006pp: 797802Li, Y., S. Zhu, M.T. Thai and D.Z. Du, 20042004Wan, P.J., K.M. Alzoubi and O. Frieder,20022002pp: 15971604Das, B. and V. Bharghavan,19971997pp: 376380Dai, Z., Z. Li, B. Wang and Q. Tang,2009810441048