Министерство науки и высшего образования РФ

Федеральное государственное бюджетное учреждение науки

Институт проблем управления им. В.А. Трапезникова

РОССИЙСКОЙ АКАДЕМИИ НАУК

В.М. Вишневский, О.В. Семёнова

МЕТОДЫ МАШИННОГО ОБУЧЕНИЯ ДЛЯ ИССЛЕДОВАНИЯ СТОХАСТИЧЕСКИХ

МОДЕЛЕЙ ЦИКЛИЧЕСКОГО ОПРОСА В ШИРОКОПОЛОСНЫХ БЕСПРОВОДНЫХ

СЕТЯХ

Научное электронное издание

Москва ИПУ РАН

2023

2.2. Обзор работ по системам поллинга . . . . . . . . . . 12

3.Модели циклического опроса в широкополосных беспроводных сетях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.1. Схема распределенного управления (DCF) . . . . . 31

3.2.Схема централизованного управления . . . . . . . . 35

3.3.Адаптивный динамический поллинг в беспроводных сетях . . . . . . . . . . . . . . . . . . . . . . . . . 39

4.Системы с адаптивным динамическим опросом. . . 43

4.1.Метод производящих функций для анализа систе-

мы поллинга с адаптивным динамическим опросом 46

4.2.Система адаптивного динамического опроса со шлюзовой дисциплиной . . . . . . . . . . . . . . . . . 50

4.3.Случай исчерпывающей дисциплины обслуживания 57

4.4.Метод средних значений для анализа систем с адаптивным динамическим опросом . . . . . . . . . . . . 62

4.5.Численные примеры . . . . . . . . . . . . . . . . . . . 64

5.Метод машинного обучения для систем цикличе-

5.1.Искусственные нейронные сети . . . . . . . . . . . . 69

5.2.Определение и свойства марковского входного потока, распределение фазового типа . . . . . . . . . . 75

5.3.Несимметричная система циклического опроса c шлюзовой дисциплиной обслуживания . . . . . . . . 86

5.4.Cистема циклического опроса типа MAP/M/1 . . . 87

5.5.Система адаптивного динамического опроса типа M/M/1 . . . . . . . . . . . . . . . . . . . . . . . . . . 89

3

5.6. Cистема адаптивного динамического опроса типа

MAP/M/1 . . . . . . . . . . . . . . . . . . . . . . . . 91 5.7. Область применения метода и алгоритмы расчета

характеристик систем циклического опроса. . . . . . . 92

6. Методы оценки производительности широкополос-

6.2.Оценка эффективности использования адаптивного динамического поллинга в беспроводных ком-

пьютерных сетях IEEE 802.11 – PCF . . . . . . . . . 106

ЛИТЕРАТУРА . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

4

1.Введение

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

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

Одним из важнейших направлений развития сетевой индустрии являются беспроводные сети передачи информации. Следует отметить, что для большинства регионов Российской Федерации, в которых обширная территория сочетается с относительно низкой плотностью населения, данное направление сетевой индустрии может предложить ряд решений, позволяющих экономично и оперативно создавать и использовать преимущества инфраструктуры беспроводных сетей передачи данных в таких регионах. Это становится особенно важным при решении одной из важнейших проблем так называемого «информационного неравенства» российских регионов. И в этом случае применение беспроводных технологий дает возможность, не привлекая значительных финансовых вложений, объединить разрозненные локальные сети в единую сеть передачи данных, а их пользователи на постоянной основе получают доступ ко всемирной сети. Таким образом, все более ускоряющееся развитие беспроводных сетей

5

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

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

Обзор результатов, полученных в области анализа систем стохастического поллинга до 1985 г., проведен Х. Такаги [1]. Дальнейшее развитие теоретических результатов в этом направлении, опубликованных до 1995 г., отражено в книге С. Борста [2]. Период публикаций с 1996 по 2009 год подробно отражен в обзоре [3] автора диссертационной работы в соавторстве с его научным консультантом, а его дополнение, охватывающее работы, опубликованные до 2009 года, опубликовано в [4]. Далее, обзор [3] совместно с новыми методами анализа систем поллинга получил свое развитие в монографиях [5, 6], где также уделено внимание применению моделей поллинга для проектирования широкополосных беспроводных сетей.

