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

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

Адаптивная маршрутизация по граням (Adaptive Face Routing, AFR) [6] представляет собой асимптотически оптимальную геометрическую маршрутизацию в планарных цивилизованных графах. Алгоритм пытается оценить длину c кратчайшего пути между s и t с шагом <math>\widehat{c}</math> (начиная с <math>\widehat{c} = 2 | \bar{st} |</math> и удваивая ее в каждом последующем раунде). В каждом раунде обход грани ограничен областью, образованной эллипсом с главной осью <math>\widehat{c}</math> и центром в <math>\bar{st}</math>. При выполнении алгоритма AFR каждое ребро проходится не более 4 раз, а его временная сложность составляет <math>O(c^2)</math>, согласно лемме 4. Соответствующая нижняя граница также приведена в [6].

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

В случае оффлайновой геометрической маршрутизации этапу маршрутизации предшествует этап предварительной обработки, во время которого на основе входного графа G строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Обработка имеет смысл в случае, если за ней следует выполнение частых запросов.