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

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

Определение 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.

Еще одним важным примитивом в беспроводных сетях является задача раскраски вершин, в которой различные цвета ассоциируются с различными временными интервалами в схеме множественного доступа с временным разделением каналов (TDMA); правильная раскраска соответствует уровню управления доступом к среде передачи данных без прямой интерференции – иначе говоря, никакие два соседних узла не посылают сообщения в одно и то же время.

Определение 4 (минимальная раскраска вершин). Пусть дан граф G = (V, E). Правильная раскраска вершин графа G представляет собой назначение цвета c(v) каждой вершине v 2 V, такого, что c(u) ф c(v) любых двух соседних вершин (u; v) 2 E. Минимальная раскраска – это правильная раскраска, при которой количество используемых цветов минимально.

Определение 5 (модель неструктурированной радиосети). В модели неструктурированной радиосети беспроводная сеть моделируется графом единичных дисков G = (V, E). В каждом временном интервале узел u 2 V может либо отправить, либо не отправить сообщение. Узел v, (u, v) 2 E, получает сообщение тогда и только тогда, когда ровно один из его соседей отправил сообщение в этом временном интервале. Кроме того, делаются следующие предположения:

• Асинхронное пробуждение: новые узлы могут просыпаться/присоединяться асинхронно в любое время. До пробуждения узлы не получают и не отправляют никаких сообщений.

• Нет глобальных часов: узлы имеют доступ только к локальным часам, «время» на которых начинает увеличиваться после пробуждения.

• Отсутствует обнаружение конфликтов: узлы не могут различить ситуацию конфликта и отсутствие сообщения. Более того, отправляющий узел не знает, сколько его соседей правильно приняли его передачу – и были ли таковые приемы вообще.

• Минимальное знание глобальной ситуации: в момент пробуждения узлы не имеют информации о своих соседях в сети и им неизвестно, проснулись ли уже некоторые соседи, чтобы начать выполнять алгоритм. Однако узлам известна верхняя граница для максимального числа узлов n = |V|.

Мерой эффективности алгоритма, определенного на модели неструктурированной радиосети, является его временная сложность. Поскольку каждый узел может просыпаться в разное время, временная сложность алгоритма определяется как максимальное количество временных интервалов между пробуждением узла и принятием им окончательного бесповоротного решения.

Определение 6 (временная сложность). Время работы Tv узла v 2 V определяется как количество временных интервалов между пробуждением v и моментом, когда v принимает бесповоротное окончательное решение о результате выполнения своего протокола (например, присоединяется ли он к доминирующему множеству в алгоритме кластеризации, какой цвет принять в алгоритме раскраски и т. п.). Временная сложность T(Q) алгоритма Q определяется как максимальное время работы над всеми узлами в сети, т.е. T(Q) := maxv2 V Tv.

Теорема 1. Если узлы не знают n, то в односкачковых сетях каждый (возможно, рандомизированный) алгоритм требует до J2(n/log n) временных интервалов, прежде чем хотя бы один узел сможет отправить сообщение.

Для односкачковых сетей, в случае если n известно глобально, в [8] представлен рандомизированный алгоритм, который с высокой вероятностью выбирает уникального лидера за время O( n log n). Впоследствии Юрдзински и Стаховяк [ ] улучшили этот результат до O(log2 n). Обобщенная задача пробуждения в многоскачковой радиосети была впервые изучена в работе [4].

Теорема 2. В модели неструктурированной радиосети ожидаемая O(1)-аппроксимация задачи нахождения доминирующего множества может быть вычислена за ожидаемое время O(log 2n). Иначе говоря, каждый узел решает, присоединиться ли к доминирующему множеству, в течение O(log n) временных интервалов после своего пробуждения.

В последующей работе [ ] было показано, что времени выполнения O(log n) достаточно даже для вычисления более сложной структуры максимального независимого множества. Этот результат является асимптотически оптимальным, поскольку, улучшая ранее известное ограничение £?(log n/loglogn)[ ], в [6] было доказано соответствующее нижнее ограничение Q(log n).

Теорема 3. С высокой вероятностью максимальное независимое множество может быть вычислено за ожидаемое время O(log n) в модели неструктурированной радиосети. Это время является асимптотически оптимальным.

Любопытно сравнить эту достижимую верхнюю границу для жесткой модели неструктурированной радиосети с лучшими известными нижними границами времени выполнения у моделей передачи сообщений: £?(log*n) на графах единичных дисков [12] и Q (log n/ log log log n) на графах общего вида [11]. Кроме того, в [7] была доказана временная граница O(log2n) в модели радиосети без асинхронного пробуждения, в которой узлы априори знают своих соседей. Наконец, также можно эффективно раскрашивать узлы сети, как было показано в [17], а затем улучшено и обобщено в главе 12 работы [15].

Аналогичные границы для модели с механизмами обнаружения конфликтов были доказаны в работе [ ].

В беспроводных децентрализованных сетях и сетях датчиков активно применяются локальные структуры координации сети. В частности, кластеризация и раскраска могут способствовать облегчению коммуникаций между соседними узлами (протоколы MAC-уровня) и между удаленными узлами (протоколы маршрутизации), а также улучшению энергоэффективности сети.

Упомянем два конкретных примера применения: На основе алгоритмов построения максимального независимого множества из теоремы 3 в [ ] был представлен протокол, который эффективно строит остов, т. е. более сложную исходную инфраструктуру, которая помогает структурировать беспроводную многоскачковую сеть. В работе [16] тот же алгоритм используется в качестве компонента протокола, который минимизирует потребление энергии беспроводными сенсорными узлами на этапе развертывания – эта задача впервые изучалась в [14].