автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Управление передачей пакетов в сенсорных сетях

На правах рукописи

Линский Евгений Михайлович

Управление передачей пакетов в сенсорных

сетях

Специальность 05 13 01 «Системный анализ, управление и обработка информации (в технике и технологиях)»

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2007

003161150

Работа выполнена на кафедре безопасности информационных систем Государственного образовательного учреждения высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" (ГУАП)

Научный руководитель-

доктор технических наук, профессор Крук Евгений Аврамович

Официальные оппоненты:

доктор технических наук, профессор Никифоров Виктор Викентьевич кандидат технических наук доцент Козенко Сергей Леонидович

Ведущая организация:

Всероссийский научно-исследовательский институт радиоаппаратуры

Защита состоится " Уо " о на заседании д иссертацион-

ного совета Д 212 233 02 при Государственном образовательном учреждении высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" по адресу 190000, г Санкт-Петербург, ул Большая Морская, д.67

С диссертацией можно ознакомиться в библиотеке ГУАП.

Автореферат разослал Ученый секретарь диссертации

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность работы Сенсорные сети представляют собой новый тип беспроводных сетей Сенсорная сеть состоит из множества сенсоров, случайным образом распределенных по исследуемой поверхности, и базовой станции Сенсор — это автономное беспроводное устройство с ограниченными ресурсами Задачей сенсора является сбор информации и ее передача базовой станции Каждый сенсор — это устройство, состоящее из пяти базовых компонент датчик, процессор, память, беспроводной передатчик и источник питания Ресурс источника питания обычно ограничен, что фактически определяет время жизни сенсора, тесно связано с его вычислительными возможностями и влияет на мощность передатчика В настоящее время сфера применения сенсорных сетей довольно обширна мониторинг окружающей среды и среды естественного обитания, раннее диагностирование поломок устройств в промышленности, управление дорожным движением, контроль за безопасностью объектов Целью протокола передачи пакетов является надежная доставка сообщений по маршрутам, построенным протоколом маршрутизации как между сенсорами и базовой станцией, так и между отдельными сенсорами В данной диссертационной работе рассматриваются протоколы передачи, качество которых оценивается с учетом следующих критериев надежность (всроягпость доставки), оперативность (время доставки), экономичность (энергозатраты) Основным источником ненадежности являются компрометированные узлы, удаляющие пересылаемые через них пакеты

Известные протоколы передачи пакетов для сенсорных сетей не учитывают критерии надежности, оперативности и экономичности, что обуславливает дальнейший интерес к разработке протоколов надежной передачи пакетов а также к разработке алгоритмов, которые управляют такой передачей

Целью работы является разработка и исследование алгоритмов, которые управляют передачей пакетов в сенсорной сети

Для достижения поставленной цели в работе решались следующие основные задачи

• исследование существующих алгоритмов надежной передачи пакетов в сенсорных сетях,

• разработка нового алгоритма надежной передачи пакетов, учитывающего требования по надежности, оперативности и экономичности,

• разработка алгоритмов для нахождения оптимальных параметров нового алгоритма надежной передачи пакетов,

• разработка алгоритма контроля живучести сети при использовани нового алгоритма надежной передачи пакетов

Методы исследования, для решения поставленных задач в работе используются методы теории кодирования дискретной оптимизации, системного анализа и теории сложности алгоритмов

Научной новизной обладают следующие результаты рабспы

• алгоритм адаптивной избыточной передачи (АИП) пакетов, учитывающий требования надежности, экономичности и оперативности,

• алгоритм нахождения оптимальных параметров для алгоритма АИП при передаче однопакетных сообщений, учитывающий ограничение на максимальную сложность,

• алгоритм нахождения оптимальных параметров для алгоритма АИП при передаче многопакетных сообщений учитывающий ограничение на максимальную сложность,

• алгоритм контроля живучести сети при использовании алгоритма АИП

Практическая ценность данной работы определяется тем, что предложенный алгортитм адаптивной избыточной передачи пакетов способствует как повышению надежности передачи, так и понижению энергозатрат сети Результаты работы использовались в учебном процессе Санкт-Петербургского государственного университета аэрокосмического приборостроения

Апробация результатов работы. Основные положения и результаты диссертации докладывались и обсуждались на международном симпозиуме по проблемам избыточности в информационных и управляющих системах (2007), на IX, X научных сессиях аспирантов ГУАП (г Санкт-Петербург 2006, 2007) а также на семинаре кафедры "Безопасности информационных систем" ГУАП Зарегистрирована программная разработка в отраслевом фонде алгоритмов и про! рамм регистрационный номер Гос ФАП 50200601922, 2006 г

Публикации. По теме диссертации опубликовано 5 печатных работ, в том числе 2 статьи в рецензируемых журналах по перечню ВАК

Основные положения, выносимые на защиту

1 Алгоритм адаптивной избыточной передачи пакетов для сенсорной сети

2 Алгоритм нахождения оптимальных параметров алгоритма АИП при передаче однопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у других алгоритмов

3 Алгоритм нахождения оптимальных параметров алгоритма АИП при передаче многопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у других алгоритмов

4 Алгоритм контроля живучести сенсорной сети, увеличивающий срок жизни сети по сравнению с аналогами

Структура работы Диссертационная работа состоит из введения, 4 разделов, заключения и списка использованных источников. Работа содержит 104 страницы, в том числе 99 страниц машинописного текста, включая 1 таблицу и 20 рисунков, а также 10 рисунков на 5 страницах В списке используемой литературы 65 наименований

Во введении обоснована актуальность темы диссертации, сформулированы цели диссертационной работы и основные задачи, основные по-

ложения, выносимые на защиту, кратко изложено содержание работы по разделен»!

Первый раздел посвящен алгоритмам надежной передачи пакетов в сенсорных сетях и постановке задаче управления передачей В подразделе 1 1 приводится общая информация о сенсорной сети В подразделе 1 2 дан обзор источников ненадежности при передаче пакетов и известных алгоритмов надежной передачи пакетов Подраздел 1 3 описывает модель рассматриваемой сенсорной сети В подразделе 1 4 изложен разработанный алгоритм адаптивной избыточной передачи, для нахождения оптимальных параметров которого в подразделе 1 5 сформулирована оптимизационная задача Раздел завершается выводами

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

Целью протокола передачи пакетов является надежная доставка сообщений по маршрутам, построенным протоколом маршрутизации как между сенсорами и базовой станцией, так и между отдельными сенсорами В данной работе рассматриваются протоколы передачи пакетов, качество которых оценивается с учетом следующих критериев надежность (вероятность доставки), оперативность (время доставки), экономичность (энергозатраты)

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

Оперативность передачи важна с точки зрения приложений сенсорной сети, например, для передачи сообщений о тревоге

Не менее важной характеристикой являются энергозатраты Как уже упоминалось выше, сенсор оснащен лимитированным источником питания Поэтому время жизни сенсора напрямую связано со скоростью расходования его источника питания Передача и прием пакетов являются наиболее энергоемкими операциями, выполняемыми сенсором Особенно важным

этот критерий делает то, что сенсор не только посылает в сеть свои пакеты, но и пересылает пакеты от других узлов С энергозатратами также связана еще одна важная характеристика, называемая живучестью Цель поддержания живучести сети заключается в том, чтобы в сети поддерживался запас источников питания узлов для передачи срочных однопакетных сообщений (сигналов тревоги) с максимальной скоростью и надежностью со всех возможных направлений

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

При случайной передаче отправитель для каждого пакета выбирает один из маршрутов случайным образом С одной стороны, алгоритмы случайной передачи не требуют много энергии, тк на каждом шаге маршрута используется только один узел С другой стороны, такой алгоритм не позволяет говорить о передаче с заданным уровнем надежности, те о доставке с заданным порогом на величину возможной ошибки

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

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

1 Используется централизованное управление сетью, которое осуществляет базовая станция

2 Для передачи управляющей информации от базовой станции не используются промежуточные узлы

3 В сети предполагается передача нескольких типов сообщений: штатных однопакетных, срочных однопакетыых, многопакетных Сообщения могут иметь, например, следующее назиаг чение штатные однопакетные — подтверждения работоспособности сенсора, срочные однопакетные — сигналы тревоги, многопакетные — затрубленный вариант изображения

4 Существует множество маршрутов ог каждого сенсора до базовой станции

5 В сети происходят потери пакетов, которые могут быть вызваны как естественными причинами, так и действиями атакующих

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

Если компрометированные узлы находятся на разных маршрутах и координируют свои действия путем удаления пакетов из одной посылки, то их нельзя выявить с помощью краткосрочного рейтинга, поскольку в этом случае резкого увеличения числа потерянных пакетов на одном маршруте не происходит Однако, ненадежность данных маршрутов будет выявлена с помощью долгосрочного рейтинга

Кроме перечисленных ограничений учитываются также следующие допущения Время функционирования сети поделено на этапы В начале каждого этапа сенсоры присылают базовой станции следующую информацию

список своих соседей, среднее количество переспросов при пересылке пакетов для каждого соседа, собственный уровень энергозапаса источника питания По собранным данным базовая станция разбивает сеть на кластеры, выбирает внутри кластера главу кластера (он же является агрегатором), строит маршруты до глав кластеров и выбирает для них параметры алгоритма надежной передачи Затем всем узлам рассылается информация о делении на кластеры и маршрутизационные таблицы, а агрегаторам — еще и информация о параметрах алгоритма надежной передачи пакетов В течение этапа базовая станция обменивается сообщениями с сенсорами, ведет рейтинги маршрутов а также следит за живучестью сети. При превышении рейтингами порогов или для поддержания живучести сети отдельные маршруты могут быть отключены Отключение маршрутов или значительное изменение их рейтингов вызывает необходимость пересчитать параметры алгоритма надежной передачи пакетов или даже выполнить частичную ремаршрутизацию Результаты пересчета параметров передачи должны быть отправлены сенсорам

Для известных алгоритмов передачи пакетов невозможно добиться выполнения требований на заданную вероятность ошибки передачи Это вызвано тем, что в этих алгоритмах по каждому маршруту передается одна копия пакета

Предлагается для выполнения ограничений на ошибку передачи передавать несколько копий пакета по каждому маршруту, т е по г-му маршруту передастся пг копий пакета Передача нескольких копий но одному маршруту имеет смысл, поскольку в описанной нами модели сети потери пакетов на маршруте являются независимыми событиями Количество пакетов, которое должно быть передано по каждому маршруту, предполагается рассчитывать путем решения оптимизационной задачи При формулировке оптимизационной задачи используется информация о характеристиках маршрутов, поэтому данный алгоритм можно назвать Адаптивной Избыточной Передачей (АИП)

Используются два алгоритма передачи с избыточностью дублирование и транспортное кодирование Дублирование используется для однопакет-ных сообщений (штатных и срочных) Транспортное кодирование используется для больших сообщений, состоящих из нескольких пакетов Определить число пакетов, которое необходимо послать по каждому из маршрутов, можно на основе решения оптимизационной задачи В этой задаче должны быть учтены ограничения на вероятность ошибки, энергозатраты на передачу и требования по оперативности

В работе описана информация, которой обладает базовая станция На основе этой информации формулируются энергетические и временные ограничения В начале каждого этапа базовая станция получает от сенсоров информацию о графе сети и следующую информацию о каждом узле г — энергетические затрагы при посылке сенсором г пакета соседу з (вычисляется на основе среднего количества переспросов), — временные затраты при посылке сенсором г пакета соседу э (вычисляется на основе среднего количества переспросов), дг — энергозапас сенсора г

По этим данным базовая станция вычисляет и присваивает каждому маршруту г следующие величины

• Ег — энергозатраты при передаче пакета по маршруту, как функцию от энергозатрат ёь,г для всех узлов маршрута

• Тг — время при передаче пакета по маршруту как функцию от временных затрат г для всех узлов маршрута

• Рг — вероятность потери пакета на маршруте Для новых маршрутов, по которым передача еще не велась, начальное значение этой вероятности принимается равным 0 При передаче по данному маршруту вероятность потери пакета оценивается на основе полученной статистики, т е на основе рейтинга маршрута

Как уже было сказано, для выполнения требования по надежности передачи в работе предлагается передавать по г-му маршруту пг пакетов По одному маршруту пакеты отправляются через интервал г

Он гимизациоппая задача при передаче с избыточное! ыо формулируется следующим образом Имеется N независимых маршрутов, и каждый маршрут описывается вектором (рг, Ег, Тг) Требуется передаль сообщение, состоящее из к пакетов При этом ошибка передачи Ре(к, IV) не должна превосходить р Для этого необходимо найти количество пакетов, которое должно быть передано по каждому маршруту, те найти целочисленное множество (щ, ,пн) (щ е АО, для которого должны выполняться следующие требования

1 Условие на величину ошибки передачи

Ре{к, Ы) = Р(пипъ, ,пп)<р,

где функция Р определяется в зависимости от выбранного ал! оритма передачи (дублирование или транспортное кодирование)

2 Условие на энергозатраты при передаче

N

Е(пх,п2, = т1г —► шш

г=1

3 Условие на оперативность передачи

Т(пх,п2, ,пц) = тах{Гг + г пг} —» тт

г=1 N

Расчет параметров передачи производится в начале каждого этапа жизни сети для всех агрегаторов что увеличивает общую вычислительную сложность расчетов Кроме того, существует ограничение на общее время расчета Ведь чем быстрее сеть адаптируется, тем дольше будет время ее жизни

и тем меньший урон нанесут атакующие Исходя из этих требований для алгоритмов расчета формулируется ограничение на максимальную сложность расчетов

Второй раздел посвящен использованию алгоритма дублирования д ля передачи однопакетных сообщений Рассмотрено два вида сообщений срочные и штатные В подразделе 2 1 приведены оптимизационные соотношения для задачи управления дублированием В подразделах 2 2 и 2 3 приведены алгоритмы решения оптизационной задачи методом динамического программирования и методом ветвей и границ соответственно В подразделе 2 4 описан гибридный алгоритм, объединяющий преимущества обоих методов и имеющий ограничение на максимальную сложность В подразделе 2 5 приведены результаты моделирования рассмотренных алгоритмов Раздел завершается выводами

Оптимизационная задача для метода дублирования сформулирована ниже

Для срочных сообщений максимальный приоритет имеет критерий Г, а для штатных сообщений — критерий Е Дано р и множества {Гг}г=х ц, {Ег}г=1 м и {рг}г=1 к, требуется найти множество {п,}г=;1 л/, где пг Е М, т е решить задачу целочисленного программирования Величина г является задаваемой константой

Выражение для Ре( 1, ЛГ) можно преобразовать к линейному виду, прологарифмировав обе части

Для оптимизации функции такого вида можно использовать метод динамического программирования и метод ветвей и границ

Для решения поставленной оптимизационной задачи был применен алгоритм динамического программирования (ДП) с ограниченной точностью Это означает, что полученный результат является оценкой оптимального решения (которое может быть получено полным перебором) с некоторой 1Г01 ретпшхл ыо За счет уменьшения точности может бьпь уменьшена вычислительная сложность алгоритма При последовательном переборе (от меньших индексов к большим) но множеству значений вектора (щ, гедг) сумма

может принимать произвольные возрастающие значения от 0 до 1 С целью уменьшения вычислительной сложности алгоритма можно уменьшить количество значений, которые может принимать эта сумма, квантуя ее с

Т = тах(7'1 + гпь . ,Тм + гпх) —> тт

(1)

(2)

(3)

некоторым шагом t (например, с шагом ¿ = 01) Уменьшение шага квантования уменьшает погрешность результата, но в то же время ведет к увеличению сложности алгоритма Меняя значение шага квантования, можно достичь необходимого компромисса между сложностью и погрешностью результата Перебор ведется построением путей в прямоугольной (1/t) N решетке

В алгоритме ветвей и границ (ВГ) перебор упорядочивается в виде дерева При этом вершины первого уровня соответствуют перебору по первой компоненте вектора ni, вершины второго уровня — по второй компоненте и-2, и так далее до гед- Для того, чтобы сократить перебор, строятся две оценки нижняя оценка текущего решения и верхняя оценка лучшего найденного решения, по которым происходит отсечение бесперспективных ветвей

Верхняя оценка вычисляется как текущее значение целевой функции при достижении частичной суммой Sb значения единицы, те Sb > 1 Из двух имеющихся оценок в качестве новой лучшей верхней оценки выбирается минимальная по основной целевой функции, а при их равенстве — по дополнительной целевой функции Начальная верхняя оценка и начальное решение строятся с помощью "жадного" алгоритма В "жадном" алгоритме предполагается что для выполнения требований по надежности передача ведется только по одному маршруту с лучшими характеристиками, т е передача по нему обеспечит минимальные энергозатраты по сравнению с дру1 ими маршрутами

При построении нижней оценки используется логика, аналогичная примененной в "жадном" алгоритме Выбирается хороший маршрут, и все пакеты, необходимые для выполнения ограничения по вероятности ошибки, отправляются по нему Только в отличие от "жадного" алгоритма, для построения оценки строится гипотетический маршрут, обладающий идеализированными характеристиками Пусть на уровне i < N имеется проме-жуточый АГ-вектор (nltJl, ,nh3l,0, ,0) Из неиспользованных маршрутов с номерами от г + 1 до N строится гипотетический маршрут best с идеализированными характеристиками, тес наилучшими из имеющихся Pbest - тш(рг+ь , pN), Ebest - mm(F,+i,. , EN) и т д.

Метод динамического программирования выигрывает у метода ветвей и границ по максимальной сложности в то же время метод ветвей и границ имеют лучшую среднюю сложность, а максимальная сложность этого алгоритма равна сложности полного перебора Согласно требованиям к алгоритму расчета, необходим гибридный алгоритм (ГБ) расчета, который объединяет достоинства описанных алгоритмов и при этом имеет ограничение на максимальную сложность

Гибридный алгоритм работает следующим образом Задается максимально допустимое время расчета По этому времени вычисляется максимально допустимая сложность гибридного алгоритма По этой сложности и оценке сложности алгоритма динамического программирования вычисляется порог Выполняется поиск решения алгоритмом ветвей и границ, при этом подсчитываете« количество просмотренных вершин в дереве перебо-

ра. Если число ййЙЙйотрснных вершин превышает порог, а решение еще не найдено, то выполнение алгоритма пе-гвей и границ прерывается и Запускается алгоритм динамического программирования. Гибридный алгоритм как и алгоритм динамического программирования не всегда находит оптимальное решение. Точность и сложность гибридного алгоритма оценены с помощью моделирования.

Ниже при веде игл результаты моделирования гибридного алгоритма расчета для штатных сообщений. Дм срочаьхх сообщений получены похожие результаты.

(а) Сложность длгорнтьюц

Hcnitc ''.V*. ; ■ t м. л : -ritt : с. -I

(b) То'нч^-ть алгоритм an

Рис. 1. Штатные сообщения. Алгоритмы ВГ, ДП и Гй.

Иа графике рисунка 1(a) показаны максимальная сложность алгоритма нетней и границ (шахВВ), максимальная (шахНВ) и средняя (avg'Hß) сложности гибридного алгоритма а также средняя сложность алгоритма динамического программирования. По оси абсцисс отложило число маршрутов (Route Number^ ano оси ординат - сложность, измеренная в количестве просмотренных вершин. Щ грификя ввдно, что гипрпднып алгоритм выигрывает по средней сложности у метода динамического программировался, при этом его максимальная сложность значительно ниже, чем максимальная сложность метода ветней и границ. Можно сделать ныв од, что гибрндный алгОрс№Н выполняет предъявленные к нему требования но сложности.

На рис. 1(b) отлажены отношения целевых функций алгоритмов ДП (DP_E и DP__T) и ГБ (НВ_Е и НВ_Т) к аналогичным оптимальным значениям, выдаваемым алгоритмом ВГ. В алгоритме динамического программирования шаг квантования выбирался равным 0.1. При зтом из графика видно, что максимальная погрешность составляет 3%.

Третей раздел носнящсн применению алгоритма транспортного кодирования для передачи миогонакетлмх сообщений. В подразделе 3.1 описаны детали применения кодов Рида-Соломона для транспортного кодирования. В подразделе а.2 приведены оптимизационные соотношения для нахождения оптимальных параметров алгоритма надежной передачи лаке-

тов для многопакетных сообщений В подразделах 3 3 и 3 4 соответственно приведены алгоритмы решения оптимизационных задач методом локального поиска и методом ветвей и границ Оба алгоритма объединены в гибридный алгоритм в подразделе 3 5 Результаты моделирования алгоритмов приведены в подразделе 3 6 Раздел завершается выводами

Оптимизационная задача для транспортного кодирования формулируется следующим образом

'Pd(k,N)= Y, C(ni,k!,pi) C(nN,kN,pN) fcl+ +kN>k

, l>ki<nu ,l>kN<nN f4\

_ „2V „ V'

E = 2^t=l пгЕг —> min

. T = max(Tj + гщ, + rnN) —> mm,

где С(тц,Ь,,Р») = C£( 1 -p^'p^

Даны к, p и множества {Тг}г=1 jv, {Ег}г=1 jv, требуется найти множество {пг}г=1 я, где пг € Л/", те решить задачу целочисленного программирования Величина г является задаваемой константой

Вид функции ограничений не позволяет использовать метод динамического программирования Поэтому приведено решение только алгоритмом ветвей и границ Общая схема метода ветвей и границ описана в разделе 2 Основное огличис состоит в методе подсчета гокущего значения функции ограничения Pd(k, N) Подсчет функции ограничения, выполняемый в каждой вершине дерева перебора, является вычислительно сложной процедурой, сложность которой оценивается как С^Т;1 . Для ускоре-

ni~rtiv — L)

ния этих вычислений предлагается использовать следующую рекурсивную формулу

N

Е П С(пг,кг,рг) =

fci+ +kN>ki=l ic-\

лдг N~ 1 W

= 2 G(nN,kN,pN) X) П С{щ,кг,Р1)

Таким образом, величина функции ограничения в вершине г-го уровня дерева вычисляется через значения, сохраненные в вершине-предке на предыдущем уровне (г — 1) Гибридный алгоритм для определения параметров транспортного кодирования выглядит следующим образом Устанавливается порог на максимальное число вершин, которые могут быть просмотрены в дереве перебора При превышении порога текущая верхняя граница рассматривается как найденное решение Затем производится попытка улучшить полученный результат с помощью алгоритма локального поиска с низкой сложностью С помощью этого алгоритма число операций, которое необходимо произвести в вершине г уровня для вычисления функции ограничений, сведено к пг Также потребуется пг ячеек памяти

Основным недостатком алгоритма ветвей и границ является то, что его максимальная сложность равна сложности полного перебора Это несовместимо с требованиями, предъявленными к алгоритму расчета Гибридный

алгоритм для определения параметров транспортного кодирования выглядит следующим образом. Устанавливается порог на максимальное число вершин, которые могут быть просмотрены в дереве перебора. При превышении порога, текущая верхняя граница рассматривается как найденное решение.

S ООО

i iooû

° tihûû п

S0ÎIÛ

Ï. I

5 2000 10 if

Л'^ЧЙ ■ >: -

■■■ JK '1X .. : I

Rtu Е 'i LptOLe t ' « J 'f- *

(a) Сложность алгоритмов

Roui - . м ,.î ; ;л . . '. ьгяайдч»

{Ь) ТОЧНОСТЬ ЛЛГчриТМОВ

Рнс. 2. Мгюгшахетные гаобгценяя, Алгоритмы ВГ к ГБ.

Путем моделирования был выбран оптнмалъ ный порог для максимальной сложности в 2000 вершин. При данном пороге погрешность вычислений составляет не более 1%. На графике на рис. 2(а) показавы средняя (avgHB) и максимальная сложность (тахНВ) гибридного алгоритма, а также максимальная сложность (тахВЩ алгоритма петвсЯ и границ. График на рис. 2{Ъ) показывает-, что при выбранном ограничении гибриДйЫй алгоритм имеет дрстаточтю малую гюг'рзпшсеи».

В четвертом разделе производится оценка качества предложенного (Шгорнтмя надежной передачи пакетов для сенсорной сети и его сравнение с существующими решениями, кроме того, рассматривается алгоритм сохранения живучести сети при использовании АИП. В подразделе 4.1 irpo-«одится сравнение предложенного алгоритма надежной передачи пакетов и существующих решений. В подразделе 4.2 рассмотрен дополнительный критерий управления: поддержание живучести сети. Раздел завершается выводами.

Для сравнения рассмотрены следующие известные алгоритмы: ¡алгоритм случайной передачи (СП) и алгоритм передачи с избыточностью (МП)- При случайной передаче отправитель для доставки пакета выбирает один из маршрутов случайным образом. При передаче с избыточностью по каждому и-j маршрутов посылается ровно одна копия пакета. В этих алгоритмам не используются данные о характеристиках маршруток, поэтому чти алгоритмы можно назвать неадантивпыми. Предложенный алгоритм адаптивной избыточной передачи (АИП) использует знания о характеристиках маршрутов. На основе этих данных для каждого из маршрутов Определяется количество копий, которое должно быть по нему послано.

В отличие от алгоритма АИП для алгоритмов СП и ИП невозможно добиться заданной вероятности ошибки при передаче пакетов, поскольку по маршруту посылается только одна копия пакета Поэтому для корректного сравнения считается, что в алгоритмах СП и ИП передача может осуществляться п раз, где тг определяется исходя из требуемой вероятности ошибки

Алгоритм АИП может быть использовав для передачи штатных, срочных и многопакетных сообщений, при этом для оценки качества передачи используются критерии энергопотребления и оперативности Алгоритмы СП и ИП предназначены только для передачи штатных сообщений Поэтому сравнение выполнено только для штатных однопакетных сообщений, у которых основным критерием качества является энергопотребление Таким образом, при заданной вероятности ошибки для каждого из алгоритмов оценены энергозатраты на доставку одного штатного сообщения

Проведено сравнение алгоритмов для N маршрутов Пусть имеется N маршрутов с вероятностями ошибки {рг}гб[1,Л'] и энергозатратами {£г}ге[1,д?] и задана требуемая вероятность ошибки передачи р

Ниже приведены системы ограничений для алгоритмов СП, ИП Система ограничений и энергозатраты для алгоритма СП имеют вид

/ ОгЕг^РгГ^Р ^ „ у-

(6)

Система ограничений и энергозатраты для алгоритма ИП имеют вид

Г(П РТ<Р . 1ое(р) у-р

Для алгоритма АИП система имеет вид

пг=1 р?<Р

Е = £)1=1 Егпг -> тш

Система (8) является задачей целочисленного линейного программирования Получить конечное выражение для энергозатрат Ещ не представляется возможным, поэтому сравнение энергозатрат Е[, Ец и Ещ проведено с помощью моделирования Решение оптимизационной задачи для алгоритма АИП проводилось с помощью метода ветвей и границ На рис 3(а) представлен график энергозатрат для алгоритмов СП, ИП и АИП Из графика видно, что алгоритм АИП имеет наименьшие энергозатраты На рис 3(Ь) показано отношение энергозатрат алгоритмов ИП и АИП Из графика видно, что с увеличением числа маршрутов ныигрыт алгориг-ма АИП увеличивается Качественное объяснение полученного выигрыша может быть дано следующим образом В алгоритм«« СП и ИП не используется информация о характеристиках маршрутов, т е они полагаются равноценными Поэтому выигрыш адаптивный алгоритм должен давать тем

(8)

260 газ 220 200 190 160 140 120 loa so 60 40

(а) Энергозатраты при передаче

Soute Nutnber

(Ь) Отношение энергозатрат при поредлче длм алгоритмов ИП и АИП

Рис 3 Сравнение энергозатрат для алгоритмов СП, ИП и АИП

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

Далее рассмотрен еще один аспект управления передачей, связанный с учетом критерия живучести Цель поддержания живучести сети заключается в том, чтобы в сети поддерживался запас источников питания узлов для передачи срочных однопакетных сообщений (сигналов тревоги) с максимальной скоростью и надежностью со всех возможных направлений

В зависимости от топологии сети и характера трафика, который определяется физическим положением и интенсивностью возникновения наблюдаемых сетью событий, энергоресурсы сети расходуются неравномерно Другими словами, через определенные сенсоры проходит большее число пакетов, чем через остальные узлы сети Энергоресурс таких сенсоров заканчивается быстрее и они выбывают из строя Это приводит к преждевременному истощению, и, следовательно, к недоступности для базовой станции некоторых участков сети В результате такой неравномерной деградации сеть не может выполнить свою основную задачу — сбор информации со всей наблюдаемой территории Под живучестью будем понимать способность сети равномерно деградировать по всем направлениям на базовую станцию

Согласно модели сети базовая станция может оценить текущее состояние источника питания каждого сенсора Множество сенсоров разбивается на несколько классов важности Разбиение делается на основе числа проходящих через сенсор маршрутов В один класс попадают сенсоры, через которые проходит приблизительно одинаковое число маршрутов Если состояние источника питания сенсора значительно отличается от среднего значения данной величины в его классе, то все маршруты проходящие через этот сенсор, временно выключаются

В заключении сформулированы основные результаты диссертационной работы

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Основные результаты работы можно сформулировать следующим образом

1 Разработан алгоритм адаптивной избыточной передачи {АИП) учитывающий требования надежности, экономичности и оперативности В отличие от существующих алгоритмов предложенный алгоритм учитывает характеристики используемых маршрутов Предложенный алгоритм существенно выгоднее по энергопотреблению, чем существующие аналоги

2 Разработаны следующие алгоритмы настройки параметров управления передачей пакетов

1 Алгоритм нахождения оптимальных параметров алгоритма АИП для однопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у аналогов

2 Алгоритм нахождения оптимальных параметров алгоритма АИП для многопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у аналогов

3 Алгоритм контроля живучести сети при использовании АИП, увеличивающий срок жизни сети по сравнению с аналогами

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1 Е.М Линский, Крук Е.А. К вопросу об управлении передачей пакетов в сенсорных сетях. Системы управления и информационные технологии №2.2(28), 2007.

2 Е.М Линский, Г.С. Евсеев. Сравнение протоколов адаптивной и неадаптивной передачи пакетов для сенсорной сети Информационно-управляющие системы, №5, Санкт-Петербург, 2007.

3 ЕМ Линский, Г С Евсеев Расчет параметров алгоритма гарантированной доставки для сенсорных сетей Фонд алгоритмов и программ, инвентарный номер ВНТИЦ 50200601922, 2006

4 Е М Линский, Крук Е А К вопросу об управлении передачей в сенсорных сетях X Научная сессия аспирантов СПбГУАП Тез докл -СПб 2007

5 EM Lmsky, GS Evseev Reliable packet transmission for sensor networks In Proceedings of XI international symposium on problems of redundancy m information and control systems, 2007

Формат 60x84 1\16 Бумага офсетная Печать офсетная. Тираж 100 экз Заказ № 5Щ

Редакционно-издательский центр ГУАП 190000, Санкт-Петербург, Б Морская ул., 67

Введение

1 Постановка задачи

1.1 Сенсорные сети.

1.2 Анализ источников ненадежности при передаче пакетов.

1.2.1 Искажение пакетов.

1.2.2 Вброс пакетов в сеть.

1.2.3 Удаление пакетов из сети.

1.2.4 Выводы.

1.3 Модель сенсорной сети.

1.4 Алгоритм передачи, учитывающий требования надежности, экономичности и оперативности

1.5 Оптимизационная задача управления передачей пакетов

1.6 Выводы.

2 Передача с дублированием пакетов

2.1 Оптимизационные соотношения

2.2 Решение алгоритмом динамического программирования.

2.3 Решение алгоритмом ветвей и границ.

2.4 Применение гибридного алгоритма.

2.5 Результаты моделирования.

2.5.1 Передача штатных сообщений

2.5.2 Передача срочных сообщений.

2.6 Выводы.

3 Передача с кодированием пакетов

3.1 Применение кодов Рида-Соломона.

3.2 Оптимизационные соотношения

3.3 Решение методом ветвей и границ.

3.4 Решение алгоритмом локального поиска.

3.5 Применение гибридного алгоритма.

3.6 Результаты моделирования.

3.7 Выводы.

4 Сравнение алгоритмов передачи и учет критерия живучести

4.1 Сравнение адаптивной и неадаптивной передачи.

4.1.1 Анализ для двух маршрутов.

4.1.2 Анализ для N маршрутов.

4.2 Учет критерия живучести сети.

4.2.1 Определение критерия живучести сети.

4.2.2 Алгоритм контроля живучести.

4.3 Выводы.

Актуальность темы. Сенсорные сети представляют собой новое семейство беспроводных сетей со своими задачами и особенностями. Их появление было вызвано резким снижением затрат на производство отдельных сенсоров, что сделало использование таких сетей экономически выгодным.

В общем случае сенсорная сеть состоит из множества сенсоров, случайным образом распределенных по исследуемой поверхности, и базовой станции. Сенсор — это автономное беспроводное устройство с ограниченными ресурсами. Задачей сенсора является сбор информации и ее передача базовой станции.

Каждый сенсор — это устройство, состоящее из пяти базовых компонент: датчик, процессор, память, беспроводной передатчик и источник питания. Ресурс источника питания обычно ограничен, что фактически определяет время жизни сенсора, тесно связано с его вычислительными возможностями и влияет на мощность передатчика.

В настоящее время сфера применения сенсорных сетей довольно обширна [1], [2]: мониторинг окружающей среды и среды естественного обитания, раннее диагностирование поломок устройств в промышленности, управление дорожным движением, контроль за безопасностью объектов.

Целью протокола передачи пакетов является надежная доставка сообщений по маршрутам, построенным протоколом маршрутизации, как между сенсорами и базовой станцией, так и между отдельными сенсорами. В данной диссертационной работе рассматриваются протоколы передачи пакетов, качество которых оценивается с учетом следующих критериев: надежность (вероятность доставки), оперативность (время доставки), экономичность (энергозатраты). Основным источником ненадежности являются компрометированные узлы, удаляющие пересылаемые через них пакеты.

Основной целью работы является разработка и исследование алгоритмов, которые управляют передачей пакетов в сенсорной сети.

Методы исследования. Для достижения цели в работе используются методы теории кодирования, дискретной оптимизации, системного анализа и теории сложности алгоритмов.

Научная новизна диссертационной работы заключается в следующем.

1. Разработан алгоритм адаптивной избыточной передачи (АИП) пакетов, учитывающий требования надежности, экономичности и оперативости. Алгоритм выигрывает по экономичности и оперативности у существующих алгоритмов.

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

3. Разработан алгоритм нахождения оптимальных параметров для алгоритма АИП при передаче многопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у других алгоритмов.

4. Разработан алгоритм контроля живучести сети при использовании алгоритма АИП. Этот алгоритм позволяет увеличить срок жизни сети по сравнению с аналогами.

Практическая ценность и реализация результатов. Практическая ценность работы определяется тем, что предложенный алгортитм адаптивной избыточной передачи пакетов способствует как повышению надежности передачи, так и понижению энергозатрат сети.

Публикации. Материалы, отражающие основное содержание и результаты диссертационной работы, опубликованы в 5 печатных работах ([3, 4, 5, 6, 7]). В том числе 2 работы [5, 7] опубликованы в журналах, реферируемых ВАК.

Основные положения, выносимые на защиту.

1. Алгоритм адаптивной избыточной передачи пакетов для сенсорной сети.

2. Алгоритм нахождения оптимальных параметров алгоритма АИП при передаче однопакетных сообщений, учитывющий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у других алгоритмов.

3. Алгоритм нахождения оптимальных параметров алгоритма АИП при передаче многопакетных сообщений, учитывющий ограничения на максимальную вычислительную сложность и обеспечивающий выигрышщ по этому параметру у других алгоритмов.

4. Алгоритм контроля живучести сенсорной сети, увеличивающий срок жизни сети по сравнению с аналогами.

Объем и структура работы. Диссертационная работа состоит из введения, 4 разделов, заключения и списка использованных источников.

Основные результаты данной диссертационной работы могут быть сформулированы следующим образом.

1. Разработан алгоритм адаптивной избыточной передачи (АИП), учитывающий требования надежности, экономичности и оперативности. В отличие от существующих алгоритмов предложенный алгоритм учитывает характеристики используемых маршрутов. Предложенный алгоритм существенно выгоднее по энергопотреблению, чем существующие аналоги.

2. Разработаны следующие алгоритмы настройки параметров управления передачей пакетов. a) Алгоритм нахождения оптимальных параметров АИП для однопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у аналогов. b) Алгоритм нахождения оптимальных параметров АИП для многопакетных сообщений, учитывающий ограничения на максимальную вычислительную сложность и обеспечивающий выигрыш по этому параметру у аналогов. с) Алгоритм контроля живучести сети при использовании АИП, увеличивающий срок жизни сети по сравнению с аналогами.

Заключение

В данной работе рассматривалась задача управления надежной передачей пакетов в сенсорной сети в присутствии компрометированных узлов, выбрасывающих передаваемые через них пакеты. Была рассмотрена передача трех типов сообщений: штатных однопакетных, срочных однопакетных и многопакетных.

1. Chee-Yee Ghong and Srikanta P.Kumar. Sensor networks: Evolution, opportunities, and challenges. March 2003.

2. Алекс Карабуто. "Сенсорные сети: как скоро?". 25 августа 2004 года.

3. Е.М. Линский, Г.С. Евсеев. "Расчет параметров алгоритма гарантированной доставки для сенсорных сетей". Фонд алгоритмов и программ, инвентарный номер ВНТИЦ 50200601922, 2006.

4. Е. М. Линский. "К вопросу об управлении передачей в сенсорных сетях". Сборник докладов научной сессии аспирантов ГУАП 2007, Санкт-Петербург, 2007.

5. Е. М. Линский. "К вопросу об управлении передачей пакетов в сенсорных сетях". Системы управления и информационные технологи, №2.2(28), 2007.

6. Е. Linsky and G. S. Evseev. Reliable packet transmission for sensor networks. In Proceedings of XI international symposium on problems of redundancy in information and control systems, 2007.

7. Е.М. Линский, Г.С. Евсеев. "Сравнение протоколов адаптивной и неадаптивной передачи пакетов для сенсорной сети". Информационно-управляющие системы, №5 , Санкт-Петербург, 2007.

8. J. M. Kahn, R. H. Katz, and K. S. J. Pister. Mobile networking for smart dust. In MobiCom, 1999.

9. Ian F. Akyildiz, Weilian Su, Yogesh Sankarasubramaniam, and Erdal Cayirci. A survey on sensor networks. August 2002.

10. Shamila Makki, Niki Pissinou, and Tirthankar Bhowmick. Leach protocol for assigning cluster-heads using a deterministic and stochastic approach for wireless sensor networks. In International Conference on Wireless Networks, pages 963-968, 2004.

11. Matthias Lott, Alexey Sitalov, Evgeny Linsky, , and Hui L. Performance analysis of multicast transmission in wlan. In In Vehicular Technology Conference. VTC 2003-Spring. The 57th IEEE Semiannual, pages 12231227, April 2003.

12. Lingxuan Hu and David Evans. Secure aggregation for wireless networks. In SAINT-W '03: Proceedings of the 2003 Symposium on Applications and the Internet Workshops (SAINT'03 Workshops), page 384, Washington, DC, USA, 2003.

13. Bartosz Przydatek, Dawn Xiaodong Song, and Adrian Perrig. Sia: secure information aggregation in sensor networks. In SenSys, pages 255-265, 2003.

14. А.Д. Фомин. "Распределенная верификация результата агрегации данных в сенсорных сетях". Программные продукты и системы, №2, 2007.

15. Panagiotis Papadimitratos, Zygmunt J. Haas, and Emin Sirer. Path set selection in mobile ad hoc networks. In MobiHoc '02: Proceedings of the 3rd A CM international symposium on Mobile ad hoc networking & computing, pages 1-11, New York, NY, USA, 2002.

16. E. M. Линский. "Сравнение производительности протоколов маршрутизации в ad hoc сетях". Труды конференции БИКАМП'ОЗ, Санкт-Петербург, Россия, 2003.

17. С. Karlof and D. Wagner. Secure routing in wireless sensor networks: Attacks and countermeasures. August 2002.

18. Adrian Perrig, Robert Szewczyk, J. D. Tygar, Victor Wen, and David E. Culler. Spins: security protocols for sensor networks. Wirel. Netw., 8(5):521-534, 2002.

19. S. Bezzateev, E.Jung, E. Krouk, К. H. Lee, and E. Linsky. Subcodes of goppa codes for multi-level access control systems. In Proceedings of NEW2AN'04, St. Petersburg, Russia, 2004.

20. E. M. Линский. "Использование одного класса кодов Гоппы для организации системы многоуровневого доступа к информации". In Сборник докладов научной сессии аспирантов ГУАП 2004, Санкт-Петербург, 2004.

21. E. Linsky and E. Krouk. LDPC Code Based Cryptosystem for Encryption on PHY. In Proceedings of ISBC'06, Moscow, Russia, 2006.

22. E. M. Линский. "Криптосистема на ldpc-кодах для защиты информации на физическом уровне". Вопросы передачи и защиты информации, 2006.

23. Alfred Menezes, Paul С. van Oorschot, and Scott A. Vanstone. Handbook of Applied Cryptography. CRC Press, 1996.

24. Sencun Zhu, Sanjeev Setia, and Sushil Jajodia. Leap: efficient security mechanisms for large-scale distributed sensor networks. In ACM Conference on Computer and Communications Security, pages 62-72, 2003.

25. Фомин А.Д. DPS: Эффективная схема управления ключами в больших сенсорных сетях. Вопросы передачи и защиты информации: Сборник статей / СПбГУАП. СПб., 2006.

26. S. Buchegger and J. Le Boudec. Nodes bearing grudges: Towards routing security, fairness, and robustness in mobile ad hoc networks, in pdp'02, 2002.

27. B. Parno, M. Luk, E. Gaustad, and A. Perrig. Secure sensor network routing: A clean-state approach. 2006.

28. C.E. Perkins. Ad Hoc Networking. Addison-Wesley, 2001.

29. J. Deng, R. Han, and S. Mishra. Intrusion-tolerant routing for wireless sensor networks. Elsevier Journal on Computer Communications. Special Issue on Dependable Wireless Sensor Networks, 2005.

30. Sergio Marti, T. J. Giuli, Kevin Lai, and Mary Baker. Mitigating routing misbehavior in mobile ad hoc networks. In Mobile Computing and Networking, pages 255-265, 2000.

31. A. D. Wood, L. Fang, J. A. Stankovic, and T. He. Sigf: A family of configurable, secure routing protocols for wireless sensor networks. In A CM SASN, October 2006.

32. Ieee std. 802.11, part 11: Wireless lan medium access control (mac) and physical layer (phy) specifications, 1997.

33. N.F. Maxemchuk. Dispersity Routing in Store and Forward Networks. PhD thesis, University of Pennsylvania, May 1975.

34. G.A. Kabatyanskii and E.A. Krouk. Coding decreases delay of messages in networks. In Proceedings of IEEE International Symposium on Information Theory.

35. Ф.Дж. Мак-Вильямс and Н.Дж.А. Слоэн. Теория кодов, исправляющих ошибки. М.: Связь, 1979.

36. A. Barg, Е. Krouk, and Н. van Tilborg. On the complexity of minimum distance decoding of long linear codes. IEEE Transactions on Information Theory, pages 1392 1405, 1999.

37. W. W. Peterson and E. J. Weldon. Error-correcting Codes. MIT Press, 1972.

38. Christian Huitema. The case for packet level fee. In Walid Dabbous and Christophe Diot, editors, Protocols for High-Speed Networks, volume 73 of IFIP Conference Proceedings, pages 109-120. Chapman & Hall, 1996.

39. E. Schooler and J. Gemmell. Using multicast fee to solve the midnight madness problem, 1997.

40. John Byers, Michael Luby, Michael Mitzenmacher, and Ashu Rege. A digital fountain approach to reliable distribution of bulk data. In Proceedings of ACM SIGCOMM '98, September 2-4, 1998, 1998.

41. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, Daniel A. Spielman, and Volker Stemann. Practical loss-resilient codes. In STOC, pages 150-159, 1997.

42. Michael Luby, Michael Mitzenmacher, Mohammad Amin Shokrollahi, and Daniel A. Spielman. Analysis of low density codes and improved designs using irregular graphs. In STOC, pages 249-258, 1998.

43. M.O. Rabin. Efficient dispersal of information for security, load balancing, and fault tolerance. Journal of the ACM, 36(2):335-348, April 1989.

44. P. Papadimitratos and Z.J. Haas. Secure message transmission in mobile ad hoc networks. In Proceedings of the ACM Workshop on Wireless Security (WiSe'03), San Diego, С A, USA, pages 41-50, September 2003.

45. S.D. Muruganathan, D.C.F. Ma, R.I. Bhasin, and A.O. Fapojuwo. A centralized energy-efficient routing protocol for wireless sensor networks. EEE Communications Magazine, 43(3):S8—13, 2005.

46. Wendi Rabiner Heinzelman, Anantha Chandrakasan, and Hari Balakrishnan. Energy-efficient communication protocol for wireless microsensor networks. In HICSS, 2000.

47. Stephanie Lindsey and Cauligi S. Raghavendra. Pegasis: Power-efficient gathering in sensor information systems, 2002.

48. P. Garda, 0. Romain, B. Granado, A. Pinna, D. Faura, and K. Hachicha. Architecture of an intelligent beacon for wireless sensor networks. In IEEE 13th Workshop Neural Networks for Signal Processing, pages 151-158, 2003.

49. Ming-Zeng Hu Zhi-Yan Cao, Zheng-Zhou Ji. An image sensor node for wireless sensor networks. In International Conference on Information Technology: Coding and Computing, volume 2, pages 740-745, 2005.

50. D. Ganesan, R. Govindan, S. Shenker, and D. Estrin. Highly-resilient, energy-efficient multipath routing in wireless sensor networks, 2001.

51. S. De, C. Qiao, and H. und. Meshed multipath routing with selective forwarding: An efficient strategy in wireless sensor networks, 2003.

52. Budhaditya Deb, Sudeept Bhatnagar, and Badri Nath. Reinform: Reliable information forwarding using multiple paths in sensor networks, in 28th annual ieee conference on local computer networks (lcn 2003), october 2003.

53. Jian Yin and Sanjay Kumar Madria. A hierarchical secure routing protocol against black hole attacks in sensor networks. In SUTC '06: Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and

54. Trustworthy Computing -Vol 1 (SUTC'06), pages 376-383, Washington, DC, USA, 2006.

55. Afrand Agah, Mehran Asadi, and Sajal K. Das. Prevention of dos attack in sensor networks using repeated game theory. In Hamid R. Arabnia, editor, ICWN, pages 29-36. CSREA Press, 2006.

56. E.C. Вентцель. Теория вероятностей. M.: Наука, 3 edition, 1962.

57. D. Whiting, R. Housley, and N. Ferguson. Counter with cbc-mac (ccm), 2002.

58. Э. Рейнгольд and Ю. Нивергельт and H. Део. Комбинаторные алгоритмы: теория и практика. М.: Мир, 1980.

59. Т. Corman, С. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 1990.

60. M. M. Ковалев. Дискретная оптимизация (целочисленное программирование). М.: Едиториал УРСС, 2003.

61. А. В. Ахо and Д. Э. Хопкрофт and Д. Д. Ульман. Структуры данных и алгоритмы. М: Издательский дом Вильяме, 2003.

62. И. В. Романовский. Субоптимальные решения. Петрозаводск: ПетрГУ, 1998.