Локальные вычисления в неструктурированных радиосетях: различия между версиями

Во многих отношениях привычные модели коммуникаций при распределенных вычислениях, такие как модель передачи сообщений, недостаточно точно описывают суровые условия, с которыми сталкиваются беспроводные децентрализованные сети и сети датчиков. Беспроводные децентрализованные сети и сети датчиков представляют собой многоскачковые радиосети, в силу чего передаваемые сообщения могут создавать помехи для одновременных передач, что приводит к коллизиям и потере пакетов. А из-за того, что все узлы используют одну и ту же беспроводную среду передачи данных, коммуникация имеет широковещательный характер, заложенный в самой ее природе. Сообщение, отправленное узлом, может быть получено всеми узлами в пределах его дальности передачи. Эти аспекты коммуникации моделируются при помощи модели радиосети – например, в [ ].

Определение 1 (модель радиосети). В модели радиосети беспроводная сеть моделируется графом G = (V, E). В каждом временном интервале узел <math>u \in V</math> может либо отправить, либо не отправить сообщение. Узел <math>v, (u, v) \in E</math>, получает сообщение тогда и только тогда, когда ровно один из его соседей отправил сообщение в этом временном интервале.

В то время как такие примитивы коммуникаций, как широковещательная передача, пробуждение или мгновенный обмен сообщениями, активно рассматривались в литературе, посвященной радиосетям (например, в [1, 2, 8]), о вычислении локальных структур координации сети, таких как кластеризация или раскраска, известно меньше. Наиболее базовое понятие кластеризации в беспроводных сетях сводится к понятию доминирующего множества из теории графов.

Определение 2 (минимальное доминирующее множество). Пусть дан граф G = (V, E). Доминирующее множество представляет собой подмножество Scy, такое, что каждая вершина графа либо находится в S, либо имеет хотя бы одного соседа в S. В задаче о минимальном доминирующем множестве требуется найти доминирующее множество S минимальной мощности.

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

Определение 3 (максимальное независимое множество). Пусть дан граф G = (V, E). Независимое множество представляет собой подмножество попарно не смежных вершин в графе G. Максимально независимое множество в G – это независимое множество S С V, такое, что для каждой вершины и <£ S существует вершина v 2 Г{и) в S.