Подвижные сенсорные сети

В настоящее время существует множество распределенных объектов различных инфраструктур, которые могут использоваться в самых различных сферах жизни. В качестве примера можно привести сеть трубопроводов, железнодорожную сеть. Может возникнуть проблема обслуживания таких объектов. В качестве примера такой ситуации можно привести возникновение неполадки. Чтобы устранить неполадку, ее нужно своевременно обнаружить. Для этого можно использовать специальную автоматизированную систему, алгоритмы которой основаны на понятии «Подвижная сенсорная сеть».

Распределённая система – это система, отношения местоположений элементов в которой играют важную роль с точки зрения функционирования, анализа и синтеза системы.

Одной из основных свойств распределенных систем является распределение функций, ресурсов между множеством элементов (узлов) и отсутствие единого управляющего центра, поэтому выход из строя одного из узлов не влечет за собой полной остановки системы [3].

С увеличением площади территории, на которой расположен объект, либо усложнением алгоритмов управления более целесообразно применение распределенных систем.

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

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

Максимальная эффективность распределенной системы достигается при автономном режиме работы контроллеров, а обмен информацией между контроллерами минимален [4].

Архитектуру распределенной системы можно представить в виде сети или графа, узлами которого являются программные или программно-аппаратные компоненты, взаимодействующие между собой и обладающие независимым поведением .

Пример представления архитектуры системы в виде графа приведен на рисунке 1.

Рисунок 1. Пример представления железнодорожной сети в виде графа

Подвижная сенсорная сеть – это распределенная, самоорганизующаяся сеть датчиков и устройств, изменяющих топологию сети в зависимости от поставленной перед ней задачей [5, с.47].

Пусть существует набор датчиков d_i, i=1..N. Операция измерения значения параметра:

,

где  – расположение устройства в момент измерения;

 – измеряемый параметр;

 – время выполнения измерения;

– полученное значение измеряемой величины.

План измерений q_х, который содержит последовательность событий:

Маршрут измерений r_y, содержащий последовательность измерений:

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

Задача идентификации определяется в виде паттерна  и функции:

.

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

,

где  – интервал допустимой задержки или опережения измерения;

 – количество событий.

В подвижной сенсорной сети нужно соблюдать экономию ресурсов (количество устройств сбора и обработки данных), то есть необходимо:

где  - расстояние между локациями  и [2].

Проведем исследование эффективности алгоритмов для сбора и обработки данных с распределенных объектов.

Предположим, что события могут возникать в узлах системы в случайные моменты времени. Смоделируем это с помощью календаря событий. Каждое событие должно быть обнаружено и обработано системой. Для наглядности сравним среднее время между возникновением и обнаружением событий.

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

Поиск в глубину – рекурсивный метод обхода графа. Идея алгоритма заключается в том, что просматриваются все ребра, исходящие из рассматриваемой вершины. Если ребро идет в не посещённую вершину, то алгоритм запускается заново от этой вершины. Затем осуществляется возврат в предыдущую вершину и просматриваются остальные ребра. Возврат происходит, если в рассматриваемой вершине не осталось ребер, которые ведут в нерассмотренную вершину.

Если после завершения алгоритма не все вершины просмотрены, то алгоритм запускается заново от одной из не просмотренных вершин.

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

Рассматриваются все ребра-потомки, выходящие из текущего узла. Все рассматриваемые ребра добавляются в очередь. Если все потомки узла просмотрены, то из очереди извлекается следующий узел, и просматриваются потомки этого узла и т.д. Алгоритм завершается после просмотра всех узлов графа.

Алгоритм миграции датчиков в подвижной сенсорный сети имеет в основе принцип алгоритма муравьиной колонии. Используется модель поведения муравьёв, ищущих пути от колонии к источнику питания. Муравьи должны добраться до пищи, которая находится за неким препятствием. Во время движения муравьи выделяют феромоны, использующиеся в качестве маркера. На самом коротком пути будет наибольшая концентрация феромонов, значит, наибольшее количество муравьев выберет именно этот путь. Избежать преждевременной сходимости можно с помощью моделирования «испарения» феромонов [1].

Проведем исследование с помощью модели графа, приведенной на рисунке 2. Результаты исследований для разного количества датчиков (от 1 до 5) и разных алгоритмов приведены в таблицах 1-3 в единицах модельного времени.

Рисунок 2.  Пример модели графа

Таблица 1.

Результаты измерения с применением алгоритма обхода в глубину

Таблица 2.

Результаты измерения с применением алгоритма обхода в ширину

Таблица 3.

Результаты измерения с применением алгоритма миграции датчиков в подвижной сенсорной сети

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