JP4517885B2 - ネットワーク再構成方法、プログラム、情報記録媒体、ノード、基地局、マルチホップネットワークシステム - Google Patents

Description

本発明は、無線センサネットワークにおいてノードの削除、故障、追加時に、ツリーネットワークを部分的に再構成するネットワーク再構成方法に関する。

無線センサネットワークとは、温度や湿度の環境情報などを分散配置されたセンサノード（以下、ノード）でセンシングし、その結果をノードによって構成されたネットワークによって基地局に集め、統計分析や異常検出通知に活用するネットワークシステムである。

無線センサネットワークにおいては、ツリーネットワークを前提とし、ノードの初期設置時に基地局をルートとしたツリーネットワークが構成される。

ツリーネットワークを構成する方法として、非特許文献１に開示される方法がある。非特許文献１に開示されるルーティングは次のようなものである。
基地局は、各ノードに検出信号を順次送信する。各ノードは検出信号の受信強度がしきい値以上であるか否かを判断し、所定の強度以上で検出信号を受信したノードのみが検出応答信号を基地局へ返信する。
これにより、基地局と検出応答信号を返信したノードとの接続が確立される。

次に、基地局は、未だ接続が確立していない各ノードに対して既に接続が確立されたノードを介して検出信号を順次発信する。各ノードは検出信号の受信強度がしきい値以上であるか否かを判断し、所定の強度以上で検出信号を受信したノードのみが検出応答信号を検出信号の送信元であるノードを介して基地局へ返信する。

これにより、基地局と直接は接続できなかったノードは、基地局と直接接続されたノードを介して基地局へ接続される。

以上の手順を繰り返すことにより、ツリーネットワークが構成される。

非特許文献１に記載の手順は、基地局がノードの信号送信タイミングを集中制御するため、信号衝突を低減でき、ノード数が多い場合でも安定してツリーネットワークを構成できる。

一方、運用中にツリーネットワークの再構成が必要となる場合がある。これは、不要になったノードを削除する場合や、ノードが故障した場合や、新しいノードを追加する場合である。

ノードを削除する場合を例として説明する。図１に、基地局をルートとして、ノード１〜ノード１４で構成されるツリーネットワーク３０を示す。

ここで、ノード４が削除されるものとする。ノード４が削除されると、ノード４をルートとする部分木に属するノード、すなわちノード７、ノード１１、ノード１２及びノード１４は、ツリーネットワーク３０との接続を失って未接続ノードとなる。

同様に、ノードが故障した場合には、故障したノードをルートとした部分木に属するノードは未接続ノードとなる。また、ノードを追加する場合には、追加されるノード自体が未接続ノードとなる。

このような場合、ツリーネットワークを再構成することで、未接続ノードをツリーネットワークに再接続する必要が生じる。その際には、できるだけ短時間でツリーネットワークを再構成する必要がある。これは、運用中のサービスの停止時間を最小限に留める必要があるからである。

図２４に、従来の再接続の手法を示す。従来は、非特許文献１に記載の手順で、基地局から未接続ノードを一つずつ再検出し、ツリーネットワークを再構成する方法が用いられていた。換言すると、全てのノードを検出するか、全てのノードを経由して検出を行うまで、非特許文献１に記載の手順を繰り返していた。

また、従来のネットワーク再構成方法に関する別の例としては、特許文献１に開示される「マルチホップ無線ネットワークおよび無線局」がある。特許文献１に開示される発明は、各無線局が最適な接続先（上位接続先無線局）を見つけることにより、各無線局が自律的に無線ネットワークを構成するものである。
特開２００１−２３７７６４号公報 大熊孝裕、川崎大輔、保木本武宏、新井正伸著、「呼出しＩＤによる省電力マルチホップルーティング機能の実現」、信学技報、Vol.103,No.624,平成１６年１月２２日、３９〜４２ページ

非特許文献１に記載の手法を用いる場合の問題点は、ツリーネットワークの再構成に非常に時間がかかることである。その理由は、基地局から未接続ノードを一つずつ検出して、ツリーネットワークに再接続していくからである。
上記のように、ツリーネットワークの再構成は、できるだけ短時間で行う必要がある。非特許文献１に記載の発明は、この要求を十分に満たすものであるとはいえない。

また、特許文献１に記載の発明は、ある無線局が上位接続先無線局と接続できなくなった場合には、それより下位の無線局（子無線局）が順次上位接続先無線局の選定動作を行う。このため、無線局の数が多いとネットワーク再構成に要する時間が長期化してしまうこととなる。

このように、従来は、短期間でツリーネットワークを確実に再構成することはできなかった。

本発明は係る問題に鑑みてなされたものであり、短時間で確実にツリーネットワークを再構成できるネットワーク再構成方法及びそのプログラム並びにそれが記録されたコンピュータが読み取り可能な情報記録媒体、並びにノード、基地局、及びマルチホップネットワークシステムを提供することを目的とする。

上記目的を達成するため、本発明は、第１の態様として、基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法であって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定するステップと、代理ノードが、自ノード又は子孫ノードと無線ツリーネットワークとの接続性を検出するステップと、ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、ツリーネットワークとの接続性を有するノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを有することを特徴とするネットワーク再構成方法を提供するものである。

本発明の第１の態様においては、無線ツリーネットワークからノードを削除する際に、削除するノードの子ノードを代理ノードとして指定することが好ましい。また、無線ツリーネットワークへノードを追加する際に、追加するノードを代理ノードとして指定することが好ましい。また、無線ツリーネットワークに属するノードが故障した際に、故障したノードの子ノードを代理ノードとして指定することが好ましい。

本発明の第１の態様の上記のいずれの構成においても、無線ツリーネットワークとの接続性を検出するステップにおいては、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出することが好ましい。

