可 能 性 がある. 本 研 究 では,まず, 各 計 算 機 がネットワークのどの 程 度 の 範 囲 の 情 報 を 得 られれば, 更 新 回 数 を 最 小 化 できるかを 検 討 した.その 結 果, 分 散 環 境 で 扱 われる 問 題 の 多 くは, 各 計 算 機 がネットワーク

10-01061 センサネットワークを 対 象 とした 分 散 アルゴリズムの 自 律 適 応 性 と 安 定 性 に 関 する 研 究 研 究 代 表 者 山 内 由 紀 子 九 州 大 学 大 学 院 システム 情 報 科 学 研 究 院 助 教 1 はじめに 小 型 の 低 能 力 な 無 線 センサ 端 末 多 数 で 構 成 されるセンサネットワークは, 環 境 観 測 等 多 くの 分 野 で 利 用 が 広 がっている. 各 無 線 センサ 端 末 は 目 的 に 合 わせたセンサ( 温 度 センサ, 照 度 センサ, 加 速 度 センサ 等 )を 備 えており, 他 の 端 末 と 無 線 通 信 を 介 して 協 調 しながら 観 測 データの 収 集 を 行 う. 自 律 的 に 動 作 する 計 算 機 群 が 相 互 に 通 信 を 行 いながら 協 調 動 作 するシステムを 分 散 システムと 呼 ぶ. 分 散 システムを 効 率 よく 運 用 する ためのアルゴリズム( 分 散 アルゴリズム)は 従 来 から 多 くの 研 究 が 行 われている. 特 に, 分 散 システムを 人 間 の 介 入 なく 運 用 することを 可 能 とするような, 自 律 適 応 性, 自 己 組 織 化 能 力 といった 性 質 を 持 つ 分 散 アル ゴリズムの 研 究 が 多 く 行 われている.センサネットワークは 分 散 システムの 一 種 ととらえることができるた め, 既 存 の 分 散 アルゴリズム 設 計 手 法 を 適 用 できる 可 能 性 があるとともに,センサネットワーク 特 有 の 問 題 を 反 映 した 新 たな 分 散 アルゴリズムの 設 計 を 必 要 とする 可 能 性 がある. 本 研 究 では,センサネットワークの 持 つ 動 的 な 環 境 変 化 に 自 律 的 に 適 応 する 分 散 アルゴリズムの 設 計 を 目 指 す. センサネットワークでは,センサ 端 末 の 故 障, 電 池 切 れによる 停 止, 無 線 通 信 の 使 用 状 況 の 変 化, 観 測 デ ータの 増 減 など,システムの 状 況 が 時 々 刻 々と 変 化 する.このような 環 境 下 の 分 散 システムには, 変 化 に 追 従 して 自 身 の 振 る 舞 いを 変 化 させる 自 律 適 応 性 と, 変 化 の 下 でも 安 定 した 振 る 舞 いを 行 う 安 定 性 の 両 方 の 性 質 を 持 つことが 必 要 である.しかし,この 2 つの 性 質 を 同 時 に 備 えた 分 散 システムの 理 論 的 な 研 究 は 十 分 に 行 われているとは 言 い 難 い. 優 れた 自 律 適 応 性 を 持 つ 分 散 アルゴリズムの 一 種 として, 自 己 安 定 アルゴリズムがよく 研 究 されている [4,5].しかし, 従 来 の 自 己 安 定 アルゴリズムでは 安 定 性 が 十 分 に 考 慮 されていない. 本 研 究 では, 自 己 安 定 アルゴリズムに 安 定 性 を 付 加 することにより, 安 定 性 と 自 律 適 応 性 を 同 時 に 備 えた 分 散 システムの 設 計 手 法 を 確 立 することを 目 指 し,いくつかの 成 果 を 得 た.また,センサネットワークで 発 生 する 大 量 の 観 測 データ の 収 集, 処 理 手 法 についてもいくつかの 成 果 を 得 た. 以 下 に 本 研 究 での 成 果 をまとめる. 2 自 己 安 定 アルゴリズムの 安 定 性 2-1 研 究 背 景 どのような 初 期 状 況 から 実 行 を 開 始 しても,やがて 目 的 の 動 作 を 行 う 状 況 に 復 帰 する 分 散 システムを 自 己 安 定 であると 言 う[4,5]. 自 己 安 定 システムは 任 意 の 有 限 個 の 一 時 故 障 (メモリのソフトエラー 等 )に 対 して, 最 後 の 故 障 発 生 後 にシステムが 自 律 的 に 復 帰 することを 保 証 するため, 優 れた 自 律 適 応 性, 故 障 耐 性 をもつ. 自 己 安 定 な 分 散 システムを 実 現 する 分 散 アルゴリズムを 自 己 安 定 アルゴリズムと 呼 び,リーダー 選 挙 問 題, 全 域 木 作 成 問 題, 極 大 独 立 点 集 合 問 題,トークン 巡 回 による 相 互 排 除 といった, 計 算 機 ネットワークを 運 用 する 上 での 基 礎 的 な 機 能 を 実 現 する 自 己 安 定 アルゴリズムがよく 研 究 されている[4, 5]. 一 般 に 自 己 安 定 アルゴリズムでは, 各 計 算 機 が 絶 えず 他 の 計 算 機 と 情 報 を 交 換 しながら, 自 身 の 計 算 結 果 (を 格 納 する 変 数 の 内 容 )を 更 新 することで,システム 全 体 が 状 況 の 変 化 に 追 従 することを 実 現 している. しかし, 自 己 安 定 アルゴリズムは 明 示 的 な 計 算 終 了 判 定 を 行 わず,アルゴリズムの 実 行 途 中 に 各 計 算 機 がも つ 計 算 の 途 中 経 過 をシステム 外 部 のユーザやソフトウェアに 観 測 されることを 許 すため, 実 行 途 中 に 信 頼 性 のある 機 能 を 保 証 できない.さらに, 計 算 の 途 中 経 過 が 更 新 される 度 に, 外 部 のユーザ,ソフトウェアが 影 響 を 受 け,ネットワーク 全 体 に 大 きな 影 響 を 与 える 可 能 性 がある. では, 実 行 途 中 の 各 計 算 機 での 更 新 回 数 を 削 減 することは 可 能 であろうか.たとえば,ネットワーク 中 に 全 域 木 を 作 成 する 全 域 木 作 成 問 題 では, 各 計 算 機 が 正 しい 計 算 結 果 を 得 るためには, 本 質 的 にある 種 のネッ トワーク 全 体 の 状 況 を 知 る 必 要 がある.ネットワーク 中 で 直 接 接 続 していない 計 算 機 どうしは, 他 の 計 算 機 が 情 報 を 中 継 することにより 互 いの 状 態 を 得 るため,この 情 報 伝 搬 の 間, 各 計 算 機 で 不 要 な 更 新 が 発 生 する 439

