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

Подставляя х = \ и х —ц/Х, а также полагая а=Я/ц, находим

Для определения ри Рь—, Pk имеем систему, состоящую из неис­ пользованных исходных уравнений, и условия нормировки

Эту систему можем решить рассмотренным выше способом. Если

чить среднее число ожидающих в очереди и т. д.

Аналогичным образом, если требуется определить среднее вре­ мя достижения 7\- некоторого состояния Xj, j< .k , полагаем

Для определения Ти, Th-i и Д, i</e— 1, ‘имеем 'неиспользованные исходные уравнения и (53). Затем получаем Т(х) и т. д.

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

а) использование части исходных уравнений при выводе соот­ ношений для производящей функции;

83

б) анализ этих соотношении, получение из них соотношений для функций с меньшим числом переменных (в рассматриваемом

изводя щимн фуикцнями.

Соотношения для производящих функций, естественно, позво­

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

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

но предоставленные Гринбергом. При описании марковского про­ цесса в виде потоков в графе автор следует монографии Бержа [25]. Комбинаторный метод классификации состояний, рассматриваемый в § 4.1.2, более простой, чем алгоритмы, ко­ торые обычно рекомендуются для анализа марковских процессов, например, действия со степенями матрицы А [137, 145] или других матриц того же порядка либо с собственными значениями и векто­ рами таких матриц [31]. Оба эти способа весьма трудоемки, если число состояний достигает нескольких сотен или больше. Для клас­ сификации состояний марковских цепей Сарымсаков [125] предла­ гает еще более трудоемкий прием, требующий как возведения матрицы типа А в степени, так и исследования всех траекторий, ис­ ходящих из отдельных состояний.

Теорема 4.1 обобщает правила, данные в свое время Кирхго­ фом [239] для расчета электрических цепей и широко реклами­ руемые в последнее время под различными другими названиями в качестве метода расчета электрических цепей [109]. Такой способ расчета предлагался также и для марковских систем [26].

84

Исследование неполнодоступных схем

Внастоящей главе подробно рассмотрена од­ на из классических проблем теории теле­ трафика — проблема выбора оптимальных

неполнодоступных схем (НС). В § 5.1 приводятся численные при­ меры, решенные на ЭВМ и иллюстрирующие различные принципы построения НС при конечных значениях нагрузки. Названия пунк­ тов в § 5.1 представляют собой перечисление этих принципов. Ос­ новной практический вывод — это целесообразность широкого при­ менения равномерных схем. Параграф 5.2 содержит математичес­ кий аппарат степенных разложений для оценки вероятности потерь при предельных больших и малых нагрузках. На основе этого ма­ тематического аппарата в § 5.3 доказаны важные предельные тео­ ремы: 1) об оптимальности равномерных схем при больших на­ грузках и 2) об оптимальности схем, содержащих максимальное число индивидуальных линий, при малых нагрузках. В § 5.4 изла­ гаются приемы построения равномерных НС.

5.1.ЧИСЛЕННЫЕ ПРИМЕРЫ АНАЛИЗА НЕПОЛНОДОСТУПНЫХ СХЕМ1

1.Существуют ли неполнодоступные схемы, равномерно лучшие по %

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

На рис. 5.1 приведены две НС, имеющие одни и те же парамет­ ры: число входных потоков п = 4, доступность d = 3, число линий и = 6. Приведенные НС отличаются только видом включения, т. е.

86

ступенчатых схем, которые еще в 60-х годах рекомендовались для.

практического применения1). В табл. 5.1 приведены результаты вы­ числения вероятности потерь рассматриваемых схем, которые ста­ вят под сомнение целесообразность такой практической рекоменда-

ции. А именно, оказывается, что ступенчатая схема на рис. 5.1а является оптимальной только в области малых потерь — приблизи­ тельно до я< 0,001 или, другими словами, до A fa 0,.7 (при этом А = 4Я). Для всех остальных значений параметров к более выгод­ но применять равномерную схему, приведенную на рис. 5.16. Тем самым на вопрос, поставленный в заголовке настоящего раздела, следует ответить отрицательно, так как при данном наборе пара­ метров п, d, v не существует схемы, равномерно лучшей при всех значениях интенсивности потока к (это доказано в § 5.3).

Заметим, что для вычисления вероятности потерь любой из двух, схем, изображенных на рис. 5.1, необходимо решить систему линей­ ных алгебраических уравнений порядка 26 = 64. Учитывая симмет­

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

87

рию схем и потоков, состояния удалось укрупнить и тем самым по­ низить порядок системы. Минимальное марковское разбиение ис­ ходного пространства состояний для схемы на рис. 5.1а имеет ^ с о ­ стоянии, для схемы на рис. 5.16 — 28. Методика составления систе­ мы уравнений подробно изложена в § 1.3.

2. Принципы построения равномерных схем и их численное подтверждение

Дадим одну из возможных формулировок принципов построе­ ния равномерных схем.

1. Контактное поле с параметрами п, d, v разбивается на кон­ тактные множества, содержащие по г или по г+1 контактов, где

г — д г (здесь квадратная скобка — знак целой части). 1

2.Контактные множества образуются так, что лднии, доступ­ ные г группам, размещены левее линий, доступных (г+1)-й группе (направление искания слева направо).

3.Каждая пара линий имеет число общих групп (по возмож­ ности), одинаковое с числом -общих групп любой другой пары линии.

4.Каждое отдельное контактное множество размещено (по воз­ можности) в минимальном количестве вертикалей контактного поля.

Приводимые ниже примеры показывают, что принципа 1 целесо­ образно придерживаться при средних и больших нагрузках, в то время как нарушение любого из принципов 2—4 приводит к увели­ чению потерь при всех нагрузках.

В качестве численного подтверждения применимости равномер­ ных схем рассмотрим два набора схем с одними и теми же пара­ метрами /2= 4, d = 3, а = 6. Каждый набор включает две схемы, рас­ смотренные выше. Данные по первому набору сведены в табл. 5.2.

88