4430
правок
Взвешенное связное доминирующее множество: различия между версиями
Материал из WEGA
Взвешенное связное доминирующее множество (посмотреть исходный код)
Версия от 13:42, 1 октября 2023
, 1 октября 2023нет описания правки
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Минимальное взвешенное связное доминирующее множество == …») |
Irina (обсуждение | вклад) мНет описания правки |
||
| (не показано 26 промежуточных версий этого же участника) | |||
| Строка 4: | Строка 4: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача представляет собой вариант классической задачи вычисления минимального связного доминирующего множества | Задача представляет собой взвешенный вариант классической задачи вычисления минимального связного доминирующего множества. Она имеет множество вариантов практического применения, в частности, в области беспроводных сетей и распределенных систем. В предыдущих работах [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> представляет собой максимальное отношение стоимостей двух смежных вершин и может быть названо ''сглаженностью стоимостей'' сети. Если <math>\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>\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]. | |||
== Основные результаты == | |||
Поскольку построение минимальных взвешенных доминирующих множеств является NP-полной задачей, исследователи изучали централизованные аппроксимационные алгоритмы для этой задачи [3, 7, 9]. В работе [9] Клейн и Рави предложили аппроксимационный алгоритм для построения дерева Штейнера с взвешенными вершинами. Обобщение этого алгоритма позволяет получить <math>O(log \; \Delta)</math>-аппроксимацию задачи МВСДМ. Гуха и Хуллер [7] также исследовали аппроксимационные алгоритмы для построения дерева Штейнера с взвешенными вершинами и МВСДМ. Для решения последней они разработали алгоритм с коэффициентом аппроксимации <math>(1,35 + \epsilon) \; log \; \Delta</math> для любого фиксированного значения <math>\epsilon > 0 \;</math>. Недавно Амбул и др. [3] предложили константный аппроксимационный алгоритм задачи МВСДМ для модели графов единичных дисков. Коэффициент аппроксимации их алгоритма ограничен 89. Все эти алгоритмы являются централизованными, в то же время в приложениях для децентрализованных беспроводных сетей обычно используются распределенные алгоритмы построения МВСДМ. | |||
В работах [12, 13] Ван и коллеги предложили распределенный алгоритм построения взвешенного связного доминирующего множества для децентрализованной беспроводной сети G, состоящий из двух этапов: на первом этапе (этап кластеризации, алгоритм 1 в [12, 13]) вычисляется множество беспроводных вершин, являющихся доминаторами (центральных узлов); на втором этапе (алгоритм 2 в [12, 13]) вычисляется множество вершин, называемых коннекторами, для соединения этих доминаторов в магистраль. Ван и коллеги доказали, что полная стоимость построенной магистрали не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G)</math> раз превышает стоимость оптимального решения. | |||
Вначале алгоритм 1 строит максимальное независимое множество, используя классический жадный метод, в котором критерием выбора служит стоимость вершины. Затем для каждой вершины v, принадлежащей к максимальному независимому множеству, алгоритм запускает локальный жадный метод поиска покрытия множества на [[локальная окрестность|локальной окрестности]] <math>N_2(v) \;</math>, который находит некоторые вершины <math>(GRDY_v) \;</math>, покрывающие всех соседей v, доступных в результате одного перехода. Если полная стоимость <math>(GRDY_v) \;</math> меньше, чем у v, то алгоритм использует <math>(GRDY_v) \;</math> вместо v, что снижает стоимость максимального независимого множества. Следующая теорема о значении полной стоимости выбранного таким образом множества была доказана в [12, 13]. | |||
'''Теорема 1. Для сети, моделируемой графом G, алгоритм 1 из работы [12, 13] строит доминирующее множество, полная стоимость которого не более чем в <math>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>2 \cdot \alpha^{ [1] } (G) \;</math> раз превышает оптимальную для сетей, моделируемых графом G.''' | |||
Объединив теоремы 1 и 2, Ван и др. сформулировали один из основных выводов своих исследований. | |||
'''Теорема 3. Для любого коммуникационного графа G алгоритмы 1 и 2 строят взвешенное связное доминирующее множество, полная стоимость которого не более чем в <math>min( \alpha^{ [2] } (G) \; log \; (\Delta + 1), (\alpha^{ [1] } (G) - 1) \delta + 1) + 2\alpha^{ [1] } (G)</math> раз превышает оптимальную.''' | |||
Отметим, что для гомогенных беспроводных сетей, моделируемых графами единичных дисков, выполняется следующее наблюдение: стоимость построенной магистрали не более чем в <math>min(18 \; log \; (\Delta + 1), 4 \delta + 1) + 10</math> раз превышает оптимальную. Преимущество построенной магистрали заключается в том, что ее полная стоимость мала по сравнению с оптимальной в случае, когда стоимости беспроводных вершин являются сглаженными (т.е. стоимости смежных вершин отличаются на небольшой константный коэффициент), либо в случае, если максимальная степень вершины невелика. | |||
С точки зрения временной сложности вычисления наиболее продолжительным этапом данного распределенного алгоритма является построение минимального остовного дерева. Кун и др. [10] привели нижнюю границу распределенной временной сложности любого распределенного алгоритма, вычисляющего минимальное доминирующее множество на графе. В сущности, авторы доказали, что даже в случаях без требований связности и взвешенности любой распределенный аппроксимационный алгоритм с гарантированным получением полилогарифмической аппроксимации для этой задачи должен иметь временную сложность не ниже <math>\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 | |||
