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

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

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

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

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

В геометрических сетях точки вложены в евклидову плоскость. Каждая вершина осведомлена о своем географическом положении, т. е. знает свои координаты (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 могут быть вложены в двумерное евклидово пространство R2, т. е. каждая вершина из V получает уникальные координаты, а ребра между каждой парой вершин из E изображаются таким образом, что они не пересекают друг друга в R2.

Граф единичных дисков (Unit-Disk Graph, UDG) определяется как граф G = (V, E), вложенный в R2, в котором две вершины u, v 2 V соединены ребром (u, v) 2 E в том случае, если евклидово расстояние между ними, обозначаемое как |u, v|, не превышает 1.

Модель с A-точностью /£?(1) или «цивилизованный граф» – это граф G = (V, E), вложенный в пространство R2, у которого для любого фиксированного A > 0 две вершины u, v 2 V находятся на расстоянии не менее A.

Граф Гэбриэла (Gabriel Graph, G G) определяется как граф G = (V, E), вложенный в R2, в котором для любых u, v 2 V ребро (u, v) 2 E в случае, если u и v – единственные вершины в V, принадлежащие к кругу диаметром (u, v) as diameter.

Триангуляция Делоне Л множества вершин V, вложенных в R2, представляет собой геометрическую двойственную конструкцию для диаграммы Вороного [9] V, в которой две вершины в V связаны ребром в A, если соответствующие им ячейки диаграммы Вороного инцидентны друг другу. Триангуляция Делоне A является единичной, если длина ребер в ней не превышает 1.

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

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

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

Основные результаты и применение

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

Лемма 1 [9]. Триангуляция Делоне A для множества точек V мощности n может быть построена локально за время O(n log n).

Лемма 2 [4]. Рассмотрим любые s, t 2 V. Предположим, что x и y – две точки, такие, что s, x и y принадлежат к триангуляции Делоне A. Пусть a и f$ - углы, образованные сегментами xs и st, и сегментами ts и sy, соответственно. Если a < f$, то |xs| < |st|. В противном случае |ys| < |st|.

Лемма 3. Пусть G = (V, E) – планарный граф, вложенный в R2, а s, t 2 V. Далее, обозначим за xi ближайшую к t точку пересечения, определяемую некоторым ребром ei, принадлежащим к некоторой грани Fi, и отрезком прямой st. Аналогично обозначим за xi+1 ближайшую к t точку пересечения, определяемую некоторым ребром, принадлежащим к грани Fi+1, и отрезком прямой st, где грань Fi+1 инцидентна Fi посредством ребра ei. Тогда jxi, t j > jxi+1, tj:

Лемма 4 [6]. Пусть G = (V, E) – планарный цивилизованный граф, вложенный в R2. Любой эллипс с большой осью c покрывает не более O(c2) вершин и ребер.

Лемма 5 [5]. Пусть R – выпуклая область в R2 с полщадью A(R) и периметром P(R), и пусть V С R: Если у графа единичных дисков для V максимальная степень равна k, то количество вершин в V ограничено |V| < 8(k + 1)(A(R) + P(R) + n)ln.

Лемма 6 [2]. Количество передас, требующееся для построения кучеобразной структуры и системы кластеров для планарного графа G, ограничено O(nD) и O(n2D), соответственно, где n – количество вершин, а D – диаметр G.

Применение

Онлайновая геометрическая маршрутизация