Geographic Routing

for Wireless Networks

 

 

Home
Overview
Status
Funding
People
Simulator
Publications
Related Work

Geographic Routing

  1. Evangelos Kranakis, Harvinder Singh and Jorge Urrutia, Compass routing on geometric networks, Proc. 11 th Canadian Conference on Computational Geometry, Vancouver, August, 1999.

  2. Prosenjit Bose, Pat Morin, Ivan Stojmenovic, and Jorge Urrutia. Routing with Guaranteed Delivery in Ad Hoc Wireless Networks. Wireless Networks, 7(6):609–616, 2001.

  3. Brad Karp. Geographic Routing for Wireless Networks. PhD thesis, 2000.

  4. Brad Karp and H. T. Kung. GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. In Proceedings of Mobicom 2000, pages 243–254, Boston, MA, August 2000.

  5. Fabian Kuhn, Roger Wattenhofer, Yan Zhang, and Aaron Zollinger. Geometric ad-hoc routing: Of theory and practice. In Proceedings of PODC 2003, July 2003.

  6. Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger. Worst-Case Optimal and Average-Case Efficient Geometric Ad-Hoc Routing. In Proceedings of 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2003), June 2003.

  7. Fabian Kuhn and Aaron Zollinger. Ad-hoc networks beyond unit disk graphs. In Proceedings of the 2003 joint workshop on Foundations of mobile computing (DIALM-POMC ’03), pages 69-78, 2003

  8. Ramakrishna Gummadi, Nupur Kothari, Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker. Reduced-state routing in the internet. In Proceedings of the Third ACM SIGCOMM Workshop on Hot Topics in Networks (HotNets 2004), November 2004.

  9. Yong-Jin Kim, Jae-Joon Lee, and Ahmed Helmy. Modeling and analyzing the impact of location inconsistencies on geographic routing in wireless networks. Mobile Computing and Communications Review, 8(1):4860, 2004.

  10. Karim Seada, Ahmed Helmy, and Ramesh Govindan. On the effect of localization errors on geographic face routing in sensor networks. In Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks (IPSN’04), pages 7180, 2004.

  11. Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker. Practical and robust geographic routing in wireless networks. Technical Report 04-832, University of Southern California, 2004

  12. Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker. Geographic routing made practical. In Proceedings of NSDI 2005, May 2005.

  13. Ben Leong, Sayan Mitra, and Barbara Liskov, "Path Vector Face Routing: Geographic Routing with Local Face Information". Proceedings of the 13th IEEE International Conference on Network Protocols (ICNP 2005). Boston, MA, November 2005.

  14. Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker. On the Pitfalls of Geographic Routing. Proceedings of the 3rd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM) -Principles of Mobile Computing, September 2005.

  15. Ben Leong, Barbara Liskov, and Robert Morris, "Geographic Routing without Planarization". Proceedings of the 3rd Symposium on Network Systems Design and Implementation (NSDI 2006). San Jose, CA, May 2006.

  16. Hannes Frey and Ivan Stojmenovic. On Delivery Guarantees of Face and Combined Greedy-Face Routing in Ad Hoc and Sensor Networks. In Proceedings of Mobicom 2006, Los Angeles, CA, September 2006.

  17. Young-Jin Kim, Ramesh Govindan, Brad Karp, Scott Shenker. Lazy Cross-Link Removal for Geographic Routing. In Proceedings of the ACM Conference on Embedded Networked Sensor Systems (Sensys '06), November 2006.

  18. Jonathan Ledlie, Peter Pietzuch, Michael Mitzenmacher, and Margo Seltzer, Wired Geometric Routing, In Proceedings of IPTPS 2007, Bellevue, WA, February 2007

Geometric Routing (Theoretical Work)

  1. Prosenjit Bose and Pat Morin. Online routing in triangulations. In ISAAC: 10th International Symposium on Algorithms and Computation (formerly SIGAL International Symposium on Algorithms)), 1999.

  2. Prosenjit Bose, Pat Morin, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, J. Ian Munro, and Alejandro Lopez-Ortiz. Online routing in convex subdivisions. In International Symposium on Algorithms and Computation, pages 4759, 2000.

  3. Prosenjit Bose and Pat Morin. Competitive online routing in geometric graphs. In Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2001), 2001.

  4. Jie Gao, Leonidas J. Guibas, John Hershberger, Li Zhang, and An Zhu. Geometric spanner for routing in mobile networks. In Proceedings of the 2001 ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2001), pages 4555, July 2001.

  5. Xiang-Yang Li, Gruia Calinescu, and Peng-Jun Wan. Distributed construction of planar spanner and routing for ad hoc wireless networks. In Proceedings of IEEE Infocom ’02, June 2002.

  6. Khaled Alzoubi, Xiang-Yang Li, Yu Wang, Peng-Jun Wan, and Ophir Frieder. Geometric spanners for wireless ad hoc networks. IEEE Transactions on Parallel and Distributed Systems, 14(5), May 2003

  7. Roger Wattenhofer and Aaron Zollinger. XTC: A practical topology control algorithm for ad-hoc networks. In Proceedings of the of the 18th International Parallel and Distributed Processing Symposium (IPDPS’04), 2004.

  8. Edgar Chavez, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, and Jorge Urrutia. Traversal of a quasi-planar subdivision without using mark bits. Journal of Interconnection Networks, 5(4):395408, 2004.

  9. Christos H. Papadimitriou and David Ratajczak. On a conjecture related to geometric routing. In Proceedings of ALGOSENSORS 2004, pages 917, July 2004.

  10. Guoliang Xing, Chenyang Lu, Robert Pless, and Qingfeng Huang. On greedy geographic routing algorithms in sensing-covered networks. In Proceedings of the 5th ACM International Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc 2004), pages 31-42, 2004.

