close

Вход

Забыли?

вход по аккаунту

?

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

код для вставкиСкачать
Новые технологии
Литература
1. Oracle Method. Application Implementation Method (AIM) 3.0 Handbook.
2. Oracle Method. Application Implementation Process and Task Reference.
3. Oracle CIS. – http://www.oracle.com/global/ru/corporate/index.html (дата обращения 18.10.2010).
4. Microsoft Dynamics. – http://www.microsoft.com/Rus/dynamics/about/overview.mspx (дата обращения
18.10.2010).
5. SAP: delivering it-powered business innovation. http://www.sap.com/about/index.epx (дата обращения
18.10.2010).
6. Руководство к своду знаний по управлению проектами (Руководство РМВОК): Американский
национальный стандарт ANSI/PMI 99-001-2004. 3-е изд. – USA: Project Management Institute, 2004. 389 с.
7. Репин В. В., Елиферов В. Г. Процессный подход к управлению. Моделирование бизнес-процессов.
– М.: Стандарты и качество, 2005. 1136 с.
8. Дмитриев О. Н. Системный анализ в управлении. 4-е изд. – М.: Доброе слово, 2003.
9. Кале В. Внедрение SAP R/3: Руководство для менеджеров и инженеров. – М.: Компания АйТи,
2006. – 511с.
УДК 004.7
РЕШЕНИЕ ЗАДАЧИ ВЫБОРА ПРЕДПОЧТИТЕЛЬНОГО
ПРОТОКОЛА МАРШРУТИЗАЦИИ В ADHOC-СЕТЯХ НА ОСНОВЕ
ИСПОЛЬЗОВАНИЯ АППАРАТА НЕЙРОННЫХ СЕТЕЙ
А. Шаваша, аспирант
Тел.: (926) 220-83-01, e-mail: alaan@inbox.ru
Московский государственный университет экономики, статистики и информатики
(МЭСИ)
http://www.mesi.ru
The paper proposes a method for selecting the preferred protocol wireless AdHoc- networks using the mathematical tools of neural networks for the given parameters: mobility
of nodes, number of nodes and network classes of user tasks that are loaded at the nodes of
the network.
В статье предложена методика выбора наиболее предпочтительного протокола беспроводной
AdHoc-сети с использованием математического аппарата нейронных сетей при заданных параметрах:
мобильности узлов, числа узлов и классов сетевых пользовательских задач, загруженных на узлах сети.
Ключевые слова: протоколы маршрутизации, моделирование протоколов, надежность, задержка
доставки пакетов, пропускная способность сети, нейронная сеть.
Keywords: routing reports, modeling of reports, reliability, delay of delivery of packages, throughput of
network, neural network
Введение
В настоящее время активно развиваются беспроводные сети передачи данных. Одним из классов таких сетей являются беспроводные AdHoc-сети, которые имеют переменную топологию, где каждый узел может выполнять функции маршрутизатора.
Подобные сети могут применяться в органах
государственного управления, организации
сетей для служб быстрого реагирования и
др. Существующие на данный момент протоколы маршрутизации AdHoc-сетей можно
классифицировать по принципу работы на
три типа [1]: проактивные (DSDV, OLSR),
Открытое образование •6/2011
реактивные (AODV, DSR) и гибридные
(HRPLS, ZRP).
Проактивные
протоколы периодически рассылают по сети служебные сообщения с информацией обо всех изменениях в ее топологии. В результате каждый узел
сети на основе
данной информа-
59
Новые технологии
ции строит маршруты до всех остальных узлов и сохраняет их в таблице маршрутизации. Эта информация используется в дальнейшем при необходимости передачи сообщения какому-либо адресату.
Реактивные, или работающие по запросу (англ. reactive, on-demand), протоколы
составляют маршруты до конкретных узлов
лишь при возникновении необходимости в
передаче им информации. Для этого узелотправитель широковещательно рассылает
по сети сообщение-запрос, которое должно
дойти до узла-адресата. В ответ адресат высылает сообщение-подтверждение, из которого отправитель узнает необходимый маршрут и записывает его в свою таблицу маршрутизации. Для повторных отправок сообщений данному адресату маршрут просто
считывается из таблицы. Если обнаруживается его разрушение, то запускается так называемая процедура поддержания маршрута,
которая фактически заключается в поиске
нового маршрута до адресата.
Гибридные (англ. hybrid) протоколы
комбинируют механизмы проактивных и
реактивных протоколов. Как правило, они
разбивают сеть на множество подсетей,
внутри которых функционирует проактивный протокол, а взаимодействие между ними осуществляется с помощью реактивных
протоколов.
В статье представлена методика выбора
наиболее предпочтительного протокола AdHoc-сети. Так как мобильность узлов и пользовательская нагрузка AdHoc-сетей могут
меняться с течением времени, то и выбор
предпочтительного протокола должен осуществляться с учетом этим изменений.
Пользовательская нагрузка зависит от сетевых задач, выполняемых в узлах сети. Предполагается, что оборудование, поддерживающее работу AdHoc-сети, может работать
под управлением разных протоколов: AODV
(AdHoc On-Demand Distance Vector), DSR
(Dynamic Source Routing), DSDV (DestinationSequenced Distance-Vector Routing) – и динамически переключаться с одного протокола
на другой.
Рассмотрим следующие классы сетевых
задач [2]:
1. Организация электронной почты, передача файлов, веб-доступ.
2. Организация удаленного доступа.
3. Передача аудио- и видеофайлов по
запросу.
4. Организация телефонии, видеоконференции.
Считаем, что на узлах сети решаются
задачи только выбранных классов. Эффективность решения указных задач зависит от
следующих показателей [2]: надежность доставки пакетов, задержка доставки пакетов,
флуктуация задержки доставки пакетов,
пропускная способность сети. В совокупности эти показатели характеризуют качество
обслуживания сети (Quality of Service).
Ниже приведена таблица чувствительности классов сетевых пользовательских задач к этим параметрам. Чувствительность
может оцениваться цифрами от 1 до 3 (1 –
низкая чувствительность, 2 – средняя, 3 –
высокая).
Таблица
Чувствительность классов сетевых пользовательских задач к параметрам сети
№
класса
Пользовательские задачи класса
Надежность
Задержка
Флуктуации
Пропускная
способность
1
Электронная почта, передача файлов, веб-доступ
3
1
1
1–2
2
Удаленный доступ
3
2
2
2
3
Передача аудио, видео в режиме
реального времени
1
1
3
2–3
4
Телефония, видеоконференция
1
3
3
1–3
Из таблицы видно, что такие сетевые
задачи, как организация электронной почты,
передача файлов, веб-доступ, организация
удаленного доступа, предъявляют высокие
требования только к показателю надежности
доставки пакетов. Если пакет во время передачи был искажен, то он высылается снова.
К остальным показателям указанные задачи
малочувствительны.
60
В [3] в результате моделирования протоколов AODV, DSR, DSDV показано, что:
1. При высокой мобильности (скорости
перемещения) узлов протокол DSR имеет
лучшие значения показателей (число удаленных пакетов, среднее время доставки пакетов) по сравнению с протоколом DSDV.
2. При увеличении числа узлов протокол DSDV имеет лучшие значения тех же
Открытое образование •6/2011
Новые технологии
показателей по сравнению с протоколами
DSR и AODV.
3. Для сетевых задач, работающих в
режиме реального времени, протокол AODV
является более предпочтительным, чем протоколы DSR и DSDV, т. к. при увеличении
числа узлов время доставки пакетов в сети
при использовании протокола AODV мало
изменяется, а указанные сетевые задачи чувствительны к флуктуациям времени доставки пакетов.
4. Для сетей с малым числом узлов и
низкой мобильностью протокол DSDV более
эффективен, чем протоколы DSR и AODV.
Таким образом, можно сделать следующие выводы:
1. Если преобладающим классом сетевых задач в узлах сети является третий или
четвертый (см. таблицу), то при любом числе узлов и мобильности предпочтение необходимо отдать протоколу AODV.
2. Если номер преобладающего класса
сетевых задач в узлах сети не третий и не
четвертый, а число узлов и средняя мобильность малы, то предпочтительным является
протокол DSDV.
3. Если номер преобладающего класса
сетевых задач в узлах сети не третий и не
четвертый, а число узлов или средняя мобильность высоки, то предпочтительным
протоколом является DSR.
При этом под средней мобильностью
понимается среднее арифметическое мобильности всех узлов. Номер преобладающего класса рассчитывается как среднее
арифметическое номеров классов задач в
узлах сети. Для различных типов запущенных сетевых приложений на узлах сети (например, Microsoft Outlook Express) известен
номер класса задачи. При запуске нескольких сетевых задач на узле определяется
среднее арифметическое номеров запущенных сетевых задач.
При выполнении условий пункта 1
предпочтительным протоколом является
AODV. В противном случае выбор протокола
зависит от числа узлов, мобильности узлов,
номера преобладающего класса. Правила,
позволяющие точно выбрать наиболее предпочтительный протокол DSDV или DSR в
зависимости от конкретных значений числа
узлов, мобильности узлов, номера преобладающего класса, как видно из пунктов 2 и 3,
не определены. Известны отдельные примеры правильного выбора предпочтительного
протокола, полученные экспериментальным
путем для некоторых значений средней мо-
Открытое образование •6/2011
бильности узлов, числа узлов и номера преобладающего класса. Следовательно, необходимо разработать формальный математический аппарат, позволяющий выбрать
предпочтительный протокол для различных
значений мобильности, числа узлов и номера
преобладающего класса задач. В качестве
такого аппарата обосновано применение
нейронных сетей.
Для решения поставленной задачи выбрана нейронная сеть, имеющая один скрытый слой [5, 6]. Поскольку число нейронов в
скрытых слоях обычно колеблется от Nx до
3Nx, где Nx – число входов нейронной сети,
то выберем число нейронов в скрытом слое
равным пяти.
Исходя из трех вариантов сетевых технологий, число входов и выходов нейронной
сети равно трем.
Введем следующие обозначения:
х1 – средняя мобильность узлов, величина
меньшая единицы, большая нуля;
х2 – номер преобладающего класса задач в
узлах сети;
х3 – число узлов в сети;
y1 – величина, равная единице при выборе
протокола AODV и нулю во всех остальных
случаях;
y2 – величина, равная единице при выборе
протокола DSR и нулю во всех остальных
случаях;
y3 – величина, равная единице при выборе
протокола DSDV и нулю во всех остальных
случаях.
Структура нейронной сети (на основе двухслойного персептрона) представлена на
рис. 1.
Для обучения и тестирования нейронной сети использовался алгоритм, реализованный на языке Delphi с использованием
библиотеки NeuralBase.
Рис. 1. Двухслойный персептрон
для выбора протокола
Обучающая выборка состояла из 300
примеров, в которых число узлов сети изменялось от 2 до 1000, номер преобладающего
класса – от 1 до 4, средняя мобильность уз-
61
Новые технологии
лов – от 0.01 до 0.9. Среднеквадратичная
ошибка, усредненная по всем обучающим
примерам, составила 0.00027.
Чтобы оценить возможности нейронной
сети к обобщению в обученной нейронной
сети была использована тестовая выборка из
10 примеров. Среднеквадратичная погрешность, усредненная по всем тестовым примерам, составила 0.00102.
Считая погрешности обучения и обобщения приемлемыми, рассмотрим процесс
выбора протокола в беспроводной сети.
Выбор протокола осуществляется программно на одном из узлов беспроводной
сети – на управляющем узле.
1. На каждом узле беспроводной сети
выполняется программа, которая периодически (с заданной частотой) передает на
управляющий узел параметры своего узла:
номер преобладающего класса задач, мобильность (предполагается, что узлы могут
определять свою мобильность).
2. После получения параметров от всех
Eff =
узлов программа, загруженная на управляющем узле, осуществляет выбор протокола беспроводной сети с помощью обученной
нейронной сети.
3. Далее программа на управляющем
узле передает команду перехода остальным
узлам сети на выбранный протокол.
Частота передачи параметров на управляющий узел от других узлов сети задается в
настройках программ на узлах.
Для оценки эффективности выбранного
нейронной сетью протокола использовалась
метрика – время доставки пакетов. В результате проведенного эксперимента с обученной нейронной сетью была получена зависимость эффективности выбранного нейронной сетью протокола от числа узлов, которая
представлена на рис. 2. Эффективность Eff
для каждого протокола (DSR, AODV, DSDV)
определялась как коэффициент абсолютного
ускорения по следующей формуле:
где T1 – время доставки пакетов с использованием одного из протоколов
(DSR, AODV, DSDV);
T2 – время доставки пакетов с использованием выбранного нейронной
сети протокола;
T1
T2
(1)
4
3,5
3
Eff
2,5
Eff(DSR)
Eff(AODV)
Eff(DSDV)
2
1,5
1
0,5
0
0
5
10
15
20
25
30
35
40
45
Число узлов
Рис. 2. Зависимость коэффициента абсолютного ускорения от числа узлов
При малом числе узлов, например при
10, как видно из рис. 2, коэффициент абсолютного ускорения выбранного нейронной
сетью протокола может быть равен 1.1, т. е.
на 10% лучше по сравнению с другими протоколами. Переход на новый протокол передачи данных в сети не может происходить
мгновенно, требуется сохранение текущего
состояния в узлах сети, разрыв соединений и
повторное подключение (reconnect). Очевидно, что переход на новый протокол целесообразен тогда, когда эффект, полученный
от использования выбранного протокола,
превосходит временные затраты, связанные
62
с переходом на этот протокол.
В связи с этим необходима предварительная оценка времени доставки пакетов
для различных протоколов на одном и том
же участке сети. Для получения таких оценок используется вторая нейронная сеть с
такой же структурой, как представленная на
рис. 1, с входами х1, х2, х3 и выходами TDSR,
TAODV, TDSDV, где TDSR, TAODV, TDSDV – время
доставки пакетов по протоколам DSR,
AODV, DSDV соответственно. После обучения этой нейронной сети она позволяет получать значения TDSR, TAODV, TDSDV для заданных входных данных.
Открытое образование •6/2011
Новые технологии
времени доставки пакетов для протоколов
DSR, AODV, DSDV (определяются второй
нейронной сетью).
Тогда T1 в (1) определяется следующим
образом [4]:
Пусть y* = F(х1, х2, х3) – функция для
выбора предпочтительного протокола первой нейронной сетью, которая принимает
значения 1, 2, 3, что соответствует выбранным протоколам DSR, AODV, DSDV.
Пусть TDSR*, TAODV*, TDSDV* – функции
T1 =
1
( у * −2) ⋅ ( у * −3) ⋅ T *DSR −( у * −1) ⋅ ( у * −3) ⋅ TAODV * + 1 ( у * −1) ⋅ ( у * −2) ⋅ T *DSDV .
2
2
(2)
Пусть состояние сети изменилось, параметры х1, х2, х3 получили приращения
x1 + ∆x1 , x2 + ∆x2 , x3 + ∆x3 .
Тогда состояние нейронной сети у = F ( x1 + ∆x1 , x2 + ∆x2 , x3 + ∆x3 ) соответствует новому
выбранному протоколу. TDSR, TAODV, TDSDV – новые оценки времени доставки пакетов, полученные второй нейронной сетью, и T2 в (1) определяются следующим образом:
T2 =
1
( у − 2) ⋅ ( у − 3) ⋅ TDSR − ( у − 1) ⋅ ( у − 3) ⋅ TAODV + 1 ( у − 1) ⋅ ( у − 2) ⋅ TDSDV .
2
2
(3)
Подставляя (3) и (2) в (1), получим значение коэффициента абсолютного ускорения
1
( у * −2)⋅ ( у * −3)⋅T *DSR −( у * −1)⋅ ( у * −3)⋅TAODV * + 1 ( у * −1)⋅ ( у * −2)⋅T *DSDV
2
Eff = 2
.
1
1
( у − 2)⋅ ( у − 3)⋅TDSR − ( у −1)⋅ ( у − 3)⋅TAODV + ( у −1)⋅ ( у − 2)⋅TDSDV
2
2
По формуле (4) вычисляется коэффициент абсолютного ускорения Eff выбранного
протокола по времени доставки пакетов. Если он меньше некоторого порога Effmin, который задается в настройках программы на
управляющем узле, то переход на выбранный протокол первой нейронной сетью не
осуществляется.
Первая нейронная сеть осуществляет
выбор предпочтительного протокола. Основываясь на различных метриках: времени
доставки пакетов, числе удаленных пакетов
и др., вторая нейронная сеть определяет целесообразность перехода на протокол, выбранный первой нейронной сетью, путем
(4)
сравнения эффективности выбранного протокола по времени доставки пакетов с некоторым пороговым значением, определяемым
экспериментально с учетом времени перехода на новый протокол.
Заключение
Таким образом, разработан эффективный инструментарий выбора предпочтительного протокола маршрутизаций AdHocсетей, основанный на использовании математического аппарата нейронных сетей. Показано, что применение разработанного инструментария может давать выигрыш в скорости доставки пакетов более чем в 2 раза.
Литература
1. Винокуров В. М., Пуговкин А. В., Пшенников А. А., Ушарова Д. Н., Филатов А. С. Маршрутизация в беспроводных мобильных Ad hoc-сетях // Доклады ТУСУРа, 2010. № 2 (22). Ч. 1. С. 288–292.
2. Таненбаум Э. Компьютерные сети. 4-е изд. – Спб.: Питер, 2003. 992 с.
3. Kaushik S. S., Deshmukh P. R. Comparison of effectiveness of AODV, DSDV and DSR routing protocols in mobile Ad hoc networks // International Journal of Information Technology and Knowledge Management, 2009. Vol. 2. No. 2. P. 499–502.
4. Комашинский В. И., Смирнов Д. А. Нейронные сети и их применение в системах управления и
связи. – М.: Горячая линия – Телеком, 2003. 94 с.
5. Ясницкий Л. Н. Введение в искусственный интеллект. – М.: Академия, 2005. 176 с.
6. Рогозин О. В. Комплексная оценка эффективности инновационного проекта на основе анализа
качественных характеристик // Открытое образование, 2010. № 6. С. 140–146.
* * *
Открытое образование •6/2011
63
1/--страниц
Пожаловаться на содержимое документа