Использование нейронных сетей при планировании сотовых сетей подвижной радиосвязи

значения і, а остальные значения =0). Однако до достижения сходимости величины Vjj принимают значения в континууме [0, 1 ] и выражение
для энергии перегрузки, определяемое с помощью выражения (3.6), применимо в полной мере только для аналоговой реализации системы.

Рассматриваемая задача оптимизации с целым рядом ограничений может быть сведена к задаче без ограничений за счет включения ограничений в целевую функцию посредством использования множителей Лагранжа [ 111J. Функция энергии перегрузки при этом приобретает следующий вид:
3 Л'?о-'?Д/)
= + (3-8)
C=l 1=1 j=I
Ограничения для задачи являются соответствующими членами уравнения энергии перегрузки Е_с (равны нулю, если ограничение выполняется) и формулируются так:
1) На SD пару активизируется (выбирается) не более одного маршрута:
i N_SDN_p(i)N_n(i)
5Хг,=о. z i=i j=1 i=i
i*j
2) В сети выбираются строго N_SD маршрутов:
( n_sdn (і)
. 1
Е^2
= 0.
¦=I j=1
3) На SD пару выбирается строго один маршрут:
i N_SJ N„U)
= 0.
e,=-I Ik,-’
i=I / = 1
Хотя последнее ограничение представляется избыточным (выполнение первых двух гарантирует удовлетворение последнего), его включение в уравнение энергии полезно для достижения более быстрой сходимости. Подстановка выражений для Е_ь и Е_с в (3.8) дает:
г л', Л’„, а;,ту..;о л .v_sr,y,(').v,,() 1 Д?(„ЛД')
(3.9)
/=1 k=\Jc*i 7=1 /=1 ^ /=І /=1 і=і ^ /=1 /=1
лу/лд/) ? ; лу.Лу.о
42 5Х-1 +ДЕ1 2Х-і -'22Х-
^ і=1 /=] ^ /=| /=1
V У V /
V .V ЛД7)
1=1 ^ /=1 ) /=1 ^ /=1 J /=1 j=]
Одним из самых важных вопросов при разработке модели НС Хоп-филда и дальнейшем моделировании работы системы является вопрос выбора коэффициентов Л_с. Фактически, любые значения Я приведут к получению справедливых выражений для Е_юш,. Однако при эволюции системы может быть гарантирован только локальный минимум, то есть конечное состояние зависит от начального состояния, при котором начинается эволюция системы.

Таким образом, различные значения коэффициентов приводят к получению различных результатов. В большинстве исследований, посвященных использованию НС Хопфилда величины коэффициентов полагаются постоянными, лучшие значения которых обычно определяются в ходе испытаний при программном моделировании. Однако существует ряд подходов, позволяющих во всей полноте использовать метод множителей Лагранжа [111, 112].

В этом случае величины Х_с изменяются по мере изменения состояния системы [111].
Оценить качество решения задачи обычно не представляется возможным, так как число возможных решений для больших сетей очень велико. Например, для 100-узловой сети существует приблизительно 5 -1035 различных решений. Поскольку исчерпывающий поиск для такой сети исключается, то при моделировании выполнялся случайный поиск 2-ІО6 выборок решений для получения опорного уровня качества работы для оценки работы НС [65].

Наилучшее решение, полученное с помощью случайного поиска, имело энергию перегрузки E_b = 567 . Использование традиционных эвристических методов решения задачи маршрутизации позволило получить Е_ъ- 313. Наилучшее решение найденное с помощью НС Хопфилда дало Е_ь- 291.

Наибольшее значение энергии перегрузки в этом случае было Е_ь = 303. Моделирование выполнялось от 50
различных начальных состояний. Таким образом, результаты моделирования показывают эффективность рассмотренной модели для минимизации перегрузки в больших сетях.

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

Использование нейронных сетей при планировании сотовых сетей подвижной радиосвязи

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

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

Одна из них состоит в выводе эмпирических формул на основе измерений, а другая основывается на аналитических моделях, использующих теорию дифракции. Практика показывает, что и та и другая модели имеют ряд недостатков [24].
Использование эмпирического метода прогнозирования напряженности поля, основанного на использовании нейронных сетей, позволяет устранить некоторые недостатки [102]. В этом случае НС решает задачу аппроксимации некоторой функции по имеющимся значениям ряда точек. Для НС эти точки являются обучающим множеством.

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

