JP6521994B2 - メッシュネットワークを最適化するための技術 - Google Patents

Description

関連出願の相互参照
本出願は、２０１４年２月２１日に出願された「ＬＯＡＤ ＢＡＬＡＮＣＩＮＧ ＡＮＤ ＢＡＣＫＧＲＯＵＮＤ ＳＣＡＮＮＩＮＧ ＩＮ Ａ ＴＩＭＥ ＳＹＮＣＨＲＯＮＩＺＥＤ ＣＨＡＮＮＥＬ ＨＯＰＰＩＮＧ ＮＥＴＷＯＲＫ」と称される米国仮出願第６１／９４３，２０４号の優先権を主張しており、この米国仮出願は、すべての目的のため、参照により、本明細書に組み入れられる。

メッシュネットワークにおけるノードが、最良の選択肢ではないコレクタまたは他の中央ノードデバイスに接続されることになり得るには、いくつかのシナリオが存在する。これは、ノードが準最適のコレクタを最初に見つけるときなどに、自然に起こり得る。これは、新たなコレクタがインストールされるまたは停電状態から復帰するときなどに、人工的に起こり得る。さらに、コレクタは限定された個数のノードをサポートできるだけであるから、ネットワークに新たなノードを追加すると、新たなノードと既存のノードとの両方に対し、コレクタの選択に影響が生じ得る。これらの理由のために、ノードは、ネットワークレイアウトを最適化するために、追加可能な「よりよい」パフォーマンスのコレクタが存在するかどうかを判断する能力を有することが必要である。

本発明の様々な態様は、現在および候補のコレクタの評価に基づき最適なコレクタを選択することにより、ネットワークを最適化するノードに関する。ある実装では、ノードは、ネットワークにおける現在のコレクタに関連する状態データを受け取るが、この場合、ノードは現在のコレクタにおいてアクティブである。ネットワークは、ＩＥＥＥ８０２．１５．４ｅによって定義されるような時間同期チャネルホッピング（ＴＳＣＨ）ネットワークであり得る。ノードは、また、ネットワークにおける候補のコレクタに関連する状態データも受け取るが、この場合には、ノードは候補のコレクタにおいてアクティブではない。コレクタに関連する状態データは、ＴＳＣＨネットワークにおいて、ビーコンメッセージとして実装され得る。

コレクタの状態データの解析が生成されるが、この場合、この解析は、受け取られた状態データにおいて報告されたそれぞれのネットワーク負荷を少なくとも比較することを含む。この解析は、さらに、状態データにおけるランクインジケータ、ノードの子ノードの個数、ノードが現在のコレクタにおいてアクティブであった時間の長さ、現在のコレクタに対して候補のコレクタによって保持される改善のマージン、および／またはそれ以外のファクタを比較することを含み得る。最適なコレクタは、現在のコレクタと候補のコレクタとのうちから、これらのコレクタの状態データの解析の少なくとも一部に基づいて決定される。現在のコレクタが最適なコレクタであると判断されるときは、ノードは、現在のコレクタにおいてアクティブであるままに継続し、候補のコレクタが最適なコレクタであると判断されるときには、ノードは、候補のコレクタにおいてアクティブになる。

本開示の多くの態様は、以下の図面を参照することで、よりよく理解され得る。図面におけるコンポーネントは必ずしも寸法通りではなく、その代わりに、本開示の原理を明瞭に図解することの方が強調されている。さらに、図面では、複数の図面を通じ、同様の参照番号は対応する部材を指す。

本開示の様々な態様による例示的なメッシュネットワークの図である。 本開示の様々な態様による例示的なメッシュネットワークの図である。 本開示の様々な態様による例示的なメッシュネットワークの図である。 本開示の様々な態様による図１のメッシュネットワークにおけるノードによって実装された機能のある例を図解するフローチャートである。 本開示の様々な態様による図１のメッシュネットワークにおいて用いられるノードのある例示的な図解を提供する、概略的なブロック図である。

本発明は、候補のコレクタを求めてネットワークを走査して、あるノードが現在のコレクタに接続されたまま維持されるべきか、または、候補のコレクタに移動すべきかを決定するために、候補のコレクタを評価するためのシステムおよび方法に関する。ノードは、これらに限定されることはないが、そのランクまたは各コレクタからの論理的距離と、その子供と、各コレクタの負荷とを含むファクタを考察する。

本明細書における定義によると、「ノード」は、メッシュネットワークにおいてメッセージを配信することに関係する機能を実行することができるインテリジェントデバイスを含む。あるシステムにおいて、ノードは、家屋またはアパートなどの設備に配置されており、ガス、水、または電力などの資源の消費を測定するメーターであり得る。そのようなメーターは、高度メーターリングインフラストラクチャ（ＡＭＩ）、無線周波数（ＲＦ）ネットワークの一部であり得る。ノードの他の例としては、ルータ、コレクタもしくは収集点、ホストコンピュータ、ハブ、またはネットワークに付属しており情報を通信チャネル経由で送信、受信、または転送することができるそれ以外の電子デバイスが含まれる。

