(57)【要約】【課題】ノードのウェイクアップをスケジューリングし、同期マルチ・ノード・アドホック・ネットワーク内で適応可能にノードのスリープ期間を設定する方法を提供すること。【解決手段】マルチ・ノード・ネットワークにおける方法であって、前記方法は、タイム・スロットを設けたフレームの少なくとも１つの対応するスロット期間に少なくとも１つのノードを低消費電力モードであるスリープ・モードからウェイクアップする工程を含む。また、マルチ・ノード・ネットワークの少なくとも１つのノードで、ノードがスリープする期間はノードの残留エネルギー、近傍ノードの残留エネルギー、近傍ノードの密度、およびそれらの組合せに基づく。【選択図】  図１
2004336779.tif 000002
【特許請求の範囲】
【請求項１】
マルチ・ノード・ネットワークにおいて、
タイム・スロットを設けたフレームの少なくとも１つの関連スロット期間中に、少なくとも１つのノード（１０）を低消費電力モードであるスリープ・モードからウェイクアップする工程を含む方法。
【請求項２】
前記ノード（１０）で、近傍ノードによって使用されるウェイクアップ決定プロセスを用いて、前記近傍ノードがウェイクアップする時刻を決定する工程をさらに含む請求項１に記載の方法。
【請求項３】
前記ウェイクアップ決定プロセスが前記ノード（１０）のアドレスに基づく請求項２に記載の方法。
【請求項４】
近傍ノードがそれぞれのスリープ・モードからいつウェイクアップするかを前記ノード（１０）が認識できるように、前記近傍ノードのアドレスを前記ノード（１０）で受信する工程をさらに含む請求項３に記載の方法。
【請求項５】
前記近傍ノード（１０）がそれぞれのスリープ・モードからいつウェイクアップするかに関する情報に基づいて、前記ノード（１０）から送信を宛先に向ける工程をさらに含む請求項４に記載の方法。
【請求項６】
マルチ・ノード・ネットワーク上の少なくとも１つのノードにおいて、
前記ノード（１０）で、前記ノード（１０）の残留エネルギーに基づいてある期間スリープする工程を含む方法。
【請求項７】
期間が前記ノード（１０）の残留エネルギー、近傍ノードの残留エネルギーおよび近傍ノードの密度の少なくとも１つに基づく請求項６に記載の方法。
【請求項８】
前記ノード（１０）のスリーパ・クラスを決定する工程をさらに含み、スリープ工程が決定されたスリーパ・クラスに対応する期間だけスリープする請求項６に記載の方法。
【請求項９】
決定されたスリーパ・クラスに基づいて、他のノードから受信した送信を中継するノード（１０）である中継ノードとして動作する工程をさらに含む請求項８に記載の方法。
【請求項１０】
スリーパ・クラスの変更から選択的にバックオフする工程をさらに含む請求項８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
マイクロ電気機械システム（ＭＥＭＳ）技術、無線通信、およびデジタル回路の近年の進歩によって、サイズが小さく、近距離で束縛なく通信できる低コスト、低消費電力の多機能センサ・ノードの開発が可能になった。検知、データ処理および通信用構成部品からなるこれらの小型のセンサ・ノードは、多数のノードが集合的に働くことに基づくセンサ・ネットワークという概念に影響を及ぼす。
【背景技術】
【０００２】
センサ・ネットワークは多数のセンサ・ノードから構成される。センサ・ネットワークは、さまざまな周囲条件を監視できる地震センサ、低サンプリング・レート磁気センサ、熱センサ、視覚センサ、赤外線センサ、音響センサ、レーダ・センサなどの様々な種類の多数のセンサから構成されていてもよい。
センサ・ノードはアクチュエータの連続検知、イベント検出、イベント識別、位置検出、およびローカル制御に使用される。これらのノードのマイクロ検知と無線通信の概念によって多くの新しい応用分野が約束される。その例として、軍事、環境、健康、家庭およびその他の商業分野が挙げられる。宇宙開発、化学処理、災害救援などのカテゴリを加えてこの分類を広げることができる。
【０００３】
図１はセンサ・ネットワークの一例を示す。図示のように、複数のセンサ・ノード１０がセンサ・フィールド１２内に分散されている。センサ・ノード１０が例えばイベントを検知すると、センサ・ノード１０はそのイベントに関する情報を含むメッセージをシンク１６に送信しようとする。シンク１６は例えばインターネット、無線通信ネットワーク、衛星ネットワークなどの通信ネットワーク１８へのゲートウェイとすることができる。メッセージは通信ネットワーク１８によってタスク・マネジャ２０（サーバまたはコンピュータ・システムなど）にルーティングされ、タスク・マネジャ２０はメッセージに含まれる情報に基づいてタスクを実行する。
【０００４】
例えばイベントを感知した後でメッセージを送信する検知ノード１０はソース・ノード１４と呼ばれる。メッセージをシンク１６に送信する際、ソース・ノード１４は、シンク１６がソース・ノード１４からメッセージを直接受信できる十分に高い電力で送信できないかまたはシンク１６に十分近い位置にない場合がある。したがって、センサ・ノード１０は近傍に位置する他のセンサ・ノード１０からメッセージを受信し、他の近傍のセンサ・ノード１０に受信メッセージを中継してメッセージがシンク１６に向かって進むように構成されている。メッセージがソース・ノード１４からシンク・ノード１６に移動する場合に経由するセンサ・ノード１０は中継ノード２２と呼ばれる。各センサ・ノード１０はソース、中継および／またはシンクの役割を引き受けることができる。あるセンサ・ノード１０から別のセンサ・ノード１０へのメッセージの各転送はホップと呼ばれ、ホップを完了するための時間はホップ待ち時間と呼ばれる。
【０００５】
センサ・ネットワークが抱える課題の１つは消費電力を最小限にすることである。センサ・ノードにアクセスできないことがしばしばあり、センサ・ノードの寿命、すなわちセンサ・ネットワークの寿命はセンサ・ノードの電源の寿命（バッテリの寿命など）によって変化する。アドホック・ネットワーク（センサ・ネットワークなど）の場合、処理電力が待ち受けと受信という２つのクラスに分類されているノード（センサ・ノードなど）での送信／受信処理電力を最小限にする技法によって効率的なエネルギー利用が達成できる。メッセージ送受信が頻繁でないためにノードの送信／受信状態がまれなときには、ノードが受信側処理を実行しないスリープ動作モードに入ることができるようにして大幅なエネルギー節約が達成できる。スリープ・パターンの研究は通常２つのケースを考えている。すなわち、非同期、独立のスリープ・パターンを備えたノードと近傍でのノード間の同期スリープ／ウェイクアップ周期である。
【０００６】
非同期システムでは、ノードがウェイクアップすると、ノードがスリープ状態だったときに到着したメッセージの再送を受けるために相当の期間ウェイクアップ状態でなければならない。ノードのデューティサイクル全体（したがって、そのエネルギー消費）は、極端に小さい再送タイムアウト値に起因する過剰なオーバーヘッドを避けるために５０％程度低減できるにすぎない。新しいウェイクアップ・ノードの延長されたリスニング期間の必要は、アクティブなノードに、ウェイクアップ状態のままでいてエネルギーが尽きるまで連続してリスンするように要求することで解消できる。この技法は受信側のウェイクアップ待ち時間を解消できるが、検知／監視処理をアクティブな状態にしたままでノードの送受信処理をオフにするという潜在的なエネルギー節約を利用していない。
【０００７】
エネルギー消費は、マルチスロット・フレーム内の同じタイム・スロットでウェイクアップするように近傍のすべてのノードを同期化することによって低減できる。ただし、近傍のすべてのメッセージ交換はフレームごとに１回しかできないので、ホップあたり平均待ち時間はフレーム期間の半分である。同じ近傍の多数のノード・ペアが同じフレーム内で通信しようとすると過剰な衝突（したがって遅延）が発生しやすくなる。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
スリープ・モードはエネルギーの著しい節約になるが、大幅な遅延を招き、マルチ・ノード・ネットワークのメッセージを適時に搬送する能力を損なうおそれがある。大半の既存のスリープ手法は、エネルギー節約と待ち時間との柔軟な兼ね合いを考慮していない。
【課題を解決するための手段】
【０００９】
本発明はノードのウェイクアップをスケジューリングし、同期マルチ・ノード・アドホック・ネットワーク内で適応可能にノードのスリープ期間を設定する方法を提供する。ネットワークは同期化されているので、ネットワーク内のメッセージの通信のためのスロットとフレームの構造を定義することができる。ネットワーク内の１つまたは複数のノードはスリープ・モードに入る（すなわち、低電力消費ノードである）。このスリープ・モードで１つまたは複数のノードはフレームの所定の（１つまたは複数の）スロットでウェイクアップし、直近のノードからの送信がないかリスンする。スリープ・モードでの各ノードのウェイクアップ・スロットは周知のプロセス（例えば、いずれかの周知のハッシング法）を用いて決定できる。さらに、隣接ノードが採用するウェイクアップ・スロットを決定するプロセスの情報を用いて、ノードはその隣接ノードがいつウェイクアップするかを判定することができる。実施例では、各ノードを識別するのにノード・アドレスが使用される。このアドレスは製造業者によってノードに割り当てられた一意の識別子でもよい。次いで、スリープ・モードの各ノードは、いずれかの周知のハッシング法を用いてアドレスをフレーム内の１つまたは複数のスロットにハッシュする。ノードがハッシュされるスロットはそのノードのウェイクアップ・スロットになる。したがって、ノードのスリープ期間が満了すると、ノードはそのウェイクアップ期間中ウェイクアップ状態になる。このようにして、各ノードはフレームのスロットにランダムに分散される。さらに、ノードがその直近のノードのアドレスと採用されているそれぞれのハッシング法を知っていれば、その近傍のウェイクアップ・スロットを決定できる。この近傍ノードのウェイクアップ・スロット情報を用いて近傍の送信のスケジューリングが可能である。
【００１０】
一実施例では、これらのノードは所定のフレーム数ごとに出現する近傍制御間隔にウェイクアップする。各ノードは、そのアドレスとこの間隔中の位置を含むメッセージを送信し、近傍ノードのアドレスおよび／または位置を受信する。一実施例では、相手ノードから受信した送信信号の信号強度が信号強度閾値を超えていると、ノードは相手を近傍のノードと見なす。
【００１１】
一実施例では、各ノードはＭ個のスリーパ・クラス（Ｍは２以上の整数）に属することができる。各スリーパ・クラスはそれに関連する事前定義されたスリープ期間と、それに関連する事前定義されたネットワーク動作特性とを有する。事前定義されたネットワーク動作特性は、例えば、特定のスリーパ・クラスのノードが中継ノードとして動作できるかどうかを含む。中継ノードは他のノードからのメッセージを受信して再送するノードである。
【００１２】
一実施例では、スリーパ・クラスが下位であるほど、スリープ期間は短く、おそらくは、ネットワーク動作特性によってノードに課される処理負荷が大きくなる。すなわち、スリーパ・クラスが下位であるほど、ノードはより頻繁にウェイクアップし、おそらくはより大きい処理負荷を課される（例えば、中継ノードとして動作する）のでより多くのエネルギーを消費することになる。例えば、一実施例では、所定のスリーパ・クラスより下位のノードは中継ノードとして動作する。
【００１３】
ノードは動作中にそのスリーパ・クラスを適応可能に変更する。これはノードのスリープ期間、おそらくは処理負荷、またエネルギー消費を適応可能に変更する効果を生む。
【００１４】
一実施例では、この適応型変更動作は近傍制御期間に実行される。この適応型変更動作はノードのみの残留エネルギー、近傍ノードの残留エネルギー、ノード密度、およびそれらの組合せに基づいて実行できる。
【００１５】
本発明は以下の詳細な説明と添付図面とからより深く理解できよう。図面では同じ要素は同じ参照番号で表される。図面は例示のために掲げたものであって本発明を限定するものではない。
【発明を実施するための最良の形態】
【００１６】
マルチ・ノード・アドホック・ネットワークのための本発明の方法をセンサ・ネットワーク、特に図１のセンサ・ネットワークに関して以下に説明する。ただし、本発明は図１のセンサ・ネットワークにも、また厳密に言えばセンサ・ネットワークにも限定されない。
【００１７】
本発明は同期マルチ・ノード・アドホック・ネットワーク内のノードのウェイクアップのスケジューリングとノードのすべての期間を適応可能に設定する方法を提供する。図１のセンサ・ネットワークなどのマルチ・ノード・アドホック・ネットワークの同期化は周知である。例えば、ある周知の技法によれば、センサ・ノード１０などの各ノードはグローバル・ポジショニング・センサ（ＧＰＳ）受信機を含む。この技法によってマイクロ秒オーダでのノード間の同期化が可能になる。マルチ・ノード・ネットワーク内の測距および分散同期化の別の方法も周知である。
【００１８】
ネットワークは同期化されているので、ネットワーク内のメッセージ通信のためのスロットとフレームの構造を定義できる。図２は本発明の方法を採用するセンサ・ネットワークが使用するスロットとフレームの構造を示す。図示のように、フレームＦはそれぞれ期間がＴのＮ個のスロットＳ１、Ｓ２、．．．ＳＮを含む（ただしＮは２以上の整数である）。したがって、フレームＦの期間はＴ＊Ｎである。さらに詳しく見ると、Ｐ個のフレームＦが終了するたびに近傍制御期間が挿入される。近傍制御期間については後に詳述する。
【００１９】
次いで、図１のセンサ・ネットワークで実施されるノードのウェイクアップのスケジューリングについて図２のスロットとフレームの構造を参照しながら説明する。各センサ・ノード１０はアドレスを含む。例えば、アドレスは製造業者によってセンサ・ノード１０に割り当てられた一意の識別子である。各センサ・ノードはいずれかの周知のハッシング法を用いてアドレスをフレームＦ内の１つまたは複数のスロットＳにハッシュする（例えば、無線移動局が一意の識別子を特定の呼び出しチャネルにハッシュするためのハッシング法を用いて）。センサ・ノード１０がハッシングするスロットＳはそのセンサ・ノード１０にとってウェイクアップ・スロットになる。したがって、センサ・ノード１０のスリープ期間が満了すると、センサ・ノード１０はそのウェイクアップ・スロット中ウェイクアップする。このようにして、センサ・ノード１０はフレームＦのスロットＳにランダムに分散される。センサ・ノード１０のスリープ期間の決定については以下に詳述する。
【００２０】
一実施例では、近傍制御期間中、すべてのセンサ・ノード１０はウェイクアップ状態である。センサ・ノード１０はこの期間中のウェイクアップ・スロット、アドレスおよび／または位置を含むメッセージを送信し、同じ情報をその近傍ノードから受信する。一実施例では、センサ・ノード１０はもう１つのセンサ・ノード１０から受信した送信信号の信号強度が信号強度閾値を超えていると、他のセンサ・ノード１０を近傍のノードと認識する。一実施例では、センサ・ノード１０は相手のセンサ・ノード１０の位置情報も用いてそのセンサ・ノード１０が近傍のセンサ・ノード１０であるか否かを判定する。一実施例では、センサ・ノード１０は上記の信号強度要件を満たすセンサ・ノード１０の数を決定する。センサ・ノード１０に関するセンサ・フィールド１２の密度を示すこの決定された数に基づいて、センサ・ノード１０は近傍半径を確立する。例えば、センサ・ノード１０は決定された数を近傍半径にマッピングするルックアップ・テーブルを記憶する。近傍半径に入る位置を有する相手センサ・ノード１０は近傍センサ・ノード１０と判定される。
【００２１】
各センサ・ノード１０はその近傍センサ・ノード１０のアドレスと位置とを記憶し、近傍センサ・ノード１０がウェイクアップするスロットＳを決定する。センサ・ノード１０はフレーム期間中にその近傍センサ・ノード１０がいつウェイクアップするかを認識し、かつ近傍センサ・ノード１０の位置を認識しているので、センサ・ノード１０は一種の方向性送信を実行できる。すなわち、特定の方向にあるこれらのセンサ・ノード１０がウェイクアップする時に送信を行うことでセンサ・ノード１０は特定の方向にメッセージを送信する。さらに、センサ・ノード１０が所望の単一ホップ遅延予算の間にウェイクアップする１つまたは複数の近傍センサ・ノード１０にメッセージを転送すると、ホップ単位の遅延の制限を満たすことができる。
【００２２】
次に、同期マルチ・ノード・アドホック・ネットワーク内のノードのスリープ期間を適応可能に設定する方法を、図１のセンサ・ネットワークについて図２を参照しながら説明する。一実施例では、センサ・ノード１０はＭ個のスリーパ・クラス（Ｍは２以上の整数）の１つに属することができる。各スリーパ・クラスはそれに関連する事前定義されたスリープ期間と、それに関連する事前定義されたネットワーク動作特性とを有する。事前定義されたネットワーク動作特性は、例えば、特定のスリーパ・クラスのノードが中継ノードとして動作できるか否かを含む。中継ノードは他のセンサ・ノード１０からのメッセージを受信して中継するセンサ・ノード１０である。
【００２３】
一実施例では、スリーパ・クラスが下位であるほど、スリープ期間は短く、おそらくは、ネットワーク動作特性がセンサ・ノード１０に課す処理負荷も重くなる。すなわち、スリーパ・クラスが下位であるほど、センサ・ノード１０はより頻繁にウェイクアップしおそらくはより重い処理負荷を課される（例えば、中継ノードとして動作する）のでより多くのエネルギーを消費することになる。例えば、一実施例では、所定のスリーパ・クラスより下位のセンサ・ノード１０は中継ノードとして動作する。
【００２４】
センサ・ノード１０が初めて操作を開始すると、センサ・ノード１０はデフォルトのスリーパ・クラスで開始する。一実施例では、デフォルトのスリーパ・クラスは最下位のスリーパ・クラスである。ただし、センサ・ノード１０は動作中にそのスリーパ・クラスを適応可能に変更する。これはセンサ・ノード１０のスリープ期間、おそらくは処理負荷、またエネルギー消費を適応可能に変更する効果を生む。
【００２５】
一実施例では、この適応型変更動作は近傍制御期間に実行される。この適応型変更動作はセンサ・ノード１０のみの残留エネルギー、近傍センサ・ノード１０の残留エネルギー、センサ・ノード１０の近傍のノード密度、およびそれらの組合せに基づいて実行できる。
【００２６】
各センサ・ノード１０は動作電源となる利用可能なエネルギーの量、例えばバッテリ寿命を含む。この利用可能なエネルギーの量は通常センサ・ノード１０の残留エネルギーと呼ばれる。
【００２７】
適応型変更動作がセンサ・ノード１０の残留エネルギーのみに基づいて実行されると、センサ・ノード１０は残留エネルギーをスリーパ・クラスにマッピングするルックアップ・テーブルを記憶する。ルックアップ・テーブルは、残留エネルギーが大きければ大きいほどスリーパ・クラスが下位になるように残留エネルギーをスリーパ・クラスにマッピングする。したがって、残留エネルギーとスリープ期間との間、さらにおそらくは処理負荷との間には反比例の関係が存在する。センサ・ノード１０はルックアップ・テーブルを用いてその残留エネルギーをスリーパ・クラスに割り当てる。残留エネルギーを各スリーパ・クラスを定義する１組の閾値と比較することで、センサ・ノード１０はルックアップ・テーブルを用いずに同じ結果を達成できる。例えば、センサ・ネットワークは２つのスリーパ・クラス−短いスリーパ・クラスと長いスリーパ・クラス−を含む場合、必要な閾値は１つだけである。残留エネルギーが閾値以下である場合、センサ・ノード１０はそれ自身を長いスリーパであると判定し、そうでない場合、センサ・ノード１０はそれ自身を短いスリーパであると判定する。
【００２８】
センサ・ノード１０がその残留エネルギーと近傍センサ・ノード１０の残留エネルギーとに基づいてそのスリーパ・クラスを決定する時、近傍制御期間中にセンサ・ノード１０が送信するメッセージもそのメッセージを送信するセンサ・ノード１０の残留エネルギーを示している。一実施例では、センサ・ノード１０は近傍センサ・ノード１０の平均残留エネルギーを決定し、決定された平均残留エネルギーを用いていくつかのルックアップ・テーブルの１つを選択する。ルックアップ・テーブルの各々は上述の実施例と同じ構造を有する。ただし、各ルックアップ・テーブルでは異なるスリーパ・クラスに対応して残留エネルギーも異なる。例えば、平均残留エネルギーが大きければ大きいほど、センサ・ノード１０が下位スリーパ・クラスの資格を得るのに必要な残留エネルギーは大きくなる。
【００２９】
一実施例では、センサ・ノード１０は、例えば、平均残留エネルギーに基づいてそのスリーパ・クラスを決定する閾値を確立する。例えば、２つのスリーパ・クラスの例では、センサ・ノード１０は閾値として平均残留エネルギーを確立する。したがって、センサ・ノード１０の残留エネルギーが平均残留エネルギーを超えると、センサ・ノード１０はそれ自身を短いスリーパであると判定し、そうでない場合、センサ・ノード１０はそれ自身を長いスリーパであると判定する。
【００３０】
一実施例では、センサ・ノード１０は、降順残留エネルギーに基づいてそれ自身と近傍センサ・ノード１０とをランク付けし、そのランクに基づいてそのスリーパ・クラスを決定する。例えば、２つのスリーパ・クラスの実施例では、センサ・ノード１０がランク付けされた複数のセンサ・ノード１０の上半分に位置する場合、センサ・ノード１０はそれ自身を短いスリーパであると判定し、そうでない場合、センサ・ノード１０はそれ自身を長いスリーパであると判定する。
【００３１】
次いで、センサ・ノード１０の近傍のノード密度を考慮するスリーパ・クラスを適応可能に変更する実施例について説明する。この実施例では、近傍制御期間中に、センサ・ノード１０はその送信メッセージ内に現在のスリーパ・クラスも示している。これらのメッセージから、各センサ・ノード１０は近傍ノードの数を決定する。近傍ノード密度と呼ばれるこの数が閾値を超えるかまたはセンサ・ノード１０がすでに中継ノードの資格を得ている場合、センサ・ノード１０は上記の方法の１つに従ってそのスリーパ・クラスを決定する。ただし、近傍ノード密度が閾値を超えず、センサ・ノード１０が中継ノードの資格を得ていない場合、センサ・ノード１０はセンサ・ノード１０に中継ノードの資格を与える最上位のスリーパ・クラスに変更する。
【００３２】
本発明の別の態様として、センサ・ノード１０がそのスリーパ・クラスを変更する決定をした場合、センサ・ノード１０はスリーパ・クラスを変更する前にいずれかの周知のバックオフ動作（例えば、通信間の衝突を回避するためのバックオフ動作）を実行してもよい。バックオフ動作はスリーパ・クラスの変更を近傍制御期間出現回数だけ遅らせる。別法として、ウェイクアップ・スロットに似た交代制スケジュールを採用してスリーパ・クラスを変更してもよい。したがって、センサ・ノード１０が以降の近傍制御期間中、バックオフ期間の満了前に変更が発生しないかまたは別の変更が発生すると判定する場合、センサ・ノード１０は決定したようにスリーパ・クラスを変更しない。
【００３３】
本発明に関して述べた閾値はネットワーク設計者がネットワーク仕様などに基づいて設定する設計パラメータである。
【００３４】
本発明の方法には各ノードの直近の決定論的交代制スリープ・スケジュールがあるため、ホップあたりの遅延を大幅に低減することができる。スリープ・パターンは動的な形で自律的に調整され、待ち時間、近傍のノード密度および／または残留エネルギーを制御する。さらに、各ノードの直近のスリープ・スケジュール情報を明示的に交換する必要はない。この情報は近傍制御期間中に交換される情報から引き出すことができる。また、各スリーパ・クラスが作成するスロット式ウェイクアップ構造および交代制スリープ期間によって待ち時間とエネルギー消費の両方を低減できる。
【００３５】
以上、本発明について説明してきたが、本発明をさまざまに変更することができる。そのような変更形態は本発明の精神および範囲を逸脱するものではなく、当業者が理解するその種の変更は本発明の範囲に含まれる。
【図面の簡単な説明】
【００３６】
【図１】従来技術のセンサ・ネットワークを示す図である。
【図２】本発明の方法を採用するセンサ・ネットワークが使用するスロットとフレームの構造を示す図である。
【図１】
2004336779.tif 000003
【図２】
2004336779.tif 000004