Использование нейронных сетей для решения задач маршрутизации

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

НС решает задачи оптимизации, связанные с нахождением бесконфликтных потоков при заданных входных и выходных значениях. При этом НС легко адаптируется к изменениям условий.
С нейросетевыми алгоритмами маршрутизации в системах связи можно ознакомится в работах [9, 97], а один из возможных алгоритмов маршрутизации будет рассмотрен в п. 3.1.2.
Постановка и решение задачи распределения каналов в подвижных системах радиосвязи в нейросетевом базисе мало отличаются от постановки и решения задачи маршрутизации. Разница заключена в сотовой структуре радиосети и большом числе коммутируемых узлов [9, 56].

Один из возможных алгоритмов распределения каналов в подвижных системах радиосвязи рассматривается в п.3.1.4.
В п.3.1.3 описан нейросетевой алгоритм прогнозирования напряженности поля, который как и алгоритм распределения каналов в подвижных системах радиосвязи может быть использован на этапе проектирования таких систем.
Кроме вышеперечисленных областей применения нейронных сетей в телекоммуникационных системах, перспективным является использование нейросетевых алгоритмов в задачах кодирования и декодирования информации. В качестве первоочередных можно рассматривать задачи связанные с обработкой речевой информации и изображений [12] (см. п.2.1.1). Широко известным является метод сжатия информации, предложенный в 1987 году [13]. При этом используется трехслойный иерцеп-трон, у которого число элементов входного и выходного слоев одинаково, а число элементов скрытого слоя значительно меньше.

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

На одном конце линии помещают входной и скрытый слои перцеп-трона, а результат работы элементов скрытого слоя (короткие векторы) подают в канал. Поместив- на другом конце линии копию скрытого слоя и выходной слой, можно на выходе последнего воспроизвести исходный вектор.
Большое количество работ посвящено построению нейросетевых приемников систем множественного доступа [39, 71].
С другими вариантами применения НС в телекоммуникационных системах можно ознакомиться в [9, 12, 19, 44, 70, 75, 85, 93].
Таким образом, область применения искусственных НС в телекоммуникационных системах постоянно расширяется. В этих условиях появление на рынке недорогих как многофункциональных, так и ориентированных на решение конкретных задач нейрочипов и нейрокомпьютеров будет способствовать быстрому переходу к очередному этапу развития телекоммуникационных систем - появлению интеллектуальных телекоммуникационных систем.

Ждать этого, по всей видимости, остается совсем недолго.
3.2. Нейронные сети в системах автоматического распознавания речи
Хорошо известно, что речь человека характеризуется высокой степенью изменчивости. Это обусловлено несколькими причинами [6]. Во-первых, даже для одного и того же говорящего, реализации одних и тех же акустических единиц будут отличаться по своему спектральному составу и длительности произношения.

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

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

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

объединены с традиционными подходами для создания распознавателей больших словарей, изолированных слов и слитной речи [6].
Рассмотрим простейшую схему распознавания изолированных слов, представленную на рис. 3.1 [6].

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

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

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

С целью высококачественного распознавания обычно используется дополнительный этап, позволяющий учесть семантические, синтаксические и прагматические ограничения.
В схеме распознавания, изображенной на рис.3.1, НС наиболее успешно используются на второй стадии вычислений при расчете локальных метрик [87]. Для статистических распознавателей с непрерывным наблюдением данные метрики являются монотонными функциями функций правдоподобия векторов признаков.
Простейшие из этих функций, такие как логарифм функции правдоподобия для гауссовского распределения векторов независимых величин, могут быть рассчитаны с помощью однослойных сетей без их предварительного обучения (для известных параметров распределений) [6]. При вычислении более сложных метрик могут быть использованы многослойные перцептроны, способные вычислять функции любой сложности. При настройке весовых коэффициентов таких сетей используется способность многослойного псрцептрона, имеющего достаточное число связей, аппроксимировать апостериорную вероятность классов после его обучения для выполнения классификации [6, 98]. Данное свойство было успешно использовано для создания высокоэффективных гибридных подходов к распознаванию слитной речи, основанных на скрытых марковских моделях (СММ), где многослойные сети служат для вычисления правдоподобий состояний СММ [47, 90].

Использование НС в таких подходах позволяет учитывать при выполнении распознавания акустический контекст векторов наблюдений СММ и снять допущения относительно формы распределения этих векторов [6].
Распознаватели речи с дискретным наблюдением сначала выполняют векторное квантование и присваивают каждому вектору признаков определенный символ из кодовой книги. Затем на основе этих символов с помощью специальных таблиц, содержащих вероятности наблюдения символов для каждого эталонного вектора, вычисляются локальные метрики. Такие вычисления могут быть выполнены однослойными перцептронами, состоящими из линейных узлов, число которых равно числу эталонов.

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

