Мультифракталы. Инфокоммуникационные приложения

Москва
Горячая линия - Телеком
2014

УДК 621.391: 519.216 
ББК 32.88 
     Ш44 
Р е ц е н з е н т : Заслуженный деятель науки Российской Федерации,

чл.-корр. РАН, доктор физ.-мат. наук, профессор  А. С. Сигов 

Шелухин О. И. 
Ш44  Мультифракталы. Инфокоммуникационные приложения. – 

М.: Горячая линия – Телеком, 2014. – 579 с.: ил. 
ISBN 978-5-9912-0142-1. 

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

ББК 32.88 

Адрес издательства в Интернет www.techbook.ru 
Научное издание 
Шелухин Олег Иванович

Мультифракталы  
Инфокоммуникационные приложения

Все права защищены.
Любая часть этого издания не может быть воспроизведена в какой бы то ни было форме и 
какими бы то ни было средствами без письменного разрешения правообладателя
© ООО «Научно-техническое издательство «Горячая линия – Телеком»
www.techbook.ru
 ©  О. И. Шелухин 

Предисловие

Термин «фрактал», впервые введенный Бенуа Мандельбротом, описывает явление, при котором некоторое свойство объекта (например, какого-то
изображения, речи, цифрового телекоммуникационного сообщения, временного ряда) сохраняется при изменении масштаба пространства или времени. Если исследуемый объект является самоподобным (или фрактальным),
то его части при увеличении подобны (в определенном смысле) его полному образу. Фрактальные формы удивительно широко распространены в
природе (береговая линия, гористый рельеф, река, дерево и т.д.). Известны фрактальные структуры веществ, фрактальные структуры множеств и
случайных процессов.
Повторяемость может быть полной (в этом случае говорят о регулярных фракталах) либо может наблюдаться некоторый элемент случайности
(такие фракталы называют случайными). Структура случайных фракталов на малых масштабах не является идентичной структуре всего объекта,
но их статистические характеристики совпадают, и свойства самоподобия
сохраняются после усреднения по статистически независимым реализациям объекта.
В телекоммуникационных приложениях свойствам стохастической самоподобности
(фрактальности)
удовлетворяют
измеренные
трафиковые
трассы. Здесь предполагается, что мерой схожести является вид трафика с
соответствующей амплитудной нормировкой. Для измеренных трасс сложно наблюдать чёткую структуру, однако самоподобность позволяет учитывать стохастическую природу многих сетевых устройств и событий, которые
совместно влияют на сетевой трафик.
Для количественного описания фракталов достаточно одной величины — размерности Хаусдорфа, или показателя скейлинга, описывающего
сохраняемость геометрии или статистических характеристик при изменении масштаба. Однако в физике, химии, биологии и в том числе в телекоммуникациях встречается много явлений, которые требуют распространения
понятия фрактала на сложные структуры с более чем одним показателем
скейлинга. Такие структуры часто характеризуются целым спектром показателей, и размерность Хаусдорфа является лишь одним из них. Сложные
фракталы, называемые мулътифракталами, важны прежде всего потому, что именно они, как правило, и встречаются в природе, тогда как простые самоподобные объекты представляют собой идеализацию реальных яв

Предисловие

лений. Фактически мультифрактальный подход означает, что изучаемый
объект каким-то образом можно разделить на части, каждая из которых
обладает своими свойствами самоподобия.
Таким образом мультифракталы — это неоднородные фрактальные
объекты, для полного описания которых, в отличие от регулярных фракталов, недостаточно введения всего лишь одной величины, фрактальной размерности, а необходим целый спектр таких размерностей, число которых,
вообще говоря, бесконечно.
Особенность последних состоит в том, что они наряду с глобальными
характеристиками стохастических процессов (получающихся в результате
использования процедуры усреднения по большим временным интервалам)
позволяют вскрыть особенности их локальной структуры.
Важной характеристикой методов, основанных на фрактальных представлениях и вейвлет-преобразованиях, является их универсальность.
Книга является некоторым итогом работ автора и его учеников:
Д.А. Лукьянцева, С.Б. Матвеева, К.Ю. Окулова, А.В. Осина, А.С. Пастухова, Г.А. Урьева в области фрактальных процессов и обобщает результаты,
опубликованные ранее в работах [1–3], на случай мультифракталов.
Автор сердечно благодарит члена-корреспондента РАН Александра Сергеевича Сигова, взявшего на себя, несмотря на огромную занятость, тяжелый труд рецензента и высказавшего ряд полезных замечаний, способствовавших улучшению содержания книги.
Особую признательность автор хотел бы высказать Николаю Федоровичу Лукьянцеву, генеральному директору ООО «ГеоТелекоммуникации»,
без чьей помощи книга вряд ли увидела бы свет.

1. Шелухин О.И. и др. Фрактальные процессы в телекоммуникациях /
Под ред. О.И. Шелухина. Монография. — М.: Радиотехника, 2003. — 480 с.
2. Sheluhin O.I., Smolskiy S.M., Osin A.V. Self-similar processes in telecommunications. — John Wiley & Sons, 2007. — 320 p.
3. Шелухин О.И. и др. Самоподобие и фракталы. Телекоммуникационные приложения / Под ред. О.И. Шелухина. Монография. — М.: Физматлит, 2008.
— 373 с.

Основные положения теории фракталов
и самоподобных процессов

1.1. Фракталы и мультифракталы

Фракталами Мандельброт называл геометрические объекты: линии поверхности, пространственные тела, имеющие сильно изрезанную форму, которые могут обладать свойством самоподобия. Слово «фрактал» произошло
от латинского слова fractus и переводится как дробный, ломаный. Фрактальный объект имеет бесконечную длину, что существенно выделяет его
на фоне объектов традиционной евклидовой геометрии. Фрактал, обладающий свойством самоподобия, более или менее единообразно устроен в широком диапазоне масштабов, т.е. существует сходство характеристик фрактала при рассмотрении его на различных разрешениях. В идеальном случае
самоподобие приводит к тому, что фрактальный объект оказывается инвариантным при изменении масштаба. Фрактальный объект может и не быть
самоподобным, но у тех фракталов, о которых пойдет речь в книге, повсеместно наблюдаются самоподобные свойства, поэтому, когда речь будет идти
о самоподобном трафике, подразумевается, что его временные реализации
являются фракталами.
Для возникшего естественным образом (природного) фрактала существует некоторый минимальный масштаб длины lmin, такой, что на масштабах l ≈ lmin его фрактальная структура не поддерживается. Кроме того,
на достаточно больших масштабах l > lmax, где lmax — характерный геометрический размер объектов в рассматриваемом окружении, фрактальная
структура объекта также нарушается. Поэтому свойства природных фракталов рассматриваются лишь на масштабах l, удовлетворяющих соотношению lmin ≪ l ≪ lmax.
Такие ограничения становятся понятными, когда в качестве примера
фрактала приводится изломанная (негладкая) траектория броуновской частицы. На малых масштабах на нее оказывает влияние конечность массы
и размеров броуновской частицы, а также конечность времени соударения.
При учете этих обстоятельств траектория броуновской частицы становится
плавной кривой и теряет свои фрактальные свойства. Значит, масштаб lmin,
на котором можно рассматривать броуновское движение в рамках фрак

Г л а в а 1

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

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

1.1.1. Фрактальная размерность множества

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

В соответствии с алгоритмом [1] для определения хаусдорфовой размерности Df некоторого множества, занимающего область с объемом LDf в
D-мерном пространстве, покроем это множество кубами с объемом εDf .
Минимальное число таких непустых кубов, покрывающих множество, есть
M(ε) = LDf (1/ε)Df. Из этого выражения можно получить приближенную
оценку Df:

Df = lim
ε→0
ln M(ε)
ln(1/ε) .
(1.1)

На практике более удобно для оценки этой размерности использовать
математическую конструкцию, известную как размерность Реньи, Dq, связанную с вероятностью pi нахождения контрольной точки в i-й ячейке в
степени q:

Dq = lim
l→0
1

q − 1
1
ln ε ln

⎛

⎝
M(t)
i=0
p(ε)q
i

⎞

⎠ ,
q = 0,1,2,...
(1.2)

Основные положения теории фракталов и самоподобных процессов
7

При q → 0 из формулы (1.2) имеем

D0 =
1
ln ε lim
ε→0

⎛

⎝ln

M(t)
i=1
1

⎞

⎠ = − lim
ε→0
ln M(ε)

ln ε
= Df,
(1.3)

т.е. размерность Реньи D0 совпадает с хаусдорфовой размерностью (1.1).
В силу монотонности Dq как функции q размерность Реньи уменьшается как функция степени, и поэтому выполняется следующее неравенство:
D2 ⩽ D0 = D. Таким образом, наибольшая нижняя граница хаусдорфовой
размерности представима в виде

D2 = lim
l→0
1
ln ε ln

⎛

⎝
M(t)
i=1
p(ε)2
i

⎞

⎠,
(1.4)

принимая во внимание, что вероятность нахождения контрольной точки в
i-й ячейке pi оценивается как

pi(ε) = lim
N→∞ Ni(ε)/N,
(1.5)

где N — общее число контрольных точек через интервалы 1/L; Ni — число
точек в i-й ячейке.
Формула (1.4) может быть рассчитана из экспериментально измеренных
длительностей сегментов. На практике наибольшую нижнюю границу размерности D2 можно вычислить как тангенс угла наклона линейной регрес
сии следующих точек:

⎡

⎣ln 1

N 2

⎛

⎝
M(t)
i=1
N 2
i

⎞

⎠ ;ln(ε)

⎤

⎦, вычисленных при разных ε.

1.1.2. Мультифракталы

Под мультифракталами понимают неоднородные фрактальные объекты, для полного описания которых, в отличие от регулярных фракталов,
недостаточно введения всего лишь одной величины, его фрактальной размерности Df, а необходим целый спектр таких размерностей, число которых
в общем случае бесконечно. Причина этого заключается в том, что наряду с
чисто геометрическими характеристиками, определяемыми величиной Df,
такие фракталы обладают и некоторыми статистическими свойствами.
Приведем описание мультифрактальных объектов с формальной точки
зрения. Рассмотрим фрактальный объект, занимающий ограниченную область L, характеризуемую размером L в евклидовом пространстве размерностью D. Пусть на каком-то этапе построения фрактал представляет собой
множество из K ≫ 1 точек, как-то распределенных в этой области. Будем
предполагать, что K → ∞. Разобьем всю область L на ячейки со стороной
l ≪ L, охватывающие εD единиц рассматриваемого пространства. Нас будут

Г л а в а 1

интересовать только занятые ячейки, в которых содержится хотя бы одна
точка из K принадлежащих данному фракталу. Пусть индекс занятых ячеек i изменяется в пределах i = 1,2,...N(ε), где N(ε) — суммарное количество
занятых ячеек, которое зависит от размера стороны ячейки ε. Пусть Ni(ε)
представляет собой количество точек в ячейке с индексом i, тогда величина

pi(ε) = lim
K→∞
Ni(ε)

K
(1.6)

представляет собой вероятность того, что наугад взятая точка из множества
находится в ячейке i.
Из условия нормировки вероятностей следует, что
N(ε)
i=1
pi(ε) = 1.
Введем в рассмотрение обобщенную статистическую сумму

Z(q,ε), характеризуемую показателем степени q, который может принимать
любые значения в интервале −∞ < q < +∞:

Z(q,ε) =

N(ε)
i=1
pq
i (ε).
(1.7)

Определение 1.1.
Спектром обобщенных фрактальных размерностей Реньи Dq, характеризующих распределение точек в области
L, называется совокупность величин

Dq = τ(q)

q − 1,
(1.8а)

где

τ(q) = lim
ε→0
ln Z(q,ε)

ln ε
.
(1.8б)

Если Dq = Df = const, т.e. не зависит от q, то данное множество точек
представляет собой обычный, регулярный фрактал, который характеризуется всего лишь одной величиной — фрактальной размерностью Df. Напротив, если функция Dq как-то меняется с q, то рассматриваемое множество
точек является мультифракталом.
Таким образом, мультифрактал в общем случае характеризуется
некоторой нелинейной функцией τ(q), определяющей поведение статистической суммы Z(q,ε) при ε → 0:

Z(q,ε) =

N(ε)
i=1
pq
i (ε) ≈ ετ(q).
(1.9)

Рассмотрим, как ведет себя обобщенная статистическая сумма в случае
обычного регулярного фрактала с фрактальной размерностью Df. В этом
случае во всех занятых ячейках содержится одинаковое количество точек
ni(ε) = K/N(ε), т.e. фрактал является однородным. Тогда очевидно, что
относительные населенности всех ячеек pi(ε) = 1/N(ε) тоже одинаковы и

Основные положения теории фракталов и самоподобных процессов
9

обобщенная статистическая сумма принимает вид

Z(q,ε) = N 1−q(ε).
(1.10)

Учтем теперь, что согласно определению фрактальной размерности Df
число занятых ячеек при достаточно малом ε ведет себя следующим образом:
N(ε) ∼ ε−Df.
(1.11)

Подставляя (1.11) в (1.10) и сравнивая с (1.9), приходим к выводу, что
в случае обычного фрактала функция

τ(q) = (q − 1)Df,
(1.12)

т.е. является линейной. Тогда все Dq = q и действительно не зависят от q.
Для фрактала, все обобщенные фрактальные размерности Dq которого совпадают, часто используется термин «монофрактал».
Если распределение точек по ячейкам неодинаково, то фрактал является неоднородным, т.е. представляет из себя мультифрактал, и для его характеристики необходим целый спектр обобщенных фрактальных размерностей
Dq, число которых в общем случае бесконечно.
Для характеристики распределения точек необходимо знать не только функцию τ(q), но и ее производную, непосредственно вычисляемую из
выражений (1.8б) и (1.7):

dτ(q)

dq
= lim
ε→0

N(ε)
i=1
pq
i ln pi

ln ε

N(ε)
i=1

.
(1.13)

Эта производная имеет важный физический смысл. Если она не остается постоянной и меняется с q, то это означает, что мы имеем дело с мультифракталом.

1.1.3. Фрактальная размерность D0 и информационная
размерность D1

Выясним, какой физический смысл имеют обобщенные фрактальные
размерности Dq для некоторых значений q. Так, при q = 0 из выражения
(1.7) следует, что Z(0,ε) = N(ε).
С другой стороны, согласно формулам (1.9) и (1.8а)

Z(0,ε) ≈ ετ(0) = ε−D0.
(1.14)

Сопоставляя эти два равенства, приходим к соотношению N(ε) ≈ ε−D0.
Это означает, что величина D0 представляет собой обычную хаусдорфову

Г л а в а 1

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

D1 = lim
ε→0
1
ln ε

N(ε)
i=1
pi ln pi.
(1.15)

С точностью до знака сумма в этой формуле представляет собой энтропию
фрактального множества S(ε):

S(ε) = −

N(ε)
i=1
pi ln pi.

В результате обобщенная фрактальная размерность D1 связана с энтропией S(ε) соотношением

D1 = − lim
ε→0
S(ε)
ln ε .
(1.16)

Основываясь на подобных соображениях, Клод Шеннон обобщил понятие энтропии S на абстрактные задачи теории передачи и обработки информации. Для этих задач энтропия стала мерой количества информации,
необходимой для определения системы в некотором состоянии i. Другими
словами, она является мерой нашего незнания о системе. Возвращаясь к исходной задаче о распределении точек на фрактальном множестве L, можно
сказать, что поскольку

S(ε) ≈ ε−D1,
(1.17)

величина D1 характеризует информацию, необходимую для определения
местоположения точки в некоторой ячейке.
В связи с этим обобщенную
фрактальную размерность D1 часто называют информационной размерностью. Она показывает, как информация, необходимая для определения местоположения точки, возрастает при стремлении размера ячейки ε
к нулю.
Свойства функции Dq. Как мы уже говорили, мультифрактал характеризуется неоднородным распределением точек по ячейкам. В то же
время, если бы точки, составляющие мультифрактал, были бы распределены по нему равномерно по всем N(ε) ячейкам с вероятностью pi = 1/N(ε),
энтропия такого распределения была бы максимальна и равна

Smax(ε) = −

N(ε)
i=1
pi ln pi = ln N(ε) ≈ −D0 ln ε.
(1.18)

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