Содержание к диссертации
Введение
Глава 1. Анализ состояния проблемы распределения частотно- временного ресурса в системах подвижной радиосвязи 16
1.1. Проблема вычислительной сложности задачи частотно-территориального планирования в современных и проектируемых системах подвижной радиосвязи 18
1.2.3адача синтеза оптимальной структуры опорной сети базовых станций 23
1.3.Общие проблемы задачи прогноза перегрузок сотовых сетей на основе анализа динамического поведения подвижных абонентов 25
1.4.Проблема адаптации систем подвижной радиосвязи к территориально-
адресному распределению нагрузки 31
Глава 2. Планирование частотно-территориального ресурса в системах подвижной радиосвязи на основе теории монотонных систем 37
2.1. Частотно-территориальное планирование в современных и проектируемых системах подвижной радиосвязи 37
2.2.Теория монотонных множеств в задачах планирования частотного ресурса 39
2.3.Синтез алгоритма выделения групп интермодуляционно совместимых частот на основе монотонной меры 55
2.4.Алгоритм синтеза оптимальной структуры сотовых сетей связи 59
Краткие выводы по главе 81
Глава 3. Развитие методов теории массового обслуживания для прогноза перегрузок сотовых сетей на основе анализа динамического поведения подвижных абонентов 82
3.1. Режим перегрузки и его связь с параметрами мобильности 83
3.2. Модели нестационарных законов для характеристик мобильности. Оценки параметров 105
3.3. Динамика переходных процессов, описывающих изменение числа абонентов в соте.Предсказание перегрузок 136
Краткие выводы по главе 150
Глава 4. Специальные методы адаптивного распределения ресурса радиоканала в сотовых и ведомственных системах подвижной радиосвязи 152
4.1. Оптимизация управления случайным множественным доступом в ССПР 152
4.2.Повышение емкости сотовых систем связи при использовании зон перекрытия в режиме управления доступом 169
4.3.Анализ пакетной передачи данных в многоканальных системах подвижной радиосвязи 178
4.4.Синтез сети подвижной радиосвязи с множественным доступом 184
Краткие выводы по главе 190
Глава 5. Использование алгоритмов оптимального распределения частотно-временного ресурса ССПР при решении народнохозяйственных задач 192
5.1.Интермодуляционная совместимость частот при частотно-
территориальном планировании сетей оперативной радиосвязи 192
5.2.Интермодуляционная совместимость частот и управление множественным доступом в низкоорбитальных спутниковых системах
связи 199
5.3.Выделение групп интермодуляционно совместимых частот для сотовых систем связи 216
5.4.Синтез радиосети оптимальной структуры для опытной зоны системы UMTS в г. Иваново 220
5.5.Оптимизация использования частотно-временного ресурса в системах передачи тревожной информации с множественным доступом 226
Краткие выводы по главе 232
Заключение 234
Список литературы
- Проблема вычислительной сложности задачи частотно-территориального планирования в современных и проектируемых системах подвижной радиосвязи
- Частотно-территориальное планирование в современных и проектируемых системах подвижной радиосвязи
- Режим перегрузки и его связь с параметрами мобильности
- Оптимизация управления случайным множественным доступом в ССПР
Введение к работе
Актуальность проблемы
Бурная информатизация общества привела к тому, что в последнее десятилетие произошел резкий скачок объема информации, передаваемой и обрабатываемой различными системами радиосвязи. Существенно увеличилось количество одновременно работающих радиосредств и систем связи различного назначения. В каждой отдельной системе значительно возросло число абонентов. Заметно поднялась скорость обработки и передачи информации. Все это потребовало повышения пропускной способности, показателей быстродействия и электромагнитной совместимости систем подвижной радиосвязи.
Наступил период, когда практически все системы радиосвязи вышли на предельный уровень нагрузки и ощутили потребность в повышении ресурса радиоканала. Усилия на уровне национальных и международных комитетов и комиссий по распределению ресурса радиоканала между различными системами, радиосредствами и службами оказались способными лишь на некоторое время снять остроту проблемы.
В качестве важнейшей тенденции решения проблемы повышения пропускной способности радиотехнических систем в последнее время выступает поиск новых усовершенствованных способов организации радиосвязи, задействование неиспользованных ресурсов существующих радиолиний. В сотовых сетях и системах связи подвижных абонентов одними из основных путей повышения пропускной способности являются: оптимизация территориального распределения частотного ресурса радиоканала, а также пространственной структуры сотового покрытия, поиск оптимальных методов обеспечения ЭМС, обеспечение более качественной и быстрой работы в режимах организации доступа, введения процедур контроля локальных перегрузок с последующим перераспределением ресурса.
Реализации перечисленных выше методов препятствует высокая сложность существующих алгоритмов, неразвитость информационных технологий в части подходов, позволяющих снижать указанную вычислительную сложность в реальных условиях, отсутствие решения вопросов, связанных с влиянием мобильности абонентов на основные характеристики систем подвижной радиосвязи.
Появление высокопроизводительных цифровых БИС с большой степенью интеграции открыло новые принципиальные возможности по созданию компактных устройств и комплексов автоматизированного решения указанных задач. Относительная простота сопряжения цифровых систем адаптивного управления ресурсом канала с другими цифровыми системами фактически решает проблему их включения в существующие и проектируемые интегрированные цифровые сети региональных, национальных и глобальных систем радиосвязи. Это объясняет то, что на первый план все отчетливее выступает проблема разработки соответствующих теоретических методов управления ресурсом радиоканала и анализа характеристик мобильности подвижных абонентов.
Главной особенностью систем подвижной радиосвязи (СПР) является подвижность абонентов системы и территориальная распределенность подсистемы радиодоступа. Эта особенность делает подчас невозможным использование для их исследования и проектирования научных результатов и инженерных методик, разработанных для телекоммуникационных систем фиксированной связи. Поэтому одной из актуальных задач является задача исследования области применения известных результатов теории массового обслуживания в части пропускной способности системы по трафику с учетом конфигурации подсистемы радиодоступа и характера мобильности абонентов. Такие исследования позволили сформулировать и решить задачу адаптивного управления канальным ресурсом в сотовых и низкоорбитальных спутниковых системах связи с учетом мобильности абонентов, а также задачу аналитического расчета режима хэндовера в них. Сформулированная выше особенность СПР предопределяет большие вычислительные сложности задач, возникающих при их проектировании, и особенно для систем поколений 2.5 G и 3G. Ярким примером могут служить две важнейшие задачи из области частотно-территориального планирования (ЧТП) СПР: определение наилучших, по большому перечню показателей, мест установки базовых станций, и выбор интермодуляционно-совместимых групп частот из большого (более 100) числа исходных номиналов частот. Учеными, работающими в указанной области, прилагаются достаточно серьезные усилия в поиске разрешения указанной проблемы с целью получения практически пригодных алгоритмов для использования их на практике. Примером могут служить источники [28,59], в которых отражены наиболее значимые результаты, полученные к настоящему времени Беблоком, по выбору максимальных групп интермодуляционно-совместимых частот из заданного множества равномерной сетки частот. Предельные значения их применимости ограничены объемом в 85 частот (в литературе приводится только одна полученная максимальная группа для заданного объема частот). В [165,179,192] указано довольно представительное число алгоритмов распределения частот для сотовых систем, однако все они построены на эмпирических или полуэмпирических подходах, не позволяющих гарантировать, даже приблизительно, оптимальный результат. Общего конструктивного алгоритма для любых СПР до сих пор так и не найдено. Все существующие в настоящее время расчетно-аналитические комплексы и алгоритмы имеют экспоненциальную вычислительную сложность или требуют активного использования интуиции проектировщика, основанной на богатом опыте и высоком профессионализме. Это предопределяет большую долю субъективизма в решении задачи и делает невозможным строгую оценку полученного решения в смысле оптимальности по выбранному критерию качества. Поэтому актуальной остается проблема создания алгоритмов для формализованного решения таких задач, имеющих вычислительную сложность не выше полиномиальной, и свободных от субъективного участия проектировщика.
Большое число нерешенных вопросов существует в СПР оперативного или производственно-технологического назначения. Как известно, система, позволяющая наиболее эффективно использовать выделенные радиоканалы (например, по критерию минимума среднего времени ожидания), является системой с равнодоступными каналами. В этой связи для оперативных сетей радиосвязи необходимо решить вопрос со структурой сети при случайном множественном доступе, а для радиосетей с пакетной передачей данных и "транкинговых" систем радиосвязи, в которых время сеанса связи соизмеримо со временем обмена служебной информацией, необходимо определить алгоритм управления свободными каналами. Большая часть работ по этому вопросу принадлежит советским ученым Цыбакову Б.С., Михайлову В.А. и др. [65-67, 122], однако вопрос централизованного управления режимом случайного множественного доступа до сих пор не рассматривался. Особую актуальность этот вопрос приобретает в связи с разработкой аппаратуры с автоматическим поиском свободного канала, на основе которой строятся "транкинговые" системы, а также с разработкой и широким внедрением в последнее время радиотехнических систем передачи специализированной (телеметрической, тревожной и т. п.) информации.
Другой важный аспект проектирования, эксплуатации и исследования рабочих характеристик сотовых сетей и других СПР, составляет задача обнаружения и распределения по пространству спонтанно возникающих локальных концентраций нагрузки. Указанная проблема относится к новой области теории информации, изучающей пространственно-временные преобразования данных, распределенные алгоритмы управления, обработки, хранения, кодирования и доставки информации. Указанное направление в настоящее время только начинает активно развиваться. Причина этого состоит в том, что активный источник требований к соответствующим результатам возник сравнительно недавно в виде бурно развивающихся сотовых сетей связи и других систем, обладающих территориально распределенной структурой. Хотя общие идеи и пионерские работы, касающиеся указанной проблематики, возникли достаточно давно. На первом этапе они относились исключительно к изучению вопросов оптимизации распределенных поисковых усилий [5,6,37,121,187]. В дальнейшем они получили развитие на отдельные задачи, решаемые в системах обмена информацией. Наибольшее влияние в этом направлении оказали работы зарубежных авторов: Клейнрока Л. [47,48], Сипсера Р. [100], Мартина Дж. [61], Галлагера Р. [168], Мерлина П., Сегалла А. [177], Прабху Н. [183], Питерсона Дж. [78] и др. Среди отечественных работ к таким относятся труды Б.В. Гнеденко [24], М.А. Шнепса [126], Б.С. Лифшица, А.П. Пшеничникова А.Д. Харкевича [60], Е.И. Рухмана, Б.Я. Советова, С.А. Яковлева [96,102], В.А Кочегарова и Г.А. Фролова [51]. Однако работ, посвященных непосредственно вопросам влияния характеристик мобильности абонентов на рабочие параметры систем связи, а также обнаружению процессов скопления/рассасывания абонентов в локальных областях для предсказания перегрузок на ранних этапах пока нет. Более того, в теории массового обслуживания нет даже раздела, посвященного указанным вопросам, который бы можно было определить как раздел, изучающий нестационарные системы массового обслуживания. Этим объясняется важность решения такой задачи, как с точки зрения теории, так и с точки зрения практики. Для ее решения представляется перспективным использовать в качестве исходных методы статистической обработки нестационарных дискретных процессов, полученные в работах А.П. Трифонова, Ю.С. Шинакова и В.К. Бутейко [112,113,190].
Таким образом, анализ публикаций в исследуемой области показал отсутствие теоретических результатов по оценке эффективности применения указанных выше, достаточно сложных методов управления ресурсами канала и контроля мобильности, а также отсутствие конкретных выводов по потенциальным возможностям от их использования в тех или иных условиях. Это не позволяет судить о целесообразности их внедрения, оставляет без ответа вопрос о том, как именно нужно осуществлять соответствующее управление, и в каких ситуациях системы наиболее чувствительны к нестационарному поведению мобильных абонентов. Последнее обстоятельство существенно сдерживает широкое распространение на практике систем связи подвижных абонентов с адаптивным управлением пространственным распределением ресурсов. Таким образом, настоятельная потребность в применении новых высокоэффективных систем связи, использующих незадействованные до настоящего времени ресурсы радиоканала, с одной стороны, и отсутствие необходимых для этого теоретических проработок, с другой стороны, настоятельно требуют разработки перспективных методов управления ресурсами радиоканала и слежения за поведением мобильных абонентов, позволяющих в полной мере учитывать нюансы функционирования в системах массового обслуживания и проводить исследования для конкретных технических приложений.
Цель и задачи работы
Целью работы является разработка научно обоснованных технических решений по повышению эффективности использования ресурса радиоканала в системах подвижной радиосвязи путем решения задач ЭМС, распределенного управления доступом и контроля мобильности абонентов. Внедрение этих решений вносит значительный вклад в развитие такой важной технико-экономической проблемы, как создание высокопроизводительных систем массового обслуживания подвижных абонентов.
Для достижения поставленной цели необходимо было решить комплекс теоретических, экспериментальных и прикладных задач:
- создать адекватные математические модели, описывающие отдельные элементы, структуры и операционные преобразования СПР, на основе которых провести синтез алгоритмов, позволяющих за реальное время счета находить решения ряда задач, возникающих при создании СПР, которые могут быть формализованы, как сложные комбинаторные задачи;
- разработать алгоритмы решения задачи формирования групп интермодуляционно совместимых частот в СПР различного назначения с произвольной территориальной структурой таких систем;
- разработать вероятностную модель СПР как системы массового обслуживания наиболее адекватную реальным ситуациям, учитывающую мобильное поведение абонентов;
- разработать алгоритмы территориального планирования сотовых систем нового поколения, обеспечивающие безъизбыточное число базовых станций;
- исследовать режимы перегрузки сотовых систем связи с учетом мобильности подвижных абонентов;
- разработать математические модели мобильности подвижных абонентов в сотовых системах связи и на их основе синтезировать алгоритмы динамического управления канальным ресурсом;
- провести анализ характеристик полученных алгоритмов контроля динамически изменяющихся параметров мобильности абонентов для оценки достоверности принимаемых решений, точностей формируемых оценок параметров и времени реакции на возникновение критических ситуаций;
- осуществить частотно-территориальное планирование конкретных СПР в части интермодуляционной совместимости частот;
- разработать новые протоколы обмена информацией при управлении случайным множественным доступом и на их основе сформулировать рекомендации для создания усовершенствованных пакетных радиотехнических систем специального назначения;
- провести анализ дополнительного ресурса радиоканала сотовых сетей связи, связанного с многократным покрытием территории в пограничных зонах сот;
- разработать методы управления доступом и организации хэндовера, позволяющие реализовать дополнительный ресурс радиоканала в зонах перекрытий для повышения показателей рабочих характеристик;
- исследовать условия, при которых в многоканальных СПР возможна передача пакетов данных в канале, совмещенном с речевым;
- разработать алгоритмы множественного доступа в пакетных радиосетях в режиме управления доступом со стороны центральной станции;
- провести сопоставительный анализ для оценки выигрыша, обеспечиваемого в режиме активного управления доступом со стороны центральной станции; - реализовать все предложенные алгоритмы в виде пакетов прикладных программ;
- сформулировать рекомендации по возможным направлениям дальнейшего развития полученных результатов в целях повышения эффективности использования ресурса радиоканала в СПР или для решения подобных задач в ряде других приложений.
Общая методика исследований
Разрабатываемые в диссертации методы управления случайным множественным доступом и контроля мобильности подвижных абонентов в сотовых сетях и СПР базируются на использовании таких методов теории вероятностей, математической статистики и адаптивной обработки, как:
1. статистическое оценивание параметров с использованием критерия максимального правдоподобия;
2. обнаружение и идентификация ситуаций на основе решающих правил, отвечающих критерию Неймана-Пирсона, примененных к нестационарным системам массового обслуживания;
3. динамическое управление по Беллману;
При решении задач синтеза алгоритмов автоматизированного формирования групп интермодуляционно совместимых частот, формирования оптимизированной структуры расположения опорной сети базовых станций и анализа влияния параметров мобильности абонентов на основные характеристики системы использовались методы теории множеств, теории графов и теории массового обслуживания.
Анализ эффективности алгоритмов контроля мобильности в режимах автоматического обнаружения и идентификации проводился с помощью методов математического моделирования.
Научная новизна и основные научные результаты
1. Разработаны конструктивные алгоритмы синтеза групп интермодуляционно-совместимых частот и территориального плана сотовых систем связи на основе применения теории монотонных систем;
2. Исследован вопрос влияния мобильности подвижных абонентов, как макропараметра, на вероятность перегрузки в сотовых системах связи, в результате чего получена формула расчета пропускной способности этих систем с учетом мобильности, что, при соответствующей организации, позволило повысить эффективность их использования;
3. Предложена математическая модель,учитывающая нестационарное поведение мобильных абонентов в пределах сот. Она позволила с единых позиций рассматривать характерные ситуации возникновения/рассасывания автомобильных пробок, флуктуации потоков абонентов на выходах из станций метро, прохождения потоков через экранирующие туннели, синхронизирующих внешних условий массового порядка (сбои расписаний, концентрации людей в местах проведения массовых мероприятий и т.п.), и т.д.
4. Исследован вопрос динамики перегрузок, возникающих в сотовых системах связи из-за мобильности подвижных абонентов и синтезированы алгоритмы совместного обнаружения-оценивания параметров мобильности, позволившие заблаговременно предсказывать режим перегрузки и перераспределяя канальный ресурс, повысить пропускную способность систем.
5. Предложена оригинальная методика, расширяющая технику теории массового обслуживания на задачи с нестационарным поведением объектов, позволяющая решать большой класс новых задач, относящихся к системам с высокой динамикой поведения и к режимам переходного процесса, возникающим в системах массового обслуживания. Новый класс задач охватывает ситуации с нестационарным поведением интенсивностей входящего потока и потока обслуженных заявок.
6. Исследованы и определены условия организации структуры сети оперативной радиосвязи с множественным доступом, минимизирующие среднее время ожидания в сети.
7. Исследована возможность уплотнения пакетами данных каналов, освобождающихся от речевых сообщений в многоканальных СПР, что увеличивает объем обслуживаемой нагрузки.
8. Разработана математическая модель организации доступа, учитывающая возможность радиоперекрытия зон и определена методика расчета вероятности отказа доступа при использовании для этой цели дополнительного ресурса зон перекрытия в сотовых системах связи, что повышает пропускную способность таких систем.
9. В системах со случайным множественным доступом синтезирован оптимальный по Беллману алгоритм управления процедурой распределения свободных каналов среди активных подвижных абонентов.
10. Разработаны вычислительные алгоритмы синтеза радиосетей с оптимизированной структурой распределения ресурсов, имеющие полиномиальную сложность, позволяющие в комбинаторных задачах создания систем подвижной радиосвязи существенно сократить время счета.
Практическая ценность работы
На основе полученных в диссертации методов синтеза и анализа алгоритмов распределения ресурса радиоканала, распределенного управления доступом и контроля мобильности предложены конкретные варианты построения или модификации целого ряда существующих и проектируемых систем. Результаты ориентированы на возможность осуществления практической разработки СПР как оперативного назначения, так и общего пользования с высокоэффективным использованием выделенного частотно-временного ресурса, что приводит к повышению технико-экономической эффективности таких систем (Приложение 6. «Акты внедрения результатов», Пр.№213 от 07.06.95 МВД РФ о принятии на вооружение системы «РОСА»).
Применение методов оптимизации распределения частотно-временного ресурса в СПР позволило:
- решить задачу частотно-территориального планирования сетей оперативной радиосвязи ГУВД г. Москвы в диапазонах 148/170 МГц, 205/210 МГц и 430V460 МГц;
- определить структуру сети оперативной радиосвязи ГУВД г. Москвы, работающей в режиме множественного доступа;
- решить задачу оптимизированного территориального планирования сотовых сетей связи третьего поколения 3G;
- решить задачу аналитического расчета пропускной способности сотовых сетей связи с учетом специфических условий режима хэндовера;
- решить задачу учета параметров мобильности подвижных абонентов при анализе пропускной способности сотовых сетей связи;
- решить задачу прогноза перегрузок сотовых сетей связи из-за изменения нагрузки сот в результате передвижения абонентов;
- рекомендовать группы частот для стандартов NMT-450, GSM-900 при проектировании сетей «Институтом сотовой связи» и ФГУП ГСПИ РТВ; - синтезировать алгоритмы распределения групп частот и множественного доступа к канальному ресурсу в низкоорбитальной спутниковой системе «Гонец»;
- разработать асинхронный протокол обмена информацией в режиме случайного множественного доступа в канале, совмещенном с речевым для систем передачи тревожной информации, таких, например, как «РОСА»
- разработать алгоритмы быстрой коммутации свободных радиоканалов в многоканальных радиостанциях и «транкинговых» системах радиосвязи.
Результаты диссертационных исследований использованы при создании сетей оперативной радиосвязи ГУВД г. Москвы; в низкоорбитальной спутниковой системе связи ГОНЕЦ, в сотовых системах связи общего пользования первого, второго и третьего поколений, что подтверждается соответствующими актами внедрения. Предложенные технические решения защищены авторским свидетельством и патентом РФ. Результаты научных исследований использованы в Программе фундаментальных и прикладных исследований вузов связи Российской Федерации «Фундаментальные аспекты новых информационных ресурсосберегающих технологий» Министерства связи и информатизации РФ, проектных работах, проводимых ФГУП ГСПИ РТВ и «Институтом сотовой связи», в научно-исследовательских работах, проводимых ФГУП НИИР и при решении задач, стоящих перед крупными операторами сотовой связи (ОАО «Вымпелком»), Кроме того, результаты исследований нашли применение в учебном процессе на радиотехническом факультете МТУСИ [17,39,76,87,123,127,].
Объем и структура диссертации
Диссертация состоит из введения, пяти глав, заключения, списка литературы и приложений. Она изложена на 236 страницах машинописного текста, содержит72 рисунка, 26 таблиц, библиография из 192 наименований на 11 страницах, материалы приложений на 109 страницах,
Основные положения, выносимые на защиту
1. Методика построения и результаты применения меры, обладающей свойствами монотонности на множестве частот и множестве возможных мест установки базовых станций сотовых сетей связи, как функции числа интермодуляционных уравнений для множества частот и функции относительной площади перекрытия для множества мест установки базовых станций, которые позволяют решить задачу выделения групп интермодуляционно-совместимых частот и определения оптимальных мест установки базовых станций для частотно-территориального планирования СПР.
2. Полученные вычислительные алгоритмы проектирования СПР полиномиальной вычислительной сложности, ориентированные на решение комбинаторных задач с использованием техники формирования векторного пространства с монотонной мерой.
4. Разработанные модели процесса функционирования сотовой сети в пределах выделенной зоны, построенные на основе двумерной марковской цепи с матрицей переходных вероятностей Pi (t), где / - число абонентов в зоне,«а число заявок на обслуживание (подключение), которые позволяют эффективно проводить исследование трафика и синтез алгоритмов функционирования СПР.
5. Разработанная общая математическая модель для описания нестационарного поведения подвижных абонентов для широкого спектра реальных ситуаций, опирающуюся на явление возникновения «ударных» волн ограниченного перечня форм в мобильных потоках при возмущающих воздействиях превышающих некоторый пороговый уровень. Отмеченные ситуации охватывают такие широко известные явления, как: возникновение/рассасывание автомобильных пробок, скопление людей в зонах массовых мероприятий, движение потоков в/из метро, флуктуации потоков, проходящих через экранирующие тоннели, постепенный рост активности с наступлением рабочего времени и т.д.
6. Синтезированные совместные алгоритмы обнаружения/идентификации и оценки параметров случайно возникающих режимов с нестационарным поведением мобильности в рамках предложенной общей модели, построенные на обработке выборок входящих регистрации и запросов на отключение от абонентов в выделенных зонах.
7. Результаты анализа, устанавливающие границы возможного повышения уровня предельной нагрузки в сотовых сетях при активации дополнительных ресурсов радиоканала, связанных с взаимными территориальными перекрытиями соседних сот/зон. Ряд конкретных технических предложений и методик активации указанных дополнительных ресурсов радиоканала, содержащихся во взаимных перекрытиях сот в сетях стандартов GSM, CDMA, а также в системах третьего поколения 3G.
8. Результаты анализа, устанавливающие предельные возможности уплотнения трафика существующих многоканальных систем подвижной радиосвязи путем совмещения передачи данных и режима передачи речевой информации, показывающие, что условие стационарности процесса передачи пакетов сохраняется пока Л т /(/-1 / М)м х / М, где М- число абонентов, Л т
- производительность w-ro источника пакетов, / - число свободных каналов в системе.
9. Предложенные алгоритмы и методы оптимизации процедуры случайного множественного доступа для СПР с пакетной передачей данных, обладающие наилучшими показателями в смысле критерия максимума пропускной способности, синтезированные на основе стратегии управления по Беллману, применяемой в режиме распределения/разбиения свободных каналов центральной станцией.
Публикации и апробация результатов работы
Основные материалы по теме диссертации опубликованы в более чем 50 печатных работах в научно-технических журналах и сборниках, отражены в 3 монографиях [23,34,82Ф)], 29 научно-технических статьях, получены авторское свидетельство на изобретение[77] и патент РФ [7].
В монографии автор принимал участие в написании §5.1-5.6, что отражено в предисловии По материалам диссертации были сделаны доклады: на 15 международных конференциях, 9 Всесоюзных и Всероссийских сессиях, симпозиумах и конференциях [45,140-159], на секции радиоэлектроники РАН в 2005г.
Результаты исследований по теме диссертации регулярно докладывались на ежегодной научно-технической конференции профессорско-преподавательского состава МТУСИ.
По материалам диссертационной работы выпущено более 20 научно-технических отчетов НИЧ МТУСИ.
Проблема вычислительной сложности задачи частотно-территориального планирования в современных и проектируемых системах подвижной радиосвязи
Одной из важнейших проблем, которую приходится решать разработчикам систем сухопутной подвижной радиосвязи (ССПР), является проблема частотно-территориального планирования (ЧТП), которая включает в себя большой перечень рассматриваемых вопросов. Главным итогом решения этой проблемы является создание территориально-распределенной структуры ССПР, обеспечивающей, с учетом внутрисистемной и межсистемной ЭМС, требуемое радиопокрытие и возможность обслуживания формируемого абонентами трафика. В самом общем виде формализация этой задачи приводит к большому множеству возможных решений и в настоящее время не представляется возможным ее общее аналитическое или алгоритмически автоматизированное решение. Поэтому применяются традиционные методы декомпозиции на более мелкие, связанные друг с другом задачи, решения которых либо известны, либо могут быть разработаны. Одной из таких задач является задача борьбы с интермодуляционными помехами. Интермодуляционные помехи возникают вследствие неизбежного присутствия нелинейных искажений в реальной аппаратуре. Методы борьбы с этими помехами можно условно разделить на три группы: - создание премо-передающей аппаратуры, в которой минимизируется влияние нелинейностей, т.е. минимизируется уровень нелинейных, в том числе и интермодуляционных помех; - разработка ЧТП, которые в случае возникновения интермодуляционной помехи, позволяют с учетом реального трафика системы считать возможные потери допустимыми (т.е. считать вероятность возникновения неблагоприятной ситуации малой); - выбор групп используемых частот, которые являются интермодуляционно-совместимыми, т.е. ни при каких комбинациях не образуют рабочую частоту группы.
Мероприятия, проводимые в рамках первой группы, выливаются в разработку стандартов на конкретную систему, в которых учитываются достижения современных технологий создания приемо-передающей аппаратуры. Анализ конкретной аппаратуры на возникновение нелинейных, в том числе и интермодуляционных помех обычно осуществляется по известным моделям с использованием пакетов прикладных программ таких например, как SimuLink, MicroCap, SistemView, MicroWaveLab, Serenada или др. С учетом требований стандартов и характеристик реально производимой аппаратуры, разрабатываются нормы частотно-территориального разноса (ЧТР), выполнение которых при создании конкретной ССПР позволяет обеспечить требуемую ЭМС радиосредств. На основе этих норм используются методы второй группы по разработке конкретных ЧТП. Регламентация требований к ЧТП помогает решать поставленную задачу, но никак не снижает ее трудоемкость с одной стороны и не исключает полностью интермодуляционной помехи с другой. Поэтому задача обеспечения интермодуляционной совместимости частот при создании ССПР остается одной из наиболее трудоемких и важных из нерешенных до конца в настоящее время задач.
Широкое применение третьего метода ограничено отсутствием регулярных алгоритмов, позволяющих с приемлемой вычислительной сложностью решать задачу набора групп интермодуляционно-совместимых частот из произвольного множества (например, более чем ста частот). Число реальных результатов, позволяющих работать с большим количеством частот, весьма ограничено [34,43,59,132,161,167,179].
В инженерной практике сложилось вполне определенное понимание влияния интермодуляционных помех, которое закрепилось на уровне соответствующих стандартов и норм (например, ГОСТ 12252-86 определят нормы на интермодуляционную избирательность приемника, а рекомендации МСЭ-Р SM. 1134(10/95) «Intermodulation interference calculations in the land-mobile service»-методы расчета интермодуляционных помех в сухопутной подвижной службе). Оно состоит в том, что в качестве интермодуляционных помех понимаются исключительно те паразитные спектральные компоненты, у которых центральная частота попадает в рабочую полосу полезного сигнала. На самом деле рассматриваемое явление сложнее.
Из-за расширения спектра появляется возможность попадания части мощности интермодуляционной помехи в полосу полезного сигнала даже в тех случаях, когда ее центральная частота не попадает в указанную полезную спектральную область. Однако таким явлением на практике, как правило, пренебрегают. Некоторые оценки, подтверждающие правильность этого предположения приводятся в ПРИЛОЖЕНИИ 1.
Результаты показали, что дополнительное уменьшение за счет «расширения» спектра интермодуляционных компонент в наименее благоприятном случае максимальной частотной упаковки каналов всегда не ниже -11.72 дБ (наблюдается на интермодуляционной компоненте 7-го порядка). Для ситуаций схожих с реальными указанное дополнительное уменьшение всегда оказывалось не хуже -21.99 дБ (компонента 5-го порядка).
Поскольку полученные значения будут складываться со значениями уменьшения уровня комбинационной составляющей по отношению к основному сигналу, которые даже при неудачном исполнении аппаратуры составляют порядка -30 дБ, то можно заключить, что в реальных системах подвижной связи можно не принимать во внимание воздействие интермодуляционных помех, проходящих через боковые сегменты расширенного спектра. Поэтому при решении поставленной задачи будем ориентироваться на традиционное понимание ситуаций с интермодуляционными помехами [27, 34, 59, 99]. Группы интермодуляционно-совместимых частот представляют собой неравномерную «сетку радиоканалов», в то время как отказ от обеспечения интермодуляционной совместимости определяет равномерную «сетку радиоканалов». В работе предполагается, что полученные неравномерные «сетки радиоканалов» также удовлетворяют всем нормам ЧТР, как и равномерные , на основе которых разрабатываются ЧТП, поэтому повышение эффективности использования частотного ресурса в случае использования неравномерных «сеток» в работе понимается как дополнительное по сравнению с равномерными «сетками» число каналов, на которых возможна одновременная работа абонентов ССПР.
Таким образом, интермодуляционные помехи р-го порядка между частотами срх,(р2,...,(рт существуют, если выполняется соотношение т где и, - целые положительные числа, для которых р = ]Г л. . 1=1
Если частоты щ выбираются равномерно из одного диапазона частот І/тіп.Л,»]. то при определенных соотношениях величин /min, = /max-/min и разносом между соседними частотами появляются существенные ограничения на возможность появления интермодуляционной зависимости различных порядков (например, для S«fmin невозможно появление интермодуляционной зависимости второго порядка). Эти ограничения обуславливают появление алгоритмов, сокращающих время прямого перебора при выявлении групп интермодуляционно независимых частот [161,192].
При отсутствии подобных ограничений используются либо метод Монте-Карло [165], либо алгоритмы теории графов [41,85,160]. Для получения максимальной группы интермодуляционно независимых частот указанными выше алгоритмами m требуется время, пропорциональное М = C jp. В дальнейшем используется оценка снизу Q = 2m pCpp\ М, что характеризует вычислительную сложность существующих алгоритмов по параметру т как экспоненциальную. Нерегулярные методы позволяют эту величину уменьшить только в некоторое фиксированное число раз (в зависимости от способа) не зависящее от величины т. Все существующие регулярные методы основаны на полном переборе при малых значениях величин р и т и затрачивают на счет время пропорциональное М. В практической деятельности величина т обуславливает (для т, измеряемого несколькими сотнями) время непрерывного счета на существующих ЭВМ в несколько десятков лет, что говорит о невозможности реализации этих методов при указанных параметрах.
Частотно-территориальное планирование в современных и проектируемых системах подвижной радиосвязи
С конца 80-х годов XX века началось массовое введение в строй качественно новых систем связи, которые получили название сотовых сетей. До этого момента ни разработчикам, ни эксплуатационным службам не приходилось сталкиваться со столь масштабными задачами, с таким разнообразием условий работы и предоставляемых услуг. Возникла необходимость решения ряда новых задач, отличающихся значительным числом параметров и ограничений. Все указанные задачи, так или иначе, касаются основной проблемы - ограниченности ресурса радиоканала.
Наряду с сотовыми системами активное развитие получили производственно технологические или выделенные системы подвижной радиосвязи (СПР), применяемые в различных сферах человеческой деятельности, например, хозяйственно-административной, гуманитарной, правоохранительной, муниципальной.
Последнее десятилетие выявило самую острую проблему, связанную с разработкой и эксплуатацией подобных систем. Она состоит в остром дефиците ресурса радиоканала. Различные системы находятся в острой конкурентной борьбе за указанный ресурс. Способность к более эффективному, рациональному его использованию становиться решающим фактором выживания. Практика эксплуатации неопровержимо доказала, что даже относительно успешное решение обозначенной проблемы в конкретных условиях приводит к заметному повышению экономической и технической эффективности.
Это объясняет актуальность задачи частотно-территориального планирования (ЧТП) для сотовых сетей и СПР. Одновременно задача ЧТП в силу объективных обстоятельств является относительно новой и пока не получила решения в рамках классических методов. Попытки применения традиционных подходов, успешно зарекомендовавшие себя при решении подобных задач на уровне более ранних и поэтому значительно более простых систем, оказываются мало успешными. Объясняется это в силу таких причин:
1) значительно возросшему числу рабочих частот, составляющих подлежащий распределению ресурс радиоканала, которое может достигать от нескольких сотен до тысяч в пределах системы;
2) практически неограниченному числу мест расположений базовых станций (БС), составляющих опорную сеть проектируемых систем;
3) динамическому характеру поведения абонентов системы, часто подвергающемуся заметному влиянию со стороны внешних, внесистемных, факторов.
Для решения задач ЭМС и распределения нагрузки в системе до последнего времени с успехом применялись методы теории графов, комбинаторики, численного перебора [34,71,160,161,165,192]. Однако в «новых» условиях их вычислительная сложность возрастает на столько, что их использование теряет всякий смысл. Объясняется это экспоненциальной вычислительной сложностью известных алгоритмов ЧТП (см., например [59,99,160,165,167]), что означает рост времени решения по закону aN, где а - некоторое фиксированное значение большее 1, а N - число степеней свободы, подлежащих оптимизации в процессе решения задачи. Поскольку, как отмечалось выше, характерные для сотовых сетей и современных СПР значения N могут достигать сотен и даже тысяч, то вычислительные затраты известных методов становятся астрономическими.
В таких условиях пришлось осуществлять разработку и ввод в эксплуатацию сотовых сетей второго поколения (2G). Поэтому вопросы распределения частот между БС и расположения самих БС решались на основе интуиции и практического опыта разработчиков. В рекомендациях стандартов GSM или CDMA, посвященным вопросам ЧТП, даются положения самого общего характера, которые относятся скорее к идеализированным, а не к реальным ситуациям. Дополнительной особенностью является тот факт, что создаваемые в России сотовые системы и СПР используют частотные диапазоны, соседствующие с диапазонами силовых ведомств. В виду этого обстоятельства подчас системы создаются на нескольких участках выделенного для нее частотного ресурса. В сложившихся обстоятельствах трудно утверждать, что реализовавшаяся структура ЧТП в сетях 2G и подобных им системам близка к оптимальной. Косвенным подтверждением этому служит то, что в ряде регионов продвинутые операторы сотовых сетей в ручном режиме перепрограммируют режим работы сети, перераспределяют ресурсы между служебным и полезным трафиком, программно корректируют зоны обслуживания отдельных БС, варьируя уровень энергетического барьера и гистерезисного зазора в режиме переключений абонентов (handover), добиваясь в итоге повышения предельной нагрузки на 30%-40% и более.
Среди задач ЧТП хорошо известны два типа трудоемких по вычислительным затратам и одновременно очень важных задач: 1) формирования из доступного для системы множества частот максимальных групп интермодуляционно совместимых до заданного порядка р; 2) синтеза опорной сети базовых станций оптимальной структуры на уровне крупного города, адаптированной к распределению нагрузки;
Одновременно с этим в математической теории множеств появился ряд весьма перспективных работ (см., например [68,69]), указывающих на возможность строгого решения задач, подобных приведенным, методами с полиномиальной сложностью вычислений. Но для их применения требуется обеспечить ряд специфических условий, реализация и доказательство наличия которых в каждом конкретном случае сами по себе представляют самостоятельные, далеко не тривиальные задачи. Материал данной главы как раз и посвящен методам, позволяющим общую технику математического аппарата монотонных множеств (систем), разработанную в [68,69], развить на решение указанных задач ЧТП.
Предлагается ряд специальных конструкций, позволяющих на множествах либо частотных литер, либо возможных местоположений БС сотовых сетей, либо зон деления СПР, ввести монотонные меры и соответствующие операции положительного/отрицательного воздействия. На уровне физического смысла доказывается связь вводимых мер с целевыми функциями решаемых задач оптимизации, и доказывается возможность применения математического аппарата монотонных систем.
Режим перегрузки и его связь с параметрами мобильности
Существующие и разрабатываемые проекты сотовых сетей традиционно ориентируются на расчетные значения уровня средней нагрузки, приходящейся на абонента, много меньшие единицы. Одновременно с этим организация службы поддержки мобильности предполагает полный контроль межзоновых перемещений абонентов, вне зависимости от того в каком режиме (активном или в пассивном) они находятся. В результате на каждой базовой станции оказывается доступным контроль не только уровня нагрузки в соте, но и числа абонентов, располагающихся на обслуживаемой территории. Количество активных пользователей в процентном представлении от общего числа абонентов всегда невелико. Указанное обстоятельство позволяет утверждать, что статистические процедуры, построенные на основе данных о мобильности, имеют существенно более высокие характеристики качества, поскольку оперируют с выборками, объем которых значительно превосходит объемы выборок данных, связанных с нагрузкой. Кроме того, как показывает опыт эксплуатации, и как подтверждает приведенный ниже анализ, динамика переходных процессов, описывающих изменение числа абонентов в соте/зоне, существенно ниже динамики переходных процессов, описывающих установление средней нагрузки соты. Поэтому, если перегрузка в соте происходит по причине скопления абонентов, то ее можно предсказать на более ранних этапах с помощью анализа изменений параметров процессов, описывающих потоки межсотовых перемещений абонентов. Для корректного решения поставленной задачи нужно синтезировать соответствующие алгоритмы обнаружения/идентификации динамического поведения мобильных потоков и предложить процедуры для расчета новых устойчивых состояний, в которые будет переходить система на уровне соты/зоны после изменений параметров мобильности. Сопоставление времени переходного процесса для числа абонентов в соте/зоны с задержкой, необходимой для завершения алгоритмов обнаружения/идентификации, должно показать, в каких ситуациях у операторов связи будет время на перераспределение дополнительного ресурса с целью парирования локальной перегрузки, а в каких нет. В случаях, когда будет иметь место определенный запас времени, необходимо вводить ограниченный по длительности режим промежуточного контроля с непосредственным наблюдением за числом абонентов (еще лучше за текущей нагрузкой в зоне/соте), с целью своевременной активизации процедуры перераспределения ресурсов для парирования локальных перегрузок.
Конечно, в реальных условиях могут возникать ситуации, когда перегрузка возникает по иным от скопления абонентов причинам. Например, при перерывах занятий в крупных учебных заведениях, в перерывах массовых мероприятий, при объявлении о нарушениях расписания движения авиатранспорта и т.п. В указанных случаях наблюдаются локальные во времени скачки удельных значений абонентской нагрузки, которые нельзя обнаружить на уровне анализа мобильности. Однако для широкого спектра ситуаций, порождающих локальные скопления людей и транспорта, анализ мобильности представляется наиболее удобным средством для предсказания и своевременных действий по предотвращению потери качества связи по причине локальной перегрузки сотовой сети.
И так рассмотрим ситуацию, когда внутри зоны обслуживания случайным образом изменяется как число абонентов (/), так и число активных соединений (ла). Предполагается, что при уточненной модели, учитывающей динамику обоих указанных процессов, распределение вызовов претерпит некоторые изменения и станет несколько иным, чем для традиционных моделей без динамики числа абонентов, которые можно найти, например, в [10,12,19,48,60,107,116].
Поскольку физическая природа явлений, приводящих к межсотовым перемещениям абонентов, и процессов установки/отключения соединений различна, следует ограничиться рассмотрением моделей, в которых параметры мобильных потоков не зависят от числа активных соединений, поддерживаемых в соте. В результате, распределение числа абонентов в соте можно найти автономно, без учета числа соединений.
Действительно, территорию отдельной соты вполне допустимо рассматривать как вариант некоторой системы массового обслуживания. При этом потоки поступающих и выходящих с территории соты абонентов получают следующую интерпретацию в терминах теории массового обслуживания. Поступающий поток - поток внешних заявок на обслуживание, выходящий поток - поток завершений обслуживания поступивших заявок. Нахождение отдельного абонента на территории соты при этом, в зависимости от модели мобильности, может трактоваться либо как время ожидания в очереди, либо как время обслуживания.
Наиболее . широкое распространение в теории массового обслуживания получила базовая модель назовем ее М1 [10,12,19,48,60,107,116], в которой входящий поток заявок описывается законом Пуассона, а длительность обслуживания каждой заявки подчиняется экспоненциальному распределению. В результате поток моментов завершения обслуживания также оказывается Пуассоновским. Все поступающие заявки в условиях занятости системы помещаются в очередь. Однако такая модель оказывается приемлемой только для описания сот со специфическим поведением мобильного трафика. Постоянная интенсивность выходящего потока модели с необходимостью предполагает штатный режим движения абонентов из соты на уровне насыщения. Примером могут служить территории с преимущественно односторонним движением, когда ряд входящих путей сливаются в один с ограниченной пропускной способностью.
Значительно более распространенными являются ситуации, в которых интенсивность потока из соты возрастает пропорционально числу абонентов в соте. Это соответствует модели Эрланга системы массового обслуживания [10,12,19,48,60,107,116].
Тем не менее, для полноты описания будем ниже рассматривать оба случая. И только при исследовании динамики, ввиду большого объема выкладок, ограничимся рассмотрением основной модели мобильности, соответствующей системе массового обслуживания Эрланга [139]. При этом следует отметить, что применимость разработанной методики анализа динамики не ограничивается исключительно моделями Эрланга или им подобными. Она вполне может быть использована и для моделей М1, которые оказываются даже более простыми с точки зрения проведения указанного анализа.
Оптимизация управления случайным множественным доступом в ССПР
Отличительной особенностью ССПР является жесткая ограниченность ресурса радиоканала в сочетании со строгим ограничением числа абонентов. В таких условиях традиционная организация доступа с использованием выделенного канала запросов, емкость которого соизмерима с ресурсом абонентского соединения, не целесообразна. Поэтому на вызывной канал в ССПР выделяется минимально возможный ресурс, который допускает трансляцию только самих фактов запросов подключений без указаний идентификационных номеров абонентов. Задача распределения ресурса радиоканала между абонентами при этом целиком ложится на управляющую базовую станцию (БС). Ее решение существенно сказывается на эффективности работы ССПР в целом. Ниже предлагается решение задачи оптимизации процесса доступа в ССПР с помощью методов динамического управления дискретными марковскими процессами. Технологической базой реализации предлагаемого решения выступают достижения последних лет в области микроэлектроники, позволяющие создавать радиостанции с синтезаторами частот на большое число каналов. Последнее делает рассматриваемую задачу распределения канальных ресурсов среди активных абонентов особенно актуальной. Главной целью создания подобных алгоритмов управления является достижение максимальной пропускной способности системы.
Возникающие в системах подобных ССПР конфликты разрешаются применением различных алгоритмов, многие из которых рассмотрены в монографии [105], теоретическому исследованию ряда алгоритмов посвящены работы Цыбакова Б.С. и Михайлова В.А., см. например, [65-67]. Однако управление центральной станцией распределением свободных каналов среди активных абонентов до сих пор не исследовалось.
Будем рассматривать следующий алгоритм распределения свободных радиоканалов центральной станцией при случайном множественном доступе абонентов. Пусть у центральной станции, обслуживающей некоторую территорию, существует L свободных радиоканалов. На обслуживаемой территории находится N абонентов системы, причем каждый из них к моменту времени t (начало процедуры распределения каналов) с вероятностью р формирует заявку на занятие свободного канала и с вероятностью q = (l-p) не принимает участия в процессе доступа. Таким образом, к моменту времени t на свободные каналы будет претендовать случайное число т абонентов центральной БС, порядковые номера которых неизвестны. Поэтому БС может организовать процедуру доступа единственно путем передачи по каждому свободному радиоканалу команд, содержащих reR (Lr N) выбранных наудачу номеров абонентов, которым предлагается занять этот канал. Здесь R - множество натуральных чисел. В частном случае, когда L-\ и r = N, получаем классический протокол случайного доступа ALOHA [12,105]. Ниже будет показано, что управление параметром г позволяет заметно повысить эффективность алгоритма доступа.
И так, указанные центральной станцией в команде абоненты будут в дальнейшем осуществлять попытки занять определенный канал из числа свободных. В результате каждой такой попытки возможны три ситуации: 1) среди г абонентов, которым предложено занять радиоканал, нет активных; 2) среди г абонентов, которым предложено занять радиоканал, оказался только один активный абонент; 3) среди г абонентов, которым предложено занять радиоканал, оказалось более одного активного абонента.
Распределение радиоканала, т.е. его занятие абонентом произойдет только во втором случае, третий случай характеризуется как конфликтный.
Центральная станция на следующем шаге корректирует количество оставшихся не обслуженными заявок и число оставшихся свободными каналов. После этого БС распределяет свободные каналы среди абонентов, которые не участвовали в бесконфликтном распределении. То есть, предлагается алгоритм, в котором после первой попытки (шага) распределить L каналов среди т абонентов, БС корректирует информацию о числе свободных каналов и числе активных абонентов и повторяет процедуру (делает второй шаг) и т.д. до тех пор, пока не будут распределены все L каналов или не будут обслужены все заявки абонентов.
Будем далее для упрощения рассуждений предполагать, что процедура распределения каналов занимает значительно меньшее время, чем время обслуживания одного абонента, т.е. за время распределения каналов ни один абонент, получивший канал на первом шаге к последнему шагу распределения не освободит предоставленный ему канал.
В результате задачу оптимизации можно формально представить так: требуется при известных L,p,N определить алгоритм пошагового изменения параметра г, который обеспечит наискорейшее распределение всех свободных каналов либо удовлетворения всех заявок на обслуживание. Решение задачи
Пусть Ly._, - число радиоканалов распределенных к у -му шагу, г, - число абонентов, которым предлагается занять один из свободных радиоканалов на j -ом шаге. Тогда в результате у-го шага свободными останется L-Lj каналов, а распределено будет Z,y - /,_,_, каналов. При этом общее число абонентов, потенциально продолжающих участвовать в доступе уменьшится на (Lj -Lh\rr Будем его обозначать Nг Число активных абонентов также уменьшится на Lj-LH. Следует отметить, что согласно построению алгоритма N N.. \ г —, 1 г, J-±—, j = \,..n.
Случайная последовательность {Z,y}, описывающая процесс распределения каналов, представляет собой простую марковскую цепь с переходной вероятностью P{LJ/Lj_x,rj)=Pk, которая является вероятностью распределения ровно Lj-Lj_y=k каналов. Выбирая значения г,, можно изменять переходную вероятность и, таким образом, управлять указанной Марковской цепью.
В рассматриваемой задаче, как указывалось выше, используется критерий качества, согласно которому лучшим (оптимальным) алгоритмом управления является тот, который обеспечивает минимальное число шагов при заданной вероятности Р полного распределения всех L каналов (или обслуживания всех абонентов).
Управлением в этом случае заключается в формировании последовательность таких {г}}, которые удовлетворяют выбранному критерию качества. Поэтому будем называть {г} оптимальной стратегией, обеспечивающей распределение всех каналов с заданной вероятностью за наименьшее число шагов.
Похожие диссертации на Методы оптимального распределения частотно-временного ресурса в системах подвижной радиосвязи
