Stochastic shortest path search using flow control parameters based on dynamic routing protocol for mobile AD-HOC networks

Full Text

Введение

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

 4.4. Стохастическое решение о маршруте

 В этом разделе описывается, как обычные параметры управления потоками данных  AODV (протокол динамической маршрутизации для мобильных AD-HOC сетей (MANET)) используются для стохастического поиска кратчайших путей [2]. На этом этапе система использует численное значение эмпирического расчета для определения  наилучшей скрытой последовательности в соответствии с исходной моделью.

Декодирование производится с использованием алгоритма Витерби, и предлагаемая система оценивает, требуется ли шаг обучения с использованием метода Баума-Уэлча для оптимизации модели.

4.4.1. Предложенная полностью связанная модель

 Чтобы определить нашу стохастическую модель, мы запускаем последовательность Y в момент времени T=10 для наблюдаемых символов. Каждый символ Y_t представляет значение энергии, которое, вероятно, наблюдается на пути в это время.

Предположим, что мы наблюдаем следующую короткую последовательность (11) уровней (12):

 

Y=v₁, v₂, v₃, v₃, v₂, v₁, v₁, v₂, v₃, v₁ ,      (11)

Y=L, M, H, H, M, L, L, M, H, L .      (12)

 

Последовательность Y представляет собой выбранные случайным образом символы наблюдения, где каждый символ определяет уровень энергий в системе [3]. Вероятность соблюдения последовательности, заданной моделью l, оценивается в Прямом алгоритме. Каждый символ v_k иллюстрирует энергетический уровень, на котором может находиться каждое состояние:

V=v₁=Low(L); v₂=Medium(M); v3=High(H).

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

 

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

 

Алгоритм Витерби используется для поиска оптимальной скрытой последовательности. Учитывая последовательность наблюдений и модель HMM, алгоритм возвращает путь к состоянию через HMM, который присваивает последовательности наблюдений максимальное правдоподобие. Мы используем следующее обозначение: P(X, Y/l).

Определим величину d_t(j) для j=1…N, для t=1…T, d_t(j) - это максимальная вероятность, учитывая количество k параметров, того, чтобы пройти через последовательность состояний X_1®t, которая заканчивается в E_j в момент времени t, и наблюдать последовательность Y_1®t:

 

d_t(j)=Max_1®t®1P(X_1®t®1, X_t=E_j,Y_1®t /l    (13)

 

Из состояния E_j в момент времени t и состояния E_i в момент времени t₁ при t=2…T, d_t(j)  - максимальная вероятность того, что пути заканчиваются в состоянии E_j.

Методом индукции получаем:

 

.     (14)

 

 

 

Таким образом, определение максимального аргумента  похоже на получение

 

 .               (15)

 

Таким образом, принимая аргумент для максимума d_t(j) для всех t=1,2,…,10 и j=1…N, мы получаем оптимальную последовательность состояний:

 

 .          (16)

 

Для любых tÎ[1, T] и jÎ[1, N] переменные d_t и ψ_t используются для оценки наилучшего скрытого пути с использованием подхода Витерби. Пороговая вероятность для процесса обнаружения была установлена равной 0,4 (рис. 1 [1]).

 

4.4.2 Обучение стохастической модели управления потоками данных

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

Следующее предположение должно быть проверено после каждого этап обучения.

 

P(Y׀׀l_i)> P(Y׀׀l_i+1) .              (17)

 

В уравнении (17) P(Y׀׀l_i) — это вероятность исходной последовательности, а P(Y׀׀l_i+1) — это вероятность после обучающего набора, заданного нашей исходной стохастической моделью управления потоками данных. После определенного количества итераций стохастическая модель управления потоками данных  должна достичь стабильности.

 

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

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

Учитывая наблюдаемую последовательность Y_1®t=Y₁, …, Y_t, получим вероятности того, что первый Y_1®t завершится состоянием E_i, для i=1…T-1. Рассмотрим прямые переменные α_i, определенные по формулам:

 

 ,                 (18)

 .         (19)

 

Каждый элемент α_i в уравнениях (18), (19) представляет собой вероятность использования энергии пути после просмотра первого наблюдения t.

Например, мы использовали процесс завершения в прямом/обратном алгоритме для оценки вероятности соблюдения наилучшей последовательности с помощью уравнения (20):

 .                  (20)

 

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

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

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

 

P(Y׀׀l)´e ,                               (21)

 

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

 

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

Обучение	Вероятность	Решение о маршруте
1	1.32e-09	1.32e-6
2	3.92e-05	0.039
3	2.24e-04	0.22
4	4.59е-04	0.5

 

5. Анализ результатов моделирования

 5.1. Настройка параметров

 Сетевой симулятор версии 2 (NS2) используется для реализации системного сетевого трафика для нашего стохастического алгоритма управления потоками данных  [5]. NS2 - это хорошо известный объектно-ориентированный сетевой симулятор с высокой степенью параметризации, используемый научным сообществом, который позволяет экспериментировать со многими вариациями параметров сети и наблюдать относительные характеристики исследуемой системы. Его версия ns-2.35 была реализована в среде Ubuntu 14.04 LTS. Возможности моделирования приведены в табл. 3.

Таблица 3. Параметры моделирования

Параметр	Значение
Протоколы управления потоками данных	AODV/предлагаемые
Модель мобильности	равномерная
Размер сети	100 на 200 м
Начальная энергия	100 Дж
Мощность передачи Tx	0,05 Вт
Мощность приема Rx	0,024 Вт
Скорость	1 Мб/с
Количество узлов	10
Время	100 с

 

 5.2. Оценка вероятности управления потоками данных

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

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

 

Таблица 4. Потребление энергии узлами-образцами

Идентификатор узла	2
4	6
8	10
Энергия (Дж)	29,98
29,82	28,71
30,45	27,91

 

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

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

 

Таблица 5. Потребление энергии между исходным и конечным узлами

Параметр управления потоками данных	Значение
Источник	N1
Пункт назначения	N10
Путь 1	1,2,4,5,7,9,10
Emin1	196,895 Дж
Путь 2	1,2,4,5,7,8,10
Emin2	197,339J
Путь 3	1,2,4,5,6,8,10
Emin3	198,246 Дж

 

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

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

 

D=E1, E2, E3, E3, E1, E1, E1, E2, E3, E1

P(Y׀׀l)=3.92e^-05,

 

которая определяется начальными параметрами. Алгоритм Витерби обеспечивает для нашей вероятностной системы уровень энергии E₁, соответствующий низкому уровню в момент времени t при минимальной энергии. Мы можем использовать соответствующий путь для увеличения срока службы сети. В качестве альтернативы, согласно подходу Витерби, нашим вероятным резервным маршрутом может быть E₃, чтобы избежать нехватки энергии и проблем с управлением потоками данных.

 

Таблица 6. Особенности управления потоками данных путей

Pathk	Узлы	Emink	Стоимостьk
1	1,2,4,5,7,9,10	196,895 Дж	2,56
2	1,2,4,5,7,8,10	197,339 Дж	2,76
3	1,2,4,5,6,8,10	198,246 Дж	2,82

Условные обозначения: E^mink=минимальная энергия Path_k

Повторная оценка параметров с помощью алгоритма Баума-Уэлча, использованного в предыдущем процессе обратного отслеживания Витерби, стабилизирует систему на оптимальном скрытом пути:

D=E1, E2, E3, E3, E3, E1, E1, E1, E2, E3, E1

P(Y׀׀l)=2.24e^-045.

То же самое наблюдается  в скрытой последовательности. Только вероятность получения начальной последовательности, заданной моделью, значительно повышается. Начальный маршрут - E1 с пятью повторениями, а резервный - E3 с тремя повторениями. Оценивается наилучшая общая вероятность управления потоками данных  (BRP) использования энергоресурса в течение определенного времени. На рис. 4 показано вероятное поведение системы при использовании энергии в начале управления потоками данных. Вероятность высока, учитывая временной ряд Y_T и модель k.

На рис. 4 показана тенденция изменения маршрута на четырех этапах обучения. Начиная с этапа 1, обозначенного пунктирной линией, высокая вероятность составляет около 0,6 %. Вероятность на этапе 2, обозначенном пунктирной линией, значительно снижается. А с этапа 3 по этап 4 общее снижение энергопотребления составляет почти 0,4 %. Динамика между наблюдениями при t=0 и t=1 показывает, что вероятность управления потоками данных  в начале процесса высока. По истечении первой единицы времени это значение уменьшается до определенного системного порога. Кривая продолжает сходиться. В момент времени t=2 траектория соответствует траектории 1, выбранной модулем принятия решений, и ее вес составляет cost=7 хопов при низкой энергии около 196,895 Дж. На данном этапе это наименьшее значение по сравнению с другими траекториями.

Рис. 4. Сравнение тенденций наилучшей вероятности управления потоками данных  (BRP) между четырьмя этапами обучения

 5.3. Сравнение производительности

 Проводится сравнение с традиционными протоколами управления потоками данных, такими как ad hoc on-demand distance vector routing protocol (AODV), для оценки эффективности предлагаемого протокола управления потоками данных  на базе HMMB. Представлены значения энергозатрат после каждой серии тренировок и проведено среднее сравнение между этим подходом и обычным.

От тренировки к тренировке (табл. 5, рис. 5) потребление энергии в системе меняется. После этапа стабилизации достигается пороговое значение, и потребление энергии в системе значительно снижается.

 

а) потребление энергии на первом шаге

б) потребление энергии на втором шаге

в) потребление энергии на третьем шаге

Рис. 5. Сравнение поведения системы после нескольких циклов оптимизации

 

г) потребление энергии на четвертом шаге

Рис. 5. Сравнение поведения системы после нескольких циклов оптимизации (окончание)

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

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

На рис. 6 мы ясно видим, что предлагаемая система значительно снижает энергопотребление. Среднее потребление энергии AODV составляет 285,46 Дж. В противном случае, после четырех тренировок в нашей системе среднее потребление составляет 231,07 Дж. Это значение соответствует снижению энергопотребления в системе с предложенной стохастической моделью на 19,05 %.

Рис. 6. Среднее потребление энергии системой

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

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

а) накладные расходы на управление

б) накладные расходы на маршрутизацию

Рис. 7. Сравнение параметра управления потоками данных с накладными расходами в сети

На рис. 7 продемонстрировано сравнение параметра управления потоками данных  с накладными расходами в сети: а) накладные расходы на управление сокращаются примерно в то же время, что и для двух протоколов управления потоками данных. Значение параметра управления потоками данных, основанного на HMM, соответствует исходному протоколу управления потоками данных; б) сравнение с нормализованным протоколом управления потоками данных. Исходный протокол управления потоками данных  приобретает все большее значение по сравнению с протоколом управления потоками данных  на основе HMM.

5.4. Обсуждение

 Предлагаемый способ направлен на повышение энергопотребления в сети WSN. Например, если в период инициализации достигается пороговое значение, мы вычисляем и декодируем соответствующую скрытую последовательность, используя метод Витерби, который вычисляет вероятность кратчайшего пути с учетом модели l и принимает решение о маршруте. Напротив, если система не может достичь порогового значения по истечении времени инициализации, выполняется этап обучения с использованием метода Баума-Уэлча, который является частным случаем алгоритма максимизации математического ожидания (EM) для улучшения решения о маршруте в нашей исходной стохастической модели управления потоками данных l.

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

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

В табл. 7 представлена максимальная вероятность получения наиболее оптимальной последовательности скрытых состояний с учетом случайной серии наблюдений (Y_t) в момент времени t=10 после четырех этапов обучения. Чтобы сгенерировать последовательность символов O(10)= Y_t, более вероятно начать сначала с состояния t₁=E₁, затем t₂=E₂ и закончить в момент времени T=10 в состоянии t₁₀=E₁. Максимальная вероятность может показаться очень малой, но это нормально. Существует множество возможных последовательностей скрытых состояний, которые могут быть сгенерированы в количестве порядка M^T [6], эквивалентном 3¹⁰ в нашем конкретном случае.

 

Таблица 7. Максимальная оценка управления потоками данных

Скрытая последовательность	Вероятность
E1,E2,E3,E3,E3,E1,E1,E1,E2,E3,E3	4.59e-04

Заключение

 1. В работе представлен стохастический подход к управлению потоками данных в мобильных AD-HOC сетях (MANET), основанный на использовании скрытых марковских моделей (HMM) для определения оптимальных маршрутов передачи данных. Разработана взаимосвязанная эргодическая модель, в которой алгоритм Витерби применяется для декодирования скрытых состояний и выбора кратчайшего пути с минимальным энергопотреблением, а алгоритм Баума–Уэлча используется для оптимизации параметров модели и уточнения вероятностных переходов.

2. Результаты моделирования, выполненного в среде NS2 (версия 2.35), показали, что предложенный метод обеспечивает снижение среднего энергопотребления сети примерно на 19,05 % по сравнению с базовым протоколом AODV. При этом наблюдается повышение стабильности маршрутизации и уменьшение накладных расходов на управление потоками данных. Проведённый анализ подтвердил эффективность стохастической модели в условиях динамически изменяющейся топологии сети и ограниченных энергетических ресурсов узлов.

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

__________________________

© Хуссейн А.И., Рындин Н.А., 2025

About the authors

Ali Eid Husein

Voronezh State Technical University

Author for correspondence.
Email: eng.alihussein1993@gmail.com

graduate Studen

Russian Federation, 84 20-letiya Oktyabrya str., Voronezh 394006, Russia

Nikita A. Ryndin

Voronezh State Technical University

Email: nikita.ryndin@gmail.com

Dr. Sc. (Technical), Associate Professor

Russian Federation, 84 20-letiya Oktyabrya str., Voronezh 394006, Russia

References

Supplementary files