また、本発明の第１の態様の上記のいずれの構成においても、無線ツリーネットワークとの接続性を検出するステップにおいて無線ツリーネットワークとの接続性を有するノードが複数検出された場合には、基地局までのホップ数が小さいものを部分木のルートとして設定することが好ましい。

また、上記目的を達成するため、本発明は、第２の態様として、基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法をノードに実行させるプログラムであって、ノードを制御する実質的なコンピュータに、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定するステップと、代理ノード又はその子孫ノードと無線ツリーネットワークとの接続性を検出するステップと、ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、ツリーネットワークとの接続性を有するノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを実行させることを特徴とするネットワーク再構成方法のプログラムを提供するものである。

本発明の第２の態様においては、自ノードが無線ツリーネットワークから削除される場合には、実質的なコンピュータに、子ノードを代理ノードとして指定させることが好ましい。また、自ノードが無線ツリーネットワークへ追加される場合には、実質的なコンピュータに自ノードを代理ノードとして指定させることが好ましい。また、自ノードの親ノードが故障した場合には、実質的なコンピュータに、自ノードを代理ノードとして指定させることが好ましい。

本発明の第２の態様の上記のいずれの構成においても、自ノードが未接続の部分木に属する場合、実質的なコンピュータに、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出させることが好ましい。

また、未接続の部分木に属する他のノードも無線ツリーネットワークとの接続性を有する場合には、実質的なコンピュータに、基地局までのホップ数が最小の場合にのみ自ノードを部分木の新たなルートとさせることが好ましい。

また、上記目的を達成するため、本発明は、第３の態様として、上記本発明の第２の態様のいずれかの構成にかかるネットワーク再構成方法のプログラムが記録されたコンピュータが読み取り可能な情報記録媒体を提供するものである。

また、上記目的を達成するため本発明は、第４の態様として、無線通信方式で基地局と接続されて無線ツリーネットワークを構成するノードであって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定する手段と、代理ノードとして指定された場合に、自ノードの子孫ノードに対して無線ツリーネットワークとの接続性の有無の確認を要求する手段と、無線ツリーネットワークとの接続性の有無を確認する手段と、自ノードが未接続の部分木に属する場合に、代理ノードからの指示に応じて、無線ツリーネットワークとの接続性を有するノードが新たなルートとなるように該未接続の部分木の階層構造を変更する手段と、自ノードが未接続の部分木の新たなルートとなった場合に、自ノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知する手段とを有することを特徴とするノードを提供するものである。

本発明の第４の態様においては、自ノードが無線ツリーネットワークから削除される場合には、子ノードを代理ノードとして指定することがこのましい、また、自ノードが無線ツリーネットワークへ追加される場合には、自ノードを代理ノードとして指定することが好ましい。また、自ノードの親ノードが故障した場合には、自ノードを代理ノードとして指定することが好ましい。

本発明の第４の態様の上記のいずれの構成においても、自ノードが未接続の部分木に属する場合、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出することがこのましい。

本発明の第４の態様の上記のいずれの構成においても、未接続の部分木に属する他のノードも無線ツリーネットワークとの接続性を有する場合には、基地局までのホップ数が最小の場合にのみ部分木の新たなルートとなることが好ましい。

また、上記目的を達成するため、本発明は、第５の態様として、無線通信方式で接続された少なくとも一つのノードとともに無線ツリーネットワークを構成する基地局であって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定する手段と、階層構造が変更された未接続の部分木に属するいずれかのノードから、変更後の未接続の部分木の階層構造に関する情報を受信した場合に、該受信した情報に応じてツリーネットワークの階層構造を表す情報を更新する手段とを有することを特徴とする基地局を提供するものである。

また、上記目的を達成するため、本発明は、第６の態様として、上記本発明の第４の態様のいずれかの構成にかかるノードを少なくとも一つと、上記本発明の第５の態様にかかる基地局とを有することを特徴とするマルチホップネットワークシステムを提供するものである。

本発明によれば、短時間で確実にツリーネットワークを再構成できるネットワーク再構成方法及びそのプログラム並びにそれが記録されたコンピュータが読み取り可能な情報記録媒体、並びにノード、基地局、及びマルチホップネットワークシステムを提供できる。

〔発明の原理〕
本発明では、ノードをツリーネットワークに再接続する処理を図１に示すように四つのステップに分けて行う。
第１のステップ（イニシエータ指定処理）では、基地局の代理となってツリーネットワークの再構成を制御する「イニシエータ」を指定する。このステップにおける処理によって、ノードの削除や故障によってツリーネットワークに未接続となった部分木（以下、未接続の部分木）のルートがイニシエータに指定される。

第２のステップ（Neighbor Discovery処理）では、ツリーネットワークとの接続性を検出するために、イニシエータがNeighbor Discoveryを実施するか、又は、イニシエータの子孫ノードがイニシエータからの指示に応じてNeighbor Discoveryを実施する。このステップにおける処理により、未接続の部分木に属するいずれかのノードと、ツリーネットワークとの接続性を検出する。

第３のステップ（部分木階層構造更新処理）では、Neighbor Discoveryによって検出したツリーネットワークとの接続性に応じて、未接続の部分木の階層構造を更新する。このステップにおける処理により、Neighbor Discoveryに成功したノードが、新しく未接続の部分木のルートとなるように階層構造を更新する。

第４のステップ（部分木再接続処理）では、未接続の部分木を再びツリーネットワークに接続する。このステップにおける処理により、未接続の部分木が再びツリーネットワークに接続される。

