Исследование математических моделей неустойчивых сетей случайного доступа
На правах рукописи
Коцюруба Полина Ивановна ИССЛЕДОВАНИЕ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ НЕУСТОЙЧИВЫХ СЕТЕЙ СЛУЧАЙНОГО ДОСТУПА 05.13.18 – математическое моделирование, численные методы и комплексы программ
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Томск-2006
Работа выполнена на кафедре теории вероятностей и математической статистики факультета прикладной математики и кибернетики Томского государственного уни верситета
Научный консультант: доктор технических наук, профессор Назаров Анатолий Андреевич
Официальные оппоненты: доктор физико-математических наук, профессор Демин Николай Серапионович, кандидат физико-математических наук, доцент Китаева Анна Владимировна
Ведущая организация: Сибирский государственный аэрокосмический университет (г. Красноярск)
Защита состоится:
29 июня 2006 г. В 10.30 часов на заседании диссертационного совета Д 212.267.08 при Томском государственном университете по адресу:
634050, г.Томск, пр.Ленина,
С диссертацией можно ознакомиться в научной библиотеке Томского государствен ного университета.
Отзыв на автореферат (в двух экземплярах, заверенные печатью), просьба высылать по адресу 634050, г.Томск, пр.Ленина, 36, Томский государственный университет, ученому секретарю университета Буровой Н.Ю.
Автореферат разослан «» мая 2006 г.
Ученый секретарь диссертационного совета, доктор технических наук, доцент А.В.Скворцов
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. Среди локальных вычислительных сетей, сети случай ного доступа составляют подавляющее большинство, благодаря наличию значи тельного числа их достоинств: высокая скорость передачи сообщений, приемлемая дальность, помехозащищенность, возможность передачи различных видов инфор мации, низкая относительная стоимость и т.д. Но такие сети обладают и рядом не достатков, основным из которых является неустойчивость их функционирования, присущая всем типам сетей случайного доступа.
Одной из наиболее важных характеристик сети передачи данных является ве личина задержки, необходимая для доставки сообщения от источника к месту на значения, которая в сетях случайного доступа является нерегулярной, поэтому ис следуется методами теории вероятностей и теории случайных процессов.
Главной методологической основой для анализа сетей случайного доступа яв ляется теория массового обслуживания. Но использование теории массового обслу живания, часто требует упрощающих предположений, так как, к сожалению, более реалистичные предположения делают содержательный анализ чрезвычайно слож ным. По этой причине невозможно провести точные количественные расчеты за держки на основе моделей теории массового обслуживания.
Здесь имеет место следующая ситуация. Классические модели массового об служивания, для которых получены аналитические формулы Эрланга, Поллачека Хинчина, приоритетные системы далеки от реальных сетей случайного доступа. Бо лее адекватными моделями являются системы массового обслуживания (СМО) с ис точником повторных вызовов (ИПВ), но, как уже отмечено выше, исследование та ких моделей является чрезвычайно сложным, поэтому реализуется либо графиче скими методами на уровне средних характеристик, либо имитационным моделиро ванием, позволяющим получать лишь численные результаты, не отражающими ка чественную картину. Тогда как системы с ИВП имеют очень странные свойства при большом числе узлов. Эти свойства становятся достаточно очевидны при аналити ческом исследовании рассматриваемых СМО, выполненном в данной работе асим птотическим методом. Исследованию математических моделей сетей связи посвя щены работы А.А.Назарова, В.И.Клименок, И.И.Хомичкова, Г.И.Фалина, Ю.Д.
Одышева, С.Л.Шохора, Н.М.Юревича, Rajan, Д.Ю.Кузнецова, В.А.Михайлова, С.У.Уразбаевой, С.М.Одоевского, К.В.Сорочинской.
Таким образом, данная работа, в которой проводиться аналитическое исследо вание математических моделей неустойчивых сетей случайного доступа, является актуальной и своевременной.
Цель работы. Целью работы является исследование сетей связи случайного доступа с общей средой передачи для нахождения вероятностно-временных характеристик, а также исследование функционирования неустойчивой сети случайного доступа во всей области изменения ее состояний.
То есть, были поставлены следующие задачи:
1. построение математической модели сети случайного доступа с протоколом доступа ALOHA с обновлением остаточного времени обслуживания искажен ной заявки;
2. исследование средних характеристик неустойчивой сети случайного доступа;
3. локальная диффузионная аппроксимация процесса изменения состояний неус тойчивой сети случайного доступа;
4. глобальная диффузионная аппроксимация процесса изменения состояний неус тойчивой сети случайного доступа;
5. нахождение времени стабильного функционирования неустойчивой сети слу чайного доступа;
6. распределение вероятностей значений процесса глобальной аппроксимации в области стабильного функционирования неустойчивой сети случайного досту па;
7. определение основных вероятностно-временных характеристик неустойчивых сетей случайного доступа.
Методика исследований. Исследование математических моделей сетей слу чайного доступа проводилось с помощью методов теории вероятностей, теории слу чайных процессов, теории массового обслуживания, статистического анализа, мо дифицированным для нестационарных режимов методом асимптотического анализа марковизированных систем.
Научная новизна и результаты, выносимые на защиту, состоит в следую щем:
1. Предложена математическая модель сети ALOHA с обновлением остаточного времени обслуживания искаженной заявки.
2. Развита модификация асимптотического метода для исследования нестацио нарных режимов.
3. Построен диффузионный процесс, аппроксимирующий процесс изменений со стояний сети не только в окрестности среднего, но и во всей области изменения ее состояний.
4. Определено понятие времени стабильного функционирования неустойчивой се ти случайного доступа, найдено явное выражение его среднего значения, и пока зано, что оно является достаточно большим, существенно превосходящим время существования любой реальной компьютерной сети связи.
5. Найдено распределение значений процесса глобальной аппроксимации в области стабильного функционирования.
6. Получены основные вероятностно-временные характеристики неустойчивых се тей случайного доступа.
Теоретическая ценность работы. Развиты аналитические методы массового обслуживания. Построены и исследованы математические модели неустойчивых се тей связи случайного доступа. Предложена модификация метода асимптотического анализа для нестационарных режимов.
Практическая ценность работы. Приведенные в диссертации результаты мо гут быть применены для выбора сетевого оборудования при проектировании новых сетей связи, для анализа функционирования уже существующих сетей, а также для нахождения их вероятностных характеристик и оценки важных параметров сетей.
Апробация работы. Основные результаты диссертации докладывались и об суждались на:
1. Всероссийской научно-практической конференции «Новые технологии и ком плексные решения: наука, образование, производство» (г. Анжеро-Судженск, 2001 г.) 2. IV Всероссийской конференции «Новые информационные технологии в иссле довании сложных структур» (г. Томск, 2002 г.) 3. Всероссийской научно-практической конференции «Информационные техно логии и математическое моделирование» (г. Томск, 2002 г.) 4. XLI международной научной студенческой конференции “Студент и научно технический прогресс” (г. Новосибирск, 2003 г.) 5. II Сибирской научной школы-семинара с международным участием “Проблемы компьютерной безопасности и криптография” (г. Томск, 2003 г.) 6. Всероссийской научно-практической конференции «Информационные техно логии и математическое моделирование» (г. Анжеро-Судженск) 7. На научных семинарах кафедры ТВиМС факультета прикладной математики и кибернетики Томского государственного университета.
Публикации. По результатам выполненных исследований было опубликовано десять научных работ, в том числе две статьи в академическом журнале, входящем в список ВАК.
Структура и объем диссертации. Диссертация состоит из введения, трех глав, заключения и списка литературы. Объем диссертации составляет 128 страниц, в том числе: титульный лист – 1 стр., оглавление – 3 стр., основной текст – 110 стр., библиография из 105 наименований – 12 стр.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, изложены цель исследования, на учная новизна, теоретическая и практическая ценность результатов, методика ис следования, сделан обзор литературы.
Сети связи случайного доступа будем называть неустойчивыми, если для их математических моделей не существует стационарного режима.
В первой главе в качестве математической модели сети случайного доступа Ethernet рассмотрим однолинейную марковскую систему массового обслуживания с источником повторных вызовов (ИПВ). Состояние системы в момент времени t оп ределим вектором {i(t ), k (t )}, где i(t ) – число заявок в источнике повторных вызовов, а k (t ) – состояния прибора, Pk (i, t ) = = P(k (t ) = k, i (t ) = i ) – вероятностей того, что в момент времени t прибор находится в состоянии k, а в ИПВ – i заявок. Тогда распределе ние Pk (i, t ) будет удовлетворять следующим уравнениям Колмогорова P0 (i, t ) 1 + ( + i ) P0 (i, t ) = P2 (i, t ) + Pc (i, t ), t a P (i, t ) + ( + i + 1) P (i, t ) = P0 (i, t ) + (i + 1) P0 (i + 1, t ), t P2 (i, t ) + + P2 (i, t ) = P (i, t ) + P2 (i 1, t ), t Pc (i, t ) + + Pc (i, t ) = P (i 2, t ) + Pc (i 1, t ) + (i 1) P (i,1, t ). (1) 1 t a Известно, что для построенной математической модели не существует стацио нарных режимов, т.е. пропускная способность сети равна нулю, а время доставки сообщения увеличивается неограниченно по мере того, как система продолжает ра ботать. В этом смысле рассматриваемая сеть связи неустойчива.
Для решения нестационарной системы (1) воспользуемся модифицированным методом асимптотического анализа марковских систем в условиях большой задерж ки 0.
Рассмотрим процесс x() = lim i( ), который имеет смысл асимптотического среднего нормированного числа заявок в ИВП.
i(t ) Теорема 1.1 Процесс (2) x() = lim i ( ) является детерминированной функцией, удовлетворяющей дифференциальному уравнению x() = R1( x()), (3) где + x.
R1 ( x) = a ( + x) + (2 + )( + x) + В ходе доказательства были найдены величины, которые являются вероятностями состояний канала + x +1 + x, R1 ( x) =, R0 ( x) = a( + x) + (2 + )( + x) + 1 a ( + x) + (2 + )( + x) + 2 ( + x) a( + x), Rс ( x) =. (4) R2 ( x) = a ( + x) 2 + (2 + )( + x) + 1 a ( + x) 2 + (2 + )( + x) + В диссертации показано, что если уравнение (3) имеет 2 точки покоя, x1 x2, то является устойчивой, а x2 неустойчивой точками покоя. Устойчивую точку покоя x x1 дифференциального уравнения (3) будем называть точкой стабилизации сети свя зи.
Для более точного исследования процесса изменения состояний математиче ской модели сети Ethernet построим случайный процесс, аппроксимирующий значе ния величины отклонений нормированного числа заявок от асимптотического сред него 2i ( 2 ) x(), (5) y () = lim где x() определяется уравнением (3). Этот процесс будем называть локальной ап проксимацией процесса изменения состояний математической модели сети Ethernet.
Теорема 1.2 Процесс y() является диффузионным процессом авторегрессии с коэффициентом переноса y b(), где ( R0 R1 ) (6) b() = aR1 R + x и коэффициентом диффузии {xR0 + ( R2 + Rc ) + (4 + x) R1} x R0 + B 2 () = + x + [R2 + a (Rc + ( x + 2) R1 )], (7) где величины R0, R1, R2 и Rc определены в соотношении (4).
Следствие 1.1 Процесс y() является решением стохастического дифференциально го уравнения dy () = b() y ()d + B ()dw(), (8) причем его решение можно представить в явном виде u b ( s ) ds b ( s ) ds dw(u ).
y0 + B(u )e y () = e 0 Для того чтобы аппроксимировать процесс изменения состояний сети, не толь ко в окрестности среднего, но и во всей области изменения ее состояний, введем в рассмотрение процесс u () = x() + y (), (9) где x() определяется уравнением (3), а y() уравнением (8).
Теорема 1.3 Случайный процесс u () с точностью до бесконечной малой более высокого порядка, чем, удовлетворяет стохастическому дифференциальному уравнению du () = { f (u )}d + B (u )dw(), (10) +u где, (11) f (u ) = a( + u ) + (2 + )( + u ) + а B (u ) определяется равенством (7).
Из (10) следует, что u () является однородным диффузионным случайным про цессом с коэффициентом переноса f (u ) и коэффициентом диффузии 2 B 2 (u ). Коэф фициенты переноса и диффузии будут зависеть от текущего состояния процесса.
Назовем этот процесс глобальной аппроксимацией процесса 2i(t ) изменения состоя ний системы массового обслуживания.
Рассмотрим интервал времени от момента до момента достижения процессом u () состояния u2 = x2. Его длину обозначим T (). Условное среднее значение величи ны T (), при условии u () = u, обозначим E (u ) = M {T () | u () = u}, (12) Средним временем стабильного функционирования сети случайного доступа назовем E (u1 ), т.е. среднее значение длины интервала от момента, когда процесс u () = u1, т.е. находится в точке стабилизации, до момента его выхода на границу u2, области устойчивого функционирования.
Теорема 1.4 Среднее значение времени стабильного функционирования имеет вид 2 s f ( + x) u2 s 2. (13) B ( y) y B 2 ( x) dxdyds exp E (u1 ) = 2 u1 Так как время достижения процессом u () состояния u2 может быть достаточно большим, то в течение этого времени распределение вероятностей p(u ) = P{u u () u + du | u () u2 } du (14) его значений не меняется с течением времени, поэтому его назовем распределением вероятностей значений процесса u () в режиме стабильного функционирования.
Теорема 1.5 Плотность распределения значений процесса u () в режиме ста бильного функционирования имеет вид u 2 y f ( x) B (u ) exp 2 2 dxdy z B ( x), (15) p(u ) = u u u2 2 f ( x) 2 y B 2 (u) exp 2 z B 2 ( x) dxdy du u где f (x ), B (x) определяются равенствами (11) и (7) соответственно.
Во второй главе рассмотрим немарковскую систему массового обслуживания с источником повторных вызовов. Определим состояние СМО в момент времени t вектором {k (t ), i(t )}, где i(t ) – число запросов в ИВП, а k (t ) – состояние канала, здесь. В силу произвольности функций распределения Bk (x) случайный процесс {k (t ), i(t )} не марковский. Для исследования процесса {k (t ), i(t )}, введем компоненту z (t ) равную длине интервала от момента t до момента окончания текущего состояния канала, когда k (t ) = 1, 2 или c, тогда случайный процесс {k (t ), i(t ), z (t )} является марковским. От метим, что если k (t ) = 0, то компонента z (t ) не определяется.
Обозначим P0 (i, t ) = P (k (t ) = 0, i (t ) = i ), Pk (i, z, t ) = P(k (t ) = k, i (t ) = i, z (t ) z ), k = 1, 2, c, распределение вероятностей того, что в момент времени t прибор находится в со стоянии k, в ИПВ – i заявок и если k = 1, 2, c, до момента окончания текущего состоя ния меньше времени меньше, чем z. Распределение Pk (i, z, t ) удовлетворяет системе уравнений Колмогорова P0 (i, t ) P (i,0, t ) Pc (i,0, t ), + ( + i ) P0 (i, t ) = 2 + t z z P (i, z, t ) P (i, z, t ) P (i,0, t ) + ( + i ) P (i, z, t ) = 1 + 1 t z z +B1 ( z ) P0 (i, t ) + (i + 1) B1 ( z ) P0 (i + 1, t ), P2 (i, z, t ) P (i, z, t ) P2 (i,0, t ) + P2 (i, z, t ) = 2 + t z z P (i,0, t ) + P2 (i 1, z, t ), + B2 ( z ) z Pc (i, z, t ) P (i, z, t ) Pc (i,0, t ) + Pc (i, z, t ) = c + t z z +Bc ( z ) P (i 2,, t ) + (i 1) Bc ( z ) P (i 1,, t ) + Pc (i 1, z, t ). (16) 1 Pk (i,0, t ) Pk (i, z, t ) Здесь и P (i,, t ) = P (i, z, t ) z =.
= 1 z z z = Для решения системы (16) воспользуемся модифицированным методом асимптоти ческого анализа в условиях большой задержки 0.
Рассмотрим процесс x() = lim i( ), который имеет смысл асимптотического среднего нормированного числа заявок в ИВП.
i(t ) Теорема 2.1 Процесс (17) x() = lim i ( ) является детерминированной функцией, удовлетворяющей дифференциальному уравнению x() = ( + x)( R0 R1 ), (18) где, R0 = 2 B ( x) + b2 ( + x) B ( x) + bc ( + x)(1 B ( x)) * * * 1 B* ( x).
R1 = 2 B ( x) + b2 ( + x) B* ( x) + bc ( + x)(1 B* ( x)) * Здесь и среднее значение времени передачи и времени оповещения о конфлик b2 bc те, а B* ( x) = ( + x) B1 ( s )e (+ x ) s ds.
В ходе доказательства теоремы были найдены вероятности распределения со стояний канала, R0 = 2 B ( x) + b2 ( + x) B ( x) + bc ( + x)(1 B ( x)) * * * 1 B* ( x), R1 = 2 B ( x) + b2 ( + x) B* ( x) + bc ( + x)(1 B* ( x)) * b2 ( + x) B* ( x), R2 = 2 B* ( x) + b2 ( + x) B* ( x) + bc ( + x)(1 B* ( x)) bc ( + x)(1 B* ( x)). (19) Rc = 2 B* ( x) + b2 ( + x) B* ( x) + bc ( + x)(1 B* ( x)) Для более точного исследования процесса изменения состояний немарковской модели сети Ethernet построим случайный процесс, аппроксимирующий значения величины отклонений нормированного числа заявок от асимптотического среднего 2i ( 2 ) x(), (20) y () = lim где x() определяется уравнением (18). Этот процесс будем называть локальной ап проксимацией процесса изменения состояний математической модели сети Ethernet.
Теорема 2.2 Процесс y() является диффузионным процессом авторегрессии с коэффициентом переноса y b(), где b() = R1 (1 + F * ( x)) R0 + ( + x)( R0 R1 ) F * ( x) + b2 ( R0 B* ( x) R1F * ( x)) + bc R1 (1 + F * ( x)), R + x и коэффициентом диффузии [ ] B 2 () = xR0 + ( R2 + Rс ) 2 R1 (1 F * ( x)) x() + x + (4 + x) R1 + [ ]+ (1 F ( x)) x() + x * + 2( x() ) R1 +b2 x() R1F * ( x) + xB* ( x) R + x [ ] + bc R1 (1 F * ( x)) x() 2 + ( x() )[R2 f 2 + Rc f c ], (21) где величины R0, R1, R2 и Rc определены в соотношении (19), f 2 и fc – среднее оста точное время передачи и оповещения о конфликте соответственно, а F * ( x) = ( + x) e ( + x ) F1 ( s)ds.
Следствие 2.1 Процесс является решением стохастического дифференци y () ального уравнения dy () = b() y ()d + B ()dw(), (22) причем его решение можно представить в явном виде u b ( s ) ds b ( s ) ds dw(u ).
y0 + B(u )e y () = e 0 Для того чтобы аппроксимировать процесс изменения состояний сети, не толь ко в окрестности среднего, но и во всей области изменения ее состояний, введем в рассмотрение процесс u () = x() + y (), (23) где x() определяется уравнением (18), а y() уравнением (22).
Теорема 2.3 Случайный процесс u () с точностью до бесконечной малой более высокого порядка, чем, удовлетворяет стохастическому дифференциальному уравнению du () = { f ( + u )}d + B(u )dw(), (24) ( + x) B * (u ) где, (25) f (u ) = 2 B * (u ) + b2 ( + u ) B * (u ) + bc ( + u )(1 B * (u )) а B (u ) определяется равенством (21).
Из (23) следует, что u () является однородным диффузионным случайным про цессом с коэффициентом переноса f (u ) и коэффициентом диффузии 2 B 2 (u ). Коэф фициенты переноса и диффузии будут зависеть от текущего состояния процесса u ().
Назовем этот процесс глобальной аппроксимацией процесса 2i(t ) изменения состоя ний системы массового обслуживания.
Рассмотрим интервал времени от момента до момента достижения процессом u () состояния u2 = x2. Его длину обозначим T (). Условное среднее значение величи ны T (), при условии u () = u, обозначим E (u ) = M {T () | u () = u}, (26) Средним временем стабильного функционирования сети случайного доступа назовем E (u1 ), т.е. среднее значение длины интервала от момента, когда процесс u () = u1, т.е. процесс находится в точке стабилизации, до момента его выхода на гра ницу u2, области устойчивого функционирования.
Для среднего времени стабильного функционирования можно доказать теорему аналогичную теоремы 1.4, т.е. найти его в явном виде.
В качества примера рассмотрим ситуацию, когда = 0.1. Пусть время резервиро вания детерминировано и равно 1, время передачи равномерно распределено в ин тервале [5, 15], а время распространения сигнала оповещения о конфликте также равномерно распределено, но в интервале [0, 4].
Здесь единица времени равна времени резервирования, которое в 10 раз меньше времени передачи сообщения.
Рассмотрим сеть, канал связи которой имеет скорость передачи 10 Мбит/сек.
Будем полагать, что средняя длина сообщения составляет 10 кбит, тогда среднее время передачи одного сообщения равна 1мсек = 103 сек. Следовательно, рассматри ваемая единица времени равна 104 сек 1. Пусть = 0.06, тогда u1 = 0.2, а величина E (u1 ) E (u1 ) = 1.42 103 104 = 0,142 сек.
2. Если = 0.055, то u1 = 0.125, тогда E (u1 ) = 2.15 106 104 = 2.15 102 = 215 сек.
3. Если = 0.05, то u1 = 0.08, тогда E (u1 ) = 1.38 1014 10 4 = 1.38 1010 сек = 440 лет.
Получили, что при значениях параметра 0.05, сеть функционирует стабильно практически неограниченный срок.
Так как время достижения процессом u () состояния u2 может быть достаточно большим, то в течение этого времени распределение вероятностей p(u ) = P{u u () u + du | u () u2 } du (27) его значений не меняется с течением времени, поэтому его назовем распределением вероятностей значений процесса u () в режиме стабильного функционирования.
Аналогично теоремы 1.5 найдена эта плотность распределения. Графики плот ности при = 0.055 и = 0.050 приведены на рисунке 1 и 2 соответственно 6. 5. 4. 4. 3. p( u) 2. 2. 1. 0. 0 0.062 0.12 0.19 0.25 0.31 0.37 0.43 0.5 0.56 0. u Рис. p( u) 0 0.04 0.08 0.12 0.16 0.2 0.24 0.28 0.32 0.36 0. u Рис. В третьей главе рассмотрим сети связи случайного доступа с протоколом ALOHA. В качестве математической модели возьмем систему массового обслужи вания с источником повторных вызовов. На вход СМО поступает простейший поток запросов с параметром. Если канал свободен, осуществляется передача запроса, продолжительность которого имеет функцию распределения B(x). Если в момент по ступления запроса, канал занят передачей другого, оба запроса попадают в кон фликт и один из них, у которого время остаточного или полного обслуживания больше, остается на приборе и продолжает обслуживаться в искаженном виде, а второй переходит в ИПВ. По завершению этапа обслуживания искаженного запроса канал вновь становится свободным, а запрос переходит в ИПВ. После случайной за держки запросов в ИПВ, время которой распределено экспоненциально с парамет ром одинаковым для всех запросов, они вновь обращаются к каналу для повтор ных попыток передачи.
Состояние системы массового обслуживания в момент времени t определим векто ром {k (t ), i(t )}, где i(t ) – число запросов в ИВП, а k (t ) – состояние канала, здесь k (t ) = 0, если канал свободен;
k (t ) = 1, если канал занят обслуживанием неискаженного запро са, k (t ) = 2 – канал занят обслуживанием искаженного запроса. В силу произвольно сти функции распределения B(x) случайный процесс {k (t ), i(t )} немарковский. Для ис следования процесса {k (t ), i(t )}, введем компоненту z (t ) равную длине интервала от момента до момента окончания обслуживания запроса, тогда случайный процесс t {k (t ), i (t ), z (t )} является марковским. Отметим, что если k (t ) = 0, то компонента z (t ) не оп ределяется.
Обозначим P0 (i, t ) = P (k (t ) = k, i (t ) = i ), Pk (i, t, z ) = P(k (t ) = k, i (t ) = i, z (t ) z ), при k = 1, 2, вероятности того, что в момент времени t прибор находится в состоянии k, в ИПВ – i заявок и если k = 1, 2, до момента окончания обслуживания запроса меньше времени меньше, чем z.
Распределение Pk (i, z, t ) удовлетворяет системе уравнений Колмогорова P0 (i, t ) P (i,0, t ) P2 (i 1,0, t ), + ( + i ) P0 (i, t ) = 1 + t z z P (i, z, t ) P (i, z, t ) P (i,0, t ) + ( + i ) P (i, z, t ) = 1 1 + B( z ) P0 (i, t ) + t z z +(i + 1) B( z ) P0 (i + 1, t ), P2 (i, z, t ) P (i, z, t ) P2 (i,0, t ) + ( + i ) P2 (i, z, t ) = 2 + t z z + B ( z )(P (i 1, z, t ) + P2 (i 1, z, t ) ) + iB ( z )(P (i, z, t ) + P2 (i, z, t ) ).
(28) 1 Для решения системы (28) воспользуемся модифицированным методом асимптоти ческого анализа для нестационарных режимов в условиях большой задержки 0, т.е. среднее время обращения заявок из ИПВ гораздо больше среднего времени ме жду приходом заявок из входного потока.
Рассмотрим процесс x() = lim i( ), который имеет смысл асимптотического среднего нормированного числа заявок в ИВП.
i(t ) Теорема 3.1 Процесс (29) x() = lim i ( ) является детерминированной функцией, удовлетворяющей дифференциальному уравнению x() = ( + x)( R0 R1 ), (30) где, R0 = ( ) ( + x ) b 2 B ( + x) + ( + x) 1 B ( + x) e * * 1 B ( + x)*.
R1 = ( ) 2 B ( + x) + ( + x) 1 B* ( + x) e(+ x )b * Здесь s ( + x ) (1 B ( u ) )du {1 B( s) F1 (s)}ds, B* ( + x) = e (+ x ) s dB( + x), (31) 1 = e 0 { } z + x где e(+ x ) z e (+ x ) s B* ( + x) B( s ) ds F1 ( z ) = 1 B* ( + x) В ходе доказательства теоремы были найдены вероятности распределения со стояний канала, R0 = ( ) ( + x ) b 2 B ( + x) + ( + x) 1 B ( + x) e * * 1 B* ( + x), R1 = ( ) 2 B ( + x) + ( + x) 1 B* ( + x) e(+ x )b * ( ) ( + x) 1 B* ( + x) e( + x )b. (32) R2 = ( ) 2 B* ( + x) + ( + x) 1 B* ( + x) e(+ x ) b Для более точного исследования процесса изменения состояний немарковской модели сети Ethernet построим случайный процесс, аппроксимирующий значения величины отклонений нормированного числа заявок от асимптотического среднего 2i ( 2 ) x(), (33) y () = lim где x() определяется уравнением (18). Этот процесс будем называть локальной ап проксимацией процесса изменения состояний математической модели сети Ethernet.
Теорема 3.2 Процесс y() является диффузионным процессом авторегрессии с коэффициентом переноса y b(), где b() = R1F * ( x) R0 B* ( x) + ( + x)( R0 R1 ) R0 R (1 B* ( + x)) 1 (1 F * ( + x)) + + x + x s ( + x ) (1 B ( u )) du {1 F2 (s)}ds + R11 + R2 2, R2 e ( + x )b +e и коэффициентом диффузии B 2 () = xR0 + (2 + x) R1 (2 x() + 3) R { }+ 2 x() R1 (1 F * ( + x)) + xR0 (1 B* ( + x)) x() R1 xR + 2( x() ) + x (1 F ( + x)) + + x (1 B ( + x)) + * * s ( + x ) (1 B ( u )) du [1 F2 (s)]ds R11 + R2 2. (34) x() R2 e ( + x ) b +e Здесь величины R0, R1, R2 определены в соотношении (33), и 1 определены вы B * ( x) ше в (31), s ( + x ) (1 B ( u )) du [1 B( s) F2 ( s)]ds, F * ( x) = ( + x) e ( + x ) F1 ( s)ds, 2 = e 0 z s ( + x ) (1 B ( s ) )ds z ( + x ) (1 B ( u ) )du где {1 B( s) F1 ( s)}ds e F2 ( z ) = e 0 e ( + x ) b 1 Следствие 3.1 Процесс является решением стохастического дифференци y () ального уравнения dy () = b() y ()d + B ()dw(), (35) причем его решение имеет вид u b ( s ) ds b ( s ) ds dw(u ).
y0 + B(u )e y () = e 0 Для того чтобы аппроксимировать процесс изменения состояний сети, не толь ко в окрестности среднего, но и во всей области изменения ее состояний, введем в рассмотрение процесс u () = x() + y (), (36) где определяется уравнением (29), а y () уравнением (35).
x() Теорема 3.3 Случайный процесс u () с точностью до бесконечной малой более высокого порядка, чем, удовлетворяет стохастическому дифференциальному уравнению du () = { f ( + u )}d + B(u )dw(), (37) где ( + x) B * (u ), (38) f (u ) = ( ) 2 B ( + u ) + ( + u ) 1 B * ( + u ) e ( + x )b * а B (u ) определяется равенством (34).
Из (37) следует, что u () является однородным диффузионным случайным про цессом с коэффициентом переноса f (u ) и коэффициентом диффузии 2 B 2 (u ). Коэф фициенты переноса и диффузии будут зависеть от текущего состояния процесса u ().
Назовем этот процесс глобальной аппроксимацией процесса 2i(t ) изменения состоя ний системы массового обслуживания.
Рассмотрим интервал от момента до момента достижения процессом u () со стояния u2 = x2. Его длину обозначим T (). Условное среднее значение величины T (), при условии u () = u, обозначим E (u ) = M {T () | u () = u}, (39) Средним временем стабильного функционирования сети случайного доступа назовем E (u1 ), т.е. среднее значение длины интервала от момента, когда процесс u () = u1, т.е. находится в точке стабилизации, до момента его выхода на границу u2, области устойчивого функционирования.
Для среднего времени стабильного функционирования можно доказать теорему аналогичную теоремы 1.4, т.е. найти его в явном виде.
Так как время достижения процессом u () состояния u2 достаточно велико, то в течение этого времени распределение вероятностей p(u ) = P{u u () u + du | u () u2 } du (40) его значений не меняется с течением времени, поэтому его назовем распределением вероятностей значений процесса u () в режиме стабильного функционирования.
Аналогично теоремы 1.5 найдена плотность распределения.
В заключении приводятся основные результаты работы, заключенные в том, что в данной работе проведено исследование сетей связи случайного доступа с об щей средой передачи для нахождения вероятностно-временных характеристик, а также исследование функционирования неустойчивой сети случайного доступа во всей области изменения ее состояний.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Грибанова П.И., Назаров А.А. Исследование нестационарных режимов в сетях случайного доступа // Новые технологии и комплексные решения: наука, образо вание, производство. Материалы всероссийской научно-практической конферен ции. Часть II (Математика) – Кем.ГУ, 2001. – С.16-18.
2. Грибанова П.И., Назаров А.А. Исследование асимптотических средних характе ристик неустойчивых сетей связи// Вестник ТГУ, приложение №1. (Материалы IV Всероссийской конференции «Новые информационные технологии в иссле довании сложных структур»). – 2002. – С.29-34.
3. Грибанова П.И., Назаров А.А. Исследование немарковских моделей неустойчи вых сетей случайного доступа// Информационные технологии и математическое моделирование. Материалы Всероссийской научно-практической конференции.
Томск: Изд-во «Твердыня», 2002. С. – 184-187.
4. Коцюруба П.И. Исследование времени и распределения вероятностей стабильно го функционирования неустойчивой сети связи// Обработка данных и управление в сложных системах. Вып.5. Томск: Изд-во Том. ун-та, 2003. – С.67-77.
5. Коцюруба П.И. Исследование неустойчивых сетей связи случайного доступа с оповещением о конфликте// Студент и научно-технический прогресс. Материалы XLI международной научной студенческой конференции. Математика. Новосиб.
гос. Университет, 2003. – С.104-105.
6. Коцюруба П.И., Назаров А.А. Исследование асимптотических средних характе ристик немарковских моделей неустойчивых сетей случайного доступа// Про блемы передачи информации. – 2003. – №3. – С.77-88.
7. Коцюруба П.И. Исследование неустойчивой сети связи методом глобальной ап проксимации// Вестник ТГУ, приложение №6. (материалы II Сибирской научной школы-семинара с международным участием “Проблемы компьютерной безо пасности и криптография), 2003. – С. 245-249.
8. Коцюруба П.И. Численное исследование неустойчивой сети связи// Информаци онные технологии и математическое моделирование. Часть III. Материалы Все российской научно-практической конференции “Наука и практика: диалоги но вого века”. Томск: Твердыня, 2003г. – С.122-124.
9. Коцюруба П.И., Назаров А.А. Локальная диффузионная аппроксимация процесса изменения состояний неустойчивой сети случайного доступа в окрестности асимптотического среднего// Проблемы передачи информации. – 2004. – №1. – С.85-97.
10. Коцюруба П.И. Исследование асимптотических средних характеристик сети свя зи, управляемой протоколом ALOHA// Информационные технологии и матема тическое моделирование. Материалы Всероссийской научно-практической кон ференции. Томск: Изд-во «Твердыня», 2004. С. – 184-187.