автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.13, диссертация на тему:Анализ и оптимизация адаптивного централизованного управления в беспроводных широкополосных сетях передачи информации

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

Лаконцев Дмитрий Владимирович

Анализ и оптимизация адаптивного централизованного управления в беспроводных широкополосных сетях передачи информации.

Специальность 05 13 13 - Телекоммуникационные системы и компьютерные сети

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

Москва - 2007

003070963

Работа выполнена в Институте проблем передачи информации им А А

Харкевича РАН

Научный руководитель

доктор технических наук, профессор Вишневский Владимир Миронович

Официальные оппоненты

доктор технических наук, профессор Зяблов Виктор Васильевич доктор физико-математических наук, профессор

Рыков Владимир Васильевич

Ведущая организация

Институт программных систем РАН

Защита состоится 28 мая 2007 г в 11 часов на заседании диссертационного совета Д 002 077 01 при Институте проблем передачи информации им А А

Харкевича РАН

по адресу 127994, г Москва, ГСП-4, Большой Каретный пер , д 19

С диссертацией можно ознакомиться в библиотеке Института проблем передачи информации им А.А Харкевича РАН

Автореферат разослан 27 апреля 2007 г

Ученый секретарь

диссертационного совета Д 002 077 01, доктор физико-математических наук

И И Цитович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В последние годы беспроводные сети передачи данных заняли прочные позиции в повседневной жизни Сфера их применения простирается от обеспечения взаимодействия между бытовыми приборами (например, между телефоном и телефонной гарнитурой, компьютером и монитором и т д ) до построения сетей передачи мультимедийной информации городского и регионального масштаба Построение беспроводных сетей передачи данных регионального масштаба на обширных территориях (например, в удаленных сельских регионах Российской Федерации) является единственным экономически оправданным и наиболее перспективным решением проблемы так называемого «информационного неравенства» При создании беспроводных сетей передачи данных регионального масштаба все большее распространение получают устройства на базе технологий IEEE 802 11 (WiFi) Активный рост числа беспроводных региональных сетей выдвигает в ряд первоочередных задач разработку методов оптимизации их работы, разработку новых алгоритмов функционирования таких сетей, а также оценку их производительности Проблемам разработки математических моделей сетей передачи данных посвящено значительное количество работ Среди наиболее известных работ, посвященных этим проблемам, следует отметить работы российских и зарубежных ученых О M Брехова, В А Васенина, В M Вишневского, В С Жданова, Р А Минлоса, А В Печинкина, В К Попкова, В В Рыкова, С H Степанова, G Balbo, S С Bruell, L Tratta, L Kleinrock, M Olivetty, H Takagi, S С Borst, О J Boxma и др Среди аналитических работ, посвященных исследованию протоколов 1ЕЕЕ 802 11 и IEEE 802 16 и оценке производительности построенных на их базе беспроводных сетей, наиболее значимыми являются работы В M Вишневского, А И Ляхова, G Blanchi, F Cali, M Conti, E Gregory,

] \Уеити11ег Особенности региональных беспроводных сетей при оценке их производительности достаточно полно отражены в ряде работ, однако недостатками этих работ является, слабое внимание, уделяемое механизмам адаптивного централизованного управления, хотя именно эти механизмы нацелены на решение основной проблемы региональных беспроводных сетей -проблемы «скрытых станций» Таким образом, задача анализа, разработки и оптимизации механизмов адаптивного динамического управления является одной из важнейших для развития беспроводных широкополосных региональных сетей передачи данных. Кроме этого, требуется разработать комплекс аналитических и имитационных моделей механизмов централизованного управления для получения адекватных оценок показателей производительности и оптимизации работы устройств широкополосной беспроводной региональной сети

В связи с этим, целью диссертационной работы является разработка механизмов адаптивного динамического централизованного управления в широкополосных беспроводных региональных сетях передачи информации, а также исследование и оптимизация этих механизмов с помощью комплекса аналитических и имитационных моделей

Методы исследования. Для достижения поставленной цели, в диссертационной работе используются методы теории вероятности, теории массового обслуживания и имитационного моделирования

Научная новизна:

впервые разработан комплекс аналитических моделей, адекватно описывающих функционирование широкополосных беспроводных сетей с централизованным управлением,

разработан комплекс имитационных моделей адаптивного динамического централизованного управления в широкополосных беспроводных сетях функционирующих под управлением семейства протоколов IEEE 802 11, на базе разработанного комплекса аналитических и имитационных моделей получены оптимальные параметры механизмов адаптивною централизованного управления в широкополосных беспроводных региональных сетях,

предложены методы минимизации накладных расходов в работе беспроводных сетей с адаптивным динамическим централизованным управлением

Практическая ценность и реализация результатов Результаты работы внедрены и используются на практике, что подтверждено соответствующими актами Изученные и предложенные механизмы адаптивного централизованного управления реализованы в радиомаршрутизаторе РЭС «Рапира», который был разработан ИППИ РАН в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям развития науки и техники» на 2002-2006 годы по Государственному контракту № 02 477 11 1003 «Разработка технологии создания нового поколения широкополосных телекоммуникационных средств комплектации беспроводных систем передачи данных, голоса и информации» Радиомаршрутизатор РЭС «Рапира» используется в качестве базового устройства в ряде широкополосных беспроводных региональных сетей, в том числе в сети RadioNet ИППИ РАН, в беспроводной локальной вычислительной сети ИППИ РАН, в беспроводной сети ООО «Уникомпорт», в беспроводной сети ЗАО «НТЦ ФИОРД» и т д РЭС «Рапира» более года успешно работает в составе комплексной сети УФСБ по Амурской области, используемой для охраны государственной границы Российской Федерации с республикой Китай

Результаты, полученные в ходе решения задачи оптимизации работы широкополосной беспроводной сети, позволяют максимально эффективно использовать пропускную способность радиосоты региональной сети, что применялось при разработке, реализации и эксплуатации беспроводных сетей, перечисленных выше, а также опорной беспроводной сети г Обнинск.

Результаты диссертационной работы используются в учебном процессе Московского Физико-Технического Института при чтении лекций по курсу «Основы инфокоммуникационных технологий» и в лабораторных работах

Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на

Международной конференции по информационным сетям, системам и технологиям (МКИССиТ-2002, Санкт-Петербург),

Международном семинаре «Распределенные компьютерные и телекоммуникационные сети Теория и приложения» (DCCN-2005, София, Болгария),

Третьей международной конференции по проблемам управления Института проблем управления (МКПУ III - 2006, Москва), Международном семинаре «Распределенные компьютерные и телекоммуникационные сети Теория и приложения» (DCCN-2006, София, Болгария),

