Skip to main content
SpringerLink
Log in

An exact algorithm for minimum CDS with shortest path constraint in wireless networks

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

In this paper, we study a minimum connected dominating set problem (CDS) in wireless networks, which selects a minimum CDS with property that all intermediate nodes inside every pairwise shortest path should be included. Such a minimum CDS (we name this problem as SPCDS) is an important tache of some other algorithms for constructing a minimum CDS. We prove that finding such a minimum SPCDS can be achieved in polynomial time and design an exact algorithm with time complexity O(δ 2 n), where δ is the maximum node degree in communication graph.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Tsai Y.-P., Hsu T.-L., Liu R.-S., Ho Y.-K.: A backbone routing protocol based on the connected dominating set in ad hoc networks. World Cong. Comput. Sci. Inf. Eng. 1, 14–18 (2009)

    Google Scholar 

  2. Cheng X., Ding M., Du D.H., Jia X.: Virtual backbone construction in multihop ad hoc wireless networks: Research articles. Wireless Commun. Mobile Comput. 6(2), 183–190 (2006)

    Article  Google Scholar 

  3. Yiwei, W., Chunyu, A., Shan, G., Yingshu, L.: p-Percent coverage in wireless sensor networks. In: WASA ’08: Proceedings of the third international conference on wireless algorithms, systems, and applications, pp. 200–211. Springer, Berlin (2008)

  4. Iqbal A., Ahmed N., Mostofa Akbar M.: Directional antenna based connected dominating set construction for energy efficient broadcasting in wireless ad hoc network. Int. Conf. Comput. Electr. Eng. 0, 839–843 (2008)

    Article  Google Scholar 

  5. Wu W., Du H., Jia X., Li Y., Huang S.C.-H.: Minimum connected dominating sets and maximal independent sets in unit disk graphs. Theor. Comput. Sci. 352(1), 1–7 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  6. Wu J., Dai F., Gao M., Stojmenovic I.: On calculating power-aware connected dominating sets for efficient routing in ad hoc wireless networks. IEEE/KICS J. Commun. Netw. 4, 59–70 (2002)

    Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  8. Mohammed, K., Gewali, L., Muthukumar, V.: Generating quality dominating sets for sensor network. In: ICCIMA ’05: Proceedings of the sixth international conference on computational intelligence and multimedia applications, pp. 204–211. IEEE Computer Society, Washington, DC (2005)

  9. Zhang, N., Shin, I., Zou, F., Wu, W., Thai, M.T.: Trade-off scheme for fault tolerant connected dominating sets on size and diameter. In: FOWANC ’08: Proceeding of the 1st ACM international workshop on foundations of wireless ad hoc and sensor networking and computing, pp. 1–8. ACM, New York (2008)

  10. Kim D., Wu Y., Li Y., Zou F., Du D.-Z.: Constructing minimum connected dominating sets with bounded diameters in wireless networks. IEEE Trans. Parallel Distrib. Syst. 20(2), 147–157 (2009)

    Article  Google Scholar 

  11. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of np-Completeness. Series of Books in the Mathematical Sciences. W. H. Freeman, San Francisco (1979)

  12. Clark B.N., Colbourn C.J., Johnson D.S.: Unit disk graphs. Discret. Math. 86(1–3), 165–177 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  13. Du, D.-Z., Lu, B., Ngo, H., Pardalos, P.M.: Steiner tree problems. In: Floudas, C., Pardalos, P. (eds.) Encyclopedia of Optimization, vol. 5, pp. 227–290. Kluwer (2001)

  14. Guha S., Khuller S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1996)

    Article  MathSciNet  Google Scholar 

  15. Ruan L., Du H., Jia X., Wu W., Li Y., Ko K.-I.: A greedy approximation for minimum connected dominating sets. Theor. Comput. Sci. 329(1–3), 325–330 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  16. Min M., Du H., Jia X., Huang C.X., Huang S.C.-H., Wu W.: Improving construction for connected dominating set with steiner tree in wireless sensor networks. J. Glob. Optim. 35(1), 111–119 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  17. Chen D., Du D.-Z., Hu X.-D., Lin G.-H., Wang L., Xue G.: Approximations for steiner trees with minimum number of steiner points. J. Glob. Optim. 18(1–3), 17–33 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  18. Du D.-Z., Pardalos P.: Handbook of Combinatorial Optimization. Kluwer, Dordrecht (2004)

    Google Scholar 

  19. Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: Proceedings of IEEE ICC (1997)

  20. Butenko, S., Cheng, X.Z., Du, D.-Z., Pardalos, P.M.: On the construction of virtual backbone for ad hoc wireless network. In: Proceedings of conference on cooperative control and optimization (2001)

  21. Alzoubi, K., Wan, P.-J., Frieder, O.: New distributed algorithm for connected dominating set in wireless ad hoc networks. In: Proceedings of IEEE HICSS (2002)

  22. Di, W., Yan, Q., Ning, T.: Connected dominating set based hybrid routing algorithm in ad hoc networks with obstacles. In: Proceedings of IEEE ICC (2006)

  23. Deb, B., Bhatnagar, S., Nath, B.: Multi-resolution state retrieval in sensor networks. In: Proceedings of IEEE international workshop on sensor network protocols and applications (2003)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, The University of Texas at Dallas, Dallas, USA

    Ling Ding, Xiaofeng Gao, Weili Wu & Ding-Zhu Du

  2. Department of Computer Science and Engineering, Korea University, Seoul, Republic of Korea

    Wonjun Lee

  3. Department of Mathematics, Xi’an Jiaotong University, Xi’an, People’s Republic of China

    Xu Zhu

Authors
  1. Ling Ding
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Xiaofeng Gao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Weili Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Wonjun Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Xu Zhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Ding-Zhu Du
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ling Ding.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ding, L., Gao, X., Wu, W. et al. An exact algorithm for minimum CDS with shortest path constraint in wireless networks. Optim Lett 5, 297–306 (2011). https://doi.org/10.1007/s11590-010-0208-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-010-0208-8

Keywords

Search

Navigation