Метод повышения структурной устойчивости цифровых систем передачи информации с использованием их спектральных характеристик

Размещено на http://www.allbest.ru/

МЕТОД ПОВЫШЕНИЯ СТРУКТУРНОЙ УСТОЙЧИВОСТИ ЦИФРОВЫХ СИСТЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ С ИСПОЛЬЗОВАНИЕМ ИХ СПЕКТРАЛЬНЫХ ХАРАКТЕРИСТИК

А.М. Межуев, Д.Л. Стуров

Воронеж, Россия

Аннотация

Ключевые слова: цифровая система; графовая модель; базовая топология; структурная устойчивость; спектральный анализ.

Work is devoted working out of the method ensuring deriving of structurally steady digital system of information transfer. At a problem solution the approach based on use of mathematical apparatus of the spectral graph theory is offered. Algorithms of correction of the base topology are developed, allowing to define kospectral topology with demanded structural performances. Outcomes of modelling for concrete variants of structural construction of systems have confirmed working capacity and a practical realizability of the offered method.

Keywords: digital system; graph model; base topology; structural stability; the spectral analysis.

Содержание

• Введение
• 1. Этапы метода
• Заключение
• Литература

Введение

Анализ общепринятых подходов к обеспечению структурной устойчивости ЦСПИ показал, что они сводятся к решению многокритериальной оптимизационной задачи и имеют ряд недостатков, в том числе: сложность математических выкладок, высокие вычислительные затраты, достаточно грубое упрощение моделей, приводящее к снижению точности решения [1].

В данной работе предлагается новый подход к решению задачи обеспечения структурной устойчивости ЦСПИ, основанный на использовании математического аппарата спектральной теории графов.

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

1. Этапы метода

Предлагаемый метод включает следующие основные этапы:

1. Определение исходных данных с учетом требований к структурной устойчивости. В качестве исходных данных могут выступать: начальные значения и интервал интенсивности входного трафика ЦСПИ, пропускные способности каналов связи (КС) , ограничение на временную задержку , количество узлов коммутации (УК) в сети , предельные и усредненные структурные характеристики: k-связность , средняя связность (ранг) УК , число остовных деревьев , диаметр сети , а также средняя длина маршрута в сети или средний диаметр .

2. Формирование базовой топологии сети (с начальной структурной избыточностью, исходя из требований исходных данных):

- полносвязная структура (при высоком входном трафике);

- звездообразная структура (при слабом входном трафике);

- ячеистая (иерархическая) структура (при умеренном входном трафике);

Данный выбор связан с особенностями функционирования ЦСПИ представленных топологий при изменениях входного трафика, а структурная устойчивость обеспечивается алгоритмом последовательных итераций основных структурных характеристик ЦСПИ.

3. Математическое описание структурных свойств базовой модели ЦСПИ в терминах спектральной теории графов.

Топологическая модель ЦСПИ представляется графом , где () - множество вершин графа, () - множеством соединяющих их ребер. Для модели ЦСПИ используем неориентированные простые графы без кратных ребер и петель. Задание графа будем осуществлять с помощью матрицы смежности:

, (1)

где - количество вершин (УК) сети, - элементы матрицы, которые отличны от нуля, если элемент, стоящий на пересечении i-й строки и j-го столбца, имеет ребро, соединяющее вершину i, с вершиной j.

Матрица определяемая выражением:

, (2)

называется характеристической матрицей графа G, где - произвольный коэффициент, - единичная матрица. Определитель матрицы (2) называется характеристическим многочленом графа и обозначается .

Корни характеристического уравнения называются собственными значениями матрицы А, а их совокупность образует "обыкновенный" спектр графа G [2]:

. (3)

Графы имеющие одинаковый спектр называются изоспектралъными или коспектральными.

Кроме того, для нахождения важнейших структурных характеристик необходимо использование С-спектра, получаемого из матрицы полных проводимостей [3]:

, (4)

