Файл: Шнепс, М. А. Численные методы теории телетрафика.pdf

Основы статистического моделирования систем коммутации

7.1. О РАЗВИТИИ МЕТОДА СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ

1. Основная идея метода

Пусть следует определить неизвестное зна­ чение а. В методе статистического модели­ рования моделируют такую случайную ве­

личину что ее математическое ожидание М| равно интересующей нас величине а; оценивают как среднее арифметическое N реа­ лизаций случайной величины £. Центральная предельная теорема при весьма широких предположениях относительно £ гарантирует асимптотическую нормальность распределения среднего арифмети-

Погрешность оценки aN не превосходит с заданной вероятностью величины t j/ ^ I , где D% — дисперсия случайной величины £, а

t — константа, определяемая вероятностью ошибки (уровнем до­ стоверности оценки). Иными словами, в методе статистического мо­ делирования моделируют нормально распределенную случайную величину, и задача заключается в вычислении параметров нор­ мального распределения. Важно заметить, что ошибка метода про­ порциональна N~4t.

Хотя порядок убывания погрешности, равный представ­ ляется недостаточно высоким для точных вычислений, имеются раз­ личные приемы преобразования случайных величин, которые уменьшают дисперсию, не меняя их среднее значение. Это так на­ зываемые приемы уменьшения дисперсии. Правда, при этом иногда усложняется вычислительная процедура.

Введем несколько определений. Эффективность оценки, получае­ мой в методе статистического моделирования, определяется в пер­ вую очередь ее дисперсией. Чем меньше дисперсия при заданном числе испытаний, тем, вообще говоря, эффективнее оценка. При этом следует учитывать также время счета. С учетом его в качест­ ве определения эффективности оценки можно использовать величи­ ну, обратно пропорциональную произведению дисперсии и трудоем­ кости оценки.

133

л л

Оценка а называется несмещенной оценкой, если M aN = M^ и

Пусть два числа А и В (возможные значения оценки а) такие,

что

Р \Л < а < б} а, 0 < а < 1 ,

л

тогда (А, В ) называется доверительным интервалом для а, соответ­ ствующим дотер ительнтгу уровню а, или 100 снпроцентньгм довврнтельным интервалом.

2. От машин искусственного телетрафика до ЭВМ

Метод статистического моделирования в теории телетрафика применялся еще до того, как были созданы универсальные вычис­ лительные машины. Для этой цели использовались специальные машины искусственного телетрафика (МИТ). Первые попытки мо­ делирования телефонных систем относятся к двадцатым годам (Дамджон и Мартин [189], 1922; Эллиман и Фразер [199], 1928). В последующем построению МИТ уделялось много внимания как у нас, так и за рубежом.

Любая МИТ представляет собой устройство, моделирующее действие одного определенного класса систем, что является их главным недостатком по сравнению с ЭВМ. К тому же создание МИТ может потребовать годы, а написание программы моделиро­ вания на ЭВМ занимает несколько месяцев или только несколько дней, если использовать алгоритмические языки, и сравнительно легко поддается изменениям. Поэтому, несмотря на дороговизну ЭВМ, область применения MITT быстро сужается. Уже на V Меж­ дународном конгрессе по телетрафику в 1967 г. был представлен лишь один подобного рода доклад (доклад Рахко о создании фин­ ской МИТ для моделирования иеполнодоступных схем).

Так как в настоящее время МИТ представляет только истори­ ческий интерес, то алгоритм ее работы рассмотрим вкратце и в терминах, которыми будем пользоваться ниже при описании алго­ ритмов моделирования на ЭВМ.

Пусть МИТ моделирует действие и-линейиого полнодоступного пучка, который обслуживает пуассоновский поток интенсивности X, продолжительность разговора подчиняется экспоненциальному рас­ пределению с параметром, равным единице. Один цикл работы МИТ состоит в выборе событий «поступил вызов» с вероятностью

----- — или события «кончается разговор на i-й линии» с вероятно- v + А.

стью —-— , i= l,..., V. Если выбранная i-я линия свободна, то цикл;

V + А

134

является безрезультатным. В итоге вычисляется оценка вероятности потерь по вызовам.

Созданы различные МИТ для моделирования неполнодоступных схем и других коммутационных систем. Действие их в какой-то ме­ ре напоминает испытания экспериментального образца коммутаци­ онной системы, требующего разработки для этой цели специальных устройств нагрузки и измерительных комплексов. Однако по мере передачи функций управления коммутационных систем специали­ зированным ЭВМ такой метод натурных испытаний уходит в про­ шлое, уступая место программной проверке системы с участием самой управляющей ЭВМ или при помощи другой, более мощной ЭВМ.

