Статистический анализ информационных систем тензорным методом при наличии случайных искажений

Золотарев, Сергей Владимирович

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

Золотарев, Сергей Владимирович АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Воронеж МЕСТО ЗАЩИТЫ

2008 ГОД ЗАЩИТЫ

01.04.03 КОД ВАК РФ

Диссертация по физике на тему «Статистический анализ информационных систем тензорным методом при наличии случайных искажений»

Автореферат диссертации на тему "Статистический анализ информационных систем тензорным методом при наличии случайных искажений"

На правах рукописи

.....•

Золотарев Сергей Владимирович

СТАТИСТИЧЕСКИЙ АНАЛИЗ ИНФОРМАЦИОННЫХ СИСТЕМ ТЕНЗОРНЫМ МЕТОДОМ ПРИ НАЛИЧИИ СЛУЧАЙНЫХ ИСКАЖЕНИЙ

Специальность 01.04.03 - «Радиофизика»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико - математических наук

Воронеж - 2008

003456823

Работа выполнена в Воронежском государственном университете.

Научный руководитель - доктор физико - математических наук,

доцент ПАРФЕНОВ Владимир Иванович

Официальные оппоненты: доктор физико - математических наук,

профессор ЛУКИН Александр Николаевич

Ведущая организация - ОАО «Концерн «Созвездие», г. Воронеж.

Защита состоится 25 декабря 2008 г. в 1700 на заседании диссертационного совета Д. 212.038.10 при Воронежском государственном университете по адресу: 394006, г. Воронеж, Университетская площадь, 1, ВГУ, физический факультет, ауд.435.

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

Автореферат разослан 24 ноября 2008 г.

доктор технических наук,

профессор СИРОТА Александр Анатольевич

Ученый секретарь диссертационного совета

МАРШАКОВ В.К.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Личный вклад автора.

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

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на

• ХП, XIII, XIV международных научно-практических конференциях «Радиолокация, Навигация, Связь.» (г. Воронеж) в 2006, 2007, 2008 г.;

• Всероссийской научно-практической конференции «Охрана, безопасность и связь - 2005». - Воронеж, Воронежский институт МВД РФ, 2005 г.

Публикации. По теме диссертации опубликовано 10 работ, из них 4 работы - в Журналах, рекомендованных ВАК для публикации результатов диссертационных работ.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

При введении новой модели узла коммутации сначала он представлялся как одноканальная система массового обслуживания (рис.1,а), состоящая из последовательно соединенных устройства накопления пакетов (УН) и канала связи (КС). Затем входной стохастический поток пакетов разделялся на два потока. Первый поток, который назовем базовым, состоит из пакетов, которые в момент своего прихода в УК нашли канал связи свободным для передачи. Второй поток, которые будем называть буферным, состоит из пакетов, которые из-за занятости КС попали в УН. Суммарный входной поток было принято назвать истоковым. Таким образом, УК можно схематически изобразить в виде трехпо-люсника, который показан на рис. 1,6, где X, Хх и Х^ равны средним интен-сивностям истокового, базового и буферного потока соответственно. При этом выводы УК были названы «истоком», «базой» и «буфером» в соответствии с протекающими через них потоками.

УН

КС

-в

юк Ч_У

буфер

^ X

а б

Рис. 1.

Интенсивности всех вышеперечисленных потоков связаны простыми соотношениями: X = Ху + Х1Г, Хх = рхХ и >.„, = ршХ, где рх и р,л, - вероятности того, что отдельный пакет принадлежит первому и второму потоку соответст-

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

Рх

в котором множитель к - pw! рх можно интерпретировать как статический коэффициент усиления интенсивности базового потока (аналог коэффициента усиления базового тока транзистора в схеме с общим эмиттером). Таким образом, УК был представлен в виде "прибора" с тремя выводами, способного выполнять усилительные функции. Под усилением понималось явление значительного (особенно в случае сильной загрузки КС) увеличения числа пакетов в УН, вызванное приращением интенсивности потока пакетов в КС.

Было произведено описание предложенной модели УК с помощью методов теории четырехполюсника. При этом сам УК представлялся в виде четырехполюсника с парой входных и выходных «зажимов». Среднее число пакетов на входе четырехполюсника обозначалось Nx, а накопления пакетов на выходе -N2. Считалось, что данные накопления пакетов вызваны соответствующими входным и выходным потоками с интенсивностями А,, и Х2. По аналогии с описанием электронных усилительных приборов при работе в режиме малого сигнала были введены и расписаны различные системы параметров УК как четырехполюсника, например, Z-параметры, g-параметры и Л-параметры. На основе последних был разработан алгоритм учета процедур управления входным потоком за счет внутренней отрицательной обратной связи.

Представление УК как четырехполюсника, который обладает собственными и взаимными внутренними проводимостями (g-параметры), позволило применить тензорный метод анализа Г. Крона для нахождения чувствительности длины очередей интересующего нас УК сети в зависимости от величины изменения интенсивности любого путевого потока. Само явление наличия такой чувствительности вызвано наличием множественного доступа к каналу связи со стороны нескольких УК радиосети при условии, что передача сигналов идет в одной полосе частот. Поэтому, если используется протокол доступа к каналу типа ALOHA, то будут неизбежно возникать искажения пакетов вследствие их наложения друг на друга из-за взаимного перекрытия во времени.

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

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

Проблема оптимизации процессов передачи и хранения информации, пожалуй, является наиболее важной при проектировании и эксплуатации телекоммуникационных систем. Основное содержание проблемы заключается в следующем: имея некоторую целевую (стоимостную) функцию сети необходимо найти такое значение аргумента этой функции, которое бы приводило к ее экстремуму (минимуму или максимуму в зависимости от постановки задачи) при наличии ограничений для аргумента. При этом аргумент является вектором, а ограничения накладываются на его компоненты. Эта задача является частным случаем более общей задачи, которую определим так. Пусть есть система (не обязательно информационная), состоящая из двух узлов, соединенных между собой с помощью М параллельных ветвей. Пусть на вход системы поступает поток (произвольной природы) постоянной величины Л, который необходимо распределить между всеми ветвями так, чтобы обеспечить экстремум некоторой заранее выбранной стоимостной функции ...../м ), где / - поток по I-й ветви. Обозначим вектор потоков через ветви { = (/,,••.,/„)■ Специфика поставленной задачи состоит в том, что имеют место следующие условия:

1=1

2. 0< /, <Л для любого ге[1,М];

3. Частные производные целевой функции дО({)1 д/г отличны от нуля и имеют одинаковый знак, что говорит о выпуклости целевой функции.

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

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

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

Была рассмотрена потоковая модель пакетной радиосети с альтернативной маршрутизацией сообщений. Считалось, что сеть состоит из N узлов коммутации и М линий связи. Предполагалось, что:

1)все линии связи абсолютно надежны;

2)все линии связи независимы и разделены между собой по одному из известных методов (частотное, временное, кодовое разделение);

3)узлы коммутации имеют бесконечную память;

4)время обработки в узлах коммутации отсутствует;

5)длины всех сообщений независимы и распределены по показательному закону со средним значением 1/ц [байт];

6)трафик, поступающий в сеть, состоит из сообщений, имеющих одинаковый приоритет, и образует пуассоновский поток со средним значением уа [со-

общений/сек] для сообщений, возникающих в узле к и предназначенных узлу

-V N

/. Обозначим у-^ЦУи ' полный внешний трафик. Пропускная способность

к=1 Ы

I - й линии связи равна С, [байт/сек].

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

1 и { м

уй'цс,-/ £

где / - суммарный поток [сообщений/сек], протекающий по линии /, а /)(/) = //у(цС, - является средней задержкой сообщенияв г-йлинии.