где D - диагональная матрица степеней или валентностей (число дуг, выходящих из i-того УК или количество соседних УК) графа G.

Тогда характеристический многочлен матрицы С имеет вид:

, (5)

а соответствующий ему спектр, (при ) обозначается в виде:

. (6)

На основе представленных спектров могут быть найдены основные структурные характеристики базовых структур ЦСПИ, такие как:

I. Число внутренней устойчивости графа G, которое характеризуется максимальным числом не соединенных УК в графе, определяется с помощью обыкновенного спектра:

(7)

где - соответственно количества собственных значений графа G, равных нулю, меньших или больших нуля, соответственно.

II. Диаметр графа ЦСПИ:

, (8)

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

Для связной графовой модели диаметр удовлетворяет неравенству:

, (9)

а средний диаметр определяется средним значением из интервала:

, (10)

тогда обобщенный структурный показатель равен:

, (11)

где - количество различных собственных значений обыкновенного спектра , - число ребер (КС) в графовой модели ЦСПИ) [3, 4].

III. Число остовных деревьев графа G, определяющее число непересекающихся путей соединяющих два любых УК, находится с использованием С-спектра:

. (12)

IV. k-связность графовой модели ЦСПИ, характеризуемая наименьшим числом УК (КС), при удалении которых граф становится несвязным (в нем появляется изолированный УК), определяется вторым минимальным собственным значением С-спектра:

. (13)

V. С точки зрения обеспечения устойчивости особый интерес представляют регулярные структуры, их важной характеристикой является индекс графа r, определяемый через собственные значения обыкновенного спектра выражением:

. (14)

Таким образом, на основе спектрального анализа графовых моделей могут быть определены все основные структурные характеристики базовой модели ЦСПИ.

4. Определение критериев оптимизации и алгоритмы коррекции базовой топологии графовой модели ЦСПИ.

В качестве критериев оптимизации выступают экстремальные значения определенных выше структурных характеристик ЦСПИ:

; ; ;

; ; . (15)

Моделирование структурных характеристик для получения графовых моделей ЦСПИ высокой устойчивости осуществляется по отдельным итерационным алгоритмам для различных вариантов базовых топологий.

Так в условиях высокого входного трафика (с учетом вероятного снижения загруженности сети) для полносвязной базовой структуры, обладающей максимальной структурной избыточностью (по наличию резервных УК и КС), алгоритм отыскания квазиоптимальной топологии будет направлен на допустимое снижение избыточности при сохранении (обеспечении) требуемых характеристик структурной устойчивости ЦСПИ (итеративное решение "сверху"). В то же время для базовой топологии типа "звезда" при слабом входном трафике (с учетом дальнейшего роста интенсивности информационной нагрузки) алгоритм структурной оптимизации, напротив, осуществляет итеративное увеличение избыточности до достижения требуемых параметров структурной устойчивости (итеративное решение "снизу"). Таким образом, в рассмотренных случаях поставленная задача получения графовых моделей ЦСПИ высокой устойчивости решается "встречно" до достижения определенной в исходных данных требуемой границы устойчивости (с необходимым запасом на возможные дестабилизирующие факторы). В случае умеренного входного трафика решается наиболее сложная компромиссная адаптивная задача (позволяющая учесть изменения входного трафика, как в сторону увеличения, так и уменьшения), когда исходя из текущего значения входного трафика определяются последовательные шаги по снижению или увеличению структурной избыточности графовой модели ЦСПИ с контролем результатов на каждой итерации для выбора "правильного" направления дальнейших преобразований.

При этом вне зависимости от используемого алгоритма осуществляется нахождение коспектральных графовых моделей ЦСПИ с целью получения нескольких альтернативных вариантов максимальной структурной устойчивости [2 - 4].

5. Определение коспектральных структур высокой устойчивости и моделирование функционирования ЦСПИ.

