JP4933421B2 - ネットワークデータの送信方法及びシステム - Google Patents

Description

本出願は、２００７年１月８日出願の米国仮出願第６０／８７９０４７号と、２００７年２月１６日出願の米国仮出願第６０／９０１６７３号との権利を主張するものであり、両出願とも、いかなる目的に対しても、全体をここに参照により援用する。
本開示は、広くネットワークシステムに関し、特に、ネットワークデータの送信方法及びシステムに関する。

通信システムでは、ネットワークノード（又はいわゆるホスト）は、自分のＩＤ又はアドレスを、静的又は動的に割り当てることができる。静的な設定では、ユーザは事前に利用可能なアドレスを知り、手動でそのアドレスを設定する必要がある。対照的に、自由度の高いマルチホップ環境では、ＩＥＥＥ８０２．１６ｊに記載されたタイプのように、オペレータ又はユーザに手動設定を実行させることは適切ではない。他の選択肢である動的設定は、ノードに自分のＩＤを動的に設定したり、集中サーバからＩＤを取得したりすることを可能にする。典型的な動的設定スキームでは、全ノードＩＤがランダムに割り当てられ、ノードが付加的なルーティング情報を交換又は維持し、且つルーティング経路を決定するようにするために、付加的なルーティングアルゴリズム又はルーティングテーブルが必要になる。

図１は模範的なマルチホップリレー（ＭＲ）ネットワーク１００を示す。ネットワーク１００では、マルチホップリレー基地局ＢＳ（ＭＲ−ＢＳ）１０２がルートノードとして動作し、リレー局（ＲＳ）及び移動局（ＭＳ）が中間ノード又はリーフノードとして動作する。ネットワークセットアップ処理は、各ネットワークノードに識別子（又はアドレス）を割り当て、さらに、ノード間にルーティンググループを構築する。例えば、ＲＳ３（１０４）にはアドレスが割り当てられて、ＭＲ−ＢＳからＲＳ４（１０６）に向かうパケットの転送を担い、さらに、ＲＳ１（１０８）は、ＲＳ３に向かうＭＲ−ＢＳから受信したパケットを破棄する。このようなルーティング情報は各ＲＳのルーティングテーブルに保持して、中間ノードがネットワークに出入りする場合に、最新のルーティング情報を更新し得るようにすることができる。

２つの例でルーティングテーブルの活用を示す。米国特許第６１９２０５１号は、ネットワークパケットを転送するための、集中型ルーティングテーブル及び分散型転送テーブルにおける、複数レベルのツリーデータ構造を開示している。各データ構造の各レベルは、受信パケットにあるネットワークアドレスの、別々のフィールドと関連付けられる。米国特許第６９３４２５２号は、ルーティングテーブルのエントリに格納された親ノードの情報を用いる、バイナリネットワークアドレス検索を開示している。可変長のプレフィックスは、ネットワークアドレス転送テーブルに格納される。各プレフィックスは、転送テーブル中のエントリに対応する。転送テーブルの各エントリは、バイナリツリーにおける各エントリの親ノードに関する経路情報を含む。

ノード識別は、ルーティングテーブルを保持せずに実行できる。米国特許第６６１８７５５号は、ネットワークのノードによって表されるネットワーク内のアドレスの範囲によって、自動的に、ネットワークにおけるサブネットを識別するソフトウェア機能を開示している。これらのアドレスは、それぞれ、順序付けられた一定数のビット列を含む。

ネットワークのノード及びノード間のグループを表現するための素因数分解方法は、米国特許公報第２００６／０１９８３２０号、及びＩＥＥＥ Ｃ８０２．１６ｊ−０６／１７１に記載されている。この方法の転送処理では、受信ノードは、パケットをどこに転送するかを決定するために、受信したパケットのＩＤ番号を因数分解する必要がある。他の方法は、ＩＥＥＥ Ｃ８０２．１６ｊ−０７／０４８ｒ６に記載されている。この方法は、パケットをどこに転送するか又はパケットを破棄すべきかどうかを決定するために、ネットワークノードが、受信したアドレスの整数ブロックを識別する、連続整数ブロックのルーティング法に関する。

本開示による１つの模範的な態様は、送信ノード及び受信ノードとしての複数の通信ノードを有するネットワーク環境にてデータを送信する方法である。
この方法は、
決められた数ＮでのＮキャリー演算（Ｎ−ｃａｒｒｙ ｏｐｅｒａｔｉｏｎ）によって、複数の通信ノードから１つのノードＩＤを送受信グループの受信ノードに割り当てる第１のステップと、
ノードＩＤを利用し、複数の通信ノード間で、送受信グループでの少なくとも１つの送信ノードから少なくとも１つの送受信グループの受信ノードへデータを送信する第２のステップとを含み、
Ｎキャリー演算は、多項式に基づく演算であり、多項式は指数値の乗数を含み、指数値は決められた数Ｎ、および第１レベルの送信ノードの第１受信レベルから前記ノードＩＤを割り当てられた受信ノードまでの送受信経路に沿っている受信ノードの１組の識別子中のそれぞれに基づいて定まり、組の識別子中のそれぞれは中間レベルシーケンシャル識別子および親ノード中間レベルシーケンシャル識別子のうちの１つである。

本開示による他の模範的な態様は、通信システムである。
このシステムは、
相互接続してネットワーク環境を形成する送信ノード及び受信ノードとしての複数の通信ノードを含み、
決められた数ＮでのＮキャリー演算によって、複数の通信ノードから１つのノードＩＤを送受信グループの受信ノードに割り当て、
送受信グループの少なくとも１つの送信ノードは、ノードＩＤを利用することによって、送受信グループの少なくとも１つの受信ノードにデータを送信し、
Ｎキャリー演算は、多項式に基づく演算であり、多項式は指数値の乗数を含み、指数値は前記決められた数Ｎ、および第１レベルの送信ノードの第１受信レベルからノードＩＤを割り当てられた受信ノードまでの送受信経路に沿っている受信ノードの１組の識別子中のそれぞれに基づいて定まり、組の識別子中のそれぞれは中間レベルシーケンシャル識別子および親ノード中間レベルシーケンシャル識別子のうちの１つである。

また、本開示による他の模範的な態様は、ネットワークの送受信グループにおける送信ノード及び受信ノードとしての複数の通信ノードであって、決められた数ＮでのＮキャリー演算によって、複数の通信ノードから１つのノードＩＤを送受信グループの受信ノードに割り当て、送受信グループの少なくとも１つの送信ノードは、ノードＩＤを利用することによって、送受信グループの少なくとも１つの受信ノードにデータを送信する。
この通信ノードは、
データ及び命令を格納する少なくとも１つのメモリと、
このメモリにアクセスするように構成した少なくとも１つのプロセッサであって、
命令を実行する場合に、
ノードＩＤを利用して通信データを送信するように構成され、Ｎキャリー演算は、多項式に基づく演算であり、多項式は指数値の乗数を含み、指数値は決められた数Ｎ、および第１レベルの送信ノードの第１受信レベルからノードＩＤを割り当てられた受信ノードまでの送受信経路に沿っている受信ノードの１組の識別子中のそれぞれに基づいて定まり、組の識別子中のそれぞれは中間レベルシーケンシャル識別子および親ノード中間レベルシーケンシャル識別子のうちの１つである。

上記の一般的な記述及び以下の詳細な記述は、模範的な説明に過ぎず、請求項として本発明を限定するものではないことに留意されたい。

通信システム環境では、データは、第１のレベルの送信ノードから第１のレベルの受信ノード又は次のレベルの受信ノードへの送受信経路を通じて、複数の通信ノードの送受信グループ間で送信できる。模範的な例として、ネットワークの複数のノードの間で、ネットワークノードの１つをルートノードとして指定し、１つ以上の他のノードを子ノードとして指定することによって、論理ツリーに基づくトポロジーによって複数のノードを含む、ネットワークを形成することができる。図２aは、本発明の実施形態による、このような論理ツリーに基づくトポロジーを有するように構成した、ネットワーク２００の概略例である。このツリーに基づくトポロジーは、最大数ｋの子レベルで構成される。より広範には、通信システムは、任意のネットワークトポロジー、例えばツリーに基づくネットワーク又はメッシュネットワークとすることができる。

