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

ВВЕДЕНИЕ.

1. ПРОБЛЕМЫ ПРОГНОЗИРОВАНИЯ И УПОРЯДОЧЕНИЯ ЗАЯВОК В СИСТЕМАХ ПЕРСОНАЛЬНОГО РАДИОВЫЗОВА.

1.1. Нейросетевые модели для прогнозирования потока заявок в СПРВ.

1.2. Упорядочение заявок в очереди СПРВ комбинаторными методами.

1.3. Методы решения NP-полных задач.

1.4. Задача "Коммивояжер" — область тестирования новых методов.

1.5. ВЫВОДЫ ПО ПЕРВОЙ ГЛАВЕ.

2. ПРОГНОЗИРОВАНИЕ ПАРАМЕТРОВ ВХОДЯЩЕГО ПОТОКА ЗАЯВОК С ПОМОЩЬЮ НЕЙРОННЫХ СЕТЕЙ.

2.1. Целочисленная модель нейронной сети.

2.2. Целочисленные алгоритмы обучения сети.

2.3. Постановка и свойства задачи прогнозирования параметров.

2.3.1. Свойства задачи. Линейное предсказание параметров.

2.3.2. Нейросетевые методы прогнозирования.

2.4. Прогнозирование в спектральной области на основе нейросетей.

2.4.1. Линейное предсказание в спектральной области.

2.4.2. Нейросетевое прогнозирование в спектральной области.

2.5. ВЫВОДЫ ПО ВТОРОЙ ГЛАВЕ.

3. УПОРЯДОЧЕНИЕ ЗАЯВОК В ОЧЕРЕДИ МЕТОДАМИ КОМБИНАТОРНОЙ ОПТИМИЗАЦИИ.:.

3.1. Способы постановки задачи упорядочения.

3.1.1. Статическое упорядочение.

3.1.2. Упорядочение в реальном времени.

3.2. Доказательство NP-полноты задачи полиномиальным преобразованием

3.3. Последовательный и параллельный алгоритмы оценки качества.

3.4. Способы учета информации о качестве.

3.5. Экспериментальное исследование методов с оценкой качества.

3.6. ВЫВОДЫ ПО ТРЕТЬЕЙ ГЛАВЕ.

4. ИССЛЕДОВАНИЕ МЕТОДОВ ПРОГНОЗИРОВАНИЯ И УПОРЯДОЧЕНИЯ ЗАЯВОК И ИХ ВНЕДРЕНИЕ В СИСТЕМАХ ПЕРСОНАЛЬНОГО РАДИОВЫЗОВА.

4.1. Экспериментальная апробация методов прогнозирования входящего потока заявок.

4.2. Повышение производительности системы персонального радиовызова в режиме максимальной нагрузки.

4.3. Разработка программного комплекса, реализующего методы упорядочения и прогнозирования потока вызовов в СПРВ.

4.4. ВЫВОДЫ ПО ЧЕТВЕРТОЙ ГЛАВЕ.

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

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

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

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

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

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

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

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

Работа выполнена в рамках тематического плана НИР, финансируемых из средств федерального бюджета по единому заказ-наряду Министерства образования Российской Федерации, номер государственной регистрации 01.99.0006644.

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

Исходя из этого, в работе решались следующие задачи:

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

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

4. Формирование модели упорядочения заявок в очереди системы на основе методов комбинаторной оптимизации. Исследование ИР-полноты задачи упорядочения. Построение модифицированных комбинаторных методов решения.

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

Методы исследования основаны на теории нейронных сетей, теории ИР-полноты, методах многомерной и комбинаторной оптимизации, имитационном моделировании.

Научная новизна работы. В работе получены следующие результаты:

1. Предложена нейросетевая модель с целочисленными операциями и "аналоговыми" сигналами. Модель снижает затраты вычислительных ресурсов, позволяет регулировать точность и занимаемый сетью объем памяти.

2. Разработан нейросетевой метод прогнозирования квазипериодических функций в многомерной спектральной области. Метод обеспечивает длительный прогноз без потери точности, сжимает входные данные задачи и сокращает необходимый объем нейросетевых вычислений.

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

4. Доказана NP-пoлнoтa задачи упорядочения заявок в очереди в различных вариантах постановки, исследованы свойства задачи и разработаны комбинаторные методы для ее решения.

Практическая ценность результатов.

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

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

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

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

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

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

3. Программная реализация целочисленной нейросети на языке С++ может быть применена в ЭВМ с целочисленной арифметикой: однокристальных ЭВМ и микроконтроллерах, встраиваемых в портативные устройства. Программный модуль комбинаторной оптимизации с локальной оценкой качества обеспечивает квазиоптимальное решение более 300 известных труд нор ешаемых задач.

Реализация и внедрение. Прогнозирование входящего потока заявок внедрено и используется в реальных системах персонального ра7 диовызова, что подтверждено актами о внедрении. Алгоритм решения задачи упорядочения интегрирован в программное обеспечение СПРВ. Разработанные программы внедрены в пейджинговых центрах "НГС-пэйдж" (Воронеж); Информ-Экском (Москва), Пэйджнет (С.Петербург).

Апробация работы. Основные результаты работы докладывались и обсуждались на Международной конференции "Радиолокация, навигация, связь" (Воронеж, 2001 г.), Всероссийской конференции "Нейрокомпьютеры и их применение" (Москва, 2000 г.), Республиканской конференции "Современные проблемы информатизации" (Воронеж, 1998 г.), научно-практической конференции Высшей школы МВД (Воронеж, 1998 г.).

Публикации. Автором опубликовано 11 печатных работ по теме диссертации.

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

4.4. ВЫВОДЫ ПО ЧЕТВЕРТОЙ ГЛАВЕ

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

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

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

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

U3H4, Мосюа дом 7, стр.3

Дtu Tenerpuafc Москва, 114 "Буква"

Teuerelfa 112338 'Буква" * ч*" nfr"' 394030, t. Воронеж, ул. Ппехавожжы, S3 199г. №.

Телефоны Секретарь m 12-22

Бухгалтерия 239-17-47 Факс 235-00-03

Телефоны Оператор Фаис

77-79-84 71-85-83 77-79-86

Г "Утверждаю*] начальник Воронежского цеха связи АООТ "Нефтегаэспецсвяэьстрой" <*&теешм* Измайлов В.Л.

15" апреля 2001 г.

АКТ о внедрении результатов кандидатской диссертационной работы Заенцева Ивана Витальевича

Настоящий Шсг составлен комиссией в составе: председатель комиссии Грипэров Виктор Ильичи члены коииссии: Лебедева Виктория Вячеславовна, Бондарева Ирина Ивановна в той, что в системе персонального радиовыэова АООТ "Нефтегаэспецсаязьстрой", г. Воронеж ( "НГС-ЛВЙДЖ" ) внедрены и применяются результаты исследований диссертационной работы Заенцева И.В. по следующий направлениям:

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

2. Упаковка сообщений в канале связи путем оптимизации порядка их обработки.

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

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

2. Оптимизация порядка обработки сообщений с целью минимизации суммарного времени обработки. Минимизация осуществляется методом с локальной оценкой качества решения при длине очереди до 90 сообщений.

Эффект от внедрении

1. Средняя относительная погрешность прогнозирования в задаче предсказания загрузки составила 26%.

2. Среднее время обучения для входных данных за б месяцев составляет 45 с. при использовании процессора Intel Celeron 500 MHz и 128 Mb RAM.

3. Среднее время прогнозирования на период б месяцев: 2.2 с .

4. Эффективность упаковки сообщений в канале при максимальной загрузка составила 72% . После внедрения модуля упорядочения средний коэффициент использования канала при максимальной загрузке составил 91%.

Внедрение результатов работы позволило сократить задержки в обслуютеании-вббнентрв, повысить пропускную способность канала в режиме максимальной^з|1ВД^£получит^1нфорыа-цию, необходимую для оптимизации структуры локальной выч

