(57)【要約】例えば８０２．１１ネットワークの様な、多重ホップ無線アドホック通信ネットワーク（１００）内の、潜在的隠れノード問題を識別するためのシステム並びに方法である。このシステム並びに方法はそれぞれの各ノード（１０２）の近隣間の関係を評価し、それぞれのデータ・パケット受信能力が隠れノードにより悪影響を受ける可能性のある無線アドホック通信ネットワーク（１００）のノード（１０２，１０４，１０６）を識別して、これらの潜在的問題ノード（１０２，１０４，１０６）がデータ・パケットが含まれた経路をルーティング用に選択されることを回避する。特に、各ノード（１０２，１０４，１０６）に関して、このシステムならびに方法は１つのノードと近隣との間の関係を識別するノード測定基準を生成する。各ノード（１０２，１０４，１０６）は次に自身のそれぞれの測定基準を自身のルーティング通知データと共に送信して、他のノードがそのノードが直面するであろう潜在的隠れノード問題の次数にアクセス出来るようにし、他のノードへデータ・パケットをルーティングするためにその潜在的問題ノードを使用することを回避して選択出来るようにしている。
2005522940.tif 000002
【特許請求の範囲】
【請求項１】
アドホック通信ネットワーク内のノード間通信に悪影響を与える隠れノードを識別するための方法であり、前記ネットワークが該ネットワーク内の他のノードとの間で信号を送受信するように適合された複数のノードを含む前記方法であって：
前記複数ノードの少なくとも１つに対して第１近隣ノード集合を計算し、前記第１近隣ノード集合に含まれる少なくとも１つの近隣ノードに対して第２近隣ノードを計算し、
前記少なくとも１つのノードに対する隠れノード値の次数を、第１および第２近隣ノード集合に基づいて計算し、前記計算値をルーティング通知の一部として通信する、以上を含む前記方法。
【請求項２】
請求項１記載の方法が更に：
前記第１近隣ノード集合が前記少なくとも１つのノードの各近隣ノードを含むように計算し、前記各近隣ノードは前記少なくとも１つのノードが直接通信出来る前記複数ノードの１つを含む、前記方法。
【請求項３】
請求項１記載の方法が更に：
前記第１近隣ノード集合を前記少なくとも１つの近隣ノードへ通信することを含む、前記方法。
【請求項４】
請求項１記載の方法が更に：
前記第２近隣ノード集合が前記少なくとも１つの近隣ノードの各近隣ノードを含むように計算し、前記各近隣ノードは前記少なくとも１つの近隣ノードが直接通信出来る前記複数ノードの１つを含む、前記方法。
【請求項５】
請求項１記載の方法が更に：
前記第２近隣ノード集合を前記少なくとも１つのノードへ通信することを含む、前記方法。
【請求項６】
請求項１記載の方法が更に：
第３近隣ノード集合が、前記第１近隣ノード集合に含まれ、また前記第２近隣ノードに含まれる近隣ノードではない、各近隣ノードを含むように計算することを含む、前記方法。
【請求項７】
請求項６記載の方法が更に：
副近隣ノードである前記第３近隣ノード内の含まれる各近隣ノードを配置し、前記副近隣ノードは前記第３ノード集合に含まれる少なくとも１つの近隣ノードで、前記第３近隣ノード集合内に含まれる少なくとも１つの他の近隣ノードと直接通信出来る近隣ノードを含み、
少なくとも１つの副近隣ノードの多数を、前記第３近隣ノード集合内の単一代表近隣ノードに結合することを含む、前記方法。
【請求項８】
請求項７記載の方法が更に：
前記隠れノード値の次数を前記第３近隣ノード集合に基づき計算することを含む、前記方法。
【請求項９】
請求項１記載の方法が更に：
前記多数の各ノードに対する隠れノード値の前記次数を計算し、
発信元ノードから宛先ノードへの少なくとも１つの送信ルートを、少なくとも１つの前記隠れノード値の次数に基づいて計算することを含む、前記方法。
【請求項１０】
請求項１記載の方法が更に：
少なくとも１つの送信ルートを、前記隠れノード値の次数に基づき、ルーティング・アルゴリズムを介して計算することを含む、前記方法。
【請求項１１】
アドホック通信ネットワーク内のノード間通信に悪影響を与える隠れノードを識別するためのシステムであり、前記ネットワークが該ネットワーク内の他のノードとの間で信号を送受信するように適合された複数のノードを含む前記システムであって：
前記複数ノードの少なくとも１つに対して、第１近隣ノード集合を計算するように適合された第１ノードを含み、
前記第１ノードが更に、前記第１近隣ノード集合に含まれる少なくとも１つの近隣ノードに対して、第２近隣ノード集合を計算するように適合され、
前記第１ノードが更に、前記少なくとも１つのノードに対する隠れノード値の次数を、前記第１および第２近隣ノード集合に基づいて計算し、前記計算値をルーティング通知の一部として通信するように適合されている、前記システム。
【請求項１２】
請求項１１記載のシステムにおいて：
前記第１ノードが、前記第１近隣ノード集合が前記少なくとも１つのノードの各近隣ノードを含むように計算するように適合され、前記各近隣ノードは前記少なくとも１つのノードが直接通信出来る前記複数ノードの１つを含む、前記システム。
【請求項１３】
請求項１１記載のシステムにおいて：
前記第１ノードが、前記第１近隣ノード集合を前記少なくとも１つの近隣ノードに通信するように適合されている、前記システム。
【請求項１４】
請求項１１記載のシステムにおいて：
前記第１ノードが、前記第２近隣ノード集合が前記少なくとも１つのノードの各近隣ノードを含むように計算するように適合され、前記各近隣ノードは前記少なくとも１つのノードが直接通信出来る前記複数ノードの１つを含む、前記システム。
【請求項１５】
請求項１１記載のシステムにおいて：
前記第１ノードが、前記第２近隣ノード集合を前記少なくとも１つのノードに通信するように適合されている、前記システム。
【請求項１６】
請求項１１記載のシステムにおいて：
前記第１ノードが、第３近隣ノード集合が前記第１近隣ノード集合に含まれるが、前記第２近隣ノード集合には含まれない近隣ノードではない各近隣ノードに含まれるように計算するように適合された、前記システム。
【請求項１７】
請求項１６記載のシステムにおいて：
前記第１ノードが、副近隣ノードである前記第３近隣ノード集合内に含まれる各近隣ノードを配置するように適合され、前記副近隣ノードは前記第３ノード集合に含まれ、前記第３近隣ノード集合内に含まれる少なくとも１つのその他の近隣ノードと直接通信出来る、少なくとも１つの近隣ノードを含み、
前記第１ノードが更に、少なくとも１つの副近隣ノードの多数を、前記第３近隣ノード集合内の単一の代表近隣ノードに組み合わせるように適合されている、前記システム。
【請求項１８】
請求項１７記載のシステムにおいて：
前記第１ノードが前記隠れノード値の次数を、前記第３近隣ノード集合に基づいて計算するように適合されている、前記システム。
【請求項１９】
請求項１１記載のシステムにおいて：
第１ノードが前記多数の各ノードに対する前記隠れノード値の次数を計算するように適合され、
前記第１ノードが更に、発信元ノードから宛先ノードへの少なくとも１つの送信ルートを、少なくとも１つの前記隠れノード値の次数に基づいて計算するように適合されている、前記システム。
【請求項２０】
請求項１１記載のシステムにおいて：
前記第１ノードが、少なくとも１つの送信ルートを前記隠れノード値の次数に基づき、ルーティング・アルゴリズムにより計算するように適合された、前記システム。
【請求項２１】
アドホック通信ネットワーク内のノード間通信に悪影響を与える隠れノードを識別するように適合された、命令のコンピュータ読み取り可能媒体であって、前記ネットワークは前記ネットワーク内の他のノードとの間で信号を送受信するように適合された複数のノードを含む前記コンピュータ読み取り可能媒体が：
前記多数のノードの少なくとも１つに対する第１近隣ノード集合を計算するように適合された、命令の第１の集合と、
前記第１近隣ノード集合内に含まれた、少なくとも１つの近隣ノードに対する第２近隣ノード集合を計算するように適合された、命令の第２集合と、
前記少なくとも１つのノードに対する隠れノード値の次数を前記第１および第２近隣ノード集合に基づき計算し、前記値をルーティング通知の一部として通信するように適合された命令の第３集合とを含む、前記コンピュータ読み取り可能媒体。
【請求項２２】
請求項２１記載のコンピュータ読み取り可能媒体において：
前記命令の第１集合が、前記第１近隣ノード集合が前記少なくとも１つのノードの各近隣ノードを含むように計算するよう適合されており、前記各近隣ノードが前記少なくとも１つのノードが直接通信可能な前記複数のノードを含む、前記コンピュータ読み取り可能媒体。
【請求項２３】
請求項２１記載のコンピュータ読み取り可能媒体において：
前記命令の第１集合が、前記第１近隣ノード集合を前記少なくとも１つの近隣ノードに通信するように適合されている、前記コンピュータ読み取り可能媒体。
【請求項２４】
請求項２１記載のコンピュータ読み取り可能媒体において：
前記命令の第２集合が、前記第２近隣ノード集合が前記少なくとも１つのノードの各近隣ノードを含むように計算するよう適合されており、前記各近隣ノードが前記少なくとも１つのノードが直接通信可能な前記複数のノードを含む、前記コンピュータ読み取り可能媒体。
【請求項２５】
請求項２１記載のコンピュータ読み取り可能媒体において：
前記命令の第２集合が、前記第２近隣ノード集合を前記少なくとも１つのノードへ通信するように適合されている、前記コンピュータ読み取り可能媒体。
【請求項２６】
請求項２１記載のコンピュータ読み取り可能媒体において：
前記命令の第３集合が、第３近隣ノード集合が各近隣ノードを含むように計算するように適合されており、各近隣ノードは前記第１近隣ノードには含まれるが前記第２近隣ノード集合には含まれない近隣ノードを含む、前記コンピュータ読み取り可能媒体。
【請求項２７】
請求項２６記載のコンピュータ読み取り可能媒体において：
前記命令の第３集合が、副近隣ノードである前記第３近隣ノード集合内に含まれる各近隣ノードを配置するように適合され、前記副近隣ノードは前記第３近隣ノード集合内に含まれる少なくとも１つの他の近隣ノードと直接通信可能な前記第３ノード集合内に含まれる少なくとも１つの近隣ノードを含み、
前記命令の第３集合が更に、少なくとも１つの副近隣ノードの多数を、前記第３近隣ノード集合内の単一の代表近隣ノードに結合するように適合されている、前記コンピュータ読み取り可能媒体。
【請求項２８】
請求項２７記載のコンピュータ読み取り可能媒体において：
命令の第３集合が、前記隠れノード値の次数を前記第３近隣ノード集合に基づき計算するように適合されている、前記コンピュータ読み取り可能媒体。
【請求項２９】
請求項２１記載のコンピュータ読み取り可能媒体において：
前記命令の第３集合が前記多数の各ノードに対する隠れノード値の前記次数を計算するように適合され、
命令の第４集合が、発信元ノードから宛先ノードへの少なくとも１つの送信ルートを、少なくとも１つの隠れノード値の前記次数に基づき計算するように適合されている、前記コンピュータ読み取り可能媒体。
【請求項３０】
請求項２９記載のコンピュータ読み取り可能媒体において：
前記命令の第４集合が前記少なくとも１つの送信ルートを、前記隠れノード値の次数に基づき、ルーティング・アルゴリズムにより計算するように適合されている、前記コンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、８０２．１１ネットワークの様な多重ホップ無線アドホック通信ネットワーク内の、潜在的隠れノード問題を識別するためのシステム並びに方法に関する。更に詳細には、本発明はデータ・パケット受信能力が隠れノード問題により悪影響を受ける可能性のある、無線アドホック通信ネットワーク内のノードを識別するためのシステム並びに方法に関し、これはデータ・パケットをルーティングするためにそれらの潜在的に問題のあるノードを含む経路が選択されることを回避するためである。本明細書は、米国仮特許出願シリアル番号第６０／３７１，７１８号、名称「潜在的問題ノードをルート選択から回避するために、多重ホップ無線アドホック・ネットワーク内の潜在的隠れノード問題を識別するためのシステム並びに方法」、２００２年４月１２日申請、および米国特許出願シリアル番号第１０／２９８，５４２号、２００２年１１月１９日申請からの利益を主張し、これらの内容は此処に挙げることで組み込まれ参照されている。
【背景技術】
【０００２】
近年、「アドホック」ネットワークとして知られている型式の移動体通信ネットワークが開発されてきている。この型式のネットワークでは、各々の使用者端末（以降「移動体ノード」）が基地局または他の移動体ノード用のルータとして動作することが可能であり、従って基地局の固定インフラストラクチャの必要性を無くしている。従って、発信元移動体ノードから宛先移動体ノードへ送られるデータ・パケットは、典型的に宛先移動体ノードに届くまでに多数の中間移動体ノードを通して回送される。
【０００３】
更に複雑なアドホック・ネットワークもまた開発されており、これは従来型アドホック・ネットワークと同様に移動体ノードが互いに通信出来ることに加えて、更に移動体ノードが固定ネットワークに接続することも可能であり、従って他の使用者端末、例えば公衆電話交換網（ＰＳＴＮ）上およびインターネットの様な他のネットワーク上の使用者端末に接続することが可能である。これらの型式のアドホック・ネットワークの詳細は米国特許出願シリアル番号第０９／８９７，７９０号、名称「ＰＳＴＮおよびセルラ・ネットワークとインタフェースするアドホック・ピアツーピア移動体無線接続システム」、２００１年６月２９日申請、米国特許出願シリアル番号第０９／８１５，１５７号、名称「個別予約チャンネルを具備した共有並列データ・チャンネルへの調整チャンネル接続を有する、アドホック・ピアツーピア無線ネットワーク用、時分割プロトコル」、２００１年３月２２日申請、および米国特許出願シリアル番号第０９／８１５，１６４号、名称「アドホック・ピアツーピア移動体無線接続システム用、優先順位付けルーティング」、２００１年３月２２日申請に記載されており、前記特許出願の各々の内容は此処に参照することで組み込まれている。
【０００４】
当業者には理解されるように、１つのノードがパケット化データを宛先ノードに送信する際、このノードはそのルーティング表を確認してその宛先ノードが自身のルーティング表に含まれているか否かを判定する。その宛先ノードがそのノードのルーティング表に含まる場合、そのデータはその宛先ノードに繋がる経路を介して送信される。その宛先ノードがそのノードのルーティング表内にリストアップされていない場合、そのパケットはそのノードのルーティング表内にリストアップされている１つまたはいくつかのその他のノードに送られ、これらのその他のノードはその宛先表が彼らのルーティング表内にリストアップされているか否かを判定する。この処理工程はそのデータ・パケットが完全に宛先ノードに到達するまで継続される。
【０００５】
更に当業者には理解されるように、「隠れノード」問題はこれらの型式のアドホック・ネットワーク内の媒体接続プロトコル（MAC : Medium Access Protocol）では古典的な問題である。この問題は、２つの無線機（ノード）が互いの有効通信範囲外に居る一方で、両者共これまたそのネットワークに参加している中間ノードの有効通信範囲内に居る時に生じる。そのネットワーク内の２つの無線機がその中間ノードにほぼ同時刻に通信しようと試みると、それらの信号は、受信機となろうとしていた中間ノードで衝突するかそして／またはパケット汚染を引き起こす。この場合、２つの外部ノードは互いに他から「隠れ」ている。
【０００６】
従って、この隠れノード問題は中間ノードでパケット配送を成功する機会を減少させる。また、中間ノードの周りに隠れノードが多ければ多いほど、パケット衝突が厳しくなる。
【０００７】
従って、無線アドホック通信ネットワーク内で隠れノード問題に直面するノードを効果的かつ効率的に識別し、これらのノードを通るルーティングを可能な限り回避するためのシステムならびに方法に対する要求が存在する。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
本発明の１つの目的は、無線アドホック通信ネットワーク内で隠れノード問題に直面するノードを効果的かつ効率的に識別するためのシステムおよび方法を提供することである。
【０００９】
本発明の別の目的は、各々のノードに対して複数の近隣ノード集合の配置および評価を行い、各ノードに存在する隠れノードの次数を計算するためのシステム並びに方法を提供することである。
【００１０】
本発明の更に別の目的は、送信ルート選択内で使用するためのルーティング通知として、各ノードでの隠れノード存在次数を通信するためのシステム並びに方法を提供することである。
【００１１】
本発明の更に別の目的は、高い隠れノード存在次数を通知するノードを避けてネットワーク内を通る少なくとも１つの送信ルートを計算するためのシステム並びに方法を提供することである。
【課題を解決するための手段】
【００１２】
本発明のこれら、およびその他の目的は、例えば８０２．１１ネットワークの様な、多重ホップ無線アドホック通信ネットワーク内の、潜在的隠れノード問題を識別するためのシステム並びに方法を提供することで、実質的に実現される。このシステム並びに方法はそれぞれ各々のノードと近隣との間の関係を評価して、そのデータ・パケット受信能力が隠れノード問題の悪影響を受けるノードを識別し、この様な潜在的問題ノードを含む経路選択をデータ・パケットのルーティング用に選択することを回避する。
【発明の効果】
【００１３】
特に、各ノードに対して本システム並びに方法は、１つのノードとその近隣との間の関係を識別するノード測定基準を生成する。第１近隣ノードの集合が対象ノードに対して計算され、その後近隣ノードの集合が第１近隣ノードの集合に含まれる各々のノードに対して計算される。第１近隣ノードの集合内に存在するが、各々の後続ノードの集合内に存在しないノードが、それぞれ対象ノードに関する潜在的隠れノードの集合内に組み込まれる。この値は他のノードに、ルーティング通知の中で測定基準として通信されるので、他のノードはそのノードが直面するであろう潜在的隠れノード問題の次数にアクセスすることができ、その潜在的問題ノードを他のノードへデータ・パケットをルーティングする際に使用することを回避するために使用できる。
【００１４】
本発明のこれらおよびその他の目的、特長および新奇な機能は、添付図を参照して以下の詳細な説明を読むことにより、更に容易に理解されるであろう。
【実施例】
【００１５】
図１は本発明の１つの実施例を採用した、アドホック・パケット交換無線通信ネットワーク１００の例を図示するブロック図である。特に、ネットワーク１００は複数の移動体無線使用者端末１０２−１から１０２−ｎ（一般的にノードまたは移動体ノード１０２と呼ぶ）と、固定ネットワーク１０４への接続をノード１０２に対して提供する、複数のアクセスポイント１０６−１、１０６−２．．．１０６−ｎ（一般的にノードまたはアクセスポイント１０６と呼ぶ）を有する固定ネットワーク１０４を含む。固定ネットワーク１０４は例えば、コア・ローカル接続ネットワーク（ＬＡＮ）、複数のサーバおよびゲートウェイ・ルータを含み、これによりノード１０２に対して他のネットワーク、例えば他のアドホック・ネットワーク、公衆電話交換網（ＰＳＴＮ）およびインターネットへの接続を提供する。ネットワーク１００は更に、他のノード１０２，１０６または１０７との間でデータ・パケットをルーティングするための複数の固定ルータ１０７−１から１０７−ｎ（一般的に固定ルータ１０７と呼ぶ）を含む。
【００１６】
当業者には理解されるように、ノード１０２，１０６および１０７互いに直接通信したり、またはノード１０２の間で送信されるデータ・パケットの１つまたは複数のルータとして機能している、１つまたは複数の他のノード１０２，１０６または１０７を介して通信することが可能であり、これらはメイヤー（Mayor）に付与された米国特許第５，９４３，３２２号、これは此処にも参照して組み込まれている、および先に参照した米国特許明細書シリアル番号第０９／８９７，７９０号、第０９／８１５，１５７号および第０９／８１５，１６４号に記載されている。特に、図２に示すように各ノード１０２，１０６および１０７はトランシーバ１０８を含み、これはアンテナ１１０に接続されていて、パケット化されたデータ信号の様な信号を、ノード１０２，１０６または１０７との間で、制御装置１１２の制御のもと、受信および送信することが出来る。パケット化されたデータ信号には、例えば音声、データまたはマルチメディアが含まれる。
【００１７】
各ノード１０２，１０６および１０７は更に、ランダム・アクセス・メモリ（ＲＡＭ）の様なメモリ１１４を含み、これはなかんずくネットワーク１００内の自分自身および他のノード１０２，１０６または１０７に属するルーティング情報を格納することが出来る。加えて、或るノード、特にノード１０２は加入者装置ホスト（図示せず）を含むことが可能で、これは任意の数の装置、例えばノート型コンピュータ端末、移動体電話機、移動体データ・ユニット、パーソナル・コンピュータ（ＰＣ）、パーソナル・データ支援装置（ＰＤＡ）、または任意の他の好適な装置で構成される。
【００１８】
音声、データおよびマルチメディア・パケット化データ信号に加えて、ノード１０２，１０６および１０７は、ルーティング通知またはルーティング表情報と呼ばれるそれぞれのルーティング情報を交換し、これは互いにブロードキャスト機構を介して定期的に、例えば新たなノード１０２がネットワーク１００に入った時、またはネットワーク１００内の既存のノード１０２が移動した時に行われる。ノード１０２，１０６または１０７はそのルーティング表の更新をブロードキャストし、近隣のノード１０２，１０６または１０７は、ブロードキャストしたノード１０２，１０６または１０７のブロードキャスト範囲（例えば無線周波数（ＲＦ）範囲）内の場合にのみ、ブロードキャストされたルーティング表更新を受信する。例えば、ノード１０２−１および１０２−６がノード１０２−３がルーティング表情報をブロードキャストした時に、ノード１０２−３のＲＦブロードキャスト範囲内に居たと仮定すると、現在の表情報はノード１０２−１および１０２−６の両方で受信されファイルされる。しかしながら、ノード１０２−２，１０２−４および１０２−５がノード１０２−３のブロードキャスト範囲の外に居る場合、これらのノードは現在の表情報ブロードキャストを受信しない。
【００１９】
ネットワーク１００内の各ノード１０２，１０６または１０７はまた、上記の背景の章で説明した隠れノード問題に直面する。次に図３に関連して説明するように、本発明の１つの実施例はノード１０２，１０６または１０７が直面するであろう潜在的隠れノード問題の次数を識別するための技術を提供し、これにより他のノード１０２，１０６および１０７がネットワーク１００を通してデータ・パケットをルーティングするためのルーティング経路を選択する際に、その様なノードを含むことを回避できる。
【００２０】
本発明の１つの実施例によれば、無線アドホック・ネットワーク１００は、性能低下を示す、ネットワークの悪化領域を回避するための或る測定基準を使用する。好ましくは、多重ホップ・アドホック・ルーティング・ネットワーク１００は、発信元ノードから宛先ノードへ選択されたルーティング経路が最大の帯域幅、最少待ち時間、そして最大のパケット配信率を保証するように構築できる。本発明の実施例はネットワーク１００のノードがルーティング測定基準を確立できるようにして、これはそれらのノードが、ネットワーク１００内の高い次数の隠れノードを含む領域を通してパケットをルーティングすることを防止している。この実施例に関して、対象ノードに於ける「隠れノードの次数」という記述的な用語は、そのノードに関して存在する隠れノードの個数を指している。
【００２１】
上記の様に、多重ホップ無線アドホック・ルーティング・ネットワーク１００内で、ノード１０２，１０６および１０７から送信されるルーティング通知は、他の全てのノード１０２，１０６および１０７またはそのノードが直接通信する近隣ノードに対して、通知する。加えて、ノード１０２，１０６および１０７から送信されるルーティング通知は、典型的にそのノードから直接到達することの出来る全ての宛先、および間接的に到達できる宛先、その宛先に到達するためにそのパケットが配送されなければならない中間ノードリスト、を通知する。次に説明するように、本発明の１つの実施例は１つのノードから送信された近隣ノード・ルーティング通知を調べ、そのノードが直面する潜在的隠れ問題を評価する。
【００２２】
図３は、ネットワーク１００内のノード１０２，１０６および１０７の任意の組み合わせからなる４つのノード、それらはノードａ，ｂ，ｃおよびｄと識別されている、間の関係１１６例を図示する概念図である。ノードａ，ｂ，ｃおよびｄ間の線は近隣関係を示している。例えば、ノードａはノードｂおよびｃと近隣であり、ノードｂはノードａおよびｃと近隣で、ノードｄはノードｃと近隣であり、そしてノードｃはノードａ，ｂおよびｄと近隣である。ノードａの近隣の集合は集合Ａと示される。エンティティーａは集合Ａで示される近隣のリスト内に含まれる。図３に示されるネットワーク１００の部分に関して、各ノードの近隣リストは次のようになる：
【００２３】
【数１】
2005522940.tif 000003
【００２４】
ノードｃを対象ノードと仮定すると、本発明の１つの実施例に基づくノードｃに関する隠れノードを識別するための技術は以下の通りである：
【００２５】
最初に、本発明の実施例は対象ノードｃに隣接する全てのノードを、ノードｃから送信されるルーティング通知、この場合ノード集合Ｃを含む、に基づいて識別する。各々の隣接ノードに対して、ノードｃから送信されたルーティング通知と各近隣ノードの近隣リストとの間で比較が行われる。特に、ノードｃからの近隣リストがノードａで受信されると、集合Ａが集合Ｃと比較される。ノードｃからの近隣リストがノードｂで受信されると、集合Ｂが集合Ｃと比較され、ノードｃからの近隣リストがノードｄで受信されると、集合Ｄが集合Ｃと比較される。各比較に基づき、各集合内の共有されていないノードが決定される。これは各集合比較の対称差でありこの例では次の通りである：
【００２６】
【数２】
2005522940.tif 000004
【００２７】
これらの集合の合同はノードｃの潜在的隠れノードの全てを表す。上記のネットワークに対するノードｃの潜在的隠れノードのこの集合はPcとして知られ、これは次を含む：
【００２８】
【数３】
2005522940.tif 000005
次にこの集合内の要素数が決定され、これはこの例では |Pc|=3 と決定され、これはそのネットワークに関するノードｃの潜在的隠れノードの個数を表す。
【００２９】
互いの近隣、または副近隣である潜在的隠れノード集合 Pc の全ての要素が決定される。この例では、ノードａ，ｂおよびｃが潜在的隠れノード集合 Pc の要素である。ノードａ，ｂおよびｃの中でノードａおよびｂのみが副近隣である。これらのノードは次に、ノードｃに関する隠れノードの新たな集合の中で、単一登録 a_b として取り扱われる：
【００３０】
【数４】
2005522940.tif 000006
故に
2005522940.tif 000007
である。
従って、ノードｃに関する隠れノードの次数は２である。
【００３１】
ノードａ，ｂおよびｃは全て互いに近隣であるので、通常調整がそれらの間で行われ、これらは同時に媒体にアクセスしようと試みてはいけない。従って、ノードａおよびｂからの隠れノードへの寄与は単一ノードの隠れノード寄与として減少されるが、これらが協調しているからである。ｃに関する隠れノードの次数（すなわち２）は、互いに他を意識せずノードｃで干渉を引き起こしかねない移動体ノードまたは無線機の数を表す。
【００３２】
上記の本発明の実施例の中で、ネットワーク１００内の各ノード１０２，１０６および１０７の隠れノードの次数は上記の通り決定される。次に各ノードはそれぞれの自身の測定基準を他のルーティング情報と共に、上記の方法で通知する。例えば各ノードの制御装置１１２で実施されるルーティング・アルゴリズムは、各ノードの測定基準を使用してより小さな隠れノード次数を有するノードを含む送信経路を選択することが出来る。従って、これはそのノードの隠れノードの影響によるパケットの衝突または遅延の可能性を最少とする。
【００３３】
上記より理解されるように、本発明の実施例はルート内のリンク品質の直接測定に注目した以前の技術には相反して、そのルートに沿った大きな次数の隠れノードによる悪化を引き起こす、無線アドホック・ルーティング・ネットワーク内のルートを識別し回避することを助けることが出来る。本発明の実施例は従って、直接リンク品質を評価することの出来ない無線機を含むネットワーク内で、高い隠れノード干渉の領域を予測することが出来る。
【００３４】
加えて、例えば８０２．１１の様な移動体ノードで使用される無線基準には、高い次数の隠れノードが存在する場合、他の基準よりも更に貧弱な性能を示すものがある。特に、８０２．１１基準は、アドホック節電モードで、隠れノードが存在する場合データ送信が出来なくなるか、またはその能力を大きく減少させる状況に直面する可能性がある。その様な場合、従来のリンク品質直接測定は、選択されたルートで直面する完全な悪化条件を反映しない。従って、アドホック節電アルゴリズムと隠れノードとの間の相乗効果が起きると、ほとんどのトラヒックがその領域を通して成功裏に回送出来なくなる場合、高い容量を持たなければならないその様な領域が現れる事が考えられる。しかしながら、上記の本発明の実施例は、特に高い次数の隠れノードを有する領域を識別できるので、ルーティング・アルゴリズムはその様な領域を通るルートを、例えその領域が高いノード容量を持っているように見えたとしても、回避するためにその様な判定を使用する。
【００３５】
当業者には理解されるように、本発明の実施例はピアツーピア・モード中の８０２．１１装置およびその他の直接ピアツーピア通信を可能とする任意のその他の無線装置と同様に、古典的隠れノード問題を被る他の無線ルーティング・ネットワークでも採用できる。
【００３６】
本発明の極僅かの実施例のみを詳細に説明してきたが、当業者には本発明の新奇な教えおよび特長から実質的に逸脱することなく、実施例内で多くの修正変更が可能であることが容易に理解されよう。従って、その様な全ての修正変更は、添付の特許請求の範囲で定義された本発明の範囲内に含まれるものと意図する。
【図面の簡単な説明】
【００３７】
【図１】図１は本発明の１つの実施例に基づき、ネットワーク内のそれぞれのノードが直面する隠れノード問題の次数を識別するためのシステムならびに方法を採用した、アドホック無線通信ネットワークの１例の概念的ブロック図である。
【図２】図２は図１に示すネットワーク内で採用された１つのノードの構成要素例を図示するブロック図である。
【図３】図３は図１に示すネットワーク内の１つのノードとその近隣ノードとの間の１つの関係例を表す概念図であり、本発明の１つの実施例に基づく、ノードが直面する潜在的隠れノード問題の次数を評価するための技術の例を示す。
【図１】
2005522940.tif 000008
【図２】
2005522940.tif 000009
【図３】
2005522940.tif 000010
【国際調査報告】
2005522940.tif 000011
2005522940.tif 000012