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

Abstract


In this article, the main algorithms of fuzziness clusterization for determination nodes of demand in mobile radio networks are compared. Identification of the most suitable algorithm for dynamic finding of nodes of demand in the conditions of abnormal zones of spatial-time changes of traffic transmitting (change of loading) is necessary for fast redistribution of a final radio-frequency resource of base stations, communication channels and computing powers of the provider. Each algorithm of an accurate and fuzzy clustering is the unique mathematical tool capable to analyze traffic on the modern telecommunication. At the same time, all algorithms have applicability boundaries in real implementation - the calculation speed, feature of a choice of boundaries of fuzziness, a choice of a metrics of belonging to some cluster and the whole range of heuristic criteria for the solution of real physical tasks. Comparing of two algorithms of a fuzziness clustering revealed that Fuzzy C-Means works quicker in the conditions of the increasing traffic, than Gustafsson-Kessel's algorithm. Simulation was made for two cases: increase of number of subscribers and increase of quantity of clusters in case of invariable number of subscribers.

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

  1. Стрельникова Л.В., Зотов К.Н., Кузнецов И.В., Жданов Р.Р., Применение методов нечеткой кластеризации для эффективного управления ресурсами сотовой связи // Международный научно-исследовательский журнал. №2-1(33), 2015. С. 86-87.
  2. Зотов К.Н. Разработка алгоритма повышения точности позиционирования мобильных станций на основе расчета статических параметров электромагнитного поля в неоднородной среде // Вестник УГАТУ. Т.17, №2(55), Уфа, 2013. - С. 14-19.
  3. Воробьев Н.П., Сошников А.А., Титов Е.В. Использование компьютерного моделирования для оценки электромагнитных загрязнений // Ползуновский вестник. №4, 2009. - С.31-33.
  4. Зотов К.Н. Повышение эффективности систем сотовой связи на основе релевантной кластеризации местоположения мобильной связи. Автореф. дис. к.т.н. Уфа, 2014. - 16 с.
  5. Зотов К.Н., Кузнецов И.В., Салов А.С., Симбирцева Д.С., Стрельникова Л.В., Разработка алгоритмов кластерного анализа концентрации абонентских устройств в системах мобильной связи // Электротехнические и информационные комплексы и системы. Т.11, №1, 2015. - С. 90-96.
  6. Gustafson D.E., Kessel W.C. Fuzzy clustering with a fuzzy covariance matrix // Scientific Systems. Inc. 186 Alewife Brook Parkway Cambridge, Massachusets, 1978. - Р. 761-766.
  7. Программа расчета узлов спроса на основе кластерного анализа местоположения абонентов в сетях сотовой связи // Рег. № 2014613981.
  8. Султанов А.Х., Кузнецов И.В., Камалов А.Э. Об одном методе прогноза оптимальной зоны радиопокрытия сети мобильной связи // Вестник УГАТУ. Т.14, №1(36), 2010. - 62-67.
  9. Блохин В.В., Кузнецов И.В., Султанов А.Х. Координированное планирование частотного ресурса в системах радиосвязи топологическим методом // Вестник УГАТУ. Т.11, №2, 2008. - 178-181.
  10. Вятченин Д. А. Нечеткие методы автоматической классификации. Минск: Технопринт, 2004. - 219 с.

Statistics

Views

Abstract - 15

PDF (Russian) - 1

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions


Copyright (c) 2017 Zotov K.N., Zhdanov R.R., Kiselev A.E., Komissarov A.M., Kuznetzov I.V.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies