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

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


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

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

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

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

«Конфликтность» радиолучей может быть определена следующими правилами:
1)      каждый узел не должен осуществлять передачу информации одновременно по двум и более радиолучам;
2)      любой узел не может одновременно принимать информацию от двух и более узлов;
3)      ни один из узлов не способен к одновременной передаче и приёму пакетов.

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

Рисунок 15


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

Рисунок 16

2)      аналогичным образом, «вершина» графа G** = (U, Г**), поставленная в соответствие дуге (Xi, Xj) должна считаться «конфликтной» для любой другой дуги = (E, Г), если эти дуги заходят в одну и ту же вершину Xj. Например, (см. рисунки 17 и 18), дуги (X1, X2), (X3, X2) и (X4, X2) будут также являться «конфликтными», и все соответствующие им вершины в графеG** = (U, Г**) должны считаться смежными.



Рисунок 17


Рисунок 18



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

Рисунок 19

 

Рисунок 20


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

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

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