Journal influence
Bookmark
Next issue
Abstract:
Аннотация:
Authors: () - , () - | |
Ключевое слово: |
|
Page views: 11593 |
Print version Full issue in PDF (1.17Mb) |
Распределенная верификация результата агрегации данных в сенсорных сетях
The article was published in issue no. № 2, 2007.
В современном мире беспроводные сенсорные сети помогают решать всевозможные задачи, связанные с мониторингом различных процессов и территорий. Сенсорные сети состоят из множества сенсоров, распределенных по исследуемой поверхности, и базовой станции, с помощью которой осуществляется контроль и управление сетью. Сенсоры являются автономными устройствами, обладают низкопроизводительным процессором, небольшим объемом памяти и маломощным передатчиком. Задачей каждого сенсора является сбор определенной информации и последующая ее передача на базовую станцию. Использование агрегации в сенсорной сети позволяет значительно повысить экономичность и живучесть сети. В том случае, когда базовой станции требуется определить интегральную характеристику для какого-либо участка сети, один из узлов этого участка назначается агрегатором. Он собирает с остальных узлов этого участка частные значения определяемой характеристики, вычисляет агрегатную функцию от них (среднее, минимум, максимум и т.д.) и передает это значение базовой станции. При этом общие затраты на передачу информации существенно ниже, чем при отсутствии агрегатора. Если количество сенсоров в сети достаточно велико, сеть обычно разбивается на кластеры и агрегация выполняется в каждом кластере независимо. Так как сенсорные сети часто разворачиваются на открытой и легкодоступной территории, необходимо использовать специальные процедуры для защиты передаваемой информации от возможных случайных или преднамеренных искажений. Обеспечение надежности агрегированного результата наиболее важно, так как его искажение может привести к более сильному искажению информации о контролируемых параметрах, чем искажение данных отдельных сенсоров. Известны два способа обеспечения надежной агрегации. Первый основан на распределенности процесса агрегации путем вовлечения в него дополнительных сенсоров. Второй способ основан на усложнении протокола взаимодействия между базовой станцией и агрегатором. В рамках этого протокола агрегатор должен доказать базовой станции корректность представленного результата. Так, в рамках первого подхода известна схема, основанная на использовании древовидной маршрутизации. Корнем дерева является базовая станция. Направление агрегации – от листьев к корню. При этом в каждом узле вычисляется агрегатная функция от значений, полученных от потомков, и вычисленное значение вместе со значениями аргументов передается узлу-родителю. В этом случае узел-родитель может проверить правильность агрегации, выполненной дочерними узлами. Однако данная схема не обладает достаточной надежностью: в частности, результат агрегации может оказаться некорректным при неправильной работе двух соседних узлов в дереве. Более того, в данном протоколе ограничено число вычисляемых функций агрегации, например, невозможно вычислить медиану. Другое решение основано на использовании так называемых узлов-свидетелей, которые фактически дублируют действия агрегатора. Если результат агрегации, полученный свидетелями, совпадает с результатом агрегатора, то они подписывают результат. После этого агрегатор отправляет результат и подписи свидетелей на базовую станцию. Недостатком данного решения является то, что объем передаваемых сенсорами данных линейно возрастает при увеличении числа узлов-свидетелей. В рамках второго подхода известен протокол, основная идея которого заключается в следующем. Агрегатор собирает от сенсоров данные, вычисляет агрегированное значение, подписывает его и отправляет базовой станции. После этого между агрегатором и базовой станцией выполняется интерактивный протокол доказательства корректности вычислений. Недостатком данного решения является передача большого объема данных между агрегатором и базовой стан- цией. Для достижения надежной агрегации предлагается протокол, основанный на распределенной верификации результата агрегации. В протоколе участвуют следующие стороны: базовая станция (BS), агрегатор (A), сенсоры ( Протокол состоит из трех этапов: вычисление результата агрегации, проверка полученного результата t узлами-верификаторами и отправка результата агрегации вместе с подписями верификаторов базовой станции. На первом этапе все сенсоры отправляют свои данные агрегатору: где На втором этапе производится распределенная проверка результата агрегации, состоящая из двух шагов. 1. Агрегатор предоставляет верификаторам все собранные данные: где 2. Каждый верификатор После того как верификатор где На третьем этапе агрегатор собирает подписи от всех узов-верификаторов, формирует отчет, подписывает его и отправляет на базовую станцию:
Для проверки полученного отчета базовая станция вычисляет все подписи, объединяет их, используя операцию XOR, и сравнивает вычисленное значение с полученным. Если отличий нет, то результат принимается и считается правильным. Для данного протокола можно определить вероятность принятия базовой станцией искаженного результата агрегации: где n – количество сенсоров в кластере; t – количество узлов-верификаторов; k – количество запросов от каждого узла-верификатора; m – количество искаженных отчетов в пакете, предоставленном верификаторам для проверки; p – вероятность некорректной работы узла-верификатора.
В таблице показано сравнение коммуникационных издержек для предложенного и известных протоколов. Сравнение производилось для сети со ста узлами и вероятностью некорректной работы узла-верификатора 0,1. В пакете, отправляемом сенсором, данные занимают два байта, а код проверки подлинности – десять байтов. Сопоставление коммуникационных издержек показывает существенное преимущество предлагаемого протокола в сравнении с известными. |
Permanent link: http://swsys.ru/index.php?page=article&id=402&lang=&lang=en&like=1 |
Print version Full issue in PDF (1.17Mb) |
The article was published in issue no. № 2, 2007 |
The article was published in issue no. № 2, 2007.
Perhaps, you might be interested in the following articles of similar topics:Perhaps, you might be interested in the following articles of similar topics:
- Программное обеспечение интеллектуально-механических мобильных роботов
- Устойчивость больших систем
- Подсистема ПАСПОРТ ВЫЕМОЧНОГО УЧАСТКА в интеллектуальной системе компьютеризации угольных шахт
- Паспорт стандартного процесса
- Проверка достоверности представляемой статистической информации
Back to the list of articles