(57)【要約】  センサー／アクチュエータ・ノードを無線でネットワーク接続する方法が記載される。センサー／アクチュエータ・ノードは、センサー／アクチュエータ・ノード・ネットワークに設置され、複数のノード・レベル及びクラスター・ヘッド・ネットワークを備える階層的な方法で配置される。一意のノード識別子がセンサー・ノードに割当てられ、センサー・ノード・ネットワークが初期化される。センサー・ノードは、タスクを実行するために起動された後、アクティブな低電力モードに設定される。
2005515696.tif 000002
【特許請求の範囲】
【請求項１】
センサー・ノードを無線でネットワーク接続する方法であって、
複数のノード・レベル及びクラスター・ヘッド・ネットワークを備える階層的な方法で配置されたセンサー・ノード・ネットワークに、センサー・ノードを設置するステップと、
前記センサー・ノードに一意の識別子を割当てるステップと、
前記センサー・ノード・ネットワークを初期化するステップと、
前記センサー・ノードをタスクを実行するよう起動するステップと、
初期化及び前記タスクの実行のいずれかの後に、前記センサー・ノードをアクティブな低電力モードに設定するステップと、
を備える方法。
【請求項２】
請求項１記載の方法であって、更に、前記センサー・ノードに暗号鍵を配布するステップを備える方法。
【請求項３】
複数のノード・レベル及びクラスター・ヘッド・ネットワークを備える階層的な方法で配置されたセンサー・ノード・ネットワークを初期化する方法であって、
仮トポロジを確立し、前記センサー・ノード・ネットワークを同期させるステップと、
前記センサー・ノード・ネットワークの少なくとも１つのリンクを検出し評価するステップと、
前記センサー・ノード・ネットワークのセンサー・ノードを、前記クラスター・ヘッド・ネットワークのクラスター・ヘッドに登録するステップと、
を備える方法。
【請求項４】
請求項３記載の方法であって、仮トポロジを確立し同期させる前記ステップが、更に、
下位レベルのノードから上位レベルのノードへ起動信号をブロードキャストするステップと、
前記下位レベルのノードから前記上位レベルのノードへ初期化パケットを送信するステップと、
前記上位レベルのノードを同期させるステップと、
前記上位レベルのノードから前記下位レベルのノードへ仮登録パケットを送信するステップと、
前記起動信号をブロードキャストする前記ステップ、前記初期化パケットを送信し同期させる前記ステップ、及び前記仮登録パケットを送信する前記ステップを、全てのノード及び所定レベルより上の全てのノードのいずれかに到達するまで繰り返すステップと、
を備える方法。
【請求項５】
請求項４記載の方法であって、前記下位レベルのノードがクラスター・ヘッドであり、前記上位レベルのノードが第１レベルのセンサー・ノードである方法。
【請求項６】
請求項４記載の方法であって、前記下位レベルのノードが第１レベル・ノードであり、前記の上位レベルのノードが第２レベル・ノードである方法。
【請求項７】
請求項４記載の方法であって、前記上位レベルのノードが上限レベルのノードである方法。
【請求項８】
請求項３記載の方法であって、検出し評価する前記ステップが、更に、複数のリンク評価パケットをブロードキャストするステップを備える方法。
【請求項９】
請求項８記載の方法であって、前記リンク評価パケットが完全に無作為な方法でブロードキャストされる方法。
【請求項１０】
請求項８記載の方法であって、前記リンク評価パケットが、タイム・スロットに分割された、無作為化された又は決定性の方法でブロードキャストされる方法。
【請求項１１】
請求項１０記載の方法であって、ブロードキャスト期間が、前記センサー・ノード・ネットワークの各レベルのためのタイム・スロットに分割される方法。
【請求項１２】
請求項１１記載の方法であって、前記ブロードキャストが、前記タイム・スロットのわずかな一部分でのみ発生する方法。
【請求項１３】
請求項１１記載の方法であって、前記ブロードキャストが前記タイム・スロットにおいて無作為に発生する方法。
【請求項１４】
請求項１１記載の方法であって、前記ブロードキャストが、前記センサー・ノードに関連付けられた一意の識別子に基づいて発生する方法。
【請求項１５】
請求項１１記載の方法であって、前記ブロードキャストが、任意の２つのノードが最大でも１つのタイム・スロット内でのみ干渉することを保証するコードに基づいて発生する方法。
【請求項１６】
請求項３記載の方法であって、登録の前記ステップが、更に、複数の登録パケットを送るステップを備える方法。
【請求項１７】
請求項１６記載の方法であって、前記登録パケットが、無作為化された個別ノードの手法により送られる方法。
【請求項１８】
請求項１６記載の方法であって、前記登録パケットが、タイム・スロットが割当てられたレベルごとの手法により送られる方法。
【請求項１９】
請求項１８記載の方法であって、ブロードキャスト期間が、前記センサー・ノード・ネットワークの各レベルに対するタイム・スロットに分割される方法。
【請求項２０】
請求項１９記載の方法であって、前記各レベルに対するブロードキャストの順番が、上位レベルから下位レベルまでを含む方法。
【請求項２１】
請求項１６記載の方法であって、上位レベル・ノードからの登録データが、下位レベル・ノードにより送信される登録パケットに積重ねられる方法。
【請求項２２】
請求項３記載の方法であって、更に、ネットワーク・トポロジを計算するステップを含む方法。
【請求項２３】
請求項２２記載の方法であって、前記ネットワーク・トポロジが、電力消費を低減するよう計算される方法。
【請求項２４】
請求項２２記載の方法であって、全てのノードの電池寿命が実質的に等しくなるよう、前記ネットワーク・トポロジが計算される方法。
【請求項２５】
請求項３記載の方法であって、更に、ネットワーク・トポロジを配布するステップを備える方法。
【請求項２６】
請求項２５記載の方法であって、前記ネットワーク・トポロジを配布するステップが、更に、トポロジに対し複数のトポロジ確立パケットを送信するステップを備える方法。
【請求項２７】
請求項２６記載の方法であって、前記トポロジ確立パケットが無作為な方法で送信される方法。
【請求項２８】
請求項２６記載の方法であって、前記トポロジ確立パケットが、タイム・スロットを割当てられたレベルごとの方法で送信される方法。
【請求項２９】
請求項２８記載の方法であって、送信期間が、前記センサー・ノード・ネットワークの各レベルに対するタイム・スロットに分割される方法。
【請求項３０】
センサー・ノード・ネットワークのセンサー・ノードに対する送信リンクのＲＦチャネルをモニタリングする方法であって、
ＲＳＳＩ読み出しを実行するステップと、
プリアンブルにおいて特有のＲＦ起動シーケンスを検索するステップと、
有効な開始シーケンスを検索するステップと、
入力パケットのパケット・ヘッダを読み取るステップと、
前記入力パケットの内容に従ってタスクを実行するステップと、
前記センサー・ノードをアクティブな低電力モードに設定するステップと、
を備え、
前記特有のＲＦ起動シーケンスが、当該センサー・ノードにより実行されるべきタスクに従って複数のＲＦチャネルに分離され、前記タスクがそれぞれに要求される待ち時間に応じて異なる周波数でモニタリングされるよう、前記タスクに相対的な優先度が割当てられる方法。
【請求項３１】
請求項３０記載の方法であって、有効な開始シーケンスを検索する前記ステップが、更に、
前記の割当てられた相対的な優先度に応じて前記有効な監視シーケンスを走査するステップ
を備える方法。
【請求項３２】
複数のノード・レベル及びクラスター・ヘッド・ネットワークを備える階層的な方法で配置されたセンサー・ノード・ネットワークを動作させる方法であって、
センサー・ノードを起動するステップと、
メッセージを送信するステップと、
前記センサー・ノードをアクティブな低電力モードに設定するステップと、
を備える方法。
【請求項３３】
請求項３２記載の方法であって、前記センサー・ノードが毎秒１〜４回起動される方法。
【請求項３４】
請求項３２記載の方法であって、前記メッセージを送信するステップが、更に、複数の優先度の高い制御パケットを送信するステップを備える方法。
【請求項３５】
請求項３４記載の方法であって、前記優先度の高い制御パケットが、幾つかの前記ノード・レベルにおけるノードに対しマルチキャストで送信される方法。
【請求項３６】
請求項３４記載の方法であって、前記優先度の高い制御パケットが、単一のノードにユニキャストで送信される方法。
【請求項３７】
請求項３４記載の方法であって、更に、監視肯定応答パケットに優先度の低いメッセージを積重ねるステップを備える方法。
【請求項３８】
請求項３２記載の方法であって、前記メッセージを送信するステップが、更に、複数の警告パケットを送信するステップを備える方法。
【請求項３９】
請求項３８記載の方法であって、前記警告パケットがディレクテド・フラッディング手法で送信される方法。
【請求項４０】
請求項３９記載の方法であって、更に、
前記警告パケットの送信の前に起動シーケンスをブロードキャストするステップと、
前記起動シーケンス及び警告パケットを、中間センサー・ノードを介して前記クラスター・ヘッド・ネットワークに送るステップと、
を備える方法。
【請求項４１】
請求項３２記載の方法であって、前記メッセージを送信するステップが、更に、警告パケットを、別途定義されたトポロジを介してユニキャストで送信するステップを備える方法。
【請求項４２】
請求項３２記載の方法であって、前記メッセージを送信するステップが、更に、レベルに基づくタイム・スロットの手法、親と複数の子とのレベルに基づくタイム・スロットの手法、及び、親と子とのレベルに基づくタイム・スロットの手法のうちの一つにより複数の監視パケットを送信するステップを備える方法。
【請求項４３】
請求項４２記載の方法であって、前記監視パケットが１時間に一度送信される方法。
【請求項４４】
請求項３２記載の方法であって、前記メッセージを送信するステップが、更に、複数のリンク評価パケットを送信するステップを備える方法。
【請求項４５】
請求項４４記載の方法であって、前記リンク評価パケットが、警告パケット及び制御パケットのうちの少なくとも一つから分離されたＲＦチャネルで送信される方法。
【請求項４６】
請求項４４記載の方法であって、前記リンク評価パケットが１日に一度送信される方法。
【請求項４７】
請求項３２記載の方法であって、前記メッセージを送信するステップが、更に、リセットに応じてＳＯＳパケットを送信するステップを備える方法。
【請求項４８】
請求項３２記載の方法であって、前記メッセージを送信するステップが、更に、新ノード・パケットを送信するステップを備える方法。
【請求項４９】
請求項３２記載の方法であって、前記メッセージを送信するステップが、更に、登録パケットを送信するステップを備える方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連発明への相互参照
本出願は、２００２年１月１０日に出願された米国仮特許出願第６０／３４７、５６９号に基づく優先権を主張し、２００２年１１月２１日に出願された「管理及び制御のための階層型無線自己組織ネットワーク」と題された出願に関連する。両出願は、参照により本明細書に援用される。
【０００２】
発明の分野
本発明は、監視及び制御のためのセンサー及びアクチュエータを無線でネットワーク接続するためのプロトコルを記述する。
【０００３】
背景情報
ネットワークは、監視及び制御に適用され得る。しかし、そのようなネットワークを実現するための実質的なコストの金額には、例えばネットワークの設計、ネットワーク要素の設置、及びネットワーク要素の配置の構成／再構成が含まれ得る。更に、そのようなネットワークには、資源の消費及び／又はネットワーク・トポロジの制約の点で制限を課し得る電池式の装置が含まれ得る。
【０００４】
発明の概要
本発明は、例えば煙探知機、運動探知機、温度センサー、ドア接触、警報音発生器、又はバルブ・アクチュエータを含む監視及び制御のためのセンサー及びアクチュエータを無線でネットワーク接続するためのプロトコルを記述する。該プロトコルは、様々な複雑さを有するノード・タイプであって、２つの独立したネットワーク（いわゆるクラスター・ヘッド・ネットワーク及びセンサー／アクチュエータ・ノード・ネットワーク）を形成する少なくとも２つの異なるノード・タイプを含むことにより故障単点を回避する階層型システム構造上に形成される。２００２年１１月２１日に出願され「管理及び制御のための階層型無線自己組織ネットワーク」と題された米国特許出願において論じられた全システムは、分散された方法で少数の基幹ノード（いわゆるクラスター・ヘッド）により制御され、各クラスター・ヘッドにおいて全ネットワークに関する情報がアクセスされる。より小さなシステムでは、単一の基幹ノード（例えば、単一のクラスター・ヘッド）を利用してもよい。
【０００５】
本発明は、また、センサー／アクチュエータ・ノード・ネットワークを形成、維持及び利用するプロトコルを記述する。これらのセンサー／アクチュエータ・ノードは、相互の及びクラスター・ヘッドとのアドホックなマルチホップ・ネットワークを形成する。センサー／アクチュエータ・ノードの大半が電池式であり得るため、エネルギー効率が問題となり得る。そのため、メッセージのオーバーヘッドは、必要最小限に維持される。この点について、プロトコルは、信頼性及びスケーラビリティ、並びに時折の緊急メッセージの迅速な送出を維持しつつ、同時に低い電力消費を達成することができる。プロトコルは、また、変化する伝送条件、及び／又はリンク障害或いはノード障害に適応するために、ネットワークが継続的に自己改良し、利用可能な全てのＲＦリンクの品質に関する情報を更新することを可能にする。設置に際し、センサー／アクチュエータ・ノード・ネットワークは、クラスター・ヘッドで共有され処理されるリンク品質及び接続性に関するグローバル情報に基づいて自らを構成する。セットアップ中のユーザによる操作、又は詳細な設計は必要とされない。リンク障害又はノード障害が起きた場合、プロトコルは、システムの稼動期間を通して大半の装置間の接続性を保証するため、自動的な再構成を可能とする。
【０００６】
詳細な説明
以下の説明において、「センサー・ノード」という用語は、センサー・ノード及びアクチュエータ・ノードの両方を集合的に表すために利用される。同様に、「センサー・ノード・ネットワーク」という用語は、センサー及び／又はアクチュエータからなるネットワークを集合的に表すために利用される。センサー・ノード・ネットワーク内の通信は、無作為なバック・オフを備える搬送波感知多重アクセス（ＣＳＭＡ）に基づき得る。送信されたパケットは、物理層により定義されるプリアンブルと、開始シンボル及び制御バイトと、パケット・タイプと、パケット長と、送信元及び／又は宛て先のノード識別子と、巡回冗長検査符号（ＣＲＣ）とを含み得る。オプションとして、送信は、共有鍵の交換を伴うリンク層の暗号化によりセキュリティを確保され、メッセージ認証コード（ＭＡＣ）により認証され得る。
【０００７】
図１Ａは、センサー及び／又はアクチュエータを無線でネットワーク接続するための例としてのプロトコル方法を表すフローチャートである。ステップ１０１において、ネットワーク・ノードが設置され、一意のノード識別子（ＩＤ）が収集され、暗号鍵が配布される。２つのセンサー・ノード間の、又はセンサー・ノードと直近のクラスター・ヘッドとの間の最大通信距離により、センサー・ノードの物理的な配置が制限される。ノードが配置されると、ノードが作動させられ、及び／又は、一意のノード識別子及び地理上の位置が有線或いは無線のインターフェース及び／又はマニュアル入力配置を介して記録される。そのような起動又は記録は、例えばバー・コード・スキャナを備える設置ツールにより実行される。代わりに、各ノードには、ユーザに装置の物理的位置を示すものとして役立ち得る短いイントラ・ネットワークＩＤがプログラムされてもよい。これは、例えばマニュアル入力（例えば、ディップ・スイッチの配列）により、又はセンサー・ノードにＩＤを電気的に格納することにより実現される。パネルＰＣは、更に、例えば、センサー・ノード・データを設置ツールからクラスター・ヘッドの一つへ送ることができる。設置されると、ノードは以下に更に詳細に説明される「アクティブな低電力モード」に留まる。
【０００８】
ステップ１０２において、クラスター・ヘッド・ネットワークが初期化される。クラスター・ヘッドの設置並びに初期化は、２００２年１１月２１日に出願され「管理及び制御のための階層型無線自己組織ネットワーク」と題された米国特許出願に記載されている。クラスター・ヘッド・ネットワークの代わりに、単一の基地局が利用されてもよい。しかし、本明細書において「クラスター・ヘッド・ネットワーク」という用語は、単一の基地局又はクラスター・ヘッド・ネットワークのいずれかを集合的に表すものとして用いられる。
【０００９】
ステップ１０３において、仮トポロジを確立し、ノードを同期させ、それらを適切なクラスター・ヘッドに登録することにより、センサー・ノード・ネットワークが初期化される。初期化に続いて、センサー・ノードは例えば電池電力などの資源を保存するために、アクティブな低電力モードへ「後退」する。
【００１０】
ステップ１０４において、センサー・ノードは、例えば毎秒に１〜４回、ＲＦ起動メッセージを受信するために「起動」される。入ってくるメッセージ又は経過した時間に応じて、センサー・ノードは、１つ又はそれ以上の手順を実行する。例えば、パケットが未送信である場合又は警告状態が生成される場合には、ステップ１０５において、入ってくるデータ又は生成された警告を処理するために、パケット処理又は警告メッセージ手順が実行される。代わりに、例えば監視間隔（例えば、１時間に１回）が経過すると、ステップ１０６において、例えばその子ノード及び／又は親ノードの状態を確認するために監視手順が実行される。それにより、ステップ１０７において、再構成／状態更新手順が実行される。更に、例えば、リンク・メンテナンス期間（例えば、１日に１回）が経過すると、ステップ１０８において、リンク・メンテナンス手順が実行される。該手順が完了すると、センサー・ノードはアクティブな低電力モードに戻り、他のＲＦ起動メッセージを待機する。各手順は、ネットワーク要素間の相互作用とともに、以下においてより詳細に説明される。
【００１１】
センサー・ノード・ネットワークの初期化には、例えば、仮トポロジ確立・同期段階、リンク検出・評価段階、及びセンサー・ノード登録段階といった３段階が含まれる。仮トポロジ確立・同期段階並びに初期の試運転において、センサー・ノード・ネットワークのトポロジが決定され、センサー・ノードのクロックが同期される。リンク検出・評価段階において、ネットワーク要素間の接続性が調査及び再検討される。センサー・ノード登録段階において、ネットワーク要素は、リンク検出・評価段階の期間に集められた情報をクラスター・ヘッド・ネットワークへ送る。
【００１２】
図１Ｂは、仮トポロジ確立段階のための例としてのメッセージ交換図を示す。時間を表す図の横軸ｔは、タイム・スロット１．１．１〜１．ｎ．３に分割される。ネットワーク要素の階層的な順序を表す図の縦軸は、一番下のクラスター・ヘッドと、第１レベルから上に向かって第ｎレベルへと増加するよう示されるセンサー・ノードとに分割される。時間軸ｔの上方の各水平線は、ネットワーク要素の特定のインスタンス（instance）、即ちクラスター・ヘッドの特定のインスタンス、第１レベル・ノードの特定のインスタンス、第２レベル・ノードの特定のインスタンス、又は第ｎレベル・ノードの特定のインスタンスのいずれかを表す。より正確には、線ｃ−１、ｃ−２及びｃ−ｍはクラスター・ヘッドの第一、第二及び上限の各インスタンスを表し、線１−１、１−２及び１−ｌは第１レベル・ノードの第１、第２及び上限の各インスタンスを表し、線２−１、２−２及び２−ｋは第２レベル・ノードの第１、第２及び上限の各インスタンスを示し、線ｎ−１、ｎ−２及びｎ−ｉは最高レベルのノードの第一、第二及び上限の各インスタンスを表す。水平線を取り囲む陰影は、関連するネットワーク要素で優勢な動作又はモードを示す。暗い陰影は「送受信」モードを示し、明るい陰影は「アクティブな低電力モード」を示し、透明な又はくすみのない陰影は「受信専用」モードを示す。
【００１３】
矢印は、ネットワーク要素間のＲＦメッセージ伝送を表す。特に、「広い」白抜きの矢印は、特定のレベル内の全ノードに対するブロードキャスト・メッセージを表し、「細い」実線は、ネットワーク要素の１つのインスタンスのみに送信されるユニキャスト・メッセージを表す。
【００１４】
タイム・スロット１．１．１において、クラスター・ヘッドは、「ＲＦ起動信号」を同時にブロードキャストする。ブロードキャストの送信距離内にある受信するノード（即ち、「第１レベル・ノード」）は、アクティブな低電力モードから受信専用モードに変化する。次に、タイム・スロット１．１．２において、クラスター・ヘッドｃ−１〜ｃ−ｍは、それぞれ、所定の数の「初期化パケット」をブロードキャストする。初期化パケットは、例えば、送信するクラスター・ヘッドの識別子、カウンタ及びタイム・スタンプを含み得る。次に、タイム・スロット１．１．３において、受信する第１レベル・ノードは、クロックを同期させ、例えばパケット成功率及び／又は最強のＲＦ出力レベルに基づいて決定された最良のリンク品質を用いて「仮登録パケット」をクラスター・ヘッドに送信し、肯定応答（ａｃｋ）を待機する。肯定応答されると、第１レベル・ノードは、タイム・スロット１．２．１まで、受信専用モードに留まり、又はアクティブな低電力モードに戻る。
【００１５】
肯定応答が受信されない場合、第１レベル・ノードは、仮登録パケットの１回又はそれ以上の再送を試みる。所定回数の送信を試みても肯定応答が受信されない場合、第１レベル・ノードは、次に良いリンク品質を有すると決定されたクラスター・ヘッドへのコンタクトを試みる。所定の最大数の連続したクラスター・ヘッドへの再送の試みが繰り返された後にも肯定応答が受信されない場合、第１レベル・ノードはアクティブな低電力モードに戻る。
【００１６】
タイム・スロット１．２．１において、ブロードキャストするクラスター・ヘッドからの肯定応答を受信した第１レベル・ノード１−１及び１−２は、「ＲＦ起動信号」をブロードキャストする。当該ブロードキャストの送信距離内にある受信するノード（即ち、「第２レベル・ノード」）は、アクティブな低電力モードから受信専用モードへと変化する。その後、タイム・スロット１．２．２において、第１レベル・ノード１−１及び１−２は、所定数の「初期化パケット」をそれぞれブロードキャストする。初期化パケットは、例えば、送信するノードの識別子、カウンタ及びタイム・スタンプを含み得る。タイム・スロット１．２．３において、受信する第２レベル・ノードは、クロックを同期させ、例えばパケット成功率又は最強のＲＦ出力レベルに基づいて決定された最良のリンク品質を用いて「仮登録パケット」を第１レベル・ノードに送信し、肯定応答を待機する。肯定応答されると、第２レベル・ノードは、タイム・スロット１．２．１まで受信専用モードに留まり、又はアクティブな低電力モードに戻る。
【００１７】
肯定応答が受信されない場合、第２レベル・ノードは、仮登録パケットの１回又はそれ以上の再送を試みる。所定回数の送信を試みても肯定応答が受信されない場合、第２レベル・ノードは、次に良いリンク品質を有すると決定された第１レベル・ノードへのコンタクトを試みる。所定の最大数の連続する第１レベル・ノードへの再送の試みが繰り返された後にも肯定応答が受信されない場合、第１レベル・ノードはアクティブな低電力モードに戻る。
【００１８】
タイム・スロット１．ｎ．１において、全てのノードが作動され又は所定の上限レベルのノードが作動されるまで、下位レベルのノードが一つ上のレベルのノードを起動し、１つ上のレベルのノードが同期をとって下位レベルのノードに仮登録することを可能とするプロセスが繰り返される。所定の上限レベルは、例えばユーザにより定義され得る。
【００１９】
図２は、リンク検出・評価段階のための例としてのメッセージ交換図を示す。図１Ｂと同様に、横軸ｔは時間を表し、縦軸はネットワーク要素の階層的な順序を表す。同様に、時間軸ｔの上方の水平線はネットワーク要素の特定のインスタンスを表し、水平線を取り囲む陰影は優勢な動作又はモードを示し、矢印はＲＦメッセージ送信を表す。しかし、図１Ｂと違い、図２の時間軸は、最初の完全に無作為化されたセグメントと、それに続く、タイム・スロットに分割された、無作為化された又は決定性のセグメントとを含み、リンク検出・評価のための二つの二者択一的な手法を表す全体的なタイム・スロット２を表す。
【００２０】
リンクを検出し評価するため、ノード及び／又はクラスター・ヘッドは、送信距離内の全ノードに「リンク評価パケット」をブロードキャストする。それにより、これらの受信するノードは、例えば電力レベル、及び／又は到達可能なネットワーク要素へのパケット成功率に基づいてリンク統計を作成する。リンク評価パケットは、例えば、送信するノードの識別子及びカウンタを含み得る。
【００２１】
リンク評価パケットのブロードキャストの回数は、正確なリンク統計が作成（収集及び構築）されるのに十分な程度に大きくなければならない。生成された多数のパケットのパケット・スケジューリングは、例えば、完全に無作為化された手法、及びタイム・スロットに分割された、無作為化された又は決定性の手法を含む少なくとも２つの手法に従って処理される。完全に無作為化された手法において、ノードは、所与の間隔ｔに渡り所定数のリンク評価パケットを無作為にブロードキャストし、送信していないときには可能な限り多くのパケットを受信するよう試みる。代わりに、タイム・スロットに分割された、無作為化された又は決定性の手法において、所与の期間はタイム・スロット２．１〜２．ｘに分割され、各タイム・スロットにおいて一連のリンク評価パケットが送信される。タイム・スロットに分割された、無作為化された又は決定性の手法において、各ノードは利用可能なタイム・スロットのわずかな一部分（例えば、１０％以下）のみに送信を行うため、送信確率は受信確率より低い。特定のタイム・スロット内に送信するか否かは、３つのオプションとしての方法により決定され得る。第１の場合、各タイム・スロットの始めに無作為な決定がなされる。第２の場合、どのタイム・スロットに送信が起こるべきか、及びどのタイム・スロットに受信が起こるべきかを決定するための擬似無作為アルゴリズムが利用される。アルゴリズムの「シード（ｓｅｅｄ）」又は基準は、例えば一意のノード識別子、又は一意のノード識別子の一部のような、各ノードにとって一意のものであってよい。シード及びアルゴリズムをクラスター・ヘッドが知っている場合、クラスター・ヘッドは各ノードのための送信タイム・スロットを再計算する。そのため、クラスター・ヘッドは、リンク評価期間に避けられ得るよう隣接のノードとの干渉が起こりやすいタイム・スロットを決定し、それにより、ネットワークのリンク評価の信頼性を向上させる。第３の場合、特定のタイム・スロット内に送信するか否かの決定は、例えば、任意の２つのノードが最大でも１つのタイム・スロットにおいてのみ干渉することを保証し得る直交光学コード（Orthogonal  Optical  Code）（ＯＯＣ）のようなコードに基づき得る。
【００２２】
図３は、センサー・ノード登録段階のための例としてのメッセージ交換図を示す。先の図面と同様に、横軸ｔは時間を表し、図の縦軸はネットワーク要素の階層的な順序を表す。同様に、時間軸ｔの上方の水平線はネットワーク要素の特定のインスタンスを表し、水平線を取り囲む陰影は優勢な動作又はモードを示し、矢印はＲＦメッセージ伝送を表す。しかし、先の図面と違い、図３の時間軸ｔは、無作為に個々のノード登録を行うセグメント３．０と、それに続く、タイム・スロットを割当てるレイヤーごとのノード登録セグメント３．１〜３．３とを含み、センサー・ノード登録に対する２つの二者択一的な手法を表す全体的なタイム・スロット３を表す。
【００２３】
センサー・ノード登録期間に、リンク品質統計は、センサー・ノードからクラスター・ヘッドへ、中間ノードを介し「登録パケット」を用いて送られる。登録パケットは、例えば、全ての隣接のノード又は最良のリンクを有すると考えられる選択された数のノードからのリンク品質データを、各リンクに関するその他のデータとともに含み得る。クラスター・ヘッドにおいて、個々のノードの対に含まれる２つのノードからの一方向のリンク品質情報を組み合わせることにより、双方向のリンク品質情報が達成され得る。登録は、例えば、無作為化された個別ノードの手法、及びタイム・スロットを割当てるレベルごとの手法を含む少なくとも２つの手法に従って処理され得る。無作為化された個別ノードの登録手法において、パケットのルーティングは、上記に論じられた例としての仮トポロジ確立手法に従って処理され得、オプションとして、クラスター・ヘッドとセンサー・ノードとの間のエンド・ツー・エンドの肯定応答が発生する。代わりに、タイム・スロットを割当てるレイヤーごとの手法においては、例えば最高レベルのノードから始まる各レベルのノードを登録するために、特定のタイム・スロットが利用される。最高レベルのノードからの登録データは、下位レベルにより送信される登録パケットに付加され（即ち、積重ねられ）得る。必要であれば、下位レベルのノードは、登録パケットを再送する。適切な登録メッセージの交換を保証するため、センサー・ノードの登録には能動的又は受動的な肯定応答が利用される。交換の成功が確認されると、登録されたノードはアクティブな電力モードに戻る。
【００２４】
センサー・ノード登録期間に受信されたリンク品質統計に基づいて、クラスター・ヘッドは、ノードにより実行される特定の機能に応じて、センサー・ノード・ネットワークに対する１つ又はそれ以上のトポロジを計算する。例えば、監視機能を実行するノードのためには「監視ツリー」トポロジが計算され、警告／制御メッセージ処理機能を実行するノードのためには「警告ツリー」トポロジが計算される。そのような特別に定義されたトポロジは、以下において更に詳細に説明される。
【００２５】
センサー・ノードは、一般的に、クラスター・ヘッドをツリーの各ルートとする複数ツリー構造に組織される。最適なトポロジを保証するため、１つ又はそれ以上の要素を考慮してよい。例えば、メッセージ遅延を最小化し、電力消費を低減し、衝突を回避し、レベルの最大数を制限し、及び、全ノードのバッテリー寿命が実質的に等しくなるようネットワークの負荷を均衡させるためには、「良い」リンク（例えば、過剰なパケットの再送を経験したことがないリンク）を利用することが望ましい。
【００２６】
図４Ａは、センサー・ノード・ネットワークの確立されたトポロジを配布するための例としてのメッセージ交換図を示す。先の図面と同様に、横軸ｔは時間を表し、図の縦軸はネットワーク要素の階層的な順序を表す。同様に、時間軸ｔの上方の水平線はネットワーク要素の特定のインスタンスを表し、水平線を取り囲む陰影は優勢な動作又はノードを示し、矢印はＲＦメッセージ伝送を表す。しかし、先の図面と違い、図４Ａの時間軸ｔは、レベルごとのタイム・スロットを割当てられた配布のセグメントと、それに続く無作為化された配布のセグメントとを含む全体的なタイム・スロット４を表し、確立されたセンサー・ノード・ネットワーク・トポロジを配布するための２つの二者択一的な手法を表す。
【００２７】
確立されたセンサー・ネットワーク・トポロジを配布するため、クラスター・ヘッドは、各ノードへ「トポロジ確立パケット」を送信し得る。トポロジ確立パケットは、例えばノードの子の定義、ノードに現在割当てられている１つ又は複数の親（ノードはオプションとして、例えば２つの異なるネットワーク・トポロジに割当てられる）、ノードの可能性のある親、ノード・レベル、共通鍵方式の暗号鍵、周波数チャネル、監視のためのタイミング情報、及びタイム・スタンプを含み得る。新しいネットワーク・トポロジにおける各ノードの特定のレベルは、仮トポロジにおけるノードの各レベルと同一でなくてもよい。特に、例えば、物理的にはクラスター・ヘッドの受信距離内にあるノードであったとしても、全体としての最適化されたトポロジにとってはそのような配置のほうが望ましいために、第二レベル・ノードに割当てられることがあり得る。レベルごとにタイム・スロットが割当てられる配布の手法では、トポロジ確立パケットは、そのレベルのために用意されたタイム・スロットにおいて同一レベルのノードに集合的に送信される。例えば、図４Ａにおいて、第１レベルの全ノードはタイム・スロット４．１にトポロジ確立パケットを送信され、第２レベルの全ノードはタイム・スロット４．２にトポロジ確立パケットを送信され、第３レベルの全ノードはタイム・スロット４．３にトポロジ確立パケットを送信される。代わりに、無作為化された配布の手法では、トポロジ確立パケットは任意のレベルのノードに対し、タイム・スロット４全体において送信される。
【００２８】
適切な確立を保証するため、能動的又は受動的なリンク・レベルの肯定応答が利用される。加えて、オプションとして、ノードからクラスター・ヘッドへのエンド・ツー・エンドの肯定応答もサポートされ得る。
【００２９】
ノードは、ネットワークにおいて確立されると、アクティブな低電力モードへ後退し、ＲＦ起動信号による起動を待機し得る。確立されたネットワークのライフタイムを通じて、ノードのほぼ全ての要素が、例えば電池式ノードのリアルタイム・クロックなどの重要と考えられるものを除き、電池の動作を延長するために、主に低電力／スリープ・モードに留まる（平均電流は、例えばμＡ範囲内であり得る）。周期的に及び／又はスケジュールされた期間に、例えば自己試験又はＲＦチャネルのモニタリングなどのタスクを実行するよう、要素が作動（即ち、低電力／スリープ・モードから「起動」）される。特に、マイクロ・コントローラは、自己試験ルーチン（例えば、電池状態の検査）を実行し、又は関連付けられたセンサーから示数を読み取るために起動される。代わりに、待ち時間の少ない適切なメッセージ処理を保証するために、例えば１００〜１０００ミリ秒ごとの定期的な間隔でＲＦチャネルがモニタリングされる。異常が検出されると、それを検出したノードが警告メッセージを発行する。
【００３０】
図４Ｂは、ＲＦチャネルをモニタリングする例としての方法を示す。ステップ４０１において、センサー・ノードはアクティブな低電力モードに設定される。ステップ４０２〜４０４において、センサー・ノードのマイクロ・コントローラは、用意された「ＲＦ起動チャネル」において受信信号強度インジケータ（ＲＳＳＩ）測定を実行する受信要素を起動し、動作可能化する。ＲＳＳＩ測定値が予め決められた閾値より大きい場合、ステップ４０５において、特徴的なＲＦ起動シーケンス（例えば、ロジック状態の交互のシーケンスである１−０−１−０−１）についてプリアンブルが検索される。ＲＳＳＩ測定値が予め決められた閾値より大きくない場合には、ステップ４０６において、ノードはアクティブな低電力モードに戻る。特徴的なＲＦ起動シーケンスが検出された場合、ステップ４０７において、１つ又はそれ以上のチャネルを走査することにより、有効な開始シーケンスが検索される。特徴的なＲＦ起動シーケンスの伝送は、実行される機能／タスクの種別に従って複数のＲＦチャネル間で分離され、それぞれには、特定の機能／タスクがそれぞれに要求される最大待ち時間に従って異なる周波数においてモニタリングされ得るよう相対的な優先度が割当てられる。そのため、例えば、警告メッセージ専用のチャネルを走査し、次いで制御メッセージ専用のチャネルを走査してから監視メッセージ専用のチャネルを走査するなどのように、所定の優先度に従って走査することにより、有効な検索シーケンスの検索が実行される。
【００３１】
所定のタイムアウト期間に有効な開始シーケンスが検出されない場合、ノードはアクティブな低電力モードに戻る。有効な開始シーケンスが検出された場合には、ステップ４０８において、意図された受信先を決定するためにパケット・ヘッダが読み込まれる。パケットが他のノードに向けられている場合又は無効である場合には、パケットが廃棄され、ノードはアクティブな低電力モードに戻る。パケットが当該ノードに向けられている場合、ステップ４０９においてパケットが受信され、適切なタスクが実行される。
【００３２】
ネットワークにおけるメッセージ処理の適切な制御を保証するため、メッセージは、例えば優先度の高いメッセージ及び優先度の低いメッセージのような、一つ又は複数の優先度分類により区別される。優先度の高いメッセージは、例えばノード及び再プログラミング・ノード・ファームウェアの武装化／非武装化などの、クラスター・ヘッドからセンサー・ノードへの即時の注意及び／又は反応を求めるコマンドを送信するために利用される。優先度の高いメッセージを送信するため、特別な「優先度の高い制御パケット」が単一のノードにユニキャストで、又はノードのグループにマルチキャストで送信される。ユニキャストで送信される場合、優先度の高い制御パケットは、タイム・スタンプと、クラスター・ヘッドから目的ノードまでの特定の経路と、目的ノードで実行されるべきコマンドとを含み得る。マルチキャストで送信される場合、優先度の高い制御パケットは、タイム・スタンプと、目的ノードのリスト又は目的グループの識別子と、転送ノードのリストと、目的ノードで実行されるべきコマンドとを含み得る。優先度の高いパケットは、ＲＦ起動シーケンスにより先行されてもよい。加えて、リンク・レベル及び／又はエンド・ツー・エンドの肯定応答が利用され得る。
【００３３】
図５は、優先度の高い制御メッセージを伝送するための例としてのメッセージ交換図を示す。先の図面と同様に、横軸ｔは時間を表し、図の縦軸はネットワーク要素の階層的な順序を表す。同様に、時間軸ｔの上方の水平線はネットワーク要素の特定のインスタンスを表し、水平線を取り囲む陰影は優勢な動作又はモードを示し、矢印はＲＦメッセージ伝送を表す。しかし、先の図面と異なり、図５の時間軸は、マルチキャストによる伝送セグメントとそれに続くユニキャストによる伝送セグメントとを含む全体的なタイム・スロット５を表し、優先度の高い制御メッセージを伝送する２つの二者択一的な手法を表す。
【００３４】
優先度の高いメッセージと比べ、優先度の低いメッセージは、クラスター・ヘッドからセンサー・ノードへの、例えばリンク切替えコマンドや校正係数更新コマンドなどの迅速な注意又は反応を必要としないコマンドを発行するために利用される。優先度の高いメッセージと違い、優先度の低いメッセージは特別なパケット・タイプを必要としない。代わりに、メッセージ・データは、監視サイクル期間にノードからノードへと配布されるよう、１つ又はそれ以上の「監視肯定応答パケット」に付け加え（即ち、積重ね）られる。優先度の低いメッセージ・データが積重ねられた監視肯定応答パケットは、目的ノード又は目的グループの識別子と、転送ノードのリストと、目的ノードで実行されるべきコマンドとを含み得る。
【００３５】
センサー・ノードからクラスター・ヘッドへの待ち時間の少ない情報伝送を保証するため、例えばディレクテド・フラッディング（ｄｉｒｅｃｔｅｄ  ｆｌｏｏｄｉｎｇ）手法又はユニキャスト手法を用いて、適切な警告メッセージ処理が実行される。例としてのディレクテド・フラッディング手法によれば、警告を生成したノードは、自らのブロードキャストの受信距離内にあるノードを起動するために、ＲＦチャネルに起動シーケンスをブロードキャストする。ブロードキャストは、全てのノードが起動シーケンスを受信し処理するのに十分な時間を取れるよう、かなり長くなければならない。最小期間は、例えば定義されたＲＦチャネルのモニタリング期間、及びノードがどれだけ正確に同期されているかにより異なり得る。起動シーケンスがブロードキャストされると、例えば送信元ノードの識別子と、送信元ノードのレベルと、警告コードと、オプションとしてのタイム・スタンプとを含み得る一連の「警告パケット」が発行される。送信元ノードより下位のレベルのノードは、ＲＦ起動シーケンスに続く警告パケットを、他の下位レベルのノードに送る。必要であれば、ブロードキャストを切り捨てるために、間接的なリンク・レベルの肯定応答を利用してもよい。
【００３６】
ディレクテド・フラッディング手法の代わりに、別途定義された「警告トポロジ」又は別途定義された「監視トポロジ」に基づくユニキャストの方法で警告メッセージ処理が実行されてもよい。例としてのユニキャスト手法によれば、警告生成元ノードは、ディレクテド・フラッディング手法の例と同様に、自らのブロードキャストの受信距離内のノードを起動するために、ＲＦチャネルに起動シーケンスをブロードキャストする。例としてのディレクテド・フラッディング手法と同様に、起動シーケンスのブロードキャストは、全てのノードが起動シーケンスを受信し処理するのに十分な時間を取れるよう、かなり長くなければならない。最小期間は、例えば定義されたＲＦチャネルのモニタリング期間、及びノードがどれだけ正確に同期されているかにより異なり得る。しかし、例としてのディレクテド・フラッディング手法とは異なり、単一の「警告パケット」が、意図された目的ノードの親ノードにユニキャストされる。次に、親ノードは、起動シーケンスに続くメッセージを、意図された目的ノードに送る。親からの（能動的又は受動的な）肯定応答が受信されるまで、警告パケットの再送が試みられる。警告パケットの再送が所定のタイムアウト期間内に不成功である場合、警告メッセージはディレクテド・フラッディング手法により再送されてもよい。
【００３７】
図６は、警告メッセージを伝送するための例としてのメッセージ交換図を示す。先の図面と同様に、横軸ｔは時間を表し、図の縦軸はネットワーク要素の階層的な順序を表す。同様に、時間軸ｔの上方の水平線はネットワーク要素の特定のインスタンスを表し、水平線を取り囲む陰影は優勢な動作又はモードを示し、矢印はＲＦメッセージ伝送を表す。しかし、先の図面と異なり、図６の時間軸は、マルチキャスト伝送セグメントとそれに続くユニキャスト伝送セグメントとを含む全体的なタイム・スロット６を表し、警告メッセージを伝送する二つの二者択一的な手法を表す。
【００３８】
センサー・ノードの適切な機能を保証し、センサー・ノードとクラスター・ヘッドとの間の通信経路を維持するため、「監視パケット」を交換することにより監視が実行される。監視パケットは、例えばステータス情報と、付加された（即ち、「積重ねられた」）優先度の低いメッセージと、オプションとしてのタイム・スタンプとを含み得る。肯定的な結果を明示的に送る代わりに、ノードは、不適切な又は潜在的な危険性を有する状態のみを、例えば監視間隔τｓにより定義された定期的な間隔でクラスター・ヘッドに報告してもよい。これらの間隔の期間に、それぞれの親が子を調べるため、及びその逆のために、親子関係が利用される。監視パケットは能動的に肯定応答されてもよく、該パケットは、各ノードに保持されたリアルタイム・クロックを更新するためのタイム・スタンプと、オプションとして優先度の低いメッセージとを含み得る。上記の通り、監視のために、例えば警告又は制御のメッセージ用のチャネルからは分離された１つ又はそれ以上のチャネルが利用される。
【００３９】
監視は、１つ又はそれ以上の手法により実行され得る。例えば、監視は、レベルに基づくタイム・スロットの手法、親と複数の子とのレベルに基づくタイム・スロットの手法、又は親と１つの子とのレベルに基づくタイム・スロットの手法により実行され得る。
【００４０】
例としてのレベルに基づくタイム・スロットの手法によれば、監視間隔τｓは、特定レベルに属するノードにより共通に利用されるｎＬ個の等しいタイム・スロットに分割される。特定のタイム・スロットにおいて、上位レベルに属する各ノードは、親ノードに監視パケットをユニキャストし、肯定応答を待機する。肯定応答が受信されない場合、監視パケットは再送され、所定数の再送に対しても肯定応答が受信されない場合には、「可能性のある」親ノードに接続することにより特定ノードの接続性の修復を試みるローカルの再構成が実行される。オプションとして、ローカルの再構成を試みる前に、次の監視サイクルにおいて監視パケットを送信する追加の試みが実行され得る。
【００４１】
代わりに、例としての親と複数の子とのレベルに基づくタイム・スロットの手法によれば、監視間隔τｓはｎＬ個の等しいタイム・スロットに分割され、各タイム・スロットは更に、特定の親及びその全ての子に用意されたスロットに分割され得る。特定のスロット内で、スロットに関連付けられた個々の子は、その親に監視パケットをユニキャストし、肯定応答を待機する。肯定応答が受信されない場合、監視パケットは再送され、所定の回数の再送に対して肯定応答が受信されない場合には、「可能性のある」親ノードに接続することにより特定のノードの接続性の修復を試みるローカルの再構成が実行される。オプションとして、ローカルの再構成を試みる前に、次の監視サイクルにおいて監視パケットを送信する追加の試みが実行され得る。
【００４２】
代わりに、例としての親と１つの子とのレベルに基づくタイム・スロットの手法によれば、監視間隔τｓはｎＬ個の等しいタイム・スロットに分割され、各タイム・スロットは更に、特定の親子の組に用意されたスロットに分割され得る。特定のスロット内で、一致した子はその親に対し監視パケットをユニキャストし、肯定応答を待機する。代わりに、子ノードは親によりポーリングされ、肯定応答により応答する。肯定応答が受信されない場合、監視パケットが再送され、所定の回数の再送に対して肯定応答が受信されない場合に、肯定応答されない親への接続性の修復を試みるローカルの再構成が実行される。オプションとして、ローカルの再構成を試みる前に、次の監視サイクルにおいて、監視パケットの再送が更に試みられ得る。
【００４３】
例としての各監視手法において、特定のタイム・スロットに含まれるノードのみが動作可能化され、そのタイム・スロットに含まれないノードはアクティブな低電力モードに留まる。
【００４４】
図７は、監視メッセージを伝送するための例としてのメッセージ交換図を示す。先の図面と同様に、横軸ｔは時間を表し、図の縦軸はネットワーク要素の階層的な順序を表す。同様に、時間軸ｔの上方の水平線はネットワーク要素の特定のインスタンスを表し、水平線を取り囲む陰影は優勢な動作又はモードを示し、矢印はＲＦメッセージ伝送を表す。しかし、先の図面と違い、図７の時間軸は、監視メッセージを伝達するための、親と１つの子とのレベルに基づく手法のみを表す分離されたタイム・スロットを含む全体的なタイム・スロット７を表す。
【００４５】
ＲＦにとって好ましくない及び／又は変化する環境においても機能を維持するため、例えばゆっくりとした中間の変化を検出し再構成／適応することを可能にするよう、ネットワークの全ての（例えば、現在は割当てられていないリンクをも含む）利用可能なリンクの品質がモニタリングされる。そのようなリンク品質のモニタリングは定期的に実行され得るが、例えば監視よりはかなり頻繁でなくてもよい（例えば、一日に１回）。上記のリンク検出段階と同様に、各ノードは、ＲＦ起動シーケンスに続く所定数の「リンク評価パケット」をブロードキャストし得る。パケットは、例えば所定の閾値以上の送信品質を持つパケットが検出される距離内などといった、定義された送信距離内のノードにより受信され得る。
【００４６】
リンク評価パケットは、例えば、全ての利用可能なリンクの統計を継続的に更新するために利用され得る。特定のリンクの品質が所定の閾値量より大きく変化した場合、ノードはリンク状態の変化に関する情報を、監視パケットに付加された（即ち、「積重ねられた」）データとしてクラスター・ヘッドに転送する。更に、エネルギー保有量に関する情報も付加され得る。リンク状態の変化に関する情報は、代わりに、警告パケットとしてブロードキャストされてもよい。
【００４７】
リンク評価パケットは、例えば警告又は制御パケットの送信に利用されるチャネルとは分離されたチャネルで送信され得る。分離されたチャネルは、監視と共有され得る。
リンク品質のモニタリングは、監視のために用意されたタイム・スロットの間に差し挟まれる特定の数のタイム・スロットが各ノードに割当てられるようスケジュールされ得る。リンク品質のモニタリングのために用意されたタイム・スロットは、「受信」距離内のノードが互いに衝突しないよう割当てられ得る。リンク品質モニタリングのスケジューリングは、タイム・スロットの予約に関する情報がネットワーク・トポロジの確立期間にノードに配布されるよう、クラスター・ヘッドにて実行され得る。
【００４８】
センサー・ノードのリセット（例えば、「監視タイムアウト」リセット又は「電力低下」リセット）が起きた場合、センサー・ネットワークは、例えば揮発性メモリに蓄積されていたためにリセット期間に失われてしまった関連情報を回復するために、再構成を実行し得る。そのような関連情報には、例えば、システム時間と、リセットしたノードの親と、リセットしたノードの子と、監視及び／又はリンク品質モニタリングのために割当てられたタイム・スロットとが含まれ得る。
【００４９】
例としての再構成方法によれば、センサー・ノードは、リセットしたノードの隣接のノードに対し、ＲＦ起動シーケンスに続いて「ＳＯＳパケット」を送信する。ＳＯＳパケットは、例えば、ノード識別子及びパケット・タイプを含み得る。リセットしたノードに関連付けられた受信するノード（即ち、親及び／又は子）は、ＳＯＳパケットに応じて、例えば、受信するノードの識別子と、タイム・スタンプと、監視及びリンク品質モニタリングのためのタイム・スロットとを含むパケットで応答する。ＳＯＳパケットは、関連情報が受信され又はタイムアウトに達するまで再送され得、オプションとして、数個のＲＦ起動シーケンスに先行される。所定のタイムアウト期間内に親からの応答が受信されない場合、関連する再構成情報がクラスター・ヘッドから受信されるよう、ＳＯＳメッセージが警告パケットとして再度ブロードキャストされる。しかし、１つ又はそれ以上の子からの応答がタイムアウト期間内に受信されない場合、ＳＯＳメッセージは再度ブロードキャストされず、それよりはむしろ、応答しない子が、リセット・ノード（即ち、それらの親）を介して、次の監視サイクル期間に再構成を試みるだろうとの想定がなされる。次の監視サイクル期間における子の２回目の試みがリセット・ノードの再構成に失敗した場合、監視の失敗に応じて、第２の例としての再構成方法が実行される。
【００５０】
第２の例としての再構成方法によれば、子ノードは、監視期間に応答しなかった親ノードへの接続性の修復を試みる。ノード障害が起きたのかリンク障害が起きたのかを区別するため、クラスター・ヘッドは、不成功に終わった監視サイクルに関するセンサー・ノードからの情報を利用し得る。監視のために、レベルに基づくタイム・スロットの手法又は親と１つの子とのレベルに基づくタイム・スロットの手法を利用する場合、「失われた」ノードは、割当てられた監視タイム・スロット内に、割当てられた親又は「可能性のある」親へのコンタクトを試みる。このプロセスは、数回の監視サイクルに渡り繰り返される。可能性のある親へのコンタクトが成功すると、可能性のある親は、「仮」の子に関する情報を、監視パケットに付加された（即ち、「積重ねられた」）データとしてクラスター・ヘッドに送信する。所定数の監視サイクルの後に、任意の可能性のある親のみが到達された場合、クラスター・ヘッドは、所望の最適ネットワーク・トポロジが維持されるよう、失われたノードに対する新しい親（必ずしも到達された可能性のある親のうちの１つでなくてもよい）を決定する。クラスター・ヘッドは、その後、失われたノード及び新しい親に対し、新しい親に関する情報を送信する。所定数の監視サイクルの後に可能性のある親又はもともと割当てられた親のいずれもが到達されない場合、失われたノードは、クラスター・ヘッドから再構成データを受信するため、警告パケットとしてＳＯＳメッセージをブロードキャストする。
【００５１】
第３の例としての再構成方法によれば、ネットワーク機能を中断なく保つため、１つ又はそれ以上のノードが所定の共通の時間に再構成を実行する。特に、クラスター・ヘッドは、例えば変更されたリンク品質、及び／又は１つ又はそれ以上のセンサー・ノードにおけるエネルギー保有量の変化に関する情報に基づいて、最適ネットワーク・トポロジを継続的に再計算する。例えば、センサー・ノードにおける所定の閾値を超える負荷の軽減、又はより信頼性の高いリンクの利用の所定の増加といった、ネットワークの現在の状態に対する或る種の改善がなされ得る場合、影響を受けるノードが新しいトポロジを採用し得るよう、それらのノードに対し、構成の変化に関する情報が優先度の低い制御メッセージとして送信される。
【００５２】
第４の例としての再構成方法によれば、既存のネットワークは、例えばネットワークの接続性を改善し、機能（例えば、センサー又はアクチュエータ）を追加し、又はネットワークの特定の領域における負荷を軽減するために必要とされる新しいノードを導入することにより拡張される。拡張による再構成を達成するため、新しいノードの一意のノード識別子及び地理上の位置が、ネットワーク暗号鍵が適用可能な場合には交換された鍵とともに記録及び格納される。既存のネットワーク・トポロジにおいて新しいノードの適正な位置を決定するため、１つ又はそれ以上の択一的な手法が利用され得る。具体的な択一的な手法は、例えば、新しいノードが、システムに機能（例えば、新しく設置されたドアのための新しいドア接触）を付加するためだけに含まれるのか、又はネットワークの接続性を直ちに向上させるために必要とされるのかにより異なり得る。
【００５３】
単に機能を追加するために含まれた新しいノードに対する適正な位置を決定するための第１の例としての手法において、新しいノードは、設置された後に、ＲＦ起動シーケンスをブロードキャストし、所定数の「新ノード・パケット」を送信する。これらの新ノード・パケットは、例えば、新しいノードのノード識別子と、新しいノードのノード・タイプと、該パケットを新しいノード・パケットとして識別するパケット・タイプとを含む。これに応じて、全ての受信するノードは、受信された新ノード・パケットに基づいて新しいノードに対するリンク品質統計を作成し、所定の時間が経過した後に、応答パケットを送信する。これらの応答パケットは、例えば、応答ノードのノード識別子と、応答ノードのレベルと、タイム・スタンプと、関連するリンク品質データとを含み得る。
【００５４】
応答パケットが受信されると、新しいノードは応答ノードの１つを仮の親として選択する。この選択は、例えば、受信されたリンク品質データに基づき得、該データは、例えば一方向のリンク品質と、応答ノードのノード・レベルと、受信信号強度のような仮のリンク品質統計とを含み得る。仮の親が選択されると、新しいノードは、このノードを介して「登録パケット」をクラスター・ヘッドに転送する。これに応じて、クラスター・ヘッドは、例えば監視及びリンク品質モニタリングのために割当てられたタイム・スロットを含み得る「トポロジ確立パケット」を送信することにより、新しいノードに応答する。新しいノードと隣接のノードとの間の全てのリンクに対する更に永続的なリンク品質は、リンク品質モニタリングの１つ又はそれ以上のサイクルの後で取得される。更新されたリンク品質データは、より永続的なトポロジを計算する特定のクラスター・ヘッドに送信された後に、特定の関係ノードに配布される。
【００５５】
ネットワークの接続性を即座に改善するために必要とされる新しいノードに対する適正な位置を決定する第２の例としての手法において、新しいノードは、設置された後に、ＲＦ起動シーケンスをブロードキャストし、所定数の「新ノード・パケット」を送信する。新ノード・パケットは、例えば新しいノードのノード識別子と、新しいノードのノード・タイプと、該パケットを新ノード・パケットとして識別するパケット・タイプとを含み得る。これに応じて、全ての受信するノードは、受信された新ノード・パケットに基づいて新しいノードに対するリンク品質統計を作成し、所定の時間が経過した後に応答パケットを送信する。これらの応答パケットは、例えば、応答ノードのノード識別子と、応答ノードのレベルと、タイム・スタンプと、関連するリンク品質データとを含み得る。応答パケットが受信されると、新しいノードは、応答する隣接の各ノードに対し、例えば、いつパケット・シーケンスの送信を開始するかを決定するためのシーケンス番号を特定し得るパケットにより肯定応答する。これに応じて、今度は隣接ノードが、割当てられたシーケンス番号に従った一連の「リンク評価パケット」を送信する。そのため、新しいノードは、双方向のリンク品質統計を迅速に取得することができる。その後、新しいノードは、応答ノードの１つを仮の親として選択し、全ての隣接ノードについて取得された双方向データを含む「登録パケット」を、選択した仮の親を介してクラスター・ヘッドに送る。これに応じて、クラスター・ヘッドは新しいノードに「トポロジ確立パケット」を送信し、該パケットは、例えば、新しいノードに新たに割当てられた永続的な親のノード識別子と、新しいノードに割当てられた子と、監視及びリンク品質モニタリングのために割当てられたタイム・スロットとを含み得る。そのため、新たに割当てられた親は、転送されたパケットから親としての新しい役割を推論することができる。その後、新しいノードは自らに割当てられた子に対し、新しい親として、子のための新しい監視タイム・スロットとともに、新しいノードの親の変化に関する通知を行う。次いで、次の監視サイクル期間に、子は「昔の」親に関係の変化を通知し、新しい親のみによる監視を始める。
【００５６】
クラスター・ヘッドに障害があった場合、センサー・ネットワークは、障害を起こしたクラスター・ヘッドを除く新たなトポロジを形成するために再構成を実行する。第５の例としての再構成手法によれば、障害を起こしたクラスター・ヘッドの影響を受けるノードのために、新しいトポロジ及び新しいタイム・スロットが再計算される。しかし、クラスター・ヘッド・ネットワークは独自の監視及び再構成機構を持ち得るため、センサー・ノード・ネットワークは、クラスター・ヘッド・ネットワーク自身が適正に再構成されるまで、新しいトポロジ・データの再計算、及び影響を受ける全ノードのためのタイム・スロットの再計算を待機してもよい。従って、クラスター・ヘッド・ネットワークが残されたクラスター・ヘッドのための新しいトポロジを再計算し終えた後に、影響を受けたセンサー・ノードのための新しいトポロジ及び新しいタイム・スロットが再計算され、例えば優先度の高い制御メッセージを介してそれらのノードに伝達される。
【図面の簡単な説明】
【００５７】
【図１Ａ】図１Ａは、センサー及び／又はアクチュエータを無線でネットワーク接続するための例としてのプロトコル方法を示すフローチャートである。
【図１Ｂ】図１Ｂは、仮トポロジ及び確立段階に対する例としてのメッセージ交換図を示す。
【図２】図２は、リンク検出・評価段階のための例としてのメッセージ交換図を示す。
【図３】図３は、センサー・ノード登録段階のための例としてのメッセージ交換図を示す。
【図４Ａ】図４Ａは、センサー・ノード・ネットワークの確立されたトポロジを配布するための例としてのメッセージ交換図を示す。
【図４Ｂ】図４Ｂは、ＲＦチャネルをモニタリングするための例としての方法を示す。
【図５】図５は、優先度の高い制御メッセージを送信するための例としてのメッセージ交換図を示す。
【図６】図６は、警告メッセージを送信するための例としてのメッセージ交換図を示す。
【図７】図７は、監視メッセージを送信するための例としてのメッセージ交換図を示す。
【図１Ａ】
2005515696.tif 000003
【図１Ｂ】
2005515696.tif 000004
【図２】
2005515696.tif 000005
【図３】
2005515696.tif 000006
【図４Ａ】
2005515696.tif 000007
【図４Ｂ】
2005515696.tif 000008
【図５】
2005515696.tif 000009
【図６】
2005515696.tif 000010
【図７】
2005515696.tif 000011
【手続補正書】
【提出日】平成16年9月14日(2004.9.14)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
センサー・ノードを無線でネットワーク接続する方法であって、
複数のノード・レベル及びクラスター・ヘッド・ネットワークを備える階層的な方法で配置されたセンサー・ノード・ネットワークに、センサー・ノードを設置するステップと、
前記センサー・ノードに一意の識別子を割当てるステップと、
前記センサー・ノード・ネットワークを初期化するステップと、
前記センサー・ノードをタスクを実行するよう起動するステップと、
前記タスクが完了した場合に、前記センサー・ノード・ネットワークにおける全てのノード・レベルに対するメッセージの伝達に先立って、前記センサー・ノードをアクティブな低電力モードに設定するステップと、
を備える方法。
【請求項２】
請求項１記載の方法であって、更に、前記センサー・ノードに暗号鍵を配布するステップを備える方法。
【請求項３】
請求項１記載の方法であって、前記センサー・ノード・ネットワークを初期化する前記ステップが、
仮トポロジを確立し、前記センサー・ノード・ネットワークを同期させるステップと、
前記センサー・ノード・ネットワークの少なくとも１つのリンクを検出し評価するステップと、
前記センサー・ノード・ネットワークのセンサー・ノードを、前記クラスター・ヘッド・ネットワークのクラスター・ヘッドに登録するステップと、
を備える方法。
【請求項４】
請求項３記載の方法であって、仮トポロジを確立し同期させる前記ステップが、更に、
下位レベルのノードから上位レベルのノードへ起動信号をブロードキャストするステップと、
前記下位レベルのノードから前記上位レベルのノードへ初期化パケットを送信するステップと、
前記上位レベルのノードを同期させるステップと、
前記上位レベルのノードから前記下位レベルのノードへ仮登録パケットを送信するステップと、
前記起動信号をブロードキャストする前記ステップ、前記初期化パケットを送信し同期させる前記ステップ、及び前記仮登録パケットを送信する前記ステップを、全てのノード及び所定レベルより上の全てのノードのいずれかに到達するまで繰り返すステップと、
を備える方法。
【請求項５】
請求項３記載の方法であって、検出し評価する前記ステップが、更に、複数のリンク評価パケットをブロードキャストするステップを備える方法。
【請求項６】
請求項５記載の方法であって、前記リンク評価パケットが完全に無作為な方法でブロードキャストされる方法。
【請求項７】
請求項５記載の方法であって、前記リンク評価パケットが、タイム・スロットに分割された、無作為化された又は決定性の方法でブロードキャストされる方法。
【請求項８】
請求項７記載の方法であって、ブロードキャスト期間が、前記センサー・ノード・ネットワークの各レベルのためのタイム・スロットに分割される方法。
【請求項９】
請求項８記載の方法であって、前記ブロードキャストが、前記タイム・スロットのわずかな一部分でのみ発生する方法。
【請求項１０】
請求項８記載の方法であって、前記ブロードキャストが前記タイム・スロットにおいて無作為に発生する方法。
【請求項１１】
請求項８記載の方法であって、前記ブロードキャストが、任意の２つのノードが最大でも１つのタイム・スロット内でのみ干渉することを保証するコードに基づいて発生する方法。
【請求項１２】
請求項３記載の方法であって、登録の前記ステップが、更に、複数の登録パケットを送るステップを備える方法。
【請求項１３】
請求項１２記載の方法であって、前記登録パケットが、無作為化された個別ノードの手法により送られる方法。
【請求項１４】
請求項１２記載の方法であって、前記登録パケットが、タイム・スロットが割当てられたレベルごとの手法により送られる方法。
【請求項１５】
請求項１４記載の方法であって、ブロードキャスト期間が、前記センサー・ノード・ネットワークの各レベルに対するタイム・スロットに分割される方法。
【請求項１６】
請求項１２記載の方法であって、上位レベル・ノードからの登録データが、下位レベル・ノードにより送信される登録パケットに積重ねられる方法。
【請求項１７】
請求項３記載の方法であって、更に、全センサー・ノードのための全体的なネットワーク・トポロジを計算するステップを含む方法。
【請求項１８】
請求項１７記載の方法であって、前記ネットワーク・トポロジが、電力消費を低減するよう計算される方法。
【請求項１９】
請求項１７記載の方法であって、全てのノードの電池寿命が実質的に等しくなるよう、前記ネットワーク・トポロジが計算される方法。
【請求項２０】
請求項１７記載の方法であって、更に、前記全体的なネットワーク・トポロジを各クラスター・ヘッドに配布するステップを備える方法。
【請求項２１】
請求項２０記載の方法であって、前記ネットワーク・トポロジを配布するステップが、更に、複数のトポロジ確立パケットを送信するステップを備える方法。
【請求項２２】
請求項２１記載の方法であって、前記トポロジ確立パケットが無作為な方法で送信される方法。
【請求項２３】
請求項２１記載の方法であって、前記トポロジ確立パケットがレベルごとにタイム・スロットを割当てられる方法で送信される方法。
【請求項２４】
センサー・ノード・ネットワークのセンサー・ノードに対する送信リンクのＲＦチャネルをモニタリングする方法であって、
ＲＳＳＩ読み出しを実行するステップと、
プリアンブルにおいて特有のＲＦ起動シーケンスを検索するステップと、
有効な開始シーケンスを検索するステップと、
入力パケットのパケット・ヘッダを読み取るステップと、
前記入力パケットの内容に従ってタスクを実行するステップと、
前記センサー・ノードをアクティブな低電力モードに設定するステップと、
を備え、
前記特有のＲＦ起動シーケンスが、当該センサー・ノードにより実行されるべきタスクに従って複数のＲＦチャネルに分離され、前記タスクがそれぞれに要求される待ち時間に応じて異なる周波数でモニタリングされるよう、前記タスクに相対的な優先度が割当てられる方法。
【請求項２５】
請求項２４記載の方法であって、有効な開始シーケンスを検索する前記ステップが、更に、
前記の割当てられた相対的な優先度に応じて前記有効な監視シーケンスを走査するステップ
を備える方法。
【請求項２６】
複数のノード・レベル及びクラスター・ヘッド・ネットワークを備える階層的な方法で配置されたセンサー・ノード・ネットワークを動作させる方法であって、
タスクを実行するようセンサー・ノードを起動するステップと、
メッセージを送信するステップと、
前記タスクが完了した場合に、前記センサー・ノード・ネットワークにおける全てのノード・レベルに対するメッセージの伝達に先立って、前記センサー・ノードをアクティブな低電力モードに設定するステップと、
を備える方法。
【請求項２７】
請求項２６記載の方法であって、前記センサー・ノードがおよそ毎秒に１〜４回起動される方法。
【請求項２８】
請求項２６記載の方法であって、前記メッセージを送信するステップが、更に、複数の優先度の高い制御パケットを送信するステップを備える方法。
【請求項２９】
請求項２８記載の方法であって、前記優先度の高い制御パケットが、幾つかの前記ノード・レベルにおけるノードに対しマルチキャストで送信される方法。
【請求項３０】
請求項２８記載の方法であって、前記優先度の高い制御パケットが、単一のノードにユニキャストで送信される方法。
【請求項３１】
請求項２８記載の方法であって、更に、監視肯定応答パケットに優先度の低いメッセージのみを積重ねるステップを備える方法。
【請求項３２】
請求項２６記載の方法であって、前記メッセージを送信するステップが、更に、複数の警告パケットを送信するステップを備える方法。
【請求項３３】
請求項３２記載の方法であって、前記警告パケットがディレクテド・フラッディング手法で送信される方法。
【請求項３４】
請求項３３記載の方法であって、更に、
前記警告パケットの送信の前に起動シーケンスをブロードキャストするステップと、
前記起動シーケンス及び警告パケットを、中間センサー・ノードを介して前記クラスター・ヘッド・ネットワークに送るステップと、
を備える方法。
【請求項３５】
請求項２６記載の方法であって、前記メッセージを送信するステップが、更に、警告パケットを、別途定義されたトポロジを介してユニキャストで送信するステップを備える方法。
【請求項３６】
請求項２６記載の方法であって、前記メッセージを送信するステップが、更に、レベルに基づくタイム・スロットの手法、親と複数の子とのレベルに基づくタイム・スロットの手法、及び、親と子とのレベルに基づくタイム・スロットの手法のうちの一つにより複数の監視パケットを送信するステップを備える方法。
【請求項３７】
請求項３６記載の方法であって、前記監視パケットがおよそ１時間に一度送信される方法。
【請求項３８】
請求項２６記載の方法であって、前記メッセージを送信するステップが、更に、複数のリンク評価パケットを送信するステップを備える方法。
【請求項３９】
請求項３８記載の方法であって、前記リンク評価パケットが、警告パケット及び制御パケットのうちの少なくとも一つから分離されたＲＦチャネルで送信される方法。
【請求項４０】
請求項３８記載の方法であって、前記リンク評価パケットが１日に一度送信される方法。
【請求項４１】
請求項２６記載の方法であって、前記メッセージを送信するステップが、更に、リセットに応じてＳＯＳパケットを送信するステップを備える方法。
【請求項４２】
請求項２６記載の方法であって、前記メッセージを送信するステップが、更に、新ノード・パケットを送信するステップを備える方法。
【請求項４３】
請求項２６記載の方法であって、前記メッセージを送信するステップが、更に、登録パケットを送信するステップを備える方法。
【請求項４４】
請求項１記載の方法であって、更に、前記センサー・ノードのクロックを更新するよう、肯定応答される監視パケットにより前記センサー・ノード・ネットワークを監視するステップを備える方法。
【請求項４５】
請求項１記載の方法であって、前記センサー・ノードのクロックが、該ノードのレベルに関して同期される方法。
【請求項４６】
請求項３記載の方法であって、前記センサー・ノード・ネットワークの前記少なくとも１つのリンクが、電力レベル、及び到達可能なネットワーク要素へのパケット成功率の少なくともいずれかに基づいて評価される方法。
【請求項４７】
請求項３記載の方法であって、前記センサー・ノード・ネットワークの前記少なくとも１つのリンクが、該少なくとも１つのリンクの少なくとも１つの統計を更新するために評価される方法。
【請求項４８】
請求項３６記載の方法であって、前記監視パケットが、周期的に送信される方法。
【国際調査報告】
2005515696.tif 000012