USING OF ALGORITHMS OF CLUSTERIZATION FOR FINDING NODES OF DEMAND IN MOBILE NETWORKS

Full Text

В процессе функционирования систем мобильной связи возникают резкие перегрузки в отдельных ее сегментах, обусловленные перемещением абонентов, что вызывает необходимость оперативного управления радиоресурсами. Так, в случае перегрузки сети в одной части зоны обслуживания, могут быть задействованы ресурсы из менее загруженной ее части [1]. Для эффективного управления радиоресурсами системы сотовой связи необходимо позиционировать мобильные станции (МС) с точностью, позволяющей выявлять зоны аномального изменения концентрации [2]. Функция позиционирования (местоопределения) МС в сетях оператора сотовой связи является актуальной проблемой современной науки и может стать универсальным инструментом для решения целого ряда задач, напрямую не связанных с услугами связи [3]. Полученные в результате позиционирования массы абонентов представляют собой большие массивы. Обрабатывать каждого абонента не представляется возможным. С точки зрения эффективного управления необходимо объединить всех абонентов в конгломерации, удобные для дальнейшего управления. Центрами таких конгломераций будут виртуальные узлы спроса (центры кластеров), в которых сконцентрирована совокупная нагрузка от МС абонентов. Количество узлов спроса резко отлично от количества всех абонентов в пространстве, что облегчит задачу подключения кластеров (узлов спроса) к существующим базовым станциям. Постановка задачи На сегодняшний день известно [4] большое количество алгоритмов четкой и нечеткой кластеризации. Каждый алгоритм является не просто инструментом, выдающим ответ, но и несколько разных ответов в течение пересчета десятков итераций. Рассматриваемая задача подразумевает ряд ограничений, границ применимости, которые необходимо использовать как критерий при выборе оптимального алгоритма в спектре реальных. В условиях пространственно-временного изменения нагрузки на сеть подвижной связи, наиболее эффективным будет алгоритм, подобранный по следующим параметрам: - способный работать с нечеткими множествами; - инвариантный к способу и началу счета; - определяющий минимальное число ответов; - выявляющий ответ за минимальное число итераций. Нечеткие (или пересекающиеся) алгоритмы каждому объекту ставят в соответствие набор вещественных значений, показывающих степень отношения объекта к кластерам. Каждый объект относится к каждому кластеру с некоторой вероятностью, что полностью отражает картину перемещения любого из абонентов сети радиосвязи в любой момент времени и учитывает пространственно-временное изменение нагрузки на сеть оператора связи. Второе ограничение связано с тем, что пространственно-временной характер нагрузки не позволяет начинать пересчет каждого случая распределения абонентов с одного и того же места (утром и вечером, летом и зимой характер нагрузки в пространстве меняется с перемещением абонентов). Решение задачи кластеризации принципиально неоднозначно, причинами являются: - не существует однозначно наилучшего критерия качества кластеризации. Известен целый ряд эвристических критериев, а также ряд алгоритмов, не имеющих четко выраженного критерия, но осуществляющих достаточно разумную кластеризацию «по построению». Все они могут давать разные результаты; - число кластеров, как правило, неизвестно заранее и устанавливается в соответствии с некоторым субъективным критерием; - результат кластеризации существенно зависит от метрики, выбор которой, также субъективен и определяется экспертом. В процессе моделирования оказалось, что алгоритм FCM (Fuzzy Classifier Means, Fuzzy C-Means) выдает до четырех ответов на одном и том же массиве данных [5]. Последнее ограничение является наиболее важным, так как изучаемые области изменяются во времени и ответ должен быть получен до рассыпания кластера. Из всего спектра алгоритмов кластеризации, благодаря указанным ограничениям, можно выделить два основных - алгоритм Густафсона-Кесселя и алгоритм FCM [6]. Таблица 1. Сравнение алгоритмов нечеткой кластеризации Алгоритм FCM Алгоритм Густафсона-Кесселя Шаг 1. Устанавливаются параметры алгоритма: количество кластеров, экспоненциальный вес, параметр остановки алгоритма. Шаг 2. Случайным образом генерируется матрица нечеткого разбиения. Шаг 3. Рассчитывается центр кластеров. Шаг 3. Вычисляется «центр масс» для каждого кластера. Шаг 4. Рассчитывается расстояние между центрами кластеров. Шаг 4. Вычисляется матрица ковариаций. Шаг 5. Для всех кластеров вычисляется расстояние. Сравнение полученных результатов с заданными параметрами и пересчет, при необходимости. Как видно из таблицы 1, второй алгоритм имеет на одно действие больше, что может привести к значительным задержкам в расчетах и увеличению вычислительных мощностей. Для выявления наиболее подходящего алгоритма требуется математическое и компьютерное моделирование. Решение задачи Данные алгоритмы имеют ряд недостатков [7]: - нечеткая кластеризация имеет в своей основе работу по перебору одних и тех же данных из большого массива данных, что приводит к значительному увеличению времени обработки данных; - в случае большого количества исходных точек (моделируемое количество абонентов радиосети), вычислительные мощности обычных ЭВМ не справляются с поставленной задачей; - алгоритм не дает четкого представления о границах раздела кластеров, так как пограничные абоненты могут относиться сразу к нескольким кластерам. Моделирование задачи происходило в среде программирования C+. В процессе компьютерного моделирования все эти утверждения были доказаны и приведены в [4-5], а по результатам моделирования была зарегистрирована программа для ЭВМ [7]. В программе использовался один алгоритм FCM. Позже программа была доработана - был добавлен алгоритм Густафсона-Кесселя. На рис. 1а представлен результат работы обновленной программы на три кластера с помощью алгоритма FCM, а на рис. 1б - результат пересчета того же примера для алгоритма Густафсона-Кесселя. Как видно из рис. 1, алгоритмы дают разные ответы в пространстве. Это связано с недостатками эвристического подхода к выбору критерия качества кластеризации, при четком математическом алгоритме расчета.Наиболее интересным представляется количество итераций, потраченных алгоритмами для предоставления визуализированного результата на экране компьютера. Для 100 точек алгоритм FCM затратил 14 итераций, в то время как алгоритм Густафсона-Кесселя - 190. При дальнейшем увеличении числа абонентов первый алгоритм показал незначительное увеличение числа итераций, по сравнению со вторым. а) б) Рис. 1. Результат компьютерного моделирования алгоритмов нечеткой кластеризации Результаты сравнения работы алгоритмов приведены на рис. 2-3. Из рис. 3 отчетливо видно, что алгоритм FCM менее ресурсоемкий. Таким образом, утверждение о том, что наличие большего числа шагов в алгоритме Густафсона-Кесселя приведет к значительным задержкам в расчетах и увеличению вычислительных мощностей доказано. а) б) Рис. 2. Сравнение работы алгоритмов а) при изменяющемся числе абонентов сети; б) при изменяющемся числе кластеров Выводы Задача выбора нечетких методов (алгоритмов) разбиения в сетях подвижной связи является не новой [10], однако, в условиях физической реализуемости той или иной задачи, практическая составляющая имеет высокий интерес со стороны эксплуатирующих организаций. В данной статье было доказано, что из двух алгоритмов нечеткой кластеризации наиболее подходящим для решения задачи динамической кластеризации абонентов сети подвижной связи является Fuzzy Classifier Means. Он работает достаточно быстро (ответ был получен в среднем за 1 с вычислений) в условиях изменяющейся нагрузки, выражающейся как в количестве абонентов, так и в числе самих узлов спроса.

About the authors

Kirill Nikolaevich Zotov

Ufa State Aviation Technical University

Email: zkn2002@inbox.ru

Ruslan Rimovich Zhdanov

Ufa State Aviation Technical University

Email: tks@ugatu.ac.ru

Anton Evgenievich Kiselev

Ufa State Aviation Technical University

Email: tks@ugatu.ac.ru

Arkadiy Mikchailovich Komissarov

Ufa State Aviation Technical University

Email: tks@ugatu.ac.ru

Igor Vasilyevich Kuznetzov

Ufa State Aviation Technical University

Email: tks@ugatu.ac.ru

References

Supplementary files