(57)【要約】  ノードが他のノード（１０６，４０２，４０４，４０６，４０８）から受信されるパケットのルーティングを行うルータとして動作することが不可能な場合にも、全てのノード（１０６，４０２，４０４，４０６，４０８）が互いへの経路を見出すことを可能とする、無線ネットワーク（４００）においてデータのルーティングを行うための方法及びシステムに関する。パケットルーティングの実行可能なメッシュノード（１０６，４０２）は、それらの関連する非メッシュノード（ＳＴＡ１３〜ＳＴＡ１５）のプロキシノードとして働き、それらの関連する非メッシュノード（ＳＴＡ１３〜ＳＴＡ１５）から宛先ノードへのパケットのルーティングを行う。さらに、一部のメッシュノードはインテリジェントアクセスポイント（１０６）として動作し、非メッシュノード及び他のメッシュノードに、インターネット（４０２）など他のネットワークに対するアクセスを提供する。
2008512901.tif 000002
【特許請求の範囲】
【請求項１】
無線通信ネットワークにおいてパケットの通信を行うための方法であって、
ネットワークにおいてパケットの通信を行うように適合されている複数の非メッシュノードを提供する非メッシュノード提供工程と、
少なくとも１つのメッシュノードを提供するメッシュノード提供工程と、
メッシュノードを、ネットワークにおいてパケットの通信を行い、かつ、メッシュノードに関連する非メッシュノードのプロキシとして機能するように動作させ、ネットワークにおいて関連する非メッシュノードから他の非メッシュノード及び他のメッシュノードへパケットをルーティングするパケットルーティング工程と、からなる方法。
【請求項２】
メッシュノード提供工程は１つ以上のメッシュノードがインテリジェントアクセスポイントである複数のメッシュノードを提供することと、
インテリジェントアクセスポイントを、他のメッシュノード及び他のメッシュノードに関連する非メッシュノードに別のネットワークへのアクセスを提供するように動作させる工程を含むことと、を含む請求項１に記載の方法。
【請求項３】
非メッシュノードが宛先ノードへパケットを送信する送信元ノードとして動作するとき、メッシュノードを、非メッシュノードが関連付けられているインテリジェントアクセスポイントへプローブメッセージを送信する非メッシュノードのプロキシとして動作させ、宛先ノードを特定する工程と、
メッシュノードが宛先ノードへパケットを送信する送信元ノードとして動作するとき、送信元ノードを、送信元ノードが関連付けられているインテリジェントアクセスポイントへプローブメッセージを送信するように動作させ、宛先ノードを特定する工程と、を含む請求項２に記載の方法。
【請求項４】
送信元が非メッシュノードであり、かつ、インテリジェントアクセスポイントがプローブメッセージを受信するとき、インテリジェントアクセスポイントを、宛先ノードを特定し、送信元ノードのプロキシとして働くメッシュノードへプローブ応答メッセージを送信するように動作させ、インテリジェントアクセスポイントがネットワーク上の宛先ノードを特定したか否かをプロキシメッシュノードに通知する工程と、
送信元ノードがメッシュノードであり、かつ、インテリジェントアクセスポイントがプローブメッセージを受信するとき、インテリジェントアクセスポイントを、宛先ノードを特定し、送信元ノードへプローブ応答メッセージを送信するように動作させ、インテリジェントアクセスポイントがネットワーク上の宛先ノードを特定したか否かを送信元ノードに通知する工程と、を含む請求項３に記載の方法。
【請求項５】
インテリジェントアクセスポイントを、宛先ノードがメッシュノード及び非メッシュノードのうちのいずれであるかを示す情報をプローブ応答メッセージに含めるように動作させる工程と、宛先ノードが非メッシュノードである場合、情報は宛先ノードのプロキシとなっているメッシュノードのアドレスを含むことと、を含む請求項４に記載の方法。
【請求項６】
送信元ノードが非メッシュノードであり、かつ、プローブ応答メッセージ中の情報は宛先ノードがメッシュノードであることを示すとき、インテリジェントアクセスポイントが宛先ノードを特定したことを示すインテリジェントアクセスポイントからのプローブ応答メッセージに応答して、送信元ノードが関連付けられているプロキシメッシュノードを、プロキシメッシュノードから宛先ノードへの経路を特定するように動作させる工程と、
送信元ノードが非メッシュノードであり、かつ、プローブ応答メッセージ中の情報は宛先ノードが非メッシュノードであることを示すとき、インテリジェントアクセスポイントが宛先ノードを特定したことを示すインテリジェントアクセスポイントからのプローブ応答メッセージに応答して、送信元ノードが関連付けられているプロキシメッシュノードを、プロキシメッシュノードから宛先ノードのプロキシとして働くメッシュノードへの経路を特定するように動作させる工程と、を含む請求項５に記載の方法。
【請求項７】
送信元ノードがメッシュノードであり、かつ、プローブ応答メッセージ中の情報は宛先ノードがメッシュノードであることを示すとき、インテリジェントアクセスポイントが宛先ノードを特定したことを示すインテリジェントアクセスポイントからのプローブ応答メッセージに応答して、送信元を、送信元から宛先ノードへの経路を特定するように動作させる工程と、
送信元ノードがメッシュノードであり、かつ、プローブ応答メッセージ中の情報は宛先ノードが非メッシュノードであることを示すとき、インテリジェントアクセスポイントが宛先ノードを特定したことを示すインテリジェントアクセスポイントからのプローブ応答メッセージに応答して、送信元ノードを、送信元ノードから宛先ノードのプロキシとして働くメッシュノードへの経路を特定するように動作させる工程と、を含む請求項５に記載の方法。
【請求項８】
宛先ノードがインテリジェントアクセスポイントに関連付けられていないとインテリジェントアクセスポイントが判定するとき、宛先ノードが別のインテリジェントアクセスポイントに関連付けられているか否かを判定するようにインテリジェントアクセスポイントを動作させる工程を含む請求項４に記載の方法。
【請求項９】
各メッシュノードに関連する非メッシュノードを識別するそれぞれの関連テーブルを作成するように各メッシュノードを動作させる工程と、
インテリジェントアクセスポイントに結合されているメッシュノードと、結合されているメッシュノードがプロキシとなっている非メッシュノードとを識別する結合テーブルを維持するようにインテリジェントアクセスポイントを動作させる工程と、を含む請求項２に記載の方法。
【請求項１０】
ルーティングメッセージから取得される、他のメッシュノード及び他のメッシュノードのそれぞれに関連する非メッシュノードに関する情報を維持するように、各メッシュノードを動作させる工程を含む請求項９に記載の方法。
【請求項１１】
メッシュノードが距離ベクトルルーティングを実行するように適合されているとき、メッシュノードに関連付けられている任意の非メッシュノードを識別する情報を経路要求に含めるようにメッシュノードを動作させる工程と、
メッシュノードがリンクステートルーティングを実行するように適合されているとき、メッシュノードに関連付けられている任意の非メッシュノード及びメッシュノードの近傍の任意の他のメッシュノードに関連付けられている非メッシュノードを識別する情報を経路要求に含めるようにメッシュノードを動作させる工程と、を含む請求項１に記載の方法。
【請求項１２】
ネットワークにおいてパケットの通信を行うように適合されている複数の非メッシュノードと、
ネットワークにおいてパケットの通信を行い、かつ、関連する非メッシュノードのプロキシとして動作して、ネットワークにおいて関連する非メッシュノードから他の非メッシュノード及び他のメッシュノードへパケットをルーティングする少なくとも１つのメッシュノードと、からなる無線通信ネットワーク。
【請求項１３】
他のメッシュノード及び他のメッシュノードに関連する非メッシュノードに別のネットワークへのアクセスを提供するように適合されている複数のメッシュノードと、複数のメッシュノードのうちの１つ以上はインテリジェントアクセスポイントであることと、を含む請求項１２に記載の無線通信ネットワーク。
【請求項１４】
メッシュノードは、非メッシュノードが関連付けられているインテリジェントアクセスポイントへプローブメッセージを送信し宛先ノードを特定するようメッシュノードが適合されるように、宛先ノードへパケットを送信するように動作する非メッシュノードのプロキシとして動作するように適合されていることと、
宛先ノードへパケットを送信するように動作するメッシュノードは、メッシュノードが関連付けられているインテリジェントアクセスポイントへプローブメッセージを送信し、宛先ノードを特定するように適合されていることと、を含む請求項１３に記載の無線通信ネットワーク。
【請求項１５】
インテリジェントアクセスポイントは、非メッシュノード送信元ノードから受信されるプローブメッセージに応答して、宛先ノードを特定し、非メッシュ送信元ノードのプロキシとして働くメッシュノードへプローブ応答メッセージを送信して、インテリジェントアクセスポイントがネットワーク上の宛先ノードを特定したか否かをプロキシメッシュノードに通知するように適合されていることと、
インテリジェントアクセスポイントは、メッシュ送信元ノードから受信されるプローブメッセージに応答して、宛先ノードを特定し、メッシュ送信元ノードへプローブ応答メッセージを送信して、インテリジェントアクセスポイントがネットワーク上の宛先ノードを特定したか否かをメッシュ送信元ノードに通知するように適合されていることと、を含む請求項１４に記載の無線通信ネットワーク。
【請求項１６】
インテリジェントアクセスポイントは宛先ノードがメッシュノード及び非メッシュノードのうちのいずれであるかを示す情報をプローブ応答メッセージに含めるように適合されていることと、宛先ノードが非メッシュノードである場合、情報は宛先ノードのプロキシとなっているメッシュノードのアドレスを含むことと、を含む請求項１５に記載の無線通信ネットワーク。
【請求項１７】
非メッシュ送信元ノードが関連付けられているプロキシメッシュノードは、メッシュノードである宛先ノードをインテリジェントアクセスポイントが特定したことを示すプローブ応答メッセージ中の情報に応答して、プロキシメッシュノードから宛先ノードへの経路を特定するように適合されていることと、
メッシュ送信元ノードが関連付けられているプロキシメッシュノードは、非メッシュノードである宛先ノードをインテリジェントアクセスポイントが特定したことを示すプローブ応答メッセージに応答して、プロキシメッシュノードから宛先ノードのプロキシとして働くメッシュノードへの経路を特定するように適合されていることと、を含む請求項１６に記載の無線通信ネットワーク。
【請求項１８】
メッシュ送信元ノードは、メッシュノードである宛先ノードをインテリジェントアクセスポイントが特定したことを示すプローブ応答メッセージ中の情報に応答して、メッシュ送信元ノードから宛先ノードへの経路を特定するように適合されていることと、
メッシュ送信元ノードは、非メッシュノードである宛先ノードをインテリジェントアクセスポイントが特定したことを示すインテリジェントアクセスポイントからのプローブ応答メッセージに応答して、メッシュ送信元ノードから宛先ノードのプロキシとして働くメッシュノードへの経路を特定するように適合されていることと、を含む請求項１６に記載の無線通信ネットワーク。
【請求項１９】
宛先ノードがインテリジェントアクセスポイントに関連付けられていないとインテリジェントアクセスポイントが判定するとき、宛先ノードが別のインテリジェントアクセスポイントに関連付けられているか否かをインテリジェントアクセスポイントが判定するように適合されていることを含む請求項１５に記載の無線通信ネットワーク。
【請求項２０】
メッシュノードは各々、メッシュノードに関連する非メッシュノードを識別するそれぞれの関連テーブルを作成するように適合されていることと、インテリジェントアクセスポイントは、インテリジェントアクセスポイントに結合されているメッシュノードと、結合されているメッシュノードがプロキシとなっている非メッシュノードとを識別する結合テーブルを維持するように適合されていることと、を含む請求項１３に記載の無線通信ネットワーク。
【請求項２１】
メッシュノードは各々、ルーティングメッセージから取得される、他のメッシュノード及び他のメッシュノードのそれぞれに関連する非メッシュノードに関する情報を維持するように適合されていることを含む請求項２０に記載の無線通信ネットワーク。
【請求項２２】
メッシュノードは、メッシュノードがメッシュノードに関連付けられている任意の非メッシュノードを識別する情報を経路要求に含めるように適合されている距離ベクトルルーティングと、メッシュノードがメッシュノードに関連付けられている任意の非メッシュノード及びメッシュノードの近傍の任意の他のメッシュノードに関連付けられている非メッシュノードを識別する情報を経路要求に含めるように適合されているリンクステートルーティングとのうちの１つ以上を実行するように適合されていることを含む請求項１２に記載の無線通信ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワークにおいてデータのルーティングを行うためのシステム及び方法に関する。
【背景技術】
【０００２】
近年、「アドホック（ａｄ−ｈｏｃ）」ネットワークとして知られるタイプのモバイル通信ネットワークが開発されている。このタイプのネットワークでは、各モバイルノードは他のモバイルノードの基地局又はルータとして動作することが可能であるため、基地局の固定インフラストラクチャの必要性が除かれる。当業者には理解されるように、ネットワークノードは時分割多元接続（ＴＤＭＡ）方式、符号分割多元接続（ＣＤＭＡ）方式、又は周波数分割多元接続（ＦＤＭＡ）方式などの多重化方式により、データパケット通信の送受信を行う。
【０００３】
より精巧なアドホックネットワークも開発されている。それらのネットワークでは、従来のアドホックネットワークと同様にモバイルノードが互いに通信を行うことが可能であるほか、モバイルノードが固定ネットワークにアクセスすることが可能であるため、公衆交換電話網（ＰＳＴＮ）上のノードや、インターネットなど他のネットワーク上のノードなど、他のモバイルノードとの通信が可能である。それらの進歩したタイプのアドホックネットワークの詳細は、「Ａｄ  Ｈｏｃ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ａｃｃｅｓｓ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅｄ  ｔｏ  ｔｈｅ  ＰＳＴＮ  ａｎｄ  Ｃｅｌｌｕｌａｒ  Ｎｅｔｗｏｒｋｓ」と題する２００１年６月２９日に出願の特許文献１、「Ｔｉｍｅ  Ｄｉｖｉｓｉｏｎ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  ａｎ  Ａｄ−Ｈｏｃ，  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｒａｄｉｏ  Ｎｅｔｗｏｒｋ  Ｈａｖｉｎｇ  Ｃｏｏｒｄｉｎａｔｉｎｇ  Ｃｈａｎｎｅｌ  Ａｃｃｅｓｓ  ｔｏ  Ｓｈａｒｅｄ  Ｐａｒａｌｌｅｌ  Ｄａｔａ  Ｃｈａｎｎｅｌｓ  ｗｉｔｈ  Ｓｅｐａｒａｔｅ  Ｒｅｓｅｒｖａｔｉｏｎ  Ｃｈａｎｎｅｌ」と題する２００１年３月２２日に出願の特許文献２、及び、「Ｐｒｉｏｒｉｔｉｚｅｄ−Ｒｏｕｔｉｎｇ  ｆｏｒ  ａｎ  Ａｄ−Ｈｏｃ，  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ，  Ｍｏｂｉｌｅ  Ｒａｄｉｏ  Ａｃｃｅｓｓ  Ｓｙｓｔｅｍ」と題する２００１年３月２２日に出願の特許文献３に記載されている。各々の全内容を引用によって本明細書に援用する。
【０００４】
今日の無線規格のほとんどは、アクセスポイント（又は、マスタノード）と呼ばれる１つのノードが局（又は、スレーブノード）と通常呼ばれる他のノードに対する通信を提供する、スタートポロジを有するネットワークに関する。通常、局はアクセスポイントに「関連付けられている（ａｓｓｏｃｉａｔｅｄ  ｗｉｔｈ）」ものとして説明される。通常、アクセスポイント又はマスタノードは、他のアクセスポイント又はマスタノードや、インターネットの他の部分に接続される。
【特許文献１】米国特許出願第０９／８９７，７９０号明細書
【特許文献２】米国特許第６，８０７，１６５号明細書
【特許文献３】米国特許第６，８７３，８３９号明細書
【発明を実施するための最良の形態】
【０００５】
ここで説明するように、本発明では、無線ネットワーク、詳細には、アドホックなマルチホッピング無線ネットワークにおける全てのノードが、パケットのルーティングに関与しない場合にも、互いのノードに対する経路を見出すことを可能とするシステム及び方法を提供する。
【０００６】
図１は、本発明の一実施形態を用いるアドホックなパケット交換無線通信ネットワーク１００の一例を示すブロック図である。詳細には、ネットワーク１００は、複数のモバイル無線ユーザ端末１０２−１〜１０２−ｎ（一般に、ノード１０２又はモバイルノード１０２と呼ぶ）を含み、必須ではないが、固定ネットワーク１０４を含み得る。固定ネットワーク１０４は、ノード１０２に固定ネットワーク１０４へのアクセスを提供するための複数のインテリジェントアクセスポイント（ＩＡＰ）１０６−１，１０６−２，．．．，１０６−ｎ（一般に、ノード１０６、インテリジェントアクセスポイント１０６、又はＩＡＰ１０６と呼ぶ）を有する。固定ネットワーク１０４は、例えば、中核のローカルアクセスネットワーク（ＬＡＮ）と、他のアドホックネットワーク、公衆交換電話網（ＰＳＴＮ）及びインターネットなど他のネットワークへのアクセスをネットワークノードに提供するための複数のサーバ及びゲートウェイルータとを含むことが可能である。ネットワーク１００は、さらに、他のノード１０２，１０６，１０７間でデータパケットのルーティングを行うための、複数の固定ルータ１０７−１〜１０７−ｎを含み得る。なお、本明細書の説明では、上述のノードを集合的に「ノード１０２，１０６，１０７」と呼ぶことや、単に「ノード」と呼ぶことがある。
【０００７】
当業者には理解されるように、ノード１０２，１０６，１０７は直接的に、或いは、Ｍａｙｏｒによる米国特許第５，９４３，３２２号明細書及び上述の特許文献１〜３に記載のようにノード間でパケットを送信するための１つ以上のルータとして動作する１つ以上の他のノード１０２，１０６，又は１０７を介して、互いに通信を行うことが可能である。図２に示すように、各ノード１０２，１０６，１０７は、送受信機、即ち、モデム１０８を備える。モデム１０８はアンテナ１１０へ結合されており、コントローラ１１２の制御下で、ノード１０２，１０６又は１０７との間で、パケット化された信号などの信号を送受信することが可能である。パケット化されたデータ信号は、例えば、音声、データ又はマルチメディア情報や、ノード更新情報を含むパケット化された制御信号を含む。
【０００８】
さらに、各ノード１０２，１０６，１０７は、特に、ネットワーク１００において自身及び他のノードに関するルーティング情報を記憶することの可能な、ランダムアクセスメモリ（ＲＡＭ）などのメモリ１１４を備える。図２にさらに示すように、一定のノード、詳細には、モバイルノード１０２は、ノートブックコンピュータ端末、モバイル電話ユニット、モバイルデータユニット、又は任意の他の適切なデバイスなど、任意の数のデバイスから構成され得るホスト１１６を備えることが可能である。また、各ノード１０２，１０６，１０７は、インターネットプロトコル（ＩＰ）及びアドレス解決プロトコル（ＡＲＰ）を実行するのに適切なハードウェア及びソフトウェアを備える。この目的は当業者には容易に理解される。また、伝送制御プロトコル（ＴＣＰ）及びユーザデータグラムプロトコル（ＵＤＰ）を実行するのに適切なハードウェア及びソフトウェアも含まれてよい。
【０００９】
図３には、ＩＥＥＥ  Ｓｔｄ．  ８０２．１１−１９９７バージョンなどの米国電気電子学会（ＩＥＥＥ）８０２．１１標準規格（「８０２．１１ネットワーク」と呼ばれることがある）に従って動作する典型的なネットワーク３００を示す。ネットワークは、第１、第２のアクセスポイント３０２（それぞれ、ＡＰ１，ＡＰ２）を含む。ＡＰ１，ＡＰ２は、有線イーサネット（登録商標）３０４を介して互いに接続される。無線局３０６（ＳＴＡ１，ＳＴＡ２，ＳＴＡ３）はＡＰ１に関連付けられ、ＳＴＡ４，ＳＴＡ５，ＳＴＡ６として識別される無線局３０６は、ＡＰ２に関連付けられる。図３に示すように、局３０６（ＳＴＡ１〜ＳＴＡ６）は、それ自身の関連するＡＰを通じてインターネット３０８にアクセスする。従来的には、これらのＡＰは、有線イーサネットなどのバックホールインフラストラクチャを通じてインターネットに接続する。
【００１０】
本発明の一実施形態では、ネットワーク１００の有線部分（例えば、固定ネットワーク１０４）に接続されているインテリジェントアクセスポイント（図１に示すＩＡＰ１０６）の使用によって、バックホールインフラストラクチャの必要が回避される。ＩＡＰ１０６は、そのＩＡＰ１０６に関連付けられているデバイスに対しインターネット接続を提供する。以下で述べるように、デバイスは結合プロトコルを用いてＩＡＰ１０６に関連付けられる。
【００１１】
本発明の種々の実施形態の説明を補助するため、次の定義を提供する。
メッシュデバイス  −  本発明の一実施形態によって動作するデバイスであり、ＩＥＥＥ８０２．１１又はＩＥＥＥ８０２．１５など、標準規格の無線プロトコルに従ってよい。これらのデバイスは、そのデバイスに関連付けられているプロキシデバイスとの間でパケットを転送する。
非メッシュデバイス  −  ＩＥＥＥ８０２．１１又はＩＥＥＥ８０２．１５など、標準規格の無線プロトコルに従うが、いかなる種類のルーティングにも関与しないデバイス。メッシュデバイスは、これらのデバイスの「プロキシ」となり、これらのデバイスの経路を確立する。
【００１２】
図４には、本発明の一実施形態による図１に示すネットワーク１００の使用を示す。ここで、同じ構成要素には、同じ識別番号が与えられている。この例で示すネットワーク１００（また、ネットワーク４００として識別される）は、有線接続（固定ネットワーク１０４など）を介してインターネット４０２に通信可能にリンクする、ＩＡＰ１として識別される１つ以上のインテリジェントアクセスポイント１０６を含む。ネットワーク４００は、さらに、ＡＰ１，ＡＰ２，ＡＰ３，ＡＰ４，ＡＰ５として識別されるアクセスポイント４０２を含む。また、ネットワーク４００は１つ以上のノード４０４（ノード１として識別される）を含む。ノード４０４はメッシュデバイスであるが、他のいかなるデバイスのプロキシにもならない。ネットワーク４００におけるノード４０４は全て、ＩＡＰ１に関連付けられる。ネットワーク４００は、さらに、無線局４０６（ＳＴＡ１〜ＳＴＡ１８）を含む。無線局４０６は各々、最も近いアクセスポイント４０２（例えば、ＡＰ１〜ＡＰ５）に関連付けられている。例えば、ＳＴＡ１３，ＳＴＡ１４，ＳＴＡ１５は各々、アクセスポイントＡＰ５に関連付けられる。一部の局４０６は、図１に関連して上述にて説明したモバイルノード１０２（又はルータ１０７）である。この例では、ＳＴＡ１３，ＳＴＡ１４，ＳＴＡ１５として識別される無線局４０６は非メッシュデバイスであり、ルーティングに直接的に関与しない。また、ネットワーク４００はデバイス１として識別されるデバイス４０８を含む。デバイス１はアクセスポイントＡＰ５に関連付けられ、イーサネット４１０を介してＡＰ５に接続されている。
【００１３】
図４に示す実施形態によれば、ＡＰ１〜ＡＰ５，ＩＡＰ１は、アクセスポイント用のＩＥＥＥ８０２．１１標準規格に準拠して動作するが、本発明について本明細書に記載の追加の機能も有する。さらに、図４に示す実施形態によれば、局４０６（ＳＴＡ１〜ＳＴＡ１８）は、ＩＥＥＥ８０２．１１標準規格に準拠して動作する。そのため、局４０６（ＳＴＡ１〜ＳＴＡ１８）は標準的な関連モデルを用いて、その局の近傍のＡＰに関連付けられる。ＡＰは無線リンクを用いて他のＡＰと通信を行う。ＡＰは、ＳＴＡと通信を行うのに使用するのと同じ無線リンクを使用することが可能であり、或いは、他のＡＰと通信を行うための代替のリンクを使用することが可能である。また、図４に示すネットワークは、ＩＥＥＥ８０２．１１−１９９７標準規格に記載の無線配信システムに関連して使用されてもよい。
【００１４】
図４に示す一例のネットワーク４００において、ＳＴＡ１３がＳＴＡ１６と通信を行う必要があるとき、この例において通信を行うために最も効率的な経路（ホップが最小）は、ＡＰ３を通る経路である。なお、ＳＴＡが標準的なＩＥＥＥ８０２．１１プロトコルに従うとき、ＳＴＡは、そのＳＴＡの関連するＡＰと「関連モード」で通信を行うことのみが許される。しかしながら、本発明の一実施形態によって最も「効率的な」経路を判定するため、ＡＰはルーティングプロトコルを使用し、テーブルを参照する。ここで、テーブルについて説明する。
【００１５】
再び図４を参照すると、各ＡＰは、ＡＰに関連付けられる各デバイス（即ち、ＡＰがプロキシとなる各デバイス）についてのエントリを含む「関連テーブル」又は「プロキシテーブル」を維持する。また、ＡＰは有線イーサネットポートによって、又はＩＥＥＥ８０２．１５、トークンリングなど他の有線／無線プロトコル若しくは当業者に理解される有線／無線プロトコルによって、ノード又はデバイスをそのＡＰに関連付けることが可能である（例えば、ＡＰ５はデバイス１を自身に関連付ける）。また、ＡＰの関連テーブルは非メッシュデバイスについてのエントリを含んでもよい。非メッシュデバイスは他のＡＰに関連付けられるが、そのＡＰを中間ノードとして使用して、ネットワーク４００における他のデバイスと通信を行う。関連テーブル中の各エントリは、次の情報のうちの１つ以上を含んでよい。
・デバイスの媒体アクセス制御（ＭＡＣ）アドレス（ＭＡＣアドレス指定方式が使用される場合）
・デバイスＩＰアドレス（ＩＰアドレス指定方式が使用される場合）
・デバイスＩＤ（ＩＰ又はＭＡＣ以外のアドレス指定方式が使用される場合）
・静的又は動的エントリ（即ち、エントリが静的であるか、動的であるか）
・関連ＡＰアドレス（このアドレスは、使用されるアドレス指定方式に応じて、ＭＡＣアドレス、ＩＰアドレス、又は他のデバイスＩＤであり得る。このエントリは、他のＡＰに関連付けられている非メッシュノードについての関連情報をノードが維持する場合に使用される。これは、ネットワークにおいて４アドレス指定方式が用いられる場合に有用である。）
・エントリの有効時間。
【００１６】
また、各ＩＡＰ１０６は「結合テーブル」を維持する。結合テーブルは、ＩＡＰに関連付けられる（本明細書では「結合される」とも呼ぶ）各ＡＰ（即ち、ＩＡＰ１０６へ結合される各メッシュデバイス）についてのエントリを含む。結合テーブル中の各エントリは、次の情報のうちの１つ以上を含んでよい。
・メッシュデバイス（例えば、ＭＡＣアドレス指定方式が使用される場合のＡＰ）のＭＡＣアドレス
・メッシュデバイス（例えば、ＩＰアドレス指定方式が使用される場合のＡＰ）のＩＰアドレス
・デバイスＩＤ（ＩＰ又はＭＡＣ以外のアドレス指定方式が使用される場合）
・メッシュデバイス（例えば、ＡＰ）に関連付けられているデバイスと、各デバイスの有効時間とのリスト
・メッシュデバイス（例えば、ＡＰ）エントリの有効時間。
【００１７】
ここで図５〜７に示すフローチャートに関連して、結合テーブル及び関連テーブルの作成及び更新のプロセスについて説明する。図５に示すように、ステップ１０００にて、非メッシュデバイス（例えば、ＳＴＡ１３）がメッシュデバイス（例えば、ＡＰ５）に関連付けられると、ステップ１０１０にて、メッシュデバイス（例えば、ＡＰ５）は、この非メッシュデバイスについて、関連テーブル又はプロキシテーブルにエントリを追加する。同時に、又は、一定期間内に、ステップ１０２０にて、メッシュデバイスＡＰ５は結合要求（ＢＲＥＱ）をそのメッシュデバイスの結合されているＩＡＰ１０６（ＩＡＰ１）に送信して、新たな更新を報告する。ＢＲＥＱを受信すると、ステップ１０３０にて、ＩＡＰ１は、この新たな関連する非メッシュデバイスについて、結合テーブルにエントリを追加する。
【００１８】
ＢＲＥＱは次の情報を含むが、それらに限定されない。
・結合ＩＡＰのアドレス（アドレスは、使用されるアドレス指定方式に応じて、ＭＡＣアドレス、ＩＰアドレス、又は他のデバイスＩＤであり得る）
・発信元のＭＡＣアドレス（メッシュデバイス、例えば、ＡＰ。アドレスは、使用されるアドレス指定方式に応じて、ＭＡＣアドレス、ＩＰアドレス、又は他のデバイスＩＤであり得る）
・発信元メッシュデバイスに関連付けられているデバイスのリスト
・古い結合ＩＡＰのＭＡＣアドレス（アドレスは、使用されるアドレス指定方式に応じて、ＭＡＣアドレス、ＩＰアドレス、又は他のデバイスＩＤであり得る）。
【００１９】
図６のフローチャートに示すように、ステップ１１００にて、メッシュデバイスＡＰ（例えば、ＡＰ５）が１つのＩＡＰ（例えば、ＩＡＰ１）から別のＩＡＰ（図示せず）にハンドオフすると、ステップ１１１０にて、「フォース」ビット「Ｆ」がＢＲＥＱにセットされる。フォースビットのセットされたＢＲＥＱを受信すると、ステップ１１２０にて、メッシュデバイスが関連付けられるＩＡＰは有線バックボーン（例えば、固定ネットワーク１０４）に対し結合告知（ＢＡＮＮ）メッセージを生成し、ネットワークにおいてメッシュデバイスが結合されていた古いＩＡＰに通知する。
【００２０】
ＢＡＮＮは次の情報を含むが、それらに限定されない。
・ＩＡＰのアドレス（メッシュデバイスの結合されている新たなＩＡＰ。アドレスは、使用されるアドレス指定方式に応じて、ＭＡＣアドレス、ＩＰアドレス、又は他のデバイスＩＤであり得る）
・発信元のアドレス（メッシュデバイスのアドレスである。アドレスは、使用されるアドレス指定方式に応じて、ＭＡＣアドレス、ＩＰアドレス、又は他のデバイスＩＤであり得る）
・古いＩＡＰのアドレス（メッシュデバイスの結合されている古いＩＡＰ。アドレスは、使用されるアドレス指定方式に応じて、ＭＡＣアドレス、ＩＰアドレス、又は他のデバイスＩＤであり得る）。
【００２１】
ＢＡＮＮメッセージ中の古いＩＡＰのアドレスが受信側ＩＡＰのアドレスである場合、ステップ１１３０にて、古いＩＡＰ（ＩＡＰ１）は、ＩＡＰ１の結合テーブルから、発信元ノード（ハンドオフしたばかりのメッシュデバイス、この例では、ＡＰ５）及びその全てのプロキシを削除する。また、ステップ１１４０にて、ＩＡＰ１は結合削除（ＢＲＥＤ）メッセージを発信元ノード（ＡＰ５）に送信し、アクションを肯定応答する。また、新たなＩＡＰは、ＷＡＮ上で最近結合されていた各デバイスについて１つのＬ２更新パケットを送信し、ブリッジ／スイッチのエントリを更新する。
【００２２】
ＷＡＮ上の他のＩＡＰは、これらのＬ２更新パケットを取得すると、Ｌ２更新パケット中の送信元アドレスが、自身の結合テーブル中に存在するか否かを検査する。送信元アドレスが結合テーブル中にあり、ＩＡＰが直接的に送信元のプロキシとならない場合、ＩＡＰはプロキシ削除（ＰＲＥＭ）メッセージを生成し、Ｌ２送信元ノードが関連付けられているメッシュノードにそのメッセージをユニキャストする。
【００２３】
非メッシュデバイスが、１つのメッシュデバイスから、同じＩＡＰ又は異なるＩＡＰに結合され得る別のメッシュデバイスへハンドオフするとき、以下でより詳細に説明するように、結合要求、レイヤ２（Ｌ２）更新、及びプロキシ削除（ＰＲＥＭ）などのメッセージの組み合わせが生成され、プロキシ／関連テーブルが即座に更新される。図７に示すように、ステップ１２００にて、非メッシュデバイス（例えば、ＳＴＡ１３）が１つのＡＰ（例えば、ＡＰ５）から移動し、別のＡＰ（例えば、ＡＰ１）に関連付けられると、ステップ１２１０にて、この関連付けによってＡＰ１がトリガされ、ＡＰ１に関連付けられた新たな非メッシュノード（ＳＴＡ１３）を示す新たなＢＲＥＱメッセージがＩＡＰへ送信される。ＩＡＰ１はＢＲＥＱを受信すると、ステップ１２２０にて、最初に、その結合テーブルを調査して、ＳＴＡ１３についてのエントリがＩＡＰ１に存在するか否かを調べる。エントリが見つからない場合、ステップ１２３０にて、ＩＡＰはデバイスが新しいと仮定して、そのデバイスについて新たなエントリを作成し、ＷＡＮ上にＬ２更新パケットを生成する。そうでない場合、ＩＡＰは既存のエントリを更新して新たな関連付けを反映するが、Ｌ２更新パケットは送信しない。この例では、同じＩＡＰへ結合されているＡＰ間で局が移動したため、ＩＡＰは既にＳＴＡ１３についての１つのエントリを有しているので、ステップ１２４０にて単にエントリを更新し、Ｌ２更新は送信しない。ステップ１２４０にて、関連エントリの更新中、ＩＡＰはＰＲＥＭを生成し、非メッシュノード（ＳＴＡ１３）が関連付けられたメッシュデバイス（ＡＰ５）にＰＲＥＭをユニキャストする。
【００２４】
ＰＲＥＭは次の情報を含むが、それらに限定されない。
・ＩＡＰのアドレス（アドレスは、使用されるアドレス指定方式に応じて、ＭＡＣアドレス、ＩＰアドレス、又は他のデバイスＩＤであり得る）
・意図されるメッシュデバイスのアドレス（そのプロキシを削除する必要があるメッシュデバイスのアドレス）
・削除の必要のあるプロキシデバイスのリスト（削除の必要のある意図されるメッシュデバイスがプロキシとなるノード／削除の必要のある意図されるメッシュデバイスに関連付けられているノードのリスト）。
【００２５】
ＰＲＥＭメッセージを受信すると、ステップ１２５０にて、メッシュデバイス（ＡＰ５）はＰＲＥＭメッセージ中のプロキシデバイスのリストに従って、プロキシ／関連テーブルからエントリを削除する。
【００２６】
上述のように、図４のアーキテクチャを効率的に利用するために、ＡＰはルーティングプロトコルを使用して、宛先への最適経路を判定する。ここで、使用可能な種々のタイプのルーティングプロトコルについて説明する。これらのプロトコルは、一般に（ａ）テーブル駆動型（即ち、プロアクティブ）ルーティングプロトコル、（ｂ）オンデマンド型（即ち、リアクティブ）ルーティングプロトコルとして分類され得る。
【００２７】
テーブル駆動型ルーティングプロトコルでは、各ノード（例えば、ＡＰ，ＩＡＰ，ＳＴＡ）は、ネットワーク４００における他の全てのノードに対するルーティング情報を含む１つ以上のテーブルを維持する。一貫した最新のネットワークについてのビューを維持するために、全てのノードは自身のテーブルを更新する。ネットワークトポロジが変化すると、ネットワーク全体に関する一貫した最新のルーティング情報を維持するために、ノードはネットワーク全体に渡って更新メッセージを伝播する。これらのルーティングプロトコルでは、ネットワークを通じてトポロジ変化情報が配信される方法や、必要なルーティング関連テーブルの数が異なる。
【００２８】
使用され得る１つのテーブル駆動型プロトコルは、距離ベクトルルーティング（又は、宛先シーケンス距離ベクトル（ＤＳＤＶ）ルーティングなど、モバイルアドホックネットワーク（ＭＡＮＥＴ）用の距離ベクトルルーティングの任意の変形形態）である。本発明の一実施形態では、距離ベクトルルーティングは次のように修正される。他のＡＰに対する経路を広告する代わりに、ＡＰは、それぞれのＡＰに関連付けられているデバイスに関する情報も含む。
【００２９】
使用され得る別のテーブル駆動型プロトコルは、リンクステートルーティング（又は、最適化ステートリンクルーティング（ＯＬＳＲ）のような、リンクステートルーティングの任意の変形形態）である。本発明の一実施形態では、リンクステートルーティングは次のように修正される。近傍のＡＰに関するリンク更新を送信する代わりに、全てのＡＰは、近傍のＡＰに関連付けられているデバイスに関する情報も含む。したがって、ルーティングの収束後、全てのＡＰは他の全てのＡＰへの経路を認識しており、それらのＡＰに関連付けられているデバイスに関しても認識している。
【００３０】
オンデマンドルーティングプロトコルは、送信元ノードによって所望されるときにのみ経路を作成する。ノードは、宛先への経路を要求するとき、ネットワーク４００内で経路発見プロセスを開始する。このプロセスは、経路が見出されるか、或いは、全ての可能な経路の組み合わせが検討されると終了する。経路は、一旦確立すると、送信元からの全てのパスに沿って宛先がアクセス不能となるか、又は、もはや経路が所望されなくなるまで、何らかの形態の経路維持手続によって維持される。
【００３１】
当業者には理解されるように、アドホックオンデマンド距離ベクトル（ＡＯＤＶ）及び動的送信元ルーティング（ＤＳＲ）は、迅速な収束及び小さなオーバヘッドを提供するオンデマンドルーティングプロトコルであり、有効な経路を有する場合に中間ノードが宛先に応答することを可能とする。しかしながら、図４に示すネットワーク４００では、この例におけるルーティングにはメッシュデバイスしか関与せず、実送信元及び実宛先がＡＯＤＶによって要求される任意のシーケンス数を維持しない非メッシュデバイスであることもあり得る。一例は、ＳＴＡ１５がデバイス１との通信を試行する場合である。宛先ノードがメッシュデバイスでない場合、宛先ノードが関連付けられているデバイスしか応答できないため、シーケンス数が維持されないことによって、ＤＳＲ、特にＡＯＤＶの標準的な実装を用いる不充分なルーティングが生じることがあり得る。
【００３２】
本発明の一実施形態では、ＡＯＤＶ及びＤＳＲなどの標準的なオンデマンドルーティングプロトコルは、全てのメッシュデバイスが、それらのメッシュデバイスに関連付けられているデバイスのリストをＩＡＰへ送信するように修正される。このリストは定期的に、或いは、イベントに応答して送信され得る。例えば、各ＡＰは新たなノードが自身に関連付けられるときはいつでも、リストを送信するように構成され得る。ＩＡＰは、この情報を自身の結合テーブルに記憶する。また、各メッシュデバイスデバイスを追加する時、又は、関連テーブルからデバイスを削除する時を、ＩＡＰへ通知する。
【００３３】
ここで図８のフローチャートを参照して、本発明の一実施形態によって局４０６（ＳＴＡ１〜ＳＴＡ１８）が別の局４０６（ＳＴＡ１〜ＳＴＡ１９）にパケットを送信する手法の一例を説明する。最初に、ステップ１３００にて、この例では「送信元ノード」とも呼ぶこともある送信局４０６（例えば、ＳＴＡ１３）は、ＩＥＥＥ８０２．１１標準規格に従って、宛先ノード（例えば、この例ではＳＴＡ１６）へアドレス指定されたパケットをＳＴＡ１３の関連するＡＰ（ＡＰ５）へ送信する。この時点で、パケットは送信元アドレス及び宛先アドレスを含む。パケットを受信すると、ＡＰ５は、以下に述べる方法及び２００４年６月７日に出願の米国特許出願第１０／８６３，７１０号明細書に記載の方法のうちの１つを用いる。この出願全体を引用によって本明細書に援用する。
【００３４】
例えば、最初に、ステップ１３１０にて、ＡＰ５は、自身のルーティングテーブルを参照し、自身が宛先への有効な経路を有するか否かを判定する。ＡＰ５は、自身のルーティングテーブル中に有効な経路を有する場合、ステップ１３２０にて、宛先に向けて次のホップに対してパケットを転送する。ＡＰ５は、自身のルーティングテーブル中に宛先への有効な経路が存在しないと判定する場合、ステップ１３３０にて、ＡＰ５の結合されているＩＡＰ１へパケットを転送し、ステップ１３４０にて、ステータス要求と呼ぶ特別なメッセージをＩＡＰ１へ送信する。ステータス要求メッセージの内容は次の情報を含むが、それらに限定されない。
１．発信元デバイスのアドレス（この例では、ＡＰのアドレス）
２．宛先ノードのアドレス
３．ファインドビット（Ｆｉｎｄ  ｂｉｔ）（以下で述べる）。
【００３５】
次いで、ステップ１３５０にて、ＡＰ５はＩＡＰ１への経路を判定する。ＡＰ５は、このタスクを種々の手法で達成することが可能である。その手法のうちの一部は、２００４年１月１３日に出願の米国特許出願第１０／７５５，３４６号明細書に記載されている。この出願全体を引用によって本明細書に援用する。
【００３６】
このステータス要求を受信すると、ステップ１３６０にて、ＩＡＰ１は自身の結合テーブルを調べ、テーブル中に宛先ノード（例えば、この例ではＳＴＡ１６）が存在するか否か、失効していないか否かを調べる。なお、結合テーブル中に含まれる情報は全て、ルーティングテーブル中の情報と組み合わされ得る。組み合わされたデータ構造は、ルーティングテーブルと、結合テーブルとの両方として使用することが可能である。結合テーブルの調査後、ＩＡＰ１はステータス応答と呼ぶメッセージをＡＰ５へ返送する。ステータス応答メッセージの内容は次の情報を含むが、それらに限定されない。
１．発信元デバイスのアドレス（この例では、ＩＡＰのアドレス）
２．宛先ノードのアドレス
３．サクセスビット
４．宛先のタイプ（メッシュデバイス又は非メッシュデバイス）
５．宛先デバイスのプロキシとなるメッシュデバイスのアドレス（宛先デバイスが非メッシュデバイスである場合）
６．ファウンドビット（Ｆｏｕｎｄ  ｂｉｔ）（以下で述べる）。
【００３７】
ＩＡＰ１は、ステップ１３６０にて、自身の結合テーブル中に有効なエントリを見出す場合、ステップ１３７０にて、サクセスビットのセットされた状態のステータス応答メッセージをＡＰに返送する。ＩＡＰ１は、自身の結合テーブル中に有効なエントリを見出さない場合、ステップ１３８０にて、サクセスビットのセットされない状態のステータス応答メッセージをＡＰ５に返送する。また、ステータス応答メッセージは宛先デバイスのタイプ、即ち、メッシュ型又は非メッシュ型を含む。宛先デバイスが非メッシュ型である場合、ＩＡＰ１は宛先デバイスのプロキシとなるメッシュデバイスのアドレスも含む。
【００３８】
サクセスビットのセットされた状態のステータス応答を受信すると、ステップ１３９０にて、ＡＰ５は、例えば、ＡＯＤＶに従って、拡張リングサーチを開始する。このサーチを開始する際、ステップ１４００にて、ＡＰ５は経路要求（ＲＲＥＱ）パケットを送信する。最大生存時間（ＴＴＬ）は、ＩＡＰ１へのホップ数と等しくすることが可能である。この例では、最大ＴＴＬがＩＡＰ１へのホップ数の関数であることも可能であり、当業者に理解される何らかの他の因子の関数であることも可能である。宛先がメッシュデバイスであることをタイプフィールドが示す場合、ＲＲＥＱパケットの「宛先アドレス」フィールドは、宛先自体のアドレスを含む。或いは、宛先が非メッシュデバイスであることをタイプフィールドが示す場合、「宛先アドレス」フィールドは、ＩＡＰ１によって報告される、宛先デバイスのプロキシとなるメッシュデバイスのアドレスを含む。この時点では、ＲＲＥＱパケットは「宛先アドレス」フィールド中にメッシュデバイスのアドレスを含むため、「宛先アドレス」への有効な経路を有する任意のノードが応答可能である。そのため、ＲＲＥＱパケットは終端（宛先）にまで到達する必要はない。一部のメッシュデバイスがＲＲＥＱパケットを受信し、自身のルーティングテーブル中で適切な経路を見出し、ステップ１４１０にて、ＲＲＥＱの発信元に戻るように（ＡＰ５に戻るように）経路応答（ＲＲＥＰ）をユニキャストすると、経路が利用可能となる。
【００３９】
送信元メッシュデバイスと宛先メッシュデバイスとの間の経路に関する経路エントリを設定及び更新又は設定若しくは更新するために、２つの変形形態を使用することが可能である。１つの変形形態は、中間メッシュデバイスのみが宛先メッシュデバイス及び送信元メッシュデバイスへの経路を維持することである。この変形形態では、次の各々のデータパケットは６つのアドレス、即ち、イニシエータアドレス、ターミネータアドレス、送信元メッシュデバイスアドレス、宛先メッシュデバイスアドレス、現在のホップデバイスアドレス、次のホップデバイスアドレスを運ぶ。実送信元及び実宛先がメッシュデバイスでない場合、イニシエータアドレス及びターミネータアドレスは、それぞれ、実送信元非メッシュデバイス及び実宛先非メッシュデバイスとなり、送信元メッシュデバイスは送信元非メッシュデバイスのプロキシのデバイスであり、宛先メッシュデバイスは宛先非メッシュデバイスのプロキシのデバイスである。実送信元及び実宛先が、メッシュデバイスである場合、イニシエータアドレスは送信元メッシュデバイスアドレスと同じであり、ターミネータアドレスは宛先メッシュデバイスアドレスと同じである。
【００４０】
第２の変形形態は、中間メッシュデバイスが、送信元メッシュデバイス及び宛先メッシュデバイスへの経路と、送信元メッシュデバイス及び宛先メッシュデバイスがプロキシとなる非メッシュデバイスについてのプロキシ／関連情報とを維持することである。ＲＲＥＰが宛先メッシュデバイスから送信元メッシュデバイスへ返送されるとき、各中間メッシュデバイスは、宛先メッシュデバイスについての経路エントリを作成／更新することに加え、実送信元及び実宛先のうちの一方又は両方がメッシュデバイスでない場合、自身のプロキシ／関連テーブルを更新する。中間ノードは非メッシュデバイスについてエントリを作成し、ＲＲＥＰ中のアドレス情報に従って、非メッシュデバイスが関連付けられているメッシュデバイスを記録する。この変形形態では、続くデータパケットについて、４つのアドレスしか必要でない。この４つのアドレスは、イニシエータアドレス、ターミネータアドレス、現在のホップデバイスアドレス、次のホップデバイスアドレスである。非メッシュ送信元デバイスから発し非メッシュ宛先デバイスで終了するデータパケットを中間メッシュノードが転送するとき、最初に、中間ノードは非メッシュ宛先デバイスについてプロキシ／関連テーブルを調べ、非メッシュ宛先デバイスのプロキシとなる宛先メッシュデバイスを取得する。次に、中間ノードは、宛先メッシュデバイスが次のホップデバイスアドレスを取得するように、経路エントリについて経路テーブルを調査する。
【００４１】
ステップ１４１０にてＲＲＥＰを受信すると、ステップ１４２０にて、ＡＰ５は自身のルーティングテーブルを更新し、新たに見つかった経路の使用を開始する。したがって、ＲＲＥＱパケットが宛先にまで移動する必要はないため、中間ノードが宛先まで又は宛先のプロキシとなるメッシュデバイスまでの有効な経路を有するレベルで、ＲＲＥＱパケットのフラッドが停止する。これによって、ネットワークが大きな領域を含むことが可能であるように、オーバヘッドは有意に減少する。また、これによって、特に、ネットワークに存在しない宛先ノードをＡＰが探索するときに行う、相当なオーバヘッドを生じ得る全ネットワーク経路発見をＡＰが行う可能性は減少する。
【００４２】
ＡＰ５は、ステータス応答又はステータスエラーのメッセージの待機中、ＩＡＰ１にパケットを送信し続ける。このため、ＡＰ５においてパケットがバッファリングされる必要はない。ステップ１３８０にて、サクセスビットのセットされた状態のステータス応答が到来する場合、ＩＡＰ１がステータスエラーと呼ばれる特別なメッセージを受信しない限り、ＡＰはＩＡＰ１にパケットを送信し続ける。ステータスエラーメッセージを発生させ得るイベントのシーケンスの一例を以下で説明する。
【００４３】
ＩＡＰ１は、ステータス要求メッセージを受信すると、上述のように、ステップ１３６０にて結合テーブルのプローブを行い、ステータス要求に述べられる宛先についてのエントリを有するか否かを見出す。プローブが不成功である場合、ステップ１４３０にて、ＩＡＰ１は、宛先が結合されるＩＡＰの特定を試みる。これには、ＩＡＰホストのルーティングテーブルにおける経路ルックアップ又はＡＲＰキャッシュのルックアップであるか、或いは何らかの他の適切な方法を使用することが可能である。ステップ１４４０にて、ＩＡＰ１は、宛先が結合されるＩＡＰを見出すことが不可能であるため、パケットの転送は不可能であると判定する場合、ステップ１４５０にて、送信元ノード（例えば、ＳＴＡ１３）に対してステータスエラーメッセージを生成する。
【００４４】
ステータスエラーメッセージの考えられる内容は次の情報を含むが、それらに限定されない。
１．エラーメッセージを送信するＩＡＰのアドレス
２．ステータス要求を生成した送信元ノードのアドレス
３．送信元ノードの述べる宛先ノードのアドレス
また、デバイス間を流れる任意の他のメッセージによっても同じ情報が伝達され得る。しかしながら、ステップ１４４０にて宛先が結合されるＩＡＰが決定され得る場合、ステップ１４６０と同様に、このＩＡＰの部分に関してさらなる処置は取られない。
【００４５】
なお、メッシュデバイス４０４（例えば、図４のノード１）は、ノード１が他のいかなるデバイスの「プロキシ」ともならないことを除き、上述の例でＡＰ５が実行した全てのステップを実行可能である。したがって、上述の例では真の「送信元ノード」はＡＰ５に関連付けられているデバイス（例えば、ＳＴＡ１３）であったが、ネットワーク４００の他の部分に関する限り、送信元ノードはＡＰ５自身であった。ノード１は、ネットワーク４００において局４０６と通信を行おうとする場合、真の「送信元ノード」でもあり、ネットワークの認識する送信元ノードでもある。
【００４６】
上述の手続に対して幾つかの変形形態が存在し得る。それらの変形形態について、以下の段落で説明する。ここでは一般的な用語「送信元ノード」を使用するが、送信元ノードがＡＰのうちの１つであるか、又は、他のいずれのノードについてもＡＰとして働かないメッシュデバイス（例えば、ノード７）であってもよいことが理解される。
【００４７】
第１の変形形態では、ステータス要求メッセージ及びデータパケットをＩＡＰへ同時に送信する代わりに、送信元ノード（例えば、ＡＰ５）は、ステータス応答又はステータスエラーの待機中にパケットをバッファリングすることも可能である。これは、送信元ノードと宛先との間に１つの直接的な最適経路が存在するため、ＩＡＰ１を介してパケットを送信することが非効率的となる場合に有利である。しかしながら、このバッファリングによってパケットの送信が遅延する場合があるため、さらなるバッファ空間が必要とされ得る。
【００４８】
第２の変形形態では、送信元ノードは、ＩＡＰ１へパケットを送信する前、又は、任意のステータス要求メッセージを送信する前に、最初に宛先についてローカル経路発見を行うことが可能である。例えば、送信元ノードは、ＩＡＰ１へのホップ数に等しい最大ＴＴＬを用いて、拡張リングサーチを行うことが可能である。最大ＴＴＬはＩＡＰ１へのホップ数の関数や、何らかの他の関数であってもよい。この場合、送信元ノードは、宛先のタイプ（メッシュ型又は非メッシュ型）を認識しない。送信元ノードは、ＲＲＥＱメッセージの「宛先アドレス」フィールドに実宛先アドレスを設定するのみである。このプロセスに伴うオーバヘッドは、宛先デバイスのタイプに依存する。宛先デバイスがメッシュデバイスである場合、上述のように、宛先デバイスへの有効な経路を有する任意のノードが応答可能である。宛先デバイスが非メッシュデバイスである場合、ＲＲＥＱパケットへの応答は、宛先のプロキシとなっているメッシュデバイス（例えば、関連するＡＰ）が行う。したがって、ＲＲＥＱメッセージが受信されるとき、各ノードは自身の関連テーブルを調査し、宛先が自身に関連付けられているノードのうちの１つであるか否かについて応答する。また、この場合、ＲＲＥＰパケットは応答により２つのアドレスを伝達する必要があり得るため、修正される必要がある。実宛先が非メッシュデバイスである場合、ＲＲＥＰメッセージは宛先のプロキシとなるデバイスのアドレスと、宛先自体のアドレスとを含む。送信元ノードは、ＲＲＥＰメッセージを受信する場合、宛先へのパケットの送信を開始する。１回以上の試行の後に応答が受信されない場合、送信元ノードは、自身の使用する最大ＴＴＬによって決定される近傍に宛先ノードが存在しないことを安全に判定することが可能である。この時点では、通常、送信元ノードはＩＡＰ１を使用して宛先へパケットを送信する必要がある。これは、次の２つの手法のうちの一方によって達成され得る。
【００４９】
第１の手法では、送信元ノードは、ローカル経路発見が失敗したと判定すると、ＩＡＰ１へのパケットの送信を開始することが可能である。ネットワークに現在は宛先ノードが存在しないことを示すステータスエラーメッセージがＩＡＰ１から受信される場合、送信元ノードは停止する。
【００５０】
第２の手法では、ネットワークに宛先ノードが存在するか否かを判定するために、送信元ノードはＩＡＰ１に対し特別なメッセージ、即ち、ファインドビットのセットされた状態のステータス要求メッセージを送信することが可能である。ＩＡＰ１は、メッセージを受信すると、自身のホストルーティングテーブル又はＡＲＰキャッシュに問い合わせを行うか、或いは、何らかの他の適切な方法を用いて、宛先ノードの結合されているＩＡＰ１を見出す。ＩＡＰ１は、宛先ノードの結合されているＩＡＰ１を、したがって、宛先ノード自体を見出すことに成功する場合、ファウンドビットのセットされた状態のステータス応答メッセージを送信することによって、そのことを送信元ノードに示す。そうでない場合、ＩＡＰ１は送信元ノードへステータスエラーメッセージを送信する。
【００５１】
ファウンドビットのセットされた状態のステータス応答メッセージが送信元ノードによって受信される場合、ＩＡＰ１が宛先ノードの結合されている適切なＩＡＰ１へ転送するように、送信元ノードはＩＡＰ１へのパケットの送信を開始する。ステータスエラーメッセージが受信される場合、送信元ノードはその時点で宛先が到達不能であることを宣言し、後に再試行する。この変形形態では、経路を見出すことに待ち時間が伴い、パケットのバッファリングが必要な場合がある。
【００５２】
第３の変形形態では、ステータス要求、ステータス応答、及びステータスエラーなどの特別なメッセージを用いる代わりに、ノードは他のメッセージを用いて同じ情報を伝達することが可能である。例えば、一般に、送信元ノードは、ＩＰアドレス、ＭＡＣアドレスなどを判定するために、送信元ノードの結合されているＩＡＰ１へＤＮＳ問い合わせ及びＡＲＰ問い合わせのうちの一方又は両方を送信する必要がある。ＩＡＰ１は、そうしたメッセージを受信すると、特別な種類のメッセージを送信して、宛先ノードがそのＩＡＰ１に結合されているか否か、又は、ネットワークに宛先ノードが存在するか否かを示すことが可能である。また、ＡＲＰ又はＤＮＳ応答は、この情報を含むように修正され得る。データパケット自体がステータス要求を置き換えることも可能である。例えば、ＩＡＰ１で受信される特定の宛先への最初のデータパケットは、ステータス要求メッセージのように取り扱われ得る。この変形形態では、特別なステータスメッセージは必要とされない。上述のように、このような情報を発見するための幾つかの手法が存在し得る。本発明の一実施形態では、ＡＲＰ，ＤＮＳ  ＤＨＣＰなどのサーバ中心サービスにおける応答を提供するために、ＩＡＰ１を使用することが可能である。
【図面の簡単な説明】
【００５３】
【図１】本発明の一実施形態によるシステム及び方法を用いる複数のノードを含むアドホック無線通信ネットワークの一例のブロック図。
【図２】図１に示すネットワークにおいて用いられるモバイルノードの一例を示すブロック図。
【図３】米国電気電子学会（ＩＥＥＥ）８０２．１１標準規格に従って動作する典型的なネットワークの接続の一例を示す図。
【図４】本発明の一実施形態によって構成されている図１に示す無線ネットワークのブロック図。
【図５】本発明の一実施形態によって図４に示す無線ネットワークにおけるノードの結合テーブル及び関連テーブルを更新するための動作の例を示すフローチャート。
【図６】本発明の一実施形態によって図４に示す無線ネットワークにおけるノードの結合テーブル及び関連テーブルを更新するための動作の例を示すフローチャート。
【図７】本発明の一実施形態によって図４に示す無線ネットワークにおけるノードの結合テーブル及び関連テーブルを更新するための動作の例を示すフローチャート。
【図８】本発明の実施形態によって図４に示す無線ネットワークにおけるノード間でパケットを送信するために実行される動作の一例を示すフローチャート。
【図１】
2008512901.tif 000003
【図２】
2008512901.tif 000004
【図３】
2008512901.tif 000005
【図４】
2008512901.tif 000006
【図５】
2008512901.tif 000007
【図６】
2008512901.tif 000008
【図７】
2008512901.tif 000009
【図８】
2008512901.tif 000010
【国際調査報告】
2008512901.tif 000011