4430
правок
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Материал из WEGA
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 14:27, 19 сентября 2013
, 19 сентября 2013→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
Это первый локализованный алгоритм управления топологиями для всех узлов, работающий на базе унифицированной энергоэффективной типологии для одноадресной и широковещательной передачи в децентрализованных беспроводных сетях и сенсорных сетях. В рамках единой структуры гарантируются следующие свойства сети: | Это первый локализованный алгоритм управления топологиями для всех узлов, работающий на базе унифицированной энергоэффективной типологии для одноадресной и широковещательной передачи в децентрализованных беспроводных сетях и сенсорных сетях. В рамках единой структуры гарантируются следующие свойства сети: | ||
1. Энергоэффективная одноадресная передача: пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в 2p + 1 раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь p > 1 – некоторая константа, которая будет определена алгоритмом далее. Предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до своего соседа v на любом выбранном пути одноадресной передачи. | 1. '''Энергоэффективная одноадресная передача''': пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в 2p + 1 раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь p > 1 – некоторая константа, которая будет определена алгоритмом далее. Предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до своего соседа v на любом выбранном пути одноадресной передачи. | ||
2. Энергоэффективная широковещательная передача: энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина дуги не более чем в константное число раз превышает длину дуги в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | 2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина дуги не более чем в константное число раз превышает длину дуги в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | ||
3. Ограниченная логическая степень узла: каждый узел должен связываться не более чем с k – 1 логическими соседями, где к > 9 – настраиваемый параметр. | 3. Ограниченная логическая степень узла: каждый узел должен связываться не более чем с k – 1 логическими соседями, где к > 9 – настраиваемый параметр. | ||
4. Ограниченная средняя физическая степень узла: ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом maxuv2 Hk UVK . | 4. Ограниченная средняя физическая степень узла: ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом maxuv2 Hk UVK . | ||
| Строка 74: | Строка 74: | ||
4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в E2(u). | 4: Как только узел u получает сообщение UPDATESTATUS(XY), он записывает статус связи xy в E2(u). | ||
5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за LS&GG финальную структуру, сформированную всеми оставшимися дугами в S&GG. | 5: Каждый узел повторяет два описанных шага до тех пор, пока не будут обработаны все дуги. Обозначим за LS&GG финальную структуру, сформированную всеми оставшимися дугами в S&GG. | ||
== Применение == | == Применение == | ||