В 2018 году О. Боксма и С. Борста в [7] опубликовали обзор методов анализа систем с циклическим опросом и одним сервером. Дальнейшее развитие методов анализа совместно с новейшими результатами в данной области, опубликованных в период с 2007 по 2019 годы, отражено в статьях [8,9].

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

6

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

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

2.Математические модели систем циклического опроса

2.1.Классификация систем поллинга и основная модель поллинга

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

Далее рассмотрим дискретные системы поллинга. Описание таких системы определяется следующими основными параметра-

7

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

Пусть далее система имеет конечное число N очередей (N ≥ 2). Очередь с номером i будем обозначать через Qi, i = 1, N.

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

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

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

Опишем далее классификацию типов порядка опроса:

1.Циклический, при котором сервер посещает очереди в порядке возрастания их номеров, а затем вновь возвращается

к первой очереди: Q1, Q2, . . . , QN , Q1, Q2, . . . , QN , . . . . Системы поллинга с таким порядком опроса называют цикли-

ческими, а время обслуживания очередей с первой до последней – циклом.

8

2.Адаптивный динамический: сервер строит следущий цикл опроса в зависимости от состояния очередей в текущем цикле. Если очередь опрошена и в этот момент она пуста, ее исключают из следующего цикла опроса.

3.Периодический: очереди обслуживаются в порядке согласно таблицы поллинга (T (1), T (2), . . . , T (M)) длины M (M ≥ N), T (i) {1, . . . , N}, i = 1, M. Порядок обслуживания оче-

редей имеет вид: QT (1), QT (2), . . . , QT (M), QT (1), QT (2), . . . ,

QT (M), . . . .

Одним из разновидностей периодического опроса является опрос типа «звезда» (star-polling) с таблицей поллинга (1, 2, 1, 3, ..., 1, N). В этом случае одна из очередей (напри-

мер, Q1) назначается приоритетной, и сервер возвращается к ней всякий раз после посещения любой другой очереди.

4.Случайный: следующая очередь на обслуживание выбирается случайно, например, независимо от номера предыдущей обслуженной очереди следующей очередью для обслуживания будет Qi с вероятностью pi, i = 1, N в предполо-

i, j = 1, N после обслуживания Qi сервер переключается к

Qj, PN pij = 1, i = 1, N.

j=1

5.Приоритетный: в данном случае очереди системы присваивается свой приоритет и она может быть обслужена, если более приоритетные очереди системы пусты.

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

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

9

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

Дисциплина обслуживания очереди – это число заявок, которое может обслужить сервер за одно посещение очереди. Основными такими ддисциплинами являются:

1.Исчерпывающая, при которой сервер обслуживает очередь до тех пор, пока она не станет пустой.

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

3.Многофазная шлюзовая, при которой заявка, поступившая в систему, ожидает несколько циклов в очереди до момента своего обслуживания. Такую дисциплину можно интерпретировать следующим образом. Очередь имеет k шлюзов, и заявка, поступающая в очередь, помещается в последний, k- й шлюз (k ≥ 1). В очередной момент опроса очереди сервером все заявки перемещаются на один шлюз вперед (то есть из шлюза i+ 1 в шлюз i), при этом сервер опустошает лишь первый шлюз и далее перемещается к следующей очереди. Таким образом заявка последовательно с каждыфм следующим циклом продвигается по шлюзам, пока не достигнет первого шлюза и не будет обслужена.

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

10

за одно посещение сервером, ограничено величиной l (l-ограниченная дисциплина). В случае, если ограничение касается времени, которое проводит сервер у очереди, то такую дисциплину называют T -ограниченной.

5.l-уменьшающая: в этом случае сервер обслуживает очередь до тех пор, пока ее длина не станет на l меньше, чем была в момент подключения сервера, либо пока очередь не опустеет, l ≥ 1 (что наступит скорее).

6.Пороговая: очередь получает обслуживание, если ее длина достигла заданной величины (порога).

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

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

Определим далее основную модель системы поллинга. Система имеет один сервер и N (N ≥ 2) очередей. Число мест для ожидания неограничено.

Входящий поток заявок в очередь Qi – простейший с параметром λi. Времена обслуживания заявок в очереди Qi независимы и одинаково распределены с функцией распределения Bi(t) со

∞

средним bi = R tdBi(t), вторым моментом b(2)i и преобразованием

i = 1, N.

Пусть ρi = λibi есть загрузка очереди Qi, а ρ = PN ρi –

i=1

загрузка системы в целом.

11