改良型 P2P ネットワークを利用した安否情報システムの提案 Safety

改良型 P2P ネットワークを利用した安否情報システムの提案
中山 淳也†
太田 学†
片山 薫†
石川 博†
†東京都立大学大学院工学研究科 〒192-0397 東京都八王子市南大沢 1-1
E-mail: †{nakayama, ohta, katayama, ishikawa}@ hikendbs.eei.metro-u.ac.jp
あらまし 災害時は，利用が集中することにより電話がつながりにくくなり，家族や知人の安否確認が非常に困
難になる．そこで，我々は既存の大規模なシステムに比べ，容易に低コストでシステム構成できる Pure PeerToPeer
（以下 P2P）ネットワークを利用した安否情報検索システムを開発している．これまでに検索履歴を用いてネット
ワーク負荷を軽減させる負荷低減型 Pure P2P ネットワークを利用した安否情報検索システムを提案したが，このシ
ステムでは，検索履歴が十分に蓄積されるまでの間，ブロードキャスト検索するためネットワーク負荷が大きいと
いう欠点がある．そこで，本研究は検索履歴が十分蓄積されていない状態においても, ネットワーク負荷を軽減す
るために，隣接ノードリストに含まれる登録ノードが設置された住所と検索者が入力した検索対象者の住所につい
て直接位置情報を算出し，距離が近いノードからクエリを出す手法を提案する．
キーワード ピアツーピア，情報検索，安否情報，位置情報
Safety information retrieval using modified P2P network
Junya NAKAYAMA†
Manabu OHTA†
Kaoru KATAYAMA†
and
Hiroshi ISHIKAWA†
†Graduate School of Engineering, Tokyo Metropolitan University
1-1 Minami-Osawa, Hachioji-shi, Tokyo, 192-0397 Japan
E-mail: †{nakayama, ohta, katayama, ishikawa}@ hikendbs.eei.metro-u.ac.jp
Abstract A centralized system such as the phone network does not resist the overload due to disasters. We are developing a
robust safety information retrieval system based on the Pure Peer-To-Peer (P2P) network using query history. However, this
retrieval system on the PureP2P network is not efficient because repeated broadcasting increases network load before a certain
amount of query history accumulates. Therefore, we propose an approach to reduce the load by finding the closest nodes to
calculated distance based on the geographical location information of nodes in a node-list and addresses of a target person .
Keyword PeerToPeer，Information Retrieval，Safety Information，Geographical Location Information
1. は じ め に
以 前 に 提 案 し た 負 荷 低 減 型 PureP2P シ ス テ ム で は 、 各
阪神大震災などの災害発生時には，利用が集中して
ノードが所持している検索履歴を用いて，過去に検索
電話がつながりにくくなり，家族や知人の安否確認が
がヒットしたノードへ，優先的にクエリを出す．これ
非 常 に 困 難 に な る [2,20,21]． ま た ， IAA（ I Am Alive）
に よ っ て ，ク エ リ を 送 信 す る ノ ー ド の 中 継 回 数 が 減 り ，
シ ス テ ム [1,21] や 静 岡 県 立 大 学 の 安 否 確 認 シ ス テ ム
ネ ッ ト ワ ー ク 負 荷 を 軽 減 さ せ る [19]． し か し ，こ の 負
[11,22]な ど ， イ ン タ ー ネ ッ ト を 利 用 し た 既 存 シ ス テ ム
荷 低 減 型 PureP2P ネ ッ ト ワ ー ク で は ， 十 分 に 検 索 履 歴
ではサーバに情報を登録するため，そこにアクセスが
が な い 場 合 ， Gnutella[3,5,12,15,16]や FreeNet[6,12] な
集中しダウンの可能性がある．また, 大規模なシステ
ど の 既 存 PureP2P シ ス テ ム や NeuroGrid[7,12]や 連 携 型
ムになりすぎて運営管理が大変である．そこで，本研
検 索 手 法 を 用 い た PureP2P シ ス テ ム [14]な ど と 同 様 に ，
究では，各ノードが最新の情報を保持し，容易に低コ
各ノードが所有している隣接ノードリスト（クエリを
ス ト で シ ス テ ム を 構 築 で き る Pure Peer-To-Peer（ 以 下
出すことができるノードの情報リスト）からブロード
P2P ） ネ ッ ト ワ ー ク を 利 用 す る ． 提 案 す る 安 否 情 報 シ
キャスト検索を行う．そのため，各ノードが所有して
ステムでは，災害時に避難場所に安否情報を登録する
いる検索履歴がある程度蓄積されるまで，ネットワー
ためのノード（コンピュータ）を設置し，検索者は身
ク負荷が大きいという欠点がある．そこで，住所のジ
近にある携帯用コンピュータなどからクエリを出す．
オ コ ー デ ィ ン グ [9,18]を 利 用 し ，避 難 場 所 に 設 置 さ れ た
図 1 P2PSystem
各ノードが所有している隣接ノードリストに含まれる
①
登録ノードとクエリに含まれる検索対象者の住所から
直接位置情報（緯度経度など）を算出する．そして，
②
検索対象者の住所から距離が近いノードへ検索を行う
改 良 型 P2P シ ス テ ム を 提 案 す る ．こ れ に よ り 、 検 索 履
歴がそれほど蓄積されていない状態でもネットワーク
③
負荷を軽減することができる．また，実際に起こった
地 震 （ 芸 予 地 震 [17]） を も と に し た シ ミ ュ レ ー シ ョ ン
実験によって，以前提案した検索方法（負荷低減型
④
PureP2P シ ス テ ム ） と の 比 較 評 価 を 行 っ た ．
以 降 ， 2 章 で は P2P シ ス テ ム の 概 要 ， 3 章 で は 関 連
⑤
研究との比較，4 章では提案システムについて説明す
る．5 章では提案システムの有効性を検証するための
ノード A は直接接続しているノード B
へ Query メ ッ セ ー ジ を 送 信 す る
Query メ ッ セ ー ジ を 受 け 取 っ た ノ ー ド B
は, すでに自分が受信したメッセージであ
れ ば 、処 分 し ,そ う で な い な ら 、自 分 の 接 続
す る ノ ー ド に Query メ ッ セ ー ジ を 送 信 す る
条件に合致するファイルを持つノード
C が ,QueryHit メ ッ セ ー ジ を Query メ ッ セ ー
ジが送信さてきた経路に沿って逆順に返
信する
ノ ー ド C か ら 送 信 さ れ た QueryHit メ ッ
セージをノード A に返信する
ノード A はノード C に対して直接接続
しファイルを要求し，そしてダウンロード
を実行する
実験について述べ，6 章では結論と今後の課題につい
図 2 Gnutella System
てまとめる．
2. P2P シ ス テ ム
2.1. 概 要
P2P シ ス テ ム [3,12,19]と は ，ピ ア（ Peer）と ピ ア（ Peer）
っていて，各ノードが実際のデータを持つ．情報を検
索するときは，サーバに接続し自分の欲しい情報が存
在するかを検索する．欲しい情報が見つかったら，そ
な関係で成り立ったシステム，つまり，構成するコン
の情報を持っているノードに直接接続しデータ取得す
ピュータが対等に処理を行うシステムのことである．
る ． 代 表 的 な も の に Napster[3,4,12]が あ り ， Hybrid 型
クライアント・サーバシステムでは，処理を要求し結
P2P シ ス テ ム に は 以 下 の 特 徴 が あ る ．
果を受け取るコンピュータがクライアントであり，要
求を受けて処理結果を返すコンピュータがサーバであ
•
認証，承認といったセキュリティの管理が行いや
ライアントでありサーバである．
すい．
P2P シ ス テ ム の 形 態 と し て は ， 大 き く 分 け て Hybrid
型 P2P と Pure 型 P2P の 2 つ の シ ス テ ム が 存 在 す る ．
•
検索効率は良い．しかし，検索対象がインデクス
2.2. Hybrid 型
されたものに限るので，常に新しい情報が得られ
Hybrid 型 P2P シ ス テ ム と は ，図 1 左 の よ う に サ ー バ
システムの中心にサーバがあるので，クライアント・
検索
サーバに集積したインデクスを検索するため，
それぞれの仕組みは以下の通りである．
と複数のノードによって構成されるシステムである．
セキュリティの管理
中央サーバを経由させるので，アカウント管理，
る が ， P2P シ ス テ ム で は ， す べ て の コ ン ピ ュ ー タ が ク
るとは限らない．
•
耐障害性
特定の機能を一箇所のサーバに依存しているの
サーバシステムと似ているが，実際は少し違う．サー
で，サーバがダウンするとシステムが使用不可能
バは各ノードに存在するデータのインデクス情報を持
になる．
•
運用管理コスト
中央サーバを用いるため，クライアント・サー
バ方式に比べたら，サーバコストは小さいが，そ
れでもサーバ強化のコストがかかる．
2.3. Pure 型
Pure 型 P2P シ ス テ ム と は ，Hybrid 型 P2P シ ス テ ム と
違い，中央サーバが存在しない各ノードのみで構成さ
れ る ネ ッ ト ワ ー ク こ と で あ る ．全 て の ノ ー ド が 対 等（ ピ
ア ）な 関 係 で あ る シ ス テ ム 形 態 で（ 図 1 右 参 照 ），全 て
のノードが互いに対等に処理要求を受けるサーバ
（ Server）で あ り ，処 理 要 求 す る ク ラ イ ア ン ト（ Client）
で あ る た め ，サ ー バ ン ト（ Servant=Server+Client）と 呼
ば れ て い る ．そ し て ，各 サ ー バ ン ト に デ ー タ を 登 録 し ，
図 3 連携型検索手法
検索はネットワークに接続している各サーバントに対
し て 行 う ．Pure 型 P2P シ ス テ ム に は 以 下 の 特 徴 が あ る ．
ド手順を図 2 に示す．
•
3. 関 連 研 究 と 提 案 シ ス テ ム の 比 較
セキュリティ管理
中心となるサーバを持たないため，アカウント
管理などのセキュリティ管理が難しい．一方，匿
名性の実現には適している．
•
•
検索
FreeNet[6,12]は ， 検 索 の 過 程 で 経 由 し た ノ ー ド に も
検索で得たデータを保存し，中継するノードは中継す
各サーバントに対してブロードキャスト検索を
るときに自分の情報保存領域にも同じデータのコピー
行うのでネットワーク負荷が大きい欠点があるが，
を保存する．すなわち情報を一箇所ではなく，より多
常に新しい情報を検索できる．
くのノードで保存し，早く検索結果が得られることを
耐障害性
目 的 と し て い る ． ま た ， ク エ リ を 出 す 方 法 は Gnutella
中央サーバを使わないので，障害には強い．
•
こ こ で ，Gnutella を 改 善 し た Pure 型 P2P シ ス テ ム と
提案システムとの違いについて説明する．
運用管理コスト
HybridP2P シ ス テ ム に 比 べ ，コ ス ト が 小 さ く 抑 え
られる．
と同様である．これに対して，提案システムは情報が
存在しそうな場所にクエリを送信することでクエリの
ノード中継回数を減らす．
NeuroGrid[7,13]は ， フ ォ ル ダ や デ ィ レ ク ト リ と い っ
た制限を取り払った一つのデータ管理システムである．
こ れ を 利 用 し た 最 も 基 本 的 な Pure 型 P2P シ ス テ ム は
このシステムは大きく 2 つの要素から構成される． 1
Gnutella[3,5,12,15,16]で あ る ．提 案 シ ス テ ム や 他 の 改 善
つはファイルのメタデータを変更する学習エンジンで，
さ れ た Pure 型 P2P に つ い て 議 論 す る た め に ， こ こ で
もう 1 つはファイルとノードの関係を記した知識デー
Gnutella の 仕 組 み に つ い て 説 明 す る ．
タ を 使 用 し ， 分 散 型 ネ ッ ト ワ ー ク の Query メ ッ セ ー ジ
Gnutella の 基 本 的 な 動 作 は ， 自 分 の 知 っ て い る 他 ノ
を制御するプロトコルである．前者は，キーワードと
ー ド に メ ッ セ ー ジ を 送 信 し ，そ の 応 答 を 待 ち ，そ し て ，
データを結び付けるために利用者の検索行動を監視す
メッセージを受信したノードは，更に他のノードへメ
る．つまり，利用者があるキーワードを使って検索し
ッセージを送信するという動作の繰り返しである．た
た後，どのファイルを開いたかまで分析し，キーワー
だし，ネットワークトラフィックの肥大化を防止する
ドとファイルの関係の強さについての情報を蓄え，検
た め に メ ッ セ ー ジ パ ケ ッ ト に 移 動 回 数 を 制 限 す る TTL
索に利用する．後者は，実世界での人に聞くというモ
（ Time To Live）が 設 定 さ れ る ．こ れ は 移 動 す る た び に
デルをシステム化したもので，ユーザが隣接している
値 を 1 ず つ 減 ら し ，0 に な っ た ら メ ッ セ ー ジ を 止 め る ．
ノードにフォワード（転送）するうちに，それぞれの
また，一度受けたメッセージの重複受け付け防止識別
NeuroGrid ノ ー ド が そ の ユ ー ザ に 適 切 な 情 報 を 提 供 す
子 に GUID （ Global Unique Identitifier ） を 与 え る ．
る か ど う か を 学 習 し ， 次 第 に Query メ ッ セ ー ジ を 効 率
Gnutella ネ ッ ト ワ ー ク 上 の フ ァ イ ル 検 索 と ダ ウ ン ロ ー
的にフォワードする．この 2 者が協調することで，学
各ノードが所持しているもの
(1) 隣接ノードリスト（緯度経度も付加）
(2) 検索履歴
(3) 緯度経度変換システム
図 4 応用例
習済みのメタデータによる経路判断と各々の経路判断
図 5
に対するユーザからの反応によるメタデータの更新が
可能となり，効率良く検索ができる．しかし，効率良
各ノードにおける検索処理
いて，クエリを出すノードを絞る．検索履歴中に，入
く検索させるための学習に，ある程度時間が掛かって
力項目すべてが一致したデータがあった場合，その情
しまうが，提案システムは検索履歴がなくても効率良
報の登録ノードへ優先的にクエリを送出する．また，
く検索ができる．
一致したデータがなかった場合，入力したキーワード
連 携 型 検 索 手 法 [14]と は ， 実 世 界 を モ デ ル と し た 検
を 使 い ， 検 索 履 歴 を OR 検 索 で ヒ ッ ト し た ノ ー ド の 中
索手法である．これをもとに，情報が存在しそうな情
からヒット件数が多い順に，クエリを出すノードの候
報源を【検索者の知識】とし，関連情報が存在しそう
補を決める手法である．検索履歴がない場合には，各
な情報源と，その情報源に対する評価を【情報源の情
ノードが所有している隣接ノードリストからランダム
報提供者の知識】と設定し，検索を行っている．この
にノードを選びクエリを転送する．このため各ノード
モ デ ル 化 は ，NeuroGrid と 同 じ 考 え で あ る ．例 と し て ，
が所有している検索履歴が，ある程度蓄積されるまで
検 索 者 は【 検 索 者 の 知 識 】か ら B に は ク エ リ を 出 さ ず
ネットワーク負荷が大きいという欠点がある．これを
に A に ク エ リ を 出 す ．別 の 情 報 源 に 検 索 提 供 者 の 知 識
改善するために，各ノードに位置情報を持たせる．そ
から，他の情報源にクエリを転送し，無駄な検索経路
して，クエリに含まれる検索対象者の住所から最も近
を 省 く 手 法 で あ る （ 図 13 参 照 ）． こ ち ら も 検 索 履 歴 が
い距離の隣接ノードリスト内のノードに検索する最短
ないと効率良く検索できない．
距 離 検 索 手 法 を 用 い た 改 良 型 P2P ネ ッ ト ワ ー ク を 提 案
ト ピ ッ ク 主 導 型 分 散 検 索 シ ス テ ム [15,16]と は ， 各 ノ
する．
ードが保有している検索対象となる各ファイルの諸属
各 登 録 ノ ー ド は , (1)ジ オ コ ー デ ィ ン グ [9,18] を 利 用
性を抽出したインデクスファイルを生成し，効果的な
して，設置した場所から算出された緯度経度を付加さ
インデクスファイルの絞込みを行う評価関数と分散イ
れ た 隣 接 ノ ー ド リ ス ト ， (2)検 索 履 歴 と , 入 力 さ れ た 間
ン デ ク ス 機 構 を 持 っ た PureP2P シ ス テ ム で あ る ． そ し
接位置情報（住所など）から位置情報を調べる手段と
て，これらを利用し，検索者の要求に応じた検索を行
し て ，(3)緯 度 経 度 変 換 シ ス テ ム を 持 つ ．ま た ，Gnutella
う．つまり，各ファイル情報を抽出し，インデクスフ
プロトコルを利用して実装した．災害時に，本システ
ァイル形成の仕方によって，このシステムがうまく検
ム は ， 自 治 体 で 決 め ら れ た 避 難 場 所 に PC を 設 置 し ，
索者の要求に答えられるかどうかが決定する．これに
そ の 上 で 利 用 す る こ と を 想 定 し て い る （ 図 4 参 照 ）．
対し，提案システムでは属性の抽出や複雑な評価関数
4.2. 登録データ
を用いないので運用コスト面では有利である．
ユ ー ザ は 【 名 前 】【 本 人 住 所 】【 年 齢 】【 性 別 】【 所 属
名 （ 会 社 ， 学 校 名 等 ）】【 所 属 住 所 】【 現 在 場 所 】【 現 在
4. 提 案 シ ス テ ム
状 況 】【 登 録 日 時 】 を 登 録 す る ． 当 た り 前 で は あ る が ，
4.1. 概 要
安否情報検索では，本人に該当する情報と本人の安否
負 荷 低 減 型 PureP2P ネ ッ ト ワ ー ク [19]で は ， 検 索 者
情 報（【 現 在 状 況 】な ど ）が 必 要 で あ る ．そ し て ，そ の
がコンピュータに検索対象者の人名や住所などを入力
情報がいつ登録されたかという情報によって情報の新
する．そして，各ノードが所持している検索履歴を用
鮮度も確認できるので【登録日時】も保存する．
表 1 検索履歴例
名前
本人住所
年齢
性別
所属名
所属住所
現在場所
現在状況
宮本浩二
八王子市南大沢
20
男
東京都立大学
八王子市南大沢
東京都立大学
無事
中田恒靖
府中市日鋼町
21
男
東京都立大学
八王子市南大沢
東京都立大学
川口正剛
八王子市石川町
19
男
東京都立大学
八王子市南大沢
東京都立大学
楢崎能活
府中市天神町
21
男
東京工科大学
八王子市片倉町
松田隆三
多摩市永山
22
男
東京都立大学
盛岡直樹
八王子市南大沢
23
男
秋田雅史
八王子市南大沢
20
中山豊
八王子市堀之内
18
登録ノード 登録ノードのIPアドレス
登録日時
獲得日時
2002/3/12/7:00
2002/3/12/9:00
144.***.***.***
2002/3/12/9:00
2002/3/12/10:00
133.***.***.***
2002/3/12/11:00
2002/3/12/12:00
C
155.***.***.***
2002/3/12/15:00
2002/3/12/16:00
重傷
D
122.***.***.***
2002/3/12/16:00
2002/3/12/18:00
東京都立大学
無事
B
133.***.***.***
2002/3/12/16:30
2002/3/12/18:30
八王子市東中野
中央大学
無事
A
144.***.***.***
2002/3/12/16:35
2002/3/12/18:35
八王子市堀之内
東京薬科大学
無事
C
155.***.***.***
2002/3/12/16:50
2002/3/12/18:50
B
133.***.***.***
軽傷
A
無事
B
東京工科大学
無事
八王子市南大沢
東京都立大学
東京都立大学
八王子市南大沢
男
中央大学
男
東京薬科大学
表 2 隣接ノードリスト例
登 録 ノード
登 録 ノードの IP アドレス
登 録 ノードの位 置 情 報 (北 緯 ，東 経 )
B
133.***.***.***
(35.35.23，139.23.7)
A
144.***.***.***
(35.38.4，139.24.39)
C
155.***.***.***
(35.37.52，139.23.54)
D
122.***.***.***
(35.37.55，139.20.27)
出す．ヒットがないなら③の処理へ．
4.3. 検 索 履 歴
③
検 索 履 歴 は【名 前 】【本 人 住 所 】【年 齢 】【性 別 】【所 属 名 】
【 本 人 住 所 】【 所 属 住 所 】の 位 置 情 報 と 隣 接 ノ
ー ド リ ス ト 内 の【 登 録 ノ ー ド の 位 置 情 報 】か ら 距
【所 属 住 所 】【現 在 場 所 】【現 在 状 況 】，安 否 情 報 を登 録 し
離 を 計 算 し ， 最 短 距 離 順 に そ れ ぞ れ i（ ブ ロ ー ド
た【登 録 ノード】 【登 録 ノードの IP アドレス】【登 録 日 時 】【獲
キ ャ ス ト す る 最 大 数 ）件 選 び ，最 後 に そ れ ら を ま
得 日 時 】とする．そして，最 新 情 報 を保 持 しているノードへ接
と め i 件 Query メ ッ セ ー ジ を 出 す ．
続 できなかった場 合 ，検 索 履 歴 の情 報 を検 索 者 に渡 す（表
1 参 照 ）．
4.4. 検 索 アルゴリズム
②は完全一致検索，③を最短距離検索とする．それ
ぞ れ 例 を 以 下 に 挙 げ て 説 明 す る ． 負 荷 低 減 型 PureP2P
【 検 索 項 目 】と し て【 名 前 】【 本 人 住 所 】【 所 属 】【 所
システムでは，③の最短距離検索の部分を隣接ノード
属住所】をユーザが入力し，その【本人住所】と【所
リストからクエリを出すノードをランダムに選択し検
属 住 所 】か ら 検 索 対 象 者 の【 位 置 情 報（ 緯 度 経 度 ）】を
索 を し て い た ． ま た ， 検 索 結 果 を Query メ ッ セ ー ジ が
割 り 出 し ，Query メ ッ セ ー ジ に 付 加 す る ．【 名 前 】と【 本
通ったノードの逆順で返し，中継したノードの検索履
人 住 所 】【 所 属 住 所 】の ど ち ら か は 必 須 で あ る が ，そ の
歴にヒットした内容を登録し，隣接ノードリストにノ
他は１つ以上入力すれば良い．
ー ド の 情 報 （【 登 録 ノ ー ド 】【 登 録 ノ ー ド の IP ア ド レ
次に，各ノードにおける検索処理の流れについて述
ス 】【 登 録 ノ ー ド の 位 置 情 報 】） を 登 録 す る ． つ ま り ，
べる．ただし，登録データと検索項目はすべて入力済
QueryHit が 返 さ れ た 伝 播 上 の 全 て の ノ ー ド の 履 歴 や ノ
み と し て 話 を 進 め る （ 図 5 参 照 ）．
ードリストが更新され，今後の検索に利用される．
①
Query メ ッ セ ー ジ の 【 名 前 】【 本 人 住 所 】【 所
属 名 】【 所 属 住 所 】 を 使 っ て ， 自 ノ ー ド の 登 録 デ
②
•
完全一致検索
完全一致検索では，検索履歴に検索対象者の情報が
ータに対して検索を行う．これにヒットすれば，
ある場合，直接その情報が登録されているノードに
QueryHit メ ッ セ ー ジ を 返 し ユ ー ザ に そ の 結 果 を
Query メ ッ セ ー ジ を 出 す こ と が で き る ． 表 1 の 検 索 履
表示する．
歴 を 検 索 項 目 の 【 名 前 】=“ 盛 岡 直 樹 ”，【 本 人 住 所 】 =
検 索 履 歴 と Query メ ッ セ ー ジ の【 名 前 】【 本 人
“ 八 王 子 市 南 大 沢 ”，
【 所 属 名 】=“ 東 京 都 立 大 学 ”，
【所
住 所 】【 所 属 名 】【 所 属 住 所 】の AND 検 索 を す る ．
属 住 所 】=“ 八 王 子 市 南 大 沢 ”で 検 索 す る と ノ ー ド B が
ヒ ッ ト す れ ば ，そ の ノ ー ド へ Query メ ッ セ ー ジ を
ヒ ッ ト し ， ノ ー ド B へ Query メ ッ セ ー ジ を 出 す ．
表 3
ノード
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
避難場所
佐方小学校
廿日市小学校
桂公園
七尾中学校
原小学校
宮内小学校
峰高公園
金剛寺小学校
地御前小学校
野坂中学校
宮園小学校
四季が丘小学校
四季が丘中学校
四季が丘公園
阿品台東小学校
阿品台西小学校
阿品台中学校
阿品公園
避難場所の情報
避難場所の住所
地域
佐方10番地１
佐方
本町２番13号
廿日市
桜尾本町
廿日市
平良二丁目２番34号
平良
原４３３番地
原
宮内１５１８番地
宮内
串戸六丁目
宮内
地御前二丁目22番１号 地御前
地御前四丁目３番１号 地御前
地御前北一丁目３番１号 地御前
宮園一丁目１番地２
宮園
四季が丘八丁目１番地１ 四季が丘
四季が丘二丁目１番地１ 四季が丘
四季が丘三丁目
四季が丘
阿品台東２番１号
阿品台
阿品台西１番１号
阿品台
阿品台東１番１号
阿品台
阿品台五丁目
阿品台
経度
132.20.10.88
132.20.19.47
132.20.39.19
132.19.36.38
132.18.23.31
132.18.39.22
132.19.28.39
132.19.18.58
132.19.13.39
132.18.26.02
132.17.30.40
132.17.36.10
132.17.44.41
132.17.36.10
132.18.28.12
132.18.43.59
132.18.42.51
132.18.31.35
緯度
34.21.24.99
34.20.57.57
34.21.15.49
34.21.04.59
34.21.58.48
34.20.55.30
34.20.04.01
34.20.04.01
34.20..24.61
34.21.06.11
34.20.40.88
34.20.43.29
34.20.56.38
34.19.43.29
34.19.19.91
34.19.19.91
34.19.50.10
34.19.40.07
を入力すると，緯度経度変換システムが“八王子
市 南 大 沢 3” か ら “ 35 度 36 分 8 秒 , 139 度 23 分
7 秒 ”, “ 八 王 子 市 南 大 沢 1”か ら“ 35 度 36 分 45
秒 , 139 度 22 分 56 秒 ” に 変 換 し ， 表 2 の 隣 接 ノ
ードリストから各ノードと本人住所，所属住所か
ら 距 離 を 算 出 し ， 距 離 が 短 い 順 に B，C，A，D と
クエリを出すノード候補が並び替えられ，そして
i=2 だ と す る と B， C へ ク エ リ を 出 す ．
5. 実 験
5.1. 実 験 概 要
提 案 手 法 に よ り 負 荷 低 減 型 PureP2P と 比 較 し て ，
図6
シミュレーションノード
Query メ ッ セ ー ジ の 中 継 回 数 （ ホ ッ プ 数 ） が 減 少 す る
かどうかを検証するためにシミュレーションを行った．
2001 年 3 月 に 起 き た 芸 予 地 震 被 害 地 域 の 一 都 市 ，
はつかいち
•
最短距離検索
【 本 人 住 所 】【 所 属 住 所 】の 位 置 情 報 と 隣 接 ノ ー
ドリスト内の【登録ノード位置情報】からそれぞ
廿 日 市 市 [10]を モ デ ル と し て ネ ッ ト ワ ー ク ト ポ ロ ジ ー
を決定し，発見までのホップ数で評価した．前提条件
を以下のように定めた．
れの住所から登録ノードまでの距離を計算し，距
まず，住所（本人住所，所属住所，避難場所住所）
離順に登録ノードを並び替える．それぞれクエリ
から地域を設定した．例えば，四季が丘 1 丁目，2 丁
総数 i 件だけ選び，それらをまとめクエリを出す
目 ， 3 丁 目 → 四 季 が 丘 と し た （ 表 3 参 照 ）．
ノ ー ド を 決 め る ．例 と し て ，【 名 前 】=“ 小 野 英 俊 ”，
【 本 人 住 所 】=“ 八 王 子 市 南 大 沢 3”，【 所 属 】=“ 東
京 都 立 大 学 ”，【 所 属 住 所 】 =“ 八 王 子 市 南 大 沢 1”
3.5
3
3
完全一致検索+ノードリスト方式
ノードリスト方式
負荷低減型PureP2P方式
2.5
完全一致検索＋ノードリスト方式
2.5
提案方式
負荷低減型PureP2P
提案方式
ッ
ホ 2
2
ッ
ホ
プ
数 1.5
プ
数
1.5
1
1
0.5
0.5
0
1
2
3
4
5
6
7
8
図7
9 10 11 12
検索回数/3000回
13
14
15
16
17
18
0
19
完全一致検索+
ノードリスト方式
図 8
実験結果 1
また，芸予地震における情報通信システムの実態調査
[16]の 芸 予 地 震 時 の 居 場 所 の ア ン ケ ー ト 結 果 か ら ， 地
負荷低減型
PureP2P方式
•
提案方式
検索方式
実験結果 2
負 荷 低 減 型 PureP2P 方 式
完全一致検索と入力したキーワードを使い，検
震 時 に 自 宅 や 自 宅 付 近 に 居 た 人 が 約 50%， 職 場 や 職 場
索 履 歴 を OR 検 索 で ヒ ッ ト し た ノ ー ド の 中 か ら ヒ
付 近 に 居 た 人 が 約 20%， そ れ 以 外 の 場 所 や 無 回 答 な ど
ット件数が上位の順にクエリを出す手法とノード
が 約 30％ で あ っ た た め ， 各 ノ ー ド の 登 録 デ ー タ （ 500
リスト方式を組み合わせた方式である．
人分）の 5 割は【本人住所地域】と【避難場所地域】
を一致させ，2 割は【所属住所地域】と【避難場所地
横軸を検索回数，縦軸をホップ数とする．1 人の被
域】が一致し，残りは【本人住所地域】や【所属住所
検索者を検索し発見した場合を検索回数 1 とする（た
地域】が【避難場所地域】と一致しないように登録し
だし，検索者が検索している避難場所（ノード）に被
た ．よ っ て ，全 デ ー タ 数 は 9000 人（ 500 人 ×18 ノ ー ド ）
検 索 者 が い た 時 の 発 見 し た 場 合 を 除 く ）．今 回 の 実 験 で
である．
は，検索対象者を発見した時のホップ数について検証
Gnutella の 初 期 設 定 を 参 考 に し て ， 各 避 難 場 所 は 隣
することを目的としたため，発見されなかった場合の
接ノードを 4 つ持ち，ブロードキャストする最大数を
検 索 回 数 は 含 め な か っ た ．そ し て ，検 索 回 数 3000 回 ご
2 とする．検索対象者，検索開始ノードは無作為に決
とのホップ数の平均をプロットすると図 7 のような結
定 し ， TTL は 7 に 設 定 し て ，【 名 前 】【 本 人 住 所 】【 所
果が得られた．提案システムは，既存方式に比べ，ホ
属 名 】【 所 属 住 所 】と【 本 人 住 所 の 位 置 情 報（ 緯 度 経 度 ）】，
ップ数が小さく，ホップ数が徐々に小さくなっていく
【 所 属 住 所 の 位 置 情 報（ 緯 度 経 度 ）】を 使 っ て 検 索 を 行
ことがわかる．
った．
5.2. 実 験 結 果
提 案 シ ス テ ム だ け で な く ，以 下 の 3 つ も 同 様 な 条 件
で検索を行い，提案システムの評価を行った．その結
果 は 図 7,8 に 示 す ．
ま た ，図 8 で は ，【 完 全 一 致 検 索 +ノ ー ド リ ス ト 方 式 】
と 【 負 荷 低 減 型 PureP2P 方 式 】 と 【 提 案 方 式 】 に つ い
て 3000 回 ま で の ホ ッ プ 数 の 平 均 を 表 し た も の で あ る ．
縦軸，横軸は図 7 と同様である．これらにより，最短
距離検索手法を用いた提案システムは，負荷低減型
PureP2P シ ス テ ム よ り ， 検 索 履 歴 が 蓄 積 す る ま で の あ
•
ノードリスト方式
る一定期間のホップ数を減少させることが期待できる．
検 索 履 歴 を 用 い ず ，Gnutella 方 式 と 同 じ く ，隣 接
ノードリストからランダムに，検索するノードを
選ぶ方式である．
•
完全一致検索＋ノードリスト方式
提案システムの完全一致検索とノードリスト方
6. ま と め
本論文では，検索履歴と登録ノードと検索対象者の
位置情報を用いた最短距離検索を利用した，改良型
P2P ネ ッ ト ワ ー ク に つ い て 提 案 し ， 安 否 情 報 検 索 へ 応
式 を 組 み 合 わ せ た 方 式 で あ り ， FreeNet と 同 様 な 働
用 し た ．ま た ，負 荷 低 減 型 PureP2P シ ス テ ム や Gnutella
きをする．
や FreeNet な ど の 既 存 シ ス テ ム と の 比 較 実 験 を 行 っ た ．
そ の 結 果 ， 提 案 手 法 に よ り ， 負 荷 低 減 型 PureP2P シ ス
テムに比べ，検索履歴が十分蓄積されていない状態に
おいても，ネットワーク負荷を軽減させることがわか
った．今後の課題として，以下のことが挙げられる．
•
今 回 の 実 験 で は ，ヒ ッ ト し た ク エ リ の ホ ッ プ
数で評価したが，ヒットしなかったクエリのホ
ップ数も加え，全クエリのネットワークトラフ
ィックで評価をする．また，蓄積する検索履歴
の制約やネットワークトポロジーの変化などを
考慮に入れた，より現実的な利用に即したシミ
ュレーションを行う．
•
負 荷 低 減 型 PureP2P シ ス テ ム で 用 い た カ テ ゴ
リ検索手法と最短距離検索手法を組み合わせた，
よりネットワーク負荷が軽減させる手法につい
て検討する．
•
ユーザが複数のノードで登録した場合の過
去の登録データの削除について考慮する必要が
ある．例えば，検索履歴に追加するときに同じ
デ ー タ が 存 在 し た 場 合 （ 名 前 ， 住 所 等 ）， 登 録 日
時から判断し新しいデータなら保存し，古いデ
ータなら登録ノードのそのデータを削除する命
令を出すことによって改善する．
•
PureP2P シ ス テ ム で は ， 最 初 の エ ン ト リ ー ポ
イントをどう決めるか，安全性の確保（特に安
否情報を扱う場合）をどう求めていくかという
問 題 が あ る ． こ れ ら は Jxta サ ー チ [8] の よ う な
HybridP2P シ ス テ ム と PureP2P シ ス テ ム の 中 間 に
位置するシステムへの移行によってエントリー
ポ イ ン ト を HybridP2P シ ス テ ム の 中 央 サ ー バ の
ようなもの設置し，エントリーのみの機能を与
えることによって改善することができる．
•
検索者が正確で詳細な住所を入力しなかっ
た場合に，直接位置情報をどう与えるかを検証
する必要がある．また，検索者が検索対象者を
発見した場合，その人と会うために，検索対象
者が発見された検索者の場所から避難場所ノー
ドまでの地図を出すことで，より安否情報検索
システムの付加価値を高めることも考えている．
文
献
[1] IAAProject, http://www.iaa.wide.ad.jp.
[2] Japan.internet.com, http://japan.internet.com.
[3] Jnutella.org, http://www.jnutella.org.
[4] Napster, http://napster.com.
[5] Gnutella, http://www.gnutella.com.
[6] FreeNet.org, http://freenetproject.org.
[7] NeuroGrid, http://www.neurogrid.net.
[8] JxtaProject, http://www.jxta.org.
[9] Mobile Info Search, www.kokono.net
[10] 廿 日 市 市 公 式 ペ ー ジ ，
http://www.hiroshima-cdas.or.jp/hatsukaichi/index.html.
[11] 静 岡 県 立 大 学 災 害 情 報 シ ス テ ム ，
http://anpi.u-shizuoka-ken.ac.jp/
[12] 伊 藤 直 樹 , ”P2P コ ン ピ ュ ー テ ィ ン グ ~技 術 解 説 と
ア プ リ ケ ー シ ョ ン ,” ソ フ ト リ サ ー チ セ ン タ ー,
November, 2001.
[13] Sam Joseph, “NeuroGrid: Semantically Routing
Queries in Peer-to-Peer Networks,” International
Workshop on Peer-to-Peer Computing, Pisa, Italy,
May, 2002
[14] 澤 田 雅 人 , 富 田 準 二 , 池 田 哲 夫 , 佐 藤 哲 司 , “分 散
型 検 索 シ ス テ ム に お け る 連 携 型 検 索 手 法 の 提 案 ,”
DEWS2002, 倉 敷 , Japan, Mar, 2002.
[15] 中 辻 真 , 川 原 稔 , 河 野 浩 之 ,“ ピ ア ツ ー ピ ア ネ ッ ト
ワーク上 のトピック主導型検索システムとイン
デ ク ス 技 術 ,” DBWeb200 論 文 集 , pp.217-224, 京
都 , Dec, 2001．
[16] 河 野 浩 之 , 中 辻 真 , 川 原 稔 , “ ネ ッ ト ワ ー ク ト ポ ロ
ジー変化を考慮したトピック主導型検索システ
ム , ” 信 学 技 報 , Vol.102, No.375, pp.13-18, Oct,
2002．
[17] 小 林 真 也 , 桶 上 喜 信 , 高 松 雄 三 , “ 芸 予 地 震 に お け
る 情 報 通 信 シ ス テ ム の 実 態 調 査 ,” 情 報 処 理 学 会
第 64 回 全 国 大 会 , pp.319-320, Mar, 2002.
[18] 有 川 正 俊 , 相 良 毅 , “ ジ オ コ ー デ ィ ン グ 手 法 を 用
い た 多 様 な 文 書 資 源 の 空 間 情 報 化 , ”IT の 深 化 の
基 盤 を 拓 く 情 報 学 研 究 − 研 究 成 果 報 告 書 − A02 コ
ン テ ン ツ の 生 産・活 用 に 関 す る 研 究 , pp.74-81, Mar,
2002.
[19] 中 山 淳 也 , 太 田 学 , 片 山 薫 , 石 川 博 , “ 負 荷 低 減 型
PureP2P ネ ッ ト ワ ー ク の 提 案 − 安 否 情 報 検 索 へ の
応 用 − , ” 日 本 デ ー タ ベ ー ス 学 会 , DBSJLetters
Vol.1,No.1, pp.51-54, Oct, 2002.
[20] 宮 沢 小 百 合 , 中 山 淳 也 , 太 田 学 , 片 山 薫 , 石 川 博 ,
“ 災 害 時 を 想 定 し た ハ イ ブ リ ッ ド 型 P2P ネ ッ ト ワ
ー ク の 提 案 , ” 情 報 処 理 学 会 第 64 回 全 国 大 会 ,
pp.329-330, Mar, 2002.
[21] 井 澤 志 充 , 木 本 雅 彦 , 多 田 信 彦 , 大 野 浩 之 , 篠 田
陽 一 , “IAA シ ス テ ム の 現 状 と そ の 課 題 ,” IC2000,
横 浜 , Japan, Nov, 2000.
http://www.csl.sony.co.jp/ic2000/papers/S01_03.pdf.
謝
辞
本研究の一部は，文部科学省科学研究費特定領域研
究 (2)[情 報 学 :A02](課 題 番 号 :14019075)， 東 京 都 立 大 学
総 長 特 別 研 究 費 (特 別 重 点 研 究 )に よ る ．
[22] 湯 瀬 裕 昭 , 五 十 川 直 也 , 岩 崎 剛 久 , 原 田 雅 樹 , “イ
ンターネットによる学生の安否情報確認システ
ム ,” IC2000, 横 浜 , Japan, Nov, 2000.
http://www.csl.sony.co.jp/ic2000/papers/DEMO03.pdf.