Маршрутизация в геометрических сетях: различия между версиями

Перейти к навигации Перейти к поиску
Строка 88: Строка 88:




'''Геометрическая децентрализованная маршрутизация''' (Geometric Ad-hoc Routing, GOAFR+) [5] обладает доказуемо высокой теоретической и практической эффективностью. Согласно лемме 5, крайне непрактичное предположение Q (1) можно отбросить. GOAFR+ сочетает алгоритмы жадной маршрутизации и маршрутизации по граням. Алгоритм начинает работу с подхода жадной маршрутизации CR-I, а когда пересылаемое сообщение достигает локального минимума (попадает в тупик), переключается на Face Routing.
'''Геометрическая децентрализованная маршрутизация''' (Geometric Ad-hoc Routing, GOAFR+) [5] обладает доказуемо высокой теоретической и практической эффективностью. Согласно лемме 5, крайне непрактичное предположение <math>\Omega(1)</math> можно отбросить. GOAFR+ сочетает алгоритмы жадной маршрутизации и маршрутизации по граням. Алгоритм начинает работу с подхода жадной маршрутизации CR-I, а когда пересылаемое сообщение достигает локального минимума (попадает в тупик), переключается на Face Routing.




При этом GOAFR+ стремится при первой возможности вернуться к жадной маршрутизации за счет применения техники быстрого восстановления. Моделирование показывает, что в среднем случае GOAFR+ превосходит GOAFR и GOAFRFC, рассматривавшиеся в работе [ ].
При этом GOAFR+ стремится при первой возможности вернуться к жадной маршрутизации за счет применения техники ''быстрого восстановления''. Моделирование показывает, что в среднем случае GOAFR+ превосходит GOAFR и GOAFR<math>_{FC}</math>, рассматривавшиеся в работе [7].




'''Теорема 9 [2]. Алгоритм GOAFR+ имеет оптимальную временную сложность O(c2) на любых графах единичных дисков, обладающих свойством графов Гэбриэла.'''
'''Теорема 9 [2]. Алгоритм GOAFR+ имеет оптимальную временную сложность <math>O(c^2)</math> на любых графах единичных дисков, обладающих свойством графов Гэбриэла.'''




Строка 100: Строка 100:


В случае оффлайновой геометрической маршрутизации этапу маршрутизации предшествует этап предварительной обработки, во время которого на основе входного графа G строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Обработка имеет смысл в случае, если за ней следует выполнение частых запросов.
В случае оффлайновой геометрической маршрутизации этапу маршрутизации предшествует этап предварительной обработки, во время которого на основе входного графа G строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Обработка имеет смысл в случае, если за ней следует выполнение частых запросов.
Запросы с единственным источником [ ] – это механизм маршрутизации, позволяющий перенаправлять сообщения из выделенного источника s в любой другой узел t сети за время O(c), где c – расстояние между s и t в графе G. Процедура маршрутизации основывается на механизме косвенной адресации, реализованном в виде кучеобразной структуры, которая может быть эффективно вычислена (см. лемму 6).




Запросы с несколькими источниками [ ] – это расширение механизма запросов с единственным источником, обеспечивающее маршрутизацию за время 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) сочетает использование глобального времени и времени начала маршрутизации для обхода остовного подграфа, содержащего только стабильные связи.




Источник — http://pco.iis.nsk.su/wega/index.php/Маршрутизация_в_геометрических_сетях