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

Ключевые слова и синонимы

Геометрическая маршрутизация; географическая маршрутизация; маршрутизация на основе местоположения

Постановка задачи

Модель сети / протокол коммуникаций

В геометрических сетях точки вложены в евклидову плоскость. Каждая вершина осведомлена о своем географическом положении, т. е. знает свои координаты (x, y) на плоскости.

У каждой вершины один и тот же диапазон передачи; если вершина v находится в пределах диапазона передачи некоторой другой вершины u, то вершина u может непосредственно передавать данные вершине v, и наоборот. Таким образом, сеть может быть смоделирована при помощи неориентированного графа G = (V, E), в котором две вершины <nath>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 с использованием информации о географическом местоположении, то есть координат вершин. Предполагается, что вершина-источник знает координаты вершины-адресата. Для получения этой информации вершиной-источником служит специализированный внешний сервис локализации местоположения [ ]. Протокол маршрутизации состоит из последовательности этапов коммуникации. На каждом этапе протоколом маршрутизации определяются как метка уникальной передающей вершины, так и метка одной из вершин-соседей, от которой мы ожидаем принятия передаваемого сообщения. Геометрическая маршрутизация является однородной в том смысле, что при принятии решения о том, кому из соседей переслать сообщение, все вершины выполняют один и тот же протокол.

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

Планарный граф. Граф 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], в котором для любых u, v 2 V ребро (u, v) 2 E в случае, если u и v – единственные вершины в V, принадлежащие к кругу диаметром (u, v) as diameter.

Триангуляция Делоне [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) – неориентированный планарный граф, имеющий n = |V| вершин и радиус R. Можно построить систему семейств кластеров F(0), F(1), ..., F(logR), такую, что (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