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

ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Экз. Ля

••ТБ ОД

Г.. г»

с I [.¿ГЦ

Святенко Кирилл Витальевич и V ' г

Математически? модели и алгоритмы оптимизации восстановительного ре-.зёрШфрранпя информации в корпбртшшйвьгчислительной сети "Государственной компании "Росвооружение4

Специальность 05ЛЗ,.рбт''4втом9ттир.оеанные системы управления"

Автореферат диссертации

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

Т>«а-2000

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

Научный руководитель:

кандидат технических наук Еснков О.В.

Научный консультант:

доктор технических наук, профессор Киселев !!./(.

Официальные оппоненты:

доктор технических наук, профессор Мотгль П.В.

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

кандидат технических наук Сукманоп С.А.

научно исследовательский институт "СТРЕЛА", г. Тула

Л йО .

Защита состоится 23 2а&£) г. в 1Н "часоп на заседании дис-

сертационного совета К 063.47.10 в Тульском государственном ушшерс1Ггете с ауд. 101 и 14.00 но адресу: г. Тула, пр.Ленина 92, 9 уч. корпус .

С диссертацией можно ознакомится в библиотеке университета

Автореферат разослан 1^2000 г. •' '

Ученый секретарь.днссергаинонного сонета

кандидат технических наук, доцент //. . КоЕешнимжВ.А, /

\С1|/ч

N

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

Главным направлением повышений эффективности формирования и осуществления процесса военно-технического сотрудничества является создания Единой автоматизированной информационной системы на основе внедрения компьютерных технологий и использования современных средств вычислительной тех-средств;прредзчи дацных и матем^чесетх методов, • ; . -

■ Постоянное совершенствование средств и методов управления различного рода структурными подразделениями «ГК «Росвооружение» стало рдшш из основных факторов, определяющих повышение эффективности действий России на мировом, рынке вооружений и военной техники (В и ВТ). Необходимость дальнейшего интенсивного развития систем управления диктуется возрастающей диспропорцией. между постоянно растущим потоком информации, представляющей Собой конъюнктуру рынка, прогноз потребностей ро каждому конкретному образцу В и ВТ, возможностями предприятий производителей специмущества (СИ), изменения российского законодательства; международные и внутренние политические аспекты, и возможностями средств по обработки для принятия решений. На этой основе возникают Ц нрвые повышенные требования к вычислительным системам (ВС) управления.

Наличие широкой сети peí иональных Представительств в более чем 20 странах также требует наличие современной ВС-

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

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

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

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

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

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

Существует большое число работ посвященных сетям ЭВМ. В. работах В.М.Глушкова, Д. Флинта, Э,Д. Якубайтиса ..излагаются основные принципы построения вычислительных сетей, организация сегтей передачи данных и связи, их анализ и синтез. В работе Г.Т.Артамонова и В.Д, Тюрина излагается оригинальная система топологических инвариантов, позволяющая эффективно решать задачи определения изоморфизма и автоморфизма сетей. ИссЛедустся,. влияние топологических характеристик сетей на их надежность/пропускную способность, стоимость и ряд других системных характеристик. В работе Г.Ф. Янбых и Б. А. Стол*- ; рова рассматривается проблема оптимизации физической структуры информационно-вычислительных сетей. Методы и алгоритмы синтеза и оптимизации структуры, централизованных и распределенных сетей.ЭВМ с единых методологических позиций рассмотрены Ю.П. Зайченко и.Ю.В. Гонта. ;

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

Приведенный перечень работ свидетельствует о большом интересе, к развитию сетей ЭВМ и определенном опыте, накопленном в .нашей стране и за р>ое//ко\(. в области решения задач сшпсза и оптимизации структуры, анализа сетей ЭВМ, особенно сетей передачи данных.

Однако основной акцепт при создании ВС на базе сетей ЭВМ делается на решение следующих проблем:

- организации информашюнно-впчнслнтельного процесса (НШ1) в системе вычислительных срелств сети ЭВМ;

- организации управления распределенными ресурсами в рамках гппе мы, ■ .

обеспечении спхраииост информации и чьчемах' с распределенной ,к~р:.бош>Н анфорчзшш;

- организации функционирования распределенных баз дешныл.

i? США и ведущих зарубежных странах решпипо перечней иных проба: м придан статус наивысшего приоршета, так как от нч решения в парную очереи. зависит эффективность сети в делом.

Eujih úíiv-oi.iviii^iu liuivoiuwiuuli otiui при решешзд задач оптимнзапип

ti iiuüutucütw jcioü'iiibuciu ппфир;,и:;;1сппо-шлч11слптсл1пого процесса (ИНН), сохранности информации п сетях ЭВМ, то необходимо отметить работы В.В. Хорошевскою, K.H.Typyni.' O.K. Кондратьева, отражающие прогресс, достигнутый при решешш í;n.a'i повышения устойчивости ИВП. Работы А.Г. Мамнко-иова, В.В. Кульбы, С.К.'Сомова, А.Б. Шелкова посвящены решению вопросов повышения достоверности и сохранности информационных модулей и программных массивов в вычислительных сетях за' счет организации оперативного и восстановительного резервирования. '

Пракч ичесп'-с решение'БЛттр~гс.т> гшгггнп сетей ЭВМ и организации нх Фунмжошфо/г.шс! св.'пани с рлзлти-лч теории и практики оптимизации, fo-термм поевзшеш i pjfwru О.Г. Алексеева, B.C. Мпхалевнча, II В. Copt пенко, А А Корбута, Ю.Ю Фннкельшгейн

Прицеленный обзор paóiU. ¡¡....«.ыпает чю задачи повышения уеюнчиво-. in ИВП, lu'o in.'Viiür i>ч])ан1И.сти информации повышении эффективности и разработка ноныч метопов оптимизации решались в основном порознь и щучены с различной V п'пен: ю глубины.

Работы, проведенные в пом нанр^в icihih к mu тояшему времени, oóa.naioi рядом существенных иедос1а1Коь:

1. Не разработан системшй подход к повышению устойчивости ИВП и ■'.л'ранноези информации па лапах проектирования и эксплуатации ВС.

2 Пело«.-) ai очно формализованы способ).! и методы обеспечения устойчивости ИВП и сохранности информации (модели распределения и перераспределения программных модулей и информационных массивов по узлам сети ЭВМ),

3. Существующие постановки указанных задач иредполашот их решение в процессе синтеза сети ЭВМ Jit ходя in зтого, к разрабатываемым меюдам и аз горитмам их решения не предъявляем достаточно жестких требований по времени решения Вместе с тем, такие задачи возникают в процессе оксплуатаппи средств автоматизации управления, а их реализация связана с решением дискретных, зачастую иешшСЛнмх .задач большой размерности к короткие сроки. Это, в свою очередь, порождает проблему дискретности, мнотмерности и

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

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

