情報滞留へのネットワーク理論における被覆問題の適用に関する研究

情報滞留へのネットワーク理論における被覆問題の適用に関する研究 A Study on Applying a Covering Problem in Network Theory to Information Floating

電気電子情報通信工学専攻 柏原 篤志 Atsushi KASHIWABARA

1.は じ め に

近 年 ，無 線 通 信 技 術 の 発 達 に よ り ，ス マ ー ト フ ォ ン な ど の 携 帯 端 末 が 急 激 に 普 及 し て い る ． こ れ に 伴 い ， 無 線 携 帯 端 末 の み で ネ ッ ト ワ ー ク を 構 築 す る ア ド ホ ッ ク ネ ッ ト ワ ー ク[1]に 注 目 が 集 ま っ て い る ．ア ド ホ ッ ク ネ ッ ト ワ ー ク の 通 信 方 式 の ひ と つ に エ ピ デ ミ ッ ク 通 信 [2]と 呼 ば れ る 方 式 が あ る ．エ ピ デ ミ ッ ク 通 信 で は ，情 報 は 端 末 同 士 の 通 信 と 端 末 の 移 動 に よ っ て 伝 達 さ れ る ． こ の エ ピ デ ミ ッ ク 通 信 の 応 用 例 と し て ， 地 域 情 報 配 信 や 災 害 時 の 情 報 配 信 ， 広 告 情 報 配 信 等 が あ る ．

情 報 配 信 等 で は ， 特 定 地 域 に い る 不 特 定 の 相 手 に 情 報 を 伝 達 さ せ る こ と が 目 的 と な る ． こ の よ う な 場 合 ， 情 報 の 宛 先 は 端 末 で は な く 場 所 や 空 間 で あ り ， 現 在 そ の 場 所 に 存 在 す る 端 末 だ け で は な く ， 後 か ら 到 着 す る 端 末 に 対 し て も 情 報 を 伝 達 さ せ る 必 要 が あ る ． 情 報 滞 留 は 空 間 に 情 報 が 「 滞 留 」 し て い る か の よ う な 状 況 を 維 持 す る 手 法 で あ る ． エ ピ デ ミ ッ ク 通 信 で は 隣 接 関 係 に あ る 端 末 が 多 け れ ば 多 い ほ ど 情 報 を 伝 達 す る こ と が 可 能 と な る ． 人 が 多 く 集 ま る 場 所 （ 駅 ， 公 園 ， シ ョ ッ ピ ン グ モ ー ル な ど ） は パ ブ リ ッ ク ス ペ ー ス と 呼 ば れ ， 情 報 の 滞 留 場 所 と し て 有 効 で あ る と 予 想 で き る ． そ し て パ ブ リ ッ ク ス ペ ー ス で な く と も 端 末 の 集 ま る 場 所 を 特 定 で き れ ば ， さ ら に 効 率 よ く 情 報 を 伝 達 で き る ．

こ の 滞 留 し や す い 場 所 の 特 定 に つ い て ， 被 覆 問 題[3]

を 適 用 さ せ て 解 く こ と を 提 案 す る ． 通 信 網 や 道 路 網 な ど の ネ ッ ト ワ ー ク の モ デ ル 化 で あ る フ ロ ー ネ ッ ト ワ ー ク に お い て ， 設 備 の 最 適 な 配 置 場 所 を 求 め る ロ ケ ー シ ョ ン 問 題 が あ り ， 被 覆 問 題 は そ の 一 種 で あ る ． 被 覆 問 題 を 用 い る 方 法 の 他 に ， 媒 介 中 心 性 を 用 い た 方 法 を 2 種 類 ， ま た ， 単 純 な 方 法 と し て ラ ン ダ ム に 決 定 す る 場 合 を 考 え ， シ ミ ュ レ ー シ ョ ン に よ り 比 較 評 価 を 行 う ． 2.情 報 滞 留

