(57)【特許請求の範囲】
【請求項１】
データを収集するために複数のノードを含む無線ネットワークを稼動させる方法であって、ここで、前記無線ネットワークは複数のクラスタに分割されており、前記無線ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、或るジェネレーションは、一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、１つのクラスタは、或る時間において或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符合化されたデータを前記クラスタ内のノードに発信し、その発信されたデータを前記クラスタ内のノードによって復号するようになっており、
各クラスタがサクセサを有するように前記複数のノードを前記複数のクラスタにグループ分けを行うステップであって、前記サクセサは、１つ前のクラスタからジェネレーションのデータを受信するノードである、ステップと、
或るクラスタから少なくとも１つのジェネレーションのデータを次のクラスタのサクセサへ移動させるステップであって、前記次のクラスタが、その移動の後に前記移動させられた少なくとも１つのジェネレーションのデータに対して操作を行うものである、ステップと
を含む方法。
【請求項２】
或るジェネレーションのデータを次のクラスタへ移動させるステップは、現在のクラスタの一部もしくは全てのノードが、現在扱っているジェネレーションのデータを完全に復号し終わったときに、実行される、または、
或るジェネレーションのデータを次のクラスタへ移動させるステップは、現在のクラスタの中心にあるノードが、現在扱っているジェネレーションのデータを完全に復号し終わったときに、実行される、
請求項１に記載の方法。
【請求項３】
現在扱っているジェネレーションのデータを復号しているクラスタまたはクラスタのノードは、該クラスタの少なくとも１つもしくは２つ以上のノードが、前記現在扱っているジェネレーションのデータを完全にリカバリし終わった後に、異なるクラスタから受信した次のジェネレーションのデータの復号を開始する、請求項１または２に記載の方法。
【請求項４】
或るノードが或るジェネレーションを完全に復号し終わったときに、前記ノードは、自身にバッファリングされたその前のジェネレーションのパケット数を縮小することによって次のジェネレーションのパケットを格納し始め、さらに、前記ノードは、前記次のジェネレーションのパケットをバッファリングしている間に、前記前のジェネレーションのパケットを更に配信し、それにより、他のノードが前記前のジェネレーションを完全にリカバリし終えることを支援する、請求項１乃至３のいずれか一項に記載の方法。
【請求項５】
既にリカバリされたジェネレーションが格納された持続性メモリが、その容量の限界に達する場合、１つ以上のジェネレーションが、その持続性メモリから削除され、ここで、
各クラスタのヘッドは、そのクラスタの全てのノードからどのジェネレーションを削除すべきかを決定するか、または、各クラスタのヘッドは、各ノードごとに前記持続性メモリからどのジェネレーションを削除すべきかを個別に決定する、請求項１乃至４のいずれか一項に記載の方法。
【請求項６】
データを収集するために複数のノードを含む無線ネットワークを稼動させる方法であって、ここで、前記無線ネットワークは複数の仮想クラスタに分割されており、前記無線ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、前記ジェネレーションは一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、仮想クラスタは、同じジェネレーションに対して現在操作を行っているノードによって定義されるものであり、各ノードは、最初は或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符合化されたデータを仮想クラスタ内のノードに発信し、その発信されたデータを前記仮想クラスタ内のノードによって復号するようになっており、
或るノードが他のジェネレーションからのパケットをオーバヒアリングするステップと、
前記ノードが現在操作を行っているジェネレーションが、完全にリカバリされたときに、前記ノードが、他のジェネレーションからの前記オーバヒアリングされたパケットに基づいて次に操作を行うべきジェネレーションを選択するステップと、
を含む方法。
【請求項７】
前記オーバヒアリングされたパケットは、前記ノードによって格納され、最も多数のパケットが格納されたジェネレーションが、前記ノードが次に操作を行ってリカバリすべきジェネレーションとして選択される、請求項６に記載の方法。
【請求項８】
或るノードは、
現在処理されているジェネレーションデータを格納するための第１のバッファと、
オーバヒアリングによって取り込まれたジェネレーションデータを格納するための第２のバッファとを備えるものであり、
或るノードが次のジェネレーションに対して操作を行い始めたら、前記次のジェネレーションのデータは、前記第２のバッファから前記第１のバッファへ移動させられ、その前のジェネレーションのデータは、前記ノードによって更に配信されるために前記第１のバッファに保持される、請求項６または７に記載の方法。
【請求項９】
前記第１のバッファに格納された前記前のジェネレーションのデータは、前記前のジェネレーションのデータのパケットの１つ以上を組み合わせることによって符合化された形式で保持される、請求項８に記載の方法。
【請求項１０】
同じジェネレーションを収集しているアクティブなノード同士の間の最も遠い距離を監視し、その距離を一定の閾値未満に保つことによって仮想クラスタのサイズを制限する、請求項６乃至８のいずれか一項に記載の方法。
【請求項１１】
或るジェネレーションが、ノードによって完全にリカバリされたときに、前記リカバリが完了したジェネレーションのデータは、前記ノードの持続性メモリに書き込まれて、次のジェネレーションに対して操作を行う前記ノードの非持続性メモリの空き容量が確保される、請求項６乃至１０のいずれか一項に記載の方法。
【請求項１２】
既にリカバリされたジェネレーションを格納している持続性メモリが、その容量の限界に達する場合、１つ以上のジェネレーションをそのメモリから削除し、
ここで、
ノードが削除すべきジェネレーションをランダムに選ぶか、または、
各ノードは、前記持続性メモリに格納された各ジェネレーションごとのカウンタを保持し、該カウンタは、時間の経過とともに値が増大し、且つオーバヒアリングされたパケットから別のノードが持続性メモリからそのジェネレーションを削除したという情報が受信された場合には値が減少するように設定されており、削除すべきジェネレーションの決定をジェネレーションの各カウンタの値に基づいて行う、請求項１１に記載の方法。
【請求項１３】
データを収集するために複数のノードを含む無線ネットワークを稼動させる装置であって、ここで、前記無線ネットワークは複数のクラスタに分割されており、前記ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、或るジェネレーションは一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、１つのクラスタは、或る時間において或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符合化されたデータをクラスタ内のノードに発信し、その発信されたデータを前記クラスタ内のノードによって復号するようになっており、
各クラスタがサクセサを有するように前記複数のノードを前記複数のクラスタにグループ分けを行うためのモジュールであって、前記サクセサは、１つ前のクラスタからジェネレーションのデータを受信するノードである、モジュールと、
或るクラスタから少なくとも１つのジェネレーションのデータを次のクラスタのサクセサへ移動させるためのモジュールであって、前記次のクラスタが、その移動の後に前記移動させられた少なくとも１つのジェネレーションのデータに対して操作を行うものである、モジュールと
を備えている装置。
【請求項１４】
データを収集するために複数のノードを含む無線ネットワークを稼動させる装置であって、ここで、前記無線ネットワークは複数の仮想クラスタに分割されており、前記ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、或るジェネレーションは一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、仮想クラスタは同じジェネレーションに対して現在操作を行っているノードによって定義されるものであり、各ノードは、最初は或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符号化されたデータを仮想クラスタ内のノードに発信し、その発信されたデータを前記仮想クラスタのノードによって復号するようになっており、
或るノードが他のジェネレーションからのパケットをオーバヒアリングするためのモジュールと、
前記ノードが現在操作を行っているジェネレーションが、完全にリカバリされたときに、前記ノードが、他のジェネレーションからの前記オーバヒアリングされたパケットに基づいて次に操作を行うべきジェネレーションを選択するためのモジュールと、
を備えている装置。
【請求項１５】
データを収集するために無線ネットワークを稼動させる複数のノードに対して実行されるコンピュータプログラムであって、ここで、前記無線ネットワークは複数のクラスタに分割されており、前記無線ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、或るジェネレーションは、一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、１つのクラスタは、或る時間において或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符合化されたデータを前記クラスタ内のノードに発信し、その発信されたデータを前記クラスタ内のノードによって復号するようになっており、
各クラスタがサクセサを有するように前記複数のノードを前記複数のクラスタにグループ分けを行うステップであって、前記サクセサは、１つ前のクラスタからジェネレーションのデータを受信するノードである、ステップと、
或るクラスタから少なくとも１つのジェネレーションのデータを次のクラスタのサクセサへ移動させるステップであって、前記次のクラスタが、その移動の後に前記移動させられた少なくとも１つのジェネレーションのデータに対して操作を行うものである、ステップと
を実行させるためのコンピュータプログラム。
【請求項１６】
データを収集するために無線ネットワークを稼動させる複数のノードに対して実行されるコンピュータプログラムであって、ここで、前記無線ネットワークは複数の仮想クラスタに分割されており、前記無線ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、前記ジェネレーションは一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、仮想クラスタは、同じジェネレーションに対して現在操作を行っているノードによって定義されるものであり、各ノードは、最初は或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符合化されたデータを仮想クラスタ内のノードに発信し、その発信されたデータを前記仮想クラスタ内のノードによって復号するようになっており、
或るノードが他のジェネレーションからのパケットをオーバヒアリングするステップと、
前記ノードが現在操作を行っているジェネレーションが、完全にリカバリされたときに、前記ノードが、他のジェネレーションからの前記オーバヒアリングされたパケットに基づいて次に操作を行うべきジェネレーションを選択するステップと
を実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はデータを収集するために無線ネットワークを稼動させる方法および装置に関する。
【背景技術】
【０００２】
継続的に長期にわたってデータ収集を行うためのシステムにおいては、携帯電話機その他のタイプの通信可能な機器が継続的に環境から読取データ（data readings）を収集する。解決すべき問題は、効率的なデータの収集、再配信と、一般には、リソースが制約された無線端末から構成される無線ネットワークにおいてこのデータの処理を可能にすることである。標準的なソリューションとしては、この問題をシンプルな日和見的ルーティング（エピデミックルーチング（epidemic routing）とも呼ばれる）を用いて解決している。このソリューションでは、データがノードからノードへそれが最終目的地に到達するまでコピーされる。これらのソリューションはローカルな相互作用で機能するのでネットワークトポロジーの完全な知識を必要としないという意味で効率的である。しかしながら、これらのスキームは、ノード、リンクまたは経路に障害が生じた場合に、ローバスト性に欠けることがある。これらの機能障害に対処するために分散型ネットワーク符合化（distributed network coding）が使用される場合がある。ネットワーク符合化は、例えば非特許文献１、非特許文献２または非特許文献３に記述されている。
【０００３】
ネットワーク符合化を用いて、ノードは異なるデータソースに属し得る（複数の）オリジナルの情報パケットにわたって符合化された（複数の）パケットを送信する。符合化は、エネルギー消費、ノード故障に対するローバスト性およびリカバリ遅延の点で大きな利点を提供する。加えて、ネットワーク符合化ソリューションは、移動性（モビリティ）がある場合でも、ネットワークトポロジーを知る必要なく、分散型ネットワークにおいて有効であることが証明されている。ただ、シンプルなネットワーク符合化スキームは、通常、復号化プロセスのためにメモリを拡張して使用する必要がある。
【０００４】
メモリは多くの場合、携帯電話機やセンサなどの既存の小型組み込み機器における希少なリソースである。例えば、センサは通常、小型ＲＡＭ（Random Access Memory）や、より大型だが少し遅いＦＬＡＳＨメモリを備えている（ＭｉｃａＺといった一般的なセンサＭＯＴＥでは４ＫＢのＲＡＭメモリとおよそ５１２ＫＢのＦＬＡＳＨメモリ）。代わりに、最も基本的な携帯電話機は、１６Ｍｂ乃至６４ＭｂのＮＯＲ型フラッシュメモリと８Ｍｂ乃至３２ＭｂのＳＲＡＭまたはＰＳＲＡＭとを併用して使用するプロセッサを特徴とする。
【０００５】
必要となるメモリを制限するため、データはいくつかのジェネレーション（generation）にグループ分けすることができる。ジェネレーションとは、同じ地理的エリア内または同じ期間内に収集されたデータ（または両方の組み合わせ）を指し、同じジェネレーションのデータだけが一度に符合化／復号化される。
【０００６】
次に無線センサネットワークを操作するための従来技術のアプローチについて説明する。
【０００７】
非特許文献４において、著者らは、モバイル・コレクタ（collector）／基地局（ＢＳ：base station）を含むモバイルＷＮについて議論している。複数のノードは協力して（かつ日和見的に）データをＢＳ（基地局）に転送し、このデータの重複コピーをそれらのメモリに格納する。ストレージが限られている場合には、ノードはメモリから最も古い受信データを削除することによってそれら自身の読取データ（data readings）を優先する（つまり“データ置換スキーム”を使う）。さらに、それら自身のデータがＢＳに転送されると、そのデータはメモリからすぐに削除される。このシンプルなデータ管理スキームは、主にデータの損失に強いが、その一方でネットワーク内におけるデータの存続性（persistence）を完全に無視している。
【０００８】
非特許文献５において、著者らは、新しいデータを定期的に生成するようなノードがある場合について、例えば、時間ジェネレーション（temporal generation）を議論している。ここで、時間ジェネレーションは、ＷＮ内の全てのノードによって同じ期間内に生成されたデータの集合として定義されている。彼らは、大規模ネットワークの場合を考慮に入れていない。実際、Kamraらの文献では、ノードはＲＡＭにより多くのジェネレーションを同時に保持するが、その際、古いデータを新しいデータで上書き（つまり置換）をする。しかし、これは、メモリに制約があるために、大規模ネットワークでは実現不可能である。
【０００９】
非特許文献６では、シンプルな分散型ジェネレーション管理スキームが設計されている。著者らは、時間ドメインと空間ドメインとの両方において特定のジェネレーションのサイズ閾値を利用するアイデアに基づいて、任意の所与のジェネレーションに挿入されたパケットの数を制限することを提案している。閾値はノードの利用可能なＲＡＭメモリに適用することができる。具体的には、ノードはパケットを空間ジェネレーション（spatial generation）に挿入する場合、それらのノードがその空間ジェネレーションの発生元だったノードのｋホップ近傍に属する場合にのみ挿入することが許される。
【００１０】
非特許文献７は、複数のジェネレーションを同時に処理するためのシンプルなバッファスキームを提示している。しかしながら、このソリューションはこの場合も同じく小規模ネットワークにのみ機能する。この場合、全てのノードが、例えば同じ発生期間の間に生成されたデータをノードメモリに格納することができる。
【００１１】
非特許文献８では、継続的なデータ収集のための更なる実用的なルールのセット、すなわち、データ置換アルゴリズムと組み合わせたＰＮＣ（Partial Network Coding）の概念が提示されている。著者らは、継続的に生成されたデータを制限されたサイズのバッファに効率的に格納する方策を提案している。詳しくは、提案されたスキームによれば、１つのネットワークはいくつかのクラスタに細分される。同じクラスタ内のデータは一緒に符合化されるが、異なるクラスタに属するデータは決して混合されない。これにより、制限されたバッファサイズに対処することが可能となる。著者らは継続的にデータ収集するためのデータ置換パラダイムを活用することを提案している。
【００１２】
このアプローチの問題はネットワーク内におけるデータの存続性を保証しないことである。加えて、あるクラスタに属するデータはそのクラスタ内に発信（disseminate）される（ばらまかれる）だけであり、そのあと基地局に移されるので、その基地局のみが全てのパケットを復号することが潜在的に可能である。それに対し、ネットワークノードはそのネットワーク内で生成されたデータの部分的なビューを取得するに過ぎない。
【００１３】
クラスタ型ネットワーク符合化の概念は、非特許文献９に紹介されている。著者らは、大規模ネットワーク全体にわたるマルチレベル符合化を組み込んだ“連結（concatenated）”ネットワーク符合化技術を提案している。彼らは１つのネットワークを複数の小さなネットワーク（クラスタ）に分割し、次いでこれらのクラスタをルーティング経路に沿って連結している。主な目的は、各クラスタが単一のジェネレーションのみを処理することで符合化と復号の両方を単純化することにある。ノードはブロック符合化をローカルな情報のみに基づいて実行することができるので、これは特に重要である。ネットワーク符合化は各クラスタ内で実行され、各ノードはそれ自身のクラスタに割り当てられたジェネレーションを処理するだけである。
【００１４】
クラスタリングアプローチはクラスタ内におけるデータの“ネットワーク符合化”と共に、限られたメモリリソースを考慮してパフォーマンスを改善する。しかしながら、ネットワーク内におけるデータの存続性の問題が残っている。
【００１５】
実際の応用例として、環境データを感知してそれを例えば携帯電話機からＷＬＡＮホットスポット（低コスト技術）へ送信するエンドユーザを考えることができる。またユーザの移動性（モビリティ）などのために、このホットスポットは頻繁に長期間使えないことが考えられる。例えば、データ置換（非常に限られた記憶容量に対処するため、古いデータに新しいデータを同じ記憶場所で上書きする）の“不満足な”メカニズムを避けて、どのようにしてこのユーザはこのデータをインタネットに損失なく格納することができるだろうか？
【００１６】
これはネットワーク内におけるデータの“存続性”、信頼性およびローバスト性の問題を示している。これはまた、無線センサネットワークのための改良された稼動方法が依然として必要とされていることを示している。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】R. Ahlswede, N. Cai, S.-Y. Li, R. Yeung, "Network information flow", IEEE Trans. on Information Theory, vol.46, no.4, pp. 1204-1216, July 2000
【非特許文献２】M. Effros, T. Ho, D. Karger, R. Koetter and M. Medard, "Randomized distributed network coding", US Patent Application, US 2005/0152391 Al, Jul 14, 2005
【非特許文献３】P. A. Chou, Y. Wu and K. Jain, "Practical Network Coding", in 51st Allerton Conf. Communication, Control and Computing, Oct 2003
【非特許文献４】P. Juang, H. Oki, Y. Wang, M. Martonosi, L.S. Peh and D. Rubenstein, "Energy-efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with ZebraNet", ASPLOS, San Jose, CA, Oct 2002
【非特許文献５】A. Kamra, V. Misra, J. Feldman and D. Rubenstein, "Growth Codes: Maximizing Sensor Network Data Persistence", In ACM SIGCOMM, Pisa,  Italy, Sept 2006
【非特許文献６】C. Fragouli, J. Widmer, and J.Y. Le Boudec, "Efficient broadcasting using network coding", accepted for IEEE/ACM Transactions on Networking, 2007
【非特許文献７】D. Munaretto, J. Widmer, M. Rossi and M. Zorzi, "Resilient Coding Algorithms for Sensor Network Data Persistence", submitted to EWSN, Sept 2007
【非特許文献８】D. Wang, Q. Zhang and J. Liu, "Partial Network Coding: Theory and Application for Continuous Sensor Data Collection", IWQoS, 14th IEEE International Workshop on Quality of Service, New Haven, CT, USA, June 2006
【非特許文献９】K. S. Wu, "Concatenated Network Coding for Large-Scale Multi-Hop Wireless Networks", in Proc. of WCNC 2007, Hong Kong, Mar 2007
【非特許文献１０】D. Wei and A. H. Chan, "Energy Efficient Dynamic Cluster Algorithm for Ad Hoc Sensor Networks", In Proc. of the First IEEE Intern. Conf. on Wireless Broadband and Ultra Wideband Communications (Aus Wireless 2006), Sidney, Australia, Mar 2006
【非特許文献１１】O. Younis and S. Fahmy, "Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach", In Proc. of the IEEE Conference on Computer Communications (INFOCOM), Hong  Kong, Mar 2004
【発明の概要】
【００１８】
本発明は、データを収集するために複数のノードを含む無線ネットワークを稼動させる方法を提供する。本方法において、前記無線ネットワークは複数のクラスタに分割されており、前記無線ネットワークによって収集されたデータはいくつかのジェネレーション（generation）に分けられ、あるジェネレーションは一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、１つのクラスタが、或る時間において或る特定のジェネレーションのデータに対して操作を行い（operate）、そのデータを符号化し、その符合化されたデータを前記クラスタのノードに発信（disseminate）し、前記クラスタのノードがその発信されたデータを復号するようになっている。そして、本方法は、
各クラスタがサクセサ（successor）を有するように前記複数のノードを前記複数のクラスタにグループ分けを行うステップと、
或るクラスタから少なくとも１つのジェネレーションのデータを次のクラスタへ移動させるステップであって、その移動の後に前記次のクラスタが前記移動させられた少なくとも１つのジェネレーションのデータに対して操作を行うものである、ステップと
を含む。
【００１９】
各クラスタがサクセサを有するようにネットワークをクラスタへグループ分けし、ジェネレーションのデータをそのサクセサへ移動させることにより、ネットワークにおけるデータの存続性とローバスト性が改善される。また、或るクラスタから少なくとも１つのジェネレーションのデータが移動させられ得る。このデータは、そのクラスタが現在復号して扱っているデータであり得る。このデータは、このデータに対して次に操作を行う次のクラスタへ移動させられ得る。このデータは、一般的にジェネレーション全体のデータまたはその一部を含み得る。少なくとも１つのジェネレーションのデータが移動させられるが、本方法の一態様によれば、複数のジェネレーションのデータがネットワーク内を移動させられる。このとき、各ジェネレーションは、それに対して操作を行っている現在のクラスタから次にそれに対して操作を行う次のクラスタへ移動させられる。
【００２０】
本方法において、その一態様として、ジェネレーションのデータを次のクラスタへ移動させるステップは、現在のクラスタの一部もしくは全てのノードが、現在扱っているジェネレーション（current generation）のデータを完全に復号し終わったときに、実行される、または、
ジェネレーションのデータを次のクラスタへ移動させるステップは、現在のクラスタの中心にあるノードが、現在扱っているジェネレーションのデータを完全に復号し終わったときに、実行される。
【００２１】
これにより、ジェネレーションをいつ次のクラスタへ移動すべきか（つまり移動すべき時）を決定することが可能となる。中心ノードのみが復号を実行し終わった後に移動を行うと、中心におけるトラフィック密度がより高いという事実を利用するものであり、その結果、全クラスタにわたるジェネレーションの移動速度が、移動をより早期に開始することによって改善される。さらに、ジェネレーションを復号し終わったクラスタの中心にあるノードは、そのクラスタのその他のノードが依然として、現在扱っているジェネレーションの復号の処理にかかり切りになっていても、次のジェネレーションの復号を既に開始することができる。
【００２２】
本方法の一態様によれば、ジェネレーションのデータは、現在のクラスタの少なくとも１つもしくは２つ以上のノードがそのジェネレーションのデータをリカバリし終わった後に、現在のクラスタから次のクラスタへ移動させられる。これはジェネレーションを次のクラスタ（サクセサ）へ移動させるための１つの適切なトリガーメカニズムである。本方法の或る特定の態様として、クラスタのノードは、この特定のノードが、現在扱っているジェネレーションの復号を完了したときに、次のジェネレーションの復号を開始する。
【００２３】
本方法において、その１つの態様として、現在扱っているジェネレーションのデータを復号しているクラスタまたはクラスタのノードは、該クラスタの少なくとも１つもしくは２つ以上のノードが、前記現在扱っているジェネレーションのデータを完全にリカバリし終わった後に、異なるクラスタから受信した次のジェネレーションのデータの復号を開始する。
【００２４】
これは、クラスタまたはクラスタのノードを次のジェネレーションを復号するようトリガーするのに適したトリガーメカニズムである。
【００２５】
本方法において、その１つの態様として、或るノードが或るジェネレーションを完全に復号し終わった後で、そのノードは、自身にバッファリングされたその前のジェネレーションのパケット数を縮小することによって次のジェネレーションのパケットを格納し始める。さらに、そのノードは、前記次のジェネレーションのパケットをバッファリングしている間に、前記前のジェネレーションのパケットを配信し、それにより他のノードが前記前のジェネレーションを完全にリカバリし終わるのを支援する。
【００２６】
既に処理されたジェネレーションをバッファに保持すること（およびそれを他のノードへ配信（distribute）すること）により、他のノードがまだ復号し終わっていないジェネレーションの復号を完了するのを支援する。
【００２７】
一態様として、非持続性メモリ（ＲＡＭなど）に格納されたジェネレーションのパケットを復号し、ジェネレーションの復号が完了したら、ノードはそれらを持続性メモリ（ＦＡＬＳＨメモリなど）に格納する。
【００２８】
本方法において、その１つの態様として、既にリカバリされたジェネレーションが格納された持続性メモリがその容量の限界に達する場合、１つ以上のジェネレーションがそのメモリから削除される。ここで、
各クラスタのヘッドは、そのクラスタの全てのノードからどのジェネレーションを削除すべきかを決定するか、または、
各クラスタのヘッドは、各ノードごとに個別に前記持続性メモリからどのジェネレーションを削除すべきかを決定する。
【００２９】
これにより持続性メモリを有効利用することができる。
【００３０】
本発明は、上記課題を解決するため、データを収集するために複数のノードを含む無線ネットワークを稼動させるもう１つの方法を提供する。本方法において、前記無線ネットワークは複数の仮想クラスタに分割されており、前記無線ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、或るジェネレーションは一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、仮想クラスタは、同じジェネレーションに現在操作を行っているノードによって定義されるものであり、各ノードは、最初は或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符合化されたデータを前記仮想クラスタのノードに発信し、前記仮想クラスタのノードが発信されたデータを復号するようになっている。本方法は、
或るノードが他のジェネレーションからのパケットをオーバヒアリングするステップと、
前記ノードが操作を行っている現在のジェネレーションが、完全にリカバリし終わったときに、前記ノードが、他のジェネレーションからの前記オーバヒアリングされたパケットに基づいて次に操作を行うべきジェネレーションを選択するステップと
を含む。
【００３１】
これにより、クラスタリングおよびジェネレーションの移動における集中型決定論的アプローチに伴う余計なオーバヘッドを、ネットワークにおけるデータの存続性をなお改善しながら避けることができる。
【００３２】
本方法において、その１つの態様として、前記オーバヒアリングされたパケットは前記ノードによって格納される。そして、最も多数のパケットが格納されたジェネレーションは、前記ノードが次に操作を行ってリカバリすべきジェネレーションとして選択される。
【００３３】
これにより、ノードは、次にリカバリされるべきジェネレーションを選ぶことが可能となる。これらのパケットは、第２の（またはマイナー）バッファに格納されることがある。この第２のバッファは、最初は空であることが可能である。なぜなら、ノードは、最初は或る特定のクラスタに属し、このノードによって最初に処理されるジェネレーションは、最初はこのクラスタに属するからである。
【００３４】
本方法において、その１つの態様として、或るノードは、
現在処理しているジェネレーションデータを格納するための第１のバッファと、
オーバヒアリングにより取り込まれたジェネレーションデータを格納するための第２のバッファとを備えており、
ノードが次のジェネレーションに対して操作を行い始めたら、次のジェネレーションのデータは前記第２のバッファから前記第１のバッファへ移動させられ、その前のジェネレーションのデータは、前記ノードによって更に配信されるために、前記第１のバッファに保持される。
【００３５】
本方法において、その１つの態様として、前記第１のバッファに格納された前記前のジェネレーションのデータは、前記前のジェネレーションのデータのパケットの１つ以上を組み合わせることによって符合化された形式で保持される。
【００３６】
既に処理されたジェネレーションをバッファに保持すること（およびそれを他のノードへ配信すること）により、他のノードがまだ復号し終わっていないジェネレーションの復号を完了するのを支援する。またデータを符合化された形式で保持することにより、配信効率が高まり、必要なメモリスペースを減らすことができる。
【００３７】
本方法は、その１つの態様として、同じジェネレーションを収集しているアクティブなノード同士の間の最も遠い距離を監視し、その距離を一定の閾値未満に保つことによって、仮想クラスタのサイズを制限することを更に含む。
【００３８】
これによりクラスタが大きくなり過ぎることを防ぐことができる。例えば、パケットは、データの出所でありその上でパケットが符合化される最も遠いノードまでの距離（ホップ数）を示すホップカウンタ（hop counter）を携行し得る。
【００３９】
本方法において、その１つの態様として、或るジェネレーションがノードによって完全にリカバリされた後で、次のジェネレーションに対して操作を行うための非持続性メモリの空き容量を確保するために、前記リカバリが完了したジェネレーションのデータは前記ノードの持続性メモリに書き込まれる。
【００４０】
これによりノードのメモリリソースを有効利用することが可能となる。
【００４１】
本方法において、その１つの態様として、既にリカバリされたジェネレーションが格納されている持続性メモリがその容量の限界に達する場合、１つ以上のジェネレーションがそのメモリから削除され、
ノードが削除すべきジェネレーションをランダムに選ぶか、または、
各ノードは、前記持続性メモリに格納された各ジェネレーションごとのカウンタを保持し、該カウンタは、時間の経過とともに値が増大し、且つ別のノードが持続性メモリからそのジェネレーションを削除したという情報がオーバヒアリングされたパケットから受信された場合には値が減少するように設定されており、削除すべきジェネレーションの決定をジェネレーションのそれぞれのカウンタの値に基づいて行う。
【００４２】
これによりデータを持続性メモリから削除するための分散型アプローチが可能となる。
【００４３】
本発明は、上記課題を解決するため、データを収集するために複数のノードを含む無線ネットワークを稼動させる装置も提供する。本装置において、前記無線ネットワークは複数のクラスタに分割されており、前記無線ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、或るジェネレーションは一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、１つのクラスタが、或る時間において或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符合化されたデータを前記クラスタのノードに発信し、前記クラスタのノードが発信されたデータを復号するようになっている。
本装置は、
各クラスタがサクセサを有するように前記複数のノードを前記複数のクラスタにグループ分けを行うためのモジュールと、
或るクラスタから少なくとも１つのジェネレーションのデータを次のクラスタへ移動させるためのモジュールであって、その移動の後で前記次のクラスタが前記移動させられた少なくとも１つのジェネレーションのデータに対して操作を行う、モジュールと
を備えるものである。
【００４４】
本発明は、上記課題を解決するため、データを収集するために複数のノードを含む無線ネットワークを稼動させるもう１つの装置も提供する。本装置において、前記無線ネットワークは複数の仮想クラスタに分割されており、前記ネットワークによって収集されたデータはいくつかのジェネレーションに分けられ、或るじぇねレーショは一定の期間内および／または一定のローカルエリア内において収集されたデータのセットであり、前記仮想クラスタは、同じジェネレーションに対して現在操作を行っているノードによって定義されるものであり、各ノードは、最初は或る特定のジェネレーションのデータに対して操作を行い、そのデータを符号化し、その符合化されたデータを前記仮想クラスタのノードに発信し、前記仮想クラスタのノードが発信されたデータを復号するようになっている。そして、本装置は、
或るノードが他のジェネレーションからのパケットをオーバヒアリングするためのモジュールと、
前記ノードが現在操作を行っているジェネレーションが、完全にリカバリし終わったときに、前記ノードによって他のジェネレーションからの前記オーバヒアリングされたパケットに基づいて次に操作を行うべきジェネレーションを選択するためのモジュールと
を備えるものである。
【００４５】
本装置は、１つの態様として、上記いずれかの態様の方法を実行するためのモジュールを更に備えるものである。
【００４６】
本発明は、上記課題を解決するため、コンピュータ上で実行される際にこのコンピュータが上記のいずれかの態様の方法を実行することを可能にするコンピュータプログラムコードを含むコンピュータプログラムも提供する。
【図面の簡単な説明】
【００４７】
【図１Ａ】本発明の実施形態を適用することができる１つのシナリオを示す図である。
【図１Ｂ】本発明の実施形態を適用することができる別のシナリオを示す図である。
【図２】異なるジェネレーションに基づく無線ネットワークのクラスタリングを説明するための図である。
【図３】本発明の実施の一形態によるジェネレーションの移動を説明するための図である。
【図４】本発明の更なる実施形態によるジェネレーションの移動を説明するための図である。
【図５】本発明の更なる実施形態によるジェネレーションの移動を説明するための図である。
【図６】本発明の更なる実施形態によるジェネレーションの移動を説明するための図である。
【図７】本発明の更なる実施形態によるジェネレーションの移動を説明するための図である。
【図８】本発明の更なる実施形態によるクラスタリングを説明するための図である。
【発明を実施するための形態】
【００４８】
最初に、本明細書で使用される用語について説明する。
ＢＳ（base station）：基地局
ＣＨ（cluster head）：クラスタヘッド
ＮＣ（network coding）：ネットワーク符合化
ＲＡＭ（random access memory）；ランダムアクセスメモリ
ＷＮ（wireless network）：無線ネットワーク
ＷＳＮ（wireless sensor network）：無線センサネットワーク
【００４９】
図１Ａおよび図１Ｂは、本発明を適用することができる環境を示している。図１Ａは複数の携帯電話機がデータを収集しており、収集したデータを携帯電話サーバに（データシンク）に送信し、そして、その携帯電話サーバからその収集したデータがインタネットに送られる。
【００５０】
図１Ｂには似たようなシナリオが示されている。しかしこの場合は、そのシナリオにおいて複数のクラスタが存在し、各クラスタは、クラスタヘッド（cluster head）を有し、このクラスタヘッドからデータが（例えばインタネット上に）それを必要とするそれぞれの場所に送信される。斯かるシナリオの用途としては、携帯電話機を使った都市およびその周辺の地図作成と監視、警報、監視、セキュリティおよび災害管理、病院や企業を支援するための都市サービスなどが挙げられる。
【００５１】
次に、斯かるシナリオにおいて採用することが可能な本発明の実施形態について説明する。本発明の実施形態は特に、データシンクが（少なくともしばらくの間）利用できないが、ネットワークにおけるデータの存続性（persistence）をそれでもなお維持しなければならない問題に対処する。一部の実施形態は、希少なリソース（例えばメモリや計算能力）で環境に適用されるのに特に適している。
【００５２】
限られたメモリリソースに対処するため、通常、ネットワーク符合化が特定のパケットのグループ、いわゆるジェネレーション（generation）に適用される。斯かるジェネレーションは、ノードのクラスタで生成されたパケット（および／または一定の期間内に生成されたパケット）を包含することができる。図２は、無線ネットワーク全体が４つのクラスタに分割されており、各クラスタが、対応するジェネレーションのパケットに働きかけるというシナリオを示している。
【００５３】
斯かるクラスタ内において、符合化された情報がその復号が完了する（つまり、クラスタ内の全てのノードがその情報を収集し終わる）まで伝播（propagate）される。本願のコーディング（coding）は、クラスタ内にデータを配信（distribute）する有効な方法であり、次にそれについて手短に説明する。例えば、クラスタ１のノード１がそのセンサからデータ（データ１）を収集し、ノード１はノード２からセンサデータ（データ２）を受信することを想定する。ここでのゴールは、クラスタのノードらの全てのセンサから全てのデータをそのクラスタの全てのノードに配布して、各ノードがデータの完全な全体像を手に入れるようにすることである。その目的のために、ノード２は何らかのアリゴリズムを使ってデータ１とデータ２（ノード２がセンサノード２から受信したもの）とを組み合わせ、それを他にノードに送信する。斯かる“符合化データ”を受信するノードは適切な復号アルゴリズムを使って、その符合化データを復号してオリジナルの（符合化されていない）データ１およびデータ２をリカバリすることができる。このようにして（符合化データを送信して、それを受信ノードにおいて復号することによって）伝送容量をより有効に利用することができる。さらに、このコーディングを通してデータを受信する単一のノードは２つ以上のノードからのデータについての知識を実際に手にし、それにより（例えばノードの損失または故障の場合に）ネットワークにおけるデータの存続性が改善される。実際のコーディングは従来技術において既に知られている既知のメカニズムを用いて実行することできる。
【００５４】
ネットワーク全体における復元力（resilience）と存続性を更に増強するために、実施の一形態によれば、異なるクラスタに含まれるデータの処理が実行される。これは実質的にこれまでのアプローチとは異なる。従来技術では、各クラスタがそのクラスタにのみ属する単一のジェネレーションにのみ働きかけており、特定のクラスタのジェネレーションは他のクラスタには配布されない。
【００５５】
ＷＮ（無線ネットワーク）上で実際にジェネレーションを移動させることによって、エネルギー消費量、オーバヘッド（余計な負荷）、遅延時間、ノードの寿命およびデータ存続性を最適化することが可能となる。継続的なデータ収集は、広範囲の用途には不可欠である。具体的には、ロスレスのアプリケーションはデータの信頼性と存続性の点で優れたパフォーマンスを必要とし、その目的のための現行のソリューションがデータ置換メカニズムである。ジェネレーション管理を使用する（クラスタ間でジェネレーションを移動させる）ことによって、メモリ制限に直面しても、リソースが制約されたＷＮにおいてデータを効率的に発信（disseminate（ばらまく））することが可能である。ネットワーク内にデータを分散して格納することによって、損失、ノードおよびリンクの故障に対する高い復元性のほかにデータの存続性が確保される。
【００５６】
次に、本発明の更なる実施形態を幾分より詳しく説明する。
【００５７】
Ｎ（Ｎ＞＞１）個のノードが存在するＷＮが与えられたとすると、斯かるＷＮ上に生成または拡散した情報パケットを取り扱う問題に直面する。携帯電話機とセルラセンサのほとんどのものは、限られた数の情報パケットしか一度にランダムアクセスメモリ（ＲＡＭ）に保持することができない。このため、ＷＮ上の異なるアプリケーションから来る全ての情報パケットを収集することは不可能である（つまり、単一のグローバルなジェネレーションを使用することは可能でない）。
【００５８】
結果として、本発明の実施形態によれば、図２に示すようにＷＮはいくつかのサブＷＮへ分割される。これは次に説明する“開始フェーズ（starting phase）”で実行される。ネットワークは、クラスタ群に編成され、そのクラスタ群に属する各クラスタはまさに初めは特定のジェネレーションと合致する（図２参照）。このため、ノードは、１乃至Ｍのインデックスを持つＭ個のクラスタの１つに属する。実施の一形態によれば、クラスタサイズの条件は、対応するジェネレーションがノードのＲＡＭメモリに完全にフィットしなければならないというものである。そうでなければ、情報をＦＬＡＳＨメモリとの間で常にスワップしなければならず、エネルギー消費量が増大する結果となる。先行技術としてクラスタを分散生成する異なる効率的なソリューションが提案されている。それらについては非特許文献１０および非特許文献１１を参照されたい。
【００５９】
そのクラスタの中において、クラスタヘッド（ＣＨ：cluster heads）は、ノードおよびネットワークパラメータ（例えば残りのエネルギー、ホップ距離など）を考慮するメカニズムを通じて選ばれる。本発明の実施形態は、新規のクラスタリングスキームを提案することを目的としていないが、本発明の実施形態は、任意の適切な既存のスキームを利用することができる。
【００６０】
クラスタが開始フェーズで決定された後、次に別のフェーズにおいてＷＮにおける複数のジェネレーションのクラスタ管理および処理に取り組む。以下、このフェーズを幾分詳しく説明する。
【００６１】
ジェネレーションを配信するための異なるアプローチ、すなわち情報フロー、例えばＷＮ上のジェネレーションの移動、を取り扱うための決定論的集中型およびランダム分散型オプションを取り扱う異なる実施形態が存在する。
【００６２】
前者の場合、ノードはデータ収集全体を通じて同じクラスタに属し、ジェネレーションはクラスタからクラスタへ移動し、各クラスタのクラスタヘッドと境界ノード（border nodes）によって監視および処理される。境界ノードは、メッセージをオーバヒアリング（overhearing：宛先以外のノードが受信すること）することによって近隣のクラスタのリカバリ状況を知り、この情報をクラスタヘッドに送る。クラスタヘッドは、クラスタ内の全てのノードに処理すべきジェネレーションを伝える。このようにして、クラスタ同士の間の同期が実現可能であり、クラスタはアイドル期間、例えば新たなジェネレーションを処理しない期間、を減らすことができる。さらに、ノードは、全てのジェネレーションをリカバリするために消費されるエネルギー量と、ＷＮ上に拡散した情報の完全なノードのカバレッジを実現するために必要な時間とを削減する。その後、それらは新たな時間ジェネレーションを迅速に開始することができる。情報フローを処理する方法はシンプルな仮想リンクリスト（virtual linked list）に基づいている。この場合、各クラスタは、例えば近隣のクラスタの間でメッセージを送り合うことによって、どれがサクセサ（successor）／プレデセサ（predecessor）かを知ることになる。図３は、斯かるメカニズムを示している。各クラスタは、サクセサとプレデセサを有している。例えば、クラスタ１は、最初はジェネレーション１に対して操作を行い（収集し、符合化し、発信（disseminate）し、復号またはリカバリを行い）、クラスタ２はジェネレーション２に対して操作を行い、等々といった具合である。次にジェネレーションは、各クラスタからその対応するサクセサへ移動する。図３に示された実施形態では、１つの“円”だけが示されているが、斯かるスキームは用途要件に応じてリストは異なる長さをとることができる（全てのクラスタを含む単一リストが存在する場合もあれば、それぞれ少数のノードを含む複数のリストが存在し、各“仮想リンクリスト”が、各ノードがサクセサとプレデセサを有するように対応するノードサークルを定めている場合もある）という点で柔軟性が高い。
【００６３】
次にジェネレーションのランダム分散に基づく実施形態について手短に説明する。ランダム分散型の場合、ジェネレーションはＷＮ上をランダムウォークと同じように移動する。現在扱っているジェネレーションをリカバリしている間、ノードは他（例えば近隣）のジェネレーションからのパケットをオーバヒアリングし、それらを（例えば、少数のパケットだけを格納することができる、ＲＡＭ内の小さなセパレートバッファに）格納する。現在扱っているジェネレーションが完全にリカバリされたら、ノードは、各近隣のジェネレーションから受信した情報ユニット（例えばパケット）の数に基づいてどのジェネレーションを開始すべきかを決定する。このとき最高の数のものがリカバリすべき新たなジェネレーションを決定する。
【００６４】
斯かるメカニズムによれば、決定論的集中型スキームにおけるような集中型の情報フロー制御は存在しない。また斯かる場合においては固定されたクラスタは存在しない。実際、同じジェネレーションに対して現在操作を行っているノードによって形成される“仮想クラスタ（virtual clusters）”しか存在しない。ジェネレーションはランダムメカニズムによってネットワーク上を移動し、同じようなやり方で“仮想クラスタ”は継続的に再形成される。仮想クラスタは、例えば管理者がネットワークをセットアップすることによって、または各ノードごとに最初にそれが属する仮想クラスタを決定する何らかの自己組織化スキームによって、最初に決定され得る。斯かる初期のクラスタ分離は、図１に示されたものと同じように見える場合もある。以前のケースのように、最初にクラスタ１はジェネレーション１に対して操作を行い、クラスタ２はジェネレーション２に対して操作を行う、等々といった具合である。しかしながら、その後、ネットワークが動作し続けるにつれ、クラスタメンバは他のジェネレーションからのオーバヘッド情報に基づく上述のランダムメカニズムによって変化する。
【００６５】
上述のランダムメカニズムは、展開が容易である点とジェネレーションの移動を決定するためにクラスタ間で交換されるメッセージが存在しない点で有益である。しかしながら、欠点は、近隣のクラスタで新しいジェネレーションが行方不明になっているために、クラスタが新しいジェネレーションの受信を停止してしまう可能性があることである。このため、ＷＮ上に情報が完全に拡散することを要求する適用例では、このスキームはあまり適さないと考えられる。損失に対する耐性がより高い適用例では、このスキームはコントロールメッセージを必要としない（低オーバヘッドで、リンク／ノードの破損または故障に対するローバスト性が高い）ので集中型メカニズムよりも適している。
【００６６】
これら２つのオプションの選択は用途に依存する。例えば、どのくらいの情報がＷＮ全体もしくは単一クラスタ内に拡散し、格納される必要があるのかとか、各クラスタごとにどんな種類の情報が重要と考えられるのかとか、現在扱っているジェネレーションがＷＮ全体で完全にリカバリされる前に新たな時間ジェネレーションに対して新たな読み出しを開始するかどうか、等々による。このため、良い点と悪い点は次のようにまとめられる。
１．決定論的集中型オプション
・良い点：ジェネレーションサイズに応じたクラスタサイズの最適化が可能である。各ジェネレーションごとに同じ発信レベルを保証するためのデータ発信（data dissemination）のコントロールが可能である。ノード同士の間の同期が可能である。
・悪い点：クラスタ構造を、特に動的環境において、維持するために追加オーバヘッドが必要となる。
２．ランダム分散型オプション
・良い点：必要とされる追加オーバヘッドがなく、非同期的な発信であり、従って遅延時間の点でよりよいパフォーマンスをもたらし、動的環境への適応が容易である。
・悪い点：不均一な発信プロセス、それは情報損失または発信プロセスの障害を引き起こす可能性がある。
【００６７】
次に、決定論的集中型アプローチを使用する更なる実施形態について幾分より詳しく説明する。
【００６８】
ノードが開始ジェネレーション（それら自身のクラスタに対応する）を完全にリカバリし終わったところで、それらのノードはその開始ジェネレーションを、例えば通常ＲＡＭの数倍のサイズを持つＦＬＡＳＨメモリなどのパーシスタントメモリ（persistent memory：持続性メモリ）に書き込む。しかし、ＦＬＡＳＨメモリとの読み出しと書き込みにはＲＡＭよりも多くのエネルギーが消費される。ＦＬＡＳＨメモリは継続的なデータ収集の間に集積した膨大な数の感知データを保持するに十分な大きさの容量があるので、これは情報パケットの寿命を延ばすのに役立つ。
【００６９】
現在扱っているジェネレーションがパーシスタントメモリに書き込まれた後、その現在扱っているジェネレーションは、隣接するクラスタから到来する新しいジェネレーションで置き換えられることが可能である。この様子を図４に概略的に示している。境界ノードは、隣接のクラスタに属する境界ノードにメッセージを送信することによって、完全なリカバリが遂行されるまで（図４の右側参照）新しいジェネレーションの収集を開始する（図４の左側参照）。以下、この手続きについて幾分より詳しく説明する。
【００７０】
図５には隣接する２つのクラスタが新しいジェネレーションの収集を開始する準備が整っているシナリオが示されている。一般的なＷＮ上に拡散したデータは通常、ノードが高密度のデータトラフィックゾーン内にあるクラスタの中心エリアにおいて高い復号／復元率の実現をもたらす。実際、ほとんどのケースでは、クラスタの中心ノードはクラスタ全体（またはＷＮ）で最も高いトラフィック密度を持つことから利益を得る。
【００７１】
この様子を図６に概略的に示している。クラスタ１は最初にジェネレーション１をリカバリし、クラスタＭからジェネレーションＭを受信する。中心ノードではトラフィック密度がより高いが故に、受信されたパケットは中心ノードに蓄積する。従って、中心ノードでは新しい情報を受信する蓋然性が最も高いのでリカバリ（復号）が最も速く進むことになる。
【００７２】
次のクラスタの中心ノードのみが、それら自身の現在扱っているジェネレーションの情報を完全にリカバリした時に次のクラスタへのジェネレーションの移動を開始するために、クラスタヘッドはそれらの間のルートを（適切なマルチホップルーティングプロトコルを用いて）設定することができる。移動させられる予定の新しいジェネレーションのパケットは（境界ノードを介して）中心から中心へダイレクトに移動することが可能である。
【００７３】
中心ノードは、全てのノードの中で最初に、新しいジェネレーションのリカバリを開始し（古いデータは１００％リカバリされており、新しいデータは２０％リカバリされている）、それと同時に、古いデータを近隣のノードへ拡散し続けてそのクラスタの全ての他のノードがリカバリを完了することができるようにする。図６に示すように、ジェネレーション１のデータはクラスタ２へ拡散する（ジェネレーション１のデータは、クラスタ１の中心からクラスタ２の中へダイレクトに発信されるので、クラスタ２の中心に蓄積する）。同様に、ジェネレーション２のデータはクラスタ３へ拡散する。
【００７４】
ジェネレーションを新しいクラスタの中心へ発信するプロセスは、本発明の実施の一形態によれば、ジェネレーションを新しいクラスタへ配信する１つの可能性である。代わりに、クラスタのあらゆるノードがジェネレーションの全てのパケットを復号し終わったら、図４に関連して述べたようにそのジェネレーションを境界から次のクラスタへ伝達することが可能である。しかし、通常は中心（のノード）が最初に復号する（または高いトラフィック密度のせいで復号手続きを真っ先に手がける）ので、実施の一形態によれば、中心から中心への情報の伝達が強制されることがある。このため、実際には、クラスタの全てのノードがあらゆるものを復号し終わる前にジェネレーションの移動の開始が可能となる。
【００７５】
次に本発明の実施の一形態によるこのプロセスを幾分より詳しく説明する。例えば、クラスタヘッドは、メッセージを送ることにより、クラスタの中央においてリカバリが完了したかどうかを知る。次に、クラスタヘッドは、情報がこれらの中央にあるノードに到達するように境界ノードをトリガーする（クラスタヘッドは誰がそのプレデセサとサクセサのクラスタかを知っている）。こうして、斯かるノード（中央にあるノード）は新しいジェネレーションの処理を開始し、それと同時にまだ古いジェネレーションのリカバリが完了していないその他のノードを、新しいジェネレーションからの情報で取り替えられる古い情報を送信して支援する。しかしながら、各パケットごとにそれが属するジェネレーションを特定することは常に可能であるという意味で、古いジェネレーションと新しいジェネレーションは“混同”されないことは留意すべきである。例えば、各パケットはそれが属するジェネレーションを特定する識別子を有し得る。このようにして、或る特定の瞬間にどのジェネレーションがどこで（どのクラスタのどのノードで）処理されるかを追跡し損なうことなくジェネレーションは適切に処理することが可能である。
【００７６】
次に実施の一形態によれば、新しいジェネレーションをリカバリ（つまり新しいジェネレーションのパケットを復号）し始めることによってその新しいジェネレーションを処理し始める時がどのようにして決定されるかについて説明する。このコンテクストにおいて実施の一形態によるノードは一度に２つ以上のジェネレーションを決してリカバリ（つまり復号）しないことに留意すべきである。実施の一形態による新しいジェネレーションのリカバリは、古いジェネレーションが完了したときに開始される。新しいジェネレーションのリカバリを開始するための追加的なまたは代替的な基準は、古いジェネレーションのパケットがしばらくの間（特に或る時間の間）もう全く到着しないときに、ノードはそこから古いジェネレーションはこれ以上リカバリできないと結論するというものである。しかし、ノード（例えばセンターノードの１つ）が完全にリカバリし終わったときはいつでも、そのノードはそれ自身のクラスタに既に移動している次のジェネレーションに取りかかることができる。まだ完全にリカバリし終わっていないノードは、現在扱っているジェネレーションの処理が済んだ後に、別のジェネレーションからのこれらのパケットをリカバリするために二次バッファに格納することができる。
【００７７】
次に実施の一形態によれば、ノードはジェネレーションが完全に復号されたことをどのようにして知るかを説明する（それを知ることにより、そのノードは次のジェネレーションのリカバリを開始することができる）。実施の一形態による集中型メカニズムでは、ノードはそれらのクラスタヘッド（ＣＨ）からその他のジェネレーションのサイズを知るようになっている。それ故、ノードは、いつそれが或る特定のジェネレーションを完全にリカバリし終わったかを知る。ランダムなケース（より詳しくは後述する）では、クラスタはまさに初めにそれらの最初のジェネレーションのサイズ（オリジナルのクラスタと一致する）を知るので、実施の一形態によればそれらは将来のジェネレーションのサイズはそれら自身の最初のジェネレーションのサイズに近いと推察することができる。それらはそのジェネレーションの全てのシンボルを復号することができるやいなや、それらは、現在扱っているジェネレーションのサイズを、その前のジェネレーションのサイズと比較する。現在扱っているジェネレーションのサイズが、その前のジェネレーションのサイズと比べて（例えば閾値を超過しないことによって）あまり逸脱していない場合は、ノードはこのジェネレーションを完全にリカバリし終わったと結論することができる。
【００７８】
実施の一形態によれば、ノードは、現在処理されているジェネレーションに属さないオーバヒアリングされたパケットを格納しておく二次バッファを備え得ることに留意すべきである。これらのジェネレーションは二次バッファに格納することができるが、それに対し一次バッファは現在リカバリされているジェネレーションのパケットを格納するために使用される。二次バッファに格納されたパケットは、現在扱っているジェネレーションが完全にリカバリ（復号）し終わった（そしてできれば一次バッファに移された）ところで使用することができる。
【００７９】
一度に１つのジェネレーションしか（“一次バッファ”または唯一つのバッファしか存在しない場合は“バッファ”に）保持することしかできないノードは、古い情報をバッファの底の方に縮小（shrink）して、新しいジェネレーションから受信されるパケット順に、新しいジェネレーションのリカバリを開始することができる。このようにして、ノードは、まだ古いジェネレーションを完全にリカバリし終わっていない近隣のノードを、その古いジェネレーションに属する古い情報を更に送信して支援することができる。同時に、古いジェネレーションのリカバリプロセスが終わったらすぐに、それらのノードが、既に受信し格納している新しい情報パケット（これらは例えば、新しいジェネレーションを格納またはバッファリングするために既にリカバリされたジェネレーション（の一部）から解放された非持続性メモリの一部に格納されていることがある）の処理を始めることをそれらのノードは保証している。
【００８０】
新しいジェネレーションのパケットは、古いジェネレーションのデータが現在保持されているバッファに書き込まれることがある。言及したように、古いジェネレーションは、新しいデータが入ってきたときに縮小され得る。古いジェネレーションデータは、メモリをより少なく占有し、より効率的に配信されるように、組み合わせた形または符合化（コーディング）された形で保持されることがある。これについては後でランダムアプローチの場合に関連して幾分より詳しく説明する。しかし、それは決定論的アプローチの場合にも利用することができる。
【００８１】
別の実施形態によれば、古いジェネレーションのデータを保持する目的で、一般にメモリ（例えばＲＡＭ）の一部を確保することも可能であり、このメモリの確保は、現在扱っているジェネレーションが完全にリカバリし終わった際にリカバリに使用され得る新しいジェネレーションのパケットを格納するために行われる。既に気付いているかもしれないが、基本的にこのメカニズムはランダム分散型アルゴリズム（この場合も新しいジェネレーションパケットは後の利用のためにバッファリングされる）に関連して後で説明するバッファと似ている。
【００８２】
実施の一形態によれば、ノードが、現在扱っているジェネレーションを完全にリカバリし終わったら、それらのノードは、そのジェネレーションを、通常はＲＡＭの数倍の容量を持つが読み出しと書き込みに要するエネルギー消費量がＲＡＭよりも大きなＦＬＡＳＨメモリのようなパーシスタントメモリに書き込む。しかしながら、長期のデータ収集では、ＦＬＡＳＨメモリがこれ以上更なるジェネレーションを保持できないという事態が生じる可能性がある。この点で、ノードは記憶領域を開放するためにどのジェネレーションをパーシスタントメモリから削除すべきかと、どのジェネレーションを保持するかを決定する場合がある。集中型の設定に基づく実施の一形態では、全てのクラスタヘッドによって事前に結ばれた合意に基づいて、各クラスタヘッドはクラスタ内の全てのノードのＦＡＬＳＨメモリからどのジェネレーションを削除すべきかを決定することができる。実施の一形態による別のシンプルなソリューションは、クラスタヘッドにクラスタ内のどのノードが或る特定のジェネレーションを削除すべきかを選ばせることである。これにより、単一クラスタ内に合理的に様々な利用可能なジェネレーションを維持することができる。
【００８３】
次に、ジェネレーションの管理がランダムアプローチに基づいて行われる実施形態を説明する。ここでの開始条件は、基本的には決定論的アプローチによるものと同じである。最初に、ノードがＮ個のクラスタ（例えばクラスタ１乃至クラスタＮ）に編成される。各クラスタは、特定のジェネレーションに対応している。従って、空間的に近いノードによって生成されたパケットは、同じジェネレーションに属する蓋然性が高い。各ノードは、同じジェネレーションに属する全てのパケットを保持することができるバッファを備えている。また異なるジェネレーションのオーバヒアリングされたパケットを格納するための更なる（一般的に必ずしも前者のバッファより小さくはない）バッファ（その他のバッファの一部または別個のもの）も存在する。
【００８４】
最初の発信（dissemination）フェーズにおいて、ノードはそれら自身のクラスタのジェネレーションに属するデータを処理する。これまでの決定論的アプローチと異なる点は、ジェネレーションの配信（distribution）が実行されるやり方である。ランダム分散型オプションでは、各ノードは更なるジェネレーションを、それ自身のバッファ状況、ポジションおよび能力といった基準に従って、また同じクラスタ内の他のノードと同期することなく、処理することを自立的に決定することができる。このようにして、完全に分散したジェネレーションの管理が実行でき、その結果、クラスタ構造を維持および同期する際に導入される余計な負担（オーバヘッド）が軽減される。
【００８５】
実施の一形態によれば、ノード間のジェネレーションの配信の管理は、オーバヒアリングしているノードに基づいている。例えば、それら自身のジェネレーションを処理しているノードは、異なるタイプ（異なるジェネレーション、例えば隣接するジェネレーション）のパケットをオーバヒアリングすることができる。それらのノードは、この情報を二次バッファに格納することができる。二次バッファに格納された情報ユニットに基づいて、ノードは、（それを復号し、符合化されたパケットを近隣のノードへ転送することによって）次に処理すべきジェネレーションを決定することができる。例えば、ノードは、そのほとんどの情報ユニット（またはパケット）がバッファの中に格納されたジェネレーションを、次に処理すべきものとして選ぶことができる。
【００８６】
次のジェネレーションの処理を開始すべき時の決定は、ノードが完全にその現在扱っているジェネレーションを処理（復号またはリカバリ）し終わったときに行われる場合がある。次いで、オーバヒアリングされたパケットが格納されているバッファのコンテント（content）に基づいて次のジェネレーションの処理を開始することがある。
【００８７】
斯かる実施形態は、分散型クラスタ形成を実装している。ノードがそれら自身のジェネレーションを処理し終わった後にそれらは別のパケットタイプを処理し始める。言及したように、その目的のため、オーバヒアリングしているノードは、二次バッファのコンテントを調べることによって、処理すべき次のノードを決定することができる。
【００８８】
しかしながら、ノードがその二次バッファにコンテントを一切持っていないことが起こる場合がある。二次バッファにパケットを持っていないノードに対しては、それらのノードがその対応する次のジェネレーションを開始することによってどのクラスタに加入すべきかを決定するための他の基準が必要とされる。１つのソリューションは、異なるジェネレーションからのパケットが受信されるまで待機することであり、このときこのパケットは処理すべき次のジェネレーションの最初のパケットとして選ばれる。言い換えると、次のジェネレーションは、このパケットが属するジェネレーションである。
【００８９】
上述のアプローチは、一種の“仮想クラスタローテーション”または“仮想クラスタ移動”を実装している。各ノードによって実行されるジェネレーション管理によれば、“仮想クラスタ”は、単一または複数の同じジェネレーションを処理しているノードによって形成される。
【００９０】
ノードは、そのメモリに複数のジェネレーション（現時点で処理している（そのデータを復号してそれをその他のノードへ転送することによって）ものと、オーバヒアリングから受信されるもの）のデータを保持する場合があることに留意すべきである。しかしながら、ノードは、現在扱っているジェネレーションの復号を完了した後にしか新しいジェネレーションの復号を開始しない。
【００９１】
次に更なる実施形態を幾分より詳しく説明する。
【００９２】
最初にオーバヒアリングしているノードによる分散型ジェネレーション管理について幾分より詳しく説明する。
【００９３】
ノードがそれ自身のジェネレーションの全てのパケットを収集し終わると、その最初のデータ発信フェーズは完了し、ノードは次のジェネレーションの処理を開始することができる。この最初のフェーズの最後においては、そのバッファのコンテントを図７にあるように表すことができる。メインバッファの中にノードはそれ自身のジェネレーション（ジェネレーション１）の全てのパケットを持ち、二次バッファの中にノードが異なるジェネレーション（ジェネレーション２および３）のオーバヒアリングされたパケットを持つ。これは例えば、境界ノード、つまり異なるジェネレーションのパケットを受信することができることからクラスタ間に置かれたノードで起こり得る。二次バッファの状況に基づいて、ノードはより多くのパケットがバッファに格納されているジェネレーションを処理することを決定することができる。例えば図７を参照すると、ジェネレーション２の方がジェネレーション３よりもバッファ内におけるパケットまたは情報ユニットが多いので、ノードは次のジェネレーションとしてジェネレーション２を選ぶことが理解できる。従って、ノードはジェネレーション３に属するパケットを二次バッファに残すことになる。この決定は、完全分散方式でなされることに留意すべきである。ノードは、近隣のノードと相互作用することなく、それら自身のバッファを見る必要があるだけである。その後、ノードは、選択したジェネレーションのパケットを、図７の右側に示すように最初のバッファポジションに上書きすることによってメインバッファに移動させる。
【００９４】
実施の一形態によれば、新しいジェネレーション（ジェネレーション２）のパケットが次に配置されることになる位置に格納されているジェネレーション１のパケットは、捨てはされないが、しかし、それらは、同じジェネレーションの１つ以上の他のパケットと組み合わされる（つまりそれらは“符合化”される）。例えば、新しいジェネレーション２のパケットで置きかえられるパケットは、ジェネレーション１の他のパケットと組み合わされることがあり、このようにしてメインバッファに、少なくともしばらくの間、保持されることがある。それらはまた他のノードへ配信することができ、このようにして、まだ完全にジェネレーション１をリカバリし終わっていない他のノードをジェネレーション１のリカバリを完了することによって手助けすることができる。これは決定論的アプローチの場合に図５と図６に関連して説明してきたメカニズムと似ている。この場合も同じく、古いジェネレーションパケットは依然として保持され、その古いジェネレーションが格納されるバッファサイズは、新しいジェネレーションのためのスペースを空けるために縮小される。
【００９５】
古いパケットの保持は、まず最初にスペースを確保し、第２に古いパケットの配信性能を改善するために、符合化された形式で行われることがある。置換されるパケットは、実施の一形態によれば、古いジェネレーションデータがまだ保持されており且つ新しいデータが入ってこない最後の位置にあるパケットと組み合わされることがある。
【００９６】
新しいジェネレーションの処理が進むにつれ、図７の右側のジェネレーション１および２の関係はジェネレーション２が占めるスペースが（このジェネレーションからより多くのパケットが入ってくるにつれ）増大し、ジェネレーション１が占めるスペースが減少するように変化し得る。
【００９７】
図７の右側に示されるように、次のジェネレーションがメインバッファに移動し終わったら、そのノードのメインバッファ内には２つのジェネレーションに属するパケットが存在する。この手続きは２つの異なるジェネレーションの発信（dissemination）を双方向に支援する利益を有する。このコンセプトをよりうまく説明するために図８を参照する。図８において、いくつかの異なるノードは、それらのバッファを用いて表現されている。メインバッファに２つのジェネレーションを格納している中間ノードは、ジェネレーション１を一方向に送信し、ジェネレーション２を反対方向に送信することができる。
【００９８】
図８を参照してこの手続きを更に詳しく説明する。２つのクラスタが示されている。１つのクラスタはノードＡ、Ｂ、ＣおよびＤを有し、もう１つのクラスタはノードＥ、Ｆ、Ｇ、およびＨを有する。パケット１、２、３、および４はジェネレーション１（最初にクラスタ１によって処理される）に属し、パケット５、６、７、および８はジェネレーション２（最初にクラスタ２によって処理される）に属する。
【００９９】
図８は各クラスタがそれ自身のジェネレーションを完全に復号し終わった後に生じる、新しいジェネレーションの処理を開始する状況を示している。例えば、ノードＣ（クラスタ１に属する）はジェネレーション２に属するパケットを受信し、このパケットはノードＣのメインバッファ内においてパケット１と置き換わる。代わりにパケット１はパケット２と符合化され、符合化されたパケットはノードＣによって更に配信することが可能である。しかしながら、ノードＣは、今度は主にジェネレーション２のパケットの処理を開始する。
【０１００】
ノードＤは、ノードＣよりも既に１ステップだけ先に進んでいる。ノードＤの場合、メインバッファの２つの場所がジェネレーション２のパケットで満たされている。図からわかるように、パケット１乃至４は、今後さらに配信されて他のノードがジェネレーション１のリカバリを完了するのを支援するために、全てメインバッファ内で符合化されている。
【０１０１】
ノードＥおよびＦについても、それらがクラスタ２に属し、ジェネレーション２を完全に処理し終わっており、いまや新しいジェネレーション（つまりジェネレーション１）を処理する準備ができていることを除けば、状況は同様である。ノードＥは既にメインバッファの２つの場所でジェネレーション１のパケットを有しており、ノードＦはジェネレーション１の唯１つのパケットを有していることは見て取れる。従って、ノードＦは、ある意味でノードＣを“鏡に映したもの”であり、ノードＥは、ノードＤを“鏡に映したもの”である。
【０１０２】
両方のクラスタは、新しいジェネレーションの処理を開始したが、図８に示すように、両方のクラスタは、それぞれの古いジェネレーションのパケットを反対方向に配信する。
【０１０３】
実施の一形態によるオーバヒアリングしているノードは、処理すべき次のジェネレーションは何かを決定するために使用することができる。しかし、このタスクは他のジェネレーションのパケットをオーバヒアリングしないノードにとっては困難な可能性がある。実施の一形態によるこの問題に対する１つのソリューションとしては、シンプルな決定規則を規定することが挙げられる。ノードがそれ自身のジェネレーションの全てのパケットを収集し終わったときに次のジェネレーションを処理するための準備が整うが、二次バッファが空の場合にはそのノードは他のジェネレーションからの何らかのパケットまたは何らかの組み合わされたパケットの受信を待機する。これらの組み合わされたパケットは既に２つのジェネレーションを処理している近隣のノードから到来し得るものである。これらの組み合わされたパケットの最初のものを受信したときにノードはその中に含まれるジェネレーションを処理することを決定することができる。
【０１０４】
次に処理すべきジェネレーションの決定フェーズの最後において、オーバヒアリングしているノードとその他のノードは双方ともノードによって処理されるべき次のジェネレーションはどれかを決定し終わっている。従って、あるノードはジェネレーション１とジェネレーション２のパケットを配信し、他のノードはジェネレーション２とジェネレーション３のパケットを配信する、等々と言った具合である。これによりノードのクラスタへの再編成のようなものが行われる。これらのクラスタは、発信プロセスの初めに定義される空間クラスタに対応していないので、仮想クラスタと呼ぶことができる。特に、それら仮想クラスタは各ノードの独立した決定によって分散型方式で形成される。これについて図９を参照して説明する。図９において、オリジナルのクラスタ編成が示されており、その上で可能な仮想クラスタ構造が描かれている。仮想クラスタ内のデータ発信が最初のデータ発信のフェーズで行われたように実行される。ノードが第２のジェネレーションの全てのパケットを収集し終わると、そのノードは第３のジェネレーションを処理することを決定する、等々といった具合である。これらの一連のフェーズは再び仮想リクラスタリングをもたらす。仮想クラスタは同じジェネレーションを処理するノードによって形成される。
【０１０５】
実施の一形態によれば、合理的なサイズの仮想クラスタを保持するためのメカニズムが提供される。実施の一形態によれば、１つのソリューションは（同じジェネレーションを収集している）アクティブノード間の最も遠い距離を（モニタすることにより）考慮し、それを計算または事前に定義された決まった閾値未満に保つことである。これは、各ジェネレーションごとに、同じジェネレーションで符合化している（ホップ数で）最も遠いノードについての情報を管理するカウンタを保持することによって可能となる。新しいノードは、現在設定されている仮想クラスタの届く範囲の境界で含まれることがあり、そのクラスタの他端にあるノードがこのジェネレーションを復号し終わったならば、言い換えると、これらのノードがこのクラスタを定義するジェネレーションの復号をやめることによって実際にこのクラスタを“離脱する”場合、それをＦＬＡＳＨメモリに格納し、そこからのパケットの送信を停止する。新しいノードは、このクラスタの他端にある対応するノードが離脱した場合または最も遠いノードまでの距離がまだ閾値未満である場合に、このジェネレーションの復号または処理を開始することによってこのクラスタに入ることができる。新しいノードが加入することで設定された閾値を超えるような場合には、そのノードの加入は１つ以上のノードがクラスタを“離脱”して閾値がもはや破られないようになるまで延期され得る。
【０１０６】
実施の一形態によれば、ノードが、現在扱っているジェネレーションを完全にリカバリし終わったところで、それらのノードは、その現在扱っているジェネレーションをＦＬＡＳＨメモリといったパーシスタントメモリに書き込む。しかしながら、データ収集が長期に及ぶ場合、ＦＬＡＳＨメモリはもうこれ以上新しいジェネレーションを保持することができない事態が起こる可能性がある。この点を鑑み、ノードは、どのジェネレーションを削除すべきかと、どのジェネレーションを斯かるメモリに保持しておくべきかとを決定すべきである。実施の一形態によれば、各ノードは、例えばシンプルな規則に基づいて、どのジェネレーションをＦＬＡＳＨから削除すべきかを決定することができる。実施の一形態によれば、或るジェネレーションが削除されるものとして選ばれる確率を意味するカウンタが使用される。斯かるカウンタは、ジェネレーションがＦＬＡＳＨメモリに書き込まれるとゼロ（削除される確率はヌルであることを意味する）に設定される。次に、各タイムスロットごとに、カウンタはその値を１（カウンタに許された最大値）に向かってわずかな数だけ増大させる。ノードは、近隣のノードが或る特定のジェネレーションを削除したことをオーバヒアリングし、斯かるジェネレーションがそのＦＬＡＳＨメモリに招かれた場合には、ノードは対応するカウンタを決められたわずかな数だけ減らす。このようにして、ノードは近隣のノードによってまだ削除されていない古いジェネレーションを高い確率で削除し、合理的に様々な利用可能なジェネレーションがローカルに保証される。
【０１０７】
別の実施形態は、ノードがそれらの近隣のノードにどのジェネレーションが削除されるかを知らせずに、ノードにランダムに削除すべきジェネレーションを選ばせるものである。このようにして余計な負担（オーバヘッド）が避けられるが、しかしながらネットワークの特定エリアに様々な利用可能なジェネレーションが存在するということはあまり好ましくない場合もある。
【０１０８】
次に、本発明の実施形態を適用することができるいくつかの例示的なシナリオを説明する。
【０１０９】
最初のシナリオとしては、セルラネットワークの場合である。携帯電話機を所持するエンドユーザは一定量のデータ（感知データ）を収集し、たいていの場合には斯かるデータを最も近いＷＬＡＮアクセスポイントへ送信する（低コスト）。問題は利用可能なホットスポットが数キロメートル範囲内に存在しない場合である。このため、どの古いデータを削除すべきかを選ぶ必要のあるそのユーザにとって新しいデータのためにより多くのスペースを確保しなければならないことは難しい問題であろう。ＲＡＭ＋ＦＬＡＳＨにアクセス可能なことは最初のフェーズでは役に立つが、そのうちに容量を使い切ってしまう可能性があるということは新たな問題である。この点を鑑み、そのエリア内にあるセルラセンサと斯かるデータを共有することで、収集された全てのオリジナルデータの期待ライフタイムを、ホットスポットまたは基地局／サーバに届くまで、再延長することが可能となる。同じことが斯かるユーザが別のセルに移動するような場合に起こる。このとき、以前にいたクラスタセルにおいて取得された感知データを生かしておくため、ユーザは斯かる情報を複製し、その情報をクラスタ内のその他のノードと離脱する前に共有すべきである。これは、本発明の実施形態を使用することによって達成可能である。
【０１１０】
別の適用シナリオとしては、セルラセンサネットワークの場合である。居住環境の監視、例えば無線センサネットワーク（ＷＳＮ）の２つの運用の用途において、長期にわたるデータ収集は不可欠である。寿命、データの信頼度および存続性は、斯かる用途をサポートするために、且つ、例えば洪水、地震、火災などの緊急実態における人々の救出に関する問題に直面したときなどに、どの行動をとるべきかをエンドユーザに迅速に知らせるためには欠かせない。このため、大規模ＷＮ（無線ネットワーク）におけるデータ管理のためのエネルギー効率の高いメカニズムが広範囲の実際および将来のＷＳＮ用途に本当に適しており、斯かる用途に本発明の実施形態を使用することが可能である。
【０１１１】
上記の実施形態は、ハードウェア、ソフトウェア、あるいはハードウェアとソフトウェアの組み合わせによって実施することができることは当業者であれば理解できるだろう。本発明の実施形態に関連して説明されたモジュールおよび機能は、全体的または部分的に、本発明の実施形態に関連して説明されたやり方の通りに動作するように適切にプログラムされたマイクロプロセッサまたはコンピュータによって実現することができる。本発明の実施形態を実現する装置は、例えば、本発明の実施形態で説明された方法を実行することが可能なように適切にプログラムされた計算機または携帯電話機その他のモバイル機器（例えば無線センサ）を構成することができる。
【０１１２】
本発明の実施の一形態として、データキャリアに格納された、あるいは他の方法で記録媒体もしくは伝送リンクといった何らかの物理的手段によって具現化されたコンピュータプログラムであって、コンピュータ上で実行する際にこのコンピュータが上記実施形態に従って動作することを可能にするコンピュータプログラムが提供される。
【符号の説明】
【０１１３】
Ａ〜Ｈ  ネットワークノード
【図１Ａ】
0004764475.tif 000002
【図１Ｂ】
0004764475.tif 000003
【図２】
0004764475.tif 000004
【図３】
0004764475.tif 000005
【図４】
0004764475.tif 000006
【図７】
0004764475.tif 000007
【図８】
0004764475.tif 000008
【図５】
0004764475.tif 000009
【図６】
0004764475.tif 000010