4551
правка
Маршрутизация в геометрических сетях: различия между версиями
Перейти к навигации
Перейти к поиску
м
Маршрутизация в геометрических сетях (посмотреть исходный код)
Версия от 22:30, 2 июня 2019
, 2 июня 2019→Применение
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| Строка 88: | Строка 88: | ||
'''Геометрическая децентрализованная маршрутизация''' (Geometric Ad-hoc Routing, GOAFR+) [5] обладает доказуемо высокой теоретической и практической эффективностью. Согласно лемме 5, крайне непрактичное предположение | '''Геометрическая децентрализованная маршрутизация''' (Geometric Ad-hoc Routing, GOAFR+) [5] обладает доказуемо высокой теоретической и практической эффективностью. Согласно лемме 5, крайне непрактичное предположение <math>\Omega(1)</math> можно отбросить. GOAFR+ сочетает алгоритмы жадной маршрутизации и маршрутизации по граням. Алгоритм начинает работу с подхода жадной маршрутизации CR-I, а когда пересылаемое сообщение достигает локального минимума (попадает в тупик), переключается на Face Routing. | ||
При этом GOAFR+ стремится при первой возможности вернуться к жадной маршрутизации за счет применения техники быстрого восстановления. Моделирование показывает, что в среднем случае GOAFR+ превосходит GOAFR и | При этом GOAFR+ стремится при первой возможности вернуться к жадной маршрутизации за счет применения техники ''быстрого восстановления''. Моделирование показывает, что в среднем случае GOAFR+ превосходит GOAFR и GOAFR<math>_{FC}</math>, рассматривавшиеся в работе [7]. | ||
'''Теорема 9 [2]. Алгоритм GOAFR+ имеет оптимальную временную сложность O( | '''Теорема 9 [2]. Алгоритм GOAFR+ имеет оптимальную временную сложность <math>O(c^2)</math> на любых графах единичных дисков, обладающих свойством графов Гэбриэла.''' | ||
| Строка 100: | Строка 100: | ||
В случае оффлайновой геометрической маршрутизации этапу маршрутизации предшествует этап предварительной обработки, во время которого на основе входного графа G строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Обработка имеет смысл в случае, если за ней следует выполнение частых запросов. | В случае оффлайновой геометрической маршрутизации этапу маршрутизации предшествует этап предварительной обработки, во время которого на основе входного графа G строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Обработка имеет смысл в случае, если за ней следует выполнение частых запросов. | ||
Запросы с несколькими источниками [ ] – это расширение механизма запросов с единственным источником, обеспечивающее маршрутизацию за время O(c log n) между любой парой вершин, расположенных на расстоянии c в графе G, где n – количество вершин в G. Это расширение базируется на системе кластеров, которая может быть эффективно вычислена (см. лемму 6). | '''Запросы с единственным источником''' [2] – это механизм маршрутизации, позволяющий перенаправлять сообщения из выделенного источника s в любой другой узел t сети за время O(c), где c – расстояние между s и t в графе G. Процедура маршрутизации основывается на механизме косвенной адресации, реализованном в виде кучеобразной структуры, которая может быть эффективно вычислена (см. лемму 6). | ||
'''Запросы с несколькими источниками''' [2] – это расширение механизма запросов с единственным источником, обеспечивающее маршрутизацию за время O(c log n) между любой парой вершин, расположенных на расстоянии c в графе G, где n – количество вершин в G. Это расширение базируется на системе кластеров, которая может быть эффективно вычислена (см. лемму 6). | |||
| Строка 111: | Строка 113: | ||
'''Динамическая геометрическая маршрутизация''' | '''Динамическая геометрическая маршрутизация''' | ||
Геометрическая маршрутизация в графах с динамическими ребрами [3] применяется к модели, в которой вершины узлы являются безошибочными и стационарными, а ребра меняют статус между активным и неактивным. Однако при этом предполагается, что, несмотря на динамические изменения топологии, сеть всегда сохраняет связность. В этой модели алгоритм маршрутизации с обходом графа по временным меткам (Timestamp-Traversal) сочетает использование глобального времени и времени начала маршрутизации для обхода остовного подграфа, содержащего только стабильные связи. | '''Геометрическая маршрутизация в графах с динамическими ребрами''' [3] применяется к модели, в которой вершины узлы являются безошибочными и стационарными, а ребра меняют статус между ''активным'' и ''неактивным''. Однако при этом предполагается, что, несмотря на динамические изменения топологии, сеть всегда сохраняет связность. В этой модели алгоритм маршрутизации с обходом графа по временным меткам (Timestamp-Traversal) сочетает использование глобального времени и времени начала маршрутизации для обхода остовного подграфа, содержащего только стабильные связи. | ||