可 能 性 がある. 本 研 究 では,まず, 各 計 算 機 がネットワークのどの 程 度 の 範 囲 の 情 報 を 得 られれば, 更 新 回 数 を 最 小 化 できるかを 検 討 した.その 結 果, 分 散 環 境 で 扱 われる 問 題 の 多 くは, 各 計 算 機 がネットワーク 全 体 の 情 報 を 必 要 とすることがわかった.この 結 果 をもとに, 本 研 究 では 更 新 回 数 を 最 小 化 する 自 己 安 定 アル ゴリズムの 実 現 可 能 性 を 議 論 する. 2-2 分 散 システムと 自 己 安 定 アルゴリズム 本 節 では, 次 節 以 降, 本 報 告 書 内 で 使 用 する 分 散 システムの 諸 定 義 を 示 す. 分 散 システムは 計 算 機 間 の 相 互 接 続 関 係 を 表 す 無 向 グラフ G=(V, E)で 表 わされる.1 つの 頂 点 が 1 台 の 計 算 機 を 表 し, 相 異 なる 計 算 機 p, q が 互 いに 直 接 通 信 可 能 であるとき, 辺 (p, q) Eであるとする.ただし, G は 一 般 のグラフであるとする.2 つの 相 異 なる 計 算 機 p, q Vに 対 し,G 上 での p-q 間 の 最 短 パスの 長 さ をこの 計 算 機 間 の 距 離 と 言 う. 各 計 算 機 は 状 態 機 械 であり, 局 所 変 数 の 集 合 と 局 所 アルゴリズムを 持 つ. 計 算 機 の 状 態 は 局 所 変 数 の 値 で 表 し, 局 所 アルゴリズムは 状 態 機 械 の 状 態 遷 移 関 数 である.すべての 計 算 機 の 局 所 アルゴリズムの 集 合 を 分 散 アルゴリズムと 呼 ぶ. 各 計 算 機 の 局 所 変 数 は, 入 力 変 数 (アルゴリズムへの 入 力 を 格 納 する 変 数 ), 出 力 変 数 (アルゴリズムの 計 算 結 果 を 格 納 する 変 数 ), 内 部 変 数 (その 他 の 変 数 )か ら 成 る. 局 所 アルゴリズムは 入 力 変 数 と 内 部 変 数 を 用 いて 計 算 を 進 め, 出 力 変 数 に 計 算 結 果 を 格 納 する.す べての 計 算 機 の 出 力 変 数 の 値 が 分 散 アルゴリズムの 出 力 である. 分 散 アルゴリズムの 計 算 の 進 行 を 把 握 するため,システムの 状 況 と 実 行 という 概 念 を 導 入 する. 分 散 シス テム 中 の 全 計 算 機 の 状 態 の 組 を 状 況 と 呼 び,システムの 状 況 の 系 列 でアルゴリズムの 実 行 を 表 現 する. 実 行 E=c 0, c 1, が 与 えられた 時, 各 状 況 遷 移 c i c i+1 (i > 0) は 以 下 のように 決 まる:スケジューラが 計 算 機 の 任 意 の 部 分 集 合 を 選 択 し, 選 択 された 計 算 機 が 各 々の 局 所 アルゴリズムを 実 行 することで 状 況 c i から 次 状 況 c i+1 へとシステムの 状 況 が 遷 移 する.スケジューラは 通 信 遅 延 や 計 算 機 の 速 度 の 速 さの 違 いといった 分 散 シ ステムの 非 同 期 性 を 反 映 するための 概 念 である. 本 研 究 では 弱 公 平 なスケジューラ( 局 所 アルゴリズムを 実 行 したい 状 態 で 待 機 し 続 けている 計 算 機 はいずれスケジューラに 選 択 される)を 想 定 する. 分 散 システムにおける 問 題 (タスク)は 目 的 とする 実 行 や 局 所 変 数 への 条 件 として 与 えられる.たとえば, 全 域 木 作 成 問 題 [6]は, 各 計 算 機 が 隣 接 する 計 算 機 のうち 1 つを 指 すポインタを 出 力 変 数 として 持 ち,すべて の 計 算 機 の 出 力 変 数 が G 上 に 根 付 き 内 向 木 を 構 成 することと 定 義 される. 自 己 安 定 アルゴリズムは 目 的 とする 問 題 に 対 し,どのような 初 期 状 況 から 実 行 を 開 始 しても, 有 限 時 間 以 内 に 正 当 な 状 況 に 到 達 すること( 収 束 性 )を 保 証 する. 任 意 初 期 状 況 から 始 まるどのような 実 行 も 問 題 の 条 件 を 満 たす 時,この 状 況 を 正 当 な 状 況 と 呼 ぶ. 自 己 安 定 アルゴリズムは 任 意 の 初 期 状 況 から 実 行 を 開 始 して も,やがてシステムが 自 律 的 に 目 的 の 性 質 を 満 たすため, 優 れた 自 律 適 応 性 を 持 つ( 図 1).また, 実 行 開 始 時 にシステム 状 況 の 初 期 化 を 必 要 としない 点 も, 集 中 型 のアルゴリズムとの 大 きな 相 違 である. 図 1: 自 己 安 定 アルゴリズムの 一 例 ( 全 域 木 作 成 問 題 ) 3-2 研 究 成 果 本 研 究 では 自 己 安 定 アルゴリズムの 収 束 途 中 における 各 計 算 機 の 状 態 変 更 回 数 に 着 目 した, 以 下 の 2 つの 性 質 それぞれを 持 つ 自 己 安 定 アルゴリズムの 実 現 可 能 性 について 示 した. - 単 調 収 束 性 :どのような 実 行 においても, 各 計 算 機 は 状 態 を 1 度 でも 更 新 すれば, 正 当 な 状 況 での 状 態 となる. - 出 力 単 調 収 束 性 :どのような 実 行 においても, 各 計 算 機 は 出 力 変 数 を 1 度 でも 更 新 すれば, 出 力 変 数 の 値 は 正 当 な 状 況 での 値 となる. 440

