Abstract
The idea of virtual backbone routing has been proposed for efficient routing among a set of mobile nodes in wireless ad hoc networks. Virtual backbone routing can reduce communication overhead and speedup the routing process compared with many existing on-demand routing protocols for routing detection. In many studies, Minimum Connected Dominating Set (MCDS) is used to approximate virtual backbones in a unit-disk graph. However finding a MCDS is a NP-hard problem. We propose a distributed, 3-phase protocol for calculating the CDS in this paper. Our new protocol largely reduces the number of nodes in CDS compared with Wu and Li’s method, while message and time complexities of our approach remain almost the same as those of Wu and Li’s method. We conduct extensive simulations and show our protocol can consistently outperform Wu and Li’s method. The correctness of our protocol is proved through theoretical analysis.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bharghavan, V., Das, B.: Routing in Ad Hoc Networks Using Minimum Connected Domination Sets. In: Proc. Int. Conf. Commun. 1997, Montreal, Canada (June 1997)
Das, B., Sivakumar, R., Bharghavan, V.: Routing in Ad-hoc Networks Using a Spine. In: Proc. Int. Conf. Comput. And Commun. Networks, Las Vegas, NV (September 1997)
Sivakumar, R., Das, B., Bharghavan, V.: An Improved Spine-Based Infrastructure for Routing in Ad Hoc Networks. In: Proc. IEEE Symp. Comput. And Commun., Athens, Greece (June 1998)
Guha, S., Khuller, S.: Approximation Algorithms for Connected Dominating Sets. Algorithmica 20(4), 374–387 (1998)
Alzoubi, K.M., Wan, P.J., Frieder, O.: New Distributed Algorithm for Connected Dominating Set in Wireless Ad Hoc Networks. In: Proc. 35th Hawaii Int. Conf. On System Sciences, January 2002, pp. 1–7 (2002)
Wu, J., Li, H.: A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks. Telecomm. System, Special Issue on Wireless Networks 18(1-3), 13–36 (2001)
Bellur, B., Ogier, R., Templin, F.: Topology Broadcast Based on Reverse-Path Forwarding (tbrpf). Internet Draft, draft-ietf-manet-tbrpf-01.txt, Work in Progress (March 2001)
Johnson, D., Maltz, D.: Mobile Computing, Chapter 5 – Dynamic Source Routing, pp. 153–181. Kluwer Academic Publishers, Dordrecht (1996)
Park, V., Corson, M.: A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. In: Proc. Of INFOCOM 1997 (1997)
Perkins, C., Royer, E.: Ad-hoc On-Demand Distance Vector Routing. In: Proc. Of the 2nd IEEE workshop on Mobile Computing System and Applications, February 1999, pp. 90–100 (1999)
Basagni, S., Chlamatac, I., Syrotiuk, V., Woodward, B.: A Distance Routing Effect Algorithm for Mobility (dream). In: Proc. Of the 4th Annual ACM/IEEE Int. Conf. On Mobile Computing and Networking (MOBICOM) 1998, Dallas, TX, USA, pp. 76–84 (1998)
Li, J., Jannotti, J., De Couto, D.S.J., Karger, D.R., Morris, R.: A Scalable Location Service for Geographic Ad Hoc Routing. In: Proc. Of the 6th Annual ACM/IEEE Int. Conf. On Mobile Computing and Networking (MOBICOM) 2000, Boston, MA, USA, pp. 120–130 (2000)
Karp, B., Kung, H.T.: Greedy Perimeter Stateless Routing for Wireless Networks. In: Proc. Of the 6th Annual ACM/IEEE Int. Conf. On Mobile Computing and Networking (MOBICOM) 2000, Boston, MA, USA, pp. 243–254 (2000)
Ko, Y.B., Vaidya, N.H.: Location-Aided Routing (LAR) in Mobile Ad Hoc Networks. ACM/Baltzer Wireless Networks (WINET) journal 6(4), 307–321 (2000)
Kozat, U.C., Kondylis, G., Ryu, B., Marina, M.K.: Virtual Dynamic Backbone for Mobile Ad Hoc Networks. In: IEEE International Conference on Communications (ICC), Helsinki, Finland (June 2001)
Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks 25, 59–68 (1995)
Zou, H.: An Algorithm for Detecting Termination of Distributed Computation in Arbitrary Network Topologies within Linear Time. In: International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN 1996), pp. 168–172 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, H., Pan, Y., Cao, J. (2004). An Improved Distributed Algorithm for Connected Dominating Sets in Wireless Ad Hoc Networks. In: Cao, J., Yang, L.T., Guo, M., Lau, F. (eds) Parallel and Distributed Processing and Applications. ISPA 2004. Lecture Notes in Computer Science, vol 3358. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30566-8_41
Download citation
DOI: https://doi.org/10.1007/978-3-540-30566-8_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24128-7
Online ISBN: 978-3-540-30566-8
eBook Packages: Computer ScienceComputer Science (R0)