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. Web of Science, 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, Web of Science, Google Scholar
3. P. Bose, P. Carmi and S. Durocher , Bounding the locality of distributed routing algorithms, Dist. Comp. 26(1) (2013) 39–58. Web of Science, 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. 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, Web of Science, Google Scholar
6. P. Bose and P. Morin , Competitive online routing in geometric graphs, Theor. Comp. Sci. 324 (2004) 273–288. Web of Science, Google Scholar
7. P. Bose and P. Morin , Online routing in triangulations, SIAM J. Comp. 33(4) (2004) 937–951. Web of Science, 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. Web of Science, Google Scholar
9. M. Braverman , On ad hoc routing with guaranteed delivery, in Proc. ACM PODC, Vol. 27 (2008), p. 418. 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. Web of Science, 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. Web of Science, 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. Misra, I. Woungag, and S. 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. Web of Science, 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