2 つの 概 念 の 違 いは, 単 調 収 束 性 が 計 算 機 の 状 態 (つまり, 内 部 変 数, 出 力 変 数 すべて)の 更 新 を 対 象 と しているのに 対 し, 出 力 単 調 収 束 性 は 出 力 変 数 のみの 更 新 を 対 象 としている 点 である. 単 調 収 束 性 では, 計 算 機 は 自 身 の 状 態 ( 入 力 変 数, 内 部 変 数, 出 力 変 数 )と 隣 接 する 計 算 機 の 状 態 から, 正 当 な 状 況 での 正 し い 状 態 を 計 算 しなければならない. 一 方, 出 力 単 調 収 束 は, 内 部 変 数 を 用 いて 計 算 機 どうしで 十 分 に 情 報 交 換 を 行 った 後 に, 出 力 変 数 を 更 新 する 余 地 がある. 出 力 変 数 をただ 1 度 しか 更 新 しないという 枠 組 みは 分 散 システムにおける 合 意 問 題 等 でも 扱 われており, 一 般 的 な 設 定 であると 言 える. 単 調 収 束 性 は 通 信 やメモリの 下 界 を 示 すために 提 案 した 制 約 であるのに 対 し, 出 力 単 調 収 束 性 は 自 己 安 定 アルゴリズムとしての 実 現 に 興 味 を 置 いた 制 約 である. 以 下 に 本 研 究 の 結 果 の 概 要 を 示 す. 1. 単 調 収 束 性 の 実 現 可 能 性 : 局 所 的 な 問 題 以 外 については 単 調 収 な 自 己 安 定 アルゴリズムは 実 現 不 可 能 であることを 示 した. 局 所 的 な 問 題 とは, 各 計 算 機 が 隣 接 する 計 算 機 の 状 況 からのみから 正 当 な 状 況 での 自 身 の 状 態 を 計 算 できる 問 題 である.このような 問 題 としては, 頂 点 彩 色 問 題 (G の 各 頂 点 にど の 隣 接 頂 点 とも 異 なる 色 を 塗 る 問 題 )が 挙 げられる. 分 散 アルゴリズムの 多 くは, 計 算 機 が 相 互 に 情 報 交 換 を 行 い,システム 全 体 として 何 らかの 強 調 動 作 を 行 うことを 要 求 するため,このような 問 題 の クラスは 非 常 に 小 さい. 2. 出 力 単 調 収 束 性 の 実 現 可 能 性 : 全 域 木 問 題, 極 大 独 立 点 集 合 問 題, 極 大 マッチング 問 題 について 出 力 単 調 収 束 性 を 持 つ 自 己 安 定 アルゴリズムは 実 現 不 可 能 であることを 示 した. 本 質 的 な 難 しさは, 任 意 の 初 期 状 況 において 局 所 的 な 情 報 のみから 正 しい 出 力 変 数 の 値 を 得 られないことにある. 困 難 さの 原 理 は 以 下 の 通 りである: 出 力 単 調 収 束 性 を 持 つ 自 己 安 定 アルゴリズムが 存 在 すると 仮 定 すれば,その アルゴリズムはどのような 局 所 的 な 状 況 ( 隣 接 する 計 算 機 の 集 合 や,それら 計 算 機 の 状 態 )であれば 計 算 機 が 出 力 変 数 を 更 新 するかを 規 定 している.ある 分 散 システム G で 計 算 機 p が 出 力 変 数 を 更 新 す る 局 所 的 な 状 況 が 存 在 すれば, 他 の 分 散 システム G においても 同 じ 局 所 的 な 状 況 で p は 出 力 変 数 を G と 同 様 の 値 に 更 新 してしまう.しかし, 上 記 に 挙 げた 3 つの 問 題 については, 局 所 的 な 状 況 が 同 一 であっても 正 当 な 状 況 では p が 異 なる 出 力 変 数 をとるような G, G が 存 在 することが 示 せる.たとえ ば, 全 域 木 作 成 問 題 においては,G と G で 全 域 木 の 根 となる 計 算 機 の 場 所 が 異 なる 場 合 が 挙 げられ る. 3. 各 計 算 機 の 出 力 変 数 の 更 新 回 数 が 定 数 である 自 己 安 定 アルゴリズム: 極 大 独 立 点 集 合 問 題, 極 大 マッ チング 問 題 について, 任 意 の 実 行 における 各 計 算 機 の 出 力 変 数 の 更 新 回 数 が 高 々2 回 であるような 自 己 安 定 アルゴリズムをそれぞれ 作 成 し,その 正 当 性 を 証 明 した. 出 力 変 数 の 更 新 回 数 を 削 減 した 一 方 で,ネットワーク 全 体 で 情 報 収 集 を 行 うため, 既 存 の 自 己 安 定 アルゴリズムより 実 行 時 間 は 長 い. 3 センサネットワークにおけるデータ 収 集 とストリームデータ 処 理 センサネットワークを 敷 設 する 目 的 は, 対 象 とする 地 理 領 域 の 観 測 である. 各 センサ 端 末 が 観 測 した 観 測 データをシンクと 呼 ばれる 指 定 されたセンサ 端 末 に 収 集 するデータ 収 集 機 能 は,センサネットワークのもっ とも 基 本 的 な 機 能 である. 本 節 では, 観 測 データの 収 集,また 収 集 したデータの 処 理 手 法 についての 成 果 の 概 要 を 示 す. 3-1 研 究 背 景 センサネットワークにおける 従 来 のデータ 収 集 手 法 の 多 くは,シンクを 根 とする 根 付 き 内 向 木 を 作 成 し( 図 2), 内 向 木 の 葉 から 根 へと 観 測 データをストア アンド フォワードで 収 集 する[1].しかし,このような 手 法 では,シンク 周 辺 のセンサ 端 末 が 多 くの 観 測 データの 中 継 を 行 うため, 無 線 通 信 により 電 池 を 消 耗 し, 早 期 に 停 止 する 可 能 性 がある. 停 止 するセンサ 端 末 が 発 生 した 場 合 に, 観 測 領 域 の 一 部 から 観 測 データを 収 集 できなくなる 可 能 性 があるため,センサネットワークの 長 寿 命 化 を 目 指 す 負 荷 分 散 手 法 がよく 研 究 されてい る[3]. 本 研 究 では,データ 収 集 に 用 いる 経 路 集 合 (データ 収 集 トポロジ)をセンサ 端 末 の 電 池 残 量, 停 止 や 追 加 に 応 じて 変 更 する 手 法 を 提 案 する.また,データ 収 集 トポロジに DAG を 用 いることにより, 電 池 消 耗 による センサ 端 末 の 停 止 があっても,データ 収 集 トポロジが 非 連 結 になることを 回 避 する.データ 収 集 においては, 中 継 端 末 の 電 池 残 量 を 考 慮 することにより 負 荷 分 散 を 行 い, 観 測 データの 転 送 を 多 重 化 することでセンサ 端 末 の 停 止 があってもデータが 消 失 なくシンクに 配 送 されることを 保 証 する. 441