Virtual Coordinate Algorithms

  1. T. S. Eugene Ng and Hui Zhang. Towards global network positioning. In Proceedings of IEEE Infocom ’02, June 2002.

  2. Radhika Nagpal, Howard Shrobe, and Jonathan Bachrach. Organizing a global coordinate system from local information on an amorphous computer. In Proceedings of the 2nd International Workshop on Information Processing in Sensor Networks (IPSN’03), April 2003.

  3. Yuval Shavitt and Tomer Tankel. Big-bang simulation for embedding network distances in Euclidean space. In Proceedings of the IEEE Infocomm, April 2003.

  4. Ananth Rao, Christos H. Papadimitriou, Scott Shenker, and Ion Stoica. Geographic routing without location information. In Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom ’03), pages 96-108, San Diego, CA, September 2003.

  5. Frank Dabek, Russ Cox, Frans Kaashoek, and Robert Morris. Vivaldi: A decentralized network coordinate system. In Proceedings of the ACM SIGCOMM ’04 Conference, Portland, Oregon, August 2004.

  6. Antonio Caruso, Stefano Chessa, Swades De, and Alessandro Urpi. GPS free coordinate assignment and routing in wireless sensor networks. In Proceedings of IEEE Infocom ’05, pages 150-160, March 2005.

  7. Noa Arad and Yuval Shavitt. Minimizing recovery state in geographic ad hoc routing. In Proceedings of the seventh ACM international symposium on Mobile ad hoc networking and computing (MobiHoc 2006), May 2006.

Related Work in Sensor Networks

  1. Jinyang Li, John Jannotti, Douglas S. J. De Couto, David R. Karger, and Robert Morris. A scalable location service for geographic ad hoc routing. In Proceedings of the 6th ACM International Conference on Mobile Computing and Networking (MobiCom ’00), pages 120-130, 2000.

  2. Sylvia Ratnasamy, Brad Karp, Li Yin, Fang Yu, Deborah Estrin, Ramesh Govindan, and Scott Shenker. GHT: A geographic hash table for data-centric storage in sensornets. In Proceedings of the First ACM International Workshop on Wireless Sensor Networks and Applications (WSNA), September 2002.

  3. James Newsome and Dawn Song. GEM: Graph EMbedding for routing and data-centric storage in sensor networks without geographic information. In Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys’03), November 2003.

  4. Jerry Zhao and Ramesh Govindan. Understanding packet delivery performance in dense wireless sensor networks. In Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys’03), pages 113, 2003

  5. Qing Fang, Jie Gao, and Leonidas J. Guibas. Locating and bypassing routing holes in sensor networks. In Proceedings of IEEE Infocom ’04, March 2004.

  6. Qing Fang, Jie Gao, Leonidas J. Guibas, Vin de Silva, and Li Zhang. GLIDER: Gradient landmark-based distributed routing for sensor networks. In Proceedings of IEEE Infocom ’05, March 2005.

  7. Rodrigo Fonseca, Sylvia Ratnasamy, Jerry Zhao, Cheng Tien Ee, David Culler, Scott Shenker, and Ion Stoica. Beacon Vector Routing: Scalable point-to-point routing in wireless sensornets. In Proceedings of the 2nd Symposium on Networked Systems Design and Implementation (NSDI 2005), May 2005.

  8. Yao Zhao, Bo Li, Qian Zhang, Yan Chen, and Wenwu Zhu. Hop ID based routing in mobile ad hoc networks. In Proceedings of the 13th IEEE International Conference on Network Protocols (ICNP 2005), pages 179190, November 2005.

  9. Cheng Tien Ee, Sylvia Ratnasamy, and Scott Shenker. Practical data-centric storage. In Proceedings of the 3rd Symposium on Networked Systems Design and Implementation (NSDI 2006), May 2006.

  10. Matthew Caesar, Miguel Castro, Edmund B. Nightingale, Gerg O, and Antony Rowstron. Virtual Ring Routing: Network Routing Inspired by DHTs. In Proceedings of Sigcomm Conference 2006, September 2006. Pisa, Italy.

