(57)【特許請求の範囲】
【請求項１】
予め定められたエリアに関連するエリアデータを、移動端末群の各移動端末に対応するノードの集合に対して分散して割り当てることにより、前記エリアデータを前記移動端末群の各移動端末で分散して記憶するためのデータ分散記憶システムにおける移動端末であって、
周辺の移動端末と無線通信を行うための通信手段と、
前記エリアを分割した分割エリアのうち、自端末が存在する前記分割エリアに隣接する前記分割エリアの各々について、前記隣接する分割エリア内に存在する移動端末のグループを経由してルーティング可能な、分割エリア内に存在する移動端末のグループのグループＩＤの集合を表わすグループ間ルーティング情報を、前記隣接する各分割エリア内に存在する移動端末から前記通信手段により受信して取得するＩＤ取得手段と、
自端末が存在する前記分割エリアに隣接する前記分割エリアの各々を送信先として、前記ＩＤ取得手段によって取得した各グループ間ルーティング情報のうち、前記送信先の分割エリアについて取得した前記グループ間ルーティング情報を除いた前記グループ間ルーティング情報の各々が表わすグループＩＤの和集合と、自端末が存在する前記分割エリアの前記グループＩＤとを表わす前記グループ間ルーティング情報を、前記送信先へ送信する前記グループ間ルーティング情報として各々生成するルーティング情報生成手段と、
前記ルーティング情報生成手段によって生成された前記グループ間ルーティング情報の各々を、前記送信先の各々へ送信するように前記通信手段を制御する送信制御手段と、
を含む移動端末。
【請求項２】
前記ルーティング情報生成手段は、前記隣接する前記分割エリアの各々に対して予め定められた、前記分割エリアを送信先とする前記グループ間ルーティング情報を生成するために必要な前記グループ間ルーティング情報の送信元となる前記分割エリアに基づいて、隣接する前記分割エリアの各々について、前記分割エリアに対して定められた前記送信元の分割エリアの全てについて前記グループ間ルーティング情報を取得したときに、前記分割エリアを送信先として送信する前記グループ間ルーティング情報を生成する請求項１記載の移動端末。
【請求項３】
前記ルーティング情報生成手段は、前記隣接する前記分割エリアの各々の自端末に対する方角に応じて予め定められた、前記分割エリアを送信先とする前記グループ間ルーティング情報を生成するために必要な前記グループ間ルーティング情報の送信元となる前記分割エリアに基づいて、隣接する前記分割エリアの各々について、前記分割エリアの方角に応じて定められた前記送信元の分割エリアの全てについて前記グループ間ルーティング情報を取得したときに、前記分割エリアを送信先として送信する前記グループ間ルーティング情報を生成する請求項１記載の移動端末。
【請求項４】
前記送信制御手段は、前記送信先の分割エリアに移動端末が存在するか否かを判断し、前記送信先の分割エリアに移動端末が存在しないと判断した場合、前記送信先へ送信する前記グループ間ルーティング情報を、前記送信先の分割エリアに対して予め定められた転送経路で送信するように前記通信手段を制御する請求項１〜請求項３の何れか１項記載の移動端末。
【請求項５】
前記ルーティング情報生成手段は、前記ＩＤ取得手段によって取得した各グループ間ルーティング情報のうち、前記送信先の分割エリアについて取得した前記グループ間ルーティング情報を除いた前記グループ間ルーティング情報の各々が表わすグループＩＤの和集合の各グループＩＤのビットパターンと、自端末が存在する前記分割エリアの前記グループＩＤのビットパターンとを足し合わせたビットパターンを、前記グループ間ルーティング情報として生成する請求項１〜請求項４の何れか１項記載の移動端末。
【請求項６】
自端末が存在する前記分割エリア内に存在する各移動端末を示すノードＩＤを取得するノードＩＤ取得手段を更に含み、
前記グループＩＤのビットパターンを、前記分割エリア内に存在する各移動端末を示すノードＩＤを用いて定められるビットパターンとし、
前記ルーティング情報生成手段は、前記ノードＩＤ取得手段によって取得した、自端末が存在する前記分割エリア内に存在する各移動端末を示すノードＩＤ及び自端末のノードＩＤを用いて、自端末が存在する前記分割エリアに対応する前記グループＩＤのビットパターンを生成し、前記ＩＤ取得手段によって取得した各グループ間ルーティング情報のうち、前記送信先の分割エリアについて取得した前記グループ間ルーティング情報を除いた前記グループ間ルーティング情報の各々が表わすグループＩＤの和集合の各グループＩＤのビットパターンと、前記生成された自端末の前記グループＩＤのビットパターンとを足し合わせて、前記グループ間ルーティング情報のビットパターンを生成する請求項５記載の移動端末。
【請求項７】
周辺の移動端末から、前記通信手段により前記エリアデータを受信した場合に、前記ノードＩＤ取得手段によって取得した自端末が存在する前記分割エリア内に存在する各移動端末のノードＩＤ及び自端末のノードＩＤを用いて、自端末が存在する前記分割エリアに対応する前記グループＩＤを生成すると共に、前記受信したエリアデータのデータＩＤを所定の関数を用いてランダムパターンに変換し、前記ランダムパターンを用いて、前記ＩＤ取得手段によって前記隣接する分割エリアの各々から取得した前記グループ間ルーティング情報のビットパターンと、前記生成した自端末が存在する前記分割エリアに対応するグループＩＤのビットパターンとの各々に処理を加え、前記処理が加えられた各ビットパターンを評価して、前記エリアデータを割り当てる前記移動端末のグループを決定するグループ決定手段と、
前記グループ決定手段によって決定された前記グループが、自端末が存在する前記分割エリアに対応するグループである場合、前記ノードＩＤ取得手段によって取得した自端末が存在する前記分割エリア内に存在する各移動端末のノードＩＤ及び自端末のノードＩＤの各々をビットパターンに変換すると共に、前記受信したエリアデータのデータＩＤを所定の関数を用いてランダムパターンに変換し、前記ランダムパターンを用いて、前記変換した各移動端末のノードＩＤ及び自端末のノードＩＤの各々のビットパターンに処理を加え、前記処理が加えられた各移動端末のノードＩＤ及び自端末のノードＩＤの各々のビットパターンを評価して、前記エリアデータを割り当てる前記ノードを決定するノード決定手段と、
前記自端末のノードに割り当てられた前記エリアデータを記憶する記憶手段と、
前記グループ決定手段によって決定されたグループが、自端末が存在する前記分割エリアに対応するグループでない場合、及び前記ノード決定手段によって決定されたノードが、自端末のノードでない場合、前記受信した前記エリアデータを他の移動端末へ転送するように前記通信手段を制御する転送制御手段と、
を更に含む請求項６記載の移動端末。
【請求項８】
ノードＩＤに応じて１以上である所定数のビットを１にしたビットパターンを、対応する前記分割エリア内に存在する各移動端末のノードＩＤについて足し合わせることにより、前記グループＩＤのビットパターンを求めた請求項５〜請求項７の何れか１項記載の移動端末。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、移動端末に係り、特に、エリアに関するデータを移動端末群で分散して記憶する移動端末に関する。
【背景技術】
【０００２】
従来から、ＭＡＮＥＴ環境への適応を目標としたＤＨＴ（Ｄｉｓｔｒｉｂｕｔｅｄ  Ｈａｓｈ  Ｔａｂｌｅ）の一つとして、ＭＡＤＰａｓｔｒｙが知られている（非特許文献１）。ＭＡＤＰａｓｔｒｙでは、ルーティングテーブルの肥大化、維持コストを抑えるために、複数のグループに分割して管理を行っている。Ｐａｓｔｒｙと呼ばれるＤＨＴに基づいた手法で、アドホックルーティングプロトコルにはＡＯＤＶを用いている。
【０００３】
また、ＭＡＤＰａｓｔｒｙに参加する移動体は必ず、どこかのグループに属している。各グループのマスターはグループのビーコンを発信し、グループマスター以外の移動体は受信したビーコンのホップ数が最も少ないグループに属する。また、各移動体はグループへのルーティングテーブルと同一グループの移動体リストを持ち、これらを用いてルーティングを行っている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｔｈｏｍａｓ  Ｚａｈｎ  ａｎｄ  Ｊｏｃｈｅｎ  Ｓｃｈｉｌｌｅｒ，”Ａ  ＤＨＴ  ｓｕｂｓｔｒａｔｅ  ＦＯＲ  ｐｒａｃｔｉｃａｂｌｙ  ｓｉｚｅｄ  ＭＡＮＥＴｓ”  ｉｎ  ＡＳＷＮ，  Ｊｕｎｅ  ２００５
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上記のＭＡＤＰａｓｔｒｙでは、位置情報を用いてグループに分けて管理しているが、各グループは、遠方のグループのルーティング情報を維持する必要があるため、ルーティングテーブルの更新に遅延が生じ、通信量も大きくなる可能性が高い、という問題がある。
【０００６】
本発明は、上記の問題点を解決するためになされたもので、ルーティング情報の更新の遅延を抑制すると共に、ルーティング情報を維持するための通信負荷の増大を抑制することができる移動端末を提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記の目的を達成するために本発明に係る移動端末は、予め定められたエリアに関連するエリアデータを、移動端末群の各移動端末に対応するノードの集合に対して分散して割り当てることにより、前記エリアデータを前記移動端末群の各移動端末で分散して記憶するためのデータ分散記憶システムにおける移動端末であって、周辺の移動端末と無線通信を行うための通信手段と、前記エリアを分割した分割エリアのうち、自端末が存在する前記分割エリアに隣接する前記分割エリアの各々について、前記隣接する分割エリア内に存在する移動端末のグループを経由してルーティング可能な、分割エリア内に存在する移動端末のグループのグループＩＤの集合を表わすグループ間ルーティング情報を、前記隣接する各分割エリア内に存在する移動端末から前記通信手段により受信して取得するＩＤ取得手段と、自端末が存在する前記分割エリアに隣接する前記分割エリアの各々を送信先として、前記ＩＤ取得手段によって取得した各グループ間ルーティング情報のうち、前記送信先の分割エリアについて取得した前記グループ間ルーティング情報を除いた前記グループ間ルーティング情報の各々が表わすグループＩＤの和集合と、自端末が存在する前記分割エリアの前記グループＩＤとを表わす前記グループ間ルーティング情報を、前記送信先へ送信する前記グループ間ルーティング情報として各々生成するルーティング情報生成手段と、前記ルーティング情報生成手段によって生成された前記グループ間ルーティング情報の各々を、前記送信先の各々へ送信するように前記通信手段を制御する送信制御手段と、を含んで構成されている。
【０００８】
本発明の移動端末によれば、ＩＤ取得手段によって、前記エリアを分割した分割エリアのうち、自端末が存在する前記分割エリアに隣接する前記分割エリアの各々について、前記隣接する分割エリア内に存在する移動端末のグループを経由してルーティング可能な、分割エリア内に存在する移動端末のグループのグループＩＤの集合を表わすグループ間ルーティング情報を、前記隣接する各分割エリア内に存在する移動端末から前記通信手段により受信して取得する。
【０００９】
そして、ルーティング情報生成手段によって、自端末が存在する前記分割エリアに隣接する前記分割エリアの各々を送信先として、前記ＩＤ取得手段によって取得した各グループ間ルーティング情報のうち、前記送信先の分割エリアについて取得した前記グループ間ルーティング情報を除いた前記グループ間ルーティング情報の各々が表わすグループＩＤの和集合と、自端末が存在する前記分割エリアの前記グループＩＤとを表わす前記グループ間ルーティング情報を、前記送信先へ送信する前記グループ間ルーティング情報として各々生成する。送信制御手段によって、前記ルーティング情報生成手段によって生成された前記グループ間ルーティング情報の各々を、前記送信先の各々へ送信するように前記通信手段を制御する。
【００１０】
このように、隣接する各分割エリアのグループを経由してルーティング可能なグループのグループＩＤの和集合と、自端末が存在する分割エリアのグループＩＤとを表わすグループ間ルーティング情報を生成して、隣接する各分割エリア内の移動体との間でグループ間ルーティング情報を送受信することにより、ルーティング情報の更新の遅延を抑制すると共に、ルーティング情報を維持するための通信負荷の増大を抑制することができる。
【００１１】
本発明に係るルーティング情報生成手段は、前記隣接する前記分割エリアの各々に対して予め定められた、前記分割エリアを送信先とする前記グループ間ルーティング情報を生成するために必要な前記グループ間ルーティング情報の送信元となる前記分割エリアに基づいて、隣接する前記分割エリアの各々について、前記分割エリアに対して定められた前記送信元の分割エリアの全てについて前記グループ間ルーティング情報を取得したときに、前記分割エリアを送信先として送信する前記グループ間ルーティング情報を生成するようにすることができる。これによって、ルーティング情報の更新順序を指定することができ、ルーティング情報の更新の遅延を更に抑制すると共に、ルーティング情報を維持するための通信負荷の増大を更に抑制することができる。
【００１２】
本発明に係るルーティング情報生成手段は、前記隣接する前記分割エリアの各々の自端末に対する方角に応じて予め定められた、前記分割エリアを送信先とする前記グループ間ルーティング情報を生成するために必要な前記グループ間ルーティング情報の送信元となる前記分割エリアに基づいて、隣接する前記分割エリアの各々について、前記分割エリアの方角に応じて定められた前記送信元の分割エリアの全てについて前記グループ間ルーティング情報を取得したときに、前記分割エリアを送信先として送信する前記グループ間ルーティング情報を生成するようにすることができる。これによって、ルーティング情報の更新順序を指定することができ、ルーティング情報の更新の遅延を更に抑制すると共に、ルーティング情報を維持するための通信負荷の増大を更に抑制することができる。
【００１３】
上記のルーティング情報生成手段は、前記ＩＤ取得手段によって取得した各グループ間ルーティング情報のうち、前記送信先の分割エリアについて取得した前記グループ間ルーティング情報を除いた前記グループ間ルーティング情報の各々が表わすグループＩＤの和集合の各グループＩＤのビットパターンと、自端末が存在する前記分割エリアの前記グループＩＤのビットパターンとを足し合わせたビットパターンを、前記グループ間ルーティング情報として生成するようにすることができる。これによって、グループ間ルーティング情報のデータ量を抑制することができ、ルーティング情報を維持するための通信負荷の増大を更に抑制することができる。
【００１４】
グループ間ルーティング情報をビットパターンとする上記移動端末は、自端末が存在する前記分割エリア内に存在する各移動端末を示すノードＩＤを取得するノードＩＤ取得手段を更に含み、前記グループＩＤのビットパターンを、前記分割エリア内に存在する各移動端末を示すノードＩＤを用いて定められるビットパターンとし、前記ルーティング情報生成手段は、前記ノードＩＤ取得手段によって取得した、自端末が存在する前記分割エリア内に存在する各移動端末を示すノードＩＤ及び自端末のノードＩＤを用いて、自端末が存在する前記分割エリアに対応する前記グループＩＤのビットパターンを生成し、前記ＩＤ取得手段によって取得した各グループ間ルーティング情報のうち、前記送信先の分割エリアについて取得した前記グループ間ルーティング情報を除いた前記グループ間ルーティング情報の各々が表わすグループＩＤの和集合の各グループＩＤのビットパターンと、前記生成された自端末の前記グループＩＤのビットパターンとを足し合わせて、前記グループ間ルーティング情報のビットパターンを生成するようにすることができる。
【００１５】
また、上記移動端末は、周辺の移動端末から、前記通信手段により前記エリアデータを受信した場合に、前記ノードＩＤ取得手段によって取得した自端末が存在する前記分割エリア内に存在する各移動端末のノードＩＤ及び自端末のノードＩＤを用いて、自端末が存在する前記分割エリアに対応する前記グループＩＤを生成すると共に、前記受信したエリアデータのデータＩＤを所定の関数を用いてランダムパターンに変換し、前記ランダムパターンを用いて、前記ＩＤ取得手段によって前記隣接する分割エリアの各々から取得した前記グループ間ルーティング情報のビットパターンと、前記生成した自端末が存在する前記分割エリアに対応するグループＩＤのビットパターンとの各々に処理を加え、前記処理が加えられた各ビットパターンを評価して、前記エリアデータを割り当てる前記移動端末のグループを決定するグループ決定手段と、前記グループ決定手段によって決定された前記グループが、自端末が存在する前記分割エリアに対応するグループである場合、前記ノードＩＤ取得手段によって取得した自端末が存在する前記分割エリア内に存在する各移動端末のノードＩＤ及び自端末のノードＩＤの各々をビットパターンに変換すると共に、前記受信したエリアデータのデータＩＤを所定の関数を用いてランダムパターンに変換し、前記ランダムパターンを用いて、前記変換した各移動端末のノードＩＤ及び自端末のノードＩＤの各々のビットパターンに処理を加え、前記処理が加えられた各移動端末のノードＩＤ及び自端末のノードＩＤの各々のビットパターンを評価して、前記エリアデータを割り当てる前記ノードを決定するノード決定手段と、前記自端末のノードに割り当てられた前記エリアデータを記憶する記憶手段と、前記グループ決定手段によって決定されたグループが、自端末が存在する前記分割エリアに対応するグループでない場合、及び前記ノード決定手段によって決定されたノードが、自端末のノードでない場合、前記受信した前記エリアデータを他の移動端末へ転送するように前記通信手段を制御する転送制御手段と、を更に含むようにすることができる。
【００１６】
ノードＩＤに応じて１以上である所定数のビットを１にしたビットパターンを、対応する前記分割エリア内に存在する各移動端末のノードＩＤについて足し合わせることにより、前記グループＩＤのビットパターンを求めるようにすることができる。これによって、エリアデータを多くの移動端末で安定して分散記憶することができる。
【発明の効果】
【００１７】
以上説明したように、本発明の移動端末によれば、隣接する各分割エリアのグループを経由してルーティング可能なグループのグループＩＤの和集合と、自端末が存在する分割エリアのグループＩＤとを表わすグループ間ルーティング情報を生成して、隣接する各分割エリア内の移動体との間でグループ間ルーティング情報を送受信することにより、ルーティング情報の更新の遅延を抑制すると共に、ルーティング情報を維持するための通信負荷の増大を抑制することができる、という効果が得られる。
【図面の簡単な説明】
【００１８】
【図１】本発明の第１の実施の形態に係る移動端末の構成を示すブロック図である。
【図２】ノードのハッシュ値とデータのハッシュ値との対応関係を示す図である。
【図３】交差点エリア内に入った移動端末に対してデータが割り当てられている様子を示す図である。
【図４】エリアから離脱する移動端末が、他の移動端末にエリアデータを渡す様子を示すイメージ図である。
【図５】単層のＤＨＴにおけるルーティング情報の通信を示す図である。
【図６】２階層のＤＨＴにおけるルーティング情報の通信を示す図である。
【図７】グループＩＤの構成を説明するための図である。
【図８】グループの構成を説明するための図である。
【図９】グループが存在しない参考例におけるルーティングテーブルを説明するための図である。
【図１０】グループが存在しない参考例におけるルーティング情報を説明するための図である。
【図１１】グループ内ルーティングテーブル及びグループ間ルーティングテーブルを説明するための図である。
【図１２】グループ間ルーティング情報を説明するための図である。
【図１３】ルーティング情報生成部の構成を示す図である。
【図１４】グループ内ルーティング情報を説明するための図である。
【図１５】隣接グループとビットパターンを交換する様子を示す図である。
【図１６】隣接グループにグループ間ルーティング情報を送信する様子を示す図である。
【図１７】グループ間ルーティングテーブルの更新順序の例を示す図である。
【図１８】グループ間ルーティング情報を送信していない初期状態を示す図である。
【図１９】エリア端のグループからグループ間ルーティング情報を送信した状態を示す図である。
【図２０】エリア中心のグループへグループ間ルーティング情報を送信した状態を示す図である。
【図２１】エリア中心のグループからグループ間ルーティング情報を送信した状態を示す図である。
【図２２】エリア端のグループへグループ間ルーティング情報を送信した状態を示す図である。
【図２３】一つのグループからのグループ間ルーティング情報の送信が遅延した場合を説明するための図である。
【図２４】グループ決定部の構成を示す図である。
【図２５】グループのビットパターンの並び替えを行う様子を示す図である。
【図２６】ノード決定部の構成を示す図である。
【図２７】本発明の第１の実施の形態に係る移動端末における参加時処理ルーチンの内容を示すフローチャートである。
【図２８】本発明の第１の実施の形態に係る移動端末における参加中処理ルーチンの内容を示すフローチャートである。
【図２９】本発明の第１の実施の形態に係る移動端末におけるグループ間移動時処理ルーチンの内容を示すフローチャートである。
【図３０】本発明の第１の実施の形態に係る移動端末におけるデータ転送処理ルーチンの内容を示すフローチャートである。
【図３１】本発明の第１の実施の形態に係る移動端末におけるグループ内ルーティング情報受信時処理ルーチンの内容を示すフローチャートである。
【図３２】本発明の第１の実施の形態に係る移動端末におけるデータ受信時処理ルーチンの内容を示すフローチャートである。
【図３３】本発明の第１の実施の形態に係る移動端末におけるグループ間ルーティング情報受信時処理ルーチンの内容を示すフローチャートである。
【図３４】本発明の第１の実施の形態に係る移動端末におけるエリア端グループ送信処理ルーチンの内容を示すフローチャートである。
【図３５】本発明の第１の実施の形態に係る移動端末におけるグループ間ルーティング情報送信処理ルーチンの内容を示すフローチャートである。
【図３６】グループ間ルーティングテーブルの更新順序の例を示す図である。
【図３７】エリア南北方向端のグループ及びエリア東西方向端のグループを説明するための図である。
【図３８】南北方向に隣接グループ間でグループ間ルーティング情報を送信した状態を示す図である。
【図３９】東西方向に隣接グループ間でグループ間ルーティング情報を送信した状態を示す図である。
【図４０】南北方向に隣接グループ間でグループ間ルーティング情報を送信した状態を示す図である。
【図４１】ルーティング情報生成部の構成を示す図である。
【図４２】グループ間ルーティング情報を転送する様子を示す図である。
【図４３】ノードＩＤのＢｌｏｏｍ  Ｆｉｌｔｅｒ（ＢＦ）及びグループＩＤのＢＦを説明するための図である。
【図４４】参考例におけるＢＦの動作を説明するための図である。
【図４５】グループＩＤのＢＦを生成する方法を説明するための図である。
【図４６】グループ決定部の構成を示す図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照して、本発明の好適な実施の形態について説明する。なお、本発明を適用した移動端末を車両に搭載し、複数の移動端末の間で無線通信を行って、データを分散して記憶するデータ分散記憶システムを例に説明する。
【００２０】
図１に示すように、第１の実施の形態に係るデータ分散記憶システムの移動端末１０は、自端末を搭載している車両に設けられ、かつ、自端末の位置を測定するためのＧＰＳ１２と、周辺の他の移動端末１０と無線通信を行うためのデータ通信部１４と、ＧＰＳ１２によって測定された自端末の位置に基づいて、周辺の複数の移動端末１０を含む移動端末群でのデータの分散管理を行うコンピュータ１６とを備えている。
【００２１】
データ通信部１４は、無線アドホック通信を行って、周辺の他の移動端末１０と通信を行う。データ通信部１４は、送信データとして、ＧＰＳ１２によって計測した自端末の位置情報を含むデータを送信する。データ通信部１４は、後述するグループ内ルーティング情報を送信する場合には、ＤＳＤＶのようなプロアクティブ形式のアドホックプロトコルで、同一グループ内でグループ内ルーティング情報を共有する。
【００２２】
コンピュータ１６は、移動端末１０全体の制御を司るＣＰＵ、後述する参加時処理ルーチン、参加中処理ルーチン、グループ内ルーティング情報受信時処理ルーチン、データ受信時処理ルーチン、グループ間ルーティング情報受信時処理ルーチン、エリア端グループ送信時処理ルーチン、及びグループ間ルーティング情報送信処理ルーチンのプログラム等を記憶した記憶媒体としてのＲＯＭ、ワークエリアとしてデータを一時格納するＲＡＭ、及びこれらを接続するバスを含んで構成されている。このような構成の場合には、各構成要素の機能を実現するためのプログラムをＲＯＭに記憶しておき、これをＣＰＵが実行することによって、各機能が実現されるようにする。
【００２３】
このコンピュータ１６をハードウエアとソフトウエアとに基づいて定まる機能実現手段毎に分割した機能ブロックで説明すると、上記図１に示すように、各交差点エリアの位置情報及び後述する分割エリアの位置情報を含む道路地図データ、並びに各分割エリアに対するルーティング情報送信条件情報を記憶する地図データベース２０と、ＧＰＳ１２によって計測された自端末の位置を取得する共に、地図データベース２０から自車両の直近の交差点エリアの位置情報及び分割エリアの位置情報を取得する位置取得部２２と、位置取得部２２によって取得された自端末位置と交差点エリアの中心位置との距離、及び分割エリアの中心位置との距離に基づいて、後述するグループ内ルーティングテーブル管理部２６及びグループ間ルーティングテーブル管理部３０を制御する制御部２４と、地図データベース２０から自端末が存在する分割エリアに対して定められたルーティング情報送信条件情報を取得する送信条件取得部２５と、グループ内のルーティングを行うためのグループ内ルーティングテーブルを管理するグループ内ルーティングテーブル管理部２６と、グループ内ルーティングテーブルを記憶するグループ内ルーティングテーブル記憶部２８と、ルーティング情報送信条件情報を用いて、グループ間のルーティングを行うためのグループ間ルーティングテーブルを管理するグループ間ルーティングテーブル管理部３０と、グループ間ルーティングテーブルを記憶するグループ間ルーティングテーブル記憶部３２と、ＤＨＴに従ってデータ分散管理を行うデータ管理部３４と、自端末に対して割り当てられたエリアデータを記憶するデータ記憶部３６と、グループ内ルーティング情報を生成すると共に、グループ間ルーティングテーブルに基づいてグループ間ルーティング情報を生成するルーティング情報生成部３８とを備えている。なお、グループ内ルーティングテーブル管理部２６が、ノードＩＤ取得手段の一例であり、グループ間ルーティングテーブル管理部３０がＩＤ取得手段の一例である。また、ルーティング情報生成部３８が、ルーティング情報生成手段及び送信制御手段の一例である。データ管理部３４が、グループ決定手段、ノード決定手段、転送制御手段の一例であり、ＤＨＴデータ記憶部３６が、記憶手段の一例である。
【００２４】
ここで、本実施の形態に係るデータ分散管理を行う原理について説明する。
【００２５】
本実施の形態では、移動体が無線通信を行う環境下で、位置に依存した情報（エリアデータ）を、特定のエリア（例えば、交差点）内の複数の移動端末によって維持し、分散管理する。エリアから離脱する移動端末は、エリア内の他の移動端末にデータを転送することで、エリア内へ情報を維持する。データの分散管理を、ＤＨＴを用いて実現する。
【００２６】
ＤＨＴ（Ｄｉｓｔｒｉｂｕｔｅｄ  Ｈａｓｈ  Ｔａｂｌｅ）とは、分散環境でデータを管理する手法の１つであり、ハッシュテーブルを用いてデータを管理する手法である。また、ハッシュテーブルは、キーとデータの組を格納し、キーに対応するデータをすばやく参照するためのデータ構造である。
【００２７】
ＤＨＴの例としては、Ｃｈｏｒｄ、Ｐａｓｔｒｙ、Ｋａｄｅｍｌｉａなどが挙げられ、ＤＨＴの応用例としては、Ｄｙｎａｍｏ、Ｃａｓｓａｎｄｒａ、Ｋａｉなどがある。
【００２８】
ＤＨＴを用いることにより、データ管理負荷をノードに対して均等に分散でき、エリアデータを誰が持つか、サーバ無しで一意に決定でき、データのキーが分かれば正確な目的地がわからなくてもルーティング可能である。ただし、ルーティングテーブルが正しく構成されていることが条件である。また、ＤＨＴを無線通信環境で応用することで、特定エリアに仮想分散データベースを実現することができる。
【００２９】
ここで、Ｃｈｏｒｄを用いたデータ分散管理について説明する。各移動端末の持つ固有のＩＤとデータの持つ固有のＩＤとをそれぞれ、ハッシュ関数を用いてハッシュ値にする。移動端末（ノード）とデータとは、図２のように対応付けられ、データは、自身のハッシュ値より大きいハッシュ値を持つ移動端末（ノード）の中で、最小のハッシュ値を持つ移動端末（ノード）に保存される。
【００３０】
また、自端末位置と交差点位置との距離が、所定値以内であれば、参加処理を行う。参加処理では、自端末ＥのＩＤのハッシュ値ｆ（Ｅ）を計算して、自端末のノードを追加する。これによって、図３に示すように、自端末のノードに割り当てられるエリアデータが、他の移動端末Ａから送信され、自端末が当該エリアデータを受け取る。なお、図３の例では、他の移動端末Ｄを介して、他の移動端末Ａからのエリアデータを自端末Ｅが受け取っている。
【００３１】
また、自端末位置と交差点位置との距離が、所定値より大きくなると、離脱処理を行う。離脱処理では、自端末のノードを削除する。これによって、図４に示すように、自端末（図４のＧ参照）のノードに割り当てられていたエリアデータが、他の移動端末Ｄへ送信される。なお、図４の例では、他の移動端末Ｆを介して、自端末Ｇから他の移動端末Ｄへエリアデータが送信されている。
【００３２】
ここで、図５に示すような階層化されていないＤＨＴでは、データを正しく管理するために、エリア内の全ノードＩＤを知る必要がある。そのため、ＤＨＴのルーティングテーブルを維持するための通信が多くなる。そこで、本実施の形態では、ルーティングテーブルを維持するための通信を抑制するために、図６のような２階層ＤＨＴを用いる。２階層ＤＨＴでは、データを管理するために複数のノードで構成されるグループという単位を追加する。ＤＨＴを階層化する場合、データはまずどのグループで管理するかが決定され、その後グループ内のどのノードがデータを管理するかが決定される。各ノードは所属するグループ内の全ノードＩＤと情報保持エリア内のグループＩＤを知っていればルーティング可能であるためルーティングテーブルの維持コストを抑制できる。
【００３３】
また、本実施の形態では、グループ内のノードＩＤを用いてグループＩＤを変更する２階層ＤＨＴを採用する。すなわち、図７に示すように、グループＩＤをグループ内のノードＩＤのＯＲ演算によって構成することで、グループとノードのＩＤの間で関連付けを行う。これによって、各ノードは全ノードＩＤを知る必要が無いため、ルーティングテーブル管理通信を低く抑えることが可能となる。また、グループ間をノードが移動する際に、ノードが管理しているデータが移動後のグループに所属する可能性があるように、グループＩＤが適切に変更されるため、グループ間を移動しても、同じノードに対して同じデータ割り当てられる可能性があり、データ通信の発生を抑えられる。
【００３４】
次に、グループ構成の具体例を図８に示す。交差点エリアは位置情報を用いて複数の分割エリアに分割され、ノードのグループが、分割エリアの中心座標と範囲（ｘ座標、ｙ座標、範囲）によって定義される。例えば、グループＡが（１５０、３００、１００）で定義され、グループＢが（３００、３００、１００）で定義され、グループＣが（４５０、３００、１００）で定義される。なお、交差点エリアが、情報保持エリアの一例である。
【００３５】
また、グループ（分割エリア）のサイズは、同一グループ内の全ノードが１ホップで通信可能なサイズを想定している。
【００３６】
グループＩＤは可変であり、内部ノードによって構成される。上記図８の例では、グループＩＤのサイズは１０ｂｉｔで、グループ内に存在するノードＩＤの各々からビットパターンに１を書き込む位置を決定している。グループＡでは内部ノードＩＤの各々が１、２、３であり、１〜３ビットに１の書き込みを行うので、グループＩＤは”０００００００１１１”となっている。
【００３７】
制御部２４は、位置取得部２２によって取得された自端末位置と交差点エリアの中心位置との距離が、所定の範囲内であれば、制御部２４は、ＤＨＴへの参加を判断する。制御部２４は、位置取得部２２によって取得された自端末位置と交差点エリアの中心位置との距離が、所定の範囲より大きくなると、ＤＨＴからの離脱を判断する。
【００３８】
また、制御部２４は、位置取得部２２によって取得された自端末位置と分割エリアの中心位置との距離に基づいて、自端末が所属するグループ（自端末が存在する分割エリア）を判断する。また、制御部２４は、所属するグループの変化により、グループ間の移動を判断する。
【００３９】
次に、ルーティングテーブル及びルーティング情報について説明する。
【００４０】
まず、参考例として、グループが存在しない場合のルーティングテーブルの具体例を図９に示す。ルーティングテーブルは、自端末が直接通信可能なノードから提供されたルーティング情報に基づいて生成され、自端末が直接通信可能なノードのノードＩＤ及びビットパターンから構成される。
【００４１】
次に、参考例として、グループが存在しない場合のルーティング情報の具体例について図１０を用いて説明する。ルーティング情報は送信先・送信元ノードＩＤとビットパターンによって構成されている。ビットパターンは、ルーティングテーブルの中でノードＩＤが送信先ノードＩＤでないビットパターンをＯＲ演算すると共に、送信元ノードＩＤによって決定されたビットを更に１にしたビット列である。
【００４２】
上記図１０の例では、ノード４がノード５に対してルーティング情報を送信する。その場合、ノード４のルーティングテーブルの中で、ノードＩＤが５以外のビットパターンをＯＲ演算し、さらに送信元ノードＩＤが４なので右から４ビット目に１を書き込んだものをビットパターンとする。作成したビットパターンに送信先ノードＩＤ（＝５）と送信元ノードＩＤ（＝４）を付加して、ノード５に対して送信する。
【００４３】
ビットパターンの具体例にはシンプルなものを用いたが、これ以外にもＢｌｏｏｍ  Ｆｉｌｔｅｒ（ＢＦ）を用いる手法などが考えられる。
【００４４】
次に、本実施の形態におけるルーティングテーブル（グループ化したときのルーティングテーブル）の具体例について説明する。グループ内ルーティングテーブル及びグループ間ルーティングテーブルの具体例を図１１に示す。各ノードはグループ間とグループ内の２つのルーティングテーブルを保持する。グループ間ルーティングテーブルは同一グループのノードの間では共通であり、隣接するグループとのデータのやりとりに用いる。グループ間ルーティングテーブルの行数は隣接するグループの数と一致し（グループＡやＣは１、グループＢは２）、各行は隣接するグループの位置情報とビットパターンという項目を持つ。隣接グループ位置情報は、上記図１１の例ではＡ、Ｂ、Ｃと書かれているが、実際には（ｘ座標、ｙ座標、範囲）である。以下、グループ位置情報の表記については同様である。グループ間ルーティングテーブルのビットパターンについては後述する。
【００４５】
グループ内ルーティングテーブルは同一グループ内でのデータのやりとりに用いる。同一グループの全ノードのＩＤがグループ内ルーティングテーブルに登録される。
【００４６】
グループ内ルーティングテーブル記憶部２８は、上述したように、同一グループに所属する全ノードのノードＩＤからなるグループ内ルーティングテーブルを記憶する。グループ間ルーティングテーブル記憶部３２は、隣接グループ毎の隣接グループ位置情報及びビットパターンからなるグループ間ルーティングテーブルを記憶する。また、グループ間ルーティングテーブル記憶部３２に記憶されているグループ間ルーティングテーブルには、隣接グループ毎に、グループ間ルーティング情報と共に、更新時刻が格納されている。
【００４７】
また、本実施の形態におけるグループ間ルーティング情報の具体例について図１２を用いて説明する。
【００４８】
グループ間ルーティング情報は、送信先グループの位置情報と送信元グループの位置情報とビットパターンとによって構成される。
【００４９】
上記図１２のようにグループＢのノードからグループＡのノードへグループ間ルーティング情報を送信する例を考える。送信先グループ位置情報はＡで送信元グループ位置情報はＢである。ビットパターンは、グループＢで保持するグループ間ルーティングテーブルの中で隣接グループ位置情報がＡではないビットパターンと自グループのグループＩＤ（自グループ内の各ノードＩＤをＯＲ演算したもの）とをＯＲ演算して構成する。
【００５０】
このとき、グループ間ルーティング情報は、同一グループのノードの間で共通であるため、グループ間ルーティング情報を送信するときに、１対１で送信する以外にも、１対多のブロードキャストでルーティング情報を伝える手法も考えられる。
【００５１】
このように、グループ間ルーティングテーブル記憶部３２は、上述したように、隣接グループ位置情報と、当該隣接グループを経由してルーティング可能なグループのグループＩＤのＯＲ演算により求まるビットパターンとからなるグループ間ルーティングテーブルを記憶する。
【００５２】
また、ルーティング情報生成部３８は、図１３に示すように、グループ間ルーティングテーブル記憶部３２に記憶されているグループ間ルーティングテーブルに基づいて、送信先グループ位置情報以外の隣接グループ位置情報のビットパターンを抽出するルーティング情報抽出部３８Ａと、ルーティング情報抽出部３８Ａによって抽出した各隣接グループ位置情報のビットパターンと、グループ内ルーティングテーブル記憶部２８に記憶されているグループ内ルーティングテーブルから得られる自グループ内の各ノードＩＤのビットパターンとをＯＲ演算して、得られたビットパターン、送信先グループ位置情報、及び送信元グループ位置情報（自グループのグループ位置情報）からなるグループ間ルーティング情報を生成してデータ通信部１４に出力するＯＲ演算部３８Ｂとを備えている。グループ間ルーティング情報が入力されたデータ通信部１４は、隣接する送信先グループに対して、グループ間ルーティング情報を送信する。
【００５３】
また、グループ間ルーティングテーブル管理部３０は、データ通信部１４により他の移動端末１０からブロードキャストされたグループ間ルーティング情報を受信すると、グループ間ルーティングテーブル記憶部３２に記憶されているグループ間ルーティングテーブルを更新する。
【００５４】
また、本実施の形態におけるグループ内ルーティング情報の具体例について、図１４を用いて説明する。
【００５５】
グループ内ルーティングテーブルを維持するためのグループ内ルーティング情報は、自端末が所属するグループの位置情報と自端末のノードＩＤとから構成され、グループ内のノードに対してブロードキャストされる。例えば、ノード３ならば、グループＡ内のノード１、２に対してグループ位置情報＝Ａ、ノードＩＤ＝３というグループ内ルーティング情報が送信されるようにブロードキャストされる。
【００５６】
また、ノードがグループ間を移動する場合は、移動前と移動後のグループそれぞれに、新たに所属するグループ位置情報と自ノードＩＤをブロードキャストすることで、グループ内ルーティングテーブルを更新させる。例えば、ノード５がグループＢからＣへ移動する場合、ノード４、６、７、８、９に対して、グループ位置情報＝Ｃ、ノードＩＤ＝５というグループ内ルーティング情報が送信されるようにブロードキャストされる。グループ内ルーティング情報を受け取ることで、ノード４、６ではグループ内ルーティングテーブルからノード５の情報が削除され、ノード７、８、９では、グループ内ルーティングテーブルにノード５の情報が追加される。
【００５７】
このように、制御部２４がグループ間の移動を判断すると、ルーティング情報生成部３８は、移動後のグループ位置情報と自ノードＩＤとからなるグループ内ルーティング情報を生成し、データ通信部１４によりブロードキャストする。このとき、グループ内ルーティングテーブル管理部２６は、移動後のグループ内の移動端末１０から、データ通信部１４によりグループ内ルーティングテーブルを受信し、グループ内ルーティングテーブル記憶部２８に格納する。また、グループ間ルーティングテーブル管理部３０は、移動後のグループ内の移動端末１０から、データ通信部１４によりグループ間ルーティングテーブルを受信し、グループ間ルーティングテーブル記憶部３２に格納する。
【００５８】
また、制御部２４がＤＨＴへの新たな参加を判断した場合には、グループ内ルーティングテーブル管理部２６は、所属するグループ内の移動端末１０から、データ通信部１４によりグループ内ルーティングテーブルを受信し、グループ内ルーティングテーブル記憶部２８に格納する。また、グループ間ルーティングテーブル管理部３０は、所属するグループ内の移動端末１０から、データ通信部１４によりグループ間ルーティングテーブルを受信し、グループ間ルーティングテーブル記憶部３２に格納する。ルーティング情報生成部３８は、所属するグループ位置情報と自ノードＩＤとからなるグループ内ルーティング情報を生成し、データ通信部１４によりブロードキャストする。
【００５９】
また、制御部２４がＤＨＴからの離脱を判断した場合には、ルーティング情報生成部３８は、離脱後のグループ位置情報（＝ＮＵＬＬ）と自ノードＩＤとからなるグループ内ルーティング情報を生成し、データ通信部１４によりブロードキャストする。このとき、グループ内ルーティングテーブル管理部２６は、グループ内ルーティングテーブル記憶部２８の内容を消去する。また、グループ間ルーティングテーブル管理部３０は、グループ間ルーティングテーブル記憶部３２の内容を消去する。
【００６０】
次に、グループ間ルーティング情報の交換方法について説明する。
【００６１】
本実施の形態では、図１５に示すように、位置情報を考慮して、ルーティング可能なグループのグループＩＤを足し合わせたビットパターンを、隣接グループと交換することにより、ＤＨＴのデータのルーティングを可能とする。
【００６２】
例えば、図１６のような状況を考える。グループＤに存在するノードがデータを管理する場合、グループＣまたはグループＥのノードに当該データを転送するか、自グループで管理するかが判断できれば、どのグループでデータを管理するか詳細に知る必要はない。そのため、グループＤのノードは、グループＤ内のノードＩＤとグループＣのＩＤ、それ以外のグループのＩＤのＯＲ（Ａ∪Ｂ∪Ｅ∪Ｆ∪Ｇ∪Ｈ∪Ｉ）を所有していれば、データのルーティングが可能である。
【００６３】
そこで、ルーティング情報生成部３８は、隣接グループＸに、グループ間ルーティング情報を送信するときには、ルーティング情報抽出部３８Ａによって、グループ間ルーティングテーブルの中で、隣接グループＸ以外の隣接グループに対するビットパターンを抽出し、ＯＲ演算部３８Ｂによって、抽出したビットパターンと、自グループＩＤのビットパターンとのＯＲ演算を行い、それを含むグループ間ルーティング情報をデータ通信部１４により隣接グループＸに送信する。
【００６４】
また、各グループが任意のタイミングで隣接グループにグループ間ルーティング情報を送信する場合、更新される直前にグループ間ルーティング情報を転送してしまい更新が反映されなかったり、最新の状態を保つために多くの通信を行ってしまったりする可能性がある。
【００６５】
そこで、情報保持エリア内のグループ間ルーティングテーブルの更新を順序付けて、隣接グループからグループ間ルーティング情報を受信したことを確認して、他の隣接グループにグループ間ルーティング情報を送信することで、通信を抑制しつつルーティングテーブルを更新の状態に保つことができる。
【００６６】
エリア内のグループの更新順序はあらかじめ決まっており、更新順序の決め方は全グループに対して個別に決定（例えば、図１７に示すように、Ｃ−＞Ｄ−＞Ｅ−＞Ｄ−＞Ｃと繰り返し更新）する。本実施の形態では、エリア端のグループ（上記図１７参照）から、エリア中心のグループに向かって順に更新し、エリア中心のグループでの更新後、エリア端のグループに向かって順に更新していく場合を例に説明する。
【００６７】
地図データベース２０には、各分割エリアに対するルーティング情報送信条件情報を記憶している。分割エリアＸに対するルーティング情報送信条件情報は、分割エリアＸの隣接グループ毎に、当該隣接グループを送信先とするグループ間ルーティング情報を送信するために、どの隣接グループからのグループ間ルーティング情報が更新される必要があるかを規定している。
【００６８】
本実施の形態の例では、地図データベース２０に記憶されている各分割エリアＸについて、分割エリアＸよりエリア中心側に隣接する隣接グループを送信先とする場合に対して、分割エリアＸよりエリア中心と反対側に隣接する隣接グループが、更新される必要があるグループ間ルーティング情報の送信元として、ルーティング情報送信条件に規定されている。また、エリア端のグループに相当する分割エリアＸに対しては、ルーティング情報送信条件は規定されていない。また、エリア中心のグループに相当する分割エリアＸに対しては、送信先の隣接グループ以外の全ての隣接グループが、更新される必要があるグループ間ルーティング情報の送信元として、ルーティング情報送信条件に規定されている。
【００６９】
送信条件取得部２５は、制御部２４より自端末が存在する分割エリアを取得し、取得した当該分割エリアについて記憶されているルーティング情報送信条件情報を、地図データベース２０から取得し、グループ間ルーティングテーブル管理部３０へ出力する。
【００７０】
グループ間ルーティングテーブル管理部３０は、ルーティング情報送信条件情報に基づいて、グループ間ルーティングテーブルの各隣接グループのグループ間ルーティング情報の更新状況に従って、各隣接グループについてルーティング情報送信条件を満たすか否かを判断し、ルーティング情報送信条件を満たしたと判定された隣接グループを送信先とするグループ間ルーティング情報を生成するように、ルーティング情報生成部３８に指示（送信先のグループＩＤ）を出力する。なお、グループ間ルーティングテーブルの各隣接グループのグループ間ルーティング情報の更新状況については、グループ間ルーティングテーブルの更新時刻の変化に基づいて判断すればよい。
【００７１】
ルーティング情報生成部３８は、グループ間ルーティングテーブル管理部３０から出力された送信先のグループＩＤに基づいて、当該送信先に対するグループ間ルーティング情報を生成し、データ通信部１４により送信する。
【００７２】
これによって、各グループのノードは、対応する各分割エリアのルーティング情報送信条件情報によって定められた隣接グループからグループ間ルーティング情報を受け取るまで、グループ間ルーティング情報の送信を行わない。本実施の形態の例では、図１８から図２２のように、エリア端のグループから、エリア中心のグループに向かって、順にグループ間ルーティング情報が送信され、各グループで保持するグループ間ルーティングテーブルが更新される。エリア中心のグループで、グループ間ルーティングテーブルが更新された後には、エリア中心のグループからエリア端のグループに向かって、順にグループ間ルーティング情報が送信され、各グループで保持するグループ間ルーティングテーブルが更新される。
【００７３】
なお、図１８は初期状態を示し、図１９は、エリア端のグループによってグループ間ルーティング情報の送信が行われた状態を示す。また、図２０は、エリア中心のグループへグループ間ルーティング情報が送信された状態を示し、図２１は、エリア中心のグループによってグループ間ルーティング情報の送信が行われた状態を示し、図２２は、エリア端のグループへグループ間ルーティング情報が送信された状態を示す。
【００７４】
上記図１８〜図２２の例では、エリア端のグループから順に行われるグループ間ルーティング情報の送信が、各エリア端のグループで同期して行われる場合を例に説明したが、これに限定されるものではない。例えば、図２３（Ａ）に示すように、グループＥからエリア中心のグループＣへのグループ間ルーティング情報の送信が遅延してもよい。この場合には、図２３（Ｂ）に示すように、エリア中心のグループＣからグループＥに送信するためのグループ間ルーティング情報が全て更新されているため、エリア中心のグループＣからグループＥへグループ間ルーティング情報が送信される。その後に、図２３（Ｄ）に示すように、グループＥからエリア中心のグループＣへグループ間ルーティング情報が送信されると、図２３（Ｃ）に示すように、エリア中心のグループＣからグループＡ，Ｂ，Ｄに送信するためのグループ間ルーティング情報が全て更新されたことになるため、エリア中心のグループＣからグループＡ，Ｂ，Ｄへグループ間ルーティング情報が送信される。
【００７５】
上記のようなグループ間ルーティング情報の交換手法を用いることで、隣接グループに対して自グループを経由することで到着可能（ルーティング可能）な全グループＩＤを伝えることができる。つまり、各隣接グループとグループ間ルーティング情報のビットパターンを交換するだけで、情報保持エリア全体のグループ情報を入手することができる。
【００７６】
また、ＤＨＴへの参加中に、データ通信部１４によりエリアデータを受信すると、データ管理部３４は、エリアデータのデータＩＤと、グループ内ルーティングテーブル記憶部２８に記憶されているグループ内ルーティングテーブルから得られる同一グループの各ノードＩＤと、グループ間ルーティングテーブル記憶部３２に記憶されているグループ間ルーティングテーブルから得られる各隣接グループのビットパターン（ルーティング可能なグループのグループＩＤを足し合わせたもの）とに基づいて、エリアデータを割り当てるグループを決定し、決定されたグループが自グループである場合には、エリアデータを割り当てるノードＩＤを決定する。
【００７７】
以下に、エリアデータを割り当てるノードが所属するグループの決定方法について説明する。
【００７８】
データ管理部３４は、図２４に示すグループ決定部５０を備えており、グループ決定部５０は、２階層のＤＨＴに従って、どのグループでデータを管理するか決定する。このときに、グループＩＤを、グループ内のノードＩＤのＯＲ演算によって構成することで、グループとノードのＩＤの間で関連付けを行う。
【００７９】
まず、同一グループ内の各ノードに対する関数ｆ（ｘ）により、同一グループ内のノードＩＤを引数としてビットパターンに変換して出力する。例えば、関数ｆ（ｘ）は、ハッシュ関数を用いて、ノードＩＤのハッシュ値を導き、そのハッシュ値を用いてビット列のどこか１ビットを１にしたビットパターンを出力する。もしくは、関数ｆ（ｘ）は、直接ノードＩＤから１にするビット数ビットの位置を決定する（例えば、ハッシュ値もしくはノードＩＤが３ならビットパターンの３ビット目を書き込む）ようにしてもよい。それ以外にも、関数ｆ（ｘ）は、ハッシュ関数から導かれたハッシュ値をそのままビットパターンとして出力してもよい。
【００８０】
次に、グループＩＤ生成部５２は、ＯＲ演算を用いて、各関数ｆ（ｘ）から出力されたビットパターン（ビット列）を足し合わせて、自グループのグループＩＤを示すビットパターンを生成する。ＯＲ演算による足し合わせを行う場合、関数ｆ（ｘ）で生成するビットパターンはハッシュ値よりも、ノードＩＤやノードＩＤのハッシュ値を用いてビットパターンのどこか１ビットに書き込む手法を用いることが好ましい。
【００８１】
また、関数ｈ（ｘ）により、データＩＤを引数としてランダムパターンを生成して出力する。例えば、関数ｈ（ｘ）で導かれるランダムパターンは、データＩＤのハッシュ値から導かれる数列である。具体的には、全てのビットの並び替えの順番が決定するまで、データＩＤからハッシュ値を生成し、まだ順番が決定していないビット数で割るという操作を繰り返してランダムパターンを生成する。
【００８２】
また、自グループ及び隣接グループの各々に対する関数ｇ（ｘ、ｙ）により、ランダムパターンを用いて、図２５に示すように、自グループのグループＩＤを示すビットパターン、及び各隣接グループのビットパターンのビットの並び替えを行い、並び替えられたビットパターンを各々出力する。
【００８３】
評価部５４は、関数ｇ（ｘ、ｙ）から出力されたビットパターンから、どのグループのビットパターンがエリアデータを管理するのに適しているのかを決定する評価関数を持ち、決定されたビットパターンのグループを出力する。例えば、上記図２５の例のように、ビットパターンを数値として評価して最も数値が大きいビットパターンのグループが、エリアデータが割り当てられるグループとして決定される。なお、隣接グループのビットパターンは、隣接グループを経由してルーティング可能なグループＩＤをＯＲ演算したものであるため、評価部５４によって出力されたグループが、隣接グループである場合には、隣接グループを経由してルーティング可能なグループの何れかが、エリアデータを管理するのに適しているグループとなる。
【００８４】
次に、エリアデータを割り当てるノードの決定方法について説明する。
【００８５】
データ管理部３４は、図２６に示すノード決定部６０を備えており、ノード決定部６０は、グループ決定部５０により決定されたグループが、自グループである場合に、自グループ内のどのノードでデータを管理するか決定する。
【００８６】
まず、同一グループ内の各ノードに対する関数ｆ（ｘ）により、グループ決定部５０と同様に、同一グループ内のノードＩＤを引数としてビットパターンに変換して出力する。
【００８７】
また、関数ｈ（ｘ）により、グループ決定部５０と同様に、データＩＤを引数としてランダムパターンを生成して出力する。
【００８８】
また、各ノードＩＤに対する関数ｇ（ｘ、ｙ）により、グループ決定部５０と同様に、関数ｈ（ｘ）から出力されたランダムパターンを用いて、グループＩＤを示すビットパターンのビットの並び替えを行い、並び替えられたビットパターンを出力する。
【００８９】
評価部６２は、各関数ｇ（ｘ、ｙ）から出力されたビットパターンから、どのノードがエリアデータを管理するのに適しているのかを決定する評価関数を持ち、決定されたノードＩＤを出力する。例えば、ビットパターンを数値として評価して最も数値が大きいビットパターンに対応するノードＩＤが、エリアデータが割り当てられるノードのノードＩＤとして決定される。
【００９０】
データ管理部３４は、エリアデータを受信すると、グループ決定部５０及びノード決定部６０により、エリアデータを割り当てるグループ又はグループ及びノードＩＤを決定し、決定されたノードＩＤが、自ノードＩＤである場合には、受信したエリアデータを、ＤＨＴデータ記憶部３６に格納する。データ管理部３４は、決定されたグループが、隣接グループである場合には、決定された隣接グループに対して、データ通信部１４によりエリアデータを転送する。また、データ管理部３４は、決定されたグループが、自グループであり、かつ、決定されたノードＩＤが、自ノードＩＤでない場合には、決定されたノードＩＤが示す自グループ内のノードに対して、データ通信部１４によりエリアデータを転送する。
【００９１】
次に、本実施の形態に係る移動端末１０の作用について説明する。移動端末１０を搭載した車両の走行中に、ＤＨＴへ参加していない場合には、コンピュータ１６において、図２７に示す参加時処理ルーチンが実行される。
【００９２】
まず、ステップ１００において、ＤＨＴへの参加を示す変数ＡＩｎに、初期値Ｆａｌｓｅを設定し、ステップ１０２において、ＧＰＳ１２から自車両の位置を取得すると共に、自車両の直近にある交差点エリアの位置情報（予め求められた情報保持エリアの中心位置及び範囲）及び当該交差点エリアの分割エリアの位置情報（予め求められたグループの中心位置及び範囲）を、地図データベース２０から取得する。
【００９３】
そして、ステップ１０４において、上記ステップ１０２で取得した自車両の位置と交差点エリアの中心位置との距離とが、交差点エリアの範囲内であるか否かに基づいて、交差点エリア内に存在するか否かを判定し、交差点エリア内に存在する場合には、ＡＩｎにＴｒｕｅを設定し、一方、交差点エリア内に存在しない場合には、ＡＩｎにＦａｌｓｅを設定する。
【００９４】
次のステップ１０６では、変数ＡＩｎがＴｒｕｅであるか否かを判定する。変数ＡＩｎがＦａｌｓｅであれば、上記ステップ１０２へ戻るが、変数ＡＩｎがＴｒｕｅであれば、ＤＨＴへ参加すると判断し、ステップ１０８へ進む。
【００９５】
ステップ１０８では、上記ステップ１０２で取得した自車両の位置と各分割エリアの中心位置との距離とに基づいて、自端末が所属するグループを特定し、同一グループ内に存在する周辺の移動端末１０とデータ通信を行い、グループ内ルーティングテーブル及びグループ間ルーティングテーブルを、当該周辺の移動端末１０から受信して取得し、グループ内ルーティングテーブル記憶部２８及びグループ間ルーティングテーブル記憶部３２に格納する。
【００９６】
そして、ステップ１１０において、上記ステップ１０８で特定した自端末が所属するグループの位置情報をＧ＿Ｌｏｃに設定し、自端末のノードＩＤをＮ＿ＩＤに設定する。次のステップ１１２では、Ｇ＿Ｌｏｃのグループ内の移動端末１０に送信するように、グループ内ルーティング情報（Ｎ＿ＩＤとＧ＿Ｌｏｃ）をブロードキャストし、参加中処理へ移行する。
【００９７】
次に、コンピュータ１６によって実行される参加中処理ルーチンについて図２８を用いて説明する。
【００９８】
ステップ１２０において、ＧＰＳ１２から自車両の位置を取得すると共に、自車両の直近にある交差点エリアの位置情報及び当該交差点エリアの各分割エリアの位置情報を、地図データベース２０から取得する。
【００９９】
そして、ステップ１２２において、上記ステップ１２０で取得した自車両の位置と交差点エリアの中心位置との距離が、交差点エリアの範囲内であるか否かに基づいて、交差点エリア内に存在するか否かを判定し、交差点エリア内に存在する場合には、ＡＩｎにＴｒｕｅを設定し、一方、交差点エリア内に存在しない場合には、ＡＩｎにＦａｌｓｅを設定する。また、上記ステップ１２０で取得した自車両の位置と各分割エリアの中心位置との距離とに基づいて、自端末が所属するグループを特定し、特定した自端末が所属するグループの位置情報をＧ＿Ｌｏｃに設定する。
【０１００】
次のステップ１２４では、Ｇ＿Ｌｏｃが変化したか否かを判定する。Ｇ＿Ｌｏｃが変化していない場合には、上記ステップ１２０へ戻るが、Ｇ＿Ｌｏｃが変化した場合には、グループ間移動があったと判断し、ステップ１２６へ移行する。
【０１０１】
ステップ１２６では、変化前のＧ＿Ｌｏｃを、Ｇ＿Ｌｏｃ０に設定する。そして、ステップ１２８において、上記ステップ１２２で設定したＧ＿Ｌｏｃ及び上記ステップ１２６で設定したＧ＿Ｌｏｃ０を用いて、グループ間移動時処理を行う。
【０１０２】
次のステップ１３０では、変数ＡＩｎが、Ｆａｌｓｅであるか否かを判定する。ＡＩｎがＴｒｕｅであれば、ＤＨＴへ参加中であると判断し、上記ステップ１２０へ戻る。一方、ＡＩｎがＦａｌｓｅであれば、ＤＨＴから離脱したと判断し、ステップ１３２において、グループ内ルーティングテーブル記憶部２８及びグループ間ルーティングテーブル記憶部３２の内容をクリアし、参加時処理へ移行する。
【０１０３】
このように、参加中処理ルーチンが実行されることにより、自端末の位置情報と交差点エリア位置情報とグループ位置情報からＡＩｎとＧ＿Ｌｏｃが周期的に更新される。また、自端末のノードがグループ間を移動することでＧ＿Ｌｏｃが変化すると、グループ間移動時の処理を行う。ＡＩｎがＦａｌｓｅの場合、エリアから離脱するため、現在所持しているグループルーティングテーブルとグループ内ルーティングテーブルがクリアされる。
【０１０４】
上記ステップ１２８は、図２９に示すグループ間移動時処理ルーチンにより実現される。
【０１０５】
ステップ１４０において、グループ内ルーティングテーブル記憶部２８及びグループ間ルーティングテーブル記憶部３２の内容をクリアする。そして、ステップ１４２において、変数ＡＩｎが、Ｔｒｕｅであるか否かを判定する。ＡＩｎがＴｒｕｅであれば、交差点エリア内に存在する（ＤＨＴへ参加中である）と判断し、ステップ１４４において、Ｇ＿Ｌｏｃのグループ内に存在する周辺の移動端末１０とデータ通信を行い、グループ内ルーティングテーブル及びグループ間ルーティングテーブルを、当該周辺の移動端末１０から受信して取得し、グループ内ルーティングテーブル記憶部２８及びグループ間ルーティングテーブル記憶部３２に格納する。ステップ１４６では、Ｇ＿Ｌｏｃのグループ内の移動端末１０及びＧ＿Ｌｏｃ０のグループ内の移動端末１０に送信するように、グループ内ルーティング情報（Ｎ＿ＩＤとＧ＿Ｌｏｃ）をブロードキャストする。
【０１０６】
一方、ＡＩｎがＦａｌｓｅであれば、自端末のノードがエリア外に存在する（ＤＨＴから離脱した）と判断し、ステップ１４８において、Ｇ＿Ｌｏｃ０のグループ内の移動端末１０に送信するように、グループ内ルーティング情報（Ｎ＿ＩＤとＧ＿Ｌｏｃ（＝ＮＵＬＬ））をブロードキャストする。
【０１０７】
そして、ステップ１５０では、自端末のＤＨＴデータ記憶部３６に格納されているエリアデータのデータＩＤ（ｎ個）を、Ｄａｔａ＿ＩＤ[ｎ]に設定する。ステップ１５２では、上記ステップ１５０で設定されたＤａｔａ＿ＩＤ[ｎ]を用いて、データ転送処理を行って、グループ間移動時処理ルーチンを終了する。データ転送処理では、現在自端末が管理しているエリアデータの管理者が変更されていないか判断し、変更されている場合には、当該エリアデータを転送し、また、交差点エリアの外に出る場合には全エリアデータを転送する。
【０１０８】
上記ステップ１５２の処理は、図３０に示すデータ転送処理ルーチンにより実現される。
【０１０９】
まず、ステップ１６０では、グループ内ルーティングテーブル記憶部２８に記憶されている、現在所属するグループ内の全ノードＩＤに基づいて、グループＩＤ（ビットパターン）を生成し、Ｇ＿ＩＤに設定する。そして、ステップ１６２において、自端末が保持するエリアデータを識別するための変数ｉを初期値１に設定する。
【０１１０】
ステップ１６４では、グループ間ルーティングテーブル記憶部３２に記憶されている各隣接グループに対するグループ間ルーティング情報のビットパターンと、Ｇ＿ＩＤと、ｉ番目のエリアデータのデータＩＤ（Ｄａｔａ＿ＩＤ[ｉ]）とに基づいて、ｉ番目のエリアデータが割り当てられるグループを決定する。決定されたグループが自グループである場合には、変数Ｇｏ＿ｊにＴｒｕｅを設定し、一方、決定されたグループが自グループでない場合には、変数Ｇｏ＿ｊにＦａｌｓｅを設定する。
【０１１１】
そして、ステップ１６６において、変数Ｇｏ＿ｊがＴｒｕｅであるか否かを判定する。Ｇｏ＿ｊがＦａｌｓｅである場合、自ノードが所属するグループに割り当てられないと判断し、ステップ１６８において、上記ステップ１６４で決定された隣接グループに所属する移動端末１０へ、ｉ番目のエリアデータを転送し、ステップ１７６へ移行する。
【０１１２】
一方、Ｇｏ＿ｊがＴｒｕｅである場合、自ノードが所属するグループに割り当てられると判断し、ステップ１７０において、グループ内ルーティングテーブル記憶部２８に記憶されている各ノードＩＤと、Ｎ＿ＩＤと、ｉ番目のエリアデータのデータＩＤ（Ｄａｔａ＿ＩＤ[ｉ]）とに基づいて、ｉ番目のエリアデータが割り当てられるノードを決定する。決定されたノードが自ノードである場合には、変数Ｇｉ＿ｊにＴｒｕｅを設定し、一方、決定されたノードが自ノードでない場合には、変数Ｇｉ＿ｊにＦａｌｓｅを設定する。
【０１１３】
そして、ステップ１７２において、変数Ｇｉ＿ｊがＴｒｕｅであるか否かを判定する。Ｇｉ＿ｊがＦａｌｓｅである場合、自ノードに割り当てられないと判断し、ステップ１７６において、上記ステップ１７０で決定されたノードの移動端末１０へ、ｉ番目のエリアデータを転送し、ステップ１７６へ移行する。
【０１１４】
一方、Ｇｉ＿ｊがＴｒｕｅである場合、ｉ番目のエリアデータを、ＤＨＴデータ記憶部３６にそのまま格納しておき、ステップ１７６へ移行する。
【０１１５】
ステップ１７６では、変数ｉを１インクリメントする。そして、ステップ１７８において、変数ｉが、保持しているエリアデータの数を示すｎ以下であるか否かを判定し、変数ｉがｎ以下であれば、上記ステップ１６４へ戻るが、一方、変数ｉがｎより大きい場合には、データ転送処理ルーチンを終了する。
【０１１６】
次に、データ通信部１４によって他の移動端末１０からグループ内ルーティング情報を受信すると、コンピュータ１６によって、図３１に示すグループ内ルーティング情報受信時処理ルーチンが実行される。
【０１１７】
ステップ１８０において、受信したグループ内ルーティング情報から、ノード（移動端末）のＩＤ及びグループ位置情報を取り出し、取り出したノードＩＤをＲＴ＿Ｎ＿ＩＤに設定し、取り出したグループ位置情報をＲＴ＿Ｇ＿Ｌｏｃに設定する。
【０１１８】
次のステップ１８２では、自端末が所属するグループの位置情報をＧ＿Ｌｏｃに設定する。ステップ１８４では、ＲＴ＿Ｇ＿ＬｏｃとＧ＿Ｌｏｃとが一致するか否かを判定する。ＲＴ＿Ｇ＿ＬｏｃとＧ＿Ｌｏｃとが一致する場合には、ステップ１８６において、グループ内ルーティングテーブル記憶部２８に記憶されているグループ内ルーティングテーブルに、ＲＴ＿Ｎ＿ＩＤが登録されていなければ、ＲＴ＿Ｎ＿ＩＤを追加登録して、グループ内ルーティング情報受信時処理ルーチンを終了する。一方、ＲＴ＿Ｇ＿ＬｏｃとＧ＿Ｌｏｃとが一致しない場合には、ステップ１８８において、グループ内ルーティングテーブル記憶部２８に記憶されているグループ内ルーティングテーブルに、ＲＴ＿Ｎ＿ＩＤが登録されていれば、ＲＴ＿Ｎ＿ＩＤを削除して、グループ内ルーティング情報受信時処理ルーチンを終了する。
【０１１９】
また、移動端末１０が、データ通信部１４によって他の移動端末１０から送信されたエリアデータを受信した場合には、コンピュータ１６によって、図３２に示すデータ受信時処理ルーチンを実行する。
【０１２０】
まず、ステップ２００において、受信したデータから、データのＩＤを取り出し、Ｄａｔａ［１］に、取り出したデータＩＤを設定する。次のステップ２０２では、上記ステップ２００で設定したＤａｔａ［１］を用いて、上記図３０で説明したデータ転送処理ルーチンを実行し、データ受信時処理ルーチンを終了する。これによって、エリアデータを自ノードで保持するか、他のノードに転送するかが判断される。
【０１２１】
また、データ通信部１４によって他の移動端末１０からグループ間ルーティング情報を受信すると、コンピュータ１６によって、図３３に示すグループ間ルーティング情報受信時処理ルーチンが実行される。
【０１２２】
ステップ２１０において、受信したグループ間ルーティング情報から、送信先グループの位置情報、送信元グループの位置情報、及びビットパターンを取り出し、取り出した送信元グループの位置情報をＲＴ＿Ｇ＿Ｓｒｃに設定し、取り出した送信先グループの位置情報をＲＴ＿Ｇ＿Ｄｓｔに設定し、取り出したビットパターンを、ＲＴ＿Ｂｉｔに設定する。
【０１２３】
次のステップ２１２では、自端末が所属するグループの位置情報をＧ＿Ｌｏｃに設定すると共に、グループ間ルーティングテーブルに基づいてｍ個の隣接グループの中心座標をＡ＿Ｌｏｃ［ｍ］に設定する。ステップ２１４では、ＲＴ＿Ｇ＿ＤｓｔとＧ＿Ｌｏｃとが一致するか否かを判定する。ＲＴ＿Ｇ＿ＤｓｔとＧ＿Ｌｏｃとが一致する場合には、ステップ２１６において、グループ間ルーティングテーブル記憶部３２に記憶されているグループ間ルーティングテーブルの隣接グループ位置情報がＲＴ＿Ｇ＿Ｓｒｃである行のビットパターンをＲＴ＿Ｂｉｔで更新し、あるいは隣接グループ位置情報としてＲＴ＿Ｇ＿Ｓｒｃが登録されていなければ、隣接グループ位置情報がＲＴ＿Ｇ＿Ｓｒｃであり、ビットパターンがＲＴ＿Ｂｉｔである行を追加登録する。
【０１２４】
次のステップ２１８では、Ｇ＿Ｌｏｃを用いて、自端末が所属するグループに対するルーティング情報送信条件情報を、地図データベース２０から取得する。そして、ステップ２２０では、自端末が所属するグループの隣接グループを識別するための変数ｉを初期値１に設定する。
【０１２５】
ステップ２２２において、上記ステップ２１８で取得したルーティング情報送信条件情報に基づいて、Ａ＿Ｌｏｃ[ｉ]を送信先とするグループ間ルーティング情報を生成するために必要とされる、隣接グループからのグループ間ルーティング情報が全て更新されているか否かを判定する。Ａ＿Ｌｏｃ[ｉ]を送信先とするグループ間ルーティング情報を生成するために必要とされる、隣接グループからのグループ間ルーティング情報が少なくとも１つ更新されていない場合には、Ａ＿Ｌｏｃ[ｉ]を送信先とするルーティング情報送信条件を満たさないと判断し、ステップ２２６へ移行する。一方、Ａ＿Ｌｏｃ[ｉ]を送信先とするグループ間ルーティング情報を生成するために必要とされる、隣接グループからのグループ間ルーティング情報が全て更新されていた場合には、Ａ＿Ｌｏｃ[ｉ]を送信先とするルーティング情報送信条件を満たすと判断し、ステップ２２４において、Ａ＿Ｌｏｃ[ｉ]を送信先とするグループ間ルーティング情報を生成して送信する。
【０１２６】
ステップ２２６では、変数ｉを１インクリメントし、ステップ２２８において、変数ｉが、隣接グループの数を示すｍ以下であるか否かを判定する。変数ｉが、ｍ以下である場合には、上記ステップ２２２へ戻る。一方、変数ｉが、ｍより大きい場合には、グループ間ルーティング情報受信時処理ルーチンを終了する。
【０１２７】
また、上記ステップ２１４で、ＲＴ＿Ｇ＿ＤｓｔとＧ＿Ｌｏｃとが一致しない場合には、グループ間ルーティング情報受信時処理ルーチンを終了する。
【０１２８】
また、移動端末１０がＤＨＴへ参加しているときであって、エリア端のグループに所属している場合には、コンピュータ１６において、図３４に示すエリア端グループ送信処理ルーチンが実行される。
【０１２９】
ステップ２３０において、隣接グループを送信先とするグループ間ルーティング情報を生成して送信する。そして、ステップ２３２において、所定時間経過したか否かを判定し、所定時間が経過すると、上記ステップ２３０へ戻る。
【０１３０】
これによって、周期的に、エリア端のグループから、グループ間ルーティング情報が送信される。
【０１３１】
また、上記ステップ２２４及びステップ２３０は、図３５に示すグループ間ルーティング情報送信処理ルーチンによって実現される。
【０１３２】
まず、ステップ２４０において、現在自端末が所属するグループの位置情報をＧ＿Ｌｏｃに設定する。また、グループ間ルーティング情報の送信先となる隣接するグループの位置情報（中心座標）をＡ＿Ｌｏｃに設定する。同一グループ内の各ノードから送信されたデータに含まれる位置情報を用いて、同一グループのノードＩＤ及び現在の位置情報（ｎ個）をＧＮ＿Ｌｏｃ[ｎ]に設定する。
【０１３３】
そして、ステップ２４２において、自グループのノードの位置情報ＧＮ＿Ｌｏｃの中で、隣接グループの位置情報Ａ＿Ｌｏｃに最も近いノードのノードＩＤを決定し、決定されたノードＩＤをＮｅａｒ＿ＩＤに設定する。
【０１３４】
次のステップ２４４では、Ｎｅａｒ＿ＩＤと自端末のノードＩＤを示すＮ＿ＩＤとが一致するか否かを判定する。Ｎｅａｒ＿ＩＤとＮ＿ＩＤとが一致する場合には、ステップ２４６において、グループ間ルーティング情報を生成する。このとき、送信元グループ位置情報をＧ＿Ｌｏｃとし、送信先グループ位置情報をＡ＿Ｌｏｃとする。また、グループ間ルーティングテーブルにおいて、グループ間ルーティング情報の隣接グループ位置情報がＡ＿Ｌｏｃでない全てのビットパターンと、自グループのグループＩＤを示すビットパターン（グループ内ルーティングテーブルから得られる自グループ内のノードＩＤのビットパターンを足し合わせたもの）とのＯＲ演算により構成されるビットパターンを、グループ間ルーティング情報のビットパターンとする。
【０１３５】
そして、ステップ２４８では、上記ステップ２４６で生成したグループ間ルーティング情報をデータ通信部１４により送信して、グループ間ルーティング情報送信処理ルーチンを終了する。
【０１３６】
また、上記ステップ２４４で、Ｎｅａｒ＿ＩＤとＮ＿ＩＤとが一致しない場合には、グループ間ルーティング情報送信処理ルーチンを終了する。
【０１３７】
これによって、自グループの中で、隣接グループＡ＿Ｌｏｃに最も近いノードによって、グループ間ルーティング情報が生成され、隣接グループＡ＿Ｌｏｃに送信される。
【０１３８】
上記のように、各種処理ルーチンが各移動端末１０で実行されると、交差点エリアに関連するエリアデータが、交差点エリア内の移動端末群で分散して記憶される。
【０１３９】
以上説明したように、第１の実施の形態に係る移動端末によれば、隣接する各グループを経由してルーティング可能なグループのグループＩＤのビットパターンの各々と、自端末が所属するグループのグループＩＤのビットパターンとのＯＲ演算により得られるビットパターンを表わすグループ間ルーティング情報を生成して、隣接する各グループとの間でグループ間ルーティング情報を送受信することにより、ルーティング情報の更新の遅延を抑制すると共に、ルーティング情報を維持するための通信負荷の増大を抑制することができる。
【０１４０】
また、各グループはデータを転送するときに目的までの正確な経路を知る必要はなく、隣接するグループの中でどれに転送すればいいのかがわかれば良い。そこで、各ノードは、隣接するグループのノードに対して、自身のグループを経由することで到達可能な全グループ情報を転送する。隣接グループの移動体とルーティング情報を交換するだけでエリア全域のグループ情報を把握でき、マルチホップ通信によるルーティングテーブルの維持が不要になるため、ルーティングテーブルを維持するための通信を効率化、抑制できる。
【０１４１】
また、位置情報を用いて情報保持エリアを分割して、ノードのグループを設定し、グループ間で、グループ間ルーティングテーブルの更新を行うことで、ルーティングのループを回避することができる。
【０１４２】
また、各グループＩＤのビットパターンはグループ内のノードＩＤのビットパターンの足し合わせである。そのため、ノードを何個追加してもグループＩＤのビットパターンの通信量は増加しないため、ＤＨＴの全ノードＩＤを知る場合と比べて、データ通信量を抑えることができる。
【０１４３】
また、グループ内のノードＩＤを用いて生成されるグループＩＤのビットパターン及びデータＩＤに基づいて、エリアデータを割り当てるグループを決定すると共に、グループ内のノードＩＤのビットパターン及びデータＩＤに基づいて、エリアデータを割り当てるノードを決定することにより、移動端末のノードが所属するグループが切り替わっても、当該ノードにエリアデータが割り当てられる可能性があるため、移動端末のノードが所属するグループが切り替わる際のデータ通信負荷の増大を抑制することができる。
【０１４４】
次に、第２の実施の形態に係る移動端末について説明する。なお、第２の実施の形態に係る移動端末は、第１の実施の形態と同様の構成となるため、同一符号を付して説明を省略する。
【０１４５】
第２の実施の形態では、エリア内でのグループ間ルーティングテーブルの更新順序が第１の実施の形態と異なっている。
【０１４６】
図３６に示すように、方角を用いてルーティング情報送信条件が定められている。例えば、エリア南北方向端のグループ（図３７参照）から、南北方向に、エリア内でのグループ間ルーティングテーブルが順番に更新された後、エリア東西方向端のグループ（図３７参照）から、東西方向に、エリア内でのグループ間ルーティングテーブルが順番に更新されるように、各分割エリアに対するルーティング情報送信条件が定められている。また、南北方向にグループ間ルーティングテーブルを更新する場合、グループ間ルーティングテーブルの破壊を防ぐために、東西方向に隣接する隣接グループから受信したグループ間ルーティング情報を送信しないように、各分割エリアに対するルーティング情報送信条件が定められている。
【０１４７】
本実施の形態の例では、地図データベース２０に記憶されている各分割エリアＸについて、分割エリアＸより北側に隣接する隣接グループを送信先とする場合に対して、分割エリアＸより南側に隣接する隣接グループが、更新される必要があるグループ間ルーティング情報の送信元としてルーティング情報送信条件に規定されていると共に、東西方向に隣接する隣接グループから受信したグループ間ルーティング情報を送信しないようにルーティング情報送信条件に規定されている。また、分割エリアＸより南側に隣接する隣接グループを送信先とする場合に対して、分割エリアＸより北側に隣接する隣接グループが、更新される必要があるグループ間ルーティング情報の送信元としてルーティング情報送信条件に規定されていると共に、東西方向に隣接する隣接グループから受信したグループ間ルーティング情報を送信しないようにルーティング情報送信条件に規定されている。また、分割エリアＸより東側に隣接する隣接グループを送信先とする場合に対して、分割エリアＸより西側に隣接する隣接グループが、更新される必要があるグループ間ルーティング情報の送信元としてルーティング情報送信条件に規定されている。また、分割エリアＸより西側に隣接する隣接グループを送信先とする場合に対して、分割エリアＸより東側に隣接する隣接グループが、更新される必要があるグループ間ルーティング情報の送信元としてルーティング情報送信条件に規定されている。
【０１４８】
また、エリア南北方向端のグループに相当する分割エリアＸに対しては、南北方向に隣接する隣接グループを送信先とする場合に対してルーティング情報送信条件は規定されていないが、他の方向に隣接する隣接グループを送信先とする場合に対しては上記と同様のルーティング情報送信条件が規定されている。また、エリア東西方向端のグループに相当する分割エリアＸに対しては、東西方向に隣接する隣接グループを送信先とする場合に対して、南北方向に隣接する全ての隣接グループが、更新される必要があるグループ間ルーティング情報の送信元として、ルーティング情報送信条件に規定されており、南北方向に隣接する隣接グループを送信先とする場合に対して上記と同様のルーティング情報送信条件が規定されている。
【０１４９】
グループ間ルーティングテーブル管理部３０は、グループ間ルーティングテーブルの隣接グループ位置情報に基づいて、各隣接グループが位置する方角を求めると共に、ルーティング情報送信条件情報に基づいて、各方角に位置する隣接グループについて、グループ間ルーティングテーブルの更新状況に従ってルーティング情報送信条件を満たすか否かを判断し、ルーティング情報送信条件を満たしたと判定された隣接グループを送信先とするグループ間ルーティング情報を生成するように、ルーティング情報生成部３８に指示（送信先のグループＩＤ）を出力する。
【０１５０】
本実施の形態の例では、図３８に示すように、エリア南北方向端の各グループから、南北方向に、順にグループ間ルーティング情報が送信され、各グループで保持するグループ間ルーティングテーブルが南北方向に更新される。南北方向の全ての隣接グループからグループ間ルーティング情報を受信して、グループ間ルーティングテーブルが更新された後には、図３９に示すように、エリア東西方向端のグループから、東西方向に、順にグループ間ルーティング情報が送信され、各グループで保持するグループ間ルーティングテーブルが東西方向に更新される。所定時間経過後に、再び、図４０に示すように、エリア南北方向端の各グループから、南北方向に、順にグループ間ルーティング情報が送信され、各グループで保持するグループ間ルーティングテーブルが南北方向に更新される。このとき、東西方向に隣接する隣接グループから受信したグループ間ルーティング情報は、送信されるグループ間ルーティング情報に含まれない。
【０１５１】
移動端末１０がＤＨＴへ参加しているときであって、エリア南北方向端のグループに所属している場合に、コンピュータ１６は、上記図３４に示すエリア端グループ送信処理ルーチンと同様の処理ルーチンを実行し、周期的に、南北方向に隣接する隣接グループを送信先とするグループ間ルーティング情報を生成して送信する。
【０１５２】
なお、第２の実施の形態に係る移動端末の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１５３】
このように、エリア南北方向端のグループから、南北方向に、エリア内でのグループ間ルーティングテーブルが順番に更新された後、エリア東西方向端のグループから、東西方向に、エリア内でのグループ間ルーティングテーブルが順番に更新される。これによって、ルーティング情報の更新の遅延を抑制すると共に、ルーティング情報を維持するための通信負荷の増大を抑制することができる。
【０１５４】
また、南北方向にグループ間ルーティング情報を送信する時に東西方向の隣接グループと交換したグループ間ルーティング情報を含まないように、グループ間ルーティング情報を生成することにより、南北のグループのルーティング情報と東西のグループのルーティング情報を分けることができ、ループが発生することを防ぐことができる。
【０１５５】
次に、第３の実施の形態に係る移動端末について説明する。なお、第１の実施の形態と同様の構成となる部分については、同一符号を付して説明を省略する。
【０１５６】
第３の実施の形態では、隣接グループにノードがいないと判断した場合に、グループ間ルーティング情報を、他のグループを経由して送信している点が、第１の実施の形態と異なっている。
【０１５７】
第３の実施の形態では、図４１に示すように、ルーティング情報生成部３８は、ルーティング情報抽出部３８Ａと、ＯＲ演算部３８Ｂと、ＯＲ演算部３８Ｂにより生成されたグループ間ルーティング情報の送信先の隣接グループに、ノード（移動端末１０）が存在するか否かに基づいて、グループ間ルーティング情報を転送するか否かを判断する転送判断部３８Ｃとを備えている。
【０１５８】
転送判断部３８Ｃは、ＯＲ演算部３８Ｂにより生成されたグループ間ルーティング情報の送信先の隣接グループについて、グループ間ルーティングテーブルに格納されている当該送信先の隣接グループの更新時刻から所定時間経過している場合には、当該送信先の隣接グループにノードが存在しないと判断し、一方、所定時間経過していない場合には、当該送信先の隣接グループにノードが存在すると判断する。転送判断部３８Ｃは、当該送信先の隣接グループにノードが存在すると判断した場合、生成されたグループ間ルーティング情報をそのままデータ通信部１４に出力する。一方、当該送信先の隣接グループにノードが存在しないと判断した場合、予め定められた、離れたグループへ送信するために他のグループを経由する経路情報を、グループ間ルーティング情報に追加して、グループ間ルーティング情報をデータ通信部１４に出力する。
【０１５９】
例えば、図４２に示すように、グループＩから、離れたグループＧへ、グループ間ルーティング情報を送信するために、Ｆ−＞Ｅ−＞Ｄを経由することが経路情報により指定される。
【０１６０】
経路情報が追加されたグループ間ルーティング情報を受信した移動端末１０は、自端末が送信先のグループに所属していないと判断すると、グループ間ルーティング情報に改変を加えず、指定された経路通りに転送する。
【０１６１】
なお、第３の実施の形態に係る移動端末の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１６２】
このように、あるグループにノードが存在しない場合、その周辺のグループのルーティング情報が更新されなくなるが、本実施の形態では、グループにノードが存在しないと判断した場合、周辺グループを経由して、グループ間ルーティング情報を転送させることにより、グループ間ルーティングテーブルの更新を持続させることができる。
【０１６３】
次に、第４の実施の形態に係る移動端末について説明する。なお、第４の実施の形態に係る移動端末は、第１の実施の形態と同様の構成となるため、同一符号を付して説明を省略する。
【０１６４】
第４の実施の形態では、図４３に示すように、ノードＩＤ及びグループＩＤを示すビットパターンをＢＦ（Ｂｌｏｏｍ  Ｆｉｌｔｅｒ）にしている点が、第１の実施の形態と異なっている。
【０１６５】
ここで、ＢＦについて説明する。ＢＦとは要素が集合の一部であるかを調べるために用いられる固定長ビットパターンのデータ構造である。参考例として図４４に動作例を示す。図４４では、ノードＡが作成したＢＦをノードＢで参照し、ノードＡとＢの所有データの差を判定している。ｇ（Ｘ）、ｆ（Ｘ）はハッシュ関数であり、ＢＦでのビットへの１の書き込みはハッシュ関数によって導いた値に基づいて行われる。本実施の形態では、ハッシュ関数によって導いた値をビットパターンの長さで割り、その剰余を用いてＢＦでの１を書き込むビットの位置を決定する。図４４では、ビットパターンの長さが１３なので、ｆ（Ｘ）＝１ｍｏｄ１３、ｇ（Ｘ）＝８ｍｏｄ１３のビットに１を書き込む。図４４ではビットパターンの長さが１３だが、実際には衝突を回避するためにもっと長いビットパターンを使用する。
【０１６６】
ＢＦの初期状態は全て０のビットパターンで、ノードＡはハッシュ関数を用いてデータＸ、Ｙ、Ｚを所有していることをＢＦに書き込む。ノードＢはノードＡの所有データを書き込んだＢＦを受信すると、自身の所有しているデータからハッシュ関数を用いて特定のビットを参照し、そのビットが全て１ならばデータを所有していると判断し、そうでないなら所有していないと判断する。上記図４４の例では、ｆ（Ｑ）＝１ｍｏｄ１３、ｇ（Ｑ）＝３ｍｏｄ１３のビットを参照すると１と０であるためノードＡはＱを所有していないと判断できる。同様にｆ（Ｗ）＝６ｍｏｄ１３、ｇ（Ｗ）＝８ｍｏｄ１３のビットは、０と１なのでノードＡはＷを所有していない。ｆ（Ｚ）＝８ｍｏｄ１３、ｇ（Ｚ）１２ｍｏｄ１３のビットは１と１なので、ノードＡはＺを所有していると判断できる。
【０１６７】
また、ＢＦには偽陽性による誤検出の問題はあるものの、ハッシュ関数の種類やビットパターンのサイズの調整により、偽陽性による誤検出の発生を十分低く抑えることが可能である。また、ＢＦは固定長のメモリ消費でビット演算が使用可能であるため、一定サイズのグループＩＤに複数のノード情報を書き込み、かつＢＦを用いた素早いルーティング処理が可能となる。
【０１６８】
また、本実施の形態におけるＢＦを用いたグループＩＤの構成を図４５に示す。グループＩＤはＢＦであり、同一グループ内に存在するノードＩＤを示すＢＦを足し合わせたものである。このグループＩＤとノードＩＤを用いてＤＨＴを管理する。
【０１６９】
グループ間ルーティングテーブル記憶部３２は、隣接グループ位置情報と、当該隣接グループを経由してルーティング可能なグループのグループＩＤを示すＢＦのＯＲ演算により求まるＢＦとからなるグループ間ルーティングテーブルを記憶する。
【０１７０】
データ管理部３４は、エリアデータのデータＩＤと、グループ内ルーティングテーブル記憶部２８に記憶されているグループ内ルーティングテーブルから得られる同一グループの各ノードＩＤと、グループ間ルーティングテーブル記憶部３２に記憶されているグループ間ルーティングテーブルから得られる各隣接グループのＢＦとに基づいて、エリアデータを割り当てるグループを決定し、決定されたグループが自グループである場合には、エリアデータを割り当てるノードＩＤを決定する。
【０１７１】
データ管理部３４は、図４６に示すグループ決定部２５０を備えており、グループ決定部２５０は、２階層のＤＨＴに従って、どのグループでデータを管理するか決定する。
【０１７２】
まず、同一グループ内の各ノードに対する関数ｆ（ｘ）により、同一グループ内のノードＩＤを引数として、１以上の所定個のビットを１にしたＢＦに変換して出力する。
【０１７３】
次に、グループＩＤ生成部２５２は、ＯＲ演算を用いて、関数ｆ（ｘ）から出力されたＢＦを足し合わせて、自グループのグループＩＤを示すＢＦを生成する。
【０１７４】
また、関数ｈ（ｘ）により、データＩＤを引数としてランダムパターンを生成して出力する。
【０１７５】
また、自グループ及び隣接グループの各々に対する関数ｇ（ｘ、ｙ）により、ランダムパターンを用いて、上記図４６に示すように、自グループのグループＩＤを示すＢＦ、及び各隣接グループのＢＦのビットの並び替えを行い、並び替えられたＢＦを各々出力する。
【０１７６】
評価部２５４は、各関数ｇ（ｘ、ｙ）から出力されたＢＦから、どのグループのＢＦがエリアデータを管理するのに適しているのかを決定する評価関数を持ち、決定されたＢＦのグループを出力する。例えば、上記図４６の例のように、ＢＦを数値として評価して最も数値が大きいＢＦのグループが、エリアデータが割り当てられるグループとして決定される。
【０１７７】
また、データ管理部３４は、第１の実施の形態で説明したノード決定部６０と同様の構成を備えており、グループ決定部５０により決定されたグループが、自グループである場合に、自グループ内の各ノードＩＤのＢＦとデータＩＤとに基づいて、自グループ内のどのノードでデータを管理するか決定する。
【０１７８】
なお、第４の実施の形態に係る移動端末の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【０１７９】
以上説明したように、第４の実施の形態に係る移動端末によれば、グループ内のノードＩＤのＢＦを用いて生成されるグループＩＤのＢＦ、及びデータＩＤに基づいて、エリアデータを割り当てるグループを決定すると共に、グループ内のノードＩＤのＢＦ及びデータＩＤに基づいて、エリアデータを割り当てるノードを決定することにより、移動端末のノードが所属するグループが切り替わっても、当該ノードにエリアデータが割り当てられる可能性があるため、移動端末のノードが所属するグループが切り替わる際のデータ通信負荷の増大を抑制することができる。
【０１８０】
各ノードがビットパターン中の１ビットにＩＤ情報を埋める方式を用いる場合、ＤＨＴに参加できるノード数がビットパターンの長さに依存してしまう。これに対し、ビットパターンにハッシュ値を用いる場合、ＯＲ演算を行ってランダムパターンでビットパターンの並び替えを行っても、データが分散しない可能性が高い。そこで、本実施の形態では、上記図４３に示すように、ノードＩＤについて、ＢＦを用いて数ビットのビットパターンの書き込みを行うことによって、ＤＨＴに参加できるノード数を増加させつつ、データを分散させることが可能になる。
【０１８１】
なお、上記の第１の実施の形態〜第４の実施の形態において、グループ間ルーティング情報として、ビットパターンを用いている場合を例に説明したが、これに限定されるものではない。グループ間ルーティング情報が、ルーティング可能なグループのグループＩＤのリストであってもよい。
【０１８２】
また、交差点エリア内の移動端末群で、データ分散記憶システムを実現する場合を例に説明したが、これに限定されるものではなく、交差点エリア内に、固定端末を設け、交差点エリア内の移動端末群と固定端末とで、データ分散記憶システムを実現するようにしてもよい。この場合には、エリア内に移動端末が存在しない場合であっても、エリア内にエリアデータを維持することができる。
【０１８３】
また、交差点エリアの基準位置として、交差点エリアの中心位置を用いる場合を例に説明したが、これに限定されるものではなく、交差点内の他の所定位置を、交差点エリアの基準位置として用いてもよい。
【０１８４】
また、仮想分散データベースを実現するエリアが、交差点である場合を例に説明したが、これに限定されるものではなく、他の所定エリアで、仮想分散データベースを実現するようにしてもよい。
【符号の説明】
【０１８５】
１０   移動端末
１４   データ通信部
１６   コンピュータ
２０   地図データベース
２２   位置取得部
２４   制御部
２５   送信条件取得部
２６   グループ内ルーティングテーブル管理部
２８   グループ内ルーティングテーブル記憶部
３０   グループ間ルーティングテーブル管理部
３２   グループ間ルーティングテーブル記憶部
３４   データ管理部
３６   データ記憶部
３８   ルーティング情報生成部
３８Ａ ルーティング情報抽出部
３８Ｂ ＯＲ演算部
３８Ｃ 転送判断部
５０、２５０  グループ決定部
６０   ノード決定部
【図１】
0005857791.tif 000002
【図２】
0005857791.tif 000003
【図３】
0005857791.tif 000004
【図４】
0005857791.tif 000005
【図５】
0005857791.tif 000006
【図６】
0005857791.tif 000007
【図７】
0005857791.tif 000008
【図８】
0005857791.tif 000009
【図９】
0005857791.tif 000010
【図１０】
0005857791.tif 000011
【図１１】
0005857791.tif 000012
【図１２】
0005857791.tif 000013
【図１３】
0005857791.tif 000014
【図１４】
0005857791.tif 000015
【図１５】
0005857791.tif 000016
【図１６】
0005857791.tif 000017
【図１７】
0005857791.tif 000018
【図１８】
0005857791.tif 000019
【図１９】
0005857791.tif 000020
【図２０】
0005857791.tif 000021
【図２１】
0005857791.tif 000022
【図２２】
0005857791.tif 000023
【図２３】
0005857791.tif 000024
【図２４】
0005857791.tif 000025
【図２５】
0005857791.tif 000026
【図２６】
0005857791.tif 000027
【図２７】
0005857791.tif 000028
【図２８】
0005857791.tif 000029
【図２９】
0005857791.tif 000030
【図３０】
0005857791.tif 000031
【図３１】
0005857791.tif 000032
【図３２】
0005857791.tif 000033
【図３３】
0005857791.tif 000034
【図３４】
0005857791.tif 000035
【図３５】
0005857791.tif 000036
【図３６】
0005857791.tif 000037
【図３７】
0005857791.tif 000038
【図３８】
0005857791.tif 000039
【図３９】
0005857791.tif 000040
【図４０】
0005857791.tif 000041
【図４１】
0005857791.tif 000042
【図４２】
0005857791.tif 000043
【図４３】
0005857791.tif 000044
【図４４】
0005857791.tif 000045
【図４５】
0005857791.tif 000046
【図４６】
0005857791.tif 000047