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

'''Маршрутизация по циркулю, тип I''' (Compass Routing I, CR-I) [ ] представляет собой жадную процедуру на основе триангуляции Делоне и наблюдения из леммы 2, в ходе которой на каждом шагу сообщение всегда направляется соседнему узлу, находящемуся ближе к точке назначения t. К сожалению, сообщение может попасть в локальный минимум (тупик) в случае, когда все соседи находятся дальше от t. Процедура CR-I очень проста. Вычисление триангуляции Делоне является локальным и недорогим (см. лемму 1). Однако алгоритм не гарантирует успешной доставки.

'''Маршрутизация по циркулю, тип II''' (Compass Routing II, CR-II) [1 , 4] – первый алгоритм геометрической маршрутизации, основанный на принципе правой руки и наблюдении из леммы 3, который гарантирует успешную доставку в любом графе, вложенном в <math>\mathcal{R}^2</math>. Алгоритм также носит название маршрутизации по граням (Face Routing), поскольку пересылаемое сообщение движется вдоль периметров граней, постепенно приближаясь к точке назначения. В выпуклом графе сегмент st пересекается с периметром любой грани не более двух раз. Таким образом, когда пересылаемое сообщение попадает в первое ребро e, пересекающее st, оно немедленно оказывается на грани по другую сторону e. Следовательно, каждое ребро на каждой грани проходит не более чем дважды. Однако в графе общего вида сообщение должно пройти по всем ребрам, инцидентным грани. Это необходимо для поиска точки пересечения <math>x_i</math>, ближайшей к точке назначения t. В этом случае каждое ребро может проходиться целых четыре раза. Однако, если после обхода всех ребер пересылаемое сообщение выбирает более короткий путь к <math>x_i</math> (вместо того чтобы воспользоваться принципом правой руки), амортизированная стоимость прохода каждого ребра оказывается равной 3 [1]. Доказательство корректности следует из леммы 3.

Адаптивная маршрутизация по граням (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.