Материал: Организация базы данных для хранения динамических моделей беспроводных компьютерных Ad hoc сетей

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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

(ФГБОУ ВПО «КубГУ»)

Кафедра вычислительных технологий

ВЫПУСКНАЯ КВАЛИФИКАЦИОННАЯ

РАБОТА БАКАЛАВРА

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

Работу выполнила

А.А. Памбукян

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

к. ф.-м. н. О.Н. Лапина

Краснодар 2015

ВВЕДЕНИЕ

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

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

1. Графы

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

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

.1 Обыкновенные графы

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

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

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

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

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

Обыкновенным графом называется пара G = (V,E), где V - конечное множество, E - множество неупорядоченных пар различных элементов из V. Элементы множества V являются вершинами графа, элементы множества E - его ребрами.

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

Если множество V конечно, то граф G тоже считается конечным. Конечный граф удобно задавать с помощью квадратной матрицы смежностей M. При этом вершины во множестве V нумеруются от 1 до p = |V|. Вершине с номером i в матрице M соответствуют i-я строка и i-й столбец. Если в графе имеется дуга (vi, vj), то в матрице смежностей этого графа имеется единица на пересечении i-й строки и j-го столбца. Если дуга отсутствует, то в соответствующей позиции матрицы находится ноль. Одному и тому же графу могут соответствовать различные матрицы смежностей, так как вид матрицы, зависит от нумерации вершин графа.

1.2 Геометрические графы

В качестве вершин графа G будем рассматривать элементы некоторого конечного множества V . Чтобы задать ребра, рассмотрим конечное множество E отрезков и некоторое отображение ∂ из множества концов этих отрезков в V. Необходимо отметить, что все отрезки предполагаются «независимыми», т.е. лежащими в разных прямых. Отображение ∂ можно интерпретировать как «приклеивание» ребер графа их концевыми точками к вершинам этого графа, в результате чего все отрезки из E склеиваются друг с другом некоторыми концевыми точками. Именно такое семейство ребер-отрезков с отождествленными в соответствии с отображением ∂ концами мы и будем называть геометрическим графом, см. рис. 1

Рисунок 1 - Склейка геометрического графа G из отрезков.

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

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

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

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

Рисунок 2 - Геометрические графы G1 и G2

2. Компьютерные сети

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

.1 Основные понятия

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

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

В сетях применяются различные сетевые технологии, из которых в локальных сетях наиболее распространены Ethernet, FDDI, Token Ring, 100VG-AnyLan. И каждой технологии соответствуют свои типы оборудования[3].

2.2 Беспроводные сети

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

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

Стандарт IEEE 802.11 <https://ru.wikipedia.org/wiki/IEEE_802.11>определяет два режима работы сети - Ad-hoc <https://ru.wikipedia.org/wiki/Ad-hoc> и клиент-сервер <https://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B8%D0%B5%D0%BD%D1%82-%D1%81%D0%B5%D1%80%D0%B2%D0%B5%D1%80>.

.2.1 Режим клиент-сервер

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

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

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

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

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

Рисунок 3 - Модель «клиент-сервер»

.2.2 Режим ad hoc hoc сети - децентрализованные беспроводные сети <https://ru.wikipedia.org/wiki/%D0%91%D0%B5%D1%81%D0%BF%D1%80%D0%BE%D0%B2%D0%BE%D0%B4%D0%BD%D1%8B%D0%B5_%D0%BA%D0%BE%D0%BC%D0%BF%D1%8C%D1%8E%D1%82%D0%B5%D1%80%D0%BD%D1%8B%D0%B5_%D1%81%D0%B5%D1%82%D0%B8>, не имеющие постоянной структуры. Клиентские устройства, соединяясь «на лету», образуют собой сеть. Каждый узел такой сети должен играть роль, как хоста, так и маршрутизатора, пытаясь переслать данные, предназначенные другим узлам. При этом определение того, какому узлу пересылать данные, производится динамически, на основании связности сети. Это является отличием от проводных сетей и управляемых беспроводных сетей, в которых задачу управления потоками данных выполняют маршрутизаторы <https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%80%D1%88%D1%80%D1%83%D1%82%D0%B8%D0%B7%D0%B0%D1%82%D0%BE%D1%80> или точки доступа <https://ru.wikipedia.org/wiki/%D0%91%D0%B5%D1%81%D0%BF%D1%80%D0%BE%D0%B2%D0%BE%D0%B4%D0%BD%D0%B0%D1%8F_%D1%82%D0%BE%D1%87%D0%BA%D0%B0_%D0%B4%D0%BE%D1%81%D1%82%D1%83%D0%BF%D0%B0> соответственно.hoc сети играют большую роль при необходимости выполнения масштабных работ в местностях с плохо развитой или разрушенной инфраструктурой. Такие сети создаются в период ликвидации чрезвычайных ситуаций, обеспечивая информационное взаимодействие участников операции. В связи с ограниченным радиусом действия приемо-передатчиков компьютерных узлов сети остро стоит вопрос обеспечения связности и живучести сети. Минимальным требованием является связность сети, т.е. наличие хотя бы одного маршрута передачи данных между двумя любыми узлами. Однако, ввиду мобильности узлов надежность односвязной сети недостаточна: в любой момент времени сеть может распасться на несколько компонент. Поэтому, достаточная живучесть сети обеспечивается только в многосвязной самоуправляемой сети [1].

Принципиальную схему ad hoc сети можно увидеть на рисунке 4.

Рисунок 4 - Схема беспроводной ad hoc сети

3. Математическая модель ad hoc сети

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

Характеристики связности беспроводной компьютерной сети зависят от координат узлов сети. Местоположение узлов изменяется со временем, поэтому для отслеживания динамики изменения и свойств компьютерной сети строится ее математическая модель, представляющая собой ранее упоминающийся в работе геометрический граф[1].

В соответствии с этой моделью, компьютерная сеть состоит из n отдельных узлов, каждому из которых соответствует вершина графа Si, i = 1..n. Структура узла включает в себя начальное местоположение, иными словами, координаты (x0,y0), в некоторый начальный момент времени t0 = 0,а также вектор скорости .

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

Рисунок 5 - Модель ad hoc сети

3.1 Моделирование поведения узлов ad hoc сети при равномерном движении на плоскости

Так как ad hoc сеть является динамической, то с течением времени местоположение некоторого узла Si меняется, при этом векторы скоростей постоянны, то есть не изменяется ни длина, ни направление. Изменение местоположения некоторого узла Si можно описать системой вида

 , (1)

где  - координаты некоторого узла Si в начальный момент времени t0,  = (ai, bi) - вектор скорости.

Требуется определить моменты изменения графа сети в некоторый временной промежуток [t0,T] и составить соответствующую последовательность t0…tk, , используя которую составляется соответствующая последовательность графов G0…Gk .

Представим компьютерную сеть соответствующим ей графом G = , где V - множество узлов Si, i = 1..n, E - множество ребер, то есть связей между узлами.