Greedy Virtual Coordinates for Geographic Routing
We present a new approach for generating virtual coordinates that produces usable coordinates quickly and improves the routing performance of existing geographic routing algorithms. Starting from a set of initial coordinates derived from a set of elected perimeter nodes, Greedy Embedding Spring Coordinates (GSpring) detects possible dead ends and uses a modified spring relaxation algorithm to incrementally adjust virtual coordinates to increase the convexity of voids in the virtual routing topology. This reduces the probability that packets will end up in dead ends during greedy forwarding. The coordinates derived by GSpring achieve routing stretch that is up to 50％ lower than that for NoGeo, the best existing algorithm for deriving virtual Euclidean coordinates for geographic routing. For realistic network topologies with obstacles, GSpring coordinates achieves from between 10 to 15％ better routing stretch than actual physical coordinates.
Ben Leong Barbara Liskov Robert Morris
Department of Computer Science National University of Singapore MIT Computer Science and Artificial Intelligence Laboratory
国际会议
The 15th IEEE International Conference on Network Protocols(ICNP 2007)(第15届IEEE国际网络协议大会)
北京
英文
71-80
2007-10-16（万方平台首次上网日期，不代表论文的发表时间）