Содержание к диссертации
Введение
ГЛАВА 1 Построение моделей схем доступа в беспроводных сетях с трафиком многоадресной передачи и прерыванием обслуживания 11
1.1. Особенности управления радиоресурсами
в телекоммуникационных беспроводных сетях 11
1.2. Модели схем доступа с трафиком многоадресной передачи 20
1.3. Модели схем доступа с прерыванием обслуживания 26
1.4. Постановка задачи исследований 36
ГЛАВА 2 Анализ вероятностно-временных характеристик моделей схем доступа с трафиком многоадресной передачи 39
2.1. Мультисервисная модель с мультипликативным распределением вероятностей 39
2.2. Построение модели с групповым обслуживанием 45
2.3. Анализ вероятностно-временных характеристик формирования группы многоадресной передачи 50
ГЛАВА 3 Модель схемы доступа с прерыванием обслуживания 56
3.1. Построение модели совместного использования ресурсов 56
3.2. Рекуррентный алгоритм расчета стационарного распределения 63
3.3. Расчет и анализ среднего числа заявок в очереди с прерванным обслуживанием 68
ГЛАВА 4 Анализ вероятностных характеристик прерывания обслуживания модели схемы доступа к ресурсам совместного использования 79
4.1. Модель распределения нагрузки между ресурсами совместного и индивидуального использования 79
4.2. Рекуррентный алгоритм расчета вероятностных характеристик модели 95
4.3. Численный анализ вероятностных характеристик прерывания обслуживания 101
Заключение 108
Библиография
- Модели схем доступа с трафиком многоадресной передачи
- Построение модели с групповым обслуживанием
- Расчет и анализ среднего числа заявок в очереди с прерванным обслуживанием
- Рекуррентный алгоритм расчета вероятностных характеристик модели
Введение к работе
Актуальность исследования. В настоящее время в мире продолжается активное распространение телекоммуникационных беспроводных сетей четвертого поколения на базе технологии LTE (Long Term Evolution), поддерживающих высокие скорости передачи данных. Увеличение спроса на высокоскоростные мультимедийные услуги и повышение требований к качеству их предоставления, с одной стороны, и ограниченность частотного диапазона, с другой стороны, приводит к проблеме нехватки радиоресурсов. Решение проблемы может быть достигнуто как за счет более эффективного использования имеющихся ресурсов, так и посредством привлечения дополнительных.
Первым подходом к решению проблемы является передача данных в многоадресном режиме – «точка – много точек», – поддерживаемом подсистемой для предоставления мультимедийных услуг в широковещательном и многоадресном режимах (Multimedia Broadcast Multicast Service, MBMS). Одна из услуг – это восстановление файлов путем их повторной передачи в случае повреждения или потери. Многоадресный режим доступа к ресурсам используется при передаче файла по заданному расписанию или при превышении порога на число запросов на его восстановление. Поступающие запросы обслуживаются не последовательно, а группами.
Второй подход, основанный на привлечении дополнительных ресурсов, может быть реализован посредством совместного их использования владельцем и арендатором-оператором под контролем третьей стороны. Правила взаимодействия трех сторон определяет регулирующая система совместного использования лицензированных частот (Licensed Shared Access, LSA). Абсолютный приоритет доступа к ресурсам совместного использования имеет их владелец. Для оператора они временно доступны, что может приводить к прерыванию обслуживания пользователей при возврате ресурсов их владельцу.
Для анализа вероятностно-временных характеристик (ВВХ) схем доступа к
ресурсам в многоадресном режиме и при совместном их использовании, таких
как вероятность простоя ресурсов, средняя задержка передачи данных,
вероятность блокировки, вероятность прерывания обслуживания, применяются
математические модели, при построении и анализе которых используются
методы теории массового обслуживания и математической теории телетрафика.
Существенный вклад в исследования внесли следующие ученые: Г.П. Башарин,
П.П. Бочаров, В.М. Вишневский, Ю.В. Гайдамака, Б.В. Гнеденко, Г.П. Климов,
А.Е. Кучерявый, С.П. Моисеева, В.А. Наумов, А.В. Печинкин,
А.П. Пшеничников, В.В. Рыков, К.Е. Самуйлов, С.Н. Степанов, И.И. Цитович,
С.Я. Шоргин, С.Ф. Яшков, M.L. Chaudhry, V.B. Iversen, F.P. Kelly,
O. Martikainen, M.F. Neuts, K.W. Ross, T.L. Saaty, J. Virtamo и др.
В настоящее время в международных стандартах не определены конкретные алгоритмы восстановления файлов в многоадресном режиме, поэтому актуальной является задача разработки соответствующих схем доступа к ресурсам с учетом группового обслуживания запросов. Исследования схем доступа к ресурсам совместного использования проводились методами имитационного моделирования, поэтому также актуальной является задача разработки математических моделей доступа как к ресурсам совместного, так и индивидуального использования.
Целью диссертационной работы являются математические модели схем доступа в телекоммуникационных беспроводных сетях с трафиком многоадресной передачи и прерыванием обслуживания для анализа ВВХ восстановления файлов и совместного использования ресурсов. Научная новизна.
-
Разработанная мультисервисная модель с эластичным трафиком учитывает многоадресную передачу, в отличие от ранее известных моделей с эластичным трафиком, передаваемым только в одноадресном режиме.
-
В разработанной математической модели формирования группы многоадресной передачи в виде системы массового обслуживания (СМО) с групповым обслуживанием, время формирования группы определяется как сумма независимых случайных величин – временных интервалов, в отличие от известных СМО типа M /Ga,b /1 с групповым обслуживанием и временем формирования группы, определяемым числом заявок.
-
Для СМО с одновременными отказами ненадежных приборов и конечной очередью предложен рекуррентный алгоритм расчета среднего числа заявок в очереди с прерванным обслуживанием. Ранее данную характеристику можно было найти численным решением системы уравнений равновесия (СУР).
-
В разработанной модели схемы доступа к ресурсам совместного использования в виде СМО с одновременными отказами ненадежных приборов, происходит приоритетное занятие надежных приборов, в отличие от ранее известных СМО с приоритетным занятием одного ненадежного прибора, одним надежным прибором и бесконечной очередью.
Методы исследования. В работе используются методы теории вероятностей, теории марковских случайных процессов, теории массового обслуживания, математической теории телетрафика.
Обоснованность и достоверность результатов. Полученные в диссертации
результаты достоверны за счет использования строгих и апробированных
математических методов исследования. Обоснованность результатов
подтверждается вычислительным экспериментом, проведенным на базе близких к реальным исходных данных.
Теоретическая значимость. Теоретическая значимость результатов состоит в создании математического аппарата для анализа схем доступа с трафиком многоадресной передачи и с прерыванием обслуживания при совместном использовании ресурсов. Возможно дальнейшее развитие разработанного аппарата с учетом произвольного закона распределения временного интервала, из которых состоит время формирования группы многоадресной передачи. Модель с ресурсами совместного и индивидуального использования может быть применена для решения задачи оптимального выбора объема ресурсов совместного использования в условиях ограничений на вероятность прерывания обслуживания.
Практическая значимость. Алгоритмы расчета ВВХ – среднего времени формирования группы многоадресной передачи, среднего числа пользователей с прерванным обслуживанием, вероятности прерывания обслуживания, вероятности блокировки – могут применяться операторами беспроводных сетей, что позволит производить оценку уровня качества обслуживания.
Результаты работы использованы в рамках исследований по грантам РФФИ
№ 13-07-00953 «Исследование и разработка программных средств для анализа
моделей управления радиоресурсами в мобильных инфокоммуникационных
сетях четвертого поколения (LTE)» и № 15-07-03608 «Разработка методов
решения задач управления доступом в широкополосных беспроводных
инфокоммуникационных сетях на основе нелинейного анализа и
математической теории телетрафика», по проекту Федеральной целевой программы Министерства образования и науки РФ № 14.U02.21.1874 «Компоненты информационных технологий, модели и алгоритмы управления широкополосным доступом к услугам сетей подвижной связи следующих поколений 4G LTE», по гранту Фонда содействия развитию малых форм предприятий в научно-технической сфере № 6264ГУ2015 «Разработка программного обеспечения для управления распределением радиоресурсов в сети 5G с поддержкой временного выделения полосы частот LSA». Результаты диссертации внедрены в учебный процесс при подготовке выпускных работ бакалавров и магистров, обучающихся по направлению «Фундаментальная информатика и информационные технологии».
Апробация работы. Результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах: 15-ой Международной конференции «International Conference on Next Generation Wired/Wireless Networking» NEW2AN (Санкт-Петербург, 2015 г.); 6-ой Международной конференции «International Congress on Ultra Modern Telecommunications and Control Systems» ICUMT (Санкт-Петербург, 2014 г.); XXXII Международной конференции «International Seminar on Stability Problems for Stochastic Models» ISSPSM (Тронхейм, Норвегия, 2014 г.); VIII и IX Международной научно-практической конференции «Современные информационные технологии и ИТ-3
образование» (Москва, 2013 и 2014 гг.); VII, VIII и IX Международной
отраслевой научно-технической конференции «Технологии информационного
общества» (Москва, 2013 – 2015 гг.); Всероссийской научной конференции
«Современные тенденции развития теории и практики управления в системах
специального назначения» (Москва, 2013 г.); Всероссийской конференции (с
международным участием) «Информационно-телекоммуникационные
технологии и математическое моделирование высокотехнологичных систем»
ИТТММ (Москва, 2012 – 2015 гг.); 55-ой научной конференции МФТИ
«Проблемы фундаментальных и прикладных естественных и технических наук
в современном информационном обществе» (Москва, 2012 г.); конференции
«Телекоммуникационные и вычислительные системы» в рамках
Международного форума информатизации и Международного конгресса «Коммуникационные технологии и сети» (Москва, 2013 г.); Научном межвузовском семинаре «Современные телекоммуникации и математическая теория телетрафика» (Москва, 2015 г.).
Публикации. Основные результаты диссертационной работы изложены в 13 печатных работах, из которых [1–4] – в ведущих рецензируемых изданиях, рекомендованных ВАК РФ, [5–13] – в трудах международных и всероссийских научных конференций. Получены два свидетельства о государственной регистрации программы для ЭВМ [14,15]. В работах, выполненных в соавторстве, соискателю принадлежит: в [1] – модель формирования группы многоадресной передачи в виде СМО с групповым обслуживанием и временем формирования группы как суммы случайных интервалов; в [2,9] – модель совместного использования ресурсов в виде СМО с одновременными отказами ненадежных приборов и конечной очередью; в [5,10,14] – рекуррентный алгоритм расчета стационарного распределения вероятностей состояний; в [3,7,15] – алгоритм расчета и численный анализ среднего числа заявок в очереди с прерванным обслуживанием; в [6] – модель распределения нагрузки между ресурсами совместного и индивидуального использования в виде СМО с одновременными отказами ненадежных приборов, надежными приборами и конечной очередью; в [8] – мультисервисная модель с эластичным трафиком многоадресной передачи; в [4,11] – модель процесса подключения пользователей к услугам многоадресной передачи. Работы [12,13] выполнены диссертантом без соавторов.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Содержание работы изложено на 121 странице. Список литературы включает 147 наименований. Текст работы иллюстрируется 48 рисунками и 8 таблицами.
Модели схем доступа с трафиком многоадресной передачи
Центр вещательных услуг BM-SC (Broadcast Multicast Service Center) является основным элементом архитектуры подсистемы MBMS. Данный элемент выполняет функции управления и прекращения соединения, инициации, тарификации, обработки запросов пользователей, а также может выступать в роли входной точки для третьей стороны (контент-провайдера), желающей предоставлять свои услуги через подсистему MBMS вещания оператора. Такой элемент архитектуры, как сетевой контроллер (Multi-cell/multicast Coordination Entity, MCE), распределяет частотно-временные ресурсы для многосотовой MBMS передачи. Контроллер является логическим узлом, при этом он может быть интегрирован в БС, либо являться отдельным элементом сети. Описание остальных элементов архитектуры для краткости изложения не приводится. С данным описанием можно ознакомиться в [6].
Поскольку интерфейс между сетевым контроллером MCE и пользователем до сих пор не до конца стандартизован, существует множество решений по организации их взаимодействия. Одно из решений заключается в осуществлении сетевым контроллером мониторинга наличия пользователей, заинтересованных в услугах мультивещания. Изначально данный мониторинг предполагалось осуществлять путем подсчета точного количества пользователей, желающих подключить услугу. Однако подобная процедура требует большого количества ресурсов для обмена сигнальной информацией между пользователями и сетевым контроллером. Поэтому, для того чтобы снизить нагрузку на сеть, было предложено осуществлять мониторинг путем определения наличия в соте хотя бы одного пользователя, заинтересованного услуге мультивещания.
Описанные выше соображения послужили основой для ряда разработанных научно-исследовательскими коллективами предложений в части разработки новых стандартов 3GPP. В документе 3GPP R2-062271 был предложен сначала метод, основанный на временном мультиплексировании информации о различных услугах, а затем в документе 3GPP R2-072758 – метод, основанный на кодово временном мультиплексировании. Последний метод позволяет за один такт времени получать информацию сразу о группе услуг.
Приведем пример схемы мониторинга наличия хотя бы одного пользователя, заинтересованного в услуге мультивещания, описанной в документе 3GPP R2-072758. Сетевой контроллер (например, БС) широковещательно посылает запрос пользователям относительно услуг мультивещания по протоколу RRC (Radio Resource Control), используя логический канал управления MCCH (MBMS pointo-multipoint Control Channel). Если пользователь заинтересован в услуге, то он посылает положительный ответ по транспортному каналу случайного доступа RACH (Random-Access Channel), который отображается на физический канал случайного доступа PRACH (Physical Random Access Channel) [19, 75]. Передача по каналу случайного доступа всегда представляет собой преамбулу и циклический префикс. При этом длина циклического префикса может быть разной в зависимости от радиуса сот. Передача данных занимает полосу частот шириной 1,08 МГц, что соответствует 6 блокам PRB, и может осуществляться только один раз в течение временного интервала, соответствующего одному подкадру радиосигнала. Передачи могут осуществляться с частотой следования подкадров один раз в 20 мс.
После того, как получен положительный ответ от первого пользователя в соте относительно данной услуги, контроллер широковещательно посылает подтверждение получения ответа, а затем останавливает процедуру мониторинга относительно этой услуги для всех пользователей данной соты. Данная процедура мониторинга длится 20 мс. Диаграмма мониторинга наличия в соте пользователей, заинтересованных в услуге мультивещания, представлена в документе 3GPP R2-072758 и в [6].
Выделяют четыре типа услуг, предоставляемых c использованием подсистемы MBMS: потоковые услуги (аудио, видео), услуги по загрузке файлов, так называемые «карусельные» услуги, являющиеся комбинацией потоковых услуг (текст и неподвижные изображения) и услуг по загрузке файлов, а также телевизионные услуги [70]. При загрузке файлов с использованием подсистемы MBMS зачастую возникают потери или повреждение сегментов этих файлов, что является неприемлемым с учетом установленных в стандартах высоких требований к качеству предоставляемых услуг в сетях LTE. Для решения данной проблемы применяется восстановление поврежденных файлов (file repair procedure) [7, 8, 12, 74, 77, 105, 114, 117, 138], осуществляемое в одноадресном, широковещательном и многоадресном режимах. Безусловно, наиболее эффективно использовать частотно-временные ресурсы сети позволяет многоадресный режим восстановления файлов, с использованием которого сегменты поврежденного файла передаются на одинаковой частоте только пользователям сети, отправившим запрос на восстановление данного файла в течение случайного временного интервала. При этом стоит заметить, что в спецификациях по MBMS 3GPP TR 26.946, 3GPP TR 26.851, 3GPP TS 26.346 [74] основное внимание уделено одноадресному режиму восстановления файлов, тогда как для многоадресного режима не приведены пошаговые алгоритмы формирования группы многоадресной передачи, а только кратко описана идея подхода.
Помимо описанных выше технологических изменений, существуют другие методы решения проблемы нехватки ресурсов в современных мобильных сетях. Часть из них связана с усовершенствованием механизмов управления радиоресурсами (Radio Resource Management, RRM) [76]. На настоящий момент к данным механизмам относятся [76]: управление доступом к ресурсам сети (Radio Admission Control, RAC), управление несущими (Radio Bearer Control, RBC), управление мобильностью (Connection Mobility Control, CMC), управление динамическим распределением ресурсов (Dynamic Resource Allocation, DRA), управление межсотовой интерференцией (Inter-Cell Interference Coordination, ICIC). Расширить частотно -временные ресурсы операторов можно также посредством административного соглашения совместного использования спектра.
Существующие модели совместного использования спектра, такие как, например, совместное использование нелицензируемого спектра (Wi-Fi сети), не имеют необходимых методов защиты от интерференции и не гарантируют требуемого качества обслуживания [129]. В отличие от этих моделей, находящаяся в разработке регулирующая система совместного использования лицензированного спектра LSA [27, 87, 95, 98, 99, 100, 103, 104, 129] позволяет осуществлять более эффективное управление распределением спектра между ограниченным числом сторон в соответствии с четкими заранее определенными правилами.
Разработки по данной системе начались в 2011 году в Европе. По поручению Европейской комиссии (Еuropean Сommission, ЕC) Группа по политике в области использования спектра (Radio Spectrum Policy Group, RSPG) впервые высказала свое мнение об LSA в документе RSPG 13-538 в ноябре 2013 года. В результате этого, в начале 2014 года Европейской комиссией был выпущен мандат на стандартизацию мобильных/фиксированных сетей (Mobile/Fixed Communications Networks, MFCN) на частотах 2.3 – 2.4 ГГц [95]. В настоящее время совместное использование спектра LSA поддерживается Европейской конференцией администраций почтовых служб и служб связи (European Conference of Postal and Telecommunications Administrations, CEPT) для MFCN [104]. С другой стороны, Европейский институт стандартизации в области телекоммуникации (European Telecommunications Standards Institute, ETSI) получил мандат M/512 на стандартизацию LSA. К настоящему времени был выпущены стандарт ETSI TR 103 113 [98] и два драфта ETSI TS 103 154 [99] и ETSI TS 103 235 [100]. LSA представляет собой официально утвержденное совместное использование одной и той же полосы частот по крайней мере двумя сторонами – владельцем (имеющим права на полосу частот) и арендатором (временным пользователем полосы частот) – согласно заранее утвержденному соглашению. Другими словами, LSA гарантирует, что владелец сохраняет право использования полосы частот везде и всегда без потери качества, а арендатор не использует данную полосу, если она понадобилась владельцу (или, по крайней мере, использует ее, не создавая интерференции с сигналом владельца) [98, 118, 121]. В роли владельца может выступать, например, международная координирующая организация, государство, оператор. В роли арендатора может выступать, например, оператор. В настоящее время в различных станах выделен диапазон частот для использования LSA. В Европе, Австралии, Китае, Индии для LSA используются частоты 2.3–2.4 ГГц, в Корее, Малайзии и Гонконге – 2.3–2.39 ГГц, в Новой Зеландии и Вьетнаме – 2.3–2.395 ГГц [98].
На рис. 1.2 представлена архитектура LSA [98, 118, 121], и показаны задействованные ключевые участники: владелец LSA полосы (Incumbent), регулятор (National Regulatory Authority, NRA) и арендатор LSA полосы (LSA Licensee). Владелец сдает LSA полосы в аренду и получает дополнительную экономическую выгоду. Регулятор согласовывает права использования LSA полосы между владельцем и арендатором. Арендатор получает доступ к LSA полосе в соответствии с правилами договора аренды.
Построение модели с групповым обслуживанием
Таким образом, в данном разделе построена модель управления доступом к ресурсам при передаче сегментов файлов разных типов в многоадресном режиме, а также получена формула для расчета среднего времени передачи сегмента файла. Данная модель описывает процедуру восстановления файлов с момента, когда группы многоадресной передачи разных типов сегментов файлов сформированы, и выделяются ресурсы для их обслуживания. В следующем разделе будет исследован второй аспект восстановления файлов в многоадресном режиме, а именно, процесс формирования группы многоадресной передачи. Модель формирования группы многоадресной передачи строится в виде СМО с групповым обслуживанием и временем формирования группы как суммы случайных интервалов, при этом вводится упрощение: число С приборов (пиковая скорость передачи сегмента файла) принимается равным единице.
Целью данного раздела является построение модели формирования группы многоадресной передачи для восстановления файлов в виде одноканальной СМО с групповым обслуживанием и с временем формирования группы как суммы случайных интервалов (задача № 2). Для данной модели заявкой является поступление запроса пользователя на восстановление файла.
Рассмотрим СМО, состоящую из одного обслуживающего прибора и конечной очереди длины г. На систему поступает пуассоновский поток заявок с параметром є . Пусть tt, і 0 - момент времени поступления /-ой заявки, при этом в момент ґ0=0 система свободна. =tii_1, / 0 - случайная величина (СВ) времени между поступлениями (/-1)-ой и /-ой заявками. Обслуживание заявок производится группами. При этом группа может начать обслуживаться только в моменты r-, j 0, по достижению которых в очереди находится хотя бы одна заявка, а прибор не занят обслуживанием предыдущей группы. Время формирования каждой группы заявок складывается из СВ hj =zjj_1J 0, распределенных по экспоненциальному закону с параметром у. Обслуживание группы начинается в момент г-,у 0 завершения формирования этой группы и завершается в момент тк,к 0. г/к =тк—т-, к 0 - СВ длительности обслуживания -группы заявок, распределенная по экспоненциальному закону с параметром к. Пусть М(ґ) - число заявок в очереди в момент t, У (7) - состояние прибора в момент t. При этом: Г0, если прибор свободен в момент t, 1, если прибор занят в момент /. Тогда функционирование системы описывает составной марковский СП {(M(t),Y(t)),t 0} над пространством состояний
На рис. 2.6 представлена временная диаграмма функционирования системы, на которой показаны различные сценарии формирования группы в зависимости от состояний прибора и поступления заявок: группа сформирована за один интервал (A1, А2), за два интервала по причине занятости прибора (А3 + А4), за два интервала по причине отсутствия заявок в очереди (А5 + А6). Поступление заявок и изменение состояния прибора Составив диаграмму интенсивностей переходов так, как это показано на рис. 2.7, можно получить СУГБ в виде аг(0,0) = юг(0,1),
Из диаграммы интенсивностей переходов (рис. 2.7) видно, что СП {(M(t),Y(t)),t 0\ не является обратимым. Стационарное распределение тг(т,у),(т,у)еЛ вероятностей состояний может быть получено из СУГБ (2.11) линейными преобразованиями.
В данном разделе проводится анализ ВВХ (2.24) – (2.26) модели процесса формирования группы многоадресной передачи, построенной в предыдущем разделе, а также численно решается задача оптимизации длины случайного интервала формирования группы многоадресной передачи при близких к реальным исходных данных. Рассмотрим соту сети LTE с пиковой пропускной способностью 50 Мбит/с. Поскольку в соответствии с обзорами компании Cisco Systems [91], трафик, генерируемый при передаче данных, в 2015 году составляет 38 % от общего объема мобильного трафика, будем рассматривать только часть пропускной способности соты сети, соответствующей передаче данных.
Таким образом, будет считать, что сегменты файлов передаются пользователям со скоростью 19 Мбит/c. Отметим, что в качестве единицы пропускной способности примем Рис. 2.8, 2.9 и 2.10 иллюстрируют зависимости вероятности В блокировки запроса пользователя на восстановление сегмента файла, средней задержки W начала восстановления сегмента файла и вероятности Р \у = 0} простоя ресурсов от увеличения размера сегмента файла и суммарной интенсивности а предложенной нагрузки, создаваемой запросами пользователей на восстановление сегмента файла. По графикам видно, что с ростом нагрузки вероятность блокировки и средняя задержка начала восстановления файла увеличиваются, а вероятность простоя ресурсов наоборот уменьшается. Однако на данные характеристики оказывает влияние и средняя длина сегмента файла. Чем больше сегмент файла, тем дольше он передается и занимает ресурсы сети, и следовательно, с меньшей вероятностью они простаивают. С другой стороны, чем дольше заняты ресурсы сети, тем больше средняя задержка начала передачи сегмента файла следующей группе пользователей. Уменьшение длины сегмента файла влечет за собой увеличение вероятности блокировки. Это связано с тем, что при фиксированной интенсивности предложенной нагрузки, равной а = єк1 = —, уменьшение длины сегмента файла влечет за собой увеличение интенсивности поступления запросов пользователей в систему, а значит, вероятность блокировки увеличивается.
Расчет и анализ среднего числа заявок в очереди с прерванным обслуживанием
Как можно заметить, введенный СП позволяет получить формулу расчета среднего числа прерванных пользователей, ожидающих возобновления обслуживания (среднего числа заявок в очереди с прерванным обслуживанием). Однако расчет по данной формуле имеет большую вычислительную сложность.
Для того, чтобы значительно сократить сложность расчета и анализа данной характеристики, введем новый СП путем объединения типов заявок в очереди, т.е. т = т1+т2. Тогда функционирование системы можно описать двумерным марковским СП{(л ),М(/)),/ 0} над пространством состояний: % = {(п,т):(п,0), « = 0,...,С; (С,т), т = 1,...,г-С; (0,т), т = 1,...,г], (3.14) где п - число заявок на ненадежных приборах, а т = т1+т2 - число заявок в очереди. Отметим, что пространство состояний (3.14) можно разбить на три подмножества: {(«,0),« = 0,...,с} соответствует состояниям, когда приборы исправны и очередь пуста, {(С,т),т = 1,...,г-С} - состояниям, когда приборы исправны и очередь не пуста, {(0,т),т = 1,...,г} - состояниям, когда приборы неисправны. При этом в очереди всегда зарезервированы места для заявок, обслуживающихся на приборах, чтобы, в случае их отказа, заявки могли ожидать возобновления обслуживания. Составим диаграмму интенсивностей переходов (рис. 3.4) с учетом трех групп состояний: приборы исправны и очередь пуста, приборы исправны и очередь не пуста, приборы неисправны.
Для расчета стационарного распределения р(п,т), (п,т)є% вероятностей состояний модели в данном разделе разработан рекуррентный алгоритм. Обозначим q(n,m) ненормированную вероятность того, что число заявок на ненадежных приборах п, число заявок в очереди т. Тогда справедлива лемма 3.1. Лемма 3.1. Ненормированные вероятности q(n,m) вычисляются по рекуррентным соотношениям
Доказательство. Докажем, что ненормированные вероятности q(n,m) вычисляются по рекуррентным соотношениям (3.24)-(3.33).
Диаграмму интенсивностей переходов состояний модели представим с учетом разбиения пространства состояний на подмножества, как показано на рис. 3.5. В частности, в отдельные группы объединены состояния, для которых уравнения СУГБ (3.15)–(3.23), следовательно, и рекуррентные соотношения 1) -5) имеют разный вид.
В данном разделе разработан алгоритм расчета среднего числа заявок, ожидающих начала обслуживания, и среднего числа заявок в очереди с прерванным обслуживанием.
Среднее число Q заявок в очереди, рассчитывающееся по формуле (3.37), состоит из среднего числа Q1 заявок, ожидающих начала обслуживания, и среднего числа Q2 заявок в очереди с прерванным обслуживанием Q = Q1+Q2=Y,k-p{m1=k} + yZk-p{m2 = kl (3.51) к=1 к=1 где Р{щ=к} - вероятность того, что к заявок ожидают начала обслуживания, Р{т2 = к} - вероятность того, что обслуживание к заявок было прервано. Однако формулы для расчета двух последних характеристик Q1 и Q2 не могут быть получены в явном виде из формулы (3.37), поскольку для каждого состояния (п,т) невозможно определить, какое количество из т заявок в очереди составляют заявки, ожидающие начала обслуживания, и заявки с прерванным обслуживанием. Найти характеристики Q1 и Q2 позволяет вероятностный подход, основанный на свойствах СВ, являющейся минимумом других независимых экспоненциально распределенных СВ. Для нахождения распределения вероятностей Р \т1 = к} того, что к заявок ожидают начала обслуживания, будем использовать формулу полной вероятности Р{щ=к}= X p(n,m)Ak(n,m), k = 0,...,r-1, (3.52) где - вероятность того, что к заявок ожидают начала обслуживания в состоянии (п,т).
Доказательство. Для доказательства формул (3.53)-(3.55) воспользуемся диаграммой интенсивностей переходов, изображенной на рис. 3.5. Выделим конкретное состояние (0,т). В это состояние можно попасть двумя способами: перейдя из состояния (ш,0) с интенсивностью ар(т,0) (в результате отказа приборов), либо перейдя из состояния (0,ш-1) с интенсивностью Лр(0,т-1) (в результате поступления заявки) (рис. 3.11). я а\ Рис. 3.11. Возможные переходы в состояние (0,т) Используя данные рассуждения, получаем, что условная вероятность попадания из состояния (т,0) при условии нахождения в состоянии (0,т) равна 7аР(т,0/ (3.56) ар(т,0) + Ар(0,т-1) Докажем формулу (3.56), используя лемму о минимуме независимых экспоненциально распределенных СВ [13]. Пусть Е,1 - СВ времени нахождения приборов в исправном состоянии при условии, что после их отказа система окажется в состоянии (0,т), распределенная по экспоненциальному закону с параметром сср{т,0). Тогда Е,2 - СВ времени между моментами поступления двух заявок, при условии, что с поступлением новой (второй) заявки система окажется в состоянии (О, т), распределенная по экспоненциальному закону с параметром Ар(0,т — Ґ) (рис. 3.12).
В этих состояниях однозначно можно определить, что заявки в очереди - это заявки, ожидающие начала обслуживания, а следовательно, и их количество определяется однозначным образом.
Для доказательства формул (3.62), (3.63) приведены фрагменты диаграммы интенсивностей переходов, демонстрирующие формирование вероятностей Ак(п,т) для подмножеств (3) и (4) (рис. 3.14), поскольку в принадлежащих этим подмножествам состояниях нельзя однозначно определить число заявок, ожидающих начала обслуживания. Пунктирными стрелками показаны переходы между состояниями модели, а сплошными стрелками – маршруты формирования числа k заявок, ожидающих начала обслуживания. Маршрут состоит из двух частей. Сплошные стрелки сверху вниз обозначают переход между состояниями в результате отказа приборов, а стрелки слева направо – в результате поступления новых заявок в период пребывания приборов в неисправном состоянии. Числа рядом со стрелками обозначают, какое число k заявок, ожидающих начала обслуживания, сформировалось в результате таких переходов.
Рекуррентный алгоритм расчета вероятностных характеристик модели
В [13, 83] показано, что элемент а- матрицы A определяет интенсивность перехода СП из состояния / в состояние j, при этом может произойти только одно «элементарное» событие: поступление или обслуживание заявки, а также отказ или восстановление приборов. Тогда определяющие такие переходы ненулевые элементы матрицы расположены в соответствии со следующим принципом: - наддиагональные блоки Ак описывают переходы СП (N1(t),N(t),M(t),S(t)) из состояний множества Щ. в состояние множества Жк+1,к = 0,...,С1 + г-1; - поддиагональные блоки М . описывают переходы из состояний множества %к в состояние множества %к_1, к = 1,...,С1+г; - диагональные блоки N . описывают переходы внутри множества Щ, к = 0,...,С1+г.
Соответственно, ненулевые элементы блоков Ак, Мк и Щ будут определяться соотношениями (4.6)-(4.8) по построению. Поясним, как формируется выражение ) в формуле (4.8). Это выражение показывает суммарную интенсивность выхода из рассматриваемого состояния. Как было описано выше, существует четыре типа переходов из состояния (n1,n,m,s) : в случае поступления новой заявки с интенсивностью Л при условии, что в системе находится п1 + п + т С1 + г заявок; в случае обслуживания заявки с интенсивностью /л на одном из п1 + п п± + тг приборах; в случае отказа ненадежных приборов с интенсивностью а при условии, что они были исправны; в случае восстановления ненадежных приборов с интенсивностью /? при условии, что они были неисправны. Таким образом, суммарная интенсивность выхода из рассматриваемого состояния равна Л1{п1+п + т С1+г} + (п1+п) + а8 +(3(1-s). Докажем теперь, что размерность блоков %к задается формулой (4.5). Поскольку в каждом блоке %к множество состояний разделяется на два подмножества с учетом состояния ненадежных приборов - состояния, когда ненадежные приборы исправны, и состояния, когда ненадежные приборы неисправны, будем отдельно подсчитывать число состояний в каждом подмножестве. Так как в данной модели имеется два типа приборов - надежные и ненадежные, то число состояний в каждом блоке равно числу возможных вариантов распределения заявок между двумя типами приборов. Рассмотрим первый случай, когда суммарное число заявок в системе к = О,..., С. Если ненадежные приборы исправны, то число способов распределения к заявок между двумя типами приборов определяется по формуле сочетаний с повторениями из 2 по А: и равно к +1. Если же ненадежные приборы неисправны, то все заявки распределятся только между надежными приборами, следовательно, в этом подмножестве имеется только одно состояние. Суммируя состояния в каждом подмножестве, получаем, что dim . = к + 2, к = О,.. .,С.
Пусть теперь суммарное число заявок в системе к = С + 1,...,Сх и ненадежные приборы исправны. Поскольку обслуживающихся на ненадежных приборах заявок может быть не больше С, значит, в данном случае к —С заявок всегда будут обслуживаться надежными приборами. Следовательно, осталось распределить только С заявок между двумя типами приборов. По формуле сочетаний с повторениями из 2 по С получаем, что таких вариантов С +1. Если же ненадежные приборы неисправны, то все заявки будут обслуживаться надежными приборами, а значит, имеется всего один вариант распределения заявок между одним типом приборов. Таким образом, в данном случае dim%=C + 2, к = С + 1,...,Сх.
В третьем случае имеем к = С1+1,...,С1+С заявок. В данном случае пойдем от обратного и будем перераспределять свободные места на приборах между двумя типами приборов. Если ненадежные приборы исправны, то суммарное число свободных приборов будет зависеть от числа к заявок в системе и равно Сх +С-к. По формуле сочетаний с повторениями из 2 по Сх +С-к получим, что число способов распределения свободных мест на приборах между двумя типами приборов равно Сх+С-к + 1. Если же ненадежные приборы неисправны, то аналогично предыдущим случаям получаем один вариант. Следовательно, АішЖк=Сх+С + 2-к, к = С1+1,...,С1+С.
Наконец, рассмотрим последний вариант, когда к = Сх+С + 1,...,Сх+г. Если ненадежные приборы исправны, то существует только один вариант распределения заявок между двумя типами приборов: Q заявка будет обслуживаться на надежных приборах, С заявок на ненадежных приборах, остальные к-Сх-С будут ожидать обслуживания в очереди. Аналогично, когда ненадежные приборы неисправны, заявки распределятся однозначно: Q заявка будет обслуживаться на надежных приборах, а к-Сх - попадет в очередь для ожидания. Следовательно,
Таким образом, в данном разделе построена модель совместного использования ресурсов в виде СМО с одновременными отказами ненадежных приборов, надежными приборами и конечной очередью. Для этой модели матрица интенсивностей переходов получена в блочном трехдиагональном виде, а также предложена формула для основного показателя эффективности - вероятности прерывания обслуживания заявок.