Маршрутизация в геометрических сетях
Ключевые слова и синонимы
Геометрическая маршрутизация; географическая маршрутизация; маршрутизация на основе местоположения
Постановка задачи
Модель сети / протокол коммуникаций
В геометрических сетях точки вложены в евклидову плоскость. Каждая вершина осведомлена о своем географическом положении, т. е. знает свои координаты (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.
Открытые вопросы
Слабо изучен вопрос пространственно эффективной онлайновой маршрутизации в статических ориентированных графах. Кроме того, имеющиеся на данный момент границы для динамической геометрической маршрутизации далеки от оптимальных.
См. также
Литература
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
