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

Размещено на http://www.allbest.ru/

Автореферат

диссертации на соискание учёной степени

кандидата технических наук

ПРИМЕНЕНИЕ ХОППИНГА ДЛЯ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ИСПОЛЬЗОВАНИЯ ПУЧКА ДИСКРЕТНЫХ КАНАЛОВ

Шевнина Ирина Евгеньевна

Специальность 05.12.13 Системы, сети и устройства телекоммуникаций

Новосибирск

2011

Работа выполнена на кафедре передачи дискретных сообщений и метрологии Федерального государственного образовательного бюджетного учреждения высшего профессионального образования «Сибирский государственный университет телекоммуникаций и информатики».

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

профессор О.Г. Мелентьев

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

профессор В.И. Носов

кандидат технических наук

В.А. Шиянов

Ведущее предприятие - Институт вычислительной математики и математической геофизики СО РАН.

Защита состоится «28» октября 2011 г. в 10.00 часов на заседании диссертационного совета Д 219.005.01. при ФГОБУ ВПО «Сибирский государственный университет телекоммуникаций и информатики» по адресу:

630102, Новосибирск, ул. Кирова, 86.

С диссертацией можно ознакомиться в читальном зале библиотеки ФГОБУ ВПО «СибГУТИ».

Автореферат разослан «____» сентября 2011 г.

Учёный секретарь

диссертационного совета Д 219.005.01,

доктор технических наук, профессор ____________ Г.В. Мамчев

Общая характеристика работы

Актуальность работы. В настоящее время большое внимание уделяется проблеме обеспечения качества передачи информации. Одним из путей её решения является разработка методов, повышающих эффективность использования ресурсов имеющихся каналов. Традиционно для этих целей применяют адаптивные системы. Известны различные классы адаптивных систем, многие их которых широко используются в системах передачи. Вопросами анализа адаптивных систем занимались М.Н. Арипов, Э.Л. Блох, Н.Н. Буга, Л.Ф. Жигулин, Л.П. Коричнев, О.В. Попов, Л.А. Растригин, Ю.Г. Ростовцев, Б.Я. Советов, А.И. Фалько, В.А. Шапцев, В.П. Шувалов, M. Zorzi и другие.

Рост возможностей элементной базы позволил перейти к реализации концепции построения интеллектуальных систем связи, способных изменять свои внутренние параметры, адаптируясь не только к уже произошедшим изменениям условий передачи, но и предсказывать эти изменения, что сокращает время реакции. Основные постулаты концепции, получившей название «Когнитивного радио», были сформулированы J. Mitola III в 1999 году. Развитие данной идеологии получило продолжение в работах G. Q. Maguire Jr, B. A. Fette, Senhua Huang, Xin Liu, Zhi Ding.

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

Как показывает анализ работы систем, первичные абоненты не используют весь временной ресурс выделенных каналов: существуют периоды активности первичного абонента и паузы, которые могут использоваться для передачи менее приоритетного трафика вторичных абонентов. В этой связи для повышения эффективности использования канального ресурса была предложена концепция гибкого доступа (opportunistic access). Вопросам гибкого доступа посвящены работы: Xin Liu, Bhaskar Krishnamachari, Hua Liu R. Knopp, P. Humblet, Q. Zhao, L. Tong, A. Swami, S. Huang.

Q. Zhao, B. Krishnamachari, K. Liu рассматривали вопросы повышения эффективности использования пучка из двух каналов вторичными абонентами, применяя для управления гибким доступом циклический алгоритм смены каналов. Philip A. Chou, Z. Miao рассмотрели вопросы передачи MPEG-потоков, имеющих внутренний приоритет блоков, по пучку каналов, описываемых цепями Маркова.

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

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

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

Научная новизна:

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

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

3. Предложены три алгоритма построения приоритетного логического канала, основанные: 1 - на учёте параметров модели Гилберта, описывающей доступность слотов физических каналов пучка; 2 - на средней статистике доступности слотов физических каналов; 3 - на анализе текущей доступности слотов пучка каналов. Предложенные алгоритмы управления нерегулярным хоппингом позволяют увеличить до 50 % вероятность доступности слотов приоритетного логического канала (ПЛК) по сравнению с лучшим физическим каналом пучка и обеспечить уменьшение потерь доступных слотов пучка для передачи неприоритетного трафика по сравнению с параллельным использованием физических каналов в ПЛК, в предположении, что доступность слотов физических каналов пучка описывается марковской цепью.

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

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

