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

Ключевые слова и синонимы

Минимальное взвешенное связное доминирующее множество

Постановка задачи

Задача представляет собой взвешенный вариант классической задачи вычисления минимального связного доминирующего множества. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [1, 2, 4, 5, 6, 14] по беспроводным сетям основное внимание уделялось разработке эффективных распределенных алгоритмов для построения связного доминирующего множества, которое можно было бы использовать в качестве виртуальной магистрали сети. Большинство предложенных методов стремились минимизировать количество вершин в магистрали (т.е. число центральных узлов). Однако для многих приложений минимизации размера магистрали будет недостаточно. Например, в беспроводных сетях различные беспроводные вершины могут иметь различную стоимость использования в качестве центрального узла из-за различий в типах устройств, энергоемкости и объеме информации, подлежащей обработке. Таким образом, предположив, что каждой вершине сопоставлена стоимость, характеризующая ее принадлежность к магистрали, необходимо изучить распределенные алгоритмы для формирования взвешенных магистралей. Было изучено несколько централизованных алгоритмов для построения взвешенных связных доминирующих множеств с минимальными весами [3, 7, 9]. В своих недавних работах Ван, Ван и Ли [12, 13] предложили эффективный распределенный метод построения взвешенной магистрали с низкой стоимостью. Они доказали, что полная стоимость построенной магистрали отличается от оптимальной на небольшой константный коэффициент либо в случае, когда стоимости вершин являются сглаженными (т.е. максимальное отношение стоимости смежных вершин ограничено), либо в случае ограничения максимальной степени вершины. В данной работе впервые была рассмотрена взвешенная версия задачи построения минимального связного доминирующего множества и представлен распределенный аппроксимационный алгоритм для этой задачи.

Нотация

Коммуникационный граф G = (V, E) над множеством беспроводных вершин V содержит ребро uv между вершинами u и v в том и только том случае, если u и v могут напрямую связываться друг с другом, т.е. находятся в пределах областей передачи друг друга. Пусть [math]\displaystyle{ d_G(u) \; }[/math] – степень вершины u в графе G, а [math]\displaystyle{ \Delta \; }[/math] – максимальная степень среди всех беспроводных вершин (т.е. [math]\displaystyle{ \Delta = max_{u \in V} \; d_G(u) \; }[/math]). Каждой беспроводной вершине u сопоставлена стоимость принадлежности к магистрали – c(u). Пусть [math]\displaystyle{ \delta = max_{ij \in E} \; c(i)/c(j) \; }[/math], где ij – ребро между вершинами i и j, E – множество коммуникационных каналов в беспроводной сети G, а операция взятия максимума производится над всеми парами смежных вершин i и j в G. Иными словами, [math]\displaystyle{ \delta \; }[/math] представляет собой максимальное отношение стоимостей двух смежных вершин и может быть названо сглаженностью стоимостей сети. Если [math]\displaystyle{ \delta \; }[/math] ограничено некоторой небольшой константой, стоимости вершин являются сглаженными. Если область передачи каждой беспроводной вершины моделируется единичным диском с этой вершиной в центре, то коммуникационный граф называют графом единичных кругов и обозначают как 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 – множество весов ребер, соответствующая задача вычисления минимального взвешенного связного доминирующего множества формулируется следующим образом.

Задача 1 (минимальное взвешенное связное доминирующее множество)

Дано: взвешенный коммуникационный граф G = (V, E, C).

Требуется: найти подмножество A множества V, являющееся минимальным взвешенным связным доминирующим множеством, т.е.: (1) A является доминирующим множеством; (2) A порождает связный подграф; (3) полная стоимость A минимальна.

Еще одна родственная задача – вычисление независимого множества. Подмножество вершин графа G является независимым множеством, если никакие две вершины подмножества не соединены ребром. Независимое множество является наибольшим, если к нему нельзя добавить ни одной вершины так, чтобы получилось независимое множество большего размера. Очевидно, что любое наибольшее независимое множество является доминирующим множеством. Независимое множество является максимальным, если не существует независимого множества с большим количеством вершин. Число независимости графа G, обозначаемое как [math]\displaystyle{ \alpha (G) \; }[/math], представляет собой размер максимального независимого множества этого графа. k-локальное число независимости, [math]\displaystyle{ \alpha^{ [k] } (G) \; }[/math], определяется как [math]\displaystyle{ \alpha^{ [k] } (G) = max_{u \in V} \; \alpha (G_k(u)) \; }[/math]. Здесь [math]\displaystyle{ G_k(u) \; }[/math] – граф, порожденный на вершинах G, находящихся от вершины u на расстоянии не более k переходов (обозначается [math]\displaystyle{ N_k(u) \; }[/math]), т.е. [math]\displaystyle{ G_k(u) \; }[/math] определяется на [math]\displaystyle{ N_k(u) \; }[/math] и содержит все ребра G, обе конечных точки которых содержатся в [math]\displaystyle{ N_k(u) \; }[/math]. Хорошо известно, что для графа единичных кругов [math]\displaystyle{ \alpha^{ [1] } (UDG) \le 5 \; }[/math] [2] и [math]\displaystyle{ \alpha^{ [2] } (UDG) \le 18 \; }[/math] [11].

Основные результаты

Поскольку построение минимальных взвешенных доминирующих множеств является NP-полной задачей, исследователи изучали централизованные аппроксимационные алгоритмы для этой задачи [3, 7, 9]. В работе [9] Клейн и Рави предложили аппроксимационный алгоритм для построения дерева Штейнера с взвешенными вершинами. Обобщение этого алгоритма позволяет получить [math]\displaystyle{ O(log \; \Delta) }[/math]-аппроксимацию задачи МВСДМ. Гуха и Хуллер [7] также исследовали аппроксимационные алгоритмы для построения дерева Штейнера с взвешенными вершинами и МВСДМ. Для решения последней они разработали алгоритм с коэффициентом аппроксимации [math]\displaystyle{ (1,35 + \epsilon) \; log \; \Delta }[/math] для любого фиксированного значения [math]\displaystyle{ \epsilon \gt 0 \; }[/math]. Недавно Амбул и др. [3] предложили константный аппроксимационный алгоритм задачи МВСДМ для модели графов единичных дисков. Коэффициент аппроксимации их алгоритма ограничен 89. Все эти алгоритмы являются централизованными, в то же время в приложениях для децентрализованных беспроводных сетей обычно используются распределенные алгоритмы построения МВСДМ.

В работах [12, 13] Ван и коллеги предложили распределенный алгоритм построения взвешенного связного доминирующего множества для децентрализованной беспроводной сети G, состоящий из двух этапов: на первом этапе (этап кластеризации, алгоритм 1 в [12, 13]) вычисляется множество беспроводных вершин, являющихся доминаторами (центральных узлов); на втором этапе (алгоритм 2 в [12, 13]) вычисляется множество вершин, называемых коннекторами, для соединения этих доминаторов в магистраль. Ван и коллеги доказали, что полная стоимость построенной магистрали не более чем в [math]\displaystyle{ min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G) }[/math] раз превышает стоимость оптимального решения.

Вначале алгоритм 1 строит максимальное независимое множество, используя классический жадный метод, в котором критерием выбора служит стоимость вершины. Затем для каждой вершины v, принадлежащей к максимальному независимому множеству, алгоритм запускает локальный жадный метод поиска покрытия множества на локальной окрестности [math]\displaystyle{ N_2(v) \; }[/math], который находит некоторые вершины [math]\displaystyle{ (GRDY_v) \; }[/math], покрывающие всех соседей v, доступных в результате одного перехода. Если полная стоимость [math]\displaystyle{ (GRDY_v) \; }[/math] меньше, чем у v, то алгоритм использует [math]\displaystyle{ (GRDY_v) \; }[/math] вместо v, что снижает стоимость максимального независимого множества. Следующая теорема о значении полной стоимости выбранного таким образом множества была доказана в [12, 13].

