автореферат диссертации по радиотехнике и связи, 05.12.13, диссертация на тему:Разработка алгоритмов размещения базовых станций на основе методов оптимизации для сетей беспроводного доступа

Ермолаев Сергей Юрьевич

На правах рукописи

РАЗРАБОТКА АЛГОРИТМОВ РАЗМЕЩЕНИЯ БАЗОВЫХ СТАНЦИЙ НА ОСНОВЕ МЕТОДОВ ОПТИМИЗАЦИИ ДЛЯ СЕТЕЙ БЕСПРОВОДНОГО ДОСТУПА

Специальность 05.12.13 -«Системы, сети и устройства телекоммуникаций»

Автореферат диссертации на соискание учёной степени кандидата технических наук

Самара-2010

- 9 ДЕК 2010

004616646

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования «Поволжский Государственный Университет Телекоммуникаций и Информатики (ГОУВПО ПГУТИ)

Ведущая организация: Институт проблем управления сложными системами РАН РФ (г. Самара)

Защита состоится «24» декабря 2010 г. в 13-00 часов на заседании диссертационного совета Д219.003.02 при Поволжском государственном университете телекоммуникаций и информатики по адресу: 443010 г. Самара, ул. Льва Толстого, 23.

С диссертацией можно ознакомиться в библиотеке ГОУВПО ПГУТИ. Автореферат разослан «23» ноября 2010 г.

Научный руководитель:

доктор технических наук, профессор Карташевский В.Г.

Официальные оппоненты: доктор технических наук,

профессор Кораблин М.А.

доктор технических наук, профессор Орлов С.П.

Учёный секретарь

диссертационного совета Д219.003.02, доктор технических наук, профессор

Мишин Д.В.

Обшая характеристика работы

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

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

Среди публикаций, посвященных изучению методологии создания сетей IEEE 802.16-2004 и решению задач размещения базовых станций, следует отметить исследования Вишневского В.М., Ляхова А.И., Портного С.Л., Шахно-вича И.В., Широкова В. Также существуют исследования, ориентированные на решение общих задач размещения, среди которых можно выделить работы Кочетова Ю.А., Пащенко М.Г., Береснева В.Л. Среди зарубежных ученых стоит отметить фамилии Murphy S., Amaldi Е., Capone A., Sridharan R., Klincewicz J.G., Barcelo J., Beasley J.E.

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

Основные задачи исследования.

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

- анализ существующих методов решения NP-трудных задач размещения;

- разработка алгоритмов оптимального размещения базовых станций и подключения к ним абонентов;

- создание программного обеспечения для решения задач размещения любой размерности и конфигурации;

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

Методы исследования. Основные теоретические и экспериментальные исследования диссертационной работы выполнены с применением методов комбинаторной оптимизации, теории графов, теории алгоритмов, и о&ьектно-ориентированного программирования.

Научная новизна работы.

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

- предложен алгоритм размещения базовых станций на основе генетического подхода;

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

Основные положения, выносимые на защиту.

- модифицированная постановка задачи размещения базовых станций;

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

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

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

Практическая ценность и реализация результатов работы.

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

Полученные результаты и алгоритмы могут быть использованы научно-исследовательскими, проектными организациями и телекоммуникационными компаниями при проектировании и внедрении сетей стандарта \ViMAX.

Основные теоретические и практические результаты, полученные в диссертации, использованы в ООО «Саха-Белком» и внедрены в учебный процесс ГОУВПО ПГУТИ, что подтверждено соответствующими актами.

Работа выполнена при поддержке гранта 2007 года для студентов, аспирантов и молодых ученых от Министерства образования и науки Самарской области (шифр гранта 302ГЭ. 7К).

Апробация работы. Основное содержание работы докладывалось и обсуждалось на VIII Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (Уфа, 2007г.), на IX - XII Международной конференции «Цифровая обработка сигналов и ее примене-

ние» (Москва, 2007 - 2010гг.), IX Международной научно-технической конференции «Кибернетика и высокие технологии» (Воронеж, 2008г.).

Публикации. По теме диссертации опубликовано 16 работ, в том числе 2 работы из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных исследований, 1 статья в журнале «Telecommunication Sciences» (Украина), 6 тезисов, 6 докладов в трудах международных научных конференций, а также 1 свидетельство о регистрации программы для ЭВМ.

Структура и объём работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Основная часть работы содержит 163 страницы машинописного текста, 39 рисунков, 29 таблиц. Список литературы включает 111 наименований.

Краткое содержание работы

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

В первой главе рассмотрены основные технологии беспроводной широкополосной связи четвертого поколения - LTE, WiMAX, основной акцент сделан на описание стандарта IEEE 802.16-2004, рассмотрена методология создания сетей беспроводного доступа, сформулирована модифицированная постановка задачи, использующая канальную модель SUI.

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

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

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

ф= £ »'ыЛпУы + 1>„*ши + XZ—->min (1)

k,m,n т,п k т ^^

где, 1ГЫп ;

И^Ьт > 0. еслн расстояние г <ЛХ

№ьпп > 0, если расстояние Щ<г<,й2 - стоимость подьслючения ^ктп ~ 0» если расстояние г > Я2

к -го абонента к станции п -го типа;

если станция л-го типа размещена на т-ом месте.

>

иначе

1, если к-й абонент подключен к станции, размещенной на т-ом месте.

Л1,е

К'

[0, иначе

стоимость станции п -го типа; g^cm - коэффициент, учитывающий условия

распространения сигнала в радиоканале между к-м абонентом и базовой станцией, размещенной на т -м месте кандидате; т - число мест кандидатов на расположение базовых станций с известными координатами, т = \,М ; п -количество типов станций, л = 1, N; к - число абонентов с заданными координатами, к = \,К.

При этом имеется следующая система ограничений:

1. На каждом из мест кандидатов должно быть размещено не более одной базовой станции:

Ут (2)

П=1

2. Каждый абонент должен быть обязательно подключен только к одной базовой станции:

м

V* ЕП» = 1 (3)

т=1

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

Ут ^ЪпХтп^ЬкУы (4)

л=1 к=1

где, Ь„ - производительность станции п -го типа, Кбит/с; Ьц — требуемая скорость передачи информации для к -го абонента, Кбит/с.

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

Задача диссертационного исследования относится к классу задач размещения с одним источником при наличии ограничения на емкость (производительность, ресурсы) этого источника и является ИР-трудной. На современном

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

Предложенный генетический алгоритм для решения задачи размещения базовых станций и подключения к ним абонентов является итерационным и разработан на основе стандартного генетического алгоритма. Каждое полное решение задачи, соответствующее определенной конфигурации сети, закодировано в виде хромосом. Хромосома - вектор, представляющий собой закодированное значение, соответствующее определенной конфигурации сети и описывающее размещение базовых станций на местах кандидатах и подключение абонентов к конкретным базовым станциям. Для адаптации генетического подхода к решаемой задаче имеются принципиальные отличия. В алгоритме использовано особое представление хромосом, в котором каждая хромосома является к -мерным вектором целых чисел на множестве {1,м} : целочисленное значение к -й позиции указывает базовую станцию, размещенную на т -м месте кандидате, к которой подключен к -й абонент.

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

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

Ко тек. = ^Ошах (5)

где, Л'0 тек - номер текущего поколения хромосом; МСтах - максимальное число поколений хромосом, задаваемое в начале работы алгоритма. Под поколением понимается конечное множество хромосом, формируемое в процессе работы генетического алгоритма. К популяции хромосом, создаваемой на очередной итерации алгоритма применяется термин «новое поколение» или «поколение потомков». На четвертом этапе на основе турнирной селекции происходит отбор хромосом, которым разрешено участвовать в создании потомков для следующего поколения.

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

Затем определяется хромосома первого потомка. Если Father\[k] = Fatherly, то Sim[fc] = Father\[k], иначе Sun[fc] = 0. Здесь происходит поэлементное сравнение хромосом двух родителей. Если целочисленное значение к -й позиции одинаково у обоих родителей, то оно переписывается в хромосому потомка. В противном случае в хромосому потомка записывается ноль. Далее выбирается родительская хромосома Fatherl, и процедура скрещивания проводится в следующей последовательности:

1. Выбирается случайным образом целое число ве]\,к\ из диапазона чисел, соответствующих количеству абонентов.

2. Переменной Я присваивается значение хромосомы Fatherl, соответствующее значению в -й позиции, т.е. Я = Falher\[0]. Данный процесс предназначен для последующего изменения подключения абонента с одной станции на другую.

3. Для всех к-к элементов в потомке S, для которых = 0, присваивается значение переменной Я, т.е. абонент оказывается подключен к другой станции, номер которой равен Я. Если к -й абонент может быть подключен к станции Я без нарушения ограничения (4) по производительности, то данное подключение считается разрешенным и значение производительности станции Я обновляется.

