(57)【要約】【課題】センサアレイのための好適な無線ネットワークを提供すること。【解決手段】線形無線センサネットワークが、各ブランチに沿って単調に変動するノード識別子を有するノードを含む。ネットワーク識別子は、ノードが、ルーティングテーブルの使用を伴わずにパケットを転送することを可能にする。低デューティサイクル無線通信プロトコルが、パケットが、殆ど電力を消費せずに非常に大きなネットワークの全てのノードにルーティングされることを可能にする。ノード間の、ユニキャストではなくブロードキャスト伝送が、好ましい信号伝搬条件を利用し、最大可能ホップを使用し、可能な限りノードをスキップし、かつ時間的または空間的に変動する条件に自動的に適合してメッセージを転送する。パケットのグループが、ブロードキャストされ、そのグループの全てのパケットを受信した最も遠隔の受信するノードによって転送される。【選択図】図２
2019220998.tif 000002
【特許請求の範囲】
【請求項１】
無線線形ネットワークにおける方法であって、前記無線線形ネットワークは、第１のノードと、前記第１のノードに近接する複数の第２のノードと、複数の追加のノードとを備え、全てのノードは、ブランチに沿って配列されており、各ノードは、ノード識別子を有し、前記ノード識別子は、前記ブランチに沿って、前記ブランチの一方の端部から前記ブランチの他方の端部に単調に変動し、前記方法は、複数のパケットを前記第１のノードから前記第２のノードのうちの１つを介してルーティングするためのものであり、前記複数のパケットは、最初のパケットと、少なくとも１つの後続パケットとを備え、
前記方法は、
前記第１のノードが、前記複数のパケットの各パケットを無線で連続的にブロードキャストすることであって、各パケットは、厳密に１回ブロードキャストされ、各パケットは、
前記複数のパケット内のパケットを識別するシーケンス番号と、
前記複数のパケット内のパケットの合計数の指示と
を含む、ことと、
各第２のノードが、前記第１のノードから直接、前記複数のパケットのうちの少なくとも１つのパケットを無線で受信し、それに応答して、肯定応答メッセージを前記第１のノードに無線で伝送することであって、前記肯定応答メッセージは、前記第２のノードのノード識別子を含み、前記第２のノードによってどの少なくとも１つのパケットが受信されたかを識別し、前記複数の第２のノードは、それによって、複数の伝送される肯定応答メッセージを集合的に伝送する、ことと、
前記第１のノードが、前記複数の伝送される肯定応答メッセージのうちの少なくとも１つの肯定応答メッセージを受信することと、
前記第１のノードによって受信される前記少なくとも１つの肯定応答メッセージに従って、少なくとも１つの第２のノードが、前記複数のパケットのうちの全てのパケットを受信した場合に、
前記第１のノードが、前記全てのパケットを受信した１つの第２のノードを選択することであって、前記第１のノードのノード識別子と前記選択された１つの第２のノードのノード識別子との間の差異は、前記第１のノードのノード識別子と前記全てのパケットを受信した任意の他の第２のノードのノード識別子との間の差異よりも大きい、こと、および、
前記第１のノードが、前記選択された１つの第２のノードに命令メッセージを無線で伝送し、前記選択された１つの第２のノードに、前記複数のパケットを転送するように命令すること
を実行することと、
そうでない場合に、
事前決定された補償試行の回数以内で、
前記第１のノードが、前記複数のパケットのセットをブロードキャストすることであって、前記セットは、少なくとも１つの第２のノードによって受信されなかったパケットを含む、ことと
を含む、方法。
【請求項２】
各第２のノードが前記第１のノードに前記肯定応答メッセージを無線で伝送することは、各第２のノードが、前記第２のノードに割り当てられたタイムスロット中に前記第１のノードに前記肯定応答メッセージを無線で伝送することを含む、請求項１に記載の方法。
【請求項３】
各第２のノードが前記第１のノードに前記肯定応答メッセージを無線で伝送することは、各第２のノードが、衝突検出および衝突回避から成るグループから選択される衝突タイプを伴うキャリアセンスマルチプルアクセスプロトコルに従って、前記肯定応答メッセージを無線で伝送することを含む、請求項１に記載の方法。
【請求項４】
前記セットは、少なくとも２つの第２のノードによって受信されなかったパケットの和集合を備えている、請求項１に記載の方法。
【請求項５】
各第２のノードは、クロックと、無線送受信機とを備え、前記方法は、各第２のノードが、
前記第２のノードによる前記複数のパケットのうちの前記少なくとも１つのパケットの受信のタイミングに基づいて、前記第２のノードのクロックを調節すること、および、
いつ前記第２のノードの無線受信機をオンにし、いつ前記無線受信機をオフにするかを制御するために、前記クロックを使用すること
を実行することをさらに含む、請求項１に記載の方法。
【請求項６】
前記第２のノードが前記最初のパケットを受信しなかった場合、前記クロックを調節することは、前記第２のノードが、サイクルにおいて以前よりも早くそれの無線受信機をオンにするように前記クロックを調節することを含む、請求項５に記載の方法。
【請求項７】
前記第２のノードが前記複数のパケットのうちの全てのパケットを受信したわけではない場合、前記クロックを調節することは、前記第２のノードが、少なくとも部分的に、前記第２のノードによって受信されなかったパケットの数に依存する量だけ、サイクルにおいて以前よりも早くそれの無線受信機をオンにするように前記クロックを調節することを含む、請求項５に記載の方法。
【請求項８】
前記クロックを調節することは、前記第２のノードによって受信されなかったパケットの数に少なくとも部分的に依存する量だけ前記クロックを調節することを含む、請求項５に記載の方法。
【請求項９】
前記クロックを調節することは、前記最初のパケットが前記第２のノードによって受信される前に前記受信機がオンであった時間量に少なくとも部分的に依存する量だけ前記クロックを調節することを含む、請求項５に記載の方法。
【請求項１０】
前記第２のノードが前記最初のパケットを受信した場合、前記クロックを調節することは、前記第２のノードが、前記最初のパケットが前記第２のノードによって受信される前に前記受信機がオンであった時間量に少なくとも部分的に依存する量だけ、サイクルにおいて以前よりも遅くそれの無線受信機をオンにするように前記クロックを調節することを含む、請求項５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の引用）
本願は、米国特許出願第１４／６９７，８３１号（２０１５年４月２８日出願、名称「Ｗｉｒｅｌｅｓｓ  Ｎｅｔｗｏｒｋ  ｆｏｒ  Ｓｅｎｓｏｒ  Ａｒｒａｙ」）に対する優先権を主張し、上記出願の全内容は、あらゆる目的のために参照により本明細書に引用される。
【０００２】
本発明は、無線コンピュータネットワークに関し、より具体的には、パイプラインまたは道路に沿ったセンサ等のノードの線形アレイのための無線コンピュータネットワークに関する。
【背景技術】
【０００３】
パイプライン、幹線道路、鉄道線路、または公共設備配管に沿って設置されるセンサ等のセンサアレイは、典型的には、それらが設置されると、殆どまたは全く保守することなく、長期間、多くの場合、数年にわたって動作するように設計される。多くのそのようなアレイは、互いに、かつ最終的に、１つ以上の中央コントローラ（基地局）と無線で通信するノードのコンピュータネットワークを形成し、例えば、センサデータもしくはメータ読み取り値を収集し、それらを基地局に転送すること、または基地局からのコマンドに応答して、センサパラメータを設定すること、もしくは他の遠隔デバイスを制御することを行う。ノードは、アクセス困難な場所に設置され、バッテリ交換等の保守を困難かつ高価にし得る。
【０００４】
ノード内の無線送信機および受信機（送受信機）が、ノード間およびノードと基地局との間の無線通信を提供する。これらの無線機は、有意な量の電力を消費し得る。しかしながら、各ノードは、典型的には、ノードを数年にわたって、場合によってはノードの全期待寿命にわたって動作させ続けることが予期されるバッテリ等、非常に限定された電気エネルギー源を有する。いくつかの場合、ノードは、その出力が比較的に小さい、太陽光、熱、または他のタイプのエネルギー回収装置によって給電される。
【０００５】
その結果、エネルギー効率的無線通信プロトコルが、開発された。殆どのそのようなプロトコルは、低デューティサイクルを採用し、無線機は、周期的に、かつ比較的に短期間にわたってのみオンに切り替えられる。例えば、ＣｏｎｔｉｋｉＭＡＣ無線デューティサイクルプロトコルによると、無線機は、１秒あたり約８回オンに切り替えられる。無線機がオフである時間量と比較した無線機がオンである時間量は、無線機のデューティサイクルと称される。約０．６％と同程度に低いデューティサイクルが、使用される。低デューティサイクルプロトコルは、エネルギーを節約するが、それらは、ノードが良好に同期させられたクロックを維持することを要求し、したがって、ノードは、その無線機をその近隣対応物と同時またはほぼ同時にオンにし得る。多数のノード間でクロックを同期させることは、エネルギーおよびコンピュータリソース消費の観点から非常に高価であり得る。改良された低デューティサイクルプロトコルが、したがって、望ましい。
【発明の概要】
【課題を解決するための手段】
【０００６】
本発明の実施形態は、線形センサネットワークを提供する。線形センサネットワークは、少なくとも２つのネットワークノードと、基地局とを含む。少なくとも２つのネットワークノードは、ブランチに沿って論理的に配列される。ブランチは、第１の端部と、第２の端部とを有する。少なくとも２つのネットワークノードの各ネットワークノードは、それぞれのネットワークノード識別子に関連付けられている。少なくとも２つのネットワークノードは、それらのそれぞれの関連付けられているネットワークノード識別子に従って、ブランチに沿って論理的に配列される。少なくとも２つのネットワークノードは、ブランチに沿って論理的に配列され、したがって、ネットワークノード識別子は、ブランチに沿って、第１の端部から第２の端部に単調に変動する。ネットワークノード識別子は、ブランチに沿って、第１の端部から第２の端部に単調に増加し得る、またはネットワークノード識別子は、ブランチに沿って、第１の端部から第２の端部に単調に減少し得る。
【０００７】
基地局は、無線送受信機を含む。基地局は、ブランチの一方の端部に隣接する。ネットワークノード識別子が、基地局に関連付けられている。
【０００８】
各ネットワークノードは、そのそれぞれのネットワークノード識別子の表現を記憶する。各ネットワークノードは、それぞれのセンサと、それぞれの無線送受信機とを含む。各ネットワークノードは、そのセンサを用いてデータを収集し、基地局において発信するコマンドを受信することに応答して、少なくとも１つのネットワークパケットを使用して、その無線送受信機を介して、データを伝送する。
【０００９】
少なくとも２つのネットワークノードの各ネットワークノードは、ブランチの一方の端部における最初のネットワークノードおよびブランチの他方の端部における最後のネットワークノードを除いて、その無線送受信機を介して、ネットワークパケットを転送する。各ネットワークパケットは、それぞれの一連のネットワークノードによって転送され、それらのそれぞれのネットワークノード識別子は、一連のネットワークノードに沿って単調に変動する。
【００１０】
各ネットワークノードは、ネットワークパケット送信元識別装置と、ネットワークパケット宛先識別装置と、ネットワークノード識別子コンパレータと、ネットワークパケットルータとを含み得る。ネットワークパケット送信元識別装置は、無線送受信機に結合される。ネットワークパケット送信元識別装置は、受信されたネットワークパケットにおける送信元ネットワークノード識別子を読み取る。ネットワークパケット宛先識別装置も、無線送受信機に結合される。ネットワークパケット宛先識別装置は、受信されたネットワークパケットにおける宛先ネットワークノード識別子を読み取る。
【００１１】
ネットワークノード識別子コンパレータは、ネットワークパケット送信元識別装置およびネットワークパケット宛先識別装置に結合される。ネットワークノード識別子コンパレータは、ノードのネットワークノード識別子の記憶された表現を受信されたネットワークパケットにおける送信元ネットワークノード識別子および受信されたネットワークパケットにおける宛先ネットワークノード識別子と比較する。
【００１２】
ネットワークパケットルータは、ネットワークノード識別子コンパレータに結合される。ネットワークパケットルータは、ノードのネットワークノード識別子の表現に対する送信元ネットワークノード識別子の値およびノードのネットワークノード識別子の表現に対する宛先ネットワークノード識別子の値に基づいて、受信されたネットワークパケットを転送することを検討すべきかどうかを決定する。
【００１３】
ネットワークパケットルータは、ルーティングテーブルを参照することなく、受信されたネットワークパケットを転送することを検討すべきかどうかを決定し得る。
【００１４】
線形センサネットワークは、パケット送信元および宛先ノード識別子コンパレータも含み得る。パケット送信元および宛先ノード識別子コンパレータは、ネットワークパケット送信元識別装置およびネットワークパケット宛先識別装置に結合される。パケット送信元および宛先ノード識別子コンパレータは、受信されたネットワークパケットにおける送信元ネットワークノード識別子および受信されたネットワークパケットにおける宛先ネットワークノード識別子を比較する。
【００１５】
ネットワークパケットルータは、パケット送信元および宛先ノード識別子コンパレータに結合され得る。ネットワークパケットルータは、宛先ネットワークノード識別子の値に対する送信元ネットワークノード識別子の値にも基づいて、受信されたネットワークパケットを転送することを検討すべきかどうかを決定し得る。
【００１６】
随意に、各ノードに対して、最初のネットワークノードおよび最後のネットワークノードを除いて、ブランチ上のノードの場所は、ブランチをノードに対して第１の部分および第２の部分に論理的に分ける。各ネットワークノードは、最初のネットワークノードおよび最後のネットワークノードを除いて、その無線送受信機を介して、ブランチの第１の部分上のそれぞれのノードから受信されたネットワークパケットをブランチの第２の部分上の少なくとも１つのノードに転送する。各ネットワークノードは、最初のネットワークノードおよび最後のネットワークノードを除いて、その無線送受信機を介して、ブランチの第２の部分上のそれぞれのノードから受信されたネットワークパケットをブランチの第１の部分上の少なくとも１つのノードに転送する。
【００１７】
本発明の別の実施形態は、ネットワークパケットを転送する方法を提供する。方法は、少なくとも２つのネットワークノードのそれぞれのものに関連付けられているそれぞれのネットワークノード識別子に従って、ブランチに沿って少なくとも２つのネットワークノードを論理的に配列することを含む。ブランチは、第１の端部と、第２の端部とを有する。ネットワークノード識別子は、ブランチに沿って、第１の端部から第２の端部に単調に変動する。ネットワークノード識別子は、ブランチに沿って、第１の端部から第２の端部に単調に増加し得るか、またはネットワークノード識別子は、ブランチに沿って、第１の端部から第２の端部に単調に減少し得る。
【００１８】
基地局が、ブランチの一方の端部に隣接して配置される。基地局は、無線送受信機を含む。ネットワークノード識別子が、基地局に関連付けられている。
【００１９】
そのそれぞれのネットワークノード識別子の表現が、ネットワークノードのメモリ内等、各ネットワークノード内に記憶される。各ネットワークノードにおいて、データが、ネットワークノードのセンサを使用して収集される。少なくとも２つのネットワークノードのうちの少なくとも１つにおいて、基地局において発信するコマンドを受信することに応答して、データは、少なくとも１つのネットワークパケットを使用して、ネットワークノードの無線送受信機を介して伝送される。
【００２０】
少なくとも２つのネットワークノードの各ネットワークノードにおいて、ブランチの一方の端部における最初のネットワークノードおよびブランチの他方の端部における最後のネットワークノードを除いて、ネットワークパケットが、ネットワークノードの無線送受信機を介して転送される。各ネットワークパケットは、それぞれの一連のネットワークノードによって転送され、それらのそれぞれのネットワークノード識別子は、一連のネットワークノードに沿って単調に変動する。
【００２１】
パケットのグループが、最も遠い受信するノードを使用して、すなわち、最大可能ホップを使用して転送され得る。本発明のさらに別の実施形態は、無線線形ネットワーク内で、第１のノードから第２のノードを介して、少なくとも２つのパケットをルーティングする方法を提供する。無線線形ネットワークは、第１のノードと、第１のノードに近接する少なくとも２つの第２のノードと、少なくとも２つの追加のノードとを含み、全てが、ブランチに沿って配列される。各ノードは、ノード識別子を有する。ノード識別子は、ブランチに沿って、ブランチの一方の端部からブランチの他方の端部に単調に変動する。少なくとも２つのパケットは、最初のパケットと、少なくとも１つの後続パケットとを含む。
【００２２】
必ずしも、最初に少なくとも２つの第２のノードとタイムスロットについてネゴシエートせずに、第１のノードは、複数のパケットの各パケットを無線で連続的にブロードキャストする。各パケットは、厳密に１回ブロードキャストされ得る。各パケットは、シーケンス番号と、少なくとも２つのパケットにおけるパケットの合計数の指示とを含む。シーケンス番号は、少なくとも２つのパケット内のパケットを識別する。
【００２３】
各第２のノードは、第１のノードから直接、少なくとも２つのパケットのうちの少なくとも１つのパケットを無線で受信する。それに応答して、各第２のノードは、肯定応答メッセージを第１のノードに無線で伝送する。肯定応答メッセージは、第２のノードのノード識別子を含む。肯定応答メッセージは、第２のノードによってどの少なくとも１つのパケットが受信されたかを識別する。少なくとも２つの第２のノードは、それによって、少なくとも２つの伝送される肯定応答メッセージを集合的に伝送する。
【００２４】
第１のノードは、少なくとも２つの伝送された肯定応答メッセージのうちの少なくとも１つの肯定応答メッセージを受信する。第１のノードによって受信される少なくとも１つの肯定応答メッセージに従って、少なくとも１つの第２のノードが、少なくとも２つのパケットのうちの全てのパケットを受信した場合、第１のノードは、全てのパケットを受信した１つの第２のノードを選択する。第１のノードは、第２のノードを選択し、第１のノードのノード識別子と選択された第２のノードのノード識別子との間の差異は、第１のノードのノード識別子と全てのパケットを受信した任意の他の第２のノードのノード識別子との間の差異よりも大きい。第１のノードは、選択された第２のノードに命令メッセージを無線で伝送し、選択された第２のノードに、複数のパケットを転送するように命令する。
【００２５】
そうでなければ、事前決定された補償試行の回数以内で、第１のノードは、少なくとも２つのパケットのセットをブロードキャストし、セットは、少なくとも１つの第２のノードによって受信されなかったパケットを含む。
【００２６】
セットは、少なくとも２つの第２のノードによって受信されなかったパケットの集合を含み得る。
【００２７】
類似する方法が、最も遠い受信するノードを使用して、すなわち、最大可能ホップを使用して、単一パケットを転送するために使用され得る。
【００２８】
各第２のノードは、第２のノードに割り当てられたタイムスロット中に第１のノードに肯定応答メッセージを無線で伝送し得る。
【００２９】
各第２のノードは、衝突検出および／または衝突回避を伴うキャリアセンスマルチプルアクセスプロトコルに従って、肯定応答メッセージを無線で伝送し得る。
【００３０】
受信機のクロック位相が、どのパケットが受信された、および／または欠落しているかに基づいて調節され得る。各第２のノードは、クロックと、無線送受信機とを含み得る。方法はさらに、各第２のノードが、第２のノードによる複数のパケットのうちの少なくとも１つのパケットの受信のタイミングに基づいて、第２のノードのクロックを調節することを含み得る。クロックは、いつ第２のノードの無線受信機をオンにするか、および／またはいつ無線受信機をオフにするかを制御するために使用され得る。
【００３１】
第２のノードが最初のパケットを受信しなかった場合、クロックは、第２のノードが、サイクルにおいて以前よりも早くその無線受信機をオンにするように調節され得る。
【００３２】
第２のノードが複数のパケットのうちの全てのパケットを受信したわけではない場合、クロックは、第２のノードが、少なくとも部分的に、第２のノードによって受信されなかったパケットの数に依存する量だけ、サイクルにおいて以前よりも早くその無線受信機をオンにするように調節され得る。
【００３３】
クロックを調節することは、少なくとも部分的に、第２のノードによって受信されなかったパケットの数に依存する量だけクロックを調節することを含み得る。
【００３４】
クロックを調節することは、少なくとも部分的に、最初のパケットが第２のノードによって受信される前に、受信機がオンであった時間量に依存する量だけクロックを調節することを含み得る。
【００３５】
第２のノードが最初のパケットを受信した場合、クロックを調節することは、第２のノードが、少なくとも部分的に、最初のパケットが第２のノードによって受信される前に、受信機がオンであった時間量に依存する量だけ、サイクルにおいて以前よりも遅くその無線受信機をオンにするようにクロックを調節することを含み得る。
【００３６】
送信側ノードに近接するノードは、そのクロックを送信側に同期させ得る。本発明の実施形態は、第１のノードが無線線形ネットワーク内の第２のノードを自動的に識別する方法を提供する。そうすることにおいて、第１のノードは、優先順位を第２のノードに割り当てる。無線線形ネットワークは、第１のノードと、第１のノードに近接する少なくとも２つの第２のノードと、少なくとも２つの追加のノードとを含む。全てのノードは、ブランチに沿って配列される。各ノードは、無線送信機と、無線受信機とを含む。各ノードは、ノード識別子を有する。ノード識別子は、ブランチに沿って単調に変動する。ネットワークノード識別子は、ブランチに沿って、第１の端部から第２の端部に単調に増加し得るか、またはネットワークノード識別子は、ブランチに沿って、第１の端部から第２の端部に単調に減少し得る。
【００３７】
第１のノードは、少なくとも２つの時間的に間隔を置かれた同期メッセージを無線でブロードキャストする。同期メッセージは、少なくとも２つの伝送タイムスロットについての情報を含む。各伝送タイムスロットに対して、同期メッセージは、伝送タイムスロットが割り当てられる単一のそれぞれの潜在的第２のノードについての情報を含む。
【００３８】
各第２のノードは、第１のノードから直接、同期メッセージのうちの少なくとも１つを受信する。各第２のノードは、複数の伝送タイムスロットのうちのどの１つが第２のノードに割り当てられているかを識別する。同期メッセージのうちの少なくとも１つの受信に応答して、各第２のノードは、その割り当てられた伝送タイムスロット中に無線で伝送する。各第２のノードは、第２のノードの識別子を含む肯定応答メッセージを無線で伝送する。したがって、集合的に、第２のノードは、複数の伝送される肯定応答メッセージを伝送する。
【００３９】
第１のノードは、複数の伝送される肯定応答メッセージのうちの少なくとも１つの肯定応答メッセージを受信する。第１のノードは、その肯定応答メッセージが第１のノードによって受信された第２のノードのセットに優先順位を付ける。優先順位付けは、少なくとも部分的に、その肯定応答メッセージが第１のノードによって受信された第２のノードの識別子に基づく。
【００４０】
各第２のノードは、クロックを含み得る。各第２のノードは、複数の同期メッセージのうちの少なくとも１つの第２のノードによる受信のタイミングに基づいて、そのクロックを調節し得る。各第２のノードは、いつその無線受信機をオンにするか、および／またはいつ無線受信機をオフにするかを制御するためにクロックを使用し得る。
【００４１】
各第２のノードは、クロックを含み得る。各第２のノードは、複数の同期メッセージのうちの少なくとも１つの第２のノードによる受信のタイミングに基づいて、そのクロックを調節し得る。各第２のノードは、いつ第２のノードがスリープ状態に入るか、および／またはいつ第２のノードがスリープ状態からウェイクするかを制御するためにクロックを使用し得る。
【００４２】
第２のノードのセットに優先順位を付けることは、第２のノードのセットのうちの各第２のノードに対して、第２のノードの識別子と第１のノードの識別子との間の差異に基づいて、第２のノードに優先順位を割り当てることを含み得る。より大きい差異を伴う第２のノードは、より小さい差異を伴う第２のノードよりも高い優先順位を割り当てられ得る。
【００４３】
加えて、第２のノードのセットにおける各第２のノードに対して、第１のノードは、優先順位付けメッセージを無線で伝送し得る。優先順位付けメッセージは、第２のノードに割り当てられた優先順位を含み得る。優先順位付けメッセージは、第２のノードに割り当てられた受信タイムスロット中に伝送され得る。
【００４４】
優先順位付けメッセージを伝送した後、第１のノードは、同期確認要求メッセージを伝送し得る。同期確認要求メッセージの受信に応答して、第２のノードのセットにおける各第２のノードは、第２のノードに割り当てられた優先順位に関連付けられているそれぞれのタイムスロット中、同期肯定応答メッセージを伝送し得る。
【００４５】
第１のノードは、メモリ内に、第２のノードのセットにおける各第２のノードについての情報を記憶し得る。情報は、第２のノードのノード識別子と、第２のノードに割り当てられた優先順位とを含み得る。
【００４６】
ビルトインスケジューリングを用いた無線プロビジョニングが、提供され得る。本発明の別の実施形態は、少なくとも２つのノードを含むネットワーク内でノードを更新する方法を提供する。少なくとも２つのメッセージが、ネットワーク内で送信される。各メッセージは、更新情報と、未来時の指示とを含む。
【００４７】
ネットワークの各ノードは、少なくとも２つのメッセージのうちの少なくとも１つを受信する。ネットワークの各ノードは、少なくとも２つのメッセージのうちの少なくとも１つの中に含まれる更新情報を記憶する。未来時において、ネットワークの各ノードは、ノードを更新するために、記憶された更新情報を使用する。
【００４８】
ネットワークの各ノードは、未来時においてアウェイクされるための要求を開始し得る。
【００４９】
各メッセージは、更新のタイプの指示も含み得る。各ノードは、ノードが更新のタイプに一致する場合のみ、ノードを更新するために、記憶された更新情報を使用し得る。
【００５０】
各ノードは、ノードが更新のタイプに一致する場合のみ、更新情報を記憶し得る。
【００５１】
健全性および安危情報が、他のタイプのネットワークパケット上で「ピギーバック」され得る。本発明のさらに別の実施形態は、ノードの無線線形センサネットワーク内で第１のネットワークステータス情報を送信する方法を提供する。無線線形センサネットワークは、中央コントローラを介して、別のネットワークに通信可能に結合される。ノードのうちの１つは、第１のネットワークステータス情報を収集する。ノードのうちの１つは、ノードのうちの別の１つからメッセージを無線で受信する。ノードのうちの１つは、メッセージ内に第１のネットワークステータス情報を記憶し、それによって、修正されたメッセージを生産する。ノードのうちの１つは、修正されたメッセージを無線で伝送する。
【００５２】
メッセージは、少なくとも修正されることに先立って、どんなネットワークステータス情報も欠き得る。
【００５３】
メッセージは、第２のネットワークステータス情報を含み得る。ノードのうちの１つは、第２のネットワークステータス情報を第１のネットワークステータス情報と比較する。メッセージ内に第１のネットワークステータス情報を記憶し、それによって、修正されたメッセージを生産することは、事前決定された比較スキームに従って、第１のネットワークステータス情報が、第２のネットワークステータス情報よりも有意である場合のみ、メッセージ内に第１のネットワークステータス情報を記憶し、それによって、修正されたメッセージを生産することを含み得る。
【００５４】
複数のネットワークセグメントが、無線センサネットワーク内に含まれ得、それぞれ、その独自のタイムスロットを伴う。本発明の実施形態は、無線センサネットワークを提供する。ネットワークは、少なくとも２つのネットワークセグメントと、基地局とを含む。各ネットワークセグメントは、少なくとも２つのそれぞれのノードを含む。各ノードは、厳密に１つのネットワークセグメントの要素である。各ノードは、それぞれのセンサと、それぞれの無線送受信機とを含む。各ノードは、その無線送受信機を使用し、そのセンサから導出されるデータを伝送する。各ノードは、そのそれぞれのネットワークセグメントの少なくとも１つの他のノードの無線通信範囲内に配置される。各ノードは、（ｉ）ネットワークセグメントの最初のノード、（ｉｉ）ネットワークセグメントの最後のノード、または（ｉｉｉ）ネットワークセグメントの中間ノードのうちの１つを含む。最初のノードおよび各中間ノードは、その送受信機を使用して、最初のノードからネットワークトポロジ的により遠隔のネットワークセグメントのノードから受信したデータを最初のノードにネットワークトポロジ的により近接したネットワークセグメントのノードに転送する。つまり、最後のノードを除く全てのノードが、基地局に向かってパケットを転送する。
【００５５】
基地局は、無線送受信機を含む。基地局は、各ネットワークセグメントの最初のノードの無線通信範囲内に配置される。基地局は、その無線送受信機を使用し、複数のノードのセンサから収集されたデータを受信する。各ノードは、繰り返し時間間隔に従って動作する。各時間間隔は、複数のタイムスロットに分割される。各ネットワークセグメントは、複数のタイムスロットのうちの固有のタイムスロットに関連付けられている。各ノードは、ノードのネットワークセグメントに関連付けられているタイムスロット中、そのセンサから収集されたデータを伝送し、各時間間隔の残りの間、省電力スリープ状態に入る。
【００５６】
各タイムスロットは、センサデータが１日以内に最後のノードから基地局に転送されることを可能にするために、十分に長くあり得る。
【００５７】
各省電力スリープ状態は、少なくともＮ−１個のタイムスロットの合計と同程度に長くあり得、Ｎは、各時間間隔におけるタイムスロットの数に等しい。
【００５８】
各タイムスロットは、少なくとも２つのサブスロットに分割され得る。各ノードは、（ａ）サブスロット中にその無線送受信機を使用し、ノードのネットワークセグメントの別のノードからセンサデータを受信することであって、別のノードは、ノードよりも基地局から遠位にある、ことと、（ｂ）後続サブスロット中に無線送受信機を使用し、センサデータを基地局に向かって転送することとを行う。
本明細書は、例えば、以下の項目も提供する。
（項目１）
線形センサネットワークであって、前記線形センサネットワークは、
複数のネットワークノードであって、前記複数のネットワークノードは、前記複数のネットワークノードのそれぞれのものに関連付けられているそれぞれのネットワークノード識別子に従って、ブランチに沿って論理的に配列されており、前記ブランチは、第１の端部と第２の端部とを有し、前記ネットワークノード識別子は、前記ブランチに沿って、前記第１の端部から前記第２の端部まで単調に変動する、複数のネットワークノードと、
前記ブランチの一方の端部に隣接する基地局であって、前記基地局は、無線送受信機を備え、前記基地局に関連付けられているネットワークノード識別子を有する、基地局と
を備え、
各ネットワークノードは、そのそれぞれのネットワークノード識別子の表現を記憶し、
各ネットワークノードは、それぞれのセンサと、それぞれの無線送受信機とを備え、
各ネットワークノードは、そのセンサを用いてデータを収集し、前記基地局において発信するコマンドを受信することに応答して、少なくとも１つのネットワークパケットを使用して、その無線送受信機を介して前記データを伝送し、
前記複数のネットワークノードの各ネットワークノードは、前記ブランチの一方の端部における最初のネットワークノードおよび前記ブランチの他方の端部における最後のネットワークノードを除いて、その無線送受信機を介して、ネットワークパケットを転送し、各ネットワークパケットは、それぞれの一連のネットワークノードによって転送され、前記一連のネットワークノードのそれぞれのネットワークノード識別子は、前記一連のネットワークノードに沿って単調に変動する、
線形センサネットワーク。
（項目２）
各ネットワークノードは、
前記無線送受信機に結合され、受信されたネットワークパケットにおける送信元ネットワークノード識別子を読み取るネットワークパケット送信元識別装置と、
前記無線送受信機に結合され、受信されたネットワークパケットにおける宛先ネットワークノード識別子を読み取るネットワークパケット宛先識別装置と、
前記ネットワークパケット送信元識別装置および前記ネットワークパケット宛先識別装置に結合されているネットワークノード識別子コンパレータであって、前記ネットワークノード識別子コンパレータは、前記ノードのネットワークノード識別子の記憶された表現を前記受信されたネットワークパケットにおける送信元ネットワークノード識別子および前記受信されたネットワークパケットにおける宛先ネットワークノード識別子と比較する、ネットワークノード識別子コンパレータと、
前記ネットワークノード識別子コンパレータに結合されているネットワークパケットルータと
を備え、
前記ネットワークパケットルータは、前記ノードのネットワークノード識別子の表現に対する前記送信元ネットワークノード識別子の値に基づき、かつ前記ノードのネットワークノード識別子の表現に対する前記宛先ネットワークノード識別子の値に基づいて、前記受信されたネットワークパケットを転送することを検討すべきかどうかを決定する、項目１に記載の線形センサネットワーク。
（項目３）
前記ネットワークパケットルータは、ルーティングテーブルを参照することなく、前記受信されたネットワークパケットを転送することを検討すべきかどうかを決定する、項目２に記載の線形センサネットワーク。
（項目４）
前記ネットワークパケット送信元識別装置および前記ネットワークパケット宛先識別装置に結合されているパケット送信元および宛先ノード識別子コンパレータをさらに備え、前記パケット送信元および宛先ノード識別子コンパレータは、前記受信されたネットワークパケットにおける送信元ネットワークノード識別子および前記受信されたネットワークパケットにおける宛先ネットワークノード識別子を比較し、
前記ネットワークパケットルータは、前記パケット送信元および宛先ノード識別子コンパレータに結合され、前記宛先ネットワークノード識別子の値に対する前記送信元ネットワークノード識別子の値にも基づいて、前記受信されたネットワークパケットを転送することを検討すべきかどうかを決定する、項目２に記載の線形センサネットワーク。
（項目５）
前記複数のネットワークノードの各ノードに対して、前記最初のネットワークノードおよび前記最後のネットワークノードを除いて、前記ブランチ上のノードの場所は、前記ブランチを前記ノードに対して第１の部分と第２の部分とに論理的に分け、
前記複数のネットワークノードの各ネットワークノードは、前記最初のネットワークノードおよび前記最後のネットワークノードを除いて、その無線送受信機を介して、前記ブランチの前記第１の部分上のそれぞれのノードから受信されたネットワークパケットを前記ブランチの前記第２の部分上の少なくとも１つのノードに転送し、各ネットワークノードは、前記最初のネットワークノードおよび前記最後のネットワークノードを除いて、その無線送受信機を介して、前記ブランチの前記第２の部分上のそれぞれのノードから受信されたネットワークパケットを前記ブランチの前記第１の部分上の少なくとも１つのノードに転送する、
項目１に記載の線形センサネットワーク。
（項目６）
ネットワークパケットを転送する方法であって、前記方法は、
複数のネットワークノードのそれぞれのものに関連付けられているそれぞれのネットワークノード識別子に従って、ブランチに沿って前記複数のネットワークノードを論理的に配列することであって、前記ブランチは、第１の端部と第２の端部とを有し、前記ネットワークノード識別子は、前記ブランチに沿って、前記第１の端部から前記第２の端部まで単調に変動する、ことと、
前記ブランチの一方の端部に隣接して基地局を配置することであって、前記基地局は、無線送受信機を備え、前記基地局に関連付けられているネットワークノード識別子を有する、ことと、
各ネットワークノード内にそのそれぞれのネットワークノード識別子の表現を記憶することと、
各ネットワークノードにおいて、前記ネットワークノードのセンサを使用して、データを収集することと、
前記複数のネットワークノードのうちの少なくとも１つにおいて、前記基地局において発信するコマンドを受信することに応答して、少なくとも１つのネットワークパケットを使用して、前記ネットワークノードの無線送受信機を介して、前記データを伝送することと、
前記複数のネットワークノードの各ネットワークノードにおいて、前記ブランチの一方の端部における最初のネットワークノードおよび前記ブランチの他方の端部における最後のネットワークノードを除いて、前記ネットワークノードの無線送受信機を介して、ネットワークパケットを転送することであって、各ネットワークパケットは、それぞれの一連のネットワークノードによって転送され、前記一連のネットワークノードのそれぞれのネットワークノード識別子は、前記一連のネットワークノードに沿って単調に変動する、ことと
を含む、方法。
（項目７）
無線線形ネットワークにおける方法であって、前記無線線形ネットワークは、第１のノードと、前記第１のノードに近接する複数の第２のノードと、複数の追加のノードとを備え、全てのノードは、ブランチに沿って配列されており、各ノードは、ノード識別子を有し、前記ノード識別子は、前記ブランチに沿って、前記ブランチの一方の端部から前記ブランチの他方の端部に単調に変動し、前記方法は、複数のパケットを前記第１のノードから前記第２のノードのうちの１つを介してルーティングするためのものであり、前記複数のパケットは、最初のパケットと、少なくとも１つの後続パケットとを備え、
前記方法は、
前記第１のノードが、前記複数のパケットの各パケットを無線で連続的にブロードキャストすることであって、各パケットは、厳密に１回ブロードキャストされ、各パケットは、
前記複数のパケット内のパケットを識別するシーケンス番号と、
前記複数のパケット内のパケットの合計数の指示と
を含む、ことと、
各第２のノードが、前記第１のノードから直接、前記複数のパケットのうちの少なくとも１つのパケットを無線で受信し、それに応答して、肯定応答メッセージを前記第１のノードに無線で伝送することであって、前記肯定応答メッセージは、前記第２のノードのノード識別子を含み、前記第２のノードによってどの前記少なくとも１つのパケットが受信されたかを識別し、前記複数の第２のノードは、それによって、複数の伝送される肯定応答メッセージを集合的に伝送する、ことと、
前記第１のノードが、前記複数の伝送される肯定応答メッセージのうちの少なくとも１つの肯定応答メッセージを受信することと、
前記第１のノードによって受信される少なくとも１つの肯定応答メッセージに従って、少なくとも１つの第２のノードが、前記複数のパケットのうちの全てのパケットを受信した場合、
前記第１のノードが、前記全てのパケットを受信した１つの第２のノードを選択することであって、前記第１のノードのノード識別子と前記選択された１つの第２のノードのノード識別子との間の差異は、前記第１のノードのノード識別子と前記全てのパケットを受信した任意の他の第２のノードのノード識別子との間の差異よりも大きい、ことと、
前記第１のノードが、前記選択された１つの第２のノードに命令メッセージを無線で伝送し、前記選択された１つの第２のノードに、前記複数のパケットを転送するように命令することと、
そうでなければ、
事前決定された補償試行の回数以内で、
前記第１のノードが、前記複数のパケットのセットをブロードキャストすることであって、前記セットは、少なくとも１つの第２のノードによって受信されなかったパケットを含む、ことと
を含む、方法。
（項目８）
前記各第２のノードが前記第１のノードに前記肯定応答メッセージを無線で伝送することは、各第２のノードが、前記第２のノードに割り当てられたタイムスロット中に前記第１のノードに前記肯定応答メッセージを無線で伝送することを含む、項目７に記載の方法。
（項目９）
前記各第２のノードが前記第１のノードに前記肯定応答メッセージを無線で伝送することは、各第２のノードが、衝突検出および衝突回避から成るグループから選択される衝突タイプを伴うキャリアセンスマルチプルアクセスプロトコルに従って、前記肯定応答メッセージを無線で伝送することを含む、項目７に記載の方法。
（項目１０）
前記セットは、少なくとも２つの第２のノードによって受信されなかったパケットの和集合を備えている、項目７に記載の方法。
（項目１１）
各第２のノードは、クロックと、無線送受信機とを備え、前記方法は、各第２のノードが、
前記第２のノードによる前記複数のパケットのうちの前記少なくとも１つのパケットの受信のタイミングに基づいて、前記第２のノードのクロックを調節することと、
いつ前記第２のノードの無線受信機をオンにし、いつ前記無線受信機をオフにするかを制御するために、前記クロックを使用することと
をさらに含む、項目７に記載の方法。
（項目１２）
前記第２のノードが前記最初のパケットを受信しなかった場合、前記クロックを調節することは、前記第２のノードが、サイクルにおいて以前よりも早くその無線受信機をオンにするように前記クロックを調節することを含む、項目１１に記載の方法。
（項目１３）
前記第２のノードが前記複数のパケットのうちの全てのパケットを受信したわけではない場合、前記クロックを調節することは、前記第２のノードが、少なくとも部分的に、前記第２のノードによって受信されなかったパケットの数に依存する量だけ、サイクルにおいて以前よりも早くその無線受信機をオンにするように前記クロックを調節することを含む、項目１１に記載の方法。
（項目１４）
前記クロックを調節することは、前記第２のノードによって受信されなかったパケットの数に少なくとも部分的に依存する量だけ前記クロックを調節することを含む、項目１１に記載の方法。
（項目１５）
前記クロックを調節することは、前記最初のパケットが前記第２のノードによって受信される前に、前記受信機がオンであった時間量に少なくとも部分的に依存する量だけ前記クロックを調節することを含む、項目１１に記載の方法。
（項目１６）
前記第２のノードが前記最初のパケットを受信した場合、前記クロックを調節することは、前記第２のノードが、前記最初のパケットが前記第２のノードによって受信される前に、前記受信機がオンであった時間量に少なくとも部分的に依存する量だけ、サイクルにおいて以前よりも遅くその無線受信機をオンにするように前記クロックを調節することを含む、項目１１に記載の方法。
（項目１７）
無線線形ネットワークにおける方法であって、前記無線線形ネットワークは、第１のノードと、前記第１のノードに近接する複数の第２のノードと、複数の追加のノードとを備え、全てのノードは、ブランチに沿って配列されており、各ノードは、無線送信機と、無線受信機とを備え、ノード識別子を有し、前記ノード識別子は、前記ブランチに沿って単調に変動し、前記方法は、前記第１のノードが前記複数の第２のノードを自動的に識別するためのものであり、前記方法は、
前記第１のノードが、複数の時間的に間隔を置かれた同期メッセージを無線でブロードキャストすることであって、前記複数の同期メッセージは、複数の伝送タイムスロットについての情報と、前記複数の伝送タイムスロットの各伝送タイムスロットに対して、前記伝送タイムスロットが割り当てられる単一のそれぞれの潜在的第２のノードについての情報とを含む、ことと、
前記複数の第２のノードの各第２のノードが、前記第１のノードから直接、前記複数の同期メッセージのうちの少なくとも１つを受信することと、
各第２のノードが、前記複数の伝送タイムスロットのうちのどの１つが前記第２のノードに割り当てられているかを識別することと、
各第２のノードが、前記複数の同期メッセージのうちの前記少なくとも１つの受信に応答して、その割り当てられた伝送タイムスロット中、前記第２のノードの識別子を含む肯定応答メッセージを無線で伝送し、前記複数の第２のノードは、それによって、複数の伝送される肯定応答メッセージを集合的に伝送することと、
前記第１のノードが、前記複数の伝送される前記肯定応答メッセージのうちの少なくとも１つの肯定応答メッセージを受信することと、
前記第１のノードが、肯定応答メッセージが前記第１のノードによって受信された前記複数の第２のノードのセットに優先順位を付けることであって、前記優先順位付けは、肯定応答メッセージが前記第１のノードによって受信された前記第２のノードの識別子に少なくとも部分的に基づく、ことと
を含む、方法。
（項目１８）
各第２のノードは、クロックを備え、前記方法は、各第２のノードが、
前記複数の同期メッセージのうちの前記少なくとも１つの第２のノードによる受信のタイミングに基づいて、前記第２のノードのクロックを調節することと、
いつ前記第２のノードの無線受信機をオンにし、いつ前記無線受信機をオフにするかを制御するために、前記クロックを使用することと
をさらに含む、項目１７に記載の方法。
（項目１９）
各第２のノードは、クロックを備え、前記方法は、各第２のノードが、
前記複数の同期メッセージのうちの前記少なくとも１つの第２のノードによる受信のタイミングに基づいて、前記第２のノードのクロックを調節することと、
いつ前記第２のノードがスリープ状態に入り、いつ前記第２のノードが前記スリープ状態からウェイクするかを制御するために、前記クロックを使用することと
をさらに含む、項目１７に記載の方法。
（項目２０）
前記第２のノードのセットに優先順位を付けることは、前記第２のノードのセットのうちの各第２のノードに対して、前記第２のノードの識別子と前記第１のノードの識別子との間の差異に基づいて、前記第２のノードに優先順位を割り当てることを含み、より大きい差異を伴う第２のノードは、より小さい差異を伴う第２のノードよりも高い優先順位を割り当てられる、項目１７に記載の方法。
（項目２１）
前記第２のノードのセットにおける各第２のノードに対して、前記第１のノードが、優先順位付けメッセージを無線で伝送することをさらに含み、前記優先順位付けメッセージは、前記第２のノードに割り当てられた優先順位を含む、項目２０に記載の方法。
（項目２２）
前記優先順位付けメッセージを伝送した後、前記第１のノードが、同期確認要求メッセージを伝送することと、
前記同期確認要求メッセージの受信に応答して、前記第２のノードのセットにおける各第２のノードが、前記第２のノードに割り当てられた優先順位に関連付けられているそれぞれのタイムスロット中、同期肯定応答メッセージを伝送することと
をさらに含む、項目２１に記載の方法。
（項目２３）
前記第１のノードが、メモリ内に、前記第２のノードのセットにおける各第２のノードについての情報を記憶することをさらに含み、前記情報は、前記第２のノードのノード識別子と、前記第２のノードに割り当てられた優先順位とを備えている、項目１７に記載の方法。
（項目２４）
複数のノードを備えているネットワークにおいて、前記ノードを更新する方法であって、前記方法は、
前記ネットワーク内で複数のメッセージを送信することであって、各メッセージは、更新情報と、未来時の指示とを含む、ことと、
前記ネットワークの各ノードが、
前記複数のメッセージのうちの少なくとも１つを受信することと、
前記複数のメッセージのうちの前記少なくとも１つの中に含まれる前記更新情報を記憶することと、
前記未来時において、前記記憶された更新情報を使用して、前記ノードを更新することと
を含む、方法。
（項目２５）
前記ネットワークの各ノードが、前記未来時においてアウェイクされるための要求を開始することをさらに含む、項目２４に記載の方法。
（項目２６）
各メッセージは、更新のタイプの指示も含み、
各ノードは、前記ノードが前記更新のタイプに一致する場合のみ、前記記憶された更新情報を使用して、前記ノードを更新する、項目２４に記載の方法。
（項目２７）
各ノードは、前記ノードが前記更新のタイプに一致する場合のみ、前記更新情報を記憶する、項目２６に記載の方法。
（項目２８）
ノードの無線線形センサネットワーク内で第１のネットワークステータス情報を送信する方法であって、前記無線線形センサネットワークは、中央コントローラを介して、別のネットワークに通信可能に結合され、前記方法は、
前記ノードのうちの１つが、前記第１のネットワークステータス情報を収集することと、
前記ノードのうちの前記１つが、前記ノードのうちの別の１つからメッセージを無線で受信することと、
前記ノードのうちの前記１つが、前記メッセージ内に前記第１のネットワークステータス情報を記憶し、それによって、修正されたメッセージを生産することと、
前記ノードのうちの前記１つが、前記修正されたメッセージを無線で伝送することと
を含む、方法。
（項目２９）
前記メッセージは、どんなネットワークステータス情報も含んでいない、項目２８に記載の方法。
（項目３０）
前記メッセージは、第２のネットワークステータス情報を含み、前記方法は、
前記ノードのうちの前記１つが、前記第２のネットワークステータス情報を前記第１のネットワークステータス情報と比較することをさらに含み、
前記メッセージ内に前記第１のネットワークステータス情報を記憶し、それによって、修正されたメッセージを生産することは、事前決定された比較スキームに従って、前記第１のネットワークステータス情報が、前記第２のネットワークステータス情報よりも有意である場合のみ、前記メッセージ内に前記第１のネットワークステータス情報を記憶し、それによって、前記修正されたメッセージを生産することを含む、項目２８に記載の方法。
（項目３１）
無線センサネットワークであって、前記無線センサネットワークは、
複数のネットワークセグメントであって、各ネットワークセグメントは、
複数のそれぞれのノードであって、各ノードは、厳密に１つのネットワークセグメントの要素であり、各ノードは、それぞれのセンサと、それぞれの無線送受信機とを備え、各ノードは、その無線送受信機を使用して、そのセンサから導出されるデータを伝送し、各ノードは、そのそれぞれのネットワークセグメントの少なくとも１つの他のノードの無線通信範囲内に配置され、各ノードは、前記ネットワークセグメントの最初のノードと、前記ネットワークセグメントの最後のノードと、前記ネットワークセグメントの中間ノードとのうちの１つを備え、前記最初のノードおよび各中間ノードは、その送受信機を使用して、前記最初のノードからネットワークトポロジ的により遠隔の前記ネットワークセグメントのノードから受信したデータを前記最初のノードにネットワークトポロジ的により近接した前記ネットワークセグメントのノードに転送する、複数のそれぞれのノードを備えている、
複数のネットワークセグメントと、
無線送受信機を備えている基地局であって、前記基地局は、各ネットワークセグメントの前記最初のノードの無線通信範囲内に配置され、その無線送受信機を使用して、前記複数のノードのセンサから収集されたデータを受信する、基地局と
を備え、
各ノードは、繰り返し時間間隔に従って動作し、各時間間隔は、複数のタイムスロットに分割され、各ネットワークセグメントは、前記複数のタイムスロットのうちの固有のタイムスロットに関連付けられ、
各ノードは、前記ノードのネットワークセグメントに関連付けられているタイムスロット中、そのセンサから収集されたデータを伝送し、各時間間隔の残りの間、省電力スリープ状態に入る、
無線センサネットワーク。
（項目３２）
各タイムスロットは、センサデータが１日以内に前記最後のノードから前記基地局に転送されることを可能にするために、十分に長い、項目３１に記載の無線センサネットワーク。
（項目３３）
各省電力スリープ状態は、少なくともＮ−１個のタイムスロットの合計と同程度に長く、Ｎは、各時間間隔におけるタイムスロットの数に等しい、項目３２に記載の無線センサネットワーク。
（項目３４）
各タイムスロットは、複数のサブスロットに分割され、
各ノードは、
（ａ）サブスロット中にその無線送受信機を使用して、前記ノードのネットワークセグメントの別のノードからセンサデータを受信することであって、前記別のノードは、前記ノードよりも前記基地局から遠位にある、ことと、（ｂ）後続サブスロット中に前記無線送受信機を使用して、前記センサデータを前記基地局に向かって転送することとを行う、項目３１に記載の無線センサネットワーク。
【図面の簡単な説明】
【００５９】
本発明は、図面と併せて具体的実施形態の以下の発明を実施するための形態を参照することによって、より完全に理解されるであろう。
【図１】図１は、本発明の実施形態による、いくつかの仮想線形ネットワークの概略ブロック図である。
【図２】図２は、本発明の実施形態による、仮想線形ネットワークのノードによる無線ブロードキャストの概略ブロック図である。
【図３】図３は、本発明の実施形態による、ネットワークパケットの概略図である。
【図４】図４は、本発明の実施形態による、ルーティングテーブルを伴わない、ネットワークノードルーティング決定を例証する、概略フローチャートである。
【図５】図５は、本発明の実施形態による、ネットワークノードにおけるネットワークパケットルーティング論理の概略ブロック図である。
【図６】図６および７は、本発明の実施形態による、より小さい仮想ネットワークパケットのセットに分けられている大きいメッセージの概略図である。
【図７】図６および７は、本発明の実施形態による、より小さい仮想ネットワークパケットのセットに分けられている大きいメッセージの概略図である。
【図８】図８および９は、本発明の実施形態による、タイムスロット配分スキームの概略例証である。
【図９】図８および９は、本発明の実施形態による、タイムスロット配分スキームの概略例証である。
【図１０】図１０は、本発明の実施形態による、仮想線形ネットワーク内でノードを受信することによって送信される肯定応答メッセージを例証する、図２と類似する概略ブロック図である。
【図１１】図１１は、本発明の実施形態による、クロック同期の一部として、受信するノードの受信機がオンである時間に対して、ネットワークパケットがブロードキャストされるタイムスロットを図式的に描写する。
【図１２】図１２は、本発明の実施形態による、ネットワークステータス情報がセンサデータネットワークパケット上で「ピギーバック」することによって送信される方法を例証する、図２と類似する概略ブロック図である。
【図１３】図１３は、本発明の実施形態による、ネットワークノード識別子を示す、図１の仮想線形ネットワークのうちの１つの概略ブロック図である。
【図１４】図１４は、本発明の実施形態による、いくつかのネットワークセグメントと、いくつかのブランチとを含む、仮想線形ネットワークの概略ブロック図である。
【図１５】図１５は、本発明の実施形態による、仮想時間間隔、タイムスロット、およびタイムサブスロットを例証する、概略タイミング図である。
【図１６】図１６は、本発明の実施形態による、図１５のタイミング図による、図１４の線形ネットワークの動作を例証する、概略タイミング図である。
【図１７】図１７は、本発明の実施形態による、線形ネットワークのいくつかの仮想ノードの概略ブロック図である。
【図１８Ａ】図１８Ａおよび１８Ｂは、本発明の実施形態による、図１７のノードによって使用され得るような４位相同期プロトコルを図式的に例証する、タイミング図である。
【図１８Ｂ】図１８Ａおよび１８Ｂは、本発明の実施形態による、図１７のノードによって使用され得るような４位相同期プロトコルを図式的に例証する、タイミング図である。
【図１９】図１９は、本発明の実施形態による、４位相同期プロトコルのノードの状態および状態遷移を図式的に例証する、状態図である。
【図２０】図２０は、本発明の実施形態による、ネットワークノードの概略ブロック図である。
【発明を実施するための形態】
【００６０】
本発明の実施形態によると、無線ネットワークのノードによる使用のための無線通信プロトコルを含む、無線線形センサネットワークを構築し、動作させるための方法および装置が、開示される。線形無線センサネットワークが、ネットワークの各ブランチに沿って単調に変動するネットワークノード識別子を有する、ネットワークノードを含む。ネットワーク識別子は、ノードが、ルーティングテーブルの使用を伴わずにネットワークパケットを転送することを可能にする。低デューティサイクル無線通信プロトコルが、ネットワークパケットが、殆ど電力を消費せずに非常に大きなネットワークの全てのノードにルーティングされることを可能にする。ノード間の、ユニキャストではなくブロードキャスト伝送が、最大可能ホップを使用し、可能な限りノードをスキップし、かつ時間的または空間的に変動する無線伝搬条件に自動的に適合して、好ましい信号伝搬条件を利用し、メッセージを転送する。ノードが、クロック同期専用のパケットを必ずしも交換することなく、そのクロックをその近隣対応物のクロックと同期させる。
【００６１】
（線形ネットワーク、単調に割り当てられたノード識別子、およびルーティング）
本発明のいくつかの実施形態は、殆どの従来のコンピュータネットワークと異なり、無線ネットワークノードの無線センサアレイおよび他のアレイが、多くの場合、その殆どまたは全てのネットワークノードが道路、パイプライン、または鉄道線路等の直線または曲線に沿って配列され、ノードの合計数と比較して、１つまたは少数のブランチ、すなわち、ゼロまたは少数のフォークとともに構築され、これらのアレイおよびネットワークが、比較的に静的であることの実状を知ることが誘引となった。各ノードは、ノードの回線における１つのノードである。しかしながら、ノードは、回線に沿って等距離に分散される必要はない。本明細書で使用される場合、ノードの「近隣対応物」は、同一回線上かつノードの無線通信範囲内のノードである。そのようなネットワークは、本明細書では、「線形ネットワーク」と称される。線形ネットワークは、以下にさらに説明される。
【００６２】
近隣対応物の数は、昼夜間等にノードの無線伝搬距離が変動するにつれて、またはノードのバッテリ充電レベルが変動するにつれて変動し得る。しかしながら、ネットワークが設置されると、ネットワークトポロジ、すなわち、回線に沿ったノードの配列は、典型的には、変化しないか、または、それは、オフィス内もしくは工場フロア上の典型的なローカルエリアネットワーク（ＬＡＮ）の変化率と比較して、まれに変化する。典型的な設置では、ノードの回線のトポロジは、数年にわたって一定のままである。「トポロジ」または「ネットワークトポロジ」は、ここでは、ノードの回線に沿ったノードの配列を指し、ノードの対間の可能な無線通信リンクを考慮する。
【００６３】
ノードの回線の各端部またはそれに近接する少数のノードを除く場合もあるが、回線の各ノードは、比較的に少ない近隣対応物、典型的には、約６つ以下の近隣対応物を有する。回線の端部またはそれに近接するノードは、より少ない近隣対応物を有し、いくつかの場合、１つのみの近隣対応物を有する。
【００６４】
各ノードの観点から、ノードは、そのノードの回線を２つの部分に分ける。典型的には、ノードの近隣対応物の約半分が、回線の一方の部分上にあり、すなわち、ノードの一方の側にあり、すなわち、ネットワークトポロジ的に回線の一方の端部により近接し、ノードの近隣対応物の他の約半分は、ノードの他方の側にあり、すなわち、ネットワークトポロジ的に回線の他方の端部により近接する。ノードは、ノードの対応する側のその近隣対応物を介して、全てのネットワークトラフィックを回線の一方の部分上のノードと交換し、それは、ノードの他方の側のその近隣対応物を介して、全てのネットワークトラフィックを回線の他方の部分上のノードと交換する。ノードの「最近傍近隣対応物」は、ノードに最も近接する近隣対応物である。全てのノードは、回線上の最初および最後のノードを除いて、厳密に２つの最近傍近隣対応物を有する。回線の端部におけるノードは、各々、一方の側にのみ１つ以上の近隣対応物を有し、厳密に１つの最近傍近隣対応物を有する。
【００６５】
ノードは、必要に応じて、ネットワークメッセージを転送する。典型的なノードの回線は、数十、数百、数千以上のノードを含み得る。その結果、殆どのネットワークメッセージは、それらがそれらの最終宛先に到達する前に、複数回転送される。
【００６６】
第１のノードが、第２のノードを介して第３のノードに通信可能に結合される場合、第１のノードは、ネットワークトポロジ的に第２のノードに隣接するが、ネットワークトポロジ的に第３のノードに隣接しない。第１のノードは、ネットワークトポロジ的に、第３のノードよりも第２のノードに近接する。
【００６７】
本明細書で使用される場合、「ノード」および「ネットワークノード」は、同義語である。本明細書で使用される場合、ブランチは、線形ネットワークの厳密に線形の部分、すなわち、ネットワークの未分化部分である。線形ネットワークは、１つ以上のブランチを含み得る。センサネットワークが、基地局を含むか、またはそれに接続される場合、ネットワークの所与のブランチの殆どのノードに対して、その近隣対応物のいくつかは、ネットワークトポロジ的に基地局により近接し、他の近隣対応物は、ネットワークトポロジ的に基地局からより遠くにある。典型的には、ブランチの１つのノード（時として、「最初のノード」と称される）は、ネットワークトポロジ的に基地局に隣接し、かつネットワークの１つの他のノードに隣接する。典型的には、１つの他のノード、すなわち、「エンドノード」は、ノードの回線の他方の端部、すなわち、ブランチの他方の端部に位置し、ネットワークトポロジ的に１つの他のノードにのみ隣接する。ブランチは、本明細書においてより詳細に議論される。
【００６８】
述べたように、そのようなネットワークは、本明細書では、線形ネットワークと称される。本明細書で使用される場合、線形ネットワークは、少なくとも５０：１のノード：ブランチ比を有する。本開示によると、６ＬｏＷＰＡＮ（低電力無線パーソナルエリアネットワークにわたるＩＰｖ６）等の既存の無線通信プロトコルが、修正され、新しいプロトコルが、実装され、従来の通信プロトコルによるものよりも、より多くのノードをサポートし、より応答性を高くし、よりエネルギー効率的に動作させるために、これらのネットワークの線形特性を利用する。改良されたプロトコルに従って動作するノードおよびネットワークもまた、説明される。
【００６９】
図１は、いくつかの仮想線形ネットワーク１００、１０２、および１０４の概略表現を含む。省略記号によって示されるように、全てのノードが、示されるわけではない。例えば、線形ネットワーク１００の４つのノード１０６、１０８、１１０、および１１２は全て、破線１１４によって表される、単一のブランチに沿って配列される。線形ネットワーク１０２は、３つのブランチ１１６、１１８、および１２０を含み、線形ネットワーク１０４は、３つのブランチ１２２、１２４、および１２６を含む。ブランチ１１６、１１８、および１２０は、共通して１つ以上のノードを有することに留意されたい。例えば、ノード１は、ブランチ１１６、１１８、および１２０の要素であり、ノード１０は、ブランチ１１８および１２０の要素である。いくつかの実施形態では、複数のブランチ間で共通であるノードは、以下に議論されるように、各ブランチに対して１つの複数のネットワークノード識別子を有する。
【００７０】
線形ネットワーク１００−１０４の各々は、それぞれ、少なくとも１つの基地局１２８、１３０、１３２、および１３４を有するが、基地局は、線形ネットワークに対して要求されない。基地局はまた、本明細書では、「エッジルータ」および「中央コントローラ」とも称され、線形ネットワーク１００、１０２、または１０４等の線形ネットワークをインターネットプロトコルバージョン６（ＩＰｖ６）ネットワーク等のローカルエリアネットワーク（ＬＡＮ）または広域ネットワーク（ＷＡＮ）１３６によって例示される別のネットワークに接続し得る。
【００７１】
各ノード１０６−１１２、ノード１、ノード２等は、温度センサ、圧力センサ、または磁気計等のセンサ（図示せず）を含む。多くの場合、基地局１２８等の基地局は、ノード１１０へのコマンド等、データを収集し、収集されたデータを基地局１２８に戻すためのコマンドをノードに送信する。
【００７２】
ノード１０６−１１２、ノード１、ノード２等内の無線送信機および受信機（送受信機、図１に図示せず）が、ノード間およびノードと基地局１２８、１３０、１３２との間に無線通信を提供する。送受信機の限定された無線範囲に起因して、これらのコマンドのいくつかは、それらのそれぞれの宛先ノードに到達する前に、ブランチに沿って、ノード１０６および１０８のうちの１つ以上のもの等によって、ノードからノードに転送される必要があり得る。同様に、ノードによって送信されたデータは、ブランチに沿って基地局に転送される必要があり得る。
【００７３】
ノード内の無線機に対する電力消費制約は、無線機の無線範囲を限定する。各ノードは、ネットワークのノードの残りの全てまたは大部分とではなく、比較的に少数の近傍ノードのみ、場合によっては２つの最近傍近隣対応物のみと直接無線で通信することが可能であり得る。殆どのノードは、基地局から遠隔にありすぎ、基地局と直接無線で通信することができない。基地局内の高出力送信機であっても、遠隔ノードに到達することが可能ではない場合がある。その結果、多くのメッセージ、特に、基地局とブランチに沿って遠く離れたノードとの間のメッセージは、その宛先に到達する前に、複数回（「ホップ」）、等しい数の中間ノードによって、転送されなければならない。各ホップは、メッセージ待ち時間に影響する。
【００７４】
しかしながら、述べたように、本発明の実施形態によると、通信プロトコルおよびノードは、特に、ノードが各ブランチに沿って単調に番号付けられる場合、これらのネットワークの線形特性を利用するように構成され得る。以下の実施例では、ノードは、それらのそれぞれのノード番号（ネットワークノード識別子）が、ベースノードから離れて、ブランチの一方の端部からブランチの他方の端部への方向において、ブランチに沿って単調に増加するように番号付けられる。代替として、ノード番号がこの方向に沿って単調に減少するノード番号付けスキームが、使用され得る。分かるであろうように、いずれのタイプの単調ノード識別スキームも、ルーティングテーブルを要求することなく、メッセージを受信するノードによってルーティング決定を行うことを促進する。
【００７５】
本明細書で使用される場合、第１の端部から第２の端部に「ネットワークノード識別子をブランチに沿って単調に変動させること」は、ベースノードから離れて、ブランチの第１の端部からブランチの第２の端部への方向に沿って、ネットワークノード識別子を単調に増加させること、またはベースノードから離れて、ブランチの第１の端部からブランチの第２の端部への方向に沿って、ネットワークノード識別子を単調に減少させることのいずれかを意味する。
【００７６】
例えば、図２に図式的に例証されるように、線形ネットワーク２００の１０個のノードが、ネットワークブランチ２０２に沿って単調に増加するネットワークノード識別子Ｎ１−Ｎ１０を割り当てられると仮定する。当然ながら、ブランチ２０２は、多くのさらなるノードを含む。基地局２０４も、ゼロ等の関連付けられているネットワークノード識別子を有し得る。各ノードＮ１−Ｎ１０は、他のノードＮ１−１０、およびノードのいくつかに対して、基地局２０４と無線で通信するための送受信機を含む。多くの文脈では、送受信機の電力および感度ならびにノード配置を所与として、各ノードＮ１−１０が、ブランチ２０２に沿って、各方向における約３つのノードの無線範囲内にあることが予期される。
【００７７】
ノードＮ４が、ブロードキャストするノードのブランチ２０２に沿ってより遠くに位置するノードＮ９に宛先指定されたメッセージをブロードキャストし、ブロードキャストするノードＮ４の両側のノード（例えば、ノードＮ２、Ｎ３、Ｎ５、Ｎ６、およびＮ７）が、メッセージを受信する場合、ブロードキャストするノードの番号（４）を下回るノード番号（この例では、それぞれ、２および３）を伴う受信するノードＮ２およびＮ３は、メッセージを無視することができる。なぜなら、それらがブロードキャストするノードＮ４よりも宛先ノードＮ９から遠くにあるからである。メッセージをノードＮ２またはＮ３のいずれかに転送することは、逆効果であろう。一方、ブロードキャストするノードの番号（４）を上回るノード番号（この例では、それぞれ、５、６、および７）を伴う受信するノードＮ５、Ｎ６、およびＮ７は、これらのノードがブロードキャストするノードＮ４よりも宛先ノードＮ９に近接するので、潜在的転送するノードである。潜在的転送するノードのノード番号は全て、ブロードキャストするノードのノード番号を上回る。
【００７８】
ノードＮ１−Ｎ１０は、ネットワークパケットを送受信することによって通信する。図３は、例示的ネットワークパケット３００の概略図である。ネットワークパケット３００は、ブロードキャストするノードＮ４のノード番号３０２（図２の実施例では４）（「送信元ノード識別子」）と、意図される宛先ノードＮ９のノード番号３０４（図２の実施例では９）（「宛先ノード識別子」）とを含む。ネットワークパケット３００は、他のヘッダ情報３０６と、ペイロード３０８とをさらに含み得る。ペイロード３０８は、特定のノードにそのセンサを用いてデータを収集することを命令するコマンド等の１つ以上のコマンド、および／またはノードから基地局に送信される収集されたデータ等のデータを含み得る。
【００７９】
ネットワークパケット３００内の情報に基づいて、ネットワークパケットを受信する各ノードは、ネットワークパケットがルーティングされるべき方向、すなわち、基地局から離れるか、または基地局に向かうかを自動的に決定することができる。宛先ノード識別子３０４が送信元ノード識別子３０２を上回る場合、メッセージは、基地局から離れる方向にルーティングされるべきである。一方、宛先ノード識別子３０４が送信元ノード識別子３０２を下回る場合、メッセージは、基地局に向かう方向にルーティングされるべきである。当然ながら、ノード番号が基地局に向かう方向に沿って単調に増加する、上で説明される代替ノード番号付けスキームの場合、ルーティング方向は、逆転される。
【００８０】
さらに、ネットワークパケット３００内の情報および受信するノードの独自のノード識別子番号に基づいて、各受信するノードは、メッセージを無視するか、または潜在的転送のためのメッセージのコピーを記憶するかを自動的に決定することができる。図２に関して述べたように、伝送ノードの識別子を下回るノード識別子番号を伴うノードは、伝送ノードのそれを上回るノード識別子番号を有するノードに宛先指定されるメッセージを安全に無視することができる。同様に、伝送ノードの識別子を上回るノード識別子番号を伴うノードは、伝送ノードのそれを下回るノード識別子番号を有するノードに宛先指定されるメッセージを安全に無視することができる。ノードが、受信されたメッセージを安全に無視することができない場合、ノードは、本明細書に説明されるように、ノードがネットワークに沿ってメッセージを転送するように求められる場合に備えて、メッセージを記憶すべきである。当然ながら、受信するノードの識別番号が、宛先ノード識別子番号に等しい場合、受信するノードは、メッセージのコマンド、データ等を処理すべきである。
【００８１】
各ノードは、その独自のネットワークノード識別番号を用いてプロビジョニングされる。各ノードは、したがって、メモリ内等に、それらのそれぞれのネットワークノード識別子の表現を記憶する。始動段階中、ネットワークノードは、自動近隣対応物発見プロセスを実行し、基地局にネットワークブランチのトポロジについての情報を転送する。
【００８２】
新たに図３を参照すると、宛先ノード番号３０４（９）が、ブロードキャストするノードの番号３０２（４）を上回り、ベースノードから離れる方向におけるルーティングを示す場合、ブロードキャストするノードの番号（４）を下回るノード番号（２および３）を有する受信するノードＮ２およびＮ３は、メッセージ３００を安全に無視することができる一方、ブロードキャストするノードの番号（４）を上回るが、宛先ノード番号（９）を下回るノード番号（５、６、および７）を有する受信するノードＮ５、Ｎ６、およびＮ７は、潜在的転送するノードである。
【００８３】
さらに、２つ以上の潜在的転送するノードＮ５、Ｎ６、およびＮ７が、ブロードキャストを受信する場合、受信側ノード間で最高の番号を付けられたノードＮ７は、ブランチに沿って最も遠くにあり、すなわち、宛先ノードＮ９に最も近接し、したがって、ブロードキャストするノードＮ４によってメッセージを転送するために選択され、それによって、ノードＮ５およびＮ６をスキップし得る。この機構によって、各ホップは、ブランチに沿ったノードの番号の観点から、ブロードキャストするノードＮ４の無線範囲内で、可能な限りメッセージを移動させることができる。したがって、具体的な１つ以上の意図される受信機にネットワークパケットを伝送（ユニキャストまたはマルチキャスト）するのではなく、ブロードキャストすることは、存在するとき、好ましい伝搬条件を利用する。対照的に、従来技術のネットワークは、ホップあたり１つのみのノードにメッセージを転送するか、またはそれらは、パケットを１つ以上の規定された受信側ノードにのみ伝送する。ここで提示される従来技術に優る改良は、ブロードキャストすることと、各ネットワークブランチの長さに沿ってノードを単調に番号付けることとによって可能にされる。実施形態のこれらおよび他の構造的特徴は、ネットワーク効率を改良し、電力消費を低減させ、他の利益を提供する。
【００８４】
ブランチのノードは、ルーティング決定を行うために、いかなるルーティングテーブルも必要としないことに留意されたい。ネットワークパケットの送信元３０２（図３）および宛先３０４のノード識別子間の単純な比較は、ネットワークパケット３００がブランチに沿って進行すべき方向、すなわち、基地局に向かうか、またはそれから離れるかを示す。ネットワークパケットの進行方向が決定されると、受信するノードのネットワーク識別子とネットワークパケットの送信元および宛先ノード識別子との間の単純な比較は、受信するノードが潜在的転送するノードであるかどうかを示す。本質的に、ネットワークパケットは、それらがルーティング決定をノードのために殆ど自明なものにする情報を含む点で、「セルフルーティング」である。
【００８５】
図４は、ルーティングテーブルを伴わない、ネットワークノードがルーティング決定を行い得る方法を例証するフローチャートを含む。４００において、受信されたネットワークパケットの宛先ノード識別子３０４（図３）が、その送信元ネットワークノード識別子３０２を上回る場合、ネットワークパケットの進行方向は、基地局から離れ、制御は、４０２に移り、そうでなければ、進行方向は、基地局に向かい、制御は、４０４に移る。４０２において、受信ネットワークノードのネットワーク識別子が、送信元ネットワークノード識別子３０２を上回る場合、制御は、４０６に移り、そうでなければ、受信ネットワークノードは、送信元ネットワークノードの「他方の側」にあり、ネットワークパケットを効率的に転送する位置になく、その場合、制御は、４０８に移り、ネットワークパケットは、無視される。４０６において、受信ネットワークノードのネットワーク識別子が、宛先ノード識別子３０４を下回る場合、受信するノードは、転送候補であり、制御は、４１０に移り、そうでなければ、受信するノードは、宛先ネットワークノードを「越え」ており、受信されたネットワークパケットを無視することができ、その場合、制御は、４０８に移る。
【００８６】
基地局に向かって進行するネットワークパケットに対して、４０４において、受信ネットワークノードのネットワーク識別子が、送信元ネットワークノード識別子３０２を下回る場合、制御は、４１２に移り、そうでなければ、受信ネットワークノードは、送信元ネットワークノードの「他方の側」にあり、ネットワークパケットを効率的に転送する位置になく、その場合、制御は、４０８に移り、ネットワークパケットは、無視される。４１２において、受信ネットワークノードのネットワーク識別子が、宛先ノード識別子３０４を上回る場合、受信するノードは、転送候補であり、制御は、４１０に移り、そうでなければ、受信するノードは、宛先ネットワークノードを「越え」ており、すなわち、基地局に近接しすぎであり、受信されたネットワークパケットを無視することができ、その場合、制御は、４０８に移る。
【００８７】
このフローチャートは、ネットワークノード識別子が、ブランチに沿って基地局から離れる方向に単調に増加すると仮定する。ネットワークノード識別子が、基地局に向かう方向に単調に増加する場合、４０２、４０４、４０６、および４１２における比較の意味は、逆転される。
【００８８】
図５は、本発明の実施形態による、ネットワークノード５００の概略ブロック図である。いくつかの実施形態では、図５のブロックは、図４のフローチャートに関して本明細書に説明されるネットワークパケットルーティング論理を実装する。無線送受信機５０２が、基地局および他のノードから、伝送（典型的には、ブロードキャスト伝送）を受信する。ネットワークパケットを含む受信された伝送に対して、ネットワークパケット送信元識別装置５０４が、ネットワークパケットを伝送したノードまたは基地局のネットワークノード識別子を識別するために、受信されたネットワークパケットのそれらを検証する。同様に、ネットワークパケット宛先識別装置５０６が、受信されたネットワークパケットのうちの１つを検証し、ネットワークパケットが宛先指定されるノードまたは基地局のネットワークノード識別子を識別する。
【００８９】
ネットワークパケット送信元および宛先識別子コンパレータ５０８が、ネットワークパケット送信元識別装置５０４およびネットワークパケット宛先識別装置５０６によって識別される送信元ネットワーク識別子と宛先ネットワーク識別子とを比較する。各受信されたネットワークパケットに対して、ネットワークパケット送信元および宛先識別子コンパレータ５０８は、ネットワークパケットが転送されるべき方向、すなわち、基地局に向かうか、または基地局から離れるかを決定する。
【００９０】
ネットワークノード識別子コンパレータ５１０が、受信ネットワークノードのネットワーク識別子の記憶された表現５１２を送信元ネットワーク識別子および宛先ネットワーク識別子と比較する。各受信されたネットワークパケットに対して、ネットワークノード識別子コンパレータ５１０は、ネットワークパケットが転送されるべき方向に対して、受信ネットワークノードが、（ａ）伝送ネットワークノードと宛先ノードとの間にあるか、（ｂ）伝送ネットワークノードの「前」にあるか、または（ｃ）宛先ネットワークノードを「越える」かを決定する。
【００９１】
ネットワークパケットルータ５１４が、（ａ）宛先ネットワークノード識別子の値に対する送信元ネットワークノード識別子の値、（ｂ）ノードのネットワークノード識別子の表現に対する送信元ネットワークノード識別子の値、および（ｃ）ノードのネットワークノード識別子の表現に対する宛先ネットワークノード識別子の値に基づいて、所与の受信されたネットワークパケットを転送することを検討すべきかどうかを決定する。
【００９２】
述べたように、いかなるルーティングテーブルも、受信されたネットワークパケットを転送することを検討すべきかどうかを決定するために、ネットワークパケットルータ５１４に対して必要とされない。例えば、比較および決定は、図４のフローチャートを参照して説明されるようなものであり得る。
【００９３】
従来技術とは異なり、本発明の実施形態によるネットワークパケットルーティング論理は、ネットワークまたはブランチ内のノードの数に依存しない。図４に描写される論理は、ネットワークまたはブランチ内のノードの数とは無関係である。本発明の実施形態によるセンサネットワークは、数千以上のネットワークノード、さらには数百万のネットワークノードを含み得ることに留意されたい。一方、従来技術のルーティングアルゴリズムは、ルーティングテーブルに依拠し、そのサイズは、ネットワークサイズに依存する。
【００９４】
センサネットワークのノード内のメモリサイズは、典型的には、制約される。したがって、大きいルーティングテーブルを記憶することは、センサネットワークに対して問題を引き起こす。加えて、メモリおよび命令を実行するプロセッサのために利用可能な電力は、典型的には、センサネットワークのノードにおいて限定される。したがって、ルーティングテーブル内のエントリの追加、削除、およびトラバースは、センサネットワークに対して問題を引き起こす。従来のセンサネットワークノードにおける電力およびメモリ制約を前提とすると、最大約１０〜３０個のノードしか、従来技術のルーティングテーブルによってサポートされることはできない。これらおよび他の問題は、本発明の実施形態によって解決される。
【００９５】
本明細書に説明されるルーティング論理を使用して、ブランチに沿ったノードが、多くの場合、ホップ２０６、２０８、および２１０（図２）によって例示される、一連のホップを利用して、ネットワークパケットをその宛先に転送する。例えば、基地局２０４は、ネットワークパケットをブロードキャストし得る。ブロードキャストを受信する最高の番号を付けられたノード（Ｎ４）は、それをブロードキャストすることによってネットワークパケットを転送し得る。ノードのブロードキャストを受信する最高の番号を付けられたノード（Ｎ７）は、ネットワークパケットの宛先ノード識別子フィールド３０４（図３）に規定されるように、ネットワークパケットが宛先ノード（Ｎ１０）によって受信されるまで、ネットワークパケット等を転送し得る。
【００９６】
ノード、例えば、ノードＮ７がネットワークパケットを受信した後、ノードＮ７は、ネットワークブランチ２０２を２つの部分に分けていると見なされ、一方の部分２１２（図２）は、基地局側で、基地局２０４からネットワークノードＮ６に延び、ネットワークノードＮ６は、この例では、ノードＮ７の最近傍近隣対応物であり、他方の部分２１４は、他の最近傍近隣対応物Ｎ８からブランチの他方の端部に延び得る。各ネットワークノードは、最初のネットワークノードＮ１および最後のネットワークノードを除いて、ブランチの第１の部分２１２内のノードから受信されたパケットを他方の部分２１４内のノードに転送し、それは、他方の部分２１４内のノードから受信されたネットワークパケットを第１の部分２１２内のノードに転送する。
【００９７】
ブランチ２０２に沿った基地局２０４から１つ以上のノードＮ１−Ｎ１０へのコマンドを伴うネットワークパケット、または１つ以上のノードＮ１−Ｎ１０によって基地局２０４に送信されるセンセデータを伴うネットワークパケット等の他のネットワークパケットが、ブランチ２０２に沿って転送される。この方法において、各ネットワークパケットは、それぞれの一連のネットワークノードによって転送され、それらのそれぞれのネットワークノード識別子は、一連のネットワークノードに沿って単調に変動する。つまり、各ネットワークパケットは、一連のネットワークノード（上記の実施例ではＮ４およびＮ７）によって転送される。各一連のノードのネットワークノード識別子は、各ネットワークパケットの経路に沿って単調に変動する。例えば、これらのノードＮ４およびＮ７のネットワーク識別子は、ネットワークパケットの経路に沿って、基地局２０４から宛先ノードＮ９まで単調に増加する。
【００９８】
線形ネットワークを設計またはプロビジョニングするとき、隣接するノードに、２以上異なるノード識別子番号を割り当てることが賢明であり得る。このようにノード識別子番号をスキップすることは、既存のノードに再番号付けすることなく、以前の隣接するノード間に、後にノードを追加することを促進する。述べたように、開示されるルーティング論理は、ネットワークノードの数とは無関係である。したがって、ノードがネットワークに追加される場合、またはそれから削除される場合、ルーティング論理は、変更される必要はなく、いかなるルーティングテーブルも、改訂される必要はない。
【００９９】
多くの要因が、無線範囲に影響を及ぼし得る。例えば、電力供給源電圧は、送信機電力出力および受信機感度に影響を及ぼし得る。近傍の重機からの無線雑音は、無線受信に干渉し、受信機が近傍のノードから強い信号のみを受信するように限定し得る。無線信号伝搬は、昼夜間に、例えば、大気変化に起因して、変動し得る。無線範囲が、昼夜間等に経時的に、またはバッテリ電圧の変動もしくは断続的無線雑音の結果として変動するので、図２に関して議論されるプロトコルは、適合し、各ホップ時、可能な限り多くのノードを自動的にスキップすることに留意されたい。所与のメッセージに対するスキップされるノードの数も、局所雑音レベルまたはエネルギー回収装置に利用可能な日光の差異等に起因して、空間的に、すなわち、ブランチ２０２に沿って変動し得る。
【０１００】
（低デューティサイクル通信プロトコル）
いくつかの無線デューティサイクルプロトコルは、比較的に小さい最大パケットサイズをサポートする。しかしながら、比較的に大量のデータが、無線線形ネットワークに沿って送信されるべきである場合、データは、無線プロトコルの最大パケットサイズに一致するように、いくつかのパケットに分けられ（フラグメント化され）、パケットは、連続的に送信され得る。例えば、ＣｏｎｔｉｋｉＭＡＣプロトコルは、ＩＰｖ６パケットよりもはるかに小さい最大パケットサイズを可能にし、線形ネットワークが、ＩＰｖ６ネットワークからネットワークトラフィックを搬送するように求められ得る。ＩＰｖ６パケットは、したがって、フラグメント化し、複数のＣｏｎｔｉｋｉＭＡＣのようなパケットを使用して送信され得る。例えば、基地局１３２（図１）は、ＷＡＮまたはＬＡＮ１３６からＩＰｖ６パケットを受信し、ネットワーク１０４のノードのうちの１つ以上のもの（ノード１・・・ノード２１）への伝送のために、パケットを複数のより小さいＣｏｎｔｉｋｉＭＡＣのようなパケットにフラグメント化し得る。
【０１０１】
一連の連続的な密接に間隔を置かれた（時間において）パケットとして複数のパケットを送信することは、エネルギー効率的であり得る。なぜなら、受信側ノードがその無線をオンにすると、受信機は、伝送ノードがパケットを伝送することを中止するまで、または少なくとも受信するノードがパケットを受信することを中止するまで、連続的なパケットを受信できるからである。受信するノードは、一連のパケットの各パケットを受信した後ではなく、最後の連続的パケットを受信した後、肯定応答を送信することができる。
【０１０２】
本発明の実施形態によると、図６に例示されるように、一連のパケットがノードによって伝送されるとき、一連のパケットの各パケットは、一連のパケット内のパケットを識別するパケットシーケンス番号と、一連のパケット内のパケットの合計数の指示とを含む。ここでは、大きいメッセージ６００が、パケット６０２、６０４、および６０６によって例示される一連のパケットにフラグメント化されている。
【０１０３】
大きいメッセージ６００が、ＩＰｖ６ネットワーク等を介して、別のネットワーク内のパケットとして送信され得るが、明確化のために、それは、この例では、「大きいメッセージ」と称され、線形ネットワークを介して送信されるより小さいパケット６０２−６０６は、「パケット」と称される。さらに、一連のパケットは、必ずしも、より大きいメッセージのフラグメントを表す必要はないことに留意されたい。例えば、一連のパケットの各パケットは、異なるノードに宛先指定され得るか、または、それは、別様に、一連のパケットの他のパケットとは無関係であり得る。
【０１０４】
継続して図６を参照すると、パケットシーケンス番号は、最初のパケットに対する番号であり得る。例えば、最初のパケットは、１と番号付けられ得、一連のパケットの各連続的パケットは、２、３、４等と番号付けられ得る。つまり、各一連のパケットは、パケットシーケンス番号１で始まる。一連のパケットの合計数の指示は、複数のパケットの最終パケットのパケットシーケンス番号に等しくあり得る。当然ながら、代替として、ゼロベースの番号付けまたは別のパケット番号付けスキームが、使用され得る。
【０１０５】
代替として、図７に例示されるように、パケット７０２−７０６は、シーケンス番号がある一連のものより大きいものに及ぶように、番号付けられ得る。これらの場合、各パケットは、一連のパケットのうちの最初のパケットのシーケンス番号と一連のパケットの合計数と、または、一連のパケットのうちの最後のパケットのシーケンス番号と一連のパケットの合計数と、または、一連のパケットのうちの最初のパケットのシーケンス番号と最後のパケットのシーケンス番号と、または、いくつのパケットが一連のパケット内にあるかと（すなわち、各パケットは、複数のパケットにおけるパケットの合計数の指示を含むべきである）、一連のパケットの開始に対する現在のパケットの位置と（すなわち、各パケットは、複数のパケット内のパケットを識別するシーケンス番号を含むべきである）を受信機が計算することを可能にするある他の情報の組み合わせを含むべきである。
【０１０６】
（関連ネットワークパケットのグループの転送）
図２に関して議論されるように、本発明の実施形態は、ネットワークパケットをブロードキャストすることによって転送し、したがって、ネットワークパケットは、各ホップにおいて可能な限り遠く転送されることができる。いくつかの実施形態では、ブロードキャストされるネットワークパケットを受信し、受信されたネットワークパケットを転送する候補である全てのネットワークノード（例えば、図２のノードＮ５、Ｎ６、およびＮ７）は、肯定応答メッセージをブロードキャストするノードＮ４に返送し、それら自身を識別し、したがって、ブロードキャストするノードＮ４は、転送するノードであるべき、受信するノードのうちの１つを選択することができる。他の条件が同じなら、ブロードキャストするノードＮ４は、ブロードキャストするノードＮ４から最も遠い受信するノード（この例ではＮ７）を選択するが、概して、宛先ノードを越えるノード（この例ではＮ９）を選択しない。
【０１０７】
いくつかの実施形態では、各ノードは、他のノードからの干渉を防止するように、それがブロードキャストし得るタイムスロットを配分される。例示的タイムスロット配分スキームが、図８に図式的に描写される。この例では、タイムスロット０中、基地局が、伝送し得る。タイムスロット１中、ノードＮ１が、伝送し得る。タイムスロット２中、ノードＮ２が、伝送し得、以下同様である。追加のタイムスロットが、必要に応じて、追加の基地局のために追加され得る。グループ８００のタイムスロットが、繰り返される。随意に、遅延時間８０２が、タイムスロットのグループの繰り返し間に生じる。遅延時間８０２中、いくつかのノードは、それらのそれぞれのセンサを使用し、データを収集し、および／または省電力スリープ状態に入り得る。全てのタイムスロットは、必要ではないが、等しい持続時間であり得る。例えば、タイムスロット０は、基地局が、ネットワークノードの各々が送信し得るよりも多くのメッセージまたは長いメッセージを送信することを可能にするために、他のタイムスロットの各々よりも長くあり得る。
【０１０８】
基地局から遠いノードからのブロードキャストが、基地局に近接するノードからのブロードキャストに干渉する可能性が低い長いブランチに対して、タイムスロットは、複数のノードによって共有され得る。例えば、ブロードキャストが、「ｎ」個のノードに及ぶ距離に伝搬する可能性が低い場合、図９に図式的に描写されるタイムスロット配分スキームが、使用され得る。この例では、ブランチに沿った全「ｎ」個に１個のノードが、共通のタイムスロットを共有する。したがって、タイムスロットの数は、ブランチ上のノードの数を下回り得る。
【０１０９】
再び図２に目を向け、継続して図８および９を参照すると、ブロードキャストするノード、例えば、ノードＮ４が、ノードＮ９に宛先指定されるネットワークパケットを送信または転送していると仮定する。ノードＮ４は、そのタイムスロット中にネットワークパケットをブロードキャストし、ノードＮ５、Ｎ６、およびＮ７は、ブロードキャストを受信する。それらのそれぞれのタイムスロット中（現在のグループ８００のタイムスロット中、または代替として、後続グループ８００のタイムスロット中）、ノードＮ５、Ｎ６、およびＮ７は、それぞれの肯定応答メッセージをブロードキャストし、それらのそれぞれのネットワークノード識別子を示し、ネットワークパケットの受信を肯定応答する。肯定応答メッセージは、ノードＮ４にアドレスされ、ノードＮ４は、複数の肯定応答メッセージを受信する。
【０１１０】
ノードＮ４は、ノードのうちの１つ（Ｎ５、Ｎ６、またはＮ７）を転送するノードとして選択し、ノードＮ４の後のタイムスロット中、ノードＮ４は、選択されたノードを示すメッセージをブロードキャストする。このブロードキャストメッセージは、選択された転送するノードにトークンを渡すものと見なされ得る。述べたように、他の条件が同じなら、ノードＮ４は、ブランチに沿って、宛先ノードＮ９に向かって最も遠く、宛先ノードＮ９を越えないノードを選択する。この例に対して、ノードＮ７が選択されると仮定する。
【０１１１】
トークンを受信すると、ノードＮ７は、ノードＮ９がネットワークパケットを受信するまで、ノードＮ４によって以前に実施されたプロセスを繰り返し、以下同様である。随意に、ノードＮ７は、第２の肯定応答メッセージを送信することによって、または肯定応答をそのネットワークパケットのブロードキャスト内に含めること等によって、トークンの受信を肯定応答する。推定されるように、ノードＮ４は、ネットワークパケットのブロードキャストを受信し、したがって、ネットワークパケットが転送されたこと、または少なくともノードＮ４が現在トークンを有しており、したがって、Ｎ４がネットワークパケットを転送することに関与していることの確認を受信する。
【０１１２】
図６および７に関して述べたように、一連の連続的な密接に間隔を置かれた（時間において）パケットとして複数のネットワークパケットを送信することは、エネルギー効率的であり得る。いくつかの実施形態では、複数のネットワークパケットが、このエネルギー効率を利用するために、単一のタイムスロット中に単一のネットワークノードによってブロードキャストされる。例えば、図８および９を参照すると、複数のネットワークパケットが、単一のタイムスロット中に単一のネットワークノードによってブロードキャストされ得る。しかしながら、ブロードキャストを受信する全てのネットワークノードが、全てのネットワークパケットを受信するわけではない場合がある。例えば、バースト局所電磁干渉（ＥＭＩ）が、受信するノードのいくつかが全てのネットワークパケットを受信することを妨害し得る。別の例では、ノードのいくつかが、省電力スリープ状態からウェイクするのが遅すぎて、全てのネットワークパケットを受信しないことがあり、または、いくつかのノードが、全てのネットワークパケットを受信する前に省電力スリープ状態に入り得る。
【０１１３】
いくつかの実施形態では、ネットワークパケットのいずれかを受信するノードは、次いで、それらのそれぞれのネットワークノード識別子およびそれらがどのネットワークパケットを受信したかを示す肯定応答メッセージをブロードキャストする。ネットワークパケット７０２−７０６（図７）、すなわち、ネットワークパケットシーケンス番号３７９２−３８４８が、ノードＮ４（図２）によってブロードキャストされ、ネットワークパケットのいくつかまたは全てが、例えば、図２に示されるようなノードＮ５、Ｎ６、およびＮ７のそれぞれによって受信されると仮定する。図１０は、ノードＮ５がネットワークパケットシーケンス番号３７９５−３８３８を受信し、ノードＮ６がネットワークパケットシーケンス番号３７９２−３８４８を受信し、ノードＮ７がネットワークパケットシーケンス番号３７９２−３７９４および３８４０を受信するこの例を図式的に例証する。
【０１１４】
それらのそれぞれの肯定応答メッセージ１０００、１００２、および１００４において、ノードＮ５、Ｎ６、およびＮ７は、それらのそれぞれのネットワークノード識別子およびそれらがどのネットワークパケットシーケンス番号を受信したかを示す。（図２とは異なり、ノードＮ５、Ｎ６、およびＮ７のアンテナからの放射を示す記号は、図１０において伝搬距離を示さない。）したがって、集合的に、ノードＮ５、Ｎ６、およびＮ７は、複数の肯定応答メッセージをブロードキャストし、ノードＮ４は、この複数の肯定応答メッセージを受信する。肯定応答メッセージは、それぞれの受信するノード（Ｎ５、Ｎ６、およびＮ７）のタイムスロット中にブロードキャストされ得る。随意に、または代替として、全ての肯定応答ノードは、衝突検出および／または衝突回避を伴うキャリアセンスマルチプルアクセスプロトコルに従って、ブロードキャスト媒体へのアクセスのために競合し得る。
【０１１５】
ノードＮ５、Ｎ６、およびＮ７のうちの少なくとも１つが、全てのネットワークパケットを受信する場合、ノードＮ４は、全てのネットワークパケットを受信し、ブランチ２０２に沿って宛先ノードＮ９に向かって最も遠いノードを選択する。この場合、ブロードキャストするノードＮ４のノード識別子と選択されたノード（Ｎ５、Ｎ６、またはＮ７）のノード識別子との間の差異は、ブロードキャストするノードＮ４のノード識別子と全てのパケットを受信する任意の他のノード（Ｎ５、Ｎ６、またはＮ７）のノード識別子との間の差異よりも大きい。図１０の実施例では、１つのノードＮ６のみが、全てのネットワークパケットを受信した。ブロードキャストするノードＮ４は、次いで、トークンを渡すメッセージを選択されたノード、すなわち、図１０の例ではノードＮ６にブロードキャストする。
【０１１６】
しかしながら、いずれの受信するノードＮ５、Ｎ６、およびＮ７も、パケットのグループの全てのパケットを受信しない場合、ブロードキャストするノードＮ４は、「補償」パケットのセットを決定し、その補償パケットをブロードキャストする。補償パケットのセットは、少なくとも、ネットワークパケットのうちの少なくとも１つの受信を肯定応答する、ノードＮ５、Ｎ６、およびＮ７のうちの少なくとも１つによって受信されていないパケットを含む。補償パケットは、最も少ないネットワークパケットをどのノードが受信することに失敗したか、最も遠い肯定応答ノードがどのパケットを受信することに失敗したか、パケットの半分よりも少ないものを受信することに失敗した最も遠い肯定応答ノードによってどのパケットが受信されなかったか、またはある他の選択基準に基づいて選択され得る。補償セットは、最大数のネットワークパケットを受信した２つの肯定応答ノードまたはブランチに沿って宛先ノードの方向に最も遠い２つの肯定応答ノード等、肯定応答ノードのうちの少なくとも２つによって受信されなかったネットワークパケットの集合を含み得る。ブロードキャストするノードＮ４は、それが補償パケットを送信する回数を限定し得る。
【０１１７】
ネットワークパケット７０２−７０６（図７）がこの例において使用されたが、ネットワークパケット７０２−７０６のいくつかのサブセットが、１つのタイムスロット中にグループとして送信され得る。１つのタイムスロット中にブロードキャストするノードによって送信されるパケットのグループは、より大きいメッセージ７００の一部または全てである必要はない。１つのタイムスロット中に送信されるグループ内のネットワークパケットは、より大きいメッセージ７００の一部ではないネットワークパケット等、互いに無関係であり得る。加えて、図６に関して議論されるように、他のネットワークパケット番号付けスキームが、使用され得る。したがって、ネットワークパケット６０２−６０６のいくつかもしくは全ておよび／または図６に示されない他のネットワークパケットが、１つのタイムスロット中に送信されるパケットのグループを形成し得る。
【０１１８】
いくつかの実施形態では、３２個のネットワークパケットが、１つのタイムスロット中に送信される。いくつかの実施形態では、２〜３２個のネットワークパケットが、１つのタイムスロット中に送信される。タイムスロットあたり他の数のネットワークパケットが、送信され得る。複数のネットワークパケットをブロードキャストすることに先立って、いかなるネゴシエーションも、ブロードキャストネットワークノードと潜在的受信ネットワークノードとの間に実行されないことに留意されたい。代わりに、ブロードキャストネットワークノードは、単に、複数のネットワークパケットをブロードキャストし、次いで、ブロードキャストネットワークノードは、１つ以上の受信するノードによって欠落したネットワークパケットを「充填」する。
【０１１９】
代替として、いくつかの実施形態では、ブロードキャストは、欠落したネットワークパケットを充填しない。代わりに、ブロードキャストするノードは、単に、受信するノードによって受信されたネットワークパケットに対して、受信するノードのうちの１つにトークンを渡す。次いで、ブロードキャストするノードは、欠落したネットワークパケットを新しいトランザクションとしてブロードキャストする。
【０１２０】
従来の通信プロトコルによると、ユニキャストおよびマルチキャストメッセージは、典型的には、肯定応答を要求するが、ブロードキャストメッセージは、肯定応答を要求しないことに留意されたい。対照的に、本発明の実施形態は、ブロードキャストメッセージの肯定応答を要求し、これは、従来技術によって教示または示唆されていない。
【０１２１】
（受信された／欠落したパケットに基づくノードクロック位相の調節）
各ネットワークノードは、ネットワークノードに割り当てられるタイムスロット（図８および９）の開始および終了、いつノードの無線受信機をオンおよびオフにすべきか、ならびにいつ省電力スリープ状態に入り、いつ省電力スリープ状態からノードをウェイクさせるべきかを決定することを促進するクロックを含む。別個のクロックまたは他の回路が、これらの機能のために使用され得るが、説明を簡易化するために、全てのこれらのクロックおよび回路は、集合的に、本明細書では、各ネットワークノード内の単一クロックと称される。種々のネットワークノードクロックは、互いに、少なくとも無線範囲内の他のネットワークノードと、いくつかの場合、任意の基地局内のクロックと合理的に同期させられるべきである。しかしながら、部分的に、各ネットワークノードの限定されたエネルギー供給源に起因して、ネットワークノードクロックは、互いに対して、かつ基地局内のクロックに対して、ドリフトする可能性が高い。
【０１２２】
同期させられたクロックを要求する従来技術の通信プロトコルは、クロックを同期させるための方法を含む。しかしながら、これらの従来技術の方法は、クロック同期の専用のネットワークトラフィックを要求し、したがって、センサコマンドまたはセンサデータを通信するために使用されない電力および帯域幅を消費する。
【０１２３】
本発明の実施形態は、ネットワークノード内のクロックを調節し、専用クロック同期通信に依拠することなく、クロックを他のネットワークノード内のクロックおよび／または基地局内のクロックと同期させる。図２および６−１０に関して議論されるように、複数のネットワークパケットが、単一のタイムスロット中にブロードキャストされ得る。ネットワークパケットのいずれかを受信するネットワークノードは、いくつのネットワークパケットがブロードキャストされたかについての情報とともに、ノードがその無線受信機をオンにしたときに対する、ネットワークパケットの受信のタイミングについての情報を使用し、そのクロックをブロードキャストするノードのクロックと同期させ得る。
【０１２４】
図１１は、上記の例のネットワークパケット７０２−７０６がネットワークノードＮ４によってブロードキャストされるタイムスロット１１００を図式的に描写する。ブロードキャストするノード（Ｎ４）のクロックに従って、タイムスロット１１００は、時間１１０２において開始する。最大数のネットワークパケットがブロードキャストされ、すなわち、タイムスロット１１００が満杯であると仮定し、ノードＮ４クロックに従って、タイムスロットは、時間１１０４において終了する。
【０１２５】
電力を節約するために、各ネットワークノードは、それが他のノードがブロードキャストすることを予期する期間の開始時、またはその直前にその無線受信機をオンにし、ノードは、予期されるブロードキャスト期間の終了時、またはその直後にその無線受信機をオフにすることを思い出されたい。受信するノードが全てのネットワークパケット７０２−７０６を受信する場合、受信するノードのクロックは、ブロードキャストするノードのクロックと合理的に同期させられている。しかしながら、受信するノードがその無線受信機をオンにするのが遅すぎて、ネットワークパケット７０２、７０３等のうちの最初の１つ以上のものを受信できない場合、受信するノードのクロックは、ブロードキャストするノードのクロックよりも遅れており、したがって、それと同期させられていない（すなわち、受信機のクロックは、「遅い」）。同様に、受信するノードが、ネットワークパケット７０２−７０６のグループの全てのネットワークパケットが受信される前にその無線受信機をオフにする場合、受信するノードのクロックは、ブロードキャストするノードのクロックよりも進んでおり、したがって、それと同期させられていない（すなわち、受信機のクロックは、「早い」）。
【０１２６】
図６および７に関して議論されるように、各ネットワークパケットは、受信ネットワークノードが、いくつのネットワークパケットが一連のネットワークパケット内にあるかおよび一連のネットワークパケットの開始に対する現在のネットワークパケットの位置を計算することを可能にするために、十分な情報を含む。ネットワークノードが開始時に受信していない、一連のネットワークパケットのうちのネットワークパケットの数に基づいて、ネットワークノードは、受信ネットワークノードのクロックがどれくらいの時間だけ遅いかを推定し、ネットワークノードは、その時間量だけそのクロックを調節する。例えば、仮想受信するノードＡクロックが、ノードＡにその無線受信機を時間１１０６においてオンにさせ、時間１１０８においてオフにさせる場合、ノードＡの受信期間１１１０は、ブロードキャストするノードのタイムスロット１１００に十分に一致せず、その結果、ノードＡは、ネットワークパケット７０２および７０４を受信しない。ノードＡは、欠落したネットワークパケットの数、すなわち、２つを計算し、その遅いクロックを少なくとも２つのネットワークパケットを受信するために十分な時間量だけ進め、それによって、そのクロックをブロードキャストするノードのクロックとより良好に同期させる。
【０１２７】
同様に、ネットワークノードが終了時に受信していない、一連のネットワークパケットのうちのネットワークパケットの数に基づいて、ネットワークノードは、受信ネットワークノードのクロックがどれくらいの時間だけ早いかを推定し、ネットワークノードは、その時間量だけそのクロックを調節する。例えば、仮想受信するノードＢクロックが、ノードＢにその無線受信機を時間１１１２においてオンにさせ、時間１１１４においてオフにさせる場合、ノードＢの受信期間１１１６は、ブロードキャストするノードのタイムスロット１１００に十分に一致せず、ノードＢは、ネットワークパケット７０６を受信しない。ノードＢは、欠落したネットワークパケットの数、すなわち、１つを計算し、その早いクロックを少なくとも１つのネットワークパケットを受信するために十分な時間量だけ遅らせ、それによって、そのクロックをブロードキャストするノードのクロックとより良好に同期させる。
【０１２８】
随意に、または代替として、受信するノードＢは、最初のネットワークパケット７０２が受信される前にその受信機がオンであった時間量１１１８を測定または推定し、およその時間量１１１８だけそのクロックを遅らせ得る。同様に、随意に、または代替として、受信するノードＡは、最後のネットワークパケット７０６が受信された後にその受信機がオンであった時間量１１２０を測定または推定し、およその時間量１１２０だけそのクロックを進め得る。
【０１２９】
各ネットワークノードは、ネットワークノードがブロードキャストを受信することが予期される、他のネットワークノード（すなわち、その予期される、または可能な近隣対応物）の各々に対するタイムスロットタイミング情報を同期させることを含め、維持する。述べたように、いくつかの文脈では、各ネットワークノードは、各方向における同一のブランチ上に約３つの近隣対応物ノードを有することが予期される。したがって、これらの文脈では、各ネットワークノードは、約６つの他のネットワークノードからブロードキャストを受信することが予期される。その結果、各ネットワークノードは、６つの他のノードについてのタイムスロットタイミング情報を維持することが可能であるべきである。２つ以上のブランチの要素であるネットワークノードは、ブランチあたり６つの他のノードについてのタイムスロットタイミング情報を維持すべきである。
【０１３０】
（近傍のノードの自動識別およびクロック同期）
随意に、または代替として、線形ネットワークのノードは、この目的のためにメッセージを交換することによって、それらのそれぞれのクロックを同期させ得る。４位相クロック同期プロトコルが、図１７、１８、および１９に関して説明される。図１８は、２つのシート（図１８Ａおよび１８Ｂ）に分割される。述べたように、各ノードは、比較的に少数の近隣対応物、典型的には、約６つを有し、各ノードは、その近隣対応物からの伝送の受信を見込んで、周期的にウェイクする。同期させられたクロックは、これらの通信を促進する。基地局から離れる等、ブランチに沿って一方の方向に流動するネットワークトラフィックは、他方の方向に流動するネットワークトラフィックとは別個にハンドリングされる。その結果、ノードは、他方の側のその近隣対応物との同期とは別個に、ノードの一方の側のその近隣対応物との同期を維持し得る。さらに、同期させられたクロックは、その近隣対応物と同期して、ノードが省電力スリープ状態に入り、それからウェイクすることを促進し、調子を合わせてその近隣対応物からブロードキャストを受信し、調子を合わせてそのセンサを用いてデータを収集等する。
【０１３１】
説明を目的として、ノードＮ５（図２７）は、一方の側でノードＮ６、Ｎ７、およびＮ８の無線通信範囲内にあるが、ノードＮ５は、まだノードＮ６−Ｎ８を発見していないか、またはノードＮ５は、これらのノードＮ６−Ｎ８と直接無線で通信するその能力を確認する必要があると仮定する。一方の側のその近隣対応物を発見または確認することにおいて、ノードＮ５は、４位相クロック同期プロトコルに従って、その側のその近隣対応物が、それらのそれぞれのクロックをノードＮ５のクロックと同期させることを可能にするパケットを伝送する。ノードＮ５は、当然ながら、代表的ものである。線形ネットワークの各ノードは、周期的または随時、このプロトコルに従い、その上流または下流近隣対応物のクロックをそのノードのクロックに同期させ得る。
【０１３２】
図１８は、時間が右側に進行する概略タイミング図であり、４位相クロック同期プロトコルに従う、ノードＮ５−Ｎ８間の通信の仮想セットを示す。ノードＮ５−Ｎ８は、１２５ミリ秒（ｍ秒）ウェイクアップサイクルで動作すると仮定するが、他のウェイクアップサイクル時間が、使用され得る。第１の位相１８００中、ノードＮ５は、時間的に間隔を置かれた同期パケットのセットを伝送する。各同期パケットは、対応するタイムスロット１−８中に伝送される。８つの伝送が、矢印１８０２、１８０４、１８０６、および１８０８によって表される垂直矢印によって示される。
【０１３３】
各同期メッセージ１８０２−１８０８は、伝送ノードＮ５のどの側が同期させられているかのインジケータを含む。例えば、インジケータは、ノードＮ５のノード識別子と、より大きいノード識別子を有するノード、すなわち、上流ノードが同期させられている指示とを含み得る。ノード識別子は、ノード識別子がブランチに沿って単調に変動するようにノードに割り当てられることを思い出されたい。
【０１３４】
図１８の例では、８つのタイムスロット１−８が、１２５ミリ秒サイクル毎に示されるが、しかしながら、他の数のタイムスロットが、使用され得る。各タイムスロット１−８は、単一の潜在的なそれぞれの受信するノードに割り当てられる。図１８の実施例は、伝送を受信するノードＮ６−Ｎ８よりも多いタイムスロット１−８を示す。したがって、タイムスロット１−８は、これらのノードがノードＮ５の無線通信範囲内にある場合、ノードＮ９およびＮ１０（図１７）等の追加のノードに適応し得る。述べたように、夜間等の他の時間中、より多くのノードが、ノードＮ５の無線通信範囲内にあり得る。したがって、タイムスロット１−８の数は、同期パケット伝送１８０２−１８０８を受信するノードＮ６−Ｎ８の数に等しい必要はない。
【０１３５】
同期メッセージ１８０２−１８０８は、タイムスロット１−８を識別し、どのノードがどのタイムスロットに割り当てられているかを示す情報を含む。例えば、タイムスロットは、これらのノードが無線通信範囲内にある場合に備えて、ノードＮ９およびＮ１０に割り当てられ得る。タイムスロットの順序は、潜在的受信するノードに割り当てられたノード識別子の順序に相関する必要はない。
【０１３６】
ノードＮ６、Ｎ７、およびＮ８内のそれぞれの無線受信機がオンである時間が、棒線１８１０、１８１２、および１８１４によって示される。「オン」時間１８１０−１８１４は、同期パケットが伝送される時間１８０２−１８０８と十分に整列されておらず、ノードＮ６−Ｎ８内のクロックがノードＮ５内のクロックと良好に同期させられていないことを示し得ることに留意されたい。
【０１３７】
ノードＮ６−Ｎ８の各々は、伝送ノードＮ５から直接、すなわち、同期パケットが任意の他のノードによって転送されることなく、８つの同期パケット伝送１８０２−１８０８のうちの少なくとも１つを受信すると仮定する。この例では、ノードＮ５の同一側のノードＮ９等の他のノードは、同期パケット伝送１８０２−１８０８のいずれも受信しない。伝送ノードＮ５の他の側のノードＮ４等の１つ以上の他のノードは、同期パケット伝送１８０２−１８０８のうちの１つ以上のものを受信し得るが、それらは、ノードＮ５の他の側のノードに意図されるので、これらの伝送を無視する。用語「同期パケット伝送を受信するノード」は、これらの他のノードを含まない。
【０１３８】
同期パケット伝送１８０２−１８０８を受信する各ノードＮ６−Ｎ８は、タイムスロットのどれがそのノードに割り当てられているかを識別する。８つのタイムスロットが８つの潜在的受信するノードに割り当てられ、割当についての情報が同期パケット内に含まれることを思い出されたい。ノードＮ６は、タイムスロット１を割り当てられ、ノードＮ７は、タイムスロット２を割り当てられ、ノードＮ８は、タイムスロット５を割り当てられると仮定する。
【０１３９】
同期パケット伝送の受信に応答して、第２の位相１８１６中、各ノードＮ６−Ｎ８は、その割り当てられたタイムスロット中、矢印１８１８、１８２０、および１８２２によって示されるように、肯定応答パケットを無線で伝送する。各肯定応答メッセージは、それぞれの伝送ノードのノード識別子を含む。したがって、ノードＮ６、Ｎ７、およびＮ８は、複数の伝送される肯定応答メッセージ１８１８−１８２２を集合的に伝送する。
【０１４０】
同期ノードＮ５は、肯定応答メッセージ１８１８−１８２２のうちの少なくとも１つを受信すると仮定する。同期ノードＮ５は、その肯定応答メッセージが受信されたノードＮ６−Ｎ８のセットに優先順位を付ける。優先順位付けは、少なくとも部分的に、その肯定応答メッセージが同期ノードＮ５によって受信されたノードのネットワークノード識別子に基づく。優先順位は、同期ノードＮ５からの距離に基づいて割り当てられ、より高い優先順位が、より遠隔のノードに割り当てられる。同期ノードＮ５からの距離の尺度は、同期ノードＮ５のノード識別子と肯定応答ノードＮ６−Ｎ８のノード識別子との間の差異を計算することによって決定され得ることに留意されたい。このスキームは、メッセージを最も遠隔のノードに転送することに有利であり、したがって、ネットワークホップを可能な限り大きくする。
【０１４１】
ノード識別子は単調に割り当てられるので、同期ノードＮ５は、肯定応答メッセージ１８１８−１８２２を送信するノードＮ６−Ｎ８間で、最大のノード識別子を伴うノードＮ８が、ブランチに沿って最も遠い、すなわち、同期ノードＮ５から最も遠いと仮定することができる。同期ノードＮ５は、したがって、最も高い優先順位をノードＮ８に割り当て、次に高い優先順位を次に最も遠隔のノードＮ７に割り当て、以下同様である。同期ノードＮ５が、他の側のノード内のクロックに同期していた場合、またはノード識別子が、ノードＮ５からノードＮ８への方向に減少する場合、優先順位割当は、最大ノード識別子ではなく、最小ノード識別子に基づくであろう。
【０１４２】
第３の位相１８２４中、同期ノードＮ５は、矢印１８２６、１８２８、および１８３０によって示されるように、優先順位付けパケットを優先順位付けられたノードＮ６−Ｎ８のうちの少なくとも１つに伝送する。優先順位付けパケットは、意図される受信するノードＮ６−Ｎ８に割り当てられたそれぞれのタイムスロット（１、２、および５）中に伝送される。ノードＮ６、Ｎ７、およびＮ８内のそれぞれの無線受信機がオンである時間が、棒線１８３２、１８３４、および１８３６によって示される。
【０１４３】
第１の位相１８００または第３の位相１８２４のいずれかの間に同期ノードＮ５から伝送を受信した結果、各受信するノードＮ６−Ｎ８は、ノードの受信機「オン」時間１８１０−１８１４または１８３２−１８３６中、いつ同期ノードＮ５からの伝送が受信されるかに基づいてそのクロックを調節する。例えば、図１１に関して議論されるやり方で、同期ノードＮ５からの伝送が、受信機「オン」時間１８１０−１８１４または１８３２−１８３６の開始時付近で受信される場合、受信するノードＮ６−Ｎ８は、そのクロックを遅い（遅れている）と見なし、その受信機をより早くオンにするようにそのクロックを調節し得る。その結果、同期ノードＮ５からの将来の伝送は、受信するノードの「オン」時間１８１０−１８１４または１８３２−１８３６の中心により近接して受信されるはずである。
【０１４４】
随意に、第４の位相１８３８中、同期ノードＮ５は、同期メッセージを確認するための要求１８４０を伝送する。同期メッセージを確認するための要求１８４０を受信するノードＮ６−Ｎ８は、矢印１８４２、１８４４、および１８４６によって示されるように、それぞれの肯定応答パケットを伝送することによって、受信を肯定応答する。ノードＮ６−Ｎ８は、優先順位順にそれらのそれぞれの肯定応答を伝送する。同期ノードＮ５は、肯定応答パケットを受信し、それらのそれぞれの優先順位を含む同期させられたノードＮ６−Ｎ８のリストを維持する。
【０１４５】
図１９に図式的に示される状態図は、ノードＮ５−Ｎ８の同期状態および状態間の遷移を例証する。述べたように、各ノードは、各近隣対応物に対する別個のクロック情報を維持する。したがって、各ノードは、それが伝送を受信することを予期する各近隣対応物のために別個の同期状態を維持する。以下は、それぞれのそのような同期状態が１つの近隣対応物に対して維持される方法を説明する。
【０１４６】
始動時、各ノードは、「同期させられていない」状態１９００に入る。ノードＮ６−Ｎ８のうちの１つ等のノードが、上で議論されるようなノードＮ５等のその近隣対応物と同期させられると、ノードＮ５は、それが同期させられたノード（Ｎ６−Ｎ８）に対して、「同期させられた」状態１９０２に入る。ノードＮ５は、事前決定された時間量にわたって、またはノードにそのクロックを再同期させるべきイベントが起こるまで、同期させられた状態１９０２のままであり得る。同期ノード（ノードＮ５等）は、周期的または随時、比較的に小さい同期パケットを送信し得、したがって、その近隣対応物は、それらのそれぞれのクロックを同期ノードのクロックと同期して維持することができる。しかしながら、ノードが事前決定された時間量にわたって同期パケットを受信しない場合、ノードは、「再同期」状態１９０４に入る。ノードがその近隣における変化を検出する場合、すなわち、より多いまたは少ないノードが近隣対応物である場合、ノードは、同期させられていない状態１９００に入り、新しい同期および優先順位を確立する。
【０１４７】
周期的または時折、ノードは、「ディープスリープ」状態１９０６に入り、その状態において、それは、比較的に長い期間にわたって省電力モードに入る。ディープスリープ中、ノードの送信機および受信機は、オフのままであり、電力を節約する。ディープスリープの持続時間は、ノードのバッテリの充電レベルならびに／またはネットワーク内および／もしくはこのノードのブランチ内のノードの数等の考慮事項に基づいて、事前決定され得る。これらの考慮事項は、ネットワークが、所望の数のコマンドおよび／またはデータを１日等の規定された時間量以内に各ブランチの一方の端部と各ブランチの他方の端部との間に伝達することを可能にする等の設計目的を満たすことに関連し得る。
【０１４８】
（スケジューリングされた実装を用いた無線プロビジョニング）
センサネットワークのネットワークノードの寿命にわたって、随時、ネットワークノードにおいて、ネットワークノード識別子、省電力スリープ間隔、タイムスロット配分、センサデータを収集する開始／中止時間等のパラメータおよび／またはソフトウェアを更新することが、望ましいか、または必要であり得る。多くの場合、ネットワークノード間のネットワークノード識別子の一貫性を維持する等のために、全てのネットワークノードに対するそのような変更を同時に、または事前決定された時間ウィンドウ以内に実装することが、望ましいか、または必要である。しかしながら、特に、長いブランチを伴うネットワーク上では、ブランチの一方の端部からブランチの他方の端部にネットワークパケットを転送するために要求される時間は、長すぎて、全ての影響を受けるノードに対する変更を同時に、または所望の時間ウィンドウ以内に有効化できない場合がある。
【０１４９】
本発明の実施形態は、影響を受けるネットワークノードにメッセージを配信することによって、または単に、ネットワークもしくはブランチ全体をメッセージで氾濫させることによって、この問題を解決する。各メッセージは、新しいソフトウェア、更新されるネットワークノード識別子、またはノードの識別子を再計算する方法の指示等の更新情報と、変更がノードによって実装されるべき未来時の指示とを含む。各メッセージは、各影響を受けるノードによって実行されるべきスクリプトを含み得る。これらのメッセージは、基地局または任意の他の好適な更新コマンドの送信元によって送信され得る。メッセージ送信側は、メッセージの一部がドロップされる場合に備えて、影響を受けるノードのそれぞれにメッセージの冗長コピーを送信し得る。
【０１５０】
各影響を受けるノードは、影響を受けるノードに宛先指定されるメッセージのうちの少なくとも１つを受信し、メッセージ内に含まれる更新情報を記憶する。各影響を受けるノードは、必要に応じて、省電力スリープ状態からアウェイクされることを含め、未来時またはその前に通知されるように、内部タイマを設定するか、または別の好適な機構を使用する。ネットワークノードが、未来時が今であることを通知されると、ネットワークノードは、記憶された更新情報を使用して、変更を行う、すなわち、それ自体を更新する。
【０１５１】
いくつかの場合、あるネットワークノードのみが、更新されるべきである。例えば、あるハードウェアコンポーネントもしくはあるバージョンのハードウェアコンポーネントを含む、またはあるバージョンのソフトウェアもしくはより前のバージョンのソフトウェアを実行するネットワークノードのみが、更新されるべきである。これらの場合、各メッセージは、更新のタイプの指示を含み得、各ノードは、更新のタイプをチェックし、更新がノードに適用されるかどうかを決定する。ノードが更新のタイプに一致する場合、ノードは、上で説明されるような更新を実装する。随意に、または代替として、各ノードは、ノードが更新のタイプに一致する場合のみ、更新情報を記憶する。
【０１５２】
（他のネットワークトラフィック上でピギーバックする健全性および安危情報）
多くの状況では、センサステータス、バッテリ充電レベル、エネルギー回収装置生産量、無線信号対雑音比、無線範囲内の他のノードの数、近傍のノードへの有効帯域幅等、ネットワークノードからネットワークノード健全性および安危情報を取得することが、望ましいか、または必要である。しかしながら、述べたように、電力およびネットワーク帯域幅を節約することが、望ましいか、または必要である。
【０１５３】
別個の健全性および安危ネットワークパケット（以降では、単純に、ネットワークステータス情報と称される）を送信することを回避するために、いくつかの実施形態は、この種類の情報をコマンドおよび／またはデータを搬送するネットワークパケット内に含む。図１２は、そのような実施形態による、仮想例示的シナリオを図式的に描写する。ノードＮ８は、ネットワークステータス情報１２００が送信されるべき方向に転送されているネットワークパケット１２０２をノードが受信し、そのネットワークパケット１２０２がネットワークステータス情報１２００の一部または全てを含むために十分な自由空間を有するまで、ネットワークステータス情報１２００を収集し、記憶する。ノードＮ８は、ネットワークパケット内に、ネットワークステータス情報１２０４またはその一部を記憶し、それによって、修正されたネットワークパケット１２０６を生産する。ノードＮ８は、次いで、修正されたネットワークパケット１２０６をブロードキャストし、修正されたネットワークパケット１２０６をそのルート上で転送する。
【０１５４】
修正されたネットワークパケット１２０６が、基地局１２０８等のその宛先に着信すると、ネットワークステータス情報１２０４が同一の宛先に宛先指定される場合、ネットワークステータス情報１２０４は、送達される。そうでなければ、ネットワークステータス情報１２０４は、ネットワークステータス情報１２０４を転送するために好適な別のネットワークパケットが、さらにそのルートに沿って受信されるまで、受信するノードによって記憶され得る。
【０１５５】
いくつかの実施形態では、転送ネットワークパケットは、センサコマンドおよび／またはセンサデータを搬送し、ネットワークステータス情報を搬送するために特に生成されるネットワークパケットではない。そのようなネットワークパケットは、したがって、本明細書に説明されるように、ノードが記憶されたネットワークステータス情報をパケットに追加するまで、任意のネットワークステータス情報を欠いている。
【０１５６】
ネットワークパケットは、ネットワークステータス情報のための限定された空間を必然的に有し、時として、いかなる空間も有していない。いくつかの場合、ブランチ上の２つ以上のネットワークノードは、送信すべきネットワークステータス情報を並行して有するが、ネットワークパケット内の利用可能な空間は、ノードの全て、またはいくつかの場合、ノードのうちの２つ以上のものを収容するために不十分であり得る。いくつかの実施形態は、事前決定された、恣意的でさえある比較スキームに従って、ネットワークステータス情報の重要性等に基づいて、ネットワークステータス情報の転送に優先順位を付ける。
【０１５７】
例えば、１つのノードのネットワークステータス情報は、ノードのセンサによって今まで取得されたサンプルの数等のルーチンの履歴情報を含み得る一方、別のノードのネットワークステータス情報は、ノードのバッテリ充電が極めて低いことを示し得る。履歴情報は、バッテリステータス情報よりも重要ではないと見なされ得る。
【０１５８】
いくつかの実施形態では、ネットワークステータス情報を搬送するネットワークパケットが、ネットワークノードを通過するとき、ネットワークノードが、ネットワークパケットが転送されている方法と同一の方向に送信されるべきネットワークステータス情報を記憶しており、かつ通過ノードによって記憶されているネットワークステータス情報が、事前決定された比較スキームに従って、現在ネットワークパケット内にあるネットワークステータス情報よりも重要である場合、通過ノードは、ネットワークパケット内にそのネットワークステータス情報を記憶し、必要に応じて、現在ネットワークパケット内にあるネットワークステータス情報に取って代わる。
【０１５９】
（ネットワークブランチ）
図１に関して述べたように、線形ネットワークは、１つ以上のブランチを含む。複数のブランチ間で共通であるネットワークノードは、各ブランチのために１つの複数のネットワークノード識別子を有する。図１３は、図１の線形ネットワーク１０２のための例示的仮想ネットワークノード識別子スキームを例証する。述べたように、線形ネットワーク１０２は、３つのブランチ１１６、１１８、および１２０を含む。
【０１６０】
全てがブランチ１１６の要素である、ノード１、２、３、４等は、そのブランチの指示を含むネットワーク識別子を割り当てられる。例えば、ノード１は、ネットワーク識別子Ｂ１−１を割り当てられ、ノード２は、ネットワーク識別子Ｂ１−２を割り当てられ、以下同様であり、Ｂ１は、ブランチ１１６を示す。このスキームによると、ノード１、２、３、４等は、ブランチ１１６に沿って、ベースノード１３０から離れ、ブランチ１１６の一方の端部からブランチ１１６の他方の端部への方向に単調に増加するネットワークノード識別子を割り当てられる。
【０１６１】
全てがブランチ１１８の要素である、ノード１、１０、１１、１２等は、そのブランチの指示を含むネットワーク識別子を割り当てられる。例えば、ノード１は、ネットワーク識別子Ｂ２−１を割り当てられ、ノード１０は、ネットワーク識別子Ｂ２−２を割り当てられ、ノード１１は、ネットワーク識別子Ｂ２−３を割り当てられ、以下同様であり、Ｂ２は、ブランチ１１８を示す。このスキームによると、ノード１、１０、１１、１２等は、ブランチ１１８に沿って、ベースノード１３０から離れ、ブランチ１１８の一方の端部からブランチ１１８の他方の端部への方向に単調に増加するネットワークノード識別子を割り当てられる。
【０１６２】
全てがブランチ１２０の要素である、ノード１、１０、１１、２０、２１、２２等は、そのブランチの指示を含むネットワーク識別子を割り当てられる。例えば、ノード１は、ネットワーク識別子Ｂ３−１を割り当てられ、ノード１０は、ネットワーク識別子Ｂ３−２を割り当てられ、ノード１１は、ネットワーク識別子Ｂ３−３を割り当てられ、ノード２０は、ネットワーク識別子Ｂ３−４を割り当てられ、ノード２１は、ネットワーク識別子Ｂ３−５を割り当てられ、以下同様であり、Ｂ３は、ブランチ１２０を示す。このスキームによると、ノード１、１０、１１、２０、２１、２２等は、ブランチ１２０に沿って、ベースノード１３０から離れ、ブランチ１２０の一方の端部からブランチ１２０の他方の端部への方向に単調に増加するネットワークノード識別子を割り当てられる。
【０１６３】
ノード１、１０、および１１は、複数のネットワーク識別子を有することに留意されたい。述べたように、各ネットワークノードは、メモリ内等に、それらのそれぞれのネットワークノード識別子の表現を記憶する。図４および５を参照して議論されるように、これらのノードがネットワークパケットを受信し、ネットワークパケットルーティングを実施するとき、ノードは、それを経由してネットワークパケットが受信されるブランチに関連付けられたそれらのそれぞれのネットワークノード識別子の記憶された表現を使用する。それを経由して所与のネットワークパケットが受信されるブランチは、ネットワークパケットをブロードキャストするノードのネットワークノード識別子も一部（Ｂ１、Ｂ２、またはＢ３部分等）によって識別されることができる。２つ以上のブランチの要素である各ネットワークノードは、それぞれのそのようなブランチについての情報を維持し得る。情報は、無線通信範囲内であるブランチ上の近傍のノードのネットワーク識別子を含み得る。
【０１６４】
（電力消費を低減させながらネットワークサイズを増加させるネットワークセグメント化）
議論されるように、低デューティサイクル無線通信プロトコルが、ネットワークノードを殆どの時間、省電力スリープ状態に保つことによって、電力を大幅に節約するために使用される。しかしながら、ネットワークノードが、それらが収集するデータを２４時間等の事前決定された時間量以内に基地局に伝達することを要求されるか、または基地局からのコマンドが、事前決定された時間量以内にその宛先ネットワークノードに送達される必要がある場合、各ネットワークブランチの長さ（ノードの数において）は、事前決定された時間量以内に起こることが可能なホップの数によって限定される。ＣｏｎｔｉｋｉＭＡＣ無線デューティサイクルプロトコル等の従来の低デューティサイクル無線通信プロトコルは、ネットワークブランチ内の比較的に少数のノードしかサポートすることができない。なぜなら、ノードがアウェイクし、他のノードからおよびそれにネットワークパケットを受信および送信することが可能な合計時間量が、２４時間等の所与の期間中に起こることが可能なホップの数を限定するからである。
【０１６５】
本発明の実施形態は、所与の線形ネットワークを２つ以上のネットワークセグメントに分割し、各ネットワークセグメントを異なるタイムスロットに関連付けることによって、従来の低デューティサイクル無線通信プロトコルを改良する。その結果、通信は、１つのネットワークセグメントの通信が別のネットワークセグメント上の通信に干渉することなく、複数のネットワークセグメント内で並行して起こり得る。これは、特に、いくつかのネットワークセグメントのノードが互いの無線範囲内にあり得る、基地局に近接するエリアにおいて重要である。
【０１６６】
図１４は、基地局１４０２と、「ｐ」ネットワークセグメント（４つが示される）１４０４、１４０６、１４０８、および１４１０とを有する仮想無線センサネットワーク１４００の概略ブロック図である。本明細書で使用される場合、ネットワークセグメントは、基地局または別のネットワークセグメントのネットワークノードを通過することなく、直接または同一のネットワークセグメントの他のネットワークノードのみを介して、互いにネットワークパケットを送受信し得る全てのネットワークノードを含む。基地局は、各ネットワークセグメントの一部と見なされ得る。しかしながら、ネットワークパケットをルーティングするために、基地局が、最初のネットワークノードからネットワークパケットを受信し、次いで、別のネットワークノードにネットワークパケットを送信しなければならない場合、他のネットワークノードは、最初のネットワークノードと同一のネットワークセグメント上にない。
【０１６７】
各ネットワークセグメントは、少なくとも１つのネットワークブランチを含む。例えば、ネットワークセグメント１４０４は、ネットワークブランチ１４１２、１４１４、および１４１６を含む。他の３つの示されるネットワークブランチ１４０６−１４１０の各々は、それぞれ、１つのネットワークブランチ１４１８、１４２０、および１４２２のみを含む。
【０１６８】
本発明の実施形態によると、各ネットワークセグメント１４０４−１４１０は、ネットワークセグメントのネットワークノードがブロードキャストし得る異なるタイムスロットを割り当てられる。各ネットワークセグメントの基地局端部に近接する、ネットワークノード１００、１０５、１１０、２００、２０５、３００、３０５、３１０、ｐ００、およびｐ０５等のネットワークノードは、互いの無線範囲内にあり得るが、そのブロードキャストは、１つのネットワークセグメントのネットワークノードがブロードキャストするとき、基地局１４０２に近接する他のネットワークセグメント内のネットワークノードの無線受信機がオフであるので、各他のネットワークセグメント内のネットワークノードによるブロードキャストに干渉しない。
【０１６９】
各ネットワークセグメントのタイムスロットは、「時間間隔」と称されるより長い期間の開始をマーキングする。ネットワークセグメント１４０４（図１４）に関する例示的仮想時間間隔１５０２およびタイムスロット１５００が、図１５に図式的に例証される。各タイムスロット１５００は、３つの期間１５０４、１５０６、および１５０８に分割される。時間間隔１５０２の残りは、長スリープ期間１５１０と称される。第１の期間１５０４は、複数の第１のサブスロット（サブタイムスロット）１５１２に細分化され、第３の期間１５０８は、複数の第２のサブスロット（サブタイムスロット）１５１４に細分化される。図１５に示されるように、各サブスロット１５１２および１５１４は、その隣接するサブスロットから時間的に間隔を置かれ得るか、または代替として、図１５の下部に示されるように、サブスロットは、連続的であり得る。
【０１７０】
第１のサブスロット１５１２の各々中、ネットワークセグメント１４０４のネットワークノードは、ネットワークパケットを基地局１４０２から離れる方向に転送することを目的としてブロードキャストし得、第２のサブスロット１５１４の各々中、ネットワークセグメント１４０４のネットワークノードは、ネットワークパケットを基地局１４０２に向かう方向に転送することを目的としてブロードキャストし得る。
【０１７１】
第２の期間１５０６中、ネットワークセグメント１４０４のネットワークノードは、それらのそれぞれのセンサを動作させ、データを感知し、感知されたデータを記憶し得る。ネットワークノードは、第２の期間１５０６中、連続的に動作し得るか、またはそれらは、周期的または時折、省電力スリープ状態に入り得る。ネットワークセグメント１４０４のネットワークノードのうちのそれぞれのものが、所与の期間中にデータを収集するように割り当てられない場合、ノードは、第２の期間１５０６中に省電力スリープ状態に入り得る。長スリープ期間１５１０中、ネットワークセグメント１４０４のノードは、省電力スリープ状態に入る。
【０１７２】
図１５は、縮尺通りに描かれないことに留意されたい。長スリープ期間１５１０は、タイムスロット１５００よりもはるかに長い。その結果、ネットワークセグメント１４０４のノードは、時間の９９％にわたって省電力スリープ状態にある。本発明の実施形態によると、ネットワークセグメント１４０４のノードは、従来技術の低電力無線デューティサイクルプロトコルを上回る割合の時間において省電力スリープ状態にある。その結果、ネットワークセグメント１４０４のノードは、従来技術の低電力無線デューティサイクルプロトコルにおいてよりも、第１および第２の期間１５０４および１５０８中に頻繁にウェイクしているために利用可能な電力を有する。より頻繁にウェイクしていることが可能であることは、ネットワークセグメント１４０４のノードが、従来技術の低電力無線デューティサイクルプロトコルを使用して可能なものよりも、２４時間等の一連の所与の期間にわたって多くのホップをハンドリングすることを可能にする。その結果、本発明のこれらの実施形態は、従来技術の低電力無線デューティサイクルプロトコルよりも長い（ネットワークノードの数の観点から）ブランチをサポートすることができる。
【０１７３】
図１６は、それぞれのネットワークセグメント１４０４−１４１０（図１４）に関する時間間隔の仮想タイミングを例証する、概略図である。図１６において分かり得るように、時間間隔１５０２、１６００、１６０２、・・・、１６０４の開始時間は、１つのネットワークセグメントのネットワークノードによるブロードキャストが、任意の他のネットワークセグメントのネットワークノードによるブロードキャストに干渉することを防止するように、互い違いにされる。例えば、互い違いの持続時間１６０６は、タイムスロット１  １５００等のタイムスロットと少なくとも同程度に長い。時間間隔１５０２−１６０４は、繰り返される。
【０１７４】
ある実施形態では、タイムスロット、時間間隔、およびサブスロットは、少なくとも１，０００，０００個のネットワークノードの線形ネットワークが、全て２４期間以内に、各ブランチ上で少なくとも１つのコマンドネットワークパケットを基地局から最後のネットワークノードに転送し、各ブランチ上で少なくとも１つのセンサデータパケットを最後のネットワークノードから基地局に転送することを可能にするように選択される。そのようなネットワークは、比較的に多数のブランチ（いくつかの場合、約１，０００個のブランチ）を要求する可能性が高い。
【０１７５】
本明細書に説明されるような方法および装置は、帯域幅を増加させるために、複数の無線周波数（チャンネル）において同時に動作し得る。
【０１７６】
ＩＥＥＥ  ８０２．１５．４は、低速無線パーソナルエリアネットワーク（ＬＲ−ＷＰＡＮ）のための物理層および媒体アクセス制御（ＭＡＣ）を規定する規格である。ＩＥＥＥ  ８０２．１５．４は、ＺｉｇＢｅｅ（登録商標）、ＩＳＡ１００．１１ａ、ＷｉｒｅｌｅｓｓＨＡＲＴ、およびＭｉＷｉ仕様に関する基準であり、それらの各々はさらに、ＩＥＥＥ  ８０２．１５．４において定義されない、上位層を開発することによってこの規格を拡張させる。代替として、  ＩＥＥＥ  ８０２．１５．４は、６ＬｏＷＰＡＮプロトコルおよび標準インターネットプロトコルと共に使用され、無線組み込みインターネットを構築することができる。６ＬｏＷＰＡＮは、ＩＥＥＥ  ８０２．１５．４規格に基づいて、無線センサネットワークを経由するＩＰｖ６パケットの伝送を可能にする。６ＬｏＷＰＡＮは、ＩＰｖ６パケットが、ＩＥＥＥ  ８０２．１５．４ベースのネットワークに送信され、それから受信されることを可能にするカプセル化およびヘッダ圧縮機構を定義する。ＩＰｖ４およびＩＰｖ６は、通常、ローカルエリアネットワーク、メトロポリタンエリアネットワーク、およびインターネット等の広域ネットワークを経由するデータ送達のために使用される。同様に、ＩＥＥＥ  ８０２．１５．４デバイスは、無線ドメインにおいて感知通信能力を提供することができる。本発明の実施形態は、６ＬｏＷＰＡＮおよび他のプロトコルの側面を拡張および／または修正する。
【０１７７】
本発明は、上で説明される例示的実施形態を通して説明されるが、本明細書に開示された発明的概念から逸脱することなく、例証される実施形態の修正および変更が、成され得る。さらに、開示される側面またはその一部は、上記に列挙されていない、および／または明示的に請求されていない方法で組み合わせられ得る。故に、本発明は、開示された実施形態に限定されると見なされるべきではない。
【０１７８】
実施形態の側面は、フローチャートおよび／またはブロック図を参照して説明され得るが、各ブロックの全てもしくは一部、またはブロックの組み合わせの機能、動作、決定等は、組み合わせられるか、別個の動作に分離されるか、または他の順序で実施され得る。各ブロックの全てもしくは一部、またはブロックの組み合わせは、コンピュータプログラム命令（ソフトウェア等）、ハードウェア（組み合わせ論理、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、または他のハードウェア等）、ファームウェア、またはそれらの組み合わせとして実装され得る。
【０１７９】
図２０は、本発明の実施形態による、ネットワークノード２０００の概略ブロック図である。ノード２０００は、本明細書に議論されるように、無線送受信機２００４と、クロック２００４と、少なくとも１つのセンサ２００６と、メモリ２００８とを含む。メモリ２００８は、ノード２０００のネットワークノード識別子２０１０、ノード更新情報２０１２、ネットワークステータス情報２０１４、および近隣対応物同期情報２０１６等の情報を記憶するために使用され得る。ネットワークノード２０００はまた、図１８に関して議論されるように、同期メッセージを生成する同期メッセージジェネレータ２０１８を含む。データコレクタ／送信装置２０２０が、センサ２００６をハンドリングし、必要に応じてセンサ２００６から収集されたデータを記憶し、収集されたデータの全てまたは一部を基地局等に向かって送信する。
【０１８０】
受信パケットハンドラ２０２４が、必要に応じて大きいパケットをフラグメント化することを含め、本明細書に議論されるように、ネットワークパケットを転送する等のタスクをハンドリングする。転送するノードセレクタ２０２４が、図２−５等に関して説明されるように、パケットを転送するノードを選択する。補償パケット識別装置／送信装置２０２６が、図１０等に関して説明されるように、他のノードに送信されるべき補償パケットを識別し、補償パケットを送信する。
【０１８１】
クロックシンクロナイザ２０２８が、図１１および１８−１９等に関して説明されるように、クロック２００４を調節し、必要に応じて他のノードとの同期を維持する。クロックシンクロナイザ２０２８はまた、近隣対応物ノードについての同期ステータス情報も維持し得る。タイムスロットマネージャ２０３０およびサブタイムスロットマネージャ２０３２が、図１５、１６、および１８に関して議論されるように、いつノード２０００が伝送および受信するかを制御する。肯定応答メッセージジェネレータ２０３４が、最後の連続的パケットを受信した後に送信されるもの、どのノードがブロードキャストを受信したかを示すためのもの、クロックを同期させるためのもの等の肯定応答メッセージを生成する。
【０１８２】
ノードプライオリタイザ２０３６が、図１８等に関して議論されるように、ノードに優先順位を付ける。ノードアップデータ２０３８が、メモリ２００８内に更新情報２０１２を記憶し、クロック２００４によってトリガされると、更新情報２０１２を適用すること等によって、ノード更新をハンドリングする。ネットワークステータス情報マネージャ２０４０が、ブランチに沿ったネットワークステータス情報の転送をハンドリングする。
【０１８３】
実施形態は、メモリ内に記憶された命令を実行する、またはそれによって制御されるプロセッサによって実装され得る。メモリは、制御ソフトウェアまたは他の命令およびデータを記憶するために好適であるランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、フラッシュメモリ、または任意の他のメモリ、またはそれらの組み合わせであり得る。
【０１８４】
本発明の機能を定義する命令は、限定ではないが、有形の書込不可能な記憶媒体（例えば、ＲＯＭ等のコンピュータ内の読み取り専用メモリデバイス、またはＣＤ−ＲＯＭもしくはＤＶＤディスク等のコンピュータＩ／Ｏアタッチメントによって読み取り可能であるデバイス）上に恒久的に記憶された情報、有形の書込可能な記憶媒体（例えば、フロッピディスク、取り外し可能フラッシュメモリ、およびハードドライブ）上に変更可能に記憶された情報、または有線もしくは無線コンピュータネットワークを含む通信媒体を通してコンピュータに伝達される情報を含む、多くの形態においてプロセッサに送達され得る。さらに、実施形態は、種々の例証的データ構造と関連して説明され得るが、システムは、種々のデータ構造を使用して具現化され得る。
【図１】
2019220998.tif 000003
【図２】
2019220998.tif 000004
【図３】
2019220998.tif 000005
【図４】
2019220998.tif 000006
【図５】
2019220998.tif 000007
【図６】
2019220998.tif 000008
【図７】
2019220998.tif 000009
【図８】
2019220998.tif 000010
【図９】
2019220998.tif 000011
【図１０】
2019220998.tif 000012
【図１１】
2019220998.tif 000013
【図１２】
2019220998.tif 000014
【図１３】
2019220998.tif 000015
【図１４】
2019220998.tif 000016
【図１５】
2019220998.tif 000017
【図１６】
2019220998.tif 000018
【図１７】
2019220998.tif 000019
【図１８Ａ】
2019220998.tif 000020
【図１８Ｂ】
2019220998.tif 000021
【図１９】
2019220998.tif 000022
【図２０】
2019220998.tif 000023