автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Анализ иерархических систем передачи и обработки информации

004615495

На правах рукописи

НГУЕН КХАНХ ТОАН

АНАЛИЗ ИЕРАРХИЧЕСКИХ СИСТЕМ ПЕРЕДАЧИ И ОБРАБОТКИ ИНФОРМАЦИИ

Специальность 05.13.01- Системный анализ, управление и обработка

информации

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

~ 2 ЛЕН 2010

Москва 2010 г.

004615495

Работа выполнена в Национальном морском университете Вьетнама

Научный руководитель: Саксонов Евгений Александрович

доктор технических наук, профессор

Официальные оппоненты: Фролов Евгений Борисович

доктор технических наук, профессор

Леохин Юрий Львович доктор технических наук, доцент

Ведущая организация: Рязанский государственный радиотехнический

университет

Защита состоится 17 декабря 2010 г. в А часов на заседании диссертационного совета Д 217.047.01 при ФГУП Научно-исследовательский и экспериментальный институт автомобильной электроники и электрооборудования по адресу 105187, Москва, ул. Кирпичная, дом 41.

С диссертацией можно ознакомиться в библиотеке ФГУП Научно-исследовательский и экспериментальный институт автомобильной электроники и электрооборудования.

Автореферат разослан « А ноября 2010 г.

Ученый секретарь диссертационного совета, доктор технических наук, с.н.с. ---Варламов О.О.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

вычислительных сетей различного назначения.

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

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

Все это требует разработки новых методов и математических моделей, позволяющих решать задачи реальной размерности и вычислять

требуемые характеристики иерархических многоуровневых систем передачи и обработки информации в зависимости от их структуры.

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

Цель работы

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

Задачи исследований.

В соответствии с поставленной целью, основными задачами, решаемыми в диссертации, являются:

• исследование свойств иерархической системы, определение основных задач формирования и анализа многоуровневой иерархической структуры, определение множества характеристик системы и установление их связей со структурой и параметрами системы;

• разработка математических моделей для анализа иерархической структуры, расчета характеристик системы;

• разработка критериев и постановка задач структурного синтеза иерархической системы;

• создание, с использованием разработанных методов и моделей, структуры системы передачи и обработки информации Национального морского университета Вьетнама.

На защиту выносятся:

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

2. Методы и постановки задач формирования многоуровневой иерархической структуры путем кластеризации элементов на каждом уровне и установления связей, с учетом заданной системы ограничений.

3. Комплекс математических моделей для описания структуры и расчета характеристик иерархической системы.

4. Метода практической реализации иерархической структуры системы в условиях конкретного предприятия.

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

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

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

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

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

Методы исследований.

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

Реализация и внедрение результатов.

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

Апробация работы.

Результаты диссертационной работы докладывались и обсуждались на научно-технической конференции «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций», Рязань, РГРТУ, 2010 г., ХЬУ1 Всероссийской конференции по проблемам математики, информатики, .физики и химии, Москва, РУДН, 2010 г., на семинарах в Национальном морском университете Вьетнама (г. Хайфон, 2008 - 2010 г.г.)

Публикации.

Результаты диссертации отражены в 4 опубликованных печатных

работах.

Структура и объем диссертации.

Диссертация состоит из введения, четырех глав, заключения и списка литературы. Объем диссертации 127 страниц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Решение задачи формирования структуры (синтеза структуры)

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

Исследованы постановки задач формирования иерархической структуры, показано, что данный класс задач может быть отнесен либо к задачам математического программирования при нахождении оптимального значения функционала: ор1{Е(/1(Р),/2{Р),...,/я(Р)} при

заданной системе ограничений ^¡(Р) < /=1,М; либо к решению

системы неравенств: Р^1(Р),/2{Р),.../п(Р))<Рр если требуется

выполнить требования технического задания. Здесь Р - множество параметров системы (структуры), fl (Р)- характеристика системы.

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

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

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

Начальный набор для разбиения задается тройкой (5,Л, (3), где Б =

... , ■ множество элементов системы; Л = Ц/?^-1|, =1, ... ,М) -матрица параметров информационного взаимодействия между

