(57)【要約】  完了速度、データ速度、ＭＡＣオーバーヘッド及び輻輳を含む一つ以上のパラメータに基づいて、多重ホッピング・ネットワーク（１００）における最良のスループットを提供する経路を選択することができる、ルーティング・メトリックを計算するためのシステム及び方法。システム及び方法は、高いスループットを有する多重ホッピング・ネットワーク（１００）における経路を選択することが可能であり、一つ以上のノード（１０２，１０６，１０７）においてルーティング・メトリックを計算する。ルーティング・メトリックは一つ以上のノード（１０２，１０６，１０７）がネットワーク（１００）における経路を選択することを可能にする。ルーティング・メトリックは、未加工のデータ速度、完了速度及びメディア・アクセス制御のオーバーヘッド及び輻輳のようなネットワーク情報を含むことができる。
2008519533.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークにおいてデータをルーティングするための方法であって、
パケットの送信時刻、失敗したパケットの再送信に関する追加時刻、及びノードにおいて受信されたパケットの到着時刻と受信されたパケットに応答するノードにより最初にパケットの送信が試みられた時刻との間の経過時間をからなるグループから選択される一つ以上の情報を含む、前記パケットの送信に関する情報を、無線ネットワークにおける少なくとも一つの前記ノードにおいて決定すること、
前記決定された情報に基づき、前記ノードによって少なくとも一連のパケットの送信で利用されるためにルーティング・メトリックを計算すること、
を備える方法。
【請求項２】
前記ノードを、前記ルーティング・メトリックに基づいて連続したパケットの送信用の帯域幅の量を割り当てるように動作させること
を備える、請求項１に記載の方法。
【請求項３】
前記ノードを、送信用に割り当てられた前記帯域の量に基づいたスループットのレベルを達成するように複数の前記連続したパケットを送信するように動作させること
を備える、請求項２に記載の方法。
【請求項４】
前記ノードを、前記ルーティング・メトリックに基づいて連続したパケットを送信する先の他のノードを決定するように動作させること
を更に備える、請求項１に記載の方法。
【請求項５】
前記ネットワークにおける複数のノードに対して前記決定することを実行すること、
前記複数のノードの各々において決定された対応する情報に基づいて、前記ルーティング・メトリックを計算すること
を更に備える、請求項１に記載の方法。
【請求項６】
前記情報は、パケットの送信時刻、失敗したパケットの再送信に関する追加時刻、及びノードにおいて受信されたパケットの到着時刻と受信されたパケットに応答するノードにより最初にパケットの送信が試みられた時刻との間の経過時間に関する情報を含む、請求項１に記載の方法。
【請求項７】
前記ノードを前記ルーティング・メトリックに関する情報を提供するように動作させること
を更に備える、請求項１に記載の方法。
【請求項８】
無線通信ネットワークで利用するように構成されるノードであって、
パケットを送信及び受信するように構成される送受信器と、
パケットの送信時刻、失敗したパケットの再送信に関する追加時刻、及び送受信器において受信されたパケットの到着時刻と受信されたパケットに応答する送受信器により最初にパケットの送信が試みられた時刻との間の経過時間からなるグループから選択される一つ以上の情報を含む、パケットの送信に関する情報を決定するように構成され、且つ前記決定された情報に基づき、少なくとも一つの連続したパケットの送信に利用されるためのルーティング・メトリックを計算するように更に構成される、コントローラと
を備えるノード。
【請求項９】
前記コントローラは、前記ルーティング・メトリックに基づいて、連続したパケットの送信用の帯域幅の量を割り当てるように更に構成される、請求項８に記載のノード。
【請求項１０】
前記コントローラは、前記送受信器を制御して複数の前記連続したパケットを送信することにより、送信用に割り当てられた帯域幅の量に基づいてスループットのレベルを達成するように更に構成される、請求項９に記載のノード。
【請求項１１】
前記コントローラは、前記ルーティング・メトリックに基づいて連続したパケットを送信するための送受信器を制御する他のノードを決定するように更に構成される、請求項８に記載のノード。
【請求項１２】
前記コントローラは、前記決定された情報と前記ネットワークにおいて複数の他のノードから受信される前記ルーティング・メトリックに関する情報とに基づいてルーティング・メトリックを計算するように更に構成される、請求項８に記載のノード。
【請求項１３】
前記情報は、前記パケットの送信時刻、失敗したパケットの再送信に関する追加時刻、及び送受信器において受信されたパケットの到着時刻と受信されたパケットに応答する前記送受信器により最初にパケットの送信が試みられた時刻との間の経過時間に関する情報を含む、請求項８に記載のノード。
【請求項１４】
前記コントローラは、前記ノードを制御して前記ルーティング・メトリックに関する情報を提供するように構成される、請求項８に記載のノード。
【請求項１５】
前記コントローラは、前記送受信器を制御して前記ネットワークにおける少なくとも一つ以上の他のノードにより受信用の前記ルーティング・メトリックに関する情報を送信するように更に構成される、請求項８に記載のノード。
【請求項１６】
前記無線通信ネットワークにおいて通信するための方法であって、
前記無線通信ネットワークに構成されるように複数のノードを動作して、パケットの送信時刻、失敗したパケットの再送信に関する追加時刻、及び受信されたパケットの到着時刻と受信されたパケットへの応答により最初にパケットの送信が試みられた時刻との間の経過時間からなるグループから選択される一つ以上の情報を含む、対応する情報を各々決定すること、
他のノードによる受信用の各々の情報を送信するために、前記複数のノードを動作させること、
対応する情報と他のノードから受信される情報とに基づいて、各々のルーティング・メトリックを計算するために前記複数のノードの各々を動作させること
を備える方法。
【請求項１７】
各々計算されたルーティング・メトリックに基づいて連続したパケットの送信用帯域幅の各々の量を割り当てるために前記ノードの各々を動作させること
を更に備える、請求項１６に記載の方法。
【請求項１８】
各前記ノードを動作させて各々の複数の連続したパケットを送信し、送信用に割り当てられた各々の帯域幅の量に基づくスループットの各レベルを達成すること
を更に備える、請求項１７に記載の方法。
【請求項１９】
各々の他のノードに連続したパケットを各々のルーティング・メトリックに基づいて送信するように決定するように、前記ノードの各々を動作させること
を更に備える、請求項１６に記載の方法。
【請求項２０】
前記各々の情報は、パケットの送信時刻、失敗したパケットの再送信に関する追加時刻、及び前記ノードにおいて受信されたパケットの到着時刻と前記ノードによる受信されたパケットへの応答する最初にパケットの送信が試みられた時刻との間の経過時間に関する情報を含む、請求項１６に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は無線通信ネットワークに関連し、特に多重ホッピング・ネットワークにおける最良のスループットを提供する経路を選択するためにルーティング・メトリックを計算するためのシステム及び方法に関連する。
【０００２】
本出願は、２００４年１１月５日に出願された米国仮出願第６０／６２５，１１３号明細書の利益を主張し、その全文は参照によって本明細書に組み込まれる。
【背景技術】
【０００３】
近年、アドホック・ネットワークとして知られる携帯通信ネットワークのタイプが発展している。このタイプのネットワークにおいて、各携帯ノードは、他の携帯ノードのベース・ステーション又はルータとして動作することが可能あり、従って固定基幹設備であるベース・ステーションの必要性が無くなる。当業者に認識されるように、ネットワーク・ノードはデータ・パケット通信を、時間分割多重接続（ＴＤＭＡ）方式、コード分割多重接続（ＣＤＭＡ）方式、又は周波数分割多重接続（ＦＤＭＡ）方式のような多重化方式で送受信する。
【０００４】
より洗練されたアドホック・ネットワークは、従来のアドホック・ネットワークと同様に携帯ノード同士が互いに通信可能であることに加えて、携帯ノードが固定ネットワークに接続することが更に可能であり、従って、公衆交換電話網（ＰＳＴＮ）のようなネットワークの他のノード及びインターネットのような他のネットワークの他の携帯ノードと通信することが可能となるようにも発展してきた。アドホック・ネットワークのこれら進化したタイプの詳細は、「Ａｄ  Ｈｏｃ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ａｃｃｅｓｓ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅｄ  ｔｏ  ｔｈｅ  ＰＳＴＮ  ａｎｄ  Ｃｅｌｌｕｌａｒ  Ｎｅｔｗｏｒｋｓ」と題された、２００１年６月１９日に出願された米国特許出願第０９／８９７，７９０号明細書、「Ｔｉｍｅ  Ｄｉｖｉｓｉｏｎ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  ａｎ  Ａｄ−Ｈｏｃ，  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｒａｄｉｏ  Ｎｅｔｗｏｒｋ  Ｈａｖｉｎｇ  Ｃｏｏｒｄｉｎａｔｉｎｇ  Ｃｈａｎｎｅｌ  Ａｃｃｅｓｓ  ｔｏ  Ｓｈａｒｅｄ  Ｐａｒａｌｌｅｌ  Ｄａｔａ  Ｃｈａｎｎｅｌｓ  ｗｉｔｈ  Ｓｅｐａｒａｔｅ  Ｒｅｓｓｅｒｖａｔｉｏｎ  Ｃｈａｎｎｅｌ」と題された、２００１年３月２２日に出願された米国特許出願第０９／８１５，１５７号明細書で、現在米国特許第６，８０７，１６５号が付与された明細書、及び「Ｐｒｉｏｒｉｔｉｚｅｄ−Ｒｏｕｔｉｎｇ  ｆｏｒ  ａｎ  Ａｄ−Ｈｏｃ，Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ，  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ａｃｃｅｓｓ  ｓｙｓｔｅｍｓ」と題された２００１年３月２２日に出願された米国特許出願第０９／８１５，１６４号明細書で、現在米国特許第６，８７３，８３９号が付与された明細書に記載されており、各々の全体が参照によって本明細書に組み込まれる。
【０００５】
アドホック・ネットワークは、携帯クライアントから宛て先ノードへ、又は一つ以上の無線ネットワーク・ノードを経由して他のネットワーク・ノードへの経路を集合的に定義する、複数のノードを典型的に備える。一般に、「チャンネル」は各ノードからネットワーク接続ノードへの経路を定義する他のノードに確立され、次にインターネットのような外部ネットワークへの接続を提供する。宛先が、ノードに関連付けられたユーザであるとき、チャンネルはあるノードから同じネットワークの他のノードへ確立される。
【０００６】
上で説明されたような無線「アドホック」ネットワークの性質から明らかなように、周波数とチャンネルを注意深く割り当てることが、ネットワークの同じ周波数又はチャンネルを利用するノード間のインターフェイスを最小化し、ネットワークの性能及び有効性を最大化するために重要である。この点において、周波数チャンネル割り当ての伝統的な方法は、例えば少数のチャンネルのみが利用可能である時に、困難である。更に、ノード数が利用可能なチャンネル数を越えるとき、周波数チャンネル割り当てが困難になる。
【０００７】
無線「アドホック」ネットワークに関して、周波数チャンネル割り当てを扱う複数の技術が存在する。例えば、米国特許出願２００４／０１５７６１３号明細書は、同一チャンネルを低減し、無線周波数チャンネルの自己選択を介してチャンネル・インターフェイスを調整する方法を開示している。更に、「Ａ  Ｈｉｇｈ−Ｔｈｒｏｕｇｈｐｕｔ  Ｐａｔｈ  Ｍｅｔｒｉｃ  ｆｏｒ  Ｍｕｌｔｉｐｌｅ  Ｗｉｒｅｌｅｓｓ  Ｒｏｕｔｉｎｇ」と題された、２００３年にＭ．Ｉ．Ｔ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ａｒｔｉｆｉｃｉａｌ  Ｉｎｔｅｌｌｉｇｅｎｃｅ  Ｌａｂｏｒａｔｏｒｙからデコート（ＤｅＣｏｕｔｏ）等による出版は、パケット完了率に反比例するが、可変データ速度又は信号化のオーバーヘッドを考慮しない関係を識別する、期待される送信数（ＥＴＸ）メトリックを開示している。
【発明の開示】
【０００８】
以下に詳細に説明されるように、本明細書に記載される本発明の実施形態は、完了速度（ｃｏｍｐｌｅｔｉｏｎ  ｒａｔｅｓ）、データ速度、メディア・アクセス制御（ＭＡＣ）オーバーヘッド及び輻輳を含む一つ以上のパラメータに基づいて、多重ホップ・ネットワークにおける最良のスループットを提供する経路を選択することができるルーティング・メトリックを計算するためのシステム及び方法を提供する。システム及び方法は高スループットを有する多重ホッピング・ネットワークにおいて経路を選択することができ、一つ以上のノードにおいてルーティング・メトリックを計算することができ、ルーティング・メトリックは、一つ以上のノードにネットワークにおける経路を選択させることができる。ルーティング・メトリックは、未加工のデータ速度、完了速度、及びメディア・アクセス制御（ＭＡＣ）オーバーヘッド及び輻輳のようなネットワーク情報を含む。
【発明を実施するための最良の形態】
【０００９】
同じ参照番号が全図を通して同じ又は機能的に類似する要素を表し、以下の詳細な記載と協調して明細書の一部を形成する添付された図面は、本発明に従う様々な実施例を更に図示し、且つ様々な原理及び優位性全てを説明するために提供される。
【００１０】
当業者は、図面の要素が単純性及び明白性を有するように図示されており、縮尺どおりに描かれる必要が無いこと認識するであろう。例えば、図面中のいくつかの要素の大きさは他の要素に比べて誇張されており、本発明の実施形態の理解を促進することに役立つ。
【００１１】
本発明の実施形態に従う詳細な実施形態を記載する前に、実施形態には、多重ホッピング・ネットワークの最良のスループットを提供する経路を選択することができるルーティング・メトリックを計算することに関する方法の段階と装置の部品との組み合わせが主に備わっていることに注意するべきである。従って、装置の部品及び方法の段階は、図面において従来の記号によって適切に表されており、本発明の実施形態を理解するために関連のある特定の詳細のみを示しており、本明細書の記載により利益を有する当業者にはすでに明らかであろう詳細により、本開示を不明確にしないようにしている。
【００１２】
本明細書において、第一及び第二、上及び下等の関連用語はあるエンティティまたは動作を他のエンティティ又は動作と区別するために単独で利用され、そのようなエンティティ又は動作間のいかなる関係又は順序を必要とする又は実施する必要は無い。用語、「備える」、「備えている」又はこれらの任意の他の活用形は非排他的包含を含むことが意図され、要素のリストを備えるプロセス、方法、物件又は装置はこれら要素のみを含むだけでなく、そのようなプロセス、方法、物件又は装置に明示的にリストされていない又は固有の他の要素を含んでよい。「〜を備える」ことにより処理される要素は、更なる拘束条件無しに、要素を備えるプロセス、方法、物件又は装置と更に同一の要素の存在を排除されない。
【００１３】
本明細書に記載される発明の実施形態が、一つ以上の従来のプロセッサと唯一記憶されたプログラム命令とを備えて、特定の非プロセッサ回路と協調して本明細書で記載されるように、多重ホップ・ネットワークにおける最良のスループットを提供する経路を選択することができるルーティング・メトリックを計算するためのシステム及び方法の幾つか、ほとんど又は全ての機能を具体化することは明らかである。非プロセッサ回路は、無線受信器、無線送信器、信号ドライバ、クロック回路、電源回路及びユーザの入力デバイスを含むが、これらには制限されない。そのようなものとして、これらの機能は多重ホップ・ネットワークにおける最良のスループットを提供する経路を選択することができるルーティング・メトリックを計算するための方法の段階として解釈される。これとは別に、幾つか又は全ての機能は、記憶されたプログラム命令を有しない状態マシンによって、又は一つ以上の特定用途向け集積回路（ＡＳＩＣ）で実施され、各機能又はある機能の組み合わせはカスタム論理として実施される。もちろん、二つのアプローチの組み合わせも利用され得る。従って、これら機能の方法及び手段が本明細書で記載される。更に、例えば、利用可能な時間、現在の技術及び経済的な判断によって動機付けられる重要な効果及び数多くの設計の選択が可能であるにもかかわらず、本明細書に開示される概念及び原理によって導かれると、当業者にとっては、最低限の実験でそのようなソフトウェア命令及びプログラムとＩＣとをすぐに生成することが可能であることが予測される。
【００１４】
図１は、本発明の実施形態を採用したアドホック・パケット切り替え無線通信ネットワーク１００の例を示すブロック図である。特に、ネットワーク１００は、必ずしも必要ではないが複数の携帯無線ユーザ端末１０２−１〜１０２−ｎ（一般にノード１０２又は携帯ノード１０２と呼ぶ）を含むことができ、複数のアクセス・ポイント１０６−１，１０６−２，…１０６−ｎ（一般にノード１０６、アクセス・ポイント１０６又は知的アクセス・ポイント（ＩＡＰ）１０６と呼ぶ）を有する固定ネットワーク１０４を含み、ノード１０２に固定ネットワーク１０４への接続を提供する。固定ネットワーク１０４は、例えばコアのローカル・アクセス・ネットワーク（ＬＡＮ）及びネットワーク・ノードに、例えば他のアドホック・ネットワーク、公衆交換電話網（ＰＴＳＮ）及びインターネットのような他のネットワークへの接続を提供する複数のサーバ及びゲートウェイ・ルータを含む。ネットワーク１００は更に複数の固定ルータ１０７−１〜１０７−ｎ（一般にノード１０７無線ルータ（ＷＲ）１０７又は固定ルータ１０７と呼ぶ）を含み、他のノード１０２，１０６又は１０７の間でデータ・パケットをルーティングする。この説明のために、上で説明されたノードは、「ノード１０２，１０６及び１０７」又は単にノードと集合的に呼ばれることに留意されたい。
【００１５】
当業者は気づいているように、上で参照された米国特許出願第０９／８９７，７９０号明細書と米国特許第６，８０７，１６５号明細書及び米国特許第６，８７３，８３９号明細書とに記載されているように、ノード１０２，１０６及び１０７は、互いに直接通信するか又は、ノード間で送信されるパケットのルータとして動作する一つ以上の他のノード１０２，１０６又は１０７を介して通信できる。
【００１６】
図２に示されるように、各ノード１０２，１０６及び１０７は、送受信器又はモデム１０８を含み、送受信器又はモデム１０８はアンテナ１００に接続されて、コントローラ１１２の制御の下でパケット化された信号のような信号をノード１０２，１０６及び１０７に送信及びノード１０２，１０６及び１０７から受信する。パケット化されたデータ信号は、例えば音声、データ又はマルチメディア情報及びノード更新情報を含むパケット化された制御信号を含む。
【００１７】
各ノード１０２，１０６及び１０７は自分自身とネットワーク１００の他のノードとを関連付ける経路情報を記憶することができるランダム・アクセス・メモリ（ＲＡＭ）のようなメモリ１１４を更に含む。図２に更に示されるように、特に携帯ノード１０２のような特定のノードは、ノートブック型コンピュータ端末、携帯電話ユニット、携帯データ・ユニット又は任意の他の適切なデバイスのような任意の数のデバイスから成るホスト１１６を含む。各ノード１０２，１０６及び１０７は、インターネット・プロトコル（ＩＰ）及びアドレス解決プロトコル（ＡＲＰ）を実行するための適切なハードウェア及びソフトウェアも含み、これらの目的は当業者にはすぐに明らかになるであろう。送信制御プロトコル（ＴＣＰ）及びユーザ・データグラム・プロトコル（ＵＤＰ）を実行するための適切なハードウェア及びソフトウェアも含む。
【００１８】
上で説明されたように、ネットワーク１００のノード１０２，１０６及び１０７がネットワークの輻輳を考慮に入れて多重ホップ・ネットワークにおける経路を選択し、最適なスループットを実現する性能を有することが望ましい。以下に記載されるように、本発明の実施形態により一つ以上のノードに、完了速度、データ速度、ＭＡＣオーバーヘッド及び輻輳を含む一つ以上のパラメータに基づいて、最良のスループットを提供する経路を選択することができるルーティング・メトリックを計算させることが可能となる。ルーティング・メトリックはノード１０２，０１６及び１０７におけるコントローラ１１２とコントローラ１１２に関連付けられるハードウェア及びソフトウェアとによって計算されるということに留意されたい。
【００１９】
＜輻輳／コンテンション＞
単チャンネルのメディア・アクセス制御（ＭＡＣ）に対して、コンテンション時間がノード１０２，１０６及び１０７によりネットワーク・アロケーション・ベクトル（ＮＡＶ）又はクリア・チャンネル・アセスメント（ＣＣＡ）のようなカウンタ又はタイムスタンプのいずれかを介して測定される。多重チャンネルＭＡＣに対して、ノード１０２，１０６又は１０７は、予約チャンネルを待ち受けている間に監視することができる測定に基づく。輻輳／コンテンション測定の前提は、ノード１０２，１０６及び１０７が所与の時刻に送信できるチャンネルの割合を評価できることである。例えば、帯域幅のどの部位もノード１０２，１０６又は１０７或いは他のノード１０２，１０６又によって利用されない場合、帯域幅の利用度は１００％（百パーセント）である。ノード１０２，１０６又は１０７の他のノードが帯域幅を利用している場合、利用度は５０％（五十パーセント）と１００％（百パーセント）近傍の間の任意の値である。この点において、利用度は１／Ｎより低いことは無く、Ｎはチャンネルにアクセスするノード１０２，１０６及び１０７のノード数である。このことにより、帯域幅が現在すべて利用されている場合、後の時刻における複数のユーザによって更に共有されることになる。帯域幅はノード１０２，１０６又は１０７（前の例にあるが）の間で等しく分配される必要は無い。例えば、特定のノード１０２，１０６または１０７がより高い優先度状態が割り当てられ得、あるトラフィック・フローがより高い帯域の需要に割り当てられる。
【００２０】
全データ速度が等しいこと、全完了速度が１００％（百パーセント）であること、及び信号化オーバーヘッドを無視することを仮定すると、図３はルーティング・メトリックの一部として輻輳を利用する経路決定を示す。示されるソース、宛先及びルータは、ネットワーク１００の任意のノード、すなわち、例えば図１に示される携帯ノード１０２、固定ルータ１０７又はアクセス・ポイント１０７に対応することに留意されたい。この説明のために、ソース及び宛先ノードは各々１０２−１及び１０２−２であり、ルータは１０７−１，１０７−２及び１０７−３であると仮定する。この例において、参照番号３００，３０４及び３０８は利用可能な帯域を含み、参照番号３０２，３０６及び３１０は利用不可能な帯域を含む。指定されているように、ノード１０７−１は輻輳しており、２５％（二十五パーセント）のみの帯域幅が利用可能であり、一方でノード１０７−２及び１−７−３はこれほど輻輳しておらず、６０％（六十パーセント）の利用可能なバンド幅を各々有する。
【００２１】
ルーティングの決定に利用するためのルーティング・メトリックは、「情報の単位を送信するために必要な時間の量」として定義される。ルーティング・メトリックは有効スループットに反比例することが当業者により理解されるであろう。以下の例において、時間の単位は秒であり、情報の基準単位はギガビットである。情報の他の基準単位及び他の時間の単位が本発明に従って利用されてもよいことに気づかれるであろう。コンテンションの無い（すなわち利用度が百パーセント（１００％）である）リンクが、毎秒十（１０）メガビットのスループットを有する場合、一ギガビットの情報は送信するのに百（１００）秒かかる。百（１００）が従って例示したシステムの特定の基準リンクに対するルーティング・メトリックである。チャンネルが六十パーセント（６０％）の利用度である場合、最大のスループットは六（６）Ｍｂｐｓであり、二十五パーセント（２５％）の利用度のチャンネルは二点五（２．５）Ｍｂｐｓのスループットを発生させる。六（６）Ｍｂｐｓにおいて、百六十六（１６６）秒が一ギガバイトの情報を送信するためにかかる。二点五（２．５）Ｍｂｐｓにおいて、四百（４００）秒が一ギガビットの情報を送信するためにかかる。図３に示される例を参照して、ノード１０２−１，１０７−１及び１０２−２から成る経路は、（両ソース店ノード１２０−１及びルータ１０７−１は同じ媒体を共有し、一ギガビットの情報を送信するために八百（８００）秒かかるため、）八百（８００）の累積したルーティング・メトリックを有する。ノード１０２−１，１０７−２，０７−３及び１０２−２から成る経路は五百（５００）の通信ルーティング・メトリックを有する。
【００２２】
＜パイプ化＞
図３に示される前の例において、ノード１０２−１と１０７−２との間の第一ホップにおける通信とノード１０７−２及びノード１０２−２との間の第三ホップとが同時に発生するかどうかまだ決定されていない。同時に発生するイベントにおいて、ルーティング・メトリックは、図４に示されるように通信用のより多くの帯域を割り当てることにより自動的にこの事実を考慮に入れる。ノード１０２−１，１０７−１及び１０７−２が集合的に利用可能な帯域幅の五十パーセント（５０％）が、４００，４０４及び４０８により指定されるように割り当てられ、４０２，４０６及び４１０によって指定されるように、五十パーセント（５０％）の帯域幅が利用不可能なままである。同時に通信することができない場合、ルーティング・メトリックがこのことを反映して、送信されるデータの量、従ってスループットが図５に示されるように低減される。すなわち、ノード１０２−１及び１０７−２各々は、５０２及び５１０で指定されるように、三十四パーセント（３４％）の利用可能帯域幅が割り当てられ、六十六パーセント（６６％）の帯域幅は５０２及び５１０によって指定されるように利用不可能なままであり、且つノード１０７−１は、５０４により指定される五十パーセント（５０％）の帯域幅が割り当てられ、５０６により指定される五十パーセント（５０％）の帯域幅が利用不可能なままである。
【００２３】
＜多重送受信器＞
図６に示されているように、各ルータ１０７−１，１０７−２及び１０７−３は、図２に示されるように二つの送受信器１０８を備える二重逆送々受信器６００を含み、例えば、各ルータ（例えば図６に示されるようにルータ１０７−１，１０７−２及び１０７−３）が同時に送信器及び受信器として利用されることを可能にし、従って通信リンクの帯域幅を二重化する。しかし、このことは、各ルータが任意の他のルータと接続せず、且つ図６の６０２及び６０４で指定される百パーセント（１００％）の容量として更に示されるように、他のトラフィックのフローが経路に沿って発生しない場合に、起こる。しかしながら、ルーティング・メトリックは両方の状況を好適に近づけるために利用される。実際に、トポロジーが二重送受信器ルータ１０７−１，１０７−２，１０７−３の直線状の列である場合、各ルータにおける最小の接続のリンクは前のホップを利用しないものである。従って、従って経路はある送受信器及び次に他の送受信器を二者択一的に利用する。図７に示されるように、他のルータ又はトラフィック源（例えば他のルータ１０７−４）との接続が存在する場合、システムは、各送受信機が等しく利用されるようにする。すなわち、（最終的なルーティング・メトリックを決定する）利用される帯域幅の大きさが、各送受信器に対して同じまたは実質的に同じである。図７の例において、各ルータ１０７−１及び１０７−４の送受信器は、７００及び７０２により指定される五十パーセント（５０％）の容量を利用し、ルータ１０７−２の各送受信器は７０４及び７０６により指定される五十パーセント（５０％）の容量を利用する。
【００２４】
＜ＴＤＭＡ＞
ＴＤＭＡのＭＡＣにおいて、特定のリンクを利用可能にする帯域幅の割合は、割り当てられた時間スロットの大きさ対リンクで送信されるフレームの全体の大きさの比に基づいて決定される。
【００２５】
＜情報の単位の送信時間＞
前節で記載された利用可能な時間中に、ノードは制限された量の情報を送信することしかできない。ルーティング・メトリックは「情報の単位を送信するために必要な時間量」として定義され、この時間は従ってデータ速度に基づく。ＭＡＣのオーバーヘッド及びリトライ数のような他のパラメータが入ってきてもよい。実際に、他のパラメータが図８のグラフに示されるように情報の単位を送信するために必要な実際の時間を増加する。図８は、要求対送信（ＲＴＳ）及びクリア対送信（ＣＴＳ）メッセージ、ヘッダ、データ・メッセージ（ＤＡＴＡ）、及び確認応答（ＡＣＫ）及び非確認応答（ＮＡＣＫ）メッセージによって占められる時間量の例を図示している。
【００２６】
この例において、チャンネル利用度は百パーセント（１００％）であり、このチャンネルを利用しようとする他のノード１０２，１０６及び１０７が存在しないことを意味する。未加工のデータ速度、ＭＡＣオーバーヘッド及び完了速度を知ることにより、実際のスループットを決定することが可能になり、従って特定のリンクのルーティング・メトリックを決定することが可能になる。データ速度は、「Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ａｄａｐｔｉｖｅ  Ｒａｔｅ  Ｓｅｌｅｃｔｉｏｉｎ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  Ｎｅｔｗｏｒｋ」と題された、２００５年６月２４日に出願された米国特許出願第１１／１６６，５７８号明細書に記載されているように計算される。ＭＡＣオーバーヘッドは、「Ｓｏｆｔｗａｒｅ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ａｎｄ  Ｈａｒｄｗａｒｅ  Ａｂｓｔｒａｃｔｉｏｎ  Ｌａｙｅｒ  ｆｏｒ  Ｍｕｌｔｉ−Ｒａｄｉｏ  Ｒｏｕｔｉｎｇ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｐｒｏｖｉｄｉｎｇ  ｔｈｅ  Ｓａｍｅ」と題された、２００５年８月１０日に出願された米国特許出願第１１／２００，６５８号明細書に記載されるように提供される。完了速度は、「Ａ  Ｍｅｔｈｏｄ  ｔｏ  Ｐｒｏｖｉｄｅ  ａ  Ｍｅａｓｕｒｅ  ｏｆ  Ｌｉｎｋ  Ｒｅｌｉａｂｉｌｉｔｙ  ｔｏ  ａ  Ｒｏｕｔｉｎｇ  Ｐｒｏｔｏｃｏｌ  ｉｎ  ａｎ  Ａｄ  Ｈｏｃ  Ｗｉｒｅｌｅｓｓ  Ｎｅｔｗｏｒｋ」と題された、２００４年６月７日に出願された米国特許出願第１０／８６３，０６９号明細書記載されているように計算される。これら三つの特許出願の各々の全文は参照として本明細書に組み込まれる。
【００２７】
＜ルーティング・メトリックの例＞
以下の節では、リンク毎の有効スループットに基づくルーティング・メトリックの例を表す。特に、ホップ毎のパケット遅延は、以下の式に従って近似される。
Td=tw+Σi∈N(1-pcr(L,R))i-1(i ts(L,R)+(i-1)te)
=tw+(ts(L,R)+(1-pcr(L,R))te)/pcr(L,R)
L  =パケット長
R  =データ速度
pcr=パケット完了速度
ts  =（オーバーヘッド、伝播時間、処理時間等を含む）パケットの送信時間
te  =（チャンネル接続時間を含む）失敗したパケットの再送信に必要な余計な時間
tw  =ノードのキューにパケットが到達した時刻とこのパケットが最初に送信された時刻との間の経過時間
例えば、コンテンション・ベースのＭＡＣプロトコルに対して、チャンネル接続時間は近隣の輻輳とチャンネルの混雑度とに依存する。コンテンションの無いシステム（例えば、ＴＤＭＡシステム）に対して、チャンネル接続時間はノード／リンクに割り当てられたスロットに依存する。teは、送信の失敗と近隣の輻輳とによる、平均バックオフ時間に依存する（パケットの送信に失敗した場合、送信されるべき最初のパケットを次回同じチャンネルで送信可能であることを仮定している）。twは、ノードの輻輳レベル（例えば、パケットがノードにおいてすでにキューにある）と近隣の輻輳とに依存する。
【００２８】
有効スループットは、次のように近似される。
G=L/Td=L pcr(L,R)/(ts(L,R)+(1-pcr(L,R))te+pcr(L,R)tw)
Ｇを計算するために利用される値は、ウィンドの大きさが安定性を提供するために最適化される移動平均として測定される。幾つかの値は米国電気電子技術者協会（ＩＥＥＥ）８０２．１１標準で定義される測定動作を利用して評価される。例えば、ＩＥＥＥ８０２．１１標準のネットワークにおいて、teは、ＩＥＥＥ８０２．１１ｈ標準及びＩＩＩＩ８０２．１１ｋ標準に各々記載されているクリア・チャンネル・アセスメント（ＣＣＡ）及びネットワーク・アロケーション・ベクトル（ＮＡＶ）混雑時により推定される。
【００２９】
各ホップに対するルーティング・メトリックは、
M=α/G
であり、αは規格化因子である。変数αは１Ｇｂｐｓのような基準となる高速リンクに対して「１」のルーティング・メトリックを得るように選択される。これにより、ネットワークにおける全ルーティング・メトリックが拘束条件付（例えば１６ビット）の解像度で整数値を使って表現される。
【００３０】
＜データ速度の依存性及び異種の送受信器＞
情報の単位を送信するためにかかる時間に基づくルーティング・メトリックの能力により、ルーティング・プロトコルが、ＩＥＥＥ８０２．１１ａ標準及びＩＥＥＥ８０２．１１ｇ標準のような、データ速度に大きな広がりがある送受信器、或いは（イーサーネット対ブルートゥースのような）異なるデータ速度を実現する複数の物理層を有する送受信器で動作することが可能になる。唯一の制限は、（例えば毎秒一（１）ギガビットに設定される）基準ルーティング・メトリックと、メトリックの解像度（２8が三点九（３．９）Ｍｂｓのリンクに対応し、１／２16が毎秒十五（１５）キロビット（Ｋｂｐｓ）に対応する）により設定される。毎秒一（１）ギガビットで且つ十六（１６）ビットの解像度であるルーティング・メトリックを利用して、ダイアルアップ・モデム及びギガビット・イーサーネットほどの異なったリンクの多重ホップ・スループットを比較することができる。
【００３１】
＜ネットワーク・フラッディングを必要とするプロトコルの経路要求満了＞
ルーティング・プロトコルが、（アドホック・オンデマンド距離ベクトル（ＡＯＤＶ）における経路要求のように）ネットワークにフラッディングすることを要求する場合、典型的なフラッディングは、ＴＴＬ（生存時間）制限を利用することにより制限される。このことにより、ノード１０２，１０６又は１０７の数が厳しく制限され、高速基幹ネットワークのリンクが十分に利用されることを保障せずに、経路要求は到達する。典型的には、ノードが小ＴＴＬ内に宛先を発見できない場合は、ノードはリング・サーチの拡大を実行する。制限が（ＴＴＬの代わりに）、蓄積されたルーティング・メトリックに基づく場合、フラッディングは経路要求としてより短いリンク及び輻輳されているノード１０２，１０６または１０７を介して中断され、フラッディングは、高速なリンク及びわずかな輻輳を有するノード１０２，１０６及び１０７を介して活性化される。このことにより、ルーティング・プロトコルに対して、横断したノード１０２，１０６又は１０７のノードの性能に基づいて経路探索の実行を可能にすることにより、ネットワークにおける経路をよる効果的に探索することが、可能になる。
【００３２】
＜快速センサー・ネットワーク配置のための接続性／性能インジケータ＞
センサー・ネットワーク配置はできる限り手動の調整を必要とせず（設定インターフェイスが無い）、無線周波数（ＲＦ）カバー調査も典型的には存在しない。典型的なネットワーク接続性インジケータは、ノード１０２，１０６又は１０７が関連付けられるアクセス・ポイントへの信号強度を示す。このことは実際のリンク性能（最大データ速度は低い）又はホップ数（すなわち、アクセス・ポイントは実際の宛先から幾つかのホップだけ離れている）を考慮に入れない。本明細書で記載されるルーティング・メトリックは、ホップ数に無関係な性能の比較を可能にする。例えば、複数のインジケータを利用する発光ダイオード（ＬＥＤ）スクリーン又は複数のＬＥＤを利用するレベル・インジケータのような可視インジケータが、快速な配置に利用される。すなわち、特定の位置におけるネットワーク性能が受け入れ可能か否かをリアル・タイムにオペレータに伝える。当該技術分野で理解されているように、ネットワーク１００は一般に自己構成型であり、ノード（例えば、アクセス・ポイント１０６及び無線ルータ１０７）を配置すること及び配置されたノード１０６及び１０７が線電流、電池、ソーラー・セル等のような電源を有することを保障することのような、最低限のユーザの調整のみを必要とするべきである。
【００３３】
＜ＱｏＳ拡張＞
経路要求が経路が要求されるフローの優先レベルを含む場合、ルーティング・メトリックの例は異なってくる。このために、一つ以上のノードが二つのタイプの優先度情報の経過を好適に追う。
１．  （所与の時間に対するノードのキューにおけるパケットの優先レベルの平均）
スケジューラ（例えばラウンド・ロビン・ベース又はパケット・タギング・ベースのスケジューラ）に依存して、各優先度は送信を試みるためにある割り当てられた割合を有する品質レベルにマッピングされる。例えばこの場合、twは優先レベルに依存する。優先度が高くなるほど、twは小さくなる。
２．  （所与の時間に対するノードの近傍におけるパケットの優先レベルの平均）
例えば、ＩＥＥＥ標準８０２．１１ｅは、異なる優先レベルに対して異なるチャンネル接続確率を利用する。ノードが近隣に送信されたパケットの優先レベルの情報を有する場合、twとteとの推定がフローの相対優先レベルと近隣のトラフィックとに従って実行される。フローの優先度が近隣のトラフィックに比べて非常に大きい場合、tw及びteは小さくなる。
【００３４】
＜搬送波感知多重アクセス/衝突回避方式（ＣＳＭＡ／ＣＡ）拡張＞
パケット完了速度は、データ・パケット完了速度に対応するパケット・ホップ遅延方程式で定義される。ＣＳＭＡ／ＣＡメディア・アクセス・コントローラを利用するシステムにおいて、いくつかのコンテンション・フレーム（すなわちＲＴＳ及びＣＴＳ）も連続的な送信に失敗する。これらの失敗はteが増加することによりリンクのスループットに影響を与える。ＲＴＳパケット完了速度を利用し、teをこの完了速度に依存させることは、実際のルーティング・メトリックを改善する。
【００３５】
これまでの明細書において、本発明の特定の実施形態が記載されてきた。しかし、様々な修正及び変形が、以下の請求項で説明される本発明の範囲から逸脱せずに成され得ることは、当業者には明らかである。従って、明細書及び図面は制限という意味よりはむしろ図説として見なされるべきであり、このような修正の全てが本発明の範囲に含まれることが意図されている。利点、優位性、問題の解決策及び利点、優位性又は問題の解決策を思いつく又はより明白にする任意の要素は、任意又は全ての請求項の決定的に重要、必要とされる、又は本質的な特徴又は要素として構成されるべきではない。本発明は、この出願の継続中に成された任意の修正及びこれら記載された請求項の全ての均等物を含む、添付された請求項によって単独で定義される。
【００３６】
尚、国際出願の英文明細書中にＪＩＳ文字集合で表現できない箇所が存在したため、この翻訳文はで代替表示を利用した。具体的には、Σi∈Nと記載した総和記号は、
【００３７】
【数１】
2008519533.tif 000003
のように表される。
【図面の簡単な説明】
【００３８】
【図１】本発明の実施形態に従うシステム及び方法を採用した複数のノードを含むアドホック無線通信ネットワークを例示するブロック図。
【図２】図１で示されるネットワークで採用される携帯ノードを例示するブロック図。
【図３】異なる帯域幅の利用可能性を有する様々な経路における、輻輳のある多重ホッピング無線ネットワークを示す図。
【図４】第一及び第三ホップが共に利用される、多重ホッピング無線ネットワークを示す図。
【図５】第一及び第三ホップは共に利用されず、スループットが低減しているマルチホッピング無線ネットワークを示す図。
【図６】各ルータは他のルータとのコンテンションを有せず、トラフィックの他のフローが経路に沿って発生しない、二重送受信器ルータの直線列を備えるネットワークを示す図。
【図７】ルータ間のコンテンションとトラフィック源が存在する、輻輳のある多重送受信器ネットワークを示す図。
【図８】本発明の実施形態に従うリンク上のデータ速度、オーバーヘッド及びリトライに基づく特定のリンクに基づいて計算されるルーティング・メトリックの例を示す図。
【図１】
2008519533.tif 000004
【図２】
2008519533.tif 000005
【図３】
2008519533.tif 000006
【図４】
2008519533.tif 000007
【図５】
2008519533.tif 000008
【図６】
2008519533.tif 000009
【図７】
2008519533.tif 000010
【図８】
2008519533.tif 000011
【国際調査報告】
2008519533.tif 000012
2008519533.tif 000013