Обработка сигналов в системах телекоммуникаций (стр. 4 )

Наличие гипотез о стратегических связях может быть выявлено на основании:

 существования функциональной связи между показателями, которую можно представить математически;

 наличия существенной корреляционной связи между показателями, оцененной коэффициентом корреляции, выявленном методами статистического или детерминированного факторного анализа;

 очевидности логической взаимосвязи между показателями.

Процесс установления устойчивых причинно-следственных связей с целью обеспечения сбалансированности и непротиворечивости показателей, формирующими структуру системы OSS/BSS, основывается на допущении необходимого и достаточного количества управляемых показателей и на их разумной оптимизации по балансу «необходимый минимум — наибольший вклад в достижение целей» при этом функциональный подход дополняется целевым..

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

 

The analysis of correlation communications between key indicators

Girev A.

PSUTI

Are analyzed not only those indicators between which there are obvious functional communications that is characteristic for physical level in system rigid hardware-programmed control, but also those indicators, communication between which difficultly formally to describe. That is, insufficiently simply to calculate KPI, it is necessary to generate cause-and-effect relationships which reflect mutual correlation of the various purposes.

¾¾¾¾¾¨¾¾¾¾¾

 

«ПРИРОДНЫЕ ВЫЧИСЛЕНИЯ» КАК СПОСОБ РЕШЕНИЯ СЛОЖНЫХ ЗАДАЧ В ТЕЛЕКОММУНИКАЦИЯХ

ГОУВПО ПГУТИ

Постоянное развитие телекоммуникационных сетей приводит к появлению все новых технологий в области связи. Так, например, еще не во всех странах созданы сети 3G, а уже появились стандарты для сетей 4G и проводятся лабораторные испытания над ними. По заявлению разработчиков, сети 4G будут базироваться на одной из следующих технологий: LTE, UMB, WIMAX. А скорее всего, на их совместном использовании. Соответственно, при создании широкополосных сетей нового поколения, возникает задача оптимального размещения базовых станций, рассмотренная в [1, 2]. Решение задачи проводится по критерию минимизации целевой функции стоимости, при этом особое внимание уделяется обеспечению параметров качества обслуживания QoS. Поскольку данная проблема NP-полная и для нее не существует хорошего алгоритма, дающего точное решение за полиномиальное время (по крайне мере, на данном этапе развития современной науки), то в [2] было предложено решить ее с помощью одной из эвристических методик – «природные вычисления» (natural computing), а именно, генетического подхода. Задачи класса NP интересны тем, что если для одной из них имеется алгоритм, обладающий достаточно хорошими характеристиками, то при правильной интерпретации его можно использовать и для решения других задач. В частности для подтверждения преимущества генетического алгоритма, было написано программное обеспечение, решающее задачу коммивояжера [3]. Задача коммивояжера – это стандартный тестовый полигон, используемый при отладке новых методов оптимизации. В [3] были приведены результаты тестирования данной программы над простыми задачами коммивояжера, созданными с помощью случайного генератора. Данные экспериментов показали преимущество генетического подхода, выраженное в большей точности получаемого решения за меньшее время, по сравнению с классическими методами.

В работе, представленной данным докладом, продолжилось тестирование вышеупомянутой программы над гораздо более трудными геометрическими задачами, взятыми из [4]. Результаты приведены в таблице 1.

Таблица 1 – Результаты экспериментов для задачи коммивояжера

Задача	berlin 52	eil 51	eil 101	kroA 100	lin 105	rat 99
Длина	7572,9	430,4	654,3	21937,5	14745,8	1232,5
Длина опт	7542	426	629	21282	14379	1211
Относительная погрешность	0,4 %	1,03 %	4,02 %	3,08%	2,55 %	1,76 %
Время, сек	166	34	235	262	116	339

Числа в названии задачи означают количество городов. В строке «Длина» указаны длины наилучших маршрутов, полученные в данной программе. В строке «Длина опт» приведены точные оптимальные значения длин маршрутов для данных задач. Строка «Время» отражает затраченное время на решение этих задач в секундах. В строке «Относительная погрешность» указаны погрешности решенных задач, вычисленные по формуле . Как видно из таблицы, погрешность не превосходит 5 %, что говорит о хорошей работе генетического подхода.

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

Таблица 2 – Время работы генетического алгоритма

	10	20	30	40	50	60	70	120	150	200
Время	1	1	2	3	4	5	6	17	25	44

Продолжением исследований, приведенных в [1,2] и в данном докладе, является возможность применения «муравьиных» алгоритмов для решения задачи оптимального размещения базовых станций. Это направление «природных вычислений» сравнительно молодое, оно появилось в начале 90-х годов 20 века, автором является Марко Дориго [5]. На данный момент с помощью муравьиных алгоритмов решены многие задачи комбинаторной оптимизации. Результаты экспериментов говорят о преимуществе данного метода по сравнению с другими эвристиками: имитация отжига, эластичная сеть, генетические алгоритмы и др.

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

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