JP2017038148A - ツリー経路決定装置、及びツリー経路決定方法 - Google Patents

Abstract

【課題】センサーノードからなるセンサーツリーを作成する際に、ツリー経路の決定を効率的に行う。【解決手段】センサーツリーにおけるルートセンサーノードと、当該センサーツリーに接続していない浮遊センサーとを有するシステムにおいて、当該浮遊センサーと当該浮遊センサーに隣接する親ツリーセンサーノードとの間の接続関係を決定するツリー経路決定装置において、前記ルートセンサーノードからのホップ数として定義されるレベル毎に浮遊センサーの情報を取得するセンサー情報取得手段と、前記浮遊センサーの情報の取得を行うレベルにおける新たなツリーセンサーノードとして、当該浮遊センサーを１つレベルの小さい親ツリーセンサーノード直下に接続させる経路決定手段とを備える。【選択図】図４

Description

本発明は、ワイヤレスセンサーネットワーク(WSN)上でルートセンサーノードを頂点とする複数センサーからなるデータ収集ツリーを作成する技術に関連するものである。このようなデータ収集ツリーでは、ツリー上の各ツリーセンサーノードが、ルートセンサーノードまでツリーに沿ってデータを転送する収集サイクルを繰り返すことにより、ルートセンサーノードが収集したデータをベースステーションに定期的に送信する。

特定の場所／地域にセンサーを配置し、対象地の湿度、温度、気体濃度等をセンサーによって計測し、その平均値、最大／最小値、等をデータ収集ツリーで収集し、ルートセンサーノードからベースステーションに通知することによって対象地の分析を行う、あるいはガスメータ、電気メータなどの情報を定期的にデータ収集ツリーで収集する、ことを可能にする技術として、RPL(Routing Protocol for Low-power and Lossy Networks)プロトコル（非特許文献１）が標準化されている。

センサーは、電池稼働のものが多く、各センサーの電池寿命内での、データ収集ツリーの収集サイクル数を最大限にするようなツリー寿命の長いツリーが求められる。また、ツリーの各リーフセンサノードからルートセンサーノードまでのホップ数が大きい場合は、データ到達率が低くなるため、ルートセンサーノードまでのホップ数が最短の経路のみで構成されるツリー（最短経路センサーツリー）を利用する場合もあり（非特許文献２）、その最短経路センサーツリーの寿命を長くすることが求められる。

T. Winter, et al., "RPL: IPv6 Routing Protocol for Low-power and Lossy Networks", RFC6550, IETF, March 2012. C. Liu and G. Cao, "Distributed Monitoring and Aggregation in Wireless Sensor Networks", IEEE Infocom, 2010.

しかしながら、非特許文献１のRPLに代表される既存のツリー経路選択方法では、ツリーに所属しない各浮遊センサーが自律的に当該浮遊センサーの複数の隣接センサーがツリーに所属しているか（ツリーセンサーノードであるか）を判断して、もしツリーセンサーノードである場合は、当該ツリーセンサーノードの直下に当該浮遊センサーを接続するという動作を実行するため、計算量が大きくなるという課題がある。この課題を図１に示す例を用いて説明する。

図１に示す例では、ツリーを構成するセンサーがルートセンサーノードRのみであり、他のセンサーはツリーに所属しない浮遊センサーであるとする。また、図中の点線はセンサー間の隣接関係を示し、レベルは各センサーのRからの最短ホップ数を示している。各センサーには、L1-1、L1-2、L2-1、...．のように、レベルと、レベル内でのセンサー識別番号からなる符号が付されている。例えば、L1-1は、レベル１のセンサー１を示す。また、識別番号を特定せずに*で表わすことにより、あるレベル内のセンサー全般を表す場合（例：L2-*、L3-*）もある。

図１に示す例において、各センサーは自身がRを隣接センサーに持つかを、自身の隣接センサーを全て調べて確認しなければならない。結果として、L1-1、L1-2のみがRと隣接しているので、まず、L1-1とL1-2がツリーセンサーノードとしてツリー上のR直下に配置される。次にL2（レベル２）のツリーセンサーノードを決定する際にも、再度L2-*、L3-*の浮遊センサーは自身の全ての隣接センサーを確認しなければならない。そのため、最大レベルがhとして、WSNの隣接センサー数（リンク数）がl（注：アルファベットのエル）の場合はO(hl)の計算量が必要となることになる。これは、lある隣接関係について最大h回の調査が必要であるからである。

