Диссертация (1137248), страница 11

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 11)

Другими словами, в0 добавляется связанный подграф с наименьшим суммарным временемпребывания стока.Возможен и другой алгоритм - постепенно наращивать множество 1 дообразования связанного графа ̃︀ . Для этого предлагается следующая эври­стика.76На первом шаге выделяются два подграфа ̃︀ и ̃︀ с наибольшим сум­марным временем пребывания стока.

После этого, используя стандартныеалгоритмы на графах [38], например алгоритм Флойда-Уоршелла, или алго­ритм Дейкстры в том случае, если число вершин в одном из двух графовнебольшое, находятся кратчайшие пути между всеми парами вершин (, ),где ∈ ̃︀ , ∈ ̃︀ . На последнем шаге выбирается кратчайший путь, соеди­няющий ̃︀ и ̃︀ , и добавляется в 1 .3.4. Эвристические алгоритмы динамическогоуправления движением стокаВ реальных системах зачастую невозможно заранее собрать всю инфор­мацию, необходимую для решения задач (3.1), (3.4). Кроме того, ключевыедля модели (2.1) величины могут меняться со временем. Ниже приведенынекоторые из практических сценариев, являющихся возможными причинами:1.

Изменение помеховой обстановки в отдельных зонах. Это может бытьв свою очередь связано с развертыванием новой сети в том же илиблизком частотном диапазоне. В подобном случае увеличивается веро­ятность повторных передач пакетов, и, следовательно, растет энергопо­требление элементов, находящихся в данной зоне.2. Реконфигурация элементов сети. В ряде случаев требуется изменениеалгоритмов работы отдельных устройств.

Например, может потребо­ваться изменение частоты посылки тестовых сообщений.3. Изменение климатических условий функционирования узлов. Как след­ствие, их аккумуляторы могут быстрее истощать свою энергию.77В таких случаях целесообразным является применение динамическогоуправления движением мобильного стока. Для формального описания алго­ритма динамического управления стоком введем несколько дополнительныхобозначений:() - подмножество вершин графа , включающее и смежные с вершины, т.е.

() = {} ∪ { : (, ) ∈ }.Обозначим также через () множество узлов, окружающих -ю пози­цию стока или, другими словами, множество узлов, которые подключаютсянапрямую к стоку, когда тот находится на позиции :() = ∈ : (, ) ∈ (), где ∈ - узел-сток.Общий алгоритм выглядит следующим образом:Алгоритм 2 Общий алгоритм динамического управления стокомВходные данные: , Γ , 0Выходные данные: Маршрут стока Π1: ← 02: цикл пока Сеть работает3:+1 ← Выбор из ( )4:Перейти на позицию +15:Работать в течение времени 6:←+17: конец цикл покаОбщий алгоритм управления движением мобильного стока выглядит сле­дующим образом. На -м шаге алгоритма, находясь на некоторой позиции ,сток выбирает из множества ( ) оптимальное положение на следующем ша­ге +1 , согласно некоторому критерию, после чего переходит на выбраннуюпозицию (либо остается на текущей) и продолжает оставаться на ней в тече­ние некоторого фиксированного времени , которое можно варьировать.Ключевым шагом алгоритма является выбор следующей позиции.

Он,как правило, осуществляется с использованием некоторой эвристики. В ли­тературе было предложено несколько различных эвристик. Самой простой78является случайное движение стока [22], при котором выбор новой позициипроисходит произвольным образом. При том, что согласно приводимым ре­зультатам моделирования, такой подход в большинстве сценариев дает замет­ный выигрыш по сравнению с неподвижным стоком, его результаты в общемслучае никак не гарантированы.В одной из работ было предложено организовать циклическое движениестока по периметру охватываемой сетью области [54].

Подход основан на том,что самые загруженные узлы обычно располагаются в центре сети. Поэтомудвижение по периметру перекладывает часть нагрузки по передаче данныхна узлы, которые обычно наименее загружены.Однако для получения лучших результатов необходимо учитывать пара­метры и состояние функционирования сети в конкретный момент времени.Большинство исследователей в качестве ключевой характеристики состояниясенсорной сети в момент времени используют распределение остаточнойэнергии ее узлов () = {1 (), 2 (), .

. . , ()}, где ()) – остаточнаяэнергия i-го узла.Basagni и др. [21] предложили жадный алгоритм нахождения локально­оптимального плана движения GMRE (Greedy Maximum Residual Energy),согласно которому сток периодически опрашивает соседние кластеры сети иперемещается в кластер с наибольшей остаточной энергией. Таким образом,для стока целенаправленно выбираются соседи с большой остаточной энерги­ей.В этом случае задача динамического планирования движения стока сво­дится к задаче поиска максимума функции остаточной энергии.