элементами; G = jg,, | - матрица векторов весов элементов, gy - величина

у-й компоненты вектора веса элемента i (i — 1,..., DJ = 1,..., М).

Простьш разбиением R(S,Ir) множества S =; {si,s2, ... , -W. называется множество SR= {Sri, Sr2, ..., Sri}, элемента которого

h

удовлетворяют заданному набору ограничений: S = (J5a,

S^eS V/=U4 S *0 Vi=\.JR SAnSy=0 V/#j,/,y = l,..,4

> )

Элементом простого разбиения является подмножество, элементов исходного множества.

N - уровневым разбиением {Ri, R2,..., RnJ множества S = {si,s2, ... , s/J, называется множество простых разбиений, элементы которого

удовлетворяют условию: k=\2,..,N} где -

простое разбиение тожества S.

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

Для формального описания процедуры разбиения используется

вектор принадлежности = Okiy—Ja^ j), где 1ц - вектор-столбец,

элементы которого определяются следующим образом:

• 1цг = 1 - если элемент г (к-1) уровня разбиения принадлежит у" элементу к уровня разбиения;

• 4,г= О-в противном случае.

Вектор - столбцы 4,- можно объединить в матрицу Lk - матрицу разбиения уровня к. Установлены свойства, которыми обладает матрица. Если величины информационных связей между элементами 0-

уровня задаются матрицей Л0 = (|>Ц>у||С'Ч J = 1,...,М), то для вычисления матрицы информационных связей элементов первого уровня получена формула элементы матрицы/!,.. - суммарная величина

информационных связей между элементом г 1-уровня и элементом j 1-уровня, - это суммарная величина информационных связей между элементами 0-уровня, находящимися в составе элемента / 1-уровня. Отметим, что величина информационных связей между элементами часто имеет смысл интенсивности потоков данных между этими элементами. Доказана справедливость выражения для /-уровня:

■ л, *л,ч *Ц=Ц *К:

Если не требуется учитывать внутренние связи элементов, то справедлива формула: A,. *(Ai_1-(AM)Jg)*Li,i = l,...,N^ где

(A,-, )dg

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

Исследованы свойства разбиений. Доказаны следующие утверждения:

1) для всех i = 1,... ^справедливо равенство: ^ \

до

2) для любого уровня разбиения i справедливо неравенство: А- ь

3) если_ Iji>Ij2 и заданы оптимальные разбиения R*(Iji) and то A\R\Ia))ZA\R\Ij2)).

Сформулированы типичные задачи разбиения. Задача разбиения 1.

Найти Л = A (R (IR)) = min {Л (R(Ir ))}

я

где ^о Лу . общий объем информационного

взаимодействия между элементами разбиения цри этом разбиение К* минимизирует общие потоки данных между элементами разбиения.

Ограничения: Л -Я, , 1 = 1,...ДК; Л,- ' = '.-Л; (ЦЛЛя - с)

¡«1 J-!

]Ч

М

J ~ Ъ-Jr ;IR<K; steSm, ifielm m = I,...JR.

i=l

Если задано Ir to предельное значение минимума внешних связей

можно вычислить по формуле: = / .У! cg ■

i=i ¡-1

Пусть Ху= 1 если элемент номер z принадлежит подмножеству у (;' = 1,..., М,у = 1,..., Ir) и 0, в противном случае.

Тогда задача разбиения может быть сформулирована следующим образом (Задача разбиения 2):

/я IR и и

'Л Ла Л2

Найти min**„))}

1=1 у=) Аг=1 г=1

При ограничениях: м м

М М 1.ч h

Ы г=1 Ы

м

я

1=1

Решение задачи разбиения в этой постановке позволяет построить матрицу разбиения.

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

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

Определены правила описания структуры сети и установлены связи между описанием процедуры разбиения и описанием структуры сети. Это необходимо для того, чтобы учитывать ограничения аппаратных средств, связанные, например, с количеством слотов у маршрутизаторов, каскадным объединением маршрутизаторов. Показано, что если общее