ツリーネットワークの再構成が必要となる契機は、上記のように、ノードを削除する場合、ノードが故障した場合及びノードを追加する場合であるが、上記のイニシエータ指定処理は再構成の契機によって手順が異なる。Neighbor Discovery処理、部分木階層構造更新処理及び部分木再接続処理は、全ての契機で共通する処理である。
ノード削除時、ノード故障時及びノード追加時のそれぞれの場合のイニシエータ指定処理については後段で詳細に説明する。

ツリーネットワークを再構成する際に、従来の手法のように基地局（ルート）から順に未接続ノードの再接続を試みるのではなく、イニシエータ指定処理でイニシエータを指定し、Neighbor Discovery処理で未接続の部分木に属するいずれかのノードとツリーネットワークとの接続性をイニシエータがNeighbor Discoveryによって検出する。そして、部分木階層構造更新処理では、Neighbor Discovery処理での検出結果に応じて、未接続の部分木の階層構造を更新し、部分木再接続処理で未接続の部分木とツリーネットワークとを再接続する。

これにより、ノードのルーティングテーブルの更新数を低減でき、結果としてツリーネットワークの再構成に要する時間を短縮できる。

以下、上記原理に基づく本発明の好適な実施の形態について説明する。

〔第１の実施形態〕
本発明を好適に実施した第１の実施形態について説明する。
図２に、基地局をルートとしてノード１〜ノード１４によって構成されるツリーネットワークを示す。
各ノードは、図３に示すルーティングテーブルを有する。ルーティングテーブルは、親ノード、子孫ノードの情報を含む。すなわち、自ノードをルートとする部分木の構成と、親ノードとの情報を含む。

基地局及び各ノードが送受信する信号の種類を図４に示す。

図５に、ツリーネットワークに適用されるノードの構成を示す。
ノード５００は、入力部５０１、出力部５０２、イニシエータ指示／実施部５０３、Neighbor Discovery指示／実施部５０４、部分木階層構造更新部５０５、記憶部５０６、ルーティング処理部５０７及び部分木追加部５０８を有する。

入力部５０１は、“ノード削除信号”、“ノード故障信号”、“イニシエータ指示信号”、“更新開始信号”、“更新開始指示信号”、“Neighbor Discovery指示信号”、“Neighbor Discovery成功信号”、“Neighbor Discovery失敗信号”、“更新信号”、“追加信号”、“更新完了信号”、“更新完了指示信号”などを入力として受け付ける。
また、入力部５０１は、ノード削除時及びノード追加時に、後述するイニシエータ指示／実施部５０３が動作を開始するための“削除開始信号”及び“追加開始信号”を受信する。

出力部５０２は、これらの信号を他のノード５００や基地局６００に対して送信する。

イニシエータ指示／実施部５０３の機能について説明する。
まず、ノード削除時の動作に関する機能ついて説明する。イニシエータ指示／制御部５０３は、ノード削除時には、以下のような動作を行う。
・入力部５０１が“削除開始信号”を受信すると、出力部５０２に“更新開始信号”を送信させる。
・入力部５０１が“更新開始信号”を受信すると、自ノードを運用状態から経路更新状態へ移行させ、Neighbor Discoveryに応答しないようにする。
・自ノードが削除ノードであるならば、全ての子孫ノードに“更新開始信号”を送信した後、“ノード削除信号”に自ノードのＩＤ情報を含めて、出力部５０２によって親ノードへ送信する。
・入力部５０１が“ノード削除信号“を受信すると、記憶部５０６に保持しているルーティングテーブルから、削除ノードをルートとする部分木を削除する。また、出力部５０２に親ノードへ“ノード削除信号”を送信させる。
・自ノードが削除ノードであるならば、親ノードに対して“ノード削除信号”を送信した後、出力部５０２に“イニシエータ指示信号”を送信させる。
・入力部５０１が“イニシエータ指示信号”を受信した場合には、自ノードをイニシエータとし、後述するNeighbor Discoveryを実行する。

ノード故障時のイニシエータ指定／実施部５０３の動作に関する機能について説明する。イニシエータ指示／制御部５０３は、ノード故障時には以下のような動作を行う。
・故障を発見したノードであるならば、記憶部５０６に保持している故障ノードをルートとする部分木を、記憶部５０６に保持しているルーティングテーブルから削除する。そして、“ノード故障信号”を故障発見ノード（すなわち、故障ノードの親ノードと基地局との間にあるノード）へ送信する。
・入力部５０１が“更新開始指示信号”を受信すると、記憶部５０６に保持している部分木から故障ノードをルートとする部分木を削除する。
・入力部５０１が“更新開始指示信号“を受信すると、出力部５０２に全子孫ノードに対して“更新開始信号”を送信させる。
・全子孫ノードに対して“更新開始信号”を送信した後、「全ての子孫ノードに対して“更新開始信号”を送信したこと」を示す“通知完了信号”を、出力部５０２から基地局へ送信させる。
・入力部５０１が“イニシエータ指示信号”を受信すると、自ノードをイニシエータとする。

ノード追加時のイニシエータ指定／実施部５０３の動作に関する機能について説明する。イニシエータ指定／制御部５０３は、ノード追加時には以下のような動作を行う。
・入力部５０１が“追加開始信号”を受信すると、自ノードをイニシエータとする。

Neighbor Discovery指示／実施部５０４について説明する。Neighbor Discovery指示／実施部５０４では、自ノードがイニシエータであるならば、Neighbor Discoveryを実行する。また、イニシエータは、子孫ノードに対して“Neighbor Discovery指示信号”を送信する。
“Neighbor Discovery指示信号”を受信したノードは、Neighbor Discoveryを実施する。Neighbor Discoveryに成功した場合はその結果を記憶部５０６に保存し、イニシエータに対して“Neighbor Discovery成功信号”を送信する。Neighbor Discoveryに成功したノードは、新しく部分木のルートとなる（以下、新ルートノード）。
Neighbor Discoveryに失敗した場合は、イニシエータに“Neighbor discovery失敗信号”を送信する。