Семинарах ИППИ РАН

Публикации. По теме диссертации опубликовано 9 научных работ, список которых приведен в конце автореферата Кроме того, получены 2 свидетельства об официальной регистрации программ для ЭВМ, и 1 патент на полезную модель

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 63 наименования, и приложения Работа изложена на 108 страницах и содержит 23 рисунка и 14 таблиц

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность работы, сформулирована основная цель, научная новизна и практическая значимость результатов, приведено краткое описание структуры диссертации

В первой главе рассмотрены области применения и преимущества широкополосных беспроводных сетей, а также кратко рассмотрено семейство протоколов IEEE 802 11, описаны различные архитектуры беспроводных сетей

Дано подробное описание уровня управления доступом к среде (MAC -уровня) протокола IEEE 802 11 Базовым методом доступа к среде передачи данных в протоколах IEEE 802 11 является функция распределенной координации (DCF) Этот метод может использоваться как в беспроводных сетях, функционирующих с использованием топологии ad-hoc, так и с использованием звездообразной топологии, то есть в сетях, инфраструктура которых включает точку доступа (Access Point, АР) Функция DCF основана на методе коллективного доступа с обнаружением несущей и механизмом избегания коллизий (Carrier Sense Multiple Access/Collision Avoidance, CSMA/CA) Коллизионный механизм регламентирования коллективного доступа к среде передачи данных имеет узкое место — так называемую проблему «скрытых станций» Из-за наличия естественных препятствий возможна ситуация, когда два узла сети не могут «слышать» друг друга напрямую Такие узлы (станции) называют скрытыми Однако для звездообразной топологии более естественными являются иные механизмы регламентирования

коллективного доступа, известные как функция централизованной координации (Point Coordination Function, PCF), и функция гибридной координации (Hybrid Coordination Function, HCF) В случае задействования этих механизмов один из узлов сети (точка доступа) является центральным и называется центром координации На центр координации возлагается задача управления коллективным доступом всех остальных узлов сети к среде передачи данных на основе алгоритма кругового опроса Таким образом, PCF и HCF реализуют централизованный приоритетный доступ к среде передачи данных Такой подход полностью исключает коллизионный доступ к среде и делает невозможным возникновение коллизий, а для приложений, критичных к задержкам при передаче, гарантирует приоритетный доступ к среде Кроме этого, механизмы PCF и HCF полностью решают проблему «скрытых станций»

В разделе 1 3 описаны принципы построения и особенности беспроводных региональных сетей Широкополосная беспроводная региональная сеть состоит из радиосот и проводных или беспроводных каналов, связывающих эти радиосоты В общем виде, типовая радиосота беспроводной широкополосной региональной сети состоит из Базовой Станции (БС), и ассоциированных с ней Оконечных Станций (ОС) Каждая радиосота обладает следующими основными свойствами

все оконечные станции скрыты друг от друга и их антенны

сфокусированы на базовую станцию, те обмен информацией между

оконечными станциями возможен только посредством базовой станции,

расстояния между базовой и оконечными станциями достаточно велики

(несколько километров) и несимметричны,

На основании анализа особенностей беспроводных региональных сетей IEEE

802 И делается вывод о перспективности использования в них

централизованного управления на базе функций координации PCF и HCF Так

как в основе обеих функций лежит механизм централизованного опроса

8

(поллинг), следует обратить особое внимание на способ конкретной реализации

этого механизма Именно от конкретного механизма поллинга, а также от его

параметров в основном зависит эффективность работы беспроводной

широкополосной региональной сети с централизованным управлением В случае

использования централизованных функций координации, базовая станция

беспроводной широкополосной региональной сети будет являться центром

координации сети, что позволит гибко управлять сетью и менять ее параметры, в

зависимости от конкретной обстановки, настраивая только базовую станцию

сети, не затрагивая оконечных

Стандарты IEEE 802 11 оставляют значительную свободу для разработчиков

в вопросе конкретной реализации функций централизованного и гибридного

управления Например, в стандартах не описаны конкретный метод опроса

оконечных станций, способ формирования очередей кадров на отправку и тд

Поэтому в данной работе описываются вновь разработанные схемы Адаптивного

Динамического Поллинга (АДП) для базовой станции типовой радиосоты

беспроводной широкополосной региональной сети Базовая станция формирует

отдельную очередь кадров для каждой оконечной станции Кадры в каждой из

очередей приоритезуются согласно типу трафика, к которому они принадлежат

Базовая станция циклически обслуживает оконечные станции, при этом она

передает им кадры из соответствующих очередей, а также, опрашивая их,

принимает кадры от них После этого, базовая станция переключается на

обслуживание следующей оконечной станции При этом в процессе передачи

данных присутствуют накладные расходы на переключение между очередями

базовая станция затрачивает время, появляются служебные кадры (CF POLL и

пр ), с помощью которых базовая станция опрашивает оконечные станции

Дня решения задач, возникающих при разработке схем АДП необходимо

выбрать метод, согласно которому базовая станция будет осуществлять

циклический опрос оконечных станций

9

выбрать дисциплину работы базовой станции с очередями (на прием и на передачу) оконечных станций,

предложить методы минимизации накладных расходов,

разработать методы расчета оптимальных параметров системы.

Далее, описываются две типовые ситуации, которые встречаются при

эксплуатации широкополосных беспроводных региональных сетей В первой

ситуации, преобладает трафик «сверху-вниз», те от базовой станции к

оконечным станциям, так как в основном требуется информация, получаемая из

внешней сети через базовую станцию (например, если сеть используется в

качестве «последней мили» поставщика интернет-услуг) Во второй ситуации,

преобладает трафик «снизу-вверх», т е от оконечных станций к базовой, так как

требуется передавать информацию через базовую станцию во внешнюю сеть

(например, если сеть используется для видеонаблюдения и телеметрии)

Принципиальная разница этих двух ситуаций в том, что в первом случае (трафик

«сверху-вниз»») базовой станции, которая является координатором работы всей

беспроводной сети, заранее известны параметры очередей кадров на передачу к

оконечным станциям, поэтому базовая станция может выбрать политику работы

с очередью, заранее, не подключаясь к ней А во втором случае (трафик «снизу-

вверх») базовая станция ничею не знает об очередях кадров оконечных станций,

поэтому вынуждена сначала подключаться к ним, а затем уже принимать

решение о политике работы с очередью Для моделирования вышеописанных

ситуаций предлагаются две аналитические модели, которые исследуются во

второй и третьей главах диссертации

