ネットワーク再構成方法、プログラム、情報記録媒体、ノード、基地局、マルチホップネットワークシステム
【課題】 無線ツリーネットワークの部分的再構成に要する時間を短縮する。
【解決手段】 ノードの削除、ノード故障、ノード追加によってツリーネットワークから未接続となった部分木のルートをイニシエータに指定し(ステップP1)、基地局の代理として未接続の部分木を制御させる。イニシエータはNeighbor Discoveryの実施、又は子孫ノードへのNeighbor Discovery実行の指示を出すことで、未接続の部分木とツリーネットワークとの接続性を検出する(ステップP2)。その結果、未接続の部分木はツリーネットワークとの接続性に応じて階層構造を変更し(ステップP3)、ツリーネットワークへ再接続する処理を行う(ステップP4)。
【解決手段】 ノードの削除、ノード故障、ノード追加によってツリーネットワークから未接続となった部分木のルートをイニシエータに指定し(ステップP1)、基地局の代理として未接続の部分木を制御させる。イニシエータはNeighbor Discoveryの実施、又は子孫ノードへのNeighbor Discovery実行の指示を出すことで、未接続の部分木とツリーネットワークとの接続性を検出する(ステップP2)。その結果、未接続の部分木はツリーネットワークとの接続性に応じて階層構造を変更し(ステップP3)、ツリーネットワークへ再接続する処理を行う(ステップP4)。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、無線センサネットワークにおいてノードの削除、故障、追加時に、ツリーネットワークを部分的に再構成するネットワーク再構成方法に関する。
【背景技術】
【0002】
無線センサネットワークとは、温度や湿度の環境情報などを分散配置されたセンサノード(以下、ノード)でセンシングし、その結果をノードによって構成されたネットワークによって基地局に集め、統計分析や異常検出通知に活用するネットワークシステムである。
【0003】
無線センサネットワークにおいては、ツリーネットワークを前提とし、ノードの初期設置時に基地局をルートとしたツリーネットワークが構成される。
【0004】
ツリーネットワークを構成する方法として、非特許文献1に開示される方法がある。非特許文献1に開示されるルーティングは次のようなものである。
基地局は、各ノードに検出信号を順次送信する。各ノードは検出信号の受信強度がしきい値以上であるか否かを判断し、所定の強度以上で検出信号を受信したノードのみが検出応答信号を基地局へ返信する。
これにより、基地局と検出応答信号を返信したノードとの接続が確立される。
【0005】
次に、基地局は、未だ接続が確立していない各ノードに対して既に接続が確立されたノードを介して検出信号を順次発信する。各ノードは検出信号の受信強度がしきい値以上であるか否かを判断し、所定の強度以上で検出信号を受信したノードのみが検出応答信号を検出信号の送信元であるノードを介して基地局へ返信する。
【0006】
これにより、基地局と直接は接続できなかったノードは、基地局と直接接続されたノードを介して基地局へ接続される。
【0007】
以上の手順を繰り返すことにより、ツリーネットワークが構成される。
【0008】
非特許文献1に記載の手順は、基地局がノードの信号送信タイミングを集中制御するため、信号衝突を低減でき、ノード数が多い場合でも安定してツリーネットワークを構成できる。
【0009】
一方、運用中にツリーネットワークの再構成が必要となる場合がある。これは、不要になったノードを削除する場合や、ノードが故障した場合や、新しいノードを追加する場合である。
【0010】
ノードを削除する場合を例として説明する。図1に、基地局をルートとして、ノード1〜ノード14で構成されるツリーネットワーク30を示す。
【0011】
ここで、ノード4が削除されるものとする。ノード4が削除されると、ノード4をルートとする部分木に属するノード、すなわちノード7、ノード11、ノード12及びノード14は、ツリーネットワーク30との接続を失って未接続ノードとなる。
【0012】
同様に、ノードが故障した場合には、故障したノードをルートとした部分木に属するノードは未接続ノードとなる。また、ノードを追加する場合には、追加されるノード自体が未接続ノードとなる。
【0013】
このような場合、ツリーネットワークを再構成することで、未接続ノードをツリーネットワークに再接続する必要が生じる。その際には、できるだけ短時間でツリーネットワークを再構成する必要がある。これは、運用中のサービスの停止時間を最小限に留める必要があるからである。
【0014】
図24に、従来の再接続の手法を示す。従来は、非特許文献1に記載の手順で、基地局から未接続ノードを一つずつ再検出し、ツリーネットワークを再構成する方法が用いられていた。換言すると、全てのノードを検出するか、全てのノードを経由して検出を行うまで、非特許文献1に記載の手順を繰り返していた。
【0015】
また、従来のネットワーク再構成方法に関する別の例としては、特許文献1に開示される「マルチホップ無線ネットワークおよび無線局」がある。特許文献1に開示される発明は、各無線局が最適な接続先(上位接続先無線局)を見つけることにより、各無線局が自律的に無線ネットワークを構成するものである。
【特許文献1】特開2001−237764号公報
【非特許文献1】大熊孝裕、川崎大輔、保木本武宏、新井正伸著、「呼出しIDによる省電力マルチホップルーティング機能の実現」、信学技報、Vol.103,No.624,平成16年1月22日、39〜42ページ
【発明の開示】
【発明が解決しようとする課題】
【0016】
非特許文献1に記載の手法を用いる場合の問題点は、ツリーネットワークの再構成に非常に時間がかかることである。その理由は、基地局から未接続ノードを一つずつ検出して、ツリーネットワークに再接続していくからである。
上記のように、ツリーネットワークの再構成は、できるだけ短時間で行う必要がある。非特許文献1に記載の発明は、この要求を十分に満たすものであるとはいえない。
【0017】
また、特許文献1に記載の発明は、ある無線局が上位接続先無線局と接続できなくなった場合には、それより下位の無線局(子無線局)が順次上位接続先無線局の選定動作を行う。このため、無線局の数が多いとネットワーク再構成に要する時間が長期化してしまうこととなる。
【0018】
このように、従来は、短期間でツリーネットワークを確実に再構成することはできなかった。
【0019】
本発明は係る問題に鑑みてなされたものであり、短時間で確実にツリーネットワークを再構成できるネットワーク再構成方法及びそのプログラム並びにそれが記録されたコンピュータが読み取り可能な情報記録媒体、並びにノード、基地局、及びマルチホップネットワークシステムを提供することを目的とする。
【課題を解決するための手段】
【0020】
上記目的を達成するため、本発明は、第1の態様として、基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法であって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定するステップと、代理ノードが、自ノード又は子孫ノードと無線ツリーネットワークとの接続性を検出するステップと、ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、ツリーネットワークとの接続性を有するノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを有することを特徴とするネットワーク再構成方法を提供するものである。
【0021】
本発明の第1の態様においては、無線ツリーネットワークからノードを削除する際に、削除するノードの子ノードを代理ノードとして指定することが好ましい。また、無線ツリーネットワークへノードを追加する際に、追加するノードを代理ノードとして指定することが好ましい。また、無線ツリーネットワークに属するノードが故障した際に、故障したノードの子ノードを代理ノードとして指定することが好ましい。
【0022】
本発明の第1の態様の上記のいずれの構成においても、無線ツリーネットワークとの接続性を検出するステップにおいては、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出することが好ましい。
【0023】
また、本発明の第1の態様の上記のいずれの構成においても、無線ツリーネットワークとの接続性を検出するステップにおいて無線ツリーネットワークとの接続性を有するノードが複数検出された場合には、基地局までのホップ数が小さいものを部分木のルートとして設定することが好ましい。
【0024】
また、上記目的を達成するため、本発明は、第2の態様として、基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法をノードに実行させるプログラムであって、ノードを制御する実質的なコンピュータに、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定するステップと、代理ノード又はその子孫ノードと無線ツリーネットワークとの接続性を検出するステップと、ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、ツリーネットワークとの接続性を有するノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを実行させることを特徴とするネットワーク再構成方法のプログラムを提供するものである。
【0025】
本発明の第2の態様においては、自ノードが無線ツリーネットワークから削除される場合には、実質的なコンピュータに、子ノードを代理ノードとして指定させることが好ましい。また、自ノードが無線ツリーネットワークへ追加される場合には、実質的なコンピュータに自ノードを代理ノードとして指定させることが好ましい。また、自ノードの親ノードが故障した場合には、実質的なコンピュータに、自ノードを代理ノードとして指定させることが好ましい。
【0026】
本発明の第2の態様の上記のいずれの構成においても、自ノードが未接続の部分木に属する場合、実質的なコンピュータに、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出させることが好ましい。
【0027】
また、未接続の部分木に属する他のノードも無線ツリーネットワークとの接続性を有する場合には、実質的なコンピュータに、基地局までのホップ数が最小の場合にのみ自ノードを部分木の新たなルートとさせることが好ましい。
【0028】
また、上記目的を達成するため、本発明は、第3の態様として、上記本発明の第2の態様のいずれかの構成にかかるネットワーク再構成方法のプログラムが記録されたコンピュータが読み取り可能な情報記録媒体を提供するものである。
【0029】
また、上記目的を達成するため本発明は、第4の態様として、無線通信方式で基地局と接続されて無線ツリーネットワークを構成するノードであって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定する手段と、代理ノードとして指定された場合に、自ノードの子孫ノードに対して無線ツリーネットワークとの接続性の有無の確認を要求する手段と、無線ツリーネットワークとの接続性の有無を確認する手段と、自ノードが未接続の部分木に属する場合に、代理ノードからの指示に応じて、無線ツリーネットワークとの接続性を有するノードが新たなルートとなるように該未接続の部分木の階層構造を変更する手段と、自ノードが未接続の部分木の新たなルートとなった場合に、自ノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知する手段とを有することを特徴とするノードを提供するものである。
【0030】
本発明の第4の態様においては、自ノードが無線ツリーネットワークから削除される場合には、子ノードを代理ノードとして指定することがこのましい、また、自ノードが無線ツリーネットワークへ追加される場合には、自ノードを代理ノードとして指定することが好ましい。また、自ノードの親ノードが故障した場合には、自ノードを代理ノードとして指定することが好ましい。
【0031】
本発明の第4の態様の上記のいずれの構成においても、自ノードが未接続の部分木に属する場合、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出することがこのましい。
【0032】
本発明の第4の態様の上記のいずれの構成においても、未接続の部分木に属する他のノードも無線ツリーネットワークとの接続性を有する場合には、基地局までのホップ数が最小の場合にのみ部分木の新たなルートとなることが好ましい。
【0033】
また、上記目的を達成するため、本発明は、第5の態様として、無線通信方式で接続された少なくとも一つのノードとともに無線ツリーネットワークを構成する基地局であって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定する手段と、階層構造が変更された未接続の部分木に属するいずれかのノードから、変更後の未接続の部分木の階層構造に関する情報を受信した場合に、該受信した情報に応じてツリーネットワークの階層構造を表す情報を更新する手段とを有することを特徴とする基地局を提供するものである。
【0034】
また、上記目的を達成するため、本発明は、第6の態様として、上記本発明の第4の態様のいずれかの構成にかかるノードを少なくとも一つと、上記本発明の第5の態様にかかる基地局とを有することを特徴とするマルチホップネットワークシステムを提供するものである。
【発明の効果】
【0035】
本発明によれば、短時間で確実にツリーネットワークを再構成できるネットワーク再構成方法及びそのプログラム並びにそれが記録されたコンピュータが読み取り可能な情報記録媒体、並びにノード、基地局、及びマルチホップネットワークシステムを提供できる。
【発明を実施するための最良の形態】
【0036】
〔発明の原理〕
本発明では、ノードをツリーネットワークに再接続する処理を図1に示すように四つのステップに分けて行う。
第1のステップ(イニシエータ指定処理)では、基地局の代理となってツリーネットワークの再構成を制御する「イニシエータ」を指定する。このステップにおける処理によって、ノードの削除や故障によってツリーネットワークに未接続となった部分木(以下、未接続の部分木)のルートがイニシエータに指定される。
【0037】
第2のステップ(Neighbor Discovery処理)では、ツリーネットワークとの接続性を検出するために、イニシエータがNeighbor Discoveryを実施するか、又は、イニシエータの子孫ノードがイニシエータからの指示に応じてNeighbor Discoveryを実施する。このステップにおける処理により、未接続の部分木に属するいずれかのノードと、ツリーネットワークとの接続性を検出する。
【0038】
第3のステップ(部分木階層構造更新処理)では、Neighbor Discoveryによって検出したツリーネットワークとの接続性に応じて、未接続の部分木の階層構造を更新する。このステップにおける処理により、Neighbor Discoveryに成功したノードが、新しく未接続の部分木のルートとなるように階層構造を更新する。
【0039】
第4のステップ(部分木再接続処理)では、未接続の部分木を再びツリーネットワークに接続する。このステップにおける処理により、未接続の部分木が再びツリーネットワークに接続される。
【0040】
ツリーネットワークの再構成が必要となる契機は、上記のように、ノードを削除する場合、ノードが故障した場合及びノードを追加する場合であるが、上記のイニシエータ指定処理は再構成の契機によって手順が異なる。Neighbor Discovery処理、部分木階層構造更新処理及び部分木再接続処理は、全ての契機で共通する処理である。
ノード削除時、ノード故障時及びノード追加時のそれぞれの場合のイニシエータ指定処理については後段で詳細に説明する。
【0041】
ツリーネットワークを再構成する際に、従来の手法のように基地局(ルート)から順に未接続ノードの再接続を試みるのではなく、イニシエータ指定処理でイニシエータを指定し、Neighbor Discovery処理で未接続の部分木に属するいずれかのノードとツリーネットワークとの接続性をイニシエータがNeighbor Discoveryによって検出する。そして、部分木階層構造更新処理では、Neighbor Discovery処理での検出結果に応じて、未接続の部分木の階層構造を更新し、部分木再接続処理で未接続の部分木とツリーネットワークとを再接続する。
【0042】
これにより、ノードのルーティングテーブルの更新数を低減でき、結果としてツリーネットワークの再構成に要する時間を短縮できる。
【0043】
以下、上記原理に基づく本発明の好適な実施の形態について説明する。
【0044】
〔第1の実施形態〕
本発明を好適に実施した第1の実施形態について説明する。
図2に、基地局をルートとしてノード1〜ノード14によって構成されるツリーネットワークを示す。
各ノードは、図3に示すルーティングテーブルを有する。ルーティングテーブルは、親ノード、子孫ノードの情報を含む。すなわち、自ノードをルートとする部分木の構成と、親ノードとの情報を含む。
【0045】
基地局及び各ノードが送受信する信号の種類を図4に示す。
【0046】
図5に、ツリーネットワークに適用されるノードの構成を示す。
ノード500は、入力部501、出力部502、イニシエータ指示/実施部503、Neighbor Discovery指示/実施部504、部分木階層構造更新部505、記憶部506、ルーティング処理部507及び部分木追加部508を有する。
【0047】
入力部501は、“ノード削除信号”、“ノード故障信号”、“イニシエータ指示信号”、“更新開始信号”、“更新開始指示信号”、“Neighbor Discovery指示信号”、“Neighbor Discovery成功信号”、“Neighbor Discovery失敗信号”、“更新信号”、“追加信号”、“更新完了信号”、“更新完了指示信号”などを入力として受け付ける。
また、入力部501は、ノード削除時及びノード追加時に、後述するイニシエータ指示/実施部503が動作を開始するための“削除開始信号”及び“追加開始信号”を受信する。
【0048】
出力部502は、これらの信号を他のノード500や基地局600に対して送信する。
【0049】
イニシエータ指示/実施部503の機能について説明する。
まず、ノード削除時の動作に関する機能ついて説明する。イニシエータ指示/制御部503は、ノード削除時には、以下のような動作を行う。
・入力部501が“削除開始信号”を受信すると、出力部502に“更新開始信号”を送信させる。
・入力部501が“更新開始信号”を受信すると、自ノードを運用状態から経路更新状態へ移行させ、Neighbor Discoveryに応答しないようにする。
・自ノードが削除ノードであるならば、全ての子孫ノードに“更新開始信号”を送信した後、“ノード削除信号”に自ノードのID情報を含めて、出力部502によって親ノードへ送信する。
・入力部501が“ノード削除信号“を受信すると、記憶部506に保持しているルーティングテーブルから、削除ノードをルートとする部分木を削除する。また、出力部502に親ノードへ“ノード削除信号”を送信させる。
・自ノードが削除ノードであるならば、親ノードに対して“ノード削除信号”を送信した後、出力部502に“イニシエータ指示信号”を送信させる。
・入力部501が“イニシエータ指示信号”を受信した場合には、自ノードをイニシエータとし、後述するNeighbor Discoveryを実行する。
【0050】
ノード故障時のイニシエータ指定/実施部503の動作に関する機能について説明する。イニシエータ指示/制御部503は、ノード故障時には以下のような動作を行う。
・故障を発見したノードであるならば、記憶部506に保持している故障ノードをルートとする部分木を、記憶部506に保持しているルーティングテーブルから削除する。そして、“ノード故障信号”を故障発見ノード(すなわち、故障ノードの親ノードと基地局との間にあるノード)へ送信する。
・入力部501が“更新開始指示信号”を受信すると、記憶部506に保持している部分木から故障ノードをルートとする部分木を削除する。
・入力部501が“更新開始指示信号“を受信すると、出力部502に全子孫ノードに対して“更新開始信号”を送信させる。
・全子孫ノードに対して“更新開始信号”を送信した後、「全ての子孫ノードに対して“更新開始信号”を送信したこと」を示す“通知完了信号”を、出力部502から基地局へ送信させる。
・入力部501が“イニシエータ指示信号”を受信すると、自ノードをイニシエータとする。
【0051】
ノード追加時のイニシエータ指定/実施部503の動作に関する機能について説明する。イニシエータ指定/制御部503は、ノード追加時には以下のような動作を行う。
・入力部501が“追加開始信号”を受信すると、自ノードをイニシエータとする。
【0052】
Neighbor Discovery指示/実施部504について説明する。Neighbor Discovery指示/実施部504では、自ノードがイニシエータであるならば、Neighbor Discoveryを実行する。また、イニシエータは、子孫ノードに対して“Neighbor Discovery指示信号”を送信する。
“Neighbor Discovery指示信号”を受信したノードは、Neighbor Discoveryを実施する。Neighbor Discoveryに成功した場合はその結果を記憶部506に保存し、イニシエータに対して“Neighbor Discovery成功信号”を送信する。Neighbor Discoveryに成功したノードは、新しく部分木のルートとなる(以下、新ルートノード)。
Neighbor Discoveryに失敗した場合は、イニシエータに“Neighbor discovery失敗信号”を送信する。
【0053】
部分木階層構造更新部505について説明する。
部分木階層構造更新部505は、Neighbor Discoveryの結果に応じて、イニシエータをルートとして更新した部分木の階層構造をルーティングテーブルに反映させる。
入力部501から“Neighbor Discovery成功信号”を受信すると、イニシエータは自ノードのルーティングテーブルを更新する。そして、そのルーティングテーブルと新しいルートノードの情報とを“更新情報”に含め、出力部502に新しい親ノードへ送信させる。
ここで、新しい親ノードは、旧ルーティングテーブルにおいて、新ルートノードを子孫として持つ子ノードが選択される。
【0054】
入力部501から“更新信号”を受信すると、これに含まれる新ルートノードを旧ルーティングテーブルで子孫ノードとして持つ子ノードを新しい親ノードとする。また、“更新信号”に含まれる部分木情報を、ルーティングテーブルに追加する。
そして、自ノードのルーティングテーブルと新しいルートノードとの情報を“更新信号”ともに親ノードへ送信する。
【0055】
新ルートノードが入力部501によって“更新信号”を受信すると、これに含まれるルーティングテーブルを自ノードのルーティングテーブルに追加する。また、Neighbor Discoveryで検出したノードを新しい親ノードにする。
【0056】
部分木追加部506について説明する。
新ルートノードでは、出力部502によって、自ノードのルーティングテーブルを“追加信号”とともに親ノードへ送信する。
“追加信号”を受信したノードでは、“追加信号”に含まれるルーティングテーブルの情報を自ノードのルーティングテーブルに追加する。そして、受信した”追加信号”の内容を出力部502を用いて親ノードへ送信する。
入力部501によって“更新完了信号”を受信した新ルートノードは、全子孫ノードへ“更新完了信号”を出力部502から送信する。“更新完了信号”を受信したノードは、経路更新状態から運用状態へと移行する。
【0057】
記憶部506は、ルーティングテーブルNeighbor Discoveryの結果などを保持する。
【0058】
ルーティング処理部507は、後述するノード故障時に非特許文献1に開示される手法を利用して、仮経路を作成する際に用いられる。
【0059】
図6に、基地局600の構成を示す。
基地局600は、入力部601,出力部602、イニシエータ指示/実施部603、記憶部606、ルーティング処理部607及び部分木追加部608を有する。
入力部601は、“ノード削除信号”、“ノード故障信号”、“追加信号”、“追加完了信号”などを入力として受け付ける。
【0060】
イニシエータ指示/実施部603の機能について説明する。
入力部601によって“ノード削除信号”を受信すると、記憶部606に保持しているルーティングテーブルから削除ノードをルートとする部分木を削除する。
入力部601によって“ノード故障信号”を受信すると、記憶部606に保持しているルーティングテーブルから故障ノードをルートとする部分木を削除する。また、出力部602を用いて、故障ノードの子ノードへ“更新開始指示信号”を送信する。
入力部601によって“通知完了信号”を受信すると、“イニシエータ指示信号”を故障ノードの子ノードへ出力部602を用いて出力する。
【0061】
部分木追加部608の機能について説明する。
入力部601によって“追加信号”を受信した基地局は、“追加信号”に含まれるルーティングテーブルの情報を、自ノードのルーティングテーブルに追加する。そして、基地局のルーティングテーブル更新が完了したことを示す“更新完了信号”を新ルートノードに対して出力部602によって送信する。
【0062】
記憶部606は、ルーティングテーブルやNeighbor Discoveryの結果などを保持する。
【0063】
ルーティング処理部607は、後述するノード故障時に非特許文献1に開示される手法を利用して、仮経路を作成する際に用いられる。
【0064】
ツリーネットワークの再構成動作について説明する。
まず、イニシエータを指定する手順について説明する。上記のように、イニシエータを指定する手順は、動作開始の契機によって異なるため、それぞれについて個別に説明する。
【0065】
<ノード削除時のイニシエータ指定手順>
最初にノード削除時のイニシエータの指定手順について説明する。図7にノード削除時のイニシエータの指定動作の流れを示す。
削除ノードは“削除開始信号”を受信すると(ステップB1)、全子孫ノードに“更新開始信号”を送信する(ステップB2)。“更新開始信号”を受信したノードは、図8に示すように運用状態から経路更新状態へと移行する。
【0066】
次に、削除ノードは、削除ノードから基地局までの間にあるノードに対して“ノード削除信号”を送信する(ステップB3)。“ノード削除信号”を受信したノードは、削除ノードをルートとする部分木をルーティングテーブルから削除する。
【0067】
削除ノードは、子ノードにイニシエータ動作を指示する“イニシエータ指示信号”を送信する(ステップB4)。“イニシエータ指示信号”を受信したノードは、イニシエータとなり、後述するNeighbor Discoveryの実行などを制御する(ステップB5)。
【0068】
<ノード故障時のイニシエータ指定手順>
次に、ノード故障時のイニシエータの指定手順について説明する。図9に、ノード故障時のイニシエータ指定動作の流れを示す。ノード故障時には、故障したノード(故障ノード)を発見したノード(すなわち、故障ノードの親ノード)が、故障ノードをルートとした部分木を自ノードのルーティングテーブルから削除する。そして、故障ノードの親ノードと基地局との間にある各ノードに対し、故障ノードの発生を通知する“ノード故障信号”を送信する(ステップC1)。“ノード故障信号”を受信したノードは、故障ノードをルートとする部分木をルーティングテーブルから削除する。
【0069】
ノード削除時と同様に、ノード故障時も、故障ノードの子ノードに”更新開始信号”と”イニシエータ指示信号”とを送信する必要がある。しかし、故障ノードの子ノードへの経路は存在しないため、基地局は故障ノードの子ノードへの仮経路を非特許文献1に開示される手法を応用して作成する(ステップC2)。
【0070】
この際には、非特許文献1に開示される手法を利用して、故障ノードの子ノードをルートとした部分木に属するいずれかのノードを検出する。これにより、ツリーネットワークと故障したノードをルートとした部分木に属するいずれかのノードとの間に仮経路を形成できる。
このとき、検出されたノードを経由ノードと呼ぶ。基地局は、この仮経路を使用して、故障ノードの子ノード宛に“更新開始指示信号”や”イニシエータ指示信号”を送信する(ステップC3)。その際に、経由ノードのIDを信号に含める。
故障ノードをルートとした部分木に属するノードは、自ノード宛ではない”更新開始指示信号”や”イニシエータ指示信号”を親ノードへ転送する。
【0071】
このようにすることで、“更新開始指示信号”や“イニシエータ指示信号”を故障ノードの子ノードへ送達できる(ステップC4)。
【0072】
また、故障ノードの子ノードは、“通知完了信号”を基地局へ送信するが、“更新開始指示信号”に含まれた経由ノードへ先ず送信する。“更新完了信号”を受信した経由ノードは、仮経路を利用して、受信した信号を基地局へ転送する(ステップC5)。
【0073】
以上の手順で、イニシエータが指定されるまで、基地局と故障ノードの子ノードとは仮経路を使用して通信する。
【0074】
基地局は仮経路を利用して、故障ノードの子ノード及び、故障ノードの子ノードの子孫ノードへ“更新開始指示信号”を送信する。“更新開始指示信号”を受信した故障ノードの子ノードは、全子孫ノードに対して“更新開始信号”を送信する。
【0075】
故障ノードの子ノードは、全子孫ノードに“更新開始信号”を送信したことを”通知完了信号”によって基地局に通知する。
【0076】
基地局は、故障ノードの子ノードから“通知完了信号”を受信すると、仮経路を利用して“イニシエータ指示信号”を故障ノードの子ノードへ送信する(ステップC6)。
【0077】
イニシエータ指示信号を受信した故障ノードの子ノードは、仮経路を削除するために、“仮経路削除信号“を、削除ノードと基地局との間にある各ノードへ送信する(ステップC7)。これにより、仮経路は削除される。
【0078】
イニシエータとなったノードは(ステップC8)、後述するNeighbor Discoveryの実行などを制御する。
【0079】
<ノード追加時の基地局の動作>
ノード追加時の基地局の動作について説明する。図10に、ノード追加時の基地局の動作の流れを示す。
“追加開始信号”を受信したノードは(ステップF1)、イニシエータとなる(ステップF2)。
【0080】
以上のようにして、ノード削除時、ノード故障時、ノード追加時にイニシエータが指定される。
【0081】
次に、イニシエータのNeighbor Discovery実施・指示の動作について説明する。図11、図12及び図13に、Neighbor Discovery実施・指示動作の流れを示す。イニシエータは、先ず自らがNeighbor Discoveryを実施し、ツリーネットワークとの新しい接続性検出を試みる(ステップD1)。ここで、Neighbor Discoveryが検出された場合は(ステップD2/Yes)、イニシエータは検出したノードを新しい親ノードに選択し、ルーティングテーブルを更新する。
【0082】
もし、イニシエータがNeighbor Discoveryに失敗した場合は(ステップD2/No)、イニシエータとのホップ数が小さい子孫ノードから順番に、“Neighbor Discovery指示信号”を送信し、子孫ノードがNeighbor Discoveryを実施する(ステップD3)。
【0083】
子孫ノードがNeighbor Discoveryに成功した場合は(ステップD4/Yes)、イニシエータをルートとした部分木を、Neighbor Discoveryに成功した子孫ノード(以下、新ルートノード)が新しい部分木のルートとなるように階層構造を変更する(ステップD6)。ここで、階層構造の変更に伴い、新ルートノードとイニシエータとの間でルーティングテーブルを更新する(ステップD6〜D12)。
【0084】
イニシエータは、新しい部分木の情報をルーティングテーブルに追加することを要求する“追加信号”を、新ルートノードと基地局(基地局も含む)の経路にあるノードに対して送信する(ステップD13〜D16)。これにより、新ルートノードと基地局との経路にある各ノードのルーティングテーブルが更新される。また、“追加信号“を受信した基地局は、“更新完了通知“を新ルートノードへ送信する(ステップD17)。基地局からの“更新完了通知”を受信した新ルートノードは、経路変更が完了したことを示す“更新完了通知”を全子孫ノードに送信する(ステップD18)。“更新完了通知”を受信したノードの状態は、経路更新状態から運用状態へと移行する。
【0085】
〔動作例1〕
図2に示したツリーネットワーク30において、ノード4が削除されるものとする。
まず、ノード4は、“削除開始信号”を受信すると、全ての子孫ノード、つまり、ノード7,ノード11、ノード14及びノード12に対して“更新開始信号”を送信する。
図8に示すように、更新開始信号を受信したノードは、運用状態から経路更新状態へと移行する。経路更新状態のノードは、基地局までの到達性を持たないため、Neighbor Discoveryに対してリプライを返さない。
【0086】
次に、ノード4は、自ノードから基地局までの経路にあるノード、すなわちノード1及び基地局に対して“ノード削除信号”を送信する。“ノード削除信号”を受信したノード(ノード1及び基地局)は、削除ノード(ノード4)をルートとする部分木の情報をルーティングテーブルから削除する。この時、ノード1と基地局とのルーティングテーブルを図14に示す。
【0087】
次に、ノード4は、子ノードであるノード7に“イニシエータ指示信号”を送信する。これにより、ノード7はイニシエータとなる。
【0088】
イニシエータとなったノード7は、まず自らがNeighbor Discoveryを実施し、ツリーネットワーク30との新しい接続性検出を試みる。
【0089】
以下、イニシエータであるノード7におけるNeighbor Discoveryが成功した場合を例として説明する。
Neighborが検出された場合は、ノード7は検出したノードを新しい親ノードに選択し、ルーティングテーブルを更新する。ここでは、ノード3がNeighborとして検出されたものとする。この時の、ノード7のルーティングテーブルを図15に示す。
【0090】
次に、ノード7は、自ノードと基地局との間のノード、すなわち、ノード3、ノード1及び基地局に“追加信号”を送信する。“追加信号”には、自ノードのルーティングテーブル情報が付加される。“追加信号”を受信したノード3、ノード1及び基地局は、ノード7をルートとする部分木の情報をルーティングテーブルに追加する。この時のノード3、ノード1及び基地局のルーティングテーブルは図16のようになる。
【0091】
このようにして、ノード7から基地局までの経路にある各ノードのルーティングテーブルが更新される。最後に、イニシエータであるノード7は、全ての子孫ノード、すなわちノード11、ノード14及びノード12へ“更新完了信号”を送信する。
“更新完了信号”を受信したノードは、経路更新状態から運用状態へと移行する。
【0092】
次に、イニシエータであるノード7におけるNeighbor Discoveryが失敗した場合について説明する。
イニシエータであるノード7がNeighbor Discoveryに失敗した場合は、イニシエータは、ホップ数が小さい子孫ノードから順番に“Neighbor Discovery指示信号”を送信し、子孫ノードにNeighbor Discoveryを実施させる。ここでは、ノード11→ノード12→ノード13の順番でNeighbor Discoveryの指示を出すものとする。
【0093】
子孫ノードがNeighbor Discoveryを実行する場合の具体例として、ノード11及びノード12がNeighbor Discoveryに失敗し、ノード14がNeighbor Discoveryに成功した場合について説明する。
イニシエータであるノード7は、ノード11にNeighbor Discovery指示信号を送信する。“Neighbor Discovery指示信号”を受信したノード11は、Neighbor Discoveryを実行する。ノード11は、Neighbor Discoveryを実行した結果、ノードを検出できなかったため、“Neighbor Discovery失敗信号”をノード7へ送信する。
【0094】
ノード7は、次に、ノード12に対して“Neighbor Discovery指示信号”を送信する。“Neighbor Discovery指示信号”を受信したノード12は、Neighbor Discoveryを実行する。ノード12は、Neighbor Discoveryを実行した結果、ノードを検出できなかったため、“Neighbor Discovery失敗信号”をノード7へ送信する。
【0095】
ノード7は、次に、ノード14に“Neighbor Discovery指示信号を送信する。“Neighbor Discovery指示信号”を受信したノード14は、Neighbor Discoveryを実行する。ノード14はNeighbor Discoveryを実行した結果、ノード9を検出する。ノード14は、検出したNeighborを保持し、イニシエータであるノード7へ“Neighbor Discovery成功信号”を送信する。
【0096】
ノード14からの“Neighbor Discovery成功信号”を受信したオード7は、ノード7をルートとする部分木を、ノード14がルートとなるように階層構造を変更する。
【0097】
ノード7にとって、ノード14を子孫ノードに持つ子ノードは、ノード11である。従って、ノード11がノード7の新しい親ノードとなる。また、ノード11をルートとする部分木をルーティングテーブルから削除する。この時の、ノード7のルーティングテーブルを図17に示す。
【0098】
ノード7は、更新したルーティングテーブルと新ルートノードのID情報とを“更新情報”とともに親ノードであるノード11へ送信する。
【0099】
“更新信号”を受信したノード11は、子孫ノードであるノード14を新しい親ノードとする。また、ノード14をルートとする部分木をルーティングテーブルから削除する。そして、受信した“更新信号”の情報をルーティングテーブルに追加する。この時のノード11のルーティングテーブルを図18に示す。
【0100】
ノード11は、更新したルーティングテーブルと新ルートノードのID情報とを、“更新情報”とともに親ノードであるノード14へ送信する。
【0101】
“更新情報”を受信したノード14は、受信した“更新信号”に含まれるルーティングテーブルの情報を、自ノードのルーティングテーブルに追加する。
【0102】
また、ノード14は、Neighbor Discoveryで検出したノード9を親ノードとして設定する。この時のノード14のルーティングテーブルを図19に示す。
【0103】
ノード14は、自ノードと基地局との経路にあるノード(基地局を含む)、すなわち、ノード9、ノード6、ノード3、ノード1及び基地局に対して“追加信号”を送信する。これにより、ノード14と基地局との経路にある各ノードのルーティングテーブルが更新される。この時のノード9、ノード6、ノード3、ノード1及び基地局のルーティングテーブルを図20に示す。
【0104】
受信した“追加信号”に応じてルーティングテーブルを更新した基地局は、“更新完了信号”をノード14へ送信する。
【0105】
“更新完了信号”を受信したノード14は、全子孫ノード、すなわち、ノード11、ノード7及びノード12に“更新完了信号”を送信する。“更新完了信号”を受信したノードは、経路変更状態から運用状態へと移行する。
【0106】
以上でノード削除時の動作を完了する。上記動作において再構成されたツリーネットワークを図21に示す。
【0107】
〔動作例2〕
ツリーネットワークを構成するノードが故障した場合の動作について説明する。上記動作例1は、ツリーネットワークからノードを削除する場合のものであったが、ノード削除時の動作と、ノード故障時又はノード追加時の動作との差分は、イニシエータ指定の動作である。従って、イニシエータ指定の動作のみを説明する。
【0108】
図2に示したツリーネットワーク30において、ノード4が故障したものとする。
【0109】
ノード故障の場合は、ノード故障を発見したノード、すなわち故障したノード(ノード4)の親ノードであるノード1が、ノード4をルートとする部分木を自ノードのルーティングテーブルから削除する。そして、ノード1から基地局までの経路にあるノード(すなわち基地局)に対して“ノード故障信号”を送信する。“ノード故障信号“を受信した基地局は、故障ノードであるノード4をルートとする部分木の情報をルーティングテーブルから削除する。この時のノード1及び基地局のルーティングテーブルを図22に示す。
【0110】
“ノード故障信号”を受信した基地局は、非特許文献1に開示される手法を用いて、基地局とノード7との間に仮経路を作成する。例えば、ノード14の子孫ノードであるノード12をノード13から検出したとする。この場合、以降の“更新開始指示信号”、“通知完了信号”、“イニシエータ指示信号”は仮経路を利用して送受信される。ノード7が、“イニシエータ指示信号”を受信してイニシエータとなると、“仮経路削除信号”をノード7→ノード12→ノード13→ノード8→ノード5→ノード2→基地局へ送信し、仮経路を削除する。
【0111】
基地局は仮経路を利用して、“更新開始指示信号”をノード7へ送信する。“更新開始信号”を受信したノード7は、全子孫ノード、すなわちノード11、ノード14及びノード12に対して“更新開始信号”を送信する。そして、ノード7は、“通知完了信号”を基地局に通知する。
【0112】
基地局は、ノード7から“通知完了信号”を受信すると、仮経路を利用して、“イニシエータ指示信号”をノード7へ送信する。“イニシエータ指示信号”を受信したノード7は、仮経路削除要求を基地局に対して送信する。そして、イニシエータとなり、Neighbor Discoveryの実行などを制御する。
【0113】
〔動作例3〕
ノードを追加する場合は、“ノード追加信号”を受信すると、追加ノード自身がイニシエータとなる。イニシエータの指定以外の手順については上記動作例1と同様である。
【0114】
本実施形態に係るツリーネットワークにおいては、ツリーネットワークの再構成時に、ノードのルーティングテーブルの更新数を低減でき、結果としてツリーネットワークの再構成に要する時間を短縮できる。しかも、イニシエータ自身がツリーネットワークとの接続性を有しない場合には、その子孫ノードとツリーネットワークとの接続性を調べ、接続性を有するノードが存在すればそれを新たなルートとしてツリー構造を変更するため、未接続の部分木を確実にツリーネットワークに接続できる。
【0115】
〔第2の実施形態〕
本発明を好適に実施した第2の実施形態について説明する。
図23に、本実施形態におけるネットワーク再構成の動作の流れを示す。
第1の実施形態の動作との違いは、Neighbor Discoveryの結果複数のNeighborが検出された場合に、基地局までのホップ数が最小のノードをNeighborとして選択することである。
【0116】
基地局までのホップ数が最小のノードをNeighborとして選択することで、新ルートノードから基地局までのホップ数が小さくなり、ルーティングテーブルの更新回数を低減できる。
【0117】
これにより、ツリーネットワークの再構成に要する時間をさらに短縮できる。
【0118】
〔第3の実施形態〕
図5及び図6に示した基地局600及びノード500は、専用のハードウェアによって実現する以外に、その機能を実現する為のプログラムをコンピュータが読み取り可能な記録媒体に記録しておき、これをコンピュータに読み取らせて基地局600及びノード500として機能させることも可能である。
コンピュータが読み取り可能な記録媒体としては、磁気ディスク、光磁気ディスク、光ディスクといった交換可能な記録媒体の他、コンピュータに内蔵される記録媒体(HDや半導体メモリなど)を適用可能である。
【0119】
さらに、インターネットを介してプログラムを送信する場合のように、短時間の間に動的にプログラムを保持するもの(伝送媒体又は伝送波)や、コンピュータ内部のメモリのように一定時間プログラムを保持するものも含む。
【0120】
基地局600やノード500の機能をコンピュータによるソフトウェア処理によって実現する場合でも、その動作については同様であるため、重複する説明は省略する。
【0121】
なお、上記各実施形態は本発明の好適な実施の一例であり、本発明はこれに限定されることはない。
例えば、上記各実施形態において例示したツリーネットワークでは、子ノードの数は2以下であったが、3以上の子ノードを備えるノードが存在していても良いことはいうまでもない。
また、2以上のノードが同時に削除、追加、故障した場合についても上記同様の動作によってツリーネットワークの再構成が可能である。
このように、本発明は様々な変形が可能である。
【図面の簡単な説明】
【0122】
【図1】本発明におけるツリーネットワーク再構成の手順を示す図である。
【図2】ツリーネットワークの一例を示す図である。
【図3】ツリーネットワークの各ノードのルーティングテーブルの一例を示す図である。
【図4】ツリーネットワークの再構成の際に各ノード間でやりとりされる信号を示す図である。
【図5】ノードの構成例を示す図である。
【図6】基地局の構成例を示す図である。
【図7】ノード削除時のイニシエータ指定処理の動作の流れを示す図である。
【図8】ノードの状態の変移を表す図である。
【図9】ノード故障時のイニシエータ指定処理の動作の流れを示す図である。
【図10】ノード追加時のイニシエータ指定処理の動作の流れを示す図である。
【図11】部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。
【図12】部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。
【図13】部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。
【図14】ルーティングテーブルの一例を示す図である。
【図15】ルーティングテーブルの一例を示す図である。
【図16】ルーティングテーブルの一例を示す図である。
【図17】ルーティングテーブルの一例を示す図である。
【図18】ルーティングテーブルの一例を示す図である。
【図19】ルーティングテーブルの一例を示す図である。
【図20】ルーティングテーブルの一例を示す図である。
【図21】再構成後のツリーネットワークの構成を示す図である。
【図22】ルーティングテーブルの一例を示す図である。
【図23】部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。
【図24】従来技術によるツリーネットワーク再構成処理の手順を示す図である。
【符号の説明】
【0123】
501、601 入力部
502、602 出力部
503、603 イニシエータ指示/実施部
504 Neighbor Discovery指示/実施部
505 部分木階層構造更新部
506、606 記憶部
507、607 ルーティング処理部
508、608 部分木追加部
【技術分野】
【0001】
本発明は、無線センサネットワークにおいてノードの削除、故障、追加時に、ツリーネットワークを部分的に再構成するネットワーク再構成方法に関する。
【背景技術】
【0002】
無線センサネットワークとは、温度や湿度の環境情報などを分散配置されたセンサノード(以下、ノード)でセンシングし、その結果をノードによって構成されたネットワークによって基地局に集め、統計分析や異常検出通知に活用するネットワークシステムである。
【0003】
無線センサネットワークにおいては、ツリーネットワークを前提とし、ノードの初期設置時に基地局をルートとしたツリーネットワークが構成される。
【0004】
ツリーネットワークを構成する方法として、非特許文献1に開示される方法がある。非特許文献1に開示されるルーティングは次のようなものである。
基地局は、各ノードに検出信号を順次送信する。各ノードは検出信号の受信強度がしきい値以上であるか否かを判断し、所定の強度以上で検出信号を受信したノードのみが検出応答信号を基地局へ返信する。
これにより、基地局と検出応答信号を返信したノードとの接続が確立される。
【0005】
次に、基地局は、未だ接続が確立していない各ノードに対して既に接続が確立されたノードを介して検出信号を順次発信する。各ノードは検出信号の受信強度がしきい値以上であるか否かを判断し、所定の強度以上で検出信号を受信したノードのみが検出応答信号を検出信号の送信元であるノードを介して基地局へ返信する。
【0006】
これにより、基地局と直接は接続できなかったノードは、基地局と直接接続されたノードを介して基地局へ接続される。
【0007】
以上の手順を繰り返すことにより、ツリーネットワークが構成される。
【0008】
非特許文献1に記載の手順は、基地局がノードの信号送信タイミングを集中制御するため、信号衝突を低減でき、ノード数が多い場合でも安定してツリーネットワークを構成できる。
【0009】
一方、運用中にツリーネットワークの再構成が必要となる場合がある。これは、不要になったノードを削除する場合や、ノードが故障した場合や、新しいノードを追加する場合である。
【0010】
ノードを削除する場合を例として説明する。図1に、基地局をルートとして、ノード1〜ノード14で構成されるツリーネットワーク30を示す。
【0011】
ここで、ノード4が削除されるものとする。ノード4が削除されると、ノード4をルートとする部分木に属するノード、すなわちノード7、ノード11、ノード12及びノード14は、ツリーネットワーク30との接続を失って未接続ノードとなる。
【0012】
同様に、ノードが故障した場合には、故障したノードをルートとした部分木に属するノードは未接続ノードとなる。また、ノードを追加する場合には、追加されるノード自体が未接続ノードとなる。
【0013】
このような場合、ツリーネットワークを再構成することで、未接続ノードをツリーネットワークに再接続する必要が生じる。その際には、できるだけ短時間でツリーネットワークを再構成する必要がある。これは、運用中のサービスの停止時間を最小限に留める必要があるからである。
【0014】
図24に、従来の再接続の手法を示す。従来は、非特許文献1に記載の手順で、基地局から未接続ノードを一つずつ再検出し、ツリーネットワークを再構成する方法が用いられていた。換言すると、全てのノードを検出するか、全てのノードを経由して検出を行うまで、非特許文献1に記載の手順を繰り返していた。
【0015】
また、従来のネットワーク再構成方法に関する別の例としては、特許文献1に開示される「マルチホップ無線ネットワークおよび無線局」がある。特許文献1に開示される発明は、各無線局が最適な接続先(上位接続先無線局)を見つけることにより、各無線局が自律的に無線ネットワークを構成するものである。
【特許文献1】特開2001−237764号公報
【非特許文献1】大熊孝裕、川崎大輔、保木本武宏、新井正伸著、「呼出しIDによる省電力マルチホップルーティング機能の実現」、信学技報、Vol.103,No.624,平成16年1月22日、39〜42ページ
【発明の開示】
【発明が解決しようとする課題】
【0016】
非特許文献1に記載の手法を用いる場合の問題点は、ツリーネットワークの再構成に非常に時間がかかることである。その理由は、基地局から未接続ノードを一つずつ検出して、ツリーネットワークに再接続していくからである。
上記のように、ツリーネットワークの再構成は、できるだけ短時間で行う必要がある。非特許文献1に記載の発明は、この要求を十分に満たすものであるとはいえない。
【0017】
また、特許文献1に記載の発明は、ある無線局が上位接続先無線局と接続できなくなった場合には、それより下位の無線局(子無線局)が順次上位接続先無線局の選定動作を行う。このため、無線局の数が多いとネットワーク再構成に要する時間が長期化してしまうこととなる。
【0018】
このように、従来は、短期間でツリーネットワークを確実に再構成することはできなかった。
【0019】
本発明は係る問題に鑑みてなされたものであり、短時間で確実にツリーネットワークを再構成できるネットワーク再構成方法及びそのプログラム並びにそれが記録されたコンピュータが読み取り可能な情報記録媒体、並びにノード、基地局、及びマルチホップネットワークシステムを提供することを目的とする。
【課題を解決するための手段】
【0020】
上記目的を達成するため、本発明は、第1の態様として、基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法であって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定するステップと、代理ノードが、自ノード又は子孫ノードと無線ツリーネットワークとの接続性を検出するステップと、ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、ツリーネットワークとの接続性を有するノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを有することを特徴とするネットワーク再構成方法を提供するものである。
【0021】
本発明の第1の態様においては、無線ツリーネットワークからノードを削除する際に、削除するノードの子ノードを代理ノードとして指定することが好ましい。また、無線ツリーネットワークへノードを追加する際に、追加するノードを代理ノードとして指定することが好ましい。また、無線ツリーネットワークに属するノードが故障した際に、故障したノードの子ノードを代理ノードとして指定することが好ましい。
【0022】
本発明の第1の態様の上記のいずれの構成においても、無線ツリーネットワークとの接続性を検出するステップにおいては、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出することが好ましい。
【0023】
また、本発明の第1の態様の上記のいずれの構成においても、無線ツリーネットワークとの接続性を検出するステップにおいて無線ツリーネットワークとの接続性を有するノードが複数検出された場合には、基地局までのホップ数が小さいものを部分木のルートとして設定することが好ましい。
【0024】
また、上記目的を達成するため、本発明は、第2の態様として、基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法をノードに実行させるプログラムであって、ノードを制御する実質的なコンピュータに、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定するステップと、代理ノード又はその子孫ノードと無線ツリーネットワークとの接続性を検出するステップと、ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、ツリーネットワークとの接続性を有するノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを実行させることを特徴とするネットワーク再構成方法のプログラムを提供するものである。
【0025】
本発明の第2の態様においては、自ノードが無線ツリーネットワークから削除される場合には、実質的なコンピュータに、子ノードを代理ノードとして指定させることが好ましい。また、自ノードが無線ツリーネットワークへ追加される場合には、実質的なコンピュータに自ノードを代理ノードとして指定させることが好ましい。また、自ノードの親ノードが故障した場合には、実質的なコンピュータに、自ノードを代理ノードとして指定させることが好ましい。
【0026】
本発明の第2の態様の上記のいずれの構成においても、自ノードが未接続の部分木に属する場合、実質的なコンピュータに、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出させることが好ましい。
【0027】
また、未接続の部分木に属する他のノードも無線ツリーネットワークとの接続性を有する場合には、実質的なコンピュータに、基地局までのホップ数が最小の場合にのみ自ノードを部分木の新たなルートとさせることが好ましい。
【0028】
また、上記目的を達成するため、本発明は、第3の態様として、上記本発明の第2の態様のいずれかの構成にかかるネットワーク再構成方法のプログラムが記録されたコンピュータが読み取り可能な情報記録媒体を提供するものである。
【0029】
また、上記目的を達成するため本発明は、第4の態様として、無線通信方式で基地局と接続されて無線ツリーネットワークを構成するノードであって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定する手段と、代理ノードとして指定された場合に、自ノードの子孫ノードに対して無線ツリーネットワークとの接続性の有無の確認を要求する手段と、無線ツリーネットワークとの接続性の有無を確認する手段と、自ノードが未接続の部分木に属する場合に、代理ノードからの指示に応じて、無線ツリーネットワークとの接続性を有するノードが新たなルートとなるように該未接続の部分木の階層構造を変更する手段と、自ノードが未接続の部分木の新たなルートとなった場合に、自ノードから基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知する手段とを有することを特徴とするノードを提供するものである。
【0030】
本発明の第4の態様においては、自ノードが無線ツリーネットワークから削除される場合には、子ノードを代理ノードとして指定することがこのましい、また、自ノードが無線ツリーネットワークへ追加される場合には、自ノードを代理ノードとして指定することが好ましい。また、自ノードの親ノードが故障した場合には、自ノードを代理ノードとして指定することが好ましい。
【0031】
本発明の第4の態様の上記のいずれの構成においても、自ノードが未接続の部分木に属する場合、代理ノードとのホップ数が小さい順に無線ツリーネットワークとの接続性を検出することがこのましい。
【0032】
本発明の第4の態様の上記のいずれの構成においても、未接続の部分木に属する他のノードも無線ツリーネットワークとの接続性を有する場合には、基地局までのホップ数が最小の場合にのみ部分木の新たなルートとなることが好ましい。
【0033】
また、上記目的を達成するため、本発明は、第5の態様として、無線通信方式で接続された少なくとも一つのノードとともに無線ツリーネットワークを構成する基地局であって、無線ツリーネットワークと未接続の部分木のルートを基地局の代理ノードとして指定する手段と、階層構造が変更された未接続の部分木に属するいずれかのノードから、変更後の未接続の部分木の階層構造に関する情報を受信した場合に、該受信した情報に応じてツリーネットワークの階層構造を表す情報を更新する手段とを有することを特徴とする基地局を提供するものである。
【0034】
また、上記目的を達成するため、本発明は、第6の態様として、上記本発明の第4の態様のいずれかの構成にかかるノードを少なくとも一つと、上記本発明の第5の態様にかかる基地局とを有することを特徴とするマルチホップネットワークシステムを提供するものである。
【発明の効果】
【0035】
本発明によれば、短時間で確実にツリーネットワークを再構成できるネットワーク再構成方法及びそのプログラム並びにそれが記録されたコンピュータが読み取り可能な情報記録媒体、並びにノード、基地局、及びマルチホップネットワークシステムを提供できる。
【発明を実施するための最良の形態】
【0036】
〔発明の原理〕
本発明では、ノードをツリーネットワークに再接続する処理を図1に示すように四つのステップに分けて行う。
第1のステップ(イニシエータ指定処理)では、基地局の代理となってツリーネットワークの再構成を制御する「イニシエータ」を指定する。このステップにおける処理によって、ノードの削除や故障によってツリーネットワークに未接続となった部分木(以下、未接続の部分木)のルートがイニシエータに指定される。
【0037】
第2のステップ(Neighbor Discovery処理)では、ツリーネットワークとの接続性を検出するために、イニシエータがNeighbor Discoveryを実施するか、又は、イニシエータの子孫ノードがイニシエータからの指示に応じてNeighbor Discoveryを実施する。このステップにおける処理により、未接続の部分木に属するいずれかのノードと、ツリーネットワークとの接続性を検出する。
【0038】
第3のステップ(部分木階層構造更新処理)では、Neighbor Discoveryによって検出したツリーネットワークとの接続性に応じて、未接続の部分木の階層構造を更新する。このステップにおける処理により、Neighbor Discoveryに成功したノードが、新しく未接続の部分木のルートとなるように階層構造を更新する。
【0039】
第4のステップ(部分木再接続処理)では、未接続の部分木を再びツリーネットワークに接続する。このステップにおける処理により、未接続の部分木が再びツリーネットワークに接続される。
【0040】
ツリーネットワークの再構成が必要となる契機は、上記のように、ノードを削除する場合、ノードが故障した場合及びノードを追加する場合であるが、上記のイニシエータ指定処理は再構成の契機によって手順が異なる。Neighbor Discovery処理、部分木階層構造更新処理及び部分木再接続処理は、全ての契機で共通する処理である。
ノード削除時、ノード故障時及びノード追加時のそれぞれの場合のイニシエータ指定処理については後段で詳細に説明する。
【0041】
ツリーネットワークを再構成する際に、従来の手法のように基地局(ルート)から順に未接続ノードの再接続を試みるのではなく、イニシエータ指定処理でイニシエータを指定し、Neighbor Discovery処理で未接続の部分木に属するいずれかのノードとツリーネットワークとの接続性をイニシエータがNeighbor Discoveryによって検出する。そして、部分木階層構造更新処理では、Neighbor Discovery処理での検出結果に応じて、未接続の部分木の階層構造を更新し、部分木再接続処理で未接続の部分木とツリーネットワークとを再接続する。
【0042】
これにより、ノードのルーティングテーブルの更新数を低減でき、結果としてツリーネットワークの再構成に要する時間を短縮できる。
【0043】
以下、上記原理に基づく本発明の好適な実施の形態について説明する。
【0044】
〔第1の実施形態〕
本発明を好適に実施した第1の実施形態について説明する。
図2に、基地局をルートとしてノード1〜ノード14によって構成されるツリーネットワークを示す。
各ノードは、図3に示すルーティングテーブルを有する。ルーティングテーブルは、親ノード、子孫ノードの情報を含む。すなわち、自ノードをルートとする部分木の構成と、親ノードとの情報を含む。
【0045】
基地局及び各ノードが送受信する信号の種類を図4に示す。
【0046】
図5に、ツリーネットワークに適用されるノードの構成を示す。
ノード500は、入力部501、出力部502、イニシエータ指示/実施部503、Neighbor Discovery指示/実施部504、部分木階層構造更新部505、記憶部506、ルーティング処理部507及び部分木追加部508を有する。
【0047】
入力部501は、“ノード削除信号”、“ノード故障信号”、“イニシエータ指示信号”、“更新開始信号”、“更新開始指示信号”、“Neighbor Discovery指示信号”、“Neighbor Discovery成功信号”、“Neighbor Discovery失敗信号”、“更新信号”、“追加信号”、“更新完了信号”、“更新完了指示信号”などを入力として受け付ける。
また、入力部501は、ノード削除時及びノード追加時に、後述するイニシエータ指示/実施部503が動作を開始するための“削除開始信号”及び“追加開始信号”を受信する。
【0048】
出力部502は、これらの信号を他のノード500や基地局600に対して送信する。
【0049】
イニシエータ指示/実施部503の機能について説明する。
まず、ノード削除時の動作に関する機能ついて説明する。イニシエータ指示/制御部503は、ノード削除時には、以下のような動作を行う。
・入力部501が“削除開始信号”を受信すると、出力部502に“更新開始信号”を送信させる。
・入力部501が“更新開始信号”を受信すると、自ノードを運用状態から経路更新状態へ移行させ、Neighbor Discoveryに応答しないようにする。
・自ノードが削除ノードであるならば、全ての子孫ノードに“更新開始信号”を送信した後、“ノード削除信号”に自ノードのID情報を含めて、出力部502によって親ノードへ送信する。
・入力部501が“ノード削除信号“を受信すると、記憶部506に保持しているルーティングテーブルから、削除ノードをルートとする部分木を削除する。また、出力部502に親ノードへ“ノード削除信号”を送信させる。
・自ノードが削除ノードであるならば、親ノードに対して“ノード削除信号”を送信した後、出力部502に“イニシエータ指示信号”を送信させる。
・入力部501が“イニシエータ指示信号”を受信した場合には、自ノードをイニシエータとし、後述するNeighbor Discoveryを実行する。
【0050】
ノード故障時のイニシエータ指定/実施部503の動作に関する機能について説明する。イニシエータ指示/制御部503は、ノード故障時には以下のような動作を行う。
・故障を発見したノードであるならば、記憶部506に保持している故障ノードをルートとする部分木を、記憶部506に保持しているルーティングテーブルから削除する。そして、“ノード故障信号”を故障発見ノード(すなわち、故障ノードの親ノードと基地局との間にあるノード)へ送信する。
・入力部501が“更新開始指示信号”を受信すると、記憶部506に保持している部分木から故障ノードをルートとする部分木を削除する。
・入力部501が“更新開始指示信号“を受信すると、出力部502に全子孫ノードに対して“更新開始信号”を送信させる。
・全子孫ノードに対して“更新開始信号”を送信した後、「全ての子孫ノードに対して“更新開始信号”を送信したこと」を示す“通知完了信号”を、出力部502から基地局へ送信させる。
・入力部501が“イニシエータ指示信号”を受信すると、自ノードをイニシエータとする。
【0051】
ノード追加時のイニシエータ指定/実施部503の動作に関する機能について説明する。イニシエータ指定/制御部503は、ノード追加時には以下のような動作を行う。
・入力部501が“追加開始信号”を受信すると、自ノードをイニシエータとする。
【0052】
Neighbor Discovery指示/実施部504について説明する。Neighbor Discovery指示/実施部504では、自ノードがイニシエータであるならば、Neighbor Discoveryを実行する。また、イニシエータは、子孫ノードに対して“Neighbor Discovery指示信号”を送信する。
“Neighbor Discovery指示信号”を受信したノードは、Neighbor Discoveryを実施する。Neighbor Discoveryに成功した場合はその結果を記憶部506に保存し、イニシエータに対して“Neighbor Discovery成功信号”を送信する。Neighbor Discoveryに成功したノードは、新しく部分木のルートとなる(以下、新ルートノード)。
Neighbor Discoveryに失敗した場合は、イニシエータに“Neighbor discovery失敗信号”を送信する。
【0053】
部分木階層構造更新部505について説明する。
部分木階層構造更新部505は、Neighbor Discoveryの結果に応じて、イニシエータをルートとして更新した部分木の階層構造をルーティングテーブルに反映させる。
入力部501から“Neighbor Discovery成功信号”を受信すると、イニシエータは自ノードのルーティングテーブルを更新する。そして、そのルーティングテーブルと新しいルートノードの情報とを“更新情報”に含め、出力部502に新しい親ノードへ送信させる。
ここで、新しい親ノードは、旧ルーティングテーブルにおいて、新ルートノードを子孫として持つ子ノードが選択される。
【0054】
入力部501から“更新信号”を受信すると、これに含まれる新ルートノードを旧ルーティングテーブルで子孫ノードとして持つ子ノードを新しい親ノードとする。また、“更新信号”に含まれる部分木情報を、ルーティングテーブルに追加する。
そして、自ノードのルーティングテーブルと新しいルートノードとの情報を“更新信号”ともに親ノードへ送信する。
【0055】
新ルートノードが入力部501によって“更新信号”を受信すると、これに含まれるルーティングテーブルを自ノードのルーティングテーブルに追加する。また、Neighbor Discoveryで検出したノードを新しい親ノードにする。
【0056】
部分木追加部506について説明する。
新ルートノードでは、出力部502によって、自ノードのルーティングテーブルを“追加信号”とともに親ノードへ送信する。
“追加信号”を受信したノードでは、“追加信号”に含まれるルーティングテーブルの情報を自ノードのルーティングテーブルに追加する。そして、受信した”追加信号”の内容を出力部502を用いて親ノードへ送信する。
入力部501によって“更新完了信号”を受信した新ルートノードは、全子孫ノードへ“更新完了信号”を出力部502から送信する。“更新完了信号”を受信したノードは、経路更新状態から運用状態へと移行する。
【0057】
記憶部506は、ルーティングテーブルNeighbor Discoveryの結果などを保持する。
【0058】
ルーティング処理部507は、後述するノード故障時に非特許文献1に開示される手法を利用して、仮経路を作成する際に用いられる。
【0059】
図6に、基地局600の構成を示す。
基地局600は、入力部601,出力部602、イニシエータ指示/実施部603、記憶部606、ルーティング処理部607及び部分木追加部608を有する。
入力部601は、“ノード削除信号”、“ノード故障信号”、“追加信号”、“追加完了信号”などを入力として受け付ける。
【0060】
イニシエータ指示/実施部603の機能について説明する。
入力部601によって“ノード削除信号”を受信すると、記憶部606に保持しているルーティングテーブルから削除ノードをルートとする部分木を削除する。
入力部601によって“ノード故障信号”を受信すると、記憶部606に保持しているルーティングテーブルから故障ノードをルートとする部分木を削除する。また、出力部602を用いて、故障ノードの子ノードへ“更新開始指示信号”を送信する。
入力部601によって“通知完了信号”を受信すると、“イニシエータ指示信号”を故障ノードの子ノードへ出力部602を用いて出力する。
【0061】
部分木追加部608の機能について説明する。
入力部601によって“追加信号”を受信した基地局は、“追加信号”に含まれるルーティングテーブルの情報を、自ノードのルーティングテーブルに追加する。そして、基地局のルーティングテーブル更新が完了したことを示す“更新完了信号”を新ルートノードに対して出力部602によって送信する。
【0062】
記憶部606は、ルーティングテーブルやNeighbor Discoveryの結果などを保持する。
【0063】
ルーティング処理部607は、後述するノード故障時に非特許文献1に開示される手法を利用して、仮経路を作成する際に用いられる。
【0064】
ツリーネットワークの再構成動作について説明する。
まず、イニシエータを指定する手順について説明する。上記のように、イニシエータを指定する手順は、動作開始の契機によって異なるため、それぞれについて個別に説明する。
【0065】
<ノード削除時のイニシエータ指定手順>
最初にノード削除時のイニシエータの指定手順について説明する。図7にノード削除時のイニシエータの指定動作の流れを示す。
削除ノードは“削除開始信号”を受信すると(ステップB1)、全子孫ノードに“更新開始信号”を送信する(ステップB2)。“更新開始信号”を受信したノードは、図8に示すように運用状態から経路更新状態へと移行する。
【0066】
次に、削除ノードは、削除ノードから基地局までの間にあるノードに対して“ノード削除信号”を送信する(ステップB3)。“ノード削除信号”を受信したノードは、削除ノードをルートとする部分木をルーティングテーブルから削除する。
【0067】
削除ノードは、子ノードにイニシエータ動作を指示する“イニシエータ指示信号”を送信する(ステップB4)。“イニシエータ指示信号”を受信したノードは、イニシエータとなり、後述するNeighbor Discoveryの実行などを制御する(ステップB5)。
【0068】
<ノード故障時のイニシエータ指定手順>
次に、ノード故障時のイニシエータの指定手順について説明する。図9に、ノード故障時のイニシエータ指定動作の流れを示す。ノード故障時には、故障したノード(故障ノード)を発見したノード(すなわち、故障ノードの親ノード)が、故障ノードをルートとした部分木を自ノードのルーティングテーブルから削除する。そして、故障ノードの親ノードと基地局との間にある各ノードに対し、故障ノードの発生を通知する“ノード故障信号”を送信する(ステップC1)。“ノード故障信号”を受信したノードは、故障ノードをルートとする部分木をルーティングテーブルから削除する。
【0069】
ノード削除時と同様に、ノード故障時も、故障ノードの子ノードに”更新開始信号”と”イニシエータ指示信号”とを送信する必要がある。しかし、故障ノードの子ノードへの経路は存在しないため、基地局は故障ノードの子ノードへの仮経路を非特許文献1に開示される手法を応用して作成する(ステップC2)。
【0070】
この際には、非特許文献1に開示される手法を利用して、故障ノードの子ノードをルートとした部分木に属するいずれかのノードを検出する。これにより、ツリーネットワークと故障したノードをルートとした部分木に属するいずれかのノードとの間に仮経路を形成できる。
このとき、検出されたノードを経由ノードと呼ぶ。基地局は、この仮経路を使用して、故障ノードの子ノード宛に“更新開始指示信号”や”イニシエータ指示信号”を送信する(ステップC3)。その際に、経由ノードのIDを信号に含める。
故障ノードをルートとした部分木に属するノードは、自ノード宛ではない”更新開始指示信号”や”イニシエータ指示信号”を親ノードへ転送する。
【0071】
このようにすることで、“更新開始指示信号”や“イニシエータ指示信号”を故障ノードの子ノードへ送達できる(ステップC4)。
【0072】
また、故障ノードの子ノードは、“通知完了信号”を基地局へ送信するが、“更新開始指示信号”に含まれた経由ノードへ先ず送信する。“更新完了信号”を受信した経由ノードは、仮経路を利用して、受信した信号を基地局へ転送する(ステップC5)。
【0073】
以上の手順で、イニシエータが指定されるまで、基地局と故障ノードの子ノードとは仮経路を使用して通信する。
【0074】
基地局は仮経路を利用して、故障ノードの子ノード及び、故障ノードの子ノードの子孫ノードへ“更新開始指示信号”を送信する。“更新開始指示信号”を受信した故障ノードの子ノードは、全子孫ノードに対して“更新開始信号”を送信する。
【0075】
故障ノードの子ノードは、全子孫ノードに“更新開始信号”を送信したことを”通知完了信号”によって基地局に通知する。
【0076】
基地局は、故障ノードの子ノードから“通知完了信号”を受信すると、仮経路を利用して“イニシエータ指示信号”を故障ノードの子ノードへ送信する(ステップC6)。
【0077】
イニシエータ指示信号を受信した故障ノードの子ノードは、仮経路を削除するために、“仮経路削除信号“を、削除ノードと基地局との間にある各ノードへ送信する(ステップC7)。これにより、仮経路は削除される。
【0078】
イニシエータとなったノードは(ステップC8)、後述するNeighbor Discoveryの実行などを制御する。
【0079】
<ノード追加時の基地局の動作>
ノード追加時の基地局の動作について説明する。図10に、ノード追加時の基地局の動作の流れを示す。
“追加開始信号”を受信したノードは(ステップF1)、イニシエータとなる(ステップF2)。
【0080】
以上のようにして、ノード削除時、ノード故障時、ノード追加時にイニシエータが指定される。
【0081】
次に、イニシエータのNeighbor Discovery実施・指示の動作について説明する。図11、図12及び図13に、Neighbor Discovery実施・指示動作の流れを示す。イニシエータは、先ず自らがNeighbor Discoveryを実施し、ツリーネットワークとの新しい接続性検出を試みる(ステップD1)。ここで、Neighbor Discoveryが検出された場合は(ステップD2/Yes)、イニシエータは検出したノードを新しい親ノードに選択し、ルーティングテーブルを更新する。
【0082】
もし、イニシエータがNeighbor Discoveryに失敗した場合は(ステップD2/No)、イニシエータとのホップ数が小さい子孫ノードから順番に、“Neighbor Discovery指示信号”を送信し、子孫ノードがNeighbor Discoveryを実施する(ステップD3)。
【0083】
子孫ノードがNeighbor Discoveryに成功した場合は(ステップD4/Yes)、イニシエータをルートとした部分木を、Neighbor Discoveryに成功した子孫ノード(以下、新ルートノード)が新しい部分木のルートとなるように階層構造を変更する(ステップD6)。ここで、階層構造の変更に伴い、新ルートノードとイニシエータとの間でルーティングテーブルを更新する(ステップD6〜D12)。
【0084】
イニシエータは、新しい部分木の情報をルーティングテーブルに追加することを要求する“追加信号”を、新ルートノードと基地局(基地局も含む)の経路にあるノードに対して送信する(ステップD13〜D16)。これにより、新ルートノードと基地局との経路にある各ノードのルーティングテーブルが更新される。また、“追加信号“を受信した基地局は、“更新完了通知“を新ルートノードへ送信する(ステップD17)。基地局からの“更新完了通知”を受信した新ルートノードは、経路変更が完了したことを示す“更新完了通知”を全子孫ノードに送信する(ステップD18)。“更新完了通知”を受信したノードの状態は、経路更新状態から運用状態へと移行する。
【0085】
〔動作例1〕
図2に示したツリーネットワーク30において、ノード4が削除されるものとする。
まず、ノード4は、“削除開始信号”を受信すると、全ての子孫ノード、つまり、ノード7,ノード11、ノード14及びノード12に対して“更新開始信号”を送信する。
図8に示すように、更新開始信号を受信したノードは、運用状態から経路更新状態へと移行する。経路更新状態のノードは、基地局までの到達性を持たないため、Neighbor Discoveryに対してリプライを返さない。
【0086】
次に、ノード4は、自ノードから基地局までの経路にあるノード、すなわちノード1及び基地局に対して“ノード削除信号”を送信する。“ノード削除信号”を受信したノード(ノード1及び基地局)は、削除ノード(ノード4)をルートとする部分木の情報をルーティングテーブルから削除する。この時、ノード1と基地局とのルーティングテーブルを図14に示す。
【0087】
次に、ノード4は、子ノードであるノード7に“イニシエータ指示信号”を送信する。これにより、ノード7はイニシエータとなる。
【0088】
イニシエータとなったノード7は、まず自らがNeighbor Discoveryを実施し、ツリーネットワーク30との新しい接続性検出を試みる。
【0089】
以下、イニシエータであるノード7におけるNeighbor Discoveryが成功した場合を例として説明する。
Neighborが検出された場合は、ノード7は検出したノードを新しい親ノードに選択し、ルーティングテーブルを更新する。ここでは、ノード3がNeighborとして検出されたものとする。この時の、ノード7のルーティングテーブルを図15に示す。
【0090】
次に、ノード7は、自ノードと基地局との間のノード、すなわち、ノード3、ノード1及び基地局に“追加信号”を送信する。“追加信号”には、自ノードのルーティングテーブル情報が付加される。“追加信号”を受信したノード3、ノード1及び基地局は、ノード7をルートとする部分木の情報をルーティングテーブルに追加する。この時のノード3、ノード1及び基地局のルーティングテーブルは図16のようになる。
【0091】
このようにして、ノード7から基地局までの経路にある各ノードのルーティングテーブルが更新される。最後に、イニシエータであるノード7は、全ての子孫ノード、すなわちノード11、ノード14及びノード12へ“更新完了信号”を送信する。
“更新完了信号”を受信したノードは、経路更新状態から運用状態へと移行する。
【0092】
次に、イニシエータであるノード7におけるNeighbor Discoveryが失敗した場合について説明する。
イニシエータであるノード7がNeighbor Discoveryに失敗した場合は、イニシエータは、ホップ数が小さい子孫ノードから順番に“Neighbor Discovery指示信号”を送信し、子孫ノードにNeighbor Discoveryを実施させる。ここでは、ノード11→ノード12→ノード13の順番でNeighbor Discoveryの指示を出すものとする。
【0093】
子孫ノードがNeighbor Discoveryを実行する場合の具体例として、ノード11及びノード12がNeighbor Discoveryに失敗し、ノード14がNeighbor Discoveryに成功した場合について説明する。
イニシエータであるノード7は、ノード11にNeighbor Discovery指示信号を送信する。“Neighbor Discovery指示信号”を受信したノード11は、Neighbor Discoveryを実行する。ノード11は、Neighbor Discoveryを実行した結果、ノードを検出できなかったため、“Neighbor Discovery失敗信号”をノード7へ送信する。
【0094】
ノード7は、次に、ノード12に対して“Neighbor Discovery指示信号”を送信する。“Neighbor Discovery指示信号”を受信したノード12は、Neighbor Discoveryを実行する。ノード12は、Neighbor Discoveryを実行した結果、ノードを検出できなかったため、“Neighbor Discovery失敗信号”をノード7へ送信する。
【0095】
ノード7は、次に、ノード14に“Neighbor Discovery指示信号を送信する。“Neighbor Discovery指示信号”を受信したノード14は、Neighbor Discoveryを実行する。ノード14はNeighbor Discoveryを実行した結果、ノード9を検出する。ノード14は、検出したNeighborを保持し、イニシエータであるノード7へ“Neighbor Discovery成功信号”を送信する。
【0096】
ノード14からの“Neighbor Discovery成功信号”を受信したオード7は、ノード7をルートとする部分木を、ノード14がルートとなるように階層構造を変更する。
【0097】
ノード7にとって、ノード14を子孫ノードに持つ子ノードは、ノード11である。従って、ノード11がノード7の新しい親ノードとなる。また、ノード11をルートとする部分木をルーティングテーブルから削除する。この時の、ノード7のルーティングテーブルを図17に示す。
【0098】
ノード7は、更新したルーティングテーブルと新ルートノードのID情報とを“更新情報”とともに親ノードであるノード11へ送信する。
【0099】
“更新信号”を受信したノード11は、子孫ノードであるノード14を新しい親ノードとする。また、ノード14をルートとする部分木をルーティングテーブルから削除する。そして、受信した“更新信号”の情報をルーティングテーブルに追加する。この時のノード11のルーティングテーブルを図18に示す。
【0100】
ノード11は、更新したルーティングテーブルと新ルートノードのID情報とを、“更新情報”とともに親ノードであるノード14へ送信する。
【0101】
“更新情報”を受信したノード14は、受信した“更新信号”に含まれるルーティングテーブルの情報を、自ノードのルーティングテーブルに追加する。
【0102】
また、ノード14は、Neighbor Discoveryで検出したノード9を親ノードとして設定する。この時のノード14のルーティングテーブルを図19に示す。
【0103】
ノード14は、自ノードと基地局との経路にあるノード(基地局を含む)、すなわち、ノード9、ノード6、ノード3、ノード1及び基地局に対して“追加信号”を送信する。これにより、ノード14と基地局との経路にある各ノードのルーティングテーブルが更新される。この時のノード9、ノード6、ノード3、ノード1及び基地局のルーティングテーブルを図20に示す。
【0104】
受信した“追加信号”に応じてルーティングテーブルを更新した基地局は、“更新完了信号”をノード14へ送信する。
【0105】
“更新完了信号”を受信したノード14は、全子孫ノード、すなわち、ノード11、ノード7及びノード12に“更新完了信号”を送信する。“更新完了信号”を受信したノードは、経路変更状態から運用状態へと移行する。
【0106】
以上でノード削除時の動作を完了する。上記動作において再構成されたツリーネットワークを図21に示す。
【0107】
〔動作例2〕
ツリーネットワークを構成するノードが故障した場合の動作について説明する。上記動作例1は、ツリーネットワークからノードを削除する場合のものであったが、ノード削除時の動作と、ノード故障時又はノード追加時の動作との差分は、イニシエータ指定の動作である。従って、イニシエータ指定の動作のみを説明する。
【0108】
図2に示したツリーネットワーク30において、ノード4が故障したものとする。
【0109】
ノード故障の場合は、ノード故障を発見したノード、すなわち故障したノード(ノード4)の親ノードであるノード1が、ノード4をルートとする部分木を自ノードのルーティングテーブルから削除する。そして、ノード1から基地局までの経路にあるノード(すなわち基地局)に対して“ノード故障信号”を送信する。“ノード故障信号“を受信した基地局は、故障ノードであるノード4をルートとする部分木の情報をルーティングテーブルから削除する。この時のノード1及び基地局のルーティングテーブルを図22に示す。
【0110】
“ノード故障信号”を受信した基地局は、非特許文献1に開示される手法を用いて、基地局とノード7との間に仮経路を作成する。例えば、ノード14の子孫ノードであるノード12をノード13から検出したとする。この場合、以降の“更新開始指示信号”、“通知完了信号”、“イニシエータ指示信号”は仮経路を利用して送受信される。ノード7が、“イニシエータ指示信号”を受信してイニシエータとなると、“仮経路削除信号”をノード7→ノード12→ノード13→ノード8→ノード5→ノード2→基地局へ送信し、仮経路を削除する。
【0111】
基地局は仮経路を利用して、“更新開始指示信号”をノード7へ送信する。“更新開始信号”を受信したノード7は、全子孫ノード、すなわちノード11、ノード14及びノード12に対して“更新開始信号”を送信する。そして、ノード7は、“通知完了信号”を基地局に通知する。
【0112】
基地局は、ノード7から“通知完了信号”を受信すると、仮経路を利用して、“イニシエータ指示信号”をノード7へ送信する。“イニシエータ指示信号”を受信したノード7は、仮経路削除要求を基地局に対して送信する。そして、イニシエータとなり、Neighbor Discoveryの実行などを制御する。
【0113】
〔動作例3〕
ノードを追加する場合は、“ノード追加信号”を受信すると、追加ノード自身がイニシエータとなる。イニシエータの指定以外の手順については上記動作例1と同様である。
【0114】
本実施形態に係るツリーネットワークにおいては、ツリーネットワークの再構成時に、ノードのルーティングテーブルの更新数を低減でき、結果としてツリーネットワークの再構成に要する時間を短縮できる。しかも、イニシエータ自身がツリーネットワークとの接続性を有しない場合には、その子孫ノードとツリーネットワークとの接続性を調べ、接続性を有するノードが存在すればそれを新たなルートとしてツリー構造を変更するため、未接続の部分木を確実にツリーネットワークに接続できる。
【0115】
〔第2の実施形態〕
本発明を好適に実施した第2の実施形態について説明する。
図23に、本実施形態におけるネットワーク再構成の動作の流れを示す。
第1の実施形態の動作との違いは、Neighbor Discoveryの結果複数のNeighborが検出された場合に、基地局までのホップ数が最小のノードをNeighborとして選択することである。
【0116】
基地局までのホップ数が最小のノードをNeighborとして選択することで、新ルートノードから基地局までのホップ数が小さくなり、ルーティングテーブルの更新回数を低減できる。
【0117】
これにより、ツリーネットワークの再構成に要する時間をさらに短縮できる。
【0118】
〔第3の実施形態〕
図5及び図6に示した基地局600及びノード500は、専用のハードウェアによって実現する以外に、その機能を実現する為のプログラムをコンピュータが読み取り可能な記録媒体に記録しておき、これをコンピュータに読み取らせて基地局600及びノード500として機能させることも可能である。
コンピュータが読み取り可能な記録媒体としては、磁気ディスク、光磁気ディスク、光ディスクといった交換可能な記録媒体の他、コンピュータに内蔵される記録媒体(HDや半導体メモリなど)を適用可能である。
【0119】
さらに、インターネットを介してプログラムを送信する場合のように、短時間の間に動的にプログラムを保持するもの(伝送媒体又は伝送波)や、コンピュータ内部のメモリのように一定時間プログラムを保持するものも含む。
【0120】
基地局600やノード500の機能をコンピュータによるソフトウェア処理によって実現する場合でも、その動作については同様であるため、重複する説明は省略する。
【0121】
なお、上記各実施形態は本発明の好適な実施の一例であり、本発明はこれに限定されることはない。
例えば、上記各実施形態において例示したツリーネットワークでは、子ノードの数は2以下であったが、3以上の子ノードを備えるノードが存在していても良いことはいうまでもない。
また、2以上のノードが同時に削除、追加、故障した場合についても上記同様の動作によってツリーネットワークの再構成が可能である。
このように、本発明は様々な変形が可能である。
【図面の簡単な説明】
【0122】
【図1】本発明におけるツリーネットワーク再構成の手順を示す図である。
【図2】ツリーネットワークの一例を示す図である。
【図3】ツリーネットワークの各ノードのルーティングテーブルの一例を示す図である。
【図4】ツリーネットワークの再構成の際に各ノード間でやりとりされる信号を示す図である。
【図5】ノードの構成例を示す図である。
【図6】基地局の構成例を示す図である。
【図7】ノード削除時のイニシエータ指定処理の動作の流れを示す図である。
【図8】ノードの状態の変移を表す図である。
【図9】ノード故障時のイニシエータ指定処理の動作の流れを示す図である。
【図10】ノード追加時のイニシエータ指定処理の動作の流れを示す図である。
【図11】部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。
【図12】部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。
【図13】部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。
【図14】ルーティングテーブルの一例を示す図である。
【図15】ルーティングテーブルの一例を示す図である。
【図16】ルーティングテーブルの一例を示す図である。
【図17】ルーティングテーブルの一例を示す図である。
【図18】ルーティングテーブルの一例を示す図である。
【図19】ルーティングテーブルの一例を示す図である。
【図20】ルーティングテーブルの一例を示す図である。
【図21】再構成後のツリーネットワークの構成を示す図である。
【図22】ルーティングテーブルの一例を示す図である。
【図23】部分木における接続性検出とツリー構造の再構成の処理の流れを示す図である。
【図24】従来技術によるツリーネットワーク再構成処理の手順を示す図である。
【符号の説明】
【0123】
501、601 入力部
502、602 出力部
503、603 イニシエータ指示/実施部
504 Neighbor Discovery指示/実施部
505 部分木階層構造更新部
506、606 記憶部
507、607 ルーティング処理部
508、608 部分木追加部
【特許請求の範囲】
【請求項1】
基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法であって、
前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定するステップと、
前記代理ノードが、自ノード又は子孫ノードと前記無線ツリーネットワークとの接続性を検出するステップと、
前記ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、
前記ツリーネットワークとの接続性を有するノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを有することを特徴とするネットワーク再構成方法。
【請求項2】
前記無線ツリーネットワークからノードを削除する際に、削除するノードの子ノードを前記代理ノードとして指定することを特徴とする請求項1記載のネットワーク再構成方法。
【請求項3】
前記無線ツリーネットワークへノードを追加する際に、追加するノードを前記代理ノードとして指定することを特徴とする請求項1又は2記載のネットワーク再構成方法。
【請求項4】
前記無線ツリーネットワークに属するノードが故障した際に、故障したノードの子ノードを前記代理ノードとして指定することを特徴とする請求項1から3のいずれか1項記載のネットワーク再構成方法。
【請求項5】
前記無線ツリーネットワークとの接続性を検出するステップにおいては、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出することを特徴とする請求項1から4のいずれか1項記載のネットワーク再構成方法。
【請求項6】
前記無線ツリーネットワークとの接続性を検出するステップにおいて前記無線ツリーネットワークとの接続性を有するノードが複数検出された場合には、前記基地局までのホップ数が小さいものを前記部分木のルートとして設定することを特徴とする請求項1から5のいずれか1項記載のネットワーク再構成方法。
【請求項7】
基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法を前記ノードに実行させるプログラムであって、
前記ノードを制御する実質的なコンピュータに、
前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定するステップと、
前記代理ノード又はその子孫ノードと前記無線ツリーネットワークとの接続性を検出するステップと、
前記ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、
前記ツリーネットワークとの接続性を有するノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを実行させることを特徴とするネットワーク再構成方法のプログラム。
【請求項8】
自ノードが前記無線ツリーネットワークから削除される場合には、前記実質的なコンピュータに、子ノードを前記代理ノードとして指定させることを特徴とする請求項7記載のネットワーク再構成方法のプログラム。
【請求項9】
前記自ノードが前記無線ツリーネットワークへ追加される場合には、前記実質的なコンピュータに自ノードを前記代理ノードとして指定させることを特徴とする請求項7又は8記載のネットワーク再構成方法のプログラム。
【請求項10】
自ノードの親ノードが故障した場合には、前記実質的なコンピュータに、自ノードを前記代理ノードとして指定させることを特徴とする請求項7から9のいずれか1項記載のネットワーク再構成方法のプログラム。
【請求項11】
自ノードが前記未接続の部分木に属する場合、前記実質的なコンピュータに、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出させることを特徴とする請求項7から10のいずれか1項記載のネットワーク再構成方法のプログラム。
【請求項12】
前記未接続の部分木に属する他のノードも前記無線ツリーネットワークとの接続性を有する場合には、前記実質的なコンピュータに、前記基地局までのホップ数が最小の場合にのみ自ノードを前記部分木の新たなルートとさせることを特徴とする請求項7から11のいずれか1項記載のネットワーク再構成方法のプログラム。
【請求項13】
請求項7から12のいずれか1項記載のネットワーク再構成方法のプログラムが記録されたコンピュータが読み取り可能な情報記録媒体。
【請求項14】
無線通信方式で基地局と接続されて無線ツリーネットワークを構成するノードであって、
前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定する手段と、
前記代理ノードとして指定された場合に、自ノードの子孫ノードに対して前記無線ツリーネットワークとの接続性の有無の確認を要求する手段と、
前記無線ツリーネットワークとの接続性の有無を確認する手段と、
自ノードが前記未接続の部分木に属する場合に、前記代理ノードからの指示に応じて、前記無線ツリーネットワークとの接続性を有するノードが新たなルートとなるように該未接続の部分木の階層構造を変更する手段と、
自ノードが前記未接続の部分木の新たなルートとなった場合に、自ノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知する手段とを有することを特徴とするノード。
【請求項15】
自ノードが前記無線ツリーネットワークから削除される場合には、子ノードを前記代理ノードとして指定することを特徴とする請求項14記載のノード。
【請求項16】
自ノードが前記無線ツリーネットワークへ追加される場合には、自ノードを前記代理ノードとして指定することを特徴とする請求項14又は15記載のノード。
【請求項17】
自ノードの親ノードが故障した場合には、自ノードを前記代理ノードとして指定することを特徴とする請求項14から16のいずれか1項記載のノード。
【請求項18】
自ノードが前記未接続の部分木に属する場合、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出することを特徴とする請求項14から17のいずれか1項記載のノード。
【請求項19】
前記未接続の部分木に属する他のノードも前記無線ツリーネットワークとの接続性を有する場合には、前記基地局までのホップ数が最小の場合にのみ前記部分木の新たなルートとなることを特徴とする請求項14から18のいずれか1項記載のノード。
【請求項20】
無線通信方式で接続された少なくとも一つのノードとともに無線ツリーネットワークを構成する基地局であって、
前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定する手段と、
階層構造が変更された前記未接続の部分木に属するいずれかのノードから、変更後の前記未接続の部分木の階層構造に関する情報を受信した場合に、該受信した情報に応じて前記ツリーネットワークの階層構造を表す情報を更新する手段とを有することを特徴とする基地局。
【請求項21】
請求項14から19のいずれか1項記載のノードを少なくとも一つと、請求項20記載の基地局とを有することを特徴とするマルチホップネットワークシステム。
【請求項1】
基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法であって、
前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定するステップと、
前記代理ノードが、自ノード又は子孫ノードと前記無線ツリーネットワークとの接続性を検出するステップと、
前記ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、
前記ツリーネットワークとの接続性を有するノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを有することを特徴とするネットワーク再構成方法。
【請求項2】
前記無線ツリーネットワークからノードを削除する際に、削除するノードの子ノードを前記代理ノードとして指定することを特徴とする請求項1記載のネットワーク再構成方法。
【請求項3】
前記無線ツリーネットワークへノードを追加する際に、追加するノードを前記代理ノードとして指定することを特徴とする請求項1又は2記載のネットワーク再構成方法。
【請求項4】
前記無線ツリーネットワークに属するノードが故障した際に、故障したノードの子ノードを前記代理ノードとして指定することを特徴とする請求項1から3のいずれか1項記載のネットワーク再構成方法。
【請求項5】
前記無線ツリーネットワークとの接続性を検出するステップにおいては、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出することを特徴とする請求項1から4のいずれか1項記載のネットワーク再構成方法。
【請求項6】
前記無線ツリーネットワークとの接続性を検出するステップにおいて前記無線ツリーネットワークとの接続性を有するノードが複数検出された場合には、前記基地局までのホップ数が小さいものを前記部分木のルートとして設定することを特徴とする請求項1から5のいずれか1項記載のネットワーク再構成方法。
【請求項7】
基地局と複数のノードとを無線通信方式で接続してなる無線ツリーネットワークにおけるネットワーク再構成方法を前記ノードに実行させるプログラムであって、
前記ノードを制御する実質的なコンピュータに、
前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定するステップと、
前記代理ノード又はその子孫ノードと前記無線ツリーネットワークとの接続性を検出するステップと、
前記ツリーネットワークと未接続の部分木に属し該ツリーネットワークとの接続性を有するノードが、該未接続の部分木のルートとなるように、該未接続の部分木の階層構造を変更するステップと、
前記ツリーネットワークとの接続性を有するノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知するステップとを実行させることを特徴とするネットワーク再構成方法のプログラム。
【請求項8】
自ノードが前記無線ツリーネットワークから削除される場合には、前記実質的なコンピュータに、子ノードを前記代理ノードとして指定させることを特徴とする請求項7記載のネットワーク再構成方法のプログラム。
【請求項9】
前記自ノードが前記無線ツリーネットワークへ追加される場合には、前記実質的なコンピュータに自ノードを前記代理ノードとして指定させることを特徴とする請求項7又は8記載のネットワーク再構成方法のプログラム。
【請求項10】
自ノードの親ノードが故障した場合には、前記実質的なコンピュータに、自ノードを前記代理ノードとして指定させることを特徴とする請求項7から9のいずれか1項記載のネットワーク再構成方法のプログラム。
【請求項11】
自ノードが前記未接続の部分木に属する場合、前記実質的なコンピュータに、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出させることを特徴とする請求項7から10のいずれか1項記載のネットワーク再構成方法のプログラム。
【請求項12】
前記未接続の部分木に属する他のノードも前記無線ツリーネットワークとの接続性を有する場合には、前記実質的なコンピュータに、前記基地局までのホップ数が最小の場合にのみ自ノードを前記部分木の新たなルートとさせることを特徴とする請求項7から11のいずれか1項記載のネットワーク再構成方法のプログラム。
【請求項13】
請求項7から12のいずれか1項記載のネットワーク再構成方法のプログラムが記録されたコンピュータが読み取り可能な情報記録媒体。
【請求項14】
無線通信方式で基地局と接続されて無線ツリーネットワークを構成するノードであって、
前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定する手段と、
前記代理ノードとして指定された場合に、自ノードの子孫ノードに対して前記無線ツリーネットワークとの接続性の有無の確認を要求する手段と、
前記無線ツリーネットワークとの接続性の有無を確認する手段と、
自ノードが前記未接続の部分木に属する場合に、前記代理ノードからの指示に応じて、前記無線ツリーネットワークとの接続性を有するノードが新たなルートとなるように該未接続の部分木の階層構造を変更する手段と、
自ノードが前記未接続の部分木の新たなルートとなった場合に、自ノードから前記基地局までの経路にある各ノードに対して、変更後の部分木の階層構造を通知する手段とを有することを特徴とするノード。
【請求項15】
自ノードが前記無線ツリーネットワークから削除される場合には、子ノードを前記代理ノードとして指定することを特徴とする請求項14記載のノード。
【請求項16】
自ノードが前記無線ツリーネットワークへ追加される場合には、自ノードを前記代理ノードとして指定することを特徴とする請求項14又は15記載のノード。
【請求項17】
自ノードの親ノードが故障した場合には、自ノードを前記代理ノードとして指定することを特徴とする請求項14から16のいずれか1項記載のノード。
【請求項18】
自ノードが前記未接続の部分木に属する場合、前記代理ノードとのホップ数が小さい順に前記無線ツリーネットワークとの接続性を検出することを特徴とする請求項14から17のいずれか1項記載のノード。
【請求項19】
前記未接続の部分木に属する他のノードも前記無線ツリーネットワークとの接続性を有する場合には、前記基地局までのホップ数が最小の場合にのみ前記部分木の新たなルートとなることを特徴とする請求項14から18のいずれか1項記載のノード。
【請求項20】
無線通信方式で接続された少なくとも一つのノードとともに無線ツリーネットワークを構成する基地局であって、
前記無線ツリーネットワークと未接続の部分木のルートを前記基地局の代理ノードとして指定する手段と、
階層構造が変更された前記未接続の部分木に属するいずれかのノードから、変更後の前記未接続の部分木の階層構造に関する情報を受信した場合に、該受信した情報に応じて前記ツリーネットワークの階層構造を表す情報を更新する手段とを有することを特徴とする基地局。
【請求項21】
請求項14から19のいずれか1項記載のノードを少なくとも一つと、請求項20記載の基地局とを有することを特徴とするマルチホップネットワークシステム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図18】
【図19】
【図20】
【図21】
【図22】
【図23】
【図24】
【公開番号】特開2006−237854(P2006−237854A)
【公開日】平成18年9月7日(2006.9.7)
【国際特許分類】
【出願番号】特願2005−47570(P2005−47570)
【出願日】平成17年2月23日(2005.2.23)
【出願人】(000004237)日本電気株式会社 (19,353)
【Fターム(参考)】
【公開日】平成18年9月7日(2006.9.7)
【国際特許分類】
【出願日】平成17年2月23日(2005.2.23)
【出願人】(000004237)日本電気株式会社 (19,353)
【Fターム(参考)】
[ Back to top ]