Если к -й абонент не может быть подключен к станции Я по причине нарушения ограничения (4) или при его расположении вне ее радиуса действия, то переменной <р присваивается значение хромосомы Fatherl, соответствующее значению 0-й позиции, т.е. (р ~ Father2[0] и осуществляется подключение абонента к станции, номер которой равен <р.

В результате описанной процедуры происходит формирование первого потомка, у которого назначение абонентов базовым станциям отлично от назначения в родительских хромосомах. Далее выбирается хромосома Fatherl, и повторяются шаги 1,2, 3 для формирования второго потомка Sun .

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

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

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

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

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

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

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

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

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

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

С целью выполнения ограничения (3) для каждого места кандидата используется специальная структура данных - «список табу», который сохраняет порядок абонентов, подключенных до момента времени t и запрещает в текущем цикле алгоритма подключать их снова. В конце цикла список табу используется для подключения абонентов к базовым станциям, установленным на выбранных местах кандидатах. Для выполнения ограничения (4) с каждым местом кандидатом ассоциируется переменная ßCT/,. В начале каждого цикла

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

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

= —1— (6) d(z,s)

где, d(z,s) - расстояние между z -м местом кандидатом и s -м абонентом.

Алгоритм размещения базовых станций и подключения к ним абонентов на основе метаэвристики муравьиной колонии представлен на рис. 1. Процесс построения решения начинается с фазы инициализации, в течение которой устанавливаются значения параметров настройки алгоритма (количество циклов, коэффициенты а, ß, q0, константы обновления динамических переменных). После фазы инициализации начинается первый цикл алгоритма. Дня каждого z -го места кандидата рассчитываются значения привлекательности всех абонентов на основе псевдослучайного пропорционального правила (7), которое учитывает как степень локальной привлекательности соответствующего абонента и ребра графа, так и его видимость, а также потери при распространении. Понятие «привлекательности» абонента означает, что этот абонент ближе всех расположен к базовой станции, соответственно, потери при распространении и стоимость подключения для такого абонента будут минимальны. Для z -го места кандидата первым окажется подключен тот s -й клиент, для которого рассчитанная по формуле (7) привлекательность максимальна. При этом сначала с помощью генератора случайных чисел определяется случайное число q (выполняется розыгрыш случайного числа q ) и если q < g0 , то применяется формула (7):

[arg max {[^(O + ^Wf ЛФ,«)? + &J если929о

« = j ' (7)

[S иначе

где, гц(0 - динамическая переменная величина, ассоциированная с абонентом; г2ц (/) - динамическая переменная величина, ассоциированная с ребром; t]{z,u) - коэффициент видимости абонента; а - параметр значимости динамических переменных, ассоциированных с клиентом и ребром (а > 0); ß - параметр значимости коэффициента видимости (ß > 0); q - случайное число, равномерно распределенное в интервале [0...I]; <?0 - коэффициент использования/исследования, (0 ^ <7о ^ 0; ^ - случайная переменная, выбранная согласно вероятностному распределению, заданному в формуле (8).

Если же q > до , то переход выполняется на основе расчета случайной переменной величины S, выбранной согласно вероятностному распределению, заданному уравнением (8):

[Ts(t) + T2i(t)la

pk(z,s) =

_ „ если cu т е J,(z)

Z hW + bWf-Wz,«/ ' (8)

0 иначе

где, J¡{z) - множество абонентов, которые еще не подключены к текущему шагу цикла, чтобы полученное решение было допустимым.

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

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

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

Рис. 1

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

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

Для проведения экспериментов было сгенерировано множество случайных задач различной размерности. По результатам проведенных экспериментов можно сделать следующие выводы. На задачах малой размерности (m = 6...40, k = 5...11) генетический и муравьиный алгоритмы обеспечивают получение точных решений при каждом исполнении алгоритма. Сравнение проводилось с решениями, полученными точным методом полного перебора.

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

Таблица 1

Размерность задачи Генетический алгоритм Муравьиный алгоритм

Время, сек ЦФ, усл. ед. Время, сек ЦФ, усл. ед.

т = 40, к = 40 0,03 1048350 0,02 1048350

т = 40 ,к = 50 0,05 1082850 0,03 1082850

я, = 40, £ = 60 13,68 1117350 1,02 1117350

и = 40,* = 70 64,18 1155300 1,31 1155300

т = 40 Д = 80 130,94 2207100 1,72 2207100

т = 40 Д = 90 238,32 2220900 2,08 2220900

т = 40 ,к = 100 388,44 2241600 2,64 2238150

Если рассматривать параметры настройки алгоритмов, то основное влияние на время работы и качество найденных решений оказывает заданное число поколений - в генетическом алгоритме, и количество циклов - в муравьином алгоритме. На рис. 2 приведена зависимость времени работы (в секундах) генетического алгоритма от числа поколений на задаче размерности « = 50, к = 50. На рис. 3 представлена зависимость (в секундах) времени работы муравьиного алгоритма от числа циклов на задаче размерности т = 50, к = 50 .

Ряд1 3.07 3.88 4.56 11.77 20.64 37.88 95.53 189.91

Число поколений

Рис. 2

I

«

I

ш

Рис.3

В заключении был проведен эксперимент по сравнению генетического и муравьиного алгоритмов на задачах большой размерности (т = 100...1000Д= 100... 1000) при следующих параметрах: Л'Стах =1000, МГтах = 1000. Для величин целевых функций приведены наилучшие значения, найденные в течение 100 запусков алгоритмов. Результаты, свидетельствующие о преимуществе муравьиного алгоритма, представлены в табл. 2.

Таблица 2

Размерность т = 100,* = 100 т = 200, £ = 200 т = 500, к - 500 »1 = 1000, £ = 1000

Параметры Время сек ЦФ усл. ед. Время сек ЦФ усл. ед. Время сек ЦФ усл. ед. Время сек ЦФ усл. ед.

ГА 435,64 5983050 989,51 6267700 2453,78 8459800 НА -

МА 6,3 5983050 36,34 6267700 127,56 8043050 302,48 9456300

Пояснения к таблице: ГА - генетический алгоритм, МА - муравьиный алгоритм, ЦФ- целевая функция, НА - время расчета превысило 10000 секунд.

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

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

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

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

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

Список трудов

1. Ермолаев, С.Ю. Математические методы топологического проектирования широкополосных беспроводных сетей передачи информации / С.Ю. Ермолаев // Обозрение прикладной и промышленной математики. - Йошкар-Ола, 2006. - С.292-293.

2. Ермолаев, С.Ю. Математические методы топологического проектирования беспроводных сетей передачи информации J С.Ю. Ермолаев // Тезисы докладов XIV российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов ПГАТИ. -Самара, 2007.-С.41-42.

3. Ермолаев, С.Ю. Задача синтеза топологической структуры беспроводной сети / С.Ю. Ермолаев // Труды 9-й Международной конференции «Цифровая обработка сигналов и ее применение» (DSPA-2007). - Москва, 2007. -С. 168-171.

4. Ермолаев, С.Ю. Методы оптимизации размещения базовых станций для сетей стандарта WiMax / С.Ю. Ермолаев // Инфокоммуникационные технологии. - 2007. - Т.5, №2. - С. 19-22.

5. Ермолаев, С.Ю. Генетические алгоритмы в методах оптимизации / С.Ю. Ермолаев // Труды VI Международной научно-технической конференции «Физика и технические приложения волновых процессов». - Казань, 2007. -С. 317-318.

6. Ермолаев, С.Ю. Эволюционный подход к оптимальному размещению базовых станций / С.Ю. Ермолаев // Обозрение прикладной и промышленной математики. - Сочи-Адлер, 2007. - С. 136-137.

7. Ермолаев, С.Ю. Оптимальное размещение базовых станций на основе генетического алгоритма / С.Ю. Ермолаев // Тезисы докладов 8-й Международной научно-технической конференции «Проблемы техники и технологии телекоммуникаций». — Уфа, 2007. - С. 228-230.

8. Ермолаев, С.Ю. Эволюционный подход к решению задачи оптимального размещения базовых станций для сетей стандарта WiMax / С.Ю. Ермолаев

// Тезисы докладов XV российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов ПГАТИ. - Самара, 2008. - С.69-70.

9. Ермолаев, С.Ю. Применение генетических алгоритмов для решения задачи оптимального размещения базовых станций / С.Ю. Ермолаев // Труды 10-й Международной конференции «Цифровая обработка сигналов и ее применение» (DSPA-2008). - Москва, 2008. - С. 312-314.

10. Ермолаев, С.Ю. О преимуществе генетического подхода в задаче синтеза беспроводных сетей передачи информации / С.Ю. Ермолаев // Труды IX Международной научно-технической конференции «Кибернетика и высокие технологии XXI века». - Воронеж, 2008. - С. 488-492.

11. Ермолаев, С.Ю. Муравьиные алгоритмы оптимизации / С.Ю. Ермолаев // Инфокоммуникационные технологии. - 2008. - Т.6, №1. - С. 23-29.

12. Ермолаев, С.Ю. Размещение базовых станций на основе муравьиных алгоритмов / С.Ю. Ермолаев // Тезисы докладов XVI российской научной конференции профессорско-преподавательского состава, научных сотрудников и аспирантов ПГУТИ. - Самара, 2009. - С.82-83.

13. Ермолаев, С.Ю. «Природные вычисления» как способ решения сложных задач в телекоммуникациях / С.Ю. Ермолаев // Труды 11-й Международной конференции «Цифровая обработка сигналов и ее применение» (DSPA-2009). - Москва, 2009. - С. 216-218.

14. Ермолаев, С.Ю. Генетический подход к задаче оптимального размещения базовых станций в сетях IEEE 802.16-2004 / С.Ю. Ермолаев, В.Г. Карта-шевский // Труды 12-й Международной конференции «Цифровая обработка сигналов и ее применение» (DSPA-2010). - Москва, 2010. - С. 255-257.

15. Ермолаев, С.Ю. Оптимальное размещение базовых станций / С.Ю. Ермолаев // Telecommunication Sciences. - 2010. - Т. 1, №1. - С. 82-90.

16. Ермолаев, С.Ю. Свидетельство о государственной регистрации программы для ЭВМ. Конфигуратор оптимальной топологии для беспроводной сети стандарта IEEE 802.16-2004 / С.Ю. Ермолаев, Т.С. Шестакова.-№ 2010616639 от 6.10.2010. - 1 с.

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

информатики» 443010, г. Самара, ул. Льва Толстого 23.

Отпечатано фотоспособом в соответствии с материалами, представленными

_заказчиком_

Подписано в печать 17.11.10 г. Формат б0х84'/,6 Бумага писчая№1. Гарнитура Тайме.

_Заказ 812. Печать оперативная .Усл. печ. л.0.92. Тираж 100 экз._

Отпечатано в издательстве учебной и научной литературы Поволжского государственного университета телекоммуникаций и информатики 443090, г. Самара, Московское шоссе 77. т. (846) 228-00-44

ВВЕДЕНИЕ

1. ЗАДАЧА СИНТЕЗА ТОПОЛОГИЧЕСКОЙ СТРУКТУРЫ

ПРИ СОЗДАНИИ СЕТЕЙ БЕСПРОВОДНОГО ДОСТУПА

1.1 Развитие беспроводных сетей передачи информации

1.2 Сети

1.2.1 Технология ЬТЕ и ее архитектура

1.2.2 Технология 11МВ и ее архитектура

1.2.3 Технология \ViMAX и ее архитектура

1.2.3.1 Основные принципы архитектуры сети \ViMAX

1.2.3.2 Варианты применения сетей \ViMAX

1.2.3.3 Место \ViMAX в иерархии структуры сетей NGN

1.2.3.4 Достоинства и недостатки

1.3 Этапы создания сети беспроводного доступа

1.3.1 Программный комплекс планирования сетей связи

1.4 Задача размещения базовых станций 34 1.4.1 Постановка модифицированной задачи размещения базовых станций

1.5 Выводы

2. СПОСОБЫ РЕШЕНИЯ ЗАДАЧ РАЗМЕЩЕНИЯ

2.1 Анализ способов решения задач размещения

2.2 Метод полного перебора

2.3 Метод ветвей и границ 56 2.3.1 Метод ветвей и отсечений

2.4 Алгоритм поиска по соседству

2.4.1 Схема «обмена клиентами»

2.4.2 Схема «перемещение устройств обслуживания»

2.4.3 Структура алгоритма

2.5 Генетический алгоритм

2.6 Выводы

3. РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО РАЗМЕЩЕНИЯ

НА ОСНОВЕ МУРАВЬИНЫХ АЛГОРИТМОВ ОПТИМИЗАЦИИ

3.1 История появления муравьиных алгоритмов оптимизации

3.2 Особенности искусственных муравьев

3.3 Характеристики муравьиных алгоритмов оптимизации

3.4 Обобщенная структура алгоритмов муравьиной оптимизации

3.5 Принципы функционирования муравьиных алгоритмов оптимизации

3.6 Применение метаэвристики оптимизации муравьиной колонией к задаче оптимального размещения базовых станций

3.7 Выводы

4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ И ИССЛЕДОВАНИЕ ПРЕДЛОЖЕННЫХ АЛГОРИТМОВ

4.1 Среда разработки Borland Delphi

4.2 Реализация предложенных алгоритмов в среде

Borland Delphi 7.

4.2.1 Интерфейс созданного программного обеспечения

4.3 Исследование алгоритмов на основе созданного программного обеспечения

4.3.1 Исследование метода полного перебора

4.3.2 Исследование генетического алгоритма

4.3.3 Исследование муравьиного алгоритма

4.4 Выводы 145 Заключение 147 Список используемой литературы 150 Приложение

СПИСОК СОКРАЩЕНИЙ

1G, 2G, 3G, 4G — сети сотовой связи первого, второго, третьего, четвертого поколений

3GPP (The 3rd Generation Partnership Project) - партнерский проект ETSI, занимающийся стандартизацией в области сетей 3G

3GPP2 (The 3rd Generation Partnership Project 2) - параллельный проект партнерства ETSI по стандартизации сетей 3G

AES (Advanced Encryption Standard) - улучшенный стандарт шифрования AMPS (Advanced Mobile Phone Service) - улучшенное обслуживание для мобильной связи АР (Access Point) - точка доступа

API (Application Programming Interface) - интерфейс прикладного программирования

ARQ (Automatic Repeat Request) - механизм автоматического запроса повторной передачи

ASN (Access Service Network) - сервисная сеть доступа

CATV (Cable Television) - система кабельного телевидения •

CDMA (Code Division Multiple Access) - множественный доступ с кодовым

разделением каналов

CFLP (Capacity Facility Location Problem) - емкостная задача размещения устройств обслуживания

CSN (Connectivity Service Network) - сеть подключения

D-AMPS (Digital Advanced Mobile Phone Service) - улучшенное обслуживание для мобильной связи на основе цифровой обработки

ЕАР (Extensible Authentication Protocol) - расширенный протокол аутентификации

EDGE (Enhanced Data GSM Environment) - технология повышения скорости передачи данных в сети GSM/GPRS

ETSI (European Telecommunication Standard Institute) - Европейский институт телекоммуникационных стандартов

EV-DO (Evolution Data Only) - эволюционная технология передачи только данных

FDMA (Frequency Division Multiple Access) - множественный доступ с частотным разделением каналов

FTTx (Fiber То The .) — архитектура широкополосного доступа с использованием оптического волокна на участке от центральной станции до некоторой точки «х»

GPRS (General Packet Radio Service) - подсистема услуг пакетной передачи данных

GSM (Global System for Mobile Telecommunications) - глобальная система мобильной связи

HSDPA (High Speed Downlink Packet Access) - высокоскоростной пакетный доступ в линии «вниз»

HSUPA (High Speed Uplink Packet Access) - высокоскоростной пакетный доступ в линии «вверх» '

ISDN (Integrated Service Digital Network) - цифровая сеть с интеграцией служб IEEE (Institute of Electrical and Electronics Engineers) — институт инженеров по электротехнике и электронике

IMT-2000 (International Mobile Telecommunications 2000) - международная программа, проводящаяся под эгидой ITU IP (Internet Protocol) — протокол сети Интернет

IPTV (Internet Protocol Television) - технология передачи телевидения по IP-сети

ITU (International Telecommunications Union) — международный союз электросвязи

JDC (Japan Digital Cellular) - Японская цифровая сотовая связь

KPI (Key Performance Indicators) — ключевые индикаторы (параметры) качества функционирования сети сотовой связи

LTE (Long Term Evolution) — долгосрочная эволюция сетей сотовой связи MAC (Medium Access Control) — уровень управления доступом к среде передачи

MIMO (Multiple Input Multiple Out) - антенная технология, имеющая несколько входов и несколько выходов (по отношению к каналу)

MSAN (Multi Service Access Node) - мультисервисный узел доступа

MSCFLP (Multi Source Capacity Facility Location Problem) - емкостная задача размещения устройств обслуживания со множеством источников обслуживания

NGN (Next Generation Network) - сеть следующего поколения

NMT (Nordic Mobile Telephone) - Северная система мобильной телефонии

NP-hard (Nonpolynomial) - трудная задача, обладающая свойством отсутствия возможности решения за время, ограниченное полиномом некоторой степени

NTT (Nippon Telegraph & Telephone Corporation) - Японская корпорация по телеграфии и телефонии

OFDM (Orthogonal Frequency Division Multiplexing) — механизм модуляции посредством ортогональных несущих

OFDMA (Orthogonal Frequency Division Multiple Access) — множественный доступ посредством ортогональных несущих

PDC (Personal Digital Cellular) - персональная цифровая сотовая связь

PLC (Power Line Communication) - технология передачи данных по существующим электрическим линиям

PON (Passive Optical Network) - технология пассивных оптических сетей QoS (Quality of Service) - качество услуг связи

RTMS (Radio Telephone Mobile System) - радиотелефонная система мобильной связи

SAE (System Architecture Evolution) — эволюция архитектуры системы, архитектура сети LTE

SMS (Short Message Service) - услуга коротких сообщений

SSCFLP (Single Source Capacity Facility Location Problem) - емкостная задача размещения устройств обслуживания с одним источником обслуживания

SUI (Stanford University Interim) - канальная модель распространения сигналов, разработанная рабочей группой IEEE 802.16-2004 в университете Стэнфорда

TACS (Total Access Communications System) - система связи с общим доступом

TDMA (Time Division Multiple Access) - множественный доступ с временным разделением каналов

UFLP (Uncapacitated Facility Location Problem) - не емкостная задача размещения устройств обслуживания

UMB (Ultra Mobile Broadband) - технология сверх мобильной широкополосной связи

UMTS (Universal Mobile Telecommunications System) — универсальная система мобильной связи

VLAN (Virtual Local Area Network) - виртуальная локальная сеть VoD (Video on Demand) - передача видео данных по запросу

VoIP (Voice over Internet Protocol) - технология передачи голоса «поверх» IP

VSAT (Very Small Aperture Terminal) - технология спутниковой связи с очень малой апертурой

W-CDMA (Wideband Code Division Multiple Access) - стандарт сети радиодоступа сотовой связи с широкополосным CDMA

WiFi (Wireless Fidelity) - технология беспроводного доступа на базе стандарта IEEE802.il

WiMAX (Worldwide Interoperability for Microwave Access) - технология беспроводного широкополосного доступа на базе стандарта IEEE 802.16 WLAN (Wireless Local Area Network) - беспроводная локальная сеть xDSL (. .Digital Subscriber Link) - технология цифровой абонентской линии AC — абонентская станция БС — базовая станция

БШД - беспроводной широкополосный доступ МАО - муравьиные алгоритмы оптимизации МСЭ - международный союз электросвязи ПО - программное обеспечение РФ - Российская Федерация '

ТфОП - сеть телефонной связи общего пользования

Актуальность темы

Стремительное развитие беспроводных телекоммуникационных технологий в последние два десятилетия привело к непрерывной смене одних стандартов в области беспроводной связи другими. Так, например, в Российской Федерации лишь в последние несколько лет начали появляться сети сотовой связи третьего поколения (сети 3G), а уже мировыми проектными организациями, разработаны документы, определяющие основы нового стандарта - сети 4G. Анализ тенденций развития телекоммуникационной отрасли показывает, что сети 4G будут создаваться на основе следующих технологий: LTE, WiMAX. Одним из возможных вариантов построения вероятно будет сосуществование вышеназванных технологий, в зависимости от потребностей операторов связи. Сети беспроводной связи 4G предоставляют широкий спектр услуг широкополосного доступа: передача голоса, передача данных, Интернет, видео телефония, мобильное телевещание и др.

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

Характерной особенностью всех стандартов, разработанных в последние годы, является .ориентация на обеспечение требуемых показателей качества обслуживания QoS. Не исключением является и стандарт IEEE 802.16-2004, на который ориентировано представленное диссертационное исследование, -стандарт беспроводных сетей для организации фиксированного широкополосного доступа.

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

Среди публикаций, посвященных изучению методологии создания сетей IEEE 802.16-2004 и решению задач размещения базовых станций, следует отметить исследования Вишневского В.М., Ляхова А.И., Портного С.Л., Шахновича И.В., Широкова В. Также существуют исследования, ориентированные на решение общих задач размещения, среди которых можно выделить работы Кочетова Ю.А., Пащенко М.Г., Береснева В.Л. Среди зарубежных ученых, занимающихся исследованием вопросов размещения, можно выделить фамилии Murphy S., Amaldi Е., Capone A., Sridharan R., Klincewicz J.G., Barcelo J., Beasley J.E. Большинство публикаций, посвященных решению задач размещения, ориентируются на использование точных методов. При этом решаются задачи небольшой размерности, поскольку точные методы, обладающие экспоненциальной зависимостью времени работы от количества входных данных, теряют свою эффективность с увеличением размерности.

Объектом исследования являются беспроводные сети фиксированного широкополосного доступа, создаваемые операторами связи.

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

Цель работы и задачи исследования

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

На основе поставленной в исследовании цели сформировалась необходимость решения следующего ряда задач:

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

- анализ существующих методов решения ЫР-трудных задач размещения;

- разработка алгоритмов оптимального размещения базовых станций и подключения к ним клиентов;

- создание программного обеспечения для решения задач размещения любой размерности и конфигурации;

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

Методы исследования

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

Достоверность результатов

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

Научная новизна

Научная новизна диссертационного исследования заключается в следующем:

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

- предложен алгоритм размещения базовых станций на основе генетического подхода;

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

Личный вклад .

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

Практическая ценность и реализация результатов работы

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

Полученные результаты и алгоритмы могут быть использованы научно-исследовательскими, проектными организациями и телекоммуникационными компаниями при проектировании и внедрении сетей стандарта "\У1МАХ.

Основные теоретические и практические результаты, полученные в диссертационном исследовании, использованы в ООО «Саха-Белком» и внедрены в учебный процесс ГОУВПО ПГУТИ, что подтверждено соответствующими актами.

Апробация работы

Основное содержание работы докладывалось и обсуждалось на XIV, XV и XVI Российской научно-технической конференции ПГУТИ (Самара, 2007г., 2008г. и 2009г.), на VIII Международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» (Уфа, 2007г.), на IX, X, XI и XII Международной конференции «Цифровая обработка сигналов и ее применение» (Москва, 2007г., 2008г., 2009г., 2010г.), IX Международной научно-технической конференции «Кибернетика и высокие технологии» (Воронеж, 2008г.).

Публикации

По теме диссертации опубликовано 16 работ, в том числе 2 работы из перечня, рекомендованного ВАК РФ для публикации результатов диссертационных исследований, 1 статья в журнале «Telecommunication Sciences» (Украина), 6 тезисов, 6 докладов в трудах международных научных конференций, а также 1 свидетельство о регистрации программы для ЭВМ.

Основные положения, выносимые на защиту

- модифицированная постановка задачи размещения базовых станций;

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

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

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

Структура и объем работы

Диссертационное исследование состоит из введения, четырех глав, заключения, списка используемой литературы и приложений. Работа содержит 163 страницы машинописного текста, 39 рисунков и 29 таблиц. Список используемой литературы состоит из 111 наименований.

4.4 Выводы

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

1. Эвристические методы затрачивают гораздо меньше времени на нахождение решения, в отличие от точных методов.

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

В целом по итогам работы можно сформулировать следующие основные полученные результаты:

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

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

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

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

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

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

1. Вишневский, В. Технология сотовой связи LTE почти 4G / В. Вишневский, А. Красилов, И. Шахнович // Первая миля. - 2009. - № 2. - С. 2-13.

2. IEEE 802.16 первый стандарт мобильной связи 4G / По материалам «Huawei Technologies Communicate» // Век качества. - 2008. - № 6. - С. 50-52.

3. Абилов, A.B. Сети сотовой связи. Учебное пособие / A.B. Абилов. Ижевск: ИжГТУ, 2000.-20 е.: ил.

4. Громаков, Ю.А. Стандарты и системы подвижной радиосвязи / Ю.А. Громаков. М.: Эко-Трендз, 1997. - 239 с.

5. Бабков, В.Ю. Системы мобильной связи / В.Ю. Бабков, М.А. Вознюк, В.И. Дмитриев. С.-Пб.: С.-ПБ ГУТ, 1999. - 330 с.

6. Волков, Л.Н. Системы цифровой радиосвязи: базовые методы и характеристики / Л.Н. Волков, М.С. Немировский, Ю.С. Шинаков. М.: Эко-Трендз, 2005. - 392 е.: ил.

7. Бабков, В.Ю. Системы связи с кодовым разделением каналов / В.Ю. Бабков, М.А. Вознюк, А.Н. Никитин, М.А. Сивере. С.-Пб.: С.-ПБ ГУТ, 1999. - 120 с.

8. Тихвинский, В. О. Управление и качество услуг в сетях GPRS/UMTS / В.О, Тихвинский, С. В. Терентьев. М.: Эко-Трендз, 2007. - 400 с.

9. Тихвинский, В.О. Сети подвижной связи третьего поколения: экономические и технические аспекты развития в России / В.О. Тихвинский. М.: Радио и связь, 2004.-312 с.

10. Тихвинский, В.О. Подвижная связь третьего поколения: Экономика и качество услуг / В.О. Тихвинский, Е.Е. Володина. М.: Радио и связь, Горячая линия - Телеком, 2005. - 240 с.

11. Кааранен, X. Сети UMTS. Архитектура, мобильность, сервисы / X. Кааранен, А. Ахтиайнен, Л. Лаитинен. М.: Техносфера, 2007. - 464 с.

12. Парфенов, Б.А. Нас ждет решающий год / Б.А. Парфенов // Вестник связи. -2008.-№ 1.-С. 38-41.

13. IEEE Std 802.16-2004. IEEE Standard for Local and metropolitan area networks. Part 16: Air Interface for Fixed Broadband Wireless Access Systems. IEEE, 1 October 2004.

14. Шахнович, И. Стандарт широкополосного доступа IEEE 802.16 для диапазонов ниже 11 ГГц / И. Шахнович // ЭЛЕКТРОПИКА: НТБ. 2005. - № 1. -С. 8-14.

15. Шахнович, И. Стандарт широкополосного доступа IEEE 802.16-2004. Режим OFDMA и адаптивные антенные системы / И. Шахнович // ЭЛЕКТРОНИКА: НТБ. 2005. - № 2. - С. 46-52.

16. Кучерявый, Е.А. Сети WiMAX, их характеристики и перспективы внедрения Электронный документ. / Е.А. Кучерявый, Д.А. Молчанов. Режим доступа: http://www.multiinfocom.ru/ru/artpdf/setiwimaxchar.pdf. - 10.12.2006.

17. Шахнович, И. Широкополосная мобильность: IEEE 802.1 бе. Часть 1: МАС-уровень / И. Шахнович // ЭЛЕКТРОНИКА: НТБ. 2007. - № 2. - С. 18-27.

18. Шахнович, И. Широкополосная мобильность: IEEE 802.1 бе. Часть 2: Физический уровень и элементная база / И. Шахнович // ЭЛЕКТРОНИКА: НТБ. -2008. -№ 1.-С. 98-104.

19. Шахнович, И. Архитектура сети WiMAX: основные элементы и принципы / И. Шахнович // Первая миля. 2009. - № 1. - С. 6-15.

20. Осипов, И.Е. Mesh-сети: технологии, приложения, оборудование / И.Е. Осипов // Технологии и средства связи. 2006. - № 4. - С. 38-45.

21. Бакланов, И.Г. NGN: принципы построения и организации / И.Г. Бакланов. -М.: Эко-Трендз, 2008. 400 с.

22. Вишневский, В. Системы поллинга: теория и применение в широкополосных беспроводных сетях / В. Вишневский, О. Семенова. М.: Техносфера, 2007. - 312 с.

23. Свердлов, Д. «Скартел» начинает с Yota / Д. Свердлов // Connect! Мир связи.-2008.-№ 10.-С. 68.

24. Широков, В. Методология создания беспроводных мультисервисных сетей класса WiMAX / В. Широков // Технологии и средства связи. 2010. - № 1. - С. 32-33.

25. Вишневский, В.М. Широкополосные беспроводные сети передачи информации / В.М. Вишневский, А.И. Ляхов, И.В. Шахнович, C.JI. Портной. -М.: Техносфера, 2005. 456 с.

26. Зыбин, В.А. Исследование новых возможностей использования технологии WiMAX / В.А. Зыбин, В.В. Крылов // Труды научной конференции по радиофизике. Нижний Новгород, 2006. - С. 66-67.

27. Иванов, А. Оборудование WiMAX решение компании Alvarion / А. Иванов, С. Портной // Первая миля. - 2009. - № 2. - С. 32-39.

28. Erceg, V. Channel models for fixed wireless applications / V. Erceg, K.V.S Hari, et al. // Tech. Rep. IEEE 802.16a-03/01, June 2003.

29. Бузов, A.JI. Управление радиочастотным спектром и электромагнитная совместимость радиосистем. Учебн. пособие / A.JI. Бузов, М.А. Быховский, Н.В. Васехо и др. Под ред. д.т.н., проф. М.А. Быховского. М.: Эко-Трендз, 2006.-376 е.: илл.

30. Lenstra, J.K. Complexity of scheduling under precedence constraints / J.K. Lenstra, K.A.H.G. Rinnooy // Operations Research. 1978. - № 26. - P. 22-35.

31. Neebe, A.W. An algorithm for the fixed-charge assigning users to sources problem / A.W. Neebe, M.R. Rao // Journal of the Operational Research Society.1983.-№34.-P. 1107-1113.

32. Barcelo, J. A heuristic Lagrangean algorithm for the capacitated plant location problem / J. Barcelo, J. Casanovas // European Journal of Operational Research.1984.-№ 15.-P. 212-226.

33. Klincewicz, J.G. A Lagrangean relaxation heuristic for capacitated facility location with single-source constraints / J.G. Klincewicz, H. Luss // Journal of the Operational Research Society. 1986. - № 37. - P. 495-500.

34. Erlenkotter, D. A dual-based procedure for uncapacitated facility location / D. Erlenkotter // Operations Research. 1978. - № 26. - P. 992-1009.

35. Sridharan, R. A Lagrangian heuristic for the capacitated plant location problem with single source constraints / R. Sridharan // European Journal of Operational Research. 1991, - № 66. - P. 305-312.

36. Pirkul, H. Efficient algorithm for the capacitated concentrator location problem / H. Pirkul // Computers & Operations Research. 1987. - № 14. - P. 197-208.

37. Beasley, J.E. Lagrangian heuristics for location problems / J.E. Beasley // European Journal of Operational Research. 1993. - № 65. - P. 383-399.

38. Сухарев, А.Г. Курс методов оптимизации: учеб. пособие / А.Г. Сухарев, А.В. Тимохов, В.В. Федоров. 2-е изд. - М.:ФИЗМАТЛИТ, 2005. - 368 с.

39. Шор, Н.З. О скорости сходимости метода обобщенного градиентного спуска с растяжением пространства / Н.З. Шор // Кибернетика. 1970. - № 2. - С. 8085.

40. Гэри, М. Вычислительные машины и труднорешаемые задачи / IVL Гэри, Д. Джонсон. М.:Мир, 1982. - 416 с.

41. Береснев, В.JI. Алгоритм неявного перебора для задачи типа размещения и стандартизации / B.JI. Береснев // Управляемые системы. Новосибирск, Институт математики Сиб.отд. АН СССР. Вып. 12. - С. 24-34.

42. Кочетов, Ю.А. Лагранжевы релаксации в задаче выбора оптимального состава системы технических средств / Ю.А. Кочетов, М.Г. Пащенко // Управляемые системы. ИМ СО РАН, 1993. - вып.31. - С. 26-39.

43. Береснев, В.Л. Дискретные задачи размещения и полиномы от булевых переменных / В.Л. Береснев. Новосибирск: Изд-во Инст. математики, 2005. — 408 с.

44. Görtz, S. A subgradient-based branch-and-bound algorithm for the capacitated facility location problem Электронный документ. / S. Görtz, A. Klose. Режим доступа: http://www.imf.au.dk/publications/wp/2009/imf-wp-2009-01 .pdf. -6.10.2009.

45. Bockmayr, A. Pseudo-Boolean and finite domain constraint programming: a case study Электронный документ. / A. Bockmayr, T. Kasper // Режим доступа: http://www.princeton.edu/~chaff/papers/pseudo-boolean-and-finite.pdf. - 7.02.2006.

46. Holland, J.H. Adaptation in natural and artificial systems / J.H. Holland. Ann Arbor: University of Michigan Press, 1992. - 228 pp.

47. Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы: Пер. с польск. И.Д. Рудинского / Л. Рутковский, Д. Рутковская, М. Пилиньский. — М.: Горячая линия Телеком, 2006. — 383 е.: ил.

48. Freisleben, В. Genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems / B. Freisleben, P. Merz // Proceedings of IEEE International Conference on Evolutionary Computation, 1996, IEEE Press, pp. 616-621.

49. Батищев, Д.И. Генетические алгоритмы решения экстремальных задач. Учебное пособие / Д.И. Батищев. Воронеж: ВГТУ, 1995. - 69 с.

50. Слюсар, В.И. Синтез антенн на основе генетических алгоритмов. Часть 1 / В .И. Слюсар // Первая миля. 2008. - № 6. - С. 16-23.

51. Слюсар, В.И. Синтез антенн на основе генетических алгоритмов. Часть 2 / В.И. Слюсар // Первая миля. 2009. - № 1. - С. 22-25.

52. Лютиков, Б.Г. Модифицированный генетический алгоритм выбора конфигурации оборудования проектируемой телекоммуникационной сети /Б.Г. Лютиков, Д.В. Морозов, В.П. Морозов // Телекоммуникации. 2008. - № 5. - С. 10-12.

53. Бугров, Д.А. Применение эволюционного метода для оптимизации магистральной сети связи / Д.А. Бугров, Н.Л. Сторожук // Электросвязь. 2007. -№ 5. - С. 30-33.

54. Курейчик, В.В. Эволюционные, синергетические и гомеостатические методы принятия решений / В.В. Курейчик. Таганрог: Изд-во ТРТУ, 2001. -221 с.

55. Курейчик, В.М. Генетические алгоритмы и их применение / В.М. Курейчик. Таганрог: Изд-во ТРТУ, 2002. - 242 с.

56. Курейчик, В.М. Генетические алгоритмы. Учебное пособие / В.М. Курейчик, В.В. Курейчик, Л.А. Гладков. М.: Физматлит, 2006. - 320 с.

57. Алексеева, Е.В. Алгоритмы локального поиска для задачи о р-медиане с предпочтениями клиентов: автореф. дис. . канд. физ-мат. наук: 01.01.09: защищена 24.10.2007 / Е.В. Алексеева, Ин-т мат. им. С. Л. Соболева СО РАН. -Новосибирск, 2007. 19 с.

58. Кочетов, Ю.А. Методы локального поиска для дискретных задач размещения: автореф. дис. . д-ра физ-мат. наук: 05.13.18: защищена1901.2010 / Ю.А. Кочетов, Ин-т. выч. матем-ки и матем-ой геофизики СО РАН. Новосибирск, 2009. - 30 с.

59. Федорова, М.А. Вычислительные и эволюционные методы в стохастических системах с обнаружением и адаптацией: автореф. дис. . канд. физ-мат. наук: 01.01.09: защищена 07.11.2007 / М.А. Федорова, Ул. гос. ун-т. Ульяновск, 2007.-23 с.

60. Cortinhal, M.J. Genetic algorithms for the single source capacitated location problem: a computational study / M.J. Cortinhal, M.E. Captivo // 4th Metaheuristics International Conference. Porto, Portugal. 2001. - P. 355-359.

61. Ярушкина, Н.Г. Эффективность генетических алгоритмов для задач автоматизированного проектирования / Н.Г. Ярушкина, A.M. Наместников // Известия РАН. Теория и системы управления. 2002. - № 2. - С. 127-134.

62. Ермолаев, С.Ю. Оптимальное размещение базовых станций / С.Ю. Ермолаев // Telecommunication Sciences. 2010. - T. 1, №1. - С. 82-90.

63. Корнеенко, В.П. Методы оптимизации / В.П. Корнеенко. М.: Высшая школа, 2007. - 664 е.: ил.

64. Dorigo, M. Optimization, learning and natural algorithms (in italian) / M. Dorigo // Ph.D. dissertation, Dipartimento di Elettronica, Politécnico di Milano, Italy. -1992.-P. 140.

65. Deneubourg, J.-L. The self-organizing exploratory pattern of the Argentine ant / J.-L. Deneubourg, S. Aron, S. Goss, J.M. Pasteels // Journal of Insect Behavior. -Vol. 3.-1990.-P. 159.

66. Goss, S. Self-organized shortcuts in the Argentine ant / S. Goss, S. Aron, J.-L. Deneubourg, J.M. Pasteels // Naturwissenschaften. vol. 76. - 1989. - P. 579-581.

67. Pasteels, J.M. Self-organization mechanisms in ant societies (i): Trail recruitment to newly discovered food sources / J.M. Pasteels, J.-L. Deneubourg, S. Goss // Experientia Supplementum. Yol. 54. - 1987. - P. 155.

68. Dorigo, M. Ant System: Optimization by a colony of cooperating agents / M. Dorigo, V. Maniezzo, A. Colorni // IEEE Transactions on Systems, Man, and Cybernetics Part B. - Vol. 26, № 1. - 1996. - P. 29-41.

69. Dorigo, M. Ant colonies for the traveling salesman problem / M. Dorigo, L.M. Gambardella // BioSystems. Vol. 43, № 2. - 1997. - P. 73-81.

70. Dorigo, M. Ant Colony System: A cooperative learning approach to the traveling salesman problem / M. Dorigo, L.M. Gambardella // IEEE Transactions on Evolutionary Computation. Vol. 1, № 1. - 1997. - P. 53-66.

71. Stutzle, T. MAX-MIN Ant System / T. Stutzle, H.H. Hoos // Future Generation Computer Systems. Vol. 16, № 8. - 2000. - P. 889-914.

72. Bullnheimer, B. A new rank-based version of the Ant System: A computational study / B. Bullnheimer, R.F. Hartl, C. Strauss // Central European Journal for Operations Research and Economics. Vol. 7, № 1. - 1999. - P. 25-38.

73. Maniezzo, V. Exact and approximate nondeterministic tree-search procedures for the quadratic assignment problem / V. Maniezzo // INFORMS Journal on Computing. Vol. 11, № 4. - 1999. - P. 358-369.

74. Blum, C. The hyper-cube framework for ant colony optimization / C. Blum, M. Dorigo // IEEE Transactions on Systems, Man, and Cybernetics Part B. - Vol. 34, №2.-2004.-P. 1161-1172.

75. Dorigo, M. Ant algorithms for discrete optimization / M. Dorigo, G. Di Caro, L.M. Gambardella // Artificial Life. Vol. 5, № 2. - 1999. - P. 137-172.

76. Dorigo, M. The Ant Colony Optimization meta heuristic / M. Dorigo, G. Di Caro // New Ideas in Optimization, D. Corne et al., Eds. McGraw Hill, London, UK. -1999.-P. 11-32.

77. Gambardella, L.M. Ant Colony System hybridized with a new local search for the sequential ordering problem / L.M. Gambardella, M. Dorigo // INFORMS Journal on Computing. Vol. 12, № 3. -2000. - P. 237-255.

78. Manfrin, M. Parallel ant colony optimization for the traveling salesman problem I M. Manfrin, M. Birattari, T. Stutzle, M. Dorigo // In Proceedings of ANTS 2006, ser. LNCS, M. Dorigo et al., Eds., vol. 4150. Springer Verlag. 2006. - P. 224-234.

79. Gutjahr, W.J. A graph-based ant system and its convergence / W.J. Gutjahr // Future Generation Computer Systems. Vol. 16, № 9. - 2000. - P. 873-888.

80. Zlochin, M. Model-based search for combinatorial optimization: A critical survey / M. Zlochin, M. Birattari, N. Meuleau, M. Dorigo // Annals of Operations Research. -Vol. 131, № 1-4.-2004.-P. 373-395.

81. Dorigo, M. Ant colony optimization artificial ants as a computational intelligence technique // M. Dorigo, M. Birattari, T. Stutzle // IEEE Computational Intelligence Magazine. - Vol. 1, № 4. - 2006. - P. 28-39.

82. Dorigo, M. An introduction to ant colony optimization Электронный документ. / M. Dorigo, К. Socha. Режим доступа: http://iridia.ulb.ac.beAridiaTrSeries/IridiaTr2006-01 ОгООЗ .pdf. -17.10.2008.

83. Fiechter, C.N. Efficient reinforcement learning / C.N. Fiechter // In Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory (COLT 1994), New Brunswick, NJ. 1994. - P. 88-9.7.

84. Gambardella, L.M. MACS-VRPTW: A multiple ant colony system for vehiclerouting problems with time windows / L.M. Gambardella, E.D. Taillard, G. Agazzi //i

85. New Ideas in Optimization, D. Corne et al., Eds. McGraw Hill, London, UK. -1999.-P. 63-76.

86. Merkle, D. Ant colony optimization for resource-constrained project scheduling / D. Merkle, M. Middendorf, H. Schmeck // IEEE Transactions on Evolutionary Computation. Vol. 6, № 4. - 2002. - P. 333-346.

87. De Campos, L.M. Ant colony optimization for learning Bayesian networks / L.M. de Campos, J.M. Fernandez-Luna, J.A. Gamez, J.M. Puerta // International Journal of Approximate Reasoning. Vol. 31, № 3. - 2002. - P. 291-311.

88. Montemanni, R. Ant colony system for a dynamic vehicle routing problem / R. Montemanni, L.M. Gambardella, A.E. Rizzoli, A.V. Donati // Journal of Combinatorial Optimization. Vol. 10. - 2005. - P. 327-343.

89. Штовба, С.Д. Муравьиные алгоритмы: теория и применение / С.Д. Штовба // Программирование. 2005. - №4. - С. 1-16.

90. Shmygelska A. An ant colony optimisation algorithm for the 2d and 3d hydrophobic polar protein folding problem Электронный документ. / A. Shmygelska, H.H. Hoos. Режим доступа: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC555464 - 14.12.2009.

91. Dorigo, M. Evolving self-organizing behaviors for a Swarm-bot / M. Dorigo, V. Trianni, E. Sahin // Autonomous Robots. Vol. 17, № 2-3. - 2004. - P. 223-245.

92. Di Caro, G. AntNet: Distributed stigmergetic control for communications networks / G. Di Caro, M. Dorigo // Journal of Artificial Intelligence Research. Vol. 9.- 1998.-P. 317-365.

93. Соболь, И.М. Метод Монте-Карло / И.М. Соболь. M.: Наука. Главная редакция физико-математической литературы, 1985. - 80 с.

94. Бакнелл, Д.М. Фундаментальные алгоритмы и структуры данных в Delphi: Пер. с англ. / Д.М. Бакнелл. СПб.: ООО «ДиаСофтЮП», 2003. - 560 с.

95. Сухарев, М.В. Основы Delphi. Профессиональный подход / М.В. Сухарев. СПб.: Наука и техника, 2004. - 600 с.

96. Ермолаев, С.Ю. Свидетельство о государственной регистрации программы для ЭВМ. Конфигуратор оптимальной топологии для беспроводной сети стандарта IEEE 802.16-2004 / С.Ю. Ермолаев, Т.С. Шестакова. № 2010616639 от 6.10.2010.-1 с.