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

На правах тажпиф

ОФИЦЕРОВ АЛЕКСАНДР ИВАНОВИЧ

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

Специальность 05.13.06 - Автоматизация и управление технологическими

процессами и производствами (промышленность)

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

2 ИЮН 2011

Орел 2011

4848302

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

Научный руководитель - доктор технических наук, профессор

Еременко Владимир Тарасович

Официальные оппоненты - доктор технических наук, профессор

Корсунов Николай Иванович

Защита состоится «21» июня 2011 г. в 12 часов на заседании диссертационного совета Д212.182.01 при ФГОУ ВПО «Госуниверситет - УНПК» по адресу: 302020, РФ, г. Орел, Наугорское шоссе, д. 29, аудитория 212.

С диссертацией можно ознакомиться в библиотеке ФГОУ ВПО «Госуниверситет - УНПК».

Автореферат разослан «13» мая 2011 г.

Ученый секретарь

диссертационного совета Д212.182.01

кандидат технических наук Лихачев Денис Валерьевич

Ведущая организация:

Государственное образовательное учреждение высшего профессионального образования «Брянский государственный технический университет».

кандидат технических наук, доцент

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

Актуальность темы. Современный этап развития сетей передачи данных (СПД) автоматизированных систем управления (АСУ) промышленных предприятий (ПП) характеризуется наличием жёсткой конкуренции среди организаций, предлагающих сетевые услуги. Они создают распределенные системы, объединяющие различные датчики, контроллеры и исполнительные устройства с использованием сложных специализированных протоколов: Profibus, FIP, ControlNet, Interbus-S, DeviceNet, P-NET, WorldFIP, LongWork, Modbus Plus и другие. Протоколы разработаны с учетом особенностей производства и технических систем, обеспечивают надежные соединения и высокую точность управления. Между тем важными требованиями в системах АСУП и АСУ ТП становятся функциональные возможности, простота инсталляции и обслуживания, адаптируемость к специфическим условиям, соответствие общепринятым стандартам, надежность процессов информационного обмена (ПИО).

Построение единой информационной инфраструктуры ПП, обеспечивающей совместную работу программных и аппаратных средств систем АСУП и АСУ ТП, позволяет объединить разные виды коммуникаций, включить производственное оборудование и управляющие ими компьютеры в единую среду. Современные АСУП в большинстве случаев используют для коммуникаций сети Ethernet и протоколы TCP/IP, а информационные системы - технологии Internet. Внедрение Ethernet на уровне промышленных систем позволяет предприятиям передавать собираемую информацию на уровень АСУП для применения в различных приложениях. С его помощью имеется возможность распространить на системы промышленной автоматизации такие преимущества Ethernet, как простота интеграции с Internet, возможность включения в сеть самых разнообразных устройств и централизованного управления ими.

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

В основе настоящего исследования лежат результаты работ в области теории графов (В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич, О. Ope), теории построения распределенных систем (B.C. Бурцев, В.В. Воеводин, В.В. Корнеев, Э. Таненбауэм), теории распределенных вычислений (А.Б. Барский, В.В. Воеводин, Н. Коновалов, В. Крюков, Б.И. Коган, В.В. Топорков, В.Н. Касьянов, Ю.В. Капитонова, A.A. Летичевский), теории вероятностей и случайных процессов (Ю.К. Беляев, И.И. Коваленко,

В.М. Шуренков, Б.А. Севастьянов, Д. Кокс, А.Д. Соловьев, В. Смит), теории надежности (В.Я. Дудник, Б. П. Филин), теории шаблонов (К. Александер, М. Фаулер).

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

Объект исследования - ПИО СПД распределенных АСУ ПП.

Предмет исследования - модели, методы и алгоритмы неблокируемой маршрутизации СПД распределенных АСУ ПП.

Цель исследования - повышение эффективности использования имеющихся сетевых ресурсов и надежности СПД распределенных АСУ ПП за счет разработки алгоритмов неблокируемой маршрутизации (НМ).

Для достижения сформулированной цели были поставлены и решены следующие задачи.

