Routing in Road Networks with Transit Nodes
- PDF / 348,566 Bytes
- 4 Pages / 547.087 x 737.008 pts Page_size
- 61 Downloads / 250 Views
R
Routing in Road Networks with Transit Nodes
stationary but the edges alternate their status between active and inactive. However, it is assumed that despite dynamic changes in the topology the network always remains connected. In this model Timestamp-Traversal routing algorithm combines the use of the global time and the starting time of the routing to traverse a spanning subgraph containing only stable links. An alternative solution called Tethered-Traversal is based on the observation that (re)appearing edges potentially shorten the traversal paths, where the time/space complexity of the routing procedure is linear in the number of nodes n. Open Problems Very little is known about space efficient on-line routing in static directed graphs. Also the current bounds in dynamic geometric routing appear to be far from optimal.
ings of the Sixth International Conference on Mobile Computing and Networking, Boston, Massachusetts, Aug 2000, pp. 120– 130 9. Li, M., Lu, X.C., Peng, W.: Dynamic delaunay triangulation for wireless ad hoc network. In Proceedings of the Sixth International Workshop on Advanced Parallel Processing Technologies, Hong Kong, China, Oct 2005, pp. 382–389
Routing in Road Networks with Transit Nodes 2007; Bast, Funke, Sanders, Schultes DOMINIK SCHULTES Institute for Computer Science, University of Karlsruhe, Karlsruhe, Germany Keywords and Synonyms Shortest paths
Cross References Communication in Ad Hoc Mobile Networks Using Random Walks Minimum k-Connected Geometric Networks Recommended Reading 1. Bose, P., Morin, P., Stojmenovic, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. In: Proceedings of the Third International Workshop on Discrete Algorithm and Methods for Mobility, Seattle, Washington, Aug 1999, pp. 48–55 2. Gasieniec, L., Su, C., Wong, P.W.H., Xin, Q.: Routing via singlesource and multiple-source queries in static sensor networks. J. Discret. Algorithm 5(1), 1–11 (2007). A preliminary version of the paper appeared in IPDPS’2005 3. Guan, X.Y.: Face traversal routing on edge dynamic graphs. In: Proceedings of the Nineteenth International Parallel and Distributed Processing Symposium, Denver, Colorado, April 2005 4. Kranakis, E., Singh, H., Urrutia, J.: Compass routing on geometric networks. In: Proceedings of the Eleventh Canadian Conference on Computational Geometry, Vancover, BC, Canada, Aug 1999, pp. 51–54 5. Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: Of theory and practice. In: Proceedings of the Twenty-Second ACM Symposium on the Principles of Distributed Computing, Boston, Massachusetts, July 2003, pp. 63–72 6. Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proceedings of the Sixth International Workshop on Discrete Algorithm and Methods for Mobility, Atlanta, Georgia, USA, Sept 2002, pp. 24–33 7. Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-case optimal and average-case efficient geometric ad-hoc routing. In: Proceedings of the Fourth ACM International
Data Loading...
