Содержание к диссертации
Введение
1 Телетрафик в беспроводных ip-сетях: характеристика объекта исследования и особенности моделирования ... 17
1.1 Обзор моделей пакетного телетрафика в компьютерных сетях 17
1.2 Общие системотехнические замечания об объекте исследования, особенности беспроводных сетей с/Р-трафиком 21
1.2.1 Достоинства беспроводных технологий передачи данных 23
1.2.2 Характеристика топологий беспроводных сетей 24
1.2.3 Характеристика производительности беспроводных сетей 25
1.3 Модели пространства сообщений в беспроводных сетях 27
1.4 Ошибки и помехи в беспроводных сетях 30
1.5 Обоснование выбора моделей телетрафика 34
1.6 Выводы 35
2 Многомерные вероятностные распределения и случайные процессы для моделирования телетрафика. алгоритмы генерации 37
2.1 Теоретическая база моделирования телетрафика многомерными распределениями 37
2.1.1 Числовые характеристики многомерных случайных величин 37
2.1.2 Моменты и характеристические функции многомерных случайных величин 40
2.1.3 Преобразования функций плотностей вероятностей многомерных случайных величин 43
2.2 Многомерное нормальное распределение и его обобщение как составная часть модели 44
2.3 Алгоритмы генерации потоков сообщений от нескольких источников в виде многомерных распределений 55
2.3.1 Общие принципы генерации многомерных нормальных распределений 55
2.3.2 Генерация ковариационных матриц многомерных нормальных распределений 59
2.4 Модели на основе смеси нормальных, сферических и эллиптических распределений 65
2.5 Конструкция многомерного случайного процесса эллиптического вида для построения модели телетрафика 69
2.5.1 Алгоритмы генерации составного случайного прог\есса эллиптического вида для построения модели телетрафика 71
2.6 Выводы 72
3 Стохастическая модель источника ошибок в канале связи 73
3.1 Математическое моделирование каналов связи 75
3.1.1 Анализ известных математических моделей источников ошибок. 76
3.1.2 Обгцая структура источника ошибок 79
3.2 Модель типа скользящего среднего (МА(р)) 81
3.2.1 Среднее и дисперсия числа ошибок в сообщении длины N 81
3.2.2 Средняя длина пакета ошибок 87
3.2.3 Среднее расстояние между соседними ошибками 90
3.2.4 Идентификация параметров модели 90
3.2.5 Пример модели типа скользящего среднего 94
3.3 Модель типа авторегрессии (AR(p)) 95
3 А Модель типа скользящего среднего второго порядка 97
3.5 Скрытая марковская модель 100
3.5.1 Оценка состояний канала 102
3.5.2 Идентификация модели 103
3.5.3 Основные характеристики канала 104
3.6 Модель Гильберта 107
3.6.1 Модель Гильберта, как пример скрытой марковской модели 107
3.6.2 Модель Гильберта. Основные характеристики канала 110
3.7 Выводы 115
4 Имитационная модель телекоммуникационного канала на основе модифицированных атрибутных грамматик 117
4.1 Общая структура модели 117
4.2 Блок математической модели помехоустойчивого цифрового канала .. 118
4.3 Блок имитации внешних воздействий 119
4.3.1 Использование модели скользящего среднего 120
4.3.2 Формально-грамматическая модель шума 122
4.3.3 Генератор шума 123
4.3.4 Модель типа скользящего среднего с линейным изменением коэффициентов 126
4.3.5 Использование скрытой марковской модели 131
4.4 Программный комплекс имитационного моделирования беспроводных сетей в условиях помех 132
4.5 Выводы 140
Заключение 141
Список литературы 142
Приложение. Акты об использовании результатов диссертационной работы 154
- Общие системотехнические замечания об объекте исследования, особенности беспроводных сетей с/Р-трафиком
- Моменты и характеристические функции многомерных случайных величин
- Модель типа скользящего среднего (МА(р))
- Блок математической модели помехоустойчивого цифрового канала
Введение к работе
Актуальность темы. Беспроводные технологии передачи данных распространяются и занимают важное место во всех отраслях промышленности и на транспорте. Тем не менее, данный процесс во многом зависит от радиуса действия и помехоустойчивости развертываемых беспроводных сетей. Снижение качества обслуживания в беспроводных сетях напрямую зависит от случайных явлений включения несанкционированных источников электромагнитного и радиоизлучения, вносящих помехи в режимы функционирования сетей. Во многом указанные источники помех нельзя отнести к чисто случайным, так как они формируются в соответствии с развертыванием систем, устанавливаемых на предприятиях, использующих технологии беспроводной передачи данных. В связи с этим разработка моделей телетрафика сетей беспроводной передачи данных на основе многомерных вероятностных распределений, а в общем случае - сведение процесса моделирования к разновидностям многомерных случайных процессов, параметры которых могут быть вычислены из наблюдения реально протекающих процессов выглядит обоснованной.
Свою долю ошибок вносит сам канал связи, в котором могут возникать различные процессы, связанные с физической структурой канала связи, также имеющие в своей основе вероятностную природу. В связи с этим актуальность задачи построения стохастической модели источников ошибок в каналах систем беспроводной передачи данных также вытекает из практических задач использования таких систем. Отрицательными факторами этих систем являются замирания и пропадания сигналов, что влечет за собой уменьшение информационной составляющей соответствующего трафика сети и снижение качества обслуживания клиентов сети. Кроме этого, характер ошибок, возникающих за счет влияния канала связи носит дискретный характер, поскольку возникают преобразования «аналог - цифра». Поэтому модели, которые используются для описания телетрафика не подходят по своей непрерывной природе для описания процесса ошибок, возникающих в канале связи.
Рассматриваемые в диссертационной работе математические модели, построенные на основе многомерных случайных процессов и с применением модифицированных атрибутных грамматик, как представляется далее, могут служить, как доказано теоретически и экспериментально, адекватным описанием процессов, протекающих в сетях беспроводной передачи данных и могут быть использованы при проектировании помехозащитных беспроводных сетей связи.
К основным математическим методам исследования процессов передачи информации в телекоммуникационных системах относятся теория вероятностей, математическая статистика, теория случайных процессов, имитационное моделирование.
Большой вклад в развитие теории моделирования компьютерных сетей, на базе которых строятся современные системы телекоммуникаций, внесли Л. Клейнрок, В.М. Вишневский. В теории телетрафика можно выделить работы В.Е. Леланда, М.С. Такку, В. Виллинджера, В.В. Крылова, B.C. Лагутина, СИ. Степанова.
При моделировании телекоммуникационных систем важнейшими характеристиками становятся законы распределения случайных величин и случайные процессы, в соответствии с которыми происходит поступление требований в систему и их обслуживание. В этой области следует отметить работы А.Н. Колмогорова, Ю.В. Прохорова, Г. Пойя, П. Леви, В. Феллера, А.Я. Хинчина, Дж. Дуба, М. Лоэва, Е. Лукача, Б. Мандельброта, А.В. Скорохода, А.Н. Ширяева, В.Н. Золотарева, А.В. Булинского, Г.Г. Галустова.
Теории и языкам имитационного моделирования посвящены работы Дж. Гордона, Е. Сейджвика, А. Лоу, В. Кельтона, В.В. Емельянова, В.М. Курейчика. Работы Г. Буча, П. Коуда, позволили создавать системы моделирования и программирования с использованием объектно-ориентированных принципов.
Как уже было отмечено выше, в каналах связи всегда присутствуют помехи, уменьшающие достоверность воспроизведения предаваемых сообщений, нарушающие требования своевременности и качества предоставляемой инфор-
мации, в математические модели потоков сообщений с целью адекватности моделирования необходимо включать модели источников ошибок. Методы исследования систем связи в условиях воздействия шумов и помех известны еще с работ В.А. Котельникова и К. Шеннона. Разработкой моделей источников ошибок занимались Э.Н. Гильберт, Е.О. Эллиот, В.И. Петрович, Б.Д. Фричман, В.М. Охорзин, В.Я. Турин, О.В. Попов и другие. Атрибутные грамматики, модификация которых предложена в данной работе для целей моделирования источников ошибок, были предложены Д.Кнутом.
Таким образом, обозначены проблемы, для решения которых потребовалось привлечение математических методов в сочетании с имитационным моделированием и разработкой программного обеспечения. Отметим, что указанные проблемы в настоящее время далеки от всестороннего и законченного исследования. Поэтому задачи, решению которых посвящена диссертация, относятся к актуальным проблемам проектирования и модернизации телекоммуникационных систем, построенных на базе распределенных компьютерных сетей с пакетной коммутацией данных.
Цель и задачи исследования. Основной целью и задачами исследования является развитие и применение математического аппарата теории многомерных случайных процессов к задачам моделирования телетрафика в беспроводных сетях пакетной передачи данных и разработка новых моделей телекоммуникационных каналов, включающих генераторы источников ошибок.
Для достижения поставленной цели необходимо решение следующих задач.
Разработка адекватных стохастических моделей информационных потоков, отражающих реальные процессы, возникающие в беспроводных сетях передачи данных. Разработка стохастических моделей источника ошибок в физическом канале связи.
Разработка методов исследования отмеченных в п.1 моделей.
На основе теоретических результатов (п. 2) разработка численных методов и алгоритмов для анализа моделей.
Разработка методов оценки параметров моделей с использованием средств современной математической статистики.
Разработка эффективных генераторов для исследуемого класса стохастических моделей процессов.
6. Развитие методов имитационного моделирования и создание про
граммного комплекса для оценки качества обслуживания систем связи на осно
ве объектно-ориентированного подхода.
7. Экспериментальная проверка разработанных теоретических подходов и
положений на адекватность в практических задачах.
Методы исследования основываются на использовании фундаментальных исследований в области случайных процессов, математической статистики, теории моделирования дискретных систем. При разработке моделей информационных потоков использовались методы генерации многомерных вероятностных распределений и случайных процессов.
Практическая проверка разработанных моделей и методов осуществлялась путем программной эмуляции, проведения имитационных экспериментов на модельных и на реальных объектах телекоммуникаций.
Научная новизна работы заключается в теоретическом обобщении и решении научно-технической проблемы, связанной с разработкой нового подхода к моделированию потоков информационного обмена в телекоммуникационных системах и сетях. К наиболее существенным научным результатам работы относятся следующие.
Разработана общая конструкция многомерного случайного процесса, отражающего процессы передачи сообщений в беспроводных сетях, позволяющая учесть особенности телетрафика в таких сетях, а также помехи, оказывающие существенное влияние.
Предложена на основе теории кумулянтного анализа (в отличие от ранее использовавшегося для таких целей аппарата характеристических функций) модель составного эллиптического процесса, в котором сохранены полезные свойства нормального процесса.
Разработаны алгоритмы генерации сообщений от нескольких источников, территориально распределенных случайным образом в зоне действия беспроводной сети с использованием в качестве ядра модели составного эллиптического процесса.
Получены новые типы моделей, использующих сочетание известных линейных моделей с неиросетевой моделью. Для названных моделей построена теория, позволяющая исследовать статистические свойства канала связи. Для класса хорошо себя зарекомендовавших моделей было предложено общее описание этих моделей в виде скрытой марковской цепи, что позволило для этого класса моделей аналитически вычислить основные характеристики каналов связи.
5. Предложена максимально общая структура генератора шума, которая
позволяет получать генераторы для разнообразных квазипериодических про
цессов. Для достижения этой цели предложена оригинальная модификация ат
рибутной грамматики Д. Кнута.
Практическая ценность. Предложенные теоретические подходы к формальному описанию случайных процессов в беспроводных компьютерных сетях используются в системах телекоммуникаций для оценки качества их функционирования, снижения количества ошибок и искажений сообщений, а также могут быть использованы при проектировании и модернизации современных систем связи.
Практическую ценность представляют следующие результаты.
Разработан, внедрен и адаптирован комплекс программ для моделирования работы систем телекоммуникаций. Внедрение этого комплекса позволило определить «узкие места» в системах связи и предложить обоснованные рекомендации по их устранению.
Проведены экспериментальные исследования статистических характеристик случайных процессов, протекающих в беспроводных системах телекоммуникаций, в частности, в системах сотовой связи. Исследованы и измерены потоки данных, на основе чего выявлены особенности беспроводных сетей с IP-
трафиком, выполнена оценка производительности беспроводных сетей, построены модели пространства сообщений в таких сетях, подробно исследованы ошибки и помехи, возникающие в беспроводных сетях связи и предложены соответствующие математические и имитационные модели.
Разработаны и внедрены в Ростовской сети сотовой связи методы моделирования и оценки потоков данных, позволяющие повысить эффективность и качество функционирования действующих систем передачи информации.
Проведенные исследования позволили осуществить расчет реальных характеристик каналов связи, сравнение их с проектными, предоставить объективные оценки качества обслуживания по сравнению с проектными характеристиками. Проведенный анализ позволил определить причины снижения качества обслуживания по сравнению с проектными характеристиками и выдать рекомендации по устранению этих причин.
Достоверность научных и практических результатов работы. Научные положения, результаты и выводы, сформулированные в диссертации, строго аргументированы. Сформулированные в работе законы моделирования, разработанные численные методы и алгоритмы основываются на известных в теории вероятностей, теории случайных процессов, теории телетрафика фундаментальных понятиях и подходах. Достоверность теоретических результатов подтверждается четкостью постановок задач, формулировок основных утверждений и определений, корректностью математических доказательств. Достоверность результатов и выводов подтверждается данными экспериментальных исследований и имитационных экспериментов, а также результатами эксплуатации разработанных методов и комплексов программ, внедренных в качестве подсистем в функционирующие системы связи.
Реализация результатов работы.
Результаты работы прошли успешную апробацию, внедрены и используются при проектировании сложных структурных решений и модернизации средств обеспечения телекоммуникаций: в работах ЗАО «Ростовский сотовый
телефон» «Скай Линк - Ростов»; ООО «ПромСвязь» (г. Ростов-на-Дону). Акты внедрения и использования научных результатов приведены в приложении.
Апробация работы. Основные положения и результаты диссертационной работы докладывались и обсуждались на Всероссийском симпозиуме по прикладной и промышленной математике (2007 г., Сочи); на международной научно-практической конференции «Актуальные проблемы информатики и информационных технологий» (2007 г., Тамбов); на Международных научно-практических конференциях «Теория, методы проектирования, программно-техническая платформа корпоративных информационных систем» и «Моделирование. Теория, методы и средства» (2007, 2008 г.г., Новочеркасск); на Всероссийской научно-практической конференции «Актуальные задачи математического моделирования и информационных технологий» (Сочи, 2008 г.), на научно-практических конференциях профессорско-преподавательского состава Ростовского государственного университета путей сообщения (2007 - 2008 г.г.).
Публикации. Полученные в диссертаций теоретические и практические результаты нашли свое отражение в 10 печатных работах, в том числе 4 статьях в научных журналах, рекомендованных ВАК РФ.
Структура и объем работы. Диссертация состоит из введения, 4 глав, заключения, приложения, списка литературных источников. Общий объем диссертации составляет 157 стр.
Во введении обосновывается актуальность проведенных исследований, формулируются цели и задачи исследований, приводятся основные научные и практические результаты, а также кратко рассматривается содержание диссертации по главам.
В 1 главе выполнен анализ современного состояния в области математического моделирования телетрафика и каналов связи в системах телекоммуникаций, построенных на базе компьютерных сетей с пакетной передачей данных.
Дана характеристика объектов исследования, и предложены принципы моделирования пространства сообщений в беспроводных сетях.
В главе 2 исследуется теоретическая база моделирования телетрафика многомерными распределениями. Разрабатываются алгоритмы генерации потоков сообщений от нескольких источников в виде многомерных распределений. Предложена конструкция многомерного случайного процесса эллиптического вида для построения модели телетрафика.
Общие системотехнические замечания об объекте исследования, особенности беспроводных сетей с/Р-трафиком
Основным объектом исследования данной работы являются беспроводные сети передачи данных. Это обстоятельство сужает круг исследований, потому что широкий класс беспроводных сетей передачи речевых сообщений, в том числе и с применением цифровых технологий в работе рассматриваться не будет. Несколько особняком стоят спутниковые сети передачи данных, обсуждение технологических особенностей которых находится далеко за пределами указанного параграфа, хотя на наш взгляд все-таки они находятся ближе к исследуемым системам, потому, что некоторые спутниковые транспондеры передают пакетный ZP-трафик. Приведем иллюстративный аспект укрупненного разделения беспроводных технологий. На рис. 1.1. левая ветвь не будет относиться к теме исследования, по технологиям значительно отличаясь от стека протоколов TCP-IP , таким образом, в дальнейшем сосредоточим свое внимание именно на системах передачи данных, хотя, безусловно, существуют технологии, позволяющие передавать речевые сообщения с помощью систем, обозначенных правой ветвью рис. 1.1. Областью исследования данной работы будут являться системы передачи пакетного /Р-трафика (на рис. 1.1. они выделены цветом). Технологии функционирования таких систем, архитектура и необходимое оборудование для их развертывания и эксплуатации достаточно полно представлены в современной литературе, из которой особо можно выделить работу [28], имеющую также ценность и в научном плане.
Обозначим несколько, на наш взгляд, существенных преимуществ использования беспроводных технологий по отношению к проводным, хотя заметим, что по отношению к магистральным линиям связи высокой производительности беспроводных сетей достичь не удается. Одним из организационных преимуществ беспроводных технологий можно назвать повышение мобильности и связанную с этим фактором производительность труда. Оставаясь подключенными к сети, абоненты могут в буквальном смысле слова встретиться и расположиться рядом друг с другом, провести необходимые переговоры, консультации. Тем не менее, ресурсы, которые они совместно используют, остаются доступными в любом месте действия сети. Еще одним преимуществом является быстрое развертывание и настройка сети. Это оказывается весьма существенным при деловых переговорах, презентациях с участием большого числа пользователей. Немаловажную роль такая возможность играет при необходимости обучения школьников, студентов или повышения квалификации специалистов. После развертывания беспроводной сети во многих случаях есть потребность пользования сервисами сети Интернет. В таком случае задача также является легко осуществимой, так как одна точка доступа, подключенная к сети Интернет, автоматически распространяет данную возможность на всех пользователей беспроводной сети. Следует обратить внимание также на свойство высокой масштабируемости беспроводной сети, и опять таки задача подключения новых пользователей не сопряжена с прокладкой кабельной системы и фиксированностью точек доступа в сеть. Как следствие указанного фактора, можно назвать гибкость развертывания сети относительно местоположения и взаимного размещения зданий и сооружений. И, наконец, в некоторых случаях, беспроводные технологии снижают стоимость эксплуатации сети в целом, вместе с тем некоторые виды беспроводного сетевого оборудования для больших радиусов действия пока еще остаются дорогостоящими. С точки зрения модели ISO/OSI основные отличия между сетями стандартов Ethernet 802.3 и IEEE 802.11, то есть проводными и беспроводными сетями существуют на двух первых уровнях — физическом и канальном. Следует отметить, что на физическом уровне в беспроводных сетях возникает больше проблем с передачей сигналов, чем в проводных, а на канальном уровне количество коллизий при передаче данных существенно зависит от концентрации пользователей в некотором сегменте сети, что также доставляет больше проблем, чем в проводных сетях.
Топологии беспроводной сети рассмотрим на примере локальных сетей масштаба предприятия или организации, потому, что среди всех других вариантов беспроводных сетей, за исключением систем спутниковой связи различия не столь существенные. Существует три варианта топологий.
Во-первых, возможен режим (самый простой в применении), который называется «точка - точка» {point to point), а также его называют IBSS — Independent Basic Service Set, независимый базовый набор служб. Он представляет собой группу рабочих станций (на базе ноутбуков, карманных персональных компьютеров), которые связываются непосредственно друг с другом с помощью беспроводных сетевых адаптеров. Таким образом, получается простая одноранговая локальная вычислительная сеть WLAN {Wireless Local Area Network). У такой сети объективно недостатков больше, чем достоинств, потому что не приходится говорить даже о какой-то определенной конфигурации сети, к тому же сеть ограничена по протяженности (мощность сетевых адаптеров не позволяет удаление более, чем на два десятка метров) и планирование разделения сетевых ресурсов в большой степени зависит от желания их владельца. В техническом плане наблюдается низкая помехоустойчивость такой сети.
Как видно из характеристик сети предыдущего типа, такое ее устройство не подходит для организации информационной поддержки функционирования предприятий. Первой топологией, имеющей вполне определенную инфраструктурную организацию, является сеть с базовыми зонами обслуживания, BSS (Basic Service Sets). Она предполагает наличие особых станций ретранслирования сигналов, которые называются точками доступа (Access Points). В таком случае клиентские рабочие места связываются не друг с другом непосредственно, а с точкой доступа, перенаправляющей поток сетевых сообщений к рабочей станции-получателю. Техническое устройство точек доступа разнообразно как по мощности сигнала и, соответственно, радиусу обслуживания, так и по возможностям ее подключения к проводным сетям и другим аналогичным устройствам.
Расширить радиус действия сети можно также несколькими способами. Либо увеличением числа точек доступа, либо с помощью применения передачи данных по проводным каналам между ними. Тогда несколько BSS, соединенных между собой, образуют ESS (Extended Service Sets). Такая топология сети подойдет для развертывания регионально распределенных предприятий и организаций.
Моменты и характеристические функции многомерных случайных величин
Для доказательства условия 2 из теоремы 2.2 воспользуемся формулами-соотношениями между кумулянтами и соответствующими моментами многомерного распределения (п. 2.2). Несмотря на то, что в своем доказательстве Г.В. Кочран использовал моменты многомерного распределения, имеющие очевидную физическую или геометрическую интерпретацию, предлагаемый здесь подход также имеет некоторые преимущества: - кумулянты и кумулянтные функции, в отличие от моментов и момент-ных функций, имеют четко выраженный самостоятельный статистический смысл, и имеется возможность задавать их в определенной степени независимо друг от друга; - учет их высших порядков позволяет просто описать любую степень не-гауссовости случайных величин и процессов; - кумулянтное описание случайных величин и процессов имеет такую особенность, что ему всегда соответствует некоторая вещественная функция, аппроксимирующая моделируемое вероятностное распределение.
Существует несколько общих подходов к построению генераторов многомерных распределений. Первая группа методов основывается на применении генераторов одномерных распределений, в которых генерируется вектор, состоящий из независимых одинаково распределенных случайных скалярных величин, а затем выполняется преобразование этого вектора в соответствии с требуемым многомерным распределением. В данном случае метод обращения кумулятивной функции распределения не применим к генерации многомерных распределений, хотя маргинальные и условные одномерные распределения могут быть использованы в методе обращения кумулятивной функции распределения для генерации многомерных случайных величин. Речь идет о том, чтобы выполнять декомпозицию кумулятивных функций распределения р -мерной случайной величины X = Х1}...,Хр в следующем виде: РХи...,Хр \Х\ — Хр ) = РХ, \Х\ )РХ2\Х, \Х2 \Х\ ) " - РХр\х,Х2...Хр \ХР Xl X2 - Xp_i )
Существуют также итеративные методы генерации многомерных наблюдений. Изложим в удобном для программирования алгоритмическом виде один из таких методов, который, как доказано в [104], позволяет получить сходящийся ряд реализаций случайной величины (при &— оо). Для этого алгоритма должна быть известна плотность распределения и сгенерировано некоторое множество S czRp, \S\» р случайных величин с заданной плотностью.
Определить, что сходимость достигнута, является достаточно трудной задачей. Если одна из р -мерных случайных величин сформирована, то есть сходимость достигнута, остальные подпоследовательности могут либо начинаться с итерации при к = 0, то есть с первого шага алгоритма, либо продолжаться с некоторого достигнутого за предыдущие итерации значения к. В последнем случае следует обращать внимание, что вновь формируемые подпоследовательности не будут независимыми. Этот факт влияет на оценку дисперсии у генерируемых случайных величин, но не влияет на среднее.
Способом прямого преобразования для генерации многомерного нормального распределения является генерация р -мерного вектора у независимых одинаково распределенных стандартных случайных величин (например, по вышеизложенному алгоритму), затем - формирование вектора х = Ату + ц., где А - матрица (рхр), такая, что А1 А = Z {А может быть получена разложением матрицы Е по методу квадратного корня, методу Холецкого [4]. В этом случае получаем х, распределенную как Ир{\1,Ъ). В дальнейшем можно получать усеченные многомерные нормальные распределения, вводя ограничивающие векторы а и Ъ так, чтобы а Сх Ь, где С - матрица ранга р, таким образом, ограничивая вектор у: (А1) (С1а-\х) у ( Ат) (C :b-[i\.
Заметим, что наряду с программными методами получения многомерных случайных величин и процессов существуют также способы генерирования случайных числовых последовательностей с заданными многомерными распределениями с помощью физических устройств, подробно описанные в [31]. Известны [24, 80] три основных метода, позволяющих генерировать дискретные случайные процессы с заданной р -мерной плотностью вероятности: метод условных вероятностей, метод Неймана и метод смешивания нормальных случайных процессов.
Использование первых двух методов возможно только для формирования процессов ограниченной длительности, которая определяется размерностью функции распределения N. Метод смешивания нормальных случайных процессов позволяет формировать случайные процессы произвольной длины К, но может быть использован для моделирования ограниченного класса процессов, многомерные плотности вероятностей которых аппроксимируются гауссовыми со случайными весовыми коэффициентами. Этот метод может быть использован для моделирования случайных процессов, нестационарных как по времени, так и по реализации, в то время как первые два метода позволяют моделировать процессы, нестационарные только по реализациям.
Модель типа скользящего среднего (МА(р))
Использование моделей типа скользящего среднего, рассматриваемых ниже, предложено автором в [92].
Процесс, порождаемый (3.1), является стационарным процессом, так как стационарным является процесс скользящего среднего ,. = ] я/о\ .. Для даль нейшего нам понадобится ковариационная функция p{k) = Cov{EiEj+k). Если к р, то Ег и Е1+к - независимы, поэтому р(к) = 0. Пусть 0 к р.
Вычислим М(ЕЕпк) = Р(ЕІ = \,Еі+к = і) = Р( Q, i+k Є). Совместное распределение случайных величин ,; и Z,j+k — двумерный нормальный закон, который полностью определяется математическими ожиданиями МЪ 1 = 0, МЪ)пк =0 и ковариационной матрицей.
Представим .+А в виде .+А. = а (),,. + [3(&)є, є - стандартная нормальная случайная величина, независимая от . ё .+Л.
Под пакетом ошибок длины s ], стартующим в момент времени / = 1, понимаются последовательности, обладающие свойством Ех -\ ,..., Es =1, Es+l -0. Обозначим через \х, - случайную величину, равную длине пакета, стартующего в момент времени /. Далее мы предполагаем, что случайное событие: А, = «пакет стартует в момент времени /» произошло. Случайное событие А, = {м = 0} л {Et = 1} л {Ем = 1} . Следовательно, условная вероятность РА (u., =s) = P{EU2 = l?---5 /+5_i = ЬE l+s - О), при s 2, и РА [\x.t = 2) = Р(/+2 =0) при s = 2. Если пакет стартует, в начальный момент времени, то мы будем считать, что произошло событие Ах =\ЕХ =1}л{2 -1}. Из стационарности последовательности Е следует, что РА (u., -s) = РА ([1, = s). Вероятность РАі (ц, = s) = P(El+2 = 1,...,El+S_x - l,El+s = 0).
Для вычисления необходимых для выбора оптимального кодирования параметров канала по формулам, приведенным в предыдущих параграфах, необходимо знать параметры модели: р, (а,) 0, 6 - порядок модели, коэффициенты, порог. Исходными данными для получения оценок является наблюдаемая последовательность Е. Поскольку последовательность А - ненаблюдаемая последовательность, то используется техника, основанная на методе Монте-Карло. При помощи генератора независимых одинаково распределенных нормальных стандартных значений генерируется необходимое число реализаций последовательности A: A,,A2,...,AL. Затем, при помощи смещающегося окна размера р +1, в каждом из А. выделяются отрезки последовательности, к которым в качестве первого элемента добавляется — 1 и, в зависимости от значения соответствующего элемента последовательности Е, эти отрезки помещаются в качестве строк либо в матрицу А (Ег = 0), либо в матрицу В (Et =1). Остановимся на оценке коэффициентов и порога и зафиксируем параметр р. Обозначим через вектор, в который входит порог и коэффициенты. Будем считать, что произведение Аа - выборка из нормального закона N(ma,Ga), произведение Ва - выборка из нормального закона N(mb,ab}. Положим та=-\, ть=\, за=аь= з.
С помощью датчика стандартного нормального распределения была сгенерирована последовательность А длиной 10004, на основании которой и параметров модели была получена последовательность Е длиной 10000, по которой были вычислены оценки параметров модели (раздел 3.7). Оценки параметров модели приведены в третьей строке таблицы.
В первом столбце таблицы приведены значения аргумента, во втором — значения ковариационной функции, в третьем - значения корреляционной функции (использовались параметры модели). В четвертом и пятом приведены значения корреляционной функции (использовались оценки параметров модели). Основные характеристики канала:
Проведенный во введении к главе анализ позволяет утверждать, что наиболее распространенные модели канала, являются частными случаями скрытой марковской модели. Предлагаемая модель может быть использована как при статистическом анализе свойств реального канала связи, так и при разработке помехоустойчивого кодирования, чтобы повысить достоверность передаваемой информации. Основные положения данного и последующих разделов главы опубликованы автором в работе [91].
По-прежнему рассматриваются аддитивная помеха Е = {Е;.}, случайная дискретная последовательность, и добавляется случайная последовательность состояний канала - D = {Д.}, значения DtEWD.
Полученные формулы позволяют непосредственно анализировать основные характеристики канала.
1. В результате исследований, выполненных в данном разделе, получены новые типы моделей, использующих сочетание известных линейных моделей с нейросетевой моделью.
2. Для названных моделей построена теория, позволяющая исследовать статистические свойства канала связи.
3. Предложен единый способ исследования для класса моделей, ранее изучавшихся в литературе разрозненно. Для этого были выявлены общие свойства моделей, которые воплотились в скрытую марковскую цепь.
4. Для скрытой марковской цепи получены результаты, позволяющие вычислять основные характеристики каналов связи.
Блок математической модели помехоустойчивого цифрового канала
Математической моделью объекта является помехоустойчивый цифровой канал передачи данных (ЦПК), который содержит пять элементов: источник сообщения, кодер канала, линия связи, декодер и приемник сообщения. Задача источника сообщений — генерация сообщений, которые кодируются кодером и поступают в линию связи. Декодер канала получает зашумленный поток данных и восстанавливает данные, которые поступают на вход приемника сообщений.
Канал считается двоичным симметричным, синхронизированным без стираний. Поэтому линия связи является битовым сумматором сообщения и процесса ошибок.
Задача блоков «Кодер канала» и «Декодер канала» заключается, в помехоустойчивом кодировании и декодировании данных.
Естественно, что модель должна содержать пополняемую библиотеку помехоустойчивых кодеков. Понятно, что выбираемая пара код ер-декодер должна быть согласована. Эта согласованность представлена на рис. 3.3. Модель допускает каскадирование кодеков канала, то есть последовательное применение нескольких кодеров и декодеров. В модели также предусмотрена возможность использования перемежителей и деперемежителей, предназначенных для превращения пакетов ошибок в случайные одиночные ошибки, с которыми легче справляться при помехоустойчивом кодировании.
В ряде работ, например, в [40, 68] предлагается моделировать ошибки, возникающие в канале связи при помощи квазипериодических процессов. Использование квазипериодических процессов основано на предположении, что одно и тоже состояние канала может сохраняться на множестве смежных позиций, то есть в последовательности состояний канала различаются серии «плохих» состояний канала и серии «хороших» состояний канала. Таким образом, можно выделить чередующиеся пакеты - пакеты, в которых вероятности возникновения ошибок существенно различаются. Число позиций в пакете ошибок — Я и число позиций в промежутках между пакетами // называются длинами пакетов. Естественно считать длины случайными величинами с распределениями вероятностей /д(г) и /м{т) соответственно, г = 0,1,...,77,... . Рассмотрим последовательность [Яі,jut ). 0. Случайные величины Я,, и /лі независимы, случайные Д0,Я,,... независимы и одинаково распределены с распределением вероятностей - /я(т), случайные величины //0,//,,... независимы и одинаково распределены с распределением вероятностей /м(т).
Более общая имитационная модель может быть получена на основе использования атрибутных грамматик, введенных в 60-х годах прошлого столетия Д.Е. Кнутом для описания статической семантики языков программирования [54]. Использование стохастических атрибутных грамматик для моделирования внешних воздействий на телекоммуникационный канал предложено автором в работе [93].
Определение атрибутной грамматики. Пусть G = ((S ,JV,7,,.P) - контекстно-свободная (КС) грамматика, где - стартовый символ, N - алфавит нетерминальных символов, Т - алфавит терминальных символов, Р -множество правил вывода КС-грамматики. Мы предполагаем, что в грамматике отсутствуют нетерминальные символы, непринадлежащие ни одному из выводов.
Атрибутная грамматика состоит из КС-грамматики G, которая называется базой атрибутной грамматики, отображений Z и I, которые ставят в соответствие каждому символу X є TV и Г непересекающиеся множества Z{x) и l(x) синтезируемых и наследуемых атрибутов, а также из множеств М(р) - множеств семантических правил (правил вычисления атрибутов) для каждого правила реР. Для наших целей атрибутная грамматика Кнута нуждается в модификации. Определение модифицированной атрибутной грамматики. В качестве базы возьмем стохастическую контекстно-свободную грамматику 122 G = (S, N, Т, О). Элемент Q конечное множество стохастических правил вывода. Стохастическое правило вывода имеет вид Y—q— X, где Y&N, X є (iV иГ) , q - вероятность применения правила. Вероятности применения правил должны удовлетворять ограничению. Пусть в Q имеется набор стохастических правил вывода: Y—qx— XX,Y— —»X2,...,F—$ — Хп, тогда п qt =1, и все qi 0. Отображения Z(x) и l(x)определяются для каждого X є Т. Множества семантических правил определяются для каждого X є Т.
Описание модели начнем с интерпретации алфавита терминальных символов. Каждый элемент алфавита терминальных символов соответствует состоянию канала. Атрибутами элемента алфавита X являются а(х\Ъ{Х),М{х). Атрибут а(Х) является наследуемым атрибутом, атрибуты Ь(Х) и М(Х) - синтезируемые атрибуты. Причем b(x) - случайная величина с распределением вероятностей fx (г) (длина периода для состояния канала X). Атрибут М(Х) — модель типа скользящего среднего, соответствующая состоянию канала X. Вычисление наследуемого атрибута а(х).
Пусть X содержится в цепочке Я є (N U Т) и Y - предшествующий X терминальный символ из цепочки Я, тогда а(Х) = a(Y)+ b(Y). Если в цепочке Я нет предшествующих X терминальных символов, то а(х) полагается равным нулю. Таким образом, каждый терминальный символ X порождает стохастический интервал [а(Х),а(х) + б(х)-і] и определяет распределение вероятностей для сегмента шума, соответствующего интервалу [а(х),а(х) + Ь(х)-\] при помощи модели м{х).
Генератор шума базируется на следующих определяющих генераторах: генератор стандартной нормальной случайной величины - Genl, генератор равномерной случайной величины на интервале [ОД] - Genl. Алгоритм работы генератора шума имеет следующий вид:
Инициализация. Определение длины сообщения. Полагаем / = 0. Генерация начального терминального символа Х0, вычисление атрибутов: а{Х0)-0, b(X0) с использованием Genl и распределения вероятностей fx {т). Вычисление правой границы стохастического интервала d(X0) = m\n(b(X0)-l,N). Генерация нулевого фрагмента «шум» с использованием Genl и М(Х0).
Итерация. Если d(X,)=N, то переходим к п. 3. Полагаем / = / + 1. Генерация терминального символа Хп вычисление атрибутов: a(Xj)=d(XI_])+l, b{Xt) с использованием Genl и распределения вероятностей fx (г). Вычисление правой границы стохастического интервала d(Xi)=mm(a(Xj) + b(Xi)-l,N). Генерация /-го фрагмента шума с использованием Genl и М(ХІ). Переход к п. 2.
Последовательность может начинаться с интервала хороших или плохих состояний с вероятностями q и 1 - q соответственно. Причем интервал хороших состояний соответствует промежутку между группами пакетов. Внутри группы пакетов интервалы плохих состояний чередуются с интервалами хороших состояний. Группы пакетов чередуются с интервалами хороших состояний. Число плохих интервалов внутри группы пакетов является случайной величиной распределенной по геометрическому закону распределения.
Выше представлен общий алгоритм генерации шума, в котором модели М(х) не конкретизированы и являются моделями типа скользящего среднего. Во второй главе представлен алгоритм настройки параметров мо 127 дели. Однако для целей моделирования было бы удобней сузить класс моделей и предложить более простой метод настройки параметров модели. Отметим, что это не исключает использование общего алгоритма настройки параметров модели. Будем предполагать, что состояния канала - алфавит терминальных символов - разбивается на два подмножества: Г = Tb u Г, где Ть множество плохих состояний канала, Tg - множество хороших состояний канала. Пусть Хі є Tb, тогда М(Х,) = М(вь, \abi }р=о), если Х{ є Tg, Тогда М(Х;)= м(# ,{а,.} 0]. То есть предполагается, что используются две модели: одна - для плохих состояний канала, другая - для хороших состояний. Пороги могут быть определены из вероятностей рь и pg — вероятностей ошибок при плохом и хорошем состояниях канала соответственно, в результате решения уравнений:
