Программные продукты и системы

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

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

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

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

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

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

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

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

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

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

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

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

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

где .

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

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

где

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

.

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

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

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

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