Рисунок 21 – График изменения среднего значения вершинной связности графа из 15 вершин
Рисунок 22 – График изменения среднего значения рёберной связности графа из 15 вершин
На представленных графиках видно, как уменьшаются значения вероятности связности графа, а также вершинной и рёберной связностей по мере уменьшения числа вершин в графе.
Увеличим число вершин графа до 20 и посмотрим, как изменятся графики.
Рисунок 23 – График зависимости вероятности связности графа из 20 вершин от времени
Рисунок 24 – График изменения среднего числа вершин графа из 20 вершин
Рисунок 25 – График изменения среднего числа рёбер графа из 20 вершин
Рисунок 26 – График изменения среднего значения вершинной связности графа из 20 вершин
Рисунок 27 – График изменения среднего значения рёберной связности графа из 20 вершин
Увеличим число вершин графа до 30, увеличим радиус генерации до 2,0, а так же увеличим время преобразования графа до 2,5, затем посмотрим, как изменятся графики.
Рисунок 28 – График зависимости вероятности связности графа из 30 вершин от времени
Рисунок 29 – График изменения среднего числа вершин графа из 30 вершин
Рисунок 30 – График изменения среднего числа рёбер графа из 30 вершин
Рисунок 31 – График изменения среднего значения вершинной связности графа из 30 вершин
Рисунок 32 – График изменения среднего значения рёберной связности графа из 30 вершин
Проанализировав эти графики, можно заметить, как возрастает вероятность связности графа при увеличении числа вершин и уменьшении радиуса генерации графа.
5.3. Исследование 3
Исследование 3 представляет собой анализ изменения графовых характеристик связности для случайных графов, состоящих из 20, 25, 35 вершин для третьей стратегии изменения графа.
Радиус генерации графа – R = 1,5. Длина вектора скорости каждой вершины равна 1. Движение вершин графа осуществляется, начиная с нулевого значения системного времени и заканчивая моментом 2,0. Шаг изменения переменной системного времени
dt = 0,1.
Для данной стратегии количество вершин n(t) в графе G(t) не изменяется с течением времени, но изменяется количество рёбер и другие характеристики.
Графики, построенные с помощью данных, полученных благодаря проведённым расчётам, представлены на рисунках 33 – 44.
Рисунок 33 – График зависимости вероятности связности графа из 20 вершин от времени
Рисунок 34 – График зависимости вероятности связности графа из 25 вершин от времени
Рисунок 35 – График зависимости вероятности связности графа из 35 вершин от времени
Анализ этих графиков показывает, что с увеличением числа вершин, также увеличивается вероятность связности графа. Наибольшего своего значения она достигает на начальных значениях времени изменения графа и постепенно уменьшается вследствие удаления вершин графа друг от друга.
Рисунок 36 – График изменения среднего числа рёбер графа из 20 вершин
Рисунок 37 – График изменения среднего числа рёбер графа из 25 вершин
Рисунок 38 – График изменения среднего числа рёбер графа из 35 вершин
Графики изменения среднего числа рёбер также представляют собой убывающие функции.
Рисунок 39 – График изменения среднего значения вершинной связности графа из 20 вершин
Рисунок 40 – График изменения среднего значения вершинной связности графа из 25 вершин
Рисунок 41 – График изменения среднего значения вершинной связности графа из 35 вершин
Рисунок 42 – График изменения среднего значения рёберной связности графа из 20 вершин
Рисунок 43 – График изменения среднего значения рёберной связности графа из 25 вершин
Рисунок 44 – График изменения среднего значения рёберной связности графа из 35 вершин
Результаты исследования 3 во многом похожи на результаты исследования 2. Для третьей стратегии изменения графа число вершин графа постоянно и отсутствуют какие-либо ограничения на движение вершин. Вершины не отражаются от границ и не исключаются из графа.
Тем не менее, построенные графики также представляют собой убывающие функции, схожие с графиками, представленными во втором тесте. Это обуславливается постоянным удалением вершин друг от друга, в результате которого между ними нарушаются связи. Поэтому мы можем наблюдать плавное уменьшение вероятности связности графа, а также средних значений вершинной и рёберной связностей.
ЗАКЛЮЧЕНИЕ
В курсовой работе дан краткий обзор беспроводных ad hoc сетей, рассмотрены основные особенности их организации и функционирования. Описаны основные используемые алгоритмы.
В работе описаны три стратегии изменения случайного графа G(t) c течением времени. На основе этих стратегий проведены исследования характеристик связности графа, построены графики, проведён их анализ.
В качестве языка программирования использовался язык C++.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
Современные технологии сетей типа ad hoc. 2010 http://cyberleninka. ru/article/n/sovremennye-tehnologii-setey-tipa-ad-hoc-i-vozmozhnye-podhody-k-organizatsii-odnorangovyh-telekommunikatsionnyh-setey-na-baze-mobilnyh (15.05.2014) ундаментальные алгоритмы на С++. Часть 5 Алгоритмы на графах.// ДиаСофт, – М.: – 2002. – 483 c. еория графов.// Едиториал УРСС, – М.: – 2003. – 297 с.
ПРИЛОЖЕНИЕ А.
ИСХОДНЫЙ КОД ПРОГРАММЫ
//main
#include <cstdlib>
#include <iostream>
#include <math. h>
#include <ctime>
#include <string>
#include "functions. h"
#include "structs_description. h"
#include "walk_through. h"
#include "delete_lists. h"
#include "check_graph. h"
#include "graph_copy. h"
#include <vector>
using namespace std;
int main(int argc, char** argv) {
graph *head_graph, *work_copy;
node *current_node;
double t, delta_t, max_t;
int coh_prob_id, nor_id, rib_coh_id, node_coh_id, non_id;
float rib_rel_status, node_rel_status;
long cycle_id;
cout << "Hello!" << endl;
//Движение вершин.
cout << " * Starting graph analysis..." << endl;
t = 0.0;
delta_t = 0.1;
max_t = 2.5;
// Число циклов.
cycle_id = 100000;
// Вектор вероятностей связности графа.
vector <float> coherence_probability(0);
coh_prob_id = 0;
// Вектор q(t) - количество рёбер в графе в момент t.
vector <float> number_of_ribs(0);
nor_id = 0;
// Вектор l(t) - изменение рёберной связности графа.
vector <float> rib_coherence(0);
rib_coh_id = 0;
rib_rel_status = 0;
// Вектор k(t) - изменение вершнинной связности графа.
vector <float> node_coherence(0);
node_coh_id = 0;
node_rel_status = 0;
// Вектор n(t) - изменение количества вершин в графе.
vector <float> number_of_nodes(0);
non_id = 0;
for (long i = 0; i < cycle_id; i++){
head_graph = create_graph(10, 1.5);
// Цикл по времени.
t = 0.0;
coh_prob_id = 0;
nor_id = 0;
rib_coh_id = 0;
node_coh_id = 0;
non_id = 0;
while (t <= max_t & head_graph->number_of_nodes > 0){
move(head_graph, delta_t, 2);
delete_arcs(head_graph->arc_pointer);
delete head_graph->arc_pointer;
head_graph->arc_pointer = NULL;
head_graph->arc_pointer = create_arc(head_graph);
rib_rel_status = 0;
node_rel_status = 0;
if (i == 0){
coherence_probability. push_back(check_relations(head_graph));
number_of_ribs. push_back(head_graph->number_of_arcs);
number_of_nodes. push_back(head_graph->number_of_nodes);
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 |
