(57)【要約】【課題】各ノードからのデータがルートノードに集約されるネットワークの寿命を長期化すること。【解決手段】ルートノードからの最短ホップ数が小さい程上位である複数のレベルごとに１以上のノードを含み、各ノードは、下位のノードからデータを受信すると、当該ノードのデータと共に受信したデータを上位のノードに送信するネットワークの経路を選択する経路選択装置は、上位のレベルから順にノードを探索する探索部と、探索されたノードごとに、当該ノードが隣接する上位のノードのうちのいずれかを接続先として選択する選択部とを有し、選択部は、探索された第１のノードが複数の上位の第２のノードと通信可能な場合には、複数の第２のノードのそれぞれに第１のノードが接続した場合の各経路について、当該経路上の各ノードのエネルギー減少度のうちの最大値を特定し、最大値が最小になる経路における第２のノードを、接続先として選択する。【選択図】図６
2017139635.tif 000002
【特許請求の範囲】
【請求項１】
ルートノードからの最短ホップ数が小さい程上位である複数のレベルごとに１以上のノードを含み、各ノードは、下位のノードからデータを受信すると、当該ノードのデータと共に受信したデータを上位のノードに送信するサイクルを繰り返すネットワークの経路を選択する経路選択装置であって、
上位のレベルから順に、当該レベルに属するノードを探索する探索部と、
前記探索部によって探索されたノードごとに、当該ノードが隣接する上位のノードのうちのいずれかを接続先として選択する選択部とを有し、
前記選択部は、
探索された第１のノードが複数の上位の第２のノードと通信可能な場合には、複数の前記第２のノードのそれぞれに前記第１のノードが接続した場合の各経路について、当該経路上の各ノードのエネルギー減少度のうちの最大値を特定し、前記最大値が最小になる経路における前記第２のノードを、前記第１のノードの接続先として選択し、
前記ノードのエネルギー減少度は、当該ノードの初期エネルギー量に対する、１サイクルにおいて当該ノードがデータの受信に要するエネルギー量と当該ノードが１サイクルにおいてデータの送信に要するエネルギー量との和の割合である、
ことを特徴とする経路選択装置。
【請求項２】
前記選択部は、
前記第１のノードが複数の上位の第２のノードと通信可能な場合には、複数の前記第２のノードのそれぞれに前記第１のノードが接続した場合の各経路について、前記第１のノードが送信するデータの数に基づいて、当該経路上の各ノードの前記エネルギー減少度を更新して、当該経路に係る前記最大値を特定する、
ことを特徴とする請求項１記載の経路選択装置。
【請求項３】
１以上の前記データを格納する１パケットの送信に必要とされるエネルギー量をＥｔｘ、１以上の前記データを格納する１パケットの受信に必要とされるエネルギー量をＥＲｘとした場合、
前記ノードのエネルギー減少度Ｄは、当該ノードの初期エネルギー量をＥｉ、当該ノードの１サイクルの送信パケット数をＴＮ、当該ノードの１サイクルの受信パケット数をＲＮとした場合、
Ｄ＝（ＥＴｘ×ＴＮ＋ＥＲｘ×ＲＮ）／Ｅｉ
であることを特徴とする請求項１又は２記載の経路選択装置。
【請求項４】
前記ノードの前記送信パケット数ＴＮは、当該ノードが１サイクルで受信する全てのパケットに含まれているデータの総数と、１つの送信パケットに格納可能なデータ数とに基づいて算出され、
前記ノードの前記受信パケット数ＲＮは、当該ノードの下位に直接接続するノードの送信パケット数ＴＮの総和である、
ことを特徴とする請求項３記載の経路選択装置。
【請求項５】
ルートノードからの最短ホップ数が小さい程上位である複数のレベルごとに１以上のノードを含み、各ノードは、下位のノードからデータを受信すると、当該ノードのデータと共に受信したデータを上位のノードに送信するサイクルを繰り返すネットワークの経路を選択する経路選択装置が、
上位のレベルから順に、当該レベルに属するノードを探索する探索手順と、
前記探索手順において探索されたノードごとに、当該ノードが隣接する上位のノードのうちのいずれかを接続先として選択する選択手順とを実行し、
前記選択手順は、
探索された第１のノードが複数の上位の第２のノードと通信可能な場合には、複数の前記第２のノードのそれぞれに前記第１のノードが接続した場合の各経路について、当該経路上の各ノードのエネルギー減少度のうちの最大値を特定し、前記最大値が最小になる経路における前記第２のノードを、前記第１のノードの接続先として選択し、
前記ノードのエネルギー減少度は、当該ノードの初期エネルギー量に対する、１サイクルにおいて当該ノードがデータの受信に要するエネルギー量と当該ノードが１サイクルにおいてデータの送信に要するエネルギー量との和の割合である、
ことを特徴とする経路選択方法。
【請求項６】
前記選択手順は、
前記第１のノードが複数の上位の第２のノードと通信可能な場合には、複数の前記第２のノードのそれぞれに前記第１のノードが接続した場合の各経路について、前記第１のノードが送信するデータの数に基づいて、当該経路上の各ノードの前記エネルギー減少度を更新して、当該経路に係る前記最大値を特定する、
ことを特徴とする請求項５記載の経路選択方法。
【請求項７】
１以上の前記データを格納する１パケットの送信に必要とされるエネルギー量をＥｔｘ、１以上の前記データを格納する１パケットの受信に必要とされるエネルギー量をＥＲｘとした場合、
前記ノードのエネルギー減少度Ｄは、当該ノードの初期エネルギー量をＥｉ、当該ノードの１サイクルの送信パケット数をＴＮ、当該ノードの１サイクルの受信パケット数をＲＮとした場合、
Ｄ＝（ＥＴｘ×ＴＮ＋ＥＲｘ×ＲＮ）／Ｅｉ
であることを特徴とする請求項５又は６記載の経路選択方法。
【請求項８】
前記ノードの前記送信パケット数ＴＮは、当該ノードが１サイクルで受信する全てのパケットに含まれているデータの総数と、１つの送信パケットに格納可能なデータ数とに基づいて算出され、
前記ノードの前記受信パケット数ＲＮは、当該ノードの下位に直接接続するノードの送信パケット数ＴＮの総和である、
ことを特徴とする請求項７記載の経路選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路選択装置及び経路選択方法に関する。
【背景技術】
【０００２】
特定の場所／地域にセンサーを配置し、対象地の湿度、温度、気体濃度等をセンサーによって計測し、その計測データをデータ収集ツリーで収集し、ルートセンサーノードからベースステーションに通知することによって対象地の分析を行う、あるいはガスメータ、電気メータなどの情報を定期的にデータ収集ツリーで収集する、ことを可能にする技術として、ＲＰＬ（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.
【非特許文献２】H. Matsuura, "Maximizing Lifetime of Shortest Path Aggregation Tree in Wireless Sensor Networks", 2015年電子情報通信学会ソサイエティ大会, BS-6.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献２では、ワイヤレスセンサーネットワークを構成する各センサーが保持する初期エネルギー量が、最短経路センサーツリーのルートセンサーノード以外は一律であると仮定されている。
【０００７】
しかしながら、ルートセンサーノード以外のツリーセンサーノードも初期に割り当てられるエネルギーに差がある場合が考えられる。また、初期のセンサー配置後、なんらかの理由でツリーの再構成を行う必要がある場合は、各センサーが保持するエネルギー量が異なることが想定される。この点について、図１〜図３を用いて説明する。
【０００８】
図１に示すＷＳＮ（ワイヤレスセンサーネットワーク）において、ツリーを構成するセンサーがルートセンサーノードＲのみであり、他のセンサーは、ツリーに所属しない浮遊センサーである。また、図中の点線はセンサー間の隣接関係を示し、レベルは各センサーのＲからの最短ホップ数を示す。各センサーには、Ｌ１−１、Ｌ１−２、Ｌ２−１、...．のように、レベルと、レベル内でのセンサー識別番号とからなる符号が付されている。例えば、Ｌ１−１は、レベル１のセンサー１を示す。また、識別番号を特定せずに＊で表わすことにより、あるレベル内のセンサー全般を表す場合（例：Ｌ２−＊、Ｌ３−＊）もある。各センサー内の数字は、センサーが保持するエネルギー量を示す。図１の例では、Ｒ以外の全てのセンサーが１００のエネルギー量を持つ。
【０００９】
図２は、従来方式による最短経路センサーツリーの寿命の増加手法を示す図である。図２の例では、データ集約率ｑをｑ＝４としている。データ集約率とは、図２に示されるようなデータ収集ツリーにおいて、リーフセンサーノードＬ３−＊からルートセンサーノードＲまでセンサーデータを収集する場合に、一つのパケットに集約できるセンサーデータ数をいう。
【００１０】
例えば、図２（ｂ）に示すＬ１−１からＲへのパケットには、Ｌ３−１、Ｌ３−２、Ｌ２−１、Ｌ１−１の４つのセンサーデータが集約されている。また、図２の例において、ツリーセンサーノード間のリンクの横に示される数は、１データ集約サイクルで必要になる送信パケット数を示す。各センサーでは１パケットを送受信する度毎にエネルギーを消費するため、多くのパケットの送受信が必要となるツリーセンサーノードは、エネルギーの枯渇が早くなる。
【００１１】
図２（ａ）及び（ｂ）は、いずれも最短経路センサーツリーであるが、（ａ）は、Ｌ２−２に負荷が集中するため、Ｌ２−２のエネルギーが無くなった時点でツリー寿命が尽きることになる。一方、（ｂ）では、Ｌ１−１、Ｌ１−２配下のそれぞれのサブネットワークでツリーセンサーノードが均等にバランスよく配置されているため、ツリー寿命が大幅に長くなる。
【００１２】
具体的に１パケット送信のエネルギー量が２、受信のエネルギー量を１とした場合、（ａ）の場合、Ｌ２−２は、１データ集約サイクル毎に２×２＋１×４＝８のエネルギーが必要となる。したがって、最初の１００のエネルギー量の保持時から数えて１３回目のデータ集約サイクル中に、最短経路センサーツリーの寿命が尽きる。一方、（ｂ）の場合は、最もエネルギー消費が大きくなるＬ２−＊のセンサーノードの１データ集約サイクル毎のエネルギー消費量は、２＋１×２＝４となるので、２５回目のデータ集約サイクルまで最短経路センサーツリー寿命が尽きることがない。
【００１３】
このように、従来方式は、各レベルのサブセンサーツリー毎に同じレベルのサブセンサーツリー間の所属センサーノード数を均等にするので、図２のようにＲ以外の全てのセンサーが同じ初期エネルギー量を保持する場合にはセンサーツリー寿命増大に効果が高い。
【００１４】
しかしながら、図３のように、初期エネルギー量が異なる場合は、従来方式では問題が生じる。図２からの違いは、Ｌ１−２、Ｌ２−１、Ｌ２−２の初期エネルギー量が、１００から１５０、５０、２００にそれぞれ変わっていることである。
【００１５】
（ａ）の場合、Ｌ１−２、Ｌ２−１、Ｌ２−２が、それぞれ１回のデータ集約サイクルで、６、２、８のエネルギー量を消費するので、２５回目のデータ集約サイクルまで、ツリー上でセンサーエネルギーの枯渇は起きない。一方、従来方式を適用してサブツリー間のバランスを取った（ｂ）の場合は、Ｌ２−１における１回のデータ集約サイクルで４のエネルギー量を消費するので、１３回目のデータ集約サイクルでＬ２−１のエネルギーの枯渇が起きることになる。
【００１６】
このように、従来方式を適用することにより大幅にツリー寿命が短くなってしまうのである。
【００１７】
本発明は、上記の点に鑑みてなされたものであって、各ノードからのデータがルートノードに集約されるネットワークの寿命を長期化することを目的とする。
【課題を解決するための手段】
【００１８】
そこで上記課題を解決するため、ルートノードからの最短ホップ数が小さい程上位である複数のレベルごとに１以上のノードを含み、各ノードは、下位のノードからデータを受信すると、当該ノードのデータと共に受信したデータを上位のノードに送信するサイクルを繰り返すネットワークの経路を選択する経路選択装置は、上位のレベルから順に、当該レベルに属するノードを探索する探索部と、前記探索部によって探索されたノードごとに、当該ノードが隣接する上位のノードのうちのいずれかを接続先として選択する選択部とを有し、前記選択部は、探索された第１のノードが複数の上位の第２のノードと通信可能な場合には、複数の前記第２のノードのそれぞれに前記第１のノードが接続した場合の各経路について、当該経路上の各ノードのエネルギー減少度のうちの最大値を特定し、前記最大値が最小になる経路における前記第２のノードを、前記第１のノードの接続先として選択し、前記ノードのエネルギー減少度は、当該ノードの初期エネルギー量に対する、１サイクルにおいて当該ノードがデータの受信に要するエネルギー量と当該ノードが１サイクルにおいてデータの送信に要するエネルギー量との和の割合である。
【発明の効果】
【００１９】
各ノードからのデータがルートノードに集約されるネットワークの寿命を長期化することができる。
【図面の簡単な説明】
【００２０】
【図１】ワイヤレスセンサーネットワークの一例を示す図である。
【図２】従来方式による最短経路センサーツリーの寿命の増加手法を示す図である。
【図３】従来方式の問題点を説明するための図である。
【図４】本発明の実施の形態におけるワイヤレスセンサーネットワークの構成例を示す図である。
【図５】本発明の実施の形態における経路選択装置のハードウェア構成例を示す図である。
【図６】本発明の実施の形態における経路選択装置の機能構成例を示す図である。
【図７】隣接浮遊センサーの取得例を示す図である。
【図８】隣接センサーリスト記憶部の記憶内容の一例を示す図である。
【図９】ツリーノード記憶部の記憶内容の一例を示す図である。
【図１０】エネルギー減少度Ｄの更新例を示す図である。
【図１１】本実施の形態におけるツリー経路選択手順の具体例を示す図である。
【図１２】本実施の形態におけるツリー経路選択手順の具体例を示す図である。
【発明を実施するための形態】
【００２１】
以下、図面に基づいて本発明の実施の形態を説明する。図４は、本発明の実施の形態におけるワイヤレスセンサーネットワークの構成例を示す図である。図４におけるＷＳＮは、ルートセンサーノードＲをルートとし、レベルＬ１〜Ｌ３のそれぞれのレベルにおいて１以上のセンサーを含む。
【００２２】
図中の点線はセンサー間の隣接関係を示し、レベルは各センサーのＲからの最短ホップ数によって定義される。隣接関係とは、通信（接続）が可能な関係をいい、例えば、一方が、他方からの電波信号（例えば、ＲＳＳＩ（Received Signal Strength Indicator））の到達範囲内に有る関係をいう。また、各センサーの識別番号は、当該センサーが属するレベルと、当該レベル内でのセンサー識別番号とを「−」で接続したものである。また、識別番号を特定せずに＊で表わすことにより、あるレベル内のセンサー全般を表す場合（例：Ｌ２−＊、Ｌ３−＊）もある。
【００２３】
本実施の形態では、ルートセンサーノードＲを頂点とする複数センサーからなるデータ収集ツリーの経路が生成される。ツリー上の各ツリーセンサーノードが、ルートセンサーノードまでツリーに沿ってデータを転送する集約サイクルを繰り返し、ルートセンサーノードが、収集したデータをベースステーションに定期的に送信する。
【００２４】
なお、初期状態では、ルートセンサーノードＲのみがツリーセンサーノードあり、他のセンサーは、浮遊センサーであるとする。また、ルートセンサーノードは、各センサーのセンサーデータの経路を選択する経路選択装置１０を含む。すなわち、各浮遊センサーＬ１−＊、Ｌ２−＊、Ｌ３−＊は、経路選択（ルーティング）を行う必要がない。
【００２５】
図５は、本発明の実施の形態における経路選択装置のハードウェア構成例を示す図である。図５の経路選択装置１０は、それぞれバスＢで相互に接続されているドライブ装置１００、補助記憶装置１０２、メモリ装置１０３、ＣＰＵ１０４、及びインタフェース装置１０５等を有する。
【００２６】
経路選択装置１０での処理を実現するプログラムは、ＣＤ−ＲＯＭ等の記録媒体１０１によって提供される。プログラムを記憶した記録媒体１０１がドライブ装置１００にセットされると、プログラムが記録媒体１０１からドライブ装置１００を介して補助記憶装置１０２にインストールされる。但し、プログラムのインストールは必ずしも記録媒体１０１より行う必要はなく、ネットワークを介して他のコンピュータよりダウンロードするようにしてもよい。補助記憶装置１０２は、インストールされたプログラムを格納すると共に、必要なファイルやデータ等を格納する。
【００２７】
メモリ装置１０３は、プログラムの起動指示があった場合に、補助記憶装置１０２からプログラムを読み出して格納する。ＣＰＵ１０４は、メモリ装置１０３に格納されたプログラムに従って経路選択装置１０に係る機能を実行する。インタフェース装置１０５は、ネットワークに接続するためのインタフェースとして用いられる。
【００２８】
図６は、本発明の実施の形態における経路選択装置の機能構成例を示す図である。図６において、経路選択装置１０は、隣接センサー情報取得部１１、レベル毎ルート決定部１２、ツリー経路最終決定部１３、及びルーティング要求部１４等を含む。レベル毎ルート決定部１２は、エネルギー減少度更新部１２１及び最終ルート決定部１２２等を含む。これら各部は、経路選択装置１０にインストールされた１以上のプログラムが、ＣＰＵ１０４に実行させる処理により実現される。経路選択装置１０は、また、隣接センサーリスト記憶部１５及びツリーノード記憶部１６等を利用する。これら各記憶部は、例えば、メモリ装置１０３、補助記憶装置１０２、又は経路選択装置１０にネットワークを介して接続可能な記憶装置等を用いて実現可能である。
【００２９】
以下、経路選択装置１０が実行する処理手順について説明する。
【００３０】
まず、隣接センサー情報取得部１１は、ルートセンサーノードＲの隣接浮遊センサーを探索する。本実施の形態では、Ｌ１−１及びＬ１−２が、該当隣接浮遊センサーとして検知される。なお、隣接浮遊センサーの検知は、例えば、各隣接浮遊センサーから発信されている電波の受信によって行われる。
【００３１】
隣接センサー情報取得部１１は、隣接浮遊センサーとして検知されたＬ１−１及びＬ１−２のそれぞれからセンサー情報を取得し（図７）、取得されたセンサー情報を隣接センサーリスト記憶部１５に記憶する。或るセンサーのセンサー情報には、当該センサーの識別子や、当該センサーの初期エネルギー量（後述のＥｉ）等が含まれている。
【００３２】
図８は、隣接センサーリスト記憶部の記憶内容の一例を示す図である。図８には、隣接センサーリスト記憶部１５の記憶内容の遷移が示されている。この時点において、隣接センサーリスト記憶部１５の記憶内容は、（１）に示される通りである。なお、図８において、Ｌ１−１、Ｌ１−２等は、Ｌ１−１、Ｌ１−２等のそれぞれのセンサー情報を示す。
【００３３】
続いて、レベル毎ルート決定部１２のエネルギー減少度更新部１２１は、Ｌ１−１及びＬ１−２のそれぞれのセンサー情報を隣接センサーリスト記憶部１５から取得して、Ｌ１−１、Ｌ１−２のエネルギー減少度を更新する。
【００３４】
エネルギー減少度は、以下の式１によって算出される。
Ｄ＝（ＥＴｘ×ＴＮ＋ＥＲｘ×ＲＮ）／Ｅｉ        （式１）
但し、ＥＴｘは、１パケットの送信に必要とされるエネルギー量、ＥＲｘは、１パケットの受信に必要とされるエネルギー量、Ｅｉは、当該ツリーセンサーノードの初期エネルギー量、ＴＮは、１データ集約サイクルに必要な送信パケット数、ＲＮは、データ集約サイクルの受信パケット数である。すなわち、或るツリーセンサーノードのエネルギー減少度は、当該ツリーセンサーノードの初期エネルギー量に対する、１データ集約サイクルにおいて当該ツリーセンサーノードがデータの受信に要するエネルギー量と当該ツリーセンサーノードが１データ集約サイクルにおいてデータの送信に要するエネルギー量との和の割合である。
【００３５】
なお、ＥＴｘ及びＥＲｘは、例えば、予め、経路選択装置１０に設定されており、各センサーに共通の値である。また、Ｅｉは、センサーから取得されたセンサー情報に含まれており、センサーごとに異なりうる。
【００３６】
また、或るツリーセンサーノードの送信パケット数ＴＮは、当該ツリーセンサーノードが１データ集約サイクルで受信する全てのパケットに含まれているデータの総数と、１つの送信パケットに格納可能なデータ数とに基づいて算出され、或るツリーセンサーノードの受信パケット数ＲＮは、当該ツリーセンサーノードの下位に直接接続するツリーセンサーノードの送信パケット数ＴＮの総和である。
【００３７】
具体的には、或るツリーセンサーノードの送信パケット数ＴＮ、受信パケット数ＲＮは、次のように求められる。
【００３８】
当該ツリーセンサーノードに繋がる親ツリーセンサーノード、直下の子センサーノード毎にバッファを生成し（例えば、メモリ装置１０３内にツリーセンサーノードごとに、親又は子とのリンクごとにバッファを生成し）、各バッファに記録されるセンサーデータ数をＢＮとし、データ集約率をｑ、整数Ａ、Ｂ（０≦Ｂ＜ｑ）とした場合、
ＢＮ＝Ａ×ｑ＋Ｂ、        （式２）
と表すことができる。この際、Ｂ＝０の場合は、当該バッファに記録されたデータ数に必要な送／受信パケットはＡと判定され、Ｂ＞０の場合は、当該バッファに記録されたデータ数に必要な受信／送信パケット数はＡ＋１となると判定される。また、ｑは、例えば、予め、経路選択装置１０に設定されており、各センサーに共通の値である。また、データ集約率とは、一つのパケットに集約できる（一つのパケットに格納可能な）センサーデータ数をいう。
【００３９】
なお、エネルギー減少度更新部１２１は、エネルギー減少度の更新に先立って、エネルギー減少度の更新対象のツリーセンサーノードの各リンクに対応するバッファ内の値を更新する。この時点では、Ｌ１−１、Ｌ１−２のそれぞれの、ルートセンサーノードＲへの送信バッファ内に１が記録される。
【００４０】
なお、ルートセンサーノードＲは、全ての経路の最終点であるので、ルートセンサーノードＲについて、エネルギー減少度の更新を行う必要がない。
【００４１】
続いて、レベル毎ルート決定部１２の最終ルート決定部１２２は、Ｌ１−１、Ｌ１−２がルートセンサーノードＲの隣接ノードであるため、Ｌ１−１、Ｌ１−２を、ツリー上でルートセンサーノードＲの直下に接続するツリーセンサーノードとして確定し、当該接続関係を示す情報をツリーノード記憶部１６に記憶する。
【００４２】
図９は、ツリーノード記憶部の記憶内容の一例を示す図である。図９には、ツリーノード記憶部１６の記憶内容の遷移が示されている。この時点において、ツリーノード記憶部１６の記憶内容は、（１）に示される通りである。
【００４３】
続いて、隣接センサー情報取得部１１は、ツリーセンサーノードＬ１−１、Ｌ１−２それぞれの隣接浮遊センサーを探索する。具体的には、隣接センサー情報取得部１１は、ツリーセンサーノードＬ１−１、Ｌ１−２のそれぞれから、まだ、ツリーセンサーノードになっていない隣接浮遊センサーのセンサー情報を取得する（図７）。すなわち、Ｌ１−１によって検知されるＬ２−１のセンサー情報が、Ｌ１−１を介して取得され、Ｌ１−２によって検知されるＬ２−２のセンサー情報が、Ｌ１−２を介して取得される。取得されたセンサー情報は、検知元のツリーセンサーノードのセンサー情報に関連付けられて、隣接センサーリスト記憶部１５に記憶される。この時点において、隣接センサーリスト記憶部１５の記憶内容は、図８の（２）に示される通りである。（２）では、Ｌ２−１が、Ｌ１−１の隣接センサーリスト（但し、リストの要素は１つ）であり、Ｌ２−２が、Ｌ１−２の隣接センサーリスト（但し、リストの要素は１つ）であることが示されている。
【００４４】
続いて、エネルギー減少度更新部１２１は、隣接センサーリスト記憶部１５から、Ｌ１−１及びＬ１−２のそれぞれの隣接センサーリストを取得して、各隣接センサーリストに係る経路上の各ツリーセンサーノードの各リンクに対応するバッファ内の値を更新すると共に、当該ツリーセンサーノードのエネルギー減少度を更新する。
【００４５】
具体的には、Ｌ２−１を新規ツリーセンサーノードとして、Ｌ１−１を親候補のツリーセンサーノードとして接続した場合について、Ｌ２−１のＬ１−１とのリンクに対応する送信バッファに１が記録されて、Ｌ２−１のエネルギー減少度が、式１及び式２に従って更新される。また、Ｌ１−１のＬ２−１とのリンクに対応する受信バッファに１が記録されるとともに、Ｌ１−１のＲとのリンクに対応する送信バッファに１が加算されて、Ｌ１−１のエネルギー減少度が式１及び式２に従って更新される。
【００４６】
同様にして、Ｌ２−２を新規ツリーセンサーノードとして、Ｌ１−２を親候補のツリーセンサーノードとして接続した場合について、Ｌ２−２及びＬ１−２のエネルギー減少度が式１及び式２に従って更新される。
【００４７】
この際、Ｌ１−１にはＬ２−１のみが、Ｌ１−２にはＬ２−２のみが隣接浮遊センサーとして存在するので（換言すれば、Ｌ２−１、Ｌ２−２のそれぞれには、親候補が１つしか無いため）、最終ルート決定部１２２は、Ｌ２−１をＬ１−１の直下に接続するツリーセンサーノードとして、Ｌ２−２をＬ１−２の直下に接続するツリーセンサーノードとして確定し、当該接続関係を示す情報をツリーノード記憶部１６に記憶する。この時点において、ツリーノード記憶部１６の記憶内容は、図９の（２）に示される通りである。
【００４８】
ここで、新たなレベル２（Ｌ２）のツリーセンサーノードが決定したので、レベル毎ルート決定部１２は、Ｌ２−１、Ｌ２−２の隣接センサーの取得を、隣接センサー情報取得部１１に要求する。
【００４９】
続いて、隣接センサー情報取得部１１は、Ｌ２−１及びＬ２−２のそれぞれの隣接浮遊センサーを探索する。具体的には、Ｌ２−１によって検知された隣接浮遊センサーである、Ｌ３−１〜Ｌ３−３のセンサー情報が、Ｌ２−１から取得され、Ｌ２−２によって検知された隣接浮遊センサーである、Ｌ３−１〜Ｌ３−４のセンサー情報が、Ｌ２−２から取得される（図７）。Ｌ２−１及びＬ２−２のそれぞれから取得されたセンサー情報は、隣接センサーリスト記憶部１５に記憶される。この時点において、隣接センサーリスト記憶部１５の記憶内容は、図８の（３）に示される通りである。すなわち、（２）まで記憶されていた、Ｌ１−１、Ｌ１−２の隣接センサーリストは、この時点で、Ｌ２−１、Ｌ２−２の隣接センサーリストに置き換えられる。Ｌ２のセンサーは全て、ツリーセンサーノードとして既にツリーノード記憶部１６に記憶されているからである。
【００５０】
続いて、エネルギー減少度更新部１２１は、Ｌ２−１の隣接センサーリストと、Ｌ２−２の隣接センサーリストとを順に取得して、各隣接センサーリストに係る経路上の各ツリーセンサーノードの各リンクに対応するバッファと、当該各ツリーセンサーノードのエネルギー減少度とを更新する。
【００５１】
まず、エネルギー減少度更新部１２１は、Ｌ２−１の隣接センサーであるＬ３−１〜Ｌ３−３を新規ツリーセンサーノードとして、Ｌ２−１を親候補のツリーセンサーノードとして接続した場合について、Ｌ３−＊からルートノードセンサーＲまでの経路上で、ルートノードセンサーＲを除く全てのツリーセンサーノードの当該経路に係るリンクに対応するバッファ内の値を更新し、当該全てのツリーセンサーノードのエネルギー減少度を、式１及び式２に従って更新する。
【００５２】
続いて、エネルギー減少度更新部１２１は、Ｌ２−２の隣接センサーＬ３−１〜Ｌ３−４のうち、まず、親候補が決まっていないＬ３−４を新規ツリーセンサーノードとして、Ｌ２−２を親候補のツリーセンサーノードとして接続した場合について、Ｌ３−４からＲへの経路上のツリーセンサーノードの当該経路に係るリンクに対応するバッファ内の値を更新し、当該ツリーセンサーノードのエネルギー減少度を更新する。
【００５３】
この際のＬ１−２のエネルギー減少度Ｄの更新例を図１０に示す。図１０において、左側の例は、Ｌ２−２がＬ１−２の直下に新規ツリーセンサーノードとして接続された場合のＤの更新例である。この場合、ｑ＝４、ＥＴｘ＝２、ＥＲｘ＝１とすると、Ｄは、１／７５から１／５０に更新される。
【００５４】
また、右に示すように、Ｌ３−４が、更に新規ツリーセンサーノードとしてＬ２−２の直下に接続された場合は、Ｌ１−２の受信センサーデータ数は１増えて２になり、送信データ数は１増えて３となるが、いずれもデータ集約率ｑよりも小さい。したがって、送受信パケット数に変更がないため、Ｄに変更はない。このように、或るツリーセンサーノードに関するＤの更新は、当該ツリーセンサーノードの各リンクに対応するバッファに基づいて、式２によって判定できる。
【００５５】
続いて、エネルギー減少度更新部１２１は、Ｌ２−２の隣接センサーＬ３−１〜Ｌ３−４のうち、既にツリーセンサーノードであり、Ｌ２−１の直下であるＬ３−１について、Ｌ２−１を親とする経路とＬ２−２を親とする経路間で、「経路エネルギー減少度」を比較する。
【００５６】
ここで、或る経路の経路エネルギー減少度とは、当該経路内において、エネルギー減少度が最大であるツリーセンサーノードのエネルギー減少度をいう。
【００５７】
エネルギー減少度更新部１２１は、Ｌ２−２を親とした場合について、Ｌ３−１からルートセンサーノードＲまでの経路上のツリーセンサーノードのエネルギー減少度を更新する。この際、Ｌ３−１がＬ２−１を親候補として接続された際にエネルギー減少度が更新されているセンサーノードのエネルギー減少度は更新されない。図７の例では、エネルギー減少度が更新されないツリーセンサーノードは、Ｌ３−１とルートセンサーノードＲのみであるが、仮に、Ｌ２−２がＬ１−１配下に接続されている場合、Ｌ１−１も更新されない。
【００５８】
続いて、エネルギー減少度更新部１２１は、Ｌ２−１を親とした場合の経路の経路エネルギー減少度と、Ｌ２−２を親とした場合の経路の経路エネルギー減少度とを比較して、経路エネルギー減少度が小さい経路を親候補として残すとともに、他の経路は親候補ではないとする。
【００５９】
例えば、Ｌ２−２を親とした場合の経路がＬ２−１を親とした場合の経路よりも経路エネルギー減少度が小さい場合は、Ｌ２−１を親とした場合の経路において、Ｌ２−２を親とした場合の経路で使われていないツリーセンサーノード（Ｌ２−１、Ｌ１−１）の各リンクに対応するバッファからＬ３−１のセンサーデータ分の１を減算し、必要に応じてこれらのセンサーノードのエネルギー減少度を再度更新する。理由は、Ｌ２−１を親とする経路は使われないことが決定したからである。
【００６０】
Ｌ３−２及びＬ３−３についてもＬ３−１と同様に経路エネルギー減少度の比較を行って、Ｌ２−１とＬ２−２とのいずれの親候補に接続するかを決定する。
【００６１】
続いて、最終ルート決定部１２２は、Ｌ３−＊の全ての接続先を決定し、その接続関係を示す情報を、ツリーノード記憶部１６に記憶する。この時点におけるツリーノード記憶部１６の記憶内容は、例えば、図９の（３）に示される通りである。この例では、Ｌ３−＊の全ての接続先が、Ｌ２−２として決定された例が示されている。
【００６２】
本実施の形態では、レベル３が最下位のレベルであるため、隣接センサー情報取得部１１は、Ｌ３−＊に対する隣接浮遊センサーの探索に失敗する。隣接浮遊センサーの探索の失敗に応じ、ツリー経路最終決定部１３は、ツリー経路の生成の完了を検知する。そこで、ルーティング要求部１４は、ツリーノード記憶部１６に記憶されている接続関係を実現するためのルーティングをＷＳＮに対して要求する。なお、ルーティング要求部１４は、レベルごとにルーティングをＷＳＮ対して要求してもよい。例えば、本実施の形態では、レベルＬ１、Ｌ２、又はＬ３までのそれぞれの接続関係がツリーノード記憶部１６に記憶されるたびに、その際に記憶されている接続関係を実現するためのルーティングがＷＳＮに対して要求されてもよい。そうすることで、各レベルにおける隣接浮遊センサーの探索処理を効率化することができる。
【００６３】
図３と同じ条件において、本実施の形態によって、従来の問題点が解決できることを説明する。図１１及び図１２は、本実施の形態におけるツリー経路選択手順の具体例を示す図である。図１１及び図１２を通して、ｑ＝４、ＥＴｘ＝２、ＥＲｘ＝１であり、各ツリーセンサーノードの括弧内の数字は、当該センサーの初期エネルギー量を示す。
【００６４】
図１１（１）は、Ｌ１のツリーセンサーノードであるＬ１−１、Ｌ１−２が、ルートセンサーノードＲの直下に接続された時点を示す。この時点において、Ｌ１−１、Ｌ１−２のルートセンサーノードＲへのリンクに対応するバッファ内の値は、１つの送信データを示す１であるので、式２においてＡ＝０、Ｂ＝１となる。この場合、このバッファに１データ集約サイクルで必要な送信パケット数はＡ＋１＝１となる。つまり、Ｌ１−１、Ｌ１−２は、受信パケットを受け取らないが、送信パケット数として１が必要になる。そのため、式１より、Ｌ１−１のエネルギー減少度及びＬ１−２のエネルギー減少度は、以下の通りとなる。
Ｌ１−１のエネルギー減少度＝ＥＴｘ／Ｅｉ＝２／１００＝１／５０
Ｌ１−２のエネルギー減少度＝２／１５０＝１／７５
図１１（２）は、Ｌ２のツリーセンサーノードであるＬ２−１、Ｌ２−２のそれぞれが、Ｌ１−１、Ｌ１−２直下に接続された時点を示す。Ｌ２−１、Ｌ２−２のそれぞれに対応する送信バッファには、１つの送信データを示す１が記録されるため、Ｌ２−１、Ｌ２−２のエネルギー減少度は、それぞれ２／５０、２／２００になる。また、Ｌ２−＊からＲまでの経路上のＬ１−１、Ｌ１−２もエネルギー減少度の更新が必要になる。ここでは、Ｌ１−１のＬ２−１からの受信バッファ内のデータ数が０から１になるので、ＥＲｘ＝１の受信のためのエネルギーが新たに考慮され、Ｌ１−１のエネルギー減少度＝（２＋１）／１００＝３／１００に更新される。同様にして、Ｌ１−２のエネルギー減少度＝（２＋１）／１５０＝１／５０に更新される。
【００６５】
図１１（３）は、Ｌ３のツリーセンサーノードが、Ｌ２−１の直下に接続され、その後にＬ２−２の隣接浮遊センサーであるＬ３−４が、Ｌ２−２直下に接続された時点を示す。Ｌ３−１〜Ｌ３−３がＬ２−１に接続された場合、Ｌ２−１に関しては、Ｌ３−＊との間の各リンクに対応する３つの受信バッファが保持されるが、その各バッファにはそれぞれ１つのデータを示す１が記録される。そのため、各バッファで必要となる受信パケット数は１であり、合計３つの受信パケットを１データ集約サイクルで受信することになる。Ｌ２−１に対応する送信バッファのデータ数は、自センサーデータを合わせると４であり、ｑ＝４のため、送信パケット数は１である。そのため、Ｌ２−１のエネルギー減少度は（２＋１×３）／５０に更新される。Ｌ１−１は、Ｌ２−１からのリンクに対応する受信バッファ内のデータ数が４であるため、受信パケット数は１であるが、ルートセンサーノードＲへのリンクに対応する送信バッファ内のデータ数は、自身のデータを含むので５となり、送信パケット数は２となる。そのため、Ｌ１−１のエネルギー減少度は（２×２＋１）／１００に更新される。
【００６６】
図１１（４）では、Ｌ２−２の隣接ノードとしてのＬ３−１がＬ２−２の直下に接続した場合について評価されている。この時点で、Ｌ３−１は、一時的にＬ２−１及びＬ２−２の両方の直下に接続している状態となっている。ただし、Ｌ２−１の直下のときに、既にエネルギー減少度Ｄが更新されているツリーセンサーノードのエネルギー減少度Ｄは更新されない。この例では、Ｌ３−１のみが該当するが、仮に、Ｌ２−２の親ツリーセンサーノードがＬ１−１の場合、Ｌ１−１は、既にＬ３−１のデータを考慮してエネルギー減少度Ｄが更新されているので更新されないことになる。
【００６７】
図１２（１）では、図１１（４）の状態において、Ｌ３−１の親として、Ｌ２−１及びＬ２−２のいずれが適しているのかを、両者に係る経路の経路エネルギー減少度を比較することにより決定されている。この例では、両者の経路がルートセンサーノードＲまで交わらないが、仮に、Ｌ２−２がＬ１−１の直下である場合は、Ｌ１−１に至るまでの経路間での比較になる（Ｌ２−１とＬ２−２のエネルギー減少度の比較）。すなわち、経路エネルギー減少度の比較は、比較される経路が交わるまでの区間に関して行われればよい。
【００６８】
経路エネルギー減少度は、経路上の各ツリーセンサーノードのエネルギー減少度の中での最大値であるため、Ｌ２−１経由の経路の経路エネルギー減少度は、Ｌ２−１の１／１０である。また、Ｌ２−２経由の経路の経路エネルギー減少度は、１／５０が複数あるので１／５０である。この場合、Ｌ２−２経由の方の経路エネルギー減少度が小さいため、Ｌ２−２経由の経路が選択され、Ｌ２−１が親候補から外される。その結果、図１２（２）のように、Ｌ３−１は、Ｌ２−１からＬ２−２に接続し直し、Ｌ２−１、Ｌ１−１のエネルギー減少度が、Ｌ３−１のデータが受信されない状態における値に再更新される。
【００６９】
図１２（２）では、Ｌ２−２の隣接センサーであるＬ３−２を、Ｌ２−２の直下に接続した場合について評価されている。図１２（１）の場合と同様に、Ｌ２−１経由の場合との経路エネルギー減少度が比較される。Ｌ２−１経由の経路では、Ｌ２−１のエネルギー減少度２／２５が最も大きく、Ｌ２−２経由の経路では、Ｌ１−２のエネルギー減少度１／３０が最も大きい。この場合、Ｌ２−２経由の経路の経路エネルギー減少度の方が小さいため、Ｌ２−２がＬ３−２の親候補として選択される。したがって、（３）に示すように、Ｌ２−１がＬ３−２の親とはならないことが確定したので、Ｌ２−１、Ｌ１−１のエネルギー減少度が、Ｌ３−２からのデータが受信されない状態における値に再更新される。
【００７０】
図１２（３）では、Ｌ２−２の隣接センサーであるＬ３−３をＬ２−２直下に接続した場合について評価されている。図１２（１）及び（２）の場合と同様に、Ｌ２−１経由の場合との経路エネルギー減少度が比較される。Ｌ２−１経由の経路では、Ｌ２−１のエネルギー減少度３／５０が最も大きく、Ｌ２−２経由の経路では、Ｌ１−２あるいはＬ２−２のエネルギー減少度１／２５が最も大きい。この場合、Ｌ２−２経由の経路の経路エネルギー減少度の方が小さいため、Ｌ２−２がＬ３−３の親候補として選択される。したがって、（４）に示すように、Ｌ２−１がＬ３−３の親とはならないことが確定したので、Ｌ２−１、Ｌ１−１のエネルギー減少度が、Ｌ３−３からのデータが受信されない状態における値に再更新される。
【００７１】
図１２（４）は、本実施の形態を図３のＷＳＮに適用した場合の経路の選択結果である。ここに示される通り、本実施の形態では、ツリー上のバランスだけでなく、初期エネルギー量とデータ集約率とを考慮したエネルギー減少率を正確に計算することが可能となることによって、ツリー寿命の長い最短経路ツリーの作成が可能とされている。
【００７２】
なお、図１１及び図１２の例では、各Ｌ３−＊の親候補がＬ２−１及びＬ２−２の２つのみであったが、３つ以上の親候補（Ｌ２−３、Ｌ２−４、...）がある場合は、親候補として残っているＬ２−２経由の経路と、Ｌ２−３経由の経路の経路エネルギー減少度の比較が行われ、経路エネルギー減少度が大きい親候補が、親候補から外される。このプロセスをＬ３−＊の全てのＬ２−＊までのリンクに対して行い、最終的に親候補として残った親候補が最終的な親として最終ルート決定部１２２によって決定され、決定された親との接続関係を示す情報がツリーノード記憶部１６に記憶される。
【００７３】
上述したように、本実施の形態によれば、各レベルで最も経路エネルギー減少度が小さくなる親候補に浮遊センサーが接続されるが、経路を構成する各センサーのエネルギー減少度にはセンサーの初期エネルギー量が考慮されている。したがって、初期エネルギー量が異なるセンサーで構成されるＷＳＮにおいて、図３で説明したようなツリー寿命低下を避けることができる。また、最もエネルギー減少度が小さい経路が使われるため、ツリー寿命が延びる効果が得られる。
【００７４】
また、本実施の形態では、エネルギー減少度にデータ集約率ｑが反映される。したがって、データ集約率が高い（ｑの値が大きい）場合、各ツリーセンサーノードのエネルギー減少速度は遅くなるため、各ツリーセンサーノードのエネルギー減少度は小さくなる必要があるが、式２のようにｑの値に応じた正確なパケット数を、ツリー上の全ての接続リンク毎に求めることができる。
【００７５】
なお、本実施の形態において、隣接センサー情報取得部１１は、探索部の一例である。レベル毎ルート決定部１２は、選択部の一例である。
【００７６】
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００７７】
１０          経路選択装置
１１          隣接センサー情報取得部
１２          レベル毎ルート決定部
１３          ツリー経路最終決定部
１４          ルーティング要求部
１５          隣接センサーリスト記憶部
１６          ツリーノード記憶部
１００        ドライブ装置
１０１        記録媒体
１０２        補助記憶装置
１０３        メモリ装置
１０４        ＣＰＵ
１０５        インタフェース装置
１２１        エネルギー減少度更新部
１２２        最終ルート決定部
Ｂ            バス
【図１】
2017139635.tif 000003
【図２】
2017139635.tif 000004
【図３】
2017139635.tif 000005
【図４】
2017139635.tif 000006
【図５】
2017139635.tif 000007
【図６】
2017139635.tif 000008
【図７】
2017139635.tif 000009
【図８】
2017139635.tif 000010
【図９】
2017139635.tif 000011
【図１０】
2017139635.tif 000012
【図１１】
2017139635.tif 000013
【図１２】
2017139635.tif 000014