4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 14:59, 19 сентября 2013
, 19 сентября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 25: | Строка 25: | ||
3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр. | 3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр. | ||
4. '''Ограниченная средняя физическая степень узла''': ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом <math>max_{uv \in H} \big\| uv \big\| </math> . | 4. '''Ограниченная средняя физическая степень узла''': ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом <math>max_{uv \in H} \big\| uv \big\| </math>. | ||
5. '''Планарность''': не имеется дуг, пересекающих друг друга. Свойство планарности позволяет выполнять над этой структурой некоторые локализованные алгоритмы маршрутизации [2, 5, 7, 8], гарантируя доставку пакетов без использования таблицы маршрутизации. | 5. '''Планарность''': не имеется дуг, пересекающих друг друга. Свойство планарности позволяет выполнять над этой структурой некоторые локализованные алгоритмы маршрутизации [2, 5, 7, 8], гарантируя доставку пакетов без использования таблицы маршрутизации. | ||
| Строка 36: | Строка 36: | ||
'''Определение 1 ( <math>\Theta\ </math>-доминирующая область)'''. Для каждого соседа v узла u <math>\Theta\ </math>-доминирующей областью v является <math>2 \Theta\ </math>-конус с вершиной в u, осью которого является дуга uv. | '''Определение 1 ( <math>\Theta\ </math>-доминирующая область)'''. Для каждого соседа v узла u <math>\Theta\ </math>-доминирующей областью v является <math>2 \Theta\ </math>-конус с вершиной в u, осью которого является дуга uv. | ||
Пусть <math>N_{UDG}(U)</math> – множество соседей узла u в UDG. Пусть N(u) – множество соседей узла u в финальной топологии, которая была инициализирована как множество соседних узлов в GG. | Пусть <math>N_{UDG}(U) \;</math> – множество соседей узла u в UDG. Пусть N(u) – множество соседей узла u в финальной топологии, которая была инициализирована как множество соседних узлов в GG. | ||
Алгоритм 1 строит сильный планарный остов степени k–1. | Алгоритм 1 строит сильный планарный остов степени k–1. | ||
'''Лемма 1. Граф S | '''Лемма 1. Граф <math>S \Theta\ GG</math> является связным, если лежащий в его основе граф <math>GG \;</math> является связным. Более того, для любых двух вершин u и v существует путь <math>\{ u, t_1, ... , t_r, v \} \; </math>, соединяющий их, такой, что все его дуги имеют длину менее <math>\sqrt{2} \big\| uv \big\| </math>.''' | ||
'''Теорема 2. Структура S&GG состоит из узлов степенью не выше к – 1 и представляет собой сильный планарный остов с 0-разделенными соседями. Его коэффициент растяжения по мощности не превышает p = л/2 I (1 — (2p2 sin j) ), где k > 9 – настраиваемый параметр.''' | '''Теорема 2. Структура S&GG состоит из узлов степенью не выше к – 1 и представляет собой сильный планарный остов с 0-разделенными соседями. Его коэффициент растяжения по мощности не превышает p = л/2 I (1 — (2p2 sin j) ), где k > 9 – настраиваемый параметр.''' | ||