1. Анализ протоколов и алгоритмов маршрутизации в современных СПД распределенных АСУ ПП.

2. Моделирование управления ПИО в СПД распределенных АСУ ПП.

3. Разработка способов и приемов НМ по адресу получателя, обеспечивающих повышение надежности передачи пакетов по сравнению с существующими аналогами.

4. Разработка критериев и алгоритмов проверки топологии сети на совместимость с НМ.

5. Оценка эффективности использования имеющихся сетевых ресурсов и надежности СПД распределенных АСУ ПП при реализации разработанных алгоритмов.

Методы и средства исследования. В ходе исследования были использованы методы теории графов, теории вероятности, теории надежности, теории шаблонов, комбинаторного и системного анализа. В разработке программного обеспечения использовалась технология объектно-ориентированного программирования.

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

Научная новизна диссертационного исследования заключается в том, что получены новые научные результаты:

1) математическая модель управления ПИО в СПД распределенных АСУ ПП, базирующаяся на аппарате потоковых графов, отличающаяся учетом типа трафика и условий НМ и позволяющая описать ПИО;

2) методика проектирования СПД, совместимых с НМ, базирующаяся на шаблонном подходе, отличающаяся сформулированными правилами достижения сообщениями узла-получателя и позволяющая обеспечить

равномерное распределение нагрузки на элементы сети и сформулировать рекомендации по изменению топологии;

3) реализация автоматизированной системы проектирования СПД, базирующаяся на проверке совместимости топологии сети с НМ, отличающаяся использованием информации о состоянии каналов связи и позволяющая обеспечить НМ для максимально возможного числа узлов в заданной топологии сети.

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

Полученные теоретические результаты использованы:

1) в процессе подготовки нормативно-методических документов и спецификаций ПИО в СПД ОАО «ПРОМПРИБОР» (г. Ливны);

2) в разработке программного средства многопутевой маршрутизации на основе шаблонного подхода (свидетельство о государственной регистрации программы для ЭВМ № 2009610538 от 22.01 2009 г.);

3) в разработке автоматического устройства неблокируемой маршрутизации для волоконно-оптических сетей связи (патент на полезную модель № 92590 от 20.03.2010 г.).

Апробация и публикации. Материалы диссертации публиковались и докладывались на: XI ежегодной научной конференции преподавателей Орел-ГТУ (2006, г. Орел), III Всероссийской научно-практической Интернет-конференции «Методы прикладной математики и компьютерной обработки данных в технике, экономике, экологии» (2006, г. Орел), V Международной электронной научно-технической конференции "Технологическая системотехника" (2006, г. Тула), XII ежегодной научной конференции преподавателей ОрелГТУ (2007, г. Орел), XIII ежегодной научной конференции преподавателей ОрелГТУ (2008, г. Орел), XIV ежегодной научной конференции преподавателей ОрелГТУ (2009, г.Орел), IV Международной научно-практической конференции «Информационные технологии в науке, образовании и производстве (ИТ-НОП)» (2010, г. Орел).

По материалам диссертации опубликовано 6 статей (из них 3 статьи в журналах из перечня ВАК), получено одно свидетельство о регистрации программы для ЭВМ и один патент на полезную модель.

Положения, выносимые на защиту:

1. Математическая модель управления ПИО в СПД распределенных АСУ ПП.

2. Методика проектирования СПД, совместимых с НМ.

3. Реализация автоматизированной системы проектирования СПД.

Структура и объем работы. Диссертация содержит введение, четыре главы, заключение, список литературы (121 наименование); 6 таблиц и 48 рисунков (общий объем диссертации - 145 листов).

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

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

Первая глава посвящена анализу ПИ О и описанию протоколов и алгоритмов маршрутизации в современных СПД распределенных АСУ ГШ.

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

Указанные особенности послужили причиной внедрения на предприятиях так называемых ERP-систем (Enterprise Resource Planning - системы планирования ресурсов предприятия), которые позволяют повысить эффективность производственных процессов и снизить себестоимость производства. Для подобных систем определяющим фактором является получение достоверной информации в режиме реального времени.

