(57)【特許請求の範囲】
【請求項１】
複数のツリー型クラスタで構成されるワイヤレスセンサネットワーク（WSN）において，まだどのクラスタにも属していない浮遊センサノードをどのクラスタに接続するかを決定する複数ツリー経路選択システムであって、
自クラスタに隣接する隣接浮遊センサノードの区間とその評価値を隣接センサリストとして隣接センサリスト記憶手段に保持するクラスタヘッドと、
前記クラスタヘッドから収集した各クラスタの情報を管理クラスタリストとして管理クラスタリスト記憶手段に保持するベースステーションと、
を有し、
前記クラスタヘッドは、
前記隣接センサリスト記憶手段から、評価値が最も小さい隣接浮遊センサノードを当該評価値とともに、前記ベースステーションに通知する手段を有し、
前記ベースステーションは、
前記クラスタヘッドから通知された情報を前記管理クラスタリスト記憶手段に格納し、当該管理クラスタリスト記憶手段内で最も小さい評価値を持つクラスタを選択し、当該クラスタのクラスタヘッドに対して、当該クラスタヘッドが通知した隣接浮遊センサノードを当該クラスタに接続させるように要求する手段を有する
ことを特徴する複数ツリー経路選択システム。
【請求項２】
複数のツリー型クラスタで構成されるワイヤレスセンサネットワーク（WSN）において，まだどのクラスタにも属していない浮遊センサノードをどのクラスタに接続するかを決定する複数ツリー経路選択システムであって、
自クラスタに隣接する隣接浮遊センサノードの区間とその評価値を隣接センサリストとして隣接センサリスト記憶手段に保持するクラスタヘッドと、
前記クラスタヘッドから収集した各クラスタの情報を管理クラスタリストとして管理クラスタリスト記憶手段に保持するベースステーションと、
を有し、
前記クラスタヘッドは、
前記隣接センサリスト記憶手段から、評価値が最も小さい隣接浮遊センサノードを当該評価値とともに、前記ベースステーションに通知する手段を有し、
前記ベースステーションは、
前記クラスタヘッドから通知された情報を前記管理クラスタリスト記憶手段に格納し、各クラスタの評価値とクラスタ間の負荷バランスを考慮した最適なクラスタを選択し、当該クラスタのクラスタヘッドに対して、当該クラスタヘッドが通知した隣接浮遊センサノードを当該クラスタに接続させるように要求する手段を有する
ことを特徴する複数ツリー経路選択システム。
【請求項３】
前記ベースステーションは、
選択したクラスタのクラスタヘッドが通知した隣接浮遊センサノードを、当該クラスタヘッドだけでなく、他のクラスタヘッドにも通知する手段を更に有し、
通知を受けた各クラスタヘッドは、
前記隣接センサリスト記憶手段を検索して、前記ベースステーションから通知された前記隣接浮遊センサノードが存在するか否かを判定し、当該隣接浮遊センサノードが存在した場合は該隣接浮遊センサノードを隣接センサリスト記憶手段から削除するとともに、該隣接浮遊センサノードまでの評価値が最小だった場合は、最小評価値を保持する新規の隣接浮遊センサを前記ベースステーションに通知する手段を更に有する
請求項１または２記載の複数ツリー経路選択システム。
【請求項４】
前記評価値は、
dist2+child+hop
（但し、distは区間の距離、childは隣接区間のクラスタ側のセンサノードのツリー上の子センサノード数、hopはクラスタヘッドから隣接センサノードまでのホップ数）
とする
請求項１乃至３のいずれか１項に記載の複数ツリー経路選択システム。
【請求項５】
複数のツリー型クラスタで構成されるワイヤレスセンサネットワーク（WSN）において，まだどのクラスタにも属していない浮遊センサノードをどのクラスタに接続するかを決定する複数ツリー経路選択方法であって、
自クラスタに隣接する隣接浮遊センサノードの区間とその評価値を隣接センサリストとして隣接センサリスト記憶手段に保持するクラスタヘッドと、
前記クラスタヘッドから収集した各クラスタの情報を管理クラスタリストとして管理クラスタリスト記憶手段に保持するベースステーションと、
を有するシステムにおいて、
前記クラスタヘッドが、前記隣接センサリスト記憶手段から、評価値が最も小さい隣接浮遊センサノードを当該評価値とともに、前記ベースステーションに通知するステップと、
前記ベースステーションが、前記クラスタヘッドから通知された情報を前記管理クラスタリスト記憶手段に格納し、当該管理クラスタリスト記憶手段内で最も小さい評価値を持つクラスタを選択し、当該クラスタのクラスタヘッドに対して、当該クラスタヘッドが通知した隣接浮遊センサノードを当該クラスタに接続させるように要求するステップと、
を行うことを特徴する複数ツリー経路選択方法。
【請求項６】
複数のツリー型クラスタで構成されるワイヤレスセンサネットワーク（WSN）において，まだどのクラスタにも属していない浮遊センサノードをどのクラスタに接続するかを決定する複数ツリー経路選択方法であって、
自クラスタに隣接する隣接浮遊センサノードの区間とその評価値を隣接センサリストとして隣接センサリスト記憶手段に保持するクラスタヘッドと、
前記クラスタヘッドから収集した各クラスタの情報を管理クラスタリストとして管理クラスタリスト記憶手段に保持するベースステーションと、
を有するシステムにおいて、
前記クラスタヘッドが、前記隣接センサリスト記憶手段から、評価値が最も小さい隣接浮遊センサノードを当該評価値とともに、前記ベースステーションに通知するステップと、
前記ベースステーションが、前記クラスタヘッドから通知された情報を前記管理クラスタリスト記憶手段に格納し、各クラスタの評価値とクラスタ間の負荷バランスを考慮した最適なクラスタを選択し、当該クラスタのクラスタヘッドに対して、当該クラスタヘッドが通知した隣接浮遊センサノードを当該クラスタに接続させるように要求するステップと、
を行うことを特徴する複数ツリー経路選択方法。
【請求項７】
前記ベースステーションにおいて、
選択したクラスタのクラスタヘッドが通知した隣接浮遊センサノードを、当該クラスタヘッドだけでなく、他のクラスタヘッドにも通知するステップを更に行い、
通知を受けた各クラスタヘッドにおいて、
前記隣接センサリスト記憶手段を検索して、前記ベースステーションから通知された前記隣接浮遊センサノードが存在するか否かを判定し、当該隣接浮遊センサノードが存在した場合は該隣接浮遊センサノードを隣接センサリスト記憶手段から削除するとともに、該隣接浮遊センサノードまでの評価値が最小だった場合は、最小評価値を保持する新規の隣接浮遊センサを前記ベースステーションに通知するステップを更に行う
請求項５または６記載の複数ツリー経路選択方法。
【請求項８】
前記評価値は、
dist2+child+hop
（但し、distは区間の距離、childは隣接区間のクラスタ側のセンサノードのツリー上の子センサノード数、hopはクラスタヘッドから隣接センサノードまでのホップ数）
とする
請求項５乃至７のいずれか１項に記載の複数ツリー経路選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数ツリー経路選択システム及び方法に係り、特に、ワイヤレスセンサネットワーク(WSN)上でルートセンサノードを頂点とする複数センサノードからなるツリー型クラスタが複数作成され、各クラスタヘッドがツリー上の各センサノードのセンシングデータを集約してベースステーション等の上位システムに当該センシングデータを転送する形態の複数ツリー経路選択システム及び方法に関する。
【背景技術】
【０００２】
特定の場所や地域にセンサを配置し、対象地の湿度、温度、気体濃度等をセンサノードによって計測し、その平均値、最大値／最小値等をセンサノードツリーで集約し、ルートセンサノードからベースステーションに通知することによって対象地の分析を行う、あるいは、ガスメータ、電気メータなどの情報を定期的にセンサノードツリーで集約することを可能にする技術として、RPL(Routing Protocol for Low-power and Lossy Networks)プロトコルが標準化されている（非特許文献１参照）。
【０００３】
センサノードは、電池稼動のものが多く、各センサノード電池寿命内でのデータ送受信回数を最大にするツリー経路選択方法が求められる。特に、二つの異なるセンサノード間距離が大きい場合は送信のために必要になる消費電力が距離の２乗に比例して大きくなることが知られている。そのため、ツリーを構成するセンサノード間の距離が小さくなるようなツリー経路選択方法が求められる。また、センサノードの他の主な電力消費要因として、データ受信する回数が多いセンサノードは、その数に比例して電力消費がかかるので、ツリー上で各センサノード直下のセンサノード数を大きくしないツリー経路選択方法が求められる。そのため，RPLを改良し、各クラスタヘッドに隣接センサリストを保持させ、距離、ツリー上の子センサ数等を評価値のパラメータとして考慮し、評価値の小さい隣接センサをツリーに接続させる手法が提案されている（非特許文献２参照）。
【０００４】
また、クラスタヘッドはクラスタに属する他のセンサと異なり、電力供給がネットワークで行われることが想定されるので、ベースステーション、クラスタヘッド等で他のセンサのルーティング機能を代替することにより他センサの省電力を実現する手法も有力である。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】T. Winter, et al., "RPL: IPv6 Routing Protocol for Low-power and Lossy Networks", RFC6550, IETF6550, IETF, March 2012.
【非特許文献２】松浦,"省電力マルチホップセンサーネットワークを構築するルーティングフレームワークの提案", 信学技法 IN2013-95.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら非特許文献１，２ともに１つのクラスタ内のツリー構成手法については検討しているが、クラスタ間でどのように連携して複数ツリーを作成していくかについては述べられていない。非特許文献２ではランダムに選択されたクラスタヘッドが自分の隣接センサリストから最も評価値の小さいセンサノードを自ツリーに接続する手法をとっている。しかし、この手法では複数ツリー間の最適化が行われない問題がある。
【０００７】
非特許文献２の従来方式で問題になる例を図１を用いて説明する。
【０００８】
図１においてT1_CHとT2_CHはクラスタヘッドを示し、T1_CHが属するツリー型クラスタには、現在T1_CHの配下にT1_1とT1_2のセンサノードが所属している。T2_CHの配下にはT2_1が接続している。S1〜S4はクラスタに所属していない浮遊センサノードを示し、点線で示されるのはセンサノード間の隣接関係を示す。また点線上の数字は当該区間の距離を示す。各クラスタヘッドは隣接センサリストを保持し、そのクラスタに隣接する浮遊センサノードまでの区間とその評価値を示す。ここで、
評価値＝dist2+child+hop
で示されるが、この式でdistは区間の距離を示し、childは隣接区間のクラスタ側のセンサノードのツリー上の子センサノード数を示し、hopはクラスタヘッドから隣接センサノードまでのホップ数を示す。区間距離を2乗にしているのは、センサノードの送信電力が距離の2乗に比例することを反映している。また、子センサノードの数が多い場合はツリー上で受信するデータが大きくなることを示している。つまり、評価値が小さい隣接センサノードがクラスタに接続されるべきなのである。なお、T2_CHの隣接センサリストでは、T2_1-S2は保持されない。理由はこの隣接センサノードS2はすでにT2_CHの隣接センサノードとしてリストに登録されており、その区間T2_1-S2の評価値が18で、T2_CH-S2の評価値と同じであり、小さくないからである。つまり、各隣接センサノードまでの最小評価値を持つ区間をただ１つのみ隣接センサリストでは保持する。
【０００９】
この例でもし、T2_CHがT1_CHより先に隣接センサリストから最小の評価値を持つ隣接センサS2を選択した場合は、S2はT2_CHの配下に接続させられることになる。しかし、S2からT2_CHにセンシングデータを送信するときにはその距離が4と長くなり、S2の送信電力消費量が大きくなる問題がある。つまり、クラスタヘッド間で最適な評価値を反映したツリー構成ができていない。
【００１０】
また、ある一定のクラスタに接続するセンサノード数が大きくなりクラスタ間の負荷分散が均等にできない問題も生じる可能性がある。
【００１１】
本発明は、上記の点に鑑みなされたもので、複数のクラスタヘッドの共有上位システムが複数のクラスタに跨り最適な評価値を持つ隣接センサノードの検索を可能とし、各クラスタの負荷を管理し、均等な負荷分散が可能な複数ツリー経路選択システム及び方法を提供することを目的とする。
【課題を解決するための手段】
【００１２】
一態様によれば、複数のツリー型クラスタで構成されるワイヤレスセンサネットワーク（WSN）において、まだどのクラスタにも属していない浮遊センサノードをどのクラスタに接続するかを決定する複数ツリー経路選択システムであって、
自クラスタに隣接する隣接浮遊センサノードの区間とその評価値を隣接センサリストとして隣接センサリスト記憶手段に保持するクラスタヘッドと、
前記クラスタヘッドから収集した各クラスタの情報を管理クラスタリストとして管理クラスタリスト記憶手段に保持するベースステーションと、
を有し、
前記クラスタヘッドは、
前記隣接センサリスト記憶手段から、評価値が最も小さい隣接浮遊センサノードを当該評価値とともに、前記ベースステーションに通知する手段を有し、
前記ベースステーションは、
前記クラスタヘッドから通知された情報を前記管理クラスタリスト記憶手段に格納し、当該管理クラスタリスト記憶手段内で最も小さい評価値を持つクラスタを選択し、当該クラスタのクラスタヘッドに対して、当該クラスタヘッドが通知した隣接浮遊センサノードを当該クラスタに接続させるように要求する手段を有する複数ツリー経路選択システムが提供される。
【発明の効果】
【００１３】
一態様によれば、複数のクラスタヘッドの共通上位システムが複数クラスタに跨り最適な評価値を持つ隣接センサノードを検索できるだけでなく、各クラスタの負荷を管理し、均等な負荷分散を可能にする。また、新規に接続するセンサノードをすべてのクラスタヘッドに通知するので、各クラスタヘッドが保持する隣接センサリストに、実際の浮遊しているセンサノードを正確に反映することが可能である。
【００１４】
よって、評価値が小さい隣接センサノードが各クラスタに繋がるとともに、クラスタ間で均等に負荷分散ができるため，各センサの省電力を実現できる。
【図面の簡単な説明】
【００１５】
【図１】従来の問題点と実施例で想定するWSNである。
【図２】本発明の一実施の形態における複数ツリー経路選択システムの構成例である。
【図３】本発明の一実施の形態におけるベースステーションでの下位クラスタ管理例である。
【図４】本発明の一実施の形態におけるベースステーションとクラスタの処理のシーケンスチャートである。
【図５】本発明の一実施の形態における管理クラスタリスト、隣接センサリストの更新例である。
【図６】本発明の一実施の形態における管理クラスタリスト、隣接センサリストの更新処理のシーケンスチャートである。
【発明を実施するための形態】
【００１６】
以下、図面と共に本発明の実施の形態を説明する。
【００１７】
図２は、本発明の一実施の形態における複数ツリー経路選択システムの構成例を示す。
【００１８】
同図に示すシステムは、ベースステーション１００と複数のクラスタヘッド２００、図２には図示しないが、図３に示すように、クラスタヘッド２００には複数のセンサノードが接続されている。
【００１９】
ベースステーション１００は、インタフェース（I/F）１１０、経路選択部１２０、図３に示すような管理クラスタリスト記憶部１３０を有する。
【００２０】
各クラスタヘッド２００は、インタフェース(I/F)２１０、検索・更新部２２０、図３に示すような隣接センサリスト記憶部２３０を有する。
【００２１】
図３は、図１のWSNに本発明を適用した場合の一実施形態を示し、図４はそのシーケンスを示す。
【００２２】
図３において、T3_CHはT1_CH, T2_CHと同様に、クラスタのクラスタヘッドを示す。S5は浮遊センサノードであり、クラスタヘッドのT3_CHと隣接関係にある。
【００２３】
ベースステーション１００は、各クラスタヘッド２００から最小の評価値を持つ隣接センサノード情報をI/F１１０を介して通知されており、その情報を評価値が小さい順に管理クラスタリスト記憶部１３０の管理クラスタリスト内で管理している。この管理クラスタリストによって、どのセンサノードが最も評価値が小さいかを把握することができる。
【００２４】
管理クラスタリスト記憶部１３０の管理クラスタリストには、クラスタを代表するクラスタヘッドと、そのクラスタに隣接する最小評価値を持つセンサノードと、その評価値、クラスタに属するセンサノード数を持つ。このセンサノード数は各クラスタの負荷指標として使うことができる。つまり、多くのセンサノードが一つのクラスタに固まるのを防ぐことが可能になる。
【００２５】
この実施の形態では、クラスタヘッド２００（以下、クラスタヘッドを単に、「T1_CH」「T2_CH」…と記す）T1_CHに代表されるクラスタが最も小さな評価値（＝3）を持つ隣接センサノードを隣接センサリスト記憶部２３０に保持するので、ベースステーション１００の経路選択部１２０は、Ｉ／Ｆ１１０を介してT1_CHに対してS2をツリーに接続するように通知する（ステップ１０１）。この通知を受けたT1_CHは自分の隣接センサリスト記憶部２３０の隣接センサリストでS2がT1_2に隣接していることが確認できるので、T1_2の配下にS2を接続する（ステップ１０２）。
【００２６】
ステップ１０２の処理の後、S2はすでにT1_CHをヘッドとするクラスタに所属し、隣接浮遊センサノードではなくなったので、T1_CHは、隣接センサリストから区間(T1_2-S2)、評価値(1+0+2=3)を削除する（ステップ１０３）。
【００２７】
図５は、図４でのステップ１０２において、S2接続要求を受けたT1_CHとS2削除要求を受けたT2_CHの隣接センサリスト更新処理と、その結果のベースステーション１００への送信内容を示す。また、これらの送信内容を受けたベースステーション１００の管理クラスタリスト記憶部１３０内の管理クラスタリストの更新内容を示す。図６はそのシーケンスを示す。
【００２８】
T1_CHはS2接続要求を受けた場合（ステップ１０１）、S2をT1_2配下にT1_3として接続する（ステップ２０１）。その場合、T1_3は隣接している浮遊センサノードであるS1とT1_3−S1の距離（＝2）をT1_CHに知らせる（ステップ２０２）。T1_3はT2_CH, T2_1とも隣接しているが、これらのセンサノードはすでにT2_CH配下のクラスタに所属しているので、T1_CHには通知されない。このT1_3からの通知を受けたT1_CHの検索・更新部２２０は、保持する隣接センサリストの評価値を比較して更新する（ステップ２０３）。いままでの隣接センサS1の評価値はT1_CH-S1の28であったが、T1_3-S1の評価値7がこの値よりも小さいため入れ替えられる。また、T1_CH-S3の評価値は51から52に増加する。この理由はT1_2配下に子センサノードであるT1_3が接続されたからである。結果としてT1_CH配下クラスタの最小評価値を持つ隣接センサノードはS1となり、その評価値は7であることをベースステーション１００に伝える（ステップ２０４（図４のステップ１０４））。
【００２９】
T1_CHから隣接センサノードの更新内容を通知されたベースステーション１００の経路選択部１２０は、管理クラスタリストのT1_CHのクラスタについて、センサ（S2→S1）、評価値(3→7)、センサ数（3→4）に更新する（ステップ１０５）。
【００３０】
この結果から現在最も評価値が小さい隣接センサはS1であることがわかり次の接続センサとなる。
【００３１】
また、ベースステーション１００の経路選択部１２０は、S2がT1_CHクラスタに接続されたので、他のクラスタの隣接センサリストからS2を削除することを、I/F１１０を介して、S2削除要求としてT2_CH, T3_CHに要求する（ステップ１０６）。
【００３２】
この要求を受けたT2_CHの検索・更新部２２０は、保持する隣接センサリスト記憶部２３０の隣接センサリストからS2とその区間(T2_CH-S2)と評価値（16+1+1=18）を削除し（ステップ１０７）、更新後の隣接センサリストの更新内容をベースステーション１００に通知する（ステップ１０８）。ベースステーション１００の経路選択部１２０は、T2_CHからの更新内容通知に基づいて、当該T2_CHについて、管理クラスタリストをセンサ（S2→S4）、評価値（18→27）と更新する（ステップ１０９）。
【００３３】
T3-CHもベースステーション１００からS2削除要求を受けるが、検索・更新部２２０は、T3-CHが保持する隣接センサリストにS2があるかどうか判断し（ステップ１１０）、存在する場合は削除して更新するが（ステップ１１１，１１２）、存在しない場合は隣接センサリストを変更しない。T3_CHは確認メッセージをベースステーション１００に通知する（ステップ１１３）。図３、図５の例では、削除されたS2は管理クラスタリスト内のT3_CHの最小評価値を持つ隣接センサではないのでベースステーション１００内の管理クラスタリストは更新されない。
【００３４】
上記のように、ベースステーション１００は、下位のクラスタヘッドからの最小評価値を持つ隣接センサ更新通知がある場合は管理クラスタリストに反映させる。
【００３５】
評価値は最も大きな接続判断要素となるが、あまりあるクラスタ配下のセンサ数が多くなった場合は、クラスタのセンサノード数を考慮して負荷分散する手法も考えられる（請求項２、６）。例えば、管理クラスタリスト記憶部１３０の管理クラスタリスト中のクラスタのセンサノード数と評価値を足し合わせた値が最小となるセンサノードを接続センサとして選択する手法がその一例である。
【００３６】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００３７】
１００  ベースステーション
１１０  I/F  （インタフェース）
１２０  経路選択部
１３０  管理クラスタリスト記憶部
２００  クラスタヘッド
２１０  I/F  （インタフェース）
２２０  検索・更新部
２３０  隣接センサリスト記憶部
【図１】
0006043741.tif 000002
【図２】
0006043741.tif 000003
【図３】
0006043741.tif 000004
【図４】
0006043741.tif 000005
【図５】
0006043741.tif 000006
【図６】
0006043741.tif 000007