Статистический анализ информационных систем тензорным методом при наличии случайных искажений тема диссертации и автореферата по ВАК РФ 01.04.03, кандидат физико-математических наук Золотарев, Сергей Владимирович

• Золотарев, Сергей Владимирович
• кандидат физико-математических наук
• 2008

Оглавление диссертации кандидат физико-математических наук Золотарев, Сергей Владимирович

ОГЛАВЛЕНИЕ.

Введение.

1. Тензорный анализ стабильности информационных систем при наличии помех.

1.1 Постановка задачи.

1.2 Узел коммутации как усилительный «прибор».

1.3 Основные характеристики узла коммутации в режиме «усиления».

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

1.5 Тензорный анализ стабильности узлов пакетной радиосети.

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

1.7 Резюме.

2. Алгоритм нахождения экстремума выпуклой целевой функции при наличии ограничений. Энергетический подход.

2.1 Постановка задачи оптимизации.

2.2 Энергетический подход к решению задачи оптимизации.

2.3 Алгоритм условной оптимизации.

2.5 Тензорный метод реализации энергетического подхода.

2.6 Тензорный метод нахождения оптимальных пугевых потоков.

2.7 Сравнение алгоритма с наиболее распространенными алгоритмами условной оптимизации.

2.8 Резюме.

3. Оптимальная альтернативная маршрутизация в пакетных радиосетях.

3.1 Основные понятия.

3.2 Постановка задачи.

3.3 Пропускные способности линий связи.при наличии замираний.

3.4 Алгоритм оптимальной альтернативной маршрутизации.

3.5 Числовой пример.

3.6 Резюме.

4. Оптимальное распределение мощности излучения в информационных сетях.

4.1 Постановка задачи.

4.2 Алгоритм условной оптимизации.

4.3 Адаптивный алгоритм оптимизации.

4.4 Оптимизация по критерию минимума среднего числаповторных передач.

4.5 Оптимизация мощности при наличии замираний сигнала.

4.6 Оптимальное распределение мощности в OFDM-системах. при наличии замираний.

4.7 Резюме.

Введение диссертации (часть автореферата) на тему «Статистический анализ информационных систем тензорным методом при наличии случайных искажений»

Актуальность темы. В последнее время все большее внимание уделяется проблемам анализа телекоммуникационных систем передачи информации, в частности, пакетных радиосетей [2, 8, 11]. Это обусловлено растущими потребностями в обслуживании мобильных абонентов связи. Упрощенно пакетную радиосеть можно представить в виде совокупности узлов коммутации, соединенных между собой беспроводными линиями связи. Во многих случаях пакетные радиосети предусматривают возможность промежуточного хранения информации в специальных устройствах накопления узлов коммутации.

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

Кроме проблемы множественного доступа для пакетных радиосетей имеет место сложный и изменчивый во времени характер распространения сигналов по линиям связи. Действительно, в линиях связи пакетной радиосети часто присутствуют явления многолучевого распространения радиоволн, что приводит к замираниям сигнала [7, 26, 29]. Это может существенно ухудшить помехоустойчивость и, соответственно, эффективность передачи информации, что, в свою очередь, спровоцирует рост длин очередей. Поэтому одной из приоритетных задач, возникающих на этапе проектирования и эксплуатации ралиосетей, является организация и поддержание такого режима функционирования сети, который был бы оптимален в плане некоторого заранее выбранного критерия. При этом алгоритм, применяемый на этапе проектирования сети, в силу непостоянства параметров линии связи должен иметь адаптивный вариант, который являлся бы работоспособным непосредственно при работе (эксплуатации) сети.

В качестве примера можно привести задачу оптимальной альтернативной (многопутевой) маршрутизации, подробно рассмотренную в отечественной и зарубежной литературе [2, 5, 6, 8, 9 и пр.]. Правило маршрутизации, оптимальное по критерию минимума средней задержки по сети, позволяет снизить время ожидания пакетов в очередях. Другим примером повышения эффективности может служить оптимальное распределение мощностей излучения по исходящим линиям связи многоканальных узлов коммутации радиосети. Значение мощности излучения по конкретной линии определяет помехоустойчивость приема информации узлом-получателем, что, в свою очередь, характеризует число повторных передач и, следовательно, длину очереди на передачу по данной линии. Поэтому эффективное распределение мощности по исходящим линиям связи позволяет производить выравнивание качества передачи информации по всем исходящим линиям и уменьшение числа пакетов в очередях выбранного узла коммутации. Проблема оптимального распределения мощности излучения касается и OFDM-систем, для которых необходимо добиться наивысшей пропускной способности путем распределения суммарной излучаемой мощности по подканалам. Для решения вышеперечисленных задач необходимо использовать итеративные методы условной оптимизации при наличии ограничений, которых к настоящему моменту существует довольно много. Однако многие из них, применяемые на практике, сложны в реализации или требуют достаточно большого числа итераций, что, безусловно, является их минусом. В настоящей диссертации разработан новый алгоритм условной оптимизации, который работает существенно быстрее своих аналогов и довольно прост в реализации. Предложенный алгоритм, а также тензорный метод его реализации, являются новыми и выносятся на защиту.

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

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

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