Теорема 1. Для сети, моделируемой графом G, алгоритм 1 из работы [12, 13] строит доминирующее множество, полная стоимость которого не более чем в [math]\displaystyle{ min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) }[/math] раз превышает оптимальную.

Алгоритм 2 находит среди доминируемых вершин несколько коннекторов, позволяющих соединить доминаторы в магистраль (связное доминирующее множество). Он формирует СДМ за счет поиска коннекторов для соединения любой пары доминаторов u и v, если они связаны в исходном графе G при помощи не более чем 3 переходов. Затем над СДМ выполняется распределенный алгоритм построения минимального остовного дерева. Теорема о полной стоимости коннекторов также была доказана в [12, 13].

Теорема 2. Полная стоимость коннекторов, выбранных алгоритмом 2 из работы [12, 13], не более чем в [math]\displaystyle{ 2 \cdot \alpha^{ [1] } (G) \; }[/math] раз превышает оптимальную для сетей, моделируемых графом G.

Объединив теоремы 1 и 2, Ван и др. сформулировали один из основных выводов своих исследований.

Теорема 3. Для любого коммуникационного графа G алгоритмы 1 и 2 строят взвешенное связное доминирующее множество, полная стоимость которого не более чем в [math]\displaystyle{ min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G) }[/math] раз превышает оптимальную.

Отметим, что для гомогенных беспроводных сетей, моделируемых графами единичных дисков, выполняется следующее наблюдение: стоимость построенной магистрали не более чем в [math]\displaystyle{ min(18 \; log \; (\Delta + 1), 4 \delta + 1) + 10 }[/math] раз превышает оптимальную. Преимущество построенной магистрали заключается в том, что ее полная стоимость мала по сравнению с оптимальной в случае, когда стоимости беспроводных вершин являются сглаженными (т.е. стоимости смежных вершин отличаются на небольшой константный коэффициент), либо в случае, если максимальная степень вершины невелика.

С точки зрения временной сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный аппроксимационный алгоритм с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь временную сложность не ниже [math]\displaystyle{ \Omega (log \; \Delta / log \; log \; \Delta) }[/math].

Применение

Предлагаемые распределенные алгоритмы построения МВСДМ могут использоваться для децентрализованных сетей или распределенных систем с целью формирования магистральной сети с низкой стоимостью для коммуникационных приложений. Стоимость, используемая здесь в качестве входного параметра алгоритмов, представляет собой общую (generic) стоимость, определяемую различными практическими приложениями. Она может обозначать пригодность или приоритет каждой вершины при выборе ее в качестве центрального узла магистрали. Чем ниже стоимость, тем выше приоритет. В других практических случаях эта стоимость может представлять коэффициент энергопотребления вершины, если необходимо получить магистраль с малым энергопотреблением; надежность вершины – для получения магистрали с высокой отказоустойчивостью; функцию от уровня безопасности – при создании магистрали с повышенным вниманием к безопасности; либо объединенную весовую функцию, интегрирующую различные метрики – такие как интенсивность трафика, накладные расходы на передачу сигнала, уровень заряда батареи и покрытие. Таким образом, определяя различные варианты стоимости, предлагаемые алгоритмы построения магистрали с низкой стоимостью могут использоваться в разных практических приложениях. Помимо формирования магистрали для маршрутизации, взвешенный алгоритм кластеризации (алгоритм 1) также может использоваться для других приложений – таких как выбор мобильных агентов для обнаружения вторжений в децентрализованных сетях [8] (для выбора более надежных агентов с более низким энергопотреблением) либо выбора точек рандеву для сбора и хранения данных в сетях датчиков [15] (для обеспечения энергоэффективности и баланса объема хранения).

Открытые вопросы

Некоторые задачи, имеющие отношение к работе Вана, Вана и Ли [12, 13], остаются нерешенными. Предложенный метод предполагает, что на протяжении разумного периода времени вершины практически статичны. Однако в некоторых сетевых приложениях сеть может быть весьма динамичной (могут меняться как топология, так и стоимость). Таким образом, после генерации взвешенной магистрали важно также иметь возможность ее динамического обслуживания. До сих пор неизвестно, как эффективно обновлять топологию с сохранением качества аппроксимации.

