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

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