В пункте 2 1 второй главы описаны основные свойства и характеристики

различных систем поллинга

В пункте 2 2 подробно рассмотрена аналитическая модель, предлагаемая для

моделирования работы типовой радиосоты широкополосной беспроводной

региональной сети, в режиме преобладания трафика «сверху-вниз» Для

10

снижения накладных расходов, предлагается обслуживать очередь только в том случае, если ее длина превышает заданную величину — порог Таким образом, при циклическом опросе, будут пропускаться пустые очереди, и очереди содержащие малое количество пакетов Предложенная модель выглядит следующим образом циклическая система поллинга с одним обслуживающим прибором (сервером) и N очередями, имеющими неограниченное число мест для ожидания N >2 Поток заявок в / -ю очередь представляет собой

простейший поток с параметром Л,,1 = 1,Ы Сервер обходит очереди циклически (в порядке возрастания их номеров) и обслуживает лишь те очереди, число заявок в которых достигло определенного порога (к1 для 1-й очереди),

к/> 0,/=1,7У Перед обслуживанием г-й очереди серверу требуется случайное, экспоненциально распределенное с параметром 5, время на подготовку к работе Время обслуживания заявок в I -й очереди экспоненциально распределено с параметром Очередь

обслуживается до тех пор, пока не опустеет, после чего сервер перемещается к следующей очереди, подлежащей обслуживанию Если же все очереди содержат недостаточное количество заявок, сервер прекращает обход цо тех пор, пока число заявок в одной из очередей не достигнет необходимого порога

Предполагается, что выполняется критерий стационарного режима для рассматриваемой системы Под состоянием системы в момент времени / понимается состояние случайного процесса £(() = п(/)),/ > 0, где

/м(/) = 0 если в момент I сервер простаивает, т(/) = 1 если сервер готовится к обслуживанию (подключается) /п({) = 2 , если сервер занят обслуживанием, / > О, /(/) - номер очереди, у которой находится сервер в момент времени /,

I(?) = 0, если в этот момент сервер простаивает, п(/) = (пх (/),и2(/), ..,пы (7)), п] (?) - число заявок в у -й очереди в момент времени Далее

вводятся стационарные вероятности процесса £(?)

