JP4394699B2 - データの送信を制御する方法および装置 - Google Patents

Description

本発明は、ワイヤレスネットワークの分野、具体的にはワイヤレスセンサネットワーク（ＷＳＮ）の分野に関する。

ワイヤレスセンサネットワーク（ＷＳＮｓ）は、環境内に深く組み込まれ、リソースが非常に限られている、ＲＦ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ：無線周波数）通信機能を有する数多くのノードから構成される。ＷＳＮノードは通常、小型のバッテリを電源としているため、エネルギーは最も重要なリソースである。ネットワークまたはシステムの寿命を最大化するには、プロトコルが、エネルギー消費量を削減できるようにうまく最適化されるとともに、外部パラメータの変化に適応できることが不可欠である。

トポロジーが静的であるとともにトラフィック負荷が予測可能なＷＳＮにおけるエネルギー効率は、通常、ノードが通信していないときはそのノードをスリープモードに設定してアイドルリスニングとオーバヒアリングとによるエネルギー消費を抑制するＴＤＭＡ（Ｔｉｍｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ：時分割多元接続）に基づいたスキームを用いることで最良のものとすることができる。送信元から送信先までのルートの選択も、いくつかのノードのデプリーションとそれによる接続の中断とを避けることにより、エネルギー消費量を最小化できる。

非特許文献９に記載されているように、ＷＳＮに対していくつかのルーティングおよびメディアアクセスコントロール（ＭＡＣ）プロトコルが提案されている。スループットと遅延時間について最適化する従来のネットワークとは異なり、ＷＳＮはネットワーク寿命を最大化するために主にエネルギー消費について最適化されなければならない。ノードがチャネルをアイドルリスニングしているときに相当量のエネルギーを浪費することから、最も効率的なスキームは、小さいデューティサイクルを有し、ノードをできる限り長くスリープ状態に保つものである。非特許文献６では、ＷＳＮに対して最も関連のあるＭＡＣを調べている。ＴＤＭＡに基づいたＭＡＣは、アイドルリスニングとオーバヒアリングとコリジョンとを最小化する。それゆえ、かなりのエネルギー節約を可能になり、特に、トポロジーが静的でトラフィックのパターンが予測可能なＷＳＮにおける信頼性が改善される。しかしながら、時間に基づくノードスケジューリングは、ノードの同期によるオーバヘッドとスケジュールの計算および配信とをもたらす。この理由により、ＴＤＭＡ ＭＡＣスケジューリングは通常、ネットワーククラスタ内で適用され、クラスタヘッドによって管理される。コリジョンベースのＭＡＣは、負荷の予測が不可能であってトラフィックが小さい動的なネットワークに適している。非特許文献１１に記載されているＳ−ＭＡＣおよび非特許文献２に記載されているＤＭＡＣなどのプロトコルは、ハイブリッドなソリューションを提供する。それによれば、コンテンションに基づくプロトコルのアイドルリスニングの時間は、ノードの同期を取ることとデューティサイクリングを適用することとによって短縮できる。

ＴＤＭＡベースのスケジュールは、通常、全てのソースノードをデータシンク（ｄａｔａ ｓｉｎｋ）へと接続するパスによって定義されるコンバージキャストツリー（ｃｏｎｖｅｒｇｅｃａｓｔ ｔｒｅｅ）をトラバースし、データ配信におけるエネルギー消費量と遅延を最小化するようにタイムスロットを割り当てることによって計算される。非特許文献１によれば、コンバージキャストツリーはノード間の距離のみを考慮に入れて定義され、スケジュールはデータ配信の時間に関して最適化される。遅延は非特許文献１３においても主要な最適化の対象である。この文献では、各ノードで生成されたパケットが宛先に到達する間にスロットの最短長コンフリクトフリー割り当て（ｓｍａｌｌｅｓｔ ｌｅｎｇｔｈ ｃｏｎｆｌｉｃｔ−ｆｒｅｅ ａｓｓｉｇｎｍｅｎｔ）を見つけるという課題に取り組んでいる。非特許文献３では、最短パスＤＩＪＫＳＴＲＡアルゴリズムを適用するとともに、ノードのエネルギーとロケーションと遅延とを考慮した目的関数を使用することで、定期的にパスが計算されている。次に、各タイムスロットが同時に１つの送信リンクへと割り当てられるＢＦＳ（ｂｒｅａｄｔｈ ｆｉｒｓｔ ｓｅａｒｃｈ）方式またはＤＦＳ（ｄｅｐｔｈ ｆｉｒｓｔ ｓｅａｒｃｈ）方式により、スロットがノードへと割り当てられる。非特許文献１０では、全てのノードが同種のデータを測定するシナリオに対する、データを中心とするルーティングのソリューションが定義されている。このときルートはデータの集約が可能になるように選択される。

非特許文献１２に記載されている自己安定化静的スケジューリング（Ｓｅｌｆ−ｓｔａｂｉｌｉｚｉｎｇ ｓｔａｔｉｃ ｓｃｈｅｄｕｌｉｎｇ）は、長方形または六角形のグリッドトポロジーを有するＷＳＮとネットワークの全寿命とに対して固定的なスケジュールを定義する。このアプローチの限界は、特定のレギュラートポロジーのみを対象としており、ネットワーク稼働中のノードのエネルギーレベルの変化に基づいてスケジュールを更新しないという点にある。非特許文献４では、リニアプログラミングを用いてルーティングおよびＭＡＣプロトコルをともに最適化し、ルーティングの要件に基づいて可変長のスロットが定義されている。

Ｖ．Ａｎｎａｍａｌａｉ， Ｓ． Ｇｕｐｔａ ａｎｄ Ｌ．Ｓｃｈｗｉｅｂｅｒｔ， 「Ｏｎ Ｔｒｅｅ−Ｂａｓｅｄ Ｃｏｎｖｅｒｇｅｃａｓｔｉｎｇ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ」， ＩＥＥＥ Ｗｉｒｅｌｅｓｓ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ Ｃｏｎｆｅｒｅｎｃｅ， ２００３． ＷＣＮＣ ２００３ Ｇ． Ｌｕ， Ｂ． Ｋｒｉｓｈｎａｍａｃｈａｒｉ， Ｃ． Ｒａｇｈａｖｅｎｄｒａ 「Ａｎ ａｄａｐｔｉｖｅ ｅｎｅｒｇｙ−ｅｆｆｉｃｉｅｎｔ ａｎｄ ｌｏｗ ｌａｔｅｎｃｙ ＭＡＣ ｆｏｒ ｄａｔａ Ｇａｔｈｅｒｉｎｇ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ」， １８ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｐａｒａｌｌｅｌ ａｎｄ Ｄｉｓｔｒｉｂｕｔｅｄ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｍｐｏｓｉｕｍ （ＩＰＤＰＳ’０４） Ｋ． Ａｒｉｓｈａ， Ｍ． Ｙｏｕｎｉｓ， Ｍ． Ｙｏｕｓｓｅｆ． Ｅｎｅｒｇｙ−Ａｗａｒｅ ＴＤＭＡ−Ｂａｓｅｄ ＭＡＣ ｆｏｒ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ． Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｉｎｔｅｇｒａｔｅｄ Ｍａｎａｇｅｍｅｎｔ ｏｆ Ｐｏｗｅｒ Ａｗａｒｅ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ｃｏｍｐｕｔｉｎｇ ａｎｄ Ｎｅｔｗｏｒｋｉｎｇ （ＩＭＰＡＣＣＴ ２００２） Ｗ． Ｈｅｉｎｚｅｌｍａｎｎ， Ａ． Ｃｈａｎｄｒａｋａｓａｎ， Ｈ． Ｂａｌａｋｒｉｓｈｎａｎ 「Ｅｎｅｒｇｙ−ｅｆｆｉｃｉｅｎｔ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｐｒｏｔｏｃｏｌｓ ｆｏｒ ｗｉｒｅｌｅｓｓ ｍｉｃｒｏｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ」， Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ Ｈａｗａｉｉ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｓｙｓｔｅｍ Ｓｃｉｅｎｃｅｓ， Ｊａｎ ２０００ Ｋ． Ｒｏｍｅｒ， Ｐ． Ｂｌｕｍ， Ｌ． Ｍｅｉｅｒ， 「Ｔｉｍｅ Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ ａｎｄ Ｃａｌｉｂｒａｔｉｏｎ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ」， Ｈａｎｄｂｏｏｋ ｏｎ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ： Ａｌｇｏｒｉｔｈｍｓ ａｎｄ Ａｒｃｈｉｔｅｃｔｕｒｅｓ， Ｊｏｈｎ Ｗｉｌｅｙ， Ｓｅｐｔ ２００５ Ｋ． Ｌａｎｇｅｎｄｏｅｎ ａｎｄ Ｇ． Ｈａｌｋｅｓ： Ｅｎｅｒｇｙ−Ｅｆｆｉｃｉｅｎｔ Ｍｅｄｉｕｍ Ａｃｃｅｓｓ Ｃｏｎｔｒｏｌ Ｂｏｏｋ ｃｈａｐｔｅｒ ｉｎ ｔｈｅ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ Ｈａｎｄｂｏｏｋ， Ｒ． Ｚｕｒａｗｓｋｉ （ｅｄｉｔｏｒ）， ＣＲＣ ｐｒｅｓｓ， Ａｕｇｕｓｔ ２００５ Ｔ． Ｃｏｒｍｅｎ， Ｃ． Ｌｅｉｓｅｒｓｏｎ， Ｒ． Ｒｉｖｅｓｔ． Ｉｎｔｒｏｄｕｃｔｉｏｎ ｔｏ Ａｌｇｏｒｉｔｈｍｓ． Ｍｃ Ｇｒａｗ Ｈｉｌｌ， １９９０ Ｉ． Ａｋｙｉｌｄｉｚ， Ｗ． Ｓｕ， Ｗ． Ｓｎａｋｒａｓｕｂｒａｍａｎｉａｍ， Ｅ． Ｃａｙｉｒｃｉ． Ａ Ｓｕｒｖｅｙ ｏｎ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ」， ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ａｕｇ． ２００２ Ｉ． Ａｋｙｉｌｄｉｚ， Ｗ． Ｓｕ， Ｗ． Ｓｎａｋｒａｓｕｂｒａｍａｎｉａｍ， Ｅ． Ｃａｙｉｒｃｉ． Ａ Ｓｕｒｖｅｙ ｏｎ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ． ＩＥＥＥ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， Ａｕｇ．２００２ Ｙｅ， Ｊ． Ｈｅｉｄｅｍａｎｎ， Ｄ． Ｅｓｔｒｉｎ， 「Ａｎ Ｅｎｅｒｇｙ−ｅｆｆｉｃｉｅｎｔ ＭＡＣ Ｐｒｏｔｏｃｏｌ ｆｏｒ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ」， ＩＮＦＯＣＯＭ ２００２ Ｙｅ， Ｊ． Ｈｅｉｄｅｍａｎｎ， Ｄ． Ｅｓｔｒｉｎ， 「Ａｎ Ｅｎｅｒｇｙ−ｅｆｆｉｃｉｅｎｔ ＭＡＣ Ｐｒｏｔｏｃｏｌ ｆｏｒ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ」， ＩＮＦＯＣＯＭ ２００２ Ｓ． Ｋｕｌｋａｒｎｉ， Ｍ． Ａｒｕｍｕｇａｍ， 「ＴＤＭＡ Ｓｅｒｖｉｃｅ ｆｏｒ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ」， ＩＣＤＣＳ Ｗｏｒｋｓｈｏｐｓ ２００４ Ｓ． Ｃｏｌｅｒｉ． Ｐｅｄａｍａｃｓ： 「Ｐｏｗｅｒ Ｅｆｆｉｃｉｅｎｔ ａｎｄ Ｄｅｌａｙ Ａｗａｒｅ Ｍｅｄｉｕｍ Ａｃｃｅｓｓ Ｐｒｏｔｏｃｏｌ ｆｏｒ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ」， Ｍ．Ｓ． Ｔｈｅｓｉｓ， ＵＣ Ｂｅｒｋｅｌｅｙ， Ｄｅｃ ２００２

以上のことをまとめると、非特許文献３に記載の周知のアプローチは、最短パスアルゴリズムにより各ノードのエネルギーレベルに基づいて、各ノードに対して個別に、各ノードからデータシンクまでのルートを最適化し、各データを各ノードから個別にデータシンクへと送信するものであるか、または非特許文献１０は、集約の可能性を最適化することに基づいて各ノードからデータシンクまでのルートのみを最適化するものであると言える。従って、これらソリューションはエネルギー消費量を削減するものの、特定のノードのデプリーションをもたらす。これは特に非特許文献１０に記載のアプローチに当てはまる。

そこで本発明の目的は、特定のノードの「早期の」デプリーションを回避するとともに、ネットワークの寿命を長くするために、マルチホップネットワークにおけるデータ送信のルーティングまたはスケジューリングのうちのいずれかまたは両方を最適化するための改良された方法および装置を提供することにある。

上記目的は、請求項１〜１１に記載のデータの送信を制御する方法と、請求項１２に記載のコンピュータプログラムと、請求項１３に記載のデータの送信を制御する装置とにより達成できる。

本発明は、あるネットワーク内で複数のセンサノードからモニタノードへのデータの送信を制御する方法であって、前記センサノードと前記モニタノードとを頂点とするグラフを生成するステップであって、前記グラフのエッジは、各ノード間の距離に基づいてセンサノードのペアを互いに接続するか、またはセンサノードを前記モニタノードへ接続するものである、ステップと、前記センサノードごとに、関連するエネルギーレベルまたはエネルギー消費量を取得するステップと、前記エネルギーレベルまたは前記エネルギー消費量と同じデータタイプのデータの集約の可能性とに応じて、前記グラフの各エッジにウェイトを割り当てるステップであって、あるセンサノードのエネルギーレベルが高くなるほどまたはエネルギー消費量が小さくなるほどおよびデータ集約の可能性が高くなるほど、ルーティングツリーを定義するステップにおいて該センサノードに接続されたエッジを選択する確率を高めるウェイトが割当てられるものである、ステップと、前記センサノードごとに、前記センサノードから前記モニタノードへと前記データを送信するためのルートを含むルーティングツリーを定義するステップであって、前記ルーティングツリーの全体のウェイトは、より小さいウェイトが選択の確率が高いことを示す場合には最小化され、より大きいウェイトが選択の確率が高いことを示す場合には最大化されるものである、ステップと、前記複数のセンサノードと前記モニタノードとに対し前記ルートを割り当てるステップとを含む方法を提供する。

さらに本発明は、あるネットワーク内で複数のセンサノードからモニタノードへのデータの送信を制御する方法であって、前記複数のセンサノードのうちの各ノードと前記モニタノードとに対して、前記データを送信または受信するためのスケジュールを定義するステップであって、前記ネットワークのルーティングツリーに基づいているとともに、同じデータタイプのデータの集約の可能性を考慮し、その結果前記センサノードが前記ルーティングツリーに基づいてそれ自体が測定する同じデータタイプのデータを受信するか、または同じデータタイプのデータを２つ以上受信する場合に、前記データタイプのうちの１つのデータのみを考慮することになる、ステップを含む方法を提供する。

本発明は、あるネットワーク内で複数のセンサノードからモニタノードへのデータの送信を制御する装置であって、前記センサノードと前記モニタノードとを頂点とするグラフを生成する手段であって、前記グラフのエッジは、各ノード間の距離に基づいてセンサノードのペアを互いに接続するか、またはセンサノードを前記モニタノードへ接続するものである、手段と、前記センサノードごとに、関連するエネルギーレベルまたはエネルギー消費量を取得する手段と、前記エネルギーレベルまたは前記エネルギー消費量と同じデータタイプのデータの集約の可能性とに応じて、前記グラフの各エッジにウェイトを割り当てる手段であって、あるセンサノードのエネルギーレベルが高くなるほどまたはエネルギー消費量が小さくなるほどおよびデータ集約の可能性が高くなるほど、ルーティングツリーを定義するステップにおいて該センサノードに接続されたエッジを選択する確率を高めるウェイトが割当てられるものである、手段と、前記センサノードごとに、前記センサノードから前記モニタノードへと前記データを送信するためのルートを含むルーティングツリーを定義する手段であって、前記ルーティングツリーの全体のウェイトは、より小さいウェイトが選択の確率が高いことを示す場合には最小化され、より大きいウェイトが選択の確率が高いことを示す場合には最大化されるものである、手段と、前記複数のセンサノードと前記モニタノードとに対し前記ルートを割り当てる手段とを備える装置を提供する。

本発明は、データシンクが各データを個別に必要としないためにデータの集約が可能なネットワークにおいて、データを集約することにより、送信するデータ量を減らすことができるとともに、ネットワーク全体の電力消費量、特に、他のノードからデータを受信して送信するノード、すなわちホップとして機能するノードであって、リレーまたはハブとも呼ばれるノードの電力消費量を減らすことができるという所見に基づいている。

従って、エネルギーレベルまたはエネルギー消費量と、例えば同じタイプのデータを集約する可能性とに基づいてルーティングを最適化する方法は、ネットワークの寿命を長くすることができる。

本発明は更に、スケジューリングが集約の可能性に基づくものである場合にネットワークの寿命を最適化できるという所見と、ノードのエネルギーレベルまたはエネルギー消費量といった下位層情報とデータタイプやデータ集約の可能性といった上位層情報とに基づいてルーティングおよびスケジューリングをともに最適化できる場合にネットワークの寿命をさらに最適化できるという所見とに基づいている。

本発明の一実施形態によれば、センサノードのエネルギーレベルまたはエネルギー消費量のうちのいずれかまたは両方とデータタイプとに基づいて、またはもっと具体的には同じデータタイプのデータを集約する可能性に基づいて、ルーティングを最適化する方法が提供される。本発明のこのような実施形態は、送信するデータの量を減らすとともに個々のノードとネットワーク全体との電力消費量を削減する。

本発明の好ましい形態によれば、ロードバランシングスキームを提供するため、すなわち他のノードと比べてすでにエネルギーレベルが低いノードをホップとして使用することを回避または軽減するため、および／または、ノードの追加もしくは消滅またはノードの位置の変更に応じてルーティングを適応化するために、ルーティングを定期的に繰り返す。

本発明の別の形態によれば、スケジューリング、すなわちデータ集約の可能性に基づくノードおよび送信リンクへのタイムスロットの割り当てが最適化される。センサノード自体が同じデータタイプと測定したデータを受信するか、または異なるノードから同じデータタイプのデータを受信するセンサノードは、好ましくは、最初に同じデータタイプのデータを全て受信し、これらデータを１つのデータに集約して、この「集約された」データを送信するだけとなるようにスケジュールされる。通常、データの集約は個々のデータを送信するよりも小さい電力消費量で済むため、これらホップの電力消費量は削減される。同時に、データを送信するのに必要なタイムスロット数を減らし、従って全てのノードからモニタノードに向けて全てのデータを送信するのに必要な全体の送信時間を短縮することが可能となる。

本発明は、データの送信を制御するための方法を更に提供する。ここで、データの送信は異なるレイヤのパラメータに基づいて最適化されたルート選択に基づいて行われ、および／または、データの送信は遅延を最小化しながらそれまでのステップで選択されたルートを用いる、最適化されたノードスケジューリングに基づいて行われる。

本発明に係るルーティングと本発明に係るスケジューリングとはともに、異なるデータタイプを測定するノードを有するネットワークと、全てが同じ種類のデータを測定するノードのみを有するネットワークとにおいて利用することができる。

本発明の好ましい形態によれば、送信を制御するための方法および装置はともに、主要なパラメータであるエネルギーレベルまたはエネルギー消費量と集約の可能性とに基づいてルーティングとスケジューリングとを最適化する。

以下、同じデータタイプのデータのみが集約される実施形態について説明するが、本発明に係るソリューションは、異なるタイプのデータの組み合わせ、すなわち集約に関心のあるネットワークにも利用できる。

更に本発明の好ましい形態によれば、異なるデータリンクが互いに干渉しない場合に、その異なるデータリンクを通してデータのパラレル送信またはオーバーラップ送信を可能にするスケジューリングが提供され、その結果、全てのノードからモニタノードへと全てのデータを送信する時間が更に短縮される。

好ましい形態によれば、ロードバランシングまたはネットワークもしくはネットワークパラメータの変化への適応のうちのいずれかまたは両方を実現するために、ルーティングまたはスケジューリングのうちのいずれかまたは両方を定期的に繰り返す。

以下、添付図面を参照して本発明の好ましい実施形態を詳細に説明する。不要な繰り返しを避けるために、文脈に応じて用語「ノード」は、センサノード、ホップノードまたはモニタリングノードのうちの少なくとも１つを指す。

図１Ａは、ルーティングを最適化する、データの送信を制御する本発明に係る方法であって、ステップＳ１〜Ｓ５を含む方法の一実施形態を示している。

ステップＳ１において、ネットワーク内のセンサノードとモニタノードとを頂点とするグラフが生成される。例えば座標または他のノードとの相対的な距離もしくは座標として提供される位置は、一般的に既知であるか、または前記センサノードによって送信されるものである。前記グラフのエッジは、ノード間の距離に基づいてセンサノードのペアを相互に接続するか、またはあるセンサノードを前記モニタノードへ接続する。例えば、ノード間の距離がある閾値より大きければ、エッジがグラフに与えられることはない。

ステップＳ２では、例えば、初期のエネルギーレベルに基づいて各ノードの電力消費量をモデル化するか、またはセンサノード自体により測定された実際のエネルギーレベルまたはエネルギー消費量を受信することにより、前記センサノードごとに関連するエネルギーレベルまたは関連するエネルギー消費量が得られる。

ステップＳ３では、前記エネルギーレベルまたは前記エネルギー消費量と、同じデータタイプのデータが集約される可能性とに応じて、前記グラフの各エッジに対しウェイトが割り当てられる。各センサノードがどのデータタイプを測定することができるかということは、例えば、既知（例えば寿命全体を通して固定的であるか、または所定のスケジュールで変わる）であるか、またはセンサノードから送られる（例えば最初に一回だけ、または定期的に更新される）。

あるセンサノードのエネルギーレベルが高いほどまたはエネルギー消費量が小さいほど、およびデータ集約の可能性が高いほど、ルーティングツリーを定義するステップにおいて、そのセンサノードに接続されているエッジを選択する確率が高まるように、ウェイトが割り当てられる。

ステップＳ４では、前記センサノードから前記モニタノードへと前記データを送信するためのルートを含むルーティングツリーが、そのルーティングツリーの全体のウェイトが最適化されるように前記センサノードごとに定義される。最適化には、例えば、最小化と最大化とがある。最小化の場合は、エッジのウェイトが小さいほど選択の確率が高くなり、最大化の場合は、エッジのウェイトが大きいほど選択の確率が高くなる。ルーティングツリーを定義するためのアルゴリズムには、最大スパニングツリー（ｍａｘｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅｅ：ＭＳＴ）アルゴリズム、または最短パスツリー（ｓｈｏｒｔｅｓｔ ｐａｔｈ ｔｒｅｅ：ＳＰＴ）アルゴリズムがある。ここで、最小スパニングツリー（ｍｉｎｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅｅ）アルゴリズムに基づいた最適化は、一般的に最短パスツリーアルゴリズムよりも良い結果をもたらす。これは、最短パスアルゴリズムはノードごとに個別に最適化されたルートを最適化するため、ツリーは集約の可能性を考慮して最適化されておらず、集約はむしろ様々な最短パスが最適化の後に１つのツリーに組み合わされただけの偶然の結果に過ぎないからである。

ステップＳ５では、最適化されたルーティングツリーのルートが、センサノードとモニタノードとへ送信される。この結果、各センサノードは、測定したデータまたは受信したデータをどのノード、すなわち他のセンサノード、ホップまたはモニタノードへ送信しなければならないかを認識する。

図１Ｂは、送信のスケジュールを最適化する、データの送信を制御するための本発明に係る方法の主要な特徴を示すチャートをＳ６として表している。

ステップＳ６において、ともにネットワークを形成する各センサノードとモニタノードとに対し、データを送信または受信するためのスケジュールが定義される。このステップは、前記ネットワークのルーティングツリーに基づいており、さらに同じデータタイプのデータが集約される可能性も考慮する。

データの集約は、多種多様な集約関数、例えば、最小関数（ｍｉｎｉｍｕｍ ｆｕｎｃｔｉｏｎ）、最大関数（ｍａｘｉｍｕｍ ｆｕｎｃｔｉｏｎ）、平均関数（ａｖｅｒａｇｅ ｆｕｎｃｔｉｏｎ）、合計関数（ＳＵＭ−ｆｕｎｃｔｉｏｎ）または論理関数に基づいて行うことができる。

一例として、ワイヤレスセンサを配備することができる場所として、「ルーブル美術館」または他の任意の美術館が挙げられる。ここでセンサは、絵画を保護するために複数のロケーションで湿度と温度とを測定する。

センサネットワークの目的が、いずれかのロケーションで温度がある閾値を下回っているかどうか、またはいずれかのロケーションで湿度がある閾値を上回っているかどうかをモニタすることである場合、センサノードは温度値を最大関数に基づいて集約し、湿度値を最小関数に基づいて集約する。別のシナリオでは、センサノードは温度を測定し、測定された温度値を温度の閾値と比較する。測定された温度値が温度閾値を下回っていれば「０」を送信し、測定された温度値が温度閾値を上回っていれば「１」を送信する。この場合、集約関数は論理関数ＯＲであり、従ってセンサの１つが温度閾値を上回る温度値を測定した場合に限り、アラームインジケータとして「１」を送信する。両方のケースとも、位置を特定するために測定値とともに追加的にノード識別子が送信される。

一般に、本発明に係る方法は集約関数には依存しない。集約を考慮できるということに関しては、例えば同じデータタイプといったような条件だけがわかればよい。このとき、前記ルーティングツリーに基づいて、センサ自体が測定するデータのうち同じデータタイプのデータを受信するか、または他のセンサノードから同じデータを２つ以上受信する場合、前記データタイプのデータのうち１つを送信することのみが集約ノードに対してスケジュールされるとともに、この特定のデータタイプのデータを送信する前に、この特定のデータタイプの全てのデータを、最初に集約ノードの当該ブランチ内にある他のセンサノードから受信し、その集約ノードによって集約する必要があるものとなるように、データの集約が考慮される。集約ノードはセンサノードまたはホップであってもよい。

次に、センサネットワーク内のルーティングとスケジューリングとをともに最適化する本発明の好ましい実施形態についてさらに詳しく議論する。言い換えると、この実施形態は、図１Ａと図１Ｂに示されている一連のステップＳ１〜Ｓ６に基づいている。さらに注目すべきことに、この好ましい実施形態に基づいて説明するルーティングとスケジューリングとに関して開示する詳細は、ルーティングを制御するための本発明に係る方法またはスケジューリングを制御するための本発明に係る方法の実施形態にも別々に適用することができる。

静的なトポロジーまたはほぼ静的なトポロジーを有するワイヤレスセンサネットワークのエネルギー消費量を最適化するために、本発明の実施の好ましい形態は、最適なルートと最適なノードスケジュールとをともに選択するアルゴリズムに基づいている。その結果、ルートは、アウェイク期間がオーバーラップまたは並行し、しかも送信（Ｔｘ）期間および受信（Ｒｘ）期間が揃った一連のノードによって定められる。

図２Ａは、クロスレイヤネットワークアーキテクチャを視覚的に示している。このアーキテクチャは、アプリケーション層に基づくデータタイプおよびノードのロケーションなどのパラメータと、物理層に基づく送信レンジおよびノードエネルギーレベルなどのパラメータとを考慮に入れて、最適なルート（ネットワーク層）と最適なノードスケジュール（ＭＡＣ層）とをともに見いだすコンポーネントを含んでいる。

このアルゴリズムの出力は、ノードがどのスロットでパケットを送受信するかということと、暗示的にセンサからモニタへのルートとを規定するスケジュールである。このアルゴリズムは一般的に、十分なエネルギーと計算能力を有するノード内で実行される。多くの場合、このノードはモニタであって、これはセンサから全てのデータを収集するための大きいエネルギーを持たなくてはならないとともに、ノードのエネルギーレベルまたはロケーションに関する最新情報もそれらノードからサイド情報として取得することができる。一度計算するとスケジュールは、ＷＳＮ内の全てのノードへブロードキャストされる。

スケジュールは２つのステップで計算される。最初のルート選択（ｒｏｕｔｅ ｓｅｌｅｃｔｉｏｎ：ＲＳ）のステップでは、各センサノードからモニタへのルートが特定される。次のノードスケジューリング（ｎｏｄｅ ｓｃｈｅｄｕｌｉｎｇ：ＮＳ）のステップでは、それまでのステップで特定されたルートが採用される。

ネットワークの寿命を最大化するには、ノードごとのエネルギー消費量を最小化するだけでなく、ネットワークにおいて良好なロードバランシングを維持することが必要である。最大のエネルギーレベルを有するノードを通してルートが維持されるように、ルート選択（ＲＳ）またはノードスケジューリング（ＮＳ）を定期的に繰り返すことにより、ロードバランシングが行われる。さらに、ＲＳまたはＮＳを定期的に繰り返すことで、例えばノードのモビリティによるネットワークトポロジーの変化にスケジュールを適応させることができる。図２Ｂは、ルート選択（ＲＳ）とノードスケジューリング（ＮＳ）との定期的な反復を示している。

以下、次のような定義を用いる。タイムスロットは、ノードがパケットを送受信するようスケジュールすることができる間隔である。データ配信（ｄａｔａ ｄｅｌｉｖｅｒｙ：ＤＤ）期間は、その期間の開始時点において送信すべきデータパケットを有する全てのセンサノードがそのデータパケットをモニタノードへと送信するのに必要な時間間隔である。ラウンドは、ＲＳアルゴリズムまたはＮＳアルゴリズムの２つの実行の間の時間間隔である。図２Ｃに示されているように、各ラウンドは、ノードが同じスケジュールに従うデータ配信期間をいくつか含んでいる。

図２Ｃは、ルート選択またはノードスケジューリングのラウンドを示している。ラウンドＲ１には、ｎ個のデータ配信期間としてＤＤ期間１、ＤＤ期間２、・・・、ＤＤ期間ｎと、それらの間のアイドル期間とが存在する。

ルート選択またはノードスケジューリングのアプローチを適用できる範囲は、ノードの時間的な同期とスケジュールの計算および配信とに起因するオーバヘッドによって制限される。非特許文献５には、ワイヤレスセンサノードの同期についての技術が概説されており、精度およびオーバヘッドの観点からそれら技術を比較している。スケジュールの計算および配信に関しては、ノードから動的情報、例えばそれらノードのエネルギーレベルまたはロケーション情報を取得し、ノードスケジュールを計算してそのスケジュールを各ノードに配信するのに十分なエネルギーを有するノードがネットワーク内にあるものとする。クラスタ化されたアーキテクチャでは、スケジューリングのタスクはクラスタヘッドに分割され、各クラスタヘッドはそのクラスタ内にあるノードのスケジュールを計算する。

本発明は、例えば、ネットワークを運営するネットワークオペレータにとって利点がある。というのも、本発明によれば、トポロジーが静的またはほぼ静的なワイヤレスセンサネットワークのネットワーク寿命が長くなり、その結果、新しいサービスが可能になるからである。

次に、以下の特徴を有するワイヤレスセンサネットワークに基づく本発明の好ましい実施形態について説明する。ほとんどのノードは、環境のパラメータを測定することができるセンサ（データソース）を有している。センサを持たないノードはホップとしてのみ機能し、他のノードから受信したデータを再送信する。各ノードは特定のパラメータを測定するただ一つのセンサを有している。ＷＳＮにおいて、異なるノードが異なるパラメータまたは異なるデータタイプのデータを測定するセンサを備えることができる（図３に明示的に示されている）。暗円３１０は、第１のタイプのデータを測定するセンサノードを表し、白円３２０は、第２のタイプのデータを測定するセンサノードを表し、中に×印が入った円３３０は、第３のタイプのデータを測定するセンサノードを表している。「Ｍ」という印の入った円はモニタノードを表している。異なるデータタイプのデータを測定するノードに対するこれらの定義は、これ以降の図面でも適用する。同じタイプのセンサによって測定されたデータを集約することができる。近傍で感知された同じタイプのパラメータを集約することができる。適用する集約関数のタイプ（例えば、最大、平均など）についての仮定は一切行わない。各センサノードは測定したデータを集約し、送信がスケジュールされるたびにデータユニットだけを有している。データユニットはタイムスロット内に収まるものであり、それらは全て同じ継続時間を有している。残りのノードはモニタリングノード、モニタまたはシンクと呼ばれ、全てのセンサからデータを収集してそのクラスタ内にあるノードに対してスケジュールを計算するのに十分な計算能力を有している。ノードはネットワークの稼働中は固定されているか、または、ＲＳもしくはＮＳのアプリケーション速度よりずっと低い速度で位置を変える。ノードのロケーションについてはモニタが事前にしかも十分な精度で認識しているものとする。各ノードは、送信状態、受信状態またはスリープ状態のいずれかの状態にある。ノードは時間で同期化される。非特許文献５に記載されているように、ＲＢＳなどの技術は１０マイクロ秒のオーダーで同期の精度を実現することができる。ノードのエネルギーレベルは稼働中に変化し、計算および通信の実行により低下する。エネルギーは稼働中に外部のソースからも供給を受けることができる。モニタはそのタスクを実行するのに十分なエネルギーを有している。

ノードのエネルギー消費量は、非特許文献７に基づく以下のモデルを使用して計算される。
・受信： Ｎ_RX＊Ｅ₁， Ｅ₁＝１３５ｎＪ／ｂｉｔ
・送信： Ｎ_TX＊（Ｅ₂₁＋（ｄⁿ）＊Ｅ₂₂）， Ｅ₂₁＝４５ｎＪ／ｂｉｔ， Ｅ₂₂＝１０ｐＪ／ｂｉｔ／ｍ²（ｎ＝２）
・センシング： Ｅ₃＝５０ｎＪ／ｂｉｔ
・処理： Ｎ_agg＊Ｅ₄， Ｅ₄＝１０ｎＪ／ｂｉｔ
・スリープ状態： Ｎ_sleep＊Ｅ₅， Ｅ₅＝１．９８ｎＪ／ｂｉｔ
ここで、Ｎ_RXはノードに割り当てられている受信タイムスロットの数であり、Ｎ_TXはノードに割り当てられている送信タイムスロットの数であり、Ｎ_aggは集約されたストリームの数であり、ｎはパスロス係数であり、ｄはノード間の距離であり、Ｎ_sleepはスリープモードにあるスロットの数である。

ルート選択は、ウェイトの付いたグラフの最小スパニングツリー（Ｍｉｎｉｍｕｍ Ｓｐａｎｎｉｎｇ Ｔｒｅｅ：ＭＳＴ）を計算することにより、全てのソースノードからモニタへの、エネルギーについて最適化されたルートを見出す。グラフのウェイトは、図４Ａに示されているように、ノード間の距離４１０と、測定されるパラメータのタイプ４２０と、ノードのエネルギーレベル４３０と、エネルギー消費の履歴と、モニタへの接続性４５０とを考慮に入れて定義される。ノード間のトラフィックロードの均等な分散を実現するために、それまでのラウンドにおけるエネルギー消費量が考慮される。非特許文献８に記載されているように、重み付けのなされたグラフが与えられると、ＭＳＴは、最小のウェイトを有し、ネットワーク内の全てのノードを接続するツリーを計算する。最短パスアルゴリズムと比較して、ＭＳＴは、モニタからノードへの両端距離を最小化するのではなく、ノードからそれらの近傍にあるノードへの最良のローカルな接続を実現するためにウェイトの小さいエッジを優先的に選択する。このため、ＭＳＴはデータ集約の機会を利用するのに特に適している。

図４Ｂは、本発明に係るルート選択の一例を示している。この図は、ルート選択（ＲＳ）アルゴリズムのルート選択ステップＲＳ１〜ＲＳ４を明示的に示している。ステップＲＳ１では、ラベル付けされたグラフＧが定義される。Ｇは（Ｎ，Ｅ，Ｐ，ＥＮ）の組み合わせである。ここでＮはノードの集合であり、Ｅはエッジの集合である。ここで、ノードｎ_iとｎ_jとの間の距離ｄ_ij＜ＴＲであるならば、∀ｎ_i，ｎ_j∈Ｎに対してｅ_ij∈Ｅとなるように定義される。ＴＲは、ノードの最大送信レンジ（１００メートル）である。Ｐは、ノードとこれらノードが測定するパラメータのタイプとを関連付ける関数（ｎ_iがホップであればＰ（ｎ_i）＝ｎｕｌｌであり、ｎ_iがモニタであればＰ（ｎ_i）＝Ｍ）である。ＥＮは、各ノードをそのエネルギーレベルと関連付ける関数である。

ステップＲＳ２では、次のような関数に基づく、ノードｉとノードｊとの間の各エッジにウェイトｗ_ijを有する、重み付けのなされたグラフが定義される。

ここで、これら全てのパラメータは、０と１との間の正規化された（ｎｏｒｍａｌｉｚｅｄ）値を採る。さらに、Ｋ_EL、Ｋ_EC、Ｋ_ND、Ｋ_MDおよびＫ_AGは各パラメータの相対ウェイト（ｒｅｌａｔｉｖｅ ｗｅｉｇｈｔ）を決定する定数であり、以下相対ウェイトとも呼ぶ。

エネルギーレベル（ＥＬ）は、ノードのエネルギーレベルを表すものであり、いかのように定義される。

ここで、

はネットワークノードの平均エネルギーである。

エネルギー消費量（Ｅｎｅｒｇｙ Ｃｏｎｓｕｍｔｉｏｎ：ＥＣ）は、それまでのラウンドでノードが消費したエネルギーを表す。

ここで、

は、ネットワークノードがそれまでのラウンドで消費したエネルギーの平均である。

ノード間距離（Ｎｏｄｅ Ｄｉｓｔａｎｃｅ：ＮＤ）は、ＴＲで正規化された、ノードｉとノードｊとの間の距離、すなわちＮＤ_ij＝ｄ_ij／ＴＲである。

モニタ距離（Ｍｏｎｉｔｏｒ Ｄｉｓｔａｎｃｅ：ＭＤ）は、モニタノードからノードまでの距離である。この係数は、可能であればいつでもモニタへのダイレクトリンクを介しての通信、またはモニタに直接接続されたノードを介しての通信を促すために用いられる（図５参照）。

図５は、モニタ距離の例示的なケースを３つ示している。１つ目の例では、センサノードＡとセンサノードＢとは、モニタノードＭのレンジ内に存在している。２つ目の例では、センサノードＡとセンサノードＢとは、ともにモニタノードＭのレンジ内に存在していない。３つ目の例では、センサノードＡのみがモニタノードＭのレンジ内に存在している。図５は、更にこれら３つのケースに対するそれぞれのモニタ距離（ＭＤ）の値も示している。

集約性（ＡＧ）は、同じタイプのパラメータを搬送するパケットをローカルに集約できる可能性であり、同じパラメータを測定するノードを接続するエッジの選択に有利に働く（図６参照）。

図６は、例示的な集約のケースを３つ示している。１つ目の例では、センサノードＡとセンサノードＢとは、同じパラメータまたは同じデータタイプのデータを集約する。２つ目の例では、ノードＢはホップである。３つ目の例では、センサノードＡとセンサノードＢとは、異なるパラメータを測定する。図６にはそれぞれのケースの集約値（ＡＧ）も示されている。

ステップＲＳ３において最小スパニングツリー（ＭＳＴ）を計算するアルゴリズムについては、非特許文献７に記載されている。

最小スパニングツリー（ＭＳＴ）が与えられると、ステップＲＳ４において、Ｇ_Wに基づいて、モニタノードをルートとした（ｒｏｏｔｅｄ）有向ツリー（ｄｉｒｅｃｔｅｄ ｔｒｅｅ）が得られる。各ノード、すなわちホップまたはセンサノードのうちのいずれかまたは両方には、ルート（ｒｏｏｔ）からノードまでの距離として定義される深度（ｄｅｐｔｈ）が割り当てられる。

図７は、図４Ｂに基づく、ルーティングを制御するための本発明に係る方法の実施形態におけるステップを図示するグラフと結果的に得られるツリーとを示している。図７ａは、エッジがノードＡ〜Ｑを接続しており、Ｍがモニタリングノードであるグラフ定義後のラベル付きグラフＧを示している（ステップＲＳ１）。図７ｂは、グラフＧのエッジにウェイトｗ_ijが割り当てられた、ウェイト割り当て後の重み付きグラフＧ_Wを示している（ステップＲＳ２）。図７ｃは、ＭＳＴを計算した後に構成または選択された最小スパニングツリー（太い矢印）を示している（ステップＲＳ３）。図７ｄは、異なるブランチがセンサノードＡ〜Ｑを、ツリーのルートであるモニタリングノードＭへと接続している、コンバージキャストツリーを定義した後の有向ツリーを示している（ステップＲＳ４）。

次に、ノードスケジューリング（ＮＳ）についてさらに詳しく説明する。ルート選択（ＲＳ）によって計算されたツリーが与えられ、センサノードによって測定されるデータのタイプがわかると、ノードスケジューリング（ＮＳ）は、例えば、全てのノードについて時間的に同期が取れていると仮定して、ノードが送信モード、受信モードまたはスリープモードにあるタイムスロットを定義する。

アルゴリズムは、最初にリーフ、すなわちセンサノードＡ、Ｄ、Ｆ、Ｐ、Ｈ、ＬおよびＱからルートＭに向けてツリーまたはブランチのノードをトラバースし、ノードがセンサを有するかどうか、そしてデータが集約可能かどうかを考慮して、各ノードに割り当てられる送信スロットまたは受信スロットの数を決定する。続いて、ノード干渉を考慮に入れ、ソースノードからモニタリングノードまでの通信遅延を最小化するように、タイムスロットをノードに割り当てる。あるノードが２つ以上の子ノードから同じタイプのパラメータを搬送するパケットを受信する場合、またはそれ自体が測定する同じタイプのパラメータを搬送するパケットを受信する場合は、集約関数（例えば、平均、最大、最小）がデータパケットに適用され、その結果が１つのタイムスロットで送信される。

タイムスロットは、深度がより大きいノードから始めて、送信するべきデータを有するノードへと割り当てられる。ノードに送信タイムスロットが割り当てられると、そのタイムスロットカウンタｎＴｘと受信ノードの受信タイムスロットカウンタｎＲｘとは、１だけカウントが減じられる。同じタイムスロットは、互いに干渉しない場合に限り複数のノードへと割り当てることができる。本アルゴリズムは、あるタイムスロット中にスケジュールされたいくつかのノードの中から選ぶことができる場合に、データを長い時間バッファに保持している（最大バッファ遅延）ノードを選ぶことができる。

図８は、ノードスケジューリング（ＮＳ）アルゴリズムの一例を示している。ステップＮＳ１において、アルゴリズムは、ノードごとに送信スロット数（ｎＴｘ）と受信スロット数（ｎＲｘ）とを計算する。ステップＮＲ２において、タイムスロット値「ｔｉｍｅｓｌｏｔ」が初期化される。図８の例では「１」に初期化されている。次のステップで、第１のループＬ１から開始して、ｔｉｍｅｓｌｏｔ１から始まるタイムスロットが、異なるノード、すなわちセンサノード、ホップおよび／またはモニタリングノードへと（反復して）割り当てられる。このループＬ１は、送信すべきデータを有するノードが無くなるまで反復され、各反復の後に、全てのノードに対するバッファ遅延カウンタが更新され、タイムスロット値がインクリメントされる。第１のループＬ１内で、第２のループＬ２が実行される。このループＬ２はリーフから始まり、すなわち値「ｄｅｐｔｈ」を「ｄｅｐｔｈＭａｘ」に初期化し、送信すべきデータを有するノード（ｎＴｘ≠０）を反復してチェックし、各反復の最後に送信スロットカウンタ（ｎＴｘ）および受信スロットカウンタ（ｎＲｘ）と、バッファ遅延カウンタとを更新し、値ｄｅｐｔｈがデクリメントされる。最大バッファ遅延を有し、同じタイムスロットでアクティブな他のアクティブノードと干渉しないノードが選択される。２つのループＬ１およびＬ２を有する本実施形態において、各タイムスロットは、最大でただ１つの、同じｄｅｐｔｈを有する送信ノードへと割り当てられる。代わりに、第３のループＬ３を挿入することができる。このループＬ３は、同じｄｅｐｔｈを有するノードを反復してチェックするが、個々のバッファ遅延に基づいてタイムスロットの割り当ての優先順位を決める。

あるノードが別のノードと干渉しているかどうかの判定は、信号対ノイズ比（ＳＮＲ）の測定に基づくか、またはそれぞれのテーブル、例えばトポロジーが静的であって全てのノードの位置が固定されている場合には、全てのシナリオに対する干渉判定パラメータを含んでおり一度作成することができるそれぞれのテーブルに基づいて行うことができる。さらに、干渉に関する判定は、干渉する可能性のあるノードまたはリンクの間の距離に基づいて行うことができる。このときノードまたはリンクが互いに干渉するかどうかの判定は、距離閾値に基づいている。

次に、図８Ｂに示されているツリーの例に基づいて、図８Ａに基づくノードスケジューリングアルゴリズムを説明する。図８Ｂのａ）は、モニタリングノードＭを有するツリーと、異なるデータタイプのデータを測定するセンサノードとを示している。ここで、センサノード６、８および９は第１のタイプのデータを測定し、ノード３、４、７、１０、１１および１３は第２のタイプのデータを測定し、ノード１、２、５および１２は第３のデータタイプのデータを測定する。第１のステップでは、パケットによって搬送されるデータのタイプと集約の機会または可能性とが与えられたノードに対して、必要な送信スロットの数（ｎＴｘ）と受信スロットの数（ｎＲｘ）とを計算する。その結果、図８Ｂのｂ）に示されているツリーが得られる。図８Ｂのｂ）のツリー内の各ノードには、（ｎＴｘ，ｎＲｘ）（左側は送信スロット数ｎＴｘ、右側は受信スロット数ｎＲｘである）が付記されている。続いて送信と受信のためのスロットがノードへと割り当てられる。最初に、ノード１、３、４、５、６、８、９および１０は送信するデータを有している。ｄｅｐｔｈ＝ｄｅｐｔｈＭａｘ＝４から開始すると、ノード１には送信のためのｔｉｍｅｓｌｏｔ１が割り当てられ、ノード２には受信のためのｔｉｍｅｓｌｏｔ１が割り当てられ、そして対応するカウンタ（ｎＴｘ，ｎＲｘ）が更新される。ｔｉｍｅｓｌｏｔ１の割り当ては、図８Ｂのｂ）の「［１］」に示されている。続いて、アルゴリズムはｄｅｐｔｈ＝３に進み、ノード１および２と干渉せずに送信することができるノード、例えばノード５を選択する。ノード５とノード８との間の送信リンクへのｔｉｍｅｓｌｏｔ１の割り当ても、図８Ｂのｂ）の「［１］」に示されている。アルゴリズムは、全てのノードに対してｎＴｘ＝ｎＲｘ＝０となるまで反復する。

以下、本発明に係る方法のシミュレーション結果について説明および解析をする。

ＲＳアルゴリズムまたはＮＳアルゴリズムは、エネルギーレベルおよびエネルギー消費量とノード間距離とモニタ距離と集約性とを考慮して、ノードスケジュールを選択する。Ｃ＋＋シミュレーションを実行して、係数Ｋの最適な値の割り当てを特定するためにこれらパラメータの相対的な重要度を評価する。本シミュレーションは、３００×３００ｍ²の面積をカバーし、モニタノードが中心に配置されたネットワークに関するものである。ノードは割り当て量（ｂｕｄｇｅｔ）０．１Ｊで動作を開始する。

エネルギーレベル（ＥＬ）およびエネルギー消費量（ＥＣ）の役割は、ネットワーク寿命の最大化において不可欠である。図９ａは、正規化されたノード密度の様々な値について、ネットワーク内でノードが最初にエネルギーレベルヌルに到達する前の、係数Ｋ_elとラウンド数との関係を視覚的に示している。ラウンド数はＫ_elの増加とともにＫ_el＝５までは増加し、ノード密度が大きいほど大きくなる。これは、モニタまでの様々なパスを確立することができるとともに、モニタノードの近傍にある複数のノードに負荷を分散できるからである。しかしながら、ＥＬを考慮しないと（Ｋ_el＝０）、ルートは各ラウンドの最後に更新されず、ノード密度が大きいネットワークでは、いくつかのノードが多くのデータ量をホップしなければならないことから、それらノードは早期にデプリートする。

３〜５のレンジにある相対的なウェイトに対し、ネットワーク内でノードが最初にエネルギーレベル０に到達する前のラウンド数は、ノード密度が１０の場合と比較して２倍であるノード密度２０の場合、約２倍高い（ｆａｃｔｏｒ ７ ｈｉｇｈｅｒ）ことも図９ａ）からわかる。

図９ｂは最小エネルギーノード（５００ラウンド後、２８個のノードを有するネットワーク）が係数Ｋ_ecとともにどのように変化するかを示している。Ｋ_ec＜１０の場合、係数Ｋ_ecが増加するとともに増加し、係数Ｋ_ec＞１０の場合ＥＣは他のパラメータを左右するために減少する。

早期にエネルギー０に達するノードは、モニタリングノードの近傍に位置するノードである。これは、ツリー内で深度が大きいノードによって感知されたデータをホップしなければならないからである。図９ｃおよび図９ｄは、Ｋ_md＝２およびＫ_md＝０に対して、ネットワークでノードが最初にエネルギーレベル０に達する前のラウンド数が、正規化されたノード密度に対してどのように変化するかを視覚的に示している。図９ｃは、ノード密度が増加するにつれてモニタノードに近いノードが多くのデータを送信する必要があり、早期にエネルギー０に達することを示している。代わりに、図９ｄは、ＭＤを考慮しない場合（Ｋ_md＝０）、モニタノードに最も近いノードはもはや選ばれず、アルゴリズムはモニタへの代わりのルートを見つける。

集約性は、平均エネルギー消費量を最小化するだけでなくＤＤ期間の持続期間を短縮するための重要なパラメータである。図１０ａでは、Ｋ_ag＝０およびＫ_ag＝１０の場合の平均消費量を比較している。ＡＧを考慮する場合、平均エネルギー消費量は小さくなり、予想どおりであるが、ネットワークにおける感知パラメータの総数が減るにしたがって減少する。同様に、図１０ｂに示されているように、ＡＧのウェイトが増加するとＤＤ期間は短くなる。Ｋ_ag＝０とＫ_ag＝１０とに対応する曲線の差は、感知パラメータの数の増加に伴って大きくなることに注意しなければならない。これは、様々な感知パラメータの数が増加するにつれ、同じパラメータを感知するノードの少ないペアのリンクを特定するタスクに対してＡＧの考慮が有利に働くからである。図１０ｂは、Ｋ_ag＝１０の場合、パラメータの数が少なくなるにつれ、データ集約によりＤＤ期間が短くなることを示している。

ノード間距離（ＮＤ）は、エネルギーの観点に基づいて短距離のリンクを介した通信が、都合が良いことを考慮する。これは、長距離のリンクを可能にする、通信レンジの大きい値に対して特に当てはまる。この場合、ＮＤを考慮することで図１０ｃに示されているように良い最適化が可能になる。

次に、ネットワークをスケジュールするための本発明に係るアプローチを、スレッド型トポロジーにおいてノードが一定の間隔を置いて配置されているシナリオに適用する。図１１に示されているような、３つの異なるタイプのデータを測定するノードが存在する３つのケースについて議論する。図１１ａでは特定の順序がなく、図１１ｂでは同じパラメータまたは同じデータタイプのデータを感知するノードが同じ列に並んでおり、図１１ｃには同じパラメータを感知するノードが同じ行に並んでいる。さらに、図１２に示されているような２つのタイプのルートを議論する。便宜上、図１２ａに基づくルートを垂直ルート（ｖｅｒｔｉｃａｌ ｒｏｕｔｅ）と呼び、図１２ｂに基づくルートを水平ルート（ｈｏｒｉｚｏｎｔａｌ ｒｏｕｔｅｓ）と呼ぶ。

ルート選択（ＲＳ）アプローチまたはノードスケジューリング（ＮＳ）アプローチに基づいた送信を制御するための本発明に係る方法を、図１２ａおよび図１２ｂに示されている水平ルートおよび垂直ルートの静的な割り当てと比較する。全ての場合において、ＲＳまたはＮＳは、エネルギー０に到達する最初のノードの寿命を長くすることができる。これは、ＲＳまたはＮＳがエネルギーレベルの動的な変化を考慮し、いくつかのノードのエネルギーのデプリーションを避けるために異なるルートを定期的に計算するからである。図１３によれば、パラメータタイプが図１１ｂに示されているように分布するケース、つまり集約性（ＡＧ）によりＲＳまたはＮＳが垂直ルートを発見することができるケースを除いては、ＲＳまたはＮＳを使用する利点は明らかである。図１１ｃの分布の場合、静的に定義された水平ルートは、集約により図１１ａおよび図１１ｂの場合と比べて寿命を長くするが、エネルギーレベルの変化は考慮しておらず、そのためＲＳまたはＮＳよりも寿命が短くなる。ＲＳまたはＮＳは集約性とエネルギーの動的な変化との両方を考慮する。それゆえネットワークはロードバランシングを改善し、寿命を延ばすことが可能となる。

取り扱う問題は、上位層および下位層に基づく関連のあるパラメータ、例えば送信データのタイプ、ノードのロケーションおよびノードの現在のエネルギーレベルなどを考慮することによりネットワーク寿命を最大化するために、ネットワーク層とＭＡＣ層（Ｍｅｄｉｕｍ Ａｃｃｅｓｓ Ｌａｙｅｒ）との両方をいかに最適化するかということである。

ただ一つの特定のパラメータを測定するセンサを有するネットワークに関して本発明の好ましい実施形態の説明をしてきたが、本発明はセンサが２つ以上のデータタイプまたはパラメータを測定するセンサネットワークにも適用できることに注意されたい。この場合は、例えば送信スロット数ｎＴｘと受信スロット数ｎＲｘは適宜適応的でなければならない。

これまでの説明では同じデータタイプのデータに集約を適用しただけであったが、ネットワークオペレータの要望と関心のある情報とに応じて、異なるタイプのデータにも集約を適用できる場合があることに注意されたい。この場合、異なるデータタイプのこの種のデータは、特定の集約関数に基づいて集約することができ、「同じデータタイプのデータ」として理解すべきものである。ルーブル美術館の例で言えば、あるノードまたは様々なノードにあるセンサは、様々なロケーションで湿度と温度とを測定し、センサノードはこれら測定値を閾値と比較し、集約関数は「低すぎる湿度」と「高すぎる温度」とに対するアラームを１つのアラームに集約することができる。

さらに、本発明は、１つの周波数帯域にあるタイムスロットを使用するだけでなく、異なる周波数帯域で同じタイムスロットに基づいて同時に送信することができるように異なる周波数帯域にあるタイムスロットを使用できるよう拡張することができる。こうすれば、データ配信期間をさらに短縮することができる。本発明に係るスケジューリング方法は、例えば周波数帯域ごとに別のループを加えることによって容易に適用することができる。

次に、図１４Ａと図１４Ｂとに基づいて、本発明の更なる利用例を説明する。図１４Ａはゴルフコースを示している。ここで、ワイヤレスセンサネットワークは、ゴルフボールの位置の特定、コースマップの視覚化、安全警報、環境のモニタリング、プロフィールおよびゲームの助言、またはコーススケジュールの管理に利用することができる。

図１４Ｂは駐車場のシナリオを示している。ここで、ワイヤレスセンサネットワークは、駐車場が空いているかどうかの問い合わせ、選択された駐車区画への方向の指示、駐車料金の支払い、チケットの管理または駐車場の予約に利用することができる。

以上のことをまとめると、ワイヤレスセンサネットワークは、環境内に深く組み込まれ、リソースが非常に限られている、ＲＦ通信機能を有する数多くのノードから構成されている。ＷＳＮノードは通常、小型のバッテリを電源としているため、エネルギーは最も重要なリソースである。ネットワークの寿命を最大化するには、プロトコルがエネルギー消費量を削減できるように完全に最適化されるとともに外部パラメータの変化に適応していることが不可欠である。本発明は、ワイヤレスネットワーク内のノード間の通信プロトコルを最適化してエネルギー消費量を最小化する方法および装置を提供する。本発明に係る方法および装置は、ノードのエネルギーレベル、送信するデータのタイプとノードのロケーションに基づいた集約の可能性などのパラメータを考慮して、ルートまたはノードスケジュールのうちのいずれかまたは両方を定義する。本発明に係る方法および装置は、ネットワークトポロジーが静的またはほぼ静的なユビキタスコンピューティングのためのネットワークプロトコルの最適化に利用することができる。好ましい実施形態において、本発明に係る方法および装置は、トポロジーが静的なワイヤレスセンサネットワークのためのエネルギー効率の高いルーティングおよびＭＡＣプロトコルを提供する。用途としては、環境のモニタリング、ホームネットワーキングまたはローカリゼーションなどがある。本発明はワイヤレスセンサネットワークの寿命を最大化し、新しいサービスを可能にするという点で効果的である。

本発明に係る方法のある実施要件に応じて、本発明に係る方法はハードウェアまたはソフトウェアで実施することができる。本発明の実施は、本発明に係る方法が実行できるようにプログラム可能なコンピュータシステムと協働することができるデジタル記憶媒体、特に電子的に読み取り可能な制御信号が保存された磁気ディスク、ＤＶＤまたはＣＤを使用して行うことができる。したがって、本発明は一般にコンピュータ上で本発明に係る方法を実行する機能を持つプログラムコードが機械的に読み取り可能な媒体に記憶されたコンピュータプログラム製品である。言い換えると、本発明に係る方法は、コンピュータ上で本発明に係る少なくとも１つの方法を実行するためのプログラムコードを有するコンピュータプログラムである。

ルーティングがノードのエネルギーレベルまたはエネルギー消費量とデータ集約の可能性とに基づく、送信を制御するための本発明の実施の一形態による方法のフローチャートである。 スケジューリングがデータ集約の可能性に基づく、送信のスケジューリングを制御するための本発明の実施の一形態による方法のフローチャートである。 クロスレイヤネットワークアーキテクチャの一例を示す図である。 ルート選択（ＲＳ）とノードスケジューリング（ＮＳ）とを定期的に反復する本発明の実施の好ましい形態による方法のフローチャートである。 ルート選択またはノードスケジューリングのラウンド当たりｎ個のデータ配信期間（ＤＤＰ１〜ｎ）が存在するタイムダイアグラムの一例を示す図である。 各ノードが可能な３つのパラメータの中の１つの特定のパラメータを測定する唯一のセンサを有する、等間隔に並んだ複数のノードを有するネットワークの一例を示す図である。 ルート最適化に関連のあるパラメータを示す図である。 ルーティング（ＲＳルート選択）を制御するための本発明に係る方法の一実施形態を示す図である。 モニタ距離（ＭＤ）と関連する相対的なウェイトとに関する典型的な３つのケースを示す図である。 集約性（ＡＧ）と関連する相対的なウェイトとに関する典型的な３つのケースを示す図である。 図４Ｂに示されているルーティングを制御するための本発明に係る方法の実施形態に基づくステップに対応した典型的なグラフと得られるツリーとを示す図である。 スケジューリングを制御するための本発明に係る方法を実行するための典型的なアルゴリズム（ノードスケジューリングＮＳ）を示す図である。 図８Ａに示されているノードスケジューリング（ＮＳ）アルゴリズムのステップを説明するための典型的なツリーを示す図である。 あるパラメータを変化させた場合のシミュレーション結果のグラフである。図９ａは、異なるノード密度に対する、エネルギーレベルの相対的なウェイトの影響を示す図である。図９ｂは電力消費量の相対的なウェイトの影響を示す図である。図９ｃと図９ｄとは、電力消費量の相対的なウェイトと組み合わせたモニタ距離の相対的なウェイトの影響を示す図である。 集約のための異なる相対的なウェイトとそれらの平均エネルギー消費量に対する影響とについてのシミュレーション結果である。 データ配信期間についてのシミュレーション結果である。 通信レンジに応じた、正規化された平均エネルギー消費量に対するノード間距離の異なる相対的なウェイトへの影響を示す図である。 パラメータタイプの分布に関する３つの実例を示す図である。 センサノードからモニタノードへのルートに関する２つの実例を示す図である。 図１１に基づく典型的な３つのパラメータタイプの分布と図１２に基づく２つのルートとに対するネットワーク寿命を、本発明に係る方法の好ましい実施形態と比較するための図である。 本発明に係る方法をゴルフコースに適用した場合の一例を示す図である。 本発明に係る方法を駐車場に適用した場合の一例を示す図である。

Claims (13)

1. あるネットワーク内で複数のセンサノード（３１０、３２０、３３０）からモニタノード（３４０）へのデータの送信を制御する方法であって、
   前記センサノードと前記モニタノードとを頂点とするグラフを生成するステップ（Ｓ１、ＲＳ１）であって、前記グラフのエッジは、各ノード間の距離に基づいてセンサノードのペアを互いに接続するか、またはセンサノードを前記モニタノードへ接続するものである、ステップと、
   前記センサノードごとに、関連するエネルギーレベル（４３０）またはエネルギー消費量を取得するステップ（Ｓ２）と、
   前記エネルギーレベル（４３０）または前記エネルギー消費量と同じデータタイプのデータの集約（４２０）の可能性とに応じて、前記グラフの各エッジにウェイトを割り当てるステップ（Ｓ３、ＲＳ２）であって、あるセンサノードのエネルギーレベルが高くなるほどまたはエネルギー消費量が小さくなるほどおよびデータ集約の可能性が高くなるほど、ルーティングツリーを定義するステップにおいて該センサノードに接続されたエッジを選択する確率を高めるウェイトが割当てられるものである、ステップと、
   前記センサノードごとに、前記センサノードから前記モニタノードへと前記データを送信するためのルートを含むルーティングツリーを定義するステップ（Ｓ４、ＲＳ３、ＲＳ４）であって、前記ルーティングツリーの全体のウェイトは、より小さいウェイトが選択の確率が高いことを示す場合には最小化され、より大きいウェイトが選択の確率が高いことを示す場合には最大化されるものである、ステップと、
   前記複数のセンサノードと前記モニタノードとに対し前記ルートを割り当てるステップ（Ｓ５）と
   を含む方法。
2. 前記複数のセンサノード（３１０、３２０、３３０）のうちの各ノードと前記モニタノード（３４０）とに対して、前記データを送信または受信するためのスケジュールを定義するステップ（Ｓ６）であって、前記ルーティングツリーに基づくとともに前記データの集約を考慮するステップをさらに含む請求項１に記載の方法。
3. 前記センサノード（３１０、３２０、３３０）は、複数の異なるデータタイプのデータを測定し、受信し、または送信するものである、請求項１または２に記載の方法。
4. ウェイトを割り当てる前記ステップ（Ｓ３、ＲＳ２）は、それぞれのセンサノード間の距離（４１０）と、あるセンサノードと前記モニタノードとの間の距離（４５０）とにさらに依存するものであり、
   距離（４１０、４５０）が大きくなるほど、前記それぞれのセンサノードにより定義されるエッジまたは前記センサノードと前記モニタノードとにより定義されるエッジを選択する確率が低いものとなる、
   請求項１〜３のいずれか一項に記載の方法。
5. ウェイトを割り当てる前記ステップ（Ｓ３、ＲＳ２）に関して、該ステップが依存するパラメータは、相対的なウェイトに基づいて他のパラメータに応じて重み付けがなされる、請求項１〜４のいずれか一項に記載の方法。
6. ウェイトを割り当てる前記ステップ（ＲＳ２）は、
   

   

   に基づくものであり、ここで、Ｅはグラフのエッジの集合であり、ｅ_ｉｊはエッジの前記集合Ｅ内の特定のエッジであり、ｗｉｊはインデックスｉを有するノードをインデックスｊを有する別のノードに接続するエッジのウェイトであり、ｉ，ｊ，＝１，．．．，Ｎまたはｉ，ｊ＝Ｍであり、Ｎは前記センサノードの数であり、Ｍは前記モニタノードのインデックスであり、ＥＬは前記エネルギーレベルであり、Ｋ_ＥＬは前記エネルギーレベルＥＬに割り当てられている相対的なウェイトであり、ＥＣは前記エネルギー消費量であり、Ｋ_ＥＣは前記エネルギー消費量ＥＣに割り当てられている相対的なウェイトであり、ＮＤは前記ノード間の距離であり、Ｋ_ＮＤは前記ノード間の距離ＮＤに割り当てられている相対的なウェイトであり、ＭＤはモニタ距離であり、Ｋ_ＭＤは前記モニタ距離ＭＤに割り当てられている相対的なウェイトであり、ＡＧは集約の可能性であり、Ｋ_ＡＧは前記集約の可能性ＡＧに割り当てられている相対的なウェイトであり、前記エネルギーレベルＥＬと前記エネルギー消費量ＥＣと前記ノード間の距離ＮＤと前記モニタ距離ＭＤと前記集約の可能性ＡＧとは、０と１との間で正規化された値である、
   請求項５に記載の方法。
7. ルーティングツリーを定義する前記ステップ（ＲＳ３）は、最小スパニングツリー（ＭＳＴ）アルゴリズムに基づいて実行される、請求項１〜６のいずれか一項に記載の方法。
8. スケジュールを定義する前記ステップ（Ｓ６）は、前記データの集約を考慮するものであり、その結果前記センサノードが前記ルーティングツリーに基づいてそれ自体が測定する同じデータタイプのデータを受信するか、または同じデータタイプのデータを２つ以上受信する場合に、これら同じデータタイプのデータが単一の送信に集約される、請求項２〜７のいずれか一項に記載の方法。
9. スケジュールを定義するステップ（Ｓ６）は、
   前記複数のセンサノードから前記モニタノードへの全てのデータの送信に対して、前記センサノードおよび前記モニタノードごとに、ノードごとに受信するデータの数（ｎＲｘ）とノードごとに送信するデータの数（ｎＴｘ）とを前記ルーティングツリーに基づいて計算するステップ（ＮＳ１）と、
   各前記センサノードと前記モニタノードとに対し、前記ノードごとに受信するデータの数に基づいて前記データを受信するための連続する時間間隔または複数の時間間隔と、前記ノードごとに送信するデータの数に基づいて前記データを送信するための連続する時間間隔または複数の時間間隔とを割り当てるステップであって、異なる送信リンクが互いに干渉しない場合に、あるアルゴリズムに基づいてオーバーラップした時間間隔を異なる送信リンクへと割り当てることができ、送信リンクはデータを送信するセンサノードと前記データを受信する対応するセンサノードまたはモニタノードとにより定義される、ステップと
   を含む請求項２〜８のいずれか一項に記載の方法。
10. 前記時間間隔は固定長のタイムスロットであり、
    １つのデータはタイムスロット当たり１つの送信リンクを介して送信可能であり、
    スケジュールを定義する前記ステップ（Ｓ６）は、前記センサノードのそれぞれに対し深度を割り当てることに基づくものであり、割り当てられた前記深度は、前記ルーティングツリーに基づいて、前記モニタノードからセンサノードまでの距離として定義されるものであり、
    計算する前記ステップ（ＮＳ１）は、最大の深度を有するセンサノードから開始して最小の深度を有するセンサノードまで進みながら、前記センサノードおよび前記モニタノードに対して前記タイムスロットを反復的に割り当てるように行われるものであり、ここで、すでに実際にタイムスロットが割り当てられている送信リンクが他の送信リンクと干渉しない場合に、前記他の送信リンクに属する深度が同じであるかまたは小さいセンサノードに同じタイムスロットが割り当てられる、
    請求項９に記載の方法。
11. 前記センサノードへのタイムスロットの前記割り当てにおいて、２つ以上のセンサノードが同じ深度を有する場合に、前記タイムスロットは最大のバッファ遅延を有するセンサノードへと割り当てられる、請求項１０に記載の方法。
12. コンピュータ上で、請求項１〜１１のいずれか一項に記載の方法を実行するためのプログラムコードを有するコンピュータプログラム。
13. あるネットワーク内で複数のセンサノードからモニタノードへのデータの送信を制御する装置であって、
    前記センサノードと前記モニタノードとを頂点とするグラフを生成する手段であって、前記グラフのエッジは、各ノード間の距離に基づいてセンサノードのペアを互いに接続するか、またはセンサノードを前記モニタノードへ接続するものである、手段と、
    前記センサノードごとに、関連するエネルギーレベルまたはエネルギー消費量を取得する手段と、
    前記エネルギーレベルまたは前記エネルギー消費量と同じデータタイプのデータの集約の可能性とに応じて、前記グラフの各エッジにウェイトを割り当てる手段であって、あるセンサノードのエネルギーレベルが高くなるほどまたはエネルギー消費量が小さくなるほどおよびデータ集約の可能性が高くなるほど、ルーティングツリーを定義する際に該センサノードに接続されたエッジを選択する確率を高めるウェイトが割当てられるものである、手段と、
    前記センサノードごとに、前記センサノードから前記モニタノードへと前記データを送信するためのルートを含むルーティングツリーを定義する手段であって、前記ルーティングツリーの全体のウェイトは、より小さいウェイトが選択の確率が高いことを示す場合には最小化され、より大きいウェイトが選択の確率が高いことを示す場合には最大化されるものである、手段と、
    前記複数のセンサノードと前記モニタノードとに対し前記ルートを割り当てる手段と
    を備える装置。

Images