Материал: Организация базы данных для хранения динамических моделей беспроводных компьютерных Ad hoc сетей

Одним из способов задания графа является его представление с помощью матрицы смежности. Значение элемента ai,j этой матрицы, расположенного на пересечении i строки и j столбца определяется по правилу:

 , (2)

где i,j = 1..n.

Например, если сеть состоит из трех узлов, изображенных на рисунке 6,

Рисунок 6 - Сеть

то для нее соответствующий граф будет иметь вид, представленный на

рисунке 7.

Рисунок 7 - Граф

Матрица смежности представляется в виде, указанном в таблице 1.

Таблица 1 - Таблица смежности графа

В соответствии с формулой (1), в начальный момент времени t0 = 0 задаем граф G0. Найдем моменты изменения графа G0 по следующей схеме.

Рассмотрим узлы Si и Si+1, i = 1..n. В начальный момент времени t0 = 0 их местоположение на плоскости определяется соответственно системами вида

, (3)

, (4)

а в некоторый момент tj соответственно

,  , (5)

, , (6)

где i = 1..n, j = 1..k.

Так как сеть связна, то условием связности графа будет неравенство вида:

, (7)

где ri, ri+1 - радиусы уверенного приема сигнала соответствующих узлов,

i = 1..n, j = 1..k.

Переходя из неравенства (2) в соответствующее равенство, для каждой пары вершин Si, Si+1 рассчитаем момент времени, который удовлетворяет условию (2). В ходе преобразований получим квадратное уравнение вида

  (8)

решая которое получаем формулу для вычисления моментов изменения графа:

 (9)

где

причем отрицательные значения моментов времени не учитываем. Поскольку равенство (8) квадратное, то получим два значения момента времени, то есть возможны две ситуации:

;

.

Каждая ситуация определяется графическим решением, изображенном на рисунке 8.

t₀                     t₁                                 t₂                           T                 t                                                                                                                                 

t₀                     t₁                                            t₂                          T             t

Рисунок 8 - Графическое решение для двух узлов

Рассмотренные ситуации будут у каждой пары вершин. Таким образом, в момент времени tj с учетом всех пар вершин получим (n*(n-1))/2 неравенств. Изображая графические решения, представленные на рисунке 3, каждого неравенства один под другим в одном масштабе и проводя прямые через t1 и t2 каждой пары узлов соответственно, перпендикулярные оси t, получим сетку. Например, для трех узлов, каждая пара из которых будет иметь свои t1 и t2, с учетом двух возможных ситуаций и, имея граф G0, представленный Таблицей 1, будем иметь графическое решение соответственно рисунку 9.

        [S₁, S₂]

   t₀                t₁                         t₂                               T       t

       [S₂, S₃]

   t₀    t₁                                                                                   t₂           T       t

    [S₁, S₃]

  t₀                                     t₁                t₂                         T        t

Рисунок 9 - Графическое решение для трех узлов

По Рисунку 9 определяем, какой паре узлов принадлежит минимальный момент времени. В рассматриваемом примере минимальный момент времени - это t1, принадлежащий паре узлов [S2, S3], обозначим его t1(S2, S3), причем при  соответствующие узлы находились в зоне видимости друг друга, обозначим tj как tj(S2, S3). Однако в зоне видимости находились и узлы (S1, S3), так как для них . Заметим, что в этот момент t1(S2, S3) узлы (S1, S2) не имели между собой связи. Таким образом, в момент времени t1(S2, S3) будем иметь следующую матрицу смежности, указанную в таблице 2.

Таблица 2 - Таблица смежности для графа в момент времени t1.

Аналогично рассуждая для t1(S1, S2), t1(S1, S3), t2(S1, S2), t2(S1, S3), t2(S2, S3), строим соответствующую матрицу смежности получившегося графа. Сравнивая матрицу смежности текущего промежутка с матрицей смежности, составленной для предыдущего промежутка, находим тот момент времени, где хотя бы одно значение матрицы изменилось.

В программной реализации алгоритм моделирования поведения узлов содержится в процедуре CalcGraph() и выглядит следующим образом:

__fastcall TfView::CalcGraph()