ノードは、それが本発明の実装の範囲内において機能することを可能にするいくつかのコンポーネントを含み得る。たとえば、ノードは、それがメッシュネットワークにおける同様のノードおよび／またはそれ以外のデバイスと通信することを可能にする無線機を含み得る。各ノードの無線機は、その無線機がコンピュータのように機能し、本明細書に記載されている本発明の実装を提供するようにコンピュータおよびコマンド機能を実行することを可能にすることができる、プログラマブル論理制御装置（ＰＬＣ）のようなデバイスを有し得る。ノードは、また、他のノードとの通信に関係する情報を記憶するための記憶媒体を含み得る。そのような記憶媒体は、たとえば、メモリ、フロッピディスク、ＣＤ−ＲＯＭ、ＤＶＤ、またはノードの内部に配置されているかまたはネットワーク経由でそのノードからアクセス可能であるそれ以外の記憶デバイスを含み得る。ノードは、また、時間管理を提供する水晶発振子（すなわちクロック）とバックアップ電力を提供する電池とを含み得る。いくつかのノードは、電池だけによって給電され得る。

ノードは、メッシュネットワークにおける他のノードと、様々な周波数チャネルを経由して通信することができる。同じ周波数ホッピングシーケンスを共用する、すなわち、同時に複数の周波数の間でホップするノードは、同じ周波数を経由して相互に通信することができる。このように、ＴＳＣＨネットワークでは、ノードは、たとえば、例示的な実装によると、７つのチャネルなど、利用可能な周波数スペクトル経由で他のノードとの通信を確立するために、異なる時点においてホップすることができる。ノードは、たとえば７００ミリ秒など、一定の時間増分または滞留時間に従ってホップすることができ、その時点において、ノードは、与えられているチャネルまたは周波数経由でメッセージを送信または受信することができる。本明細書に記載されているように、用いられるホッピングシーケンス長は、ホッピングシーケンスにおけるいくらかのオーバラップを促進するために、チャネルの個数の整数倍であるべきである。たとえば７つのチャネルが存在する場合には、ホッピングシーケンス長は、２１など、７の整数倍であるべきであって、それにより、ホッピングシーケンスに２１個の時間枠が存在することになる。これによって、非干渉のためのランダム化を依然として提供しつつ、地理的に近接するコレクタのホッピングシーケンスにおいては、いくらかのオーバラップが生じる可能性が高まることになる。

本明細書における用法では、「親ノード」とは、情報を宛先に送りメッセージを受け取るために、別のノードによって用いられ得るノードを指す。各ノードがそれ自体と通信することが可能な他のノード（一般に、隣接ノードと称される）を習得または識別する際には、通信を容易にするために、これらのノードに関する情報およびパフォーマンスの計量が取得される。ノードは、識別されたどのノードが情報を宛先に送りメッセージを受け取るための最良のオプションを提供するのか、すなわち親ノードであるのかを決定するために、この計量を用いて識別したノードのそれぞれを採点することができる。親ノードを識別したノードは、同意語的であるが、その親ノードの子ノードと称され得る。

本明細書における用法では、「コレクタノード」とは、ネットワークと他のネットワークとの間においてはもちろん、ネットワークの内部でメッセージをルーティングするのに用いられるノードを指す。たとえば、コレクタノードは、多数のメーターを含むワイヤレスメッシュネットワークとヘッドエンドシステムまたはコントロールセンタを含む光ファイバネットワークとの内部で、メッセージをルーティングし得る。与えられたネットワークが１つまたは複数のコレクタノードを含む場合があり得るが、その場合、各コレクタノードがパーソナルエリアネットワーク（ＰＡＮ）を確立する。様々なＰＡＮが、集合的に、ネットワークを構成する。ノードは、そのノードがコレクタのＰＡＮの一部であるときに、与えられたコレクタで「アクティブである」、または、与えられたコレクタと「関連する」、と称されることがあり得る。

本明細書における用法では、「状態データ」とは、メッセージまたは一連のメッセージにおいて通信された情報を指し、ノードはその情報から、与えられたコレクタと関連するネットワーク状態情報を取得し得る。情報データは、コレクタから直接に、または、１つまたは複数の中間的なノードを経由して、ノードによって受信され得る。ＩＥＥＥ８０２．１５．４ｅによって定義されるネットワークのいくつかの実装では、状態データは、ビーコンによって運ばれ得る。ビーコンは、スケジュール駆動および／またはイベント駆動ベースで、伝送され得る。

ここで図面を参照すると、図１は、本明細書において説明されているシステムを実装するように構成された例示的なメッシュネットワーク１０を示す。メッシュネットワーク１０は、コレクタノード１９〜２０と無線ノード２１〜３１とを含み得る。コレクタノード１９〜２０は、そのノードと関連する施設におけるガス、水、または電力の消費の測定値などの情報を、ノード２１〜３１が送り得る収集点として機能し得る。ノード２１〜３１は、既に論じたように、メッシュネットワークにおける他のノードと通信し、そのような通信を容易にするためのインテリジェントな決定を行うために十分なネットワークおよび計算能力を有し得る。コレクタノード１９〜２０は、ノード２１〜３１に存在するものと少なくとも同じ機能および能力を有するように構成され得る。さらに、コレクタノード１９〜２０は、ノード２１〜３１からの情報を記憶するために十分な記憶能力と、いくつかの例では、それらのノードから受信された情報を処理するためにより大きな計算能力と、を含み得る。他の例では、コントロールセンタまたはそれ以外のコンピュータデバイス（図示せず）が、ノードから受信された情報を処理するのに、用いられ得る。

