(57)【特許請求の範囲】
【請求項１】
分割実行体を規定するステップと、
複数の移動体が存在する複数のセルを規定した初期データ構造を構築するステップと、
前記複数のセルの各々に、マルチキャストグループを対応付けるステップと、
複数のセルに対する地理的情報を上記移動体に通信するステップと、
各移動体について、移動体のための位置情報に基づきセルに選択的に参加し、セルに関連するマルチキャストグループを用いてセルの中の他の移動体と通信するステップと、
各セルについて、各移動体に実装された調整者選定ルールを用いて、セルに存在する移動体の組から、調整者を選定するステップと、
前記調整者が、前記セルの選択的な細分および統合に関連するコストを協同的に計算し、前記コストを、前記分割実行体に伝達するステップと、
前記分割実行体が、前記コストを用いて新たな分割スキームを生成し、前記複数の移動体に伝達するステップと
からなる、複数の移動体のグループ化方法。
【請求項２】
協同的に計算する前記ステップは、
前記調整者の各々が、該調整者のセルの細分に関連する第１のコストを計算するステップと、
クアッドツリーデータ構造を用いて、前記調整者間の兄弟関係を識別し、兄弟関係の調整者を規定するステップと、
前記兄弟関係の調整者が、前記兄弟関係の調整者が存在するセルの統合に関連する第２のコストを協同的に計算するステップと
からなる、請求項１に記載の方法。
【請求項３】
前記複数のセルの各々に、マルチキャストグループを対応付けるステップと、
前記複数の移動体の各々に、視野の範囲を関連付けるステップと、
前記視野の範囲に基づいて、前記複数の移動体を、複数のマルチキャストグループの少なくとも１つへ選択的に参加可能にするステップと
をさらに包含する、請求項１に記載の方法。
【請求項４】
前記複数のセルの各々に、マルチキャストグループを対応付けるステップと、
複数のマルチキャストグループの少なくとも１つへ、前記複数の移動体を参加可能にするステップと、
前記複数の移動体が参加しているマルチキャストグループの数を評定することにより、前記コストを計算するステップと
をさらに包含する、請求項１に記載の方法。
【請求項５】
前記複数のセルの各々に、マルチキャストグループを対応付けるステップと、
前記複数のマルチキャストグループを用いて、前記移動体に、前記新たな分割スキームを伝達するステップと
をさらに包含する、請求項１に記載の方法。
【請求項６】
前記分割実行体が、前記複数のセルの１つであって、コストの減少が最大のセルを分割することにより、新たな分割スキームを生成する、請求項１に記載の方法。
【請求項７】
複数の移動体が存在する複数のセルに対応した、複数のノードを有するクアッドツリーデータ構造を規定する分割サーバと、
各々が前記複数の移動体の１つに対応した、通信機構を有する複数のクライアントアプリケーションであって、各々が、他のクライアントアプリケーションの通信機構と通信でき、かつ、前記分割サーバと通信できる複数のクライアントアプリケーションと
を備え、前記クライアントアプリケーションおよび前記分割サーバは、動的分割プロトコルが構築されて構成され、それにより前記クアッドツリーデータ構造が、前記複数のセルの各々に含まれる通信体の数に基づいて再構成される、複数の移動体のグループ化システム。
【請求項８】
前記複数のクライアントアプリケーションの各々は、関心のある所定の領域に対応する視野の範囲を格納するメモリを有し、
前記複数のクライアントアプリケーションの各々の通信機構は、前記視野の範囲に重複するセル内の、マルチキャストグループ通信移動体に加わるよう構成されている、請求項７に記載のシステム。
【請求項９】
前記複数の移動体は、乗物の位置データを生成する位置特定装置を有し、前記クライアントアプリケーションは、共通のセルに存在する移動体に対応する他のクライアントアプリケーションに、前記乗物の位置データを伝達する、請求項７に記載のシステム。
【請求項１０】
所与のセルに存在する複数のマルチキャストグループに基づいてコストを計算するステップを更に含む請求項１に記載の方法。
【請求項１１】
所与のセルの移動体が拒否する複数の余剰のメッセージに基づいて、コスト計算するステップを更に含む請求項１に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、概して分散型情報システムに関する。より具体的には、本発明は、移動エージェントのための、スケール可変マルチキャストアルゴリズムに関する。本発明にかかる出願は、インテリジェント移動システムを含む。インテリジェント移動システムでは、高性能の乗物がネットワークに接続され、周期的に、位置、速度、交通および気象事情等のような状態情報を送信する。本発明はさらに、乗物が目的地に商品を配達するインテリジェント協同移動システムにおいて有用である。本発明の原理はまた、マルチユーザネットワークゲームを含む、移動手段の他の応用に拡張できる。
【０００２】
【従来の技術】
分散型情報システムは、ますます多くの機器がインターネットへの接続を確立するにつれて、急激に普及してきている。主要な分散型情報システムのタイプでは、クライアントは、地理的に非常に近い情報にのみ関心を持っている。本発明による技術の目的は、そのような情報を効率的に見つけ、取り出すことにある。インテリジェント移動システムに関する応用が、特に将来有望である。全ての乗物の大部分がワイヤレスインターネット接続能力を備え付ければ、乗物のコンピュータシステム上で稼動するソフトウェアアプリケーションは、分散型情報システムを確立するのに利用できる。
【０００３】
このようなシステムでは、それぞれの乗物は、データ発信源として機能し、また、それぞれの乗物の位置、その速度、移動方向、および交通や気象事情などの他の状態情報についての情報を集めるデータ送信先として機能するであろう。その結果、それぞれの乗物は、自らの状態についての情報を集め、その情報に関心があって利用したいであろう乗物に、広く配信（ブロードキャスト）できる。
【０００４】
【発明が解決しようとする課題】
この種の応用のための分散型情報システムを構成するには、全てのユーザ（例えば、全ての乗物）から情報を収集する中央サーバを構築する手法が広く知られている。ユーザが、特定の領域の条件についての情報を入手したい場合には、ユーザはサーバに要求を送信し、サーバは要求したユーザにその結果を返送する。このアプローチには、その用途のユーザの数が増加すると、中央サーバに必要となるネットワーク帯域および処理資源が急速に増加するというスケーリングの問題が存在する。中央サーバは、すぐにボトルネックになり、このシステムの１つの欠点になる。
【０００５】
他の周知の手法として、全てのユーザが共通のマルチキャストグループに属して、そのグループを通して全ての情報をブロードキャストする手法がある。マルチキャストから情報を受信した後は、各ユーザは、余剰と考えるメッセージを取り除かなければならない。交通への応用では、例えば、町の北東部のユーザは、南西部の交通情報に関心を持たないであろうから、クライアントアプリケーションソフトウェアが南西部の情報を余剰として取り除くように構成するであろう。
【０００６】
周知のマルチキャストを用いたアプローチは、１つのサーバに関連する故障の問題を解決する一方、ネットワーク帯域の要求の増加、および、各ユーザのオンボードコンピュータにより消費される処理資源の増加にも膨大なコストがかかる。
【０００７】
よって本発明は、配信された要素（マルチキャスト、調整者）および中央の要素（分割サーバ）の両方を用いて、ある範囲を動的に分割する混成した解決法を提供する。これにより、移動体は効率的にグループ化される。本発明、その目的および効果のより完全な理解のため、以下の説明および添付の図面を参照されたい。
【０００８】
【課題を解決するための手段】
本発明は、複数のマルチキャストグループを設けることにより、上述の問題を解決する。システムは、ある範囲を複数の領域またはセルに分け、各領域またはセルを、マルチキャストグループアドレスに関連付ける。このようにして、すぐ周辺の範囲、または視野の範囲に関する情報にのみ関心があるユーザは、近隣の他のユーザと協同して、関心のある情報を見出すことができる。よって、北西部にいるユーザは、その領域またはセル内の他のユーザから、そのセルに対応するマルチキャストグループアドレスを用いて情報を得ることができる。一方、南西部のセルの事情に関連する情報は、異なるマルチキャストグループアドレスを用いて通信できる。よって、北東部にいるユーザは南西部の情報を取り除く必要はない。当然に、特定のユーザが他の領域またはセルの情報を取得したい場合には、システムをうまく設計してその情報を配信できるようにすべきである。本発明によれば、動的に再構成可能な、現在の構成、および、全てのセルまたは領域の関係を格納するクアッドツリー（quad-tree）データ構造を用いることにより、これが可能になる。クアッドツリーデータ構造は現時点では好ましいが、Ｋ−ｄツリーなどのような他のデータ構造を用いてもよい。データ構造は、１つまたは複数の分割サーバにより維持、更新される。これらのサーバは、中央サーバまたは分散サーバにすることができ、絶え間なく変わるユーザの要求に基づいて、セルの最適なサイズおよびグルーピングを判断する。
【０００９】
移動体としての乗物が、ある位置から位置へ移動すると、分割サーバはこの移動についての情報を得て、クアッドツリーデータ構造を再構築して性能を最適化する。よって、ユーザの密度が高い領域は、１以上の既存のセルをより小さなセルに分割することにより、多数のセルに細分化する。逆に、人がまばらな領域は、人がより少ない、連続する小さなセルを統合することにより、より大きなセルに割り当てる。
【００１０】
本発明のある局面によれば、動的クアッドツリー分割アルゴリズムは、各セルに対して、そのセルのユーザにより選定された調整者（コーディネータ：coordinator）を割り当てる。この調整者は、使用条件に関する局所的な知識に基づいて、セルの分割または統合に関連するコストを評価する。選定された調整者にこの役割を持たせることにより、そのセル内の他のユーザは、この情報を集める計算資源を消費しない。調整者は、分割サーバに、このコスト情報を送信する。分割サーバは、アルゴリズムを用いてどのセルを分割して、どのセルを統合するかを判断し、全体的なコストを最小にする。これにより、システムの性能を最適化する。そして、分割サーバは新たな分割スキームを全てのユーザに広く配信（ブロードキャスト）する。このように全てのユーザは、どのセルと通信可能かを知らされる。よって、北西部のユーザが南東部から情報を取得したい場合には、ユーザは、どのセルが、関心のある情報を有する南東部に現在対応付けられているかを識別できる。
【００１１】
本発明では、ある範囲が、複数の領域またはセルに分割される。その各々は、対応するマルチキャストグループアドレスを有する。複数のセルは、動的に更新されるクアッドツリーデータ構造を用いて構成されている。所与のセル内の移動体は、その中の移動体の１つを調整者として選定する。調整者は、そのセルの分割、および、そのセルと他の兄弟セルとの統合に関連するコストデータを評定する。調整者は、このコストデータを、中央サーバである分割実行体に伝達する。分割実行体は、総ざらいアルゴリズムを用いて、新たな分割スキームを計算する。そして新たな分割スキームは、その後の通信のために、複数の移動体にブロードキャストされる。移動体は、個々の視野の範囲に交差するマルチキャストグループに加わる。このように、移動体は、全てのマルチキャストグループの伝送を監視する必要なく、他の移動体から情報を獲得できる。
【００１２】
【発明の実施の形態】
本発明は、以下の説明および添付の図面から、より完全に理解できるであろう。
本発明の動的マルチキャストアルゴリズムには、多くの使途がある。本発明の原理を教示するため、図１に、分散型交通事情を発見する応用例を示す。移動体（mobile entity）は、所定の地理的な範囲内を転々と移動し、その地理的な範囲内の領域またはセルと各々関連する種々のマルチキャストグループに加わって、互いの間で交通事情を通信する。移動体は自動車でよいが、本発明の原理は、他のタイプの移動体（航空機、歩行者、そして輸送中のパッケージまたは商品ですら）にも容易に適用できることが明らかである。さらに、分散型交通事情を発見する用途が図示されているが、本発明は、他の広い範囲で用いることができる。そのような使用法の別の例は、インテリジェント協同輸送システムである。ここでは、乗物は他の乗物と協同して、他の製品を適切な目的地に運ぶ。本発明は、マルチユーザネットワークゲームおよび他のシミュレーションにおいても利用できる。
【００１３】
図１を参照して、コロンビア特別区の地図１０が示されている。この地図は、バージニア州のコロンビア特別区とその周辺地域、および、マリーランド（MARYLAND）を含む、対象となる例示的な地理的範囲を示す。同じコロンビア特別区のコピー１２には、その上に移動体１４を配置している。例えば、各移動体は、本発明によるクライアントアプリケーションソフトウェアを備えた、車、トラック、またはその他の乗物である。各移動体は、さらに、適当なインターネットに接続可能な通信設備を備えており、１以上のマルチキャストセッションに加わることにより、他の移動体との通信を確立できる。移動体の配置分布は、均一な分布から、通常の分布、多く集まった、または密集した分布にわたる、任意の分布でよい。さらに、用事があって移動体が領域内を転々と移動すると、分布は一日を通じて変化すると想定される。図示のため、図１には均一な分布が示されている。しかし、その地区の異なる区域の交通量が、確実に他より多い場合には、多く集まった、または密集した分布が予想される条件になるであろう。
【００１４】
図１には、２つの移動体１４、１６がより詳細に記載されている。図示のため、移動体の大きさまたは規模は、誇張されている。移動体１４は、移動体１６の北西の位置にある。各移動体は、それぞれサークル１８、２０で示される、視野の範囲（vision domain）を持つ。視野の範囲は、その移動体が情報を得たい地理的な領域に対応する。図示されたこれら２つの移動体の視野の範囲１８、２０は、重複することがあることに留意されたい。これは、これら２つの移動体が、共通の関心を持つことを意味する。各移動体が自身の視野の範囲を制御して、それにより所望する多くの地域を含み、または除外できるのはシステムの要件ではない。
【００１５】
集合的な全ての通信移動体は、大域情報２２を集める。大域情報２２は、移動体１６に対応する局所情報２４のような、全ての局所情報の集合から構成されている。現在の好ましい実施の形態では、大域情報２２は分散された形態で保持されている。よって、中央データベースの大域情報の完全なコピーをアップロードし、格納する必要はない。むしろ大域情報は、分散された状態で、局所情報が集合した形で存在する。各移動体は、その特定の視野の範囲に応じて、その移動体に関連がある情報にアクセスできる。局所的な移動体は、それぞれの視野の範囲を制御するので、希望する場合には、どのような移動体でも地理的な範囲内の領域についての情報を得ることができる。交通における応用では、移動体は、典型的には近隣の交通事情に関心を持つであろう。
【００１６】
移動体は、他の移動体と通信して、典型的には地理的な考慮に基づいて情報を取得する。移動体は、関心のある地理的な領域内に物理的に存在する他の移動体と、または関心のある地理的な領域についての情報を獲得した他の移動体と通信する。移動体は、どのように移動体が物理的にグループ化され、または配置されるかを表す共通のデータ構造を用いて、どの移動体と通信を希望するかを決定する。全ての移動体に、どのようにグループ化されるかをまとめた共通の基準を与えるために、現在の好ましい実施の形態は、移動体が転々と移動するのに応じて、移動体の分散パターンの変化を表すように動的に更新するクアッドツリーデータ構造を用いる。好ましい実施の形態では、クアッドツリーデータ構造は、局所的に集められ、評価された情報に基づいて、中心の分割サーバにおいて生成される。クアッドツリーが修正されるたびに、クアッドツリーデータ構造のコピーが、移動体間で共有される。
【００１７】
クアッドツリーデータ構造内の各ノードまたはセルは、割り当てられたマルチキャストグループアドレスを有する。そのセルに関連する条件についての情報を取得したい移動体は、単にマルチキャストグループに加わるのみでよい。よって、クアッドツリーデータ構造は、移動体の現在の視野の範囲に基づいて、どのマルチキャストグループに加わるかを決定する際に、移動体を導く。
【００１８】
好ましい実施の形態では、各移動体は、データ発信源としても、データ送信先としても機能する。これは、図１の参照符号２６および２８において図示されている。
【００１９】
好ましい実施の形態では、各移動体は、図２に機能的に示されているクライアントアプリケーションを実行するコンピュータシステムを有する。クライアントアプリケーションは、データ送信先ポート４０を有する。データ送信先ポート４０を通して、入来する情報が、大域情報２２の集合体から到着する。大域情報２２は典型的には、分散された形態で格納されているので、実際のデータは、クライアントアプリケーションが１以上のマルチキャストチャネルを用いて通信する１以上の移動体から流れてくる。
【００２０】
クライアントアプリケーションもまた大域情報２２の集合体に情報を提供できるように、クライアントアプリケーションは、データ発信源ポート４２を含む。局所情報は、局所データ格納部４４に格納される。図示されるように、この局所データ格納部４４は、データ発信源ポート４２に情報を供給する。局所データ格納部４４はまた、情報フィルタ４６により最初に処理された後に、データ送信先ポート４０から情報を受信する。情報フィルタは、移動体の視野の範囲に関係にない情報を選別して除く。
【００２１】
局所データ格納部４４は、好ましくはクライアントアプリケーションにより管理される、コンピュータにより読み取り可能なメモリに格納されている。局所データ格納部４４は、符号５０で図示されているクアッドツリーのホームセル内に、移動体およびそのメンバーシップについての情報を保護する。局所データ格納部４４はまた、アプリケーション固有の、他の局所状態情報を保護する。符号５２で図示されているように、局所状態情報は、移動体の位置、速度、そして他の関連する位置情報、および、気温、風速および他の環境条件のような他の条件を含むこともできる。
【００２２】
現在の好ましい実施の形態では、各移動体は、自らが存在するセルの調整者として機能する可能性を有する。調整者の役割は、そのセル内の密集状況を評定し、そのセルを細分し、または他のセルと統合するべきかを評定して、性能を向上させることにある。好ましい実施の形態では、移動体が、物理的にはセル内のどの位置にいるかに基づいて、各セルに対して単一の調整者が選定される。希望する場合には、それに代えて他の基準を利用できる。クライアントアプリケーションは、処理モジュール５４を用いる。処理モジュール５４は、現在のクアッドツリー構成、および、特定のセル内での移動体の位置に関する、局所データ格納部４４からの情報を評定し、その移動体が、調整者となるべき資格に適合するかを判断する。他の全ての移動体は、同じモジュール５４を有し、よって、移動体が調整者として資格を有するかを判断できる。現在の好ましい実施の形態では、調整者の選定規則は、セルごとに１つの調整者および１つのみの調整者を選定するとする。
【００２３】
各移動体は、潜在的には、特定のセルについての調整者に選定される要件に適合しうるので、処理モジュール５４は、そのセルが細分されるか統合されるかを表すコスト情報を評価する処理ルーチンを含む。このコスト情報は、セルレベルで評価され、以下により完全に説明されるように、分割サーバに伝達される。現在の好ましい情報は、所与のセル内で生じた、マルチキャストグループ参加者の数に基づいて、および、そのセルのメンバーが取り除き、または拒否しなければならない余剰のメッセージの数に基づいて、コストを評定する。加わるためのコストは、セル内で関連するマルチキャストグループに加わるユーザが負う。余剰のメッセージコストは、マルチキャストグループから受信された、必要のないメッセージの数を数えることにより課せられる。セルを、より小さな子セルに細分することにより、システムに、ユーザをより識別できる能力を与えるより細かいグリッドを確立し、よって、余剰のメッセージの数を減少できる。一方、セルをますます小さな子セルに細分すると、ユーザは、更なるマルチキャストグループに加わって、視野の範囲を実現する必要が高くなる。よって、マルチキャストグループ参加者の数と、余剰メッセージの数との間には、トレードオフがある。このトレードオフは、所与の範囲内のユーザの密度に直接関連する。
【００２４】
上述のように、現在の好ましい実施の形態は、クアッドセルデータ構造を用いて範囲を表し、どのようにその範囲を領域またはセルに細分するかを示す。図３に示すように、クアッドツリーの基本原理は、四角形または他の形状で、関心のある平面領域を覆うことである。そして、その四角形または形状を、より小さな四角形または形状に繰り返し分割する。これは、各々の領域が、適当な均一な入力集合を含むようになるまで行われる。好ましい実施の形態では、各四角形は、マルチキャストグループアドレスが割り当てられるセルを表す。本明細書では、４つの辺（すなわち四角形）のデータ構造が示され、現在はこれが好ましいが、他の幾何図形（例えば、Ｋ−ｄツリー）のデータ構造および他の寸法を利用して、本発明の原理を実現できることは、明らかであろう。よって、本明細書で用いるクアッドツリーという語は、ｎ次元データ構造を含むことを意図している。ここで、ｎは２以上の整数値である。
【００２５】
図３を参照して、ワシントンＤ．Ｃ．の全区域を含む四角形を境界線として引くことにより、ワシントンＤ．Ｃ．区域のクアッドツリーを構築し、参照符号６０、６２、６４で示すように、その四角形の範囲を繰り返し細分する。これは、上述のコストデータの評価に基づいて、適当な大きさのセルが得られるまで行われる。現在の好ましい実施の形態では、必ずしも全てのセルが、同じ大きさである必要はない。最も南西の四分区域は、符号７０のような小さなセルに細分される。それに対して、わずかに北および東のセルは、符号７２のようなセルの４倍の大きさである。一方、残りのセルは、符号７６のようないまだ大きいセルである。
【００２６】
本発明により実装される動的再分割アルゴリズムによると、クアッドツリーセルの大きさおよび構成は、移動体が転々と移動するについれて、動的に変動する。クアッドツリーを任意の時刻において構成する基本的な分割スキーム（分割計画または分割図）は、選定された各セルの調整者により分割サーバに送信された情報を用いて、分割サーバにより計算される。図４は、どのように、この動的再分割のためのメッセージフローが生じるかを示す図である。図４では、１つの例示のためのセル７０が示されている。そのセル内に位置するのは、サークル７２で示された６つの移動体である。セル７０内の全ての移動体は、接続線により示されるように、セル７０に関連付けられたマルチキャストグループアドレスを用いて、互いに通信する。図６に関連して後述される選定規則を用いて、移動体の１つが調整者として宣言される。図４に示す例では、セル７０の右下角の移動体は、調整者７４に指定される。調整者７４は、セル７０のメンバーから、加わる者と余剰メッセージ取り扱いデータを収集し、分割サーバ８０にその情報を伝送する。現在の好ましい実施の形態では、分割サーバ８０は、その領域内の全てのセルに責任を負う中央サーバである。当然、必要に応じて、１つのサーバをサーバのネットワークに置換して、分割生成機能を分散させてもよい。
【００２７】
分割サーバは、あらかじめ規定されたアルゴリズムを用いて、新たな分割スキームを判断する。このとき、クアッドツリーに表されている様々なセルの全ての調整者から受け取った情報を用いる。分割サーバは、全てのユーザマルチキャストグループに広く配信（ブロードキャスト）することにより、または、調整者７４のような単一のユーザを通して情報をリレーすることにより、新たな分割スキームを移動ユーザにブロードキャストする。システムは、この目的のために、専用の調整者マルチキャストグループを持っていてもよい。新たな分割スキームは、各移動ユーザにより（図２の局所データ格納部４４に）格納される新たなクアッドツリーを表す。そして各移動体は、クアッドツリー情報を用い、その移動体の視野の範囲に基づいて、その移動体が加わるべきマルチキャストグループを決定する。
【００２８】
現在の好ましい分割サーバは、総ざらい（greedy）アルゴリズム８４を用い、局所的に評価されたコストデータに基づいて、既存のクアッドツリーデータ構造を修正することにより、新たな分割スキームを生成する。最初のクアッドツリーデータ構造を生成するために、現在はトップダウン総ざらいアルゴリズムが好ましい。図７は、この総ざらいアルゴリズムのフローチャートを示す。以下、このアルゴリズムを説明する。ただし初期化アルゴリズムを説明する前に、図４に示す基本的な動的再分割手順を、図５のフローチャートおよび図６のクアッドツリー図を参照して、より完全に説明する。
【００２９】
図５を参照して、動的分割アルゴリズムは、ステップ１００の調整者の選定から開始する。現在の好ましい実施の形態では、調整者は、そのセルが派生してきた親セルの中心との位置的な近さに基づいて、選定される。これを図６に示す。図６では、複数の移動体が円で示されている。調整者の基準に適合する移動体は、黒に色付けされている。
【００３０】
調整者の選定手順を理解するために、まず、大規模セル２００に着目する。その子セル２０２は、孫セル２０４、２０６、２０８、２１０に細分割されて示されている。孫セル２０４、２０６、２０８、２１０の各々において、１の調整者を選定する。最終的な候補者は、その子供の親セルの中心に最も近い者である。この場合には、親セル２０４の中心をＸで示している。孫セル２０４は、移動体を１つだけ含んでおり、その移動体は、デフォルトでは親セルの中心Ｘに最も近い。孫セル２０６の移動体２１２は、そのセル内の他のどの移動体よりも、中心Ｘに近い。よって移動体２１２は、セル２０６の調整者として選定される。同様に、移動体２１４および２１６は、各セルにおける中心争いで最も近いこととなり、調整者として選定される。各セル２０４、２０６、２０８、２１０の調整者は、いわゆる兄弟関係にある。
【００３１】
中心に最も近い者を選定する技術は、各セルに対する１調整者を決定するのに役立つが、それに代えて、調整者を選定する他の技術もまた利用できる。本システムは、移動体が転々と移動することを予期して設計しているため、調整者の選定手順は、十分な頻度で繰り返され、分散型情報システムの動的特性を獲得できる。
【００３２】
再び図５を参照して、一旦、調整者の選定手順が完了すると、ステップ１０２において、各調整者は、局所的な知識に基づいてそのセルの分割または統合のコスト変化を評価する。そして調整者は、ステップ１０４において、コスト評価情報をサーバに送信する。ステップ１０６において、サーバは総ざらいアルゴリズムを用いて、全体的なコストが最小になるように、どのセルを分割し、どのセルを統合するかを判断する。ステップ１０８において、サーバは、新たに計算した分割スキームを、全てのユーザにブロードキャストして戻す。これは、全てのユーザマルチキャストグループへの包括的ブロードキャストを用いて行うことができる。そして任意で、ステップ１１０に示すように、おそらくは調整者マルチキャストグループを介して、新たな分割スキームを各セルの調整者に送信できる。そしてその調整者は、調整者が属するセルの各メンバーに、局所的な分割および統合指示を広める役割を果たす。
【００３３】
上述のように、現在の好ましい実施の形態では、トップダウン型の総ざらいアルゴリズムを用いて、クアッドツリーのための初期分割スキームを生成する。総ざらいアルゴリズムは、ステップ３００から始まる図７に示されている。ステップ３００において、まず、全ての範囲を囲うように境界が引かれた大きなセルが分析される。アルゴリズムは、繰り返し進む。各セルについて、このアルゴリズムはセルがｎ個のより小さなセルに分割された場合の減少コストを計算する。これはステップ３０２に示されている。次に、ステップ３０２の結果に基づいて、アルゴリズムは、最も大きくコストを低減するセルを選択する。そして、ステップ３０４に示すように、そのセルをｎ＝４のより小さなセルに分割する。その後、ステップ３０６に示すように、全てのセルが処理されるまで、または、コストが減少しなくなるまで、ステップ３０２および３０４が繰り返される。現時点ではトップダウン型の総ざらいアルゴリズムが好ましいが、他のアルゴリズムもまた考えられる。例えば、新たな分割スキームは、ユーザの数に基づいてトップダウン型の総ざらいアルゴリズムにより計算でき、または、ボトムアップ型の総ざらいアルゴリズムにより計算できる。ユーザの数に基づくトップダウン型の総ざらいアルゴリズムの例は、以下のステップを有する。
１．大きなセルとして、四角形の境界が引かれた範囲から開始する。その大きなセル内の各セルに対して、そのセル内のユーザの数を計算する。
２．前のステップの結果から、最もユーザ数が多いセルを選択し、そのセルを４つのより小さな四角形のセルに分割する。
３．全てのグループアドレス（セル）が用いられるまで、またはどのセルのユーザ数も閾値より小さくなるまで、前の２つのステップを繰り返す。
４．まだ得られるグループが存在する場合には、図７に示すアルゴリズムのような総ざらいアルゴリズムを用いて分割を継続する。
【００３４】
ボトムアップ型総ざらいアルゴリズムの例は、以下のとおりである。
１．所与の深さの完全クアッドツリーにより、範囲を複数のセルに分割する。
２．統合可能な各ノード（すなわち、４つの葉である子を持つ各ノード）に対して、コストの減少を計算する。
３．統合コストが最も小さいノードを選択して、統合する。
４．セルの数が、利用可能なマルチキャストグループの数に等しくなるまで、前の２つのステップを繰り返す。
【００３５】
使用の際、移動体はそれぞれの視野の範囲、および、現在のクアッドツリーを用いて、状態伝播プロトコルを実行する。このプロトコルは、各移動体から発信された状態メッセージが、関心のある他の全ての移動体に確実に到達するように設計されている。このプロトコルは、以下のステップを有する。
１．各ユーザは、クアッドツリーデータ構造に表される現在の分割スキームの知識を用いて、自身の「視野の範囲」に交差（重複）するセルを計算する。
２．各ユーザは、交差するセルに関連する全てのマルチキャストグループに加わり、これらのマルチキャストグループから情報を受け取る準備をする。
３．各ユーザは、自身の状態情報を、自身の「ホーム」セルグループに送信する。セルグループとはすなわち、ユーザがその中に位置するセルグループである。
４．加わった全てのマルチキャストグループから情報を受信して、ユーザは、余剰のメッセージを取り除き、取り除かれたメッセージの数の記録を維持する。それにより、調整者は、コストの規準としてその情報を利用できる。
【００３６】
現在の好ましい実施の形態では、動的再分割は、図７の総ざらいアルゴリズム（またはその同等アルゴリズム）を用いて生成された静的な分割から開始することにより、実行される。移動体が転々と移動すると、移動体は動的にマルチキャストグループセッションに加わり、または離れる。新たな分割スキームに基づいて、新たな調整者もまた選定される。現在の好ましい動的分割アルゴリズムは、以下のステップにより進行する。
１．ユーザは転々と移動する。各ステップで新たな調整者が選定される。
２．調整者は、その子である葉をそれぞれ分割することに関連するコストの低減を計算する。
３．ノードが４つの子のノードを有する場合には、対応する調整者は、それらのノードを統合することに関連するコストの増加を計算する。
４．各調整者は、分割サーバにコスト変化情報を送信する。サーバは、新たに分割するかを判断する。所定の時間の経過後に周期的に新たな分割を生成する基準、または、新たな分割によるコスト減少が所定のレベルに到達するかが考えられる。
５．サーバが、新たな分割を行うと判断すると、総ざらいアルゴリズムを用いて、分割すべきおよび統合すべきセルを計算して、新たな分割スキームを生成する。新たなスキームは、全てのユーザにブロードキャストされる。
【００３７】
上述のアルゴリズムは、分割サーバが新たな分割スキームを判断するのに完全に依存するが、サーバには、計算負荷がほとんどかからない。それはコスト評価が、調整者により分散的に行われるからである。
【００３８】
本発明による動的分割アルゴリズムは、実際の地図データを用いて、コンピュータシミュレーションでテストされ、８０パーセントのメッセージコストの削減が確認された。シミュレーションでは、動的クアッドツリー分割アルゴリズムの性能をテストし、セルベースのプロトコルおよび静的クアッドツリー分割と比較した。四角形のシミュレーション範囲は、１辺の単位長さと仮定している。シミュレーションでは、全てのユーザが、同じ円形の視野の範囲を有しているとした。その視野の範囲の半径は、０．０１に設定した。全てのユーザは、任意に方向を選択し、その方向に一定のステップで移動させている。移動によりユーザがその範囲の外に出た場合には、そのユーザは、その範囲内に「跳ね返」らせた。それにより、ユーザの数を一定に保つことができた。またシミュレーションでは、全てのユーザが同じステップの大きさを持つと仮定している。選択したステップの大きさは、それぞれ０．００１、０．００２、０．００５および０．０１である。データ量を減らすため、１００ステップごとに、１つのデータポイントをサンプリングした。また、新たな分割がメッセージコストを２０パーセント減少する場合に、新たな分割を行うとした。その結果、動的クアッドツリー分割アルゴリズムが、８０パーセントのメッセージコストが削減できた。
【００３９】
本発明は、現在の好ましい実施例により説明したが、本発明は、特許請求の範囲に説明される本発明の精神のあらゆる範囲内で、修正可能であり、また様々な異なる使用に対して適用できることが理解される。
【発明の効果】
本発明によれば、調整者および分割実行体（分割サーバ）の両方を用いて、ある範囲を動的に分割する。これにより、移動体を効率的にグループ化できる。
【図面の簡単な説明】
【図１】  本発明の原理を理解するのに有用な、領域またはセルに分割されている例示的な地理的な範囲の概略表現を示す図である。
【図２】  現在の好ましい実施の形態による、クライアントアプリケーションのブロック図である。
【図３】  クアッドツリーデータ構造の一例を示すデータ構造図である。
【図４】  移動体、選定された調整者、および、分割サーバ間の関係を示すデータフロー図である。
【図５】  動的分割アルゴリズムのフローチャートを示す図である。
【図６】  調整者の選定手順を理解するのに有用な、例としての移動体が配置された、例示的なクアッドツリーデータ構造を示す図である。
【図７】  セルを細分するための、現時点での好ましいトップダウン型総ざらい（greedy）アルゴリズムを示す図である。
【符号の説明】
１４、１６  移動体
１８、２０  サークル
２２  大域情報
２４  局所情報
２６  データ発信源
２８  データ送信先
７０  セル
７２  親セル
７４  調整者
７６  親セル
８０  分割サーバ
２００  大規模セル
２０２  子セル
２０４、２０６、２０８、２１０  孫セル
２１２、２１４、２１６  移動体
【図１】
0004018496.tif 000002
【図２】
0004018496.tif 000003
【図３】
0004018496.tif 000004
【図４】
0004018496.tif 000005
【図５】
0004018496.tif 000006
【図６】
0004018496.tif 000007
【図７】
0004018496.tif 000008