ネットワーク２００の第ｋの子レベルの各子ノードには、この子ノードを識別するように各親ノードに対する識別子ａ_ｋを割り当てる。ここで識別子ａ_ｋは任意の数とすることができる。実装段階では、識別子ａ_ｋは、０以上Ｎ以下の整数とすることができる。Ｎは決められた数とする。Ｎは、あらゆる任意の数、又はツリートポロジーの複数ノードのそれぞれに接続される子ノードの最大数に、予め決めることができる。ある実装では、決められた数Ｎは、システムにより動的に維持することができる。さらに、識別子ａ_ｋは、ランダムシーケンスで、又は逐次割り当てることができる。一例として、各子ノードの識別子ａ_ｋは、それがその親ノードと関連付けられる順番に従って割り当てることができる。

図２ａに示すように、ノードＳの子ノードは、ツリートポロジーの第ｋの子レベルを形成するように接続され、Ｎ個の子ノードがノードＳに接続される。本発明による一例示実施形態では、ノードＳの各子ノードの識別子ａ_ｋに、１からＮの範囲で選んだ数を割り当てることができる。１つの実装では、ノードＴの識別子ａ_ｋとしてＮ、ノードＵの識別子ａ_ｋとしてＮ−１、・・・、ノードＹの識別子ａ_ｋとして２、そして、ノードＺの識別子ａ_ｋとして１を割り当てることができる。

本発明による他の例示実施形態では、代わりに、ノードＳの各子ノードの識別子ａ_ｋに、０からＮ−１の範囲で選んだ数を割り当てることができ、例えば、ノードＴの識別子ａ_ｋとして０を割り当て、ノードＵの識別子ａ_ｋとして１を割り当て、・・・、ノードＹの識別子ａ_ｋとしてＮ−２を割り当て、ノードＺの識別子ａ_ｋとしてＮ−１を割り当てる。この例では、第１の子レベルの識別子ａ_１を１〜Ｎ−１の中から割り当て、決められた数Ｎを２^ｉとし、ここで、ｉは０以上の整数とする。

ルートノード、又はコントロール能力を備える少なくとも１つの他のノード、又は子ノードは、ノードＩＤを生成する情報を格納し、且つデータの転送又はネットワークの設定を管理できる。例えば、このような情報は、決められた数Ｎ、論理ツリートポロジーにおける親ノードの最大子ノード数、Ｎ＝２^ｉの実装における整数ｉ、子ノードの識別子ａ_ｋ、子ノードの子レベルｋ、ルートノードの第１の子レベルから子ノードへの、親−子経路に沿った一組の識別子｛ａ_１，ａ_２，・・・，ａ_ｋ｝、及び、論理ツリーの最大子レベルＨ、を含むことができる。他の情報又はパラメータを用立てることもでき、随意格納すべき情報の種類は、実装の仕方に依存する。

本発明の実施形態は、任意のネットワーク通信システムにて実施することができる。例示目的用に、以下の段落では、マルチホップリレーネットワークを、決められた数Ｎのノードが存在し、ノードＩＤを利用してデータを送信する通信ネットワーク環境において、ノードＩＤを生成するデータ送信アルゴリズムを実証するための、例示通信システムとして説明する。

各子ノードのノードＩＤは、以下の段落で説明するように、２桁のキャリー演算（２’ｃａｒｒｙ ｏｐｅｒａｔｉｏｎ）によって生成することができる。図３はマルチホップリレー基地局（ＭＲ−ＢＳ）及び多数のリレー局（ＲＳ）を含む、例示マルチホップリレーネットワーク３００を示す。移動局（ＭＳ、図示せず）は、ＭＲ−ＢＳかＲＳのいずれかに関連付けることができる。

ネットワーク３００は、ＭＲ−ＢＳルートノード３０２を含み、５段の子レベルを持つ論理ツリートポロジーを有するように構成する。第１の子レベルは、子ノードＲＳ_Ａ（ａ_１＝１、ＩＤ＝１）、ＲＳ_Ｂ（ａ_１＝２、ＩＤ＝２）及びＲＳ_Ｃ（ａ_１＝３、ＩＤ＝３）を含む。第２の子レベルは、ＲＳ_Ａの子ノードであるＲＳ_Ｄ（ａ_２＝０、ＩＤ＝４）、並びに、ＲＳ_Ｃの子ノードであるＲＳ_Ｅ（ａ_２＝０、ＩＤ＝１２）及びＲＳ_Ｆ（ａ_２＝１、ＩＤ＝１３）を含む。第３の子レベルは、ＲＳ_Ｄの以下の子ノード、すなわち、ＲＳ_Ｇ（ａ_３＝０、ＩＤ＝１６）、ＲＳ_Ｈ（ａ_３＝１、ＩＤ＝１７）、ＲＳ_Ｉ（ａ_３＝２、ＩＤ＝１８）及びＲＳ_Ｊ（ａ_３＝３、ＩＤ＝１９）を含む。第４の子レベルは、ＲＳ_Ｉの３つの子ノード、すなわち、ＲＳ_Ｋ（ａ_４＝０、ＩＤ＝７２）、ＲＳ_Ｌ（ａ_４＝１、ＩＤ＝７３）及びＲＳ_Ｍ（ａ_４＝２、ＩＤ＝７４）を含む。第５の子レベルは、ＲＳ_Ｋの４つの子ノード、すなわち、ＲＳ_Ｎ（ａ_５＝０、ＩＤ＝２８８）、ＲＳ_Ｏ（ａ_５＝１、ＩＤ＝２８９）、ＲＳ_Ｐ（ａ_５＝２、ＩＤ＝２９０）及びＲＳ_Ｑ（ａ_５＝３、ＩＤ＝２９１）を含む。

ネットワーク３００の構成では、ｉ＝２であるため子ノードの決められた数Ｎ＝２^ｉは２^２＝４であり、最大子レベルＨは５、そして、第１の子レベル（ｋ＝１）の各ノードの識別子ａ_ｋには、１から３の整数を順次割り当てる。この例では、各親ノードに関連する他の子レベルの各ノードの識別子ａ_ｋには、０から３の整数を順次割り当てる。

図４は、ノードＩＤを２進数表記で表したネットワーク３００を示す。ネットワーク３００の論理ツリートポロジーの各子ノードのノードＩＤを２進数表記に変換することにより、ネットワーク３００のノードＩＤを生成するのに、４（２桁）のキャリー演算の実行が可能になる。さらに、ノードＩＤ割り当ての計算はビット演算で実現できる。

図４を参照すると、本発明の実施形態による例示実装として、各ノードＩＤの下位ｉビットの値を異なる値に設定することにより、第１の子レベルのノードのノードＩＤには１から２^ｉ―１の範囲から選択した整数を割り当てる。他の子レベルのノードに対しては、コントロールノード、例えばＭＲ−ＢＳが、各子ノードの親ノードＩＤをｉビット左シフトし、さらに、０から２^ｉ―１の範囲から整数を選択することにより下位ｉビットを異なる値に設定する。このプロセスは、新たに出現したノードに対するノードＩＤを生成したり、子ノードＲＳを接続したりするのに利用できる。例えば、図４のノードＲＳ_Ｇ及びＲＳ_Ｈの出現後に、新たにＲＳ_Ｉ及びＲＳ_ＪがＲＳ_Ｄ（ＩＤ＝００ ００ ０１ ００）を親ノードとして次々に関連付けられるように出現するものとする。ＲＳ_ＩにＩＤを割り当てるために、コントロールノードＭＲ−ＢＳは自分自身のＩＤを２ビット左シフトして００ ０１ ００ ００を得て、さらに、ノードＲＳ_ＩはＲＳ_Ｄに属する３番目のノードであるため、下位２ビットを１０に設定して、００ ０１ ００ １０を得る。同様に、ノードＭＲ−ＢＳは、ノードＲＳ_ＩにＩＤを割り当てた後、ノードＲＳ_Ｊに００ ０１ ００ １１を割り当てる。同様の方法を用い（図示せず）、各ノードＩＤの上位ｉビットの値を異なる値に設定することにより、第１の子レベルのノードのノードＩＤを整数で割り当てることもできる。他の子レベルのノードに対しては、コントロールノード、例えばＭＲ−ＢＳは、各子ノードの親ノードＩＤをｉビット右シフトして、さらに、０から２^ｉ―１の範囲内で整数を選択することにより上位ｉビットを異なる値に設定する。