部分木階層構造更新部５０５について説明する。
部分木階層構造更新部５０５は、Neighbor Discoveryの結果に応じて、イニシエータをルートとして更新した部分木の階層構造をルーティングテーブルに反映させる。
入力部５０１から“Neighbor Discovery成功信号”を受信すると、イニシエータは自ノードのルーティングテーブルを更新する。そして、そのルーティングテーブルと新しいルートノードの情報とを“更新情報”に含め、出力部５０２に新しい親ノードへ送信させる。
ここで、新しい親ノードは、旧ルーティングテーブルにおいて、新ルートノードを子孫として持つ子ノードが選択される。

入力部５０１から“更新信号”を受信すると、これに含まれる新ルートノードを旧ルーティングテーブルで子孫ノードとして持つ子ノードを新しい親ノードとする。また、“更新信号”に含まれる部分木情報を、ルーティングテーブルに追加する。
そして、自ノードのルーティングテーブルと新しいルートノードとの情報を“更新信号”ともに親ノードへ送信する。

新ルートノードが入力部５０１によって“更新信号”を受信すると、これに含まれるルーティングテーブルを自ノードのルーティングテーブルに追加する。また、Neighbor Discoveryで検出したノードを新しい親ノードにする。

部分木追加部５０６について説明する。
新ルートノードでは、出力部５０２によって、自ノードのルーティングテーブルを“追加信号”とともに親ノードへ送信する。
“追加信号”を受信したノードでは、“追加信号”に含まれるルーティングテーブルの情報を自ノードのルーティングテーブルに追加する。そして、受信した”追加信号”の内容を出力部５０２を用いて親ノードへ送信する。
入力部５０１によって“更新完了信号”を受信した新ルートノードは、全子孫ノードへ“更新完了信号”を出力部５０２から送信する。“更新完了信号”を受信したノードは、経路更新状態から運用状態へと移行する。

記憶部５０６は、ルーティングテーブルNeighbor Discoveryの結果などを保持する。

ルーティング処理部５０７は、後述するノード故障時に非特許文献１に開示される手法を利用して、仮経路を作成する際に用いられる。

図６に、基地局６００の構成を示す。
基地局６００は、入力部６０１，出力部６０２、イニシエータ指示／実施部６０３、記憶部６０６、ルーティング処理部６０７及び部分木追加部６０８を有する。
入力部６０１は、“ノード削除信号”、“ノード故障信号”、“追加信号”、“追加完了信号”などを入力として受け付ける。

イニシエータ指示／実施部６０３の機能について説明する。
入力部６０１によって“ノード削除信号”を受信すると、記憶部６０６に保持しているルーティングテーブルから削除ノードをルートとする部分木を削除する。
入力部６０１によって“ノード故障信号”を受信すると、記憶部６０６に保持しているルーティングテーブルから故障ノードをルートとする部分木を削除する。また、出力部６０２を用いて、故障ノードの子ノードへ“更新開始指示信号”を送信する。
入力部６０１によって“通知完了信号”を受信すると、“イニシエータ指示信号”を故障ノードの子ノードへ出力部６０２を用いて出力する。

部分木追加部６０８の機能について説明する。
入力部６０１によって“追加信号”を受信した基地局は、“追加信号”に含まれるルーティングテーブルの情報を、自ノードのルーティングテーブルに追加する。そして、基地局のルーティングテーブル更新が完了したことを示す“更新完了信号”を新ルートノードに対して出力部６０２によって送信する。

記憶部６０６は、ルーティングテーブルやNeighbor Discoveryの結果などを保持する。

ルーティング処理部６０７は、後述するノード故障時に非特許文献１に開示される手法を利用して、仮経路を作成する際に用いられる。

ツリーネットワークの再構成動作について説明する。
まず、イニシエータを指定する手順について説明する。上記のように、イニシエータを指定する手順は、動作開始の契機によって異なるため、それぞれについて個別に説明する。

＜ノード削除時のイニシエータ指定手順＞
最初にノード削除時のイニシエータの指定手順について説明する。図７にノード削除時のイニシエータの指定動作の流れを示す。
削除ノードは“削除開始信号”を受信すると（ステップＢ１）、全子孫ノードに“更新開始信号”を送信する（ステップＢ２）。“更新開始信号”を受信したノードは、図８に示すように運用状態から経路更新状態へと移行する。

次に、削除ノードは、削除ノードから基地局までの間にあるノードに対して“ノード削除信号”を送信する（ステップＢ３）。“ノード削除信号”を受信したノードは、削除ノードをルートとする部分木をルーティングテーブルから削除する。

削除ノードは、子ノードにイニシエータ動作を指示する“イニシエータ指示信号”を送信する（ステップＢ４）。“イニシエータ指示信号”を受信したノードは、イニシエータとなり、後述するNeighbor Discoveryの実行などを制御する（ステップＢ５）。

＜ノード故障時のイニシエータ指定手順＞
次に、ノード故障時のイニシエータの指定手順について説明する。図９に、ノード故障時のイニシエータ指定動作の流れを示す。ノード故障時には、故障したノード（故障ノード）を発見したノード（すなわち、故障ノードの親ノード）が、故障ノードをルートとした部分木を自ノードのルーティングテーブルから削除する。そして、故障ノードの親ノードと基地局との間にある各ノードに対し、故障ノードの発生を通知する“ノード故障信号”を送信する（ステップＣ１）。“ノード故障信号”を受信したノードは、故障ノードをルートとする部分木をルーティングテーブルから削除する。

ノード削除時と同様に、ノード故障時も、故障ノードの子ノードに”更新開始信号”と”イニシエータ指示信号”とを送信する必要がある。しかし、故障ノードの子ノードへの経路は存在しないため、基地局は故障ノードの子ノードへの仮経路を非特許文献１に開示される手法を応用して作成する（ステップＣ２）。

この際には、非特許文献１に開示される手法を利用して、故障ノードの子ノードをルートとした部分木に属するいずれかのノードを検出する。これにより、ツリーネットワークと故障したノードをルートとした部分木に属するいずれかのノードとの間に仮経路を形成できる。
このとき、検出されたノードを経由ノードと呼ぶ。基地局は、この仮経路を使用して、故障ノードの子ノード宛に“更新開始指示信号”や”イニシエータ指示信号”を送信する（ステップＣ３）。その際に、経由ノードのＩＤを信号に含める。
故障ノードをルートとした部分木に属するノードは、自ノード宛ではない”更新開始指示信号”や”イニシエータ指示信号”を親ノードへ転送する。

このようにすることで、“更新開始指示信号”や“イニシエータ指示信号”を故障ノードの子ノードへ送達できる（ステップＣ４）。

また、故障ノードの子ノードは、“通知完了信号”を基地局へ送信するが、“更新開始指示信号”に含まれた経由ノードへ先ず送信する。“更新完了信号”を受信した経由ノードは、仮経路を利用して、受信した信号を基地局へ転送する（ステップＣ５）。

以上の手順で、イニシエータが指定されるまで、基地局と故障ノードの子ノードとは仮経路を使用して通信する。

基地局は仮経路を利用して、故障ノードの子ノード及び、故障ノードの子ノードの子孫ノードへ“更新開始指示信号”を送信する。“更新開始指示信号”を受信した故障ノードの子ノードは、全子孫ノードに対して“更新開始信号”を送信する。

故障ノードの子ノードは、全子孫ノードに“更新開始信号”を送信したことを”通知完了信号”によって基地局に通知する。

基地局は、故障ノードの子ノードから“通知完了信号”を受信すると、仮経路を利用して“イニシエータ指示信号”を故障ノードの子ノードへ送信する（ステップＣ６）。

イニシエータ指示信号を受信した故障ノードの子ノードは、仮経路を削除するために、“仮経路削除信号“を、削除ノードと基地局との間にある各ノードへ送信する（ステップＣ７）。これにより、仮経路は削除される。

イニシエータとなったノードは（ステップＣ８）、後述するNeighbor Discoveryの実行などを制御する。

＜ノード追加時の基地局の動作＞
ノード追加時の基地局の動作について説明する。図１０に、ノード追加時の基地局の動作の流れを示す。
“追加開始信号”を受信したノードは（ステップＦ１）、イニシエータとなる（ステップＦ２）。

以上のようにして、ノード削除時、ノード故障時、ノード追加時にイニシエータが指定される。

次に、イニシエータのNeighbor Discovery実施・指示の動作について説明する。図１１、図１２及び図１３に、Neighbor Discovery実施・指示動作の流れを示す。イニシエータは、先ず自らがNeighbor Discoveryを実施し、ツリーネットワークとの新しい接続性検出を試みる（ステップＤ１）。ここで、Neighbor Discoveryが検出された場合は（ステップＤ２／Ｙｅｓ）、イニシエータは検出したノードを新しい親ノードに選択し、ルーティングテーブルを更新する。

もし、イニシエータがNeighbor Discoveryに失敗した場合は（ステップＤ２／Ｎｏ）、イニシエータとのホップ数が小さい子孫ノードから順番に、“Neighbor Discovery指示信号”を送信し、子孫ノードがNeighbor Discoveryを実施する（ステップＤ３）。

子孫ノードがNeighbor Discoveryに成功した場合は（ステップＤ４／Ｙｅｓ）、イニシエータをルートとした部分木を、Neighbor Discoveryに成功した子孫ノード（以下、新ルートノード）が新しい部分木のルートとなるように階層構造を変更する（ステップＤ６）。ここで、階層構造の変更に伴い、新ルートノードとイニシエータとの間でルーティングテーブルを更新する（ステップＤ６〜Ｄ１２）。

イニシエータは、新しい部分木の情報をルーティングテーブルに追加することを要求する“追加信号”を、新ルートノードと基地局（基地局も含む）の経路にあるノードに対して送信する（ステップＤ１３〜Ｄ１６）。これにより、新ルートノードと基地局との経路にある各ノードのルーティングテーブルが更新される。また、“追加信号“を受信した基地局は、“更新完了通知“を新ルートノードへ送信する（ステップＤ１７）。基地局からの“更新完了通知”を受信した新ルートノードは、経路変更が完了したことを示す“更新完了通知”を全子孫ノードに送信する（ステップＤ１８）。“更新完了通知”を受信したノードの状態は、経路更新状態から運用状態へと移行する。

〔動作例１〕
図２に示したツリーネットワーク３０において、ノード４が削除されるものとする。
まず、ノード４は、“削除開始信号”を受信すると、全ての子孫ノード、つまり、ノード７，ノード１１、ノード１４及びノード１２に対して“更新開始信号”を送信する。
図８に示すように、更新開始信号を受信したノードは、運用状態から経路更新状態へと移行する。経路更新状態のノードは、基地局までの到達性を持たないため、Neighbor Discoveryに対してリプライを返さない。

次に、ノード４は、自ノードから基地局までの経路にあるノード、すなわちノード１及び基地局に対して“ノード削除信号”を送信する。“ノード削除信号”を受信したノード（ノード１及び基地局）は、削除ノード（ノード４）をルートとする部分木の情報をルーティングテーブルから削除する。この時、ノード１と基地局とのルーティングテーブルを図１４に示す。

