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

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

Мохаммед Мокред Наджи Сайд

АДАПТИВНАЯ ПОШАГОВАЯ МАРШРУТИЗАЦИЯ НА ОСНОВЕ ЛОГИЧЕСКОЙ НЕЙРОННОЙ СЕТИ В БЕСПРОВОДНОЙ ТЕЛЕКОММУНИКАЦИОННОЙ ТРАНСПОРТНОЙ СИСТЕМЕ

Специальность 05.13.01-Системный анализ, управление и обработка информации (транспорт)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

12 ДЕК 2013

005543502

МОСКВА-2013

005543502

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

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

Барский Аркадий Бенционович

Официальные оппоненты:

Сидоренко Валентина Геннадьевна, доктор технических наук, профессор, кафедра "Управление и информатика в технических системах" федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Московский государственный университет путей сообщения», профессор.

Жданов Владимир Сергеевич, доктор технических наук, профессор, кафедра «Вычислительные системы и сети» федеральное государственное автономное образовательное учреждение высшего профессионального образования "Московский институт электроники и математики национального исследовательского университета" «Высшая школа экономики» (МИЭМ НИУ ВШЭ), профессор.

Ведущая организация: Научно- исследовательский и проектно - конструкторский институт информатизации, автоматизации и связи на железнодорожном транспорте, ОАО «НИИАС».

Защита состоится «23» декабря 2013 г., в 14.00 часов на заседании диссертационного совета Д 218.005.07 на базе федерального государственного бюджетного образовательного учреждении высшего профессионального образования «Московский государственный университет путей сообщения» по адресу: 127994, г. Москва, ул. Образцова, д. 9, стр. 9, ауд. 2505.

С диссертацией можно ознакомиться в библиотеке МГУ ПС (МИИТ). Автореферат разослан «22» ноября 2013 г.

Ученый секретарь диссертационного совета, доктор технических наук, профессор

Горелик Александр Владимирович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Особое распространение и важные перспективы обрели технологии Wi-Fi. Они активно внедряются на всех видах транспорта: на железнодорожном транспорте и метрополитене, на авиационном, морском и даже личном транспорте. В средствах массовой информации обсуждается испытание и применение технологии Wi-Fi на железнодорожном экспрессе «Москва -Адлер», обслуживающем Олимпиаду в Сочи. В Европейском Союзе в условиях большой популярности высокоскоростного железнодорожного транспорта больше всего проектов связано именно с этой технологией.

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

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

• взаимодействие абонентов-пользователей и узлов сети;

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

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

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

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

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

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

Теории и методы, лежащие в основе исследования. Основной теорией, положенной в основу построения метода управления маршрутизацией и

алгоритма альтернативного смещения, является теория логических нейронных сетей. Активно использованы:

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

связи;

• теория и практика компьютерных сетей, алгоритмы управления маршрутизацией, использованные в существующих протоколах;

• теория и практика моделирования;

• методы параллельной обработки информации;

• среда моделирования Borland Pascal.

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

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

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

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

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

Научная новизна диссертационного исследования заключается в следующимем:

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

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

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

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

4. В исследованной области алгоритм альтернативной маршрутизации обес-печивает среднее время выполнения заявок и вероятность их выполнения на 7 — 10% лучше, чем алгоритм безальтернативной маршрутизации. Алгоритм альтернативной маршрутизации способен не менее чем на 7% увеличить пропускную способность сети.

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

Тема диссертации разработана полностью.

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

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

Публикации. По теме диссертации опубликовано 6 печатных работ, из них две - в журнале из списка ВАК, две опубликованы в трудах международных конференций, две работы - в трудах конференций «Неделя науки» в МИИТ.

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

Рисунок 1- Беспроводная телекоммуникационная транспортная система

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

Рисунок 2 - Формализованная структура компьютерной сети, управляющей беспроводной телекоммуникационной транспортной системой Возможны два подхода к решению задачи адаптивной маршрутизации: 1. Традиционный подход предполагает, что весь маршрут планируется заранее, до его выполнения. Его оптимизация производится по статистическим данным о загрузке узлов следования. При реализации такого заранее заданного маршрута смещение заявки в смежный узел производится без выбора альтернативы (безальтернативное смещение).

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

Первый подход полно отображён в работах Д.В. Иванова, выполненных в МИИТ, и широко освещен в литературе. Результаты работы Д.В. Иванова можно связать с результатами работ Б.В. Желенкова и Сан Вин Аунга, посвященных проблеме прогнозирования трафика в компьютерной сети.

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

1. Минимизация среднего времени выполнения запроса на передачу информационного пакета от узла-отправителя к узлу-получателю:

Тейп ->min (1)

2. Минимизация количества отказов в выполнении заявок:

потк ->min (2)

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

Рот* ~ noimc /п min (3)

Важным критерием, определяющим максимальную пропускную способность сети, является требуемая вероятность Р = 1 - Ротк обслуживания заявки:

Р>Ро, (4)

где Ро задаётся техническими требованиями на разработку (3) Алгоритм альтернативного смещения построен на основе аппарата логических нейронных сетей, разработанного А.Б. Барским (Рисунок 3). Функция активации нейронов этой сети:

у= ,У=

V, У> и

(5)

[О, V < к

В данном случае эта функция имеет вид:

У;=УА Щ-Ь, (6)

если эта разность превышает порог Л, 0 в противном случае (порог выбирается

экспериментально). Здесь К/ значение возбуждения нейрона / (г=1, ..., М), щ -вес /-го узла смещения из узла /, А, - коэффициент загрузки буфера /-го узла, УА - запрос по адресу А. Предпочтительные адреса смещения выбираются на основе целесообразности. Матрица следования, отображающая этот фрагмент логичес-кой нейронной сети и используемая для расчётов, имеет вид, представленный в Таблице 1.

Буферы смежных узлов

Рисунок 3- Фрагмент логической нейронной сети, размещённой на узловом компьютере, и её связей

Таблица 1

Матрица следования фрагмента нейронной сети выбора смежного узла смещения кадра

Узел назначения А Смежные узлы

1 2 N

Веса предпочтительного смещения Юл 1 в>А2 G>AN

Веса обратных связей -кх -кг -кц

Решение сом-к^

Решение /?2 (0л2-кг

Решение (О АН-км

Выбор решения Л о направлении смещения определяется значением тах{(0А1- к„ акц}, УА= 1.

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

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

Рисунок 4- Простейшая телекоммуникационная (компьютерная) сеть с указанием смежности узлов

ЪЛврщруг 5 1

МврИ£ут4 - ^ 1 ■ , Маршрут2 -»4

Меры^ут 1 5

Рисунок 5- Оптимизированная безальтернативная маршрутизация «сквозных»

запросов

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

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

На Рисунке. 6 показано информационное взаимодействие функциональных блоков модели. Как в каждой сложной системе, время работы модели условно тактируется. Такт определяется основными циклами обработки информации. В «малом» такте производится анализ (с помощью цикла по всем компьютерам) регистров с одинаковым номером всех буферов узловых компьютеров (БУК). Такая обработка на не параллельном моделирующем компьютере в наибольшей степени отображает параллельную работу буферов. В «большом» такте, реализующем циклическое выполнение работ малого такта по всем регистрам буферов, производится анализ и изменение (включая продвижение заявок) состояния всех буферов узловых компьютеров. Важным информационным источником для каждого узлового компьютера является набор таблиц выбора смещения (TBC), представляющих собой частично заполненную форму. TBC вызывается на основании указанного в ней адреса назначения. Первоначально в TBC отображены только предпочтения при этом смещении. Окончательный выбор (окончательное заполнение формы) производится на основе значений коэффициента загрузки БУК, приходящих от смежных компьютеров.

Буфер «внешних» _заявок •_

е Адрес назначения

.....'ОС

С С Р - си т о к свой«доп регистров

БПЗ — буфер

прамгжі ІО'ІМОЙ

затее»

рг Лзрес отправ.г Адрес назияч. Тшік

ц - 2

Шб 8 3 4

Ц Свободен

Г ■ ЬУК Ї

Л* регистр ж Заявка

5 ТВС -Тк&гапы выбора сминекни ; Та&ияды — г^итрвхда>£ следовлки* <6« I значений коэффициентов загр^ьки) ' фря-т^еитов лсгшсско» нейронной СеТИ, I каждый из которвгх отображает один : лоя^зжный адрес нвначения, кроме * емвкиыя узлов.

Рисунок 6 - Информационное взаимодействие блоков модели

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

Используем два обращения к дачику случайных чисел (ДСЧ) для каждй из 5 числа заявок в такте. Получим два случайных числа щ и а2, обозначающих пару «А (адрес отправления) - В (адрес назначения)»:

А = [с^хл], В = [а2х«] (7)

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

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

заявок высокой интенсивности, исходящих из области узла А. Интенсивность «потребления» также соответствует нормальному закону распределения вероятностей по узлам области В.

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

Упорядочим и пронумеруем последовательности:

А = {А,,А2> •-•.А-} (8)

/= { 0,1.....[0,5г]-1, [0,5г], [0,5г]+1,.... г} (9)

Найдём три случайных числа аи а2, «з (между нулём и единицей) и рассчитаем ближайший целый номер м во второй последовательности, соответствующий номеру узла А „ из первой последовательности:

и,=гх —------(10)

3

Узел А „ является узлом отправления.

Аналогично

В = {Ви В2, ..., В[0,5/], В, В{............ В,} (11)

7= { 0,1,..., [0,5/]-1, [0,5/], [0,5/]+1,..., /} (12)

Найдём три случайных числа сц, а5, о% и рассчитаем номер //у во второй последовательности, соответствующий ближайшему целому номеру узла Ву из первой последовательности.

Узел Ву является узлом назначения.

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

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

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

Рассмотрим пример построения TBC для узлового компьютера 1 при выборе смещения «сквозной» заявки, следующей к узловому компьютеру 5. Фрагмент логической нейронной сети представлен на Рисунке 7.

Буферы смежных узлов

Рисунок 7- Фрагмент логической нейронной сети для определения смещения при следовании информационного пакета от компьютера I к компьютеру 5

Матрица следования для выполнения необходимого смещения представлена в Таблице 2.

Таблица 2

Матрица следования фрагмента логической нейронной сети для передачи пакета от компьютера 1 компьютеру 5

Адрес назначения Смежные узлы

5 2 3 4

Веса предпочтительного смещения 1 0,2 0,8

Веса обратных связей -кг -кэ -Ь

Решение Ль Передать пакет узлу 2 1 - кг

Решение К-1 Передать пакет узлу 3 0,2 - к3

Решение Л3: Передать пакет узлу 4 0.8 -к4

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

Таблица предпочтительного смешения для компьютера 1

Адрес назначения Альтернативное смещение Безальтернативное смещение

Смежные компьютеры Смежные компьютеры

2 3 4 2 3 4

5 1 0,2 0,8 1

6 0,1 1 0,2 1

7, 10,11 1 1 1

8 0,8 0,5 1 1

9 1 1 1

12 0,8 0,5 1 1

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

Для исследований выбраны два типа сценариев поступления «сквозных» заявок: одинаковой интенсивности в каждом такте (Таблица 4) и нарастающей

интенсивности (Таблица 5).

Таблица 4

Сценарий с постоянной интенсивностью потока заявок

Такты Заявки на передачу

0 У\ = (3-> 9), v2 = (1->11), v3 = (5->6), г< = (9->3), vs = (5->10), v6 = (2->11), V-, = (6->12),v8 = (11->2), v9 = (6 -»5), v,0 = (12 ->3), v„ =• (10 -> 2), vu = (12->1),

1 Vu = (2—>10), vI4 = (1->12), vis = (3—>9), v,6 = (6->5), v17 = (10->2), vw = (12->3), Vl9 = (12—>3), V20 = (9->3), V2| = (1->U), V22 = (9->6), V23 = (5 ->10), V24 = (10->5),

2 K25 = (1->12), V26 = (5->10), V27= (12—>3), v28 = (11—>2), V29 = (12->2), v30 = (9->6), v31 = (9->10), v32 = (1->11), v33 = (1->11) v34 = (10->5), v35 = (9->l), v36 = (2->l 1),

8 K97 = (1 ->11), V98 = (2 ->12), V99 = (3 ->12), v100 = (12 -> 1), v,oi = (10 -> 1), V102 = (l-> 1 l)»vjo3 = (5 ->10), v,o4 = (1 ->11), vios = (12 ->3), vI06 = (11->2), VIO7 = (3->12), V,08 = (I1 ->2),

9 Vio9 = (l-> И), V] 10 = (2 -> 12), vin = (5 -> 10), V112 = (1 -> 12), vil3 = (9 -> 6), VU4 = (6 -> 2), Viu = (3 -> 12), v„6 = (11 -> 2), VM7 = (12 -> 3), v„8 = (11 -> 2), Vl 19 = (3 -> 12), Vl20=(ll->2),

Сценарий поступления заявок с нарастающей интенсивностью

Такты Заявки на передачу

0 vi = (10-»2), v2 = (1—>12), уз = (11-»1), V4 = (1->10), v5 = (12-»2), v6 = (9 -» 6), V, = (12 -»3), vg = (10-» 9), v, = (12 -» 6), v10 = (1 -» 11),

1 vu = (12—>3), viz = (11 ->1), vj3 = (2 ->10), Ун = (5-»6), vis = (l-»5), v,6 = (5-й), Vir = (4-»2), v,8 = (2-»4), Vi, = (l-> 5), v20 = (5-»l), v2i = (2->4), vn = (4-»2),

2 V23 - (6—>9), V24 = (1-И2), vM = (ll-»2), v26 = (5->6), v27 = (2 -»11), v28 = (1-»12), \>29 = (1l-»2), v30 = (2-» 10), V3i = (5-»6), v32 = (l-»l 1), v33 = (І2-»3), v34 = (10 -»1), V35= (12 2), V36 = (11 3),

7 vii3 = (12 -» 2), V114 = (6 -»5), vus = (10 -» 1), vus=(12 -> 1), vU7 = (l-> 12), vm = (2-> 11), vM9=(l-> 11), V,20 = (2-» 10), V121 = (1l-»2), V122 = (12-» 1), V123 = (10 -» 2), V124 = (9 -» 3), V,25 = (6 -> 5), V126 = (2-» 10), V,27 = (1-» 12), V128 = (12-» 2), v,29 = (10 -» 1), v,30 = (12 -» 1), V,31 = (1 -» 10), V,32 = (9 -» 3), V133 = (3 -» 12), V134 = (12-» 2), vus = (12 -» 2), vi36 = (6 -» 5).

Очевидно, минимальное время выполнения заявки (в тактах) равно длине кратчайшего пути от адреса отправления до адреса назначения, если в каждом такте производится её смещение, увеличенной на единицу за счёт такта поступления. Следовательно, при анализе альтернативного и безальтернативного алгоритмов управления маршрутизацией необходимо исследовать среднее превышение действительного времени выполнения заявок по сравнению с минимально возможным временем. На Рисунке 8 приведены графики зависимости среднего времени Твып выполнения заявок от их интенсивности 5 поступления на исследуемую сеть. Графики составлены для вариантов применения алгоритма альтернативного смещения и для безальтернативного смещения. Зависимости получены на основе анализа пяти сценариев при л = 12 (приведён выше), 13,14,15, 16 для размера буфера N = 6.

Рисунок 8 - Зависимость времени выполнения заявки от интенсивности потока для альтернативного и безальтернативного алгоритмов смещения

Анализ графиков показывает:

1. Превышение среднего времени выполнения заявок при применении алгоритма альтернативного смещения ЛТшьт над минимально возможным временем, для диапазона изменения 12 < і < 16, меняется в пределах

2. Превышение среднего времени выполнения заявок при применении алгоритма безальтернативного смещения АТ^^т над минимально возможным временем, для того же диапазона изменения л изменяется в пределах

О, 6 < АТбезтьт ^ 2,2.

3. Таким образом, при выбранных исходных данных моделирования альтернативное смещение заявок, стремящееся продвинуть заявку в направлении адреса назначения по менее загруженным буферам (с учётом предпочтительного смещения), за счёт снижения времени разрешения конфликтов позволяет существенно снизить среднее время выполнения заявки. По сравнению с алгоритмом безальтернативного смещения это время снижается от 8% - для 5 = 12, до 23% - для і = 16.

Рисунок 9 - Зависимость вероятности выполнения заявок ог интенсивности потока для альтернативного и безальтернативного алгоритмов смещения

На Рисунке 9 приведены графики зависимости вероятности выполнения заявок для тех же значений 5 интенсивности потока заявок, отображённых в сценариях. Графики построены на основе отношения количества выполненных к общему количеству заявок, отображённых в сценарии.

Анализ графиков показывает:

1. Конфликты на буферах, связанные с их переполнением, приводят к существенным задержкам продвижения заявок. Задержки времени, превышающие допустимые, приводят к снятию заявок с обслуживания. Эти конфликты приводят к отказам в обслуживании заявок, поступающих извне.

2. Алгоритм альтернативного смещения демонстрирует более высокую «сопротивляемость» перегрузкам буферов попутных компьютеров, в своём постоянном стремлении уравнять загрузку смежных узловых компьютеров. Это приводит к повышению соответствия требованиям технического задания. Так, например, на графике указан требуемый уровень вероятности выполнения заявок, равный 0,9. Видно, что при безальтернативном смещении этот уровень ещё достижим при .у = 14. Алгоритм альтернативного смещения обеспечивает этот уровень при 15. Это на 7% увеличивает пропускную способность сети 5/. с учётом данного ограничения.

Рисунок 10 - Зависимость времени выполнения заявок от нарастающей интенсивности их потока

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

На Рисунке 10 приведены графики зависимости среднего времени выполнения заявок в рамках одного сценария при изменяющемся по тактам значении л от 10 до 24. Отражено среднее время выполнения заявок, поступивших в каждом такте. Однако из-за резкого роста времени выполнения и интенсивного снятия с обслуживания графики ограничены рассмотрением значения= 20.

При значении / = 5, соответствующем значению .V = 20, наращивать поток заявок (увеличивать значение я) нет смысла из-за принятых в моделируемых алгоритмах значений допустимого (накапливаемого) времени выполнения заявок. Если считать, что это время равно 2Тт,„, то до заявок 6-го такта при применении альтернативного алгоритма дело просто не дойдёт: все буфера будут переполнены. Ведь все вновь поступающие заявки выполняются на фоне уже обрабатываемых. В данном случае поток, определяемый значением 5=18, определяет максимальную пропускную способность по времени выполнения.

Для безальтернативного алгоритма смещения недоступен уже 4-й такт. То есть его пропускная способность определяется значением 5=17.

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

Рисунок 11 - Зависимость вероятности выполнения заявок от нарастающей интенсивности их потока

Если вероятность выполнения заявки ограничена в технических задании (ТЗ) величиной 0,9, то при данных условиях моделирования для алгоритма безальтернативного смещения это значение достигается при л = 12. Применение алгоритма альтернативного смещения позволяет достичь этого ограничения при £ = 14. Таким образом, пропускная способность сети 5> увеличивается на 14%.

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

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

ЗАКЛЮЧЕНИЕ. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЙ

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

Обосновано применение метода адаптивной пошаговой маршрутизации в беспроводной телекоммуникационной транспортной сети.

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

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

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

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

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

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

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

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

7.2. Сравнительная оценка вероятности выполнения заявок показала, что алгоритм альтернативного смещения демонстрирует более высокую «сопротивляемость» перегрузкам буферов попутных компьютеров. Так, например, при требуемом уровне вероятности выполнения заявок, равном 0,9, оказывается, что при безальтернативном смещении этот уровень ещё достижим при интенсивности 14 заявок в такте. Алгоритм альтернативного смещения обеспечивает этот уровень при 15 заявок в такте. Это на 7% увеличивает пропускную способность сети с учётом данного ограничения.

7.3. Анализ сценариев с нарастающей интенсивностью потока заявок показывает резкий рост среднего времени выполнения заявок, сопровождающийся резким снижением вероятности их выполнения. В частности, если вероятность выполнения заявки ограничена (в ТЗ) величиной 0,9, то при данных условиях моделирования для алгоритма безальтернативного смещения это значение достигается при интенсивности 12 заявок в такте. Применение алгоритма альтернативного смещения позволяет достичь ограничения при интенсивности 14 заявок в такте. Таким образом, пропускная способность сети увеличивается на 14%.

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

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

региона) элементарными подструктурами беспроводной телекоммуникационной транспортной сети с двухуровневым отношением смежности узлов.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных вак россия:

1. Сайд Мохаммед, М. Н. Технология Wi-Fi и логика нейросети / М. Н. Сайд Мохаммед // Мир Транспорта, - М.: №2, 2011. с. 112 - 115.

2. Сайд Мохаммед, М. Н. Выбор смещения при пошаговой маршрутизации в беспроводной сети / М. Н. Сайд Мохаммед, А. Б. Барский // Мир Транспорта, - М.: №2,2013. с. 30 - 37.

Публикации в других изданиях:

3. Мохаммед, М. Н. С. Оценка алгоритма пошаговой альтернативной маршрутизации в беспроводной телекоммуникационной сети / М. Н. С. Мохаммед // Труды научно - практической конференции Неделя науки - 2013 «Наука МИИТа - транспорту». - М.: МГУПС(МИИТ), 2013. - IV- 38. - ISBN 978-5-7876-0215-9.

4. Сайд Мохаммед, М. Н. Альтернативный алгоритм маршрутизации данных в Wi-Fi системах / М. Н. Сайд Мохаммед // Труды научно -практической конференции Неделя науки - 2011 «Наука МИИТа -транспорту». - М.: МИИТ, 2011. - IV- 5. - ISBN 978-5-7876-0202-9.

5. Сайд Мохаммед, М. Н. Адаптивная динамическая маршрутизация в телекоммуникационных системах беспроводной связи / М. Н. Сайд Мохаммед //1 международной научной конференции "современное общество: проблемы, идеи, инновации" Ставрополь.: Логос, 2012. -с.80-83. - ISBN 978-5-905519-01-7.

6. Сайд Мохаммед, М. Н. Обоснование выбора предпочтений при альтернативной динамической пошаговой маршрутизации и возможности её развития / М. Н. Сайд Мохаммед // Перспективы развития информационных технологий: сборник материалов X Международной научно-практической конференции / Под общ. ред. С.С. Чернова. - Новосибирск: Издательство НГТУ, 2012. - с. BIDS.- ISBN 978-5-7782-2131-4.

Мохаммед Мокред Наджи Сайд

АДАПТИВНАЯ ПОШАГОВАЯ МАРШРУТИЗАЦИЯ НА ОСНОВЕ ЛОГИЧЕСКОЙ НЕЙРОННОЙ СЕТИ В БЕСПРОВОДНОЙ ТЕЛЕКОММУНИКАЦИОННОЙ ТРАНСПОРТНОЙ СИСТЕМЕ

05.13.01- Системный анализ, управление и обработка информации (транспорт)

Автореферат диссертации на соискание ученой степени кандидата технических наук

Подписано к печати 10.Л. 15, Формат 60x90 1/16

Заказ № %01 Объем 1,5 пл._Тираж 80 экз.

УПЦ ГИ МИИТ, Москва, 127994, ул Образцова, д 9, стр. 9

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ

СООБЩЕНИЯ» (МГУПС(МИИТ))

АДАПТИВНАЯ ПОШАГОВАЯ МАРШРУТИЗАЦИЯ НА ОСНОВЕ ЛОГИЧЕСКОЙ НЕЙРОННОЙ СЕТИ В БЕСПРОВОДНОЙ ТЕЛЕКОММУНИКАЦИОННОЙ ТРАНСПОРТНОЙ СИСТЕМЕ

Системный анализ, управление и обработка информации (транспорт)

04201451606

МОХАММЕД МОКРЕД НАДЖИ САИД

Специальность 05.13.01-

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата технических наук

Научный руководитель: доктор технических наук, профессор Барский Аркадий Бенционович

МОСКВА -2013

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ....................................................................................................................4

ГЛАВА 1. ПРИНЦИПЫ АДАПТИВНОЙ ПОШАГОВОЙ МАРШРУТИЗАЦИИ. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЙ...........................................................8

1.1. Абстрактная модель беспроводной телекоммуникационной транспортной сети и критерии эффективности адаптивной маршрутизации.....................8

1.2. Компьютерная сеть в основе управления телекоммуникационной транспортной системой беспроводной связи...........................................................12

1.3. Элементы адаптации в современных сетевых коммутаторах................15

1.4. Периодическая статическая адаптация маршрутов следования информационных пакетов в беспроводной телекоммуникационной транспортной сети.... 18

1.5. Адаптивная пошаговая маршрутизация на основе альтернативного выбора смещения информационного пакета в смежный узел................................22

Выводы по главе 1....................................................................................................27

Г ЛАВА 2. АЛГОРИТМ АЛЬТЕРНАТИВНОЙ ДИНАМИЧЕСКОЙ ПОШАГОВОЙ МАРШРУТИЗАЦИИ В КОМПЬЮТЕРНОЙ СЕТИ, УПРАВЛЯЮЩЕЙ БЕСПРОВОДНОЙ ТЕЛЕКОММУНИКАЦИОННОЙ ТРАНСПОРТНОЙ СИСТЕМОЙ..................................................................................................................29

2.1. Адаптивная маршрутизация по смежным узлам на основе логической нейронной сети с обратными связями.......................................................................29

2.2. Исследование элементарной подструктуры компьютерной сети, использующей альтернативную маршрутизацию............................................................36

2.3. Использование безальтернативной маршрутизации...............................58

Выводы по главе 2....................................................................................................64

ГЛАВА 3. МОДЕЛЬ КОМПЬЮТЕРНОЙ СЕТИ УПРАВЛЕНИЯ БЕСПРОВОДНОЙ ТЕЛЕКОММУНИКАЦИОННОЙ ТРАНСПОРТНОЙ СИСТЕМОЙ С ПРИМЕНЕНИЕМ МЕТОДА АЛЬТЕРНАТИВНОЙ

МАРШРУТИЗАЦИИ....................................................................................................65

3.1. Обоснование метода моделирования и выбор критериев эффективности .............................................................................................................................65

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

3.3. Алгоритм модели........................................................................................72

3.4. Алгоритмы формирования сценариев поступления заявок...................79

3.4.1. Алгоритм формирования сценариев с равновероятным выбором адресов отправления и назначения............................................................................79

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

Выводы по главе 3.....................................................................................................83

ГЛАВА 4. ОЦЕНКА ЭФФЕКТИВНОСТИ АДАПТИВНОГО АЛГОРИТМА АЛЬТЕРНАТИВНОЙ ПОШАГОВОЙ МАРШРУТИЗАЦИИ.................................85

4.1. Выбор структуры компьютерной сети для моделирования....................85

4.2. Обоснование сценариев поступления заявок............................................96

4.3. Сравнительная оценка эффективности применения алгоритмов альтернативной и безальтернативной пошаговой маршрутизации в компьютерной сети, управляющей беспроводной телекоммуникационной транспортной системой ..102

4.4. Модель компьютерной сети, управляющей беспроводной телекоммуникационной транспортной системой, - инструментальное средство проектирования

...................................................................................................................................... 108

Выводы по главе 4.....................................................................................................110

ЗАКЛЮЧЕНИЕ...........................................................................................................113

CI < ИСОК СОКРАЩЕНИЙ.......................................................................................118

СПИСОК ЛИТЕРАТУРЫ..........................................................................................119

ПРИЛОЖЕНИЕ..........................................................................................................126

ВВЕДЕНИЕ

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

Особое распространение и важные перспективы обрели технологии Wi-Fi [12,13,58,62]. Они активно внедряются на всех видах транспорта: на железнодорожном транспорте и метрополитене, на авиационном, морском и даже личном транспорте. В средствах массовой информации обсуждается испытание и применение технологии Wi-Fi на железнодорожном экспрессе «Москва - Адлер», обслуживающем Олимпиаду в Сочи. В Европейском Союзе в условиях большой популярности высокоскоростного железнодорожного транспорта больше всего проектов связано именно с этой технологией.

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

Рассматривая классическую схему системы сотовой связи, какой является беспроводная телекоммуникационная сеть [12,13,18,44], состоящей из сети стационарных узлов и переменных (вследствие движения) множеств абонентов, связанных с каждым узлом, можно выделить две проблемы, присущие системе в целом:

• взаимодействие абонентов-пользователей и узлов сети;

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

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

Решению этой задачи посвящена данная работа.

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

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

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

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

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

• теория построения беспроводных тетекоммуникационных систем связи;

• теория и практика компьютерных сетей, алгоритмы управления маршрутизацией, использованные в существующих протоколах;

• теория и практика моделирования;

• методы параллельной обработки информации;

• среда моделирования Borland Pascal.

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

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

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

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

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

Научная новизна работы:

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

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

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

4. В исследованной области алгоритм альтернативной маршрутизации обеспечивает среднее время выполнения заявок и вероятность их выполнения на 7 -10% лучше, чем алгоритм безальтернативной маршрутизации. Алгоритм альтернативной маршрутизации способен не менее чем на 7% увеличить пропускную способность сети.

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

Тема диссертации разработана полностью.

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

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

Публикации. По теме диссертации опубликовано 6 печатных работ, из них две - в журнале из списка ВАК, две опубликованы в трудах международных конференций, две работы - в трудах конференций «Неделя науки» в МИИТ.

ГЛАВА 1. ПРИНЦИПЫ АДАПТИВНОЙ ПОШАГОВОЙ МАРШРУТИЗАЦИИ. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЙ

1.1. Абстрактная модель беспроводной телекоммуникационной транспортной сети и критерии эффективности адаптивной

маршрутизации

Беспроводная телекоммуникационная транспортная сеть [44,45] представляет собой ячеистую (сотовую) структуру. Основой ячейки является ст&ционарный узел (Рисунок 1.1). Узлы автоматически устанавливают и поддерживают каналы связи, совместно создавая одноранговую архитектуру (Рисунок 1.2) [54]. Мобильные станции абонентов, находясь в зоне достижимости (устойчивого сигнала!) беспроводного канала связи узла (радиосвязи), обмениваются информационными пакетами с этим узлом для дальнейшей передачи абонентам в рамках всей сети.

Рисунок 1.1- Ячейка беспроводной телекоммуникационной транспортной сети на

базе узла

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

Рисунок 1.2- Телекоммуникационн :я беспроводная транспортная сеть, покрывающая ограниченную территорию (станции показаны частично)

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

Так как узлы образуют одноранговую сеть, то исключительно важную роль играет маршрутизация потоков информационных пакетов от узлов абонентов-отправителей к узлам абонентов-получателей [42,43]. Средства и алгоритмы (протоколы) такой маршрутизации определяют качество обслуживания, надёжность и быстродействие телекоммуникационной сети.

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

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

Рассматривая функцию маршрутизации в телекоммуникационной сети абстрактно и учитывая, что в беспроводной сети используется радиосвязь для передачи пакетов по смежным узлам, следует выделить основные свойства и требования к адаптированному маршрутизатору: он должен быть динамическим, распределённым и пошаговым [51,53]. Это означает следующее:

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

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

3. Каждый информационный пакет подвергается пошаговой маршрутизации, при которой каждый «попутный» узел производит его передачу

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

В основе адаптации маршрутизатора к текущему трафику сети лежат следующие критерии оптимизации:

1. Минимизация среднего времени выполнения запроса на передачу информационного пакета от узла-|отправителя к узлу-получателю."

Твып ~> тж в (1.1)

2. Минимизация количества отказов в выполнении заявок - как на входе, так и в процессе их выполнения?

потк->тт, (1-2)^

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

Ротк = П0тк /п тт , (1.3) ^

Важным критерием, определяющим максимальную пропускную способность сети, является требуемая вероятность Р = 1 - Ротк обслуживания заявки:

Р>Ро, (1.4)

где Ро задаётся техническими требованиями на разработку.

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

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