Введение к работе
Актуальность работы Сенсорные сети представляют собой новый тип беспроводных сетей Сенсорная сеть состоит из множества сенсоров, случайным образом распределенных по исследуемой поверхности, и базовой станции Сенсор — это автономное беспроводное устройство с ограниченными ресурсами Задачей сенсора является сбор информации и ее передача базовой станции Каждый сенсор — это устройство, состоящее из пяти базовых компонент датчик, процессор, память, беспроводной передатчик и источник питания Ресурс источника питания обычно ограничен, что фактически определяет время жизни сенсора, тесно связано с его вычислительными возможностями и влияет на мощность передатчика В настоящее время сфера применения сенсорных сетей довольно обширна мониторинг окружающей среды и среды естественного обитания, раннее диагностирование поломок устройств в промышленности, управление дорожным движением, контроль за безопасностью объектов Целью протокола передачи пакетов является надежная доставка сообщений по маршрутам, построенным протоколом маршрутизации как между сенсорами и базовой станцией, так и между отдельными сенсорами В данной диссертационной работе рассматриваются протоколы передачи, качество которых оценивается с учетом следующих критериев надежность (всроягпость доставки), оперативность (время доставки), экономичность (энергозатраты) Основным источником ненадежности являются компрометированные узлы, удаляющие пересылаемые через них пакеты
Известные протоколы передачи пакетов для сенсорных сетей не учитывают критерии надежности, оперативности и экономичности, что обуславливает дальнейший интерес к разработке протоколов надежной передачи пакетов а также к разработке алгоритмов, которые управляют такой передачей
Целью работы является разработка и исследование алгоритмов, которые управляют передачей пакетов в сенсорной сети
Для достижения поставленной цели в работе решались следующие основные задачи
исследование существующих алгоритмов надежной передачи пакетов в сенсорных сетях,
разработка нового алгоритма надежной передачи пакетов, учитывающего требования по надежности, оперативности и экономичности,
разработка алгоритмов для нахождения оптимальных параметров нового алгоритма надежной передачи пакетов,
разработка алгоритма контроля живучести сети при использовани нового алгоритма надежной передачи пакетов
Методы исследования, для решения поставленных задач в работе используются методы теории кодирования дискретной оптимизации, системного анализа и теории сложности алгоритмов
Научной новизной обладают следугощие результаты работы
алгоритм адаптивной избыточной передачи (АИП) пакетов, учитывающий требования надежности, экономичности и оперативности,
алгоритм нахождения оптимальных параметров для алгоритма АИП при передаче однопакетных сообщений, учитывающий ограничение на максимальную сложность,
алгоритм нахождения оптимальных параметров для алгоритма АИП при передаче многопакетных сообщений учитывающий ограничение на максимальную сложность,
алгоритм контроля живучести сети при использовании алгоритма АИП
Практическая ценность данной работы определяется тем, что предложенный алгортитм адаптивной избыточной передачи пакетов способствует как повышению надежности передачи, так и понижению энергозатрат сети Результаты работы использовались в учебном продессе Санкт-Петербургского государственного университета аэрокосмического приборостроения
Апробация результатов работы. Основные положения и результаты диссертации докладывались и обсуждались на международном симпозиуме по проблемам избыточности в информационных и управляющих системах (2007), на IX, X научных сессиях аспирантов ГУАП (г Санкт-Петербург 2006, 2007) а также на семинаре кафедры "Безопасности информационных систем" ГУАП Зарегистрирована программная разработка в отраслевом фонде алгоритмов и про! рамм регистрационный помер Гос ФАП 50200601922, 2006 г
Публикации. По теме диссертации опубликовано 5 печатных работ, в том числе 2 статьи в рецензируемых журналах по перечню ВАК
Основные положения, выносимые на защиту
Алгоритм адаптивной избыточной передачи пакетов для сенсорной сети
Алгоритм нахождения оптимальных параметров алгоритма АИП при передаче однопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у других алгоритмов
Алгоритм нахождения оптимальных параметров алгоритма АИП при передаче многопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у других алгоритмов
Алгоритм контроля живучести сенсорной сети, увеличивающий срок жизни сети по сравнению с аналогами
Структура работы Диссертационная работа состоит из введения, 4 разделов, заключения и списка использованных источников. Работа содержит 104 страницы, в том числе 99 страниц машинописного текста, включая 1 таблицу и 20 рисунков, а также 10 рисунков на 5 страницах В списке используемой литературы 65 наименований
Во введении обоснована актуальность темы диссертации, сформулированы цели диссертационной работы и основные задачи, основные по-
ложения, выносимые на защиту, кратко изложено содержание работы по разделам
Первый раздел посвящен алгоритмам надежной передачи пакетов в сенсорных сетях и постановке задаче управления передачей В подразделе 1 1 приводится общая информация о сенсорной сети В подразделе 1 2 дан обзор источников ненадежности при передаче пакетов и известных алгоритмов надежной передачи пакетов Подраздел 1 3 описывает модель рассматриваемой сенсорной сети В подразделе 1 4 изложен разработанный алгоритм адаптивной избыточной передачи, для нахождения оптимальных параметров которого в подразделе 1 5 сформулирована оптимизационная задача Раздел завершается выводами
Сенсорная сеть состоит из множества сенсоров, распределенных по некоторой поверхности, и базовой станции, управляющей сетью Сенсор состоит из следующих компонент датчик, низкопроизводительный процессор, небольшой объем памяти, маломощный приемопередатчик и ограниченный источник питания Сфера применения сенсорных сетей довольно обширна и включает в себя контроль за окружающей средой, раннее диагностирование неисправностей в системах промышленного применения, контроль и управление дорожным движением, контроль безопасности зданий и других объектов.
Целью протокола передачи пакетов является надежная доставка сообщений по маршрутам, построенным протоколом маршрутизации как между сенсорами и базовой станцией, так и между отдельными сенсорами В данной работе рассматриваются протоколы передачи пакетов, качество которых оценивается с учетом следующих критериев надежность (вероятность доставки), оперативность (время доставки), экономичность (энергозатраты)
В сенсорной сети надежность передачи не является идеальной Потери пакетов могут происходить как по естественным причинам, так и вследствие действий атакующих Среди естественных причин можно выделить естественный шум в беспроводной среде передачи, отказы отдельных сенсоров а также конфликты при множественном доступе к каналу Основная атака на алгоритм передачи состоит в том, что компрометированный узел удаляет пересылаемый через него пакет Под компрометированным узлом понимается узел, который был захвачен, из него были извлечены все криптографические ключи, л его программное обеспечение было заменено Под ошибкой передачи понимается ситуация, при которой сообщение, посланное узлом-отправителем, не может быть восстановлено на узле-получателе из-за потерь пакетов на промежуточных узлах
Оперативность передачи важна с точки зрения приложений сенсорной сети, например, для передачи сообщений о тревоге
Не менее важной характеристикой являются энергозатраты Как уже упоминалось выше, сенсор оснащен лимитированным источником питания Поэтому время жизни сенсора напрямую связано со скоростью расходования его источника питания Передача и прием пакетов являются наиболее энергоемкими операциями, выполняемыми сенсором Особенно важным
этот критерий делает то, что сенсор не только посылает в сеть свои пакеты, но и пересылает пакеты от других узлов С энергозатратами также связана еще одна важная характеристика, называемая живучестью Цель поддержания живучести сети заключается в том, чтобы в сети поддерживался запас источников питания узлов для передачи срочных однопакетных сообщений (сигналов тревоги) с максимальной скоростью и надежностью со всех возможных направлений
Наиболее эффективным средством борьбы с удалением пакетов являются алгоритмы передачи по нескольким маршрутам Используется два основных подхода случайная передача и передача с избыточностью В обоих подходах предполагается, что имеется несколько маршрутов между отправителем и получателем Желательно, чтобы эти маршруты были независимыми Это означает, что маршруты либо вообще не пересекаются, либо пересекаются только по надежным узлам
При случайной передаче отправитель для каждого пакета выбирает один из маршрутов случайным образом С одной стороны, алгоритмы случайной передачи не требуют много энергии, тк на каждом шаге маршрута используется только один узел С другой стороны, такой алгоритм не позволяет говорить о передаче с заданным уровнем надежности, те о доставке с заданным порогом на величину возможной ошибки
При передаче с избыточностью передача ведется одновременно по всем имеющимся маршрутам При этом используются как простое дублирование сообщения но всем маршрутам, так и более эффективные схемы на основе помехоустойчивого кодирования (такие методы называются транспортным кодированием) Дублирование может быть рассмотрено как частный случай транспортного кодирования В транспортном кодировании пакеты, составляющие сообщение, рассматриваются как элементы некоторого алфавита, а само сообщение представляется как информационный вектор длины к из этих элементов Информационный вектор кодируется (п, к) помехоустойчивым кодом в кодовое слово длины п В качестве помехоустойчивого кода используется код Рида-Соломона Символы получившегося кодового слова рассматриваются как пакеты и посылаются по п маршрутам. Для восстановления исходного сообщения достаточно получить любые к пакетов
Известные алгоритмы передачи пакетов по нескольким маршрутам не могут быть эффективно применены в сенсорной сети Так как ни в одном из них не гарантируется качество передачи, тк не формулируются требования по надежности, энергозатратам и оперативности Это вызвано тем, что в этих алгоритмах по каждому маршруту передается одна копия пакета В диссертации предложена модификация алгоритма избыточной передачи, которая позволяет учесть описанные требования В работе описаны следующие основные ограничения модели рассматриваемой сети как среды передачи сообщений
1 Используется централизованное управление сетью, которое осуществляет базовая станция
Для передачи управляющей информации от базовой станции не используются промежуточные узлы
В сети предполагается передача нескольких типов сообщений: штатных однопакетных, срочных однопакетных, многопакетных Сообщения могут иметь, например, следующее назначение штатные однопакетные — подтверждения работоспособности сенсора, срочные однопакетные — сигналы тревоги, многопакетные — затрубленный вариант изображения
Существует множество маршрутов ог каждого сенсора до базовой станции
В сети происходят потери пакетов, которые могут быть вызваны как естественными причинами, так и действиями атакующих
Потери пакетов на одном маршруте являются независимыми событиями Потери пакетов на разных маршрутах являются независимыми событиями. Предложенный алгоритм надежной передачи пакетов основывается на этом свойстве Для того, чтобы контролировать состояние маршрутов при передаче с избыточностью, базовая станция ведет рейтинги каждої о маршрута, как это предложено в одном из известных алгоритмов избыточной передачи Передаваемые пакеты несут в себе информацию о числе копий, посланных по другим маршрутам Поэтому, если хотя бы один пакет из посылки дойдет до базовой станции, то она получит информацшо о том, сколько пакетов и на каких маршрутах было потеряно На основе этой статистки строятся два рейтинга краткосрочный (контролирует резкое увеличение числа потерянных пакетов) и долгосрочный (контролирует общее число потерянных пакетов) Превышение любым из рейтингов нороіа приводит к исключению маршрута
Компрометированный узел не может удалить все передаваемые через него пакеты, т к он будет быстро обнаружен Кроме того, он не может удалить большое число подряд идущих пакетов, поскольку это приведет к ухудшению краткосрочного рейтинга маршрута Наилучшей маскировкой для атакующего узла является удаление пакетов в соответствии со схемой Бернулли
Если компрометированные узлы находятся на разных маршрутах и координируют свои действия путем удаления пакетов из одной посылки, то их нельзя выявить с помощью краткосрочного рейтинга, поскольку в этом случае резкого увеличения числа потерянных пакетов на одном маршруте не происходит Однако, ненадежность данных маршрутов будет выявлена с помощью долгосрочного рейтинга
Кроме перечисленных ограничений учитываются также следующие допущения Время функционирования сети поделено на этапы В начале каждого этапа сенсоры присылают базовой станции следующую информацию
список своих соседей, среднее количество переспросов при пересылке пакетов для каждого соседа, собственный уровень энергозапаса источника питания По собранным данным базовая станция разбивает сеть на кластеры, выбирает внутри кластера главу кластера (он же является агрегатором), строит маршруты до глав кластеров и выбирает для них параметры алгоритма надежной передачи Затем всем узлам рассылается информация о делении на кластеры и маршрутизационные таблицы, а агрегаторам — еще и информация о параметрах алгоритма надежной передачи пакетов В течение этапа базовая станция обменивается сообщениями с сенсорами, ведет рейтинги маршрутов а также следит за живучестью сети. При превышении рейтингами порогов или для поддержания живучести сети отдельные маршруты могут быть отключены Отключение маршрутов или значительное изменение их рейтингов вызывает необходимость пересчитать параметры алгоритма надежной передачи пакетов или даже вьшолнить частичную ремаршрутизацию Результаты пересчета параметров передачи должны быть отправлены сенсорам
Для известных алгоритмов передачи пакетов невозможно добиться выполнения требований на заданную вероятность ошибки передачи Это вызвано тем, что в этих алгоритмах по каждому маршруту передается одна копия пакета
Предлагается для выполнения ограничений на ошибку передачи передавать несколько копий пакета по каждому маршруту, т е по г-му маршруту передастся щ копий пакета Передача нескольких копий но одному маршруту имеет смысл, поскольку в описанной нами модели сети потери пакетов на маршруте являются независимыми событиями Количество пакетов, которое должно быть передано по каждому маршруту, предполагается рассчитывать путем решения оптимизационной задачи При формулировке оптимизационной задачи используется информация о характеристиках маршрутов, поэтому данный алгоритм можно назвать Адаптивной Избыточной Передачей (АИП)
Используются два алгоритма передачи с избыточностью дублирование и транспортное кодирование Дублирование используется для однопакет-ных сообщений (штатных и срочных) Транспортное кодирование используется для больших сообщений, состоящих из нескольких пакетов Определить число пакетов, которое необходимо послать по каждому из маршрутов, можно на основе решения оптимизационной задачи В этой задаче должны быть учтены ограничения на вероятность ошибки, энергозатраты на передачу и требования по оперативности
В работе описана информация, которой обладает базовая станция На основе этой информации формулируются энергетические и временные ограничения В начале каждого этапа базовая станция получает от сенсоров информацию о графе сети и следующую информацию о каждом узле г егі3 — энергетические затраты при посылке сенсором г пакета соседу j (вычисляется на основе среднего количества переспросов), tlt] — временные затраты при посылке сенсором г пакета соседу j (вычисляется на основе среднего количества переспросов), vz — энергозапас сенсора г
По этим данным базовая станция вычисляет и присваивает каждому маршруту г следующие величины
Ег — энергозатраты при передаче пакета по маршруту, как функцию от энергозатрат ek,% для всех узлов маршрута
Тг — время при передаче пакета по маршруту как функцию от временных затрат tk,i для всех узлов маршрута
Рг — вероятность потери пакета на маршруте Для новых маршрутов, по которым передача еще не велась, начальное значение этой вероятности принимается равным 0 При передаче по данному маршруту вероятность потери пакета оценивается на основе полученной статистики, т е на основе рейтинга маршрута
Как уже было сказано, для выполнения требования по надежности передачи в работе предлагается передавать по г-му маршруту пг пакетов По одному маршруту пакеты отправляются через интервал г
Оптимизационная задача при передаче с избыточностью формулируется следующим образом Имеется N независимых маршрутов, и каждый маршрут описывается вектором (рг, Ег, Тг) Требуется передаль сообщение, состоящее из к пакетов При этом ошибка передачи Pe{k,N) не должна превосходить р Для этого необходимо найти количество пакетов, которое должно быть передано по каждому маршруту, те найти целочисленное множество (щ, ,njv) (щ Є -Л/"), для которого должны выполняться следующие требования
1 Условие на величину ошибки передачи
Pe(k,N) = Р(т,П2, ,nN)
где функция Р определяется в зависимости от выбранного алі оритма передачи (дублирование или транспортное кодирование)
2 Условие на энергозатраты при передаче
Е{пип2, ,nN) = *22lEz пг-*шш i=i
3 Условие на оперативность передачи
Т(пх,П2, ,nN) = тах.{Тг + г пг} —» mm
г=1 N
Расчет параметров передачи производится в начале каждого этапа жизни сети для всех агрегаторов что увеличивает общую вычислительную сложность расчетов Кроме того, существует ограничение на общее время расчета Ведь чем быстрее сеть адаптируется, тем дольше будет время ее жизни
и тем меньший урон нанесут атакующие Исходя из этих требований для алгоритмов расчета формулируется ограничение на максимальную сложность расчетов
Второй раздел посвящен использованию алгоритма дублирования для передачи однопакетных сообщений Рассмотрено два вида сообщений срочные и штатные В подразделе 2 1 приведены оптимизационные соотношения для задачи управления дублированием В подразделах 2 2 и 2 3 приведены алгоритмы решения оптизационной задачи методом динамического программирования и методом ветвей и границ соответственно В подразделе 2 4 описан гибридный алгоритм, объединяющий преимущества обоих методов и имеющий ограничение на максимальную сложность В подразделе 2 5 приведены результаты моделирования рассмотренных алгоритмов Раздел завершается выводами
Оптимизационная задача для метода дублирования сформулирована ниже
Г рв(і,до = ііРГ*<р
\ = Е,=іДпг^шш (1)
I Г = max(Ti + rni, . ,Тм + ггіц) —> mm
Для срочных сообщений максимальный приоритет имеет критерий Т, а для штатных сообщений — критерий Е Дано р и множества {Г»}г=і n, {Ег}г=і лги{рг}г-і #, требуется найти множество {пг}г=1 jv, гдепг Є AT, т е решить задачу целочисленного программирования Величина г является задаваемой константой
Выражение для Ре{1, N) можно преобразовать к линейному виду, прологарифмировав обе части
Для оптимизации функции такого вида можно использовать метод динамического программирования и метод ветвей и границ
Для решения поставленной оптимизационной задачи был применен алгоритм динамического программирования (ДП) с ограниченной точностью Это означает, что полученный результат является оценкой оптимального решения (которое может быть получено полным перебором) с некоторой hoi ретпшхл ыо За счет уменьшения точности можег бьиь уменьшена вычислительная сложность алгоритма При последовательном переборе (от меньших индексов к большим) но множеству значений вектора (пі, га#) сумма
может принимать произвольные возрастающие значения от 0 до 1 С целью уменьшения вычислительной сложности алгоритма можно уменьшить количество значений, которые может принимать эта сумма, квантуя ее с
некоторым шагом t (например, с шагом t = 0 1) Уменьшение шага квантования уменьшает погрешность результата, но в то же время ведет к увеличению сложности алгоритма Меняя значение шага квантования, можно достичь необходимого компромисса между сложностью и погрешностью результата Перебор ведется построением путей в прямоугольной (1/i) N решетке
В алгоритме ветвей и границ (ВГ) перебор упорядочивается в виде дерева При этом вершины первого уровня соответствуют перебору по первой компоненте вектора щ, вершины второго уровня — по второй компоненте и-2, и так далее до re/v Для того, чтобы сократить перебор, строятся две оценки нижняя оценка текущего решения и верхняя оценка лучшего найденного решения, по которым происходит отсечение бесперспективных ветвей
Верхняя оценка вычисляется как текущее значение целевой функции
при ДОСТИЖеНИИ ЧаСТИЧНОЙ СУММОЙ Sb Значения еДИШЗДЫ, ТЄ Sfr > 1 Из
двух имеющихся оценок в качестве новой лучшей верхней оценки выбирается минимальная по основной целевой функции, а при их равенстве — по дополнительной целевой функции Начальная верхняя оценка и начальное решение строятся с помощью "жадного" алгоритма В "жадном" алгоритме предполагается что для выполнения требований по надежности передача ведется только по одному маршруту с лучшими характеристиками, т е передача по нему обеспечит минимальные энергозатраты по сравнению с друї ими маргггрутами
При построении нижней оценки используется логика, аналогичная примененной в "жадном" алгоритме Выбирается хороший маршрут, и все пакеты, необходимые для выполнения ограничения по вероятности ошибки, отправляются по нему Только в отличие от "жадного" алгоритма, для построения оценки строится гипотетический маршрут, обладающий идеализированными характеристиками Пусть на уровне ъ < N имеется проме-жуточый і\Г-вектор (пііЛ, ,п,л,0, ,0) Из неиспользованных маршрутов с номерами от г + 1 до N строится гипотетический маршрут best с идеализированными характеристиками, тес наилучшими из имеющихся Pbest = тш(рг+ь , par), Ebest = mm(F,+l,. , EN) итд.
Метод динамического программирования выигрывает у метода ветвей и границ по максимальной сложности в то же время метод ветвей и границ имеют лучшую среднюю сложность, а максимальная сложность этого алгоритма равна сложности полного перебора Согласно требованиям к алгоритму расчета, необходим гибридный алгоритм (ГБ) расчета, который объединяет достоинства описанных алгоритмов и при этом имеет ограничение на максимальную сложность
Гибридный алгоритм работает следующим образом Задается максимально допустимое время расчета По этому времени вычисляется максимально допустимая сложность гибридного алгоритма По этой сложности и оценке сложности алгоритма динамического программирования вычисляется порог Выполняется поиск решения алгоритмом ветвей и границ, при этом подсчитывается количество просмотренных вершин в дереве перебо-
pa. Если число просмотренных вершин превышает ворог, а решение еще не найдено, то выполнение алгоритма ветвей и границ прерывается и запускается алгоритм динамического программирования. Гибридный алгоритм как и алгоритм динамического программирования не всегда находит опти-малыгое решение. Точность и сложность гибридного алгоритма оценены с помощью моделирования
Ниже приведены результаты моделирования габридного алгоритма расчета для штатных сообщений. Для срочных сообщений получены похожие результаты.
.-'-_-л НиВЫГ. "*.r.L:j: 'rr.j-'j'.-.,
(а) Сложітосггь алгоритмоп
Holt* rt.-.r^r. >t*gular Є*»А<Сз
(b) Точность ал горите or*
Рис. і. Штатные сообщения. Алгоритмы ВГ, ДП и ГВ.
На графике рисунка 1(a) показаны максимальная сложность алгоритма ветвей и границ (шахВВ), максимальная (тахІГВ) и средняя fftygHB) сложности гибридного алгоритма а также средняя сложность алгоритма динамического программирования. По оси абсцисс отложило число маршрутов (Route Number), а по оси ординат - сложность, измеренная в количестве просмотренных вершин. Из графика эидао, что пібридньїп алгоритм пыигрывает по средней сложности у метода динамического програм мировая;?*, при этом сто мяхеишлыгая сложность зйачитеяьнэ ниже, чем максимальная сложность метода ветвей и границ. Можно сделать ньшод, что гибридный алгоритм выполняет пре.тьян.теїщьге к нему требования но сложности.
На рис. 1(b) отложеіпя отношения целевых функций алгоритмов ДП (DP_E и DP__T) и ГБ (НВЕ и НВТ) к аналогичным оптимальным значения^ выдаваемым алгоритмом ВГ. В алгоритме динамического программирования шаг квантования выбирался равным 0,1. При -этом ип графика виді ці, что максимальная Погрешность составляет 3%.
Третий раздел посвящен применению алгоритма трап с пореного кодирования для передачи многопакетных сообщений. В подразделе 3.1 описаны детали применения кодов Рида-Соломон а для транспортного кодирования. В подразделе 3.2 приведены оптимизационные соотношения дли нахождения оптимальных параметров алгоритма надежной передачи паке-
тов для многопакетных сообщений В подразделах 3 3 и 3 4 соответственно приведены алгоритмы решения оптимизационных задач методом локального поиска и методом ветвей и границ Оба алгоритма объединены в гибридный алгоритм в подразделе 3 5 Результаты моделирования алгоритмов приведены в подразделе 3 6 Раздел завершается выводами
Оптимизационная задача для транспортного кодирования формулируется следующим образом
'Pd(k,N)= Y, С(піДі.Рі) C(nN,kN,pN)
ki+ +kN>k
, l>ki
E = 2^t=l "»"» —* mm
. T = max(Ti + rn\, , TV + rnN) —> mm,
где С(тц,Ь,,Р») = C(l -Pi)KPnS~K
Даны к, p и множества {Гг}г=і jv, {Ег}%=і n, требуется найти множество {пг}г=1 jv, где пг N, те решить задачу целочисленного программирования Величина г является задаваемой константой
Вид функции ограничений не позволяет использовать метод динамического программирования Поэтому приведено решение только алгоритмом ветвей и границ Общая схема метода ветвей и границ описана в разделе 2 Основное огличис состоит в методе подсчета гокущего значения функции ограничения Pd(k, N) Подсчет функции ограничения, выполняемый в каждой вершине дерева перебора, является вычислительно сложной процедурой, сложность которой оценивается как С^,1 ,„ . Для ускоре-ния этих вычислений предлагается использовать следующую рекурсивную формулу
Е ЦС(пг,кг,рг) =
fci+ +кы>кг=1 /г\
лдг N-l \)
= 2 c(nN,kN,pN) X) П сіщіКіРі)
Таким образом, величина функіщи ограничения в вершине г-го уровня дерева вычисляется через значения, сохраненные в вершине-предке на предыдущем уровне (г — 1) Гибридный алгоритм для определения параметров транспортного кодирования выглядит следующим образом Устанавливается порог на максимальное число вершин, которые могут быть просмотрены в дереве перебора При превышении порога текущая верхняя граница рассматривается как найденное решение Затем производится попытка улучшить полученный результат с помощью алгоритма локального поиска с низкой сложностью С помощью этого алгоритма число операций, которое необходимо произвести в вершино г уровня для вычисления функции ограничений, сведено к пг Также потребуется пг ячеек памяти
Основным недостатком алгоритма ветвей и границ является то, что его максимальная сложность равна сложности полного перебора Это несовместимо с требованиями, предъявленными к алгоритму расчета Гибридный
алгоритм для определения параметров транспорте го го кодирования выгля-дит следующим образом. Устанавливается порог на максимальное -число вершин, которые могут быть просмотрены в дереве перебора. При превышении порога, текущая верхняя граница рассматривается "как найденное решение.
а « « * і» a it it 7 * t # і* is і» іб
HMU №:пь*т. У-'-:i.p*e>- ше*лэ*« Haute Hurter, Ниіььрчсїлс at»a*g*»
fa) Сложность алгоритмов (Ь) Точность алгоритмов
Рис. 2. М/гогоггзкетные (твобгдоння. Алгоритмы ВГ к ГБ.
Путем моделирования был вьібр.їк олпшальный порог для максимальной сложности и 2000 вершин. При данном пороге погрешность вычислений составляет ке более 1%. На графике на ряс. 2(a) доказаны средняя (avgHB) и максимальная сложность ImaxHB) гибридного алгоритма, а также максимальная сложность (гаахВВ) Алгоритма ветвсїї и границ. График на рис 2(b) показывает, что при ныСранном ограничении гибридный алгоритм имеет досгаточ^о малую гюг'решноси».
В четвертом разделе производится оценка качества предложенного іілгоритма падежной передачи пакетов для сенсорной сети и его сравнение с Существующими решениями, Кроме того, рассматривается алгоритмі сохранения живучести сети при использовании АИП В подразделе 4.1 проводится сравнение предложенного алгоритма надежной передачи пакетов и существующих решений. В подразделе 4.2 рассмотрен дополнительный критерий управления: поддержание живучести сети. Раздел завершается выводами.
Для сравнения рассмотрены следующие известные алгоритмы: алгоритм случайной передачи (СП) и алгоритм передачи с избыточностью (ИП). При случайной передаче отправитель для доставки пакета выбирает одни из маршрутов случайным образом. При передаче с избыточностью но каждому из маршрутов посылается ровно одна копия пакета. В этих алгоритма;; не используются данные о характеристиках маршрутов, поэтому эти алгоритмы можно назвать не адаптивным и. Предложенный алгоритм адаптивной избыточной передачи (АИП) использует знания о характеристиках маршрутов. На основе этих данных для юіждого из маршрутов определяется количество копий, которое должно быть по нему послано.
В отличие от алгоритма АИП для алгоритмов СП и ИП невозможно добиться заданной вероятности ошибки при передаче пакетов, поскольку по маршруту посылается только одна копия пакета Поэтому для корректного сравнения считается, что в алгоритмах СП и ИП передача может осуществляться п раз, где п определяется исходя из требуемой вероятности ошибки
Алгоритм АИП может быть использован для передачи штатных, срочных и многопакетных сообщений, при этом для оценки качества передачи используются критерии энергопотребления и оперативности Алгоритмы СП и ИП предназначены только для передачи штатных сообщений Поэтому сравнение выполнено только для штатных однопакетных сообщений, у которых основным критерием качества является энергопотребление Таким образом, при заданной вероятности ошибки для каждого из алгоритмов оценены энергозатраты на доставку одного штатного сообщения
Проведено сравнение алгоритмов для N маршрутов Пусть имеется N маршрутов с вероятностями ошибки {pt}i[i,N] и энергозатратами {^Kg[i,jv) и задана требуемая вероятность ошибки передачи р
Ниже приведены системы ограничений для алгоритмов СП, ИП Система ограничений и энергозатраты для алгоритма СП имеют вид
Система ограничений и энергозатраты для алгоритма ИП имеют вид
Г(Пл)"<р ^р . bg(p) "
и«»:Еі*-шш ^"-logOT^)^* (7)
Для алгоритма АИП система имеет вид
/а=ірг*<р (s)
\ Е = E,=i Егпг -* mm w
Система (8) является задачей целочисленного линейного программирования Получить конечное выражение для энергозатрат Ещ не представляется возможным, поэтому сравнение энергозатрат /, Ец и Ещ проведено с помощью моделирования Решение оптимизационной задачи для алгоритма АИП проводилось с помощью метода ветвей и границ На рис 3(a) представлен график энергозатрат для алгоритмов СП, ИП и АИП Из графика видно, что алгоритм АИП имеет наименьшие энергозатраты На рис 3(b) показано отношение энергозатрат алгоритмов ИП и АИП Из графика видно, что с увеличением числа маршрутов выигрыш алгориг-ма АИП увеличивается Качественное объяснение полученного вьшгрыша может быть дано следующим образом В алгоритмах СП и ИП не используется информация о характеристиках маршрутов, т е они полагаются равноценными Поэтому выигрыш адаптивный алгоритм должен давать тем
sir ~-*-
EIII *
* -f -X ^
ROU&8 Huiltoer
(а) Энергозатраты при передаче
Route number
(b) Отношение энергозлтрлт при поредлче дли алгоритмов ИП и АИП
Рис 3 Сравнение энергозатрат для алгоритмов СП, ИП и АИП
больший, чем менее равноценными данные маршруты являются В отличие от неадаптивных алгоритмов, которые ведут передачу по всем имеющимся маршрутам, адаптивный алгоритм на основе решения оптимизационной задачи выбирает подмножество маршрутов и передает только по ним
Далее рассмотрен еще один аспект управления передачей, связанный с учетом критерия живучести Цель поддержания живучести сети заключается в том, чтобы в сети поддерживался запас источников питания узлов для передачи срочных однопакетных сообщений (сигналов тревоги) с максимальной скоростью и надежностью со всех возможных направлений
В зависимости от топологии сети и характера трафика, который определяется физическим положением и интенсивностью возникновения наблюдаемых сетью событий, энергоресурсы сети расходуются неравномерно Другими словами, через определенные сенсоры проходит большее число пакетов, чем через остальные узлы сети Энергоресурс таких сенсоров заканчивается быстрее и они выбывают из строя Это приводит к преждевременному истощению, и, следовательно, к недостуїгаости для базовой станции некоторых участков сети В результате такой неравномерной деградации сеть не может выполнить свою основную задачу — сбор информации со всей наблюдаемой территории Под живучестью будем понимать способность сети равномерно деградировать по всем направлениям на базовую станцию
Согласно модели сети базовая станция может оценить текущее состояние источника питания каждого сенсора Множество сенсоров разбивается на несколько классов важности Разбиение делается на основе числа проходящих через сенсор маршрутов В один класс попадают сенсоры, через которые проходит приблизительно одинаковое число маршрутов Если состояние источника питания сенсора значительно отличается от среднего значения данной величины в его классе, то все маршруты проходящие через этот сенсор, временно выключаются
В заключении сформулированы основные результаты диссертационной работы
