(57)【要約】通信装置ネットワーク（１００）内において、通信装置（１１１）はクラスタヘッドとして動作すべきかを判断する。前記装置は、性能および好ましくは装置の環境（４１０, ４２０, ４３０）に関連する要素に重みを割り当てる公式に基づく、クラスタヘッドとして動作する能力の自己評価を実行する。装置の能力は、クラスタヘッドとして動作するかを判定する際に、乱数成分と併用される（４４０）。好適な実施形態では、クラスタヘッドステータスを仮定すると、その装置は近隣の装置と通信し、クラスタヘッドであることを伝え、クラスタの形成に加わるように他の装置に促す。
2005522099.tif 000002
【特許請求の範囲】
【請求項１】
複数の通信ノードの中からクラスタヘッドを選択する方法であって、該方法は、複数の前記通信ノードの各々において、
複数の通信ノードの内の少なくとも一つの通信ノードの特性を表す、少なくとも二つの要素を得るステップと、
前記少なくとも二つの要素の各々に、重みを割り当てる公式を使用して導かれた能力レベルの評価と、乱数成分の使用とに基づいて、クラスタヘッドとして動作するステップとを、備える方法。
【請求項２】
請求項１記載の方法において、前記少なくとも二つの要素は、有効エネルギー、有効処理能力、および特定の通信ノードとの接続性の中から選択される方法。
【請求項３】
請求項２記載の方法において、前記少なくとも二つの要素は更に、一つ以上の近隣通信ノードのエネルギー利用可能度に関連する要素を備える方法。
【請求項４】
請求項２記載の方法において、前記少なくとも二つの要素は更に、クラスタヘッドとの接続確立に対する待機時間に関連する要素を備える方法。
【請求項５】
請求項２記載の方法において、前記少なくとも二つの要素は、有効エネルギー、有効処理能力、および特定の通信ノードとの接続性に関連する少なくとも二つの値を備える方法。
【請求項６】
請求項１記載の方法において、クラスタヘッドとして動作するステップは、特定のノードをクラスタヘッドとして識別する信号によって、近隣の装置に通信するステップを備える方法。
【請求項７】
請求項６記載の方法において、クラスタヘッドとして動作するステップは更に、近隣ノードを含むクラスタを形成するステップを備える方法。
【請求項８】
通信ネットワーク内において、クラスタヘッドとして選択的に動作するための通信装置であって、
送信器と、
メモリであって、
通信装置の動作特性を表す少なくとも二つの要素と、
前記少なくとも二つの要素の各々に異なる重みを割り当てる公式に基づいて能力レベルを評価し、かつ評価された能力レベルに基づいてクラスタヘッドステータスを判定する動作命令とを備える、メモリと、
メモリ内の動作命令を実行し、送信器に、クラスタヘッドステータスの判定に応答して、クラスタヘッドとなる通信装置を識別する信号を送信させる制御装置とを備える通信装置。
【請求項９】
請求項８記載の通信装置において、乱数値を出力するように機能する乱数発生器を備え、制御装置は、クラスタヘッドステータスを判定する際、乱数値を利用する方法で動作命令を実行する通信装置。
【請求項１０】
請求項９記載の通信装置において、メモリは近隣の通信装置を含むクラスタを形成する動作命令を備える通信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概ね、通信ネットワークに関連し、更に特定すると、組織化されたクラスタノードを有するネットワークにおける、クラスタヘッドの選択に関連する。
（関連出願のクロスリファレンス）
本発明は、２００１年４月２０日に出願された、「クラスタツリープロトコルを利用する通信ネットワーク（Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｎｅｔｗｏｒｋ  Ｕｔｉｌｉｚｉｎｇ  Ａ  Ｃｌｕｓｔｅｒ  Ｔｒｅｅ  Ｐｒｏｔｏｃｏｌ）」と題する、出願番号第６０／２８５１６５号を割り当てられた出願に関連する。
【背景技術】
【０００２】
無線ネットワークは、一般的にノードと呼ばれる多数の通信装置を円滑に管理するため、二階層アーキテクチャに構成されることが多い。典型的な構成では、ノードは、地理的に近接していること、または他の共通する特性に基づいて、クラスタにグループ化される。各クラスタ内の一つのノードは、クラスタヘッドとして指定され、一定の管理業務の実行や通信の効率化を行う。例えば、クラスタヘッドは、クラスタ内のデータ集約、データ経路指定、意思決定、およびネットワーク装置の動作制御を受け持つ。クラスタヘッドは、セルラーネットワーク内の基地局が携帯加入者端末のクラスタヘッドとして機能する場合のように、ネットワーク構成の初期設定時に手動で割り当てることが可能である。クラスタヘッドはまた、ネットワークオペレーションプロトコルに基づき、動的に割り当てられてもよい。
【０００３】
最近では、異種装置間の自己組織化、非同期式無線ネットワークが提案されてきている。これらのネットワーク内のノードは性能や機能において大きく異なる。クラスタヘッドを指定する従来の方法は、装置が同じ種類であることや、ノードの配置およびノードの性能に関する先験的知識に基づく手動による割り当てのような、一定の基本的な前提が適用できないので、不十分であることが分かってきている。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従って、クラスタの形成およびクラスタヘッドの選択に対する新しい方法が必要とされる。特に、自己組織化、非同期式異種ネットワークに適した方法を必要とする。
本発明の目的および利点は、付属の図面と照らし合わせることにより、発明を実施するための最良の形態において、より速やかに明確になることであろう。
【課題を解決するための手段】
【０００５】
本発明は、無線ネットワークの形成、および運用の方法を提供するものである。さらに特定すると、無線ネットワークの通信装置の中からクラスタヘッドを選択する方法を提供する。例えば処理能力、有効エネルギー、他の装置への接続性、かつ／またはその他のような特性は、クラスタヘッドとして動作する通信装置の適合性を判定する要素である。好ましくは、装置は、装置各要素に重みを割り当てる公式に基づき、クラスタヘッドとして動作する自身の能力レベルについて自己評価を行う。通常、クラスタヘッドとして選択されるには、より高い能力レベルを有する装置がより望ましい。いくつかの装置が適当な能力レベルを有する場合、該方法は、クラスタヘッドを判定する過程において、より高い能力レベルを有する装置がクラスタヘッドとして選択される可能性が高くなるように、無作為化を用いることを含む。クラスタヘッドステータスの仮定により、そのクラスタヘッド装置は近隣の装置と通信を行い、クラスタヘッドステータスを信号送信し、その他の装置
に対してクラスタの形成に加わるように促す。
【発明を実施するための最良の形態】
【０００６】
図１は本発明に基づく、無線ネットワーク１００を表す図である。無線ネットワーク１００は二階層構成を有し、本願においてノードと称されるいくつかの通信装置１１１, １１２, １２１, １２２, １３１, １３２, １４１, １４２を含み、それらの通信装置は、クラスタ１１０,  １２０, １３０, １４０に編制される。その好適な実施形態において
、クラスタは一般に、同様の地理的地域に属し、互いに首尾よく通信可能であり、通信チャネル、伝送周波数等の他の特性を共有する複数のノードにより形成される。集合体であるクラスタ１１０, １２０, １３０, １４０は、概念上の階層的配列において、ネットワークの第一層１０１を形成する。各クラスタ１１０, １２０, １３０, １４０は、それぞれ指定されたクラスタヘッド１１１, １２１, １３１, １４１を有し、該クラスタヘッドはクラスタ内のデータ集約、データ経路指定、意思決定、および装置の動作制御等の特定の機能を実行する。例えば、クラスタヘッドは、クラスタ内のノードと外部ノードとの通信における情報の経路として機能する。クラスタヘッド１１１, １２１, １３１, １４１は相互に通信し、ネットワークの第二層１０２を形成する。第二層１０２は、高レベルな通信、または通信の優先度、独立した通信チャネル、高速のデータ転送、高い送信電力量等により特徴付けられる。第二層ネットワーク１０２は、異なるクラスタ内におけるノード間の通信を促進し、外部アクセスおよび制御をサポートする。
【０００７】
図２は、図１において記述された通信装置を表すネットワーク通信ノードである、装置１１１のシステムレベルのブロック図を示す。ネットワーク装置１１１において、メッセージ受信器２１５は着信メッセージを受信し、ファンクションプロセッサ２２５へ情報を提供する。ファンクションプロセッサ２２５は、検出、計測、監視、制御、かつ／または他の機能を実行する構成要素のような、装置全体の機能に特化した構成要素を含む。メッセージ送信器２２０はファンクションプロセッサ２２５と結合しており、装置の機能または他の必要に応じた通信要件に関するデータ送信能力を提供する。タイミングモジュール２４５は、通信、同期化、および他の装置の機能の情報を提供する。メモリモジュール２５５は装置の動作命令、およびデータを記憶し、制御部２３５は装置の全般的制御を提供する。乱数発生器２７５は、制御部２３５に０から１までの乱数を一様な頻度で提供する。好適な実施形態によると、クラスタヘッドは、各ノードにおいて実行されるアルゴリズムを使用してノードの中から選択される。つまり、そのようなノードの各々は、クラスタヘッドとして動作すべきかを判断する。クラスタヘッドがノードのグループの中から選択されると、グループ内の他のノードはクラスタヘッド周辺で自己組織化を行い、クラスタを形成する。従って、クラスタ１３０はまた、特にクラスタヘッド（ＣＨ）の動作をサポートするための構成要素、または機能性を含む。例えばファンクションプロセッサ２２５、制御部２３５、タイミングモジュール２４５、およびメモリモジュール２５５の全ては、クラスタヘッドの機能性をサポートするように、特別に調整された構成要素２３０, ２４０, ２５０, ２６０を含む。メモリ２５５は、性能パラメータ、または性能因子２６１、重み係数２６２、クラスタヘッドステータスを判定し、クラスタヘッドとして動作するアルゴリズムによる命令、および他の命令２６５、を含む。好適な実施形態では、性能パラメータは、例えばバッテリ残容量のような使用可能なエネルギー、有効処理能力、および特定の通信ノードの接続状態を特定する要素を含む。接続状態は、潜在的なクラスタヘッドノードの通信範囲内にあるその他の通信ノード数を参照する。例えば一つ以上の近隣にある通信ノードのエネルギー利用可能度、クラスタヘッドとの接続確立に対する待機時間のような他の要素も装置のメモリ２５５に含まれる。クラスタヘッドの選択、および動作命令２６５により実行される手続き、およびステップは以下に説明される。
【０００８】
図３は本発明に基づく、非同期式無線ネットワーク内における潜在的ノードである、通信装置３００の組織化されていないグループを示す。少なくとも通信装置のいくつかは、
図２に説明するような全般的構造のものであり、各装置によりクラスタヘッドとして機能する性能に違いはあるものの、そのような構造において各装置はクラスタヘッドとして機能することができる。そのため、ノードはそれぞれ、ある特定の要素を識別する設定されたパラメータを有している。おおよそ固定されているパラメータは、予めプログラムされている。例としては、全般的処理能力や、外部供給品へのアクセス状態に関するパラメータが挙げられる。消耗電源からの有効エネルギーおよび接続性のような他のパラメータは、通常、より動的であり、定期的または継続的に測定される。ネットワークの初期設定時、または再設定した場合には、そのネットワークは組織化されていない状態になり得る。
【０００９】
先に述べたように、各ノードは、クラスタヘッドの役割を実行する上での適正を判定するのに有用であると考えられる特定の能力、または属性に関する情報を有する。クラスタヘッドとして機能するためのノードの能力に影響する性能／属性は、好ましくは代表値のベクトルに含まれる。代表値のベクトルを本願において、性能ベクトルＣと呼ぶ。一実施形態では、ベクトルＣはノードの処理能力、有効エネルギー、ネットワーク内の他の装置への接続性、およびクラスタヘッドとの接続確立に対する待機時間を表す値を含む。ある実施形態では、ベクトルＣは更に、一つ以上の他のノードの特性を表す値を含む。ノードは好ましくは、性能ベクトルＣにおける各要素、または基準に起因する重要度、または重みを表す値を有する別のベクトルＷを含む。ベクトルＷの値によって表される重みの要素、または重みの割り当ては、性能ベクトルの値と組合せてノードによって使用され、クラスタヘッドとして動作するための能力レベルの評価を得る。
【００１０】
図４は本発明に基づく、クラスタヘッドステータスを判定し、クラスタを形成するためノードによって利用される手順４００の流れ図を示す。ステップ４１０において、典型的な動作において、各ノードは特定ノードの性能の特性を表す二つ以上の要素を得、ある場合には他の近隣ノードのそれを得る。そのような機能の情報は、クラスタヘッドステータスを判定する過程において使用するため、更に近隣ノード間に分配され得る。好ましくは、その要素の内、少なくとも二つは、有効エネルギー、有効処理能力、特定通信ノードの接続状態、一つ以上の近隣通信ノードの有効エネルギー、およびクラスタヘッドとの接続確立に対する待機時間の中から選択される。ステップ４２０において、一組の性能値に対応する一組の重み割り当ても同様に得られる。ステップ４３０において、評価は、一組の重みの割り当てに一致する一組の性能値を組み合わせることにより、クラスタヘッド動作の適正に関連する能力レベルから成る。ステップ４４０において、ノードは、能力レベル、および乱数成分の使用に基づき、クラスタヘッドとして動作すべきか判定する。好適な実施形態では、閾値Ｔｎは次の公式で決定される。
【００１１】
【数１】
2005522099.tif 000003
上記式中、ｎ＝特定のノード数
ＡＬｎ＝の能力レベル
Ｈｄ＝ネットワークに必要なクラスタヘッドの平均数
Ｎｕｍｎ＝特定のノードと同じクラスの潜在的なノードの総数
閾値Ｔｎはその後、クラスタヘッドステータス、即ちクラスタヘッドとして動作すべきか否か判定するため、乱数値と比較される。好適な実施形態では、０から１までの一様な頻度を有する乱数値（Ｘｎ）を得る。ＴｎがＸｎ以上である場合、ノードはクラスタヘッドとして選択される。そうでなければ、ノードはクラスタヘッドとして選択されない。
【００１２】
一つの例が、記述したアルゴリズムを説明するのに役立つであろう。２レベルクラスタ
ネットワークを形成する、無作為に配置された５００ノードを伴うネットワークを考える。そのネットワークは任意であり、接続されていると仮定する。アプリケーションやネットワーク内の特定の有効な装置に依って、必要クラスタ数（つまり、クラスタヘッドの数）は異なる。この例では、必要とされるクラスタ（クラスタヘッド）の数はネットワークノードの総数のおよそ１パーセントであると考えられる。この場合、クラスタ数は５である。実際に説明する目的のため、ネットワークに三つの異なる装置があるとする。三つの各装置は、異なる性能ベクトルＣを有する。性能ベクトルＣは、処理能力、有効エネルギー、およびノード接続性を表す。
【００１３】
Ｃ＝［処理能力、有効エネルギー、接続性］
三つの異なる装置の性能ベクトル（Ｃ１, Ｃ２, Ｃ３）は、
Ｃ１＝［１, １, １］，Ｃ２＝［１，０．５，０．５］，Ｃ３＝［０，０．５，０．５］
である。
この例の目的では、これら機能の各々の重みは等しいと仮定されている（多くの場合は異なるのだが）。
【００１４】
Ｗ＝［１／６，１／６，１／６］
ＷとＣの内積は、ネットワークにある三つの異なる装置の能力レベル（ＡＬ）を与える。
ＡＬ１＝１／２, ＡＬ２＝１／３, ＡＬ３＝１／６
ネットワーク内に５００個のノードがあり、ノードの１０％が能力レベルＡＬ１＝１／２を有し、１５％が能力レベルＡＬ２＝１／３を有し、７５％が能力レベルＡＬ３＝１／６を有し、５つのクラスタヘッドがそのネットワークに必要であると仮定する。前述の閾値の方程式に基づくと、第一クラス装置については、
ＡＬ１＝１／２, Ｈｄ＝５, Ｎｕｍ１＝５０, および
Ｔ１＝（１／２）（５）／５０＝１／２０
第二クラス装置については、
ＡＬ２＝１／３, Ｈｄ＝５, Ｎｕｍ２＝７５, および
Ｔ３＝（１／３）（５）／７５＝１／４５
第三クラス装置については、
ＡＬ３＝１／６, Ｈｄ＝５, Ｎｕｍ３＝３７５, および
Ｔ３＝（１／６）（５）／３７５＝１／４５０
データ解析は概して、より高い能力レベルのノードが選択される可能性が高いことを示すと共に、５ノードがクラスタヘッドとして選択されることを示す。図５は、説明した例のシミュレーションの結果を示す。
【００１５】
クラスタヘッドの判定に続いて、クラスタヘッドとして選択されたノードは、自分がクラスタヘッドであることを、すぐ隣のノードに通知する。即ち、各クラスタヘッドはクラスタヘッドとしての特定のノードであることを識別する信号を送信し、近隣の装置にクラスタに加わるように促すことによって、近隣の装置と通信する。他のノードもまた、通知しているプロセスに参加することもある。好ましくは、クラスタヘッドの通信範囲内にあるノードは、自分に最も近いクラスタヘッドに応答を返すとともに、クラスタの第一レベルノードであることを識別する。これらの第一レベルノードは、そのプロセスを繰り返す。即ち、第一レベルノードであることを通知し、まだクラスタに属していないすぐ隣のノードに、クラスタの次レベルのノードとしてクラスタに加わるように促す。このプロセスは、ネットワークの全てのノードがクラスタに加わるか、またはそのネットワーク層において定義されたある停止基準に達するまで続く。その結果形成されたネットワークは、クラスタヘッドに直属するマルチレイヤノードを有するクラスタを伴う、マルチホップネットワークになるであろう。本発明に基づき、図５は選択されたクラスタヘッド周辺でのネットワーク組織の初期段階を示し、図６は最終段階を示す。このクラスタヘッドの選択プ
ロセスは、ネットワークの特定のプロトコルによって定期的に再始動または、繰り返すことができる。
【００１６】
本発明は従来技術を超える重要な利点を提供する。好適な実施形態では、クラスタヘッドの選択は、少なくとも部分的には装置の性能、および相対的重要度に基づく能力の自己評価に基づき、また無作為化する成分の結合に基づくものである。加えて、クラスタヘッドの選択は、各ノードがノード自身の認識、およびすぐ近くの環境を利用するように、ネットワーク全体に渡る広範囲な知識を個々のノードに要求しない。付加的な利益は、クラスタヘッド選択の間に送信されるメッセージ数の低減である。このようなクラスタヘッドの選択の考え方は、自己組織化、異種装置間非同期式無線ネットワーク、その他の装置間において非常に適している。特に、これらネットワーク内の各ノードが、性能、および機能において大幅に異なる場合には非常に適している。
【００１７】
上記説明は、発明の好適な実施形態において記述されているが、その発明は、以下の特許請求の範囲における精神と公正な意味を逸脱することなく修正、改良または変更可能であることを認識されよう。
【図面の簡単な説明】
【００１８】
【図１】本発明に基づく、分類されたクラスタヘッド、および二階層構造を有する典型的なネットワークを示す図。
【図２】本発明に基づく、クラスタヘッドとして機能可能な典型的なネットワーク装置のブロック図。
【図３】本発明に基づく、組織化されていないノードを示す図。
【図４】本発明に基づく、クラスタヘッドとして動作すべきか判定するため、ノードにより使用される手順流れ図。
【図５】本発明に基づく、クラスタヘッド選択後のクラスタ形成を示す図。
【図６】本発明に基づく、クラスタ形成の後期段階を示す図。
【図１】
2005522099.tif 000004
【図２】
2005522099.tif 000005
【図３】
2005522099.tif 000006
【図４】
2005522099.tif 000007
【図５】
2005522099.tif 000008
【図６】
2005522099.tif 000009
【国際調査報告】
2005522099.tif 000010
2005522099.tif 000011