上記のO(hl)で使用しているO記法（O-notation）は、アルゴリズムの計算量を表す方法の一つであり、問題のサイズを大きくしていったときの漸近的計算量を示すものである。Oはオーダーと呼ばれる。O記法は、計算量の上限を表す場合に有効である。以下にO(g(n))の定義を示す。

まず、

とする。

このとき、次のようにfの集合がOを用いて定義される。

例１、例２を以下に示す。

上記の定義、及び例で示すように、f(n)∈O(g(n))とは、ある定数c、n₀が存在し、nがn₀より大きいときには必ず0≦f(n)≦c・g(n)となることを意味する。

従来技術における第２の課題は、作成した最短経路センサーツリーが、必ずしもエネルギー使用量とツリー寿命の観点から見て効率的とは言えないことである。この課題を図２を参照して説明する。

図２の例では、データ集約率qをq=4としている。データ集約率とは図２に示すようなデータ収集ツリーでリーフセンサーノードL3-*からルートセンサーノードRまでセンサーデータを収集する場合に一つのパケットに集約できるセンサーデータ数を示す。例えば、図２（ａ）に示すL1-1からRへのパケットには、L3-1、L3-2、L2-1、L1-1の４つのセンサーデータが集約されている。また、図２の例において、ツリーセンサーノード間のリンクの横に示される数は１データ収集サイクルで必要になる送信パケット数を示す。

図１を参照して説明した方法で最短経路センサーツリーを作成した場合、図２（ａ）に示すようにサブツリー間でツリーセンサーノード数がバランスよく配置される場合もあるが、図２（ｂ）に示すようにサブツリー間でツリーセンサーノードが偏って配置される場合もある。図２（ｂ）の場合は、L2-2からL1-2、L1-2からRの各区間で必要となるパケット送信数がそれぞれ２となり、パケット送信数の合計が図２（ａ）の場合に比べて２大きくなってしまう。また、図２（ｂ）の場合、L2-2は４つのツリーセンサーノードが直下に配置されているので、パケット受信数が４になり、パケット受信に必要となるエネルギーが大きくなり、L2-2に割り当てられたエネルギーを他と比較して早く消費してしまう問題点もある。

本発明は上記の点に鑑みてなされたものであり、センサーノードからなるセンサーツリーを作成する際に、ツリー経路の決定を効率的に行うことを可能とする技術を提供することを目的とする。

本発明の実施の形態によれば、センサーツリーにおけるルートセンサーノードと、当該センサーツリーに接続していない浮遊センサーとを有するシステムにおいて、当該浮遊センサーと当該浮遊センサーに隣接する親ツリーセンサーノードとの間の接続関係を決定するツリー経路決定装置であって、
前記ルートセンサーノードからのホップ数として定義されるレベル毎に浮遊センサーの情報を取得するセンサー情報取得手段と、
前記浮遊センサーの情報の取得を行うレベルにおける新たなツリーセンサーノードとして、当該浮遊センサーを１つレベルの小さい親ツリーセンサーノード直下に接続させる経路決定手段と
を備えることを特徴とするツリー経路決定装置が提供される。

本発明の実施の形態によれば、センサーツリーにおけるルートセンサーノードと、当該センサーツリーに接続していない浮遊センサーとを有するシステムにおいて、当該浮遊センサーと当該浮遊センサーに隣接する親ツリーセンサーノードとの間の接続関係を決定するツリー経路決定装置が実行するツリー経路決定方法であって、
前記ルートセンサーノードからのホップ数として定義されるレベル毎に浮遊センサーの情報を取得するセンサー情報取得ステップと、
前記浮遊センサーの情報の取得を行うレベルにおける新たなツリーセンサーノードとして、当該浮遊センサーを１つレベルの小さい親ツリーセンサーノード直下に接続させる経路決定ステップと
を備えることを特徴とするツリー経路決定方法が提供される。

本発明の実施の形態によれば、センサーノードからなるセンサーツリーを作成する際に、ツリー経路の決定を効率的に行うことを可能とする技術が提供される。

従来技術を説明するための図である。 従来技術を説明するための図である。 本発明の実施の形態に係るシステム構成を示す図である。 ルートセンサーノードＲの構成図である。 バランス機能を説明するための図である。 バランス機能が適さない場合の例を示す図である。 浮遊センサーを優先的に親に接続させる処理を説明するための図である。 効果を説明するための図である。

以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。

