(57)【要約】  本発明は、交通路(L1,L2,L3,C1,C2,C3)がそれらの間で複数の交差点(I1-I6)を形成する特定の地理的ネットワーク(10)の交通路上に配置されると共に交通路上を移動し得る移動ノード(1-14)を含むアドホックネットワークにおいて、ソースノード(S)とターゲットノード(C)との間でデータパケット(P)を経路指定する方法に関係する。該方法は、パケット(P)のキャリアノード(S)が、近隣交差点から、そして交通条件に従って、送信先交差点(I2)を選択する送信先交差点選択段階と、キャリアノードより選択された送信先交差点(I2)に近い、パケットのキャリアノードの１つ以上の近隣の移動ノード(1)を探索する段階と、もし１つ以上の近隣の移動ノード(1)が発見される場合、データパケットが選択された送信先交差点に向かって経路指定されるように、パケット(P)をパケットのキャリアノード(S)から発見された近隣の移動ノード(1)に転送する段階とを含む。
2009538076.tif 000002
【特許請求の範囲】
【請求項１】
交通路（Ｌ１、Ｌ２、Ｌ３、Ｃ１、Ｃ２、Ｃ３）がそれらの間で複数の交差点（Ｉ１−Ｉ６；Ｉｉ、Ｉ１０、Ｉ２０、Ｉ３０；Ｉｎ、Ｉｎ＋１）を形成する特定の地理的ネットワークの前記交通路上を移動する複数の移動ノード（１−１４；Ｒ０−Ｒ５）を含むアドホックネットワークにおけるソースノード（Ｓ）とターゲットノード（Ｃ）との間の１つ以上のデータパケット（Ｐ）の経路指定方法であって、
前記方法が、
・前記ターゲットノード（Ｃ）に対して経路指定されるべきデータパケット（Ｐ）のキャリアノード（１；Ｓ）が、交通条件の関数として、候補近隣交差点から送信先交差点（Ｉ２；Ｉ２０）を選択する段階（Ｅ３）と、
・前記キャリアノードより選択された前記送信先交差点（Ｉ２）に近い、前記データパケット（Ｐ）の前記キャリアノード（１）の１つ以上の近隣の移動ノード（２、３）を探索する段階（Ｅ７；Ｅ９）と、
・もし１つ以上の近隣の移動ノード（２）が発見される場合には、前記データパケットが選択された前記送信先交差点（Ｉ２）に向かって経路指定されるように、前記データパケット（Ｐ）を、前記データパケットの前記キャリアノード（１）から発見された前記近隣の移動ノード（２）に対して転送する段階（Ｅ１３）と
を有することを特徴とする方法。
【請求項２】
もし前記データパケットの前記キャリアノード（１）が現在の交差点と言われる選択された前記送信先交差点に位置している（Ｅ５）場合には、新しい送信先交差点を選択する段階（Ｅ３）が実行される
ことを特徴とする請求項１に記載の方法。
【請求項３】
選択する段階（Ｅ３）の間、データパケットのキャリア移動ノード（１；Ｓ）が、それぞれの候補交差点（Ｉ２；Ｉ２０）を現在の交差点（Ｉ１；Ｉｉ）に接続する交通路に関する１つ以上のリアルタイムの交通条件の関数として、前記候補交差点から送信先交差点（Ｉ２；Ｉ２０）を選択する
ことを特徴とする請求項２に記載の方法。
【請求項４】
前記キャリア移動ノード（１；Ｓ）が、前記候補交差点（Ｉ２；Ｉ２０）と前記ターゲットノード（Ｃ）との近接性の関数として、前記候補交差点から前記送信先交差点（Ｉ２；Ｉ２０）を選択する
ことを特徴とする請求項１から請求項３のいずれか一項に記載の方法。
【請求項５】
前記探索する段階（Ｅ７−Ｅ９）において、もし近隣の移動ノード（２）が発見されない場合には、前記キャリアノードが新しい近隣のノードを検出するまで、前記キャリアノードがパケットを保有する
ことを特徴とする請求項１から請求項４のいずれか一項に記載の方法。
【請求項６】
各ノードが、各ノードの近隣のノードの位置、速度、及び移動方向に関する最新の測定値を保持すると共に、
前記キャリアノードより選択された前記送信先交差点に近い、前記データパケットの前記キャリアノードの１つ以上の近隣の移動ノードを探索する段階が、現在の時刻においてこれらの測定値から近隣のノードの現在位置が計算される予測段階（Ｅ９）を有する
ことを特徴とする請求項１から請求項５のいずれか一項に記載の方法。
【請求項７】
前記キャリア移動ノード（１；Ｓ）が、前記候補交差点から、最大のスコア（Ｓｊ）を有する前記送信先交差点（Ｉ２；Ｉ２０）を選択すると共に、
前記スコアが、以下の式を用いて計算され、
【数１】
2009538076.tif 000009
ここで、
・“Ｔｉｊ”は、前記現在の交差点（Ｉｉ）と前記送信先交差点（Ｉｊ）との間を移動するノードの交通密度を表し、
・“Ｄｊ”は、前記送信先交差点（Ｉｊ）を前記ターゲットノード（Ｃ）と接続するルーティング経路の曲線に沿った距離を表し、
・“α”及び“β”は、補正率を表し、
・“ｆ”は、道路交通量の密度関数であり“０≦ｆ（Ｔｉｊ）≦１”であって、
・そして“ｇ（Ｄｊ）”は、以下の式を用いて計算され、“−１≦ｇ（Ｄｊ）≦１”であり、
【数２】
2009538076.tif 000010
ここで、“Ｄｉ”は、前記現在の交差点（Ｉｉ）と前記ターゲットノード（Ｃ）との間の距離である
ことを特徴とする請求項１から請求項６のいずれか一項に記載の方法。
【請求項８】
交通路（Ｌ１、Ｌ２、Ｌ３、Ｃ１、Ｃ２、Ｃ３）がそれらの間で複数の交差点（Ｉ１、Ｉ２、Ｉ３、Ｉ４、Ｉ５、Ｉ６；Ｉｉ、Ｉ１０、Ｉ２０、Ｉ３０；Ｉｎ、Ｉｎ＋１）を形成する特定の地理的ネットワーク（１０）の前記交通路上を移動する複数の移動ノード（１−１４）を含むアドホックネットワークの移動ノード（１；Ｓ）によって、データパケット（Ｐ）を、前記アドホックネットワークのターゲットノード（Ｃ）に対して経路指定するために使用されるように構成された通信端末であって、
前記通信端末が、
・交通条件の関数として、近隣交差点から送信先交差点（Ｉ２；Ｉ２０）を選択するための手段と、
・前記移動ノードより選択された前記送信先交差点に近い近隣の移動ノードを探索するための手段と、
・もし検索の結果が肯定的である場合には、前記データパケット（Ｐ）を、発見された前記近隣のノードに対して転送するための手段と
を備えることを特徴とする通信端末。
【請求項９】
無線通信システムであって、
アドホック構造において相互接続されると共に、交通路（Ｌ１、Ｌ２、Ｌ３、Ｃ１、Ｃ２、Ｃ３）がそれらの間で複数の交差点（Ｉ１、Ｉ２、Ｉ３、Ｉ４、Ｉ５、Ｉ６、Ｉｉ、Ｉ１０、Ｉ２０、Ｉ３０）を形成する特定の地理的ネットワーク（１０）の前記交通路上を移動する移動ノード（１−１４）を備え、
前記ノードが、請求項８に記載された通信端末を備えている
ことを特徴とする無線通信システム。
【請求項１０】
コンピュータプログラムであって、前記プログラムがコンピュータによって実行されるときに請求項１から請求項７のいずれか一項に記載の経路指定方法の各段階を実行するための命令を含む
ことを特徴とするコンピュータプログラム。
【請求項１１】
コンピュータ読み取り可能な記録媒体であって、請求項１から請求項７のいずれか一項に記載の経路指定方法の各段階を実行するための命令を含むコンピュータプログラムを格納する
ことを特徴とするコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の分野は、アドホック通信ネットワークの分野である。
【背景技術】
【０００２】
アドホック通信ネットワークは、無線媒体を使用する。それらは、無線通信がノードとその近隣のノードとの間でセットアップされた後で、ネットワークのあらゆるポイントからネットワークの他のポイントまでパケットの経路指定（ルーティング：routing）が可能であるネットワークを自動的及び動的に構成する特質を有する移動ノード及び／または固定ノードから構成される。
【０００３】
アドホックネットワークにおいて、パケットは、もし送信先ノード（destination node）が送信元ノード（source node）の接続可能領域内に存在する場合は直接的に、またはもし送信先ノードが送信元ノードの接続可能領域外に存在する場合は中間の近隣のノードを介して、送信元ノードと送信先ノードとの間で送信される。
【０００４】
従って、アドホックネットワークは、前から存在する社会基盤（infrastructure）及び集中的管理（centralized control）なしで、通信ネットワークの即座の配置を可能にする。ネットワークは、動的に形成されると共に、全ての管理タスクは、ネットワークの全てのノードに割り振られる。
【０００５】
アドホックネットワークの主な特徴は、ネットワークのノードが、ルータ（router）として機能するか、またはルータとして機能することができるということである。ノード自身は、従って、近隣のノードの間で経路情報の交換が可能であると共に、ネットワークのノードが他の全てのノードに対する通信路を計算することを可能にする特定の経路指定プロトコルを使用して、連続的なネットワークの接続性のセットアップと保持に関与する。これらの経路指定プロトコルは、アドホックネットワークの接続形態を更新するために、すなわちノード及びそれらの間のリンクを確認するために、定期的にメッセージを送信する。
【０００６】
具体的には、本発明は、それらの間で交差点が形成される特定の地理的ネットワークの交通路上を移動する移動ノードによって形成されたアドホックネットワークのソースノード（source node）とターゲットノード（target node）との間でデータパケットを送信する際の経路指定方法に関連していると共に、移動ノードは、ターゲットノードに対してデータパケットを経路指定するためのキャリアとして使用される。
【０００７】
本発明は、車車間アドホックネットワーク（vehicular ad hoc network：ＶＡＮＥＴ）及び都会の環境における、特別な、しかし制限的でない利用方法を発見する。
【０００８】
都市の車車間アドホックネットワークは、通信ノードが既知の構造の道路網の交通路を移動する車両である、分散型で柔軟な車両間通信（intervehicular communication：ＩＶＣ）無線通信システムである。
【０００９】
そのようなシステムにおいて、各車両は、それが無線周波数信号を送受信すると共に、従って、他の車両と連動して一時的な通信ネットワークを形成することを可能にする短距離用の無線伝送手段を備えている。
【００１０】
これらのネットワークにおいて、データパケットは、それによって道路網の交通路上を移動する１台以上の車両によりソース車両とターゲット車両との間でデータパケットが連続して送信される経路指定プロトコルを使用して、ソース車両からターゲット車両まで経路指定される。
【００１１】
一番多く存在している経路指定プロトコルは、データパケットの転送に関する決定を行うために、ネットワークのノードの明白な地理的位置に関する局所的な情報を有効に利用する地理的経路指定に基づいている。
【００１２】
ＧＳＲ（Geographic Source Routing）プロトコルとして知られている最初の経路指定プロトコルは、経路指定の基礎を、ネットワークの接続形態に関する情報と関連付けられるアドホックネットワークのノードの地理的位置に置く。
【００１３】
ＧＳＲプロトコルによれば、データパケットをターゲット車両に対して送信しようと試みるソース車両は、道路地図が提供する地理的な情報に基づいて、ターゲット車両に到達するための最短距離のルーティング経路（ルーティングパス：routing path）を計算する。例えば、問題のルーティング経路が、全体としてダイクストラアルゴリズム（Dijkstra algorithm）を使用して計算される点に注意が必要である。
【００１４】
計算されたルーティング経路に基づいて、ソース車両は、その場合に、データパケットがターゲット車両に到達するために伝送中に通過しなければならない交差点のシーケンスを選択する。交差点のこのセットは、データパケットが通過することになる固定した地理的ポイント（地点）のセットから構成される。
【００１５】
従って、固定した地理的ポイントの完全なシーケンスは、各パケットをターゲット車両に対して送信する前に計算されなければならないと共に、このシーケンスは、その場合に、ターゲット車両に対して送信されるべきパケットのヘッダに挿入される。
【００１６】
ＧＳＲプロトコルの欠点は、選択された交差点のシーケンスが、良好な接続を提供するためのその上に存在する車両が少なすぎると共に、パケット損失率を増加させるという有害な影響を有する道路を含み得るということである。
【００１７】
この種類のシーケンスの挿入は、もしそれがターゲット車両に対して送信される全てのパケットのヘッダに挿入されなければならないと仮定すると、アドホックネットワークに対する追加の負荷を表す。従って、それがアドホックネットワークに割り当てられた帯域幅を最適化し得ないという点で、この種類のアプローチは不利である。
【００１８】
更に、ターゲット車両に到達するように全体のルーティング経路を決定する段階が、計算資源に関するどん欲な操作であることに留意すべきである。このオペレーションはソースノードにおいてのみ実行されると共に、ＧＳＲプロトコルは、移動するターゲット車両の漸進的変化を追跡することを提供しない。
【００１９】
これは、ソース車両がパケットを送信してターゲット車両がそれを受信するまでの間に、比較的長い待ち時間を生じさせ得る。
【００２０】
ルーティング経路が確立されたとき、データパケットは、“グリーディーフォワーディング（Greedy Forwarding）”として知られている転送戦略（forwarding strategy）を使用して、ノードからノードまでその経路に沿って連続して転送される。
【００２１】
この転送戦略によれば、パケットのキャリアノードは、キャリアノードそのものよりターゲット車両の近くに存在する近隣のノードにそのパケットを転送しようと常に試みる。データパケットが得られるとすぐに、近隣のノードは、入れ替わりに、パケットを近隣のノードに対して転送しようと入れ替わりに試みるキャリアノードになり、以下同じことが繰り返される。
【発明の概要】
【発明が解決しようとする課題】
【００２２】
しかしながら、この転送戦略は、キャリアノードの近隣のノードがキャリアノードそのものよりターゲットノードの近くに存在しない特別な状況において失敗し得る。この状況は、“局所最適（局所解：local optimum）”の状況として知られていると共に、回復ソリューション（recovery solution）を必要とする。
【００２３】
“Ａ−ＳＴＡＲ（Anchor-based Street and Traffic Aware Routing）”プロトコルは、具体的には、都会の環境における車両間通信ネットワークのために設計されていると共に、それがルーティング経路を計算するときに、それが道路交通量データを考慮するという点で、ＧＳＲプロトコルとは異なる。しかしながら、この交通量データは、（例えば統計学に基づいて）静的であると共に、道路交通量が時間と共に絶えず進化している都市のネットワークに適当ではない。特に、車両間通信という状況における現存する経路指定プロトコルは、現時点では、道路交通密度（road traffic density）における空間的変化及び時間的変化、または多方向の交通路の存在を考慮しない。
【課題を解決するための手段】
【００２４】
本発明は、交通路がそれらの間で複数の交差点を形成する特定の地理的ネットワークの前記交通路上を移動する複数の移動ノードを含むアドホックネットワークにおけるソースノードとターゲットノードとの間の１つ以上のデータパケットの経路指定方法を提案することによって、上述の欠点を緩和する。
【００２５】
この方法は、・前記ターゲットノードに対して経路指定されるべきデータパケットのキャリアノードが、交通条件の関数として、候補近隣交差点から送信先交差点を選択する段階と、・前記キャリアノードより選択された前記送信先交差点に近い、前記データパケットの前記キャリアノードの１つ以上の近隣の移動ノードを探索する段階と、・もし１つ以上の近隣の移動ノードが発見される場合には、前記データパケットが選択された前記送信先交差点に向かって経路指定されるように、前記データパケットを、前記データパケットの前記キャリアノードから発見された前記近隣の移動ノードに対して転送する段階とを有する。
【００２６】
本発明の経路指定方法は、ターゲットノードに向けたノードからノードへの連続する転送によって、データパケットを徐々に経路指定すると共に、各ノードは、データパケットが伝送中に通過しなければならない中間の送信先交差点を選択する。
【００２７】
従って、その中で移動ノードが絶えず移動しているアドホックネットワークの接続形態に対する変化の実質的に瞬間的な追跡を可能にし、特定の地理的ネットワークを横断するデータパケットによって採用される交通路は、徐々に決定される。
【００２８】
徐々に交通路を決定することによって、本発明の方法は、現存する経路指定プロトコルよりも、パケットがはるかに長い距離を超えて送信されることを可能にする。ソースノードとターゲットノードとの間の距離が更に長くなるほど、それらの２つのノードの間の伝送時間も更に大きくなる。伝送時間が更に大きくなるほど、アドホックネットワークの接続形態に対する変化の確率も更に大きくなる。ルーティング経路の頻繁な計算がないと、ターゲットノードに対して送信されるべきパケットの損失のレートは、現存するプロトコルと同様に、急速に高い値に達する。
【００２９】
最新の広範囲の地理的位置情報を保持すると共に、全体のルーティング経路を計算する経路指定プロトコルと対照的に、局所的な経路情報に基づく漸進的な経路指定は、データを経路指定するために使用されるデータパケットのヘッダのサイズを減少させる。
【００３０】
これは、アドホックネットワークの資源を非常に効率的に活用すると共に、特にネットワークに割り当てられる帯域幅を最小限にする。
【００３１】
更に、本発明の経路指定方法は、データパケットが、低いデータパケット損失レートと結合された最小の終端間（end-to-end）の遅延でソースノードからターゲットノードに対して経路指定されることを可能にする。ターゲットノードが固定され得る（例えば、ガソリンスタンドにおける受付ポイント）か、または可動性であり得る（例えば、移動する車両）ということに、注意が必要である。
【００３２】
本発明の経路指定方法は、従って、ノードが高速で絶えず移動していると共に、ネットワーク接続形態の変更が頻繁であり、（特にマルチホップ経路における）移動ノードの間の接続の持続期間が短いアドホックネットワークに特に適当である。
【００３３】
更に、交通条件を考慮することによって、それは、選択された交通路上の不十分な交通量によって引き起こされるパケット経路指定の中断のリスクを制限する。
【００３４】
本発明の方法の１つの特徴によれば、もし前記データパケットの前記キャリアノードが現在の交差点と言われる選択された前記送信先交差点に位置している場合には、新しい送信先交差点を選択する段階が実行される。
【００３５】
これは、現在の送信先交差点の周辺に入って来たノードに対するこの段階の実行を制限することによって、ノードに関する計算負荷を最適化する。
【００３６】
本発明の方法の１つの特徴によれば、選択する段階の間、データパケットのキャリア移動ノードは、候補交差点を現在の交差点に接続する交通路に関する１つ以上のリアルタイムの交通条件の関数として、前記候補交差点から送信先交差点を選択する。
【００３７】
リアルタイムの移動ノードの交通条件を考慮することは、移動ノードが現在位置する交差点と候補送信先交差点との間の交通路が選択されることになると共に、接続性の問題を最小限にし、それによって、経路指定待ち時間とパケット損失が軽減されることを確かにする。
【００３８】
例えば、交通路上のノードの交通量が濃密になる程、交通路上の接続性のレベルがより高くなると共に、従って最短時間において送信先交差点に着く可能性があるこの経路で伝送されるパケットの数がより大きくなる。
【００３９】
本発明の方法の別の特徴によれば、前記キャリア移動ノードは、前記候補交差点と前記ターゲットノードとの近接性の関数として、前記候補交差点から前記送信先交差点を選択する。
【００４０】
キャリア移動ノードは、従って、地理的にターゲットノードの最も近くに存在すると共に、その方向における交通条件が最適である送信先交差点を選択する。
【００４１】
本発明の方法の別の特徴によれば、各ノードは、その近隣のノードの位置、速度、及び移動方向を含むグループに属するパラメータの内の少なくとも１つを最新の状態で保持する。
【００４２】
本発明の方法の別の特徴によれば、キャリアノードは、近隣のノードの速度及び／または選択された送信先交差点へ向かう速度の増加の関数として、近隣の移動ノードを選択する。
【００４３】
スピードベクトル（大きさ及び方向）と、その近隣のノードのそれぞれの位置を考慮することによって、キャリアノードは、推定計算を用いて送信先交差点の最も近くに存在する近隣のノードを決定する。例えば、キャリアノードによって選択された近隣のノードは、送信先交差点の最も近くに存在すると共に、最も速い速度で送信先交差点に向かって進んでいるノードである。
【００４４】
本発明の方法の別の特徴によれば、各ノードは、各ノードの近隣のノードの位置、速度、及び移動方向に関する最新の測定値を保持すると共に、前記キャリアノードより選択された前記送信先交差点に近い、前記データパケットの前記キャリアノードの１つ以上の近隣の移動ノードを探索する段階は、近隣のノードの現在位置が現在の時刻においてこれらの測定値から予測される予測段階を有する。
【００４５】
本発明の方法の別の特徴によれば、前記データパケットの前記キャリア移動ノードは、前記候補交差点から、最大のスコア（Ｓｊ）を有する前記送信先交差点を選択すると共に、前記スコアは、以下の式を用いて計算され、
【００４６】
【数１】
2009538076.tif 000003
【００４７】
ここで、・“Ｔｉｊ”は、前記現在の交差点と前記送信先交差点との間のノードの交通密度を表し、・“Ｄｊ”は、前記送信先交差点を前記ターゲットノードと接続するルーティング経路の曲線に沿った距離を表し、・“α”及び“β”は、補正率を表し、・“ｆ”は、道路交通量の密度関数であり“０≦ｆ（Ｔｉｊ）≦１”であって、・そして“ｇ（Ｄｊ）”は、以下の式を用いて計算され、“−１≦ｇ（Ｄｊ）≦１”である。
【００４８】
【数２】
2009538076.tif 000004
【００４９】
ここで、“Ｄｉ”は、前記現在の交差点と前記ターゲットノードとの間の距離である。
【００５０】
本発明は、更に、交通路がそれらの間で複数の交差点を形成する特定の地理的ネットワークの前記交通路上を移動する複数の移動ノードを含むアドホックネットワークの移動ノードによって、データパケットを、前記アドホックネットワークのターゲットノードに対して経路指定するために使用されるように構成された通信端末を対象とする。
【００５１】
本発明の端末は、・交通条件の関数として、近隣交差点から送信先交差点を選択するための手段と、・前記移動ノードより選択された前記送信先交差点に近い近隣の移動ノードを探索するための手段と、・もし検索の結果が肯定的である場合には、前記データパケットを、発見された前記近隣のノードに対して転送するための手段とを備える。
【００５２】
この端末の特別な実施例及び利点は、上で示された本発明の方法の実施例及び利点と同じである。
【００５３】
本発明の方法の別の特徴によれば、本発明の端末は、送信先交差点を、ターゲットノードに対するその近接性の関数として選択するための手段を備える。
【００５４】
本発明の方法の別の特徴によれば、本発明の端末は、その近隣のノードの最新の位置、速度、及び移動方向を保持するための手段を備える。
【００５５】
本発明の方法の別の特徴によれば、本発明の端末は、近隣のノードの速度及び／または選択された送信先交差点へ向かう速度の増加の関数として、近隣の移動ノードを選択するための手段を備える。
【００５６】
本発明は、更に、アドホック構造において相互接続されると共に、交通路がそれらの間で複数の交差点を形成する特定の地理的ネットワークの前記交通路上を移動する移動ノードを備え、前記ノードが上述の通信端末を備えている無線通信システムを対象とする。
【００５７】
そのようなシステムにおいて、ターゲットノードに対して経路指定されるべきデータパケットは、その上に適切な接続性を提供するのに十分な移動ノードが存在する交通路上の連続するノードからノードへのホップ（hop）によって、そのターゲットノードに向けて徐々に経路指定される。
【００５８】
もう一つの方法として、上述のデータパケット経路指定方法の様々な段階は、コンピュータプログラムの命令によって決定される。
【００５９】
従って、本発明は、そのプログラムがコンピュータによって実行されるときに上述の経路指定方法の各段階を実行するための命令を含むコンピュータプログラムを対象とする。
【００６０】
このプログラムは、あらゆるプログラミング言語を使用すると共に、ソースコード、オブジェクトコード、または部分的にコンパイルされた形式、またはあらゆる他の望ましい形式のようなソースコードとオブジェクトコードとの間の中間コードの形式をとることができる。
【００６１】
本発明は、上述のデータパケット経路指定方法の各段階を実行するための命令を含むコンピュータプログラムを格納するコンピュータ読み取り可能な記録媒体を対象とする。
【００６２】
情報媒体は、プログラムを格納することが可能であるあらゆる主体または装置であり得る。例えば、媒体は、ＲＯＭ、例えばＣＤ ＲＯＭまたは超小形電子回路ＲＯＭ、あるいは磁気記憶手段、例えばディスケット（フロッピー（登録商標）ディスク）またはハードディスク、のような格納手段を含み得る。
【００６３】
更に、情報媒体は、無線によって、または他の手段によって、電気ケーブルもしくは光学ケーブルを介して経路指定され得る電気信号もしくは光学信号のような伝達できる媒体であり得る。本発明のプログラムは、特にインターネットタイプのネットワークを介してダウンロードされ得る。
【００６４】
もう一つの方法として、情報媒体は、その中にプログラムが組み込まれる集積回路であり得ると共に、その回路は、本発明のデータパケット経路指定方式を実行するか、またはその実行において使用されるように構成される。
【図面の簡単な説明】
【００６５】
【図１】アドホックネットワークの車両が循環する道路網を示す図である。
【図２】本発明のデータパケット経路指定方法の一実施例の１つの反復を示すフローチャートである。
【図３】送信先交差点を選択する本発明の一実施例の段階を示すフローチャートである。
【図４】都市の車両間通信アドホックネットワークの特定の構成において送信先交差点を選択する１つの例を示す図である。
【図５Ａ】本発明の一実施例における２つの連続する交差点の間のデータパケット“Ｐ”の転送を示す図である。
【図５Ｂ】本発明の一実施例における２つの連続する交差点の間のデータパケット“Ｐ”の転送を示す図である。
【図６Ａ】本発明の一実施例における局所最適状況の存在下での回復戦略の使用の１つの例を示す図である。
【図６Ｂ】本発明の一実施例における局所最適状況の存在下での回復戦略の使用の１つの例を示す図である。
【発明を実施するための形態】
【００６６】
本発明の他の特徴及び利点は、添付された図面を参照した本発明の１つの非制限的実施例を示す以下の説明から明確になる。
【００６７】
本発明は、特にウェブブラウジング、インスタントメッセージング、ファイルシェアリング、リアルタイムゲームのような高い接続性サービスを提供することを意図している車両間通信アドホックネットワークとの関連で、以下で詳細に説明される。本発明のプロトコルは、等しく交通安全または協調走行（cooperative driving）のようなアプリケーションに適当である。
【００６８】
図１は、特定の道路網１０の交通路“Ｌ１、Ｌ２、Ｌ３、Ｃ１、Ｃ２”上を移動する複数の車両１〜１４、データパケット“Ｐ”を送信するソース車両“Ｓ”、及びデータパケット“Ｐ”が対象とするターゲット車両“Ｃ”を含むアドホックネットワークを示す図である。
【００６９】
図１において道路網１０の道路地図は、“水平の”交通路“Ｌ１、Ｌ２、Ｌ３”、及び“垂直の”交通路“Ｃ１、Ｃ２”を含むと共に、これらの交通路“Ｌ１、Ｌ２、Ｌ３、Ｃ１、Ｃ２”は、複数の交差点“Ｉ１、Ｉ２、Ｉ３、Ｉ４、Ｉ５”を定義する。この例においては、簡単化のために、直角に交差する交通路が示される。しかしながら、本発明は、相互にあらゆる角度で交差する特定の交通路を含む交通プラン形状（traffic plan configuration）に対して、区別なしで適用される。
【００７０】
アドホックネットワークの各車両は、アドホックネットワークの各車両が所在位置を発見されるように、地理的な位置決め装置、例えばＧＬＳ（Grid Location Service）と結合されたＧＰＳ（Global Positioning System）受信機を装備している。ＧＰＳ受信機は、ＧＬＳサービスが他の車両及び特にターゲット車両“Ｃ”の瞬間的な地理的な位置を提供する場合に、車両が、それ自身の地理的な位置を測定することを可能にする。
【００７１】
更に、各車両は、事前に定義された道路地図と結合された位置情報に基づいて、近くに存在する近隣交差点の位置を測定するように構成される。この目的のために、各車両は、事前に格納される（事前にロードされる）道路網１０に関するデジタル道路地図を含む標準のオンボードナビゲーション装置（onboard navigation device）を装備され得る。
【００７２】
各車両は、各々のこれらの近隣交差点の周辺の道路交通量に関する情報を有している。例えば、この情報は、各車両によって定期的に（例えば、毎秒ごとに）その近隣車両に対して送信されたビーコンメッセージによって提供され得る。もう一つの方法として、各交差点に設置された道路交通量センサ（図示せず）が、交差点の周辺におけるあらゆる車両に、道路交通状況に関する情報を提供するであろう。
【００７３】
図２は、本発明のデータパケット経路指定方法の一実施例の１つの反復を示すフローチャートである。
【００７４】
初めに、経路指定方法の最初の段階に関して２つの異なる状況がある。
【００７５】
第１の状況において、最初の段階Ｅ０の間に、ソース車両“Ｓ”は、データパケット“Ｐ”をターゲット車両“Ｃ”に対して送信しようと試みている。
【００７６】
第２の状況において、初期化段階Ｅ１の間に、データパケット“Ｐ”は、ソース車両“Ｓ”によって既に送信されたと共に、以下では“キャリア車両”と言われる車両によって受信された。
【００７７】
第１の状況において、選択段階Ｅ３の間に、ソース車両“Ｓ”は、データパケット“Ｐ”が経路指定されることになる送信先交差点を選択する。この選択段階Ｅ３は、図３を参照して、以下で詳細に説明される。
【００７８】
送信交差点が選択されるとすぐに、方法の次の段階と関連して説明されたように、データパケット“Ｐ”は、その送信先交差点に向かって送信される。ソースノードは、以下ではデータパケットのキャリアノードと言われる。
【００７９】
従って、データパケット“Ｐ”は、例えばそれらのヘッダの中に、選択された送信先交差点の地理的な位置が示されている。アドホックネットワークの各車両は、それらの近くに存在する近隣車両に関連する、近隣車両の位置、速度（大きさ）、及び移動方向のような情報を格納する最新の“近隣車両テーブル（neighbor table）”を保持する。例えば、これらの近隣車両テーブルは、定期的にビーコンメッセージをその近隣車両に対して送信する各車両によって更新され得る。従って、アドホックネットワーク１０の各車両は、ビーコンメッセージを通常の時間間隔Δｔ（例えば、Δｔ＝１ｓ）でその全ての近隣車両に対して送信する。
【００８０】
用語“近隣車両（neighbor）”は、データパケット“Ｐ”のキャリア車両の無線範囲の中に存在する車両のことを指す。用語“近くに存在する近隣車両（near neighbor）”は、（例えば所定の信号対雑音比しきい値パラメータに適合する）要求される伝送品質またはサービスの品質を保証するために、キャリア車両から十分に短い距離にある近隣車両（neighbor vehicle）のことを指す。
【００８１】
次の段階は、近くに存在する近隣車両を捜す段階Ｅ７である。
【００８２】
第２の状況において、すなわち、もし、初期化段階Ｅ１の間に、データパケット“Ｐ”が既にソース車両“Ｓ”によって送信され、そしてキャリア車両によって受信されていた場合、段階Ｅ５は、キャリア車両が送信先交差点に位置するか否かを確認する。“送信先交差点に位置する”という表現は、キャリア車両が、送信先交差点を包囲する所定の領域、例えば送信先交差点をその中心に有する所定の半径の円の中に位置するということを意味する。
【００８３】
もしこれがそうではないならば、すなわち、もしキャリア車両が送信先交差点に位置していないならば、次の段階は、検索段階Ｅ７である。
【００８４】
もしそれがそうであるならば、すなわち、もしキャリア車両が送信先交差点に位置するならば、キャリア車両は、選択段階Ｅ３の間に、データパケット“Ｐ”が経路指定されることになる送信先交差点を選択すると共に、データパケット“Ｐ”は、その送信先交差点に向かって転送される。その場合に、次の段階は、検索段階Ｅ７である。
【００８５】
検索段階Ｅ７は、転送されるべきパケット“Ｐ”のキャリア車両の近隣車両を捜す。上述の近隣車両テーブルは、この段階の間に更新され得る。
【００８６】
その場合に、予測段階Ｅ９の間、時刻“ｔ１”の後の現在時刻“ｔ２”の近隣車両の位置は、上述の近隣車両テーブルにおいて最も最近の時刻“ｔ１”に格納された情報（時刻“ｔ１”における速度、移動方向、及び最後の既知の位置）から予測される。これは、検索段階Ｅ７の間に検出される近隣車両の現在位置、すなわち現在時刻“ｔ２”における近隣車両の位置を予測する。
【００８７】
この目的のために、例えば、各々の車両は、以前に検出された速度に等しいと共に、時刻“ｔ１”において格納された一定の速度で移動していると仮定される。
【００８８】
その場合に、段階Ｅ７及び段階Ｅ９は、データパケット“Ｐ”のキャリアノード１の近隣に存在すると共に、キャリアノードより選択された送信先交差点に近い少なくとも１つの移動ノード２、３を探索する。
【００８９】
検査段階Ｅ１１は、先行する予測段階Ｅ９の間に予測された位置に基づいて、時刻“ｔ２”におけるその送信先交差点からの距離が、キャリア車両と該送信先交差点との間の距離より小さく、キャリア車両がその場合にそのパケット“Ｐ”を転送できる少なくとも１台の近隣車両が存在するか否かを判定する。
【００９０】
もし時刻“ｔ２”において、２台以上の車両がキャリア車両そのものより送信先交差点の近くに位置していると予測されるならば、その場合には、この距離がより短いか、もしくは最も短い車両が選択される。
【００９１】
もしそのような近隣車両が存在するならば、キャリア車両は、伝送段階Ｅ１３においてデータパケット“Ｐ”をそれに対して送信すると共に、それによって本発明の方法の１つの反復の終了を示す（段階Ｅ１５）。
【００９２】
そうでなければ、すなわち、もしキャリア車両より送信先交差点に近いであろう近隣車両が存在しないならば、その場合には、検査段階Ｅ１７は、パケット“Ｐ”のキャリア車両が十分に送信先交差点に近いか否かを判定する。
【００９３】
例えば、固定した遅延に対応する基準移動時間の上限が、この目的のために定義されると共に、送信先交差点に到着するためのキャリア車両の概算の移動時間と比較される。この上限は、必要とされるサービスの品質を前提として、容認可能な遅延を生成するように選択される。
【００９４】
もしキャリア車両が十分に送信先交差点の近くに存在すると予測される場合には、車両は、段階Ｅ１９において、パケット“Ｐ”を送信先交差点まで運ぶ。
【００９５】
パケット“Ｐ”のキャリア車両が選択された送信先交差点に到達するとすぐに、本発明の経路指定方法の反復は終了する。その場合に、次の段階は、段階Ｅ１５である。
【００９６】
そうでなければ、すなわち、もしデータパケット“Ｐ”のキャリア車両が十分に送信先交差点の近くに存在しないと予測されるならば、段階Ｅ２１において、・キャリア車両が送信先交差点に到達するまで、もしくは、・送信先交差点に近い別の車両がキャリア車両の伝送フィールド／領域に入るまで、キャリア車両はパケット“Ｐ”をその送信先交差点の方向に運ぶ。
【００９７】
その場合に、次の段階は、段階Ｅ１５である。
【００９８】
段階Ｅ１５において、新しい反復が段階Ｅ１から始まる。
【００９９】
図２を参照して説明される本発明の経路指定方法の実例となる実施例２は、図１を参照して、以下で説明示される。
【０１００】
交通路“Ｌ２”上を移動するソース車両“Ｓ”は、交通路“Ｃ２”上を移動するターゲット車両“Ｃ”に対して、パケット“Ｐ”を送信しようと試みている。この目的のために、ソース車両“Ｓ”は、ソース車両“Ｓ”に最も近い交差点である第１の交差点“Ｉ１”に位置する第１の車両１に対して、パケット“Ｐ”を送信すると仮定される。明らかに、第１の車両１はソース車両“Ｓ”の無線範囲の中にあると、同様に仮定される。
【０１０１】
第１の車両１は、初期化段階Ｅ１において、パケット“Ｐ”を受信する。第１の交差点と呼ばれる交差点“Ｉ１”に位置している（検査Ｅ５への肯定応答）第１の車両１は、選択段階Ｅ３において送信先交差点を選択する。
【０１０２】
この実施例において、第１の車両１は、ターゲット車両“Ｃ”のより近くに存在すると共に、第１の交差点“Ｉ１”と第２の交差点“Ｉ２”との間に車両の密集した交通路が存在するので、送信先交差点として、第２の交差点“Ｉ２”を選択する。
【０１０３】
第２の交差点“Ｉ２”を送信先交差点として選択した後で、第１の車両１は、パケット“Ｐ”に第２の交差点“Ｉ２”の位置を示す。そして、第１の車両１は、段階Ｅ１３において、データパケット“Ｐ”を第２の車両２に対して転送する。
【０１０４】
この目的のために、第１の車両１は、検索段階Ｅ７において、その最も近くに存在する近隣車両を検出する。この実施例において、第１の車両１は、第２の移動車両２及び第３の移動車両３の存在を検出すると共に、これらの車両は、両方とも、車両１によって送信された転送されるべきデータを伝送する電磁気信号（electromagnetic signal）を受信するのに、第１の車両に十分に近い。
【０１０５】
予測段階Ｅ９において、第１の車両１は、最新の状態に維持される第１の車両１の近隣車両テーブルに含まれる２つの車両２、３に関連する位置情報と速度情報から、後の時刻“ｔ２”における第２の車両２及び第３の車両３の位置を計算する。この例は、第３の車両３が第２の車両２より更にゆっくりと移動していると仮定した。
【０１０６】
検査段階Ｅ１１において、第１の車両１は、たとえ、第１の車両１の近隣車両テーブルに含まれる情報に従って、第２の車両２が第３の車両３よりも第２の交差点“Ｉ２”から更に遠いとしても、そのパケット“Ｐ”を第２の車両２に対して送信することを決定する。この選択は、第３の車両３が第２の車両２よりも更に遅い速度で第２の交差点に向かって進んでいるという事実、及びその結果として、それらの現在位置が予測された後では、第２の車両２が第３の車両３よりも第２の交差点の近くに存在することになる可能性が高いという事実によって動機づけられる。
【０１０７】
段階Ｅ１３においてパケット“Ｐ”を送信した後で、本発明の方法の第１の反復は終了する（段階Ｅ１５）。方法は、その場合に、データパケット“Ｐ”を転送する各車両に関して繰り返される。
【０１０８】
パケット“Ｐ”は、ここでは第２の車両２に適用される、上述の方法の新しい反復を開始する初期化段階Ｅ１において、第２の車両２によって受信される。この反復の終りに、第２の車両２は、パケット“Ｐ”を、第２の交差点“Ｉ２”において、第４の車両４に対して転送する。交差点に位置している第４の車両４は、選択段階Ｅ３において、新しい送信先交差点（第５の交差点“Ｉ５”）を選択すると共に、段階Ｅ１３において、交通路“Ｃ２”上をターゲット車両“Ｃ”の方に向かって移動している第５の車両５に、パケット“Ｐ”を転送する。
【０１０９】
この例において、第５の車両５は、第４の交差点“Ｉ４”と第５の交差点“Ｉ５”との間を、後者の第５の交差点“Ｉ５”に向かって進行する唯一の車両である。従って、第２の車両２は、第５の車両５より第５の交差点“Ｉ５”の近くに存在する最も近い近隣車両を検出しない。
【０１１０】
すなわち、状況は、“局所最適”の状況である。それ故に、本発明の回復戦略（recovery strategy）は、既に述べた段階Ｅ１７、Ｅ１９、または段階Ｅ１７、Ｅ２１を含む回復段階“Ｐ３”において適用される。従って、段階Ｅ２１において、第５の車両５は、パケット“Ｐ”を第５の交差点“Ｉ５”まで運ぶ。
【０１１１】
最終的に、第５の車両５が第５の交差点“Ｉ５”に到達する場合に、第５の車両５はターゲット車両“Ｃ”の無線範囲に存在すると共に、従って、これ以上の転送なしで、ターゲット車両“Ｃ”に対して直接的にパケット“Ｐ”を送信することができると仮定される。
【０１１２】
図３は、データパケット“Ｐ”のキャリア車両が送信先交差点を選択することを可能にするために実行される段階を示すフローチャートである。
【０１１３】
最初の段階Ｅ３０において、パケット“Ｐ”のキャリア車両は、以下で“現在の交差点”と言われる交差点“Ｉｉ”に到達する。
【０１１４】
次の段階Ｅ３２の間、その車両は、近隣の交差点の位置を測定する。この測定段階Ｅ３２は、例えば、問題の車両の瞬間的な位置、及びターゲット車両“Ｃ”の位置を考慮する標準のオンボードナビゲーション装置に事前に読み込まれるデジタル道路地図からの地理的な情報に基づいている。
【０１１５】
配置された近隣交差点“Ｉｊ”のそれぞれに関して、以下で説明されると共に、パケット“Ｐ”が経路指定されるべき送信先交差点を選択するために使用されるスコア“Ｓｊ”を計算する段階“Ｐ１”が実行される。
【０１１６】
従って、計算段階“Ｐ１”は、検出された近隣交差点の数と同じだけ何度も繰り返される。この例において、各候補送信先交差点“Ｉｊ”に関して計算されたスコア“Ｓｊ”は、特に２つのパラメータ、道路交通密度（road traffic density）及び幾何学的距離（geometrical distance）によって決定される。
【０１１７】
計算段階“Ｐ１”は、現在の交差点“Ｉｉ”を近隣送信先交差点“Ｉｊ”と接続する交通路上の現在の道路交通量に関する情報を獲得する第１の段階Ｅ３４を含む。この情報は、候補送信先交差点“Ｉｊ”のスコア“Ｓｊ”を計算する際に考慮されるべき、以下で“Ｔｉｊ”と表示される第１のパラメータを構成してる、この交通路上のリアルタイムの道路交通密度から構成される。
【０１１８】
第２の段階Ｅ３６において、ターゲット車両“Ｃ”と候補送信先交差点“Ｉｊ”との間の距離が測定される。以下で“Ｄｊ”と表されるこの距離は、送信先交差点“Ｉｊ”のスコア“Ｓｊ”を計算する際に考慮されるべき第２のパラメータを構成する。
【０１１９】
例えば、この距離“Ｄｊ”は、標準のオンボードナビゲーション装置に事前に読み込まれると共に、規則正しく更新されるターゲット車両“Ｃ”に関する位置通報と関連したデジタル道路地図が提供する地理的な情報から計算される。
【０１２０】
候補送信先交差点“Ｉｊ”のスコア“Ｓｊ”は、第３の段階Ｅ３８において計算される。
【０１２１】
このスコア“Ｓｊ”は、道路交通密度“（Ｔｉｊ）”と関連付けられた第１の要素“ｆ（Ｔｉｊ）”、及び距離“（Ｄｊ）”と関連付けられた第２の要素“ｇ（Ｄｊ）”を含み、これらの２つの要素は、それぞれ“交通量スコア”、及び“距離スコア”と言われる。
【０１２２】
候補送信先交差点“Ｉｊ”のスコア“Ｓｊ”は、以下の式（数式（１））から計算される。
【０１２３】
【数３】
2009538076.tif 000005
【０１２４】
ここで、“Ｔｉｊ”は、現在の交差点“Ｉｉ”を候補送信先交差点“Ｉｊ”と接続する交通路上の道路交通密度を表す。
【０１２５】
・“Ｄｊ”は、候補送信先交差点“Ｉｊ”をターゲット車両“Ｃ”と接続するルーティング経路の曲線に沿った距離を表す。
【０１２６】
・“α”及び“β”は、特定の重みを、スコア“Ｓｊ”の２つの要素の各々に割り当てるための補正率である。（例えば、もし距離“Ｄｊ”より道路交通密度“Ｔｉｊ”に対して更に大きい重要性が与えられるべきであるならば、“α”及び“β”の値は、“α＞β”となるように選択される。）
【０１２７】
交通量スコア“ｆ（Ｔｉｊ）”は、現在の交差点“Ｉｉ”と送信先交差点“Ｉｊ”との間を移動している車両の現在の数“Ｘ”を、データパケットの連続的な伝送を可能にする車両の基準最小数“Ｎ”と比較することによって獲得される。この基準数は、２台の連続する車両が、車両の無線範囲の半径の２倍に等しい距離だけ引き離されるように、現在の交差点“Ｉｉ”と送信先交差点“Ｉｊ”との間に規則正しく分散された同一の無線範囲を有する“Ｎ”台の車両に対応する。
【０１２８】
従って、基準数“Ｎ”は、以下の式のとおりに定義され得る。
【０１２９】
【数４】
2009538076.tif 000006
【０１３０】
ここで、“Ｄｉｊ”は、現在の交差点“Ｉｉ”と送信先交差点“Ｉｊ”との間の距離を表す。
【０１３１】
・“Ｒ”は、（全ての車両に関して同一であると仮定される）車両の無線範囲の半径を表す。
【０１３２】
・“Ｉｎｔ｛  ｝”は、その引数の整数部を決定する関数である。
【０１３３】
以下の表１において示されたように、それぞれが交通密度レベルに対応する交通量スコアの異なる値が定義される。この表によれば、もし車両の数“Ｘ”が“Ｎ”と“２．Ｎ”との間にあるならば、割り当てられた交通量スコアは、中程度高い交通密度に対応する“０．６”である。
【０１３４】
【表１】
2009538076.tif 000007
【０１３５】
距離スコアは、以下の式（数式（２））から決定される。
【０１３６】
【数５】
2009538076.tif 000008
【０１３７】
ここで、“−１≦ｇ（Ｄｊ）≦１”であり、“Ｄｉ”は現在の交差点“Ｉｉ”とターゲット車両“Ｃ”との間の距離である。
【０１３８】
従って、候補交差点“Ｉｊ”が現在の交差点“Ｉｉ”よりターゲット車両の近くに存在するならば（すなわち、もし“Ｄｊ＜Ｄｉ”であるならば）、正の距離スコアが獲得される。対照的に、もし候補交差点“Ｉｊ”がターゲット車両“Ｃ”から更に遠くに存在するならば（すなわち、もし“Ｄｊ＞Ｄｉ”であるならば）、その交差点を選択することの阻害要因となる負の距離スコアが獲得される。
【０１３９】
スコア“Ｓｊ”が各送信先交差点“Ｉｊ”に関して計算された後で、最大のスコア“Ｓｊ”を有する送信先交差点“Ｉｊ”が選択段階Ｅ４０において選択される。
【０１４０】
選択された送信先交差点は、地理的にターゲット車両“Ｃ”の最も近くに存在すると共に、最も高い道路交通量レベル（または、密度）を有する交差点である。
【０１４１】
都市の車両間通信アドホックネットワークの特定の構成において送信先交差点を選択することの非制限的な１つの例が、図３及び図４を参照して、以下で説明される。
【０１４２】
図４は、交通路“Ｌ１”、“Ｌ２”、“Ｌ３”、“Ｃ１”、“Ｃ２”を含む図１の道路網と類似した道路網１０を表す図であると共に、交通路“Ｌ１”、“Ｌ２”、“Ｌ３”、“Ｃ１”、“Ｃ２”は、それらの間で交差点“Ｉｉ”、“Ｉ１０”、“Ｉ２０”、“Ｉ３０”を定義する。これらの交通路上で表される主体は、アドホックネットワークを形成すると共に、ソース車両“Ｓ”とターゲット車両“Ｃ”との間でデータパケット“Ｐ”を転送する車両である。
【０１４３】
交差点“Ｉｉ”に到達するソース車両“Ｓ”は、データパケット“Ｐ”をターゲット車両“Ｃ”に対して送信しようと試みていると考えられる。明らかに同等の方法で、転送されるべきデータパケット“Ｐ”のキャリア車両を考えることができるであろう。
【０１４４】
この目的のために、ソース車両“Ｓ”は、送信先交差点を選択することによって、パケット“Ｐ”に関して経路指定の方向を選択しなければならない。
【０１４５】
既に説明された測定段階Ｅ３２において、ソース車両“Ｓ”は、その時にデータパケット“Ｐ”を経路指定するための候補送信先交差点である３つの送信先交差点、第１の交差点“Ｉ１０”、第２の交差点“Ｉ２０”、及び第３の交差点“Ｉ３０”（図４を参照）を検出する。
【０１４６】
パケット“Ｐ”がどの送信先交差点に対して経路指定されるべきであるかを決定するために、ソース車両“Ｓ”は、上述の計算段階Ｐ１において、これらの３つの交差点のスコア“Ｓｊ”を計算する。
【０１４７】
第１の候補送信先交差点“Ｉ１０”、第２の候補送信先交差点“Ｉ２０”、及び第３の候補送信先交差点“Ｉ３０”のそれぞれのスコアは、“Ｓ１”、“Ｓ２”、“Ｓ３”である。
【０１４８】
図４において示されるように、この例における交通状況は、以下のようなものである。具体的には、現在の交差点“Ｉｉ”を第２の送信先交差点“Ｉ２０”と接続する交通路“Ｌ２”の一部分上の道路交通量“Ｔｉ２”（図４における斜線部分）は、現在の交差点“Ｉｉ”を第３の送信先交差点“Ｉ３０”と接続する交通路“Ｃ１”の一部分上の道路交通量“Ｔｉ３”より、密度が高く、道路交通量“Ｔｉ３”それ自体は、現在の交差点“Ｉｉ”を第１の送信先交差点“Ｉ１０”と接続する交通路“Ｃ１”の一部分上の道路交通量“Ｔｉ１”より、密度が高い。すなわち、（図４には示されていないが）“Ｔｉ２＞Ｔｉ３＞Ｔｉ１”である。
【０１４９】
図４において示されるように、第２の送信先交差点“Ｉ２０”は、ターゲット車両“Ｃ”の最も近くの送信先交差点である。第２の送信先交差点“Ｉ２０”とターゲット車両“Ｃ”との間の曲線に沿った距離Ｄ２は、第３の送信先交差点“Ｉ３０”とターゲット車両“Ｃ”との間の曲線に沿った距離Ｄ３より小さく、距離Ｄ３それ自体は、第１の送信先交差点“Ｉ１０”とターゲット車両“Ｃ”との間の曲線に沿った距離Ｄ１より小さい。すなわち、“Ｄ２＜Ｄ３＜Ｄ１”である。
【０１５０】
それがターゲット車両“Ｃ”の最も近くに存在すると共に、最も高い交通密度を有すると仮定すると、第２の送信先交差点“Ｉ２０”が、従って、最も高いスコアＳ２を獲得する（Ｓ２＞Ｓ３＞Ｓ１）。
【０１５１】
データパケット“Ｐ”がその交差点に向かって移動する多数の車両によって経路指定されることは、従って、この交差点“Ｉ２０”に対して経路指定されることである。
【０１５２】
２つの連続する交差点の間に配置された車両を介して、本発明の１つの特別な実施例に従ってデータパケット“Ｐ”を転送することの例は、図５Ａ及び図５Ｂを参照して、以下で説明される。
【０１５３】
図５Ａは、所定時刻“Ｎ１”における、連続する２つの交差点“Ｉｎ”と“Ｉｎ＋１”との間の交通路“Ｖ”を表す。
【０１５４】
図５Ｂは、“Ｎ２＞Ｎ１”であって、時刻“Ｎ１”より後の時刻“Ｎ２”における図５Ａと同じ交通路“Ｖ”を示す。この新しい構成は、この交通路上を移動する車両の現在の位置を、各移動ノードによって格納されると共に最新の状態に維持されるそれらの位置情報及び速度情報から予測する図２の予測段階Ｅ９によって獲得される。
【０１５５】
この例において、交通路“Ｖ”上を送信先交差点“Ｉｎ＋１”に向かって移動するデータパケット“Ｐ”のキャリア車両“Ｒ０”は、そのパケットを送信先交差点“Ｉｎ＋１”に向かって送信しようと試みていると考えられる。本発明によると、キャリア車両“Ｒ０”は、この目的のために、交通路“Ｖ”上を送信先交差点“Ｉｎ＋１”に向かって移動する車両を使用する。
【０１５６】
図５Ａ及び図５Ｂに示されるように、４台の車両（Ｒ１、Ｒ２、Ｒ３、Ｒ４）が、キャリア車両“Ｒ０”の無線範囲“Ｋ”の中に存在する。
【０１５７】
キャリア車両“Ｒ０”は、従って、データパケット“Ｐ”を送信先交差点“Ｉｎ＋１”に向かって経路指定するために、これらの車両の１台以上と交信することができる。
【０１５８】
図５Ａでは、例えば、時刻“Ｎ１”において、・第１の車両“Ｒ１”及び第２の車両“Ｒ２”は、交通路“Ｖ”を、キャリア車両“Ｒ０”と同じ方向に、すなわち送信先交差点“Ｉｎ＋１”の方向に移動している、・第１の車両“Ｒ１”は、第２の車両“Ｒ２”より速く移動している、そして・第３の車両“Ｒ３”及び第４の車両“Ｒ４”は、交通路“Ｖ”上を、キャリア車両“Ｒ０”とは反対の方向に移動している、と仮定される。
【０１５９】
本発明の経路指定プロトコルによれば、図５Ｂに示されるように、キャリア車両“Ｒ０”は、時刻“Ｎ２”において、第１の車両“Ｒ１”が送信先交差点“Ｉｎ＋１”に最も近い位置に到達すると予測するので、キャリア車両“Ｒ０”は、データパケット“Ｐ”を、第１の車両“Ｒ１”に対して転送する。
【０１６０】
しかしながら、特に近隣車両の速度及び移動方向を考慮するこの予測段階がない場合、時刻“Ｎ１”において送信先交差点“Ｉｎ＋１”に最も近い車両が第４の車両“Ｒ４”であると仮定すると、キャリア車両“Ｒ０”は、そのパケット“Ｐ”を、第４の車両“Ｒ４”に対して転送することを選択したであろう、ということに注意が必要である。
【０１６１】
本発明の予測段階は、第４の車両“Ｒ４”及び第３の車両“Ｒ３”がキャリア車両“Ｒ０”と反対の方向に移動しているという事実を有利に考慮する。これのために、キャリア車両“Ｒ０”は、これらの２台の車両を、パケット“Ｐ”を送信するための対象から除外する。
【０１６２】
本発明の１つの特別な実施例において回復戦略を実行することの例は、図６Ａ及び図６Ｂを参照して、以下で説明される。
【０１６３】
図６Ａの例は、時刻“Ｎ１”において、パケット“Ｐ”を転送しようと試みるキャリア車両“Ｒ０”が、キャリア車両“Ｒ０”と送信先交差点“Ｉｎ＋１”との間を移動する車両を発見できない状況を例証する。
【０１６４】
この状況において、本発明の方法に適合する回復ソリューションは、キャリア車両“Ｒ０”が送信先交差点“Ｉｎ＋１”の最も近くに存在する車両である“極小”状況でパケット“Ｐ”が立ち往生することを防止するために使用される。
【０１６５】
このソリューションは、キャリア車両“Ｒ０”がパケット“Ｐ”を送信先交差点“Ｉｎ＋１”まで運ぶことを必要とする。この戦略は、キャリア車両“Ｒ０”が送信先交差点“Ｉｎ＋１”からそれほど離れていないという条件（図２の段階Ｅ１９）で、想定され得る。
【０１６６】
図６Ｂの例は、適切な車両が無線範囲に入るまで、キャリア車両“Ｒ０”がパケット“Ｐ”を運ぶと共に、従ってパケット“Ｐ”は適切な車両に対して転送され得るという、上述の回復ソリューションの変形の使用を示す。
【０１６７】
この変形は、特に、もしキャリア車両“Ｒ０”が送信先交差点“Ｉｎ＋１”の十分な近くに存在しない場合（図２の段階Ｅ２１）において使用される。
【符号の説明】
【０１６８】
１〜９、１１〜１４    車両
１０    道路網
Ｐ    データパケット
Ｓ    ソース車両
Ｃ    ターゲット車両
Ｌ１、Ｌ２、Ｌ３、Ｃ１、Ｃ２    交通路
Ｉ１、Ｉ２、Ｉ３、Ｉ４、Ｉ５    交差点
Ｉｉ、Ｉ１０、Ｉ２０、Ｉ３０、Ｉｎ、Ｉｎ＋１    交差点
Ｓ１、Ｓ２、Ｓ３”    スコア
Ｔｉ１    交通路“Ｃ１”の一部分上の道路交通量
Ｔｉ２    交通路“Ｌ２”の一部分上の道路交通量
Ｔｉ３    交通路“Ｃ１”の一部分上の道路交通量
Ｄ１    第１の送信先交差点とターゲット車両との間の曲線に沿った距離
Ｄ２    第２の送信先交差点とターゲット車両との間の曲線に沿った距離
Ｄ３    第３の送信先交差点とターゲット車両との間の曲線に沿った距離
Ｖ    交通路
Ｒ０    キャリア車両
Ｒ１、Ｒ２、Ｒ３、Ｒ４    車両
Ｋ    キャリア車両“Ｒ０”の無線範囲
【図１】
2009538076.tif 000011
【図２】
2009538076.tif 000012
【図３】
2009538076.tif 000013
【図４】
2009538076.tif 000014
【図５Ａ】
2009538076.tif 000015
【図５Ｂ】
2009538076.tif 000016
【図６Ａ】
2009538076.tif 000017
【図６Ｂ】
2009538076.tif 000018
【国際調査報告】
2009538076.tif 000019
2009538076.tif 000020
2009538076.tif 000021
2009538076.tif 000022
2009538076.tif 000023
2009538076.tif 000024