図１には、メッシュネットワーク１０における３層のノード（層１、層２、および層３）が示されている。他の構成では、より少数のまたはより多数の層が存在することがあり得る。ノードは、ノードからコレクタノードへの論理的距離およびデータ伝送の信頼性など、一定のファクタに基づいて、特定の層と関連し得る。ファクタおよび／またはファクタに与えられるウェイトは、ネットワークが異なることにより変動し得る。ノードが層１に配置されているということは、それらがコレクタノードへの「よりよい」接続を有しており、コレクタノードと通信するために中間ノードの使用を要求しない、ということを示す。より大きな数字が付された層に配置されたノードは、少なくとも１つの中間ノードを介して、コレクタノード１９〜２０と通信する。たとえば、層２に配置されたノードは親ノードである層１に対して子ノードであり、層３に配置されたノードは親ノードである層２に対して子ノードである（すなわち、ここでは、層２のノードは、異なるノードの組み合わせにおいて、親および子の両方の役割として機能し得る）。このように、層３のノードは、その親である層２のノードを介して、コレクタノード１９〜２０のうちの１つと通信し、層２のノードは、今度は、その親である層１のノードと通信し、層１のノードはコレクタと通信する。図１には、層１のノードの方が層２のノードよりもコレクタノード１９〜２０に近接し、層２のノードの方が層３のノードよりも近接していることが示されているが、物理的距離だけによって層が判断されることはあり得ない。ノードが評価される態様に応じて、層１のノードが、層２のノードよりも、コレクタノード１９〜２０から遠く離れて配置されていることがあり得る。

上述したように、最適な選択肢ではないコレクタノード１９〜２０にノード２１〜３１が接続されることになり得るシナリオは、いくつか存在する。たとえば、ノード２２は、「よりよい」選択肢であるコレクタノード２０を発見する前に、コレクタノード１９を識別することがあり得る。さらに、新たなノードが追加されるなど、時間経過と共にネットワーク１０における条件が変化することがあり、その結果として、かつては最適なコレクタノードであったものが、もはや最適な選択肢ではなくなることがある。これらのおよびそれ以外の起こり得る理由により、ノード２１〜３１が、そのノードのためにパフォーマンスの改善を結果的に生じさせ得る利用可能な他のコレクタノードが存在するかどうかを判断する能力を有することが必要である。

本明細書に開示されている技術を用いると、ノード２１〜３１のそれぞれが、自らの最適なコレクタノード１９〜２０を決定することができ、現在選択されているコレクタノードが最適な選択肢であり続けることを周期的に確認できるので、ノード２１〜３１のそれぞれのパフォーマンスが改善される。結果的に、メッシュネットワーク１０のパフォーマンスと効率性とが、改善され得る。

この目的のため、図２は、ネットワーク１０の別の例証のための例を提示しており、このネットワーク１０は状態データ２１９〜２２０を含み、ノード２１〜３１は最適なコレクタノードを選択するために状態データ２１９〜２２０を用いてコレクタノード１０〜２０を比較し得る。ノードは、同期を維持するため、周期的に状態データをネットワークに送る。この状態データの一例として、ビーコンまたは強化されたビーコンがある。たとえば、ノード２６などのノードは、その現在のコレクタ１９と関連するパーソナルエリアネットワーク（ＰＡＮ）において、親ノード２２などのノードから、状態データ２１９を受け取り、また、候補のコレクタ２０と関連するＰＡＮにおけるノードからも、状態データ２２０を受け取ることがあり得る。ノード２６は、それ自身がコレクタ１９と関連するＰＡＮからコレクタ２０と関連するＰＡＮに切り換わるべきかどうかを判断するために、状態データの中の情報を用いる。

状態データ２１９〜２２０の中の情報は、（１）ＰＡＮ識別子（ＩＤ）、（２）ネットワークＩＤ、（３）署名、（４）ランクインジケータ、（５）ネットワーク負荷インジケータ、および／または、認識され得るそれ以外の状態情報を含み得る。「ＰＡＮ ＩＤ」は、状態データを送るノードのＰＡＮを識別する。「ネットワークＩＤ」は、ネットワークを識別する。たとえば、ノードが公益事業メーターである場合には、ネットワークＩＤは、公益事業またはそれ以外の資源プロバイダを識別し得る。「署名」は、状態データの正当性をノードが確認することを可能にするデータである。たとえば、署名は、公開鍵または共有鍵暗号の動作を用いることを通じて確認され得るデジタル署名またはそれ以外のデータであり得る。「ランクインジケータ」（ＲＩ）は、送信側ノードの層、またはそのコレクタノードからの論理的距離を指示する値である。「ネットワーク負荷インジケータ」（ＮＬＩ）は、コレクタの相対的負荷を表す値である。

たとえば、状態データがＴＳＣＨネットワークにおけるビーコンとして実装される場合には、ＰＡＮ ＩＤ、ネットワークＩＤ、および署名のためのデータ要素は、適用可能なネットワークプロトコルによって定義されるのが典型的であるが、これに対し、ＲＩおよびＮＬＩのためのデータ要素は定義され得ない。ＲＩおよびＮＬＩのためのデータ要素が定義されない場合には、それらは、ビーコンにおける不特定情報要素（ＩＥ）に含まれ得る。

再び図２を参照すると、コレクタ１９に接続されたノードからの状態データ２１９に対するＰＡＮ ＩＤは、コレクタ２０に接続されたノードからの状態データ２２０に対するＰＡＮ ＩＤと異なっているが、コレクタ１９〜２０に対するネットワークＩＤは、これらが同じネットワーク１０の一部であるため、同じである。ＲＩは、状態データのソースによって、メッシュネットワーク１０の宛先指向有向非巡回グラフ（ＤＯＤＡＧ）における位置に関して、以下のようにマッピングされる値である。ある実装では、ＲＩは、下記のように定義される０から７までの整数値である。
ランクインジケータ＝［７，（ランク／（２ｘＭｉｎＲａｎｋＩｎｃｒｅａｓｅ＋１））］の最小値