Функцияявляется дискретной, область ее определения представляет собой набор воз­можных позиций стока. Есть несколько способов определения данной функ­ции для позиции стока :791. () =1|()|∑︀∈() ()2. () = min∈() ()3. () = max∈() ()Однако независимо от того, как определяется (), информация об оста­точной энергии лишь приблизительно характеризует состояние сети. Можнопривести следующий пример: узел с небольшой остаточной энергией можетпотреблять минимальную мощность и проработать от батарей дольше, чемузел с большой остаточной энергией, но на порядок большей потребляемоймощностью. Однако эвристика GMRE будет приводить сток к большей оста­точной энергии, как следствие, время жизни сети будет меньше, так как по­требляемая мощность отдельных устройств не учитывается.Поэтому в диссертации предлагается альтернативная эвристика: выби­рать на каждом шаге такую позицию, которая обеспечит наибольшее времяавтономной работы сети в том случае, если перемещений стока больше небудет.

Данная эвристика по аналогии с предыдущей названа GML (GreedyMaximal Lifetime).Сведем эвристики динамического управления стоком, которые будут да­лее сравниваться в ходе имитационного моделирования, в таблицу 3.1.ЭвристикаВыбор вершины на следующем шагеRANDOM Произвольный выбор из множества ( )GMRE+1 = argmax GML+1 = argmax∈( ) min∈() Таблица 3.1. Эвристики динамического управления стокомДля применения эвристики GML необходима информация о потребля­емой мощности узлов . Ее можно оценить заранее, согласно методике,приведенной во второй главе, либо динамически по ходу работы сети. Такесли время нахождения стока на некоторой позиции равно , и известна80остаточная энергия каждого узла до ( ()) и после ( ( + )) нахождениястока на -й позиции, тогда потребляемую мощность каждого узла можнооценить по формуле: = () − ( + ), = 1..Отметим, что и GMRE, и GML используют локальную информацию обостаточной энергии, то есть не обеспечивают глобальный взгляд на сеть.

Какследствие, возможно попадание в ловушку локального максимума [4], кото­рый может быть на порядок меньше глобального. Однако применительно кзадаче управления мобильным стоком получение глобальной информации всвою очередь приводит к дополнительным энергетическим затратам и не яв­ляется эффективным.3.5. Выводы к главе 3Таким образом, динамическая реконфигурация позволяет увеличить вре­мя жизни беспроводной сенсорной сети за счет более выравнивания потреб­ляемой мощности между узлами сети.Новый метод динамической реконфигурации БСС заключается в сведе­нии общей задачи планирования движения стока к задаче частично-целочис­ленного линейного программирования, в результате решения которой получа­ется оптимальный маршрут стока по критерию максимизации времени жизнисети.

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

К данной группе относится разработанныйалгоритм GML движения к максимальному времени жизни сети.Для оценки разработанных методов и алгоритмов необходимо провестиимитационное моделирование.82Глава 4Моделирование БСС с мобильным стоком4.1. ВведениеГлава посвящена моделированию времени жизни динамически реконфи­гурируемых БСС, проводимому с целью получения количественных оценокуправляемой мобильности стока, а также нахождения оптимальных условийдля ее использования.На первом этапе исследована возможность проведения натурного экспе­римента на существующих аппаратных платформах, сделан вывод о том, чтополноценный эксперимент при текущем состоянии технических и программ­ных средств сильно затруднен.На втором этапе проведено имитационное моделирование при помощиразработанного комплекса программных средств.4.2.

Исследование возможности проведения натурногоэксперимента4.2.1. Обзор аппаратных платформ для стационарной части сетиС точки зрения оборудования для стационарной части сети, существуетогромный выбор устройств для разных задач. Можно условно разбить весьспектр оборудования на три группы:1. Электронные компоненты - микроконтроллеры, приемопередатчики ипр., являющиеся основой для разработки решений, начиная с самогонизкого уровня.832. Промежуточные платформы, как правило, разрабатываемые исследо­вательскими университетами с целью проведения экспериментов.3. Встраиваемые системы, создаваемые для решения конкретных задач.Теоретически можно провести натурный эксперимент, собрав из отдель­ных компонентов специализированную платформу на базе одного из множе­ства доступных беспроводных модулей, производимых такими компаниямикак Texas Instruments, Atmel, NXP, Telegesis, Freescale и др.Автор диссертационной работы участвовал в совместном российско-гер­манском проекте по созданию системы активного беспроводного сбора дан­ных в интралогистике.

Характеристики

Список файлов диссертации