Результаты диссертационной работы использованы при разработке системных решений в ЗАО «Национальный институт радио и инфокоммуникационных технологий» и используются в учебном процессе в Сибирском государственном университете телекоммуникаций и информатики на кафедре передачи дискретных сообщений и метрологии и подтверждены актами внедрения.

Апробация работы. Основные положения работы докладывались на следующих семинарах и конференциях:

1. Международном семинаре «Электронные приборы и материалы», EDM. - Эрлагол, 2008.

2. X международной конференции «Проблемы функционирования информационных сетей». - Новосибирск, 2008.

3. XXV международной конференции Российской академии естественных наук (РАЕН) «Мобильный бизнес: перспективы развития и проблемы реализации систем мобильной связи в России и за рубежом». - Ньян-Чанг, 2009.

4. Российской научно-технической конференции «Информатика и проблемы телекоммуникаций». - Новосибирск, 2008, 2009, 2011.

Публикации. По теме диссертации опубликовано 11 работ. В их числе: 3 статьи - в научных периодических журналах (из них 2 - в журналах, рекомендованных ВАК), 8 докладов - в материалах научных конференций и семинаров.

Структура и объём диссертации. Диссертационная работа состоит из введения, четырёх глав и трёх приложений. Содержит 133 страницы, 2 таблицы, 86 рисунков. Список литературы состоит из 73 наименований.

Основные результаты, выносимые на защиту:

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

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

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

4. Математические выражения для вычисления вероятностей ошибок заданной кратности при параллельной передаче по нескольким дискретным каналам, описываемым простой марковской цепью.

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

6. Алгоритмы управления нерегулярным хоппингом.

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

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

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

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

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

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

Рис. 1 - Граф модели Гилберта

Изменение состояний модели определяется матрицей переходных вероятностей

. (1)

хоппинг пучок дискретный канал

Дискретным шагом системы является блок (слот). Смысл переходной вероятности - вероятность перехода системы при передаче следующего блока в состояние y, если при передаче текущего блока она находилась в состоянии x.

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

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

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

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

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

2. Разработать и классифицировать методы построения логических каналов на базе пучка с использованием различных видов хоппинга.

3. Разработать методики построения логических каналов с заданными параметрами на базе имеющегося пучка каналов при использовании различных видов регулярного хоппинга. Построение логического канала в данном случае сводится к определению схемы последовательно-параллельного выделения слотов исходных каналов пучка.

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

Если для организации приоритетного логического канала параллельно использовать все каналы пучка, то вероятность недоступности слотов ПЛК в этом случае будет минимальной, но коэффициент потерь доступных слотов за счёт дублирования блоков в нескольких слотах - максимальный.

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

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

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

Задача минимизации потерь блоков из-за превышения числа допустимых переспросов также может быть решена путём прогноза доступности слотов в каналах пучка и предоставления слотов в лучших по прогнозам каналах блокам с максимальным числом неудачных попыток.

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

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

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

Доступность слотов исходных каналов пучка описывалась моделью Гилберта с переходными вероятностями: Pgg1=0.95, Pbb1=0.9; Pgg2=0.9, Pbb2=0.9 и вероятностью недоступности слота в плохом состоянии p=0.5.

Выигрыш в разах по коэффициенту потерь идеального алгоритма относительно алгоритма А0 приведён в табл. 1.

Таблица 1

Lm	1	2	3	4	5	6	7
КПА0/КПИд	1	3	4.7	8.8	17	35	61

Ещё большего выигрыша можно добиться при параллельной передаче по трём каналам. Выигрыш для данного случая приведён в табл. 2. Параметры каналов: Pgg1=0.95, Pbb1=0.9; Pgg2=0.99, Pbb2=0.95; Pgg3=0.98, Pbb3=0.9.

Таблица 2

Lm	1	2	3	4	5
КПА0/КПИд	1	11.6	66	160	883

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

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

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

 (2)

и выражение для производительности источника, , (3)

где - количество слотов, передаваемых по каналу за секунду.

Далее рассмотрена обратная задача определения вероятности недоступности слота, необходимой для удовлетворения заданных требований .

Относительное количество доступных слотов должно быть не менее, чем передаваемых блоков, за минусом допустимых потерь. Из выражения (3) получим первое граничное значение вероятности недоступности слота

