4501
правка
Взвешенное связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
м
Взвешенное связное доминирующее множество (посмотреть исходный код)
Версия от 12:03, 9 августа 2016
, 9 августа 2016нет описания правки
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 5: | Строка 5: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача представляет собой взвешенный вариант классической задачи вычисления минимального связного доминирующего множества. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремились минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные беспроводные вершины могут иметь различную стоимость использования в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке. Таким образом, предположив, что каждой вершине сопоставлена стоимость, характеризующая ее принадлежность к магистрали, необходимо изучить распределенные алгоритмы для формирования взвешенных магистралей. Было изучено несколько централизованных алгоритмов для построения взвешенных связных доминирующих множеств с минимальными весами [3, 7, 9]. В своих недавних работах Ван, Ван и Ли [12, 13] предложили эффективный распределенный метод построения взвешенной магистрали с низкой стоимостью. Они доказали, что полная стоимость построенной магистрали отличается от оптимальной на небольшой константный коэффициент либо в случае, когда стоимости вершин являются сглаженными (т.е. максимальное отношение стоимости смежных вершин ограничено), либо в случае ограничения максимальной степени вершины. В данной работе впервые была рассмотрена взвешенная версия задачи построения минимального связного доминирующего множества и представлен распределенный алгоритм аппроксимации для этой задачи. | Задача представляет собой взвешенный вариант классической задачи вычисления минимального связного доминирующего множества. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремились минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные беспроводные вершины могут иметь различную стоимость использования в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке. Таким образом, предположив, что каждой вершине сопоставлена стоимость, характеризующая ее принадлежность к магистрали, необходимо изучить распределенные алгоритмы для формирования взвешенных магистралей. Было изучено несколько централизованных алгоритмов для построения взвешенных связных доминирующих множеств с минимальными весами [3, 7, 9]. В своих недавних работах Ван, Ван и Ли [12, 13] предложили эффективный распределенный метод построения взвешенной магистрали с низкой стоимостью. Они доказали, что полная стоимость построенной магистрали отличается от оптимальной на небольшой константный коэффициент либо в случае, когда стоимости вершин являются сглаженными (т.е. максимальное отношение стоимости смежных вершин ограничено), либо в случае ограничения максимальной степени вершины. В данной работе впервые была рассмотрена взвешенная версия задачи построения минимального связного доминирующего множества и представлен распределенный алгоритм аппроксимации для этой задачи. | ||
== Нотация == | == Нотация == | ||
Коммуникационный граф G = (V, E) над множеством беспроводных вершин V содержит ребро uv между вершинами u и v в том и только том случае, если u и v могут напрямую связываться друг с другом, т.е. находятся в пределах областей передачи друг друга. Пусть <math>d_G(u) \;</math> – степень вершины u в графе G, а <math>\Delta \;</math> – максимальная степень среди всех беспроводных вершин (т.е. <math>\Delta = max_{u \in V} \; d_G(u) \;</math>). Каждой беспроводной вершине u сопоставлена стоимость принадлежности к магистрали – c(u). Пусть <math>\delta = max_{ij \in E} \; c(i)/c(j) \;</math>, где ij – ребро между вершинами i и j, E – множество коммуникационных каналов в беспроводной сети G, а операция взятия максимума производится над всеми парами смежных вершин i и j в G. Иными словами, <math>\delta \;</math> представляет собой максимальное отношение стоимостей двух смежных вершин и может быть названо '' | Коммуникационный граф G = (V, E) над множеством беспроводных вершин V содержит ребро uv между вершинами u и v в том и только том случае, если u и v могут напрямую связываться друг с другом, т.е. находятся в пределах областей передачи друг друга. Пусть <math>d_G(u) \;</math> – степень вершины u в графе G, а <math>\Delta \;</math> – максимальная степень среди всех беспроводных вершин (т.е. <math>\Delta = max_{u \in V} \; d_G(u) \;</math>). Каждой беспроводной вершине u сопоставлена стоимость принадлежности к магистрали – c(u). Пусть <math>\delta = max_{ij \in E} \; c(i)/c(j) \;</math>, где ij – ребро между вершинами i и j, E – множество коммуникационных каналов в беспроводной сети G, а операция взятия максимума производится над всеми парами смежных вершин i и j в G. Иными словами, <math>\delta \;</math> представляет собой максимальное отношение стоимостей двух смежных вершин и может быть названо ''сглаженностью стоимостей'' сети. Если <math>\delta \;</math> ограничено некоторой небольшой константой, стоимости вершин являются ''сглаженными''. Если область передачи каждой беспроводной вершины моделируется единичным диском с этой вершиной в центре, то коммуникационный граф называют [[граф единичных дисков|графом единичных дисков]] и обозначают как UDG(V). Такие сети также называются гомогенными сетями. | ||
| Строка 21: | Строка 22: | ||
Еще одна родственная задача – вычисление независимого множества. Подмножество вершин графа G является [[независимое множество вершин|независимым множеством]], если никакие две вершины подмножества не соединены ребром. Независимое множество является ''наибольшим'', если к нему нельзя добавить ни одной вершины так, чтобы получилось независимое множество большего размера. Очевидно, что любое наибольшее независимое множество является доминирующим множеством. Независимое множество является [[максимальное независимое множество|максимальным]], если не существует независимого множества с большим количеством вершин. [[Число независимости]] графа G, обозначаемое как <math>\alpha (G) \;</math>, представляет собой размер максимального независимого множества этого графа. ''k-локальное число независимости'', <math>\alpha^{ [k] } (G) \;</math>, определяется как <math>\alpha^{ [k] } (G) = max_{u \in V} \; \alpha (G_k(u)) \;</math>. Здесь <math>G_k(u) \;</math> – граф, порожденный на вершинах G, находящихся от вершины u на расстоянии не более k переходов (обозначается <math>N_k(u) \;</math>), т.е. <math>G_k(u) \;</math> определяется на <math>N_k(u) \;</math> и содержит все ребра G, обе конечных точки которых содержатся в <math>N_k(u) \;</math>. Хорошо известно, что для графа единичных дисков <math>\alpha^{ [1] } (UDG) \le 5 \;</math> [2] и <math>\alpha^{ [2] } (UDG) \le 18 \;</math> [11]. | Еще одна родственная задача – вычисление независимого множества. Подмножество вершин графа G является [[независимое множество вершин|независимым множеством]], если никакие две вершины подмножества не соединены ребром. Независимое множество является ''наибольшим'', если к нему нельзя добавить ни одной вершины так, чтобы получилось независимое множество большего размера. Очевидно, что любое наибольшее независимое множество является доминирующим множеством. Независимое множество является [[максимальное независимое множество|максимальным]], если не существует независимого множества с большим количеством вершин. [[Число независимости]] графа G, обозначаемое как <math>\alpha (G) \;</math>, представляет собой размер максимального независимого множества этого графа. ''k-локальное число независимости'', <math>\alpha^{ [k] } (G) \;</math>, определяется как <math>\alpha^{ [k] } (G) = max_{u \in V} \; \alpha (G_k(u)) \;</math>. Здесь <math>G_k(u) \;</math> – граф, порожденный на вершинах G, находящихся от вершины u на расстоянии не более k переходов (обозначается <math>N_k(u) \;</math>), т.е. <math>G_k(u) \;</math> определяется на <math>N_k(u) \;</math> и содержит все ребра G, обе конечных точки которых содержатся в <math>N_k(u) \;</math>. Хорошо известно, что для графа единичных дисков <math>\alpha^{ [1] } (UDG) \le 5 \;</math> [2] и <math>\alpha^{ [2] } (UDG) \le 18 \;</math> [11]. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 51: | Строка 53: | ||
С точки зрения временной сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный алгоритм аппроксимации с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь временную сложность не ниже <math>\Omega (log \; \Delta / log \; log \; \Delta)</math>. | С точки зрения временной сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный алгоритм аппроксимации с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь временную сложность не ниже <math>\Omega (log \; \Delta / log \; log \; \Delta)</math>. | ||
== Применение == | == Применение == | ||
Предлагаемые распределенные алгоритмы построения МВСДМ могут использоваться для децентрализованных сетей или распределенных систем с целью формирования магистральной сети с низкой стоимостью для коммуникационных приложений. Стоимость, используемая здесь в качестве входного параметра алгоритмов, представляет собой общую (generic) стоимость, определяемую различными практическими приложениями. Она может обозначать пригодность или приоритет каждой вершины при выборе ее в качестве центрального узла магистрали. Чем ниже стоимость, тем выше приоритет. В других практических случаях эта стоимость может представлять коэффициент энергопотребления вершины, если необходимо получить магистраль с малым энергопотреблением; надежность вершины – для получения магистрали с высокой отказоустойчивостью; функцию от уровня безопасности – при создании магистрали с повышенным вниманием к безопасности; либо объединенную весовую функцию, интегрирующую различные метрики – такие как интенсивность трафика, накладные расходы на передачу сигнала, уровень заряда батареи и покрытие. Таким образом, определяя различные варианты стоимости, предлагаемые алгоритмы построения магистрали с низкой стоимостью могут использоваться в разных практических приложениях. Помимо формирования магистрали для маршрутизации, взвешенный алгоритм кластеризации (алгоритм 1) также может использоваться для других приложений – таких как выбор мобильных агентов для обнаружения вторжений в децентрализованных сетях [8] (для выбора более надежных агентов с более низким энергопотреблением) либо выбора точек рандеву для сбора и хранения данных в сетях датчиков [15] (для обеспечения энергоэффективности и баланса объема хранения). | Предлагаемые распределенные алгоритмы построения МВСДМ могут использоваться для децентрализованных сетей или распределенных систем с целью формирования магистральной сети с низкой стоимостью для коммуникационных приложений. Стоимость, используемая здесь в качестве входного параметра алгоритмов, представляет собой общую (generic) стоимость, определяемую различными практическими приложениями. Она может обозначать пригодность или приоритет каждой вершины при выборе ее в качестве центрального узла магистрали. Чем ниже стоимость, тем выше приоритет. В других практических случаях эта стоимость может представлять коэффициент энергопотребления вершины, если необходимо получить магистраль с малым энергопотреблением; надежность вершины – для получения магистрали с высокой отказоустойчивостью; функцию от уровня безопасности – при создании магистрали с повышенным вниманием к безопасности; либо объединенную весовую функцию, интегрирующую различные метрики – такие как интенсивность трафика, накладные расходы на передачу сигнала, уровень заряда батареи и покрытие. Таким образом, определяя различные варианты стоимости, предлагаемые алгоритмы построения магистрали с низкой стоимостью могут использоваться в разных практических приложениях. Помимо формирования магистрали для маршрутизации, взвешенный алгоритм кластеризации (алгоритм 1) также может использоваться для других приложений – таких как выбор мобильных агентов для обнаружения вторжений в децентрализованных сетях [8] (для выбора более надежных агентов с более низким энергопотреблением) либо выбора точек рандеву для сбора и хранения данных в сетях датчиков [15] (для обеспечения энергоэффективности и баланса объема хранения). | ||
== Открытые вопросы == | == Открытые вопросы == | ||
| Строка 59: | Строка 63: | ||
В работах [12, 13] используются следующие предположения о модели беспроводной сети: всенаправленная антенна, единичная передача принимается всеми вершинами в пределах досягаемости передатчика. Если ослабить некоторые из этих предположений, решение задачи МВСДМ становится намного более сложным. | В работах [12, 13] используются следующие предположения о модели беспроводной сети: всенаправленная антенна, единичная передача от которой принимается всеми вершинами в пределах досягаемости передатчика. Если ослабить некоторые из этих предположений, решение задачи МВСДМ становится намного более сложным. | ||