(a) フィールド 内 での 配 置 (b) 全 域 木 によるデータ 収 集 (c)dag によるデータ 収 集 図 2: 無 線 センサネットワーク 無 線 センサネットワークにおいて, 各 々のセンサ 端 末 が 観 測 し,シンクに 配 送 される 観 測 データは 1 つの データストリームと 見 なすことができる. 大 規 模 なデータストリームに 対 する 効 率 のよいストリーム 処 理 技 術 が 近 年 注 目 を 集 めており, 本 研 究 ではその 中 でも 基 本 的 な 問 題 のひとつである 頻 出 アイテム 検 知 問 題 に 着 目 する. 頻 出 アイテム 検 知 は, 与 えられたストリームデータ 中 に 一 定 割 合 以 上 出 現 するデータを 抽 出 するものであ る. 単 一 ストリーム 上 の 頻 出 アイテム 検 知 問 題 について,これまでさまざまな 研 究 がなされてきたが[2,7,8], いずれもストリーム 長 N に 対 して,O(log N)ビットを 要 する. 本 研 究 では,O(log log N)ビットのメモリで, 高 確 率 ですべての 頻 出 アイテムを 出 力 する 乱 択 アルゴリズムを 示 す. 提 案 アルゴリズムは 指 数 近 似 による 頻 出 アイテムの 数 え 上 げのアイデアをもとにしている. 使 用 するメモリサイズより, 既 存 の 頻 出 アイテム 検 知 アルゴリズムと 比 較 してメモリオーバーフローに 対 してロバストであると 言 える. 3-2 研 究 成 果 :センサネットワークにおける 自 己 安 定 データ 収 集 手 法 (1)センサネットワーク センサネットワークをグラフ G=(V, E)で 表 わされる 分 散 システムとする. 頂 点 集 合 V はセンサ 端 末 の 集 合 に,E は 無 線 通 信 により 決 まるセンサ 端 末 間 の 隣 接 関 係 を 表 す.V 中 には,シンクと 呼 ばれる 特 別 なセンサ 端 末 がただ 1 つだけ 含 まれているとする. 各 センサ 端 末 は 電 池 駆 動 であり, 各 時 点 において 自 身 の 電 池 残 量 を 知 ることができる. 各 センサ 端 末 はデータの 送 受 信, 定 期 的 なセンシングを 行 う. センシング 対 象 領 域 内 にはセンシングポイントと 呼 ばれる 点 集 合 が 指 定 されているとする.すべてのセン シングポイントがセンサ 端 末 のセンシング 半 径 に 含 まれる 時,センシング 対 象 領 域 は 被 覆 されていると 言 う.すべてのセンシングポイントが k 個 以 上 の 起 動 状 態 のセンサ 端 末 のセンシング 半 径 内 にある 時,そのよ うな 最 大 の k に 対 して,センシング 対 象 領 域 が k 重 被 覆 されていると 言 う. 各 センサ 端 末 はセンシング 半 径 内 のデータを 観 測 でき, 自 身 が 観 測 できるセンシングポイントを 知 っているとする.また,センシング 半 径 はセンサ 端 末 の 通 信 距 離 よりも 十 分 小 さく,あるセンシングポイントを 観 測 できるセンサ 端 末 は 互 いに 隣 接 しているとする. (2) 提 案 手 法 提 案 手 法 は,シンク 端 末 をシンクとする DAG を 構 成 する 自 己 安 定 アルゴリズムと,この DAG 上 でのデータ 収 集 アルゴリズムから 成 る. DAG 構 成 における 各 センサ 端 末 の 処 理 は 以 下 の 4 つの 手 順 から 成 る: 1. シンクからのホップ 数 計 算 : 幅 優 先 探 索 を 用 いた 既 存 の 自 己 安 定 全 域 木 作 成 アルゴリズムと 同 様 の 手 順 により, 各 センサ 端 末 がシンクからの 距 離 (ホップ 数 )を 得 る. 2. 各 センサ 端 末 の 転 送 先 の 選 択 :1 で 得 られたホップ 数 をもとに, 各 センサ 端 末 は 自 身 よりシンクに 近 いセンサ 端 末 のうち 1 つを 転 送 先 として 選 ぶ. 3. 各 センシングポイントの 2 重 被 覆 の 保 証 : 各 センシングポイントを 2 重 被 覆 するためのセンサ 端 末 を 2 つ 選 択 する. 提 案 手 法 では, 電 池 残 量 の 多 いセンサ 端 末 を 選 択 する.つまり, 各 計 センサ 端 末 はセ ンシング 領 域 内 の 各 センシングポイントについて, 電 池 残 量 について 上 位 2 位 のセンサ 端 末 をそのセ ンシングポイントの 観 測 者 と 見 なす. 各 センサ 端 末 には 自 身 のセンシング 領 域 内 のセンシングポイン トが 与 えられており,また,あるセンシングポイントをセンシング 領 域 にもつセンサ 端 末 は 互 いに 通 442