（システム構成）
本実施の形態では、ワイヤレスセンサーネットワーク(WSN)上でルートセンサーノードRを頂点とする複数センサーからなるデータ収集ツリーを作成する。図３は、本実施の形態に係るシステム構成を示す図である。図３に示す状態は、図１の場合と同様であり、ツリーを構成するセンサーがルートセンサーノードRのみであり、他のセンサーはツリーに所属しない浮遊センサーである。既に説明したように、図中の点線はセンサー間の隣接関係を示し、レベルは各センサーのRからの最短ホップ数を示している。各センサーには、L1-1、L1-2、L2-1、...．のように、レベルと、レベル内でのセンサー識別番号からなる符号が付されている。図３において、センサー間を結ぶ矢印付きの線は動作を説明するための線であり、これについては後述する。

各センサーは、無線通信機能、センサーデータ収集機能、パケット送受信機能等を含む装置である。また、各センサーは、隣接センサー取得要求に基づいて、自身に隣接する隣接センサーを検出し、当該隣接センサーの識別情報を要求元に通知する機能を含む。

なお、本実施の形態において、あるセンサーＡが他のセンサーＢから受信する信号の受信電力が所定の閾値以上である場合に、センサーＡはセンサーＢをセンサーＡの隣接センサーであると認識する。

ルートセンサーノードRは、最短経路のパスで構成される最短経路センサーツリーのツリー経路を決定する装置（ツリー経路決定装置）である。ルートセンサーノードRは、当該ルートセンサーノードRからのホップ数として定義されるレベル毎に浮遊センサーを取得し、当該浮遊センサーを当該レベルの新たなツリーセンサーノードとして１つレベルの小さい親ツリーセンサーノード直下に接続することによりツリー経路を決定する機能を有する。また、ルートセンサーノードRは、新たなレベルの浮遊センサーを取得する際には、当該レベルより１つ小さいレベルで既にツリーセンサーノードとなっているセンサーの隣接センサーを取得し、当該隣接センサーが当該レベル以下のレベルのツリーセンサーノードでない場合は、当該隣接センサーを、当該隣接センサーと隣接関係にある１つ小さいレベルのセンサーを親ツリーセンサーノードとしてその直下に接続する。ルートセンサーノードRの具体的な構成例を次に説明する。

図４は、ルートセンサーノードRの構成例を示す図である。図４に示すように、ルートセンサーノードRは、ルーティングモジュールRMを備える。ルーティングモジュールRMは、隣接センサー情報取得部１、ルーティング要求部２、レベル毎ルート決定部３、ツリー経路最終決定部４、隣接センサーリスト格納部５、及びツリーノード格納部６を有する。また、レベル毎ルート決定部３は、共通祖先センサーノード探索部３１、親間移動判断部３２を有する。各機能部の機能概要は以下のとおりである。

隣接センサー情報取得部１は、ルートセンサーノードR自身に隣接する隣接センサーを取得するとともに、ツリーを構成するツリーセンサーノードに対して隣接センサー取得要求を送信することにより、当該ツリーセンサーノードから、当該ツリーセンサーノードに隣接する隣接センサーを取得する。なお、本実施の形態において、「隣接センサーを取得する」とは、隣接センサーを示す情報（識別情報等）を取得することである。便宜上、「隣接センサーを取得する」という表現を用いている。

ルーティング要求部２は、最終的に決定されたツリー経路に従ってパケットの転送を行うよう、各ツリーセンサーノードに対してルーティングの設定を行う。

レベル毎ルート決定部３は、レベル毎に、当該レベルの新たなツリーセンサーノードを１つレベルの小さい親ツリーセンサーノード直下に接続する等の処理を行う。レベル毎ルート決定部３に含まれる共通祖先センサーノード探索部３１と親間移動判断部３２は後述するバランス機能に係る処理を実行する。ツリー経路最終決定部４は、全てのレベルの浮遊センサーがツリーセンサーノードとして決定されたことを検知した場合に、ルーティング要求部２に対してルーティング要求を行う。

隣接センサーリスト格納部５は、ツリーセンサーノードとして決定されたノード毎に、当該ノードに隣接する隣接センサーのリストを格納する。本実施の形態では、小さいレベルから順にレベル毎にツリーセンサーノードが決定されることから、隣接センサーリスト格納部５には、小さいレベルから順に、当該レベルのツリーセンサーノードに隣接する隣接センサーが格納され、当該隣接センサーがツリーセンサーノードとして決定された場合には、当該隣接センサーは隣接センサーリスト格納部５から削除される。図４には、例として、レベル２のツリーセンサーノードに隣接する隣接センサー（の識別情報）が格納されている状態が示されている。

ツリーノード格納部６には、決定されたツリーの情報（センサーノード、接続関係等）が格納される。

本実施の形態に係るルートセンサーノードRは、例えば、無線通信機能を備えるコンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、ルートセンサーノードRが有する機能は、当該コンピュータに内蔵されるＣＰＵやメモリなどのハードウェア資源を用いて、ルートセンサーノードRで実施される処理に対応するプログラムを実行することによって実現することが可能である。上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。

なお、本実施の形態では、ツリー経路決定装置がルートセンサーノードRであるとしているが、これは必須ではなく、ツリー経路決定装置の機能をルートセンサーノードR以外のセンサーノードに持たせてもよいし、ツリー経路決定装置を、センサーノードとは別の装置としてツリーの外部に設けてもよい。

（ルートセンサーノードRの動作）
以下、上記の構成を備えるルートセンサーノードRにおけるツリー経路の決定処理について説明する。以下では、説明の便宜上、ルートセンサーノードRをRと表記する。

＜基本的な処理＞
既に説明したように、図３に示す構成において、最初はRだけがツリーセンサーノードである。次に、Rの隣接センサー情報取得部１は、R自身の隣接センサーであるL1-1、L1-2を取得し、取得結果（L1-1、L1-2）を隣接センサーリスト格納部５に格納する。

R内のレベル毎ルート決定部３は、L1-1、L1-2をデータ収集ツリー上でRの直下に確定ツリーセンサーノードとして配置し、ツリーノード格納部６に格納する。

新たなレベル１(L1)のツリーセンサーノードが決定したので、R内のレベル毎ルート決定部３はL1-1、L1-2の隣接センサー取得要求を、隣接センサー情報取得部１に指示し、隣接センサー情報取得部１は、隣接センサー取得要求をL1-1、L1-2に送信する。

隣接センサー取得要求を受信した隣接センサーL1-1、L1-2はそれぞれ、各自の親（この場合はR）を除いた隣接センサーをRに通知する。つまり、L1-1はL1-2、L2-1を通知し、L1-2はL1-1、L2-2を通知する。これらの通知は、図３においてＡで示される。

なお、本実施の形態において、隣接センサー取得要求をRからツリーセンサーノードに送信する場合の信号経路、及びツリーセンサーノードから隣接センサーの情報をRに通知する場合の信号経路には特に限定はなく、どのような経路で信号が伝送されてもよい。

L1-1の隣接センサーのリストL1-2、L2-1と、L1-2の隣接センサーのリストL1-1、L2-2は隣接センサーリスト格納部５に格納されるとともに、Rの隣接センサーのリストL1-2、L1-1は隣接センサーリスト格納部５から削除される。その理由は、これらのセンサーは既にレベル１(L1)のツリーセンサーノードとしてツリーに接続されているからであり、L2のツリーセンサーノードを決める際には不要であるからである。

次に、レベル毎ルート決定部３は、隣接センサーリスト格納部５に格納されているL1-1、 L1-2の隣接センサーをL2のツリーセンサーノードとして接続する。この際、L1-1にはL2-1のみが、L1-2にはL2-2のみがL2の隣接センサーとして存在するので、L2-1はL1-1の直下に、L2-2はL1-2の直下に接続され、この接続の情報がツリーノード格納部６に格納される。図４の例では、ツリーノード格納部６の中に、このときの格納情報が示されている。

ここで、新たなレベル２(L2)のツリーセンサーノードが決定したので、R内のレベル毎ルート決定部３はL2-1、L2-2に対する隣接センサー取得要求送信を、隣接センサー情報取得部１に指示し、隣接センサー情報取得部１は、L2-1、L2-2のそれぞれに隣接センサー取得要求を送信する。

隣接センサー取得要求を受信したL2-1、L2-2はRからの要求を受けてそれぞれの隣接センサーをRに通知する。L2-1からは隣接センサーとしてL3-1〜L3-3が通知され、L2-2からは隣接センサーとしてL3-1〜L3-4が通知される。これらの通知は図３においてＢで示されている。

L2-1、L2-2のそれぞれから取得された隣接センサーは隣接センサーリスト格納部５に格納される。隣接センサーリスト格納部５で、今まで格納されていたL1-1、L1-2の隣接センサーリストはこの時点でL2-1、L2-2の隣接センサーリストに置き換えられる。その理由は既にL2のセンサーは全て、ツリーセンサーノードとして、ツリーノード格納部６に格納されているからである。図４の例では、隣接センサーリスト格納部５の中に、このときの格納情報が示されている。

隣接センサーリスト格納部５は、L2-1、L2-2の隣接センサーを順にレベル毎ルート決定部３に渡す。もしくは、レベル毎ルート決定部３がL2-1、L2-2の隣接センサーを順に隣接センサーリスト格納部５から読み出すこととしてもよい。なお、L2-1、L2-2の隣接センサーを順に隣接センサーリスト格納部５から読み出すとは、ツリーセンサーノードの識別番号の順に読み出すことであり、具体的には、まず、L2-1の隣接センサー（L3-1〜L3-3）を読み出し、次に、L2-2の隣接センサー（L3-1〜L3-4）を読み出すことである。

ここで、L2-1の隣接センサーはL3-1〜L3-3であり、これらのセンサーはまだツリーに参加していないので、レベル毎ルート決定部３は、L3-1〜L3-3を無条件でL2-1配下のツリーセンサーノードに決定し、ツリーノード格納部６に格納する。

次にL2-2の隣接センサーL3-1〜L3-4がレベル毎ルート決定部３に渡されると、レベル毎ルート決定部３は、まず、L2-2直下のツリーセンサーノードとしてL3-1を選択するが、L3-1は既にL2-1の直下のツリーセンサーノードとして選択されている。本実施の形態では、あるレベルのセンサーノードは、１つ小さいレベルのセンサーノードのうち１つのセンサーノードのみに接続することを許容する。従って、上記のような状況になる場合、本実施の形態では、バランス機能により適切にセンサーノードの選択の修正を行うこととしている。

＜バランス機能＞
バランス機能とは次のような機能である。すなわち、１つ小さいレベルのツリーセンサーノード（新親ツリーセンサーノード）（本例では、L2-2）の隣接センサーとして選択されたセンサーが既にツリーセンサーノード（本例では、L3-1）になっていて、他の親ツリーセンサーノード（既存親ツリーセンサーノード）（本例ではL2-1）の直下に配置されている場合は、当該既存親ツリーセンサーノード（L2-1）と、新親ツリーセンサーノード（L2-2）の共通の祖先となる共通祖先センサーノード（本例では、R）を検索し、共通祖先センサーノードの配下で当該既存親ツリーセンサーノード（L2-1）が所属するサブツリーのツリーセンサーノード数と、新親ツリーセンサーノード（L2-2）が所属するサブツリーのツリーセンサーノード数を比較し、もしも当該センサー（L3-1）が既存親ツリーセンサーノード直下から新親ツリーセンサーノード直下に移動した場合に、当該２つのサブツリー間のツリーセンサーノード数差が小さくなる場合には、当該センサーを既存親ツリーセンサーノード直下から新親ツリーセンサーノード直下に移動させる、というものである。

より具体的には、バランス機能に係る処理は共通祖先センサーノード探索部３１と親間移動判断部３２が実行する。まず、共通祖先センサーノード探索部３１は、上述した既存親ツリーセンサーノードL2-1と新親ツリーセンサーノードL2-2との間で共通祖先ツリーセンサーノードを見つける。この例では共通祖先ツリーセンサーノードはRであり、その配下のサブツリーのツリーセンサーノード数の算出、比較を行う。この処理はR内の親間移動判断部３２が実行する。

親間移動判断部３２は、L1-1配下のサブツリーのツリーセンサーノード数を５と算出し（L1-1、L2-1、L3-1、L3-2、L3-3の５つ）、L1-2配下のサブツリーのツリーセンサーノード数を２と算出し（L1-2とL2-2の２つ）、差を３と算出する。そして、親間移動判断部３２は、L3-1をサブツリー間で移動させることによってノード数の差が３から１に減少することを確認し、当該移動を行う。移動後の状態から、L3-2、L3-3を更に移動してもサブツリー間のノード数差は１のままなので、L3-2、L3-3は移動されない。L3-4は、L2-2にしか隣接していないので、L2-2直下に配置される。この処理を行った結果（ツリーノード格納部６に格納される内容）を図５に示す。図５に示すように、結果として各サブツリーのノード数は４となりバランスが保たれる。

＜ルーティング要求＞
このように全てのレベルの浮遊センサーがツリーセンサーノードとして決定されたことをR内のツリー経路最終決定部４が認識した場合、ツリー経路最終決定部４はルーティング要求部２にルーティング要求を行う。なお、このルーティング要求は各レベルのツリーノードが確定した都度行うことも可能である。ルーティング要求部２は、ツリーノード格納部６に格納されているツリーの情報に基づいて、決定した通りのルーティングを行う。ここでのルーティングとは、ツリーを構成する各センサーノードに対して、ツリーの経路のとおりに、センサーデータを格納するパケットの転送を行うように設定を行うことである。

＜浮遊センサーを優先的に親に接続させる処理＞
上述したように、図５の左側に示すセンサーの隣接関係の場合、バランス機能が適切に機能する。しかし、図６の左側に示すようなセンサーの隣接関係の場合、以下に説明するように、バランス機能がうまく働かない。

図５と図６では、隣接関係が一区間だけ異なる。すなわち、図５ではL2-1が隣接センサーとしてL3-3を持つが、図６ではL2-1が隣接センサーとしてL3-3を持たない。図６の場合、レベル３でのツリーセンサーノードの決定の際に、まず、L2-1の直下の子ツリーセンサーノードとしてL3-1、L3-2のみが決定され、次に、L2-2の隣接センサーであるL3-1の帰属先を決める際、親間移動判断部３２はL1-1の配下のサブツリーのノード数が４でL1-2配下のサブツリーのノード数が２であり、L3-1をL2-1からL2-2へ移動することでノード数差を０にできるので、この移動を行う判断をする。その後にL3-2を移動するとノード数差が広がるため移動しない。L3-3、L3-4は浮遊センサーで親がL2-2のみなので、L2-2直下にツリーセンサーノードとして接続することになる。結果として図６の右側に示すようにL1-2配下サブツリーのノード数が５となり、L1-1配下サブツリーのノード数３に比較して大きくアンバランスになってしまう。

そこで、上記のようにアンバランスになってしまうことを解消するために、レベル毎ルート決定部３は、新親ツリーセンサーノード配下に複数の隣接センサーが存在する場合は、その複数の隣接センサーの中で浮遊センサーが存在するか判断し、浮遊センサーが存在する場合は、当該浮遊センサーを新親ツリーセンサーノード直下に最初に接続し、その後に既に既存親ツリーセンサーノードを親に持つ隣接センサーを新親ツリーセンサーノード直下に移動するかどうかの判断をすることとしている。

つまり、レベルが１小さい親ツリーセンサーノードの隣接センサーが複数ある場合は、まだ親が決まっていない浮遊センサーノードから先に当該親直下に接続することにより、新親ツリーセンサーノードが所属するサブツリーのノード数を正確に移動時に反映することを可能としている。具体的には以下のとおりである。

図７の左側（図６の左側と同じ）の隣接関係において、レベル３のツリーセンサーノードを決定する際に、まず、レベル毎ルート決定部３は、L3-1、L3-2を無条件でL2-1配下のツリーセンサーノードとしして選択する。次に、レベル毎ルート決定部３は、L2-2直下のツリーセンサーノードの選択を行う。ここでは、まだ親が決まっていない浮遊センサーであるL3-3、L3-4から先に当該親（L2-2）直下にツリーセンサーノードとして接続する。この後に、前述したバランス機能により、既存親ツリーセンサーノード（L2-1）を親に持つ隣接センサー(L3-1、L3-2)を新親ツリーセンサーノード（L2-2）直下に移動するかどうかの判断をする。

図７では、上記のようにL2-2直下にL3-3、L3-4が最初に接続されるので、新親ツリーセンサーノードL2-2が所属するサブツリーのノード数が４となり、既存ツリーセンサーノードL2-1が所属するサブツリーのノード数も４であるため、親間移動判断部３２は、L3-1、L3-2をL2-1直下からL2-2直下に移動する必要がないと判断する。そのため、サブツリー間でのノード数バランスが保たれる。

なお、レベルが１小さい親ツリーセンサーノードの隣接センサーが複数ある場合に、まだ親が決まっていない浮遊センサーノードから先に当該親直下に接続する処理について、図７の隣接関係の例で説明したが、この処理は図５の隣接関係に適用してもよい。

（本実施の形態の効果について）
Rが実行する基本的な処理により、データ収集ツリーとして最短経路センサーツリーを作成することができる。そして、その計算量はO(l)(注：O ()の括弧の中の文字はアルファベットのエルである)になる。この理由は各レベルの浮遊センサーを取得することは、そのレベルより１小さいレベルのツリーセンサーノードに隣接する隣接センサーを取得することにより可能になるからである。本実施の形態では、同一ツリーセンサーノードは一度だけ、隣接センサーを取得すればよいので、従来手法のように異なるレベルの数だけ隣接センサーを取得する必要がない。故に計算量は隣接センサー数の合計であるlのオーダとなる。この計算量は従来方式のO(hl)に比較して計算量が小さくなっていることがわかる。

また、バランス機能により、データ収集ツリーにおけるサブツリー間で、構成するツリーセンサーノード数に差が開くこと（例：図２（ｂ））を避けることができ、そのため、従来方式に比較して、１サブツリー内の送信パケット数の削減、少数ツリーセンサーノードへの受信パケットの集中を避けることができ、データ収集ツリー寿命を延ばすことが可能になる。

バランス機能を使った場合と使わなかった場合のデータ収集ツリー寿命の比較結果を図８に示す。図８に示す例における評価条件として、コンピュータシミュレーション環境で50×50の各座標(x、y)にセンサーを70%の確率で存在させ、結果として1758のセンサーを配置した。そのセンサー間に方向性リンクをランダムに45698本作成し、センサー間の隣接関係を作成した。その後に、対象平面の中央に近い座標(26, 26)にルートセンサーノードを設定し、前述した基本的処理に従ってデータ収集ツリーを作成した。図８において "balanced"はバランス機能を用いてツリーを作成したものであり、"random"は、バランス機能を用いずに、既存親ツリーセンサーノードと新親ツリーセンサーノードが同一の子ツリーセンサーを持った場合はランダムにどちらかを選択することとしてツリーを作成したものである。

なお、この評価結果は各ツリーセンサーノードが1Jのエネルギーまで使えるとして、データ収集サイクルを繰り返す中でいずれか一つのツリーセンサーノードが1Jを使いきった時点がツリーの寿命であるとして、データ収集サイクルを止めて、そのサイクル数を評価している。なお、データ集約率(q)は1〜17の間で変化させ、1のときには複数のセンサーデータを１パケットに格納することはできず、各ツリーノードセンサーが作成するセンサーデータ毎にパケットを作成してRまで転送していく。図８（ａ）は、データ集約率をx軸に、収集サイクル数をy軸にとって"balanced"と"random"を比較した図である。図８（ｂ）は"random"=1としたときの"balanced"の収集サイクル数を正規化した値を示す。

図８（ａ）に示すように、データ集約率が上がると収集サイクル数は増えるが、全ての集約率でbalancedがrandomに比較して収集サイクル数が多いことがわかる。また図８（ｂ）に示すように、balancedはデータ集約率が低いほどデータ収集ツリー寿命増加効果が高いことがわかる。その理由はデータ集約率が低いと、あるサブツリー内のツリーセンサーノード数が多い場合は、そのサブツリー内でのパケット送受信数がより大きくなってしまい、収集サイクル数に与える影響が大きいためであると考えられる。

また、浮遊センサーを優先的に親に接続させる処理を用いて、まず新親ツリーセンサーノードの子としてこの時点で確定している浮遊センサーを新親ツリーセンサーノードの直下に最初に接続することにより、新親ツリーセンサーノード直下に位置するツリーセンサーノード数を最新状態にした上で、既存親ツリーセンサーノードを親に持つセンサーを新親ツリーセンサーノード配下に移動するかどうかを判断することができる。

本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。

１ 隣接センサー情報取得部
２ ルーティング要求部
３ レベル毎ルート決定部
４ ツリー経路最終決定部
５ 隣接センサーリスト格納部
６ ツリーノード格納部
３ レベル毎ルート決定部
３１ 共通祖先センサーノード探索部
３２ 親間移動判断部

Claims (8)

1. センサーツリーにおけるルートセンサーノードと、当該センサーツリーに接続していない浮遊センサーとを有するシステムにおいて、当該浮遊センサーと当該浮遊センサーに隣接する親ツリーセンサーノードとの間の接続関係を決定するツリー経路決定装置であって、
   前記ルートセンサーノードからのホップ数として定義されるレベル毎に浮遊センサーの情報を取得するセンサー情報取得手段と、
   前記浮遊センサーの情報の取得を行うレベルにおける新たなツリーセンサーノードとして、当該浮遊センサーを１つレベルの小さい親ツリーセンサーノード直下に接続させる経路決定手段と
   を備えることを特徴とするツリー経路決定装置。
2. 前記センサー情報取得手段は、新たなレベルの浮遊センサーの情報を取得する際には、当該レベルより１つ小さいレベルで既にツリーセンサーノードとなっているセンサーに隣接する隣接センサーの情報を取得し、
   前記経路決定手段は、当該隣接センサーがツリーセンサーノードでない場合は、当該隣接センサーと隣接関係にある１つ小さいレベルのセンサーを親ツリーセンサーノードとして当該隣接センサーをその直下に接続する
   ことを特徴とする請求項１に記載のツリー経路決定装置。