Анализ использования протоколов в современных СПД распределенных АСУ ПП показал, что отсутствие единых унифицированных протоколов для промышленного оборудования обуславливает необходимость внедрения для управления процессами в цехах, сбора данных для ERP-приложений единого протокола, в качестве которого в последнее время на большинстве предприятий выступает Ethernet.

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

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

Во второй главе описаны свойства топологий сетей, совместимых с не-блокируемой маршрутизацией и представлена математическая модель управления ПИО в СПД распределенных АСУ ПП.

В качестве математической модели управления ПИО в СПД распределенных АСУ ПП выбрана потоковая, позволяющая учесть взаимодействие нескольких источников и потребителей информации.

Пусть задана сеть, состоящая из | V | узлов. Узлы соединены между собой направленными линиями е е Е (Е - множество всех линий, соединяющих узлы v, eF, i = l,\V\). Каждая линия е имеет пропускную способность Се. Таким образом, физическая топология исходной сети характеризуется графом N = (V,E,C).

По сети передается трафик различных классов сервиса s eS, где S - мно-

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

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

данного узла - Gv .. Для заданного адресата в сети может существовать много

различных графов маршрутизации. Далее, для каждого узла сформируем условия, что Vi*Vj,ú)G Ы)>\,аз0^ (vy)= 0, где ú)Gvj (v,) и coG (vj - это исходящие степени узлов v, и vj в графе маршрутизации Gv .

Для повышения надежности СПД особый интерес представляют графы маршрутизации, которые обеспечивают для каждого узла v,- Ф v¡ :a>G (v,)> 2.

J Vj

Такая маршрутизация в научной литературе рассматривается как неблокируемая.

Для того чтобы повысить надежность связей узлов, для которых ú)Gv (v,)= 1, необходимо разрешить петли маршрутизации в графе, состоящем

из двух ориентированных дуг, но блокировать их использование в течение нормального режима работы. Двунаправленная дуга v(v¿, для которой (v,-,v¿)e Е и (v¿,v,-)e Е, рассматривается как резервная дуга.

Пусть узел v, является источником, а узел vj - приемником трафика. Пара узлов (y;-, vy ) обозначается как a¡j (/', j = 1, | V /V j; v¡, vj е к).

Поток трафика fas пары узлов Су класса сервиса í может передаваться по различным путям в сети. В работе введено понятие допустимого маршрута г , по которому часть потока класса сервиса .v может достигнуть узла v,. Через

ffjjS J

каждую линию е может проходить множество допустимых маршрутов, суммарный трафик которых fk не должен превышать пропускной способности линии.

OjjS

Для каждой линии е определяется суммарный поток fesv класса сервиса s от всех маршрутов, исходящих из узла v,:

fesv, = |! 0)

Тогда общий поток трафика класса сервиса s от всех узлов v¡ е V, который должен пройти через линию е, может быть представлен в виде:

т т т , г , )

fes = Т. fesv, =III/Í/H , (2)

а максимально допустимый поток класса сервиса 5, который может пройти че-

рез ветвь е:

= Се Р^доп ' ^

где Р!доп - максимально допустимый коэффициент загрузки, который показывает, какую долю пропускной способности линии может использовать трафик класса сервиса ^.

Суммарный допустимый коэффициент загрузки линии е потоками класса сервиса 5 и более приоритетными может быть представлен следующим выражением:

R.

едоп

= I/

£=1

(4)

где g - порядковый номер класса сервиса в множестве Л'; g = 1 обозначает наиболее приоритетный класс сервиса.

Коэффициент Кедоп позволяет определить максимальную пропускную

способность линии е, которую может использовать суммарный поток Ре ,

т.е. максимально допустимый поток класса сервиса 5 и более приоритетных классов сервиса:

= CJl

едоп

(5)

^едо„ ^ fei g=1

Тогда суммарный расчетный поток, который должен пройти по ветви е, описывается следующим выражением:

■S

