(57)【要約】  ソースノードが複数のデスティネーションノードと通信するよう動作可能なマルチノード通信ネットワークにおけるノード選択方法が提供される。本方法は、（ａ）前記ソースノードから前記デスティネーションノードに第１メッセージを送信するステップと、（ｂ）前記デスティネーションノードの１以上からの１以上のレスポンスメッセージを前記ソースノードにおいて受信するステップと、（ｃ）前記ソースノードにおいて受信される１以上のレスポンスメッセージの間に競合が発生した場合、前記１以上のレスポンスメッセージが競合することなく前記ソースノードにおいて受信されるまで、前記ソースノードにおける受信用の１以上のレスポンスメッセージを再送する前記複数のデスティネーションノードのサブセットを繰り返し選択するステップとを有し、前記競合することなく受信される１以上のレスポンスメッセージは、適切なデスティネーションノードが選択されたことを示す。本方法は、ネットワークを高いＱｏＳによってより信頼性のあるものにするため通信ネットワークにおいて実行可能である。
2010503308.tif 000002
【特許請求の範囲】
【請求項１】
ソースノードが複数のデスティネーションノードと通信するよう動作可能なマルチノード通信ネットワークにおけるノード選択方法であって、
（ａ）前記ソースノードから前記デスティネーションノードに第１メッセージを送信するステップと、
（ｂ）前記デスティネーションノードの１以上からの１以上のレスポンスメッセージを前記ソースノードにおいて受信するステップと、
（ｃ）前記ソースノードにおいて受信される１以上のレスポンスメッセージの間に競合が発生した場合、前記１以上のレスポンスメッセージが競合することなく前記ソースノードにおいて受信されるまで、前記ソースノードにおける受信用の１以上のレスポンスメッセージを再送する前記複数のデスティネーションノードのサブセットを繰り返し選択するステップと、
を有し、
前記競合することなく受信される１以上のレスポンスメッセージは、適切なデスティネーションノードが選択されたことを示す方法。
【請求項２】
前記ステップ（ｃ）は、ツリー分割プロセスを介し前記複数のデスティネーションノードの徐々に小さくなるサブセットを繰り返し選択することを含み、
前記複数のデスティネーションノードの徐々に小さくなるサブセットは、前記選択される適切なデスティネーションノードに収束する、請求項１記載の方法。
【請求項３】
前記ステップ（ｃ）は、前記複数のデスティネーションノードのサブセットを繰り返し選択するため、キャプチャプロセスを適用することを含み、
前記キャプチャプロセスは、前記複数のデスティネーションノードにおいて受信される最初のメッセージと、前記ソースノードにおいて受信される１以上のレスポンスメッセージの少なくとも１つの信号パワーの指標に応答する、請求項２記載の方法。
【請求項４】
前記キャプチャプロセスは、前記ソースノードから前記１以上のデスティネーションノードに１以上のメッセージを送信するステップを含み、
前記１以上のメッセージは、受信したメッセージのパワーに関する情報を含む、請求項３記載の方法。
【請求項５】
前記キャプチャプロセスは、前記信号パワーの指標と前記複数のデスティネーションノードの１以上における１以上の閾値パワーパラメータとを比較するステップを含む、請求項３記載の方法。
【請求項６】
前記１以上の閾値パワーパラメータは、１以上のメッセージが前記ソースノードから前記複数のデスティネーションノードの１以上に送信されることに応答して、変更される可能性がある、請求項５記載の方法。
【請求項７】
前記最初のメッセージはＲＴＳ（Ｒｅｑｕｅｓｔ−Ｔｏ−Ｓｅｎｄ）メッセージであり、前記１以上のレスポンスメッセージはＣＴＳ（Ｃｌｅａｒ−Ｔｏ−Ｓｅｎｄ）メッセージであり、
当該方法はさらに、（ｄ）前記ステップ（ｃ）において競合が解消され、前記適切なデスティネーションノードが選択されることに応答して、前記ソースノードから前記適切なデスティネーションノードにデータメッセージを送信し、その後に前記ソースノードにおいて前記適切なデスティネーションノードから送信される対応するアクノリッジメントメッセージを受信するステップを有する、請求項１記載の方法。
【請求項８】
前記最初のメッセージはデータメッセージであり、前記１以上のレスポンスメッセージはアクノリッジメントメッセージである、請求項１記載の方法。
【請求項９】
互いの間でメッセージを通信するよう動作可能なソースノードと複数のデスティネーションノードとを有するノード通信ネットワークであって、
前記ソースノードと前記複数のデスティネーションノードとは、請求項１記載の方法に従って機能するよう動作可能であるノード通信ネットワーク。
【請求項１０】
請求項１記載の方法を実現することを支援するソフトウェアを実行するよう動作可能な計算ハードウェアを有する通信ノード。
【請求項１１】
データキャリア上のソフトウェアであって、当該ソフトウェアは、計算ハードウェア上で実行されると、請求項１記載の方法を実現することを支援するよう処理可能であるソフトウェア。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワークなどの通信ネットワークにおけるノード選択方法に関する。さらに、本発明はまた、当該方法に従って機能するよう動作するノードネットワークに関する。さらに、本発明は、当該方法を実現するため計算ハードウェア上で実行可能なソフトウェアプロダクトに関する。
【背景技術】
【０００２】
無線通信ネットワークなどの共有媒体を利用するネットワークにおいて、信頼性のある通信を提供すること、すなわち、信頼性のあるＱｏＳ（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ）を提供することは、困難であることが知られている。対応する有線通信システムと異なって、無線通信システムは、パスロス、シャドーイング、フェーディングなどの伝搬効果を受ける傾向がある。さらに、このような効果は、位置に依存し、時間可変的なものである。これらの効果は、オーディオ／ビデオストリーミング及びカンファレンシングなどの時間が重要となるアプリケーションの無線システムの設計を極めて困難なものにする。
【０００３】
ダイバーシチを利用することによって、より信頼できる通信が無線ネットワークにおいて達成可能であることが知られている。例えば、送信ノードと複数の協力ノードとを有する無線ネットワークにおける通信の信頼性は、送信ノードからのデータ通信についてベストな即時通信チャネルを示すことが可能なネットワークにおける協力ノードを選択することによって向上される。しかしながら、このようなネットワークに対する満足いく所望の動作特性を提供するため、発生からの許容できない通信オーバヘッドを回避するよう、ベストな即時通信チャネルを提供するための協力ノードの選択が極めて迅速に実行されることが重要である。
【０００４】
無線ネットワークにおけるダイバーシチは、ネットワークの送信機が意図された受信機だけでなくその近傍の受信機にもまた送信するよう動作可能であるという理由から生じる。無線ネットワーク内で確立された無線チャネルは、実質的に相関のない方法により位置及び時間に可変的な通信性質を有する。
【０００５】
無線などの共有通信媒体を利用する通信システムでは、バーチャルセルラーネットワーク（ＶＣＮ）が、第１の技術文献“Ｖｉｒｔｕａｌ  Ｃｅｌｌｕｌａｒ  Ｎｅｔｗｏｒｋ：Ａ  Ｎｅｗ  Ｗｉｒｅｌｅｓｓ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ａｒｃｈｉｔｅｃｔｕｒｅ  ｗｉｔｈ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ  Ｐｏｒｔｓ”（ｐｐ．２８７−３０７，ｖｏｌ．１０，ｎｏ．３，Ｗｉｒｅｌｅｓｓ  Ｐｅｒｓｏｎａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，１９９９）に報告されるように提案されている。ＶＣＮは、それが単一の移動局からの送信を受信する複数の協力アクセスポイント（ＡＰ）を利用するという点で、従来のワイヤレスローカルエリアネットワーク（ＷＬＡＮ）と区別される。ＶＣＮでは、移動局から複数のＡＰへの通信パスが独立しているため、アップリンク送信のロウバスト性を向上させるため、空間ダイバーシチがパケット単位で動的に適用される可能性がある。しかしながら、ＡＰがアップリンク送信を協力して受信することが可能となるように、各種プロトコルが提案されてきた。ＩＥＥＥ８０２．１１に準拠しながらＶＣＮを適用する際に生じる主要なチャレンジは、協力ＡＰのタイムリーな選択と、送信元の移動局に対する対応するタイムリーなアクノリッジメントに関する。
【０００６】
第２の技術文献“Ｇｅｏｇｒａｐｈｉｃａｌ  Ｒａｎｄｏｍ  Ｆｏｒｗａｒｄｉｎｇ（ＧｅＲａＦ）  ｆｏｒ  Ａｄ  Ｈｏｃ  ａｎｄ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ：Ｅｎｅｒｇｙ  ａｎｄ  Ｌａｔｅｎｃｙ  Ｐｅｒｆｏｒｍａｎｃｅ”（Ｍｉｃｈｅｌｅ  Ｚｏｒｚｉ  ａｎｄ  Ｒａｍｅｓｈ  Ｒｏａ，ｐｐ．３４９−３５１，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｍｏｂｉｌｅ  Ｃｏｍｐｕｔｉｎｇ，ｖｏｌ．２，ｎｏ．４，Ｏｃｔｏｂｅｒ−Ｄｅｃｅｍｂｅｒ  ２００３）では、（ａ）各自の空間位置を決定可能なセンサノードと、（ｂ）メッセージに明示的に含まれる送信ノードから送信されるメッセージの最終的な送信先と送信ノードの位置とに依存するセンサネットワーク及びアドホックネットワークが記載される。
【０００７】
このような記載されたネットワークでは、メッセージを受信する、すなわち、メッセージを“聞く”ノードは、当該メッセージの中継として動作する際に自らの優先度を評価可能である。さらに、当該ネットワークにおいてメッセージを受信するすべてのノードは、任意的には、自らの優先度に応じてメッセージの中継として動作可能である。このような動作方法は、ベストな空間的に位置するノードがメッセージの中継として動作させる。さらに、中継として動作するノードの事前的選択のため、ノード位置情報が十分であるため、各ノードにおいてトポロジカル情報又はルーティングテーブルは必要でない。このようなネットワークにおける地理的ルーティングは、ノードの調整なしのアクティブ化又は非アクティブ化を可能にする。さらに、ルーティング、ＭＡＣ及びトポロジー管理は、当該ネットワークに関する単一の制御レイヤに統合される可能性がある。
【０００８】
上記第２の技術論文に記載されるネットワークでは、所与の非アクティブ化されたノードがデータパケットを送信することが要求されるとき、当該ノードはまずアクティブ化され、ある期間２つのキャリア周波数における送信をモニタする。当該ノードがこれらの２つのキャリア周波数の何れかにおいて送信が行われていることを特定すると、すなわち、周波数が“ビジー”であるとき、当該ノードは断念し、以降にデータパケットを送信する試みを再スケジューリングする。他方、当該ノードが期間中に両方の周波数において送信が行われていないと特定すると、ＲＴＳ（Ｒｅｑｕｅｓｔ−Ｔｏ−Ｓｅｎｄ）メッセージを送信し、当該ノードに通信近傍にある潜在的な中継ノードからのＣＴＳ（Ｃｌｅａｒ−Ｔｏ−Ｓｅｎｄ）メッセージを以降のタイムスロットにおいて聴取する。ＲＴＳメッセージのエンドに続く各ＣＴＳスロットでは、所与のノードは以下のステップを実行する。
（ａ）所与のノードにおいて１つのＣＴＳメッセージしか受信されない場合、当該ノードは、ＣＴＳメッセージを発信した中継ノードに対するＣＴＳコンファメーションとして機能する最初の部分を有するデータパケットの送信をスタートする。
（ｂ）所与のノードにおいてＣＴＳメッセージが受信されない場合、当該ノードは、継続メッセージを送信し、Ｎｐ個のエンプティＣＴＳタイムスロットの後のタイムアウトの下でＣＴＳメッセージを聴取する。又は、
（ｃ）所与のノードによって意味のあるメッセージでない信号が聞かれた場合、メッセージ衝突が発生したと想定され、当該ノードは衝突解決アルゴリズムを呼び出すための衝突メッセージを送信するよう動作可能であり、その後に、当該ノードは再びＣＴＳメッセージを聴取する。
【０００９】
所与のノードからのデータパケットの送信後、当該ノードは、即座のアクノリッジメント（ＡＣＫ）メッセージを受信することを予想する。当該ＡＣＫメッセージが受信されると、当該ノードが、メッセージ送信が成功し、それの非アクティブ化状態を再開する。
【００１０】
上記に教示される既知の無線通信ネットワークは、協力ノード間の競合と、データメッセージの受信をアクノリッジし、データメッセージを転送する好適なノードの選択を決定する際、協力ノード間におけるメッセージ衝突を可能な限り回避するという設計原理を共有している。このような設計原理は、これら既知のネットワークが適切な通信信頼性、すなわち、上述したＱｏＳを提供する難しさをもたらす大きなオーバヘッドを受けるという短所を有している。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本発明の課題は、より小さなＱｏＳの低下によりネットワークのノード間の競合を解消するノード通信ネットワークにおけるノード選択方法を提供することである。
【課題を解決するための手段】
【００１２】
本発明の第１の特徴によると、ソースノードが複数のデスティネーションノードと通信するよう動作可能なマルチノード通信ネットワークにおけるノード選択方法であって、
（ａ）前記ソースノードから前記デスティネーションノードに第１メッセージを送信するステップと、
（ｂ）前記デスティネーションノードの１以上からの１以上のレスポンスメッセージを前記ソースノードにおいて受信するステップと、
（ｃ）前記ソースノードにおいて受信される１以上のレスポンスメッセージの間に競合が発生した場合、前記１以上のレスポンスメッセージが競合することなく前記ソースノードにおいて受信されるまで、前記ソースノードにおける受信用の１以上のレスポンスメッセージを再送する前記複数のデスティネーションノードのサブセットを繰り返し選択するステップと、
を有し、
前記競合することなく受信される１以上のレスポンスメッセージは、適切なデスティネーションノードが選択されたことを示す方法が提供される。
【００１３】
本発明は、通信ネットワークのノード間の処理において生じる競合が適切に選択されたノードによってより効果的に解消できるという効果を有する。
【００１４】
任意的には、前記ステップ（ｃ）は、ツリー分割プロセスを介し前記複数のデスティネーションノードの徐々に小さくなるサブセットを繰り返し選択することを含み、前記複数のデスティネーションノードの徐々に小さくなるサブセットは、前記選択される適切なデスティネーションノードに収束する。このような徐々に小さくなる選択は、最も適したデスティネーションノードへの繰り返しと、潜在的に競合を引き起こす可能性のある関係するデスティネーションノードの個数を減少させる可能性がある。小さくする選択は、アルゴリズムのためのノードの選択に利用されるキャプチャ効果と相乗的に組み合わされたツリー分割アルゴリズムを介し効果的に実現される。
【００１５】
任意的には、前記ステップ（ｃ）は、前記複数のデスティネーションノードのサブセットを繰り返し選択するため、キャプチャプロセスを適用することを含み、前記キャプチャプロセスは、前記複数のデスティネーションノードにおいて受信される最初のメッセージと、前記ソースノードにおいて受信される１以上のレスポンスメッセージの少なくとも１つの信号パワーの指標に応答する。キャプチャプロセスは、ソースノードから受信されたデータメッセージを伝送するのに適さないノードを排除することができ、これにより、メッセージ競合を引き起こすよう潜在的に動作しうるデスティネーションノードをより少なくすることができる。
【００１６】
より任意的には、本方法において、前記キャプチャプロセスは、前記ソースノードから前記１以上のデスティネーションノードに１以上のメッセージを送信するステップを含み、前記１以上のメッセージは、受信したメッセージのパワーに関する情報を含む。受信したメッセージのパワーは、より適切なデスティネーションノードを選択するため上述したキャプチャプロセスを実現するのに利用される有用な指標である。
【００１７】
より任意的には、本方法では、前記キャプチャプロセスは、前記信号パワーの指標と前記複数のデスティネーションノードの１以上における１以上の閾値パワーパラメータとを比較するステップを含む。１以上の閾値パワーパラメータの使用は、より適切なデスティネーションノードを選択するため、便利なバイナリサーチプロセスを提供する。
【００１８】
より任意的には、本方法では、前記１以上の閾値パワーパラメータは、１以上のメッセージが前記ソースノードから前記複数のデスティネーションノードの１以上に送信されることに応答して、変更される可能性がある。これにより、本方法は、ソースノードと共にデスティネーションノードに関する動作条件を考慮することができ、より適切なデスティネーションノードのサブセットが提供される。
【００１９】
任意的には、本方法では、前記最初のメッセージはＲＴＳ（Ｒｅｑｕｅｓｔ−Ｔｏ−Ｓｅｎｄ）メッセージであり、前記１以上のレスポンスメッセージはＣＴＳ（Ｃｌｅａｒ−Ｔｏ−Ｓｅｎｄ）メッセージであり、当該方法はさらに、（ｄ）前記ステップ（ｃ）において競合が解消され、前記適切なデスティネーションノードが選択されることに応答して、前記ソースノードから前記適切なデスティネーションノードにデータメッセージを送信し、その後に前記ソースノードにおいて前記適切なデスティネーションノードから送信される対応するアクノリッジメントメッセージを受信するステップを有する。
【００２０】
任意的には、本方法では、前記最初のメッセージはデータメッセージであり、前記１以上のレスポンスメッセージはアクノリッジメントメッセージである。
【００２１】
本発明の第２の特徴によると、互いの間でメッセージを通信するよう動作可能なソースノードと複数のデスティネーションノードとを有するノード通信ネットワークであって、前記ソースノードと前記複数のデスティネーションノードとは、本発明の第１の特徴による方法に従って機能するよう動作可能であるノード通信ネットワークが提供される。
【００２２】
本発明の第３の特徴によると、本発明の第１の特徴による方法を実現することを支援するソフトウェアを実行するよう動作可能な計算ハードウェアを有する通信ノードが提供される。
【００２３】
本発明の第４の特徴によると、データキャリア上のソフトウェアであって、当該ソフトウェアは、計算ハードウェア上で実行されると、本発明の第１の特徴による方法を実現することを支援するよう処理可能であるソフトウェアが提供される。
【００２４】
本発明の各特徴は、添付した請求項により規定されるような本発明の範囲から逸脱することなく、何れかの組み合わせにより組み合わせ可能であることが理解されるであろう。
【図面の簡単な説明】
【００２５】
本発明の実施例が、添付した図面を参照して例示により説明される。
【図１】図１は、本発明に従って動作可能なシンプルな通信ネットワークを示す。
【図２】図２は、本発明による通信方法を説明するためのシンプルなネットワークにおけるメッセージ交換を示す。
【図３】図３は、本発明の方法によるデータ通信を実現するためのツリー分割アルゴリズムを補完するためキャプチャ効果が利用される本発明によるプレ選択方法を示す。
【図４】図４は、本発明によるポスト選択方法を示す。  添付した図面では、下線の番号は、下線の番号が配置されるアイテム又は隣接するアイテムを表すのに利用される。下線のない番号は、当該番号とアイテムとを結び付けるラインによって特定されるアイテムに関する。番号が下線が付けられず、係る矢印を伴うとき、下線のない番号は、矢印が指し示している全体的なアイテムを特定するのに利用される。
【発明を実施するための形態】
【００２６】
概略的に、本発明は、データのソースノードとして又は当該データを受信する協力ノードとして機能するよう動作可能なノードに関するマルチノード通信ネットワークに関する。メッセージを交換する際、ノードが同期していないとき、メッセージ衝突のリスクが発生しうる。このような衝突を解消するため、本発明は、衝突を効率的に解決するよう動作可能な分割ツリーベースアルゴリズムを利用する。分割ツリーベースアルゴリズムは、このようなネットワーク内で衝突が発生することを許容し、アイドリング、通信成功又はさらなる衝突が発生したか示すフィードバックによって衝突を解決することによって機能する。
【００２７】
原理的には、ネットワークＮは送信機Ｔ１〜Ｔｎを有する。添え字ｎは、１より大きな整数である。送信機Ｔ１〜Ｔｎは、受信機Ｒに対して互いに競合するよう動作しうる。まず、送信機Ｔ１〜Ｔｎのすべてが、時間的なメッセージの衝突が発生するように、受信機Ｒに第１メッセージＭを送信する。受信機Ｒは、衝突が発生したことを示すフィードバックを送信機Ｔ１〜Ｔｎに与えることによって応答する。このようなフィードバックは、例えば、フィードバック信号の欠落を含む可能性がある。このようなフィードバックに応答して、送信機Ｔ１〜Ｔｎのそれぞれは、各自の最初のメッセージＭを受信機Ｒに再送するか否か個別にランダムに計算する。ここで、送信機Ｔ１〜Ｔｎは２つのグループに分割される。すなわち、各自の第１メッセージＭを再送するよう動作可能な送信機Ｔ１〜Ｔｋのプライマリ第１グループＧ１，１と、各自の第１メッセージＭの再送を拒否するよう動作可能な送信機Ｔｋ＋１〜Ｔｎのプライマリ第２グループＧ１，２とである。送信機Ｔ１〜Ｔｋのプライマリ第１グループＧ１，１は、その後に受信機Ｒに各自の第１メッセージＭを再送する。メッセージ衝突が発生しない場合、受信機Ｒは、第１グループＧ１，１のうち最も速い又は強力な送信機Ｔとの通信リンクを確立する。他方、第１メッセージＭの再送に１以上のメッセージ衝突が発生した場合、上記個別計算により、送信機Ｔ１〜Ｔｋのプライマリ第１グループＧ１，１を２つのセカンダリグループにさらに分割する。すなわち、第１メッセージＭの再送を繰り返すよう動作可能な送信機Ｔ１〜Ｔｍのセカンダリ第１グループＧ２，１と、第１メッセージＭの再送を繰り返すよう動作可能な送信機Ｔｍ＋１〜Ｔｋのセカンダリ第２グループＧ２，２とである。さらなるメッセージ衝突に直面した場合、同様の方法によるさらなる分割が行うことができる。
【００２８】
本発明は、衝突がノードを選択し、上述した分割ツリーアルゴリズムを用いて衝突を解消するプリフェーズ中に行われることを効果的に可能にすることによって、メッセージ衝突を処理する既知のアプローチと区別される。すなわち、ＲＴＳメッセージが、１つのソースと送信先としての複数の受信機とがある予約フェーズ中の以降のメッセージ衝突を招くよう意図的に送信される。このため、本発明は、複数のノードからのＣＴＳレスポンスを招き、その結果としてあえてメッセージ衝突を生じさせるＲＴＳメッセージを利用する。さらに、本発明は、ある形式のキャプチャ効果を利用して、このようなツリー分割アルゴリズムを相乗的に高速化する点で特徴付けされる。媒体アクセス問題を受ける従来のネットワークでは、例えば、より大きな電磁放射を行う強力に通信するノードは、過度に大きな媒体アクセス時間をキャプチャする可能性がある。本発明では、このようなキャプチャ効果特性は、上述したツリー分割アルゴリズムの処理を加速させるため利用される。
【００２９】
キャプチャ効果がさらに、図１を参照して説明される。図１では、シンプル無線ネットワークが１０により全体的に示される。ネットワーク１０は、２０（Ｒ）により示される受信機を有し、受信機２０は、受信機２０におけるＳＩＮＲ（Ｓｉｇｎａｌ−ｔｏ−Ｉｎｔｅｒｆｅｒｅｎｃｅ−Ｎｏｉｓｅ−Ｒａｔｉｏ）閾値Ｈを超える大きさを有する場合、そこでの信号受信をキャプチャするよう動作可能である。このため、送信機３０，４０，５０（Ｔ１，Ｔ２，Ｔ３）から受信機２０（Ｒ）への２以上の同時的な送信は、式１（Ｅｑ．１）により記述されるように、送信機３０（Ｔ１）からの送信が送信機４０，５０（Ｔ２，Ｔ３）からの送信のＥ（Ｐ２＋Ｐ３）とバックグラウンドノイズＮの和より実質的に高い電力Ｐ１を有する場合、受信機２０（Ｒ）において信号衝突を発生させない。
【００３０】
【数１】
2010503308.tif 000003
本発明は、例えば、無線ネットワークなどの媒体アクセスが共有されているネットワークにおけるメッセージ衝突を処理するための効率的で直接的な方法を提供するため、図２に示されるようなキャプチャ効果と上述したツリー分割アルゴリズムの相乗的な組み合わせを提供する。しかしながら、本発明は、無線ネットワークのみに限定されるものでなく、媒体共有された他の形式のネットワークにおいて利用可能である。
【００３１】
図２を参照するに、ノードネットワークの一部が１００により全体的に示される。ネットワーク１００は、ソースノード１１０（Ｓ）と、３つの協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）などの複数の協力ノードとを含む。ソースノード１１０と協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の１以上は、任意的に、矢印１８０により示される他のネットワークノード（図示せず）に接続される。さらに、ソースノード１１０（Ｓ）と、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）とは、例えば、無線放射伝搬パスなどの無線通信リンク１５０，１６０，１７０を介し相互接続される。任意的には、このような無線通信リンク１５０，１６０，１７０は、ＩＥＥＥ８０２．１１などの通信規格に準拠している。
【００３２】
それらの間でデータを通信するためのノード１１０，１２０，１３０，１４０（Ｓ，Ｃ１，Ｃ２，Ｃ３）の処理が、図２を参照して説明される。第１ステップ２００において、ソースノード１１０（Ｓ）は、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）が受信するのに適したフォーマットによりＲＴＳメッセージ２１０を送信する。ＲＴＳメッセージ２１０は、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）において受信するため、それぞれ通信リンク１５０，１６０，１７０を介し伝搬する。協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は相互調整されていないか、又は動作について同期されていないため、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のそれぞれは、ソースノード１１０（Ｓ）における受信のため通信リンク１５０，１６０，１７０を介しそれぞれＣＴＳメッセージ３１０ａ，３１０ｂ，３１０ｃ（ＣＴＳ１，ＣＴＳ２，ＣＴＳ３）を即座に送信することによって、第２ステップ３００においてＲＴＳメッセージ２１０の受信に応答する。
【００３３】
協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の所与のノードが、それのメッセージ３１０がその他の協力ノードのものと比較して最初にかつ最も強力にソースノード１１０（Ｓ）において受信されるように、それの通信リンクを介しそれのＣＴＳメッセージ３１０を送信するよう動作可能である場合、当該ノードは、上述されるようにキャプチャされ、ソースノード１１０（Ｓ）が通信を確立した協力ノードとなることが受け入れられる。例えば、協力ノード１３０（Ｃ２）は、協力ノード１２０，１４０（Ｃ１，Ｃ３）と比較して、それのＣＴＳ２メッセージ３１０ｂにより最も強力かつ迅速に応答し、第３ステップ４００に移行して、ソースノード１１０（Ｓ）にデータパケット（ＤＡＴＡ）４１０を協力ノード１３０（Ｃ２）に送信させる。
【００３４】
しかしながら、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）がソースノードにおいて実質的に同時にかつ実質的に互いに同様の強度により受信されるように、各自のＣＴＳ１，ＣＴＳ２，ＣＴＳ３メッセージ３１０ａ，３１０ｂ，３１０ｃを送信するよう動作可能である場合、メッセージの衝突が発生し、すなわち、競合が発生し、ソースノード１１０（Ｓ）はそれのデータパケット（ＤＡＴＡ）４１０を送信するよう応答開始することができなくなる。協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の何れかにおけるこのような衝突におけるデータパケット（ＤＡＴＡ）４１０の欠落から以降の非受信において、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のそれぞれは、競合が発生したことをデータパケット（ＤＡＴＡ）４１０が示す場合、受信欠落し、それのＣＴＳ１，ＣＴＳ２，ＣＴＳ３メッセージ３１０ａ，３１０ｂ，３１０ｃをそれぞれソースノード１１０（Ｓ）に再送すべきか確率分布に従って計算する。協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３は、これにより２つのグループに分割される。すなわち、（ａ）各自のＣＴＳメッセージ３１０を再送しないよう計算する協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のプライマリ第１グループ５２０と（例えば、プライマリ第１グループ５２０は協力ノード１４０（Ｃ３）を有する）と、（ｂ）各自のＣＴＳメッセージ３１０を再送するよう計算する協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のプライマリ第２グループ５１０（例えば、プライマリ第２グループ５１０は協力ノード１２０，１３０（Ｃ１，Ｃ２）を有する）とである。
【００３５】
図２に示される第４ステップ５００では、プライマリ第１グループ５１０の協力ノード１２０，１３０（Ｃ１，Ｃ２）のそれぞれは、各自のＣＴＳ１，ＣＴＳ２メッセージ３１０ａ，３１０ｂをソースノード１１０（Ｓ）に再送する。協力ノード１２０，１３０（Ｃ１，Ｃ２）の１つが、協力ノード１２０，１３０（Ｃ１，Ｃ２）の他方より、ソースノード１１０（Ｓ）においてより迅速かつ強力に受信されるように、それのＣＴＳメッセージ３１０を送信する場合、ソースノード１１０（Ｓ）は、データパケット（ＤＡＴＡ）４１０を受信するプライマリ第１グループ５２０のより迅速な協力ノードを、図１を参照して上述されるようにキャプチャすることができる。しかしながら、協力ノード１２０，１３０（Ｃ１，Ｃ２）が、ソースノード１１０（Ｓ）において実質的に同時にかつ実質的に互いに同様の強度により受信されるように、各自のＣＴＳ１，ＣＴＳ２メッセージ３１０ａ．３１０ｂを送信するよう動作可能である場合、応答においてソースノード１１０（Ｓ）がそれのデータパケット（ＤＡＴＡ）４１０を送信開始することができない結果によって、さらなるメッセージの衝突が発生する。第２グループ５１０の協力ノード１２０，１３０（Ｃ１，Ｃ２）におけるこのような衝突でのデータパケット（ＤＡＴＡ）４１０の欠落から以降の非受信において、協力ノード１２０，１３０（Ｃ１，Ｃ２）のそれぞれは、それのＣＴＳ１，ＣＴＳ２メッセージ３１０ａ，３１０ｂを再送すべきか否かさらなる確率分布に従って計算する。これにより、協力ノード１２０，１３０（Ｃ１，Ｃ２）は、ステップ６００においてさらに２つのグループに分割される。すなわち、（ａ）各自のＣＴＳ１，ＣＴＳ２メッセージ３１０ａ，３１０ｂをソースノード１１０（Ｓ）に再送しないよう計算する協力ノード１２０，１３０（Ｃ１，Ｃ２）のセカンダリ第１グループ６１０（例えば、セカンダリ第１グループ６１０は、協力ノード１２０（Ｃ１）を有する）と、（ｂ）各自のＣＴＳ１，ＣＴＳ２メッセージ３１０ａ，３１０ｂをソースノード１１０（Ｓ）に再送するよう計算する協力ノード１２０，１３０（Ｃ１，Ｃ２）のセカンダリ第２グループ６２０（例えば、セカンダリ第２グループ６２０は、協力ノード１３０（Ｃ２）を有する）とである。セカンダリグループ６１０，６２０への分割の結果において、協力ノード１３０（Ｃ２）は、通信のためソースノード１１０（Ｓ）を最終的にキャプチャすることができる。潜在的にプライマリとセカンダリグループより多くがソースノード１１０（Ｓ）と通信することに関係するように、本例の３つの協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）より多くがネットワーク１００に関係する可能性があることは理解されるであろう。図２は、マルチノード通信ネットワーク内の通信コンフリクトを解消する“分割ツリーベース”アルゴリズムを表す。
【００３６】
ノードネットワーク１１０とその動作は、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）がソースノード１１０（Ｓ）への各自の通信チャネル１５０，１６０，１７０の特性を効果的に決定することを可能にすることによって、さらに向上される。このような特性の決定は、図３を参照して説明されるように、各自の通信チャネル１５０，１６０，１７０に関する協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の  “学習”と便宜上呼ばれる。
【００３７】
図３を参照するに、図示され、７００により全体が示されるノード選択方法が示される。方法７００は、ステップ７１０，７２０，７３０，７４０，７５０，７６０の系列を有する。方法７００では、ソースノード１１０（Ｓ）と協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）とは、垂直線により表される。方法７００では、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、ソースノード１１０（Ｓ）との各自の通信チャネル、すなわち、各自の通信リンク１５０，１６０，１７０を特徴付けるよう動作可能である。このような各チャネルは相互的なものであると仮定される。各協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、第１ＲＴＳメッセージの受信中にそこでの受信パワーを測定するよう動作可能である。効果的には、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のそれぞれは、それの閾値パワーレベルＰＬを印加するよう構成される。すなわち、所与の協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）における測定された受信パワーＰＬが当該協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の閾値パワーレベルＰＬより高い場合、当該協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、以降にそれのＣＴＳメッセージをソースノード１１０（Ｓ）に送り返すよう動作する。他方、所与の協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）における上述した測定された受信パワーが当該協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の閾値パワーレベルＰＬ以下である場合、当該協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、それのＣＴＳメッセージをソースノード１１０（Ｓ）に送り返さないよう動作する。受信パワーに基づく協力ノード選択の上記方法は、図２を参照して上述されたツリー分割アルゴリズムと共に方法７００において適用される。
【００３８】
従って、ソースノード１１０（Ｓ）においてメッセージ衝突が発生した場合、ソースノード１１０（Ｓ）は、それのＲＴＳメッセージを再送するよう動作可能である。ソースノード１１０（Ｓ）はまた、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の何れも最初のＲＴＳメッセージに応答しない場合、ＲＴＳメッセージを再送するよう動作可能である。このような再送は、ソースノード１１０（Ｓ）が以下のシナリオに従って協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）と通信するため要求される。すなわち、（ａ）協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）における閾値パワーレベルＰＬが、低くすぎるよう指定され、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の多くが第１ＲＴＳメッセージに応答しすぎることになるため、ソースノード１１０（Ｓ）における高い受信パワーにより衝突が発生したか、又は（ｂ）協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）において測定された対応する受信ＲＴＳメッセージ信号パワーが協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の閾値パワーレベルＰＬ以下となるように、ソースノード１１０（Ｓ）は不十分なパワーにより第１ＲＴＳメッセージを送信するよう動作可能であった、である。
【００３９】
閾値パワーレベルＰＬが低すぎるよう指定されたシナリオ（ａ）では、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３は、ソースノード１１０（Ｓ）からの再送されたＲＴＳメッセージの受信に応答して、各自の閾値パワーレベルＰＬを増大させ、増大した閾値パワーレベルＰＬを基準として利用して、ソースノード１１０（Ｓ）に各自のＲＴＳメッセージを応答として返送するか評価するよう動作可能である。他方、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の何れもが第１ＲＴＳメッセージに応答しないシナリオ（ｂ）では、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、ソースノード１１０（Ｓ）から再送されたＲＴＳメッセージを受信することに応答して、各自のＣＴＳメッセージを送信するよう協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のより多くが動作可能となるように、各自の閾値パワーレベルＰＬを低下させるよう動作可能である。
【００４０】
図３を再び参照するに、方法７００のステップ７１０において、ソースノード１１０（Ｓ）は、７７０により示されるそれの第１ＲＴＳメッセージを３つの協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）に送信する。各協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、そこで受信された第１ＲＴＳメッセージのパワーを測定し、測定したパワーとそれの閾値パワーレベルＰＬと比較する。例えば、測定されたパワーが協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のすべてにおける閾値パワーレベルＰＬを超える状況では、方法７００のステップ７２０におけるすべての協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、７８０により示される各自のＣＴＳメッセージをソースノード１１０（Ｓ）に送信するよう動作可能である。ここで、ＣＴＳメッセージは、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）において受信した第１ＲＴＳメッセージ７７０の測定されたパワーを示す情報を有する。例えば、協力ノード１２０（Ｃ１）から送信される７９０により示されるＣＴＳメッセージは、第１ＲＴＳメッセージが協力ノード１２０（Ｃ１）において最も強力に受信されたことを示す。方法７００のステップ７３０において、ソースノード１１０（Ｓ）は、ＣＴＳメッセージ７８０の受信に応答して、そこで受信されたトータルパワーＥＰを測定するよう動作可能である。さらに、ソースノード１１０（Ｓ）は、８００により示される第１ＲＴＳメッセージの再送において、トータル受信パワーＥＰを示すデータを送信する。方法７００のステップ７４０において、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、トータルパワーＥＰと比較して、ＲＴＳメッセージの受信に関するそれの受信パワーのレシオＫを計算し、当該レシオＫとそれの閾値パワーレベルＬＰとを比較する。所与の協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のレシオＫが閾値パワーレベルＬＰより大きい場合、当該協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、それのＣＴＳメッセージを送信することにより応答する。例えば、協力ノード１２０（Ｃ１）は、８１０により示されるそれのＣＴＳメッセージをソースノード１１０（Ｓ）に送り返す。方法７００の次のステップ７５０において、ソースノード１１０（Ｓ）は、８２０により示されるデータメッセージを、例えば、ステップ７４０において応答した協力ノード１２０（Ｃ１）などの協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）に送信する。さらに次のステップ７６０において、協力ノード１２０（Ｃ１）は、８３０により示されるアクノリッジメントメッセージＡＣＫをソースノード１１０（Ｓ）に送信する。
【００４１】
方法７００を実現するとき、閾値パワーレベルＬＰは、すべての協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）において最初に設定可能である。あるいは、ソースノード１１０（Ｓ）は、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）について閾値パワーレベルＬＰを設定するよう動作可能である。任意的には、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、互いに異なる閾値パワーレベルＬＰに割当て可能であり、すなわち、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）に個別化できる。あるいは、任意的には、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、互いに同様の閾値パワーレベルＬＰに割当て可能である。例えば、レシオとして表現される初期的な閾値パワーレベルは、効果的には５０％である。各協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、それに割り当てられた閾値パワーレベルＬＰに基づき、以降の送信を行う必要があるか判断するよう動作可能である。
【００４２】
上述したキャプチャ効果は、方法７００の実現が絶対的なパワー又はパワーレシオに関してソースノード１１０（Ｓ）からのフィードバックを伴う際に発生するため、方法７００は、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の迅速な選択の技術的効果を提供する可能性があり、またベストな即時チャネル状態を有する協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の所与の１つが競合に勝ち、データメッセージ８２０を受信するため選択されることを保証する。
【００４３】
本発明が３つの協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の一例となる状況において説明されたが、潜在的に３より少ない協力ノードと共に、３より多くの協力ノードが存在する可能性もあることは理解されるであろう。
【００４４】
本発明はまた、図４を参照して説明されるように、他の方法により実現される可能性もある。上述した方法７００は、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）のプレ選択を利用して、好適な協力ノードを選択し、その後に当該協力ノードとアクノリッジメッセージによるデータ通信を行う。図４において９００により示される本発明による方法は、後述されるように、協力ノードのポスト選択に関する。
【００４５】
図４を参照するに、方法９００は、４つのステップ９１０，９２０，９３０，９４０を有し、図４の垂直線により表されるようなノード１１０，１２０，１３０，１４０（Ｓ，Ｃ１，Ｃ２，Ｃ３）に関する。方法９００の第１ステップ９１０では、ソースノード１１０（Ｓ）は、９５０により示されるデータメッセージを協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）に送信する。協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）は、例えば、上述されるようなパワー閾値レベルアルゴリズムに従って、メッセージ交換などを介し互いに競合し、方法９００の第２ステップ９２０において９６０により示されるソースノード１１０（Ｓ）にアクノリッジメントメッセージを送り返すことによって応答するため、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の１つを互いに選択する。任意的には、ソースノード１１０（Ｓ）は、データメッセージを受信したすべての協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）が方法９００のステップ９３０，９４０に示される対応するアクノリッジメントメッセージにより応答するまでの期間待機する。ポスト選択が方法９００において利用されるため、データメッセージの伝搬のため、ソースノード１１０（Ｓ）は、協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）の少なくとも１つがデータメッセージ９５０を受信したことしか心配しない。本方法では、各自のアクノリッジメントメッセージ９６０，９８０，９９０を送り返した協力ノード１２０，１３０，１４０（Ｃ１，Ｃ２，Ｃ３）がデータメッセージの通信をサポートするのにベストなノードであるか否かは、データメッセージ９５０の伝搬成功に関して重要でない。
【００４６】
本発明は、各種形式のデータ通信システムにおいて利用される可能性がある。例えば、本発明は、無線コンピュータ通信ネットワークなどにおいて１ホップ通信が行われるバーチャルセルラーネットワークへの適用である。さらに、例えば、本発明はまた、分散センサネットワークなどのマルチホップアドホックネットワークに関する。さらに、本発明はまた、ＩＥＥＥ８０２．１１ｓやＩＥＥＥ８０２．１５．５などの既存の確立された通信規格をアップグレードするため適用可能である。
【００４７】
上述された実施例で説明された本発明は、計算ハードウェア上で実行可能な１以上のソフトウェアプロダクトにより実現可能である。さらに、このような１以上のソフトウェアプロダクトは、信号、記憶装置、データメモリなどのデータキャリア上で搬送可能である。
【００４８】
上述された本発明の実施例に対する改良は、添付した請求項により規定されるような本発明の範囲から逸脱することなく可能である。
【００４９】
本発明を説明及び請求するのに使用される“含む”、“有する”、“内蔵する”、“構成する”、“である”などの各表現は、限定的に解釈されるべきでなく、すなわち、明示的には記載されていないアイテム、コンポーネント又は要素が存在することを許容する。単数形の表現はまた、複数に関すると解釈されるべきである。
【００５０】
添付した請求項の括弧内に含まれる数字は、請求項の理解を助けるためのものであり、これらの請求項により請求される構成を限定するものとして解釈されるべきでない。
【図１】
2010503308.tif 000004
【図２−１】
2010503308.tif 000005
【図２−２】
2010503308.tif 000006
【図３】
2010503308.tif 000007
【図４】
2010503308.tif 000008
【国際調査報告】
2010503308.tif 000009
2010503308.tif 000010
2010503308.tif 000011