При нахождении коспектральных (изоспектральных) структур для топологий ЦСПИ, удовлетворяющих заданным требованиям устойчивости (на 4 этапе работы метода), могут применяться различные аналитические методы (например, метод Сунада, переключение Зайделя) [2]. Так для графовой модели из 6 УК определяются только две коспектральные структуры ЦСПИ (рисунок 1).

Рис. 1. Коспектральные топологии графовых моделей ЦСПИ, состоящие из 6 УК

Определение коспектральных структур необходимо для обеспечения альтернативного выбора топологии ЦСПИ при оценке ее информационной эффективности на основе системы обобщенных показателей [5, 6].

Заключение

цифровой информация алгоритм топология

Для ЦСПИ, состоящей из 6 УК, были разработаны аналитическая и имитационная модели информационного обмена в ЦСПИ с базовой полносвязной структурой (рисунок 1) и ее преобразованиями при реализации итеративного решения "сверху" в условиях высокого входного трафика и воздействия помех.

Программы аналитических моделей выполнены в средах программирования Maple и Delphi 7, а программы имитационного моделирования в средах GPSS/PC и LiteIDE X. Результаты моделирования показали, что максимальной устойчивостью и наибольшей информационной эффективностью к изменениям входного трафика и помеховой обстановки обладают структуры с и . Это объясняется уменьшением числа конфликтов и потерь пакетов в виду распределенности потоков по различным независимым путям в первом случае, а также уменьшения вероятности их возникновения во втором.

Таким образом, реализация рассмотренных этапов предлагаемого метода повышения структурной устойчивости ЦСПИ позволяют получить несколько альтернативных вариантов построения графовых моделей (коспектральных структур), обеспечивающих выполнение заданных требований к системе.

Результаты аналитического и имитационного моделирования подтверждают работоспособность предлагаемого способа, а также достоверность, получаемых на его основе параметров и характеристик. По итогам работы, основываясь на результатах проведенных исследований, могут быть сформулированы конкретные практические рекомендации по применению вариантов построения структурно устойчивых ЦСПИ. Разработанный метод также может быть практически реализован при организации комплексной многоконтурной адаптации ЦСПИ в реальном масштабе времени к изменяющимся условиям информационного обмена и помеховой обстановки, что позволит обеспечить повышение (поддержание) требуемой структурной устойчивости и информационной эффективности системы [7].

Литература

1. Назаров А.Н., Сычев К.И. Модели и методы расчета показателей качества функционирования узлового оборудования и структурно-сетевых параметров сетей связи следующего поколения. Красноярск: Поликом, 2010. - 389 с.

2. Цветкович Д., Дуб М., Захс Х. Спектры графов. Теория и применение. Киев: Наукова думка, 1984. - 384 с.

3. Андреев А.М., Можаров Г.П., Сюзев В.В. Многопроцессорные вычислительные системы: Теоретический анализ, математические модели и применение. М.: МГТУ им. Н.Э. Баумана, 2011. - 334 с.

4. Межуев А.М. Структурные характеристики информационной сети на основе спектрального анализа топологии / А.М. Межуев, И.И. Пасечников, М.Г. Третьяков // Вестник Тамбовского университета. - Тамбов: 2016. - т.21, вып.2. - С. 676-680.

5. Межуев А.М. Тензорные методы в теории оценки информационной эффективности и анализа элементов цифровых радиосетей (монография). Тамбов: Интеграция, 2008. - 262 с.

6. Межуев А.М. Анализ функции эффективности информационной сети и алгоритм оценки режимов информационного обмена на основе производных обобщенного показателя / А.М. Межуев, И.И. Пасечников, А.В. Коренной // Электромагнитные волны и электронные системы. - М.: 2017, № 5. - С. 12-22.

7. Межуев А.М. Совместное решение задач алгоритмической и структурной адаптации в инфокоммуникационных системах / А.М. Межуев // Наукоемкие технологии в космических исследованиях Земли. - С.-Пб.: 2015. - Т. 7, №6. - С. 36-43.

Размещено на Allbest.ru