Генератор псевдо-случайных UDG-графов с наперед заданными свойствами

Тип разработки: 
Программа
Регистрационный номер в ФАП: 
PR13046
Дата регистрации в ФАП: 
2013-12-23
Тематическая направленность: 
Теория графов. Моделирование сетей связи
Разработчики программы (базы данных): 
Аннотация: 

Назначение - генерация псевдо-случайных Unit Disk Graphs (UDG-графов)
Область применения - моделирование сенсорных и Mesh сетей

Используемый алгоритм:

Граф G=(V,E) называется UDG-графом (unit disk graph), если ребро (u,v)  существует тогда и только тогда, когда расстояние между вершинами u и v меньше либо равно 1 (в общем случае - d).Программа генерирует на заданной области случайные UDG-графы с наперед заданными свойствами (связность, ограничение на степень вершин, ограничение на количество хопов).

Реализованы три способа генерации UDG-графов::

  1. Традиционный алгоритм (случайный выбор точек в заданной области и проверка заданных свойств)
  2. Алгоритм C-Crug (используются полярные координаты для выбора каждой следующей вершины [1])
  3. Алгоритм Lattice (строится дополнительная сетка в заданной области, которая используется для выбора каждой следующей вершины. Использование распределения Пуассона при выборе ячеек сетки) [2]. Осуществляется сбор статистики по распределению степеней для серии сгенерированных графов.

Функциональные возможности - Во вложении приведена таблица времени генерации UDG-графов в зависимости от количества вершин и способа генерации.
Инструментальные средства создания - Lazarus.

[1] Furuzan Atay Onat, Ivan Stojmenovic, Halim Yanikomeroglu Generating random graphs for the simulation of wireless ad hoc, actuator, sensor, and internet networks. Pervasive and Mobile Computing, 4:597-615, 2008.

[2] Шахов В.В., Соколова О.Д., Юргенсон А.Н. "Эффективный метод для генерации псевдо-случайных UDG-графов" // Труды конференции «Информационные технологии и системы — 2013», Светлогорск, ISBN 978-5-901158-23-4, стр. 411-414.

Версия регистрируемой программы (базы данных): 
1
Использованные при разработке материалы: 
Furuzan Atay Onat, Ivan Stojmenovic, Halim Yanikomeroglu Generating random graphs for the simulation of wireless ad hoc, actuator, sensor, and internet networks. Pervasive and Mobile Computing, 4:597-615, 2008.
Признак доступности программы (базы данных): 
доступ по запросу
Требования к аппаратным и программным средствам: 

ОС Linux

Контактная информация: 
nastya@rav.sscc.ru
ВложениеРазмер
udg-generator.pdf657.91 КБ