На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

Распределенная верификация результата агрегации данных в сенсорных сетях

Статья опубликована в выпуске журнала № 2 за 2007 год.
Аннотация:
Abstract:
Авторы: Фомин А.Д. () - , Крук Е.А. () -
Ключевое слово:
Ключевое слово:
Количество просмотров: 8231
Версия для печати
Выпуск в формате PDF (1.17Мб)

Размер шрифта:       Шрифт:

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

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

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

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

Так, в рамках первого подхода известна схема, основанная на использовании древовидной маршрутизации. Корнем дерева является базовая станция. Направление агрегации – от листьев к корню. При этом в каждом узле вычисляется агрегатная функция от значений, полученных от потомков, и вычисленное значение вместе со значениями аргументов передается узлу-родителю. В этом случае узел-родитель может проверить правильность агрегации, выполненной дочерними узлами. Однако данная схема не обладает достаточной надежностью: в частности, результат агрегации может оказаться некорректным при неправильной работе двух соседних узлов в дереве. Более того, в данном протоколе ограничено число вычисляемых функций агрегации, например, невозможно вычислить медиану.

Другое решение основано на использовании так называемых узлов-свидетелей, которые фактически дублируют действия агрегатора. Если результат агрегации, полученный свидетелями, совпадает с результатом агрегатора, то они подписывают результат. После этого агрегатор отправляет результат и подписи свидетелей на базовую станцию. Недостатком данного решения является то, что объем передаваемых сенсорами данных линейно возрастает при увеличении числа узлов-свидетелей.

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

Для достижения надежной агрегации предлагается протокол, основанный на распределенной верификации результата агрегации. В протоколе участвуют следующие стороны: базовая станция (BS), агрегатор (A), сенсоры (), и t узлов-верификаторов (). Агрегатор и верификаторы – это обычные сенсоры, выбираемые базовой станцией внутри кластера случайным образом. Периодически базовая станция переназначает агрегатора и верификаторов.

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

На первом этапе все сенсоры отправляют свои данные агрегатору:

где  – данные, измеренные сенсором ;  – общий ключ сенсора  и агрегатора A. Агрегатор собирает все данные, проверяет их подлинность, используя соответствующие MAC-ко­ды, и вычисляет результат агрегации.

На втором этапе производится распределенная проверка результата агрегации, состоящая из двух шагов.

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

где .

2.   Каждый верификатор  анализирует соответствующее значение кода проверки подлинности в полученном пакете. Если MAC правильный, верификатор случайным образом выбирает k сенсоров и запрашивает у них данные. Каждый сенсор , получив запрос от , высылает от- вет:

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

где

На третьем этапе агрегатор собирает подписи от всех узов-верификаторов, формирует отчет, подписывает его и отправляет на базовую станцию:

.

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

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

где n – количество сенсоров в кластере; t – количество узлов-верификаторов; k – количество запросов от каждого узла-верификатора; m – количество искаженных отчетов в пакете, предоставленном верификаторам для проверки; p – вероятность некорректной работы узла-верификатора.

Тип издержек

Протокол

SIA

Свидетели

Предложенный

Передача сенсора

22

42

36

Передача вне кластера

992

22

22

Объем данных, передаваемых внутри кластера

2200

4230

3916

Объем данных, получаемых внутри кластера

2200

16830

4432

Вероятность принятия искаженного результата агрегации

0,4

0,05

0,05

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


Постоянный адрес статьи:
http://swsys.ru/index.php?page=article&id=402
Версия для печати
Выпуск в формате PDF (1.17Мб)
Статья опубликована в выпуске журнала № 2 за 2007 год.

Возможно, Вас заинтересуют следующие статьи схожих тематик: