вторник, 28 мая 2013 г.

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




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

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


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

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

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


Рисунок 2


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


На основании такой раскраски, можно принять следующее решение:
-          узлам X1, X2 и X5 должны соответствовать разные слоты;
-          узлыX3 и X4 могут использовать один и тот же слот;
-          узел X6 не нуждается в слоте (поскольку этот узел никто «не слышит»).

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

Рисунок 4


Согласно приведённой на рисунке 5 диаграмме, передача пакетов в такой сети может осуществляться в следующей последовательности:
1)  первый(«красный») слот может использоваться для передачи информации по радиолучам (X1, X4), (X3, X6) и (X5, X2);
2)      второй («зелёный») слот – для передачи по радиолучам (X2, X1) и (X4, X5);
3)      третий («жёлтый») слот – по радиолучу (X2, X3);
4)      четвёртый («синий») слот – по радиолучу (X1, X2);
5)      наконец, пятый («чёрный») слот может  использоваться для передачи информации по радиолучу (X3, X2).
Рисунок 5

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