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

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

Максимальные независимые множества в радиосетях; раскраска неструктурированных радиосетей

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

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

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

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

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

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

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

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

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

Для того чтобы отразить особенно жесткие характеристики беспроводных многоскачковых сетей сразу после их развертывания, модель неструктурированной радиосети делает дополнительные предположения. В частности, рассматривается новое понятие асинхронного пробуждения, поскольку в беспроводной многоскачковой среде вполне реально предположить, что некоторые узлы присоединяются к сети (например, развертываются или включаются) позже других. Отметим, что это понятие отличается от асинхронного пробуждения, определенного и изученного в [8] и последующих работах, в которых предполагается, что узлы «пробуждаются» входящими сообщениями.

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

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

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

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

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

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

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

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

Разумеется, алгоритмы для таких неинициализированных, хаотических сетей отличаются от «традиционных» алгоритмов, работающих с заранее заданным графом сети, статичным и известным всем узлам. Таким образом, алгоритмическая сложность следующих алгоритмов частично обусловлена тем, что, поскольку узлы просыпаются асинхронно и не имеют доступа к глобальным часам, различные фазы алгоритма могут произвольно переплетаться или смещаться во времени. Следовательно, в то время как некоторые узлы могут уже находиться на продвинутой стадии алгоритма, сеть может содержать узлы, которые либо только что проснулись, либо все еще находятся на ранней стадии. В [9] было доказано, что даже в односкачковых сетях (G является полным графом) не существует эффективных алгоритмов, если узлы не обладают знанием n.

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

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

Сложность локальных сетевых структур, таких как кластеризация или раскраска в неструктурированных многоскачковых радиосетях, была впервые изучена в [10]; согласно полученным результатам, хорошая аппроксимация задачи нахождения минимального доминирующего множества может быть вычислена за полилогарифмическое время.

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

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

Теорема 3. С высокой вероятностью максимальное независимое множество может быть вычислено за ожидаемое время [math]\displaystyle{ O(log^2 \; n) }[/math] в модели неструктурированной радиосети. Это время является асимптотически оптимальным.

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

Наконец, также можно эффективно раскрашивать узлы сети, как было показано в [17], а затем улучшено и обобщено в главе 12 работы [15].

Теорема 4. В модели неструктурированной радиосети правильная раскраска не более чем в [math]\displaystyle{ O(\Delta) }[/math] цветов может быть с высокой вероятностью вычислена за время [math]\displaystyle{ O(\Delta \; log \; n) }[/math].

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

Применение

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

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

Литература

1. Alon, N., Bar-Noy, A., Linial, N., Peleg, D.: A Lower Bound for Radio Broadcast. J. Comput. Syst. Sci. 43, 290-298 (1991)

2. Bar-Yehuda, R., Goldreich, O., Itai, A.: On the time-complexity of broadcast in radio networks: an exponential gap between determinism randomization. In: Proc. 6th Symposium on Principles of Distributed Computing (PODC), pp. 98-108 (1987)

3. Busch, R., Magdon-Ismail, M., Sivrikaya, F., Yener, B.: Contention-Free MAC Protocols for Wireless Sensor Networks. In: Proc. 18th Annual Conference on Distributed Computing (DISC) (2004)

4. Chrobak, M., Gasieniec, L., Kowalski, D.: The Wake-Up Problem in Multi-Hop Radio Networks. In: Proc. of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 992-1000 (2004)

5. Farach-Colton, M., Fernandes, R.J., Mosteiro, M.A.: Bootstrapping a Hop-Optimal Network in the Weak Sensor Model. In: Proc. of the 13th European Symposium on Algorithms (ESA), pp. 827-838 (2005)

6. Farach-Colton, M., Fernandes, R.J., Mosteiro, M.A.: Lower Bounds for Clear Transmissions in Radio Networks. In: Proc. of the 7th Latin American Symposium on Theoretical Informatics (LATIN), pp. 447^54 (2006)

7. Gandhi, R., Parthasarathy, S.: Distributed Algorithms for Coloring and Connected Domination in Wireless Ad Hoc Networks. In: Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 447-459 (2004)

8. Gasieniec, L., Pelc, A., Peleg, D.: The Wakeup Problem in Synchronous Broadcast Systems (Extended Abstract). In: Proc. of the 19th ACM Symposium on Principles of Distributed Computing (PODC), pp. 113-121 (2000)

9. Jurdzinski, T., Stachowiak, G.: Probabilistic Algorithms for the Wakeup Problem in Single-Hop Radio Networks. In: Proc. of the 13th Annual International Symposium on Algorithms and Computation (ISAAC), pp. 535-549 (2002)

10. Kuhn, F., Moscibroda, T., Wattenhofer, R.: Initializing Newly Deployed Ad Hoc and Sensor Networks. In: Proc. of the 10th Annual International Conference on Mobile Computing and Networking (MOBICOM), pp. 260-274 (2004)

11. Kuhn, F., Moscibroda, T., Wattenhofer, R.: What Cannot Be Computed Locally! In: Proceedings of 23rd Annual Symposium on Principles of Distributed Computing (PODC), pp. 300-309 (2004)

12. Linial, N.: Locality in Distributed Graph Algorithms. SIAM J. Comput. 21(1), 193-201 (1992)

13. Luby, M.: A Simple Parallel Algorithm for the Maximal Independent Set Problem. SIAM J. Comput. 15,1036-1053 (1986)

14. McGlynn, M.J., Borbash, S.A.: Birthday Protocols for Low Energy Deployment and Flexible Neighborhood Discovery in Ad Hoc Wireless Networks. In: Proc. of the 2nd ACM Int. Symposium on Mobile Ad Hoc Networking & Computing (MOBIHOC), (2001)

15. Moscibroda, T.: Locality, Scheduling, and Selfishness: Algorithmic Foundations of Highly Decentralized Networks. Doctoral Thesis Nr. 16740, ETH Zurich (2006)

16. Moscibroda, T., von Rickenbach, P., Wattenhofer, R.: Analyzing the Energy-Latency Trade-off during the Deployment of Sensor Networks. In: Proc. of the 25th Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), (2006)

17. Moscibroda, T., Wattenhofer, R.: Coloring Unstructured Radio Networks. In: Proc. of the 17th ACM Symposium on Parallel Algorithms and Architectures (SPAA), pp. 39^8 (2005)

18. Moscibroda, T., Wattenhofer, R.: Maximal Independent Sets in Radio Networks. In: Proc. of the 23rd ACM Symposium on Principles of Distributed Computing (PODC), pp. 148-157 (2005)