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

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

Full description

Saved in:

Bibliographic Details
Date:	2011
Main Authors:	Копытчук, Н.Б., Тишин, П.М., Ботнарь, К.В.
Format:	Article
Language:	Russian
Published:	Інститут програмних систем НАН України 2011
Subjects:	Прикладне програмне забезпечення
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/51005
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности / Н.Б. Копытчук, П.М. Тишин, К.В. Ботнарь // Пробл. програмув. — 2011. — № 4. — С. 108-117. — Бібліогр.: 4 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859471018002743296
author	Копытчук, Н.Б. Тишин, П.М. Ботнарь, К.В.
author_facet	Копытчук, Н.Б. Тишин, П.М. Ботнарь, К.В.
citation_txt	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности / Н.Б. Копытчук, П.М. Тишин, К.В. Ботнарь // Пробл. програмув. — 2011. — № 4. — С. 108-117. — Бібліогр.: 4 назв. — рос.
collection	DSpace DC
description	Построены математические модели расчета показателей качества функционирования вычислительных сетей, которые можно представить в виде сетей массового обслуживания с отказами. Сформулированы задачи оптимизации показателей качества функционирования таких сетей при заданных ограничениях на максимальную пропускную способность каналов связи и на выделяемые для модернизации сети ресурсы. Построены алгоритмы, которые позволяют решать поставленные оптимизационные задачи в рамках оговоренных ограничений.
first_indexed	2025-11-24T09:46:57Z
format	Article
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
id	nasplib_isofts_kiev_ua-123456789-51005
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1727-4907
language	Russian
last_indexed	2025-11-24T09:46:57Z
publishDate	2011
publisher	Інститут програмних систем НАН України
record_format	dspace
spelling	Копытчук, Н.Б. Тишин, П.М. Ботнарь, К.В. 2013-11-08T14:48:45Z 2013-11-08T14:48:45Z 2011 Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности / Н.Б. Копытчук, П.М. Тишин, К.В. Ботнарь // Пробл. програмув. — 2011. — № 4. — С. 108-117. — Бібліогр.: 4 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/51005 519.711 Построены математические модели расчета показателей качества функционирования вычислительных сетей, которые можно представить в виде сетей массового обслуживания с отказами. Сформулированы задачи оптимизации показателей качества функционирования таких сетей при заданных ограничениях на максимальную пропускную способность каналов связи и на выделяемые для модернизации сети ресурсы. Построены алгоритмы, которые позволяют решать поставленные оптимизационные задачи в рамках оговоренных ограничений. ru Інститут програмних систем НАН України Прикладне програмне забезпечення Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности Article published earlier
spellingShingle	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности Копытчук, Н.Б. Тишин, П.М. Ботнарь, К.В. Прикладне програмне забезпечення
title	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности
title_full	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности
title_fullStr	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности
title_full_unstemmed	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности
title_short	Решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности
title_sort	решение оптимизационных задач для систем массового обслуживання с отказами в условиях неопределенности
topic	Прикладне програмне забезпечення
topic_facet	Прикладне програмне забезпечення
url	https://nasplib.isofts.kiev.ua/handle/123456789/51005
work_keys_str_mv	AT kopytčuknb rešenieoptimizacionnyhzadačdlâsistemmassovogoobsluživannâsotkazamivusloviâhneopredelennosti AT tišinpm rešenieoptimizacionnyhzadačdlâsistemmassovogoobsluživannâsotkazamivusloviâhneopredelennosti AT botnarʹkv rešenieoptimizacionnyhzadačdlâsistemmassovogoobsluživannâsotkazamivusloviâhneopredelennosti

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

Institution

Similar Items