Председатель комиссии Член ютмиссии Член комиссии ригороэ В,Pl. Лебедева В.В. Бондарева И.И.

ИНФОРМ-ЭКСКОМ

Пей джин говая компания

117970, Россия, Москва, ул. Житная, 14 Тел./Те1. (7)-(095)-755-65-0^aKC/Fax(7)-(095)-938-5270 '"Ж

-Утверждаю"

ННФОРГенеральный директор ;ЭКСКО^о "Инфпрм-Экском "

Спицын А.Г. 2000 г.

АКТ о внедрении результатов диссертационной работы Заенцева И.В.

Настоящий акт составлен в том, что в действующем центре персонального радиовызова ЗАО "Ииформ-Эюском", г. Москва, внедрены и эксплуатируются результаты исследований указанной диссертационной работы по следующим темам:

1. Прогнозирование интенсивности входящего потока заявок на основе нейронных сетей в системах массового обслуживания.

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

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

2. Упорядочение сообщений в очереди для системы персонального радиовызова. Входные данные поступают в реальном времени и представляют собой поток сообщений, каждое из которых имеет параметры: {начальный кадр, длина, текущая задержка, скорость передачи}. Выходные данные: перестановка сообщении, обеспечивающая минимальное количество пустых кадров и преамбул при передаче по протоколу РОСБАС. Должно обеспечиваться выполнение условий: а) максимальная теку щая задержка любого сообщения не должна превышать ладанной величины: б) промежуток времени между преамбулами РОСБАО не должен превышать заданного значения.

Результаты внедрения и экономическая эффекгавноегь 1. Задача прогнозирования интенсивности

1. Средняя относительная погрешность прогнозирования в задаче п. I составила 24 %.

2. Среднее время обучения для входных данных за 4 недели составляет 13 с. при использовании процессора AMD К6-2 450 МГц и 64 Мб ОЗУ.

3. Среднее время прогнозирования на период 1 нсд.: 0.8 с.

2. Задача упорядочения сообщений

4. Коэффициент использования радиоканала при максимальной нагрузке для терминала 2с1гоп-16 составил 74.5%, После внедрения системы пакетирования средний коэффициент использования канала при максимальной нагрузке составил 91 %, т.е. пропускная способность канала возросла в 1,22 раз.

Технический директор Иро-** Трахтеиберг С. !>.

Составлен в том, что в пейджинговой компании "ПЭЙДЖНЕТ" (Санкт-Петербург) внедрены и используются результаты, полученные в ходе исследований по теме: "Дисциплина очереди пейджинговых сообщений в протоколе РОСЗАС'. Эти исследования проведены в рамках работы И.В. Заенцева, представленной на соискание ученой степени кандидата технических наук.

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

На вход модуля поступает информация о сообщениях в очереди на отправку. Для каждого сообщения известны:'

1. Текущая задержка, уже накопленная на данный момент, в кадрах РОСвАС.

2. Номер начального кадра протокола РОСвАЗ, 0.7.

3. Скорость передачи сообщения: 512, 1200 или 2400 бод.

4. Длина сообщения в кадрах РОСЗАС.

На выходе программного модуля формируются данные о моментах времени (в кадрах РОСЭАС), в которые начнется передача каадого из сообщений в очереди. Моменты времени определяют также порядок отправки сообщений, отличный от порядка поступления.

Перестановка, формируемая модулем, должна быть квазиоптимальной по следующим условиям:

1. Число пустых кадров при отправке должно быть минимальным.

2. Количество преамбул РОСБАС должно быть минимальным, но интервал между двумя соседними преамбулами не может превышать предельно допустимого для устойчивого приема.

3. Текущая задержка любого сообщения при его отправке не должна превышать максимально допустимой.

В ходе тестирования модуля получены следующие данные.

1. Коэффициент использования радиоканала без применения модуля составил 82%.

2. После встраивания модуля упорядочения коэффициент использования канала

