Материал: Основы автоматизации проектирования беспроводных систем и сетей связи. Семёнов Р.В

Таблица 4.22

Пропускная способность

ИС=0,076 ОС=0,07

Итоговые результаты: ДМВ1 - 0,2965; ДМВ2 - 0,2693;

ДКМВ - 0,2388; МВ -0,1954.

На рис. 4.5 представлены результаты многокритериального выбора частотного диапазона.

Рис. 4.5. Результаты многокритериального выбора частотного диапазона

4.3. Размещение базовых станций

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

156

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

Приведем математическую постановку задачи. Предполагается, что каждая базовая станция может быть установлена на одно из M вакантных мест с фиксированными координатами. Таким образом, может быть от 1 до M –1 базовых станций. Существует K клиентов, каждого из которых необходимо подключить к одной базовой станции. Под клиентом понимается группа индивидуальных абонентов с одинаковыми условиями распространения сигналов, количество запросов от которых определено по результатам предварительного маркетингового исследования. Задача оптимального проектирования состоит в выборе наиболее дешевого варианта назначения базовых станций на вакантные места и распределения клиентов по базовым станциям.

Введем следующие обозначения:

X = ( X1 , X 2 ,K, X M ) – вектор размещения базовых станций, в котором значение координаты X m =1(0) указывает, что m-ое вакантное место занято (незанято) базовой станцией, m =1, M ; Y = Ykm – матрица распределения клиентов по базо-

вым станциям ( m =1, M , k =1, K ), в которой значение элемента Ykm указывает, что к-й клиент подключен (не подключен) к ба-

зовой станции, размещенной на m-м вакантном месте. Математически, решение задачи сводится к нахожде-

нию X и Y , обеспечивающих:

∑ ∑Ykm ×W (rkm ) + c × ∑X m + ∑ ∑Ykm × P(rkm ) ® min , (4.1)

k =1,K m=1,M m=1,M k =1,K m=1,M

где rkm – расстояния между к-м клиентом и m-м вакантным местом размещения базовой станции;

157

клиента к базовой станции с учетом пороговых значений удаленности R1 и R2 ; с – стоимость базовой станции; P(rkm ) –

штраф за снижение качества связи из-за потерь при распространении сигнала в радиоканале, расчет которого предлагается осуществить по табл. 4.23.

Для работы с табл. 4.23 требуется рассчитать потери сигнала по следующей формуле:

PL = 20 lg(4π r0 / λ) +10γ lg(r / r0 ) + s + 6 lg( f / 2000) − 20 lg(0.5h) ,

где r0 – базовое расстояние, равное 100 м; λ – длина волны; γ –

экспонента потерь при распространении сигнала; r – расстояние между базовой и абонентской станциями; s = 8.2…10.6 дБ

– случайная составляющая потерь при распространении сигнала с логнормальным распределением; f – рабочая частота.

Таблица 4.23

Штраф за ослабление сигнала

m=1

2.Суммарный трафик всех клиентов, обслуживаемых с

m-го места, не должен превышать производительность станции:

k =1

158

где Bm – производительность станции, установленной на m-ом месте, Кбит/с; bk – затребованная k-м клиентом ширина кана-

ла, Кбит/с.

В представленной формулировке данная задача относится к классу задач размещения с одним источником обслуживания при наличии ограничений на его емкость [26].

Рассмотрим решение поставленной задачи с помощью муравьиного алгоритма. Для применения муравьиной метаэвристики необходимо свести задачу к поиску кратчайшего пути на некотором графе и определить процедуры обновления феромонов и правила выбора маршрута [27]. Для рассматриваемой задачи поиск решений предлагается осуществить на конструирующем графе GC (V1,V2 , E) . В этом графе множество

вершин V1 соответствует вакантным местам размещения базовых станций, множество вершин V2 представляет клиентов, а

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

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

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

Выбирая маршрут, муравьи будут ориентироваться не только на динамически обновляемые феромонные уровни, но и на некоторый статический показатель локальной привлекательности ребер графа. Таким показателем назначим так называемую видимость клиента ηkm =1/ rkm

Ограничения задачи оптимизации выполним следующим образом. Согласно ограничению (4.2) каждому муравью

159

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

Для выполнения ограничения (4.3) с каждым вакантным местом ассоциируется переменная Bемк . В начале каждой ите-

рации алгоритма значение этой переменной приравняем к производительности станции. После возвращения муравья от клиента значение Bемк уменьшается на величину полосы пропус-

кания, затребованную клиентом.

Процесс построения решения начинается с фазы инициализации, в течение которой устанавливаются значения параметров алгоритма. Затем всем вакантным местам кандидатам, клиентами ребрам присваивается одинаковое значение начального уровня феромона τ0 . В основном цикле алгоритма

муравьи, стартуя из различных вакантных мест, направляются к клиентам. Для каждого муравья, размещенного в m-ом вакантном месте, рассчитывается привлекательность каждого допустимого клиента. Привлекательность клиента рассчитывается по правилу (4.4), которое учитывает уровни феромонов соответствующих клиента и ребра графа, а также его видимость. Муравей, размещенный в m-ом вакантном месте, двигается к k-му клиенту с максимальной привлекательностью. Такой выбор осуществляется, если q £ q0 :

160