Have a personal or library account? Click to login
An efficient connected dominating set algorithm in WSNs based on the induced tree of the crossed cube Cover

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

By: Jing Zhang,  Shu-Ming Zhou,  Li Xu,  Wei Wu and  Xiucai Ye  
Open Access
|Jun 2015

References

  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.10.1016/j.jpdc.2013.01.009
  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.10.1002/net.10097
  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.10.1109/TPDS.2011.30
  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.10.1109/TMC.2011.129
  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.10.1145/1167935.1167941
  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.1142/S1793830909000105
  10. Goli, J.D. (2012). A new authentication model for ad hoc networks, International Journal of Information Security 11(5): 333-347.10.1007/s10207-012-0167-4
  11. Han, B. (2009). Zone-based virtual backbone formation in wireless ad hoc networks, Ad Hoc Networks 7(1): 183-200.10.1016/j.adhoc.2008.01.003
  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.10.1016/j.tcs.2012.11.020
  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.10.1109/TPDS.2008.74
  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.10.1007/s00453-011-9512-7
  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.10.1007/978-3-642-31869-6_11
  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.10.1007/s10878-010-9346-2
  18. Liao, Q. and Li, Z. (2013). Portfolio optimization of computer and mobile botnets, International Journal of Information Security 13(1): 1-14.10.1007/s10207-013-0206-9
  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.10.1007/11745693_50
  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.10.1007/978-1-4614-5131-0_9
  21. Pardalos, R. Enkhbat and E.N. Pistikopoulos (Eds.), Optimization, Simulation, and Control, Springer, New York, NY, pp. 131-142.
  22. 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.10.1109/TPDS.2009.78
  23. 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.
  24. 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.10.1186/1687-1499-2012-83
  25. 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.10.1016/j.tcs.2007.05.025
  26. 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.
  27. 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.
  28. 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.10.1109/TWC.2009.051053
  29. Wang, Y.,Wang, X. andWu, G. (2011). An equivalent definition of the crossed cube, Chinese Quarterly Journal of Mathematics 26(2): 234-238.
  30. 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.
  31. 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.10.1016/j.tcs.2005.08.037
  32. Wu, W., Gao, X., Pardalos, P.M. and Du, D.Z. (2010). Wireless networking, dominating and packing, Optimization Letters 4(3): 347-358.10.1007/s11590-009-0151-8
  33. 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.
  34. 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.
  35. 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.
  36. 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.10.5815/ijcnis.2013.10.04
  37. 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.10.1109/TPDS.2011.305
  38. 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.10.1007/s10207-011-0127-4
  39. 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. 10.1016/j.tcs.2009.06.022
DOI: https://doi.org/10.1515/amcs-2015-0023 | Journal eISSN: 2083-8492 | Journal ISSN: 1641-876X
Language: English
Page range: 295 - 309
Submitted on: Jan 3, 2014
Published on: Jun 25, 2015
Published by: University of Zielona Góra
In partnership with: Paradigm Publishing Services
Publication frequency: 4 issues per year

© 2015 Jing Zhang, Shu-Ming Zhou, Li Xu, Wei Wu, Xiucai Ye, published by University of Zielona Góra
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.