(6)

V ~ £ feg ■

К=1

Рассматриваемая сеть не будет иметь блокировок, если для любой линии ее Е будет выполняться условие:

Р'е ^ ■ (7)

ерас ^аоп 4 '

Критерием надежности анализируемой сети является условие: * М

Рс = I 8т-Рст ~>тах,

(8)

т=1

где М - общее количество двухполюсных сетей; gm - удельный вес (значиМ

мость) /я-й двухполюсной сети ( 0> а показатель надежности двухпо-

т=1

люсной сети Рс при известных значениях вероятностей безотказной работы элементов системы е/ И использовании критерия вероятности связности хотя бы по одному работоспособному пути может быть определен как:

Рс = Ра,; = Р

У(еъ...,еп)= U rka = U к=1 у

К

и П«/ = 1

к=1 /eß t

(9)

где у(е\,...,еп) - функция работоспособности системы (ФРС), связывающая состояние элементов с состоянием системы; D к - множество переменных е/

Ч

входящих в А-й путь.

В качестве естественного ограничения в работе рассматривается стоимостная функция построения СПД:

ш

ZdCei<Dmax, (10)

/=1

где dei - стоимость построения I -го канала.

Таким образом, управление ПИО должно осуществляться на основе требований по пропускной способности (7), надежности (8) и стоимости (10) и удовлетворять условиям НМ:

1) узел-получатель должен быть достижим всеми остальными узлами, то есть Vvj е V : Vj-tQVj ;

2) каждый узел, кроме узла-получателя, должен иметь степень выхода не менее чем 2, то есть Vv,- е V - |vy j : coq (v, ) > 2 ;

3) если любой узел, кроме узла-получателя, удален, то узел-получатель должен быть достижим всеми оставшимися узлами, то есть

Vv,- e F - (vy j Vv* eV-{vhVj}:vk->G_ViVj;

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

Vv,- e F - |vy)3 vk e F : (v,-,vk)e E и {vk, v,) g E;

5) если два узла v, и vk взаимно достижимы в G, то они являются соседями, а связь между ними - это резервная дуга, то есть

vi~*Gvk и vk^Gvi^vivkeE-

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

Методика проектирования СПД, совместимых с НМ, включает в себя следующие этапы.

Этап 1. Анализ исходных данных. Исходными данными для проектирования СПД, совместимых с НМ, являются:

1 ) топология сети, включающая:

- множество узлов F = |v,;/ = 1,|F]j;

- множество дуг E = je, ; / = 1, |£||;

2) способ задания исходной топологии сети: в виде ориентированного или неориентированного графа.

Этап 2. Анализ топологии сети на совместимость с НМ, предваряющий проектирование СПД. На основе теоретических положений, изложенных во второй главе, алгоритм анализа топологии сети на совместимость с НМ проверяет, что от любого узла сети возможно достичь любой другой узел двумя или более независимыми по узлам и рёбрам путями, что соответствует

определению НМ (рис.1).

Рис. 1. Алгоритм анализа топологии сети на совместимость с НМ

Результатом работы алгоритма является вывод о совместимости топологии сети с НМ.

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

I. Построение прямых дуг.

II. Удаление лишних прямых дуг.

III. Добавление дуг, обеспечивающих НМ. Если это невозможно обеспечить обычными дугами, то используются резервные дуги.

IV. Перестановка дуг с целью минимизации числа резервных дуг.

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

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

ето(к|5|£|4).

с

Начало

Ввод исходных данных

Классифицировать дуги на прямые, кольцевые и обратные

Добавить прямые дуги в

Нет

Найти узел :

1. ФМ,

2. МАХ\ос^к)\

3.

4.

Удалить прямую дугу (V,, )

Добавить все узлы с С0а (V, ) = 1 В СПИСОК ¿01

Найти узел V;.:

1. м/^^Л

3- Ас, к)>!

в, - граф пеблокируемой маршрутизации

Конец

Рис.2. Алгоритм построения графа НМ на основе пошагового улучшения