{(!dm->qGraph->IsEmpty())

{>qGraph->DisableControls();BK = dm->qGraph->GetBookmark(); //закладкаT= UpDown1->Position;>qGraph->First(); // указатель текущей записи на первую, база= dm->qGraphX->Value+dm->qGraphA->Value*T+dm->

>qGraphR->Value ,= dm->qGraphY->Value+dm->qGraphB->Value*T+dm->

>qGraphR->Value,= dm->qGraphX->Value+dm->qGraphA->Value*T-dm->

>qGraphR->Value,= dm->qGraphY->Value+dm->qGraphB->Value*T-dm->qGraphR->Value;(dm->qGraph->First();!dm->qGraph->Eof;dm->qGraph->Next()) //указатель на след. запись в базе, цикл

{if(maxX < dm->qGraphX->Value+dm->qGraphA->Value*T+dm->

>qGraphR->Value) maxX = dm->qGraphX->Value+dm->

>qGraphA->Value*T+dm->qGraphR->Value;(maxY < dm->qGraphY->Value+dm->qGraphB->Value*T+dm->

>qGraphR->Value) maxY = dm->qGraphY->Value+dm->

>qGraphB->Value*T+dm->qGraphR->Value;(minX > dm->qGraphX->Value+dm->qGraphA->Value*T-dm->

>qGraphR->Value) minX = dm->qGraphX->Value+dm->

>qGraphA->Value*T-dm->qGraphR->Value;(minY > dm->qGraphY->Value+dm->qGraphB->Value*T-dm->

>qGraphR->Value) minY = dm->qGraphY->Value+dm->

>qGraphB->Value*T-dm->qGraphR->Value;

}(maxY> maxX) maxX=maxY;(minY< minX) minX=minY;(gImage->Width<gImage->Height)=gImage->Width / (maxX-minY);=gImage->Height / (maxX-minY);>qGraph1->SQL->Clear();(int i=0;i<dm->qGraph->SQL->Count;i++) dm->qGraph1->SQL->

>Add(dm->qGraph->SQL->Strings[i]);(int i=0;i<dm->qGraph->Params->Count;i++) >qGraph1->Params->Items[i]->Value=dm->qGraph->Params->Items[i]->Value;>qGraph->GotoBookmark(BK);>qGraph->FreeBookmark(BK);>qGraph->EnableControls();

}

}

4. Организация базы данных для хранения ad hoc сети

4.1 База данных

База данных - собрание записей, интегрированных в некоторые структуры. Записью в базах данных называют минимальную уникально идентифицируемую единицу независимого хранения данных, образованную иерархией полей[5].

Система управления базами данных - совокупность языковых и программных средств, предназначенных для создания, ведения и совместного использования БД многими пользователями.

Основные функции систем управления базами данных - это определение данных (описание структуры базы данных), обработка данных и управление данными.

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

Известны три разновидности структуры данных: иерархическая, сетевая и табличная. Соответственно по признаку структуры базы данных делятся на иерархические БД, сетевые БД и реляционные БД (наиболее распространенные). Хранение динамической модели беспроводной ad hoc сети в данной работе осуществляется в реляционной БД.

Каждая таблица реляционной БД представляется как совокупность строк и столбцов, где строки соответствуют экземпляру объекта, конкретному событию или явлению, а столбцы - атрибутам (признакам, характеристикам, параметрам) объекта, события, явления.

4.2 База данных для ad hoc сети

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

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

Рисунок 10 - Схема БД для хранения ad hoc сети

Из приведённой выше схемы можно увидеть, что база данных сводит к минимуму количество избыточных данных, при этом сохраняя их целостность, то есть является нормализованной.

Имена графов хранятся в таблице «GRAPHS_NAME», которая включает два поля:

Первичный ключ «ID». Служит для того, чтобы уникально идентифицировать каждую запись в таблице. Поле первичного ключа является автоинкрементным и не может быть пустым. Для получения автоинкремента перед вставкой был создан и установлен триггер «After insert» со следующим скриптом:

AS IF (NEW.ID IS NULL) NEW.ID = GEN_ID(GEN_GRAPHS_NAME_ID,1);

END

В переменной «NEW» находится введенная нами новая запись для таблицы. Поле «ID» этой переменной проверяется, и если оно ровно «NULL», то вызывается функция «GEN_ID», которая генерирует значение, увеличенное на 1 для генератора «GEN_GRAPHS_NAME_ID». И присваивает результат переменной «NEW.ID».

Скрипт генератора «GEN_GRAPHS_NAME_ID»:

CREATE SEQUENCE GEN_GRAPHS_NAME_ID;SEQUENCE GEN_GRAPHS_NAME_ID RESTART WITH 20;

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

Хранимые процедуры и триггеры являются модулями компилированных, выполняемых кодов, которые выполняются на сервере. Исходный код пишется на расширении языка SQL, называемом процедурным SQL, или PSQL.