Актуальность задачи обусловлена: необходимое и ш повышения эффективности функционирования вычислительной сети «ГК «'Росвооружение» за счет придания ей свойств устойчивости ИВГ1, необходимостью разработки и совершенствования теоретического аппарата обеспечения сохранности информации, исследования задач многомерности и дискретности задач оптимизации.

Ооьскюм исследования являются автоматическая система обработки информации подразделении «ГК «Росвооружение»

Предметом исследовании являются методы обеспечения сохранности информационных массивов в вычислительных сетях «ГК ((Росвооружение».

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

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

1. разработка' общего подхода к решению задач обеспечения сохранности информации в системе вычислительных средств сети;

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

3. повышение эффективности существующих и разработка новых методов решения задач оптимизации;

4. оценка эффективности, обоснование рекомендаций по использованию разработанного теоретического аппарата. '

Содержание этих решений изложено в трех главах настоящей работы.

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

Вторая глава посвящена.разработке системы математических моделей он I имитации распределения (перераспределения) ПМ и ИМ с учетом их резервирования в СВС сет и ЭВМ. Обоснован метод их декомпозиции на ряд взаимосвязан пых задач в целях практической разрешимости. Предлаглмю. мсылы и алториг-

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

В третьей ьтавс обосновываются критерии оценки эффективности разработанных мо1одов и алгоритмов ощшшзащш. Проводи гея сравнительная оцетл зффекшвности разработанных и существующих «лгершмов оптимизации. Прел яигаюгея рекомендации но использования разработанного теоретического ;<ппп;-.) та ий этапах проектирования и зкеплуатанпп ВС.

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

Och.quiiu.mh научными результатами, выносимыми на зншнту явля

ются:

Система • мженашчсиинл ьшдьльй икипушацпл пнформанноннп-вычнслителыюго процесс« ь сс1Ял Г)ПМ, позволяющая конплгпеио и тяимосвя-зано решать задачи распределения программных модулей, информационных массивов и их восстановительного резерва в системе вычислительных средств, а также определять необходимый объем резерва.

2. Метод решения общих задач оптимизации распределения (перераспределения) программных модулей и информационных массивов с учетом их резервирования в- системе вычислительных средств па основе предложенной их декомпозиции на ряд.взаимосвязанных задач и разработанные математические модели оптимгпг.иии для кижиЫи .иЛнл „•¡••¡•"■чиозииип. • .....

М.лод и мниманнкм..^. молоть он. нкн порядка ветвления переменных, оьр.ч&инмч флпнц решения и метле ьетой и границ, исшимуюиш** .¡¡чншин ;и-:.Ь-1(«с!П1';| т /!(м1.".)»!и1шн- шчнпмьно сокрашть вычислштезьпук. сложное п. ошоригмо» нетей и 1 р.-пит.

■!. '■.К.лифнчиропаннын чеюл ¡члречио;с, решения функциональных ур;ы пепин /шна.г'пческою про) рлммированн.ч. нивыьзуюший теорию двойственности ч 1н \ иорял.зчеиия 01 раниченпй и схссаа бесперспективных переменных при решении ча.чачи по нерио.иу ограничению по условиям меюда ветвей и границ, обеспечивающий значительное уменьшение времени решения задач и. число членов условно онтнмапьк'мх'иослелователыюстей.

Мракинич'к.ш ишчимосн. работ заключает си н том, чш предложенные модели, мешди и д.иоритмы испольчонл.чи при проведении 1ШР в »асш обоснования методов обеспечения сохранности информационных массивов п системе вычислительных средств различных контуров управления корпоративной вычислительной сети компании "Росвооружение", а также в.силу своей общности могу! найти применение при разрабонсе и эксплуатации перспективных вычислительных сетей различных уровней ) правления. Методы и алгоритмы доведены ли рабочих программ и позволяют решать широкий Круг науЧно-теЯническнх задач. ■ Апробации рабшы. Материалы диссертации докладывались, обсуждались и одобрены на.Н ТК Тульского ВАИУ (1997, .1999 гг.), Михайловской артл-лерийской академии г. С-Петербург (199$ Г.), на расширенных заседаниях кафедр

"ЭВМ и ВС", "Математическое, программное н информационное обеспечение ВС" Тульского артиллерийского инженерного института.

Публикации. Материалы диссертации опубликованы в 8 печатных работах и ведомственных научно-технических изданиях

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

в 3 ЦНИИ МО России;

в Таганрогском авиационном научно-техническом комплексе им. Бериева в учебном процессе Тульского ВЛПУ в дисциплине "Исследование операции"

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

СОДЕРЖАНИЕ РЛ1ЮТЫ lio квздешш обоснована актуальность задачи и дана кратка л хар-чаорпеш-ка се решения, сформулирована цель paooiu и обоснованы положения, взносимые на защиту, указана cipyiuypd дасссркщпи. формы анробашш и внедрения ре плыаюв.

U iicpuoii гдаае раесмафнваются гребовшнш, »ре/и.&ш'юоппс к ПС ком па innt "Росвооружение" ш» современном чганс, основные направления сс соьсршгн-l it.obaiii;>i и связанные с этим задачи. Показано, чи) уффскгнвпость ПС во многом определяет ся обеспеченном есхрапприн ннформашн. в системе вмчнелннтшк ».редей-. УС. Исследуются основные нанравлеийп обеспечения сохранности информации и методы их реализации. Показано, что при заданных характеристиках юхническнх средств шпоматизацни сохранность информации обеспечивается рациональным .распределением программных модулей (ПМ) и информационных массивов (ИМ) в системе вычиелтельных средств (СВС) ВС с учетом их резервирования, Формулируется задача исследования и обосновывается общий подход ее решения. • - \ .' • .

Проведен анализ развития и современною состояния корпоративной вычислительной сети Главного инженерного управления (впоследствии Государственное} компании «Росвооружение»). .-' .

'Показано, что при проектировании и эксплуатации PC на.первый план выходит проблема распределения по узлам сети программных модулей и информационных массивов, а также проблема сохранности информации. В-настоящее вре--мя эти вопросы решаются методом проб н ошибок,".зачастую приводящим к серьезным последствиям. , ' . .-' , - -: "■

Системный подход к решению задачи обеспечения сохранности ИМ и ИМ цредпататст резервирование, заключающееся в использовании некоторого числа копни и (пли) предыстории Г1М и ИМ. Па уровне отдельного узла, предлагается' осуществлять оперативное резервирование ПМ и ИМ, хранящихся в этом узле',-а на уровне сети ЭВМ н]>именять восстановительное резервирование ИМ, ИМ и-их

оперативного резерва с децентрализованным способом хранения восстановительного резерва.

