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

Jing Zhang; Li Xu; Shu-ming Zhou; Wei Wu; Xiucai Ye

International Journal of Applied Mathematics and Computer Science (2015)

  • Volume: 25, Issue: 2, page 295-309
  • ISSN: 1641-876X

Abstract

top
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.

How to cite

top

Jing Zhang, et al. "An efficient connected dominating set algorithm in wsns based on the induced tree of the crossed cube." International Journal of Applied Mathematics and Computer Science 25.2 (2015): 295-309. <http://eudml.org/doc/270520>.

@article{JingZhang2015,
abstract = {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.},
author = {Jing Zhang, Li Xu, Shu-ming Zhou, Wei Wu, Xiucai Ye},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {wireless sensor networks; connected dominating set; induced tree; approximation algorithm; crossed cube},
language = {eng},
number = {2},
pages = {295-309},
title = {An efficient connected dominating set algorithm in wsns based on the induced tree of the crossed cube},
url = {http://eudml.org/doc/270520},
volume = {25},
year = {2015},
}

TY - JOUR
AU - Jing Zhang
AU - Li Xu
AU - Shu-ming Zhou
AU - Wei Wu
AU - Xiucai Ye
TI - An efficient connected dominating set algorithm in wsns based on the induced tree of the crossed cube
JO - International Journal of Applied Mathematics and Computer Science
PY - 2015
VL - 25
IS - 2
SP - 295
EP - 309
AB - 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.
LA - eng
KW - wireless sensor networks; connected dominating set; induced tree; approximation algorithm; crossed cube
UR - http://eudml.org/doc/270520
ER -

References

top
  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. Zbl1284.68449
  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. Zbl1031.05092
  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. Zbl1101.68003
  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. Zbl1178.68680
  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. Zbl1301.68035
  13. Kim, D., Wang, W., Li, X., Zhang, Z. and Wu, 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. Zbl1231.68182
  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. Zbl1245.90106
  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. Zbl1308.90188
  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. Zbl1124.68082
  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. and Wu, G. (2011). An equivalent definition of the crossed cube, Chinese Quarterly Journal of Mathematics 26(2): 234-238. Zbl1240.05152
  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. Zbl1086.68107
  31. Wu, W., Gao, X., Pardalos, P.M. and Du, D.Z. (2010). Wireless networking, dominating and packing, Optimization Letters 4(3): 347-358. Zbl1201.90046
  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. Zbl1209.68389

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.