再び図３を参照すると、他の例示実施形態では、各子ノードに識別子ａ_ｋを割り当てることができ、第１の子レベルの各ノードのノードＩＤには、自分自身の識別子ａ_１を割り当てることができる。他の子レベルの各ノードのノードＩＤは、各子ノードの親ノードＩＤをｉビット左シフトし、且つ各子ノードの識別子ａ_ｋに下位ｉビットを設定する演算を行うことで割り当てることができる。例えば、図３のＲＳ_ＩとＲＳ_Ｊは共通の親ノードＲＳ_Ｄ（ＩＤ＝４）（００ ００ ０１ ００）と関連付けられる。ＲＳ_ＩにＩＤを割り当てるために、ＭＲ−ＢＳは親ノードＲＳ_ＤのＩＤを２ビット左シフトさせ、且つ２進数の“１０”（１０進数の２、自分の識別子ａ_３）を加えて、１０進数の１８を得る。同様に、ＲＳ_ＪのノードＩＤ１９は、親ノードのＩＤを２ビット左シフトさせ、且つ自身のａ_３識別子である３を加えることにより生成する。

子ノードの識別子の割り当て演算は、Ｎキャリー演算とすることができる。図５は多項式としてのＮキャリー演算の例示実施形態を示す。図５を参照すると、通信システム５００におけるネットワークノードのツリートポロジーの第ｋの子レベルの各子ノードは、ノードＩＤ＝（ａ_ｋ・Ｎ^ｋ−１＋ａ_ｋ−１・Ｎ^ｋ−２＋…＋ａ_２・Ｎ^１＋ａ_１・Ｎ^０）を有する。第１の子レベルの各子ノードのノードＩＤを多項式（ａ_１・Ｎ^０）により生成し、第２の子レベルの各子ノードのノードＩＤを多項式（ａ_２・Ｎ^１＋ａ_１・Ｎ^０）により生成し、第３の子レベルの各子ノードのノードＩＤを多項式（ａ_３・Ｎ^２＋ａ_２・Ｎ^１＋ａ_１・Ｎ^０）により生成し、第４の子レベルの各子ノードのノードＩＤを多項式（ａ_４・Ｎ^３＋ａ_３・Ｎ^２＋ａ_２・Ｎ^１＋ａ_１・Ｎ^０）により生成する。図３及び図４につき説明した前述の２桁のキャリー演算も、Ｎ＝２^ｉとする同じ多項式形式によって表現できる。

図６は、Ｎ＝５とする論理ツリートポロジー６００を有する通信システムにおける、Ｎキャリー演算を用いたノードＩＤ割り当ての例示実施形態を示す。第１の子レベルのノードＸ１のノードＩＤに、（２×５^０＝２）によって生成した、２を割り当てる。第１の子レベルのノードＸ２のノードＩＤに、（２×５^０＋４×５^１＝２２）によって生成した、２２を割り当てる。同じ多項式計算ルールに従って、ノードＸ３及びＸ４に、それぞれ（２×５^０＋４×５^１＋１×５^２＝４７）及び（２×５^０＋４×５^１＋１×５^２＋５×５^３＝６７２）によって生成した、４７及び６７２をそれぞれ割り当てる。この第ｋの子レベルの子ノードのＮキャリー演算は、親ノードＩＤにａ_ｋ・Ｎ^ｋ−１を加えることによって実行する。

図示したノードＩＤ割り当て実施形態の使用により、データのルーティング処理の間、子ノードのノードＩＤを利用することによりデータを送信できる。データを転送する場合には、データの宛先ノードＩＤを各子ノードのノードＩＤに対してチェックし、各子ノードは、宛先ノードＩＤがこの各子ノードのノードＩＤである場合に、他の処理のためにデータを受け取り、宛先ノードＩＤが子ノードのノードＩＤではないかどうかに応じて、データを下位の子ノードに転送するか、又はデータを破棄するかを決定する。

図７は通信システムにおけるデータ送信の例を示すフローチャートである。ノードが宛先ノードＩＤを有するデータパケットを受信する（ステップ７０５）毎に、その受信ノードはこの宛先ノードＩＤから自分自身のノードＩＤを引算する（ステップ７１０）。引算の結果が０の場合（ステップ７１５のｙｅｓ）には、ノードは他の処理のためにデータパケットを受け取る（受信する）（ステップ７２０）。引算の結果が０ではない場合（ステップ７１５のｎｏ）、引算の結果をモジュロＮ^ｋ演算にかける（ステップ７２５）。モジュロ演算の結果が０である場合（ステップ７３０のｙｅｓ）には、ノードはデータを自分の下位の子ノードに転送する（ステップ７３５）。そうでなければ（ステップ７３０のｎｏ）、データを破棄する（ステップ７４０）。

再び図６を参照し、ツリートポロジー６００を用いて、ＩＤ６７２を有するノードＸ４に向けられるデータパケットに対する、データの転送例について説明する。ノードＸ１がパケットを受信した場合には、ＩＤ６７２から２を引算する。引算の結果は０ではないため、ノードＸ１は、パケットの宛先ではないと判断し、引算の結果をモジュロＮ^ｋ演算にかける。この計算後、モジュロの結果は０であるため、ノードＸ１はパケットを下位ノードに転送する。ノードＸ２及びＸ３では同じプロセスを実行する。ノードＸ４が転送データパケットを受信したとき、ノードＸ４はパケットのノードＩＤから自分のＩＤを引算する。この引算の結果は０であるため、Ｘ４は他の処理のためにパケットを受信する。他の子ノードが転送データパケットを受信した場合には、モジュロ計算後に、モジュロの結果が０ではないため、それらのノードはこのデータパケットを破棄する。

図４に示すルーティングと組合わせたＩＤの割り当てにより、各ＲＳは自分のレベルを決定し、データパケットの転送を効率的に行うことができる。上り方向のフレームに対しては、各ＲＳは、自分自身のＩＤをｉビット右シフトすることにより、容易に自分の親ＩＤを決定できる。例えば、ＲＳ_ＭのＩＤは０１ ００ １０ １０であるため、ＲＳ_Ｍは、自分のＩＤを２ビット右シフトすることにより、自分の親ノードＲＳ_ＩのＩＤは００ ０１ ００ １０であるとわかる。親ノードから受信した下り方向のフレームに対しては、子ノードは、図７に示すようなプロセスに従って、このフレームを受け取るか、転送するか、又は破棄するかを決定する必要がある。

図８は図４に示した本発明の例示実施形態によるデータ送信処理に対するフローチャートを示す。子ノードのノードＩＤは、各子ノードの親ノードＩＤをｉビット左シフトし、さらに、各ノードＩＤの下位ｉビットに異なる値を設定することにより割り当て、ここに、Ｎ＝２^ｉとする。データパケットを受信するノードは、このパケットの宛先ノードＩＤが自分自身のＩＤと等しいかどうか判定し（ステップ８１０）、これら２つのＩＤが同じ場合にはこのフレームを受け取る（ステップ８１０のｙｅｓ）。この２つのＩＤが同じではない場合には、ノードは宛先ノードＩＤにｉビットの右シフトを実行し（ステップ８２０）、この結果を自分自身のＩＤと等しいか判定する（ステップ８３０）。シフトした宛先ノードＩＤがノード自身のＩＤと同じである場合には、ノードはこのフレームを自分の下位の子ノードに転送する（ステップ８３０のｙｅｓ）。そうでなければ、右シフトを続行し、判定（ステップ８２０、８３０）をｊ回（ステップ８４０，８５０）行う。ここでｊ＝Ｈ−ｋとし、Ｈは子レベルの最大数とし、ｋはデータ送信ノードの子レベルとする。全ての判定が失敗すれば、ノードはフレームを破棄する（ステップ８４０のｙｅｓ）。同様に、子ノードのノードＩＤを、各子ノードの親ノードＩＤをｉビット右シフトし、さらに、各ノードＩＤの上位ｉビットに異なる値を設定するすることによって割り当てる場合には、データ送信処理中、ステップ８２０は右シフトの代わりに左シフトを行い、他のステップは同じ手順のままである。

