Аноним

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

Материал из WEGA
Строка 18: Строка 18:




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




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




Определение 4 (минимальная раскраска вершин). Пусть дан граф G = (V, E). Правильная раскраска вершин графа G представляет собой назначение цвета c(v) каждой вершине v 2 V, такого, что c(u) ф c(v) любых двух соседних вершин (u; v) 2 E. Минимальная раскраска – это правильная раскраска, при которой количество используемых цветов минимально.
'''Определение 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>. Минимальная раскраска – это правильная раскраска, при которой количество используемых цветов минимально.




Строка 30: Строка 30:




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


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


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


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


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




Строка 44: Строка 44:




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


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

правка