Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина дуги не более чем в константное число раз превышает длину дуги в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | 2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина дуги не более чем в константное число раз превышает длину дуги в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | ||
3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с | 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> . | ||
| Строка 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. | ||
Алгоритм 1 строит сильный планарный остов степени | Алгоритм 1 строит сильный планарный остов степени k–1. | ||