4551
правка
Взвешенное связное доминирующее множество: различия между версиями
Перейти к навигации
Перейти к поиску
Взвешенное связное доминирующее множество (посмотреть исходный код)
Версия от 12:17, 29 июля 2016
, 29 июля 2016нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества с учетом весов. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремятся минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные вершины могут иметь различную стоимость обслуживания в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке. | Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества с учетом весов. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремятся минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные вершины могут иметь различную стоимость обслуживания в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке. Таким образом, предположив, что каждой вершине сопоставления стоимость, характеризующая ее принадлежность к магистрали, необходимо изучить распределенные алгоритмы для вычисления взвешенных магистралей. Было предложено несколько централизованных алгоритмов для построения взвешенных доминирующих множеств с минимальными весами [3, 7, 9]. В своих недавних работах Ван, ван и Ли [12, 13] предложили эффективный и недорогой распределенный метод построения взвешенной магистрали. Они доказали, что полная стоимость построенной магистрали отличается на оптимальной на небольшой коэффициент либо в случае, когда стоимости вершин являются сглаженными (т.е. максимальное соотношение стоимости смежных вершин ограничено), либо в случае ограничения максимальной степени вершины. В данной работы впервые была рассмотрена взвешенная версия задачи построения минимального связного доминирующего множества и представлен распределенный алгоритм аппроксимации. | ||
== Нотация == | |||
Коммуникационный граф G = (V, E) над множеством беспроводных вершин V содержит ребро uv между вершинами u и v в том и только том случае, если u и v могут напрямую связываться друг с другом, т.е. находятся в пределах областей передачи друг друга. Пусть dG(u) – степень вершины u в графе G, а Л – максимальная степень среди всех беспроводных вершин (т.е. Л = maxu2V dG(u)). Каждой вершине u сопоставлена стоимость c(u) принадлежности к магистрали. Пусть 8 = maxij2E c(i)/c(j), где ij – ребро между вершинами i и j, E – множество коммуникационных каналов в беспроводной сети G, а операция взятия максимума производится над всеми парами смежных вершин i и j в G. Иными словами, S представляет собой максимальное соотношение стоимостей двух смежных вершин и может быть названо гладкостью сети. Если S ограничено некоторой небольшой константой, стоимости вершин являются гладкими. Если область передачи каждой беспроводной вершины моделируется единичным диском с этой вершиной в центре, то коммуникационный граф иногда называют графом единичных дисков и обозначают как UDG(V). Такие сети также называются гомогенными сетями. | |||
Подмножество S множества V называется доминирующим множеством, если каждая вершина V либо принадлежит к S, либо смежна с некоторой вершиной, принадлежащей к S. Вершины S называются доминаторами, а вершины, не входящие в S – доминируемыми вершинами. Подмножество B множества V называется связным доминирующим множеством (СДМ), если B является доминирующим множеством и порождает связный подграф. Следовательно, вершины подмножества В могут связываться друг с другом без использования вершин V — B. Доминирующее множество минимальной мощности называется минимальным доминирующим множеством (МДМ). Связное доминирующее множество минимальной мощности называется минимальным связным доминирующим множеством (МСДМ). Во взвешенной версии каждой вершине u сопоставлена стоимость c(u). В этом случае связное доминирующее множество B называется взвешенным связным доминирующим множеством (ВСДМ). Подмножество B множества V называется минимальным взвешенным связным доминирующим множеством (МВСДМ), если B является ВСДМ с минимальной общей стоимостью. Хорошо известно, что нахождение множеств МСДМ и МВДСМ является NP-полной задачей, даже если G является графом единичных дисков. В работе Вана и др. рассматривались эффективные алгоритмы аппроксимации, вычисляющие магистраль с низкой стоимостью и способные успешно аппроксимировать нахождение МВСДМ. Для заданного коммуникационного графа G = (V, E, C), где V – множество вершин, E – множество ребер, а C – множество весов ребер, задача вычисления минимального взвешенного связного доминирующего множества формулируется следующим образом. | |||
Задача 1 (минимальное взвешенное связное доминирующее множество) | |||
Дано: Взвешенный коммуникационный граф G = (V, E, C). Требуется: найти подмножество A множества V, являющееся минимальным взвешенным связным доминирующим множеством, т.е.: (1) A является доминирующим множеством; (2) A порождает связный подграф; (3) общая стоимость A минимальна. | |||
Еще одна родственная задача – вычисление независимого множества. Подмножество вершин графа G является независимым множеством, если для любой пары вершин подмножества между ними не имеется ребер. Независимое множество является максимальным, если к нему нельзя добавить ни одной вершины так, чтобы получилось независимое множество большего размера. Очевидно, что любое максимальное независимое множество является доминирующим множеством. Оно является максимальным независимым множеством (МНМ), если не существует независимого множества с большим количеством вершин. Число независимости графа G, обозначаемое как a(G), представляет собой размер максимального независимого множества этого графа. k-локальное число независимости, a^(G), определяется как a^(G) = maxu2V a(Gk(u)). Здесь GK(U) – граф, порожденный из графа G и включающий вершины, находящиеся от вершины u на расстоянии не более k переходов (обозначается Nk(u)), т.е. Gk(u) определяется на Nk(u) и содержит все ребра G, обе конечных точки которых содержатся в Nk(u). Хорошо известно, что для графа единичных дисков tt'''((7DG) < 5 [2] и a[2](UDG) < 18 [11]. | |||
== Основные результаты == | |||
Поскольку построение взвешенных доминирующих множеств с минимальными весами является NP-полной задачей, исследователи изучали централизованные алгоритмы аппроксимации для этой задачи [3, 7, 9]. В работе [9] Клейн и Рави предложили алгоритм аппроксимации для построения дерева Штейнера с взвешенными вершинами. Обобщение этого алгоритма позволяет получить O(log Л)-аппроксимацию для задачи МВСДМ. Гуха и Хуллер [ ] также исследовали алгоритмы аппроксимации для построения дерева Штейнера с взвешенными вершинами и МВСДМ. Для решения последней они разработали алгоритм с коэффициентом аппроксимации (1:35 + e) log Л для любого фиксированного значения e > 0. Недавно Амбул и др. [3] предолжили алгоритм аппроксимации задачи МВСДМ для модели графов единичных дисков. Коэффициент аппроксимации их алгоритма ограничен 89. Все эти алгоритмы являются централизованными, в то же время в приложениях для децентрализованных беспроводных сетей обычно используются распределенные алгоритмы построения МВСДМ. | |||