ノードが通信システムに出入りする場合には、これに応じてネットワークトポロジーも変化し、論理ツリートポロジーにおける子レベルへの接続の仕方が変わることからして、ノードＩＤは更新する必要がある。例えば、ある実装では、ネットワークは子ノードの最大数を識別し、その最大数をブロードキャスト又は転送し、各子ノードのノードＩＤを更新する。

ルートノード又はネットワークコントロール能力を備える他の指定ノードは、この識別及びブロードキャスト／転送を処理でき、各子ノードは、ブロードキャスト又は転送された情報に基づいて、自分自身のＩＤを更新して、例えば、識別子｛ａ_１，ａ_２，・・・，ａ_ｋ｝の組を識別するか、又は、例えば、旧のノードＩＤをビットシフトすることにより、自分自身の旧のノードＩＤのデコーディングすることに基づいて、ノードＩＤを生成することができる。ブロードキャスト又は転送処理の間、この情報は、子ノードに格納するか、又はネットワークコントロール能力を備える、少なくとも１つのノードによって転送することができる。

図２ｂに示すように、本発明が開示するネットワークシステムの通信ノード２２０は１つ以上の以下の要素、即ち、様々な処理及び方法を実行するコンピュータプログラム命令を実行するように構成された少なくとも１つの中央処理部（ＣＰＵ）２２１、情報及びコンピュータプログラム命令にアクセスし、且つこれらを格納をするように構成したランダムアクセスメモリ（ＲＡＭ）２２２及びリードオンリーメモリ（ＲＯＭ）２２３、情報及びデータを格納するメモリ２２４又は１つ以上のデータベース２２５、１つ以上のアンテナ２２６、１つ以上のＩ／Ｏ装置２２７、及び、１つ以上のインタフェース２２８等を含むことができる。これらの各要素は当該技術分野で周知であるため、これ以上の説明はしない。

図９は、親ノードから他のノードへのノードハンドオーバーを示す、例示ネットワーク９００を示す。ルートノード又は他のノードは、ハンドオーバーノードに、例えば｛ａ_１ ^’，ａ_２ ^’，・・・，ａ_ｋ ^’｝のような、ノードＩＤ生成用の新たな情報を転送するためのコントロール能力を有する。この情報を受信後、ハンドオーバーノードは新しいノードＩＤを生成できる。図９では、ＩＤ９０のノードが、親ノード１９から他の親ノード３７へのハンドオーバーを行う。ルートノードは、新しい情報、例えば｛１，３，３，１｝をハンドオーバーノードに転送する。結果として、ハンドオーバーノードは、ハンドオーバー処理中又はその後に、自分の新しいノードＩＤを更新できる。

図１０ａは本発明の実施形態による、論理ツリーにマップしたメッシュトポロジーネットワーク１０００の例である。図１０ｂは、接続ノードを有するネットワーク１０００内で形成される３つの論理ツリーを示す。この３つの論理ツリーは、ノード１をルートノードとして有する論理ツリー１（１０１０）、ノード８をルートノードとして有する論理ツリー２（１０２０）、及びノード９をルートノードとして有する論理ツリー３（１０３０）である。一般に、外部ネットワークへのゲートウェイを、論理ツリーネットワークにおけるルートノードとする。

論理ツリーネットワーク内でパケットを転送する場合には、このパケットは、図１０ａに示すように、少なくとも論理ツリープレフィックスフィールド１００１及び宛先ノードＩＤフィールド１００２を有する、宛先アドレスを含むことができる。宛先アドレスを有するパケットを受信したノードは、データを転送するための論理ツリープレフィックスを割り当てる。例えば、ノード４がノード９に論理ツリー１（１０１０）を使ってパケットを送信するためには、ノード４は論理ツリープレフィックスフィールドに１を割り当て、論理ツリー１でのノード９のＩＤを宛先アドレスの宛先ノードＩＤフィールドに割り当てる。

異なる論理ツリーではプレフィックス及びノードＩＤが異なるため、論理ツリー間でパケットを転送するためには、各ノードはプレフィックス及びノードＩＤを変更することにより宛先アドレスを変換することができる。図１１は、論理ツリー間でのデータ送信を示す、例示概略図１１００を示す。ノード８がノード９にパケットを送信するために、ノード８は、論理ツリープレフィックスフィールドに１を挿入し、論理ツリー１でのノード９のノードＩＤを、宛先ノードＩＤフィールドとして挿入し、論理ツリー１を介してパケットを転送する。このパケットを受信した場合に、ノード７は、パケット転送決定用の従来のアルゴリズム利用して、このパケットを、論理ツリー２を介して転送することを決定する。ノード７は論理プレフィックスフィールドを２に変更し、論理ツリー１でのノード９のノードＩＤ（９^１にて表記）を論理ツリー２でのノード９のノードＩＤ（９^２にて表記）に変換する。このパケットは、ノードＩＤ９^２、及び論理ツリー２のデータ送信アルゴリズムを用いて、ノード９に転送される。このように、本システムは、１つ以上の論理ツリーを利用してデータを送信するのに、異なる論理ツリープレフィックス値を割り当て、元の論理ツリーにおける宛先ノードＩＤを、割り当てられた論理ツリーにおけるノードＩＤに変換できる。

図１２はデータ送信フローチャートの例を示す。ネットワークノードがパケットを受信して、パケットの宛先アドレスを抽出した場合（ステップ１２１０）、そのノードは論理ツリープレフィックスを識別し（ステップ１２２０）、且つ論理ツリーでの宛先ノードＩＤを識別する（ステップ１２３０）。宛先ノードＩＤの識別後、受信ノードは、パケットを他の論理ツリーに転送するか、しないかを決定する（ステップ１２４０）。受信ノードは、他の論理ツリーでパケットを転送しない場合には（ステップ１２４０のｎｏ）、識別された論理ツリーで割り当てられたＩＤ（データ送信アルゴリズム）に基づく、任意の従来又は任意の上記した、データ送信方法を使用できる（ステップ１２５０）。ノードが他の倫理ツリーでパケットを送信すると決定した場合には（ステップ１２４０のｙｅｓ）、このノードは、新しい論理ツリーをあるアルゴリズムによって割り当てた後に（ステップ１２６０）、論理ツリープレフィックスフィールドに新たな論理ツリーを示し、宛先ノードＩＤを新しい論理ツリーでのノードＩＤに変換する（ステップ１２７０）。新しい論理ツリーのデータ転送アルゴリズムを利用して、新しい経路を介してパケットを転送する（ステップ１２８０）。

当業者にとっては、通信システムにおける信号干渉を減少するために、システム及び方法において、様々な修正例及び派生例が作成可能であることは明らかである。記載及び例は例示としてのみ解するべきであり、開示された実施形態の真の範囲は、添付の特許請求の範囲およびその均等の範囲によって示されることを意図している。

マルチホップリレーネットワークのブロック図である。 論理ツリートポロジーの模範的な概略を示す図である。 通信ノードのブロック図の模範的な概略を示す図である。 特定の開示実施形態による、通信システムのネットワークノードＩＤ割り当てを示す図である。 図３で割り当てられたノードＩＤを２進数表記に広げた、ＩＤ割り当て動作を示す図である。 特定の開示実施形態による、多項式によるＮキャリー演算を利用する通信システムの、他のネットワークノードＩＤ割り当て例を示す図である。 特定の開示実施形態による、図５のＮキャリー演算ノードＩＤ割り当て例を示す図である。 通信システムにおけるデータ転送用の例示プロセスを示すフローチャートである。 通信システムにおけるデータ転送用の他の例示プロセスを示すフローチャートである。 ネットワークノードのハンドオーバーを示す概略図である。 メッシュトポロジーネットワークを示す概略図である。 図１０ａのメッシュネットワークにおいて形成された論理ツリーを示す概略図である。 論理ツリー間におけるデータ送信を示す概略図である。 本発明の実施形態による、データ送信の例示フローチャートを示す図である。

Claims (112)

1. 送信ノード及び受信ノードとしての複数の通信ノードを有するネットワーク環境にてデータを送信する方法であって、
   前記方法は、
   決められた数ＮでのＮキャリー演算によって、前記複数の通信ノードから１つのノードＩＤを送受信グループの受信ノードに割り当てる第１のステップと、
   前記ノードＩＤを利用し、前記複数の通信ノード間で、前記送受信グループでの少なくとも１つの送信ノードから少なくとも１つの送受信グループの受信ノードへデータを送信する第２のステップとを含み、
   前記Ｎキャリー演算は、第１レベルの送信ノードの第１受信レベルから前記ノードＩＤを割り当てられた前記受信ノードまでの送受信経路に沿っている受信ノードの１組の識別子に基づいて行う演算であり、
   前記Ｎキャリー演算を、多項式ａ _ｋ ・Ｎ ^ｋ−１ ＋ａ _ｋ−１ ・Ｎ ^ｋ−２ ＋…＋ａ _２ ・Ｎ ^１ ＋ａ _１ ・Ｎ ^０ によって実行し、
   ａ _ｋ は、送信ノードに関連し、第ｋの受信レベルにおける各受信ノードの、前記各受信ノードを識別するための識別子であり、
   ｛ａ _１ ，ａ _２ ，・・・，ａ _ｋ−１ ，ａ _ｋ ｝は、第１のレベルの送信ノードの第１の受信レベルから、前記ノードＩＤが割り当てられている前記受信ノードへの、送受信経路に沿った受信ノードの一組の識別子である、データ送信方法。
2. 前記第１のステップの前に、前記送受信グループの前記複数の通信ノード間で、ルートノードと、１つ以上の子ノードとを指定し、論理ツリートポロジーを形成するステップをさらに含み、
   前記各子ノードは、０、又は１つ以上の他の子ノードの親ノードである、請求項１に記載の方法。
3. 前記第１のステップの前記決められた数Ｎは、前記論理ツリートポロジーの前記各ノードに接続される子ノードの最大数である、請求項２に記載の方法。
4. 前記第１のステップの前記ノードＩＤを割り当てることは、各親ノードが前記各子ノードを識別するために、前記論理ツリートポロジーの第ｋの子レベルにおける各子ノードに対して、親ノードに関連する識別子ａ_ｋを割り当てるステップを含む、請求項２に記載の方法。
5. 前記Ｎキャリー演算は、多項式ａ_ｋ・Ｎ^ｋ−１＋ａ_ｋ−１・Ｎ^ｋ−２＋…＋ａ_２・Ｎ^１＋ａ_１・Ｎ^０によって実行する演算であり、
   ｛ａ_１，ａ_２，・・・，ａ_ｋ−１，ａ_ｋ｝は、前記ルートノードの第１の子レベルから、前記ノードＩＤが割り当てられている前記子ノードへの、送受信経路に沿った子ノードの識別子の組である、請求項４に記載の方法。
6. 前記第１のステップの前記ノードＩＤを割り当てることは、各送信ノードが前記各受信ノードを識別するために、前記送受信グループの第ｋの受信レベルにおける前記各受信ノードに対して、送信ノードに関連する識別子ａ_ｋを割り当てるステップを含む、請求項１に記載の方法。
7. 前記Ｎキャリー演算は、多項式ａ_ｋ・Ｎ^ｋ−１＋ａ_ｋ−１・Ｎ^ｋ−２＋…＋ａ_２・Ｎ^１＋ａ_１・Ｎ^０によって実行する演算であり、
   ｛ａ_１，ａ_２，・・・，ａ_ｋ−１，ａ_ｋ｝は、第１のレベルの送信ノードの第１の受信レベルから、前記ノードＩＤが割り当てられている受信ノードへの、送受信経路に沿った受信ノードの一組の識別子である、請求項６に記載の方法。
8. 前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項１に記載の方法。
9. 前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項２に記載の方法。
10. 前記決められた数Ｎは、前記論理ツリートポロジーの各ノードに接続する子ノードの最大数である、請求項９に記載の方法。
11. 前記第１のステップは、第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    親ノードＩＤをｉビット左シフトし、さらに、前記子レベルのそれぞれの子ノードに対して、前記シフトしたノードＩＤの下位ｉビットに異なる値を設定することによって実行し、
    前記第１の子レベルのノードのそれぞれのノードＩＤの下位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てるステップを含む、請求項９に記載の方法。
12. 前記第１のステップは、第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    親ノードＩＤをｉビット左シフトし、さらに、前記シフトしたノードＩＤの下位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって実行し、
    前記第１の子レベルのノードの各ノードのノードＩＤに０から２^ｉ−１の範囲から選択した整数を割り当てるステップを含む、請求項９に記載の方法。
13. 前記第１のステップは、前記各子ノードのノードＩＤを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てるステップを含む、請求項１２に記載の方法。
14. 前記第１のステップは、第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    親ノードＩＤをｉビット右シフトし、さらに、前記子レベルのそれぞれの子ノードに対して、前記シフトしたノードＩＤの上位ｉビットに異なる値を設定することによって実行し、
    前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てるステップを含む、請求項９に記載の方法。
15. 前記第１のステップは、第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって実行し、
    前記第１の子レベルのノードの各ノードのノードＩＤを、上位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって割り当てるステップを含む、請求項９に記載の方法。
16. 前記第１のステップは、前記各子ノードの前記ノードＩＤを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てるステップを含む、請求項１５に記載の方法。
17. 前記第１のステップは、前記識別子ａ_ｋに、１からＮの範囲から選択した数を割り当てるステップを含む、請求項４に記載の方法。
18. 前記第１のステップは、前記識別子ａ_ｋに、１からＮの範囲から選択した数を割り当てるステップを含む、請求項５に記載の方法。
19. 前記第１のステップの前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項４に記載の方法。
20. 前記第１のステップは、第１の子レベルの各ノードの識別子ａ_ｋに、１からＮ−１の範囲から選択した整数を割り当てるステップと、
    他の子レベルの各ノードの識別子ａ_ｋに、０からＮ−１の範囲から選択した整数を割り当てるステップと、を含む、請求項１９に記載の方法。
21. 前記第１のステップは、前記各子ノードの前記識別子ａ_ｋを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てるステップを含む、請求項２０に記載の方法。
22. 前記第１のステップは、前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    前記各子ノードの親ノードＩＤをｉビット左シフトし、さらに、前記シフトしたノードＩＤの下位ｉビットに前記各子ノードの前記識別子ａ_ｋを設定することによって実行し、
    前記第１の子レベルの各前記ノードの前記ノードＩＤに、自分自身の識別子ａ_１を割り当てるステップを含む、請求項２０に記載の方法。
23. 前記第１のステップは、前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    前記各子ノードの親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに前記各子ノードの識別子ａ_ｋを設定することによって実行し、
    前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに自分自身の識別子ａ_１を設定することによって、前記第１の子レベルの各ノードのノードＩＤを割り当てるステップを含む、請求項２０に記載の方法。
24. 前記第１のステップの前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項５に記載の方法。
25. 前記第１のステップは、前記第１の子レベルの各ノードの識別子ａ_ｋに、１からＮ−１の範囲から選択した整数を割り当てるステップと、
    他の子レベルの各ノードの識別子ａ_ｋに、０からＮ−１の範囲から選択した整数を割り当てるステップと、を含む、請求項２４に記載の方法。
