説明

移動ノードのネットワークにおいてデータパケットを放送する方法、及び関連する端末

本発明は、それらの間で交差点を形成している交通路に沿って移動すると共に自らを配置し得る複数の移動ノードによって形成されたアドホックネットワークにおけるデータパケットの定期的放送に関連する。データパケットの放送は、各交差点のレベルにおける候補ノードのセットから選定された放送局ノードによって保証される。放送局ノードの選定は、2つの連続する放送の間の所定の基準時間期間に対する、交差点の中心に到達するための推定の移動時間の比較に応じて、各候補ノードのレベルにおける分散的な方法で行われる。

【発明の詳細な説明】
【技術分野】
【0001】
本発明の分野は、アドホック通信ネットワークの分野である。
【0002】
本発明は、更に正確には、各ノードが位置し得る特定の地理的ネットワークの車線上を移動する複数の通信移動ノードによって動的に形成されたアドホックネットワークにおいて情報を放送することに関連する。
【背景技術】
【0003】
本発明は、車々間アドホックネットワーク(vehicular ad hoc network:VANET)における、好ましいが、しかし制限しないアプリケーションを見いだすと共に、その中で、各通信ノードは、特に都会の環境における道路網の車線に沿って移動する車両から構成される。
【0004】
このタイプのネットワークにおいて情報を放送することは、運転者の安全及び快適性を向上させるために、高度道路交通システム(intelligent transportation system)のための道路交通に関する情報を放送することのような、多くのアプリケーションを有している。
【0005】
“VANET '04: Proceedings of the 1st ACM International Workshop on Vehicular Ad Hoc Networks, Philadelphia, PA, USA: ACM Press, Sept. 2004, pp. 76-85”において発表された“Urban multihop broadcast protocol for inter-vehicle communications systems”と題名が付けられた論文において、“G. Korkmaz”、“E. Ekici”、“F. ozguner”、及び“U. ozguner”は、都会の環境に適している車々間通信システムに関するデータパケットを放送するためのマルチホッププロトコルについて述べている。
【0006】
そのプロトコルは、各交差点におけるローカル放送と2つの連続する交差点の間の指向性のある放送の、2つのタイプのパケット放送の組み合わせを使用する。
【0007】
それは、ローカル放送の間に交差点に位置するノードにデータパケットを転送するために、各交差点に配置された固定の中継器の使用を提供する。中継器により送信されたパケットを運ぶノードが交差点を離れて車線に入るとき、それは、指向性のある放送に参加する。指向性のある放送の間に、パケットを運ぶノードは、その最も遠い近隣のノードにパケットを送信すると共に、その近隣のノードは、送信ノードになり、そして、ネットワークの接続形態に関する情報を使用することなく、同様にその最も遠い近隣のノードに、更にパケットを送信する。
【発明の概要】
【発明が解決しようとする課題】
【0008】
このタイプのアプローチの欠点は、それが各交差点における固定の中継器の導入を必要とすることである。これは、特に、もしアドホック車々間ネットワークによってカバーされた道路網が非常に大きいならば、困難であると共に、高価であり得る。
【課題を解決するための手段】
【0009】
本発明は、地理空間を移動するように構成された複数の移動ノードによって形成されたネットワークにおいて少なくとも1つのデータパケットを放送する方法を提案することによって、上述の欠点が緩和されることを可能にする。
【0010】
前記方法は、その間に、セルと呼ばれる前記地理空間の所定領域において前記セルに存在する前記移動ノードに対して少なくとも1つのデータパケットが放送される、ローカル放送を行うステップを含む。
【0011】
本発明によれば、前記方法は、更に、・前記少なくとも1つのデータパケットを受信するステップと、・その間に、前記移動ノードが、それが前記セルにおいて前記データパケットを放送する候補であるかどうかを判定する、選択ステップと、・前記セルの中心までの前記候補ノードの推定の移動時間に応じて、前記候補ノードを前記セルにおける前記データパケットの放送局ノードとして選定するステップとを含む。
【0012】
前記ローカル放送を行うステップは、前記放送局ノードが前記セルの中心付近に位置しているときに実行される。
【0013】
第一に、以前に選定されたと共に、セルの中心の近くに位置している放送局ノードによって放送するステップは、データパケットを放送するための設備(中継器)の導入及び保守を回避する、標準のインフラストラクチャのエミュレーションを可能にする。セルの中心の周辺に位置するその全ての近隣のノードにデータパケットを放送する選定されたノードは、一時的に、そのセルの中心に導入された中継器の役割を引き受ける。
【0014】
従って、セルは、放送局ノードによって活性化され得る放送領域と見なされ得ると共に、この領域は、候補ノードがそのセルのための放送局ノードとして選定されるとき、及びその領域の中に位置する、パケットを受信するノードが存在するときに活性状態になる。
【0015】
推定の移動時間に応じて放送局ノードを選定することは、一定時間ごとにセルが活性化されることを可能にし、そしてその結果としてデータパケットの定期的放送を可能にする。
【0016】
従って、本発明は、事前に定義された地理的領域のセットのレベルにおいて、アドホックネットワークにおけるデータパケットの放送のための解決法を提供すると共に、その解決法は、比較的低いコストで実現することが容易であり、配置の観点から柔軟性がある。本発明は、ネットワークのノードの間での位置情報の交換を必要とせずに、データパケットの分散的(非集中的)な放送を可能にする。
【0017】
更に、セルレベルで放送局ノードを選定することは、1つのノードが、地理的領域でデータパケットを放送することに関与すると共に、従って多重伝送によるアドホックネットワークの帯域幅の不必要な過負荷を回避するように指定されることを可能にする。
【0018】
本発明の別の特徴によれば、前記選択ステップの間に、前記移動ノードは、それが前記セルの中心に向かって移動していると共に、それが前記セルに含まれた前記中心を中心とするアンカー領域に位置していることを条件として、それが前記データパケットを放送する候補であると判定する。
【0019】
各候補ノードは、自発的に、それに特有である待ち時間を判定することによって、分散型、分散的方法において達成される選定作業に参加し、従って、あらゆるインフラストラクチャの導入を回避する。これは、広範囲にわたる地理的ネットワークを横断して新しい放送領域を展開するために特に有利である。
【0020】
本発明の別の特徴によれば、前記選定するステップの間に、・前記候補ノードが、待ち時間を計算すると共に、前記計算された待ち時間の値は、前記セルの中心までの前記候補ノードの推定の移動時間が所定の基準時間期間に近づくにつれて減少し、・前記待ち時間の終わりにおいて、前記候補ノードは、もしそれが別のノードから放送局ノードに選定されたことを伝える通知メッセージを受信していなかったならば、それが放送局ノードに選定されたことを伝える通知メッセージを放送する。
【0021】
従って、セルのレベルで選定された放送局ノードは、基準時間期間にできる限り近い時間期間にセルの中心に到達する可能性がある候補ノードに対応する。
【0022】
所定の基準時間期間は、ローカル放送ステップの必要とされた期間に有利に対応する。
【0023】
データパケットは、従って、基準時間期間に近い時間期間の終りに放送され、従って、各セルのレベルでデータパケットの定期的なローカル放送を保証する。
【0024】
本発明の別の特徴によれば、前記セルは、移動ノードの伝送距離に等しい半径によって定義されると共に、アンカー領域は、移動ノードの伝送距離の半分に等しい半径によって定義される。
【0025】
放送局ノードとしてちょうど選定されると共に、アンカー領域の周囲に存在する候補ノードは、そのアンカー領域に位置する全てのノード、そして特にアンカー領域の周囲に位置すると共に、選ばれたノードと直径に沿って反対側に位置するノードと有利に通信し得る。従って、候補ノードは、それがセルの中心から離れている距離が、移動ノードの伝送距離の半分より下回るか、または良くても等しいと共に、アンカー領域がその伝送距離に等しい直径を有することを条件として、放送局ノードとして選ばれ得る。
【0026】
本発明の別の特徴によれば、前記選定するステップの間に、候補ノードは、以下の、・前記セルの中心に到達するために必要な移動時間を推定するステップ、・前記セルのレベルで放送局ノードに選定される確率を計算するステップ、前記選定される確率に応じて、前記待ち時間を計算するステップ、というサブステップを達成し、前記確率の計算は、前記セルの中心に到達するための推定の移動時間が基準時間期間に近づくにつれて、選定される確率が増加するように構成され、前記待ち時間の計算は、前記選定される確率が増加するにつれて前記待ち時間が減少するように構成される。
【0027】
セルの中心に到達するための推定の移動時間が放送期間にできる限り近いノードを選定することは、選ばれたノードがパケットを放送するとき、それがセルの中心の周辺に存在することを保証する。
【0028】
本発明の別の特徴によれば、推定の移動時間に応じて選定される確率は、基準時間期間に等しい期待値を有するガウス関数から判定される。
【0029】
この関数は、セルの中心に到達するための推定の移動時間が基準時間期間に対応する候補ノードに関して、最大の確率が獲得されることを可能にすると共に、確率は、推定の移動時間と基準時間期間との間の差の絶対値が増加するにつれて減少する。
【0030】
本発明の別の特徴によれば、以下の式から、待ち時間WTは、選定される確率に応じて判定される。
【0031】
【数1】

