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

Ключевые слова и синонимы: [[унифицированное энергоэффективное управление одноадресной и широковещательной топологиями]]

Важным требованием к децентрализованным беспроводным сетям является возможность их самоорганизации; необходима динамическая реструктуризация диапазонов передачи и трактов передачи данных при изменении топологии. Рациональное использование энергии и производительность работы сети – два наиболее важных параметра функционирования децентрализованных беспроводных сетей, поскольку беспроводные устройства обычно работают только от аккумуляторов, а их вычислительные возможности и объем памяти ограничены. Таким образом, в этой динамичной среде с ограниченными ресурсами каждый беспроводной узел должен локально выбирать соседей по коммуникации и соответствующим образом корректировать мощность передачи; в результате все узлы сети самостоятельно формируют топологию, являющуюся энергоэффективной и для одноадресной передачи, и для широковещательной трансляции.

1. СИЛЬНЫЙ ОСТОВ: [1, 9, 13, 16, 17]. Подграф H называется [[сильный остов|сильным остовом]] графа G, если существует положительная вещественная константа <math>\rho\ </math>, такая, что для любых двух вершин графа потребление энергии на кратчайшем пути в H не более чем в <math>\rho\ </math> раз выше потребления энергии на кратчайшем пути в G. <math>\rho\ </math> называется [[коэффициент растяжения по мощности|коэффициентом растяжения по мощности]] или просто [[коэффициент растяжения|коэффициентом растяжения]].

Для поддержки энергоэффективной широковещательной связи [15] локально построенная топология должна обладать свойством [[малые веса|малых весов]]: полная длина линии связи финальной топологии не более чем в константное число раз превышает длину линии в [[минимальное Евклидово остовное дерево|минимальном Евклидовом остовном дереве]] (Euclidean Minimum Spanning Tree, EMST). Некоторые локализованные алгоритмы [10, 12] были применены для построения структур с малыми весами, способных аппроксимировать энергоэфективность EMST по мере роста плотности сети. Однако ни один из них не был достаточно энергоэффективным для одноадресной передачи.

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

Это первая известная локализованная стратегия управления топологиями для всех узлов, совместно поддерживающих такую простую структуру с подобными свойствами. Прежде был известен только централизованный алгоритм, представленный в [1]. Первый шаг представляет собой Алгоритм 1, который строит энергоэффективную топологию для одноадресной передачи; затем Алгоритм 2 строит топологию, способную одновременно поддерживать энергоэффективную широковещательную передачу.

1. Вначале каждый узел самостоятельно строит локальный граф Гэбриэла (GG). Алгоритм построения графа Гэбриэла хорошо известен; одну из возможных реализаций можно найти в [13]. Вначале все узлы помечают себя меткой WHITE, т.е. «необработанные».

Локализованное управление топологией в децентрализованных беспроводных сетях является важнейшим механизмом поддержки связности сети и организации обратной связи для протоколов обмена данными. Большая часть сетевого трафика приходится на одноадресные передачи. Основными задачами являются экономия энергозатрат и повышение производительности работы сети за счет поддержки энергоэффективной типологии локальным образом. Данный алгоритм решает эти задачи за счет выбора относительно малого уровня мощности передачи и числа соседей по коммуникации для каждой вершины, что позволяет снизить уровень интерференции. Протоколы маршрутизации MANET нередко требуют применения широковещательной передачи. К примеру, такие одноадресные протоколы маршрутизации, как [[динамическая маршрутизация от источника]] (Dynamic Source Routing, DSR), [[дистанционно-векторный алгоритм маршрутизации по запросу]] (Ad Hoc On Demand Distance Vector, AODV), [[протокол зонной маршрутизации]] (Zone Routing Protocol, ZRP) и [[протокол географической маршрутизации]] (Location Aided Routing, LAR), используют для прокладки маршрутов широковещательную передачу или какие-либо ее разновидности. Крайне важно использовать в таких сетях энергоэффективные алгоритмы широковещательной передачи, поскольку беспроводные устройства часто работают только от аккумуляторов.

* ''[[Остовы разреженных графов]]