авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Исследование стратегий контроля сигнала оповещения о конфликте в математических моделях сетей случайного доступа

На правах рукописи

Никитина Марина Анатольевна ИССЛЕДОВАНИЕ СТРАТЕГИЙ КОНТРОЛЯ СИГНАЛА ОПОВЕЩЕНИЯ О КОНФЛИКТЕ В МАТЕМАТИЧЕСКИХ МОДЕЛЯХ СЕТЕЙ СЛУЧАЙНОГО ДОСТУПА 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.



 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.