автореферат диссертации по радиотехнике и связи, 05.12.14, диссертация на тему:Модели и методы расчета моноканальных интегральных локальных сетей

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМЕНИ ПРОФ.М.А.БОНЧ-БРУЕВИЧА

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

Верзун Наталья Аркадьевна

МОДЕЛИ И МЕТОДЫ РАСЧЕТА МОНОКАНАЛЬНЫХ ИНТЕГРАЛЬНЫХ ЛОКАЛЬНЫХ СЕТЕЙ

05.12.14 - Сети, узлы связи и распределение информации

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель -доктор технических наук профессор 0.ч_..Чугреев

Санкт-Петербург 1998

СОДЕРЖАНИЕ

Введение ......................................................................4

1. Объект и постановка задач исследования............................9

1.1. Алгоритмы сжатия информации ................................9

1.2. Вероятностные характеристики процесса передачи непрерывной информации..............................................24

1.3. Базовая модель интегральной локальной сети................27

1.4. Вероятностные, вероятностно-временные, стоимостные характеристики и проектные процедуры анализа и выбора. Постановка задачи анализа и выбора структуры............36

Выводы ......................................................................43

2. Модели и методы расчета интегральной локальной сети с

маркерным доступом..................................................44

2.1. Модель интегральной локальной сети с механизмом сжатия непрерывной информации........................................44

2.2. Сеансовая модель интегральной сети..........................65

2.3. Модель ИЛС с регулируемым маркерным доступом ... 74

2.4. Модель ИЛС с переспросами сжатой непрерывной информации........................................................87

Выводы ................................... 100

3. Модели и методы расчета интегральной локальной сети с син-

хронным временным доступом................... 103

3.1. Модель интегральной локальной сети с механизмом сжатия непрерывной информации.................... 103

3.2. Модели ИЛС с регулируемым СВД и переспросами сжатой непрерывной информации............... 115

3.3. Модель ИЛС с фиксированным числом станций сжатой и несжатой непрерывной информации ............. 122

Выводы ................................... 129

4. Выбор вариантов структуры интегральной локальной сети ... 131

4.1. Отношения вариантов интегральных локальных сетей со сжатием по вероятностно-временным характеристикам............131

4.2. Задачи выбора структуры интегральной локальной сети . . . 142

4.3. Пример выбора структуры интегральной локальной сети . . . 144

Выводы..........................................................................168

Заключение..................................................................170

Литература ..................................................................172

ПРИЛОЖЕНИЕ 1. Листинги программы расчета вероятностных и вероятностно-временных характеристик моноканальных интегральных локальных сетей ............................................182

ВВЕДЕНИЕ

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

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

Необходимость исследований интегральных локальных сетей подтверждается также наличием международных стандартов IEEE 802.8, 802.9, стандарта с явной передачей права FDDI, технологий ATM, ISDN-технологии, интеллектуальных сетей связи, предназначенных для создания информационных систем с передачей в них различных видов информации.

Объектом исследования диссертационной работы являются моноканальные интегральные локальные сети, представляющие собой

нижние уровни локальных информационно-вычислительных сетей и систем управления.

Предметом исследования являются математические модели и методы расчета моноканальных интегральных локальных Сетей.

Цель работы состоит в разработке моделей и методов расчета интегральных моноканальных локальных сетей

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

1. Разработка базовой модели моноканальной интегральной локальной сети.

2. Создание математических моделей моноканальных интегральных локальных сетей с механизмами сжатия и сеансовости непрерывной

информации, а также с различными протоколами и правилами передачи права доступа.

3. Разработка методов расчета характеристик интегральных локальных сетей.

4. Создание методов и алгоритмов выбора структуры моноканальных интегральных локальных сетей.

5. Разработка алгоритмического и программного обеспечения численного анализа интегральных локальных сетей.

Научная новизна исследований данной диссертационной работы состоит в следующем.

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

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

3. Разработана модель интегральной локальной сети со сжатием непрерывной информации со случайным числом станций НИ, представленным биномиальным распределением, с использованием аппарата условных г-преобразований.

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

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

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

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

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

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

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

Апробация результатов работы. Основные положения диссертационной работы обсуждались на III международной конференции по информационным сетям и системам ISINAS-94, 1994, С-Петербург, на 50-й научно-технической конференции ГУТ, С-Петербург, 1997, на международной конференции по информатизации и управлению 1С1&Г97, С-Петербург, на международном семинаре "Информационные сети, системы и технологии" в Ярославле, 1997, и на 51-й научно-технической конференции ГУТ, С-Петербург, 1998.

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

Объем работы. Реферируемая диссертационная работа состоит из введения, четырех разделов, заключения, списка литературы и приложений и содержит - страниц текста, 64 - рисунка, 12 - таблиц.

Основные положения, выносимые на защиту.

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

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

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

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

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

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

1.Объект и постановка задач исследования.

1.1.Алгоритмы сжатия информации

Широко распространилось в последнее время применение цифрового представления всех видов передаваемых сигналов. В связи с этим возникла возможность интеграции служб связи. Тенденция к интеграции услуг связи существует и в сфере развития локальных сетей [1,2]. В данной диссертационной работе рассматриваются интегральные локальные сети (ИЛС), представляющие собой коммуникационные системы, обеспечивающие взаимодействие средств сбора, обработки и хранения информации различных типов: данные и непрерывная информация. Все виды информации передаются в дискретном виде в пакетном режиме по цифровому каналу. Если при представлении некоторых видов информации (речи, изображения, видеоинформации) не учитывать особенности её восприятия, а также связность элементов, их частотность появления, то кодирование равномерным кодом порождает избыточность[3,4]. Поэтому для эффективного использования ресурсов сети целесообразно применять компактное представление непрерывной информации, т.е. её сжатие. Любое уменьшение кодовой последовательности в результате неравномерного кодирования реализует механизм сжатия информации.

Сжатие непрерывной информации может осуществляться на прагматическом, семантическом, синтаксическом и физическом уровне [5,6]. На прагматическом (высшем по иерархии) уровне определяется содержание и объем сообщения в целом. На семантическом уровне для экономного представления не используется та часть сообщения, которая несет дублирующие или ненужные сведения (здесь применяются определенные формы редактирования информации в широком смысле). На синтаксическом уровне сокращается статистическая и психофизическая избыточность информации. (Например: наиболее часто встречающиеся сообщения кодируем меньшей длиной). На физическом

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

В общем виде систему передачи информации с применением средств сжатия информации можно представить блок-схемой, приведенной на рис. 1.1 [5]. От источника непрерывной информации поступает аналоговый сигнал на вход устройства первичного кодирования. На выходе устройства первичного кодирования получаем дискретный сигнал, который затем подвергается сжатию в кодере источника (или устройстве сжатия). Согласование выхода кодера с каналом связи (передающей средой) осуществляется с помощью промежуточной буферной памяти (БЗУ). При приеме сигнала с канала связи также используется БЗУ, затем сигнал поступает на декодер и фильтр для распознавания и восстановления переданного сообщения.

Сокращение избыточности информации осуществляется устройством сжатия. Функционирование устройств сжатия основано на применении различных методов (алгоритмов) сжатия [3,6-10]: процедуры Хаффмана, Шеннона-Фано, кодирование длин серий, модифицированный код Хаффмана, метод потетрадного сжатия и др.

Для оценки эффективности алгоритмов сжатия [11] можно использовать.следующие коэффициенты:

Рис.1.1

- коэффициент избыточности Г|

Нт(х)-Н(х) Нт(х) '

- коэффициент сжатия р.

^ Н(х) М Нт(х)'

где Н(х) - энтропия источника сообщений. Пусть переменная х принимает значения множества X (хеХ). Множество X состоит из N однотипных элементов. Мо5кно сказать, что мощность множества X равна числу элементов в этом множестве х| = 1Ч(Х) .Тогда энтропию можно найти следующим образом Н(Х) = \og2 И(Х).

Нт(х)- максимальная энтропия достигается когда вероятность

появления символа р! ,1 = 1,М равна = 1 = 1,14, т.е. при

кодировании равномерным кодом.

Рассмотрим подробнее некоторые алгоритмы сжатия и оценим параметры сжатия [3,6,7,10].

Процедура Хаффмана основана на построении оптимальных неравномерных кодов (ОНК). Построение ОНК осуществляется следующим образом: все возможные кодовые комбинации (символы) выписываются в основной столбец в порядке убывающей вероятности их появления в сообщениях. Последние по вероятности По символов, где п0 -

ш - п

такое наибольшее число (2< п0 < а), что - - целое число, ш - число

а -1

возможных кодовых комбинаций, а - основание кода; объединяются в новый вспомогательный столбец, вероятность которого равна суммарной вероятности символов, его составляющих. Оставшиеся (ш-пр) символы и

вновь полученный символ выписываются в первый дополнительный столбец опять в порядке убывающей вероятности. Цоследние а по

вероятности символы первого дополнительного столбца опять объединяется в вспомогательный символ, (ш-п0 + 1-а) оставшихся

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

ш-п

вероятности, и т.д. до тех пор пока а оставшихся символов--го

п-1

дополнительного столбца не дадут вспомогательный символ с вероятностью 1.

Ключ построения кода: число кодовых знаков кодовой комбинации i-ro символа, записываемой справа налево (от конца), равно числу объединений, в которых участвует данный символ по пути образования вспомогательного символа с единичной вероятностью. Если

номерам символов в объединениях сопоставить а знаков (0,1 .....(а-1)), то

значения N-ro кодового знака, отсчитываемого от конца кодовой комбинации, определяется номером, занимаемым данным символом (или вспомогательным символом, в образовании которого он участвовал) в его N-ом объединении от начала построения. Пример построения ОНК приведен в таблице 1.1. Исследования по применению кода Хаффмана к сжатию программ позволили получить уплотнение в диапазоне 1,5-1,6 для готовых программ и 2,2-4 для программ на исходном языке [3].

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

0000000000 111111 0000 111111111 000000 1111111111

10 6 4 9 6 10 Всего 45 символов

Количеству одинаковых знаков в серии ставится в соответст