Этап 4. Проектирование СПД, совместимой с НМ, в случае, если исходная топология сети задана в виде неориентированного графа. Для построения графа НМ в данном случае используются разработанные в рамках диссертационного исследования алгоритмы на основе минимально необходимого числа шаблонов и применения дополнительных шаблонов. В основе работы данных алгоритмов при проектировании СПД распределенных АСУ ПП лежит процесс построения графа маршрутизации при помощи содержащихся в базе данных шаблонов для обеспечения НМ.

В ходе исследования установлено, что любой граф НМ может быть представлен совокупностью шаблонов (Щ1-Ш4), а алгоритм построения графа НМ на основе минимально необходимого числа шаблонов реализован следующим образом.

В начале работы алгоритма неполный граф маршрутизации С\, содержит только узел-адресат V]. Пока Су содержит не все узлы из V, алгоритм

ищет шаблон графа маршрутизации из кольца вокруг неполного графа маршрутизации Су. и добавляет его в . Неполный граф маршрутизации С\. изменяется после каждого шага алгоритма. Поэтому кольцо вокруг графа С\,

также изменяется после каждого шага алгоритма.

На первом шаге в зависимости от топологии сети алгоритм может добавить только шаблоны маршрутизации ШЗ или Ш4. Если невозможно добавить шаблон маршрутизации ШЗ на первом шаге, то сеть не является совместимой с НМ. На всех остальных шагах алгоритм стремится использовать шаблон маршрутизации Ш1. Когда это невозможно, он использует шаблоны маршрутизации Ш2, ШЗ или, в крайнем случае, Ш4 (правила приведены в порядке предпочтительности). Шаблон маршрутизации 1114 рекомендуется к использованию только в крайнем случае, если никакой другой шаблон не может быть применён в процессе построения графа маршрутизации.

Оценка сложности расчёта маршрутизации для всех адресатов с использованием данного алгоритма о|к|3 +\У\21о§|Г| + |К|£|)« о|к|3 +|к||£|).

Алгоритм построения графа НМ на основе применения дополнительных шаблонов развивает идею, реализованную в предыдущем алгоритме. Как и предыдущий, он строит граф маршрутизации С„ из элементов, называемых шаблонами маршрутизации, но в отличие от вышеприведенного здесь используются также дополнительные шаблоны Ш5 и Ш6, позволяющие свести к минимуму вероятность применения шаблона Ш4.

Оценка сложности расчёта маршрутизации для всех адресатов с использованием данного алгоритма составляет о|к|4 +|К||£|21.

Этап 5. Проверка совместимости топологии сети с НМ, повторно использующая алгоритм анализа топологии сети на совместимость с НМ. Результатом работы алгоритма является вывод о совместимости спроектированной СПД с НМ.

Этап 6. Оценка надежности, стоимости и эффективности использования имеющихся сетевых ресурсов спроектированной СПД

Сравнение разработанных алгоритмов с алгоритмом Райхерта и алгоритмом неравных кратчайших путей (модифицированным алгоритмом Дейкстры) протокола маршрутизации ОБРР, приводившееся для двух фрагментов топологии сети, показало превосходство шаблонных алгоритмов практически по всем сравниваемым показателям. Главным преимуществом разработанных алгоритмов является то, что они, в отличие от алгоритмов-конкурентов, способны всегда обеспечить

НМ, если топология сети позволяет это сделать.

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

В диссертационном исследовании оценка эффективности процесса функционирования СПД распределенных АСУ ПП осуществлялась на основе сформулированной в соответствии с целью исследования системой показателей

