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

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

КОСИЛОВ Никита Александрович

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

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

Автореферат

Диссертация на соискание ученой степени кандидата технических наук

5 АПР Ш1

Москва-2012 __

005020445

005020445

Работа выполнена на кафедре «Вычислительные системы и сети» Московско государственного института электроники и математики (технически университета)

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

доктор технических наук, профессор Жданов Владимир Сергеевич

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

Царегородцев Анатолий Валерьевич, зав. кафедрой «Комплекскной защит объектов информатизации» Всероссийской Государственной налогово" академии министерства финансов Российской Федерации;

кандидат технических наук, Воробьев Владимир Михайлович, начальни отдела НПФ «Информационные и сетевые технологии», г .Москва.

Ведущая организация: Федеральное государственное унитарное предприятие Московский научно-исследовательский радиотехнический институт (МНИРТИ)

Защита состоится " 26 " апреля 2012 года в 14 час. 00 мин. на заседании диссертационного совета Д 212.133.06 Московского государственного института электроники и математики (технического университета), 109028, Москва, Б. Трёхсвятительский пер., д. 3.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электроники и математики (технического университета).

Автореферат разослан "_"_2012 года.

Учёный секретарь диссертационного совета кандидат технических наук, профессор Н.Н.Грачёв

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

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

Одной из важных задач при построении беспроводных широкополосных сетей является проектирование зон покрытия, которое предназначено для обеспечения заданного качества приема по всей области обслуживания. На этом этапе определяются граничные участки обслуживаемой территории, обеспечивающие заданное качество приема сигналов, уточняются частотные и мощностные характеристики передатчиков базовых станций. Процесс проектирования зоны покрытия представляет многопараметрическую итерационную задачу со многими неизвестными, требующую соответствующих ресурсов и времени на обработку данных, таких как: количество соединительных линий, пропускная способность каналов связи и т.д. Проблемам проектирования зопы покрытия беспроводных широкополосных сетей посвящено значительное количество работ, среди которых следует отметить работы российских и зарубежных ученых: В. М. Вишневского, С. Портного, И. Шахновича, G. Balbo, S. С. Bruell, L. Fratta, L. Kleinrock, M. Olivetty, H. Takagi, S.C. Borst, OJ. Boxma и др.

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

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

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

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

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

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

1. Анализ способов организации беспроводных широкополосных сетей, методов и моделей проектирования зоны покрытия беспроводной широкополосной сети.

2. Исследование зоны покрытия беспроводной широкополосной сети, ее основных свойств и параметров.

3. Разработка математических моделей и алгоритмов пространственной организации беспроводных широкополосных сетей.

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

На защиту выносятся следующие основные результаты:

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

- алгоритмы проектирования зоны покрытия;

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

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

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

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

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

Результаты, полученные в диссертационной работе, имеют как теоретическое, так и прикладное значение и могут найти свое применение при анализе и построении беспроводных широкополосных сетей. Разработанные алгоритмы были использованы при проектировании зоны покрытия сети офиса страховой компании ОАО СК «Альянс» для подключения абонентов к voip-серверу, обеспечивающее передачу голосовой и видеоинформации. Результаты диссертационной работы использованы в учебном процессе кафедры «Вычислительных систем и сетей» МИЭМ при изучении дисциплин на курсах «Новые информационные технологии», «Беспроводные сети и мобильные системы».

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

Апробация диссертационной работы. Положения данной диссертации докладывались и обсуждались на следующих конференциях:

• на международных научно-технических конференциях «Information and Telecommunication Technologies in Intelligent Systems» (Швейцария, 2010 г);

• на 14-ой Международной конференции «Распределенные компьютерные и телекоммуникационные сети: теория и приложения» (DCCN-2010);

• на научно-методических совещаниях и семинарах ОАО СК «Альянс»;

• на научно-технических конференциях студентов, аспирантов и молодых специалистов МИЭМ (2008 - 2011 гг.);

• на научно-технических семинарах кафедры «Вычислительные системы и сети» МИЭМ (2008 - 2011 гг.).

