Abstract
Geometric routing is a routing scheme proposed for networks with highly dynamic topology, like wireless ad hoc networks. It uses the geometric coordinates of the nodes and makes routing decisions based on the geometric properties between them. Hence, it does not build and maintain routing tables. Nevertheless, as geometric routing requires an auxiliary location service to equip nodes with geometric location, there are not much deployments in real network settings. In this chapter, we investigate an efficient localization system called Virtual Raw Anchor Coordinates (VRACs), which is an anchor-based coordinate system. It assigns the raw distances from anchors as the coordinates of nodes, hence avoiding further computations. Despite its efficiency, it is not possible to perform geometric operations on VRAC. In this manuscript, we propose alternative constructs to perform geometric routing over VRAC. Initially, a greedy routing algorithm is developed, which is then combined with a face routing strategy, when greedy routing does not guarantee delivery. Moreover, we present the conditions over which greedy routing can be performed on VRAC. In Sect. 5, a geometric routing algorithm is presented, where greedy and face routing are combined to guarantee the delivery of messages. In Sect. 6, a greedy routing algorithm is presented and proved to be successful given that certain connectivity conditions are satisfied.
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
Similar content being viewed by others
Notes
- 1.
A total order is a binary relation which is valid for all the pairs in a set.
- 2.
Given two nodes u and v, we do not assume that we can compute the distance d(u, v).
References
Perkins, C.E., Royer, E.M.: Ad-hoc on-demand distance vector routing. In: Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p. 90. IEEE Computer Society (1999)
Haas, Z.J.: A new routing protocol for the reconfigurable wireless networks. In: 1997 IEEE 6th International Conference on Universal Personal Communications Record. Conference Record, 1997, vol. 2, pp. 562–566. IEEE (1997)
Bose, P., Carmi, P., Durocher, S.: Bounding the locality of distributed routing algorithms. Distrib. Comput. 26(1), 39–58 (2013)
Bose, P., Morin, P., Stojmenović, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wirel. Netw. 7(6), 609–616 (2001)
Karp, B., Kung, H.-T.: GPSR: greedy perimeter stateless routing for wireless networks. In: Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, pp. 243–254. ACM (2000)
Santoro, N., Khatib, R.: Labelling and implicit routing in networks. The Comput. J. 28(1), 5–8 (1985)
Gnawali, O., Fonseca, R., Jamieson, K. Moss, D., Levis, P.: Collection tree protocol. In: Proceedings of the 7th ACM Conference on Embedded Networked Sensor Systems, pp. 1–14 (2009)
Li, Y., Yang, Y., Xianliang, L.: Rules of designing routing metrics for greedy, face, and combined greedy-face routing. IEEE Trans. Mob. Comput. 9(4), 582–595 (2010)
Frey, H., Stojmenovic, I.: On delivery guarantees and worst-case forwarding bounds of elementary face routing components in ad hoc and sensor networks. IEEE Trans. Comput. 59(9), 1224–1238 (2010)
Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-case optimal and average-case efficient geometric ad-hoc routing. In: Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, pp. 267–278. ACM (2003)
Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Syst. Biol. 18(3), 259–278 (1969)
Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recognit. 12(4), 261–268 (1980)
Leong, B., Liskov, B., Morris, R.: Geographic routing without planarization. In: NSDI, vol. 6, p. 25 (2006)
Fonseca, R., Ratnasamy, S., Zhao, J., Ee, C.T., Culler, D., Shenker, S., Stoica, I.: Beacon vector routing: scalable point-to-point routing in wireless sensornets. In: Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation, vol. 2, pp. 329–342. USENIX Association (2005)
Fang, Q., Gao, J., Guibas, L.J., De Silva,V., Zhang, L.: Glider: gradient landmark-based distributed routing for sensor networks. In: INFOCOM 2005. Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, pp. 339–350. IEEE (2005)
Samarasinghe, K., Leone, P.: Combinatorial approach for geographic routing with delivery guarantees. In: SENSORNETS 2014—Proceedings of the 3rd International Conference on Sensor Networks, Lisbon, Portugal, 7–9 January, 2014, pp. 195–204 (2014)
Schnyder, W.: Planar graphs and poset dimension. Order 5(4), 323–343 (1989)
Huc, F., Jarry, A., Leone, P., Rolim, J.: Efficient graph planarization in sensor networks and local routing algorithm. In: 2012 IEEE 8th International Conference on Distributed Computing in Sensor Systems (DCOSS), pp. 140–149. IEEE (2012)
Samarasinghe, K., Leone, P.: Geographic routing with minimal local geometry. In: 2012 IEEE 18th International Conference on Parallel and Distributed Systems (ICPADS), pp. 901–906. IEEE (2012)
Leone, P., Samarasinghe, K.: Greedy routing on virtual raw anchor coordinate (vrac) system. In: 2016 International Conference on Distributed Computing in Sensor Systems (DCOSS), pp. 52–58. IEEE (2016)
Dhandapani, R.: Greedy drawings of triangulations. Discret. Comput. Geom. 43(2), 375–392 (2010)
He, X., Zhang, H.: Schnyder greedy routing algorithm. In: Theory and Applications of Models of Computation, pp. 271–283. Springer (2010)
Angelini, P. Frati, F., Grilli, L.: An algorithm to construct greedy drawings of triangulations. J. Graph Algorithms Appl. 14(1), 19–51 (2010)
He, X., Zhang, H.: A simple routing algorithm based on schnyder coordinates. Theor. Comput. Sci. 494, 112–121 (2013)
Leone, P., Samarasinghe, K.: Every Schnyder Drawing is a Greedy Embedding. arXiv:1609.04173 (2016)
He, X., Zhang, H.: On succinct convex greedy drawing of 3-connected plane graphs. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1477–1486. SIAM (2011)
Wang, J.-J., He, X.: Succinct strictly convex greedy drawing of 3-connected plane graphs. Front. Algorithm. Algorithm. Asp. Inf. Manag. 13–25 (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer International Publishing AG, part of Springer Nature
About this chapter
Cite this chapter
Leone, P., Samarasinghe, K. (2019). Geometric Routing Without Coordinates but Measurements. In: Ammari, H. (eds) Mission-Oriented Sensor Networks and Systems: Art and Science. Studies in Systems, Decision and Control, vol 163. Springer, Cham. https://doi.org/10.1007/978-3-319-91146-5_16
Download citation
DOI: https://doi.org/10.1007/978-3-319-91146-5_16
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-91145-8
Online ISBN: 978-3-319-91146-5
eBook Packages: EngineeringEngineering (R0)