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

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