Аноним

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

Материал из WEGA

Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)

Версия от 03:08, 25 ноября 2024

337 байт добавлено ,  25 ноября 2024
→‎Основные результаты
мНет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
Ключевые слова и синонимы: [[унифицированное энергоэффективное управление одноадресной и широковещательной топологиями]]
'''Планарные остовы ограниченной степени с малыми весами ---''' Degree-bounded planar spanner
 
with low weight 
 
Ключевые слова и синонимы: унифицированное энергоэффективное управление одноадресной и широковещательной топологиями (Unified energy-efficient unicast and broadcast topology
 
control)


== Постановка задачи ==
== Постановка задачи ==
Строка 6: Строка 12:
Для поддержки энергоэффективной одноадресной передачи топология должна обладать следующими свойствами:
Для поддержки энергоэффективной одноадресной передачи топология должна обладать следующими свойствами:


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


2. ОГРАНИЧЕННАЯ СТЕПЕНЬ: [1, 9, 11, 13, 16, 17]. Желательно также, чтобы логическая степень узла в построенной топологии была ограничена сверху некоторой небольшой константой. Структуры с ограниченной логической степенью находят применение в беспроводных сетях, работающих по протоколу Bluetooth, в которых главный узел может одновременно иметь не более семи подчиненных узлов. Структура с логическими узлами невысокой степени сокращает стоимость обновления таблицы маршрутизации при мобильности узлов. Структура с малым значением степени и укороченными связями может значительно повысить общую пропускную способность сети [6].
2. ОГРАНИЧЕННАЯ СТЕПЕНЬ: [1, 9, 11, 13, 16, 17]. Желательно также, чтобы логическая степень узла в построенной топологии была ограничена сверху некоторой небольшой константой. Структуры с ограниченной логической степенью находят применение в беспроводных сетях, работающих по протоколу Bluetooth, в которых главный узел может одновременно иметь не более семи подчиненных узлов. Структура с логическими узлами невысокой степени сокращает стоимость обновления таблицы маршрутизации при мобильности узлов. Структура с малым значением степени и укороченными связями может значительно повысить общую пропускную способность сети [6].
Строка 13: Строка 19:




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


До сих пор все известные алгоритмы управления топологиями не были способны обеспечить энергоэффективные одноадресную и широковещательную передачи в рамках одной и той же структуры. Была поставлена задача проектирования унифицированной топологии, обладающей одновременно свойствами остовности и малых весов. Основной целью разработки алгоритма было решение этой задачи.
До сих пор все известные алгоритмы управления топологиями не были способны обеспечить энергоэффективные одноадресную и широковещательную передачи в рамках одной и той же структуры. Была поставлена задача проектирования унифицированной топологии, обладающей одновременно свойствами остовности и малых весов. Основной целью разработки алгоритма было решение этой задачи.
Строка 70: Строка 76:
'''Алгоритм 1. Построение <math>S \Theta\ GG</math>: энергоэффективная одноадресная топология'''
'''Алгоритм 1. Построение <math>S \Theta\ GG</math>: энергоэффективная одноадресная топология'''


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


2. Если WHITE-узел u имеет наименьший идентификатор среди всех WHITE-соседей в N(u), он использует следующую стратегию выбора соседей:
2. Если WHITE-узел u имеет наименьший идентификатор среди всех WHITE-соседей в N(u), он использует следующую стратегию выбора соседей:
Строка 141: Строка 147:


17. Yao, A.C.-C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11, 721-736(1982)
17. Yao, A.C.-C.: On constructing minimum spanning trees in k-dimensional spaces and related problems. SIAM J. Comput. 11, 721-736(1982)
[[Категория: Совместное определение связанных терминов]]
Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/15518...15661