Информационные системы и технологии
МАТЕМАТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ
УДК 004.72
А.Ю. ОСТРИКОВ
АЛГОРИТМ СИНТЕЗА СЕТИ АБОНЕНТСКОГО ДОСТУПА
C УЧЕТОМ ХАРАКТЕРА МОБИЛЬНОСТИ ПОЛЬЗОВАТЕЛЕЙ
Статья посвящена вопросам структурного синтеза сети абонентского доступа с
учетом динамики поведения абонентов. Автором предложен алгоритм синтеза, основанный
на решении задачи многомерной кластеризации методом k-средних. Проведена сравнительная
оценка эффективности решений, полученных при помощи классических алгоритмов синтеза
радиально-узловых структур (COM, Drop, R-структур) и предлагаемого алгоритма.
Ключевые слова: структурный синтез; сеть абонентского доступа; точка доступа;
кластеризация; алгоритм.
Article is devoted to user's access network structural synthesis with view in dynamics
behaviour of subscribers. Authors offer a algorithm based on the decision of multivariate
clusterization problem by k-averages method. The comparative estimation of efficiency by classical
synthesis algorithms for structures (COM, Drop, R-structure) and offered algorithm are leaded.
Keywords: structural synthesis; user's access network; point of access; clusterization;
algorithm.
ВВЕДЕНИЕ
На сегодняшний день неотъемлемым атрибутом конвергированных
инфокоммуникационных сетей является возможность обеспечения услуг с
использованием различных технологий доступа, в том числе, и мобильных [1, 6, 8].
Налицо изменение приоритетов на рынке инфокоммуникаций как со стороны
операторов фиксированной проводной связи, так и операторов мобильного сегмента.
Если первые расширяют спектр своих возможностей за счет внедрения устройств
радио доступа (Wi-Fi Router, точки доступа WiMax), то вторые непрерывно
совершенствуют технологии, позволяющие предоставлять высокоскоростные услуги,
характерные для проводных технологий.
Эти тенденции ведут к непременной смене парадигмы в области
сетей
проектирования
и
принципов
их
организации. Современные
инфокоммуникационные сети не только должны быть масштабируемыми и гибкими,
но и обладать свойством некой технической инерции. Другими словами на этапе
проектирования сети должны учитываться возможные траектории динамически
изменяемых условий, например, передвижение абонентов, изменяемая нагрузка и т.д.
С этой точки зрения наиболее важным аспектом является построение сети
абонентского доступа.
Данная статья содержит отдельные результаты исследований
связанные с вопросами проектирования современных инфокоммуникационных сетей.
ПОСТАНОВКА ЗАДАЧИ
Задача синтеза сети абонентского доступа сводится к выбору мест размещения
точек доступа и определения их характеристик. В качестве целевого эффекта при
построении сети выступает качество обслуживания, показателем которого с учетом
№ 6(62)2010
5
автора,
Стр.1
Научно-технический журнал
специфики абонентских сетей выступает вероятность доступности с требуемыми
параметрами (интенсивностями потоков). Таким образом, формальная постановка
задачи синтеза сети абонентского доступа может быть представлена в виде (1):
∑λ j) ≤
i
nC С
ТД
где тд
i
P (R ,λ ,t)
≤
i
дост
ТД
i
i( Λ , j =1 ..n
АС
i →max
j
,
R – расстояние i-го абонента до точки доступа;
i
λ – интенсивность потока от i-го абонента;
j
С – стоимость точки доступа.
C – нормативная стоимость абонентской сети;
ТД
Λ – максимально возможная нагрузка j -ой точки доступа;
АС
(1)
АНАЛИТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
СЕТИ АБОНЕНТСКОГО ДОСТУПА
В качестве прототипа модели синтеза сети абонентского доступа целесообразно
использовать аналитические решения задач кластеризации. Из существующих
методов наиболее адекватен условиям решаемой задачи метод k-средних [7],
принадлежащий группе итеративных методов кластеризации эталонного типа,
поскольку он позволяет разбить исходное множество на то количество кластеров,
которое задано исходными данными (например, количеством точек доступа).
Кроме того, метод k-средних использует два критерия разбиений исходного
множества: первый определяет меру сходства объектов (например, эвклидово
расстояние), а второй – мощность сформированных кластеров, обеспечивающий
равномерность их заполнения, что и отвечает требованиям к построению сетей
абонентского доступа [4].
Пусть синтезируемая сеть должна предоставлять услуги n абонентам.
Географическое положение абонентов определяется координатами (x,y)n. Значение x и
значение y являются случайными величинами, каждая из которых характеризуется
плотностью функции распределения. События, определяющие местоположение
абонентов относительно координат x и y, являются независимыми и поэтому могут
быть описаны системой случайных величин с функцией распределения вероятности
вида [2, 5]:
f x y n
где f x n
( , ) = f1 x( )n ⋅ f y( ) n
2
,
1( ) , 2f y( ) n плотности функций распределения координат x и y для n –го
абонента.
Таким образом, плотность функции распределения для географического
положения абонента описывает поверхность распределения. Так, например, если в
качестве закона распределения координат определим нормальный закон,
характеризующийся математическим ожиданием mx, my и дисперсией dx, dy , тогда
поверхность распределения будет иметь вид, представленный на рисунке 1.
6
№ 6(62)2010
(2)
Стр.2
Информационные системы и технологии
абонента как объект кластеризации. Другим признаком является интенсивность
потока i
Вид поверхности распределения является одним из признаков, определяющий
λ порождаемого i -ым абонентом. Для уменьшения размерности пространства
решений целесообразно использование мультипликативной свертки двух признаков:
i
f x y ′ = f x y
( , )i
( , )i ⋅λ
.
(3)
Рисунок 1 – Вид поверхности распределения
Учитывая независимость признаков объектов в качестве меры сходства
целесообразно использовать евклидово расстояние между каждой парой
классифицируемых объектов [7]:
d ,i j = ρ ( , ) , ( , ) j
l
= ∑∑ −ix x ) k
i j =k 1
j
,
Для построения модели сети абонентского доступа воспользуемся
аналитическими выражениями метода К–средних [7, 9]. В соответствии с этим
методом из всего множества объектов выбираются эталоны E. Исходя из решаемой
задачи, количество эталонов кластеризации определяется количеством точек доступа,
концентрирующих нагрузку абонентской сети, а оно, в свою очередь, может быть
заданно в качестве стоимостного ограничения на синтез сети.
Процедура объединение объектов в кластеры определяется выражением (5):
f x y w f x y j
j
( , ) =
j
( , ) + f x y n
w +1
j
где j=1..e – номер кластера (при первой итерации за кластеры произвольно
принимаются e объектов из множества N);
№ 6(62)2010
7
( , ) +1
: d j n, 1+ →m ,ax
(5)
(f x y f x y
(
i
(yi
)=
2 + − y ) k + f xi yj ) − f xi y )) k
2
j
( ( ,
( ,
2
j
.
(4)
Стр.3
Научно-технический журнал
w – коэффициент, учитывающий количество входящих в кластер объектов.
В результате m итераций, образующих устойчивые кластеры, формируются
e объектов, характеризующихся приведенными плотностями функций распределения
e
f x y),(
e
. Математическое ожидание и значение этой функции в точке
математического ожидания определяют наиболее вероятное место географического
положения концентрирующего элемента сети абонентского доступа (точки доступа),
для которого рассчитываются характеристики потока, исходя из модели источника
нагрузки.
В общем случае поток концентратора рассчитывается как сумма потоков всех
терминалов, входящих в один кластер с концентратором (6) (7):
Λ = ∑λ .
n∈E j
вх
j
исх
j
вх
n
Λ = ∑λ
n∈Ej
исх
n
(6)
(7)
Специфика поведения пользователей предполагает решение задачи в динамике.
Для этого необходимо определить временные интервалы, в пределах которых будет
выполнен расчет конфигурации сети, а затем объединить частные решения в единое
общее.
В связи с этим нагрузка абонента будет задаваться не интенсивностью и
некоторым профилем λ(t ) . Анализ литературы [3, 8] показал целесообразность
p i
выбора временных интервалов размером астрономического часа.
АЛГОРИТМ СИНТЕЗА СЕТИ АБОНЕНТСКОГО ДОСТУПА
На основании предложенной математической модели, алгоритм синтеза сети
абонентского доступа может быть представлен в виде блок-схемы (рис. 2).
В качестве исходных данных задаются (бл.1):
– характер мобильности пользователя (функция
f ( , )yx
интервалах pt ;
– профиль нагрузки абонентского терминала (λ t ) ;
( )p
– количество точек доступа K.
В совокупности признаки 1 и 2 определяют метрическое пространство,
содержащее n объектов (абонентских терминалов).
В блоке 2 (рис. 2) для каждого терминала производится нормирование
характеристики профиля нагрузки, а затем осуществляется мультипликативная
свертка параметров
f ( , )yx
и λ( )t (блок 3) .
формируется совокупность
В итоге для каждого терминала на выделенных временных интервалах
f x y),(
значений обобщенного признака
t p
i
,
характеризующего как мобильность, так и интенсивность нагрузки объекта (рис. 3).
В блоках 5-8 алгоритма производится кластеризация объектов на заданные K
кластеров методом k-средних в пределах каждого временного интервала p
результате чего образуется множество новых объектов с признаками F x y),(
k K..1=
ср
k
,
8
p ..1=
T , T – количество рассматриваемых временных интервалов.
№ 6(62)2010
t , в
p , где
) на временных
Стр.4