In various wireless networking settings, node locations determine a network’s topology, allowing the network to be modelled by a geometric graph drawn in the plane. Without any additional information, local geometric routing algorithms can guarantee delivery to the target node only in restricted classes of geometric graphs, such as triangulations. In order to guarantee delivery on more general classes of geometric graphs (e.g., convex subdivisions or planar subdivisions), previous local geometric routing algorithms required $Θ (log n)$ state bits to be stored and passed with the message. We present the first local geometric routing algorithm using only one state bit to guarantee delivery on convex subdivisions and, when the algorithm has knowledge of the incoming port (the preceding node on the route), the first stateless local geometric routing algorithm that guarantees delivery on edge-augmented monotone subdivisions (including all convex subdivisions). We also show that $Ω (log n)$ state bits are necessary in planar subdivisions in which faces may have three or more reflex vertices.

Communicated by Joe Mitchell

Keywords:

References

1. M. de Berg, M. van Kreveld, R. van Oostrum and M. Overmars , Simple traversal of a subdivision without extra storage, Int. J. Geog. Inf. Sci. 11(4) (1997) 359–373. Crossref, ISI, Google Scholar
2. P. Bose, A. Brodnik, S. Carlsson, E. D. Demaine, R. Fleischer, A. López-Ortiz, P. Morin and I. Munro , Online routing in convex subdivisions, Int. J. Comp. Geom. & Appl. 12(4) (2002) 283–295. Link, Google Scholar
3. P. Bose, P. Carmi and S. Durocher , Bounding the locality of distributed routing algorithms, Dist. Comp. 26(1) (2013) 39–58. Crossref, ISI, Google Scholar
4. P. Bose, S. Durocher, D. Mondal, M. Peabody, M. Skala and M. A. Wahid , Local routing in convex subdivisions, in Proc. SOFSEM, Vol. 8939 (LNCS, Springer, 2015), pp. 140–151. Crossref, Google Scholar
5. P. Bose and P. Morin , An improved algorithm for subdivision traversal without extra storage, Int. J. Comp. Geom. & Appl. 12(4) (2002) 297–308. Link, ISI, Google Scholar
6. P. Bose and P. Morin , Competitive online routing in geometric graphs, Theor. Comp. Sci. 324 (2004) 273–288. Crossref, ISI, Google Scholar
7. P. Bose and P. Morin , Online routing in triangulations, SIAM J. Comp. 33(4) (2004) 937–951. Crossref, ISI, Google Scholar
8. P. Bose, P. Morin, I. Stojmenović and J. Urrutia , Routing with guaranteed delivery in ad hoc wireless networks, Wireless Net. 7(6) (2001) 609–616. Crossref, ISI, Google Scholar
9. M. Braverman , On ad hoc routing with guaranteed delivery, in Proc. ACM PODC, Vol. 27 (2008), p. 418. Crossref, Google Scholar
10. E. Chavez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho and J. Urrutia , Traversal of a quasi-planar subdivision without using mark bits, J. Interconn. Net. 5(4) (2004) 395–408. Link, Google Scholar
11. D. Chen, L. Devroye, V. Dujmović and P. Morin , Memoryless routing in convex subdivisions: Random walks are optimal, Comp. Geom.: Theory & Appl. 45(4) (2012) 178–185. Crossref, ISI, Google Scholar
12. S. Durocher, D. Kirkpatrick and L. Narayanan , On routing with guaranteed delivery in three-dimensional ad hoc wireless networks, Wireless Net. 16 (2010) 227–235. Crossref, ISI, Google Scholar
13. G. G. Finn, Routing and addressing problems in large metropolitan-scale internetworks, Technical Report ISI/RR-87-180 (Information Sciences Institute, 1987). Google Scholar
14. H. Frey, S. Ruehrup and I. Stojmenovic , Routing in wireless sensor networks, In S. MisraI. WoungagS. Misra, editors, Guide to Wireless Ad Hoc Networks, Chap. 4 (Springer-Verlag, 2009), pp. 81–111. Google Scholar
15. X. Guan, Face Routing in Wireless ad-hoc Networks (PhD thesis, Univ. Toronto, 2009). Google Scholar
16. E. Kranakis, H. Singh and J. Urrutia , Compass routing on geometric networks, in Proc. CCCG, Vol. 11 (1999), pp. 51–54. Google Scholar
17. F. Kuhn, R. Wattenhofer and A. Zollinger , Ad hoc networks beyond unit disk graphs, Wireless Networks 14(5) (2008) 715–729. Crossref, ISI, Google Scholar
18. P. Morin, Online Routing in Geometric Graphs, (PhD thesis, Carleton Univ., 2001). Google Scholar
19. J. Urrutia , Handbook wireless net. & mob. comp, in I. Stojmenovic, editor, Routing with Guaranteed Delivery in Geometric and Wireless Networks (John Wiley & Sons, Inc., 2002), pp. 393–406. Google Scholar
20. M. A. Wahid, Local geometric routing algorithms for edge-augmented planar graphs, (Master’s thesis, Univ. Manitoba, 2013). Google Scholar

Remember to check out the Most Cited Articles!
Check out these titles in image analysis!

Vol. 30, No. 01

Metrics

History

Received 8 June 2015

Accepted 12 June 2020

Published: 31 August 2020

Keywords

PDF download

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Local Routing in Convex Subdivisions

Abstract

References

Recommended