площади для размещения, растет среднее число появляющихся мостов и
время, необходимое на отыскание одного такого моста. Если в модели с 500
0
10
20
30
40
50
60
0 5000 10000 15000
Среднее число мостов в соответствующей серии
испытаний
Среднее число
мостов
Верхняя оценка
среднего числа
мостов
0
1
2
3
4
5
6
7
8
0 2000 4000 6000 8000 10000 12000 14000 16000
18
узлами оно составляет всего лишь 0,16 мс., то уже в тестах с 4500 узлами
поднимается до 1,46 мс. на 1 мост. Однако, сильнее всего время отыскания
моста выросло в последнем случае. Для троекратного увеличения N (по
сравнению с случаем 4500 узлов) наблюдаю увеличение времени отыскания
каждого моста в 4,8 раза (7,06 мс. на 1 мост).
Также, при троекратном увеличении концентрации узлов сети, среднее
число мостов повышается только в 2 раза.
Для того, чтобы говорить о корректности данных, собранных
многопоточной программой, оценим отличия в асимптотике вероятности
появления мостов в случае однопоточной (О) и многопоточной (М)
программ:
Рисунок 7 – сравнение данных о вероятности появления мостов.
Как видно, отличия незначительны. Поэтому можно говорить о
корректности собранных данных.
Тестирование среднего числа мостов дало следующие результаты:
0
0,001
0,002
0,003
0,004
0,005
0,006
0,007
0,008
0,009
0 2000 4000 6000 8000 10000 12000
(М)
(О)
Рисунок
Результаты, полученные
следующей рекурсивной
Пусть a= F(n
Тогда остальные результаты
Для получения верхней
F
n/2 .
В результате применения
получен следующий результат
Рисунок
многопоточной
0
20
40
60
80
100
120
140
0 2000 4000
0
2
4
6
8
10
12
Однопоточная
19
8 – оценка среднего количества мостов
Результаты программой, хорошо
функцией:
/3
можно оценить как a7
оценки достаточно будет рассчитать
параллельной архитектуры
времени работы, мин.:
9 – Сравнение временных затрат однопоточной
версий программы.
6000 8000 10000 12000
Среднее
оценка
Многопоточная
Сравнение временных затрат
Однопоточная
Многопоточная
мостов.
приближаются
! a'89 a;
a!
программы был
и
число мостов
20
Таблица 2.
Сравнение производительности многопоточной и однопоточной
программ.
Однопоточная, мин. Многопоточная, 2 потока,
мин.
Прирост, %.
11,12 5,8 47,84
Листинг подпрограмм, использованных в экспериментах, приведен в
приложении Д.
21
ЗАКЛЮЧЕНИЕ
Основные результаты и выводы работы:
Разработана программа, позволяющая исследовать имеющуюся
беспроводную ad hoc сеть, представленную неориентированным графом, на
предмет повреждений структуры сети и возможности восстановить
поврежденную структуру, а так же снизить риск нарушения структуры путем
выявления ненадежных участков сети – мостов.
Проведены испытания, показавшие, что при увеличении числа узлов в
сети, расположенных на фиксированной площади, растет и количество
ненадежных каналов связи, при разрыве которых сеть потеряет целостность,
распавшись на несколько несвязанных сегментов. При этом, количество
таких каналов возрастает в 2 раза при увеличении концентрации сетевых
узлов в 3 раза.
Рассмотрен стандарт многопоточного программирования С++ 11 на
примере конкретной программы. Оценка прироста производительности
составила ~48%.
22
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. , , Лекции по
теории графов. // М: Наука, 1990. с. 36.
2. Басакер Р, еревод с английского. Конечные графы и сети. // М:
Наука. 1973. с. 25.
3. еория графов. Перевод с английского. // М: Едиториал УРСС.
2003. с. 27, 42.
4. зык программирования С++. // Второе дополненное
издание. 1997. с. 14 – 17.
5. Элементы теории графов.// Пенза: изд-во ПГУ, 2007.
6. Основы теории графов.// М.: Вузовская книга. 2004.
7. араллельное программирование на С++ в действии.//М.:ДМК
Пресс, 2012.
23
ПРИЛОЖЕНИЕ А
Класс node.
/*Вершина. Имеет координаты x, y и радиус действия передатчика range*/
class node
{
public:
float x, y;
float range;
node::node(float x, float y, float range)
{
this->x = x;
this->y = y;
this->range = range;
};
};
24
ПРИЛОЖЕНИЕ Б
Класс grafe.
class grafe
{
public:
vector<vector <int> > edgelist;// список смежности.
vector<int> Marker;//массив посещенных врешин
int size; //число вершин
vector<vector <int>> Components; // Хранит компоненты связности
графа
vector<int> comp; // временный вектор для сборки Components
vector<node*> GNodes; //Вектор, хранит указатели на все
имеющиеся узлы сети
vector<node*> AverageComponents;//Указатели на узлы
среднестатистических координат в компонентах
vector<T_Averaged_Components*> UCComponents; //Информация о
возможностях связать компоненты
vector<T_Bridges*> Bridges; //Ребра-мосты
vector<pair<int, int>> IRepair;/*пары вершин для прокладки ребер
между компонентами*/
int diam; //диаметр графа
grafe (int n);
~grafe(void){};
int DFS1(int); // Поиск в глубину в чистом виде.
void grafe::bridgeUtil(int u, bool visited[], int disc[], int
low[], int parent[]); //вспомогательная подпрограмма поиска мостов
void bridge(); //основная подпрограмма поиска мостов
int GDDFS_Iter(int v1);//итеративный DFS, поиск диаметра графа.
int GDiamIter(); //Поиск диаметра графа, основная подпрограмма
int GUComponents_Iter();//проверка связности графа на итеративном
обходе.
//-----------------------------------------------
void EListPrint();//Печать списка смежности графа
void UCComponentsPrint();//Печать компонент связности
int BridgesPrint();//Печать мостов
void PMayRepair(); //Информация о возможности восстановления
float Range_Between(node *, node *); // Дистанция между узлами
сети.
};
25
ПРИЛОЖЕНИЕ В
Класс T_Averaged_Components.
class T_Averaged_Components
{
public:
pair<int, node*> Node1;//Номер первого узла/компоненты,
pair<int, node*> Node2; //Номер второго узла/компоненты
float mydistance;
T_Averaged_Components(node * P1, node* P2, float dist, int num1,
int num2)
{
this->Node1.first=num1;
this->Node1.second = P1;
this->Node2.first=num2;
this->Node2.second=P2;
this->mydistance = dist;
}
};
26
ПРИЛОЖЕНИЕ Г
Класс T_Bridges
class T_Bridges
{
public:
int v1,v2;
T_Bridges(int x, int y)
{
this->v1 = x;
this->v2 = y;
}
};
27
ПРИЛОЖЕНИЕ Д
Реализация методов класса grafe.
grafe::grafe(int n)
{
size = n;
diam=0;
for (int i = 0; i<n; i++)
{
Marker. push_back(0);
edgelist. push_back(vector <int> ());
Components. push_back(vector <int> ());
}
}
//---------------Печать списка смежности графа------------------------
void grafe::EListPrint()
{
cout << "Ребра: " << endl;
int v, u;
for(int i=0; i<(int)edgelist. size(); i++)
{
for(int j=0; j<(int)edgelist[i].size(); j++)
{
u=i+1;
v=edgelist[i][j]+1;
cout << "(" << u << " <-> " << v <<"); \n";
}
cout << endl;
}
}
int grafe::DFS1(int v)
{
int tmp=0; //tmp, is result
int mtmp=0; //max for tmp
comp. push_back(v+1);
Marker[v] = 1; //вершина посещена
for (vector<int>::iterator i = this->edgelist[v].begin(); i!=
this->edgelist[v].end(); ++i)
{
if ( Marker[*i] != 1 )
{
DFS1(*i);
28
}
}
return 1;
}
//-----------------------------------------------------------
void grafe::bridgeUtil(int u, bool visited[], int disc[], int low[],
int parent[])
{
static int time = 0;
// Отметка о посещении вершины
visited[u] = true;
// Инициализуем минимальное значение и счетчик посещения
disc[u] = low[u] = ++time;
// Пройдем по всем вершинам, смежным с данной
vector<int>::iterator i;
for (i = edgelist[u].begin(); i!= edgelist[u].end(); ++i)
{
int v = *i; // выбранная v смежна с u
// Если v не посещена, повторим поиск для нее
if (!visited[v])
{
parent[v] = u;
bridgeUtil(v, visited, disc, low, parent);
/*Убедимся, что поддерево с корнем v имеет связь с одним
из предков u*/
low[u] = min(low[u], low[v]);
/*Если вершины в разных компонентах связности, то
ребро - мост*/
if (low[v] > disc[u])
{
// cout << u+1 <<" <-> " << v+1 << endl;
this->Bridges. push_back(new T_Bridges(u+1, v+1));
}
}
// Обновим значения.
else if (v!= parent[u])
low[u] = min(low[u], disc[v]);
}
}
void grafe::bridge()
{
29
// Отметим все вершины как непосещенные
bool *visited = new bool[this->size];
int *disc = new int[this->size];
int *low = new int[this->size];
int *parent = new int[this->size];
// Проинициализуем массив предков и массив посещений
for (int i = 0; i < this->size; i++)
{
parent[i] = NIL;// NIL = -1, т. к. изначально предков нет.
visited[i] = false;
}
// Вызов рекурсивной функции поиска мостов. Корень поддерева i-я
вершина.
for (int i = 0; i < this->size; i++)
if (!visited[i] )
bridgeUtil(i, visited, disc, low, parent);
}
int grafe::BridgesPrint()
{
if (this->Bridges. size()>0)
{
cout << "Найдено "<< this->Bridges. size() << " мостов,
формат вывода \nv1 <-> v2 \n";
for (int i = 0; i < this->Bridges. size(); i++)
{
cout << " " << this->Bridges[i]->v1 << " - " << this-
>Bridges[i]->v2 << endl;
}
}
else
cout << "Мостов не обнаружено. \n";
return 0;
}
//------------------Дистанция между узлами---------------------
float grafe::Range_Between(node *P1, node *P2)
{
return (float)sqrt(pow(P1->x - P2->x, 2) + pow(P1->y - P2-
>y, 2));
};
//-----------------Печать компонент связности-------------------
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 |
