close

Вход

Забыли?

вход по аккаунту

?

Применение технологии сенсорных сетей в системе мониторинга судового навигационного оборудования.

код для вставкиСкачать
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
УДК 627.71:519.852.3
Т. Ю. Шейкин,
аспирант,
ГУМРФ имени адмирала С. О. Макарова
ПРИМЕНЕНИЕ ТЕХНОЛОГИИ СЕНСОРНЫХ СЕТЕЙ В СИСТЕМЕ
МОНИТОРИНГА СУДОВОГО НАВИГАЦИОННОГО ОБОРУДОВАНИЯ
APPLYING SENSOR NETWORKS TECHNOLOGY
TO ATON MONITORING SYSTEM
Аннотация. Рассматривается задача оптимального размещения шлюзов в сети навигационных знаков. Предлагаются критерии оценки структурной надежности и энергоэффективности сети, позволяющие ограничить размер решаемой задачи.
Abstract. The problem of gateway optimal placement in aids to navigation network is regarded. Evaluation
criteria of network structural reliability and energy efficiency are proposed to limit the size of the problem being
solved.
Ключевые слова: средства навигационного оборудования, система мониторинга, сенсорная сеть,
структурная надежность, энергоэффективность, целочисленное линейное программирование.
Key words: aids to navigation, monitoring system, sensor network, structural reliability, energy efficiency,
integer-linear programming.
Выпуск 3
О
122
ДНИМ из аспектов обеспечения безопасности судовождения является исправное функционирование средств навигационного оборудования (СНО). Основным направлением работ в эксплуатации навигационных знаков можно назвать предупреждение выхода из строя аппаратуры СНО, а также минимизацию времени пребывания СНО в состоянии
отказа. Организация удаленного мониторинга эксплуатационных параметров навигационных
знаков позволяет решать данную задачу без материальных и временны́х затрат на посещение каждого объекта и проведения регламентных работ. Для передачи информации в системе
мониторинга СНО технология сенсорных сетей (СС) является перспективным направлением
развития.
Сенсорная сеть — самоорганизующаяся сеть, состоящая из множества датчиков (сенсоров),
объединенных между собой радиоканалом. Ретрансляция сообщений позволяет многократно экономить энергию за счет сокращения мощности передатчиков. При организации централизованного наблюдения за объектами возникает задача передачи данных в некоторый центр мониторинга,
который может располагаться вне сенсорной сети. В подобных случаях целесообразно использовать шлюзы — узлы сенсорной сети, на которые установлены устройства, позволяющие передавать данные на большие расстояния, например передатчики сотовой или спутниковой связи.
В таком случае центр мониторинга может располагаться на любом расстоянии от наблюдаемых
объектов, однако существует вероятность потери связи с исправными узлами в случае выхода
из строя промежуточных узлов-ретрансляторов в СС и отсутствия альтернативных маршрутов
доставки пакетов данных к шлюзу. Таким образом, очевидна необходимость в обеспечении некоторой степени надежности сенсорной сети. Так же в данной работе рассматривается возможность
использования UHF-, VHF-модемов или специализированных передатчиков AIS AtoN без применения функции ретрансляции сообщений. Размещение приемопередатчиков в зоне радиовидимости базовой станции позволит не учитывать отдельно надежность сети шлюзов. В зависимости от
взаимного расположения узлов сенсорной сети в цепочке ретрансляции сообщений в направлении
шлюзов будет зависеть энергетическая нагрузка каждого узла и соответственно время функционирования всей сети.
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
Таким образом, появляется необходимость в создании системы проектирования и оценки
сенсорных сетей, которая позволит учитывать ряд требований и ограничений, определяемых условиями эксплуатации СНО. В данной статье уделено внимание некоторым вопросам данной проблемы, в частности разработана математическая модель задачи оптимального размещения шлюзов, а также разработана методика сокращения области поиска решений с учетом требований к
сети. Далее сформулированы основные критерии пригодности СС, по которым будут определены
требования:
— структурная надежность сети, то есть способность сети сохранять связность ее исправных узлов относительно шлюзов, в случае выхода из строя любого из ее элементов (в рамках данной статьи мы ограничимся рассмотрением обеспечения двусвязности);
— энергетическая эффективность сети, то есть рациональное использование энергетического ресурса узлов для увеличения времени функционирования сети.
Особенность средств навигационного оборудования как элементов сенсорной сети заключается в том, что каждый узел располагается в фиксированной точке некоторой акватории с заданными координатами. В зависимости от радиуса действия приемопередатчиков и их взаимного геометрического расположения формируется топологическая структура сети. Существование узлов,
выход из строя которых может повлиять на работу всей сети передачи данных, может оказаться
серьезным недостатком всей системы мониторинга СНО. Использование одноранговой (децентрализованной) многоячейковой сети позволит в некоторой степени исключить данный недостаток.
В качестве аппаратной платформы выбраны устройства Xbee с реактивным протоколом DigiMesh, основанном на Ad-hoc On-demand Distance Vector (AODV). Ключевыми свойствами данного протокола можно назвать:
— возможность самовосстановления сети, то есть каждый узел может подключаться и отключаться от сети в любой момент времени без влияния на целостность всей сети в целом;
— отсутствие в архитектуре сети иерархической взаимосвязи между узлами;
— наличие режима «сна», который обеспечивает существенное сокращение энергопотребления.
Суть реактивного протокола заключается в том, что узлы формируют новые записи в таблице маршрутизации только по запросу, то есть при условии, что ранее путь к узлу назначения был
не известен или существовавший маршрут не является рабочим из-за исчезновения промежуточных узлов. В таблице каждого узла-отправителя хранится маршрут с минимальным количеством
хопов (ретрансляций) до узла назначения. Преимущество реактивного протокола заключается в
отсутствии необходимости постоянного поддержания в актуальном состоянии таблицы маршрутизации. Надежность доставки данных обеспечивается пакетами подтверждения. Более подробно
с технологией СС и алгоритмом AODV читатель может ознакомиться в [5].
Объектом исследования в данной работе является зависимость энергопотребления узлов от
структуры сети и схемы размещения шлюзов, поэтому количество энергии Eu, затрачиваемое узлом u в единицу времени t, можно представить следующим образом:
Выпуск 3
где t — период сбора информации при условии, что все узлы генерируют одно сообщение за
период (за час, за сутки и т. п.), независимо от типа СНО;
Еtx — энергия, необходимая для передачи пакетов данных одного сообщения;
nret — количество узлов, для которых узел u является ретранслятором;
Emax — предельно допустимое значение количества энергии, потребляемой узлом в единицу
времени t.
Значения перечисленных параметров зависят от аппаратной платформы и функциональных настроек сети, устанавливаемых проектировщиком. Максимальное количество сообщений txmax, которое может передаваться узлом в единицу времени, можно найти следующим образом:
123
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
Тогда энергетическая эффективность сети будет достигаться, если для каждого узла u будет
выполняться условие
(1)
Представим сеть навигационных знаков в виде графа G = (V, E), где V — множество вершин,
характеризующее навигационные знаки (|V | = n — количество вершин, определяемое порядком
множества V), E — множество ребер графа, характеризующее наличие радиоканала между СНО.
Наличие или отсутствие ребра между вершинами определяется радиусом действия передатчиков
сенсорной сети. Для построения графа G следует определить расстояние между навигационными
знаками по их географическим координатам. Расстояния между всеми вершинами графа представим в виде матрицы D порядка n, где каждый элемент является расстоянием d(u, v) от узла u до
узла v. Определим матрицу инцидентности A графа G, сравнивая каждый элемент матрицы D с
радиусом действия передатчиков R, полагая:
Изолированные вершины графа не могут участвовать в решении задачи размещения
шлюзов, так как данные узлы не имеют канала связи ни с одним другим узлом сети, поэтому
V = {v | deg v ≥ 1}. Таким образом, получаем некоторый граф, отражающий структуру сети
навигационных знаков. Задача оптимального размещения шлюзов в сети без введения требований структурной надежности и энергоэффективности может быть сформулирована как задача о
→
→
р-медиане графа [4]. Рассмотрим ацикличный ориентированный мультиграф G (V, E), в котором
→
E — множество направленных ребер (дуг). Дуга uv характеризует направление передачи одного
сообщения от узла u к узлу v в направлении ближайшего шлюза в единицу времени. Обозначим
как
множество дуг, входящих в вершину u, которое характеризует сообщения,
принимаемые узлом u от v,
nret (u). Множество дуг
из вершины u, характеризует сообщения, передаваемые узлом u до v,
Выпуск 3
Обозначим множество шлюзов сети как Vp  V (|V p| = p);
ременную:
124
, исходящих
.
и введем бинарную пе-
Пусть X — множество вариантов размещений р-медиан в графе. Для каждого варианта раз→
мещения шлюзов x  X следует построить ориентированный мультиграф G, отражающий направление потоков передаваемых данных в сети и соответственно нагрузку на узлы. Далее в работе
последовательность дуг, характеризующая передачу данных от каждого узла сети до ближайшего
шлюза (шлюзов), будет представляться в виде эквивалентной последовательности узлов. Особенность работы алгоритма маршрутизации AODV заключается в том, что в случае существования
нескольких вариантов кратчайших маршрутов выбор варианта, как правило, осуществляется произвольно. Таким образом, целесообразно учитывать все варианты кратчайших маршрутов доставки пакетов данных между вершинами. Пусть Nluv — множество узлов, составляющих l-ю простую
цепь узлов из V \ Vp от узла u до шлюза v при l  L, то есть для l-й простой цепи, состоящей из
последовательности u → u′ → ... → v′ → v, соответствует множество Nluv = {u, u′, ..., v′, v}. Тогда
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
′ — множество узлов, составляющих s-й кратчайший маршрут от узла u до шлюза v при
где Nsuv
s  S; N ′ — множество узлов, составляющих j-й кратчайший маршрут от узла u до ближайших
ju
J
шлюзов из Vp при j  J.
Вариант размещения шлюзов x считается приемлемым, если выполняется условие
|N ′ |
≤ txmax для всех u  V \ Vp. Подобное утверждение можно обосновать тем, что если для некоторого узла u существует маршрут до ближайшего шлюза v, то для всех узлов-ретрансляторов,
принадлежащих данному маршруту, шлюз v также является ближайшим. Энергетическая нагрузка на узел-ретранслятор v′, инцидентный шлюзу v, не будет превышать допустимого значения при
ju
выполнении условия nret (v′) + 1 ≤ txmax в соответствии с (1). Следовательно, для цепи узлов маршрута u → ... → v′ → v справедливо равенство |N ′ | = n (v′) + 1. С учетом данного утверждения
ju
ret
u
обозначим через V p множество ближайших шлюзов, на которые узел u  V \ Vp может передавать
данные в процессе эксплуатации. Тогда
Кроме того, обозначим через Vu множество узлов, которые могут быть задействованы при
u
передаче данных узлом u  V \ Vp до шлюзов из V p, при
В процессе эксплуатации каждым узлом будет задействован только один маршрут, поэтому
следует определить значение максимально возможной нагрузки на узлах, входящих в состав нескольких маршрутов. Таким образом, следует ввести бинарную переменную:
Для обеспечения двусвязности узлов относительно шлюзов достаточно существования для
каждого узла сети двух вершинно непересекающихся простых цепей узлов до двух разных шлюзов. Введем следующее обозначение:
N iu — множество узлов, представляющее i-ю простую цепь узлов из V \ Vp от узла u до шлюзов из Vp при i  IJ .
Также введем бинарную переменную, отражающую наличие подобных множеств для узла u:
,
(2)
при ограничениях:
(3)
Выпуск 3
С использованием введенных обозначений математическая модель задачи оптимального
размещения шлюзов (р-медиан) в терминологии целочисленного линейного программирования
имеет следующий вид
125
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
(4)
(5)
(6)
Целевая функция (2) определяет количество шлюзов. Условие (3) гарантирует подключение
каждого узла к ближайшему шлюзу. Неравенство (4) исключает избыточную энергетическую нагрузку в процессе эксплуатации, когда все узлы исправны. Условие (5) обеспечивает двусвязность
узлов относительно шлюзов.
В данной работе предлагается решение комбинаторной задачи (2)–(6) методом перебора вариантов размещения шлюзов (р-медиан) в сети при ограничениях на значения p, принимаемых в
некоторых областях размещения. Рассмотрим случай, где граф G = (V, E) состоит из нескольких
максимальных связных подграфов — компонент связности Gi = (Vi, Ei), I = {1 … m}, m — количество компонент связности. На рис. 1 изображен пример при m = 3.
Рис. 1. Несвязный граф G
Количество вариантов размещений шлюзов в подграфе Gi, где исключены варианты размещения при 1 < pi < ni , выглядит следующим образом:
Выпуск 3
где ni — количество узлов в компоненте i.
Стоит заметить, что задача размещения возникает лишь в тех Gi, где ni ≥ 3. В разных компонентах связности множества Xi являются независимыми, поэтому количество вариантов размещений в G находим по формуле
126
Если в структуре сети компонента связности графа двусвязна, то требование по надежности
(5) выполняется для этой компоненты, поэтому следует найти граничные значения pi , которые
обеспечивали бы сокращение перебора вариантов размещений шлюзов без предварительного анализа структуры сети
min
где pi — минимально возможное количество шлюзов, которое может покрывать компоненту
max
связности i; pi — максимально возможное количество шлюзов, которое может покрывать компоненту связности i.
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
Тогда количество вариантов размещения в компоненте связности i можно представить в виде
суммы биномиальных коэффициентов следующим образом:
min
Граница pi без информации о структуре графа определяется из предположения, что каждый шлюз будет передавать сообщения от максимально возможного количества узлов сети. Таким
min
образом, следует найти минимальное значение pi , для которого выполняется условие
где V i — упорядоченное множество вершин v  V
J i, степень которых отсортирована по убыванию,
то есть deg v1 ≥ deg v2 ≥ ... ≥ deg vn .
>
i
max
max
Для того чтобы найти pi , необходимо определить минимальное значение pi , для которого выполняется нижеследующее неравенство, исходя из предположения, что каждый шлюз будет
передавать сообщения от минимально возможного количества узлов сети:
где V i — упорядоченное множество вершин v  V
J i, степень которых отсортирована по возрастанию, то есть deg v1 ≤ deg v2 ≤ ... ≤ deg vn .
<
i
Если компонента связности графа имеет вершинные разрезы, состоящие из одной вершины,
тогда Gi следует рассматривать как множество блоков и точек сочленения. Блоком в графе называется максимальный двусвязный подграф, не содержащийся в другом таком подграфе, Bi — множество
блоков компоненты i. Точкой сочленения называется вершина, удаление которой нарушает связность
графа (увеличивает число компонент связности), Yi — множество точек сочленения компоненты i.
С алгоритмами поиска блоков в графе можно ознакомиться в [1; 3, с. 1309–1316]. Далее при рассмотрении блоков будем подразумевать, что Vbi  Vi, где это возможно, и придерживаться следующих
обозначений для упрощения записи Vb = (Vbi ). Количество точек сочленения блока b определяет его
степень на дереве блоков и точек сочленения, тогда deg b = | δ (b)|, при δ (b) = Vb ∩ Yi . Граф с тремя
точками сочленения и шестью блоками проиллюстрирован на рис. 2.
Выпуск 3
127
Рис. 2. Несвязный граф G с блоками
Сокращение Xi возможно путем введения ограничения на значения, принимаемые pb
внутри каждого блока b  B
J i. Пусть B1 — множество блоков, имеющих одну точку сочлене-
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
ния, B1 = {b | deg b = 1}. В целях обеспечения условия (5) достаточно выполнения неравенств
, следовательно, pi ≥ | B1|.
Поскольку точка сочленения может принадлежать множествам узлов нескольких блоков,
то при переборе вариантов размещения шлюзов во всей компоненте i точки сочленения будут
учитываться по несколько раз. Для исключения избыточности Xi будем рассматривать Yi отдельно.
Количество шлюзов внутри каждого блока будет определяться следующими ограничениями:
min
где
pb — минимально возможное количество шлюзов, покрывающее блок b;
max
pb — максимально возможное количество шлюзов, покрывающее блок b.
Задачи размещения шлюзов внутри блоков связного графа взаимозависимы, тогда внутри
каждой компоненты связности количество вариантов размещения примет вид
min
min
Вычисление pb производится следующим образом. Найти минимальное значение pb , для
которого выполняется условие
где V b — упорядоченное множество вершин v  V
J b \ Yi, степень которых отсортирована по убыва>
нию, то есть deg v1 ≥ deg v2 ≥ ... ≥ deg vn
;
b –degb
y f — точка сочленения блока b, степень которой определяется количеством ребер только
J b ∩ Yi, f = {1 ... deg b}.
внутри блока, δ (yf ) = Eb ∩ δ (vf ) при vf  V
max
max
Для того чтобы найти pb ,необходимо найти минимальное значение pb , для которого выполняется условие
где V b — упорядоченное множество вершин v  V
J b \ Yi, степень которых отсортирована по возрастанию, то есть deg v1 ≤ deg v2 ≤ ... ≤ deg vn –deg .
<
Выпуск 3
b
128
b
В результате работы получена математическая модель дискретной задачи оптимального
размещения шлюзов в сенсорной сети. Получена методика сокращения области поиска решений
за счет введения ограничений на количество шлюзов, которые могут размещаться в компонентах
связности и блоках. Разработан способ определения энергоэффективных вариантов размещения
шлюзов. Представленный в данной работе метод перебора не является оптимальным с вычислительной точки зрения, но может оказаться приемлемым для частных случаев при ni ≤ 20 [2]. Ввиду
подобных ограничений появляется необходимость в более глубоком понимании сути проблемы и
разработке полиномиального алгоритма для решения поставленной задачи. Также в дальнейшем
предстоит рассмотреть вопрос реализации k-связности узлов относительно шлюзов для обеспечения структурной надежности сети при k > 2.
Ж У Р Н А Л
университета
в о д н ы х
коммуникаций
Список литературы
1. Асанов М. О. Дискретная математика: графы, матроиды, алгоритмы: учеб. пособие /
М. О. Асанов, В. А. Баранский, В. В. Расин. — 2-е изд., испр. и доп. — СПб.: Лань, 2010. — 368 с.
2. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. — М.:
Мир, 1982. — 416 с.
3. Диниц Е. А. Экономный алгоритм выделения блоков в графе / Е. А. Диниц, М. А. Зайцев,
А. В. Карзанов // Журнал вычислительной математики и математической физики. — М., 1974. —
Т. 14, № 5.
4. Кристофидес Н. Теория графов. Алгоритмический подход / Н. Кристофидес. — М.: Мир,
1978. — 432 с.
5. Dargie W. Fundamentals of wireless sensor networks: theory and practice // W. Dargie, C. Poellabauer. — Singapore: Markono, 2010. — 311 p.
Выпуск 3
129
Документ
Категория
Без категории
Просмотров
4
Размер файла
886 Кб
Теги
мониторинг, судового, сенсорными, навигационного, технология, система, оборудование, сетей, применению
1/--страниц
Пожаловаться на содержимое документа