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

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

Описание графа G** = (U, Г**) может быть оформлено в виде матрицы U = ║U_ij║ размером N×N, где N – число дуг в исходном графе G = (E, Г). Столбцы и строки такой матрицы должны соответствовать дугам исходного графа, а элементы U_ij содержать следующую информацию:

Пример такой матрицы, составленной для приведённого на рисунке 2.2 исходного графа, представлен на рисунке 21:

Рисунок 21

(для удобства чтения, дуги обозначены соответствующими им парами вершин исходного графа).

Данной матрице соответствует граф G** = (U, Г**), показанный на рисунке 22:

 

Рисунок 22

Сравнивая приведённые на рисунках 14 и 22 графы, отметим, что описание графа G** = (U, Г**) более громоздко, чем описание графа G* = (E, Г*). Это объясняется тем, что в исходном графе G = (E, Г) число дуг превышает число вершин.

И, если функциональная избыточность сети достаточно высока – число вершин в графе G**=(U, Г**) будет очень велико, и число «красок» будет мало отличаться от числа дуг в исходном графе.  В предельном же случае, когда граф  G = (E, Г) будет представлять собой «клику», то есть отвечать условию (7):    

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

Число таких слотов будет определяться выражением (8):

где n – число вершин в графе G = (E, Г).

Если же отказаться от идеи распределения слотов по радиолучам, и распределять слоты по узлам, то число слотов будет равняться величине n. Так, если «клика» включает в себя 16 узлов, то при распределении слотов по радиолучам, необходимо предусмотреть организацию 240 слотов, а при распределении по узлам – всего 16.

Казалось бы, сама идея распределения слотов по радиолучам - нерациональна. Однако, если считать, что выделение временных слотов должно производиться для ограниченного числа пользователей, то их число может оказаться небольшим. Например, (см. рисунок 23), для организации дуплексного соединения между узлами X₁ и X₅, потребуются всего два временных слота.

Рисунок 23

По-видимому, этот вопрос требует более детального рассмотрения. И очевидно, что он тесно связан с алгоритмами решения задачи раскраски графов.

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

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

Следует отметить, что, в общем случае, граф коллизий G* = (E, Г*) может обладать семейством внутренне устойчивых подмножеств и не иметь таких подмножеств вообще – всё зависит от конфигурации исходного графа G = (E, Г).

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

Сказанное относится и к задаче «бесконфликтной» раскраске радиолучей. Только в данном случае должен быть построен граф коллизий иного вида – граф      G** = (U, Г**), причём множество вершин этого графа должно соответствовать дугам исходного графа - G = (E, Г), а отображения Г** – указывать на «конфликтные» радиолучи.

«Конфликтность» радиолучей может быть определена следующими правилами:

1)      каждый узел не должен осуществлять передачу информации одновременно по двум и более радиолучам;

2)      любой узел не может одновременно принимать информацию от двух и более узлов;

3)      ни один из узлов не способен к одновременной передаче и приёму пакетов.

Более точно, эти правила будут выглядеть следующим образом:

1)      «вершина» графа G** = (U, Г**), поставленная в соответствие дуге (X_i, X_j) должна считаться «конфликтной» для любой другой дуги G=(E, Г), если эти дуги исходят из одной и той же вершины X_i. Например, фрагменту исходного графа G = (E, Г), который изображён на рисунке 15

Рисунок 15

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

Рисунок 16

2)      аналогичным образом, «вершина» графа G** = (U, Г**), поставленная в соответствие дуге (X_i, X_j) должна считаться «конфликтной» для любой другой дуги G = (E, Г), если эти дуги заходят в одну и ту же вершину X_j. Например, (см. рисунки 17 и 18), дуги (X₁, X₂), (X₃, X₂) и (X₄, X₂) будут также являться «конфликтными», и все соответствующие им вершины в графеG** = (U, Г**) должны считаться смежными.

Рисунок 17

Рисунок 18

3)      наконец, любая пара дуг (X_i, X_k) и (X_k, X_j), первая из которых заходит в вершину X_kисходного графа G = (E, Г), а вторая выходит из той же вершины того же графа, также должны считаться «конфликтными» - см. рисунки 19 и 20:

Рисунок 19

 

Рисунок 20

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

Анализ существующих протоколов 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₄.

Анализ существующих протоколов 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

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