Автоматизация многокритериального выбора оптимального решения при планировании сетей мобильной связи

АВТОМАТИЗАЦИЯ МНОГОКРИТЕРИАЛЬНОГО ВЫБОРА ОПТИМАЛЬНОГО РЕШЕНИЯ ПРИ ПЛАНИРОВАНИИ СЕТЕЙ МОБИЛЬНОЙ СВЯЗИ

ЧЕБОТАРЁВА Д.В., БЕЗРУКВ.М._____________

Рассматриваются методы многокритериальной оптимизации, которые могут быть использованы при планировании сетей мобильной связи. Описываются практические аспекты выбора оптимальных проектных решений с использованием созданного программного средства для выбора оптимального варианта с учетом совокупности показателей качества.

Введение

В процессе планирования сети мобильной связи (СМС) необходимо учитывать противоречивые технико-экономические требования оператора. Для этого используется совокупность показателей качества, что определяет необходимость применения методов многокритериальной оптимизации при выборе оптимальных проектных решений. Многокритериальный подход в проектировании систем достаточно развит в различных технических отраслях. Однако в существующих методах и программных средствах планирование СМС не рассматривается как задача многокритериальной оптимизации [1-3]. Это определяет актуальность исследования таких вопросов. Кроме того, актуальной задачей является также автоматизация проектирования, включающая создание программных средств для реализации методов многокритериального выбора оптимальных проектных вариантов СМС. При этом удовлетворяются требования сокращения сроков и затрат на планирование СМС.

В данной статье приведены некоторые результаты исследования особенностей решения задач многокритериальной оптимизации проектных решений при планировании СМС. Рассмотрены практические аспекты выбора оптимальных проектных решений с использованием созданного программного средства.

1. Методы выбора оптимальных проектных вариантов с учетом совокупности показателей качества

Часто вследствие плохих исходных представлений об оптимальности проектных вариантов невозможно в формализованном виде установить скалярный

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

к

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

Наиболее популярным является метод дискретного выбора подмножества Парето, при котором формализованная процедура получения подмножества Парето-оптимальных проектных вариантов в критериальном пространстве V = к(Фa) определяется путем дискретного перебора и сравнения вариантов согласно соотношению [4]

P

Отсюда следует, что подмножество Парето-оптимальных проектных вариантов включает недоминируемые варианты, для которых отсутствуют варианты, предпочтительные по бинарному отношению нестрогого предпочтения - безусловному критерию Парето.

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

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

Нахождение оптимальных по критерию Парето проектных вариантов системы может осуществляться либо непосредственно согласно (2) на множестве допустимых вариантов Фд , либо с использованием специальных методов, например, весового метода, метода рабочих характеристик, метода последовательных уступок[4,5].

Формальная модель задачи Парето-оптимизации не содержит информации для выбора единственного варианта. Множество допустимых проектных вариантов сужается лишь к подмножеству Парето-оптимальных решений путем исключения безусловно худших вариантов по безусловному критерию предпочтения - критерию оптимальности Парето.

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

Выбор единственного проектного варианта из подмножества Парето может быть выполнен с помощью любого из существующих методов, основанных на скалярной функции ценности, на теории

размытых множеств, на лексикографических отношениях [4,5]. В основу разработанного программного средства лег метод выбора единственного проектного варианта из подмножества Парето с использованием скалярной функции ценности. Это один из наиболее часто используемых методов сужения подмножества Парето-оптимальных решений до единственного проектного варианта. Он основан на формировании скалярной функции ценности F(kj,..,km) m переменных. Выбирается такая функция, значениям которой соответствует бинарное отношение f в случае, если для произвольных оценок k , k є V неравенство F(k) > F(k ) выполняется тогда и только тогда,

когда выполняется бинарное отношение k f k . Функция ценности может иметь вид

m

F

j=1

где Cj коэффициенты, определяющие относительную важность соответствующих показателей качества, fj(kj) одномерные функции ценности, которые являются оценками ценности варианта системы ф с точки зрения показателя качества k j (ф).

2. Результаты исследования методов многокритериального выбора при планировании СМС

Процесс выбора оптимальных проектных вариантов при планировании радиосети СМС с учетом совокупности показателей качества выполняется в несколько этапов:

- задание набора исходных данных для допустимых проектных вариантов СМС, включающих: радиостандарт, занимаемую полосу частот, число активных абонентов, площадь покрытия, сектори-зацию и высоту антенн, мощности передатчиков базовых станций, параметры затухания радиоволн;