【0032】
ここで、WTMaxは、移動ノードに割り当てられ得る最大の待ち時間を示し、P/Pmaxは、選定される正規化確率(normalized probability)を示し、そして、γは、無作為に生成された数である。
【0033】
従って、正規化確率が“1”に近づくにつれて待ち時間は減少する。無作為に生成された数γは、ちょうど同じ確率値を計算した候補ノードに対して、特にもし推定の待ち時間が、正確に等しいか、もしくは“Δt=T±x”という形式であった場合に、異なる待ち時間が割り当てられることを有利に可能にし、ここで、xは、基準時間期間Tと比較した時間オフセット値を指定する実数である。
【0034】
本発明の別の特徴によれば、前記地理空間は、複数の車線から成り、それらの間に複数の交差点を形成している交通網であると共に、前記セルは、交差点と関連付けられている。
【0035】
本発明の方法は、特に、そこでデータパケットが放送されなければならない多数の交差点を含む密集した広い道路網に適している。各交差点における放送領域を形成するためにアンカーポイントを各交差点の中心に配置することは、特に有利である。市街地において、車両(移動ノード)の集中状態は、大部分の車両が交差しなければならない交差点において、一般的に最も濃密である。
【0036】
上述の放送方法が各ノードにおいて分散的方法で実施されることによって、本発明は、更に、複数の通信移動ノードを含むネットワークの移動ノードを提供する。
【0037】
各移動ノードは、・少なくとも1つのデータパケットを受信するように構成された受信機手段と、・前記少なくとも1つのデータパケットを関連するノードの範囲領域の中に位置している移動ノードに対して放送するように構成された放送局手段とを具備する。
【0038】
本発明によれば、前記移動ノードは、更に、・前記移動ノードが前記ネットワークと関連するセルと呼ばれる地理空間の所定領域において前記データパケットを放送する候補であるかどうかを判定するように構成された選択手段と、・前記セルの中心までの前記候補ノードの推定の移動時間に応じて、前記候補ノードを前記セルにおける前記少なくとも1つのデータパケットの放送用の放送局ノードとして選定するように構成された選定手段と、・前記放送局ノードが前記セルの中心付近に位置しているときに前記放送局手段を起動するように構成された起動手段とを具備する。
【0039】
本発明の別の特徴によれば、前記選択手段は、もし前記移動ノードが前記セルの中心に向かって移動していると共に、それが前記セルに含まれた前記中心を中心とするアンカー領域に位置しているならば、前記移動ノードが前記データパケットを放送する候補であると判定するように構成される。
【0040】
本発明の別の特徴によれば、端末は、更に、・セルの中心に到達するために必要な移動時間を推定するための推定手段と、・セルのレベルで放送局ノードに選定される確率を計算するための第1の計算手段と、・待ち時間を選定される確率に応じて計算するための第2の計算手段とを具備し、前記第1の計算手段は、前記セルの中心に到達するための推定の移動時間が基準時間期間に近づくにつれて増加する確率を計算するように構成され、前記第2の計算手段は、選定される確率が増加するにつれて減少する待ち時間を計算するように構成される。
【0041】
従って、第2の計算手段は、前記セルの中心に到達するための候補ノードの推定の移動時間が所定の基準時間期間に近づくにつれて減少する待ち時間が計算されることを可能にする。
【0042】
本発明の別の特徴によれば、第1の計算手段は、選定される確率を、基準時間期間に等しい期待値を有するガウス関数によって判定された推定の移動時間に応じて判定するように構成される。
【0043】
本発明の別の特徴によれば、第2の計算手段は、以下の式から、選定される確率に応じて待ち時間を判定するように構成される。
【0044】
【数2】

【0045】
ここで、WTMaxは、移動ノードに割り当てられ得る最大の待ち時間を示し、P/Pmaxは、選定される正規化確率(normalized probability)を示し、そして、γは、無作為に生成された数である。
【0046】
本発明は、更に、特定の交通網の車線上を移動する複数の移動ノードを含む無線通信システムを提供すると共に、前記システムは、各ノードが上で定義されたような本発明に基づく移動ノードであることを特徴とする。
【0047】
もう一つの方法として、上述のデータパケットを放送する方法のステップは、コンピュータプログラム命令によって決定される。
【0048】
従って、本発明は、更に、端末のプロセッサ手段(プロセッサ)上で実行されるコンピュータプログラムを提供すると共に、前記プログラムは、そのプログラムがコンピュータによって実行されるときに、前述のデータパケットを放送する方法のステップを実行するための命令を含む。
【0049】
このプログラムは、あらゆるプログラミング言語を使用し得ると共に、ソースコード、オブジェクトコード、または、部分的に編集された形式もしくは他の望ましい形式のような、ソースコードとオブジェクトコードの中間のコードの形式を取り得る。
【0050】
本発明は、更に、プログラムが、コンピュータ上で、更に詳しくは無線通信端末の処理手段(プロセッサ)上で実行されるときに、上述のデータパケットを放送する方法のステップを実行するための命令を含むコンピュータプログラムを記憶しているコンピュータ読み取り可能な記憶媒体を提供する。
【0051】
情報媒体は、プログラムを記憶することが可能である、あらゆる実体(entity)または装置であり得る。例えば、その媒体は、ROM、例えばCD−ROMまたはマイクロ電子回路ROMのような記憶手段、例えばフロッピー(登録商標)ディスクまたはハードディスクのような磁気記憶手段を含み得る。
【0052】
更に、情報媒体は、無線もしくは他の手段により電気ケーブルもしくは光学ケーブルを介して送られ得る、電気信号もしくは光学信号のような伝送可能な媒体であり得る。本発明のプログラムは、特に、インターネットタイプのネットワークを介してダウンロードされ得る。
【0053】
もう一つの方法として、情報媒体は、プログラムを組み込んだ集積回路であり得ると共に、前記回路は、本発明のデータパケット伝送方法を実行するように、またはその実行において使用されるように構成される。
【図面の簡単な説明】
【0054】
【図1】図式的に、本発明が実施されているアドホックネットワークのノードがそれを横断して移動する都市の道路網を示す図である。
【図2】道路網の交差点におけるデータパケットのローカル放送のために使用される本発明の方法のステップをフローチャート形式において示す図である。
【図3】図式的に、放送局ノードの選定のために候補ノードのセットが交差点で選択される本発明に適合するシナリオの例を示す図である。
【図4】選択された候補ノードから交差点における放送局ノードを選定するために使用される本発明の方法のステップをフローチャート形式において示す図である。
【図5A】グラフ形式で、本発明の方法において候補ノードを選定する確率の第1の例を示す図である。
【図5B】グラフ形式で、本発明の方法において候補ノードを選定する確率の第2の例を示す図である。
【図5C】グラフ形式で、交差点の周囲領域における待っている列(queue)内の移動ノードの数を、ノードの到着時間の関数として示す図である。
【図6】図式的に、交差点において放送局ノードが選定されるシナリオの例を示す図である。
【図7】図式的に、データパケットが交差点において選定された放送局ノードによって放送されると共に、隣接する交差点に対するデータパケットの指向性のある伝播のステップが開始されるシナリオの例を示す図である。
【図8】図式的に、指向性のある伝播のステップの間の2つの連続する交差点の間のデータパケットの放送を示す図である。
【発明を実施するための形態】
【0055】
本発明の他の特徴及び利点は、添付された図面を参照して以下で与えられた、本発明の1つの制限しない実施例を示す説明から明らかになる。
【0056】
本発明は、市街地の道路網から成る地理空間を移動する複数の移動ノードによって形成された車々間アドホックネットワーク(vehicular ad hoc network:VANET)との関連で、以下で詳細に説明される。
【0057】
図1は、図式的に、複数の車線L、L12、L13、L、L、L34、L24、L、L、Lを含み、それらの間に複数の交差点J、J、J、Jを形成している道路網を表す。この実例において、車線は、直線で示される。しかしながら、本発明は、それらの中にあらゆる角度を有する曲がった車線を含むあらゆる道路網構成に適用される。
【0058】
車々間アドホックネットワークのメンバーである各移動ノードは、車線L、L12、L13、L、L、L34、L24、L、L、Lに沿って移動すると共に、道路網の交差点J、J、J、Jを横断することができる車両から成る。
【0059】
各ノードは、いつでも道路網の中に位置していることができる。この目的のために、各車両は、従来の衛星航法デバイスを装備していると共に、少なくとも、・いつでもそれ自身の地理座標を獲得するための受信機、例えばGPS(全地球測位システム)またはガリレオタイプの受信機と、・移動ノードの瞬間的な位置を道路地図上で表示するための、道路網を表すと共にGPS受信機と連結されるデジタル道路地図とを具備する。
【0060】
異なる実施例において、この位置情報をネットワークの専用の装置を用いて移動ノードに送ることを構想することが可能である。
【0061】
各ノードは、各ノードがIEEE802.11プロトコルを使用してその近隣のノードと通信することができるように、無線通信端末、例えばWiFi(登録商標)トランシーバを装備している。特に、通信端末は、データパケットを放送することができる。通信チャンネルへのアクセスは、IEEE802.11プロトコルの自立分散制御機能(distributed coordination function:DCF)に従って、従来と同じように管理される。
【0062】
移動ノードに搭載されている無線通信端末は、もちろん他のワイヤレス技術、例えば赤外線の技術を使用することができる。
【0063】
以下では、基準ノードに言及しているとき、“隣接のノード”という表現は、基準ノードの伝送距離内に位置するあらゆるノードのことを指す。例えば、移動ノードの伝送距離は、DSRC(Dedicated Short Range Communications:狭域通信システム)標準の指針に従って250メートル(m)に設定された半径によって定義される。
【0064】
図1において示されたように、固定された地理座標を有する仮想アンカーポイントC、C、C、Cが、各交差点J、J、J、Jの中心にそれぞれ定義される。各仮想アンカーポイントC、C、C、Cは、移動ノードによって、そのナビゲーション装置を用いて識別され得る。特に、仮想アンカーポイントに近づくと、各ノードは、それ自身の瞬間的な地理座標と仮想アンカーポイントの地理座標から、それがその仮想アンカーポイントから離れている距離を判定することができる。
【0065】
移動ノードの伝送距離に等しい半径(R=250[m])を有する適用範囲(coverage)セルZ、Z、Z、Zが、適用範囲セルの中心が仮想アンカーポイントC、C、C、Cと一致するように、各交差点J、J、J、Jにおいて定義される。従って、以下では、“仮想アンカーポイント”という表現は、適用範囲セルの中心のことを指す。各適用範囲セルZ、Z、Z、Zは、データパケットが放送局ノードによって定期的な放送時刻に放送されるローカル放送領域を定義する。
【0066】
2つの連続する放送時刻の間の基準時間期間Tは、事前に各仮想アンカーポイントにおいて決定される。この例において、各データパケットが同じ期間によって各交差点において放送されるように、基準時間期間Tは、全ての仮想アンカーポイントに関して同じであると仮定されている。
【0067】
交差点JにおけるデータパケットDのローカル放送のために実行される本発明の方法のステップは、図2及び図3を参照して以下で説明される。
【0068】
受信ステップE1の間に、放送されるべきデータパケットDは、交差点Jの適用範囲セルZに位置する全てのノードによって受信される。
【0069】
この例において、データパケットDは、最初に、車線の側に導入された固定の放送局(図示せず)によってアドホックネットワークに挿入されると仮定されている。この放送局は、その領域に入るノードがデータパケットDを交差点の方に運ぶように、例えば市街地への入り口点(entry point)に位置している。
【0070】
選択ステップE3の間に、放送局ノードとして選定されるのに適した候補ノード2、3、5、7のセットが、交差点Jにおいて選択されると共に、ここで、放送局ノードの機能は、適用範囲セルZにおいてデータパケットDを放送することである。
【0071】
受信ステップE1の間にデータパケットDを受信した後で、選択ステップE3の間に、データパケットDを運ぶ各ノードは、それが仮想アンカーポイントCの方へ進んでおり、そして適用範囲セルZに含まれるアンカー領域A内に位置していることを条件として、候補ノードのステータス(status)を割り当てられる。
【0072】
明らかに、図3において示されたように、アンカー領域Aは、仮想アンカーポイントCを中心としていると共に、適用範囲セルZの半径Rの半分に等しい半径R/2、すなわち移動ノードの伝送距離の半分(R/2=125メートル)によって定義された領域である。
【0073】
従って、データパケットDを受信すると、データパケットDを運ぶ各ノードは、それがアンカー領域Aに位置しているかどうかを判定する。この目的のために、それが仮想アンカーポイントCから離れている距離が、R/2(ノードの伝送距離の半分)より小さいかどうかを確認するために、そのナビゲーション装置を使用する。もし確認結果が肯定であるならば、そのノードは、それが仮想アンカーポイントCの方へ進んでいるかどうかを判定するために、そのナビゲーション装置を使用する。もしそうであるならば、そのノードは、候補ノードのステータスを割り当てられる。これは、図3において示されたように、アンカー領域Aに位置するノード2、3、5、7に適用される。ノード1、4、6は、それらがアンカー領域Aに位置しているとしても、それらが仮想アンカーポイントCから離れているので、候補ノードとして切り捨てられる。
【0074】
各ノードは、有利に、自発的にそれが放送局ノードとしての選定の候補であるかどうかを判定するように構成される。従って、候補ノードは、ノードの間での、またはあらゆる中央集権化されたインフラストラクチャ要素の間での情報交換を必要とせずに、各ノードにおいて完全に分散された方法で選択される。
【0075】
選定ステップE5の間に、放送局ノード7は、事前に選択ステップE3の間に判定された全ての候補ノード2、3、5、7から選定される。この選定は、仮想アンカーポイントCに到達するための推定の移動時間と、仮想アンカーポイントにおける2つの連続する放送時刻の間の特定の基準時間期間Tとを比較することによって達成される。
【0076】
その時々に有利に、適用範囲セルZにおいてデータパケットDを放送するための放送局ノード7を選ぶことは、複数のノードが同じ適用範囲セルZにおいて同時に同じデータパケットDを放送することを回避して、アドホックネットワークの帯域幅の使用を最適化することを可能にする。伝達ステップE7の間に、以前に選定された放送局ノードが、データパケットDを仮想アンカーポイントCの周辺に運ぶ。
【0077】
ローカル放送ステップE9の間に、選定された放送局ノードは、それが交差点Jの中心の周辺に存在するとき、現時点の交差点の適用範囲セル内の全てのノードがデータパケットDを受信するように、データパケットDを全ての近隣のノードに放送する。
【0078】
放送局ノード7を選定するステップE5は、図4及び図5を参照して、以下で詳細に説明される。この選定ステップE5は、図4を参照することによって説明されると共に、選択ステップE3の間に事前に選択された各候補ノード2、3、5、7によって独立して実行されるサブステップのセットを含む。
【0079】
選定ステップE5は、適用範囲セルZ内に候補ノード2、3、5、7のセットが構成されるときに始まる(サブステップE50が始まる)。
【0080】
第1の計算サブステップE51の間に、各候補ノードは、以下のように、仮想アンカーポイントCに到達するために必要な移動時間Δtを推定する。
【0081】
Δt=Δt+Δt
【0082】
ここで、Δtは、交差点の周囲におけるノードの待ち時間を示すと共に、Δtは、そのノードが交差点の周囲領域を横切った時刻から交差点の中心に到達するために必要な時間を示し、この時間はノードの速度とそれが交差点の中心に到達するために移動しなければならない距離に応じて計算される。
【0083】
交差点の周囲領域における交通信号に起因する待ち時間Δtは、以下の数式(数式0)から、ノードの到着時間tに応じて計算される。
【0084】
【数3】

【0085】
ここで、tは、交通信号が赤に見えるステージの持続時間(秒)であり、tは、交通信号が緑に見えるステージの持続時間(秒)であり、Cは、周期の持続時間(秒)であり、Q(t)は、時刻tにおける待っている列(queue)の長さ(車両の数)であり、Qは、待っている列(queue)の初期の長さ(車両の数)であり、qは、交通信号へ到着する平均レート(車両/s)であり、sは、交通信号から出発するレート(車両/s)であり、tは、交通信号におけるノードの到着時間(秒)であり、tは、待っている列が空になってからの時間(秒)であり、そして、Δt(t)は、時刻tにおける待ち時間(秒)である。
【0086】
時刻tにおける待っている列Q(t)の長さは、図5Cにおけるグラフ形式で表された関数から判定された複数の車両を意味する。示されたように、持続時間Cの周期は、以下の、・その間に、交通信号が赤に見えると共に、待っている列における車両の数が増加する持続時間tの第1のステージ、・その間に、交通信号が緑に見えると共に、待っている列における車両の数が減少する持続時間tの第2のステージ、という2つのステージから成る。
【0087】
交通信号が赤から緑に変わる(ステージの変更)ときに待っている列がいっぱい(Qmax)であり、そして時刻tにおいて待っている列が空であるということが仮定されている。
【0088】
もし交通信号が赤に変わる前に待っている列が空になるならば、その待っている列は、完全に空である。この状況において、時間tは、図5Cにおいて示されるように、第2のステージを定義する時間期間tの中に含まれると共に、次の周期の始まりにおいてQ=0である。もしそうでなければ、Q≠0である。
【0089】
時間tは、以下の数式から計算される。
【0090】
【数4】

【0091】
時間Δtを計算するために、各候補ノードは、そのナビゲーション装置を使用し、それ自身の地理座標と仮想アンカーポイントの地理座標を用いて、それが仮想アンカーポイントCから離れている距離を計算する。各候補ノードは、そのナビゲーション装置を使用して、次に、その速度vとそれが仮想アンカーポイントCから離れている距離とに応じて、仮想アンカーポイントCに到達するための推定の移動時間Δtを計算する。もちろん、移動時間Δtは、ノードの速度が増加するか、及び/またはそれが仮想アンカーポイントCから離れている距離が減少するにつれて、減少する。
【0092】
従って、図6の状況における候補ノード2、3、5、7は、自発的に、それらのそれぞれの移動時間Δt、Δt、Δt、Δtを、それらのそれぞれの速度v、v、v、vとそれぞれの仮想アンカーポイントCからの距離とに応じて判定する。
【0093】
xが実数を示す場合に、Δt=T±xであり得ると共に、従って、例えばΔt=T+xでありΔt=T−xであり得るような、ノード2及びノード7が基準時間期間Tに対して“対称的である”移動時間を推定する特別な状況が検討される。
【0094】
更に、ノード5の速度がゼロ(v=0)であると共に、従ってその推定の移動時間Δtが、他のノードの推定の移動時間よりも大きくなり得る、すなわちΔt<Δt<Δtであるように、ノード5の速度vを獲得する時刻において、ノード5が交通信号Fにおいて止められるということが仮定されている。
【0095】
最終的に、移動ノード3が、仮想アンカーポイントCに最も近い候補ノードであると共に、ゼロでない速度(v>0)でポイントCに向かって移動しているとすると、その推定の移動時間Δtは、他のノードの移動時間と比べると短く、Δt<Δt<Δt<Δtになる。
【0096】
第2の計算サブステップE52の間に、各候補ノードは、そのナビゲーションシステムを使用して、放送局ノードに選定される確率を計算する。各確率は、第1の計算サブステップE51の間に計算された推定の移動時間Δtに応じて、そして基準時間期間Tに応じて判定される。
【0097】
この目的のために、各候補ノード2、3、5、7は、例えば、図5Aにおけるグラフ形式において表されると共に、以下の数式(数式1)によって定義された標準のガウス関数を適用することによって、その推定の移動時間Δt(それぞれΔt、Δt、Δt、Δtと表示される)に応じて、選定される確率P(それぞれP、P、P、Pと表示される)を計算する。
【0098】
【数5】

【0099】
ここで、Δtは、仮想アンカーポイントCに到達するためのi番目の候補ノードの推定の移動時間であり、σは、関数P(Δt)を表すガウス曲線の真ん中の高さ(mid-height)の時間的な幅に対応する時定数であり、そして、Tは、関数P(Δt)の平均値に対応すると共に、アンカーポイントCにおける2つの連続する放送時刻の間の基準時間期間を示す。
【0100】
時定数σの値は、基準時間期間Tと放送局ノードを選定するために必要とされる正確度とに応じて定義される。この時定数の値が低くなるほど、この選択が更に厳しく選択される。σ=0である極限状況において、ガウス曲線は、δ(T)=1であると共に、あらゆるt≠Tに関してδ(T)=0であり得るようなディラックパルス(Dirac pulse)δになる。この状況において、各放送局ノードは、セルの中心に到達するための推定の移動時間がちょうど基準時間期間Tと一致する候補ノードである。実際上、Tに正確に等しい推定の移動時間を有する候補ノードが各放送周期において発見されるということは、ありそうもない。従って、σの値は、ゼロでなく、そして推定の移動時間がTに十分に近い候補ノードが各放送周期において選択されることを可能にするように調整される。基準時間期間Tの値は、平均速度で交差点を横切るための平均移動時間と一致する最大の基準値Tmaxを越え得ない。概して言えば、Tの値は、関係のあるアプリケーションのタイプに応じて選択される。特に、交通安全に関する情報を放送するために、基準時間期間Tは、情報放送の短命な性質を考慮して、十分に短くされる。
【0101】
この例において、選定される確率P(Δt)は、ガウス関数を用いて計算される。明らかに、当業者は、Δt=Tにおいてその最大値に到達すると共に、差分|T−Δt|が増加するにつれて減少する確率値を生成するあらゆる他の関数を使うであろう。
【0102】
従って、異なる実施例において、確率Pは、図5Bにおけるグラフ形式で表されると共に、以下の数式(数式3)によって定義された“三角”関数に従って判定される。
【0103】
【数6】

【0104】
ここで、τは、図5Bにおいて表されたような三角関数の幅を定義するために使用される正の実数定数であり、PMaxは、全ての確率の和が1に等しくなり得るように、PMax=P(T)=1/τのように、最大確率に対応すると共に、Tは、基準時間期間を示す。
【0105】
図5A及び図5Bに示された状況において、仮想アンカーポイントCに到達するための推定の移動時間Δtが基準時間期間Tに近づくにつれて、選定される確率P(Δt)は増加する。すなわち、確率Pは、差分|T−Δt|が増加するにつれて、減少する。これは、適用範囲セルの中心に到達するための推定の移動時間が相応して更にTに近い放送局ノードを選ぶことを可能にする。
【0106】
もし候補ノード2及び候補ノード7が、それぞれ推定の移動時間Δt=T+x及びΔt=T−xを有するならば、図5Aに示されるように、これらの候補ノード2及び候補ノード7は、同じ選定される確率P≡P(Δt)=P≡P(Δt)を正確に判定する。従って、図6に示される候補ノード2、3、5、7として選定される確率は、図5Aに示されるように、P≡P(Δt)<P(Δt)<P=Pのようになる。
【0107】
第3の計算サブステップE53の間に、各候補ノードは、そのナビゲーション装置を使用して、第2の計算サブステップE52の後に獲得された選定される確率に応じて、待ち時間WTを計算する。待ち時間WTは、以下の数式(数式3)から判定される。
【0108】
【数7】

【0109】
ここで、WTMaxは、候補ノードに割り当てられ得る最大の待ち時間を示す実数定数であり、WTMax=WT(P=0)であると共に、P/Pmaxは、i番目の候補ノードの選定される正規化確率(normalized probability)を示し、そして、γは、無作為に生成された実数である。
【0110】
数式3から判定された時間WTは、選定される確率Pが増加するにつれて減少する。
【0111】
数γを使用することには、正確に同じ選定される確率を有する複数のノードが異なる待ち時間WTを計算することを可能にするという利点がある。これはちょうど、計算された同じ確率値P=Pを有するノード2及びノード7の状況であると共に、無作為の数γは、それらを区別する。例えば、ノード2に関して生成された無作為の数γは、ノード7に関して生成された無作為の数γより大きく(γ<γ)、ノード7及びノード2は、WT<WTのような、異なる待ち時間WT及び待ち時間WTを有している。
【0112】
選定される確率P(Δt)が最も小さい(P(Δt)<P(Δt)<P(Δt)=P(Δt))候補ノード3は、数式3から、WT>WT>WT>WTのような大きい待ち時間WTを計算する。
【0113】
待ち時間WTが決定されるとすぐに、各候補ノード2、3、5、7は、その値WTによって初期化されたカウンタを起動すると共に、放送局ノードの選定をノードが通知されない限り、カウントダウンステップE54の間に、その値からカウンタをカウントダウンする。
【0114】
この目的のために、検査ステップE55の間に、カウンタが起動された各候補ノードは、その待ち時間WTが経過していないことを確認する。もしその待ち時間が経過していないならば、確認ステップE56の間に、ノードは、それが、放送局ノードが選定されたことを示す通知メッセージ、すなわち、より短い待ち時間を有する候補ノードが既に放送局ノードに選定されたことを意味する(ステップE58)であろう通知メッセージを受信したか否かを確認する。どのノードもデータパケットDを放送していないと共に、あるノードの待ち時間WTが経過していない限り、そのノードは、ステップE54、E55、E56を繰り返す。もしそのノードが通知メッセージを受信したならば、そのノードのカウンタは動作を停止されると共に、選定ステップE5は終了する(サブステップE58)。
【0115】
あるノードの待ち時間WTが経過するとすぐに、そしてもしその時点においてデータパケットDが他のノードによって放送されていなかったならば、問題のノードは、全てのその近隣のノードに、それが放送局ノードのステータスを獲得したことを示す通知メッセージMを放送し(ステップE58)、それによって選定ステップE5を終了させる。図6を参照すると、候補ノード2、3、5は、ノード7が放送局ノードに選定されたことをそれらに通知する通知メッセージMを受信する。
【0116】
図6の例において、最も小さい待ち時間(WT<WT<WT<WT)を計算した候補ノード7は、通知メッセージMを放送する最初の候補ノードである。これのために、それは、放送局ノード7に選定される。通知メッセージを受信すると、残っている候補ノード2、3、5は、ノード7がちょうど放送局ノードに選ばれたということが通知され、それは、選定ステップE5を終了させる。
【0117】
ちょうど選定された候補ノード7が、仮想アンカーポイントCから最大限でもノードの伝送半径の半分の距離に存在すると仮定すると、ノード7は、アンカー領域Aに位置する全てのノードに通知メッセージMを送信することができるということに、注意が必要である。特に、もしノード7が、選定の時にアンカー領域Aの周囲に存在したならば、すなわち、仮想アンカー中心Cの伝送距離の半分(R/2)に等しい距離に存在したならば、中心Cは、アンカー領域Aの周囲であって、直径に沿ってノード7の反対側に位置する候補ノードに通知することができたであろう。極限では、選定された放送局ノード7と残っている候補ノードとを分割する距離は、ノードの伝送半径に等しかったであろう。
【0118】
選定された放送局ノード7がセルZのアンカーポイントCに到達するとき、それは、そのセルに位置する全ての近隣のノードに、データパケットDを放送する。
【0119】
上で示された方法のステップは、選定された放送局ノードが一定時間ごとにデータパケットDを放送し得るように繰り返される。各反復は、その間にデータパケットが放送局ノードによって放送される周期を定義する。各周期において、それに関して交差点の中心に到達するための推定の時間が可能な限り基準時間期間Tに近い放送局ノードを選定することは、データを周期的に放送する交差点のインフラストラクチャをエミュレートする。従って、その交差点は、データが変化しない放送領域であると考えられ得る。
【0120】
道路網全体を横断してデータを広めるために、交差点を相互接続する車線に沿ってデータを送信することが必要である。このために、本発明は、2つの連続する交差点の間にデータを放送するための進歩的な放送ステージを提供すると共に、その間に、データパケットは、2つの連続する交差点を接続する車線に沿ってパケットが進んでいくにつれて連続して選定された放送局ノードのセットによって放送される。
【0121】
指向性のある伝播ステージは、現在の交差点においてデータパケットを運ぶと共に隣接する交差点の方へ移動する移動ノードによって始められると共に、これらの運搬ノードは、適用範囲セル内の放送局ノードによって以前に放送されたデータパケットDを受信している。
【0122】
図7において示されたように、交差点Jの中心に位置する放送局ノード7は、全てのその近隣のノード、特に適用範囲セルZの周囲に位置すると共に、それぞれ隣接の交差点J、J、Jの方へ移動する周囲の移動ノード20、21、22にデータパケットDを放送した。データパケットを周辺ノード20、21、22に転送することは、各近隣の交差点に対する指向性のある伝播のステージを始める。
【0123】
図8において示されたように、データパケットDは、指向性のある伝播ステージの間に連続して選定される放送局ノード22、23、27によって、2つの連続する交差点J及びJを接続する車線に沿って徐々に放送される。
【0124】
交差点Jから交差点Jへのデータパケットの伝播を可能にする指向性のある伝播ステージは、当業者に知られている放送アルゴリズムに従って実行される。
【0125】
各移動ノードの無線通信端末は、データパケットD及び通知メッセージMを放送すると共に受信することを可能にする送受信手段を備える。
【0126】
各移動ノードに搭載されているナビゲーション装置は、自発的に、そして分散的(非集中的)な方法で、上述の放送局ノードの選定に関連するステップ及びサブステップを達成するように構成されたプロセッサ手段(プロセッサ)を備える。
【0127】
ナビゲーション装置は、ナビゲーション装置と関連付けられたノードがデータパケットを放送する候補であるかどうかを判定することができるソフトウェア手段(選択手段)を備える。もしそうであるならば、ナビゲーション装置に含まれる更なるソフトウェア手段(選定手段)は、そのノードが放送局ノードに選定されたかどうかを判定する。もしそのノードが放送局ノードに選定されるならば、ナビゲーション装置に含まれる更なるソフトウェア手段(起動手段)は、もしそのノードがセルの中心の周辺に存在することをナビゲーション装置が検知するならば、関連した通信端末の送信手段を起動する。
【0128】
特に、前述の数式0、1、2、3は、プログラムされると共にオンボードナビゲーション装置のメモリに保存され、そして、ノードと関連付けられたプロセッサ手段(プロセッサ)によって実行される。
【産業上の利用可能性】
【0129】
第1の応用例において、本発明の放送方法は、車両の経路の計算を最適化するために使用される交通状況情報を広める。
【0130】
第2の応用例において、本発明の放送方法は、運転者に、彼らの現在の位置の周辺で利用可能な駐車場を、リアルタイムで示す。利用可能な駐車場は、車両(移動ノード)によって交差点を横断して広められるこの情報を定期的に放送する放送局において確認されると、仮定されている。
【0131】
第3の応用例において、本発明の放送方法は、イベント(事故、道路工事)が起きている地理的領域内の交通安全情報を広めるために高速道路部分において使用され、それは、交通の変更(交通量の低下、迂回路)を運転者に伝わるようにする。この状況では、警告メッセージを構成するデータパケットが、手動で、もしくは自動的に、イベントの場所で生成される。このデータパケットは、このポイントから近隣の交差点に伝わると共に、ここで、そのパケットは、本発明の放送方法によって、一定時間ごとに放送される。このように、交差点を移動する各車両(移動ノード)は、それが警告領域に入るので、データパケットを受信するときに警告される(警報を出される)。
【符号の説明】
【0132】
1、4、6、20、21、22、24、25、28、29、30:移動ノード
2、3、5、7:候補ノード
22、23、27:放送局ノード
、L12、L13、L、L、L34、L24、L、L、L:車線
、J、J、J、J:交差点
、C、C、C、C:仮想アンカーポイント
、Z、Z、Z、Z:適用範囲セル
:アンカー領域
F:交通信号
D:データパケット
M:通知メッセージ
、v、v、v、v:速度

【特許請求の範囲】
【請求項1】
地理空間を移動するように構成された複数の移動ノード(1−7)によって形成されたネットワークにおいて少なくとも1つのデータパケット(D)を放送する方法であって、
前記方法は、その間に、セルと呼ばれる前記地理空間の所定領域(Z、Z、Z、Z、Z)において前記セルに存在する前記移動ノードに対して少なくとも1つのデータパケット(D)が放送される、ローカル放送を行うステップ(E9)を含み、
前記方法が、更に、
・前記少なくとも1つのデータパケット(D)を受信するステップ(E1)と、
・その間に、前記移動ノードが、それが前記セル(Z)において前記データパケット(D)を放送する候補(2、3、5、7)であるかどうかを判定する、選択ステップ(E3)と、
・前記セル(Z)の中心(C)までの前記候補ノードの推定の移動時間(Δt)に応じて、前記候補ノードを前記セル(Z)における前記データパケット(D)の放送局ノード(7)として選定するステップ(E5)とを含み、
・前記ローカル放送を行うステップ(E9)が、前記放送局ノード(7)が前記セル(Z)の中心(C)付近に位置しているときに実行される
ことを特徴とする方法。
【請求項2】
前記選択ステップ(E3)の間に、前記移動ノードは、それが前記セル(Z)の中心(C)に向かって移動していると共に、それが前記セル(Z)に含まれた前記中心(C)を中心とするアンカー領域(A)に位置していることを条件として、それが前記データパケット(D)を放送する候補(2、3、5、7)であると判定する
ことを特徴とする請求項1に記載の方法。
【請求項3】
前記選定するステップ(E5)の間に、前記候補ノード(2、3、5、7)が、待ち時間(WT)を計算する(E53)と共に、前記計算された待ち時間(WT、WT、WT、WT)の値が、前記セル(Z)の中心(C)までの前記候補ノードの推定の移動時間(Δti;Δt、Δt、Δt、Δt)が所定の基準時間期間(T)に近づくにつれて減少し、前記待ち時間(WT)の終わりにおいて、前記候補ノードは、もしそれが別のノードから放送局ノード(7)に選定されたことを伝える通知メッセージを受信していなかったならば、それが放送局ノード(7)に選定された(E58)ことを伝える通知メッセージ(M)を放送する
ことを特徴とする請求項1に記載の方法。
【請求項4】
前記所定の基準時間期間(T)が、前記ローカル放送を行うステップ(E9)の期間に対応する
ことを特徴とする請求項3に記載の方法。
【請求項5】
前記待ち時間(WT、WT、WT、WT)が、更に、無作為に生成された数γに応じて計算される
ことを特徴とする請求項3に記載の方法。
【請求項6】
前記地理空間が、複数の車線(L、L、L、L、L、L、L12、L13、L24、L34)から成り、それらの間に複数の交差点(J、J、J、J)を形成している交通網であると共に、
前記セル(Z、Z、Z、Z)が、交差点(J、J、J、J)と関連付けられている
ことを特徴とする請求項1に記載の方法。
【請求項7】
複数の通信移動ノードを含むネットワークの移動ノードであって、
前記移動ノードが、
・少なくとも1つのデータパケット(D)を受信するように構成された受信機手段と、
・前記少なくとも1つのデータパケット(D)を前記ノードの範囲領域の中に位置している移動ノードに対して放送するように構成された放送局手段とを具備し、
前記移動ノードが、更に、
・前記移動ノードが前記ネットワークと関連するセル(Z)と呼ばれる地理空間の所定領域において前記データパケットを放送する候補であるかどうかを判定するように構成された選択手段と、
・前記セル(Z)の中心(C)までの前記候補ノードの推定の移動時間(Δt)に応じて、前記候補ノードを前記セル(Z)における前記少なくとも1つのデータパケット(D)の放送用の放送局ノード(7)として選定するように構成された選定手段と、
・前記放送局ノード(7)が前記セルの中心付近に位置しているときに前記放送局手段を起動するように構成された起動手段とを具備する
ことを特徴とする移動ノード。
【請求項8】
前記選択手段は、もし前記移動ノードが前記セル(Z)の中心(C)に向かって移動していると共に、それが前記セル(Z)に含まれた前記中心を中心とするアンカー領域(A)に位置しているならば、前記移動ノードが前記データパケットを放送する候補(2、3、5、7)であると判定するように構成される
ことを特徴とする請求項7に記載の移動ノード。
【請求項9】
前記選定手段が、
・待ち時間(WT、WT、WT、WT)を計算するための手段と、
・前記候補ノードが放送局ノードに選定されたことを伝える通知メッセージを放送するための手段とを具備し、
前記待ち時間(WT)の計算された値が、前記セルの中心までの前記候補ノードの推定の移動時間(Δt)が所定の基準時間期間(T)に近づくにつれて減少すると共に、
もし前記候補ノードが別のノードから放送局ノードに選定されたことを伝える通知メッセージを受信していなかったならば、前記通知メッセージを放送するための手段が前記待ち時間の終わりに起動される
ことを特徴とする請求項7に記載の移動ノード。
【請求項10】
特定の交通網の車線上を移動する複数の移動ノードを含む無線通信システムであって、
各ノードが請求項7に記載の移動ノードである
ことを特徴とするシステム。
【請求項11】
コンピュータプログラムであって、前記プログラムがコンピュータによって実行されるときに、請求項1から請求項6のいずれか一項に記載の放送する方法のステップを実行するための命令を含むことを特徴とするコンピュータプログラム。
【請求項12】
請求項1から請求項6のいずれか一項に記載の放送する方法のステップを実行するための命令を含むコンピュータプログラムを記憶していることを特徴とするコンピュータ読み取り可能な記憶媒体。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5A】
image rotate

【図5B】
image rotate

【図5C】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate


【公表番号】特表2011−501597(P2011−501597A)
【公表日】平成23年1月6日(2011.1.6)
【国際特許分類】
【出願番号】特願2010−530519(P2010−530519)
【出願日】平成20年10月17日(2008.10.17)
【国際出願番号】PCT/FR2008/051881
【国際公開番号】WO2009/053657
【国際公開日】平成21年4月30日(2009.4.30)
【出願人】(591034154)フランス・テレコム (290)
【Fターム(参考)】