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

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

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

'''Определение 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>. Минимальная раскраска – это правильная раскраска, при которой количество используемых цветов минимально.