(57)【要約】  本発明は、通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための方法に関し、各ノードは通信ネットワークのネットワーク・デバイスに対応し、この方法は、第１ツリーパラメータ（Ｃm、Ｒm、Ｌm）を決定するステップと、所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、ツリーの第１セクションのノード、すなわち第１ノード（４０）の直系子孫のノード（４１、４２、４３、４４ａ、４４ｂ）にノードアドレスを割り当てるステップと、所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、特定ノード（４４ａ、４４ｂ）についての利用可能な子孫ノードの第１の数を決定するステップと、特定ノードについての第２ツリーパラメータ（Ｃm2、Ｒm2、Ｌm2）を、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて決定される特定ノードについての利用可能な子孫ノードの第２の数が利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように決定するステップと、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて、特定ノードの直系子孫のノード（４５ａ、４５ｂ、４６ａ、４６ｂ）にノードアドレスを割り当てるステップとを含む。【選択図】図２
2010510708.tif 000002
【特許請求の範囲】
【請求項１】
通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための方法であって、各ノードは前記通信ネットワークのネットワーク・デバイスに対応し、
前記通信ネットワーク・ツリー構造の第１ツリーパラメータを決定するステップと、
所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、第１ノードの直系子孫のノードにノードアドレスを割り当てるステップと、
前記所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定するステップと、
前記特定ノードについての第２ツリーパラメータを、前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて決定される前記特定ノードについての利用可能な子孫ノードの第２の数が、前記利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように、決定するステップと、
前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて、前記特定ノードの直系子孫のノードにノードアドレスを割り当てるステップと、を含むことを特徴とする方法。
【請求項２】
前記ノードが、親ノード及び親ノードの子孫である子ノードを含み、前記第１ツリーパラメータを決定する前記ステップが、親ノード当たりの子ノードの最大数、親ノード当たりの子ノードの中の親ノードの最大数、及び最大ツリー深さを定義するステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記所定の割当てアルゴリズムが、Ｃｓｋｉｐツリーアドレス割当てアルゴリズムであることを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記ノードが、エンドノード及びルータノードを含み、各エンドノードはいかなる子孫ノードも持たず、各ルータノードは他の子孫ノードを持つことができ、ノードにノードアドレスを割り当てる前記ステップが、次式
ＡRouterChild＝Ａparent＋１＋Ｃｓｋｉｐ（ｄ）・ｍ
ＡZEDChild＝Ａparent＋Ｃｓｋｉｐ（ｄ）・Ｒm＋ｎ
に基づき、ここで
【数１】
2010510708.tif 000012
であり、
Ａparentは親ノードのアドレスであり、
ＡRouterChildは割り当てられるルータノード・アドレスであり、
ＡZEDChildは割り当てられるエンドノード・アドレスであり、
ｍは連結されたルータノードの現在の数であって、ｍ∈｛０，Ｒm−１｝であり、
Ｒmは親ノード当たりのルータノードの最大数であり、
ｎは連結されたエンドノードの現在の数であって、ｎ∈｛０，Ｃm−Ｒm−１｝であり、
Ｃmは親ノード当たりの子ノードの最大数であり、
Ｌmは最大ツリー深さであり、
ｄは親ノードの実際の深さである、
ことを特徴とする請求項３に記載の方法。
【請求項５】
深さｄにおける前記特定ノードについての前記利用可能な子孫ノードの第１の数が、次式
Ｄ1（ｄ）＝Ｃｓｋｉｐ（ｄ−１）−１
に基づくことを特徴とする請求項４に記載の方法。
【請求項６】
深さｄにおける前記特定ノードについての前記利用可能な子孫ノードの第２の数が、次式
Ｄ2（ｄ）＝Ｒm2＊Ｃｓｋｉｐ（ｄ）＋Ｃm2−Ｒm2
に基づき、ここで
Ｃm2は親ノード当たりの子ノードの第２の最大数であり、
Ｒm2は親ノード当たりの子ノードの中の親ノードの第２の最大数であり、
Ｌm2は第２の最大ツリー深さである、
ことを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
前記第２ツリーパラメータを決定する前記ステップが、
前記第２ツリーパラメータのうちの少なくとも１つを決定するステップと、
欠けている任意の前記第２ツリーパラメータを、前記決定された少なくとも１つの第２ツリーパラメータ、並びに前記特定ノードについての利用可能な子孫ノードの前記第１及び第２の数に基づいて決定するステップと、を含むことを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
前記第２ツリーパラメータのうちの少なくとも１つが、ユーザによって決定及び設定されることを特徴とする請求項１に記載の方法。
【請求項９】
前記第１又は第２ツリーパラメータが、親ノードによって子ノードに、その子ノードのアドレスと共に提供されることを特徴とする請求項１に記載の方法。
【請求項１０】
子ノードに提供される前記第１又は第２ツリーパラメータが、前記子ノードにおけるツリーパラメータ設定のいずれかを上書きすることを特徴とする請求項９に記載の方法。
【請求項１１】
親ノードのＣｓｋｉｐオフセットが、親ノードによって子ノードに、その子ノードのアドレスと共に提供されることを特徴とする請求項３に記載の方法。
【請求項１２】
前記特定ノードの子孫である第２特定ノードについての利用可能な子孫ノードの第３の数を、前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて決定するステップと、
前記第２特定ノードについての第３ツリーパラメータを、前記所定の割当てアルゴリズム及び前記第３ツリーパラメータに基づいて決定される前記第２特定ノードについての利用可能な子孫ノードの第４の数が、前記利用可能な子孫ノードの第３の数と等しいか又はそれより小さくなるように決定するステップと、
前記所定の割当てアルゴリズム及び前記第３ツリーパラメータに基づいて、前記第２特定ノードの直系子孫のノードにノードアドレスを割り当てるステップと、をさらに含むことを特徴とする請求項１に記載の方法。
【請求項１３】
前記第３ツリーパラメータが、前記第１ツリーパラメータと等しいことを特徴とする請求項１２に記載の方法。
【請求項１４】
コンピュータに請求項１乃至１３のいずれか１項に記載の方法を実行させることを特徴とするコンピュータプログラム。
【請求項１５】
請求項１４に記載のコンピュータプログラムを記憶した記録担体。
【請求項１６】
通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための装置であって、各ノードは前記通信ネットワークのネットワーク・デバイスに対応し、
前記通信ネットワーク・ツリー構造の第１ツリーパラメータを決定する手段と、
所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、第１ノードの直系子孫のノードにノードアドレスを割り当てる手段と、
前記所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定する手段と、
前記特定ノードについての第２ツリーパラメータを、前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて決定される前記特定ノードについての利用可能な子孫ノードの第２の数が、前記利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように決定する手段と、
前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて、前記特定ノードの直系子孫のノードにノードアドレスを割り当てる手段と、を含むことを特徴とする装置。
【請求項１７】
通信ネットワークのネットワーク・デバイスであって、
通信ネットワーク・ツリー構造の第１ツリーパラメータを決定する手段と、
ツリーパラメータの変更が必要かどうか決定する手段と、
所定の割当てアルゴリズム及び前記第１ツリーパラメータ／Ｃｓｋｉｐオフセットに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定する手段と、
前記特定ノードについての第２ツリーパラメータを、前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて決定される前記特定ノードについての利用可能な子孫ノードの第２の数が、前記利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように、ユーザ入力に基づいて決定する手段と、
前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて、前記特定ノードの直系子孫である子ノードにノードアドレスを割り当てる手段と
前記通信ネットワーク・ツリー構造の第２ツリーパラメータを子ノードに伝達する手段と、を含むことを特徴とするネットワーク・デバイス。
【請求項１８】
前記第１ツリーパラメータを決定する前記手段が、親ノードによって使用される通信ネットワーク・ツリー構造の前記第１ツリーパラメータを決定するように構成されることを特徴とする請求項１７に記載のネットワーク・デバイス。
【請求項１９】
請求項１６又は１７に記載の装置と、
ツリー構造に配置され、各デバイスが前記ツリー構造のノードに対応する複数のルータデバイス及び端末デバイスと、を含むことを特徴とするシステム。
【請求項２０】
前記デバイスが大規模無線制御ネットワークの一部であることを特徴とする請求項１９に記載のシステム。
【請求項２１】
前記デバイスが建物内に配置され、前記ツリー構造が前記建物のトポロジーを表すことを特徴とする請求項１９に記載のシステム。
【請求項２２】
前記デバイスがＺｉｇＢｅｅデバイスであることを特徴とする請求項１９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク・ツリー構造、特に無線制御ネットワーク・ツリー構造のノードにアドレスを割り当てるための方法及び装置に関する。
【背景技術】
【０００２】
通信ネットワーク・ツリー構造のノード又はデバイスにアドレスを割り当てるために、ＩＥＥＥ８０２．１５．４によって提唱された（かつＺｉｇＢｅｅ（登録商標）によって採用された）、簡略的にはＣｓｋｉｐツリーアドレス割当てアルゴリズムと呼ばれるアルゴリズムは、ＺｉｇＢｅｅルータが、ルータ及び端末デバイスの両方の子ノードに自動的にネットワークアドレスを割り当てることを可能にする。しかしながら、Ｃｓｋｉｐツリーアドレス割当てアルゴリズム及び固有のツリールーティング・アルゴリズムは、単純なだけに機能が非常に限られており、その結果、広いが浅いツリー又は深いが狭いツリーのいずれかの、自由度の低いトポロジーがもたらされる。どちらの選択肢も、物理的制御ネットワーク・トポロジー、特に、大きい建物内の通信ネットワーク、例えば無線照明制御ネットワークのトポロジーには必ずしも最適であるとはいえない。
【０００３】
特許文献１は、アドレス空間の浪費を避けるためにＺｉｇＢｅｅネットワーク・クラスタツリー構造内の各デバイスに対して異なるネットワーク・パラメータを決定することによってアドレスを割り付けるための、ＺｉｇＢｅｅネットワーク・クラスタツリー構造のためのアドレス割当て方法を提供する。ＺｉｇＢｅｅネットワーク・デバイスは、パラメータ決定セクション、計算セクション及びコントローラを含む。パラメータ決定セクションは、少なくとも１つのネットワーク・パラメータを決定する。計算セクションは、決定されたネットワーク・パラメータに基づいて子デバイスのためのアドレスを計算し、コントローラは、そのアドレスをＺｉｇＢｅｅネットワーク・デバイスの子デバイスに割り当てる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願公開第２００５／２８１２０７号明細書
【非特許文献】
【０００５】
【非特許文献１】Ｉｎｃ．Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｅｌｅｃｔｒｉｃａｌ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ｅｎｇｉｎｅｅｒｓ、ＩＥＥＥ  Ｓｔａｎｄａｒｄ  ８０２．１５．４−２００３、Ｐａｒｔ  １５．４：Ｗｉｒｅｌｅｓｓ  Ｍｅｄｉｕｍ  Ａｃｃｅｓｓ  Ｃｏｎｔｒｏｌ（ＭＡＣ）  ａｎｄ  Ｐｈｙｓｉｃａｌ  Ｌａｙｅｒ（ＰＨＹ）  Ｓｐｅｃｉｆｉｃａｔｉｏｎｓ  ｆｏｒ  Ｌｏｗ  Ｒａｔｅ  Ｗｉｒｅｌｅｓｓ  Ｐｅｒｓｏｎａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋｓ（ＷＰＡＮｓ）、Ｎｅｗ  Ｙｏｒｋ：ＩＥＥＥ  Ｐｒｅｓｓ、２００３年
【非特許文献２】ＺｉｇＢｅｅ  ｓｐｅｃｉｆｉｃａｔｉｏｎ、ＺｉｇＢｅｅ  Ｄｏｃｕｍｅｎｔ  ０５３４７４ｒ０６（２００５年６月）、第１．０版、２００４年１２月１４日；０５３４７４ｒ０６ＺＢ＿ＴＳＣ−ＺｉｇＢｅｅ−Ｓｐｅｃｉｆｉｃａｔｉｏｎ−ｖ１［１］．０．ｐｄｆ、ｗｗｗ．ｚｉｇｂｅｅ．ｏｒｇ、ｐ．２２４，ｓｅｃ．２．７．１．４
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための改良された方法及び改良された装置を提供することである。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明は、通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための方法を提供し、各ノードは通信ネットワークのネットワーク・デバイスに対応し、この方法は、
通信ネットワーク・ツリー構造の第１ツリーパラメータを決定するステップと、
所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、第１ノードの直系子孫のノードにノードアドレスを割り当てるステップと、
所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定するステップと、
特定ノードについての第２ツリーパラメータを、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて決定される特定ノードについての利用可能な子孫ノードの第２の数が、利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように、決定するステップと、
所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて、特定ノードの直系子孫のノードにノードアドレスを割り当てるステップと、を含む。
【０００８】
上記の目的を達成するために、本発明は、さらに通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための装置を提供し、各ノードは通信ネットワークのネットワーク・デバイスに対応し、この装置は、
通信ネットワーク・ツリー構造の第１ツリーパラメータを決定する手段と、
所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、第１ノードの直系子孫のノードにノードアドレスを割り当てる手段と、
所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定する手段と、
特定ノードについての第２ツリーパラメータを、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて決定される特定ノードについての利用可能な子孫ノードの第２の数が、利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように決定する手段と、
所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて、特定ノードの直系子孫のノードにノードアドレスを割り当てる手段と、を含む。
【０００９】
上記の目的を達成するために、本発明はさらに、通信ネットワークのネットワーク・デバイスを提供し、このデバイスは、
親ノードによって使用される、通信ネットワーク・ツリー構造の第１ツリーパラメータを決定する手段と、
ツリーパラメータの変更が必要かどうか決定する手段と、
所定の割当てアルゴリズム及び第１ツリーパラメータ／Ｃｓｋｉｐオフセットに基づいて、この特定ノードについての利用可能な子孫ノードの第１の数を決定する手段と、
特定ノードについての第２ツリーパラメータを、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて決定される特定ノードについての利用可能な子孫ノードの第２の数が、利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように、ユーザ入力に基づいて決定する手段と、
所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて、特定ノードの直系子孫である子ノードにノードアドレスを割り当てる手段と
通信ネットワーク・ツリー構造の第２ツリーパラメータを子ノードに伝達する手段と、を含む。
【００１０】
本発明によれば、アドレスは、割当てを行うノードからその直接の子に対してのみ割り当てられる。利用可能な子孫ノードの数は、全ての下位要素（ｓｕｃｃｅｓｓｏｒ）を意味する。
【００１１】
本発明による特徴は、本発明を用いて、例えば大きい建物内の無線照明制御ネットワークの物理的ネットワーク・トポロジーに適合することができる非常に自由度の高いネットワーク・トポロジーを実現することができるという利点を提供するが、これは、最大深さ、並びに子及びルータ子の数を互いにトレードオフの関係にすることができるので、それらを、各深さレベルで、ツリーセクション毎に、ブランチ毎に、又は全てのルータ毎にさえ自由に定めることができるという事実に依るものである。特許文献１とは対照的に、本発明は、全体的なトポロジー最適化を目的としており、一方、特許文献１のアドレス割り当て方法は主にローカルな最適化を目的としている。
【００１２】
本発明による可能なツリー構造は、ＺｉｇＢｅｅネットワーク・クラスタツリー構造である。このツリー構造のノードは、親ノード及び子ノードを含む。「子孫（ｄｅｓｃｅｎｄｅｎｔ）」という用語は、特定のノードに対して下位にある、全ての深さレベルにおける全てのノードを指す。「子ノード」は、親ノードに対する次の深さレベルにある直系子孫又は下位要素である。「第１ノード」という用語は、開始位置又はツリー構造の根（ルート）の位置に配置されたノードを意味する。「特定ノード」は、第１ノードの子孫のツリー構造の任意のノードとすることができる。
【００１３】
「ツリーパラメータ」という用語は、ツリー構造を定義するのに適した任意のパラメータを意味する。ツリーパラメータは、親ノード当たりの子ノードの最大数を定義するパラメータ、親ノード当たりの子ノードの中のルータノードの最大数を定義するパラメータ、及び最大ツリー深さを定義するパラメータを含むことができる。
【００１４】
「利用可能な子孫ノードの数」という用語は、全ての下位ノードに対して費やすことができるアドレスのプールを意味する。
【００１５】
「所定の割当てアルゴリズム」は、任意の特定ノード対してノードアドレス及び利用可能な子孫ノードの数を計算するのに適した、任意のアルゴリズム若しくは式、又はアルゴリズム若しくは式の集合を意味する。所定の割当てアルゴリズムは、Ｃｓｋｉｐツリーアドレス割当てアルゴリズムとすることができる。
【００１６】
「デバイス」という用語は、ネットワーク（例えば、大規模無線照明制御ネットワーク）を確立又は接続するのに適した任意のデバイスを意味する。デバイスの典型的な例は、スイッチ、ランプ、動き／光センサ又は照明コントローラといった、ルータ又は端末デバイスである。ＺｉｇＢｅｅは埋め込み式デバイス用の規格である。従ってＺｉｇＢｅｅにおいては、例えばＬＯＮ Ｗｏｒｋｓとは対照的に、ルータはアプリケーション・オブジェクトをホストすることができ、幹線電源駆動式（ｍａｉｎｓ−ｐｏｗｅｒｅｄ）でありさえすればよい。それゆえ、例えば照明システムにおいては、ランプはルータの役割を果たすことが期待され、電池駆動式のスイッチは端末デバイスの役割を果たすことになる。
【００１７】
本発明の基本的な思想は、Ｃｓｋｉｐアドレス割当て及びツリールーティングの単純性といったＣｓｋｉｐの利点を、動的アドレス割当て方式の自由度と組み合わせた方式を提唱することである。
【００１８】
本発明の方法の実施形態によれば、第２ツリーパラメータの決定は、第２ツリーパラメータのうちの少なくとも１つを決定することと、欠けている任意の第２ツリーパラメータを、少なくとも１つの決定された第２ツリーパラメータ、並びに特定のノードについての利用可能な子孫ノードの第１及び第２の数に基づいて決定することによって実行することができる。上記少なくとも１つの第２ツリーパラメータは、ユーザによって決定及び設定することができる。
【００１９】
ツリーパラメータは、親ノードによって子ノードに、その子ノードのアドレスと共に提供されることができる。子ノードに提供された第１又は第２のツリーパラメータは、子ノードにおける任意のツリーパラメータ設定を上書きすることができる。さらに、親ノードのＣｓｋｉｐオフセットが、親ノードによって子ノードに、その子ノードのアドレスと共に提供されることができる。
【００２０】
さらなる実施形態によれば、本発明の方法は、特定ノードの子孫である第２特定ノードについての利用可能な子孫ノードの第３の数を、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて決定するステップと、第２特定ノードについての第３ツリーパラメータを、所定の割当てアルゴリズム及び第３ツリーパラメータに基づいて決定される第２特定ノードについての利用可能な子孫ノードの第４の数が、利用可能な子孫ノードの第３の数と等しいか又はそれより小さくなるように決定するステップと、所定の割当てアルゴリズム及び第３ツリーパラメータに基づいて、第２特定ノードの直系子孫のノードにノードアドレスを割り当てるステップと、をさらに含むことができる。第３ツリーパラメータは第１ツリーパラメータと等しいものとすることができる。
【００２１】
本発明はまた、システムのデバイスが大規模無線制御ネットワークの一部とすることができる、システムに関する。
【００２２】
一実施形態によれば、システムのデバイスは建物内に配置されることができ、ツリー構造は建物のトポロジーを表す。
【００２３】
一実施形態によれば、確立されるツリー構造は、親子関係を定義する物理的ツリー構造のみであり、システム内の実際の通信は、任意のその他の論理構造、例えばメッシュに従って行われることができる。
【００２４】
一実施形態によれば、システムのデバイスはＺｉｇＢｅｅデバイスとすることができる。
【００２５】
本発明を、以下、例示的な実施形態を参照してより詳細に説明する。しかしながら、本発明はそれらの例示的な実施形態に限定されるものではない。
【図面の簡単な説明】
【００２６】
【図１】ネットワークにおけるアドレス割当て方式を示す。
【図２】本発明による方法ステップのダイヤグラムを示す。
【図３】本発明の装置のブロック図を示す。
【図４】本発明によるネットワークにおける例示的なアドレス割当て方式を示す。
【発明を実施するための形態】
【００２７】
以下、機能的に類似又は同一の要素は同じ参照番号を有することがある。
【００２８】
非特許文献１のＩＥＥＥ８０２．１５．４によって提唱され、ＺｉｇＢｅｅによって採用されたＣｓｋｉｐに基づくツリーアドレス割当てアルゴリズムは、簡略的にＣｓｋｉｐと呼ばれ、ＺｉｇＢｅｅルータが、ルータ及び端末デバイスの両方の子ノードにネットワークアドレスを、次式に従って自動的に割り当てることを可能にする。
ＡRouterChild＝Ａparent＋１＋Ｃｓｋｉｐ（ｄ）・ｍ
ＡZEDChild＝Ａparent＋Ｃｓｋｉｐ（ｄ）・Ｒm＋ｎ
ここで、
Ａparentは親ノードのアドレスであり、
ＡRouterChildは割り当てられるルータノード・アドレスであり、
ＡZEDChildは割り当てられるエンドノード・アドレスであり、
ｍは連結された（ａｓｓｏｃｉａｔｅｄ）ルータノードの現在の数であって、
ｍ∈｛０，Ｒm−１｝であり、
Ｒmは親当たりのルータ子の最大数であり
ｎは連結されたエンドノードの現在の数であって、ｎ∈｛０，Ｃm−Ｒm−１｝であり、
Ｃmは親当たりの子ノードの最大数であり、
【００２９】
【数１】
2010510708.tif 000003
【００３０】
であり、ｄは親ノードの実際の深さである。
【００３１】
このアドレス割当て方式を稼働させるためには、各ＺｉｇＢｅｅルータデバイスは、ＩＥＥＥ８０２．１５．４に従って、ツリー全体にわたって、すなわちネットワーク全体において一定の、かつ、いわゆるＺｉｇＢｅｅスタック・プロファイルで規定されるＺｉｇＢｅｅに従って、すなわちアプリケーションのクラス全体に対して一定の、以下のパラメータを知る必要がある。
Ｃm（ｎｗｋＭａｘＣｈｉｌｄｒｅｎ）−親デバイス当たりの子ノードの最大数、
Ｒm（ｎｗｋＭａｘＲｏｕｔｅｒｓ）−親デバイス当たりの子ノードの中のルータの最大数、
Ｌm（ｎｗｋＭａｘＤｅｐｔｈ）−最大ツリー深さ
【００３２】
さらに、各デバイスは、それ自体の実際の深さを知らなければならない。
【００３３】
従って、初期の予備環境設定の後は、アドレスは、ＺｉｇＢｅｅアプリケーション・プロファイルコードの一部となり、Ｃｓｋｉｐパラメータだけに基づいて完全に分散された方式でノードに割り当てられることができる。集中型アドレス割当てサーバは必要とされず、ランダムアドレス割当て方式に固有の競合は生じる可能性がない。
【００３４】
この方式には、単純なツリールーティング方式を用いることを可能にするという利点もある。各ルータは、それ自体のアドレスと宛先のＣｓｋｉｐベースのアドレスを比較することによって、宛先がその子孫であるか否かを判定することができる。次に、メッセージはそれぞれツリーを遡って又は下って送られる。メモリを消費するルーティングテーブルも、帯域を消費するルート発見（ｒｏｕｔｅ  ｄｉｓｃｏｖｅｒｉｅｓ）も必要とされない。これはおそらく最も効率的なるルーティング方式ではないが、確かに最も単純であり、リソースが制限された埋め込みデバイスのためには理想的である。
【００３５】
ｎｗｋＭａｘＣｈｉｌｄｒｅｎ Ｃm＝４、ｎｗｋＭａｘＲｏｕｔｅｒｓ Ｒm＝４及びｎｗｋＭａｘＤｅｐｔｈ Ｌm＝３を有するネットワークについての例示的なＣｓｋｉｐオフセット値及びネットワークアドレスは、非特許文献２の表１３４に見いだすことができる。
【００３６】
【表１】
2010510708.tif 000004
【００３７】
図１（非特許文献２の図５４である）は、ＺｉｇＢｅｅ規格による例示的なネットワークにおけるアドレス割当てを示す。この例示的なネットワークはアドレスが０の１つのＺｉｇＢｅｅコーディネータ、並びに複数のルータ及び端末デバイスを含む。以下のデバイス、すなわちアドレスが１、２２、４３及び６４のルータは、ＺｉｇＢｅｅコーディネータの子ノードである。アドレス２のルータデバイスは、アドレス１のルータの子である。アドレス２２のルータは、アドレスが２３及び２８の２つのルータ子を有する。ルータ４３はいかなる子も有していない。アドレスが６５及び７０のルータは、アドレス６４のルータの子である。ルータ６５は、アドレス６６の子ルータデバイスを有する。ネットワークの深さ０のＺｉｇＢｅｅコーディネータはＣｓｋｉｐオフセット値２１を有し、これは、ノード０から開始する各ブランチが上限２１ノードから構成されることができることを意味し、すなわち、そのルータ子ノード（アドレス１、２２、４３及び６４のノード）の各々はＣｓｋｉｐ−１個、すなわち合計で２０個の子孫ノードを有することができる。深さ１にあるデバイス、すなわちアドレス１、２２、４３及び６４のデバイスはＣｓｋｉｐ値５を有し、深さ２にあるデバイス、すなわちアドレス２、２３、２８、６５及び７０のデバイスはＣｓｋｉｐ値１を有し、深さ３にあるデバイス、すなわちアドレス６６のデバイスはＣｓｋｉｐ値０を有する。
【００３８】
Ｃｓｋｉｐツリーアドレス割当てアルゴリズムが単純なせいで、かつ固有のツリールーティング・アルゴリズムの機能が非常に限られているので、１６ビットのアドレス空間（上限６５５３６ノード）内で、広いが浅いツリー又は深いが狭いツリーのいずれかである、自由度の低いトポロジーがもたらされる。広いが浅いツリーは、大きいＣm及びＲmと小さいＬm値で特徴付けられる。深いが狭いツリーは、大きいＬmと小さいＣm及びＲm値で特徴付けられる。どちらの選択肢も、物理的制御ネットワーク・トポロジー又は大きい建物のトポロジーには必ずしも最適であるとはいえない。
【００３９】
図２は、本発明の実施形態による、ツリー構造のノードにアドレスを割り当てる方法のステップを示す。図１に示されるように、ツリー構造は複数のブランチを含むことができる。ツリー構造の親ノードは、子孫である子ノードを有する。子ノードは、ルータノード（それ自身の子ノードを受け入れることができる）、又はブランチの末端位置を定める端末ノードとすることができる。ツリー構造はツリーパラメータによって定義される。ツリーパラメータは、親ノード当たりの子ノードの最大数、親ノード当たりの子ノードの中の親ノードの最大数、又は最大ツリー深さを定義することができる。
【００４０】
第１のステップにおいて、第１のツリーパラメータが決定又は定義される。第１ツリーパラメータは、そのツリー構造によって表されるトポロジー、例えば建物のトポロジーに従って選択される。本発明によれば、ツリーパラメータはツリー構造全体に対して同一である必要はなく、ツリー構造の特定のノードにおいて変更することができる。それゆえ、第１ツリーパラメータは、ツリー構造の第１セクションによって表されるトポロジーに従って選択される。典型的には、第１セクションは、ツリー構造の根位置にある第１ノードから開始する。
【００４１】
第２のステップにおいて、ツリー構造の第１セクション内のノードにノードアドレスが割り当てられる。好ましくは、アドレス割当ては第１ノードから開始され、子孫ノードへと続く。ノードアドレスは、第１ツリーパラメータを考慮して所定の割当てアルゴリズムを実行することによって計算される。
【００４２】
第１の特定ノードに到達したなら、第１ツリーパラメータのうちの１つ又はそれ以上を第２ツリーパラメータに変更することができる。第２ツリーパラメータは、ツリー構造の第２セクションによって表されるトポロジーに従って選択される。第２セクションのノードに割り当てられるアドレスは、第２ツリーパラメータを用いて計算される。従って、第２ツリーパラメータは、特定ノードについて利用可能なアドレスプールが、第２ツリーパラメータで計算した場合に第１ツリーパラメータで計算した場合よりも大きくならないように、選択されなければならない。従って、第３のステップにおいて、特定ノードについての利用可能な子孫ノードの第１の数が、第１ツリーパラメータ及び所定の割当てアルゴリズムに基づいて決定される。第４のステップにおいて、特定ノードについての第２ツリーパラメータが選択され、特定ノードについての利用可能な子孫ノードの第２の数が、第２ツリーパラメータ及び所定の割当てアルゴリズムに基づいて決定される。特定ノードについての利用可能な子孫ノードの第２の数が第１の数と等しいか又はそれより小さい場合、選択された第２ツリーパラメータは有効である。そうでない場合には、選択された第２ツリーパラメータは、利用可能な子孫ノードの第２の数が第１の数と等しいか又はそれより小さくなるような、異なる第２ツリーパラメータによって置換されなければならない。このアプローチは、特定ノードの下位のノード上で費やすことができるアドレスのプールが、ツリーパラメータの変更のせいで大きくならないことを保証する。
【００４３】
有効な第２ツリーパラメータが決定された後、第５のステップにおいて、特定ノードの直系子孫であるツリー構造の第２セクションのノードに、ノードアドレスが割り当てられる。このノードアドレスは、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて計算される。
【００４４】
ツリー構造の第２セクションはブランチ全体をカバーすることができ、又は１つ又は幾つかのノードをカバーすることもできる。この場合、第２セクションの後には第３ツリーパラメータを有する第３セクションが続き、第３ツリーパラメータは、第２ツリーパラメータに関して説明されたのと同様に選択することができる。
【００４５】
本発明の方法ステップは、異なる順序で実行することができる。例えば、第２ツリーパラメータの定義は、どのノードアドレスの割当ての前にも実行することもできる。
【００４６】
図３は、本発明の実施形態による、通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための、通信ネットワークの装置、ノード又はデバイスのブロック図を示す。本発明の方法ステップは、装置のセクションによって実行することができる。装置は、通信ネットワーク・ツリー構造の第１ツリーパラメータを決定する手段３１と、所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、第１ノードの直系子孫のノードにノードアドレスを割り当てる手段３２と、所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定する手段３３と、特定ノードについての第２ツリーパラメータを、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて決定される特定ノードについての利用可能な子孫ノードの第２の数が利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように決定する手段３４と、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて、特定ノードの直系子孫のノードにノードアドレスを割り当てる手段３５とを含む。
【００４７】
通信ネットワーク・ツリー構造の第１ツリーパラメータを決定する手段３１は、第１ツリーパラメータを、第１ノードの直系子孫のノードにノードアドレスを割り当てる手段３２、及び特定ノードについての利用可能な子孫ノードの第１の数を決定する手段３３に提供するように構成される。第１の数を決定する手段３３は、利用可能な子孫ノードの第１の数を、第２ツリーパラメータを決定する手段３４に提供するように構成される。第２ツリーパラメータを決定する手段３４は、第２ツリーパラメータを、特定ノードの子孫ノードにノードアドレスを割り当てる手段３５に提供するように構成される。
【００４８】
本発明の実施形態によれば、所定の割当てアルゴリズムは、Ｃｓｋｉｐツリーアドレス割当てアルゴリズムである。
【００４９】
以下のＣｓｋｉｐの式を、例示的なツリーパラメータのセットであるＬm＝７、Ｃm＝１２、Ｒm＝４について計算すると、深さレベルｄごとに以下のＣｓｋｉｐオフセット値が得られる。
【００５０】
【数２】
2010510708.tif 000005
【００５１】
【表２】
2010510708.tif 000006
【００５２】
深さレベルｄ＋１の新たな子ルータの各々は、深さレベルｄのその親から、その前の子ルータよりもＣｓｋｉｐ（ｄ）だけ高いアドレスを取得する。それゆえ、Ｃｓｋｉｐ（ｄ）オフセットは、深さレベルｄ＋１における子ルータの各々に対して確保されるアドレス空間のサイズを定める。このプールの第１のアドレスは、子ルータ自身のアドレスである。
【００５３】
アドレス空間の残りは、子ルータによって、深さレベルｄ＋２からＬmまでの自身の子孫に対してＣｓｋｉｐアルゴリズムを用いてアドレスを割り当てるために用いられることになる。
【００５４】
ＺｉｇＢｅｅ規格は、Ｃｓｋｉｐパラメータをネットワーク全体を通じての定数として定義するが、アドレスのプールは多くの異なる設定を用いて消費することができるので、各ルータがＬm、Ｃm、Ｒmについて同一の値を用いる技術的な必要性があるわけではない。他の値のＬm2、Ｃm2、及びＲm2について、ルータ当たり収容できる子孫の総数Ｄ（ｄ）は、
Ｄ（ｄ）＝Ｒm2＊Ｃｓｋｉｐ（ｄ＋１）＋Ｃｍ2−Ｒｍ2
として計算することができる。
【００５５】
例えば、上記の例のＬm＝７、Ｃm＝１２、Ｒm＝４の場合の深さｄ＝１の４つのルータのうちのいずれかについて利用可能な１６３８０個の子孫ノードの総プールは、以下のいずれの仕方でも使い尽くすことができる。
【００５６】
【表３】
2010510708.tif 000007
【００５７】
表３は、アドレス空間をどのように使用できるかの例を示すにすぎず、全ての可能な再利用の仕方を示しているのでもなく、アドレス空間を完全に再利用する仕方を示しているのでもない。さらになお可能な組合せを、例えば他のＬm値について追加することができる。
【００５８】
従って、ツリー構造の最大深さ、並びに子及びルータ子の最大数を、ツリーセクション毎に、ブランチ毎に、又は各深さレベルの全てのルータ毎にさえ自由に定めることができる。
【００５９】
１つの実施形態によれば、本発明は、幾つかの大きな部屋が長く狭い廊下に接続している建物内に実装することができる。長い距離は、廊下のためにカバーされる必要がある。これは多くのホップ（ｈｏｐ）を必要とする。従って、Ｌmは大きな値に設定されなければならない。廊下は狭いので、小さいＣm／Ｒm値で十分である。しかしながら、大きな部屋の内部では、全てのデバイスを収容し、かつ全てのノードに達するために必要とされるホップの数を減らすために、親当たりのルータの数は多い方が好ましいだろう。
【００６０】
ネットワーク全体にわたって定義されたパラメータによる「１つで全てに適合する（ｏｎｅ−ｆｉｔ−ａｌｌ）」Ｃｓｋｉｐソリューションは不可能である。ホールに適合したツリーパラメータ、例えばＬm＝７、Ｃm＝４、Ｒm＝４を選択すると、アドレスプールは部屋用としては小さすぎるものになる。この場合、深さ＝４において各ルータ当たりわずか２１デバイスしか利用できない。もっと多数のデバイスが好ましい。
【００６１】
【表４】
2010510708.tif 000008
【００６２】
部屋に適合したツリーパラメータ、例えばＬm＝７、Ｃm＝３１、Ｒm＝１５を選択すると、計算されたアドレスは１６ビットアドレス空間（上限６５５３６アドレス）を越えるので、不適切な値、すなわち許容範囲外となる。
【００６３】
【表５】
2010510708.tif 000009
【００６４】
従って、廊下のためには、例えばＬm＝１５、Ｃm＝２、Ｒm＝２を用いることができるだろう。しかしながら、大きな部屋の内部では、全てのノードに達するために必要とされるホップの数を減らすために、親当たりのルータはより大きい数が好ましい。
【００６５】
以下、４ホップ後に大きな部屋に達すると仮定する。
【００６６】
【表６】
2010510708.tif 000010
【００６７】
そうすると、深さ３において、各ルータのアドレスプール・サイズは４０９４である。このアドレスプールを様々な仕方で用いることができる。いくつかの例を下記に示す。
【００６８】
【表７】
2010510708.tif 000011
【００６９】
広いエリアをわずかな追加のホップでカバーするために、例えばＬm＝７でＲm＝８を選択することができる。
【００７０】
図４は、上記の選択についての模式的なツリートポロジーの断片（１ブランチ）を示す。深さ４から開始する各ルータ「Ｒ」に対して、Ｃm＝５５までの子ノードを連結することができるので、部屋内の全てのノードに達する十分な機会がある。もしＲm＝８をシステム内の全てのルータに対して設定したならば、Ｌmの最大値は５となり、対応する最大Ｃmは１４であり、総プールサイズは６５５３４である。部屋に達するまでにすでに４ホップを必要とするので、この部屋の内部で使うためには１ホップしか残らないことになる。深さ４の２つのルータで、Ｃmの２倍のノード、すなわち２８ノードしかアドレス指定できないことになる。
【００７１】
ツリーの最大深さは図４に示すようにｄ＝７である。ツリー構造は２つのセクションに分けられる。第１のセクションは、深さ０、１、２及び３をカバーする。第２のセクションは、深さ４、５及び６をカバーする。
【００７２】
第１セクションは、深さ０に開始ノード４０、深さ１にルータノード４１、深さ２にルータノード４２、そしてさらに深さ３にルータノード４３を含む。ルータノード４１は開始ノード４０の子である。ルータノード４２はルータノード４１の子ノードであり、ルータノード４３はルータノード４２の子ノードである。第１ツリーパラメータＬm＝１５、Ｃm＝２及びＲm＝２は、ツリー構造の第１セクションに対して有効である。表６に示されるように、第１ノード４０はＣｓｋｉｐ値３２７６７を有し、ルータノード４１はＣｓｋｉｐ値１６３８３を有し、ルータノード４２はＣｓｋｉｐ値８１９１を有し、ルータノード４２はＣｓｋｉｐ値４０９５を有する。上述のように、ツリー構造の第１セクションは、建物の長いホールをカバーするのに適している。長いホールでは、親ノードが１又は２より多くの子ノードを有する必要はない。
【００７３】
ツリー構造の第２のセクションは、建物の部屋をカバーするのに適している。部屋においては、親ノードが複数の子ノードを有する必要がある。従って、第１ツリーパラメータとは異なる第２ツリーパラメータは、第２セクションに対して有効である。表７に示されるいずれかのパラメータのセットを第２ツリーパラメータとして用いることができる。表７の全てのパラメータは、対応する子孫数Ｄがルータノード４３のＣｓｋｉｐ値より小さいか又はそれと等しいことで共通している。この実施形態によれば、Ｌm＝７、Ｃm＝５５及びＲm＝８が第２ツリーパラメータとして選択される。これらの第２ツリーパラメータは、第２セクションの親ノードが複数の子ノードを有することを可能にする。図４に示されるように、深さｄ＝４には２つのルータノード４４ａ、４４ｂがある。ルータノード４４ａ、４４ｂは、ルータノード４３の子ノードである。ルータノード４４ａ、４４ｂの各々は、複数の子ノードを有する。例示的に、深さｄ＝５において、ルータノード４４ａ、４４ｂの子ノードである２つのルータノード４５ａ、４５ｂのみが、参照符号付きで示されている。深さｄ＝５のルータノードの各々もまた、深さｄ＝６において複数の子孫ノードを有する。第２ツリーパラメータＬm＝７、Ｃm＝５５及びＲm＝８を用いることで、第２ツリーセクションのルータノードのための対応するＣｓｋｉｐ値を計算することができる。図４に示されるように、深さｄ＝４におけるルータノード４４ａ、４４ｂの各々はＣｓｋｉｐ値４９６を有し、深さｄ＝５におけるルータノードの各々はＣｓｋｉｐ値５６を有し、深さｄ＝６におけるルータノードの各々はＣｓｋｉｐ値１を有する。
【００７４】
ユーザは、物理的な建物のトポロジー及び意図されるネットワークのトポロジーの知見に基づいて、特定のルータについて、最大深さＬm、子の数Ｃm及びルータ子の数Ｒmのパラメータを予め定める。
【００７５】
ユーザは、これらの３つのパラメータの全て又はそのうちのただ１つだけを定めることができる。後者の場合、その他のパラメータは、一旦、利用可能なアドレスプールのサイズ、すなわち親ノードのＣｓｋｉｐオフセットが既知となったら、トレードオフの関係となる。親のＣｓｋｉｐオフセットは、親によって、関連する手順の間に、例えば子ルータのアドレスと共に、子ルータに自動的に提供されることができる。あるいは、子ノードは、親によって用いられるＬm、Ｃm及びＲm並びに親の深さが既知であれば、親ノードについてのＣｓｋｉｐオフセットを計算することができる。
【００７６】
ユーザは、Ｃｓｋｉｐパラメータを子孫のブランチ全体に対して定数として定めることもでき、あるいは、この特定のルータに対してのみ必須のものとして、例えば１状態ビットとして、定めることもできる。前者の場合、Ｃｓｋｉｐパラメータは、親ルータによって、関連するプロセスの間に、例えば子ルータのＣｓｋｉｐアドレスと共に、ビーコン要求に応じて送信されるビーコンの中で、又は関連する応答の中で、帯域内で接続された子ルータデバイスに伝達されることができる。接続している子ルータ上で、帯域内伝達されたＣｓｋｉｐパラメータは、例えばＺｉｇＢｅｅスタック・プロファイルで定義された、デフォルトの設定を上書きすべきである。
【００７７】
任意に、伝達されたパラメータは、例えばコンパイルされたコードにより、又はコンソールからの帯域によりユーザによって設定された子の上のＣｓｋｉｐパラメータのセットを上書きすることもできる。
【００７８】
本発明の機能の少なくとも一部は、ハードウェア又はソフトウェアによって実行することができる。ソフトウェア内に実装された場合、単一の又は複数の標準的なマイクロプロセッサ又はマイクロコントローラを用いて、本発明を実行する単一の又は複数のアルゴリズムを処理することができる。
【００７９】
「含む」という語は、他の要素又はステップを除外せず、「ａ」又は「ａｎ」という語は、複数を除外しない。さらに、特許請求の範囲におけるどの参照符号も、本発明の範囲を限定するものと解釈されるべきではない。
【符号の説明】
【００８０】
４０：開始ノード、第１ノード
４１、４２、４３、４４ａ、４４ｂ、４５ａ、４５ｂ：ルータノード
【図１】
2010510708.tif 000013
【図２】
2010510708.tif 000014
【図３】
2010510708.tif 000015
【図４】
2010510708.tif 000016
【手続補正書】
【提出日】平成21年5月19日(2009.5.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための方法であって、各ノードは前記通信ネットワークのネットワーク・デバイスに対応し、
前記通信ネットワーク・ツリー構造の第１ツリーパラメータを、前記ツリー構造の第１セクションによって表されるトポロジーに従って決定するステップと、
所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、第１ノードの直系子孫の前記第１セクション内のノードにノードアドレスを割り当てるステップと、
前記所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定するステップと、
前記特定ノードについての第２ツリーパラメータを、前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて決定される前記特定ノードについての利用可能な子孫ノードの第２の数が、前記利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように、前記ツリー構造の第２セクションによって表されるトポロジーに従って決定するステップと、
前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて、前記特定ノードの直系子孫の前記第２セクション内のノードにノードアドレスを割り当てるステップと、を含むことを特徴とする方法。
【請求項２】
前記ノードが、親ノード及び親ノードの子孫である子ノードを含み、前記第１ツリーパラメータを決定する前記ステップが、親ノード当たりの子ノードの最大数、親ノード当たりの子ノードの中の親ノードの最大数、及び最大ツリー深さを定義するステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記所定の割当てアルゴリズムが、Ｃｓｋｉｐツリーアドレス割当てアルゴリズムであることを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記ノードが、エンドノード及びルータノードを含み、各エンドノードはいかなる子孫ノードも持たず、各ルータノードは他の子孫ノードを持つことができ、ノードにノードアドレスを割り当てる前記ステップが、次式
ＡRouterChild＝Ａparent＋１＋Ｃｓｋｉｐ（ｄ）・ｍ
ＡZEDChild＝Ａparent＋Ｃｓｋｉｐ（ｄ）・Ｒm＋ｎ
に基づき、ここで
【数１】
2010510708.tif 000017
であり、
Ａparentは親ノードのアドレスであり、
ＡRouterChildは割り当てられるルータノード・アドレスであり、
ＡZEDChildは割り当てられるエンドノード・アドレスであり、
ｍは連結されたルータノードの現在の数であって、ｍ∈｛０，Ｒm−１｝であり、
Ｒmは親ノード当たりのルータノードの最大数であり、
ｎは連結されたエンドノードの現在の数であって、ｎ∈｛０，Ｃm−Ｒm−１｝であり、
Ｃmは親ノード当たりの子ノードの最大数であり、
Ｌmは最大ツリー深さであり、
ｄは親ノードの実際の深さである、
ことを特徴とする請求項３に記載の方法。
【請求項５】
深さｄにおける前記特定ノードについての前記利用可能な子孫ノードの第１の数が、次式
Ｄ1（ｄ）＝Ｃｓｋｉｐ（ｄ−１）−１
に基づくことを特徴とする請求項４に記載の方法。
【請求項６】
深さｄにおける前記特定ノードについての前記利用可能な子孫ノードの第２の数が、次式
Ｄ2（ｄ）＝Ｒm2＊Ｃｓｋｉｐ（ｄ）＋Ｃm2−Ｒm2
に基づき、ここで
Ｃm2は親ノード当たりの子ノードの第２の最大数であり、
Ｒm2は親ノード当たりの子ノードの中の親ノードの第２の最大数であり、
Ｌm2は第２の最大ツリー深さである、
ことを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
前記第２ツリーパラメータを決定する前記ステップが、
前記第２ツリーパラメータのうちの少なくとも１つを決定するステップと、
欠けている任意の前記第２ツリーパラメータを、前記決定された少なくとも１つの第２ツリーパラメータ、並びに前記特定ノードについての利用可能な子孫ノードの前記第１及び第２の数に基づいて決定するステップと、を含むことを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
前記特定ノードの子孫である第２特定ノードについての利用可能な子孫ノードの第３の数を、前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて決定するステップと、
前記第２特定ノードについての第３ツリーパラメータを、前記所定の割当てアルゴリズム及び前記第３ツリーパラメータに基づいて決定される前記第２特定ノードについての利用可能な子孫ノードの第４の数が、前記利用可能な子孫ノードの第３の数と等しいか又はそれより小さくなるように決定するステップと、
前記所定の割当てアルゴリズム及び前記第３ツリーパラメータに基づいて、前記第２特定ノードの直系子孫のノードにノードアドレスを割り当てるステップと、をさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記第３ツリーパラメータが、前記第１ツリーパラメータと等しいことを特徴とする請求項８に記載の方法。
【請求項１０】
コンピュータに請求項１乃至９のいずれか１項に記載の方法を実行させることを特徴とするコンピュータプログラム。
【請求項１１】
請求項１０に記載のコンピュータプログラムを記憶した記録担体。
【請求項１２】
通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための装置であって、各ノードは前記通信ネットワークのネットワーク・デバイスに対応し、
前記通信ネットワーク・ツリー構造の第１ツリーパラメータを、前記ツリー構造の第１セクションによって表されるトポロジーに従って決定する手段と、
所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、第１ノードの直系子孫の前記第１セクション内のノードにノードアドレスを割り当てる手段と、
前記所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定する手段と、
前記特定ノードについての第２ツリーパラメータを、前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて決定される前記特定ノードについての利用可能な子孫ノードの第２の数が、前記利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように前記ツリー構造の第２セクションによって表されるトポロジーに従って決定する手段と、
前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて、前記特定ノードの直系子孫の前記第２セクション内のノードにノードアドレスを割り当てる手段と、を含むことを特徴とする装置。
【請求項１３】
通信ネットワークのネットワーク・デバイスであって、
通信ネットワーク・ツリー構造の第１ツリーパラメータを、前記ツリー構造の第１セクションによって表されるトポロジーに従って決定する手段と、
ツリーパラメータの変更が必要かどうか決定する手段と、
所定の割当てアルゴリズム及び前記第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定する手段と、
前記特定ノードについての第２ツリーパラメータを、前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて決定される前記特定ノードについての利用可能な子孫ノードの第２の数が、前記利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように、前記ツリー構造の第２セクションによって表されるトポロジーに従って、ユーザ入力に基づいて決定する手段と、
前記所定の割当てアルゴリズム及び前記第２ツリーパラメータに基づいて、前記特定ノードの直系子孫である前記第２セクション内の子ノードにノードアドレスを割り当てる手段と
前記通信ネットワーク・ツリー構造の第２ツリーパラメータを子ノードに伝達する手段と、を含むことを特徴とするネットワーク・デバイス。
【請求項１４】
前記第１ツリーパラメータを決定する前記手段が、親ノードによって使用される通信ネットワーク・ツリー構造の前記第１ツリーパラメータを決定するように構成されることを特徴とする請求項１３に記載のネットワーク・デバイス。
【請求項１５】
請求項１２又は１３に記載の装置と、
ツリー構造に配置され、各デバイスが前記ツリー構造のノードに対応する複数のルータデバイス及び端末デバイスと、を含むことを特徴とするシステム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００７
【補正方法】変更
【補正の内容】
【０００７】
上記目的は、独立請求項によって解決される。さらに、実施形態が従属請求項に示されている。
上記目的を達成するために、本発明は、通信ネットワーク・ツリー構造のノードにアドレスを割り当てるための方法を提供し、各ノードは通信ネットワークのネットワーク・デバイスに対応し、この方法は、
通信ネットワーク・ツリー構造の第１ツリーパラメータを決定するステップと、
所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、第１ノードの直系子孫のノードにノードアドレスを割り当てるステップと、
所定の割当てアルゴリズム及び第１ツリーパラメータに基づいて、特定ノードについての利用可能な子孫ノードの第１の数を決定するステップと、
特定ノードについての第２ツリーパラメータを、所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて決定される特定ノードについての利用可能な子孫ノードの第２の数が、利用可能な子孫ノードの第１の数と等しいか又はそれより小さくなるように、決定するステップと、
所定の割当てアルゴリズム及び第２ツリーパラメータに基づいて、特定ノードの直系子孫のノードにノードアドレスを割り当てるステップと、を含む。
【国際調査報告】
2010510708.tif 000018
2010510708.tif 000019