.Для сокращсши размерности задан оптимизации восстанови 1елышго ретер-шфования нредл.и аетси рассматривать систему управления в виде совокупности вложенных контуров управления (рис.1). Основным назначением лтого разбиения является такая организация системы, которая приводит к необходимости внесения изменений либо и один ¡ti ее элементов, либо, в крайнем случае, в минимальное их число.

Число конурой управления должно определяйся исходя из практических потребностей проводимого исследования. При таком подходе решение тобой дос-1 а точно сложной задачи может быть достигнуто в результате последовательного >1йчшашя значений параметров сцстеяп И структурных компонентов с помо-iiu.io расчеши иа соьикупнссптатематпчрскну полечен.

На этапе проектирования предлагается решение задач опишизации восстановительного резервирования осуществлять по принципу "сверху-вниз". Для уровня сетц ЭВМ они в общем случае определяются как задачи оптимального распределения функций хранения и обработки в системе с учетом соответствующего выбора типажа вычислительных средств п узлах сети. При этом в качестве ■ целевой.функции задачи выбираются затраты ресурсов сети на реализацию заданной совокупности ИВП. Для данного уровня эти затраты можно связать со средним объ'маи передаваемой в се ¡и информации при вьшо.шешш всех ИВП совокупности.

В mt:r;pa\ ynpaiijiciih.i mr.KíieiО уровня (узеп сети ЗИМ) задачи оптимизации воссмноььгелыюго резерва выражаются в распределении ИМ и ИМ и их вос-становшелыкя о резерва между несколькими ЭВМ с улетом их Приоритет и интенсивное ni решения, oipdiHi4r:mii h.i -дЧе». на'::»:«« и время решения каждой задачи, л чаК/Кс в определении ipeíV. счете, ял>- о-.;с. и ••„ |,||Я заданного уровня показателя сохршшогти Hii(ji"j).M.im'ii объема вас* ын>.шн. -п.ною рес-рва каждого ПМ .ц ИЛ}..Причем решение залами ..ншмнзации »с^сган^и.яельцпго резервирования на этом уровне целесообразно осуществлять по критерию максимума вероятности решения всех <адач, что «юзволш осушсавнп. выбор нс.иг'елей информации, ]ре0>е:.мы;ч дл, хранения ПМ, ПМ и их ре<ерва m лапе проектирования ВС. Та к'им образом,'решение, последовательности задач оптимизации иозв>> шет определять и у точнять размещение информационных ресурсов на этане проектирования ВС. * '

На лапе функционирования ВС задача распределения njioipaMM, информационных массивов и их восстановительного резервированная решаекя при выходе из строя отдельных компонентов сети ЭВМ и при вводе в эксплуатацию новых IIM, ИМ или элементов сети ЭВМ.

Для повышения устойчивости ИВП на этапе экснл>«иацни ВС-иредлагаею1 распределение (перераспределение) информационных ресурсов осуществлять по

принципу "снизу-пверх'\ т.е. первоначально на низших контурах управления (узел сети), а затем - на верхних (уровень отдельных контуров ЭВМ).

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

Предложенный подход и методы распределения информационных ресурсов, естественно, не исчерпывай^ все возможные ситуации, связанные с оптимизацией восстановительного резервирования На различных уровнях их-представления. Эти задачи демонстрируют общую идею, заключающуюся в предварительном определении на стадии проектирования и настроит! системы в ходе эксплуатации такой организации восстановительною резервирования, которая позволила бы осуществить в некотором смысле оптимальным образом реализацию заданной в системе совокупности ИВП.

Вторая глава посвящена формализации задач восианоиительного резервирования данных в системе вычислительных средств ВС и разработке методов их решения.

Разработана общая математическая модель оптимизации информационно-вычислительного процесса в СВС на уровне сети ЭВМ, которая формулируется следующим образом. Пусть задана сеть (контур управления), состоящая из Ь ЭВМ, каждая из которых имеет пт-(] = 1,Ц пунктов обработки'информации (микроэвм, дисплеев и т.п.). В сети решается. К задач, которые используют данные из М информационных массивов. На каждом И-м пункте ]-й ЭВМ (¡=1> 2, . . , ,'Ь; Ь=1, 2,....т,) решается строго определенный круг задач с использованием определенных информационных массивов и генерацией соответствующих запросов.

При этом примем, что планы оптимального распределения Г1М, их восстановительного резерва и объем резерва ПМ известны. Оптимальное распределение (¡N1 и их восстановительного резерва задано матрицами X' ЧК" Рас_

иредеденне ИМ и их резерва по узлам сети определяется планом распределения задаваемым матрицами У = |уГ)|, Ф = [срм| ,-где'.

[1, если к - й ПМ размещается на й ЭВМ, '' [О, в противном случае;

П, если {"-й ИМ размещается на _|-й ЭВ М,

[О, в противном случае;

[1, если резерв к - го ПМ размещается иа ] - й ЭВМ,

Ч'мН, ' ' ' ■" '

(О, в противном случае;.

(1, если.резерв Г - го ИМ размещается на й ЭВМ,'

Ф, - ■ - • '

' [0, в противном случае;' ■ ' ,

к- 1,2,...,К, Г=1,2„..,М, р1,2,...Д..

Обозначим через z*k , Zf объем восстановительного резерва к-ro ПМ и f-ro ИМ (число копий (предысторий) k-ro ПМ , f-ro ИМ) (k = 1, 2,...,К, f = 1, 2,..., М) соответственно. Объём восстановительного резерва k-го Г1М известен по результатам решения задачи оптимального распределения ПМ и их восстановительного резерва. ........

При постановке задач оптимизации восстановительного резервирования в сети ЭВМ могут быть использованы следующие критерии: максимум вероятное i и решения всех задач; минимум объема информации циркулирующей в сети.

По критерию максимума вероятности решения всех задач математическая постановка задачи имеет следующий вид: необходимо определить значения переменных f(j=J,2,,,.,L; f=i,2,.,„M), такиечто

Р-тахПППР^Су^) (1)

¡-1 h-l k=J

при ограничениях

T;ráTj7>j = l>2,...,L;h = l)2í...,mj;k = l,2.....К; (2)

AjkkáA^,j = l,2,.„>L;h = lX,,mj;k = l,2,...(K; (3)

. I(yri+>rJir)5fáVi,j = l,2>...>L; (4)

£yf)=i,i' = l,2,-,M; (5)

У о = (6)

t<P(J=l,f = l,21...,M; (7)

i-i

е>гНМ; ' (В)

Z ,= (0,1,2,3,,..) (f = 1,2,...,М; j = 1,2,...,L), (9)

где Pjt,i, Т-^.Л^-вероятность, время л объем лог ока информации, циркулирующей в сети при решении k-й задачи h-м абонентом j-й ЭВМ

L р М 1. ' ^ _ ' ' g

Pjh к ~ Т jhk ¿C^jlikl ^jllik Хк| ПХ! У f г ( к f г ^ |rkf )J

l-I f=l H

I L

ijhk"= 2X,(Tjlllk +Q +Qjhk( tkl) + rji,k i-i

M 1 - — -D

&jhkf Z(Tlrkf+Qlkfr.tfr)yrr-Ajbr-VÍXbC feljH+^líbkl¡f+4, úk )] +

L¡4 • . N

M l. 4jhkf _ L

+ II Zyrr fc.1 Mf +Fir I <qf +Q ikfr £>л (FrIlf +F|r S ,)] }}

f«l r»l i=1

V -объем ВЗУ j-н ЭВМ; > ¿>f - объем f-го ИМ;

Т"ь°к - максимально допустимое время решения h-м абонентом j-й ЭВМ k-¡ задачи; . ,

А"°Кк - максимально допустимый объем информации- циркулирующей р системе при решении h-м абонентом j-й ЭВМ к-и задачи.

Отличительной особенность^ этой модели является возможность комплекс-лото и взаимосвязанного решения задач распределения ИМ и их восстановительного резерва с системе вычислительных средств, а также определения объема резерва. ' ' ' ■

Для сокращения размерности и вычислительной сложности общей 'задача оптимизации восстановительного резервирования в ВС предлагается произпсст! ce декомпозицию на три взаимосвязанные подзадачи: распределения ИМ по узлам сети, распределения восстановительного резерва ИМ по узлам сети, определения объема резерва для каждого ИМ.

Задача распределения ИМ по.критерию минимума обьема информации циркулирующей в сети, может быть сформулирована следующим образом. Определить значения у <j=l,2,...,L; f=l,2,...,M) такие, что

