Маршрутизация в геометрических сетях: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 20: | Строка 20: | ||
Рассматриваются три класса геометрической маршрутизации: ''онлайновая геометрическая маршрутизация'', ''оффлайновая геометрическая маршрутизация'' и ''динамическая геометрическая маршрутизация''. | Рассматриваются три класса геометрической маршрутизации: ''онлайновая геометрическая маршрутизация'', ''оффлайновая геометрическая маршрутизация'' и ''динамическая геометрическая маршрутизация''. Во всех трех классах особое внимание уделяется построению маршрута сообщения из истоника в точку назначения, включающего минимально возможное количество этапов коммуникации. Заметим, что количество этапов коммуникации соответствует общему числу передач. Таким образом, минимизируя количество этапов коммуникации, мы уменьшаем и количество передач, способствуя экономии энергии. Далее рассмотрим список комбинаторных и алгоритмических определений, часто используемых контексте геометрической маршрутизации. | ||
Планарный граф. Граф 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. | |||
== Применение == | |||
'''Онлайновая геометрическая маршрутизация''' | |||