信 可 能 であると 仮 定 しているため, 各 センシングポイントについてちょうど 2 個 のセンサ 端 末 が 観 測 を 行 うこととなる. 4. 各 センサ 端 末 が 転 送 先, 迂 回 先 を 複 数 持 つ DAG の 作 成 : 各 センサ 端 末 は 隣 接 するセンサ 端 末 のうち, シンクからの 距 離 が 自 身 と 同 じものを 選 択 し, 迂 回 先 とする. 各 センサ 端 末 が 取 得 した 観 測 データは, 上 記 の 自 己 安 定 アルゴリズムによって 作 成 された DAG に 沿 って 中 継 され,シンクに 配 送 される. 配 送 途 中 のデータの 消 失 に 備 えるため, 観 測 を 行 うセンサ 端 末 は 現 在 の 観 測 データと 直 前 の 観 測 データを 1 つのデータとして 転 送 する.1 つの 観 測 データにつき,2 個 のコピーが 転 送 さ れることになるので, 中 継 途 経 路 上 のセンサ 端 末 が 1 つ 停 止 してもデータが 失 われることはない. データ 収 集 トポロジ,データ 収 集 ともに 複 数 のセンサ 端 末 が 停 止 や 故 障 する 場 合 には 正 当 性 を 保 証 できな い.そのような 場 合 には,アルゴリズムの 自 己 安 定 性 により 上 記 の 機 能 が 自 律 的 に 回 復 されることのみが 保 証 される. 3-3 研 究 成 果 :ストリームデータからの 頻 出 アイテム 検 知 手 法 (1) 頻 出 アイテム 検 知 問 題 Σ をアイテムの 有 限 集 合 とする.Σ の 要 素 から 成 る 入 力 ストリームを 系 列 x = (x 1, x 2,..., x N ) とした 時, 指 定 された 閾 値 θ (0,1] に 対 して,x 中 に θn 回 以 上 出 現 するすべてのアイテムを 出 力 せよ. (2) 提 案 手 法 ストリームデータ 処 理 では, 入 力 ストリームのサイズが 予 め 分 からない 場 合 にも 正 しく 動 作 することが 必 要 である.つまり,どのようなサイズの 入 力 ストリームに 対 しても,メモリオーバーフローが 生 じず, 高 速 に 終 了 することが 期 待 される.つまり,ストリーム 全 体 を 一 度 メモリ 上 に 保 存 し, 複 数 回 走 査 するのではな く, 入 力 ストリームの 各 要 素 に 対 して,オンラインに 処 理 を 行 うことが 必 要 である. 提 案 手 法 は 入 力 ストリーム 中 のアイテムの 一 様 乱 択 により, 頻 出 アイテムの 検 知 を 実 現 する.ストリーム 長 N が 既 知 であれば, 適 切 に 選 んだ c を 用 い, 一 定 の 割 合 c/n で 乱 択 を 行 えば, 所 望 の 精 度 を 保 証 する 一 様 乱 択 は 容 易 である.しかし,ストリームデータでは 一 般 的 に 事 前 にその 長 さ N を 知 ることは 不 可 能 である. 簡 単 のために,1 つのアイテム a から 成 るストリームデータを 想 定 する.アイテム a が 頻 出 であるかどう か(ストリーム 中 にθ 割 以 上 出 現 するか)はストリームの 最 後 の 要 素 が 入 力 されるまで 判 定 できない.ここ でストリームの 長 さを 数 える 問 題 を 考 える. 提 案 手 法 では 既 に 読 み 込 んだストリーム 長 に 合 わせて, 乱 択 確 率 を 減 少 する.つまり,K 個 のサンプルを 保 持 できる 領 域 を 使 用 できる 時,その 領 域 を 使 用 しきるまでは 確 率 1/2 で,その 後 は 1/2 2,1/2 3,1/2 4, と 乱 択 確 率 を 減 少 させていく. 乱 択 確 率 を 減 少 する 際, 既 にメモリ 内 に 保 持 しているアイテムに 対 しては, 確 率 1/2 で 再 度 乱 択 を 行 えば, 常 に 一 様 乱 択 したサンプルを 保 持 できる.このような 手 順 で,( 現 在 保 持 してい るサンプル 数 ) ( 現 在 の 乱 択 確 率 ) -1 がストリーム 長 の 近 似 値 となるような 数 え 上 げを 行 える.また, 入 力 ストリーム 中 での 頻 出 アイテムは 高 確 率 でサンプル 中 でもθ 割 以 上 出 現 することが 保 証 できる. 数 え 上 げのために 提 案 手 法 が 必 要 とするメモリサイズは 高 確 率 で log log N ビットである.アルゴリズム 終 了 時 に 乱 択 確 率 は 高 確 率 で 2 -logn であることが 保 証 できる.この 確 率 をそのまま 保 持 するには log N ビット が 必 要 である.しかし, 確 率 1/2 のコインフリップを log N 回 行 えば,2 -logn を 実 現 することができ,log N は log log N ビットで 表 現 することができる.K については,θ やアルゴリズムの 終 了 確 率 には 依 存 するものの, N に 無 関 係 に 選 ぶことができる. 提 案 する 頻 出 アイテム 検 知 手 法 の 性 能 は 以 下 の 通 りである. 任 意 のθ (0,1),γ (0,1),δ (0,1) に 対 し て,K=2 b, b= lg((θγ/2) -2 ln(3((1-γ/2) θγ) -1 ))+3 とした 時, 任 意 のストリームに 対 して 以 下 の 出 力 を 行 い 提 案 アル ゴリズムが 終 了 する 確 率 は 1- δ である:(i) θn 回 以 上 出 現 するアイテムをすべて 含 み,(ii) 出 現 回 数 が (1-γ)θN 未 満 のアイテムを 含 まない.アルゴリズム 全 体 で 使 用 するメモリは O((log 2 θ -1 ) / θ 2 + log log N)ビット である. 計 算 時 間 については, 提 案 手 法 は 各 入 力 アイテムに 対 して 平 均 的 に 定 数 時 間 で 動 作 する. 443