次に、ノード４は、子ノードであるノード７に“イニシエータ指示信号”を送信する。これにより、ノード７はイニシエータとなる。

イニシエータとなったノード７は、まず自らがNeighbor Discoveryを実施し、ツリーネットワーク３０との新しい接続性検出を試みる。

以下、イニシエータであるノード７におけるNeighbor Discoveryが成功した場合を例として説明する。
Neighborが検出された場合は、ノード７は検出したノードを新しい親ノードに選択し、ルーティングテーブルを更新する。ここでは、ノード３がNeighborとして検出されたものとする。この時の、ノード７のルーティングテーブルを図１５に示す。

次に、ノード７は、自ノードと基地局との間のノード、すなわち、ノード３、ノード１及び基地局に“追加信号”を送信する。“追加信号”には、自ノードのルーティングテーブル情報が付加される。“追加信号”を受信したノード３、ノード１及び基地局は、ノード７をルートとする部分木の情報をルーティングテーブルに追加する。この時のノード３、ノード１及び基地局のルーティングテーブルは図１６のようになる。

このようにして、ノード７から基地局までの経路にある各ノードのルーティングテーブルが更新される。最後に、イニシエータであるノード７は、全ての子孫ノード、すなわちノード１１、ノード１４及びノード１２へ“更新完了信号”を送信する。
“更新完了信号”を受信したノードは、経路更新状態から運用状態へと移行する。

次に、イニシエータであるノード７におけるNeighbor Discoveryが失敗した場合について説明する。
イニシエータであるノード７がNeighbor Discoveryに失敗した場合は、イニシエータは、ホップ数が小さい子孫ノードから順番に“Neighbor Discovery指示信号”を送信し、子孫ノードにNeighbor Discoveryを実施させる。ここでは、ノード１１→ノード１２→ノード１３の順番でNeighbor Discoveryの指示を出すものとする。

子孫ノードがNeighbor Discoveryを実行する場合の具体例として、ノード１１及びノード１２がNeighbor Discoveryに失敗し、ノード１４がNeighbor Discoveryに成功した場合について説明する。
イニシエータであるノード７は、ノード１１にNeighbor Discovery指示信号を送信する。“Neighbor Discovery指示信号”を受信したノード１１は、Neighbor Discoveryを実行する。ノード１１は、Neighbor Discoveryを実行した結果、ノードを検出できなかったため、“Neighbor Discovery失敗信号”をノード７へ送信する。

ノード７は、次に、ノード１２に対して“Neighbor Discovery指示信号”を送信する。“Neighbor Discovery指示信号”を受信したノード１２は、Neighbor Discoveryを実行する。ノード１２は、Neighbor Discoveryを実行した結果、ノードを検出できなかったため、“Neighbor Discovery失敗信号”をノード７へ送信する。

ノード７は、次に、ノード１４に“Neighbor Discovery指示信号を送信する。“Neighbor Discovery指示信号”を受信したノード１４は、Neighbor Discoveryを実行する。ノード１４はNeighbor Discoveryを実行した結果、ノード９を検出する。ノード１４は、検出したNeighborを保持し、イニシエータであるノード７へ“Neighbor Discovery成功信号”を送信する。

ノード１４からの“Neighbor Discovery成功信号”を受信したオード７は、ノード７をルートとする部分木を、ノード１４がルートとなるように階層構造を変更する。

ノード７にとって、ノード１４を子孫ノードに持つ子ノードは、ノード１１である。従って、ノード１１がノード７の新しい親ノードとなる。また、ノード１１をルートとする部分木をルーティングテーブルから削除する。この時の、ノード７のルーティングテーブルを図１７に示す。

ノード７は、更新したルーティングテーブルと新ルートノードのＩＤ情報とを“更新情報”とともに親ノードであるノード１１へ送信する。

“更新信号”を受信したノード１１は、子孫ノードであるノード１４を新しい親ノードとする。また、ノード１４をルートとする部分木をルーティングテーブルから削除する。そして、受信した“更新信号”の情報をルーティングテーブルに追加する。この時のノード１１のルーティングテーブルを図１８に示す。

ノード１１は、更新したルーティングテーブルと新ルートノードのＩＤ情報とを、“更新情報”とともに親ノードであるノード１４へ送信する。

“更新情報”を受信したノード１４は、受信した“更新信号”に含まれるルーティングテーブルの情報を、自ノードのルーティングテーブルに追加する。

また、ノード１４は、Neighbor Discoveryで検出したノード９を親ノードとして設定する。この時のノード１４のルーティングテーブルを図１９に示す。

ノード１４は、自ノードと基地局との経路にあるノード（基地局を含む）、すなわち、ノード９、ノード６、ノード３、ノード１及び基地局に対して“追加信号”を送信する。これにより、ノード１４と基地局との経路にある各ノードのルーティングテーブルが更新される。この時のノード９、ノード６、ノード３、ノード１及び基地局のルーティングテーブルを図２０に示す。

受信した“追加信号”に応じてルーティングテーブルを更新した基地局は、“更新完了信号”をノード１４へ送信する。

“更新完了信号”を受信したノード１４は、全子孫ノード、すなわち、ノード１１、ノード７及びノード１２に“更新完了信号”を送信する。“更新完了信号”を受信したノードは、経路変更状態から運用状態へと移行する。

以上でノード削除時の動作を完了する。上記動作において再構成されたツリーネットワークを図２１に示す。

〔動作例２〕
ツリーネットワークを構成するノードが故障した場合の動作について説明する。上記動作例１は、ツリーネットワークからノードを削除する場合のものであったが、ノード削除時の動作と、ノード故障時又はノード追加時の動作との差分は、イニシエータ指定の動作である。従って、イニシエータ指定の動作のみを説明する。

図２に示したツリーネットワーク３０において、ノード４が故障したものとする。

ノード故障の場合は、ノード故障を発見したノード、すなわち故障したノード（ノード４）の親ノードであるノード１が、ノード４をルートとする部分木を自ノードのルーティングテーブルから削除する。そして、ノード１から基地局までの経路にあるノード（すなわち基地局）に対して“ノード故障信号”を送信する。“ノード故障信号“を受信した基地局は、故障ノードであるノード４をルートとする部分木の情報をルーティングテーブルから削除する。この時のノード１及び基地局のルーティングテーブルを図２２に示す。

“ノード故障信号”を受信した基地局は、非特許文献１に開示される手法を用いて、基地局とノード７との間に仮経路を作成する。例えば、ノード１４の子孫ノードであるノード１２をノード１３から検出したとする。この場合、以降の“更新開始指示信号”、“通知完了信号”、“イニシエータ指示信号”は仮経路を利用して送受信される。ノード７が、“イニシエータ指示信号”を受信してイニシエータとなると、“仮経路削除信号”をノード７→ノード１２→ノード１３→ノード８→ノード５→ノード２→基地局へ送信し、仮経路を削除する。

基地局は仮経路を利用して、“更新開始指示信号”をノード７へ送信する。“更新開始信号”を受信したノード７は、全子孫ノード、すなわちノード１１、ノード１４及びノード１２に対して“更新開始信号”を送信する。そして、ノード７は、“通知完了信号”を基地局に通知する。

基地局は、ノード７から“通知完了信号”を受信すると、仮経路を利用して、“イニシエータ指示信号”をノード７へ送信する。“イニシエータ指示信号”を受信したノード７は、仮経路削除要求を基地局に対して送信する。そして、イニシエータとなり、Neighbor Discoveryの実行などを制御する。

〔動作例３〕
ノードを追加する場合は、“ノード追加信号”を受信すると、追加ノード自身がイニシエータとなる。イニシエータの指定以外の手順については上記動作例１と同様である。

本実施形態に係るツリーネットワークにおいては、ツリーネットワークの再構成時に、ノードのルーティングテーブルの更新数を低減でき、結果としてツリーネットワークの再構成に要する時間を短縮できる。しかも、イニシエータ自身がツリーネットワークとの接続性を有しない場合には、その子孫ノードとツリーネットワークとの接続性を調べ、接続性を有するノードが存在すればそれを新たなルートとしてツリー構造を変更するため、未接続の部分木を確実にツリーネットワークに接続できる。

〔第２の実施形態〕
本発明を好適に実施した第２の実施形態について説明する。
図２３に、本実施形態におけるネットワーク再構成の動作の流れを示す。
第１の実施形態の動作との違いは、Neighbor Discoveryの結果複数のNeighborが検出された場合に、基地局までのホップ数が最小のノードをNeighborとして選択することである。

基地局までのホップ数が最小のノードをNeighborとして選択することで、新ルートノードから基地局までのホップ数が小さくなり、ルーティングテーブルの更新回数を低減できる。

これにより、ツリーネットワークの再構成に要する時間をさらに短縮できる。

〔第３の実施形態〕
図５及び図６に示した基地局６００及びノード５００は、専用のハードウェアによって実現する以外に、その機能を実現する為のプログラムをコンピュータが読み取り可能な記録媒体に記録しておき、これをコンピュータに読み取らせて基地局６００及びノード５００として機能させることも可能である。
コンピュータが読み取り可能な記録媒体としては、磁気ディスク、光磁気ディスク、光ディスクといった交換可能な記録媒体の他、コンピュータに内蔵される記録媒体（ＨＤや半導体メモリなど）を適用可能である。

さらに、インターネットを介してプログラムを送信する場合のように、短時間の間に動的にプログラムを保持するもの（伝送媒体又は伝送波）や、コンピュータ内部のメモリのように一定時間プログラムを保持するものも含む。

基地局６００やノード５００の機能をコンピュータによるソフトウェア処理によって実現する場合でも、その動作については同様であるため、重複する説明は省略する。

なお、上記各実施形態は本発明の好適な実施の一例であり、本発明はこれに限定されることはない。
例えば、上記各実施形態において例示したツリーネットワークでは、子ノードの数は２以下であったが、３以上の子ノードを備えるノードが存在していても良いことはいうまでもない。
また、２以上のノードが同時に削除、追加、故障した場合についても上記同様の動作によってツリーネットワークの再構成が可能である。
このように、本発明は様々な変形が可能である。

本発明におけるツリーネットワーク再構成の手順を示す図である。 ツリーネットワークの一例を示す図である。 ツリーネットワークの各ノードのルーティングテーブルの一例を示す図である。 ツリーネットワークの再構成の際に各ノード間でやりとりされる信号を示す図である。 ノードの構成例を示す図である。 基地局の構成例を示す図である。 ノード削除時のイニシエータ指定処理の動作の流れを示す図である。 ノードの状態の変移を表す図である。 ノード故障時のイニシエータ指定処理の動作の流れを示す図である。 ノード追加時のイニシエータ指定処理の動作の流れを示す図である。 部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。 部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。 部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。 ルーティングテーブルの一例を示す図である。 ルーティングテーブルの一例を示す図である。 ルーティングテーブルの一例を示す図である。 ルーティングテーブルの一例を示す図である。 ルーティングテーブルの一例を示す図である。 ルーティングテーブルの一例を示す図である。 ルーティングテーブルの一例を示す図である。 再構成後のツリーネットワークの構成を示す図である。 ルーティングテーブルの一例を示す図である。 部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。 従来技術によるツリーネットワーク再構成処理の手順を示す図である。