94,3%.

3. Пропускная способность канала возросла в 1,15 раз.

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

Технический директор ООО " ПЭЙДЖНЕТ "

Ссменьков С. М,

ЗАКЛЮЧЕНИЕ

1) Предложена нейросетевая модель с целочисленными операциями, которая позволяет регулировать точность представления сигналов, сократить требуемый объем памяти по сравнению с моделями с плавающей запятой, перенести нейросети на дешевые однокристальные микро-ЭВМ с целочисленной арифметикой.

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

3) Разработанная методика краткосрочного нейросетевого прогнозирования потока заявок в СПРВ с преобразованием прогнозируемой функции в многомерную по каждому из ее периодов сокращает время обучения сети и повышает точность прогноза.

4) В работе доказана КР-полнота задачи упорядочения и предложен комбинаторный алгоритм локальной оценки качества в решении ОТ-полных задач. Применение локальной оценки качества в известных комбинаторных методах дает рост скорости сходимости и точности результата.

5) На основе предложенного алгоритма развиты комбинаторные методы упорядочения заявок в очереди. Упорядочение заявок в центре СПРВ повысило производительность канала в часы пик на 20%.

6) Разработан комплекс программ, содержащий модель канала СПРВ с различными способами упорядочения заявок на основе комбинаторных методов и нейросетевой модуль, прогнозирующий входящий поток вызовов. Комплекс позволяет исследовать работу центра СПРВ с целью создания алгоритмов упорядочения заявок и прогнозирования входящего потока вызовов. Благодаря объектно-ориентированному подходу алгоритмы могут быть непосредственно внедрены из модельной среды в действующий центр СПРВ.

7) Внедрение предложенного комплекса в пейджинговых компаниях в г. Москве, С.-Петербурге, Воронеже позволило сэкономить 15-20% частотных ресурсов, сократить задержку передачи сообщений, распределять смены персонала на основе прогнозированной загрузки радиоцентра и принесло ощутимый экономический эффект.

145

1. Ивченко Г.И., Каштанов В.А., Коваленко И.Н. Теория массового обслуживания: Учеб. пособие для вузов. М.: Высш. школа, 1982. - 256 с.

2. Саати Т.Л. Элементы теории массового обслуживания и ее приложения: Пер. с англ. М.: Сов. радио, 1971. - 520 с.

3. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. 2-е изд., перераб. и доп. - М.: Наука, 1987. - 336 с.

4. Бронштейн О.И., Духовный И.М. Модели приоритетного обслуживания в информационно-вычислительных системах. -М.: Наука, 1976. 220 с.

5. Глушков В.М., Гусев В.В., Марьянович Т.П., Сахнюк М.А. Программные средства моделирования непрерывно-дискретных систем. Киев: Наукова думка, 1975.

6. Ivakhnenko A.G., Krotov G.I. and Cheberkus V.I. Harmonic and exponential-harmonic GMDH algorithms for long-term prediction of oscillating processes. Part I. Sov. J. of Automation and Information Sciences, y.14, no. 1, 1981, P.3-17.

7. Muller, J.-A.: Analysis and prediction of ecological systems. SAMS, vol.21, 1996.

8. Галушкин А.И., Томашевич Д.С., Томашевич H.С., Муромский М.Ю., Шачнев Е.А. Нейронные алгоритмы экстраполяции функций и их применение в задачах прогнозирования работы Call-центров Чястъ 1. // Нейрокомпьютер. N2 2, 2000. - 12 с.

9. Заенцев И.В. Прогнозирование загрузки локальной вычислительной сети пейджингового центра на основе нейронных сетей. // Студенческие научные сообщения (выпуск 2). Тезисы докладов 52 студенческой научной конференции. -Воронеж: ВГУ, 1998. С. 27.

10. Николис Г., Пригожин И. Самоорганизация в неравновесных системах. -М.: Мир, 1979. 309 с.

11. Николис Г. Динамика иерархических систем. М.: Мир, 1989. -486 с.12