1, mj к

A = min£llAjhk(y)

j=l h=l - - . при ограничениях (8), (5), (6), и

PJh4 > J =' .2.».,'L, h = l',2,..„ m,, k = 1,2,..,, M,

- Vt> J -1,2,..„L.

¡ i ■

Допущение: вероятность разрушения ИМ в процессе эксплуатации и храпе ния равную.нулю

Задача относится к классу линейных задач дискретного программирован!!) со смешанными ограничениями.

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

нулю(г'к,2 ,= 1), математическая модель распределения восстановительного резерва по узлам сети имеет следующий вид:

Определить значения ф8 (Г=1,2,...,М; Такие, Что

1. к .

Р = тахПППР,,(ф)

11=1 к=1

при ограничештях (2), (3), (7), (8) И

.....¡..

Г-1 - .

Данная задала является задачей целочисленного линейного программирования.

Математическая модель определения объема восстановительного резерва

представлена в виде: определить значения г г (Г=1,^,...,М) такие, что . I. '"■) к _ ■

Р = тахЛПП^ьк.С2) при ограничениях (2), (9) и

' И !.-! к"! - ..... ............'

М

1(Уп+Фп2)6, ^1,2,....Ь

Данная задача является задачей оптимально; о резервирования.

Таким образом, образующиеся при декомпозиции общей модели ыпими^ ции посстановшелыкно резервирования в сеш ЭВМ ВС задачи.оптимизации распределения ИМ, а также их восс1ановителыюю резерва по узлам сеш и ошимн зации объема восстановительного резерва ПМ, сведены к стандартному виду задач дискретного программирования, что позволяет использовать для их решения су. шествующие методы. Однако, для решения этих задач в вычислительных системах, функционирующих в режиме реального времени, необходимо повышение эффективности существ} ющнх и разработка новых методов онтимишинн.

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

1) включение в схему ветвления нелинейных'о> раничсииГг:

■ 2) решение редуцированной задачи без учета нелинейных шрлппчеинй и на полученном множестве допустимых решений проверка выполнимости этих ограничений.

При решении задачи с Использованием первого подхода прс/матюн» ал» о-ритмы, основанные на идеях методах ветвей и границ. Для определения множества допустимых решений редуцированном задачи пред.таГ.юки модифшшронлиннн

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

Основными направлениями совершенствования метода ветвей и границ является поиск рациональных схем ветвления и определения границ решения.

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

В общем случае задачи ЦЛП Можно представить в следующем виде. Требуется максимизировать целевую функцию

С=--тах££с^ (10) .

Н ы

при ограничениях

п А,

£Ёа|Цх1]<Ь1)1 = 1Д...,ш, (И)

£хк,< 1Л = 1,2,:.,п, (12)

Ы

ХЧ £{0,1},к = 1,2,...)Д^о = 1,2,...,п. (13)

Разработаны и теоретически обоснованы три способа вычисления границ решения на основе теории двойственности;.

Способ!. Решением двойственной задачи для каждой вершины.

/ т т+п ^

г^М^тп 2>/у( + £уЛ (14)

1=1 »=т+|ч1 /

при |Х,У, +У,1^>си, (15)

к = 1,2,...,А 3=1 +1,1 + 2,,..,п,

ь=ь,- ¿а,и, у, 0,- (16)

I = 1,2,...,т,т + 1 + 1,...,гп + п.

Способ 2. Решением двойственной задачи на уровне.

^.Ы^ь/у;* £у„ (17).

где у' - " решение двойственной задачи

т

к = 1,2,Л', j - £ 4 1, t + 2,..., n,

i

м

Ь/ - b, - £ a,kj- - min aikf.

k€S,

где min alk, - минимальное значение i-ro ограничения среди переменит к

1 -ГО уровня.

Способ 3. Однократным решением двойственной задачи с исиоль »ованием двух вариантов:

а) величина ZSl(xkl) определяется ныражением (1 7). но у' = (у,',у!. ...у',, ,) - решение двойственной задачи (14) - (16);

б) определяйся оценка грячицп решения при ве»ьлсиш; вс-;: псрг:.!:::!'^ с использованием результатов решения двошлвеннои задачи (И)-(1б) стсрг-нч"" ными методами. Если применить градиентный метод, то при вычислении двойственной переменной на р -ой итерации по формуле

nun р т , , ,

yiW-mina"'ti kj

Необходимо определить номер j условия (15), которое обеспечивает min у,'1', и сформировать ;iay.«.ieptiMli маселв ■ ■ ■

Г

.! L2....,VA, i - 1-2.... m + n

i и J

При этом ч;, =у,(р|.

По иелнчлшш p.'Ctnu д.иирнтма дпоПпг.еш!"- решения усеченных .■р "/сдаются чыр ¡лл'миямп

Л' А

__ щ -г| ' J = ' . _

гр, = 1 I

гдеЧ;„„,=0, ¡ = i,2,..,m + n, А,' = £Ал Л,,'- О

........../»I

'Величина Zs определяется по формуле

m . tii + l)

+ - Z'VUU '

.=1 1---ПИЫ

Для приближенного решения двойственной задачи рл ¡работай шераинон ный алгоритм; оСнОванпЫй на идеях градиеижою метода.

