Планарные остовы ограниченной степени с малыми весами: различия между версиями

1. Энергоэффективная одноадресная передача: пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в 2p + 1 раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь p > 1 – некоторая константа, которая будет определена алгоритмом далее. Предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до своего соседа v на любом выбранном пути одноадресной передачи.

2. Энергоэффективная широковещательная передача: энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина дуги не более чем в константное число раз превышает длину дуги в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам.