(57)【特許請求の範囲】
【請求項１】
非同期ワイヤレス通信ネットワークのルーティングノード（Ｒ３）の動作を設定するための方法であって、前記ルーティングノード（Ｒ３）は、間欠的動作を有する無線トランシーバを含み、前記間欠的動作は、アウェイク・インターバル（Ｒｌ）及びスリープ・インターバル（Ｒｓ）の周期的シーケンスに対応し、前記ネットワークは、複数のクラスタ（ＣＬ１、ＣＬ２、．．．）を含み、前記クラスタ（ＣＬ１、ＣＬ２、．．．）のそれぞれは、１つのクラスタヘッドノード（Ｒ３、Ｒ４、．．．）を有し、クラスタヘッドノードは、前記クラスタの他のノードから送信されたデータパケットを受信するルーティングノードであり、クラスタ内での送信が試行されたときにビジーチャネル確率（ｃ）に出くわし、クラスタ内での送信が実行されたときに通信衝突確率（ｐ）に出くわし、データパケットは、伝送成功確率（ψ）及び伝送の平均遅延（τ）と共にクラスタ内で伝送され、前記方法は、
Ａ）前記ルーティングノード（Ｒ３）が前記クラスタヘッドノードである前記クラスタ（ＣＬ１）について、前記ビジーチャネル確率（ｃ）、前記通信衝突確率（ｐ）、前記ルーティングノード（Ｒ３）の前記アウェイク・インターバルの継続時間（Ｒｌ）及び前記スリープ・インターバルの継続時間（Ｒｓ）の関数としてのエネルギー消費を求めるステップと、
Ｂ）前記ルーティングノード（Ｒ３）が前記クラスタヘッドノードである前記クラスタ（ＣＬ１）について、前記ビジーチャネル確率（ｃ）及び通信衝突の前記確率（ｐ）の所定の値のもと、且つ、前記伝送成功確率（ψ）及び伝送の前記平均遅延（τ）に対する所定の制限もとで、前記エネルギー消費を設定された閾値未満に低減する前記ルーティングノード（Ｒ３）の前記アウェイク・インターバルの継続時間（Ｒｌ）及び前記スリープ・インターバルの継続時間（Ｒｓ）の値を求めるステップと、
Ｃ）前記ルーティングノード（Ｒ３）の前記アウェイク・インターバルの継続時間（Ｒｌ）及び前記スリープ・インターバルの継続時間（Ｒｓ）を、ステップＢで求めた前記値の中から選択された値に設定するステップと
を含む方法。
【請求項２】
前記ネットワークを複数のクラスタ（ＣＬ１、ＣＬ２、．．．）に分割し、それにより前記クラスタ（ＣＬ１、ＣＬ２、．．．）のそれぞれが１つのクラスタヘッドノード（Ｒ３、Ｒ４、．．．）を含むようにするステップを更に含む、請求項１に記載の方法。
【請求項３】
前記ルーティングノード（Ｒ３）が前記クラスタヘッドノードである前記クラスタ（ＣＬ１）は、（Ｎ）個のノードを含み、前記クラスタ（ＣＬ１）の前記ノードは、平均データパケット生成率（λ）に従ってデータパケットを送信し、ステップＡにおいて、エネルギー消費は、ノードの前記数（Ｎ）及び前記平均データパケット生成率（λ）の関数としても求められる、請求項１に記載の方法。
【請求項４】
前記ルーティングノード（Ｒ３）は、前記ビジーチャネル確率（ｃ）を繰り返し求め、ステップＢを繰り返し実行するためにそのように求めた確率を使用する、請求項１に記載の方法。
【請求項５】
前記ルーティングノード（Ｒ３）は、前記クラスタ（ＣＬ１）のその他のノード（Ｒ２、Ｅ４、Ｅ５、Ｒ４）によって作成される前記ビジーチャネル確率の推定値を受信し、受信した前記推定値の平均又は最大を計算することによって、前記ビジーチャネル確率（ｃ）を求める、請求項４に記載の方法。
【請求項６】
前記ルーティングノード（Ｒ３）は、推定値を作成することによって前記通信衝突確率（ｐ）を繰り返し求め、ステップＢを繰り返し実行するためにそのように求めた確率を使用する、請求項１に記載の方法。
【請求項７】
ステップＢの求めることは、前記ルーティングノード（Ｒ３）によって、内部に格納された値のテーブル（ＴＢＬ）に基づいて実行される、請求項１に記載の方法。
【請求項８】
前記テーブル（ＴＢＬ）は、ノードの前記数（Ｎ）、前記平均データパケット生成率（λ）、前記ビジーチャネル確率（ｃ）、前記通信衝突確率（ｐ）、前記伝送成功確率（ψ）及び伝送の前記平均遅延（τ）の異なる値について、前記アウェイク・インターバルの継続時間（Ｒｌ）及び前記スリープ・インターバルの継続時間（Ｒｓ）の値の複数の組を含む、請求項３及び７に記載の方法。
【請求項９】
間欠的動作を有する無線トランシーバを含む非同期ワイヤレス通信ネットワークのノードであって、前記間欠的動作は、アウェイク・インターバル及びスリープ・インターバルの周期的シーケンスに対応し、前記無線トランシーバは、少なくともデータパケットを受信するために使用され、その動作は、請求項１から８の何れかに記載の方法によって設定される、ノード。
【請求項１０】
請求項９に記載の１つ又は複数のルーティングノードを含む非同期ワイヤレス通信ネットワーク。
【請求項１１】
全てのルーティングノードが請求項９に記載のものである、請求項１０に記載の非同期ワイヤレス通信ネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、非同期ワイヤレス通信ネットワークのルーティングノードの動作を設定するための方法に関し、それを実装するネットワークノード及び通信ネットワークに関する。
【背景技術】
【０００２】
ＷＰＡＮ［ワイヤレス・パーソナル・エリア・ネットワーク］ネットワークは数年来知られている。ＰＡＮ［パーソナル・エリア・ネットワーク］ネットワークは、ある人に近接するデバイス間で通信するためのコンピュータネットワークと定義され得る。ＷＰＡＮネットワークは、ワイヤレス短距離通信技術を使用するＰＡＮネットワークである。
【０００３】
ＷＰＡＮネットワークを実装するために頻繁に使用される通信技術はＺｉｇＢｅｅである。
【０００４】
ＷＰＡＮネットワークの主な最近の適用例の１つは、ＷＳＮ［ワイヤレス・センサ・ネットワーク］ネットワークである。
【０００５】
ＷＰＡＮネットワークでは、主要な構成要素はネットワークのノードであり、これらノードはデバイスとも呼ばれている。一般に、ＷＰＡＮネットワークは商用電源式デバイスとバッテリ電源式デバイスとの混合を含み得る。バッテリ電源式デバイスは、該デバイスのバッテリの長寿命を保証するために、エネルギー消費を制限するように設計される。センサネットワークノードは、該ノードのバッテリのエネルギーがなくなったときに容易に再充電又は交換できない場合があるため、適用例の長期配備を達成するために、ＷＳＮネットワークにおけるエネルギーの効率的な使用を提供することが特に重要である。
【０００６】
ＷＰＡＮネットワークのノードのうちの、エネルギー消費の主な原因である構成要素は、無線トランシーバ（送信時と受信時の両方）である。非同期ＷＰＡＮネットワーク（ノードが同期クロックを有さず、従って同期して送信及び受信をしないネットワーク）におけるエネルギー消費を低減する典型的で有効な方法は、「デューティーサイクル」を使用すること、即ち、短い時間インターバル中にデバイスの無線トランシーバを間欠的に動作させることである。このようにすると、各ノードの動作は（短い）アウェイク・インターバルと（長い）スリープ・インターバルとの周期的（固定トランシーバ動作周期）シーケンスになる。当然、これにより、ＷＰＡＮネットワークにおいて使用される通信プロトコルは複雑化する。
【０００７】
従来技術から、既知の非同期ＷＳＮネットワークが存在し、この非同期ＷＳＮネットワークでは、全ての（又はほとんど全ての）ノードはバッテリ電源式であり、従ってエネルギー消費を制限するように設計されており、無線トランシーバのエネルギー消費を制限するために特別なＭＡＣプロトコルが使用されている。
【０００８】
ジェイ・ポラストル（Ｊ．Ｐｏｌａｓｔｒｅ）らによる論文、「Ｖｅｒｓａｔｉｌｅ  Ｌｏｗ  Ｐｏｗｅｒ  Ｍｅｄｉａ  Ａｃｃｅｓｓ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ（ワイヤレスセンサネットワークのための多用途な低電力メディアアクセス）」（ＳｅｎＳｙｓ２００４、２００４年１１月）は、「プリアンブルサンプリング」に基づく「Ｂ−ＭＡＣ」と呼ばれるそのようなＭＡＣプロトコルの１つを詳細に記載している。このプロトコルによれば、送信側ノードが送信するデータを有するとき、送信側ノードは少なくとも受信側ノードのスリープ周期のインターバル（この継続時間は「プリアンブル長」と呼ばれる）の長さ持続するプリアンブルを送信する。受信側ノードが起動するとき（これは「検査インターバル」と呼ばれる周期に従って発生する）、受信側ノードはプリアンブルを検出し、アウェイクを維持してデータを受信する。この論文は、エネルギー消費、遅延及び処理量を最適化し、変化するネットワーク条件に適応するために、適用例が「検査インターバル」及び「プリアンブル長」を変更することが可能な一組の双方向インターフェースを使用することについても述べている。
【０００９】
エム・ビュットナー（Ｍ．Ｂｕｅｔｔｎｅｒ）らの論文、「Ｘ−ＭＡＣ：Ａ  Ｓｈｏｒｔ  Ｐｒｅａｍｂｌｅ  ＭＡＣ  Ｐｒｏｔｏｃｏｌ  ｆｏｒ  Ｄｕｔｙ−Ｃｙｃｌｅｄ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ（Ｘ−ＭＡＣ：デューティーサイクル化ワイヤレスセンサネットワークのための短プリアンブルＭＡＣプロトコル）」（ＳｅｎＳｙｓ２００６、２００６年１１月）は、「プリアンブルサンプリング」及び短い固定長プリアンブルのシーケンスに基づく「Ｘ−ＭＡＣ」と呼ばれるそのようなＭＡＣプロトコルの別の１つを詳細に記載している。このプロトコルによれば、送信元ノードが情報パケットを送信しなければならないとき、その送信機は、それぞれが宛先ノードのアドレスを含む一連の短い固定長プリアンブルを送信する。プリアンブルの間の小さな中断は、（自身の内部動作スケジュールに従って）宛先ノードの受信機がアウェイクし、プリアンブルを検出し確認応答を送ることを可能とし、この確認応答は、プリアンブルのシーケンスを停止し、データを受信するために宛先ノードが利用可能であることを信号で伝えるものである。ストローブドプリアンブルを傍聴した宛先ではない受信機は、データを受信するためにアウェイクを維持するのではなく、直ちにスリープに戻ることができる。この論文は、パケット毎のエネルギー消費、遅延、又はその両方について最適化するために、デューティーサイクルパラメータを動的に調整するために使用され得る適応アルゴリズムも記載している。
【００１０】
エネルギー消費を低減するための別の手法が米国特許第７，０３５，２４０号によって開示されている。この特許は、エネルギー効率の良いネットワークを実装するための方法及びネットワークアーキテクチャを扱う。このネットワークは、最終的には基地局に送られるデータを収集及び送信する複数のノードを含む。ネットワークノードは、クラスタヘッドとして動作する単一のノードを有する一組のクラスタを形成する。クラスタヘッドはそのクラスタに加わることをノードに通知し、クラスタ内のデータの収集をスケジュールし、次いでデータを基地局に送信する。クラスタは個々のノードからのデータをインテリジェントに結合することができる。ある動作期間の後、クラスタはクラスタヘッドとして動作するノードの別の組で再形成される。このネットワークは、個々のノードのエネルギー使用のバランスを取ることによって、システムの長寿命を提供する。
【発明の概要】
【発明が解決しようとする課題】
【００１１】
本願の出願人は、非同期ワイヤレス通信ネットワークにおいて、特にＷＰＡＮ／ＷＳＮネットワークにおいて、以下の理由で、既知のプロトコルに関してネットワークノードのエネルギー消費のはるかに良い最適化が必要であると考えた。
【００１２】
米国特許第７，０３５，２４０号から知られている解決策は、高いレベルのアプローチに基づいており、この高いアプローチは、ネットワークのクラスタヘッドノードにおける負荷分散及びデータ集約を必要とし、ＴＤＭＡ［時分割多元接続］スケジュールに基づいてネットワークの各クラスタ内で同期ネットワークを提供する。
【００１３】
上述の２つの論文から知られている解決策はランダムアクセスの影響を考慮しておらず、このランダムアクセスは、データトラフィック、ＭＡＣパラメータ及びネットワークトポロジの関数であり、大部分のエネルギー消費の原因である。言い換えれば、エネルギー消費モデルは簡略化されすぎており、いかなる真の最小化ももたらすことができない。
【００１４】
本願発明は、従来技術の解決策を改善することを目的とする。
【００１５】
特に、本願発明は、デューティーサイクル化非同期ワイヤレス通信ネットワークにおけるエネルギー消費を最小化する課題に取り組んでいる。
【課題を解決するための手段】
【００１６】
本願発明の背後にある基本的な着想は、ランダムアクセスの影響を考慮するエネルギー消費モデルを使用することである。何れにせよ、モデルを簡略化するために、ネットワークは複数のクラスタに分割され、それにより前記クラスタのそれぞれは１つのクラスタヘッドノードを含むようになる。この分割を行う目的で、クラスタヘッドノードはクラスタのその他のノードからデータパケットを受けるのみとみなされるルーティングノードであり、クラスタのその他のノードはクラスタヘッドノードにデータパケットを送るのみとみなされるノードである。このことは、この分割次第でクラスタが部分的に重複し得ることを意味する。
【００１７】
このモデルを構築するために、本願の出願人は、クラスタのノードの何れかによってクラスタ内での送信が試行されたときにビジーチャネル確率に出くわし、クラスタのノードの何れかによってクラスタ内での送信が実行されたときに通信衝突確率に出くわし、データパケットは、伝送成功確率（「信頼性」と呼ばれ得る）及び伝送の平均遅延（「レイテンシ」と呼ばれ得る）とともにクラスタ内で伝送されると考えた。更に、本願の出願人は、クラスタのノードの数及び平均データパケット生成率の影響を考え、この平均データパケット生成率に従って、クラスタのノードはデータパケットを送信することになる。
【００１８】
本願の明細書において提案されるモデルによれば、クラスタのエネルギー消費は、主に、ビジーチャネル確率、通信衝突確率、クラスタヘッドノードのアウェイク・インターバルの継続時間及びスリープ・インターバルの継続時間の関数である。更に、エネルギー消費は、クラスタのノードの数及び平均データパケット生成率の関数である。
【００１９】
エネルギー消費の最小化は、ビジーチャネル確率及び通信衝突確率の所定の値のもと、且つ、伝送成功確率及び伝送の平均遅延に対する所定の制限のもとで実行される。このようにして、クラスタヘッドノードのアウェイク・インターバルの継続時間及びスリープ・インターバルの継続時間の最適値が求められる。これらの最適値が求められると、これらはクラスタヘッドノードの動作パラメータとして設定され、使用される。
【００２０】
ネットワークの複数のクラスタへの分割は、固定され且つ所定のものであってもよく、又は、本願発明に従って１回のみ若しくは繰り返して例えば周期的に実行されるステップのうちの１つであってもよい。
【００２１】
一般に、ネットワークの様々なルーティングノードの動作パラメータは異なることに留意されたい。
【００２２】
最適な動作パラメータを求めることは、ネットワークの動作中に、例えば周期的に、繰り返され得る。これは、例えば、ビジーチャネル確率若しくは通信衝突確率又はそのような確率の両方がネットワークの動作中に変化する場合に有利である。これらの２つの確率は、ネットワークの動作中にネットワークの各ルーティングノードによって求めることができる。特に、ビジーチャネル確率は、同一クラスタのその他のノードによって作成されるビジーチャネル確率の推定値を受信し、受信した推定値の平均又は最大を計算することによって求めることができる。
【００２３】
動作パラメータの最適値は、ネットワークの動作中にネットワークの各ルーティングノードによって求めることができる。これを迅速に単純なハードウェアを用いて行うために、このような求めることは事前に計算された値のテーブルに基づいていてもよい。このようなテーブルは、各ルーティングノードの内部に格納され得る。ルーティングノード内にこのように格納することは、例えば基地局によって実行されてもよい。このような基地局は、ネットワークが動作を開始する前に、１つ又は複数のテーブルの全ての値を計算しておくことができる。
【００２４】
更なる態様によれば、本願発明は、エネルギー消費を最小化する上記の方法を実装するネットワークノード及び通信ネットワークに関する。
【００２５】
本願発明は、添付の図面と併せて考慮されるべき以下の説明からより明らかとなろう。
【図面の簡単な説明】
【００２６】
【図１】第１のクラスタ及び第２のクラスタが強調された、本願発明によるデューティーサイクル化非同期ワイヤレス通信ネットワークを示す図である。
【図２】プリアンブルサンプリングに基づき複数の短いプリアンブルを有する非同期デューティーサイクルＭＡＣプロトコルによる送信元ノード及び宛先ノードの動作を説明する時間図である。
【図３】本願発明によるビジーチャネル確率を推定するための方法を説明する流れ図である。
【図４】本願発明による衝突の確率を推定するための方法を説明する流れ図である。
【図５】本願発明に従って最適な動作パラメータを求めるためにルーティングノードによって使用される値のテーブルである。
【図６】本願発明に従ってルーティングノードによって図５のテーブルを使用する方法を説明する流れ図である。
【発明を実施するための形態】
【００２７】
以下の説明及び添付の図面は、本願発明を限定するものではなく、単に例示するものとして解釈されるべきであることを理解されたい。
【００２８】
本願発明がより一般に非同期ワイヤレス通信ネットワークに適用され得るとしても、以下に記載される本願発明の実施形態は、ＷＰＡＮ［ワイヤレス・パーソナル・エリア・ネットワーク］ネットワーク、具体的にはＺｉｇＢｅｅ技術を使用するＷＳＮ［ワイヤレス・センサ・ネットワーク］ネットワークに関する。ネットワークノードの動作は、例えば水晶振動子であるが、タイマ（通常はローカルタイマ）によって生成される独自のクロック信号を用いて調節される。タイマは、ネットワークノードによって時間インターバルの継続時間を測定するためにも使用される。既に説明したように、ネットワークは、そのノードが同期クロックを有さず、従って同期して送信及び受信しない場合、「非同期」と定義される。
【００２９】
デューティーサイクル化非同期ワイヤレス通信ネットワークの動作は知られており、例えば、既に引用したエム・ビュットナー（Ｍ．Ｂｕｅｔｔｎｅｒ）による論文に記載されている。また、この論文は、以下に記載される本願発明の実施形態の場合と同様の、短い固定長プリアンブルのシーケンスの送信に基づくＭＡＣプロトコルを記載している。
【００３０】
図１は、本願発明による、ＺｉｇＢｅｅメッシュ型トポロジを具体化するＷＳＮネットワークを示す。このネットワークは、７つのルータ、Ｒ１、Ｒ２、Ｒ３、Ｒ４、Ｒ５、Ｒ６、Ｒ７、及び７つのエンドデバイス、Ｅ１、Ｅ２、Ｅ３、Ｅ４、Ｅ５、Ｅ６、Ｅ７を含む。
【００３１】
図２は、図１のネットワークにおいてデータが送信元ノードＳＮから宛先ノードＤＮに送信されるべきときの、送信元ノードＳＮ（例えばノードＥ４）及び宛先ノードＤＮ（例えばノードＲ３）の動作を説明する時間図を示す。
【００３２】
「デューティーサイクル化」送信方式によれば、宛先ノードＤＮは、例えば送信元ノードＳＮからの宛先ノードＤＮ向けのデータがあるかどうかを確認するために、周期的に起動する。データがある場合、宛先ノードＤＮはデータを受信し、データがない場合、宛先ノードＤＮはスリープに戻る。これが周期的に繰り返される。スリープ状態で費やされる時間は「スリープ時間」と呼ばれ、スリープ・インターバルの継続時間Ｒｓに対応し、アウェイク状態で費やされる時間は「アウェイク時間」と呼ばれ、アウェイク・インターバルの継続時間Ｒｌに対応する。
【００３３】
「プリアンブルサンプリング」ＭＡＣプロトコルにおいて、送信元ノードが宛先ノードに送信するデータを有する場合、送信元ノードが宛先ノードから確認応答パケットを受け取るか、又は宛先ノードの最大スリープ時間に対応する「時間制限」ＴＬを超えるまで、送信元ノードは、それぞれが宛先ノードの識別子を含む一連の短いプリアンブルパケットを送信する。図２の例では、確認応答パケットＡＣＫは、わずか２つのプリアンブルパケットＰＲＥ１及びＰＲＥ２の送信後に、送信元ノードＳＮによって受信される。
【００３４】
一般に、宛先ノードが起動し、通信チャネル内の無線信号を検出しない場合、宛先ノードは直ちにスリープに戻る。宛先ノードがプリアンブルパケットを受信するが、そのプリアンブルパケットの対象ではない場合、宛先ノードはこの検査の後にスリープに戻る。宛先ノードがプリアンブルパケットを受信し、そのプリアンブルパケットの対象である場合、宛先ノードはプリアンブルパケットの受信後に確認応答パケットを送信元ノードに送信する。確認応答パケットの受信後、送信元ノードはデータパケットを宛先ノードに送信する。
【００３５】
図２は、このような通信に関連する更なる詳細を示す。図２のイベントのシーケンスは図１のネットワークの動作中に発生し得る多くの可能性の１つに過ぎないことが強調されるべきである。
【００３６】
送信の要求ＲＴは送信元ノードＳＮの上位層からＭＡＣ層に送信され、ランダムな時間ＲＢ１（「ランダムバックオフ」と呼ばれる）が費やされてから通信チャネルが検知される。短い時間インターバルＣＳ１中にチャネル検知が実行される。この時点で、通信チャネル内に無線信号があり、即ち、チャネルがビジーであり（典型的には、送信のために別のノードによって使用され）、従って別のランダムな時間ＲＢ２が費やされ、次いで時間インターバルＣＳ２中にチャネルが再度検知される。ここで、チャネルが利用可能となり、従ってプリアンブルパケットＰＲＥ１が送信元ノードＳＮによって送信される。
【００３７】
プリアンブルパケットＰＲＥ１の送信後、送信元ノードＳＮは宛先ノードＤＮからの応答を待ちながら時間インターバルＴＯ１を費やす。この場合、時間インターバルＴＯ１は「タイムアウト」ＴＯとして持続する。プリアンブルパケットＰＲＥ１が送信されたときに宛先ノードＤＮがスリープ状態であったため、時間インターバルＴＯ１中に宛先ノードＤＮは応答しない。
【００３８】
時間インターバルＴＯ１の後、宛先ノードＤＮが応答しなかったため、ランダムな時間ＲＢ３が費やされてから時間インターバルＣＳ３中に通信チャネルが検知され（チャネルが利用可能であることが分かる）、プリアンブルパケットＰＲＥ２が送信元ノードＳＮによって送信される。ランダムな時間ＲＢ３中に宛先ノードＤＮが起動する（図２の時点ｔＡＷ）。
【００３９】
プリアンブルパケットＰＲＥ２の送信後、送信元ノードＳＮは宛先ノードＤＮからの応答を待ちながら時間インターバルＴＯ２を費やす。この場合、プリアンブルパケットＰＲＥ２が送信され送信元ノードＳＮに応答したときに宛先ノードＤＮが起動していたため、時間インターバルＴＯ２は「タイムアウト」ＴＯ未満しか持続しない。
【００４０】
プリアンブルパケットＰＲＥ２の受信後、宛先ノードＤＮはランダムな時間ＲＢ４を費やしてから時間インターバルＣＳ４中に通信チャネルを検知し（チャネルが利用可能であることが分かる）、確認応答パケットＡＣＫを送信元ノードＳＮに送信する。
【００４１】
確認応答パケットＡＣＫの受信後、送信元ノードＳＮはランダムな時間ＲＢ５を費やしてから時間インターバルＣＳ５中に通信チャネルを検知し（チャネルが利用可能であることが分かる）、データパケットＤＡＴを宛先ノードＤＮに送信する。
【００４２】
確認応答パケットＡＣＫの送信後、宛先ノードＤＮは単にデータパケットＤＡＴを待ち、データパケットＤＡＴを受信した後、スリープに戻る（図２の時点ｔＡＳ）。
【００４３】
「プリアンブルサンプリング」プロトコルでは、データパケットを送信するためのランダムアクセスに費やされる時間は一般に、送信に費やされる時間よりもはるかに大きい（例えば、デフォルトのパラメータ設定を有するＩＥＥＥ８０２．１５．４によれば、データパケット送信前の最大バックオフ時間は２７．４ｍｓであるが、５６バイトデータパケットの送信時間は２５０ｋｂｐｓで１．７９ｍｓである）。ランダムアクセスはデータトラフィック、ＭＡＣパラメータ及びネットワークトポロジに依存する。ランダムアクセスはエネルギー消費を引き起こす。従って、正確なエネルギー消費モデルはランダムアクセスも考慮するべきである。
【００４４】
本願発明によるエネルギー消費モデルの場合、ネットワークのノードはクラスタに編成されると仮定される。同モデルは各クラスタに適用される。
【００４５】
クラスタ化されたトポロジでは、ノードは、クラスタヘッドノード（これはルーティングノードである）として機能する１つのノードを有するクラスタに編成される。クラスタの全てのノード（クラスタヘッドノードを除く）は、そのデータを直接クラスタヘッドノードに送信する。
【００４６】
ネットワークが「ツリー型」トポロジを有する場合、クラスタヘッドノードは、クラスタのその他全てのノード（エンドデバイスである）からデータを受信し、これらのデータをコーディネータノードとして機能する基地局に転送する。ネットワークが「メッシュ型」トポロジを有する場合、クラスタヘッドノードはクラスタのその他全てのノードからデータを受信し、これらのデータをルータノードに転送する。
【００４７】
本願発明によるエネルギー消費モデルの「ツリー型」トポロジへの適用は容易である。
【００４８】
このモデルを「メッシュ型」トポロジに適用するために、ネットワークは複数のクラスタに分割され、それにより前記クラスタのそれぞれが１つのクラスタヘッドノードを含む。この分割を行う目的で、クラスタヘッドノードはクラスタのその他のノードからデータパケットを受信するのみとみなされるルーティングノードであり、クラスタのその他のノードはデータパケットをクラスタヘッドノードに送信するのみとみなされるノードである。ルーティングノードがデータパケットを受信するだけでなく送信する場合もあることを考慮するため、ルーティングノードは、一般に、少なくとも２つの異なるクラスタに属するが、ただ１つのクラスタのクラスタヘッドノードである。このことは、この分割次第でクラスタが部分的に重複し得ることを意味する。
【００４９】
図１を参照すると、ネットワークの第１のクラスタＣＬ１は、ルータＲ２、Ｒ３及びＲ４、並びにエンドデバイスＥ４及びＥ５を含み、ルータＲ３をそのクラスタヘッドノードとみなし、ネットワークの第２のクラスタＣＬ２は、ルータＲ３、Ｒ４、Ｒ５及びＲ６を含んでエンドデバイスを含まず、ルータＲ４をそのクラスタヘッドノードとみなす。従って、ノードＲ３及びＲ４は、２つの異なるクラスタ、即ち、ＣＬ１及びＣＬ２に属するが、第１のクラスタＣＬ１を見てみると、ノードＲ３はデータパケットを受信するのみ、ノードＲ４はデータパケットを送信するのみであり、第２のクラスタＣＬ２を見てみると、ノードＲ３はデータパケットを送信するのみ、ノードＲ４はデータパケットを受信するのみである。図１のネットワークの完全な分割は、ネットワークの各ルータに１つの、７つのクラスタを提供することを理解されたい。
【００５０】
本願の明細書を通して、ネットワークのノードのデータパケット生成率は、アウェイク・インターバルの継続時間を加えたスリープ・インターバルの継続時間によって与えられる継続時間中に、ノードが最大で１つの送信するデータパケットを有するように仮定される。従って、ノードがＲｌ＋Ｒｓ以内にデータパケットを送信できない場合、そのパケットは破棄される。
【００５１】
以下において、頭字語「ＲＸ」及び「ｒｘ」はしばしば「受信機」又は「受信側ノード」の代わりに使用され、頭字語「ＴＸ」及び「ｔｘ」はしばしば「送信機」又は「送信側ノード」の代わりに使用される。
【００５２】
以下の数式における全ての符号を、以下の表に列挙し説明する。
【００５３】
【表１】
0005175398.tif 000002
【００５４】
【表２】
0005175398.tif 000003
【００５５】
遅延のモデル化
送信元ノード（送信側ノード）から宛先ノード（受信側ノード又はクラスタヘッドノード）にデータパケットを伝送するための遅延の確率は、以下の式
【００５６】
【数１】
0005175398.tif 000004
【００５７】
によって与えられる。ここで、ＥＴａ及びＥＴｌは、それぞれＴａ（Ｔ、下付きのＡ）及びＴｌ（Ｔ、下付きのＬ）の分散についての統計的平均を表す。Ｔａ（Ｔ、下付きのＡ）は、送信の開始からアウェイク・インターバルの開始まで待つするためのランダムな時間であり、Ｔｌ（Ｔ、下付きのＬ）は、アウェイク・インターバル中にプリアンブルパケットが受信される時点からアウェイク・インターバルが終了するまでの継続時間であり、Ｔｐは、データパケットの受信に成功するまで待つするための遅延であり、ｔｍａｘは、適用例によって所望される最大遅延であり、Ｃは、通信衝突確率である。
【００５８】
パケットがｔｍａｘ又はｔｍａｘ未満遅延する確率は、以下の式
【００５９】
【数２】
0005175398.tif 000005
【００６０】
によって与えられる。
【００６１】
Ｔｐの平均及び分散は、以下の式
【００６２】
【数３】
0005175398.tif 000006
【００６３】
によって与えられる。ここで、μＴｐ及びσＴｐは、それぞれＴｐの平均及び分散であり、Ｔ２は、データパケットが内部で生成される時点から対応する確認応答パケットがＴＸノードに到達するまでＴＸノードによって費やされる期間であり、Ｔ３は、確認応答パケットが受信された直後から開始されデータパケットが送信される直前に終了する、ＴＸノードによって費やされる期間である。
【００６４】
Ｔ２の平均及び分散は、以下の式
【００６５】
【数４】
0005175398.tif 000007
【００６６】
によって与えられる。ここで、
【００６７】
【数５】
0005175398.tif 000008
【００６８】
であり、ここで、
【００６９】
【数６】
0005175398.tif 000009
【００７０】
及び
【００７１】
【数７】
0005175398.tif 000010
【００７２】
である。
【００７３】
上記の式から分かるように、Ｔ２の平均及び分散は、以下の式によって与えられるＴ１（データパケットが内部で生成される時点から第１の対応するプリアンブルパケットが実際に送信されるまでＴＸノードによって費やされる期間）の平均及び分散に関係する。
【００７４】
【数８】
0005175398.tif 000011
【００７５】
ここで、
【００７６】
【数９】
0005175398.tif 000012
【００７７】
であり、ここで、
【００７８】
【数１０】
0005175398.tif 000013
【００７９】
である。
【００８０】
上記の式から分かるように、Ｔ２の平均及び分散は、以下の式によって与えられるＴａｃｋ（プリアンブルパケットの送信の終了から対応する確認応答パケットの送信の終了までの期間）の平均及び分散にも関係する。
【００８１】
【数１１】
0005175398.tif 000014
【００８２】
【数１２】
0005175398.tif 000015
【００８３】
Ｔ３の平均及び分散は、以下の式
【００８４】
【数１３】
0005175398.tif 000016
【００８５】
によって与えられる。
【００８６】
信頼性のモデル化
「信頼性」と呼ばれ得る、送信元ノード（送信側ノード）から宛先ノード（受信側ノード又はクラスタヘッドノード）へのデータパケットの伝送に成功する確率は、以下の式
【００８７】
【数１４】
0005175398.tif 000017
【００８８】
によって与えられる。ここで、ＲＸノードのアウェイク・インターバル中にプリアンブルパケットの送信に成功し、ＴＸノードのタイムアウトが終了する前に対応する確認応答パケットの送信に成功する確率は、以下の式
【００８９】
【数１５】
0005175398.tif 000018
【００９０】
によって与えられる。
【００９１】
ＴＸノードがデータパケットの送信に成功する確率は、プリアンブルパケットの受信に成功し、確認応答パケットの受信にも成功した場合、以下の式
【００９２】
【数１６】
0005175398.tif 000019
【００９３】
によって与えられる。
【００９４】
エネルギー消費のモデル化
ネットワークの各クラスタについて、Ｒｌ＋Ｒｓによって正規化された、平均エネルギー消費（言い換えれば、合計エネルギーＥｔｏｔの期待値
【００９５】
【数１７】
0005175398.tif 000020
【００９６】
）は、以下の式
【００９７】
【数１８】
0005175398.tif 000021
【００９８】
によって与えられる。ここで、Ｎは、クラスタ内の送信側ノードの数（クラスタのノードの合計数から１、即ち、クラスタヘッドノードを引いた数に等しい）であり、ｄＴＸは、Ｒｌ＋Ｒｓの時間インターバル中に送信側ノードがクラスタヘッドノードに送信する少なくとも１つのデータパケットを有する確率、即ち、
【００９９】
【数１９】
0005175398.tif 000022
【０１００】
であり、ここで、λは、平均データパッケージ生成率である。
【０１０１】
この式において、第１の加数は、送信側ノードの平均エネルギー消費であり、第２の加数は、受信側ノード、即ち、クラスタヘッドノードの平均エネルギー消費である。
【０１０２】
１つの送信側ノードの平均エネルギー消費は、以下の式
【０１０３】
【数２０】
0005175398.tif 000023
【０１０４】
によって与えられる。
【０１０５】
上記の等式における第１の行は、データパケット送信が成功した場合に費やされるエネルギーに対応し、第２の行は、データパケット送信が失敗した場合に費やされるエネルギーに対応する。
【０１０６】
上記の式の第１の行における４つの加数はそれぞれ、イベントＢｉが発生した場合、即ちｉ番目のプリアンブルパケットの送信に成功し、対応する確認応答パケットの受信に成功した場合にチャネルにアクセスして「ｉ」個のプリアンブルパケットを送信するためのエネルギー、プリアンブルパケットに対してＴＸノードの「ｉ−１」（固定）タイムアウト期間中に費やされるエネルギー、確認応答パケットを受信するためのエネルギー、データパケットを送信するためのエネルギーである。
【０１０７】
上記の式の第２の行における３つの加数はそれぞれ、チャネルがビジーであるか、衝突又はランダムバックオフのために受信側ノードのアウェイク・インターバルを逸したため、Ｎｐ個（プリアンブルパケットの最大数）のプリアンブルパケットは送信されるが、データパケットは送信されないときに費やされるエネルギーである。
【０１０８】
これらの加数は、以下の式
【０１０９】
【数２１】
0005175398.tif 000024
【０１１０】
によって定義される。
【０１１１】
これらの等式において、以下の項が使用されている。
【０１１２】
【数２２】
0005175398.tif 000025
【０１１３】
ここで、
【０１１４】
【数２３】
0005175398.tif 000026
【０１１５】
である。
【０１１６】
クラスタヘッドノードでのエネルギー消費（「Ｅｒｘ」）は、アイドルリスニング、確認応答パケットの送信及びデータパケットの受信のために費やされるエネルギーによってもたらされる。これらのイベントはそれらの間及び異なるノード間で高度に相互相関しているため、これらのイベントの確率に閉形式を提供することは難しい。その結果、正確な特徴付けは、受信側ノードがデータパケットの受信時にビジーであると同時に他のノードが別のデータパケットを送信しようとしている確率をモデル化することを必要とする。従って、送信側ノードで費やされるエネルギーと比べた場合に受信側ノードで費やされるエネルギーが小さいことを考慮することによって、以下の上限が使用される。
【０１１７】
【数２４】
0005175398.tif 000027
【０１１８】
ここで、確認応答パケットがアウェイク・インターバルの終了直前に送信された場合、アウェイク・インターバルの終了後、受信側ノードはタイムアウト（「Ｔｏｕｔ」＝データパケットに対するＲＸノードの固定のタイムアウト期間）の間リッスンしていることができると仮定される。
【０１１９】
エネルギー消費の最小化
先ほど求めたエネルギー、遅延及び信頼性の式を使用する前に、送信を試行するときのビジーチャネル確率及び送信中の通信衝突確率を求めることが必要である。その後、エネルギー消費を設定された閾値未満に低減する、例えば最小化するアウェイク・インターバルの継続時間及びスリープ・インターバルの継続時間の最適値を求めることができる。
【０１２０】
本願発明の最良の実施形態によれば、ビジーチャネル確率及び通信の確率は何れも可変であり、ネットワークの動作中に各クラスタについて繰り返し（例えば周期的に）求められ、次いでこれらの値は各クラスタヘッドノードに対するアウェイク・インターバルの継続時間及びスリープ・インターバルの継続時間の最適値を繰り返し求めるために使用される。
【０１２１】
ビジーチャネル確率を求めること
ビジーチャネル確率は、クラスタヘッドノードへのパケット（プリアンブルパケット又はデータパケット）の送信を試行している間、各非クラスタヘッドノードで推定される。図３は、ビジーチャネル確率を推定するための方法の考え得る流れ図を示す。
【０１２２】
ノードによって作成される推定値は、プリアンブルパケットのペイロード内でクラスタヘッドノードに送信され得る。プリアンブルパケットがクラスタヘッドノードに送信されるたびに、送信側ノードがビジーチャネル確率の送信側ノードの最新の推定値をペイロード内に挿入することが好ましい。
【０１２３】
クラスタヘッドノードは、その隣接するノードから受信したビジーチャネル確率の推定値（例えば各隣接ノードに１つの値）をテーブルに格納し得る。最適な動作パラメータを求めるために使用されるビジーチャネル確率は、このテーブルに格納された値の平均として計算されることが好ましい。代替として、例えば、最適な動作パラメータを求めるために使用されるビジーチャネル確率は、このテーブルに格納された値の最大値として計算され得る。
【０１２４】
図３の例は、非スロット化ＩＥＥＥ８０２．１５．４  ＣＳＭＡ／ＣＡ［衝突回避を有する搬送波検知多重アクセス］機構の場合を引用している。ネットワーク内の各ノードは、２つの変数ＮＢ及びＢＥを有する。ＮＢは、現在の送信を試行している間に使用されるバックオフの数（「ランダムバックオフ時間」と呼ばれる、ランダムな期間を測定するための単位期間である）である。ＮＢは、全ての新規の送信前に０に初期化される。ＢＥは、バックオフ指数であり、これはノードがチャネルを評価することを試みる前に何回バックオフを待たなければならないかに関連する。ランダムバックオフ時間に影響するパラメータは、ｍｉｎＢＥ、ｍａｘＢＥ、及びｍａｘＮＢであり、これらはそれぞれ、ＢＥの最小値及び最大値並びにＮＢの最大値に対応する。
【０１２５】
ＮＢは０に初期化され、ＢＥはｍｉｎＢＥに初期化される（ステップ３０１）。ＭＡＣ層は０から２ＢＥ−１の範囲のバックオフの乱数の間遅延し（ステップ３０２）、次いで物理層にＣＣＡ［クリアチャネル評価］を実行するよう要求する（ステップ３０３）。ＣＣＡの結果が考慮される（ステップ３０４）。チャネルがビジーである場合（ブロック３０４から出ていく矢印Ｎ）、チャネルはアクセスされず、ＭＡＣ層は、ＢＥがｍａｘＢＥ未満を維持することを保証しながらＮＢ及びＢＥの両方を１だけ増分し（ステップ３０６）、チャネルが利用可能である場合（ブロック３０４から出ていく矢印Ｙ）、チャネルがアクセスされ、本方法は成功裏に終了する（ステップ３１０）。ＮＢ及びＢＥを増分した後、ＮＢの値に関して、即ちＮＢの値がｍａｘＮＢより大きいかどうかについて検査が実行される（ステップ３０７）。検査が肯定的である場合（ブロック３０７から出ていく矢印Ｙ）、チャネルはアクセスされず、本方法は不成功に終了する（ステップ３０８）。検査が否定的である場合（ブロック３０７から出ていく矢印Ｎ）、ＭＡＣ層はＮＢ及びＢＥの更新された値を使用してバックオフの乱数の間遅延する（ステップ３０２）。
【０１２６】
ビジーチャネル確率「ｃ」は初期値「ｃ０」に初期化され、上記のプロセス中に更新される。チャネルがビジーである場合（ブロック３０４から出ていく矢印Ｎ）、ビジーチャネル確率はｃ＝αｃ＋（１−α）１に更新され（ステップ３０５）、チャネルが利用可能である場合（ブロック３０４から出ていく矢印Ｙ）、ビジーチャネル確率はｃ＝αｃに更新され（ステップ３０９）、ここで、αは重み係数、例えば０．９又は０．９９である。
【０１２７】
衝突の確率を求めること
送信側ノードは、送信されたプリアンブルパケットに対する応答として確認応答パケットが受信されない場合、そのプリアンブルパケットに衝突が発生したと結論付ける場合がある。何れにせよ、確認応答パケットを返すのに失敗する理由は、ほとんどの場合、送信中に宛先ノードがスリープ状態であるということである。
【０１２８】
従って、本願発明によれば、衝突の確率は、クラスタヘッドノードであるレシーバ（即ちクラスタヘッドノード）側で有利に求められる。図４は任意の受信試行時の衝突の確率を求めるための方法の考え得る流れ図を示す。
【０１２９】
カウンタ「ｎ」は０に初期化される（ステップ４０１）。クラスタヘッドノードはＲＳＳＩ［受信信号強度指標］を検査する（ステップ４０２）。ＲＳＳＩが受信閾値「Ｒｔｈ」より大きい場合（ブロック４０２から出ていく矢印Ｙ）、パケットは送信されている。そうでない場合（ブロック４０２から出ていく矢印Ｎ）、パケットは送信されておらず、カウンタがリセットされる（ステップ４０１）。送信がある場合、クラスタヘッドノードはカウンタ「ｎ」を増分することによってＲＳＳＩが受信閾値を上回っている間のシンボルの数を数え（ステップ４０３）、その値をパケット「Ｎｔｈ」を形成するシンボルの最小数と比較する（ステップ４０４）。そのように数えられたシンボルの数がＮｔｈより大きい場合（ブロック４０４から出ていく矢印Ｙ）、パケットは受信されており、プリアンブルビットについて検査が実行される（ステップ４０５）。プリアンブルビットの検出に成功しなかった場合（ブロック４０５から出ていく矢印Ｎ）、クラスタヘッドノードは衝突があったものとみなし、衝突の確率をｐ＝βｐ＋（１−β）１に更新する（ステップ４０６）。プリアンブルビットの検出に成功した場合（ブロック４０５から出ていく矢印Ｙ）、ＣＲＣ［巡回冗長検査］が検査される（ステップ４０７）。ＣＲＣが一致する場合（ブロック４０７から出ていく矢印Ｎ）、衝突があり、衝突の確率はｐ＝βｐ＋（１−β）１に更新され（ステップ４０６）、ＣＲＣが一致しない場合（ブロック４０７から出ていく矢印Ｙ）、衝突の確率はｐ＝βｐに更新され（ステップ４０８）、ここで、βは重み係数、例えば０．９又は０．９９である。
【０１３０】
最適化の問題
クラスタヘッドのスリープ・インターバル及びアウェイク・インターバルの継続時間、ノードの数、平均データパケット生成率、ビジーチャネル及び衝突の確率の関数としてエネルギー、遅延及び信頼性の式が与えられると、エネルギーは以下の信頼性の制限及び遅延の制限を条件として最小化される。
【０１３１】
【数２５】
0005175398.tif 000028
【０１３２】
ここで、τｍａｘは、遅延がｔｍａｘ未満である所望の確率であり、ψｍｉｎは、データパケットが伝送されるべき最小の所望の確率である。この最適化において、ｃ及びｐはフィードフォワード変数であるが、λ、ｔｍａｘ、τｍａｘ、及びψｍｉｎは適用例の要件である。
【０１３３】
動作パラメータＲｌ及びＲｓに関するこの最小化の問題の解決策は、標準的な数値技法によって得ることができる。当業者は、それぞれの特定の状況において、信頼性の制限及び遅延の制限を条件として、設定された閾値を下回るエネルギーレベルを達成するクラスタヘッドのスリープ・インターバル及びアウェイク・インターバルの継続時間の値、ノードの数、平均データパケット生成率、ビジーチャネル及び衝突の確率を求めることができ、そのような閾値レベルは、実際的な観点から、最小のエネルギーレベルに十分に近い。設定された閾値を下回るエネルギーレベルをもたらす上記に示したクラスタヘッドのスリープ・インターバル及びアウェイク・インターバルの継続時間並びにその他のパラメータのこれらの値はまた、最低エネルギー条件を満たすものとみなされる。
【０１３４】
本願発明の有利な実施形態によれば、この最小化の問題は、５つの変数、即ち、クラスタ内の合計パケット生成率（即ち、平均データパケット生成率を乗じたノードの数）、衝突の確率及びビジーチャネル確率、遅延の制限及び信頼性の制限の多くの代表的な値について、例えばネットワークに接続された基地局によって、オフラインで解決される。こうすることより、ネットワークのノードは、込み入った計算をリアルタイムで実行するための複雑なハードウェアを必要としない。
【０１３５】
５つのパラメータの値並びに動作パラメータＲｌ及びＲｓの対応する事前に計算された最適値Ｒｌｏｐｔ及びＲｓｏｐｔは、ネットワークのクラスタヘッドノードのそれぞれに含まれる、図５に示すもののようなテーブルＴＢＬに格納される。
【０１３６】
図５のテーブルＴＢＬ（又は類似のテーブル）を使用する方法は、ネットワークのクラスタのうちの１つのクラスタヘッドノードに関連して、図６の流れ図を用いて説明される。
【０１３７】
クラスタヘッドノードを初期化する（例えば基地局によって実行され得る）際に、３つの変数、即ち、そのクラスタの合計パケット生成率Ｎλ、遅延がｔｍａｘ未満である所望の確率τｍａｘ、データパケットが伝送されるべき最小の所望の確率ψｍｉｎの値は、クラスタヘッドノードに格納される。また、クラスタヘッドノードの動作パラメータは、例えばデフォルト値に設定される。クラスタヘッドノードはその隣接するノードからビジーチャネル確率の推定値を受信し、その平均を計算する（ステップ６０１）。クラスタヘッドは衝突の確率を推定する（ステップ６０２）。３つの変数の値、計算されたビジーチャネルの平均確率及び推定された衝突の確率を入口点として使用して、クラスタのエネルギー消費を最小化する最適値Ｒｌｏｐｔ及びＲｓｏｐｔに対応するＲｌ及びＲｓの２つの値がテーブルＴＢＬから読み取られ（ステップ６０３）、以前の動作パラメータと置き換わるクラスタヘッドノードの新しい動作パラメータとして設定される（ステップ６０４）。その後、クラスタヘッドノードは、本方法のステップを繰り返す前に、しばらくの間待つ（ステップ６０５）。
【図１】
0005175398.tif 000029
【図２】
0005175398.tif 000030
【図３】
0005175398.tif 000031
【図４】
0005175398.tif 000032
【図５】
0005175398.tif 000033
【図６】
0005175398.tif 000034