4551
правка
Маршрутизация в геометрических сетях: различия между версиями
Перейти к навигации
Перейти к поиску
Маршрутизация в геометрических сетях (посмотреть исходный код)
Версия от 22:20, 2 июня 2019
, 2 июня 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 98: | Строка 98: | ||
'''Оффлайновая геометрическая маршрутизация''' | '''Оффлайновая геометрическая маршрутизация''' | ||
В случае оффлайновой геометрической маршрутизации этапу маршрутизации предшествует этап предварительной обработки, во время которого на основе входного графа G строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Обработка имеет смысл в случае, если за ней следует выполнение частых запросов. | |||
Запросы с единственным источником [ ] – это механизм маршрутизации, позволяющий перенаправлять сообщения из выделенного источника s в любой другой узел t сети за время O(c), где c – расстояние между s и t в графе G. Процедура маршрутизации основывается на механизме косвенной адресации, реализованном в виде кучеобразной структуры, которая может быть эффективно вычислена (см. лемму 6). | |||
Запросы с несколькими источниками [ ] – это расширение механизма запросов с единственным источником, обеспечивающее маршрутизацию за время O(c log n) между любой парой вершин, расположенных на расстоянии c в графе G, где n – количество вершин в G. Это расширение базируется на системе кластеров, которая может быть эффективно вычислена (см. лемму 6). | |||
'''Теорема 10 [5]. После предварительной обработки запросы с единственным источником требуют O(c) времени, а с несколькими источниками – O(c log n) в графах единичных дисков, обладающих свойством графов Гэбриэла.''' | |||
'''Динамическая геометрическая маршрутизация''' | |||
Геометрическая маршрутизация в графах с динамическими ребрами [3] применяется к модели, в которой вершины узлы являются безошибочными и стационарными, а ребра меняют статус между активным и неактивным. Однако при этом предполагается, что, несмотря на динамические изменения топологии, сеть всегда сохраняет связность. В этой модели алгоритм маршрутизации с обходом графа по временным меткам (Timestamp-Traversal) сочетает использование глобального времени и времени начала маршрутизации для обхода остовного подграфа, содержащего только стабильные связи. | |||
Альтернативное решение под названием «обходом с ограничением дистанции» (Tethered-Traversal) основывается на наблюдении, согласно которому (вновь) появляющиеся ребра потенциально сокращают пути обхода; у этого решения временная и пространственная сложность процедуры маршрутизации линейны относительно числа вершин n. | |||
== Открытые вопросы == | |||
Слабо изучен вопрос пространственно эффективной онлайновой маршрутизации в статических ориентированных графах. Кроме того, имеющиеся на данный момент границы для динамической геометрической маршрутизации далеки от оптимальных. | |||
== См. также == | |||
* [[Коммуникация в децентрализованных мобильных сетях с использованием метода случайного блуждания]] | |||
* [[Минимальные k-связные геометрические сети]] | |||
== Литература == | |||
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 single-source 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 Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, Maryland, June 2003, pp. 267-278 | |||
8. Li, J., Jannotti, J., De Couto, D.S.J., Karger, D.R., Morris, R.: A scalable location service for geographic ad hoc routing. In Proceedings 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 | |||