Для получения первого допустимого решения С',, p.u.paöoian алюри1м! ос номнпый ид идее пошагового конструирования решений.

■■ ... Выбор переменной для включения инлекса в мшг-тество производится с ««»-мощыоусловия •

Hs..(x,:)-max 11,(4,,).

i 1

Для отсечения бесперспективных вариантов использу ется условие , Н5,(х„)<С0.

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

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

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

Я = £г,(Х)) , (18)

при ограничениях

¿аДх^Б,, 1-1,2,.. .,М, (19)

и ■

Х, = 1,2,...А,, (20)

где а,(х,)>0,гДх,)>0. Н,2„..,М,)=1.:!,...,п.

На основании принципа оптимальности метода динамического программирования можно составить два функциональных уравнения:

= (Рн. ~¿2»(*.)>■••>О», -(^(х,,)]^ г„(х,)},

п=1,2.....N. т-1,2,...,М; (21)

.......Г>"п«.)= тах{рП4| [п"|„ -ё,п(хп),П3го - а^.Ск^.....1>°„-«1и,(Х;))+1,|(хп)}.

п=Ы,М-1,...,1, т=1.2,...,М, (22)

где Р,„-¿ЙДх,), О^ХаДх^Л^иг.-.ш;

......».....шах|^г^(х)||]с111(х))5Рт1х) е Х,,1 = 1,2, .,т|-п=1,2,

т«1,2,...,М, .¡ = 1,2.......

......Р™) = тах(£гДх))|£с)11(х))<09,„,х)бХ),!=],2.....т),т=1,2,

и-» ) 0<Р°„, <0,, Ь=1,2.....т .

Функциональные }равнения (21), (22) отличаются от обычных функциональных уравнении тем, что количество ограничений п них не является постоянной величиной, они могут быгь решены при различных значениях т-!,2,....М.

На предоаршелыюм 'лапе определяется допустимое решение цслсчислен-jidi чц;)ч« - значение рекорда R с помочило олгоригма, осночпчного на илее по шлювон) K«!ucipyiipoii<uiiit; вариантов: и решение двойственной задачи. Если значения К, и 7. совпадают, то опиьмалыюс решение получено лрмбллженммн иргр-ж\ч. В противном сйучае применяется процедура предварит'елытсчо скрашеми.; p-ií.'.iepuoc i и задачи.

Для исключения бесперспективных переменных используется условие

r-+f,'¡> ,-.i;Vv;+ Yv. у,;., > R.„,

i.| Í.Í.HI

j = l,2,...,N, k = l,2,...,AJ.

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

Из топомическол интерпретации двойственной задачи следует, что двойственные переменные Y = {у,,...,ум} определяют оценку каждого фактора (ограни-чепи;: исходной задачи) для данного производства. Следовательно, чем больше :,;•••!. n::i . е • .¡v-rr-rnííft м'м Гнысс жсст::им я?тя?тс.« гпотпртоrnvwinee

е.", А I . 1 ~> 1 C!. , : I j :0 , V ' I ' ' : "> . ' ч i 1'!V-Л Л : О > JVI ! i i Ч 'Л i 11'' I К YO '1! ^ И 1TÍ >•41 11 Г

'. ■> ■■ М.Ц-.Ц1 ¡„и- L I (. л л' j е у . .i, . у (i i г■

Вы'шс.нпелншш npoiin«, начинаемся с решечня ф>нкш101м.и,н.ч.1 ; р:.пцг пил (Г 1) при. hi r I. О7к>сиова1ву что об;,ем треоуемон помяли ЭВМ и врем;! реии пия 1.1 ¡ in и при использовании метода Bctpennoio решения функциональных и1'11' пенни динамическою программирования в основном определяемо) решением <а дачи по первому ограничению. Поэтому при rrt = 1 вводится дополнительный от сев оссперснекл'ивпых иаридггтог? по целевой функции. При этом рассматриваются только члены последовательности Гп(1)п) (n = l,2, .,N), которые обеспечивают

выполн'ениё'нёрашгетва ■ - ■ . . .. ......... .. .....

; r(D,)-tZ„>Rc, ,. (23)

. .•-' где Z„. определяется выражением

' .Z.^D.-DJy.+ ^y,,

. y,' (¡ = 1,2,...,N ■»']') - решение двойственной заЧачн при М-1,- •

Решением уравнения (21) с использованием неравенства (23). определяйте.! . оптимальные последовательное!»! f„{plV), • coo uiei иную ¡une им. з.ншснмисш xjf'hrjxj (и = N,N-1 ,*...,!) и функшти DlS(f,;) (in2,3,...,M). "Значения последовательностей fN(I),..)и D..(Г„) (М.2....,М)" позволяю! определим, ч-осси--

¿o-

мальное значение fN(D,N) = RM, при котором выполняется ограничение (.19) при i=l, и максимальное значение f„(Dm) = R,2, при котором выполняется (19) при ¡=1,2,...,М. Если R|,=RU, то значения переменных xn (n-l,2,...,N), еоответст-Ьующих значению Rn, являются решением задачи ЦЛП, в противном случае (R,, > R ,г) осуществляется переход ко второй итерации, которая состоит в решении функционального уравнения (22) при т=2.

Решение функциональных уравнений при nv=2,3,...,M происходит аналогично. На k-й итерации используется дополнительное условие, которое имеет вид max[fn(Dln,D¡„v..)Dl„) + Fjltl(Dl -D.^D, - Dbi.-,Dk_, -Dk.,„)]>R,

n = l,2.....N, k = 3,5,7,.,.,

где R - max[Rt,Rl,,R¡¡,...JRk l ¡ j, при прямом порядке решения (21) и maxfFJD*,,,,0°„,...,D\„) + f„w(D, -DVD, -DV'.«)]>R.

n - N, N — 11, k = 2,4,6,..., . при обратном порядке решения (22),

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

Анализ результатов экспериментального исследования алгоритмов получения первого допустимого решения (А11) и Приближенного решения 'двойственной задачи (Ал) показывают, что они имеют достаточно высокую Точность И приемлемое время решения. Средняя относительная погрешность полученных приближенных решений изменяется в пределах (0-7,28)%, а в 75% случаев она не превышает 3%. В 65% случаев решение, полученное алгоритмом А11, Являлось оптимальном, а в 95% случаев отличалось от точного не более чем ría 8'=10%. Время решения алюритмами Ац и Ад невелико, что в итоге определяет эффективность их применения в методе ветвей и границ. 1

Наиболее эффективным способом является использование результатов однократного решения двойственной задачи итерационными алгоритмам!!. Среднее время решения с применением данного способа в 7-42 раза меньше относительно первого, в 3-13 раза меньше относительно второго н в 1,1-2,2 раза меньше относительно третьего способа. С ростом числа ограничении и Переменных задачи это преимущество возрастает. Увеличение числа просмотренных вершин от первого к третьему способу объясняется тем, что точность вычисления границ путем решения двойственной задйчи больше, чем решением двойственной задачи для уровня и тем более чем однократным решением. Этим же ббьяскяется и увеличение процента вершин, отсеченных по целевой функции.

■ . Таким образом, наиболее простым а эффективным способом определения рерхних границ является однократное решение двойственной задали приближенными йтерашклшьЫи алгоритмами.

Оценка эффективности ме+ода встречно!о peUieiikij.функциональных уравнений, использующею Принцип двойстЬенностй для упорядочивания ограничений но жсс i кос ni и отсева бесперспективных переменных при решении задачи по пер-

вому ограничению, и сравнения его с алгоритмом проводились по времени peine ния задач и числу итераций.

Результаты экспериментов показывают, что упорядочивание ограничений по жесткости в способе встречного решения дает выигрыш но времени в 2,3-) 4,8 раза за счет ¿менцпения числа решений функциональных уравнений динамическою npoi раммиропания (числа итераций). Например, при решении задач размерностью 20-20-6 среднее время решения по предлагаемому алгоритму равно 91,7 секунды, а с использованием существующего способа встречного решения - 361,3 секунды. -по п четыре разя больше. Jh десяти задач в одной онг'имялмюс решеннс нолучеио приближенным, меюдом, семь задач решены за одну итерацию и дне задачи - за две Итерации.

проггрпз ртр^ботяирн* ччте«атичег.ких моделей, ме-»идов и алгоритмов оптимизации ппсстз^оритечьнпт ¡клонирования инфор;.;а цци на отдельных контурах управления подтвердила их эффективность и целесообразность включения в состав специального математического и программного обеспечения. ■ - • ' •

Разработанные математические модели, методы и алгоритмы оптимизации восстановительного резервирования информации в сети ЭВМ могут быть использованы на этапе проектирования и в период эксплуатации ВС при организации ИВП в системе вычислительных средств сети с целыо повышения его устойчиво-С1Й и ЬОс'сйечсипя есхряпттссти информации. • • • ........

ЗАКЛЮЧГШ1К

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

Переход к созданию ВС на базе вычислительных сетей во многом предопределит возможность существенного повышения устойчивости ИВП и обеспечения v»\(wniii)cin информации в территориально-распрск ленных вычислительных се ту >о «см распределения (перераспределении) ПМ и ИМ н системе ВС сети при изменении ее состояния с > четом их резервирования, т.е.. путем реконфигурации сети. -

Системный подход к решению задачи обеспечения сохранности ПМ и ИМ предполагает резервирование, зпкчючпюшееся п использовании некоторою числа копий и (или) предыстории ПМ и ПМ. На \pomte от ярлыки о узла предлагается осуществлять оперативное ре кэширование ПМ и ИМ, хранящихся н этом узле, а' на уровне, сети ЭПМ применять восстановигелмюе резервирование HM, I1M и их оперативного резерва.г денептрллтпппгтным viihcih'iom чрлп.лтя mstcTaauBUiwil.-. пою резерва, -

Па основе аиалтыа характеристик различных носителей информации еле,¡ли тчяшд о том. что на современном 'маис развитие вычислителмюи техиики накипи-'

1ели на оптических дисках наиболее полно удовлетворяют требованиям долговременного хранения информации и могут использоваться при восстановительном резервировании информации в ВС.

Оптимизация распределения ПМ и ИМ, с учетом резервирования для терри-ториально-распределенных вычислительных сетей со значительным объемом информационно-вычислительных работ, представляет собой задачу большой размерности. Поэтому предложено использовать подход, основанный на структурной декомпозиции и представлении ВС в виде совокупности вложенных контуров управ нения (по принципу "сеть в сеть"). Разбиение по контурам управлений'осуществляется в соответствии с организационной структурой DC и определяется задачами исследования.

Обоснование путей организации распределения ПМ, ИМ, а также их резерва на этапе проектирования и в период эксплуатации ВС позволяет определить два пути: на этапе проектирования распределение осуществлять по принципу "сверху вниз", в период эксплуатации и боевого применения - "снизу вверх".

Обоснование критериев оптимизация и'принципов распределения и восстановительного резервирования ПМ И ИМ в системе вычислительных средств сети позволяет рекомендовать в качестве критериев оптимальности восстановительцого резервирования минимум о|5ьема информации, передаваемой по каналу связи, . максимум вероятности решения всех задач. .

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

