(57)【要約】【課題】従来のものと比較して、伝送遅延および消費電力を低減することができる位置情報分散管理システムを提供すること。【解決手段】サービスの対象エリアに１次元的に割り当てられたセル毎にサーバを配置し、各サーバには、一方向に０から１ずつ加算された識別情報が割り当てられ、各サーバは、ルーティングテーブルを有し、このルーティングテーブルは、該当サーバに近いサーバから遠いサーバまでが段階的にグループ化され、各グループのなかで該当サーバに最も近いサーバのＩＤからなる。【選択図】図２
2012080391.tif 000002
【特許請求の範囲】
【請求項１】
サービスの対象エリアに１次元的に割り当てられたセル毎にサーバを設置し、
前記各サーバには、一方向にそれぞれ０から１ずつ加算された識別情報が割り当てられ、
前記各サーバは、
ルーティングテーブルを格納するルーティングテーブル格納部と、
前記ルーティングテーブルを構成する識別情報のなかで前記伝送データの伝送先に最も近いサーバの識別情報を抽出するサーバ抽出部と、
前記サーバ抽出部によって抽出された識別情報が割り当てられたサーバに前記伝送データを伝送する伝送部と、を有する位置情報分散管理システムにおいて、
前記ルーティングテーブルは、該当サーバに近いサーバから遠いサーバまでが段階的にグループ化され、各グループのなかで該当サーバに最も近いサーバの識別情報からなることを特徴とする位置情報分散管理システム。
【請求項２】
前記ルーティングテーブルは、前記識別情報がｍビットで表される場合に、該当サーバの識別情報と上位ｍ−１ビットのみが等しい識別情報が割り当てられたサーバが該当サーバに最も近いサーバのグループに属し、該当サーバの識別情報と上位１ビットが異なる識別情報が割り当てられたサーバが該当サーバに最も遠いサーバのグループに属するように設定されていることを特徴とする請求項１に記載の位置情報分散管理システム。
【請求項３】
前記各サーバは、設置されたセルに関するセル情報を格納するセル情報格納部を有し、
前記伝送部は、前記伝送データが該当セルに関する情報の要求を表す場合には、前記セル情報格納部に格納されたセル情報のなかで要求されたセル情報を表すデータを前記伝送データとして前記サーバ抽出部によって抽出された識別情報が割り当てられたサーバに伝送することを特徴とする請求項１または請求項２に記載の位置情報分散管理システム。
【請求項４】
前記伝送部は、前記セル情報を表す伝送データを受信したときに、前記セル情報を表すデータを要求した端末が該当セル内にある場合には、前記伝送データを前記端末に伝送することを特徴とする請求項３に記載の位置情報分散管理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サービスの対象エリアに１次元的に割り当てられたセル毎にサーバを配置し、各サーバが各セルに関する情報を管理する位置情報分散管理システムに関する。
【背景技術】
【０００２】
従来、携帯端末や車載器等の端末が取得した情報の管理は、中央サーバを利用したクライアント−サーバ型が主流である。今後、端末が取得したあらゆる場所における情報の利用要求は、増大することが予想される。この増大する要求に対応するためには、情報を分散して管理し、検索や共有が可能なシステムが要求される。
【０００３】
このようなシステムにおいては、各サーバにルーティングテーブルを格納しておき、特定のサーバ間で情報を転送する場合には、各サーバがルーティングテーブルに基づいて情報をルーティングする。
【０００４】
したがって、端末から特定位置の情報が要求された場合には、端末が位置するセルに設置されたサーバから特定位置を含むセルに設置されたサーバまでの伝送ルートを探索する必要がある。
【０００５】
このような伝送ルートを探索するときに用いられる探索アルゴリズムとして、分散ハッシュテーブル（Distributed Hash Table：ＤＨＴ）を用いたものが知られている。このＤＨＴを用いた探索アルゴリズムの代表的なものとして「Chord」と呼ばれるものが知られている（例えば、非特許文献１参照）。
【０００６】
Chordでは、本明細書におけるサーバに該当する各ノードに対して、０から１ずつ加算された識別情報（ＩＤ）が割り当てられる。ここで、ノード数を２ｍとし、ｎを０から（ｍ−１）までの自然数とすると、各ノードは、自己のＩＤに２ｎを加算したＩＤからなるルーティングテーブルを有し、目的のノードのＩＤに最も近いＩＤを有するノードにルーティングする。なお、Chordでは、自己のＩＤに２ｎを加算したＩＤが２ｍを超える場合には、当該ＩＤから２ｍが減じられる。
【０００７】
例えば、ｍ＝４とすると、ＩＤが０のノードは、［１，２，４，８］のルーティングテーブルを有する。具体的には、ＩＤが０のノードからＩＤが６のノードまでのルートを探索する場合には、ＩＤが０のノードのルーティングテーブルのなかで最も６に近い４が選択される。ＩＤが４のノードは、［５，６，８，１２］のルーティングテーブルを有するため、［０，４，６］といったルートが探索される。
【０００８】
また、ＤＨＴを用いた探索アルゴリズムの代表的なものとして「Kademlia」というものも知られている（例えば、非特許文献２参照）。
【０００９】
Kademliaでは、本明細書におけるサーバに該当する各ノードに対して、０から１ずつ加算されたＩＤが割り当てられる。ここで、ノード数を２ｍとすると、各ノードに割り当てられるＩＤは、ｍビットで表すことができる。
【００１０】
各ノードは、自己のＩＤの各ビットをそれぞれ反転させたＩＤからなるルーティングテーブルを有し、目的のノードのＩＤとＸＯＲ（排他的論理和）をとったときに最も小さくなるＩＤを有するノードにルーティングする。
【００１１】
例えば、ｍ＝４とすると、ＩＤが０（0000）のノードは、［0001，0010，0100，1000］すなわち［１，２，４，８］のルーティングテーブルを有する。具体的には、ＩＤが０のノードからＩＤが６のノードまでのルートを探索する場合には、ＩＤが０のノードのルーティングテーブルのなかで最も６（0110）とＸＯＲをとったときに最も小さくなる４（0100）が選択される。ＩＤが４のノードは、［0101，0110，0000，1100］すなわち［５，６，０，１２］のルーティングテーブルを有するため、［０，４，６］といったルートが探索される。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】I.Stoica、外５名、「Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications」、IEEE/ACM Transactions on Networking、第１１巻、第１号、２００３年２月、ｐ．１７−３２
【非特許文献２】P.Maymounkov、外１名、「Kademlia:A peer-to-peer information system based on the XOR metric」、The 1st International Workshop on Peer-to-Peer Systems、２００２年３月
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、探索アルゴリズムとしてChordを用いたものにおいて、ｍ＝４とし、ＩＤが１２のノードからＩＤが６のノードまでのルートを探索する場合には、ＩＤが１２のノードのルーティングテーブル［１３，１４，０，４］のなかで最も６に近い４が選択され、ＩＤが４のノードは、［５，６，８，１２］のルーティングテーブルを有するため、［１２，４，６］といったルートが探索される。
【００１４】
この場合、図６に示すように、経由するノードのＩＤが１２から４に減少した後に、６に増加するため、中継距離が冗長になってしまう。これにより、Chordを用いたものは、伝送遅延が生じたり、消費電力が余分にかかってしまったりすることがあるといった課題があった。
【００１５】
一方、探索アルゴリズムとしてKademliaを用いたものにおいて、ｍ＝４とし、ＩＤが１２のノードからＩＤが６のノードまでのルートを探索する場合には、ＩＤが１２（1100）のノードのルーティングテーブル［1101，1110，1000，0100］のなかで６（0110）ＸＯＲをとったときに最も小さくなるＩＤを有する４（0100）が選択され、ＩＤが４のノードは、［0101，0110，0000，1100］のルーティングテーブルを有するため、［１２，４，６］といったルートが探索される。
【００１６】
この場合も、図６に示すように、経由するノードのＩＤが１２から４に減少した後に、６に増加するため、中継距離が冗長になってしまう。これにより、Kademliaを用いたものも、伝送遅延が生じたり、消費電力が余分にかかってしまったりすることがあるといった課題があった。
【００１７】
本発明は、このような従来の課題を解決するためになされたもので、従来のものと比較して、伝送遅延および消費電力を低減することができる位置情報分散管理システムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明の位置情報分散管理システムは、サービスの対象エリアに１次元的に割り当てられたセル毎にサーバを設置し、前記各サーバには、一方向に０から１ずつ加算された識別情報が割り当てられ、前記各サーバは、ルーティングテーブルを格納するルーティングテーブル格納部と、前記ルーティングテーブルを構成する識別情報のなかで前記伝送データの伝送先に最も近いサーバの識別情報を抽出するサーバ抽出部と、前記サーバ抽出部によって抽出された識別情報が割り当てられたサーバに前記伝送データを伝送する伝送部と、を有する位置情報分散管理システムにおいて、前記ルーティングテーブルは、該当サーバに近いサーバから遠いサーバまでが段階的にグループ化され、各グループのなかで該当サーバに最も近いサーバの識別情報からなる構成を有している。
【００１９】
この構成により、本発明の位置情報分散管理システムは、各サーバに近いサーバから遠いサーバまでを段階的にグループ化し、各グループのなかで該当サーバに最も近いサーバを介してルーティングさせることにより中継距離が冗長になることを防止するため、従来のものと比較して、伝送遅延および消費電力を低減することができる。
【００２０】
例えば、前記ルーティングテーブルは、前記識別情報がｍビットで表される場合に、該当サーバの識別情報と上位ｍ−１ビットのみが等しい識別情報が割り当てられたサーバが該当サーバに最も近いサーバのグループに属し、該当サーバの識別情報と上位１ビットが異なる識別情報が割り当てられたサーバが該当サーバに最も遠いサーバのグループに属するように設定されている。
【００２１】
この構成により、本発明の位置情報分散管理システムは、各サーバに近いサーバから遠いサーバまでが段階的にグループ化され、各グループのなかで該当サーバに最も近いサーバを介してルーティングさせることができる。
【００２２】
なお、前記各サーバは、設置されたセルに関するセル情報を格納するセル情報格納部を有し、前記伝送部は、前記伝送データが該当セルに関する情報の要求を表す場合には、前記セル情報格納部に格納されたセル情報のなかで要求されたセル情報を表すデータを前記伝送データとして前記サーバ抽出部によって抽出された識別情報が割り当てられたサーバに伝送するようにしてもよい。
【００２３】
この構成により、本発明の位置情報分散管理システムは、サーバが設置されたセルに関する情報を要求元に伝送することができる。
【００２４】
また、前記伝送部は、前記セル情報を表す伝送データを受信したときに、前記セル情報を表すデータを要求した端末が該当セル内にある場合には、前記伝送データを前記端末に伝送するようにしてもよい。
【００２５】
この構成により、本発明の位置情報分散管理システムは、サーバが設置されたセルに関する情報を遠隔地にある端末に伝送することができる。
【発明の効果】
【００２６】
本発明は、従来のものと比較して、伝送遅延および消費電力を低減することができる位置情報分散管理システムを提供することができる。
【図面の簡単な説明】
【００２７】
【図１】本発明の一実施の形態に係る位置情報分散管理システムの構成を示すブロック図である。
【図２】本発明の一実施の形態に係る位置情報分散管理システムを構成するサーバに割り当てられた識別情報を示す概念図である。
【図３】本発明の一実施の形態に係る位置情報分散管理システムを構成するサーバのハードウェア構成図である。
【図４】本発明の一実施の形態に係る位置情報分散管理システムを構成するサーバの機能ブロック図である。
【図５】本発明の一実施の形態に係る位置情報分散管理システムによるルーティングを説明するための概念図である。
【図６】従来のアルゴリズムによるルーティングを説明するための概念図である。
【発明を実施するための形態】
【００２８】
以下に、本発明の実施の形態おける位置情報分散管理システムについて、図面を参照しながら説明する。
【００２９】
図１に示すように、本発明の一実施の形態に係る位置情報分散管理システム１は、サービスの対象エリアに１次元的に割り当てられたセル毎にサーバが設置されている。なお、図１において、本発明を理解しやすくするために１６個のサーバが示されているが、本発明の位置情報分散管理システムを構成するサーバの数を限定するものではない。
【００３０】
また、図１において、１６個のサーバのうち１つのサーバに符号１０が付されているが、他のサーバもサーバ１０と同様に構成される。また、本実施の形態においては、本発明を理解しやすくするために、各セルが直線状に割り当てられている例が示されているが、本発明においては、各セルが曲線状に割り当てられていてもよい。
【００３１】
図２に示すように、各サーバには、一方向にそれぞれ０から１ずつ加算された識別情報（ＩＤ）が割り当てられている。本実施の形態において、サーバは、互いに有線で通信するようになっているものとして説明するが、互いに無線で通信するようにしてもよい。
【００３２】
図３に示すように、サーバ１０は、ＣＰＵ（Central Processing Unit）２０と、ＲＡＭ（Random Access Memory）２１と、ＲＯＭ（Read Only Memory）２２と、ハードディスク装置２３と、キーボード装置やポインティングデバイス等よりなる入力装置２４と、表示装置２５と、携帯端末や車載器等の端末および他のサーバと通信するための通信モジュール２６とを備えた一般的なコンピュータ装置によって構成されている。
【００３３】
ＲＯＭ２２やハードディスク装置２３には、当該コンピュータ装置をサーバ１０として機能させるためのプログラムが記憶されている。すなわち、ＣＰＵ２０がＲＡＭ２１を作業領域としてＲＯＭ２２やハードディスク装置２３に記憶されたプログラムを実行することにより、当該コンピュータ装置は、サーバ１０として機能する。
【００３４】
図４に示すように、サーバ１０は、設置されたセルに関するセル情報を格納するセル情報格納部３０と、ルーティングテーブルを格納するルーティングテーブル格納部３１と、ルーティングテーブルを構成するＩＤのなかで伝送データの伝送先に最も近いサーバのＩＤを抽出するサーバ抽出部３２と、サーバ抽出部３２によって抽出されたＩＤが割り当てられたサーバに伝送データを伝送する伝送部３３とを備えている。
【００３５】
セル情報格納部３０は、ハードディスク装置２３によって構成され、サーバ１０が設けられたセルの気象情報、交通情報および店舗情報等のセル情報を格納するようになっている。なお、セル情報格納部３０は、セル情報を予め格納しておいてもよく、携帯端末や車載器等の移動端末から通信モジュール２６を介して無線通信により得られた情報を格納するようにしてもよい。
【００３６】
ルーティングテーブル格納部３１は、ハードディスク装置２３によって構成され、ルーティングテーブルは、サーバ１０に近いサーバから遠いサーバまでが段階的にグループ化され、各グループのなかでサーバ１０に最も近いサーバのＩＤからなる。
【００３７】
具体的には、ルーティングテーブルは、ＩＤがｍビットで表される場合に、サーバ１０のＩＤと上位ｍ−１ビットのみが等しいＩＤが割り当てられたサーバがサーバ１０に最も近いサーバのグループ（以下、単に「サーバグループ」という。）に属し、サーバ１０のＩＤと上位１ビットが異なるＩＤが割り当てられたサーバがサーバ１０に最も遠いサーバグループに属するように設定されている。
【００３８】
本実施の形態においては、ＩＤが４ビットで表されるため、ＩＤ（0001）が割り当てられたサーバを例に説明すると、ＩＤ（0001）と上位３ビットのみが等しい唯一のＩＤ（0000）が割り当てられたサーバが最も近いサーバグループに属し、（0000）がルーティングテーブルに設定されている。
【００３９】
また、ＩＤ（0001）と上位２ビットのみが等しいＩＤ（0010）が割り当てられたサーバおよびＩＤ（0011）が割り当てられたサーバが次に近いサーバグループに属し、このサーバグループに属するサーバのＩＤのなかでＩＤ（0001）に最も近いＩＤ（0010）がルーティングテーブルに設定されている。
【００４０】
また、ＩＤ（0001）と上位１ビットのみが等しいＩＤ（0100）〜ＩＤ（0111）がそれぞれ割り当てられたサーバが次に近いサーバグループに属し、このサーバグループに属するサーバのＩＤのなかでＩＤ（0001）に最も近いＩＤ（0100）がルーティングテーブルに設定されている。
【００４１】
また、ＩＤ（0001）と上位１ビットが異なるＩＤ（1000）〜ＩＤ（1111）がそれぞれ割り当てられたサーバが最も遠いサーバのサーバグループに属し、このサーバグループに属するサーバのＩＤのなかでＩＤ（0001）に最も近いＩＤ（1000）がルーティングテーブルに設定されている。
【００４２】
このように、ＩＤ（１）が割り当てられたサーバのルーティングテーブルには、［０，２，４，８］が設定されている。
【００４３】
サーバ抽出部３２は、ＣＰＵ２０によって構成され、ルーティングテーブルを構成するＩＤのなかで伝送データの伝送先に最も近いサーバのＩＤを抽出するようになっている。ここで、ルーティングテーブルを構成するＩＤのなかで伝送データの伝送先に最も近いＩＤが２つ存在する場合には、サーバ抽出部３２は、サーバ１０に割り当てられたＩＤにより近いＩＤを抽出するようになっている。
【００４４】
例えば、ＩＤ（６）が割り当てられたサーバを伝送データの伝送先とし、ＩＤ（１）が割り当てられたサーバを例に説明すると、サーバ抽出部３２は、ルーティングテーブルに登録されたＩＤ［０，２，４，８］のなかでＩＤ（６）に最も近いＩＤ［４，８］のなかでＩＤ（１）により近いＩＤ（４）を抽出するようになっている。
【００４５】
伝送部３３は、ＣＰＵ２０および通信モジュール２６によって構成され、他のサーバから伝送された伝送データをサーバ抽出部３２によって抽出されたＩＤが割り当てられたサーバに伝送するようになっている。
【００４６】
また、伝送部３３は、伝送データを受信したときに、サーバ１０が伝送データの伝送先である場合、すなわち、サーバ１０が設置されたセルに関する情報の要求を伝送データが表す場合には、セル情報格納部３０に格納されたセル情報のなかで要求されたセル情報を表すデータを伝送データとしてセル情報の要求元に伝送されるように、サーバ抽出部３２によって抽出されたＩＤが割り当てられたサーバに伝送するようになっている。
【００４７】
また、伝送部３３は、セル情報を表す伝送データを受信したときに、サーバ１０が設置されたセル内に、セル情報を表すデータを要求した端末がある場合には、伝送データを端末に伝送するようになっている。
【００４８】
以上のようにサーバ１０を構成することにより、例えば、図５に示すように、ＩＤ（１２）が割り当てられたサーバからＩＤ（６）が割り当てられたサーバまでの伝送ルートを探索する場合には、ＩＤ（１２）が割り当てられたサーバのルーティングテーブル［１３，１４，１１，７］のなかでＩＤ（６）に最も近いＩＤ（７）が抽出され、ＩＤ（７）が割り当てられたサーバのルーティングテーブル［６，５，３，８］のなかでＩＤ（６）が割り当てられたサーバが抽出され、［１２，７，６］といった伝送ルートが探索される。したがって、経由するノードのＩＤが１２から７に減少した後に、６に減少するため、中継距離が冗長になることが防止される。
【００４９】
サービスの対象エリアに割り当てたセルの数をＮとした場合に、位置情報分散管理システム１（以下、位置情報分散管理システム１の探索アルゴリズムを「Proposal」という）によるルート探索における平均ホップ数は、１／２（ｌｏｇＮ）となり、ChordやKademliaのアルゴリズムに基づいて探索した場合と違いはないが、平均中継距離は、下記の数式に示すように、Chord、Kademliaにそれぞれ基づいて探索した場合と比較して短くなっている。
【００５０】
【数１】
2012080391.tif 000003
【００５１】
このように、本発明の一実施の形態に係る位置情報分散管理システム１は、各サーバに近いサーバから遠いサーバまでを段階的にグループ化し、各グループのなかで該当サーバに最も近いサーバを介してルーティングさせることにより中継距離が冗長になることを防止するため、従来のものと比較して、伝送遅延および消費電力を低減することができる。
【００５２】
なお、本実施の形態において、サービスの対象エリアに１次元的に割り当てられたセル毎にサーバを設置した例について説明したが、本発明においては、各セル間が離隔していてもよく、重なりを有していてもよい。また、各セルのサイズおよび形状は、全て同じでなくともよい。
【産業上の利用可能性】
【００５３】
本発明の位置情報分散管理システムは、鉄道やバス等の停車場周辺および道路のサービスエリア、パーキングエリアまたは料金所周辺等の特定位置の気象情報、交通情報および店舗情報等の経度および緯度に対応する情報を端末に提供するシステムとして利用することができる。
【符号の説明】
【００５４】
１  位置情報分散管理システム
１０  サーバ
２０  ＣＰＵ
２１  ＲＡＭ
２２  ＲＯＭ
２３  ハードディスク装置
２４  入力装置
２５  表示装置
２６  通信モジュール
３０  セル情報格納部
３１  ルーティングテーブル格納部
３２  サーバ抽出部
３３  伝送部
【図１】
2012080391.tif 000004
【図２】
2012080391.tif 000005
【図３】
2012080391.tif 000006
【図４】
2012080391.tif 000007
【図５】
2012080391.tif 000008
【図６】
2012080391.tif 000009