Публикации. Основное содержание диссертационной работы и ее результатов отражено в научных и научно-технических работах автора. Всего автором опубликовано 7 научных работ из них 3 в журналах из перечня ВАК.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка использованных источников. Работа изложепа на 125 страницах, содержит 6 иллюстраций, 3 таблицы.

Основное содержание работы

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

В первой главе диссертации описываются способы построения беспроводных широкополосных сетей (БПШС): описана их структура, обеспечивающая взаимодействие пользователей и оконечных систем (базовая станция, точка доступа, контролер доступа), программное обеспечение БПШС и основные типы приложений, обеспечивающих соединения (эмулятор терминала, прямое соединение с базой данных, промежуточное программное обеспечение), описаны платы интерфейса сети, а также структура БПШС; приведена классификация беспроводных технологий (Bluetooth, Wi-Fi, WiMAX, беспроводная технология ZigBee) и краткое описание каждой из них; приведено описание зоны покрытия беспроводной широкополосной сети, под которой понимается обслуживаемая базовыми станциями местность, в которой энергетический уровень сигнала не ниже заданного соотношения сигнал/шум, определяемого чувствительностью приемника пользователя сети и вероятностью выполнения требований по допустимому соотношению сигнал/помеха, а также методы определения границы зоны покрытия БПШС,

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

Сформулированы три проблемы, возникающие при организации сети беспроводного доступа:

1. Потеря подключения к выбранной точке доступа и к локальной сети при перемещении между комнатами;

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

3. Неравномерное покрытие пространства офиса. Выполнен сравнительный анализ ряда основных известных методов планирования зоны покрытия БПШС: статистических, детерминированных, а также квазидетерминированных методов, а также моделей пространственной организации БПШС, среди которых модели Окипшга-ГЫа, СОБТ231-На1а и ^УаШзЬ-П^агш, а также недостатки каждой из них.

Табл. 1.

Модель Частотный диапазон, МГц Высота передающей антенны, м Высота приемной антеняы,м Расстояние между антеннами, ем

ОЬшшга-На1а 150...1500 30...200 1...10 1...20

БТ231-Ша 1500...2000 30...200 1...10 1...20

ТУаШЬ-П^апи 800...2000 4...50 1...3 0.02...5

Табл. 2.

Модель Крупный город Города средних гота малых размеров Пригородная зона Сельская местность

Окшпига-НаЬ + + + +

С08Т231-На1а + + - +

^'аШкЪ-Тксйапц + + - -

: В таблицах 1 и 2 приводится сравнительная характеристика моделей (в табл. 1 приведены ограничения моделей, а в табл. 2 - область применения.

По результатам сравнительного анализа выявлены следующие недостатки:

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

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

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

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

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

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

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

Функциональная зависимость множеств множества и, С,Б представляется в виде системы (3). Введены дополнительные функции, отражающие ограничения и критерии эффективности для зоны покрытия: / - вычисляет С с: II с учётом ограничений и выбранных критериев эффективности; <р - вычисляет

элементы подмножества Щ уг - вычисляет подмножество г/Д{//+/; -вычисляет модуль вектора в координатах Г/.

ЬГ = 1>Л

1=1

СсУ^с^;

иеи,се С, I е с е и,х е II, е

V*/

Дополнительные функции выражаются через исходные переменные:

ср (и, :и.р(х,у,г)ми))\

После чего искомые множества Ся Б записываются в виде системы

. Ф)

Для вычисления вхождения элемента и во множество у/(Ц) с параметрами Л и р(х,удля всех элементов

у^и) вводится функция

Система уравнений (5) тогда приобретает вид:

С = {и:/[?Ы)]}; (6)

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

В работе предложен также алгоритм построения зоны покрытия БПШС по принципу нахождения точек множества с максимальным числом соседних точек. Определяются значения переменных:

- при решении открывать станцию в точке с и подсоединить к ней клиента