Для сокращения размерности задачи оптимизации восстановительного резервирования предложена ее декомпозиция на ряд взаимосвязанных подзадач, а именно: ( •

• оптимизации распределения ИМ в системе ВС без учета их восстановительного резервирования при известном распределении ПМ;

• оптимизация распределения восстановительного резерва.ИМ без учета его разрушения (без определения объема восстановительного резерва) с учеюм заданного распределения восстановительного резерва ПМ;

• оптимизация объема восстановительного резерва ИМ.

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

• оптимизация распределения ИМ'по критерию минимума передаваемой информации по каналам связи - к классу задач ЦЛИ со смешанными ограничениями; '

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

• оптимизация объема восстановительного резерва - к стандартной задаче оптимального резервирования.

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

Сформулированное задачи распределения и оптимизаций восстановительного резервирования программных модулей и информационных массивов в сети ЭВМ относятся к классу задач комбинаторного типа. Трудоемкости сформулированных зада*! выдвигает требование дальнейшего совершенствования й модификации алгоритмов ее решения.

Для сокращения'вычислительной сложности определения границ рещения

могут быть использованы разработанные и обоснованные способы на основе теории двойственности: решение двойственной, задачи для каждой вершины дерева ветвления; решения двойственной задачи для уровня; однократное решение двойственной задачи; однократное решение двойственной задачи с уточнением границы итерационными алгоритмами.. Результаты экспериментальной оценки способов определения границ решения с использованием теории Двойственности показали, что наиболее эффективным является однократное решение двойственной Задали Итерационными Методами, который позволяет уточнять оценки переменных и определить порядок их ветвления. ''■:'■

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

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

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

ПУБЛИКАЦИИ по TEMI: ДИССЕРТАЦИИ

1, Киселев В.Д., Есиков О.В., Святенко К.В. Декомпозиция задачи восстанови-■ -тельного резервирования программных модулей и информационных массивов

в сети ЭВМ,- НТК М'9 (сборник тетнеон докладов). Гула: ТОЛПУ, 1993 г.

2. Есиков О.В., С'вятеико К.П. Обеспечение сохранносш информации в .чокаль-• г- ных сетях ЭВМ.--ПТК N~:9 (сборник кчисов докладов). Тула "1 ПЛИУ, IW.ir.

3. рейкой O.B. , Святенко К.В., Матвеев ДВ- Имитационная модель оценку эффективности перспективных ДСУ- НТК №10 (сборник тезисов докладов). Тула: ТВАИУ. 1995 г.

4. Киселев В.Ц., Бесков р.В.,Свят?ИКР К-В-. Логврнрв C.Ç. Анализ влияния восстановительного резервирования на. эффективность функционирования АСУ, построенных на базе сетей ЭВМ- ЦТС N 14. Тул^ : ТВАИУ, 199?: С.-144-148.

5. Киселер В.Д., Крутских В.Д., СвятеНко К.В. Определение типа носителей восстановительного резерва 'информации в территориально-распределенных ВС. НТС N 5. Санкт-Петербург: МО РФ. 1998. С.-27-31.

6. Киселев В.Д., Святенко К.В. Обеспечение сохранности информации в ВС специального назначения, построенных на базе сетей ЭВМ. НТС N 5. Санкт-Петербург: МО РФ, 1998. С,-38-41, / •

7. Киселев В.Д., Новиков В.В., Святенко {СВ. Распределение задач в системе обработки информации методом альтернативного программирования.- НТС N 15. Тула : ТВАИУ, 1998. С.-134-138.

8. Святенко К.В., Новиков В.В. Оценка способов ветвление переменных в методе ветвей и Границ. - НТСК 15,Тула: ТВАИУ, 1998. C.-175-179.

9. Святенко К.В,,- Федрсов Е.И-, Лагутин H.II. Оптмизация информационно-вычислигелыюго процесса на объектах ВС - НТС N 15. Тула : ТВАИУ, 1998. С.-179-182.

10. Есиков О.В., Святенко К.В. Принципы построения систем защиты информации в современных АСОД - НТС N 16. Тула : ТАЙИ, 1999. С.-82-85.

Подписано и печаи. ИХ «♦Ч'а'Фррмат бумага 60x84 1116. бумаг» типографскаа.М 1 Офсетная печать. Усл.нсч. л. < 1 .Усл.кр.-огт. /, / .Уч. изд. л. .

Тира* ЭЮ.Закв! . .

Тульский тсударствениый уницерситет. 300600, I. Тула, пр. Левина, 91. Релакииоипо- издательский центр Тульского государственною университета. 300600, г. Гул«, ул. БолЛнна, 151

Введение.

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

1.1 Структура и краткий обзор основных направлений совершенствования ВС «ГК «Росвооружение».

1.2 Характеристика и особенности разрушающих факторов, влияющих на носители информации и сравнительная характеристика устройств хранения информации.

1.3 Обеспечение сохранности информации в вычислительных сетях.

1.4 Анализ видов и стратегий резервирования.

1.5 Определение областей эффективного использования восстановительного резервирования.

1.6 Обоснование общего подхода к решению задач оптимизации восстановительного резервирования.

Выводы по первой главе.

2. Математические модели и алгоритмы оптимизации восстановительного резервирования информации в ВС.

2.1 Общая математическая модель оптимизации восстановительного резервирования.

2.2 Декомпозиция общей задачи на систему взаимосвязанных задач.

2.3 Методы решения задач восстановительного резервирования информации.

Выводы по второй главе.

3. Экспериментальная проверка моделей и методов оптимизации восстановительного резервирования информации.

3.1 Экспериментальная оценка эффективности методов и алгоритмов оптимизации.

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

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

Наличие широкой сети региональных представительств в более чем 20 странах также требует наличие современной ВС.

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

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

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

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

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

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

Существует большое число работ посвященных сетям ЭВМ. В работах В.М.Глушкова [4], Д. Флинта [5], Э.А. Якубайтиса [6,7] излагаются основные принципы построения вычислительных сетей, организация сетей передачи данных и связи, их анализ и синтез. В работе Г.Т.Артамонова и В.Д. Тюрина [8] излагается оригинальная система топологических инвариантов, позволяющая эффективно решать задачи определения изоморфизма и автоморфизма сетей. Исследуется влияние топологических характеристик сетей на их надежность, пропускную способность, стоимость и ряд других системных характеристик. В работе Г.Ф. Янбых и Б.А. Столярова [9] рассматривается проблема оптимизации физической структуры информационно-вычислительных сетей. Методы и алгоритмы синтеза и оптимизации структуры, централизованных и распределенных сетей ЭВМ с единых методологических позиций рассмотрены Ю.П. Зайченко и Ю.В. Гонта [10].

В работах В.А. Балыбердина [11,12,13] предложены единый метод исследования системы вычислительных средств (СВС) сетей ЭВМ, основанный на выделении и рассмотрении совокупностей взаимодействующих информационных процессов, протекающих в СВС, комплекс аналитических моделей совокупностей информационных процессов для решения задач анализа сетей ЭВМ и методы многоуровневой оптимизации для решения задач синтеза.

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

Однако основной акцент при создании ВС на базе сетей ЭВМ делается на решение следующих проблем:

- организации информационно-вычислительного процесса (ИБП) в системе вычислительных средств сети ЭВМ;

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

- организации функционирования распределенных баз данных.

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

Если рассмотреть накопленный опыт при решении задач оптимизации и повышения устойчивости информационно-вычислительного процесса (ИВП), сохранности информации в сетях ЭВМ, то необходимо отметить работы В.В. Хорошевского [14], Е.Н.Турута [15,16]. O.K. Кондратьева [17], отражающие прогресс, достигнутый при решении задач повышения устойчивости ИВП. Работы А.Г. Мамиконова, В.В. Кульбы, С.К. Сомова, А.Б. Шелкова [20,21,22] посвящены решению вопросов повышения достоверности и сохранности информационных модулей и программных массивов в вычислительных сетях за счет организации оперативного и восстановительного резервирования.

Практическое решение вопросов синтеза сетей ЭВМ и организации их функционирования связано с развитием теории и практики оптимизации, которым посвящены работы О.Г. Алексеева [23], B.C. Михалевича [24,25], И.В. Сергиенко [26], A.A. Корбута, Ю.Ю. Финкелынтейн [27].

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

Работы, проведенные в этом направлении к настоящему времени, обладают рядом существенных недостатков:

1. Не разработан системный подход к повышению устойчивости ИБП и сохранности информации на этапах проектирования и эксплуатации ВС.

2. Недостаточно формализованы способы и методы обеспечения устойчивости ИВП и сохранности информации (модели распределения и перераспределения программных модулей и информационных массивов по узлам сети ЭВМ).

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

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

Актуальность задачи обусловлена: необходимостью повышения эффективности функционирования вычислительной сети «ГК «Росвооружение» за счет придания ей свойств устойчивости ИВП, необходимостью разработки и совершенствования теоретического аппарата обеспечения сохранности информации, исследования задач многомерности и дискретности задач оптимизации.

Объектом исследования являются автоматическая система обработки информации подразделений «ГК «Росвооружение»

Предметом исследования являются методы обеспечения сохранности информационных массивов в вычислительных сетях «ГК «Росвооружение».

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

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

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

2. разработка системы математических моделей оптимизации ИБП в ВС с учетом резервирования программных модулей и информационных массивов;

3. повышение эффективности существующих и разработка новых методов решения задач оптимизации;

4. оценка эффективности, обоснование рекомендаций по использованию разработанного теоретического аппарата.

Содержание этих решений изложено в трех главах настоящей работы.

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

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

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

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

Основными научными результатами, выносимыми на защиту являются:

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

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

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

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

Практическое значение и реализация работы. Предложенные методики, методы, модели и алгоритмы использованы при проведении ряда работ по созданию образцов комплексов средств автоматизации, а также в силу своей общности могут найти применение при разработке, эксплуатации перспективных комплексов средств автоматизации различных уровней управления, методы и алгоритмы доведены до рабочих программ и позволяют решать широкий круг научно-технических задач. Основные практические результаты диссертационной работы внедрены: в 3 ЦНИИ МО России; в Таганрогском авиационном научно-техническом комплексе им. Бериева; в учебном процессе Тульского ВАИУ в дисциплине "Исследование операций"

Апробация работы и публикации. Материалы диссертации докладывались, обсуждались и одобрены на НТК Тульского ВАИУ (1997, 1999 г.г.), Михайловской артиллерийской академии г. С-Петербург (1998 г.), на расширенных заседаниях кафедр "ЭВМ и ВС", "Математическое, программное и информационное обеспечение ВС" Тульского артиллерийского инженерного института. Материалы диссертации опубликованы в 10 печатных работах в ведомственных научно-технических изданиях:

Киселев В.Д., Есиков О.В., Святенко К.В. Декомпозиция задачи восстановительного резервирования программных модулей и информационных массивов в сети ЭВМ,- НТК №9 (сборник тезисов докладов). Тула: ТВАИУ, 1993 г.

Есиков О.В., Святенко К.В. Обеспечение сохранности информации в локальных сетях ЭВМ.- НТК №9 (сборник тезисов докладов). Тула: ТВАИУ, 1993 г.

Есиков О.В. , Святенко К.В., Матвеев Д.В. Имитационная модель оценки эффективности перспективных АСУ- НТК №10 (сборник тезисов докладов). Тула: ТВАИУ, 1995 г.

Киселев В.Д. , Есиков О.В.,Святенко К.В., Логвинов С.С. Анализ влияния восстановительного резервирования на эффективность функционирования АСУ, построенных на базе сетей ЭВМ- НТС N 14. Тула : ТВАИУ, 1997. С.-144-148.

Киселев В.Д., Крутских В.А., Святенко К.В. Определение типа носителей восстановительного резерва информации в территориально-распределенных ВС. НТС N 5. Санкт-Петербург: МО РФ. 1998. С.-27-31.

Киселев В.Д., Святенко К.В. Обеспечение сохранности информации в ВС специального назначения, построенных на базе сетей ЭВМ. НТС N 5. Санкт-Петербург: МО РФ. 1998. С.-38-41.

Киселев В.Д., Новиков В.В., Святенко К.В. Распределение задач в системе обработки информации методом альтернативного программирования,- НТС N 15. Тула : ТВАИУ, 1998. С,-134-138.

Святенко К.В., Новиков В.В. Оценка способов ветвления переменных в методе ветвей и границ. - НТС N 15. Тула: ТВАИУ, 1998. С,-175-179.

Святенко К.В., Федосов Е.И., Лагутин H.H. Оптмизация информационно-вычислительного процесса на объектах ВС - НТС N 15. Тула : ТВАИУ, 1998. С,-179-182.

Есиков О.В., Святенко К.В. Принципы построения систем защиты информации в современных АСОД - НТС N 16. Тула : ТАИИ, 1999. С.-82-85.

Выводы по третей главе

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

2. Результаты экспериментальной оценки способов определения границ решения с использованием теории двойственности показали, что наиболее эффективным является однократное решение двойственной задачи итерационными методами, который позволяет уточнять оценки переменных и определить порядок их ветвления. Среднее время решения с применением данного способа в 7-42 раза относительно первого, 3-13 раза относительно второго и в 1,1-2,2 раза относительного третьего способа меньше. С ростом числа ограничений и переменных задачи это преимущество возрастает.

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

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

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

Для сокращения размерности задачи оптимизации восстановительного резервирования предложена ее декомпозиция на ряд взаимосвязанных подзадач, а именно:

1. оптимизации распределения ИМ в системе ВС без учета их восстановительного резервирования при известном распределении ПМ;

2. оптимизация распределения восстановительного резерва ИМ без учета его разрушения (без определения объема восстановительного резерва) с учетом заданного распределения восстановительного резерва ПМ;

3. оптимизация объема восстановительного резерва ИМ.

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

5. оптимизация распределения ИМ по критерию минимума передаваемой информации по каналам связи - к классу задач ЦЛП со смешанными ограничениями;

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

7. оптимизация объема восстановительного резерва - к стандартной задаче оптимального резервирования.

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

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

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

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

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

19. Сергиенко И.В. Математические модели и методы решения задач дискретной оптимизации.- 2-е изд., доп. и перераб.-Киев: Наук. Думка, 1988.472 с.

20. Сергиенко И.В., Лебедева Т.Т., Рогцин В.А. Приближенные методы решения дискретных задач оптимизации.- Киев: Наук. Думка, 1980.-276 с.

21. Михалевич B.C. Последовательные алгоритмы оптимизации и их применение // Кибернетика. - 1965. -№1.- с. 45-55.

22. Первозванский A.A., Гайцгори В.Г. Декомпозиция, агрегирование и приближенная оптимизация. - М.: Наука, 1979. -276 с.

23. Мельник Э.М., Киселев В.Д. Об одном подходе к распределению задач между работоспособными микро ЭВМ при функциональной деградации вычислительной системы. // Алгоритмы и структуры систем обработки информации. - Тула: ТулПИ, 1990.- с. 99-105.

24. Киселев В.Д., Алексеев О.Г., Мировицкий Г.П. Сужение области поиска в задачах дискретного программирования на основе теории двойственности.// Электронное моделирование. - 1989.- Т 11.-№5.

25. Алексеев О.Г., Алексеев А.О., Киселев В.Д., Мировицкий Г.П. Применение двойственности для повышения эффективности метода встречного решения функциональных уравнений динамического программирования // Кибернетика. - 1990,- №1. с. 114-116.

26. Киселев В.Д., Алексеев О.Г. Упорядочение ограничений в методе встречного решения функциональных уравнений динамического программирования.// Экономика и математические методы. - 1994.

27. Майника Э. Алгоритмы оптимизации на сетях и графах,- М.: Мир, 1981.-323с.

28. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. Пер. с англ.- М.: Мир, 1985. - 512 с.