(57)【特許請求の範囲】
【請求項１】
データノードおよび少なくとも１つのシンクノードを含むノードのネットワークであって、該ネットワークは、パケットが前記シンクノードと前記データノードとの間においてマルチホップ方式で交換される無線マルチホップネットワークであって、前記データノードと前記シンクノードとの間で該パケットを中継する少なくとも１つの中間データノードを通じて該パケットを前記シンクノードと交換する少なくとも１つのデータノードが存在するような無線マルチホップネットワークであり、前記データノードは、アクティブ期間およびスリープ期間を有するバッテリー駆動式ノード（ＢＰＮ）と、アクティブ期間のみを有する商用電源式ノード（ＭＰＮ）とを含み、各データノードは、対応するアクティブ期間内でのみ前記パケットを送信し、ＢＰＮは、
データパケットを送受信する送受信機と、
該ＢＰＮのアクティブ期間およびスリープ期間のスケジュールを、該ネットワーク内の他のデータノードの前記アクティブ期間および前記スリープ期間から独立して、かつ前記シンクノードによって送信されるコマンドから独立して求めるプロセッサであって、前記送受信機を前記スケジュールに従ってオンおよびオフに切り替える、プロセッサと、
前記送受信機および前記プロセッサにエネルギーを提供するバッテリーと
を備え、
前記シンクノードは、宛先指向有向非巡回グラフ（ＤＯＤＡＧ）情報オブジェクト（ＤＩＯ）メッセージ、宛先告知オブジェクト（ＤＡＯ）メッセージ、およびＤＯＤＡＧ情報要請（ＤＩＳ）メッセージを含む制御メッセージをブロードキャストすることによってルーティングパス発見を開始し、各データノードは、データノードが前記ＢＰＮであるのかまたは前記ＭＰＮであるのかを識別する電源（ＰＳ）メトリックと、ルーティングパスに沿った前記ＢＰＮの数を記憶するバッテリー駆動式ノードカウント（ＢＮＣ）メトリックと、前記ルーティングパスに沿った前記ＢＰＮの中の最小レベルを記憶する最小バッテリーレベル（ＭＢＬ）メトリックと、前記ネットワークのＢＰＮが前記ルーティングパス上に送信された前記データパケットをオーバーヒアする回数を記憶するバッテリー駆動式オーバーヒアリングカウント（ＢＯＣ）メトリックとを含む省エネルギーメトリックを用いて前記ＤＩＯメッセージを決定および更新し、
前記ＢＰＮの前記プロセッサは、各親ノードが前記シンクノードへの対応するルーティングパスを開始する親ノードの集合を求め、
【数１】
0006359194.tif 000017
の最小値を有するデフォルトの親ノードを選択する
ネットワーク。
【請求項２】
前記ＢＰＮの前記プロセッサは、前記ＢＰＮによって検知された前記ネットワークの活動を用いた前記ＢＰＮの内部の情報に基づいて前記スケジュールを求める
請求項１に記載のネットワーク。
【請求項３】
前記ＢＰＮは、前記シンクノードに送信される前記データパケットをバッファリングするメモリをさらに備え、
前記プロセッサは、該メモリ内の前記データパケットの数に基づいて前記スケジュールを求める
請求項１に記載のネットワーク。
【請求項４】
前記ＢＰＮは、各アクティブ期間の開始時にウェイクアップ信号を送信する
請求項１に記載のネットワーク。
【請求項５】
異なるＢＰＮは、アクティブ期間およびスリープ期間の異なるスケジュールを有する
請求項１に記載のネットワーク。
【請求項６】
前記ＢＰＮの前記プロセッサは、前記ＢＰＮから前記シンクノードへのルーティングパスであって、該パス上に送信された前記データパケットを送信またはオーバーヒアする前記ＢＰＮの数を削減するルーティングパスを求め、
前記送受信機は、前記シンクノードへの対応する前記ルーティングパスを開始する親ノードに前記データパケットを送信する
請求項１に記載のネットワーク。
【請求項７】
前記ＢＰＮの前記プロセッサは、各親ノードが前記シンクノードへの対応するルーティングパスを開始するアクティブな親ノードの集合を確率的に求め、以下の式に従って求められた最小平均バッテリーエネルギー消費値ａｖｇ（Ｐ（Ｎ，Ｓ））を有するデフォルトの親ノードを前記集合から選択し、
【数２】
0006359194.tif 000018
ここで、Ｎは、ソースノードであり、Ｓは、前記シンクノードであり、ｍａｘ（Ｐ（Ｎ，Ｓ））は、ノードＮからノードＳへのルーティングパスに沿ったＢＰＮおよびＭＰＮのレイアウトの中の最大バッテリーエネルギー消費推定値であり、ｍｉｎ（Ｐ（Ｎ，Ｓ））は、前記ノードＮから前記ノードＳへの前記ルーティングパスに沿ったＢＰＮおよびＭＰＮのレイアウトの中の最小バッテリーエネルギー消費推定値である
請求項１に記載のネットワーク。
【請求項８】
前記ＢＰＮは、前記ルーティングパスに沿った前記ＢＰＮの中の最小レベルが閾値よりも大きい場合、前記ルーティングパスにわたって前記データパケットを送信する
請求項１に記載のネットワーク。
【請求項９】
前記プロセッサは、前記メモリ内のパケットの数に比例する前記ＢＰＮのアイドルリスニング時間を求める
請求項３に記載のネットワーク。
【請求項１０】
データノードおよび少なくとも１つのシンクノードを含むノードの異種無線マルチホップネットワークを形成するバッテリー駆動式ノード（ＢＰＮ）であって、前記データノードは、バッテリー駆動式ノード（ＢＰＮ）および商用電源式ノード（ＭＰＮ）を含み、該ＢＰＮは、
データパケットを送受信する送受信機と、
該ＢＰＮのアクティブ期間およびスリープ期間のスケジュールを、ネットワーク内の他のデータノードの前記アクティブ期間および前記スリープ期間から独立して、かつ前記シンクノードによって送信されるコマンドから独立して求めるプロセッサであって、前記送受信機を前記スケジュールに従ってオンおよびオフに切り替える、プロセッサと、
前記送受信機および前記プロセッサにエネルギーを提供するバッテリーと
を備え、
前記ＢＰＮは、該ＢＰＮから前記シンクノードへのルーティングパスであって、該ルーティングパス上に送信された前記データパケットを送信またはオーバーヒアする前記ＢＰＮの数を削減するルーティングパスを求め、前記送受信機は、前記シンクノードへの対応する前記ルーティングパスを開始する親ノードに前記データパケットを送信し、
前記ＢＰＮは、データノードが前記ＢＰＮであるのかまたは前記ＭＰＮであるのかを識別する電源（ＰＳ）メトリックと、ルーティングパスに沿った前記ＢＰＮの数を記憶するバッテリー駆動式ノードカウント（ＢＮＣ）メトリックと、前記ルーティングパスに沿った前記ＢＰＮの中の最小レベルを記憶する最小バッテリーレベル（ＭＢＬ）メトリックと、前記ネットワークのＢＰＮが前記ルーティングパス上に送信された前記データパケットをオーバーヒアする回数を記憶するバッテリー駆動式オーバーヒアリングカウント（ＢＯＣ）メトリックとを含む省エネルギーメトリックを用いて前記親ノードを求める
ＢＰＮ。
【請求項１１】
前記プロセッサは、前記ＢＰＮによって観測された前記ネットワークの活動を用いた前記ＢＰＮの内部の情報に基づいて前記スケジュールを求める
請求項１０に記載のＢＰＮ。
【請求項１２】
前記ＢＰＮは、前記データパケットをバッファリングするメモリをさらに備え、
前記プロセッサは、該メモリ内の前記データパケットの数に基づいて前記スケジュールを求める
請求項１０に記載のＢＰＮ。
【請求項１３】
前記ＢＰＮは、各アクティブ期間の開始時にウェイクアップ信号を送信する
請求項１０に記載のＢＰＮ。
【請求項１４】
データノードおよび少なくとも１つのシンクノードを含むノードの異種無線マルチホップネットワークを形成するバッテリー駆動式ノード（ＢＰＮ）を管理する方法であって、前記データノードは、バッテリー駆動式ノード（ＢＰＮ）および商用電源式ノード（ＭＰＮ）を含み、該方法は、
前記ＢＰＮのアクティブ期間およびスリープ期間のスケジュールを、ネットワーク内の他のデータノードの前記アクティブ期間および前記スリープ期間から独立してかつ前記シンクノードによって送信されるコマンドから独立して求めることと、
前記ＢＰＮの送受信機を前記スケジュールに従ってオンおよびオフに切り替えることと、
各アクティブ期間の開始時にウェイクアップ信号を送信することと、
前記ＢＰＮから前記シンクノードへのルーティングパスであって、該ルーティングパス上に送信されたデータパケットを送信またはオーバーヒアする前記ＢＰＮの数を削減するルーティングパスを求めることと、
前記アクティブ期間中に前記シンクノードへの対応する前記ルーティングパスを開始する親ノードに前記データパケットを送信することと
を含み、
データノードが前記ＢＰＮであるのかまたは前記ＭＰＮであるのかを識別する電源（ＰＳ）メトリックと、ルーティングパスに沿った前記ＢＰＮの数を記憶するバッテリー駆動式ノードカウント（ＢＮＣ）メトリックと、前記ルーティングパスに沿った前記ＢＰＮの中の最小レベルを記憶する最小バッテリーレベル（ＭＢＬ）メトリックと、前記ネットワークのＢＰＮが前記ルーティングパス上に送信された前記データパケットをオーバーヒアする回数を記憶するバッテリー駆動式オーバーヒアリングカウント（ＢＯＣ）メトリックとを含む省エネルギーメトリックを用いて前記親ノードを求めることをさらに含む
方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、無線ネットワークの管理に関し、特に、バッテリー駆動式ノードおよび商用電源式ノードを備える異種マルチホップ無線ネットワークの管理に関する。
【背景技術】
【０００２】
データパケットのルーティング等のエネルギー効率の良い管理は、制約された電源を有するノードを含むネットワークのための重大な問題である。ノードの電源に従って、ノードは、２つのカテゴリー、すなわち、バッテリー駆動式ノード（ＢＰＮ：battery-powered node）等の制約された電源を有するノード、および商用電源式ノード（ＭＰＮ：mains-powered node）等の制約されていない電源を有するノードに分類することができる。いくつかの用途では、バッテリー交換は、実現困難であるか、または不可能である。したがって、ＢＰＮを含む無線ネットワークにおいて、ネットワーク寿命を延ばすことが重要である。ネットワーク寿命は、通常、最初に電池残量が切れるバッテリー駆動式ノードの作動時間によって定義される。
【０００３】
ノードのリソースおよび能力に基づいて、無線ネットワークは、同種および異種に分類することができる。同種無線ネットワークでは、全てのノードは同一のリソースおよび能力を有する。全てのノードは、バッテリー駆動式または商用電源式である。無線センサーネットワークは、全てのノードが通常バッテリー駆動式である同種無線ネットワークの例である。電気スマートメーターネットワークは、全てのノードが商用電源式である同種無線ネットワークの別の例である。他方で、異種無線ネットワークでは、ノードは、異なるリソースおよび能力を有し、例えば、いくつかのノードは、バッテリー駆動式とすることができ、小さなメモリおよび限られた計算能力を有し、他のノードは、商用電源式とすることができ、より大きなメモリおよびより高い計算能力を有する。
【０００４】
バッテリー駆動式ノードを有する無線ネットワークにおいて、ルーティング等のネットワーク管理の主要な目的は、ネットワーク寿命を最大にすることである。ノードは、データ送信、データ受信、制御メッセージ送信および制御メッセージ受信のために自身のエネルギーを消費する。このカテゴリーのエネルギー消費は、必要なエネルギー使用とみなされる。ノードは、アイドルリスニング、オーバーヒアリング、衝突および再送信時にも自身のエネルギーを消費する。このカテゴリーのエネルギー消費は、エネルギーの浪費とみなされる。エネルギー節減管理のための主な目標のうちの１つは、エネルギー浪費を最小限にすることである。
【０００５】
一方、同種無線ネットワークのために設計されたエネルギー関連管理方法は、異種無線ネットワークの場合に良好に機能しない。例えば、同種ネットワークのために設計されたルーティング方法は、異種性を考慮および活用しない。さらに、いくつかの方法は、ネットワークのノードの動作を同期させることによって、同種ネットワークのエネルギー消費を低減する。例えば、ノードがあらかじめ指定された期間中にのみスリープすることができる集中型スリープ制御メカニズムを用いる方法を記載している特許文献１および特許文献２を参照されたい。一方、ネットワークの同期は、データパケットの衝突を低減することができるが、アイドル時間も増大させ、結果として、さらなるエネルギー浪費が生じる可能性がある。さらに、同期パケットの送信および受信によっても、結果として、追加のエネルギー浪費が生じる。
【０００６】
したがって、バッテリー駆動式ノードおよび商用電源式ノードを含む異種マルチホップ無線ネットワークのエネルギー効率の良い管理のシステムおよび方法を提供する必要がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第７２９８７１６号明細書
【特許文献２】米国特許第７３５６５６１号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明の様々な実施の形態の目的は、バッテリー駆動式ノード（ＢＰＮ）および商用電源式ノード（ＭＰＮ）を含む少なくとも１つのシンクノードおよびデータノードを有する異種マルチホップ無線ネットワークのエネルギー効率の良い管理のシステムおよび方法を提供することである。いくつかの実施の形態の別の目的は、少なくとも１つのデータノードが、当該データノードとシンクノードとの間でパケットを中継する少なくとも１つの中間データノードを通じて上記シンクノードとパケットを交換するマルチホップ方式でパケットを送信するエネルギー効率の良いルーティングメカニズムを提供することである。加えてまたは代替的に、本発明のいくつかの実施の形態の目的は、ノードの動作の同期を必要としないそのような異種無線ネットワークの分散型スリープ制御モデルを提供することである。
【課題を解決するための手段】
【０００９】
本発明のいくつかの実施の形態は、集中型管理が異種ネットワークよりも同種ネットワークにとって有利であるという認識に基づいている。これは、ネットワークの同期がエネルギー浪費をもたらすからである。例えば、集中型スリープ制御方法は、データパケットの送信の衝突を削減することができるが、特に、商用電源式ノードを用いるデータ送信が好ましい状況では、ノードのアイドル時間を増加させる可能性もある。
【００１０】
したがって、本発明のいくつかの実施の形態は、異種ネットワークのデータノードのスリープスケジュールを管理する分散型スリープ管理モデルを提供する。例えば、１つの実施の形態では、ＭＰＮは、アクティブ期間のみを有する。すなわち、これらのノードは、スリープ期間を有しない。これとは対照的に、ＢＰＮは、アクティブ期間およびスリープ期間の双方を有するが、アクティブ期間およびスリープ期間のスケジュールを、ネットワーク内の他のデータノードのアクティブ期間およびスリープ期間またはシンクノードによって送信されるコマンドから独立して求める。例えば、いくつかの実施の形態では、ＢＰＮのプロセッサは、ＢＰＮによって検知されたネットワークの活動を用いたＢＰＮの内部の情報に基づいてスケジュールを求める。常にアクティブなＭＰＮとエネルギー効率の良いルーティングとを組み合わせて、この分散型スリープ管理モデルは、ＢＰＮのスリープ時間を増加させる。
【００１１】
加えてまたは代替的に、いくつかの実施の形態は、特定のデータノードからシンクノードへのデータパケットのバッテリー効率の良いルーティングが、最も少ないバッテリーエネルギーを消費するルーティングパスを介するべきであるという認識に基づいている。例えば、いくつかの実施の形態は、データパケットを送信するかまたは送信されたデータパケットを受信するバッテリー駆動式ノードの数を削減するルーティングパスに沿って、データパケットを送信する。オプションとして、１つの実施の形態は、エネルギー効率の良いルーティングパスを突き止める省エネルギーメトリックを求める。この省エネルギーメトリックは、データノードがＢＰＮであるのかまたはＭＰＮであるのかを識別する電源（ＰＳ）メトリックと、ルーティングパスに沿ったＢＰＮの数を記憶するバッテリー駆動式ノードカウント（ＢＮＣ）メトリックと、ルーティングパスに沿ったＢＰＮの中の最小レベルを記憶する最小バッテリーレベル（ＭＢＬ）メトリックと、ネットワークのＢＰＮがルーティングパス上に送信されたデータパケットを受信および／またはオーバーヒアする回数を記憶するバッテリー駆動式オーバーヒアリングカウント（ＢＯＣ）メトリックとのうちの１つまたは組み合わせを含むことができる。
【００１２】
したがって、本発明の１つの実施の形態は、データノードおよび少なくとも１つのシンクノードを含むノードのネットワークであって、本ネットワークは、パケットがシンクノードとデータノードとの間においてマルチホップ方式で交換される無線マルチホップネットワークであって、データノードとシンクノードとの間でパケットを中継する少なくとも１つの中間データノードを通じてパケットをシンクノードと交換する少なくとも１つのデータノードが存在するような無線マルチホップネットワークであり、データノードは、アクティブ期間およびスリープ期間を有するバッテリー駆動式ノード（ＢＰＮ）と、アクティブ期間のみを有する商用電源式ノード（ＭＰＮ）とを含み、各データノードは、対応するアクティブ期間内でのみパケットを送信する、ネットワークを開示する。
【００１３】
ＢＰＮは、データパケットを送受信する送受信機と、ＢＰＮのアクティブ期間およびスリープ期間のスケジュールを、ネットワーク内の他のデータノードのアクティブ期間およびスリープ期間から独立してかつシンクノードによって送信されるコマンドから独立して求めるプロセッサであって、送受信機をスケジュールに従ってオンおよびオフに切り替える、プロセッサと、送受信機およびプロセッサにエネルギーを提供するバッテリーとを備える。
【００１４】
別の実施の形態は、データノードおよび少なくとも１つのシンクノードを含むノードの異種無線マルチホップネットワークを形成するバッテリー駆動式ノード（ＢＰＮ）であって、データノードは、バッテリー駆動式ノード（ＢＰＮ）および商用電源式ノード（ＭＰＮ）を含む、ＢＰＮを開示する。ＢＰＮは、データパケットを送受信する送受信機と、ＢＰＮのアクティブ期間およびスリープ期間のスケジュールを、ネットワーク内の他のデータノードのアクティブ期間およびスリープ期間から独立して、かつシンクノードによって送信されるコマンドから独立して求めるプロセッサであって、送受信機をスケジュールに従ってオンおよびオフに切り替える、プロセッサと、送受信機およびプロセッサにエネルギーを提供するバッテリーとを備える。
【００１５】
さらに別の実施の形態は、データノードおよび少なくとも１つのシンクノードを含むノードの異種無線マルチホップネットワークを形成するバッテリー駆動式ノード（ＢＰＮ）を管理する方法であって、データノードは、バッテリー駆動式ノード（ＢＰＮ）および商用電源式ノード（ＭＰＮ）を含む、方法を開示する。本方法は、ＢＰＮのアクティブ期間およびスリープ期間のスケジュールを、ネットワーク内の他のデータノードのアクティブ期間およびスリープ期間から独立して、かつシンクノードによって送信されるコマンドから独立して求めることと、ＢＰＮの送受信機をスケジュールに従ってオンおよびオフに切り替えることと、各アクティブ期間の開始時にウェイクアップ信号を送信することと、ＢＰＮからシンクノードへのルーティングパスであって、ルーティングパス上に送信されたデータパケットを送信またはオーバーヒアするＢＰＮの数を削減するルーティングパスを求めることと、アクティブ期間中にルーティングパスを開始する親ノードにデータパケットを送信することとを含む。
【図面の簡単な説明】
【００１６】
【図１Ａ】本発明のいくつかの実施の形態による異種無線ネットワークの概略図である。
【図１Ｂ】図１Ａのネットワークにおけるデータノードの構造のブロック図である。
【図２Ａ】本発明のいくつかの実施の形態によるバッテリー駆動式ノードのスリープ間隔構成の概略図である。
【図２Ｂ】本発明のいくつかの実施の形態による分散型スリープ管理モデルの概略図である。
【図３Ａ】従来のルーティングアルゴリズムが、より短いパスを選択することによってネットワーク寿命を短くする一例を示す図である。
【図３Ｂ】従来のルーティングアルゴリズムが、より高いバッテリーレベルを有するノードにデータパケットを送信することによってネットワーク寿命を短くする一例を示す図である。
【図４Ａ】本発明のいくつかの実施の形態による、ルーティングパスに沿ってバッテリー駆動式ノードをどのようにカウントするのかを示す図である。
【図４Ｂ】本発明のいくつかの実施の形態による、ルーティングパスに沿って最小バッテリーレベルをどのように測定するのかを示す図である。
【図４Ｃ】本発明のいくつかの実施の形態による、バッテリー駆動式近傍がルーティングパスに沿ったパケット送信をオーバーヒアする一例を示す図である。
【図５】本発明のいくつかの実施の形態による、分散型スリープ管理モデルを用いた無線ネットワークにおけるブロードキャストメッセージ送信を示す図である。
【図６】シンクへの次のホップノードとして商用電源式ノードを選択することがより多くのバッテリー電力を実際に消費する一例を示す図である。
【図７】本発明のいくつかの実施の形態によるルーティングパス発見のブロック図である。
【図８】分散型スリープ管理モデルを用いると、マルチホップロング遅延（multi-hop long delay）が可能であることを示す図である。
【発明を実施するための形態】
【００１７】
図１Ａは、本発明の実施の形態を用いる異種無線ネットワークの一例の概略図を示す。ネットワークは、バッテリー駆動式ノード（ＢＰＮ）１００および商用電源式ノード（ＭＰＮ）１１０等のデータノードを含む。ネットワークは、シンクノード（Ｓ）１２０も含む。ノードは、有向無線リンク１３０を用いて無線メッシュネットワークを形成し、ここで、データパケットの概略フローは、データノード（バッテリー駆動式ノードまたは商用電源式ノード）からシンクノードへのものであるが、制御メッセージは、いずれの方向にも送信することができる。
【００１８】
ネットワークは、パケットがシンクノードとデータノードとの間で、マルチホップ方式で交換される無線マルチホップネットワークであり、データノードとシンクノードとの間でパケットを中継する少なくとも１つの中間データノードを通じてシンクノードとパケットを交換する少なくとも１つのデータノードが存在するようになっている。例えば、いくつかのノード、例えば、１４０は、データパケットをシンクノードに直接送信することができる。ノードのうちのいくつか、例えば、１００および１１０は、データパケットをいずれのシンクノードにも直接送信することができない。代わりに、データパケットは、まず中間ノードまたは中継ノードに送信され、次に、中間ノードまたは中継ノードは、パケットをシンクノードに中継する。換言すれば、データ収集は、マルチホップ方式で行われる。したがって、いずれのシンクノードとも直接通信することができないノードからのデータパケットをルーティングするルーティングアルゴリズムが提供されなければならない。
【００１９】
図１Ｂは、図１Ａのネットワークを形成するデータノード１０１の構造を概略的に示す。ノードは、データパケットを送信および受信するための送受信機を備え、この送受信機は、受信機１５０および送信機１６０のうちの１つまたはこれらの組合せを備える。ノードは、当該ノードの構成要素に電力供給する電源１８０も備える。電源１８０のタイプに従って、ノードは、２つのカテゴリー分類することができる。すなわち、ＢＰＮは、バッテリー等の制約された電源を有し、ＭＰＮは、例えば、幹線またはグリッドから電力供給される無制限の電源を有する。いくつかの実施の形態では、シンクノードの電源に対する制約はなく、シンクノードは、商用電源式とすることもできるし、バッテリー駆動式とすることもできる。
【００２０】
データノード１０１は、ノードの動作を実行するための、および／または、ノードのアクティブ期間およびスリープ期間のスケジュールを決定するためのプロセッサ１７０を備える。各データノードは、対応するアクティブ期間中にのみパケットを送信する。
【００２１】
いくつかの実施の形態によれば、ＢＰＮは、アクティブ期間およびスリープ期間を有し、ＭＰＮは、アクティブ期間のみを有する。データノード１０１がＢＰＮである場合、すなわち、電源１８０がバッテリーである場合、プロセッサは、ＢＰＮのアクティブ期間およびスリープ期間のスケジュールを決定し、このスケジュールに従って送受信機をオンおよびオフに切り換える。
【００２２】
分散型スリープ管理モデル
本発明のいくつかの実施の形態は、集中型管理が、異種ネットワークではなく同種ネットワークの場合に、より有利であるという認識に基づく。これは、ネットワークの同期の結果として、エネルギーの浪費が生じることに起因する。例えば、集中型スリープ制御方法は、データパケット送信の衝突を低減することができるが、特に、商用電源式ノードを通じたデータ送信が好ましいときの状況において、ノードのアイドル時間を増大させる可能性もある。
【００２３】
本発明の様々な実施の形態において、ＢＰＮのプロセッサは、ネットワーク内の他のデータノードのアクティブ期間およびスリープ期間と独立して、かつ、シンクノードによって送信される任意のコマンドと独立して、スケジュールを決定する。例えば、ＢＰＮのプロセッサは、ＢＰＮによって観測されるネットワークのアクティビティを用いて、ＢＰＮの内部の情報に基づいてスケジュールを決定する。例えば、データノード１０１は、シンクノードに送信されるデータパケットをバッファリングするためのメモリ１９０を備える。１つの実施の形態において、プロセッサは、メモリ内のデータパケットの数に基づいてスケジュールを決定し、例えば、アクティブ期間またはスリープ期間は、メモリ内のデータパケットの数に比例する。
【００２４】
図２Ａは、本発明のいくつかの実施の形態による分散型スリープ管理モデルの概略図を示す。これらの実施の形態において、ＢＰＮ２００は、アクティブ間隔およびスリープ間隔の独自のスケジュールを管理する。時間は、異なる長さを有するスリープ間隔に分割される。間隔２０５は、アクティブ期間２１０と、それに続くスリープ期間２１５とを含む。アクティブ期間およびスリープ期間の順序は、実施の形態が異なると変動する。ＢＰＮ２００がスリープするとき、ＢＰＮ２００の送受信機は、オフにされる。ＢＰＮ２００がスリープからウェイクアップするとき、ＢＰＮ２００の送受信機は、オンにされ、ＢＰＮは、ウェイクアップメッセージ２２０を送信して、近傍データノードに、ＢＰＮ２００がアクティブであることを通知する。近傍ノードがＢＰＮ２００に送信されるデータパケットを有する場合、近傍ノードは、その送信を開始することができる。ノードは、アクティブ期間２１０およびスリープ期間２１５の長さを動的に決定し、すなわち、アクティブ期間およびスリープ期間のスケジュールは、周期的である必要がない。例えば、スリープ期間２１８は、スリープ期間２１５よりも短い。
【００２５】
図２Ｂは、本発明のいくつかの実施の形態による分散型スリープ管理モデルの概略図を示す。異なるノードはアクティブ期間およびスリープ期間の異なる長さを有することができ、ここで、バッテリー駆動式ノードＢ１２２５、Ｂ２２３０およびＢ３２３５はそれぞれ異なる長さのスリープ期間２４０、２４５および２５０を有する。
【００２６】
分散型スリープ管理モデルでは、バッテリー駆動式ノードが送信するデータを有しない場合、ノードは、周期的スリープ間隔をスケジューリングする。例えば、ノードＢ２２３０およびＢ３２３５は、送信するデータを有せず、したがって、周期的スリープスケジューリングを実行する。一方、１つの実施の形態におけるように、バッテリー駆動式ノードが別のバッテリー駆動式ノードに送信するデータを有する場合、送信側ノードは、受信側バッテリー駆動式ノードからのウェイクアップメッセージ２２０を待つ。この場合、送信側ノードは、自身のアクティブ期間を延ばす。例えば、ノードＢ１は、バッテリー駆動式ノードＢ２に送信するデータを有する。ノードＢ１は、自身のアクティブ期間２５５を拡張し、ノードＢ２からのウェイクアップメッセージを待つ。ノードＢ２からウェイクアップメッセージ２２０を受信すると、ノードＢ１は、そのデータパケット２６０をノードＢ２に送信する。ノードＢ１は、データを送信した後、スリープスケジューリングを実行する。
【００２７】
１つの実施の形態では、ＢＰＮは、２つのタイマー、すなわち、スリープタイマーおよびウェイクアップタイマーを用いて、自身のスリープスケジュールを管理する。スリープタイマーは、スリープ間隔においてノードがどれだけ長くスリープするかをスケジューリングするのに用いられ、ウェイクアップタイマーは、スリープ間隔においてノードがどれだけ長くウェイクするかをスケジューリングするのに用いられる。バッテリー駆動式ノードは、自身のアクティブ期間の長さおよびスリープ期間の長さを動的に決定する。スリープタイマーが満了すると、バッテリー駆動式ノードは、アクティブ時間値を計算し、アクティブタイマーを開始する。アクティブタイマーが満了すると、バッテリー駆動式ノードは、スリープ時間値を計算し、スリープタイマーを開始する。
【００２８】
いくつかの実施の形態では、ＢＰＮのためのスリープ期間の長さは、限定され、ネットワークについて定義される。バッテリー駆動式ノードは、自身のスリープ期間の長さを、最大の長さ以下に設定しなくてはならない。同様に、ネットワークのためにアクティブ期間の最小の長さも定義することができる。バッテリー駆動式ノードは、自身のアクティブ期間の長さを、最小の長さ以上に設定しなくてはならない。
【００２９】
分散型スリープ管理モデルでは、商用電源式ノードは、常にアクティブである。例えば、ＭＰＮ２６５は、無限のアクティブ期間２７０を有する。ノードは、データパケットを任意の時点において商用電源式ノードに送信することができる。いくつかの実施の形態では、ＭＰＮは、ウェイクアップメッセージを送信しない。したがって、いくつかの実施の形態では、ルーティングアルゴリズムはデータノードのタイプを決定する。
【００３０】
バッテリーエネルギー効率の良いルーティング
いくつかの実施の形態は、特定のデータノードからシンクノードへのデータパケットのバッテリー効率の良いルーティングが、最も少ないエネルギーを消費するルーティングパスを介するべきであるという認識に基づいている。例えば、いくつかの実施の形態は、データパケットを送信または受信するバッテリー駆動式ノードの数を削減するルーティングパスに沿ってデータパケットを送信する。
【００３１】
無線ネットワークの場合、従来のルーティングメトリックは、２つのカテゴリー、すなわち、ノード状態メトリック、例えば、ホップカウントおよびノードエネルギーレベルと、リンクメトリック、例えば、リンク品質および予想送信カウント（ＥＴＸ）とに分類することができる。これらの従来のルーティングメトリックは、２つのノード間の測定またはノード自体のステータスしか考慮していない。それらのルーティングメトリックは、ルーティングパスに沿った情報を利用していない。その結果、それらのメトリックは、スリープノードを有しない同種無線ネットワークについては良好に機能するが、スリープノードを有する無線ネットワークについては、それらのメトリックは、ネットワーク寿命を短くする可能性がある。
【００３２】
図３Ａは、Ｂ１〜Ｂ３がバッテリー駆動式ノードであり、Ｍ１〜Ｍ４が商用電源式ノードである一例を示している。シンクノードＳ３００は、パス発見メッセージ３１０をブロードキャストすることによってパス発見を開始する。ノードＮ３２０は、２つの近傍Ｂ３３３０およびＭ４３４０からパス発見メッセージを受信する。従来のルーティングメトリックを用いると、ノードＮは、Ｂ３を介するパスを選択する。なぜならば、パスＳ→Ｂ１→Ｂ２→Ｂ３はパスＳ→Ｍ１→Ｍ２→Ｍ３→Ｍ４よりも短いからである。しかしながら、パスＳ→Ｂ１→Ｂ２→Ｂ３は、全てバッテリー駆動式ノードからなる。他方、パスＳ→Ｍ１→Ｍ２→Ｍ３→Ｍ４は、全て商用電源式ノードからなる。その結果、ノードＮは、Ｍ４を介するパスを選択するべきである。より多くのバッテリー駆動式ノードを有するパスは、より多くのバッテリーエネルギーを消費し、バッテリー駆動式ノードのスリープに起因してより大きな遅延も有する。
【００３３】
図３Ｂは、１つのシンクノードＳ３００、６つのバッテリー駆動式ノードＢ４〜Ｂ９および１つのノードＮ３１０（バッテリー駆動式または商用電源式）が存在する一例を示している。ノードＮは、シンクＳへの２つのパス、すなわち、一方のパスＢ８→Ｂ６→Ｂ４→Ｓおよび他方のパスＢ９→Ｂ７→Ｂ５→Ｓを発見している。ノードＮは、シンクノードＳ３００に送信されるデータパケットを有する。ノードＮは、シンクノードＳと直接通信することができないので、ノードＮは、ノードＢ８３５０またはＢ９３６０のいずれかに自身のパケットを送信しなければならない。Ｂ８は、より高いエネルギーレベル８０％  ３７０を有するので、従来のルーティングメトリックによって、Ｎは、自身のパケットをＢ８に送信することが可能になる。一方、Ｂ８を介するパスは、バッテリーレベル１８％  ３９０を有する、より低いバッテリー駆動式ノードＢ６３８０を有する。ノードＮが、自身のパケットをＢ８を介してシンクＳに送信する場合、ノードＢ６は、バッテリー電力をより急速に使い尽くす。なぜならば、Ｂ６は、ノードＮによって送信されるパケットを中継しなければならないからである。それよりも、ノードＮは、自身のパケットをＢ９に送信するべきである。Ｂ９を介するパスは、最低バッテリーレベル４０％  ３９５を有し、これは、Ｂ６のバッテリーレベルよりもはるかに高い。しかしながら、従来のルーティングメトリックを用いると、ノードＮ３２０は、Ｂ６のバッテリーレベルを知らない。
【００３４】
したがって、１つの実施の形態は、エネルギー効率の良いルーティングパスを突き止める省エネルギーメトリックを求める。この省エネルギーメトリックは、データノードがＢＰＮであるのかまたはＭＰＮであるのかを識別する電源（ＰＳ）メトリックと、ルーティングパスに沿ったＢＰＮの数を記憶するバッテリー駆動式ノードカウント（ＢＮＣ）メトリックと、ルーティングパスに沿ったＢＰＮの中の最小レベルを記憶する最小バッテリーレベル（ＭＢＬ）メトリックと、ネットワークのＢＰＮがルーティングパス上で送信されたデータパケットをオーバーヒアする回数を記憶するバッテリー駆動式オーバーヒアリングカウント（ＢＯＣ）メトリックとのうちの１つまたは組み合わせを含むことができる。
【００３５】
パスのバッテリー駆動式ノードカウント（ＢＮＣ）は、パスに沿ったバッテリー駆動式ノードの数をカウントしたものである。ルーティングパスの発見中に、シンクノードは、当該シンクが商用電源式であるときは、ＢＮＣ＝０を設定する。そうでないとき、シンクは、ＢＮＣ＝１を設定する。バッテリー駆動式ノードは、ＢＮＣを１だけ増加させ、商用電源式ノードは、ＢＮＣの値を変更しない。
【００３６】
図４Ａは、シンクＳ３００がＢＮＣ＝０を設定し、バッテリー駆動式ノードＢ１、Ｂ２およびＢ３のそれぞれがＢＮＣを１だけ増加させ、商用電源式ノードＭ１およびＭ２がＢＮＣ値を変更しない一例を示している。ルーティングパス発見メッセージが、ノードＮ３１０（バッテリー駆動式または商用電源式）に伝播すると、Ｎは、３つのバッテリー駆動式ノードがこのパスに沿って存在することを知る。
【００３７】
パスの最小バッテリーレベル（ＭＢＬ）は、パスに沿った全てのバッテリー駆動式ノードの中の最小バッテリーレベルを測定したものである。ルーティングパスの発見中、シンクノードは、当該シンクが商用電源式であるとき、ＭＢＬ＝１００を設定する。そうでないとき、シンクノードは、ＭＢＬを自身のバッテリーレベルに設定する。バッテリー駆動式ノードは、パス発見メッセージに含まれるＭＢＬを自身のバッテリーレベルと比較する。ノードのバッテリーレベルが、受信されたＭＢＬよりも低い場合、ノードは、ＭＢＬを自身のバッテリーレベルに取り替える。そうでない場合、ノードは、ＭＢＬの値を変更しない。商用電源式ノードは、ＭＢＬの値を変更しない。
【００３８】
図４Ｂは、シンクＳ３００がＭＢＬ＝１００を設定し、バッテリー駆動式ノードＢ１がＭＢＬ＝６０に変更し、バッテリー駆動式ノードＢ２がＭＢＬ＝５０に変更し、バッテリー駆動式ノードＢ３並びに商用電源式ノードＭ１およびＭ２がＭＢＬ値を変更しない一例を示している。ルーティングパス発見メッセージが、ノードＮ３１０（バッテリー駆動式または商用電源式）に伝播すると、ノードＮは、５０％のバッテリーレベルを有する少なくとも１つのバッテリー駆動式ノードがこのパスに沿って存在することを知る。
【００３９】
パスのバッテリー駆動式オーバーヒアリングカウント（ＢＯＣ）は、バッテリー駆動式近傍が当該パスに沿ったパケット送信をオーバーヒアする総回数をカウントしたものである。バッテリー駆動式ノードがパス上の複数のノードの近傍である場合、このバッテリー駆動式ノードは、複数回カウントされる。無線ネットワークでは、送信機がパケットを受信機に送信すると、この送信元の全てのアクティブな近傍は、このパケットがこれらの近傍を宛先としていなくても、このパケットを受信する。したがって、ルーティングアルゴリズムは、オーバーヒアリングの確率を最小にしなければならない。ＢＯＣは、オーバーヒアリングに関するバッテリーエネルギー消費を削減するのに用いることができるメトリックである。ルーティングパスの発見中、各ノードは、商用電源式であるのかまたはバッテリー駆動式であるのかを示す。シンクノードは、ＢＯＣを自身のバッテリー駆動式近傍の数（ＮＢＮ）に設定する。
【００４０】
１つの実施の形態では、各ホップにおいて、パス上のノードＮ（商用電源式またはバッテリー駆動式）は、以下のようにＢＯＣを更新する。
１）ノードＮは、バッテリー駆動式である場合、ＢＯＣを１だけ減少させる。なぜならば、先行ホップノードは、ノードＮをバッテリー駆動式近傍としてカウントしなければならないからである。
２）先行ホップノードがバッテリー駆動式である場合、ノードＮは、自身のＮＢＮを１だけ減少させる。なぜならば、先行ホップノードは、ノードＮのバッテリー駆動式近傍であるからである。
３）ノードＮは、自身の更新されたＮＢＮを、更新されたＢＯＣに加算し、ＢＯＣをパス発見メッセージに含める。
【００４１】
図４Ｃは、実線４００がパケット送信を表し、破線４１０がバッテリー駆動式ノードによるパケットオーバーヒアリングを示す一例を示している。ノードＮ３１０は、パスＮ→Ｍ２→Ｂ３→Ｍ１→Ｂ２→Ｂ１→Ｓに沿ってパケットをシンクノードＳ３００（この例では商用電源式）に送信する。バッテリー駆動式ノードＢ４〜Ｂ９は、ルーティングパス上になくても、これらのノードは、アウェイクしているときにパケットを受信する。その結果、それらのノードのバッテリーは、消費される。
【００４２】
ルーティングパスの発見中、シンクノードＳは、ＢＯＣ＝２に設定する。なぜならば、ノードＳは、自身のバッテリー駆動式近傍としてＢ１およびＢ４を有するからである。Ｂ１は、パス発見メッセージを受信すると、ＢＯＣを１だけ減少させる。すなわち、ＢＯＣ＝１に設定する。Ｂ１は、３つのバッテリー駆動式近傍Ｂ２、Ｂ４およびＢ５を有する。したがって、Ｂ１は、ＢＯＣを４に更新する。Ｂ２がパス発見メッセージを受信すると、このノードは、ＢＯＣを１だけ減少させる。すなわち、ＢＯＣ＝３にする。Ｂ２は、自身のＮＢＮも１だけ減少させ、最終的に、Ｂ２は、ＢＯＣ＝ＢＯＣ＋１＝４に設定する。同様に、Ｍ１、Ｂ３およびＭ２もＢＯＣを更新する。ルーティングパス発見メッセージが、ノードＮ３１０に伝播すると、ノードＮは、ＢＯＣ＝１０に設定する。この例では、ノードＢ４、Ｂ５、Ｂ８およびＢ９は２回カウントされる。
【００４３】
スリープノードを有する異種無線ネットワークでは、ルーティングアルゴリズムは、近時の更新を反映するようにパスレベルルーティングメトリックを頻繁にリフレッシュする必要がある。
【００４４】
新たなノード状態ルーティングメトリック
従来のノード状態メトリックエネルギーレベルは、全てのノードがバッテリー駆動式である同種ネットワークについて定義されている。商用電源式ノードおよびバッテリー駆動式ノードの双方を有する異種ネットワークの場合、エネルギーレベルメトリックは、ノードが商用電源式であるのかまたはバッテリー駆動式であるのかを示していない。なぜならば、ネットワーク起動時に、全てのノードは、１００％のエネルギーレベルを有するからである。したがって、電源（ＰＳ）と呼ばれる新たなノード状態メトリックが、いくつかの実施の形態において用いられる。ノードＮの場合、ＰＳ（Ｎ）＝１は、ノードＮが商用電源式であることを示し、ＰＳ（Ｎ）＝０は、ノードＮがバッテリー駆動式であることを示す。
【００４５】
ＲＰＬの概略
低電力高損失ネットワーク（ＬＬＮ）のスケーラブルなルーティングプロトコルを設計するために、インターネットエンジニアリングタスクフォース（ＩＥＴＦ）の低電力高損失ネットワーク上のルーティング（ＲＯＬＬ）のワーキンググループ（ＷＧ）は、低電力高損失ネットワーク用ルーティングプロトコル（ＲＰＬ）をＲＦＣ６５５０として標準化している。ＲＰＬは、ＬＬＮにおけるノードを有向非巡回グラフ（ＤＡＧ）として組織化し、ＤＡＧを１つまたは複数の宛先指向ＤＡＧ（ＤＯＤＡＧ）に分割する。データシンクあたり１つのＤＯＤＡＧが存在する。
【００４６】
ＤＯＤＡＧのトポロジーおよびノードからデータシンクへのアップワードルートを構築するために、データシンクは、ＤＯＤＡＧの根としての役割を果たし、ＤＯＤＡＧ情報オブジェクト（ＤＩＯ）メッセージを近傍ノードにブロードキャストする。ＤＩＯメッセージは、ＤＯＤＡＧを構築するための情報を含む。例えば、ＤＯＤＡＧバージョンを識別するために、３つのパラメーターＲＰＬＩｎｓｔａｎｃｅＩＤ、ＤＯＤＡＧＩＤおよびＤＯＤＡＧＶｅｒｓｉｏｎＮｕｍｂｅｒが含められる。ノードの階層は、ＤＯＤＡＧの根に対して、他のノードに対するノードの個々の位置を規定する。データシンクの近傍にあるノードは、ＤＩＯメッセージを受信し、それらのノードがＤＯＤＡＧに参加することを決めたときに自身の階層を決定し、更新されたＤＩＯメッセージを近傍ノードに送信する。ノードの階層は、ＤＩＯメッセージ内に含まれる。ＤＩＯメッセージは、全てのノードがＤＯＤＡＧに参加するまで、ＤＯＤＡＧトポロジーが波面方式で構築されるように全ての方向に伝播される。ＲＰＬは、宛先告知オブジェクト（ＤＡＯ）メッセージを用いて、データシンクから他の宛先へのダウンワードルートを築く。ＤＡＯメッセージは、ノードから当該ノードの親または根に上り方向に送信される。ＤＯＤＡＧ情報要請（ＤＩＳ）メッセージを用いて、ＲＰＬノードからＤＩＯが要請される、すなわち、新たなルートが発見される。
【００４７】
信頼性のあるルーティングを達成するために、ＲＰＬは、ノードが、データパケット転送のための次のホップを求めるために、ＤＯＤＡＧ構造を用いて複数の親を有することを可能にする。親のうちの１つは、好ましい親として選択され、他の親は、バックアップ親として選択される。好ましい親は、パケット転送のためのデフォルトの次のホップとして用いられる。好ましい親が利用可能でない場合、バックアップ親を用いることができる。ＲＰＬは、ノードが階層を決定し親を選択するのを支援するための目的関数（ＯＦ）を用いる。
【００４８】
ルーティングアルゴリズムは、制御メッセージを用いてルーティングパスを発見する。例えば、ＡＯＤＶは、経路要求（ＲＥＱ）メッセージおよび経路応答（ＲＥＰ）メッセージを経路発見に用いる。ＲＰＬは、ＤＩＯメッセージを上りルーティングパス発見に用い、ＤＡＯメッセージを下りルーティングパス発見に用いる。ルーティングパス発見メッセージを伝播させることは、スリープノードからなる異種無線ネットワークでは難題である。スリープノードを有しないネットワークでは、ノードが、経路発見メッセージをブロードキャストし、全ての近傍が、このブロードキャストされたメッセージを受信する。一方、分散されたスリープノードを有するネットワークでは、いくつかの近傍がスリープし、いくつかの近傍がアウェイクしている。スリープした近傍は、いずれもメッセージも受信することができない。
【００４９】
集中型スリープ制御を用いると、制御ノードは、ノードがスリープしている時およびノードがアクティブである時を判断する。一方、分散型スリープモデルを用いると、そのようなスケジューリングされたスリープ情報およびアクティブ情報は、入手可能でない。入手可能な唯一の情報は、スリープノードがウェイクアップしたときにウェイクアップメッセージを送信するということだけである。ユニキャストパケットの場合、送信元は、受信機からウェイクアップメッセージを受信するまで待機することができる。しかし、ブロードキャストメッセージおよびマルチキャストメッセージは、異なる。これらのメッセージは複数の受信機を宛先とする。ＲＰＬにおけるＤＩＯ等のルーティングパス発見メッセージのほとんどは、ブロードキャストメッセージである。ネットワーク接続を得るには、あらゆるノードが、そのようなブロードキャストメッセージを受信しなければならない。受信しない場合、そのノードは、ネットワークから隔離される。したがって、重要なブロードキャストメッセージについて、送信元は、メッセージを全ての近傍に配信することを保証しなければならない。
【００５０】
分散型スリープ管理モデルを用いてブロードキャストメッセージを全ての近傍に配信する１つの方法は、ブロードキャストメッセージを以下のＲＴＸ回送信することである。
【００５１】
【数１】
0006359194.tif 000002
【００５２】
これらのＲＴＸ回の送信は、ブロードキャスト間隔と呼ばれる時間期間にわたって均等に分散される。ブロードキャスト間隔の長さは、ＭｉｎＡｃｔｉｖｅＰｅｒｉｏｄＬｅｎｇｔｈ＋ＭａｘＳｌｅｅｐＰｅｒｉｏｄＬｅｎｇｔｈである。これらの送信の間、送信ノードは、各再送信後にスリープする場合があり、次の再送信のためにウェイクアップする。送信ノードは、ウェイクアップしても、ウェイクアップメッセージを送信しない場合がある。ＲＴＸ回の再送信を用いると、あらゆる近傍は、ブロードキャストメッセージの少なくとも１つのコピーを受信することが保証される。複製検出のために、送信ノードは、シーケンス番号をブロードキャストメッセージに含め、ＲＴＸ回の全ての再送信は、ブロードキャストメッセージが複製されたものであるか否かを受信ノードが判断することができるように同じシーケンス番号を有する。このブロードキャストメッセージ送信方法は、ＲＴＸが相対的に小さくなるようにＭｉｎＡｃｔｉｖｅＰｅｒｉｏｄＬｅｎｇｔｈが相対的に大きいときにより効率的である。図５は、ノードＮ５００（商用電源式またはバッテリー駆動式）がＤＩＯ送信ノードであり、ノードＢ１５１０およびＢ２５２０がノードＮの２つのバッテリー駆動式近傍である一例を示している。ノードＢ１は、ノードＢ２のスリープ期間５５０よりも長いスリープ期間５４０を有する。この例では、ＭａｘＳｌｅｅｐＰｅｒｉｏｄＬｅｎｇｔｈ＝２＊ＭｉｎＡｃｔｉｖｅＰｅｒｉｏｄＬｅｎｇｔｈであり、したがって、ＲＴＸ＝４である。４つのＤＩＯ送信５６０は、ブロードキャスト間隔５７０にわたって均等に分散される。ノードＢ１は、ＤＩＯメッセージの２つのコピーを受信し、ノードＢ２は、ＤＩＯメッセージの１つのコピーを受信する。
【００５３】
分散型スリープ管理モデルを用いてブロードキャストメッセージを全ての近傍に配信する別の方法は、送信ノードがブロードキャスト間隔の間、アウェイクの状態にあることである。ブロードキャスト間隔の開始時に、送信ノードは、ブロードキャストメッセージを１回送信し、全ての商用電源式近傍がブロードキャストメッセージを受信することを確認する。ブロードキャスト間隔の間、送信ノードは、ウェイクアップメッセージをバッテリー駆動式近傍から受信するごとに１回、ブロードキャストメッセージを送信する。この方法を用いると、送信ノードは、ブロードキャストメッセージをＮＢＮ＋１回送信する。同様に、複製検出のために、送信ノードは、シーケンス番号をブロードキャストメッセージに含め、全ての再送信は同じシーケンス番号を有する。このブロードキャストメッセージ送信方法は、送信ノードが有するバッテリー駆動式近傍がより少ない場合には、より効率的である。
【００５４】
ルーティングアルゴリズムは、ＲＴＸとＮＢＮとを比較することによって異なるノードにいずれかの方法を適応的に用いることができる。ＲＴＸは、ネットワーク内の全てのノードについて同じであるが、ＮＢＮは、ノードに依存する。なぜならば、異なるノードは、異なる数のバッテリー駆動式近傍を有する場合があるからである。商用電源式近傍は、同じブロードキャストメッセージのＲＴＸ個またはＮＢＮ＋１個のコピーを受信する。
【００５５】
スリープノードを有する異種ネットワークにおけるルーティングパス発見
商用電源式およびバッテリー駆動式の双方を有する異種無線ネットワークでは、商用電源式ノードを次のホップノードとして選択することが、常にエネルギー効率が良いとは限らない。図６は、シンクノードがＳ６００である一例である。バッテリー駆動式ノードＢ５６１０は、商用電源式ノードＭ１６２０を次のホップノードとして選択する。なぜならば、Ｍ１は、商用電源式ノードであるからである。選択されたパスＢ５→Ｍ１→Ｂ６→Ｂ２→Ｓは、２つのバッテリー駆動式ノードＢ２６３０およびＢ６６４０がパス上に存在するので、より多くのバッテリー電力を実際に消費する。それよりも、Ｂ５は、Ｂ２がバッテリー駆動式ノードであっても、Ｂ２を自身の次のホップノードとして選択するべきである。パスＢ５→Ｂ２→Ｓは、パスＢ５→Ｍ１→Ｂ６→Ｂ２→Ｓよりもエネルギー効率が良い。
【００５６】
既存のルーティングアルゴリズムは、商用電源式ノードおよびバッテリー駆動式ノードの双方を有する異種ネットワーク、特に、分散型スリープ管理モデル用に設計されていない。新たなルーティング機能を提供しなければならない。
【００５７】
ＲＰＬを例にとると、ＲＰＬは、スリープノードをサポートしていない。スリープノードをサポートするには、ＲＰＬによって規定された従来のルーティングメトリックのほかに、新たなメトリックＢＮＣ、ＭＢＬ、ＢＯＣおよびＰＳをＤＩＯメッセージで搬送しなればならない。これらのメトリックを用いると、親の選択およびランクの計算の基準として、多くの方法を用いることができる。エネルギー効率の良い方法は、以下の段落において提供される。ＲＰＬは、ＤＩＯメッセージ伝播を用いて、上りルーティングパスを発見する。ＤＩＯメッセージは、シンクノードによって発信される。ＤＩＯ伝播中、各ノードは、１つのデフォルトの親、および複数のバックアップの親が利用可能である場合には、これらのバックアップの親を選択する。
【００５８】
図７は、新たに導入されたバッテリー電力効率の良いルーティングメトリックをサポートする提供されたルーティングパス発見方法を有するＲＰＬを示している。ノードは、ＤＩＯメッセージを受信すると（７００）、このＤＩＯが新たなＤＯＤＡＧ用であるのかまたは既存のＤＯＤＡＧ用であるのかを調べる（７０５）。ＤＩＯが新たなＤＯＤＡＧ用である場合、ノードは、このＤＯＤＡＧに加わっているか否かを判定する（７１０）。ノードが新たなＤＯＤＡＧに加わっていない場合、ＤＩＯメッセージは、廃棄される（７１５）。ノードがＤＯＤＡＧに加わっている場合、ＤＩＯは、処理される（７２０）。ＢＮＣが０に等しい場合（７２５）、ノードは、ＤＩＯ送信元を自身のデフォルトの親として設定して自身のランクを計算し（７３０）、ＤＡＯ送信をスケジューリングし（７３５）、上記で提供したブロードキャストメッセージ送信方法のうちの１つを用いることによって、ＤＩＯの送信を開始する（７４０）。ＢＮＣが０でない場合、ノードは、ＤＩＯ送信元を親として選択する（７４５）が、ランクを計算しない。その代わりに、ノードは、より好ましいＤＩＯを待機するタイマーを始動する（７５０）。ＤＩＯが既存のＤＯＤＡＧ用である場合、ノードは、親を既に選択している。そのため、ノードは、ランクが計算されているか否かを調べる（７５５）。ｙｅｓである場合、ノードは、自身のランクがＤＩＯメッセージに含まれるランクよりも大きいか否かを調べる（７５８）。ｎｏである場合、ＤＩＯは、廃棄される（７１５）。ｙｅｓである場合、ノードは、十分な親が選択されているか否かを調べ（７６０）、ｎｏである場合、ノードは、ＤＩＯ送信元を自身の親集合に加え（７６５）、ｙｅｓである場合、このＤＩＯがより優れたルーティングパスを含むときは、ノードは、親のうちの１つを取り替えることによって自身の親集合を更新する（７７０）。ランクが計算されておらず、このＤＩＯがＢＮＣ＝０を有する場合（７７５）、ノードは、ＤＩＯ送信元をデフォルトの親として設定し（７８０）、ＤＩＯ待機タイマーをキャンセルし（７８５）、ランクを計算し、十分な親が選択されているときは、既存の親のうちの１つを取り替えることによって親集合を更新し（７９０）、ＤＡＯ送信をスケジューリングし（７３５）、ＤＩＯのブロードキャストを開始する（７４０）。ＤＩＯがＢＮＣ＞０を有する場合、ノードは、十分な親が選択されていないときは、ＤＩＯ送信元を自身の親集合に加え（７６５）、そうではなく十分な親が選択されているときは、当該ノードの親集合を更新する（７７０）。タイマーが満了すると（７９５）、ノードは、親集合から１つの親をデフォルトの親として選択して、ランクを計算し（７９８）、ＤＡＯ送信をスケジューリングし（７３５）、ＤＩＯメッセージ送信を開始する（７４０）。
【００５９】
親集合を更新するには、１つのパスが別のパスよりも優れていると判断する基準を定義する必要がある。１つのパスがこの他のパスよりも優れていることを定義する方法には、種々の方法がある。より小さなＢＮＣを有するパスは、他のメトリックが同様である場合には、大きなＢＮＣを有するパスよりも優れているとみなされる。より大きなＭＢＬを有するパスは、他のメトリックが同様である場合には、より小さなＭＢＬを有するパスよりも優れているとみなされる。より小さなＢＯＣを有するパスは、他のメトリックが同様である場合には、大きなＢＯＣを有するパスよりも優れているとみなされる。最初のホップノードが商用電源式であるパスは、他のメトリックが同様である場合には、最初のホップノードがバッテリー駆動式であるパスよりも優れているとみなされる。
【００６０】
開示された発明は、より優れたパスを求める方法を提供する。各親候補Ｐについて、ノードは、以下のように親適格値Ｑ（Ｐ）を計算する。
【００６１】
【数２】
0006359194.tif 000003
【００６２】
より小さなＱ（Ｐ）値は、より優れたパスを示す。ノードは、式（２）を用いて、自身の親集合を更新する。ＤＩＯタイマーが満了すると、ノードは、最も小さなＱ（Ｐ）値を有する親をデフォルトの親として選択する。互角の場合、ノードは、ＰＳを用いて、この互角を解消する。ＰＳが互角を解消することができない場合、ＲＰＬによって定義された従来のルーティングメトリックが、互角を解消するのに用いられる。
【００６３】
従来のルーティングメトリックおよび新たなルーティングメトリックを用いると、ノードのランクを計算する多くの方法がある。以下は、４つの新たなメトリックを従来のランク計算に組み込んだランク計算方法である。
【００６４】
【数３】
0006359194.tif 000004
【００６５】
ここで、ＲＤは、デフォルトの親（ＤＰ）のランクであり、ＲＩは、従来のＲＰＬルーティングメトリックおよび目的関数を用いることによって計算されたランク増加量であり、ＣＢＮＣ、ＣＭＢＬ、ＣＢＯＣ、およびＣＰＳは、それぞれＢＮＣ、ＭＢＬ、ＢＯＣ、およびＰＳの重要度を反映する係数である。ノードがより優れたデフォルトパスを発見する場合、これらの係数は、ノードがより小さなランクを有するように選択されるべきである。そうでない場合、ノードは、より大きなランクを有する。
【００６６】
提供された親選択方法を用いて、ノードは複数の親を選択する。換言すれば、ノードは、シンクノードに向かう複数のルーティングパスを発見する。ノードは、発見された最も優れたルーティングパスを自身のＤＩＯメッセージで告知する。例えば、ノードがシンクノードへの２つのルーティングパス、すなわち、ＢＮＣ＝０を有する一方のパスおよびＢＮＣ＝２を有する他方のパスを発見した場合、このノードは、ＢＮＣ＝０を有するパスを告知する。
【００６７】
例として、ＲＰＬは、バッテリー電力効率の良いルーティングパスを発見するのに用いられているが、提供された方法は、任意のルーティングアルゴリズムに適用することができる。
【００６８】
アイドルリスニング時間削減
図８は、バッテリー駆動式ノードＢ０、Ｂ１、Ｂ２、・・・、ＢＮが同じアクティブ期間長およびスリープ期間長を用いる一例を示している。ノードＢ１は、ノードＢ０に送信されるデータパケットを有するが、Ｂ１は、Ｂ０からの最初のウェイクアップメッセージ８００を見逃したばかりであり、Ｂ１は、ノードＢ０からの次のウェイクアップメッセージ８１０を待機し、パケット８２０をＢ０に送信する。同様に、ノードＢ２は、ノードＢ１に送信されるデータパケットを有するが、Ｂ２は、Ｂ１からの最初のウェイクアップメッセージ８００を見逃したばかりであり、そのため、ノードＢ２は、Ｂ１からの次のウェイクアップメッセージ８１０を待機し、パケット８２０をＢ１に送信する。他のノードについても同様である。このシーケンスでは、Ｂ１の待機時間≒ＡｃｔｉｖｅＰｅｒｉｏｄＬｅｎｇｔｈ（アクティブ期間長）＋ＳｌｅｅｐＰｅｒｉｏｄＬｅｎｇｔｈ（スリープ期間長）、Ｂ１の待機時間≒ＡｃｔｉｖｅＰｅｒｉｏｄＬｅｎｇｔｈ＋２＊ＳｌｅｅｐＰｅｒｉｏｄＬｅｎｇｔｈ、・・・、ＢＮの待機時間≒ＡｃｔｉｖｅＰｅｒｉｏｄＬｅｎｇｔｈ＋Ｎ＊ＳｌｅｅｐＰｅｒｉｏｄＬｅｎｇｔｈである。アクティブ期間長が１０秒であり、スリープ期間長が９０秒である場合、ノードＢ５は、約４６０秒間待機する。
【００６９】
本発明のいくつかの実施の形態では、ルーティングアルゴリズムは、ＢＰＮのアクティブ期間およびスリープ期間のスケジュールを管理して、より多くのエネルギー消費をもたらすアイドルリスニング時間も削減する。分散型スリープモデルにおいてアイドルリスニング時間を削減するために、いくつかの実施の形態では、送信ノードは、受信機ノードからのウェイクアップメッセージが受信されるまで待機することを要しない。異なる実施の形態は、異なる方法のうちの１つまたは組み合わせを用いて、アイドルリスニング時間を削減する。
【００７０】
例えば、バッファー内のパケットの数は、アイドルリスニングを削減するのに用いることができる１つのパラメーターである。送信されるパケットがバッファーにより多く存在する場合、送信ノードは、より長い時間、待機する可能性がある。そうでない場合、送信ノードは、より短い時間を待機し、ウェイクアップが受信されない場合、送信ノードはスリープする。したがって、アイドルリスニング時間は、バッファー内のパケットの数に比例するように設定することができる。
【００７１】
オーバーヒアリングは、アイドルリスニング時間を削減する別の方法である。無線媒体は、共有媒体である。受信ノードからオーバーヒアされたいずれの送信も、受信ノードがアウェイクしていることを示し、したがって、送信ノードは、パケットを受信ノードに送信することができる。例えば、ＲＰＬプロトコルによれば、ＲＰＬノードは、トリクル（trickle）タイマーアルゴリズムに基づいてＤＩＯを送信する。これは、擬似周期送信である。送信ノードが、受信ノードからのＤＩＯメッセージをオーバーヒアした場合、受信ノードはアウェイクしている。また、ネットワーク内のノードは、自身のデータをシンクにも送信する必要がある。
【００７２】
アクティブ通知は、アイドルリスニング時間を削減する別の方法である。送信ノードが、自身の受信機からのウェイクアップメッセージを待機している間、この送信ノードからのウェイクアップメッセージを待機している他のノードが存在する場合がある。したがって、送信ノードは、しばらくの間待機している場合に、アクティブ通知信号を動的に送信して、自身がアウェイクしていることを自身の近傍に知らせることができ、それによって、それらの近傍が、この送信ノードに送信することできるパケットを有する場合に、それらのパケットをこの送信ノードに送信することができるようにする。
【００７３】
バッテリーレベルも、アイドルリスニング時間管理において考慮する必要がある。バッテリーレベル閾値ＢＬＴＨが定義される。バッテリーノードのバッテリーレベルがＢＬＴＨよりも低い場合、このバッテリーノードは、危機状態にある。したがって、このバッテリーノードは、自身のアクティブ期間を最小アクティブ期間に設定するべきであり、自身のスリープ期間を最大スリープ期間に設定する。一方、バッテリー駆動式ノードが、自身が収集したＭＢＬよりもはるかに高いバッテリーレベルを有する場合、このバッテリー駆動式ノードは、アイドルリスニング時間をより長く設定することができる。
【００７４】
バッテリーエネルギー効率の良いデータパケット送信
スリープノードがある場合、データパケットの送信は、スリープノードがある場合と異なる。スリープノードがない場合には、受信機は、常にアウェイクしており、送信ノードは、パケットを受信機に任意の時間において送信することができる。スリープノードがある場合、送信機は、パケットを送信するために、受信機がアウェイクしていることを確認しなければならない。従来の集中型スリープ制御を用いると、送信機および受信機は、同時にスリープおよびウェイクアップするようにスケジューリングされる。すなわち、送信機がアウェイクしている場合、受信機はアウェイクしていなければならない。したがって、送信機は、受信機がアウェイクしている限り、パケットを受信機に送信することができる。一方、分散型スリープモデルを用いると、送信機および受信機は、独立してスリープおよびウェイクアップする。すなわち、送信機がアウェイクしているとき、受信機は、アスリープしている場合がある。したがって、ルーティングアルゴリズムは、パケット損失を回避するとともにバッテリー電力を節約するために、データパケット送信を効率的に管理しなければならない。
【００７５】
従来のＲＰＬでは、ノードは、データパケットを自身のデフォルトの親に常に送信する。一方、分散型スリープモデルと用いると、ノードは、パケットを自身のデフォルトの親に常に送信することができるとは限らない。なぜならば、デフォルトの親は、アスリープしている場合があるからである。ノードは、自身のデフォルトの親がウェイクアップするのを待機することができるが、待機は、エネルギーを消費し、データ遅延も増大させる。効率的な方法は、ノードが、アウェイクしている任意の親にデータパケットを送信することができることである。親がアウェイクしていない場合、ノードは、上記で説明したスリープ管理方法を用いることによってスリープまたは待機することができる。
【００７６】
バッテリー電力を効率良くするために、送信ノードは、複数の親がアウェイクしている場合に、いずれの親にパケットを送信するべきであるかを決定しなければならない。好ましい親を決定するために、各アクティブな親を介するパスに沿ったバッテリーエネルギー消費を推定しなければならない。送信ノードは、その後、最も少ないバッテリーエネルギーを消費するアクティブな親を介するパスを選択する。ルーティングパスに沿ったバッテリー電力消費の推定は、以下の段落において説明される。
【００７７】
分散型スリープ管理モデルを用いると、バッテリー駆動式ノードＢがアウェイクしている確率は、以下の式となる。
【００７８】
【数４】
0006359194.tif 000005
【００７９】
データパケットを送信するための電力消費および受信するための電力消費が、それぞれＰｔおよびＰｒであり、ウェイクアップメッセージを送信するための電力消費および受信するための電力消費は、それぞれＷｔおよびＷｒであると仮定する。バッテリー駆動式ノードＢについて、Ｐｉ（Ｂ）は、パケット送信前にバッテリー駆動式受信ノードからのウェイクアップメッセージを待機するアイドルリスニングに関するバッテリー電力消費を示す。
【００８０】
送信ノードがデータパケットをシンクノードに配信するパスに沿ったバッテリー電力消費を推定するための３つのステップがある。
【００８１】
ステップ１：あるノードから別のノードにパケットを送信することによって消費されるバッテリー電力を計算する
ａ）バッテリー駆動式ノードＢｔからバッテリー駆動式ノードＢｒにパケットを送信することによって消費されるバッテリー電力は、以下の式となる。
【００８２】
【数５】
0006359194.tif 000006
【００８３】
ここで、Ｎｒは、ノードＢｔを含まないノードＢｒのバッテリー近傍の総数であり、ＢＢｒｋ（ｋ＝１〜Ｎｒ）は、ノードＢｔを含まないノードＢｒのバッテリー近傍であり、Ｎｔは、ノードＢｒを含まないノードＢｔのバッテリー近傍の総数であり、ＢＢｔｊ（ｊ＝１〜Ｎｔ）は、ノードＢｒを含まないノードＢｔのバッテリー近傍である。
ｂ）商用電源式ノードＭｔからバッテリー駆動式ノードＢｒにパケットを送信することによって消費されるバッテリー電力は、以下の式となる。
【００８４】
【数６】
0006359194.tif 000007
【００８５】
ここで、Ｎｒは、ノードＢｒのバッテリー近傍の総数であり、ＢＢｒｋ（ｋ＝１〜Ｎｒ）は、ノードＢｒのバッテリー近傍であり、Ｎｔは、ノードＢｒを含まないノードＭｔのバッテリー近傍の総数であり、ＢＭｔｊ（ｊ＝１〜Ｎｔ）は、ノードＢｒを含まないノードＭｔのバッテリー近傍である。
ｃ）バッテリー駆動式ノードＢｔから商用電源式ノードＭｒにパケットを送信することによって消費されるバッテリー電力は、以下の式となる。
【００８６】
【数７】
0006359194.tif 000008
【００８７】
ここで、Ｎｔは、ノードＢｔのバッテリー近傍の総数であり、ＢＢｔｊ（ｊ＝１〜Ｎｔ）は、ノードＢｔのバッテリー近傍である。
ｄ）商用電源式ノードＭｔから商用電源式ノードＭｒにパケットを送信することによって消費されるバッテリー電力は、以下の式となる。
【００８８】
【数８】
0006359194.tif 000009
【００８９】
ここで、Ｎｔは、ノードＭｔのバッテリー近傍の総数であり、ＢＭｔｊ（ｊ＝１〜Ｎｔ）は、ノードＭｔのバッテリー近傍である。
【００９０】
ステップ２：ソースノードからシンクノードにパケットを送信することによって消費されるバッテリー電力を計算する。
【００９１】
ソースノードＮ（商用電源式またはバッテリー駆動式）からシンクノードＳ（商用電源式またはバッテリー駆動式）へのパスに沿って、バッテリー駆動式ノードからバッテリー駆動式ノードへのＢ２Ｂ送信と、商用電源式ノードからバッテリー駆動式ノードへのＭ２Ｂ送信と、バッテリー駆動式ノードから商用電源式ノードへのＢ２Ｍ送信と、商用電源式ノードから商用電源式ノードへのＭ２Ｍ送信とがあると仮定する。式（５）〜（８）を用いると、ソースノードＮからシンクノードＳにパケットを送信することによって消費されるバッテリー電力は、以下の式によって与えられる。
【００９２】
【数９】
0006359194.tif 000010
【００９３】
ステップ３：パスに沿ってＰ（Ｎ，Ｓ）の最大値および最小値を計算する。
【００９４】
ソースノードＮからシンクノードＳへの特定のルーティングパスについて、バッテリー駆動式ノードの数および商用電源式ノードの数が固定されていても、これらのノードのレイアウトは、バッテリーエネルギー消費に影響を与える。ソースノードＮおよびシンクノードＳを含めて、ＮＢ個のバッテリー駆動式ノードＢ１、Ｂ２、・・・、ＢＮＢと、ＮＭ個の商用電源式ノードＭ１、Ｍ２、・・・、ＭＮＭとがパス上に存在すると仮定する。最大バッテリーエネルギー消費は、全ての商用電源式ノードがパスの先頭部分にあり、その後に全てのバッテリー駆動式ノードが続いているとき、すなわち、Ｍ１→Ｍ２→・・・→ＭＮＭ→Ｂ１→Ｂ２→・・・→ＢＮＢであるときに起こる。したがって、以下の式となる。
【００９５】
【数１０】
0006359194.tif 000011
【００９６】
最小バッテリーエネルギー消費は、バッテリー駆動式ノードおよび商用電源式ノードが交互に配置されているときに起こる。ＮＭ≧ＮＢである場合、最小バッテリー電力消費レイアウトは、Ｂ１→Ｍ１→Ｂ２→Ｍ２→・・・→ＢＮＢ→ＭＮＢ→ＭＮＢ＋１→・・・→ＭＮＭであり、ＮＭ＜ＮＢである場合、最小バッテリー電力消費レイアウトは、Ｂ１→Ｍ１→Ｂ２→Ｍ２→・・・→ＢＮＭ→ＭＮＭ→ＢＮＭ＋１→・・・→ＢＮＢである。したがって、ＮＭ≧ＮＢである場合、以下の式となる。
【００９７】
【数１１】
0006359194.tif 000012
【００９８】
また、ＮＭ＜ＮＢである場合、以下の式となる。
【００９９】
【数１２】
0006359194.tif 000013
【０１００】
最大バッテリーエネルギー消費および最小バッテリーエネルギー消費が計算されると、ソースノードＮからシンクノードＳへのルーティングパスの平均バッテリー電力消費が、以下の式によって与えられる。
【０１０１】
【数１３】
0006359194.tif 000014
【０１０２】
したがって、複数のアクティブな親が存在する場合、送信ノードは、自身のデータパケットを親に最小ａｖｇ（Ｐ（Ｎ，Ｓ））で転送する。一方、ルーティングパスのＭＢＬがＢＬＴＨに達している場合、そのパスは、選択肢がない場合を除いて用いられない。
【０１０３】
ノードＮがパスに沿ったａｖｇ（Ｐ（Ｎ，Ｓ））を実際に計算するには、ノードＮは、パス上の各ノードのバッテリー駆動式近傍の数およびパス上の商用電源式ノードの数、並びに各バッテリー駆動式近傍がアウェイクしている確率を知る必要がある。
【０１０４】
ホップカウントは、以下のように、パスに沿った商用電源式ノード（ＮＭＮ）の数を計算するのに用いられる。
【０１０５】
【数１４】
0006359194.tif 000015
【０１０６】
したがって、パス上のノードの総数は、ＮＭＮ＋ＢＮＣである。平均すると、パス上の各ノードは、
【数１５】
0006359194.tif 000016
個のバッテリー駆動式オーバーヒアリング近傍を有する。
【０１０７】
バッテリー駆動式近傍がアウェイクしている確率を推定するのに、通常のアクティブ期間長および通常のスリープ期間長を用いることができる。
【０１０８】
本発明の上記の実施の形態は、数多くの方法のいずれかにおいて実現することができる。例えば、それらの実施の形態は、ハードウェア、ソフトウェアまたはその組み合わせを用いて実現することができる。ソフトウェアにおいて実現されるとき、そのソフトウェアコードは、単一のコンピューター内に設けられるにしても、複数のコンピューター間に分散されるにしても、任意の適切なプロセッサ、またはプロセッサの集合体において実行することができる。そのようなプロセッサは集積回路として実現することができ、集積回路コンポーネント内に１つまたは複数のプロセッサが含まれる。しかしながら、プロセッサは、任意の適切な構成の回路を用いて実現することができる。そのプロセッサは、当該技術分野において既知であるように、メモリ、送受信機および入出力インターフェースに接続することができる。
【図１Ａ】
0006359194.tif 000019
【図１Ｂ】
0006359194.tif 000020
【図２Ａ】
0006359194.tif 000021
【図２Ｂ】
0006359194.tif 000022
【図３Ａ】
0006359194.tif 000023
【図３Ｂ】
0006359194.tif 000024
【図４Ａ】
0006359194.tif 000025
【図４Ｂ】
0006359194.tif 000026
【図４Ｃ】
0006359194.tif 000027
【図５】
0006359194.tif 000028
【図６】
0006359194.tif 000029
【図７】
0006359194.tif 000030
【図８】
0006359194.tif 000031