(57)【特許請求の範囲】
【請求項１】
無線アドホック・マルチホッピング・ピアツーピア通信ネットワークにおけるノード間のデータパケット経路制御のための経路判定方法において、
ノードのうちの１つが発信元ノードとして機能し、宛先に対するデータパケットの送信を試行する時、宛先はネットワーク内の別のノードであるか、又はネットワーク外であるかを発信元ノードが判定することと、
宛先はネットワーク外であると発信元ノードが判定した場合、発信元ノードは同発信元ノードに関連するネットワークのインテリジェント・アクセス・ポイントに送達するようにデータパケットを発信することと、
宛先はネットワーク内の別のノードであると発信元ノードが判定した場合、宛先への経路が存在するか否かを判定するために発信元ノードが経路表を照合することと、
経路表により宛先への経路が存在することが示された場合、同経路を経て宛先に送達するように発信元ノードがデータパケットを発信することと、
経路表に宛先への経路が存在しない場合、発信元ノードは前記インテリジェント・アクセス・ポイントに送達するようにデータパケットを発信し、且つ前記インテリジェント・アクセス・ポイントに対し状態要求メッセージを発信することと、
状態要求メッセージの受信に応答して、前記インテリジェント・アクセス・ポイントは前記インテリジェント・アクセス・ポイントの経路表に宛先への経路が含まれるか否かを判定し、前記インテリジェント・アクセス・ポイントの経路表に宛先への経路が含まれる場合、前記インテリジェント・アクセス・ポイントは経路を示す第１の状態の状態応答メッセージを発信元ノードに対し送信し、且つ前記インテリジェント・アクセス・ポイントの経路表に宛先への経路が含まれない場合、前記インテリジェント・アクセス・ポイントは第２の状態の状態応答メッセージを発信元ノードに対し送信することと、
第１の状態の状態応答メッセージの受信に応答して、発信元ノードは宛先への最適経路の検出を試行し、且つ最近検出された経路を経て宛先に送達するように宛先に宛てられた追加のデータパケットを発信することと、
第２の状態の状態応答メッセージの受信に応答して、発信元ノードは宛先に送達するように追加のデータパケットを前記インテリジェント・アクセス・ポイントに対し発信することとからなる方法。
【請求項２】
発信元ノードが状態応答メッセージの受信を待機する時、発信元ノードが追加のデータパケットを前記インテリジェント・アクセス・ポイントに発信することを含む請求項１に記載の方法。
【請求項３】
発信元ノードが状態応答メッセージの受信を待機する時、発信元ノードが追加のデータパケットを前記インテリジェント・アクセス・ポイントに発信しないことを含む請求項１に記載の方法。
【請求項４】
発信元ノードは移動体ノードである請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、「経路制御」パケットの配布を制御しノード間の経路検出における遅延時間を低減することにより、無線通信ネットワークのシステム性能を改良するためのシステム及び方法に関する。詳細には、本発明は、オーバヘッド・メッセージ及びバッファされるデータが最小化される最適な通信経路を判定するためのメッセージ交換のシステム及び方法に関する。
【背景技術】
【０００２】
移動体無線電話ネットワークなど無線通信ネットワークは、過去十年間を通じて次第に普及しつつある。それらの無線通信ネットワークは、「セル（ｃｅｌｌ）」と呼ばれる複数の領域にサービス域を分割するようにネットワークのインフラストラクチャが構成されているため、一般に「セルラー（ｃｅｌｌｕｌａｒ）・ネットワーク」と称される。地上のセルラー・ネットワークには、サービス域全体を通じて所定の位置に地理的に分配された複数の相互接続された基地局、すなわち基地ノードが含まれる。各基地ノードは、カバレッジ域内に位置する無線電話機など移動体ユーザ・ノードに対し、無線周波数（ＲＦ）通信信号など電磁信号の受発信を行うことが可能な１つ以上のトランシーバを備える。通信信号には、例えば、所望の変調手法に従って変調されデータパケットとして発信される音声データが含まれる。当業者には認められ得るように、ネットワーク・ノードは、時分割多元接続（ＴＤＭＡ）形式、符号分割多元接続（ＣＤＭＡ）形式、又は周波数分割多元接続（ＦＤＭＡ）形式などの多重化形式によりデータパケット通信の受発信を行うことにより、第１のノードの単一のトランシーバがカバレッジ域の幾つかの他のノードと同時に通信することを可能とする。
【０００３】
近年では、「アドホック（ａｄ−ｈｏｃ）」ネットワークとして周知の種類の移動体通信ネットワークが開発されている。この種類のネットワークにおいては、各移動体ノードは他の移動体ノードに対する基地局又は経路制御装置（ｒｏｕｔｅｒ）として動作することが可能であるため、固定インフラストラクチャの基地局の必要は除かれる。アドホック・ネットワークに関する詳細はメイヤー（Ｍａｙｏｒ）による特許文献１に述べられている。その全内容を引用により本明細書に援用する。
【０００４】
より洗練されたアドホック・ネットワークも開発されている。このアドホック・ネットワークでは、従来のアドホック・ネットワークにおけるように移動体ノードの相互通信が可能であることに加え、移動体ノードが固定ネットワークへアクセスすることも可能であるため、公衆交換電話網（ＰＳＴＮ）上、及びインターネットなど他のネットワーク上の他の移動体ノードと通信することが可能となる。これらの進歩した種類のアドホック・ネットワークに関する詳細は、「ＰＳＴＮ及びセルラー・ネットワークとインタフェースするアドホック・ピアツーピア移動体無線接続システム（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 Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel）」と題された２００１年３月２２日出願の特許文献３、及び「アドホック・ピアツーピア移動体無線接続システムにおける優先付け経路制御（Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System ）」と題された２００１年３月２２日出願の特許文献４に記載されている。これらの各々の全内容を引用により本明細書に援用する。
【０００５】
当業者には認められ得るように、アドホック・ネットワークの一部のノードが移動体であるため、ネットワークにおいてそれらのノードとの接続性が保持される必要がある。発信されたデータパケットは、通常、最終的な宛先に到達するまで移動体デバイスから移動体デバイスへと「ホップ（ｈｏｐ）」し、伝送のパス（ｐａｔｈ）、すなわち経路を生成する。しかしながら、移動体デバイス間の伝送パスはデバイスの移動に従って変化し易いため、アドホック・ネットワーク通信においては、個々の移動体デバイスの限定された能力及び容量に対処しつつ最適性能を達成するように適合される必要がある。
【０００６】
無線ネットワークにおいては、そうした通信における経路制御プロトコルとして、オンデマンド（Ｏｎ−Ｄｅｍａｎｄ）・プロトコル（例えば、ＡＯＤＶ（ＲＦＣ３５６１），ＤＳＲ（インターネット・ドラフト）など）が頻繁に用いられる。この種類の経路制御プロトコルでは、発信元ノードの所望時にのみ経路が作成される。ノードが宛先への経路を要求する時、そのノードはネットワーク内において経路探索処理を開始する。経路が検出されるか、又は全ての可能な経路の組合せが検査されると、この処理は完了する。経路が確立されると、発信元からのパスの全てにおいて宛先へのアクセスが不可能となるか、又はその経路がもはや所望されなくなるまで、その経路は何らかの経路保持手続によって保持される。
【０００７】
通常、「経路探索」には、経路が検出されるまで「経路要求（ＲＲＥＱ）」パケットをブロードキャスト及び転送することが伴う。この間に生成されるアプリケーションパケットの全ては、発信元ノードにバッファされる。宛先が数ホップ離れている場合、この経路探索に伴い大きな遅延時間が存在し得る。特に、ＡＯＤＶにおいて用いられるように拡張リングサーチ（ｅｘｐａｎｄｉｎｇ  ｒｉｎｇ  ｓｅａｒｃｈ）手法が用いられる場合、この遅延時間は非常に大きくなり得る。これらのネットワークにおいて通常用いられるトランシーバにはメモリの制約が存在するため、遅延時間が大きいことによりバッファからパケットが欠落し得る。遅延時間が大きいことは、一部のアプリケーション、特にＴＣＰを用いるアプリケーションにおいても不適切である。
【０００８】
この経路探索処理の他の欠点は、処理中に多数の経路制御パケットが生成／転送されることである。これらのネットワークが広範囲に渡る場合、そうしたブロードキャスト及び転送により遅延時間やオーバヘッドは著しく増大し得る。宛先ノードがネットワーク内に存在しない場合、オーバヘッドはさらに悪化し、この場合には、発信元ノードは経路探索処理を繰り返し、無駄にネットワークのフラッディング（ｆｌｏｏｄｉｎｇ）を続ける。
【特許文献１】米国特許第５，９４３，３２２号明細書。
【特許文献２】米国特許出願第０９／８９７，７９０号明細書。
【特許文献３】米国特許出願第０９／８１５，１５７号明細書。
【特許文献４】米国特許出願第０９／８１５，１６４号明細書。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、効率的に宛先への経路を探索するとともに、経路検出に伴う遅延時間を低減するためのシステム及び方法の必要が存在する。
本発明の目的の１つは、オーバヘッド・メッセージ及びバッファされるデータが最小化される最適な通信経路を判定するためのメッセージ交換のシステム及び方法を提供することである。
【００１０】
本発明の別の目的は、検知された隣接ノードが宛先である場合、ＩＡＰの補助なしで経路の特定を試行するように送信ノードを制御するためのシステム及び方法を提供することである。
【００１１】
本発明の別の目的は、非最適経路を用いることを防止するために、ＩＡＰの経路探索補助を用いたメッセージ交換中にパケットをバッファするように送信ノードを制御するためのシステム及び方法を提供することである。
【００１２】
本発明の別の目的は、ＩＡＰの補助なしで経路の特定を試行し、且つその後でＩＡＰの経路探索補助を用いてメッセージを交換するように送信ノードを制御するためのシステム及び方法を提供することである。
【００１３】
本発明の別の目的は、非最適経路を用いることを防止するために、ＩＡＰのＩＡＰの経路探索補助を用いて種々の非特定メッセージを交換するように送信ノードを制御するためのシステム及び方法を提供することである。
【課題を解決するための手段】
【００１４】
これらの目的及び他の目的は、経路検知中にノード間の「経路制御」パケットの配布を制御するためのシステム及び方法を提供することにより、実質的に達成される。宛先、宛先ノード検知、及び経路を示す特定の一連の交換に対し交換されるメッセージを、好適には一連のＩＡＰデバイスを用いて減少させることにより、効率的に経路が探索され、ノード間の経路検出における遅延時間が低減される。そのような遅延時間を低減することにより、少なくとも経路選択のために個々のデバイスにおいてバッファされる情報のレベルは低減される。
【発明を実施するための最良の形態】
【００１５】
本出願においては、３５  Ｕ．Ｓ．Ｃ．第１１９条（ｅ）に基づき、２００３年６月６日に出願の米国特許仮出願第６０／４７６，２３６号に対する優先権を主張するとともに、その全内容を引用により本明細書に援用する。
【００１６】
本発明のこれらの目的及び他の目的、利点並びに新規な特徴は、以下の詳細な説明を添付の図面と共に読むことにより、さらに容易に明らかとなる。
以下に開示の本発明の実施形態により、「経路制御」パケットの配布（ｄｉｓｓｅｍｉｎａｔｉｏｎ）を制御して経路検出における遅延時間を低減することにより、無線通信ネットワークのシステム性能は改良される。その際、各実施形態は、各加入者装置（ＳＤ）において大きなバッファを保持する必要を除去するように働く。
【００１７】
上述のように、無線ネットワークにおいては、経路制御プロトコルとしてオンデマンド・プロトコル（例えば、ＡＯＤＶ（ＲＦＣ３５６１），ＤＳＲ（インターネット・ドラフト）など）が頻繁に用いられる。通常、「経路探索」には、経路が検出されるまでＲＲＥＱパケットをブロードキャスト及び転送することが伴う。この間に生成されるアプリケーションパケットの全ては発信元ノードにバッファされるので、宛先が数ホップ離れている場合、通常、この経路探索に伴い大きな遅延時間が存在する。以下に記載の実施形態には、効率的に宛先への経路を探索するとともに、経路の検出に伴う遅延時間を低減するためのシステム及び方法が含まれる。
【００１８】
「オンデマンド経路制御プロトコルによる無線ネットワークにおけるアクセス・ポイント又はゲートウェイに対する連続的な接続性を達成するためのシステム及び方法（Sys tem And Method For Achieving Continuous Connectivity To An Access Point Or Gateway In A Wireless Network Following An On-Demand Routing Protocol ）」と題された２００３年１月１３日出願の関連する米国特許仮出願第６０／４３９，４４９号、「無線ネットワークにおけるスムース・ハンドオフの達成及び単向性リンクの除去のためにＡＯＤＶを修正するシステム及び方法（System And Method For Modifying AODV To Facilitate Smooth Handoffs And Eliminate Unidirectional Links In A Wireless Network ）」と題された２００３年１月１３日出願の米国特許仮出願第６０／４３９，４５５号、及び「オンデマンド経路制御プロトコルによる無線ネットワークにおけるアクセス・ポイント又はゲートウェイに対する連続的な接続性を達成するため、及びネットワークの固定端末間における移動体端末のスムース・ハンドオフを実行するためのシステム及び方法（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 Terminals Between Fixed Terminals In The Network ）」と題された２００４年１月１３日出願の米国特許出願第１０／７５５，３４６号の記載のように、通常、ノードはそのノードに関連するＩＡＰへの経路を保持し、ＩＡＰはそのＩＡＰに関連する全てのノードへの経路を保持する。これらの各々の全内容を引用により本明細書に援用する。
【００１９】
そのようなシステムのＩＡＰは、１つのＳＤのためのパケットをそのＳＤに関連するＩＡＰに対し転送することが可能であるように、バックボーン又は何らかの他の種類のリンクを通じて他のＩＡＰデバイスとの接続性を有すると仮定される。一例を図１に示す。
【００２０】
図１は、本発明の一実施形態によるシステム及び方法を実施する第１の位置におけるアドホック・ネットワーク内の接続の一例を示す概念的なブロック図である。図１に示すネットワーク１００は、加入者装置であるＳＤ１〜ＳＤ５、ＩＡＰデバイスであるＩＡＰ１〜ＩＡＰ４、及び一連の通信リンク１２０を備える。図２は、図１に示した加入者装置ＳＤ及びＩＡＰの一例のブロック図である。
【００２１】
上述にて参照したメイヤーによる米国特許第５，９４３，３２２号明細書、並びに米国特許出願第０９／８９７，７９０号明細書、米国特許出願第０９／８１５，１５７号明細書、及び米国特許出願第０９／８１５，１６４号明細書の記載のように、ＳＤ及びＩＡＰは各々、相互に直接的に通信可能であること、又はノード間にて送信されるパケットのための経路制御装置として動作する１つ以上の他のノードを介して通信可能であることが当業者には認められ得る。図２に示すように、各ＳＤ及びＩＡＰはトランシーバ１０２を備えることが可能である。トランシーバ１０２はアンテナ１０４に接続されており、コントローラ１０６の制御により、パケット化された信号などの信号をＳＤ及びＩＡＰに対し受発信することが可能である。パケット化されたデータ信号には、例えば、音声、データ、又はマルチメディア情報と、ノード経路制御及び更新情報を含むパケット化された制御信号とが含まれ得る。
【００２２】
各ＳＤ及びＩＡＰはさらに、ランダム・アクセス・メモリ（ＲＡＭ）などのメモリ１０８を備えることが可能であり、他の情報に加え、自身及びネットワークの他のノードに属する経路制御情報を記憶することが可能である。経路制御広告と称されるように、新たなノードがネットワークに参加する（ｅｎｔｅｒ）時、又はネットワークの既存ノードが移動する時など種々の期間において、ＳＤ及びＩＡＰは、それぞれの経路制御情報をブロードキャスト機構を介して定期的に相互に交換する。
【００２３】
図２に示すように、一部のノードは、ノートブック・コンピュータ端末、移動体電話機、移動体データ装置、又は任意の他の適切なデバイスなど、任意数のデバイスからなるホスト１１０を備えることが可能である。また、各ＳＤ及びＩＡＰは、インターネット・プロトコル（ＩＰ）及びアドレス解決プロトコル（ＡＲＰ）を用いるために、適切なハードウェア及びソフトウェアを備えることが可能である。ＩＰ及びＡＲＰを用いる目的は、当業者には容易に認められ得る。伝送制御プロトコル（ＴＣＰ）及びユーザ・データグラム・プロトコル（ＵＤＰ）を用いるための適切なハードウェア及びソフトウェアも含まれてよい。これに加え、各ノードは、以下に記載の本発明の実施形態によるローカル配布プロトコルを含む、自動再送要求（ＡＲＱ）機能及び媒体アクセス制御（ＭＡＣ）を用いるための適切なハードウェア及びソフトウェアのプロトコルを含む。
【００２４】
ＩＡＰは、ＡＲＰ−ＲＡＲＰ機構又は経路制御を用い、宛先に関連する特定のＩＡＰを発見することが可能であるため、その特定のＩＡＰに対し転送することが可能である。続いて他のＩＡＰが、その宛先に対する転送を担う。以下の例においては、ノードがネットワーク内に存在するか否かをＩＡＰが認識することが可能であるとも仮定する。ＩＡＰにより保持されるこの経路に関する認識は、以下に記載の実施形態において用いられる。
【００２５】
データパケットがホストからトランシーバへ送信される時、トランシーバは、宛先がメッシュ・ネットワーク内であるか、又はメッシュ・ネットワーク外であるかを判定する。宛先がネットワーク外（例えば、ワールド・ワイド・ウェブ上）である場合、パケットはＩＡＰに対して送信される。このプロトコルでは、関連するＩＡＰへの経路がプロアクティブに（ｐｒｏａｃｔｉｖｅｌｙ）保持されるため、この伝送はいかなるバッファリング／遅延時間も伴うことなく達成される。宛先がネットワーク内であると判定された場合、宛先への最適経路を検出するための作業が行われる。宛先への経路が経路表に存在し、且つ有効である場合、パケットは宛先に向けて次ホップに対し転送される。宛先への経路が経路表に存在しない場合、関連するＩＡＰに対しパケットが転送されるとともに、宛先アドレスを含む「状態要求」と呼ばれる特別なメッセージがそのＩＡＰに対し送信される。
【００２６】
この「状態要求」を受信すると、関連するＩＡＰは、その関連するＩＡＰの経路表にそのノードが存在するか否かを認識するために、その関連するＩＡＰの経路表を参照する。上述のように、ＩＡＰは、そのＩＡＰに関連する全てのノードへの経路を有する。また、ＩＡＰは、そのＩＡＰに関連しない幾つかの他のノードへの幾つかの経路も有する。経路が存在する場合、関連するＩＡＰは「状態応答」と呼ばれる特別なメッセージに「成功ビット」を添えて送り返し、経路が存在しない場合、「成功ビット」を外した「状態応答」を送信する。
【００２７】
「成功ビット」の添えられた「状態応答」を受信すると、ＡＯＤＶの記載のように、ＳＤは、ＩＡＰへのホップ数に等しい最大ＴＴＬを用いて、宛先に対する拡張リングサーチを開始する。この例では、最大ＴＴＬがＩＡＰへのホップ数その他の関数であることも可能である。ＲＲＥＱ自身が宛先に到達した時、又は宛先への「充分に新しい（ｆｒｅｓｈ  ｅｎｏｕｇｈ）」経路を有する中間ノードを介してＲＲＥＱが宛先に到達した時、経路が判定され得る。「充分に新しい」経路は、関連シーケンス番号がＲＲＥＱに含まれるシーケンス番号以上である、有効な経路エントリである。ＲＲＥＱの発信元に対し「経路応答（ＲＲＥＰ）」をユニキャストして返すことにより、この経路は利用可能となる。要求を受信する各ノードは、その発信元へのパスに沿って宛先から、又は要求を満足させることが可能な任意の中間ノードから同様に、ＲＲＥＰをユニキャストすることが可能であるように、要求の発信元へ戻る経路をキャッシュ（ｃａｃｈｅ）する。
【００２８】
ＲＲＥＰを受信すると、発信元ノードは経路表を更新するとともに、新たに検出された経路の使用を開始する。その際、「経路要求」パケットのフラッディングはＩＡＰレベルにおいて停止するので、制御不能となることはない。これにより、そうしたネットワークが広範囲に渡る場合のオーバヘッドは有意に減少される。また、ネットワーク中に渡る経路探索が行われる場合、ネットワーク中に存在しない宛先ノードのため重度のオーバヘッドが生じ得るが、これにより、その可能性も除去される。
【００２９】
ＩＡＰが「状態応答」又は「状態誤り」のメッセージを待機する間、発信元ノードはＩＡＰへパケットを送信し続ける。このため、ＳＤのトランシーバにはパケットがバッファされない。「状態ビット（ｓｔａｔｕｓ  ｂｉｔ）」の外された「状態応答」が到達した場合、ＩＡＰが「状態誤り」と呼ばれる特別なメッセージを受信しない限り、そのノードは関連するＩＡＰへパケットを送信し続ける。そのようなメッセージを生じ得るイベントを以下で説明する。
【００３０】
宛先アドレスを含むＩＡＰは「状態要求」メッセージを受信すると、宛先への無線経路を有するか否かを検出するために、トランシーバの経路表を探査する。探査が成功でない場合、ＩＡＰは宛先に関連するＩＡＰを特定することを試みる。これには、ＩＡＰのホストの経路表における経路ルックアップ（ｌｏｏｋ  ｕｐ）、若しくはＡＲＰキャッシュのルックアップを用いること、又はその他適切な方法を用いることが可能である。宛先に関連するＩＡＰの検出が不可能であるためパケットの転送が不可能であるとＩＡＰが判定した場合、そのＩＡＰは発信元ノードに対する「状態誤り」メッセージを生成する。
【００３１】
上述のメッセージの内容には、以下に限定されないが、以下を含めることが可能である。
「状態要求」パケット
１．発信元ノードのアドレス
２．宛先ノードのアドレス
３．「発見ビット（Ｆｉｎｄ  Ｂｉｔ）」（下述）
「状態応答」パケット
１．発信元ノードのアドレス
２．宛先ノードのアドレス
３．状態ビット
４．「発見済みビット（Ｆｏｕｎｄ  Ｂｉｔ）」（下述）
「状態誤り」パケット
１．誤りメッセージを送信するＩＡＰのアドレス
２．発信元ノードのアドレス
３．宛先ノードのアドレス
デバイス間を流通する任意の他のメッセージにより、同じ情報を伝達することも可能である。宛先がメッシュ・ネットワークの内部であるか、又は外部であるかをトランシーバが判定することが不可能な場合にも、経路を検出するために、上述の「状態要求」及び「状態応答」の方法が用いられる。
【００３２】
本発明のシステム及び方法の好適な実施形態に対し、幾つかの変形形態が存在し得る。「オンデマンド」プロトコルによるネットワークにおいては、隣接表の隣接するノードに対する隣接エントリを有することが可能であるが、経路表のそのノードに対する経路エントリを有することは不可能である。これは、隣接に関して有効なシーケンス番号を有しないことなど、幾つかの理由のためである。
【００３３】
したがって、第１の変形形態では、ノードは宛先ノードが隣接ノードであることを認識し、さらにその宛先ノードのための経路を検出する必要がある。そのような場合には、ＩＡＰに対する「状態要求」メッセージを開始しＩＡＰに対するパケットの送信を開始する前に、宛先に対するＲＲＥＱを送信することが好適である。ＲＲＥＱはブロードキャスト又はユニキャストであることが可能である。
【００３４】
ブロードキャストの場合には、ＲＲＥＱはいずれのノードによっても転送されない。「経路応答」が受信された場合、上述の処理を完了させる必要はない。誤った隣接の情報、移動、又は出力損のため、「経路応答」が受信されない場合が生じ得るが、その場合、ノードは上述の処理に従うことが可能であり、又は、この宛先を当面到達不可能な宛先として宣言するとともに、後に再試行することが可能である。したがって、続く手段において幾つかの変形形態が存在し得る。
【００３５】
第２の変形形態では、ＩＡＰに対し「状態要求」メッセージ及びデータパケットを同時に送信する代わりに、「状態応答」又は「状態誤り」の待機中、発信元ノードがパケットをバッファすることも可能である。この方法では、一時的な非最適経路を通じてパケットが送信されることはない。以下の例において、このことをより詳細に説明する。
【００３６】
図１に示したネットワーク１００において、１２０−１〜１２０−ｎの線は、ＳＤ及びＩＡＰデバイス間の接続性を表している。したがって、ＳＤ１はＳＤ２及びＳＤ４の隣接ＳＤである。以下の例ではＳＤ１を発信元ノード、ＳＤ５を宛先ノードとするが、しかしながら、ネットワーク１００においては任意の数のノード構成が存在し得る。この例においては、全てのＳＤデバイス（ＳＤ１〜ＳＤ５）はＩＡＰ１に関連すると仮定する。また、この例では、ＳＤ１はＩＡＰに到達するためにＳＤ２を用いること、ＳＤ５はＩＡＰに到達するためにＳＤ３を用いること、及びＩＡＰはＳＤ１及びＳＤ５に到達するために逆の経路を用いることも仮定する。図１のネットワーク１００における１つの通信例では、アプリケーションがＳＤ１からＳＤ５への通信のためのパケットの生成を開始すると即座に、ＳＤ１のトランシーバはＩＡＰに対するパケットの送信を開始するとともに、「状態要求」メッセージの発行を行う。今度はＩＡＰがＳＤ５に対しパケットを転送するとともに、「状態ビット」の添えられた「状態応答」メッセージを用いて応答する。この場合、ノードＳＤ１によりローカル「経路探索」処理が完了されるまで、パケットは４ホップの非最適経路（すなわち、ＳＤ１〜ＳＤ２〜ＩＡＰ〜ＳＤ３〜ＳＤ５）を通じて運ばれる。ローカル「経路探索」処理が完了された時、ＳＤ４を通じる２ホップの経路（すなわち、ＳＤ１〜ＳＤ４〜ＳＤ５）が得られる可能性が最も高い。
【００３７】
したがって、第２の変形形態では、「状態応答」又は「状態誤り」の待機中、ＩＡＰに対しパケットを送信しないことにより、この一時的な非最適経路（すなわち、ＳＤ１〜ＳＤ２〜ＩＡＰ〜ＳＤ３〜ＳＤ５）の利用を回避する。しかしながら、第２の実施形態においてパケットの送信が遅延することは、一部のアプリケーションには好ましくない。また、第２の実施形態においてはＳＤ１のトランシーバに大きなバッファ空間も必要である。
【００３８】
第３の変形形態では、ノードはＩＡＰに対しパケットを送信する前、又は任意の「状態要求」メッセージを送信する前に、最初にローカル「経路探索」を行うことが可能である。この変形形態では、発信元ノードは最初に宛先に対するローカル「経路探索」処理を行う。例えば、発信元ノードは、ＩＡＰへのホップ数に等しい最大ＴＴＬを用いて拡張リングサーチを行う。最大ＴＴＬはＩＡＰへのホップ数その他の関数であることも可能である。ノードが「経路応答」メッセージを受信した場合、そのノードは宛先に対するパケットの送信を開始する。１回以上の試行の後に応答が受信されない場合、ノードは、そのノードが使用した最大ＴＴＬにより決定される近傍に、宛先ノードが存在しないことを安全に判定することが可能である。
【００３９】
この点において、通常、ノードは宛先に対しパケットを送信するためにＩＡＰを用いる必要がある。これは、以下の２つの手法により達成可能である。
第１の手法では、ノードがローカル「経路探索」に失敗したことを判定すると、ノードがＩＡＰに対するパケットの送信を開始することが可能となる。ネットワーク内に宛先ノードが現在存在することを示すＩＡＰからの「状態誤り」メッセージを受信した場合のみ、ノードは停止する。
【００４０】
第２の手法では、ノードはＩＡＰに対する特別なメッセージ、又は「発見ビット」の添えられた「状態要求」メッセージを送信し、ネットワークに宛先ノードが存在するか否かを検出することが可能である。ＩＡＰはメッセージを受信すると、そのＩＡＰのホストの経路表又はＡＲＰキャッシュに問合せを実行し、又はその他適切な方法を実行し、宛先ノードに関連するＩＡＰを検出することが可能である。宛先ノードに関連するＩＡＰの検出にＩＡＰが成功することにより、宛先ノード自体の検出に成功した場合、そのＩＡＰは「発見済みビット」の添えられた「状態応答」メッセージを送信することにより、そのことを示す。成功しない場合、ＩＡＰは「状態誤り」メッセージを送信する。
【００４１】
「発見済みビット」の添えられた「状態応答」メッセージが発信元ノードにより受信された場合、そのノードは、ＩＡＰによる宛先ノードに関連する適切なＩＡＰへの転送のため、そのＩＡＰに対するパケットの送信を開始する。「状態誤り」メッセージが受信された場合、ノードは、その宛先を当面到達不可能な宛先として宣言するとともに、後に再試行することが可能である。第３の変形形態においてもやはり、経路の検出に伴う遅延時間が存在し、パケットがバッファされる必要もある。
【００４２】
第４の変形形態では、ノードは「状態要求」、「状態応答」、及び「状態誤り」など特別なメッセージを用いる代わりに、他のメッセージを用いて同じ情報を伝達する。例えば、一般にＩＰアドレス、ＭＡＣアドレスなどを発見するには、ノードは関連するＩＡＰに対しＤＮＳ、ＡＲＰ、またはその両方の問合せを送信する必要がある。関連するＩＡＰは、そうしたメッセージを受信すると、特別な種類のメッセージを送信し、宛先ノードがそのＩＡＰに関連するか否か、或いは、宛先ノードがネットワーク内に存在するか否かを示すことが可能である。また、この情報を含むように、ＤＮＳ応答に関するＡＲＰを変更することも可能である。これにより「状態」メッセージは不要となる。上述のように、そうした情報を探索するための幾つかの方法が存在し得る。
【００４３】
上述の本発明の変形形態により幾つかの利点が提供される。経路検出に関する遅延時間は少なく、ＳＤのトランシーバにおけるパケットのバッファは不要である。宛先が隣接に存在することが認識されている場合にのみ「経路探索」処理が開始されるので、必要な経路制御オーバヘッドは少ない。また、本発明によりネットワークのスケーラビリティ（ｓｃａｌａｂｉｌｉｔｙ）も増大する。
【００４４】
本発明の幾つかの例示的実施形態のみを上述にて詳細に説明したが、本発明の新規な教示及び利点から実質的に逸脱することなく、例示的実施形態において多くの修正が可能であることを当業者は容易に認めるであろう。したがって、そのような修正の全ては、以下の特許請求の範囲において規定される本発明の範囲の内に包含されることを意図するものである。
【図面の簡単な説明】
【００４５】
【図１】本発明の一実施形態によるシステム及び方法を実施する第１の位置におけるアドホック・ネットワーク内の接続の一例を示す概念的なブロック図。
【図２】図１に示す無線ノードの一例のブロック図。
【図１】
0004505454.tif 000002
【図２】
0004505454.tif 000003