Information Technology Journal1812-56381812-5646Asian Network for Scientific Information10.3923/itj.2010.1081.1092LiuZhuo WangBingwen GuoLejiang 6201096In Wireless Sensor Network (WSN), all nodes are energy constrained. Clustering is a kind of energy efficient algorithm, while using a virtual backbone to organize the nodes is a better way. Although, there is no physical backbone infrastructure, a virtual backbone can be formed by constructing a Connected Dominating Set (CDS). The CDS of a graph representing a network has a significant impact on an efficient design of routing algorithms in WSN. A good CDS should first and foremost be small, additionally, it should have other characteristics such as robustness to node failures and low stretch. In this paper, we present a taxonomy and general classification of CDS construction algorithms. We survey different CDS construction algorithms for WSNs.]]>Abbasi, A.A. and M. Younis,2007Alzoubi, K.M., P.J. Wan and O. Frieder,2003Alzoubi, K.M., P.J. Wan and O. Frieder,2002Das, B. and V. Bharghavan,1997Das, B., R. Sivakumar and V. Bharghavan,1997Jeremy, B., D. Min, T. Andrew and C. Xiuzhen,2004Butenko, S., X. Cheng, C. Oliveira and P.M. Pardalos,2004Chong, C.Y. and S.P. Kumar,2003Estrin, D., R. Govindan, J. Heidemann and S. Kumar,1999Dai, F. and J. Wu,2004Pottie, G.J. and W.J. Kaiser,2000Guha, S. and S. Khuller,1998Chen, G. and I. Stojmenovic,1999Gao, B., Y. Yang and H. Ma, 2005Wang, H., J. Elson, L. Girod, D. Estrin and K. Yao,2003Raei, H., M. Sarram, F. Adibniya and F. Tashtarian,2008Raei, H., M.A. Fathi, A. Akhlaghi and B. Ahmadipoor,2009Akyildiz, I.F., W. Su, Y. Sankarasubramaniam and E. Cayirci,2002Cidon, I. and O. Mokryn,1998Stojmenovic, I., M. Seddigh and J. Zunic,2001Rabaey, J.M., M. Josie Ammer, J.L. da Silva, D. Patel and S. Roundy,2000Wu, J. and H. Li,1999Alzoubi, K.M., P.J. Wan and O. Frieder,2002Li, Y., M.T. Thai, F. Wang, C.W. Yi, P.J. Wang and D.Z. Du,2005Ruan, L., H. Du, X. Jia, W. Wu, Y. Li and K.I. Ko,2004Thai, M.T., F. Wang, D. Liu, S. Zhu and D.Z. Du,2007Cadei, M., X. Cheng and D.Z. Du,2002Misra, R. and C. Mandal,2010Rai, M., S. Verma and S. Tapaswi,2009Gerla, M. and J.T.C. Tsai,1995Wan, P.J., K.M. Alzoubi and O. Frieder,2002Funke, S., A. Kesselman, U. Meyer and M. Segal,2006Sivakumar, R., B. Das and V. Bharghavan,1998Bharghavan, V. and B. Das,1999Chvatal, V.,1979Yingchang, X., X. Kai, C. Wei, E.K. Park and R. Shmuel,2009Cheng, X., M. Ding, D.H. Du and X. Jia,2004Xie, R., D. Qi, Y. Li and J.Z. Wang,2009Li, Y., S. Zhu, M.T. Thai and D.Z. Du, 2004Liu, Z., B. Wang and Q. Tang,2010Liu, Z., B. Wang and W. Yang,2010Lin, C.R. and M. Gerla,1997Kahn, J.M., R.H. Katz and K.S.J. Pister,1999Zeng, Y., X. Jia and Y. He,2006