подсетей в реальной сети равно +1.

Для описания и анализа структуры использовалась матрица С = ||с || (/—1,

.. , М; 7=1, ... , Д/), где с,у = 1, если элемент номер / подключен к каналу связи номер У; с,у = 0, в противном случае. Показано, что матрица

N

число элементов в многоуровневом

позволяет проводить анализ структуры сети. Так матрица G = Ст * С есть матрица размерности (N х jV), элемент которой g,у - число элементов, подключенных одновременно к каналу i и каналу j. Матрица R = С*СТ размерности (M х М), элемент которой ц- - число каналов, к которым подключены элементы i и j. Использование этих матриц дает возможность количественно оценить связность сети. Разработаны методы расчета загрузки каналов связи при заданной структуре сети.

Показано, что для разгрузки каналов связи можно ввести дополнительные каналы (ввести избыточность). Для наиболее эффективного введения избыточности необходимо решить задачу:

M M _

Найти:

* ¡-i i--\

мм

При ограничениях: =1 sieSrandk^r.

■-•i /' i

Здесь переменная xt] е X (i, j = 1,..., M) такова, что x,j = 1, если элемент i уровня разбиения j подключен к дополнительному каналу связи, и Xij — 0, в противном случае.

В четвертой главе приводятся данные о применении полученных теоретических результатов для проектирования и анализа системы передачи и обработки информации Национального морского университета Вьетнама в г. Хайфон. Система построена в виде иерархической вычислительной сети с применением технологии VLAN.

Показано применение метода разбиения (кластеризации) для выделения виртуальных подсетей. При этом разбиение минимизировало связи между виртуальными сетями, а в качестве одного из ограничений

Digiti.) Dial Modem

O

o

Uigftxi Dial Modem

A4 File Server

использовалось априорное объединение в кластеры (подсети) рабочих станций, входящих в состав одного подразделения. Анализ показал, что в данном случае достаточно двух уровней разбиения.

Применение метода расчета параметров потоков данных между подсетями позволило обоснованно выбрать параметры структурообразующей аппаратуры (коммутаторов) с учетом интенсивности работы пользователей системы и объема передаваемых ими данных. Структура системы приведена на рисунке.

ОБЩИЕ ВЫВОДЫ

1. Анализ современных распределенных систем передачи и обработки информации показал, что большинство из них строятся как иерархические многоуровневые системы, Разработаны принципы формирования иерархической структуры, при этом основной принцип построения заключается в разбиении (кластеризации) заданного множества элементов на группы и минимизации информационных связей между элементами (группами) одного уровня и между уровнями.

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

3. Разработаны математические модели и постановки для расчета характеристик иерархической многоуровневой структуры при заданном разбиении. Это позволило сформулировать и решать задачи

формирования структур с заданными характеристиками, оптимизации характеристик.

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Горшков Г.С., Нгуен Кханх Тоан. Расчет характеристик корпоративной сети с миграцией контента // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций. Материалы конференции. - Рязань, 2010. - С. 53 - 55.

2. Нгуен Кханх Тоан. Модель системы с обработкой пакетов запросов // XLYI Всероссийская конференция по проблемам математики, информатики, физики и химии. Тезисы докладов. - М.: РУДН, 2010. С. 57-58.

3. Будихин A.B., Пашков Д.А., Домбровский Д.А., Кханх Тоан. Информационная обучающая среда с использованием Java-технологий. //Качество. Инновации. Образование. № 10,2010. С. 56 - 62.

4. Nguyen Canh Toan/ Analysis of the hierarchial systems of the transfer and processing of inforaiation. Препринт. M.: МИЭМ, 2009. С. 68.

Подписано в печать 11.11.2010 . Фермат 60x84/16. Бумага типографская № 2. Печать - ризография. Усл. печ. л. 1,2 Тираж 50. экз. Заказ -10 35.

Московский государственный институт электроники и математики 109028, Мосхва, Б.Трехсзятительский пер., 3.

Центр оперативной полиграфии (495) 916-88-04, 916-89-25