. (4)

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

. (5)

Решение данного уравнения даёт второе граничное значение вероятности недоступности слота . При бмольших значениях не выполняется условие по потерям.

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

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

.

Определён коэффициент потерь блоков относительно числа безошибочных слотов

. (6)

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

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

. (7)

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

. (8)

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

Множество пар значений вероятностей и , удовлетворяющих граничному условию по потерям (пересечение поверхности с плоскостью на рис. 2a и кривая 1 на рис. 2б), будет определяться решением уравнения

. (9)

Отобразив в плоскости границы, определяемые выражениями (8) и (9), определим область выполнения обоих требований. На рис. 2б приведён такой график, где кривая 1 - выполнение требований по кривая 2 - выполнение требований по доступности слотов.

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

Рис. 2. a - Графическое решение уравнения (9)

б - Границы выполнения требований по и

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

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

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

Рис. 3. К классификации видов хоппинга

В начале главы проведена классификация методов хоппинга. По периодичности схемы выделения слотов логическому каналу, хоппинг может быть регулярный и нерегулярный. Схема регулярного хоппинга имеет постоянный период. При нерегулярном хоппинге смена канала (или схемы последовательно-параллельного выделения слотов) происходит в случайные моменты времени при выполнении определённых условий.

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

По использованию слотов для передачи блоков:

- Последовательный хоппинг. При образовании логического канала слоты физических каналов располагаются последовательно (рис.3а).

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

- Параллельный хоппинг с чередованием. Слоты второго канала на участке подключаются параллельно, но используются последовательно, чередуя слоты исходных каналов через один (рис.3в). При этом увеличивается скорость передачи слотов.

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

Средняя вероятность недоступности слота в результирующем канале:

при регулярном, последовательном хоппинге

; (10)

при параллельном регулярном хоппинге

; (11)

при параллельном хоппинге с чередованием

. (12)

Коэффициенты потерь блоков в каналах:

при регулярном неравномерном хоппинге

; (13)

при регулярном неравномерном хоппинге с параллельным подключением

; (14)

при регулярном неравномерном хоппинге с чередованием

. (15)

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

При регулярном, последовательном хоппинге:

, отсюда ; (16)

при регулярном неравномерном хоппинге с параллельным подключением

; (17)

при параллельном хоппинге с чередованием канальных слотов

. (18)

После определения отношения , или проверяем требование по коэффициенту потерь блоков.

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

.

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

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

Рис. 4. Выбор каналов идеальным алгоритмом

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

.

Рис. 5. Граф системы из двух параллельных каналов

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

Система из двух параллельных каналов может иметь четыре состояния: нулевое GG - соответствует доступности слотов обоих каналов; первое GB - в первом канале слот доступен, во втором нет; второе BG - в первом канале слот недоступен, во втором доступен; третье BB слоты обоих каналов недоступны. Полный граф системы из двух параллельных каналов показан на рис. 5.

Для ПЛК, выбранного идеальным алгоритмом из двух исходных, финальная вероятность плохого состояния равна

Вероятность сохранения плохого состояния и вероятность перехода в безошибочное состояние после ошибки

.

Для финальной вероятности ошибок справедливо соотношение

Выразим из данного соотношения переходную вероятность

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

Таким образом, матрица марковской цепи лучшего канала, полученного с помощью идеального алгоритма, определена

.

Аналогично были получены переходные вероятности для худшего канала. При этом агрегировались первое, второе и третье состояния.

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

,

,

.

Аналогично определены переходные вероятности «худшего» канала и канала «среднего качества», построенных идеальным алгоритмом в пучке из трёх исходных физических каналов.

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

и .

Целью анализа является определение переходных вероятностей результирующего канала

.

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



Рис. 6. Граф для регулярного неравномерного хоппинга, общий случай

Для определения параметров результирующего канала была проведена свёртка графа путём агрегирования всех одноимённых состояний до двух состояний. Подграфы агрегируемых состояний приведены на рис. 7.

Рис. 7. Агрегирование хороших состояний для общего случая

Ниже приведены выражения для определения переходных вероятностей графа, свёрнутого до двух состояний, при любых значениях длин слотов хоппинга:

;

;

;

.