Сделанные предположения и обозначения позволили сформулировать задачу поиска таких значений потоков / , образующих вектор I = (/,,..,/и), которые обеспечат оптимальное (наименьшее) значение величине О. При этом полагались известными:

1) топологическая структура ИС;

2) входные потоки

3) пропускные способности линий связи С,;

4) средняя длина сообщения 1/ц. Требовалось найти: потоки в линиях связи / такие, что:

1 " /■ У-'ЦС,-/ при выполнении следующих ограничений:

0< / <цС,; /' = 1,2,...,М ■ Данная задача, которая называется задачей выбора оптимачьных потоков в информационной сети по критерию минимума средней задержки, была успешно решена в третьей главе диссертации.

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

ям сигнала. Были получены выражения для средних пропускных способностей ЛС при следующих моделях замираний:

• медленные рэлеевские замирания;

• замирания Накагами;

• замирания Рэлея-Райса.

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

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

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

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

Из рисунка видно, что по мере реализации алгоритма оптимизации осуществляется своего рода выравнивание линий по числу повторных передач на один пакет. Это происходит за счет переброски мощностей с наиболее благоприятных в плане воздействия замираний на наименее благоприятные в этом

100 1

2 3 4 Номер итерации к

Рис.2. Зависимости количества повторных передач на один пакет для пяти исходящих линий от номера итерации алгоритма оптимизации

плане линии. Таким образом, осуществляется в некотором смысле справедливое выравнивание.

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

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

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

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

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

Номер нтерапни, к

Рнс.З. Зависимости пропускных способностей подканалов ОРОМ-систсмы с различными мощностями замираний в зависимости от номера итерации алгоритма оптимизации

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

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

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

♦ Основные результаты диссертации опубликованы в работах:

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

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

3. Парфенов В.И. Анализ эффективности передачи и хранения информации в пакетных радиосетях при наличии помех с использованием обобщенной ортогональной подразделенной модели / В.И. Парфенов, C.B. Золотарев // Материалы XII Международной научно-технической конференции «Радиолокация, навигация, связь». - Воронеж, 2006. - Т.2. - С.776-784.

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

5. Парфенов В.И. Об одном алгоритме решения задачи оптимальной маршрутизации по критерию средней задержки / Парфенов В.И., Золотарев С.В // Вестник ВГУ, Серия: Математика, физика. - Воронеж, ВГУ, 2007. -Вып.2.-С. 28-33.

6. Парфенов В.И. Алгоритм условной минимизации целевой функции для оптимального выбора маршрутов в информационных сетях / Парфенов

B.И., Золотарев C.B. // Изв. Вузов. Радиоэлектроника, 2008. - Т.51. - №5.-

C. 12-22.

7. Парфенов В.И. Тензорный анализ чувствительности узлов пакетной радиосети в условиях изменчивой помеховой обстановки / В.И. Парфенов, СВ. Золотарев // Материалы XIII Международной научно-технической конференции «Радиолокация, навигация, связь». - Воронеж, 2007. - Т.2. -С.925-936.

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

9. Парфенов В.И. Оптимальное распределение мощности излучения в пакетных радиосетях по критерию минимума среднего числа повторных передач / В.И. Парфенов, C.B. Золотарев // Материалы XIV Международной научно-технической конференции «Радиолокация, навигация, связь». - Воронеж, 2008. -Т.2.-С.901-910.

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

Работы № 4, 6, 8,10 опубликованы в изданиях, соответствующих перечню ВАК РФ.

Подписано в печать 21.11.08. Формат 60*84 7,в. Усл. печ. л. 1. Тираж 110 экз. Заказ 2199

Ошечагаио с готового оригинала-макета в типографии Излательско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3.

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

ОГЛАВЛЕНИЕ.

Введение.

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 может быть использован непосредственно при работе сети на основе периодических отчетов целевой функции, когда аналитический вид или некоторые ее параметры неизвестны.

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

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

Заключение диссертации по теме "Радиофизика"

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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.