Автореферат (1137247), страница 2
Текст из файла (страница 2)
Дается общее определение времени жизни БСС с автономными источниками питания,анализируются возможные способы его увеличения. В качестве одного изперспективных методов подробно рассматривается динамическая реконфигурация сети с помощью мобильного стока, приводятся результаты анализаматематических моделей, описывающих работу БСС, обосновывается необходимость разработки новой модели.Основным отличием БСС от всех других типов беспроводных сетей является использование ограниченных по вычислительным возможностям миниатюрных устройств для решения задач мониторинга и управления.
Каждоеустройство может содержать различные датчики контроля параметров окружающей среды (температура, давление, влажность, освещенность, уровеньшума и др).Главным лимитирующим фактором использования БСС с автономнымиисточниками питания является их ограниченное время жизни. При разрядеисточников питания в определенные моменты времени узлы сети становятсянеработоспособными. Поэтому время жизни БСС является принципиальноважным показателем, зачастую определяющим их применимость на практике. Таким образом, увеличение времени жизни является актуальной научнойи практической задачей.У исследователей в области БСС нет общего подхода к определению вре8мя жизни распределенной сети, в структуре которой может быть заложенаизбыточность.
Так существуют показатели времени жизни, основанные наколичестве работающих узлов, проценте покрытия и связности графа сети.Часто применяется самое простое определение, согласно которому сеть считается работоспособной до выхода из строя первого по счету узла.Существующие определения не различают типы узлов, а также не учитывают способности сенсорных сетей к самовосстановлению.
Поэтому одной изактуальных задач является определение единого показателя времени жизнисети.Анализ литературы выявил большое разнообразие подходов к решениюзадачи увеличения времени жизни сенсорной сети. Наиболее простыми являются использование больших по емкости аккумуляторов, снижение интенсивности генерируемого узлами трафика, сжатие данных.
В то же время, исходяиз специфики сенсорных сетей как централизованных сетей сбора данных,в большинстве случаев нерешенной остается проблема энергетического дисбаланса, выраженная в том, что сеть становится неработоспособной в тотмомент, когда энергия заканчивается у нескольких узлов, в то время какбольшинство остальных имеют значительный запас энергии.Таким образом, возникает задача балансировки мощности, потребляемой узлами сети. Ее можно решать несколькими способами, среди которыхиспользование динамических протоколов маршрутизации, использующих вкачестве метрики энергию узлов, чередование дальней и ближней передачи.Недавно был предложен новый класс перспективных методов, использующихв качестве ресурса для балансировки мобильность центрального узла сбораданных (стока).Динамическая реконфигурация БСС с помощью мобильного стока требует описания последовательности его перемещения между узлами сети. Всуществующих моделях такой возможности нет: в них каждая возможная9конфигурация сети рассматривается независимо от других.
Другим ограничением является то, что они рассчитаны только на фиксированные сетевыетопологии (дерево, решетка и т.д.). Таким образом, необходима общая модельБСС, позволяющая оценивать время жизни при динамических реконфигурациях.Для неизменных условий функционирования сети необходимо разработать метод, позволяющий находить оптимальный маршрут движения стокапо критерию максимизации времени жизни, а для случая изменяющихся условий - алгоритмы управления движением стока.Результаты первой главы опубликованы в следующих работах: [1, 5, 7, 8].Во второй главе дается описание общей модели динамически реконфигурируемой сенсорной сети. Приводится оригинальная методика расчетаключевых параметров модели, учитывающая особенности современных стандартов БСС. Детально исследуется понятие времени жизни сети с автономными источниками питания, предлагается новое определение, учитывающееспособность БСС к самовосстановлению.Реконфигурируемая сеть задается в виде следующей тройки: = ( , Γ , Π),где = ( , ) - граф конфигураций сети,Γ = { (), ∈ } - множество сетевых графов, каждый элемент которогосвязан с конфигурацией сети ,Π = (< 1 , 1 >, < 2 , 2 >, .
. . , < , >) - последовательность смены конфигураций.Граф конфигураций состоит из множества вершин = {1, 2, . . . , }и множества ребер : ⊆ × . В общем случае задает возможныесостояния, в которых может находиться сеть. Применительно к рассматриваемым далее в диссертации методам состояние определяется положением10мобильного стока. Например, на рис.
1 граф организован в виде решетки4 × 4, переходы стока возможны только по горизонтали и вертикали междусоседними вершинами.Рис. 1. Управляемая мобильность стокаКаждый из графов, входящих во множество Γ задает беспроводнуюсеть: () = ( , ), ∈ , где - множество вершин, ⊆ × множество ребер. Вершины соответствуют узлам сети, ребра - установленнымбеспроводным каналам передачи данных. = ∪ является множеством узлов сети, состоящим в общем случаеиз сенсорных узлов = {1 , 2 , . .
. , } и узлов-стоков = {1 , 2 , . . . , }.Каждый сенсорный узел = ( , , Σ ) характеризуется своей начальной энергией , набором = (1 , 2 , . . . , ), где представляет собоймощность, потребляемую -м узлом, при использовании -й конфигурациисети, и матрицей Σ = |− |× , где − - дополнительная энергия, затрачиваемая -м узлом при переходе сети от -й конфигурации к -й.
Такимобразом, особенностью предлагаемой модели является то, что работа любогосетевого узла выражается интегральной характеристикой потребляемой иммощности.11Сток представляет собой специальный тип идеального узла, для которого начальная энергия принимается неограниченной: = ( → ∞). Вдиссертации рассматривается случай с одним стоком.Последним элементом модели является последовательность смены конфигураций Π, состоящая из пар < , >, где ∈ - номер конфигурации, - время ее использования.Во-втором разделе главы приводится методика расчета времени автономной работы оконечных узлов и маршрутизаторов БСС.В третьем разделе главы приводится описание предлагаемого авторомопределения времени жизни БСС.
Разобъем сеть на отдельные зоны обслуживания и введем показатель качества работы сети для каждой зоны, зависящий от времени . Для этого рассмотрим некоторый интервал ( − ∆ , ).Пусть () – общее количество событий, возникших в зоне в данный интервал времени, а () – количество событий из общего числа (), доставленных до стока за допустимое время. Допустимое время может задаватьсякак в целом для области , так и для каждого типа события, возникающегов ней.
Значение параметра ∆ выбирается исходя из интенсивности событийв конкретной зоне и требований приложения по обеспечению качества обслуживания. Тогда показателем качества работы сети в зоне в момент времени можно считать: () =⎧⎪⎨ () , если () ̸= 0 ()⎪⎩1,если () = 0Пусть – пограничное значение показателя , выше которого сеть считается работоспособной. Зададим через Θ множество точек во времени, вкоторых переходит через границу сверху вниз и обратно:12Рис.
2. Изменение показателя качества работы сети со временемΘ = { , = 1, 2, . . . : ( ) ≥ ∧ ( ( + ) < ∨∨ ( − ) < ), < +1 , → 0}Пусть максимальное время восстановления сети после сбоев, вызванныхотказами узлов либо внешними факторами, ограничено некоторой величиной . Определим подмножество Θ′ ⊆ Θ точек перехода через границу сверху вниз, таких, что последующий переход в обратную сторону происходитпозже , либо не происходит вовсе.Θ′ = {() , = 1, 2, .
. . : () ∈ [1..|Θ | − 1] : ∀ ∈ (() ..()+1 ) () < ∧ ()+1 − () > } ∪ {|Θ | }Тогда моментом времени, после которого сеть выходит из строя для отдельной зоны , будет = inf Θ′ , а временем жизни всей сети: = min Результаты второй главы опубликованы в работе [1].В третьей главе приводится описание предлагаемого автором методадинамической реконфигурации БСС, оптимизирующего маршрут движениямобильного стока по критерию максимизации времени жизни сети.13Пусть задана динамически реконфигурируемая сеть в соответствии сописанной во второй главе моделью = ( , Γ , Π).
Необходимо найти оптимальный маршрут движения стока Π по критерию максимизации временижизни сети.Предлагаемый метод основан на сведении задачи нахождения маршрутак оптимизационной задаче частично-целочисленного линейного программирования (ЧЦЛП). Постановка задачи в терминах ЧЦЛП выглядит следующимобразом: (1 , 2 , . .
. , ) =∑︁ → (1)=1при следующих ограничениях:∑︁=1 +∑︁∑︁ − ≤ , = 1..(2)=1 =1,̸=∑︁0, = 1(3),+1 = 1(4)=1∑︁=1∑︁ ==0,̸=∑︁+1∑︁ , = 1..(5)=1,̸= = , = 1..(6)=0 ≤ ≤ , = 1.. − + · ≤ − 1, ≤ ,1 ≤ , ≤ , ̸= 1 ≤ , ≤ , ̸= ∈ {0, 1}, , ∈ Nгде = | | - матрица смежности графа ,14(7)(8)(9)(10)Целевая функция является временем жизни сети при условии что каждый узел во время движения стока работает в рамках своего начального запаса энергии.
Последнее обеспечивается набором ограничений (2).Для построения маршрута в структуру задачи вводится искусственноедополнение. Так как движение может начинаться с любой точки, в граф позиций стока добавляются дополнительные виртуальные вершины – 0 и + 1,чтобы зафиксировать начало и конец маршрута. Генерация маршрута обеспечивается ограничениями (3) - (5).
Для выполнения равенства (3) происходитустановка в 1 одной из переменных 0, . Аналогично окончание маршрутафиксируется установкой в 1 одной из переменных ,+1 . Чтобы в каждуювершину входила только одна дуга, используется ограничение (6).
Выражение (5) выравнивает входящий и исходящий потоки для каждой посещаемойвершины, что автоматически обеспечивает построение маршрута.Однако при этом не исключаются возможности образования циклов, несвязанных с основным маршрутом. Для решения данной проблемы в модельвводится дополнительное ограничение (8). Вспомогательные переменные служат для присвоения посещенным вершинам индексов в соответствии спорядком прохода стока через них: если = 1, то < . Таким образом, становится невозможным повторное посещение одной и той же вершиныграфа.Ограничения (7) оставляют в маршруте только те позиции , для которых > 0. и представляют собой соответственно минимальное имаксимальное время нахождения стока на каждой из позиций.В результате решения задачи (1), например, одним из стандартных методов, получается набор величин , ∈ [1..].
Маршрут однозначно восстанавливается по значениям переменных и имеет вид: ((1), (2), . . . , ()),где () < (+1) , ∀ ∈ [1.. − 1].Описанная выше задача ЧЦЛП является NP-трудной. Поэтому в диссер15тации также предложен приближенный метод, позволяющий упростить еерешение за счет учета следующих особенностей предметной области:1. Современные алгоритмы маршрутизации в сенсорных сетях позволяютсущественно сократить величины − , в результате второй суммой вкаждом из неравенств (2) можно пренебречь.2. Учитывая неограниченность стока в ресурсах, необязательно строитькратчайший путь по найденному множеству позиций, для которых >0.В реальных системах зачастую невозможно заранее собрать всю информацию, необходимую для решения задачи (1). Поэтому рассматривается рядэвристических алгоритмов динамического управления мобильным стоком, использующих локальную информацию о состоянии сети.К ним относятся алгоритм случайного перемещения стока (RANDOM),обход сети по периметру, а также эвристический алгоритм GMRE (GreedyMaximal Residual Energy).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
