Математические модели и алгоритмы оптимизации восстановительного резервирования информации в корпоративной вычислительной сети «Государственной компании» Росвооружение

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

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

Наличие широкой сети региональных представительств в более чем 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 с.