Каждый узел вычисляет евклидово расстояние между входным вектором сети и соответствующим эталоном, представленным весами узла, после чего выбирается узел с наименьшим евклидовым расстоянием. Веса данной сети вычисляются с помощью алгоритма Кохонена, его модификаций [6] или с помощью любого другого традиционного алгоритма векторного квантования, использующего в качестве метрики евклидово расстояние (например, с помощью кластеризационно-го алгоритма к-средних [6, 87].
Многослойные нейронные сети также могут быть использованы для снижения размерности векторов признаков, извлекаемых препроцессором на начальном этапе распознавания. Такая НС имеет столько же выходов, сколько и входов, и один или более слоев скрытых узлов. При обучении НС ее веса подбираются так, чтобы она могла воспроизводить на выходе любой входной вектор через небольшой слой скрытых узлов.

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

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

Использование динамических сетей при распознавании речи позволяет преодолеть основные недостатки, присущие статическим сетям, и, как показывают экспериментальные исследования, приводит к превосходному качеству распознавания для акустически схожих слов, согласных и гласных [6]. Частота ошибок у динамических сетей для задач с малым словарем часто оказывалась значительно ниже, чем у лучших альтернативных распознавателей, в том числе и основанных на СММ.
Нейронная сеть с временными задержками (НСВЗ) представляет собой многослойный перцептрон, узлы которого модифицированы введением временных задержек. Узел, имеющий N задержек т, 2т, ...,Nr , показан на рис. 3.2.

Он суммирует взятые в N+1 последовательных моментов времени J своих входов, умноженных на соответствующие весовые коэффициенты, вычитает порог и вычисляет нелинейную функцию F полученного результата.
Архитектура трехслойной НСВЗ, предложенной для распознавания трех фонем (или трех классов фонем), показана на рис. 3.3 (на нем показаны связи только для одного выходного узла).
На рис. 3.3 показано, что обработка сетью входной последовательности акустических векторов эквивалентна прохождению окон временных задержек над образами узлов нижнего уровня.

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

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

Простая структура делает НСВЗ подходящей для стандартизованной СБИС-реализации с загружаемыми извне весами.

Рис. 3.3. Архитектура НСВЗ

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

Использование нейронных сетей для решения задач маршрутизации

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

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

Эти модели явились началом развития нейронных методов решения сложных оптимизационных задач. Большинство последующих исследований так или иначе базировались именно на них [77, 78].

Коротко остановимся на формулировке и основных принципах организации вычислений при решении задачи коммивояжера.
Для некоторой группы городов с известными расстояниями между ними требуется найти кратчайший маршрут посещения каждого города один раз с возвращением в исходную точку.
Обозначим города, которые необходимо посетить, буквами А, В, С..., а расстояния - сідв* d_AC...d_Bc--- Решением является упорядоченное множество из п городов. Последовательность, в которой обходятся города удобно представлять матрицей п х п , строки которой соответствуют городам, а столбцы номерам городов в последовательности. Например, имеется пять городов А, В, С, D, Е, а последовательность обхода этих городов задана матрицей
А
В
С
D
Е
(3.1)
1 2 3 4 5 0 10 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 0 10 0
Таким образом город С посещается первым, город А - вторым и т. д. Длина маршрута равна d_CA + d_AE +...+ d_DC. В каждом столбце и в каждой строке этой матрицы может быть только одна единица, так как в каждый момент посещается только один город и каждый город посещается только один раз. Матрицу вида (3.1) можно воспринимать как состояние нейронной сети из N = п2 нейронов. Задача состоит в том, чтобы из nJ^_n маршрутов выбрать один с наименьшей длиной.

Состояние каждого нейрона описывается двумя индексами, которые соответствуют городу и порядковому номеру его посещения в маршруте. Например, У . = 1 показывает,
что город х был j -м по порядку городом маршрута.
Запишем функцию вычислительной энергии для сети, предназначенной для решения задачи коммивояжера, в которой состояние с наименьшей энергией соответствует самому короткому маршруту. В общем виде такая функция для рассматриваемой сети может иметь следующий вид [19]:
Е = -У 4Y, -1Ч, + X Ч, ¦ (3.2)
z ' і J J
где Е - искусственная энергия сети, w_ij - вес от выхода нейрона і к входу нейрона j, Yj - выход нейрона j, /_у - внешний вход нейрона j, Т_}-порог нейрона j.
Изменение энергии, вызванное изменением состояния j -нейрона, можно вычислить следующим образом:

(3.3)
Каждому состоянию системы соответствует конкретная величина вычислительной энергии. Устойчивое состояние имеет меньшую энергию, чем неустойчивое.

Эволюция системы во времени - это движение в пространстве состояний в поисках минимума энергии и остановка в этой точке.
Для рассматриваемой системы функция энергии должна удовлетворять следующим требованиям [32]. Во-первых, она должна поддерживать устойчивые состояния в форме матрицы (3.1).

Во-вторых, из всех возможных решений функция энергии должна поддерживать те, которые соответствуют коротким маршрутам. Этим требованиям удовлетворяет функция энергии вида (при этом, Y . = 0,1)

(3.4)
Первые три члена выражения (3.4) поддерживают первое требование, четвертый член - второе; А, В, С, D - положительные множители. Первый член равен нулю, если каждая строка х содержит не больше одной единицы. Второй член равен нулю, если каждый столбец содержит не более одной единицы.

Третий член равен нулю, если в матрице вида (3.1) п единиц. Таким образом, без учета четвертого члена функция энергии имеет минимумы (Е = 0) во всех состояниях, представленных матрицей с одной единицей в каждом столбце и каждой строке. Все другие состояния имеют более высокую энергию. Короткие маршруты поддерживает четвертый член.

В нем индексы і берутся по mod/7, для того чтобы показать, что і -й город соседствует в маршруте с (/7 -1) -м и первым, т. е. Y_k . = Y_kj. Четвертый член численно равен длине маршрута.
Раскрывая скобки в (3.4) и приравнивая коэффициенты при квадратичных и линейных членах в полученном выражении и общей формуле энергии (2.2), определяем матрицу связей и внешние взаимодействия:
W** = -Л5_л(\-8,)~ В8_? о-8_Л) - с - Orf* (S_!M+S_u_,). (3.5)
где 5_:/ = 1 , если і = /, в противном случае 5_у = 0 . Кроме того, каждый нейрон имеет смещающий вес І_хі = Сп .
Первый член в (3.5) задает связи нейронов в каждой строке, второй -внутри каждого столбца, третий и четвертый - глобальные связи. И в (3.4) и в (3.5) три первых члена отвечают за общие ограничения для любой задачи коммивояжера и приводят сеть к финальному состоянию в виде (3.1).
Четвертый член управляет тем, какое из пУ^_п возможных различных финальных состояний соответствует самому короткому маршруту.
Рассмотрим вариант совместного решения задачи маршрутизации и планирования использования линий радиосвязи для сети пакетной радиосвязи с многоскачковой топологией. Важность взаимосвязи между маршрутизацией и вопросами планирования последовательности выбора направления для передачи по используемым линиям связи показана в [65]. Там же обобщен случай непрерывного трафика для определенного класса сетей. При этом выбор маршрутов максимизирующих степень узла в сети, позволяет спланировать работу так, чтобы время ее выполнения было минимальным.

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

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

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

где Я - j -й маршрут между SD парой /,
\Р₀ ОР_кІ\ - число узлов, которые совместно используют маршруты Р_ци ри,
[1, если выбирается Р~
'' 0, если не выбирается P_tj
N_р(і) - число вариантов маршрутов, определенных между SD парой і.
Цель состоит в минимизации Е_ь с учетом того, что для каждой пары SD выбирается только один маршрут (т. е. Н = 1 для единственного значения j для каждого значения і). В этом случае энергия перегрузки соответствует сумме числа общих узлов всех выбранных маршрутов (одного для каждой SD пары), взятых попарно. Например, на рис.

3.4 показана простая сеть пакетной радиосвязи с шестью узлами и двумя маршрутами между каждой из двух SD пар.

Задача маршрутизации состоит в выборе либо пары Р_и или Р₁₂ для соединения SI с D1 и либо пары Р_2] или Р₂₂ для соединения S2 с D2. Допустимое решение, которое задается выбором трасс Р_и и Р₂₂, имеет энергию перегрузки E_b = 1, так как эти маршруты имеют один общий узел (узел 6).
Теперь рассмотрим модель НС Хопфилда, используемую в этом случае для выбора маршрута между несколькими SD парами в сети пакетной радиосвязи. Выходные напряжения нейронов (которые и определяют их состояния) такой НС приближаются к двоичным значениям по мере перехода сети к состоянию устойчивого равновесия с минимальной "энергией". Соединения между нейронами і и j описываются весом 77 , который
положителен если соединение возбуждающее и отрицателен, если соединение тормозящее (запрещающее). В рассматриваемой модели НС для каждого маршрута между каждой SD парой определяется один нейрон.

Вариант модели НС для сети изображенной на рис. 3.4 представлен на рис.

3.5. В соответствии с рис. 3.5 нейрон ij отображает j маршрут между SD парой і.
НС эволюционирует от какого-то начального состояния до состояния равновесия, которое отображает минимум (не обязательно глобальный) функции энергии Ляпунова, которая по аналогии с (3.2) может быть записана через веса соединений, токи смещения и напряжения на выходах нейронов следующим образом [111]:
1 І??л^шЛЩіЭЛЩ*) N_snN_pU)
= у У У Угл - 3-7)
У /=| *=1 у= I ,=| І=1 у=1
В выражении (3.7) T_ijkl - вес соединения между нейронами ij и /, /_у - ток смещения, прикладываемый к нейрону ij, N (і) - число маршрутов между SD парой і. В рассматриваемой модели веса соединений являются симметричными (т. е. 77 _kl = Т_кі ). Эта симметрия гарантирует сходимость к устойчивому состоянию [111]. Общее число нейронов N задается как N = N (і). Таким образом, веса соединений T_ijk, являются элементами матрицы связности размерности NxN .
Таким образом, целевая функция, моделируемая с помощью НС Хопфилда, включает взвешенные суммы произведений пар выходных напряжений нейрона и выходных напряжений взятых по отдельности. При выборе Е_ь вида (3.6) предполагалось, что оценивается энергия перегрузки сети в допустимом состоянии, т. е. активируется только один маршрут для каждой SD пары (т. е. V_ij = 1 для единственного значения j для каждого

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