У = (о\,Б0,Мрс!,Р\е,Р2е,Р1у,Р2у,Рче,оУ, где 01 - суммарное число узлов,

имеющих только один независимый путь до цели; 50 - суммарное число узлов, отказ одного из которых превращает граф в несвязный; Л^ - число резервных дуг; Ри- вероятность безотказной работы сети в случае отказа одного из ребер; Р2е- вероятность безотказной работы сети в случае отказа двух ребер; Ри- вероятность безотказной работы сети в случае отказа одного из узлов; Р2„- вероятность безотказной работы сети в случае отказа двух узлов; Руе- вероятность безотказной работы сети в случае одновременного отказа одного из узлов и одного из рёбер; О - стоимость построения СПД при применении алгоритма. Значения обобщенного показателя эффективности рассчитаны для различных алгоритмов (разработанных шаблонных алгоритмов, алгоритмов Райхерта и модифицированного алгоритма Дейкстры) при применении метода «идеальной точки», в котором обобщенный векторный критерий оптимальности:

Г™'"(У) = л1Е(Лн>(Г) - Л"**")1 тш, (11)

V "=1

гДе /¡ГЧ^) - нормированные значения показателей эффективности; - идеальные значения показателей эффективности.

Сравнительный анализ по обобщенному показателю эффективности для различных алгоритмов (табл. 1) показал значительное превосходство алгоритмов построения графов НМ на основе минимально необходимого числа шаблонов и на основе применения дополнительных шаблонов над предшествующими аналогами. Оба шаблонных алгоритма обеспечивают НМ для любой сети, совместимой с НМ. В свою очередь алгоритм на основе минимально необходимого числа шаблонов является более предпочтительным, чем алгоритм на основе применения дополнительных шаблонов, в связи с более высокой скоростью его работы.

Таблица 1 Значения обобщенного показателя эффективности

Алгоритм Алгоритм на основе минимально необходимого числа шаблонов Алгоритм на основе применения дополнительных шаблонов Модифицированный алгоритм Дейкстры Алгоритм Райхерта

1,52/1,03 1,52/1,03 7 / 6,32 2,08 / 6,2

Состоятельность представленных результатов позволила предложить автоматизированную систему (АС) проектирования СПД, совместимых с НМ, разработанную с помощью унифицированного языка моделирования (Unified Modeling Language, UML). Данная система реализует разработанную в рамках диссертационного исследования методику проектирования СПД, совместимых с НМ.

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

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

В заключении сформулированы основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ:

В диссертационной работе решена актуальная научно-техническая задача разработки способов и приемов проектирования технологической подсистемы АСУ ПП - сети передачи данных - за счет использования шаблонного подхода.

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

1. Разработана математическая модель управления ПИО в распределенных АСУ ПП, базирующаяся на аппарате потоковых графов, отличающаяся учетом условий НМ. Для выявления внутреннего параллелизма при информационном обмене использовались потоковые модели. Потоковая организация передачи данных в работе рассматривается, как использование информационных связей между частично упорядоченными действиями маршрутизаторов сети для реализации заложенного в ней параллелизма. Модель позволяет учесть взаимодействие нескольких источников и потребителей информации.

2. Произведено обоснование свойств топологий СПД распределенных АСУ ПП, совместимых с НМ. Описанные свойства используются для обоснования корректности работы разработанных алгоритмов.

3. Разработана методика проектирования СПД, совместимых с НМ, включающая в себя следующие этапы: анализ исходных данных; анализ топологии сети на совместимость с НМ; построение графа НМ; проектирование СПД, совместимой с НМ; проверка совместимости топологии сети с НМ; оценка надежности, стоимости и эффективности использования имеющихся сетевых ресурсов спроектированной СПД.

Последовательность этапов разработанной методики напрямую зависит от способа задания исходной топологии сети.

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

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

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

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

8. Произведено сравнение разработанных алгоритмов с алгоритмом Райхерта и алгоритмом неравных кратчайших путей (модифицированным алгоритмом Дейк-стры) протокола маршрутизации OSPF, приводившееся для двух фрагментов топологии сети. Сравнительный анализ показал превосходство шаблонных алгоритмов практически по всем сравниваемым показателям. Главным преимуществом разработанных алгоритмов построения графов НМ является то, что они, в отличие от алгоритмов-конкурентов, способны всегда обеспечить НМ, если топология сети позволяет это сделать.

9. Произведена оценка эффективности процесса функционирования СПД распределенных АСУ ПП на основе сформулированной в соответствии с целью исследования системой показателей и применения метода «идеальной точки», показавшая значительное превосходство алгоритмов построения графов НМ на основе минимально необходимого числа шаблонов и на основе применения дополнительных шаблонов над предшествующими аналогами.

10. Предложена автоматизированная система проектирования СПД, совместимых с НМ, реализованная с помощью унифицированного языка моделирования (Unified Modeling Language, (JML) в виде программы для ЭВМ. Данная система реализует разработанную в рамках диссертационного исследования методику проектирования СПД, совместимых с НМ.

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

Список работ, опубликованных по теме диссертации в изданиях, рекомендованных ВАК РФ

1. Офицеров, А.И. Алгоритмы выбора оптимального маршрута в корпоративных сетях [Текст] / А.И. Офицеров, В. Т. Еременко, А. В. Еременко // Известия Тульского государственного университета. Серия «Технологическая системотехника». Выпуск 10-Тула: Изд-во ТулГУ, 2006. - С. 101 - 107.

2. Офицеров, А. И. Управление информационными потоками на основе резервирования ресурсов в сетях передачи данных предприятий. [Текст]. / А. И. Офицеров, В. Т. Еременко, А. В. Демидов // Информационные системы и технологии - Орел: Изд-во ОрелГТУ, 2007. -№ 4-2/268(535) -С. 167- 172.

3. Офицеров, А. И. Оценка эффективности работы маршрутизаторов в сетях передачи данных предприятий. [Текст]. / А. И. Офицеров, В. Т. Еременко // Информационные системы и технологии - Орел: Изд-во ОрелГТУ, 2009. -№4/54(567)-С. 105-111.

Список работ, опубликованных по теме диссертации в журналах и материалах конференций

4. Офицеров, А. И. Алгоритмы оптимизации мультимедийного трафика в многоприоритетных сетях. [Текст]. / А. И. Офицеров // Известия Орловского государственного технического университета. Серия «Информационные системы и технологии». III Всероссийская научно-практическая Интернет-конференция «Методы прикладной математики и компьютерной обработки данных в технике, экономике, экологии». Труды конференции. - Орел: Изд-во ОрелГТУ, 2006,- № 2 - С.147 - 155.

5. Офицеров, А. И. Методы управления информационными потоками в сетях передачи данных на основе резервирования ресурсов. [Текст]. / А. И. Офицеров, В. Т. Еременко // Методы и устройства передачи и обработки информации. Межвузовский сборник научных трудов. Выпуск 11. - М.: «Радиотехника», 2009. - С. 340 - 346.

6. Офицеров, А. И. Моделирование процессов информационного обмена с приоритетами в сетях передачи данных промышленных предприятий. [Текст]. / А. И. Офицеров, С. И. Афонин, А. В. Демидов // «Информационные технологии в науке, образовании и производстве». Материалы международной научно-технической конференции. - Орел: ОрелГТУ, 2010.-Т.1 - С. 188-191.

7. Офицеров, А. И. Свидетельство об официальной регистрации программы для ЭВМ № 2009610538 «Программное средство многопутевой маршрутизации на основе шаблонного подхода». // В. Т. Еременко, С. И. Афонин, А. И. Офицеров, А. В. Демидов. - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам: Реестр программ для ЭВМ. - 22.01.2009.

8. Офицеров, А. И. Патент на полезную модель № 92590 «Автоматическое устройство неблокируемой маршрутизации для волоконно-оптических сетей связи». // И. А. Сайтов, А. И. Офицеров, О. О. Басов, И. Г. Кобзарева. - Федеральная служба по интеллектуальной собственности, патентам и товарным знакам: Государственный реестр полезных моделей Российской Федерации. - 20.03.2010.

ЛР ИД № 00670 от 05.01.2000 г. Подписано к печати « 10 » мая 2011 г. Усл. печ. л.1,00 Тираж 100 экз. Заказ № 136.

Полиграфический отдел ФГОУ ВПО «Госуниверситет - УНПК» 302005, г. Орел, ул. Московская, 65