Впервые телефонные системы на ЭВМ изучали шведские ин­ женеры Неовиус [265] в 1955 г. и Валстрем [295] в 1958 г. Составленные ими программы моделирования воспроизводили ра­ боту МИТ. Впоследствии по мере развития вычислительной техники этот подход стал применяться повсеместно: Одновременно шло развитие алгоритмов моделирования.

Среди работ по статистическому моделированию телефонных си­ стем, проведенных в Советском Союзе, исторически первыми яв­ ляются работы Г. П. Башарина и его учеников [19, 30], где исследо­ ваны некоторые простые двухкаскадные схемы с упором на стати­ стическое изучение характеристик марковских процессов, описы­ вающих действие телефонных систем при простейших предположе­ ниях. Однако эти первые работы не нашли прямого инженерного применения в телефонии, хотя и сыграли важную роль при установ­ лении слабой зависимости условных вероятностей уа (X) от Я, (см. гл. 9).

В настоящее время моделированием коммутационных систем (не только телефонных) заняты многие коллективы. Работы, нача­ тые Г. П. Башариным, нашли дальнейшее развитие в ЦНИИКА при моделировании производственных систем. Наиболее известный кол­ лектив, изучающий производственные процессы методом статисти­ ческого моделирования, — это коллектив в МГУ, руководимый член-корреспондентом АН СССР Л. А. Люстерником. Большие ус­ пехи в изучении практически важных телефонных систем достиг­ нуты в Вычислительном центре Латвийского Госуниверситета, где под руководством Г. Л. Нонина в содружестве с ЦНИИС ЛФ (с лабораторией, руководимой Б. С. Лившицем) и СКВ завода ВЭФ (руководимым Т. Я. Розитисом) разработан набор программ стати­ стического моделирования различных телефонных систем, состоя­ щий из более чем 20 программ, которые впервые в Советском Сою­ зе доведены доширокого практического применения в научно-ис­ следовательской и конструкторской практике. Часть алгоритмов и программ перечислена в [64]. Например, там указано, что уже в 1966 г. было произведено моделирование станции АТС К-40/80 или, другими словами, моделирование двухкаскадной неполнодоступной коммутационной схемы, входящей в АТС К-40/80. Использование

135

предложенных нами принципов построения оптимальных неполно­ доступных схем (см. гл. 5) и учет других соображений, предло­ женных Т. Я. Розитисом, дало возможность выбрать новую схему АТС К-40/80, которая содержала на 25—40% меньше МКС (много­ кратных координатных соединителей — основных блоков комму­ тационной схемы координатных АТС), чем ранее разработанная схема.

3.Об алгоритмических языках для статистического моделирования

По мере увеличения области применения метода статистиче­ ского моделирования все больше ощущается необходимость в соз­ дании специальных алгоритмических языков, направленных на об­ легчение работы составления программы моделирования. Хороший обзор этого вопроса содержится в [159].

Среди разработанных алгоритмических языков моделирования наиболее общими и универсальными по своим возможностям явля­ ются языки СИМСКРИПТ [104] н СИМУЛА [48]. Оба языка рас­ полагают богатым набором арифметических операторов и операто­ ров управления, который позволяет запрограммировать практиче­ ски любой алгоритм поведения сложной системы.

Язык СИМСКРИПТ построен па основе алгоритмического язы­ ка ФОРТРАН, который особенно широко распространен в США. Язык СИМУЛА является расширением языка АЛГОЛ, который в настоящее время все больше применяется в практике программи­ рования в Советском Союзе. Однако эти языки недостаточно учиты­ вают специфику коммутационных схем, поэтому пх использование в задачах телетрафика весьма ограничено. Для нужд статистичес­ кого моделирования коммутационных систем следует создавать спе­ циальные проблемно ориентированные языки.

Вряде организаций в США [296], ФРГ [252], Швеции [215, 272]

идругих, создающих телефонные системы, используется язык

GPSS (General Purpose Simulation System) [211], который предна­ значен для моделирования графа, приближенно описывающего

коммутационную систему согласно подходу Ли [166]' (см. также гл. 4). Еще большее облегчение инженерного труда дает система автоматического программирования SMILE (Switching Mashine Interpreter for Lazy Engineers), созданная в лабораториях Белла

(США) для автоматизации разработки математического обеспече­

136