- при решении не соединять клиента г и станцию с: (х^у^0.

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

Таким образом, необходимо найти такой набор (х,у), при котором получается

(8)

при условиях:

(9)

определяет соединение каждого клиента с одной станцией;

(х, - х/ + (у,-у$<?, (У/,с) (10)

ограничивает расстояние от клиента к станции, к которой он подсоединен. Основные шаги алгоритма:

• шаг 1: создается набор множеств /5/..., 8п};

• шаг 2: находятся все клиенты с частотой 1:

• шагЗ: открываются соответствующие станции

{(хсЛ)еС|Ос ~хе)2 +(ус -у$)2 <г2}.

к которым подключаются все клиенты в зоне покрытия.

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

Работа модели показана на примере: Случайным образом задаются координаты 100 точек на плоскости векторами а и Ь. Для радиуса 50 центрами будет четыре точки.

pok(x,y,r) lit- length(x)

for i e 0.. n - 1

d <-0 l

for j e 0.. n - 1 dj d; + ! if i «j л |х( - x^ + (yi - У])" S r2 k t-0

while max(d) > 0 \ n > 1 for i e 0.. n - 1 s <- i if = max(d)

Далее рассматривается модель pok_og(x,y,r,C) с условием, при котором станции имеют разные мощности (разные радиусы покрытия станций). Для их построения сначала находятся центры большего радиуса, а затем, если остались не покрытые точки на множестве - центры меньшего радиуса.

Для этого в предыдущую модель вводится параметр Q, который

ограничивает сверху количество покрывающих центров радиуса г: ¿gi<g

1

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

у

• • • А<1

pok(X,Y,50)i 60

О

I ® .. • • * •

* *

®

I I I_L_

20 40 60 80

X,p<lk(X,Y,50)o

100 120

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

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

Работа каждой модели в диссертационной работе продемонстрирована на нескольких примерах.

Во второй главе предложены алгоритмы построения зоны покрытия БПШС на плоскости, основанные на понятии диаметра множества. Центры выбираются так, чтобы диаметр непокрытого множества уменьшался. Когда диаметр становится не больше двух радиусов, процесс прекращается. Последний покрывающий центр будет находиться ровно посредине диаметра множества и может не совпасть с точкой множества, как все предыдущие центры. Ранее при выборе центров не было критериев, позволяющих поместить их вне точек множества, а для последнего центра он появился. Основные шаги алгоритма: • шаг 1: создается множество

к которым подключаются все клиенты в зоне покрытия.

Модели, реализующие алгоритм построения зоны покрытия БПШС, основанный на понятии диаметра множества, приведены в пункте 2.5.1. Модель 1й(х,у) находит диаметр множества, заданного векторами координат х и у, и все его диаметральные точки. После нахождения диаметра множества, модель рок<1(х,у,г) находит точки центра окружностей согласно нашему алгоритму.

Далее рассматривается модель рок«1(х,у,г,А) с условие ограничения диаметра множества. Установлено, что первый алгоритм более универсальный, чем второй. Он позволяет реализовать все ограничения при решении задачи покрытия множества. Второй алгоритм более быстродействующий и даёт более равномерное распределение точек между центрами.

• шаг 2: находятся все клиенты с частотой 1:

в=1х„у,)е8\}г{х„у,)=\\,

• шагЗ: открываются соответствующие станции

I'

(*еЛЫ-х,)2 +(ус-у,)1*4г2

\{хс,усЫМ;

роЫ(х. у. г) := п-*— 1пщ11(х)

рокЦ(х,у.г ,А) п 1стч1Ь(х)

с<-0

5> 2глп> I

с О

« *- ч«(х,у)0

и<-Р1

к<-1сп^и) !■*—1с — 1

¡е О..Д- 1 £ог

»Пае (>2глп>| Р

ц-р,

V *-р,

1с «Гот 1 е 0.. п - 1 вж ] е 0.. I

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

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

Введены переменные:

- при решении открывать станцию в точке с и подсоединить к ней клиента

(ХюУю^с)

- при решении не соединять клиента / и станцию с: (хк,ук,г!су=0.

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

Таким образом, необходимо найти такой набор (х,у,г), при котором достигается

(П)

при ограничениях:

определяет соединение каждого клиента с одной станцией;

+ (И)

ограничивает расстояние от клиента к станции, к которой он подсоединен.

Основные шаги алгоритма:

• шаг 1: создается набор множеств {Б] ..., 8п};

