(57)【要約】慎重に選択されたならば、ネットワーク（１００）に対する安定性をもたらし、また自己回復および負荷バランスのような機能をもたらすことができるルート・メトリックを使用することによって、ノード（１０２，１０６，１０７）における最適なルートを計算するためのシステムおよび方法。ルート・メトリックは、ホップの数、データ・レート、リンク品質、および装置の種類のような多くの因子に基づいたスカラー数として計算される。各因子は、ハロー・メッセージ、または必要に応じて他のルーティング・メッセージを評価することにより決定可能である。
2006526937.tif 000002
【特許請求の範囲】
【請求項１】
無線通信ネットワークにおけるノードの間の最適なルートを計算するための方法であって、
複数のノードのうちの１つが送信元ノードとして動作して、かつ該送信元ノードと直接通信することがない宛先ノードである複数のノードのうちの別の１つにデータ・パケットを送信しようと試みるときに、前記送信元ノードは、ルート要求メッセージを送信し、
他の複数のノードが前記ルート要求メッセージを受信し、かつ前記他の複数のノードのうちの１つが前記宛先ノードまでのルートを有するときに、前記１つのノードは、前記他の複数のノードを含む経路に沿った配送のためのルート返答メッセージを送信し、該ルート返答メッセージは前記１つのノードと前記宛先ノードとの間のルートのためのルート・メトリックを含み、前記他の複数のノードのそれぞれは、前記ルート返答メッセージを受信すると、前記ルート返答メッセージを前記送信元に配送する前に、該ノードそのものと前記ルート返答メッセージを送信してきたノードとの間のルートのための個別のルート・メトリックを追加し、
前記送信元ノードは、前記ルート返答メッセージに基づいて、前記宛先ノードまでの配送のために、データ・パケットを送信すること、
を備える方法。
【請求項２】
請求項１に記載の方法において、
前記送信元ノードが受信する前記ルート返答メッセージに含まれている前記宛先までの前記ルート・メトリックは、さらに、前記送信元ノードと前記宛先ノードとの間のルートにおける次のホップ／近隣の種類に基づいたバイアス成分を含む、方法。
【請求項３】
請求項１に記載の方法において、
前記送信元ノードおよび前記宛先ノードは移動ノードである、方法。
【請求項４】
請求項１に記載の方法において、
前記ルート要求メッセージおよび前記ルート返答メッセージのそれぞれは、個別のホップ・カウント情報およびルート・メトリック情報を含み、該情報は、それぞれのメッセージが１つのノードから別のノードに送信される度に更新される、方法。
【請求項５】
請求項１に記載の方法において、前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のホップの数と、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったリンク品質と、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、方法。
【請求項６】
請求項１に記載の方法において、
前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、方法。
【請求項７】
請求項１に記載の方法において、
前記無線通信ネットワークは、複数のノードが動作するアドホック・マルチホッピング・ピア・ツゥ・ピア無線通信ネットワークを含む、方法。
【請求項８】
無線通信ネットワークにおけるノードの間の最適なルートを計算するための命令のコンピュータ可読媒体であって、
複数のノードのうちの１つが送信元ノードとして動作して、かつ該送信元ノードと直接通信することがない宛先ノードである複数のノードのうちの別の１つにデータ・パケットを送信しようと試みるときに、前記送信元ノードを、ルート要求メッセージを送信するように制御する第１の組みの命令と、
他の複数のノードが前記ルート要求メッセージを受信し、かつ前記他の複数のノードのうちの１つが前記宛先ノードまでのルートを有するときに、前記１つのノードを、前記他の複数のノードを含む経路に沿った配送のためのルート返答メッセージを送信するように制御する第２の組の命令であって、該ルート返答メッセージは前記１つのノードと前記宛先ノードとの間のルートのためのルート・メトリックを含み、前記他の複数のノードのそれぞれを、前記ルート返答メッセージの受信の際に、前記ルート返答メッセージを前記送信元に配送する前に、該ノードそのものと前記ルート返答メッセージを送信してきたノードとの間のルートのための個別のルート・メトリックを追加するように制御する第２の組の命令と、
前記送信元ノードを、前記ルート返答メッセージに基づいて、前記宛先ノードまでの配送のために、データ・パケットを送信するように制御するよう構成された第３の組の命令と、
を備える命令のコンピュータ可読媒体。
【請求項９】
請求項８に記載の命令のコンピュータ可読媒体において、
前記送信元ノードが受信する前記ルート返答メッセージに含まれている前記宛先までの前記ルート・メトリックは、さらに、前記送信元ノードと前記宛先ノードとの間のルートにおける次のホップ／近隣の種類に基づいたバイアス成分を含む、命令のコンピュータ可読媒体。
【請求項１０】
請求項８に記載の命令のコンピュータ可読媒体において、
前記送信元ノードおよび前記宛先ノードは移動ノードである、命令のコンピュータ可読媒体。
【請求項１１】
請求項８に記載の命令のコンピュータ可読媒体において、
前記ルート要求メッセージおよび前記ルート返答メッセージのそれぞれは、個別のホップ・カウント情報およびルート・メトリック情報を含み、該情報は、それぞれのメッセージが１つのノードから別のノードに送信される度に更新される、命令のコンピュータ可読媒体。
【請求項１２】
請求項８に記載の命令のコンピュータ可読媒体において、前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のホップの数と、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったリンク品質と、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、命令のコンピュータ可読媒体。
【請求項１３】
請求項８に記載の命令のコンピュータ可読媒体において、
前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、命令のコンピュータ可読媒体。
【請求項１４】
請求項８に記載の命令のコンピュータ可読媒体において、
前記無線通信ネットワークは、複数のノードが動作するアドホック・マルチホッピング・ピア・ツゥ・ピア無線通信ネットワークを含む、命令のコンピュータ可読媒体。
【請求項１５】
無線通信ネットワークにおけるノードの間の最適なルートを計算するためのシステムであって、
送信元ノードであって、該送信元ノードと直接通信することがない宛先ノードである複数のノードのうちの別の１つに、該送信元ノードがデータ・パケットを送信しようと試みるときに、ルート要求メッセージを送信するように構成された送信元ノードと、
他の複数のノードであって、前記ルート要求メッセージを受信するように構成され、前記他の複数のノードのうちの１つは前記宛先ノードまでのルートを有し、該ルートを有するノードは、前記他の複数のノードを含む経路に沿った配送のためのルート返答メッセージを送信するように構成され、該ルート返答メッセージは前記１つのノードと前記宛先ノードとの間のルートのためのルート・メトリックを含み、前記他の複数のノードのそれぞれは、前記ルート返答メッセージを受信すると、前記ルート返答メッセージを前記送信元に配送する前に、該ノードそのものと前記ルート返答メッセージを送信してきたノードとの間のルートのための個別のルート・メトリックを追加するように構成される他の複数のノードと、
を備え、前記送信元ノードは、さらに、前記ルート返答メッセージに基づいて、前記宛先ノードまでの配送のために、データ・パケットを送信するように構成されている、システム。
【請求項１６】
請求項１５に記載のシステムにおいて、
前記送信元ノードが受信する前記ルート返答メッセージに含まれている前記宛先までの前記ルート・メトリックは、さらに、前記送信元ノードと前記宛先ノードとの間のルートにおける次のホップ／近隣の種類に基づいたバイアス成分を含む、システム。
【請求項１７】
請求項１５に記載のシステムにおいて、
前記送信元ノードおよび前記宛先ノードは移動ノードである、システム。
【請求項１８】
請求項１５に記載のシステムにおいて、
前記ルート要求メッセージおよび前記ルート返答メッセージのそれぞれは、個別のホップ・カウント情報およびルート・メトリック情報を含み、該情報は、それぞれのメッセージが１つのノードから別のノードに送信される度に更新される、システム。
【請求項１９】
請求項１５に記載のシステムにおいて、前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のホップの数と、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったリンク品質と、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、システム。
【請求項２０】
請求項１５に記載のシステムにおいて、
前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、システム。
【請求項２１】
請求項１５に記載のシステムにおいて、
前記無線通信ネットワークは、複数のノードが動作するアドホック・マルチホッピング・ピア・ツゥ・ピア無線通信ネットワークを含む、システム。
【請求項２２】
無線通信ネットワークにおけるノードと他の複数のノードとの間の最適なルートを計算するための方法であって、
前記ノードの存在を前記他の複数のノードに通知し、かつ前記ノードそのものまでのルート・メトリックを含むメッセージを、前記ノードが放送すること、
前記他の複数のノードが前記メッセージを受信する場合、前記他の複数のノードのそれぞれは、前記メッセージの受信の際、前記メッセージを再放送する前に、前記メッセージにおける前記ルート・メトリックに、前記ノードそのものと前記メッセージを送信してきたノードとの間のルートのための個別のルート・メトリックを追加し、前記メッセージにおける更新ルート・メトリックを生成して、該更新ルート・メトリックを前記ノードまでのルートのためのルート・メトリックとして使用すること、
を備える方法。
【請求項２３】
請求項２２に記載の方法において、
前記メッセージは、ルーティング・メッセージである、方法。
【請求項２４】
請求項２２に記載の方法において、
前記メッセージは、ハロー・メッセージである、方法。
【請求項２５】
請求項２２に記載の方法において、
前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、方法。
【請求項２６】
無線通信ネットワークにおけるノードと他の複数のノードとの間の最適なルートを計算するための命令のコンピュータ可読媒体であって、
前記ノードの存在を前記他の複数のノードに通知し、かつ前記ノードそのものまでのルート・メトリックを含むメッセージを放送するように、前記ノードを制御するよう構成された第１の命令の組と、
前記他の複数のノードが前記メッセージを受信する場合、前記他の複数のノードのそれぞれを、前記メッセージの受信の際、前記メッセージを再放送する前に、前記メッセージにおける前記ルート・メトリックに、前記ノードそのものと前記メッセージを送信してきたノードとの間のルートのための個別のルート・メトリックを追加し、前記メッセージにおける更新ルート・メトリックを生成して、該更新ルート・メトリックを前記ノードまでのルートのためのルート・メトリックとして使用するように制御する第２の命令の組と、
を備える命令のコンピュータ可読媒体。
【請求項２７】
請求項２６に記載の命令のコンピュータ可読媒体において、
前記メッセージは、ルーティング・メッセージである、命令のコンピュータ可読媒体。
【請求項２８】
請求項２６に記載の命令のコンピュータ可読媒体において、
前記メッセージは、ハロー・メッセージである、命令のコンピュータ可読媒体。
【請求項２９】
請求項２６に記載の命令のコンピュータ可読媒体において、
前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、命令のコンピュータ可読媒体。
【請求項３０】
無線通信ネットワークにおけるノードと他の複数のノードとの間の最適なルートを計算するためのシステムであって、
前記ノードは、前記ノードの存在を前記他の複数のノードに通知し、かつ前記ノードそのものまでのルート・メトリックを含むメッセージを、放送するように構成されており、
前記他の複数のノードは前記メッセージを受信し、前記他の複数のノードのそれぞれは、前記メッセージの受信の際、前記メッセージを再放送する前に、前記メッセージにおける前記ルート・メトリックに、前記ノードそのものと前記メッセージを送信してきたノードとの間のルートのための個別のルート・メトリックを追加し、前記メッセージにおける更新ルート・メトリックを生成して、該更新ルート・メトリックを前記ノードまでのルートのためのルート・メトリックとして使用する、
システム。
【請求項３１】
請求項３０に記載のシステムにおいて、
前記メッセージは、ルーティング・メッセージである、システム。
【請求項３２】
請求項３０に記載のシステムにおいて、
前記メッセージは、ハロー・メッセージである、システム。
【請求項３３】
請求項３０に記載のシステムにおいて、
前記ルート・メトリックは、前記送信元ノードと前記宛先ノードとの間のルートに沿ったデータ・レートと、前記送信元ノードと前記宛先ノードとの間のルートに沿ったノードの種類を表わす情報とのうちの少なくとも１つ表わす情報を含む、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、送信元と宛先との間の最適なルートを検出することにより、無線通信ネットワークのネットワーク性能を向上させるためのシステムおよび方法に関する。最適なルートは、ルート・メトリックを用いることによって選択される。ルート・メトリックは、慎重に選択されたならば、ネットワークに対する安定性をもたらし、また自己回復および負荷バランスのような機能をもたらすことができる。
【背景技術】
【０００２】
この１０年間で、移動無線電話機ネットワークなどの無線通信ネットワークは、ますます普及している。このような無線通信ネットワークは、一般に、「セルラ・ネットワーク」と呼ばれている。何故なら、サービス・エリアを「セル」と呼ばれる複数の領域に分割するように、ネットワーク・インフラストラクチャの配置が行なわれるからである。地上のセルラ・ネットワークには、サービス・エリアの全体を通して指定箇所に地理的に分布された複数の相互接続された基地局、またはベース・ノードが含まれている。各ベース・ノードには、カバー・エリア内に位置する移動ユーザ・ノードたとえば無線電話機と、電磁信号たとえば無線周波数（ＲＦ：Radio Frequency ）通信信号を送受信することができる１つまたは複数の送受信装置が含まれる。通信信号には、たとえば、所望の変調技術により変調されてデータ・パケットとして送信される音声データが含まれる。当業者ならば理解できるように、ネットワーク・ノードは、データ・パケット通信を多重化フォーマットで、たとえば、時分割多元接続（ＴＤＭＡ：Time Division Multiple Access ）フォーマット、符号分割多元接続（ＣＤＭＡ：Code Division Multiple Access ）フォーマット、または周波数分割多元接続（ＦＤＭＡ：Frequency Division Multiple Access）フォーマットで送受信する。多重化フォーマットは、第１のノードにおける単一の送受信装置が、そのカバー・エリア内の複数の他のノードと同時に通信することを可能にするものである。
【０００３】
近年、「アドホック」ネットワークとして知られる移動通信ネットワークの形式が開発されている。この形式のネットワークでは、各移動ノードが、他の移動ノードに対する基地局またはルータとして動作できるため、基地局の固定されたインフラストラクチャを設ける必要がなくなる。アドホック・ネットワークの詳細については、メイヤ（Mayor ）に付与された米国特許第５，９４３，３２２号の明細書で述べられている。なお、この文献の全体の内容は、本明細書において参照により取り入れられている。
【０００４】
より高性能なアドホック・ネットワークも開発中である。すなわち、従来のアドホック・ネットワークと同様に移動ノードが互いと通信できるだけでなく、さらに、移動ノードが、固定ネットワークにアクセスして、それにより、他の移動ノード（たとえば公衆交換電話網（ＰＳＴＮ：Public Switched Telephone Network ）上の移動ノード、および他のネットワークたとえばインターネット上の移動ノード）と通信できるようなアドホック・ネットワークである。これらの高性能な形式のアドホック・ネットワークの詳細は、以下の文献に記載されている。「ＰＳＴＮおよびセルラ・ネットワークに接続されたアドホック・ピア・トゥ・ピア移動無線アクセス・システム（Ad hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks ）」（米国特許出願第０９／８９７，７９０号明細書、２００１年６月２９日出願）、「別個の予約チャンネルを有する共有パラレル・データ・チャンネルに対する調整チャンネル・アクセスを有するアドホック、ピア・トゥ・ピア無線ネットワークに対する時分割プロトコル（Time Division Protocol for an Ad-Hoc, Peer-to-Peer Network Having Coordinating Channel Access to Shared Parallel Data Channel with Separate Reservation Channel ）」（米国特許出願第０９／８１５，１５７号明細書、２００１年３月２２日出願）、および「アドホック、ピア・トゥ・ピア、移動無線アクセス・システムに対する優先順位決めされたルーティング（Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System ）」（米国特許出願第０９／８１５，１６４号明細書、２００１年３月２２日出願）。なお、これらの文献の全体の内容は本明細書において参照により取り入れられている。
【０００５】
当業者ならば理解できるように、アドホック・ネットワークのある特定のノードは移動性であるため、そのネットワークでは、それらのノードとの接続性を維持する必要がある。送信されたデータ・パケットは、一般に、最終的な宛先に辿り着くまで、送信経路、すなわちルートを生成して、移動装置から移動装置にホップする。しかしながら、移動装置間の送信経路は、多くの場合、装置が移動するにつれて変化する傾向にあるため、アドホック・ネットワークの通信は、個々の移動装置の制限された能力および容量に注意しながらも、最適の性能を達成することに適合できなければならない。
【０００６】
典型的な無線通信ネットワークでは、送信元と宛先との間のホップの数を、ルート・メトリックとして利用する。ホップの数が少なければ少ないほど、良好なルートである。しかしながら、これが非最適なルートをもたらす可能性がある。何故なら、より多くのホップの数を伴うものの、より良好なリンク品質またはデータ・レートを有するより良好なルートが存在する可能性があるからである。
【０００７】
従って、単一のメトリックとしてのホップ以外の因子を用いることによって、効率的に、送信元と宛先との間の最適ルートを発見するシステムおよび方法の必要性が存在する。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の目的は、広範なルート・メトリックを使用して送信元ノードと宛先ノードとの間の最適なルートを検出するシステムおよび方法を提供することにある。
本発明の別の目的は、ネットワークにおいて交換されるハロー・メッセージを使用してルート・メトリックを計算するシステムおよび方法を提供することにある。
【０００９】
本発明の別の目的は、ルート要求およびルート返答のようなルーティング・メッセージを使用してルート・メトリックを計算するシステムおよび方法を提供することにある。
【課題を解決するための手段】
【００１０】
これらの目的および他の目的は、実質的に、慎重に選択されたならば、ネットワークに対する安定性をもたらし、また自己回復および負荷バランスのような機能をもたらすことができるルート・メトリックを使用するシステムおよび方法を提供することによって達成される。ルート・メトリックは、ホップの数、データ・レート、リンク品質、および装置の種類のような多くの因子に基づいたスカラー数として計算される。各因子は、ハロー・メッセージ、または必要に応じて他のルーティング・メッセージを評価することにより決定可能である。
【発明を実施するための最良の形態】
【００１１】
本発明のこれらの目的および他の目的、優位性および新たな特徴は、以下の詳細な説明を添付図面とともに読むことにより、容易に理解されよう。
以下に説明する本発明の実施形態は、送信元と宛先との間の最適ルートを検出することによって、無線通信ネットワークのネットワーク性能を向上させる方法およびシステムを提供する。最適ルートは、より短い待ち時間、および／または、より高いスループット、および／または、より良好なネットワーク・リソースの稼働率を有するルートである。このルートは、以下に詳細に説明するルート・メトリックを用いることによって選択される。ルート・メトリックは、慎重に選択されたならば、ネットワークに対する安定性をもたらし、また自己回復および負荷バランスのような機能をもたらすことができる。
【００１２】
典型的な無線通信ネットワーク、例えば、図１のネットワーク１００では、送信元と宛先との間のホップの数を、一般に、ルート・メトリックとして利用する。ホップの数が少なければ少ないほど、良好なルートである。前述したように、これが非最適なルートをもたらす可能性がある。何故なら、より多くのホップの数を伴うものの、より良好なリンク品質またはデータ・レートを有するより良好なルートが存在する可能性があるからである。
【００１３】
図１は、本発明の実施形態を用いるアドホック・パケット交換型無線通信ネットワーク１００の例を示すブロック図である。具体的には、ネットワーク１００は、複数の移動無線ユーザ端末１０２−１〜１０２−ｎ（ノード１０２または移動ノード１０２と呼ぶ）を含んでいる。ネットワーク１００は、複数のアクセス・ポイント１０６−１，１０６−２，…１０６−ｎ（ノード１０６またはアクセス・ポイント１０６と呼ぶ）を有する固定ネットワーク１０４を含むことができる（しかしながら、必ずしも必要とする訳ではない）。これらのノード１０６は、ノード１０２に、固定ネットワーク１０４へのアクセスを与えるためのものである。固定ネットワーク１０４は、たとえば、核となるローカル・アクセス・ネットワーク（ＬＡＮ：Local Area Network）、および複数のサーバおよびゲートウェイ・ルータを含むことができる。サーバおよびゲートウェイ・ルータは、ネットワーク・ノードに、他のネットワークたとえば他のアドホック・ネットワーク、公衆交換電話網（ＰＳＴＮ：Public Switched Telephone Network ）およびインターネットへのアクセスを与えるためのものである。ネットワーク１００は、さらに、複数の固定ルータ１０７−１〜１０７−ｎ（ノード１０７または固定ルータ１０７と呼ぶ）を含むことができる。これらのルータ１０７は、データ・パケットを他のノード１０２，１０６，または１０７の間でルーティングするためのものである。ここでの説明上、前述したノードを一括して、「ノード１０２，１０６，および１０７」、または単純に「ノード」もしくは「端末」と呼ぶこともあることに注意されたい。
【００１４】
当業者ならば理解できるように、ノード１０２，１０６，および１０７は、互いに直接通信することもできるし、あるいはノード間で送信中のパケットに対するルータ、または複数のルータとして動作する１つまたは複数の他のノード１０２，１０６，または１０７を介して通信することもできる。このことは以下の文献に記載されている。米国特許第５，９４３，３２２号明細書（メイヤ）、および米国特許出願第０９／８９７，７９０号明細書、米国特許出願第０９／８１５，１５７号明細書、および米国特許出願第０９／８１５，１６４号明細書（これらはすでに参照されている）。
【００１５】
図２に示したように、各ノード１０２，１０６，および１０７には、送受信装置またはモデム１０８が含まれている。送受信装置１０８はアンテナ１１０に結合され、コントローラ１１２の制御の下で、ノード１０２，１０６，または１０７との間で、パケット化された信号などの信号を送受信することができる。パケット化されたデータ信号は、たとえば、音声、データ、またはマルチメディア情報、およびパケット化された制御信号（ノード更新情報など）を含むことができる。
【００１６】
各ノード１０２，１０６，および１０７には、さらに、メモリ１１４、たとえばランダム・アクセス・メモリ（ＲＡＭ：Random Access Memory）が含まれている。メモリ１１４は、とりわけ、ネットワーク１００における自分自身および他のノードに関するルーティング情報を記憶することができる。図２にさらに示すように、ある特定のノード、特に移動ノード１０２は、ホスト１１６を含むことができる。ホスト１１６は、任意の数の装置、たとえばノートブック・コンピュータ端末、移動電話機ユニット、移動データ・ユニット、または任意の他の好適な装置により構成されていても良い。また各ノード１０２，１０６，および１０７には、インターネット・プロトコル（ＩＰ：Internet Protocol ）およびアドレス解決プロトコル（ＡＲＰ：Address Resolution Protocol ）を実行するための適切なハードウェアおよびソフトウェアも含まれている。当業者ならば、これらのプロトコルの目的を容易に理解することができよう。また伝送制御プロトコル（ＴＣＰ：Transmission Control Protocol ）およびユーザ・データグラム・プロトコル（ＵＤＰ：User Datagram Protocol）を実行するための適切なハードウェアおよびソフトウェアが含まれていても良い。
【００１７】
前述したように、図１のネットワーク１００のようなネットワークにおいて、ノード間のルートを選択する場合、送信元ノードと宛先ノードとの間のホップの数を、一般に、ルート・メトリックとして利用する。これが非最適なルートをもたらす可能性がある。何故なら、より多くのホップの数を伴うものの、より良好なリンク品質またはデータ・レートを有するより良好なルートが存在する可能性があるからである。以下に説明する実施形態は、そのようなメトリックとして他のものを使用することを含む。
【００１８】
ルート・メトリックとは、送信元と宛先との間のコストを表わすスカラー数である。コストが高くなればなるほど、ルートは悪化する。コストを決定する種々の因子として、以下の因子が挙げられるが、それらに限定される訳ではない。
１．  送信元と宛先との間のホップの数
２．  送信元から宛先に至るルートに沿ったデータ・レート
３．  送信元から宛先に至るルートに沿ったリンク品質
４．  送信元と宛先との間の中間ノードとして存在する装置の種類
以下の理由一覧により、これらの因子を用いることを正当化することができる。
【００１９】
ホップの数
任意のネットワークにおいて、各ホップにおけるパケットにより生じる遅延は、送信ノードにおける処理および待ち行列遅延、ならびにリンク上の媒体アクセスを含む送信および伝播遅延の関数である。従って、マルチホップ・ネットワークにおいて、ルート中のホップの数を減らすことにより、そのルートを伝播するパケットが被る端末間遅延は著しく低減され得る。巨大ネットワークの遠距離ノード間において、多くの場合、少数の長距離リンクからなる基幹回線のルーティングが利用され、低遅延かつ高速接続がもたらされる。
【００２０】
マルチホップ無線ネットワークの場合では、各ホップにおいて生じ得る大きな遅延のために、無線ネットワークの場合に比べて、ルート長を低減することに対する必要性は遥かに高い。これらの遅延は、共有されるチャネルに対する競合の結果として生じる媒体アクセス遅延、誤り制御または直接拡散スペクトル符号化のために増大したパケット・サイズの結果として生じる送信遅延、誤りを起こしやすいリンク上の信頼性のためのリンク層の自動再送要求（ＡＲＱ：Automatic Repeat Request）プロトコルの結果として生じる再送信遅延、および送信ノードと受信ノードとの間で交換する場合に生じるような無線依存遅延を含むことができる。
【００２１】
データ・レート
ノードは、リンクの信頼性に応じて、種々の近隣に対して、種々のデータ・レートを用いることができる。選択できるならば、ノードは、スループットを高めるために、利用可能な最大のデータ・レートを利用するべきである。このように、データ・レートは、ルート・メトリック全体における一因子であるべきである。
【００２２】
リンク品質
ＲＳＳＩレベル、ビット誤り率、ＰＤＳＱ値、タイムアウト等を組み合わせた値であるリンク品質もまた、メトリックの一部であるべきである。これにより、劣悪な品質のリンクから良好な品質のリンクを選び出すようにルーティングすることが可能になる。
【００２３】
装置の種類
メッシュ・ネットワークのような無線ネットワークにおいては、３つの異なる装置の種類が存在する。すなわち、加入者装置（ＳＤ：Subscriber Device ）、無線ルータ（ＷＲ：Wireless Router ）、およびインテリジェント・アクセス・ポイント（ＩＡＰ：Intelligent Access Point）である。中間ノード（すなわち、宛先ノード以外）を選択できるならば、装置は、ＳＤまたはＩＡＰの前にＷＲを選択して、他のＳＤ装置のバッテリーを消耗させないように、かつＩＡＰをビジー状態にしないようにするべきである。同様に、装置は、同じ理由により、ＳＤの前に中間ノードとしてＩＡＰを使用するべきである。そのようなネットワークでは、いくつかの他の装置も存在することができ、従って、装置の種類はルート・メトリック全体の重要な部分をなすべきである。この例を以下に詳細に説明する。
【００２４】
この種のネットワークにおいて使用される装置は、一般に、ＡＴＰと呼ばれるモジュールを有する。このモジュールは、ノードがデータ・メッセージを交換することにより通信した全てのＭＡＣアドレスに対するリンク品質を報告する。ＡＴＰはまた、この近隣との通信に使用されている現在のデータ・レートも提供する。リンク品質／データ・レートを、一般に、スカラー数としてルーティングすることにより、他のモジュールに通信することができる。次いで、ルックアップ・テーブルを利用して、リンクの信頼性および使用されるデータ・レートを得ることができる。ＡＴＰおよびリンク品質については、以下の文献にさらに詳細に記載されている。「アドホック・ネットワークにおいて、送信電力およびデータ・レートの適合制御を行なうためのシステムおよび方法（System and Method for Providing Adaptive Control of Transmit Power and Data Rate in Ad-Hoc Networks ）」（米国特許出願第１０／０８７，０１６号明細書、２００２年３月１５日出願）、「アドホック・ネットワークにおいて、ルーティング・プロトコルに対するリンク信頼性の基準を与える方法（A Method to Provide a Measure of Link Reliability to a Routing Protocol in an Ad hoc Network）」（米国仮特許出願第６０／５４６，９４０号明細書、２００４年２月２４日出願）、および「無線ネットワークにおいて、リンク品質を特徴付けるためのシステムおよび方法（System and Method for Characterizing the Quality of a Link in a Wireless Network）」（米国仮特許出願第６０／５４６，９４１号明細書、２００４年２月２４日出願）。なお、これらの特許出願および仮特許出願の全体の内容は本明細書において参照により取り入れられている。
【００２５】
以下の例は、修正されたオン・デマンド・ルーティング・プロトコルを用いて、システムにおいて使用されるルート・メトリックを計算する方法を示す。そのようなルーティング方法については、以下の文献にさらに詳細に記載されている。「オン・デマンド・ルーティング・プロトコルに従うネットワークにおいて、アクセス・ポイントまたはＩＡＰまたはゲートウェイに対する連続接続を実現するためのシステムおよび方法（System and Method for Achieving Continuous Connectivity to an Access Point or IAP or Gateway in a Network Following an On-Demand Routing Protocol ）」（米国特許出願第６０／４３９，４４９号明細書、２００３年1 月１３日出願）、「無線ネットワークにおいて、円滑なハンドオフをもたらし、かつ一方向リンクを削除するようにＡＯＤＶを修正するためのシステムおよび方法（System And Method For Modifying  AODV To Facilitate Smooth Handoffs And Eliminate Unidirectional Links In A Wireless Network）」（米国特許出願第６０／４３９，４５５号明細書、２００３年1 月１３日出願）、「オン・デマンド・ルーティング・プロトコルに従う無線ネットワークにおいて、アクセス・ポイントまたはゲートウェイに対する連続接続を実現し、かつそのネットワークにおける固定端末間での移動端末の円滑なハンドオフを実行するためのシステムおよび方法（System And Method For Achieving Continuous Connectivity To An Access Point Or Gateway In A Wireless Network Following An On-Demand Routing Protocol, and To Perform Smooth Handoff of Mobile Terminal Between Fixed Terminals in the Network）」（米国特許出願第１０／７５５，３４６号明細書、２００４年1 月１３日出願）、「無線通信ネットワークの全体の性能を向上させるためのシステムおよび方法（System and Method to Improve the Overall Performance of a Wireless Communication Network）」（米国特許出願第６０／４７６，２３６号明細書、２００３年６月６日出願）、および「マルチチャネル無線通信ネットワークにおけるチャネル稼働率を最大化するためのシステムおよび方法（System and Method to Maximize Channel Utilization in a Multi-Channel Wireless Communication Network ）」（米国特許出願第６０／４７５，８８２号明細書、２００３年６月５日出願）。なお、これらの全体の内容は本明細書において参照により取り入れられている。本発明の実施形態によるルート・メトリックの計算は、以下に詳細に説明される。
【００２６】
インフラストラクチャ・モードにおいて、ノードは、ルーティング・パケットを交換することによって、ＩＡＰ以外の任意の宛先までのルート・メトリックについての情報を得る。ＩＡＰまでのルート・メトリックについては、ルーティング・パケットを交換するとともに、近隣からのハロー・パケットを受信することによって得ることができる。ハロー・メッセージから計算されたルート・メトリックと、ルーティング・パケットから計算されたルート・メトリックとの間に差異がある場合は、ハロー・メッセージの情報が用いられる。以下は、本発明の実施形態によるルート・メトリックの計算の例である。
【００２７】
ハロー・メッセージによるＩＡＰまでのルート・メトリック
前述のプロトコルに従う送信元ノードは、ＩＡＰに至るルートおよびＩＡＰに至るまでのルート・メトリックについての情報を、この情報をハロー中で周期的に放送している近隣から得る。このメトリックは、次いで、ＩＡＰを通知している特定の近隣までのメトリックに加えられる。また、異なる種類のノード間で区別するために、一方を他方よりも選択するバイアスが加えられる。数学的に、これは次式（１）により表現される。
Ｒｓｄ＝Ｒｓｎ＋Ｒｎｄ＋次のホップのバイアス      （１）
ここで、Ｒｓｄ＝送信元（source）と宛先（destination ）との間のルート・メトリック、Ｒｓｎ＝送信元と次のホップ（next hop）との間のルート・メトリック、Ｒｎｄ＝次のホップ（next hop）と宛先との間のルート・メトリック（これは、次のホップが報告したものである）、およびＲｓｎ，すなわち次のホップまたは近隣までのルート・メトリックは、次式（２）を用いて計算される。
【００２８】
【表１】
2006526937.tif 000003
近隣ではなく宛先までのルート・メトリックは、式（１）を用いて計算される。式（１）では、近隣の種類に基づいて、さらに、次のホップのバイアスが加えられている。文章にすれば、上式は、以下のように表現可能である。
宛先までのルート・メトリック＝次のホップ／近隣までのルート・メトリック＋次のホップ／近隣から宛先までのルート・メトリック＋次のホップ／近隣の種類に基づいたバイアス
図３に示す以下の例は、上記手順を明確にするために与えられている。図３は、本発明の実施形態に従って、ハロー・パケットによるルート・メトリックの計算を示す例である。
【００２９】
この例における「ｓ」１２０は、宛先（通常は、ＩＡＰ）に至るルートを検出しようとしている現在のノードである。「ｎ」１３０は、ハロー・パケットにより宛先に至るルートを通知する近隣ノードである。ハロー・パケット１４０は、近隣から宛先までのルート・メトリックＲｎｄを含む。「ｓ」から「ｎ」までのルート・メトリックはＲｓｎであり、「ｎ」から「ｓ」までのルート・メトリックはＲｎｓである。リンクは均一である必要はなく、従って、これらの値は異なっていても良い。そのようなハロー・メッセージを受信すると、ノード「ｓ」は、上式（１）を用いて、宛先までのルート・メトリックＲｓｄを求める。ノードｓ，ｎは、いかなる装置（すなわち、ＳＤ，ＷＲ，ＩＡＰ）であっても構わない。ＩＡＰの場合は、通知されるメトリックはゼロである。
【００３０】
ルーティング・メッセージによる他の宛先までのルート・メトリック
この種のネットワークでは、一般に、ルート要求（ＲＲＥＱ：Route Request ）およびルート返答（ＲＲＥＰ：Route Reply ）を用いて、異なるノードまでのルートを得る。これらのメッセージは、「ルート・メトリック」および「ホップ・カウント」と呼ばれるフィールドを有する。「ホップ・カウント」は、ホップにより伝播される度に更新される。ノードは、ルート要求を生成するとき、これらのフィールドの両方にゼロを書き込む。中間ノード、あるいは宛先がこのパケットを受信することができる。いずれの場合であっても、受信ノードは、「ルート・メトリック」フィールドには「近隣までのルート・メトリック」を加え、「ホップ・カウント」フィールドには「１」を加えた後、ＲＲＥＱの送信元に戻るルートを生成する。次いで、受信ノードは、ＲＲＥＱを転送するか、プロトコルにおいて指定されるようにＲＲＥＰメッセージで返送する。ＲＲＥＱを転送した場合、その受信ノードは前述のことと同じことを行なう（すなわち、ルートに送信元ルートを加え、ＲＲＥＱパケットの「ルート・メトリック」フィールドに「近隣までのルート・メトリック」を加え、従って、送信元アドレスまでのルート・メトリックを得る）。
【００３１】
ノードは、そのノードが宛先までの妥当なルートを有する場合か、あるいはそのノードそのものが宛先である場合にのみ、返答することができる。ノードが中間ノードである場合は、そのノードは、ＲＲＥＰにおけるフィールドにルーティング・テーブルからのルート・メトリックを書き込む。このＲＲＥＰを受信すると、ノードは、このＲＲＥＰを転送／送信した「近隣までのルート・メトリック」を追加する。このようにして、関連する宛先までのルート・メトリックが完成する。現在のノードが送信元ではない場合、ＲＲＥＰは送信元に転送される。返答するノードが宛先のときも、そのノードがＲＲＥＰにおける「ルート・メトリック」フィールドにゼロを書き込むという事実を除いて、同様な処理が実行される。この値は、ＲＲＥＰがこのように種々のノードの間を行き来するにつれて変更される。
【００３２】
図４に示す以下の例は、上記手順を明確にするために与えられている。図４は、本発明の実施形態に従って、ルーティング・パケットによるルート・メトリックの計算を示す例である。
【００３３】
図４では、４つのノード、ノードＡ１５０，Ｂ１６０，Ｃ１７０，Ｄ１８０が示されている。これらの間のルート・メトリックもまた、図中に示されている。ＲＸＹは、ノードＸとＹとの間のルート・メトリックを表わす。なお、無線リンクに伴う非対称性により、ＲＸＹとＲＹＸとは異なる可能性があることに注意されたい。ノードＡがノードＤとの通信を望む場合、ノードＡは、ゼロに設定された「ルート・メトリック」フィールドを有するルート要求パケットを生成する。このパケットがノードＢにより受信されると、ノードＢは、ＲＲＥＱパケットを転送してきた「近隣（この場合は、Ａそのものである）までのルート・メトリック」を、ＲＲＥＱパケットにおける「ルート・メトリック」フィールドに加え、そのルーティング・プロトコルに従って送信元（すなわち、ノードＡ）までのルートを生成／更新する。この例では、Ｂは、ゼロ（「ルート・メトリック」フィールドに記憶されている現在の値）にＲＢＡを加え、Ａまでのルート・メトリックを得る。ノードＢがＤまでのルートを認識していない場合、ノードＢは、「ルート・メトリック」フィールドに現在のところＲＢＡを有するＲＲＥＱパケットを転送する。このパケットを受信すると、Ｃは同じことを行い、ＲＢＡにＲＣＢを加え、Ａまでのルート・メトリックを得る。従って、Ａまでのルート・メトリックは、ＲＣＡ＝ＲＢＡ＋ＲＣＢのように計算される。
【００３４】
図４の例において、Ｃは、Ｄまでの「十分に使用可能な（fresh enough）」ルートを有する、すなわち、Ｃは、ルート・メトリックＲＣＤを伴う有効なルートを有するものとする。従って、Ｃは、ＲＲＥＱパケットに対する返答として、ＲＲＥＰパケットの「ルート・メトリック」フィールドにルート・メトリックＲＣＤを書き込み、ノードＢに対してそのパケットをユニキャストする。そのようなパケットを受信すると、ノードＢは、ノードＢに対してＲＲＥＰパケットを転送してきた近隣までのルート・メトリックを、そのＲＲＥＰにおける「ルート・メトリック」フィールドに追加する。この場合、ノードＢは、そのフィールドに既に存在していたＲＣＤにＲＢＣを追加する。従って、Ｄまでのルート・メトリックは、ＲＢＤ＝ＲＢＣ＋ＲＣＤのように計算される。
【００３５】
ノードＡが最後にＲＲＥＰを受信したときも、同様な手順がノードＡにより用いられる。従って、ＲＲＥＰは、ノードＤまでのルート・メトリックＲＡＤ＝ＲＡＢ＋ＲＢＣ＋ＲＣＤを有する。
【００３６】
上記のルート・メトリックの計算の比較を以下に説明する。選択できるならば、ノードは、そのノードに付随するルート・メトリックとして最小のルート・メトリックを有するルートを使用するべきである。近隣処理サブモジュールは、ＩＡＰまでのルート・メトリックの昇順に並べられたルートのリストを保持している。このリストの初めの方にあるルートは、後の方にあるルートよりも好ましい。
【００３７】
この方法には、いくつかの変形が存在し得る。例えば、ルートの振動を回避するために、さらなるバイアスまたはヒステリシスを追加することができる。「バイアス」は、一定値であっても良いし、あるいはメトリックそのものまたはホップの数のような所定量の関数であっても良い。バイアスの使用は、以下の例において説明される。
【００３８】
この例において、ノードがＩＡＰまでの有効なルートを有し、かつそれに付随するメトリック「ｘ」を有する場合、振動を回避するために、ノードは、現在のメトリックよりも「ｙ」（バイアス）だけ小さいメトリックを与えない限り、新たなルートを確立しようと試みるべきではない。ルートが他のＩＡＰの方を向いている場合は、さらに高いバイアスを使用することができる。
【００３９】
前述したメトリックに加えて、さらに他のメトリック、例えば、バッテリー寿命、帯域幅、混雑状態等を使用することができる。前述の４つを含むそのような任意の種類のメトリックを用い、前述したように、例えばハロー・メッセージ内で伝播させることができる。
【００４０】
本発明のいくつかの典型的な実施形態のみについて詳細に説明してきたが、当業者であれば容易に分かるように、本発明の新たな示唆および優位性から実質的に逸脱することなく、典型的な実施形態において多くの変更が可能である。したがって、このような変更はすべて、以下の請求項に規定されるような本発明の範囲に含まれることが意図される。
【図面の簡単な説明】
【００４１】
【図１】本発明の実施形態による複数のノードを含むアドホック無線通信ネットワーク例を示すブロック図。
【図２】図１に示すネットワークにおいて用いられる移動ノードの例を示すブロック図。
【図３】本発明の実施形態に従ったハロー・パケットによるルート・メトリックの計算の例を示す概念ブロック図。
【図４】本発明の実施形態に従ったルーティング・パケットによるルート・メトリックの計算の例を示す概念ブロック図。
【図１】
2006526937.tif 000004
【図２】
2006526937.tif 000005
【図３】
2006526937.tif 000006
【図４】
2006526937.tif 000007
【国際調査報告】
2006526937.tif 000008
2006526937.tif 000009