この実装では、ランク値は、次の通りである。
０−コレクタまたはコレクタから１ホップ
１−コレクタから２または３ホップ
２−コレクタから４または５ホップ
３−コレクタから６または７ホップ
４−コレクタから８または９ホップ
５−コレクタから１０または１１ホップ
６−コレクタから１２または１３ホップ
７−コレクタから１４ホップ以上

ＭｉｎＲａｎｋＩｎｃｒｅａｓｅは、それぞれのコレクタによって定義される。

ある実装では、ＮＬＩは、下記のように特定される０から８までの値である。
０−コレクタ負荷が通常または通常未満（＜全容量の２５％）
２−コレクタ負荷が通常から高い（２５％から５０％の間）
５−コレクタ負荷が重い（５０％から７５％の間）
８−コレクタ負荷が最大値を超えている（＞７５％）

理解され得るように、他の実装では、上に示されているもの以外の値が用いられることがあり得る。ＮＬＩ値は、ノード２１〜３１から、状態データ２１９〜２２０の中で転送されるが、他方で、ＲＩ値は、状態データ２１９〜２２０を転送するノードによって更新され得る。一般に、通常の負荷を有するコレクタ１９〜２０と関連するノードが与えられている場合には、ランクの著しい改善が存在しない限り、その与えられたノードを別のコレクタに切り換えるべきではないのだが、それは、現在のコレクタに留まり、与えられたノードの子ノードに影響を生じない方がより好ましいであろうから、という理由による。

次に、ネットワーク１０のノード２１〜３１において実装され得るネットワーク最適化動作の例示的な例証が提供される。この例証の目的のために、ノード２６で実行され得る動作について説明されるが、同様の動作がノード２１〜３１のいずれにおいても実行され得ると理解される。最初に、ノード２６が、状態データ２１９を、コレクタ１９に接続されたノード２２から受け取っても良い。状態データ２１９が受け取られる時点で、ノード２６は、既にコレクタ１９のＰＡＮのアクティブなノードであり得るか、または、ノード２６によって検出された全ての別のコレクタノードの間で状態データ２１９が最適な選択肢であることに基づいて、コレクタ１９のＰＡＮに参加しても良い。

その後で、ノード２６が、コレクタ２０と関連する状態データ２２０を受け取ることがあるが、この場合、状態データ２２０は、コレクタ２０から直接に、または、１つまたは複数の中間ノードを介して、受け取られる。ノードが現時点で関連しているコレクタ以外のコレクタは、本明細書では、「候補のコレクタ」と称され得る。ノード２６は、状態データ２２０が（その現在のコレクタではなくて）候補のコレクタと関連するということを、状態データ２２０のＰＡＮ ＩＤがコレクタ１９と関連する状態データ２１９のＰＡＮ ＩＤと異なることに基づいて、認識し得る。ノード２６は、また、候補のコレクタと現在のコレクタとが両者共に同じネットワークに参加していることを確認するために、状態データ２２０のネットワークＩＤが状態データ２１９によって用いられるネットワークＩＤと同じであることを、確認する。たとえば、公益事業メーターであるノードの場合には、あるネットワークＩＤが電気メーターを表すのに用いられ、他方で、別のネットワークＩＤがガスメーターのために用いられる。これらのネットワークのそれぞれの内部では、各ＰＡＮが１つのコレクタによって統率されながら、様々な複数のＰＡＮが存在し得る。

再び図２を参照すると、いくつかの実装では、ノード２６が、状態データ２１９〜２２０の信頼性を確認するために、状態データ２１９〜２２０の署名を確認しても良い。この署名確認は、理解され得るように、デジタル署名、公開鍵、共有鍵、暗号ハッシング、および／またはそれ以外の認証機構を用いて、実行され得る。その後で、ノード２６は、現在のコレクタと候補のコレクタとのうちから最適なコレクタを決定するために、それぞれの状態データ２１９〜２２０において報告された様々なファクタを比較する。比較され得るファクタは、（１）ＮＬＩ、（２）ＲＩ、（３）ノード２６の子の個数、（４）ノード２６が現在のコレクタ（すなわち、コレクタ１９）のＰＡＮの中に存在してきた時間の長さ、および／または他の可能性のあるファクタを含む。

たとえば、現在のコレクタ１９と関連する状態データ２１９は、ネットワーク負荷が最大容量の７５％を超えることを表す「８」というＮＬＩ値を報告し得る。候補のコレクタ２０と関連する状態データ２２０は、ネットワーク負荷が最大容量の２５％〜５０％であることを表す「２」というＮＬＩ値を報告し得る。いくつかの実装では、現在のコレクタ１９に対する候補のコレクタ２０の、そのような大幅なＮＬＩの改善は、他のファクタを考慮しなくても、候補のコレクタ２０を最適のコレクタとして決定するのに十分であり得る。図３には、ノード２６がノード２３の子ノードとなり、コレクタ２０のＰＡＮの一部になった後の、結果的なネットワーク１０の例示的な図が示されている。変更の結果として、ノード２６に対する子ノードであるノード３０もまた、コレクタ２０においてアクティブになる。

図３を用いて、さらに後の時点における別の例について続けると、いま現在のコレクタであるコレクタ２０が「５」というＮＬＩ値を報告し、他方で、候補のコレクタ１９が「２」というＮＬＩ値を報告する場合には、ノード２６は、最適なコレクタを決定する前に、ＲＩなど、他のファクタを考慮することがあり得る。この例では、ノード２６は、ＲＩおよびＮＬＩの両方のファクタを評価し得るが、それはそれぞれの状態データ２１９〜２２０において報告されたＲＩおよびＮＬＩの値を加算し、より低い値が好まれるが、加算された値での差の程度を確かめることによって行われる。

ここで、ノード２６がノード２５から状態データ２１９を受け取る場合には、ノード２５はコレクタ１９から２ホップなので、ＲＩ値は「１」となる。ノード２６がノード２３から状態データ２２０を受け取る場合には、ノード２３はコレクタ２０から１ホップなので、ＲＩ値は「０」となる。したがって、現在のコレクタに対するＮＬＩ＋ＲＩの値は「５」であり、他方で、候補のコレクタ１９に対するＮＬＩ＋ＲＩの値は「３」である。２つのＮＬＩ＋ＲＩの値の差（すなわち、５−３＝２）が改善の最小限のマージンを満たす場合には、今度は、候補のコレクタ１９が最適なコレクタであることが決定され得る。あるいは、改善の最小限のマージンが満たされない場合には、ノード２６が、現在のコレクタ２０においてアクティブであり続けることになる。改善の最小限のマージンは、コレクタ１９への変更から結果的に生じ得るノード２６とその子であるノード３０とへの断絶のコストを表す別のファクタと考えられ得る。

次に図４を参照すると、様々な態様によるメッシュネットワーク１０におけるノード２１〜３１の方法４００のためのネットワーク最適化動作の一例を提供するフローチャートが示されている。図４のフローチャートは、本明細書に記載されている方法４００のネットワーク最適化動作を実装するために用いられ得る、多くの異なるタイプの機能配列の一例を提供するに過ぎない、ということが理解される。図４のフローチャートに示されている例示的な動作は、コレクタのＰＡＮにおいてノードが前もってアクティブになった後で、メッシュネットワーク１０のノード２１〜３１によって開始される。

ブロック４０３で開始するのであるが、ノード２１〜３１は、その現在のコレクタと関連する状態データを、直接に、または、１つもしくは複数の中間ノードを介して、受け取り得る。状態データにおける情報は、理解され得るように、（１）ＰＡＮ ＩＤ、（２）ネットワークＩＤ、（３）署名、（４）ＲＩ、（５）ＮＬＩ、および／または他の状態データを含み得る。

次に、ブロック４０６において、ノードは、その現在のコレクタとは異なる候補のコレクタと関連する状態データを受け取っても良いが、状態データは、候補のコレクタから直接に、または、１つもしくは複数の中間ノードを介して、受け取られ得る。ノードは、状態データのＰＡＮ ＩＤが現在のコレクタによって用いられる状態データのＰＡＮ ＩＤとは異なることに基づいて、その状態データが（現在のコレクタではなくて）候補のコレクタからのものである、ということを認識し得る。ノードは、また、候補のコレクタと現在のコレクタとが両方共に同じネットワークに参加していることを確認するために、候補のコレクタから受け取られた状態データのネットワークＩＤが現在のコレクタの状態データによって用いられるネットワークＩＤと同じである、ということを確認し得る。いくつかの態様では、ノードは、また、受け取られた状態データの信頼性を確認するために、状態データの署名を確認しても良い。署名の確認は、デジタル署名、公開鍵、共有鍵、暗号的ハッシング、および／または認識されうる他の認証機構を用いて、実行され得る。

そして、ブロック４０９では、ノードは、ノード自体にローカルなものだけでなく、状態データにおいて報告され得る様々なファクタに基づいて、それぞれのコレクタの解析を生成する。解析され得るファクタは、（１）ＮＬＩ、（２）ＲＩ、（３）ノードの子の個数、（４）ノードが現在のコレクタのＰＡＮの中に存在してきた時間の長さ、（５）改善の最小限のマージン、および／またはそれ以外のファクタを含み得る。

最適なコレクタとして選択されるためには、候補のコレクタが、より低いＮＬＩ値など、１つまたは複数のファクタに関して現在のコレクタに対する改善を示すことが必要であり得るが、それだけでは十分でない。ブロック４１２では、ノードは、現在のコレクタによって示され得る改善のマージンを考慮する。たとえば、ある可能な実装では、ノードは、ファクタの下記のグループを考慮し得る。
１）（ＲＩ＋ＮＬＩ）の合計値の５以上の減少、および、候補のコレクタのＮＬＩが５未満
２）（現在のコレクタのＮＬＩが５以上）および（候補のコレクタのＮＬＩが５未満）
３）（子の個数が３以下、および、このコレクタでアクティブになってから８時間が経過）
または
（子の個数が１０以下、および、このコレクタでアクティブになってから１６時間が経過）
または
（子の個数が１０を超える、および、ＲＩ＋ＮＬＩの合計値の８以上の減少）
４）（現在のコレクタのＮＬＩが８、および、候補のコレクタのＮＬＩが５未満）

この例では、ノードは、ファクタグループの（１および３）、（２および３）、または（４）が真である場合に、候補のコレクタが最適なコレクタであると判断し得る。ここで、ファクタグループは、「（ＲＩ＋ＮＬＩ）の合計値の５以上の減少」など、改善の最小限のマージンを本質的に考慮する様々な規則を特定する。

ノードによって考慮されるファクタが候補のコレクタとの関係で改善の最小限のマージンを示す場合には、次に、ブロック４１５において、候補のコレクタが最適なコレクタであり、ノードは候補のコレクタにおいてアクティブになる。あるいは、ノードによって考慮されるファクタが候補のコレクタとの関係で少なくとも改善の最小限のマージンを示さない場合には、次に、ブロック４１８において、現在のコレクタが最適なコレクタであり、ノードは引き続き現在のコレクタにおいてアクティブであり続ける。その後では、ノード２１〜３１における方法４００の実行はブロック４０３に戻り、そこで、ネットワーク最適化動作が、後で、隣接のコレクタを再度評価し得る。