Хранимые процедуры могут быть выполняемыми процедурами и селективными процедурами. Они могут получать входные аргументы и возвращать выходные наборы. Выполняемые процедуры выполняются полностью на сервере и могут возвращать набор констант из одной строки (одиночный набор) по завершении выполнения. Селективные процедуры генерируют многострочные наборы из нуля или более строк, которые могут использоваться клиентскими приложениями различными способами, как и любой другой выходной набор.

С данной таблицей также связаны две хранимые процедуры. Процедура «NEW_GRAPH» по добавлению нового графа в базу данных, представляющая собой скрипт:

begin=gen_id(gen_graphs_name_id,1);into graphs_name values(:outid,:inname);

end

И процедура «DELETE_GRAPH» по удалению выбранного графа:

beginfrom graphs_name where id=:inid;

end

Каждому узлу соответствует запись в таблице «GRAPHS», состоящей из семи полей:

«GRAPH_ID» является суррогатным ключом, то есть дополнительным полем, единственное предназначение которого - служить внешним ключом. Значение этого поля заполняется путем выбора значений из связанной с полем внешней таблицы и не может быть пустым.

«GRAPH_TIME» отражает момент времени, когда характеристика соответствующего узла была сохранена и экспортирована из приложения СУБД.

«X» задает одну из ключевых координат положения узла на плоскости по оси абсцисс.

«Y» задает одну из ключевых координат положения узла на плоскости по оси ординат.

«A» это одна из координат вектора скорости, задающее направление по оси абсцисс.

«B» это одна из координат вектора скорости, задающее направление по оси ординат.

Для таблицы «GRAPHS» также организованы хранимые процедуры. Это процедура по добавлению вершины «ADD_POINT»:

begininto graphs values(:ingraph_id,:ingraph_time,:inx,:iny,:inA,:inb,:inr);

end

И процедура по удалению вершины «DELETE_POINT»:

beginfrom graphs:ingraph_id=graph_id and :ingraph_time=graph_time

:inx=X and :iny=Y

:inA=A

:inb=B and :inr=R;

end

Для реализации базы данных использовалась Firebird SQL - компактная, кроссплатформенная <https://ru.wikipedia.org/wiki/%D0%9A%D1%80%D0%BE%D1%81%D1%81%D0%BF%D0%BB%D0%B0%D1%82%D1%84%D0%BE%D1%80%D0%BC%D0%B5%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D0%B5%D1%81%D0%BF%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D0%B5>, свободная <https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D0%BE%D0%B1%D0%BE%D0%B4%D0%BD%D0%BE%D0%B5_%D0%9F%D0%9E> система управления базами данных <https://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%83%D0%BF%D1%80%D0%B0%D0%B2%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%B1%D0%B0%D0%B7%D0%B0%D0%BC%D0%B8_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85>. Плюсами Firebird являются высокая эффективность и мощная языковая поддержка для хранимых триггеров и процедур. Кроме того, стоит отметить, что Firebird легко поддерживает довольно большие базы данных. СУБД Firebird используется в промышленных системах различного рода как государственного, так и негосударственного сектора.

Для создания, администрирования и совершения каких-либо действий с базой данных используется GUI <https://ru.wikipedia.org/wiki/GUI>-оболочка IBExpert. Данный продукт является одним из лучших инструментальных пакетов для работы с базами данных Firebird. Он позволяет в визуальном режиме создавать и модифицировать объекты, содержащиеся в БД. После работы в одном из визуальных редакторов (таблиц, доменов, скриптов и т.д.) выполняется компиляция произведенных действий. При этом IBExpert генерирует соответствующие операторы модификации базы, выполнение которых над БД подтверждается нажатием кнопки «Commit». IBExpert также содержит средства анализа производительности выполнения запросов. С его помощью можно решать подавляющее большинство задач, возникающих при проектировании и создании баз данных Firebird.

4.3 Клиентское приложение для работы с базой данных

Для работы с базой данных разработано специальное клиентское приложение в системе программирования Borland C++ Builder. Данный выбор обусловлен небольшой требовательностью к аппаратным ресурсам, легкостью в освоении и применении средств системы для разработки приложений, а также популярность языка С++.

Все объекты компонентов размещаются в объектах - формах. Для каждой формы C++Builder создает отдельные модули, в которых и осуществляется программирование задачи [7].

Для реализации просмотра, добавления, удаления и сохранения информации в приложении использованы следующие компоненты С++ Builder:. Это центральный компонент, предназначен для соединения с базой данных. . Организует управление транзакциями.. В качестве источника данных используется размещенный на странице DataSource. Он связывается с набором данных своим свойством Data Set.. Компонент для выполнения запросов SQL к серверу.. Используется для просмотра и редактирования базы данных в режиме таблицы.- набор кнопок для навигации по DBGrid.