26. 前記第１のステップは、前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    前記各子ノードの親ノードＩＤをｉビット左シフトし、さらに、下位ｉビットに前記各子ノードの識別子ａ_ｋを設定することによって実行し、
    第１の子レベルの各ノードの前記ノードＩＤに自分自身の識別子ａ_１を割り当てるステップを含む、請求項２５に記載の方法。
27. 前記第１のステップは、前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    前記各子ノードの親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに前記各子ノードの識別子ａ_ｋを設定することによって実行し、
    前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに自分自身の識別子ａ_１を設定することによって、前記第１の子レベルの各ノードのノードＩＤを割り当てるステップを含む、請求項２５に記載の方法。
28. 前記第２のステップは、各ノードによる前記データの宛先ＩＤと自分のノードＩＤとの送信データ判定ステップを含み、前記ＩＤが自分のノードＩＤである場合に、前記データを他の処理のために受け取る、請求項１記載の方法。
29. 前記判定ステップを、前記宛先ＩＤから自分のノードＩＤを引算することにより実行する、請求項２８に記載の方法。
30. 前記宛先ＩＤが自分のノードＩＤではない場合に、
    各ノードによる前記送信データの前記判定ステップが、
    前記引算結果がゼロではなく、前記引算結果のモジュロＮ^ｋの結果がゼロである場合に、第ｋの受信レベルの下位受信ノードにデータを転送するステップを含む、請求項２９に記載の方法。
31. 前記宛先ＩＤが自分のノードＩＤではない場合に、
    各ノードによる前記送信データの前記判定ステップが、
    前記引算結果がゼロではなく、前記引算結果をモジュロＮ^ｋにかけた結果がゼロではない場合に、前記データを破棄するステップを含む、請求項３０に記載の方法。
32. 前記第２のステップは、各ノードによる前記データの宛先ＩＤと自分のノードＩＤとの送信データ判定ステップを含み、前記ＩＤが自分のノードＩＤである場合に、前記データを他の処理のために受け取る、請求項５記載の方法。
33. 前記判定ステップを、前記宛先ＩＤから自分のノードＩＤを引算することにより実行する、請求項３２に記載の方法。
34. 各ノードによる前記送信データの前記判定ステップが、
    前記引算結果がゼロではなく、前記引算結果のモジュロＮ^ｋの結果がゼロである場合に、
    第ｋの受信レベルの下位の子ノードにデータを転送するステップを含む、請求項３３に記載の方法。
35. 各ノードによる前記送信データの前記判定ステップが、
    前記引算結果がゼロではなく、前記引算結果をモジュロＮ^ｋにかけた結果がゼロではない場合に、
    前記データを破棄するステップを含む、請求項３４に記載の方法。
36. 前記第２のステップは、各ノードによる前記データの宛先ＩＤと自分のノードＩＤとの送信データ判定ステップを含み、前記ＩＤが自分のノードＩＤである場合に、前記データを他の処理のために受け取る、請求項１１記載の方法。
37. 各ノードによる前記送信データの前記判定ステップが、前記宛先ＩＤが自分のノードＩＤではない場合に、
    前記宛先ＩＤをｉビット右シフトするステップと、
    前記シフトしたＩＤを判定するステップと、
    前記シフトしたＩＤが自分のノードＩＤである場合に、前記データを下位の子ノードに転送するステップと、
    前記右シフトと前記シフトしたＩＤの判定とをｊ回繰返すステップと、を含み、
    ｊは子レベルの最大数とデータ送信ノードの子レベルとの間の差と等しい、請求項３６に記載の方法。
38. 前記宛先ＩＤが自分のＩＤではない場合に、
    各ノードによる前記送信データの判定ステップが、
    前記データが転送されない場合に前記データを破棄するステップを含む、請求項３７に記載の方法。
39. 前記第２のステップは、各ノードによる前記データの宛先ＩＤと自分のノードＩＤとの送信データ判定ステップを含み、前記ＩＤが自分のノードＩＤである場合に、前記データを他の処理のために受け取る、請求項１４記載の方法。
40. 各ノードによる前記送信データの判定ステップが、前記宛先ＩＤが自分のノードＩＤではない場合に、
    前記宛先ＩＤをｉビット左シフトするステップと、
    前記シフトしたＩＤを判定するステップと、
    前記シフトしたＩＤが自分のノードＩＤである場合に前記データを下位の子ノードに転送するステップと、
    前記左シフトと前記シフトしたＩＤの判定とをｊ回繰返すステップと、を含み、
    ｊは子レベルの最大数とデータ送信ノードの子レベルとの間の差と等しい、請求項３９に記載の方法。
41. 前記宛先ＩＤが自分のＩＤではない場合に、
    各ノードによる前記送信データの判定ステップが、前記データが転送されない場合に、
    前記データを破棄するステップを含む、請求項４０に記載の方法。
42. 前記第１のステップの前記ノードＩＤを割り当てることは、前記送受信グループの各ノードの前記ノードＩＤを、前記複数の通信ノードの少なくとも１つによって割り当てるステップを含む、請求項１に記載の方法。
43. 前記第１のステップの前記ノードＩＤを割り当てることは、前記送受信グループの前記各ノードのノードＩＤを、前記複数の通信ノードの少なくとも１つの、ネットワークコントロール能力を有するノードによって割り当てるステップを含む、請求項１に記載の方法。
44. 前記第１のステップの前記ノードＩＤを割り当てることは、前記送受信グループの前記各ノードのノードＩＤを、前記送受信グループ自身の前記各ノードによって割り当てるステップを含む、請求項１に記載の方法。
45. 前記第１のステップの前記Ｎキャリー演算は、前記複数の通信ノードの少なくとも１つによって、前記決められた数Ｎを識別するステップと、
    前記複数の通信ノードの少なくとも１つによって、前記識別した数Ｎを前記送受信グループにブロードキャスト又は転送するステップとを含む、請求項１に記載の方法。
46. 前記第１のステップの前記ノードＩＤを割り当てることは、前記送受信グループの前記各ノードのノードＩＤを、前記複数の通信ノードの少なくとも１つによって割り当てるステップを含む、請求項４５に記載の方法。
47. 前記第１のステップの前記ノードＩＤを割り当てることは、前記送受信グループの前記各ノードのノードＩＤを、前記複数の通信ノードの少なくとも１つの、ネットワークコントロール能力のあるノードによって割り当てるステップを含む、請求項４５に記載の方法。
48. 前記第１のステップの前記ノードＩＤを割り当てることは、前記送受信グループの前記各ノードのノードＩＤを、前記送受信グループ自身の前記各ノードによって割り当てるステップを含む、請求項４５に記載の方法。
49. 前記第１のステップの前記数Ｎを決めることは、前記複数の通信ノードの少なくとも１つによって、子ノードの前記最大数Ｎを識別するステップと、
    前記複数の通信ノードの少なくとも１つによって、前記識別した最大数Ｎを前記論理ツリートポロジーにブロードキャスト又は転送するステップとを含む、請求項３に記載の方法。
