Исследование стратегий контроля сигнала оповещения о конфликте в математических моделях сетей случайного доступа
На правах рукописи
Никитина Марина Анатольевна ИССЛЕДОВАНИЕ СТРАТЕГИЙ КОНТРОЛЯ СИГНАЛА ОПОВЕЩЕНИЯ О КОНФЛИКТЕ В МАТЕМАТИЧЕСКИХ МОДЕЛЯХ СЕТЕЙ СЛУЧАЙНОГО ДОСТУПА 05.13.18 – «Математическое моделирование, численные методы и комплексы программ»
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата физико-математических наук
Томск – 2003
Работа выполнена на кафедре теории вероятностей и математической ста тистики факультета прикладной математики и кибернетики Томского го сударственного университета
Научный консультант: доктор технических наук, профессор Назаров Анатолий Андреевич
Официальные оппоненты: доктор физико-математических наук, профессор Воробейчиков Сергей Эрикович, кандидат физико-математических наук, доцент Змеева Елена Евдокимовна
Ведущая организация:
Белорусский государственный университет (г. Минск)
Защита состоится:
18 декабря 2003 г. в 10.30 часов на заседании диссертационного совета Д 212.267.08 при Томском государственном университете по адресу:
634050, г. Томск, пр. Ленина, 36.
С диссертацией можно ознакомиться в научной библиотеке Томского го сударственного университета.
Автореферат разослан «_» ноября 2003г.
Ученый секретарь диссертационного совета, доктор технических наук, доцент А.В. Скворцов
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность проблемы.
Быстрое развитие систем сбора, обработки, хранения и передачи информации привели к появлению информационно-вычислительных се тей (ИВС).
Потребности в качественной и быстрой связи возрастают, поэтому постоянно ведется проектирование и усовершенствование информацион но-вычислительных сетей.
Использование вычислительных сетей открывает новые возможно сти, такие как, например, улучшение доступа к информации, разделение дорогостоящих ресурсов. Однако много проблем связано с транспорти ровкой сообщений по каналам связи. Основные задачи здесь – обеспече ние надежности (чтобы передаваемые данные не терялись и не искажа лись) и производительности (чтобы обмен данных происходил с прием лемыми задержками). В структуре общих затрат на вычислительную сеть расходы на решение этих вопросов составляют существенную часть.
Успешное развитие информационных технологий невозможно без теоретических исследований. Сложность и высокая стоимость современ ных ИВС требуют оценки производительности проектируемой сети или её пропускной способности.
Основным современным методом исследования сложных инфор мационных систем на всех стадиях их разработки, проверки и модерниза ции является моделирование. По результатам моделирования могут быть найдены условия устойчивого функционирования сети, определены ос новные характеристики и решены задачи, связанные с выбором опти мальных параметров и построением рациональной стратегии управления.
Исследование математических моделей сетей связи проведено в работах Бочарова П.П., Фалина Г.И., Степанова С.Н., Дудина А.Н., Клименок В.И., Назарова А.А., Хомичкова И.И., Рыкова В.В., Меликова А.З, Виш невского В.М., Одышева Ю.Д., Шохора С.Л., Туенбаевой А.Н, Кузнецова Д.Ю. и др.
Таким образом, данная работа, в которой находятся условия суще ствования стационарного режима и основные вероятностно-временные характеристики сетей связи, является актуальной.
Целью работы является исследование математических моделей се тей связи с протоколами случайного доступа для нахождения вероятност но-временных характеристик сетей связи с дискретным и непрерывным контролем сигнала оповещения о конфликте и для нахождения условий, при которых сети связи функционирует устойчиво.
Таким образом, были поставлены следующие задачи:
1. Построение математических моделей сетей связи с протокола ми случайного множественного доступа с дискретным и непрерывным контролем сигнала оповещения о конфликте.
2. Разработка методики нахождение условий существования или отсутствия стационарного режима для математических моделей таких сетей связи.
3. Исследование предложенных марковских и немарковских мо делей сетей связи случайного доступа с дискретным и непрерывным кон тролем сигнала оповещения о конфликте, функционирующих в стацио нарном режиме.
4. Определение вероятностно-временных характеристик иссле дуемых сетей связи.
Методика исследований.
Исследование математических моделей сетей связи случайного доступа проводилось с использованием методов теории вероятностей, теории случайных процессов, эргодических теорем, теории массового обслуживания, асимптотического анализа марковизируемых систем.
Научная новизна и результаты, выносимые на защиту, состоят в следующем:
1. Предложена математическая модель сети связи случайного дос тупа с непрерывной стратегией контроля сигнала оповещения о конфлик те в виде однолинейной системы массового обслуживания с источником повторных вызовов и очередью.
2. Разработана методика нахождения условий существования ста ционарного режима для цепей Маркова с неоднородным ленточным гра фом.
3. Показано применение этой методики для математических моде лей сетей связи с дискретным или непрерывным контролем сигнала опо вещения о конфликте и сети связи с протоколом Ethernet.
4. Предложен подход к доказательству отсутствия стационарных режимов для математических моделей сетей связи.
5. Развит метод асимптотического анализа марковских и немарков ских моделей сетей связи случайного доступа при непрерывном контроле сигнала оповещения о конфликте.
Теоретическая ценность работы.
Построены и исследованы математические модели сетей случайно го доступа с непрерывным и дискретным контролем сигнала оповещения о конфликте.
Практическая ценность работы.
Приведенные в работе результаты могут быть применены при про ектировании новых сетей связи, а также для анализа процессов функцио нирования существующих сетей.
Апробация работы.
Основные положения диссертации и отдельные ее результаты по мере их получения докладывались и обсуждались:
1. На Всероссийской научно-практической конференции “Новые технологии и комплексные решения: наука, образование, произ водство” (г. Анжеро-Судженск, 2001 г.).
2. На IV всероссийской конференции с международным участием “Новые информационные технологии в исследовании сложных структур” (г. Томск, 2002 г.).
3. На Всероссийской научно-практической конференции “ Наука и практика: диалоги нового века ” (г. Анжеро-Судженск, 2003 г.).
4. На научных семинарах кафедры ТВиМС факультета прикладной математики и кибернетики Томского государственного универ ситета 1998 – 2003 гг.
Публикации. По результатам выполненных исследований опубли ковано научных 9 работ.
Структура и объем диссертации. Диссертация состоит из введе ния, 3 глав, заключения и списка литературы из 108 наименований. Объем диссертации составляет 136 страниц, в том числе: основной текст – стр.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обоснована актуальность темы, изложены цель иссле дования, научная новизна, теоретическая и практическая ценность резуль татов, методика исследования, сделан обзор литературы.
В первой главе исследуются условия существования или отсутст вия стационарных режимов для математических моделей сетей случайно го доступа с дискретной или непрерывной стратегией контроля сигнала оповещения о конфликте и с протоколом Ethernet.
В качестве математической модели сети случайного доступа с кон тролем сигнала оповещения о конфликте рассмотрим однолинейную сис тему массового обслуживания (СМО), на вход которой поступает про стейший поток заявок с параметром. Если прибор свободен, поступаю щая заявка начинает обслуживаться. Время обслуживания, случайная ве личина, имеющая функцию распределения B (x). Если за это время дру гие требования не поступают, то заявка, завершив обслуживание, покида ет систему. Если во время обслуживания поступает другая заявка, то воз никает конфликт. Все заявки, попавшие в конфликт, переходят в источник повторных вызовов (ИПВ). В ИПВ каждая заявка находится случайное время, распределенное по экспоненциальному закону с параметром, по завершении которого она вновь обращается к прибору для повторной по пытки обслуживания. На приборе начинается этап оповещения о кон фликте, продолжительность которого есть случайная величина с функци ей распределения A(x).
В случае дискретного контроля сигнала оповещения все заявки, по ступающие в систему на этапе оповещения о конфликте, переходят в ис точник повторных вызовов. Так как повторные обращения происходят в дискретные моменты времени, в которых определяется состояние канала, то эту ситуацию будем называть дискретным контролем сигнала опове щения о конфликте.
В случае непрерывного контроля все заявки, поступающие в систе му на этапе оповещения о конфликте, становятся в очередь. После его завершения, каждая заявка, находящаяся в очереди обращается к прибору.
В рассматриваемой ситуации момент окончания сигнала оповещения об наруживается мгновенно всеми заявками, находящимися в очереди, по этому такую ситуацию будем называть непрерывным контролем сигнала оповещения о конфликте. Если в очереди не было заявок, прибор остается свободным, если в очереди одна заявка, она начинает обслуживаться. Ес ли в очереди больше одной заявки, то все они попадают в конфликт и с вероятностью 1 уходят в ИПВ, а на приборе начинается этап оповещения о конфликте.
В марковских моделях функции распределения A(x) и B (x) явля ются экспоненциальными с параметрами µ1 и µ соответственно.
Для анализа условий эргодичности таких моделей рассмотрим цепь Маркова с дискретным временем, множество состояний которой опреде ляется двумерным вектором (k, i ), где k принимает значения из конечно го множества k = 1, K, а – i счетное. Такой марковский процесс будем называть цепью Маркова с ленточным графом. Функционирование цепи Маркова определяется не только структурой графа, но и вероятностями qn,i (k, j ) перехода за один шаг из состояния (n, i ) в состояние (k, j ).
Здесь мы будем рассматривать условия эргодичности для цепей Маркова с неоднородными ленточными графами, вероятности переходов qn,i (k, j ) которой имеют вид qn,i (k, j ) = qn,i (k, i + m) и удовлетворяют условиям: для любых n, i, k, m существуют конечные пределы lim qn,i (k, i + m) = qn (k, m). (1) i Пусть существуют следующие конечные пределы K lim m qn,i (k, i + m) = n, (2) i m= i k = lim qn,i (k, i + m) = qn (k ). (3) i m=i Матрица Q = {q n (k )} является стохастической матрицей для неко торой неприводимой, непериодической цепи Маркова с конечным числом состояний. Система уравнений K k = n q n (k ), k = 1, K n = относительно k имеет ограниченное ненулевое неотрицательное реше ние.
ТЕОРЕМА 1. Пусть вероятности переходов qn,i (k, j ) неприводи мой, непериодической марковской цепи с неоднородным ленточным гра фом удовлетворяют условию (1). Тогда для того чтобы эта цепь была эр годична, достаточно существования натурального i0 и набора неотрица тельных чисел xk (i ), имеющих вид xk (i) = Ai + Bk, таких, что K 0, для i i0, (4) n n n = K q (k, j ) xk ( j ), для i i0, n = 1, K. (5) n,i k =1 j = Данная теорема применяется для нахождения условий существова ния стационарных режимов в математических моделях сетей случайного доступа. Не менее полезным является метод доказательства отсутствия стационарных режимов для цепей Маркова. Возможный подход в этом направлении реализуется применением теоремы Пуанкаре Способ применения этой теоремы для доказательства отсутствия стационарного распределения цепи Маркова заключается в следующем.
Пусть цепь Маркова такова, что если бы для этого процесса существовало стационарное распределение, то оно бы удовлетворяло уравнению в ко нечных разностях вида 0 (i ) y (i + n) + 1 (i ) y (i + n 1) + K + n 1 (i ) y (i + 1) + n (i ) y (i ) = 0. (6) Если значение всех корней z p уравнения 0 z n + 1 z n1 + K + n 1 z + n = 0, (7) где s = lim s (i ), s = 0, 1, 2, K, n, таково, что соответствующие решения i y (i ) уравнения (6) не могут определять стационарное распределение ве роятностей, например, для решений y (i ) выполняется признак расходи мости Даламбера, тогда для рассматриваемой цепи Маркова не существу ет стационарных режимов.
При этом наиболее сложная ситуация возникает для решений y (i ), отвечающих корню z = 1. Рассмотрим этот случай более подробно для уравнения (6), в котором коэффициенты s (i ), при i, имеют вид s s (i ) = s + + o. (8) i i ЛЕММА. Если коэффициенты s (i ) уравнения (6) имеют вид (8), и z = 1 является корнем уравнения (7), то для решения y (i ) уравнения (6), удовлетворяющему условию y (i + 1) =1, lim y (i ) i имеет место равенство y (i + 1) = 1 + o, y (i ) i i n n (n s ) где = s.
s s =0 s = Данная лемма позволяет применять признак расходимости Раабе.
В диссертации рассматриваются четыре класса сетей случайного доступа: с 1-настойчивым доступом, с h1 -настойчивым доступом, с h2 настойчивым доступом и с протоколом Ethernet.
Рассмотрим вопрос отсутствия стационарного режима сети связи с протоколом 1-настойчивого доступа и непрерывным контролем сигнала оповещения о конфликте. Для этого состояние системы определим векто ром (k, i ), где k состояние прибора: 1) k = 0, прибор свободен, 2) k = 1, прибор занят обслуживанием заявки, 3) k = 20, на приборе реализуется сигнал оповещения о конфликте, и в очереди нет заявок, 4) k = 21, на приборе реализуется сигнал оповещения о конфликте и в очереди одна заявка, 5) k = 22, на приборе реализуется сигнал оповещения о конфликте и в очереди больше чем одна заявка, i – число заявок в системе.
Процесс {k (t ), i (t )} изменения во времени состояния системы явля ется цепью Маркова с непрерывным временем. Если бы для этого процес са существовало стационарное распределение вероятностей Pk (i ), то, по лагая =, µ = 1, µ1 =, для него можно было бы записать систему a уравнений:
( + i ) P0 (i ) = P1 (i + 1) + P20 (i ), a ( + (i 1) + 1) P1 (i ) = P0 (i 1) + iP0 (i ) + P21 (i ), a 1 + i + P20 (i ) = P1 (i 1) + (i 1) P1 (i ) + P22 (i ), a a + (i 1) + P21 (i ) = P20 (i 1) + iP20 (i ), a + P22 (i ) = P21 (i 1) + (i 1) P21 (i ) + P22 (i 1). (9) a ТЕОРЕМА 2. В марковской модели сети связи с непрерывным кон тролем сигнала оповещения о конфликте не существует стационарного режима.
В диссертации, используя сформулированную лемму, показано, что любое решение системы (9) не является стационарным распределением Далее рассмотрены марковские модели сети связи с протоколами h1-настойчивого доступа с дискретной или непрерывной стратегией кон троля сигнала оповещения о конфликте. В математической модели сети связи с протоколом h1-настойчивого доступа и дискретным контролем сигнала оповещения отличие заключается в том, что, если за время об служивания другие требования не поступают, то заявка, завершив обслу живание, покидает систему. Если во время обслуживания поступает дру гая заявка, то возникает конфликт. Каждая заявка, попавшая в конфликт, с вероятностью h1 переходит в ИПВ, и с вероятностью 1 h1 теряется. На приборе начинается этап оповещения о конфликте. Все заявки, поступив шие в систему на этапе оповещения о конфликте, с вероятностью 1 уходят в ИПВ.
Процесс {k (t ), i (t )} изменения во времени состояния системы явля ется цепью Маркова с непрерывным временем.
Построена вложенная цепь по моментам времени t n – моменты, непосредственно следующие за моментами изменения состояния прибора.
Получена цепь Маркова с дискретным временем, множество состояний которой определяется двумерным вектором (k, i ), и вероятностями qn,i (k, j ) – вероятности перехода за один шаг из состояния (n, i ) в со стояние (k, j ), которые имеют вид:
i q0,i (1, i ) = q0,i (1, i 1) =,, + i + i µ i q1, i (2, i 1) = (1 h1 ) q1, i (0, i ) =,, + i + µ + i + µ ih1 + 2h1 (1 h1 ) µ q1, i (2, i + 1) = q 2, i (0, i ) =,, + µ1 + i + µ i2h1 (1 h1 ) + (1 h1 ) q1, i (2, i ) =.
+ i + µ Из вида вероятностей перехода следует, что данная цепь неприво дима и непериодична.
2(1 h1 ) µ ТЕОРЕМА 3. При условии, где =, a =, в мар µ µ a ковской модели h1 - настойчивой сети связи с дискретным контролем сиг нала оповещения о конфликте существует стационарный режим.
Далее аналогично получены условия существования и отсутствия стационарных режимов для математических моделей других сетей.
ТЕОРЕМА 4. В марковской модели h1 -настойчивой сети связи с непрерывным контролем сигнала оповещения о конфликте не существует стационарного режима, если загрузка сети.
a ТЕОРЕМА 5. При условии h2 1, в марковской модели h2 настойчивой сети связи с непрерывным контролем сигнала оповещения о конфликте существует стационарный режим для любых значений пара метра.
ТЕОРЕМА 6. При условии h2 1 в марковской модели h2 настойчивой сети связи с дискретным контролем сигнала оповещения о конфликте существует стационарный режим для любых значений пара метра.
В качестве математической модели сети связи Ethernet рассмотрена однолинейная СМО, на вход которой поступает простейший с параметром поток заявок. Если прибор свободен, заявка начинает этап резервиро вания. Время резервирования распределено по экспоненциальному закону с параметром µ1. Если за это время другие требования не поступают, то начинается передача, продолжительность которой распределена по экспо ненциальному закону с параметром µ 2. Если во время передачи поступа ет другое сообщение, то оно переходит в ИПВ, не искажая исходной заяв ки. Завершив передачу, сообщение покидает систему. Если во время ре зервирования поступает другая заявка, то возникает конфликт. Все заявки, попавшие в конфликт, переходят в ИПВ. На приборе начинается этап оповещения о конфликте. Его продолжительность распределена по экспо ненциальному закону с параметром µ c. Все заявки, поступившие в сис тему на этапе оповещения о конфликте, поступают в ИПВ, где каждая заявка находится случайное время, распределенное по экспоненциально му закону с параметром.
Состояние системы определим вектором (k, i ), где 1) k состояние канала: k = 0, прибор свободен, k = 1, резервиро вание, k = 2, передача сообщения, k = c, в системе реализуется сигнал оповещения о конфликте, 2) i – число заявок в ИПВ.
Если бы для процесса {k (t ), i (t )} существовало стационарное рас пределение вероятностей Pk (i) = P{k (t ) = k, i (t ) = i}, тогда, полагая 1 =, µ1 = 1, µ 2 =, µ c =, для него можно было бы записать систему a уравнений 1 ( + i )P0 (i ) = P2 (i ) + Pc (i ), a ( + i + 1) P (i ) = P0 (i ) + (i + 1) P0 (i + 1), + P2 (i ) = P (i ) + P2 (i 1), + Pc (i ) = P (i 2) + (i 1) P (i 1) + P2 (i 1).
1 a Показано, что любое решение этой системы не может быть распре делением вероятностей, для этого используется теорема Пуанкаре.
ТЕОРЕМА 7. В сети связи с протоколом Ethernet не существует стационарного режима для любых значений загрузки сети.
Построена модифицированная модель протокола Ethernet с h настойчивым доступом. Здесь имеет место, следующее утверждение:
ТЕОРЕМА 8. При условии h 1, в сети связи h -настойчивый Ether net существует стационарный режим для любых значений параметра.
В этой главе проводится исследование условий существования ста ционарных режимов для немарковских моделей сетей связи В немарковской модели сети связи с h1-настойчивым протоколом доступа и дискретным контролем сигнала оповещения о конфликте веро ятности qn,i (k, j ) перехода за один шаг из состояния (n, i ) в состоя ние (k, j ) имеют вид q0,i (1, i ) = (i ), q0,i (1, i 1) = 1 (i ), q 2, i (0, i + m) = m, m = 0,1K q1, i (0, i ) = 0 (i ), q1, i (2, i 1) = (1 h1 ) 2 (i ), 2 q1, i (2, i + 2) = h1 1 (i ), q1, i (2, i ) = 2h1 (1 h1 ) 2 (i ) + (1 h1 ) 1 (i ), q1, i (2, i + 1) = h1 2 (i ) + 2h1 (1 h1 )1 (i ).
Здесь 0 (i ) = e ( +i )x dB( x), (i) =, + i i (1 0 (i) ), (1 0 (i) ), 1 (i ) = 2 (i ) = + i + i ( x ) m x m = e dA( x), m = 0,1,K 0 m!
2(1 h1 ) ТЕОРЕМА 9. При выполнении условия:, в немарков a ской модели h1 - настойчивой сети связи с дискретным контролем сигнала оповещения о конфликте существует стационарный режим, где a1 – сред нее время продолжительности сигнала оповещения о конфликте.
Аналогично доказано:
ТЕОРЕМА 10. При условии h2 1, в немарковской модели h2 настойчивой сети связи с дискретным контролем сигнала оповещения о конфликте существует стационарный режим для любых значений пара метра.
ТЕОРЕМА 11. При условии h2 1 в немарковской модели h2 настойчивой сети связи с непрерывным контролем сигнала оповещения о конфликте существует стационарный режим для любых значений пара метра.
Во второй главе проводится исследование марковских моделей для h2-настойчивых сетей связи случайного доступа с дискретным и не прерывным контролем сигнала оповещения о конфликте.
В качестве марковской модели h2 -настойчивой сети связи с дис кретным контролем сигнала оповещения предлагается однолинейная СМО, на вход которой поступает простейший поток заявок с параметром. Если прибор свободен, поступающая заявка начинает обслуживаться.
Время обслуживания распределено по экспоненциальному закону с пара метром µ. Если за это время другие требования не поступают, то заявка, завершив обслуживание, покидает систему. Если во время обслуживания поступает другая заявка, то возникает конфликт. Все заявки, попавшие в конфликт, переходят в ИПВ. На приборе начинается этап оповещения о конфликте, продолжительность которого распределена экспоненциально с параметром µ 1. Каждая заявка, поступившая в систему на этапе оповеще ния о конфликте, с вероятностью h2 переходит ИПВ, а с вероятностью (1 h2 ) теряется. В ИПВ заявка находится случайное время, распределен ное по экспоненциальному закону с параметром.
В марковской модели сети связи с h2 -настойчивым протоколом случайного доступа и непрерывным контролем сигнала оповещения о конфликте, в отличие от рассмотренного выше, если во время обслужива ния поступает другая заявка, то возникает конфликт. Каждая заявка, по павшая в конфликт, переходит в ИПВ с вероятностью 1. На приборе на чинается этап оповещения о конфликте. Все заявки, поступившие в сис тему на этапе оповещения о конфликте, становятся в очередь. После окончания этапа оповещения о конфликте, все заявки, находящиеся в оче реди обращаются к прибору. Если в очереди нет заявок прибор, остается свободным, если в очереди одна заявка, она начинает обслуживаться, если в очереди больше одной заявки, то каждая из них с вероятностью h2 ухо дит в ИПВ, а с вероятностью 1 h2 теряется. На приборе начинается этап оповещения о конфликте.
Для исследования математической модели сети связи с h2- настой чивым протоколом доступа и дискретным контролем сигнала оповещения о конфликте введем вероятности Pk (i, t ) = P{k (t ) = k, i (t ) = i}.
В диссертации показано, вероятности Pk (i ) удовлетворяют сле дующей системе разностных уравнений ( + i ) P0 (i ) = P (i ) + P2 (i ), a ( + i + 1) P (i ) = P0 (i ) + (i + 1) P0 (i + 1), h2 + (1 h2 )i + P2 (i ) = P (i 2) + (i 1) P (i 1) + 1 (10) a + h2 P2 (i 1) + (1 h2 )(i + 1) P2 (i + 1).
Проводится исследование системы (10) методом асимптотического анализа в условиях большой задержки ( 0). В диссертации доказаны следующие теоремы.
ТЕОРЕМА 12. Асимптотически при 0 среднее значение x нормированного числа заявок в ИПВ находится из уравнения G + (1 h2 )aG =, aG 2 + 2G + где G = x +.
Распределение вероятностей rk состояний канала имеет вид aG G +1 G r0 =, r1 =, r2 =.
aG 2 + 2G + 1 aG 2 + 2G + 1 aG 2 + 2G + ТЕОРЕМА 13. Асимптотически при 0 распределение вероят ностей состояний (k, i) определяется распределением вида k ( y ) = rk ( y ).
Функция ( y ) – распределение величины отклонения нормированного числа заявок в ИПВ от асимптотического среднего x имеет вид y ( y ) = exp, 2 2 2 2 1 (1 h2 )aG 2 (G + 2) aG (G + 2) ( + G ) 1 + (1 h2 )aG 2 = +, (aG 2 + 2G + 1)(G + 1) aG 2 + 2G + 2 (1 a) + G + (1 h2 )aG G + 2G + h2aG 1 = (G ) +.
aG 2 + 2G + 1 aG 2 + 2G + Для исследования сети связи с h2-настойчивым протоколом слу чайного доступа и непрерывным контролем сигнала оповещения о кон фликте состояние системы определяется вектором (k, i, j ), где k – со стояние канала, i – число заявок в ИПВ, если k = 2, то j – число заявок в очереди, если k 2, то компонента j не определяется.
Показано, что вероятности Pk, j (i ) удовлетворяют следующей сис теме разностных уравнений ( + i + 1) P1 (i ) = P0 (i ) + (i + 1) P0 (i + 1) + P2,1 (i ), a ( + i + ) P2,0 (i ) = P1 (i 2) + (i 1) P1 (i 1) + a 1i j ss + C j h2 (1 h2 ) j s P2, j (i s ), a j = 2s = ( + i + ) P2, j (i ) = P2, j 1 (i ) + (i + 1) P2, j 1 (i + 1), j 1.
a ТЕОРЕМА 14. Асимптотически при 0 среднее значение x нормированного числа заявок в ИПВ находится из уравнения (1 h )a 2 G 4 (2 + aG ) + G (1 + 2aG ) = 3 4 2 2 3.
a G + 2a G + 4aG 2 + 2aG + 2G + Распределение вероятностей rk состояний канала имеет вид G (1 + aG ) + 1 + 2aG r0 =, a 3G 4 + 2a 2G 3 + 4aG 2 + 2aG + 2G + G (1 + 2aG ) r1 =, a 3G 4 + 2a 2G 3 + 4aG 2 + 2aG + 2G + aG 2 (1 + aG ) =34, r2, a G + 2a G + 4aG 2 + 2aG + 2G + j aG 2 (1 + aG ) aG r2, j =, j 1.
1 + aG a G + 2a 2G 3 + 4aG 2 + 2aG + 2G + ТЕОРЕМА 15. Асимптотически при 0 распределение вероят ностей состояний (k, i) определяется распределением вида k ( y ) = rk ( y ), где функция ( y ) – распределение величины отклонения нормированного числа заявок в ИПВ от асимптотического среднего x имеет вид y ( y ) = exp.
2 2 2 2 Значения для s приведены в диссертации.
В третьей главе проводится исследование немарковских моделей сетей связи, управляемых h2-настойчивым протоколом случайного досту па, где B (x) – функция распределения времени обслуживания и A(x) – функция распределения времени распространения в системе сигнала опо вещения о конфликте.
Для исследования сети связи с дискретным контролем сигнала опо вещения, обозначим i – число заявок в ИПВ, k принимает значения:
k = 0, прибор свободен, k = 1, если он занят обслуживанием заявки и k = 2, в системе реализуется сигнал оповещения о конфликте.
Процесс {k (t ), i (t )} – немарковский. Для исследования математиче ской модели данной сети связи воспользуемся методом дополнительной переменной. Введем переменную z(t) – длина интервала от момента t до момента изменения текущего состояния канала. Процесс изменения со стояний системы {k (t ), i (t ), 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 0.
В диссертации показано, что вероятности состояний P0 (i ), Pk (i, z ), k = 1,2, удовлетворяют системе уравнений ( + i)P0 (i) = P1 (i,0) + P2 (i,0), z z ( + i)P1 (i, z ) = P1 (i, z ) P1 (i,0) + [P0 (i) + (i + 1)P0 (i + 1)]B( z ), z z P2 (i, z ) P2 (i,0) (h2 + (1 h2 )i)P2 (i, z ) = + h2 P2 (i 1, z ) + z z + (1 h2 )(i + 1)P2 (i + 1, z ) + (P (i 2) + (i 1)P (i 1) )A( z ).
1 Pk (i,0) Pk (i, z ) Здесь P1 (i ) = P1 (i, ), = z z z = Проводится исследование данной системы методом асимптотиче ского анализа в условиях большой задержки ( 0).
ТЕОРЕМА 16. Асимптотически при 0 среднее значение x нормированного числа заявок в ИПВ находится из уравнения (2 + h2G ), = G G 1 + + G где G G G = x +, = (1 B ( s ) )ds, = e (1 B() )d, = (1 A( s ) )ds, 0 Распределение вероятностей rk состояний канала имеет вид G r0 =, r1 =, r2 =.
1 + + G 1 + + G 1 + + G ТЕОРЕМА 17. Асимптотически при 0, распределение вероят ностей состояний (k, i) определяется распределением вида k ( y ) = rk ( y ).
Функция ( y ) – распределение величины отклонения нормирован ного числа заявок в ИПВ от асимптотического среднего x имеет вид y ( y ) = exp, 2 2 2 2 1 где значения для s приведены в диссертации.
Аналогично в диссертации проводится исследования сети связи с h2-настойчивым протоколом случайного доступа и непрерывным контро лем сигнала оповещения о конфликте асимптотически при 0. Нахо дятся среднее значение x нормированного числа заявок в ИПВ, распреде ление вероятностей rk состояний канала и функция ( y ) – распределение величины отклонения нормированного числа заявок в ИПВ от асимптотического среднего x.
Выпишем основные вероятностно-временные характеристики для сетей связи с дискретным и непрерывным контролем сигнала оповещения о конфликте:
1. Вероятность простоя канала для дискретного контроля:
r0 =, 1 + + G для непрерывного контроля:
1 G 2 + G 31 G 2 r0 =, 1 + G(1 G) + G 2 ( 1 ) 1 G G (1 A( x))dx, e (1 A( x) )dx.
где = 1 = e 2. Число заявок в ИПВ:
x + y i=, где плотность распределения вероятностей величин у определяется в со ответствующих теоремах.
3. Асимптотическое среднее значение x нормированного числа зая вок в ИПВ определяется уравнением для дискретного контроля:
(2 + h2G ), =G G 1 + + G для непрерывного контроля:
(1 h2 )G 3(G1 + ) + G (1 G + G 31 G 2 1 ), = 1 + G(1 G) + G 2 ( 1 ) где G = + x.
4. Среднее число заявок в ИПВ:
x I=.
5. Среднее время пребывания сообщения в сети:
I W=, здесь единицей времени служит среднее время передачи одного сообще ния.
6. Вероятность передачи сообщения с нулевым временем ожидания:
R0 = r0 P( ) = r0G e Gx B( x)dx, здесь – время передачи сообщения, а – длина интервала между мо ментами поступления сообщений в канал связи, тогда для дискретного контроля G e Gx B ( x)dx, R0 = 1 + + G для непрерывного контроля 1 G 2 + G 3 1 G 2 G e Gx B ( x )dx.
R0 = 1 + G(1 G) + G 2 ( 1 ) В заключение приводятся основные результаты работы.
В данной работе разработана методика, которая позволяет найти условия, при которых сеть функционирует устойчиво, в стационарном режиме, также предложен подход для доказательства отсутствия стацио нарного режима в математических моделях сетей связи случайного досту па. Исследуются марковские и немарковские модели сетей связи с прото колами случайного доступа с непрерывной и дискретной стратегией кон троля сигнала оповещения о конфликте методом асимптотического анали за в условиях большой задержки.
Полученные результаты дают новые возможности для нахожде ния вероятностно-временных характеристик сетей связи.
ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ 1. Назаров А.А., Никитина М.А. Сравнение стратегий контроля сиг нала оповещения о конфликте // Математическое моделирование.
Кибернетика. Информатика. Томск: Изд-во Томского ун-та, 1999. – С. 99-108.
2. Назаров А.А., Никитина М.А. Эргодичность цепей Маркова с не однородными ленточными графами и их применение к задачам анализа условий существования стационарных режимов в сетях связи с протоколами случайного множественного доступа // Стати ческая обработка данных и управление в сложных системах. Вып.
3. Томск: Изд-во Том. ун-та, 2001. – С. 101-109.
3. Назаров А.А., Никитина М.А. Исследование сети связи с h настойчивым протоколом случайного множественного доступа // Новые технологии и комплексные решения: наука, образование, производство. Материалы Всероссийской научно-практической конференции. Часть II (Математика). КемГУ, 2001. – С. 54-56.
4. Никитина М.А. Исследование немарковской модели сети связи, управляемой h2-настойчивым протоколом доступа с дискретным контролем оповещения о конфликте // Обработка данных и управ ление в сложных системах. Вып. 5. Томск: Изд-во Томского ун-та, 2003. – С. 136-143.
5. Никитина М.А. Исследование сети связи с h2-настойчивым прото колом доступа и дискретным контролем сигнала оповещения о конфликте // Вестник ТГУ, материалы научных конференций. – 2002. – С. 87-89.
6. Назаров А.А., Никитина М.А. Исследование условий существова ния стационарного режима в сетях связи c h-настойчивым досту пом // Вестник ТГУ. – 2002. – №275. – С. 191-198.
7. Назаров А.А., Никитина М.А. Применение условий эргодичности цепей Маркова к исследованию существования стационарных ре жимов в сетях связи // Автоматика и вычислительная техника. – 2003. – №1. – С. 59-66.
8. Никитина М.А. Исследование марковских моделей для h2 настойчивых сетей связи случайного доступа // Изв. Вузов. Физика.
– 2003. – №3. – С. 69-75.
9. Никитина М.А. Исследование немарковской модели h-настойчивой сети связи с непрерывным контролем сигнала оповещения о кон фликте // Наука и практика: диалоги нового века. (Материалы Все российской научно-практической конференции). КемГУ, 2003. – С.
34-37.