Abstract
Location-based routing techniques, greedy routing and face routing, route data by using the location information of wireless nodes. Greedy routing efficiently routes data in dense networks by giving short hop paths, but it does not guarantee message delivery. Face routing has been designed and combined with greedy routing to achieve both transmission efficiency and guaranteed message delivery. The existing face routing algorithms mainly works on three types of planar graphs: Gabriel graph, relative neighborhood graph, and Delaunay triangulation. One major observation is that each transmission in face routing only can pass message over a short distance, resulting in that the existing face routing traverses long hop paths to destinations. In this paper, we present a Skip Face Routing (SFR) to reduce the face traversal cost incurred in the existing approaches. By using simulation studies, we show that SFR significantly increases routing performance.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kleinrock, L., Silvester, J.: Optimum Transmission Radii for Packet Radio Networks or why Six is a Magic Number. In: Conference Record, National Telecommunications Conference, December 1978, pp. 432–435 (1978)
Finn, G.G.: Routing and Addressing Problems in Large Metropolitan-scale Internetworks. ISI Research Report ISU/RR-87-180 (1987)
Kranakis, E., Singh, H., Urrutia, J.: Compass Routing on Geometric Networks. In: Proc. Canadian Conference on Computational Geometry, Vancouver (August 1999)
Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with Guaranteed Delivery in Ad Hoc Wireless Networks. In: Proc. ACM Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications DIAL M99, pp. 48–55 (1999)
Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with Guaranteed Delivery in Ad Hoc Wireless Networks. ACM Wireless Networks 7(6), 609–616 (2001)
Karp, B., Kung, H.T.: GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In: Proc. ACM/IEEE MOBICOM, August 2000, pp. 243–254 (2000)
Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically Optimal Geometric Mobile Ad-Hoc Routing. In: Proc. Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, pp. 24–33. ACM Press, New York (2002)
Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing. In: Proc. MobiHoc (2003)
Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric Ad-hoc Routing: Of Theory and Practice. In: Proc. PODC (2003)
Al-Karaki, J.N., Kamal, A.E.: Routing Techniques in Wireless Sensor Networks: A Survey. IEEE Wireless Communication 11(6), 6–28 (2004)
Liu, J.: A Distributed Routing Algorithm in Mobile Packet Radio Networks. University of Illinois, Urbana, TR (1980)
Nelson, R., Kleinrock, L.: The Spatial Capacity of a Slotted ALOHA Miltihop Packet Radio Network with Capture. IEEE TON 32(6), 649–684 (1984)
Takagi, H., Kleinrock, L.: Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals. IEEE TON 32(3), 246–257 (1984)
Zorzi, M., Rao, R.R.: Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Multi-hop Performance. IEEE TMC 2(4), 337–348 (2003)
Stojmenovic, I.: Geocasting with Guaranteed Delivery in Sensor Networks. IEEE Wireless Communications 11(6), 29–37 (2004)
Li, X., Calinescu, G., Wan, P., Wang, Y.: Localized Delaunay Triangulation with Applications in Ad Hoc Wireless Networks. IEEE TPDS 14, 1035–1047 (2003)
Calinescu, G.: Computing 2-hop neighborhoods in ad hoc wireless networks. In: Pierre, S., Barbeau, M., Kranakis, E. (eds.) ADHOC-NOW 2003. LNCS, vol. 2865, pp. 175–186. Springer, Heidelberg (2003)
Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Springer, Heidelberg (1985)
Lian, J., Naik, K., Agnew, G.: Data Capacity Improvement of Wireless Sensor Networks Using Non-Uniform Sensor Distribution. International Journal of Distributed Sensor Networks (2005)
Giordano, S., Stojmenovic, I.: Position Based Routing Algorithms for Ad Hoc Networks: A Taxonomy. In: Ad Hoc Wireless Networking, pp. 103–136. Kluwer, Dordrecht (2004)
Liu, Y., Xiao, L., Liu, X., Ni, L.M., Zhang, X.: Location Awareness in Unstructured Peer-to-Peer Systems. IEEE TPDS 16(2), 163–174 (2005)
Datta, S., Stojmenovic, I., Wu, J.: Internal node and shortcut based routing with guaranteed delivery in wireless networks. Cluster Computing 5(2), 169–178 (2002)
Ni, L.M., Liu, Y., Lau, Y., Patil, A.: LANDMARC: Indoor Location Sensing Using Active RFID. ACM Wireless Networks 10(6), 701–710 (2004)
Boone, P., Chávez, E., Gleitzky, L., Kranakis, E., Opatrny, J., Salazar, G., Urrutia, J.: Morelia Test: Improving the Efficiency of the Gabriel Test and Face Routing in Ad-Hoc Networks. In: Kralovic, R., Sýkora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 23–34. Springer, Heidelberg (2004)
Xue, W., Luo, Q., Chen, L., Liu, Y.: Contour Map Matching For Event Detection in Sensor Networks. In: Proc. ACM SIGMOD (June 2006)
Wu, J., Li, H.: On calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks. Telecommunication Systems 18(1-3), 13–36 (2001)
Stojmenovic, Seddigh, M., Zunic, J.: Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks. IEEE TPDS 13(1), 14–25 (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lian, J., Naik, K. (2006). Skipping Face Routing with Guaranteed Message Delivery for Wireless Ad Hoc and Sensor Networks. In: Cao, J., Stojmenovic, I., Jia, X., Das, S.K. (eds) Mobile Ad-hoc and Sensor Networks. MSN 2006. Lecture Notes in Computer Science, vol 4325. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11943952_5
Download citation
DOI: https://doi.org/10.1007/11943952_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49932-9
Online ISBN: 978-3-540-49933-6
eBook Packages: Computer ScienceComputer Science (R0)