Abstract
This paper presents an algorithm for constructing a spanner for ad hoc networks whose nodes have variable transmission range. Almost all previous spanner constructions for ad hoc networks assumed that all nodes in the network have the same transmission range. This allowed a succinct representation of the network as a unit disk graph, serving as the basis for the construction. In contrast, when nodes have variable transmission range, the ad hoc network must be modeled by a general disk graph. Whereas unit disk graphs are undirected, general disk graphs are directed. This complicates the construction of a spanner for the network, since currently there are no efficient constructions of low-stretch spanners for general directed graphs. Nevertheless, in this paper it is shown that the class of disk graphs enjoys (efficiently constructible) spanners of quality similar to that of unit disk graph spanners. Moreover, it is shown that the new construction can be done in a localized fashion.
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
Bose, P., Morin, P.: Online routing in triangulations. In: Aggarwal, A.K., Pandu Rangan, C. (eds.) ISAAC 1999. LNCS, vol. 1741, pp. 113–122. Springer, Heidelberg (1999)
Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks 7(6), 609–616 (2001)
Callahan, P.B., Kosaraju, S.R.: A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM 42, 67–90 (1995)
Chan, T.-H., Gupta, A., Maggs, B.M., Zhou, S.: On hierarchical routing in doubling metrics. In: Proc. 16th ACM-SIAM Symp. on Discrete Algorithms, pp. 762–771 (2005)
Chan, T., Patrascu, M.: Point location in sublogarithmic time and other transdichotomous results in computational geometry. In: Proc. 47th IEEE Symp. on Foundations of Computer Science, pp. 325–332 (2006)
Cole, R., Gottlieb, L.: Searching dynamic point sets in spaces with bounded doubling dimension. In: Proc. 38th ACM Symp. on Theory of Computing (2006)
Das, G., Naraimhan, G., Salowe, J.: A new way to weigh malnourished Euclidean graphs. In: Proc. 6th ACM-SIAM Symp. on Discrete Algorithms, pp. 215–222 (1995)
Dobkin, D.P., Lipton, R.J.: Multidimensional searching problems. SIAM J. Comput. 5(2), 181–186 (1976)
Gao, J., Guibas, L., Nguyen, A.: Deformable spanners and applications. In: Proc. 20th ACM Symp. on Computational Geometry, pp. 179–199 (2004)
Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanners for routing in mobile networks. IEEE J. on Selected Areas in Communications 23(1), 174–185 (2005)
Gao, J., Guibas, L.J., Nguyen, A.: Distributed proximity maintenance in ad hoc mobile networks. In: Proc. IEEE Conf. on Distributed Computing in Sensor Systems, June 2005, pp. 4–19 (2005)
Karp, B., Kung, H.T.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proc. 6th Conf. on Mobile computing and networking, pp. 243–254 (2000)
Kuhn, F., Zollinger, A.: Ad-hoc networks beyond unit disk graphs. In: DIALM-POMC 2003: Proceedings of the 2003 joint workshop on Foundations of mobile computing, pp. 69–78. ACM Press, New York (2003)
Li, X.-Y., Calinescu, G., Wan, P.-J., Wang, Y.: Localized delaunay triangulation with application in ad hoc wireless networks. IEEE Trans. on Parallel and Distributed Systems 14(10), 1035–1047 (2003)
Li, X.-Y., Song, W.-Z., Wang, Y.: Localized topology control for heterogeneous wireless sensor networks. ACM Transactions on Sensor Networks 2(1), 129–153 (2006)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)
Onus, M., Richa, A.: Efficient broadcasting and gathering in wireless ad-hoc networks. In: ISPAN 2005 (2005)
Peleg, D.: Distributed computing: a locality-sensitive approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)
Peleg, D., Schäffer, A.A.: Graph spanners. J. Graph Theory 13, 99–116 (1989)
Rajaraman, R.: Topology control and routing in ad hoc networks: a survey. SIGACT News 33(2), 60–73 (2002)
Salowe, J.S.: Constructing multidimensional spanner graphs. Int. J. Comput. Geometry Appl. 1(2), 99–107 (1991)
Stojmenovic, I., Lin, X.: Loop-free hybrid single-path/flooding routing algorithms with guaranteed delivery for wireless networks. IEEE Trans. Parallel Distrib. Syst. 12(10), 1023–1032 (2001)
Vaidya, P.M.: A sparse graph almost as good as the complete graph on points in K dimensions. Discrete & Computational Geometry 6, 369–381 (1991)
Wang, Y., Li, X.-Y.: Efficient delaunay-based localized routing for wireless sensor networks. Int. J. of Communication Systems 20(7), 767–789 (2006)
Wang, Y., Li, X.-Y.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. MONET 11(2), 161–175 (2006)
Yao, A.C.-C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11(4), 721–736 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Peleg, D., Roditty, L. (2008). Localized Spanner Construction for Ad Hoc Networks with Variable Transmission Range. In: Coudert, D., Simplot-Ryl, D., Stojmenovic, I. (eds) Ad-hoc, Mobile and Wireless Networks. ADHOC-NOW 2008. Lecture Notes in Computer Science, vol 5198. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-85209-4_11
Download citation
DOI: https://doi.org/10.1007/978-3-540-85209-4_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-85208-7
Online ISBN: 978-3-540-85209-4
eBook Packages: Computer ScienceComputer Science (R0)