(57)【要約】【課題】モバイル環境のP2Pネットワークにおいて、端末移動に伴うネットワークの再構築を必要最小限に抑える。【解決手段】情報交換部１０１は隣接端末との間でネットワーク情報を交換する。ネットワーク構築部１０２は、ネットワーク情報に基づいてネットワークを構築する。P2P通信部１０３は、ネットワークトポロジに基づいてP2Pパケットを送受信する。測位部１０４は移動端末の現在位置P0を測位する。再構築判定部１０５は、現在のネットワークトポロジに基づいて、自端末が移動してもネットワークの再構築が必要とならないトポロジ維持範囲を設定する範囲設定部１０５ａと、現在位置P0がトポロジ維持範囲内であるか否かを判定する位置判定部１０５ｂと、現在位置P0がトポロジ維持範囲外であれば、現在位置Ptに基づいて更新された位置IDをネットワーク上に広報してネットワークの再構築を要求する再構築要求部１０５ｃとを含む。【選択図】図１
2011071857.tif 000002
【特許請求の範囲】
【請求項１】
各移動端末にその現在位置を代表する位置IDが割り当てられ、各移動端末が隣接端末と位置IDを交換してネットワークを自律分散的に構築するピア・ツー・ピアネットワークの管理方法において、
各移動端末が、
現在のネットワークトポロジに基づいて、移動してもネットワークトポロジが変化しないトポロジ維持範囲を設定する手順と、
現在位置を測位する手順と、
現在位置が前記トポロジ維持範囲内であるか否かを判定する手順と、
現在位置が前記トポロジ維持範囲内でないと判定されると、現在位置を代表する位置IDをネットワーク上へ広報する手順とを含み、
前記位置IDを受信した移動端末では、当該位置IDに基づいてネットワークトポロジを再構築することを特徴とするピア・ツー・ピアネットワークの管理方法。
【請求項２】
前記ネットワークが、空間的に分散された多数の移動端末の位置をZNetにより一次元化することにより構築され、
前記トポロジ維持範囲は、移動端末ごとに、その両端に位置する一対の隣接端末間に設定されることを特徴とする請求項１に記載のピア・ツー・ピアネットワークの管理方法。
【請求項３】
前記ネットワークが、空間的に分散された多数の移動端末がドロネー図の接続関係を満足するドロネーネットワークとして構築され、
前記トポロジ維持範囲は、移動端末ごとに、その隣接端末を仮想的に結んで得られる多角形の範囲内に設定されることを特徴とする請求項１に記載のピア・ツー・ピアネットワークの管理方法。
【請求項４】
各移動端末にその現在位置を代表する位置IDが割り当てられ、各移動端末が隣接端末と位置IDを交換してネットワークトポロジを自律分散的に構築するピア・ツー・ピアネットワークの移動端末において、
現在のネットワークトポロジに基づいて、移動してもネットワークトポロジが変化しないトポロジ維持範囲を設定する手段と、
現在位置を測位する手段と、
現在位置が前記トポロジ維持範囲内であるか否かを判定する手段と、
現在位置が前記トポロジ維持範囲内でないと判定されると、現在位置を代表する位置IDをネットワーク上へ広報する手段と、
他の移動端末から広報された位置IDを受信してネットワークトポロジを再構築する手段とを具備したことを特徴とするピア・ツー・ピアネットワークの移動端末。
【請求項５】
前記ネットワークが、空間的に分散された多数の移動端末の位置をZNetにより一次元化することにより構築され、
前記トポロジ維持範囲は、移動端末ごとに、その両端に位置する一対の隣接端末間に設定されることを特徴とする請求項１に記載のピア・ツー・ピアネットワークの移動端末。
【請求項６】
前記ネットワークが、空間的に分散された多数の移動端末がドロネー図の接続関係を満足するドロネーネットワークとして構築され、
前記トポロジ維持範囲は、移動端末ごとに、その隣接端末を仮想的に結んで得られる多角形の範囲内に設定されることを特徴とする請求項１に記載のピア・ツー・ピアネットワークの移動端末。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ピア・ツー・ピアネットワークの管理方法および移動端末に係り、特に、各移動端末が自律分散的にネットワークを構築するピア・ツー・ピアネットワークに好適なネットワーク管理方法および移動端末に関する。
【背景技術】
【０００２】
ピア・ツー・ピア(P2P)通信の普及に伴い、従来の固定端末をピアノードとするP2Pに加えて、PDAや携帯端末などの移動端末をピアノードとするモバイル環境のP2Pネットワークが注目されている。
【０００３】
非特許文献１には、モバイル環境の普及を背景に、天気や気候などの状況情報を利用した状況依存型サービスの開発の一環として、移動端末の位置情報を考慮したP2Pネットワークにおいて位置に依存する情報を効率良く検索する技術が開示されている。
【０００４】
非特許文献２には、P2Pネットワークのトポロジとしてドロネー図を導入する試みが開示されている。ドロネー図とは、一定の条件を満足する平面を、この平面上に与えられた点（母点）を用いて多数の三角形に分割した図であり、非特許文献２では、ドロネー図の母点をピアノード、辺を通信路とみなし、グラフがドロネー図の接続関係を満たすネットワークをP2Pドロネーネットワークと定義している。
【０００５】
なお、ドロネー図の作成にあたっては全ての母点の位置情報が既知である必要があるため、非特許文献２では、各ノードが自律的に他のノードから情報を取得して自ノードの周囲をドロネー三角形に分割することで局所的なP2Pドロネーネットワークを構成し、さらに各ノードが相互にノード情報を交換することで各局所ネットワークを融合し、全体のドロネーネットワークを認識するようにしている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】「モバイル環境における端末の位置情報に基づくP2Pネットワークの提案と評価」，電子情報通信学会第15回データ工学ワークショップ(DEWS2004)論文集，Web掲載, 1-A-01
【非特許文献２】「ノード位置を用いたP2Pモデルのためのドロネー図の自律分散生成アルゴリズム」，情報処理学会論文誌，Vol. 47 No.SIG 4 (TOD 29)
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１に開示されたモバイル環境のP2Pネットワークでは、各移動端末においてネットワークトポロジを自律分散的に管理するために、各端末の識別子がその現在位置を代表する位置IDとされるため、端末が移動して位置IDが変化すると、これを周囲の移動端末へ広報してネットワークを再構築させる必要がある。したがって、端末が頻繁に移動する環境下ではネットワークの再構築が頻発し、ネットワークおよび各端末の処理負荷が増大してしまう。
【０００８】
本発明の目的は、上記した従来技術の課題を解決し、モバイル環境のP2Pネットワークにおいて、端末移動に伴うネットワークの再構築を必要最小限に抑えられるピア・ツー・ピアネットワークの管理方法および移動端末を提供することにある。
【課題を解決するための手段】
【０００９】
上記の目的を達成するために、本発明は、各移動端末にその現在位置を代表する位置IDが割り当てられ、各移動端末が隣接端末と位置IDを交換してネットワークトポロジを自律分散的に構築するピア・ツー・ピアネットワークの管理方法において、各移動端末が以下のような手段（または手順）を含むことを特徴とする。
【００１０】
(1)現在のネットワークトポロジに基づいて、移動してもネットワークトポロジが変化しないトポロジ維持範囲を設定する手段と、現在位置を測位する手段と、現在位置が前記トポロジ維持範囲内であるか否かを判定する手段と、現在位置が前記トポロジ維持範囲内でないと判定されると、現在位置を代表する位置IDをネットワーク上へ広報する手段と、他の移動端末から広報された位置IDを受信してネットワークトポロジを再構築する手段とを具備した。
【００１１】
(2)前記ネットワークが、空間的に分散された多数の移動端末の位置をZNetにより一次元化することにより構築され、トポロジ維持範囲は、移動端末ごとに、その両端に位置する一対の隣接端末間に設定されることを特徴とする。
【００１２】
(3)前記ネットワークが、空間的に分散された多数の移動端末がドロネー図の接続関係を満足するドロネーネットワークとして構築され、トポロジ維持範囲は、移動端末ごとに、その隣接端末を仮想的に結んで得られる多角形の範囲内に設定されることを特徴とする。
【発明の効果】
【００１３】
本発明によれば、以下のような効果が達成される。
【００１４】
(1)移動端末が移動しても、現在のネットワークトポロジを維持できるトポロジ維持範囲内での移動であれば、その移動量にかかわらずネットワークトポロジが再構築されないので、端末移動に伴うネットワークの再構築を必要最小限に抑えられる。
【００１５】
(2)ネットワークが、空間的に分散された多数の移動端末の位置をZNetにより一次元化することにより構築されているときは、各移動端末のトポロジ維持範囲を、その両端に位置する一対の隣接端末間に設定すれば良いので、トポロジ維持範囲を簡単に設定できるようになる。
【００１６】
(3)ネットワークがドロネーネットワークとして構築されているときは、各移動端末のトポロジ維持範囲を、その隣接端末を仮想的に結んで得られる多角形の範囲内に設定すれば良いので、トポロジ維持範囲を簡単に設定できるようになる。
【図面の簡単な説明】
【００１７】
【図１】本発明に係る移動端末の主要部の構成を示した機能ブロック図である。
【図２】本発明に係る移動端末の動作を示したフローチャートである。
【図３】ZNetによるネットワークの構築方法およびトポロジ維持範囲の設定方法の一例を模式的に表現した図である。
【図４】z-orderingによる位置情報の一次元化手法を示した図である。
【図５】移動端末がトポロジ維持範囲内で移動した場合のトポロジを模式的に表現した図である。
【図６】移動端末がトポロジ維持範囲外へ移動した場合のトポロジを模式的に表現した図（その１）である。
【図７】移動端末がトポロジ維持範囲外へ移動した場合のトポロジを模式的に表現した図（その２）である。
【図８】ドロネーネットワークの構築方法およびトポロジ維持範囲の設定方法を模式的に表現した図である。
【図９】ドロネーネットワーク上で移動端末がトポロジ維持範囲内で移動した場合の様子を模式的に表現した図である。
【図１０】ドロネーネットワーク上で移動端末がトポロジ維持範囲内で移動した場合のネットワークトポロジを模式的に表現した図である。
【図１１】ドロネーネットワーク上で移動端末がトポロジ維持範囲外まで移動した場合の様子を模式的に表現した図である。
【図１２】ドロネーネットワーク上で移動端末がトポロジ維持範囲外まで移動した場合のネットワークトポロジを模式的に表現した図である。
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施の形態について詳細に説明する。本発明では、P2Pネットワークに参加している移動端末が移動した場合でも、端末間の隣接関係が崩れなければネットワークトポロジが変化しないことに着目し、移動端末が移動した場合でも端末間の隣接関係が崩れなければネットワークの再構築が行われないようにしている。
【実施例１】
【００１９】
図１は、本発明に係る移動端末Nの主要部の構成を示した機能ブロック図であり、ここでは本発明の説明に不要な構成は図示が省略されている。
【００２０】
情報交換部１０１は、隣接端末との間で現在位置や局所的なネットワーク情報等（以下、単にネットワーク情報と表現する場合もある）を交換する。ネットワーク構築部１０２は、前記隣接端末と交換したネットワーク情報や自端末の位置情報に基づいてP2Pネットワークを自律分散的に構築し、そのトポロジを解釈する。P2P通信部１０３は、前記ネットワークトポロジに基づいて隣接端末との間でP2Pパケットを送受信する。測位部１０４は、例えば少なくとも３つのGPS衛星から送信されるGPS信号を受信して現在位置P0を繰り返し測位する。
【００２１】
再構築判定部１０５において、範囲設定部１０５ａは、現在のネットワークトポロジに基づいて、自端末が移動しても端末間の隣接関係が崩れずにネットワークトポロジが維持され、したがってネットワークの再構築が必要とならない移動範囲（以下、トポロジ維持範囲Apと表現する）を設定する。位置判定部１０５ｂは、現在位置P0が前記トポロジ維持範囲Ap内であるか否かを判定する。再構築要求部１０５ｃは、現在位置P0がトポロジ維持範囲Apの外側であれば自身の位置IDを現在位置P0に基づいて更新し、これをP2Pネットワーク上へ広報して他の移動端末にネットワークの再構築を要求する。
【００２２】
図２は、前記移動端末の動作を示したフローチャートであり、ここでは、移動端末がP2Pネットワークに既に参加しており、前記トポロジ維持範囲Apが設定済みの状態から説明を始める。また、本実施形態では各移動端末がP2Pネットワークを自律分散的に構築するので、同様の手順が全ての移動端末で実行される。
【００２３】
ステップＳ１では、時刻tにおいて測位部１０４により自端末N0の現在位置Ptが測位される。ステップＳ２では、現在位置Ptが前記トポロジ維持範囲Apの内側であるか否かが、前記位置判定部１０５ｂにより判定される。現在位置Ptがトポロジ維持範囲内であればステップＳ１へ戻り、上記の各処理が繰り返される。これに対して、現在位置Ptが前記トポロジ維持範囲Apの外側と判定されればステップＳ３へ進み、隣接端末Nxに対してleave（離脱）要求が送信されてP2Pネットワークから一旦離脱する。
【００２４】
ステップＳ４では、自端末の位置IDが現在位置Ptに基づいて更新される。ステップＳ５では、P2Pネットワークに参加している端末の一つにjoin（接続）要求が送信されてP2Pネットワークに改めて参加する。ステップＳ６では、現在位置Ptに基づいて更新された位置IDを含む各種のネットワーク情報が隣接端末Nxとの間で交換される。
【００２５】
ステップＳ７では、隣接端末Nxから取得したネットワーク情報および自身の現在位置Pt等に基づいて、前記ネットワーク構築部１０２によりP2Pネットワークが再構築される。このとき、隣接端末でも同様にP2Pネットワークが再構築される。ステップＳ８では、前記範囲設定部１０５ａにより、再構築されたP2Pネットワークのトポロジに基づいて、前記範囲設定部１０５ａによりトポロジ維持範囲Apが更新される。
【実施例２】
【００２６】
図３は、本発明に係るP2Pネットワーク管理方法におけるネットワークの構築方法およびトポロジ維持範囲Apの設定方法の一例を模式的に表現した図である。本実施形態では、空間的に分散された多数の移動端末Nxの位置をZNetにより一次元化することで前記トポロジ維持範囲Apを規定するようにしている。
【００２７】
ZNetとは、空間的に分散された位置情報を、空間充填法の一つであるz-orderingを用いて一次元化すると共に位置IDを与え、スキップグラフによりP2Pネットワークを構築する手法である。z-orderingは、図４に一例を示したように、x-y座標上の各位置をz状にスキャンして各位置に位置IDを与える手法であり、座標（５，７）には位置IDとして「５５」が付与され、その逆に、位置IDの「３７」は座標（４，３）が与えられる。
【００２８】
前記ZNetを用いたP2Pネットワークの構築方法については、論文「Y. Shu, B. C. Ooi, K.-L. Tan, and A. Zhou, "Supporting multi-dimensional range queries in peer-to-peer systems," in P2P ’05: Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing (P2P’05), (Washington, DC, USA), pp. 173.180, IEEE Computer Society, 2005.」に記載の内容を援用する。
【００２９】
このようなネットワーク構成において、図３の中央部に位置している端末N0に注目すると、この注目端末N0が移動した場合でも、図５に示したように、その移動先が隣接端末N3，N4を超えない範囲内であれば、移動端末N0と各隣接端末N3，N4との距離は変化するものの隣接関係は維持されるのでネットワークトポロジは実質的に変化しない。したがって、本実施形態では、一次元上で前記一対の隣接端末N3，N4で挟まれた範囲が、前記範囲設定部１０５ａによりトポロジ維持範囲Apに設定される。
【００３０】
そして、図６，７に示したように、注目端末N0が隣接端末N3，N4を越えてトポロジ維持範囲Apの外側まで移動し、これが前記測位部１０４により検知されて前記位置判定部１０５ｂによりトポロジ維持範囲外と判定されると、位置IDが現在位置Ptに基づいて更新される。前記再構築要求部１０５ｃは、更新された位置IDを広報してネットワークの再構築を他の移動端末へ要求すると共に、自端末のネットワーク構築部１０２に対してもネットワークの再構築を要求する。
【実施例３】
【００３１】
図８は、本発明に係るP2Pネットワーク管理方法におけるネットワークの構築方法およびトポロジ維持範囲Apの設定方法の他の一例を模式的に表現した図である。本実施形態では、P2Pネットワークのトポロジとしてドロネー図が採用され、そのグラフがドロネー図の接続関係を満足している。
【００３２】
このようなネットワーク構成において、図の中央部に位置している端末N0が移動した場合でも、図９に示したように、その移動先が６つの隣接端末N1〜N6を結んで得られる仮想的な六角形で囲まれた範囲内であれば、図１０に示したように、移動端末N0と各隣接端末N1〜N6との距離は変化するものの隣接関係は維持されるのでネットワークトポロジは実質的に変化しない。したがって、本実施形態では複数の隣接端末を結んで得られる仮想的な多角形で囲まれた範囲が、前記範囲設定部１０５ａによりトポロジ維持範囲Apに設定される。
【００３３】
そして、本実施形態では図１１に示したように、端末M0がトポロジ維持範囲Apの外側まで移動し、これが前記測位部１０４により検知されて前記位置判定部１０５ｂによりトポロジ維持範囲外と判定されると、位置IDが現在位置Ptに基づいて更新される。前記再構築要求部１０５ｃは、更新された位置IDを広報してネットワークの再構築を他の移動端末へ要求すると共に、自端末のネットワーク構築部１０２に対してもネットワークの再構築を要求する。図１２は、再構築されたP2Pネットワークの一例を示している。
【符号の説明】
【００３４】
１０１…情報交換部，１０２…ネットワーク構築部，１０３…P2P通信部，１０４…測位部，１０５…再構築判定部，１０５ａ…範囲設定部，１０５ｂ…位置判定部，１０５ｃ…再構築要求部
【図１】
2011071857.tif 000003
【図２】
2011071857.tif 000004
【図３】
2011071857.tif 000005
【図４】
2011071857.tif 000006
【図５】
2011071857.tif 000007
【図６】
2011071857.tif 000008
【図７】
2011071857.tif 000009
【図８】
2011071857.tif 000010
【図９】
2011071857.tif 000011
【図１０】
2011071857.tif 000012
【図１１】
2011071857.tif 000013
【図１２】
2011071857.tif 000014