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

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

Антон Кутафин

Дмитрий Некрылов

1. Введение.

В наше время миллионы людей используют услуги, предоставляемые телекоммуникационными сетями, в повседневной жизни и это число непрерывно растёт. Современные технологии позволяют использовать сети связи для обычного просмотра web – страниц, отправки электронных писем, передачи голоса и видео. Трафик пакетных данных достиг таких объёмов, что для телекоммуникационных компаний любого типа он стал заметным источником доходов, поэтому сети IP эксплуатируются всё активнее. С целью увеличения прибыли операторы стараются повысить эффективность использования сети, а значит, методы оптимизации сетей IP приобретают все большую значимость. Максимальный коммерческий эффект от сети IP не может быть получен без рационального использования всех сетевых ресурсов — в первую очередь маршрутизаторов и каналов связи. Функционирование пакетной сети можно считать эффективным только тогда, когда каждый ресурс загружен, но не перегружен.

Несколько лет назад услуги телевидения и телефона предоставлялись пользователям по различным сетям доступа. В конце 90-х – начале 2000 года в телекоммуникации начался новый этап развития индустрии, а именно конвергенция трафика. Теперь по одним и тем же сетям доступа пользователи могут получать услуги и телевидения, телефонии, доступа в Internet и др. виды сервисов. Однако методы маршрутизации, которые применялись для трафика единственного типа сервиса, стали неэффективными для трафика пакетов различных сервисов.

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

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

2. Обзор технологии РРЛ.

Рассмотрим подробнее, что же представляет собой технология РРЛ, ее принципы, аспекты построения радиорелейных сетей и сферы применения.

2.1 История РРЛ, область применения и перспективы развития.

Современные экспертные оценки признают, что линии связи на основе радиорелейного оборудования во многих случаях могут быть альтернативой волоконно-оптическим (ВОЛС). Дело не только в дешевизне радиорелейных линий, но в том, что за 60-летнюю историю развития радиорелейной связи оборудование РРЛ достигло очень высокого технического уровня. При этом оно позволяет оперативно развертывать сети связи с различной топологией: "звезда", "магистраль", "кольцо" и пр., а также может быть использовано в условиях, когда прокладка оптического кабеля невозможна.

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

На магистральных направлениях (где нелегко развернуть полноценную кабельную инфраструктуру, а еще сложнее поддерживать и развивать ее в соответствии с требованиями рынка) традиционно использовались и будут широко использоваться РРЛ, образно названные Р. Подойницыным («Микротест») цифровыми быстро возводимыми мостами, устраняющими цифровой разрыв на огромной территории страны. При этом, по мнению Г. Муратова («Эрикссон»), в России тенденции развития РРЛ как одного из направлений телекоммуникационных транспортных систем не отличаются от общемировых. Более того, опираясь на статистику использования РРЛ, можно утверждать, что рынок России и других стран бывшего СССР в значительной мере определяет эти тенденции. Для мобильных операторов, у которых, по данным агентства Visant Strategies, сосредоточено более 70% всех приемопередатчиков РРЛ в мире, этот вид связи оптимален для быстрого развертывания современной управляемой сетевой инфраструктуры с большой пропускной способностью на обширной, зачастую неосвоенной территории.

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

За несколько лет своей «новой истории» российский рынок РРС прошел несколько стадий развития. Специалисты компании Telecor считают, что подъем в конце прошлого – начале нынешнего века был обусловлен бурным развитием операторов мобильной связи и компаний, сдающих в аренду каналы передачи данных. На этапе расширения зон покрытия наблюдался количественный рост радиорелейного оборудования PDH, который позже (по мере осознания региональными сотовыми операторами необходимости объединяться, имея собственные каналы связи) сменился ростом качественных показателей – началось активное строительство радиорелейных сетей SDH.

Среди корпоративных пользователей – в основном компании транспортной, энергетической, нефтегазовой отраслей. Построение собственной беспроводной инфраструктуры позволяет крупным фирмам снизить затраты на поддержку сети, добиться лучшего соответствия коммуникационных средств бизнес-процессам и высокой надежности и независимости от внешних факторов. В этом сегменте, видимо, будет расширяться строительство систем связи на основе РРЛ, что обусловлено в первую очередь ростом добывающей и перерабатывающей отраслей в сфере полезных ископаемых в России и связанного с этим увеличения финансовых возможностей компаний. Прокладка топливопроводов, открытие новых точек добычи требуют оперативной организации новых направлений технологической связи, а территориальная распределенность и местонахождение филиалов компаний, как правило, в труднодоступных районах делает использование РРЛ зачастую единственно возможным решением. При этом увеличение объемов передаваемой информации обусловливает выбор технологии SDH.
Сегодня все вендоры, независимо от «национальности», готовятся к новому этапу конкурентной борьбы, главные аргументы в которой – надежность оборудования; высокая пропускная способность; гибкость, универсальность, возможность передавать как TDM-, так и IP-трафик; масштабируемость; интеграция с PDH/SDH-проводными системами передачи; эффективность системы управления (удаленный контроль, диагностика и мониторинг, динамическое управление трафиком); возможности миграции и апгрейда оборудования только за счет замены ПО; экономичность, минимизация габаритов и энергопотребления. Ю. Скирта (НПФ «Микран») убежден, что РРЛ, которые применяются во всех регионах России, продолжат свое развитие в ближайшие 15–20 лет – до тех пор, пока самые отдаленные уголки страны не будут обеспечены связью.

Первые РРЛ были придуманы и сделаны в СССР в середине ХХ века. Их особенности – оперативная установка оборудования при сравнительно небольших затратах, высокая эксплуатационная рентабельность, способность создавать каналы связи между удаленными объектами без прокладки кабеля. Радиорелейные линии были призваны в основном решать задачи связи для войсковых частей.

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

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

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

Сразу оговоримся, что речь идет о «гражданской» радиорелейной связи, главная проблема которой – «прописка в радиочастотном доме». У РРС военного назначения такой проблемы нет, и, судя по тому, что добрая половина работающих на российском рынке производителей радиорелейного оборудования поставляет свою продукцию войскам связи, историческое предназначение РРЛ остается в силе.

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

Среди технических средств, применяемых при построении телекоммуникационных сетей, РРЛ занимают особое место. Зачастую РРЛ являются единственным средством в районах, где прокладка кабеля невозможна или нецелесообразна по экономическим соображениям. Традиционно РРЛ используются для организации магистральных и внутризоновых каналов связи, межстанционной связи, абонентских выносов, в том числе в составе интегрированного комплекса оборудования класса «точка-много точек». При ограниченной по сравнению с оптическим кабелем пропускной способности радиорелейный тракт тем не менее эффективен в условиях средней и невысокой плотности населения, которая, как правило, характеризуется так называемым очаговым спросом.

В последнее время в сельских, малонаселенных, удаленных и труднодоступных районах стали широко использовать малоканальные РРЛ, которые изначально предназначены для организации каналов связи на большие расстояния, в том числе на полузакрытых трассах. И хотя скорость передачи в радиоканалах, образованных такими РРЛ, невелика (до 2,048 Мбит/с), в районах с низкой плотностью населения важна длина интервала радиорелейной линии, а она, в силу физических свойств радиоволн этого участка спектра, может достигать 50–70 км.

«ЦентрТелеком» рассматривает РРЛ как эффективную альтернативу традиционной сети. В сельских районах, где отсутствует проводная инфраструктура, перспективным является использование малоканальных РРЛ, в том числе при развертывании сетей для оказания универсальных услуг. Возможности радиорелейных станций при этом достаточно широки. В зависимости от конкретной ситуации радиорелейную линию можно использовать для абонентского доступа (при наличии в составе оборудования функционально законченных абонентских окончаний), в сочетании с оконечным мультиплексорным оборудованием или оборудованием АТС, в сочетании с другими средствами абонентского радиодоступа. Безусловно, целесообразность применения радиорелейных систем, равно как и других технологических решений, безусловно, должна быть обоснована детальным технико-экономическим расчетом, с учетом возможности получения разрешений на использование частот. Особенно актуально это сегодня, в условиях конвергентной интеграции телекоммуникаций и сетей передачи данных.

2.2 Преимущества РРЛ, некоторые аспекты построения сети на основе радиорелейного оборудования.

По сравнению с проводной и спутниковой связью, радиорелейные линии (РРЛ) достаточно легко обслуживаются и характеризуются такими показателями, как:

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

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

Как известно, радиочастотный ресурс ограничен, поэтому использовать его следует экономно. Для этого важно правильно составить частотный план для радиорелейной линии. Проект сети РРЛ, кроме сведений о количестве и месторасположении сетевых узлов, должен содержать информацию о номиналах рабочих радиочастот. Разнос между частотами приема и передачи должен быть не менее 155 МГц.

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

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

Возможно использование РРЛ и для организации абонентских линий связи (проблема "последней мили"). Для этого рабочие частоты всех передатчиков и приемников на одном объекте должны быть одинаковыми.

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

Стандартные параболические антенны диаметром 60 см позволяют получить устойчивую, не зависящую от погодных условий радиосвязь на расстояниикм в зависимости от "чистоты" трасы (наличия радиопомех). Для расстояний более 25 км необходимо использовать параболические антенны большего диаметра см.).

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

Для размещения оборудования РРЛ обычно используются крыши высоких зданий или специальные антенные мачты. Длина кабеля от радиооборудования до оборудования Ethernet может достигать 400 м. что дает дополнительные возможности при установке приемопередатчика на необходимой высоте. Корпус приемопередатчика и антенна должны быть надежно заземлены.

2.3 Общие принципы построения РРЛ.

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

Необходимость этого процесса связана с тем, что информация, преобразованная в электрический сигнал, имеет относительно низкую частоту, которая, как известно, плохо излучается. Модулированные ВЧ колебания, называемые радиосигналом, подаются в передающую антенну и возбуждают в окружающем пространстве электромагнитные волны. Небольшая часть энергии электромагнитных волн от передатчика достигает приемной антенны и создает в ней слабый модулированный ток высокой частоты. В приемнике 4 ВЧ модулированные колебания усиливаются и затем преобразуются в 5 обратно в сигнал такого же вида, как полученный в пункте передачи от преобразователя. Такое преобразование называется детектированием. Далее сигнал поступает в воспроизводящее устройство 6 – буквопечатающий аппарат, телефон, телевизионную приемную трубку и т. п., после чего принятая информация поступает к получателю.
Комплекс из передатчика, передающей антенны, среды распространения волн, приемной антенны и приемника образует радиолинию. Радиолиния, как видно из рис. 1, допускает одностороннюю передачу информации из пункта размещения передающей станции в пункт, где находится приемник. Обратная передача в этом случае не предусматривается.
Односторонняя передача используется чаще не в радиосвязи, а в звуковом и ТВ радиовещании, в службах передачи информации для агентств печати, метеорологической информации, сигналов точного времени, точной частоты и др. Чтобы улучшить эффективность использования оборудования и увеличить пропускную способность радиолинии, применяют аппаратуру уплотнения (рис. 2). Передающая часть аппаратуры образует из сигналов различных источников информации 1а–1n, преобразованных преобразователями 2а–2n, единый групповой сигнал. Приемная часть этой аппаратуры разделяет сигналы, производит их преобразование (7а–7n), после чего они поступают к потребителям 8а-8n. Совокупность технических средств, обеспечивающих передачу сообщения от одного источника информации к получателю, называется каналом радиосвязи. Система радиосвязи с уплотнением радиолинии называется многоканальной радиосвязью.

Для обмена информацией между двумя пунктами организуется двусторонняя радиосвязь, которая обеспечивается при помощи двух комплектов оборудования односторонней связи, действующих навстречу друг другу. В каждом конечном пункте двусторонней линии радиосвязи размещаются и приемное и передающее оборудования. Источник и получатель информации обычно совмещены, а также передатчик и приемник в некоторых случаях объединяются в единой приемо-передающей радиостанции. Тогда в каждом пункте обычно вместо двух антенн имеется одна общая приемо-передающая антенна. Двусторонняя радиосвязь может организовываться по двум вариантам:
1. Оба передатчика работают на одной и той же частоте, т. е. и приемники настроены на одну и ту же частоту. В этом случае радиолиния в оба направления одновременно работать не может. Работа производится поочередно в одном из направлений. Такая связь называется симплексной.
2. Передатчики работают на разных частотах, соответственно и приемники настроены на разные частоты. В этом случае радиолиния в оба направления может работать одновременно. Такая связь называется дуплексной.

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

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

РРЛ связь – это особый вид радиосвязи на УКВ волнах с многократной ретрансляцией сигнала. К УКВ радиоволнам относятся волны длиной короче 10 м, что соответствует частотам выше 30 МГц. Полоса частот, соответствующих диапазону УКВ, очень широкая, и в этом диапазоне можно разместить гораздо большее число радиостанций, работающих без взаимных помех, чем в диапазонах более длинных волн.
В диапазоне УКВ полоса частот приемопередающего оборудования может быть сделана очень широкой. Как известно, отношение ширины полосы пропускания одиночного колебательного контура к его резонансной частоте равна Df / f0 = 1/ Q , где Q –добротность контура. Обычно в контурах, применяемых в радиоустройствах, это отношение не превышает нескольких процентов (1 ÷ 3) % , следовательно, если на волне длиной 1000 м. ширина полосы контура может быть 3 ÷ 9 кГц, то на волне длиной 10 см она составляет 30 ÷ 90 МГц. Таким образом, на УКВ можно осуществлять передачу сигналов, занимающих очень широкую полосу частот, например TV или большое число ТЛФ.

Важной особенностью диапазона УКВ является практическое отсутствие на этих волнах внешних помех: атмосферных и промышленных. Единственным видом помех, существующим в диапазоне УКВ, являются собственные шумы ламп и сопротивлений в радиоприемниках. Антенны, обладающие большой направленностью на ультракоротких волнах, имеют сравнительно небольшие размеры, т. к. к. н.д. обратно пропорциональны квадрату длины волны при постоянной площади антенны. Qа >> 40 дБ (>>10000 раз) по мощности. С такой антенной передатчик мощностью в 1 Вт создает напряженность поля в точке приема равную передатчику мощностью 10 кВт, работающему на ненаправленную антенну.

Таким образом, применение УКВ для организации связи обеспечивает: - возможность передачи сигналов, занимающих очень широкую полосу частот (ТV, многоканальных ТЛФ); отсутствие внешних помех; - возможность осуществления устойчивой связи при малой мощности передатчика, благодаря применению направленных антенн. Недостатком радиосвязи на УКВ является ограниченная дальность. УКВ радиоволны, особенно дециметровые и сантиметровые, не отражаются от ионосферы и очень слабо огибают препятствия, поэтому дальность радиосвязи на этих волнах ограничена. При малой мощности передатчиков устойчивая связь на дециметровых и сантиметровых волнах возможна в пределах прямой видимости. За пределами прямой видимости напряженность поля очень быстро падает с увеличением расстояния между станциями, и связь становится ненадежной. Вследствие этой особенности распространения волн, дальняя связь на УКВ возможна только с помощью ретрансляционных или радиорелейных линий

2.4 Классификация РРЛ.

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

1. Линии с частотным разделением (ЧР ) каналов и частотной модуляцией.
2. Линии с временным разделением (ВР) каналов и импульсной модуляцией.

