Автореферат (1090593), страница 3

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

Текст из файла (страница 3)

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

Компоненты вектора qнеизвестны и не изменяются во времени, то есть, q  0 .В данной работе для решения задач идентификации модели и оценкизагрузки узлов сети предлагается использовать метод квазилинеаризации,который позволяет наиболее полно идентифицировать нелинейную систему,14которой, с помощью нелинейных дифференциальных уравнений, можноописать распределённый вычислительный комплекс.Стоит отметить, что задача идентификации и прогнозирования тесносвязаны, так как идентификация проводится с целью облегчения предсказанияповедения идентифицируемой системы. В связи с этим, с помощью методаквазилинеаризации возможно получение оценок (прогнозирование) векторапараметров и вектора состояния динамической системы на этапе дооцениваниявектора состояния системы.

Это особенно важно для задачи предсказаниязагрузки узлов РВК, так как здесь параметры модели обычно также неизвестны.Методквазилинеаризации,фактически,реализуетподходпредикатор-корректор, что позволяет минимизировать ошибку ковариации, за счёткорректировки предсказанных значений.Обозначим через t k текущий момент времени. Наша задача заключаетсяв нахождении прогнозных значений загрузки узла РВК x1 (tk 1 ) , а измерениямподдается та же величина в предыдущие моменты времени x1 (ti ), i  k , притом, что вектор параметров q нам неизвестен, то вводим новый вектор x1 (t )    x n (t ) (t )  . q1    q k Уравнение динамики вектора  (t ) имеет вид: (t )  (  (t ), u(t )) ,где f1 (  (t ), u (t ))  f n (  (t ), u (t )).0015Метод квазилинеаризации основан на нахождении линеаризованногоприближения относительно предыдущей итерации (собственно, поэтому методи называется квазилинеаризация).

Если найдена N-я итерация оценки новоговектора состояния €N ( t ) (t ) , то, раскладывая уравнение  (t )  (  (t ), u(t )) , встепенной ряд относительно найденного приближения €N (t ) и оставляя толькочлены первого порядка малости, получаем следующее (N+1)-е приближениеоценки искомого вектора, которое можно записать в линейном виде€N 1 (t )  A€N (t ) €N 1 (t )  V€N 1 , (t )где:€A€N (t )   ( t )  €€, V€N (t )  N (t ) ( t )  N ( t )€  ( t )  €€ N (t )  A€N (t ) €N .(t )N (t )Для оценки прогнозных значений загрузки узла РВК x1 (tk 1 ) следуетнайти вектор €N 1 (t ) размерности n+k, включающий в себя n компонентвектора состояния x(t ) и k компонент оценки вектора параметров модели q .Для этого необходимо иметь n+k измерений.

Как уже говорилось, измерениюподдаются предыдущие значения первой компоненты вектора x(t ) в t jмоменты времени. Тогда новый вектор состояния на N  1 итерации €N 1 (t0 )удовлетворяет граничному условиюx1 (t j )  Y1, N (t j , t 0 ) €N 1 (t 0 )  1, N (t j ) , j  1, n  k ,гдеtj1, N (t j )   Y1, N (t j , ) VN ( ) d , j  1, n  k.t0В описанных выше уравнениях Y1, N () представляет собой 1-ую строкуфундаментальной матрицы Y N () . Так как произведено n+k измерений, тоуравнений тоже n+k, и они представляют собой полную систему линейных16алгебраических уравнений с n+k переменными.

Решение этой системы даетn+k компонентов, составляющих вектор €N 1 (t0 ) , последние k компоненткоторого представляют собой оценку искомого вектора параметров q . По€N 1 (t0 ) и фундаментальной матрице Y1, N () можнонайденному значениюнайти прогнозное значение загрузки узла:x1, N (tk 1 )  1 0  0 €N 1 (tk 1 ),t k 1t k 1t0t0€ ( )d  Y (t , ) A€ ( ) € ( )d ,€N 1 (t k 1 )  YN (t k 1 , t 0 ) €N 1 (t 0 )   YN (t k 1 , )N N k 1 N NПрименённыйвработеметодквазилинеаризацииотличаетсяквадратичной сходимостью, если только он вообще сходится.

Для обеспечениясходимости метода необходимо, чтобы начальное приближение было не оченьдалеко от истинного значения параметров. Для получения адекватногоначальногоприближениявработепредлагается использоватьметодыпрогнозирования, основанные на фрактальных свойствах трафика. Шагдискретизации, глубина прогноза, размер интервала [t1,t2] определяютсяособенностями среды grid и набором сетевого оборудования.Третья глава посвящена экспериментальной проверке предложенныхалгоритмов. Для проведения эксперимента предложено использовать методимитационного моделирования, позволяющий осуществлять полный контрольвсех параметров исследуемого комплекса, с возможностью оперативногоизменения алгоритма балансировки нагрузки и обеспечивающий возможностьмоделирования условий эксплуатации комплекса близких к реальнымнагрузкам.Экспериментальная проверкаосуществлялась с целью выявленияфункциональных характеристик и определения возможности использования напрактике методов, разработанных в главе 2 данного диссертационногоисследования.

В качестве критерия качества прогнозирования методом17квазилинеаризации предложено использовать оценку индекса безразмернойошибки (англ. NDEI), определяемой как:NDEI RMSEsdt ( yt )или11 t T( yt  y€t ) 2 ,sdt ( yt ) T t 1NDEI где sdt ( yt ) - стандартное отклонение.Было произведено сравнение метода прогнозирования на основепредложенного алгоритма квазилинеаризации с методом экспоненциальногосглаживания.Примоделированииколичествоузловвычислительногокомплекса было фиксированным и составило N=10. На вход тестовой системыпоступало на обслуживание n=104 запросов (набор для формированиявременного ряда), которые требовалось обработать.Для анализа уровня адаптации разработанного алгоритма к возникающейнагрузке могут применяться различные метрики, такие каккоэффициентвариации, стандартное отклонение и коэффициент Джини.

В данной работе, дляоценки уровня дисбаланса вычислительной нагрузки в РВК, был рассчитанкоэффициент вариации:CV где,- стандартное отклонение нагрузки; - среднее значение нагрузки.Анализ полученных значений позволил выявить некоторое преимуществоразработанного алгоритма, по сравнению с алгоритмом экспоненциальногосглаживания. На рисунке 2 показан баланс вычислительной нагрузки взапросах, обрабатываемых распределённым вычислительным комплексом навсём периоде работы.18Рисунок 2 – Распределение нагрузки в зависимости от времени работы [5]Однако,дляквазилинеаризации,оценкикачествапрогнозированияметодомиспользование таких оценок как индекс безразмернойошибки и среднеквадратичной ошибки модели в некоторых случаях бываетнедостаточно.

На практике, для этих целей, часто применяют совокупностьрасчёта стандартного отклонения и интервальную оценку для исследуемогопрогнозного параметра. В отличие от точечной оценки параметра, методпостроения доверительного интервала статистической величины нагрузкиявляется хорошим способом проверки не только точности, но и надёжности(качества) прогнозирования разработанной модели, по сравнению с другимимоделями, например ARIMA.Доверительный интервал для среднего по совокупности данных, законраспределения вероятностей которого описывается непрерывным нормальнымраспределением, рассчитывается по следующей формуле:x ts /2 n   x ts /2 n,где x - выборочное среднее арифметическое;t /2- квантиль распределения Стьюдента уровня α;s - несмещённое среднее квадратичное отклонение по выборке;n - размер выборки; - среднее по совокупности.19Таким образом, возможно нахождение интервальных оценок длязначений вычислительной нагрузки, что впоследствии, можно использовать вкачестве критерия оценки качества прогнозирования.

Например, полученныезначениядоверительногоинтерваладлязначенийнагрузкиприсоответствующем уровне α=0,1, говорят о том, что с выбранным процентомвероятности, реальная загрузка узла комплекса должна лежать в тех границах,которые определяются формулой.В результате проведенной экспериментальной проверки выявлено, чтопредложенный метод прогнозирования вычислительной нагрузки обладаетприемлемой точностью и скоростью прогнозирования, что делает возможнымегоприменениенапрактикедляосуществлениякраткосрочногоисреднесрочного прогнозирования. Полученные результаты не противоречатрезультатамдругихработ,посвящённыхисследованиюметодовпрогнозирования сетевой нагрузки (сетевого трафика) и вычислительнойнагрузки (узловой нагрузки).

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

Характеристики

Список файлов диссертации