次に、図５には、本明細書に開示されている技術をワイヤレスメッシュネットワークまたはそれ以外のデータネットワークにおいて実装するために用いられるノード２１〜３１の例を示すブロック図が、示されている。ノード２１〜３１は、処理デバイス５０２を含み得る。処理デバイス５０２の非限定的な例には、マイクロプロセッサ、特定用途向け集積回路（「ＡＳＩＣ」）、ステートマシン、またはそれ以外の適切な処理デバイスが含まれる。処理デバイス５０２は、１つを含む任意の個数の処理デバイスを含み得る。処理デバイス５０２は、メモリデバイス５０４などのコンピュータ可読な媒体に、通信可能に接続され得る。処理デバイス５０２は、メモリデバイス５０４にそれぞれ記憶されたコンピュータ実行可能なプログラム命令および／またはアクセス情報を、実行することができる。

メモリデバイス５０４は、処理デバイス５０２によって実行されると処理デバイス５０２に本明細書に記載された動作を遂行させる命令を記憶することができる。メモリデバイス５０４は、（これらに限定されないが）電子的、光学的、磁気的、またはそれ以外のコンピュータ可読な命令をプロセッサに提供することができる記憶デバイスなどの、コンピュータ可読媒体であり得る。そのような光学的、磁気的、またはそれ以外の記憶媒体の非限定的な例には、リードオンリ（「ＲＯＭ」）デバイス、ランダムアクセスメモリ（「ＲＡＭ」）デバイス、磁気ディスク、磁気テープもしくはそれ以外の磁気ストレージ、メモリチップ、ＡＳＩＣ、環境設定されたプロセッサ、光学記憶装置、またはコンピュータプロセッサがそこから命令を読み出すことができる全てのそれ以外の媒体が含まれる。ここでの命令は、コンパイラおよび／またはインタプリタによって、任意の適切なコンピュータプログラミング言語で書かれたコードから生成されたプロセッサに固有の命令を含み得る。適切なコンピュータプログラミング言語の非限定的な例には、Ｃ、Ｃ＋＋、Ｃ＃、Ｖｉｓｕａｌ Ｂａｓｉｃ、Ｊａｖａ、Ｐｙｔｈｏｎ、Ｐｅｒｌ、およびＪａｖａＳｃｒｉｐｔなどが含まれる。

ノード２１〜３１は、ノード２１から３１のうちの１つまたは複数のコンポーネントを通信可能に接続することができるバス５０６を含み得る。図５ではプロセッサ５０２、メモリ５０４、およびバス５０６が相互に通信する別個の構成要素として示されているが、他の実装も可能である。たとえば、プロセッサ５０２、メモリ５０４、およびバス５０６は、プログラミングコードを記憶し実行するためにノード２１〜３１に配置され得るプリント基板またはそれ以外の適切なデバイスの構成要素であっても良い。

ノード２１〜３１は、また、ネットワークインターフェースデバイス５０８を含むことができる。ネットワークインターフェースデバイス５０８は、アンテナ５１０を経由して１つまたは複数のワイヤレス通信リンクを確立するように構成された送受信デバイスであり得る。ネットワークインターフェースデバイス５０８の非限定的な例は、ＲＦトランシーバであり、メッシュネットワーク１０において他のノード２１〜３１への通信リンクを確立するための１つまたは複数のコンポーネントを含み得る。

多数の特定の詳細が、特許請求の範囲に記載された主題に関する完全な理解を提供するために、本明細書において明らかにされている。しかし、当業者であれば、特許請求の範囲に記載された主題は、これらの特定の詳細がなくても実現され得る、ということを理解するであろう。それ以外の場合であっても、当業者であれば知り得るであろう方法、装置、またはシステムが、特許請求の範囲に記載された主題を曖昧にすることを回避するために、詳細については記載されていない。

いくつかの部分は、コンピュータメモリなどのコンピューティングシステムメモリに記憶されたデータビットもしくはバイナリデジタル信号に対する動作のアルゴリズムまたは記号表現として、提示されている。これらのアルゴリズムに関する記載または表現は、データ処理技術の当業者が、彼らの仕事の実体をその技術分野の他の当業者に伝達するために用いられる技術の例である。アルゴリズムとは、所望の結果に至る自己完結的な一連の動作または同様の処理である。この文脈において、動作または処理は、物理量の物理的操作を含む。必ずではないが、典型的には、そのような量は、記憶、転送、合成、比較、またはそれ以外の操作がなされ得る電気的または磁気的信号という形式を取り得る。主に一般的に用いられるという理由のために、このような信号を、ビット、データ、値、エレメント、シンボル、キャラクタ、ターム、数、数字などと言及するのが便利である場合があることが判明している。しかし、これらおよび同様の用語は、すべて、適切な物理量と関連付けられること、そして、単に便利なラベルであることが、理解されるべきである。そうではないと特に断らない限り、本明細書の全体を通じて、「処理する（ｐｒｏｃｅｓｓｉｎｇ）」、「コンピュートする（ｃｏｍｐｕｔｉｎｇ）」、「計算する（ｃａｌｃｕｌａｔｉｎｇ）」、「決定する（ｄｅｔｅｒｍｉｎｉｎｇ）」および「識別する（ｉｄｅｎｔｉｆｙｉｎｇ）」などの用語を用いた議論は、コンピューティングプラットフォームのメモリ、レジスタ、もしくはそれ以外の記憶デバイス、伝送デバイス、または表示デバイスにおける物理的な電子的または磁気的量として表現されたデータを操作または変換する、１つもしくは複数のコンピュータまたは同様な１つもしくは複数の電子的コンピュータデバイスなどのコンピュータデバイスの作用またはプロセスを指す、と理解される。