情 報 配 信 等 を 端 末 同 士 の 通 信 の み で 行 う と す る と ， そ れ ぞ れ の 端 末 が 情 報 源 と な り ， 情 報 を 所 有 す る 端 末 が 特 定 地 域 内 か ら 消 え る と 情 報 も 消 え て し ま う ． し た が っ て ， 情 報 が 存 続 す る よ う な 工 夫 が 必 要 で あ る ．

情 報 滞 留 は エ ピ デ ミ ッ ク 通 信 を 利 用 し た ， 情 報 を 空 間 的 に 維 持 す る 手 法 で あ る ． エ ピ デ ミ ッ ク 通 信 は 無 線 携 帯 端 末 の み で 構 成 さ れ た ネ ッ ト ワ ー ク で 行 わ れ ， 情 報 は 端 末 同 士 の 通 信 と 端 末 の 移 動 に よ っ て 伝 達 さ れ る ．

宛 先 ま で の 連 結 し た 通 信 経 路 を 想 定 し な い こ と が 特 徴 で あ る ． こ の エ ピ デ ミ ッ ク 通 信 を 用 い る こ と で ， 理 想 的 に は ， 特 定 地 域 内 に 侵 入 し た 端 末 が 情 報 所 有 端 末 と 接 触 ・ 保 持 し ， 特 定 地 域 か ら 出 る ま で の 間 に 別 の 端 末 へ 情 報 を 伝 達 す る こ と に よ り ， 端 末 の 行 き 来 に 関 わ り な く 情 報 が 空 間 的 に 滞 留 す る 手 法 と な る ．

情 報 滞 留 に 関 し て ， そ の 滞 留 特 性 が 様 々 な 状 況 で 解 析 さ れ て い る ． 本 論 文 で は ， 端 末 の 移 動 に つ い て ， 経 路 上 の 辺 の 重 み に 従 っ て 確 率 的 に 移 動 す る モ デ ル を 構 築 し て い る ．

3.被 覆 問 題

通 信 網 や 輸 送 網 な ど の ネ ッ ト ワ ー ク に お い て ， 種 々 の 施 設 を 配 置 す る 際 に そ の 最 適 な 位 置 を 求 め る 問 題 を ネ ッ ト ワ ー ク の ロ ケ ー シ ョ ン 問 題 と い い ， 被 覆 問 題 は ロ ケ ー シ ョ ン 問 題 の 一 種 で あ る ． 被 覆 問 題 は 辺 の 重 み と し て 容 量 を 与 え た フ ロ ー ネ ッ ト ワ ー ク に お い て 考 え ら れ る ． ま た ， 無 向 フ ロ ー ネ ッ ト ワ ー ク で の 被 覆 問 題 を 解 く ア ル ゴ リ ズ ム が 存 在 す る ． 本 論 文 で は ， 情 報 の 滞 留 場 所 を 決 定 す る 際 に 重 み 付 き グ ラ フ に 対 し て 被 覆 問 題 を 適 用 し ， そ の 解 を 用 い る 手 法 を 提 案 す る ． 3.1 被 覆 問 題 の 定 義

本 論 文 で は ，無 向 フ ロ ー ネ ッ ト ワ ー ク𝑁 = (𝑉, 𝐸, 𝑤)を 用 い る ．こ こ で ，𝑉を 点 集 合 ，𝐸を 辺 集 合 と し ，辺𝑒 ∈ 𝐸 に 付 与 さ れ て い る 重 み を𝑤(𝑒)と す る ． ま た ， 点𝑢, 𝑣 ∈ 𝑉 を 端 点 と す る 辺 に つ い て ，𝑒(𝑢, 𝑣)と 記 述 す る こ と も あ る ． 無 向 フ ロ ー ネ ッ ト ワ ー ク に お い て ， 点𝑢か ら 点𝑣へ の 最 大 フ ロ ー 値 を𝑔(𝑢, 𝑣)と す る ．ま た ，点 集 合𝐴か ら 点 集 合𝐵を𝑔(𝐴, 𝐵)と す る ．

被 覆 問 題 は𝑁上 の 供 給 元 と な る 点 か ら 任 意 の 点 ま で の 最 大 フ ロ ー 値 が 要 求 容 量𝑟以 上 と な る よ う に 点 を 配 置 し た と き ， そ の 要 素 数 最 小 を 求 め る 問 題 で あ る ． 総 合 被 覆 問 題 で は ，𝑔(𝑈, {𝑣}) ≥ 𝑟を 満 た す 要 素 数 最 小 の𝑈 が 解 と な る ．こ の と き ，𝑈は𝑁を𝑟 −総 合 被 覆 す る と い う ．

あ る 点 集 合𝑊に つ い て ，𝑊 = 𝑉ま た は𝑔(𝑊, 𝑉 − 𝑊) < 𝑟 の と き𝑊を 未 充 足 集 合 と い い ， 未 充 足 集 合 の う ち 真 部 分 集 合 と し て 未 充 足 集 合 を 含 ま な い も の を 極 小 な 未 充 足 集 合 と い う ． ま た ， 極 小 な 未 充 足 集 合 は 互 い に 素 で あ る こ と も わ か っ て い る ． そ し て 同 じ 集 合 に 属 す る 点 間 の 接 続 辺 は 比 較 的 容 量 が 大 き い ． 被 覆 問 題 の 解𝑈に つ い て ， そ の 要 素 は た だ ひ と つ の 極 小 な 未 充 足 集 合 に

属 す る と い う 特 徴 が あ る ． 以 下 の ア ル ゴ リ ズ ム A は ， 被 覆 問 題 の 解𝑈を 出 力 す る こ と が 知 ら れ て い る ．

3.2 被 覆 問 題 の 適 用

道 路 網 に お い て ， 道 路 を 辺 と し ， 道 路 同 士 が 交 わ る 箇 所 を 点 と す る ． 辺 の 重 み は ， 一 つ の 点 に 複 数 の 辺 が 接 続 さ れ て い る 状 況 で ， 点 に い る 端 末 が ど の 辺 に 移 動 す る か を 決 定 す る 確 率 と し て 重 み 付 け す る こ と と す る ． 重 み か ら 確 率 を 求 め る 計 算 式 は 式(1)で あ る ． 式(1)は ， 端 末 が い る 点 を𝑠，点𝑠の 隣 接 点 集 合 を𝑉𝑠と し た と き ，点 𝑖に 向 か っ て 移 動 す る 確 率𝑝_𝑠(𝑖)を 表 し た 式 で あ る ．

た だ し 式(1)の ま ま で は 目 的 地 に 到 着 す る こ と が 困 難 で あ る た め ，辺 の 重 み を 式(2)の よ う に 変 更 し て か ら 確 率 計 算 を 行 う こ と と す る ．変 更 後 が 式(3)で あ る ．こ こ で ，点𝑢, 𝑣間 の 距 離 を𝑑(𝑢, 𝑣)と し ，点𝑔は 各 端 末 の 目 的 地 点 と す る ．式(2)中𝑤(𝑒(𝑠, 𝑖)) − 𝛼 = 0と す る こ と で ，基 本 的 に 目 的 地 点 へ 向 か っ て 移 動 す る こ と に な る ．

𝑝_𝑠(𝑖) = 𝑤(𝑒(𝑠, 𝑖))

∑_{𝑘∈𝑉𝑠}𝑤(𝑒(𝑠, 𝑘)) (1)

