Маршрутизация в геометрических сетях: различия между версиями
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) м (→Применение) |
||
| (не показано 17 промежуточных версий этого же участника) | |||
| Строка 8: | Строка 8: | ||
У каждой вершины один и тот же диапазон передачи; если вершина v находится в пределах диапазона передачи некоторой другой вершины u, то вершина u может непосредственно передавать данные вершине v, и наоборот. Таким образом, сеть может быть смоделирована при помощи неориентированного графа G = (V, E), в котором две вершины < | У каждой вершины один и тот же диапазон передачи; если вершина v находится в пределах диапазона передачи некоторой другой вершины u, то вершина u может непосредственно передавать данные вершине v, и наоборот. Таким образом, сеть может быть смоделирована при помощи неориентированного графа G = (V, E), в котором две вершины <math>u, v \in V</math> соединены ребром <math>(u, v) \in E</math> в том случае, если они находятся в пределах диапазона передачи друг друга. Такие две вершины называются ''соседними вершинами'' или просто ''соседями''. Если две вершины находятся за пределами диапазона передачи друг друга, потребуется многоскачковая передача; иными словами, эти вершины должны будут связываться друг с другом через промежуточные вершины. | ||
| Строка 14: | Строка 14: | ||
В геометрических сетях не предполагается фиксированной инфраструктуры | В геометрических сетях не предполагается фиксированной инфраструктуры или центрального сервера. Иначе говоря, все вершины выступают и как ячейки сети, и как маршрутизаторы. Топология сети неизвестна вершинам за исключением их непосредственного окружения, т. е. каждая вершина знает свое местоположение и координаты своих соседей. Вершины должны вычислить и поддерживать маршруты для многоскачковых передач самостоятельным и распределенным образом. В большинстве случаев предполагается (если речь идет о сетях датчиков), что память и мощность каждой вершины ограничены. | ||
''Геометрическая маршрутизация'' представляет собой маршрутизацию из ''вершины-источника'' s к ''вершине-адресату'' t с использованием информации о географическом местоположении, то есть координат вершин. Предполагается, что вершина-источник знает координаты вершины-адресата. Для получения этой информации вершиной-источником служит специализированный внешний сервис локализации местоположения [ ]. Протокол маршрутизации состоит из последовательности этапов коммуникации. На каждом этапе протоколом маршрутизации определяются как метка уникальной передающей вершины, так и метка одной из вершин-соседей, от которой мы ожидаем принятия передаваемого сообщения. Геометрическая маршрутизация является однородной в том смысле, что при принятии решения о том, кому из соседей переслать сообщение, все вершины выполняют один и тот же протокол. | ''Геометрическая маршрутизация'' представляет собой маршрутизацию из ''вершины-источника'' s к ''вершине-адресату'' t с использованием информации о географическом местоположении, то есть координат вершин. Предполагается, что вершина-источник знает координаты вершины-адресата. Для получения этой информации вершиной-источником служит специализированный внешний сервис локализации местоположения [8]. Протокол маршрутизации состоит из последовательности этапов коммуникации. На каждом этапе протоколом маршрутизации определяются как метка уникальной передающей вершины, так и метка одной из вершин-соседей, от которой мы ожидаем принятия передаваемого сообщения. Геометрическая маршрутизация является однородной в том смысле, что при принятии решения о том, кому из соседей переслать сообщение, все вершины выполняют один и тот же протокол. | ||
Рассматриваются три класса геометрической маршрутизации: ''онлайновая геометрическая маршрутизация'', ''оффлайновая геометрическая маршрутизация'' и ''динамическая геометрическая маршрутизация''. Во всех трех классах особое внимание уделяется построению маршрута сообщения из | Рассматриваются три класса геометрической маршрутизации: ''онлайновая геометрическая маршрутизация'', ''оффлайновая геометрическая маршрутизация'' и ''динамическая геометрическая маршрутизация''. Во всех трех классах особое внимание уделяется построению маршрута сообщения из источника к адресату, включающего минимально возможное количество этапов коммуникации. Заметим, что количество этапов коммуникации соответствует общему числу передач. Таким образом, минимизируя количество этапов коммуникации, мы уменьшаем и количество передач, способствуя экономии энергии. Далее рассмотрим список комбинаторных и алгоритмических определений, часто используемых в контексте геометрической маршрутизации. | ||
| Строка 26: | Строка 26: | ||
'''Граф единичных дисков''' (Unit-Disk Graph, UDG) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором две вершины <math>u, v \in V</math> соединены ребром e в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1. | '''Граф единичных дисков''' (Unit-Disk Graph, UDG) определяется как граф G = (V, E), вложенный в пространство <math>\mathcal{R}^2</math>, в котором две вершины <math>u, v \in V</math> соединены ребром e в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1. | ||
| Строка 32: | Строка 32: | ||
'''Граф Гэбриэла''' (Gabriel Graph, GG) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором для любых u, v | '''Граф Гэбриэла''' (Gabriel Graph, GG) определяется как граф G = (V, E), вложенный в <math>\mathcal{R}^2</math>, в котором для любых <math>u, v \in V</math> ребро <math>(u, v) \in E</math> в случае, если u и v – единственные вершины в V, принадлежащие к кругу c диаметром (u, v). | ||
'''Триангуляция Делоне''' <math>\Delta</math> множества вершин V, вложенных в <math>\mathcal{R}^2</math>, представляет собой геометрическую двойственную конструкцию диаграммы Вороного [9] V, в которой две вершины в V связаны ребром в <math>\Delta</math>, если соответствующие им ячейки диаграммы Вороного инцидентны друг другу. Триангуляция Делоне <math>\Delta</math> является ''единичной'', если длина ребер в ней не превышает 1. | '''Триангуляция Делоне''' <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. | '''Кучеобразная структура'''. Пусть G = (V, E) – неориентированный планарный граф, такой, что каждая вершина в V содержит некоторое численное значение. ''Кучеобразная структура'' представляет собой базисное возможное решение (BFS) в виде дерева T, содержащее все вершины G, такое, что для каждой вершины v, отличной от корня, хранящееся в v значение меньше значения, хранящегося в предке v. | ||
'''Системы кластеров''' [2]. Пусть G = (V, E) – неориентированный планарный граф, имеющий | '''Системы кластеров''' [2]. Пусть G = (V, E) – неориентированный планарный граф, имеющий |V| = n вершин и радиус R. Можно построить систему семейств кластеров F(0), F(1), ..., F(log R), такую, что (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), содержащий две вершины. | ||
== Основные результаты и применение == | == Основные результаты и применение == | ||
| Строка 53: | Строка 53: | ||
'''Лемма 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> | '''Лемма 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) – планарный граф, вложенный в | '''Лемма 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) – планарный цивилизованный граф, вложенный в | '''Лемма 4''' [6]. Пусть G = (V, E) – планарный цивилизованный граф, вложенный в <math>\mathcal{R}^2</math>. Любой эллипс с большой осью ''c'' покрывает не более <math>O(c^2)</math> вершин и ребер. | ||
'''Лемма 5''' [5]. Пусть R – выпуклая область в | '''Лемма 5''' [5]. Пусть R – выпуклая область в <math>\mathcal{R}^2</math> с площадью A(R) и периметром P(R), и пусть <math>V \subset R</math>. Если у графа единичных дисков для V максимальная степень равна k, то количество вершин в V ограничено соотношением <math>|V| \le 8(k + 1)(A(R) + P(R) + \pi) / \pi</math>. | ||
'''Лемма 6''' [2]. Количество передач, требующееся для построения кучеобразной структуры и системы кластеров для планарного графа G, ограничено O(nD) и O( | '''Лемма 6''' [2]. Количество передач, требующееся для построения кучеобразной структуры и системы кластеров для планарного графа G, ограничено <math>O(nD)</math> и <math>O(n^2 D)</math>, соответственно, где n – количество вершин, а D – диаметр G. | ||
== Применение == | == Применение == | ||
'''Онлайновая геометрическая маршрутизация''' | '''Онлайновая геометрическая маршрутизация''' | ||
Онлайновая геометрическая маршрутизация основывается на крайне скудном объеме информации, содержащейся в передаваемом сообщении, и локальной информации, доступной в узлах сети. Это приводит к естественной масштабируемости геометрической маршрутизации. Кроме того, предполагается, что сеть статична, то есть узлы не перемещаются, а ребра не пропадают и не появляются. | |||
'''Маршрутизация по циркулю, тип I''' (Compass Routing I, CR-I) [4] представляет собой жадную процедуру на основе триангуляции Делоне и наблюдения из леммы 2, в ходе которой на каждом шагу сообщение всегда направляется соседнему узлу, находящемуся ближе к точке назначения t. К сожалению, сообщение может попасть в локальный минимум (''тупик'') в случае, когда все соседи находятся дальше от t. Процедура CR-I очень проста. Вычисление триангуляции Делоне является локальным и недорогим (см. лемму 1). Однако алгоритм не гарантирует успешной доставки. | |||
'''Маршрутизация по циркулю, тип 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. | |||
'''Теорема 7 [1]. Алгоритм Compass Routing II гарантирует успешную доставку сообщений в планарных графах за время O(n) шагов, где n – количество узлов в сети.''' | |||
'''Адаптивная маршрутизация по граням''' (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]. | |||
'''Теорема 8 [6]. Временная сложность <math>O(c^2)</math>, где c – длина кратчайшего пути между s и t, является асимптотически оптимальной в случае цивилизованных графов единичных дисков, обладающих свойством графов Гэбриэла.''' | |||
'''Геометрическая децентрализованная маршрутизация''' (Geometric Ad-hoc Routing, GOAFR+) [5] обладает доказуемо высокой теоретической и практической эффективностью. Согласно лемме 5, крайне непрактичное предположение <math>\Omega(1)</math> можно отбросить. GOAFR+ сочетает алгоритмы жадной маршрутизации и маршрутизации по граням. Алгоритм начинает работу с подхода на основе жадной маршрутизации CR-I, а когда пересылаемое сообщение достигает локального минимума (попадает в тупик), переключается на Face Routing. | |||
При этом GOAFR+ стремится при первой возможности вернуться к жадной маршрутизации за счет применения техники ''быстрого восстановления''. Моделирование показывает, что в среднем случае GOAFR+ превосходит GOAFR и GOAFR<math>_{FC}</math>, рассматривавшиеся в работе [7]. | |||
'''Теорема 9 [2]. Алгоритм GOAFR+ имеет оптимальную временную сложность <math>O(c^2)</math> на любых графах единичных дисков, обладающих свойством графов Гэбриэла.''' | |||
'''Оффлайновая геометрическая маршрутизация''' | |||
В случае оффлайновой геометрической маршрутизации этапу маршрутизации предшествует этап предварительной обработки, во время которого на основе входного графа G строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Предварительная обработка имеет смысл в случае, если за ней следует выполнение частых запросов. | |||
'''Запросы с единственным источником''' [2] – это механизм маршрутизации, позволяющий перенаправлять сообщения из выделенного источника s в любой другой узел t сети за время O(c), где c – расстояние между s и t в графе G. Процедура маршрутизации основывается на механизме косвенной адресации, реализованном в виде кучеобразной структуры, которая может быть эффективно вычислена (см. лемму 6). | |||
'''Запросы с несколькими источниками''' [2] – это расширение механизма запросов с единственным источником, обеспечивающее маршрутизацию за время O(c log n) между любой парой вершин, расположенных на расстоянии c в графе G, где n – количество вершин в G. Это расширение базируется на системе кластеров, которая может быть эффективно вычислена (см. лемму 6). | |||
'''Теорема 10 [5]. После предварительной обработки запросы с единственным источником требуют O(c) времени, а с несколькими источниками – O(c log n) времени в графах единичных дисков, обладающих свойством графов Гэбриэла.''' | |||
'''Динамическая геометрическая маршрутизация''' | |||
'''Геометрическая маршрутизация в графах с динамическими ребрами''' [3] применяется к модели, в которой узлы являются безошибочными и стационарными, а ребра меняют статус между ''активным'' и ''неактивным''. Однако при этом предполагается, что, несмотря на динамические изменения топологии, сеть всегда сохраняет связность. В этой модели алгоритм маршрутизации ''с обходом графа по временным меткам'' (Timestamp-Traversal) сочетает использование глобального времени и времени начала маршрутизации для обхода остовного подграфа, содержащего только стабильные связи. | |||
Альтернативное решение под названием «''обход с ограничением дистанции''» (Tethered-Traversal) основывается на наблюдении, согласно которому (вновь) появляющиеся ребра потенциально сокращают пути обхода; у этого решения временная и пространственная сложность процедуры маршрутизации линейны относительно числа вершин n. | |||
== Открытые вопросы == | |||
Слабо изучен вопрос пространственно эффективной онлайновой маршрутизации в статических ''ориентированных'' графах. Кроме того, имеющиеся на данный момент границы для динамической геометрической маршрутизации далеки от оптимальных. | |||
== См. также == | |||
* [[Коммуникация в децентрализованных мобильных сетях с использованием метода случайного блуждания]] | |||
* [[Минимальные k-связные геометрические сети]] | |||
== Литература == | |||
1. Bose, P., Morin, P., Stojmenovic, I., Urrutia,J.: Routing with guaranteed delivery in ad hoc wireless networks. In: Proceedings of the Third International Workshop on Discrete Algorithm and Methods for Mobility, Seattle, Washington, Aug 1999, pp. 48-55 | |||
2. Gasieniec, L., Su, C., Wong, P.W.H., Xin, Q.: Routing via single-source and multiple-source queries in static sensor networks. J. Discret. Algorithm 5(1), 1-11 (2007). A preliminary version of the paper appeared in IPDPS'2005 | |||
3. Guan, X.Y.: Face traversal routing on edge dynamic graphs. In: Proceedings of the Nineteenth International Parallel and Distributed Processing Symposium, Denver, Colorado, April 2005 | |||
4. Kranakis, E., Singh, H., Urrutia,J.: Compass routing on geometric networks. In: Proceedings of the Eleventh Canadian Conference on Computational Geometry, Vancover, BC, Canada, Aug 1999, pp. 51-54 | |||
5. Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: Of theory and practice. In: Proceedings of the Twenty-Second ACM Symposium on the Principles of Distributed Computing, Boston, Massachusetts, July 2003, pp. 63-72 | |||
6. Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proceedings of the Sixth International Workshop on Discrete Algorithm and Methods for Mobility, Atlanta, Georgia, USA, Sept 2002, pp. 24-33 | |||
7. Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-case optimal and average-case efficient geometric ad-hoc routing. In: Proceedings of the Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, Maryland, June 2003, pp. 267-278 | |||
8. Li, J., Jannotti, J., De Couto, D.S.J., Karger, D.R., Morris, R.: A scalable location service for geographic ad hoc routing. In Proceedings of the Sixth International Conference on Mobile Computing and Networking, Boston, Massachusetts, Aug 2000, pp. 120-130 | |||
9. Li, M., Lu, X.C., Peng, W.: Dynamic delaunay triangulation for wireless ad hoc network. In Proceedings of the Sixth International Workshop on Advanced Parallel Processing Technologies, Hong Kong, China, Oct 2005, pp. 382-389 | |||
Текущая версия от 15:22, 27 июня 2019
Ключевые слова и синонимы
Геометрическая маршрутизация; географическая маршрутизация; маршрутизация на основе местоположения
Постановка задачи
Модель сети / протокол коммуникаций
В геометрических сетях точки вложены в евклидову плоскость. Каждая вершина осведомлена о своем географическом положении, т. е. знает свои координаты (x, y) на плоскости.
У каждой вершины один и тот же диапазон передачи; если вершина v находится в пределах диапазона передачи некоторой другой вершины u, то вершина u может непосредственно передавать данные вершине v, и наоборот. Таким образом, сеть может быть смоделирована при помощи неориентированного графа G = (V, E), в котором две вершины [math]\displaystyle{ u, v \in V }[/math] соединены ребром [math]\displaystyle{ (u, v) \in E }[/math] в том случае, если они находятся в пределах диапазона передачи друг друга. Такие две вершины называются соседними вершинами или просто соседями. Если две вершины находятся за пределами диапазона передачи друг друга, потребуется многоскачковая передача; иными словами, эти вершины должны будут связываться друг с другом через промежуточные вершины.
Стоимость c(e) отправки сообщения соседней вершине через ребро [math]\displaystyle{ e \in E }[/math] можно моделировать различными способами. Среди наиболее распространенных можно упомянуть следующие: метрика прыжков (или каналов) (c(e) = 1), евклидова метрика (c(e) = |e|), где |e| – евклидова длина ребра e, и метрика энергии ([math]\displaystyle{ c(e) = |e|^{\alpha} }[/math] для [math]\displaystyle{ \alpha \ge 2 }[/math]).
В геометрических сетях не предполагается фиксированной инфраструктуры или центрального сервера. Иначе говоря, все вершины выступают и как ячейки сети, и как маршрутизаторы. Топология сети неизвестна вершинам за исключением их непосредственного окружения, т. е. каждая вершина знает свое местоположение и координаты своих соседей. Вершины должны вычислить и поддерживать маршруты для многоскачковых передач самостоятельным и распределенным образом. В большинстве случаев предполагается (если речь идет о сетях датчиков), что память и мощность каждой вершины ограничены.
Геометрическая маршрутизация представляет собой маршрутизацию из вершины-источника s к вершине-адресату t с использованием информации о географическом местоположении, то есть координат вершин. Предполагается, что вершина-источник знает координаты вершины-адресата. Для получения этой информации вершиной-источником служит специализированный внешний сервис локализации местоположения [8]. Протокол маршрутизации состоит из последовательности этапов коммуникации. На каждом этапе протоколом маршрутизации определяются как метка уникальной передающей вершины, так и метка одной из вершин-соседей, от которой мы ожидаем принятия передаваемого сообщения. Геометрическая маршрутизация является однородной в том смысле, что при принятии решения о том, кому из соседей переслать сообщение, все вершины выполняют один и тот же протокол.
Рассматриваются три класса геометрической маршрутизации: онлайновая геометрическая маршрутизация, оффлайновая геометрическая маршрутизация и динамическая геометрическая маршрутизация. Во всех трех классах особое внимание уделяется построению маршрута сообщения из источника к адресату, включающего минимально возможное количество этапов коммуникации. Заметим, что количество этапов коммуникации соответствует общему числу передач. Таким образом, минимизируя количество этапов коммуникации, мы уменьшаем и количество передач, способствуя экономии энергии. Далее рассмотрим список комбинаторных и алгоритмических определений, часто используемых в контексте геометрической маршрутизации.
Планарный граф. Граф G = (V, E) является планарным, если вершины V могут быть вложены в двумерное евклидово пространство [math]\displaystyle{ \mathcal{R}^2 }[/math], т. е. каждая вершина из V получает уникальные координаты, а ребра между каждой парой вершин из E изображаются таким образом, что они не пересекают друг друга в [math]\displaystyle{ \mathcal{R}^2 }[/math].
Граф единичных дисков (Unit-Disk Graph, UDG) определяется как граф G = (V, E), вложенный в пространство [math]\displaystyle{ \mathcal{R}^2 }[/math], в котором две вершины [math]\displaystyle{ u, v \in V }[/math] соединены ребром e в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1.
Модель с [math]\displaystyle{ \lambda }[/math]-точностью / [math]\displaystyle{ \Omega(1) }[/math] или «цивилизованный граф» – это граф G = (V, E), вложенный в пространство [math]\displaystyle{ \mathcal{R}^2 }[/math], у которого для любого фиксированного [math]\displaystyle{ \lambda \gt 0 }[/math] две вершины [math]\displaystyle{ u, v \in V }[/math] находятся на расстоянии не менее [math]\displaystyle{ \lambda }[/math].
Граф Гэбриэла (Gabriel Graph, GG) определяется как граф G = (V, E), вложенный в [math]\displaystyle{ \mathcal{R}^2 }[/math], в котором для любых [math]\displaystyle{ u, v \in V }[/math] ребро [math]\displaystyle{ (u, v) \in E }[/math] в случае, если u и v – единственные вершины в V, принадлежащие к кругу c диаметром (u, v).
Триангуляция Делоне [math]\displaystyle{ \Delta }[/math] множества вершин V, вложенных в [math]\displaystyle{ \mathcal{R}^2 }[/math], представляет собой геометрическую двойственную конструкцию диаграммы Вороного [9] V, в которой две вершины в V связаны ребром в [math]\displaystyle{ \Delta }[/math], если соответствующие им ячейки диаграммы Вороного инцидентны друг другу. Триангуляция Делоне [math]\displaystyle{ \Delta }[/math] является единичной, если длина ребер в ней не превышает 1.
«Принцип правой руки»: правило, используемое алгоритмами обхода графа, которые при движении в сторону точки назначения первым выбирают ребро, ведущее вправо.
Кучеобразная структура. Пусть G = (V, E) – неориентированный планарный граф, такой, что каждая вершина в V содержит некоторое численное значение. Кучеобразная структура представляет собой базисное возможное решение (BFS) в виде дерева T, содержащее все вершины G, такое, что для каждой вершины v, отличной от корня, хранящееся в v значение меньше значения, хранящегося в предке v.
Системы кластеров [2]. Пусть G = (V, E) – неориентированный планарный граф, имеющий |V| = n вершин и радиус R. Можно построить систему семейств кластеров F(0), F(1), ..., F(log R), такую, что (1) диаметр каждого кластера в F(i) составляет [math]\displaystyle{ O(2^i \; log \; n) }[/math], (2) каждая вершина принадлежит не более чем к O(log n) кластерам, (3) для любых двух вершин, расстояние между которыми в G описывается неравенством [math]\displaystyle{ 2^{i - 1} \lt d \le 2^i }[/math], существует по меньшей мере один кластер в F(i), содержащий две вершины.
Основные результаты и применение
Основные результаты в области геометрической маршрутизации получены на базе нижеследующих лемм, описывающих триангуляцию Делоне, планарные графы и графы единичных дисков.
Лемма 1 [9]. Триангуляция Делоне [math]\displaystyle{ \Delta }[/math] для множества точек V мощности n может быть построена локально за время O(n log n).
Лемма 2 [4]. Рассмотрим любые [math]\displaystyle{ s, t \in V }[/math]. Предположим, что x и y – две точки, такие, что s, x и y принадлежат к триангуляции Делоне [math]\displaystyle{ \Delta }[/math]. Пусть [math]\displaystyle{ \alpha }[/math] и [math]\displaystyle{ \beta }[/math] - углы, образованные сегментами [math]\displaystyle{ \bar{xs} }[/math] и [math]\displaystyle{ \bar{st} }[/math] и сегментами [math]\displaystyle{ \bar{ts} }[/math] и [math]\displaystyle{ \bar{sy} }[/math], соответственно. Если [math]\displaystyle{ \alpha \lt \beta }[/math], то |xs| < |st|. В противном случае |ys| < |st|.
Лемма 3. Пусть даны G = (V, E) – планарный граф, вложенный в [math]\displaystyle{ \mathcal{R}^2 }[/math], и [math]\displaystyle{ s, t \in V }[/math]. Обозначим за [math]\displaystyle{ x_i }[/math] ближайшую к t точку пересечения, определяемую некоторым ребром [math]\displaystyle{ e_i }[/math], принадлежащим к некоторой грани [math]\displaystyle{ F_i }[/math], и отрезком прямой [math]\displaystyle{ \bar{st} }[/math]. Аналогично обозначим за [math]\displaystyle{ x_{i + 1} }[/math] ближайшую к t точку пересечения, определяемую некоторым ребром, принадлежащим к грани [math]\displaystyle{ F_{i + 1} }[/math], и отрезком прямой [math]\displaystyle{ \bar{st} }[/math], где грань [math]\displaystyle{ F_{i+1} }[/math] инцидентна [math]\displaystyle{ F_i }[/math] посредством ребра [math]\displaystyle{ e_i }[/math]. Тогда [math]\displaystyle{ |x_i, t| \gt |x_{i+1}, t| }[/math].
Лемма 4 [6]. Пусть G = (V, E) – планарный цивилизованный граф, вложенный в [math]\displaystyle{ \mathcal{R}^2 }[/math]. Любой эллипс с большой осью c покрывает не более [math]\displaystyle{ O(c^2) }[/math] вершин и ребер.
Лемма 5 [5]. Пусть R – выпуклая область в [math]\displaystyle{ \mathcal{R}^2 }[/math] с площадью A(R) и периметром P(R), и пусть [math]\displaystyle{ V \subset R }[/math]. Если у графа единичных дисков для V максимальная степень равна k, то количество вершин в V ограничено соотношением [math]\displaystyle{ |V| \le 8(k + 1)(A(R) + P(R) + \pi) / \pi }[/math].
Лемма 6 [2]. Количество передач, требующееся для построения кучеобразной структуры и системы кластеров для планарного графа G, ограничено [math]\displaystyle{ O(nD) }[/math] и [math]\displaystyle{ O(n^2 D) }[/math], соответственно, где n – количество вершин, а D – диаметр G.
Применение
Онлайновая геометрическая маршрутизация
Онлайновая геометрическая маршрутизация основывается на крайне скудном объеме информации, содержащейся в передаваемом сообщении, и локальной информации, доступной в узлах сети. Это приводит к естественной масштабируемости геометрической маршрутизации. Кроме того, предполагается, что сеть статична, то есть узлы не перемещаются, а ребра не пропадают и не появляются.
Маршрутизация по циркулю, тип I (Compass Routing I, CR-I) [4] представляет собой жадную процедуру на основе триангуляции Делоне и наблюдения из леммы 2, в ходе которой на каждом шагу сообщение всегда направляется соседнему узлу, находящемуся ближе к точке назначения t. К сожалению, сообщение может попасть в локальный минимум (тупик) в случае, когда все соседи находятся дальше от t. Процедура CR-I очень проста. Вычисление триангуляции Делоне является локальным и недорогим (см. лемму 1). Однако алгоритм не гарантирует успешной доставки.
Маршрутизация по циркулю, тип II (Compass Routing II, CR-II) [1, 4] – первый алгоритм геометрической маршрутизации, основанный на принципе правой руки и наблюдении из леммы 3, который гарантирует успешную доставку в любом графе, вложенном в [math]\displaystyle{ \mathcal{R}^2 }[/math]. Алгоритм также носит название маршрутизации по граням (Face Routing), поскольку пересылаемое сообщение движется вдоль периметров граней, постепенно приближаясь к точке назначения. В выпуклом графе сегмент [math]\displaystyle{ \bar{st} }[/math] пересекается с периметром любой грани не более двух раз. Таким образом, когда пересылаемое сообщение попадает в первое ребро e, пересекающее [math]\displaystyle{ \bar{st} }[/math], оно немедленно оказывается на грани по другую сторону e. Следовательно, каждое ребро на каждой грани проходится не более чем дважды. Однако в графе общего вида сообщение должно пройти по всем ребрам, инцидентным грани. Это необходимо для поиска точки пересечения [math]\displaystyle{ x_i }[/math], ближайшей к точке назначения t. В этом случае каждое ребро может проходиться целых четыре раза. Однако, если после обхода всех ребер пересылаемое сообщение выбирает более короткий путь к [math]\displaystyle{ x_i }[/math] (вместо того чтобы воспользоваться принципом правой руки), амортизированная стоимость прохода каждого ребра оказывается равной 3 [1]. Доказательство корректности следует из леммы 3.
Теорема 7 [1]. Алгоритм Compass Routing II гарантирует успешную доставку сообщений в планарных графах за время O(n) шагов, где n – количество узлов в сети.
Адаптивная маршрутизация по граням (Adaptive Face Routing, AFR) [6] представляет собой асимптотически оптимальную геометрическую маршрутизацию в планарных цивилизованных графах. Алгоритм пытается оценить длину c кратчайшего пути между s и t с шагом [math]\displaystyle{ \widehat{c} }[/math] (начиная с [math]\displaystyle{ \widehat{c} = 2 | \bar{st} | }[/math] и удваивая ее в каждом последующем раунде). В каждом раунде обход грани ограничен областью, образованной эллипсом с главной осью [math]\displaystyle{ \widehat{c} }[/math] и центром в [math]\displaystyle{ \bar{st} }[/math]. При выполнении алгоритма AFR каждое ребро проходится не более 4 раз, а его временная сложность составляет [math]\displaystyle{ O(c^2) }[/math], согласно лемме 4. Соответствующая нижняя граница также приведена в [6].
Теорема 8 [6]. Временная сложность [math]\displaystyle{ O(c^2) }[/math], где c – длина кратчайшего пути между s и t, является асимптотически оптимальной в случае цивилизованных графов единичных дисков, обладающих свойством графов Гэбриэла.
Геометрическая децентрализованная маршрутизация (Geometric Ad-hoc Routing, GOAFR+) [5] обладает доказуемо высокой теоретической и практической эффективностью. Согласно лемме 5, крайне непрактичное предположение [math]\displaystyle{ \Omega(1) }[/math] можно отбросить. GOAFR+ сочетает алгоритмы жадной маршрутизации и маршрутизации по граням. Алгоритм начинает работу с подхода на основе жадной маршрутизации CR-I, а когда пересылаемое сообщение достигает локального минимума (попадает в тупик), переключается на Face Routing.
При этом GOAFR+ стремится при первой возможности вернуться к жадной маршрутизации за счет применения техники быстрого восстановления. Моделирование показывает, что в среднем случае GOAFR+ превосходит GOAFR и GOAFR[math]\displaystyle{ _{FC} }[/math], рассматривавшиеся в работе [7].
Теорема 9 [2]. Алгоритм GOAFR+ имеет оптимальную временную сложность [math]\displaystyle{ O(c^2) }[/math] на любых графах единичных дисков, обладающих свойством графов Гэбриэла.
Оффлайновая геометрическая маршрутизация
В случае оффлайновой геометрической маршрутизации этапу маршрутизации предшествует этап предварительной обработки, во время которого на основе входного графа G строятся несколько структур данных. Это ускоряет последующее выполнение маршрутизации. Предварительная обработка имеет смысл в случае, если за ней следует выполнение частых запросов.
Запросы с единственным источником [2] – это механизм маршрутизации, позволяющий перенаправлять сообщения из выделенного источника s в любой другой узел t сети за время O(c), где c – расстояние между s и t в графе G. Процедура маршрутизации основывается на механизме косвенной адресации, реализованном в виде кучеобразной структуры, которая может быть эффективно вычислена (см. лемму 6).
Запросы с несколькими источниками [2] – это расширение механизма запросов с единственным источником, обеспечивающее маршрутизацию за время O(c log n) между любой парой вершин, расположенных на расстоянии c в графе G, где n – количество вершин в G. Это расширение базируется на системе кластеров, которая может быть эффективно вычислена (см. лемму 6).
Теорема 10 [5]. После предварительной обработки запросы с единственным источником требуют O(c) времени, а с несколькими источниками – O(c log n) времени в графах единичных дисков, обладающих свойством графов Гэбриэла.
Динамическая геометрическая маршрутизация
Геометрическая маршрутизация в графах с динамическими ребрами [3] применяется к модели, в которой узлы являются безошибочными и стационарными, а ребра меняют статус между активным и неактивным. Однако при этом предполагается, что, несмотря на динамические изменения топологии, сеть всегда сохраняет связность. В этой модели алгоритм маршрутизации с обходом графа по временным меткам (Timestamp-Traversal) сочетает использование глобального времени и времени начала маршрутизации для обхода остовного подграфа, содержащего только стабильные связи.
Альтернативное решение под названием «обход с ограничением дистанции» (Tethered-Traversal) основывается на наблюдении, согласно которому (вновь) появляющиеся ребра потенциально сокращают пути обхода; у этого решения временная и пространственная сложность процедуры маршрутизации линейны относительно числа вершин n.
Открытые вопросы
Слабо изучен вопрос пространственно эффективной онлайновой маршрутизации в статических ориентированных графах. Кроме того, имеющиеся на данный момент границы для динамической геометрической маршрутизации далеки от оптимальных.
См. также
- Коммуникация в децентрализованных мобильных сетях с использованием метода случайного блуждания
- Минимальные k-связные геометрические сети
Литература
1. Bose, P., Morin, P., Stojmenovic, I., Urrutia,J.: Routing with guaranteed delivery in ad hoc wireless networks. In: Proceedings of the Third International Workshop on Discrete Algorithm and Methods for Mobility, Seattle, Washington, Aug 1999, pp. 48-55
2. Gasieniec, L., Su, C., Wong, P.W.H., Xin, Q.: Routing via single-source and multiple-source queries in static sensor networks. J. Discret. Algorithm 5(1), 1-11 (2007). A preliminary version of the paper appeared in IPDPS'2005
3. Guan, X.Y.: Face traversal routing on edge dynamic graphs. In: Proceedings of the Nineteenth International Parallel and Distributed Processing Symposium, Denver, Colorado, April 2005
4. Kranakis, E., Singh, H., Urrutia,J.: Compass routing on geometric networks. In: Proceedings of the Eleventh Canadian Conference on Computational Geometry, Vancover, BC, Canada, Aug 1999, pp. 51-54
5. Kuhn, F., Wattenhofer, R., Zhang, Y., Zollinger, A.: Geometric ad-hoc routing: Of theory and practice. In: Proceedings of the Twenty-Second ACM Symposium on the Principles of Distributed Computing, Boston, Massachusetts, July 2003, pp. 63-72
6. Kuhn, F., Wattenhofer, R., Zollinger, A.: Asymptotically optimal geometric mobile ad-hoc routing. In: Proceedings of the Sixth International Workshop on Discrete Algorithm and Methods for Mobility, Atlanta, Georgia, USA, Sept 2002, pp. 24-33
7. Kuhn, F., Wattenhofer, R., Zollinger, A.: Worst-case optimal and average-case efficient geometric ad-hoc routing. In: Proceedings of the Fourth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Annapolis, Maryland, June 2003, pp. 267-278
8. Li, J., Jannotti, J., De Couto, D.S.J., Karger, D.R., Morris, R.: A scalable location service for geographic ad hoc routing. In Proceedings of the Sixth International Conference on Mobile Computing and Networking, Boston, Massachusetts, Aug 2000, pp. 120-130
9. Li, M., Lu, X.C., Peng, W.: Dynamic delaunay triangulation for wireless ad hoc network. In Proceedings of the Sixth International Workshop on Advanced Parallel Processing Technologies, Hong Kong, China, Oct 2005, pp. 382-389