ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.10.2024
Просмотров: 146
Скачиваний: 0
3.Переход от произвольных распределений
кмарковским законам
Под марковским законом понимаем закон распределения случайной величины, представляющей собой сумму детерминиро ванного или случайного числа слагаемых (этапов обслуживания), каждое из которых подчиняется экспоненциальному закону. Мар ковский закон представляет -собой линейную комбинацию сверток экспоненциальных законов. Наиболее известным примером мар ковского закона является распределение Эрланга, представляю щее собой свертку заданного числа одинаковых экспоненциальных законов.
Построим модифицированный марковский процесс в случае, когда функции А (х) и В (х) представляют собой распределения Эрланга. Пусть расстояние между двумя последующими вызова ми состоит из /е этапов, каждый из которых подчиняется экспонен циальному закону с параметром а, т. е.
(1А (х) = ^ - i ) i е_°Аdx’ х > 0 -
Пусть длительность разговора состоит из / этапов, каждый из ко торых подчиняется экспоненциальному закону с параметром Ь:
dB (*) = -Jn = T jr е~Ь* dx> х > 0 -
При построении модифицированного марковского процесса введем дополнительные события, соответствующие переходам между эта пами. Для моделирования о-линейной полнодоступной системы с потерями введем вектор {хо, ..., хр . . % ; } , где Xj — число разго
воров, |
обслуживаемых -в /-м этапе, |
Хо — число свободных |
линий; |
XXj = v. Для моделирования потока вызовов введем число у, |
|
|
i=o |
|
которое будет меняться скачками по единице от k до 1 циклически. Переходу из состояния 1 в состояние к будет соответствовать мо мент поступления вызова. Следовательно, состояние системы ха рактеризуется (Л-й)-мерным (векторам {у, х0, . . xi}.
Кратко рассмотрим алгоритм моделирования. В состоянии {у,
.... xij неслучайное время пребывания равно [a + (v —x0)b]~\ после
чего с -вероятностью --------------- |
происходит переход к новой фа- |
a+(v—xо) ъ |
|
зе в потоке вызовов (вычитание 1 из у), а с дополнительной веро ятностью происходит переход к новой фазе в одной из v—Хо заня тых линий (равновероятно). Если -выбрана одна из линий с i эта пами (i> 0 ), то из Xi вычитается -единица, а хг-_1 увеличивается на единицу. Подобным образом можно построить модифицированный марковский процесс для любых марковских законов А (х) и В (х ) для любых систем массового обслуживания. Общая запись мар ковского закона дана Коксом 1[181]. Преобразование Лапласа об щего марковского закона f(t) по Коксу имеет вид
147
/* (s) = 1 e |
' f{t)dt |
= p0 + |
y q 0qi ■ ■ •+■пS + а/ |
|
|
|
|
|
;=l |
/=i |
|
где параметры удовлетворяют |
условиям |
a j> 0 , Os |
q}=■ |
||
= 1—pj, j-= 1, . . |
k и |
имеют следующий |
смысл: а,- — интенсив- |
||
ность экспоненциального закона, определяющего длительность t'-ro этапа; — вероятность окончания обслуживания после £-го этапа; qi — вероятность перехода к следующему (7 + 1 )-му этапу.
Любое эмпирическое распределение можно сколько угодно точно аппроксимировать марковским законом {101]. Следует только заметить, что выбор такого закона представляет собой непростую задачу численного анализа, особенно из-за того, что даже не большие изменения исходных данных резко меняют показатели экспонент, входящих в марковский закон, и их число (см. § 4.2.4).
Задачу построения марковских законов облегчает то обстоя тельство, что, грубо говоря, характеристики системы обслуживания мало меняются при небольших изменениях исходных законов. Хорошо известен факт независимости вероятности потерь (форму лы Эрланга) от вида закона обслуживания в 1пол1нодоетупной сис теме с потерями при обслуживании простейшего потока [126]. Такой же результат установлен для задачи «станки и рабочие» [121]. Это система с ожиданием, в которой поломка станков происходит по экспоненциальному закону, длительность обслуживания — по про извольному закону; вероятность состояний зависит только от сред-
л __^ |
q |
0 |
ней длительности времени обслуживания. Од |
|
|
|
|
нако такая инвариантность наблюдается толь |
|
|
|
|
ко в исключительных случаях. Например, уже |
|
Л—» |
|
О |
в простейшем случае иеполнедоступной схе- |
|
Рис. 7.6. |
Трехли- |
мы. изображенной на рис. 7.6, она нарушается |
||
нейная |
неполнодо |
[18], что показано сравнением вероятности по |
||
ступная схема |
терь в двух случаях: в первом случае время |
|||
|
|
|
обслуживания |
подчиняется экспоненциально |
му закону с параметром, равным 1, |
а во втором случае состоит из |
|||
двух экспоненциально распределенных этапов, каждый со средней длительностью 4/2. В обоих случаях поступают два паусоонов'ских потока интенсивности К. Вероятности потерь для этих двух случаев различные, а именно:
2А2 (1 |
+ 2Х) |
|
|
Р1 = 2 + Тк + |
8А2 + 4А,3 |
|
|
___________64А2 + 134А3 + |
108?у4 + |
16А5 |
|
Р2 = |
272Х + 433А2 + |
352А3 + |
132А.4 + 16А6 |
64 + |
|||
Выражения р i и р2 не совпадают. Например, при A = l , pi = 0,286, р2= 0,254, т. е. уменьшение дисперсии длительности занятия умень шает вероятность потерь. Доказательство общей теоремы об усло виях инвариантности и формулировка дальнейших задач содержит ся в [10, 11].
В последнее время появляются результаты, содержащие оцен ки того, как меняются характеристики системы обслуживания при
.148
изменении исходных данных. Например, в |[160] получены двусто ронние неравенства для системы G//G/1, на основе чего можно выбирать марковские законы, аппроксимирующие исходные теоре тические предположения или числовые данные.
4. О других алгоритмах, уменьшающих дисперсию оценок
Настоящий параграф посвящен поиску алгоритмов моделиро вания коммутационных систем, которые за фиксированное машин ное время дают минимальную дисперсию оценок. Этому содейст вует переход от моделирования произвольных распределений А(х) и В (х ) к экспоненциальным (см. §§ 7.3.1 и 7.3.3), а потом от экс поненциально распределенных длительностей к их средним зна чениям. Несколько методов еще будет рассмотрено в гл. 9 и 10: использование линейной регрессии для учета разброса оценок ин тенсивности (моделируемого потока, проведение расчетов по фор мулам, куда входят оценки условных вероятностей потерь, полу чаемые моделированием, и др.
Остановимся иа методе использования отрицательно коррели рованных случайных чисел, предложенном для нужд метода Мон те-Карло Хаммерслеем и Мортоном [217] и примененного в зада чах теории массового обслуживания, в частности, Пейджем [274]. Суть метода в следующем. Пусть получена исходная серия равно мерно распределенных случайных чисел [ц, £2, . . . По этой серии
строим вторую |
серию таких чисел r]i= l—£1, 142= 1—£2, ••• • Спер |
ва моделируем |
систему на основе чисел {£*}, а потом — на основе |
чисел {r]i}. Числа тр попарно имеют отрицательную корреля цию, что уменьшает разброс данных. Действительно, если на ос нове чисел {^} получена завышенная оценка вероятности потерь, то на основе серии {г|,} получится заниженная оценка, так как по дынтервалы на [0, 1], означающие в первой серии занятие линий,, во второй серии более вероятно будут означать освобождение ли ний и наоборот. При усреднении обоих оценок среднее значение искомой статистики сохранится, а ее дисперсия уменьшится.
Другую модификацию этого метода предлагает Поляк [117]. Он пользуется последовательностью тщ Ъ> Рг •••При этом, в отли чие метода Пейджа, зависимость вносится не между двумя после дующими реализациями, а внутри каждой отдельной реализации. В частных случаях Поляк показывает, что это дает уменьшение дисперсии на одну треть. ■
Методы уменьшения дисперсии в задачах массового обслужива ния рассматривали также Кларк [177], Эренфельд и Бен-Тувия [193]. В статье Моя [264] рассмотрены четыре метода: 1) примене
ние регрессивного анализа 1(в § 10.1.3); |
2) |
(применение отрицатель |
но коррелированных случайных чисел; |
3) |
моделирование случай |
ных событий по подпространствам с последующим вычислением поформулам (подобным подходом в данной книге является примене ние формулы БЛБ в гл. 9); 4) замена одной случайной величины другой е тем же средним значением, но меньшей дисперсией.
Г л а в а |
8 |
Алгоритмы моделирования систем коммутации
Внастоящей главе изложены алгоритмы мо делирования коммутационных схем, взятых из инженерной практики: однокаскадных п
двухкаскадных неполнодоступных схем, шестикаскадной схемы. Особое внимание обращается на компактную запись структуры и состояний схемы и составление экономичного алгоритма поиска свободных соединительных линий. Эти соображения важны как при моделировании схем на ЭВМ, так и при управлении коммута ционной системы в случае программно управляемой АТС.
8.1. НЕПОЛНОДОСТУПНАЯ СХЕМА
Пусть требуется моделировать неполнодоступную схему, имеющую параметры: v — число линий; п — число групп контак тов (абонентов); d — число доступных линий в каждой группе контактов. Пример НС приведен на рис. 8.1а. Для записи состоя-
|
|
|
|
|
|
|
|
Рис. 8.1. Неполиодоступ- |
|
|
|
S) |
|
|
|
|
|
ная схема с параметра |
|
а) |
1 |
/ |
0 1 а 1 1 |
ми п = 3, d = 4, t> = 6 (за |
|||||
|
|
|
|
|
|
|
|
нятые линии |
1 и 5 на |
|
|
0 |
1 |
0 |
1 |
1 |
1 |
рис. обозначены черными |
|
|
|
0 |
0 |
1 |
1 |
1 |
1 |
кружочками) (a); Pi, R2, |
|
|
|
0 |
! |
1 |
I |
0 |
1 |
Яз — указатели |
структу |
|
|
|
|
|
|
|
|
ры НС (Я — указатель |
|
|
|
|
|
|
|
|
|
занятых линий) (б) |
|
ния линий, доступных t'-й группе контактов, |
отводится строка Ri |
||||||||
с v разрядами. |
Если /-я линия |
(7 = 1 , |
... , v) |
доступна £-й группе |
|||||
( t=l , |
..., /г), то |
значение /-го слева |
разряда |
в строке Ri |
равно 1, |
||||
в противоположном случае равно 0. Для записи всей системы тре буется nv разрядов. Состояние системы характеризует указатель занятых линий R e v разрядами. Бели /-я линия свободна, то зна чение /-го разряда строки R равно 1, в противоположном случае— 0. Для нахождения свободных линий, доступных г-й группе, стро ка Ri логически умножается на строку R. Это дает возможность получить информацию одновременно о всех линиях, доступных i-й группе (см. пример на рис. 8.16). Кроме того, есть список заня-
1'50