(57)【要約】      （修正有）【課題】マルチ‐ホップおよびモバイル・インフォステーション・ネットワーク両方のハイブリッドを使用するルーティング・ストラテジを提供する。【解決手段】ソースとディスティネーションの間においてパケットを転送するために互いに通信するモバイル・ノードが、順方向の移動においてパケットを通信するためにマルチ‐ホップ・ネットワーク・ストラテジを使用し、逆方向の移動においてパケットを通信するためにモバイル・インフォステーション・ネットワーク・ストラテジのみ、あるいはマルチ‐ホップ・ネットワーク・ストラテジとともにそれを使用し、それによって、容量の改善とランダム・パケット遅延の間のトレードオフを平衡させるコントロールされたフラッディング通信スキームを利用する。このシステムは、インテリジェント・ハイウェイ情報システムを含む種々の応用に使用することができる。【選択図】図３
2006229968.tif 000002
【特許請求の範囲】
【請求項１】
関連付けされた移動方向を有する複数のモバイル中間ノードを使用してソース・ノードからディスティネーション・ノードにネットワーク・パケットをルーティングする方法であって、
第１の中間ノードにおいてパケットを受信し、かつ前記第１の中間ノードに対する情報の流れの方向を決定するステップ、
前記第１の中間ノードの前記移動方向が前記情報の流れの方向に対応する場合に、前記パケットを第２のモバイル中間ノードに送信するステップ、および、
前記第２の中間ノードを使用して前記ディスティネーション・ノードに向かう前記パケットの送信を続行するステップ、
を包含する方法。
【請求項２】
さらに、前記第１の中間ノードの前記移動方向が前記情報の流れの方向に対応しない場合に、前記パケットを破棄することを包含する、請求項１に記載の方法。
【請求項３】
さらに、前記パケットの現在の位置が、前記ソース・ノードおよび前記ディスティネーション・ノードの位置に対するあらかじめ決定済みの範囲外であるか否かを決定し、前記現在の位置が前記あらかじめ決定済みの範囲外である場合には前記パケットを破棄することを包含する、請求項１に記載の方法。
【請求項４】
さらに、前記第１および第２の中間ノードの１つにおいて、前記パケットがそのノードによって以前に送信されたことがあるか否かをテストし、送信されたことがあれば前記パケットを破棄することを包含する、請求項１に記載の方法。
【請求項５】
さらに、前記ソース・ノードにおいて前記パケットにタイムスタンプを取り付けること、および前記第１および第２の中間ノードの１つにおいて前記タイムスタンプの取り付けからあらかじめ決定済みの時間が経過したか否かをテストし、経過していれば前記パケットを破棄することを包含する、請求項１に記載の方法。
【請求項６】
ソースとディスティネーションの間においてネットワーク・パケットをルーティングするためのルーティング・システムであって、
それぞれが関連付けされた移動方向を有し、かつ有限送信レンジにわたってパケットの送信および受信を行うべく適合された複数のモバイル中間ノード、
前記ノードのそれぞれが、次のａからｄまでのデータ要素をストアするべく構成されたメモリを有すること、
（ａ）ソースの位置、
（ｂ）ディスティネーションの位置、
（ｃ）現在の位置、および、
（ｄ）ペイロード情報
前記ノードのそれぞれが、現在の位置が、ソースの位置とディスティネーションの位置を比較することによって決定されるとおりの情報の流れの方向にあるか否かを決定するべく構成され、かつ前記ノードとは別のノードに、前記ノードとは別のノードの現在の位置が情報の流れの方向にある場合に前記パケットを送信するべく構成されていること、
を包含するルーティング・システム。
【請求項７】
前記ノードは、さらに、前記ソースおよびディスティネーションの位置を基礎として範囲を確かめるべく構成され、かつ前記現在の位置がその範囲外であるとき前記パケットを削除するべく構成される、請求項６に記載のルーティング・システム。
【請求項８】
前記メモリは、さらにノードのシーケンス番号をストアするべく構成されており、それにおいて前記ノードは、さらに前記パケットが以前にそのノードによって送信されたことのある同一のシーケンス番号を伴うパケットである場合にはそれを破棄するべく構成される、請求項６に記載のルーティング・システム。
【請求項９】
前記メモリは、さらに前記ソースの位置から前記パケット送信された時刻に対応するタイムスタンプをストアするべく構成されており、それにおいて前記ノードは、さらに、前記タイムスタンプが生成されてからあらかじめ決定済みの時間が失効すると前記パケットを破棄するべく構成される、請求項６に記載のルーティング・システム。
【請求項１０】
前記モバイル・ノードはワイヤレス・ネットワーク・トランシーバを使用してそれらの間においてパケットを送信する、請求項６に記載のルーティング・システム。
【請求項１１】
ソースからディスティネーションにパケットを送信するためにそれぞれが互いに通信するべく構成された複数のモバイル・ノード、
前記モバイル・ノードのそれぞれが、同時に、
マルチ‐ホップ・ネットワーク・ストラテジ、および、
モバイル・インフォステーション・ネットワーク・ストラテジ、
を具体化するべく構成されること、および前記モバイル・ノードがさらに、第１の方向に移動するモバイル・ノード間においてパケットを通信するために前記マルチ‐ホップ・ネットワーク・ストラテジを使用し、かつ前記第１の方向と反対の第２の方向に移動するモバイル・ノード間においてパケットを通信するために前記モバイル・インフォステーション・ネットワーク・ストラテジを使用するように構成されること、
を包含するハイブリッド・モバイル・アドホック・ネットワーク・アーキテクチャ。
【請求項１２】
前記マルチ‐ホップ・ネットワーク・ストラテジは、前記第２の方向に移動するモバイル・ノード間においてパケットを通信するためにも使用される、請求項１２に記載のネットワーク・アーキテクチャ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して情報のルーティングのためのネットワーク・ストラテジに関する。より詳細に述べれば、本発明は、マルチ‐ホップおよびモバイル・インフォステーション・ネットワーク両方のハイブリッドを使用するルーティング・ストラテジに関する。本発明は、多くの用途を有するが、ここでは、インテリジェント・ハイウェイ・レポーティング・システム内において使用される情報ルーティング・システムに関連して述べる。
【背景技術】
【０００２】
情報ルーティング・システムは、多くの形式を取ることが可能である。しばしば、最適ルーティング・ソリューションは、情報が伝播しなければならないノードの物理的トポロジによって左右される。モバイル・ネットワーク・システムは、通信ノードが常に固定された位置に配置されるとは限らないという事実に部分的に起因して独特の問題のセットを呈する。結果として、任意の２つのノードが信頼伝送レンジを超える距離によって隔てられるとき、それら２つのノード間の通信が散発的に切断される。場合によっては、通信を再確立することができるが、そのほかの場合には無期限に通信が切断されることもある。
【０００３】
文献上においては、モバイル・アドホック・ネットワークは２つの基本パラダイムに分類される、すなわち、マルチ‐ホップ・ネットワークおよびモバイル・インフォステーション・ネットワークである。マルチ‐ホップ・ネットワークにおいては、マルチ‐ホップ・ルーティングを使用してノードが互いに通信する。マルチ‐ホップ・ネットワークは、しばしば『アドホック・ネットワーク』とも呼ばれている。モバイル・インフォステーション・ネットワークにおいては、ノードが短い送信レンジで動作し、それらが近接しているときに限り通信する。したがってノードの可動性が、情報のパケットがどのように送信されるかにおいて重要な役割を演じている。各ノードは、ほかのソースおよびディスティネーション・ノードの中継ノードとして作用することもあり、それが移動するとき、ソース・ノードからディスティネーション・ノードへ物理的にパケットを運ぶことになる。
【０００４】
現行のパラダイムは、いずれも利点ならびに欠点を併せ持つ。マルチ‐ホップ・ネットワークは、概してスケーラブルでない。したがって、マルチ‐ホップ・ノードの数が増加すると、与えられたソース‐ディスティネーション接続の達成可能なスループットが漸近的にゼロに向かう。これに対してモバイル・インフォステーション・ネットワークは、よりスケーラブルである。ソース‐ディスティネーション通信フローの達成可能なネットワーク・スループットは、モバイル・インフォステーション・ネットワーク内のネットワークのサイズと独立している。しかしながら容量の改善は、ランダムなパケット遅延の代償としてもたらされる。この遅延は、可動性プロセスの時間スケールに関連する。したがって、物理的空間内をノードがよりゆっくりと移動するようになると、ランダムなパケット遅延が増加する。
【０００５】
本発明は、マルチ‐ホップおよびモバイル・インフォステーション・ネットワークを、一般的な容量‐遅延トレードオフの２つの極端な事例として取り扱う。それに加えて、瞬時データ配信とネットワーク・パーティショニングに対する堅牢性の間におけるトレードオフも扱うネットワーク・ストラテジに焦点を当てる。
【０００６】
本発明によって取られるハイブリッド・アプローチの例示として、インテリジェント・ハイウェイ・レポーティング・システムを説明する。その種のシステムにおいては、所定のハイウェイ上の場所における渋滞、事故、またはそのほかの沿道情報の緊急交通レポートがレポートされて、行く手にある接近しつつある交通情況についてドライバに警告する。その種の応用においては、生成されるパケットの数ならびにパケット・サイズは小さくなりがちであり、したがってネットワーク容量が緊急の関心事とならない。それに代わり、いくつかのメッセージが緊急性を持つことがあるため、データの配信について厳しい遅延要件が存在する。パケット遅延が大きい場合には、渋滞地点の現場の後の自動車が、その交通情況を回避して適時にハイウェイを出ることが不可能になることがある。同様に自動車が、事故の現場を通過する前までに安全な速度まで減速する充分な時間を得られないことがある。
【発明の開示】
【発明が解決しようとする課題】
【０００７】
インテリジェント・ハイウェイ・レポーティング・システムの具体化における以前のアプローチは、セルラ・ネットワークの利用に傾いていた。セルラ通信は、成熟したテクノロジであり、乗り物応用においてそれを採用するためにもたらされる技術的障害は比較的小さい。しかしながら、セルラ・ネットワークを介したパケットのルーティングは、本質的に高価であり、効率的でない。
【課題を解決するための手段】
【０００８】
本発明は、ネットワーク・ストラテジのアーキテクチャにハイブリッド・アプローチを採用している。ハイブリッド・アプローチは、マルチ‐ホップおよびモバイル・インフォステーション・ネットワーク両方の利点を利用し、それぞれの欠点を最小化するか、あるいはそれと取り組む。現在のところ好ましいその形式において、各ノードは、ディスティネーションとパケット・ソースの位置の間にあるとき、パケットの転送にかかわる。各パケットは、そのパケット・フィールド内にソース座標を含む。それによりノードは、単純に、その現在の座標と適切なパケット座標を比較することによって、パケットを転送するか否かを決定することが可能になる。各パケットは、オリジナルのソース・パケットが作成された時刻のタイムスタンプも含む。パケットが妥当な時間内にディスティネーションに到達することができない場合には、送信ノードがそれを検出してそのパケットを破棄することができる。各パケットは、事象フィールドも含み、そこには交通渋滞の状態あるいは事故といった事象の基本的なレポートが含まれる。ネットワーク上においては有向フラッディングが使用される。ノードｊがノードｉからパケットを受信するとき、その位置がノードｉよりもディスティネーションに近い場合に限り、そのパケットを再度送信する。これは、単純にパケット内に送信機位置フィールドを含めることによって達成可能である。その場合、受信機ノードは、その現在位置と送信機位置を比較することによってパケットを転送するか否かを決定する。各パケットは、また、シーケンス番号をパケット・フィールド内に有する。このシーケンス番号は、フラッディングの具体化においてノードが、同一パケットを再三にわたって繰り返し送信することを防止する。ノードは、パケット内のシーケンス番号を調べ、コントロールされたフラッディングをサポートするべく１回に限りそれを転送する。
【０００９】
本発明の適用可能性の追加の分野については、以下に提供される詳細な説明から明らかになるであろう。ここで理解する必要があるが、これらの詳細な説明および特定の例は、本発明の好ましい実施態様を示してはいるが、例示のみを目的としており、本発明の範囲を限定することは意図されていない。
【００１０】
本発明は、以下の詳細な説明および添付の図面からより完全に理解されることになろう。
【発明を実施するための最良の形態】
【００１１】
以下の好ましい実施態様（１ないしは複数）の説明は、本質的に例示に過ぎず、いかなる形においても本発明、その応用、または利用を限定する意図はない。
【００１２】
本発明の原理を理解するために、最初に、いくつかの基本的なパケット・ルーティング・テクニックについて再考する。図１を参照すると、全体が１０としてモバイル・アドホック・ネットワークが例示されている。このネットワーク内のノードは、アクセス・ポイントあるいは基地局等のインフラストラクチャの使用を必要とすることなく互いに通信する。ノードは、ソース、ディスティネーション、および／またはパケットのルータとして作用することができる。モバイル・アドホック・ネットワークには２つの基本タイプ、すなわちマルチ‐ホップ・ネットワークおよびモバイル・インフォステーション・ネットワークが存在する。図１は、マルチ‐ホップ・ネットワークを表している。
【００１３】
図１のマルチ‐ホップ・ネットワークにおいては、通常、ほとんどの時間にわたってネットワークが接続される（つまりネットワーク・パーティショニングがない）送信レンジを有することが前提とされる。ノードが大きなエリアにわたって空間的に分布することから、有限の送信レンジに起因して任意の２つのノードが直接通信できないことがある。ソース・ノードが送信するパケットを有しているとき、通常、ルート発見メカニズムを起動して、それが意図しているディスティネーションに対するルートを見つける。ルートは、オン・デマンドで作成され、ネットワーク・トポロジが変化することから、ルートを更新するルート・メンテナンスが実行されなければならない。このタイプのネットワーク用のルーティング・メカニズムは、概してリアクティブ・ルーティング・スキームとしてカテゴリ分類される。
【００１４】
アドホック・ネットワークの第２のクラスは、主としてモバイル・インフォステーション・ネットワークであるが、それが図２の１２に例示されている。モバイル・インフォステーション・ネットワークにおいては、さらに小さい送信電力でノードが動作する。ネットワークは、多くの場合、激しくパーティショニングを受ける（すなわち、互いに関してノードはレンジ外であり、したがって任意の所定時において通信パス内に切断が存在する）。
【００１５】
モバイル・インフォステーション・ネットワークにおいては、任意の２つのノードが、それらが近接しており、かつ非常に良好なチャンネルを有している場合に限って通信する。この送信制約の下においては、任意のノードのペアが、可動性がそれらのノードの位置をシャッフルすることから断続的に接続される。モバイル・インフォステーション・ネットワークのネットワーク容量は、従来のマルチ‐ホップ・アドホック・ネットワークに好適になぞらえる。比較すると、マルチ‐ホップ・ネットワークのノード当たりのスループットは、多数のノードｎの極限内においてＯ（１／（ｎ  ｌｎ  ｎ）１／２）のレートでゼロまで低下する。したがって、マルチ‐ホップ・ネットワークは、大きなネットワーク・サイズに伴ってスケーリングされない。これに対して、モバイル・インフォステーション・ネットワークのノード当たりのスループットは、ノードの数とは独立にＯ（１）である。この容量は、２ホップ中継ストラテジを介して達成される。
【００１６】
図２に示されているモバイル・インフォステーション・ネットワークにおいて、ネットワーク内の各ノードが、ユニキャストのためにランダムなディスティネーションを選択すると仮定する。図２において、ディスティネーション・ノードに配信するパケットを有するソース・ノードｉに注目する。ノードｉは、時間経過とともにランダムな軌跡に沿って移動し、結局はノード１および２と遭遇する。ノード１もしくは２のいずれもノードｉのディスティネーションではないことから、ノードｉは、中継ノードのそれぞれがディスティネーションｊに到達するとき、それがノードｉに代わって第２の中継を完成することを期待してそれらにパケットを中継する。安定状態においては、ほかのｎ‐２のノードのそれぞれが、ノードｉによって生成され、かつディスティネーションｊが指定されたパケットを含む。任意のネットワーク・スナップショットにおいて、ディスティネーションｊにもっとも近い近隣が、ノードｉからアドレスされたパケットを有し、ノードｉに代わって第２の中継を完成することがほとんど確かである。すなわち、長期にわたるスループットは一定であり、ネットワーク・サイズと独立している。この容量の改善は、ネットワーク全体にわたりパケットを物理的に運び、しかも基礎をなす可動性モデルから独立しているノードの可動性を利用することからもたらされる。しかしながら、ネットワーク容量の改善の大きさの程度は代償を伴う。エンド‐ツー‐エンド送信は、可動性プロセスと同じ時間スケールのランダムな遅延を受ける。
【００１７】
マルチ‐ホップ・ネットワークおよびモバイル・インフォステーション・ネットワークは、多くの可能なネットワーク・パラダイムにわたる容量‐遅延トレードオフの２つの極端な事例である。モバイル・インフォステーション・ネットワークは、ランダムで制限のない遅延の代償として大きな容量を可能にする。これに対してマルチ‐ホップ・ネットワークは、迅速なデータ配信を可能にするが、ノード数に伴うスケーラブルなネットワーク容量は得られない。モバイル・インフォステーション・ネットワークにおけるデータの伝達を迅速化するために、マルチ‐ホップ転送を、ノードがある時間にわたってほかのノードのためにそれを行っていない場合に、臨時に行うこともできる。同様に、ノードの可動性をマルチ‐ホップ・ネットワークにおいて利用し、ネットワーク・パフォーマンスを改善することも可能である。たとえば、ノードの可動性を利用して、通信のオーバーヘッドを招くことなくすべてのノードの位置の座標を伝達する。この位置情報は、地理的なルーティング・スキームが使用される場合に、ノードが、ディスティネーションに対するローカル・ルーティング決定を行う上で有用である。
【００１８】
インテリジェント・ハイウェイ・レポーティング・システムに関して言えば、容量の問題は主要な考慮事項ではない。ハイウェイ上の乗り物間の距離が大きいことから、パケット送信が散発的になる。パケット・サイズは、パケットが、ソース・ノード座標、そのパケットがいつ作成されたかを表すタイムスタンプ、および事象のタイプ（事故または渋滞）等のエア・コントロール情報のみを含むことから小さくなる傾向になる。これに対して、遅延パフォーマンスを重要なパフォーマンス評価基準とすることはより適切である。容量‐遅延のトレードオフの観点からマルチ‐ホップ・ネットワークよりモバイル・インフォステーション・ネットワークが優先される理由は皆無である。
【００１９】
残りの図面を参照してさらに立証するとおり、ここで採用されるハイブリッド・アプローチは、マルチ‐ホップ・ネットワークとモバイル・インフォステーション・ネットワークの間のトレードオフの別のセットを明らかにする。マルチ‐ホップ・ネットワークは、概して迅速なデータ・パケットの配信をもたらすが、同時にネットワーク・パーティショニングに対して脆弱でもある。ハイウェイのシナリオにおいては乗り物間距離が一般に大きい、ノード密度が一般に低い。低いノード密度に起因して、かつハイウェイ・ネットワークが本質的に１次元であり、ネットワーク・パーティショニングに対して脆弱であるという事実によって助長されてネットワーク・パーティショニングが生じがちである。これに対して、モバイル・インフォステーション・ネットワークは、設計上、ノードの可動性に対して堅牢である。激しいネットワーク・パーティショニングは、モバイル・インフォステーション・ネットワークにおけるノルムであり、それは、効率的なデータ配信を明示するものではなく、ノードの可動性のみに依存する。またモバイル・インフォステーション・ネットワークのパケット遅延は、ハイウェイ応用における高いノードの可動性および指向性のあるノードの可動性によって劇的に短縮される。特に、パケット遅延もまた、より少ない変動を伴って、より決定論的となる。モバイル・インフォステーション・ネットワークおよびマルチ‐ホップ・ネットワークのハイブリッド・アプローチを実施し、ネットワーク接続性が利用可能であるときにはマルチ‐ホップ接続を利用し、ネットワーク・パーティショニングが生じているときにはモバイル・インフォステーション・ネットワークのクーリエ・サービスに頼ることが望ましい。これは、広範な交通および可動性のシナリオに対して堅牢な遅延パフォーマンスを保証することになる。
【００２０】
図３〜１１において、モバイル・ネットワークを構築するための４つのストラテジについて考察する。図３〜５および６〜７に例示されているストラテジは、それぞれ純粋なマルチ‐ホップ・ネットワークおよびモバイル・インフォステーション・ネットワークの事例である。図８〜１０および１１〜１２に例示されているストラテジは、モバイル・インフォステーションおよびマルチ‐ホップ・ネットワークのハイブリッド事例である。現在のところ図１１〜１２のストラテジの方が好ましく、発明者らの研究によって、ほかとの比較から最良の遅延パフォーマンスを提供することが明らかになった。現行の８０２．１１テクノロジを使用するストラテジを利用するための具体化が可能である。しかしながら、ほかのテクノロジを使用することもできる。
【００２１】
図３を参照すると、ストラテジＩは、順方向交通のみを伴うマルチ‐ホップ・ネットワークに頼っている。言い換えると、乗り物がディスティネーションの位置の方向に移動することを前提として、パケットがノードからノードへ（乗り物から乗り物へ）渡される。図３に例示されているとおり、すべてのノードは順方向に移動する。パケットは、ノードｉにある。ノードが異なるランダムな速度で移動することから、ノードが互いを追い越し、あるいは追い越されることがあり得る。ここで、ノードｊがノードｉより高速であるとする。ノードｊがノードｉの送信半径内に移動したとき、接続が確立される。これが生じると、ノードｉはパケットをノードｊに送信する。ノードｊは、そのパケットを受信すると、次のネットワーク・パーティションが生じるまで、つまりこの例ではノードｋにおいてそれが生じるまで、ディスティネーションに向かってパケットを送信するマルチ‐ホップ送信を試みる。
【００２２】
図４はストラテジＩＩを例示している。このストラテジでは、ノードｊがノードｋに接続されない。したがってパケットがノードｉからノードｊに、それらの接続が確立されている間に単一ホップで送信される。しかしながらノードｊは、より高速であることから最終的にノードｉを追い越すことになる。ノードの遭遇が生じると、そのパケットが、意図されたディスティネーションに近いノードｉに戻されることになる。ここで注意が必要であるが、このストラテジにおいて、システムは、２つの状態の間を交番する。接続状態においては、パケットを伴うノードが後方のノードに接続される。パケットは、別のノード・パーティションが生じるまで、ディスティネーションに向かうマルチ‐ホップ転送を使用して送信される。したがってパケットは、瞬時にディスティネーションに向かう正の進行を行う。非接続状態においては、順方向ノードが常にディスティネーションから離れる方向に移動しているため、パケットが負の進行を行う。
【００２３】
ストラテジＩにおける接続状態と非接続状態の間の交番は、図５に示されているとおり、時間に対してパケット軌跡をプロットすることによって視覚的に表すことができる。パケットがディスティネーションに対して前後に移動することから、ジグザグのパケット軌跡が観察される。当初パケットは、原点にあるディスティネーションからｄ＝１０の距離にある。ｔ＝０において、パケットが、瞬時にｄ＝７のノードにマルチ‐ホップする。続いてこのパケットを運ぶノードは、ｔ＝０．４において新しい接続ができるまで、非接続状態でディスティネーションから離れる方向に移動する。このモデルにおいてマルチ‐ホップが瞬時であることから、ここでもノードが接続状態において使用する時間は無視できる。直感的に言えば、接続状態における順方向の進行は、ノードに依存する。高いノード密度においては、パケットが、ネットワーク・パーティションによって行き詰まるまで、マルチ‐ホップをトラバースする傾向がある。一方、非接続状態においてパケットによってトラバースされる距離ならびに消費される時間の量もまたノードの密度に依存する。ノード密度が高い場合には、ネットワーク・パーティショニングがあまり起こらず、パケットが非接続状態に貼り付くことがない。その逆にノード密度が低い場合には、パケットが非接続状態で有意の時間を消費し、有限時間内においてパケットがディスティネーションに到達できないこともあり得る。
【００２４】
ストラテジＩＩの下においては、パケットが逆方向交通のみによって運ばれる。逆方向ノードが物理的にディスティネーションに向かって物理的に運ぶことから、モバイル・インフォステーション・ネットワーク・スキームの事例となる。図６を参照すると、パケットは、当初ソース・ノードにおいて作られる。逆方向ノードｉとソース・ノードの間において接続が確立すると、ソースが、逆方向ノードにパケットを中継し、それがディスティネーションに向かってそのパケットを物理的に運ぶ。さらに時間の経過とともに逆方向ノードｉが、より高速なノード、たとえばノードｊに追い越されることがある。逆方向対逆方向のノードの遭遇が生じると、ノードｉは、ノードｊにパケットを中継してパケット送信を迅速化することができる。
【００２５】
図７を参照すると、時間に対してプロットされたストラテジＩＩのパケット軌跡が示されている。当初パケットは、原点のディスティネーションから距離ｄ＝１０にある。逆方向ノードｉは、ｔ＝０．４においてソースに到達し、そのパケットをディスティネーションに向けて運ぶ。逆方向ノードｊは、その後方にいるが、より高速で移動している。ｔ＝１．５においてノードｊがノードｉを追い越し、パケットがノードｊに中継されてパケット配信が迅速化される。ここで観察されとおり、このモデルにおいてパケット軌跡は、時間の区分線形関数である。頂点は、より高速のノードがパケットを運ぶノードを追い越す事象に対応する。
【００２６】
総合的なパケット遅延は、逆方向ノードと遭遇するまでの待機時間およびディスティネーションに向かって逆方向ノードが移動する時間の合計である。実用的な関心通信距離について、λをノードの到着レートとするとき、ｄ＞＞１／λである。パケット遅延は逆方向ノードの移動時間によって支配される。さらに、ｄが大きいときには、より低速の逆方向ノードが、より高速の逆方向ノードによって追い越されることがありがちとなる。逆方向ノードが、必ずディスティネーションに向かう方向にあることから、またパケットのクーリエが高速のノードとなりがちであることから、ランダムな可動性を伴う平面ネットワーク内におけるよりはるかに効率的である。
【００２７】
以上から認識されるとおり、ストラテジＩおよびＩＩは、ネットワーク・アプローチの２つの極端な事例を例示している。ストラテジＩは、マルチ‐ホップ送信を排他的に使用する。通常に提供される道路環境においてワイヤレス送信の遅延は無視できるが、ネットワーク・パーティションを有することの遅延の代償は高い。順方向ノードは、非接続状態において常に意図されたディスティネーションから遠ざかる。これは、システムが非接続状態において有意な時間を消費するということが高いノードの可動性によって左右される乗り物ネットワークにおいて重要な結果を有する。これに対して、ストラテジＩＩは、モバイル・インフォステーション・パラダイムを使用することによって、ネットワーク・パーティショニングの問題をまとめて回避する。モバイル・インフォステーション・ネットワークにおいては、遅延パフォーマンスがノードの可動性にのみ依存し、ネットワーク・パーティショニングとは無関係になる。通信は、ネットワークに沿ってノードがパケットを物理的に運ぶときに生じる。マルチ‐ホップ・ネットワークに内在する瞬時の配信を利用するとともに、ネットワーク・パーティショニングに対するモバイル・インフォステーション・ネットワークの堅牢性を享受することが望ましい。次に例示するストラテジＩＩＩは、ハイブリッド形式でマルチ‐ホップおよびモバイル・インフォステーション両方のネットワーク・パラダイムが使用されるストラテジである。
【００２８】
ここで、ストラテジＩＩＩを例示した図８を参照する。ストラテジＩＩＩは、順方向および逆方向交通をともに使用する。順方向ノードについて、ストラテジＩＩＩは、図３および４に図示したものと同じ、ほかの順方向ノードに対する接続の確立ならびにノード遭遇プロシージャを使用する。同様に逆方向ノードは、ほかの逆方向ノードとの遭遇について、図６に示したものと同じプロシージャを使用する。順方向対順方向ノード・トランザクションおよび逆方向対逆方向ノード・トランザクションに加えてストラテジＩＩＩは、順方向と逆方向のノードの間における接続の確立ならびにノードの遭遇を可能にする。図８を参照すると、ノードｉおよびノードｊは、それぞれ逆方向および順方向のノード・エンティティである。ノードｉおよびノードｊが同一の送信レンジ内にあるとき、接続の確立が生じる。ノードｉがパケットを運んでいる場合には、ノードｊがそのパケットをより遠くに、すなわちこの例ではノードｋにマルチ‐ホップするという期待の下に、そのパケットをノードｊに渡す。しか心ながら、ノードｊがノードｋに接続しない場合には、図９に示されるように最終的にノードｊがノードｉに追いつく。ノードｊがディスティネーションから離れる方向に移動することから、パケットは、ディスティネーションに配信されるべくノードｉに中継し戻される。
【００２９】
図１０に、ストラテジＩＩＩのパケット軌跡の例を示す。当初パケットは、逆方向ノードによって運ばれる。このストラテジは、日和見的であり、逆方向ノードが順方向ノードに接続される都度、瞬時のマルチ‐ホップ送信を利用する。この例の場合には、マルチ‐ホップ送信がＴ＝０．８、１．２、２．１、２．８、および３．６において試みられている。最悪シナリオでは、順方向ノードが非接続状態において有意の時間を消費する。パケットは、最終的に、図９に示されている規則に従って逆方向ノードに戻される。
【００３０】
この例に示されているとおり、パケットは、逆方向ノードの軌跡を補間することによって推論できるように、ほとんどの時間を逆方向ノード内で消費する。最終的にＴ＝３．６において、逆方向ノードおよびディスティネーション・ノードが順方向ノードによって接続される。その後、パケットが瞬時にディスティネーション・ノードにマルチ‐ホップされる。
【００３１】
ストラテジＩＩＩは、順方向交通のためにマルチ‐ホップ・ネットワークの、逆方向交通のためにモバイル・インフォステーション・ネットワークのユーザを使用する。しかしながら、マルチ‐ホップ送信についても逆方向ノードを追加して使用することによってさらにパケットの遅延を短縮することができる。ストラテジＩＶとして示すストラテジは、ストラテジＩＩＩに類似しており、さらに日和見的にマルチ‐ホップ送信を頼る。一例のパケット軌跡は、ストラテジＩＩＩのそれに類似しているが、各日和見的マルチ‐ホップ送信においてディスティネーションに向かう順方向の進行が可能性としてより長くなる。マルチ‐ホップ送信の効率は、この場合、マルチ‐ホップ・ルートが順方向ならびに逆方向の両方からセットアップされることから向上する。低いノード密度においては、複数の送信が散発的であり、利用することができない。パケットは、ほとんどの時間にわたって逆方向ノードによって運ばれることになる。したがって、パケット遅延はストラテジＩＩＩに類似となり、それは、これら両方の場合においてモバイル・インフォステーション・ネットワークが支配的な通信モードとなることによる。
【００３２】
ストラテジＩＶは、フラッディングの形式を採用する。現在のところ好ましいストラテジＩＶの具体化においては、ノードがアドレスを有していない。各ノードは、それがディスティネーションとパケット・ソースの位置の間にあるとき、パケットの転送にかかわる。各パケットは、そのパケット・フィールド内にソース座標を含んでいる。その場合にノードは、現在の座標と適切なパケット・フィールドを比較することによって、単純にパケットを転送するべきか否かを決定することができる。また各パケットは、オリジナルのソース・パケットが作成されたときのタイムスタンプも含んでいる。パケットが妥当な時間内にディスティネーションに到達できなかった場合に、送信ノードは、そのパケットを破棄する。各パケットは、交通渋滞または事故等の事象の基本レポートをストアする事象フィールドも含む。有向性フラッディングがこのネットワーク上において使用される。ノードｊがノードｉからパケットを受け取るとき、その位置がノードｉの位置よりもディスティネーションに近いときに限り、そのパケットを再度送信する。これは、パケット内に送信機位置フィールドを含むことによって単純に行うことができる。続いて受信機ノードは、その現在位置と送信機位置を比較することによってパケットを転送するべきか否かを決定する。また各パケットは、パケット・フィールド内にシーケンス番号も有している。シーケンス・ノードは、フラッディングの具体化においてノードが、再三にわたる同一パケットの送信の繰り返しを行うことを防止する。ノードは、コントロールされたフラッディングをサポートするためにパケット内のシーケンス番号を調べて１度だけそれを送信する。
【００３３】
図１１を参照するとストラテジＩＶが例示されている。特に図１１は、現在のところ好ましいデータ構造５０を図示するとともに、データ・パケットが情報フロー方向に対して両方向に送信される態様を例示している。現在のところ好ましい実施態様においては、モバイル・ノードに、それらがペイロード（ソースとディスティネーションの間において通信される事象に関する情報）だけでなく、動作中のシステムによって使用されるほかのメタデータもストアできるように、データ構造５０に従って構成されたメモリが備えられる。したがってこのデータ構造は、ソース・ノード、すなわちパケットが最初に生成されたノードの座標をストアすることなどによってソース位置をストアするフィールドまたはストレージ・ロケーションを含む。同様にデータ構造５０は、そのパケットの意図されたディスティネーションの座標を与えるディスティネーション位置をストアするフィールドまたはストレージ・ロケーションも含む。それに加えて好ましいデータ構造は、そのパケットが最初に送信された時刻、あるいはそれに代えてそのパケットが満了となる時刻をストアするタイムスタンプ・フィールドまたはストレージ・ロケーションも含む。いずれの場合においてもタイムスタンプは、あらかじめ決定済みの時間内に配信されなかったパケットの抹消に使用される。データ構造５０はまた、送信機位置がストアされるストレージ・ロケーションまたはフィールドを含む。このフィールドは、そのパケットが送信されるときの送信ノードの現在位置を含む。シーケンス番号フィールドまたはストレージ・ロケーションは、パケットの一意的な識別に使用されるシーケンス番号をストアする。したがって複製パケットは、同一のシーケンス番号を有することから容易に検出される。
【００３４】
例示のストラテジＩＶにおいては、情報がソースからディスティネーションに例示されているとおりに流れる。所定のノードについての移動方向は、概して情報の流れと逆方向または情報の流れと同じ方向になることができる。これに関して、情報の流れの方向と移動方向の間の関係は相対的なものである。情報の流れの方向と移動方向は、平行である必要はなく、むしろ角度を持った関係とすることができる。移動方向および情報の流れの方向がともに平行かつ同一の方向を向くベクトル成分を含む限り、移動方向と情報の流れの方向は同一の方向であると見なされるものとする。同じことが、移動方向と情報の流れの方向が逆方向と見なされる場合にも当てはまる。その場合のベクトル成分は平行であるが逆方向を向く。
【００３５】
図１２を参照し、次に、ストラテジＩＶの現在のところ好ましい実施態様について説明する。ステップ１００においては、複数のモバイル・ノードの第１のノードが所定のパケットを受信する。ステップ１０２においては受信ノードが、それ自体が情報の流れの方向に移動しているか否かを決定する。異なるときにはそのパケットが破棄される。同じときには、ステップ１０４においてそのパケットを、適切なパケット送信ルーチンを使用してレンジ内の近隣のパケットに送信する。次にステップ１０６において、現在位置がソースおよびディスティネーションの位置によって定義されるあらかじめ決定済みの範囲外であるか否かについてパケットがテストされる。範囲外の場合にはそのパケットが破棄される。該当しなければ、以前にそれが送信されているか否かを決定するべくパケットがテストされる。これは、ステップ１０８においてシーケンス番号を調べて以前の送信済みシーケンス番号と比較することによって行われる。そのパケットが以前に送信済みのものであれば破棄される。該当しなければ、ステップ１１０において、タイムスタンプが満了となっているか否かを決定するべくパケットがテストされる。前述したとおり、タイムスタンプは、送信の時刻においてパケットにタイムスタンプすること、あるいはソース位置から送信された時刻後のあらかじめ決定された期間として計算された満了時間を用いてパケットにタイムスタンプすることのいずれかによって具体化することができる。タイムスタンプが満了となっていれば、そのパケットが破棄される。該当しなければ、そのパケットは近隣ノードに送信される。
【００３６】
このフラッディングがネットワーク・レイヤ内において使用されることから、８０２．１１実装における送信要求（ＲＴＳ）パケットおよび送信可能（ＣＴＳ）パケットの使用をあらかじめ排除する方法でＭＡＣレイヤ・ブロードキャストが使用される必要がある。これは、隠れ端末問題に起因するパケットの衝突の可能性をかなり増加させる。しかしながら、適切な送信レンジの選択は、この隠れ端末問題を有意に緩和する。
【００３７】
以上の本発明の説明は、本質的に例示に過ぎず、したがって本発明の要旨から逸脱しない変形は本発明の範囲内に含まれることが意図されている。その種の変形は、本発明の精神ならびに範囲から逸脱していると考えられるべきものではない。
【図面の簡単な説明】
【００３８】
【図１】マルチ‐ホップ・ネットワークを例示したネットワーク通信ダイアグラムである。
【図２】モバイル・インフォステーション・ネットワークを例示したネットワーク通信ダイアグラムである。
【図３】２つの順方向移動ノードに関する接続確立のための第１のストラテジを例示した説明図である。
【図４】２つの順方向移動ノードに関するノード遭遇ストラテジを例示した説明図である。
【図５】図３および４のストラテジのパケット軌跡を例示したグラフである。
【図６】２つの逆方向移動ノードに関するノード遭遇ストラテジを例示した通信ダイアグラムである。
【図７】図６のストラテジのパケット軌跡を例示したグラフである。
【図８】順方向および逆方向ノードに関する接続確立ストラテジを例示した通信ダイアグラムである。
【図９】順方向および逆方向ノードに関するノード遭遇ストラテジを例示した通信ダイアグラムである。
【図１０】図８および９に例示したストラテジのパケット軌跡を例示したグラフである。
【図１１】通信パケットおよびノードについて現在のところ好ましいデータ構造をそれぞれ例示したデータ構造の説明図である。
【図１２】コントロールされたフラッディングを基礎とする現在のところ好ましいストラテジの詳細を例示したフローチャートである。
【符号の説明】
【００３９】
２  ノード
１０  モバイル・アドホック・ネットワーク
１２  モバイル・インフォステーション・ネットワーク
５０  データ構造
【図１】
2006229968.tif 000003
【図２】
2006229968.tif 000004
【図３】
2006229968.tif 000005
【図４】
2006229968.tif 000006
【図５】
2006229968.tif 000007
【図６】
2006229968.tif 000008
【図７】
2006229968.tif 000009
【図８】
2006229968.tif 000010
【図９】
2006229968.tif 000011
【図１０】
2006229968.tif 000012
【図１１】
2006229968.tif 000013
【図１２】
2006229968.tif 000014
【外国語明細書】
2006229968.tif 000015
2006229968.tif 000016
2006229968.tif 000017
2006229968.tif 000018
2006229968.tif 000019
2006229968.tif 000020
2006229968.tif 000021
2006229968.tif 000022
2006229968.tif 000023
2006229968.tif 000024
2006229968.tif 000025
2006229968.tif 000026
2006229968.tif 000027
2006229968.tif 000028
2006229968.tif 000029
2006229968.tif 000030
2006229968.tif 000031
2006229968.tif 000032
2006229968.tif 000033
2006229968.tif 000034
2006229968.tif 000035
2006229968.tif 000036
2006229968.tif 000037
2006229968.tif 000038
【図１】
2006229968.tif 000039
【図２】
2006229968.tif 000040
【図３】
2006229968.tif 000041
【図４】
2006229968.tif 000042
【図５】
2006229968.tif 000043
【図６】
2006229968.tif 000044
【図７】
2006229968.tif 000045
【図８】
2006229968.tif 000046
【図９】
2006229968.tif 000047
【図１０】
2006229968.tif 000048
【図１１】
2006229968.tif 000049
【図１２】
2006229968.tif 000050