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

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

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

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

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

В геометрических сетях точки вложены в евклидову плоскость. Каждая вершина осведомлена о своем географическом положении, т. е. знает свои координаты (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) [ ] представляет собой жадную процедуру на основе триангуляции Делоне и наблюдения из леммы 2, в ходе которой на каждом шагу сообщение всегда направляется соседнему узлу, находящемуся ближе к точке назначения t. К сожалению, сообщение может попасть в локальный минимум (тупик) в случае, когда все соседи находятся дальше от t. Процедура CR-I очень проста. Вычисление триангуляции Делоне является локальным и недорогим (см. лемму 1). Однако алгоритм не гарантирует успешной доставки.

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

Теорема 7 [1]. Алгоритм Compass Routing II гарантирует успешную доставку сообщений в планарных графах за время O(n) шагов, где n – количество узлов в сети.