本明細書で論じられている１つまたは複数のシステムは、特定のハードウェアアーキテクチャまたは構成に制限されることはない。コンピュータデバイスは、１つまたは複数の関数コールを条件とする結果を提供するコンポーネントの任意の適切な配置を含み得る。適切なコンピュータデバイスは、マルチパーパスのマイクロプロセッサベースのコンピュータシステムを含むのであるが、このマルチパーパスのマイクロプロセッサベースのコンピュータシステムは、コンピューティングシステムを、汎用のコンピューティング装置から本発明の主題の１つまたは複数の態様を実装する特別のコンピューティング装置にプログラミングまたは環境設定する、記憶されているソフトウェアにアクセスするのである。コンピュータデバイスをプログラミングまたは環境設定するのに用いられるソフトウェアとして本明細書に含まれる教示を実装するためには、任意の適切なプログラミング、スクリプト、またはそれ以外のタイプの言語または言語の組合せが、用いられ得る。

本明細書に開示されている方法の態様は、そのようなコンピュータデバイスの動作として実行され得る。上述の例で提示されているブロックの順序は変更が可能であり、たとえば、ブロックの順序を再決定すること、複数のブロックを組み合わせること、および／またはブロックをさらにサブブロックに分割することが可能である。一定の複数のブロックまたはプロセスは、並列的に実行され得る。

本明細書における「適合されている（ａｄａｐｔｅｄ ｔｏ）」または「構成されている（ｃｏｎｆｉｇｕｒｅｄ ｔｏ）」という用法は、追加的なタスクまたはステップを実行するように適合されているまたは構成されている装置を除外することのない、開放的で包括的な用法であることが意図されている。さらに、「基づく」という用法は、明記されている１つまたは複数の条件または値に「基づく」プロセス、ステップ、計算、またはそれ以外の作用が、実際には、明記されているものを超える追加的な条件または値に基づく場合もあり得るという点で、開放的で包括的な用法であることが意図されている。本明細に含まれる表題、リスト、および番号は、説明を容易にするためだけのものであり、制限を意図していない。

以上では、本発明の主題を、その特定の態様に関して詳細に説明してきたが、当業者であれば、以上についての理解を得ることにより、そのような態様の改変、変形および均等物を容易に想到し得る、ということが理解されるだろう。したがって、本開示は、限定ではなく例示の目的のために提示されてきたのであり、当業者に対して容易に明らかになるように、本発明の主題に、そのような修正、変形、および／または追加を包含させることを排除しない、ということが理解されるべきである。

Claims (13)

1. ネットワークにおいて、ノードのプロセッサによるネットワークパフォーマンスを最適化するための方法であって、
   前記ネットワークにおいて、前記ノードがアクティブである現在のコレクタと関連するビーコンを受け取り、
   前記ネットワークにおいて、前記ノードがアクティブではない候補のコレクタと関連するビーコンを受け取り、
   前記ビーコンの解析を生成し、前記解析は前記ビーコンで報告されたそれぞれのネットワーク負荷の比較を含み、
   前記現在のコレクタと前記候補のコレクタとのうちから最適なコレクタを決定し、前記決定は、前記ビーコンの前記解析と、前記候補のコレクタによる前記現在のコレクタに対するいずれかの改善のマージンのサイズとに少なくとも部分的に基づき、
   前記ノードは、前記現在のコレクタが前記最適なコレクタであると決定されるときには、前記現在のコレクタでアクティブであるまま留まり、
   前記ノードは、前記候補のコレクタが前記最適なコレクタであると決定されるときには、前記候補のコレクタでアクティブになり、
   前記解析が前記現在のコレクタに対する最小限のマージンの改善を示すときにのみ、前記候補のコレクタが前記最適なコレクタであると決定され、
   前記ノードが複数の子ノードを有しており、前記最適なコレクタの前記決定が、さらに、前記ノードの前記子ノードの個数に基づき、
   前記最適なコレクタの前記決定が、さらに、前記ノードが前記現在のコレクタでアクティブであった時間の長さの決定に基づく方法。