В работах [12, 13] используются следующие предположения о модели беспроводной сети: всенаправленная антенна, единичная передача от которой принимается всеми вершинами в пределах досягаемости передатчика. Если ослабить некоторые из этих предположений, решение задачи МВСДМ становится намного более сложным.

Экспериментальные результаты

В [12, 13] выполняется моделирование на случайных сетях для оценки эффективности предложенной взвешенной магистрали и нескольких магистралей, построенных при помощи более ранних методов. Результаты моделирования подтверждают теоретические предположения.

См. также

• Связное доминирующее множество

Литература

1. Alzoubi, K., Wan, P.-J., Frieder, O.: New distributed algorithm for connected dominating set in wireless ad hoc networks. In: Proceedings of IEEE 35th Hawaii International Conference on System Sciences (HICSS-35), Hawaii, 7-10 January 2002

2. Alzoubi, K., Li, X.-Y., Wang, Y., Wan, P.-J., Frieder, O.: Geometric spanners for wireless ad hoc networks. IEEE Trans. Parallel Distrib. Process. 14,408-421 (2003)

3. Ambuhl, C., Erlebach, T., Mihalak, M., Nunkesser, M.: Constant-factor approximation for minimum-weight (connected) dominating sets in unit disk graphs. In: Proceedings of the 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2006), Barcelona, 28-30 August 2006, LNCS, vol.4110, pp. 3-14. Springer, Berlin Heidelberg (2006)

4. Bao, L., Garcia—Aceves, J.J.: Topology management in ad hoc networks. In: Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, Annapolis, 1 - 3 June 2003, pp. 129-140. ACM Press, New York (2003)

5. Chatterjee, M., Das, S., Turgut, D.: WCA: A weighted clustering algorithm for mobile ad hoc networks. J. Clust. Comput. 5, 193-204(2002)

6. Das, B., Bharghavan, V.: Routing in ad-hoc networks using minimum connected dominating sets. In: Proceedings of IEEE International Conference on on Communications (ICC'97), vol. 1, pp. 376-380. Montreal, 8-12 June 1997

7. Guhaa, S., Khuller, S.: Improved methods for approximating node weighted Steiner trees and connected dominating sets. Inf. Comput. 150,57-74 (1999)

8. Kachirski, O., Guha, R.: Intrusion detection using mobile agents in wireless ad hoc networks. In: Proceedings of IEEE Workshop on Knowledge Media Networking, Kyoto, 10-12 July 2002

9. Klein, P., Ravi, R.: A nearly best-possible approximation algorithm for node-weighted Steiner trees. J. Algorithms 19, 104-115(1995)

10. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd ACM Symposium on the Principles of Distributed Computing (PODC), St. John's, July (2004)

11. Li, X.-Y., Wan, P.-J.: Theoretically good distributed CDMA/OVSF code assignment for wireless ad hoc networks. In: Proceedings of 11th Internatioanl Computing and Combinatorics Conference (COCOON), Kunming, 16-19 August 2005

12. Wang, Y., Wang, W., Li, X.-Y.: Efficient distributed low-cost back bone formation for wireless networks. In: Proceedings of 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2005), Urbana-Champaign, 25-27 May 2005

13. Wang, Y., Wang, W., Li, X.-Y.: Efficient distributed low cost back bone formation for wireless networks. IEEE Trans. Parallel Distrib. Syst. 17,681-693 (2006)

14. Wu,J., Li, H.: A dominating-set-based routing scheme in ad hoc wireless networks. The special issue on Wirel. Netw. Telecommun. Systems J. 3,63-84 (2001)

15. Zheng, R., He, G., Gupta, I., Sha, L.: Time idexing in sensor networks. In: Proceedings of 1 st IEEE International Conference on Mobile Ad-hoc and Sensor Systems (MASS), Fort Lauderdale, 24-27 October 2004