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

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

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

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

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

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

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

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

Рисунок 6

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

Рисунок 7

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

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

Рисунок 8

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

Рисунок 9

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

Элемент матрицы смежности - A=║A_ij║ определяются условиями (3):

1)      «тупиковые» вершины, отвечающие условию (2) – таким вершинам будут соответствовать строки, состоящие из сплошных нулей;

2)      подмножества вершин  – таким вершинам будут соответствовать элементы A_ij=1.

Пример матрицыA, (которая соответствует изображённому на рисунке 2 графу), представлен на рисунке 10.

Рисунок 10

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