Исследование вершинной и рёберной связностей графов мобильных сетей при различных стратегиях перемещения узлов (стр. 1 )

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

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

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

(ФГБОУ ВПО ‹‹КубГУ››)

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

ИССЛЕДОВАНИЕ ВЕРШИННОЙ И РЁБЕРНОЙ СВЯЗНОСТЕЙ ГРАФОВ МОБИЛЬНЫХ СЕТЕЙ ПРИ РАЗЛИЧНЫХ СТРАТЕГИЯХ ПЕРЕМЕЩЕНИЯ УЗЛОВ

А. Адамов

Краснодар 2014

СОДЕРЖАНИЕ

Введение        3

Представление графов в программе        5 Описание процесса генерации графа        7 Основные алгоритмы        9

3.1  Алгоритм проверки связности графа        9

3.2  Алгоритм вычисления рёберной связности графа        10

3.3  Алгоритм вычисления вершинной связности графа        12

Стратегии изменения графа        14 Исследования        16

5.1  Исследование 1        16

5.2  Исследование 2        25

5.3  Исследование 3        34

Заключение        42

Список использованных источников        43

сходный код программы        44

ВВЕДЕНИЕ

Одной из перспективных современных технологий передачи данных являются беспроводные сети типа «ad hoc». Отличительной особенностью беспроводных сетей ad hoc (от лат. ad hoc — «по месту»), или самоорганизующихся динамических сетей является то, что узлы сети соединяются «на лету». Если при этом сеть является телекоммуникационной, то есть предназначенной для передачи данных на значительные расстояния, превосходящие радиус действия используемых приемопередающих устройств, то для передачи данных необходимо использовать принцип «возьми и передай дальше».

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

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

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

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

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

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

Рисунок 1 – Пример структуры ad hoc сети

1. ПРЕДСТАВЛЕНИЕ ГРАФОВ В ПРОГРАММЕ

Топология самоорганизующихся ad hoc сетей, согласно наиболее общей модели, представляется в виде графа G = (V, U) , где V – множество узлов, а U – множество ребер. При переходе заданной топологии из состояния n в состояние n +1 равновероятно появление любого графа G` = (V`, U`) из множества возможных графов, которые можно получить из комбинации доступных узлов и ребер [1].

Для построения графа модели самоорганизующейся ad hoc сети будем использовать двунаправленные динамические списки следующих структур:

а) Дескриптор графа

б) Вершины

в) Дуги

г) Входы

д) Выходы

е) Вспомогательные структуры:

       1) Вспомогательный элемент для дуги

       2) Вспомогательный элемент для входа

       3) Вспомогательный элемент для выхода

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

В качестве наглядного примера рассмотрим то, как в программе представляется граф G из двух вершин, соединённых одной дугой. Этот пример представлен на рисунках 2 и 3.

Рисунок 2 – Графическое представление графа G

Рисунок 3 – Представление графа G в программе

2. ОПИСАНИЕ ПРОЦЕССА ГЕНЕРАЦИИ ГРАФА

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

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

Начальные векторы скорости всех вершин графа равны по длине, но получают случайные направления, равномерно распределённые в пределах от 0 до 360 градусов.

Радиусы радиовидимости всех вершин при этом имеют одинаковые значения равные 1.

Генерация осуществляется вызовом процедуры create_graph(N, R, S). Параметрами этой процедуры являются число вершин графа – N, радиус генерации для координат вершин графа – R и длина вектора скорости для каждого узла графа – S.

Вызов процедуры create_graph(N, R, S) порождает вызовы вспомогательных процедур create_node(), create_arc(), create_input() и create_output(). Эти процедуры предназначены для создания узлов, дуг, входов и выходов графа соответственно.

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

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

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

3. ОСНОВНЫЕ АЛГОРИТМЫ

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

3.1. Алгоритм проверки связности графа

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

На вход алгоритма подаётся заданный граф и стартовая вершина s. Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д. Если исходный граф связный, то поиск в ширину пометит все его вершины [2].

Поиск в ширину реализуется с помощью структуры данных очередь. Создадим очередь q и массив used[] для хранения меток посещённых вершин.

Изначально в очередь помещается только стартовая вершина s и used[s] = 1. Для всех остальных вершин used[i] = 0. Затем алгоритм представляет собой цикл: пока очередь не пуста, достать из её головы одну вершину, просмотреть все рёбра, исходящие из этой вершины, и если какие-то из смежных вершин ещё не помечены, то пометить их и поместить в конец очереди.

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

Рисунок 4 – Пример связного графа

3.2. Алгоритм вычисления рёберной связности графа

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

Рёберной связностью графа G называется наименьшее количество рёбер, удаление которых приводит к несвязному или тривиальному графу. Рёберная связность несвязного графа равна 0 [3].

Для нахождения количества непересекающихся путей из s в t используется алгоритмом нахождения максимального потока.

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

Псевдокод алгоритма таков:

               ans = INF

               for s :