eng
TS_pub
technospheramag
technospheramag
ТЕХНОСФЕРА_РИЦ
В статье рассмотрены основные принципы и режимы работы тактовой сетевой синхронизации, алгоритмы обнаружения и устранения замкнутых петель в сетях синхронизации, методы проектирования и модернизации сети, а также анализ структуры существующей сети. В качестве основного аппарата для описания сетей использована теория графов.
Теги: graph theory network synchronization triangular matrix синхронизация сети теория графов треугольная матрица
Развитие цифровых систем коммутации и систем передачи, разработка и внедрение технологии SDH привели к возрастанию роли системы синхронизации в сетях. Все операции по обработке сигналов в ЦСП должны выполняться в строгой временной последовательности, а приемное оборудование должно работать синхронно с передающим. Только в этом случае переданные сигналы попадут на приемной стороне в свои каналы и на отведенные им временные позиции.
При построении системы тактовой синхронизации сети SDH необходимо избегать формирования замкнутых петель, т.е. ни один из генераторов не должен синхронизироваться своим собственным сигналом, это может привести к уходу частоты генератора от номинального значения.
Основным инструментом для описания сетей служит теория графов. Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра – линиями, соединяющими точки. Петля – это дуга, начальная и конечная вершина которой совпадают. Для каждого графа можно составить соответствующую ему матрицу смежности.
Алгоритм нахождения замкнутых петель в направленном графе основывается на возведении матрицы смежности данного графа в ту же степень, что и порядок матрицы. Если после возведения в степень на главной диагонали матрицы останутся только нули, значит, в графе нет петель. Наличие ненулевых элементов на главной диагонали говорит о наличии петель в графе. Причем в петле будут участвовать те узлы, которым будут соответствовать ненулевые элементы диагонали.
Для примера рассмотрим SDH-сеть, состоящую из десяти элементов, и изобразим ее граф (рис.1). Направление стрелок графа указывает, какой генератор задающий, а какой ведомый. В данном случае генератор А задающий, B, C и D – вторичные генераторы, E, F и О – третичные генераторы. L и К – четверичные генераторы, они могут синхронизировать генератор М.
Построим матрицу А смежности данного графа. Единицами обозначим наличие связей между элементами сети, нулями – их отсутствие. При использовании данного метода не важно, с какого элемента начинать построение матрицы.
.
Так как получившаяся матрица – десятого порядка, для обнаружения петель в графе ее необходимо возвести в десятую степень. После возведения данной матрицы в десятую степень оказалось, что результат – нулевая матрица. Можно сделать вывод, что данная SDH-сеть не имеет замкнутых петель.
Данный способ обнаружения петель удобен лишь для малого количества элементов в сети, так как с ростом их числа порядок матрицы
смежности увеличивается. Увеличивается и степень, в которую эту матрицу необходимо возводить, а значит, и количество операций умножения и сложения тоже возрастет.
При проектировании сети синхронизации можно использовать свойство треугольной матрицы: при возведении такой матрицы в степень, равную ее порядку, на главной диагонали остаются только нулевые элементы. Если матрица смежности имеет треугольный вид:
то при возведении ее в квадрат элементы на главной диагонали останутся нулевыми. При возведении треугольной матрицы в более высокую степень она постепенно будет вырождаться в нулевую матрицу.
Полученная в ходе анализа SDH-сети матрица смежности может быть не треугольной. Однако если в результате перестановок строк и столбцов матрицу удается привести к тре-
угольному виду, то это означает, что SDH-сеть не имеет петель. В противном случае они есть.
На основании рассмотренного варианта анализа возникает вариант синтеза SDH-сети: элементы и связи надо добавлять так, чтобы матрица смежности оставалась треугольной.
Итак, если матрица смежности графа треугольная или приводится к треугольной перестановкой строк и столбцов, то в графе нет замк-нутых петель. Если матрица не треугольная и не приводится к треугольной, то в графе есть замкнутые петли. Расположение петель можно вычислить, возведя матрицу смежности в степень, равную ее порядку. Ненулевые элементы главной диагонали укажут местонахождение петель.
При построении графа по составленной тре-
угольной матрице смежности нужно учитывать, что порядок матрицы выбирается равным требуемому количеству элементов сети. Первыми элементами строк и столбцов будут элементы, соответствующие задающему и вторичным генераторам. Не все элементы матрицы, стоящие выше главной диагонали, должны быть единичными. При построении сети с древовидной архитектурой единичные элементы будут смещены ближе к главной диагонали.
Для примера построим сеть синхронизации, состоящую из десяти генераторов по древовидной архитектуре.
Составим матрицу смежности, отражающую возможные связи в направленном графе:
.
Направленный граф, соответствующий этой матрице, показан на рис.2. Полученный граф не имеет петель. Для проверки данного утверждения возведем матрицу смежности в десятую степень – получаем тот же результат.
Для использования метода построения сети по треугольной матрице смежности необходимо:
задать число элементов сети;
решить, какие элементы будут соответствовать задающему, вторичным и третичным генераторам;
составить треугольную матрицу, причем первыми элементами строк и столбцов выбрать те, которые соответствуют задающему, вторичным и третичным генераторам соответственно;
по полученной треугольной матрице построить направленный граф, стрелками изобразить наличие связей между элементами;
построить сеть SDH по направленному графу.
При проектировании сети синхронизации можно воспользоваться методом наращивания сети добавлением элементов. Новые элементы добавляются таким образом, чтобы матрица, отображающая связи направленного графа, оказалась треугольной. В этом случае замкнутых петель не получится.
При построении матрицы необходимо учитывать также то, что нумерация проводится, начиная от задающего генератора ко вторичным и третичным генераторам.
Для примера рассмотрена сеть, состоящая из трех элементов. Число элементов сети будем увеличивать до десяти. В данной сети генератор А – задающий. Генераторы В и С – вторичные. Граф, отображающий связи сети, показан на рис.3. Составим матрицу смежности для графа:
.
Данная матрица треугольная, из этого следует, что в графе нет петель.
Добавим к сети третичный генератор D и построим граф (рис.4).
Построим матрицу смежности. Элемент D добавлен так, чтобы матрица оставалось треугольной:
.
Далее добавим третичный генератор Е, который могут синхронизировать вторичный генератор С и третичный генератор D. Граф, отображающий связи в получившейся сети, показан на рис.5.
Построим матрицу смежности для получившегося графа. Элемент Е добавлен так, что матрица осталась треугольной, и следовательно, в графе нет петель:
.
К получившейся сети добавим третичный генератор F, который могут синхронизировать вторичный генератор С и третичный Е (рис.6). Построим матрицу, отражающую все возможные связи в данной сети. Так как эта матрица треугольная и при ее построении нумерация элементов сети проведена от высшего генератора к низшему, можно сказать, что в сети нет замкнутых петель.
Для использования метода добавления к сети по одному узлу необходимо:
построить направленный граф, состоящий из небольшого числа элементов, так чтобы его матрица смежности оказалась тре-
угольной;
последовательно добавить необходимое число элементов. При этом следить, чтобы матрица смежности была треугольной.
Проанализируем возможности упрощения алгоритма обнаружения петель. Для обнаружения петли в готовой сети необходимо составить матрицу смежности данной сети. Если матрица смежности треугольная, значит, в сети нет замкнутых петель. Если матрица не треугольная, то необходимо привести ее к треугольной. Для этого выбирается строка, содержащая наибольшее число единиц, и ставится первой. Второй будет строка, в которой единиц меньше, чем в первой, но больше, чем во второй, и т.д. Если ниже главной диагонали будут единицы, то необходимо переставить строки и столбцы матрицы, перенумеровав ее. Если матрицу нельзя привести к треугольной, то необходимо проверить наличие петель возведением матрицы в степень, равную ее порядку.
Имеющуюся сеть синхронизации можно разбить на подсети и оценить связи между ними.
Вначале проверим существование петель в сети, показанной на рис.7, с помощью возведения матрицы смежности в степень, равную ее порядку.
Матрица смежности имеет следующий вид:
.
Так как полученная матрица не треугольная, то по ней нельзя сказать, будут ли в графе петли. Для выявления петель матрица А была возведена в десятую степень, что доказало отсутствие замкнутых петель в графе рассматриваемой сети.
Этот способ обнаружения петель очень трудоемок. Разобьем имеющуюся сеть на подсети R, V и Т. Подсеть R состоит из генераторов А, В и С. Подсеть V состоит из генераторов D, F и E. Подсеть Т состоит из генераторов О, К, L и М (рис.8).
Составим матрицы смежности для полученных подсетей. При их составлении будем учитывать, что нумерацию необходимо начинать от задающего генератора ко вторичным и третичным.
Составим матрицу R:
.
Данная матрица смежности треугольная. Значит, в подсети R нет петель. Аналогично проверяются матрицы V и Т. Проверка показывает, что матрицы приводятся к треугольному виду, следовательно, подсети не имеют петель.
Составим матрицу смежности В. Она отражает связи между подсетями R, T и V:
.
Матрица смежности В треугольная. Значит, между подсетями R, V и T также нет замкнутых петель. А так как и в подсетях нет петель, можно сделать вывод, что петель нет во всей сети.
Метод обнаружения замкнутых петель разбиением сети на подсети можно использовать не всегда. Если же удается разбить сеть на несколько небольших сетей, то сложность вычислений значительно уменьшается.
Для использования данного метода необ-
ходимо:
разбить имеющуюся сеть на подсети;
построить направленный граф для каждой подсети;
составить для полученных графов их матрицы смежности. При составлении первыми элементами строк и столбцов выбирать те, которые соответствуют задающему и вторичным генераторам;
проанализировать, есть ли в графах подсетей петли. Если матрицы смежности треугольные, то замкнутых петель нет. Если же матрицы не треугольные, то проверить наличие петель возведением матрицы в степень, равную ее порядку;
если петель не обнаружено, составить матрицу, отражающую связи в подсетях.
проанализировать полученную матрицу аналогично.
Подводя итоги, можно сказать, что если матрица смежности графа треугольная или приводится к треугольной перестановкой строк и столбцов, то в графе нет замкнутых петель. Если матрица не треугольная и не приводится к треугольной, то в графе есть замкнутые петли. Расположение петель можно вычислить, возведя матрицу смежности в степень, равную ее порядку. Ненулевые элементы главной диагонали укажут местонахождение петель. ▪
При построении системы тактовой синхронизации сети SDH необходимо избегать формирования замкнутых петель, т.е. ни один из генераторов не должен синхронизироваться своим собственным сигналом, это может привести к уходу частоты генератора от номинального значения.
Основным инструментом для описания сетей служит теория графов. Граф – это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра – линиями, соединяющими точки. Петля – это дуга, начальная и конечная вершина которой совпадают. Для каждого графа можно составить соответствующую ему матрицу смежности.
Алгоритм нахождения замкнутых петель в направленном графе основывается на возведении матрицы смежности данного графа в ту же степень, что и порядок матрицы. Если после возведения в степень на главной диагонали матрицы останутся только нули, значит, в графе нет петель. Наличие ненулевых элементов на главной диагонали говорит о наличии петель в графе. Причем в петле будут участвовать те узлы, которым будут соответствовать ненулевые элементы диагонали.
Для примера рассмотрим SDH-сеть, состоящую из десяти элементов, и изобразим ее граф (рис.1). Направление стрелок графа указывает, какой генератор задающий, а какой ведомый. В данном случае генератор А задающий, B, C и D – вторичные генераторы, E, F и О – третичные генераторы. L и К – четверичные генераторы, они могут синхронизировать генератор М.
Построим матрицу А смежности данного графа. Единицами обозначим наличие связей между элементами сети, нулями – их отсутствие. При использовании данного метода не важно, с какого элемента начинать построение матрицы.
.
Так как получившаяся матрица – десятого порядка, для обнаружения петель в графе ее необходимо возвести в десятую степень. После возведения данной матрицы в десятую степень оказалось, что результат – нулевая матрица. Можно сделать вывод, что данная SDH-сеть не имеет замкнутых петель.
Данный способ обнаружения петель удобен лишь для малого количества элементов в сети, так как с ростом их числа порядок матрицы
смежности увеличивается. Увеличивается и степень, в которую эту матрицу необходимо возводить, а значит, и количество операций умножения и сложения тоже возрастет.
При проектировании сети синхронизации можно использовать свойство треугольной матрицы: при возведении такой матрицы в степень, равную ее порядку, на главной диагонали остаются только нулевые элементы. Если матрица смежности имеет треугольный вид:
то при возведении ее в квадрат элементы на главной диагонали останутся нулевыми. При возведении треугольной матрицы в более высокую степень она постепенно будет вырождаться в нулевую матрицу.
Полученная в ходе анализа SDH-сети матрица смежности может быть не треугольной. Однако если в результате перестановок строк и столбцов матрицу удается привести к тре-
угольному виду, то это означает, что SDH-сеть не имеет петель. В противном случае они есть.
На основании рассмотренного варианта анализа возникает вариант синтеза SDH-сети: элементы и связи надо добавлять так, чтобы матрица смежности оставалась треугольной.
Итак, если матрица смежности графа треугольная или приводится к треугольной перестановкой строк и столбцов, то в графе нет замк-нутых петель. Если матрица не треугольная и не приводится к треугольной, то в графе есть замкнутые петли. Расположение петель можно вычислить, возведя матрицу смежности в степень, равную ее порядку. Ненулевые элементы главной диагонали укажут местонахождение петель.
При построении графа по составленной тре-
угольной матрице смежности нужно учитывать, что порядок матрицы выбирается равным требуемому количеству элементов сети. Первыми элементами строк и столбцов будут элементы, соответствующие задающему и вторичным генераторам. Не все элементы матрицы, стоящие выше главной диагонали, должны быть единичными. При построении сети с древовидной архитектурой единичные элементы будут смещены ближе к главной диагонали.
Для примера построим сеть синхронизации, состоящую из десяти генераторов по древовидной архитектуре.
Составим матрицу смежности, отражающую возможные связи в направленном графе:
.
Направленный граф, соответствующий этой матрице, показан на рис.2. Полученный граф не имеет петель. Для проверки данного утверждения возведем матрицу смежности в десятую степень – получаем тот же результат.
Для использования метода построения сети по треугольной матрице смежности необходимо:
задать число элементов сети;
решить, какие элементы будут соответствовать задающему, вторичным и третичным генераторам;
составить треугольную матрицу, причем первыми элементами строк и столбцов выбрать те, которые соответствуют задающему, вторичным и третичным генераторам соответственно;
по полученной треугольной матрице построить направленный граф, стрелками изобразить наличие связей между элементами;
построить сеть SDH по направленному графу.
При проектировании сети синхронизации можно воспользоваться методом наращивания сети добавлением элементов. Новые элементы добавляются таким образом, чтобы матрица, отображающая связи направленного графа, оказалась треугольной. В этом случае замкнутых петель не получится.
При построении матрицы необходимо учитывать также то, что нумерация проводится, начиная от задающего генератора ко вторичным и третичным генераторам.
Для примера рассмотрена сеть, состоящая из трех элементов. Число элементов сети будем увеличивать до десяти. В данной сети генератор А – задающий. Генераторы В и С – вторичные. Граф, отображающий связи сети, показан на рис.3. Составим матрицу смежности для графа:
.
Данная матрица треугольная, из этого следует, что в графе нет петель.
Добавим к сети третичный генератор D и построим граф (рис.4).
Построим матрицу смежности. Элемент D добавлен так, чтобы матрица оставалось треугольной:
.
Далее добавим третичный генератор Е, который могут синхронизировать вторичный генератор С и третичный генератор D. Граф, отображающий связи в получившейся сети, показан на рис.5.
Построим матрицу смежности для получившегося графа. Элемент Е добавлен так, что матрица осталась треугольной, и следовательно, в графе нет петель:
.
К получившейся сети добавим третичный генератор F, который могут синхронизировать вторичный генератор С и третичный Е (рис.6). Построим матрицу, отражающую все возможные связи в данной сети. Так как эта матрица треугольная и при ее построении нумерация элементов сети проведена от высшего генератора к низшему, можно сказать, что в сети нет замкнутых петель.
Для использования метода добавления к сети по одному узлу необходимо:
построить направленный граф, состоящий из небольшого числа элементов, так чтобы его матрица смежности оказалась тре-
угольной;
последовательно добавить необходимое число элементов. При этом следить, чтобы матрица смежности была треугольной.
Проанализируем возможности упрощения алгоритма обнаружения петель. Для обнаружения петли в готовой сети необходимо составить матрицу смежности данной сети. Если матрица смежности треугольная, значит, в сети нет замкнутых петель. Если матрица не треугольная, то необходимо привести ее к треугольной. Для этого выбирается строка, содержащая наибольшее число единиц, и ставится первой. Второй будет строка, в которой единиц меньше, чем в первой, но больше, чем во второй, и т.д. Если ниже главной диагонали будут единицы, то необходимо переставить строки и столбцы матрицы, перенумеровав ее. Если матрицу нельзя привести к треугольной, то необходимо проверить наличие петель возведением матрицы в степень, равную ее порядку.
Имеющуюся сеть синхронизации можно разбить на подсети и оценить связи между ними.
Вначале проверим существование петель в сети, показанной на рис.7, с помощью возведения матрицы смежности в степень, равную ее порядку.
Матрица смежности имеет следующий вид:
.
Так как полученная матрица не треугольная, то по ней нельзя сказать, будут ли в графе петли. Для выявления петель матрица А была возведена в десятую степень, что доказало отсутствие замкнутых петель в графе рассматриваемой сети.
Этот способ обнаружения петель очень трудоемок. Разобьем имеющуюся сеть на подсети R, V и Т. Подсеть R состоит из генераторов А, В и С. Подсеть V состоит из генераторов D, F и E. Подсеть Т состоит из генераторов О, К, L и М (рис.8).
Составим матрицы смежности для полученных подсетей. При их составлении будем учитывать, что нумерацию необходимо начинать от задающего генератора ко вторичным и третичным.
Составим матрицу R:
.
Данная матрица смежности треугольная. Значит, в подсети R нет петель. Аналогично проверяются матрицы V и Т. Проверка показывает, что матрицы приводятся к треугольному виду, следовательно, подсети не имеют петель.
Составим матрицу смежности В. Она отражает связи между подсетями R, T и V:
.
Матрица смежности В треугольная. Значит, между подсетями R, V и T также нет замкнутых петель. А так как и в подсетях нет петель, можно сделать вывод, что петель нет во всей сети.
Метод обнаружения замкнутых петель разбиением сети на подсети можно использовать не всегда. Если же удается разбить сеть на несколько небольших сетей, то сложность вычислений значительно уменьшается.
Для использования данного метода необ-
ходимо:
разбить имеющуюся сеть на подсети;
построить направленный граф для каждой подсети;
составить для полученных графов их матрицы смежности. При составлении первыми элементами строк и столбцов выбирать те, которые соответствуют задающему и вторичным генераторам;
проанализировать, есть ли в графах подсетей петли. Если матрицы смежности треугольные, то замкнутых петель нет. Если же матрицы не треугольные, то проверить наличие петель возведением матрицы в степень, равную ее порядку;
если петель не обнаружено, составить матрицу, отражающую связи в подсетях.
проанализировать полученную матрицу аналогично.
Подводя итоги, можно сказать, что если матрица смежности графа треугольная или приводится к треугольной перестановкой строк и столбцов, то в графе нет замкнутых петель. Если матрица не треугольная и не приводится к треугольной, то в графе есть замкнутые петли. Расположение петель можно вычислить, возведя матрицу смежности в степень, равную ее порядку. Ненулевые элементы главной диагонали укажут местонахождение петель. ▪
Отзывы читателей
