MULTIPLE ATTRIBUTE COMPOSITION OF DEPENDABLE CONTROL AND DATA PROCESSING SYSTEMS

Full Text

Создание новых и совершенствование существующих систем управления и обработки информации требует решения ряда задач, связанных с формированием структуры систем, а также перечнем функций, которые должны выполнять системы в соответствии с выбранным принципом построения [1; 2]. На сегодняшний день актуальна проблема обеспечения заданного уровня надежности при формировании структуры систем управления и обработки информации с учетом ряда технико-экономических требований [3]. Для обеспечения гарантированной работоспособности систем управления и обработки информации требуется высоконадежное отказоустойчивое функционирование как программных, так и аппаратных средств системы [4]. Реализация механизмов аппаратной и программной отказоустойчивости возможна благодаря использованию программной избыточности и аппаратного резервирования элементов подсистем. Внедрение дополнительных избыточных элементов в структуру систем управления и обработки информации требует разработки программно-алгоритмических средств формирования оптимального состава систем и планирования оптимального развития структуры систем на различных этапах их жизненного цикла и с учетом динамики функционирования. Постановка задачи. Рассмотрим систему управления и обработки информации, которая состоит из ряда подсистем. Отказ любой из подсистем приводит к отказу всей системы в целом. Каждая из подсистем может быть реализована несколькими способами, характеризующимися различными значениями параметров надежности, стоимости, ресурсоемкости и т. п. Требуется определить вариант реализации системы управления и обработки информации, т. е. выбрать конфигурацию элементов каждой подсистемы, которая доставляет экстремум некой целевой функции и обеспечивает успешное решение всех задач, поставленных перед системой управления и обработки информации, с вероятностями не ниже заданных ограничений. При этом затраты также не должны превосходить заданных границ. Метод решения. Математическая модель задачи формирования системы управления и обработки информации имеет следующий вид: определить вариант v0, доставляющий максимум целевой функции P(v) = 1JPj (uj (1) j=1 при наличии ограничений n gp(v)=X gp (ujdj)) < g*, p = 1, •••, q; (2) j=1 n gp(v) = X gp (uj (lj)) > gp, p = q + 1, •••, Q; j=1 v e V, uj(lj) e Uj, j = 1, ..., n, (3) где uj(lj) - способ реализации j-й подсистемы; Uj = {uj(1), ..., uj(lj), ._, uj(lj), j = 1, ._, n - совокупность всех элементов, которые могут быть использованы в j-й подсистеме, количество элементов во множестве Uj равно tj; v - текущий вариант системы n управления и обработки информации; V = j=1 Pj(uj(lj)) - надежность (вероятность безотказной работы на заданном интервале времени) элемента lj-го типа j-й подсистемы; gp(uj(lj)) - значение р-го ограничивающего фактора для элемента lj-го типа j-й подсистемы; gp(v) - количество р-го ограничивающего фактора, израсходованного на всю систему; gp* - максимально возможное количество р-го ограничивающего фактора для всей системы в целом. Задачи (1)-(3) эквивалентны следующей задаче: найти максимум f (v) = Hfj (uj (j)) (4) j=1 при наличии ограничений (2) и (3), где fj(uj(lj)) = = lgPj(uj(lj)). Таким образом, задача оптимального формирования системы управления и обработки информации по критерию надежности сводится к задаче вида (2)-(4). Если результат решения задачи оптимального формирования неудовлетворителен (т. е. полученная надежность системы управления и обработки информации мала), но используемые ресурсы исчерпаны не полностью, то необходимо прибегнуть к резервированию элементов подсистемы, понимая под этим следующее. * Исследования выполнены в рамках реализации ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009-2013 гг. 106 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева Если произведено резервирование в j-й подсистеме, и она содержит Xj + 1 элементов (Xj резервных и один основной), то выход из строя подсистемы происходит при выходе из строя всех Xj + 1 элементов (так называемое «параллельное резервирование»). Рассмотрим задачу повышения надежности формируемой системы управления и обработки информации путем резервирования. При этом по мере рассмотрения допустимых значений технико-экономических параметров элементов подсистем будут отсеяны типы элементов, которые учитывать в дальнейшем нет необходимости. В частности, это делается при построении вариантов системы управления и обработки информации с резервированием [5]. Перенумеруем оставшиеся элементы во множествах Uj (j = 1, ..., n) после отсева их по ограничениям (2) и (3), так что Uj = (u/1), ..., uj(lj), ..., uj(Ej)}, где Sj < Ej (j = 1, ..., n). Для построения вариантов подсистем с резервированием определим максимальный Xj(lj) и минимальный X j(lj) объем избыточности (соответственно, максимальное и минимально возможное число резервных элементов) для lj-го типа j-й подсистемы. При этом будем использовать постоянные для каждой подсистемы величины: p = 1, ..., Q, j = 1, •••, n. При этом максимальный объем избыточности X j(lj) для каждого элемента, вошедшего во множество Uj, определим следующим образом: = gp*- gp(vPv(l) / j Xj (j)=p=?nq Agp gp (Mj(j)) --1 (5) где через [а] обозначена целая часть а. Минимальный объем избыточности X j(lj) для каждого элемента, вош деляется по формуле 0. — X j (j) = max p=q+1,...,Q Agp gp (Uj(lj)) -- 1 (6) j(lj) = 0, = p^j(lj ')> Несмотря на то что можно положить X* для уменьшения множества возможных вариантов реализации системы управления и обработки информации с резервированием желательно получить число различных объемов избыточности |Xj(lj)| = Xj(lj) -X j(lj) + 1 как можно меньшим. В случае когда ограничения на минимально допустимые значения вероятности отсутствуют, минимальный объем избыточности можно определить следующим способом. Будем прибавлять в j-й подсистеме по одному элементу того типа, который имеет максимальную надежность, до тех пор пока при добавлении очередного элемента не произойдет нарушения хотя бы одного из ограничений. Если же ограничения нарушаются сразу, то рассматривается следующий по надежности тип элементов. Вычислим значение надежности для построенной таким образом системы: P =П (1 - (1 - Pj (uk (lk)))) Xk (lk) +1 где Pj(uk(lk)), k t j - максимально возможная надежность, которой обладает один из типов элементов, использующийся в k-й подсистеме; Pj(uj(lj)) - надежность элемента lj-го типа, использующегося в j-й подсистеме; Xj(lj) - количество резервных элементов lj-го типа j-й подсистемы. **j(j) + 1 Из выражения P < 1 - (1 - Pj(uj(lj)))X ‘ можно определить X jj - минимально возможное количество резервных элементов, необходимых для достижения надежности, равной P или более. Ясно, что максимум надежности будет достигаться для величин Xj(j), которые, по крайней мере, не меньше полученных величин X j(j). Если определенная таким образом или по формуле (6) минимальная глубина объема избыточности равна X jj хотя бы для одного j = 1, ..., n, то максимальный объем избыточности X j(j), определяемый по формуле (5), может быть уточнен выражением X j (lj) = min p=1..., q gp - £ (Xk(lk) +1)gp (uk(lk)) gp (uk (lk)) --1 Видно, что X j(j) < X j(j). Аналогично можно уточнить минимальный объем избыточности, определяемый формулой (6), при помощи известного максимального объема избыточности X j(j). Запишем математическую модель задачи оптимального «параллельного» резервирования: P(v) = П Pj (uXjjj}) ^ max j=1 опре- при наличии ограничений gp(v) = £ gp jjo < gp, p = 1, •, q, j=1 (7) (8) gp(v) = £ gp(ujjl) - g*p, p = q+1, •, Q, (9) j=1 E V" = Пи " uXj(lj) j, uj(lj) U", j = 1, ..., n, (10) j=1 где наличие в варианте системы управления и обработки информации v = (u1(l1) J,..., u jjJ,..., un/) пеk=1 *1(l1) uj(ljMn(ln) ременной ujjjj e U” означает, что в выбранном варианте в j-й подсистеме в качестве основного и резервных элементов выбраны элементы lj-го типа, и выбранный объем избыточности равен Xj(lj )(Xj(lj) <X j (lj) < Xj(lj)). В ограничениях (8) и (10) слагаемые в левых частях, определяющие значение р-го ограничивающего фактора для j-й подсистемы для основного и резервных элементов, примут вид gp (um)) =(X j(lj) +1) gp (uj (j)). * 107 Математика, механика, информатика Вероятность безотказной работы j-й подсистемы в выражении (7) определяется в виде Р, (ujjj =1 - (1 - Р,(и, (в))"®’*1- Множество возможных вариантов реализации j-й подсистемы с резервированием имеет вид иrUV(,) | l = 1 е' • X = X** X* } UJ = {Uj(lJ) 1 lJ = 1 еJ• XJ(lJ) = X,(»’ XJ(’ j = 1,., n, число элементов в этом множестве n е j |Uj 1=ПI (Xj(lj) -Х7(У) + 2). j=1 lj =1 Представим задачу формирования системы управления и обработки информации следующим образом: _ П. _ максимизировать f (v) = I f.j (u j j) при условиях j=1 — —Xj (lj) * gp(v) = I gp (uJ(m) - gp, p = 1 •••, q; j=1 gp(v) = Igp(u mJj>) > gp, p = q + 1 •••, 6; j=1 _ t7 _XJ(,) 77 ■ i V £ V = Y\Uj, Uj(lj) e U,, j = 1, ..., n, j=1 _ _ е, гдеf v) = lgP(v); U, ={и,m 1 ^ 1..., I(| X,(I,)1 +1» l,=i множество возможных вариантов j-й подсистемы; |Uj|=|uj |,| V |=| v "|. Эта задача эквивалентна задаче (7)-(10), поскольку логарифм является монотонным преобразованием. Введение множеств U j является просто результатом замены переменной и„ на и,. с соответствующим изменением множества значений. Таким образом, имея целевую функцию и ограничения, можно перейти к формированию оптимальной системы управления и обработки информации. Оптимизация происходит по критерию надежности, тогда как на все оставшиеся технико-экономические параметры накладываются ограничения. Ограничение на систему в целом: gp(v) - gp (v), где p - критерий, на который накладываются ограничения. Одним из подходов к решению проблемы выбора является следующая итерационная процедура. Поочередно производится отсев по каждому из критериев. Для этого, рассматривая каждый критерий, для каждой из n подсистем упорядочим все типы элементов по возрастанию, согласно значениям рассматриваемого критерия. Сумма первых значений упорядоченных типов элементов представляет необходимый минимум ресурсов для формирования системы управления и обработки информации. Очевидно, что эта сумма должна быть меньше ограничения на текущий критерий как необходимое условие существования допустимых решений. Следующим шагом является определение «допуска» для каждой подсистемы, он вычисляется по формуле AgpJ = gp - gps, где gps - сумма элементов первого столбца. Все элементы j-й подсистемы, превосходящие значение «допуска», отбрасываются и в дальнейшем уже не рассматриваются. Рассмотрев все критерии, выполняем следующую итерацию. Процедура заканчивается, когда отсева элементов больше не происходит. Однако может случиться и так, что все элементы будут отброшены. В этом случае необходимо расширить наложенные на систему ограничения или использовать менее ресурсоемкие элементы в подсистемах. Резервирование элементов происходит с учетом объема избыточности, что приведет к повышению надежности создаваемой системы управления и обработки информации. Максимизируемая целевая функция будет иметь вид f (v) = I (Colg Pj + cl), j=1 где Р, - надежность j-й подсистемы; с0, с - константы (с0 > 0), значения которых можно выбрать из соображений удобства вычисления. Завершающий этап предлагаемого метода - поиск оптимального решения. При нахождении решения используются элементы подсистем с учетом объема избыточности и целевой функции. Применяется итерационная процедура, предложенная выше. Однако прежде рассмотрения допустимости по критериям рассматривается ограничение на целевую функцию. Это ограничение не задано жестким образом, а находится на каждой итерации по формуле f (v) > f* = fmax2+ fi-1 , для первой итерации /,ч = fmm, где f^, fmm - соответственно сумма максимальных и минимальных для каждой подсистемы значений целевой функции. Вычисления заканчиваются, когда прекращается отсев, т. е. найдено оптимальное решение, или же когда все элементы какой-либо подсистемы отброшены. Во втором случае приходится расширить ограничение на целевую функцию. Решением будет являться результат, полученный на последней итерации. Экспериментальная часть. С использованием предложенных подходов и моделей разработана программная система многоатрибутивного выбора компонентов гарантоспособной системы управления и обработки информации. Гарантоспособность системы обеспечивается применением мультиверсионной методологии при реализации отдельных элементов подсистем [6]. Благодаря использованию данной программной системы автоматизируется процесс выбора лучшего варианта реализации гарантоспособной системы из множества предложенных вариантов (рис. 1). 108 Вестник Сибирского государственного аэрокосмического университета имени академика М. Ф. Решетнева |ц Оптимизация состава мультиверсионной системы по критерию надежности f-~1 Параметры системы N- подсист МультиЕ;ера Стоимость |0£гьем | Время |Надежность] л 1 И 5 10 4 0,6 1 2 17 5 2 0,8 1 3 10 5 5 0,85 1 4 2 40 20 0,55 1 5 5 6 5 0,8 1 6 25 2 2 0,85 1 7 7 35 10 0,65 2 1 9 15 15 0,7 2 2 30 10 10 0,85 2 3 8 10 40 0,75 2 4 10 15 10 0,85 3 1 12 12 20 0,75 3 2 10 15 15 0,7 3 3 25 10 10 0,8 3 4 11 15 ЗЭ 0,7 4 1 5 5 13 0,7 4 2 4 10 35 0,8 4 3 20 2 5 0,85 4 4 5 6 10 0,8 v Исходные данные | "Глубина" | Поиск опт, решения | Ограничения по стоимости <=50 по объему <=65 по времени <=65 “Константы СО = 96 С1 =22 Г" показать элементы оставшиеся отсев по типам Рис. 1. Главное окно программной системы многоатрибутивного выбора компонентов гарантоспособной системы управления и обработки информации 1.4 Оптимизация состава мультиверсионной системы по критерию надежности НИЗ 21 (1.6.5) 20 (1.5.5) 15(1.3.3) 14(1.2.1) 12(1.4.5) 0(1.1.1) 21 (2.3.4) 15(2.2.4) 7 (2.1.1) 13(3.3.2) 20 (4.4.4) 10(3.1.1) 12(4.3.4) 7 (3.2.2) 12(4.3.4) 7(41.1) 20 (5.4.4) 15(5.2.2) 12(5.3.4) 0(5.1.1) 5 (1.4.5) 110 (1.3.3) 10(1.2.1) 10(1.5.5) 15(1.6.5) 15(1.6.5) 10(2.2.4) 10(2.2.4) 20 (2.3.4) 12(3.1.1) 5(43.4) 20 (3.3.2) 10(4.4.4) 20 (3.3.2) 10(4.2.1) 10(4.4.4) 10(5.3.4) 12(5.2.2) 20 (5.4.4) 20 (5.4.4) 5 (1.3.3) | 6(1.4.5) 12(1.5.5) 20 (1.2.1) 20 (1.2.1) 20 (1.2.1) 15(2.2.4) 15(2.2.4) 30 (2.3.4) 12(3.1.1) 6 (4.3.4) 15(3.2.2) 12(4.4.4) 30 (3.3.2) 10(4.2.1) 12(4.4.4) 10(5.2.2) 11 (5.3.4) 22 (5.4.4) 22 (5.4.4) 5 (1.3.3) | 5 (1.4.5) 8 (1.2.1) 10(1.5.5) 15(1.6.5) 15(1.6.5) 10(2.2.4) 15(2.1.1) 20 (2.3.4) 20 (3.1.1) 20 (3.1.1) 30 (3.3.2) 10(4.3.4) 20 (4.4.4) 20 (4.4.4) 26 (4.2.1) 10(5.2.2) 10(5.3.4) 20 (5.4.4) 20 (5.4.4) Исходные данные | "Глубина" Поиск опт. решения Ограничение на целевую Функцию Л=[ээ— 1 Пересчитать Отчет: Итерация 3 Критерий 2: 3.3.2 4 итерация: f=85 Итерация 4 Целевая Ф-ция: 1.2.1 1.3.3 1.4.5 1.5.5 2.2.4 3.1.1 4.3.4 4.4.4 5.2.2 5.3.4 расчитегть Рис. 2. Выбор компонентов гарантоспособной системы управления и обработки информации с оптимальной избыточностью 109 Математика, механика, информатика Протокол выбора компонентов программной системы многоатрибутивного выбора компонентов гарантоспособной системы управления и обработки информации представлен на рис. 2 в части окна с заголовком «Отчет». В верхней правой части окна (см. рис. 2) приведено значение надежности формируемой системы управления и обработки информации, которая выступает ограничением при выборе компонентов. Таким образом, в данной статье выполнена формализация постановки задачи формирования оптимальной структуры системы управления и обработки информации. Согласно данной формализации, при развитии системы управления и обработки информации обеспечивается повышение уровня ее надежности за счет резервирования элементов отдельных подсистем при условии, что ресурсы использованы не полностью. В результате теоретических исследований, проведенных при тестировании программного комплекса, подтверждена высокая эффективность мультиверси-онной методологии при разработке гарантоспособных систем управления и обработки информации и целесообразность ее применения в таких критичных областях, как космические системы, распределенные вычисления, а также управление и обработка информации. Результаты работы позволят решать задачи по формированию и развитию структуры систем управления и обработки информации, обеспечивающей гарантоспособность функционирования систем данного класса.

About the authors

R. Yu. Tsarev

Email: rahatamatahata@mail.ru

D. V. Kapulin

Email: kapulin@gmail.com

D. V. Mashurova

Email: mashurova@bk.ru

Ya. A. Tynchenko

Email: JaTynchenko@mesi.ru

D. N. Kovtanyuk

References

Supplementary files