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

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