Для проверки корректности полученных выражений проведено имитационное моделирование. Имитировались два канальных массива с параметрами: ; и , каждый исходный массив объёмом 900000 элементов. Так как средние длины нахождения в состояниях однозначно связаны с переходными вероятностями и имеют погрешности одного порядка, но определяются проще, то при моделировании сравнивались средние длины в диапазоне от 1 до 150, полученные из имитации и расчёта по полученным выше выражениям. Погрешности в указанном диапазоне не превысили 2 %, что подтверждает состоятельность полученных выражений.

Аналогично получены переходные вероятности результирующего канала, образованного регулярным неравномерным хоппингом c параллельным подключением слотов:



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

; ;

; .

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

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

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

вероятность доступности следующего слота при недоступности текущего

; (19)

вероятность доступности следующего слота при доступности текущего:

; (20)

вероятность недоступности следующего слота, при недоступности текущего

; (21)

вероятность недоступности следующего слота, при доступности текущего

. (22)

Выражения (19 - 22) справедливы для прогнозирования результатов приёма только следующего слота, то есть без задержки квитанции. Если квитанция приходит с задержкой, то в выражениях (19 - 22) следует использовать модифицированные значения переходных вероятностей модели Гилберта с соответствующей глубиной . Определить данные параметры можно по следующим выражениям:

, .

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

По использованию информации о результатах предыдущих попыток алгоритмы данного класса можно разделить на три группы:

- алгоритмы без памяти не используют информацию о предыдущих попытках;

- алгоритмы с единичной памятью принимают решения по результатам анализа качества приёма последнего блока в каждом канале;

- алгоритмы с длинной памятью принимают решения на основе анализа исходов фиксированного числа последних попыток.

Для оценки эффективности от управления хоппингом используем введённый ранее алгоритм А0, в котором управление отсутствует.

Рассмотрим алгоритмы, показавшие лучшие результаты при моделировании.

Алгоритм с минимизацией смен каналов A1-МСК. Логика принятия решения данным алгоритмом такова: если результат последнего известного приёма в текущем канале не хуже, чем в других, то не меняем канал, иначе выбираем слот в одном из каналов с лучшим результатом.

AБ-СКО/L - алгоритм выбора по среднему коэффициенту ошибок с буфером длиной L. Для каждого канала по содержимому буфера оценивается средний коэффициент ошибок (или число недоступных слотов). Каналы ранжируются по качеству. На каждом шаге блокам с бмольшим числом неудач предоставляются слоты в каналах с меньшим числом ошибок в буфере.

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

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

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

С использованием рассмотренных выше алгоритмов было проведено имитационное моделирование, позволившее получить количественные оценки эффективности применение данных протоколов. На рис. 8 приведены зависимости средних коэффициентов ошибок в лучших логических каналах, организованных разными алгоритмами в пучках из двух и трёх исходных каналов, от задержки квитанций. Как видим из рисунков, при небольших задержках квитанций алгоритмы с буфером и алгоритм с минимизацией действий позволяют получить логический канал с существенно (на 40 - 50 %) меньшим, чем в лучшем их исходных каналов, коэффициентом ошибок. Для определения потенциальных возможностей по выбору лучшего канала, на рисунках пунктирной линией показано значение коэффициента ошибок канала, выбранного идеальным алгоритмом или параллельным использованием всех каналов пучка. При этом коэффициент потерь слотов для двух каналов равен 0.21, а для трёх - 0.39.

Рис. 8. Зависимости средних коэффициентов ошибок ПЛК, организованных разными алгоритмами в пучках:

из двух исходных каналов

1 - , ;

2 - , .

из трёх исходных каналов

1 - , ; 2 - , ; 3 - , .

Далее представлены результаты моделирования алгоритмов управления хоппингом с целью минимизации потерь блоков из-за превышения количества допустимых попыток передачи. Графики зависимости коэффициента потерь от допустимого числа переспросов при фиксированной величине задержки квитанций для пяти алгоритмов приведены на рис. 9. Алгоритмы обозначены следующим образом: 1 - алгоритм A0, 2 - идеальный алгоритм ID, 3 - алгоритм A1Б-ПЦМ (Г), 4 - алгоритм А1-МСК, 5 - алгоритм с буфером А1Б-СКО. Как видно из рисунков, предложенные алгоритмы управления позволяют в десятки раз уменьшить потери блоков.

Рис. 9. Зависимость КП

, ; , ; , .



Рис. 10. Зависимости выигрыша в разах по коэффициенту потерь для алгоритмов управления в сравнении с A0 от величины задержки квитанций

На рис. 10 представлены зависимости отношения коэффициентов потерь блоков алгоритма А0 к коэффициенту потерь соответствующего алгоритма управления: 1 - выигрыш идеального алгоритма ID, 2 - выигрыш алгоритма А1Б-ПЦМ, 3 - алгоритма с минимизацией смен каналов, 4 - алгоритма с буфером. Как видно из рисунков, все алгоритмы управления имеют выигрыш в рассматриваемом диапазоне задержек.

Сравнивая алгоритмы управления, можно сказать, что наилучших результатов позволяет добиться А1Б-ПЦМ (А1Б-Г). Однако этот алгоритм значительно сложнее остальных по вычислительным затратам и требует постоянных оценок параметров цепи каждого канала пучка. Как видно из приведённых выше рисунков, при малых значениях и малом числе каналов в пучке, алгоритмы А1-МСК и А1Б-СКО проигрывают незначительно, но при этом они существенно проще.

В заключении сформулированы основные результаты исследования.

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

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

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

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

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

6. Разработаны математические модели для вычисления параметров результирующих каналов, образованных параллельным использованием двух и трёх каналов с группирующимся характером доступности слотов.

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

при регулярном неравномерном параллельном хоппинге; при регулярном неравномерном параллельном хоппинге с чередованием канальных слотов.

8. Получены выражения для коэффициентов прогноза качества передачи блока на основании анализа результата последнего известного принятого блока и задержки квитанции.

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

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

Список работ, опубликованных по теме диссертации

1. Карпылев М.Л., Шевнина И.Е. Простой алгоритм управления хоппингом для выбора лучшего канала. - Материалы Российской НТК «Информатика и проблемы телекоммуникаций». Т. 1, 2008. - с. 257 - 258.

2. Shevnina I. Calculation probability of n errors by parallel transmission in several discrete channels. International Workshops and Tutorials on Electron Devices and Materials EDM 2008.

3. Мелентьев О.Г., Шевнина И.Е. Вычисление параметров результирующих каналов при идеальном алгоритме управления хоппингом. - Материалы X международной конференции «Проблемы функционирования информационных сетей», 2008. - с. 167 - 174.

4. Шевнина И.Е. Прогнозирование качества приёма слота по результатам предыдущих попыток в каналах с группирующимися ошибками. - Материалы X международной конференции «Проблемы функционирования информационных сетей», 2008. - с. 143 -145.

5. Мелентьев О.Г., Шевнина И.Е. Соотношения параметров модели Гилберта и простой марковской цепи // Журнал научных публикаций аспирантов и докторантов. 2008, № 8, с. 243 - 246.

6. Мелентьев О.Г., Шевнина И.Е. Оценка эффективности управления хоппингом при передаче по каналам с группирующимися ошибками // Вестник СибГУТИ. 2008, № 2, с. 28 - 30.

7. Шевнина И.Е. Алгоритм построения приоритетного логического канала с прогнозированием качества приёма слотов - Материалы Российской НТК «Информатика и проблемы телекоммуникаций». Т. 1, 2009. - с. 223 - 224.

8. Мелентьев О.Г., Шевнина И.Е. Сравнение алгоритмов выбора логического канала, с учетом приоритетов // Электросвязь. 2010, № 2, с.50 - 52

9. Величко В.В., Шевнина И.Е. Оценка вероятности успешной доставки слота в каналах, описываемых моделью Гилберта - XXV международная конференция Российской академии естественных наук (РАЕН) «Мобильный бизнес: перспективы развития и проблемы реализации систем мобильной связи в России и за рубежом» 30 марта - 1 апреля 2009 г. в г. Ньян-Чанг (Вьетнам).

10. Шевнина И. Е., Лямин Н.В., Клейко Д.В. Модифицированная методика вычисления матрицы переходных вероятностей при неравномерном хоппинге двух каналов. Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций». - Новосибирск, 2011. - с.

11. Шевнина И. Е. Методика определения параметров канала с независимым поражением слотов для удовлетворения заданных требований на качество обслуживания. Российская научно-техническая конференция «Информатика и проблемы телекоммуникаций». - Новосибирск, 2011. - с.

Размещено на Allbest.ru