4551
правка
Маршрутизация в геометрических сетях: различия между версиями
Перейти к навигации
Перейти к поиску
Маршрутизация в геометрических сетях (посмотреть исходный код)
Версия от 18:47, 2 июня 2019
, 2 июня 2019→Применение
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 79: | Строка 79: | ||
Теорема 7 [1]. Алгоритм Compass Routing II гарантирует успешную доставку сообщений в планарных графах за время O(n) шагов, где n – количество узлов в сети. | '''Теорема 7 [1]. Алгоритм Compass Routing II гарантирует успешную доставку сообщений в планарных графах за время O(n) шагов, где n – количество узлов в сети.''' | ||
Адаптивная маршрутизация по граням (Adaptive Face Routing, AFR) [ ] представляет собой асимптотически оптимальную геометрическую маршрутизацию в планарных цивилизованных графах. Алгоритм пытается оценить длину c кратчайшего пути между s и t с шагом 2 (начиная с bc = 2jstj удваивая ее в каждом последующем раунде). В каждом раунде обход грани ограничен областью, образованной эллипсом с главной осью 2 и центром в st. При выполнении алгоритма AFR каждое ребро проходится не более 4 раз, а его временная сложность составляет O(c2), согласнолемме 4. Соответствующая нижняя граница также приведена в [6]. | |||
'''Теорема 8 [6]. Временная сложность O(c2), где c – длина кратчайшего пути между s и t, является асимптотически оптимальной в случае цивилизованных графов единичных дисков, обладающих свойством графов Гэбриэла.''' | |||
Геометрическая децентрализованная маршрутизация (Geometric Ad-hoc Routing, GOAFR+) [ ] обладает доказуемо высокой теоретической и практической эффективностью. Согласно лемме 5, крайне непрактичное предположение Q (1) можно отбросить. GOAFR+ сочетает алгоритмы жадной маршрутизации и маршрутизации по граням. Алгоритм начинает работу с подхода жадной маршрутизации CR-I, а когда пересылаемое сообщение достигает локального минимума (попадает в тупик), переключается на Face Routing. | |||
При этом GOAFR+ стремится при первой возможности вернуться к жадной маршрутизации за счет применения техники быстрого восстановления. Моделирование показывает, что в среднем случае GOAFR+ превосходит GOAFR и GOAFRFC, рассматривавшиеся в работе [ ]. | |||
'''Теорема 9 [2]. Алгоритм GOAFR+ имеет оптимальную временную сложность O(c2) на любых графах единичных дисков, обладающих свойством графов Гэбриэла.''' | |||
'''Оффлайновая геометрическая маршрутизация''' | |||