По областям применения РРЛ можно классифицировать следующим образом:

Магистральные линии большой емкости. Эти линии имеют значительную протяженность и предназначены для организации 600 и более ТЛФ каналов. Общее число ТЛФ каналов на магистральных линиях может достигать нескольких тысяч при так называемой многоствольной работе. Для этого на каждой станции устанавливается несколько комплектов приемо-передающей аппаратуры, так что образуется несколько параллельных радиоканалов (стволов), работающих на разных несущих частотах на общих антенно-фидерных устройствах. Число стволов на магистральных РРЛ может достигать 6 ÷ 8, причем часть стволов обычно используется для передачи ТV программ, а один или два ствола являются резервными – на них автоматически переключается передача сообщений при выходе из строя основных стволов (отводится сантиметровый и миллиметровый диапазон волн). Линии средней емкости, используются на ответвлениях от магистральных линий и на внутриобластных связях и предназначаются для организации от 60 до 300 ТЛФ каналов. Причем на одной линии обычно работает до 3 стволов (отводится дециметровый диапазон волн). Малоканальные РРЛ с емкостью не более 30 ТЛФ-каналов используются для местной или, так называемой, низовой связи. На этих линиях чаще всего используется аппаратура в виде контейнера, которая зарывается в землю у основания относительно невысокой и простой по конструкции антенной мачты (отводится обычно метровый и дециметровый диапазон волн). РРЛ для связи на железнодорожном транспорте, газопроводах, нефтепроводах, линиях электропередач и т. п. Число ТЛФ обычно до 30 каналов, необходимо выделение на каждой станции. Поэтому применяется аппаратура с ВР (отводится дециметровый диапазон волн). РРЛ с подвижными станциями. Используются для нужд обороны, а также для оперативной замены поврежденных участков РРЛ и кабельной магистрали (в зависимости от назначения выбирается диапазон волн). Тропосферные РРЛ с расстояниями между станциями до 300-400 км и емкостью до 120 ТЛФ каналов (конец метрового и начало дециметрового диапазона волн). РРЛ с использованием ИСЗ с расстоянием между наземными станциями до нескольких тысяч километров, предназначенные для передачи сигналов ТВ и многоканальной ТЛФ (конец дециметрового и начало сантиметрового диапазона волн).

2.5 Диапазоны частот, отведенные для РРЛ.

В соответствии с классификацией РРЛ по назначению, способам разделения каналов и областью применения, отводится и диапазон частот для работы данной РРЛ.

1. Наземные РРЛ или РРЛ прямой видимости, в зависимости от емкости работают в диапазоне от метровых волн до сантиметровых.
Малоканальные РРЛ работают в нижней части диапазона, а многоканальные или широкополосные - в верхней. Применение более высоких частот (11 ГГц и выше) приводит к дополнительному ослаблению сигнала, так как длина волны становится соизмеримо с размерами атмосферных осадков.

2. Тропосферные РРЛ – это такие РРЛ, в которых за счет отражения от тропосферы осуществляется дальнее распространение УКВ волн. Работают они в диапазоне 1000 МГц (дециметровые волны).

3. Тропосферные РРЛ – работают в диапазоне 3,8; 8,4 ГГц и 11; 14 ГГц – сантиметровые волны.

2.6 Виды станций на РРЛ.

На РРЛ имеется несколько видов станций.

1. Оконечная станция (OC), предназначаются для ввода в РРЛ многоканального и ТВ сигнала на стороне передачи и для выделения этих сигналов на стороне приема. ОС РРЛ связана соединительными линиями с МТС и ТЦ. Часто ОС совмещаются с ТЦ.

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

В малоканальных РРЛ и особенно в РРЛ с временным разделением применяется построение аппаратуры ПС, при котором демодуляция и модуляция производится на каждой ПС. Это позволяет вводить и выводить ТЛФ каналы на любой ПС.

3. Узловые станции (OС) предназначаются для выделения части ТЛФ каналов и введения соответствующего количества новых каналов. От УС часто берут начало новые РРЛ (линии ответвления). В ТЛФ стволах на УС производится демодуляция сигналов со стороны приема и модуляция со стороны передачи. При необходимости эти преобразования производятся и в ТВ стволах.

3. Архитектура сети GSM и UMTS

Вкратце опишем основные принципы устройства сетей GSM и UMTS (с точки зрения организации сети они практически одинаковы), и рассмотрим, в какой именно плоскости лежит наша задача.

3.1 Основные части системы GSM, их назначение и взаимодействие друг с другом.

Для начала рассмотрим т. н. «Блок схему» сети, описывающую общую картину взаимодействия ее элементов.

Рис.1 Упрощенная архитектура сети GSM.

Самая простая часть структурной схемы - переносной телефон, он состоит из двух частей: собственно "трубки" - МЕ (Mobile Equipment - мобильное устройство) и смарт-карты SIM (Subscriber Identity Module - модуль идентификации абонента), получаемой при заключении контракта с оператором. Каждому сотовому телефону на заводе присваивается собственный уникальный номер - IMEI (International Mobile Equipment Identity - международный идентификатор мобильного устройства), который может передаваться сети по ее запросу. SIM, в свою очередь, содержит так называемый IMSI (International Mobile Subscriber Identity - международный идентификационный номер абонента). Разница между IMEI и IMSI в том, что IMEI соответствует конкретному телефону, а IMSI - определенному абоненту, точнее сим-карте.

"Центральной нервной системой" сети является NSS (Network and Switching Subsystem - подсистема сети и коммутации), а компонент, выполняющей функции "мозга" называется MSC (Mobile services Switching Center - центр коммутации). MSC в сети может быть и не один (в данном случае очень уместна аналогия с многопроцессорными компьютерными системами). Именно MSC занимается контролем вызовов, управлением BSS, формированием данных для биллинговой системы, сбором статистики о сети, осуществляет взаимодействие с внешними сетями и т. д. и т. п.

Следующая часть NSS, это HLR (Home Location Register - реестр собственных абонентов) и VLR (Visitor Location Register - реестр «гостей»). HLR, представляет собой базу данных обо всех абонентах, заключивших с рассматриваемой сетью контракт. В нем хранится информация о номерах пользователей (под номерами подразумеваются, во-первых, упоминавшийся выше IMSI, а во-вторых, так называемый MSISDN-Mobile Subscriber ISDN, т. е. телефонный номер в его обычном понимании), перечень доступных услуг и многое другое - далее по тексту будут описываться некоторые параметры, находящиеся в HLR.

