635_Nosov_V.I._Optimizatsija_parametrov_setej__

учетом всех помех в сети и в беспомеховой обстановке. Расчет зон вещания проводился с помощью разработанной под руководством автора автоматизированной системы анализа ТВ сети путем расчета радиусов зоны вещания по 12 азимутальным направлениям.

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

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

3.1.2 Анализ задачи

Независимо от способа решения поставленной задачи в процессе присвоения частотных каналов планируемым передатчикам сети многократно возникает один и тот же вопрос: можно или нельзя присвоить некоторому передатчику данный частотный канал? Отрицательный ответ следует в трех случаях: если данный канал несовместим с действующим или уже является присвоенным каналом другого передатчика, расположенного в одном пункте с рассматриваемым; если существует хотя бы один действующий или планируемый, но не расположенный в одном пункте с рассматриваемым, передатчик с уже присвоенным каналом, создающий помеху по данному каналу (соседнему или совмещенному), величина которой превышает допустимый уровень; если присвоение данного канала рассматриваемому передатчику ведет к созданию недопустимой помехи хотя бы одному действующему или планируемому с уже назначенным каналом, удаленному передатчику, т.е. ребра рассматриваемого подграфа принадлежат реберному множеству запрещений графа G

{A(vi), A(vj)} H(eij), eij = ( vi , vj ) E.

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

112

коэффициента взаимного влияния (КВВ), который определяет, насколько изменяются радиусы зон вещания передающих станций относительно максимальных зон под воздействием взаимных помех. Этим дается количественная оценка степени взаимного влияния передатчиков (рис.1.12).

Коэффициент взаимного влияния определяется по формуле

