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

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

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

Анализ существующих протоколов TDMA
Часть1. Постановка задачи и возможные подходы к её решению

При уплотнении с временным разделением (Time Division Multiplexing - TDM) распределение каналов идёт по времени, то есть передатчики передают или ретранслируют пакет на одной и той же частоте f в области s, но в различные промежутки времени t_i (циклически повторяющиеся через интервал ΔT).

Например, (см. рисунок 1) каждому потенциальному передатчику – узлу X_i может быть выделен конкретный интервал времени – слот  t_i, который не может быть использован другими конкурентными узлами.

Рисунок 1

Подобная схема достаточно удобна, так как временные интервалы могут динамично перераспределяться между устройствами сети – устройствам с большим трафиком могут назначаться большее число интервалов, чем устройствам с меньшим объёмом трафика. Но главное преимущество такой схемы – существенное уменьшение риска коллизий, (правда, только в том случае, если сеть будет отвечать достаточно строгим требованиям к синхронизации процессов передачи).

Очевидно, что использование рассмотренной схемы распределения слотов немыслимо без какого-либо механизма составления расписаний, задающего очерёдность выхода в эфир для всех узлов сети. При этом следует стремиться к тому, чтобы число слотов в одном интервале ΔT было минимальным,  поскольку основные задержки передачи пакетов будут определяться не столько временем передачи пакета, а сколько числом слотов в таком интервале.

Следует отметить, что данная задача достаточно сложна и трудоёмка, и её решение должно быть основано на знании структуры сети, которые позволят определить подмножества узлов или радиолучей, которые расположены в разных зонах радиослышимости, и, следовательно, могут использовать один и тот же временной слот.

Суть этой задачи заключается в следующем.Пусть сеть (или, точнее, её фрагмент, работающий на одной и той же частоте f) описывается ориентированным графом G=(E, Г), в котором

- Е – множество вершин, поставленных в соответствие узлам сети;

-  Г – однозначные соответствия между вершинами множества Е.

В качестве примера рассмотрим граф, изображенный на рисунке 2:

Рисунок 2

Множество вершин такого графа может быть «расфасовано» таким образом, что каждой вершине будет  соответствовать «цвет» - S_k, определяющий принадлежность вершины к конкретному подмножеству узлов, которые могут выходить в эфир одновременно. (Подмножество S_k может включать в себя от одного до нескольких узлов).

Например, (см. рисунки 2 и 3) вершины рассматриваемого графа могут быть раскрашены следующим образом:

Рисунок 3

На основании такой раскраски, можно принять следующее решение:

-          узлам X₁, X₂ и X₅ должны соответствовать разные слоты;

-          узлыX₃ и X₄ могут использовать один и тот же слот;

-          узел X₆ не нуждается в слоте (поскольку этот узел никто «не слышит»).

Возможен и другой подход. Распределение слотов может быть основано на раскраске дуг (радиолучей). Например, на основании раскраски дуг, показанной на рисунке 4, расписание выхода в эфир может соответствовать временной диаграмме, которая представлена на рисунке 5.

Рисунок 4

Согласно приведённой на рисунке 5 диаграмме, передача пакетов в такой сети может осуществляться в следующей последовательности:

1)  первый(«красный») слот может использоваться для передачи информации по радиолучам (X₁, X₄), (X₃, X₆) и (X₅, X₂);

2)      второй («зелёный») слот – для передачи по радиолучам (X₂, X₁) и (X₄, X₅);

3)      третий («жёлтый») слот – по радиолучу (X₂, X₃);

4)      четвёртый («синий») слот – по радиолучу (X₁, X₂);

5)      наконец, пятый («чёрный») слот может  использоваться для передачи информации по радиолучу (X₃, X₂).

Рисунок 5

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

Возможная структура управления в самоорганизующихся системах связи

Исходя из приведенного примера, можно сделать следующие выводы:

1) Свойства и характеристики системы и её окружающей среды могут изменяться во времени, причём законы, по которым они изменяются, далеко не всегда поддаются прогнозу. Тем не менее, управление системой без знаний о её состоянии и состоянии среды (и, самое главное - имеющихся ресурсов) практически невозможно.

2) Состояние системы определяется весьма большим числом факторов, поэтому число управляющих воздействий на элементы системы и среду, а также объёмы соответствующей управляющей информации могут оказаться весьма большими.

3) Время, которое требуется на поиск оптимального решения, увеличивается по мере увеличения числа взаимодействующих элементов системы. В свою очередь решение, найденное в результате длительных вычислений, может потерять свою ценность из-за несвоевременного его получения или запоздалого использования.

На первый взгляд, перечисленные трудности могут оказываться вполне преодолимыми, если отказаться от стремления построить идеальную систему, которая способна мгновенно отыскать и осуществить строго оптимальное решение в любой ситуации.

Действительно, система может требовать не оптимального, а лишь достаточно хорошего (рационального) управления. Например, управление системой, может быть основано на использовании относительно небольшого числа «шаблонных» решений.

Но, даже придерживаясь подобной точки зрения, следует учитывать, что возможности человека в отношении восприятия и переработки информации ограничены. Даже самый талантливый администратор (или служба) может принимать решения только на основании учёта относительно небольшого числа факторов и весьма грубых прогнозов, и, самое главное, будет затрачивать довольно много времени на их обдумывание. Это обстоятельство лишает систему возможности осуществлять управление на достаточно высоком уровне.

Другая крайняя точка зрения – основана на внедрении во все комплексы дополнительных элементов, обеспечивающих автоматическое решение всех задач управления без участия людей. Но такой подход практически исключает возможность административного управления воздействиями на систему «извне», если для осуществления таких воздействий требуется привлечение обслуживающего персонала системы (ремонтных бригад, операторов, экспедиторов и т.п.).

Возможный подход к решению задач управления и «самоорганизации».

1) Задача управления системой разбивается на несколько подзадач или слоев:

● управление ресурсами канального и физического уровней;

● управление ресурсами сетевого уровня;

● управление безопасностью;

● прочие

2) Каждая из этих подзадач решается в какой-то степени автономно, однако все подзадачи должны быть подчинены одной и той же цели - поддержке высокого уровня надёжности и живучести системы. Эти задачи взаимосвязаны и взаимозависимы: например, несоответствие радиочастот и маршрутов у абонентов одного и того же канала приведёт к невозможности передачи/приёма пакетов по этому каналу, использование топологии системы, в составе которой указаны «неорганизованные» каналы приведёт к неверному расчету маршрутов.

3) Получив все настроечные данные, система «самоорганизуется»: на основании исходных данных каждая станция способна, как рассчитать все необходимые маршруты, так и «перерасчитать» их, в случае спонтанной реконфигурации системы. Для обеспечения такой возможности может использоваться протокол динамической маршрутизации, обеспечивающий широковещательную рассылку информации об изменениях состояний связей (типа OSPF или OLSR).

4) Управление ресурсами системы должно осуществляться централизовано: администратором системы со специально выделенного автоматизированного рабочего места (АРМ). Для эффективного управления системой, АРМ должно обеспечивать:

● наглядную интерпретацию текущей топологии системы и её ресурсов;

● оценку возможности дистанционной доставки служебной (настроечной) информации оборудованию при осуществлении манёвров частотами, каналами и т.д.;

● оценку последствий возможных решений администратора системы (потери/восстановления топологической связности и т.п.);

● оповещение администратора о возникновении нештатных ситуаций, требующих вмешательства соответствующего технического персонала (ремонтных бригад, экспедиторов и т.п.);

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