4551
правка
Планарные остовы ограниченной степени с малыми весами: различия между версиями
Перейти к навигации
Перейти к поиску
м
Планарные остовы ограниченной степени с малыми весами (посмотреть исходный код)
Версия от 13:59, 19 сентября 2013
, 19 сентября 2013→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «Ключевые слова и синонимы: [[унифицированное энергоэффективное управление одноадресной и…») |
Irina (обсуждение | вклад) |
||
| Строка 5: | Строка 5: | ||
Для поддержки энергоэффективной одноадресной передачи топология должна обладать следующими свойствами: | Для поддержки энергоэффективной одноадресной передачи топология должна обладать следующими свойствами: | ||
1. СИЛЬНЫЙ ОСТОВ: [1,9,13,16,17]. Подграф H называется сильным остовом графа G, если существует положительная вещественная константа | 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]. | ||
| Строка 14: | Строка 14: | ||
Для поддержки энергоэффективной широковещательной связи [15] локально построенная топология должна обладать свойством малых весов: полная длина линии связи финальной топологии не более чем в константное число раз превышает длину линии в минимальном Евклидовом остовном дереве (Euclidean Minimum Spanning Tree, EMST). Некоторые локализованные алгоритмы [10,12] были применены для построения структур с малыми весами, способных аппроксимировать энергоэфективность EMST по мере роста плотности сети. Однако ни один из них не был достаточно энергоэффективным для одноадресной передачи. | Для поддержки энергоэффективной широковещательной связи [15] локально построенная топология должна обладать свойством малых весов: полная длина линии связи финальной топологии не более чем в константное число раз превышает длину линии в минимальном Евклидовом остовном дереве (Euclidean Minimum Spanning Tree, EMST). Некоторые локализованные алгоритмы [10,12] были применены для построения структур с малыми весами, способных аппроксимировать энергоэфективность EMST по мере роста плотности сети. Однако ни один из них не был достаточно энергоэффективным для одноадресной передачи. | ||
До сих пор все известные алгоритмы управления топологиями не были способны обеспечить энергоэффективные одноадресную и широковещательную передачи в рамках одной и той же структуры. Была поставлена задача проектирования унифицированной топологии, обладающей одновременно свойствами остовности и малых весов. Основной целью разработки алгоритма было решение этой задачи. | До сих пор все известные алгоритмы управления топологиями не были способны обеспечить энергоэффективные одноадресную и широковещательную передачи в рамках одной и той же структуры. Была поставлена задача проектирования унифицированной топологии, обладающей одновременно свойствами остовности и малых весов. Основной целью разработки алгоритма было решение этой задачи. | ||
== Основные результаты == | == Основные результаты == | ||