КВВ = max { 1 - ((min (Rpi1; Rpi2)) / Rмаксi );

где Rpi1, Rpj1 — реальные радиусы зон вещания i - го и j - го передатчиков по направлению друг к другу с учетом влияния помехи, км;

Rpi2, Rpj2 —реальные радиусы зон вещания i - го и j - го передатчиков в противоположных направлениях с учетом влияния помехи, км;

Rмаксi , Rмаксj — радиусы зон вещания i-го и j-го передатчиков без учета влияния помех, км, определяемые из условия

Ес ( Rмакс, HА ) = Е(50,50, Rмакс, HА) + Р = Емин.

Радиус Rpi определяется из условия

Е(50,50,Rpi,HА) + Р i - E(50,10,d,HА) - Р j = AЗ.

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

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

Значения и задаются эмпирически. Если КВВ > , то уровень вза-

113

имных помех считается недопустимо высоким; если же КВВ < , то снижается эффективность использования спектра.

3.1.3 Решение задачи

Пусть частотный канал К присвоен некоторому передатчику. Тогда вокруг него выделяется множество передатчиков, которым критерий (3.14) запрещает назначить канал К ввиду сильных взаимных помех с передатчиком А, т.е. рассматриваемое ребро принадлежит множеству запрещений графа G

КВВ : {A(vк), A(vА)} H(eкА), eкА = ( vк , vА ) E.

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

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

Передатчики, образующие с передатчиком А оптимальные пары, расположены на территории, по форме напоминающей кольцо (в однородной сети — строгое кольцо) с центром в точке А, непосредственно охватывающее круг, формируемый по критерию (3.14) (рис.1.12). Множество этих передатчиков будем называть координационным кольцом передатчика А

КВВ : {A(vj), A(vА)} H(ejА), ejА = ( vj , vА ) ,

которое строится следующим образом.

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

114

в нем передатчики удовлетворяют одновременно обоим требованиям. Такие присвоения действительно равноценны по отношению к присвоению канала К передатчику А, поэтому проблема выбора отпадает.

КВВ =

КВВ = 0

КВВ =

Рис.3.1 Построение координационного кольца

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

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

Дальнейший ход присвоения канала К очевиден.

115

С

Рис.3.3 Пересечение координационных колец

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

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

3.1.4 Результаты машинных экспериментов распределения частотных присвоений в ТВ сети методом координационных колец

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

116

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

3.2 Разработка эвристических алгоритмов назначения частотных каналов в сетях радиовещания

3.2.1 Математическая модель задачи

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

Исходными данными для составления частотного плана являются ограничения на помехи по основному и неосновным каналам приема, представленные в виде минимально допустимых частотно - пространственных разносов РЭС, нуждающихся в назначении частот. Прямой перебор заявок и частот как метод нахождения точного решения неприменим, т.к. требует реализации машинного времени, экспоненциально зависящего от размерности массивов. Единственным средством, позволяющим сравнительно быстро решать рассматриваемую задачу ( при отсутствии гарантии получения строго оптимального плана ) является эвристическая методика, в частности , базирующаяся на отождествлении РЭС с вершиной графа взаимных влияний, а минимальных частотных разносов – с весами ребер этого графа. Отсутствие ребра в графе свидетельствует об отсутствии взаимных помех между соответствующими РЭС. Задача присвоения частот сводится к задаче " раскраски " вершин графа, когда связанным некоторым заданным образом вершинам ( передатчикам ) требуется приписать некоторый " цвет " ( выделить канал ) . Этот граф строится следующим образом .

Пусть имеется конечное множество М радиовещательных передатчиков. Поставим ему в соответствие граф G = (V, Е ) со множеством вершин V и множеством ребер Е так, что отображение М на V является биективным, а каждое ребро

118

соединит пару вершин vi , vj V, соответствующих радиовещательным передатчикам mi , mj M, которые создают недопустимые взаимные помехи в зонах обслуживания друг друга. Классическая задача раскраски графа заключается в следующем: присвоить вершинам графа минимально возможное число цветов из множества С так, чтобы смежные вершины были окрашены в разные цвета. Так как раскраска осуществляет разбиение множества V на n непересекающихся подмножеств Vi , то эта задача может быть сформулирована следующим образом . Для множества вершин V мощностью m ( V = m ) графа G = ( V, Е ) без петель найти такое присвоение, что

А :V С, i, j = 1...m , A(vi ) A(vj ), eij E , n min. (3.16)

В отличие от классической, в рассматриваемой задаче цвета ( частоты ) некоторых пар смежных вершин должны быть не просто различными, а модуль разности их частот f ( vi ) - f( vj ) должен быть не менее определенной величины fij определяемой возможностью появления помех по побочным каналам приема супергетеродинного радиовещательного приемника. Используемые для радиовещания частотные каналы обозначим через F. При создании новых или развитии существующих радиовещательных сетей в граф передатчиков необходимо включать все взаимодействующие с новыми вершинами сети действующие станции, но частоты последних в большинстве случаев при решении задачи присвоения изменять нельзя. Подмножество вершин графа, биективных вещательным передатчикам с фиксированными частотами, обозначим через VД. Учтем также, что при назначении частот по условиям отсутствия помех по побочным каналам для некоторых подмножеств передатчиков Мl М являются недопустимыми частоты находящихся в смежных , зеркальных и гетеродинных каналах приема , описываемые функцией ( Vl ) = 0. Следовательно , задача присвоения частот является задачей раскраски взвешенного графа, часть вершин которого окрашена заранее, а для некоторых подмножеств вершин Vl существуют запрещенные комбинации цветов . Она может быть сформулирована как обобщенная задача раскраски графа следующим образом.

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

119

возможным на данном шаге номером. При правильной нумерации вершин и цветов полученная таким образом раскраска будет глобально - оптимальной в смысле минимизации числа использованных цветов. Критерием ранжирования вершин является степень сложности присвоения, которая связана с числом цветов C = { 1, ... , n } , любой из которых можно присвоить на данном шаге раскраски. Очевидно, на любом шаге

где ni0 - число смежных с i - той вершиной вершин с фиксированными цветами;

nпбк - число частот по побочным каналам приема , если i -тая вершина входит в подмножество Vl [3.3].

Анализ литературы [3.9 , 3.10] показал , что наиболее применимыми эвристическими процедурами раскраски графа являются алгоритмы, основанные на многократном упорядочении вершин графа и множества цветов при исключении из множества V окрашенной очередной вершины. Принятая классификация таких алгоритмов разделяет их на два класса : " вершина - краска " и " краска - вершина " . В первом случае сначала выбирается очередная из упорядоченного по какому - либо критерию списка вершина, а затем для нее выбирается первый из упорядоченного списка цвет. Далее данная процедура повторяется для оставшегося не окрашенным множества вершин графа до тех пор, пока их список не окажется пуст. Во втором подходе фиксируется первый из упорядоченных по какому - либо критерию списка цвет, а затем выбираются те вершины , которым этот цвет допустим для присвоения. Вершины так же выбираются путем ранжирования их списка. После невозможности выбора очередной вершины для данного цвета, осуществляется поиск нового цвета путем упорядочивания списка неиспользованных цветов.

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

Алгоритм содержит следующие основные операции

[3.11]:

– формирование очереди передатчиков;

– выбор по определенному критерию частоты ( канала ) для очередного передатчика ( из числа разрешенных для него частот ( каналов ) );

–корректировка таблицы разрешенных частот для передатчиков, не имеющих частотного присвоения, которые оказываются для них запрещенными вследствие присвоения канала очередному передатчику ;

–переход к рассмотрению следующего передатчика.

Алгоритм выбора каналов и передатчиков, при использовании алгоритмов типа "вершина - краска " и " краска - вершина " , включает следую-

120

щие операции :

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

-определение для каждого передатчика числа разрешенных ему для присвоения каналов;

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

Обобщенный алгоритм оптимального частотного планирования для группы ТВ передатчиков представлен на рис. 3.3. Он включает в себя: подготовку исходных данных – предполагаемая дислокация вещательного передатчика ( его координаты ) и его основные технические характеристики ; анализ ЭМС планируемых ТВ передатчиков с радиосредствами существующей ТВ и ОВЧ ЧМ сети и другого назначения; выбор очередного передатчика из планируемых и поиск для него частотного присвоения . Это справедливо для алгоритмов типа ―вершина - краска―, а для алгоритмов типа "краска - вершина" действия 4 и 5 меняются местами .

3.2.2 Разработка эвристических алгоритмов раскраски графов сетей радиовещания

Для проведения дальнейшего исследования удобно принять для рассмотрения регулярную телевизионную сеть состоящую из N передатчиков. Нумерацию передатчиков произведем начиная с левого нижнего передатчика, ему присваивается нулевой номер , до правого верхнего, ему присваивается номер ( N-1 ). Расстояние между двумя соседними передатчиками назовем модулем сети R0.

Как видно из рис. 3.3. основными блоками любого из возможных алгоритмов являются действия 3 , 4 и 5. Причем блок 3, анализ ЭМС радиосредств, является обязательным при использовании того или иного метода планирования. Этот блок определяет множество ребер Е графа ТВ сети и весовые коэффициенты ребер и вершин.

Анализ ЭМС проводится относительно предполагаемой зоны обслуживания ТВ передатчиков. При этом выбираются те радиосредства, которые могут создать помеху на основе расчетных значений частотно – пространственного разноса для наихудших условий ( максимальные значения ). Далее определяется наличие действующих ТВ и ОВЧ ЧМ передатчиков в том же пункте и исключаются из рассмотрения те частотные присвоения , которые поражаются данными радиосредствами ( по побочным каналам приема ) . Для оставшихся разрешенных частотных присвоений производится расчет мешающих полей от всех помех. Для упрощения расчетов принято исследовать условия ЭМС не на контуре зоны , а только в одной ее точке – точке размещения самого передатчика . Анализ ЭМС предполагает оценку как " прямого " , так и "обратного " мешающего влияния. Под первым понимается

121