Содержание к диссертации
Введение
1. Оптимизация адаптивных систем передачи данных 9
1.1 Многоуровневый подход и декомпозиция при моделировании систем передачи данных 10
1.2. Системы с корректировкой внутренних параметров 14
1.3. Адаптивные алгоритмы оценки состояния дискретного канала по результатам анализа качества приема блока 16
1.4. Производительность моделируемой системы 17
1.5. Выбор дискретного шага моделируемой системы 23
1.6. Выводы и постановка задач для исследования 27
2. Анализ адаптивных систем с изменением длины блока при работе по дискретному каналу с двумя состояниями 30
2.1. Обобщенная методика анализа адаптивных систем с изменением длины блока при работе по дискретному каналу с двумя состояниями 30
2.2. Адаптивный алгоритм с оценкой успешных и ошибочных приемов 37
2.3. Адаптивный алгоритм со скользящим окном наблюдения 42
2.4. Сравнение производительностей адаптивных алгоритмов 50
2.5. Основные результаты, полученные в главе 50
3. Анализ адаптивных систем с изменением длины блока при работе по дискретному каналу с тремя состояниями 52
3.1. Обобщенная методика анализа адаптивных систем с изменением длины блока при работе по дискретному каналу с тремя состояниями 52
3.2. Адаптивный алгоритм с оценкой успешных и ошибочных приемов 61
3.3. Основные результаты, полученные в главе 67
4. Имитационное моделирование работы адаптивной системы передачи данных при работе по дискретным каналам с двумя и тремя состояниями 68
4.1. Имитационные модели работы адаптивной системы передачи данных по дискретному каналу с двумя состояниями 68
4.1.1. Определение параметров модели по результатам имитационного моделирования 69
4.1.2. Имитационная модель алгоритма ОУОП 71
4.1.3. Имитационная модель алгоритма СОН 83
4.2. Имитационные модели работы адаптивной системы передачи данных по каналу с тремя состояниями 96
4.2.1. Имитационная модель алгоритма ОУОП 98
4.4. Основные результаты, полученные в главе 110
Заключение 111
Литература
- Многоуровневый подход и декомпозиция при моделировании систем передачи данных
- Обобщенная методика анализа адаптивных систем с изменением длины блока при работе по дискретному каналу с двумя состояниями
- Обобщенная методика анализа адаптивных систем с изменением длины блока при работе по дискретному каналу с тремя состояниями
- Имитационные модели работы адаптивной системы передачи данных по дискретному каналу с двумя состояниями
Введение к работе
Актуальность работы: Обострение конкурентной борьбы операторов связи требует введения новых услуг и повышения качества обслуживания. Это обуславливает необходимость обеспечения гарантированных показателей задержки, верности и скорости передачи при минимизации затрат. Но реальные каналы имеют нестационарный характер особенно в беспроводных системах передачи данных, таких как Wi-Fi, WiMAX, MBWA. Наилучших качественных показателей в таких условиях позволяют достичь адаптивные системы передачи.
Вопросами анализа адаптивных систем занимались М.Н. Арипов, Э.Л. Блох, Н.Н. Буга, Л.П. Коричнев, Л.А. Растригин, Ю.Г. Ростовцев, Б.Я. Советов, А.И. Фалько, В.А. Шапцев, В.П. Шувалов, М. Zorzi и другие.
Адаптивная система предполагает контроль условий передачи и адекватную реакцию на их изменения. Контроль условий передачи может осуществляться на различных уровнях системы и по различным параметрам. На канальном уровне наименее затратной является оценка состояния канала по качеству приема блока. Данная оценка проводится для каждого принятого блока, а её результаты являются естественным источником информации о состоянии канала при использовании систем с решающей обратной связью с адресным переспросом (РОС-АП).
Важным моментом является выбор алгоритма, использующего информацию о качестве приема блока и на основе этого принимающего решение об изменении состояния канала. Время, затрачиваемое при использовании данных алгоритмов, и ошибки при определении состояния канала во многом будут определять производительность системы в целом.
В работах A. Annamalai, V. Bhargava, М. Rice и S. Cho описан ряд алгоритмов использования сигналов переспроса. Предложены отдельные методики оценки эффективности алгоритмов. Однако всё ещё актуальным остается вопрос разработки универсальных методик, позволяющих анализировать и сравнивать различные алгоритмы с приемлемой точностью и при сравни-
тельно небольших затратах вычислительных ресурсов.
Цель работы: Разработка моделей адаптивных систем и методик оценки и оптимизации их вероятностно-временных характеристик, обеспечивающих передачу данных по дискретному каналу с двумя и тремя состояниями.
Методы исследования: В диссертации представлены результаты исследований, полученные с помощью аппарата теории вероятностей, теории марковских цепей, имитационного и математического моделирования.
Научная новизна:
1. Разработаны обобщенные методики анализа и оптимизации адаптив
ных систем передачи данных с изменением длины блока, учитывающие од
новременно:
время, затрачиваемое на определение состояния дискретного канала;
ошибки в определении состояния канала;
исходные вероятностные характеристики дискретного канала, отражающие процесс изменения его состояний.
Методики позволяют анализировать производительность различных алгоритмов адаптации при работе по дискретному каналу с двумя и тремя состояниями. В отличие от известных, в данных методиках использовано масштабирование дискретного шага системы, описываемой марковской цепью, позволяющее упростить модели и сократить время моделирования.
Предложен алгоритм адаптации со скользящим окном наблюдения переменной длины (СОН-ПД), позволяющий получить большую производительность относительно известных.
Разработаны аналитические модели алгоритмов адаптации с оценкой успешных и ошибочных приемов (ОУОП), со скользящим окном наблюдения (СОН), со скользящим окном наблюдения переменной длины (СОН-ПД), с фиксированным периодом наблюдения (ФПН) и с переменным периодом наблюдения (ППН), позволяющие получать оценки производительности адаптивной системы в зависимости от параметров алгоритма и параметров дис-
кретного канала с двумя и тремя состояниями.
4. Разработаны имитационные модели алгоритмов адаптации ОУОП, СОН, СОН-ПД, ФПН и ППН для дискретного канала с двумя и тремя состояниями.
Практическая ценность работы и внедрение её результатов: Разработаны методики расчета и оптимизации вероятностно-временных характеристик (ВВХ) систем передачи данных, позволяющие проектировать эффективно работающие системы передачи данных.
Апробация работы. Основные положения работы докладывались на следующих семинарах и конференциях:
Международном семинаре «Электронные приборы и материалы», EDM. - Эрлагол, 2004, 2005.
IV-Всероссийская научно-практическая конференция «Информационные Недра Кузбасса-2005». - Кемерово, 2005.
Всероссийская научно-техническая конференция «Измерение, Автоматизация и Моделирование в Промышленности и Научных Исследованиях». - Бийск, 2005.
Всероссийской научной конференции «Наука. Технологии. Инновации» (НТИ-2005). - Новосибирск, 2005.
Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций». - Новосибирск, 2006.
Международная научно-техническая конференция «Перспективы развития современных средств и систем телекоммуникаций». - Екатеринбург, 2006.
Публикации. По теме диссертации опубликовано 11 работ. В их числе: 1 статья, 2 депонированных рукописи и 8 докладов.
Структура и объем диссертации: Диссертационная работа состоит из введения, четырех глав и шести приложений. Содержит 175 страниц, 1 таблицу, 60 рисунков. Список литературы состоит из 62 наименований.
Основные результаты, выносимые на защиту:
Обобщенные методики анализа и оптимизации адаптивной системы с изменением длины блока, позволяющая анализировать производительность различных алгоритмов адаптации при работе по дискретному каналу с двумя и тремя состояниями.
Методика масштабирования дискретного шага системы, описываемой марковской цепью, позволяющая упростить модели адаптивных алгоритмов и сократить время моделирования.
Алгоритм адаптации со скользящим окном наблюдения переменной длины (СОН-ПД).
Аналитические модели алгоритмов адаптации ОУОП, СОН, СОН-ПД, ФПН и ППН, позволяющие получать оценки производительности адаптивной системы в зависимости от параметров данного алгоритма и параметров дискретного канала с двумя состояниями.
Аналитическая модель алгоритма адаптации ОУОП, позволяющая получать оценку производительности адаптивной системы в зависимости от параметров алгоритма и параметров дискретного канала с тремя состояниями.
Имитационные модели алгоритмов адаптации ОУОП, СОН, СОН-ПД, ФПН и ППН для дискретного канала с двумя и тремя состояниями.
Многоуровневый подход и декомпозиция при моделировании систем передачи данных
Анализ систем и сетей передачи дискретных сообщений является достаточно сложной задачей. Для решения сложных задач часто используют многоуровневый подход и декомпозицию [21]. Декомпозиция предполагает: - разбиение сложной задачи (системы) на несколько простых задач (модулей); - четкое определение функций каждого модуля, решающего отдельную задачу; - определение правил взаимодействия между модулями.
При многоуровневом подходе: - все множество модулей разбивается на уровни (при этом функции всех уровней четко определены); - уровни образуют иерархию (т.е. существуют верхние и нижние); - для решения своих задач каждый уровень обращается с запросами только к модулям непосредственно примыкающего нижнего уровня; - результаты работы модулей уровня могут быть переданы только соседнему, вышележащему.
Рассмотренный подход реализован в модели взаимодействия открытых систем (Open System Interconnection reference model, OSI). В соответствии с данной моделью все процессы, реализуемые открытой системой, разбиты на семь взаимно подчиненных уровней. Таким образом, каждый узел сети представляет собой иерархическую систему. Процедура взаимодействия этих узлов может быть описана в виде набора правил взаимодействия каждой пары соответствующих (равноправных) уровней участвующих сторон. Формализованные правила, определяющие последовательность и формат сообщений, которыми обмениваются сетевые компоненты, лежащие на одном уровне, но в разных узлах, называется протоколом. Правила взаимодействия уровней находящихся в одном узле принято называть интерфейсами. Таким образом, средства каждого уровня должны отрабатывать, во-первых, свой собствен ный протокол, а во-вторых, интерфейсы с соседними уровнями.
Помимо упрощения решения задач анализа сложных систем, такой подход позволяет достичь независимости протоколов разных уровней, что в свою очередь дает возможность параллельного проведения работ на разных уровнях.
Так как для решения своих задач каждый уровень использует возможности нижних уровней, то характеристики любого верхнего уровня могут быть выражены через параметры нижнего.
В данной работе рассматриваются вопросы анализа систем передачи данных, ограниченные двумя нижними уровнями модели OSI. Основой любой системы передачи данных является канал передачи данных. Структурная схема канала представлена на рис. 1.1.
Перечислим блоки, входящие в структурную схему. КК, (ДК) - кодер (декодер) канала, обеспечивает корректирующее кодирование, с целью защиты от ошибок. П, (ДП) - перемежитель (деперемежитель), обеспечивает перемежение с целью декорреляции ошибок. УПС - устройство преобразования сигнала обеспечивает согласование характеристик внутрисистемных сигналов с параметрами непрерывного канала связи. В общем случае могут использоваться различные виды модуля ции и линейного кодирования. ДМ - демодулятор. Р - регистрирующее устройство, принимает решение о значащей позиции на текущем единичном интервале. УК - средства управления каналом.
Функции, выполняемые блоками структурной схемы и их соответствие физическому и канальному уровням модели OSI подробно рассмотрены в [4Д6].
Канал передачи данных так же является иерархической системой. Нижний уровень данной системы представлен непрерывным каналом связи (НКС). Далее следуют канал постоянного тока, дискретный канал и преобразованный дискретный канал. Система передачи дискретных сообщений (СПДС), в свою очередь, может иметь несколько прямых и обратных каналов. Каждый из указанных каналов имеет свои параметры и характеристики, но при этом характеристики каждого канала более высокого уровня и СПДС в целом могут быть выражены через параметры канала нижнего уровня.
При прохождении информационного сигнала по непрерывному каналу связи он подвергается воздействию многочисленных возмущающих факторов, изменяющих его параметры. Данные воздействия могут носить как случайный, так и регулярный характер. Искажения регулярного характера, могут быть как линейными, так и нелинейными. Линейные искажения вызваны отклонениями амплитудно-частотных (АЧХ) и фазочастотных (ФЧХ) характеристик от идеальных форм. Нелинейные искажения обусловлены нелинейностью характеристик усилительных элементов и преобразователей. При рассмотрении вопросов передачи дискретных сообщений регулярными нелинейными искажениями, как правило, пренебрегают, поскольку действующие нормы на собственные нелинейности канала и на суммарную мощность группового сигнала практически исключают их из числа существенных факторов повышения неопределенности сигнала.
Обобщенная методика анализа адаптивных систем с изменением длины блока при работе по дискретному каналу с двумя состояниями
В соответствии с данным алгоритмом уменьшение длины блока происходит, если количество пораженных блоков достигает а. При этом наряду с # текущим блоком учитываются результаты приема (N-1) предыдущих блоков. Можно выделить два режима переходный и установившийся. Переходный « режим длится с момента обнуления счетчиков до приема первых N блоков. В этом режиме возможно только увеличение числа пораженных блоков и при достижении а, сразу происходит уменьшение длины. После приема N блоков система переходит в установившийся режим, в котором при получении каждого следующего блока результат приема самого старого блока отбрасывается. Таким образом, реализуется скользящее окно размером в N блоков. В этом режиме возможно как увеличение, так и уменьшение числа пораженных блоков в окне наблюдения. Аналогичным образом принимается решение и на увеличение длины передаваемых блоков. При этом анализируется число правильно принимаемых блоков в окне наблюдения, и при равенстве этого числа /? система увеличивает длину блока.
В соответствии с обобщенной моделью функционирования адаптивной системы оценим средние длины промежуточных состояний для алгоритма СОН. Сначала проведем рассуждения для состояния Sb, .возникающего при переходе дискретного канала из хорошего в плохое состояние.
Поведение системы в этом промежуточном состоянии так же можно описать марковской цепью. Выберем в качестве состояний системы число пораженных блоков в окне наблюдения /. Тогда количество возможных состояний системы будет (а +1). При достижении последнего состояния i = a, система переходит из Sb в Sc с изменением длины блока и обнулением счетчиков, поэтому состояние (а +1) является поглощающим. С учетом сказанного, поведение алгоритма СОН в состоянии Sb при установившемся режиме, может быть представлено графом (рис. 2.7).
Определим переходные вероятности системы. При нулевом состоянии (/ = 0) на каждом шаге возможны два исхода: сохранение этого состояния с вероятностью Р00 =1 - РеЬ или переход в состояние (/ = 1) при получении пора женного блока Р01 = Peb. Для всех промежуточных невозвратных состояний есть три исхода: - сохранение состояния Ри; - переход в состояние с большим номером Pt м; - переход в состояние с меньшим номером Р, ,.,.
Увеличение счетчика возможно в случае, когда следующий принятый блок оказывается пораженным, а отбрасываемый - безошибочным. При независимых ошибках поражение каждого блока происходит с вероятностью Ре.
Вероятность отбрасывания безошибочного блока или блока с ошибкой зави сит от соотношения таких блоков в окне наблюдения. Чем больше среди N блоков ошибочных, тем выше вероятность отбрасывания такового. Т.о. веро ятность отбрасывания пораженного блока равна —, а безошибочного . Значит, для вероятности перехода в состояние с большим номером можно за писать Р и, = Ре
Уменьшение. номера состояния возможно, если следующий блок безошибочный, а отбрасываемый содержит ошибки. Вероятность такого события Р., ,=—(1-/У). «..-і N Сохранить состояние можно двумя способами: 1 - получить и отбросить пораженный блок; 2 - получить и отбросить безошибочные блоки. В таком случае соответствующая переходная вероятность запишется следующим образом: Ри =—Ре+——(l-Pe).
Рассмотренный выше граф описывает работу системы при нахождении канала в состоянии с вероятностью поражения блока, равной Ре и установившемся режиме.
Зная матрицу (2.40) нетрудно найти среднее число шагов до попадания в поглощающее состояние при старте из любого невозвратного состояния, а значит и время до выполнения критерия смены длины блока. Решим данную задачу через фундаментальную матрицу N. Для получения среднего числа шагов до попадания в поглощающее состояние при старте из состояния (/), необходимо просуммировать элементы і-ой строки фундаментальной матрицы L«\=±Nix. (2.41)
В исключением (/ = а). Вероятности начальных состояний определяются числом пораженных блоков за N последних шагов в состоянии Sa. Т.о. вероятность того, что начальным будет i-oe состояние можно оценить выражениемнашем случае, с некоторой вероятностью, начальным может быть любое состояние за
Обобщенная методика анализа адаптивных систем с изменением длины блока при работе по дискретному каналу с тремя состояниями
Рассмотрим нестационарный дискретный канал с тремя состояниями S], 5 2 и 5j. Каждое состояние канала характеризуется соответствующей вероятностью ошибки по единичным элементам роші,р0ш2 -Рошз- Смена состояний описывается марковской цепью с тремя состояниями и соответствующими переходными вероятностями (см. рис. 3.1), которые записываются в виде матрицыРассмотрим работу систем передачи дискретных сообщений, использующих разные алгоритмы адаптации длины блока и оценим их производительность в условиях данного канала, с целью выбора наилучшего [56].
Рассмотрим состояния, возникающие в процессе работы адаптивной системы по дискретному каналу с тремя состояниями.
Пусть в некоторый момент времени дискретный канал находится в состоянии Sj, а система использует для передачи блоки с оптимальной для данного случая длиной щ. Обозначим данное производное состояние Sa - (iSp !). Через какое-то время дискретный канал может изменить свое состояние на»%, но системе требуется некоторое время на определение нового состояния канала. В течение этого времени будет сохраняться прежняя длина блока. Таким образом, возникает производное промежуточное состояние Sb r (S2, пх). После определения нового состояния система изменит длину блока и, -» п2 и перейдет в состояние Sc r (S2, п2). Если канал меняет свое состояние на »% до того, как система изменит длину блока, то возникает производное промежуточное состояние А - (&,, л,). В СОСТОЯНИИ Sh также после определения нового состояния система изменит длину блока «, - «2 и перейдет в производное промежуточное состояние Sd r±(S3,n2).
Когда система находится в состоянии Sc, канал может изменить свое состояние, как S2- Slf так и S2 - S3, результатом чего являются переходы в состояния Sg «-»(,, я2)и Sd r (S3,n2), соответственно. В Sg и Sd система за некоторое время определяет свое новое состояние и уменьшает (для состояния Sg), увеличивает (для состояния Sd) длину блока, происходят переходы в состояния Sa -» (S,, л,) и Se - (53, щ), соответственно. При работе системы в состояние Se происходят аналогичные процедуры и возникают производные промежуточные состояния Sf -» (S2, щ) и Sk -» (,, пъ).
В данном случае, работа системы описывается марковской цепью с девятью состояниями и тридцатью тремя вероятностными переходами между ними, граф которой представлен на рис. 3.2.
Назовем состояния Sa, SCVL Se — основными, а остальные - промежуточными. Физический смысл переходов между состояниями при работе по дискретному каналу с тремя состояниями аналогичен физическому смыслу переходов для канала с двумя состояниями.
Переходные вероятности представленной модели так же будут зависеть от параметров исходного дискретного канала, алгоритма адаптации и значений его внутренних параметров. Нахождение данных вероятностей для алгоритма ОУОП будет рассмотрено далее. В рамках обобщенной модели опре делим основные соотношения между переходными вероятностями, а так же выражения для нахождения финальных вероятностей и производительности системы в целом.
Переходные вероятности, отражающие изменения физического состояния дискретного канала (пересекающие штриховую линию на рис. 3.2.) будут определяться только параметрами канала и могут быть определены независимо от параметров алгоритма.
Остальные вероятности будут зависеть как от параметров канала, так и от используемого алгоритма, поэтому в рамках обобщенной модели могут быть получены только соотношения между ними.
Аналогично обобщенной модели, рассмотренной в главе 2, состояния Sa, Sg и Sk соответствуют первому состоянию дискретного канала (см. рис.
Процесс смены физического состояния канала , - 52 однозначно характеризуется переходной вероятностью рп. В обобщенной модели, переходу S, - S2 соответствуют вероятности Gab, Ggc и G. Поэтому данные вероятности будут однозначно определяться вероятностью рп и длинами блоков.
Процесс сохранения состояния Sx также характеризуется с одной стороны вероятностью р115 а с другой вероятностями (Gaa,Gag), (Ggg,Gga,Ggk) и (Gkk,Gkg). Соотношения для этих вероятностей будут получены ниже. Значения этих переходных вероятностей будут определяться конкретным алгоритмом адаптации и его параметры.
Положим, что в некоторый момент времени система находится в состоянии Sa. Вероятность перехода в Sb будет определяться вероятностью смены состояния канала, поэтому для шага равного элементу можно записать 8аь - Рп - — Дискретный шаг системы в состоянии Sa равен длине блока л,. d\ Средняя длина первого состояния, выраженная в шагах щ равна ,(«,) = —. "і Следовательно, можно записать
Имитационные модели работы адаптивной системы передачи данных по дискретному каналу с двумя состояниями
В диссертационной работе рассмотрены вопросы адаптации системы передачи данных к дискретному каналу, описываемому марковской цепью с двумя и тремя состояниями.
Основные результаты, полученные в работе:
Для различных уровней системы передачи данных проанализированы параметры, контроль которых позволяет принимать решение об изменении состояний канала. Показано, что в зависимости от соотношений средней длины состояний канала и длины блока, могут быть использованы преобразования на разных уровнях канала, в частности, если длина состояний канала соизмерима или меньше длины блока, то целесообразно использовать операции изменяющие параметры дискретного канала - хоппинг и перемежение, в противном случае эффективным является применение алгоритмов, основанных на оценке качества приема блока.
Рассмотрены внутренние параметры системы, которые могут меняться в зависимости от условий передачи. На уровне дискретного канала и канала передачи данных можно изменять: длины передаваемых блоков, корректирующий код, глубину перемежения или длину слота хоппинга совместно с исправляющей способностью кода и т.д. Изменение большинства параметров системы на уровне дискретного канала и канала передачи данных можно учесть соответствующим изменением длин блоков и производительности системы в том или ином состоянии.
Рассмотрены известные адаптивные алгоритмы оценки состояния дискретного канала с изменением длины блока по результатам контроля качества приема.
Предложен адаптивный алгоритм со скользящим окном наблюдения переменной длины (СОН-ПД).
Проанализированы различные модели источников ошибок в дискретных каналах, использующихся в настоящее время для анализа ВВХ систем передачи данных [12-14,23,46-49]. Показано, что наиболее часто для построения моделей источников ошибок применяют марковские цепи с разным числом состояний.
Определены граничные значения производительности адаптивной системы передачи данных с изменением длины блока при работе по дискретному каналу с различным числом состояний.
Получена оценка относительной погрешности определения производительности и сложности моделей для канала с двумя, тремя и четырьмя состояниями, которая показала, что с увеличением числа состояний погрешность определения производительности убывает медленнее, чем возрастает сложность моделей, так при уменьшении числа учитываемых состояний канала с четырех до трех погрешность не превысила 2,9 %, а сложность модели уменьшилась в 3,4 раза; с четырех до трех - 6 %, а сложность - в 20 раз. Пропорционально сложности уменьшается и время вычисления оптимальных параметров, что является очень важным в адаптивных системах.
Предложена методика масштабирования дискретного шага моделируемой системы, позволяющая уменьшить сложность моделей.
Разработаны обобщенные методики анализа адаптивной системы с изменением длины блока, позволяющая анализировать производительность различных алгоритмов при работе по дискретному каналу с двумя и тремя состояниями. Данные методики одновременно учитывают время, затрачиваемое на определение состояния дискретного канала; ошибки возможные при оценке состояния и исходные вероятностные характеристики дискретного канала, отражающие процесс изменения его состояний. Кроме того, в отличие от известных, данные методики используют масштабирование дискретного шага моделируемой системы, что уменьшает время моделирования.
Разработаны аналитические модели пяти адаптивных алгоритмов, позволяющих получать оценки производительности адаптивной системы в зависимости от параметров алгоритмов и параметров дискретного канала.
Похожие диссертации на Исследование методов оптимизации систем передачи данных по результатам оценки качества канала
