(57)【要約】      （修正有）【課題】ノードＩＤを利用することによって、ネットワーク環境にてデータを送信する方法を提供する。【解決手段】通信システムでネットワークデータを送信する方法及びシステムは、ノードＩＤを利用することによって、前記複数の通信ノード間で、送受信グループの少なくとも１つの送信ノードから少なくとも１つの受信ノードへデータを送信する手段を含み、前記ノードＩＤは、決められた数ＮでのＮキャリー演算によって割り当てる。【選択図】図４
2008228274.tif 000002
【特許請求の範囲】
【請求項１】
複数の通信ノードを有するネットワーク環境にてデータを送信する方法であって、
前記方法は、
ノードＩＤを利用することによって、前記複数の通信ノード間で、少なくとも１つの送信ノードから少なくとも１つの送受信グループの受信ノードへデータを送信するステップを含み、
前記ノードＩＤを、決められた数ＮでのＮキャリー演算（Ｎ−ｃａｒｒｙ  ｏｐｅｒａｔｉｏｎ）によって割り当てる、データ送信方法。
【請求項２】
前記送受信グループの前記複数の通信ノード間で、ルートノードと、１つ以上の子ノードとを指定し、論理ツリートポロジーを形成するステップをさらに含み、
前記各子ノードは、０、又は１つ以上の他の子ノードの親ノードである、請求項１に記載の方法。
【請求項３】
前記決められた数Ｎは、前記論理ツリートポロジーの前記各ノードに接続される子ノードの最大数である、請求項２に記載の方法。
【請求項４】
各親ノードが前記各子ノードを識別するために、前記論理ツリートポロジーの第ｋの子レベルにおける各子ノードに対して、親ノードに関連する識別子ａｋを割り当てるステップをさらに含む、請求項２に記載の方法。
【請求項５】
前記Ｎキャリー演算を、多項式ａｋ・Ｎｋ−１＋ａｋ−１・Ｎｋ−２＋…＋ａ２・Ｎ１＋ａ１・Ｎ０によって実行し、
｛ａ１，ａ２，・・・，ａｋ−１，ａｋ｝は、前記ルートノードの第１の子レベルから、前記ノードＩＤが割り当てられている前記子ノードへの、送受信経路に沿った子ノードの識別子の組である、請求項４に記載の方法。
【請求項６】
各送信ノードが前記各受信ノードを識別するために、前記送受信グループの第ｋの受信レベルにおける前記各受信ノードに対して、送信ノードに関連する識別子ａｋを割り当てるステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記Ｎキャリー演算を、多項式ａｋ・Ｎｋ−１＋ａｋ−１・Ｎｋ−２＋…＋ａ２・Ｎ１＋ａ１・Ｎ０によって実行し、
｛ａ１，ａ２，・・・，ａｋ−１，ａｋ｝は、第１のレベルの送信ノードの第１の受信レベルから、前記ノードＩＤが割り当てられている受信ノードへの、送受信経路に沿った受信ノードの一組の識別子である、請求項６に記載の方法。
【請求項８】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項１に記載の方法。
【請求項９】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項２に記載の方法。
【請求項１０】
前記決められた数Ｎは、前記論理ツリートポロジーの各ノードに接続する子ノードの最大数である、請求項９に記載の方法。
【請求項１１】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
親ノードＩＤをｉビット左シフトし、さらに、前記子レベルのそれぞれの子ノードに対して、前記シフトしたノードＩＤの下位ｉビットに異なる値を設定することによって実行し、
前記第１の子レベルのノードのそれぞれのノードＩＤの下位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てる、請求項９に記載の方法。
【請求項１２】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
親ノードＩＤをｉビット左シフトし、さらに、前記シフトしたノードＩＤの下位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって実行し、
前記第１の子レベルのノードの各ノードのノードＩＤに０から２ｉ−１の範囲から選択した整数を割り当てる、請求項９に記載の方法。
【請求項１３】
前記各子ノードのノードＩＤを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てる、請求項１２に記載の方法。
【請求項１４】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
親ノードＩＤをｉビット右シフトし、さらに、前記子レベルのそれぞれの子ノードに対して、前記シフトしたノードＩＤの上位ｉビットに異なる値を設定することによって実行し、
前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てる、請求項９に記載の方法。
【請求項１５】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって実行し、
前記第１の子レベルのノードの各ノードのノードＩＤを、上位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって割り当てる、請求項９に記載の方法。
【請求項１６】
前記各子ノードの前記ノードＩＤを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てる、請求項１５に記載の方法。
【請求項１７】
前記識別子ａｋに、１からＮの範囲から選択した数を割り当てるステップをさらに含む、請求項４に記載の方法。
【請求項１８】
前記識別子ａｋに、１からＮの範囲から選択した数を割り当てるステップをさらに含む、請求項５に記載の方法。
【請求項１９】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項４に記載の方法。
【請求項２０】
第１の子レベルの各ノードの識別子ａｋに、１からＮ−１の範囲から選択した整数を割り当てるステップと、
他の子レベルの各ノードの識別子ａｋに、０からＮ−１の範囲から選択した整数を割り当てるステップと、をさらに含む、請求項１９に記載の方法。
【請求項２１】
前記各子ノードの前記識別子ａｋを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てるステップをさらに含む、請求項２０に記載の方法。
【請求項２２】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
前記各子ノードの親ノードＩＤをｉビット左シフトし、さらに、前記シフトしたノードＩＤの下位ｉビットに前記各子ノードの前記識別子ａｋを設定することによって実行し、
前記第１の子レベルの各前記ノードの前記ノードＩＤに、自分自身の識別子ａ１を割り当てる、請求項２０に記載の方法。
【請求項２３】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
前記各子ノードの親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに前記各子ノードの識別子ａｋを設定することによって実行し、
前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに自分自身の識別子ａ１を設定することによって、前記第１の子レベルの各ノードのノードＩＤを割り当てる、請求項２０に記載の方法。
【請求項２４】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項５に記載の方法。
【請求項２５】
前記第１の子レベルの各ノードの識別子ａｋに、１からＮ−１の範囲から選択した整数を割り当てるステップと、
他の子レベルの各ノードの識別子ａｋに、０からＮ−１の範囲から選択した整数を割り当てるステップと、をさらに含む、請求項２４に記載の方法。
【請求項２６】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
前記各子ノードの親ノードＩＤをｉビット左シフトし、さらに、下位ｉビットに前記各子ノードの識別子ａｋを設定することによって実行し、
第１の子レベルの各ノードの前記ノードＩＤに自分自身の識別子ａ１を割り当てる、請求項２５に記載の方法。
【請求項２７】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
前記各子ノードの親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに前記各子ノードの識別子ａｋを設定することによって実行し、
前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに自分自身の識別子ａ１を設定することによって、前記第１の子レベルの各ノードのノードＩＤを割り当てる、請求項２５に記載の方法。
【請求項２８】
前記送信ステップは、各ノードによる前記データの宛先ＩＤと自分のノードＩＤとの送信データ判定ステップをさらに含み、前記ＩＤが自分のノードＩＤである場合に、前記データを他の処理のために受け取る、請求項１記載の方法。
【請求項２９】
前記判定ステップを、前記宛先ＩＤから自分のノードＩＤを引算することにより実行する、請求項２８に記載の方法。
【請求項３０】
前記宛先ＩＤが自分のノードＩＤではない場合に、
各ノードによる前記送信データの前記判定ステップが、
前記引算結果がゼロではなく、前記引算結果のモジュロＮｋの結果がゼロである場合に、第ｋの受信レベルの下位受信ノードにデータを転送するステップをさらに含む、請求項２９に記載の方法。
【請求項３１】
前記宛先ＩＤが自分のノードＩＤではない場合に、
各ノードによる前記送信データの前記判定ステップが、
前記引算結果がゼロではなく、前記引算結果をモジュロＮｋにかけた結果がゼロではない場合に、前記データを破棄するステップをさらに含む、請求項３０に記載の方法。
【請求項３２】
前記送信ステップは、各ノードによる前記データの宛先ＩＤと自分のノードＩＤとの送信データ判定ステップをさらに含み、前記ＩＤが自分のノードＩＤである場合に、前記データを他の処理のために受け取る、請求項５記載の方法。
【請求項３３】
前記判定ステップを、前記宛先ＩＤから自分のノードＩＤを引算することにより実行する、請求項３２に記載の方法。
【請求項３４】
各ノードによる前記送信データの前記判定ステップが、
前記引算結果がゼロではなく、前記引算結果のモジュロＮｋの結果がゼロである場合に、
第ｋの受信レベルの下位の子ノードにデータを転送するステップをさらに含む、請求項３３に記載の方法。
【請求項３５】
各ノードによる前記送信データの前記判定ステップが、
前記引算結果がゼロではなく、前記引算結果をモジュロＮｋにかけた結果がゼロではない場合に、
前記データを破棄するステップをさらに含む、請求項３４に記載の方法。
【請求項３６】
前記送信ステップは、各ノードによる前記データの宛先ＩＤと自分のノードＩＤとの送信データ判定ステップをさらに含み、前記ＩＤが自分のノードＩＤである場合に、前記データを他の処理のために受け取る、請求項１１記載の方法。
【請求項３７】
各ノードによる前記送信データの前記判定ステップが、前記宛先ＩＤが自分のノードＩＤではない場合に、
前記宛先ＩＤをｉビット右シフトするステップと、
前記シフトしたＩＤを判定するステップと、
前記シフトしたＩＤが自分のノードＩＤである場合に、前記データを下位の子ノードに転送するステップと、
前記右シフトと前記シフトしたＩＤの判定とをｊ回繰返すステップと、をさらに含み、
ｊは子レベルの最大数とデータ送信ノードの子レベルとの間の差と等しい、請求項３６に記載の方法。
【請求項３８】
前記宛先ＩＤが自分のＩＤではない場合に、
各ノードによる前記送信データの判定ステップが、
前記データが転送されない場合に前記データを破棄するステップをさらに含む、請求項３７に記載の方法。
【請求項３９】
前記送信ステップは、各ノードによる前記データの宛先ＩＤと自分のノードＩＤとの送信データ判定ステップをさらに含み、前記ＩＤが自分のノードＩＤである場合に、前記データを他の処理のために受け取る、請求項１４記載の方法。
【請求項４０】
各ノードによる前記送信データの判定ステップが、前記宛先ＩＤが自分のノードＩＤではない場合に、
前記宛先ＩＤをｉビット左シフトするステップと、
前記シフトしたＩＤを判定するステップと、
前記シフトしたＩＤが自分のノードＩＤである場合に前記データを下位の子ノードに転送するステップと、
前記左シフトと前記シフトしたＩＤの判定とをｊ回繰返すステップと、をさらに含み、
ｊは子レベルの最大数とデータ送信ノードの子レベルとの間の差と等しい、請求項３９に記載の方法。
【請求項４１】
前記宛先ＩＤが自分のＩＤではない場合に、
各ノードによる前記送信データの判定ステップが、  前記データが転送されない場合に、前記データを破棄するステップをさらに含む、請求項４０に記載の方法。
【請求項４２】
前記送受信グループの各ノードの前記ノードＩＤを、前記複数の通信ノードの少なくとも１つによって割り当てるステップをさらに含む、請求項１に記載の方法。
【請求項４３】
前記送受信グループの前記各ノードのノードＩＤを、前記複数の通信ノードの少なくとも１つの、ネットワークコントロール能力を有するノードによって割り当てるステップをさらに含む、請求項１に記載の方法。
【請求項４４】
前記送受信グループの前記各ノードのノードＩＤを、前記送受信グループ自身の前記各ノードによって割り当てるステップをさらに含む、請求項１に記載の方法。
【請求項４５】
前記複数の通信ノードの少なくとも１つによって、前記決められた数Ｎを識別するステップと、
前記複数の通信ノードの少なくとも１つによって、前記識別した数Ｎを前記送受信グループにブロードキャスト又は転送するステップとをさらに含む、請求項１に記載の方法。
【請求項４６】
前記送受信グループの前記各ノードのノードＩＤを、前記複数の通信ノードの少なくとも１つによって割り当てるステップをさらに含む、請求項４５に記載の方法。
【請求項４７】
前記送受信グループの前記各ノードのノードＩＤを、前記複数の通信ノードの少なくとも１つの、ネットワークコントロール能力のあるノードによって割り当てるステップをさらに含む、請求項４５に記載の方法。
【請求項４８】
前記送受信グループの前記各ノードのノードＩＤを、前記送受信グループ自身の前記各ノードによって割り当てるステップをさらに含む、請求項４５に記載の方法。
【請求項４９】
前記複数の通信ノードの少なくとも１つによって、子ノードの前記最大数を識別するステップと、
前記複数の通信ノードの少なくとも１つによって、前記識別した最大数を前記論理ツリートポロジーにブロードキャスト又は転送するステップとをさらに含む、請求項３に記載の方法。
【請求項５０】
前記各子ノードのノードＩＤを、前記複数の通信ノードの少なくとも１つによって割り当てるステップをさらに含む、請求項４９に記載の方法。
【請求項５１】
前記各子ノードのノードＩＤを、前記各親ノードによって割り当てるステップをさらに含む、請求項４９に記載の方法。
【請求項５２】
前記各子ノードのノードＩＤを、前記各子ノードによって割り当てるステップをさらに含む、請求項４９に記載の方法。
【請求項５３】
前記各子ノードのノードＩＤを、前記ルートノードによって割り当てるステップをさらに含む、請求項４９に記載の方法。
【請求項５４】
前記複数通信ノードの少なくとも１つが、前記決められた数Ｎと、前記各子ノードの転送経路に沿った子ノードの前記一組の識別子｛ａ１，ａ２，・・・，ａｋ−１，ａｋ｝とを記録するステップをさらに含む、請求項５記載の方法。
【請求項５５】
前記各子ノードが、前記決められた数Ｎと、自分の転送経路に沿った子ノードの前記一組の識別子｛ａ１，ａ２，・・・，ａｋ−１，ａｋ｝とを記録するステップをさらに含む、請求項５記載の方法。
【請求項５６】
前記複数通信ノードの少なくとも１つが、子ノードの前記最大数を記録するステップをさらに含む、請求項３に記載の方法。
【請求項５７】
前記各子ノードが、子ノードの前記最大数を記録するステップをさらに含む、請求項３に記載の方法。
【請求項５８】
前記複数通信ノードの少なくとも１つが、数ｉ及び子レベルの前記最大数を記録するステップをさらに含む、請求項９に記載の方法。
【請求項５９】
前記各子ノードが、数ｉ及び自分の子レベルの数を記録するステップをさらに含む、請求項９に記載の方法。
【請求項６０】
前記各子ノードが、子レベルの最大数を記録するステップをさらに含む、請求項５９に記載の方法。
【請求項６１】
ａｋ・Ｎｋ−１を自分の親ノードＩＤに加えることにより第ｋ子レベルの子ノードのＮキャリー演算を実行し、第1の子レベルの各ノードの前記識別子ａｋに１からＮの範囲から選んだ整数を割り当てる、請求項１７記載の方法。
【請求項６２】
１つ以上の論理ツリーを形成し、
前記送信するデータは、論理ツリープレフィックスフィールドと、前記論理ツリーフィールドでの宛先ノードＩＤとを有する宛先アドレスを含む、請求項２に記載の方法。
【請求項６３】
２つ以上の論理ツリーを形成し、
前記送信ステップは、
前記宛先アドレスに別の論理ツリープレフィックス値を割り当てるステップと、及び、
元の論理ツリーでの前記宛先ノードＩＤを割り当てられた論理ツリーでの宛先アドレスのノードＩＤへと変換して、前記２つ以上の論理ツリーを利用してデータを送信するステップと、をさらに含む、
請求項６２記載の方法。
【請求項６４】
相互接続してネットワーク環境を形成する複数の通信ノードを含み、
前記ネットワークは、送受信グループの少なくとも１つの送信ノードと、少なくとも１つの受信ノードとを含み、かつ、
前記少なくとも１つの送信ノードは、ノードＩＤを利用することによって、前記少なくとも１つの受信ノードにデータを送信し、
前記ノードＩＤを、決められた数ＮでのＮキャリー演算によって割り当てる、通信システム。
【請求項６５】
前記送受信グループの前記複数の通信ノード間を接続するルートノードと1つ以上の子ノードによって形成する論理ツリートポロジーをさらに含み、
前記各子ノードは、０、又は１つ以上の他の子ノードの親ノードである、請求項６４記載のシステム。
【請求項６６】
前記決められた数Ｎは、前記論理ツリートポロジーの各ノードに接続される子ノードの最大数である、請求項６５に記載のシステム。
【請求項６７】
前記Ｎキャリー演算を、多項式ａｋ・Ｎｋ−１＋ａｋ−１・Ｎｋ−２＋…＋ａ２・Ｎ１＋ａ１・Ｎ０によって実行し、
ａｋは、送信ノードに関連し、第ｋの受信レベルにおける各受信ノードの、前記各受信ノードを識別するための識別子であり、
｛ａ１，ａ２，・・・，ａｋ−１，ａｋ｝は、第１のレベルの送信ノードの第１の受信レベルから、前記ノードＩＤが割り当てられている前記受信ノードへの、送受信経路に沿った受信ノードの一組の識別子である、請求項６４に記載のシステム。
【請求項６８】
前記Ｎキャリー演算を、多項式ａｋ・Ｎｋ−１＋ａｋ−１・Ｎｋ−２＋…＋ａ２・Ｎ１＋ａ１・Ｎ０によって実行し、
ａｋは、親ノードに関連し、第ｋの子レベルにおける、前記各子ノードを識別するための各子ノードの識別子であり、
｛ａ１，ａ２，・・・，ａｋ−１，ａｋ｝は、第１のレベルのルートノードの第１の子レベルから、前記ノードＩＤを割り当てた子ノードへの、送受信経路に沿った子ノードの一組の識別子である、請求項６５に記載のシステム。
【請求項６９】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項６４に記載のシステム。
【請求項７０】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項６５に記載のシステム。
【請求項７１】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
親ノードＩＤをｉビット左シフトし、さらに、前記子レベルのそれぞれの前記子ノードに対して、前記シフトしたノードＩＤの下位ｉビットに異なる値を設定することによって実行し、
前記第１の子レベルのノードのそれぞれの前記ノードＩＤの下位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てる、請求項７０に記載のシステム。
【請求項７２】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
親ノードＩＤをｉビット左シフトし、さらに、下位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって実行し、
前記第１の子レベルのノードの各ノードのノードＩＤに０から２ｉ−１の範囲から選択した整数を割り当てる、請求項７０に記載のシステム。
【請求項７３】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
親ノードＩＤをｉビット右シフトし、さらに、前記子レベルのそれぞれの前記子ノードに対して、前記シフトしたノードＩＤの上位ｉビットに異なる値を設定することによって実行し、
前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てる、請求項７０に記載のシステム。
【請求項７４】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
親ノードＩＤをｉビット右シフトし、さらに、上位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって実行し、
前記第１の子レベルのノードの各ノードのノードＩＤを、上位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって割り当てる、請求項７０に記載のシステム。
【請求項７５】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項６８に記載のシステム。
【請求項７６】
第１の子レベルの各ノードの識別子ａｋに、１からＮ−１の範囲から選択した整数を割り当て、
他の子レベルの各ノードの識別子ａｋに、０からＮ−１の範囲から選択した整数を割り当てる、請求項７５に記載のシステム。
【請求項７７】
前記各子ノードの識別子ａｋを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てる、請求項７６に記載のシステム。
【請求項７８】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
前記各子ノードの親ノードＩＤをｉビット左シフトし、さらに、
下位ｉビットに前記各子ノードの識別子ａｋを設定することによって実行し、
前記第１の子レベルの各ノードのノードＩＤに、自分自身の識別子ａ１を割り当てる、請求項７６に記載のシステム。
【請求項７９】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算を、
前記各子ノードの親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに前記各子ノードの識別子ａｋを設定することによって実行し、
前記第１の子レベルのノードのそれぞれのノードＩＤの上位ｉビットに自分自身の識別子ａ１を設定することによって、前記第１の子レベルの各ノードのノードＩＤを割り当てる、請求項７６に記載のシステム。
【請求項８０】
前記各受信ノードのノードＩＤを、前記受信ノードが自分の送信ノードに関連付けられる順番に従って割り当てる、請求項１２に記載のシステム。
【請求項８１】
前記複数の通信ノードの少なくとも１つが、子ノードの前記最大数を識別する、請求項６６に記載のシステム。
【請求項８２】
前記複数の通信ノードの少なくとも１つが、前記識別した最大数を前記ツリートポロジーにブロードキャスト又は転送する、請求項８１に記載のシステム。
【請求項８３】
前記複数の通信ノードの少なくとも１つが、前記各受信ノードのノードＩＤを割り当てる、請求項６４に記載のシステム。
【請求項８４】
前記複数の通信ノードの少なくとも１つが、前記各受信ノードのノードＩＤを割り当てる、請求項６５に記載のシステム。
【請求項８５】
前記ルートノードが、前記各子ノードのノードＩＤを割り当てる、請求項８４に記載のシステム。
【請求項８６】
前記各子ノードが、自分のノードＩＤを割り当てる、請求項８４に記載のシステム。
【請求項８７】
前記システムがハンドオーバー動作を処理する場合に、前記複数の通信ノードの少なくとも１つが、ハンドオーバーノードに対するノードＩＤを割り当てる、請求項６４に記載のシステム。
【請求項８８】
前記システムがハンドオーバー動作を処理する場合に、前記複数の通信ノードの少なくとも１つが、ハンドオーバーノードに対するノードＩＤを割り当てる、請求項６５に記載のシステム。
【請求項８９】
前記ルートノードが、前記ハンドオーバーノードのノードＩＤを割り当てる、請求項８８に記載のシステム。
【請求項９０】
前記システムがハンドオーバー動作を処理する場合に、ハンドオーバーノードが自分のノードＩＤを割り当てる、請求項６４に記載のシステム。
【請求項９１】
前記システムは１つ以上の論理ツリーを形成し、
前記送信するデータは、論理ツリープレフィックスフィールドと、前記論理ツリーフィールドでの宛先ノードＩＤとを有する宛先アドレスを含む、請求項６５に記載のシステム。
【請求項９２】
１つ以上の論理ツリーを形成し、
前記システムは、前記宛先アドレスに別の論理ツリープレフィックス値を割り当て、且つ、元の論理ツリーでの前記宛先ノードＩＤを割り当てられた論理ツリーでの宛先アドレスのノードＩＤへと変換して、前記１つ以上の論理ツリーを利用してデータを送信するようにした、請求項９１記載のシステム。
【請求項９３】
ネットワークの送受信グループにおける通信ノードであって、
前記ネットワークは、複数の通信ノード、及び、少なくとも１つの送信ノードと少なくとも１つの受信ノードとを含む送受信グループを有し、
前記通信ノードは、
データ及び命令を格納する少なくとも１つのメモリと、
このメモリにアクセスするように構成した少なくとも１つのプロセッサであって、
前記命令を実行する場合に、
ノードＩＤを利用して通信データを送信するように構成され、前記ノードＩＤは決められた数ＮでのＮキャリー演算によって割り当てられるようにした、少なくとも１つのプロセッサを備えている、通信ノード。
【請求項９４】
前記ネットワークは、前記送受信グループの前記複数の通信ノード間を接続するルートノードと1つ以上の子ノードとによって形成する論理ツリートポロジーをさらに有し、
前記各子ノードは、０、又は１つ以上の他の子ノードの親ノードである、請求項９３に記載の通信ノード。
【請求項９５】
前記決められた数Ｎは、前記論理ツリートポロジーの前記各ノードに接続される子ノードの最大数である、請求項９４に記載の通信ノード。
【請求項９６】
前記Ｎキャリー演算が、多項式ａｋ・Ｎｋ−１＋ａｋ−１・Ｎｋ−２＋…＋ａ２・Ｎ１＋ａ１・Ｎ０によって実行され、
ａｋは、送信ノードに関連し、第ｋの受信レベルにおける各受信ノードの、前記各受信ノードを識別するための識別子であり、
｛ａ１，ａ２，・・・，ａｋ−１，ａｋ｝は、第１のレベルの送信ノードの第１の受信レベルから、前記ノードＩＤが割り当てられる前記受信ノードへの、送受信経路に沿った受信ノードの一組の識別子である、請求項９３に記載の通信ノード。
【請求項９７】
前記Ｎキャリー演算が、多項式ａｋ・Ｎｋ−１＋ａｋ−１・Ｎｋ−２＋…＋ａ２・Ｎ１＋ａ１・Ｎ０によって実行され、
ａｋは、親ノードに関連し、第ｋの子レベルにおける、前記各子ノードを識別するための各子ノードの識別子であり、
｛ａ１，ａ２，・・・，ａｋ−１，ａｋ｝は、第１のレベルのルートノードの第１の子レベルから、前記ノードＩＤが割り当てられる前記子ノードへの、送受信経路に沿った子ノードの一組の識別子である、請求項９４に記載の通信ノード。
【請求項９８】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項９３に記載の通信ノード。
【請求項９９】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項９４に記載の通信ノード。
【請求項１００】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
親ノードＩＤをｉビット左シフトし、さらに、前記子レベルのそれぞれの前記子ノードに対して、前記シフトしたノードＩＤの下位ｉビットに異なる値を設定することによって実行し、
前記第１の子レベルのノードのそれぞれの前記ノードＩＤの下位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードの前記ノードＩＤを割り当てる、請求項９９に記載の通信ノード。
【請求項１０１】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
親ノードＩＤをｉビット左シフトし、さらに、下位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって実行され、
前記第１の子レベルのノードの各ノードのノードＩＤに０から２ｉ−１の範囲から選択した整数を割り当てる、請求項９９に記載の通信ノード。
【請求項１０２】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
親ノードＩＤをｉビット右シフトし、さらに、前記子レベルのそれぞれの前記子ノードに対して、前記シフトしたノードＩＤの上位ｉビットに異なる値を設定することによって実行され、
前記第１の子レベルのノードのそれぞれの前記ノードＩＤの上位ｉビットに異なる値を設定することによって、前記第１の子レベルのノードの各ノードのノードＩＤを割り当てる、請求項９９に記載の通信ノード。
【請求項１０３】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
親ノードＩＤをｉビット右シフトし、さらに、上位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって実行され、
前記第１の子レベルのノードの各ノードの前記ノードＩＤを、上位ｉビットに０から２ｉ−１の範囲から選択した整数を設定することによって割り当てる、請求項９９に記載の通信ノード。
【請求項１０４】
前記決められた数Ｎは２iであり、ｉは０以上の整数である、請求項９７に記載の通信ノード。
【請求項１０５】
第１の子レベルの各ノードの識別子ａｋに、１からＮ−１の範囲から選択した整数を割り当て、
他の子レベルの各ノードの識別子ａｋに、０からＮ−１の範囲から選択した整数を割り当てる、請求項１０４に記載の通信ノード。
【請求項１０６】
前記各子ノードの前記識別子ａｋを、前記子ノードが自分の親ノードに関連付けられる順番に従って割り当てる、請求項１０５に記載の通信ノード。
【請求項１０７】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
前記各子ノードの親ノードＩＤをｉビット左シフトし、さらに、
下位ｉビットに前記各子ノードの前記識別子ａｋを設定することによって実行され、
前記第１の子レベルの各ノードの前記ノードＩＤに、自分自身の識別子ａ１を割り当てる、請求項１０５に記載の通信ノード。
【請求項１０８】
前記第１の子レベル以外の各子レベルにおける子ノードの前記Ｎキャリー演算が、
前記各子ノードの親ノードＩＤをｉビット右シフトし、さらに、前記シフトしたノードＩＤの上位ｉビットに前記各子ノードの識別子ａｋを設定することによって実行され、
前記第１の子レベルのノードのそれぞれの前記ノードＩＤの上位ｉビットに自分自身の識別子ａ１を設定することによって、前記第１の子レベルの前記各ノードの前記ノードＩＤを割り当てる、請求項１０５に記載の通信ノード。
【請求項１０９】
前記各受信ノードの前記ノードＩＤを、前記受信ノードが自分の送信ノードに関連付けられる順番に従って割り当てる、請求項９３に記載の通信ノード。
【請求項１１０】
前記複数の通信ノードの少なくとも１つが、子ノードの前記最大数を識別する、請求項９５に記載の通信ノード。
【請求項１１１】
前記複数の通信ノードの少なくとも１つが、前記識別した最大数を前記ツリートポロジーにブロードキャスト又は転送する、請求項１１０に記載の通信ノード。
【請求項１１２】
前記複数の通信ノードの少なくとも１つが、前記各受信ノードのノードＩＤを割り当てる、請求項９３に記載の通信ノード。
【請求項１１３】
前記複数の通信ノードの少なくとも１つが、前記各受信ノードのノードＩＤを割り当てる、請求項９４に記載の通信ノード。
【請求項１１４】
前記通信ノードが、自分のノードＩＤを割り当てる、請求項９４に記載の通信ノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、２００７年１月８日出願の米国仮出願第６０／８７９０４７号と、２００７年２月１６日出願の米国仮出願第６０／９０１６７３号との権利を主張するものであり、両出願とも、いかなる目的に対しても、全体をここに参照により援用する。
本開示は、広くネットワークシステムに関し、特に、ネットワークデータの送信方法及びシステムに関する。
【背景技術】
【０００２】
通信システムでは、ネットワークノード（又はいわゆるホスト）は、自分のＩＤ又はアドレスを、静的又は動的に割り当てることができる。静的な設定では、ユーザは事前に利用可能なアドレスを知り、手動でそのアドレスを設定する必要がある。対照的に、自由度の高いマルチホップ環境では、ＩＥＥＥ８０２．１６ｊに記載されたタイプのように、オペレータ又はユーザに手動設定を実行させることは適切ではない。他の選択肢である動的設定は、ノードに自分のＩＤを動的に設定したり、集中サーバからＩＤを取得したりすることを可能にする。典型的な動的設定スキームでは、全ノードＩＤがランダムに割り当てられ、ノードが付加的なルーティング情報を交換又は維持し、且つルーティング経路を決定するようにするために、付加的なルーティングアルゴリズム又はルーティングテーブルが必要になる。
【０００３】
図１は模範的なマルチホップリレー（ＭＲ）ネットワーク１００を示す。ネットワーク１００では、マルチホップリレー基地局ＢＳ（ＭＲ−ＢＳ）１０２がルートノードとして動作し、リレー局（ＲＳ）及び移動局（ＭＳ）が中間ノード又はリーフノードとして動作する。ネットワークセットアップ処理は、各ネットワークノードに識別子（又はアドレス）を割り当て、さらに、ノード間にルーティンググループを構築する。例えば、ＲＳ３（１０４）にはアドレスが割り当てられて、ＭＲ−ＢＳからＲＳ４（１０６）に向かうパケットの転送を担い、さらに、ＲＳ１（１０８）は、ＲＳ３に向かうＭＲ−ＢＳから受信したパケットを破棄する。このようなルーティング情報は各ＲＳのルーティングテーブルに保持して、中間ノードがネットワークに出入りする場合に、最新のルーティング情報を更新し得るようにすることができる。
【０００４】
２つの例でルーティングテーブルの活用を示す。米国特許第６１９２０５１号は、ネットワークパケットを転送するための、集中型ルーティングテーブル及び分散型転送テーブルにおける、複数レベルのツリーデータ構造を開示している。各データ構造の各レベルは、受信パケットにあるネットワークアドレスの、別々のフィールドと関連付けられる。米国特許第６９３４２５２号は、ルーティングテーブルのエントリに格納された親ノードの情報を用いる、バイナリネットワークアドレス検索を開示している。可変長のプレフィックスは、ネットワークアドレス転送テーブルに格納される。各プレフィックスは、転送テーブル中のエントリに対応する。転送テーブルの各エントリは、バイナリツリーにおける各エントリの親ノードに関する経路情報を含む。
【０００５】
ノード識別は、ルーティングテーブルを保持せずに実行できる。米国特許第６６１８７５５号は、ネットワークのノードによって表されるネットワーク内のアドレスの範囲によって、自動的に、ネットワークにおけるサブネットを識別するソフトウェア機能を開示している。これらのアドレスは、それぞれ、順序付けられた一定数のビット列を含む。
【０００６】
ネットワークのノード及びノード間のグループを表現するための素因数分解方法は、米国特許公報第２００６／０１９８３２０号、及びＩＥＥＥ  Ｃ８０２．１６ｊ−０６／１７１に記載されている。この方法の転送処理では、受信ノードは、パケットをどこに転送するかを決定するために、受信したパケットのＩＤ番号を因数分解する必要がある。他の方法は、ＩＥＥＥ  Ｃ８０２．１６ｊ−０７／０４８ｒ６に記載されている。この方法は、パケットをどこに転送するか又はパケットを破棄すべきかどうかを決定するために、ネットワークノードが、受信したアドレスの整数ブロックを識別する、連続整数ブロックのルーティング法に関する。
【発明の開示】
【０００７】
本開示による１つの模範的な態様は、ネットワークでデータを送信する方法である。
この方法は、
ネットワークの複数ノードの間で、ルートノードと１つ以上の子ノードとを接続することによって論理ツリートポロジーを形成するステップと、
決められた数ＮでのＮキャリー演算（Ｎ−ｃａｒｙｙ  ｏｐｅｒａｔｉｏｎ）によって各子ノードに対するノードＩＤを生成するステップと、
子ノードの生成したノードＩＤを利用してデータを送信するステップと、を含む。
【０００８】
本開示による他の模範的な態様は、通信システムである。
このシステムは、
相互接続してネットワークを形成する複数の通信ノードと、
複数の通信ノードの間に接続されて論理ツリートポロジーを形成するルートノードと１つ以上の子ノードとを含み、
各子ノードは決められた数ＮでのＮキャリー演算によって生成されたノードＩＤをそれらに割り当てており、
子ノードに割り当てられたノードＩＤを利用してデータを送信する。
【０００９】
また、本開示による他の模範的な態様は、ネットワークの送受信グループにおける通信ノードであり、このネットワークは複数のネットワークノードを含み、送受信グループは少なくとも１つの送信ノードと少なくとも１つの受信ノードとを含む。
この通信ノードは、
データ及び命令を格納する少なくとも１つのメモリと、
このメモリにアクセスするように構成された少なくとも１つのプロセッサであって、命令を実行する場合に、ノードＩＤを利用して通信データを送信するように構成され、このノードＩＤは決められた数ＮでのＮキャリー演算によって割り当てられるようにした少なくとも１つのプロセッサを備えている。
【００１０】
上記の一般的な記述及び以下の詳細な記述は、模範的な説明に過ぎず、請求項として本発明を限定するものではないことに留意されたい。
【発明を実施するための最良の形態】
【００１１】
通信システム環境では、データは、第１のレベルの送信ノードから第１のレベルの受信ノード又は次のレベルの受信ノードへの送受信経路を通じて、複数の通信ノードの送受信グループ間で送信できる。模範的な例として、ネットワークの複数のノードの間で、ネットワークノードの１つをルートノードとして指定し、１つ以上の他のノードを子ノードとして指定することによって、論理ツリーに基づくトポロジーによって複数のノードを含む、ネットワークを形成することができる。図２aは、本発明の実施形態による、このような論理ツリーに基づくトポロジーを有するように構成した、ネットワーク２００の概略例である。このツリーに基づくトポロジーは、最大数ｋの子レベルで構成される。より広範には、通信システムは、任意のネットワークトポロジー、例えばツリーに基づくネットワーク又はメッシュネットワークとすることができる。
【００１２】
ネットワーク２００の第ｋの子レベルの各子ノードには、この子ノードを識別するように各親ノードに対する識別子ａｋを割り当てる。ここで識別子ａｋは任意の数とすることができる。実装段階では、識別子ａｋは、０以上Ｎ以下の整数とすることができる。Ｎは決められた数とする。Ｎは、あらゆる任意の数、又はツリートポロジーの複数ノードのそれぞれに接続される子ノードの最大数に、予め決めることができる。ある実装では、決められた数Ｎは、システムにより動的に維持することができる。さらに、識別子ａｋは、ランダムシーケンスで、又は逐次割り当てることができる。一例として、各子ノードの識別子ａｋは、それがその親ノードと関連付けられる順番に従って割り当てることができる。
【００１３】
図２ａに示すように、ノードＳの子ノードは、ツリートポロジーの第ｋの子レベルを形成するように接続され、Ｎ個の子ノードがノードＳに接続される。本発明による一例示実施形態では、ノードＳの各子ノードの識別子ａｋに、１からＮの範囲で選んだ数を割り当てることができる。１つの実装では、ノードＴの識別子ａｋとしてＮ、ノードＵの識別子ａｋとしてＮ−１、・・・、ノードＹの識別子ａｋとして２、そして、ノードＺの識別子ａｋとして１を割り当てることができる。
【００１４】
本発明による他の例示実施形態では、代わりに、ノードＳの各子ノードの識別子ａｋに、０からＮ−１の範囲で選んだ数を割り当てることができ、例えば、ノードＴの識別子ａｋとして０を割り当て、ノードＵの識別子ａｋとして１を割り当て、・・・、ノードＹの識別子ａｋとしてＮ−２を割り当て、ノードＺの識別子ａｋとしてＮ−１を割り当てる。この例では、第１の子レベルの識別子ａ１を１〜Ｎ−１の中から割り当て、決められた数Ｎを２ｉとし、ここで、ｉは０以上の整数とする。
【００１５】
ルートノード、又はコントロール能力を備える少なくとも１つの他のノード、又は子ノードは、ノードＩＤを生成する情報を格納し、且つデータの転送又はネットワークの設定を管理できる。例えば、このような情報は、決められた数Ｎ、論理ツリートポロジーにおける親ノードの最大子ノード数、Ｎ＝２ｉの実装における整数ｉ、子ノードの識別子ａｋ、子ノードの子レベルｋ、ルートノードの第１の子レベルから子ノードへの、親−子経路に沿った一組の識別子｛ａ１，ａ２，・・・，ａｋ｝、及び、論理ツリーの最大子レベルＨ、を含むことができる。他の情報又はパラメータを用立てることもでき、随意格納すべき情報の種類は、実装の仕方に依存する。
【００１６】
本発明の実施形態は、任意のネットワーク通信システムにて実施することができる。例示目的用に、以下の段落では、マルチホップリレーネットワークを、決められた数Ｎのノードが存在し、ノードＩＤを利用してデータを送信する通信ネットワーク環境において、ノードＩＤを生成するデータ送信アルゴリズムを実証するための、例示通信システムとして説明する。
【００１７】
各子ノードのノードＩＤは、以下の段落で説明するように、２桁のキャリー演算（２’ｃａｒｒｙ  ｏｐｅｒａｔｉｏｎ）によって生成することができる。図３はマルチホップリレー基地局（ＭＲ−ＢＳ）及び多数のリレー局（ＲＳ）を含む、例示マルチホップリレーネットワーク３００を示す。移動局（ＭＳ、図示せず）は、ＭＲ−ＢＳかＲＳのいずれかに関連付けることができる。
【００１８】
ネットワーク３００は、ＭＲ−ＢＳルートノード３０２を含み、５段の子レベルを持つ論理ツリートポロジーを有するように構成する。第１の子レベルは、子ノードＲＳＡ（ａ１＝１、ＩＤ＝１）、ＲＳＢ（ａ１＝２、ＩＤ＝２）及びＲＳＣ（ａ１＝３、ＩＤ＝３）を含む。第２の子レベルは、ＲＳＡの子ノードであるＲＳＤ（ａ２＝０、ＩＤ＝４）、並びに、ＲＳＣの子ノードであるＲＳＥ（ａ２＝０、ＩＤ＝１２）及びＲＳＦ（ａ２＝１、ＩＤ＝１３）を含む。第３の子レベルは、ＲＳＤの以下の子ノード、すなわち、ＲＳＧ（ａ３＝０、ＩＤ＝１６）、ＲＳＨ（ａ３＝１、ＩＤ＝１７）、ＲＳＩ（ａ３＝２、ＩＤ＝１８）及びＲＳＪ（ａ３＝３、ＩＤ＝１９）を含む。第４の子レベルは、ＲＳＩの３つの子ノード、すなわち、ＲＳＫ（ａ４＝０、ＩＤ＝７２）、ＲＳＬ（ａ４＝１、ＩＤ＝７３）及びＲＳＭ（ａ４＝２、ＩＤ＝７４）を含む。第５の子レベルは、ＲＳＫの４つの子ノード、すなわち、ＲＳＮ（ａ５＝０、ＩＤ＝２８８）、ＲＳＯ（ａ５＝１、ＩＤ＝２８９）、ＲＳＰ（ａ５＝２、ＩＤ＝２９０）及びＲＳＱ（ａ５＝３、ＩＤ＝２９１）を含む。
【００１９】
ネットワーク３００の構成では、ｉ＝２であるため子ノードの決められた数Ｎ＝２ｉは２２＝４であり、最大子レベルＨは５、そして、第１の子レベル（ｋ＝１）の各ノードの識別子ａｋには、１から３の整数を順次割り当てる。この例では、各親ノードに関連する他の子レベルの各ノードの識別子ａｋには、０から３の整数を順次割り当てる。
【００２０】
図４は、ノードＩＤを２進数表記で表したネットワーク３００を示す。ネットワーク３００の論理ツリートポロジーの各子ノードのノードＩＤを２進数表記に変換することにより、ネットワーク３００のノードＩＤを生成するのに、４（２桁）のキャリー演算の実行が可能になる。さらに、ノードＩＤ割り当ての計算はビット演算で実現できる。
【００２１】
図４を参照すると、本発明の実施形態による例示実装として、各ノードＩＤの下位ｉビットの値を異なる値に設定することにより、第１の子レベルのノードのノードＩＤには１から２ｉ―１の範囲から選択した整数を割り当てる。他の子レベルのノードに対しては、コントロールノード、例えばＭＲ−ＢＳが、各子ノードの親ノードＩＤをｉビット左シフトし、さらに、０から２ｉ―１の範囲から整数を選択することにより下位ｉビットを異なる値に設定する。このプロセスは、新たに出現したノードに対するノードＩＤを生成したり、子ノードＲＳを接続したりするのに利用できる。例えば、図４のノードＲＳＧ及びＲＳＨの出現後に、新たにＲＳＩ及びＲＳＪがＲＳＤ（ＩＤ＝００  ００  ０１  ００）を親ノードとして次々に関連付けられるように出現するものとする。ＲＳＩにＩＤを割り当てるために、コントロールノードＭＲ−ＢＳは自分自身のＩＤを２ビット左シフトして００  ０１  ００  ００を得て、さらに、ノードＲＳＩはＲＳＤに属する３番目のノードであるため、下位２ビットを１０に設定して、００  ０１  ００  １０を得る。同様に、ノードＭＲ−ＢＳは、ノードＲＳＩにＩＤを割り当てた後、ノードＲＳＪに００  ０１  ００  １１を割り当てる。同様の方法を用い（図示せず）、各ノードＩＤの上位ｉビットの値を異なる値に設定することにより、第１の子レベルのノードのノードＩＤを整数で割り当てることもできる。他の子レベルのノードに対しては、コントロールノード、例えばＭＲ−ＢＳは、各子ノードの親ノードＩＤをｉビット右シフトして、さらに、０から２ｉ―１の範囲内で整数を選択することにより上位ｉビットを異なる値に設定する。
【００２２】
再び図３を参照すると、他の例示実施形態では、各子ノードに識別子ａｋを割り当てることができ、第１の子レベルの各ノードのノードＩＤには、自分自身の識別子ａ１を割り当てることができる。他の子レベルの各ノードのノードＩＤは、各子ノードの親ノードＩＤをｉビット左シフトし、且つ各子ノードの識別子ａｋに下位ｉビットを設定する演算を行うことで割り当てることができる。例えば、図３のＲＳＩとＲＳＪは共通の親ノードＲＳＤ（ＩＤ＝４）（００  ００  ０１  ００）と関連付けられる。ＲＳＩにＩＤを割り当てるために、ＭＲ−ＢＳは親ノードＲＳＤのＩＤを２ビット左シフトさせ、且つ２進数の“１０”（１０進数の２、自分の識別子ａ３）を加えて、１０進数の１８を得る。同様に、ＲＳＪのノードＩＤ１９は、親ノードのＩＤを２ビット左シフトさせ、且つ自身のａ３識別子である３を加えることにより生成する。
【００２３】
子ノードの識別子の割り当て演算は、Ｎキャリー演算とすることができる。図５は多項式としてのＮキャリー演算の例示実施形態を示す。図５を参照すると、通信システム５００におけるネットワークノードのツリートポロジーの第ｋの子レベルの各子ノードは、ノードＩＤ＝（ａｋ・Ｎｋ−１＋ａｋ−１・Ｎｋ−２＋…＋ａ２・Ｎ１＋ａ１・Ｎ０）を有する。第１の子レベルの各子ノードのノードＩＤを多項式（ａ１・Ｎ０）により生成し、第２の子レベルの各子ノードのノードＩＤを多項式（ａ２・Ｎ１＋ａ１・Ｎ０）により生成し、第３の子レベルの各子ノードのノードＩＤを多項式（ａ３・Ｎ２＋ａ２・Ｎ１＋ａ１・Ｎ０）により生成し、第４の子レベルの各子ノードのノードＩＤを多項式（ａ４・Ｎ３＋ａ３・Ｎ２＋ａ２・Ｎ１＋ａ１・Ｎ０）により生成する。図３及び図４につき説明した前述の２桁のキャリー演算も、Ｎ＝２ｉとする同じ多項式形式によって表現できる。
【００２４】
図６は、Ｎ＝５とする論理ツリートポロジー６００を有する通信システムにおける、Ｎキャリー演算を用いたノードＩＤ割り当ての例示実施形態を示す。第１の子レベルのノードＸ１のノードＩＤに、（２×５０＝２）によって生成した、２を割り当てる。第１の子レベルのノードＸ２のノードＩＤに、（２×５０＋４×５１＝２２）によって生成した、２２を割り当てる。同じ多項式計算ルールに従って、ノードＸ３及びＸ４に、それぞれ（２×５０＋４×５１＋１×５２＝４７）及び（２×５０＋４×５１＋１×５２＋５×５３＝６７２）によって生成した、４７及び６７２をそれぞれ割り当てる。この第ｋの子レベルの子ノードのＮキャリー演算は、親ノードＩＤにａｋ・Ｎｋ−１を加えることによって実行する。
【００２５】
図示したノードＩＤ割り当て実施形態の使用により、データのルーティング処理の間、子ノードのノードＩＤを利用することによりデータを送信できる。データを転送する場合には、データの宛先ノードＩＤを各子ノードのノードＩＤに対してチェックし、各子ノードは、宛先ノードＩＤがこの各子ノードのノードＩＤである場合に、他の処理のためにデータを受け取り、宛先ノードＩＤが子ノードのノードＩＤではないかどうかに応じて、データを下位の子ノードに転送するか、又はデータを破棄するかを決定する。
【００２６】
図７は通信システムにおけるデータ送信の例を示すフローチャートである。ノードが宛先ノードＩＤを有するデータパケットを受信する（ステップ７０５）毎に、その受信ノードはこの宛先ノードＩＤから自分自身のノードＩＤを引算する（ステップ７１０）。引算の結果が０の場合（ステップ７１５のｙｅｓ）には、ノードは他の処理のためにデータパケットを受け取る（受信する）（ステップ７２０）。引算の結果が０ではない場合（ステップ７１５のｎｏ）、引算の結果をモジュロＮｋ演算にかける（ステップ７２５）。モジュロ演算の結果が０である場合（ステップ７３０のｙｅｓ）には、ノードはデータを自分の下位の子ノードに転送する（ステップ７３５）。そうでなければ（ステップ７３０のｎｏ）、データを破棄する（ステップ７４０）。
【００２７】
再び図６を参照し、ツリートポロジー６００を用いて、ＩＤ６７２を有するノードＸ４に向けられるデータパケットに対する、データの転送例について説明する。ノードＸ１がパケットを受信した場合には、ＩＤ６７２から２を引算する。引算の結果は０ではないため、ノードＸ１は、パケットの宛先ではないと判断し、引算の結果をモジュロＮｋ演算にかける。この計算後、モジュロの結果は０であるため、ノードＸ１はパケットを下位ノードに転送する。ノードＸ２及びＸ３では同じプロセスを実行する。ノードＸ４が転送データパケットを受信したとき、ノードＸ４はパケットのノードＩＤから自分のＩＤを引算する。この引算の結果は０であるため、Ｘ４は他の処理のためにパケットを受信する。他の子ノードが転送データパケットを受信した場合には、モジュロ計算後に、モジュロの結果が０ではないため、それらのノードはこのデータパケットを破棄する。
【００２８】
図４に示すルーティングと組合わせたＩＤの割り当てにより、各ＲＳは自分のレベルを決定し、データパケットの転送を効率的に行うことができる。上り方向のフレームに対しては、各ＲＳは、自分自身のＩＤをｉビット右シフトすることにより、容易に自分の親ＩＤを決定できる。例えば、ＲＳＭのＩＤは０１  ００  １０  １０であるため、ＲＳＭは、自分のＩＤを２ビット右シフトすることにより、自分の親ノードＲＳＩのＩＤは００  ０１  ００  １０であるとわかる。親ノードから受信した下り方向のフレームに対しては、子ノードは、図７に示すようなプロセスに従って、このフレームを受け取るか、転送するか、又は破棄するかを決定する必要がある。
【００２９】
図８は図４に示した本発明の例示実施形態によるデータ送信処理に対するフローチャートを示す。子ノードのノードＩＤは、各子ノードの親ノードＩＤをｉビット左シフトし、さらに、各ノードＩＤの下位ｉビットに異なる値を設定することにより割り当て、ここに、Ｎ＝２ｉとする。データパケットを受信するノードは、このパケットの宛先ノードＩＤが自分自身のＩＤと等しいかどうか判定し（ステップ８１０）、これら２つのＩＤが同じ場合にはこのフレームを受け取る（ステップ８１０のｙｅｓ）。この２つのＩＤが同じではない場合には、ノードは宛先ノードＩＤにｉビットの右シフトを実行し（ステップ８２０）、この結果を自分自身のＩＤと等しいか判定する（ステップ８３０）。シフトした宛先ノードＩＤがノード自身のＩＤと同じである場合には、ノードはこのフレームを自分の下位の子ノードに転送する（ステップ８３０のｙｅｓ）。そうでなければ、右シフトを続行し、判定（ステップ８２０、８３０）をｊ回（ステップ８４０，８５０）行う。ここでｊ＝Ｈ−ｋとし、Ｈは子レベルの最大数とし、ｋはデータ送信ノードの子レベルとする。全ての判定が失敗すれば、ノードはフレームを破棄する（ステップ８４０のｙｅｓ）。同様に、子ノードのノードＩＤを、各子ノードの親ノードＩＤをｉビット右シフトし、さらに、各ノードＩＤの上位ｉビットに異なる値を設定するすることによって割り当てる場合には、データ送信処理中、ステップ８２０は右シフトの代わりに左シフトを行い、他のステップは同じ手順のままである。
【００３０】
ノードが通信システムに出入りする場合には、これに応じてネットワークトポロジーも変化し、論理ツリートポロジーにおける子レベルへの接続の仕方が変わることからして、ノードＩＤは更新する必要がある。例えば、ある実装では、ネットワークは子ノードの最大数を識別し、その最大数をブロードキャスト又は転送し、各子ノードのノードＩＤを更新する。
【００３１】
ルートノード又はネットワークコントロール能力を備える他の指定ノードは、この識別及びブロードキャスト／転送を処理でき、各子ノードは、ブロードキャスト又は転送された情報に基づいて、自分自身のＩＤを更新して、例えば、識別子｛ａ１，ａ２，・・・，ａｋ｝の組を識別するか、又は、例えば、旧のノードＩＤをビットシフトすることにより、自分自身の旧のノードＩＤのデコーディングすることに基づいて、ノードＩＤを生成することができる。ブロードキャスト又は転送処理の間、この情報は、子ノードに格納するか、又はネットワークコントロール能力を備える、少なくとも１つのノードによって転送することができる。
【００３２】
図２ｂに示すように、本発明が開示するネットワークシステムの通信ノード２２０は１つ以上の以下の要素、即ち、様々な処理及び方法を実行するコンピュータプログラム命令を実行するように構成された少なくとも１つの中央処理部（ＣＰＵ）２２１、情報及びコンピュータプログラム命令にアクセスし、且つこれらを格納をするように構成したランダムアクセスメモリ（ＲＡＭ）２２２及びリードオンリーメモリ（ＲＯＭ）２２３、情報及びデータを格納するメモリ２２４又は１つ以上のデータベース２２５、１つ以上のアンテナ２２６、１つ以上のＩ／Ｏ装置２２７、及び、１つ以上のインタフェース２２８等を含むことができる。これらの各要素は当該技術分野で周知であるため、これ以上の説明はしない。
【００３３】
図９は、親ノードから他のノードへのノードハンドオーバーを示す、例示ネットワーク９００を示す。ルートノード又は他のノードは、ハンドオーバーノードに、例えば｛ａ１’，ａ２’，・・・，ａｋ’｝のような、ノードＩＤ生成用の新たな情報を転送するためのコントロール能力を有する。この情報を受信後、ハンドオーバーノードは新しいノードＩＤを生成できる。図９では、ＩＤ９０のノードが、親ノード１９から他の親ノード３７へのハンドオーバーを行う。ルートノードは、新しい情報、例えば｛１，３，３，１｝をハンドオーバーノードに転送する。結果として、ハンドオーバーノードは、ハンドオーバー処理中又はその後に、自分の新しいノードＩＤを更新できる。
【００３４】
図１０ａは本発明の実施形態による、論理ツリーにマップしたメッシュトポロジーネットワーク１０００の例である。図１０ｂは、接続ノードを有するネットワーク１０００内で形成される３つの論理ツリーを示す。この３つの論理ツリーは、ノード１をルートノードとして有する論理ツリー１（１０１０）、ノード８をルートノードとして有する論理ツリー２（１０２０）、及びノード９をルートノードとして有する論理ツリー３（１０３０）である。一般に、外部ネットワークへのゲートウェイを、論理ツリーネットワークにおけるルートノードとする。
【００３５】
論理ツリーネットワーク内でパケットを転送する場合には、このパケットは、図１０ａに示すように、少なくとも論理ツリープレフィックスフィールド１００１及び宛先ノードＩＤフィールド１００２を有する、宛先アドレスを含むことができる。宛先アドレスを有するパケットを受信したノードは、データを転送するための論理ツリープレフィックスを割り当てる。例えば、ノード４がノード９に論理ツリー１（１０１０）を使ってパケットを送信するためには、ノード４は論理ツリープレフィックスフィールドに１を割り当て、論理ツリー１でのノード９のＩＤを宛先アドレスの宛先ノードＩＤフィールドに割り当てる。
【００３６】
異なる論理ツリーではプレフィックス及びノードＩＤが異なるため、論理ツリー間でパケットを転送するためには、各ノードはプレフィックス及びノードＩＤを変更することにより宛先アドレスを変換することができる。図１１は、論理ツリー間でのデータ送信を示す、例示概略図１１００を示す。ノード８がノード９にパケットを送信するために、ノード８は、論理ツリープレフィックスフィールドに１を挿入し、論理ツリー１でのノード９のノードＩＤを、宛先ノードＩＤフィールドとして挿入し、論理ツリー１を介してパケットを転送する。このパケットを受信した場合に、ノード７は、パケット転送決定用の従来のアルゴリズム利用して、このパケットを、論理ツリー２を介して転送することを決定する。ノード７は論理プレフィックスフィールドを２に変更し、論理ツリー１でのノード９のノードＩＤ（９１にて表記）を論理ツリー２でのノード９のノードＩＤ（９２にて表記）に変換する。このパケットは、ノードＩＤ９２、及び論理ツリー２のデータ送信アルゴリズムを用いて、ノード９に転送される。このように、本システムは、１つ以上の論理ツリーを利用してデータを送信するのに、異なる論理ツリープレフィックス値を割り当て、元の論理ツリーにおける宛先ノードＩＤを、割り当てられた論理ツリーにおけるノードＩＤに変換できる。
【００３７】
図１２はデータ送信フローチャートの例を示す。ネットワークノードがパケットを受信して、パケットの宛先アドレスを抽出した場合（ステップ１２１０）、そのノードは論理ツリープレフィックスを識別し（ステップ１２２０）、且つ論理ツリーでの宛先ノードＩＤを識別する（ステップ１２３０）。宛先ノードＩＤの識別後、受信ノードは、パケットを他の論理ツリーに転送するか、しないかを決定する（ステップ１２４０）。受信ノードは、他の論理ツリーでパケットを転送しない場合には（ステップ１２４０のｎｏ）、識別された論理ツリーで割り当てられたＩＤ（データ送信アルゴリズム）に基づく、任意の従来又は任意の上記した、データ送信方法を使用できる（ステップ１２５０）。ノードが他の倫理ツリーでパケットを送信すると決定した場合には（ステップ１２４０のｙｅｓ）、このノードは、新しい論理ツリーをあるアルゴリズムによって割り当てた後に（ステップ１２６０）、論理ツリープレフィックスフィールドに新たな論理ツリーを示し、宛先ノードＩＤを新しい論理ツリーでのノードＩＤに変換する（ステップ１２７０）。新しい論理ツリーのデータ転送アルゴリズムを利用して、新しい経路を介してパケットを転送する（ステップ１２８０）。
【００３８】
当業者にとっては、通信システムにおける信号干渉を減少するために、システム及び方法において、様々な修正例及び派生例が作成可能であることは明らかである。記載及び例は例示としてのみ解するべきであり、開示された実施形態の真の範囲は、添付の特許請求の範囲およびその均等の範囲によって示されることを意図している。
【図面の簡単な説明】
【００３９】
【図１】マルチホップリレーネットワークのブロック図である。
【図２ａ】論理ツリートポロジーの模範的な概略を示す図である。
【図２ｂ】通信ノードのブロック図の模範的な概略を示す図である。
【図３】特定の開示実施形態による、通信システムのネットワークノードＩＤ割り当てを示す図である。
【図４】図３で割り当てられたノードＩＤを２進数表記に広げた、ＩＤ割り当て動作を示す図である。
【図５】特定の開示実施形態による、多項式によるＮキャリー演算を利用する通信システムの、他のネットワークノードＩＤ割り当て例を示す図である。
【図６】特定の開示実施形態による、図５のＮキャリー演算ノードＩＤ割り当て例を示す図である。
【図７】通信システムにおけるデータ転送用の例示プロセスを示すフローチャートである。
【図８】通信システムにおけるデータ転送用の他の例示プロセスを示すフローチャートである。
【図９】ネットワークノードのハンドオーバーを示す概略図である。
【図１０ａ】メッシュトポロジーネットワークを示す概略図である。
【図１０ｂ】図１０ａのメッシュネットワークにおいて形成された論理ツリーを示す概略図である。
【図１１】論理ツリー間におけるデータ送信を示す概略図である。
【図１２】本発明の実施形態による、データ送信の例示フローチャートを示す図である。
【図１】
2008228274.tif 000003
【図２ａ】
2008228274.tif 000004
【図２ｂ】
2008228274.tif 000005
【図３】
2008228274.tif 000006
【図４】
2008228274.tif 000007
【図５】
2008228274.tif 000008
【図６】
2008228274.tif 000009
【図７】
2008228274.tif 000010
【図８】
2008228274.tif 000011
【図９】
2008228274.tif 000012
【図１０ａ】
2008228274.tif 000013
【図１０ｂ】
2008228274.tif 000014
【図１１】
2008228274.tif 000015
【図１２】
2008228274.tif 000016
【外国語明細書】
2008228274000001.pdf