(57)【要約】【課題】ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信する方法を提供する。【解決手段】ネットワークは、Ｎ個のクラスタにクラスタ化され、Ｎ個のクラスタの各クラスタは、該ノードの少なくとも１つを有する。第１のステップにおいて、ＴＤＭＡスキームは、周期的なスーパーフレームにより編成される。周期的なスーパーフレームの各スーパーフレームは、Ｎ個のクラスタに対して、少なくとも１つのブロードキャスト・フレームおよび１つのコレクション・フレームを含むいくつかのフレームを有する。第２のステップにおいて、ブロードキャスト・フレーム内で、１つの専用通信チャネルがＮ個のクラスタにより共有される。第３のステップにおいて、コレクション・フレーム内で、別々のＮ個の通信チャネルがＮ個のクラスタにより使用される。【選択図】図２
2014532346.tif 000002
【特許請求の範囲】
【請求項１】
ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード（０１〜３７）間でデータを送信する方法であって、前記ネットワークは、Ｎ個のクラスタ（Ｃ１、Ｃ２）へとクラスタ化され、前記Ｎ個のクラスタ（Ｃ１、Ｃ２）の各クラスタ（Ｃ１、Ｃ２）は、ノード（０１〜３７）のうちの少なくとも１つを含み、前記方法は、
前記ＴＤＭＡスキームを、周期的なスーパーフレーム（３００）へと編成するステップ（３０１、４０１、５０１）であって、前記周期的なスーパーフレーム（３００）の各スーパーフレーム（３００）は、前記Ｎ個のクラスタ（Ｃ１、Ｃ２）に対して、少なくとも１つのブロードキャスト・フレーム（３１０）および１つのコレクション・フレーム（３２０）を含むいくつかのフレームを有する、前記ステップ（３０１、４０１、５０１）と、
前記ブロードキャスト・フレーム（３１０）内で、１つの専用通信チャネル（Ｂ）を前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により共有するステップと、
前記コレクション・フレーム（３２０）内で、別々のＮ個の通信チャネル（Ａ、Ｂ、Ｃ）を前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により使用するステップと、
を含む、方法。
【請求項２】
前記Ｎ個のクラスタの各クラスタ（Ｃ１、Ｃ２）は、基地局として機能する１つのノード（０１、１２）を有し、前記Ｎ個のクラスタ（Ｃ１、Ｃ２）の前記Ｎ個の基地局（０１、１２）の中で、１つのノードが主基地局（０１）として機能する、
請求項１に記載の方法。
【請求項３】
構成段階の中で、チャネル指示が前記ネットワークの前記ノードの各ノード（０１〜３７）に提供され、前記チャネル指示は、前記コレクション・フレーム（３２０）内で前記ノード（０１〜３７）に割り振られる前記通信チャネル（Ａ、Ｂ、Ｃ）を示す、
請求項１または２に記載の方法。
【請求項４】
前記ブロードキャスト・フレーム（３１０）内で、前記ネットワークのすべてのノード（０１〜３７）に情報を配信するために、前記Ｎ個のクラスタ（Ｃ１、Ｃ２）のすべてのノード（０１〜３７）にわたる単一のブロードキャスト・ツリーが、前記主基地局（０１）により使用される、
請求項１〜３のうちの１項に記載の方法。
【請求項５】
前記ブロードキャスト・ツリーは、前記主基地局（０１）を根とする前記ネットワークのトポロジ全体から計算される、
請求項４に記載の方法。
【請求項６】
前記コレクション・フレーム（３２０）内で、前記Ｎ個のクラスタの各クラスタ（Ｃ１、Ｃ２）は、それ自体のコレクション・ツリーを有し、前記コレクション・ツリーは、当該クラスタに属する前記ノードのみにわたるものであり、当該クラスタ（Ｃ１、Ｃ２）の前記基地局（０１、１２）と情報を交換するために当該クラスタの前記ノードにより使用される、
請求項１〜５のうちの１項に記載の方法。
【請求項７】
前記クラスタ（Ｃ１、Ｃ２）の前記コレクション・ツリーは、前記クラスタ（Ｃ１、Ｃ２）の前記基地局（０１、１２）を根とする前記クラスタ（Ｃ１、Ｃ２）のトポロジから計算される、
請求項６に記載の方法。
【請求項８】
前記周期的なスーパーフレームの各スーパーフレーム（３００）は、少なくとも、前記ブロードキャスト・フレーム（３１０）、前記コレクション・フレーム（３２０）、およびリスニング・フレーム（３３０）を有し、
前記ブロードキャスト・フレーム（３１０）内で、前記１つの専用通信チャネル（Ｂ）が前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により共有され、
前記コレクション・フレーム（３２０）内で、前記別々のＮ個の通信チャネル（Ａ、Ｂ、Ｃ）が前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により使用され、
前記リスニング・フレーム（３３０）内で、前記１つの専用通信チャネル（Ｂ）が前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により共有される、
請求項１〜７のうちの１項に記載の方法。
【請求項９】
非同期ノードを前記ネットワークと同期させるために、前記リスニング・フレーム（３３０）内でＣＳＭＡまたはＭＡＣＡを使用して情報が交換される、
請求項８に記載の方法。
【請求項１０】
前記ネットワーク内の非同期ノードを同期させるために、前記リスニング・フレーム（３３０）の初めにブラック・バーストが送信される、
請求項８に記載の方法。
【請求項１１】
前記スーパーフレーム（３００）内で、前記ブロードキャスト・フレーム（３１０）の後に前記リスニング・フレーム（３３０）が続く、
請求項９または１０に記載の方法。
【請求項１２】
前記周期的なスーパーフレーム（３００）の各スーパーフレーム（３００）は、前記ブロードキャスト・フレーム（３１０）、前記コレクション・フレーム（３２０）、リスニング・フレーム（３３０）、ダウンツリー・フレーム（３４０）、およびアップツリー・フレーム（３５０）を有し、
前記ブロードキャスト・フレーム（３１０）内および前記リスニング・フレーム（３３０）内で、１つの専用通信チャネル（Ｂ）が前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により共有され、
前記コレクション・フレーム（３２０）内、前記ダウンツリー・フレーム（３４０）内、および前記アップツリー・フレーム（３５０）内で、前記別々のＮ個の通信チャネル（Ａ、Ｂ、Ｃ）が前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により使用される、
請求項１〜１１のうちの１項に記載の方法。
【請求項１３】
前記ブロードキャスト・ツリーおよび各コレクション・ツリーに関して、前記マルチホップ・ネットワークは、１つの根ノード（０１）と、親ノード（０１〜２４）よりも低いレベル（Ｌ１〜Ｌ３）に配置された少なくとも１つの子ノード（１１〜３７）の前記親である少なくとも１つの前記親ノード（０１〜２４）と、少なくとも１つの子ノード（１１〜３７）とを備える種々のレベル（Ｌ０〜Ｌ３）に階層的に配置される、
請求項１〜１２のうちの１項に記載の方法。
【請求項１４】
ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信するためのデバイス（６０）であって、前記ネットワークは、Ｎ個のクラスタ（Ｃ１、Ｃ２）へとクラスタ化され、前記Ｎ個のクラスタの各クラスタ（Ｃ１、Ｃ２）は、前記ノード（０１〜３７）のうちの少なくとも１つを含み、前記デバイス（６０）は、
前記ＴＤＭＡスキームを周期的なスーパーフレーム（３００）へと編成するオーガナイザ（６１）であって、前記周期的なスーパーフレームの各スーパーフレーム（３００）は、前記Ｎ個のクラスタ（Ｃ１、Ｃ２）に対して、少なくとも１つのブロードキャスト・フレーム（３１０）および１つのコレクション・フレーム（３２０）を含む、前記オーガナイザ（６１）と、
前記コレクション・フレーム（３２０）内で前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により使用される別々のＮ個の通信チャネル（Ａ、Ｂ、Ｃ）を提供するプロバイダ（６２）と、
前記ブロードキャスト・フレーム（３１０）内で前記Ｎ個のクラスタ（Ｃ１、Ｃ２）により共有される１つの通信チャネル（Ｂ）を、前記別々のＮ個の通信チャネル（Ａ、Ｂ、Ｃ）から選択し、さらに、前記別々のＮ個の通信チャネル（Ａ、Ｂ、Ｃ）のうちの１つを、前記コレクション・フレーム（３２０）内で使用されるよう前記Ｎ個のクラスタ（Ｃ１、Ｃ２）のうちの１つに割り当てる、セレクタ（６３）と、
を含むデバイス（６０）。
【請求項１５】
複数のノード（０１〜３７）を含むマルチホップ・ネットワークであって、前記複数のノードの各ノード（０１〜３７）は、請求項１〜１３のうちの１項に記載の方法に前記ノードが従うことを可能にするプロセッサを有する、マルチホップ・ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、時分割多重接続（ＴＤＭＡ：Ｔｉｍｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅｘ  Ａｃｃｅｓｓ）スキームを用いるマルチホップ・ネットワーク、特にＴＤＭＡベースの低電力センサ・ネットワークのノード間でデータを送信する方法およびデバイスに関する。ネットワークは、複数のクラスタへとクラスタ化され、複数のクラスタの各クラスタは、いくつかのノードを含む。
【背景技術】
【０００２】
低電力センサ・ネットワーク、特に電池式無線センサ・ネットワークでは、エネルギーを節約するために、センサ・ノードの無線送受信機のアイドル期間中に無線送受信機をオフにすることが非常に重要である。アイドル期間とは、ノードが送受信すべきものがまったくない期間である。さらなる重要な側面は、メッセージを送信するときの衝突を回避すること、および個々のノード宛てでないメッセージの漏話を最小限に抑えることである。
【０００３】
上記の文脈において、ＴＤＭＡベースのシステムは、本質的にエネルギー効率に優れている。なぜなら、システムのノードが、その無線送受信機をメッセージの送受信のためにオンにしなければならないタイム・スロットを定義する、明確に定義されたスケジュールを有するためである。他のタイム・スロットすべてにおいて、個々のノードは、その無線送受信機をオフにできる。適切なタイム・スロット割り当てにより、送信側および受信側がネットワーク上でメッセージを交換できるようにそれらを同じタイム・スロットでウェイクアップさせることができる。
【０００４】
マルチホップ・ネットワークにおける多対一通信は、例えば環境モニタリングまたはデータ収集の分野などにおけるセンサ・ネットワークの応用のごく一般的な要件であり、センサ・ノードは、基本的にはシンク・ノードと情報を交換し、通常はセンサ・ノード同士の間では情報を交換しない。この点に関して、センサ・ノードは、通常、周期的データ・サンプルを生成して、これらの生成された周期的データ・サンプルをさらなる処理のためにシンク・ノードへ送る。シンク・ノードから他のセンサ・ノードへの反対方向も、例えばシンク・ノードから他のノードへ制御情報を送るために使用され得る。シンク・ノードと、さらなるセンサ・ノードとの間の経路または分岐は、シンク・ノードを根としてすべてのノードに広がるマルチホップ・ツリーを形成し得る。
【０００５】
ネットワークにおける通信のために、ＴＤＭＡスキームは周期的なスーパーフレームにより編成され得る。周期的なスーパーフレームの各スーパーフレームは、例えばブロードキャスト・フレームおよびコレクション・フレームを含むいくつかのフレームを有し得る。
【０００６】
フレームは、固定長の複数のタイム・スロットからなる。Ｎ個のメッセージが、１つのスロットの間に送られ得る。１つのスロットの間、ノードは、送信、受信、またはスリープの３つの状態のうちの１つであり得る。ノードは、送受信のためにそれらに割り当てられたスロットの間のみアウェイク状態である。
【０００７】
従来のＴＤＭＡスーパーフレーム構造は、多数のノードを備えるネットワーク向けに拡大できない。なぜなら、ブロードキャスト・フレームおよびコレクション・フレームの長さがネットワーク・ノードの数とともに増大する一方で、スーパーフレームの長さは待ち時間要件により制限されるためである。具体的には、ブロードキャスト・フレームは、例えば同期情報などの情報をブロードキャストするために親ノードにより使用され得る。この目的のために、各親ノードは、ブロードキャスト・フレーム内のスロットを割り当てられ、このスロットを使用して、そのメッセージを子ノードへブロードキャストする。すなわち、ブロードキャスト・フレームは、ネットワーク内にある親ノードと同数のスロットを含む。
【０００８】
コレクション・フレーム内のスロットは、センサ・ノードにより、その周期的データをシンクに送るために使用され得る。ノードに割り当てられるスロットの数は、当該ノードの下位ノードによりもたらされるトラフィックがある場合はその量に、当該ノード自体によりもたらされるトラフィックを加えることにより決まる。ネットワーク内のあらゆるノードが、シンクへ転送されるべきメッセージをスーパーフレーム毎に少なくとも１つ有すると仮定すると、コレクション・フレームに必要なスロットの数は、ネットワーク内のノードの数よりも常に大きくなる。
【０００９】
この拡張性の問題は、多数のノードを備えるネットワークがクラスタと呼ばれるより少数のノードのグループへと分割される、周知の手法であるクラスタ化により解決され得る。その場合、各クラスタは、それ自体のシンク、それ自体のルーティング・ツリー、およびそれ自体のＴＤＭＡスケジューリングを有することができ、したがって、単一の大型ネットワークよりも容易に管理できる。
【００１０】
さらに、周波数（ＦＤＭＡ；Ｆｒｅｑｕｅｎｃｙ−Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ（周波数分割多重接続））または符号（ＣＤＭＡ；Ｃｏｄｅ−Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ（符号分割多重接続））多重が、種々のクラスタ内のノードの同時送信を可能にするために使用され得る。例えば、ＩＥＥＥ８０２．１５．４標準は、２．４ＧＨｚ  ＩＳＭバンドにおいて、独立した１６のＦＤＭＡチャネルを定義しており、そのそれぞれが、異なるクラスタにより使用可能であり、種々のクラスタ内のノードが相互に干渉せずに並行して送信できる。
【００１１】
クラスタ化については、科学論文において広範囲な研究が行われている。例えば非特許文献１または非特許文献２を参照されたい。研究のほとんどは、クラスタをどう形成するか、またはクラスタ・ヘッドをどう選択するかのアルゴリズムについて論じている。さらに、ＭＡＣプロトコルに関する膨大な一連の研究もある。しかしながら、同期には一般的なＴＤＭＡブロードキャスト・ツリーを利用し、かつクラスタ・データ収集には異なる周波数上で追加のスロット化フレームを利用するＭＡＣソリューションは、他にない。現在の概要は、非特許文献３で入手できる。
【００１２】
さらに、特許文献１には、多重バス・システム・ネットワークおよび無線ネットワークのためのデータ送信の制御方法が記載されている。ネットワークで使用される送信制御方法は、時分割多重チャネルおよび競合制御チャネルを含む。少なくとも１つの局および中央制御ユニットが、競合制御チャネルおよび時分割多重（ＴＤＭＡ）チャネルの両方に接続される。局は、時分割多重セッションを開始するとき、競合制御チャネルを介して中央制御ユニットにアクセス要求を送信する。中央制御ユニットがアクセス要求を受信した後、アクセス要求を送信した局は、時分割多重（ＴＤＭＡ）の順番に含められる。中央制御ユニットは、局に対して、ＴＤＭＡチャネルを介して時分割多重の順序に従って繰り返し送信許可トークンを送信する。送信許可トークンを受信した局は、データ実体が存在すれば、それを他の局または中央制御ユニットへ、第２の通信チャネルを介して送信し、さらに、中央制御ユニットへ、第２の通信チャネルを介して送信終了トークンを送信する。中央制御ユニットは、送信終了トークンを受信すると、時分割多重の順序において次の局に対して、第２の通信チャネルを介して送信許可トークンを送信する。
【００１３】
特許文献２は、コンパクトなインターネットワーク化無線統合ネットワーク・センサ（ＷＩＮＳ：ｗｉｒｅｌｅｓｓ  ｉｎｔｅｇｒａｔｅｄ  ｎｅｔｗｏｒｋ  ｓｅｎｓｏｒｓ）を使用してデータを集める方法を示す。さらに、特許文献３には、無線通信ネットワークおよび当該ネットワークのためのデータ集約方法が記載されている。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】米国特許第６，０３４，９６６（Ａ）号
【特許文献２】米国特許第６，７３５，６３０（Ｂ１）号
【特許文献３】米国特許第７，８３０，８３４（Ｂ２）号
【非特許文献】
【００１５】
【非特許文献１】Ｙｏｕｎｉｓ  Ｏ．ら著、「Ｎｏｄｅ  Ｃｌｕｓｔｅｒｉｎｇ  ｉｎ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ：Ｒｅｃｅｎｔ  Ｄｅｖｅｌｏｐｍｅｎｔｓ  ａｎｄ  Ｄｅｐｌｏｙｍｅｎｔ  Ｃｈａｌｌｅｎｇｅｓ」、ＩＥＥＥ  Ｎｅｔｗｏｒｋｓ、２００６年５月／６月
【非特許文献２】Ａｂｂａｓｉ  Ａ．Ａ．およびＹｏｕｎｉｓ  Ｍ．著、「Ａ  ｓｕｒｖｅｙ  ｏｎ  ｃｌｕｓｔｅｒｉｎｇ  ａｌｇｏｒｉｔｈｍｓ  ｆｏｒ  ｗｉｒｅｌｅｓｓ  ｓｅｎｓｏｒ  ｎｅｔｗｏｒｋｓ」、Ｃｏｍｐｕｔｅｒ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、第３０巻、（２００７年）
【非特許文献３】Ｂａｃｈｉｒ  Ａ、Ｄｏｈｌｅｒ  Ｍ、Ｗａｔｔｅｙｎｅ  Ｔ、Ｌｅｕｎｇ  ＫＫ著、「ＭＡＣ  Ｅｓｓｅｎｔｉａｌｓ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ」、ＩＥＥＥ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｕｒｖｅｙｓ  ＆  Ｔｕｔｏｒｉａｌｓ、２０１０年、第１２巻第２号、ｐ．２２２〜２４８
【発明の概要】
【発明が解決しようとする課題】
【００１６】
従来のＴＤＭＡスーパーフレーム構造は、多数のノードを備えるネットワーク向けに拡大できない。なぜなら、ブロードキャスト・フレームおよびコレクション・フレームの長さがネットワーク・ノードの数とともに増大する一方で、スーパーフレームの長さは待ち時間要件により制限されるためである。具体的には、ブロードキャスト・フレームは、例えば同期情報などの情報をブロードキャストするために親ノードにより使用され得る。この目的のために、各親ノードは、ブロードキャスト・フレーム内のスロットを割り当てられ、このスロットを使用して、そのメッセージを子ノードへブロードキャストする。すなわち、ブロードキャスト・フレームは、ネットワーク内にある親ノードと同数のスロットを含む。
【００１７】
コレクション・フレーム内のスロットは、センサ・ノードにより、その周期的データをシンクに送るために使用され得る。ノードに割り当てられるスロットの数は、当該ノードの下位ノードによりもたらされるトラフィックがある場合はその量に、当該ノード自体によりもたらされるトラフィックを加えることにより決まる。ネットワーク内のあらゆるノードが、シンクへ転送されるべきメッセージをスーパーフレーム毎に少なくとも１つ有すると仮定すると、コレクション・フレームに必要なスロットの数は、ネットワーク内のノードの数よりも常に大きくなる。
【００１８】
したがって、ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間のデータの転送を改善することが、本発明の一側面である。
【課題を解決するための手段】
【００１９】
第１の側面によれば、ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信する方法が提案される。ネットワークは、Ｎ個のクラスタにクラスタ化され、Ｎ個のクラスタの各クラスタは、該ノードの少なくとも１つを有する。第１のステップにおいて、ＴＤＭＡスキームは、周期的なスーパーフレームにより編成される。周期的なスーパーフレームの各スーパーフレームは、Ｎ個のクラスタに対して、少なくとも１つのブロードキャスト・フレームおよび１つのコレクション・フレームを含むいくつかのフレームを有する。第２のステップにおいて、ブロードキャスト・フレーム内で、１つの専用通信チャネルがＮ個のクラスタにより共有される。第３のステップにおいて、コレクション・フレーム内で、別々のＮ個の通信チャネルがＮ個のクラスタにより使用される。
【００２０】
一部の実装によれば、集中化およびクラスタ化された無線センサ・ネットワーク・アーキテクチャ用とされ得るＴＤＭＡスーパーフレーム構造が提供される。本ＴＤＭＡスーパーフレーム構造では、単一の同期チャネル、すなわちブロードキャスト・チャネルが、Ｎ個のクラスタにより共有され、複数のチャネルが、コレクション・フレームにおけるデータ収集のために使用される。
【００２１】
ある実施形態では、Ｎ個のクラスタの各クラスタは、基地局として機能する１つのノードを有し、Ｎ個のクラスタのＮ個の基地局の中で、１つのノードが主基地局として機能する。
【００２２】
さらなる実施形態では、構成段階の中で、チャネル指示がネットワークのノードの各ノードに提供され、チャネル指示は、コレクション・フレーム内でノードに割り振られる通信チャネルを示す。
【００２３】
さらなる実施形態では、ブロードキャスト・フレーム内で、ネットワークのすべてのノードに情報を配信するために、Ｎ個のクラスタのすべてのノードにわたる単一のブロードキャスト・ツリーが主基地局により使用される。
【００２４】
さらなる実施形態では、ブロードキャスト・ツリーは、主基地局を根とするネットワークのトポロジ全体から計算される。
【００２５】
さらなる実施形態では、コレクション・フレーム内で、Ｎ個のクラスタの各クラスタは、それ自体のコレクション・ツリーを有し、該コレクション・ツリーは、当該クラスタに属するノードのみにわたるものであり、当該クラスタの基地局と情報を交換するために当該クラスタのノードにより使用される。
【００２６】
さらなる実施形態では、クラスタのコレクション・ツリーは、クラスタの基地局を根とするクラスタのトポロジから計算される。
【００２７】
さらなる実施形態では、周期的なスーパーフレームの各スーパーフレームは、少なくとも、ブロードキャスト・フレーム、コレクション・フレーム、およびリスニング・フレームを有する。ブロードキャスト・フレーム内で、１つの専用通信チャネルがＮ個のクラスタにより共有される。コレクション・フレーム内で、別々のＮ個の通信チャネルがＮ個のクラスタにより使用される。さらに、リスニング・フレーム内で、１つの専用通信チャネルがＮ個のクラスタにより共有される。
【００２８】
さらなる実施形態では、非同期ノードをネットワークと同期させるために、リスニング・フレーム内でＣＳＭＡ（Ｃａｒｒｉｅｒ−Ｓｅｎｓｅ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ：キャリア検知多重アクセス）またはＭＡＣＡを使用して情報が交換される（Ｐ．Ｋａｒｎ、「ＭＡＣＡ−Ａ  Ｎｅｗ  Ｃｈａｎｎｅｌ  Ａｃｃｅｓｓ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｐａｃｋｅｔ  Ｒａｄｉｏ」、９ｔｈ  ＡＲＲＬ  Ｃｏｍｐｕｔｅｒ  Ｎｅｔｗｏｒｋｉｎｇ  Ｃｏｎｆｅｒｅｎｃｅ、１９９０年参照）。
【００２９】
さらなる実施形態では、ネットワーク内の非同期ノードを同期させるために、リスニング・フレームの初めにブラック・バーストが送信される。
【００３０】
さらなる実施形態では、スーパーフレーム内で、ブロードキャスト・フレームの後にリスニング・フレームが続く。
【００３１】
さらなる実施形態では、周期的なスーパーフレームの各スーパーフレームは、ブロードキャスト・フレーム、コレクション・フレーム、リスニング・フレーム、ダウンツリー・フレーム、およびアップツリー・フレームを含む。ブロードキャスト・フレーム内およびリスニング・フレーム内で、１つの専用通信チャネルがＮ個のクラスタにより共有される。コレクション・フレーム内、ダウンツリー・フレーム内、およびアップツリー・フレーム内で、別々のＮ個の通信チャネルがＮ個のクラスタにより使用される。
【００３２】
さらなる実施形態では、ブロードキャスト・ツリーおよび各コレクション・ツリーに関して、マルチホップ・ネットワークは、１つの根ノードと、親ノードよりも低いレベルに配置された少なくとも１つの子ノードの親である少なくとも１つの親ノードと、少なくとも１つの子ノードとを備える種々のレベルに階層的に配置される。
【００３３】
具体的には、コレクション・フレームは、データを根ノードへ周期的に送信するよう構成される。コレクション・フレーム内のスロットは、ノードにより、そのデータ、特に周期的データを根またはシンク・ノードへ送るために使用され得る。ノードに割り当てられるスロットの数は、当該ノードの下位ノードによりもたらされるトラフィックがある場合はその量に、当該ノードによりもたらされるトラフィックを加えることにより決まる。コレクション・フレームの長さは、ノードによりもたらされるすべてのメッセージ、具体的にはすべての周期的メッセージが、コレクション・フレームの持続期間内に根ノードに到達できるような長さである。
【００３４】
したがって、根ノードは、周期的データのシンクであってもよい。例えば、マルチホップ・ネットワークが低電力センサ・ネットワークにより具現化される場合、周期的データは周期的センサ・データであってもよい。
【００３５】
コレクション・フレームは、アップツリー・メッセージ、すなわちノードから根へ送られるメッセージの、マルチホップで衝突のない周期的収集の手段を提供するよう構成される。コレクション・フレームは、基地局に結合され得る根ノードへ、ノードの通常データを送るために、ノード、特にセンサ・ノードにより使用されてもよい。ノードに割り当てられるスロットの数は、当該ノードの下位ノードによりもたらされるトラフィックの量に、当該ノードによりもたらされるトラフィックを加えることにより決まってもよい。コレクション・フレームの長さは十分に長いため、ノードによりもたらされるすべてのメッセージが、コレクション・フレームの持続期間内に根ノードに到達できる。スロット割り当てアルゴリズムは、必要とされるスロットの総数を計算して、それらをノードに割り当ててもよい。
【００３６】
スロット割り当てアルゴリズムに関して、コレクション・フレームの初めに、ノードＮｉが根ノードに送るべきＭｉ個のメッセージを有すると仮定されてもよい。アルゴリズムは、フレームの終わりにすべてのメッセージが根ノードに到達しているように、フレームのスロットをノード間に配分しなければならない。
【００３７】
上記の要件を満たす単純なスケジューリング・アルゴリズムは、最大レベルのノード、すなわち根ノードから最も遠く離れたノードについてまず考慮し、それらに、そのメッセージをすべて送るのに必要な数だけのスロットを与えることであると思われる。これらのノードの親は、この割り当てられたスロットを受信スロットとして有することになる。続いて、次に低いレベルのノードが考慮される。これらのノードは、それ自体のメッセージに加えて、その下位のメッセージの中継も行わなければならないため、その下位のメッセージおよびそれ自体のメッセージを転送するのに必要な数だけの送信スロットを得るとよい。この場合もやはり、これらのノードの親は、これらのスロットを受信スロットとして有することになる。記載された割り当てアルゴリズムは、第１のレベルのノードに送信スロットが割り当てられるまで繰り返される。
【００３８】
上記のように、スーパーフレームは、少なくとも１つのブロードキャスト・フレームおよび１つのコレクション・フレームを含むいくつかのフレームからなる。例えばブロードキャスト・フレームなどの個々のフレームは、固定長の複数のタイム・スロットからなってもよい。１つのスロットの間、いくつかのメッセージを転送できる。さらに、１つのスロットの間、ノードは、送信、受信、またはスリープ（アイドル）の３つの状態またはモードのうちの１つであってもよい。ノードは、送信または受信のためにノードに割り当てられているスロットの間のみ、アウェイク状態であってもよい。
【００３９】
さらに、上記のように、各親ノードは、ブロードキャスト・フレーム内のスロットを割り当てられ、その子ノードへメッセージをブロードキャストするために、このスロットを使用する。これらのメッセージは、ネットワーク全体にブロードキャストされず、その１つまたは複数の最終宛先ノードに向かってのみ転送されるよう、個別にソース・ルーティングされてもよい。具体的には、子ノードは、その親のブロードキャスト・スロットの間、ウェイクアップ状態になり、その親により送られるメッセージを受信してもよい。特に、フレームの初めにシンク・ノードにより送られたメッセージが、ネットワーク内のその宛先ノードに、前記ブロードキャスト・フレームの持続時間内に到達するような形で、ブロードキャスト・フレームのスロットが割り当てられる。
【００４０】
一実施形態では、マルチホップ・ネットワークには、１つの根ノード、親ノードよりも低いレベルに配置された少なくとも１つの子ノードの親である少なくとも１つの親ノード、および少なくとも１つの子ノードが提供される。
【００４１】
さらなる実施形態では、レベルＮを有するノードが、根ノードからＮホップ離れて配置され、各親ノードは、そのレベルＮに基づいてブロードキャスト・フレーム内のスロットを割り当てられる。
【００４２】
さらなる実施形態において、本方法は、
−各親ノードＮｉに、マルチホップ・ネットワークにおけるレベルＬｉを割り当てるステップと、
−各親ノードＮｉに、そのレベルＬｉに基づいてブロードキャスト・フレーム内のスロットＳｉを割り当てるステップと、
をさらに含み、スロットは、すべてのＬｉ（Ｎｉ）≦Ｌｊ（Ｎｊ）およびすべてのＮｉに対しＳｉ≦Ｓｊという条件に基づいて、ブロードキャスト・フレーム内に順番に配置される。
【００４３】
さらなる実施形態では、各親ノードは、マルチホップ・ネットワーク内のそれ自体の親ノードから受信された同期情報を再配信するためのスロットを割り当てられる。
【００４４】
本発明の別の側面によれば、時分割多重接続（ＴＤＭＡ）を用いるマルチホップ・ネットワークのノードへデータを送信する方法が提供され、ノードは、種々のレベルに階層的に配置されており、本方法は、
−マルチホップ・ネットワークのノードを同期させる上述の方法によってマルチホップ・ネットワークのノードを同期させるためにマルチホップ・ネットワーク上で同期情報を送信すること
を含む。
【００４５】
さらなる実施形態では、同期情報に加えて、少なくとも１つのダウンツリー・メッセージが、ブロードキャスト・フレームの少なくとも１つのスロット内で送信される。
【００４６】
さらなる実施形態では、ダウンツリー・メッセージおよび同期情報は、ブロードキャスト・フレームの個々のスロット内の単一のメッセージによって送信される。
【００４７】
さらなる実施形態では、ダウンツリー・メッセージおよび同期情報は、ブロードキャスト・フレームの個々のスロット内の別々の２つのメッセージによって送信される。
【００４８】
さらなる実施形態では、少なくとも１つのダウンツリー・メッセージが、マルチホップ・ネットワーク内のすべてのノードにブロードキャストされる。
【００４９】
さらなる実施形態では、少なくとも１つのダウンツリー・メッセージが、定義された１つの受信側ノードへユニキャストされるか、または少なくとも１つのダウンツリー・メッセージが、定義されたいくつかの受信側ノードへマルチキャストされ、前記少なくとも１つのダウンツリー・メッセージは、前記根ノードと個々の受信側ノードとの間に配置されている任意の中間ノードにより中継される。
【００５０】
さらなる実施形態では、ダウンツリー・フレームをアクティブ化するためのダウンツリー・フレーム要求があると、スーパーフレームに前記ダウンツリー・フレームがさらに提供され、ダウンツリー・フレームは、少なくとも１つのダウンツリー・メッセージをマルチホップ・ネットワーク内の少なくとも１つのノードへ送信するよう構成される。
【００５１】
さらなる実施形態では、マルチホップ・ネットワークの単一の分岐がアクティブ化されるように、ダウンツリー・フレームをアクティブ化するためのダウンツリー・フレーム要求が、ブロードキャスト・フレーム内の割り当てられたスロットにより子ノードへ送信される。
【００５２】
さらなる実施形態では、マルチホップ・ネットワークの複数の分岐がアクティブ化されるように、ダウンツリー・フレームをアクティブ化するためのダウンツリー・フレーム要求が、ブロードキャスト・フレーム内の割り当てられたスロットにより子ノードへ送信される。
【００５３】
そのような場合、ダウンツリー・フレーム要求は、個々のダウンツリー・フレームの間にアクティブ化されるべきノードのリストを含んでもよい。
【００５４】
ダウンツリー・フレームと同様に、マルチホップ・ネットワークの単一の分岐がアクティブ化されるように、アップツリー・フレームをアクティブ化するためのアップツリー・フレーム要求が、ブロードキャスト・フレーム内の割り当てられたスロットにより子ノードへ送信されてもよい。
【００５５】
さらなる実施形態では、マルチホップ・ネットワークの単一の分岐がアクティブ化されるように、アップツリー・フレームをアクティブ化するためのアップツリー・フレーム要求が、ブロードキャスト・フレーム内の割り当てられたスロットにより子ノードへ送信される。
【００５６】
さらなる実施形態では、マルチホップ・ネットワークの複数の分岐がアクティブ化されるように、アップツリー・フレームをアクティブ化するためのアップツリー・フレーム要求が、ブロードキャスト・フレーム内の割り当てられたスロットにより子ノードへ送信される。
【００５７】
そのような場合、アップツリー・フレーム要求は、個々のアップツリー・フレームの間にアクティブ化されるべきノードのリストを含んでもよい。
【００５８】
任意選択のダウンツリーおよびアップツリー・フレームが、根ノードから、および根ノードへ追加のメッセージを転送するために使用されてもよい。基本的に、通常のトラフィックは、ブロードキャストおよびコレクション・フレームの間に転送可能である。その結果、任意選択のフレームは、例えばブロードキャスト・フレームまたはコレクション・フレームの間に転送できない追加のメッセージを送るなど、例外的な場合に使用される。任意選択のフレームの存在は、前述のブロードキャスト・フレームまたはコレクション・フレーム内で送られるメッセージ内にセットされたフラグにより示されてもよい。
【００５９】
具体的には、ダウンツリー・フレームは、親ノードにより、その子ノードに追加のメッセージを送るために使用されてもよい。親ノードは、ブロードキャスト・フレーム内で送るメッセージ内に前述のフラグをセットすることにより、ダウンツリー・フレームの必要性を示してもよい。その結果、親によりセットされたフラグを確認する子ノードのみが、ダウンツリー・フレームの持続期間、受信モードになる。
【００６０】
さらに、アップツリー・フレームは、子ノードにより、その親ノードに追加のメッセージを送るために使用されてもよい。ダウンツリー・フレームと同様に、子ノードは、その親ノードへ前述のコレクション・フレームの間に送るメッセージ内に適切なフラグをセットすることにより、アップツリー・フレームを要求してもよい。その結果、子のうちの１つによりセットされたフラグを確認する親ノードのみが、アップツリー・フレームの持続期間、アクティブ化される。
【００６１】
任意選択のフレームの間、複数のノードが同時に送ることができる。したがって、ノードは、衝突および干渉を削減するためにキャリア検知多重アクセス（ＣＳＭＡ）を使用してもよい。
【００６２】
さらなる実施形態では、前記アップツリー・フレームをアクティブ化するためのアップツリー・フレーム要求は、個々の子ノードによりその親ノードへ、親ノードのために割り当てられたコレクション・フレーム内のスロット内で送信される。
【００６３】
このように、最初の要求元ノード、すなわち子ノードからその親ノードへの、アップツリー・フレーム要求の送信が提供されてもよい。
【００６４】
さらなる実施形態では、前記アップツリー・フレームをアクティブ化するためのアップツリー・フレーム要求は、最初の要求元ノードから、根ノードに達するまで中継される。
【００６５】
そのような場合、前記最初の要求元ノードから根ノードまでのパス上に配置されているネットワークのノードはすべて、この任意選択のアップツリー・フレームの間、アクティブ化されてもよい。
【００６６】
さらなる実施形態では、ダウンツリー・フレームおよびアップツリー・フレームは、タイム・スロット化される。あるいは、ダウンツリー・フレームおよびアップツリー・フレームは、スロット化されなくてもよい。
【００６７】
さらなる実施形態では、スーパーフレームには、ブロードキャスト・フレーム、少なくとも１つのコレクション・フレーム、少なくとも１つのダウンツリー・フレーム、少なくとも１つのアップツリー・フレーム、少なくとも１つのリスニング・フレーム、および空フレームが提供される。リスニング・フレームは、シンク・ノードまたは根ノードと管理メッセージを交換するために、非同期ノードにより使用されてもよい。非同期ノードは、その親との同期を失ったノード、または例えば稼働中のネットワークに新たに追加されたノードなどのまだ親がないノードである。すべての同期ノードは、このフレームの間、リスニング・モードまたは受信モードであり、このフレームの間に受信されたメッセージを、その親を介して根ノードへ転送する。非同期ノードがリスニング・フレームの開始を検知するのを支援するために、同期ノードにより送られるメッセージはすべて、次のリスニング・フレームがいつ開始するかの指示を含んでもよい。例えば、ネットワークに新たに追加されたノードは、チャネルをリッスンし、受信されるメッセージをすべて復号して、次のリスニング・フレームがいつ開始するかを判断してもよい。続いて、リスニング・フレームの間に、例えばＣＳＭＡを使用して、近隣ノードのうちの１つへ、例えばネットワークに参加するための要求などの管理メッセージを送ってもよい。近隣ノードは、例えばコレクション・フレームの間など、それに割り当てられている送信スロットのうちの１つの間に、このメッセージを根へ転送してもよい。
【００６８】
フレームおよびスロットの持続期間の値の例は以下のとおりである：
−スーパーフレーム：５ｓ〜１０ｍｉｎ；
−スロット：１０ｍｓ〜５０ｍｓ；
−ブロードキャスト・フレーム：ネットワーク内の親ノードと同数のスロット；
−コレクション・フレーム：ネットワークのトポロジおよびスーパーフレーム毎に根ノードへ送らなければならないメッセージの数によるが、典型的には５０〜２００スロット；
−リスニング・フレーム：２〜５スロット；
−ダウンツリー・フレーム：２〜５スロット；および
−アップツリー・フレーム：５〜１００スロット
【００６９】
第１の側面の任意の実施形態が、第１の側面の任意の実施形態と組み合わされて、第１の側面の別の実施形態が得られてもよい。
【００７０】
第２の側面によれば、本発明は、少なくとも１つのコンピュータ上で実行されると、ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信する第１の側面の方法を実行するための、プログラム・コードを含むコンピュータ・プログラムに関する。
【００７１】
第３の側面によれば、ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信するためのデバイスが提案される。ネットワークは、Ｎ個のクラスタ別にクラスタ化され、Ｎ個のクラスタの各クラスタは、いくつかのノードを有する。デバイスは、オーガナイザ、プロバイダ、およびセレクタを含む。オーガナイザは、ＴＤＭＡスキームを周期的なスーパーフレームへと編成するよう構成され、周期的なスーパーフレームの各スーパーフレームは、Ｎ個のクラスタに対して、少なくとも１つのブロードキャスト・フレームおよび１つのコレクション・フレームを含むいくつかのフレームを有する。プロバイダは、コレクション・フレーム内でＮ個のクラスタにより使用される別々のＮ個の通信チャネルを提供するよう構成される。さらに、セレクタは、ブロードキャスト・フレーム内でＮ個のクラスタにより共有される１つの通信チャネルを、別々のＮ個の通信チャネルから選択し、さらに、別々のＮ個の通信チャネルのうちの１つを、コレクション・フレーム内で使用されるようＮ個のクラスタのうちの１つに割り当てるよう構成される。
【００７２】
オーガナイザは、任意の編成手段とされ得る。プロバイダは、任意の提供手段とされ得る。さらに、セレクタは、任意の選択手段とされ得る。
【００７３】
個々の手段、具体的にはオーガナイザ、プロバイダ、およびセレクタは、ハードウェアまたはソフトウェアにおいて実装され得る。前記手段がハードウェアにおいて実装される場合、例えばコンピュータとして、またはプロセッサとして、または例えばコンピュータ・システムなどのシステムの一部としてなど、デバイスとして具現化され得る。前記手段がソフトウェアにおいて実装される場合、コンピュータ・プログラム製品として、関数として、ルーチンとして、プログラム・コードとして、または実行可能オブジェクトとして具現化され得る。
【００７４】
第４の側面によれば、複数のノードを含むマルチホップ・ネットワークが提案される。複数のノードの各ノードは、第１の側面の方法によるＴＤＭＡスキームにノードが従うことを可能にするプロセッサを有する。
【００７５】
下記では、本発明の例示的な実施形態について、添付の図面を参照して記載する。
【００７６】
図面内の類似した、または機能的に類似した構成要素には、別途示されていなければ同じ参照符号が割り振られている。
【図面の簡単な説明】
【００７７】
【図１】ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信するための一連の方法ステップの第１の実施形態を示す。
【図２】ＴＤＭＡベースのマルチホップ・ネットワークの実施形態の図を示す。
【図３】スーパーフレームの実施形態の図を示す。
【図４】ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信するための一連の方法ステップの第２の実施形態を示す。
【図５】ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信するための一連の方法ステップの第３の実施形態を示す。
【図６】ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信するためのデバイスのブロック図を示す。
【図７】ブロードキャスト・フレーム、コレクション・フレーム、リスニング・フレーム、および３つの通信チャネルを用いる、概略のＴＤＭＡスキームを示す。
【図８】ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信する方法を実行するのに適したシステムの実施形態の概略ブロック図を示す。
【発明を実施するための形態】
【００７８】
本発明は、ＴＤＭＡベースのマルチホップ・ネットワークに適応し得る。マルチホップ・ネットワークのノードは、種々のレベルに配置され得る。
【００７９】
この関連で、図１は、ＴＤＭＡベースのマルチホップ・ネットワークのノード間でデータを送信するための一連の方法ステップの第１の実施形態を示す。ＴＤＭＡベースのマルチホップ・ネットワークの実施形態の図を示す図２を参照しながら、図１の方法について説明する。
【００８０】
図２を参照する。各ノードは、２文字を含む参照番号を有する。第１の文字は、マルチホップ・ネットワークにおける個々のノードのレベルを示し、根ノードは第１の文字として「０」を有する。第２の文字は、個々のレベルにおける連続番号を示す。例えば、レベルＬ１には、１１により示される第１のノードおよび１２により示される第２のノードがある。
【００８１】
根ノードまたはシンク・ノード０１へ向かう経路は、シンク・ノード０１を根とするツリーを形成する。ここで、ツリー構成は既に実行されていると仮定する。さらに、ノード０１〜３７は、メッセージのヘッダに含まれるソース・ルーティング情報に基づきメッセージをルーティングできてもよい。このように、マルチホップ・ネットワークにおいてシンク・ノードにより宛先ノードへ送られるメッセージが中継されてもよい。
【００８２】
図２のネットワークは、２つのクラスタＣ１、Ｃ２（Ｎ＝２）へとクラスタ化される。一般性を失うことなく、図２のネットワークは、２つのクラスタＣ１、Ｃ２を有する。第１のクラスタＣ１は、ノード０１、１１、２１、２２、３１、３２、および３３を有する。したがって、第１のクラスタＣ１は、主基地局０１を含む。第２のクラスタＣ２は、ノード１２、２３、２４、３４、３５、３６、および３７を含む。図２のマルチホップ・ネットワークの各ノード０１〜３７は、図１のステップ１０１〜１０３に記載されているＴＤＭＡスキームにノード０１〜３７が従うことを可能にする、プロセッサ（図示せず）を有する。
【００８３】
ステップ１０１において、ＴＤＭＡスキームが、周期的なスーパーフレームにより編成される。個々のスーパーフレームは、少なくともブロードキャスト・フレームおよびコレクション・フレームを含むいくつかのフレームを有する。
【００８４】
この関連で、図３は、スーパーフレーム３００の実施形態の図を示す。図３のスーパーフレーム３００は、ブロードキャスト・フレーム３１０、コレクション・フレーム３２０、リスニング・フレーム３３０、ダウンツリー・フレーム３４０、アップツリー・フレーム３５０、および空フレーム３６０を有する。ブロードキャスト・フレーム３１０は、特に、スーパーフレーム３００の初めに配置されてもよい。
【００８５】
ダウンツリー・フレーム３４０は、ダウンツリー・フレーム要求が受信された場合にアクティブ化されてもよい。ダウンツリー・フレーム３４０は、少なくとも１つのダウンツリー・メッセージをマルチホップ・ネットワーク内の少なくとも１つのノードへ送信するよう構成されてもよい。
【００８６】
具体的には、マルチホップ・ネットワークの単一の分岐がアクティブ化されるように、ダウンツリー・フレーム要求が、ブロードキャスト・フレーム３１０内の割り当てられたスロットにより、子ノードへ送信されてもよい。あるいは、マルチホップ・ネットワークの複数の分岐がアクティブ化されるように、ダウンツリー・フレーム要求が、ブロードキャスト・フレーム３１０内の割り当てられたスロットにより、子ノードへ送信されてもよい。
【００８７】
前記アップツリー・フレーム３５０は、マルチホップ・ネットワークにおいてアップツリー・フレーム要求があるとアクティブ化されてもよい。
【００８８】
具体的には、マルチホップ・ネットワークの単一の分岐がアクティブ化されるように、前記アップツリー・フレーム要求が、ブロードキャスト・フレーム３１０内の割り当てられたスロットにより、子ノードへ送信されてもよい。あるいは、マルチホップ・ネットワークの複数の分岐がアクティブ化されるように、アップツリー・フレーム要求が、ブロードキャスト・フレーム３１０内の割り当てられたスロットにより、子ノードへ送信されてもよい。
【００８９】
さらに、前記コレクション・フレーム３２０は、確定的データを根ノード０１へ周期的に送信するのに適したものであってもよい。前記周期的に送信される確定的データは、センサ・データであってもよい。さらに、前記アップツリー・フレーム３５０をアクティブ化するための前記アップツリー・フレーム要求は、個々の子ノードによりその親ノードへ、親ノードのために割り当てられたコレクション・フレーム３２０内のスロット内で送信されてもよい。この関連で、アップツリー・フレーム３５０要求は、最初の要求元ノードから、根ノード０１に達するまで中継されてもよい。
【００９０】
さらに、リスニング・フレーム３３０は、マルチホップ・ネットワーク内の同期ノードの中で管理メッセージを交換するのに適したものであってもよい。
【００９１】
スーパーフレーム３００の空フレーム３６０または空の部分の間、ノード０１〜３７は、スリープ・モードである。
【００９２】
さらに、スーパーフレーム３００の種々のフレーム３１０〜３６０は、種々の持続時間Ｔ１〜Ｔ６を有してもよい。
【００９３】
ステップ１０２において、ブロードキャスト・フレーム３１０内で、１つの専用通信チャネルが２つのクラスタＣ１、Ｃ２により共有される。具体的には、ブロードキャスト・フレーム３１０内で、２つのクラスタＣ１、Ｃ２のすべてのノード０１〜３７にわたる単一のブロードキャスト・ツリーが、主基地局０１により使用され、ネットワークの他のノード１１〜３７すべてに情報が配信される。その場合、ブロードキャスト・ツリーは、主基地局０１を根とするネットワークのトポロジから計算されてもよい。
【００９４】
ステップ１０３において、コレクション・フレーム３２０内で、別々の２つの通信チャネルが２つのクラスタＣ１、Ｃ２により使用される。具体的には、コレクション・フレーム３２０内で、各クラスタＣ１、Ｃ２は、それ自体のコレクション・ツリーを有し、該コレクション・ツリーは、クラスタＣ１についてはノード０１、１１、２１、２２、３１、３２、３３を備え、クラスタＣ２についてはノード１２、２３、２４、３４、３５、３６、３７を備え、個々のクラスタＣ１、Ｃ２に属するノードのみにわたり、当該クラスタＣ１、Ｃ２のノードによって前記クラスタＣ１、Ｃ２の基地局０１、１２と情報を交換するために使用される。クラスタＣ１については、ノード０１が基地局である。さらに、クラスタＣ２については、ノード１２が基地局である。
【００９５】
さらに、個々のクラスタＣ１、Ｃ２の個々のコレクション・ツリーは、クラスタＣ１、Ｃ２の個々の基地局０１、１２を根とする個々のクラスタＣ１、Ｃ２のトポロジから計算される。例えば、クラスタＣ１のコレクション・ツリーは、クラスタＣ１の基地局０１を根とするクラスタＣ１のトポロジから計算される。さらに、クラスタＣ２のコレクション・ツリーは、クラスタＣ２の基地局１２を根とするクラスタＣ２のトポロジから計算される。クラスタＣ１、Ｃ２のコレクション・ツリーのトポロジは、必ずしも、図２に示されているブロードキャスト・ツリーと重ならなければならないわけではない。例として、ノード３５は、そのデータを、２３を通じて基地局１２へ送ることもできるであろう。
【００９６】
図４には、ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信するための一連の方法ステップの第２の実施形態が示されている。図４の実施形態は、方法ステップ４０１〜４０４を有する。
【００９７】
ステップ４０１において、各スーパーフレーム３００が少なくともブロードキャスト・フレーム３１０、コレクション・フレーム３２０、およびリスニング・フレーム３３０を有するように、ＴＤＭＡスキームが周期的なスーパーフレームにより編成される。
【００９８】
ステップ４０２において、ブロードキャスト・フレーム３１０内で、１つの専用通信チャネルが２つのクラスタＣ１、Ｃ２により共有される。
【００９９】
ステップ４０３において、コレクション・フレーム３２０内で、別々の２つの通信チャネルが２つのクラスタＣ１、Ｃ２により使用される。
【０１００】
さらに、ステップ４０４において、リスニング・フレーム３３０内で、１つの専用チャネルが２つのクラスタＣ１、Ｃ２により共有される。
【０１０１】
非同期ノード０１〜３７をネットワークと同期させるために、リスニング・フレーム３３０内でＣＳＭＡまたはＭＡＣＡを使用して情報が交換される。あるいは、非同期ノード０１〜３７をネットワークと同期させるために、リスニング・フレーム３３０の初めにブラック・バーストが送信されてもよい。
【０１０２】
図５には、ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード０１〜３７間でデータを送信するための一連の方法ステップの第３の実施形態が示されている。図５の実施形態は、方法ステップ５０１〜５０６を有する。
【０１０３】
ステップ５０１において、各スーパーフレーム３００が少なくともブロードキャスト・フレーム３１０、コレクション・フレーム３２０、リスニング・フレーム３３０、ダウンツリー・フレーム３４０、およびアップツリー・フレーム３５０を有するように、ＴＤＭＡスキームが周期的なスーパーフレームにより編成される。
【０１０４】
ステップ５０２において、ブロードキャスト・フレーム内で、１つの専用通信チャネルが２つのクラスタＣ１、Ｃ２により共有される。
【０１０５】
ステップ５０３において、コレクション・フレーム内で、別々の２つの通信チャネルが２つのクラスタＣ１、Ｃ２により使用される。
【０１０６】
ステップ５０４において、リスニング・フレーム３３０内で、１つの専用通信チャネルが２つのクラスタＣ１、Ｃ２により共有される。
【０１０７】
ステップ５０５において、ダウンツリー・フレーム３４０内で、別々の２つの通信チャネルが２つのクラスタＣ１、Ｃ２により使用される。
【０１０８】
類似した形で、ステップ５０６において、アップツリー・フレーム３５０内で、別々の２つの通信チャネルが２つのクラスタＣ１、Ｃ２により使用される。
【０１０９】
図６は、ＴＤＭＡスキームを用いるマルチホップ・ネットワークのノード間でデータを送信するためのデバイス６０のブロック図を示す。ネットワークは、Ｎ個のクラスタＣ１、Ｃ２別にクラスタ化される。各クラスタＣ１、Ｃ２は、いくつかのノード０１、１１、２１、２２、３１、３２、３３；１２、２３、２４、３４、３５、３６、３７（図２参照）を有する。
【０１１０】
デバイス６０は、オーガナイザ６１、プロバイダ６２、およびセレクタ６３を含む。オーガナイザ６１は、ＴＤＭＡスキームを周期的なスーパーフレームへと編成するよう構成され、周期的なスーパーフレームの各スーパーフレームは、Ｎ個のクラスタに対して、少なくとも１つのブロードキャスト・フレームおよび１つのコレクション・フレームを含むいくつかのフレームを有する。
【０１１１】
プロバイダ６２は、コレクション・フレーム内でＮ個のクラスタにより使用される、別々のＮ個の通信チャネルを提供するよう構成される。
【０１１２】
さらに、セレクタ６３は、ブロードキャスト・フレーム内でＮ個のクラスタにより共有される１つの通信チャネルを、別々のＮ個の通信チャネルから選択し、さらに、別々のＮ個の通信チャネルのうちの１つを、コレクション・フレーム内で使用されるようＮ個のクラスタのうちの１つに割り当てるよう構成される。
【０１１３】
図７は、ブロードキャスト・フレーム３１０、コレクション・フレーム３２０、リスニング・フレーム３３０、および３つのクラスタＣ１、Ｃ２、およびＣ３のための３つの通信チャネルＡ、Ｂ、Ｃを備える、概略のＴＤＭＡスキームを示す。ブロードキャスト・フレーム３１０、コレクション・フレーム３２０、およびリスニング・フレーム３３０はそれぞれタイム・スロット化されており、いくつかのスロットＳを有する。
【０１１４】
ブロードキャスト・フレーム３１０内およびリスニング・フレーム３３０内で、通信チャネルＢは３つのクラスタＣ１、Ｃ２、Ｃ３により共有される。対照的に、コレクション・フレーム３２０内では、各クラスタＣ１、Ｃ２、Ｃ３は、チャネルＡ、Ｂ、Ｃの別々のチャネルを使用する。３つのクラスタＣ１、Ｃ２、Ｃ３に対して３つのチャネルＡ、Ｂ、Ｃがあると仮定すると、コレクション・フレーム３２０内では、クラスタＣ１がチャネルＡを使用してもよく、クラスタＣ２がチャネルＢを使用してもよく、クラスタＣ３がチャネルＣを使用してもよい。
【０１１５】
共有されるブロードキャストおよびリスニング・フレーム３１０、３３０のための共有チャネルＢは、時間参照をネットワーク内のすべてのノードに配信するために使用され得るため、同期チャネルとも呼ぶことができる。このように、クラスタＣ１、Ｃ２、Ｃ３を時間同期するための容易かつ単純な方法が提供される。
【０１１６】
詳細には、各クラスタＣ１、Ｃ２、Ｃ３は、それ自体のコレクション・フレーム３２０を有し、それらは別々のチャネルＡ、Ｂ、Ｃ上で送られる。さらに、クラスタＣ２は、そのコレクション・フレーム３２０に、同期チャネルＢとは別のチャネルを使用してもよい。
【０１１７】
なお、図７のリスニング・フレーム３３０の位置に関して、リスニング・フレーム３３０がコレクション・フレーム３２０の後に続いている。この場合、その位置についての情報は、葉ノードによって、そのコレクション・スロット内で送られてもよい。その位置についての情報は、ブロードキャスト・フレーム３１０内でもブロードキャストされ、その結果、リスニング・フレーム３３０は、例えばブロードキャスト・フレーム３１０の直後に転送されてもよい。
【０１１８】
コンピュータ・デバイスは、本願明細書に記載された本発明の実施形態を実装するよう適切に設計できる。その点に関して、本願明細書に記載された方法は、主として非対話型で、自動化されていることが理解できる。例示的な実施形態では、本願明細書に記載された方法は、対話型、部分的に対話型、または非対話型のシステムのいずれかにおいて実装できる。本願明細書に記載された方法は、ソフトウェア（例えばファームウェア）、ハードウェア、またはその組み合わせにおいて実装できる。例示的な実施形態では、本願明細書に記載された方法は、ソフトウェアにおいて、実行可能プログラムとして実装され、後者は、適切なデジタル処理デバイスにより実行される。さらなる例示的な実施形態では、図１、図４または図５の上記の方法の少なくとも１つのステップまたはすべてのステップは、ソフトウェアにおいて、実行可能プログラムとして実装されてもよく、後者は、適切なデジタル処理デバイスにより実行される。より一般的には、パーソナル・コンピュータ、ワークステーションなどの汎用デジタル・コンピュータが使用される本発明の実施形態を実装することができる。
【０１１９】
例として、図８に示されているシステム８００は、例えば汎用コンピュータなどのコンピュータ・ユニット８０１を概略的に表現する。例えば、システム８００は、図２に示されているノード０１〜３７を具現化してもよい。例示的な実施形態では、図８に示されているように、ハードウェア・アーキテクチャの点で、ユニット８０１は、プロセッサ８０５、メモリ・コントローラ８１５に結合されたメモリ８１０、およびローカル入力／出力コントローラ８３５を介して通信可能に結合されている１つ以上の入力もしくは出力またはその両方の（Ｉ／Ｏ）デバイス８４０、８４５、８５０、８５５（または周辺装置）を含む。入力／出力コントローラ８３５は、当該技術分野で既知のように、１つ以上のバスまたはその他有線もしくは無線接続とすることができるが、これに限定はされない。入力／出力コントローラ８３５は、通信を可能にするために、コントローラ、バッファ（キャッシュ）、ドライバ、リピータ、および受信器など、簡潔性のために省略されている追加の構成要素を有してもよい。さらに、ローカル・インターフェースは、前述のコンポーネント間の適切な通信を可能にするために、アドレス、制御、もしくはデータ接続、またはそのいずれかの組み合わせを含んでもよい。例えば、プロセッサ８０５は、図１、図４または図５の実施形態のうちの１つに記載されているＴＤＭＡスキームにノード０１〜３７が従うことを可能にするよう構成されてもよい。
【０１２０】
プロセッサ８０５は、ソフトウェア、特にメモリ８１０に記憶されているソフトウェアを実行するためのハードウェア・デバイスである。プロセッサ８０５は、特別仕様または市販の任意のプロセッサ、中央処理ユニット（ＣＰＵ：ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）、コンピュータ８０１に関連するいくつかのプロセッサの中の補助プロセッサ、半導体ベースのマイクロプロセッサ（マイクロチップまたはチップセットの形態）、または広く、ソフトウェア命令を実行するための任意のデバイスとすることができる。
【０１２１】
メモリ８１０は、揮発性メモリ要素（例えばランダム・アクセス・メモリ）および不揮発性メモリ要素のうちの任意の１つまたは組み合わせを含むことができる。さらに、メモリ８１０は、電子、磁気、光学、もしくはその他のタイプ、またはそのいずれかの組み合わせの記憶媒体を含んでもよい。なお、メモリ８１０は、様々なコンポーネントが互いに離れて位置するがプロセッサ８０５によりアクセス可能である、分散アーキテクチャを有することができる。
【０１２２】
メモリ８１０内のソフトウェアは、１つ以上の別々のプログラムを含んでもよく、そのそれぞれが、論理機能を実装するための実行可能命令の順序づけられたリスティングを含む。図８の例では、メモリ８１０内のソフトウェアは、例示的な実施形態に従って本願明細書に記載された方法、および適切なオペレーティング・システム（ＯＳ：ｏｐｅｒａｔｉｎｇ  ｓｙｓｔｅｍ）８１１を含む。ＯＳ８１１は、本願明細書に記載された方法（例えば図１、図４または図５）などの他のコンピュータ・プログラムの実行を基本的に制御し、スケジューリング、入出力制御、ファイルおよびデータ管理、メモリ管理、ならびに通信制御および関連サービスを提供する。
【０１２３】
本願明細書に記載された方法は、ソース・プログラム、実行可能プログラム（オブジェクト・コード）、スクリプト、または実行される命令のセットを含むその他任意の実体の形態とされ得る。ソース・プログラムの形態である場合、プログラムは、ＯＳ８１１に関連して適切に動作するよう、元来周知のように、コンパイラ、アセンブラ、インタープリタ、または同様のものを介して変換される必要があり、これらはメモリ８１０内に含まれていることも、いないこともある。さらに、方法は、データおよびメソッドのクラスを有するオブジェクト指向プログラミング言語、またはルーチン、サブルーチン、もしくは関数、またはそのいずれかの組み合わせを有する手続きプログラミング言語として書くことができる。
【０１２４】
場合によっては、従来のキーボード８５０およびマウス８５５を入力／出力コントローラ８３５に結合できる。他のＩ／Ｏデバイス８４０〜８５５は、センサ（特にネットワーク構成要素の場合）、すなわち温度または圧力のような物理条件の変化に対して測定可能な応答（モニタリングされる物理データ）を生じるハードウェア・デバイスを含んでもよい。典型的には、センサにより生じるアナログ信号は、アナログ・デジタル変換器によりデジタル化され、さらなる処理のためにコントローラ８３５へ送られる。センサ・ノードは、小型で消費エネルギーが低く、自律型で自動運転するものが理想的である。
【０１２５】
さらに、Ｉ／Ｏデバイス８４０〜８５５は、入力および出力の両方を伝達するデバイスをさらに含んでもよい。システム８００は、ディスプレイ８３０に結合されたディスプレイ・コントローラ８２５をさらに含むことができる。例示的な実施形態では、システム８００は、ネットワーク８６５に結合するためのネットワーク・インターフェースまたは送受信機８６０をさらに含むことができる。
【０１２６】
ネットワーク８６５は、ユニット８０１と外部システムとの間でデータを送受信する。ネットワーク８６５は、場合により、例えばＩＥＥＥ８０２．１５．４または類似のものなどの無線プロトコルおよび技術を使用するなど、無線方式で実装される。ネットワーク８６５は、固定無線ネットワーク、無線ローカル・エリア・ネットワーク（ＬＡＮ：ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）、無線広域ネットワーク（ＷＡＮ：ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ）、パーソナル・エリア・ネットワーク（ＰＡＮ：ｐｅｒｓｏｎａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ）、仮想プライベート・ネットワーク（ＶＰＮ：ｖｉｒｔｕａｌ  ｐｒｉｖａｔｅ  ｎｅｔｗｏｒｋ）、イントラネット、またはその他適切なネットワーク・システムであってもよく、信号を送受信するための機器を含む。
【０１２７】
ユニット８０１の動作中、プロセッサ８０５は、メモリ８１０内に記憶されたソフトウェアを実行し、メモリ８１０と相互にデータを伝達し、ソフトウェアに従ってコンピュータ８０１の動作を全般的に制御するよう構成されている。本願明細書に記載された方法、およびＯＳ８１１は、全体的または部分的に、プロセッサ８０５により読み取られ、典型的にはプロセッサ８０５内にバッファリングされ、続いて実行される。本願明細書に（例えば図１、図４または図５を参照して）記載された方法がソフトウェアにおいて実装される場合、方法は、任意のコンピュータ関連システムまたは方法により、またはそれに関連して使用されるよう、記憶装置８２０などの任意のコンピュータ可読媒体上に記憶できる。
【０１２８】
当業者であれば当然のことであるが、本発明の各側面は、システム、方法またはコンピュータ・プログラム製品として具現化され得る。したがって、本発明の各側面は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、またはソフトウェアおよびハードウェアの側面を組み合わせる実施形態の形態をとり得る。さらに、本発明の各側面は、コンピュータ可読プログラム・コードが具現化された１つ以上のコンピュータ可読媒体（単数または複数）において具現化された、コンピュータ・プログラム製品の形態をとることもできる。１つ以上のコンピュータ可読媒体（単数または複数）の任意の組み合わせが利用され得る。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体とされ得る。コンピュータ可読記憶媒体は、例えば、限定はされないが、電子、磁気、光学、電磁気、赤外線もしくは半導体のシステム、装置もしくはデバイス、または前述のものの任意の適切な組み合わせとされ得る。コンピュータ可読記憶媒体のより具体的な例（包括的でないリスト）には、１つ以上のワイヤを有する電気的接続、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）、読み取り専用メモリ（ＲＯＭ：ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、消去可能プログラム可能読み取り専用メモリ（ＥＰＲＯＭ（ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）もしくはフラッシュ・メモリ）、光ファイバ、ポータブル・コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ：ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）、光学式記憶デバイス、磁気記憶デバイスまたは前述のものの任意の適切な組み合わせが含まれるであろう。この文書の文脈では、コンピュータ可読記憶媒体は、命令実行システム、装置もしくはデバイスによって、またはそれに関連して使用されるプログラムを含むこと、または記憶することができる任意の有形の媒体とされ得る。
【０１２９】
コンピュータ可読信号媒体は、例えば、ベースバンドに、または搬送波の一部としてコンピュータ可読プログラム・コードが具現化された、伝搬データ信号を含み得る。そのような伝搬信号は、電磁気、光学またはその任意の適切な組み合わせを含むがこれらに限定はされない、様々な形態のいずれかをとってよい。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体でなく、かつ命令実行システム、装置もしくはデバイスによって、またはそれに関連して使用されるプログラムの伝達、伝搬または搬送をすることができる、任意のコンピュータ可読媒体としてよい。コンピュータ可読媒体上に具現化されたプログラム・コードは、無線、有線、光ファイバ・ケーブル、ＲＦなど、または前述のものの任意の適切な組み合わせを含むがこれらに限定はされない、任意の適切な媒体を使用して送信され得る。
【０１３０】
本発明の各側面の動作を実行するコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋または同様のものなどのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語もしくは同様のプログラミング言語などの従来の手続きプログラミング言語を含む、１つ以上のプログラミング言語の任意の組み合わせで書かれていてよい。プログラム・コードは、完全にユニット８０１上で実行されてもよく、部分的にユニット８０１上で実行されてもよく、ユニット８０１と、類似または非類似の別のユニット８０１とで部分的に実行されてもよい。
【０１３１】
本発明の各側面について、本発明の実施形態による方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図もしくはブロック図またはその両方を参照して上述している。当然のことながら、フローチャート図もしくはブロック図またはその両方の各ブロックは、１つ以上のコンピュータ・プログラム命令により実装可能である。マシンを生じるよう、こうしたコンピュータ・プログラム命令が、汎用コンピュータ、専用コンピュータ、またはその他プログラム可能データ処理装置のプロセッサに提供されて、この命令が、コンピュータまたはその他プログラム可能データ処理装置のプロセッサにより実行されて、フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて指定された機能／動作を実装する手段をもたらすようにすることもできる。
【０１３２】
さらに、コンピュータ・プログラム命令は、コンピュータ、その他プログラム可能データ処理装置、またはその他デバイスにロードされて、コンピュータ、その他プログラム可能装置、またはその他デバイス上で一連の動作ステップが実行されるようにしてコンピュータで実装されるプロセスを生じさせ、コンピュータまたはその他プログラム可能装置上で実行される命令が、フローチャートもしくはブロック図またはその両方の１つまたは複数のブロックにおいて指定された機能／動作を実装するためのプロセスを提供するようにすることもできる。
【０１３３】
各図面のフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法およびコンピュータ・プログラム製品の考えられる実装のアーキテクチャ、機能性、および動作を示す。この関連で、フローチャートまたはブロック図内の各ブロックは、指定の論理機能（単数または複数）を実装する１つ以上の実行可能命令を含むモジュール、セグメント、またはコードの一部を表すこともできる。なお、さらに、いくつかの代わりの実装では、ブロック内に示されている機能は、図面に示されているのとは異なる順序で生じてもよい。例えば、関連する機能性およびアルゴリズム最適化によっては、連続して示されている２つのブロックが実際には事実上同時に実行されてもよく、または各ブロックが逆順で実行されることがあってもよい。さらに、ブロック図もしくはフローチャート図またはその両方の各ブロック、およびブロック図もしくはフローチャート図またはその両方の複数ブロックの組み合わせは、指定の機能もしくは動作を実行する専用ハードウェア・ベース・システム、または専用ハードウェアおよびコンピュータ命令の組み合わせにより実装することができるということに留意されたい。
【０１３４】
より一般的に、本発明について、特定の実施形態を参照して記載してきたが、当業者には当然のことながら、本発明の範囲から逸脱することなく、様々な変更が加えられ、等価物が代わりに用いられてもよい。さらに、本発明の教示の範囲から逸脱することなく、本教示に特定の状況を適合させるよう多数の変更が加えられてもよい。したがって、本発明は、開示された特定の実施形態に限定されないが、添付の特許請求の範囲に記載の範囲内に入るすべての実施形態を含むものとする。
【０１３５】
参考文献
Ｓｏｂｒｉｎｈｏ，Ｊ．Ｌ．およびＫｒｉｓｈｎａｋｕｍａｒ，Ａ．Ｓ．著（１９９９年）、「Ｑｕａｌｉｔｙ−ｏｆ−ｓｅｒｖｉｃｅ  ｉｎ  ａｄ  ｈｏｃ  ｃａｒｒｉｅｒ  ｓｅｎｓｅ  ｍｕｌｔｉｐｌｅ  ａｃｃｅｓｓ  ｗｉｒｅｌｅｓｓ  ｎｅｔｗｏｒｋｓ」、ＩＥＥＥ  Ｊｏｕｒｎａｌ  ｏｎ  Ｓｅｌｅｃｔｅｄ  Ａｒｅａｓ  ｉｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ、第１７巻第８号、Ｐ．１３５３〜１３６８
【図１】
2014532346.tif 000003
【図２】
2014532346.tif 000004
【図３】
2014532346.tif 000005
【図４】
2014532346.tif 000006
【図５】
2014532346.tif 000007
【図６】
2014532346.tif 000008
【図７】
2014532346.tif 000009
【図８】
2014532346.tif 000010
【国際調査報告】
2014532346.tif 000011
2014532346.tif 000012