2. 前記解析が、前記ビーコンで報告されたそれぞれのランクインジケータの比較をさらに備え、ランクインジケータが、コレクタノードから送信側ノードの論理的距離を示す値である、請求項１に記載の方法。
3. 前記候補のコレクタが、（１）前記候補のコレクタと関連する前記ビーコンが前記ネットワーク負荷を約５０％またはそれ未満として報告していることと、（２）前記現在のコレクタに対する前記候補のコレクタの所定の改善閾値と、に少なくとも部分的に基づいて、前記最適なコレクタであると決定され、前記改善閾値は、前記ビーコンで報告された前記それぞれのランクインジケータとそれぞれのネットワーク負荷とに少なくとも部分的に基づく、請求項２に記載の方法。
4. 前記現在のコレクタと関連する前記ビーコンが前記ネットワーク負荷を約７５％またはそれを超えると報告し、他方で、前記候補のコレクタと関連する前記ビーコンが前記ネットワーク負荷を約５０％またはそれ未満であると報告するときに、前記候補のコレクタが前記最適なコレクタであると決定される、請求項１に記載の方法。
5. ネットワークにおいて、ノードのプロセッサによって実行可能でありネットワークを最適化するためのプログラムを実施する非一時的コンピュータ可読媒体であって、前記プログラムが、
   前記ネットワークにおいて、前記ノードがアクティブである現在のコレクタと関連する状態データを受け取るコードと、
   前記ネットワークにおいて、前記ノードがアクティブではない候補のコレクタと関連する状態データを受け取るコードと、
   前記コレクタと関連する前記状態データの解析を生成するコードであって、前記解析は前記状態データで報告されたそれぞれのネットワーク負荷とランクインジケータとの比較を備える、コードと、
   前記現在のコレクタと前記候補のコレクタとのうちから最適なコレクタを決定するコードであって、前記決定は、前記状態データの前記解析に少なくとも部分的に基づく、コードと、を備えており、
   前記ノードは、前記現在のコレクタが前記最適なコレクタであると決定されるときには、前記現在のコレクタでアクティブであるまま留まり、
   前記ノードは、前記候補のコレクタが前記最適なコレクタであると決定されるときには、前記候補のコレクタでアクティブになり、
   前記解析が前記現在のコレクタに対する最小限のマージンの改善を示すときにのみ、前記候補のコレクタが前記最適なコレクタであると決定され、
   前記ノードが複数の子ノードを有しており、前記最適なコレクタの前記決定が、さらに、前記ノードの前記子ノードの個数に基づき、
   前記最適なコレクタの前記決定が、さらに、前記ノードが前記現在のコレクタでアクティブであった時間の長さの決定に基づく非一時的コンピュータ可読媒体。
6. 前記現在のコレクタと関連する前記状態データが前記ネットワーク負荷を約５０％またはそれを超えると報告し、他方で、前記候補のコレクタと関連する前記状態データが前記ネットワーク負荷を約５０％未満であると報告することに少なくとも部分的に基づいて、前記候補のコレクタが前記最適なコレクタであると決定される、請求項５に記載の非一時的コンピュータ可読媒体。
7. 前記ネットワークが時間同期チャネルホッピング（ＴＳＣＨ）ネットワークである、請求項５に記載の非一時的コンピュータ可読媒体。
8. 前記候補のコレクタと関連する前記状態データが前記ネットワーク負荷を約５０％未満であると報告することに少なくとも部分的に基づいて、前記候補のコレクタが前記最適なコレクタであると決定される、請求項５に記載の非一時的コンピュータ可読媒体。
9. ノードであって、
   プロセッサと、
   ネットワーク上で通信するためのネットワークインターフェースであって、
   前記ネットワークにおいて、前記ノードがアクティブである現在のコレクタと関連するビーコンを受け取り、
   前記ネットワークにおいて、前記ノードがアクティブではない候補のコレクタと関連するビーコンを受け取る、
   ように構成されたネットワークインターフェースと、
   前記ノードにおいて実行されるネットワーク最適化アプリケーションによって構成されたメモリであって、前記ネットワーク最適化アプリケーションが、前記ノードに、前記ビーコンの解析であって、前記ビーコンで報告されたそれぞれのネットワーク負荷とランク識別子との比較を備えた解析を生成させ、
   前記ビーコンの前記解析に少なくとも部分的に基づいて、前記現在のコレクタと前記候補のコレクタとのうちから最適なコレクタを決定させる、メモリと、を備えており、
   前記ノードは、前記現在のコレクタが前記最適なコレクタであると決定されるときは、前記現在のコレクタでアクティブであるまま留まり、
   前記ノードは、前記候補のコレクタが前記最適なコレクタであると決定されるときは、前記候補のコレクタでアクティブになり、
   前記ノードが複数の子ノードを有しており、前記最適なコレクタの前記決定が、さらに、前記ノードの前記子ノードの個数に基づき、
   前記最適なコレクタの前記決定が、さらに、前記ノードが前記現在のコレクタでアクティブであった時間の長さの決定に基づくノード。
10. 前記解析が前記現在のコレクタに対して最小限のマージンの改善を示すときにのみ、前記候補のコレクタが前記最適なコレクタであると決定される、請求項９に記載のノード。
11. 前記ネットワークがＩＥＥＥ（Ｉｎｓｔｉｔｕｔｅ ｏｆ Ｅｌｅｃｔｒｉｃａｌ ａｎｄ Ｅｌｅｃｔｒｏｎｉｃｓ Ｅｎｇｉｎｅｅｒｓ）８０２．１５．４によって定義されている、請求項９に記載のノード。
12. 前記現在のコレクタと関連する前記ビーコンが前記ネットワーク負荷を約５０％またはそれを超えると報告し、他方で、前記候補のコレクタと関連する前記ビーコンが前記ネットワーク負荷を約５０％未満であると報告することに少なくとも部分的に基づいて、前記候補のコレクタが前記最適なコレクタであると決定される、請求項９に記載のノード。
13. （ａ）前記ノードの前記子ノードの個数が３未満または３に等しく、前記ノードが前記現在のコレクタでアクティブであった時間の長さが８時間またはそれよりも長い、（ｂ）前記ノードの前記子ノードの個数が１０未満または１０に等しく、前記ノードが前記現在のコレクタでアクティブであった時間の長さが１６時間またはそれよりも長い、および（ｃ）前記ノードの前記子ノードの個数が１０を超えており、前記候補のコレクタの前記ネットワーク負荷と前記ランク識別子とが、前記現在のコレクタの前記ネットワーク負荷と前記ランク識別子とに対して最小限のマージンの改善を示す、のうちの１つが真であることに少なくとも部分的に基づいて、前記候補のコレクタが前記最適なコレクタであると決定される、請求項９に記載のノード。

Images