Для повышения точности аппроксимации среднего значения напряженности поля, вклад последнего может вычисляться аналитически и исключаться из процесса обучения.
Результаты использования НС для прогнозирования напряженности поля можно рассмотреть на следующих примерах.
В первом случае используется хорошо известная формула Хата [69], отражающая эмпирическую аппроксимацию потерь при распространении L в городских районах:
Ь_р{дБ) = 69,55 + 26,16log/(МГц) - 13,82logк_БС(м) -
- {1,1 log/(МГц) - 0,7_м (.) + {l,56log/(Mn₍) - 0,8}+ (3.10)
+ {44,9 - 6,55 log /!_6r(,w)}logt/(/cvi).
Диапазон частот f = 150... 1500 МГц, высота расположения базовых станций (БС) к_БС =30...200м., высоты расположения подвижных станций h_M =1...10м и дальность d =1...20км.

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

/э,тах /,тпіп
где L _{пе[ і} - потери на трассе, получаемые с выхода НС.




Рис. 3.6. Вариант применение НС для прогнозирования напряженности поля

После 1200 циклов обучения на примере обучающего множества из 2160 точек среднее отклонение составило приблизительно 0,18%. Для точек тестирования, выбранных между точками обучения в рассматриваемом параметрическом пространстве, отклонение увеличивается до 0,24%, при этом М_ітх 1,23% . В этом эксперименте динамический диапазон
составляет L_{p max} -L_{p mm} =\00дБ.
Другая типичная задача связана с использованием геометрической теорией дифракции Келлера [80] для случая дифракции на клине (см. рис. 3.7а).

При этом также может использоваться многослойная НС с одним скрытым слоем. Число нейронов во входном и скрытом слое выбирается исходя из задачи и предъявляемых к решению требований.
В модели для аппроксимации нормализованной напряженности поля Е/Е₀ на профиле трассы изображенной на рис. 3.7а использовалась НС, имеющая 11 нейронов во входном слое и 8 нейронов в скрытом слое.

Рис. 3.7. Аппроксимация напряженности поля с помощью нейронной сети
Выборка топографических данных производилась в 10 точках, которые обеспечивают входные данные для 10 элементов. Величина выборки может изменяться. Данные о ней поступают на 11 вход. В результате последней операции выборка приспосабливается к длине профиля трассы.

Моделирование проводилось для различных комбинаций высот, углов участков препятствия моделируемого "клином". Среднее отклонение вычислялось по формуле (3.11) и после 20 000 циклов обучения составило 0,3%.

В обоих случаях при обучении использовался алгоритм обратного распространения. На практике для обучения НС могут использоваться как результаты аналитических расчетов, так и результаты текущих и ранее
проведенных измерений. После завершения процесса обучения для тестовых примеров максимальное отклонение М_тах не превышало 6% (см. рис.

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

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

Использование нейронных сетей для распределения каналов в сотовых радиосетях

Решение задачи назначения частот, так же как и решение задачи прогнозирования напряженности поля, является одним из этапов проектирования ССПР. При решении этой задачи назначение частот должно производиться в рамках ограничений заданных матрицей электромагнитной совместимости (ЭМС). При этом рассматриваются такие ограничения, как:
ограничения из-за помех по соседнему каналу;
ограничения из-за помех, обусловленных совместным расположением (несущие используемые в одной ячейке, должны иметь необходимый разнос по частоте);
ограничения по числу частот для каждой ячейки.
В 1982 г. Гамет и Рейв определили общий вид задачи распределения каналов в произвольной неоднородной сотовой радиосети [61]. Согласно их определению ограничения ЭМС в п -сотовой сети описываются с помощью матрицы размером п хп , которую называют матрицей совместимости С . Каждый недиагональный элемент су матрицы С представляет
собой расстояние минимального разнесения в частотной области между частотой, присваиваемой і -й ячейке и частотой, присваиваемой j -й ячейке. Ограничения из-за помех по соседнему каналу могут быть записаны как су = 1 . Запись су = 2 указывает на то, что частоты, смежные в частотной области не могут присваиваться смежным ячейкам, а значение су = 0 - на то, что ячейкам і и j разрешается использовать одну и ту же
частоту. Каждый диагональный элемент су в С обозначает расстояние минимального разнесения между двумя любыми частотами, присваивас-мыми і -й ячейке. При этом для удовлетворения выше сформулированных ограничений с_и всегда должно удовлетворять ограничению с_и 1 .
Требования, предъявляемые к частотному каналу каждой ячейки п -сотовой сети, описываются с помощью п -элементного вектора, который называют вектором спроса D . Элемент d. вектора D обозначает число частот, которые должны присваиваться і -й ячейке. Обозначая через /_ік к -ю частоту, присваиваемую і -й ячейке, ограничения по ЭМС можно записать следующим образом:
I (3.12)
для і = 1j - 1к = 1,...,і₍ и / = 1 , исключая і = j,k = /.
В качестве примера, приведем решение задачи распределения каналов (рис.3.8в) для четырехсотовой сети [101]. На рис.

3.8а приведена матрица совместимости С и вектор спроса D. На рис. 3.86 показана топология сети, соответствующая матрице совместимости С .

'5	4	0	0		т
4	5	0	1	, D =	]
0	0	5	2		1
0	1	2	5		3

ячейка 3 ^ ячейка 4

Рис. 3.8. Распределение частотных каналов для четырехсотовой сети
Задача распределения каналов относится к математическим задачам, связанным с раскраской графов [67]. Из теории известно, что время необходимое для нахождения решения, экспоненциально увеличивается с увеличением размерности задачи (то есть, ростом числа базовых станций).
В соответствии с теорией окрашивания графов, путем поиска так называемого максимально полного подграфа, можно определить нижнюю границу для общего использованного частотного ресурса. Известные алгоритмы различной степени сложности направлены на удовлетворение всех требований с учетом заданных ограничений при минимизации использованного частотного ресурса.

Если в результате решения общее число рабочих частот близко к определенной нижней границе, то оно принимается, в противном случае (если спрос превышает полный частотный ресурс, выделенный для сети подвижной связи) размеры ячеек следует уменьшить (произвести их "расщепление"), чтобы сеть хотя бы локально работала с более высоким уровнем повторного использования частот.
Рассмотрим алгоритм решения задачи распределение частотных каналов, основанный на использовании искусственной НС.
Модель НС для решения комбинаторной задачи оптимизации впервые была введена Хопфилдом и Танком [77]. Решение задачи заключается в минимизации сформированной функции энергии (см. п. 1.3.2).

Несмотря на то что в ряде работ [95, 109] критиковались устойчивость и качество решения, для таких моделей известно о большом количестве успешных применений НС Хопфилда [19, 57, 58, 93].
В 1991 г. Кунц впервые предложил использовать модель НС Хопфилда для решения задачи распределения каналов в сотовой радиосети [84]. Кунц не рассматривал ограничения из-за помех по соседнему каналу и установил предел для ограничения по расстоянию минимального разнесения между двумя любыми частотами, присваиваемыми і -й ячейке с_и = 2 .
Однако, модель НС Кунца имеет несколько недостатков. Прежде всего, он использует "медленную" сигмоидальную активационную функцию.

Кроме этого, в используемой функции энергии не учитываются особенности решаемой задачи. Эти недостатки модели Кунца препятствуют ее использованию для решения задачи распределения каналов в сотовой радиосети на практике.
Предлагаемая модель нейронной сети использует гистерезисную активационную функцию и модифицированную функцию энергии [59]. Используемая функция энергии Е определяется путем рассмотрения всех ограничений, описанных выше. При этом она характеризует текущее состояние НС.

Это обеспечивает более быструю сходимость решения, чем модель Кунца.
Частные производные вычислительной функции энергии E(V_l ,
которую также называют уравнением энергии, задают изменения входа / -го нейрона
dU, _ ЭЕ(У_п...,У_п) dt д?_і
(3.13)
Здесь С/, и ?_і соответственно вход и выход і -го нейрона, п - число нейронов используемых, для решения конкретной задачи.
На рис. 3.9 в виде матрицы состояний представлены 4x11 выходов нейронов, используемых для решения задачи распределения каналов в четырехсотовой сети, изображенной на рис.

3.86, и их сходимость к решению. Минимально необходимое число нейронов для решения этой задачи равно 4x11. Это следует из матрицы совместимости С и вектора спроса D, представленных на рис.3.8а (с₄₄ = 5, d₄ = 3, следовательно,
ячейка 4 требует самое малое 11 (1+5x2) частот).
Число требуемых частот, а следовательно и необходимое для решения задачи число нейронов должно определяться перед моделированием. Обычно для задач большой размерности т приблизительно может быть определено путем перемножения с_н и максимального значения в векторе спроса.

Если с помощью определенного таким образом значения т задача не решается, то его необходимо увеличивать до тех пор, пока система не найдет решения. Однако можно воспользоваться и найденными в предыдущих работах, в частности [84, 101] значениями.

Рис. 3.9.

Представление выходов 4x11 нейронов, используемых для решения задачи распределения каналов в четырехсотовой сети, изображенной на рис. 3.86, и их сходимость к решению
Выход ij -го обрабатывающего нейрона 1+ указывает на то, присваивается или не присваивается / -частота і -й ячейке. Ненулевой выход ( V_tj = 1 ) указывает на то, что j -частота присваивается і -й ячейке. Нулевой выход (?_г = 0) указывает на то, что j -частота не присваивается і -й ячейке.

На решении задачи, приведенной на рис. 3.9, черные квадраты обозначают ненулевой выход, а белые квадраты - нулевой выход.
Уравнение движения ij -го обрабатывающего нейрона V_tj для п -ячеечной, Щ -частотной задачи задается следующим образом:
f \
j+(c,~ 1) n j+K-l)
X г + X X ^
q=j-(c„-1) P=I ‘7=/-(C,_/J-0
q* j l qm
[qm c_lp 0
dU,
dt1,1=ЧХг,-^,
(3.14)
7=I
Первый член выражения (3.14) (A-член) вынуждает d_t нейронов обрабатывающих состояния т частот выделенных для і -й ячейки иметь ненулевой выход в случае, если соответствующие частоты присваиваются / -й ячейке. Второй член выражения (3.14) (В-член) мешает ij -у нейрону иметь ненулевой выход в случае, если присвоение j -й частоты і -й ячейке нарушает следующие ограничения:
если q -я частота в пределах расстояния с_и от j -й частоты (I j - q\ с,,) присваивается і -й ячейке, то j -я частота не должна присваиваться этой ячейке, то есть
І+(с„-1)X г,
1)
ч*і
\qm
имеет ненулевой выход в случае, если присвоение j -й частоты і -й
ячейке нарушает ограничение по числу частот для каждой ячейки;
при ограничении из-за помех по соседнему каналу и ограничении из-за помех, обусловленных совместным расположением, если q -я частота в
пределах расстояния с_ір от j -й частоты (| / - q\ с_ір ) присваивается р -й
ячейке, для с_ір 0 и рФі j -я частота не должна присваиваться і -й ячейке. Таким образом
п ./- (¦'* - !) X X ?„
р^і I qm c _lf) 0
имеет ненулевой выход, если присвоение j -й частоты і -й ячейке нарушает ограничении из-за помех по соседнему каналу и ограничении из-за помех, обусловленных совместным расположением.
А и В являются постоянными коэффициентами (А = В = 1).
Исходя из вышесказанного, функция энергии для задачи распределения каналов в сотовой радиосети задается следующим образом:
f \
j+(c„-1) „ У+(с,_р-І) X г,+ Х X ^
/=' /=/ l',, -о
P*i I qm
1 qm c 0
А -А
E = jl Ж-*, + ХХ
L '=,\ /=1
(3.15)
і=1 М
Известно, что для используемой модели НС гарантируется нахождение только локального минимума. Для того чтобы обеспечить более быструю сходимость алгоритма и увеличить частоту нахождения глобального минимума введены следующие дополнения функции энергии.
1. Для того чтобы ограничить A-член между двумя значениями, он модифицируется следующим образом:
( т л
ХГ,
(3.16)
-Af
и
где Дх) = А_тт , если х А_шх, /(х) - А_тіп, если х Л_тіп и Дх) = х в других случаях. Таким образом А_ітх и 4_тш являются соответственно верхней и нижней границей А-члена.
2. Используемый в уравнении энергии В-член, может принимать две формы: если (/тоёГ) гд
( \
у+(с„-1) п М^_р-1) X г, + Х X г„
4=j-(c,r 0 А=1 ?=/-( ^?Ч)
4*j P*i 1 qm
\i/m с 0
(3.17)
-В
в других случаях
j+(c„-1) п /+(с,„-1) X г, + Х X
1) p=i q=j-i?_ip-1)
/*/ \qm
1 qm t1 0
(3.18)
-В
где t - число итерационных шагов, а Т и сд - постоянные параметры. 3. К уравнению движения добавляется следующее выражение:
f щ \
+ Ch
о-у,у
(3.19)
9=і
где h{x) = 1 при х 0 и /г(х) = 0 при х 0.
Значение С выбирается на каждом итерационном шаге таким образом, чтобы устранить ситуацию, при которой два или более обрабатывающих нейрона имеют одни и те же состояния. С-член помогает ij -у обрабатывающему нейрону иметь ненулевой выход, если менее чем d_t нейронов для і -й ячейки имеют ненулевой выход и V_tj = 0 .
4. Вход обрабатывающего нейрона ограничивается двумя величинами:
uij = ^max если и у и_ітх
uij = , если и у и_тт, (3.20)
где (7_тах и U_mm соответственно постоянные верхняя и нижняя границы входного значения U_у.
Алгоритм распределения каналов в сотовой радиосети, основанный на использовании уравнения движения (3.14), функции энергии (3.15) и ее дополнений может быть описан следующим образом.
1 этап. Эмпирическим путем устанавливаются используемые значения коэффициентов и параметров А, В, С, t, Т, ш, U_max, U_mm, T_max, UTR, LTR .
2 этап. Рандомизируем начальные значения входа U_tj(t) для і = 1
и j = 1 ,...,ш между 0 и U_mm . Назначаем начальные значения выхода ?у(/) для и j - , равными нулю.
3 этап. Используя уравнение движения (3.14), вычисляем изменение входа ДUy(t):
если (г mod Г) ш
P=1 Ч=ІЛс,_р-1) P*i 1 qm
c,„0
(3.21)
ч4~і Cj/-1) 4*j
1 qm
+ Ch
5X(o-4
V 9=1
в других случаях
0-nW).
_/+(c„-l) n У+(с_?-1) X r,w+ x X Г,м
?=Hf,r4 p=i 4=H‘'V1)
q*j p*i \qm
\qm c 0
2X )-
UM) = -Af
4=1
(3.22)
+ C/z
4 этап. Обновляем значение входа
(/..(/ + 1) = (7, (0 +At/ДО. (3.23)
5 этап. Используя выражение (2.20) модифицируем значение входа:
Uу 0 + 1) = ^шах. если (Г + 1) U_max
?_ц(t + 1) = U_mm, если и_и(( + 1) U_тів. (3.24)
6 этап. Используя гистерезисную активационную функцию, обновляем выход обрабатывающего нейрона V_tj (t + 1):
Vy (t + 1) = 1, если U_tJ (/ + 1) UTR ,
V_i;/(t + 1) = 0 , если U_lj(t + \)LTR , (3.25)
в других случаях не изменяется.
Здесь UTR, LTR - соответственно верхняя и нижняя точки обхода. 7 этап.

Проверка условия окончаня работы алгоритма.
/+(?¦„-I) Я j+(c_ip-\)
X Ц + Х X
4=У-(С„-П р=1 4=./-(с_?-1)
q*j P*i \qm
1 qm c’ 0
= о И (V' (0 = 1 И
0),
ХГ.-4,
4 = 1
Если
для i = \,...,n и 3/ G {l,...,w} или t = T_max то алгоритм работу заканчивает.
В других случаях увеличиваем значение t на единицу и возвращаемся на этап 2.
Для того чтобы сократить время сходимости при решении ряда задач, можно зафиксировать назначение частот для одной из ячеек или нескольких ячеек с самым большим числом требуемых частот. Например, из рис. 3.8а видно, что четвертая ячейка имеет наибольший элемент в векторе спроса, поэтому логичным является фиксирование присвоения частот этой ячейке, что и делалось при моделировании.

Кроме того, фиксированное назначение частот может быть априорно заданно, например на случай расширения сети, для того чтобы не было совпадений с частотами соседних сетей.
Результаты моделирования показали, что сходимость рассматриваемого алгоритма значительно выше, например известного алгоритма Кунца [84]. Так для 25-и ячеечной сети и 73-х распределяемых частотах для решения потребовалось 200 итерационных шагов, против 2450 при использовании алгоритма Кунца.
Модификация этого алгоритма может быть направлена на учет большого количества всевозможных ограничений, которые могут быть заданы матрицей ЭМС.

Заключение

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

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

Содержание раздела

---