センサネットワーク構築装置および方法、並びにプログラム
【課題】複数のセンサでセンシングしたセンサデータを少ない遅延で並行して効率よく収集する。
【解決手段】センサネットワーク構築装置３０において、最小送信電波強度収集装置３２で、各センサノード１０から最小送信電波強度値を収集し、評価値算出装置３３で、これら最小送信電波強度値に基づき、任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出し、クラスタリング処理装置３４で、これら評価値に基づき階層ごとにクラスタ構成を決定することにより、センサネットワーク５０のトポロジを決定し、ネットワーク設定装置３５で、このトポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、センサネットワーク５０を介して各センサノード１０へ通知する。
【解決手段】センサネットワーク構築装置３０において、最小送信電波強度収集装置３２で、各センサノード１０から最小送信電波強度値を収集し、評価値算出装置３３で、これら最小送信電波強度値に基づき、任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出し、クラスタリング処理装置３４で、これら評価値に基づき階層ごとにクラスタ構成を決定することにより、センサネットワーク５０のトポロジを決定し、ネットワーク設定装置３５で、このトポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、センサネットワーク５０を介して各センサノード１０へ通知する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ収集技術に関し、特に複数のセンサから無線通信を介してセンサデータを収集する技術に関する。
【背景技術】
【０００２】
一般に、センサノードがネットワークを構成してデータを収集するような通信ネットワークをセンサネットワークと呼んでいる。これまで、センサネットワークを構成するノードとして特許文献１のようなデバイスが提案されているが、この例ではネットワーク上の通信のやり取りについては詳しく定義されていない。ネットワークの構築に関しては、非特許文献１や非特許文献２に代表されるように、ネットワークインフラがない広大な場所において、ノード間でデータを転送し合うさまざまな手法が提案されている。
【０００３】
しかし、屋内にセンサノードを配置することを想定した場合、このような屋内型のセンサネットワークにおいては、限られた範囲に多数のセンサノードが配置される。したがって、ほぼすべてのセンサノードが互いに通信可能であることから、無線の干渉を避けてネットワークを構築する必要がある。このため、既存技術を屋内型のセンサネットワークにそのまま適用することはできない。
【０００４】
最近では、無線の送信電力を調整できる無線通信モジュールが普及してきている。このようなデバイスを想定し、すべてのノードはお互いに通信可能であるが、省電力性や通信の効率向上のために、送信電波強度を動的に変更してクラスタを生成し、効率よくデータを収集するための研究がなされている。
その１つとして、非特許文献３に示すＬＥＡＣＨがある。この研究では、送信電力が送信先までの距離の２乗に比例するという前提に基づき、マルチホップを利用して省電力を実現している。しかし、屋内型センサネットワークにおける近距離無線では、無線の電波の送信よりも受信に電力が必要であるため、既存の省電力のための手法をそのまま屋内型センサネットワークに適応しても省電力にならず、無線の干渉を避けることも主な目的とはされていない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−２０８７１９号公報
【非特許文献】
【０００６】
【非特許文献１】D. B. Johnson and D. A. Maltz: Dynamic Source Routing in Ad Hoc Wireless Networks, in Proc, of Mobile Computing 1996, 1996.
【非特許文献２】C. E. Perkins and E. M. Royer: Ad-hoc On-Demand Distance Vector Routing, in Proc. of WMCSA1999, 1999.
【非特許文献３】W. R, Heinzelman, A. Chandrakasan, and H. Balakrishnan: Energy-Efficient Communication Protocol for Wireless Microsensor Networks, In Proc. of 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, 2000.
【非特許文献４】R. T. Ng and J. Han: Efficient and Effective Clustering Methods for Spatial Data Mining, in Proc. of VLDB'94, pp.144-155, 1994.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
屋内型センサネットワークにおいて、センサノードが多数存在するときに、これらセンサノードでセンシングしたセンサデータを、少ない遅延で並行して効率よく基地局に収集することが重要となる。ここで、遅延とは、状況が変化してセンサデータが発生してから基地局にデータが到達するまでの所要時間を指す。また、送信するデータ量を抑えて多数のノードからデータを収集できるよう、センサノードは周囲の状況が変化したときにのみセンサデータを送信するものとする。
【０００８】
無線通信によって多数のセンサノードからデータを収集することを考えると、まず単純な方法として、ポーリングによる手法と時分割多重による方法が挙げられる。ポーリングでは、基地局が各ノードに対してデータを要求するパケットを送信し、パケットを受信したノードがセンサデータを基地局に返信することで、データを収集できる。
センサノードでの実装は単純で実現は容易であり、確実にデータを収集できる。しかし、ノード１台ずつに順にデータを要求するため、データが発生してからデータが基地局に収集されるまでの遅延が大きくなる。さらにイベント駆動型センサを利用するため、センサデータが発生していないノードにもデータを要求しなければならず、効率が悪い。
【０００９】
例えば、時分割多重方式では、各ノードにタイムスロットを割り当て、ノードが割り当てられた時間に基地局へデータを送信することで、無線通信の衝突を避けながらデータを収集できる。しかし、均一にタイムスロットをノードに割り当てると、送信するセンサデータの量はセンサの種類と周囲の状況によって変化するため、データが発生していないときにもタイムスロットが割り当てられる可能性が高く、無駄な時間が多い。センサデータの量に応じて動的にタイムスロットを割り当てるような手法も考えられるが、センサデータの発生量を予測することは不可能である上に、実装も困難である。さらに、時分割多重は時刻の同期が必要なため計算機リソースの限られるセンサノードでは実装しにくいという問題もある。
【００１０】
本発明はこのような課題を解決するためのものであり、複数のセンサでセンシングしたセンサデータを少ない遅延で並行して効率よく収集できるセンサデータ収集システム、方法、プログラム、および記録媒体を提供することを目的としている。
【課題を解決するための手段】
【００１１】
このような目的を達成するために、本発明にかかるセンサネットワーク構築装置は、複数の階層を有するセンサネットワークを無線通信により構成する複数のセンサノードと、各センサノードでセンシングした当該センサノードの周囲状況を示すセンサデータをセンサネットワークを介して収集する基地局とを含み、センサネットワークは、階層ごとに１つ以上のクラスタを有し、任意のセンサノードからなる１つ以上の子ノードと１つのクラスタヘッドとからクラスタが構成され、当該クラスタ内の子ノードとクラスタヘッドとが無線通信を行うとともに、クラスタヘッドが１つ上位の階層における任意の上位クラスタの子ノードとして動作し、最上位階層に構成する１つのクラスタのクラスヘッダが基地局からなる、階層クラスタ構造を有するセンサデータ収集システムにおいて、各センサノードで検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、センサネットワークを介してそれぞれ収集する最小送信電波強度収集装置と、これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出装置と、階層ごとに複数選択したクラスタ構成について評価値算出装置で評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、センサネットワークのトポロジを決定するクラスタリング処理装置と、トポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、センサネットワークを介して各センサノードへ通知するネットワーク設定装置とを備えている。
【００１２】
この際、クラスタリング処理装置で、任意の階層についてクラスタ構成を決定する際、当該階層に含まれるノードからランダムにサンプルノードを選択し、このサンプルノードから各クラスタのクラスタヘッドをそれぞれ任意に選択し、クラスタ以外のサンプルノードを当該サンプルノードから最も小さい電波強度で通信可能なクラスタヘッドのクラスタにそれぞれ割り当てて当該階層の基準となるクラスタ構成を生成して、評価値算出装置により基準クラスタ構成に関する基準評価値を算出し、基準クラスタ構成のうちクラスタヘッド以外のサンプルノードからランダムに選択して当該クラスタのクラスタヘッドと入れ替えた候補クラスタ構成を順次生成して、評価値算出装置により候補クラスタ構成に関する候補評価値を算出し、候補評価値のうち最も小さい最小候補評価値と基準評価値とを比較し、いずれか小さい方のクラスタ構成を当該階層のクラスタ構成として決定するようにしてもよい。
【００１３】
また、本発明にかかるセンサネットワーク構築方法は、複数の階層を有するセンサネットワークを無線通信により構成する複数のセンサノードと、各センサノードでセンシングした当該センサノードの周囲状況を示すセンサデータをセンサネットワークを介して収集する基地局とを含み、センサネットワークは、階層ごとに１つ以上のクラスタを有し、任意のセンサノードからなる１つ以上の子ノードと１つのクラスタヘッドとからクラスタが構成され、当該クラスタ内の子ノードとクラスタヘッドとが無線通信を行うとともに、クラスタヘッドが１つ上位の階層における任意の上位クラスタの子ノードとして動作し、最上位階層に構成する１つのクラスタのクラスヘッダが基地局からなる、階層クラスタ構造を有するセンサデータ収集システムにおいて、最小送信電波強度収集装置が、各センサノードで検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、センサネットワークを介してそれぞれ収集する最小送信電波強度収集ステップと、評価値算出装置が、これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出ステップと、クラスタリング処理装置が、階層ごとに複数選択したクラスタ構成について評価値算出装置で評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、センサネットワークのトポロジを決定するクラスタリング処理ステップと、ネットワーク設定装置が、トポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、センサネットワークを介して各センサノードへ通知するネットワーク設定ステップとを備えている。
【００１４】
この際、クラスタリング処理装置で、任意の階層についてクラスタ構成を決定する際、当該階層に含まれるノードからランダムにサンプルノードを選択し、このサンプルノードから各クラスタのクラスタヘッドをそれぞれ任意に選択し、クラスタ以外のサンプルノードを当該サンプルノードから最も小さい電波強度で通信可能なクラスタヘッドのクラスタにそれぞれ割り当てて当該階層の基準となるクラスタ構成を生成して、評価値算出装置により基準クラスタ構成に関する基準評価値を算出し、基準クラスタ構成のうちクラスタヘッド以外のサンプルノードからランダムに選択して当該クラスタのクラスタヘッドと入れ替えた候補クラスタ構成を順次生成して、評価値算出装置により候補クラスタ構成に関する候補評価値を算出し、候補評価値のうち最も小さい最小候補評価値と基準評価値とを比較し、いずれか小さい方のクラスタ構成を当該階層のクラスタ構成として決定するようにしてもよい。
【００１５】
また、本発明にかかるプログラムは、コンピュータを、前述したいずれか１つセンサネットワーク構築装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１６】
本発明によれば、センサノードを階層的にクラスタリングすることで、多数のノードから、少ない遅延で並行して効率よくセンサデータを収集できる。多数の箇所でセンシングを行いたい場合であっても、本発明を用いると理想的には１台の基地局を設置するのみで容易にセンサネットワークが構築できるようになるため、一般家庭などへセンサネットワークを普及させる上で効果的である。多数のセンサノードを用いてセンシングを行うときに、本発明を用いれば、遅延を一定以下に抑えながら、すべてのノードから効率よくデータを収集できる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施の形態にかかるセンサデータ収集システムの構成を示すブロック図である。
【図２】センサノードの構成例を示すブロック図である。
【図３】基地局の構成例を示すブロック図である。
【図４】ネットワーク構築装置の構成例を示すブロック図である。
【図５】センサネットワークの階層クラスタ構造例を示す説明図である。
【図６】本実施の形態にかかるセンサデータ収集システムのデータ集約処理を示すフローチャートである。
【図７】階層クラスタ構造の一例を示すトポロジである。
【図８】本実施の形態にかかるセンサデータ収集システムのクラスタリング処理を示すフローチャートである。
【図９】クラスタリング処理の一例を示す説明図である。
【図１０】本実施の形態にかかるセンサデータ収集システムの評価結果を示す説明図である。
【図１１】評価に用いたトポロジを示す説明図である。
【発明を実施するための形態】
【００１８】
次に、本発明の実施の形態について図面を参照して説明する。
［センサデータ収集システム］
まず、図１を参照して、本発明の一実施の形態にかかるセンサデータ収集システムについて説明する。図１は、本発明の一実施の形態にかかるセンサデータ収集システムの構成を示すブロック図である。図２は、センサノードの構成例を示すブロック図である。図３は、基地局の構成例を示すブロック図である。図４は、ネットワーク構築装置の構成例を示すブロック図である。
【００１９】
このセンサデータ収集システム１は、無線通信網からなるセンサネットワーク５０で相互に接続された、複数のセンサノード１０、基地局２０、ネットワーク構築装置３０を含み、各センサノード１０のセンサでセンシングしたセンサデータを、センサネットワーク５０を介して基地局２０へ並行して収集する機能を有している。このうち、ネットワーク構築装置３０については、センサネットワーク５０の構築時にのみ必要となる構成であり、その後のセンサデータ収集時には不要となる。また、このネットワーク構築装置３０の機能を基地局２０で実現してもよい。
【００２０】
センサノード１０には、図２に示すように、周囲の状況をセンシングしセンサデータとして出力するセンサ１１と、センサ１１から出力されるセンサデータに変化があったことをイベントとして検出するセンサイベント検出装置１２と、無線通信用送信キューとして送信すべきセンサデータを記憶するセンサデータ記憶装置１４と、センサイベント検出装置１２でイベントを検出した際のセンサデータを処理してセンサデータ記憶装置１４へ保存するセンサデータ処理装置１３と、他のセンサノード１０や基地局２０と無線通信を行うことによりセンサデータなどの各種データを送受信するとともに、送信電波の強度を多段階に調整でき、他センサノードとの間で最小送信電波強度を検出する無線通信装置１５とが設けられている。
【００２１】
センサノード１０を構成するセンサ１１、センサイベント検出装置１２、センサデータ処理装置１３、センサデータ記憶装置１４、および無線通信装置１５については、それぞれ別個の装置から実現した場合を例として説明するが、これらのうち複数の装置を１つの装置で実現してもよい。また、これら装置での内部処理については、専用の信号処理回路で実現してもよく、コンピュータでＣＰＵなどの演算処理装置とプログラムとを協働させてなる個々の機能処理装置で実現してもよい。
【００２２】
基地局２０には、図３に示すように、センサノード１０と無線通信を行うことによりセンサデータなどの各種データを送受信する無線通信装置２１と、無線通信装置２１で受信したセンサデータを集約して上位装置（図示せず）へ出力する受信データ処理装置２２とが設けられている。
基地局２０を構成する無線通信装置２１および受信データ処理装置２２については、それぞれ別個の装置から実現した場合を例として説明するが、これらのうち複数の装置を１つの装置で実現してもよい。また、これら装置での内部処理については、専用の信号処理回路で実現してもよく、コンピュータでＣＰＵなどの演算処理装置とプログラムとを協働させてなる個々の機能処理装置で実現してもよい。
【００２３】
ネットワーク構築装置３０には、図４に示すように、センサノード１０と無線通信を行うことによりセンサデータなどの各種データを送受信する無線通信装置３１と、各センサノード１０で検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、センサネットワーク５０を介してそれぞれ収集する最小送信電波強度収集装置３２と、これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出装置３３と、階層ごとに複数選択したクラスタ構成について評価値算出装置３３で評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、センサネットワークのトポロジを決定するクラスタリング処理装置３４と、このトポロジに基づいて個々のセンサノード１０に関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、センサネットワーク５０を介して各センサノード１０へ通知するネットワーク設定装置３５とが設けられている。
【００２４】
ネットワーク構築装置３０を構成する無線通信装置３１、最小送信電波強度収集装置３２、評価値算出装置３３、クラスタリング処理装置３４、およびネットワーク設定装置３５については、それぞれ別個の装置から実現した場合を例として説明するが、これらのうち複数の装置を１つの装置で実現してもよい。また、これら装置での内部処理については、専用の信号処理回路で実現してもよく、コンピュータでＣＰＵなどの演算処理装置とプログラムとを協働させてなる個々の機能処理装置で実現してもよい。
【００２５】
これにより、センサノード１０では、周囲の状況の変化によるセンサデータの変化がイベントとしてセンサデータ処理装置１３により検出されると、その変化を示すセンサデータが無線通信装置１５を介して基地局２０へ送信される。基地局２０では、このようにして各センサノード１０でセンシングしたセンサデータを無線通信装置２１で受信し、受信データ処理装置２２で集約して出力する。
【００２６】
［センサネットワーク］
次に、図５を参照して、本実施の形態にかかるセンサデータ収集システムのセンサネットワークについて説明する。図５は、センサネットワークの階層クラスタ構造例を示す説明図である。
センサネットワーク５０は、複数の階層を有するとともに、階層ごとに１つ以上のクラスタが設けられている階層クラスタ構造をなしている。
【００２７】
図５の例では、最下位階層ＬL、中間階層ＬM、最上位階層ＬHの３つの階層から構成されており、これら階層ごとに１つ以上のセンサノード１０からなるクラスタが１つ以上設けられている。なお、実際のセンサネットワーク５０において、階層数は３に限定されるものではなく、少なくとも最下位階層ＬL、最上位階層ＬHの２つの階を含み、センサノード１０の数やクラスタの数に応じて、中間階層ＬMを増加させればよい。
【００２８】
最下位階層ＬLでは、各センサノード１０は位置的に近くに存在する他のセンサノード１０とともにクラスタをそれぞれ生成し、クラスタごとにその中の１台のセンサノード１０にデータを集約する。各クラスタにおいてデータが集約されるセンサノード１０を当該クラスタのクラスタヘッドと定義する。また、各クラスタに属するセンサノード１０のうちクラスタヘッド以外のセンサノード１０を子ノードという。
【００２９】
各クラスタ内の無線通信については、当該クラスタの子ノードからクラスタヘッドにセンサデータが送信できれば十分であるため、無線送信の電波強度を制限して微弱な電波で無線通信を行うことができる。これにより、クラスタ間での電波の干渉を低減でき、各クラスタにおいて並行してデータ収集を行うことが可能となる。
【００３０】
中間層ＬMおよび最上位階層ＬHのクラスタの子ノードは、１段下の階層における各クラスタのクラスタヘッドから構成されており、階層ごとにこのようなクラスタ構成が繰り返し形成されている。これにより、階層が上がるごとにそれぞれのクラスタでデータが順次集約される。
最上位階層ＬHのクラスタは、基地局２０をクラスタヘッドとする１つのクラスタから構成されており、このクラスタの子ノードは、中間層ＬMの各クラスタのクラスタヘッドから構成されている。このため、最終的には最上位階層ＬHの基地局２０に対してすべてのセンサノード１０からセンサデータが集約される。
【００３１】
また、この階層クラスタ構造では、各階層で異なる通信チャネルを使用する。図５の例では、最下位階層ＬL、中間階層ＬM、最上位階層ＬHごとに、通信チャネルＣｈL，ＣｈM，ＣｈHを用いる。これにより、階層間での無線通信の干渉がなくなり、各階層で独立してデータを収集できる。
本実施の形態では、このような階層クラスタ構造を用いることで、各センサノード１０でセンシングしたセンサデータを少ない遅延で並行して効率よく収集している。これにより、ポーリングを用いる手法とは異なり、効率よくデータが収集できる。また、時分割多重を用いる方法と異なり、実装もシンプルで容易に導入可能である。
【００３２】
なお、本実施の形態では、通信帯域が溢れるほどのデータは発生しないものとする。また、センサノード間の距離は、位置取得センサを用いるのではなく、電波の強度を利用して計測するものとする。具体的には、あるセンサノードから送信電波強度を変化させて複数のパケットを送信し、受信側では、受け取ったパケットのうち最小の電波強度を距離とする。
【００３３】
［データ収集方法］
次に、図６および図７を参照して、本実施の形態にかかるセンサデータ収集システムのデータ集約方法について説明する。図６は、本実施の形態にかかるセンサデータ収集システムのデータ集約処理を示すフローチャートである。図７は、階層クラスタ構造の一例を示すトポロジである。
【００３４】
最下位階層ＬLのクラスタでは、各子ノードの持つセンサデータをクラスタヘッドに集約する。この際、クラスタヘッドは、まず、無線通信装置１５において通信チャネルとして最下位階層ＬLのチャネルＣｈLを選択し、クラスタ内の子ノードへデータ要求メッセージを送信する。子ノードは、無線通信装置１５において通信チャネルとしてチャネルＣｈLを選択しており、クラスタヘッドからデータ要求メッセージを受信した子ノードは、その時点で自身の送信キューに格納されているセンサデータをクラスタヘッドへ送信する。送信キューが空であれば、何も送信しない。
【００３５】
クラスタヘッドは、無線通信装置１５により各子ノードからデータを受信して収集した後、通信チャネルを１段上の中間階層ＬMのチャネルＣｈLに切り替え、この中間階層ＬMのクラスタヘッドからデータ要求メッセージが送られるのを待つ。データ要求を受信すると、クラスタヘッドは、最下位階層ＬLの子ノードから収集したセンサデータを、前述した最下位階層ＬLの子ノードと同様にして中間階層ＬMのクラスタヘッドへ送信する。このようにして、すべての階層のクラスタでこの処理が繰り返し実行され、最上位階層ＬHにある基地局２０にデータが集約される。また、各階層のクラスタヘッドも他の子ノードと同じくセンシングを行っているため、子ノードから収集したセンサデータを上位階層へ送信する際、自身がセンシングしたセンサデータも付加して送信する。
【００３６】
次に、図６を参照して、任意の階層に属するセンサノードのデータ集約処理について説明する。図６において、最下位階層ＬLから上にｍ番目の階層におけるｉ番目の子ノードをＮciとし、そのクラスタヘッドをＮpとし、当該階層で用いる通信チャネルをＣｈmとし、１段上のｍ＋１番目の階層で用いる通信チャネルをＣｈm+1とし、子ノードＮciへの送信電波強度をＥciとし、クラスタヘッドＮpへの送信電波強度をＥpとする。
【００３７】
センサノード１０は、ループ１として、ループ２を含むステップ１０１〜１０７を繰り替えし実行している。ループ１では、まず、センサデータ処理装置１３により、センサイベント検出装置１２でイベントを検出した際のセンサデータを処理して送信キューであるセンサデータ記憶装置１４へ追加保存し（ステップ１０１）、無線通信装置１５により、通信チャネルをＣｈmに設定し（ステップ１０２）、子ノード選択用変数ｉを０に初期化する（ステップ１０３）。
【００３８】
次に、センサノード１０は、変数ｉが子ノード数ｎに達するまで、ステップ１１１〜１１５からなるループ２を繰り返し実行する。ループ２では、まず、無線通信装置１５により、送信電波強度をＥciに設定し（ステップ１１１）、子ノードＮciに対してデータ要求メッセージを送信した後（ステップ１１２）、子ノードＮciからのデータ受信待ちとなる（ステップ１１３）。
ここで、所定の待ち時間が経過するまでに子ノードＮciからデータを受信した場合（ステップ１１３：ＹＥＳ）、無線通信装置１５により、その受信データを送信キューへ追加保存し（ステップ１１４）、変数ｉを１だけ加算する（ステップ１１５）。また、ステップ１１３において、データ要求メッセージの送信から待ち時間が経過するまでに子ノードＮciからデータを受信できなかった場合（ステップ１１３：ＮＯ）、ステップ１１５へ移行する。
【００３９】
このようにして、すべての子ノードについてループ２を繰り返し実行することにより、各子ノードからセンサデータを収集して送信キューに保存した後、センサノード１０は、無線通信装置１５により、通信チャネルをＣｈm+1に設定するとともに（ステップ１０４）、送信電波強度をＥpに設定し（ステップ１０５）、クラスタヘッドＮpからのデータ要求メッセージの受信待ちとなる（ステップ１０６）。
【００４０】
ここで、所定の待ち時間が経過するまでにクラスタヘッドＮpからのデータ要求メッセージを受信した場合（ステップ１０６：ＹＥＳ）、無線通信装置１５により、送信キューに保存されている各子ノードから収集したセンサデータ、さらには自身でセンシングしたセンサデータをクラスタヘッドＮpへ送信し（ステップ１０７）、ループ１の先頭であるステップ１０１へ戻る。また、ステップ１０６において、待ち時間が経過するまでにクラスタヘッドＮpからのデータ要求メッセージを受信できなかった場合（ステップ１０６：ＮＯ）、ループ１の先頭であるステップ１０１へ戻る。
【００４１】
したがって、このデータ集約処理では、各センサノードにおいて、自身のセンシング結果と他のノードから受信したセンシング結果がセンサデータ記憶装置１４の中の送信キューで管理され、送信要求があったときには送信キューに保存されているセンサデータがすべて送信される。また、ループ２のデータ収集処理とステップ１０２の通信チャネル変更処理については、子ノードが存在するときにだけ実行される処理であり、当該センサノードが子ノードを持たない場合、これら処理は実行されない。
【００４２】
次に、図７を参照して、センサデータの集約手順の具体例について説明する。図７のトポロジ例では、階層Ｌ1に、センサノードＡ，Ｂ，ＥからなるクラスタＣ11と、センサノードＣ，Ｄ，ＦからなるクラスタＣ12が設けられており、このうちノードＥ，Ｆがそれぞれのクラスタヘッドである。また階層Ｌ2に、センサノードＥ，Ｆ，ＧからなるクラスタＣ21が設けられており、ノードＧがクラスタヘッドである。また階層Ｌ3には、センサノードＧ，Ｈ，ＩからなるクラスタＣ31が設けられており、このうちノードＩがクラスタヘッドである。また、階層Ｌ1，Ｌ2，Ｌ3では、通信チャネルとして、それぞれ異なるチャネルＣｈ1，Ｃｈ2，Ｃｈ3を用いる。
【００４３】
このようなトポロジでは、次のようなステップ（ａ）〜（ｃ）でセンサデータを集約する。
（ａ）ノードＡとノードＢはノードＥへチャネルＣｈ1でセンサデータを集約し、ノードＣとノードＤはノードＦへチャネルＣｈ1でセンサデータを集約する。
（ｂ）ノードＥとノードＦは、それぞれの子ノードからチャネルＣｈ1でデータを集約し終えると通信チャネルをチャネルＣｈ2に切り替え、ノードＧへセンサデータを集約する。
（ｃ）ノードＧとノードＨは、それぞれの子ノードからチャネルＣｈ2でデータを集約し終えると通信チャネルをチャネルＣｈ3に切り替え、ノードＩにデータを集約する。
図７のトポロジでは２分木を例としているが、クラスタ内のノード数は通信の効率を考慮して最適な値を決めるものとする。
【００４４】
このようなデータ収集方法は以下のような特徴を持つ。
・アルゴリズムの共通化：すべてのノードが単一のアルゴリズムで動作し、チャネルや自身の親ノードと子ノードのＩＤなど数個のパラメータを設定するだけで、センサネットワークを構築できる。このため、ユーザはセンサの種類を意識することなくセンサノードを設置できる。また、今後ノードの移動などを考慮したデータ収集方法についても、数個のパラメータを変更するだけでトポロジを変更できる。
【００４５】
・遅延の抑制：遅延を一定以下に抑制するには、遅延をＴ秒以下にする場合、階層数がｈであるとき、各階層でＴ／ｈ秒以内にデータを上位階層に転送すればよい。ネットワーク全体で遅延を一定以下に抑制しようとするとデータ収集方法が複雑になりがちであるが、このデータ収集方法によれば、各クラスタにおいて一定時間以内にデータを送信することさえ保証されれば、全体でも遅延が一定以下になることが保証される。
【００４６】
・チャネル数の削減：一般的な無線通信では、通信帯域は有限であり、チャネル数も有限である。このデータ収集方法によれば、全ノード数をＮとするとき、平衡にクラスタリングできたとすると、必要なチャネル数はＯ（logＮ）となり、大規模なセンサネットワークに好適なデータ収集方法であるといえる。
【００４７】
以上の説明では、実装が最も簡単なチャネルを変更することで、上位階層と下位階層の通信が干渉しないようにしているが、実装が可能であれば、ＴＤＭＡ(Time Division Multiple Access)のタイムスロットを変えたり、ＣＤＭＡ(Code Division Multiple Access)のコードを変更することで通信が重ならないようにしてもよい。
【００４８】
［ネットワーク構築方法］
次に、図８および図９を参照して、本実施の形態にかかるセンサデータ収集システムのネットワーク構築方法について説明する。図８は、本実施の形態にかかるセンサデータ収集システムのクラスタリング処理を示すフローチャートである。図９は、クラスタリング処理の一例を示す説明図である。
本実施の形態にかかるセンサデータ収集システム１のネットワーク構築装置３０では、センサネットワーク５０のトポロジを決定するために、図８に示すようなクラスタリング処理を行う。
【００４９】
センサノード１０に対するクラスタリングは、電波強度から得られた距離に基づいて行う。電波強度を用いると、遮蔽物があるために本来の距離よりも強い電力が必要な場合があり、電波強度から３次元の位置を推測して、その上で一般的な手法を用いてクラスタリングすることはできない。このため、各ノード間の相対的な距離の情報のみを用いてクラスタリングを行う。
【００５０】
屋内型センサネットワークにおいて通信の効率化を図るには、複数のクラスタ間の無線の干渉を抑える必要がある。省電力のためにセンサノードをクラスタリングする手法がいくつか提案されているが、これらの研究は省電力化が目的であるため、センサノードからクラスタヘッドまでの距離の和が最短になるようなクラスタリングを行っている。これに対して、本実施の形態では、クラスタ内の通信電波が他のクラスタの通信に干渉しないことが求められるため、クラスタ間の重複を最小にするようにクラスタリングを行う。
【００５１】
クラスタ間の重複は次の式（１）に示す評価関数Ｆを用いて評価する。ここで、Ｎはクラスタリングを行っている階層の全ノード数、ｋはクラスタの個数、Ｎiはクラスタｉのノード数、Ｐiはクラスタｉのクラスタヘッド、Ｃijはクラスタｉに属するクラスタヘッド以外のｊ番目のノード、ｘlは全ノード中のｌ番目のノードである。
【数１】
【００５２】
式（１）において、評価関数Ｆは、任意のノードｘaから別のノードｘbへの通信が第３のノードｘcで受信可能かを判別する関数であり、次の式（２）のように定義する。
【数２】
【００５３】
ここで、ｄ（ｘa、ｘb）は、ノードｘaからノードｘbへの距離、つまりノードｘaがノードｘbへパケットを送信できる最小の電波強度を意味する。ただし、ノードｘa、ｘb、ｘcの３つが同一のクラスタに属するときは、クラスタヘッドが通信衝突しないように制御しているため、次の式（３）が成り立つものとする。
【数３】
【００５４】
この評価関数Ｆは、各クラスタにおいて、クラスタヘッドから当該クラスタ内の子ノードのへの通信を受信可能なクラスタ外のノードの個数と、クラスタ内の子ノードからクラスタヘッドへの通信を受信可能なクラスタ外のノードの個数の合計を意味し、この値が最小になるクラスタリングが最適なものとなる。
【００５５】
以下で、上記の評価関数Ｆを用いてノードをクラスタリングする手法を説明する。クラスタリングは、ノードの数が多いときに、単純にすべてノード間の距離を比較して計算を行うと、計算時間が膨大になるため、ＣＬＡＲＡ法を用いる（非特許文献４など参照）。この手法では、全ノードからいくつかのサンプルをランダムに選択し、サンプルのみを用いてクラスタリングした後、サンプル以外のノードを最も近いクラスタに割り当てる。本実施の形態にかかるクラスタリング処理は、このＣＬＡＲＡ法を元にしている。
【００５６】
ネットワーク構築装置３０は、まず、最小送信電波強度収集装置３２により、各センサノード１０に対する最小送信電波強度要求メッセージを、ブロードキャスト方式などを用いて、無線通信装置３１からセンサネットワーク５０を介して送信し、これに応じて返送された最小送信電波強度を受信して、センサノード１０間ごとに保存する。
【００５７】
各センサノード１０の無線通信装置１５は、この最小送信電波強度要求メッセージに応じて、他センサノードとの間で検査用データを送受信することにより、最小送信電波強度を検出する。例えば、無線通信装置１５により、送信電波強度を変化させつつ、当該送信電波強度情報を含む検査用データをロードキャスト方式などを用いて送信し、一方、他ノードから検査用データを受信して同一送信元ノードごとに分類し、受信できた検査用データのうち当該送信電波強度情報で指定されている送信電波強度が最小の送信電波強度を、当該送信元ノードから自ノードへ送信する際の最小送信電波強度として検出すればよい。
【００５８】
このようにして、ネットワーク構築装置３０は、各センサノード１０間の最小送信電波強度値を収集した後、クラスタリング処理装置３４により、階層ごとに、図８のクラスタリング処理を繰り返し実行する。なお、中間階層および最上位階層についてクラスタリング処理を行う場合、当該階層より１段下の階層でクラスタヘッドとして選択されたセンサノードを当該階層のノードとして選択するものとする。図８において、Ｆold，Ｆnew，Ｆcは評価関数Ｆの計算結果であり、Ｎrandomはクラスタヘッド以外のサンプルノードからランダムに選択したセンサノードである。
【００５９】
まず、Ｎ個のノードからランダムにｍ個のサンプルノードを選択し（ステップ２０１）、ｍ個のサンプルノードからｋ個のクラスタヘッドをランダムに選択する（ステップ２０２）。これらｍやｋの値については、全ノード数や階層数に基づき予め決定しておけばよい。この後、ループ１として、ループ２を含むステップ２１１〜２１７を繰り返し実行する。
【００６０】
ループ１では、まず、クラスタヘッド以外のサンプルノードを、当該サンプルノードからクラスタヘッドまでの最小送信電波強度が最も小さいクラスタヘッドのクラスタにそれぞれ割り当てることにより当該階層の基準となる基準クラスタ構成を生成し（ステップ２１１）、この基準クラスタ構成について前述した式（１）の評価関数Ｆを算出して基準評価値Ｆoldとする（ステップ２１２）。
【００６１】
次に、クラスタヘッド以外のサンプルノードから、入れ替え対象となるノードとしてＮrandomをランダムに１つ選択し（ステップ２１３）、クラスタ選択用変数ｉを１に初期化するとともに、比較評価値Ｆnewを∞（無限大または最大値）に設定する（ステップ２１４）。
続いて、変数ｉがクラスタ数ｋに達するまで、ステップ２２１〜２２４からなるループ２を繰り返し実行する。
【００６２】
ループ２では、まず、クラスタヘッドＮHiをＮrandomと入れ替えて候補クラスタ構成を生成し、この候補クラスタ構成について前述した式（１）の評価関数Ｆを算出して候補評価値Ｆcを算出し（ステップ２１１）、比較評価値Ｆnewと比較する（ステップ２２２）。ここで、Ｆnew＞Ｆcの場合（ステップ２２２：ＹＥＳ）、Ｆcを新たなＦnewとして設定し（ステップ２２３）、変数ｉを１だけ加算する（ステップ１１５）。また、Ｆnew≦Ｆcの場合（ステップ２２２：ＮＯ）、ステップ２２４へ移行する。
【００６３】
このようにして、すべてのクラスタについてループ２を繰り返し実行することにより、これらクラスタをＮrandomと入れ替えて生成した候補クラスタ構成から、最も小さい候補評価値Ｆcを持つ候補クラスタ構成を見つけて、その候補評価値Ｆcを示す評価値Ｆnewと基準評価値Ｆoldとを比較する（ステップ２１５）。
【００６４】
ここで、Ｆnew＜Ｆoldの場合（ステップ２１５：ＹＥＳ）、Ｆnewが最小となったＮHiとＮrandomとを入れ替えて、最小候補評価値を持つ候補クラスタ構成を当該階層のクラスタ構成として決定し（ステップ２１６）、ループ１の先頭であるステップ２１１へ戻る。また、Ｆnew≧Ｆoldの場合（ステップ２１５：ＮＯ）、上記入れ替えを行わずに、基準クラスタ構成を当該階層のクラスタ構成として決定し、ループ１を脱出して一連のクラスタリング処理を終了する。
【００６５】
ネットワーク構築装置３０は、クラスタリング処理装置３４により、このようなクラスタリング処理を階層ごとに繰り返し実行することにより、センサネットワーク５０のトポロジを決定する。
この後、ネットワーク構築装置３０は、クラスタリング処理装置３４で決定したトポロジに基づいて、ネットワーク設定装置３５により、各センサノード１０に関する通信相手ノードと当該通信相手ノードに関する最小送信電波強度とを決定する。
【００６６】
この際、子ノードのセンサデータを送信すべき通信相手ノードは、同一クラスタに属するクラスタヘッドとなり、クラスタヘッドのセンサデータを収集すべき通信相手ノードは、その逆となる。また、各センサノードの最小送信電波強度は、当該通信相手ノードとの間の最小送信電波強度を最小送信電波強度収集装置３２から取得すればよい。
このようにして、ネットワーク設定装置３５は、各センサノード１０に関する通信相手ノードと当該通信相手ノードに関する最小送信電波強度とを決定し、無線通信装置３１からセンサネットワークを介して各センサノードへ通知する。これにより、センサデータ収集に適したセンサネットワーク５０が構築されることになる。
【００６７】
次に、図９を参照してクラスタリング処理例について説明する。ここでは、１３個のノードを３つのクラスタに分割する場合を例として説明する。以下のステップ（ａ）〜（ｇ）は、図９（ａ）〜図９（ｇ）に相当する。
【００６８】
（ａ）ノードの中からランダムにサンプルを選択する。ここでは、６個のサンプルを選択した。
（ｂ）サンプルの中からランダムにクラスタヘッドを選択する。この例では３つのクラスタに分割するため、３つのクラスタヘッドＰ1、Ｐ2、Ｐ3を選択する。
（ｃ）クラスタヘッド以外のサンプルノードをクラスタリングし、評価関数Ｆを計算し、Ｆoldとする。各ノードは最小距離のクラスタヘッドのクラスタに所属するため、この例ではＰ1のクラスタには２個のノードが、Ｐ2のクラスタには０個のノードが、Ｐ3のクラスタには１個のノードがそれぞれ所属する。また、Ｐ1からＣ12への通信は、クラスタ外のＰ2，Ｐ3の２個のノードでも受信でき、Ｐ3からＣ31の通信はクラスタ外のＰ1、Ｃ11、Ｃ12，Ｐ2でも受信できる。このように通信の重なり、すなわち無線通信干渉度合いを数えることで評価関数Ｆを算出する。
【００６９】
（ｄ）クラスタヘッド以外のサンプルノードの中から１つをＮrandomとして選択する。この例では、Ｃ31が選ばれたとする。
（ｅ）Ｎrandomとクラスタヘッドを入れ替えた場合のＦcを計算し、最小となるものをＦnewとする。この例では、クラスタヘッドが３つあるため、Ｐ1と入れ替えるパターン１、Ｐ2と入れ替えるパターン２、Ｐ3と入れ替えるパターン３の３つのパターンについて計算を行うことになる。３つのパターンの中では、狭い範囲に同一クラスタのノードが集中するパターン２やパターン３がパターン１や現在のクラスタヘッドの配置よりもＦの値が小さく、無線通信干渉の少ない良好なクラスタリングとなる。ここでは、パターン３の場合にＦnewが最小になったものとする。
【００７０】
（ｆ）Ｆnewを最小にしたクラスタヘッドとＮrandomを入れ替える。ＦnewがＦoldよりも大きく、つまりクラスタヘッドを変更しない方が評価が高いならば、入れ替えを行わずにクラスタヘッドを確定させてクラスタリング処理を終了する。一方、入れ替えを行ったときは、ステップ（ｃ）以降の処理を繰り返す。この例では、Ｐ3とＮrandomとを入れ替え、再度処理を繰り返す。
（ｇ）確定されたクラスタヘッドを用いて、すべてのノードを最短距離のクラスタヘッドのクラスタに所属させることでクラスタリングを行う。
【００７１】
以上のクラスタリング処理において、クラスタリングの結果はサンプルの選択やクラスタヘッドの初期選択に左右されるため、評価関数Ｆが予め定めた値以下ではなくクラスタリングの精度が不十分に場合は、何度か繰り返してクラスタリングを行い、その中から最適なものを選択する。
【００７２】
最下位の階層のクラスタリングが終了すると、各クラスタの中から最適なクラスタヘッドを選択し直し、クラスタヘッドのみを用いて１つ上位の階層のクラスタリングを行う。これを繰り返し、すべての階層のクラスタを決定する。したがって、最上位階層ＬHに予め設定しておいた、基地局２０がクラスタヘッドとなる１つのクラスタに対して、すべてのノードが所属することになる。
すべての階層におけるクラスタリング処理が終了すると、データを収集するためのトポロジと、各ノード間の通信での最適な電波強度が決まるため、基地局２０が、ノードのクラスタヘッド、子ノードの一覧、それぞれの通信における送信電波強度をすべてのノードに対して通知する。これによって、データ収集が開始できるようになる。
【００７３】
図１０は、本実施の形態にかかるセンサデータ収集システムの評価結果を示す説明図である。図１１は、評価に用いたトポロジを示す説明図である。
ここでは、本実施の形態にかかるセンサデータ収集方法と、従来のポーリング手法とについて、４つのセンサノードからセンサデータを基地局２０へ収集する際に発生する遅延時間を測定した。本実施の形態にかかるセンサデータ収集方法では、図１１のトポロジのセンサネットワーク５０を用いた。また、無線通信にはＩＥＥＥ８０２．１５．４準拠の無線通信モジュールを用いた。評価の結果、センサノード数が少ないにもかかわらず、従来のポーリング手法に比べて、本実施の形態にかかるセンサデータ収集方法の方が、データ収集に要する所要時間、すなわち遅延が少なくなる傾向にあることが分かる。
【符号の説明】
【００７４】
１…センサデータ収集システム、１０…センサノード、１１…センサ、１２…センサイベント検出装置、１３…センサデータ処理装置、１４…センサデータ記憶装置、１５…無線通信装置、２０…基地局、２１…無線通信装置、２２…受信データ処理装置、３０…ネットワーク構築装置、３１…無線通信装置、３２…最小送信電波強度収集装置、３３…評価値算出装置、３４…クラスタリング処理装置、３５…ネットワーク設定装置、５０…センサネットワーク。
【技術分野】
【０００１】
本発明は、データ収集技術に関し、特に複数のセンサから無線通信を介してセンサデータを収集する技術に関する。
【背景技術】
【０００２】
一般に、センサノードがネットワークを構成してデータを収集するような通信ネットワークをセンサネットワークと呼んでいる。これまで、センサネットワークを構成するノードとして特許文献１のようなデバイスが提案されているが、この例ではネットワーク上の通信のやり取りについては詳しく定義されていない。ネットワークの構築に関しては、非特許文献１や非特許文献２に代表されるように、ネットワークインフラがない広大な場所において、ノード間でデータを転送し合うさまざまな手法が提案されている。
【０００３】
しかし、屋内にセンサノードを配置することを想定した場合、このような屋内型のセンサネットワークにおいては、限られた範囲に多数のセンサノードが配置される。したがって、ほぼすべてのセンサノードが互いに通信可能であることから、無線の干渉を避けてネットワークを構築する必要がある。このため、既存技術を屋内型のセンサネットワークにそのまま適用することはできない。
【０００４】
最近では、無線の送信電力を調整できる無線通信モジュールが普及してきている。このようなデバイスを想定し、すべてのノードはお互いに通信可能であるが、省電力性や通信の効率向上のために、送信電波強度を動的に変更してクラスタを生成し、効率よくデータを収集するための研究がなされている。
その１つとして、非特許文献３に示すＬＥＡＣＨがある。この研究では、送信電力が送信先までの距離の２乗に比例するという前提に基づき、マルチホップを利用して省電力を実現している。しかし、屋内型センサネットワークにおける近距離無線では、無線の電波の送信よりも受信に電力が必要であるため、既存の省電力のための手法をそのまま屋内型センサネットワークに適応しても省電力にならず、無線の干渉を避けることも主な目的とはされていない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−２０８７１９号公報
【非特許文献】
【０００６】
【非特許文献１】D. B. Johnson and D. A. Maltz: Dynamic Source Routing in Ad Hoc Wireless Networks, in Proc, of Mobile Computing 1996, 1996.
【非特許文献２】C. E. Perkins and E. M. Royer: Ad-hoc On-Demand Distance Vector Routing, in Proc. of WMCSA1999, 1999.
【非特許文献３】W. R, Heinzelman, A. Chandrakasan, and H. Balakrishnan: Energy-Efficient Communication Protocol for Wireless Microsensor Networks, In Proc. of 33rd Hawaii International Conference on System Sciences-Volume 8, p.8020, 2000.
【非特許文献４】R. T. Ng and J. Han: Efficient and Effective Clustering Methods for Spatial Data Mining, in Proc. of VLDB'94, pp.144-155, 1994.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
屋内型センサネットワークにおいて、センサノードが多数存在するときに、これらセンサノードでセンシングしたセンサデータを、少ない遅延で並行して効率よく基地局に収集することが重要となる。ここで、遅延とは、状況が変化してセンサデータが発生してから基地局にデータが到達するまでの所要時間を指す。また、送信するデータ量を抑えて多数のノードからデータを収集できるよう、センサノードは周囲の状況が変化したときにのみセンサデータを送信するものとする。
【０００８】
無線通信によって多数のセンサノードからデータを収集することを考えると、まず単純な方法として、ポーリングによる手法と時分割多重による方法が挙げられる。ポーリングでは、基地局が各ノードに対してデータを要求するパケットを送信し、パケットを受信したノードがセンサデータを基地局に返信することで、データを収集できる。
センサノードでの実装は単純で実現は容易であり、確実にデータを収集できる。しかし、ノード１台ずつに順にデータを要求するため、データが発生してからデータが基地局に収集されるまでの遅延が大きくなる。さらにイベント駆動型センサを利用するため、センサデータが発生していないノードにもデータを要求しなければならず、効率が悪い。
【０００９】
例えば、時分割多重方式では、各ノードにタイムスロットを割り当て、ノードが割り当てられた時間に基地局へデータを送信することで、無線通信の衝突を避けながらデータを収集できる。しかし、均一にタイムスロットをノードに割り当てると、送信するセンサデータの量はセンサの種類と周囲の状況によって変化するため、データが発生していないときにもタイムスロットが割り当てられる可能性が高く、無駄な時間が多い。センサデータの量に応じて動的にタイムスロットを割り当てるような手法も考えられるが、センサデータの発生量を予測することは不可能である上に、実装も困難である。さらに、時分割多重は時刻の同期が必要なため計算機リソースの限られるセンサノードでは実装しにくいという問題もある。
【００１０】
本発明はこのような課題を解決するためのものであり、複数のセンサでセンシングしたセンサデータを少ない遅延で並行して効率よく収集できるセンサデータ収集システム、方法、プログラム、および記録媒体を提供することを目的としている。
【課題を解決するための手段】
【００１１】
このような目的を達成するために、本発明にかかるセンサネットワーク構築装置は、複数の階層を有するセンサネットワークを無線通信により構成する複数のセンサノードと、各センサノードでセンシングした当該センサノードの周囲状況を示すセンサデータをセンサネットワークを介して収集する基地局とを含み、センサネットワークは、階層ごとに１つ以上のクラスタを有し、任意のセンサノードからなる１つ以上の子ノードと１つのクラスタヘッドとからクラスタが構成され、当該クラスタ内の子ノードとクラスタヘッドとが無線通信を行うとともに、クラスタヘッドが１つ上位の階層における任意の上位クラスタの子ノードとして動作し、最上位階層に構成する１つのクラスタのクラスヘッダが基地局からなる、階層クラスタ構造を有するセンサデータ収集システムにおいて、各センサノードで検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、センサネットワークを介してそれぞれ収集する最小送信電波強度収集装置と、これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出装置と、階層ごとに複数選択したクラスタ構成について評価値算出装置で評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、センサネットワークのトポロジを決定するクラスタリング処理装置と、トポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、センサネットワークを介して各センサノードへ通知するネットワーク設定装置とを備えている。
【００１２】
この際、クラスタリング処理装置で、任意の階層についてクラスタ構成を決定する際、当該階層に含まれるノードからランダムにサンプルノードを選択し、このサンプルノードから各クラスタのクラスタヘッドをそれぞれ任意に選択し、クラスタ以外のサンプルノードを当該サンプルノードから最も小さい電波強度で通信可能なクラスタヘッドのクラスタにそれぞれ割り当てて当該階層の基準となるクラスタ構成を生成して、評価値算出装置により基準クラスタ構成に関する基準評価値を算出し、基準クラスタ構成のうちクラスタヘッド以外のサンプルノードからランダムに選択して当該クラスタのクラスタヘッドと入れ替えた候補クラスタ構成を順次生成して、評価値算出装置により候補クラスタ構成に関する候補評価値を算出し、候補評価値のうち最も小さい最小候補評価値と基準評価値とを比較し、いずれか小さい方のクラスタ構成を当該階層のクラスタ構成として決定するようにしてもよい。
【００１３】
また、本発明にかかるセンサネットワーク構築方法は、複数の階層を有するセンサネットワークを無線通信により構成する複数のセンサノードと、各センサノードでセンシングした当該センサノードの周囲状況を示すセンサデータをセンサネットワークを介して収集する基地局とを含み、センサネットワークは、階層ごとに１つ以上のクラスタを有し、任意のセンサノードからなる１つ以上の子ノードと１つのクラスタヘッドとからクラスタが構成され、当該クラスタ内の子ノードとクラスタヘッドとが無線通信を行うとともに、クラスタヘッドが１つ上位の階層における任意の上位クラスタの子ノードとして動作し、最上位階層に構成する１つのクラスタのクラスヘッダが基地局からなる、階層クラスタ構造を有するセンサデータ収集システムにおいて、最小送信電波強度収集装置が、各センサノードで検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、センサネットワークを介してそれぞれ収集する最小送信電波強度収集ステップと、評価値算出装置が、これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出ステップと、クラスタリング処理装置が、階層ごとに複数選択したクラスタ構成について評価値算出装置で評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、センサネットワークのトポロジを決定するクラスタリング処理ステップと、ネットワーク設定装置が、トポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、センサネットワークを介して各センサノードへ通知するネットワーク設定ステップとを備えている。
【００１４】
この際、クラスタリング処理装置で、任意の階層についてクラスタ構成を決定する際、当該階層に含まれるノードからランダムにサンプルノードを選択し、このサンプルノードから各クラスタのクラスタヘッドをそれぞれ任意に選択し、クラスタ以外のサンプルノードを当該サンプルノードから最も小さい電波強度で通信可能なクラスタヘッドのクラスタにそれぞれ割り当てて当該階層の基準となるクラスタ構成を生成して、評価値算出装置により基準クラスタ構成に関する基準評価値を算出し、基準クラスタ構成のうちクラスタヘッド以外のサンプルノードからランダムに選択して当該クラスタのクラスタヘッドと入れ替えた候補クラスタ構成を順次生成して、評価値算出装置により候補クラスタ構成に関する候補評価値を算出し、候補評価値のうち最も小さい最小候補評価値と基準評価値とを比較し、いずれか小さい方のクラスタ構成を当該階層のクラスタ構成として決定するようにしてもよい。
【００１５】
また、本発明にかかるプログラムは、コンピュータを、前述したいずれか１つセンサネットワーク構築装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１６】
本発明によれば、センサノードを階層的にクラスタリングすることで、多数のノードから、少ない遅延で並行して効率よくセンサデータを収集できる。多数の箇所でセンシングを行いたい場合であっても、本発明を用いると理想的には１台の基地局を設置するのみで容易にセンサネットワークが構築できるようになるため、一般家庭などへセンサネットワークを普及させる上で効果的である。多数のセンサノードを用いてセンシングを行うときに、本発明を用いれば、遅延を一定以下に抑えながら、すべてのノードから効率よくデータを収集できる。
【図面の簡単な説明】
【００１７】
【図１】本発明の一実施の形態にかかるセンサデータ収集システムの構成を示すブロック図である。
【図２】センサノードの構成例を示すブロック図である。
【図３】基地局の構成例を示すブロック図である。
【図４】ネットワーク構築装置の構成例を示すブロック図である。
【図５】センサネットワークの階層クラスタ構造例を示す説明図である。
【図６】本実施の形態にかかるセンサデータ収集システムのデータ集約処理を示すフローチャートである。
【図７】階層クラスタ構造の一例を示すトポロジである。
【図８】本実施の形態にかかるセンサデータ収集システムのクラスタリング処理を示すフローチャートである。
【図９】クラスタリング処理の一例を示す説明図である。
【図１０】本実施の形態にかかるセンサデータ収集システムの評価結果を示す説明図である。
【図１１】評価に用いたトポロジを示す説明図である。
【発明を実施するための形態】
【００１８】
次に、本発明の実施の形態について図面を参照して説明する。
［センサデータ収集システム］
まず、図１を参照して、本発明の一実施の形態にかかるセンサデータ収集システムについて説明する。図１は、本発明の一実施の形態にかかるセンサデータ収集システムの構成を示すブロック図である。図２は、センサノードの構成例を示すブロック図である。図３は、基地局の構成例を示すブロック図である。図４は、ネットワーク構築装置の構成例を示すブロック図である。
【００１９】
このセンサデータ収集システム１は、無線通信網からなるセンサネットワーク５０で相互に接続された、複数のセンサノード１０、基地局２０、ネットワーク構築装置３０を含み、各センサノード１０のセンサでセンシングしたセンサデータを、センサネットワーク５０を介して基地局２０へ並行して収集する機能を有している。このうち、ネットワーク構築装置３０については、センサネットワーク５０の構築時にのみ必要となる構成であり、その後のセンサデータ収集時には不要となる。また、このネットワーク構築装置３０の機能を基地局２０で実現してもよい。
【００２０】
センサノード１０には、図２に示すように、周囲の状況をセンシングしセンサデータとして出力するセンサ１１と、センサ１１から出力されるセンサデータに変化があったことをイベントとして検出するセンサイベント検出装置１２と、無線通信用送信キューとして送信すべきセンサデータを記憶するセンサデータ記憶装置１４と、センサイベント検出装置１２でイベントを検出した際のセンサデータを処理してセンサデータ記憶装置１４へ保存するセンサデータ処理装置１３と、他のセンサノード１０や基地局２０と無線通信を行うことによりセンサデータなどの各種データを送受信するとともに、送信電波の強度を多段階に調整でき、他センサノードとの間で最小送信電波強度を検出する無線通信装置１５とが設けられている。
【００２１】
センサノード１０を構成するセンサ１１、センサイベント検出装置１２、センサデータ処理装置１３、センサデータ記憶装置１４、および無線通信装置１５については、それぞれ別個の装置から実現した場合を例として説明するが、これらのうち複数の装置を１つの装置で実現してもよい。また、これら装置での内部処理については、専用の信号処理回路で実現してもよく、コンピュータでＣＰＵなどの演算処理装置とプログラムとを協働させてなる個々の機能処理装置で実現してもよい。
【００２２】
基地局２０には、図３に示すように、センサノード１０と無線通信を行うことによりセンサデータなどの各種データを送受信する無線通信装置２１と、無線通信装置２１で受信したセンサデータを集約して上位装置（図示せず）へ出力する受信データ処理装置２２とが設けられている。
基地局２０を構成する無線通信装置２１および受信データ処理装置２２については、それぞれ別個の装置から実現した場合を例として説明するが、これらのうち複数の装置を１つの装置で実現してもよい。また、これら装置での内部処理については、専用の信号処理回路で実現してもよく、コンピュータでＣＰＵなどの演算処理装置とプログラムとを協働させてなる個々の機能処理装置で実現してもよい。
【００２３】
ネットワーク構築装置３０には、図４に示すように、センサノード１０と無線通信を行うことによりセンサデータなどの各種データを送受信する無線通信装置３１と、各センサノード１０で検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、センサネットワーク５０を介してそれぞれ収集する最小送信電波強度収集装置３２と、これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出装置３３と、階層ごとに複数選択したクラスタ構成について評価値算出装置３３で評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、センサネットワークのトポロジを決定するクラスタリング処理装置３４と、このトポロジに基づいて個々のセンサノード１０に関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、センサネットワーク５０を介して各センサノード１０へ通知するネットワーク設定装置３５とが設けられている。
【００２４】
ネットワーク構築装置３０を構成する無線通信装置３１、最小送信電波強度収集装置３２、評価値算出装置３３、クラスタリング処理装置３４、およびネットワーク設定装置３５については、それぞれ別個の装置から実現した場合を例として説明するが、これらのうち複数の装置を１つの装置で実現してもよい。また、これら装置での内部処理については、専用の信号処理回路で実現してもよく、コンピュータでＣＰＵなどの演算処理装置とプログラムとを協働させてなる個々の機能処理装置で実現してもよい。
【００２５】
これにより、センサノード１０では、周囲の状況の変化によるセンサデータの変化がイベントとしてセンサデータ処理装置１３により検出されると、その変化を示すセンサデータが無線通信装置１５を介して基地局２０へ送信される。基地局２０では、このようにして各センサノード１０でセンシングしたセンサデータを無線通信装置２１で受信し、受信データ処理装置２２で集約して出力する。
【００２６】
［センサネットワーク］
次に、図５を参照して、本実施の形態にかかるセンサデータ収集システムのセンサネットワークについて説明する。図５は、センサネットワークの階層クラスタ構造例を示す説明図である。
センサネットワーク５０は、複数の階層を有するとともに、階層ごとに１つ以上のクラスタが設けられている階層クラスタ構造をなしている。
【００２７】
図５の例では、最下位階層ＬL、中間階層ＬM、最上位階層ＬHの３つの階層から構成されており、これら階層ごとに１つ以上のセンサノード１０からなるクラスタが１つ以上設けられている。なお、実際のセンサネットワーク５０において、階層数は３に限定されるものではなく、少なくとも最下位階層ＬL、最上位階層ＬHの２つの階を含み、センサノード１０の数やクラスタの数に応じて、中間階層ＬMを増加させればよい。
【００２８】
最下位階層ＬLでは、各センサノード１０は位置的に近くに存在する他のセンサノード１０とともにクラスタをそれぞれ生成し、クラスタごとにその中の１台のセンサノード１０にデータを集約する。各クラスタにおいてデータが集約されるセンサノード１０を当該クラスタのクラスタヘッドと定義する。また、各クラスタに属するセンサノード１０のうちクラスタヘッド以外のセンサノード１０を子ノードという。
【００２９】
各クラスタ内の無線通信については、当該クラスタの子ノードからクラスタヘッドにセンサデータが送信できれば十分であるため、無線送信の電波強度を制限して微弱な電波で無線通信を行うことができる。これにより、クラスタ間での電波の干渉を低減でき、各クラスタにおいて並行してデータ収集を行うことが可能となる。
【００３０】
中間層ＬMおよび最上位階層ＬHのクラスタの子ノードは、１段下の階層における各クラスタのクラスタヘッドから構成されており、階層ごとにこのようなクラスタ構成が繰り返し形成されている。これにより、階層が上がるごとにそれぞれのクラスタでデータが順次集約される。
最上位階層ＬHのクラスタは、基地局２０をクラスタヘッドとする１つのクラスタから構成されており、このクラスタの子ノードは、中間層ＬMの各クラスタのクラスタヘッドから構成されている。このため、最終的には最上位階層ＬHの基地局２０に対してすべてのセンサノード１０からセンサデータが集約される。
【００３１】
また、この階層クラスタ構造では、各階層で異なる通信チャネルを使用する。図５の例では、最下位階層ＬL、中間階層ＬM、最上位階層ＬHごとに、通信チャネルＣｈL，ＣｈM，ＣｈHを用いる。これにより、階層間での無線通信の干渉がなくなり、各階層で独立してデータを収集できる。
本実施の形態では、このような階層クラスタ構造を用いることで、各センサノード１０でセンシングしたセンサデータを少ない遅延で並行して効率よく収集している。これにより、ポーリングを用いる手法とは異なり、効率よくデータが収集できる。また、時分割多重を用いる方法と異なり、実装もシンプルで容易に導入可能である。
【００３２】
なお、本実施の形態では、通信帯域が溢れるほどのデータは発生しないものとする。また、センサノード間の距離は、位置取得センサを用いるのではなく、電波の強度を利用して計測するものとする。具体的には、あるセンサノードから送信電波強度を変化させて複数のパケットを送信し、受信側では、受け取ったパケットのうち最小の電波強度を距離とする。
【００３３】
［データ収集方法］
次に、図６および図７を参照して、本実施の形態にかかるセンサデータ収集システムのデータ集約方法について説明する。図６は、本実施の形態にかかるセンサデータ収集システムのデータ集約処理を示すフローチャートである。図７は、階層クラスタ構造の一例を示すトポロジである。
【００３４】
最下位階層ＬLのクラスタでは、各子ノードの持つセンサデータをクラスタヘッドに集約する。この際、クラスタヘッドは、まず、無線通信装置１５において通信チャネルとして最下位階層ＬLのチャネルＣｈLを選択し、クラスタ内の子ノードへデータ要求メッセージを送信する。子ノードは、無線通信装置１５において通信チャネルとしてチャネルＣｈLを選択しており、クラスタヘッドからデータ要求メッセージを受信した子ノードは、その時点で自身の送信キューに格納されているセンサデータをクラスタヘッドへ送信する。送信キューが空であれば、何も送信しない。
【００３５】
クラスタヘッドは、無線通信装置１５により各子ノードからデータを受信して収集した後、通信チャネルを１段上の中間階層ＬMのチャネルＣｈLに切り替え、この中間階層ＬMのクラスタヘッドからデータ要求メッセージが送られるのを待つ。データ要求を受信すると、クラスタヘッドは、最下位階層ＬLの子ノードから収集したセンサデータを、前述した最下位階層ＬLの子ノードと同様にして中間階層ＬMのクラスタヘッドへ送信する。このようにして、すべての階層のクラスタでこの処理が繰り返し実行され、最上位階層ＬHにある基地局２０にデータが集約される。また、各階層のクラスタヘッドも他の子ノードと同じくセンシングを行っているため、子ノードから収集したセンサデータを上位階層へ送信する際、自身がセンシングしたセンサデータも付加して送信する。
【００３６】
次に、図６を参照して、任意の階層に属するセンサノードのデータ集約処理について説明する。図６において、最下位階層ＬLから上にｍ番目の階層におけるｉ番目の子ノードをＮciとし、そのクラスタヘッドをＮpとし、当該階層で用いる通信チャネルをＣｈmとし、１段上のｍ＋１番目の階層で用いる通信チャネルをＣｈm+1とし、子ノードＮciへの送信電波強度をＥciとし、クラスタヘッドＮpへの送信電波強度をＥpとする。
【００３７】
センサノード１０は、ループ１として、ループ２を含むステップ１０１〜１０７を繰り替えし実行している。ループ１では、まず、センサデータ処理装置１３により、センサイベント検出装置１２でイベントを検出した際のセンサデータを処理して送信キューであるセンサデータ記憶装置１４へ追加保存し（ステップ１０１）、無線通信装置１５により、通信チャネルをＣｈmに設定し（ステップ１０２）、子ノード選択用変数ｉを０に初期化する（ステップ１０３）。
【００３８】
次に、センサノード１０は、変数ｉが子ノード数ｎに達するまで、ステップ１１１〜１１５からなるループ２を繰り返し実行する。ループ２では、まず、無線通信装置１５により、送信電波強度をＥciに設定し（ステップ１１１）、子ノードＮciに対してデータ要求メッセージを送信した後（ステップ１１２）、子ノードＮciからのデータ受信待ちとなる（ステップ１１３）。
ここで、所定の待ち時間が経過するまでに子ノードＮciからデータを受信した場合（ステップ１１３：ＹＥＳ）、無線通信装置１５により、その受信データを送信キューへ追加保存し（ステップ１１４）、変数ｉを１だけ加算する（ステップ１１５）。また、ステップ１１３において、データ要求メッセージの送信から待ち時間が経過するまでに子ノードＮciからデータを受信できなかった場合（ステップ１１３：ＮＯ）、ステップ１１５へ移行する。
【００３９】
このようにして、すべての子ノードについてループ２を繰り返し実行することにより、各子ノードからセンサデータを収集して送信キューに保存した後、センサノード１０は、無線通信装置１５により、通信チャネルをＣｈm+1に設定するとともに（ステップ１０４）、送信電波強度をＥpに設定し（ステップ１０５）、クラスタヘッドＮpからのデータ要求メッセージの受信待ちとなる（ステップ１０６）。
【００４０】
ここで、所定の待ち時間が経過するまでにクラスタヘッドＮpからのデータ要求メッセージを受信した場合（ステップ１０６：ＹＥＳ）、無線通信装置１５により、送信キューに保存されている各子ノードから収集したセンサデータ、さらには自身でセンシングしたセンサデータをクラスタヘッドＮpへ送信し（ステップ１０７）、ループ１の先頭であるステップ１０１へ戻る。また、ステップ１０６において、待ち時間が経過するまでにクラスタヘッドＮpからのデータ要求メッセージを受信できなかった場合（ステップ１０６：ＮＯ）、ループ１の先頭であるステップ１０１へ戻る。
【００４１】
したがって、このデータ集約処理では、各センサノードにおいて、自身のセンシング結果と他のノードから受信したセンシング結果がセンサデータ記憶装置１４の中の送信キューで管理され、送信要求があったときには送信キューに保存されているセンサデータがすべて送信される。また、ループ２のデータ収集処理とステップ１０２の通信チャネル変更処理については、子ノードが存在するときにだけ実行される処理であり、当該センサノードが子ノードを持たない場合、これら処理は実行されない。
【００４２】
次に、図７を参照して、センサデータの集約手順の具体例について説明する。図７のトポロジ例では、階層Ｌ1に、センサノードＡ，Ｂ，ＥからなるクラスタＣ11と、センサノードＣ，Ｄ，ＦからなるクラスタＣ12が設けられており、このうちノードＥ，Ｆがそれぞれのクラスタヘッドである。また階層Ｌ2に、センサノードＥ，Ｆ，ＧからなるクラスタＣ21が設けられており、ノードＧがクラスタヘッドである。また階層Ｌ3には、センサノードＧ，Ｈ，ＩからなるクラスタＣ31が設けられており、このうちノードＩがクラスタヘッドである。また、階層Ｌ1，Ｌ2，Ｌ3では、通信チャネルとして、それぞれ異なるチャネルＣｈ1，Ｃｈ2，Ｃｈ3を用いる。
【００４３】
このようなトポロジでは、次のようなステップ（ａ）〜（ｃ）でセンサデータを集約する。
（ａ）ノードＡとノードＢはノードＥへチャネルＣｈ1でセンサデータを集約し、ノードＣとノードＤはノードＦへチャネルＣｈ1でセンサデータを集約する。
（ｂ）ノードＥとノードＦは、それぞれの子ノードからチャネルＣｈ1でデータを集約し終えると通信チャネルをチャネルＣｈ2に切り替え、ノードＧへセンサデータを集約する。
（ｃ）ノードＧとノードＨは、それぞれの子ノードからチャネルＣｈ2でデータを集約し終えると通信チャネルをチャネルＣｈ3に切り替え、ノードＩにデータを集約する。
図７のトポロジでは２分木を例としているが、クラスタ内のノード数は通信の効率を考慮して最適な値を決めるものとする。
【００４４】
このようなデータ収集方法は以下のような特徴を持つ。
・アルゴリズムの共通化：すべてのノードが単一のアルゴリズムで動作し、チャネルや自身の親ノードと子ノードのＩＤなど数個のパラメータを設定するだけで、センサネットワークを構築できる。このため、ユーザはセンサの種類を意識することなくセンサノードを設置できる。また、今後ノードの移動などを考慮したデータ収集方法についても、数個のパラメータを変更するだけでトポロジを変更できる。
【００４５】
・遅延の抑制：遅延を一定以下に抑制するには、遅延をＴ秒以下にする場合、階層数がｈであるとき、各階層でＴ／ｈ秒以内にデータを上位階層に転送すればよい。ネットワーク全体で遅延を一定以下に抑制しようとするとデータ収集方法が複雑になりがちであるが、このデータ収集方法によれば、各クラスタにおいて一定時間以内にデータを送信することさえ保証されれば、全体でも遅延が一定以下になることが保証される。
【００４６】
・チャネル数の削減：一般的な無線通信では、通信帯域は有限であり、チャネル数も有限である。このデータ収集方法によれば、全ノード数をＮとするとき、平衡にクラスタリングできたとすると、必要なチャネル数はＯ（logＮ）となり、大規模なセンサネットワークに好適なデータ収集方法であるといえる。
【００４７】
以上の説明では、実装が最も簡単なチャネルを変更することで、上位階層と下位階層の通信が干渉しないようにしているが、実装が可能であれば、ＴＤＭＡ(Time Division Multiple Access)のタイムスロットを変えたり、ＣＤＭＡ(Code Division Multiple Access)のコードを変更することで通信が重ならないようにしてもよい。
【００４８】
［ネットワーク構築方法］
次に、図８および図９を参照して、本実施の形態にかかるセンサデータ収集システムのネットワーク構築方法について説明する。図８は、本実施の形態にかかるセンサデータ収集システムのクラスタリング処理を示すフローチャートである。図９は、クラスタリング処理の一例を示す説明図である。
本実施の形態にかかるセンサデータ収集システム１のネットワーク構築装置３０では、センサネットワーク５０のトポロジを決定するために、図８に示すようなクラスタリング処理を行う。
【００４９】
センサノード１０に対するクラスタリングは、電波強度から得られた距離に基づいて行う。電波強度を用いると、遮蔽物があるために本来の距離よりも強い電力が必要な場合があり、電波強度から３次元の位置を推測して、その上で一般的な手法を用いてクラスタリングすることはできない。このため、各ノード間の相対的な距離の情報のみを用いてクラスタリングを行う。
【００５０】
屋内型センサネットワークにおいて通信の効率化を図るには、複数のクラスタ間の無線の干渉を抑える必要がある。省電力のためにセンサノードをクラスタリングする手法がいくつか提案されているが、これらの研究は省電力化が目的であるため、センサノードからクラスタヘッドまでの距離の和が最短になるようなクラスタリングを行っている。これに対して、本実施の形態では、クラスタ内の通信電波が他のクラスタの通信に干渉しないことが求められるため、クラスタ間の重複を最小にするようにクラスタリングを行う。
【００５１】
クラスタ間の重複は次の式（１）に示す評価関数Ｆを用いて評価する。ここで、Ｎはクラスタリングを行っている階層の全ノード数、ｋはクラスタの個数、Ｎiはクラスタｉのノード数、Ｐiはクラスタｉのクラスタヘッド、Ｃijはクラスタｉに属するクラスタヘッド以外のｊ番目のノード、ｘlは全ノード中のｌ番目のノードである。
【数１】
【００５２】
式（１）において、評価関数Ｆは、任意のノードｘaから別のノードｘbへの通信が第３のノードｘcで受信可能かを判別する関数であり、次の式（２）のように定義する。
【数２】
【００５３】
ここで、ｄ（ｘa、ｘb）は、ノードｘaからノードｘbへの距離、つまりノードｘaがノードｘbへパケットを送信できる最小の電波強度を意味する。ただし、ノードｘa、ｘb、ｘcの３つが同一のクラスタに属するときは、クラスタヘッドが通信衝突しないように制御しているため、次の式（３）が成り立つものとする。
【数３】
【００５４】
この評価関数Ｆは、各クラスタにおいて、クラスタヘッドから当該クラスタ内の子ノードのへの通信を受信可能なクラスタ外のノードの個数と、クラスタ内の子ノードからクラスタヘッドへの通信を受信可能なクラスタ外のノードの個数の合計を意味し、この値が最小になるクラスタリングが最適なものとなる。
【００５５】
以下で、上記の評価関数Ｆを用いてノードをクラスタリングする手法を説明する。クラスタリングは、ノードの数が多いときに、単純にすべてノード間の距離を比較して計算を行うと、計算時間が膨大になるため、ＣＬＡＲＡ法を用いる（非特許文献４など参照）。この手法では、全ノードからいくつかのサンプルをランダムに選択し、サンプルのみを用いてクラスタリングした後、サンプル以外のノードを最も近いクラスタに割り当てる。本実施の形態にかかるクラスタリング処理は、このＣＬＡＲＡ法を元にしている。
【００５６】
ネットワーク構築装置３０は、まず、最小送信電波強度収集装置３２により、各センサノード１０に対する最小送信電波強度要求メッセージを、ブロードキャスト方式などを用いて、無線通信装置３１からセンサネットワーク５０を介して送信し、これに応じて返送された最小送信電波強度を受信して、センサノード１０間ごとに保存する。
【００５７】
各センサノード１０の無線通信装置１５は、この最小送信電波強度要求メッセージに応じて、他センサノードとの間で検査用データを送受信することにより、最小送信電波強度を検出する。例えば、無線通信装置１５により、送信電波強度を変化させつつ、当該送信電波強度情報を含む検査用データをロードキャスト方式などを用いて送信し、一方、他ノードから検査用データを受信して同一送信元ノードごとに分類し、受信できた検査用データのうち当該送信電波強度情報で指定されている送信電波強度が最小の送信電波強度を、当該送信元ノードから自ノードへ送信する際の最小送信電波強度として検出すればよい。
【００５８】
このようにして、ネットワーク構築装置３０は、各センサノード１０間の最小送信電波強度値を収集した後、クラスタリング処理装置３４により、階層ごとに、図８のクラスタリング処理を繰り返し実行する。なお、中間階層および最上位階層についてクラスタリング処理を行う場合、当該階層より１段下の階層でクラスタヘッドとして選択されたセンサノードを当該階層のノードとして選択するものとする。図８において、Ｆold，Ｆnew，Ｆcは評価関数Ｆの計算結果であり、Ｎrandomはクラスタヘッド以外のサンプルノードからランダムに選択したセンサノードである。
【００５９】
まず、Ｎ個のノードからランダムにｍ個のサンプルノードを選択し（ステップ２０１）、ｍ個のサンプルノードからｋ個のクラスタヘッドをランダムに選択する（ステップ２０２）。これらｍやｋの値については、全ノード数や階層数に基づき予め決定しておけばよい。この後、ループ１として、ループ２を含むステップ２１１〜２１７を繰り返し実行する。
【００６０】
ループ１では、まず、クラスタヘッド以外のサンプルノードを、当該サンプルノードからクラスタヘッドまでの最小送信電波強度が最も小さいクラスタヘッドのクラスタにそれぞれ割り当てることにより当該階層の基準となる基準クラスタ構成を生成し（ステップ２１１）、この基準クラスタ構成について前述した式（１）の評価関数Ｆを算出して基準評価値Ｆoldとする（ステップ２１２）。
【００６１】
次に、クラスタヘッド以外のサンプルノードから、入れ替え対象となるノードとしてＮrandomをランダムに１つ選択し（ステップ２１３）、クラスタ選択用変数ｉを１に初期化するとともに、比較評価値Ｆnewを∞（無限大または最大値）に設定する（ステップ２１４）。
続いて、変数ｉがクラスタ数ｋに達するまで、ステップ２２１〜２２４からなるループ２を繰り返し実行する。
【００６２】
ループ２では、まず、クラスタヘッドＮHiをＮrandomと入れ替えて候補クラスタ構成を生成し、この候補クラスタ構成について前述した式（１）の評価関数Ｆを算出して候補評価値Ｆcを算出し（ステップ２１１）、比較評価値Ｆnewと比較する（ステップ２２２）。ここで、Ｆnew＞Ｆcの場合（ステップ２２２：ＹＥＳ）、Ｆcを新たなＦnewとして設定し（ステップ２２３）、変数ｉを１だけ加算する（ステップ１１５）。また、Ｆnew≦Ｆcの場合（ステップ２２２：ＮＯ）、ステップ２２４へ移行する。
【００６３】
このようにして、すべてのクラスタについてループ２を繰り返し実行することにより、これらクラスタをＮrandomと入れ替えて生成した候補クラスタ構成から、最も小さい候補評価値Ｆcを持つ候補クラスタ構成を見つけて、その候補評価値Ｆcを示す評価値Ｆnewと基準評価値Ｆoldとを比較する（ステップ２１５）。
【００６４】
ここで、Ｆnew＜Ｆoldの場合（ステップ２１５：ＹＥＳ）、Ｆnewが最小となったＮHiとＮrandomとを入れ替えて、最小候補評価値を持つ候補クラスタ構成を当該階層のクラスタ構成として決定し（ステップ２１６）、ループ１の先頭であるステップ２１１へ戻る。また、Ｆnew≧Ｆoldの場合（ステップ２１５：ＮＯ）、上記入れ替えを行わずに、基準クラスタ構成を当該階層のクラスタ構成として決定し、ループ１を脱出して一連のクラスタリング処理を終了する。
【００６５】
ネットワーク構築装置３０は、クラスタリング処理装置３４により、このようなクラスタリング処理を階層ごとに繰り返し実行することにより、センサネットワーク５０のトポロジを決定する。
この後、ネットワーク構築装置３０は、クラスタリング処理装置３４で決定したトポロジに基づいて、ネットワーク設定装置３５により、各センサノード１０に関する通信相手ノードと当該通信相手ノードに関する最小送信電波強度とを決定する。
【００６６】
この際、子ノードのセンサデータを送信すべき通信相手ノードは、同一クラスタに属するクラスタヘッドとなり、クラスタヘッドのセンサデータを収集すべき通信相手ノードは、その逆となる。また、各センサノードの最小送信電波強度は、当該通信相手ノードとの間の最小送信電波強度を最小送信電波強度収集装置３２から取得すればよい。
このようにして、ネットワーク設定装置３５は、各センサノード１０に関する通信相手ノードと当該通信相手ノードに関する最小送信電波強度とを決定し、無線通信装置３１からセンサネットワークを介して各センサノードへ通知する。これにより、センサデータ収集に適したセンサネットワーク５０が構築されることになる。
【００６７】
次に、図９を参照してクラスタリング処理例について説明する。ここでは、１３個のノードを３つのクラスタに分割する場合を例として説明する。以下のステップ（ａ）〜（ｇ）は、図９（ａ）〜図９（ｇ）に相当する。
【００６８】
（ａ）ノードの中からランダムにサンプルを選択する。ここでは、６個のサンプルを選択した。
（ｂ）サンプルの中からランダムにクラスタヘッドを選択する。この例では３つのクラスタに分割するため、３つのクラスタヘッドＰ1、Ｐ2、Ｐ3を選択する。
（ｃ）クラスタヘッド以外のサンプルノードをクラスタリングし、評価関数Ｆを計算し、Ｆoldとする。各ノードは最小距離のクラスタヘッドのクラスタに所属するため、この例ではＰ1のクラスタには２個のノードが、Ｐ2のクラスタには０個のノードが、Ｐ3のクラスタには１個のノードがそれぞれ所属する。また、Ｐ1からＣ12への通信は、クラスタ外のＰ2，Ｐ3の２個のノードでも受信でき、Ｐ3からＣ31の通信はクラスタ外のＰ1、Ｃ11、Ｃ12，Ｐ2でも受信できる。このように通信の重なり、すなわち無線通信干渉度合いを数えることで評価関数Ｆを算出する。
【００６９】
（ｄ）クラスタヘッド以外のサンプルノードの中から１つをＮrandomとして選択する。この例では、Ｃ31が選ばれたとする。
（ｅ）Ｎrandomとクラスタヘッドを入れ替えた場合のＦcを計算し、最小となるものをＦnewとする。この例では、クラスタヘッドが３つあるため、Ｐ1と入れ替えるパターン１、Ｐ2と入れ替えるパターン２、Ｐ3と入れ替えるパターン３の３つのパターンについて計算を行うことになる。３つのパターンの中では、狭い範囲に同一クラスタのノードが集中するパターン２やパターン３がパターン１や現在のクラスタヘッドの配置よりもＦの値が小さく、無線通信干渉の少ない良好なクラスタリングとなる。ここでは、パターン３の場合にＦnewが最小になったものとする。
【００７０】
（ｆ）Ｆnewを最小にしたクラスタヘッドとＮrandomを入れ替える。ＦnewがＦoldよりも大きく、つまりクラスタヘッドを変更しない方が評価が高いならば、入れ替えを行わずにクラスタヘッドを確定させてクラスタリング処理を終了する。一方、入れ替えを行ったときは、ステップ（ｃ）以降の処理を繰り返す。この例では、Ｐ3とＮrandomとを入れ替え、再度処理を繰り返す。
（ｇ）確定されたクラスタヘッドを用いて、すべてのノードを最短距離のクラスタヘッドのクラスタに所属させることでクラスタリングを行う。
【００７１】
以上のクラスタリング処理において、クラスタリングの結果はサンプルの選択やクラスタヘッドの初期選択に左右されるため、評価関数Ｆが予め定めた値以下ではなくクラスタリングの精度が不十分に場合は、何度か繰り返してクラスタリングを行い、その中から最適なものを選択する。
【００７２】
最下位の階層のクラスタリングが終了すると、各クラスタの中から最適なクラスタヘッドを選択し直し、クラスタヘッドのみを用いて１つ上位の階層のクラスタリングを行う。これを繰り返し、すべての階層のクラスタを決定する。したがって、最上位階層ＬHに予め設定しておいた、基地局２０がクラスタヘッドとなる１つのクラスタに対して、すべてのノードが所属することになる。
すべての階層におけるクラスタリング処理が終了すると、データを収集するためのトポロジと、各ノード間の通信での最適な電波強度が決まるため、基地局２０が、ノードのクラスタヘッド、子ノードの一覧、それぞれの通信における送信電波強度をすべてのノードに対して通知する。これによって、データ収集が開始できるようになる。
【００７３】
図１０は、本実施の形態にかかるセンサデータ収集システムの評価結果を示す説明図である。図１１は、評価に用いたトポロジを示す説明図である。
ここでは、本実施の形態にかかるセンサデータ収集方法と、従来のポーリング手法とについて、４つのセンサノードからセンサデータを基地局２０へ収集する際に発生する遅延時間を測定した。本実施の形態にかかるセンサデータ収集方法では、図１１のトポロジのセンサネットワーク５０を用いた。また、無線通信にはＩＥＥＥ８０２．１５．４準拠の無線通信モジュールを用いた。評価の結果、センサノード数が少ないにもかかわらず、従来のポーリング手法に比べて、本実施の形態にかかるセンサデータ収集方法の方が、データ収集に要する所要時間、すなわち遅延が少なくなる傾向にあることが分かる。
【符号の説明】
【００７４】
１…センサデータ収集システム、１０…センサノード、１１…センサ、１２…センサイベント検出装置、１３…センサデータ処理装置、１４…センサデータ記憶装置、１５…無線通信装置、２０…基地局、２１…無線通信装置、２２…受信データ処理装置、３０…ネットワーク構築装置、３１…無線通信装置、３２…最小送信電波強度収集装置、３３…評価値算出装置、３４…クラスタリング処理装置、３５…ネットワーク設定装置、５０…センサネットワーク。
【特許請求の範囲】
【請求項１】
複数の階層を有するセンサネットワークを無線通信により構成する複数のセンサノードと、各センサノードでセンシングした当該センサノードの周囲状況を示すセンサデータを前記センサネットワークを介して収集する基地局とを含み、前記センサネットワークは、前記階層ごとに１つ以上のクラスタを有し、任意のセンサノードからなる１つ以上の子ノードと１つのクラスタヘッドとから前記クラスタが構成され、当該クラスタ内の前記子ノードと前記クラスタヘッドとが無線通信を行うとともに、前記クラスタヘッドが１つ上位の階層における任意の上位クラスタの子ノードとして動作し、最上位階層に構成する１つのクラスタのクラスヘッダが前記基地局からなる、階層クラスタ構造を有するセンサデータ収集システムにおいて、
前記各センサノードで検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、前記センサネットワークを介してそれぞれ収集する最小送信電波強度収集装置と、
これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出装置と、
階層ごとに複数選択したクラスタ構成について前記評価値算出装置で前記評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、前記センサネットワークのトポロジを決定するクラスタリング処理装置と、
前記トポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、前記センサネットワークを介して前記各センサノードへ通知するネットワーク設定装置と
を備えることを特徴とするセンサネットワーク構築装置。
【請求項２】
請求項１に記載のセンサネットワーク構築装置において、
前記クラスタリング処理装置は、任意の階層についてクラスタ構成を決定する際、当該階層に含まれるノードからランダムにサンプルノードを選択し、
このサンプルノードから各クラスタのクラスタヘッドをそれぞれ任意に選択し、
前記クラスタ以外のサンプルノードを当該サンプルノードから最も小さい電波強度で通信可能なクラスタヘッドのクラスタにそれぞれ割り当てて当該階層の基準となるクラスタ構成を生成して、前記評価値算出装置により前記基準クラスタ構成に関する基準評価値を算出し、
前記基準クラスタ構成のうちクラスタヘッド以外のサンプルノードからランダムに選択して当該クラスタのクラスタヘッドと入れ替えた候補クラスタ構成を順次生成して、前記評価値算出装置により前記候補クラスタ構成に関する候補評価値を算出し、
前記候補評価値のうち最も小さい最小候補評価値と前記基準評価値とを比較し、いずれか小さい方のクラスタ構成を当該階層のクラスタ構成として決定することを特徴とするセンサネットワーク構築装置。
【請求項３】
複数の階層を有するセンサネットワークを無線通信により構成する複数のセンサノードと、各センサノードでセンシングした当該センサノードの周囲状況を示すセンサデータを前記センサネットワークを介して収集する基地局とを含み、前記センサネットワークは、前記階層ごとに１つ以上のクラスタを有し、任意のセンサノードからなる１つ以上の子ノードと１つのクラスタヘッドとから前記クラスタが構成され、当該クラスタ内の前記子ノードと前記クラスタヘッドとが無線通信を行うとともに、前記クラスタヘッドが１つ上位の階層における任意の上位クラスタの子ノードとして動作し、最上位階層に構成する１つのクラスタのクラスヘッダが前記基地局からなる、階層クラスタ構造を有するセンサデータ収集システムにおいて、
最小送信電波強度収集装置が、前記各センサノードで検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、前記センサネットワークを介してそれぞれ収集する最小送信電波強度収集ステップと、
評価値算出装置が、これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出ステップと、
クラスタリング処理装置が、階層ごとに複数選択したクラスタ構成について前記評価値算出装置で前記評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、前記センサネットワークのトポロジを決定するクラスタリング処理ステップと、
ネットワーク設定装置が、前記トポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、前記センサネットワークを介して前記各センサノードへ通知するネットワーク設定ステップと
を備えることを特徴とするセンサネットワーク構築方法。
【請求項４】
請求項３に記載のセンサネットワーク構築方法において、
前記クラスタリング処理装置が、任意の階層についてクラスタ構成を決定する際、当該階層に含まれるノードからランダムにサンプルノードを選択し、このサンプルノードから各クラスタのクラスタヘッドをそれぞれ任意に選択し、前記クラスタ以外のサンプルノードを当該サンプルノードから最も小さい電波強度で通信可能なクラスタヘッドのクラスタにそれぞれ割り当てて当該階層の基準となるクラスタ構成を生成して、前記評価値算出装置により前記基準クラスタ構成に関する基準評価値を算出し、前記基準クラスタ構成のうちクラスタヘッド以外のサンプルノードからランダムに選択して当該クラスタのクラスタヘッドと入れ替えた候補クラスタ構成を順次生成して、前記評価値算出装置により前記候補クラスタ構成に関する候補評価値を算出し、前記候補評価値のうち最も小さい最小候補評価値と前記基準評価値とを比較し、いずれか小さい方のクラスタ構成を当該階層のクラスタ構成として決定することを特徴とするセンサネットワーク構築方法。
【請求項５】
コンピュータを、請求項１または請求項２に記載のセンサネットワーク構築装置を構成する各部として機能させるためのプログラム。
【請求項１】
複数の階層を有するセンサネットワークを無線通信により構成する複数のセンサノードと、各センサノードでセンシングした当該センサノードの周囲状況を示すセンサデータを前記センサネットワークを介して収集する基地局とを含み、前記センサネットワークは、前記階層ごとに１つ以上のクラスタを有し、任意のセンサノードからなる１つ以上の子ノードと１つのクラスタヘッドとから前記クラスタが構成され、当該クラスタ内の前記子ノードと前記クラスタヘッドとが無線通信を行うとともに、前記クラスタヘッドが１つ上位の階層における任意の上位クラスタの子ノードとして動作し、最上位階層に構成する１つのクラスタのクラスヘッダが前記基地局からなる、階層クラスタ構造を有するセンサデータ収集システムにおいて、
前記各センサノードで検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、前記センサネットワークを介してそれぞれ収集する最小送信電波強度収集装置と、
これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出装置と、
階層ごとに複数選択したクラスタ構成について前記評価値算出装置で前記評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、前記センサネットワークのトポロジを決定するクラスタリング処理装置と、
前記トポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、前記センサネットワークを介して前記各センサノードへ通知するネットワーク設定装置と
を備えることを特徴とするセンサネットワーク構築装置。
【請求項２】
請求項１に記載のセンサネットワーク構築装置において、
前記クラスタリング処理装置は、任意の階層についてクラスタ構成を決定する際、当該階層に含まれるノードからランダムにサンプルノードを選択し、
このサンプルノードから各クラスタのクラスタヘッドをそれぞれ任意に選択し、
前記クラスタ以外のサンプルノードを当該サンプルノードから最も小さい電波強度で通信可能なクラスタヘッドのクラスタにそれぞれ割り当てて当該階層の基準となるクラスタ構成を生成して、前記評価値算出装置により前記基準クラスタ構成に関する基準評価値を算出し、
前記基準クラスタ構成のうちクラスタヘッド以外のサンプルノードからランダムに選択して当該クラスタのクラスタヘッドと入れ替えた候補クラスタ構成を順次生成して、前記評価値算出装置により前記候補クラスタ構成に関する候補評価値を算出し、
前記候補評価値のうち最も小さい最小候補評価値と前記基準評価値とを比較し、いずれか小さい方のクラスタ構成を当該階層のクラスタ構成として決定することを特徴とするセンサネットワーク構築装置。
【請求項３】
複数の階層を有するセンサネットワークを無線通信により構成する複数のセンサノードと、各センサノードでセンシングした当該センサノードの周囲状況を示すセンサデータを前記センサネットワークを介して収集する基地局とを含み、前記センサネットワークは、前記階層ごとに１つ以上のクラスタを有し、任意のセンサノードからなる１つ以上の子ノードと１つのクラスタヘッドとから前記クラスタが構成され、当該クラスタ内の前記子ノードと前記クラスタヘッドとが無線通信を行うとともに、前記クラスタヘッドが１つ上位の階層における任意の上位クラスタの子ノードとして動作し、最上位階層に構成する１つのクラスタのクラスヘッダが前記基地局からなる、階層クラスタ構造を有するセンサデータ収集システムにおいて、
最小送信電波強度収集装置が、前記各センサノードで検出した当該ノードと他のノードとの間で無線通信可能な最小送信電波強度値を、前記センサネットワークを介してそれぞれ収集する最小送信電波強度収集ステップと、
評価値算出装置が、これら最小送信電波強度値に基づいて、任意の階層における、各クラスタに属する子ノードとクラスタヘッドとの組合せを示す任意のクラスタ構成について、異なるクラスタに属するセンサノード間における無線通信干渉度合いを示す評価値を算出する評価値算出ステップと、
クラスタリング処理装置が、階層ごとに複数選択したクラスタ構成について前記評価値算出装置で前記評価値を算出し、得られた評価値に基づき階層ごとにクラスタ構成を決定することにより、前記センサネットワークのトポロジを決定するクラスタリング処理ステップと、
ネットワーク設定装置が、前記トポロジに基づいて個々のセンサノードに関する通信相手情報と当該通信相手ノードに関する最小送信電波強度値とを、前記センサネットワークを介して前記各センサノードへ通知するネットワーク設定ステップと
を備えることを特徴とするセンサネットワーク構築方法。
【請求項４】
請求項３に記載のセンサネットワーク構築方法において、
前記クラスタリング処理装置が、任意の階層についてクラスタ構成を決定する際、当該階層に含まれるノードからランダムにサンプルノードを選択し、このサンプルノードから各クラスタのクラスタヘッドをそれぞれ任意に選択し、前記クラスタ以外のサンプルノードを当該サンプルノードから最も小さい電波強度で通信可能なクラスタヘッドのクラスタにそれぞれ割り当てて当該階層の基準となるクラスタ構成を生成して、前記評価値算出装置により前記基準クラスタ構成に関する基準評価値を算出し、前記基準クラスタ構成のうちクラスタヘッド以外のサンプルノードからランダムに選択して当該クラスタのクラスタヘッドと入れ替えた候補クラスタ構成を順次生成して、前記評価値算出装置により前記候補クラスタ構成に関する候補評価値を算出し、前記候補評価値のうち最も小さい最小候補評価値と前記基準評価値とを比較し、いずれか小さい方のクラスタ構成を当該階層のクラスタ構成として決定することを特徴とするセンサネットワーク構築方法。
【請求項５】
コンピュータを、請求項１または請求項２に記載のセンサネットワーク構築装置を構成する各部として機能させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１２−５４９８９（Ｐ２０１２−５４９８９Ａ）
【公開日】平成２４年３月１５日（２０１２．３．１５）
【国際特許分類】
【出願番号】特願２０１１−２３２６３３（Ｐ２０１１−２３２６３３）
【出願日】平成２３年１０月２４日（２０１１．１０．２４）
【分割の表示】特願２００８−４４０３５（Ｐ２００８−４４０３５）の分割
【原出願日】平成２０年２月２６日（２００８．２．２６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２４年３月１５日（２０１２．３．１５）
【国際特許分類】
【出願日】平成２３年１０月２４日（２０１１．１０．２４）
【分割の表示】特願２００８−４４０３５（Ｐ２００８−４４０３５）の分割
【原出願日】平成２０年２月２６日（２００８．２．２６）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]