среда, 26 июня 2013 г.

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



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

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



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

Рисунок 21

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

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

 
Рисунок 22


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




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





где n – число вершин в графе = (E, Г).
Если же отказаться от идеи распределения слотов по радиолучам, и распределять слоты по узлам, то число слотов будет равняться величине n. Так, если «клика» включает в себя 16 узлов, то при распределении слотов по радиолучам, необходимо предусмотреть организацию 240 слотов, а при распределении по узлам – всего 16.
Казалось бы, сама идея распределения слотов по радиолучам - нерациональна. Однако, если считать, что выделение временных слотов должно производиться для ограниченного числа пользователей, то их число может оказаться небольшим. Например, (см. рисунок 23), для организации дуплексного соединения между узлами X1 и X5, потребуются всего два временных слота.

Рисунок 23

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


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

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