符号の説明

５０１、６０１ 入力部
５０２、６０２ 出力部
５０３、６０３ イニシエータ指示／実施部
５０４ Neighbor Discovery指示／実施部
５０５ 部分木階層構造更新部
５０６、６０６ 記憶部
５０７、６０７ ルーティング処理部
５０８、６０８ 部分木追加部

Claims (21)

1. 基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法であって、
   前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定するステップと、
   前記代理ノードが、自ノード又は子孫ノードと前記無線ツリーネットワークとの接続性を検出するステップと、
   前記ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、
   前記ツリーネットワークとの接続性を有するノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを有することを特徴とするネットワーク再構成方法。
2. 前記無線ツリーネットワークからノードを削除する際に、削除するノードの子ノードを前記代理ノードとして指定することを特徴とする請求項１記載のネットワーク再構成方法。
3. 前記無線ツリーネットワークへノードを追加する際に、追加するノードを前記代理ノードとして指定することを特徴とする請求項１又は２記載のネットワーク再構成方法。
4. 前記無線ツリーネットワークに属するノードが故障した際に、故障したノードの子ノードを前記代理ノードとして指定することを特徴とする請求項１から３のいずれか１項記載のネットワーク再構成方法。
5. 前記無線ツリーネットワークとの接続性を検出するステップにおいては、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出することを特徴とする請求項１から４のいずれか１項記載のネットワーク再構成方法。
6. 前記無線ツリーネットワークとの接続性を検出するステップにおいて前記無線ツリーネットワークとの接続性を有するノードが複数検出された場合には、前記基地局までのホップ数が小さいものを前記部分木のルートとして設定することを特徴とする請求項１から５のいずれか１項記載のネットワーク再構成方法。
7. 基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法を前記ノードに実行させるプログラムであって、
   前記ノードを制御する実質的なコンピュータに、
   前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定するステップと、
   前記代理ノード又はその子孫ノードと前記無線ツリーネットワークとの接続性を検出するステップと、
   前記ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、
   前記ツリーネットワークとの接続性を有するノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを実行させることを特徴とするネットワーク再構成方法のプログラム。
8. 自ノードが前記無線ツリーネットワークから削除される場合には、前記実質的なコンピュータに、子ノードを前記代理ノードとして指定させることを特徴とする請求項７記載のネットワーク再構成方法のプログラム。
9. 前記自ノードが前記無線ツリーネットワークへ追加される場合には、前記実質的なコンピュータに自ノードを前記代理ノードとして指定させることを特徴とする請求項７又は８記載のネットワーク再構成方法のプログラム。
10. 自ノードの親ノードが故障した場合には、前記実質的なコンピュータに、自ノードを前記代理ノードとして指定させることを特徴とする請求項７から９のいずれか１項記載のネットワーク再構成方法のプログラム。
11. 自ノードが前記未接続の部分木に属する場合、前記実質的なコンピュータに、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出させることを特徴とする請求項７から１０のいずれか１項記載のネットワーク再構成方法のプログラム。
12. 前記未接続の部分木に属する他のノードも前記無線ツリーネットワークとの接続性を有する場合には、前記実質的なコンピュータに、前記基地局までのホップ数が最小の場合にのみ自ノードを前記部分木の新たなルートとさせることを特徴とする請求項７から１１のいずれか１項記載のネットワーク再構成方法のプログラム。
13. 請求項７から１２のいずれか１項記載のネットワーク再構成方法のプログラムが記録されたコンピュータが読み取り可能な情報記録媒体。
14. 無線通信方式で基地局と接続されて無線ツリーネットワークを構成するノードであって、
    前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定する手段と、
    前記代理ノードとして指定された場合に、自ノードの子孫ノードに対して前記無線ツリーネットワークとの接続性の有無の確認を要求する手段と、
    前記無線ツリーネットワークとの接続性の有無を確認する手段と、
    自ノードが前記未接続の部分木に属する場合に、前記代理ノードからの指示に応じて、前記無線ツリーネットワークとの接続性を有するノードが新たなルートとなるように該未接続の部分木の階層構造を変更する手段と、
    自ノードが前記未接続の部分木の新たなルートとなった場合に、自ノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知する手段とを有することを特徴とするノード。
15. 自ノードが前記無線ツリーネットワークから削除される場合には、子ノードを前記代理ノードとして指定することを特徴とする請求項１４記載のノード。
16. 自ノードが前記無線ツリーネットワークへ追加される場合には、自ノードを前記代理ノードとして指定することを特徴とする請求項１４又は１５記載のノード。
17. 自ノードの親ノードが故障した場合には、自ノードを前記代理ノードとして指定することを特徴とする請求項１４から１６のいずれか１項記載のノード。
18. 自ノードが前記未接続の部分木に属する場合、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出することを特徴とする請求項１４から１７のいずれか１項記載のノード。
19. 前記未接続の部分木に属する他のノードも前記無線ツリーネットワークとの接続性を有する場合には、前記基地局までのホップ数が最小の場合にのみ前記部分木の新たなルートとなることを特徴とする請求項１４から１８のいずれか１項記載のノード。
20. 無線通信方式で接続された少なくとも一つのノードとともに無線ツリーネットワークを構成する基地局であって、
    前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定する手段と、
    階層構造が変更された前記未接続の部分木に属するいずれかのノードから、変更後の前記未接続の部分木の階層構造に関する情報を受信した場合に、該受信した情報に応じて前記ツリーネットワークの階層構造を表す情報を更新する手段とを有することを特徴とする基地局。
21. 請求項１４から１９のいずれか１項記載のノードを少なくとも一つと、請求項２０記載の基地局とを有することを特徴とするマルチホップネットワークシステム。

Images