4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
м
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 18:28, 19 сентября 2013
, 19 сентября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
1. '''Энергоэффективная одноадресная передача''': пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в <math>2 \rho\ + 1</math> раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь <math>\rho\ > 1</math> – некоторая константа, которая будет определена далее в описании алгоритма. Предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до своего соседа v на любом выбранном пути одноадресной передачи. | 1. '''Энергоэффективная одноадресная передача''': пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в <math>2 \rho\ + 1</math> раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь <math>\rho\ > 1</math> – некоторая константа, которая будет определена далее в описании алгоритма. Предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до своего соседа v на любом выбранном пути одноадресной передачи. | ||
2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина | 2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина ее дуг не более чем в константное число раз превышает длину дуги в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | ||
3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр. | 3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр. | ||