(57)【要約】無線マルチホップ通信ネットワークにおけるアドレス解決マッピングのための方法が提示される。ネットワークはクライアントデバイスおよびインフラストラクチャデバイスまたはそれらのいずれかにより構築され、ネットワークトラフィックは、ＡＲＰの転送および再ブロードキャストを使用してそのようなネットワークアーキテクチャにおけるデバイスの位置を決めることを基本とする。また、本発明はそのようなネットワークのためのデバイスを含み、完全な通信システムについて記載する。
2007532058.tif 000002
【特許請求の範囲】
【請求項１】
無線マルチホップデータ通信ネットワークにおけるアドレス解決マッピングのための方法であって、本方法は、
第１のノードから第２のノードにアドレス解決プロトコル（ＡＲＰ）要求をブロードキャストするステップと、
前記ＡＲＰ要求を受信する前記第２のノードが、ＡＲＰメッセージの宛先を判断するステップと、
前記ＡＲＰ要求が、第３のノードに向けられると判断されれば、前記ＡＲＰ要求を送信するステップと、
前記第３のノードから前記第１のノードに前記第２のノードを介してＡＲＰ応答を転送するステップと
を備える方法。
【請求項２】
前記第２のノードは複数のノードを含む請求項１に記載の方法。
【請求項３】
前記ノードにおいて格納され、検出された以前のＡＲＰ要求およびＡＲＰ転送の保留リストをさらに備える請求項１に記載の方法。
【請求項４】
格納された前記以前のＡＲＰ要求またはＡＲＰ転送の前記保留リストの格納時間を制限するステップをさらに備える請求項３に記載の方法。
【請求項５】
ノードが特定の宛先へ送信を許されるＡＲＰ転送の前記割合を制限するステップをさらに備える請求項１に記載の方法。
【請求項６】
ノード間のリンク品質を測定するステップと、
ＡＲＰメッセージ手順の途中でノードにリンク品質情報を配信するステップとをさらに備える請求項１に記載の方法。
【請求項７】
前記リンク品質情報が、確認情報および無線リンク品質、データ速度のスループット、ビットエラー率のうちの少なくとも１つを備える請求項１に記載の方法。
【請求項８】
ＡＲＰテーブルが更新されるべき時間を判断するために前記リンク品質情報を使用するステップをさらに備える請求項６または７に記載の方法。
【請求項９】
更新がなされるべきであるかの判断のために前記リンク品質情報を閾値と比較するステップをさらに備える請求項６または７に記載の方法。
【請求項１０】
あるノードがあるノードと通信することができないときに、ＡＲＰエラーメッセージが生成され、前記ネットワークの受信中のノードに配信される請求項１に記載の方法。
【請求項１１】
前記ＡＲＰ要求の再ブロードキャストまたは転送の前に前記ＡＲＰ要求を変更するステップをさらに備える請求項１に記載の方法。
【請求項１２】
マルチホップ無線ネットワークにおけるルーティング手段を有する通信デバイスであって、前記デバイスは、
命令セットメモリと、
少なくとも１つの無線トランシーバと、
前記命令セットメモリにアドレス解決プロトコル（ＡＲＰ）命令を付与する手段と、
前記命令セットメモリにＡＲＰメッセージの転送および再ブロードキャスト命令を付与する手段と
を備えるデバイス。
【請求項１３】
ＡＲＰの転送およびブロードキャストのための前記手段はＡＲＰメッセージの前記宛先を判断する手段を含む請求項１２に記載のデバイス。
【請求項１４】
前記通信デバイスはクライアントシステムである請求項１２に記載のデバイス。
【請求項１５】
前記クライアントシステムは、１または幾つかのラップトップコンピュータ、またはパーソナルコンピュータ（ＰＣ）、またはパーソナルディジタルアシスタント（ＰＤＡ）、または移動電話機、または組み込みコンピュータである請求項１４に記載のデバイス。
【請求項１６】
前記通信デバイスはインフラストラクチャシステムである請求項１２に記載のデバイス。
【請求項１７】
前記インフラストラクチャシステムは、１または幾つかのＷＬＡＮ（無線ローカルエリアネットワーク）インフラストラクチャデバイス、および移動電話機インフラストラクチャデバイスである請求項１６に記載のデバイス。
【請求項１８】
前記ＡＲＰの転送または再ブロードキャスト命令は、前記ＡＲＰメッセージを変更して前記デバイスが送信元であるように見せかける請求項１２に記載のデバイス。
【請求項１９】
マルチホップ無線データ通信のためのシステムであって、前記システムは複数の通信デバイスを含み、
前記通信デバイスは、
命令セットメモリと、
少なくとも１つの無線トランシーバと、
前記命令セットメモリにアドレスリゾリューションプロトコル（ＡＲＰ）命令を付与する手段と、
前記命令セットメモリにＡＲＰの転送および再ブロードキャスト命令を付与する手段と、
前記通信デバイスによって構築された通信ネットワークと
を備えるシステム。
【請求項２０】
前記通信デバイスはＡＲＰメッセージの宛先を判断する手段をさらに含む請求項１９に記載のシステム。
【請求項２１】
前記通信デバイスはクライアントシステムである請求項１９に記載のシステム。
【請求項２２】
前記クライアントシステムは、１または幾つかのラップトップ、またはパーソナルコンピュータ（ＰＣ）、またはパーソナルディジタルアシスタント（ＰＤＡ）、または移動電話機、または組み込みコンピュータである請求項２１に記載のシステム。
【請求項２３】
前記通信デバイスはインフラストラクチャシステムである請求項１９に記載のシステム。
【請求項２４】
前記インフラストラクチャシステムは、１または幾つかのＷＬＡＮ（無線ローカルエリアネットワーク）インフラストラクチャデバイス、および移動電話機インフラストラクチャデバイスである請求項２３に記載のシステム。
【請求項２５】
外部ネットワークに接続された少なくとも１つのゲートウエイをさらに含む請求項１９に記載のシステム。
【請求項２６】
無線マルチホップデータ通信ネットワークにおけるアドレス解決マッピングのための命令セットであって、該命令セットは、
第１のネットワークノードから第２のノードにアドレス解決プロトコル（ＡＲＰ）要求をブロードキャストするための第１の命令セットと、
前記ＡＲＰ要求を受信し、ＡＲＰメッセージの宛先を判断するための前記第２のノードにおける第２の命令セットと、
前記ＡＲＰ要求が第３のノードに向けられると判断されれば、前記ＡＲＰ要求を送信する第３の命令セットと、
前記第３のノードから前記第１のノードに前記第２のノードを介してＡＲＰ応答を転送するための第４の命令セットと
を含む命令セット。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は通信ネットワーク、特にアドホックネットワークにおけるコンピュータネットワークに関し、特にアドレス解決プロトコル（ＡＲＰ）のメッセージタイプを追加して使用するパケットベースのルーティングスキームに関する。
【背景技術】
【０００２】
移動ユーザ間の無線通信はデバイスおよび技術の発展と共にますます普及している。インフラストラクチャの展開が電気通信システムおよびデータネットワークシステム双方において広がりつつある。また今日、電気通信システムでは、パケット交換ネットワークを使用することが多くなり、傾向としては明らかにこのパケットベースのルーティングスキームの方向に向かっている。このシステムはデータネットワークでは多年にわたって使用されており、従ってこの目的のために多くの標準化されたルーティングプロトコルが存在する。しかしながらそのプロトコルは、例えばいわゆるアドホックネットワークのような急激に変化するネットワークトポロジに対する備えがない。
【０００３】
無線アドホックネットワークは、通常の有線ネットワークのインフラストラクチャと同じ静的性質を持たないことを特徴とし、アドホックベースのネットワークには中央制御はなく、ネットワークは自然発生的に構築されることが多い。アドホックベースのネットワークは分散化の概念による制御を維持している。標準的な固定ネットワークアーキテクチャと比較してノードを自由に接続または切断することができ、ノードは急激に発生、消滅し、ネットワークトポロジは動的に変化する。幾つかの場合では、そのようなアドホックネットワークは、インフラストラクチャの構成要素としてのユーザ／クライアントデバイス自体により形成される。その場合、ユーザがネットワークセルの内外に動き回るという意味においてこれらの構成要素にはまさしく移動性があり、したがってそれ故にインフラストラクチャは動き回り、動的に変化するであろう。これはインフラストラクチャを構築する上で刺激に富み、可能性に満ちた方法ではあるが、その方法はルーティングプロトコルに極めて大きな要求を課す。
【０００４】
無線環境におけるその他の問題は、ネットワークフローの性能および効率を劣化させる無線に固有の問題に起因する。インフラストラクチャノードの移動または無線環境における物体の移動によるフェーディングの問題が生じ得るし、領域内にある他の無線源からの妨害による問題もあり得る。
【０００５】
この種のネットワークの機構は軍事環境で使用されたが、今や民事領域にも移行してきつつある。今日例えば、住宅地域または商業地域における広帯域無線アクセスのために素早くインフラストラクチャエリアを構築するのに、無線システムが使用される。例えば非常時の状況で、災害地域で、または軍事目的の戦場で、一時的なインフラストラクチャの構築に無線システムが使用されることがある。また例えば、コンサート、会議、会合または季節的な旅行先などのようなイベントの中で一時的にアクセス提供エリアを構築するのに使用することもできる。この種の分野では、一年中アクセスを提供する必要はなく特定期間中のみであり、従ってこのような場合に固定インフラストラクチャを構築するのはあまりにも不経済といえる。
【０００６】
今日、幾つかのインターネットサービスプロバイダ（ＩＳＰ）は、空港、レストラン、コーヒーショップおよびホテルなどの公共または準公共地域で固定無線インフラストラクチャシステムを使用して無線アクセスを提供している。これらのシステムはホットスポットと呼ばれることが多い。
【０００７】
ユーザからのアクセス取得要求が増加すると、提供領域および帯域幅を考慮して、無線提供領域または帯域幅を拡張する一つの方法はインフラストラクチャの構成要素をさらに多く設置することであるが、通常の固定無線の構成要素によりこれを実施すれば高くつく。そこで無線ルータを使用するネットワークの構築概念が浮上した。この場合設置手順の単純化のために、アドホックルーティングプロトコルが使用され得る。
【０００８】
アドホックネットワークを検討する場合、基本的に２種類のネットワークの使用法がある。第１の使用法は、外部ネットワーク、例えばインターネットへのアクセスを提供する外部ゲートウエイを持たないローカルエリアネットワークの構築である。このやり方は災害地域に関係する設置または戦場での軍事的設置に見られる。他のそして恐らくさらに一般的な使用法は１または幾つかのゲートウエイが、例えばＩＰ（インターネットプロトコル）ベースの私設または公共ネットワーク、例えばインターネットへの外部接続を有するネットワークを提供する場合である。そのようなネットワーク構成では、例えばデータトラフィックのタイプ、混雑度、またはルーティングコストに応じて、データパケットは種々のルートをとったり、種々のゲートウエイを使用したりすることができる。
【０００９】
パケットベースのルーティングスキームはその通信ネットワークシステムを階層モデル、例えばＯＳＩ参照モデルに沿って構築することが多い。通信ソフトウエアまたはハードウエアは階層的に動作する幾つかの小さなサブユニット、レイヤに分割される。情報および通信制御パラメータは局所的に上下に、そして送受信端間の同じ層間でやり取りされる。そのような各層は通信命令の種々のタスクを担う。ルーティングに関しては、ＯＳＩ参照モデルによる最初の３つの層が最も重要である。
【００１０】
レイヤ１はデータビットの物理的伝送を担う。物理的手段の例は、例えばイーサネットベースのネットワークの有線リンクまたは無線ローカルエリアネットワーク（ＷＬＡＮ）の無線リンクでありうる。
【００１１】
レイヤ２は多くの場合リンク層またはＭＡＣ層と呼ばれ、まとまりのあるデータ、誤り検出およびネットワークリソースの調整を担う。
【００１２】
レイヤ３は多くの場合ネットワーク層と呼ばれ、ネットワークにおける任意のノード対の間の通信を可能にすることを担う。例えば、この層はルーティング計算および幾つかの輻輳制御を行う。この目的のためにネットワークのタイプに応じて、種々のルーティングプロトコルが開発されている。
【００１３】
ＩＰベースのネットワークにおけるパケットルーティングプロトコルは距離ベクトルまたはリンク状態情報を使用するルーティングアルゴリズムを一般にベースとし、ネットワークにおける送信元と宛先の各対に対するルートを見つけ、維持する。原理的に距離ベクトルルーティングアルゴリズムでは、各ルータは全てのホストへの距離をその近隣ルータにブロードキャストし、その情報を受信する各ルータはネットワークにおける各ホストへの最短ルートを計算する。リンク状態ルーティングアルゴリズムでは、各ルータはその各隣接ネットワークリンクの状態情報をブロードキャストし、その情報を受信する各ルータはリンク状態情報からネットワークの全体像に関するデータベースを維持し、データベースのリンクコストに基づいて各ホストへの最短ルートを計算する。これらのルーティングアルゴリズムは比較的静的なネットワークに対して設計されており、従ってトポロジーが頻繁に変化するアドホックネットワークに対しては新しいルーティングアルゴリズムの設計が必要である。
【００１４】
アドホックネットワークに対して基本的に２つのカテゴリのルーティングプロトコルが存在する。これらは「プロアクティブ」（テーブル駆動）および「リアクティブ」（オンデマンド）ルーティングプロトコルである。これらのプロトコルを組み合わせたプロトコルも可能である。
【００１５】
プロアクティブルーティングプロトコルは、アドホックネットワークにおける全てのホストへのルートを、絶えず定期的に計算する。従ってパケットが特定の宛先ホストに送信される必要がある場合、ルートは常に利用可能である。結果は全てのノードのルーティングテーブルに保持される。
【００１６】
各ホストへのルートを維持するために、制御メッセージがルータ間で交換され、ネットワーク構成およびリンク状態の変化を通知する。距離ベクトルおよびリンク状態ルーティングプロトコルは共にプロアクティブプロトコルに区分される。当然のことながら制御メッセージはオーバヘッドとなり、ネットワークの効率を低減させることになる。また、ネットワークトポロジが頻繁に変化する場合、プロアクティブプロトコルは有効なルートを維持することが困難であることがある。
【００１７】
ＤＳＤＶ（宛先順序付け距離ベクトルルーティング）は、ルーティング情報プロトコル（ＲＩＰ）をアドホックネットワークに適応させる距離ベクトルアルゴリズムに基づくプロアクティブルーティングプロトコルである。各ノードはルーティングテーブルを維持し、ルーティングテーブルに次のホップノードおよび到達可能な全ての宛先ホストのそれぞれへのホップ数を格納する。ＤＳＤＶでは、定期的に、またはネットワークトポロジの変化を検出すると、各ノードはルーティングの更新をブロードキャスト、またはマルチキャストする。前回の更新以来の変化に関する情報のみを更新する変化分の更新も使用され、制御情報を削減する。
【００１８】
リアクティブプロトコルは制御メッセージの交換のみを行い、送信すべきデータパケットがあるとルートを見つけ、更新する。送信元ノードがデータパケットの送信を望むと、制御プロトコルを開始し、その近隣ノードにルート要求メッセージを送信してルートを見つける。この原理によると、伝送すべきパケットがない場合、ネットワークリソースが無駄にならないという点で、リアクティブ手法は優れている。しかしながら最初にルートを形成する必要がある場合、パケットの送信に時間を要する。ＡＯＤＶおよびＤＳＲは代表的なリアクティブプロトコルである。
【００１９】
ＡＯＤＶ（アドホックオンデマンド距離ベクトルルーティング）プロトコルはＤＳＤＶアルゴリズムを使用し、オンデマンドベースで、即ち送信元ノードがデータパケットの送信を望む場合にのみルートを構築し、あるいは更新する。これはルートを見つけるあるいは更新するのに必要なブロードキャストの回数の削減に繋がる。
【００２０】
ＡＯＤＶでは、各ノードは検出された近隣ノードのリストを維持する。近隣リストは次の３方法のうち１つにおいて更新される。（ａ）パケットが近隣ノードから受信される場合、（ｂ）近隣ノードからローカルな通知、即ちハローメッセージを受信することによる、（ｃ）リンクレイヤからのフィードバックによる。各ノードからその近隣ノードに自己の所在を知らせるために定期的にハローメッセージがブロードキャストされる。
【００２１】
ＡＯＤＶでは、各ノードは全ての宛先へのルーティングテーブルを維持し、各宛先と通信する、または他のノードのためにデータパケットを転送する。各宛先に対して、ＩＰアドレス、宛先ノードのシーケンス番号、宛先へのホップ数、宛先への次ホップノードおよびルートの存続時間などの宛先に関する情報を含む入力がルーティングテーブルに存在する。
【００２２】
ノードが宛先ノードとの通信を望む、即ち宛先へのデータパケットの送信を望む場合、その場合送信元ノードはルート回復機構を開始し、検出された全ての近隣ノードにルート要求（ＲＲＥＱ）をブロードキャストする。近隣ノードがＲＲＥＱメッセージを受信し、そのルーティングテーブルにその宛先への十分新しいルートの入力があれば、その場合近隣ノードは送信元ノードにルート応答（ＲＲＥＰ）メッセージを返送する。近隣ノードにその宛先に対するルート入力が見あたらなければ、その場合近隣ノードは自体が検出した近隣ノードにＲＲＥＱメッセージを転送する。宛先ノードがＲＲＥＱを受信すると、ＲＲＥＰメッセージを送信元ノードに返送する。
【００２３】
ＲＲＥＱパケットの転送プロセスで、各中間ノードは、ブロードキャストされたＲＲＥＱの第１のコピーを受信する近隣ノードのＩＰアドレスを記録し、近隣ノードのＩＰアドレスにより逆ルートが確立される。後に受信される同じＲＲＥＱメッセージのコピーは全て廃棄される。中間ノードは宛先に対するそのルーティングテーブルに入力を加え、ＲＲＥＰを受信した近隣ノードがその宛先への次ホップノードとして記録される。宛先シーケンス番号およびルートの存続時間はＲＲＥＰからコピーされ、入力に記録される。ＲＲＥＰメッセージが最終的に送信元ノードに返送されると、送信元から宛先への転送ルートが形成される。
【００２４】
ルートに付随するリンクの障害によりルートが利用不可能になっていることをノードが検出すると、ルートを使用する全ての近隣ノードにルートエラー（ｒｏｕｔｅ  ｅｒｒｏｒ、ＲＥＲＲ）メッセージを送信する。ＲＥＲＲメッセージは、送信元ノードに達するまでその近隣ノードに送信し続けられる。次いで、送信元ノードはデータパケットの送信を停止するか、または新規ルートの発見を開始するかを決めることができる。
【００２５】
ＤＳＲ（Ｄｙｎａｍｉｃ  Ｓｏｕｒｃｅ  Ｒｏｕｔｉｎｇ、動的ソースルーティング）プロトコルはソースルーティング機構を使用し、ソースルーティング機構では送信元ノードはオンデマンドベースでルートに沿う完全な複数のノードのシーケンスを決定し、中間ノードのリストをパケットヘッダに設定し、ルートのノードシーケンスを示す。このようにして、各パケットはパケットのルーティングのためにオーバヘッドを運ばなければならない。一方、中間ノードはルートに関する情報をなんら維持する必要はなく、データパケットを配信するときは、ルートを探知することができる。
【００２６】
ＤＳＲでは、各ノードは探知したルートを格納（キャッシュ）する。送信元ノードがデータパケットの宛先ノードへの送信を望み、その宛先に対する入力がキャッシュにない場合、その場合そのリンクレイヤにおけるＲＲＥＱメッセージのブロードキャストによりルート発見機構を起動する。ＲＲＥＱメッセージを受信する各ノードはＲＲＥＱメッセージにそのＩＰアドレスを添付し、次いでそのメッセージをさらに転送する。宛先へのルートが見つけられる、または別のノードが宛先ノードへのルートを与えることができるまで、このプロセスが行われる。次いで、宛先ノードへのネットワークホップシーケンスを含むルート応答（ＲＲＥＰ）メッセージが送信元ノードに返送される。
【００２７】
ＤＳＲでは、あるノードでリンク障害が検出される（即ちパケットが最大回数再送信される）と、そのノードはそのルートキャッシュから該当リンクを除去し、前に確認が受信されているので、該当リンクを使用した各ノードにルートエラー（ＲＥＲＲ）メッセージを送信する。それらのノードは該当リンクを含むルートを除去しなければならない。次いで、送信元ノードからのデータパケットの再送信は転送制御プロトコル（ＴＣＰ）などの上位レイヤにより取り扱われる。
【００２８】
ＴＣＰ／ＩＰプロトコルの１つの問題は、プロトコルがＩＰアドレスのみを使用し、イーサネットまたはトークンリングの例におけるデータリンクでは、ネットワーク構成要素がそれ自体のアドレス付与スキームを有し、このスキームに、データリンクを使用するいずれのネットワークレイヤも準拠しなければならないことである。例えばイーサネットでは、幾つかの異なるネットワークレイヤが同時に協力し、幾つかのネットワークアプリケーションが物理的に同じケーブルを使用することができる。イーサネットのフレーム、即ちパケットが１つの場所から別の場所へ送信されると、パケットの宛先と送信元を判断するのに４８ビットのイーサネットアドレスが使用される。４８ビットの固有のイーサネットアドレスは全てのイーサネットのネットワークを形成するハードウエアにおいて見られ、ＭＡＣ（メディアアクセス制御）アドレスと呼ばれることが多い。この４８ビットのアドレスはＩＰｖ４（インターネットプロトコルバージョン４）で使用される３２ビットのＩＰアドレスと比較することができる。アドレス解決は２つの異なる形式のアドレス間のマッピングスキームを付与する。このマッピングはＡＲＰ（アドレス解決プロトコル）により行われる。ＡＲＰはＡＲＰキャッシュと呼ばれる一時メモリ空間においてハードウエアのＭＡＣアドレスをＩＰアドレスに動的にマッピングする機構を提供する。換言すれば、ＡＲＰはＩＰアドレスをＭＡＣアドレスに翻訳する。
【００２９】
ＡＲＰの基本的動作は次の通りである。ＩＰレイヤがネットワークの別のデバイスとの通信を望むと、ＡＲＰキャッシュを（イーサネットアドレスとの整合の有無を見るために）チェックする。ＡＲＰキャッシュに整合する入力がなければ、ＡＲＰブロードキャストデータグラムが送信され、基本的に「このＩＰアドレスを持つデバイスはそのイーサネットアドレスを応答せよ？」と伝える。（ＩＰアドレスを持つ）受信ステーションはＡＲＰデータグラムにより応答して、「これは自分のＩＰアドレスであり、自分のイーサネットアドレスはこれである」と伝える。ＡＲＰキャッシュは更新され、元のＩＰレイヤ情報はＭＡＣレイヤに渡され、処理される。
【００３０】
このスキームは固定配線ネットワークに対しては良好に動作するが、無線アドホックおよびマルチホップネットワークでは、全てのネットワークユニットが互いに連絡が取れず、この場合標準ＡＲＰの解決では十分ではない。この目的に対しては、ＩＰとＭＡＣアドレスをマッピングする、ある異なるレイヤ２．５のソリューションが開発されている。
【００３１】
レイヤ２と３の間の仲介をする主として２つの異なるルーティングプロトコル、所謂レイヤ２．５プロトコルが存在する。
【００３２】
１．軽量基礎ネットワーク（ＬＵＮＡＲ）。純粋ＡＲＰを使用する代りに、ＡＲＰトラフィックは基礎翻訳ネットワーク（ＳｅｌＮｅｔ）により捕捉され、拡張解決プロトコル（ＸＲＰ）に書き直される。ＸＲＰは標準ＡＲＰよりはるかにリッチな表現セットを可能にする。ＬＵＮＡＲにおいてルートを維持するには、全てのルートが３秒ごとにクリアされ、経路発見手順が再駆動される。
【００３３】
２．レイヤ２ＤＳＲ（最初のバージョン）。ルート発見プロセスでは、ルーティングに使用されるパケットはＡＲＰに類似するが、途中のノードの全てのアドレスが記録される。プロトコルがソースルーティングプロトコルであるので、全ルートもデータパケットの各ヘッダに加えられる。そのようなアドレスの数は制限され、それによりホップ数も制限される。ルートの維持は各送信データパケットの確認（ａｃｋ）のホップバイホップの検出により動作している。確認が得られないと、リンクが障害と考えられ、別のルートが探されるまで、パケットは一定の回数、再送信される。
【００３４】
上記解決法における問題は以下のように要約することができる。
【００３５】
１．標準ＡＲＰは無線ネットワークにおけるローカルなピアツーピアにのみ使用可能である。
【００３６】
２．ネットワークのパケットはアドホックルーティングプロトコルでは標準的には再使用されない。
【００３７】
３．ＬＵＮＡＲプロトコルは総計最大１０から１５ノードのネットワークセルに限られ、最大３ホップに限られる。更新されたマッピングテーブルを保持するために、ＬＵＮＡＲプロトコルがネットワークに満ち溢れることが多く、これは制御トラフィックをさらに増加させることになる。また、マルチホップ機能を可能にするためにＬＵＮＡＲプロトコルは外部のプロトコルを追加して利用する。
【００３８】
４．全てのネットワークアドレスが全てのパケットに格納される（データおよび制御トラフィックパケット双方とも）ので、レイヤ２のＤＳＲは一定数のホップに限られる。この解決法は追加リソースを必要とし、新規ＡＲＰのようなプロトコルが導入される。
【００３９】
従って、上記解決法は標準ＩＰベースのネットワークではトランスペアレントではなく、利用可能なネットワークリソースと関連するルーティングの構成要素の計算能力から余計なリソースを奪う。
【発明の開示】
【発明が解決しようとする課題】
【００４０】
従って、上記の問題および欠点の少なくとも幾つかを軽減することが本発明の好ましい実施形態の１つの目的である。
【００４１】
これは、ＡＲＰメッセージの構成を変えることなくＡＲＰメッセージに新しい特徴を導入することにより行われる。このように、標準ＡＲＰの機能性を使用するネットワークの構成要素はこの新規ＡＲＰメッセージ構成により影響されることはない。一方本発明によるＡＲＰのソリューションを使用するネットワークコンポーネントは効率的なＡＲＰのマッピングを使用することができる。
【課題を解決するための手段】
【００４２】
本発明の１つの好ましい実施形態では、無線マルチホップデータ通信ネットワークの「アドレス解決マッピング」のための方法が提供され、本方法は第１のノードから第２のノードまたは複数のノードにアドレス解決プロトコル（ＡＲＰ）要求をブロードキャストするステップと、第２のノードがＡＲＰ要求を受信して、ＡＲＰメッセージの宛先を判断するステップと、ＡＲＰ要求が第３のノードに向けられると判断されれば、ＡＲＰ要求を送信するステップと、および宛先ネットワークノードから第１のネットワークノードに中間ネットワークノードまたは複数のノードを介してＡＲＰ応答を転送するステップを含む。
【００４３】
さらに本方法はノードにおいて格納され、検出された以前のＡＲＰ要求およびＡＲＰ転送の保留リストを含む。
【００４４】
さらに本方法は、格納された以前のＡＲＰ要求またはＡＲＰ転送の保留リストにおける格納時間を制限し、ノードが特定の宛先へ送信を許されるＡＲＰ転送の割合を制限し、ノード間のリンク品質を測定し、ＡＲＰメッセージ手順の中でノードにリンク品質情報を配信し、ＡＲＰテーブルが更新されるべき時間を判断するためにリンク品質情報を使用し、更新がなされるべきであるかの判断のためにリンク品質情報を閾値と比較し、ＡＲＰ要求の再ブロードキャストまたは転送の前にＡＲＰ要求を変更する、各ステップを含む。
【００４５】
本方法によれば、あるノードがあるノードと通信することができないときに、ＡＲＰエラーメッセージが生成され、ネットワークの受信中のノードに配信されることができる。
【００４６】
本発明の別の実施形態では、通信デバイスが提示され、本デバイスはマルチホップ無線ネットワークにおけるルーティング手段を有し、命令セットメモリ、少なくとも１つのトランシーバ、命令セットメモリにアドレス解決プロトコル（ＡＲＰ）命令を付与する手段および命令セットメモリにＡＲＰメッセージの転送および再ブロードキャスト命令を付与する手段を含む。
【００４７】
本デバイスにおいて、ＡＲＰの転送およびブロードキャストの手段はＡＲＰメッセージの宛先を判断する手段を含むことができる。
【００４８】
本デバイスは、ラップトップ、パーソナルコンピュータ（ＰＣ）、パーソナルディジタルアシスタント（ＰＤＡ）、移動電話機、または組み込みコンピュータなどのクライアントシステムであってよいが、これらに制限されることはなく、またＷＬＡＮ（無線ローカルエリアネットワーク）インフラストラクチャデバイス、および移動電話機インフラストラクチャデバイスなどのインフラストラクチャシステムであってよいが、これらに制限されることはない。
【００４９】
ＡＲＰの転送または再ブロードキャスト命令はメッセージを変更して、ＡＲＰメッセージがメッセージを変更するデバイスから発生するように見えるようにすることができる。
【００５０】
本発明のさらに別の実施形態では、マルチホップ無線データ通信のためのシステムが提示され、本システムは複数の通信デバイスを含み、本通信デバイスは、命令セットメモリ、少なくとも１つの無線トランシーバ、命令セットメモリにアドレス解決プロトコル（ＡＲＰ）命令を付与する手段、命令セットメモリにＡＲＰの転送および再ブロードキャスト命令を付与する手段、および通信デバイスによって構築された通信ネットワークを含む。
【００５１】
データ通信システムにおける通信デバイスはＡＲＰメッセージの宛先を判断する手段をさらに含む。
【００５２】
通信デバイスはクライアントシステム、インフラストラクチャシステム、またはこれら２つのタイプのデバイスの組み合わせであってよい。クライアントシステムの例はラップトップ、パーソナルコンピュータ（ＰＣ）、パーソナルディジタルアシスタント（ＰＤＡ）、移動電話機、または組み込みコンピュータであってよいが、これらに制限されることはない。インフラストラクチャシステムの例はＷＬＡＮ（無線ローカルエリアネットワーク）インフラストラクチャデバイス、および移動電話機インフラストラクチャデバイスであってよいが、これらに制限されることはない。
【００５３】
システムは、インターネットまたは私設ＩＰネットワークなどの外部ネットワークに接続された少なくとも１つのゲートウエイをさらに含むことができる。
【００５４】
本発明は、無線マルチホップデータ通信ネットワークにおける「アドレス解決マッピング」のための命令セットにも関係し、本命令セットは、第１のネットワークノードから第２のノードにアドレス解決プロトコル（ＡＲＰ）要求をブロードキャストする第１の命令セット、ＡＲＰ要求を受信し、ＡＲＰメッセージの宛先を判断するための第２のノードにおける第２の命令セット、ＡＲＰ要求が第３のノードに向けられると判断されれば、ＡＲＰ要求を送信する第３の命令セット、および第３のノードから第１のネットワークノードに第２のノードを介してＡＲＰ応答を転送する第４の命令セットを含む。
【００５５】
以下では、本発明を非制限的方法において、包含する図面に示される例示的実施形態を参照してより詳細に記載する。
【発明を実施するための最良の形態】
【００５６】
本発明は移動アドホックネットワークの概念に関する。その概念においては、移動ノードにより自律的に組織する無線ネットワークは、いわゆるマルチホップルーティングシステムを使用して、互いに通信する。ノードはホストまたはクライアントシステムおよびルータ、即ちインフラストラクチャデバイスの両方として動作する。トラフィックはノードを介してルーティングされ、必要であれば、外部ＩＰネットワーク、例えばインターネットへのアクセスを有する外部ゲートウエイにルーティングされる。
【００５７】
本発明では、ＡＲＰ（アドレス解決プロトコル）に対する新しい解決法が提示される。その解決法では、ＡＲＰメッセージはＡＲＰ要求ノードとＡＲＰメッセージの最終受信者との間の経路に位置する中間ノードを使用して、受信ノードに転送される。
【００５８】
図１には、マルチホップ無線ネットワークの幾つかのネットワークノード１０１、１０２、１０３、および１０４が示されている。ノード１０１、１０２、１０３、および１０４は互いに通信するが、全てのノードが互いに接点を有するわけではない。これはある状況では、幾つかのノードはメッセージを中継し、ルーティングエレメントとして動作することを意味する。例えば、ノード１０１がノード１０４との通信を望めば、ノード１０１および１０４はこの状況では直接互いに「聞く」、即ち互いに直接通信することはできないので、ノード１０２またはノード１０２および１０３はパケットの処理に絡む必要がある。
【００５９】
メッセージが１つのノードから別のノードへ送信される場合、ノードのネットワークアドレスを解決する必要がある。本発明では、新しいＡＲＰ手順が提案されており、その提案では、新規ＡＲＰメッセージが加えられ、ＡＲＰを転送または再ブロードキャストするようにＡＲＰメッセージ構成の変更を可能にする。これは、ＡＲＰ要求が探し当てる宛先に到達するまで、互いのネットワークアドレスを知る必要のある２つのノードの間にあるノードがそのようなＡＲＰ要求を転送することを意味する。
【００６０】
図１によりノード１０１がノード１０４との通信を望むものとしてステップごとの概要手順によりこのことを説明する。
【００６１】
１．ノード１０１はノード１０４へのデータの送信を希望する。
【００６２】
２．ノード１０１はＡＲＰ要求「１０４が誰かを１０１に告げよ？」を自動的にブロードキャストする。
【００６３】
３．このメッセージは隣接ノード１０２により受信され、ノード１０２は要求「１０４が誰かを１０２に告げよ？」を直ちに再ブロードキャストする。
【００６４】
４．この要求は隣接ノード１０３により受信され、ノード１０３は要求「１０４が誰かを１０３に告げよ？」を再ブロードキャストする。しかしながらこの特定の場合には、要求はノード１０４によっても受信され、ノード１０４は「ノード１０２よ、私が１０４である」の送信により応答する。
【００６５】
５．ノード１０３によって送信された要求はノード１０４によって受信され、ノード１０４は「ノード１０３よ、私が１０４である」の送信により応答する。
【００６６】
６．ノード１０４からノード１０２への応答はノード１０２によって受信される。
【００６７】
７．ノード１０２は要求元（ノード１０１）にＡＲＰ転送「ノード１０１よ、ノード１０４へのゲートウエイとしてノード１０２を使用せよ」の送信により応答する。
【００６８】
８．ノード１０４からノード１０３への応答はノード１０３により受信される。ノード１０３は「ノード１０２よ、ノード１０４へのゲートウエイとしてノード１０３を使用せよ」の送信によりノード１０２に応答する。
【００６９】
図２に示されるように別の例では、３つのノード（２０１、２０２、２０３）が小さなネットワークにおいて接続されている。ノード２０１はノード２０３との通信を望むが、直接そうすることはできない。一方ノード２０２は、ノード２０１とノード２０３との間のメッセージを中継することができるように位置している。図２で、ノード２０１は、一般にｐｉｎｇと呼ばれるＩＣＭＰ（インターネット制御メッセージプロトコル）のエコー要求のノード２０３への送信を希望する。図２のメッセージボックス２０５、２０７、２１１、および２１３は、本発明によるノード間で通信される新規メッセージタイプを示している。
【００７０】
１．ノード２０１がその通信手順を開始すると、まず通信を望むＩＰ番号の位置を尋ねるＡＲＰメッセージを送信する。
【００７１】
２．このＡＲＰ要求はノード２０２により受信される。ノード２０２は、メッセージが自分とは別のノード宛であると判断する。メッセージはノード２０２から来るように見えるように変更され、ボックス２０５に示すようにノード２０２により再ブロードキャストされる。
【００７２】
３．メッセージはノード２０３により受信され、ＡＲＰ応答がノード２０２に送信され（ボックス２０６）、ノード２０２はノード２０１へＡＲＰ応答を転送する（ボックス２０７）。
【００７３】
４．次いで、ノード２０１はノード２０３の座標位置を有し、ＩＣＭＰ要求をノード２０３に送信し（ボックス２０８）、ＩＣＭＰ要求はノード２０２により中継される（ボックス２０９）。
【００７４】
５．ノード２０３はＩＣＭＰ要求を受信し、次いでＩＣＭＰ応答の送信を望む。しかしながら応答を送信するためには、ノード２０３はノード２０１のＭＡＣアドレスを知る必要があり、それ故ノード２０１に対するＡＲＰ要求を送信する。これはボックス２１０に示されている。
【００７５】
６．このメッセージはノード２０２により受信される。ノード２０２は、メッセージが自分とは別のノード宛であると判断する。メッセージはノード２０２から来るように見えるように変更され、ボックス２１１に示すようにノード２０２により再ブロードキャストされる。
【００７６】
７．メッセージはノード２０１により受信され、ＡＲＰ応答がノード２０２に送信され（ボックス２１２）、ノード２０２はノード２０３へ応答を転送する（ボックス２１３）。
【００７７】
８．次いで、ノード２０３はノード２０１の座標位置を有し、ＩＣＭＰ応答を送信し（ボックス２１４）、ＩＣＭＰ応答はノード２０１へノード２０２により中継され（ボックス２１５）、ＩＣＭＰ通信手順は終了する。
【００７８】
上記の通信方法はＩＣＭＰエコー要求により示されたが、本発明の範囲では任意のタイプの通信手順、プロトコル、またはスキームを使用することができることは当業者により当然ながら理解されるはずである。４以上のノードが通信ネットワークおよびトラフィックの処理に含まれることができることも当業者は当然ながら理解するはずである。
【００７９】
上記のメッセージは全ての部分が標準ＡＲＰ手順ではない。しかしながら動作コード（ｏｐ）フィールドを使用することにより、非標準メッセージであっても標準メッセージに組み込むことができる。このようにして標準ＡＲＰ要求に準拠するルーティングエレメントは本発明の新規ＡＲＰ転送スキームを使用するルーティングエレメントにより作成されたＡＲＰ要求を取り扱うことができる。標準ルーティングエレメントはそのような新規ＡＲＰメッセージタイプのみを無視する。本発明の新規ＡＲＰ転送スキームを取り扱うことができる変更されたルーティングエレメントは、ｏｐフィールドに含まれる新規コードを使用することができる。ｏｐフィールドは、送信または受信するメッセージタイプを規定する。それ故ＡＲＰ転送スキームを実装するために、ＡＲＰ標準を変更する必要はない。アドレス解決プロトコルのｏｐフィールドにおいて使用される正規メッセージタイプは、ＡＲＰ要求、ＡＲＰ応答、ＲＡＲＰ要求、およびＲＡＲＰ応答を含む。本発明の提案する新規メッセージタイプは、ＡＲＰ転送、ＡＲＰエラー、およびＡＲＰリンク品質を含む。例として以下の表１に、イーサネットメッセージシステムにおける３つの異なるＡＲＰメッセージタイプとそのそれぞれの内容および伝送ヘッダを示す。表１Ａは標準ＡＲＰ要求メッセージを示し、表１Ｂは本発明によるＡＲＰ応答メッセージを示し、表１Ｃは本発明によるＡＲＰ転送メッセージを示す。メッセージに含まれる実際の情報は表１Ａから表１Ｃの表の右側に示され、タイプ、ハードウエアタイプ、プロトコルタイプ、および動作コードフィールドには記述用語および実際に送信される１６進コード（カッコ内に）の両者が示される。
【００８０】
【表１Ａ】
2007532058.tif 000003
【００８１】
【表１Ｂ】
2007532058.tif 000004
【００８２】
【表１Ｃ】
2007532058.tif 000005
【００８３】
新規タイプのＡＲＰメッセージタイプについて次に説明する。
【００８４】
ＡＲＰ転送：このタイプがＡＲＰメッセージのｏｐフィールドに含まれれば、本発明による実装に伴ういずれのルーティングデバイスも、このメッセージがＡＲＰ転送メッセージであることが分かり、これをＡＲＰ応答としてメッセージの扱いにある相違を持って取り扱う。この扱いが本発明に導入されるＡＲＰ転送スキームの実装における機能でもある。この機能により複数のルートを複数のノードに中継する。メッセージは最終宛先および最終宛先への直近のホップを含む。
【００８５】
ノードが或るノードと通信することができないことがわかると、ＡＲＰエラーが生成される。これは、ノードが探し求めるノードへの代替ルートを見出すことができない場合に生成される。ＡＲＰエラーメッセージは（隣接ノード、即ち単一ホップの隣へ）ブロードキャストされ、エラーメッセージを生成したノードおよび到達しえないノードに関する情報を含む。ＡＲＰエラーを起こすノードはエラーを起こすノードを含むルートおよびエラーを起こすノードがゲートウエイとして動作する全てのルートへの入力を全て除去する。ブロードキャストされたＡＲＰエラーメッセージの受信者はエラーを起こすノードを含む全てのアクティブルートを除去する。受信ノードに代替ルートがなければ、ＡＲＰエラーメッセージが生成され、ブロードキャストされる。
【００８６】
ＡＲＰリンク品質メッセージは２つのノード間のリンク品質に関する情報を含む。
【００８７】
中間ノードにより再ブロードキャストされたメッセージが連鎖して、通信する以前のノードにより受信されることもまた考慮されるべきである。図２の例でノード２０２がＡＲＰ要求を再ブロードキャストすると、ノード２０１は同じメッセージを受信する。制御トラフィック量を削減するために、各ノードは各要求を記憶し、各ノードにおいて保留リストをローカルに格納することにより応答する。ＡＲＰ要求の転送の前に最近の要求および応答に関するこのリストを見ることにより、ノードはネットワークインフラストラクチャにブロードキャストされる制御トラフィック量を削減することができる。受信メッセージが既に保留リストに設定されたノードに関するものであると判断されれば、そのメッセージは廃棄される。応答が受信され、応答が別のノードに転送されていれば、この保留リストにはどのノードがどのノードを探しているか、いつその要求がなされたかに関する情報が格納される。
【００８８】
この解決法では、ノードが特定ノード宛ての要求をどれだけ速く再ブロードキャストできるかに関する時間制限を導入することも可能である。ある要求が２以上の異なる経路を通り、あるノードで受信されると、その要求は２回以上転送されない。これは、時間制限以内でしかノードが特定ノードへの要求の転送を認めないことにより解決される。逆に、再ブロードキャストが送信されたことがないかぎり、ＡＲＰ応答または転送は一度だけそれぞれの発生もとへの送信が認められる。
【００８９】
本発明はＡＲＰ標準を変更しないので、特別なＡＲＰ開始ルーティンは必要ではない。一方本発明の別の実施形態では、リンク品質監視システムが上記のＡＲＰソリューションと共に導入され、制御トラフィック量をさらに削減し、トラフィック速度を増大させることができる。ノード間のリンク品質、例えば無線品質、確認情報、ビットエラー率、または（例えば伝送制御プロトコル（ＴＣＰ）からの）データ速度のスループットを測定することにより、リンク品質の低下の検出や、積極的なＡＲＰのリスティングの更新が可能である。そのようなスキームはデータパケットのロス量を削減することができ、インフラストラクチャの制御トラフィック量を削減する。（参照により本明細書に組み込まれる）ＰＣＴ／ＳＥ０３／００２０７４では、アドホックネットワークにおけるリンク品質調査のための類似のスキームが導入され、参照により本明細書に組み込まれている。同じシステムがＡＲＰテーブルの更新時期の決定に使用されることができる。
【００９０】
本発明によるＡＲＰの実装における制御可能なパラメータはノードのＡＲＰ要求送信可能回数、保留リストにおける入力の有効時間およびＡＲＰルーティングテーブルに格納されたルーティング入力が使用されることなくＡＲＰルーティングテーブルに残存を許される時間長を含むが、これに制限されることはない。
【００９１】
応答が他のノードから受信されれば、受信ノードは要求ノードへ応答を送信することができるように、要求は受信ノードに格納される。
【００９２】
ノードは任意の計算デバイスであってよく、ラップトップ、パーソナルディジタルアシスタント（ＰＤＡ）、組み込みコンピュータ、または移動電話機を含むが、これに制限されることはない。そのようなデバイスは少なくとも１つの無線トランシーバおよびアドレス解決プロトコル命令およびアドレス解決プロトコルの転送および再ブロードキャスト命令を取り扱うプログラミングコードを有する命令セットメモリを含む。デバイスは命令セットメモリに本発明によるメッセージの最終宛先を判断する手段およびＡＲＰメッセージを変更する手段も含む。
【００９３】
本発明は、例えば災害エリアのネットワーク設定または戦場における軍事ネットワークの設定におけるなど、外部接続が提供されない独立ネットワーク、および共に接続された無線構成要素群であって、該群に少なくとも１つの外部ネットワーク（例えばインターネットまたは独立ＩＰネットワーク）への接続がある場合の両方に使用することができる。後者の実施形態を図４に示す。複数の無線構成要素６０２、．．．、６０ｎ（ｎは整数）は外部ネットワーク、例えばインターネットへの接続を有するゲートウエイ６０７に接続される。外部接続６００は任意のタイプであってよく、固定有線接続（例えばイーサネット、光ファイバ、または同類のもの）、または固定無線（例えばＬＭＤＳ）を含むがこれに制限されることはない。
【００９４】
通信スキームは使用する無線コーディングスキームに独立であり、任意の無線タイプを使用することができる。タイプとしては例えば、ＩＥＥＥ８０２．１１シリーズ（例えばＩＥＥＥ８０２．１１ａ、ＩＥＥＥ８０２．１１ｂ、ＩＥＥＥ８０２．１１ｇなど）ＩＥＥＥ８０２．１５、ＩＥＥＥ８０２．１６、ハイパーＬＡＮ、ホームＲＦ、ブルトゥース、ＩＲ（赤外線）、ＵＷＢ（超広帯域）、ＪＴＲＳ（共同戦術無線システム）、３Ｇ（第３世代移動通信）、ＧＰＲＳ（汎用パケット無線サービス）、ＥＤＧＥ（グローバル拡張版向けの高速データレート）のような無線規格がある。しかしながら、可能な無線規格は上記のものに限られない。１００ｋｈｚから１００ｐＨｚの周波数帯域内で動作する任意の適する電磁的放射ベースの伝送スキームであってよく、これは無線周波数、マイクロ波周波数、および赤外、可視および紫外領域の周波数を含む。
【００９５】
本発明によるＡＲＰの方法は多くの異なるアプリケーション領域で使用することができる。領域としては例えば一般的に警察または特別なイベント中、災害または事故における救助隊、戦場または訓練における軍隊、または住宅および商用ネットワークアクセスの両方のための通信目的の無線アクセス領域の構築などがある。例えば、他の広帯域アクセス技術が殆ど無い、または接続するには高価でありすぎる住宅領域において、これらのアドホックネットワークを使用してショートレンジ、低コスト、無線装置を使用する広帯域アクセスを構築することができる。本方法は商業地域において、企業または小さな会社に広帯域アクセスを提供するために、または所謂ホットスポットにおける無線接続に使用することもできる。ホットスポットは、一定のエリア、例えば空港のラウンジまたはホテルにおいてビジネスモデルに応じて有料の顧客にまたは無料で通信アクセスを提供することを特徴とする。
【００９６】
以上の例では３または４つのノードが本発明を示すために使用されたが、このようなネットワークの設置にはノードの数はより多くも少なくも使用することができることは当然のことながら当業者により理解される。含まれるノードの数には特別な制限は無い。
【００９７】
本発明は説明のために詳細に記載されたが、このような詳細さはただ説明のためであって、添付の特許請求の範囲によって制限されうる場合を除いて、本発明の精神と範囲を逸脱することなく変形が本明細書で当業者によりなされうることは理解される。
【図面の簡単な説明】
【００９８】
【図１】小さなマルチホップネットワークの概要を示す図である。
【図２】小さなマルチホップネットワークを介する種々の通信メッセージのフロー図である。
【図３】ＡＲＰメッセージのメッセージ構成の概要を示す図である。
【図４】固定ネットワークと接続される大きなマルチホップ無線ネットワークの概要を示す図である。
【図１】
2007532058.tif 000006
【図２】
2007532058.tif 000007
【図３】
2007532058.tif 000008
【図４】
2007532058.tif 000009
【国際調査報告】
2007532058.tif 000010
2007532058.tif 000011
2007532058.tif 000012