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

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

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

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

'''Определение 3 (максимальное независимое множество)'''. Пусть дан граф G = (V, E). Независимое множество представляет собой подмножество попарно не смежных вершин в графе G. Максимально независимое множество в G – это независимое множество <math>S \subseteq V</math>, такое, что для каждой вершины <math>u \notin S</math> существует вершина <math>v \in \Gamma (u)</math> в S.

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

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

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

'''Определение 6 (временная сложность)'''. ''Время работы'' <math>T_v</math> узла <math>v \in V</math> определяется как количество временных интервалов между ''пробуждением'' v и моментом, когда v принимает бесповоротное ''окончательное решение'' о результате выполнения своего протокола (например, присоединяется ли он к доминирующему множеству в алгоритме кластеризации, какой цвет принять в алгоритме раскраски и т. п.). ''Временная сложность'' <math>T(\mathcal{Q})</math> алгоритма <math>\mathcal{Q}</math> определяется как максимальное время работы над всеми узлами в сети, т. е. <math>T(\mathcal{Q}) := max_{v \in V} T_v</math>.

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

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

В последующей работе [18] было показано, что времени выполнения <math>O(log^2 \; n)</math> достаточно даже для вычисления более сложной структуры максимального независимого множества. Этот результат является асимптотически оптимальным, поскольку, улучшая ранее известное ограничение <math>\Omega(log^2 \; n / log \; log \; n)</math> [9], в [6] было доказано соответствующее нижнее ограничение <math>\Omega(log^2 \; n)</math>.

Любопытно сравнить эту достижимую верхнюю границу для жесткой модели неструктурированной радиосети с лучшими известными нижними границами времени выполнения у моделей передачи сообщений: <math>\Omega(log^* \; n)</math> на графах единичных дисков [12] и <math>\Omega(\sqrt{log \; n / log \; log \; n})</math> на графах общего вида [11]. Кроме того, в [7] была доказана временная граница <math>O(log^2 \; n)</math> в модели радиосети без асинхронного пробуждения, в которой узлы априори знают своих соседей. Наконец, также можно эффективно раскрашивать узлы сети, как было показано в [17], а затем улучшено и обобщено в главе 12 работы [15].

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

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