Диссертация (1137248), страница 6
Текст из файла (страница 6)
Оптимизация движения стока внутри каждого сегмента по критериюмаксимизации времени жизни узлов. Для решения предлагается методдинамического программирования. Однако в результате решения находится только последовательность движения стока, которая не включаетв себя распределения времени его нахождения на позициях, входящихв маршрут.Все рассмотренные выше модели и методы реконфигурации сети с помощью мобильного стока не определяют последовательности смены конфигураций в единой неразделенной сети.
Она является важной по нескольким причинам. Прежде всего, именно данная последовательность задает алгоритмдвижения мобильного агента. Кроме того, она может вносить изменения висходные данные задачи. Поясним последнее утверждение более подробно.Во-первых, в реальных системах смена конфигураций связана с определенными накладными расходами в виде дополнительной энергии, затрачиваемой узлами, например, для перенастройки таблиц маршрутизации.Но куда более важным является необходимость учета ограничений, накладываемых на возможные перемещения стока. Эти ограничения могут быть34обусловлены картой местности, наличием физических препятствий, мешающих прямому переходу между позициями, и другими причинами.
Как былосказано выше, одним из преимуществ использования управляемой мобильности стока является сохранение в допустимых пределах задержек передачиинформации, так как сеть по-прежнему работает в режиме связного графа смногозвенной трансляцией данных. Вместе с тем для того, чтобы задержкиоставались небольшими, и учитывая конечную и зачастую небольшую скорость перемещения стока, необходимо также вводить ограничения в его возможных движениях.В настоящей диссертационной работе ставится задача построения общеймодели реконфигурируемой сети с мобильным стоком, узлы которой работают от автономных источников питания, при этом основное внимание уделяется вопросу оценки фиксированных маршрутов стока и нахождения оптимальных маршрутов по критерию максимизации времени жизни сети.1.5. Выводы к главе 1Таким образом, проведенный анализ открытых источников показал, чтобеспроводные сенсорные сети являются перспективной технологией в областисоздания бытовых и промышленных систем сбора данных и управления.Ключевым показателем БСС, определяющим их применимость на практике, является время их жизни, задача его увеличения по-прежнему являетсяактуальной.Использование мобильного стока является одним из наиболее перспективных методов увеличения времени жизни сети.
Наличие подвижного узладает возможность осуществлять динамическую реконфигурацию системы сцелью выравнивания мощности, потребляемой различными ее элементами.В литературе описан ряд моделей реконфигурируемых сетей, однако все35они рассматривают частные сетевые структуры - кольцо, решетку. Необходима более общая модель, которая позволяла бы оценивать время жизни сети ирешать задачу максимизации данного времени путем изменения различныхпараметров работы сети. Также необходимо провести более детальный анализвозможных подходов к определению времени жизни сети как комплексной системы.
Данные задачи рассматриваются в следующих главах диссертации.36Глава 2Математическая модель реконфигурируемыхБСС2.1. ВведениеВ главе рассмотрена модель сенсорной сети, позволяющая оценивать время ее жизни при динамических реконфигурациях. Приведена методика расчета ключевых параметров модели.Детально исследуется понятие времени жизни сети. Его определение ирасчет сводится к двум основным подзадачам:1. Определение времени жизни каждого устройства сети.2. Определение времени жизни сети в целом.Проводится анализ существующих подходов к определению времени жизни сети как распределенной системы, предлагается новое определение, учитывающее ее способность к самовосстановлению.В заключительном разделе главы рассматриваются различные оценкивремени жизни динамически реконфигурируемой сети с использованием предложенной модели.2.2.
Модель реконфигурируемой сенсорной сетиЗададим реконфигурируемую сеть в виде следующей тройки: = ( , Γ , Π),37(2.1)где = ( , ) - граф конфигураций сетиΓ = { (), ∈ } - множество сетевых графов, каждый элемент которогоопределяется конфигурацией сети .Π = (< 1 , 1 >, < 2 , 2 >, .
. . , < , >) - последовательность смены конфигураций, где ∈ - номер конфигурации, - время ее использования.Граф конфигураций состоит из множества вершин = {1, 2, . . . , }и множества ребер : ⊆ × . в общем случае задает возможныесостояния, в которых может находиться сеть. Применительно к рассматриваемым далее в диссертации методам состояние определяется положением мобильного стока.
Например, на рис. 2.1 организован в виде решетки 4 × 4,переходы стока возможны только по горизонтали и вертикали между соседними вершинами.Рис. 2.1. Управляемая мобильность стокаЕсли рассмотреть более общий случай с несколькими мобильными стоками, каждый из которых может занимать одну из позиций, то количество38состояний определяется выражением:(︂ )︂!| | =,=!( − )!где - количество стоков, ≤ .Возьмем другой метод энергетической балансировки - чередование ближней и дальней передачи [79]. Предположим, что каждый узел может работатьв двух режимах передачи - ближнем и дальнем.
В ближнем режиме он передает информацию своему ближайшему соседу, в дальнем - стоку сети безретрансляции. Если в сети узлов и считается, что каждый узел выбираетсвой режим независимо от других, возможно следующее количество конфигураций:| | = 2Заметим, что в последнем случае количество состояний зависит от количества узлов сети. В случае мобильного стока такой зависимости нет.Каждый из графов, входящих во множество Γ задает беспроводнуюсеть: () = ( , ), ∈ , где - множество вершин, ⊆ × множество ребер. Вершины соответствуют узлам сети, ребра - установленнымбеспроводным каналам передачи данных.
= ∪ состоит в общем случае из сенсорных узлов = {1 , 2 , . . . , }и узлов-стоков = {1 , 2 , . . . , }.Каждый сенсорный узел = ( , , Σ ) характеризуется своей начальной энергией , набором мощностей = (1 , 2 , . . .
, ), где представляетсобой мощность, потребляемую -м узлом, при использовании -й конфигурации сети, и матрицей энергий Σ = |− |× , где − - дополнительнаяэнергия, затрачиваемая -м узлом при переходе сети от -й конфигурации к-й, ((, ) ∈ ). Таким образом, главной отличительной особенностью пред39лагаемой модели является то, что работа любого сетевого узла выражаетсяинтегральной характеристикой потребляемой им мощности.Сток представляет собой специальный тип идеального узла, для которого начальная энергия принимается неограниченной: = ( → ∞), ахарактеристики потребляемой мощности не являются важными.Отметим, что далее в работе рассматривается только случай с однимстоком.Последним элементом модели является последовательность смены конфигураций или маршрут стока Π, состоящий из пар < , >, где ∈ позиция стока на -м шаге, - время нахождения на ней.Рассмотрим ограничения предложенной модели.
Прежде всего, модельприменима только для сетей с устойчивым характером функционированияузлов, выраженным в неизменной потребляемой мощности в каждой из возможных конфигураций. Как будет показано далее, потребляемая мощность напрямую зависит от трафика, генерируемого и ретранслируемого узлом.Это не позволяет использовать модель в сетях общего вида с изменяющимся трафиком, однако для сенсорных сетей, в которых объемы передаваемыхданных можно оценить заранее, это не является столь существенным.Также модель не описывает процесс передачи данных при перемещениистока. При необходимости он может быть учтен в виде дополнительной энергии в матрице Σ , однако в дальнейшем будет считаться, что в процессе перемещения стока передача полезных данных в сети не ведется.Далее рассматривается методика расчета ключевых параметров предложенной модели.402.3.
Расчет потребляемой мощности и времени жизниузлов БССВ целом понятно, что узел беспроводной сети сбора данных можно считать работающим, пока он может безошибочно считывать показания с датчиков, производить необходимые вычисления и передавать данные в сеть. Приразработке и установке сети важно заранее оценить приблизительное времяработы каждого узла до момента, когда будет необходима замена его батарей.Для этого важно понимать, какие факторы влияют на продолжительностьвремени его автономной работы.В частности, хорошо известно, что энергопотребление отдельных элементов сети зависит от следующих факторов, которые необходимо принимать вовнимание при моделировании БСС:∙ Характеристики аппаратных средств (емкость батарей, потребляемаямощность микроконтроллера, приемопередатчика, датчиков и прочихэлектронных компонентов).∙ Частота сбора и передачи данных, зависящая от приложения.
Например, в широко распространенных системах климат-контроля, экологического мониторинга достаточно собирать информацию раз в несколькосекунд или даже десятков секунд, поскольку такие параметры как температура или влажность меняются плавно. Как следствие, большуючасть времени сенсор может находится в режиме сна. В то же времяпередача звука требует высокой частоты сбора данных (8 кГц, 16 кГц,32 кГц и более), что фактически исключает возможность нахожденияэлемента сети в режиме пониженного энергопотребления.∙ Протоколы физического и канального уровней, определяющие, прежде всего, механизмы контроля доступа к среде. В асинхронном режиме41доступа к среде, например, CSMA/CA [51], ретрансляторы не могут находиться в режиме сна, в противном случае оконечные устройства несмогут передать свои данные.
Синхронный режим доступа к среде характеризуется тем, что все элементы могут на некоторое время уходитьв режим пониженного энергопотребления, так как функционированиевсей сети координируется специальными синхрофреймами (все элементы сети знают время передачи следующего такого кадра). Однако данный режим сложно реализовать в распределенных сетях, в которыхиспользуются десятки или сотни маршрутизаторов. Тем не менее ужеразработан ряд алгоритмов и протоколов, направленных на уменьшениепотребляемой мощности устройств сети: Berkeley MAC (B-MAC) [60],Sensor MAC (S-MAC) [78], D-MAC [53], адаптивный алгоритм быстройдоставки сообщений [6].∙ Топология сети, определяющая объем информации, проходящий черезкаждый элемент (с учетом ретрансляции сообщений). В сенсорных сетях применяются как простые топологии (звезда, кольцо, дерево), таки более сложные ячеистые структуры.∙ Используемый протокол маршрутизации, добавляющий в сеть дополнительный служебный трафик.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