𝑤′(𝑒(𝑠, 𝑖)) = { 𝑤(𝑒(𝑠, 𝑖)), 𝑑(𝑠, 𝑔) ≥ 𝑑(𝑖, 𝑔)

𝑤(𝑒(𝑠, 𝑖)) − 𝛼, 𝑑(𝑠, 𝑔) < 𝑑(𝑖, 𝑔) (2) 𝑝_𝑠(𝑖) = 𝑤′(𝑒(𝑠, 𝑖))

∑_{𝑘∈𝑉𝑠}𝑤′(𝑒(𝑠, 𝑘)) (3)

図1 パ ブ リ ッ ク ス ペ ー ス の モ デ ル

パ ブ リ ッ ク ス ペ ー ス の モ デ ル 化 を 上 記 の 重 み 付 け に 従 っ て 考 え る ． パ ブ リ ッ ク ス ペ ー ス で は 端 末 が 多 く 集 ま る た め ， 外 部 か ら 内 部 へ 侵 入 し や す い 重 み の 分 布 で あ る 必 要 が あ る ． そ の た め ， そ の 境 界 は 重 み の 差 は 大 き く な る ． ま た ， 内 部 に い る 端 末 は 滞 留 す る よ う に 移 動 す る た め ，境 界 よ り 内 側 は 重 み の 差 が 小 さ く な る ． よ っ て 図 1の よ う な ネ ッ ト ワ ー ク が パ ブ リ ッ ク ス ペ ー

ス の モ デ ル 化 と し て 考 え ら れ る ． な お ， 重 み の 大 き さ を 辺 の 太 さ で 表 現 し て い る ． そ し て こ れ は 被 覆 問 題 上 で 現 れ る 未 充 足 集 合 と 似 た 構 造 し て お り ， 被 覆 問 題 の 解 ＝ 未 充 足 集 合 の 要 素 ＝ パ ブ リ ッ ク ス ペ ー ス 内 部 ＝ 端 末 が 多 い と 予 想 さ れ る 場 所 と み な せ る の で ， 被 覆 問 題 を 適 用 さ せ て 解 く こ と で 情 報 の 拡 散 に 有 利 な 場 所 の 特 定 が 期 待 さ れ る ．

4. シ ミ ュ レ ー シ ョ ン の 概 要

シ ミ ュ レ ー シ ョ ン 実 験 で は ， 辺 の 重 み の 分 布 が 比 較 的 ラ ン ダ ム な ネ ッ ト ワ ー ク に お い て 「 滞 留 場 所 決 定 手 法 」 を 用 い る こ と で 情 報 の 滞 留 の し や す い 領 域 を 特 定 す る ．

・ 各 辺 に 一 様 分 布 に 従 っ て0,1,5,10の い ず れ か の 重 み を 付 与 す る ．

・ 各 辺𝑒(𝑖, 𝑗)に つ い て ， 端 点𝑖に よ っ て 隣 接 し て い る 辺 𝑒(𝑖,∗)と 端 点𝑗に よ っ て 隣 接 し て い る 辺𝑒(𝑗,∗)の 辺 の 重 み が 同 じ な ら ， 自 身 も そ の 重 み に 変 更 す る ．

以 上 の 手 順 に よ っ て 作 成 し た 10 個 の ネ ッ ト ワ ー ク を シ ミ ュ レ ー シ ョ ン で 用 い る ．

本 論 文 で は 滞 留 場 所 決 定 手 法 と し て 被 覆 問 題 を 適 用 さ せ て 解 く 方 法 を 提 案 す る ． ま た 比 較 対 象 と し て ， 媒 介 中 心 性 を 用 い る 方 法 ， ラ ン ダ ム に 決 定 す る 方 法 に つ い て も 実 験 す る ． 各 手 法 に よ っ て 求 め た 点 に 固 定 局 を 設 置 し ， 情 報 所 有 端 末 数 を 比 較 す る ． ま た ， 設 置 す る 固 定 局 を1~5台 ま で 増 や し ，固 定 局 数 に よ る 値 の 変 化 を 検 証 す る ．

4.1 シ ミ ュ レ ー シ ョ ン 条 件

シ ミ ュ レ ー シ ョ ン は ，1400 × 1400 [m]の エ リ ア 上 で 行 う ．エ リ ア は 縦 横50 [m]間 隔 で 格 子 状 の 道 路 が あ り ，端 末 は そ の 道 路 上 を 移 動 す る ． 端 末 は エ リ ア の 端 の い ず れ か の 点 か ら ポ ア ソ ン 分 布 に 従 っ て 現 れ る ． ま た ， 端 の 点 に 到 着 し た 端 末 は エ リ ア 上 か ら 消 滅 す る ． 端 末 は お 互 い が 通 信 範 囲 30[m]以 内 の 場 合 に 情 報 伝 達 を 行 う ．

ま た ， エ リ ア 上 に 現 れ た 端 末 は エ リ ア 内 の い ず れ か の 点 を 目 的 地 点 と し て 設 定 し ， 目 的 地 点 に 到 着 し た 後 は エ リ ア 端 の 点 を 目 的 地 点 と し て 設 定 す る こ と と す る ． こ れ に よ り ，エ リ ア 内 の 端 末 の 入 れ 替 わ り を 促 進 す る ． 各 パ ラ メ ー タ を 表 1に ま と め る ．

図2 シ ミ ュ レ ー シ ョ ン で 用 い る ネ ッ ト ワ ー ク ア ル ゴ リ ズ ム A

Step1 𝑈 ≔ 𝑉, (𝑉 = {𝑣₁, 𝑣₂, ⋯ , 𝑣_𝑛}) 𝑖 ≔ 1と す る

Step2 𝑈 − {𝑣_𝑖}が𝑁を 総 合 被 覆 す る 場 合 ， 𝑈 ≔ 𝑈 − {𝑣𝑖}

Step3 𝑖 = 𝑛の と き𝑈を 出 力 し て 終 了

そ う で な け れ ば𝑖 ≔ 𝑖 + 1と し て Step2へ

表1 シ ミ ュ レ ー シ ョ ン 条 件

固 定 局 数 1~5台

計 測 時 間 10000[s]

シ ミ ュ レ ー シ ョ ン 数 200回

端 末 の 速 さ 1.4[m/s]

通 信 範 囲 30[m]

辺 の 重 み 1~10

情 報 保 持 時 間 200[s]

端 末 発 生 確 率 平 均λの ポ ア ソ ン 分 布

α 1

λ 0.04[𝑠⁻¹]

4.2滞 留 場 所 決 定 手 法

辺 の 重 み の 分 布 に 規 則 性 が あ り ， パ ブ リ ッ ク ス ペ ー ス が 存 在 す る 場 合 ， そ の 領 域 を 滞 留 場 所 と し て 固 定 局 を 設 置 す る こ と で よ り 多 く 端 末 に 情 報 が 伝 達 さ れ る こ と が 予 想 で き る ． し か し 辺 の 重 み の 分 布 が ラ ン ダ ム な 状 況 で は ， 固 定 局 を 設 置 す る 目 安 と な る 場 所 が 特 定 で き な い ． そ の よ う な 状 況 に お い て 滞 留 場 所 決 定 手 法 を 用 い る こ と で ， ネ ッ ト ワ ー ク の い ず れ か の 点 に 固 定 局 を 設 置 す る こ と を 考 え る ． こ の 滞 留 場 所 決 定 手 法 と し て 被 覆 問 題 を 適 用 さ せ て 解 く 方 法 を 提 案 す る ． ま た 比 較 対 象 と し て ， ラ ン ダ ム に 配 置 場 所 を 選 択 す る 方 法 を 用 意 す る ． た だ し こ れ は 単 純 な 方 法 な の で ， 比 較 対 象 と し て さ ら に ， ネ ッ ト ワ ー ク の 中 心 性 に 関 し て 活 発 に 議 論 さ れ て い る 媒 介 中 心 性 を 用 い る 方 法 を 用 意 し た ． 4.2.1 被 覆 問 題 の 適 用 方 法

被 覆 問 題 を 適 用 す る 際 ， 辺 の 重 み を そ の ま ま 利 用 せ ず に 変 換 後 の 値 を 利 用 す る ． 今 回 は𝑤(𝑒) ↦ 𝑤(𝑒)³と し ， 重 み の 大 小 の 差 を 顕 著 に す る こ と で 未 充 足 集 合 が 形 成 さ れ や す い 状 況 を 作 る ．ま た ，要 求 容 量𝑟 = 2000と し て い る ． 固 定 局 を 配 置 す る 点 を 選 ぶ 優 先 順 位 と し て ， 要 素 数 の 大 き い 未 充 足 集 合 に 属 し て い る 点 を 選 択 す る ． 4.2.2 媒 介 中 心 性 を 適 用 す る 方 法 （ １ ）

媒 介 中 心 性 は ネ ッ ト ワ ー ク の 「 中 心 」 を 示 す 尺 度 の ひ と つ で あ る ． 媒 介 中 心 性 の 高 い 点 は ， 最 短 経 路 上 の 点 と し て 選 ば れ る た め ， 端 末 の 移 動 に よ っ て 訪 れ る 点 で あ る 可 能 性 が 高 く ， 滞 留 場 所 を 選 ぶ 指 標 と し て 適 し て い る と 考 え ら れ る ． 媒 介 中 心 性 を 計 算 す る 際 は ， 𝑤(𝑒) ↦ 1/𝑤(𝑒)と し 辺 の 重 み の 逆 数 を 用 い る こ と で ， 重 み が 大 き い ＝ コ ス ト が 小 さ い と し て 計 算 す る ．た だ し ， 0 ↦ ∞と す る ．

4.2.3 媒 介 中 心 性 を 適 用 す る 方 法 （ ２ ）

媒 介 中 心 性(1)で は 重 み を 単 純 な 変 換 に よ っ て 計 算 し て い る た め ， よ り 複 雑 な 方 法 と し て 辺 の 重 み を 交 通 流 量 の 容 量 と み な し ， 辺 の 長 さ を 再 評 価 す る 方 法 を 用

意 す る ．媒 介 中 心 性(2)の 手 法 で は 隣 接 す る 辺 の 重 み を 加 味 し て 計 算 し て お り ， 重 み の 大 き い 辺 と 小 さ い 辺 が 隣 接 し て い る と き ， 重 み の 大 き い 辺 は よ り コ ス ト が 小 さ く ， 小 さ い 辺 は よ り コ ス ト が 大 き く な る ． 5． シ ミ ュ レ ー シ ョ ン 結 果

図 3 は 情 報 所 有 端 末 の 累 計 を 示 し た グ ラ フ で あ り ， 図4は 端 末 が 情 報 を 所 有 し た こ と が あ る 割 合 を 示 し た グ ラ フ で あ る ． グ ラ フ よ り ， ど の 固 定 局 数 に お い て も 被 覆 問 題 の 値 が 大 き い こ と が 分 か る ． ま た ， 固 定 局 が 1台 の 場 合 と 比 較 し 2台 以 上 は 媒 介 中 心 性(1)，(2)と の 差 が 広 が っ て い る ．媒 介 中 心 性(1)よ り 媒 介 中 心 性(2)の 値 が 上 回 っ て い る が ， 被 覆 問 題 の 値 は そ れ 以 上 と な っ た ． ま た ， 固 定 局 が5台 の と き の 情 報 を 所 有 し た 端 末 の 割 合 を 図5に 示 す ． 図5よ り ， 被 覆 問 題 の 値 が ラ ン ダ ム の 場 合 と ほ ぼ 同 じ 時 刻 で 上 昇 し て い る こ と が わ か る ． ま た ， ラ ン ダ ム と 異 な り ， 上 昇 が 緩 や か に な っ た 後 も 下 降 す る こ と な く 高 い 割 合 を 保 っ て い る ．

図3 情 報 を 所 有 し た 端 末 の 累 計

図4情 報 を 所 有 し た 端 末 の 割 合

図5 情 報 を 所 有 し た 端 末 の 割 合 （ 固 定 局 5台 ）

0 100 200 300 400 500 600

1 2 3 4 5

r-cover betweenness1 betweenness2 random Number of terminals with information

Number of Fixed station

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

1 2 3 4 5

r-cover betweenness1 betweenness2 random Number of terminals with iformation

Number of Fixed station

0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500 6000 6500 7000 7500 8000 8500 9000 9500

Percentage of terminals with information

Time [s]

r-cover betweenness1 betweenness2 random

6.4 結 果 に 対 す る 考 察

被 覆 問 題 を 用 い た 配 置 方 法 が 媒 介 中 心 性 を 用 い た 配 置 方 法 よ り も 情 報 所 有 端 末 数 が 大 き く な っ た 理 由 と し て ， 固 定 局 同 士 を 近 す ぎ な い 距 離 で 配 置 で き た た め だ と 考 え ら れ る ． 固 定 局 間 の 距 離 が 小 さ い と き ， 一 方 の 固 定 局 が 被 覆 す る 領 域 と 他 方 の 固 定 局 の 領 域 が 重 な っ て 存 在 し て し ま い ， そ の 分 効 率 が 下 が っ て し ま っ た と 考 え ら れ る ． 図 6は 各 固 定 局 数 に お け る 固 定 局 同 士 の 距 離 の 平 均 を 示 し た グ ラ フ で あ る ． グ ラ フ よ り ， 被 覆 問 題 は 媒 介 中 心 性 と 比 較 し て ， 固 定 局 間 の 距 離 が 大 き く な っ て い る ． こ の 結 果 に お い て 最 も 固 定 局 間 の 距 離 が 大 き い の は ラ ン ダ ム で あ る ． し か し ， ラ ン ダ ム の 場 合 は 被 覆 す る 領 域 同 士 が 離 れ て い て も ， 被 覆 問 題 や 媒 介 中 心 性 と 比 較 し て そ こ を 訪 れ る 端 末 が 少 な い た め 情 報 所 有 端 末 数 が 小 さ く な っ た と 考 え ら れ る ．

図6 固 定 局 間 の 平 均 距 離

ま た ， シ ミ ュ レ ー シ ョ ン 中 で 端 末 が 頻 繁 に 訪 れ た 点 と 固 定 局 の 配 置 場 所 の 分 布 を 比 較 す る ． 図 7は シ ミ ュ レ ー シ ョ ン で 用 い た ネ ッ ト ワ ー ク の １ つ に つ い て ， 端 末 が 訪 れ た 回 数 を カ ウ ン ト し た と き の ， 値 ご と に 色 分 け し た 分 布 図 で あ る ． こ の 図 で は 昇 順 に ， 赤 紫 色 ， 赤 色 ， 橙 色 ， 黄 色 ， 青 色 ， 水 色 の 順 で 値 が 大 き い ． そ し て ，こ の 図 に 配 置 さ れ て い る 点 が 固 定 局 の 場 所 で あ る ． 被 覆 問 題 は 青 色 で 四 角 の 点 ，媒 介 中 心 性(1)は 橙 色 で 丸 の 点 ，媒 介 中 心 性(2)は 緑 色 で 三 角 の 点 で あ る ．図 よ り ， 端 末 の 訪 れ て い る 数 が 60 台 以 上 の 領 域 内 に あ る 固 定 局 は 被 覆 問 題 の 場 合 が 最 も 多 い ． し た が っ て 被 覆 問 題 を 用 い た 配 置 方 法 は 端 末 の 多 い 場 所 の 近 く に 固 定 局 を 配 置 で き る と い え る ． ま た ， 被 覆 問 題 に よ っ て 設 置 さ れ る 固 定 局 は ，ネ ッ ト ワ ー ク の 端 側 に も 存 在 し て い る ． し た が っ て ， 早 い 時 刻 で 端 末 に 情 報 を 伝 達 で き る 確 率 が 高 ま る た め ， ラ ン ダ ム の 場 合 と 同 等 の 時 刻 か ら 情 報 所 有 端 末 が 発 生 し た と 考 え ら れ る ．

図7に お い て ， 被 覆 問 題 の 解 の い く つ か の 点 が 端 末 到 達 数 の 大 き い 場 所 に 配 置 さ れ て い る が ， 端 末 到 達 数 が 大 き く と も 解 の 点 が な い 場 所 も 存 在 す る ． そ の よ う な 場 所 を 被 覆 問 題 が 特 定 で き な か っ た 理 由 と し て ， 境 界 の 辺 の 重 み の 合 計 が 僅 か に 大 き く ， 未 充 足 集 合 で な か っ た た め だ と 考 え ら れ る ．

図7 端 末 到 達 数 の 分 布 の 一 例 7． ま と め ・ 今 後 の 課 題

本 論 文 で は ， エ ピ デ ミ ッ ク 通 信 に よ る 情 報 滞 留 に つ い て ， 道 路 網 の モ デ ル に パ ブ リ ッ ク ス ペ ー ス の 概 念 を 導 入 し た ． 情 報 滞 留 特 性 を 高 め る た め ， よ り 効 率 の 良 い 滞 留 場 所 を 特 定 す る 方 法 と し て 被 覆 問 題 を 適 用 す る こ と を 提 案 し た ． 被 覆 問 題 を 解 く こ と で ， 媒 介 中 心 性 の 高 い 点 を 選 ぶ 方 法 や ラ ン ダ ム に 選 ぶ 方 法 と 比 較 し ， 情 報 所 有 端 末 数 を 増 加 さ せ る こ と が で き た ． 固 定 局 を 複 数 台 設 置 す る 状 況 に お い て ， 被 覆 問 題 は 固 定 局 同 士 の 距 離 を と る こ と が で き ， 効 果 を 重 複 さ せ な い こ と で 効 率 を 良 く し た こ と が わ か っ た ． 被 覆 問 題 の 解 と 端 末 到 達 数 の 分 布 を 比 較 し た と き ， 多 く 訪 れ る 領 域 に 解 の 点 が 含 ま れ な い 場 合 も あ っ た ． こ の 原 因 と し て ， そ の 領 域 と 外 部 と の 間 の 最 大 フ ロ ー 値 が 大 き い と 特 定 で き な く な る こ と が 考 え ら れ る ．

今 後 の 課 題 と し て ， 端 末 到 達 数 の 大 き い 領 域 を 特 定 で き る 確 率 を 上 げ る 改 良 方 法 の 提 案 ， そ し て 情 報 伝 達 の 向 上 だ け で な く ， 無 駄 に 情 報 が 拡 散 す る こ と を 防 ぐ た め に 通 信 を 抑 制 す る 方 法 の 開 発 等 が 挙 げ ら れ る ． 参 考 文 献

[1] 間 瀬 憲 一 ，中 野 敬 介 ，仙 石 正 和 ，篠 田 庄 司 ，“ ア ド ホ ッ ク ネ ッ ト ワ ー ク ，” 信 学 誌 Vol.84，No.2， pp.127-134，2001年2月 ．

[2] A．Vahdat，D．Becker，“Epidemic routing for partially-connected ad hoc network ， ” Technical Report，Duke University，April 2000．

[3] Hiroshi Tamura，Masakazu Sengoku，Shouji Shinoda，Takeo Abe，“Some Covering Problems in Location Theory on Flow Networks，”IEICE TRANS．FUNDAMENTALS，VOL．E75-A，NO．

6 JUNE 1992．

0 100 200 300 400 500 600 700 800

1 2 3 4 5

r-cover betweenness1

betweenness2 random

50 150 250 350 450 550 650 750 850 950 1050 1150 1250

50 150 250 350 450 550 650 750 850 950 1050 1150 1250 13501350

0-15 15-30 30-45 45-60 60-75 75-90

Distance[m]

Number of Fixed station