×

Geographic routing on virtual raw anchor coordinate systems. (English) Zbl 1335.68184

Summary: In this manuscript, we present geographic routing algorithms with delivery guarantees on a virtual coordinate system, namely Virtual Raw Anchor Coordinates (VRAC). Proposed algorithms can be seen as a variant of GFG (Greedy Face Greedy of P. Bose et al. [Wirel. Netw. 7, No. 6, 609–616 (2001; Zbl 0996.68012)]) algorithm and based on combinatorial and geometric properties derived in the Virtual Raw Anchor Coordinate system. We utilize a local planarization algorithm of a geometric graph, which is based on the Schnyder’s characterization of planar graphs. The new approach is combinatorial in the sense that the nodes are ordered with respect to three distinct order relations satisfying suitable properties. The coordinate system that motivated the development of this routing algorithm is VRAC, which localizes the nodes with the raw distances from three fixed anchors. Since the positions of the anchors are not known, the VRAC coordinate system does not correspond to the Euclidean location of nodes, yet leaving sufficient information to define necessary combinatorial and geometric constructs for routing with guaranteed delivery. In particular, the routing algorithm avoids the references to geographical arguments and makes use only of the order relations on the nodes. We expect that our approach will foster further research on building efficient order relations, that will prove to be useful in practical implementation of geographic routing algorithms. In particular, we expect that further work will prove that the geographic routing based on a raw anchor based positioning system is more robust in the presence of distance measurement errors.

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C62 Graph representations (geometric and intersection representations, etc.)
05C85 Graph algorithms (graph-theoretic aspects)
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Citations:

Zbl 0996.68012
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Karp, B.; Kung, H.-T., GPSR: greedy perimeter stateless routing for wireless networks, (Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (2000), ACM), 243-254
[2] Bose, P.; Morin, P.; Stojmenović, I.; Urrutia, J., Routing with guaranteed delivery in ad hoc wireless Networks, Wirel. Netw., 7, 6, 609-616 (2001) · Zbl 0996.68012
[3] Perkins, C. E.; Royer, E. M., Ad-hoc on-demand distance vector routing, (Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, vol. 90 (1999), IEEE Computer Society)
[4] Huc, F.; Jarry, A.; Leone, P.; Rolim, J., On the efficiency of routing in sensor networks, J. Parallel Distrib. Comput., 72, 7, 889-901 (2012) · Zbl 1248.68063
[5] 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) · Zbl 1368.68040
[6] Rao, A.; Ratnasamy, S.; Papadimitriou, C.; Shenker, S.; Stoica, I., Geographic routing without location information, (Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (2003), ACM), 96-108
[7] Priyantha, N. B.; Balakrishnan, H.; Demaine, E.; Teller, S., Anchor-free distributed localization in sensor networks, (Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (2003), ACM), 340-341
[8] Leone, P.; Schiller, E. M., Interacting urns processes for clustering of large-scale networks of tiny artifacts, Int. J. Distrib. Sens. Netw. (2010)
[9] 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, (Proceedings of the 2nd Conference on Symposium on Networked Systems Design & Implementation, vol. 2 (2005), USENIX Association), 329-342
[10] Fang, Q.; Gao, J.; Guibas, L. J.; De Silva, V.; Zhang, L., GLIDER: gradient landmark-based distributed routing for sensor networks, (Proceedings of IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1. Proceedings of IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, INFOCOM 2005 (2005), IEEE), 339-350
[11] Huc, F.; Jarry, A.; Leone, P.; Rolim, J., Virtual raw anchor coordinates: a new localization paradigm, Theoret. Comput. Sci., 453, 44-53 (2012) · Zbl 1252.68038
[12] Huc, F.; Jarry, A.; Leone, P.; Rolim, J., Efficient graph planarization in sensor networks and local routing algorithm, (2012 IEEE 8th International Conference on Distributed Computing in Sensor Systems. 2012 IEEE 8th International Conference on Distributed Computing in Sensor Systems, DCOSS (2012), IEEE), 140-149
[13] He, X.; Zhang, H., A simple routing algorithm based on Schnyder coordinates, Theoret. Comput. Sci., 494, 112-121 (2013) · Zbl 1294.68036
[14] Schnyder, W., Planar graphs and poset dimension, Order, 5, 4, 323-343 (1989) · Zbl 0675.06001
[15] Li, Y.; Yang, Y.; Lu, X., Rules of designing routing metrics for greedy, face, and combined greedy-face routing, IEEE Trans. Mob. Comput., 9, 4, 582-595 (2010)
[16] Samarasinghe, K.; Leone, P., Combinatorial approach for geographic routing with delivery guarantees, (Proceedings of the 3rd International Conference on Sensor Networks. Proceedings of the 3rd International Conference on Sensor Networks, SENSORNETS 2014, Lisbon, Portugal, 7-9 January, 2014 (2014)), 195-204
[17] Samarasinghe, K.; Leone, P., Geographic routing with minimal local geometry, (2012 IEEE 18th International Conference on Parallel and Distributed Systems. 2012 IEEE 18th International Conference on Parallel and Distributed Systems, ICPADS (2012), IEEE), 901-906
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.