4 おわりに 本 研 究 では,センサネットワークの 自 律 的 かつ 安 定 的 運 用 手 法 の 確 立 を 目 指 し,アルゴリズム 設 計 理 論 の 観 点 からは 自 己 安 定 アルゴリズムの 出 力 変 更 回 数 の 削 減 に 着 目 し, 観 測 データ 処 理 の 観 点 からはデータの 収 集 とストリーム 処 理 に 着 目 した. 得 られた 結 果 はセンサネットワークのみならず, 他 の 分 散 システムやデー タ 処 理 にも 有 用 なものであり, 今 後 はより 広 い 分 野 での 発 展 が 期 待 される. 本 研 究 では 理 論 的 な 枠 組 みの 中 での 正 当 性, 性 能 保 証 を 主 眼 に 置 いたが, 実 際 のセンサネットワークでの 運 用 手 法 についてはさらなる 検 討 や 実 装 実 験 が 必 要 である. 今 後 は 理 論 的 な 側 面, 実 用 上 の 側 面 両 方 から 研 究 をすすめる 必 要 がある. 参 考 文 献 1. N. Burri, P. von Rickenbach, and R. Wattenhofer. Dozer: Ultra-low power data gathering in sensor networks. In Proc. of IPSN 2007, pp. 250 259. 2. E.D. Demaine, A. Lopez-Ortiz, and J.I. Munro. Frequency estimation of internet packet streams with limited space. In Proc. of ESA 2002, pp.348--360. 3. J. Deng, Y.S. Han, W.B. Heinzelman, and P.K. Varshney. Balanced energy sleep scheduling scheme for high-density cluster-based sensor networks. Computer Communications, 28, pp. 1631 1642, 2005. 4. E.W. Dijkstra. Self-stabilizing systems in spite of distributed control. Communications of ACM, 17 (11), pp.643 644, 1974. 5. S. Dolev. Self-stabilization. The MIT Press, 2000. 6. S.T. Huang. A self-stabilizing algorithm for constructing breadth-first trees. Information Processing Letters, 41, pp.109-117, 1992. 7. R.M. Karp, S. Shenker, and C. Papadimitriou. A simple algorithm for finding frequent elements in streams and bags, ACM Transactions on Database Systems, 28,pp.51--55, 2003. 8. G.S. Manku, and R. Motwani. Approximate frequency counts over data streams. In Proc. of VLDB 2002, pp.346--357. A randomized algorithm for finding frequent elements in streams using O(log log N) space. Monotonic Stabilization. 発 表 資 料 題 名 掲 載 誌 学 会 名 等 発 表 年 月 Proc. of 22nd International Symposium on Algorithms and 2011 年 12 月 Computation, pp.514 523. 自 己 安 定 アルゴリズムの 出 力 変 化 回 数 削 減 手 法 の 提 案. ストリーム 中 の 頻 出 アイテム 発 見 に 対 する O(loglogN) 領 域 乱 択 アルゴリズム 無 線 センサネットワークでのノードの 停 止 追 加 を 考 慮 した 省 電 力 データ 収 集 手 法. Proc. of 14th International Conference on Principles of Distributed Systems, pp. 475 490. 情 報 処 理 学 会 研 究 報 告, Vol.2012-MPS-87, No.4, pp.1-8. 情 報 処 理 学 会 研 究 報 告, Vol.2011-AL-137, No.1, pp.1 5. 情 報 処 理 学 会 研 究 報 告, Vol.2011-MPS-82, No.7, pp.1--6 2010 年 12 月 2012 年 3 月 2011 年 11 月 2011 年 3 月 444