исследований.
Провести исследование сети на предмет наличия в ней изолированных
групп узлов и мостов.
Проанализировать возможность восстановления полной структуры
сети (в случае, если изолированные группы узлов присутствуют).
Организовать параллельное исполнение программы, используя
возможности стандарта С++ 11.
Оценить полученный прирост производительности.
2.2 Проектирование.
В качестве языка реализации программы выбран язык C++.
С++ – язык общего назначения. За исключением, может быть,
некоторых деталей, он целиком содержит в себе язык С. Язык С++
расширяется введением средств, предназначенных для гибкого создания
необходимых типов. Программист получает возможность доопределять
свою задачу, определив новые типы, которые наиболее точно соответствуют
его задаче. Такой подход к построению программных продуктов принято
называть абстракцией данных. Информация о типах содержится в некоторых
объектах типов, определенных пользователем. Если этот подход применяется
10
правильно, то код программы становится короче и понятнее, а дальнейшее
сопровождение программного продукта упрощается.
Ключевым понятием С++ является класс. Класс - это определяемый
пользователем тип.
Классы обеспечивают удобную работу с данными пользователя:
создание интерфейсов (дающих пользователю необходимые методы доступа
и работы с данными – и не более), инициализацию определенными
начальными значениями, возможность перегрузки операций, механизмы
контроля распределения памяти.
Язык и стандартные библиотеки С++ разрабатывались с расчетом на
переносимость. Имеющиеся реализации языка С++ будут работать в
большинстве систем, поддерживающих С. В программах на С++ можно
использовать библиотеки С.
С был выбран как основа для С++ по нескольким причинам. Среди них:
универсальность, краткость; соответствие большинству задач,
заключающихся в написании системного программного обеспечения;
переносимость программных продуктов (4).
2.3 Стандарт С++ 11.
Введение стандарта С++ 11 расширяет возможности программиста в
многопоточном программировании. Работать с потоками можно как
вручную, используя std::thread (управляя запуском, числом потоков,
параметрами ожидания), так и с помощью вызова функции через
std::async. Функция, вызванная вторым способом, может быть запущена
в отдельном потоке (при необходимости).
Число одновременно работающих потоков программы задается
пользователем, учитываю проверку на корректность – не более, чем число
ядер в системе. Иначе произойдет существенный спад производительности
вследствие повышения накладных расходов на избыточное контекстное
переключение ядер процессора.
11
Стандарт С++ 11 предоставляет 4 вида мьютексов:
(необходимо подключение #include <mutex> )
· mutex — повторный захват одним и тем же потоком не
контролируется
· recursive_mutex — повторные захваты тем же потоком допустимы,
каждый такой захват учитывается счетчиком
· timed_mutex — нет контроля повторного захвата тем же потоком,
поддерживается захват мьютекса с тайм-аутом;
· recursive_timed_mutex — повторные захваты тем же потоком
допустимы, ведётся счётчик таких захватов, поддерживается захват
мьютекса с тайм-аутом.
Сбор результирующих данных программой производится в глобальную
структуру MyRes, представляющую собой вектор результирующих строк.
Запись в структуру не вызывает взаимоблокировок потоков вследствие того,
что запускаемые одновременно потоки гарантированно не завершатся
одновременно (если не произойдет ошибки, в этом случае поток завершится
без обращения к структуре) – соответственно, каждый поток к моменту
завершения получает доступ к незаблокированной структуре MyRes без
необходимости согласовывать свой доступ с другими потоками и дожидаться
ее разблокировки. Таким образом, отпадает необходимость использовать
механизм мьютексов-семафоров для синхронизации потоков, и, тем более –
писать собственный мьютекс.
2.4 Модель.
Пусть есть граф G=(V, E).
Информация о сети генерируется как набор вершин ∈
объектов
класса node (приложение А), имеющих координаты расположения на
плоскости xu, yu и радиус приема/передачи радиосигнала rangeu.
12
По этому набору программой вычисляется множество E ребер,
соединяющих пары вершин графа.
Ребро между u и v определяется, как возможность узлов обмениваться
информацией без участия дополнительных передатчиков. Для этого оба узла
должны находиться в зоне радиовидимости друг друга, т. е. расстояние
( − )+ ( − ) должно быть меньше, чем rangeu и rangev.
Сформулируем условие окончательно:
Ребро e(u, v) добавляется в граф G тогда и только тогда, когда
( − )+ ( − ) < min, ∈(‑,‑)
Узлы сети заданы вектором объектов класса node (приложение А).
Проведя анализ расстояний, получим список смежности графа.
Таким образом, получаем граф G=(V, E), являющийся моделью
структуры данной сети. В программе представлен объектом класса grafe
(приложение Б)
Недостаток такой модели заключается в том, что при высокой степени
связности графа (на практике это может выражаться в большом скоплении
узлов сети в пределах прямой видимости. Схема связей в этом случае
стремится к «каждый к каждому») алгоритм поиска мостов, основанный на
рекурсивном обходе, вызовет переполнение стека вызовов. Однако, в
современных условиях вероятность наступления такой ситуации очень мала
(т. к. потребуется собрать свыше 30000 устройств внутри круга радиуса r ≤
100 м., препятствий обмену радиосигналом между устройствами быть не
должно).
Алгоритмы.
Для поиска связных компонент используется итеративная форма
обхода графа в глубину.
Описание алгоритма итеративного обхода в глубину:
Пусть вершины графа перенумерованы i=1…n, n – общее число
вершин.
13
Поиск компонент связности.
Для нахождения всех групп изолированных узлов сети,
представленных компонентами связности в графовой модели, необходимо
обойти граф в глубину. Каждый обход из непосещенной вершины графа
будет возвращать множество вершин, находящихся в одной компоненте
связности со стартовой вершиной. Если таковая компонента одна, то граф
является связным, изолированных узлов в сети нет. Иначе в векторе
Components после завершения просмотра графа получим номера компонент
связности и список вершин, входящих в каждую компоненту.
Поскольку обходятся все ребра графа, временная оценка алгоритма
О(|V|+|E|).
Компоненты связности представлены в классе grafe полем vector<vector
<int>> Components.
Сведения о восстановлении структуры хранятся в виде расстояний
между парами компонент UCi, UCj; , = 1$$$,$#$ , k – число компонент.
На рисунке 3. изображен граф G сети с 6 узлами. Узлы 4 и 5 находятся
в одной компоненте связности, остальные узлы изолированы (находятся в
компонентах связности, состоящих из 1 узла).
14
Рисунок 3 – Пример графа ad hoc сети.
Поскольку для установки связи со всеми узлами компоненты UCi
достаточно установить связь хотя бы с одним ее узлом, то представим группу
узлов, входящих в компоненту UCi, как один узел ACi, имеющий
характеристики, средние по всем узлам компоненты UCi:
%&' =()
*+
,-
.' (1)
%&' =()
*+
,-
.' (2)
‑%&' =(‑)
*+
,-
.' (3)
Где ni – число вершин в i-й компоненте.
Для показанного на рис. 6. Графа после преобразования получим вид,
изображенный на рисунке 7 , некоторые компоненты перенумерованы для
удобства.
15
Рисунок 4 – Граф ad hoc сети после преобразования компоненты
связности.
Эти данные хранятся в векторе объектов класса
T_Averaged_Components (приложение В).
Поиск мостов.
Из определения моста, приведенного выше, следует, что ребра (u, v),
являющиеся мостами в данной сетевой модели, имеют в ней особое значение.
Соответственно, таким участкам следует уделить внимание в виде
повышения их надежности (усиление аппаратуры конкретных узлов,
соединенных мостом), либо добавления дополнительных мостов,
связывающих сегменты, содержащие u и v для снижения вероятности
разрыва структуры сети в случае выхода из строя моста (u, v).
Для того чтобы найти мосты в графе, необходимо для каждого ребра:
А) Удалить его из графа.
Б) Проверить, не увеличилось ли число компонент связности
16
В) Если увеличилось – добавляем это ребро в вектор, хранящий
информацию о мостах.
Информация о найденных мостах хранится в grafe::Bridges – векторе
объектов класса T_Bridges (приложение Г).
Координаты и область радиовидимости узла (x, y, range) задаются
псевдослучайными числами и ограничены диапазонами: ∈ 10,1003, ∈
10,1003,‑ ∈ 10,1003 . Псевдослучайное задание величины range
имитирует влияние препятствий на прохождение радиосигнала между
узлами.
Для выяснения зависимости появления мостов в сети от плотности
расположения узлов, расположенных на фиксированной площади, были
проведены серии из 50 тестов на графовых моделях сетей случайного
построения из 500, 1500, 4500 и 13500 узлов.
Обозначим среднее число мостов B(N), среднее время поиска мостов
T(N), время, затраченное на поиск одного моста T1(N). N – число вершин в
тестируемом графе.
Результаты тестирования представлены в таблице 2.
Таблица 2.
Результаты оценки величин B(N), T(N), T1(N) для проведенных серий
испытаний.
N = 500 N = 1500 N = 4500 N = 13500
B(N) 6 13 26 48
T(N), мс. 0,96 4,3 38 339
T1(N), мс. 0,16 0,33 1,46 7,06
Более наглядно итоги показаны на рисунках 5 и 6.
17
Рисунок 5 – Итоговый график, показывающий изменение среднего
количества мостов при увеличении плотности размещения узлов в сети.
Рисунок 6 – Итоговый график, показывающий изменение времени,
затраченного на поиск одного моста при увеличении плотности размещения
узлов в сети.
Видно, что с ростом количества узлов в сети, при фиксированной
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