• разработка нового алгоритма условной оптимизации при наличии i ограничений и описание тензорной методики его реализации;

• разработка адаптивного алгоритма оптимизации при использовании непосредственно в процессе работы системы;

• сравнение разработанных алгоритмов с существующими аналогами с помощью имитационного моделирования на ЭВМ;

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

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

• решение задач оптимального распределения мощности излучения по подканалам OFDM-системы по критерию максимума суммарной пропускной способности системы при наличии замираний Накагами.

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

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

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

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

• новый алгоритм условной оптимизации при наличии ограничений, основанный на энергетическом подходе к анализу сети, позволяет оптимизировать сети произвольного типа, для которых имеется выпуклая целевая функция и линейные ограничения как следствие закона сохранения потока. Алгоритм Франка-Вольфа и производный от него алгоритм отклонения потока, а также некоторые проекционные градиентные методы, в ряде случаев сходятся медленнее предложенного алгоритма. Предложенный алгоритм реализуется за одну итерацию при квадратичном виде целевой функции;

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

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

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, содержащего 43 наименования. Включает 26 рисунков и 8 таблиц. Общий объем работы 119 листов.

Заключение диссертации по теме «Радиофизика», Золотарев, Сергей Владимирович

Заключение

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

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

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

3. Разработан адаптивный метод оптимизации для использования непосредственно при работе сети;

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

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

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

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

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

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

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Золотарев, Сергей Владимирович, 2008 год

1. Батушев В. А. Электронные приборы: учебник для вузов. - 2-е изд., пере-раб. и доп. - М.: Высш. школа, 1980. -383 с.

2. Бертсекас Д., Галлагер Р. Сети передачи данных: Пер. с англ. М.: Мир, 1989.-544 с.

3. Будницкий Я. Усилители низкой частоты на транзисторах: Пер. с чешского/Под ред. К. М. Брежневой. -М.: Связьиздат., 1963 г.

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

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

6. Дэвис Д., Барбер Д., Прайс У., Соломонидес С. Вычислительные сети и сетевые протоколы: Пер. с англ. М.: Мир, 1981. - 563 с.

7. Зюко А. Г. Помехоустойчивость и эффективность систем связи. М.: Связь, 1972.-360 с.

8. Клейнрок Л. Коммуникационные сети: Пер. с англ. М.: Наука, 1975. -256 с.

9. Клейнрок Л. Вычислительные системы с очередями: Пер. с англ. М.: Мир, 1979.-600 с.

10. Крон Г. Тензорный анализ сетей: Пер. с англ.//Под ред. Л. Т. Кузина, П. Г. Кузнецова. М.: Сов. Радио, 1978. - 719 с.

11. Мизин И. А., Богатырев В. А., Кулешов А. П. Сети коммутации пакетов. М.: Радио и связь, 1986. - 408 с.

12. Павлов В. Н., Ногин В. Н. Схемотехника аналоговых полупроводниковых устройств: учебник для вузов. 2-е изд., испр. — М.: Горячая линия - Телеком, 2003 г.

13. Парфенов В.И. Прием узкополосного случайно модулированного сигнала / Парфенов В.И., Золотарев С.В. // Вестник ВГУ, Серия: Математика, физика. Воронеж, ВГУ, 2005. - Вып. 1. - С. 86-92.

14. Парфенов В.И. Анализ сетей передачи данных тензорным методом /

15. B.И. Парфенов, С.В. Золотарев //Материалы Всероссийской научно-практической конференции «Охрана, безопасность и связь 2005». - Воронеж, Воронежский институт МВД РФ, 2005. - Часть 2. - С.81.

