вторник, 4 июня 2013 г.

Анализ существующих протоколов TDMA


Анализ существующих протоколов TDMA
Часть 2


Для определения возможных коллизий между узлами (для последующей раскраски вершин графа)  можно воспользоваться  методикой, основанной на следующих рассуждениях.

Будем считать, что ни один, привязанный к одной и той же частоте узел, не может осуществлять одновременный приём и передачу информации. Следовательно, узел Xiне должен использовать слоты узлов Xj, которые отвечают условию (1):


Исключение могут составлять вершины Xz, отвечающие условию (2):


поскольку такие вершины лишены возможности передачи информации.


Однако основная причина возможных коллизий – претендующие на один и тот же узел Xiвершины, составляющие подмножество Г-1Xi, поэтому каждому узлу  должен быть назначен отдельный слот.

Потенциальные возможности коллизий могут быть описаны графом коллизий G* = (E, Г*), множество вершин которого совпадает с множеством вершин графа радиослышимости - = (E, Г), а дуги – соответствовать парам узлов, которые могут «мешать» друг другу. Например, если в исходный граф G = (E, Г) имеет вид, показанный на рисунке 6:




Рисунок 6



то все потенциальные коллизии могут быть описаны графом G*=(E, Г*), представленным на рисунке 7:


Рисунок 7



Такой вид графа G*=(E, Г*) объясняется тем, что вершина Xiявляется «тупиковой», то есть отвечает условию (2).
Иной результат будет получен в том случае, если это  условие выполняться не будет. Например, если граф G=(E, Г) будет иметь вид, показанный на рисунке 8:


Рисунок 8


то граф G*=(E, Г*) будет иметь другую структуру – см. рисунок 9:

Рисунок 9




Задача синтеза  графа коллизий может быть решена в общем виде. Для этого достаточно иметь формальное описание исходного графа G=(E, Г), которое может быть оформлено в виде матрицы смежности -A.
Элемент матрицы смежности - A=║Aij║ определяются условиями (3):


1)      «тупиковые» вершины, отвечающие условию (2) – таким вершинам будут соответствовать строки, состоящие из сплошных нулей;
2)      подмножества вершин  – таким вершинам будут соответствовать элементы Aij=1.
Пример матрицыA, (которая соответствует изображённому на рисунке 2 графу), представлен на рисунке 10.



Рисунок 10

Мы продолжим обсуждение темы в следующей части.

Комментариев нет:

Отправить комментарий