キャッシュ管理装置およびデータ配信システム
【課題】車車間通信により交換される、位置に関連した情報を効率よくキャッシュする。
【解決手段】各車両は、自車両の走行予定経路、キャッシュに保持しているデータの種類、位置情報を含む状態通知メッセージを周囲の車両に送信する。状態通知メッセージによって、自車両が保持しているデータのそれぞれについて、他のどの車両がそのデータを要求しているのかと、そのデータを提供可能であるかを判断可能である。要求者数の多いデータほど、また、提供者数の少ないデータほど優先的にキャッシュに格納されるようにキャッシュ管理を行う。他車両が自車両と同一方向に走行し、かつ、自車両が保持しているデータを保持している場合は、この他車両はこのデータの提供者であると判断する。他車両が自車両と反対方向に走行し、かつ、自車両が保持するデータを保持していない場合は、この他車両はこのデータの要求者であると判断する。
【解決手段】各車両は、自車両の走行予定経路、キャッシュに保持しているデータの種類、位置情報を含む状態通知メッセージを周囲の車両に送信する。状態通知メッセージによって、自車両が保持しているデータのそれぞれについて、他のどの車両がそのデータを要求しているのかと、そのデータを提供可能であるかを判断可能である。要求者数の多いデータほど、また、提供者数の少ないデータほど優先的にキャッシュに格納されるようにキャッシュ管理を行う。他車両が自車両と同一方向に走行し、かつ、自車両が保持しているデータを保持している場合は、この他車両はこのデータの提供者であると判断する。他車両が自車両と反対方向に走行し、かつ、自車両が保持するデータを保持していない場合は、この他車両はこのデータの要求者であると判断する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、キャッシュ管理技術に関し、特に、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおけるキャッシュ管理技術に関する。
【背景技術】
【０００２】
地図情報のように位置に関連するデータ（以下、「データ」と呼ぶ）を配信するサービス（以下、「位置情報サービス」と呼ぶ）が普及しつつある。これに伴い、データ提供元である、クライアント・サーバ型システムにおけるサーバ装置や、インフラ協調型システムにおける路側基地局（以下、これらを総称してサーバ装置と呼ぶ）に必要とされる通信帯域は年々増加する傾向にある。
【０００３】
一般に、サービス提供者が通信業者に支払う通信料金は従量課金制である場合が多く、必要とされる通信帯域が大きくなりすぎると、サービス提供のコストが増大してしまう。または、通信帯域の逼迫によりサービス品質に支障が生じてしまう。したがって、クライアント（車両）とサーバ装置との間の通信帯域を削減することが望まれる。
【０００４】
特許文献１では、複数の車載機が、サーバにアクセスしてデータの異なる部分を分担して取得し、取得した部分データを車車間通信により相互に交換することで完全なデータを形成する方法が開示されている。この方法では、直接通信可能な状態にある車両でしかデータの交換ができず、サーバの通信帯域の削減効果は限定的である。
【０００５】
上記の問題を考慮してマルチホップ型のピア・ツー・ピア通信を行い、直接通信できない車載機間でデータの交換を行う方法が考えられる。しかし、この方法を単純に適用した場合、データを複数の車載機を経由してルーティングすることになり、通信経路上の車載機の通信帯域をより多く消費してしまう。この方法では、車載機の数やホップ数が増えた場合に、通信量が許容範囲を超えてしまうため、サーバの通信帯域の削減効果は限定的である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２７４４１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記を考慮して、車載機が取得したデータをストレージに保存しておき、移動先で、そのデータを将来必要とすると予想される車載機に配信する方法が考えられる。しかしこの方法は、車載機のストレージに保持できるデータ量の限界が問題となる。３次元地図情報などのように巨大なデータを扱う場合、保持しておくデータを適切に取捨選択しなければ、ストレージがあふれてしまう。
【０００８】
このように、車載機がデータを保持してサーバ装置に代わって他の車両に配信する場合は、車載機のストレージ容量は有限なので、より重要なデータを優先的に保持することが求められる。
【０００９】
本発明は、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおいて、他の車両に配信するためにデータを車両内にキャッシュする際にキャッシュヒット率を向上させるようにキャッシュ管理することを目的とする。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、本発明に係るキャッシュ管理装置は、周囲の車両から送信される走行予定経路情報と保持データ情報を基に、自車両が保持しているデータのそれぞれについてデータ要求者数とデータ提供者数を算出し、データ要求者数が多いデータほど、また、データ提供者が少ないデータほど優先的にキャッシュメモリに保持する。
【００１１】
より具体的には、本発明に係るキャッシュ管理装置は、複数の車両とサーバ装置から構成され、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおける、車両に搭載されたキャッシュ管理装置であって、キャッシュメモリと、キャッシュ管理手段と、状態通知手段と、状態取得手段と、データ取得手段と、データ送信手段を備える。
【００１２】
状態通知手段は、自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する。すなわち、状態通知手段は、自車両が今後どのような経路を走行するかという情報と、自車両がどのようなデータを保持しているかという情報を、周囲の車両に対して送信する。状態通知メッセージには位置情報や走行速度など、車両の走行に関するその他の情報を含めることも好ましい。
【００１３】
状態取得手段は、周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する。すなわち、状態取得手段によって、周囲の車両が今後どのような経路を走行するかということと、どのようなデータを保持しているかということを認識できる。
【００１４】
データ取得手段は、自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得する。また、データ送信手段は、他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信する。
【００１５】
ここで、本発明の状態取得手段は、他車両から受信した状態通知に基づいて、以下の二つの判断を行う。
（１）他車両（状態通知メッセージの送信元車両）と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータをこの他車両も保持している場合は、この他車両をこのデータのデータ提供者であると判断する。
（２）他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータをこの他車両が保持していない場合は、この他車両をこのデータのデータ要求者であると判断する。
この処理を周囲の車両から送信される状態通知メッセージの全てに対して行うことで、自車両が保持しているデータのそれぞれについて、データ提供者の数とデータ要求者の数を把握することができる。
【００１６】
そして、本発明のキャッシュ管理手段は、キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する。
【００１７】
これにより、各車両のキャッシュメモリには、データ要求者の数が多いデータほど、また、データ提供者の数が少ないデータほど優先的に格納されることになる。したがって、キャッシュヒット率を向上させることができる。
【００１８】
上記の状態通知メッセージは、送信元車両の走行予定経路に沿ってルーティングされることが好ましい。なぜならば、データ要求者やデータ提供者に該当するかは、走行予定経路に重複があるか否かによって判断されるためである。走行予定経路から大きくずれる場所に位置する車両がデータ要求者やデータ提供者に該当する可能性は低く、状態通知メッセージをその位置に送信しても無駄に通信帯域が消費されるだけである。走行予定経路に沿ってルーティングすることで、通信帯域の浪費を防止できる。ただし、現時点では走行予定経路に位置しない車両と将来的に走行経路が重複することはあるので、走行予定経路とその周辺の範囲に状態通知メッセージが送信されるようにしても良い。
【００１９】
走行予定経路に沿ってルーティングさせるために、送信元の車両の状態通知手段が状態通知メッセージをブロードキャスト送信し、以下の基準で受信車両が転送を行うことが好ましい。すなわち状態通知メッセージの受信車両の状態取得手段は、自車両がこの状態通知メッセージに含まれる走行予定経路上に位置し、かつ、走行予定経路上流の車両から状態通知メッセージを受信した場合に、受信した状態通知メッセージを転送すればよい。なお、通信帯域の逼迫を避けるために、一度受信したことのある状態通知メッセージは転送しないとか、転送回数に上限を設けるとか、送信元車両から所定の距離内の場合のみ転送するとかという基準を設けることも好ましい。
【００２０】
また、走行予定経路に沿ってルーティングさせるための別の方法として、送信元の車両の状態通知手段が、自車両の走行予定経路上の車両を中継車両として指定して状態通知メッセージを送信することも好ましい。
【００２１】
なお、状態通知メッセージを走行予定経路にそってルーティングする場合は、状態通知メッセージは走行予定経路上流（後方）に対しては伝わらないことになる。したがって、同じ走行予定経路を走行中の二台の車両が同じデータを保持している場合に、下流の車両は上流の車両がこのデータのデータ提供者であることが判断できるが、上流の車両は下流の車両がこのデータのデータ提供者であると判断できないことになってしまう。これに対処するために、状態通知メッセージを受信し、送信元車両が自車両の保持するいずれかのデータについてのデータ提供者であると判断したときに、自車両がこのデータのデータ提供者であることを通知する重複データ保持通知を送信元の車両に対して送信することが好ましい。
【００２２】
また、状態取得手段は、状態通知メッセージ送信元の他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持し、かつ当該他車両の走行予定経路近傍のデータであって、当該他車両が保持していないデータについて、当該他車両を当該データのデータ要求者であると判断することが好ましい。すなわち、自車両が保持している全てのデータを対象としてデータ要求者であるか否かを判断するのではなく、自車両が保持しかつ相手車両の走行予定経路近傍のデータのみを対象としてデータ要求者であるか否かを判断する。走行予定経路近傍に関連づけられていないデータを要求することは少ないと考えられるので、これにより、さらに精度の良いキャッシュ管理が可能となる。
【００２３】
また、キャッシュ管理手段は、データ要求者数およびデータ提供者数を利用せずに求めた指標と、データ要求者数およびデータ提供者数を利用して求めた指標の両方を用いて、削除するデータを決定することも好ましい。「データ要求者数およびデータ提供者数を利用せずに求めた指標」には、ＬＲＵ（Least Recently Used）、ＬＦＵ（Least Frequently Used）、ＡＲＣ（Adaptive Replacement Cache）などの従来のアルゴリズムにしたがって求めた指標を採用することができる。
【００２４】
本発明は、上記手段の少なくとも一部を含むキャッシュ管理装置として捉えることができる。また、本発明は、車載端末においてこれらの処理を行うキャッシュ管理方法、さらには、これらの方法を実現するためのプログラムとして捉えることもできる。また、本発明は、上記キャッシュ管理装置を備える車両と位置に関連するデータを配信するサーバ装置とから構成されるデータ配信システムとして捉えることもできる。上記手段および処理の各々は可能な限り互いに組み合わせて本発明を構成することができる。
【発明の効果】
【００２５】
本発明によれば、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおいて、他の車両に配信するためにデータを車両内のキャッシュを有効活用でき、サーバ装置との間の通信を削減可能となる。
【図面の簡単な説明】
【００２６】
【図１】本実施形態に係るデータ配信システムの概要図。
【図２】本実施形態に係る車載端末のハードウェア構成図。
【図３】本実施形態に係る車載端末の機能ブロック図。
【図４】（Ａ）経路情報のデータ形式。（Ｂ）保持データ情報のデータ形式。（Ｃ）近傍車両管理テーブルのテーブルフォーマット。（Ｄ）データ要求者管理テーブルのテーブルフォーマット。（Ｅ）データ提供者管理テーブルのテーブルフォーマット。
【図５】上位プログラムからデータ要求を受け付けたときに実行される、データ取得処理のフローチャート。
【図６】定期的あるいは不定期に実行される状態通知メッセージ送信処理のフローチャート。
【図７】状態通知メッセージのフォーマット。
【図８】状態通知メッセージを受信したときに実行される処理のフローチャート。
【図９】データ提供者管理テーブル更新処理（図８のＳ８０８）の詳細なフローチャート。
【図１０】データ要求者管理テーブル更新処理（図８のＳ８１２）の詳細なフローチャート。
【図１１】キャッシュ管理処理（図５のＳ５１６）のフローチャート。
【図１２】本実施形態の動作例説明の前提となる状況を説明する図。
【図１３】図１２に示す状況での状態通知メッセージを示す図。
【図１４】図１２に示す状況で車両Ｃ１によって作成される（Ａ）データ要求者管理テーブルと（Ｂ）データ提供者管理テーブル。（Ｃ）はデータ要求者数とデータ提供者数を考慮したキャッシュの削除優先度の値を示す。
【発明を実施するための形態】
【００２７】
＜概要＞
図１は本実施形態に係るデータ配信システムの概要を示す図である。データ配信システムは、複数の車両１００と、データを配信するサーバ装置２００とから構成される。サーバ装置２００は、車両１００に送信するためのデータ２０１を保持しており、車両１００からの要求に応じてデータを車両に配信する。ここで、データは位置に関連したデータであり、たとえば、３次元地図データ、店舗情報、広告情報などであるが、データの内容は本発明では限定されない。
【００２８】
車両１００は基本的にサーバ装置２００からデータを取得するが、取得したデータをキャッシュメモリに保持しておき、自車が必要とするデータを周囲の車両が保持していれば、サーバ装置２００からではなく、周囲の車両からこのデータを取得する。これによって、サーバの通信帯域を削減することができる。
【００２９】
なお、図１では車両１００とサーバ装置２００が無線通信を直接行うように記載しているが、サーバ装置２００と通信可能に接続された路側通信設備を設けて、車両はこの路側通信設備からデータを取得する構成としても良い。また、車両１００間の通信はマルチホップの通信を行うものとするが、データの取得はシングルホップあるいは限られたホップ数の通信に限定して車車間通信による通信帯域の逼迫を避けることが好ましい。
【００３０】
このような仕組みにおいて、車両内のキャッシュを有効に活用するためには適切なキャッシュアルゴリズムの採用が必須である。基本的には、他の車両から必要とされるデータを優先的に保持しておけばよく、また、自車両のみが提供できるデータを優先的に保持しておけばよい。本実施形態においては、各車両が、自車両の走行予定経路と、自車両がどのデータをキャッシュしているかという情報を周囲の車両に対して通知する。これにより、各車両は、周囲の車両がどのような経路を走行し、かつ、どのようなデータを保持しているかを把握することができる。そして、このように把握された状況に基づいて、自車両が保持しているデータのそれぞれについて、このデータを要求している車両の数、および、このデータを提供できる他の車両の数を算出し、これに基づいてキャッシュ管理を行う。
【００３１】
＜構成＞
図２に車両１００に搭載される車載端末のハードウェア構成を示す。また、図３に車載端末の機能構成を示す。図２に示すように、車載端末は、ＣＰＵ１、位置検出装置群２、表示装置７、音声出力装置８、入力装置９、車車間通信装置１３、路車間通信装置１４などを含んで構成される。これらの装置は車内ネットワークやシステムバスなどを介してＣＰＵ１と接続されている。
【００３２】
位置検出装置群２は、衛星などからの電波に基づいて車両の位置を検出するＧＰＳ（Global Positioning System）受信機３、車両の回転角速度を検出するジャイロセンサ４、
車両の向きを取得するための地磁気センサ５，車両の走行距離を検出する距離センサ６を有している。これらのセンサから取得される情報や、地図情報とのマッチング（マップマッチング）などにより自車両の位置を検出できる。
【００３３】
表示装置７は液晶ディスプレイなどであり、音声出力装置８はスピーカーである。入力装置９は、ユーザからの指示を入力するためのものであり、ボタンやスイッチあるいは、キーボードやマウスなどを採用可能である。また、表示装置７と入力装置９を一体化したタッチパネルを採用してもかまわない。また、音声入力装置を採用しても良い。
【００３４】
車車間通信装置１３は他の車両（の車車間通信装置）と無線通信を行うための装置である。無線通信方式には、例えば、無線ＬＡＮ（ＩＥＥＥ８０２．１１ａ，ｂ，ｇ，ｎ）、ＤＳＲＣ（Dedicated Short Range Communication）、ＵＷＢ、ミリ波通信などを採用可
能である。路車間通信装置１４は、サーバ装置と無線通信を行うための装置である。無線通信方式には、ＷｉＭＡＸやＬＴＥを採用可能である。なお、車両とサーバ装置が路側通信設備を介して通信を行う場合には、その他の狭域な無線通信方式を採用しても良い。
【００３５】
ＣＰＵ１は、ＲＯＭ１０や補助記憶装置１２などに格納されたＯＳプログラムやアプリケーションプログラムをＲＡＭ１１上に展開して実行することで、図３に示すような種々の機能を実現する。
【００３６】
キャッシュ管理機能２０は、ナビゲーションプログラム３０などの上位プログラムからのデータ要求を受けて、キャッシュメモリ２５またはサーバ装置や他の車両からデータを取得して上位プログラムに返す機能を有する。ナビゲーションプログラム３０は、位置検出装置群２による自車両の位置検出や経路探索などの周知の処理を行う。キャッシュ管理
機能２０は、次のような機能部から構成される。
【００３７】
状態記憶部２１は、自車両および周囲の車両に関する状態を記憶する。具体的には、各車両について、今後どのような経路を走行するかという経路情報、どのようなデータを保持しているかという保持データ情報、および、どの位置にいるのかという位置情報を格納する。なお、自車両の経路情報および位置情報は、例えば、ナビゲーションプログラム３０から取得することができる。ナビゲーションプログラムでは、走行経路の探索や設定がなされるのでこの経路をキャッシュ管理機能２０へ通知すればよい。また、自車両がどのようなデータを保持しているかは、キャッシュ管理部２４から取得できる。
【００３８】
経路情報は、図４Ａに示すように、ノードＩＤ（交差点ＩＤ）のリストとして表現される。経路情報は、リンクＩＤのリストとして表現されてもかまわない。
【００３９】
サーバ装置から配信されるデータには、それぞれのデータを識別可能なデータＩＤが付与される。このデータＩＤから、そのデータがどの位置に関連づけられているか判断可能とすることが好ましい。例えば、データＩＤの一部に位置を示す識別子を含むことが好ましい（データＩＤ＝エリアＩＤ＋識別番号）。保持データ情報は、図４Ｂに示すように、各車両がキャッシュメモリ内に保持しているデータのデータＩＤのリストとして表現される。
【００４０】
状態記憶部２１には、図４Ｃに示すような、周囲の車両を管理するための近傍車両管理テーブルが格納される。近傍車載機管理テーブルには、車両ＩＤ（または車載機ＩＤ）、保持データ情報、経路情報、位置情報が格納される。
【００４１】
状態記憶部２１には、さらに、自車両が有する各データについて、そのデータを要求していると考えられる車両を格納したデータ要求者管理テーブル（図４Ｄ）、および、そのデータを提供可能と考えられる車両を格納したデータ提供者管理テーブル（図４Ｅ）も格納される。これらのテーブルは、自車両が有するデータごとに、車両ＩＤのリストとして構成される。これらのテーブルについての詳細は後述する。
【００４２】
状態通知部２２は、定期的あるいは不定期に自車両の状態（経路情報、保持データ情報、位置情報など）を周囲の車両に通知するための機能部である。なお、状態情報として、走行速度やその他の情報を含めることも好ましい。状態通知部２２は、車車間通信装置１３から状態通知メッセージを送信することで、周囲の車両へ自車両の状態変更を通知する。この状態通知メッセージの伝播経路は、送信元車両の経路に沿うことが好ましい。そのために、状態通部２２が送信経路または中継車両を指定して状態通知メッセージを送信しても良いし、状態通知メッセージの受信車両がメッセージ内に格納された経路情報と自車の位置を基に自律的に中継するか否かを決定しても良い。
【００４３】
状態取得部２３は、周囲の車両から送信される状態通知メッセージを車車間通信装置１３によって受信して、状態記憶部２１を更新するための機能部である。状態取得部２３が周囲の車両から状態通知メッセージを受信して状態記憶部２１を更新することで、状態記憶部２１の内容が最新に保たれる。状態取得部２３は、受信した状態通知メッセージに自車両が中継車両として指定されていたり、状態通知メッセージに含まれる経路情報と自車両の位置を比較により必要ありと判断できたりする場合は、この状態通知メッセージの転送を行う。また、状態通知メッセージが走行予定経路（以下単に、走行経路と称する）に沿ってルーティングされると、状態通知メッセージによる情報は走行経路下流方向にのみ伝播するので、自車両が送信元車両の有するデータのデータ提供者である場合には、このことを別途通知する。
【００４４】
キャッシュ管理部２４は、キャッシュメモリ２５を管理する機能部であり、キャッシュメモリにデータを格納するための空き容量がないときに、いずれのデータをキャッシュメモリから削除するか決定する。キャッシュヒット率を高めるためには、将来使われる可能性の高いデータをキャッシュメモリに残すことが必要である。キャッシュ管理部２４は、データ要求者の数が多いデータほど、また、データ提供者の数が少ないデータほど優先してキャッシュメモリ内に残す制御を行う。また、データ要求者およびデータ提供者の数だけを考慮するのではなく、ＬＲＵやＬＦＵなどの従来のキャッシュアルゴリズムによる削除優先度も考慮して、いずれのデータをキャッシュメモリから削除するか決定する。
【００４５】
データ取得部２６は、上位プログラム３０からデータの要求を受け付け、要求されたデータを取得して返す機能部である。データ取得部２６は、自車両のキャッシュメモリ内に要求されたデータがあればキャッシュメモリから取得して上位プログラムに渡す。一方、キャッシュメモリ内に要求されたデータがなければ、可能であれば車車間通信によって他の車両から、それもできなければ路車間通信によってサーバ装置からデータを取得して上位プログラムに渡す。
【００４６】
データ送信部２７は、他の車両からデータの要求を受け付けて、キャッシュメモリ２５内にそのデータがあれば、要求元の車両にデータを送信する。キャッシュメモリ２５内に要求されたデータがない場合には、何も行わないか、データを保持していないことを通知する。
【００４７】
＜処理詳細＞
以下、各機能部が行う処理の内容について、より詳細に説明する。
【００４８】
［データ取得処理］
まず図５を参照して、ナビゲーションプログラムなどの上位プログラムからデータ取得要求を受け付けたときの処理を説明する。データ取得部２６が上位プログラム３０からデータ取得要求を受け付ける（Ｓ５０２）と、以下の処理が行われる。データ取得部２６は、要求されたデータがキャッシュメモリ２５内に存在するか否かを、キャッシュ管理部２４に問い合わせる（Ｓ５０４）。要求されたデータがキャッシュメモリ２５内に存在する場合（Ｓ５０４−ＹＥＳ）には、キャッシュメモリからデータを取得する（Ｓ５０６）。
【００４９】
一方、要求されたデータがキャッシュメモリ２５内に存在しない場合（Ｓ５０４−ＮＯ）には、このデータを提供可能な車両が周囲に存在するか判定する（Ｓ５０８）。この判定は、近傍車両管理テーブルを参照することで判断できる。たとえば十分に近い位置に存在する車両（Ｎホップ以内（Ｎは設計パラメータ）で通信可能な車両）がデータを持っている場合に、この車両が要求されたデータを提供可能と判断する。周囲にデータの提供者が存在する場合（Ｓ５０８−ＹＥＳ）は、車車間通信によってこの車両からデータを取得する（Ｓ５１０）。周囲に要求されたデータを提供可能な車両が存在しない（Ｓ５０８−ＮＯ）か、周囲の車両にデータを要求したが所定時間内にデータが得られない場合（Ｓ５１２−ＮＯ）は、路車間通信によってサーバ装置２００からデータを取得する（Ｓ５１４）。
【００５０】
このようにして、周囲の車両またはサーバ装置からキャッシュメモリ内に存在しないデータを取得したら、取得したデータをキャッシュメモリに格納するキャッシュ管理処理を行う（Ｓ５１６）。ここで、キャッシュメモリに空き容量が無い場合には、参照される可能性が最も低いと考えられるデータをキャッシュメモリから削除する。キャッシュの削除アルゴリズムについては、その判断の基となる情報の取得方法を説明した後に改めて説明する。
【００５１】
データ取得部２６は、キャッシュメモリ、他の車両またはサーバ装置のいずれかから要求されたデータを取得し、取得したデータを要求元の上位プログラムへ渡す（Ｓ５１８）。
【００５２】
［状態通知送信処理］
次に図６を参照して、状態通知部２２が行う状態通知メッセージの送信処理について説明する。この処理は定期的あるいは不定期に実行される。たとえば、１００ミリ秒おきに実行するようにしても良いし、あるいは、自車両の状態（経路情報、保持データ情報、位置など）に変更があったときに実行するようにしても良い。
【００５３】
状態通知部２２は、キャッシュ内に格納されているデータのデータＩＤを取得する（Ｓ６０２）。本実施形態では、状態通知部２２が状態記憶部２１に格納されている自車両の保持データ情報を参照することで、キャッシュ内のデータの一覧を取得する。キャッシュ管理部２４がキャッシュに変更がある度に状態記憶部２１を更新する構成とすれば、状態記憶部２１内の自車両の保持データ情報を参照することでキャッシュメモリ内に格納されているデータの一覧を取得できる。もちろん、状態通知部２２がキャッシュ管理部２４に問い合わせてデータの一覧を取得しても良い。
【００５４】
状態通知部２２は、自車両の走行予定経路および位置情報を取得する（Ｓ６０４）。これらの情報はナビゲーションプログラムが保持しているので、ここから取得すれば良い。
【００５５】
状態通知部２２は、送信者ＩＤ（自車両の車載機ＩＤ）、経路情報、保持データ情報、および位置情報を含む状態通知パケット（図７）を作成し（Ｓ６０６）、車車間通信装置１３から送信する（Ｓ６０８）。状態通知パケットは、図７に示すように、送信者ＩＤ（車両ＩＤ）、経路情報、保持データ情報、および位置情報が含まれる。また、中継車両の指定やフラッディングを停止させる条件など、ルーティングに関する情報も含まれる。
【００５６】
本実施形態では、通信を中継する車載機（以下、中継者と呼ぶ）を経由することで、マルチホップ通信によって状態通知メッセージを伝播させる。この際、この状態通知メッセージは、自車両の走行経路にしたがって伝播するようにルーティングされる。すなわち、走行経路の上流から下流に向かって、状態通知メッセージを伝播させる。たとえば、自車両の走行経路上に位置する車両を中継者として選択して伝播させるか、フラッディングにより伝播させればよい。フラッディングを採用する場合には、受信者両側で自律的に中継するか否かを判断することで、走行経路に沿って伝播するようにする。
【００５７】
［状態通知受信時処理］
次に図８を参照して、状態取得部２３が行う、状態通知メッセージ受信時の処理について説明する。この処理は、状態取得部が他の車両から状態通知メッセージを受信するたびに実行される。なお、この項において、状態通知メッセージの送信元車両のことを「相手車両」と記載する。
【００５８】
相手車両から状態通知メッセージを受信する（Ｓ８０２）と、状態記憶部２１内の近傍車両管理テーブルの相手車両に関するエントリを、この状態通知メッセージに含まれる情報で更新する（Ｓ８０４）。
【００５９】
状態取得部２３は、状態通知メッセージに含まれる相手車両の走行経路と、自車両の走行経路が、同一方向であり、かつ、十分な重なりがあるか判断する（Ｓ８０６）。ここで、「十分な重なり」というのは、今後の互いの位置関係の類推から、すれ違う他の車載機の集合が近いと予測できることを意味する。すれ違う他車両の集合は、両車両の、走行経路、現在位置、進行速度などから判断できる。簡単な実装では、両車両の走行経路に所定
距離以上の重複があり、かつ、互いの距離が所定値以内である場合に、「走行経路が十分に重なっている」と判断する。
【００６０】
状態通知メッセージの送信元車両（相手車両）と走行経路が同一方向であり、かつ、十分な重なりがある場合（Ｓ８０６−ＹＥＳ）には、すれ違う他車両に対して、相手車両と自車両の両方がデータを提供可能である。したがって、相手車両が自車両の保持するデータを保持していれば、相手信元車両をこのデータの提供者であると判断できる。状況取得部２３は、このようにして状態記憶部２１内のデータ提供者管理テーブルを更新する（Ｓ８０８）。
【００６１】
図９に、上記のデータ提供者管理テーブルの更新処理の詳細を示す。まず、データ提供者管理テーブルから、相手車両に関するエントリを削除する（Ｓ９０２）。そして、自車両が保持しているデータのそれぞれについて、以下の処理（Ｓ９０６−Ｓ９０８）を繰り返す。まず、相手車両がこのデータを保持している、すなわち、状態更新通知メッセージ内のこのデータのデータＩＤが存在するか判断する（Ｓ９０６）。そして、この条件に該当する場合には、この送信車両を当該データの提供者であるとしてデータ提供者管理テーブルを更新する（Ｓ９０８）。以上の処理によって、データ提供者管理テーブルの更新が完了する。なお、ここでは相手車両に関するエントリを全削除してから再度追加する手法を採用したが、もちろん、それ以外のアルゴリズムによってテーブルの更新を行ってもかまわない。
【００６２】
図８のフローチャートの説明に戻る。状態通知メッセージの送信元車両（相手車両）と、走行経路が同一方向ではない、または、走行経路に十分な重なりがない場合（Ｓ８０６−ＮＯ）には、走行経路が逆方向で、かつ、走行経路に十分な重なりがあるか判断する（Ｓ８１０）。ここでの「十分な重なり」というのは、今後の互いの位置関係の類推から、両車両が実際にすれ違う可能性が高いと予測できることを意味する。走行経路が重なっていても実際にはすれ違わないことは想定できるため、このような判断を行っている。簡単な実装では、両車両の走行経路に所定距離以上の重複があり、かつ、互いの距離が所定値以内である場合に「走行経路が十分に重なっている」と判断する。この判断基準はステップＳ８０６の基準と同様のものであるが、両者の判断基準は必ずしも同じにする必要はなく、それぞれ異なる判断基準で「走行経路が十分に重なっている」と判断してかまわない。
【００６３】
状態通知メッセージの相手車両と走行経路が逆方向であり、かつ、十分な重なりがある場合（Ｓ８１０−ＹＥＳ）には、自車両から相手車両に対してデータの提供が可能である。したがって、相手車両が自車両の保持するデータを必要とするのであれば、相手車両をこのデータの要求者であると判断できる。状況取得部２３は、このようにして状態記憶部２１内のデータ要求者管理テーブルを更新する（Ｓ８１２）。
【００６４】
図１０に、上記のデータ要求者管理テーブルの更新処理の詳細を示す。データ要求者管理テーブルから、相手車両に関するエントリを削除する（Ｓ１００２）。各車両は、走行経路近傍の情報を必要とすると考えられる。そこで、自車両が保持するデータのうち、相手車両の走行経路近傍に関連づけられたデータであり、かつ、相手車両が保持していないデータが、相手車両から要求されると考えることができる。そこで、相手車両の走行予定経路のそれぞれの位置ついて、以下の処理（Ｓ１００６−Ｓ１０１０）を繰り返し実行する。まず、自車両がこの位置に関連するデータを保持しているか判断し（Ｓ１００６）、自車両が保持している場合には、相手車両が保持しているか判断する（Ｓ１００８）。相手車両が保持していない場合には、相手車両がこのデータの要求者であるとして、データ要求者管理テーブルを更新する（Ｓ１０１０）。なお、図１０のフローチャートでは相手車両の走行経路内の位置ごとにループ処理を実行しているが、自車両が保持するデータご
とに、これが相手車両の走行経路の近傍に位置し、かつ、相手車両が保持していないことを確認してもかまわない。
【００６５】
なお、相手車両がどのデータを実際に必要とするかを正確に判断するのは困難である。上記の手法も完全なものではなく、他の方法によって相手車両がどのようなデータを必要とするか判断することも考えられる。一つの方法としては、状態通知メッセージの送信元車両が、メッセージ内にどのようなデータが必要となるかを明示的に記載する方法である。この方法によれば、相手車両が必要としないデータについて相手車両をデータ要求者と判断することがなくなる。ただし、各車両が今後どのようなデータが必要になるかを事前にわかる必要がある。別の方法としては、相手車両の走行経路にかかわらず、相手車両が保持していないデータは全て相手車両が必要とすると見なすことが考えられる。この方法は、実際には必要とされないデータについて相手車両をデータ要求者であると判断してしまうが、処理が簡単であるという利点がある。
【００６６】
図８のフローチャートの説明に戻る。自車両の走行経路と状態通知メッセージ送信元車両の走行経路とが同一方向に重複し、かつ、重複するデータを保持している場合（Ｓ８１４−ＹＥＳ）に、自車両が保持する重複するデータ保持していることを示す重複データ保持通知を送信元車両に送信する（Ｓ８１６）。すなわち、相手車両がデータ提供者であると判断された場合に、自車両もそのデータを提供可能であることを相手車両に通知する。この通知には、走行経路、保持データ情報、位置情報などの情報、すなわち、状態通知メッセージと同様の情報を含めることも好ましい。
【００６７】
ステップＳ８１４，Ｓ８１６の処理は、自車両がデータ提供者に該当することを相手車両に通知するためのものである。状態通知メッセージが走行経路に沿ってルーティングされると、走行経路上流側の車両がデータ提供者に該当することを判断できても、走行経路下流の車両がデータ提供者に該当することが判断できない。そこで、走行経路下流の車両から上流の車両に対して、重複するデータについてデータ提供可能である旨を通知することとしている。なお、「データ提供者」の判断基準から、車両Ａが車両Ｂの保持するデータのデータ提供者であれば、車両Ａにとっても車両Ｂがこのデータのデータ提供者となる。下流側車両からの重複データ保持通知を受信した上流側車両は、下流側車両を重複しているデータのデータ提供者であるとして、データ提供者管理テーブルを更新する。
【００６８】
なお、ステップＳ８１６において、下流側車両は状態通知メッセージを上流側車両に送信しても良い。すなわち、下流側車両がどのデータのデータ提供者であるかを上流側車両が判断するようにしても良い。この場合は、下流側車両からの状態通知メッセージを受信した上流側車両は、図９に示すフローチャートを実行してデータ提供者管理テーブルを更新する。
【００６９】
また、ステップＳ８１４，Ｓ８１６の処理は状態通知メッセージを走行経路の下流方向にルーティングさせる場合に必要となる処理であるので、状態通知メッセージを特定方向にルーティングさせない場合には不要な処理である。
【００７０】
ステップＳ８１８では、状態通知メッセージの転送が必要であるか判断し、必要であればその転送を行う。たとえば、状態通知メッセージに中継車両（のＩＤ）が格納されているのであれば、自車両が中継車両として指定されている場合に、状態通知メッセージの転送を行う。状態通知メッセージをフラッディング方式で送信する場合には、自車両が状態通知メッセージに格納される走行経路の下流方向に位置する場合に転送すればよい。なお、フラッディングによる不要な通信を防止するために、一度受信したことのある状態通知メッセージは転送しない、一つのメッセージに対して転送回数の上限、配信距離（送信元車両との直線距離や経路に沿った距離）の上限や、交差点ノードの経由数の上限などを設
けることが好ましい。
【００７１】
［キャッシュ管理処理］
ここまで説明したように、状態通知メッセージを車両間で交換することで、周囲の車両に関する情報（図４Ｃの近傍車両管理テーブル）、自車両が保持するデータについてのデータ要求者（図４Ｄのデータ要求者管理テーブル）およびデータ提供者の情報（図４Ｅのデータ提供者管理テーブル）を常に把握できる。キャッシュ管理部２４は、これらの情報を用いて、キャッシュメモリ２５から破棄するデータを決定する（図５のＳ５１６）。
【００７２】
図１１にキャッシュ管理部２４が行うキャッシュ管理処理のフローチャートを示す。この処理は、データ取得部２６が新しいデータを外部から取得するたびに実行される。キャッシュ管理部２４は、新たなデータが取得されると、保持データがキャッシュメモリ２５のキャッシュサイズの上限を超えるか判断する（Ｓ１１０２）。新しいデータを格納してもキャッシュサイズを超えない場合（Ｓ１１０２−ＮＯ）は、そのデータをキャッシュメモリ２５に格納する（Ｓ１１０６）。
【００７３】
一方、保持データの合計がキャッシュサイズを超える場合（Ｓ１１０２−ＹＥＳ）は、いずれかのデータをキャッシュメモリ２５から削除する。キャッシュメモリを有効利用するには今後参照されないと予想されるデータを削除することが好ましい。本実施形態では、データ要求者数が多いデータほど、また、データ提供者数が少ないデータほど優先的にキャッシュメモリに保持するようにする。データ要求者数が多いデータほど、他の車両からデータの要求を受け付ける可能性が高いためである。また、データ提供者が多ければ自車両がキャッシュメモリから削除しても他の提供者が提供可能と考えられるためである。
【００７４】
本実施形態においては、キャッシュ管理部２４は、データ要求者数とデータ提供者数を考慮した削除優先度と、既存のＬＲＵ（Least Recently Used）アルゴリズムによる削除
優先度と組み合わせて、キャッシュメモリから削除するデータを決定する。すなわち、下記の式１で表される削除優先度指標の値が最も大きいデータを、キャッシュメモリから削除して（Ｓ１１０４）、新たなデータをキャッシュメモリに格納する（Ｓ１１０６）。
【数１】
ここで、ＬはＬＲＵにおける削除優先度（最終利用時刻から現在までの経過時間）、Ｎｒはデータ要求者数、Ｎｐはデータ提供者数を表す。αは０≦α≦１で与えられる重み付け係数である。
【００７５】
重み付け係数を変えることで、ＬＲＵの振る舞いと、データ要求者数やデータ提供者数に対する考慮の度合いを調整できる。α＝０とおくことで通常のＬＲＵの振る舞いとなり、α＝１とおくことでデータ要求者数やデータ提供者数のみを考慮する振る舞いとなる。
【００７６】
なお、キャッシュアルゴリズムは上記の式以外にも種々の方法が採用可能である。基本的には、他の条件が同じであるときに、データ要求者数が多いほど削除優先度が低くなり、データ提供者数が少ないほど削除優先度が低くなるようなアルゴリズムであれば、キャッシュメモリを有効活用できると考えられる。たとえば、以下の式２のようにデータ要求者数とデータ提供者数を独立に評価した削除優先度を採用することが考えられる。
【数２】
ここで、０≦α，β，γ≦１かつα＋β＋γ＝１である。
【００７７】
またここでは既存のキャッシュアルゴリズムとしてＬＲＵを例に説明したが、ＬＦＵ（Least Frequently Used）やＡＲＣ（Adaptive Replacement Cache）などの任意のキャッ
シュアルゴリズムを採用して良い。
【００７８】
＜動作例＞
図１２，１３を参照して、具体的な状況での動作例を説明する。図１２は、ここでの説明における状況を説明する図である。図１２において、Ｎｉは交差点ノードＩＤを表し、Ｃｉは車両ＩＤ、ＤｉはデータＩＤを表す。各車両Ｃｉは図に示す位置に存在し、点線がその走行予定経路である。データＤｉは図に示す位置に関連づけられているものとする。
【００７９】
図１３は、各車両の現在の状態（走行経路、保持データ、位置情報）を示している。すなわち、図１３に示した情報は、各車両から送信される状態通知メッセージに含まれる情報である。車両Ｃ１の走行予定経路は、図１２に示されるように、（Ｎ０，Ｎ２，Ｎ３，Ｎ４，Ｎ５）である。また、車両Ｃ１は、データＤ１，Ｄ２，Ｄ３，Ｄ４をキャッシュメモリ内に保持しているものとする。また車両Ｃ１の位置は緯度Ｘ１、経度Ｙ１とする。他の車両Ｃ２〜Ｃ５についても、図１３に示すような走行経路、保持データ、位置情報を持つものとする。
【００８０】
車両Ｃ１から送信される状態通知メッセージは、車両Ｃ１の走行経路Ｎ０，Ｎ２，Ｎ３，Ｎ４，Ｎ５に沿ってルーティングされる。例えば、車両Ｃ１が、車両Ｃ２およびＣ３を中継車両として送信しても良いし、車両Ｃ１はブロードキャスト送信し車両Ｃ２，Ｃ３が自律的に転送するようにしても良い。
【００８１】
車両Ｃ１から送信される状態通知メッセージを受信した各車両では以下の判断がなされる。車両Ｃ２，Ｃ３では、走行経路が同一方向であり十分な重なりがあると判断され（図８のステップＳ８０６−ＹＥＳ）、データ提供者管理テーブル更新処理が実行される。車両Ｃ４では、走行経路が逆方向であり十分な重なりがあると判断され（ステップＳ８１０−ＹＥＳ）、データ要求者管理テーブル更新処理が実行される。車両Ｃ５では、走行経路に十分な重なりがないと判断され（Ｓ８０６−ＮＯかつＳ８１０−ＮＯ）、管理テーブルの更新処理は行われない。
【００８２】
車両Ｃ２は、車両Ｃ１から状態通知メッセージを受信したときにデータ提供者管理テーブル更新処理（図９）を実行する。ここで、図１３に示すように、車両Ｃ２はデータＤ１，Ｄ２を保持しており、これらのデータについては車両Ｃ１も保持している。したがって、車両Ｃ２は、車両Ｃ１がデータＤ１およびＤ２のデータ提供者であると判断できる（Ｓ９０６−Ｓ９０８）。なお、車両Ｃ２は、車両Ｃ１に対して自車両がデータＤ１およびＤ２を提供可能である旨を通知する（Ｓ８１６）。したがって、車両Ｃ１も、車両Ｃ２がデータＤ１およびＤ２のデータ提供者であると判断できる。
【００８３】
車両Ｃ３も車両Ｃ２と同様の処理を行い、車両Ｃ１がデータＤ２およびＤ４のデータ提供者であると判断する。また、車両Ｃ１に対して、車両Ｃ３がデータＤ２およびＤ４のデータ提供者である旨の通知も行われる。
【００８４】
また、車両Ｃ１は、車両Ｃ４から状態通知メッセージを受信したときにデータ要求者管理テーブル更新処理（図１０）を実行する。車両Ｃ４の走行経路はＮ６，Ｎ４，Ｎ３，Ｎ２，Ｎ１である。車両Ｃ１は、この経路近傍の位置に関連づけられたデータのうち、データＤ１，Ｄ２，Ｄ３を保持している。このうち、車両Ｃ４はデータＤ３を保持し、データＤ１およびＤ２を保持していない。したがって、車両Ｃ１は、車両Ｄ４をデータＤ１およびＤ２のデータ要求者であると判断して、データ要求者管理テーブルを更新する（Ｓ１００６〜Ｓ１０１０）。
【００８５】
上記のような処理の結果として得られる、車両Ｃ１のデータ要求者管理テーブルとデータ提供者管理テーブルを図１４Ａ，Ｂに示す。図１４Ａに示すように、車両Ｃ１は、データＤ１およびＤ２の要求者が車両Ｃ４であり、データＤ３およびＤ４については要求者が存在しないと記憶する。また、図１４Ｂに示すように、車両Ｃ１は、データＤ１の提供者が車両Ｃ２、データＤ２の提供者が車両Ｃ２とＣ３、データＤ３の提供者は存在せず、データＤ４の提供者は車両Ｃ３であると記憶する。
【００８６】
車両Ｃ１は、このようなデータ要求者管理テーブルとデータ提供者管理テーブルに基づいてキャッシュ管理処理を行う。上述の式１に基づいて算出される削除優先度のうち、データ要求者数とデータ提供者数に基づく項目の値は図１４Ｃに示すようになる。データＤ１については、データ要求者数が１台で、データ提供者数が１台であることから、削除優先度は１と算出される。データＤ２については、データ要求者数が１台で、データ提供者数が２台であることから、削除優先度は１．５と算出される。データＤ３については、データ要求者数が０台で、データ提供者数が０台であることから、削除優先度は１と算出される。データＤ４については、データ要求者数が０台で、データ提供者数が１台であることから、削除優先度は２と算出される。したがって、車両Ｃ１はキャッシュメモリからデータを削除する必要が生じたときに、ＬＲＵによる削除優先度等が等しければ、削除優先度の最も高いデータＤ４を削除するように決定する。
【００８７】
各車両は、データが上位プログラムからデータを要求されたときに、データがキャッシュメモリ内にあればそこから取得して上位プログラムに渡す（Ｓ５０６）。キャッシュメモリに無い場合には、近傍車両管理テーブル（図４Ｃ）を参照して、周囲のこのデータを保持する車両が存在するか判断し、存在する場合にはその車両から取得する（Ｓ５１０）。サーバ装置からデータを取得するのは、自車両のキャッシュメモリにも周囲の車両のキャッシュメモリにも要求されたデータが存在しないときとなる（Ｓ５１４）。
【００８８】
＜実施形態の作用／効果＞
本実施形態によれば、サーバ装置から配信されるデータを車両内にキャッシュし、車両間でデータの送信を行うことで、サーバ装置との通信帯域を削減することができる。そして、車両におけるキャッシュ管理を要求者が多く提供者が少ないほど優先してキャッシュメモリに残るように行っているので、キャッシュヒット率が高まり、限られた容量のストレージを有効活用できる。
【符号の説明】
【００８９】
１００ 車両
２００ サーバ装置
２０ キャッシュ管理機能
２１ 状態記憶部
２２ 状態通知部
２３ 状態取得部
２４ キャッシュ管理部
２５ キャッシュメモリ
２６ データ取得部
２７ データ送信部
３０ ナビゲーションプログラム
【技術分野】
【０００１】
本発明は、キャッシュ管理技術に関し、特に、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおけるキャッシュ管理技術に関する。
【背景技術】
【０００２】
地図情報のように位置に関連するデータ（以下、「データ」と呼ぶ）を配信するサービス（以下、「位置情報サービス」と呼ぶ）が普及しつつある。これに伴い、データ提供元である、クライアント・サーバ型システムにおけるサーバ装置や、インフラ協調型システムにおける路側基地局（以下、これらを総称してサーバ装置と呼ぶ）に必要とされる通信帯域は年々増加する傾向にある。
【０００３】
一般に、サービス提供者が通信業者に支払う通信料金は従量課金制である場合が多く、必要とされる通信帯域が大きくなりすぎると、サービス提供のコストが増大してしまう。または、通信帯域の逼迫によりサービス品質に支障が生じてしまう。したがって、クライアント（車両）とサーバ装置との間の通信帯域を削減することが望まれる。
【０００４】
特許文献１では、複数の車載機が、サーバにアクセスしてデータの異なる部分を分担して取得し、取得した部分データを車車間通信により相互に交換することで完全なデータを形成する方法が開示されている。この方法では、直接通信可能な状態にある車両でしかデータの交換ができず、サーバの通信帯域の削減効果は限定的である。
【０００５】
上記の問題を考慮してマルチホップ型のピア・ツー・ピア通信を行い、直接通信できない車載機間でデータの交換を行う方法が考えられる。しかし、この方法を単純に適用した場合、データを複数の車載機を経由してルーティングすることになり、通信経路上の車載機の通信帯域をより多く消費してしまう。この方法では、車載機の数やホップ数が増えた場合に、通信量が許容範囲を超えてしまうため、サーバの通信帯域の削減効果は限定的である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００４−２７４４１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記を考慮して、車載機が取得したデータをストレージに保存しておき、移動先で、そのデータを将来必要とすると予想される車載機に配信する方法が考えられる。しかしこの方法は、車載機のストレージに保持できるデータ量の限界が問題となる。３次元地図情報などのように巨大なデータを扱う場合、保持しておくデータを適切に取捨選択しなければ、ストレージがあふれてしまう。
【０００８】
このように、車載機がデータを保持してサーバ装置に代わって他の車両に配信する場合は、車載機のストレージ容量は有限なので、より重要なデータを優先的に保持することが求められる。
【０００９】
本発明は、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおいて、他の車両に配信するためにデータを車両内にキャッシュする際にキャッシュヒット率を向上させるようにキャッシュ管理することを目的とする。
【課題を解決するための手段】
【００１０】
上記の目的を達成するために、本発明に係るキャッシュ管理装置は、周囲の車両から送信される走行予定経路情報と保持データ情報を基に、自車両が保持しているデータのそれぞれについてデータ要求者数とデータ提供者数を算出し、データ要求者数が多いデータほど、また、データ提供者が少ないデータほど優先的にキャッシュメモリに保持する。
【００１１】
より具体的には、本発明に係るキャッシュ管理装置は、複数の車両とサーバ装置から構成され、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおける、車両に搭載されたキャッシュ管理装置であって、キャッシュメモリと、キャッシュ管理手段と、状態通知手段と、状態取得手段と、データ取得手段と、データ送信手段を備える。
【００１２】
状態通知手段は、自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する。すなわち、状態通知手段は、自車両が今後どのような経路を走行するかという情報と、自車両がどのようなデータを保持しているかという情報を、周囲の車両に対して送信する。状態通知メッセージには位置情報や走行速度など、車両の走行に関するその他の情報を含めることも好ましい。
【００１３】
状態取得手段は、周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する。すなわち、状態取得手段によって、周囲の車両が今後どのような経路を走行するかということと、どのようなデータを保持しているかということを認識できる。
【００１４】
データ取得手段は、自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得する。また、データ送信手段は、他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信する。
【００１５】
ここで、本発明の状態取得手段は、他車両から受信した状態通知に基づいて、以下の二つの判断を行う。
（１）他車両（状態通知メッセージの送信元車両）と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータをこの他車両も保持している場合は、この他車両をこのデータのデータ提供者であると判断する。
（２）他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータをこの他車両が保持していない場合は、この他車両をこのデータのデータ要求者であると判断する。
この処理を周囲の車両から送信される状態通知メッセージの全てに対して行うことで、自車両が保持しているデータのそれぞれについて、データ提供者の数とデータ要求者の数を把握することができる。
【００１６】
そして、本発明のキャッシュ管理手段は、キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する。
【００１７】
これにより、各車両のキャッシュメモリには、データ要求者の数が多いデータほど、また、データ提供者の数が少ないデータほど優先的に格納されることになる。したがって、キャッシュヒット率を向上させることができる。
【００１８】
上記の状態通知メッセージは、送信元車両の走行予定経路に沿ってルーティングされることが好ましい。なぜならば、データ要求者やデータ提供者に該当するかは、走行予定経路に重複があるか否かによって判断されるためである。走行予定経路から大きくずれる場所に位置する車両がデータ要求者やデータ提供者に該当する可能性は低く、状態通知メッセージをその位置に送信しても無駄に通信帯域が消費されるだけである。走行予定経路に沿ってルーティングすることで、通信帯域の浪費を防止できる。ただし、現時点では走行予定経路に位置しない車両と将来的に走行経路が重複することはあるので、走行予定経路とその周辺の範囲に状態通知メッセージが送信されるようにしても良い。
【００１９】
走行予定経路に沿ってルーティングさせるために、送信元の車両の状態通知手段が状態通知メッセージをブロードキャスト送信し、以下の基準で受信車両が転送を行うことが好ましい。すなわち状態通知メッセージの受信車両の状態取得手段は、自車両がこの状態通知メッセージに含まれる走行予定経路上に位置し、かつ、走行予定経路上流の車両から状態通知メッセージを受信した場合に、受信した状態通知メッセージを転送すればよい。なお、通信帯域の逼迫を避けるために、一度受信したことのある状態通知メッセージは転送しないとか、転送回数に上限を設けるとか、送信元車両から所定の距離内の場合のみ転送するとかという基準を設けることも好ましい。
【００２０】
また、走行予定経路に沿ってルーティングさせるための別の方法として、送信元の車両の状態通知手段が、自車両の走行予定経路上の車両を中継車両として指定して状態通知メッセージを送信することも好ましい。
【００２１】
なお、状態通知メッセージを走行予定経路にそってルーティングする場合は、状態通知メッセージは走行予定経路上流（後方）に対しては伝わらないことになる。したがって、同じ走行予定経路を走行中の二台の車両が同じデータを保持している場合に、下流の車両は上流の車両がこのデータのデータ提供者であることが判断できるが、上流の車両は下流の車両がこのデータのデータ提供者であると判断できないことになってしまう。これに対処するために、状態通知メッセージを受信し、送信元車両が自車両の保持するいずれかのデータについてのデータ提供者であると判断したときに、自車両がこのデータのデータ提供者であることを通知する重複データ保持通知を送信元の車両に対して送信することが好ましい。
【００２２】
また、状態取得手段は、状態通知メッセージ送信元の他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持し、かつ当該他車両の走行予定経路近傍のデータであって、当該他車両が保持していないデータについて、当該他車両を当該データのデータ要求者であると判断することが好ましい。すなわち、自車両が保持している全てのデータを対象としてデータ要求者であるか否かを判断するのではなく、自車両が保持しかつ相手車両の走行予定経路近傍のデータのみを対象としてデータ要求者であるか否かを判断する。走行予定経路近傍に関連づけられていないデータを要求することは少ないと考えられるので、これにより、さらに精度の良いキャッシュ管理が可能となる。
【００２３】
また、キャッシュ管理手段は、データ要求者数およびデータ提供者数を利用せずに求めた指標と、データ要求者数およびデータ提供者数を利用して求めた指標の両方を用いて、削除するデータを決定することも好ましい。「データ要求者数およびデータ提供者数を利用せずに求めた指標」には、ＬＲＵ（Least Recently Used）、ＬＦＵ（Least Frequently Used）、ＡＲＣ（Adaptive Replacement Cache）などの従来のアルゴリズムにしたがって求めた指標を採用することができる。
【００２４】
本発明は、上記手段の少なくとも一部を含むキャッシュ管理装置として捉えることができる。また、本発明は、車載端末においてこれらの処理を行うキャッシュ管理方法、さらには、これらの方法を実現するためのプログラムとして捉えることもできる。また、本発明は、上記キャッシュ管理装置を備える車両と位置に関連するデータを配信するサーバ装置とから構成されるデータ配信システムとして捉えることもできる。上記手段および処理の各々は可能な限り互いに組み合わせて本発明を構成することができる。
【発明の効果】
【００２５】
本発明によれば、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおいて、他の車両に配信するためにデータを車両内のキャッシュを有効活用でき、サーバ装置との間の通信を削減可能となる。
【図面の簡単な説明】
【００２６】
【図１】本実施形態に係るデータ配信システムの概要図。
【図２】本実施形態に係る車載端末のハードウェア構成図。
【図３】本実施形態に係る車載端末の機能ブロック図。
【図４】（Ａ）経路情報のデータ形式。（Ｂ）保持データ情報のデータ形式。（Ｃ）近傍車両管理テーブルのテーブルフォーマット。（Ｄ）データ要求者管理テーブルのテーブルフォーマット。（Ｅ）データ提供者管理テーブルのテーブルフォーマット。
【図５】上位プログラムからデータ要求を受け付けたときに実行される、データ取得処理のフローチャート。
【図６】定期的あるいは不定期に実行される状態通知メッセージ送信処理のフローチャート。
【図７】状態通知メッセージのフォーマット。
【図８】状態通知メッセージを受信したときに実行される処理のフローチャート。
【図９】データ提供者管理テーブル更新処理（図８のＳ８０８）の詳細なフローチャート。
【図１０】データ要求者管理テーブル更新処理（図８のＳ８１２）の詳細なフローチャート。
【図１１】キャッシュ管理処理（図５のＳ５１６）のフローチャート。
【図１２】本実施形態の動作例説明の前提となる状況を説明する図。
【図１３】図１２に示す状況での状態通知メッセージを示す図。
【図１４】図１２に示す状況で車両Ｃ１によって作成される（Ａ）データ要求者管理テーブルと（Ｂ）データ提供者管理テーブル。（Ｃ）はデータ要求者数とデータ提供者数を考慮したキャッシュの削除優先度の値を示す。
【発明を実施するための形態】
【００２７】
＜概要＞
図１は本実施形態に係るデータ配信システムの概要を示す図である。データ配信システムは、複数の車両１００と、データを配信するサーバ装置２００とから構成される。サーバ装置２００は、車両１００に送信するためのデータ２０１を保持しており、車両１００からの要求に応じてデータを車両に配信する。ここで、データは位置に関連したデータであり、たとえば、３次元地図データ、店舗情報、広告情報などであるが、データの内容は本発明では限定されない。
【００２８】
車両１００は基本的にサーバ装置２００からデータを取得するが、取得したデータをキャッシュメモリに保持しておき、自車が必要とするデータを周囲の車両が保持していれば、サーバ装置２００からではなく、周囲の車両からこのデータを取得する。これによって、サーバの通信帯域を削減することができる。
【００２９】
なお、図１では車両１００とサーバ装置２００が無線通信を直接行うように記載しているが、サーバ装置２００と通信可能に接続された路側通信設備を設けて、車両はこの路側通信設備からデータを取得する構成としても良い。また、車両１００間の通信はマルチホップの通信を行うものとするが、データの取得はシングルホップあるいは限られたホップ数の通信に限定して車車間通信による通信帯域の逼迫を避けることが好ましい。
【００３０】
このような仕組みにおいて、車両内のキャッシュを有効に活用するためには適切なキャッシュアルゴリズムの採用が必須である。基本的には、他の車両から必要とされるデータを優先的に保持しておけばよく、また、自車両のみが提供できるデータを優先的に保持しておけばよい。本実施形態においては、各車両が、自車両の走行予定経路と、自車両がどのデータをキャッシュしているかという情報を周囲の車両に対して通知する。これにより、各車両は、周囲の車両がどのような経路を走行し、かつ、どのようなデータを保持しているかを把握することができる。そして、このように把握された状況に基づいて、自車両が保持しているデータのそれぞれについて、このデータを要求している車両の数、および、このデータを提供できる他の車両の数を算出し、これに基づいてキャッシュ管理を行う。
【００３１】
＜構成＞
図２に車両１００に搭載される車載端末のハードウェア構成を示す。また、図３に車載端末の機能構成を示す。図２に示すように、車載端末は、ＣＰＵ１、位置検出装置群２、表示装置７、音声出力装置８、入力装置９、車車間通信装置１３、路車間通信装置１４などを含んで構成される。これらの装置は車内ネットワークやシステムバスなどを介してＣＰＵ１と接続されている。
【００３２】
位置検出装置群２は、衛星などからの電波に基づいて車両の位置を検出するＧＰＳ（Global Positioning System）受信機３、車両の回転角速度を検出するジャイロセンサ４、
車両の向きを取得するための地磁気センサ５，車両の走行距離を検出する距離センサ６を有している。これらのセンサから取得される情報や、地図情報とのマッチング（マップマッチング）などにより自車両の位置を検出できる。
【００３３】
表示装置７は液晶ディスプレイなどであり、音声出力装置８はスピーカーである。入力装置９は、ユーザからの指示を入力するためのものであり、ボタンやスイッチあるいは、キーボードやマウスなどを採用可能である。また、表示装置７と入力装置９を一体化したタッチパネルを採用してもかまわない。また、音声入力装置を採用しても良い。
【００３４】
車車間通信装置１３は他の車両（の車車間通信装置）と無線通信を行うための装置である。無線通信方式には、例えば、無線ＬＡＮ（ＩＥＥＥ８０２．１１ａ，ｂ，ｇ，ｎ）、ＤＳＲＣ（Dedicated Short Range Communication）、ＵＷＢ、ミリ波通信などを採用可
能である。路車間通信装置１４は、サーバ装置と無線通信を行うための装置である。無線通信方式には、ＷｉＭＡＸやＬＴＥを採用可能である。なお、車両とサーバ装置が路側通信設備を介して通信を行う場合には、その他の狭域な無線通信方式を採用しても良い。
【００３５】
ＣＰＵ１は、ＲＯＭ１０や補助記憶装置１２などに格納されたＯＳプログラムやアプリケーションプログラムをＲＡＭ１１上に展開して実行することで、図３に示すような種々の機能を実現する。
【００３６】
キャッシュ管理機能２０は、ナビゲーションプログラム３０などの上位プログラムからのデータ要求を受けて、キャッシュメモリ２５またはサーバ装置や他の車両からデータを取得して上位プログラムに返す機能を有する。ナビゲーションプログラム３０は、位置検出装置群２による自車両の位置検出や経路探索などの周知の処理を行う。キャッシュ管理
機能２０は、次のような機能部から構成される。
【００３７】
状態記憶部２１は、自車両および周囲の車両に関する状態を記憶する。具体的には、各車両について、今後どのような経路を走行するかという経路情報、どのようなデータを保持しているかという保持データ情報、および、どの位置にいるのかという位置情報を格納する。なお、自車両の経路情報および位置情報は、例えば、ナビゲーションプログラム３０から取得することができる。ナビゲーションプログラムでは、走行経路の探索や設定がなされるのでこの経路をキャッシュ管理機能２０へ通知すればよい。また、自車両がどのようなデータを保持しているかは、キャッシュ管理部２４から取得できる。
【００３８】
経路情報は、図４Ａに示すように、ノードＩＤ（交差点ＩＤ）のリストとして表現される。経路情報は、リンクＩＤのリストとして表現されてもかまわない。
【００３９】
サーバ装置から配信されるデータには、それぞれのデータを識別可能なデータＩＤが付与される。このデータＩＤから、そのデータがどの位置に関連づけられているか判断可能とすることが好ましい。例えば、データＩＤの一部に位置を示す識別子を含むことが好ましい（データＩＤ＝エリアＩＤ＋識別番号）。保持データ情報は、図４Ｂに示すように、各車両がキャッシュメモリ内に保持しているデータのデータＩＤのリストとして表現される。
【００４０】
状態記憶部２１には、図４Ｃに示すような、周囲の車両を管理するための近傍車両管理テーブルが格納される。近傍車載機管理テーブルには、車両ＩＤ（または車載機ＩＤ）、保持データ情報、経路情報、位置情報が格納される。
【００４１】
状態記憶部２１には、さらに、自車両が有する各データについて、そのデータを要求していると考えられる車両を格納したデータ要求者管理テーブル（図４Ｄ）、および、そのデータを提供可能と考えられる車両を格納したデータ提供者管理テーブル（図４Ｅ）も格納される。これらのテーブルは、自車両が有するデータごとに、車両ＩＤのリストとして構成される。これらのテーブルについての詳細は後述する。
【００４２】
状態通知部２２は、定期的あるいは不定期に自車両の状態（経路情報、保持データ情報、位置情報など）を周囲の車両に通知するための機能部である。なお、状態情報として、走行速度やその他の情報を含めることも好ましい。状態通知部２２は、車車間通信装置１３から状態通知メッセージを送信することで、周囲の車両へ自車両の状態変更を通知する。この状態通知メッセージの伝播経路は、送信元車両の経路に沿うことが好ましい。そのために、状態通部２２が送信経路または中継車両を指定して状態通知メッセージを送信しても良いし、状態通知メッセージの受信車両がメッセージ内に格納された経路情報と自車の位置を基に自律的に中継するか否かを決定しても良い。
【００４３】
状態取得部２３は、周囲の車両から送信される状態通知メッセージを車車間通信装置１３によって受信して、状態記憶部２１を更新するための機能部である。状態取得部２３が周囲の車両から状態通知メッセージを受信して状態記憶部２１を更新することで、状態記憶部２１の内容が最新に保たれる。状態取得部２３は、受信した状態通知メッセージに自車両が中継車両として指定されていたり、状態通知メッセージに含まれる経路情報と自車両の位置を比較により必要ありと判断できたりする場合は、この状態通知メッセージの転送を行う。また、状態通知メッセージが走行予定経路（以下単に、走行経路と称する）に沿ってルーティングされると、状態通知メッセージによる情報は走行経路下流方向にのみ伝播するので、自車両が送信元車両の有するデータのデータ提供者である場合には、このことを別途通知する。
【００４４】
キャッシュ管理部２４は、キャッシュメモリ２５を管理する機能部であり、キャッシュメモリにデータを格納するための空き容量がないときに、いずれのデータをキャッシュメモリから削除するか決定する。キャッシュヒット率を高めるためには、将来使われる可能性の高いデータをキャッシュメモリに残すことが必要である。キャッシュ管理部２４は、データ要求者の数が多いデータほど、また、データ提供者の数が少ないデータほど優先してキャッシュメモリ内に残す制御を行う。また、データ要求者およびデータ提供者の数だけを考慮するのではなく、ＬＲＵやＬＦＵなどの従来のキャッシュアルゴリズムによる削除優先度も考慮して、いずれのデータをキャッシュメモリから削除するか決定する。
【００４５】
データ取得部２６は、上位プログラム３０からデータの要求を受け付け、要求されたデータを取得して返す機能部である。データ取得部２６は、自車両のキャッシュメモリ内に要求されたデータがあればキャッシュメモリから取得して上位プログラムに渡す。一方、キャッシュメモリ内に要求されたデータがなければ、可能であれば車車間通信によって他の車両から、それもできなければ路車間通信によってサーバ装置からデータを取得して上位プログラムに渡す。
【００４６】
データ送信部２７は、他の車両からデータの要求を受け付けて、キャッシュメモリ２５内にそのデータがあれば、要求元の車両にデータを送信する。キャッシュメモリ２５内に要求されたデータがない場合には、何も行わないか、データを保持していないことを通知する。
【００４７】
＜処理詳細＞
以下、各機能部が行う処理の内容について、より詳細に説明する。
【００４８】
［データ取得処理］
まず図５を参照して、ナビゲーションプログラムなどの上位プログラムからデータ取得要求を受け付けたときの処理を説明する。データ取得部２６が上位プログラム３０からデータ取得要求を受け付ける（Ｓ５０２）と、以下の処理が行われる。データ取得部２６は、要求されたデータがキャッシュメモリ２５内に存在するか否かを、キャッシュ管理部２４に問い合わせる（Ｓ５０４）。要求されたデータがキャッシュメモリ２５内に存在する場合（Ｓ５０４−ＹＥＳ）には、キャッシュメモリからデータを取得する（Ｓ５０６）。
【００４９】
一方、要求されたデータがキャッシュメモリ２５内に存在しない場合（Ｓ５０４−ＮＯ）には、このデータを提供可能な車両が周囲に存在するか判定する（Ｓ５０８）。この判定は、近傍車両管理テーブルを参照することで判断できる。たとえば十分に近い位置に存在する車両（Ｎホップ以内（Ｎは設計パラメータ）で通信可能な車両）がデータを持っている場合に、この車両が要求されたデータを提供可能と判断する。周囲にデータの提供者が存在する場合（Ｓ５０８−ＹＥＳ）は、車車間通信によってこの車両からデータを取得する（Ｓ５１０）。周囲に要求されたデータを提供可能な車両が存在しない（Ｓ５０８−ＮＯ）か、周囲の車両にデータを要求したが所定時間内にデータが得られない場合（Ｓ５１２−ＮＯ）は、路車間通信によってサーバ装置２００からデータを取得する（Ｓ５１４）。
【００５０】
このようにして、周囲の車両またはサーバ装置からキャッシュメモリ内に存在しないデータを取得したら、取得したデータをキャッシュメモリに格納するキャッシュ管理処理を行う（Ｓ５１６）。ここで、キャッシュメモリに空き容量が無い場合には、参照される可能性が最も低いと考えられるデータをキャッシュメモリから削除する。キャッシュの削除アルゴリズムについては、その判断の基となる情報の取得方法を説明した後に改めて説明する。
【００５１】
データ取得部２６は、キャッシュメモリ、他の車両またはサーバ装置のいずれかから要求されたデータを取得し、取得したデータを要求元の上位プログラムへ渡す（Ｓ５１８）。
【００５２】
［状態通知送信処理］
次に図６を参照して、状態通知部２２が行う状態通知メッセージの送信処理について説明する。この処理は定期的あるいは不定期に実行される。たとえば、１００ミリ秒おきに実行するようにしても良いし、あるいは、自車両の状態（経路情報、保持データ情報、位置など）に変更があったときに実行するようにしても良い。
【００５３】
状態通知部２２は、キャッシュ内に格納されているデータのデータＩＤを取得する（Ｓ６０２）。本実施形態では、状態通知部２２が状態記憶部２１に格納されている自車両の保持データ情報を参照することで、キャッシュ内のデータの一覧を取得する。キャッシュ管理部２４がキャッシュに変更がある度に状態記憶部２１を更新する構成とすれば、状態記憶部２１内の自車両の保持データ情報を参照することでキャッシュメモリ内に格納されているデータの一覧を取得できる。もちろん、状態通知部２２がキャッシュ管理部２４に問い合わせてデータの一覧を取得しても良い。
【００５４】
状態通知部２２は、自車両の走行予定経路および位置情報を取得する（Ｓ６０４）。これらの情報はナビゲーションプログラムが保持しているので、ここから取得すれば良い。
【００５５】
状態通知部２２は、送信者ＩＤ（自車両の車載機ＩＤ）、経路情報、保持データ情報、および位置情報を含む状態通知パケット（図７）を作成し（Ｓ６０６）、車車間通信装置１３から送信する（Ｓ６０８）。状態通知パケットは、図７に示すように、送信者ＩＤ（車両ＩＤ）、経路情報、保持データ情報、および位置情報が含まれる。また、中継車両の指定やフラッディングを停止させる条件など、ルーティングに関する情報も含まれる。
【００５６】
本実施形態では、通信を中継する車載機（以下、中継者と呼ぶ）を経由することで、マルチホップ通信によって状態通知メッセージを伝播させる。この際、この状態通知メッセージは、自車両の走行経路にしたがって伝播するようにルーティングされる。すなわち、走行経路の上流から下流に向かって、状態通知メッセージを伝播させる。たとえば、自車両の走行経路上に位置する車両を中継者として選択して伝播させるか、フラッディングにより伝播させればよい。フラッディングを採用する場合には、受信者両側で自律的に中継するか否かを判断することで、走行経路に沿って伝播するようにする。
【００５７】
［状態通知受信時処理］
次に図８を参照して、状態取得部２３が行う、状態通知メッセージ受信時の処理について説明する。この処理は、状態取得部が他の車両から状態通知メッセージを受信するたびに実行される。なお、この項において、状態通知メッセージの送信元車両のことを「相手車両」と記載する。
【００５８】
相手車両から状態通知メッセージを受信する（Ｓ８０２）と、状態記憶部２１内の近傍車両管理テーブルの相手車両に関するエントリを、この状態通知メッセージに含まれる情報で更新する（Ｓ８０４）。
【００５９】
状態取得部２３は、状態通知メッセージに含まれる相手車両の走行経路と、自車両の走行経路が、同一方向であり、かつ、十分な重なりがあるか判断する（Ｓ８０６）。ここで、「十分な重なり」というのは、今後の互いの位置関係の類推から、すれ違う他の車載機の集合が近いと予測できることを意味する。すれ違う他車両の集合は、両車両の、走行経路、現在位置、進行速度などから判断できる。簡単な実装では、両車両の走行経路に所定
距離以上の重複があり、かつ、互いの距離が所定値以内である場合に、「走行経路が十分に重なっている」と判断する。
【００６０】
状態通知メッセージの送信元車両（相手車両）と走行経路が同一方向であり、かつ、十分な重なりがある場合（Ｓ８０６−ＹＥＳ）には、すれ違う他車両に対して、相手車両と自車両の両方がデータを提供可能である。したがって、相手車両が自車両の保持するデータを保持していれば、相手信元車両をこのデータの提供者であると判断できる。状況取得部２３は、このようにして状態記憶部２１内のデータ提供者管理テーブルを更新する（Ｓ８０８）。
【００６１】
図９に、上記のデータ提供者管理テーブルの更新処理の詳細を示す。まず、データ提供者管理テーブルから、相手車両に関するエントリを削除する（Ｓ９０２）。そして、自車両が保持しているデータのそれぞれについて、以下の処理（Ｓ９０６−Ｓ９０８）を繰り返す。まず、相手車両がこのデータを保持している、すなわち、状態更新通知メッセージ内のこのデータのデータＩＤが存在するか判断する（Ｓ９０６）。そして、この条件に該当する場合には、この送信車両を当該データの提供者であるとしてデータ提供者管理テーブルを更新する（Ｓ９０８）。以上の処理によって、データ提供者管理テーブルの更新が完了する。なお、ここでは相手車両に関するエントリを全削除してから再度追加する手法を採用したが、もちろん、それ以外のアルゴリズムによってテーブルの更新を行ってもかまわない。
【００６２】
図８のフローチャートの説明に戻る。状態通知メッセージの送信元車両（相手車両）と、走行経路が同一方向ではない、または、走行経路に十分な重なりがない場合（Ｓ８０６−ＮＯ）には、走行経路が逆方向で、かつ、走行経路に十分な重なりがあるか判断する（Ｓ８１０）。ここでの「十分な重なり」というのは、今後の互いの位置関係の類推から、両車両が実際にすれ違う可能性が高いと予測できることを意味する。走行経路が重なっていても実際にはすれ違わないことは想定できるため、このような判断を行っている。簡単な実装では、両車両の走行経路に所定距離以上の重複があり、かつ、互いの距離が所定値以内である場合に「走行経路が十分に重なっている」と判断する。この判断基準はステップＳ８０６の基準と同様のものであるが、両者の判断基準は必ずしも同じにする必要はなく、それぞれ異なる判断基準で「走行経路が十分に重なっている」と判断してかまわない。
【００６３】
状態通知メッセージの相手車両と走行経路が逆方向であり、かつ、十分な重なりがある場合（Ｓ８１０−ＹＥＳ）には、自車両から相手車両に対してデータの提供が可能である。したがって、相手車両が自車両の保持するデータを必要とするのであれば、相手車両をこのデータの要求者であると判断できる。状況取得部２３は、このようにして状態記憶部２１内のデータ要求者管理テーブルを更新する（Ｓ８１２）。
【００６４】
図１０に、上記のデータ要求者管理テーブルの更新処理の詳細を示す。データ要求者管理テーブルから、相手車両に関するエントリを削除する（Ｓ１００２）。各車両は、走行経路近傍の情報を必要とすると考えられる。そこで、自車両が保持するデータのうち、相手車両の走行経路近傍に関連づけられたデータであり、かつ、相手車両が保持していないデータが、相手車両から要求されると考えることができる。そこで、相手車両の走行予定経路のそれぞれの位置ついて、以下の処理（Ｓ１００６−Ｓ１０１０）を繰り返し実行する。まず、自車両がこの位置に関連するデータを保持しているか判断し（Ｓ１００６）、自車両が保持している場合には、相手車両が保持しているか判断する（Ｓ１００８）。相手車両が保持していない場合には、相手車両がこのデータの要求者であるとして、データ要求者管理テーブルを更新する（Ｓ１０１０）。なお、図１０のフローチャートでは相手車両の走行経路内の位置ごとにループ処理を実行しているが、自車両が保持するデータご
とに、これが相手車両の走行経路の近傍に位置し、かつ、相手車両が保持していないことを確認してもかまわない。
【００６５】
なお、相手車両がどのデータを実際に必要とするかを正確に判断するのは困難である。上記の手法も完全なものではなく、他の方法によって相手車両がどのようなデータを必要とするか判断することも考えられる。一つの方法としては、状態通知メッセージの送信元車両が、メッセージ内にどのようなデータが必要となるかを明示的に記載する方法である。この方法によれば、相手車両が必要としないデータについて相手車両をデータ要求者と判断することがなくなる。ただし、各車両が今後どのようなデータが必要になるかを事前にわかる必要がある。別の方法としては、相手車両の走行経路にかかわらず、相手車両が保持していないデータは全て相手車両が必要とすると見なすことが考えられる。この方法は、実際には必要とされないデータについて相手車両をデータ要求者であると判断してしまうが、処理が簡単であるという利点がある。
【００６６】
図８のフローチャートの説明に戻る。自車両の走行経路と状態通知メッセージ送信元車両の走行経路とが同一方向に重複し、かつ、重複するデータを保持している場合（Ｓ８１４−ＹＥＳ）に、自車両が保持する重複するデータ保持していることを示す重複データ保持通知を送信元車両に送信する（Ｓ８１６）。すなわち、相手車両がデータ提供者であると判断された場合に、自車両もそのデータを提供可能であることを相手車両に通知する。この通知には、走行経路、保持データ情報、位置情報などの情報、すなわち、状態通知メッセージと同様の情報を含めることも好ましい。
【００６７】
ステップＳ８１４，Ｓ８１６の処理は、自車両がデータ提供者に該当することを相手車両に通知するためのものである。状態通知メッセージが走行経路に沿ってルーティングされると、走行経路上流側の車両がデータ提供者に該当することを判断できても、走行経路下流の車両がデータ提供者に該当することが判断できない。そこで、走行経路下流の車両から上流の車両に対して、重複するデータについてデータ提供可能である旨を通知することとしている。なお、「データ提供者」の判断基準から、車両Ａが車両Ｂの保持するデータのデータ提供者であれば、車両Ａにとっても車両Ｂがこのデータのデータ提供者となる。下流側車両からの重複データ保持通知を受信した上流側車両は、下流側車両を重複しているデータのデータ提供者であるとして、データ提供者管理テーブルを更新する。
【００６８】
なお、ステップＳ８１６において、下流側車両は状態通知メッセージを上流側車両に送信しても良い。すなわち、下流側車両がどのデータのデータ提供者であるかを上流側車両が判断するようにしても良い。この場合は、下流側車両からの状態通知メッセージを受信した上流側車両は、図９に示すフローチャートを実行してデータ提供者管理テーブルを更新する。
【００６９】
また、ステップＳ８１４，Ｓ８１６の処理は状態通知メッセージを走行経路の下流方向にルーティングさせる場合に必要となる処理であるので、状態通知メッセージを特定方向にルーティングさせない場合には不要な処理である。
【００７０】
ステップＳ８１８では、状態通知メッセージの転送が必要であるか判断し、必要であればその転送を行う。たとえば、状態通知メッセージに中継車両（のＩＤ）が格納されているのであれば、自車両が中継車両として指定されている場合に、状態通知メッセージの転送を行う。状態通知メッセージをフラッディング方式で送信する場合には、自車両が状態通知メッセージに格納される走行経路の下流方向に位置する場合に転送すればよい。なお、フラッディングによる不要な通信を防止するために、一度受信したことのある状態通知メッセージは転送しない、一つのメッセージに対して転送回数の上限、配信距離（送信元車両との直線距離や経路に沿った距離）の上限や、交差点ノードの経由数の上限などを設
けることが好ましい。
【００７１】
［キャッシュ管理処理］
ここまで説明したように、状態通知メッセージを車両間で交換することで、周囲の車両に関する情報（図４Ｃの近傍車両管理テーブル）、自車両が保持するデータについてのデータ要求者（図４Ｄのデータ要求者管理テーブル）およびデータ提供者の情報（図４Ｅのデータ提供者管理テーブル）を常に把握できる。キャッシュ管理部２４は、これらの情報を用いて、キャッシュメモリ２５から破棄するデータを決定する（図５のＳ５１６）。
【００７２】
図１１にキャッシュ管理部２４が行うキャッシュ管理処理のフローチャートを示す。この処理は、データ取得部２６が新しいデータを外部から取得するたびに実行される。キャッシュ管理部２４は、新たなデータが取得されると、保持データがキャッシュメモリ２５のキャッシュサイズの上限を超えるか判断する（Ｓ１１０２）。新しいデータを格納してもキャッシュサイズを超えない場合（Ｓ１１０２−ＮＯ）は、そのデータをキャッシュメモリ２５に格納する（Ｓ１１０６）。
【００７３】
一方、保持データの合計がキャッシュサイズを超える場合（Ｓ１１０２−ＹＥＳ）は、いずれかのデータをキャッシュメモリ２５から削除する。キャッシュメモリを有効利用するには今後参照されないと予想されるデータを削除することが好ましい。本実施形態では、データ要求者数が多いデータほど、また、データ提供者数が少ないデータほど優先的にキャッシュメモリに保持するようにする。データ要求者数が多いデータほど、他の車両からデータの要求を受け付ける可能性が高いためである。また、データ提供者が多ければ自車両がキャッシュメモリから削除しても他の提供者が提供可能と考えられるためである。
【００７４】
本実施形態においては、キャッシュ管理部２４は、データ要求者数とデータ提供者数を考慮した削除優先度と、既存のＬＲＵ（Least Recently Used）アルゴリズムによる削除
優先度と組み合わせて、キャッシュメモリから削除するデータを決定する。すなわち、下記の式１で表される削除優先度指標の値が最も大きいデータを、キャッシュメモリから削除して（Ｓ１１０４）、新たなデータをキャッシュメモリに格納する（Ｓ１１０６）。
【数１】
ここで、ＬはＬＲＵにおける削除優先度（最終利用時刻から現在までの経過時間）、Ｎｒはデータ要求者数、Ｎｐはデータ提供者数を表す。αは０≦α≦１で与えられる重み付け係数である。
【００７５】
重み付け係数を変えることで、ＬＲＵの振る舞いと、データ要求者数やデータ提供者数に対する考慮の度合いを調整できる。α＝０とおくことで通常のＬＲＵの振る舞いとなり、α＝１とおくことでデータ要求者数やデータ提供者数のみを考慮する振る舞いとなる。
【００７６】
なお、キャッシュアルゴリズムは上記の式以外にも種々の方法が採用可能である。基本的には、他の条件が同じであるときに、データ要求者数が多いほど削除優先度が低くなり、データ提供者数が少ないほど削除優先度が低くなるようなアルゴリズムであれば、キャッシュメモリを有効活用できると考えられる。たとえば、以下の式２のようにデータ要求者数とデータ提供者数を独立に評価した削除優先度を採用することが考えられる。
【数２】
ここで、０≦α，β，γ≦１かつα＋β＋γ＝１である。
【００７７】
またここでは既存のキャッシュアルゴリズムとしてＬＲＵを例に説明したが、ＬＦＵ（Least Frequently Used）やＡＲＣ（Adaptive Replacement Cache）などの任意のキャッ
シュアルゴリズムを採用して良い。
【００７８】
＜動作例＞
図１２，１３を参照して、具体的な状況での動作例を説明する。図１２は、ここでの説明における状況を説明する図である。図１２において、Ｎｉは交差点ノードＩＤを表し、Ｃｉは車両ＩＤ、ＤｉはデータＩＤを表す。各車両Ｃｉは図に示す位置に存在し、点線がその走行予定経路である。データＤｉは図に示す位置に関連づけられているものとする。
【００７９】
図１３は、各車両の現在の状態（走行経路、保持データ、位置情報）を示している。すなわち、図１３に示した情報は、各車両から送信される状態通知メッセージに含まれる情報である。車両Ｃ１の走行予定経路は、図１２に示されるように、（Ｎ０，Ｎ２，Ｎ３，Ｎ４，Ｎ５）である。また、車両Ｃ１は、データＤ１，Ｄ２，Ｄ３，Ｄ４をキャッシュメモリ内に保持しているものとする。また車両Ｃ１の位置は緯度Ｘ１、経度Ｙ１とする。他の車両Ｃ２〜Ｃ５についても、図１３に示すような走行経路、保持データ、位置情報を持つものとする。
【００８０】
車両Ｃ１から送信される状態通知メッセージは、車両Ｃ１の走行経路Ｎ０，Ｎ２，Ｎ３，Ｎ４，Ｎ５に沿ってルーティングされる。例えば、車両Ｃ１が、車両Ｃ２およびＣ３を中継車両として送信しても良いし、車両Ｃ１はブロードキャスト送信し車両Ｃ２，Ｃ３が自律的に転送するようにしても良い。
【００８１】
車両Ｃ１から送信される状態通知メッセージを受信した各車両では以下の判断がなされる。車両Ｃ２，Ｃ３では、走行経路が同一方向であり十分な重なりがあると判断され（図８のステップＳ８０６−ＹＥＳ）、データ提供者管理テーブル更新処理が実行される。車両Ｃ４では、走行経路が逆方向であり十分な重なりがあると判断され（ステップＳ８１０−ＹＥＳ）、データ要求者管理テーブル更新処理が実行される。車両Ｃ５では、走行経路に十分な重なりがないと判断され（Ｓ８０６−ＮＯかつＳ８１０−ＮＯ）、管理テーブルの更新処理は行われない。
【００８２】
車両Ｃ２は、車両Ｃ１から状態通知メッセージを受信したときにデータ提供者管理テーブル更新処理（図９）を実行する。ここで、図１３に示すように、車両Ｃ２はデータＤ１，Ｄ２を保持しており、これらのデータについては車両Ｃ１も保持している。したがって、車両Ｃ２は、車両Ｃ１がデータＤ１およびＤ２のデータ提供者であると判断できる（Ｓ９０６−Ｓ９０８）。なお、車両Ｃ２は、車両Ｃ１に対して自車両がデータＤ１およびＤ２を提供可能である旨を通知する（Ｓ８１６）。したがって、車両Ｃ１も、車両Ｃ２がデータＤ１およびＤ２のデータ提供者であると判断できる。
【００８３】
車両Ｃ３も車両Ｃ２と同様の処理を行い、車両Ｃ１がデータＤ２およびＤ４のデータ提供者であると判断する。また、車両Ｃ１に対して、車両Ｃ３がデータＤ２およびＤ４のデータ提供者である旨の通知も行われる。
【００８４】
また、車両Ｃ１は、車両Ｃ４から状態通知メッセージを受信したときにデータ要求者管理テーブル更新処理（図１０）を実行する。車両Ｃ４の走行経路はＮ６，Ｎ４，Ｎ３，Ｎ２，Ｎ１である。車両Ｃ１は、この経路近傍の位置に関連づけられたデータのうち、データＤ１，Ｄ２，Ｄ３を保持している。このうち、車両Ｃ４はデータＤ３を保持し、データＤ１およびＤ２を保持していない。したがって、車両Ｃ１は、車両Ｄ４をデータＤ１およびＤ２のデータ要求者であると判断して、データ要求者管理テーブルを更新する（Ｓ１００６〜Ｓ１０１０）。
【００８５】
上記のような処理の結果として得られる、車両Ｃ１のデータ要求者管理テーブルとデータ提供者管理テーブルを図１４Ａ，Ｂに示す。図１４Ａに示すように、車両Ｃ１は、データＤ１およびＤ２の要求者が車両Ｃ４であり、データＤ３およびＤ４については要求者が存在しないと記憶する。また、図１４Ｂに示すように、車両Ｃ１は、データＤ１の提供者が車両Ｃ２、データＤ２の提供者が車両Ｃ２とＣ３、データＤ３の提供者は存在せず、データＤ４の提供者は車両Ｃ３であると記憶する。
【００８６】
車両Ｃ１は、このようなデータ要求者管理テーブルとデータ提供者管理テーブルに基づいてキャッシュ管理処理を行う。上述の式１に基づいて算出される削除優先度のうち、データ要求者数とデータ提供者数に基づく項目の値は図１４Ｃに示すようになる。データＤ１については、データ要求者数が１台で、データ提供者数が１台であることから、削除優先度は１と算出される。データＤ２については、データ要求者数が１台で、データ提供者数が２台であることから、削除優先度は１．５と算出される。データＤ３については、データ要求者数が０台で、データ提供者数が０台であることから、削除優先度は１と算出される。データＤ４については、データ要求者数が０台で、データ提供者数が１台であることから、削除優先度は２と算出される。したがって、車両Ｃ１はキャッシュメモリからデータを削除する必要が生じたときに、ＬＲＵによる削除優先度等が等しければ、削除優先度の最も高いデータＤ４を削除するように決定する。
【００８７】
各車両は、データが上位プログラムからデータを要求されたときに、データがキャッシュメモリ内にあればそこから取得して上位プログラムに渡す（Ｓ５０６）。キャッシュメモリに無い場合には、近傍車両管理テーブル（図４Ｃ）を参照して、周囲のこのデータを保持する車両が存在するか判断し、存在する場合にはその車両から取得する（Ｓ５１０）。サーバ装置からデータを取得するのは、自車両のキャッシュメモリにも周囲の車両のキャッシュメモリにも要求されたデータが存在しないときとなる（Ｓ５１４）。
【００８８】
＜実施形態の作用／効果＞
本実施形態によれば、サーバ装置から配信されるデータを車両内にキャッシュし、車両間でデータの送信を行うことで、サーバ装置との通信帯域を削減することができる。そして、車両におけるキャッシュ管理を要求者が多く提供者が少ないほど優先してキャッシュメモリに残るように行っているので、キャッシュヒット率が高まり、限られた容量のストレージを有効活用できる。
【符号の説明】
【００８９】
１００ 車両
２００ サーバ装置
２０ キャッシュ管理機能
２１ 状態記憶部
２２ 状態通知部
２３ 状態取得部
２４ キャッシュ管理部
２５ キャッシュメモリ
２６ データ取得部
２７ データ送信部
３０ ナビゲーションプログラム
【特許請求の範囲】
【請求項１】
複数の車両とサーバ装置から構成され、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおける、車両に搭載されたキャッシュ管理装置であって、
データを格納するキャッシュメモリと、
キャッシュメモリを管理するキャッシュ管理手段と、
自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する状態通知手段と、
周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する状態取得手段と、
自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得するデータ取得手段と、
他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信するデータ送信手段と、
を備え、
前記状態取得手段は、他車両から受信した状態通知に基づいて、
当該他車両と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータを当該他車両も保持している場合は、当該他車両を当該データのデータ提供者であると判断し、
当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータを当該他車両が保持していない場合は、当該他車両を当該データのデータ要求者であると判断し、
前記キャッシュ管理手段は、前記キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する
キャッシュ管理装置。
【請求項２】
前記状態通知手段は、状態通知メッセージをブロードキャスト送信し、
前記状態取得手段は、自車両がこの状態通知メッセージに含まれる走行予定経路上に位置し、かつ、当該走行予定経路上流の車両から状態通知メッセージを受信した場合に、この状態通知メッセージを転送する、
請求項１に記載のキャッシュ管理装置。
【請求項３】
前記状態通知手段は、自車両の走行予定経路上の車両を中継車両として指定して状態通知メッセージを送信する、
請求項１に記載のキャッシュ管理装置。
【請求項４】
状態通知メッセージを受信し、前記状態取得手段が、送信元車両が自車両の保持するいずれかのデータについてのデータ提供者であると判断したときに、自車両が当該データのデータ提供者であること示す重複データ保持通知を送信元の車両に送信し、
他車両から重複データ保持通知を受信したときに、当該他車両を当該データについてのデータ提供者であると判断する、
請求項１〜３のいずれかに記載のキャッシュ管理装置。
【請求項５】
前記状態取得手段は、他車両から受信した状態通知に基づいて、当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、
自車両が保持し、かつ当該他車両の走行予定経路近傍のデータであって、当該他車両が保持していないデータについて、当該他車両を当該データのデータ要求者であると判断す
る、
請求項１〜４のいずれかに記載のキャッシュ管理装置。
【請求項６】
前記キャッシュ管理手段は、データ要求者数およびデータ提供者数を利用せずに求めた指標と、データ要求者数およびデータ提供者数を利用して求めた指標の両方を用いて、削除するデータを決定する、
請求項１〜５のいずれかに記載のキャッシュ管理装置。
【請求項７】
複数の車両とサーバ装置から構成されサーバ装置から車両に対して位置に関連するデータを配信するデータ配信システム、における車両が実行するキャッシュ管理方法であって、
自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する状態通知ステップと、
周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する状態取得ステップと、
自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得するデータ取得ステップと、
他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信するデータ送信ステップと、
を含み、
前記状態取得ステップでは、他車両から受信した状態通知に基づいて、
当該他車両と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータを当該他車両も保持している場合は、当該他車両を当該データのデータ提供者であると判断し、
当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータを当該他車両が保持していない場合は、当該他車両を当該データのデータ要求者であると判断し、
前記キャッシュ管理ステップは、前記キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する
キャッシュ管理方法。
【請求項８】
複数の車両とサーバ装置から構成されサーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおける車両が実行するためのキャッシュ管理プログラムであって、
車両に、
自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する状態通知ステップと、
周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する状態取得ステップと、
自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得するデータ取得ステップと、
他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信するデータ送信ステップと、
を実行させるためのものであり、
前記状態取得ステップでは、他車両から受信した状態通知に基づいて、
当該他車両と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータを当該他車両も保持している場合は、当該他車両を当該データのデータ提供者であると判断し、
当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータを当該他車両が保持していない場合は、当該他車両を当該データのデータ要求者であると判断し、
前記キャッシュ管理ステップは、前記キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する
キャッシュ管理プログラム。
【請求項９】
複数の車両とサーバ装置から構成され、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムであって、
前記サーバ装置は、
データを格納する記憶装置と、
車両からのデータ取得要求に応じて、前記記憶装置に格納されたデータを配信するデータ配信手段と、
を備え、
前記複数の車両は、それぞれ、
データを格納するキャッシュメモリと、
キャッシュメモリを管理するキャッシュ管理手段と、
自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する状態通知手段と、
周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する状態取得手段と、
自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得するデータ取得手段と、
他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信するデータ送信手段と、
を備え、
前記状態取得手段は、他車両から受信した状態通知に基づいて、
当該他車両と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータを当該他車両も保持している場合は、当該他車両を当該データのデータ提供者であると判断し、
当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータを当該他車両が保持していない場合は、当該他車両を当該データのデータ要求者であると判断し、
前記キャッシュ管理手段は、前記キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する
データ配信システム。
【請求項１】
複数の車両とサーバ装置から構成され、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおける、車両に搭載されたキャッシュ管理装置であって、
データを格納するキャッシュメモリと、
キャッシュメモリを管理するキャッシュ管理手段と、
自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する状態通知手段と、
周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する状態取得手段と、
自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得するデータ取得手段と、
他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信するデータ送信手段と、
を備え、
前記状態取得手段は、他車両から受信した状態通知に基づいて、
当該他車両と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータを当該他車両も保持している場合は、当該他車両を当該データのデータ提供者であると判断し、
当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータを当該他車両が保持していない場合は、当該他車両を当該データのデータ要求者であると判断し、
前記キャッシュ管理手段は、前記キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する
キャッシュ管理装置。
【請求項２】
前記状態通知手段は、状態通知メッセージをブロードキャスト送信し、
前記状態取得手段は、自車両がこの状態通知メッセージに含まれる走行予定経路上に位置し、かつ、当該走行予定経路上流の車両から状態通知メッセージを受信した場合に、この状態通知メッセージを転送する、
請求項１に記載のキャッシュ管理装置。
【請求項３】
前記状態通知手段は、自車両の走行予定経路上の車両を中継車両として指定して状態通知メッセージを送信する、
請求項１に記載のキャッシュ管理装置。
【請求項４】
状態通知メッセージを受信し、前記状態取得手段が、送信元車両が自車両の保持するいずれかのデータについてのデータ提供者であると判断したときに、自車両が当該データのデータ提供者であること示す重複データ保持通知を送信元の車両に送信し、
他車両から重複データ保持通知を受信したときに、当該他車両を当該データについてのデータ提供者であると判断する、
請求項１〜３のいずれかに記載のキャッシュ管理装置。
【請求項５】
前記状態取得手段は、他車両から受信した状態通知に基づいて、当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、
自車両が保持し、かつ当該他車両の走行予定経路近傍のデータであって、当該他車両が保持していないデータについて、当該他車両を当該データのデータ要求者であると判断す
る、
請求項１〜４のいずれかに記載のキャッシュ管理装置。
【請求項６】
前記キャッシュ管理手段は、データ要求者数およびデータ提供者数を利用せずに求めた指標と、データ要求者数およびデータ提供者数を利用して求めた指標の両方を用いて、削除するデータを決定する、
請求項１〜５のいずれかに記載のキャッシュ管理装置。
【請求項７】
複数の車両とサーバ装置から構成されサーバ装置から車両に対して位置に関連するデータを配信するデータ配信システム、における車両が実行するキャッシュ管理方法であって、
自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する状態通知ステップと、
周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する状態取得ステップと、
自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得するデータ取得ステップと、
他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信するデータ送信ステップと、
を含み、
前記状態取得ステップでは、他車両から受信した状態通知に基づいて、
当該他車両と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータを当該他車両も保持している場合は、当該他車両を当該データのデータ提供者であると判断し、
当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータを当該他車両が保持していない場合は、当該他車両を当該データのデータ要求者であると判断し、
前記キャッシュ管理ステップは、前記キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する
キャッシュ管理方法。
【請求項８】
複数の車両とサーバ装置から構成されサーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムにおける車両が実行するためのキャッシュ管理プログラムであって、
車両に、
自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する状態通知ステップと、
周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する状態取得ステップと、
自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得するデータ取得ステップと、
他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信するデータ送信ステップと、
を実行させるためのものであり、
前記状態取得ステップでは、他車両から受信した状態通知に基づいて、
当該他車両と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータを当該他車両も保持している場合は、当該他車両を当該データのデータ提供者であると判断し、
当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータを当該他車両が保持していない場合は、当該他車両を当該データのデータ要求者であると判断し、
前記キャッシュ管理ステップは、前記キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する
キャッシュ管理プログラム。
【請求項９】
複数の車両とサーバ装置から構成され、サーバ装置から車両に対して位置に関連するデータを配信するデータ配信システムであって、
前記サーバ装置は、
データを格納する記憶装置と、
車両からのデータ取得要求に応じて、前記記憶装置に格納されたデータを配信するデータ配信手段と、
を備え、
前記複数の車両は、それぞれ、
データを格納するキャッシュメモリと、
キャッシュメモリを管理するキャッシュ管理手段と、
自車両の走行予定経路と自車両が保持しているデータのデータ識別子とを含む状態通知メッセージを、周囲の車両に送信する状態通知手段と、
周囲の車両から受信した状態通知メッセージに基づいて、周囲の車両の走行予定経路とこの車両が保持しているデータのデータ識別子を取得する状態取得手段と、
自車両内のプログラムからデータの要求を受け付けたときに、当該データがキャッシュメモリ内に格納されていればキャッシュメモリから取得し、キャッシュメモリ内に格納されていなければサーバ装置または他の車両から当該データを取得するデータ取得手段と、
他車両からデータの要求を受け付けたときに、当該データがキャッシュメモリに格納されていればキャッシュメモリから取得して、当該他車両に送信するデータ送信手段と、
を備え、
前記状態取得手段は、他車両から受信した状態通知に基づいて、
当該他車両と自車両の走行予定経路が重複し、かつ、同一方向に走行している場合に、自車両が保持するデータを当該他車両も保持している場合は、当該他車両を当該データのデータ提供者であると判断し、
当該他車両と自車両の走行予定経路が重複し、かつ、反対方向に走行している場合に、自車両が保持するデータを当該他車両が保持していない場合は、当該他車両を当該データのデータ要求者であると判断し、
前記キャッシュ管理手段は、前記キャッシュメモリからデータを削除する必要が生じたときに、データ要求者が少ないデータほど、また、データ提供者が多いデータほど優先して削除する
データ配信システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１２−４８４８９（Ｐ２０１２−４８４８９Ａ）
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願番号】特願２０１０−１８９８９７（Ｐ２０１０−１８９８９７）
【出願日】平成２２年８月２６日（２０１０．８．２６）
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【Ｆターム（参考）】
【公開日】平成２４年３月８日（２０１２．３．８）
【国際特許分類】
【出願日】平成２２年８月２６日（２０１０．８．２６）
【出願人】（５０２０８７４６０）株式会社トヨタＩＴ開発センター (232)
【出願人】（０００００３２０７）トヨタ自動車株式会社 (59,920)
【Ｆターム（参考）】
[ Back to top ]