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

Рассматриваются три класса геометрической маршрутизации: ''онлайновая геометрическая маршрутизация'', ''оффлайновая геометрическая маршрутизация'' и ''динамическая геометрическая маршрутизация''. Во всех трех классах особое внимание уделяется построению маршрута сообщения из источника к адресату, включающего минимально возможное количество этапов коммуникации. Заметим, что количество этапов коммуникации соответствует общему числу передач. Таким образом, минимизируя количество этапов коммуникации, мы уменьшаем и количество передач, способствуя экономии энергии. Далее рассмотрим список комбинаторных и алгоритмических определений, часто используемых контексте геометрической маршрутизации.

'''Граф единичных дисков''' (Unit-Disk Graph, UDG) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором две вершины <math>u, v \in V</math> соединены ребром e в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1.

'''Граф Гэбриэла''' (Gabriel Graph, GG) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором для любых u, v 2 V ребро (u, v) 2 E в случае, если u и v – единственные вершины в V, принадлежащие к кругу диаметром (u, v) as diameter.

'''Триангуляция Делоне''' <math>\Delta</math> множества вершин V, вложенных в <math>\mathcal{R}^2</math>, представляет собой геометрическую двойственную конструкцию диаграммы Вороного [9] V, в которой две вершины в V связаны ребром в <math>\Delta</math>, если соответствующие им ячейки диаграммы Вороного инцидентны друг другу. Триангуляция Делоне <math>\Delta</math> является ''единичной'', если длина ребер в ней не превышает 1.

«'''Принцип правой руки'''»: правило, используемое алгоритмами обхода графа, которые при движении в выбранную сторону первым выбирают ребро, ведущее направо.

'''Кучеобразная структура'''. Пусть G = (V, E) – неориентированный планарный граф, такой, что каждая вершина в V содержит некоторое численное значение. Кучеобразная структура представляет собой базисное возможное решение (BFS) в виде дерева T, содержащее все вершины G, такое, что для каждой вершины v, отличной от корня, хранящееся в v значение меньше значения, хранящегося в предке v.

'''Системы кластеров''' [2]. Пусть G = (V, E) – неориентированный планарный граф, имеющий n = |V| вершин и радиус R. Можно построить систему семейств кластеров F(0), F(1), ..., F(logR), такую, что (1) диаметр каждого кластера в F(i) составляет <math>O(2^i \; log \; n)</math>, (2) каждая вершина принадлежит не более чем к O(log n) кластерам, (3) для любых двух вершин, расстояние между которыми в G описывается неравенством <math>2^{i - 1} < d \le 2^i</math>, существует по меньшей мере один кластер в F(i), содержащий две вершины.

'''Лемма 2''' [4]. Рассмотрим любые <math>s, t \in V</math>. Предположим, что x и y – две точки, такие, что s, x и y принадлежат к триангуляции Делоне <math>\Delta</math>. Пусть <math>\alpha</math> и <math>\beta</math> - углы, образованные сегментами <math>\bar{xs}</math> и <math>\bar{st}</math>, и сегментами <math>\bar{ts}</math> и <math>\bar{sy}</math>, соответственно. Если <math>\alpha < \beta</math>, то |xs| < |st|. В противном случае |ys| < |st|.

'''Лемма 3'''. Пусть G = (V, E) – планарный граф, вложенный в <math>\mathcal{R}^2</math> и <math>s, t \in V</math>. Далее, обозначим за <math>x_i</math> ближайшую к t точку пересечения, определяемую некоторым ребром <math>e_i</math>, принадлежащим к некоторой грани <math>F_i</math>, и отрезком прямой <math>\bar{st}</math>. Аналогично обозначим за <math>x_{i + 1}</math> ближайшую к t точку пересечения, определяемую некоторым ребром, принадлежащим к грани <math>F_{i + 1}</math>, и отрезком прямой <math>\bar{st}</math>, где грань <math>F_{i+1}</math> инцидентна <math>F_i</math> посредством ребра <math>e_i</math>. Тогда <math>x_i, t| > |x_{i+1}, t|</math>.

'''Лемма 4''' [6]. Пусть G = (V, E) – планарный цивилизованный граф, вложенный в <math>\mathcal{R}^2</math>. Любой эллипс с большой осью c покрывает не более <math>O(c^2)</math> вершин и ребер.

'''Маршрутизация по циркулю, тип 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 строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Обработка имеет смысл в случае, если за ней следует выполнение частых запросов.

'''Теорема 10 [5]. После предварительной обработки запросы с единственным источником требуют O(c) времени, а с несколькими источниками – O(c log n) в графах единичных дисков, обладающих свойством графов Гэбриэла.'''

'''Геометрическая маршрутизация в графах с динамическими ребрами''' [3] применяется к модели, в которой вершины узлы являются безошибочными и стационарными, а ребра меняют статус между ''активным'' и ''неактивным''. Однако при этом предполагается, что, несмотря на динамические изменения топологии, сеть всегда сохраняет связность. В этой модели алгоритм маршрутизации с обходом графа по временным меткам (Timestamp-Traversal) сочетает использование глобального времени и времени начала маршрутизации для обхода остовного подграфа, содержащего только стабильные связи.

Альтернативное решение под названием «обходом с ограничением дистанции» (Tethered-Traversal) основывается на наблюдении, согласно которому (вновь) появляющиеся ребра потенциально сокращают пути обхода; у этого решения временная и пространственная сложность процедуры маршрутизации линейны относительно числа вершин n.