50. 前記第１のステップの前記ノードＩＤを割り当てることは、前記各子ノードのノードＩＤを、前記複数の通信ノードの少なくとも１つによって割り当てるステップを含む、請求項４９に記載の方法。
51. 前記第１のステップの前記ノードＩＤを割り当てることは、前記各子ノードのノードＩＤを、前記各親ノードによって割り当てるステップを含む、請求項４９に記載の方法。
52. 前記第１のステップの前記ノードＩＤを割り当てることは、前記各子ノードのノードＩＤを、前記各子ノードによって割り当てるステップを含む、請求項４９に記載の方法。
53. 前記第１のステップの前記ノードＩＤを割り当てることは、前記各子ノードのノードＩＤを、前記ルートノードによって割り当てるステップを含む、請求項４９に記載の方法。
54. 前記第１のステップの前に、前記複数通信ノードの少なくとも１つが、前記決められた数Ｎと、前記各子ノードの転送経路に沿った子ノードの前記一組の識別子｛ａ_１，ａ_２，・・・，ａ_ｋ−１，ａ_ｋ｝とを記録するステップをさらに含む、請求項５記載の方法。
55. 前記第１のステップの前に、前記各子ノードが、前記決められた数Ｎと、自分の転送経路に沿った子ノードの前記一組の識別子｛ａ_１，ａ_２，・・・，ａ_ｋ−１，ａ_ｋ｝とを記録するステップをさらに含む、請求項５記載の方法。
56. 前記第１のステップの前に、前記複数通信ノードの少なくとも１つが、子ノードの前記最大数を記録するステップをさらに含む、請求項３に記載の方法。
57. 前記第１のステップの前に、前記各子ノードが、子ノードの前記最大数を記録するステップをさらに含む、請求項３に記載の方法。
58. 前記第１のステップの前に、前記複数通信ノードの少なくとも１つが、数ｉ及び子レベルの前記最大数を記録するステップをさらに含む、請求項９に記載の方法。
59. 前記第１のステップの前に、前記各子ノードが、数ｉ及び自分の子レベルの数を記録するステップをさらに含む、請求項９に記載の方法。
60. 前記第１のステップの前に、前記各子ノードが、子レベルの最大数を記録するステップをさらに含む、請求項５９に記載の方法。
61. 前記第１のステップは、ａ_ｋ・Ｎ^ｋ−１を自分の親ノードＩＤに加えることにより第ｋ子レベルの子ノードのＮキャリー演算を実行し、第1の子レベルの各ノードの前記識別子ａ_ｋに１からＮの範囲から選んだ整数を割り当てるステップを含む、請求項１７記載の方法。
62. 前記論理ツリートポロジーを形成するステップは、１つ以上の論理ツリーを形成し、
    前記送信するデータは、論理ツリープレフィックスフィールドと、前記論理ツリーフィールドでの宛先ノードＩＤとを有する宛先アドレスを含む、請求項２に記載の方法。
63. 前記論理ツリートポロジーを形成するステップは、２つ以上の論理ツリーを形成し、
    前記第２のステップは、
    前記宛先アドレスに別の論理ツリープレフィックス値を割り当てるステップと、
    元の論理ツリーでの前記宛先ノードＩＤを割り当てられた論理ツリーでの宛先アドレスのノードＩＤへと変換して、前記２つ以上の論理ツリーを利用してデータを送信するステップと、を含む、請求項６２記載の方法。
64. 相互接続してネットワーク環境を形成する送信ノード及び受信ノードとしての複数の通信ノードを含み、
    決められた数ＮでのＮキャリー演算によって、前記複数の通信ノードから１つのノードＩＤを送受信グループの受信ノードに割り当て、
    送受信グループの少なくとも１つの前記送信ノードは、ノードＩＤを利用することによって、前記送受信グループの少なくとも１つの前記受信ノードにデータを送信し、
    前記Ｎキャリー演算は、第１レベルの送信ノードの第１受信レベルから前記ノードＩＤを割り当てられた前記受信ノードまでの送受信経路に沿っている受信ノードの１組の識別子に基づいて行う演算であり、
    前記Ｎキャリー演算を、多項式ａ _ｋ ・Ｎ ^ｋ−１ ＋ａ _ｋ−１ ・Ｎ ^ｋ−２ ＋…＋ａ _２ ・Ｎ ^１ ＋ａ _１ ・Ｎ ^０ によって実行し、
    ａ _ｋ は、送信ノードに関連し、第ｋの受信レベルにおける各受信ノードの、前記各受信ノードを識別するための識別子であり、
    ｛ａ _１ ，ａ _２ ，・・・，ａ _ｋ−１ ，ａ _ｋ ｝は、第１のレベルの送信ノードの第１の受信レベルから、前記ノードＩＤが割り当てられている前記受信ノードへの、送受信経路に沿った受信ノードの一組の識別子である、通信システム。
65. 前記送受信グループの前記複数の通信ノード間を接続するルートノードと1つ以上の子ノードによって論理ツリートポロジーを形成し、
    前記各子ノードは、０、又は１つ以上の他の子ノードの親ノードである、請求項６４記載のシステム。
66. 前記決められた数Ｎは、前記論理ツリートポロジーの各ノードに接続される子ノードの最大数である、請求項６５に記載のシステム。
67. 前記Ｎキャリー演算を、多項式ａ_ｋ・Ｎ^ｋ−１＋ａ_ｋ−１・Ｎ^ｋ−２＋…＋ａ_２・Ｎ^１＋ａ_１・Ｎ^０によって実行し、
    ａ_ｋは、親ノードに関連し、第ｋの子レベルにおける、前記各子ノードを識別するための各子ノードの識別子であり、
    ｛ａ_１，ａ_２，・・・，ａ_ｋ−１，ａ_ｋ｝は、第１のレベルのルートノードの第１の子レベルから、前記ノードＩＤを割り当てた子ノードへの、送受信経路に沿った子ノードの一組の識別子である、請求項６５に記載のシステム。
68. 前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項６４に記載のシステム。
69. 前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項６５に記載のシステム。
70. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    親ノードＩＤをｉビット左シフトし、さらに、前記子レベルのそれぞれの前記子ノードに対して、前記シフトしたノードＩＤの下位ｉビットに異なる値を設定することによって実行し、
    前記第１の子レベルのノードのそれぞれの前記ノードＩＤの下位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てる、請求項６９に記載のシステム。
71. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    親ノードＩＤをｉビット左シフトし、さらに、下位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって実行し、
    前記第１の子レベルのノードの各ノードのノードＩＤに０から２^ｉ−１の範囲から選択した整数を割り当てる、請求項６９に記載のシステム。
72. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    親ノードＩＤをｉビット右シフトし、さらに、前記子レベルのそれぞれの前記子ノードに対して、前記シフトしたノードＩＤの上位ｉビットに異なる値を設定することによって実行し、
    前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てる、請求項６９に記載のシステム。
73. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    親ノードＩＤをｉビット右シフトし、さらに、上位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって実行し、
    前記第１の子レベルのノードの各ノードのノードＩＤを、上位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって割り当てる、請求項６９に記載のシステム。
74. 前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項６７に記載のシステム。
75. 第１の子レベルの各ノードの識別子ａ_ｋに、１からＮ−１の範囲から選択した整数を割り当て、
    他の子レベルの各ノードの識別子ａ_ｋに、０からＮ−１の範囲から選択した整数を割り当てる、請求項７４に記載のシステム。
76. 前記各子ノードの識別子ａ_ｋを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てる、請求項７５に記載のシステム。
77. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    前記各子ノードの親ノードＩＤをｉビット左シフトし、さらに、下位ｉビットに前記各子ノードの識別子ａ_ｋを設定することによって実行し、
    前記第１の子レベルの各ノードのノードＩＤに、自分自身の識別子ａ_１を割り当てる、請求項７５に記載のシステム。
78. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
    前記各子ノードの親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに前記各子ノードの識別子ａ_ｋを設定することによって実行し、
    前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに自分自身の識別子ａ_１を設定することによって、前記第１の子レベルの各ノードのノードＩＤを割り当てる、請求項７５に記載のシステム。
