4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 14:37, 19 сентября 2013
, 19 сентября 2013нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 19: | Строка 19: | ||
Это первый локализованный алгоритм управления топологиями для всех узлов, работающий на базе унифицированной энергоэффективной типологии для одноадресной и широковещательной передачи в децентрализованных беспроводных сетях и сенсорных сетях. В рамках единой структуры гарантируются следующие свойства сети: | Это первый локализованный алгоритм управления топологиями для всех узлов, работающий на базе унифицированной энергоэффективной типологии для одноадресной и широковещательной передачи в децентрализованных беспроводных сетях и сенсорных сетях. В рамках единой структуры гарантируются следующие свойства сети: | ||
1. '''Энергоэффективная одноадресная передача''': пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в | 1. '''Энергоэффективная одноадресная передача''': пусть даны два любых узла, тогда между ними в структуре существует путь, полные энергозатраты которого не более чем в <math>2 \rho\ + 1</math> раза превышают энергозатраты любого пути, соединяющего их в исходной сети. Здесь <math>\rho\ > 1</math> – некоторая константа, которая будет определена алгоритмом далее. Предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до своего соседа v на любом выбранном пути одноадресной передачи. | ||
2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина дуги не более чем в константное число раз превышает длину дуги в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | 2. '''Энергоэффективная широковещательная передача''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина дуги не более чем в константное число раз превышает длину дуги в минимальном Евклидовом остовном дереве. Для случая широковещательной передачи и в целом любой многоабонентской передачи предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | ||
3. Ограниченная логическая степень узла: каждый узел должен связываться не более чем с k – 1 логическими соседями, где | |||
4. Ограниченная средняя физическая степень узла: ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом maxuv2 Hk UVK . | 3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где k > 9 – настраиваемый параметр. | ||
5. Планарность: не имеется дуг, пересекающих друг друга. Свойство планарности позволяет выполнять над этой структурой некоторые локализованные алгоритмы маршрутизации [2, 5, 7, 8], гарантируя доставку пакетов без использования таблицы маршрутизации. | |||
6. ©-разделенные соседи: направления между двумя логическими соседями любого узла разделены углом не менее 9, что снижает интерференцию. | 4. '''Ограниченная средняя физическая степень узла''': ожидаемая средняя физическая степень узла не превышает константы малой величины. Здесь физическая степень узла u в структуре H определяется как число узлов внутри диска с центром в u и радиусом maxuv2 Hk UVK . | ||
5. '''Планарность''': не имеется дуг, пересекающих друг друга. Свойство планарности позволяет выполнять над этой структурой некоторые локализованные алгоритмы маршрутизации [2, 5, 7, 8], гарантируя доставку пакетов без использования таблицы маршрутизации. | |||
6. '''©-разделенные соседи''': направления между двумя логическими соседями любого узла разделены углом не менее 9, что снижает интерференцию. | |||
Это первая известная локализованная стратегия управления топологиями для всех узлов, совместно поддерживающих такую простую структуру с подобными свойствами. Прежде был известен только централизованный алгоритм, представленный в [1]. Первый шаг представляет собой Алгоритм 1, который строит энергоэффективную топологию для одноадресной передачи; затем Алгоритм 2 строит топологию, способную одновременно поддерживать энергоэффективную широковещательную передачу. | Это первая известная локализованная стратегия управления топологиями для всех узлов, совместно поддерживающих такую простую структуру с подобными свойствами. Прежде был известен только централизованный алгоритм, представленный в [1]. Первый шаг представляет собой Алгоритм 1, который строит энергоэффективную топологию для одноадресной передачи; затем Алгоритм 2 строит топологию, способную одновременно поддерживать энергоэффективную широковещательную передачу. | ||