Skip to main content
SpringerLink
Log in

Minimum connected dominating set based RSU allocation for smartCloud vehicles in VANET

  • Published:
Cluster Computing Aims and scope Submit manuscript

Abstract

Nodes (smartCloud vehicles) of minimum connected dominating set form a virtual backbone in a wireless vehicular ad hoc network. A minimum connected dominating set is a minimum set of connected nodes such that every other node in the network is one hop connected with a node in this set. A smartCloud vehicle sends periodic beacon messages (Coordinates) to nearest roadside unit. Every time check smartCloud vehicle or Star whether it belongs to a connected dominating set (CDS). SmartCloud Vehicles in the CDS use a shorter waiting period and retransmit coordinates to same RSU. At time-out expiration, a smartCloud vehicle to address next RSU connectivity and appearance of new neighbors transmits the coordinates. In general, the problem is proved to be NP-hard. In this paper we find a minimum connected dominating set for certain vehicular ad hoc networks. Simulation-based performance evaluation for improving speed, transmission range, processing power, delay using graphs.

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

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

Abbreviations

VANET:

Vehicular ad hoc networks

RSU:

Road side unit

STAR:

Transportation server

G:

Graph

\(\hbox {G}(\hbox {n},\pm \{1,2,3\ldots \hbox {j}\})\) :

Circulant network

S:

Dominating set

R:

Connected dominating set

N[v]:

Closed neighbourhood of v

\({\upgamma }\) (G):

Minimum dominating set (MDS)

\({\upgamma }_{\mathrm{c}}\) (G):

Minimum connected dominating set

\({\uptau }_{\mathrm{l}}\) (G):

Maximum leaf spanning tree (MLST)

