Содержание к диссертации
Введение
1 Обзор протоколов беспроводных сетей. Описание семейства протоколов IEEE 802.11. Аналитические методы исследования. Постановка задач диссертации 9
1.1 Беспроводные сети и их протоколы 9
1.2 Семейство протоколов ШЕЕ 802.11, архитектура, спецификации MAC и физического уровней 16
1.2.1 Семейство протоколов IEEE 802.11 16
1.2.2 Архитектура стандарта IEEE 802.11 21
1.2.3 Уровень управления доступом к среде (МАС-уровень) протокола IEEE 802.11 24
1.2.4 Физический (PHY) уровень протокола IEEE 802.11 32
1.3 Обзор методов аналитического исследования беспроводных сетей на базе протокола IEEE 802.11 и постановка задач 34
2 Оценка производительности локальных сетей при идеальном канале и произвольной нагрузке . 39
2.1 Марковская модель поведения сети однородных станций 39
2.2 Оценка показателей производительности 47
2.3 Случай неоднородных станций 51
3 Моделирование локальных сетей с учетом влияния помех 53
3.1 Модификация Марковской модели 53
3.2 Оценка производительности в условиях помех 61
4 Анализ взаимозависимости поведения станций локальной сети . 66
4.1 Описание иерархической модели 66
4.2 Оценка среднего времени задержки и вероятности отказа 71
4.3 Учет искажения пакетов из-за помех 73
4.4 Обобщение модели 76
4.5 Определение вероятностей для модели насыщенной сети 79
5 Численные результаты 83
5.1 Сравнение результатов численного и имитационного моделирования 83
5.2 Оптимизации RTS/CTS-предела для сети из однородных станций 86
5.3 Оценка влияния помех на характеристики работы сети 88
Заключение 94
Список литературы 96
- Беспроводные сети и их протоколы
- Марковская модель поведения сети однородных станций
- Модификация Марковской модели
- Описание иерархической модели
Введение к работе
Актуальность темы диссертации.
В настоящее время беспроводные сетевые технологии заняли прочное место в нашей жизни. Область их применения простирается от взаимодействия бытовых устройств на дистанции меньше метра (телефон и телефонная гарнитура и т.п.) до построения городских и региональных сетей, в которых расстояния между устройствами могут достигать десятков километров.
Введение новых, прогрессивных методов кодирования, модуляции и передачи информации дало беспроводным технологиям уникальные преимущества по сравнению с «обычными» проводными. Это и гибкость архитектуры и простота подключения, используемая в, так называемых, сетях типа «hot-spot», и отсутствие необходимости прокладывать медный или оптоволоконный кабель. Последнее преимущество особенно актуально для Российской Федерации, где есть удаленные и сельские регионы с невысокой плотностью населения и дорогостоящая прокладка кабеля экономически не выгодна. В то же время от решения проблемы «информационного неравенства» зависит информационная безопасность страны.
Изначально отсутствие общепринятых стандартов, и как следствие этого, несовместимость между собой оборудования различных производителей препятствовали широкому распространению беспроводных устройств. К настоящему времени эта проблема в целом решена. Разработан ряд международных стандартов, протоколов и рекомендаций (Bluetooth, DECT, IEEE 802.11 и т.д.), которые специфицируют физический уровень и МАС-уровень (уровень доступа к среде передачи) беспроводных сетей и обеспечивают эффективное управление доступом к беспроводной среде. Протокол IEEE 802.11, разработанный институтом IEEE (Institute of Electrical and Electronics Engineers) и утвержденный как международный стандарт в 1997 г., получил наибольшую популярность среди разработчиков беспроводных локальных сетей.
В связи со всем вышесказанным, актуальной является задача дальнейшей разработки фундаментальной теории в области передачи информации вообще,и разработки аналитических методов моделирования сетей, построенных с использованием протокола IEEE 802.11, в частности. Интенсивные работы в этом направлении ведутся как в нашей стране, так и за рубежом. Проблемам разработки математических моделей сетей передачи данных посвящено значительное количество работ. Среди наиболее известных работ, посвященных этим проблемам, следует отметить работы российских и зарубежных ученых: Г.П. Башарина, П.П. Бочарова, О.М. Брехова, В.А. Васенина, В.М. Вишневского, Р.Л. Добрушина, А.Н. Дудина, B.C. Жданова, Н.А. Кузнецова, В.В. Кульбы, Р.А. Минлоса, А.В. Печинкина, В.К. Попкова, В.В. Рыкова, С.Н. Степанова, G. Balbo, S.C. Bruell, L. Fratta, L. Kleinrock, M. Olivetty и др. Среди аналитических работ, посвященных исследованию протокола IEEE 802.11 и оценке производительности построенных на его базе беспроводных сетей, наиболее значимыми являются работы В.М. Вишневского, А.И. Ляхова, G. Bianchi, F. Cali, М. Conti, Е. Gregory, J. Weinmiller.
К сожалению, особенности локальных беспроводных сетей при оценке их производительности до сих пор недостаточно полно учтены. Полученные результаты оказываются неприменимы в условиях нормальной нагрузки, когда очереди станций периодически оказываются пустыми, ввиду существенного завышения оценок среднего времени обслуживания пакетов, и в условиях помех и искажений передаваемых пакетов. Таким образом, остаются не полностью исследованными следующие особенности функционирования локальных сетей под управлением протокола IEEE 802.11:
1) станция локальной беспроводной сети после передачи пакета и
при отсутствии пакета в очереди также переходит в состояние задержки;
возможность немедленной передачи пакета, пришедшего в пустую очередь, при отсутствии передач других станций;
возможность неудачной передачи из-за помех и искажения пакета;
4) взаимосвязанность поведения станций беспроводной сети.
Таким образом, целью диссертационной работы является разработка системы аналитических методов для исследования и моделирования локальных беспроводных сетей на базе протокола IEEE 802.11 при произвольном режиме нагрузки, оценки производительности беспроводных сетей и оптимизации параметров их функционирования.
Методы исследования.
В диссертационной работе используются методы теории вероятности, вычислительной математики, теории сетей связи, теории телетрафика и имитационного моделирования.
Научная новизна работы.
Существенно новыми результатами диссертации являются:
аналитическая модель локальных беспроводных сетей, функционирующих на базе протокола IEEE 802.11, позволяющая оценить их производительность при произвольном режиме нагрузки, детально учитывающая все основные особенности протокола;
расширения данной аналитической модели с целью учета влияния радиопомех и анализа беспроводных сетей с неоднородными станциями;
аналитическая модель учета взаимозависимости поведения станций локальных беспроводных сетей с протоколом IEEE 802.11;
алгоритмы оптимизации параметров протокола.
Практическая ценность и реализация результатов.
Результаты работы используются для оценки основных показателей производительности беспроводной локальной сети и оптимизации механизма передачи пакетов. В частности, на основе разработанных методов аналитического моделирования сетей с протоколом IEEE 802.11 может быть разработана система автоматической или полуавтоматической настройки
параметров протокола, позволяющая достигать оптимальных показателей производительности с учетом:
конфигурации сети;
интенсивности поступающего трафика;
- распределения пакетов;
интенсивности радиопомех и других факторов, влияющих на функционирование сети.
Основные теоретические положения и практические результаты работы были использованы при построении, выборе конфигурации и настройке параметров беспроводной сети архитектуры «хот-спот», функционирующей под управлением протокола IEEE 802.11 в Центре реабилитации Медицинского центра Управления делами Президента Российской Федерации.
Использование результатов диссертации позволило значительно снизить сроки проектирования и реализации беспроводной сети передачи информации и положительно сказалось на эффективности ее функционирования и эксплуатации.
Реализация результатов работы подтверждена соответствующим актом.
Апробация результатов работы:
Основные результаты диссертации докладывались и обсуждались на:
- Международном семинаре «Информационные сети, системы и
технологии» (ИССиТ-2004, Москва)
Международная научно-техническая конференция «Новые методологии проектирования изделий микроэлектроники» (НМП-2004, Владимир)
Международном семинаре «Distributed Computer and Communication Network (DCCN-2005)», София, Болгария
- Семинарах ИППИ РАН.
Основные публикации по теме диссертации.
По теме диссертации опубликовано 4 научных работы (из них 1 статья в ведущем научном журнале - [2] объемом 15 страниц; 3 - тезисы докладов на ведущих международных конференциях - [1], [3], [9] общим объемом 20 страниц). В совместных публикациях вклад соискателя состоит в разработке основных методов, построении моделей и получении численных результатов исследований.
Структура и объем диссертационной работы.
Диссертация состоит из введения, 5 глав, заключения и списка литературы, включающего 50 наименований. Работа изложена на 101 странице и содержит 21 рисунок и 1 таблицу.
Беспроводные сети и их протоколы
Беспроводные сетевые соединения - логическое развитие обычных, проводных, сетей. Всего несколько лет назад использование беспроводных сетей было ограничено отраслями, где рабочие должны были перемещаться в течении дня - к примеру, складские рабочие, использующие переносные устройства для инвентаризации, управления запасами и т.п. В настоящее время преимущества беспроводных сетей полностью осознаны, развитие в производстве оборудования сделало его более доступным, и использование беспроводных технологий получило широкое распространение. К преимуществам беспроводных технологий относят: гибкость архитектуры сети, когда обеспечивается возможность динамического изменения топологии сети при подключении, передвижении и отключении мобильных пользователей без значительных потерь времени; высокая скорость передачи информации (до 1 Гбит/с); быстрота проектирования и реализации, что критично при жестких требованиях к времени построения сети; высокая степень защиты от несанкционированного доступа; отказ от дорогостоящей прокладки или аренды оптоволоконного или медного кабеля. Таким образом, в настоящее время беспроводные персональные и локальные сети (WPAN - Wireless Personal Area Network и WLAN - Wireless Local Area Network) являются серьезной альтернативой проводным сетевым соединениям для огромного круга коммерческих потребителей. На стыке XX и XXI веков беспроводные сегменты сети достигли «критической массы», с которой начался их быстрый рост. Современные высокопроизводительные беспроводные сети предоставляют беспрецедентный уровень мобильности и производительности для различных компьютерных нужд. К примеру, пользователь переносного компьютера может оставаться подключенным к сети, в то время, как он перемещается по рабочей территории, легко подключаясь к ресурсам проводной сети. Сотрудники, находящиеся в командировке, могут иметь доступ к корпоративной сети находясь в зоне доступа аэропорта или отеля, значительно увеличивая производительность. В процессе сдвига использования беспроводных технологий от производственных сетей к их повсеместному развертыванию стоит отметить следующие моменты: - Стандартизация. Принятие ряда международных стандартов упростило создание сетевых устройств различными производителями, специфицировало их назначение и взаимодействие. Следует отметить этот огромный шаг в сравнении с изначальной ситуацией, когда могли взаимодействовать только друг другом исключительно устройства одного производителя. Ясно, что это являлось значительным препятствием распространению беспроводных сетей. Создание консорциумов и объединенных рабочих групп. Создание исследовательских групп было большим шагом, направленным на разработку современных конкурентоспособных беспроводных технологий. Ярким примером этого является созданный в 1998 г. SIG (Special Interest Group) - группа разработавшая технологию Bluetooth, вошедшую в стандарт IEEE 802.15.1 (опубликован 14 июня 2002 г.). Этот консорциум был создан ведущими производителями элементной базы, программного обеспечения, портативных компьютеров, сотовых телефонов и др., такими как IBM, Ericsson, Intel, Nokia и др. В настоящее время устройства, использующие Bluetooth, получили чрезвычайное распространение. Например, большинство современных сотовых телефонов имеют возможность подключения гарнитуры или соединения с персональным компьютером через Bluetooth. Развитие микроэлектроники. Современные беспроводные устройства легкие и компактные, не уступающие в производительности проводным аналогам, и достаточно мощные, чтобы поддерживать надежную связь на необходимой дистанции. Все это было достигнуто развитием микроэлектроники, сделавшей устройства с необходимыми характеристиками достаточно дешевыми для массового использования. Для четкого разделения областей применения беспроводных сетей передачи данных (БСПД) необходима их классификация. Остановимся на наиболее популярных способах ранжирования различных беспроводных систем. Обычно БСПД подразделяют [5]: по способу обработки первичной информации - на цифровые и аналоговые; по ширине полосы передачи - на узкополосные, широкополосные и сверхширокополосные; по локализации абонентов - на подвижные и фиксированные; по географической протяженности - на персональные, локальные, региональные (городские) и глобальные; по виду передаваемой информации - на системы передачи речи и данных.
Марковская модель поведения сети однородных станций
Исследуем БЛС, состоящую из N станций, в очередь каждой из которых поступает пуассоновский поток пакетов с одинаковой интенсивностью X, и одинаковым распределением D(lj) длин пакетов /,. Станции сети работают в распределенном режиме управления DCF. Кроме того, предполагается, что очередь пакетов станции может содержать не более В пакетов, пределы LuNs = т также одинаковы для всех станций, а время распространения сигнала пренебрежимо мало. Основная цель моделирования, проводимого в данном разделе - найти среднее значение времени обслуживания пакета Т, отсчитываемого от момента либо поступления пакета в пустую очередь данной станции, либо окончания обслуживания предыдущего пакета из этой очереди, и до момента либо получения подтверждения АСК, либо истечения интервала EIFS после последней неудачной попытки передачи (т.е. в случае потери пакета). Будем называть пакеты, передача которых начинается в момент поступления, переданными асинхронно, а все остальные - переданными синхронно. Асинхронная передача имеет место, если в момент прихода пакета станция была в состоянии простоя, и канал был свободен в течении как минимум DIFS или EIFS. Таким образом, асинхронная передача происходит только при отсутствии синхронных передач других станций, а так как Ша « 1, то можно считать, что за время одного слота задержки в сети может произойти не более одной асинхронной передачи. Следовательно, асинхронная передача всегда успешна. Для оценки времени Т построим модель поведения станции в виде цепи Маркова с дискретным целочисленным временем (см. рис. 2.1), единицей которого является виртуальный слот - промежуток времени между последовательным изменением счетчика задержки у каждой станции, не находящейся в состоянии простоя. Пусть b(t) - стохастический процесс изменения счетчика задержки для данной станции, времена /и t+l соответствуют началу двух последовательных виртуальных слотов, причем, станция передает, когда b(t) = 0. В тоже время, s(t) - стохастический процесс изменения стадии задержки 0, ..., т, расширенный значением -1 для ситуации, когда в очереди нет пакета. Заметим, что, исходя из принятой модели, эти времена не имеют прямого соответствия реальному времени, и виртуальные слоты неоднородны. Как уже было сказано, счетчик задержки «замораживается», если станция замечает передачу другой станции. Поэтому реальное время, прошедшее между t и М-1, больше слота задержки а, при наличии передачи другой станции. Таким образом, имеем 3 вида виртуальных слотов: а) «пустой» слот, во время которого ни одна станция не вела передачу, б) «успешный» слот, когда одна и только одна станция вела передачу, и в) «коллизионный» слот, во время которого произошла коллизия. Двумерный процесс {s(t), b(t)} описан цепью Маркова. Состоянию простоя станции соответствует состояние (-1, 0). Состояния, когда станция не имеет пакета для передачи, но выполняет процедуру задержки после удачной передачи или отказа - это (-1, l...W0-l). Наконец, состояния, когда станция имеет пакет и выполняет процедуру задержки - это все остальные (/, к), где к = 0, ..., W \ характеризует значение счетчика задержки, а і = 0, ..., т - стадию задержки. Пусть а(і, к) - стационарная вероятность состояния (/, к), а Р{іг, к2 ij, kj} - вероятность одношагового перехода из (/ /, к}) в ( , 2). Введем следующие обозначения: Р0 - вероятность опустошения очереди после завершения синхронного обслуживания. Ps - вероятность прихода хотя бы одного пакета за время виртуального слота, при условии, что очередь данной станции пуста. Очевидно, что эта вероятность включает в себя два компонента: Ps = PsF + PsE где PSF - вероятность прихода хотя бы одного пакета за время непустого слота, при условии, что очередь данной станции пуста. PSE - вероятность прихода хотя бы одного пакета за время пустого слота, при условии, что очередь данной станции пуста. Рт - вероятность прихода хотя бы одного пакета за время успешной передачи другого пакета. р - вероятность неудачной попытки передачи данной станции из-за, коллизии (вероятность коллизии). Как и в [15] считаем, что она не зависит от стадии задержки /. Определим возможные одношаговые переходы между состояниями и соответствующие им ненулевые вероятности переходов: P{i, k \ i, k+l} = І, і є (0, m), к є (0, Wr2), - уменьшение счетчика задержки. P{i, к /-1, 0} = plWh і є (1, m), к є (0, W, l), - неудачная попытка передачи и переход на следующую стадию задержки. Р{0, к /, 0} = (l-P0emws)(l-p)/W0, і є (0, m-1), к e (0,.ИЪ-1), - удачная передача, в очереди есть еще пакет(ы). Р{-1, к U 0} = Р0еЮШ\\-p)IW0, і є (0, m-\), к є (0, Wo-l), - удачная передача, в очереди нет пакетов. Р{0, к т, 0} = [(1- Р0еют)(\-р) + (1- Р0ешт)р]/Ж0, к є (0, W0-\), - последняя попытка передачи, после которой пакет удаляется из очереди;, в очереди есть еще пакет(ы). Р{-\, к т, 0} = P0[emiF\l-p) + emjFSp]/Wo, к є (0, Wrl), - последняя попытка передать пакет, в очереди больше нет пакетов.
Модификация Марковской модели
Как и во второй главе, мы исследуем БЛС, состоящую из N станций, в очередь каждой из которых поступает пуассоновский поток пакетов с интенсивностью Я и одинаковым распределением D(lj) длин пакетов /,-. Все пакеты передаются механизмом основного доступа. Очередь любой станции может содержать не более В пакетов. Передаваемые пакеты могут быть искажены помехами. Предполагается, что вносимые искажения статистически независимы, что имеет место, например, в случае канала с аддитивным гауссовым шумом [5]. Интенсивность помех (Bit Error Rate - BER) считается постоянной и не зависящей от расположения источника и получателя пакетов. Заметим, что в отличие от случая идеального канала, асинхронная передача может быть неудачной из-за искажения пакетов радиопомехами. Как и ранее, основная цель моделирования - найти среднее значение времени обслуживания пакета Г для каждой станции. Для оценки времени Т модифицируем модель на рис 2.1 и опишем поведение исследуемой станции цепью Маркова с дискретным целочисленным временем, изображенной на рис. 3.1. Как и ранее, единицей времени является виртуальный слот, a(i, к) -стационарная вероятность состояния (/, к), где к характеризует значение счетчика задержки, а / - стадию задержки, а Р{І2, //, к]} - вероятность одношагового перехода из (ij, kj) в ( ki). Пусть: Pj - вероятность прихода хотя бы одного пакета за время успешной асинхронной передачи другого пакета. qi - вероятность неудачи попытки передачи данной станции на стадии задержки / из-за искажения пакетов радиопомехами. Тогда вероятность неудачи передачи пакета на стадии / равна р. = 1 -(1 — р\{\ — дЛ, гдер - вероятность коллизии. Определим возможные одношаговые переходы между состояниями и соответствующие им ненулевые вероятности переходов, отличающиеся от модели на рис. 2.1: P{i, к /-1, 0} = Д.ч /Wt, і є (1, пі), к є (0, Wrl), - неудачная попытка передачи и переход на следующую стадию задержки. Р{0, к і, 0} = (1-Р0е-яо/га)(1- Д)/Ж0, / є (0, т-1), к є (0, W0- 1), - удачная передача, в очереди есть еще пакет(ы). Р{-1, к /, 0} - P0e-W!FS(l-pt)/W0, і є (0, т-\), к є (0, W0-l), - удачная передача, в очереди нет пакетов. Р{0,к\т, 0} = [(і_роЄ- )(і_рт) + (і_роЄ- ) ]/й/, к є (0, Wo-l), - последняя попытка передачи, после которой пакет удаляется из очереди;, в очереди есть еще пакет(ы). Р{-1, к т, 0} = P0[e-XDIFS(l-pm) + e-XEIFSpm]/W0, к є (0, Wo-l), - последняя попытка передать пакет, в очереди больше нет пакетов. Р{0, к -1, 0} = [Р/ + PSEPT\UO)WO, к є (0, Wo-l), -переход из состояния простоя в состояние задержки. Такой переход имеет место, если в момент прихода пакета среда была занята или в момент удачной асинхронной передачи пришел еще один пакет. Р{-\, к I -1, 0} = PsE(\-PTA)(\-q0yWo, к є (1, Wo-l), - переход соответствует удачной асинхронной передаче, после которой в очереди нет больше пакетов и счетчик Ь = к 0. Р{-\, 0 -1, 0} = l-Ps + PsE(l-PTA)(l-q0yWo -нет поступивших пакетов или имела место удачная асинхронная передача, за время которой не поступило больше пакетов и счетчик Ь = 0. Р{\, к -1, 0} = PsEqofWh к є (0, Wr\), - имела место асинхронная передача, неудачная из-за помех. (3.3) Для і = -I и к є (1, W0-\), т.е. состояний, соответствующих процедуре задержки после удачно переданного пакета или отказа, но при отсутствии пакета для передачи, из уравнения глобального баланса имеем
Описание иерархической модели
В предыдущих главах описывалась работа БЛС в условиях нормальной нагрузки. Однако, подход к моделированию, изложенный в этих главах, основан на допущении о статистической независимости поведения отдельных станций сети. Данное допущение, вполне применимое в случае высокой нагрузки, может привести к существенным погрешностям при оценке производительности сетей, работающих при нормальной нагрузке. В частности, если очередь одной станции непуста, то высока вероятность, что за время виртуального слота в очередь другой станции также поступит пакет. В данной главе предлагается другой подход, позволяющий учесть взаимозависимость поведения станций сети. Рассмотрим БЛС с протоколом IEEE 802.11 DCF, состоящую из N статистически однородных станций, в очередь каждой из которых поступает пуассоновский поток пакетов с интенсивностью Л. Пакеты одинаковы и передаются с помощью базового метода; канал считается идеальным, а время распространения сигнала между станциями - пренебрежимо малым. Кроме того, предполагается, что очередь пакетов каждой станции может содержать не более В пакетов. Цель моделирования - оценить следующие показатели производительности: - среднее значение Т времени задержки пакета, отсчитываемого от момента поступления пакета в очередь данной станции и до момента окончания его обслуживания, т.е. по окончании интервала DIFS, завершающего успешную передачу, или интервала EIFS в случае последней неудачной попытки передачи, приводящей к потере пакета; - вероятность отказа в передаче пакета, происходящего из-за либо переполнения очереди станции, либо истечения числа Ns = R повторных передач. Следуя подходу, предложенному Бьянки в [14] и использованному в предыдущих главах, разобьем все время работы сети на виртуальные слоты. Виртуальные слоты не одинаковы, и каждый из них может представлять из себя: 1) «пустой» слот отсрочки а, в котором ни одна из станций не ведет передачу; 2) «успешный» слот, в котором только одна из станций передает пакет синхронно; 3) «асинхронный» слот, в котором одна из станций передает пакет асинхронно; 4) «коллизионный» слот, в котором две или более станций пытаются осуществить передачу. Очевидно, вероятности этих слотов, обозначаемые соответственно Ре(п) Р,(п) Ра(п) и рс(п), зависят только от числа «активных» станций п, очереди которых непусты в начале данного виртуального слота. Опишем работу сети процессом рождения-гибели с дискретным временем (см. рис. 4.1), причем состояние этого процесса описывается суммарным числом пакетов, находящихся в очередях станций сети, включая передаваемые в данный момент пакеты, а единицей времени является виртуальный слот. На рис. 4.1 не показаны так называемые петли, то есть переходы в то же самое состояние (из в ). Для определения вероятностей рождения Д(), т.е. увеличения на 1 за слот, и гибели ju(), т.е. уменьшения на 1 за слот, введем следующие допущения. Допущение 1. В течение попытки передачи (включая завершающие ее интервалы DIFS или EIFS) в очереди станций может поступить не более одного пакета. Допущение 2. По завершении коллизии отказ в дальнейшей передаче пакета может произойти не более чем на одной из станций, вовлеченных в коллизию (вероятность одновременного отказа на двух и более станциях пренебрежимо мала). При = О рождение происходит, когда одна из станций передает асинхронно и во время этой успешной передачи, равное ts = - + tH +tACK +SIFS + DIFS, где IDATA длина пакета, в очередь этой или другой станции поступает еще один пакет. Таким образом, (0) = (1- )(1- -). При 0 рождение происходит, когда новый пакет поступает в непереполненную очередь либо во время пустого слота, либо во время асинхронной передачи, либо в течение коллизионного слота, в конце которого не происходит отказ в дальнейшей передаче пакета ни на одной из станций, вовлеченных в коллизию. Гибель происходит, когда в течение «успешного» слота или коллизии, приводящей к отказу в дальнейшей передаче пакета, не поступает новый пакет. Следовательно, при 0 В этих формулах: лтіп(Л =]( -1УЯ[+1, где ].[ - целая часть числа; у(п,1) - вероятность наличия п активных станций при условии, что сумма длины очередей в начале слота равна ; peq(n,) и Pq(n,) - вероятность потери из-за переполнения очереди, которая была непустой в начале слота и в которую поступает новый пакет, при данных п и ; эти вероятности различны для пустого слота (/??е) и для остальных слотов (pfq ), так как по определению в течение пустого слота пакеты могут поступать только в очереди активных станций; кроме того, очевидно, что эти вероятности равны 0 при п + В -1; Рт(п) - вероятность отказа из-за достижения предельного числа NS = R повторных передач при данном числе активных станций; здесь мы предполагаем, что счетчик ns только одной из станций, участвующих в коллизии, может достичь предела Ns; tc = -Ш4- + EIFS - время коллизии. Очевидно, стационарные вероятности л() состояний данного процесса описываются формулами: ю= о)П , (0)=і/{і+ЕП г1- (4.1) Для оценки вероятностей у(п,) и Р(п,) примем следующее допущение. Допущение 3. Пусть суммарное число пакетов, находящихся в очередях станций сети, равно 0. Тогда все варианты размещения этих пакетов по iV очередям сети равновероятны. Используя это допущение, находим для 0 NB и пш () п min( JV, ) : Г(п, ) = C?g[t -n,n,B-1], fif(n,) = 0 при п + В-1,апря n + B-l 1 K{e-n) к ttW = c H- T S -C"kg[-n-k(B-V),n-k,B-2]; кроме того, Peq(n,) определяется аналогично с заменой в последней формуле k/N на кіп. Здесь С„ =N\/[(N —«)!«!], a g[u,v,M] - число вариантов, которыми можно разместить и неразличимых шаров по v урнам так, что в любой урне было бы не более М шаров. kmia(,ri) = max[lJ-n(B-l)], а К(,п) -наибольшее целое, не превышающее отношения (-п)/(В-1). Функция g[u,v,M] вычисляется рекурсивно согласно [40]: g[0,v,M] = l Vv 0, g[w,l,M] = l при и М и g[w,l,M] = 0 при и М; т\п(иМ) g[u,v,M]= Г g[u-k,v-\,M] при v 2, и 0. Наконец, для нахождения вероятностей слотов и вероятности отказа jBm (ri) примем последнее допущение. Допущение 4. В начале данного виртуального слота число активных станций равно п. Тогда для любой из этих станций вероятность т(п) начала синхронной передачи, а также вероятность отказа Д,(«) в случае коллизии в этом слоте совпадают с соответствующими значениями, полученными для сети Sn, аналогичной исследуемой, но включающей в себя п постоянно активных станций. Остальные N-n станций в Sn могут передавать только асинхронно при условии, что ни одна из активных станций не передает. Если пакет поступает в очередь любой из N-n неактивных станций в момент передачи любой из станций, то этот пакет теряется.
