|
| |
Geographic Routing in Higher Dimensions
Project Type: HYP/UROP
As wireless networks continue to grow in size, we are faced with the
prospect of emerging wireless networks with hundreds or thousands of nodes.
Geographic routing algorithms have emerged as an efficient alternative to
traditional ad hoc routing algorithms for such networks.
Existing geographic routing algorithms generally operate in two-dimensional
coordinates.
GDSTR, a recently developed geographic algorithm, together with
GSpring, its companion virtual coordinate assignment algorithm, are
however extensible to higher dimensions. It is anticipated that routing in
higher dimensions is likely to yield benefits in routing efficiency.
In this project, the student will implement higher-dimensional versions of GDSTR
and GSpring and evaluate the benefits of higher-dimensional geographic
routing. 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.
|