• шаг 2: находятся все клиенты с частотой 1:

• шаг 3: открываются соответствующие станции

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

Приведено описание двух разработанных моделей построения зоны покрытия БПП1С, реализующие первый алгоритм. Первая модель расЗ_оЬ(х,у,е,г,2Д,Ь) реализует алгоритм при одинаковом радиусе покрытия станций. Каждое решение относительно подключения клиента или определения клиента в качестве станции является окончательным, при этом эти клиенты и станции исключаются из соответствующих множеств и не принимают участия в последующих расчетах.

расЗ_оЬ(х.У,е>г>2,1>Ь) :=

п <~ 1еп$Кх) &г ¡е0..п- 1

= (7 36196482 8)

—1

Ь = (9 6 3 5 1 9 6 7 3 7)

йПсеО..]*® СТ=(8 4 5 9 з ! 2 8 з 6) -к

йг jeO..п- 1

¡5 (г;-х^2+(1;-уд)2+(14-е;)2 < г2 Л с

расЗ_оЬ(а,Ь,с,5,2,Т,Ц) =

сг 1! г 3 4! в" 7' 'в 9

0 1 0 а г 0 3 3 1 а 1

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

£g,<<2 • Если для покрытия множества хватило сфер или даже меньшего

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

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

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

Основные шага алгоритма:

• шаг 1: создается множество

£>=- х,)2 + (у. - у,)2+(& - л)2 < г2

• шаг 2: находятся все клиенты с частотой 1:

<5 = {(*«,>>„ г,) е5| И(х„у„ г,)=11;

• шагЗ: открываются соответствующие станции

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

Приведено описание моделей, реализующих алгоритм построения зоны покрытия БПШС в пространстве, основан на понятии диаметра множества. Модель Ю(лг,у,2) находит диаметр множества, заданного векторами координат х, у и 2, и все его диаметральные точки.

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

:ю

tD(x,y,z) '■= о ч- lengti(x)

tD(a,b,c)T = 10.77

for ie0..n-2 for js i+ 1..П- 1

pt (ч - + (я - yj)2 + (ч - ч)2 k<-k+ 1 0

Третье условие состоит в том, что между точками могут быть различные препятствия, что влияет на качество беспроводной связи между ними; для учета этого в модель pok3m(x,y,e,r,m) вводится дополнительный параметр т соответствующий качеству сигнала между двумя точками.

Ek е; 1 := О.. 9 j := 0.. 9 A;j := rad(l)

к<-к+ I

2 t

Е

\COj

pok3m(a,b,c,5,M)

f8> f?> V i9>

3 6 4 1

9 1 3 4

1 5 9 3

J,

и := рокЗш(а,Ь,с,5,М)

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

pokcXx.y.t.cb.r) :=

n*-Iengfl(i) nc+-ltngth(cb) for ie0..n-l

for ie0..nc-l

for ie0..nc-I di+-0

for J€0..D-1

pokpr(x ,y, с, cb, r) :=

rH-lragtf^x) nc ■«- lengfl(cb) for ie 0..n- 1

dcj 0 for ie0..nc- 1

p <—0

v*-0

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

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

В четвертой главе диссертации проводится реализация алгоритмов на примере проектирования зоны покрытия БПШС офиса компании ОАО СК «Альянс». Беспроводная сеть офиса в компании должна обеспечить подключение абопентов к voip-серверу, обеспечить передачу голосовой и видеоинформации. План помещения офиса компании представлен на рис.1. Беспроводная сеть должна отвечать следующим требованиям:

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

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

- Беспроводное подключение должно удовлетворять промышленным стандартам 802.11Ь и 802.1 lg.

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

Зоны покрытия точек должны полностью покрывать площадь офисного помещения.

В табл. 1 показано изменение мощности сигнала в децибелах при перемещении между комнатами.

#габ. 1 2 3 4 5

1 40dBm -74dBm -80dBm -69dBm -83dBm

2 -72dBm -40dBm -72dBm -78dBm -74dBm

3 -72dBm -64dBm -40dBm -78 (fi m -64dBm

4 -69dBm -78dBm -82dBm -40dBm -78dBm

5 -80dBm -72dBm -61dBm -74dBm -40dBm

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

#каб. 1 2 3 4 5

1 80% 35% 25% 45% 15%

2 40% 80% 40% 30% 35%

3 40% 50% 80% 30% 50%

4 45% 30% 20% 80% 30%

5 25% 40% 55% 35% 80%

В табл. 3 рассчитано отношения сигнал/шум - безразмерная величина, равная отношению мощности полезного сигнала к мощности шума.

SNR 1 2 3 4 5

1 76 55 45 51 31

2 59 78 54 36 48

3 46 58 78 40 50

4 50 43 33 80 ЗЭ

5 37 40 60 43 80

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

Рис.1. План размещение точек доступа Рис.2. Трехмерная зона покрытия в офисе компании беспроводной сети.

По итогам моделирования установлено:

- в офисе компании ОАО СК «Альянс» следует установить пять точек доступа;

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

В найденных точках размещаются беспроводные маршрутизаторы Asus WL500g Premium.

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

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

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

Развернутая беспроводная сеть обеспечивает обмен данными через Б1Р-протокол между клиентами и сервером (аудио- и видео потоки); гарантированную работу устройств в сети в любой точки зоны покрытия офиса компании ОАО СК «Альянс»; обеспечивает требуемую пропускную способность между клиентами и сервером; реализует беспрепятственный обмен данным между сетевыми пользователями; обладает надежностью, безопасностью и конфиденциальностью передачи данных;

Общие выводы

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

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

2. Разработаны алгоритмы для решения задач размещения объектов сетей в в зоне активности сети.

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

4. Реализован комплекс программно-аппаратных средств, который был использован для проведения работ по проектированию зоны покрытия БПШС ОАО СК «Альянс».

5. Результаты диссертационной работы использованы в учебном процессе кафедры «Вычислительных систем и сетей» МИЭМ в курсах «Новые информационные технологии» и «Беспроводные сети и мобильные системы».

Основные публикации по теме диссертации.

1. Косилов Н.А., Андронов А.В., Меркулов А.М., Петриков И.А., Проектирование беспроводной сети с заданным качеством обслуживания // журнал «Качество. Инновации. Образование», вып. 82,2012.

2. Косилов Н.А., Проферансов Д.Ю. Оценка пропускной способности узла коммутации // журнал «Качество. Инновации. Образование», вып. 82,2012.

3. Kosilov N.A., Zhdanov V.S. Churkov V.M., «Optimization of spatial models wireless sensor network» // В сб. докладов международной научн. конференции «Information and telecommunication technologies in intelligent systems», Schweiz July 03-09,2010, p. 8-12.

4. Kosilov N.A. «Applications and challenges of designing sensory networks clustered» // В сб. трудов международной научи, конференции «Information and Telecommunication Technologies in Intelligent Systems», Schweiz, July 03-09, 2010, p. 15-18.

5. Косилов H.A.«Оптимизация пространственной модели беспроводной сенсорной сети» // В сб. трудов международной конференции «Distributed Computer and Communication Netwotks», Moscow- 2010, c.268-270.

6. Kosilov N.A. «Simulation cluster network" // В сб. докладов международной научн. конференции «Information and Telecommunication Technologies in Intelligent Systems», Schweiz July 03-09,2010, p.21-23.

Подписано в печать 21.03.2012 г. Формат 60x90 1/16 Печать на ризографе. Тираж 100 экз. Заказ № 7371. Объем: 1,0 усл. пл.

Отпечатано в типографии ООО "Алфавит 2000", ИНН: 7718532212, г. Москва, ул. Маросейка, д. 6/8, стр. 1, х 623-08-10, www.alfiivit2000.ru

61 12-5/3563

Московский государственный институт электроники и математики

(Технический Университет)

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

КОСИЛОВ Никита Александрович

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

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

Диссертации на соискание ученой степени кандидата технических наук

Научный руководитель Доктор технических наук профессор, Жданов Владимир Сергеевич

Москва 2012

ОГЛАВЛЕНИЕ

Оглавление...............................................................................................................2

ВЕДЕНИЕ.................................................................................................................4

ГЛАВА 1. Способы построения беспроводных широкополосных сетей........10

Организация беспроводных широкополосных сетей................ ........................10

Классификация беспроводных технологий........................................................14

Зона покрытия беспроводных широкополосных сетей............... ......................16

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

сетей........................................................................................................................22

Методы планирования зоны покрытия беспроводных широкополосных

сетей........................................................................................................................24

Модели пространственной организации беспроводных широкополосных

сетей........................................................................................................................26

Выводы по главе....................................................................................................29

ГЛАВА 2. Построение моделей и алгоритмов проектирования зоны покрытия беспроводных широкополосных сетей на плоскости........................................31

2.1. Постановка задачи моделирования зоны покрытия на плоскости............31

2.2. Решение задачи моделирования зоны покрытия на плоскости.................31

2.3. Разработка математической модели пространственной организации беспроводных широкополосных сетей................................................................32

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

соседних точек.......................................................................................................35

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

2.5. Алгоритм построения зоны покрытия беспроводных широкополосных

сетей основанный на понятии диаметра множества..........................................51

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

широкополосных сетей основанный на понятии диаметра множества...........52

Выводы по главе....................................................................................................62

ГЛАВА 3. разработка моделей и алгоритмов пространственной организации беспроводных широкополосных сетей................................................................63

3.1. Постановка задачи моделирования зоны покрытия в пространстве.........63

3.2. Решение задачи моделирования зоны покрытия в пространстве..............63

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

соседних точек.......................................................................................................64

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

3.4. Алгоритм построения зоны покрытия беспроводных широкополосных

сетей основанный на понятии диаметра множества..........................................75

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

широкополосных сетей основанный на понятии диаметра множества...........75

Выводы по главе..................................................................................................104

ГЛАВА 4. организация зоны покрытия беспроводных широкополосных сетей

офиса страховой компании.................................................................................

Проектирование зоны покрытия........................................................................105

Выводы по главе..................................................................................................117

ЗАКЛЮЧЕНИЕ....................................................................................................П8

ЛИТЕРАТУРА.....................................................................................................120

ПРИЛОЖЕНИЯ.................................................................................................133

ВЕДЕНИЕ

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

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

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

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

Проблемам проектирования зоны покрытия беспроводных широкополосных сетей посвящено значительное количество работ, среди которых следует отметить работы российских и зарубежных ученых: В. М. Вишневского, С. Портного, И. Шахновича, G. Balbo, S. С. Bruell, L. Fratta, L. Kleinrock, M. Olivetty, H. Takagi, S.C. Borst, O.J. Boxma и др.

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

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

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

Объектом исследования является беспроводные широкополосные сети.

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

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

Задачи исследований

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

1. Анализ способов организации беспроводных широкополосных сетей, методов и моделей проектирования зоны покрытия беспроводной широкополосной сети.

2. Исследование зоны покрытия беспроводной широкополосной сети, ее основных свойств и параметров.

3. Разработка комплекса математических моделей и алгоритмов пространственной организации беспроводных широкополосных сетей.

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

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

На защиту выносятся следующие основные результаты:

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

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

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

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

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

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

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

Результаты диссертационной работы использованы в учебном процессе кафедры «Вычислительных систем и сетей» МИЭМ при изучении дисциплин на курсах «Новые информационные технологии», «Беспроводные сети и

мобильные системы».

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

Апробация диссертационной работы

Положения данной диссертации докладывались и обсуждались на следующих конференциях:

• на международных научно-технических конференциях «Information and Telecommunication Technologies in Intelligent Systems» (Швейцария, 2010 г);

• на 14-ой Международной конференции «Распределенные компьютерные и телекоммуникационные сети: теория и приложения» (DCCN-2010);

• на научно-методических совещаниях и семинарах ОАО «Альянс»;

• на научно-технических конференциях студентов, аспирантов и молодых специалистов МИЭМ (2008 - 2011 гг.);

• на научно-технических семинарах кафедры «Вычислительные системы и сети» МИЭМ (2008 - 2011 гг.).

Публикации

Основное содержание диссертационной работы и ее результатов отражено в научных и научно-технических работах автора.

Всего автором опубликовано 8 научных работ из них 2 в журналах из перечня ВАК:

1. Косилов Н.А., Андронов А.В., Меркулов A.M., Петриков И.А., Проектирование беспроводной сети с заданным качеством обслуживания // журнал «Качество. Инновации. Образование», вып. 82, 2012.

2. Косилов Н.А., Проферансов Д.Ю. Оценка пропускной способности узла коммутации // журнал «Качество. Инновации. Образование», вып. 82, 2012.

3. Kosilov N.A., Zhdanov V.S. Churkov V.M., «Optimization of spatial models wireless sensor network» // В сб. докладов международной научн. конференции «Information and telecommunication technologies in intelligent systems», Schweiz July 03-09, 2010, p. 8-12.

4. Kosilov N.A. «Applications and challenges of designing sensory networks clustered» // В сб. трудов международной научн. конференции «Information and Telecommunication Technologies in Intelligent Systems», Schweiz, July 03-09, 2010, p.15-18.

5. Косилов Н.А.«Оптимизация пространственной модели беспроводной сенсорной сети» // В сб. трудов международной конференции «Distributed Computer and Communication Networks», Moscow- 2010, c.268-270.

6. Kosilov N.A. «Simulation cluster network" // В сб. докладов международной научн. конференции «Information and Telecommunication Technologies in Intelligent Systems», Schweiz July 03-09, 2010, p.21-23.

7. Косилов H.A., Выбор платформы разработки бестпроводных сенсорных сетей // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, 2010.

8. Косилов H.A., Области применения и задачи проектирования сенсорных сетей с кластерной структурой // Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, 2011.

Структура и объем работы. Диссертационная работа состоит из

введения, четырех глав, заключения, списка использованных источников. Работа изложена на «134» страницах, содержит «6» иллюстраций, «3» таблицы.

ГЛАВА 1. СПОСОБЫ ПОСТРОЕНИЯ БЕСПРОВОДНЫХ ШИРОКОПОЛОСНЫХ СЕТЕЙ

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

Для построения широкополосных сетей в настоящие время все чаще используются беспроводные каналы доступа[38].

Беспроводные широкополосные сети (БПШС) передачи данных позволяют объединить в единую информационную систему разрозненные локальные сети и компьютеры для обеспечения доступа всех пользователей этих сетей к единым информационным ресурсам без прокладки дополнительных проводных линий связи. БПШС обычно создаются в тех случаях, когда прокладка кабельной системы затруднена или экономически нецелесообразна. Примером могут служить предприятия, имеющие распределенную структуру (складские помещения, отдельные цеха, карьеры и пр.), наличие естественных преград при построении кабельных систем (рек, озер и т.д.), предприятия, арендующие офисы на небольшой срок, выставочные комплексы и гостиницы, предоставляющие доступ в Интернет для своих клиентов. Беспроводные сети уменьшают затраты на планирование и подготовку рабочего пространства, а также обновление оборудования и периферии [5],[13-17],[71-78].

Организация беспроводных широкополосных сетей

Инфраструктура

Инфраструктура беспроводной сети обеспечивает беспроводное взаимодействие пользователей и оконечных систем. Ее могут образовывать

базовые станции, контроллеры доступа, программное обеспечение приложений, обеспечивающих установление соединений, и распределительная система. Эти компоненты участвуют в беспроводной связи и выполняют важные функции в конкретных применениях[ 10-12],[143].

Базовая станция — распространенный компонент инфраструктуры. Она обеспечивает передачу информационных сигналов беспроводных сетей, распространяющихся через воздушную среду, в проводную сеть, ее иногда называют распределительной системой [23],[25],[31],[33],[110].

Название базовой станции зависит от выполняемых ею функций. Например, точка доступа (access point) — это основная базовая станция беспроводных локальных сетей. Шлюзы и маршрутизаторы локальной сети — это примеры базовых станций с расширенными возможностями, обеспечивающих выполнение дополнительных функций в сети [59],[70].

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

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