Исследование методов оптимизации систем передачи данных по результатам оценки качества канала
На правах рукописи
Коновалов Павел Анатольевич
ИССЛЕДОВАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ
СИСТЕМ ПЕРЕДАЧИ ДАННЫХ
ПО РЕЗУЛЬТАТАМ ОЦЕНКИ КАЧЕСТВА КАНАЛА
Специальность 05.12.13 Системы, сети и устройства телекоммуникаций
Автореферат
диссертации на соискание учёной степени
кандидата технических наук
НОВОСИБИРСК 2006
Работа выполнена на кафедре передачи дискретных сообщений и метрологии Сибирского государственного университета телекоммуникаций и информатики.
Научный руководитель – кандидат технических наук,
доцент Мелентьев О.Г.
Официальные оппоненты – доктор технических наук,
профессор Поллер Б.В.
– кандидат технических наук,
профессор Макаров А. А.
Ведущее предприятие указано в решении диссертационного совета.
Защита состоится «27» июня 2006 г. в 10.00 часов на заседании диссертационного совета Д 219.005.01. при Сибирском государственном университете телекоммуникаций и информатики по адресу: 630102, Новосибирск, ул. Кирова, 86.
С диссертацией можно ознакомиться в читальном зале библиотеки СибГУТИ.
Автореферат разослан «25» мая 2006 г.
Учёный секретарь
диссертационного совета Д 219.005.01,
кандидат технических наук, профессор ____
_ Б.И. Крук
Общая характеристика работы
Актуальность работы: Обострение конкурентной борьбы операторов связи требует введения новых услуг и повышения качества обслуживания. Это обуславливает необходимость обеспечения гарантированных показателей задержки, верности и скорости передачи при минимизации затрат. Но реальные каналы имеют нестационарный характер особенно в беспроводных системах передачи данных, таких как Wi-Fi, WiMAX, MBWA. Наилучших качественных показателей в таких условиях позволяют достичь адаптивные системы передачи.
Вопросами анализа адаптивных систем занимались М.Н. Арипов, Э.Л. Блох, Н.Н. Буга, Л.П. Коричнев, Л.А. Растригин, Ю.Г. Ростовцев, Б.Я. Советов, А.И. Фалько, В.А. Шапцев, В.П. Шувалов, M. Zorzi и другие.
Адаптивная система предполагает контроль условий передачи и адекватную реакцию на их изменения. Контроль условий передачи может осуществляться на различных уровнях системы и по различным параметрам. На канальном уровне наименее затратной является оценка состояния канала по качеству приема блока. Данная оценка проводится для каждого принятого блока, а её результаты являются естественным источником информации о состоянии канала при использовании систем с решающей обратной связью с адресным переспросом (РОС-АП).
Важным моментом является выбор алгоритма, использующего информацию о качестве приема блока и на основе этого принимающего решение об изменении состояния канала. Время, затрачиваемое при использовании данных алгоритмов, и ошибки при определении состояния канала во многом будут определять производительность системы в целом.
В работах A. Annamalai, V. Bhargava, M. Rice и S. Cho описан ряд алгоритмов использования сигналов переспроса. Предложены отдельные методики оценки эффективности алгоритмов. Однако всё ещё актуальным остается вопрос разработки универсальных методик, позволяющих анализировать и сравнивать различные алгоритмы с приемлемой точностью и при сравнительно небольших затратах вычислительных ресурсов.
Цель работы: Разработка моделей адаптивных систем и методик оценки и оптимизации их вероятностно-временных характеристик, обеспечивающих передачу данных по дискретному каналу с двумя и тремя состояниями.
Методы исследования: В диссертации представлены результаты исследований, полученные с помощью аппарата теории вероятностей, теории марковских цепей, имитационного и математического моделирования.
Научная новизна:
- Разработаны обобщенные методики анализа и оптимизации адаптивных систем передачи данных с изменением длины блока, учитывающие одновременно:
- время, затрачиваемое на определение состояния дискретного канала;
- ошибки в определении состояния канала;
- исходные вероятностные характеристики дискретного канала, отражающие процесс изменения его состояний.
Методики позволяют анализировать производительность различных алгоритмов адаптации при работе по дискретному каналу с двумя и тремя состояниями. В отличие от известных, в данных методиках использовано масштабирование дискретного шага системы, описываемой марковской цепью, позволяющее упростить модели и сократить время моделирования.
- Предложен алгоритм адаптации со скользящим окном наблюдения переменной длины (СОН-ПД), позволяющий получить большую производительность относительно известных.
- Разработаны аналитические модели алгоритмов адаптации с оценкой успешных и ошибочных приемов (ОУОП), со скользящим окном наблюдения (СОН), со скользящим окном наблюдения переменной длины (СОН-ПД), с фиксированным периодом наблюдения (ФПН) и с переменным периодом наблюдения (ППН), позволяющие получать оценки производительности адаптивной системы в зависимости от параметров алгоритма и параметров дискретного канала с двумя и тремя состояниями.
- Разработаны имитационные модели алгоритмов адаптации ОУОП, СОН, СОН-ПД, ФПН и ППН для дискретного канала с двумя и тремя состояниями.
Практическая ценность работы и внедрение её результатов: Разработаны методики расчета и оптимизации вероятностно-временных характеристик (ВВХ) систем передачи данных, позволяющие проектировать эффективно работающие системы передачи данных.
Апробация работы. Основные положения работы докладывались на следующих семинарах и конференциях:
- Международном семинаре «Электронные приборы и материалы», EDM. – Эрлагол, 2004, 2005.
- IV-Всероссийская научно-практическая конференция «Информационные Недра Кузбасса-2005». – Кемерово, 2005.
- Всероссийская научно-техническая конференция «Измерение, Автоматизация и Моделирование в Промышленности и Научных Исследованиях». – Бийск, 2005.
- Всероссийской научной конференции «Наука. Технологии. Инновации» (НТИ-2005). – Новосибирск, 2005.
- Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций». – Новосибирск, 2006.
- Международная научно-техническая конференция «Перспективы развития современных средств и систем телекоммуникаций». – Екатеринбург, 2006.
Публикации. По теме диссертации опубликовано 11 работ. В их числе: 1 статья, 2 депонированных рукописи и 8 докладов.
Структура и объем диссертации: Диссертационная работа состоит из введения, четырех глав и шести приложений. Содержит 160 страниц, 1 таблица, 60 рисунков. Список литературы состоит из 62 наименований.
Основные результаты, выносимые на защиту:
- Обобщенные методики анализа и оптимизации адаптивной системы с изменением длины блока, позволяющая анализировать производительность различных алгоритмов адаптации при работе по дискретному каналу с двумя и тремя состояниями.
- Методика масштабирования дискретного шага системы, описываемой марковской цепью, позволяющая упростить модели адаптивных алгоритмов и сократить время моделирования.
- Алгоритм адаптации со скользящим окном наблюдения переменной длины (СОН-ПД).
- Аналитические модели алгоритмов адаптации ОУОП, СОН, СОН-ПД, ФПН и ППН, позволяющие получать оценки производительности адаптивной системы в зависимости от параметров данного алгоритма и параметров дискретного канала с двумя состояниями.
- Аналитическая модель алгоритма адаптации ОУОП, позволяющая получать оценку производительности адаптивной системы в зависимости от параметров алгоритма и параметров дискретного канала с тремя состояниями.
- Имитационные модели алгоритмов адаптации ОУОП, СОН, СОН-ПД, ФПН и ППН для дискретного канала с двумя и тремя состояниями.
Краткое содержание работы
Во введении обоснована актуальность темы диссертации, сформулированы цель исследований, научная новизна и практическая ценность результатов диссертации.
В первой главе рассмотрены вопросы построения адаптивных систем передачи данных. Для различных уровней модели ВОС (OSI) проанализированы параметры, контроль которых позволяет принимать решение об изменении состояний канала.
На уровне канала передачи данных критерием качества является факт обнаружения или не обнаружения ошибок в принятом блоке. При обнаружении ошибок в блоке система формирует сигналы переспроса. Частота появления этих сигналов является естественным и во многих случаях достаточным источником информации о состоянии канала. В более сложных случаях можно контролировать кратность ошибок в блоках, факты повторного обнаружения ошибок после их исправления в системах с гибридной обратной связью и т.д.
Реакцией на изменившиеся условия передачи может быть изменение длин передаваемых блоков, смена корректирующего кода, изменение глубины перемежения или длин слота хоппинга совместно с исправляющей способностью кода и т.д. Изменение большинства параметров системы на уровне дискретного канала и канала передачи данных можно учесть соответствующим изменением длин блоков и производительности системы в том или ином состоянии.
Рассмотрены вопросы применения операций перемежения и хоппинга в адаптивных системах. Показана целесообразность применения данных операций в случаях, когда средняя длина состояния канала соизмерима с длиной блока. Если средние длины состояний канала много больше длины блока, то целесообразно использовать алгоритмы с контролем качества приема блока.
Приведен анализ известных адаптивных алгоритмов оценки состояния дискретного канала с изменением длины блока по результатам контроля качества приема. Предложен адаптивный алгоритм со скользящим окном наблюдения переменной длины (СОН-ПД).
Проанализированы различные модели источников ошибок в дискретных каналах, использующихся в настоящее время для анализа ВВХ систем передачи данных. Анализ показал, что наиболее часто для построения моделей источников ошибок применяют марковские цепи с разным числом состояний. С увеличением числа состояний модели возрастает точность описания канала, но при этом значительно увеличиваются затраты времени на определение параметров модели и оптимизацию внутренних параметров системы, что затрудняет использование этих моделей в адаптивных системах.
В качестве критерия для сравнения различных адаптивных алгоритмов предложено использовать производительность системы. Под производительностью системы будем понимать произведение скорости кода на вероятность правильного приема блока длиной n элементов 
(1) где 
- длина блока в состоянии 
, 
- число служебных элементов, 
- вероятность правильного приема блока длиной 
.
Далее определяется максимальное значение производительности адаптивной системы с изменением длины блока при работе по заданному каналу (
), которое обеспечивается только в идеальной системе, которая мгновенно и безошибочно определяет состояние канала и изменяет длину блока на оптимальную для новых условий. К основным факторам, снижающим производительность адаптивной системы, относится время, затрачиваемое на определение состояния канала и ошибки определения данного состояния. Нижний предел производительности адаптивных систем определяет система с фиксированной длиной блока, оптимизированной для данного канала. Найденные границы характеризуют потенциальный выигрыш, который может быть достигнут от применения адаптивной системы
Таким образом, встает задача выбора адаптивных алгоритмов, которые позволяют не только быстро определить новое состояние канала, но и минимизировать число ложных реакций системы (ошибочных изменений длины блока).
Далее рассматривается методика масштабирования дискретного шага системы при её описании марковской цепью. Показано, что при моделировании работы адаптивной системы в качестве дискретного шага целесообразно выбирать длины блоков, оптимальные для каждого состояния. Однако, длина блока зависит от состояния, поэтому необходимо пересчитывать значения вероятностей, приведенных к длине блока, в вероятности, приведенные к одинаковому шагу, в частности к единичному элементу.
Применение данной методики позволяет упростить модели и значительно сократить время моделирования. Кроме того, методика позволяет снизить требования к точности представления чисел в процессе моделирования, что в ряде случаев уменьшает погрешность вычислений.
Обоснована необходимость разработки обобщенной методики анализа адаптивной системы с изменением длины блока, позволяющей анализировать производительность различных алгоритмов адаптации при работе по дискретному каналу с двумя и тремя состояниями. Данная методика должна одновременно учитывать время, затрачиваемое на определение состояния дискретного канала; ошибки возможные при оценке состояния; исходные вероятностные характеристики дискретного канала, отражающие процесс изменения его состояний. Кроме того, показана целесообразность разработки аналитических и имитационных моделей адаптивных алгоритмов, позволяющих получать оценки производительности адаптивной системы в зависимости от параметров алгоритма и параметров дискретного канала с двумя и тремя состояниями.
Во второй главе предлагается обобщенная методика оценки производительности системы передачи данных для различных адаптивных алгоритмов контроля длины передаваемых блоков при работе по дискретному каналу с двумя состояниями.
Состояния канала S1 и S2 характеризуются соответствующими вероятностями ошибки на единичный элемент 
и 
. Смена состояний описывается марковской цепью с двумя состояниями и соответствующими переходными вероятностями. Показано, что в процессе работы адаптивной системы по каналу с двумя состояниями дополнительно возникают два промежуточных состояния.
Пусть в некоторый момент времени дискретный канал находится в состоянии 
, а система использует для передачи блоки с оптимальной для данного случая длиной 
. Обозначим данное производное состояние 
. Через какое-то время дискретный канал изменит свое состояние на 
, но системе будет требоваться некоторое время на определение нового состояния канала. В течение этого времени будет сохраняться прежняя длина блока. Таким образом, возникает производное промежуточное состояние 
. После определения нового состояния система изменит длину блока 
и перейдет в состояние 
. Возврат дискретного канала в состояние 
также требует определения нового состояния. В этом случае система какое-то время будет сохранять прежнюю длину блока – это второе промежуточное состояние 
.
В данном случае поведение системы может быть описано марковской цепью с четырьмя состояниями и вероятностными переходами между ними, граф которой представлен на рис. 1.
Переходные вероятности представленной модели будут определяться параметрами дискретного канала, алгоритмом адаптации и значениями его внутренних параметров. Определение данных вероятностей для конкретного алгоритма рассматривается далее.
После определения переходных вероятностей проводится вычисление финальных вероятностей и производительности системы в целом.
Рисунок 1. Граф состояний адаптивной системы при работе по дискретному каналу с двумя состояниями
Для определения соотношений переходных вероятностей обобщенной модели, и модели исходного дискретного канала рассмотрим рис. 2.
Рисунок 2. Логические взаимосвязи моделей.
Очевидно, что состояния обобщенной модели 
соответствуют первому состоянию дискретного канала. Процесс смены физического состояния канала 
характеризуется с одной стороны переходной вероятностью 
, а с другой вероятностями 
и 
. Процесс сохранения состояния 
также характеризуется с одной стороны вероятностью 
, а с другой вероятностями 
и 
.
Представленная на рис. 1 марковская цепь может быть описана следующей матрицей переходных вероятностей
(2)
Далее выводятся выражения для финальных вероятностей системы, описываемой матрицей (2). Учитывая, что шагом системы является блок, длина которого равна или 
или 
, перед оценкой производительности системы необходимо привести шаг к единичному элементу. Для этого необходимо провести следующие преобразования
, 
,
, 
. (3)
где 
– финальные вероятности, приведенные к длине блока, а 
– финальные вероятности, приведенные к единичному элементу.
Производительность анализируемой адаптивной системы можно найти, используя следующее выражение
. (4)
Далее предложенная обобщенная методика используется для анализа адаптивного алгоритма со скользящим окном наблюдения.
В соответствии с данным алгоритмом уменьшение длины блока происходит, если количество пораженных блоков в окне наблюдения достигает 
. При этом наряду с текущим блоком учитываются результаты приема (N-1) предыдущих блоков. Можно выделить два режима: переходный и установившийся. Переходный режим длится с момента обнуления счетчиков до приема первых N блоков. В этом режиме возможно только увеличение числа пораженных блоков и при достижении 
сразу происходит уменьшение длины. После приема N блоков система переходит в установившийся режим, в котором при получении каждого следующего блока результат приема самого старого блока отбрасывается. Таким образом, реализуется скользящее окно размером в N блоков. В этом режиме возможно как увеличение, так и уменьшение числа пораженных блоков в окне наблюдения.
Аналогичным образом принимается решение и на увеличение длины передаваемых блоков, при этом анализируется число правильно принимаемых блоков в окне наблюдения, и в случае равенства этого числа 
система увеличивает длину блока.
Исходными данными для анализа алгоритма являются:
- Матрица переходных вероятностей дискретного канала P;
- Вероятности ошибки Pош в различных состояниях канала;
- Алгоритм изменения длин блоков и его параметры.
Переходные вероятности обобщенной модели адаптивной системы можно определить через средние длины состояний. В начале рассматривается определение длины промежуточного состояния 
, в котором система распознает новое состояние канала и принимает решение уменьшить длину блока. Поведение системы в этом промежуточном состоянии можно описать марковской цепью с поглощающими состояниями. Выберем в качестве состояний системы число пораженных блоков в окне наблюдения 
. Тогда количество возможных состояний системы будет 
. При достижении последнего состояния 
система переходит из 
в 
с изменением длины блока и обнулением счетчиков, поэтому состояние 
является поглощающим. С учетом сказанного, поведение алгоритма СОН в состоянии 
при установившемся режиме, может быть представлено графом (рис. 3).
Рисунок 3. Граф работы алгоритма СОН в установившемся режиме
Матрица переходных вероятностей для данного графа имеет вид
(5)
Определим переходные вероятности системы. При нулевом состоянии 
на каждом шаге возможны два исхода: сохранение этого состояния с вероятностью 
или переход в состояние 
при получении пораженного блока 
.
Для всех промежуточных невозвратных состояний существует три исхода:
– сохранение состояния 
;
– переход в состояние с большим номером 
;
– переход в состояние с меньшим номером 
.
Увеличение показания счетчика возможно в случае, когда следующий принятый блок оказывается пораженным, а отбрасываемый – безошибочным. При независимых ошибках поражение каждого блока происходит с вероятностью 
. Вероятность отбрасывания безошибочного блока или блока с ошибкой зависит от соотношения таких блоков в окне наблюдения. Чем больше среди N блоков ошибочных, тем выше вероятность отбрасывания такового. Таким образом, вероятность отбрасывания пораженного блока равна 
, а безошибочного –
. Значит, для вероятности перехода в состояние с большим номером имеем
.
Уменьшение номера состояния возможно, если следующий блок безошибочный, а отбрасываемый содержит ошибки. Вероятность такого события 
.
Сохранить состояние можно двумя способами:
1 – получить и отбросить пораженный блок;
2 – получить и отбросить безошибочные блоки.
В таком случае соответствующая переходная вероятность запишется следующим образом: 
.
Рассмотренный выше граф описывает работу системы при нахождении канала в состоянии с вероятностью поражения блока, равной Pe, и установившемся режиме.
Зная матрицу (5), можно определить фундаментальную матрицу 
. Как известно, элементы фундаментальной матрицы имеют смысл среднего числа шагов, проведённых системой в данном невозвратном состоянии (которому соответствует столбец) при старте из состояния, соответствующего номеру строки. Для определения среднего числа шагов до попадания в поглощающее состояние при старте из состояния 
необходимо просуммировать элементы i-ой строки фундаментальной матрицы
. (6)
В нашем случае начальным может быть любое состояние за исключением 
. Вероятности начальных состояний определяются числом пораженных блоков за 
последних шагов в состоянии 
. Таким образом, вероятность того, что начальным будет i-ое состояние, можно оценить выражением
(7)
С учетом вероятностей начальных состояний для установившегося режима получим 
. (8)
Рисунок 4. Граф работы алгоритма СОН в переходном режиме
Помимо установившегося возможен переходный режим, когда критерий выполняется до того, как система сделает N шагов с момента обнуления счетчика. В этом режиме блоки не отбрасываются, а значит, переходы в состояния с меньшим номером невозможны. Граф работы системы в переходном режиме показан на рис. 4.
Такая ситуация будет иметь место, если за первые N шагов число пораженных блоков достигнет. Вероятность такого события 
. Средняя длина промежуточного состояния при переходном режиме определится выражением 
. Тогда общее выражение для определения средней длины промежуточного состояния Lb при отсутствии ограничения на время нахождения системы в состоянии S2 примет вид:
. (9)
С учетом конечности средней длины состояния канала S2 средняя длина промежуточного состояния определится выражением:
. (10)
Аналогичным образом можно получить выражения для средних длин оставшихся состояний, после чего вычислить переходные и финальные вероятности в соответствии с обобщенной моделью.
Поверхность производительности системы, использующей алгоритм со скользящим окном наблюдения (СОН), приведена на рис. 5.
Рисунок 5. Производительность адаптивного алгоритма СОН
Здесь же показаны плоскости производительности идеальной системы и максимальной производительности системы с фиксированной длиной для данного дискретного канала. Превышение поверхностью производительности плоскости производительности стационарной системы наглядно показывает область значений параметров алгоритма с СОН, при которых возможен выигрыш.
Аналогично разработаны аналитические модели для адаптивных алгоритмов:
- с оценкой успешных и ошибочных приемов (ОУОП);
- с фиксированным периодом наблюдения (ФПН);
- с переменным периодом наблюдения (ППН);
- со скользящим окном наблюдения переменной длины (СОН-ПД).
Проведенный анализ показал, что:
- наибольшую производительность среди рассматриваемых алгоритмов обеспечивает алгоритм СОН-ПД;
- алгоритм ОУОП является наиболее простым из рассмотренных с точки зрения аппаратной реализации;
- алгоритм ФПН – с точки зрения аналитического описания.
В третьей главе предлагается обобщенная методика оценки производительности системы передачи данных, использующей различные адаптивные алгоритмы при работе по дискретному каналу с тремя состояниями.
Состояния канала S1, S2 и S3 характеризуются соответствующей вероятностью ошибки по единичным элементам pош1, pош2 и pош3. Смена состояний описывается марковской цепью с тремя состояниями и соответствующими переходными вероятностями (рис. 6).
Рисунок 6. Модель дискретного канала с тремя состояниями
Рассмотрим основные состояния, возникающие в процессе работы адаптивной системы по данному дискретному каналу с тремя состояниями.
Пусть в некоторый момент времени дискретный канал находится в состоянии S1, а система использует для передачи блоки с оптимальной для данного случая длиной n1. Обозначим данное производное состояние 
.
При смене состояния канала 
, системе требуется некоторое время на определение нового состояния канала. В течение этого времени будет сохраняться прежняя длина блока. Таким образом, возникает производное промежуточное состояние 
.
После определения нового состояния система изменит длину блока 
и перейдет в состояние 
.
Если канал меняет свое состояние на S3 до того, как система изменит длину блока, то возникает производное промежуточное состояние 
.
В состоянии Sh после определения нового состояния канала система изменит длину блока 
и перейдет в производное промежуточное состояние 
.
Когда система находится в состоянии Sс, канал может перейти как в состояние 
, так и в 
, результатом чего являются переходы в состояния 
и 
соответственно.
В Sg и Sd система за некоторое время определяет свое новое состояние и уменьшает (для состояния Sg) или увеличивает (для состояния Sd) длину блока, соответственно происходят переходы в состояния 
и 
.
При работе системы в состоянии Se выполняются аналогичные процедуры и возникают производные промежуточные состояния 
и 
.
Таким образом, работа системы может быть описана девятью состояниями и тридцатью тремя вероятностными переходами между ними (рис. 7).
Рисунок 7. Граф состояний адаптивной системы
Полученная марковская цепь может быть описана следующей матрицей переходных вероятностей
. (11)
Аналогично обобщенной модели для дискретного канала с двумя состояниями, состояния обобщенной модели 
, 
и 
соответствуют первому состоянию дискретного канала (см. рис. 8). Процесс смены физического состояния канала 
однозначно характеризуется переходной вероятностью 
. В обобщенной модели переходу 
соответствуют вероятности 
, 
и 
. Поэтому данные вероятности будут однозначно определяться вероятностью 
и длинами блоков.
Процесс сохранения состояния 
также характеризуется с одной стороны вероятностью 
, а с другой – вероятностями 
, 
и 
. В главе получены соотношения для этих вероятностей, однако значения данных переходных вероятностей будут определяться конкретным алгоритмом адаптации и его параметрами.
Рисунок 8. Логические взаимосвязи моделей для состояния S1
Состояния Sb, Sc и Sf обобщенной модели соответствуют второму состоянию дискретного канала (см. рис. 9). Процессы смены физических состояний канала 
и 
характеризуются с одной стороны переходными вероятностями p21 и p23, а с другой – вероятностями Gba, Gcg, Gfk и Gbh, Gcd, Gfe.
Рисунок 9. Логические взаимосвязи моделей для состояния S2
Сохранение состояния S2 также характеризуется с одной стороны вероятностью p22, а с другой – вероятностями 
, 
и 
.
Финальные вероятности вычислялись из матрицы переходных вероятностей (11).
Следует помнить, что шагом системы, представленной на рис. 7, является блок, длина которого равна или n1 или n2 или n3, поэтому перед оценкой производительности системы необходимо привести шаг к единичному элементу. Это можно сделать следующим образом:
,
,
,
,
,
,
,
,
,
, (12)
где 
– вероятности, приведенные к длине блока, а 
– вероятности, приведенные к единичному элементу.
Производительность анализируемой адаптивной системы определится выражением.
. (13)
Далее обобщенная методика применяется для анализа адаптивного алгоритма с оценкой успешных и ошибочных приемов.
В соответствии с данным алгоритмом решения в системе принимаются по результатам анализа ошибочно или правильно принятых подряд блоков. Если система находится в состоянии канала S1 (с наименьшей вероятностью ошибки), то передача ведется блоками наибольшей длины n1.
Критерии изменения длины блока: если поражено подряд блоков, то система уменьшает длину блока; если правильно принято подряд блоков, то система увеличивает длину блока.
Для определения переходных вероятностей обобщённой модели первоначально рассчитаем средние длины состояний. В состояниях Sa, Sb, Sh – возможно только уменьшение, а в состояниях Se, Sf, Sk – только увеличение длин блока. В состояниях Sс, Sg, Sd возможно как увеличение, так и уменьшение длины блока. Рассмотрим одно из таких состояний и определим его среднюю длину.
Рисунок 10. Граф поведения системы в состоянии Sc при >1 и >1
Поведение системы в переходном состоянии Sc удобнее всего представить марковской цепью с двумя поглощающими состояниями. В зависимости от значений параметров алгоритма ОУОП возможны 4 варианта графов. Наиболее общим является граф для значений параметров >1 и > 1 (рис. 10).
В качестве состояний системы выбрано количество принятых подряд правильных (j ) или пораженных (i) блоков.
Поглощающие состояния и соответствуют выполнению критериев изменения длины блока.
Задачу определения средней длины состояния Sc можно свести к определению среднего числа шагов, за которое система достигнет любого из двух поглощающих состояний, при старте из нулевого состояния. Для решения поставленной задачи определим фундаментальную матрицу 
. Далее определим вероятности попадания в поглощающие состояния, для чего вычислим следующую матрицу: 
. (14)
Элементы первого столбца матрицы имеют смысл вероятности попадания в поглощающее состояние при старте из состояния, соответствующего номеру строки. Аналогично, элементы второго столбца имеют смысл вероятности попадания в поглощающее состояние.
Таким образом, вероятности попадания из нулевого состояния в поглощающие состояния и равны соответственно:
, 
. (15)
Полученная оценка справедлива для случая, когда длительность состояния канала S2 значительно превышает величину Lc. Очевидно, что длительность переходного состояния Sc не может превышать длительности состояния дискретного канала S2. Таким образом, средняя длина переходного состояния оказывается ограниченной и может быть определена выражением
. (16)
Аналогично вычисляются длины состояний Dd и Dg.
После нахождения средних длин состояний переходные и финальные вероятности вычисляются в соответствии с обобщенной моделью.
Рисунок 11. Поверхность производительности адаптивного алгоритма
На рис. 11 приведена поверхность производительности адаптивного алгоритма с оценкой успешных и ошибочных приемов, полученная по предложенной методике, а так же поверхности стационарной и идеальной системы.
В четвертой главе представлены имитационные модели для пяти алгоритмов адаптации при работе по дискретному каналу с двумя и тремя состояниями.
Целью имитационного моделирования процесса являлась проверка аналитических моделей адаптивных алгоритмов.
Для реализации моделирования были разработаны программа имитации работы системы на языках C++ и Pascal и анализатор результатов моделирования в среде MathCAD 11.0.
Относительное отличие производительностей, полученных методами имитационного моделирования и аналитического расчета по предложенным выражениям, не превышало 2 %. Данный факт иллюстрирует относительно высокую точность расчетов по предложенной методике и позволяет рекомендовать её для инженерного применения.
В заключении перечислены основные результаты, полученные в диссертационной работе, и даны рекомендации по использованию предложенных методик.
- Разработаны обобщенные методики анализа адаптивной системы с изменением длины блока, позволяющие анализировать производительность различных алгоритмов при работе по дискретному каналу с двумя и тремя состояниями. Данная методика позволят одновременно учитывать время, затрачиваемое на определение состояния дискретного канала; ошибки возможные при оценке состояния; исходные вероятностные характеристики дискретного канала, отражающие процесс изменения его состояний, а также значительно упрощать модели и сокращать время моделирования.
- Разработаны аналитические модели пяти адаптивных алгоритмов, позволяющие определить оптимальные значения параметров алгоритмов, при которых достигается максимальная производительность системы в условиях заданного дискретного канала с двумя и тремя состояниями.
- Разработаны имитационные модели пяти адаптивных алгоритмов, позволяющие оценить производительность системы в зависимости от параметров алгоритмов и параметров дискретного канала. Сравнение теоретических результатов, полученных по предложенным аналитическим моделям, с результатами имитационного моделирования показали достаточную для инженерных расчетов точность вычислений, составляющую единицы процентов.
В приложениях к диссертационной работе представлены тексты программ, реализующих предлагаемые методики и алгоритмы.
Публикации по основным результатам диссертации:
- Konovalov P.A., Makarov D.O., Melentyev O.G. Development of Estimation Techniques of Data Transmission Systems // Siberian Russian Workshops and Tutorials on Electron Devices and Materials EDM 2004. – pp. 95-97.
- Konovalov P.A., Melentyev O. G. Development of Imitating Model of Adaptive Data Transmission Systems // Siberian Russian Workshops and Tutorials on Electron Devices and Materials EDM 2005. – pp. 192-194.
- Коновалов П.А., Мелентьев О.Г. Анализ алгоритмов адаптации по результатам оценки качества приема блоков. ГОУ ВПО Сиб. гос. Ун-т телекоммуникаций и информатики. – Новосибирск, 2005. – 56 с., ил. – Библиогр.: 12 назв. – Рус. – Деп. в ВИНИТИ 10.10.05 № 1291-В2005.
- Коновалов П.А. Моделирование адаптивного алгоритма передачи данных со скользящим окном наблюдения переменной длины // Всероссийская научная конференция студентов, аспирантов и молодых ученых «Наука. Технологии. Инновации» (НТИ-2005). – Новосибирск, 2005. – С. 34 – 35.
- Коновалов П.А., Мелентьев О.Г. Моделирование адаптивного алгоритма передачи данных со скользящим окном наблюдения // Труды учебных заведений связи / СПбГУТ. СПб, 2005. № 173. – С. 39 – 46.
- Коновалов П.А., Мелентьев О.Г. Имитационная модель хоппинг-процесса // IV-Всероссийская научно-практическая конференция «Информационные Недра Кузбасса-2005». – Кемерово, 2005. – С.
- Коновалов П.А., Левыкин К.Н. Вычисление модифицированных параметров дискретного канала, описываемого моделью Гилберта, после применения операции сверточного перемежения // Всероссийская научно-техническая конференция «Измерение, Автоматизация и Моделирование в Промышленности и Научных Исследованиях». – Бийск, 2005. – С. 70 – 73.
- Будылдина Н.В., Коновалов П.А. Разработка программного обеспечения для оптимизации мультисервисных сетей // Всероссийская научно-техническая конференция «Измерение, Автоматизация и Моделирование в Промышленности и Научных Исследованиях». – Бийск, 2005. – С. 68 – 70.
- Коновалов П.А. Моделирование адаптивного алгоритма передачи данных с переменным периодом наблюдения // Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций». – Новосибирск, 2006. – С. 60 – 62.
- Коновалов П.А., Мелентьев О.Г. Анализ производительности алгоритма адаптации при работе по дискретному каналу с тремя состояниями - ГОУ ВПО Сиб. гос. Ун-т телекоммуникаций и информатики. – Новосибирск, 2006. – 21 с. – Библиогр.: 3 назв. – Рус. – Деп. в ВИНИТИ 03.05.06 № 589-В2006
- Коновалов П.А., Крашенинников П.В. Имитационная модель адаптивного алгоритма со скользящим окном наблюдения при работе по дискретному каналу с 3-мя состояниями // Материалы двенадцатой международной научно-технической конференции «Перспективы развития современных средств и систем телекоммуникаций». – Екатеринбург, 2006. – С.
Лицензия ЛР_020475, январь 1998 г. Подписано в печать ________
Формат бумаги 62x84 1/16, отпечатано на ризографе, шрифт № 10,
Изд. л. 1, заказ № ____, тираж – 100 экз, СибГУТИ
630102, г. Новосибирск, ул. Кирова, 86.
