Телетраффика. Издание второе, переработанное и дополненное
 Скачать 3.77 Mb.
|
|
7.3. Моделирование коммутационных систем на универсальных вычислительных машинах Моделирование на основе цепи Маркова процесса обслуживания потока вызовов коммутационной системой. При моделировании процесса обслуживания потока вызовов коммутационной системой, как и при моделировании любой системы массового обслуживания, нет необходимости полностью имитировать реальный процесс. Достаточно, чтобы различные состояния искусственного и реального процессов совпадали либо находились во взаимно однозначном соответствии, иными словами, достаточно, чтобы моделируемый искусственный процесс и получаемые при этом характеристики соответствовали в статистическом смысле реальному процессу и исследуемым вероятностным характеристикам. Ранее было показано, что процесс функционирования любойкоммутационной системы при обслуживании потока с простымпоследействием (в том числе и простейшего потока вызовов) припоказательном распределении длительности занятия является марковским процессом. Поэтому вместо моделирования реальногопроцесса обслуживания потока вызовов коммутационной системойможно моделировать марковский процесс, те. моделировать искусственный процесс с вероятностными свойствами реального процесса. При этом модель описывается системой уравнений различных состояний обслуживающей коммутационной системы. Заменамоделирования реального процесса моделированием марковскогопроцесса приводит к существенной экономии в оперативной и постоянной памяти вычислительной машины. При имитации моделирования реального процесса обслуживающей коммутационной системы марковским процессом требуется учитывать случайные отрезки времени пребывания системы в различных состояниях. Существенное дальнейшее упрощение статистического моделирования обслуживающей коммутационной системы достигается заменой моделирования марковского процесса моделированием цепи Маркова. При этом переход модели из одного состояния в другое происходит в дискретные моменты времени, в каждый из которых реализация случайной величины имитирует либо поступление нового вызова, либо окончание находящегося на обслуживании какого-либо вызова. Между всеми состояниями коммутационной системы и моделируемой цепи Маркова устанавливается взаимно однозначное соответствие. Это означает, что под воздействием поступившего в дискретный момент времени вызова (или окончания соединения) переход моделируемой цепи Маркова из какого-либо определенного состояния в новое соответствует переходу реальной коммутационной системы в такое же новое состояние, если до этого коммутационная система находилась в однозначном состоянии с моделируемой цепью Маркова. При моделировании цепи Маркова каждое изменение цепи происходит за один цикл работы машины, в течение которого реализуется случайная величина, имитирующая поступление нового вызова или окончание обслуживания какого-либо ранее поступившего вызова, а также происходит переход цепи в другое состояние. Не требуется в явном виде учитывать время пребывания системы в различных состояниях. В результате уменьшаются объемы информации, которые должны храниться в памяти машины, на каждое изменение состояния обслуживающей системы требуется меньшее число операций машины – сокращается время цикла работы машины. Поэтому имеется возможность осуществлять на ЭВМ статистическое моделирование обслуживающих коммутационных параметров, получать значительные по объему статистические характеристики исследуемых систем и одновременно сокращать время моделирования. Для реализации каждого из событий, поступающих в дискретные моменты времени (поступления нового вызова, освобождения какого-либо соединительного пути, необходимо знать вероятности их поступления. С этой целью определим указанные вероятности и способ их реализации при моделировании на ЭВМ цепи Маркова, имитирующей обслуживающую коммутационную систему при достаточно общих предположениях. Коммутационная система произвольной структуры (рис. 7.3) содержит s групп входов и h групп (направлений) выходов. На каждую группу входов поступает поток с простым последействием. Параметр потока вызовов – λ(i, j, k), где i – номер группы входов j – номер выбираемого направления k – номер состояния коммутационной системы в момент поступления вызова. Параметр потока освобождений соединительного пути между й группой входов им направлением при k-мсостоянии системы – ν(i, j, k). Суммарный параметр потоков вызовов аи суммарный параметр потоков освобождений в промежутки времени, в которые коммутационная система находится в состоянии k, составляют При k-мсостоянии цепи Маркова моделируется случайная величина ξ, равномерно распределенная на отрезке [0, Если в рассматриваемом цикле работы ЭВМ случайная величина ξ реализуется на участке равномерно распределенного отрезка [0, а, соответствующем то полагаем, что эта случайная величина определяет поступление вызова на п-югруппу входов и соединение требуется установить в м направлении. Если ξ реализуется на участке то величина ξ определяет освобождение соединительного пути между й группой входов и т-йгруппой выходов. Заметим, что при этом может освободиться любой из установленных соединительных путей между указанными группами входов и выходов. Статистические характеристики моделирования. Целью моделирования является получение статистических оценок вероятностных характеристик процессов обслуживания коммутационными системами поступающих потоков вызовов при заданных дисциплинах обслуживания. Эти оценки принято называть статистическими характеристиками. К таким характеристикам относятся в системах с потерями – вероятность потерь, вероятности различных состояний коммутационной системы в системах с ожиданием – распределение времени ожидания начала обслуживания, среднее время ожидания, средняя длина очереди и другие характеристики. Моделирование исследуемого процесса разбивается на группу п экспериментов (серий, в каждом из которых производится равное число m испытаний (например, число поступающих вызовов. Число испытаний в каждом эксперименте выбирается таким, чтобы измеряемые статистические характеристики исследуемых вероятностных величин были бы достаточно представительны. Так, при определении вероятности потерь (ожидаемая величина которых 86 составляет порядка 5%o) необходимо в каждом эксперименте предусмотреть десять и более тысяч испытаний, стем чтобы число потерянных вызовов достигало нескольких десятков и даже сотен. В конце моделирования исследуемого процесса определяются средние значения, дисперсии и доверительные интервалы измеряемых статистических характеристик. Перед моделированием первого эксперимента необходимо осуществить нулевую серию моделирования для приведения исследуемой системы в стационарный режим. 7.4. Точность и достоверность результатов моделирования При моделировании коммутационных систем, как отмечалось выше, общее время моделирования разбивается на п равных отрезков, те. разбивается на п экспериментов серий. В каждом эксперименте производится равное число т испытаний (как правило, т поступающих вызовов. Для каждой серии определяется экспериментальное значение исследуемой статистической характеристики, например потерь, по формуле где r i – число появлений исследуемого события (число потерянных вызовов) в i-йсерии; x i – экспериментальное значение статистической характеристики (потерь) в той же серии. После завершения процесса моделирования определяются статистические оценки среднего значениях, дисперсии σ 2 и среднеквадратического отклонения σ по формулам Оценка точности и достоверности результатов моделирования может быть произведена на основе применения центральной предельной теоремы для стационарных последовательностей, согласно которой исследуемые статистические характеристики сходятся к нормальному закону. При этом оценка точности и достоверности результатов моделирования производится по критерию Стьюдента: где р) – доверительная вероятность или надежность статистической оценки, те. вероятность того, что случайный доверительный интервал х, х) содержит в себе теоретическую (достоверную) характеристику х S n-1 (z* n-1 ) – коэффициент, определяемый распределением Стьюдента при (п–1)-й степени свободы. Величина ε определяет точность статистической оценки, или доверительную границу статистической оценки. При числе степеней свободы пи величина S n _ 1 (z* n _ 1 ) определяется по таблицам распределения Стьюдента. Если число степеней свободы (n–1)>19 (те. число экспериментов n>20), то величину S n _ 1 (z* n _ 1 ) можно определять по приближенной формуле где Ф) – интегральная форма функции, предназначенная для вычисления значений функции нормального распределения и определяемая по формуле Функция Ф) табулирована. В (7.11) , * 1 n z n σ = − ε и при заданной доверительной 87 вероятности p(z* n _ 1 ) с увеличением числа экспериментов п повышается точность статистической оценки, те. уменьшается доверительная граница статистической оценки е, а следовательно, сокращается доверительный интервал х, х. Поэтому рекомендуется, чтобы количество серий п при моделировании исследуемой коммутационной системы было достаточно большим – желательно, чтобы n ≥50. Расчетами установлено, что при таких значениях п достигается и достаточно устойчивое значение статистической оценки среднеквадратического отклонения σ. Задача. Исследуется коммутационная система с потерями, в которой необходимо определить вероятность потерь р при определенных параметрах системы и заданной величине интенсивности поступающей нагрузки. Моделирование коммутационной системы проведено 3 раза с различным числом экспериментов (серий n 1 =16, n 2 =25, n 3 =49. В результате каждого процесса моделирования получены одинаковые статистические оценки среднего значения потерь р и среднеквадратического отклонения σ, а именно р и σ=0,01. Определить доверительные интервалы вероятности потерь р для трех процессов моделирования при доверительной вероятности p(z* n-1 ) =0,95. Решение. Значения коэффициента z* n-1 табулированы в зависимости от доверительной вероятности p(z* n-1 ) и числа степеней свободы n–1 [29]. Для p(z* n–1 )=0,95 и n 1 –1=15 значение коэффициента z* n-1 =2,13. Из соотношения , * 1 n z n σ = ε − определяем ε 1 =0,0053. Доверительный интервал составит (р. Для n 2 =25 и n 3 = 49 коэффициент z можно определять в предположении, что величина р распределена по нормальному закону. В этом случае при p(z* n-1 )=0,95 значение z=l,96. Тогда при n 2 =25 и n 3 =49 соответственно ε 2 =0,004 и ε 3 =0,0028 и доверительные интервалы (р) и (р. Таким образом, рассмотренная задача показывает, что при определенной доверительной вероятности p(z* n-1 ) с увеличением числа экспериментов п сокращается доверительный интервал. Контрольные вопросы 1. Как формируется непрерывная случайная величина, равномерно распределенная на отрезке [0,1] с помощью моделирования дискретной случайной величины 2. В чем заключается принцип моделирования непрерывной случайной величины, распределенной по любому закону 3. В чем сущность и каковы достоинства моделирования цепью Маркова процесса обслуживания потока вызовов коммутационной системой 4. Что представляют собой статистические характеристики моделирования 5. Как определяются точность и достоверность результатов моделирования 88 ГЛАВА ВОСЬМАЯ Неполно доступное включение. Системы с потерями. Общие сведения Неполнодоступная коммутационная схема (НС) – это схема с таким включением выходов, при котором каждому входу доступны не все, а лишь некоторая часть выходов, хотя в совокупности все входы могут использовать все выходы. Совокупность входов НС, каждому из которых доступны одни и те же d выходов, называется нагрузочной группой. Число нагрузочных групп обозначается g. Число выходов d НС, каждый из которых доступен каждому входу одной нагрузочной группы, называется доступностью. Чаще всего применяются такие НС, у которых доступность для всех нагрузочных групп одинакова. На риса приведена четырехгрупповая схема неполнодоступного включения. Схема характеризуется следующими параметрами число нагрузочных групп g=4; число выходов υ=4k 1 +2k 2 +k 4 =16; доступность выходов d=k 1 +k 2 +k 4 =10; число индивидуальных выходов в каждой группе k 1 =1; число выходов, общих для двух групп, k 2 =3; число выходов, общих для четырех групп, k 4 =6. В схеме, приведенной на риса, число объединяемых точек коммутации монотонно возрастает с увеличением порядкового номера точки в ряду, относящемуся к одной группе. Такие неполнодоступные схемы называют схемами ступенчатого включения. В схемах ступенчатого включения могут объединяться точки коммутации несоседних групп перехваченные включения) и точки коммутации с разными номерами сдвинутые включения. На рис. б приведена схема ступенчатого включения с теми же параметрами, что и схема на риса. Коммутационные точки с порядковыми номерами 3 и 4 здесь объединяются с применением перехваченного, а точки 5–10 – сдвинутого включения. Другой разновидностью неполнодоступных схем являются равномерные схемы неполнодоступного включения. На рис. 8.1 в приведена четырехгрупповая схема с теми же параметрами, что и две предыдущие. В отличие от ступенчатой схемы, равномерная схема строится по принципу объединения точек коммутации у одинакового числа групп при образовании любого общего выхода. На рис. в видно, как объединяются по две или три точки коммутации, принадлежащие разным группам. Здесь применяются также сдвинутое и перехваченное включения. Равномерная схема рис. в состоит из четырех элементарных подсхем, каждая с одинаковым сдвигом между соседними шагами искания. Такие элементарные подсхемы называются цилиндрами Для заданных значений 89 параметров d ив случае двухгруппо-вого включения (g=2) существует лишь один вариант структуры неполнодоступного включения (один набор значений структурных параметров и k 2 ). Для многогруппового включения (g>2) каждому значению параметров d и υможет соответствовать несколько вариантов структуры, и при достаточно больших g, d и υчисло вариантов может быть велико. Неполнодоступная схема имеет существенные отличия от полнодоступной. В полнодоступной схеме (ПС) d ≥υ, в неполнодоступной схеме d<υ. Кроме того, в полнодоступной схеме (см. гл) характер включения выходов в точки коммутации и порядок искания свободного выхода не влияют на вероятность потерь при заданной интенсивности поступающей нагрузки, учитываются только макросостояния. В неполнодоступной схеме характер включения выходов и порядок искания существенно влияют на пропускную способность НС, так как вероятность потери поступающего вызова в общем случае зависит не только от числа выходов, но и оттого, какие выходы заняты, те. необходимо учитывать микросостояния. В связи с этим метод исследования полнодоступной схемы с помощью системы уравнений для вероятностей состояний, как правило, непригоден для НС из-за большого числа уравнений в системе, которая не может быть решена в хоть сколько-нибудь приемлемое время даже с помощью быстродействующих ЭВМ. Решение системы уравнений для вероятностей состояний НС возможно лишь для неполнодоступных схем, рассчитанных на небольшое число линий или схем, обладающих свойствами симметрии, как это имеет, место в случае идеально симметричного неполнодоступного включения, для которого можно ограничиться рассмотрением только макросостояний, а следовательно, и число уравнений сравнительно мало. К сожалению, эти случаи не имеют существенного практического значения и представляют лишь теоретический интерес для получения оценок вероятности потерь. В практике проектирования обычно пользуются приближенными инженерными методами, которые основаны на априорных предположениях не о поступающем потоке вызовов, а о промежуточных или конечных результатах его воздействия на НС, те. о характере распределения числа занятых выходов схемы или о средней нагрузке, обслуженной каждым выходом НС. К таким методам можно отнести известные методы О'Делла, Бабицкого, Лотце модифицированная формула Пальма–Якобеуса) и другие. В некоторых приближенных инженерных методах используются свойства определенных видов НС стем, чтобы отдельные части такой НС представить в виде полнодоступной схемы и воспользоваться сравнением НС с некоторой эквивалентной ПС (метод эквивалентных замен. Основные цели, преследуемые при теоретическом анализе НС, заключаются в том, чтобы при заданной доступности определить число выходов НС, требуемых для обслуживания заданной нагрузки при установленном качестве обслуживания (вероятности потерь для систем с потерями, и определить оптимальную структуру НС (способ включения выходов в точки коммутации схемы при заданном порядке искания свободного выхода. 8.2. Некоторые характеристики неполнодоступных схем Матрица связности. Одной из характеристик неполнодоступной схемы является число связей, те. число соединений между точками коммутации (контактами) отдельных нагрузочных групп НС. Так, на риса первая группа имеет девять связей со второй группой (нам шагах искания, вторая группа – шесть связей с третьей, третья группа – девять связей с четвертой и т. д. Число связей между каждой парой групп можно представить в виде матрицы связности. Матрица связности является квадратной-симметричной относительно главной диагонали матрицей порядка g, где g – число нагрузочных групп неполнодоступной схемы. На рис. 8.1 где, приведены матрицы связности для неполнодоступных схем, изображенных на риса, б, в. Схемы имеют одинаковое число групп g = 4, одинаковую доступность d = 10, одно и тоже число выходов υ=16, отличаются способом соединения 90 точек коммутации. Элементы главной диагонали равны доступности d. Элементы, стоящие на пересечении строки и столбца, показывают число связей между группами, соответствующими номерам строки и столбца. Элементы столбца, расположенного справа от матрицы, указывают на суммарное число связей соответствующей группы с остальными. Как видно из рис. 8.1, и суммарное число связей у каждой группы с другими и равномерность их распределения по группам различны у разных схем. Суммарное число связей у первых двух неполнодоступных схем больше, чему третьей равномерной схемы. Наиболее равномерно распределены связи каждой группы с другими во второй НС. Исследования показывают, что при прочих равных условиях схема, обладающая более равномерной матрицей связности, имеет в определенных случаях преимущество перед схемой с менее равномерной матрицей. Считают, что если разница между любыми двумя элементами матрицы связности и разница между любыми двумя элементами столбца, расположенного справа от матрицы, не превышают по абсолютной величине единицу, то неполнодоступная схема построена хорошо. Матрица, удовлетворяющая указанным условиям, обеспечивает одинаковую связность каждой из нагрузочных групп с любой другой и одинаковую суммарную связность каждой из групп со всеми остальными. При одинаковой нагрузке на каждую из нагрузочных групп НС, обладающая такой матрицей связности, характеризуется одинаковым влиянием всех нагрузочных групп друг на друга. Однако матрица связности не может служить полной характеристикой НС. Существенное значение имеет также распределение связей по шагам искания, учет порядка искания в НС и др. Коэффициент уплотнения. Для характеристики схемы неполнодоступного включения используют коэффициент уплотнения Значения γ лежат в пределах l<γ υ=d), а при γ=1меполнодоступная схема распадается на g изолированных полно-доступных схем. Таким образом, чтобы НС не распадалась на g отдельных ПС, должно соблюдаться неравенство γ>1. Для уточнения величины можно привлечь следующие соображения. При проведении предварительного запараллеливания надо получить такое число групп, чтобы телефонная нагрузка, создаваемая каждой группой, была меньше нагрузки, которую могут обслужить d линий полнодоступного пучка при заданных потерях. Если при заданных потерях р интенсивность нагрузки, обслуживаемой всеми линиями неполнодоступного пучка, равна НС, υ, d), то ее можно представить в виде где НС, υ, d) – средняя нагрузка, пропускаемая каждой линией неполнодоступного пучка, состоящего из линий. При равномерном распределении нагрузки между группами нагрузка каждой группы будет равна Интенсивность нагрузки у 0ПС (p, υ=d), обслуживаемой полнодоступным пучком, состоящим из d линий, при заданных потерях p может быть выражена как ПС, υ, d)=d η HC (p, υ=d). В соответствии с вышесказанным [υη HC (p, υ, ПС, υ=d), откуда Из неравенства (8.2) видно, что нижняя граница γ зависит от величины потерь р, числа линий в пучке и доступности d. Для столинейного неполнодоступного пучка (υ=100) с доступностью при потерях р неравенство (8.2) выглядит следующим образом γ>1,6. Практика эксплуатации телефонных систем и теоретические исследования показывают, что величину коэффициента уплотнения следует выбирать в пределах γ=2÷4. При малых коэффициентах уплотнения уменьшается пропускная способность неполнодоступного пучка за счет того, что среди возможных при такому схем неполнодоступного включения может не оказаться схемы с достаточно хорошей пропускной способностью. При больших увеличивается расход кабеля на АТС. Из предыдущего соотношения вытекает, что предварительное запараллеливание нужно производить так, чтобы получить число групп g, удовлетворяющее условию |