Взвешенное связное доминирующее множество: различия между версиями

Задача представляет собой взвешенный вариант классической задачи вычисления минимального связного доминирующего множества. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [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 называется связным доминирующим множеством (СДМ), если оно является доминирующим множеством и порождает связный подграф. Следовательно, вершины подмножества В могут «общаться» друг с другом без использования вершин V — B. Доминирующее множество минимальной мощности называется минимальным доминирующим множеством (МДМ). Связное доминирующее множество минимальной мощности называется минимальным связным доминирующим множеством (МСДМ). Во взвешенной версии каждой вершине u сопоставлена стоимость c(u). В этом случае связное доминирующее множество B называется взвешенным связным доминирующим множеством (ВСДМ). Подмножество B множества V называется минимальным взвешенным связным доминирующим множеством (МВСДМ), если оно является ВСДМ с минимальной полной стоимостью. Хорошо известно, что нахождение множеств МСДМ и МВДСМ оказывается NP-полной задачей, даже если G является графом единичных дисков. В работе Вана и др. рассматривались эффективные алгоритмы аппроксимации, вычисляющие магистраль с низкой стоимостью и способные успешно аппроксимировать нахождение МВСДМ. Для заданного коммуникационного графа G = (V, E, C), где V – множество вершин, E – множество ребер, а C – множество весов ребер, соответствующая задача вычисления минимального взвешенного связного доминирующего множества формулируется следующим образом.

Дано: взвешенный коммуникационный граф 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. Все эти алгоритмы являются централизованными, в то же время в приложениях для децентрализованных беспроводных сетей обычно используются распределенные алгоритмы построения МВСДМ.