Fabian Kuhn
ABSTRACT
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we consider two aspects: We propose a new geometric routing algorithm which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal. On the other hand we are able to drop the formerly necessary assumption that the distance between network nodes may not fall below a constant value, an assumption that cannot be maintained for practical networks. Abandoning this assumption we identify from a theoretical point of view two fundamentamentally different classes of cost metrics for routing in ad-hoc networks.
- {1} K. Alzoubi, P.-J. Wan, and O. Frieder. Message-Optimal Connected Dominating Sets in Mobile Ad Hoc Networks. In Proc. ACM Int. Symposium on Mobile ad hoc networking & computing (MobiHoc), 2002. Google Scholar
Digital Library
- {2} P. Bose, A. Brodnik, S. Carlsson, E. D. Demaine, R. Fleischer, A. López-Ortiz, P. Morin, and J. I. Munro. Online Routing in Convex Subdivisions. In International Symposium on Algorithms and Computation (ISAAC), volume 1969 of Lecture Notes in Computer Science, pages 47-59. Springer, 2000.Google Scholar
- {3} P. Bose and P. Morin. Online Routing in Triangulations. In Proc. 10th Int. Symposium on Algorithms and Computation (ISAAC), volume 1741 of Springer LNCS, pages 113-122, 1999.Google ScholarDigital Library
- {4} P. Bose, P. Morin, I. Stojmenovic, and J. Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. In Proc. Discrete Algorithms and Methods for Mobility (Dial-M), pages 48-55, 1999. Google ScholarDigital Library
- {5} C. Chiang, H. Wu, W. Liu, and M. Gerla. Routing in Clustered Multihop, Mobile Wireless Networks. In Proc. IEEE Singapore Int. Conf. on Networks, pages 197-211, 1997.Google Scholar
- {6} S. Datta, I. Stojmenovic, and J. Wu. Internal Node and Shortcut Based Routing with Guaranteed Delivery in Wireless Networks. In Cluster Computing 5, pages 169-178. Kluwer Academic Publishers, 2002. Google ScholarDigital Library
- {7} P. G. Doyle and J. L. Snell. Random Walks and Electric Networks. The Carus Mathematical Monographs. The Mathematical Association of America, 1984.Google ScholarCross Ref
- {8} G. G. Finn. Routing and Addressing Problems in Large Metropolitan-scale Internetworks. Technical Report ISI/RR-87-180, USC/ISI, March 1987.Google ScholarCross Ref
- {9} J. Gao, L. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Discrete Mobile Centers. In Proc. 17th Annual Symposium on Computational Geometry (SCG), pages 188-196. ACM Press, 2001. Google ScholarDigital Library
- {10} J. Gao, L. Guibas, J. Hershberger, L. Zhang, and A. Zhu. Geometric Spanner for Routing in Mobile Networks. In Proc. ACM Int. Symposium on Mobile ad hoc networking & computing (MobiHoc), 2001. Google ScholarDigital Library
- {11} S. Guha and S. Khuller. Approximation Algorithms for Connected Dominating Sets. In J. Díaz and M. Serna, editors, Algorithms--ESA '96, Fourth Annual European Symposium, volume 1136 of Lecture Notes in Computer Science, pages 179-193. Springer, 1996. Google ScholarDigital Library
- {12} T. C. Hou and V. O. K. Li. Transmission Range Control in Multihop Packet Radio Networks. IEEE Transactions on Communications, 34(1):38-44, 1986.Google Scholar
- {13} H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz, and R. E. Stearns. NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. J. Algorithms, 26(2):238-274, 1998. Google ScholarDigital Library
- {14} D. B. Johnson and D. A. Maltz. Dynamic Source Routing in Ad Hoc Wireless Networks. In T. Imielinski and H. Korth, editors, Mobile Computing, chapter 5, pages 153-181. Kluwer Academic Publishers, 1996.Google ScholarCross Ref
- {15} B. Karp and H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proc. 6th Annual Int. Conf. on Mobile Computing and Networking (MobiCom), pages 243-254, 2000. Google ScholarDigital Library
- {16} Y. Ko and N. Vaidya. Geocasting in Mobile Ad Hoc Networks: Location-Based Multicast Algorithms. In Proc. 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA), 1999. Google ScholarDigital Library
- {17} E. Kranakis, H. Singh, and J. Urrutia. Compass Routing on Geometric Networks. In Proc. 11th Canadian Conference on Computational Geometry, pages 51-54, 1999.Google Scholar
- {18} P. Krishna, M. Chatterjee, N. H. Vaidya, and D. K. Pradhan. A Cluster-based Approach for Routing in Ad-Hoc Networks. In Proc. 2nd USENIX Symposium on Mobile and Location-Independent Computing, pages 1-10, 1995. Google ScholarDigital Library
- {19} F. Kuhn, R. Wattenhofer, and A. Zollinger. Asymptotically Optimal Geometric Mobile Ad-Hoc Routing. In Proc. 6th Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (Dial-M), pages 24-33. ACM Press, 2002. Google ScholarDigital Library
- {20} F. Kuhn, R. Wattenhofer, and A. Zollinger. Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing. In Proc. 4th ACM Int. Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc), 2003. Google ScholarDigital Library
- {21} M. Mauve, J. Widmer, and H. Hartenstein. A Survey on Position-Based Routing in Mobile Ad-Hoc Networks. IEEE Network, 15(6), 2001. Google ScholarDigital Library
- {22} J. C. Navas and T. Imielinski. GeoCast - Geographic Addressing and Routing. In Proc. Int. Conf. on Mobile Computing and Networking (MobiCom), pages 66-76, 1997. Google ScholarDigital Library
- {23} H. Takagi and L. Kleinrock. Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals. IEEE Transactions on Communications, 32(3):246-257, 1984.Google ScholarCross Ref
- {24} J. Urrutia. Routing with Guaranteed Delivery in Geometric and Wireless Networks. In I. Stojmenovic, editor, Handbook of Wireless Networks and Mobile Computing, chapter 18, pages 393-406. John Wiley & Sons, 2002. Google ScholarDigital Library
- {25} Y. Wang and X.-Y. Li. Geometric Spanners for Wireless Ad Hoc Networks. In Proc. 22nd International Conference on Distributed Computing Systems (ICDCS), 2002. Google ScholarDigital Library
- {26} J. Wu. Dominating-Set-Based Routing in Ad Hoc Wireless Networks. In I. Stojmenovic, editor, Handbook of Wireless Networks and Mobile Computing, chapter 20, pages 425-450. John Wiley & Sons, 2002. Google ScholarDigital Library
- {27} Y. Xue, B. Li, and K. Nahrstedt. A Scalable Location Management Scheme in Mobile Ad-hoc Networks. In Proc. IEEE Conference on Local Computer Networks (LCN), 2001. Google ScholarDigital Library
Index Terms
- Geometric ad-hoc routing: of theory and practice
Recommendations
Worst-Case optimal and average-case efficient geometric ad-hoc routing
MobiHoc '03: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computingIn this paper we present GOAFR, a new geometric ad-hoc routing algorithm combining greedy and face routing. We evaluate this algorithm by both rigorous analysis and comprehensive simulation. GOAFR is the first ad-hoc algorithm to be both asymptotically ...
Asymptotically optimal geometric mobile ad-hoc routing
DIALM '02: Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communicationsIn this paper we present AFR, a new geometric mobile ad-hoc routing algorithm. The algorithm is completely distributed; nodes need to communicate only with direct neighbors in their transmission range. We show that if a best route has cost c, AFR finds ...
Self-Adaptive On-Demand Geographic Routing for Mobile Ad Hoc Networks
It has been a big challenge to develop a routing protocol that can meet different application needs and optimize routing paths according to the topology changes in mobile ad hoc networks. Basing their forwarding decisions only on local topology, ...
Comments