| |
Resilient Geographic Routing Networks
Project Type: HYP/UROP
As wireless sensor networks continue to grow in size, we are faced with
the prospect of emerging wireless networks with hundreds or thousands of
nodes. In all likelihood, nodes will occasionally fail. For conventional
routing algorithms, routing tables may have to be re-computed. The same
seems to apply for geographic routing algorithms, i.e. face routing
algorithms require that the network be re-planarized and tree routing
algorithms (GDSTR) will require that hull trees be repaired/reformed. During
this process, packets might not be deliverable. We believe that there is a
better way.....
In this project, the student will develop and evaluate a new geographic
routing algorithm that can offer resilience in the presence of node failures. The algorithm will
be evaluated with our
in-house network simulator.
References:
-
Evangelos Kranakis,
Harvinder Singh and Jorge Urrutia,
Compass routing on geometric networks, Proc. 11 th Canadian Conference
on Computational Geometry, Vancouver, August, 1999.
-
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.
-
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.
-
Young-Jin Kim, Ramesh Govindan, Brad Karp, and Scott Shenker. Geographic routing made practical. In Proceedings of NSDI 2005, May 2005.
-
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.
-
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.
-
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.
-
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.
|