а(г) = ИтРМО = 0,/(0 = 0,п(0 = г} , 0 < гт < кт ,/я = 1, N,

(->00

д (г) = ИтР{т(0 = 1,1(0 =»,»(/) = г}, гт > 0, от = 1,ЛГ,от * ¿,г, > к,, (г) = 11шР{т(0 = 2, /СО = /,п(0 = г}, гт > О, от = Щот * г,г, > 0,

Г—

__N

где г = (г,,г2, ..,Гд,), г = 1,ЛГ и Л =

Система уравнений равновесия для стационарных вероятностей имеет вид

N N

(1) Мг) = £л/а(г-е,)1{г >0} + 0,,

7=1 у = 1

Г\ < К, ги<кн>

N

(2) (Я + //, )?, (г) = £ Лд (г - >й (, + (г + е,) + (г)/)г ^},

7=1

Г] >0 >0, г, >0, г = ЦУ,

(3) (Л + )р, (г) = р, (г - е, )1{Г; >кА/, + д (г + е;_,)/{,. (+ 7=1

+ Х,а{гх, ,Г(_,Д,_,,Г1+1,. ,Гц)1{г^к1 г^к^г^к, г,и<А,+] +

1-2

/=1

г, >0 >0, г, 1 = 1,N

гае е / - вектор-строка, элементы которой равны нулю, за исключением / -го,

равного единице, принимает значение 1, если условие А

выполнено, в противном случае равно нулю, ¿>;; - символ Кронекера Уравнение нормировки для стационарных вероятностей имеет вид

! ! \ ОС \ СО -Ю

X .2>(г) + Х X 2>(г) + £ X Хл(г) = 1

Далее вводятся производящие функции

/, =0 =0 г\ ад =2 !>,№ / =

г, =<5,, =<ьл

!дег = (2,,22, ) , | < 1, ,|гл|<1

После умножения уравнений (1) - (3) на соответствующие степени г,,

и суммирования их в каждой из групп (1), (2) и (3), а затем сложения групп

уравнений (1) и (3), получаются следующие функциональные уравнения

13

[_«=1 J 7=1

Ш=1

(5) а (ж) = „ где 2о

И=1

В силу аналитичности производящей функции в области

{(г,, г2, . , гА,) ^ | <1,.. , Ьд, I < 1} числитель правой части (5) обращается в

нуль в точках, в которых обращается в нуль знаменатель Отсюда

N

2X0 - + мХг, ~= 0> ПРИ = Ц(2Г)>

Ш=1

где

IV

т=1

ты

При этом и, (г,)| < 1

Числитель правой части (5) также равен нулю в точке и с

учетом этого получается соотношение

М,

Дальнейший анализ функциональных уравнений (4) - (5) затруднен, поскольку имеется N +1 уравнений для 11Я 4-1 неизвестных производящих функций В связи с этим, далее рассматривается система толлинга с конечным числом мест для ожидания в очередях и численным решением системы

уравнений для стационарных вероятностей. В этом случае стационарный режим существует при любых параметрах, характеризующих рассматриваемую систему поллинга

В случае ограниченного числа мест для ожидания в I -й очереди, одно из

уравнений системы уравнений (1) — (3) заменяется условием нормировки для стационарных вероятностей

геЛ /=1 геП, (=1 геХ,

где Л = {(г,, ..,г ,).гт< кт,т = \ Щ,

П, = {(г„ . ,г„) • 0 < г, < Л„0 <гт< Ят,т = Ш,т Ф /},

X, = {(г„ . ,гы) :к,<г,< £„0 < гт < Кт,т = Ш,т * г,\

В результате получается система уравнений относительно N N п

Л (2Я, - к, ++1) + Пк/ неизвестных

,=1 /=1 /=1 ]*>

Из стационарных распределений вероятности получаются характеристики производительности

Ч = Х^ -ЛИС-)' /,./ = ЦУ, 5/ = 5>,р,(г),

геП, геХ,

геЛ геЛ

Ц - средняя длина } -й очереди в момент обслуживания / -й очереди (без учета обслуживаемой заявки), Б/ - средняя длина ] -й очереди в момент подключения

к I -й очереди, II1 - средняя длина ] -й очереди в момент простоя сервера и а -средняя доля простоя сервера в единицу времени

Для нахождения среднего времени ожидания Щ заявки, поступившей в г -ю очередь, использован принцип декомпозиции для систем массового обслуживания с простоями Для отдельно взятой г -й очереди системы поллинга простои могут быть интерпретированы как периоды времени, когда сервер не обслуживает эту очередь, а подключается к какой-либо очереди или простаивает из-за недостаточного количества заявок в системе

Кратко принпип декомпозиции состоит в следующем количество работы У/ в I -й очереди в произвольный момент времени распределено так же, как сумма количества работы в соответствующей системе М | М 111 и количества работы /, в системе поллинга в произвольный момент, когда сервер не занят

обслуживанием очереди Количество работы в данный момент времени, это время, которое затратит сервер на обслуживание заявок, находящихся в системе в данный момент Для средних значений принцип декомпозиции имеет вид

(6) м^=м>; + м/(

Среднее количество работы в I -й очереди А, А

где первое слагаемое это среднее количество работы в I -й очереди, второе

1

слагаемое - среднее время, равное —, оставшееся до окончания обслуживания

А,

заявки в I -й очереди, начиная с произвольного момента времени при условии, что в данный момент сервер обслуживает эту очередь По формуле Литтла

—= —ЛД = р}¥1, откуда

А М

М

Среднее количество работы в соответствующей системе М \ М 111 Я1 (без простоев сервера)

' И-рГК-РМ,

Величина /, представляет собой сумму среднего количества работы в / -й очереди в момент простоя сервера 1} , в момент подключения /( , и в момент обслуживания других очередей /(3 при условии, что момент не является моментом обслуживания I -й очереди

т, '

где 7] - вероятность того, что в произвольный момент времени сервер не обслуживает г -ю очередь

(9) Л'= /,2=-£

И 1 г 6 Л т=1 геХ,

А т-1 геП,

Вероятность Т1 равна сумме вероятностей того, что в произвольный момент

времени сервер простаивает, переключается к некоторой очереди или обслуживает ] -ю очередь / Ф I

(ю) 7>2>(г)+Х 2>,Лг)+Е

геЛ

от=1 геХ,

т-1 геП, тФ1

Из равенств (6) — (10) получается формула для среднего времени ожидания в I -й очереди

(п) гг 1

< /1 _ ч 1

(1-А )(!-Р,И

+

+ ■

| Л N

/77=1 геХ

геЛ

т=\ геП, т^т

В третьей главе рассмотрена аналитическая модель, предлагаемая для моделирования работы типовой радиосогы широкополосной беспроводной региональной сети, в режиме преобладания трафика «снизу-вверх» В данном случае, базовая станция ничего не знает об очередях кадров оконечных станций, поэтому вынуждена сначала подключаться к ним, а затем уже принимать решение о политике работы с очередью Как ранее было отмечено, для сокращения накладных расходов следует пропускать пустые очереди и очереди с малым числом кадров Однако, если в режиме преобладания трафика «сверху-вниз», базовая станция может сразу пропустить незаполненную очередь, то в режиме преобладания трафика «снизу-вверх», базовая станция может пропустить незаполненную очередь только в следующем цикле опроса, т к узнает о состоянии очереди только после подключения к ней Поэтому, для

моделирования ситуации преобладания трафика «снизу-вверх» используется следующая модель

Модель представляет собой систему поллинга с N очередями и одним обслуживающим сервером Обслуживание очередей - шлюзовое, т.е сервер обслуживает лишь те заявки в очереди, которые присутствовали в ней в момент подключения сервера этой очереди Поток заявок в I -ю очередь представляет

собой простейший поток с параметром Я,, I = 1, А^. Время обслуживания заявок

в г -й очереди экспоненциально распределено со средним Ь1 Время на

подключение к очереди распределено экспоненциально со средним gl Сервер обходит очереди циклически (в порядке возрастания их номеров) Опрос очередей происходит по следующему правилу Сервер опрашивает очередь, если опрашивал ее в предыдущем цикле, и в очереди были заявки, либо в предыдущем цикле очередь была пропущена Если же при опросе (подключении) в предыдущем цикле очередь была пуста, то в текущем цикле сервер ее не опрашивает (не подключается), а подключается к следующей по циклу очереди, которая должна быть опрошена Если же в цикле все очереди подлежат пропуску, сервер простаивает случайное, экспоненциально распределенное время со средним т > О

Далее в работе показано, что использование уравнений равновесия для стационарных вероятностей нецелесообразно, т к система уравнений получается слишком громоздкой и практически не поддающейся аналитическому решению Поэтому рассматриваемая модель исследовалась с использованием методов приближенного анализа Результаты приближенного анализа подтверждены результатами имитационного моделирования в четвертой главе

В качестве приближенного анализа используется следующий подход

Предполагается, что с некоторой вероятностью И, очередь в цикле

19

опрашивается, а с вероятностью 1 — и, - нет В этом смысле рассматриваемая модель сводится к системе поллинга с обслуживанием типа Бернулли Вероятности и,, .,иы вычисляются следующим образом

и, = 1-м, +м,(1 -е~х,с),

где С - среднее время цикла Согласно этой формуле, очередь будет обслужена в текущем цикле, если она не была обслужена в предыдущем цикле с вероятностью 1 — и, или она была обслужена (с вероятностью И,) и за среднее время цикла С в нее поступили заявки Получаем

(12) и,=-— =

1 + е '

Следует заметить, что если Я мало, то вероятность и1 = 0,5, что

согласуется с принятой адаптивной схемой поллинга В случае, тогда интенсивность потока заявок большая, и среднее время цикла увеличивается так,

что значение Я, С велико, и следовательно е ~Х,С стремится к нулю Отсюда = 1, т е при большой интенсивности входного потока очередь практически

всегда не пуста и в каждом цикле опрашивается сервером Среднее время цикла вычисляется по формуле

N N

+гП(1-*о

(13) С = —-----, где р = ^р1=^А1Ь1

1-уо ^ ы

Время цикла, это либо время подключения сервера очередям, подлежащим обслуживанию в цикле, и совокупная длительность их обслуживания, либо простой сервера, если все очереди пропускаются в цикле

Из равенств (12) и (13) имеем систему уравнений для нахождения неизвестных С и и,, . , ии

Для нахождения средней длины очереди, применяется метод анализа средних С помощью среднего времени цикла С отыскивается ряд характеристик

Среднее время обслуживания г -й очереди, при условии, что очередь в цикле опрашивается

Средняя длина 1 -й очереди в момент опроса, при условии, что в этот момент очередь не пуста

и,А,С + (1-«,)2Л,С

Я,

1 -и,е'х'с -(\-и,)е~ыс Произвольный момент времени может быть моментом обслуживания у -й очереди (с вероятностью р;), либо моментом подключения к ней (с

вероятностью ^ ), либо моментом простоя с вероятностью где

о = П(1-и.)

/77=1

Применяя метод анализа средних, получаем формулу для вычисления средней длины I -й очереди Ь1

(14) Ч-Р,---+ -^г12-и,ИС +

n

+ 1

i-l

Sjuj С

+Pj

[{и,р,С + Tl+gj)Al+0-И(С)А,С]+

/.

+ + ^ Ib.P.C + T2+gl )Л, + (ur + T1+gj )Я, + (1 - и,С)Л,ф

v с

(Rj-Wj от

( N

1

l*i

С

где

= + A+ic) + • + + Pj-iQ ;

. = + Д+iO + •• + uN(gN + pNC);

=щ (gi+pf) + +(я,., + Pj-iQ

Среднее время ожидания в /-й очереди находится по формуле Литтла

л

В четвертой главе приведено сравнение аналитических результатов, полученных во второй и третьей главах, с результатами, полученными с помощью имитационной системы общего назначения GPSS World

Объектом моделирования служила широкополосная беспроводная региональная сеть, состоящая из нескольких оконечных станций, работающих с одной базовой станцией Интенсивности поступления пакетов к устройствам и скорости их обработки различны Оконечные станции опрашивались согласно дисциплинам опроса соответствующих аналитических моделей

Параметрами сравнения аналитических и имитационных данных результатов служат стационарные вероятности состояния системы в произвольный момент времени, средние длины очередей и среднее время ожидания заявки в очереди

При выполнении имитации предполагается, что система вошла в стационарный режим тогда, когда при удваивании числа проходящих через систему заявок, ни один из параметров сравнения не изменяется более чем на 0,5% При проведении имитационного моделирования через систему проходило более 3 миллионов пакетов Результаты имитационного моделирования с хорошей точностью подтверждают результаты аналитического исследования

В пункте 4 2 рассмотрены способы оптимизации параметров предложенных механизмов адаптивного централизованного управления Основное внимание уделено оптимизации системы под трафик приложений, критичных к задержкам, таких как 1Р телефония и потоковое видео

В пункте 4 3 сравниваются характеристики беспроводной широкополосной региональной сети в случае децентрализованного управления и в случае адаптивного динамического централизованного управления Анализ характеристик проводится на основании данных, полученных в ходе аналитического и имитационного моделирования адаптивного динамического централизованного опроса, проведенного в данной диссертации

В конце четвертой главы описано специальное программное обеспечение -драйвер модуля радиоканала, которое в настоящий момент используется в радиомаршрутизаторе РЭС «Рапира», разработанном в ИППИ РАН При разработке драйвера были широко использованы результаты, полученные в ходе работы над данной диссертацией

В заключении приводятся основные результаты и выводы диссертационной работы

В приложении приведены акты о внедрении результатов диссертационной работы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

В работе разработаны механизмы адаптивного динамического централизованного управления в широкополосных беспроводных региональных сетях передачи информации, а также проведено исследование и оптимизация этих механизмов с помощью комплекса аналитических и имитационных моделей В частности

1 Сформулированы принципы построения и особенности широкополосных беспроводных региональных сетей, функционирующих на базе семейства

'протоколов IEEE 802 11

2 Разработаны новые механизмы адаптивного централизованного управления в беспроводных сетях

3 Разработаны аналитические модели адаптивного централизованного управления в беспроводных сетях, позволяющие вычислять и оптимизировать параметры адаптивного динамического поллинга

4 Предложены комплекс имитационных моделей, позволяющий рассчитывать характеристики широкополосных беспроводных региональных сетей с адаптивным динамическим централизованным управлением

5 Разработаны новые механизмы адаптивного централизованного управления в широкополосных беспроводных региональных сетях

6 Выводы, сделанные на основе результатов данной работы широко используются при разработке программного обеспечения для оборудования широкополосных беспроводных региональных сетей, а также для построения таких сетей, что подтверждено соответствующим актами о внедрении

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

[1] Вишневский В М, Лаконцев Д В , Семенова О В., Шпилев С А., Модель системы поллинга для исследования широкополосных беспроводных сетей//Автоматика и телемеханика. 2006 №12 С 123-135

[2] Вишневский В М , Гузаков Н Н, Лаконцев Д В , Система «Рапира» - базис для отечественных широкополосных беспроводных сетей // Электроника НТБ, 2005, №1, стр 30-35

[3] Вишневский В М , Лаконцев Д В , Семенова О В , Шпилев С А Об одной стохастической системе поллинга и ее применении для моделирования 5 беспроводных сетей // Третья межд конф по проблемам управления (2022 июня 2006 г г Москва, Россия) Тезисы докладов Том 2 - М Институт проблем управления 2006 - стр 145

[4] Кушнир Т С, Лаконцев Д В , Сафонов А А, Механизм опроса в программном обеспечении радиомаршрутизатора, работающего по протоколу ШЕЕ 802 11 // Труды межд сем «Распределенные компьютерные и телекоммуникационные сети (DCCN'2005)» София, Болгария М Техносфера, 2005, стр 177-182

[5] Лаконцев Д В, Семенова О В, Математические модели централизованного управления в беспроводных сетях IEEE 802 11. // Труды межд сем «Распределенные компьютерные и телекоммуникационные сети (DCCN'2005)» София, Болгария М Техносфера, 2005, стр 77-83

[6] Вишневский В М , Лаконцев Д В , Семенова О В , Левнер Е В , Модель поллинга с адаптивной схемой опроса очередей // Труды межд сем «Распределенные компьютерные и телекоммуникационные сети (DCCN-

2006)» София, Болгария - M Государственная публичная научно-техническая библиотека России, 2006 - стр 58-64

Вишневский В M, Лаконцев Д В , Шпилев С А , Астафьева И H , Адаптивный динамический механизм опроса, в применении к сетям IP телефонии // Труды межд сем «Распределенные компьютерные и телекоммуникационные сети (DCCN-2006)» София, Болгария - M Государственная публичная научно-техническая библиотека России, 2006 -стр 65-79

Лаконцев Д В, Пидоненко В Л, Анализ и изучение модели •централизованного опроса (поллинга) с шлюзовой дисциплиной обслуживания // Труды межд сем «Распределенные компьютерные и телекоммуникационные сети (DCCN-2006)» София, Болгария - M Государственная публичная научно-техническая библиотека России, 2006 -стр 80-99

Ляхов А И , Мацнев Д H , Лаконцев Д В , Шелихов О H , Сбор и анализ характеристик функционирования действующей беспроводной сети на основе протокола IEEE 802 11 // VIII межд конф по информационным сетям, системам и технологиям (МКИССиТ-2002), Санкт-Петербург, 16-19 сентября 2002 С 225-235

Введение

1 Принципы построения и особенности широкополосных беспроводных региональных сетей.

1.1 Широкополосные беспроводные сети.

1.2 Семейство протоколов IEEE 802.

1.2.1 Архитектура и основные понятия.

1.2.2 Уровень управления доступом к среде семейства протоколов IEEE 802.11. Распределенная функция координации (DCF).

1.2.3 Централизованная (PCF) и гибридная (HCF) функции координации.

1.3 Принципы построения, особенности и характерные ситуации использования беспроводных широкополосных региональных сетей.

2 Аналитическая модель радиосоты, работающей в режиме „последняя миля".

2.1 Основные понятия и классификация систем поллинга.

2.2 Аналитическая модель радиосоты в режиме „последняя миля". 56 2.2.1 Математическая модель.

2.2.2 Получение стационарного распределения состояний системы.

2.2.3 Получение характеристик производительности системы.

3 Аналитическая модель радиосоты, работающей в режиме „сбор данных".

3.1 Математическая модель.

3.2 Стационарное распределение состояний системы.

3.3 Определение характеристик производительности.

4 Имитационное моделирование и оптимизация работы радиосоты.

4.1 Сравнение аналитических результатов с результатами имитационного моделирования.

4.2 Оптимизация параметров схем Адаптивного Динамического Поллинга.

4.3 Сравнение характеристик радиосоты при децентрализованном и при адаптивном динамическом централизованном управлениях.

4.4 Программная реализация результатов работы.

Объект исследования и актуальность темы. В последние годы беспроводные сети передачи данных заняли прочные позиции в повседневной жизни. Сфера их применения простирается от обеспечения взаимодействия между бытовыми приборами (например, между телефоном и телефонной гарнитурой, компьютером и монитором и т.д.) до построения сетей передачи мультимедийной информации городского и регионального масштаба. Построение беспроводных сетей передачи данных регионального масштаба на обширных территориях (например, в удаленных сельских регионах Российской Федерации) является единственным экономически оправданным и наиболее перспективным решением проблемы так называемого „информационного неравенства". При создании беспроводных сетей передачи данных регионального масштаба все большее распространение получают устройства на базе технологий IEEE 802.11 (WiFi). Активный рост числа беспроводных региональных сетей выдвигает в ряд первоочередных задач разработку методов оптимизации их работы, разработку новых алгоритмов функционирования таких сетей, а также оценку их производительности. Проблемам разработки математических моделей сетей передачи данных посвящено значительное количество работ. Среди наиболее известных работ, посвященных этим проблемам, следует отметить работы российских и зарубежных ученых: О.М. Брехова, В.А. Васенина, В.М. Вишневского, B.C. Жданова, P.A. Минлоса, A.B. Печинкина, В.К.

Попкова, B.B. Рыкова, С.Н. Степанова, G. Balbo, S.C. Bruell, L. Fratta, L. Kleinrock, M. Olivetty, H. Takagi, S.C. Borst, O.J. Boxma и др. Среди аналитических работ, посвященных исследованию протоколов IEEE 802.11 и IEEE 802.16 и оценке производительности построенных на их базе беспроводных сетей, наиболее значимыми являются работы В.М. Вишневского, А.И. Ляхова, G. Bianchi, F. Cali, М. Conti, Е. Gregory, J. Weinmiller. Особенности региональных беспроводных сетей при оценке их производительности достаточно полно отражены в ряде работ, однако недостатками этих работ является, слабое внимание, уделяемое механизмам адаптивного централизованного управления, хотя именно эти механизмы нацелены на решение основной проблемы региональных беспроводных сетей — проблемы „скрытых станций". Таким образом, задача анализа, разработки и оптимизации механизмов адаптивного динамического управления является одной из важнейших для развития беспроводных широкополосных региональных сетей передачи данных. Кроме этого, требуется разработать комплекс аналитических и имитационных моделей механизмов централизованного управления для получения адекватных оценок показателей производительности и оптимизации устройств широкополосной беспроводной региональной сети.

В связи с вышеизложенным, целью диссертационной работы является разработка механизмов адаптивного динамического централизованного управления в широкополосных беспроводных региональных сетях передачи информации, а также исследование и оптимизация этих механизмов с помощью комплекса аналитических и имитационных моделей.

Методы исследования. Для достижения поставленной цели, в диссертационной работе используются методы теории вероятности, теории массового обслуживания и имитационного моделирования. Научная новизна:

• впервые разработан комплекс аналитических моделей, адекватно описывающих функционирование широкополосных беспроводных сетей с централизованным управлением;

• разработан комплекс имитационных моделей адаптивного динамического централизованного управления в широкополосных беспроводных сетях функционирующих под управлением семейства протоколов IEEE 802.11;

• на базе разработанного комплекса аналитических и имитационных моделей получены оптимальные параметры механизмов адаптивного централизованного управления в широкополосных беспроводных региональных сетях;

• предложены методы минимизации накладных расходов в работе беспроводных сетей с адаптивным динамическим централизованным управлением.

Научная и практическая ценность. Результаты работы внедрены и используются на практике, что подтверждено соответствующими актами. Изученные и предложенные механизмы адаптивного централизованного управления реализованы в радиомаршрутизаторе РЭС „Рапира", который был разработан ИППИ РАН в рамках Федеральной целевой научно-технической программы „Исследования и разработки по приоритетным направлениям развития науки и техники" на 2002-2006 годы по Государственному контракту 02.477.11.1003 „Разработка технологии создания нового поколения широкополосных телекоммуникационных средств комплектации беспроводных систем передачи данных, голоса и информации". Радиомаршрутизатор РЭС „Рапира" используется в качестве базового устройства в ряде широкополосных беспроводных региональных сетей, в том числе в сети 11ас1юНе1 ИППИ РАН, в беспроводной локальной вычислительной сети ИППИ РАН, в беспроводной сети ООО „Уникомпорт", в беспроводной сети ЗАО „НТЦ ФИОРД" и т.д. РЭС „Рапира" более года успешно работает в составе комплексной сети УФСБ по Амурской области, используемой для охраны государственной границы Российской Федерации с республикой Китай. Результаты, полученные в ходе решения задачи оптимизации работы широкополосной беспроводной сети, позволяют максимально эффективно использовать пропускную способность радиосоты региональной сети, что применялось при разработке, реализации и эксплуатации беспроводных сетей, перечисленных выше, а также опорной беспроводной сети г. Обнинск. Результаты диссертационной работы используются в учебном процессе Московского Физико-Технического Института при чтении лекций по курсу „Основы инфокоммуникационных технологий" и в лабораторных работах.

Апробация результатов работы. Основные результаты диссертации докладывались и обсуждались на:

• Международной конференции по информационным сетям, системам и технологиям (МКИССиТ-2002, Санкт-Петербург);

• Международном семинаре „Распределенные компьютерные и телекоммуникационные сети. Теория и приложения" (DCCN-2005, София, Болгария.);

• Третьей международной конференции по проблемам управления Института проблем управления (МКПУ III - 2006, Москва);

• Международном семинаре „Распределенные компьютерные и телекоммуникационные сети. Теория и приложения" (DCCN-2006, София, Болгария.);

• Семинарах ИППИ РАН.

Публикации. По теме диссертации опубликовано 9 научных работ, список которых приведен в конце автореферата. Кроме того, получены 2 свидетельства об официальной регистрации программ для ЭВМ, и 1 патент на полезную модель.

Структура и объем диссертационной работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы, включающего 63 наименования, и приложения. Работа изложена на 108 страницах и содержит 23 рисунка и 14 таблиц.

5. Выводы, сделанные на основе результатов данной работы широко используются при разработке программного обеспечения для оборудования широкополосных беспроводных региональных сетей, а также для построения таких сетей, что подтверждено соответствующим актами о внедрении.

Все результаты данной диссертационной работы доказали свою теоретическую и практическую ценность при разработке, реализации и эксплуатации беспроводного оборудования в составе широкополосных беспроводных региональных сетей, развернутых на территории Российской Федерации.

Заключение

В работе разработаны механизмы адаптивного динамического централизованного управления в широкополосных беспроводных региональных сетях передачи информации, а также проведено исследование и оптимизация этих механизмов с помощью комплекса аналитических и имитационных моделей. В частности:

1. Сформулированы принципы построения и особенности широкополосных беспроводных региональных сетей, функционирующих на базе семейства протоколов IEEE 802.11.

2. Разработаны новые механизмы адаптивного централизованного управления в беспроводных сетях.

3. Разработаны аналитические модели адаптивного централизованного управления в беспроводных сетях, позволяющие вычислять и оптимизировать параметры адаптивного динамического поллинга.

4. Предложены комплекс имитационных моделей, позволяющий рассчитывать характеристики широкополосных беспроводных региональных сетей с адаптивным динамическим централизованным управлением.

1. Вишневский В.M. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003.

2. Вишневский В.М., Ляхов А.И., Портной С.Л., Шахнович И.В. Широкополосные беспроводные сети передачи информации. М.: Техносфера, 2005.

3. Вишневский В.М. Беспроводные сети широкополосного доступа к ресурсам Интернета // Электросвязь. 2000. №10. С. 9-13.

4. Vishnevsky V.M., Lyakhov A.I. Adaptive features of IEEE 802.11 Protocol: utilization, tuning and modifications // Proc. of 8th HP-OVUA Conf. Berlin, June 2001.

5. Баканов A.С., Вишневский В.M., Ляхов A.И. Метод оценки показателей производительности беспроводных сетей с централизованным управлением // АиТ. 2000. №4. С. 97-105.

6. Вишневский В.М., Ляхов А.И., Гузаков Н.Н. Оценка максимальной производительности беспроводного доступа в Интернет // АиТ. 2004. т. С. 52-70.

7. Лаконцев Д.В., Семенова О.В. Математические модели централизованного управления в беспроводных сетях IEEE 802.11 / Распределенные компьютерные и телекоммуникационные сети (DCCN-2005). М.: Техносфера, 2005. С. 77-83.

8. Vishnevsky V.M., Lyakhov A.I., Guzakov N.N. An adaptive polling strategy for IEEE 802.11 PCF // Proc. 7th Int. symp. on Wireless Personal Multimedia Communications (WPMC'04). Abano Terme, Italy, September 12-15, 2004. V. 1. P. 87-91.

9. Мацнев Д.Н. Разработка методов исследования протокола МАС-уровня беспроводных региональных сетей RadioEthernet: Дис. к.т.н. М., 2004 103с.

10. И. Столлингс В. Беспроводные линии связи и сети. : Пер. с англ. // М.: Издательский дом „Вильяме", 2003.

11. IEEE 802.11, The working Group for Wireless LANs // http: / / grouper.ieee.org/groups /802/11/index.html.

12. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications // ANSI/IEEE Std 802.11, 1999 Edition.

13. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications. Amendment 4: Further Higher Data Rate in the 2.4

14. GHz Band // IEEF Std 802.11g-2003 (Amendment to IEEE Std 802.11, 1999 Edition).

15. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: High-speed Physical Layer in the 5 GHz Band // IEEE Std 802.11a-1999 (Supplement to IEEE Std 802.11, 1999 Edition).

16. Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications: Higher-Speed Physical Layer Extension in the 2.4 GHz Band // IEEE Std 802.11b-1999 (Supplement to ANSI/IEEE Std 802.11, 1999 Edition).

17. Borst S. C. Polling systems. Amsterdam: Stichting Mathematisch Centrum, 1996.

18. Chang K.-H. First-come-first-served polling systems // Asia-Pacific J. Oper. Res. 2001. V. 18. No. 1. P. 1-11.

19. Takagi H. Analysis and applications of polling models / Performance Evaluat: Origins and Directions. Ed. Haring G., Lindemann Ch., Reiser M. Lecture Notes Comput. Sci. 2000. V. 1769. P. 423-442.

20. Takagi H. Analysis of polling systems. MIT Press, 1986. 175 p.

21. Takagi H. Queueing analysis of polling models: an update / Stochastic Analysis of Computer and Communication Systems. Ed. Takagi H. Amsterdam, North-Holland, 1990. P. 267-318.

22. Takagi H. Queueing analysis of polling models: progress in 1990-1994 / Frontiers in Queueing, ed. Dshalalow J.H., CRC, Boca Raton, FL, 1997. P. 119-146.

23. Levy H., Sidi M. Polling systems: applications, modeling and optimization 11 IEEE Trans. Commun. 1990. V. 38. No. 10. P. 1750-1760.

24. Bruneel H., Kim B G. Discrete-time models for communication systems including ATM. Boston: Kluwer Academic Publishers, 1993.

25. Grillo D. Polling mechanism models in communication systems -some application examples. / Stochastic Analysis of Computer and Communication Systems. Ed. Takagi H. Amsterdam, North-Holland, 1990. P. 659-698.

26. Takagi H. Applications of polling models to computer networks // Comput. Networks ISDN Syst. 1991. V. 22. No. 3. P. 193-211.

27. Bing B. Wireless local area networkss: the new wireless revolution. Wiley-Interscience, 2002.

28. Ziouva E., Antonakopoulos T. Improved IEEE802.il PCF performance using silence detection and cyclic shift on stations polling // IEE Proc. Commun. 2003. V. 150. No. 1. P. 45-51.

29. Ziouva E., Antonakopoulos T. Efficient voice communications over

30. EE802.il WLANs using improved PCF procedures // Proc. Third Int. Work Conf. INC 2002/07.

31. Ziouva E., Antonakopoulos T. Improved IEEE802.il PCF performance using silence detection and cyclic shift on stations polling // IEE Proc. Commun. 2003. V. 150. No. 1. P. 45-51.

32. Adán I.J.B.F., Boxma O.J., Resing J.A.C. Queueing models with multiple waiting lines // Queueing Syst. 2001. V. 37. No. 1-3. P. 65-98.

33. Bruno R., Conti M., Gregory E. Bluetooth: architecture, protocols and scheduling algorithms // Cluster Comput. 2002. V. 5. P. 117-131.

34. Kopsel A., Ebert J.-P., Wolisz A. A performance comparison of point and distributed function of an IEEE 802.11 WLAN in the presence of real-time reqiurements // Proc. Inf. Workshop MoMuc2000-Waseda. Japan. October 2000.

35. Olsen T.L., van Der Mei R.D. Polling systems with periodic server routing in heavy-traffic: renewal arrivals // Oper. Res. Lett. 2005. V. 33. No. 1. P. 17-25.

36. Qiao D., Choi S., Soomoro A., Shin K.G. Energy-efficient PCF operation of IEEE 802.11a Wireless LAN // Proc. of INFOCOM 2002. New York, June 2002.

37. Levy H., Sidi M., Boxma O.J. Dominance relations in polling systems // Queueing Syst. 1990. V. 6. No. 2. P. 155-171.

38. Khalid M., Vyavahare P.D., Kerke H.B. Analysis of asymmetric polling systems // Comput. Oper. Res. 1997. V. 42. No. 4. P. 317-333.

39. Miorandi D., Zanella A., Pierobon G. Performance Evaluat of Bluetooth polling schemes: an analytical approach // ACM Mobile Networks and Appl. 2004. V. 9. No. 2. P. 63-72.

40. Altman E., Blanc H., Khamisy A., Yechiali Y. Gated-type polling systems with walking and switch-in times // Commun. in Stat.: Stochastic Models. 1994. V. 10. No. 4. P. 741-763.

41. Singh M.P., Srinivasan M.M. Exact analysis of the state-dependent polling model // Queueing Syst. 2002. Vol. 41. P. 371-399.

42. Eisenberg M. The polling system with a stopping server // Queueing Syst. 1994. Vol. 18. P. 387-431.

43. Giinalay Y., Gupta D. Polling system with patient server and state-dependent setup times // HE Transactions. 1997. V. 29. No. 6. P. 469-480.

44. Giinalay Y,, Gupta D. Threshold start-up control policy for polling systems // Queueing Syst. 1998. V. 29. No. 2-4. P. 399-421.

45. Gupta D., Srinivasan M.M. Polling systems with state-dependent setup times // Queueing Syst. 1996. V. 22. No. 3-4. P. 403-423.

46. Fricker C., Jaibi M.R. Monotonicity and stability of periodic polling models // Queueing Systems, Theory and Applications. 1994. Vol. 15, No. 3. P. 211-238.

47. Fuhrmann S.W., Cooper R.B. Stochastic decompositions in the M/G/l queue with generalized vacations // Operations Research. 1985. Vol. 33, No. 5. P. 1117-1129.

48. Schriber T.J. Simulation using GPSS. John Wiley & Sons, 1974.

49. Liu Z., Nain P., Towsley D. On optimal polling policies // Queueing Syst. 1992. V.ll. No. 1-2. P. 59-83.

50. Boxma O.J., Levy H., Weststrate J.A. Efficient visit orders for polling systems // Performance Evaluat. 1993. V. 18. No. 2. P. 103-123.

51. Boxma O.J., Levy E., Weststrate J.A. Efficient visit frequencies for polling tables: minimization of waiting cost // Queueing Syst. 1991. V. 9. No. 1-2. P. 133-162.

52. Feng W., Kowada M., Adachi K. A two-queue model with Bernoulli service schedule and switching times // Queueing Syst. 1998. V. 30. No. 3-4. P. 405-434.

53. Feng W., Kowada M., Adachi K. Analysis of a multi-server queue with two priority classes rnd (M,N)-threshold service schedule I: non-preemptive priority // Int. Trans. Oper. Res. 2000. V. 7. No. 6. P. 653-671.

54. Feng W., Kowada M., Adachi K. Performance analysis of a two-queue model with an (M, ^-threshold service schedule // J. Oper. Res. Soc. Japan. 2001. V. 44. No. 2. P. 101-124.

55. Feng W., Kowada M., Adachi K. Two-queue and two-server model with a hysteretic control service policy // Sci. Math. Japonicae. 2001. V. 54. No. 1. P. 93-107.

56. Fischer M.J., Harris C.M., Xie J. An interpolation approximation for expected wait in a time-limited polling system // Comput. Oper. Res. 2000. V. 27. No. 4. P. 353-366.

57. Foss S., Kovalevskii A. A stability criterion via fluid limits and its application to a polling system // Queueing Syst. 1999. V. 32. No. 1-3. P. 131-168.

58. Foss S., Last G. On the stability of greedy polling systems with general service policies // Prob. Engineering Inform. Sei. 1998. V. 12. No. 1. P. 49-68.

59. Foss S., Last G. Stability of polling systems with exhaustive service policies and state-dependent routing // Ann. Appl. Prob. 1996. V. 6. No. 1. P. 116137.

60. Fournier L., Rosberg Z. Expected waiting times in cyclic service systems under priority disciplines // Queueing Syst. 1991. V. 9. No. 4. P. 419-439.

61. Frigui I., Alfa A.S. Analysis of a discrete time table polling system with MAP input and time-limited service discipline // Telecommunication Syst. 1999. V. 12. No. 1. P. 51-77.

62. Frigui I., Alfa A.S. Analysis of time-limited polling system // Comput. Commun. 1998. V. 21. No. 6. P. 558-571.

63. Fuhrmann S. W. A decomposition result for a class of polling models // Queueing Syst. 1992. V. 11. No. 1-2. P. 109-120.