An efficient connected dominating set algorithm in WSNs based on the induced tree of the crossed cube

Zhang, J. ; Xu, L. ; Zhou, S. M. ; Wu, W. ; Ye, X.

International Journal of Applied Mathematics and Computer Science, Tome 25 (2015) no. 2, pp. 295-309.

Résumé

The connected dominating set (CDS) has become a well-known approach for constructing a virtual backbone in wireless sensor networks. Then traffic can forwarded by the virtual backbone and other nodes turn off their radios to save energy. Furthermore, a smaller CDS incurs fewer interference problems. However, constructing a minimum CDS is an NP-hard problem, and thus most researchers concentrate on how to derive approximate algorithms. In this paper, a novel algorithm based on the induced tree of the crossed cube (ITCC) is presented. The ITCC is to find a maximal independent set (MIS), which is based on building an induced tree of the crossed cube network, and then to connect the MIS nodes to form a CDS. The priority of an induced tree is determined according to a new parameter, the degree of the node in the square of a graph. This paper presents the proof that the ITCC generates a CDS with a lower approximation ratio. Furthermore, it is proved that the cardinality of the induced trees is a Fibonacci sequence, and an upper bound to the number of the dominating set is established. The simulations show that the algorithm provides the smallest CDS size compared with some other traditional algorithms.

Détail

Keywords: wireless sensor networks, connected dominating set, induced tree, approximation algorithm, crossed cube
Mots-clés : bezprzewodowa sieć sensorowa, podgrafy indukowane, algorytm aproksymacyjny

Bibliographie

[1] Bahaa-Eldin, A.M., Hassan, D.S.M. and Fahmy, H. (2012). RCA: Efficient connected dominated clustering algorithm for mobile ad hoc networks, arXiv preprint, arXiv:1211.0673.

[2] Cheng, B., Fan, J., Jia, X. and Wang, J. (2013). Dimension-adjacent trees and parallel construction of independent spanning trees on crossed cubes, Journal of Parallel and Distributed Computing 73(5): 641–652.

[3] Cheng, X., Huang, X., Li, D., Wu, W. and Du, D.Z. (2003). A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks, Networks 42(4): 202–208.

[4] Dai, F. and Wu, J. (2005). On constructing k-connected k-dominating set in wireless networks, 19th IEEE International Parallel and Distributed Processing Symposium, Denver, CO, USA, p. 81a.

[5] Ding, L., Wu, W., Willson, J., Du, H., Lee, W. and Du, D.Z. (2011). Efficient algorithms for topology control problem with routing cost constraints in wireless networks, IEEE Transactions on Parallel and Distributed Systems 22(10): 1601–1609.

[6] Ding, L., Wu, W., Willson, J., Du, H. and Lee, W. (2012). Efficient virtual backbone construction with routing cost constraint in wireless networks using directional antennas, IEEE Transactions on Mobile Computing 11(7): 1102–1112.

[7] Du, H., Ye, Q., Wu, W., Lee, W., Li, D. and Du, D. (2011). Constant approximation for virtual backbone construction with guaranteed routing cost in wireless sensor networks, INFOCOM, Shanghai, China, pp. 1737–1744.

[8] Funke, S., Kesselman, A., Meyer, U. and Segal, M. (2006). A simple improved distributed algorithm for minimum cds in unit disk graphs, ACM Transactions on Sensor Networks 2(3): 444–453.

[9] Gao, X., Wang, Y., Li, X. and Wu, W. (2009). Analysis on theoretical bounds for approximating dominating set problems, Discrete Mathematics, Algorithms and Applications 1(1): 71–84.

[10] Goli, J.D. (2012). A new authentication model for ad hoc networks, International Journal of Information Security 11(5): 333–347.

[11] Han, B. (2009). Zone-based virtual backbone formation in wireless ad hoc networks, Ad Hoc Networks 7(1): 183–200.

[12] He, J., Ji, S., Pan, Y. and Cai, Z. (2013). Approximation algorithms for load-balanced virtual backbone construction in wireless sensor networks, Theoretical Computer Science 507: 2–16.

[13] Kim, D.,Wang,W., Li, X., Zhang, Z. andWu,W. (2010). A new constant factor approximation for computing 3-connected m-dominating sets in homogeneous wireless networks, INFOCOM, San Diego, CA, USA, pp. 1–9.

[14] Kim, D., Wu, Y., Li, Y., Zou, F. and Du, D.Z. (2009). Constructing minimum connected dominating sets with bounded diameters in wireless networks, IEEE Transactions on Parallel and Distributed Systems 20(2): 147–157.

[15] Li, M., Wan, P.J. and Yao, F. (2011). Tighter approximation bounds for minimum cds in unit disk graphs, Algorithmica 61(4): 1000–1021.

