(57)【要約】【課題】パーティションに基づくスロット割り当て方法及び装置を提供する。【解決手段】該方法は、マルチホップセンサネットワークにおけるシンクノード以外のノードに適用するものであって、ノードが属するサブツリーのサブツリー情報を含む検出要求パケットをブロードキャスト送信し、他のノードから送信された、他のノードが属するサブツリーのサブツリー情報を含む検出要求パケットに基づいて、他のノードとノードとが同一のサブツリー内に位置するか否かを決定し、他のノードとノードとが同一のサブツリー内に位置しない場合、他のノードが属するサブツリーのサブツリー情報をローカルの衝突テーブルに記憶し、ノードの親ノードにローカルの衝突テーブルを送信する。該サブツリーがシンクノードから１ホップ離れたノードをルートノードとする。【選択図】図４
2015089121.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークにおけるノードであって、
前記ノードが属するサブツリーのサブツリー情報を含む検出要求パケットをブロードキャスト送信する送信手段であって、前記サブツリーがシンクノードから１ホップ離れたノードをルートノードとする、送信手段と、
他のノードから送信された、他のノードが属するサブツリーのサブツリー情報を含む検出要求パケットに基づいて、前記他のノードと前記ノードとが同一のサブツリー内に位置するか否かを決定する決定手段と、
前記他のノードと前記ノードとが同一のサブツリー内に位置しない場合、前記他のノードが属するサブツリーのサブツリー情報をローカルの衝突テーブルに記憶し、前記ノードの親ノードにローカルの衝突テーブルを送信する処理手段と、を含むノード。
【請求項２】
前記ノードの全ての１ホップ子ノードからの衝突テーブルパケットを受信する第１の受信手段と、
受信された衝突テーブルパケットに基づいてローカルの衝突テーブルを更新し、前記ノードの親ノードに更新されたローカルの衝突テーブルを送信する更新手段と、をさらに含む請求項１に記載のノード。
【請求項３】
前記更新手段は、
受信された各衝突テーブルパケットにおける各サブツリー情報を走査する走査モジュールと、
前記ローカルの衝突テーブルに前記サブツリー情報が含まれている場合、前記サブツリー情報に対して処理を行わず、前記ローカルの衝突テーブルに前記サブツリー情報が含まれていない場合、前記サブツリー情報を前記ローカルの衝突テーブルに追加する処理モジュールと、を含む請求項２に記載のノード。
【請求項４】
前記ノードの親ノードから送信された、前記ノードが属するグループの関連情報及び予約可能なスロットリソースの範囲を含むスロット割り当て情報を受信する第２の受信手段と、
前記ノードが属するグループに基づいて、該グループに対応するスロットリソースにおいてスロットを割り当てるスロット割り当て手段と、をさらに含む請求項１に記載のノード。
【請求項５】
無線ネットワークにおけるシンクノードであって、
受信された、前記シンクノードの全ての１ホップ子ノードからの衝突テーブルパケットに基づいて、サブツリー間の衝突関係を決定する決定手段と、
各ノードが該ノードの属するグループに対応するスロットリソースにおいてスロットを割り当てるように、前記衝突関係に基づいて、全てのサブツリーをサブツリーごとに、同一のラウンド又は異なるラウンドに位置する複数のグループに分ける処理手段と、を含むシンクノード。
【請求項６】
同一のラウンドにおける各グループが占有可能なスロットリソースの範囲は同一であり、同一のラウンドにおける各グループのノードは互いに干渉せず、異なるラウンドにおける各グループが占有可能なスロットリソースの範囲は重ならない請求項５に記載のシンクノード。
【請求項７】
前記処理手段は、
現在のラウンドを決定する決定モジュールと、
所定のポリシーに従って、選択可能なサブツリーから第１の所定数のサブツリーを現在のラウンドの１番目のグループとして選択する第１の選択モジュールと、
残りのサブツリーに、現在のラウンドの他の全てのグループにおけるサブツリーと干渉せず、且つノードの数の和と現在のラウンドの他のいずれかのグループにおけるノードの数の和との差が第１の閾値未満である少なくとも１つのサブツリーが存在しているか否かを判断する第１の判断モジュールと、
存在していると前記第１の判断モジュールにより判断された場合、残りのサブツリーから現在のラウンドの次のグループのサブツリーを選択する第２の選択モジュールと、
存在していないと前記第１の判断モジュールにより判断された場合、選択されていないサブツリーがあるか否かを判断する第２の判断モジュールと、
あると前記第２の判断モジュールにより判断された場合、次のラウンドに進み、ないと前記第２の判断モジュールにより判断された場合、処理を終了する処理モジュールと、を含む請求項５に記載のシンクノード。
【請求項８】
前記第２の選択モジュールは、現在のラウンドの他の全てのグループにおけるサブツリーと干渉しないサブツリーから、第２の所定数のサブツリーを現在のラウンドの次のグループとして選択し、
前記次のグループにおけるノードの数の和と前記１番目のグループにおけるノードの数の和との差は第１の閾値未満である請求項７に記載のシンクノード。
【請求項９】
各サブツリーにおけるノードがそれぞれのグループにおいてスロットを割り当てるように、各サブツリーのルートノードに、各サブツリーのルートノードの属するグループの情報及び利用可能なスロットリソースの範囲の情報をそれぞれ送信する送信手段、をさらに含む請求項５に記載のシンクノード。
【請求項１０】
前記各サブツリーのルートノードに対して、異なるスロットを割り当てる割り当て手段、をさらに含み、
前記送信手段は、各サブツリーのルートノードに対して前記割り当て手段により割り当てられたスロットを、各サブツリーのルートノードに送信する請求項９に記載のシンクノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信分野に関し、特にパーティションに基づくスロット割り当て方法及び装置に関する。
【背景技術】
【０００２】
無線センサネットワークでは、隣接ノードが各自のデータパケットを同時に送信するとは、衝突が生じる場合がある。図１に示すように、ノードＡ及びノードＣは同一のスロットを占有して各自のデータパケットを送信し、隣接ノードＢは該スロットでデータパケットを受信するため、明らかな衝突が生じてしまう。
【０００３】
現在、このような衝突を回避するため、スロット割り当ての方法により、隣接ノードに異なるスロットで各自のデータパケットを送信させる。図２に示すように、ノードＡはスロットｎでデータパケットを送信し、ノードＣはスロットｍでデータパケットを送信し、隣接ノードＢはノードＡ及びノードＣから送信されたデータパケットを異なるスロットで受信する。よって、伝送の衝突を回避でき、パケットロスト（lost）を低減でき、より高いデータパケットの伝送率を図ることができる。
【０００４】
しかし、ネットワークが大きいほど、スロットの割り当てが難しくなる。複数のノードの場合では、１つのスロットについて、どのノードがこのスロットを予約できるかについての判定は複雑になり、ネゴシエーションのオーバーヘッド（例えば、ノードにおけるローカルテーブルのサイズ及び制御パケットのサイズ）も大きい。如何に上記の問題を軽減するかは業界の研究方向となる。
【０００５】
なお、上述した技術背景の説明は、本発明の技術案を明確、完全に理解させるための説明であり、当業者を理解させるために記述されているものである。これらの技術案は、単なる本発明の背景技術部分として説明されたものであり、当業者により公知されたものではない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の実施例は、大きいネットワークにおけるスロット割り当てをいくつかの比較的に小さいネットワークにおける（空間的及び時間的に）独立のスロット割り当てに変更することで、上記の問題点を解決できるパーティションに基づくスロット割り当て方法及び装置を提供することを主な目的とする。
【課題を解決するための手段】
【０００７】
本発明の実施例の第１の態様では、マルチホップセンサネットワークにおけるシンクノード以外のノードに用いられる、パーティションに基づくスロット割り当て方法であって、前記ノードが、前記ノードが属するサブツリーのサブツリー情報を含む検出要求パケットをブロードキャスト送信するステップであって、前記サブツリーがシンクノードから１ホップ離れたノードをルートノードとする、ステップと、他のノードから送信された、他のノードが属するサブツリーのサブツリー情報を含む検出要求パケットに基づいて、前記他のノードと前記ノードとが同一のサブツリー内に位置するか否かを決定するステップと、前記他のノードと前記ノードとが同一のサブツリー内に位置しない場合、前記他のノードが属するサブツリーのサブツリー情報をローカルの衝突テーブルに記憶し、前記ノードの親ノードにローカルの衝突テーブルを送信するステップと、を含むスロット割り当て方法を提供する。
【０００８】
本発明の実施例の第２の態様では、マルチホップセンサネットワークにおけるシンクノードに用いられる、パーティションに基づくスロット割り当て方法であって、前記シンクノードが、受信された、前記シンクノードの全ての１ホップ子ノードからの衝突テーブルパケットに基づいて、サブツリー間の衝突関係を決定するステップと、前記シンクノードが、各ノードが該ノードの属するグループに対応するスロットリソースにおいてスロットを割り当てるように、前記衝突関係に基づいて、全てのサブツリーをサブツリーごとに、同一のラウンド又は異なるラウンドに位置する複数のグループに分けるステップと、を含むスロット割り当て方法を提供する。
【０００９】
本発明の実施例の第３の態様では、無線ネットワークにおけるノードであって、前記ノードが属するサブツリーのサブツリー情報を含む検出要求パケットをブロードキャスト送信する送信手段であって、前記サブツリーがシンクノードから１ホップ離れたノードをルートノードとする、送信手段と、他のノードから送信された、他のノードが属するサブツリーのサブツリー情報を含む検出要求パケットに基づいて、前記他のノードと前記ノードとが同一のサブツリー内に位置するか否かを決定する決定手段と、前記他のノードと前記ノードとが同一のサブツリー内に位置しない場合、前記他のノードが属するサブツリーのサブツリー情報をローカルの衝突テーブルに記憶し、前記ノードの親ノードにローカルの衝突テーブルを送信する処理手段と、を含むノードを提供する。
【００１０】
本発明の実施例の第４の態様では、無線ネットワークにおけるシンクノードであって、受信された、前記シンクノードの全ての１ホップ子ノードからの衝突テーブルパケットに基づいて、サブツリー間の衝突関係を決定する決定手段と、各ノードが該ノードの属するグループに対応するスロットリソースにおいてスロットを割り当てるように、前記衝突関係に基づいて、全てのサブツリーをサブツリーごとに、同一のラウンド又は異なるラウンドに位置する複数のグループに分ける処理手段と、を含むシンクノードを提供する。
【００１１】
本発明の実施例の他の態様では、少なくとも１つの第３の態様に記載のノードと、第４の態様に記載のシンクノードと、を含む、ネットワークを提供する。
【００１２】
本発明の実施例の効果として、大きいネットワークにおけるスロット割り当てをいくつかの比較的に小さいネットワークにおける（空間的及び時間的に）独立のスロット割り当てに変更することで、上記の問題点を解決できる。
【００１３】
本発明の特定の実施形態は、後述の説明及び図面に示すように、詳細に開示され、本発明の原理を採用されることが可能な方式を示している。なお、本発明の実施形態は、範囲上には限定されるものではない。本発明の実施形態は、添付されている特許請求の範囲の主旨及び内容の範囲内、各種の改変、修正、及び同等的なものが含まれる。
【００１４】
ある一つの実施形態に説明及び又は示されている特徴は、同一又は類似の方式で一つ又は多くの他の実施形態に使用されてもよく、他の実施形態における特徴と組み合わせてもよく、他の実施形態における特徴を代替してもよい。
【００１５】
なお、用語「包括／含む」は、本文に使用される際に、特徴、要素、ステップ又は構成要件の存在を意味し、一つ又は複数の他の特徴、要素、ステップ又は構成要件の存在又は追加を排除するものではない。
【図面の簡単な説明】
【００１６】
ここで含まれる図面は、本発明の実施例を理解させるためのものであり、本明細書の一部を構成し、本発明の実施例を例示するためのものであり、文言の記載と合わせて本発明の原理を説明する。なお、ここに説明される図面は、単なる本発明の実施例を説明するためのものであり、当業者にとって、これらの図面に基づいて他の図面を容易に得ることができる。
【図１】スロット割り当てを行わない場合に生じた衝突を示す図である。
【図２】生じた衝突がスロット割り当てにより回避されたことを示す図である。
【図３】無線センサネットワークのトポロジーの一例を示す図である。
【図４】本発明の１つの実施例に係るパーティションに基づくスロット割り当て方法のフローチャートである。
【図５】検出要求パケットのフォーマットを示す図である。
【図６】衝突配列（衝突テーブル）のフォーマットを示す図である。
【図７】衝突配列パケット（衝突テーブルパケット）のフォーマットを示す図である。
【図８】衝突配列の更新のフローチャートである。
【図９】衝突配列パケットの受信及び更新のフローチャートである。
【図１０】本発明のもう１つの実施例に係るパーティションに基づくスロット割り当て方法のフローチャートである。
【図１１】シンクノードにより全ての１ホップサブツリーをグループに分ける方法を示す図である。
【図１２】本発明の実施例の１つの態様のスロット割り当てのフローチャートである。
【図１３】無線センサネットワークの一例を示す図である。
【図１４】図１３に示される無線センサネットワークにおける各１ホップサブツリーの衝突関係配列を示す図である。
【図１５】グループ分けの結果を示す図である。
【図１６】１ホップサブツリーのルートノードのために割り当てられたスロットが衝突しているかについてのシンクノードによるチェックを示す図である。
【図１７】スロット割り当てを示す図である。
【図１８】本発明の実施例に係る一般のノード（シンクノードに対して）の構成を示す図である。
【図１９】本発明の実施例に係るシンクノードの構成を示す図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照しながら本発明の各実施形態を説明する。これらの実施形態は単なる例示的なものであり、本発明を限定するものではない。当業者に本発明の原理及び実施形態をより簡単に理解させるため、本発明の実施形態では、マルチホップセンサネットワークにおけるパーティションに基づくスロット割り当て方法を例として説明している。なお、本発明の実施例は上記のネットワークに限定されず、スロット割り当てに関する他のネットワーク、例えばアドホック（ad hoc）ネットワーク、スマート電力グリッド（smart power grid）などにも適用されてもよい。即ち、本発明の実施例に係るスロット割り当て方法は、完全な連続性のツリートポロジー構造を有するネットワークに適用し、ルーティングアルゴリズムにより、どのルートでデータパケットをＳＩＮＫ（「ルート」）に伝送するかを決定してもよい。
【００１８】
本発明の実施例をより分かりやすくするため、まず、本発明の実施例に関するいくつかの概念を説明する。
【００１９】
本発明の実施例では、「ｓｉｎｋ」は、全てのアップロードされたデータを収集するノードを指し、説明の便宜上、シンクノードと称される。
【００２０】
本発明の実施例では、１ホップサブツリーは、ｓｉｎｋ（シンクノード）から１ホップ離れたノードをルートとするサブツリー、例えば図３におけるＨ、Ｌ及びＰをルートとするサブツリーを指す。
【００２１】
＜実施例１＞
本発明の実施例は、パーティションに基づくスロット割り当て方法を提供し、該方法は、無線ネットワーク、例えばマルチホップセンサネットワークにおけるシンクノード以外のノードに用いられる。図４は該方法のフローチャートであり、図４に示すように、該方法は以下のステップを含む。
【００２２】
ステップ４０１：該ノードが、該ノードが属するサブツリーのサブツリー情報を含む検出要求パケットをブロードキャスト送信する。該サブツリーは、シンクノードから１ホップ離れたノードをルートノードとする。
【００２３】
本実施例では、ルーティングが既に確立され、且つ各ノードが自分の属する１ホップサブツリーを知っている、と仮定する。各ノードは、各１ホップサブツリーにおける衝突関係を見つけるように、潜在的な衝突ノードを検出する。ステップ４０１において、各ノードは、該ノードの属する１ホップサブツリーをその隣接ノードに知らせるように、１ホップブロードキャストする。図５は、該検出要求パケット（ブロードキャストデータパケットとも称される）の一例を示す図である。図５に示すように、該検出要求パケットは、種類（Ｔｙｐｅ）、送信元アドレス（Ｓｏｕｒｃｅ  Ａｄｄｒ）、宛先アドレス（Ｄｅｓｔｉｎａｔｉｏｎ  Ａｄｄｒ）、及びルートＩＤ（Ｒｏｏｔ  ＩＤ）を主に含み、ここで、ルートＩＤは該送信元アドレスの属する１ホップサブツリーのルートを指す。なお、本実施例はここに例示されるものに限定されず、該検出要求パケットは、該ノードの属する１ホップサブツリーを表すことさえできれば、他の内容を含み、他のフォーマットを有してもよい。
【００２４】
本実施例では、該検出要求パケットを受信したノードとして、本実施例の方法は以下のステップをさらに含む。
【００２５】
ステップ４０２：該ノードが、他のノードから送信された、他のノードが属するサブツリーのサブツリー情報を含む検出要求パケットに基づいて、該他のノードと該ノードとが同一のサブツリー内に位置するか否かを決定する。
【００２６】
ステップ４０３：該ノードが、該他のノードと該ノードとが同一のサブツリー内に位置しない場合、該他のノードが属するサブツリーのサブツリー情報をローカルの衝突テーブルに記憶し、該ノードの親ノードにローカルの衝突テーブルを送信する。
【００２７】
本実施例では、ノードが送信側からの検出要求パケットを受信した場合は、該ノードは、自分自身と該送信側のノードとが同一の１ホップサブツリーに属するか否かを判断する。同一の１ホップサブツリーに属しない、即ちこの２つのノードがデータを並行的に送信できない場合は、受信側のノードは、異なる１ホップサブツリーの情報（例えば、該１ホップサブツリーのルートノードのＩＤ）を衝突配列に記憶し、その親ノードにアップロードする。本実施例は、衝突配列が衝突テーブルと称される。例えば、ノードＢがノードＩの情報を受信でき、ノードＢとノードＩとが異なる１ホップサブツリーに属する場合は、ノードＢの衝突配列は図６に示されている。ここで、Ｌは衝突ルートノードであり、即ちノードＩの１ホップサブツリーはノードＬをルートとし、ＬはノードＩの１ホップサブツリーのルートノードである。
【００２８】
本実施例では、該衝突テーブルパケットを受信するノード、即ち衝突テーブルパケットを送信するノードの親ノードとして、本実施例の方法は以下のステップをさらに含む。
【００２９】
ステップ４０４：該ノードが、該ノードの全ての１ホップ子ノードからの衝突テーブルパケットを受信する。
【００３０】
ステップ４０５：該ノードが、受信された衝突テーブルパケットに基づいてローカルの衝突テーブルを更新し、該ノードの親ノードに更新されたローカルの衝突テーブルを送信する。
【００３１】
本実施例では、ネットワークにおけるリーフノードは、子ノードを有しないため、ステップ４０４〜ステップ４０５を実行する必要がなく、ステップ４０１〜ステップ４０３のみを実行すればよい。リーフノード以外のノードは、ステップ４０４〜ステップ４０５においてその衝突配列を更新し、更新された衝突配列をその親ノードにアップロードする。
【００３２】
ステップ４０４では、ローカルの衝突テーブルを完全に更新するため、該ノードは、一定時間待機して、全てのその１ホップ子ノードからの衝突テーブルパケットを受信して、受信された衝突テーブルパケットに基づいてローカルの衝突テーブルを更新してもよい。
【００３３】
図７は、衝突配列パケット（衝突テーブルパケット）のフォーマットを示す図である。図７に示すように、該衝突テーブルパケットは、種類（Ｔｙｐｅ）、送信元アドレス（Ｓｏｕｒｃｅ  Ａｄｄｒ）、宛先アドレス（Ｄｅｓｔｉｎａｔｉｏｎ  Ａｄｄｒ）、及び少なくとも１つのルートＩＤ（Ｒｏｏｔ  ＩＤ）を主に含む。ここで、ルートＩＤは、該ノードの衝突ノードの属するサブツリーのルートノードのＩＤであり、該少なくとも１つのルートＩＤは、上記の衝突テーブル（衝突配列）である。なお、本実施例の衝突テーブルパケットは図７に示される衝突テーブルパケットのフォーマット及びそれに含まれる内容に限定されず、該衝突テーブルパケットは、該ノードの属する１ホップサブツリーと衝突している１ホップサブツリーを表すことさえできれば、他の内容を含み、他のフォーマットを有してもよい。
【００３４】
ステップ４０５では、該ノードは、受信された各衝突テーブルパケットにおける各サブツリー情報（即ち上記のルートＩＤ）を走査することでローカルの衝突テーブルを更新してもよい。ローカルの衝突テーブルに該サブツリー情報が含まれている場合、該サブツリー情報に対して処理を行わず、ローカルの衝突テーブルに該サブツリー情報が含まれていない場合、該サブツリー情報をローカルの衝突テーブルに追加する。これによって、ローカルの衝突テーブルを更新できる。
【００３５】
本実施例では、上記アップロードのプロセスは、リーフノードからシンクノードまで段階ごとに行われる。ノードが子ノードからの衝突配列データパケットを受信した場合は、その処理プロセスは図８に示されている。
【００３６】
図８に示すように、該プロセスは以下のステップを含む。
【００３７】
ステップ８０１：１つの衝突配列パケットを受信し、ｉを１に設定する。
【００３８】
ステップ８０２：受信されたパケットにおけるｉ番目のルートＩＤ（Ｒｏｏｔ  ＩＤ）を走査する。
【００３９】
ステップ８０３：ｉがｎよりも大きいか否かを判断し、ＹＥＳの場合は、処理を終了し、ＮＯの場合は、ステップ８０４を実行する。ｎは、受信された衝突配列パケットに含まれるルートＩＤの数である。
【００４０】
ステップ８０４：ローカルの衝突配列に該ルートＩＤが存在するか否かを判断し、ＹＥＳの場合は、該ルートＩＤに対して処理を行わず、次のルートＩＤを走査し続け、ＮＯの場合は、ステップ８０５を実行する。
【００４１】
ステップ８０５：該ルートＩＤをローカルの衝突配列に追加し、次のルートＩＤを走査し続ける。
【００４２】
図９に示すように、ノードが全てのその１ホップ子ノードからの全ての衝突配列データパケットを受信した場合は、該ノードの衝突配列の更新を終了し、更新された衝突配列をその親ノードにアップロードする。
【００４３】
図９に示すように、このプロセスは以下のステップを含む。
【００４４】
ステップ９０１：子ノードからのパケットを待つ（ｊを０に設定する）。
【００４５】
ステップ９０２：ｊ番目のパケットを受信し、ローカルの衝突配列を更新する。
【００４６】
ステップ９０３：ｊがｎに等しいか否かを判断し、ＹＥＳの場合は、ステップ９０４を実行し、ＮＯの場合は、ステップ９０１に戻る。ｎは、１ホップ子ノードの数である。
【００４７】
ステップ９０４：親ノードにローカルの衝突配列をアップロードする。
【００４８】
最後に、シンクノードは、最終的に更新された衝突配列を取得する。このため、シンクノードは、該最終的に更新された衝突配列に基づいて全ての１ホップサブツリーをグループに分ける。ここで、シンクノードは、任意の２つの１ホップサブツリーが衝突しているか否かを判別し（２つの１ホップサブツリーが衝突している場合は、該２つの１ホップサブツリーにおける２つのノードは、同一のスロットを予約すると、衝突する可能性がある）、それに基づいてグループ分けを行うことで、同一ラウンドの異なるグループの１ホップサブツリーが衝突しないことを確保できる。具体的なグループ分け方法は、以下の実施例で説明する。
【００４９】
この実施例では、シンクノードは、全ての１ホップサブツリーに対してグループ分けを行った後で、下に向けてスロット割り当て情報を段階ごとに送信する。該スロット割り当て情報は、各ノードの属するグループ、及び各ノードが予約可能なスロットリソースの範囲を含む。これによって、各ノードは、受信された該スロット割り当て情報に基づいて、それぞれのスロットリソース範囲内でスロット割り当てを行うことができる。
【００５０】
本実施例では、該スロット割り当て情報を受信するノードとして、本実施例の方法は以下のステップをさらに含む。
【００５１】
ステップ４０６：該ノードが、該ノードの親ノードから送信された、該ノードが属するグループの関連情報及び予約可能なスロットリソースの範囲を含むスロット割り当て情報を受信する。
【００５２】
ステップ４０７：該ノードが、該ノードの属するグループに基づいて、該グループに対応するスロットリソースにおいてスロットを割り当てる。
【００５３】
本実施例では、シンクノードは、各１ホップサブツリーにおける衝突関係（衝突関係は、２つの異なる１ホップサブツリーにおける２つのノードが同一のスロットでデータを送信する場合に衝突しているか否かを表す）を確立し、該衝突関係に基づいて全ての１ホップサブツリーからいくつかの１ホップサブツリーを１つのグループとして選択することで、いくつかのグループを（空間的に）形成でき、このプロセスは、残りの１ホップサブツリーがなくなるまで、いくつかのラウンドで（時間的に）継続する。１つのラウンドの異なるグループでは、他のグループによる影響を考慮することなく、各グループにおいてスロットの割り当てを行うことができる。本実施例の方法によれば、２つの異なるグループにおける同一のスロットを予約した２つのノードによる衝突は極めて小さい。よって、ネットワーク全体のスロット割り当てがいくつかのラウンドのいくつかのグループにおける独立のスロット割り当てに変更されたので、従来技術に記載された問題が解決された。
【００５４】
本実施例では、ステップ４０１〜ステップ４０７の順序でネットワークにおけるノードがスロット割り当てのプロセスにおいて実行されたステップを表示しているが、本発明の実施例に係る方法はこの順序に限定されず、具体的に実施する際に、補助的なステップを追加してもよいし、ステップを減らしてもよいし、必要に応じてステップを実行するための前後順序を調整してもよい。本発明の実施例の思想から逸脱することさえなければ、本発明の実施例の保護範囲内のものに属する。例えば、ある実施例では、該ノードは、他の検出要求パケットを受信してから、自分の検出要求パケットを送信する、即ちステップ４０２〜ステップ４０３を実行してからステップ４０１を実行してもよいし、同時に実行してもよい。また、別の例として、ネットワークにおけるリーフノードは、子ノードを有しないため、ステップ４０４〜ステップ４０５を実行する必要がない。
【００５５】
本実施例の方法によれば、いくつかのラウンドにおいて、大きな無線センサネットワークにおけるスロット割り当てを行うことができる。１つのラウンドで、該ネットワークの一部のみのスロット割り当てを行う。１つのラウンドで、いくつかのグループにさらに分けてもよく、これらのグループにおけるスロット割り当ては独立したものであってもよい。これによって、ノード用の記憶コストを低減でき（ＧＴＳテーブルのサイズが小さくなった）、１つのグループにおけるスロット割り当てを簡単にすることができ（１つのグループにおけるスロット割り当ては独立したものであり、ノードの数は大きくない）、ネットワークを容易に保守できる。
【００５６】
＜実施例２＞
本発明の実施例は、無線ネットワーク、例えばマルチホップセンサネットワークにおけるシンクノード（ｓｉｎｋ）に用いられる、パーティションに基づくスロット割り当て方法を提供する。図１０は、該方法のフローチャートであり、図１０に示すように、該方法は以下のステップを含む。
【００５７】
ステップ１００１：該シンクノードが、受信された、該シンクノードの全ての１ホップ子ノードからの衝突テーブルパケットに基づいて、サブツリー間の衝突関係を決定する。
【００５８】
ステップ１００２：該シンクノードが、各ノードが該ノードの属するグループに対応するスロットリソースにおいてスロットを割り当てるように、該衝突関係に基づいて、全てのサブツリーをサブツリーごとに、同一のラウンド又は異なるラウンドに位置する複数のグループに分ける。
【００５９】
本実施例では、上述したように、シンクノードは、最終的に更新された衝突配列に基づいて１ホップサブツリーに対してグループ分けを行ってもよい。また、シンクノードは、任意の２つの１ホップサブツリーが衝突しているか否かを判別してもよい（２つの１ホップサブツリーが衝突している場合は、該２つの１ホップサブツリーにおける２つのノードは、同一のスロットを予約すると、衝突する可能性がある）。
【００６０】
ステップ１００１では、シンクノードは、まず、該最終的に更新された衝突配列に基づいて衝突関係行列を確立する。表１は、衝突関係行列の一例を示す図であるが、本実施例はこれに限定されない。表１に示すように、該衝突関係行列により、ネットワークにおいてどの１ホップサブツリーが衝突しているか、どの１ホップサブツリーが衝突していないかを決定できる。
【表１】
2015089121.tif 000003
【００６１】
ここで、該行列におけるパラメータの意味は次の通りである。
【００６２】
Ｓｉ：ｉ番目の１ホップサブツリーのルートＩＤであり、該１ホップサブツリーを表示できる。
【００６３】
０：該２つの１ホップサブツリーが衝突していない（同一のラウンドにおいて、異なるグループに位置できる）。
【００６４】
１：該２つの１ホップサブツリーが衝突している（同一のラウンドにおいて、異なるグループに位置できない）。
【００６５】
また、１ホップサブツリーＳｉのノード数は、ｎｉで表示される。
【００６６】
ステップ１００２では、シンクノードは、同一ラウンドの異なるグループの１ホップサブツリーが衝突しないように、上記の衝突関係に基づいて、全ての１ホップサブツリーに対してグループ分けを行ってもよい。同一ラウンドの同一グループの１ホップサブツリーが衝突しているかについて、本実施例は限定されない。好ましくは、より均一的なスロット割り当てを図るため、同一のラウンドの異なるグループのノード数は大体同じである。好ましくは、同一のラウンドにおける各グループが占有可能なスロットリソースの範囲は同一である。好ましくは、基本的に衝突しないスロット割り当てを図るため、異なるラウンドにおける各グループが占有可能なスロットリソースの範囲は重ならない（not intersect）。
【００６７】
ステップ１００２の一例では、シンクノードが全ての１ホップサブツリーに対してグループ分けを行う方法は、図１１に示される方法により行われ、図１１に示すように、該方法は以下のステップを含む。
【００６８】
ステップ１１０１：現在のラウンドを決定する。
【００６９】
ステップ１１０２：所定のポリシーに従って、選択可能なサブツリーから第１の所定数のサブツリーを現在のラウンドの１番目のグループとして選択する。
【００７０】
ステップ１１０３：残りのサブツリーに、第１の条件を満たす少なくとも１つのサブツリーが存在しているか否かを判断し、ある場合は、ステップ１１０４を実行し、ない場合は、ステップ１１０５を実行する。該第１の条件は、該少なくとも１つのサブツリーが現在のラウンドの他の全てのグループにおけるサブツリーと干渉せず、且つ該少なくとも１つのサブツリーのノードの数の和と現在のラウンドの他のいずれかのグループにおけるノードの数の和との差が第１の閾値未満であることである。
【００７１】
ステップ１１０４：残りのサブツリーから、現在のラウンドの次のグループのサブツリーを選択し、ステップ１１０３に戻る。
【００７２】
ステップ１１０５：選択されていないサブツリーがあるか否かを判断し、ある場合は、次のラウンドに進み、次のラウンドのグループ分けを実行し続け、ない場合は、処理を終了する。次のラウンドのグループ分けの方法は、現在のラウンドのグループ分けの方法と同じである。
【００７３】
ステップ１１０４では、該シンクノードは、該現在のラウンドの他の全てのグループにおけるサブツリーと干渉しないサブツリーから、第２の所定数のサブツリーを現在のラウンドの次のグループとして選択してもよい。該次のグループにおけるノードの数の和と該１番目のグループにおけるノードの数の和との差は、第１の閾値未満である。
【００７４】
本実施例の一例では、該シンクノードは、選択可能なサブツリーからノード数の最も大きいサブツリー（即ちノードの最も多いサブツリー）を現在ラウンドの１番目のグループとして選択し、残りのサブツリーから、現在のラウンドの１番目のグループにおけるサブツリーと干渉しない少なくとも１つのサブツリーを、現在のラウンドの２番目のグループとして選択してもよい。２番目のグループにおけるノードの数の和と１番目のグループにおけるノードの数の和との差は、第１の閾値未満である、即ちノード数はほぼ同じである。まだ選択されていないサブツリーがある場合は、次のラウンドに進み、上記の方法によりグループ分けをし続ける。即ち、この例では、各ラウンドは多くとも２つのグループを有し、１番目のグループは１つのサブツリーのみを有し、１番目のグループのサブツリーは全ての選択可能なサブツリーのうちノード数が最大のものである。
【００７５】
本実施例のもう１つの例では、各ラウンドの１番目のグループにおけるサブツリーは、ノード数が最も多いサブツリーに限定されず、１つのみのサブツリーにも限定されない。
【００７６】
本実施例のもう１つの例では、各ラウンドは、２つのグループに分けることに限定されず、複数のグループを有してもよいが、各グループ間は干渉しない。
【００７７】
以下は、１つのラウンドが２つのグループのみに分けることを例として、本実施例の方法を説明する。図１２は該方法のフローチャートであり、図１２に示すように、該方法は以下のステップを含む。
【００７８】
ステップ１２０１：最も大きいノード数（ｎＸ）を有する１ホップサブツリー（ＳＸ）をグループ１の唯一のメンバーとして選択する。
【００７９】
ステップ１２０２：残りの１ホップサブツリーから他の１ホップサブツリーをグループ２のメンバーとして選択する。選択された１ホップサブツリー（１ホップサブツリーが任意の数存在する場合）は、次の２つの条件を満たす。
【００８０】
１）ＳＸと干渉しない（衝突関係行列における０で表示される）
２）選択された１ホップサブツリーにおけるノードの数の和はｎＸに近い（２つのグループのバランスを維持する）
ステップ１２０３：上記の２つのステップの後、１つのラウンドにおけるグループ分けが完成した。次のラウンドのグループ分けを開始し、残りの１ホップサブツリーがなくなるまで、残りの１ホップサブツリーにおいてステップ１２０１及び１２０２を繰り返す。
【００８１】
本実施例のグループ分けの結果は図１３〜図１５に示されている。図１３は、無線センサネットワークの一例を示す図である。該無線センサネットワークは５つの１ホップサブツリーを有し、ノードＡ１、Ｂ１、Ｃ１、Ｄ１及びＥ１それぞれをルートとし、１ホップサブツリーＡ１、１ホップサブツリーＢ１、１ホップサブツリーＣ１、１ホップサブツリーＤ１及び１ホップサブツリーＥ１とも称される。図１４は、図１３に示される無線センサネットワークにおける各１ホップサブツリーの衝突関係配列を示す図である。この例では、図１４に示すように、１ホップサブツリーＡ１と１ホップサブツリーＢ１、Ｄ１、Ｅ１とは衝突し、１ホップサブツリーＢ１と１ホップサブツリーＡ１、Ｄ１とは衝突し、１ホップサブツリーＣ１と１ホップサブツリーＤ１、Ｅ１とは衝突し、１ホップサブツリーＤ１と１ホップサブツリーＢ１、Ｃ１とは衝突し、１ホップサブツリーＥ１と１ホップサブツリーＡ１、Ｃ１とは衝突している。図１５は、グループ分けの結果を示す図である。図１５に示すように、第１ラウンド（ｒｏｕｎｄ  １）は２つのグループを有し、第１グループ（ｇｒｏｕｐ  １）は１ホップサブツリーＣ１を含み、第２グループ（ｇｒｏｕｐ  ２）は１ホップサブツリーＡ１及びＢ１を含み、第２ラウンド（ｒｏｕｎｄ  ２）は２つのグループを有し、第１グループ（ｇｒｏｕｐ  １）は１ホップサブツリーＥ１を含み、第２グループ（ｇｒｏｕｐ  ２）は１ホップサブツリーＤ１を含み、他のラウンドも類似する。
【００８２】
図１２に示されるものは単なる一例であり、上述したように、本実施例はこれに限定されず、具体的に実施する際に、下記のグループ分け方法も可能である。１）１つのラウンドでは３つ以上のグループに分け、任意の２つのグループが衝突しない（１つのグループにおける任意の１つの１ホップサブツリーとその他の任意のグループにおける任意の１つの１ホップサブツリーとが衝突しない）。２）１つのグループには２以上の１ホップサブツリーがあり、各グループにおけるノードの数はほぼ同じである。３）１つのグループにおけるノードの数は選択可能であり、ステップ１２０１のように、最大のノード数を有する１ホップサブツリーを選択することは必須ではない。
【００８３】
本実施例では、ネットワークにおける１ホップサブツリーのグループ分けを完成した後で、該シンクノードは、各サブツリーにおけるノードがそれぞれのグループにおいてスロットを割り当てるように、各１ホップサブツリーのルートノード（即ち該シンクノードの子ノード）に、各サブツリーのルートノードの属するラウンド、属するグループの情報及び利用可能なスロットリソースの範囲の情報をそれぞれ送信してもよい。ここで、各ラウンドの各グループの利用可能なスロットリソースの範囲は、所定のポリシーに基づいてシンクノードにより割り当てられるが、本実施例はこれに限定されない。
【００８４】
表２は、シンクノードにより割り当てられた１ホップサブツリーのＧＴＳ（Ｇｕａｒａｎｔｅｅｄ  Ｔｉｍｅ  Ｓｌｏｔ：保証スロット）テーブルの一例である。なお、表２は単なる一例であり、本実施例はこれに限定されない。
【表２】
2015089121.tif 000004
【００８５】
本実施例では、ネットワークにおける１ホップサブツリーのルートノード（即ちシンクノードの子ノード）は、上記の情報を受信した後で、その属するサブツリーにおける各ノードが受信された上記の情報に基づいてグループにおいてスロット割り当てを行うように、該情報を下方へ段階的に送信する。
【００８６】
本実施例では、シンクノードにおいて衝突することを回避するため、該シンクノードは、各ノードがグループ内でスロット割り当てを行うように、各サブツリーのルートノード（即ちシンクノードの子ノード）に対して、異なるスロットを割り当てる必要がある。図３に示されるネットワークのトポロジー構成を例として、グループにおける全ての１ホップサブツリーの各ルートノード（例えば、図３のノードＨ、Ｌ、Ｐ）に対して、異なるスロットを割り当てる必要がある。
【００８７】
図１６は、表２に示されるＧＴＳ（保証スロット）テーブルに基づく、１ホップサブツリーのルートノードのために割り当てられたスロットが衝突しているかについてのシンクノードによるチェックのプロセスを示す図である。図１６に示すように、該チェックのプロセスは以下のステップを含む。
【００８８】
ステップ１６０１：１ホップサブツリーのルートノードにスロットを割り当てる。
【００８９】
ステップ１６０２：シンクノードは、上記の割り当てられたスロットをチェックする。
【００９０】
ステップ１６０３：割り当てられたスロットとＧＴＳテーブルとが衝突しているかを判断し、ＹＥＳの場合は、ステップ１６０１に戻り、１ホップサブツリーにスロットを再割り当て、ＮＯの場合は、ステップ１６０４を実行する。
【００９１】
ステップ１６０４：ルートノードＩＤ及び割り当てられたスロットをＧＴＳテーブルに追加する。
【００９２】
本実施例では、同一グループ内の異なるサブツリーにおけるノードに用いられる具体的なスロット割り当て方法は同じであってもよく、１つのグループ内では任意の従来のスロット割り当て方法を用いてもよい。本実施例では、異なるグループ内の異なるサブツリーにおけるノードに用いられる具体的なスロット割り当て方法は同じであってもよいし、異なってもよい。また、１つのラウンドの各グループでは、スロット割り当て方法に用いられるスロット数は類似したほうがよい。
【００９３】
図１７は、本実施例の方法によるスロット割り当ての一例を示す図である。図１７に示すように、この例では、ネットワークにおける全ての１ホップサブツリーは３つのラウンドに分けられ、各ラウンドはいくつかのグループを有し、各グループは１つ又はより多くの１ホップサブツリーを有してもよい。
【００９４】
本実施例の方法によれば、いくつかのラウンドにおいて、大きな無線センサネットワークにおけるスロット割り当てを行うことができる。１つのラウンドで、該ネットワークの一部のみのスロット割り当てを行う。１つのラウンドで、いくつかのグループにさらに分けてもよく、これらのグループにおけるスロット割り当ては独立したものであってもよい。これによって、ノード用の記憶コストを低減でき（ＧＴＳテーブルのサイズが小さくなった）、１つのグループにおけるスロット割り当てを簡単にすることができ（１つのグループにおけるスロット割り当ては独立したものであり、ノードの数は大きくない）、ネットワークを容易に保守できる。
【００９５】
本発明の実施例はノードをさらに提供し、下記の実施例３に述べるように、該ノードの問題解決の原理は実施例１と類似するため、その具体的な実施は実施例１の方法の実施を参照してもよく、重複する内容の説明は省略される。
【００９６】
＜実施例３＞
本発明の実施例は、無線ネットワーク、例えばマルチホップセンサネットワークにおけるノードを提供する。図１８は、該ノードの構成を示す図である。図１８に示すように、該ノードは、送信部１８１、決定部１８２、及び処理部１８３を含む。
【００９７】
送信部１８１は、該ノードが属するサブツリーのサブツリー情報を含む検出要求パケットをブロードキャスト送信する。該サブツリーは、シンクノードから１ホップ離れたノードをルートノードとする。
【００９８】
決定部１８２は、他のノードから送信された、他のノードが属するサブツリーのサブツリー情報を含む検出要求パケットに基づいて、該他のノードと該ノードとが同一のサブツリー内に位置するか否かを決定する。
【００９９】
処理部１８３は、該他のノードと該ノードとが同一のサブツリー内に位置しない場合、該他のノードが属するサブツリーのサブツリー情報をローカルの衝突テーブルに記憶し、該ノードの親ノードにローカルの衝突テーブルを送信する。
【０１００】
本実施例の一例では、該ノードは、第１の受信部１８４及び更新部１８５をさらに含む。
【０１０１】
第１の受信部１８４は、該ノードの全ての１ホップ子ノードからの衝突テーブルパケットを受信する。
【０１０２】
更新部１８５は、受信された衝突テーブルパケットに基づいてローカルの衝突テーブルを更新し、該ノードの親ノードに更新されたローカルの衝突テーブルを送信する。
【０１０３】
この例では、更新部１８５は、走査モジュール１８５１及び処理モジュール１８５２を含んでもよい。
【０１０４】
走査モジュール１８５１は、受信された各衝突テーブルパケットにおける各サブツリー情報を走査する。
【０１０５】
処理モジュール１８５２は、該ローカルの衝突テーブルに該サブツリー情報が含まれている場合、該サブツリー情報に対して処理を行わず、該ローカルの衝突テーブルに該サブツリー情報が含まれていない場合、該サブツリー情報を該ローカルの衝突テーブルに追加する。
【０１０６】
本実施例の他の例では、該ノードは第２の受信部１８６及びスロット割り当て部１８７をさらに含む。
【０１０７】
第２の受信部１８６は、該ノードの親ノードから送信された、該ノードが属するグループの関連情報及び予約可能なスロットリソースの範囲を含むスロット割り当て情報を受信する。
【０１０８】
スロット割り当て部１８７は、該ノードが属するグループに基づいて、該グループに対応するスロットリソースにおいてスロットを割り当てる。
【０１０９】
本実施例のノードによれば、自分の属するグループのスロットリソースの範囲内でリソースを割り当てることで、ノード用の記憶コストを低減でき（ＧＴＳテーブルのサイズが小さくなった）、１つのグループにおけるスロット割り当てを簡単にすることができ（１つのグループにおけるスロット割り当ては独立したものであり、ノードの数は大きくない）、ネットワークを容易に保守できる。
【０１１０】
本発明の実施例はノードをさらに提供し、下記の実施例４に述べるように、該ノードの問題解決の原理は実施例２と類似するため、その具体的な実施は実施例２の方法の実施を参照してもよく、重複する内容の説明は省略される。
【０１１１】
＜実施例４＞
本発明の実施例は、無線ネットワーク、例えばマルチホップセンサネットワークにおけるノードを提供し、本実施例はこれに限定されない。図１９は、該ノードの構成を示す図であり、図１９に示すように、該ノードは、決定部１９１及び処理部１９２を含む。
【０１１２】
決定部１９１は、受信された、該シンクノードの全ての１ホップ子ノードからの衝突テーブルパケットに基づいて、サブツリー間の衝突関係を決定する。
【０１１３】
処理部１９２は、各ノードが該ノードの属するグループに対応するスロットリソースにおいてスロットを割り当てるように、該衝突関係に基づいて、全てのサブツリーをサブツリーごとに、同一のラウンド又は異なるラウンドに位置する複数のグループに分ける。
【０１１４】
本実施例では、同一のラウンドにおける各グループが占有可能なスロットリソースの範囲は同一であり、同一のラウンドにおける各グループのノードは互いに干渉せず、異なるラウンドにおける各グループが占有可能なスロットリソースの範囲は重ならない（not intersect）。
【０１１５】
本実施例の一例では、処理部１９２は、決定モジュール１９２１、第１の選択モジュール１９２２、第１の判断モジュール１９２３、第２の選択モジュール１９２４、第２の判断モジュール１９２５、及び処理モジュール１９２６を含んでもよい。
【０１１６】
決定モジュール１９２１は、現在のラウンドを決定する。
【０１１７】
第１の選択モジュール１９２２は、所定のポリシーに従って、選択可能なサブツリーから第１の所定数のサブツリーを現在のラウンドの１番目のグループとして選択する。
【０１１８】
第１の判断モジュール１９２３は、残りのサブツリーに、現在のラウンドの他の全てのグループにおけるサブツリーと干渉せず、且つノードの数の和と現在のラウンドの他のいずれかのグループにおけるノードの数の和との差が第１の閾値未満である少なくとも１つのサブツリーが存在しているか否かを判断する。
【０１１９】
第２の選択モジュール１９２４は、存在していると第１の判断モジュール１９２３により判断された場合、残りのサブツリーから現在のラウンドの次のグループのサブツリーを選択する。
【０１２０】
第２の判断モジュール１９２５は、存在していないと第１の判断モジュール１９２３により判断された場合、選択されていないサブツリーがあるか否かを判断する。
【０１２１】
処理モジュール１９２６は、あると第２の判断モジュール１９２５により判断された場合、次のラウンドに進み、ないと第２の判断モジュール１９２５により判断された場合、処理を終了する。
【０１２２】
この例では、第２の選択モジュール１９２４は、現在のラウンドの他の全てのグループにおけるサブツリーと干渉しないサブツリーから、第２の所定数のサブツリーを現在のラウンドの次のグループとして選択する。該次のグループにおけるノードの数の和と該１番目のグループにおけるノードの数の和との差は第１の閾値未満である。
【０１２３】
本実施例の他の例では、シンクノードは、送信部１９３をさらに含んでもよい。
【０１２４】
送信部１９３は、各サブツリーにおけるノードがそれぞれのグループにおいてスロットを割り当てるように、各サブツリーのルートノードに、各サブツリーのルートノードの属するグループの情報及び利用可能なスロットリソースの範囲の情報をそれぞれ送信する。
【０１２５】
本実施例の他の例では、シンクノードは、割り当て部１９４をさらに含んでもよい。
【０１２６】
割り当て部１９４は、該各サブツリーのルートノードに対して、異なるスロットを割り当てる。
【０１２７】
送信部１９３は、各サブツリーのルートノードに対して割り当て部１９４により割り当てられたスロットを、各サブツリーのルートノードに送信する。
【０１２８】
本実施例のシンクノードによれば、全ての１ホップサブツリーに対してグループ分けを行い、各グループが同一又は異なるラウンドに位置するため、ネットワークにおける各ノードは自分の属するグループのスロットリソースの範囲内でリソースを割り当てることで、ノード用の記憶コストを低減でき（ＧＴＳテーブルのサイズが小さくなった）、１つのグループにおけるスロット割り当てを簡単にすることができ（１つのグループにおけるスロット割り当ては独立したものであり、ノードの数は大きくない）、ネットワークを容易に保守できる。
【０１２９】
本発明の実施例は、少なくとも１つの実施例３に記載のノードと、実施例４に記載のシンクノードと、を含むネットワークをさらに提供する。
【０１３０】
本発明の実施例は、少なくとも１つの実施例２に記載のノード、又は少なくとも１つの実施例２に記載のノードの任意の組み合わせを含む無線ネットワーク、例えばマルチホップセンサネットワークをさらに提供する。
【０１３１】
本発明の以上の装置及び方法は、ハードウェアにより実現されてもよく、ハードウェアとソフトウェアを結合して実現されてもよい。本発明はコンピュータが読み取り可能なプログラムに関し、該プログラムはロジック部により実行される時に、該ロジック部に上述した装置又は構成要件を実現させる、或いは該ロジック部に上述した各種の方法又はステップを実現させることができる。本発明は上記のプログラムを記憶するための記憶媒体、例えばハードディスク、ディスク、光ディスク、ＤＶＤ、フラッシュメモリ等に関する。
【０１３２】
以上、具体的な実施形態を参照しながら本発明を説明しているが、上記の説明は、例示的なものに過ぎず、本発明の保護の範囲を限定するものではない。本発明の趣旨及び原理を離脱しない限り、本発明に対して各種の変形及び修正を行ってもよく、これらの変形及び修正も本発明の範囲に属する。
【０１３３】
また、上述の各実施例を含む実施形態に関し、更に以下の付記を開示する。
【０１３４】
（付記１）
マルチホップセンサネットワークにおけるシンクノード以外のノードに用いられる、パーティションに基づくスロット割り当て方法であって、
前記ノードが、前記ノードが属するサブツリーのサブツリー情報を含む検出要求パケットをブロードキャスト送信するステップであって、前記サブツリーがシンクノードから１ホップ離れたノードをルートノードとする、ステップと、
前記ノードが、他のノードから送信された、他のノードが属するサブツリーのサブツリー情報を含む検出要求パケットに基づいて、前記他のノードと前記ノードとが同一のサブツリー内に位置するか否かを決定するステップと、
前記ノードが、前記他のノードと前記ノードとが同一のサブツリー内に位置しない場合、前記他のノードが属するサブツリーのサブツリー情報をローカルの衝突テーブルに記憶し、前記ノードの親ノードにローカルの衝突テーブルを送信するステップと、を含むスロット割り当て方法。
【０１３５】
（付記２）
前記ノードが、前記ノードの全ての１ホップ子ノードからの衝突テーブルパケットを受信するステップと、
前記ノードが、受信された衝突テーブルパケットに基づいてローカルの衝突テーブルを更新し、前記ノードの親ノードに更新されたローカルの衝突テーブルを送信するステップと、をさらに含む付記１に記載のスロット割り当て方法。
【０１３６】
（付記３）
前記ノードが、受信された衝突テーブルパケットに基づいてローカルの衝突テーブルを更新するステップは、
受信された各衝突テーブルパケットにおける各サブツリー情報を走査するステップと、
前記ローカルの衝突テーブルに前記サブツリー情報が含まれている場合、前記サブツリー情報に対して処理を行わず、前記ローカルの衝突テーブルに前記サブツリー情報が含まれていない場合、前記サブツリー情報を前記ローカルの衝突テーブルに追加するステップと、を含む付記２に記載のスロット割り当て方法。
【０１３７】
（付記４）
前記ノードが、前記ノードの親ノードから送信された、前記ノードが属するグループの関連情報及び予約可能なスロットリソースの範囲を含むスロット割り当て情報を受信するステップと、
前記ノードが、前記ノードが属するグループに基づいて、該グループに対応するスロットリソースにおいてスロットを割り当てるステップと、をさらに含む付記１に記載のスロット割り当て方法。
【０１３８】
（付記５）
マルチホップセンサネットワークにおけるシンクノードに用いられる、パーティションに基づくスロット割り当て方法であって、
前記シンクノードが、受信された、前記シンクノードの全ての１ホップ子ノードからの衝突テーブルパケットに基づいて、サブツリー間の衝突関係を決定するステップと、
前記シンクノードが、各ノードが該ノードの属するグループに対応するスロットリソースにおいてスロットを割り当てるように、前記衝突関係に基づいて、全てのサブツリーをサブツリーごとに、同一のラウンド又は異なるラウンドに位置する複数のグループに分けるステップと、を含むスロット割り当て方法。
【０１３９】
（付記６）
同一のラウンドにおける各グループが占有可能なスロットリソースの範囲は同一であり、同一のラウンドにおける各グループのノードは互いに干渉せず、異なるラウンドにおける各グループが占有可能なスロットリソースの範囲は重ならない付記５に記載のスロット割り当て方法。
【０１４０】
（付記７）
前記全てのサブツリーを複数のグループに分けるステップは、
現在のラウンドを決定するステップと、
所定のポリシーに従って、選択可能なサブツリーから第１の所定数のサブツリーを現在のラウンドの１番目のグループとして選択するステップと、
残りのサブツリーに、現在のラウンドの他の全てのグループにおけるサブツリーと干渉せず、且つノードの数の和と現在のラウンドの他のいずれかのグループにおけるノードの数の和との差が第１の閾値未満である少なくとも１つのサブツリーが存在しているか否かを判断するステップと、
存在していると判断された場合、残りのサブツリーから現在のラウンドの次のグループのサブツリーを選択するステップと、
存在していないと判断された場合、選択されていないサブツリーがあるか否かを判断するステップと、
あると判断された場合、次のラウンドに進み、ないと判断された場合、処理を終了するステップと、を含む付記５に記載のスロット割り当て方法。
【０１４１】
（付記８）
前記現在のラウンドの次のグループのサブツリーを選択するステップにおいては、現在のラウンドの他の全てのグループにおけるサブツリーと干渉しないサブツリーから、第２の所定数のサブツリーを現在のラウンドの次のグループとして選択し、
前記次のグループにおけるノードの数の和と前記１番目のグループにおけるノードの数の和との差は第１の閾値未満である付記７に記載のスロット割り当て方法。
【０１４２】
（付記９）
前記シンクノードが、各サブツリーにおけるノードがそれぞれのグループにおいてスロットを割り当てるように、各サブツリーのルートノードに、各サブツリーのルートノードの属するグループの情報及び利用可能なスロットリソースの範囲の情報をそれぞれ送信するステップ、をさらに含む付記５に記載のスロット割り当て方法。
【０１４３】
（付記１０）
前記シンクノードが、前記各サブツリーのルートノードに対して、異なるスロットを割り当てるステップ、をさらに含む付記９に記載のスロット割り当て方法。
【０１４４】
（付記１１）
無線ネットワークにおけるノードであって、
前記ノードが属するサブツリーのサブツリー情報を含む検出要求パケットをブロードキャスト送信する送信手段であって、前記サブツリーがシンクノードから１ホップ離れたノードをルートノードとする、送信手段と、
他のノードから送信された、他のノードが属するサブツリーのサブツリー情報を含む検出要求パケットに基づいて、前記他のノードと前記ノードとが同一のサブツリー内に位置するか否かを決定する決定手段と、
前記他のノードと前記ノードとが同一のサブツリー内に位置しない場合、前記他のノードが属するサブツリーのサブツリー情報をローカルの衝突テーブルに記憶し、前記ノードの親ノードにローカルの衝突テーブルを送信する処理手段と、を含むノード。
【０１４５】
（付記１２）
前記ノードの全ての１ホップ子ノードからの衝突テーブルパケットを受信する第１の受信手段と、
受信された衝突テーブルパケットに基づいてローカルの衝突テーブルを更新し、前記ノードの親ノードに更新されたローカルの衝突テーブルを送信する更新手段と、をさらに含む付記１１に記載のノード。
【０１４６】
（付記１３）
前記更新手段は、
受信された各衝突テーブルパケットにおける各サブツリー情報を走査する走査モジュールと、
前記ローカルの衝突テーブルに前記サブツリー情報が含まれている場合、前記サブツリー情報に対して処理を行わず、前記ローカルの衝突テーブルに前記サブツリー情報が含まれていない場合、前記サブツリー情報を前記ローカルの衝突テーブルに追加する処理モジュールと、を含む付記１２に記載のノード。
【０１４７】
（付記１４）
前記ノードの親ノードから送信された、前記ノードが属するグループの関連情報及び予約可能なスロットリソースの範囲を含むスロット割り当て情報を受信する第２の受信手段と、
前記ノードが属するグループに基づいて、該グループに対応するスロットリソースにおいてスロットを割り当てるスロット割り当て手段と、をさらに含む請求項１に記載のノード。
【０１４８】
（付記１５）
無線ネットワークにおけるシンクノードであって、
受信された、前記シンクノードの全ての１ホップ子ノードからの衝突テーブルパケットに基づいて、サブツリー間の衝突関係を決定する決定手段と、
各ノードが該ノードの属するグループに対応するスロットリソースにおいてスロットを割り当てるように、前記衝突関係に基づいて、全てのサブツリーをサブツリーごとに、同一のラウンド又は異なるラウンドに位置する複数のグループに分ける処理手段と、を含むシンクノード。
【０１４９】
（付記１６）
同一のラウンドにおける各グループが占有可能なスロットリソースの範囲は同一であり、同一のラウンドにおける各グループのノードは互いに干渉せず、異なるラウンドにおける各グループが占有可能なスロットリソースの範囲は重ならない付記１５に記載のシンクノード。
【０１５０】
（付記１７）
前記処理手段は、
現在のラウンドを決定する決定モジュールと、
所定のポリシーに従って、選択可能なサブツリーから第１の所定数のサブツリーを現在のラウンドの１番目のグループとして選択する第１の選択モジュールと、
残りのサブツリーに、現在のラウンドの他の全てのグループにおけるサブツリーと干渉せず、且つノードの数の和と現在のラウンドの他のいずれかのグループにおけるノードの数の和との差が第１の閾値未満である少なくとも１つのサブツリーが存在しているか否かを判断する第１の判断モジュールと、
存在していると前記第１の判断モジュールにより判断された場合、残りのサブツリーから現在のラウンドの次のグループのサブツリーを選択する第２の選択モジュールと、
存在していないと前記第１の判断モジュールにより判断された場合、選択されていないサブツリーがあるか否かを判断する第２の判断モジュールと、
あると前記第２の判断モジュールにより判断された場合、次のラウンドに進み、ないと前記第２の判断モジュールにより判断された場合、処理を終了する処理モジュールと、を含む付記１５に記載のシンクノード。
【０１５１】
（付記１８）
前記第２の選択モジュールは、現在のラウンドの他の全てのグループにおけるサブツリーと干渉しないサブツリーから、第２の所定数のサブツリーを現在のラウンドの次のグループとして選択し、
前記次のグループにおけるノードの数の和と前記１番目のグループにおけるノードの数の和との差は第１の閾値未満である付記１７に記載のシンクノード。
【０１５２】
（付記１９）
各サブツリーにおけるノードがそれぞれのグループにおいてスロットを割り当てるように、各サブツリーのルートノードに、各サブツリーのルートノードの属するグループの情報及び利用可能なスロットリソースの範囲の情報をそれぞれ送信する送信手段、をさらに含む付記１５に記載のシンクノード。
【０１５３】
（付記２０）
前記各サブツリーのルートノードに対して、異なるスロットを割り当てる割り当て手段、をさらに含み、
前記送信手段は、各サブツリーのルートノードに対して前記割り当て手段により割り当てられたスロットを、各サブツリーのルートノードに送信する付記１９に記載のシンクノード。
【０１５４】
（付記２１）
少なくとも１つの付記１１〜１４のいずれかに記載のノードと、付記１５〜２０のいずれかに記載のシンクノードと、を含む、ネットワーク。
【図１】
2015089121.tif 000005
【図２】
2015089121.tif 000006
【図３】
2015089121.tif 000007
【図４】
2015089121.tif 000008
【図５】
2015089121.tif 000009
【図６】
2015089121.tif 000010
【図７】
2015089121.tif 000011
【図８】
2015089121.tif 000012
【図９】
2015089121.tif 000013
【図１０】
2015089121.tif 000014
【図１１】
2015089121.tif 000015
【図１２】
2015089121.tif 000016
【図１３】
2015089121.tif 000017
【図１４】
2015089121.tif 000018
【図１５】
2015089121.tif 000019
【図１６】
2015089121.tif 000020
【図１７】
2015089121.tif 000021
【図１８】
2015089121.tif 000022
【図１９】
2015089121.tif 000023