16. Парфенов В.И. Тензорный подход к решению задачи оптимальной маршрутизации в информационных сетях / Парфенов В.И., Золотарев С.В. // Теория и техника радиосвязи. Воронеж, ОАО «Концерн «Созвездие», 2007. — Вып.2. С.5-11.

17. Парфенов В.И. Об одном алгоритме решения задачи оптимальной маршрутизации по критерию средней задержки / Парфенов В.И., Золотарев

18. C.В. // Вестник ВГУ, Серия: Математика, физика. Воронеж, ВГУ, 2007. -Вып.2.-С. 28-33.

19. Парфенов В.И. Алгоритм условной минимизации целевой функции для оптимального выбора маршрутов в информационных сетях / Парфенов В.И., Золотарев С.В. // Изв. Вузов. Радиоэлектроника, 2008. Т.51. - №5 - С. 12-22.

20. Парфенов В.И. Процессы усиления в информационных сетях с промежуточным хранением информации / Парфенов В.И., Золотарев С.В. // Изв. Вузов. Радиоэлектроника, 2007. Т.50. - №7. С.21-30.

21. Парфенов В.И. Оптимальный выбор маршрутов в сетях передачи данных. Энергетический подход / Парфенов В.И., Золотарев С.В. // Изв. Вузов. Радиоэлектроника, 2008. -Т.51. №10. - С.56-69.

22. Пасечников И. И. Методология анализа и синтеза предельно нагруженных информационных сетей. М: "Издательство МАШИНОСТРОЕНИЕ -1", 2004.-216 с.

23. Пасечников И. И. Модельное отображение информационных се гей // Изв. вузов. Радиоэлектроника. 2004. Т. 45, № 4. С. 9 18.

24. Петров М. И. Исследование характеристик распределенных систем методом тензорного анализа и теории массового обслуживания. Дис. . д-ра техн. Наук. Красноярск: КрГУ, 1998 г. — 240 с.

25. Прокис Д. Цифровая связь. Пер. с англ.// Под ред. Д. Д. Кловского. -М.: Радио и связь. 2000. 800 с.

26. Пышкин И. М. Теория кодового разделения сигналов. М. Связь, 1980.-208 с.

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

28. Скляр Б. Цифровая связь. Теоретические основы и практическое применение: Пер. с англ. М.: Издательский дом «Вильяме», 2003. - 1104 с.

29. ТИИЭР, т. 75, №1. Тематический выпуск ПАКЕТНЫЕ РАДИОСЕТИ: Пер. с англ. М.: Мир, 1987 г.

30. Финк JI. М. Теория передачи дискретных сообщений. М.: Советское радио, 1963.

31. Шварц М. Сети связи: протоколы, моделирование и анализ. М.: Наука, 1992.

32. Шеннон К. Э. Работы по теории информации и кибернетике. М.: Иностранная литература, 1963.

33. Bertsekas D. P., Constraint Optimization and Lagrange Multiplier Methods, New York, Academic Press, 1982.

34. Cannon M. D., Cullum C. D., A Tight Upper Bound on the Rate of Convergence of the Frank Wolfe Algorithm, SIAM J Contr Optim, 6, 509-516, 1968.

35. Cantor D. G., Gerla M. Optimal routing in a packet-switched computer net-work//IEEE Trans. On Computers. 1974. - V. C-23,N 10. - P.1062-1068.

36. Chih-ping Li, Wei-jen Hsu, Bhaskar Krishnamachari and Ahmed Ilelmy, A Local Metric for Geographic Routing with Power Control in Wireless Networks, IEEE SECON, September 2005.

37. Dunn J. C., Rates of Convergence of Conditional Gradient Algorithms Near Singular and Nonsingular Extremals, SIAM J Contr Optim, 17 187-211, 1979.

38. Frank M., Wolfe P. An algorithm for quadratic programming // Naval Research Logistic Quarterly. 1956. - N 3. - P. 95-110.

39. Fratta L., Gerla M., Kleinrock L. The flow deviation method: An approach to store and forward communication network design // Networks. 1973. - V. 3, N2.-P. 97-133.

40. Gerla M., Kleinrock L. On the topological design of distributed computer networks//IEEE Trans. On Commun. 1977. - V. COM - 25, N 1. - P. 48-53.

41. Schwartz M., Cheung С. K. The gradient projection algorithm for multiple routing in message-switched networks // IEEE Trans. On Commun. 1976. - V. 25.-P. 100-127.

42. Theodor S. Rappapport, Wireless Communications: Principles and Practice, Prentice Hall.