79. 前記各受信ノードのノードＩＤを、前記受信ノードが自分の送信ノードに関連付けられる順番に従って割り当てる、請求項６４に記載のシステム。
80. 前記複数の通信ノードの少なくとも１つが、子ノードの前記最大数を識別する、請求項６６に記載のシステム。
81. 前記複数の通信ノードの少なくとも１つが、前記識別した最大数を前記ツリートポロジーにブロードキャスト又は転送する、請求項８０に記載のシステム。
82. 前記複数の通信ノードの少なくとも１つが、前記各受信ノードのノードＩＤを割り当てる、請求項６４に記載のシステム。
83. 前記複数の通信ノードの少なくとも１つが、前記各受信ノードのノードＩＤを割り当てる、請求項６５に記載のシステム。
84. 前記ルートノードが、前記各子ノードのノードＩＤを割り当てる、請求項８３に記載のシステム。
85. 前記各子ノードが、自分のノードＩＤを割り当てる、請求項８３に記載のシステム。
86. 前記システムがハンドオーバー動作を処理する場合に、前記複数の通信ノードの少なくとも１つが、ハンドオーバーノードに対するノードＩＤを割り当てる、請求項６４に記載のシステム。
87. 前記システムがハンドオーバー動作を処理する場合に、前記複数の通信ノードの少なくとも１つが、ハンドオーバーノードに対するノードＩＤを割り当てる、請求項６５に記載のシステム。
88. 前記ルートノードが、前記ハンドオーバーノードのノードＩＤを割り当てる、請求項８７に記載のシステム。
89. 前記システムがハンドオーバー動作を処理する場合に、ハンドオーバーノードが自分のノードＩＤを割り当てる、請求項６４に記載のシステム。
90. 前記システムは１つ以上の論理ツリーを形成し、
    前記送信するデータは、論理ツリープレフィックスフィールドと、前記論理ツリーフィールドでの宛先ノードＩＤとを有する宛先アドレスを含む、請求項６５に記載のシステム。
91. １つ以上の論理ツリーを形成し、
    前記システムは、前記宛先アドレスに別の論理ツリープレフィックス値を割り当て、且つ、元の論理ツリーでの前記宛先ノードＩＤを割り当てられた論理ツリーでの宛先アドレスのノードＩＤへと変換して、前記１つ以上の論理ツリーを利用してデータを送信するようにした、請求項９０記載のシステム。
92. ネットワークの送受信グループにおける送信ノード及び受信ノードとしての複数の通信ノードであって、
    決められた数ＮでのＮキャリー演算によって、前記複数の通信ノードから１つのノードＩＤを送受信グループの受信ノードに割り当て、
    送受信グループの少なくとも１つの前記送信ノードは、ノードＩＤを利用することによって、前記送受信グループの少なくとも１つの前記受信ノードにデータを送信し、
    前記通信ノードは、
    データ及び命令を格納する少なくとも１つのメモリと、
    このメモリにアクセスするように構成した少なくとも１つのプロセッサであって、
    前記命令を実行する場合に、
    ノードＩＤを利用して通信データを送信するように構成され、前記Ｎキャリー演算は、第１レベルの送信ノードの第１受信レベルから前記ノードＩＤを割り当てられた前記受信ノードまでの送受信経路に沿っている受信ノードの１組の識別子に基づいて行う演算であり、
    前記Ｎキャリー演算が、多項式ａ _ｋ ・Ｎ ^ｋ−１ ＋ａ _ｋ−１ ・Ｎ ^ｋ−２ ＋…＋ａ _２ ・Ｎ ^１ ＋ａ _１ ・Ｎ ^０ によって実行され、
    ａ _ｋ は、送信ノードに関連し、第ｋの受信レベルにおける各受信ノードの、前記各受信ノードを識別するための識別子であり、
    ｛ａ _１ ，ａ _２ ，・・・，ａ _ｋ−１ ，ａ _ｋ ｝は、第１のレベルの送信ノードの第１の受信レベルから、前記ノードＩＤが割り当てられる前記受信ノードへの、送受信経路に沿った受信ノードの一組の識別子である、通信ノード。
93. 前記ネットワークは、前記送受信グループの前記複数の通信ノード間を接続するルートノードと1つ以上の子ノードとによって論理ツリートポロジーを形成し、
    前記各子ノードは、０、又は１つ以上の他の子ノードの親ノードである、請求項９２に記載の通信ノード。
94. 前記決められた数Ｎは、前記論理ツリートポロジーの前記各ノードに接続される子ノードの最大数である、請求項９３に記載の通信ノード。
95. 前記Ｎキャリー演算が、多項式ａ_ｋ・Ｎ^ｋ−１＋ａ_ｋ−１・Ｎ^ｋ−２＋…＋ａ_２・Ｎ^１＋ａ_１・Ｎ^０によって実行され、
    ａ_ｋは、親ノードに関連し、第ｋの子レベルにおける、前記各子ノードを識別するための各子ノードの識別子であり、
    ｛ａ_１，ａ_２，・・・，ａ_ｋ−１，ａ_ｋ｝は、第１のレベルのルートノードの第１の子レベルから、前記ノードＩＤが割り当てられる前記子ノードへの、送受信経路に沿った子ノードの一組の識別子である、請求項９３に記載の通信ノード。
96. 前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項９２に記載の通信ノード。
97. 前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項９３に記載の通信ノード。
98. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
    親ノードＩＤをｉビット左シフトし、さらに、前記子レベルのそれぞれの前記子ノードに対して、前記シフトしたノードＩＤの下位ｉビットに異なる値を設定することによって実行し、
    前記第１の子レベルのノードのそれぞれの前記ノードＩＤの下位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードの前記ノードＩＤを割り当てる、請求項９７に記載の通信ノード。
99. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
    親ノードＩＤをｉビット左シフトし、さらに、下位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって実行され、
    前記第１の子レベルのノードの各ノードのノードＩＤに０から２^ｉ−１の範囲から選択した整数を割り当てる、請求項９７に記載の通信ノード。
100. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
     親ノードＩＤをｉビット右シフトし、さらに、前記子レベルのそれぞれの前記子ノードに対して、前記シフトしたノードＩＤの上位ｉビットに異なる値を設定することによって実行され、
     前記第１の子レベルのノードのそれぞれの前記ノードＩＤの上位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てる、請求項９７に記載の通信ノード。
101. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
     親ノードＩＤをｉビット右シフトし、さらに、上位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって実行され、
     前記第１の子レベルのノードの各ノードの前記ノードＩＤを、上位ｉビットに０から２^ｉ−１の範囲から選択した整数を設定することによって割り当てる、請求項９７に記載の通信ノード。
102. 前記決められた数Ｎは２ⁱであり、ｉは０以上の整数である、請求項９５に記載の通信ノード。
103. 第１の子レベルの各ノードの識別子ａ_ｋに、１からＮ−１の範囲から選択した整数を割り当て、
     他の子レベルの各ノードの識別子ａ_ｋに、０からＮ−１の範囲から選択した整数を割り当てる、請求項１０２に記載の通信ノード。
104. 前記各子ノードの前記識別子ａ_ｋを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てる、請求項１０３に記載の通信ノード。
105. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
     前記各子ノードの親ノードＩＤをｉビット左シフトし、さらに、下位ｉビットに前記各子ノードの前記識別子ａ_ｋを設定することによって実行され、
     前記第１の子レベルの各ノードの前記ノードＩＤに、自分自身の識別子ａ_１を割り当てる、請求項１０３に記載の通信ノード。
106. 前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
     前記各子ノードの親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに前記各子ノードの識別子ａ_ｋを設定することによって実行され、
     前記第１の子レベルのノードのそれぞれの前記ノードＩＤの上位ｉビットに自分自身の識別子ａ_１を設定することによって、前記第１の子レベルの前記各ノードの前記ノードＩＤを割り当てる、請求項１０３に記載の通信ノード。
107. 前記各受信ノードの前記ノードＩＤを、前記受信ノードが自分の送信ノードに関連付けられる順番に従って割り当てる、請求項９２に記載の通信ノード。
108. 前記複数の通信ノードの少なくとも１つが、子ノードの前記最大数を識別する、請求項９４に記載の通信ノード。
109. 前記複数の通信ノードの少なくとも１つが、前記識別した最大数を前記ツリートポロジーにブロードキャスト又は転送する、請求項１０８に記載の通信ノード。
110. 前記複数の通信ノードの少なくとも１つが、前記各受信ノードのノードＩＤを割り当てる、請求項９２に記載の通信ノード。
111. 前記複数の通信ノードの少なくとも１つが、前記各受信ノードのノードＩＤを割り当てる、請求項９３に記載の通信ノード。
112. 前記通信ノードが、自分のノードＩＤを割り当てる、請求項９３に記載の通信ノード。

Images