References

  1. Dai, F., Wu, J.: An extended localized algorithm for connected dominating set formation in ad hoc wireless networks. IEEE Trans. Parallel Distrib. Syst. 15(10), 908–920 (2004)

    Article  Google Scholar 

  2. Misra, R., Mandal, C.: Minimum connected dominating set using a collaborative cover heuristic for ad hoc sensor networks. IEEE Trans. Parallel Distrib. Syst. 21, 292–302 (2010)

    Article  Google Scholar 

  3. Xu, J.: Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, Dordrecht (2001)

    Book  MATH  Google Scholar 

  4. 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, 147–157 (2009)

    Article  Google Scholar 

  5. Dimokas, N., Katsaros, D., Manolopoulos, Y.: Energy-efficient distributed clustering in wireless sensor networks. J. Parallel Distrib. Comput. 70, 371–383 (2010)

    Article  MATH  Google Scholar 

  6. Rai, M., Verma, S., Tapaswi, S.: A power aware minimum connected dominating set for wireless sensor networks. J. Netw. 4(6), 511–519 (2009)

    Google Scholar 

  7. Wan, P.J., Alzoubi, K.M., Frieder, O.: Distributed construction of connected dominating set in wireless ad hoc networks. In: IEEE INFOCOM, pp. 1597–1604 (2002)

  8. Bharghavan, V., Das, B.: Routing in ad hoc networks using minimum connected dominating set. In: Proceedings of International Conference on Communications’97, Montreal, Canada (1997)

  9. Wu, J., Li, H.L.: On calculating connected dominating set for efficient routing in ad hoc wireless networks. In: Proceedings of the 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 7–14 (1999)

  10. Kleitman, D.J., West, D.B.: Spanning trees with many leaves. SIAM J. Discret. Math. 4, 99–106 (1991)

    Article  MathSciNet  MATH  Google Scholar 

  11. Storer, J.A.: Constructing full spanning trees for cubic graphs. Inf. Process. Lett. 13, 8–11 (1981)

    Article  MathSciNet  MATH  Google Scholar 

  12. Fernandes, L.M., Gouveia, L.: Minimal spanning trees with a constraint on the number of leaves. Eur. J. Oper. Res. 104, 250–261 (1998)

    Article  MATH  Google Scholar 

  13. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)

    MATH  Google Scholar 

  14. Fernau, H., Kneis, J., Kratsch, D., Langer, A., Liedloff, M., Raible, D., Rossmanith, P.: An exact algorithm for the maximum leaf spanning tree problem. Theoret. Comput. Sci. 412, 6290–6302 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  15. Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20, 374–387 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fomin, F.V., Grandoni, F., Kratsch, D.: Solving connected dominating set faster than 2n. Algorithmica 52(2), 153–166 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  17. Lu, H., Ravi, R.: Approximating maximum leaf spanning trees in almost linear time. J. Algorithms 29, 132–41 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  18. Fujie, T.: An exact algorithm for the maximum leaf spanning tree problem. Comput. Oper. Res. 30(13), 1931–1944 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  19. Tsai, Y.T., Lin, Y.L., Hsu, F.R.: Efficient algorithms for the minimum connected domination on trapezoid graphs. Inf. Sci. 177(12), 2405–2417 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  20. Li, P.C., Toulouse, M.: Maximum leaf spanning trees for grid graphs. J. Comb. Math. Comb. Comput. 73, 181–193 (2010)

    MathSciNet  MATH  Google Scholar 

  21. Chen, Y.C., Syu, Y.L.: Connected dominating set of hypercubes and star graphs. In: International conference on software and computer applications, vol. 41 (2012)

  22. Suresh, A., Varatharajan, R.: Competent resource provisioning and distribution techniques for cloud computing environment. Cluster Comput. (2017) https://doi.org/10.1007/s10586-017-1293-6

  23. Aslam, B., Wang, P., Zou, C.: An economical, deployable and secure vehicular ad hoc network. In: Proc, Military Communication Conf., San Diego, CA, pp. 1–7 (2008)

  24. Kafsi, M., Papadimitratos, P., Doussey, O., Alpcanz, T., Hubaux, J.P.: VANET connectivity analysis. Tech. Rep., EPFL/T-Labs, Lausanne, Switzerland (2008)

  25. Mohandas, B.K., Nayak, A., Naik, K., Goel, N.: ABSRP-A service discovery approach for vehicular ad-hoc networks. In: Proc. 3rd IEEE Asia-Pacific Services Computing Conf., Pisa, Italy, pp. 1590–1594 (2008)

  26. Wong, G.K., Coppersmith, D.A.: A combinatorial problem related to multi module memory organization. J. Assoc. Comput. Mach. 21, 392–401 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  27. Boesch, F.T., Wang, J.: Reliable circulant networks with minimum transmission delay. IEEE Trans. Circ. Syst. 32(12), 1286–1291 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  28. Bermond, J.C., Comellas, F., Hsu, D.F.: Distributed loop computer networks, a survey. J. Parallel Distrib. Comput. 24(1), 2–10 (1995)

    Article  Google Scholar 

  29. Mershad, K., Artail, H., Gerla, M.: We can deliver messages to far vehicles. IEEE Trans. Intell. Transp. Syst. 13(3), 1099–1115 (2012)

    Article  Google Scholar 

  30. Rajasingh, I., Rajan, B., Rajan, R.S.: Combinatorial properties of circulant networks. Int. J. Appl. Math. 41(4), 349–351 (2011)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, Sri Sairam Engineering College, Anna University, Chennai, India

    A. Chinnasamy

  2. Department of Computer Science and Engineering, RGM College of Engineering and Technology, Nandyal, India

    B. Sivakumar

  3. Department of Computer Science and Engineering, Tagore Engineering College, Anna University, Chennai, India

    P. Selvakumari

  4. Department of Computer Science and Engineering, Nehru Institute of Engineering and Technology, T.M. Palayam, Coimbatore, Tamil Nadu, 641105, India

    A. Suresh

Authors
  1. A. Chinnasamy
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Sivakumar
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. P. Selvakumari
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. A. Suresh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to B. Sivakumar.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Chinnasamy, A., Sivakumar, B., Selvakumari, P. et al. Minimum connected dominating set based RSU allocation for smartCloud vehicles in VANET. Cluster Comput 22 (Suppl 5), 12795–12804 (2019). https://doi.org/10.1007/s10586-018-1760-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10586-018-1760-8

Keywords

Search

Navigation