- определение множества допустимых проектных вариантов с учетом ограничений на структуру и параметры СМС;

- задание показателей показателей качества СМС и вычисление их значений для допустимых проектных вариантов;

- выбор подмножества Парето-оптимальных проектных вариантов СМС в критериальном пространстве оценок значений показателей качества;

- анализ полученных Парето-оптимальных проектных вариантов, многомерных потенциальных ха-

рактеристик и многомерных диаграмм обмена показателей качества СМС;

- формирование условного критерия предпочтения с привлечением полученной дополнительной информации и выбор единственного проектного варианта СМС.

Указанные процедуры реализованы в виде специального программного комплекса, состоящего из двух частей [5].

Первая часть программного комплекса реализована в среде MathCad. Она решает следующие задачи: задание исходных данных для всех допустимых вариантов сетей, расчет основных параметров СМС, нормирование и приведение данных к стандартному виду, составление таблицы оценок совокупности показателей качества для допустимого множества вариантов СМС.

Результаты всех расчетов программа транспортирует в текстовый файл «mL.txt», который используется второй частью программного комплекса.

Вторая часть программного комплекса реализована в среде Delphi. Она производит выбор подмножества Парето-оптимальных вариантов СМС в критериальном пространстве и сужение множества Парето до единственного варианта построения сети.

На рисунке для иллюстрации представлена часть интерфейса программы выбора оптимальных проектных вариантов сотовых сетей мобильной связи с учетом совокупности показателей качества.

Интерфейс программы многкритериальноговыбора оптимальных проектных вариантов СМС

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

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

Созданный программный комплекс выбора оптимальных проектных вариантов СМС с учетом совокупности показателей качества был использован для решения задачи оптимизации СМС на номинальном этапе планирования радиосети стандарта GSM [5].

В первой части программы было сформировано множество из 100 допустимых вариантов СМС, отличающихся разными исходными данными: планируемым количеством абонентов в сети, размером площади покрытия, активностью абонентов в час наибольшей нагрузки, занимаемой полосой частот, размерами кластеров; возможной вероятностью блокировки вызовов и процентом времени ухудшения качества связи. Были найдены оценки значений всех возможных показателей качества, выполнено их нормирование и приведение к сопоставимому виду. Множество вариантов было представлено в критериальном пространстве оценок введенных показателей качества. Перечень всех параметров СМС, которые могут быть использованы как показатели качества, представлен в табл. 1. При исследованиях применялись разные наборы показателей качества из указанного перечня. В частности, при решении одной из задач оптимизации СМС были выбраны следующие показатели качества: kb k2, k5, k8 k10, k12.

С помощью второй части программы по критерию Парето (2) было выделено подмножество, включающее 71 вариант сети, т.е. исключено из рассмотрения 29 безусловно худших вариантов. Из условия минимума условного критерия предпочтения (3) из подмножества Парето выбран единственный вариант (J№ 72). Он характеризуется следующими данными: количество абонентов - 30000; площадь обслуживания - 320 км2; активность абонентов - 0,025 Эрл; занимаемая полоса частот -4 MHz; возможная вероятность блокировки вызова

- 0,01; процент времени ухудшения качества связи

- 0,07; плотность обслуживания - 94 активных або-

2

нентов на км ; размер кластера - 7 сот; количество базовых станций в сети - 133; количество абонентов, обслуживаемых одной базовой станцией - 226; телефонная нагрузка - 3,326 Эрл; вероятность ошибки - 5,277-10-7.

Таблица 1

Параметры СМС Показатели качества

Na / S0 - плотность обслуживаемых абонентов k1

Pom - допустимая вероятность ошибки k2

Nk - общее количество частотных каналов в сети k3

А - допустимая телефонная нагрузка k4

Na BTS - число абонентов, обслуживаемых одной BTS k5

N BTS - необходимое количество базовых станций k6

R - радиус соты k7

Y - эффективность использования радиочастотного спектра k8

Na - число обслуживаемых абонентов k9

S0 - площадь обслуживаемой территории k10

в - активность одного абонента в час наибольшей нагрузки kn

P^ - допустимая вероятность блокирования вызова k12

Pt - процент времени, в течение которого допускается, чтобы отношение сигнал/помеха на входе приемника мобильной станции было меньше защитного отношения k13

AFc - полоса частот базовых станций на передачу k14

Кроме того, с помощью разработанного программного комплекса исследованы результаты многокритериальной оптимизации СМС для разных наборов показателей качества. Эти результаты приведены в табл. 2, в которой указаны количество и тип показателей качества, а также соответствующее им число безусловно худших и Парето-оптимальных вариантов из рассматриваемых 100 допустимых вариантов СМС.

Таблица 2

Количе- Совокуп- Число Число

ство пока- ность пока- безусловно Парето-

зателей зателей худших оптимальных

качества качества вариантов вариантов

5 kb k2j k5j k8, k12 52 48

5 k4, k6, k7, k9, k14 64 36

3 k4, k5, k11 84 16

3 k6, k9, k12 86 14

3 k4j k10j k14 87 13

2 k4, k8 90 10

2 k2, k12 96 4

2 k1, k8 96 4

2 k4, k5 97 3

По результатам исследований сделан следующий вывод. Чем меньше заданное количество показателей качества, с учетом которых проводится оптимизация сетей, тем больше число безусловно худших вариантов и, соответственно, меньше число Парето-оптимальных вариантов СМС.

Были проведены также исследования многокритериального выбора единственного варианта из подмножества Парето с использованием условного критерия предпочтения (3) при различных значениях весовых коэффициентов относительной важности показателей качества (табл. 3).

Таблица 3

№ опы -та Показатели качества Номер лучшего варианта

к1 k2 k5 k8 k10 k12

Весовые коэффициенты относительной важности

1 0,17 0,17 0,17 0,17 0,17 0,17 № 72

2 0,2 0,2 0,1 0,1 0,1 0,3 № 82

3 0,1 0,2 0,1 0,3 0,1 0,2 № 72

4 0,1 0,1 0,1 0,1 0,5 0,1 № 59

5 0,1 0,1 0,5 0,1 0,1 0,1 № 63

6 0,2 0,3 0,05 0,05 0,2 0,2 № 82

7 0,1 0,25 0,25 0,1 0,1 0,2 № 47

Из табл. 3 видно, что большое влияние на результат оптимизации оказывает выбор весовых коэффициентов относительной важности показателей качества. При одной и той же совокупности показателей качества, но различных значениях весовых коэффициентов, выбираемый разный единственный вариант.

Значения весовых коэффициентов относительной важности показателей качества задаются с использованием дополнительной субъективной информации от экспертов с применением специальных методов: метода экспертного оценивания, метода Саати. [5].

Выводы

Методы многокритериального выбора оптимальных проектных решений реализованы в созданном программном комплексе, который может быть использован для автоматизации проектирования СМС на этапе номинального планирования радиосети.

С помощью разработанного программного комплекса исследованы особенности решения многокритериальной задачи оптимизации на этапе номинального планирования сетей мобильной связи.

Литература: 1. Mishra A.R. Advanced Cellular Network Planning and Optimisation. 2G/2.5G/3G Evolution TO 4G. /Edited by Ajay R. Mishra. UK: John Wiley & Sons Ltd, 2007. 542 р. 2. Granat J., Wierzbicki A.P. Multicriteria analysis in telecommunications // Proceedings of the 37th Hawaii International Conference on System Sciences. 2004. Р. 1-6. 3.

UMTS Radio Network Planning, Optimization and QOS Management. For Practical Engineering Tasks / Edited by J. Lempidinen and M. Manninen. Dordrecht: Kluwer Academic Publishers, 2004. 343 p. 4. Ногин, В.Д. Принятие решений в многокритериальной среде: количественный подход. М.: ФИЗМАТЛИТ, 2002. 176с. 5. Чеботарёва Д.В., Безрук В.М. Многокритериальная оптимизация проектных решений при планировании сотовых сетей мобильной связи. Х.: Компания СМИТ, 2013. 148с.

Поступила в редколлегию 10.03.2014 Рецензент: д-р техн. наук, проф. Баранник В.В.

Чеботарёва Дарья Васильевна, канд. техн. наук, доцент кафедры «Сети связи» ХНУРЕ. Научные интересы: планирование и проектирование сетей мобильной связи, многокритериальная оптимизация сетей связи. Адрес: Украина, 61166, Харьков, пр. Ленина, 14. E-mail: dasha-che@ukr.net. Контактный телефон: +380-57-702-14-29.

Безрук Валерий Михайлович, д-р техн. наук, профессор, заведующий кафедрой «Сети связи» ХНУРЕ. Научные ит-нтересы: статистические методы обработки и распознавания сигналов, автоматизация проектирования сетей связи, многокритериальная оптимизация сложных технических систем, математическое моделирование и оптимизация сетей связи. Адрес: Украина, 61166, Харьков, пр. Ленина, 14. Email: bezruk@kture.kharkov.ua. Контактный телефон: +38067-722-31-18.