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

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