Алгоритм DESYNC. Достоинства и недостатки

Алгоритм DESYNC. Достоинства и недостатки.
Часть 2. 

3.      Позитивные свойства  алгоритма и его недостатки

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

Пользователю сети достаточно знать допустимое число абонентов в «клике», которое ограничено возможностями используемых технических средств и задано разработчиком изделия как некая константа.

Это объясняется тем, что, при использовании алгоритма DESYNC, узлы сети определяют моменты передачи собственных синхросигналов автономно,  опираясь лишь на  показания собственных «часов», ход которых корректируется в моменты приёма «синхросигналов» от соседей. При этом  данный алгоритм игнорирует такие атрибуты узлов, как идентификаторы (адреса) соседних узлов, их число, статус и т.п.  

3.2. Рассматриваемый алгоритм обладает свойством «самоадаптации» - добавление или удаление того или иного узла не приведёт к потере синхронизма. Возникающий при этом «дисбаланс» фаз вызовет лишь  их коррекцию в узлах сети, причём, по окончании соответствующего переходного процесса, сеть войдёт в стационарный режим. То же самое будет происходить при поражениях или спонтанных отказах узлов.  

3.3. Использование данного алгоритма обеспечивает «справедливое» деление временных интервалов между узлами -  в стационарном режиме (в независимости от числа узлов) интервалы времени между передачами очередных синхросигналов – T / n будут распределены равномерно.

Эта особенность может оказаться полезной при случайных сбоях и временных потерях радиослышимости – если число абонентов в сети невелико, то случайные сбои, которые могут спровоцировать резкие скачки фаз, далеко не всегда приведут к коллизиям. Такие события будут всегда приводить к увеличению длин интервалов T / n, что увеличивает шансы на успех  при возврате элементов сети к прежнему состоянию.  Вообще, любая подобная ситуация может рассматриваться как «штатная».

 3.4. Однако следует отметить, что использование рассматриваемого протокола эффективно только в том случае, если топология сети отвечает условию (9):

то есть сеть является «кликой».

Если же условие (9) соблюдаться не будет, то сеть может оказаться в состоянии «перманентного переходного процесса», который может быть проиллюстрирован следующим примером.

Допустим, что сеть состоит из трёх узлов и её топология соответствует графу, который изображён на рисунке 2:

Рисунок 2

Представим себе, что в сети работают только два узла – X_a и X_b, и моменты выдачи «синхросигналов» этими узлами, соответствуют временному циклу, представленному на рисунке 3:

Рисунок 3

Теперь представим себе, что, после очередной коррекции фазы в узле X_b, к сети подключился узел X_с,  и следующий цикл T будет соответствовать рисунку 4:

Рисунок 4

Такая ситуация приведёт к сдвигу фазы узла X_b, причём «новая» фаза этого узла будет стремиться к середине интервала времени между выдачей «синхросигналов» от узла X_a (воспринимаемого как узел X_b-1) и X_с (воспринимаемого как узел X_b+1).

Но, поскольку «новая» фаза узла X_b  обнаружится только в следующем цикле, резких скачков фаз в узлах X_a и X_с  не произойдёт. Произойдут лишь следующие события:

1)      узел X_c зафиксирует длину интервала Δ_с(t), воспринимая  X_b  как источник «синхросигнала» от  мнимого  узла X_c-1;

2)      узел X_a  зафиксирует либо длину интервала Δ_a(t), либо длину интервала Δ_a+1(t)  (в последнем случае процедуры коррекции фазы в узле X_a будут выполнены, но фаза этого узла практически не изменится).

Далее, последовательность событий может развиваться по следующему сценарию:

- получив  следующий «синхросигнал» от X_b, узел X_с сдвинет свою фазу так, что момент выдачи «синхросигнала» X_c  в следующем цикле будет смещён в сторону X_a, (см. рисунок 5):

Рисунок 5

- если узел X_a воспринимает «синхросигнал» от X_b как сигнал от источника X_a+1, то он также сдвинет свою фазу, но в противоположенную сторону – навстречу X_с (см. рисунок 6):

Рисунок 6

- возникает коллизия, в результате чего узел X_b перестанет воспринимать сигналы от своих соседей и будет менять свою фазу только за счёт погрешности собственных «часов»;

- однако «дрейф» фазы X_b не улучшит сложившуюся ситуацию, поскольку узлы X_a и X_c будут всегда стремиться занять один и тот же слот.

Возможны другие (может и более благополучные) сценарии, но приведённого примера вполне достаточно, чтобы убедиться в том, что использование алгоритмов DESYNC в сетях, не отвечающих условию (9), не имеет смысла.

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

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

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

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

Рисунок 21

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

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

 

Рисунок 22

Сравнивая приведённые на рисунках 14 и 22 графы, отметим, что описание графа G** = (U, Г**) более громоздко, чем описание графа G* = (E, Г*). Это объясняется тем, что в исходном графе G = (E, Г) число дуг превышает число вершин.

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

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

Число таких слотов будет определяться выражением (8):

где n – число вершин в графе G = (E, Г).

Если же отказаться от идеи распределения слотов по радиолучам, и распределять слоты по узлам, то число слотов будет равняться величине n. Так, если «клика» включает в себя 16 узлов, то при распределении слотов по радиолучам, необходимо предусмотреть организацию 240 слотов, а при распределении по узлам – всего 16.

Казалось бы, сама идея распределения слотов по радиолучам - нерациональна. Однако, если считать, что выделение временных слотов должно производиться для ограниченного числа пользователей, то их число может оказаться небольшим. Например, (см. рисунок 23), для организации дуплексного соединения между узлами X₁ и X₅, потребуются всего два временных слота.

Рисунок 23

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

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

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

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

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

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

«Конфликтность» радиолучей может быть определена следующими правилами:

1)      каждый узел не должен осуществлять передачу информации одновременно по двум и более радиолучам;

2)      любой узел не может одновременно принимать информацию от двух и более узлов;

3)      ни один из узлов не способен к одновременной передаче и приёму пакетов.

Более точно, эти правила будут выглядеть следующим образом:

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

Рисунок 15

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

Рисунок 16

2)      аналогичным образом, «вершина» графа G** = (U, Г**), поставленная в соответствие дуге (X_i, X_j) должна считаться «конфликтной» для любой другой дуги G = (E, Г), если эти дуги заходят в одну и ту же вершину X_j. Например, (см. рисунки 17 и 18), дуги (X₁, X₂), (X₃, X₂) и (X₄, X₂) будут также являться «конфликтными», и все соответствующие им вершины в графеG** = (U, Г**) должны считаться смежными.

Рисунок 17

Рисунок 18

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

Рисунок 19

 

Рисунок 20

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

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