[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Topology Control and Geographic Routing in Realistic Wireless Networks

  • Conference paper
Ad-Hoc, Mobile, and Wireless Networks (ADHOC-NOW 2007)

Part of the book series: Lecture Notes in Computer Science ((LNCCN,volume 4686))

Included in the following conference series:

  • 432 Accesses

Abstract

We present a distributed topology control protocol that runs on a d-QUDG for d ≥ 1/\(\sqrt{2}\), and computes a sparse, constant-spanner, both in Euclidean distance and in hop distance. QUDGs (short for Quasi Unit Disk Graphs) generalize Unit Disk Graphs and permit more realistic modeling of wireless networks, allowing for imperfect and non-uniform transmission ranges as well as uncertain node location information.Our protocol is local and runs in O(1) rounds. The output topology permits memoryless (geographic) routing with guaranteed delivery. In fact, when our topology control protocol is used as preprocessing step for the geographic routing protocol GOAFR + , we get the routing time guarantee of O(l 2) for any source-destination pair that are l units away from each other in the input d-QUDG. The key idea is simple: to obtain planarity, we replace each edge intersection with a virtual node and have a real node serve as a proxy for the virtual node. This idea is supported by other parts of our protocol that (i) use clustering to keep the density of edge crossings bounded and (ii) guarantee that an edge between a virtual node and a neighbor is realized by a constant-hop path in the real network. The virtual node idea is simple enough to be useful in many contexts. For example, it can be combined with a scheme recently suggested by Funke and Milosavljević (INFOCOM 2007) to guarantee delivery under uncertain node locations. Similarly, the virtual nodes idea can also be used as a cheap alternative to edge-crossing removal schemes suggested by Kim et al. (DIALM-POMC 2005, SENSYS 2006).

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Alzoubi, K.M., Wan, P.-J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: MobiHoc 2002. Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, pp. 157–164. ACM Press, New York (2002)

    Chapter  Google Scholar 

  2. Barriére, L., Fraigniaud, P., Narayanan, L.: Robust position-based routing in wireless ad hoc networks with unstable transmission ranges. In: DIALM 2001. Proceedings of the 5th international workshop on Discrete algorithms and methods for mobile computing and communications, pp. 19–27 (2001)

    Google Scholar 

  3. Bose, P., Devroye, L., Evans, W.S., Kirkpatrick, D.G.: On the spanning ratio of gabriel graphs and beta-skeletons. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 479–493. Springer, Heidelberg (2002)

    Chapter  Google Scholar 

  4. 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)

    Chapter  Google Scholar 

  5. Bose, P., Morin, P., Stojmenović, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wireless Networks 7(6), 609–616 (2001)

    Article  MATH  Google Scholar 

  6. Chang, E.: Echo algorithms: Depth parallel operations on general graphs. IEEE Transactions on Software Engineering 8(4), 391–401 (1982)

    Article  Google Scholar 

  7. Damian, M., Pandit, S., Pemmaraju, S.: Local approximation schemes for topology control. In: PODC 2006. Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pp. 208–217. ACM Press, New York (2006)

    Chapter  Google Scholar 

  8. Dobkin, D.P., Friedman, S.J., Supowit, K.J.: Delaunay graphs are almost as good as complete graphs. Discrete and Computational Geometry 5(4), 399–407 (1990)

    MATH  MathSciNet  Google Scholar 

  9. Eppstein, D.: Spanning trees and spanners. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, ch. 9, pp. 425–461. Elsevier, Amsterdam (2000)

    Chapter  Google Scholar 

  10. Fang, Q., Gao, J., Guibas, L., Silva, V., Zhang, L.: GLIDER: Gradient landmark-based distributed routing for sensor networks. In: INFOCOM 2005. Proceedings of the 24th Conference of the IEEE Communication Society, vol. 1, pp. 339–350 (2005)

    Google Scholar 

  11. Funke, S., Milosavljević, N.: Guaranteed-delivery geographic routing under uncertain node locations. In: INFOCOM 2007. Proceedings of the 26th Annual Joint Conference of the IEEE Computer and Communications Societies (2007)

    Google Scholar 

  12. Gao, J., Guibas, L.J., Hershberger, J., Zhang, L., Zhu, A.: Geometric spanner for routing in mobile networks. In: MobiHoc 2001. Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, pp. 45–55 (2001)

    Google Scholar 

  13. Kim, Y.-J., Govindan, R., Karp, B., Shenker, S.: Lazy cross-link removal for geographic routing. In: SenSys 2006. Proceedings of the 4th international conference on Embedded networked sensor systems, pp. 112–124. ACM Press, New York (2006)

    Google Scholar 

  14. Karp, B., Kung, H.T.: GPSR: Greedy perimeter stateless routing for wireless networks. In: MobiCom 2000. Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking, pp. 243–254 (2000)

    Google Scholar 

  15. Kim, Y.-J., Govindan, R., Karp, B., Shenker, S.: On the pitfalls of geographic face routing. In: DIALM-POMC 2005. Proceedings of the 2005 joint workshop on Foundations of mobile computing, pp. 34–43. ACM Press, New York (2005)

    Chapter  Google Scholar 

  16. Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: Of theory and practice. In: PODC 2003. Proceedings of the twenty-second annual symposium on Principles of distributed computing, pp. 63–72. ACM Press, New York (2003)

    Chapter  Google Scholar 

  17. Kuhn, F., Wattenhofer, R., 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)

    Chapter  Google Scholar 

  18. Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-case optimal and average-case efficient geometric ad-hoc routing. In: MobiHoc 2003. Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, pp. 267–278. ACM Press, New York (2003)

    Chapter  Google Scholar 

  19. Li, X.-Y., Song, W.-Z., Wang, W.: A unified energy-efficient topology for unicast and broadcast. In: MobiCom 2005. Proceedings of the 11th annual international conference on Mobile computing and networking, pp. 1–15. ACM Press, New York (2005)

    Chapter  Google Scholar 

  20. Moscibroda, T., Wattenhofer, R.: Minimizing interference in ad hoc and sensor networks. In: DIALM-POMC 2005. Proceedings of the 2005 joint workshop on Foundations of mobile computing, pp. 24–33. ACM Press, New York (2005)

    Chapter  Google Scholar 

  21. Peleg, D.: Distributed computing: a locality-sensitive approach. In: Peleg, D. (ed.) Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2000)

    Google Scholar 

  22. Wang, Y., Li, X.-Y.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. In: DIALM-POMC 2003. Proceedings of the Joint Workshop on Foundations of Mobile Computing, pp. 59–68 (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Iowa, Iowa City, IA 52242-1419, USA

    Kevin M. Lillis, Sriram V. Pemmaraju & Imran A. Pirwani

  2. Computer and Information Science, St. Ambrose University, Davenport, IA 52803, USA

    Kevin M. Lillis

Authors
  1. Kevin M. Lillis
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sriram V. Pemmaraju
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Imran A. Pirwani
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Evangelos Kranakis Jaroslav Opatrny

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Lillis, K.M., Pemmaraju, S.V., Pirwani, I.A. (2007). Topology Control and Geographic Routing in Realistic Wireless Networks. In: Kranakis, E., Opatrny, J. (eds) Ad-Hoc, Mobile, and Wireless Networks. ADHOC-NOW 2007. Lecture Notes in Computer Science, vol 4686. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74823-6_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-74823-6_2

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-74822-9

  • Online ISBN: 978-3-540-74823-6

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation