Оценка самоподобности речевого трафика вейвлет-методом с автоматическим определением границ масштабирования

УДК 621.396.67

Оценка самоподобности речевого трафика вейвлет-методом с автоматическим определением границ масштабирования

О.И. Шелухин, А.В. Осин, Р.Р. Ахметшин

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

In this paper we present the results of the multiplexed voice traffic self-similar properties examination by wavelet technique with the help of automatic selection of the onset of scaling.

Введение

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

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

Новизной работы можно считать использование для анализа самоподобных свойств объединенного речевого трафика оценок, основанных на вейвлет-преобразовании [4]. Такие оценки позволяют получить более точные результаты по сравнению с эвристическими методами (R/S-статистика, изменение дисперсии, периодограммный метод и др.). Кроме того, вейвлет-метод дает возможность вычислить доверительные интервалы получаемых оценок.

С использованием информации о статистических моментах вейвлет-коэффициентов на разных уровнях разложения и информации о характере масштабирования могут быть построены вейвлет-модели для объединенного речевого трафика в магистральных каналах сетей связи [5].

В качестве экспериментальных использовались данные, приведенные в [8]. С целью исследования эти речевые данные, после предварительной

их сегментации и пакетизации, подвергались объединению [9].

Разложение сигналов по вейвлет-базису

Вейвлет-анализ [6] выполняется путем разложения выборки Х((): {х(^о), х(?!),...,х(^_!)} объема п0 = 2/тах , (п0<Л^) на функции детализации различного масштаба. Здесь /тах=[^2^]— максимальное число масштабов разложения; [^2^] - целая часть числа [1о§2Л].

Значение индекса масштаба/=0 соответствует случаю максимального разрешения - самой точной аппроксимации, которая равна исходному ряду Х(0, состоящему из п0 отсчетов. С увеличением / (0</</тах) происходит переход к более грубому разрешению.

При заданных скейлинг-функции ф и мате-ринском-вейвлете у коэффициенты аппроксимаций а/к и коэффициенты деталей / дискретного вейвлет-преобразования для процесса Х(0 определяются следующим образом:

да да

а/к = | Х (р/к (, к =| Х (?У/к ()^,

—да —да

где (р/к = 2—7/2р2—Ч — к) ; у// к = 2—7/2^(2—Ч — к) .

В соответствии с положениями вейвлет-анализа известно, что временной ряд Х(0 может быть представлен в виде

/

Х (Г) = Х/ (Г) + 1 Б/ (Г),

/=1

п0 / 2/ —1

где Х/ () = I а/ р/ к ({) -функция начальной

к=0

аппроксимации, соответствующая масштабу / (/</тах), а/^к =^Х(?),р/ к} - масштабный коэффициент, равный скалярному произведению ис-

ходного ряда У(0 и масштабной функции «самого грубого» масштаба /, смещенной на к единиц масштаба вправо от начала координат;

п0/2/ —1

Б С) = I й/У/,к (*) - функция детализации

к=0

/-го масштаба, й/ к =(Х(I), у/ к) - вейвлет-

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

Материнский вейвлет у(0 можно представить в виде полосового фильтра с граничными частотами а>1 и а>2, которые являются соответственно нижней и верхней отсечками частоты для у(1). В результате коэффициенты деталей / можно рассматривать как процесс на выходе полосового

фильтра. Квадрат процесса деталей й/,к грубо измеряет энергию около момента времени ^ = 2/кА и частоты 2-/ а>0, где А - принятый единичный интервал времени; 0 = (1+2)/2.

Дисперсии процессов деталей й/ на всех масштабах {2 } (когда такие процессы являются стационарными) - это характеристики 2-го порядка процесса Х(0, которые определяют вид «вейвлет-спектра».

Для реализации вейвлет-метода оценки само-подобности из многообразия существующих вейвлетов выберем вейвлеты Хаара (рис. 1) и Добеши (рис. 2).

1 . £ А / 1 X 1 / V 1/ X г \ У ! 1 1 4 1 1 " 1 1 ^ ! •

1 1 V 7 1 / 1 1 1

1 1 1 I

0 12 3

Рис. 2. Материнский вейвлет и скейлинг-функция вейвлета Добеши-4

Вейвлет-метод оценки самоподобия

Пусть Х(0 будет стационарным в широком смысле процессом. Тогда его вейвлет-коэффициенты й/к могут быть найдены из уравнения [4]

М [й/ к 2] = | /

где /Л) и ^(Л) — спектр мощности для У и преобразование Фурье для вейвлет-функции у0 (•) соответственно.

На основании (1) получаем

М [/ 2] ~ 2/

где С(Я, у) —постоянная, зависящая от Я и у0 .

Если длина выборки У равна п, тогда доступное число вейвлет-коэффициентов в октаве / равно П/ = 2-/п. В результате получим выражение

п /

,,/= М[/2]и-111 I2.

/ к=1

Величина /1/ является несмещенной и состоятельной оценкой для М[й/, )2].

Формула (2) описывает возможный способ оценки показателя Херста ДВЗ-процессов в виде зависимости

1°ё2 М/ ~ (2Я — 1)/ + с = а/ + С,

где С =00^.

Это означает, что, если У(0 является ДВЗ с показателем Херста Н, то график зависимости 1о§2(м) от /, называемый логарифмической диаграммой (ЬБ), имеет линейный наклон 2Я—1, и масштабный показатель а = (2Я — 1) может быть получен путем оценки наклона графика функции

1о82(м) от/.

Можно найти взвешенную оценку а для а на интервале [/1; /2] [10]:

Рис. 1. Вейвлет Хаара: а - материнский вейвлет; б - скей-линг-функция

ос =

I ,

/

С=1 //,

/

% — 5!

где =

У/ = 1о82(м ) — 8(/),

8/ =у(П/ /2) /1п2 — (П/ /2) ;

V- =

%2 —

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

В табл. 1 приводятся численные аппроксимации показателя Хертса для графиков, показанных на рис. 3.

Таблица 1. Численные результаты вейвлет-оценок показателя Херста с использованием различных материнских вейвлетов

2

/2

/2

/2

5 = 1 % =1 // Х2 = 1/СТ/

/ = /1 / = /1 /=/1

<г2 = 2/(П/ 1п2 2), п/ - число коэффициентов-деталей

на соответствующем уровне разложения (/).

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

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

При использовании вейвлетов Хаара и Добе-ши-4 были получены схожие результаты (рис. 3), что свидетельствует о независимости получаемого результата при анализе самоподобных свойств

Материнские вейвлеты Число источников

10 50 100

Вейвлет Добеши-4 1,309 1,234 1,149

Вейвлет Хаара 1,192 1,216 1,092

Оценки выполнены на всем диапазоне масштабов, представленных на графиках (рис. 3). Они показывают, что найденные оценки показателя Херста для любого уровня агрегирования Я>1. Это свидетельствует либо о том, что данный процесс является нестационарным, либо о том, что исследуемый процесс является мультифракталь-ным, а диапазон масштабов, задаваемый в рамках монофрактальной оценки, определен неверно [11]. В [12] показано, что при большом объеме мультиплексируемых речевых потоков условие стацио-

1о§2

!<>&

а)

б)

в)

Рис. 3. Оценки показателя Херста, найденные вейвлет-методом с использованием вейвлетов Добеши-4 (сверху) и Хаара (снизу), для различного числа источников: а — 10; б — 50; в — 100

нарности выполняется. Следовательно, при анализе показателя Херста в рамках монофрактальной оценки неверно выбран диапазон масштабов.

Для выбора диапазона масштабирования воспользуемся результатами работы [7].

Автоматическое определение нижней границы масштабирования. Идея метода обнаружения начала масштабирования основана на использовании устойчивости и отчетливости перехода на графике выборочной функции Q(/l) = 1-2( V (/1)) от «зоны стремительного роста» до «нулевого равновесия» и нахождению масштаба , со-

ответствующего такому переходу [7] (здесь ¥т — дополнительная функция распределения хи-квадрат случайной переменной с т степенями сво- Таблица 2. Результаты оценки степени самоподобности для различных диапазонов

Если такого / не существует, тогда устанавливается * *

/1 = 1. Если такое / существует, тогда / приравни-

* *

вается ему. В итоге устанавливается /1 = /1 +1.

Экспериментальным путем показано [7], что при выборе коэффициента стремительного роста (/ас) достаточно ограничиться значением 10, так как дальнейшее увеличение оказывает слабое влияние на получаемый результат, а значения, меньшие 10, показывают неустойчивый результат и, следовательно, не могут быть выбраны.

В табл. 2 и на рис. 4 представлены результаты оценок показателя Херста (слева), выполненных с учетом выбора начальной границы масштабирования и соответствующих исследованию с помощью вейвлетов Добеши-3.

масштабного

]2

диапазона;

V (/1) = I (у/ — (а+с))2) ’

/=/1

оценки а и С определяются соотношениями (3) и (4)).

Ограничение количества степеней свободы величиной .7—2 обусловлено наличием двух налагаемых связей: наклона а и смещения С .

Детерминированная величина V описывает взвешенный квадрат расстояния подбора логарифмической диаграммы, который учитывается при вычислении ^е[0;1]. В результате оценка К( /1) является хи-квадрат случайной переменной

с (./—2) степенями свободы. Такая концепция удобна для практической реализации, так как тест критерия согласия может быть без труда применен к данным и явление резкого роста устойчиво к статистическим вариациям.

Алгоритм определения границы масштаба перехода / может быть представлен следующим образом.

Шаг 1. Определяется диапазон / [1, /ко], в котором Q(j\) является неуменьшающейся функ*

цией. Если /ко = 1, тогда устанавливаем /1 =1, иначе переходим к шагу 2.

Шаг 2. Вычисляется коэффициент наклона r/=Q(jУQ(j —1) для каждого/е [2, /ко].

Шаг 3. Выбирается некоторый коэффициент /ас, названный «коэффициентом стремительного роста», и находится наибольшее / такое, что Г/ > /ас.

Диапазон масштабирования Число источников

10 25 50 111

Полный диапазон оценки ] = 1.10, Н =1,407 ± 0,014 ] = 1.10, Я =1,394 ± 0,014 ] = 1.10, Я =1.384 ± 0,014 ] = 1.10, Я =1.388 ± 0,014

Автоматический выбор ] = 6.10, Я =0,894 ± 0,114 ] = 6.10, Я =0,902 ± 0,114 ] = 7.10, Н =0,695 ± 0,2 ] = 7.10, Н =0.675 ± 0,2

На рис. 4 (справа) представлен результат работы алгоритма автоматического определения нижней границы масштабирования. Сплошной линией показана «зона стремительного роста», а пунктиром «зона нулевого равновесия». Так как при вычислении функции Q для начальных масштабов / = 1, 2, 3 были получены очень маленькие значения, то их логарифмы были усечены до -10. Горизонтальные линии соответствуют Q = 0,01;

0,05 и 0,1. Закрашенным ромбом на графиках отмечена найденная в результате работы алгоритма точка начала области масштабирования /1* . По этой точке можно судить о нахождении «границы раздела» между кратковременными и долговременными корреляциями в данных. Так как при оценке показателя Херста учитываются только долговременные корреляции, а наличие сильной кратковременной составляющей может только исказить оценку, то точка выбиралась в качестве начальной, при аппроксимации логарифмической диаграммы.

В табл. 2 приводится сводная информация по полученным результатам с 95% доверительными интервалами. Здесь для сравнения приведены оценки выполненной на всей области логарифми-

Рис. 4. Результаты оценки показателя Херста вейвлет-методом в соответствии с автоматически выбранной областью масштабирования (слева) и автоматический выбор границы масштабирования (справа) для различного числа речевых источников: а - 10; б - 25; в - 50; г - 100

ческой диаграммы, т.е. / =1,...,10, и в зоне масштабирования, начало которой определено в соответствии с автоматическим алгоритмом. Результаты, представленные в табл. 2 подтверждают, что, если производить оценку по всем доступным масштабам, то оценка показателя Херста будет подвержена сильному влиянию кратковременных корреляций (Н > 1). Но как только при оценке учитывалась найденная граница раздела между кратковременными и долговременными корреляциями, то показатель Херста принимал значения в диапазоне 0,675.0,902.

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

Проведенные исследования с использованием вейвлетов Хаара и Добеши показали, что в режиме

масштабирования выбор конкретного вейвлета не важен и приводит к близким результатам;

вейвлет-анализ мультиплексируемых данных обнаруживает мультифрактальный характер речевого трафика на малых масштабах и монофрак-тальный на больших масштабах;

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

0.675...0.902.

ЛИТЕРАТУРА

1. Leland W.E., Taqqu M., Willinger W., Wilson D.V., On the Self-Similar Nature of Ethernet Traffic. Proc. SIG-COM93, 1993, San Francisco, California, pp. 183-193.

2. Garrett M.W., Willinger W. Analysis, Modeling and Generation of Self-Similar VBR Video Traffic. Proc. ACM Sigcomm, London, September 1994, pp. 269-280.

3. Kalden R., Ibrahim S. Searching for Self-Similarity in GPRS, Antibes Juan-les-Pins, France, PAM 2004, pp. 83-92.

4. Abry P., Flandrin P., Taqqu M.S., Veitch D. Wavelets for the analysis, estimation and synthesis of scaling data, to be published as a chapter to «Self Similar Network Traffic Analysis and Performance Evaluation», K. Park and W. Willinger, Eds., Wiley, 1999.

5. Riedi R.H.,. Crouse M.S., Ribeiro V.J. and Baraniuk R. G. A Multifractal Wavelet Model with Application to Network Traffic. IEEE Transactions on Information Theory, 45(3): 992-1019, 1999.

6. Добеши И. Десять лекций по вейвлетам. — Москва-Ижевск: НИЦ Регулярная и хаотическая динамика, 2001.

7. Veitch D, Abry P., Taqqu M. On the automatic selection of the onset of scaling, Fractals 11 (2003), pp. 377-390.

8. Шелухин О.И., Осин А.В., Урьев Г.А. Экспериментальные исследования речевых потоков в VoIP-сетях: - Электротехнические и информационные комплексы и системы, 200б, т. 2, №2, с. 54-59.

9. Осин А.В., Ахметшин Р.Р. Сегментация речи с использованием вейвлет-преобразования. - Электротехнические и информационные комплексы и системы, 200б, т. 2, №2, с. 30-32.

10. Шелухин О.И., Осин А.В., Ахметшин Р.Р. Оценка самоподобности телекоммуникационного трафика с

помощью вейвлетов. - Электротехнические и информационные комплексы и системы, 2006, т.2, №3, с. 28-34.

11. Шелухин О.И., Тенякшев А.В., Осин А.В. Фрактальные процессы в телекоммуникациях / Под ред. О.И. Шелухина. - М.: Радиотехника, 2003.

12. Шелухин О.И., Осин А.В., Невструев И.А., Урьев Г.А. Сравнительный анализ методов оценки стационарности самоподобных процессов. - Электротехнические комплексы и информационные системы, 2006, т.2, №1, с.55-60.

Поступила 22. G9. 2GG6 г.