3. １つ小さいレベルのツリーセンサーノードである新親ツリーセンサーノードの隣接センサーとして選択されたセンサーが既にツリーセンサーノードになっており、他の親ツリーセンサーノードである既存親ツリーセンサーノードの直下に配置されている場合において、
   前記経路決定手段は、前記既存親ツリーセンサーノードと、前記新親ツリーセンサーノードの共通の祖先となる共通祖先センサーノードを探索し、当該共通祖先センサーノードの配下で前記既存親ツリーセンサーノードが所属するサブツリーのツリーセンサーノード数と、前記新親ツリーセンサーノードが所属するサブツリーのツリーセンサーノード数とを比較し、仮に当該センサーが前記既存親ツリーセンサーノード直下から前記新親ツリーセンサーノード直下に移動したとした場合に、当該２つのサブツリー間のツリーセンサーノード数差が小さくなる場合には、当該センサーを前記既存親ツリーセンサーノード直下から前記新親ツリーセンサーノード直下に移動させる
   ことを特徴とする請求項２に記載のツリー経路決定装置。
4. 前記新親ツリーセンサーノード配下に複数の隣接センサーが存在する場合において、
   前記経路決定手段は、前記複数の隣接センサーの中で浮遊センサーが存在するか否かを判断し、浮遊センサーが存在する場合に、当該浮遊センサーを前記新親ツリーセンサーノード直下に最初に接続し、その後に既に前記既存親ツリーセンサーノードを親に持つ隣接センサーを前記新親ツリーセンサーノード直下に移動するか否かを判断する
   ことを特徴とする請求項３に記載のツリー経路決定装置。
5. センサーツリーにおけるルートセンサーノードと、当該センサーツリーに接続していない浮遊センサーとを有するシステムにおいて、当該浮遊センサーと当該浮遊センサーに隣接する親ツリーセンサーノードとの間の接続関係を決定するツリー経路決定装置が実行するツリー経路決定方法であって、
   前記ルートセンサーノードからのホップ数として定義されるレベル毎に浮遊センサーの情報を取得するセンサー情報取得ステップと、
   前記浮遊センサーの情報の取得を行うレベルにおける新たなツリーセンサーノードとして、当該浮遊センサーを１つレベルの小さい親ツリーセンサーノード直下に接続させる経路決定ステップと
   を備えることを特徴とするツリー経路決定方法。
6. 前記センサー情報取得ステップにおいて、前記ツリー経路決定装置は、新たなレベルの浮遊センサーの情報を取得する際には、当該レベルより１つ小さいレベルで既にツリーセンサーノードとなっているセンサーに隣接する隣接センサーの情報を取得し、
   前記経路決定ステップにおいて、前記ツリー経路決定装置は、当該隣接センサーがツリーセンサーノードでない場合は、当該隣接センサーと隣接関係にある１つ小さいレベルのセンサーを親ツリーセンサーノードとして当該隣接センサーをその直下に接続する
   ことを特徴とする請求項５に記載のツリー経路決定方法。
7. １つ小さいレベルのツリーセンサーノードである新親ツリーセンサーノードの隣接センサーとして選択されたセンサーが既にツリーセンサーノードになっており、他の親ツリーセンサーノードである既存親ツリーセンサーノードの直下に配置されている場合において、
   前記経路決定ステップにおいて、前記ツリー経路決定装置は、前記既存親ツリーセンサーノードと、前記新親ツリーセンサーノードの共通の祖先となる共通祖先センサーノードを探索し、当該共通祖先センサーノードの配下で前記既存親ツリーセンサーノードが所属するサブツリーのツリーセンサーノード数と、前記新親ツリーセンサーノードが所属するサブツリーのツリーセンサーノード数とを比較し、仮に当該センサーが前記既存親ツリーセンサーノード直下から前記新親ツリーセンサーノード直下に移動したとした場合に、当該２つのサブツリー間のツリーセンサーノード数差が小さくなる場合には、当該センサーを前記既存親ツリーセンサーノード直下から前記新親ツリーセンサーノード直下に移動させる
   ことを特徴とする請求項６に記載のツリー経路決定方法。
8. 前記新親ツリーセンサーノード配下に複数の隣接センサーが存在する場合において、
   前記経路決定ステップにおいて、前記ツリー経路決定装置は、前記複数の隣接センサーの中で浮遊センサーが存在するか否かを判断し、浮遊センサーが存在する場合に、当該浮遊センサーを前記新親ツリーセンサーノード直下に最初に接続し、その後に既に前記既存親ツリーセンサーノードを親に持つ隣接センサーを前記新親ツリーセンサーノード直下に移動するか否かを判断する
   ことを特徴とする請求項７に記載のツリー経路決定方法。

Images