コンパクトなデータ構造による大規模な集合表現の研究

点击翻译按钮获取中文摘要

昨年度は,大規模な集合をコンパクトに表現するデータ構造であるDivided Bloom FilterやRinged Filterを提案した.今年度は,この提案Filterを無線センサーネットワークへ適用した.無線センサーネットワークにおいては,バッテリ駆動であるノードを用いるため,できるだけトラフィック量を減らす必要がある.また,各ノードが保存できるデータ量も限られる.無線センサーネットワークにおけるセキュリティ分野において,提案Filterを利用することにより,少ないトラフィック量やデータ保存量で高いセキュリティを実現できることを示した.具体的には,不正ノードから発生される不正イベントの検知を行った.物理的に近い距離にあるノードが同じイベントを検知できることを利用して,あるイベントには隣接するT個以上のノードの鍵を付加する.そのT個の鍵の組み合わせが不正なものである場合,それは不正イベントであると判断することができる.できる限りノードのバッテリを維持させるため,不正イベントは転送ノードが検知する必要がある.そのため,全てのノードが,正しいT個の鍵の組み合わせを保持する必要がある.だがこの組み合わせをそのまま保持と,データ保存量が膨大になってしまう.そこで,Filter Positiveを許して,各ノードに提案Filterを保持させることにより,保存データ量を削減することができる.数学的解析やシミュレーションにより,従来より86%程度データ保存量を削減できることを示した.また,不正イベントを発生させたノード自体の検知も行った.従来では,動的な環境において検知することはできなかったが.提案手法を用いることにより,動的な環境においても不正イベントを発生させたノードを検知することができるようになった.