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

Постановка задачи

Свое название сотовые сети (сети) связи получили в соответствии с сотовым принципом организации связи, согласно которому зона обслуживания (территория города или региона) делится на большое число малых рабочих зон, или сот [1]. В центре каждой соты расположена базовая приемопередающая станция (BTS), осуществляющая связь по радиоканалам с подвижными абонентами мобильных радиостанций (MS), находящимися в ее рабочей зоне.

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

Для сот используют три геометрические фигуры: треугольник, квадрат и правильный шестиугольник.

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

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

Однако с практической точки зрения при планировании зоны обслуживания следует руководствоваться следующими рекомендациями:

• 1.    Отличное качество связи будет в зоне, границы которой определяются исходя из ожидаемого превышения сигналом уровня чувствительности приемника в 95% мест и 95% времени (вероятность устойчивой двусторонней связи 0,9);

• 2.    Хорошее качество связи будет в зоне, границы которой определяются исходя из ожидаемого превышения сигналом уровня чувствительности приемника в 90% мест и 90% времени (вероятность устойчивой двусторонней связи 0,8).

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

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

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

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

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

В качестве критериев сравнения и выбора лучшего из проектов (или вариантов проекта) рекомендуются [2-3]:

• -    чистый дисконтированный доход (ЧДД);

• -    индекс доходности дисконтированный (ИДД);

• -    внутренняя норма доходности (ВНД);

• -    срок окупаемости с учетом дисконтирования (Т_ОВД).

Требуется выбрать такой (i-ый) вариант проекта, при котором:

т

ЧДД- = 2 Otat(E) ^ max, 1 t=0 1 1

где T – горизонт расчета; Ф^ – денежный поток; a_t – коэффициент дисконтирования; Е – норма дисконта. При этом ЧДД_i > 0; ИДД_i > 1; ЧДД_i и ИДД_i > 1;       ii где

Гокд – множество сроков окупаемости проекта).

Условия сопоставимости вариантов проекта:

• -    рекомендации 1 и 2 выполняются;

• -    заданная территория имеет коэффициент неровности местности порядка 50 м;

• -    сопряжение с частотным планом сети обеспечено.

Структура сети, обеспечивающая максимальное значение ЧДД и удовлетворяющая ограничениям и условиям 1-3, называется оптимальной структурой сети, а сеть, имеющая такую структуру, называется сетью оптимальной структуры.

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

В связи с этим требуется разработать метод синтеза оптимальной структуры сети, являю- щийся элементом САПР сети. При этом возможны два случая: расширение существующей сети БС и построение сети вновь.

Исходные данные для решения задачи синтеза

При решении задачи синтеза оптимальной структуры сети используются следующие исходные данные.

• 1.    Планируемый период, Т.

• 2.    Характеристика пунктов, расположенных на заданной территории.

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

• 4.    Характеристика существующей сети БС на заданной территории на начало планируемого периода.

• 5.    Частотный план.

• 6.    Процент времени, в течение которого напряженность поля, создаваемая БС; и процент точек приема, в которых напряженность поля, создаваемая БС, обеспечивает прием сигналов.

• 7.    Основные параметры сети.

• 8.    Зависимость напряженности поля от расстояния в пригородной и сельских зонах.

Математическая модель задачи синтеза оптимальной структуры сети

Задана территория, на которой расположено некоторое число пунктов возможной установки БС. Требуется построить сеть, обеспечивающую всю территорию связью заданного качества. Если на заданной территории уже имеется некоторая сеть БС, обеспечивающая часть пунктов связью, то задача сводится к ее модернизации.

Заданы исходные данные, необходимые для синтеза оптимальной структуры сети.

Необходимо найти оптимальную структуру сети.

Пусть имеется непустое множество С={с_k} пунктов c_k, п од лежащих обслуживанию сотовой связью (k = l,n). Пусть, кроме того, С₀ – непустое под мн ожество из m пунктов с_0i множества Co (i = 1, m; m < n), в которых возможна установка БС. Очевидно, чтоC„cC.

Будем считать, что установка БС в пункте c0i создает зону обслуживания – непустое континуальное точечное множество Di. В Di входят все точки местности, в которых обеспечивается тре- буемое качество связи от БС, установленной в пункте c0i. Очевидно, что если каждый пункт ck идентифицировать с упорядоченной двойкой чисел (δk,φk), δk и φk – географические координаты (широта и долгота) пункта ck, то с01 g D, , но, кроме того, в Di могут входить и другие пункты из C. Это пункты, попавшие в зону обслуживания станции, установленной в пункте c0i.

