ТЕОРИЯ ИНФОРМАЦИИ И КОДИРОВАНИЯ. Воронежский институт мвд россии кафедра высшей математики
 Скачать 1.43 Mb.
|
|
(s ∗ 1 , s ∗ 2 , s ∗ 3 ) существуют. г) Для нахождения предельных состояний решим систему: q − 1 q 0 p 0 − 1 q 0 p p − 1 0 0 0 = 0 с дополнительным условием s 1 + s 2 + s 3 = 1: (q − 1)s 1 + qs 2 + 0 · s 3 = 0 ps 1 + (0 − 1)s 2 + qs 3 = 0 0 · s 1 + ps 2 + (p − 1)s 3 = 0 s 1 + s 2 + s 3 = 1 Поскольку система переопределена, вычеркнем любое уравнение (кроме последнего): (q − 1)s 1 + qs 2 + 0 · s 3 = 0 ps 1 + (0 − 1)s 2 + qs 3 = 0 s 1 + s 2 + s 3 = 1 Решая систему, получим: s 1 = q 2 q 2 + pq + p 2 , s 2 = pq q 2 + pq + p 2 , s 3 = p 2 q 2 + pq + p 2 . N 2.3.2 Работа телефонного коммутатора Пример 2.11. Исследуемая система (коммутатор) может принимать два состояния: она может быть свободной в момент времени t с вероятностью P 0 (t) и занятой с вероятностью P 1 (t). Если линия свободна, то за промежуток времени ∆t на коммутатор приходит сигнал с вероятностью α∆t, и переводит систему в состояние занято. Если коммутатор занят, то с вероятностью β∆t он обрабатывает сигнал и переходит в состояние свободно. Найти предельное состояние системы при α = 0.5; β = 0.3. Решение. Допустим, что в момент времени (t + ∆t) система была свободна. Это означает, что в предыдущий момент времени t: 1. система находилась в состоянии свободно P 0 (t) и на нее не пришел сигнал (вероятность непоступления сигнала равна 1 − α∆t); 2. система находилась в состоянии занято P 1 (t), но за промежуток времени ∆t запрос был обработан с вероятностью β∆t. 2.3. Теория массового обслуживания 65 Тогда по формуле полной вероятности получим: P 0 (t + ∆t) = P 0 (t)(1 − α∆t) + P 1 (t)β∆t или P 0 (t + ∆t) − P 0 (t) = −P 0 (t)α∆t + P 1 (t)β∆t. Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0 lim ∆t→0 P 0 (t + ∆t) − P 0 (t) ∆t = −P 0 (t)α + P 1 (t)β Поскольку, по определению производной lim ∆t→0 P 0 (t + ∆t) − P 0 (t) ∆t = dP 0 (t) dt = P 0 0 , то мы получили дифференциальное уравнение первого порядка P 0 0 = −P 0 α + P 1 β. Теперь допустим, что в момент времени (t+∆t) система была занята. Это означает, что в предыдущий момент времени t: 1. система находилась в состоянии свободно (с вероятностью P 0 (t)) и на нее пришел сигнал (вероятость поступления сигнала равна α∆t); 2. система находилась в состоянии занято (с вероятностью P 1 (t)) и за промежуток времени ∆t запрос так и не был обработан (вероятность необработки сигнала равна 1 − β∆t). Тогда, по формуле полной вероятности получим: P 1 (t + ∆t) = P 0 (t)α∆t + P 1 (t)(1 − β∆t), или P 1 (t + ∆t) − P 1 (t) = P 0 (t)α∆t − P 1 (t)β∆t. Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0: P 0 1 = αP 0 − βP 1 Предполагая, что в начальный момент времени t = 0 система была свободной (с вероятностью P 0 (0) = 1 (тогда P 1 (0) = 0)) мы получим систему дифференциальных уравнений P 0 0 = −αP 0 + P 1 β, P 0 (0) = 1, P 0 1 = P 0 α − P 1 β, P 1 (0) = 0. 66 Глава 2. Каналы связи Для получения данного решения в математическом пакете Maple необходимо ввести следующие операторы задающие систему дифференциальных уравнений: > s1 := diff(p0(t), t) + a ∗ p0(t) − b ∗ p1(t); (нажать Shift+Enter) s2 := dif f (p1(t), t) − a ∗ p0(t) + b ∗ p1(t); (нажать Enter) s1 := d dt (p0(t) + ap0(t) − bp1(t) s2 := d dt (p1(t) − ap0(t) + bp1(t) Решение ищем с учетом краевых условий (p 0 (0) = 1, p 1 (0) = 0): > dsolve([s1, s2, p0(0) = 1, p1(0) = 0], p0(t), p1(t)); p0(t) = β β + α + α β + α e −(β+α)t p1(t) = α β + α − α β + α e −(β+α)t Для конкретных значений α = 0.5; β = 0.3 несложно получить и графики зависимости состояния системы p0(t) и p1(t) от времени > a := 0.5; b := 0.3; p0(t) := b/(a + b) + a ∗ exp((−a − b) ∗ t)/(a + b); p1(t) := ( −a ∗ exp((−a − b) ∗ t) ∗ b/(a + b) + a ∗ b/(a + b))/b; > plot([p0(t), p1(t)], t = 0..5); p (t) p (t) 0 t 0 1 t* При t → ∞ предельные состояния системы имеют вид P 0 (t) = β α + β , P 1 (t) = α α + β Из графика видно, что кривая вероятности свободного состояния пересекается с кривой загруженного состояния. Это означает, что после достижения некоторого времени t ∗ система перестанет справляется с потоком заявок. Поэтому необходимо либо увеличивать производительность системы (уменьшить время обслуживания заявки), либо уменьшить сам поток заявок. N 2.3. Теория массового обслуживания 67 Ниже показан скриншот решения данной задачи в Maple. 0 2 4 6 8 10 0.5 1 P0 t ( ) P1 t ( ) P2 t ( ) t 0 2 4 6 8 10 0.5 1 P0 t ( ) P1 t ( ) P2 t ( ) P3 t ( ) P5 t ( ) t 68 Глава 2. Каналы связи Пример 2.12. Исследуется микропроцессор, рассчитанный на одновременное обслуживание 3 контроллеров. Найти предельное состояние системы, если вероятность поступления прерывания на микропроцессор за промежуток времени ∆t равна α∆t. Вероятность обработки прерывания за промежуток времени ∆t равна β∆t. (α = 0.3 , β = 0.5) Решение. Обозначим через P 0 (t) вероятность того, что микропроцессор свободен (на него не поступило ни одного прерывания). Тогда P 1 (t) - вероятность обработки микропроцессором одного прерывания, P 2 (t) - двух прерываний, P 3 (t)-трех прерываний. Введем обозначения для следующих состояний микропроцессора: x 0 - свободен; x 1 - занят ровно один вход x 2 -занято два входа x 3 -заняты все три входа. 0. Допустим, что в момент времени (t+ ∆t) система была свободна. Это означает, что в предыдущий момент времени t: 1. система находилась в состоянии свободно x 0 (с вероятностью P 0 (t)) и на нее не пришел сигнал (вероятность непоступления сигнала равна 1 − α∆t); 2. система находилась в состоянии занято x 1 , (с вероятностью P 1 (t)), но за промежуток времени ∆t запрос был обработан с вероятностью β∆t. Тогда по формуле полной вероятности получим: P 0 (t + ∆t) = P 0 (t)(1 − α∆t) + P 1 (t)β∆t или P 0 (t + ∆t) − P 0 (t) = −P 0 (t)α∆t + P 1 (t)β∆t. Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0 lim ∆t→0 P 0 (t + ∆t) − P 0 (t) ∆t = −P 0 (t)α + P 1 (t)β Поскольку, по определению производной lim ∆t→0 P 0 (t + ∆t) − P 0 (t) ∆t = dP 0 (t) dt = P 0 0 , то мы получили дифференциальное уравнение первого порядка P 0 0 = −P 0 α + P 1 β. 1. Теперь допустим, что в момент времени (t + ∆t) микропроцессор был занят обработкой одного прерывания. Это означает, что в предыдущий момент времени t: 2.3. Теория массового обслуживания 69 1. система находилась в состоянии x 0 свободно (с вероятностью P 0 (t)) и на нее пришел сигнал (вероятность поступления сигнала равна α∆t); 2. система находилась в состоянии x 1 и за промежуток времени ∆t система не обработала прерывание и на нее не пришел ни один сигнал (вероятность 1 − α∆t − β∆t). 3. система находилась в состоянии x 2 и за промежуток времени ∆t обработал один запрос из двух (вероятность 2β∆t). Тогда по формуле полной вероятности получим: P 1 (t + ∆t) = P 0 (t)α∆t + P 1 (t)(1 − α∆t − β∆t) + 2β∆tP 2 (t), или P 1 (t + ∆t) − P 1 (t) = P 0 (t)α∆t − (α + β)P 1 (t)∆t + 2P 2 (t)β∆t. Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0: P 0 1 = αP 0 − (α + β)P 1 + 2βP 2 2. Теперь допустим, что в момент времени (t + ∆t) микропроцессор находился в состоянии x 2 (был занят обработкой двух прерываний). Это означает, что в предыдущий момент времени t: 1. система находилась в состоянии x 1 (с вероятностью P 1 (t)) и на нее пришел сигнал (с вероятностью α∆t); 2. система находилась в состоянии x 2 (с вероятностью P 2 (t)) и за промежуток времени ∆t запрос так и не был обработан и не пришел ни один запрос (вероятность 1 − α∆t − 2β∆t). 3. микропроцессор был полностью загружен обработкой трех прерываний (с вероятностью P 3 (t)) и за промежуток времени ∆t обработал одно из 3 прерываний. Т.е. перешел из состояния x 3 в состояние x 2 с вероятностью 3β∆t. Тогда по формуле полной вероятности получим: P 2 (t + ∆t) = P 1 (t)α∆t + P 2 (t)(1 − α∆t − 2β∆t) + 3β∆tP 3 (t), или P 2 (t + ∆t) − P 2 (t) = P 1 (t)α∆t − P 2 (t)(α + 2β)∆t + P 3 (t)3β∆t. Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0: P 0 2 = αP 1 − (α + 2β)P 2 + 3βP 3 3. Теперь допустим, что в момент времени (t + ∆t) микропроцессор находился в состоянии x 3 (был полностью загружен). Это означает, что в предыдущий момент времени t: 70 Глава 2. Каналы связи 1. система находилась в состоянии x 2 (с вероятностью P 2 (t)) и на нее пришел сигнал (с вероятностью α∆t); 2. система находилась в состоянии x 3 (с вероятностью P 3 (t)) и за промежуток времени ∆t запрос так и не был обработан ни один из 3 запросов (вероятность необработки сигналов равна 1 − 3β∆t). Тогда по формуле полной вероятности получим: P 3 (t + ∆t) = P 2 (t)α∆t + P 3 (t)(1 − 3β∆t), или P 3 (t + ∆t) − P 3 (t) = P 2 (t)α∆t − 3P 3 (t)β∆t. Разделим обе части уравнения на ∆t и возьмем предел ∆t → 0: P 0 3 = αP 2 − 3βP 3 Предполагая, что в начальный момент времени t = 0 система была свободной (с вероятностью P 0 (0) = 1 (тогда P 1 (0) = 0, P 2 (0) = 0, P 3 (0) = 0) мы получим систему дифференциальных уравнений P 0 0 = −αP 0 + P 1 β, P 0 (0) = 1, P 0 1 = P 0 α − (α + β)P 1 + 2P 2 β, P 1 (0) = 0, P 0 2 = P 1 α − (α + 2β)P 2 + 3P 3 β, P 2 (0) = 0, P 0 3 = P 2 α − 3P 3 β, P 3 (0) = 0. Для конкретных значений α = 0.3; β = 0.5 график решений принимает вид 0 2 4 6 8 10 0.5 1 P0 t ( ) P1 t ( ) P2 t ( ) t Из графика видно, что кривые вероятности свободного состояния P 0 (t) не пересекается с кривыми загруженного состояния. Это означает, что система справляется с потоком заявок и ее производительности хватает на обслуживание всех прерываний. N 2.3. Теория массового обслуживания 71 Ниже показан скриншот решения данной задачи в Maple. 72 Глава 2. Каналы связи Задача 2.7. Рассматривается работа офисной мини-АТС, рассчитанной на одновременное обслуживание n абонентов (n-канальная система). Найти предельное состояние системы. N n α β N n α β N n α β 1 5 0.21 0.36 11 5 0.11 0.31 21 5 0.21 0.19 2 6 0.22 0.37 12 6 0.12 0.32 22 6 0.22 0.20 3 7 0.23 0.38 13 7 0.13 0.33 23 7 0.23 0.21 4 8 0.24 0.39 14 8 0.14 0.34 24 8 0.24 0.22 5 9 0.25 0.40 15 9 0.15 0.35 25 9 0.25 0.23 6 5 0.26 0.41 16 5 0.16 0.49 26 5 0.26 0.24 7 6 0.27 0.42 17 6 0.17 0.50 27 6 0.27 0.25 8 7 0.28 0.43 18 7 0.18 0.21 28 7 0.28 0.46 9 8 0.29 0.44 19 8 0.19 0.33 29 8 0.29 0.47 10 9 0.30 0.45 20 9 0.20 0.34 30 9 0.30 0.48 2.3.3 Система массового обслуживания с ожиданием Рассмотрим ситуацию, в которой заявка, заставшая все n каналов занятыми, становится в очередь и ждет, пока не освободится какой либо канал. Очевидно, что для постановки заявки в очередь должны быть выделены соответствующие ресурсы (объем кэш- памяти процессора, количество мест в приемной у начальника). Если ресурсы (места) для ожидания заполнены, то заявка в очередь не становится. Обозначим α∆t- вероятность поступления заявки в систему; β∆t- вероятность обслуживания заявки; γ∆t- вероятность ухода заявки из очереди. В общем случае n-канальная система с k-разрядной памятью (память удерживающая k-заявок) может принимать следующие состояния x 0 -все каналы свободны; x 1 -один канал занят; x 2 -два канала заняты; x n -все n-каналов заняты; x n+1 -все каналы заняты и одна заявка в очереди; x n+2 -занято два места в очереди; x n+k -заняты все n-каналов и k-мест в очереди. 2.3. Теория массового обслуживания 73 Система дифференциальных уравнений для данного случая принимает вид P 0 0 = −αP 0 + βP 1 P 0 1 = P 0 α − (α + β)P 1 + 2βP 2 P 0 2 = P 1 α − (α + 2β)P 2 + 3βP 3 P 0 n−1 = P n−2 α − (α + (n − 1)β)P n−1 + nβP n P 0 n = P n−1 α − (α + nβ)P n + (nβ + γ)P n+1 P 0 n+1 = P n α − (α + nβ + γ)P n+1 + (nβ + 2γ)P n+2 P 0 n+2 = P n+1 α − (α + nβ + 2γ)P n+2 + (nβ + 3γ)P n+3 P 0 n+k = P n+k−1 α − (nβ + kγ)P n+k Начальные условия P 0 (0) = 1, P 1 (0) = P 2 (0) = P 3 (0) = P 4 (0) = ... = P n+k (0) = 0. Пример 2.13. На 3 канальный коммутатор с 2 разрядной памятью приходит поток заявок. Вероятность поступления заявки на коммутатор за промежуток времени ∆t равна α∆t; вероятность обслуживания β∆t; вероятность ухода заявки из очереди γ∆t. Найти предельное состояние системы при α = 0.5; β = 0.3. Решение. Система может принимать одно из следующих возможных состояний: x 0 -ни один канал не занят x 1 -занят ровно один канал x 2 -занято два канала x 3 -заняты три канала x 4 -заняты все каналы, и одна заявка стоит в очереди x 5 - заняты все каналы, и две заявки стоит в очереди Тогда, система дифференциальных уравнений для соответствующих вероятностей имеет вид: P 0 0 = −P 0 α + P 1 β P 0 1 = P 0 α − (α + β)P 1 + 2βP 2 P 0 2 = P 1 α − (α + 2β)P 2 + 3βP 3 P 0 3 = P 2 α − (α + 3β)P 3 + (3β + γ)P 4 P 0 4 = P 3 α − (α + 3β + γ)P 4 + (3β + 2γ)P 5 P 0 5 = P 4 α − (3β + 2γ)P 5 Начальные условия P 0 (0) = 1, P 1 (0) = P 2 (0) = P 3 (0) = P 4 (0) = P 5 (0) = 0. 0 2 4 6 8 10 0.5 1 P0 t ( ) P1 t ( ) P2 t ( ) P3 t ( ) P5 t ( ) t Для конкретных значений α = 0.5; β = 0.3; γ = 0.1 график решений принимает вид, показанный на рисунке. 74 Глава 2. Каналы связи Задача 2.8. Рассматривается работа офисной мини-АТС, рассчитанной на одновременное обслуживание n абонентов (n-канальная система), которая может держать в памяти (на очереди k вызовов). Найти предельное состояние системы. № n k α β γ № n k α β γ 1 2 4 0.11 0.36 0.21 16 3 3 0.11 0.21 0.36 2 3 5 0.12 0.37 0.22 17 4 4 0.12 0.22 0.37 3 4 6 0.13 0.38 0.23 18 5 5 0.13 0.23 0.38 4 5 7 0.14 0.39 0.24 19 6 6 0.14 0.24 0.39 5 6 8 0.15 0.40 0.25 20 7 5 0.15 0.25 0.40 6 7 7 0.16 0.41 0.26 21 8 4 0.16 0.26 0.41 7 8 6 0.17 0.42 0.27 22 9 3 0.17 0.27 0.42 8 9 5 0.18 0.43 0.28 23 8 3 0.18 0.28 0.43 9 8 4 0.19 0.44 0.29 24 7 3 0.19 0.29 0.44 10 7 3 0.20 0.45 0.30 25 6 4 0.20 0.30 0.45 11 6 4 0.21 0.46 0.31 26 5 4 0.21 0.31 0.46 12 5 5 0.22 0.47 0.32 27 4 4 0.22 0.32 0.47 13 4 6 0.23 0.48 0.33 28 3 5 0.23 0.33 0.48 14 3 7 0.24 0.49 0.34 29 4 3 0.24 0.34 0.49 15 4 8 0.25 0.50 0.35 30 5 4 0.25 0.35 0.50 2.4 Стандарт сотовой связи GSM GSM сначала означало Groupe Special Mobile, по названию группы анализа, которая создавала стандарт. Теперь он известен как Global System for Mobile Communications (Глобальная Система для Мобильной Связи), хотя слово «Связь» не включается в сокращение. Система синхронизации рассчитана на компенсацию абсолютного времени задержки сигналов до 233 мкс, что соответствует максимальной дальности связи или максимальному радиусу ячейки (соты) 35 км. Общая скорость преобразования речевого сигнала - 13 кбит/с. Скорость передачи сообщений в радиоканале, кбит/с 270, 833 Скорость преобразования речевого кодека, кбит/с 13 Ширина полосы канала связи, кГц 200 Максимальное количество каналов связи 124 Максимальное количество каналов, организуемых в базовой станции 16-20 GSM 900 BS 935MHz ⇐ 25MHz ⇒ 960MHz ⇑ 125 × 200 ⇑ 45MHz 45MHz ⇓ ⇓ MS 890MHz 200KHz 200KHz 200KHz 200KHz 915MHz № канала 1 123 124 2.4. Стандарт сотовой связи GSM 75 Стандарт GSM разработан для создания сотовых систем подвижной связи в следующих полосах частот: 890-915 МГц - для передачи мобильными станциями (телефоном) (линия "вверх"); 935-960 МГц- для передачи базовыми станциями (сотовой антенной) (линия "вниз"). Каждая из полос, выделенных для сетей GSM, разделяется на частотные каналы. Разнос каналов составляет 200 кГц, что позволяет организовать в сетях GSM 124 частотных канала. Частоты, выделенные для передачи сообщений подвижной станцией на базовую и в обратном направлении, группируются парами, организуя дуплексный канал с разносом 45 МГц. Эти пары частот сохраняются и при перескоках частоты. |