4817
правок
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
м
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 11:05, 19 ноября 2024
, 19 ноября 2024нет описания правки
Irina (обсуждение | вклад) м (→См. также) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 2: | Строка 2: | ||
== Постановка задачи == | == Постановка задачи == | ||
Важным требованием к децентрализованным беспроводным сетям является возможность их самоорганизации; необходима динамическая реструктуризация диапазонов передачи и трактов передачи данных при изменении топологии. Рациональное использование энергии и производительность работы сети – два наиболее важных параметра функционирования децентрализованных беспроводных сетей, поскольку беспроводные устройства обычно работают только от аккумуляторов, а их вычислительные возможности и объем памяти ограничены. Таким образом, в этой динамичной среде с ограниченными ресурсами каждый беспроводной узел должен локально выбирать соседей по коммуникации и соответствующим образом корректировать мощность передачи; в результате все узлы сети самостоятельно формируют топологию, являющуюся энергоэффективной и для одноадресной передачи, и для широковещательной | Важным требованием к децентрализованным беспроводным сетям является возможность их самоорганизации; необходима динамическая реструктуризация диапазонов передачи и трактов передачи данных при изменении топологии. Рациональное использование энергии и производительность работы сети – два наиболее важных параметра функционирования децентрализованных беспроводных сетей, поскольку беспроводные устройства обычно работают только от аккумуляторов, а их вычислительные возможности и объем памяти ограничены. Таким образом, в этой динамичной среде с ограниченными ресурсами каждый беспроводной узел должен локально выбирать соседей по коммуникации и соответствующим образом корректировать мощность передачи; в результате все узлы сети самостоятельно формируют топологию, являющуюся энергоэффективной и для одноадресной передачи, и для широковещательной рассылки. | ||
Для поддержки энергоэффективной одноадресной передачи топология должна обладать следующими свойствами: | Для поддержки энергоэффективной одноадресной передачи топология должна обладать следующими свойствами: | ||
| Строка 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. '''Энергоэффективная широковещательная | 2. '''Энергоэффективная широковещательная рассылка''': энергопотребление широковещательной связи не более чем в константное число раз превышает оптимальное энергопотребление среди всех локально сконструированных структур. В [10] было показано, что для доказательства справедливости этого утверждения достаточно доказать, что структура имеет малые веса. Мы говорим, что структура имеет малые веса, если полная длина ее ребер не более чем в константное число раз превышает полную длину ребер в минимальном Евклидовом остовном дереве. Для случая широковещательной рассылки и в целом любой многоабонентской рассылки предполагается, что каждый узел u может корректировать свою мощность так, чтобы успешно доставать до самого далекого достижимого узла любой выбранной структуры (обычно дерева) при передаче нескольким абонентам. | ||
3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр. | 3. '''Ограниченная логическая степень узла''': каждый узел должен связываться не более чем с k – 1 логическими соседями, где <math>k \ge 9</math> – настраиваемый параметр. | ||
| Строка 33: | Строка 33: | ||
6. '''<math>\Theta\ </math>-разделенные соседи''': направления между любыми двумя логическими соседями любого узла разделены углом не менее <math>\Theta\ </math>, что снижает интерференцию коммуникации. | 6. '''<math>\Theta\ </math>-разделенные соседи''': направления между любыми двумя логическими соседями любого узла разделены углом не менее <math>\Theta\ </math>, что снижает интерференцию коммуникации. | ||
Это первая известная локализованная стратегия управления топологиями для всех узлов, совместно поддерживающих такую простую структуру с подобными свойствами. Прежде был известен только централизованный алгоритм, представленный в [1]. Первый шаг представляет собой Алгоритм 1, который строит энергоэффективную топологию для одноадресной передачи; затем Алгоритм 2 строит топологию, способную одновременно поддерживать энергоэффективную широковещательную | Это первая известная локализованная стратегия управления топологиями для всех узлов, совместно поддерживающих такую простую структуру с подобными свойствами. Прежде был известен только централизованный алгоритм, представленный в [1]. Первый шаг представляет собой Алгоритм 1, который строит энергоэффективную топологию для одноадресной передачи; затем Алгоритм 2 строит топологию, способную одновременно поддерживать энергоэффективную широковещательную рассылку. | ||
| Строка 97: | Строка 97: | ||
== Применение == | == Применение == | ||
Локализованное управление топологией в децентрализованных беспроводных сетях является важнейшим механизмом поддержки связности сети и организации обратной связи для протоколов обмена данными. Большая часть сетевого трафика приходится на одноадресные передачи. Основными задачами являются экономия энергозатрат и повышение производительности работы сети за счет поддержки энергоэффективной типологии локальным образом. Данный алгоритм решает эти задачи за счет выбора относительно малого уровня мощности передачи и числа соседей по коммуникации для каждой вершины, что позволяет снизить уровень интерференции. Протоколы маршрутизации MANET нередко требуют применения широковещательной | Локализованное управление топологией в децентрализованных беспроводных сетях является важнейшим механизмом поддержки связности сети и организации обратной связи для протоколов обмена данными. Большая часть сетевого трафика приходится на одноадресные передачи. Основными задачами являются экономия энергозатрат и повышение производительности работы сети за счет поддержки энергоэффективной типологии локальным образом. Данный алгоритм решает эти задачи за счет выбора относительно малого уровня мощности передачи и числа соседей по коммуникации для каждой вершины, что позволяет снизить уровень интерференции. Протоколы маршрутизации MANET нередко требуют применения широковещательной рассылки. К примеру, такие одноадресные протоколы маршрутизации, как [[динамическая маршрутизация от источника]] (Dynamic Source Routing, DSR), [[дистанционно-векторный алгоритм маршрутизации по запросу]] (Ad Hoc On Demand Distance Vector, AODV), [[протокол зонной маршрутизации]] (Zone Routing Protocol, ZRP) и [[протокол географической маршрутизации]] (Location Aided Routing, LAR), используют для прокладки маршрутов широковещательную рассылку или какие-либо ее разновидности. Крайне важно использовать в таких сетях энергоэффективные алгоритмы широковещательной рассылки, поскольку беспроводные устройства часто работают только от аккумуляторов. | ||
== См. также == | == См. также == | ||