Диссертация (1137248), страница 9
Текст из файла (страница 9)
С точки зрения наблюдения за сетью, при отсутствии информации об остаточнойэнергии элементов питания, единственным способом, с помощью которогоможно установить факт выхода из строя отдельных узлов - превышение допустимых задержек доставки событий, связанных с ними. Поэтому данноеопределение легко формализуется в виде алгоритма на узле сбора данныхсети.2.5.
Оценка времени жизни динамическиреконфигурируемых сетейРассмотрим задачу оценки времени жизни сенсорных сетей, конфигурации которых меняются с течением времени. Пусть задана сенсорная сеть всоответствии с моделью, описанной в разделе 2.2: = ( , Γ , Π).Необходимо оценить время жизни сети при прохождении стока по заданному маршруту Π. Данная задача имеет большое значение на этапе проектирования сети, когда необходимо выявить узкие места с точки зрения времениавтономной работы.Прежде всего, можно вычислить остаточную энергию узлов после прохождения стока через точек маршрута: () = −∑︁ ·()−=1−1∑︁()−(+1) , = 1..(2.9)=1где () - остаточная энергия -го узла после прохождения стока через ( ≤) точек заданного маршрута Π.59Подставляя вместо получим остаточную энергию узлов по завершениидвижения стока.
Если () < 0, то -й узел выходит из строя до окончаниядвижения стока по маршруту.Оценка времени жизни сети зависит от того, как именно в ней заданытребования по качеству обслуживания, а также от того, как построен маршрут Π. Прежде всего, важно распределение времени нахождения стока напозициях.Если требования к качеству обслуживания таковы, что необходима работа каждого узла сети, время жизни можно оценить следующим образом.Предположим, что при вычислении остаточной энергии узлов найденодин или несколько узлов, для которых остаточная энергия отрицательна.Тогда сеть выходит из строя до окончания движения стока по изначальнозаданному маршруту.
Найдем точку маршрута, на которой происходит выходиз строя первого по счету узла:′ = min( ∈ [1..] : ∃ ∈ [1..] : () < 0). Тогда время жизни сети можно оценить по формуле:′ −1∑︁ (′ − 1) = + min∈[1..](′ )=1(2.10)где (0) = , ∀ ∈ [1..]Если же ∀ ∈ [1..] : () > 0, то есть по окончании движения стокавсе узлы имеют положительную остаточную энергию, потенциальное времяжизни можно оценить разными способами.Например, можно максимально увеличить время пребывания стока напоследней позиции в маршруте, приращение будет равно: ∆ = min∈[1..] ,()а итоговое время жизни сети602 =∑︁ + ∆(2.11)=1Перечисленные выше способы оценки времени жизни можно применятьв тех случаях, когда маршрут строго фиксирован.
Теперь рассмотрим различные оценки времени жизни для случаев, когда можно менять отдельныесоставляющие маршрута. Если есть возможность менять время нахождениястока на других позициях, кроме последней, целесообразно выбрать такуюпозицию , которая обеспечила бы максимальное приращение ∆:∈[1..] () = argmax min∈[1..]Время жизни сети в этом случае будет равно:3 =∑︁∈[1..] () + min=1(2.12)Наконец, можно пропорционально увеличить время нахождения стокана всех позициях. Мультипликативный коэффициент в этом случае будетравен =∑︀−1 − =1 ()−(+1)∑︀min∈[1..],=1 ·()а потенциальное время жизни сети:4 = ∑︁(2.13)=1Однако все вышеперечисленные подходы, скорее всего, приведут к неоптимальному итоговому распределению времени нахождения стока на разныхпозициях с точки зрения максимально возможного времени жизни сети.
Ниже приведена постановка задачи для случая, когда последовательность перемещения стока фиксирована, однако можно варьировать время нахождениястока на всех позициях.Пусть имеется маршрут стока Π, необходимо для каждой точки марш61рута с индексом ∈ [1..] найти такое оптимальное время нахождения стокана ней , чтобы общее время работы сети было максимальным.В общем случае в маршруте задано отображение множества ={1, 2, .
. . , } индексов точек маршрута на множество . Обозначим ′ =(), = | −1 ()|, ∈ .Далее сформулируем следующую оптимизационную задачу линейногопрограммирования:5 ( , ∈ ′ ) =∑︁ → (2.14)∈′при ограничениях:∑︁· +∈′−1∑︁()−(+1) ≤ , = 1..(2.15)=1 ≥ · , ∈ ′ ,(2.16)где - минимальное время нахождения стока на каждой из позицийЦелевая функция 5 является временем жизни сети при условии чтокаждый узел во время движения стока работает в рамках своего начальногозапаса энергии. Последнее обеспечивается набором ограничений (2.15). Первая сумма в каждом неравенстве (2.15) представляет собой общую энергию,затрачиваемую -м узлом на обработку и пересылку данных, вторая - энергию, затрачиваемую на перенастройку сети при перемещении стока.
Наборограничений (2.16) гарантирует, что на каждой позиции сток будет находиться по крайней мере .Задача (2.14) может быть решена одним из стандартных методов линейного программирования [2, 38]. В результате будет получен набор величин , ∈ ′62На последнем шаге искомые величины ( ∈ [1..]) определяются поформуле: =()()Заметим, что если время нахождения стока на некоторых позициях изначально фиксировано, то можно легко модифицировать задачу (2.14), изменивнеобходимые ограничения из набора (2.16) на следующие: = ,где - фиксированное время нахождения стока на -й позиции.Все рассмотренные выше оценки времени жизни сети являются также характеристиками маршрутов. Поэтому, имея множество заданных маршрутов{Π1 , Π2 , . . .
, Π }, можно выбирать наилучший, используя одну или совокупность оценок (2.10) - (2.14).2.6. Выводы к главе 21. Во второй главе описана разработанная математическая модель БСС,позволяющая оценивать время ее жизни для фиксированных маршрутов движения стока, а также оптимизировать время нахождения стокав точках маршрута по критерию максимизации времени жизни. Модель отличается от существующих тем, что описывает функционирование каждого узла сети интегральной характеристикой потребляемойим мощности, а также учитывает последовательность смены конфигураций сети и связанные с ней накладные расходы.2.
Разработана методика расчета параметров модели, учитывающая последние работы по тематике исследования и особенности современных63беспроводных стандартов передачи данных. В частности, процесс передачи данных представлен в виде последовательности переходов устройства между различными режимами. Итоговое значение мощности, потребляемой устройством при передаче данных, зависит от многих параметров, ниже приведены основные из них:∙ Характеристики аппаратных решений∙ Интенсивность потоков данных∙ Алгоритмы доступа к среде передачиДанные зависимости будут исследоваться при имитационном моделировании БСС.3.
Выявлено большое разнообразие подходов в определению времени жизни сети как распределенной системы. Предложено новое определение,учитывающее способность БСС к самовосстановлению.4. Предложены варианты оценки времени жизни реконфигурируемых сенсорных сетей с использованием разработанной модели.64Глава 3Метод динамической реконфигурациисенсорной сети с мобильным стоком3.1. ВведениеВ главе рассмотрен метод динамической реконфигурации автономныхбеспроводных сенсорных сетей с мобильным стоком.
Дается постановка общей задачи планирования движения стока (ПДС). Далее рассматриваютсядва варианта ее решения в зависимости от входных данных:1. Узлы имеют устойчивый характер функционирования, выраженный внеизменной потребляемой мощности в каждой из возможных конфигураций (топологий) сети.2. Условия функционирования сети могут изменяться, как следствие, мощность, потребляемая узлами, также меняется со временем.Для первого варианта предлагается метод нахождения оптимальногомаршрута стока путем решения оптимизационной задачи частично-целочисленного линейного программирования.
Также рассматривается приближенный метод, позволяющий решать задачи большой размерности.Для второго сценария рассматривается несколько эвристических алгоритмов, в том числе новый алгоритм GML.653.2. Общая задача планирования движения стокаПусть задана реконфигурируемая сенсорная сеть в соответствии с моделью, представленной в 2.2: = ( , Γ , Π)Исходными данными для общей задачи планирования движения стока (ПДС) являются граф конфигураций и множество сетевых графовΓ .
Необходимо найти оптимальный маршрут стока Π по критерию максимизации времени жизни сети, то есть определить как последовательность(1 , 2 , . . . , ), 1 ≤ ≤ перемещения стока по позициям, так и время его нахождения на каждой из позиций.Следует напомнить, что в разделе 2.5 рассмотрен частный случай задачи, когда последовательность перемещений стока заранее задана. Теперь жерассмотрим более общий случай.Сначала приведем постановку задачи, встречающуюся в работах других авторов [21] и которая положена в основу предлагаемого далее метода.Она важна по двум причинам.
Прежде всего, она дает верхнюю оценку возможного времени жизни сети. Во-вторых, ее можно использовать для случаяпредсказуемой мобильности стока (см. далее раздел 3.2.1). (1 , 2 , . . . , ) =∑︁ → (3.1)=1при следующих ограничениях∑︁ ≤ ,=166 = 1..(3.2) ≥ 0, = 1..(3.3)Целью задачи оптимизации (3.1) является максимизация суммарноговремени пребывания стока на всех позициях, что является общим временемавтономной работы сети при условии, что каждый узел работает в рамках своего начального запаса энергии .
Последнее гарантируется набором ограничений (3.2). Результатом решения задачи будет набор значений (1 , 2 , . . . , ).∑︀ = =1 является верхней границей возможного времени жизни сети. В дальнейшем она будет называться OPT. Рассмотрим, как решение задачи (3.1) можно использовать для случая предсказуемой мобильности стока.3.2.1. Предсказуемая мобильность стокаВ случае предсказуемой мобильности стока его движение не контролируется самой сетью, однако с большой долей вероятности можно предсказатьего положение в каждый момент времени.Рис. 3.1. Предсказуемая мобильность стокаНа рис. 3.1 представлен случай циклического движения мобильного агента по заданной траектории.
Пусть общий период циклического движения мобильного агента - , а время его нахождения на каждом из участков траектории - 1 , 2 , . . . , 67Каждый участок связан с определенной сетевой топологией (конфигурацией). Поскольку последовательность смены топологий определяется внешними по отношению к сети факторами, задача оптимизации сводится к вычислению общего времени использования каждой конфигурации.Пусть в результате решения задачи (3.1) получено некоторое распределение времени действия энергетических схем: (1 , 2 , . . . , ).
Тогда существуетдве основные возможности осуществлять динамическую реконфигурацию сети в описанном выше сценарии предсказуемой мобильности:1. Сеть сначала полностью работает в режиме, определяемом нахождением стока на первом участке траектории (в течение времени 1 ). Этоможет потребовать многократного прохождения стока по циклическому маршруту. Пока общее время работы в первом режиме не достигнетоптимального 1 , другие режимы не задействуются. Только по достижении границы 1 происходит переход ко второй конфигурации, котораяв свою очередь может быть использована только во время нахождения стока на втором участке траектории.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
