Optimization problems solution for queuing systems with failure under uncertainty

The mathematical models of the functioning quality of computer networks that can be represented in the form of queuing networks with failures are described. The problems of optimizing the functioning quality of such networks under given constraints on the maximum bandwidth of communication channels...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2025
Hauptverfasser:	Kopytchuk, M.B., Tishin, P.M., Botnar, K.V.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	PROBLEMS IN PROGRAMMING 2025
Schlagworte:	UDC 519.711
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/832
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming
Завантажити файл:

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-832
record_format	ojs
resource_txt_mv	ppisoftskievua/76/69882ef6edc4bad7b84cafb748906a76.pdf
spelling	pp_isofts_kiev_ua-article-8322025-09-02T15:42:07Z Optimization problems solution for queuing systems with failure under uncertainty Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности Вирішення оптимізаційних задач для систем масового обслуговування з відмовами в умовах невизначеності Kopytchuk, M.B. Tishin, P.M. Botnar, K.V. UDC 519.711 УДК 519.711 УДК 519.711 The mathematical models of the functioning quality of computer networks that can be represented in the form of queuing networks with failures are described. The problems of optimizing the functioning quality of such networks under given constraints on the maximum bandwidth of communication channels and allocated to upgrade the network resources are defined. Algorithms that allow solving optimization problems within the specified limits are built.Prombles in programming 2011; 4: 108-117 Построены математические модели расчета показателей качества функционирования вычислительных сетей, которые можно представить в виде сетей массового обслуживания с отказами. Сформулированы задачи оптимизации показателей качества функционирования таких сетей при заданных ограничениях на максимальную пропускную способность каналов связи и на выделяемые для модернизации сети ресурсы. Построены алгоритмы, которые позволяют решать поставленные оптимизационные задачи в рамках оговоренных ограничений.Prombles in programming 2011; 4: 108-117 Побудовані математичні моделі розрахунку показників якості функціонування обчислювальних мереж, які можна представити у вигляді мереж масового обслуговування з відмовами. Сформульовано задачі оптимізації показників якості функціонування таких мереж при заданих обмеженнях на максимальну пропускну здатність каналів зв'язку та на ресурси, які виділяються для модернізації мережі. Побудовано алгоритми, які дозволяють вирішувати поставлені оптимізаційні задачі в рамках обумовлених обмежень.Prombles in programming 2011; 4: 108-117 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-09-02 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/832 PROBLEMS IN PROGRAMMING; No 4 (2011); 108-117 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2011); 108-117 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2011); 108-117 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/832/883 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2025-09-02T15:42:07Z
collection	OJS
language	Russian
topic	UDC 519.711
spellingShingle	UDC 519.711 Kopytchuk, M.B. Tishin, P.M. Botnar, K.V. Optimization problems solution for queuing systems with failure under uncertainty
topic_facet	UDC 519.711 УДК 519.711 УДК 519.711
format	Article
author	Kopytchuk, M.B. Tishin, P.M. Botnar, K.V.
author_facet	Kopytchuk, M.B. Tishin, P.M. Botnar, K.V.
author_sort	Kopytchuk, M.B.
title	Optimization problems solution for queuing systems with failure under uncertainty
title_short	Optimization problems solution for queuing systems with failure under uncertainty
title_full	Optimization problems solution for queuing systems with failure under uncertainty
title_fullStr	Optimization problems solution for queuing systems with failure under uncertainty
title_full_unstemmed	Optimization problems solution for queuing systems with failure under uncertainty
title_sort	optimization problems solution for queuing systems with failure under uncertainty
title_alt	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности Вирішення оптимізаційних задач для систем масового обслуговування з відмовами в умовах невизначеності
description	The mathematical models of the functioning quality of computer networks that can be represented in the form of queuing networks with failures are described. The problems of optimizing the functioning quality of such networks under given constraints on the maximum bandwidth of communication channels and allocated to upgrade the network resources are defined. Algorithms that allow solving optimization problems within the specified limits are built.Prombles in programming 2011; 4: 108-117
publisher	PROBLEMS IN PROGRAMMING
publishDate	2025
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/832
work_keys_str_mv	AT kopytchukmb optimizationproblemssolutionforqueuingsystemswithfailureunderuncertainty AT tishinpm optimizationproblemssolutionforqueuingsystemswithfailureunderuncertainty AT botnarkv optimizationproblemssolutionforqueuingsystemswithfailureunderuncertainty AT kopytchukmb rešenieoptimizacionnyhzadačdlâsistemmassovogoobsluživannâsotkazamivusloviâhneopredelennosti AT tishinpm rešenieoptimizacionnyhzadačdlâsistemmassovogoobsluživannâsotkazamivusloviâhneopredelennosti AT botnarkv rešenieoptimizacionnyhzadačdlâsistemmassovogoobsluživannâsotkazamivusloviâhneopredelennosti AT kopytchukmb viríšennâoptimízacíjnihzadačdlâsistemmasovogoobslugovuvannâzvídmovamivumovahneviznačeností AT tishinpm viríšennâoptimízacíjnihzadačdlâsistemmasovogoobslugovuvannâzvídmovamivumovahneviznačeností AT botnarkv viríšennâoptimízacíjnihzadačdlâsistemmasovogoobslugovuvannâzvídmovamivumovahneviznačeností
first_indexed	2025-09-17T09:24:51Z
last_indexed	2025-09-17T09:24:51Z
_version_	1850410161952260096
fulltext	Прикладне програмне забезпечення 108 УДК 519.711 Н.Б. Копытчук, П.М. Тишин, К.В. Ботнарь РЕШЕНИЕ ОПТИМИЗАЦИОННЫХ ЗАДАЧ ДЛЯ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ С ОТКАЗАМИ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ Построены математические модели расчета показателей качества функционирования вычислительных сетей, которые можно представить в виде сетей массового обслуживания с отказами. Сформулированы задачи оптимизации показателей качества функционирования таких сетей при заданных ограничениях на максимальную пропускную способность каналов связи и на выделяемые для модернизации сети ре- сурсы. Построены алгоритмы, которые позволяют решать поставленные оптимизационные задачи в рамках оговоренных ограничений. Вступление В работе [1] авторами рассматрива- лись вычислительные сети, в которых за- держка передачи сообщений не была кри- тичным показателем качества функциони- рования. Однако данное утверждение не всегда справедливо и имеет смысл рас- смотреть задачу, когда в сеть поступают сообщения, которые не допускают задерж- ки. Это характерно для передачи данных в режиме реального времени. Так как пропу- скные способности каналов ограничены, а задержки передачи сообщений недопусти- мы, то в такой системе будут иметь место отказы обслуживания поступающих зая- вок. В работе [2] рассмотрена подобная задача, однако она рассматривалась в ус- ловиях полной определенности исходных данных. Но, следует заметить, что чет- кость и определенность исходных данных не всегда возможна. В данной работе рас- сматриваются оптимизационные задачи для сетей, которые можно описать моде- лями систем с отказами, и параметры ко- торых заданы нечетко. Постановка оптимизационной зада- чи сформулирована аналогично [1], при этом в качестве показателя качества функ- ционирования системы выступает вероят- ность отказа передачи сообщений. Анало- гичная постановка задачи, но без верхнего ограничения на увеличение пропускной способности каналов связи и с четко за- данными параметрами, описана в [2]. В той постановке, в которой задача рассмат- ривается в данной работе, задача не реша- лась. Нечеткие модели расчета вероятностных характеристик для СМО с отказами Модели систем массового назна- чения с отказами. Введем в рассмотрение модель некоторой подсети, которая имеет радиальную структуру. Входящие сообще- ния поступают на некоторые периферий- ные системы обслуживания (ПСО), в каче- стве которых могут выступать, например, терминалы, которые при возможности пе- редают сообщения по соответствующим каналам связи центральному устройству (ЦУ). В качестве ЦУ в самом простом слу- чае могут выступать, например, мультип- лексор или концентратор. ЦУ в свою оче- редь передает сообщения далее в сеть по выходному каналу. На каждое ПСО посту- пает поток заявок интенсивностью njj ..1, =λ , и при этом каждый канал связи (КС) ограничен максимально возможной скоростью передачи данных njC j ..1, = . Выходной канал связи в ЦУ также ограни- чен по скорости передачи данных величи- ной ΣC . Такую систему можно предста- вить, так как показано на рис. 1. Введем соотношение, которое будет определять связь между скоростями пере- дачи данных выходного КС ЦУ и входя- щими каналами: ∑ = Σ = n j jCC 1 . (1) © Н.Б. Копытчук, П.М. Тишин, К.В. Ботнарь, 2011 ISSN 1727-4907. Проблеми програмування. 2011. № 4 Прикладне програмне забезпечення 109 Такое описание системы позволяет сформулировать задачу поиска значений пропускных способностей КС jC , при ко- торых с учетом заданной структуры сети, входящих потоков заявок и выходного ка- нала ЦУ потери сообщений были бы ми- нимальны, т. е. вероятность отказа на пе- риферийных системах была бы минималь- на. Ограничениями для такой оптимизаци- онной задачи может послужить выражение (1). Подобная задача может возникнуть как при проектировании сети, так и при ее мо- дернизации, когда изменение потоков вхо- дящих сообщений ведет к перегрузке КС и соответственно повышению вероятности отказа на ПСО. В случае модернизации системы за- дачу можно сформулировать в терминах затрат ресурсов на увеличение пропускной способности КС с целью минимизации ве- роятности отказа. Тогда в качестве огра- ничений при оптимизации показателя ве- роятности отказа может послужить сумма выделяемых ресурсов. Такое ограничение можно описать следующим образом: 0 1 Sxs n j jj ≤∑ = . (2) Здесь jjj CCx 0−= , (3) где jC – значение скорости передачи дан- ных для j-го КС после модернизации; jC0 – скорость передачи данных в j-м КС до модернизации; js – удельная стоимость увеличения скорости передачи данных для j-го КС. Для расчета показателя вероятности отказа передачи сообщения введем сле- дующие обозначения: ,, 0 jjjjjj Cuflu +=λ= (4) где jl – средняя длина сообщений в j-м КС. Учитывая выражения (3) и (4) веро- ятность отказа передачи сообщения по j-у КС jP можно рассчитать по следующему соотношению [2]: jj j j fx u P + = . (5) Выражение для расчета среднесете- вого значения показателя для рассматри- ваемой подсети из n КС такое: ∑ =Σ + λ λ = n j jj jj C fx u P 1 1 , (6) где Σλ – суммарный поток заявок в рас- сматриваемой подсети. Выражение (6) дает возможность оценить среднесетевую вероятность отказа в рассматриваемой подсети в случае, когда все исходные данные заданы точно. Одна- ко в реальной ситуации часто такие пара- метры, как средняя длина сообщений jl , интенсивность входящего потока jλ и удельная стоимость модернизации сети js не могут быть заданы четко. Для учета нечеткости исходных данных представим их в виде нечетких ве- личин jl~ , jλ ~ , js~ , каждая из которых оп- ределена на своем полном ортогональном семантическом пространстве (ПОСП): ljl Π∈ ~ , sjs Π∈~ , λΠ∈λ j ~ . Далее будем рассматривать ПОСП с функциями при- надлежности в виде трапеций. В соответ- ствии с условиями формирования ПОСП, описанными в [3], функции принадлежно- сти параметров примут вид (7). При этом количество термов в ПОСП определяется на основе степени нечеткости, значение которой задается исходя из конкретной решаемой задачи. ⇒Π∈⇒ pjj pp ~ Рис. 1. СМО с отказами Прикладне програмне забезпечення 110 ,..1 , ,,1 , ,,0 )( 1 1 11 1 1 p kejke keke kej kejkb kbjkb kbkb kbj kejkbj j p k Kk ppp pp pp ppp ppp pp pp pppp p = ⎪ ⎪ ⎪ ⎪ ⎩ ⎪⎪ ⎪ ⎪ ⎨ ⎧ << − − ≤≤ << − − ≥≤ =⇒μ (7) где pK – количество нечетких значений в пространстве pΠ , принимаемых некото- рым параметром р, в виде нечетких чисел с трапецеидальной функцией принадлежно- сти p kμ , которая положительно определена на некотором интервале ),( kekb pp , а ),( 11 kekb pp – интервал, на котором функция принадлежности равна единице. Нечеткое описание исходных дан- ных трапецеидальными функциями при- надлежности приводит к нечеткому виду параметров и значения показателя эффек- тивности функционирования системы. Для расчета нечетких значений параметров в соответствующих ПОСП используем моде- ли, описанные в [3]. Следует отметить, что при расчете нечеткого значения некоторого параметра его рассчитанная функция принадлежности в общем случае не будет совпадать ни с одной из функций принадлежности термов его ПОСП. Для расчета значения парамет- ра в ПОСП введем следующие обозначе- ния: p~ – нечеткое значение параметра р, kp~ – k-ый терм соответствующего ПОСП, p′ – нечеткое значение параметра, полу- ченное в результате расчетов на основе не- четких исходных данных. С учетом трапе- цеидальной формы функций принадлежно- сти поиск соответствующего семантиче- ского значения будем осуществлять по со- отношениям: ),,~(minarg~ ..1 ppfp kdKk p ′= = (8) где ,),~(),~( ),~(),~( 32 1 pppp ppppf kk kkd ′σ+′σ+ +′σ=′ в котором сумма функций ),~( ppks ′σ бе- рется по модулю, так как ),~( ppf kd ′ опи- сывает расстояние между двумя трапецеи- дальными функциями принадлежности – рассчитанной и некоторой функцией при- надлежности в ПОСП. При этом ( ) ;3..1,,,, ,,,,),~( 1111 =′′ ′′Ξ=′σ spppp pppppp bkbeke bkbekesks где ( ) ; ,,,,,,, 11111 bkbeke bkbekebkbeke pppp pppppppp ′−+′−= =′′′′Ξ ( ) ; ,,,,,,, 1111 11112 be bbee kbke kbkbkeke bkbekebkbeke pp pppp pp pppp pppppppp ′−′ ′′−′′ − − − = =′′′′Ξ ( ) . )()()()( ,,,,,,, 2222 3 1111 1111 be be kbke kbke bkbekebkbeke pp pp pp pp pppppppp ′−′ ′−′ − − − = =′′′′Ξ Используя описанные соотношения рассчитаем значения параметров ju и jf . ),~(minarg~~ ..1 jkdKkkj uufuu u ′== = , (9) ),~(minarg~~ ..1 jkdKkkj fffff f ′== = , (10) где ( ) .3..1,,,, ,,,,),~( 111111 =λλ λλΞ=′σ slulu luluuu jbjb k bjeje k e jbjb k bjeje k esjks ( ) .3..1,,,, ,,,,),~( 111111 00 00 =++ ++Ξ=′σ sCufCuf CufCufff jbjb k bjeje k e jbjb k bjeje k esjks Прикладне програмне забезпечення 111 Будем считать, что параметр jx оп- ределяется четко. Тогда значения показа- телей вероятности отказа передачи по j-у КС и среднесетевые значения могут быть рассчитаны по соотношениям: ).,~(minarg~~ ..1 jkdKkkj PPfPP P ′== = (11) Здесь ( ) ,3..1,,,, ,,,,),~( 43 21 11 = Ξ=′σ spPpP pPpPPP kbke kbkesjks где ., ,, 1 1 1 1 43 21 jej jb jbj je jej jb jbj je fx u p fx u p fx u p fx u p + = + = + = + = Выражения для нахождения нечет- кого значения среднесетевой вероятности отказа в доставке сообщения в рассматри- ваемой подсети будут иметь вид: ).,~(minarg~~ ..1 CkdKkkC PPfPP P ′== = (12) Здесь ( ) ,3..1,,,, ,,,,),~( 43 21 11 = Ξ=′ spPpP pPpPPP kbke kbkesCksσ где .1,1 ,1,1 1, 4 1, 3 1, 2 1, 1 11 1 11 1 ∑∑ ∑∑ =Σ=Σ =Σ=Σ λ λ =λ λ = λ λ =λ λ = n j jbjb e n j jeje b n j jbjb e n j jeje b PpPp PpPp Модели систем уникального на- значения с отказами. Вышерассмотрен- ная модель сети описывает систему массо- вого назначения. Это означает, что значе- ния показателей эффективности функцио- нирования рассматриваемой подсети в равной степени зависели от всех элемен- тов. То есть при ухудшении показателей некоторого КС, среднесетевой показатель можно было улучшить за счет улучшения показателей качества по другим каналам связи. Такие модели адекватны, когда в подсети все элементы равноправны. Одна- ко, при наличии КС, от работы которых зависит функционирование всей системы, разработанные модели будут неэффектив- ными. Рассмотрим случай, когда выше- описанная подсеть является уникальной. В этом случае вероятность отказа сети надо измерять не среднесетевым значением, а вероятностью отказа хотя бы в одном КС хотя бы для одного сообщения. В этом случае задача поиска минимума показате- ля вероятности отказа сведется к поиску максимума показателя W, который для не- которого j-го КС определяется следующим соотношением [1]: ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + −= jj j j fx u W 1ln , (13) где параметры jx , ju и jf определяются соотношениями (3) и (4). Среднесетевое значение показателя W будем вычислять по формуле ∑ =Σ λ λ = n j jjWW 1 1 . (14) Определяя параметры показателя W как нечеткие переменные с функциями принадлежности вида (7), можно описать расчет нечеткого значения показателей jW~ и W~ . В этом случае значения переменных ju~ и jf~ определяются из выражений (9) и (10), а для показателя W~ строиться соот- ветствующее ПОСП WΠ . Нечеткое значение jW~ для j-го КС определяется по следующим соотношени- ям: ),~(minarg~~ ..1 jkdKkkj WWfWW W ′== = . (15) Здесь ( ) ,3..1,,,, ,,,,),~( 43 21 11 = Ξ=′ swWwW wWwWWW kbke kbkesjksσ где .1ln,1ln ,1ln,1ln 1 1 1 1 43 21 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + −=⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + −= ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + −=⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + −= jbj je jej jb jbj je jej jb fx u w fx u w fx u w fx u w Прикладне програмне забезпечення 112 Следует отметить, что в силу тео- рем, доказанных в [4], функция принад- лежности нечеткой величины jW~ будет иметь трапецеидальную форму, что позво- ляет нам и дальше оперировать этой вели- чиной, применяя формулы (8). Среднесе- тевой показатель эффективности функ- ционирования подсети будет вычисляться по соотношениям следующего вида: ),~(minarg~~ ..1 WWfWW kdKkk W ′== = . (16) Здесь ( ) ,3..1,,,, ,,,,),~( 43 21 11 = Ξ=′σ swWwW wWwWWW k b k e k b k esks где ,1,1 1 2 1 1 ∑∑ =Σ=Σ == n j jbjb e n j jeje b WwWw λ λ λ λ .1,1 1 4 1 3 11 1 11 1 ∑∑ =Σ=Σ == n j jbjb e n j jeje b WwWw λ λ λ λ Полученная в результате нечеткая величина W~ является показателем степени экспоненты при вычислении вероятности передачи сообщения, т. е. jW j eQ ~~ = , (17) W C eQ ~~ = . (17') Алгоритмы решения оптимизаци- онных задач Алгоритм для систем массового назначения. Рассмотрим задачу, которую формально можно представить в следую- щем виде: min,~ ~~ ~ 1~ 1 ⇒ + = ∑ =Σ n j jj jj С fx u P λ λ ,~ 0 1 Sxs n i ii ≤∑ = (18) .0 ii ax ≤≤ Так как функция, описывающая за- висимость ÑP~ от величины jx является выпуклой и монотонно убывающей, то к решению задачи (18) можно применить алгоритм, аналогичный алгоритму реше- ния задач, описанных в [1]. Для этого вве- дем параметр, по которому будет прово- диться упорядочивание КС в зависимости от необходимости их модернизации отно- сительно заданного показателя качества. 2~ ~~ ~ j jj j f uλ =ν . (19) Как видно из формулы (19) пара- метр jν ~ представляет собой нечеткое тра- пецеидальное число, также как и парамет- ры jλ ~ , ju~ , jf~ . Данный параметр рассчи- тывается отдельно для каждого j-го КС и является параметром, определяющим по- рядок модернизации КС при заданной ве- личине ресурса. Каналы связи модернизи- руются в порядке убывания величины jν ~ . Для построения алгоритма решения задачи (18) построим ПОСП νΠ для пара- метра jν ~ . Определим нечеткое значение jν ~ из νΠ , применив следующие соотно- шения: ),~(minarg~~ ..1 jkdKkkj f ν′ν=ν=ν ν= , (20) где .3..1,,, ,,,,,),~( 22 22 1 11 1 1 11 1 = ⎟ ⎟ ⎠ ⎞λ ν λ ⎜ ⎜ ⎝ ⎛ ν λ ν λ νΞ=ν′νσ s f u f u f u f u je jbjb kb jb jeje ke je jbjb kb jb jeje kesjks Алгоритм решения рассматривае- мой задачи во многом схож с алгоритмами, описанными в [1]. Отличия заключаются только в рассчитываемых величинах, а по- рядок действий остается таким же. Алгоритм 1. 1. Определить нечеткие значения па- раметров ju~ , jf~ , js~ nj ..1= . 2. Задать количество термов и пара- метры трапецеидальных функций принад- лежности каждого терма на ПОСП uΠ , ПОСП fΠ и ПОСП sΠ . 3. Выполнить операции дефаззифи- кации параметров ju~ , jf~ и js~ . Прикладне програмне забезпечення 113 4. Задать количество термов и пара- метры трапецеидальных функций принад- лежности каждого терма на νΠ . 5. Рассчитать параметр jν ~ для каж- дого НС по формуле (20). 6. Выполнить операцию дефаззифи- кации для параметров jν ~ и jf~ . В резуль- тате получаем значения D jν и D jf соответ- ственно. 7. Задать величину a, соответст- вующую minS , и 0=s . 8. Задать 1=j . 9. Рассчитать величину ( )1−ν⋅= D j D jj afz . 10. Если 0≤jz , то перейти к пункту 11, иначе перейти к пункту 12. 11. Присвоить переменной jx значе- ние нуль, где jx – приращение к скорости передачи данных по j-у КС и перейти к пункту 14. 12. Если выполняется неравенство 2 /1 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + ≥ν a fa D jjD j , то присвоить jx значение ja и перейти к пункту 14, иначе перейти к пункту 13. 13. Присвоить переменной jx значе- ние jz , где jx – приращение к пропускной способности j-го КС. 14. 1+= jj . 15. Если nj > , то параметр jx рас- считан для всех КС, переходим к пункту 15, иначе к пункту 10. 16. Расчет трапецеидального нечетко- го числа ),,( 1,342 ppppPC =′ . 17. 1+= ss . Задать a, соответствую- щее sS +min . 18. Если maxaa > , где maxa соответ- ствует maxS , то перейти к пункту 19, иначе к пункту 8. 19. Конец. Полученный набор величин CP′ отображает изменение вероятности отказа передачи сообщения в подсети при увели- чении выделяемых ресурсов на модерни- зацию КС. В алгоритме 1 на шаге 3–6 делается переход к четким значениям параметров подсети, что дает возможность рассчитать четкое решение n jjx 1)( = . При этом величи- на jx характеризует приращение к скоро- сти передачи данных по j-у КС. Алгоритм для систем уникально- го назначения. Когда рассматриваемая подсистема является уникальной, т. е. от ее функционирования зависит функциони- рование всей сети, то рассмотренные ранее модели оказываются неэффективными для расчета сетевых показателей качества. Вы- ражения (13–17) дают возможность опи- сать процесс расчета оптимальных показа- телей и для систем уникального назначе- ния (СУН). Причем, алгоритм расчета оп- тимальных показателей будет схожим с уже описанным алгоритмом для систем массового назначения (СМН). Формально постановку задачи по- иска оптимального значения показателя качества при ограничениях на развитие КС и нечетких исходных данных можно запи- сать в следующем виде: max,~ ~ 1ln~ ~ 1~ 1 ⇒⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ + −= ∑ =Σ n j jj j j fx u W λ λ ,~ 0 1 Sxs n i ii ≤∑ = (21) .0 ii ax ≤≤ Показатель W~ необходимо макси- мизировать, так как он является показате- лем степени экспоненты при расчете веро- ятности передачи сообщения, что показано в соотношениях (17). Для решения задачи (21) введем па- раметр jϕ , который будет характеризовать степень необходимости модернизации КС с учетом оптимизации показателя W~ : jjj jj j Cfs u 0 λ =ϕ . Прикладне програмне забезпечення 114 Как и ранее, большее значение па- раметра jϕ~ означает большую степень не- обходимости модернизации j-го КС. Так как исходные параметры заданы в виде нечетких трапецеидальных чисел, то и в результате получиться трапецеидальное нечеткое число из ПОСП ϕΠ . Для опреде- ления нечеткого значения jϕ~ применим следующие соотношения: ),~(minarg~~ ..1 jkdKkkj f ϕ′ϕ=ϕ=ϕ ν= , (22) где .3..1,,,, ,,,,),~( 00 00 11 11 1 11 11 1 =⎟ ⎟ ⎠ ⎞λ ϕ λ ϕ ⎜ ⎜ ⎝ ⎛ λ ϕ λ ϕΞ=ϕ′ϕσ s Cfs u Cfs u Cfs u Cfs u jjeje jbjb kb jjbjb jeje ke jjeje jbjb kb jjbjb jeje kesjks Алгоритм решения задачи (21) с учетом описанного в (22) параметра jϕ~ может быть представлен в следующем ви- де: Алгоритм 2. 1. Определить нечеткие значения па- раметров ju~ , jf~ , js~ nj ..1= . 2. Задать количество термов и пара- метры трапецеидальных функций принад- лежности каждого терма на ПОСП uΠ , ПОСП fΠ и ПОСП sΠ . 3. Выполнить операции дефаззифика- ции параметров ju~ , jf~ и js~ . 4. Задать количество термов и пара- метры трапецеидальных функций принад- лежности каждого терма на ϕΠ . 5. Рассчитать параметр jϕ~ для каждо- го КС по формуле (22). 6. Построить ϕΠ и выполнить опера- цию дефаззификации для параметра jϕ~ . 7. Задать a, соответствующее minS и 0=s . 8. Задать 1=j . 9. Рассчитать величину ( )11 2 221 −ϕ+−= afffz D jjjjj , где 2 0 1 D jj j fC f + = , 2 1 0 2 j D jj j f fC f = . 10. Если 0≤jz , то перейти к пункту 11, иначе перейти к пункту 12. 11. Присвоить переменной jx значе- ние нуль, где jx – приращение к скорости передачи данных по j-у КС и перейти к пункту 14. 12. Если выполняется неравенство 2 0 0 aCf Cfa j D j j D jjD j + ≥ϕ , то присвоить jx значение ja и перейти к пункту 14, иначе перейти к пункту 13. 13. Присвоить переменной jx значе- ние jz , где jx – приращение к пропускной способности j-го КС. 14. 1+= jj . 15. Если nj > , то параметр jx рас- считан для всех КС, переходим к пункту 15, иначе к пункту 10. 16. Расчет трапецеидального нечетко- го числа ),,( 1,342 wwwwW =′ . 17. 1+= ss . Задать a, соответствую- щее sS +min . 18. Если maxaa > где maxa соответст- вует maxS , то перейти к пункту 19, иначе к пункту 8. 19. Конец. Подставляя полученный в описан- ном алгоритме набор величин W ′ в соот- ношения (17), можно рассчитать набор значений вероятности передачи сообщения jQ′ по j-у КС и по всей сети CQ′ . Для опре- деления соответствующих нечетких значе- ний на ПОСП QΠ . Прикладне програмне забезпечення 115 ),~(minarg~~ ..1 jkdKkkj QQfQQ Q ′== = , (23) ),~(minarg~~ ..1 CkdKkkC QQfQQ Q ′== = , (24) где ,3..1,,,, ,,,,),~( 1 1 1 1 ~~ ~~ =⎟⎟ ⎠ ⎞ ⎟ ⎠ ⎞⎜ ⎝ ⎛⎟ ⎠ ⎞⎜ ⎝ ⎛ ⎜ ⎝ ⎛ ⎟ ⎠ ⎞⎜ ⎝ ⎛⎟ ⎠ ⎞⎜ ⎝ ⎛Ξ=′σ seQeQ eQeQQQ b Wk b e Wk e b Wk b e Wk esjks jj jj ( ) ( )( ( ) ( ) ) .3..1,,,, ,,,,),~( 1111 ~~ ~~ = Ξ=′σ seQeQ eQeQQQ b Wk be Wk e b Wk be Wk esCks Результаты моделирования Для оценки точности алгоритмов 1 и 2 были построены имитационные моде- ли. Исходные данные при моделировании определялись следующим множеством па- раметров: − count – количество экспериментов; − n – количество каналов; − dlj – средняя длина сообщений в j-м КС; − rj – скорость j-го КС; − aj – максимально возможная скорость j-го КС; − jλ – интенсивность нагрузки j-го КС; − sj – удельная стоимость повышения пропускной способности j-го КС; − S0 – сумма, выделенная на модерни- зацию подсети; − mfN – количество термов на ПОСП соответствующего параметра; − angle – доля проекции ребра трапе- ции на носитель соответствующего терма. Функции принадлежностей нечет- ких параметров задавались в виде равно- бедренных трапеций. При проведении имитационного моделирования для одних и тех же исходных данных выполнялись расчеты по алгоритмам четких моделей, оптимизирующих показатели функциони- рования подсети, взятые из [1], и расчеты по алгоритмам 1 и 2. Итогом моделирова- ния является оценка ошибки расчета пока- зателей с помощью разработанных алго- ритмов относительно значений, получен- ных в четком случае вычислений. Далее приведены результаты про- веденного моделирования для вероятности отказа доставки сообщения в сети. При этом параметры определены следующим образом: − count = 50 экспериментов; − n = 200 каналов; − dlj – с лучайная величина до 1024 бит; − rj – случайная величина, принимае- мая значения из множества {64, 128, 256, 512} Кбит/с; − aj = 1 Мбит/с.; − angle = 0,3; − S0 – изменяется в пределах от 1 до 200 у.е.; − jλ – выбиралось случайно для каж- дого j-го КС при максимально допустимом значении 50 сообщений в секунду; − sj – выбиралась случайно для каждо- го j-го КС при максимально допустимом значении 10 условных единиц. Чтобы показать, что нечеткая мо- дель соответствует четкой модели, необ- ходимо, чтобы при уменьшении степени нечеткости ПОСП показателей уменьша- лась относительная ошибка расчета. Оче- видно, что степень нечеткости ПОСП бу- дет обратно пропорциональна количеству заданных на нем термов. Поэтому было проведено моделирование при вышеопи- санных значениях параметров для различ- ного количества термов на семантических пространствах нечетких переменных. На рис. 2–4 показаны графики изменения от- носительной ошибки расчета вероятности отказа доставки сообщения в рассматри- ваемой подсети (ось ординат) при увели- чении выделяемых на модернизацию ре- сурсов (ось абсцисс) для значений пара- метра mfN 10, 50 и 100 соответственно. Аналогичные эксперименты были проведены для СУН с отказами. Результаты моделирования показаны на рис. 5–7. Прикладне програмне забезпечення 116 Рис. 6. Ошибка расчета показателя PC, при mfN =50 для СУН Рис. 5. Ошибка расчета показателя PC, при mfN =10 для СУН Рис. 3. Ошибка расчета показателя PC, при mfN =50 для СМН Рис. 2. Ошибка расчета показателя PC, при mfN =10 для СМН Рис. 4. Ошибка расчета показателя PC, при mfN =100 для СМН Рис. 7. Ошибка расчета показателя PC, при mfN =100 для СУН Прикладне програмне забезпечення 117 Из вышеприведенных графиков видно, что наибольшая ошибка расчета показателей находиться в области низких значений параметра 0S , при этом четко прослеживается уменьшение ошибки при увеличении количества термов на семантических пространствах нечетких параметров. Это дает право утверждать, что построенная нечеткая модель соответствует четкой модели, и может применяться в случаях, когда некоторые параметры расчета показателей функционирования подсети заданы в нечетком виде. Выводы В работе описаны нечеткие модели расчета вероятности отказа доставке со- общения в некоторой вычислительной се- ти, которую можно представить в виде се- ти массового обслуживания с отказами. Приведенные модели позволяют перейти от четкой задачи оптимизации показателей качества функционирования при измене- нии параметров каналов связи к нечеткой оптимизационной задаче, а построенные алгоритмы позволили реализовать описан- ные нечеткие модели. 1. Тишин П.М., Ботнарь К.В. Сравнение ха- рактеристик двух моделей описания разви- тия направлений связи // Наукові записки УНДІЗ. – Киев: УНИИС, 2009. – C. 77–88. 2. Дымарский Я.С. Задачи и методы оптимизации сетей связи: Учебное пособие // СПб. –ГУТ. СПб, 2005. – С. 207. 3. Тишин П.М., Ботнарь К.В. Нечеткие моде- ли сетей связи // Холодильная техника и технология. – Одесса: ОГАХ, 2009.– №8.– С. 60–67. 4. Ботнарь К.В. Методы и модели описания характеристик телекоммуникационной сети в условиях неопределенности : дис. ... канд. техн. наук // Киев, Государственный уни- верситет информационно-коммуникаци- онных технологий, 2010. – С. 184. Получено 13.05.2011 Об авторах: Копытчук Николай Борисович, доктор технических наук, профессор, проректор по научной и научно- педагогической работе, Тишин Петр Метталинович, кандидат физико-математических наук, доцент кафедры компьютерных интеллек- туальных систем и сетей, Ботнарь Константин Васильевич, кандидат технических наук. Место работы авторов: Одесский национальный политехнический университет. 65044, проспект Шевченко, 1, г. Одесса, Украина. Тел.: +38(095)302 0265. e-mail: botnar_k@bk.ru

Optimization problems solution for queuing systems with failure under uncertainty

Institution

Ähnliche Einträge