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

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

Имея подобную информацию можно построить «матрицу коллизий» - C=║C_ij║, элементы которой могут принимать следующие значения:

Для этого достаточно:

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

Рисунок 11

2) построить матрицу коллизий –C=║C_ij║, действуя следующим образом:

- поочерёдно просмотреть всестолбцы скорректированной матрицы A;

- при просмотре элементов каждого столбца этой матрицы, составить список вершин – E_j, отвечающих условию (4):

Aij= 1

(4)

например, (см. рисунок 2.11)  рассматривая столбец, поставленный в соответствие вершине X₁, будем иметь список (2.5):

E1= {X1, X2}

(5)

- каждой паре вершин этого списка поставить  в соответствие элемент C_ij=1.

(списку E₁ будут соответствовать элементы матрицы C, которые показаны на рисунке  12)

Рисунок 12

Далее, действуя аналогичным образом можно получить матрицу C следующего содержания (см. рисунок 13)

Рисунок 13

поскольку, исходя из содержания приведённой на рисунке 11 матрицы, будем иметь:

E1 = {X1, X2}

E2 = {X1, X2, X3, X5}

E3 = {X2, X3,}

E4 = {X1, X4}

E5 = {X4, X5}

E6 = {X3, X5}

Полученной таким образом матрице C=║C_ij║ будет соответствовать граф коллизий G*=(E, Г*), представленный на рисунке 14.

Рисунок 14

Построив подобный граф можно отыскать подмножества узлов, которые могут использовать один и тот же слот, не «мешая» друг другу.

В графе G*=(E, Г*) такие подмножества будут являться внутренне устойчивыми,  то есть отвечать условию (6):

 

Иными словами, никакие две вершины из S_k не смежны.

Если отбросить изолированную вершину X₆, то в представленном на рисунке 14 графе таких подмножеств - два:

1)      S₁= {X₂, X₄} –выделенное штриховыми линиями;

2)      S₂ = {X₃, X₄} – выделенное штрих-пунктирными линиями.

Исходя из этого, можно прийти к следующему выводу: вершины приведённого на рисунке 2  графа G=(E, Г) могут быть окрашены четырьмя цветами, причём возможно два равноценных решения: первое - с одинаковой окраской вершин X₂ и X₄, второе - с одинаковой окраской вершин X₃ и X₄.