Ad Hoc Routing Algorithms

  1. Gregory G. Finn. Routing and addressing problems in large metropolitan-scale internetworks. Technical Report ISI/RR-87-180, ISI, March 1987.

  2. Charles Perkins and Pravin Bhagwat. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. In Proceedings of ACM SIGCOMM’94 Conference, pages 234-244, August 1994.

  3. David B Johnson and David A Maltz. Dynamic source routing in ad hoc wireless networks. In Mobile Computing, volume 353. 1996.

  4. Tomasz Imielinski and Julio C. Navas. GPS-based addressing and routing, November 1996. RFC 2009.

  5. Vincent D. Park and M. Scott Corson. A highly adaptive distributed routing algorithm for mobile wireless networks. In Proceedings of IEEE Infocom ’97, pages 14051413, 1997.

  6. Charles Perkins. Ad-hoc on-demand distance vector routing. In Proceedings of IEEE Military Communications Conference (MILCOM ’97), November 1997.

  7. Zygmunt J. Haas. A routing protocol for the recongurable wireless networks. In Proceedings of IEEE International Conference on Universal Personal Communications (ICUPC’97), volume 2, pages 562-566, 1997.

  8. Zygmunt J. Haas and Marc R. Pearlman. The performance of query control schemes for the zone routing protocol. In Proceedings of ACM SIGCOMM Conference 1998, pages 167-177, August 1998.

  9. Stefano Basagni, Imrich Chlamtac, Violet R. Syrotiuk, and Barry A. Woodward. A distance routing effect algorithm for mobility (DREAM). In Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking (MobiCom ’98), pages 76-84, New York, NY, USA, 1998. ACM Press.

  10. Young-Bae Ko and Nitin H. Vaidya. Location-aided routing (LAR) in mobile ad hoc networks. In Proceedings of the 4th ACM International Conference on Mobile Computing and Networking (MobiCom ’98), pages 66-75, October 1998.

  11. Charles E. Perkins and Elizabeth M. Royer. Ad hoc On-Demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, February 1999, pp. 90-100.

  12. Philippe Jacquet, Paul Muhlethaler, Thomas Clausen, Anis Laouiti, Amir Qayyum, and Laurent Viennot. Optimized link state routing protocol for ad hoc networks. In Proceedings of the 5th IEEE Multi Topic Conference (INMIC 2001), 2001.

  13. Martin Mauve, Jorg Widmer, and Hannes Hartenstein. A survey on position-based routing in mobile ad hoc networks. IEEE Network Magazines, 15(6), November 2001.

  14. Philippe Jacquet, Paul Muhlethaler, and Amir Qayyum. Optimized link state routing protocol, October 2003. RFC 3626.

  15. Douglas S. J. De Couto and Robert Morris. Location proxies and intermediate node forwarding for practical geographic forwarding. Technical report, MIT, 2001.

  16. Kwan-Wu Chin, John Judge, Aidan Williams, and Roger Kermode. Implementation experience with MANET routing protocols. SIGCOMM Computer Communications Review, 32(5):49–59, 2002.

  17. Silvia Giordano and Ivan Stojmenovic. Position based routing algorithms for ad hoc networks: A taxonomy. Ad Hoc Wireless Networking, pages 103-136, 2004.

Network Localization

  1. Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine, and Seth Teller. Anchor-free distributed localization in sensor networks. Technical Report LCS 892, MIT, March 2000.

  2. Nissanka B. Priyantha, Allen Miu, Hari Balakrishnan, and Seth Teller. The cricket compass for context-aware mobile applications. In Proceedings of the 7th ACM International Conference on Mobile Computing and Networking (MobiCom ’01), July 2001.

  3. Chris Savarese, Jan M. Rabaey, and Jan Beutel. Locationing in distributed ad-hoc wireless sensor networks. In Proceedings of IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2001), pages 2037-2040, May 2001.

  4. Andreas Savvides, Chih-Chieh Han, and Mani B. Strivastava. Dynamic ne-grained localization in ad-hoc networks of sensors. In Proceedings of the 7th ACM International Conference on Mobile Computing and Networking (MobiCom ’01), pages 166179, 2001.

  5. Lance Doherty, Kristofer S. J. Pister, and Laurent El Ghaoui. Convex position estimation in wireless sensor networks. In Proceedings of IEEE Infocom ’01, pages 1655-1663, 2001.

  6. Chris Savarese, Jan Rabay, and Koen Langendoen. Robust positioning algorithms for distributed ad-hoc wireless sensor networks. In Proceedings of the USENIX Technical Annual Conference, June 2002.

  7. Dragos Niculescu and Badri Nath. Ad hoc positioning system (APS) using angle of arrival (AoA). In Proceedings of IEEE Infocom ’03, March 2003.

  8. David Moore, John Leonard, Daniela Rus, and Seth Teller. Robust distributed network localization with noisy range measurements. In Proceedings of the 2nd international conference on Embedded networked sensor systems (SenSys’04), pages 5061, November 2004.

Network Coding in Wireless Networks

  1. Sachin Katti, Hariharan Rahul, Wenjun Hu, Dina Katabi, Muriel Medard, and Jon Crowcroft. XORs in the air: Practical wireless network coding. In Proceedings of ACM SIGCOMM Conference 2006, September 2006.

  2. Tracey Ho, Yu-Han Chang, and Keesook Han. On Constructive Network Coding for Multiple Unicasts. In Proceedings of Forty-Fourth Annual Allerton Conference. September 2006.

Practical Wireless Networks

  1. David Eckhardt and Peter Steenkiste. Measurement and analysis of the error characteristics of an in-building wireless network. In Proceedings of the ACM SIGCOMM Conference, pages 243–254, 1996.

  2. Giao T. Nguyen, Randy H. Katz, Brian Noble, and Mahadev Satyanarayanan. A trace-based approach for modeling wireless channel behavior. In Winter Simulation Conference, pages 597–604, 1996.

  3. David A. Maltz, Josh Broch, and David B. Johnson. Experiences designing and building a multi-hop wireless ad hoc network testbed. Technical Report CMU-CS-99-116, CMU, 1999.

  4. David A. Maltz, Josh Broch, and David B. Johnson. Quantitative lessons from a full-scale multi-hop wireless ad hoc network testbed. In Proceedings of the IEEE Wireless Communications and Networking Conference 2000, September 2000.

  5. Jinyang Li, Charles Blake, Douglas S. J. De Couto, Hu Imm Lee, and Robert Morris. Capacity of Ad Hoc Wireless Networks. In Proceedings of the 7th annual international conference on Mobile computing and networking (Mobicom ’01), pages 61-69, New York, NY, USA, 2001. ACM Press.

  6. Mike Ritter, Robert J. Friday, Rodrigo Garces, Will San Filippo, and Cuong-Thinh Nguyen. Mobile connectivity protocols and throughput measurements in the ricochet microcellular data network (MCDN) system. In Proceedings of the 7th annual international conference on Mobile computing and networking (Mobicom ’01), pages 322–331, New York, NY, USA, 2001. ACM Press.

  7. Almudena Konrad, Ben Y. Zhao, Anthony D. Joseph, and Reiner Ludwig. A Markov-Based Channel Model Algorithm for Wireless Networks. In Proc. of Fourth ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM 2001), 2001.

  8. Deepak Ganesan, Bhaskar Krishnamachari, Alec Woo, David Culler, Deborah Estrin, and Stephen Wicker. Complex Behavior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks. Technical Report CSD-TR 02-0013, UCLA, February 2002

  9. Henrik Lundgren, Erik Nordström, and Christian Tschudin. Coping with communication grey zones in IEEE 802.11b based ad hoc networks. In Proceedings of WoWMoM Workshop, 2002.

  10. Erik Nordstrom. APE – a large scale ad hoc network testbed for reproducible performance tests. Master’s thesis, Uppsala University, June 2002.

  11. Mark D. Yarvis, W. Steven Conner, Lakshman Krishnamurthy, Jasmeet Chhabra, and Brent Elliott, and Alan Mainwaring. Real-world experiences with an interactive ad hoc sensor network. In Proceedings of the International Workshop on Ad Hoc Networking, August 2002.

  12. Andreas Willig, Martin Kubisch, Christian Hoene, and Adam Wolisz. Measurements of a wireless link in an industrial environment using an IEEE 802.11-compliant physical layer. IEEE Transactions on Industrial Electronics, 43(6):1265–1282, December 2002.

  13. Rudi van Drunen, Jasper Koolhaas, Dirk-Willem van Gulik, Huub Schuurmans, and Marten Vijn. Building a wireless community network in the netherlands. In Proceedings of USENIX/Freenix Conference, June 2003.

  14. David Kotz, Calvin Newport, and Chip Elliott. The mistaken axioms of wireless-network research. Technical Report TR2003-467, Dartmouth College, July 2003.

  15. Douglas S. J. De Couto, Daniel Aguayo, John Bicket, and Robert Morris. A high-throughput path metric for multi-hop wireless routing. In Proceedings of the 9th ACM International Conference on Mobile Computing and Networking (MobiCom ’03), San Diego, California, September 2003.

  16. Alec Woo, Terence Tong, and David Culler. Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks. In Proc. of the 1st ACM Conf. on Embedded Networked Sensor Systems, pages 14-27. Los Angeles, November 5-7 2003.

  17. Glenn Judd and Peter Steenkiste. Repeatable and Realistic Wireless Experimentation through Physical Emulation. In Proceedings of HotNets-II, November 2003

  18. David Kotz, Calvin Newport, Robert S. Gray, Jason Liu, Yougu Yuan, and Chip Elliott. Experimental evaluation of wireless simulation assumptions. In ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), 2004.

  19. Daniel Aguayo, John Bicket, Sanjit Biswas, Glenn Judd, and Robert Morris. Link-level Measurements from an 802.11b Mesh Network. In Proceedings of ACM SIGCOMM Conference 2004, August 2004.

  20. Robert S. Gray, David Kotz, Calvin Newport, Nikita Dubrovsky, Aaron Fiske, Jason Liu, Christopher Masone, Susan McGrath, and Yougu Yuan. Outdoor experimental comparison of four ad hoc routing algorithms. In ACM/IEEE International Symposium on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), October 2004.

  21. Bhaskaran Raman and Kameswari Chebrolu. Revisiting MAC design for an 802.11-based mesh network. In Proceedings of the Third Workshop on Hot Topics in Networks (HotNets-III), November 2004.

  22. John Bicket, Daniel Aguayo, Sanjit Biswas, and Robert Morris. Architecture and Evaluation of an Unplanned 802.11b Mesh Network. In Proceedings of Mobicom 2005, Cologne, Germany, August 2005.

Geocast

  1. Julio C. Navas and Tomasz Imielinski. Geocast - geographic addressing and routing. In Proceedings of the 3rd ACM International Conference on Mobile Computing and Networking (MobiCom ’97), pages 66-76, New York, NY, USA, 1997. ACM Press.

  2. Young-Bae Ko and Nitin H Vaidya. Geocasting in mobile ad hoc networks: Location-based multicast algorithms. Technical Report TR-98-018, Texas A&M, September 1998.

  3. Young-Bae Ko and Nitin H. Vaidya. GeoTORA: A protocol for geocasting in mobile ad hoc networks. In Proceedings of the International Conference on Network Protocols (ICNP 2000). Pages 240-250. November 2000.

  4. Wen-Hwa Liao, Yu-Chee Tseng, Kuo-Lun Lo, and Jang-Ping Sheu. GeoGRID: A geocasting protocol for mobile ad hoc networks based on grid. Journal of Internet Technology, 1(2):2332, 2000.

  5. Qingfeng Huang, Chenyang Lu, and Gruia-Catalin Roman. Spatiotemporal multicast in sensor networks. In Proceedings of the 1st international conference on Embedded networked sensor systems (SenSys’03), pages 205-217, New York, NY, USA, 2003. ACM Press.

  6. Qingfeng Huang, Chenyang Lu, and Gruia-Catalin Roman. Reliable mobicast via face-aware routing. In Proceedings of IEEE Infocom ’04, March 2004.

Increasing Throughput in Wireless Networks

  1. Hyuk Lim, Chaegwon Lim and Jennifer Hou. A Coordinate-Based Approach for Exploiting Temporal-Spatial Diversity in Wireless Mesh Networks. In Proceedings of Mobicom 2006, Los Angeles, CA, September 2006.

  2. Andrew Brzezinski, Gil Zussman, and Eytan Modiano. Enabling Distributed Throughput Maximization in Wireless Mesh Networks A Partitioning Approach. In Proceedings of Mobicom 2006, Los Angeles, CA, September 2006.

 

 

$Date: 2008/01/01 06:35:12 $