В отличие от HLR, который в системе один, VLR`ов может быть и несколько - каждый из них контролирует свою часть сети. В VLR содержатся данные об абонентах, которые находятся на его (и только его!) территории, причем он обслуживает не только абонентов своего провайдера, но и управляет доступом в сеть абонентов других операторов. Как только пользователь покидает зону действия какого-то VLR, информация о нем копируется в новый VLR, а из старого удаляется. Фактически, между тем, что есть об абоненте в VLR и в HLR, очень много общего – в таблицах ниже приведен перечень долгосрочных (табл.1) и временных (табл.2 и 3) данных об абонентах, хранящихся в этих реестрах. Заметим, что в HLR для каждого абонента постоянно присутствует ссылка на тот VLR, который с ним (абонентом) сейчас работает (при этом сам VLR может принадлежать чужой сети, расположенной, например, на другом конце Земли).

1.	Международный идентификационный номер подписчика (IMSI)
2.	Телефонный номер абонента в обычном смысле (MSISDN)
3.	Категория подвижной станции
4.	Ключ идентификации абонента (Ki)
5.	Виды обеспечения дополнительными услугами
6.	Индекс закрытой группы пользователей
7.	Код блокировки закрытой группы пользователей
8.	Состав основных вызовов, которые могут быть переданы
9.	Оповещение вызывающего абонента
10.	Идентификация номера вызываемого абонента
11.	График работы
12.	Оповещение вызываемого абонента
13.	Контроль сигнализации при соединении абонентов
14.	Характеристики закрытой группы пользователей
15.	Льготы закрытой группы пользователей
16.	Запрещенные исходящие вызовы в закрытой группе пользователей
17.	Максимальное количество абонентов
18.	Используемые пароли
19.	Класс приоритетного доступа

Таблица 1. Полный состав долгосрочных данных, хранимых в HLR и VLR.

1.	Параметры идентификации и шифрования
2.	Временный номер мобильного абонента (TMSI)
3.	Адрес реестра перемещения, в котором находится абонент (VLR)
4.	Зоны перемещения подвижной станции
5.	Номер соты при эстафетной передаче
6.	Регистрационный статус
7.	Таймер отсутствия ответа
8.	Состав используемых в данный момент паролей
9.	Активность связи

Таблица 2. Полный состав временных данных, хранимых в HLR.

1.	Временный номер мобильного абонента (TMSI)
2.	Идентификаторы области расположения абонента (LAI)
3.	Указания по использованию основных служб
4.	Номер соты при эстафетной передаче
5.	Параметры идентификации и шифрования

Таблица 3. Полный состав временных данных, хранимых в VLR.

NSS содержит еще два компонента - AuC (Authentication Center - центр авторизации) и EIR (Equipment Identity Register - реестр идентификации оборудования). Первый блок используется для процедур установления подлинности абонента, а второй, как следует из названия, отвечает за допуск к эксплуатации в сети только разрешенных сотовых телефонов. Подробно работа этих систем будет рассмотрена в следующем разделе, посвященном регистрации абонента в сети.

Транспортной частью сети провайдера, является BSS (Base Station Subsystem - подсистема базовых станций). Если продолжать аналогию с человеческим организмом, то эту подсистему можно назвать конечностями тела. BSS состоит из узлов управления небольшим количеством локальных точек доступа - BSC (Base Station Controller - контроллер базовых станций), и точек доступа, с которыми непосредственно связывается абонент - BTS (Base Transceiver Station - базовая станция). Базовые станции можно наблюдать повсюду, фактически это просто приемно-передающие устройства, содержащие от одного до шестнадцати излучателей. Каждый BSC контролирует целую группу BTS и отвечает за управление и распределение каналов, уровень мощности базовых станций и некоторые другие параметры. Пример топологии BTS, принадлежащих одному BSC приведен на рисунке.

3.2 Регистрация в сети.

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

Пусть сеть найдена. По запросу сети телефон передает IMSI абонента. IMSI начинается с кода страны "приписки" его владельца, далее следуют цифры, определяющие домашнюю сеть, а уже потом - уникальный номер конкретного подписчика. Например, начало IMSI 25099… соответствует российскому оператору Билайн. (250-Россия, 99 - Билайн). По номеру IMSI VLR гостевой сети определяет домашнюю сеть и связывается с ее HLR. Последний передает всю необходимую информацию об абоненте в VLR, который послал запрос, а у себя размещает ссылку на этот VLR, чтобы в случае необходимости знать, "где искать" абонента.

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

3.3 Территориальное деление сети и handover.

Как уже было сказано, сеть состоит из множества BTS - базовых станций (одна BTS - одна "сота", ячейка). Для упрощения функционирования системы и снижения служебного трафика, BTS объединяют в группы - домены, получившие название LA (Location Area - области расположения). Каждой LA соответствует свой код LAI(Location Area Identity). Один VLR может контролировать несколько LA. И именно LA и помещается в VLR для задания местоположения мобильного абонента. В случае необходимости именно в соответствующей LA (а не в отдельной соте, заметьте) будет произведен поиск абонента. При перемещении абонента из одной соты в другую в пределах одной LA перерегистрация и изменение записей в VLR/HLR не производится, но стоит ему (абоненту) попасть на территорию другой LA, как начнется взаимодействие телефона с сетью. Каждому пользователю, наверное, не раз приходилось слышать периодические помехи (типа хрюк-хрюк---хрюк-хрюк---хрюк-хрюк :-) ) в музыкальной системе своего автомобиля от находящегося в режиме ожидания телефона - зачастую это является следствием проводимой перерегистрации при пересечении границ LA. При смене LA код старой области стирается из VLR и заменяется новым LAI, если же следующий LA контролируется другим VLR, то произойдет смена VLR и обновление записи в HLR.

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

Теперь рассмотрим очень красивый алгоритм так называемого handover`ра (такое название получила смена используемого канала в процессе соединения). Во время разговора по мобильному телефону вследствие ряда причин (удаление "трубки" от базовой станции, многолучевая интерференция, перемещение абонента в зону так называемой тени и т. п.) мощность (и качество) сигнала может ухудшиться. В этом случае произойдет переключение на канал (может быть, другой BTS) с лучшим качеством сигнала без прерывания текущего соединения (добавлю - ни сам абонент, ни его собеседник, как правило, не замечают произошедшего handover`а). Handover`ы принято разделять на четыре типа:

·  смена каналов в пределах одной базовой станции

·  смена канала одной базовой станции на канал другой станции, но находящейся под патронажем того же BSC.

·  переключение каналов между базовыми станциями, контролируемыми разными BSC, но одним MSC

·  переключение каналов между базовыми станциями, за которые отвечают не только разные BSC, но и MSC.

В общем случае, проведение handover`а - задача MSC. Но в двух первых случаях, называемых внутренними handover`ами, чтобы снизить нагрузку на коммутатор и служебные линии связи, процесс смены каналов управляется BSC, а MSC лишь информируется о происшедшем.

Во время разговора мобильный телефон постоянно контролирует уровень сигнала от соседних BTS (список каналов (до 16), за которыми необходимо вести наблюдение, задается базовой станцией). На основании этих измерений выбираются шесть лучших кандидатов, данные о которых постоянно (не реже раза в секунду) передаются BSC и MSC для организации возможного переключения. Существуют две основные схемы handover`а:

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

·  "Энергосберегающий режим" (Power budget). При этом мощность передатчика мобильного телефона остается неизменной, а в случае ухудшения качества меняется канал связи (handover).

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

3.4 Маршрутизация вызовов.

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

При поступлении запроса (рис.2) на соединение от проводной телефонной (или другой сотовой) системы на MSC домашней сети (вызов «находит» нужный коммутатор по набранному номеру мобильного абонента MSISDN, который содержит код страны и сети).

Рис.2 Взаимодействие основных блоков сети при поступлении входящего вызова.

MSC пересылает в HLR номер (MSISDN) абонента. HLR, в свою очередь, обращается с запросом к VLR гостевой сети, в которой находится абонент. VLR выделяет один из имеющихся в ее распоряжении MSRN (Mobile Station Roaming Number – номер «блуждающей» мобильной станции). Идеология назначения MSRN очень напоминает динамическое присвоение адресов IP при коммутируемом доступе в Интернет через модем. HLR домашней сети получает от VLR присвоенный абоненту MSRN и, сопроводив его IMSI пользователя, передает коммутатору домашней сети. Заключительной стадией установления соединения является направление вызова, сопровождаемого IMSI и MSRN, коммутатору гостевой сети, который формирует специальный сигнал, передаваемый по PAGCH (PAGer Channel – канал вызова) по всей LA, где находится абонент.

Заметим, что BSC обычно соединяются друг с другом и с MSC с помощью обычных проводных, чаще оптоволоконных соединений, использующих протокол IP (Internet Protocol), и коммутацией в такой сети управляют специальные устройства – маршрутизаторы. В них уже заложены протоколы и алгоритмы выбора маршрута, поэтому пытаться продемонстрировать прелесть аутороутинга на их примере бессмысленно – врядли когда-то это будет реализовано.

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

В связи с большим количеством пользователей сети, например в Москве и Области около тысячи BTS более чем на 10 миллионов пользователей, имеет смысл говорить о средней загрузке каждой линии связи в сети, и использовать ее как текущую загрузку канала при асчетах. Мы будем рассматривать наиболее вероятный случай, в котором может потребоваться решение задачи аутороутинга – подключение новой BTS. В этом случае потребуется прокладка статических маршрутов ко всем точкам сети, с использованием данных о текущих загрузках каналов, их характеристиках и топологии сети. Так как цель данной статьи продемонстрировать возможности подхода, а не предоставить готовое «боевое» решение, сделаем некоторое упрощение: будем проводить маршрутизацию только внутри сети РРЛ, не используя оптоволоконных связей провайдера. Итак, задача поставлена, время перейти к рассмотрению алгоритмов ее решения.

4. Задача маршрутизации.

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

Классическая задача аутороутинга:

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

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

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

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

Задача аутороутинга с использованием многокритериального подхода:

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

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

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

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

Поставим задачу следующим образом:

Дан граф, аналогичный тому, который используется в классической задаче, на каждом из ребер которого задано несколько параметров, представляющих интересующие нас критерии. Для каждого пути будем на основе каждого параметра, или нескольких из них будем вычислять вектор значений критериев, «векторную оценку», для каждого из которых задан коэффициент его важности (например по параметрам соединения «пропускная способность», «текущая загрузка» и «задержка», а также зная о сервисе требуемую пропускную способность вычислим минимальную по всем соединениям обрабатываемого пути оставшуюся доступную пропускную способность суммарную задержку, задержке припишем важность 5, пропускной способности – 1, сделав таким образом задержку в пять раз более важным параметром).

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

4.2 Модель сети и выбор параметров сети для последующего анализа.

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

Сеть состоит из 726 BTS и 670 соединений РРЛ. Среднее количество соединений в рассчете на одну BTS приблизительно равно 2 (1.9035), максимальное – 9. К сожалению, из-за больших размеров сети, наглядно изобразить ее можно только с помощью специальных утилит. В приложении, прилагающемся к данной статье такая возможность реализована.

Очевидно, что в сетях таких масштабов ни о каком ручном выборе маршрутов речи быть не может, однако при автоматическом выборе лучшего маршрута есть опасность пренебречь одним из параметров из-за слишком хорошего значения другого. Поэтому, к примеру, в модуле автоматической маршрутизации, включенном в OSS(Operating Support System) компании Netcracker, при использовании классического алгоритма маршрутизации все равно выбирается не один, а несколько лучших путей, чтобы инженер сам мог исключить неподходящие варианты.

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

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

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

Голосовой трафик имеет ряд особенностей в отличие от статических данных или видео. Существуют несколько параметров, которые крайне необходимо учитывать при построении пути.

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

Второй важный параметр – это потери на пути следования трафика. Здесь наоборот существенный вклад дает расстояние между соседними базовыми станциями и обуславливается потерями в окружающей среде. Для УКВ сигнала длина волны порядка сантиметра. Это меньше, чем на порядок больше капельки дождя, любая птица может помешать связи, чувствительной оказывается дифракция на неровностях рельефа местности, не говоря уже о непостоянной плотности воздуха. Все это – так называемые замирания сигнала, с которыми ничего не поделаешь, но врядли провайдер будет мерить, да, именно мерить такие мелочи. Поэтому так как данных о самой сети немного, и чтобы излишне не усложнять задачу, для оценки потерь было выбрано расстояние между антеннами РРЛ. Он подсчитывается как 1/(max( d1 / 5000.0, 1.0 )* max( d2 / 5000.0, 1.0 )* max( d3 / 5000.0, 1.0 )*…* max( dn / 5000.0, по всем ребрам). 5000 метров – условное расстояние, на котором потерями решено пренебречь

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

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

Многокритериальный анализ – это математический аппарат для сравнения нескольких возможных вариантов при принятии некоторого решения на предмет предпочтительности сразу по нескольким параметрам. Традиционным методом решения этой задачи является использование некоторой весовой функции от аргументов - некоторым образом полученных числовых значений параметров. Недостатками такого подхода являются:

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

2.  Потенциальная опасность практически полного пренебрежения значением одного из параметров в случае слишком большого числового значения другого

Рассмотрим, к примеру, формулу для подсчета метрики протокола IGRP (Interior Gateway Routing Protocol)

Где:

d – коэффициент, характеризующий временные задержки при движении пути по маршруту пакетов,

b – ширина пропускания канала в самом узком сегменте пути,

o – коэффициент, характеризующий загрузку канала

r – коэффициент надежности маршрута (пропорционален доле теряемых пакетов)

K1, K2 – константы

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

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

Математическую модель для анализа многокритериальных задач принятия решения можно представить следующим набором:

< S, K1, …, Km, X, P, I > (10)

где

S – множество вариантов решений

K1, …, Km – критерии

X – множество векторных оценок

P, I – соотношения предпочтения и безразличия, соответственно.

Поясним содержание модели.

Каждый вариант s из множества всех имеющихся (заданных) вариантов S характеризуется значениями m≥2 критериев Ki. Под критерием Ki понимается функция, определенная на S и принимающая значения из множества Xi, называемого шкалой (а также множеством оценок, градаций, значений критерия). По существу, критерий Ki служит для измерения интенсивности соответствующего признака, и оценка Ki(s) есть результат измерения для решения s.

Ki: S Xi.

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

Таким образом, каждый вариант s характеризуется значениями Ki(s) всех критериев, образующих векторную оценку этого варианта x(s) = (K1(s), …, Km(s)). Поэтому сравнение вариантов по предпочтительности сводится к сопоставлению их векторных оценок. Соответственно, множество всех векторных оценок есть декартово произведение

X = X1 … Xm.

По своему характеру критерии делятся на количественные и качественные. Критерии называются количественными, когда его значения (оценки), в контексте конкретной задачи конечно, имеет смысл сравнивать, указывая, «на сколько» или «во сколько» раз одна оценка больше другой. Примером количественного критерия является вес объекта. Если объект a имеет вес K(a), а объект b имеет вес K(b), то a тяжелее b в K(a)/K(b) раз. Если изменить масштаб (единицу) измерения веса, то в новых единицах веса объектов будут равными соответственно kK(a) и kK(b) (где k>0), но соотношение kK(a)/kK(b) останется равным прежней величине K(a)/K(b). Понятно, однако, что всякое другое преобразование функции K (не являющееся умножением заданную константу) может привести к изменению исходного соотношения. Например, если K(a) ≠ K(b), то K2(a)/K2(b) ≠ K(a)/K(b).

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

В вышеизложенном примере Ф={φ(x)= kx, k>0}. Шкала такого типа называет шкалой отношений, так как сохраняется величина отношения.

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

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

Рассмотрим еще несколько широко применяющихся типов шкал.

Распространённым случаем являются измерения в шкале типа

Фи = {φ(x)= kx+l, k>0}.

Такая шкала называется шкалой интервалов. Это название объясняется свойством сохранения отношения интервалов:

Шкала считается тем более совершенной, чем уже множество Ф допустимых преобразований. Самой совершенной является абсолютная шкала, для которой единственным допустимым преобразованием является тождественное преобразование: Фa={φ(x) x}. Примерами критериев с абсолютной шкалой являются количество пользователей, количество устройств сети и т. п. Абсолютные шкалы могут получить критерии, образованные путем соответствующих преобразований исходных критериев, имевших менее совершенные шкалы. Например, если K имеет шкалу отношений, то у нормированного критерий K/Kº, где Kº - некоторое “эталонное” значение K, шкала оказывается абсолютной.

Критерии, имеющие шкалу, не менее совершенную, чем шкала интервалов, относятся к количественным.

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

Более совершенной, чем номинальная, является порядковая шкала, для которой множество Ф состоит из всех монотонно возрастающих функций. Оценки, полученные в порядковой шкале, имеют смысл сравнивать только по отношению “больше-меньше”: оно сохраняется при монотонных преобразованиях. Длины интервалов между оценками сравнивать бессмысленно.

Критерий K с порядковой шкалой естественным образом формируется на основе ранжирования объектов: под K(a) можно понимать ранг объекта a. Понятно, что если ранг объекта a есть 4, а объекта b – 2, то это вовсе не значит, что объект b в два раза менее предпочтителен, чем объект a: вопрос о количественном соотношении ранговых оценок является бессмысленным. Эти оценки служат только для указания упорядоченности объектов. Поэтому для задания упорядоченности объектов можно вместо K использовать с тем же успехом функцию (критерий) φ(K), где φ – любая монотонно возрастающая функция. Примером критерия с порядковой шкалой может служить место объекта рассмотрения в некотором рейтинге.

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

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

a)  Соответствие. Набор критериев должен соответствовать смыслу (существу) задачи.

b)  Полнота. Набор из m критериев считается полным, если каждый исход ясно и четко характеризуется совокупностью соответствующих значений критериев. Введение дополнительных критериев в полный набор не должен приводить к изменению решения задачи.

c)  Минимальность. Набор должен содержать как можно меньшее число критериев. Следовательно, различные критерии не должны характеризовать одно и тоже свойство исходов.

d)  Операциональность. Каждый критерий должен иметь понятную для принимающего решения формулировку, характеризовать вполне определенное свойство исходов.

e)  Измеримость. Каждый критерий должен допускать получение оценки (количественной или хотя бы качественной) интенсивности характеризуемого им свойства.

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

Функцией ценности (полезности) vX называется функция XRe, обладающая следующим свойством: для любых двух векторных оценок y, z

vX(y) > vX(z) y предпочтительнее, чем z,

vX(y) = vX(z) y и z одинаковы по предпочтительности.

Другим способом моделирования предпочтения служат следующие бинарные отношения:

§  Отношение (строгого) предпочтения P: x’Px” означает, что векторная оценка x’ предпочтительнее (лучше), чем x”;

§  Отношение безразличия I: x’Ix” означает, что x’ и x” одинаковы по предпочтению;

§  Отношение нестрогого предпочтения R: x’Rx” означает, что векторная оценка x’ не менее предпочтительна, чем x”.

Введенные отношения должны обладать следующими свойствами:

§  P иррефлексивно (т. е. yPy не выполняется) и ассиметрично (если верно yPz, то zPy не выполняется);

§  I рефлексивно (т. е. yIy выполняется) и симметрично (если верно yIz, то справедливо и zIy);

§  R рефлексивно;

§  P и I не пересекаются (не может одновременно быть yPz и yIz).

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

Лицом, принимающей решение, является инженер телекоммуникационных сетей.

Множеством вариантов решений S служат всевозможные пути в сети между двумя точками, для которых строится маршрут. Пути должны удовлетворять ограничениям (7) – (8).

Каждый вариант будем характеризовать тремя критериями:

·  K1 – минимальная неиспользованная пропускная (11)

способность по всем ребрам пути, остающаяся после его резервирования

·  K2 – коэффициент, отражающий приблизительную потерю (12)

пакетов на данном пути

·  K3 – «количество хопов». (13)

Шкалы Xi, i = 1, 2, 3 для каждого критерия различны:

Множество значений критерия K1 принадлежат [0, +∞),

Множество значений критерия K2 принадлежат отрезку [0, 1]

Множество значений критерия K3 принадлежат [0, +∞).

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

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

Большинство известных методов предусматривает использование в той или иной форме информации о важности критериев. Одним из наиболее известных методов такого рода является метод обобщенного критерия, который состоит в следующем. Вначале все исходные критерии Ki приводят к сопоставимому безразмерному виду (“нормализуют”). Для этого можно использовать, например, следующие преобразования: , , где - некоторые “эталонные” (напр., максимально возможные и т. п.), а - минимально допустимые значения критериев Ki. Далее все критерии ”сворачивают” в одну функцию – обобщенный критерий Ф(α1, , …, αm, ), учитывая их относительную важность при помощи специальных положительных чисел αi, называемых коэффициентами важности. Обычно требуют еще, чтобы . В итоге исходная многокритериальная задача сводится к обычной задаче оптимизации по одному критерию Ф.

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

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

В связи с этим для решения задачи маршрутизации был выбран метод количественной важности критериев, в основе которого лежат точные определения понятий типа “Критерий K1 и K2 равноценны”, “Критерии K1 и K2 (в совокупности) важнее, чем критерий K3” и т. п.

4.3.1 Метод количественных оценок важности критериев

Критерии K1, …, Km называются однородными, если они имеют общую шкалу X1 = … = Xm. Тогда, если x – векторная оценка, то вектор, полученный из x любой перестановкой ее координат, также оказывается векторной оценкой (т. е. принадлежит X).

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

Рассмотрим, что же считать важностью критериев.

Обозначим через xij векторную оценку, полученную из x=(x1, x2, x3) перестановкой её компонент xi и xj. Например, если x=(3, 0.2, 0.1), то x13=(0.1, 0.2, 3), тоесть попробуем поменять местами сами значения оценок, соответствующих критериям i и j.

Определение 1. Утверждение “Критерии Ki и Kj равноценны” (обозначается Ki ~ Kj) означает, что каждые две векторные оценки x и xij одинаково предпочтительны: xIxij.

Определение 2. Утверждение “Критерии Ki предпочтительнее критерия Kj” (обозначается Ki Kj) означает, что векторная оценка x, у которой xi>xj, предпочтительнее, чем xij: xPxij.

Важность критерия определяется степенью влияния изменения его значения на общее “качество” исходов.

Пусть информация о важности состоит в том, что все критерии равноважны. Порождаемые такой информацией отношения P и I можно задать следующим образом. Обозначим через z векторную оценку, полученную из x упорядочением ее компонент по убыванию. Например, если x=(3, 4, 2), то z=(2, 3, 4). Решающее правило, задающее отношения P и I:

x’Ix’’ при z’=z”; (14)

x’Px” при zi’≥zi”, i=1,…, m. z’≠z”.

Т. е. для сравнения по предпочтительности векторных оценок x’ и x” следует покомпонентно сравнивать по величине соответствующие им векторы z’ и z”.

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

Рассмотрим дробную модель (аналог модели (10)) с “разделенными” на “равные доли” критериями.

Пусть N=(n1, n2, …, nm) – вектор, все компоненты которого – натуральные числа, и n = n1 + n2 + …+ nm. Под N-дробной моделью (сокращенно N-моделью) понимается модель

, (15)

которая получена заменой каждого из исходных критериев Ki набором ni однородных (попарно) равноважных критериев , …, , а отношения PN и IN определяются на множестве векторных оценок YN = X0n.

Поскольку информация о важности на практике получается экспертным путем, то можно утверждать, что в сообщениях типа “Один критерий важнее другого в h раз” число h > 1 будет целым или дробным, т. е. h = n’ / n”, где n’ и n” – натуральные числа.

Определение 3. Утверждение “Критерий Ki в h раз важнее критерия Kj” (обозначается ) означает, что во всякой N-модели, для которой ni/nj = h, каждый из ni критериев равноважен любому из nj критериев .

Если 0<h<1, то фактически критерий Kj в 1/h>1 раз важнее критерия Ki, а при h=1 критерии равноважны (т. е. или ).

Пусть Ω – информация о количественной важности критериев, т. е. набор сообщений ω, имеющих смысл согласно определению 3.

Определение 4. Положительные числа λi, удовлетворяющие системе

λi = hλj, если (16)

называются (количественным) коэффициентами важности порождаемые информацией Ω.

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

Все n критериев модели (15), согласованной с Ω, попарно равноважны, и поэтому можно построить отношения PNΩ и INΩ на YN, используя решающее правило (14). По этим отношениям на YN строятся отношения PΩ и IΩ на X, т. е. в исходной модели. Каждой векторной оценке соответствует векторная оценка , первые n1 компонент которой равны x1, следующие n2 компонент – x2 и т. д.

Получаем,

(17)

(18)

Используя коэффициенты важности, можно указать решающее правило, задающее PΩ и IΩ. Примем, что X0 содержит всего q градаций: X0 = {1, …, q}. Для обозначим через Λk(x) сумму коэффициентов важности λi, соответствующих компонентам xi, не меньшим, чем k:

(19)

Решающее правило выглядит так: если справедливы q-1 нестрогих неравенств

Λk(x’) ≥ Λk(x”), k = 2, …, q, (20)

то при наличии среди них хотя бы одного строгого, верно , а при отсутствии таковых верно - .

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

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

4.3.2 Метод интервальных оценок важности критериев

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

Метод интервальных оценок также предполагает однородность всех критериев.

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

(21)

где все li > 0, ri < 1. Чтобы информация (21) была внутренне непротиворечивой, должны выполняться условия: l1 + … + lm ≤ 1.

Понятно, что если для векторных оценок x и y при любом векторе коэффициентов важности λ = (λ1, …, λm), компоненты которого удовлетворяют (21), справедливо xR(λ)y, то следует считать, что векторная оценка x не менее предпочтительна, чем y. Указанное решающее правило, задающее отношение R(λ[ ]), можно представить следующим образом.

Неравенства (20) перепишем в виде:

ak1λ1 + … + akmλm ≥ 0, k = 2, …, m, (22)

где каждый коэффициент aki есть -1, 0 или 1.

Условие выполнения (21) при любых λi, удовлетворяющих условию (21), можно записать так:

µk ≥ 0, k=2, …, m,

где µk – наименьшее значение левой части соответствующего неравенства из (22).

Задача отыскания µk есть задача минимизации левой части (22) при ограничениях (20) и . Таким образом задача проверки выполнения xR(λ[ ])y свелась к ряду задач линейного программирования (которые, в свою очередь, можно свести к одной задаче). Однако, учитывая простую структуру (22) и ограничений, можно указать более простой путь.

Неравенства (22) можно разбить на три группы:

·  заведомо (при любых допустимых значениях λi) верные: все m коэффициентов aki неотрицательны;

·  заведомо неверные: нет положительных aki и есть хотя бы один отрицательный;

·  сомнительные: есть и положительные, и отрицательные aki.

Перепишем ограничения (21) следующим образом:

(23)

Где Суммируя эти неравенства, получим

(24)

где

(25)

Теперь значения λi можно представить в виде:

(26)

и переписать (21) так:

(27)

Величина µk для сомнительного неравенства вычисляется следующим образом. Вначале поочередно (в любом порядке) назначаем максимально возможные (согласно (26)) значения δi с такими номерами i, при которых aki=-1, до тех пор, пока сумма назначенных δi не достигнет Δ. Если все такие номера исчерпаны, а “запас” Δ не полностью истрачен, то поочередно (в любом порядке) назначаем максимально возможные значения δi для всех номеров i, при которых aki = 0, до тех пор, пока сумма всех назначенных δi не достигнет Δ. Если и после этого некоторый “запас” все еще остается, назначаем поочередно (в любом порядке) максимально возможные значения δi для оставшихся номеров i. На любом этапе назначения величин δi после исчерпания “запаса” Δ все оставшиеся δi полагаются равными нулю.

Получили следующую формулировку решающего правила: xR(λ[])y выполняется тогда и только тогда, когда среди q-1 неравенств (22) нет заведомо неверных и для всех сомнительных неравенств вычисленные указанным выше способом величины µk ≥ 0.

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

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

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

5. Обзор алгоритмов решения задачи многокритериального аутороутинга.

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

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

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

Рассмотрим подробнее обоснование алгоритма Дейкстры:

Множеством S назовем множество вершин, до которых известны кратчайшие пути от источника, w – следующая вершина, до которой мы хотим найти кратчайший путь, x – вершина, через которую этот путь мог бы проходить. Алгоритм предлагает нам выбрать из вершин, не входящих во множество S ту, до которой путь через это множество существует и является кратчайшим. Утверждается, что он является кратчайшим путем во до w во всем графе. Потому что если бы он не был кратчайшим, он должен бы был пройти через вершины, не входящие в S, но, так как все ребра положительны, на этом шаге следовало бы выбрать не w, а X – первую вершину в этом «обходном» пути, не принадлежащую S, так как до нее расстояние меньше. Таким образом, в классическом случае для доказательства справедливости алгоритма Дейкстры работает метод математической индукции. Следуя этому алгоритму и сохраняя для каждой вершины графы предыдущую вершину, через которую мы в нее пришли, можно найти путь до интересующей нас вершины.

В нашем же случае независимых критерия два, и если не повезет, может не выполниться даже первое утверждение – база индукции: пусть у исходной точки соседними являются две вершины, при этом являющиеся соседями друг другу. В случае выполнения строгого неравенства при выборе между этими двумя точками, нет сомнения, нужно выбрать ту, которая эффективнее, для нее кратчайший путь можно считать известным, так как с увеличением количества ребер в пути, он становится не лучше (т. е. x1Rx2 если путь x2 получен путем добавления ребер к x1), а в используемом нами методе количественных оценок отношения P и R транзитивны. По другому обстоит дело с I, в которое приходится включать понятие несравнимости путей. Если два пути x1 и x2 несравнимы, то мы ничего не можем сказать о том, какие отношения будут между путями, состоящими в отношениях R и P с путем x1 и аналогичными путями для x2. Например, в случае, указанном на рисунке предположим, что на ребре src-p1 хороший показатель пропускной способности, но плохой показатель задержки, а на ребре src-p2 – наоборот. Согласно алгоритму мы должны выбрать одну из этих точек как точку, до которой все множество кратчайших путей известно, пусть это будет p1. Но теперь предположим, что у ребра p1-p2 просто отличные показатели и задержки и пропускной способности, из-за чего получается, что пути src-p1 и src-p2-p1 опять же получаются несравнимыми и должны оба быть рассмотрены как пути до p1, а окончательный выбор – предоставлен инженеру.

Аналогично рассмотрим возможность применения алгоритма Беллмана-Форда:

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

Авторы полагают, что читателю известен принцип работы алгоритма, поэтому ограничимся описанием того, почему в нашем случае он не работает. Дело, как и в предыдущем случае, в отношении несравнимости путей. Предположим путь src-p2-p3 в процессе анализа путей до p3 на каком-либо шаге был отброшен, так как src-p1-p3 оказался доминируемым из-за того, что пропускная способность этих путей одинакова, а потеря пакетов на пути через p1 оказалась меньше. Однако оказалось, что дуга p3-p5-dst характеризуется маленькой пропускной способностью, но практически отсутствуют потери, и p3-p4-dst – наоборот: высокая потеря при высокой пропускной способности. Таким образом нетрудно убедиться, что пути src-p2-p3-p4-dst и src-p1-p3-p5-dst оказались несравнимы. Вопрос о том, будет ли путь src-p1-p3-p4-dst, где задержка также велика остается открытым, так как здесь все зависит от конкретных значений параметров.

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

Как бы противно ни звучало название, на исследуемой модели алгоритм действительно работает и работает относительно эффективно. Время вычисления всех вариантов путей составляет в среднем 10-15 секунд, а выбора из них недоминируемых – порядка двух минут при шкале 10000 и порядка 5 секунд при шкале 100. Результаты приведены для обычного персонального компьютера, причем не была произведена оптимизация с точки зрения производительности и реализация поддержки параллельных вычислений. Вопрос как оптимизировать алгоритм полного перебора не заслуживает большого внимания, так как алгоритм предусматривает переход на вершину и попытку перейти на каждую из соседних. Сложности могут возникнуть только при технической реализации пула параллельных потоков. Но это задача параллельного программирования, и не относится к данной статье.

Вопрос о том, как распараллелить нахождение недоминируемых путей в большом массиве более интересен. Не будем подробно на этом останавливаться, но пару слов сказать стоит. Во-первых для каждого пути требуется вычислить значения критериев и составить последовательность сумм (19). Для каждого пути это независимый процесс, поэтому масштабируемость этого процесса практически единица. Что же касается сравнения этих сумм, требуется сравнивать варианты, которые еще не признаны доминируемыми каждый с каждым. Одна из возможных реализаций – сделать дополнительный поток, который будет «выдавать» остальным потокам варианты для сравнения, однако такой подход эффективен только для большого числа обрабатывающих потоков.

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

6. Анализ модели

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

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

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

·  Остающаяся пропускная способность: 1

·  Расстояние: 5

·  Количество вершин: 4

Также была выбрана шкала от 0 до 100.

Замечательно, что даже при шкале 100, что, в общем, дает небольшой потенциал для дискретизации, в среднем между двумя случайно выбираемыми вершинами применение многокритериального подхода дает в среднем три вершины (точно – 2.86). Максимальное же число путей – 12.

Среднее время вычислений составило 25 cекунд, однако максимум равен десяти минутам! Однако это единичный случай, дисперсия времени вычисления составляет около 10 секунд (9.85 сек)

Приведем несколько примеров работы алгоритма (с иллюстрациями):

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

Оптимальные пути между точками 72 и 80
№ пути	Bandwidth	Distance	Number of Nodes	Points
Найденные с помощью классического алгоритма:
1	47	29	33	7 -5 -6
Найденные с помощью многокритериального подхода:
1	47	29	33	7 -5 -6
2	6	100	30	7 -2 -1
3	21	95	30	7 -2 -1
4	47	34	28	7 -6 -5 -6

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

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

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

Оптимальные пути между точками 252 и 175
№ пути	Bandwidth	Distance	Number of Nodes	Points
Найденные с помощью классического алгоритма:
1	1	100	50	-
Найденные с помощью многокритериального подхода:
1	1	100	50	-
2	6	29	22	-6 -5 -8 -2 -
3	21	28	22	-6 -5 -8 -2 -

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

7. Описание приложения

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

7.1 Модель

Модель данных включает в себя следующие классы:

1.  Initializer (Interface) – интерфейс класса, описывающий методы загрузки модели из какой-либо базы данных и предоставляющий доступ к вершинам графа

метод загружает модель из базы

public abstract void loadModel() throws IOException;

метод находит объект EquipmentPoint по уникальному имени

public abstract EquipmentPoint getPointByName(String name);

метод возвращает список всех вершин. Список можно использовать только для чтения

public abstract Collection<EquipmentPoint> getPoints();

Методы, возвращающие параметры сети для рисования, в пикселах.

public abstract int getNetworkWidth();

public abstract int getNetworkHeight();

public abstract int getNetworkBottom();

public abstract int getNetworkLeft();

public abstract int getNetworkTop();

public abstract int getNetworkRight();

метод возвращает «псевдоним» точки. В текущей реализации это P_##, где ## - натуральное число от 1 до общего количества точек

public abstract String getAlias(EquipmentPoint point);

2.  netmodel. LinkManager – класс, реализующий базовые операции с ребрами графа и предоставляющий доступ к ребрам, загруженным с помощью NetInitializer

метод вызывается для добавления ребра в модель. Он так же добавляет информацию о соседней вершине вершинам a и z

public Link addLink(EquipmentPoint a, EquipmentPoint z, double loadingFactor, double errorRate)

метод возвращает Link, описывающий ребро между двумя вершинами или null если такового нет.

public Link getLinkByNodes(EquipmentPoint a, EquipmentPoint z)

метод возвращает

public Link getLinkByNodes(String a, String z)

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

public static LinkManager getInstance()

3.  InitializerImpl – класс, реализующий интерфейс NetInitializer для загрузки данных из базы в формате csv (comma separated values)

4.  netmodel. EquipmentPoint – класс, реализующий представление вершины графа и хранящий ее имя и информацию о соседних вершинах

5.  netmodel. Link – класс, реализующий представление ребра графа и хранящий информацию о вершинах, между которыми это ребро проходит и параметрах моделируемого соединения, таких как пропускная способность, текущая закрузка и длина соединения.

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

7.2 Представление

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

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

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

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

Описание реализации:

1.  ModelViewer – класс, реализующий создание графического интерфейса и открытие окна приложения.

2.  NetViewer – оболочка для объекта класса JGraph – JComponent, непосредственно реализующего отображение графа, реализующяя базовые методы инициализации графа, загрузки модели и интерфейс, используемый ModelViewer

7.2 Контроллер

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

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

Описание реализации:

1.  compengine. PathComparator – класс, реализующий непосредственно сравнение двух путей на предмет предпочтительности, на основе ServiceType, используемого в системе по умолчанию

По сути, в нем и заключается вся суть многокритериального подхода.

2.  compengine. PathCriterionValueCalculator – интерфейс, описывающий методы, необходимые для вычисления значения критерия. Имеет 3 наследника:

BandwidthCalculator

DistanceCalculator

NumberOfNodesCalculator

3.  compEngine. Router – абстрактный класс, описывающий методы, необходимые для реализации многокритериального роутера

Методы:

Метод, возвращающий коллекцию найденных путей

public abstract Collection<Path> findRoutes(EquipmentPoint src, EquipmentPoint dst) throws Exception;

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

protected void removeDominated (List<Path> pathes)

4.  compengine. StupidRouter – неабстрактная реализация класса Router. Название получилось по историческим причинам, до доказательства того факта, что кроме полного перебора всех возможных путей вариантов действий нет J

5.  compengine. RowHolder – класс, реализующий последовательность сумм, описанную в главе 4.3

6.  classicengine. LinkWeightCalculator – класс, реализующий вычисление веса ребра

7.  classicengine. DejkstraRouter – класс, реализующий нахождение пути по алгоритму Дейкстры на основе весов, вычисленных LinkWeightCalculator

Заключение

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

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

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

Итак, из ста случайно выбранных для анализа пар точек алгоритм Дейкстры «угадал» все 100 недоминируемых вариантов, вычисленных с помощью многокритериального подхода. Но в пяти из этих ста случаев значение параметра загрузки было меньше пяти(тоесть оставалось меньше 500 kbps свободной пропускной способности), что при наличии «взрывного» пакетного трафика может привести к перегрузке сети. Как оказалось, во всех пяти случаях существовали обходные пути, состоящие из в полтора-два раза большего числа ребер графа, но параметр загрузки канала имел значения больше 25, тоесть оставалось около 4 mbps свободной пропускной способности.

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

Источники:

Андрей Экономов - Сети GSM. Взгляд изнутри. (11 ноября 2000 г.)

Heikki Kaaranen, Ari Ahtiainen - UMTS Networks. Architecture, Mobility and Services

Альфред В Ахо, Джеффри Д Ульман - Структуры данных и алгоритмы

ru. wikipedia. org/wiki/Математическая индукция

//Научно-техническая информация, сер. 2, Информационные процессы и системы, N5, 1998, с. 171-242