Пусть li – натуральное число, удовлетворяющее условиям: 1 < 1 < m; 1;^ lj, если i ^ j ■ Тогда систему {D }Sj множеств D^l^) будем называть согласованной, если БС, установленные в пунктах C0i' ’ не создают взаимных помех и согласуются с частотным планом существующей сети (ограничения и условия, указанные в 1) и 2), выполняются).

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

dP 1

(i-i,M). Объединение мно- жеств согласованной системы

Dp i

, то есть

S. J множество Tj =iP1Dl (Sj – число множеств, входящих в систему множеств {d ^ }), будем называть сопряженным с некоторой полной сетью, которую обозначим (Wj,Тj) (Wj – набор БС, установленных в пунктах, принадлежащих Тj), если из C G C следует, что C G T , то есть С c Tj . Очевидно, что не каждое из М множеств Тj окажется сопряженным с некоторой полной сетью, а лишь те M°

Необходимо из всех М0 возможных вариантов структуры полной сети найти вариант оптимальной структуры, при котором:

ЧДД

s s

opt         opt T

2 ЧДД. = 2  2 Ф а (E)^ max, i=l 1 i=lt=0

где ЧДД[(W,T)] – ЧДД при варианте структуры полной сети (W, T); ЧДД [(W_opt,T_ot)] – Ч при варианте оптимальной структуры i-hS_opt (S_opt – число БС в варианте оптимальной структуры); при выполнении условий 1 и 2.

Таким образом, при заданном множестве С пунктов задача планирования сети сводится к задаче синтеза оптимальной структуры сети.

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

Теоретические исследования показали, что существующие методы решения задачи оптимизации обслуживающей системы не учитывают особенности структуры сети и, в первую очередь, вопросы электромагнитной совместимости БС. Поэтому использование этих методов для решения поставленной задачи приводит к практически неприемлемым результатам. Для решения задачи синтеза оптимальной структуры сети необходимо разработать новый метод. Как показал анализ методов оптимизации, метод синтеза оптимальной структуры сети должен быть основан на случайном поиске.

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

В рамках экспериментальной проверки данного метода была смоделирована территория населенного пункта среднего города до 100 тыс. человек населения. Площадь территории 178,37 км2. Заданы координаты возможных точек установки БС и возможное количество точек установки. На заданной территории построено 2500 различных независимых вариантов структуры сотовых сетей. Получены результаты построения 2500 независимых вариантов структуры сотовой сети и их статистический ряд.

Минимальное значение затрат

Xmin = 27316,37 тыс. руб. Максимальное значение затрат Xmax =39762,50 тыс. руб. Математическое ожидание затрат m = 33539,43 тыс.

руб. Среднее квадратическое отклонение затрат <7 = 1880,25 тыс. руб. Коэффициент k1 = 3,7512. Коэффициент k2 = 3,7485. Аппроксимирующая плотность распределения затрат имеет вид:

1      1 РЗ

----e ’

Pl P2

m-kjO < x < m + k2;

0;

n1 .,39443,64-33539,43, ^,27316,37-33539,43, где Pl = Ф(-----------------—) - Ф(------------------—),

1880,25                 1880,25

(x-33539,43)2

г 2 = 2 л 1 ooU,25,   =------------г—.

2 -1880.252

В результате проверки гипотезы о распределении затрат по вышеописанному закону по критерию Колмогорова определено максимальное значение модуля разности D между статистической функцией распределения Fx (x) и соответствующей теоретической функцией распределения :

D = max|F;(x)-Fx(x)| = 0,01028 .

Значение величины k = DV2500 =0,5143. Вероятность того, что (если величина затрат распределена по закону Fx(x))за счет чисто случайных причин максимальное расхождение между Fx(x) и Fx(x) будет не меньше, чем фактически наблюденное, равна 0,95. Эта вероятность является сравнительно большой, ее можно считать совместной с опытными данными. Поэтому гипотезу о распределении затрат по усеченному нормальному закону можно считать правдоподобной.

Задавшись надежностью P = 0,998; из 2500 построенных вариантов структур сотовых сетей получили, что наибольшее возможное отклонение затрат от оценочного минимума не превзойдет 80=5,lтыс. руб.

Результаты проведенной экспериментальной проверки подтвердили предположение о том, что планирование вариантов структуры сотовой сети с использованием предложенного метода синтеза способствует построению оптимального варианта сотовой сети.

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