[16] Li, D., Kim, D., Zhu, Q., Liu, L. and Wu, W. (2012a). Minimum total communication power connected dominating set in wireless networks, in X. Wang, R. Zheng, T. Jing and X. Kai (Eds.), Wireless Algorithms, Systems, and Applications, Springer, Berlin/Heidelberg, pp. 132–141.

[17] Li, Y.,Wu, Y., Ai, C. and Beyah, R. (2012b). On the construction of k-connected m-dominating sets in wireless networks, Journal of combinatorial optimization 23(1): 118–139.

[18] Liao, Q. and Li, Z. (2013). Portfolio optimization of computer and mobile botnets, International Journal of Information Security 13(1): 1–14.

[19] Lin, Z., Xu, Wang, D. and Gao, J. (2006). A coloring based backbone construction algorithm in wireless ad hoc network, in Y.-C. Chung and J.E. Moreira (Eds.), Advances in Grid and Pervasive Computing, Springer, Berlin/Heidelberg, pp. 509–516.

[20] Liu, Q., Zhang, Z., Hong, Y., Wu, W. and Du, D.Z. (2013). A PTAS for weak minimum routing cost connected dominating set of unit disk graph, in A. Chinchuluun, P.M. Pardalos, R. Enkhbat and E.N. Pistikopoulos (Eds.), Optimization, Simulation, and Control, Springer, New York, NY, pp. 131–142.

[21] Misra, R. and Mandal, C. (2010). Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks, IEEE Transactions on Parallel and Distributed Systems 21(3): 292–302.

[22] Padmavathy, M.C. (2010). Performance evaluation of energy efficient modulation scheme and hop distance estimation for WSN, International Journal of Communication Networks and Information Security 2(1): 44–49.

[23] Tang, Q., Yang, K., Li, P., Zhang, J., Luo, Y. and Xiong, B. (2012). An energy efficient MCDS construction algorithm for wireless sensor networks, EURASIP Journal on Wireless Communications and Networking 2012: 83.

[24] Thai, M.T., Zhang, N., Tiwari, R. and Xu, X. (2007). On approximation algorithms of k-connected m-dominating sets in disk graphs, Theoretical Computer Science 385(1): 49–59.

[25] Wan, P.J., Alzoubi, K.M. and Frieder, O. (2002). Distributed construction of connected dominating set in wireless ad hoc networks, INFOCOM, 21st Annual Joint Conference of the IEEE Computer and Communications Societies, New York, NY, USA, Vol. 3, pp. 1597–1604.

[26] Wan, P.J., Wang, L. and Yao, F. (2008). Two-phased approximation algorithms for minimum CDS in wireless ad hoc networks, 28th International Conference on Distributed Computing Systems, Beijing, China, pp. 337–344.

[27] Wang, F., Thai, M.T. and Du, D.Z. (2009). On the construction of 2-connected virtual backbone in wireless networks, IEEE Transactions on Wireless Communications 8(3): 1230–1237.

[28] Wang, Y.,Wang, X. andWu, G. (2011). An equivalent definition of the crossed cube, Chinese Quarterly Journal of Mathematics 26(2): 234–238.

[29] Wu, J. and Li, H. (1999). On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Seattle, WA, USA, pp. 7–14.

[30] Wu, W., Du, H., Jia, X., Li, Y. and Huang S.C.H. (2006). Minimum connected dominating sets and maximal independent sets in unit disk graphs, Theoretical Computer Science 352(1): 1–7.

[31] Wu, W., Gao, X., Pardalos, P.M. and Du, D.Z. (2010). Wireless networking, dominating and packing, Optimization Letters 4(3): 347–358.

[32] Wu, Y. and Li, Y. (2008). Construction algorithms for k-connected m-dominating sets in wireless sensor networks, Proceedings of the 9th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Hong Kong SAR, China, pp. 83–90.

[33] Wu, Y., Wang, F., Thai, M, T. and Li, Y. (2007). Constructing k-connected m-dominating sets in wireless sensor networks, Military Communications Conference, MILCOM, Orlando FL, USA, pp. 1–7.

[34] Xu, L. and Lin, Z. (2007). Graph coloring based minimal connected dominating set algorithm in wireless ad hoc networks, Journal on Communications 28(3): 108–114.

[35] Zam, A. and Movahedinia, N. (2013). Performance improvement of cache management in cluster based manet, International Journal of Computer Network and Information Security 5(10): 24–29.

[36] Zhao, Y., Wu, J., Li, F. and Lu, S. (2012). On maximizing the lifetime of wireless sensor networks using virtual backbone scheduling, IEEE Transactions on Parallel and Distributed Systems 23(8): 1528–1535.

[37] Zhu,W.T., Xiang, Y., Zhou, J.D., Deng, R.H. and Bao, F. (2011). Secure localization with attack detection in wireless sensor networks, International Journal of Information Security 10(3): 155–171.

[38] Zou, F., Wang, Y., Xu, X.H., Li, X., Du, H., Wan, P. and Wu, W. (2011). New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs, Theoretical Computer Science 412(3): 198–208.