マルチホップ無線ネットワークの経路制御方法
【課題】マルチホップ無線ネットワークシステムにおけるツリートポロジの偏りを改善するには多大なコストが必要になること。
【解決手段】マルチホップ無線ネットワークは、複数の無線ノードから構成される。各無線ノードは、周囲の無線ノードから受信するノード情報に関する周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出し、算出したメトリック値に基づいて上位接続先ノードを決定する。マルチホップ無線ネットワークにおける特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジの偏りを改善するために、所定の無線ノードを目的の無線ノードとして選択し、この目的の無線ノードから周囲の無線ノードに送信するノード情報の値を故意に変更する。
【解決手段】マルチホップ無線ネットワークは、複数の無線ノードから構成される。各無線ノードは、周囲の無線ノードから受信するノード情報に関する周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出し、算出したメトリック値に基づいて上位接続先ノードを決定する。マルチホップ無線ネットワークにおける特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジの偏りを改善するために、所定の無線ノードを目的の無線ノードとして選択し、この目的の無線ノードから周囲の無線ノードに送信するノード情報の値を故意に変更する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、複数の無線ノードから構成され、特定の無線ノードとマルチホップ無線通信を行うネットワークシステムおよびその経路制御方法に関する。
【背景技術】
【0002】
この種のネットワークシステムとして、無線センサネットワークシステムがある。無線センサネットワークシステムにおいて、OLSR(Optimized Link State Routing),AODV(Ad hocのOn-Demand Distance Vector)などの無線マルチホップネットワークに適したルーティングプロトコルを適用して、シンクノードを送信先、センサノードを送信元とするパスを生成すると、結果として、シンクノードを頂点とし、節および葉の部分にセンサノードが位置するツリー構造のネットワークトポロジ(以降、ツリートポロジ)が構築される。但し、このとき、同じ階層の複数のノード間で子ノードの数に偏りが発生することがある。このような偏りは、特定のノードの負荷が増加する原因になるので、できるだけ解消する必要がある。
【0003】
ツリートポロジに生じた上記のような偏りを解消する経路制御方法の一例が特許文献1に記載されている。この技術では、特定の装置(ネットワーク構築装置30)が、生成されたツリートポロジに偏りが生じていることを検出すると、その偏りを解消するためには、どのノードをどのノードに接続替えすれば良いかを解析し、接続替え対象の各ノードに対してメッセージを送信して接続替えを実施する。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2010-166150号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、接続替え対象の各ノードに対してメッセージを送信して接続替えを実施する方法は、接続替え対象のノード数に比例したメッセージの送信とその応答のやりとりが必要になる。
【0006】
本発明の目的は、上述したような課題、すなわち、マルチホップ無線ネットワークシステムにおけるツリートポロジの偏りを改善するには多大なコストが必要になる、という課題を解決することにある。
【課題を解決するための手段】
【0007】
上記課題を解決するために、本発明の一形態にかかるマルチホップ無線ネットワークの経路制御方法は、
複数の無線ノードから構成され、それぞれの無線ノードが、周囲の無線ノードから受信するノード情報に関する周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出し、算出したメトリック値に基づいて上位接続先ノードを決定する、マルチホップ無線ネットワークの経路制御方法であって、
前記マルチホップ無線ネットワークにおける特定の無線ノードを根、その他の無線ノードを節および葉とするツリートポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、目的の無線ノードから周囲の無線ノードに送信するノード情報の値を故意に変更する、
といった構成を採る。
【発明の効果】
【0008】
本発明は上述したような構成を有するため、マルチホップ無線ネットワークシステムにおけるツリートポロジの偏りを少ないコストで解消することができる。
【図面の簡単な説明】
【0009】
【図1】本発明の第2の実施形態にかかる無線センサネットワークの物理的な構成例を示す図である。
【図2】本発明の第2の実施形態にかかる無線センサネットワークのノード間の接続関係を示す図である。
【図3】本発明の第2の実施形態にかかる無線センサネットワークのセンサノードのブロック図である。
【図4】本発明の第2の実施形態にかかる無線センサネットワークのシンクノードのブロック図である。
【図5】本発明の第2の実施形態にかかる無線センサネットワークの基本動作を示すタイムチャートである。
【図6】本発明の第2の実施形態にかかる無線センサネットワークの偏り是正前のツリートポロジを示す図である。
【図7】本発明の第2の実施形態にかかる無線センサネットワークのシンクノードが実施するトポロジ偏り是正処理の流れを示すフローチャートである。
【図8】本発明の第2の実施形態にかかる無線センサネットワークのシンクノードが有するネットワークデータベースの構成例を示す図である。
【図9】本発明の第2の実施形態にかかる無線センサネットワークの偏り是正後のツリートポロジを示す図である。
【図10】本発明の第3の実施形態にかかる無線センサネットワークのノード間の偏り是正前の接続関係を示す図である。
【図11】本発明の第3の実施形態にかかる無線センサネットワークのトポロジデータベースが保持するトポロジ情報(偏り是正前)の一例を示す図である。
【図12】本発明の第3の実施形態にかかる無線センサネットワークのトポロジデータベースが保持するトポロジ情報(偏り是正後)の一例を示す図である。
【図13】本発明の第3の実施形態にかかる無線センサネットワークのノード間の偏り是正後の接続関係を示す図である。
【図14】本発明の第1の実施形態にかかるマルチホップ無線ネットワークの物理的な構成例を示す図である。
【図15】本発明の第1の実施形態にかかるマルチホップ無線ネットワークの無線ノードのブロック図である。
【図16】本発明の第1の実施形態にかかるマルチホップ無線ネットワークの偏り是正前のトポロジを示す図である。
【図17】本発明の第1の実施形態にかかるマルチホップ無線ネットワークの偏り是正後のトポロジを示す図である。
【発明を実施するための形態】
【0010】
次に本発明の実施の形態について図面を参照して詳細に説明する。
[第1の実施形態]
図14を参照すると、本発明の第1の実施形態にかかるマルチホップ無線ネットワークシステムは、9個の無線ノード1〜9から構成される。無線ノードの数を9個としているのは説明の便宜上であり、本発明において無線ノードの数は任意である。
【0011】
各無線ノード1〜9は、図15の無線ノード10に示すように、周辺ノード情報取得部11、メトリック計算部12、および上位接続先ノード決定部13を有する。
【0012】
周辺ノード情報取得部11は、周囲の無線ノードに対して自無線ノードに関するノード情報を同報通信により送信する機能と、周囲の無線ノードから受信するノード情報に関する周辺ノード情報を取得する機能とを有する。本実施形態の場合、各無線ノード1〜9が周囲に送信するノード情報は、自ノードを一意に識別するノード識別子と、自ノードから特定の無線ノードまでのホップ数とから構成される。また、各無線ノード1〜9が周囲の無線ノードから受信するノード情報に関する周辺ノード情報は、上記ノード識別子と、上記ホップ数と、当該ノード情報を受信した際の受信強度(無線信号の強度)とから構成される。ここで、本実施形態は、無線ノード1を上記特定の無線ノードとしており、他の無線ノード2〜9が無線ノード1とパケット通信するものとする。
【0013】
メトリック計算部12は、周辺ノード情報取得部11で取得された周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出する機能を有する。本実施形態の場合、各無線ノード1〜9は、受信したノード情報に含まれるホップ数と、当該ノード情報を受信した際の受信強度とを用い、メトリック値Mを以下の計算式で計算する。
M=Meh(e、h) …(1)
ここで、Meh(e、h)は、ホップ数hと受信強度eとを引数として、ホップ数hがより大きくなるほど、また受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。また、メトリック値は、リンクの通信コストが小さくなるほど小さくなる値であるとする。
【0014】
上位接続先ノード決定部13は、メトリック計算部12により算出されたメトリック値に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードを決定する機能を有する。上位接続先ノード決定部13は、周囲のノード毎に算出したメトリック値のうち最も小さなメトリック値となった周囲ノードを、上位接続先ノードに選択する。
【0015】
他方、上記9個の無線ノード1〜9とは別に制御ノードが存在する。或いは9個の無線ノード1〜9の何れかが制御ノードとして機能する。本実施形態では、無線ノード1が制御ノードとして機能する例について説明する。
【0016】
制御ノードとして機能する無線ノード1は、図15に示すように、周辺ノード情報11、メトリック計算部12、上位接続先ノード決定部13に加えてさらに、ネットワーク管理部14を有する(制御ノード以外の無線ノードはネットワーク管理部14が無くてもよい)。ネットワーク管理部14は、マルチホップ無線ネットワークにおける特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジを生成する機能と、この生成した木構造のネットワークトポロジにおける所定の無線ノードを目的の無線ノードとして選択する機能と、この目的の無線ノードから周囲の無線ノードに送信するノード情報の値を故意に変更する機能とを有する。
【0017】
ネットワーク管理部14が有するネットワークトポロジ生成機能について説明する。本実施形態の場合、無線ノード1は他の無線ノード2〜9からマルチホップ無線通信によってパケットを受信する。このとき、受信するパケットには、送信元の無線ノードの識別子と中継点の無線ノードの識別子とを含む通信履歴が付加されている。ネットワーク管理部14は、この通信履歴に基づいて上記のネットワークトポロジを生成する。あるいは、ネットワーク管理部14は次のような方法でネットワークトポロジを生成してよい。各無線ノードが上位接続先ノードを決定した際、決定した上位接続先ノードに対して、自ノードが子ノードとして存在することを認識させるための通知が行われる。この通知を受信した上位接続先ノードが、この通知を制御ノードである無線ノード1に転送する。無線ノード1は、この転送されてきた情報に基づいて、どの無線ノードの下位にどの無線ノードが存在するか、すなわちネットワークトポロジを把握する。
【0018】
ネットワーク管理部14が有する目的の無線ノードを選択する機能について説明する。本実施形態の場合、無線ノード1は、木構造のネットワークトポロジにおける同階層の他の無線ノードに比較して下位の無線ノード数が多い無線ノードを目的の無線ノードとして選択する。例えば、ネットワーク管理部14は、ネットワークトポロジのルート階層以外の階層毎に、その階層に属する各無線ノードの下位ノード数(子ノード、孫ノードを含む子孫ノードの数)を調査し、平均や中央値や標準偏差や最大値や最小値などと比較して、下位ノード数の偏り箇所を検出する。例えば、或る階層にA、B、C、Dの4つのセンサノードがあり、各々の下位ノード数が、Aは10台、Bは33台、Cは9台、Dは5台であった場合、平均を求めると約15台になる。このとき、例えば平均値の2倍以上のノード数となる箇所を偏り箇所として検出するものと予め定められている場合、ノードBが目的の無線ノードとして検出される。
【0019】
ネットワーク管理部14が有するノード情報変更機能について説明する。ネットワーク管理部14は、目的の無線ノードから周囲の無線ノードに送信するノード情報を、目的の無線ノードを上位接続先ノードの候補として計算されるメトリック値がリンクの通信コスト的に大きくなるように変更する制御を実施する。具体的には、変更を要求するメッセージを目的の無線ノードに送信し、その応答を受信する。本実施形態の場合、無線ノードから周囲の無線ノードに送信されるノード情報は、ノード識別子とホップ数であり、メトリック値が上記(1)式によって計算される。このため、ネットワーク管理部14は、目的の無線ノードから周囲の無線ノードに送信するホップ数を、実際のホップ数よりも大きな数に変更する。どの程度大きくするかは任意である。予め定められた数(例えばホップ数1)だけ大きくしても良いし、あるいは予め定められた割合(例えば5割)を実際のホップ数に加算した後に四捨五入等しても良い。
【0020】
次に本実施形態の動作を説明する。
【0021】
無線ノード1〜9は、周辺ノード情報取得部11によって、例えば定期的に、無線ノード1からのホップ数を含むノード情報を周囲の無線ノードに送信する。初期の状態において、無線ノード1からのホップ数を認識しているのは無線ノード1のみであるため、無線ノード1がホップ数0を、同報通信により周囲の無線ノードに送信する。今、この同報通信を受信した無線ノードが無線ノード2と無線ノード3との2つの無線ノードであったとする。無線ノード2、3は、メトリック計算部12を用いて、無線ノード1から受信したホップ数0と受信強度とに基づいて、無線ノード1を上位接続先ノードの候補としてメトリック値を計算し、上位接続先ノード決定部13により無線ノード1を上位接続先ノードに決定する。このとき、無線ノード2、3で計算された無線ノード1のメトリック値は、それぞれ2.0と3.0であったとする。
【0022】
次に、無線ノード2、3は、上位接続先ノードに決定した無線ノード1までのホップ数1を同報通信により周囲の無線ノードに送信する。無線ノード2からの同報通信を受信した無線ノードは、無線ノード1を除いて、無線ノード4、5、6、7の4台であり、無線ノード3からの同報通信を受信した無線ノードは、無線ノード1を除いて、無線ノード7、8、9の3台であったとする。
【0023】
無線ノード4、5、6は、無線ノード2から受信したホップ数1と受信強度とに基づいて、無線ノード2を上位接続先ノードの候補としてメトリック値を計算し、無線ノード2を上位接続先ノードに決定する。このとき、無線ノード4、5、6で計算された無線ノード2のメトリック値は、それぞれ5.0であったとする。同様に、無線ノード9は、無線ノード3から受信したホップ数1と受信強度とに基づいて、無線ノード3を上位接続先ノードの候補としてメトリック値を計算し、無線ノード3を上位接続先ノードに決定する。このとき、無線ノード9で計算された無線ノード3のメトリック値は6.0であったとする。
【0024】
他方、無線ノード7と無線ノード8は、無線ノード2、3の双方からノード情報を受信している。無線ノード7と無線ノード8は、無線ノード2、3のそれぞれを上位接続先ノードの候補としてメトリック値を計算し、メトリック値の小さい方を上位接続先ノードに決定する。今、無線ノード7で計算された無線ノード2のメトリック値が4.5、無線ノード3のメトリック値が5.5であり、無線ノード8で計算された無線ノード2のメトリック値が5.0、無線ノード3のメトリック値が5.5であったとする。すなわち、ホップ数は共に2だが、受信強度の相違によってこのような結果になったとする。すると、無線ノード7、8は、共に無線ノード2を上位接続先ノードに決定する。
【0025】
以降、無線ノード4〜9からノード情報が周囲に送信され、また無線ノード1〜3からも再度ノード情報が周囲に送信され、これを受信した無線ノードにおいてメトリック値の計算、上位接続先ノードの決定が繰り返される。ここでは、上位接続先ノードの決定結果に変化がなかったものとする。このとき、無線ノード1を根、無線ノード2〜9を節あるいは葉とする木構造のネットワークトポロジは図16に示すようになる。
【0026】
図16において、無線ノード間を上下に結ぶ実線は、下側の無線ノードが上側の無線ノードを上位接続先ノードとして選択していることを示す。また無線ノード間を上下に結ぶ破線は、下側の無線ノードが上側の無線ノードを上位接続先ノードの候補としているが、他にメトリック値の小さな上位接続先ノード候補が存在しているために棄却されたことを示している。また、実線および破線に付記された数値は、下側の無線ノードが上側の無線ノードを対象として計算したメトリック値を示す。この図16を参照すると、無線ノード2の下位ノード数は5であり、同じ階層の無線ノード3の下位ノード数1と大きな偏りがある。
【0027】
制御ノードである無線ノード1のネットワーク管理部14は、図16に示したようなネットワークトポロジを生成し、同階層の他の無線ノードに比較して下位の無線ノード数が多い無線ノード2を目的の無線ノードとして選択する。続いて無線ノード1のネットワーク管理部14は、無線ノード2から周囲の無線ノードに送信するホップ数を、例えば実際のホップ数1に予め定められた数である1を加算した2に変更すべく、無線ノード2に対して変更要求メッセージを送信する。無線ノード2の周辺ノード情報取得部11は、この変更要求メッセージを受信すると、その応答を無線ノード1に返した後、実際とは異なるホップ数2を周囲に送信する。他方、無線ノード3は、依然として実際のホップ数1を周囲に送信している。
【0028】
無線ノード2からの同報通信を受信した無線ノードは、以前の状況と同じく、無線ノード1を除いて、無線ノード4、5、6、7の4台であり、無線ノード3からの同報通信を受信した無線ノードは、無線ノード1を除いて、無線ノード7、8、9の3台であったとする。
【0029】
無線ノード4、5、6は、無線ノード2から受信したホップ数2と受信強度とに基づいて、無線ノード2を上位接続先ノードの候補としてメトリック値を計算し、無線ノード2を上位接続先ノードに決定する。このとき、無線ノード4、5、6で計算された無線ノード2のメトリック値は、それぞれ6.5であったとする。同様に、無線ノード9は、無線ノード3から受信したホップ数1と受信強度とに基づいて、無線ノード3を上位接続先ノードの候補としてメトリック値を計算し、無線ノード3を上位接続先ノードに決定する。このとき、無線ノード9で計算された無線ノード3のメトリック値は6.0であったとする。
【0030】
他方、無線ノード7と無線ノード8は、無線ノード2、3の双方からノード情報を受信している。無線ノード7と無線ノード8は、無線ノード2、3のそれぞれを上位接続先ノードの候補としてメトリック値を計算し、メトリック値の小さい方を上位接続先ノードに決定する。今、無線ノード7で計算された無線ノード2のメトリック値が6.0、無線ノード3のメトリック値が5.5であり、無線ノード8で計算された無線ノード2のメトリック値が6.5、無線ノード3のメトリック値が5.5であったとする。すなわち、受信強度は以前の状況と同じであったとしても、ホップ数は無線ノード2が2ホップ、無線ノード3が1ホップと相違するためにこのような結果になったとする。すると、無線ノード7、8は、共に無線ノード3を上位接続先ノードに決定する。
【0031】
以降、無線ノード4〜9からノード情報が周囲に送信され、また無線ノード1〜3からもノード情報が周囲に送信され、これを受信した無線ノードにおいてメトリック値の計算、上位接続先ノードの決定が繰り返される。ここでは、上位接続先ノードの決定結果に変化がなかったものとする。このとき、無線ノード1を根、無線ノード2〜9を節あるいは葉とする木構造のネットワークトポロジは図16から図17に示すように変化する。
【0032】
図17を参照すると、無線ノード2の下位ノード数は5から3に変化しており、結果的に同じ階層の無線ノード3の下位ノード数3と等しくなっている。
【0033】
このように本実施形態によれば、マルチホップ無線ネットワークシステムにおけるツリートポロジの偏りを少ないコストで解消することができる。例えば、上述した例の場合、制御ノードである無線ノード1から無線ノード2に対して変更要求メッセージが1回送信され、その応答が無線ノード2から無線ノード1に1回送信される。無線ノード1から無線ノード2までは1ホップなので、総送信回数は2回である。これに対して、無線ノード1から無線ノード7、8に対して上位接続先ノードを無線ノード2から無線ノード3に切り替えるよう要求するメッセージを送信し、無線ノード7、8からその応答を無線ノード1に返す場合、無線ノード1から無線ノード7、8までは2ホップなので、総送信回数は8回となる。
【0034】
本実施形態では、無線ノードから周囲に送信するノード情報がノード識別子とホップ数とから構成されているとしたが、ホップ数に代えて、あるいはホップ数に加えて他のデータを用いてもよい。例えば、ホップ数に代えて、あるいはホップ数に加えて、自ノードを上位接続先ノードとして選択している無線ノードの数である子ノード数を用いてもよい。この場合、メトリック値Mは以下の計算式で計算してよい。
M=Mek(e、k) …(2)
M=Mehk(e、h、k) …(3)
ここで、Mek(e、k)は、受信強度eと子ノード数kとを引数として、子ノード数kがより多くなるほど、また受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。またMehk(e、h、k)は、受信強度eとホップ数hと子ノード数kとを引数として、ホップ数hおよび子ノード数kがより多くなるほど、また受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。そして、その場合には、実際の値と異なる値に故意に変更する対象をホップ数と子ノード数、あるいは子ノード数だけにしてもよい。
【0035】
また本実施形態では、無線ノードから周囲に送信するノード情報がノード識別子とホップ数とから構成されているとしたが、ホップ数に代えて、あるいはホップ数に加えて、自ノードが上位接続先ノードを決定する際に計算した当該上位接続先ノードのメトリック値を用いてもよい。例えば、図16の場合、無線ノード2は、無線ノード1のメトリック値2.0を含むノード情報を周囲に送信する。この場合、メトリック値Mは以下の計算式で計算してよい。
M=Mem(e、m) …(4)
M=Mehm(e、h、m) …(5)
ここで、Mem(e、m)は、受信強度eとメトリック値mとを引数として、メトリック値mがより大きくなるほど、また受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。またMehm(e、h、m)は、受信強度eとホップ数hとメトリック値mとを引数として、ホップ数hがより多くなるほど、メトリック値mがより大きくなるほど、受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。そして、その場合には、実際の値と異なる値に故意に変更する対象をホップ数hとメトリック値m、或いはメトリック値mだけにしてもよい。
また、メトリック値の計算に、重み付けパラメータの値であるハンディキャップ値を使用し、上記の計算式(1)〜(5)を以下の計算式のように変形してもよい。
M=Meh(e、h)+α …(1’)
M=Mek(e、k)+α …(2’)
M=Mehk(e、h、k)+α …(3’)
M=Mem(e、m)+α …(4’)
M=Mehm(e、h、m)+α …(5’)
上記の計算式(1’)〜(5’)において、αはハンディキャップ値を示す。ハンディキャップ値αの初期値は0である。そしてこの場合、ツリートポロジの偏りを解消するために、ハンディキャップ値αの値を設定あるいは変更するようにしてもよい。すなわち、制御ノードである無線ノード1は、ツリートポロジの偏りを解消するために、目的の無線ノード2のハンディキャップ値を設定あるいは変更し、変更後のハンディキャップ値を変更要求メッセージで無線ノード2へ送信する。無線ノード2の周辺ノード情報取得部11は、この変更要求メッセージを受信すると、その応答を無線ノード1に返した後、ノード情報中の一つの情報としてハンディキャップ値を周囲に送信する。このノード情報を受信した周囲の無線ノードは、受信したノード情報に含まれる変更後の最新のハンディキャップ値を用いて無線ノード2を上位接続先ノード候補としてメトリック値を計算する。
【0036】
また本実施形態では、特定の無線ノードを唯一つとしたが、2以上の特定の無線ノードが存在していてもよい。この場合、特定の無線ノード以外の無線ノードは、複数の特定の無線ノードと通信するのではなく、よりメトリック値の小さな1つの特定の無線ノードと通信する。従って、特定の無線ノードが複数存在する場合、特定の無線ノードの数だけ、ツリートポロジが形成される。そして、複数のツリートポロジ間に帰属する無線ノード数の偏りが発生する場合、特定の無線ノードから周囲に送信するノード情報に含まれるホップ数、子ノード数、メトリック値、ハンディキャップ値といったデータを故意に変更することにより、上記偏りを解消する制御を実施してもよい。
【0037】
また本実施形態では、トポロジにおける同階層の他の無線ノードに比較して下位の無線ノード数が多い無線ノード2を目的の無線ノードとして選択したが、トポロジにおける同階層の他の無線ノードに比較して下位の無線ノード数が少ない無線ノード3を目的の無線ノードとして選択してもよい。この場合、無線ノード3が周囲に送信するホップ数を、無線ノード3を上位接続先ノードの候補として計算されるメトリック値がリンクの通信コスト的に小さくなるように変更すればよい(すなわち、実際より少ないホップ数を周囲に送信する)。ホップ数を実際のホップ数よりも小さな値に設定する際は、トポロジ構築時にループが発生する可能性があるため、ループ回避の処理を組み込む必要がある。ただし、本発明ではループ回避の処理については、範囲外であるため詳細には言及しない。
【0038】
[第2の実施形態]
次に本発明の第2の実施形態について詳細に説明する。
【0039】
[背景]
温度や湿度などの環境情報を収集する環境計測システムに適用される無線センサネットワークでは、各ノード(センサノード)がセンシングしたデータを一つのノード(シンクノード)に集める必要がある。そのため、ネットワークトポロジとしては、シンクノードを頂点としたツリートポロジを構築するのが一般的である。このツリートポロジは一般的に無線マルチホップネットワークに適したルーティングプロトコルにより構築される。
【0040】
無線マルチホップネットワークに用いられるルーティングプロトコルには、プロアクティブ型のルーティングプロトコルと、リアクティブ型のルーティングプロトコルがある。プロアクティブ型のプロトコルの代表例はOLSR(Optimized Link State Routing)プロトコルである。リアクティブ型のプロトコルの代表例は、AODV(Ad hoc On-Demand Distance Vector)プロトコルやDSR(Dynamic Source Routing)プロトコルである。OLSRやAODVやDSRは、IETF(Internet Engineering Task Force)により規定されたプロトコルである。
【0041】
これらのルーティングプロトコルでは、受信強度やホップ数に基づいて、シンクノードまでのコストをあらわすメトリック値を算出し、算出されたメトリック値に基づいたネットワークトポロジが構築される。そのため、無線センサネットワークでこれらのルーティングプロトコルを適用した場合、それぞれのセンサノードはシンクノードまでのリンクの通信コストが最小のパス(経路)を選択し、ネットワークトポロジを構築する。
【0042】
また、ネットワークトポロジの最適化・平準化方法については規定がなく、ルーティングプロトコルにて作成されたトポロジをそのまま用いるか、各システムにて個別の対応を行っている。このため、次のような課題がある。
【0043】
第1の課題は、センサノードはシンクノードまでの最小のパスを選択するため、ネットワークトポロジに接続しているノード数に偏りが発生することで、通信帯域を有効に利用できないことである。
【0044】
第2の課題は、ネットワークトポロジ平準化のために、各ノードに接続先変更メッセージを送信する際に、参加しているノードをどれだけ(台数)何処へ(場所)どの様に(トポロジの形状)移動させるかを調整するための処理が増大し、管理サーバの負荷が増大することである。
【0045】
第3の課題は、ネットワークトポロジの偏りを平準化するためには、各ノードに接続先変更メッセージを送信する必要があり、通信帯域を圧迫することである。
【0046】
本実施形態の目的は、無線センサネットワークにおいて、ツリートポロジの平準化を低コスト(少ない通信量と計算量)で実現する方法を提供することである。
【0047】
[概要]
本実施形態は、センサデータを収集する無線センサネットワークシステムにおいて、ツリートポロジを構築する際に、ツリートポロジの各枝の構成ノード数に偏りが生じた場合に、少ない通信量と計算量でノード数を平準化し、負荷分散する。
【0048】
無線センサネットワークを構成する各ノードは、ノード情報を送信すると共に周辺ノード情報を取得する周辺ノード情報取得手段と、センサデータを収集するシンクノードへのコストを表すメトリック値を計算するメトリック計算手段と、メトリック計算手段により計算されたメトリック値を基に接続するノードを決定する接続先ノード決定手段とにより、自律的にシンクノードを頂点としてクラスタリングされたツリートポロジを構築する。その際、ツリートポロジ内の各枝間に下位ノード数の偏りが発生する可能性がある。本実施形態では、各枝間の下位ノード数の偏りを解消させる目的で、所定のセンサノードから周囲のノードに送信するシンクノードまでのホップ数を強制的に変更することで、各枝間のノードの移動を促し、下位ノード数の平準化を行う。
【0049】
このようにして、本実施形態では、自律的にネットワークトポロジを構築するネットワークにおいて、トポロジ構築に使用するホップ数を故意に変更することで、少ない計算量と通信量にて無線センサネットワークにおけるツリートポロジのノード数を平準化することで、負荷分散ができるようにする。以下、本実施形態の構成、動作を説明する。
【0050】
[構成]
図1を参照すると、本実施形態としてのシンクノードとセンサノードを使用した物理的な構成が示されている。図1において、シンクノード201は、センサノード202〜211がセンシングした情報をこれらセンサノード202〜211から収集する装置である。センサノード202〜211は、屋内、もしくは、屋外に設置され、外界の情報をセンシングし、センシングした情報をシンクノード201に対して送信を行う。なお、図1において、各ノード間を結ぶ折れ線は無線にて通信を行う関係を表したものである。
【0051】
図2を参照すると、シンクノード201とセンサノード202〜211の接続関係が論理的に示されている。図2において、ノード間を結ぶ直線は無線にて通信を行う関係を表したものである。本実施形態は、図2に表すようにツリートポロジを構成し、シンクノード201を起点としてセンサノード202〜211がセンシングした情報を収集する構成が基本構成である。
【0052】
図3を参照すると、センサノードの内部構成が示されている。図3において、センサノード30は、図1および図2に示したセンサノード202〜211の何れかである。センサノード30は、無線通信部301とルーティング機能部302とアプリケーション部303とセンサ部304とを有する。
【0053】
無線通信部301は、ルーティング機能部302からの無線通信データの送受信と、他のノードとの無線通信を行う機能である。無線通信部301は、無線LANやZigBee、省電力無線などの無線通信を行うことのできるモジュールもしくは回路にて構成される。
【0054】
ルーティング機能部302は、ルーティングテーブル3021とメトリック計算部3022と周辺ノード情報取得部3023とパケット送受信部3024とで構成される。
【0055】
ルーティングテーブル3021は、周辺ノード情報取得部3023から得られるノード識別情報や受信感度、シンクノードまでのホップ数といった周辺ノード情報を格納するテーブルであり、周辺ノード情報とともにメトリック計算部3022で算出されたメトリック値、上位ノードや下位ノードといったツリートポロジの情報も格納されており、パケットの送信先を決定するためのテーブルである。
【0056】
メトリック計算部3022は、周辺ノード情報取得3023から得られるノード識別情報や受信強度、シンクノードまでのホップ数などから、該当するノードとのリンクのメトリック値を算出し、上位接続先ノードを決定する機能である。
【0057】
周辺ノード情報取得部3023は、受信したパケットのメッセージからノードの識別情報とそのパケットの受信強度などを取得する機能である。また、周辺ノード情報取得部3023は、周囲のノードに自ノードのノード情報として、ノード識別子およびシンクノードまでのホップ数などを送信する機能を有する。
【0058】
パケット送受信部3024は、無線通信部301とのパケットを送受信する機能とアプリケーション部303とのデータパケットを送受信する機能とを有する。また、本パケット送受信部3024は、無線通信部301から受信したパケットが自ノード宛てではないが、転送が必要な場合は再転送する機能も有する。
【0059】
アプリケーション部303は、センサ情報取得部3031とデータパケット送信部3032とで構成される。
【0060】
センサ情報取得部3031は、センサ部304がセンシングしたデータを取得する機能である。
【0061】
データパケット送信部3032は、センサ情報取得部3031が取得したセンサデータをデータパケットとして送信する機能である。
【0062】
センサ部304は、温度や湿度、電力など所定の物理量をセンシングする機能と、センシングした物理量のデータをアプリケーション部303へ通知する仕組みを有する。
【0063】
なお、本実施形態では、無線通信部301で使用する無線規格を無線LANやZigBee、省電力無線としているが、無線通信を行えればよく、Bluetoothといった他の無線通信規格を使用してもよい。メトリック計算部3022において、周辺ノード情報取得部3023から取得する情報を、ノード識別情報や受信強度、シンクノードまでのホップ数としているが、計算に使用する情報は、周辺ノード情報取得部3023が取得できる情報であればよく、バッテリー残容量など周辺ノードに関連する情報を用いて計算してもよく、特に限定しない。周辺ノード情報取得部3023において、取得する情報をノード識別情報とパケット受信強度などとしているが、周辺ノードに関連する情報であればよく、特に限定しない。センサ部304において、センシングする物理量を温度や湿度、電力量としているが、センシングする物理量は例示している3種以外であってもセンシング可能な情報であればよいため、特に限定しない。
【0064】
図4を参照すると、シンクノードの内部構成が示されている。図において、シンクノード40は、図1および図2のシンクノード201に対応する。シンクノード40は、無線通信部301とルーティング機能部302とアプリケーション部403とデータベース404とネットワーク管理部405を有する。
【0065】
無線通信部301とルーティング機能部302については、図3に示したセンサノード30の無線通信部301とルーティング機能部302と同一の機能である。
【0066】
アプリケーション部403は、データベース管理部4031とデータパケット受信部4032とで構成される。
【0067】
データベース管理部4031は、データパケット受信部4032から得られるセンサデータをデータベース404に書き込む機能である。
【0068】
データパケット受信部4032は、ルーティング機能部302からデータパケットを受信する機能と、受信したパケットからノード識別情報とセンサデータとを取り出し、データベース管理部4031へ渡す機能を有する。
【0069】
データベース404は、アプリケーション部403から得られるノード識別情報とセンサデータとを対応付けて格納するデータベースである。
【0070】
ネットワーク管理部405は、トポロジ管理部4051と演算部4052とで構成される。
【0071】
トポロジ管理部4051は、演算部4052において導きだされたツリートポロジの情報を、ネットワークデータベース406へ格納する。また、周期的にツリートポロジの情報を監視し、偏りがある場合は、演算部4052に平準化処理を依頼する。さらに、演算部4052で平準化用に算出したホップ数を、該当ノードへ反映するために、ルーティング情報をネットワークデータベース406から取得し、値変更メッセージパケットを作成した後、ルーティング機能部302を通して該当ノードへ通知する。
【0072】
演算部4052は、センサノードから受信したパケット上のルーティング情報をルーティング機能部302から取得し、ネットワークデータベース406に格納済みのルーティング情報と統合することでセンサネットワーク全体のツリートポロジを導出する。また、トポロジ管理部4051から平準化処理を依頼された場合は、ネットワークデータベース406にアクセスし、導き出したツリートポロジにおけるノード数偏りの平準化を行うために該当ノードへ設定するホップ数の算出を行い、トポロジ管理部4051へ通知する。
【0073】
ネットワークデータベース406は、ネットワーク管理部405から得られるトポロジ情報とルーティングデータとを格納するデータベースである。
【0074】
なお、本実施形態では、シンクノード40上のデータベース404へセンサデータを、ネットワークデータベース406にツリートポロジ情報をそれぞれ格納しているが、別途設置したサーバにデータベース404とネットワークデータベース405の機能を搭載する構成としてもよい。
【0075】
[動作]
次にシンクノードとセンサノードの基本動作を図5に示すタイムチャートを使用して説明する。
【0076】
図5は、プロアクティブ型のルーティングプロトコルを動作させた場合の例である。プロアクティブ型のルーティングプロトコルでは、各センサノードが定期的にネットワークトポロジ構築処理を実施し、接続先ノードを決定することでツリートポロジが構築される。図5のタイムチャートは、センサノード502がツリートポロジ構築処理を実施した場合の動作を示している。図5において、センサノード502、503は図1および図2のセンサノード202〜211の何れか2つのセンサノードを示している。
【0077】
図5において、センサノード502が周辺ノード情報取得504を実施し、周辺探索メッセージをブロードキャストで送信している。ブロードキャストとは、あて先のアドレスにブロードキャストアドレスを指定し、すべてのノードに対して送信する送信方法である。なお、周辺探索メッセージには、センサノード502のネットワークトポロジへの参加状況やシンクノードまでのホップ数などを含んでいる。
【0078】
周辺探索メッセージを受信したシンクノード201とセンサノード503は、それぞれ周辺探索メッセージに対する周辺探索応答メッセージをユニキャストで送信する(505、506)。ユニキャストとは、あて先アドレスにノードのアドレスを指定することで、そのノードに対して送信する送信方法である。なお、周辺探索応答メッセージには、ネットワークトポロジへの参加状況やシンクノードまでのホップ数などを含んでいる。
【0079】
周辺探索応答メッセージを受信したセンサノード502は、周辺探索応答メッセージに含まれるツリートポロジへの参加状況やシンクノードまでのホップ数などを取得する。また、周辺探索応答メッセージを受信した際の受信強度についても取得する。
【0080】
このように、周辺ノード情報取得504により、周辺探索メッセージと周辺探索応答メッセージとを周辺のノード間で送受信することで、周辺の通信可能なノードの周辺ノード情報を取得することができる。
【0081】
次に、メトリック計算507を実施する。メトリック計算507は、周辺ノード情報取得504により得られた周辺ノード情報から、周辺のノード毎に、自ノードからシンクノードまでのパスのコストを示すメトリック値を計算する処理である。ルーティングプロトコルごとに異なるが、ここでは、取得した周辺ノード情報の受信強度とシンクノードまでのホップ数とからメトリック値を計算する。なお、本実施形態は、コストが小さい値であるほどシンクノードまでの通信状況が有利となるルーティングプロトコルを適用した場合である。
【0082】
次に、ルーティングテーブル更新508を実施する。ルーティングテーブル更新508は、メトリック計算507で算出した周辺ノードのメトリック値をルーティングテーブルへ書き込む処理である。
【0083】
次に、接続先ノード決定509を実施する。接続先ノード決定509は、ルーティングテーブル上で最もメトリック値が小さい(コストが低い)ノードを選出する。選出した結果、現在接続中のノードであるかどうかを確認し、現在接続中のノードではない場合は接続先変更処理510を実施する。接続先変更処理510は、新たな接続先となった上位接続先ノードに対して自ノードが子ノードとして存在することを知らせる処理である。接続先変更処理510によるメッセージを受信した上位接続先ノードは通信元のノードを子ノードとして認識すると共に、このメッセージをシンクノード201に転送する。
【0084】
上記の処理を繰り返し実施することにより、ネットワークトポロジが構築されることとなる。
【0085】
図2は上記処理を実施することで作成されたネットワークトポロジ図であり、トポロジに偏りがある。以下、この偏りを是正し、トポロジを平準化する処理の概要を説明する。
【0086】
図2を参照すると、シンクノード201を頂点としたツリートポロジとなっており、シンクノードからの最大ホップ数は3ホップである。また、センサノードで子ノードを持つノード(センサノード202,203,204,206)は、クラスタヘッドノードと呼ばれる。図2の例では、クラスタヘッドノード206が最も多く子ノードを収容しており、その数は3台である。
【0087】
図6を参照すると、図2の論理的な構成図上の各リンクにメトリック値を追記したものである。各ノード間の点線は、接続は可能であるが、トポロジ構成時に接続先として選択されなかったリンクを示している。
【0088】
図6のツリートポロジにおいて、2ホップ目に注目すると、センサノード204の子ノード数は1台、センサノード206の子ノード数は3台、センサノード205,207の子ノードは無く、センサノード206に多くの子ノードが接続しており、ツリートポロジの下位ノード数に偏りがある。この状況では、センサノード206は、下位ノードを管理するのに他の2ホップ目のノード(204,205,207)の3倍以上のメモリを使用し、センサデータ収集時は他の2ホップ目のノード(204,205,207)の3倍以上のデータを転送することになり、処理負荷およびネットワーク負荷ともに高い状況となっている。
【0089】
本実施形態では、図6のツリートポロジにおいてセンサノード206の負荷を、データ通信量を少なく、センサノード206から周囲に送信するシンクノードまでのホップ数を変更させることで、処理負荷およびネットワーク負荷を軽減させる。処理内容について、図7の処理フローを用いて説明する。
【0090】
図7を参照すると、トポロジ偏り周期監視701をシンクノード201では周期的に実施する。周期監視は1時間毎であってもよいし、1月毎といった長期間であってもよい。ただし、短時間で周期監視する設定にした場合は、シンクノードでの処理負荷が上がることや、長期間で周期監視する設定にした場合は、ツリートポロジにおけるノード数の偏りが継続することで特定リンクの通信負荷が解消されないこととなるため、参加しているノード数などから周期時間を設定するとよいが、特に限定しない。本実施形態ではセンシングの対象を電力メータの電力使用量であるものとし、それを考慮して、トポロジ偏り周期監視701の周期は1日とするが、特に限定しない。
【0091】
次に、一日ごとに実施されるトポロジ偏り周期監視701により、ネットワークデータベース調査702が実行される。ネットワークデータベース調査702は、トポロジ管理部4051が、ネットワークデータベース406に格納されているツリートポロジ情報から偏りがあるかどうかを調査する。
【0092】
図8はネットワークデータベース406に格納されているツリートポロジ情報の構成例である。ネットワークデータベース406は、ノード201〜211のノード識別子に対応して、ノード201までのホップ数、上位接続先ノード、当該上位接続先ノードのメトリック値、子ノード数、変更フラグ、変更値とを保持している。例えば6行目は、センサノード206は、シンクノード201までのホップ数は2であり、シンクノード201と通信する際の上位接続先ノードはセンサノード203であり、センサノード203を上位接続先ノードとして選択した際にセンサノード203に対して計算したメトリック値は4.0であり、子ノード数は3であり、変更フラグは0(変更なし)であり、変更値は未設定であることを示している。なお、ツリートポロジ情報に格納する情報は図8に記載した情報に限定されない。例えば、周辺に存在するセンサノードの識別子やそのノードを上位接続先ノード候補とした際に計算したメトリック値が追加されていても良いし、ルーティング情報や各ノードの接続状況などの情報が追加されていてもよい。
【0093】
図8のツリートポロジ情報から、ホップ数が1のノードは2台(202,203)あり、それぞれ子ノードが2台接続している。ホップ数が2のノードは4台(204,205,206,207)あり、子ノードの接続台数はセンサノード206に3台、センサノード204に1台、その他のノードには0台である。ホップ数が3のノードは4台(208,209,210,211)あり、すべてのセンサノードで子ノードの接続台数は0台である。この結果から、ホップ数が2のノードにおいて、下位ノード数に偏りがあることが分かり、トポロジ偏り判定703にて、『偏りあり』の方向へ処理が進む。偏りがないと判断した場合は、特に処理を行わず次の周期まで待機する。
【0094】
変更値算出704は、ツリートポロジにおけるノード数の偏りを解消するために、センサノード206が周辺探索メッセージにおいて通知するホップ数を算出する処理である。本実施形態では、変更値算出704は、センサノード206が周辺探索メッセージにおいて通知するホップ数を実際のホップ数2に1を加えたホップ数3へ変更すると算出し、ツリートポロジのノード数の平準化を行う。変更値の算出には、ツリートポロジ情報80上のデータのみを使用してもよいし、位置情報や消費電力量など他の情報を加えて算出してもよい。算出した変更値は、図8のツリートポロジ情報に記録される。
【0095】
次に、変更メッセージ作成705では、トポロジ管理部4051が算出したホップ数の変更値をルーティング機能部302に通知し、パケット送受信部3024が該当のノード(センサノード206)へ要求を出すためのメッセージを作成する。その後、変更通知送信706の処理において、無線通信部301を通して送信を行う。この変更要求メッセージは、センサノード203を中継してセンサノード206へ届けられる。
【0096】
センサネットワーク206は、上記変更要求メッセージを無線通信部301を通して、ルーティング機能部302で受信する。受信した変更要求メッセージの内容は、パケット送受信部3024から周辺ノード情報取得部3023へ通知され、周辺ノード情報取得部3023に強制変更値として保存される。この後、変更応答メッセージを無線通信部301からシンクノード201へ送信する。この変更応答メッセージを受けたシンクノード201では、変更が行われた場合、図8のツリートポロジの該当する変更フラグが1(変更あり)に設定される。
【0097】
センサノード206の周辺ノード情報取得部3023は、変更値が保存されている場合、自ノード206が選択している上位接続先ノード203が送信しているシンクノードまでのホップ数1に1を加えて計算するホップ数2に代えて、変更値を用いる。変更値が保存されていない場合には、上記計算したホップ数2をそのまま使用する。センサノード206の周辺ノード情報取得部3023は、変更値を保存すると速やかに(或いは次の周期の到来を待ってもよい)、変更値を用いて周辺探索メッセージをブロードキャストで送信する。すなわち、今の例では、センサノード206は、シンクノード201までのホップ数を実際は2ホップであるが、3ホップとして送信する。この周辺探索メッセージを受信した周囲のシンクノード205、209、210、211等は、センサノード206を上位接続先ノード候補とするメトリック値の計算を実施する。この結果、センサノード206よりもメトリック値の小さな他の上位接続先ノード候補が存在すれば、接続先変更処理を実施する。
【0098】
メトリック変更応答受信707の処理では、シンクノード201は、指定した変更値の反映処理について結果を確認し、応答判定708にて変更不可の場合は、変更通知送信706の処理を再度実施する(このとき、図8のツリートポロジ情報の該当する変更フラグを0に戻し、変更値を消去する)。数回繰り返しても変更できない場合は、処理を終了し、周期監視状態へ戻る。他方、変更完了の場合、接続先変更通知が受信されるのを一定期間だけ待ち合わせ、接続先変更通知を受信すると、トポロジ情報更新709にてトポロジを再構築し、ネットワークデータベース更新710にてその結果をデータベース上へ反映する。
【0099】
図9は、トポロジ情報更新709にて再構築されたツリートポロジを示す。図9を参照すると、ツリートポロジは平準化された状態である。これは、センサノード206から送信されるホップ数が2から3に変わったことで、センサノード209、211が上位接続先ノードとしてセンサノード206でなくセンサノード205、207を選択したことによる。これにより、センサノード206に接続していた下位ノード数は3台から1台へと減少し、負荷分散することができる。さらに、ツリートポロジは、2ホップ目のセンサノード(204,205,206,207)の下位ノードが全て1台となり平準化できる。
【0100】
上記接続変更処理する際、ネットワーク上へ送信されるメッセージ数は要求と応答の2メッセージ、送信回数はホップ数の2回であり、総送信回数は4回である。これに対して、各センサノード209、211へ接続先変更メッセージを送信する場合は、メッセージ数は要求2つ、応答2つの合計4メッセージで、送信回数はホップ数の3回となり、総送信回数は12回となる。このことから、本実施形態では、送信回数で3分の1となり、ネットワークの通信負荷を抑えつつ、ツリートポロジのノード数の平準化、ネットワークの負荷分散を実現できる。
【0101】
[効果]
このように本実施形態は、以下に記載するような効果を奏する。
第1の効果は、ツリートポロジにおけるノード数の偏りを平準化するのに、接続先を切り替える下位のノードでなく、その上位のノードに対して、周囲に送信するホップ数を変更する要求メッセージを与えることで実施するため、ツリートポロジの平準化による負荷分散を実施する際の通信量を抑えられることである。
第2の効果は、ツリートポロジにおけるノード数の偏りを平準化する際に、どのセンサノードをどのセンサノードに接続換えすべきかを算出する必要がないため、計算量を少なくできることである。
第3の効果は、ホップ数を強制的に変更しても、各センサノードは上位接続先ノード候補の中からメトリック値が最も小さな上位接続先ノードを自律的に決定するため、通信可能な状態を維持したまま平準化が実施可能なことである。
【0102】
なお、本実施形態では、ホップ数を強制的に変更する例を示したが、第1の実施形態において既に説明したように、ホップ数以外のデータ、例えば子ノード数やメトリック値やハンディキャップ値を変更対象とすることも可能である。
【0103】
また設定した強制変更値の設定を解除する方法は任意で良い。例えば、設定してから一定期間経過後に自動的に解除するようにしてもよい。
【0104】
[第3の実施形態]
本実施形態は、電力、ガス、水道の使用量を無線により検針する自動検針システムなどへ適用するのに好適な実施形態を示す。自動検針システムにおいては、シンクノードが複数ある大規模ネットワークとなる。そのため、シンクノード間での帰属ノード数の平準化が必要になる。
【0105】
第2の実施形態においては、シンクノードが1台のみ存在し、ツリートポロジを1つ構成し、ツリートポロジにおけるノード数の偏りの平準化を実施した。本実施形態では、シンクノードが2台存在する場合について説明を行う。また、シンクノードの数が3台以上となった場合も同様に実現できる。
【0106】
図10を参照すると、シンクノードが2台存在する。シンクノード1000、1021は、有線ネットワークへ接続され、トポロジデータベース1030と有線を介して接続する。トポロジデータベース1030は、ネットワーク情報とセンシングデータとを格納する機能と、偏り是正機能とを有する。図10において、各ノード間の無線リンクは折れ線で示し、各リンク上に記述した数値は、下位ノードの上位接続先ノードに対するメトリック値を示す。また、破線のリンクは接続に使用されていないが、通信が可能である予備リンクを示す。
【0107】
図11は、偏り是正前のトポロジデータベース上のトポロジ情報110を示している。図11を参照すると、トポロジ情報110は、各ノードの識別子に対応して、シンクノードまでのホップ数、シンクノードと通信する際の上位接続先ノード、この上位接続先ノードを選定する際に計算したメトリック値、情報送信先のシンクノードの番号、変更フラグ、変更値を格納している。しかし、トポロジ情報110に格納される情報は、これに限定されるものではない。例えば周辺ノードの情報を含んでいても良い。図11のツリートポロジ情報110から、シンクノード1021に帰属しているセンサノード数は13台、シンクノード1000に帰属しているノード数は7台であり、シンクノード間の帰属台数に偏りがあることがわかる。トポロジデータベース1030には、トポロジの偏り調査機能や平準化機能が実装されており、シンクノード間のノード数の平準化動作を実施する。
【0108】
トポロジデータベース1030では、トポロジ偏り周期監視701を実施し、周期的にシンクノード間の帰属ノード数を比較し偏りを検査する。図10の例では、ネットワーク内にセンサノードは全部で20台存在する。
【0109】
ネットワーク上のツリートポロジ間のノード数の偏りを検出する方法の一例を以下に説明する。まず、全センサノード数をシンクノード数で割った商(10台)を平均帰属ノード数とする(式6)。帰属ノード数と平均帰属ノード数の差分許容をある量に設定(本例では2割)し、平均帰属ノード数から差分許容数(2台)を算出する(式7)。平準化実行判定閾値ノード数を、平均帰属ノード数と差分許容数とに基づいて算出し(式8)、結果を用いて判定を行う。本実施形態では、平準化実行判定閾値台数を下限は8台、上限は12台と設定する。
全ノード数 ÷ 全シンクノード数 = 平均帰属ノード数・・・・・(式6)
平均帰属ノード数 × 0.2 = 差分許容数・・・・(式7)
平均帰属ノード数 ± 差分許容数 = 平準化実行判定閾値ノード数・・・・(式8)
【0110】
上記算出方法について、差分許容量や判定実施時に平準化実行判定閾値ノード数を含むか否か、等については、特に限定するものではない。
【0111】
算出した平準化実行判定閾値ノード数を用いて、トポロジ偏り判定(703)を実施すると、シンクノード毎の帰属ノード数に偏りがあると判定する。
【0112】
次に、トポロジデータベース1030は、シンクノード1000に比べて下位ノード数が多いシンクノード1021を目的のノードとして選択し、このノード1021から周囲のノードに送信するホップ数を実際の値とは異なる値に故意に変更する。ここでは、例えば実際のホップ数が0であるところを、ホップ数1に強制的に変更する。
【0113】
図12は、シンクノード1021のホップ数を1に変更した後、一定期間経過後のトポロジデータベース上のトポロジ情報120を示している。なお、トポロジ情報120では、メトリック値や上位接続先ノードが変更となった箇所に下線を引いている。また図13は、シンクノード1021のホップ数を1に変更した後、一定期間経過後のツリートポロジを示している。
【0114】
図12および図13を参照すると、シンクノード1021の送信するホップ数が0から1に変化することにより、センサノード1019、1020のシンクノード1021に対するメトリック値が変化している。また、センサノード1019、1020から周囲に送信するホップ数が1から2へと変化するため、センサノード1018、1015のセンサノード1019に対するメトリック値、センサノード1016、1017のセンサノード1020に対するメトリック値が変化している。さらに、センサノード1018、1015、1016、1017、1013が周囲に送信するホップ数が2から3へと変化するため、センサノード1014、1008、1009、1010のセンサノード1015に対するメトリック値が変化し、センサノード1011、1012、1013のセンサノード1017に対するメトリック値が変化している。この結果、センサノード1009、1010は、センサノード1015からメトリック値のより小さなセンサノード1003に上位接続先ノードを切り替えている。また、センサノード1011は、センサノード1017からメトリック値のより小さなセンサノード1004に上位接続先ノードを切り替えている。
【0115】
以上の結果、シンクノード1000、1021に帰属しているセンサノード数は各10台になり、平準化されている。
【0116】
また、シンクノード1000、1021それぞれに帰属のトポロジ(シンクノードの内のトポロジ)に偏りがあると判断した場合は、第2の実施形態と同様の手順で平準化されることになる。
【0117】
なお、本実施形態では、ホップ数を強制的に変更する例を示したが、第1の実施形態において既に説明したように、ホップ数以外のデータ、例えば子ノード数やメトリック値やハンディキャップ値を変更対象とすることも可能である。
【0118】
以上本発明を幾つかの実施形態を挙げて説明したが、本発明は以上の実施形態にのみ限定されず、その他各種の付加変更が可能である。また、本発明の無線ノードは、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態における無線ノードとして機能させる。
【産業上の利用可能性】
【0119】
本発明は、環境計測システム、自動検針システム、無線センサネットワーク、無線マルチホップネットワーク、無線基地局と無線端末などに適用可能である。
【符号の説明】
【0120】
1〜10…無線ノード
11…周辺ノード情報取得部
12…メトリック計算部
13…上位接続先ノード決定部
14…ネットワーク管理部
【技術分野】
【0001】
本発明は、複数の無線ノードから構成され、特定の無線ノードとマルチホップ無線通信を行うネットワークシステムおよびその経路制御方法に関する。
【背景技術】
【0002】
この種のネットワークシステムとして、無線センサネットワークシステムがある。無線センサネットワークシステムにおいて、OLSR(Optimized Link State Routing),AODV(Ad hocのOn-Demand Distance Vector)などの無線マルチホップネットワークに適したルーティングプロトコルを適用して、シンクノードを送信先、センサノードを送信元とするパスを生成すると、結果として、シンクノードを頂点とし、節および葉の部分にセンサノードが位置するツリー構造のネットワークトポロジ(以降、ツリートポロジ)が構築される。但し、このとき、同じ階層の複数のノード間で子ノードの数に偏りが発生することがある。このような偏りは、特定のノードの負荷が増加する原因になるので、できるだけ解消する必要がある。
【0003】
ツリートポロジに生じた上記のような偏りを解消する経路制御方法の一例が特許文献1に記載されている。この技術では、特定の装置(ネットワーク構築装置30)が、生成されたツリートポロジに偏りが生じていることを検出すると、その偏りを解消するためには、どのノードをどのノードに接続替えすれば良いかを解析し、接続替え対象の各ノードに対してメッセージを送信して接続替えを実施する。
【先行技術文献】
【特許文献】
【0004】
【特許文献1】特開2010-166150号公報
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、接続替え対象の各ノードに対してメッセージを送信して接続替えを実施する方法は、接続替え対象のノード数に比例したメッセージの送信とその応答のやりとりが必要になる。
【0006】
本発明の目的は、上述したような課題、すなわち、マルチホップ無線ネットワークシステムにおけるツリートポロジの偏りを改善するには多大なコストが必要になる、という課題を解決することにある。
【課題を解決するための手段】
【0007】
上記課題を解決するために、本発明の一形態にかかるマルチホップ無線ネットワークの経路制御方法は、
複数の無線ノードから構成され、それぞれの無線ノードが、周囲の無線ノードから受信するノード情報に関する周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出し、算出したメトリック値に基づいて上位接続先ノードを決定する、マルチホップ無線ネットワークの経路制御方法であって、
前記マルチホップ無線ネットワークにおける特定の無線ノードを根、その他の無線ノードを節および葉とするツリートポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、目的の無線ノードから周囲の無線ノードに送信するノード情報の値を故意に変更する、
といった構成を採る。
【発明の効果】
【0008】
本発明は上述したような構成を有するため、マルチホップ無線ネットワークシステムにおけるツリートポロジの偏りを少ないコストで解消することができる。
【図面の簡単な説明】
【0009】
【図1】本発明の第2の実施形態にかかる無線センサネットワークの物理的な構成例を示す図である。
【図2】本発明の第2の実施形態にかかる無線センサネットワークのノード間の接続関係を示す図である。
【図3】本発明の第2の実施形態にかかる無線センサネットワークのセンサノードのブロック図である。
【図4】本発明の第2の実施形態にかかる無線センサネットワークのシンクノードのブロック図である。
【図5】本発明の第2の実施形態にかかる無線センサネットワークの基本動作を示すタイムチャートである。
【図6】本発明の第2の実施形態にかかる無線センサネットワークの偏り是正前のツリートポロジを示す図である。
【図7】本発明の第2の実施形態にかかる無線センサネットワークのシンクノードが実施するトポロジ偏り是正処理の流れを示すフローチャートである。
【図8】本発明の第2の実施形態にかかる無線センサネットワークのシンクノードが有するネットワークデータベースの構成例を示す図である。
【図9】本発明の第2の実施形態にかかる無線センサネットワークの偏り是正後のツリートポロジを示す図である。
【図10】本発明の第3の実施形態にかかる無線センサネットワークのノード間の偏り是正前の接続関係を示す図である。
【図11】本発明の第3の実施形態にかかる無線センサネットワークのトポロジデータベースが保持するトポロジ情報(偏り是正前)の一例を示す図である。
【図12】本発明の第3の実施形態にかかる無線センサネットワークのトポロジデータベースが保持するトポロジ情報(偏り是正後)の一例を示す図である。
【図13】本発明の第3の実施形態にかかる無線センサネットワークのノード間の偏り是正後の接続関係を示す図である。
【図14】本発明の第1の実施形態にかかるマルチホップ無線ネットワークの物理的な構成例を示す図である。
【図15】本発明の第1の実施形態にかかるマルチホップ無線ネットワークの無線ノードのブロック図である。
【図16】本発明の第1の実施形態にかかるマルチホップ無線ネットワークの偏り是正前のトポロジを示す図である。
【図17】本発明の第1の実施形態にかかるマルチホップ無線ネットワークの偏り是正後のトポロジを示す図である。
【発明を実施するための形態】
【0010】
次に本発明の実施の形態について図面を参照して詳細に説明する。
[第1の実施形態]
図14を参照すると、本発明の第1の実施形態にかかるマルチホップ無線ネットワークシステムは、9個の無線ノード1〜9から構成される。無線ノードの数を9個としているのは説明の便宜上であり、本発明において無線ノードの数は任意である。
【0011】
各無線ノード1〜9は、図15の無線ノード10に示すように、周辺ノード情報取得部11、メトリック計算部12、および上位接続先ノード決定部13を有する。
【0012】
周辺ノード情報取得部11は、周囲の無線ノードに対して自無線ノードに関するノード情報を同報通信により送信する機能と、周囲の無線ノードから受信するノード情報に関する周辺ノード情報を取得する機能とを有する。本実施形態の場合、各無線ノード1〜9が周囲に送信するノード情報は、自ノードを一意に識別するノード識別子と、自ノードから特定の無線ノードまでのホップ数とから構成される。また、各無線ノード1〜9が周囲の無線ノードから受信するノード情報に関する周辺ノード情報は、上記ノード識別子と、上記ホップ数と、当該ノード情報を受信した際の受信強度(無線信号の強度)とから構成される。ここで、本実施形態は、無線ノード1を上記特定の無線ノードとしており、他の無線ノード2〜9が無線ノード1とパケット通信するものとする。
【0013】
メトリック計算部12は、周辺ノード情報取得部11で取得された周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出する機能を有する。本実施形態の場合、各無線ノード1〜9は、受信したノード情報に含まれるホップ数と、当該ノード情報を受信した際の受信強度とを用い、メトリック値Mを以下の計算式で計算する。
M=Meh(e、h) …(1)
ここで、Meh(e、h)は、ホップ数hと受信強度eとを引数として、ホップ数hがより大きくなるほど、また受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。また、メトリック値は、リンクの通信コストが小さくなるほど小さくなる値であるとする。
【0014】
上位接続先ノード決定部13は、メトリック計算部12により算出されたメトリック値に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードを決定する機能を有する。上位接続先ノード決定部13は、周囲のノード毎に算出したメトリック値のうち最も小さなメトリック値となった周囲ノードを、上位接続先ノードに選択する。
【0015】
他方、上記9個の無線ノード1〜9とは別に制御ノードが存在する。或いは9個の無線ノード1〜9の何れかが制御ノードとして機能する。本実施形態では、無線ノード1が制御ノードとして機能する例について説明する。
【0016】
制御ノードとして機能する無線ノード1は、図15に示すように、周辺ノード情報11、メトリック計算部12、上位接続先ノード決定部13に加えてさらに、ネットワーク管理部14を有する(制御ノード以外の無線ノードはネットワーク管理部14が無くてもよい)。ネットワーク管理部14は、マルチホップ無線ネットワークにおける特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジを生成する機能と、この生成した木構造のネットワークトポロジにおける所定の無線ノードを目的の無線ノードとして選択する機能と、この目的の無線ノードから周囲の無線ノードに送信するノード情報の値を故意に変更する機能とを有する。
【0017】
ネットワーク管理部14が有するネットワークトポロジ生成機能について説明する。本実施形態の場合、無線ノード1は他の無線ノード2〜9からマルチホップ無線通信によってパケットを受信する。このとき、受信するパケットには、送信元の無線ノードの識別子と中継点の無線ノードの識別子とを含む通信履歴が付加されている。ネットワーク管理部14は、この通信履歴に基づいて上記のネットワークトポロジを生成する。あるいは、ネットワーク管理部14は次のような方法でネットワークトポロジを生成してよい。各無線ノードが上位接続先ノードを決定した際、決定した上位接続先ノードに対して、自ノードが子ノードとして存在することを認識させるための通知が行われる。この通知を受信した上位接続先ノードが、この通知を制御ノードである無線ノード1に転送する。無線ノード1は、この転送されてきた情報に基づいて、どの無線ノードの下位にどの無線ノードが存在するか、すなわちネットワークトポロジを把握する。
【0018】
ネットワーク管理部14が有する目的の無線ノードを選択する機能について説明する。本実施形態の場合、無線ノード1は、木構造のネットワークトポロジにおける同階層の他の無線ノードに比較して下位の無線ノード数が多い無線ノードを目的の無線ノードとして選択する。例えば、ネットワーク管理部14は、ネットワークトポロジのルート階層以外の階層毎に、その階層に属する各無線ノードの下位ノード数(子ノード、孫ノードを含む子孫ノードの数)を調査し、平均や中央値や標準偏差や最大値や最小値などと比較して、下位ノード数の偏り箇所を検出する。例えば、或る階層にA、B、C、Dの4つのセンサノードがあり、各々の下位ノード数が、Aは10台、Bは33台、Cは9台、Dは5台であった場合、平均を求めると約15台になる。このとき、例えば平均値の2倍以上のノード数となる箇所を偏り箇所として検出するものと予め定められている場合、ノードBが目的の無線ノードとして検出される。
【0019】
ネットワーク管理部14が有するノード情報変更機能について説明する。ネットワーク管理部14は、目的の無線ノードから周囲の無線ノードに送信するノード情報を、目的の無線ノードを上位接続先ノードの候補として計算されるメトリック値がリンクの通信コスト的に大きくなるように変更する制御を実施する。具体的には、変更を要求するメッセージを目的の無線ノードに送信し、その応答を受信する。本実施形態の場合、無線ノードから周囲の無線ノードに送信されるノード情報は、ノード識別子とホップ数であり、メトリック値が上記(1)式によって計算される。このため、ネットワーク管理部14は、目的の無線ノードから周囲の無線ノードに送信するホップ数を、実際のホップ数よりも大きな数に変更する。どの程度大きくするかは任意である。予め定められた数(例えばホップ数1)だけ大きくしても良いし、あるいは予め定められた割合(例えば5割)を実際のホップ数に加算した後に四捨五入等しても良い。
【0020】
次に本実施形態の動作を説明する。
【0021】
無線ノード1〜9は、周辺ノード情報取得部11によって、例えば定期的に、無線ノード1からのホップ数を含むノード情報を周囲の無線ノードに送信する。初期の状態において、無線ノード1からのホップ数を認識しているのは無線ノード1のみであるため、無線ノード1がホップ数0を、同報通信により周囲の無線ノードに送信する。今、この同報通信を受信した無線ノードが無線ノード2と無線ノード3との2つの無線ノードであったとする。無線ノード2、3は、メトリック計算部12を用いて、無線ノード1から受信したホップ数0と受信強度とに基づいて、無線ノード1を上位接続先ノードの候補としてメトリック値を計算し、上位接続先ノード決定部13により無線ノード1を上位接続先ノードに決定する。このとき、無線ノード2、3で計算された無線ノード1のメトリック値は、それぞれ2.0と3.0であったとする。
【0022】
次に、無線ノード2、3は、上位接続先ノードに決定した無線ノード1までのホップ数1を同報通信により周囲の無線ノードに送信する。無線ノード2からの同報通信を受信した無線ノードは、無線ノード1を除いて、無線ノード4、5、6、7の4台であり、無線ノード3からの同報通信を受信した無線ノードは、無線ノード1を除いて、無線ノード7、8、9の3台であったとする。
【0023】
無線ノード4、5、6は、無線ノード2から受信したホップ数1と受信強度とに基づいて、無線ノード2を上位接続先ノードの候補としてメトリック値を計算し、無線ノード2を上位接続先ノードに決定する。このとき、無線ノード4、5、6で計算された無線ノード2のメトリック値は、それぞれ5.0であったとする。同様に、無線ノード9は、無線ノード3から受信したホップ数1と受信強度とに基づいて、無線ノード3を上位接続先ノードの候補としてメトリック値を計算し、無線ノード3を上位接続先ノードに決定する。このとき、無線ノード9で計算された無線ノード3のメトリック値は6.0であったとする。
【0024】
他方、無線ノード7と無線ノード8は、無線ノード2、3の双方からノード情報を受信している。無線ノード7と無線ノード8は、無線ノード2、3のそれぞれを上位接続先ノードの候補としてメトリック値を計算し、メトリック値の小さい方を上位接続先ノードに決定する。今、無線ノード7で計算された無線ノード2のメトリック値が4.5、無線ノード3のメトリック値が5.5であり、無線ノード8で計算された無線ノード2のメトリック値が5.0、無線ノード3のメトリック値が5.5であったとする。すなわち、ホップ数は共に2だが、受信強度の相違によってこのような結果になったとする。すると、無線ノード7、8は、共に無線ノード2を上位接続先ノードに決定する。
【0025】
以降、無線ノード4〜9からノード情報が周囲に送信され、また無線ノード1〜3からも再度ノード情報が周囲に送信され、これを受信した無線ノードにおいてメトリック値の計算、上位接続先ノードの決定が繰り返される。ここでは、上位接続先ノードの決定結果に変化がなかったものとする。このとき、無線ノード1を根、無線ノード2〜9を節あるいは葉とする木構造のネットワークトポロジは図16に示すようになる。
【0026】
図16において、無線ノード間を上下に結ぶ実線は、下側の無線ノードが上側の無線ノードを上位接続先ノードとして選択していることを示す。また無線ノード間を上下に結ぶ破線は、下側の無線ノードが上側の無線ノードを上位接続先ノードの候補としているが、他にメトリック値の小さな上位接続先ノード候補が存在しているために棄却されたことを示している。また、実線および破線に付記された数値は、下側の無線ノードが上側の無線ノードを対象として計算したメトリック値を示す。この図16を参照すると、無線ノード2の下位ノード数は5であり、同じ階層の無線ノード3の下位ノード数1と大きな偏りがある。
【0027】
制御ノードである無線ノード1のネットワーク管理部14は、図16に示したようなネットワークトポロジを生成し、同階層の他の無線ノードに比較して下位の無線ノード数が多い無線ノード2を目的の無線ノードとして選択する。続いて無線ノード1のネットワーク管理部14は、無線ノード2から周囲の無線ノードに送信するホップ数を、例えば実際のホップ数1に予め定められた数である1を加算した2に変更すべく、無線ノード2に対して変更要求メッセージを送信する。無線ノード2の周辺ノード情報取得部11は、この変更要求メッセージを受信すると、その応答を無線ノード1に返した後、実際とは異なるホップ数2を周囲に送信する。他方、無線ノード3は、依然として実際のホップ数1を周囲に送信している。
【0028】
無線ノード2からの同報通信を受信した無線ノードは、以前の状況と同じく、無線ノード1を除いて、無線ノード4、5、6、7の4台であり、無線ノード3からの同報通信を受信した無線ノードは、無線ノード1を除いて、無線ノード7、8、9の3台であったとする。
【0029】
無線ノード4、5、6は、無線ノード2から受信したホップ数2と受信強度とに基づいて、無線ノード2を上位接続先ノードの候補としてメトリック値を計算し、無線ノード2を上位接続先ノードに決定する。このとき、無線ノード4、5、6で計算された無線ノード2のメトリック値は、それぞれ6.5であったとする。同様に、無線ノード9は、無線ノード3から受信したホップ数1と受信強度とに基づいて、無線ノード3を上位接続先ノードの候補としてメトリック値を計算し、無線ノード3を上位接続先ノードに決定する。このとき、無線ノード9で計算された無線ノード3のメトリック値は6.0であったとする。
【0030】
他方、無線ノード7と無線ノード8は、無線ノード2、3の双方からノード情報を受信している。無線ノード7と無線ノード8は、無線ノード2、3のそれぞれを上位接続先ノードの候補としてメトリック値を計算し、メトリック値の小さい方を上位接続先ノードに決定する。今、無線ノード7で計算された無線ノード2のメトリック値が6.0、無線ノード3のメトリック値が5.5であり、無線ノード8で計算された無線ノード2のメトリック値が6.5、無線ノード3のメトリック値が5.5であったとする。すなわち、受信強度は以前の状況と同じであったとしても、ホップ数は無線ノード2が2ホップ、無線ノード3が1ホップと相違するためにこのような結果になったとする。すると、無線ノード7、8は、共に無線ノード3を上位接続先ノードに決定する。
【0031】
以降、無線ノード4〜9からノード情報が周囲に送信され、また無線ノード1〜3からもノード情報が周囲に送信され、これを受信した無線ノードにおいてメトリック値の計算、上位接続先ノードの決定が繰り返される。ここでは、上位接続先ノードの決定結果に変化がなかったものとする。このとき、無線ノード1を根、無線ノード2〜9を節あるいは葉とする木構造のネットワークトポロジは図16から図17に示すように変化する。
【0032】
図17を参照すると、無線ノード2の下位ノード数は5から3に変化しており、結果的に同じ階層の無線ノード3の下位ノード数3と等しくなっている。
【0033】
このように本実施形態によれば、マルチホップ無線ネットワークシステムにおけるツリートポロジの偏りを少ないコストで解消することができる。例えば、上述した例の場合、制御ノードである無線ノード1から無線ノード2に対して変更要求メッセージが1回送信され、その応答が無線ノード2から無線ノード1に1回送信される。無線ノード1から無線ノード2までは1ホップなので、総送信回数は2回である。これに対して、無線ノード1から無線ノード7、8に対して上位接続先ノードを無線ノード2から無線ノード3に切り替えるよう要求するメッセージを送信し、無線ノード7、8からその応答を無線ノード1に返す場合、無線ノード1から無線ノード7、8までは2ホップなので、総送信回数は8回となる。
【0034】
本実施形態では、無線ノードから周囲に送信するノード情報がノード識別子とホップ数とから構成されているとしたが、ホップ数に代えて、あるいはホップ数に加えて他のデータを用いてもよい。例えば、ホップ数に代えて、あるいはホップ数に加えて、自ノードを上位接続先ノードとして選択している無線ノードの数である子ノード数を用いてもよい。この場合、メトリック値Mは以下の計算式で計算してよい。
M=Mek(e、k) …(2)
M=Mehk(e、h、k) …(3)
ここで、Mek(e、k)は、受信強度eと子ノード数kとを引数として、子ノード数kがより多くなるほど、また受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。またMehk(e、h、k)は、受信強度eとホップ数hと子ノード数kとを引数として、ホップ数hおよび子ノード数kがより多くなるほど、また受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。そして、その場合には、実際の値と異なる値に故意に変更する対象をホップ数と子ノード数、あるいは子ノード数だけにしてもよい。
【0035】
また本実施形態では、無線ノードから周囲に送信するノード情報がノード識別子とホップ数とから構成されているとしたが、ホップ数に代えて、あるいはホップ数に加えて、自ノードが上位接続先ノードを決定する際に計算した当該上位接続先ノードのメトリック値を用いてもよい。例えば、図16の場合、無線ノード2は、無線ノード1のメトリック値2.0を含むノード情報を周囲に送信する。この場合、メトリック値Mは以下の計算式で計算してよい。
M=Mem(e、m) …(4)
M=Mehm(e、h、m) …(5)
ここで、Mem(e、m)は、受信強度eとメトリック値mとを引数として、メトリック値mがより大きくなるほど、また受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。またMehm(e、h、m)は、受信強度eとホップ数hとメトリック値mとを引数として、ホップ数hがより多くなるほど、メトリック値mがより大きくなるほど、受信強度eがより小さくなるほど、より大きな値のメトリック値Mを返す関数である。そして、その場合には、実際の値と異なる値に故意に変更する対象をホップ数hとメトリック値m、或いはメトリック値mだけにしてもよい。
また、メトリック値の計算に、重み付けパラメータの値であるハンディキャップ値を使用し、上記の計算式(1)〜(5)を以下の計算式のように変形してもよい。
M=Meh(e、h)+α …(1’)
M=Mek(e、k)+α …(2’)
M=Mehk(e、h、k)+α …(3’)
M=Mem(e、m)+α …(4’)
M=Mehm(e、h、m)+α …(5’)
上記の計算式(1’)〜(5’)において、αはハンディキャップ値を示す。ハンディキャップ値αの初期値は0である。そしてこの場合、ツリートポロジの偏りを解消するために、ハンディキャップ値αの値を設定あるいは変更するようにしてもよい。すなわち、制御ノードである無線ノード1は、ツリートポロジの偏りを解消するために、目的の無線ノード2のハンディキャップ値を設定あるいは変更し、変更後のハンディキャップ値を変更要求メッセージで無線ノード2へ送信する。無線ノード2の周辺ノード情報取得部11は、この変更要求メッセージを受信すると、その応答を無線ノード1に返した後、ノード情報中の一つの情報としてハンディキャップ値を周囲に送信する。このノード情報を受信した周囲の無線ノードは、受信したノード情報に含まれる変更後の最新のハンディキャップ値を用いて無線ノード2を上位接続先ノード候補としてメトリック値を計算する。
【0036】
また本実施形態では、特定の無線ノードを唯一つとしたが、2以上の特定の無線ノードが存在していてもよい。この場合、特定の無線ノード以外の無線ノードは、複数の特定の無線ノードと通信するのではなく、よりメトリック値の小さな1つの特定の無線ノードと通信する。従って、特定の無線ノードが複数存在する場合、特定の無線ノードの数だけ、ツリートポロジが形成される。そして、複数のツリートポロジ間に帰属する無線ノード数の偏りが発生する場合、特定の無線ノードから周囲に送信するノード情報に含まれるホップ数、子ノード数、メトリック値、ハンディキャップ値といったデータを故意に変更することにより、上記偏りを解消する制御を実施してもよい。
【0037】
また本実施形態では、トポロジにおける同階層の他の無線ノードに比較して下位の無線ノード数が多い無線ノード2を目的の無線ノードとして選択したが、トポロジにおける同階層の他の無線ノードに比較して下位の無線ノード数が少ない無線ノード3を目的の無線ノードとして選択してもよい。この場合、無線ノード3が周囲に送信するホップ数を、無線ノード3を上位接続先ノードの候補として計算されるメトリック値がリンクの通信コスト的に小さくなるように変更すればよい(すなわち、実際より少ないホップ数を周囲に送信する)。ホップ数を実際のホップ数よりも小さな値に設定する際は、トポロジ構築時にループが発生する可能性があるため、ループ回避の処理を組み込む必要がある。ただし、本発明ではループ回避の処理については、範囲外であるため詳細には言及しない。
【0038】
[第2の実施形態]
次に本発明の第2の実施形態について詳細に説明する。
【0039】
[背景]
温度や湿度などの環境情報を収集する環境計測システムに適用される無線センサネットワークでは、各ノード(センサノード)がセンシングしたデータを一つのノード(シンクノード)に集める必要がある。そのため、ネットワークトポロジとしては、シンクノードを頂点としたツリートポロジを構築するのが一般的である。このツリートポロジは一般的に無線マルチホップネットワークに適したルーティングプロトコルにより構築される。
【0040】
無線マルチホップネットワークに用いられるルーティングプロトコルには、プロアクティブ型のルーティングプロトコルと、リアクティブ型のルーティングプロトコルがある。プロアクティブ型のプロトコルの代表例はOLSR(Optimized Link State Routing)プロトコルである。リアクティブ型のプロトコルの代表例は、AODV(Ad hoc On-Demand Distance Vector)プロトコルやDSR(Dynamic Source Routing)プロトコルである。OLSRやAODVやDSRは、IETF(Internet Engineering Task Force)により規定されたプロトコルである。
【0041】
これらのルーティングプロトコルでは、受信強度やホップ数に基づいて、シンクノードまでのコストをあらわすメトリック値を算出し、算出されたメトリック値に基づいたネットワークトポロジが構築される。そのため、無線センサネットワークでこれらのルーティングプロトコルを適用した場合、それぞれのセンサノードはシンクノードまでのリンクの通信コストが最小のパス(経路)を選択し、ネットワークトポロジを構築する。
【0042】
また、ネットワークトポロジの最適化・平準化方法については規定がなく、ルーティングプロトコルにて作成されたトポロジをそのまま用いるか、各システムにて個別の対応を行っている。このため、次のような課題がある。
【0043】
第1の課題は、センサノードはシンクノードまでの最小のパスを選択するため、ネットワークトポロジに接続しているノード数に偏りが発生することで、通信帯域を有効に利用できないことである。
【0044】
第2の課題は、ネットワークトポロジ平準化のために、各ノードに接続先変更メッセージを送信する際に、参加しているノードをどれだけ(台数)何処へ(場所)どの様に(トポロジの形状)移動させるかを調整するための処理が増大し、管理サーバの負荷が増大することである。
【0045】
第3の課題は、ネットワークトポロジの偏りを平準化するためには、各ノードに接続先変更メッセージを送信する必要があり、通信帯域を圧迫することである。
【0046】
本実施形態の目的は、無線センサネットワークにおいて、ツリートポロジの平準化を低コスト(少ない通信量と計算量)で実現する方法を提供することである。
【0047】
[概要]
本実施形態は、センサデータを収集する無線センサネットワークシステムにおいて、ツリートポロジを構築する際に、ツリートポロジの各枝の構成ノード数に偏りが生じた場合に、少ない通信量と計算量でノード数を平準化し、負荷分散する。
【0048】
無線センサネットワークを構成する各ノードは、ノード情報を送信すると共に周辺ノード情報を取得する周辺ノード情報取得手段と、センサデータを収集するシンクノードへのコストを表すメトリック値を計算するメトリック計算手段と、メトリック計算手段により計算されたメトリック値を基に接続するノードを決定する接続先ノード決定手段とにより、自律的にシンクノードを頂点としてクラスタリングされたツリートポロジを構築する。その際、ツリートポロジ内の各枝間に下位ノード数の偏りが発生する可能性がある。本実施形態では、各枝間の下位ノード数の偏りを解消させる目的で、所定のセンサノードから周囲のノードに送信するシンクノードまでのホップ数を強制的に変更することで、各枝間のノードの移動を促し、下位ノード数の平準化を行う。
【0049】
このようにして、本実施形態では、自律的にネットワークトポロジを構築するネットワークにおいて、トポロジ構築に使用するホップ数を故意に変更することで、少ない計算量と通信量にて無線センサネットワークにおけるツリートポロジのノード数を平準化することで、負荷分散ができるようにする。以下、本実施形態の構成、動作を説明する。
【0050】
[構成]
図1を参照すると、本実施形態としてのシンクノードとセンサノードを使用した物理的な構成が示されている。図1において、シンクノード201は、センサノード202〜211がセンシングした情報をこれらセンサノード202〜211から収集する装置である。センサノード202〜211は、屋内、もしくは、屋外に設置され、外界の情報をセンシングし、センシングした情報をシンクノード201に対して送信を行う。なお、図1において、各ノード間を結ぶ折れ線は無線にて通信を行う関係を表したものである。
【0051】
図2を参照すると、シンクノード201とセンサノード202〜211の接続関係が論理的に示されている。図2において、ノード間を結ぶ直線は無線にて通信を行う関係を表したものである。本実施形態は、図2に表すようにツリートポロジを構成し、シンクノード201を起点としてセンサノード202〜211がセンシングした情報を収集する構成が基本構成である。
【0052】
図3を参照すると、センサノードの内部構成が示されている。図3において、センサノード30は、図1および図2に示したセンサノード202〜211の何れかである。センサノード30は、無線通信部301とルーティング機能部302とアプリケーション部303とセンサ部304とを有する。
【0053】
無線通信部301は、ルーティング機能部302からの無線通信データの送受信と、他のノードとの無線通信を行う機能である。無線通信部301は、無線LANやZigBee、省電力無線などの無線通信を行うことのできるモジュールもしくは回路にて構成される。
【0054】
ルーティング機能部302は、ルーティングテーブル3021とメトリック計算部3022と周辺ノード情報取得部3023とパケット送受信部3024とで構成される。
【0055】
ルーティングテーブル3021は、周辺ノード情報取得部3023から得られるノード識別情報や受信感度、シンクノードまでのホップ数といった周辺ノード情報を格納するテーブルであり、周辺ノード情報とともにメトリック計算部3022で算出されたメトリック値、上位ノードや下位ノードといったツリートポロジの情報も格納されており、パケットの送信先を決定するためのテーブルである。
【0056】
メトリック計算部3022は、周辺ノード情報取得3023から得られるノード識別情報や受信強度、シンクノードまでのホップ数などから、該当するノードとのリンクのメトリック値を算出し、上位接続先ノードを決定する機能である。
【0057】
周辺ノード情報取得部3023は、受信したパケットのメッセージからノードの識別情報とそのパケットの受信強度などを取得する機能である。また、周辺ノード情報取得部3023は、周囲のノードに自ノードのノード情報として、ノード識別子およびシンクノードまでのホップ数などを送信する機能を有する。
【0058】
パケット送受信部3024は、無線通信部301とのパケットを送受信する機能とアプリケーション部303とのデータパケットを送受信する機能とを有する。また、本パケット送受信部3024は、無線通信部301から受信したパケットが自ノード宛てではないが、転送が必要な場合は再転送する機能も有する。
【0059】
アプリケーション部303は、センサ情報取得部3031とデータパケット送信部3032とで構成される。
【0060】
センサ情報取得部3031は、センサ部304がセンシングしたデータを取得する機能である。
【0061】
データパケット送信部3032は、センサ情報取得部3031が取得したセンサデータをデータパケットとして送信する機能である。
【0062】
センサ部304は、温度や湿度、電力など所定の物理量をセンシングする機能と、センシングした物理量のデータをアプリケーション部303へ通知する仕組みを有する。
【0063】
なお、本実施形態では、無線通信部301で使用する無線規格を無線LANやZigBee、省電力無線としているが、無線通信を行えればよく、Bluetoothといった他の無線通信規格を使用してもよい。メトリック計算部3022において、周辺ノード情報取得部3023から取得する情報を、ノード識別情報や受信強度、シンクノードまでのホップ数としているが、計算に使用する情報は、周辺ノード情報取得部3023が取得できる情報であればよく、バッテリー残容量など周辺ノードに関連する情報を用いて計算してもよく、特に限定しない。周辺ノード情報取得部3023において、取得する情報をノード識別情報とパケット受信強度などとしているが、周辺ノードに関連する情報であればよく、特に限定しない。センサ部304において、センシングする物理量を温度や湿度、電力量としているが、センシングする物理量は例示している3種以外であってもセンシング可能な情報であればよいため、特に限定しない。
【0064】
図4を参照すると、シンクノードの内部構成が示されている。図において、シンクノード40は、図1および図2のシンクノード201に対応する。シンクノード40は、無線通信部301とルーティング機能部302とアプリケーション部403とデータベース404とネットワーク管理部405を有する。
【0065】
無線通信部301とルーティング機能部302については、図3に示したセンサノード30の無線通信部301とルーティング機能部302と同一の機能である。
【0066】
アプリケーション部403は、データベース管理部4031とデータパケット受信部4032とで構成される。
【0067】
データベース管理部4031は、データパケット受信部4032から得られるセンサデータをデータベース404に書き込む機能である。
【0068】
データパケット受信部4032は、ルーティング機能部302からデータパケットを受信する機能と、受信したパケットからノード識別情報とセンサデータとを取り出し、データベース管理部4031へ渡す機能を有する。
【0069】
データベース404は、アプリケーション部403から得られるノード識別情報とセンサデータとを対応付けて格納するデータベースである。
【0070】
ネットワーク管理部405は、トポロジ管理部4051と演算部4052とで構成される。
【0071】
トポロジ管理部4051は、演算部4052において導きだされたツリートポロジの情報を、ネットワークデータベース406へ格納する。また、周期的にツリートポロジの情報を監視し、偏りがある場合は、演算部4052に平準化処理を依頼する。さらに、演算部4052で平準化用に算出したホップ数を、該当ノードへ反映するために、ルーティング情報をネットワークデータベース406から取得し、値変更メッセージパケットを作成した後、ルーティング機能部302を通して該当ノードへ通知する。
【0072】
演算部4052は、センサノードから受信したパケット上のルーティング情報をルーティング機能部302から取得し、ネットワークデータベース406に格納済みのルーティング情報と統合することでセンサネットワーク全体のツリートポロジを導出する。また、トポロジ管理部4051から平準化処理を依頼された場合は、ネットワークデータベース406にアクセスし、導き出したツリートポロジにおけるノード数偏りの平準化を行うために該当ノードへ設定するホップ数の算出を行い、トポロジ管理部4051へ通知する。
【0073】
ネットワークデータベース406は、ネットワーク管理部405から得られるトポロジ情報とルーティングデータとを格納するデータベースである。
【0074】
なお、本実施形態では、シンクノード40上のデータベース404へセンサデータを、ネットワークデータベース406にツリートポロジ情報をそれぞれ格納しているが、別途設置したサーバにデータベース404とネットワークデータベース405の機能を搭載する構成としてもよい。
【0075】
[動作]
次にシンクノードとセンサノードの基本動作を図5に示すタイムチャートを使用して説明する。
【0076】
図5は、プロアクティブ型のルーティングプロトコルを動作させた場合の例である。プロアクティブ型のルーティングプロトコルでは、各センサノードが定期的にネットワークトポロジ構築処理を実施し、接続先ノードを決定することでツリートポロジが構築される。図5のタイムチャートは、センサノード502がツリートポロジ構築処理を実施した場合の動作を示している。図5において、センサノード502、503は図1および図2のセンサノード202〜211の何れか2つのセンサノードを示している。
【0077】
図5において、センサノード502が周辺ノード情報取得504を実施し、周辺探索メッセージをブロードキャストで送信している。ブロードキャストとは、あて先のアドレスにブロードキャストアドレスを指定し、すべてのノードに対して送信する送信方法である。なお、周辺探索メッセージには、センサノード502のネットワークトポロジへの参加状況やシンクノードまでのホップ数などを含んでいる。
【0078】
周辺探索メッセージを受信したシンクノード201とセンサノード503は、それぞれ周辺探索メッセージに対する周辺探索応答メッセージをユニキャストで送信する(505、506)。ユニキャストとは、あて先アドレスにノードのアドレスを指定することで、そのノードに対して送信する送信方法である。なお、周辺探索応答メッセージには、ネットワークトポロジへの参加状況やシンクノードまでのホップ数などを含んでいる。
【0079】
周辺探索応答メッセージを受信したセンサノード502は、周辺探索応答メッセージに含まれるツリートポロジへの参加状況やシンクノードまでのホップ数などを取得する。また、周辺探索応答メッセージを受信した際の受信強度についても取得する。
【0080】
このように、周辺ノード情報取得504により、周辺探索メッセージと周辺探索応答メッセージとを周辺のノード間で送受信することで、周辺の通信可能なノードの周辺ノード情報を取得することができる。
【0081】
次に、メトリック計算507を実施する。メトリック計算507は、周辺ノード情報取得504により得られた周辺ノード情報から、周辺のノード毎に、自ノードからシンクノードまでのパスのコストを示すメトリック値を計算する処理である。ルーティングプロトコルごとに異なるが、ここでは、取得した周辺ノード情報の受信強度とシンクノードまでのホップ数とからメトリック値を計算する。なお、本実施形態は、コストが小さい値であるほどシンクノードまでの通信状況が有利となるルーティングプロトコルを適用した場合である。
【0082】
次に、ルーティングテーブル更新508を実施する。ルーティングテーブル更新508は、メトリック計算507で算出した周辺ノードのメトリック値をルーティングテーブルへ書き込む処理である。
【0083】
次に、接続先ノード決定509を実施する。接続先ノード決定509は、ルーティングテーブル上で最もメトリック値が小さい(コストが低い)ノードを選出する。選出した結果、現在接続中のノードであるかどうかを確認し、現在接続中のノードではない場合は接続先変更処理510を実施する。接続先変更処理510は、新たな接続先となった上位接続先ノードに対して自ノードが子ノードとして存在することを知らせる処理である。接続先変更処理510によるメッセージを受信した上位接続先ノードは通信元のノードを子ノードとして認識すると共に、このメッセージをシンクノード201に転送する。
【0084】
上記の処理を繰り返し実施することにより、ネットワークトポロジが構築されることとなる。
【0085】
図2は上記処理を実施することで作成されたネットワークトポロジ図であり、トポロジに偏りがある。以下、この偏りを是正し、トポロジを平準化する処理の概要を説明する。
【0086】
図2を参照すると、シンクノード201を頂点としたツリートポロジとなっており、シンクノードからの最大ホップ数は3ホップである。また、センサノードで子ノードを持つノード(センサノード202,203,204,206)は、クラスタヘッドノードと呼ばれる。図2の例では、クラスタヘッドノード206が最も多く子ノードを収容しており、その数は3台である。
【0087】
図6を参照すると、図2の論理的な構成図上の各リンクにメトリック値を追記したものである。各ノード間の点線は、接続は可能であるが、トポロジ構成時に接続先として選択されなかったリンクを示している。
【0088】
図6のツリートポロジにおいて、2ホップ目に注目すると、センサノード204の子ノード数は1台、センサノード206の子ノード数は3台、センサノード205,207の子ノードは無く、センサノード206に多くの子ノードが接続しており、ツリートポロジの下位ノード数に偏りがある。この状況では、センサノード206は、下位ノードを管理するのに他の2ホップ目のノード(204,205,207)の3倍以上のメモリを使用し、センサデータ収集時は他の2ホップ目のノード(204,205,207)の3倍以上のデータを転送することになり、処理負荷およびネットワーク負荷ともに高い状況となっている。
【0089】
本実施形態では、図6のツリートポロジにおいてセンサノード206の負荷を、データ通信量を少なく、センサノード206から周囲に送信するシンクノードまでのホップ数を変更させることで、処理負荷およびネットワーク負荷を軽減させる。処理内容について、図7の処理フローを用いて説明する。
【0090】
図7を参照すると、トポロジ偏り周期監視701をシンクノード201では周期的に実施する。周期監視は1時間毎であってもよいし、1月毎といった長期間であってもよい。ただし、短時間で周期監視する設定にした場合は、シンクノードでの処理負荷が上がることや、長期間で周期監視する設定にした場合は、ツリートポロジにおけるノード数の偏りが継続することで特定リンクの通信負荷が解消されないこととなるため、参加しているノード数などから周期時間を設定するとよいが、特に限定しない。本実施形態ではセンシングの対象を電力メータの電力使用量であるものとし、それを考慮して、トポロジ偏り周期監視701の周期は1日とするが、特に限定しない。
【0091】
次に、一日ごとに実施されるトポロジ偏り周期監視701により、ネットワークデータベース調査702が実行される。ネットワークデータベース調査702は、トポロジ管理部4051が、ネットワークデータベース406に格納されているツリートポロジ情報から偏りがあるかどうかを調査する。
【0092】
図8はネットワークデータベース406に格納されているツリートポロジ情報の構成例である。ネットワークデータベース406は、ノード201〜211のノード識別子に対応して、ノード201までのホップ数、上位接続先ノード、当該上位接続先ノードのメトリック値、子ノード数、変更フラグ、変更値とを保持している。例えば6行目は、センサノード206は、シンクノード201までのホップ数は2であり、シンクノード201と通信する際の上位接続先ノードはセンサノード203であり、センサノード203を上位接続先ノードとして選択した際にセンサノード203に対して計算したメトリック値は4.0であり、子ノード数は3であり、変更フラグは0(変更なし)であり、変更値は未設定であることを示している。なお、ツリートポロジ情報に格納する情報は図8に記載した情報に限定されない。例えば、周辺に存在するセンサノードの識別子やそのノードを上位接続先ノード候補とした際に計算したメトリック値が追加されていても良いし、ルーティング情報や各ノードの接続状況などの情報が追加されていてもよい。
【0093】
図8のツリートポロジ情報から、ホップ数が1のノードは2台(202,203)あり、それぞれ子ノードが2台接続している。ホップ数が2のノードは4台(204,205,206,207)あり、子ノードの接続台数はセンサノード206に3台、センサノード204に1台、その他のノードには0台である。ホップ数が3のノードは4台(208,209,210,211)あり、すべてのセンサノードで子ノードの接続台数は0台である。この結果から、ホップ数が2のノードにおいて、下位ノード数に偏りがあることが分かり、トポロジ偏り判定703にて、『偏りあり』の方向へ処理が進む。偏りがないと判断した場合は、特に処理を行わず次の周期まで待機する。
【0094】
変更値算出704は、ツリートポロジにおけるノード数の偏りを解消するために、センサノード206が周辺探索メッセージにおいて通知するホップ数を算出する処理である。本実施形態では、変更値算出704は、センサノード206が周辺探索メッセージにおいて通知するホップ数を実際のホップ数2に1を加えたホップ数3へ変更すると算出し、ツリートポロジのノード数の平準化を行う。変更値の算出には、ツリートポロジ情報80上のデータのみを使用してもよいし、位置情報や消費電力量など他の情報を加えて算出してもよい。算出した変更値は、図8のツリートポロジ情報に記録される。
【0095】
次に、変更メッセージ作成705では、トポロジ管理部4051が算出したホップ数の変更値をルーティング機能部302に通知し、パケット送受信部3024が該当のノード(センサノード206)へ要求を出すためのメッセージを作成する。その後、変更通知送信706の処理において、無線通信部301を通して送信を行う。この変更要求メッセージは、センサノード203を中継してセンサノード206へ届けられる。
【0096】
センサネットワーク206は、上記変更要求メッセージを無線通信部301を通して、ルーティング機能部302で受信する。受信した変更要求メッセージの内容は、パケット送受信部3024から周辺ノード情報取得部3023へ通知され、周辺ノード情報取得部3023に強制変更値として保存される。この後、変更応答メッセージを無線通信部301からシンクノード201へ送信する。この変更応答メッセージを受けたシンクノード201では、変更が行われた場合、図8のツリートポロジの該当する変更フラグが1(変更あり)に設定される。
【0097】
センサノード206の周辺ノード情報取得部3023は、変更値が保存されている場合、自ノード206が選択している上位接続先ノード203が送信しているシンクノードまでのホップ数1に1を加えて計算するホップ数2に代えて、変更値を用いる。変更値が保存されていない場合には、上記計算したホップ数2をそのまま使用する。センサノード206の周辺ノード情報取得部3023は、変更値を保存すると速やかに(或いは次の周期の到来を待ってもよい)、変更値を用いて周辺探索メッセージをブロードキャストで送信する。すなわち、今の例では、センサノード206は、シンクノード201までのホップ数を実際は2ホップであるが、3ホップとして送信する。この周辺探索メッセージを受信した周囲のシンクノード205、209、210、211等は、センサノード206を上位接続先ノード候補とするメトリック値の計算を実施する。この結果、センサノード206よりもメトリック値の小さな他の上位接続先ノード候補が存在すれば、接続先変更処理を実施する。
【0098】
メトリック変更応答受信707の処理では、シンクノード201は、指定した変更値の反映処理について結果を確認し、応答判定708にて変更不可の場合は、変更通知送信706の処理を再度実施する(このとき、図8のツリートポロジ情報の該当する変更フラグを0に戻し、変更値を消去する)。数回繰り返しても変更できない場合は、処理を終了し、周期監視状態へ戻る。他方、変更完了の場合、接続先変更通知が受信されるのを一定期間だけ待ち合わせ、接続先変更通知を受信すると、トポロジ情報更新709にてトポロジを再構築し、ネットワークデータベース更新710にてその結果をデータベース上へ反映する。
【0099】
図9は、トポロジ情報更新709にて再構築されたツリートポロジを示す。図9を参照すると、ツリートポロジは平準化された状態である。これは、センサノード206から送信されるホップ数が2から3に変わったことで、センサノード209、211が上位接続先ノードとしてセンサノード206でなくセンサノード205、207を選択したことによる。これにより、センサノード206に接続していた下位ノード数は3台から1台へと減少し、負荷分散することができる。さらに、ツリートポロジは、2ホップ目のセンサノード(204,205,206,207)の下位ノードが全て1台となり平準化できる。
【0100】
上記接続変更処理する際、ネットワーク上へ送信されるメッセージ数は要求と応答の2メッセージ、送信回数はホップ数の2回であり、総送信回数は4回である。これに対して、各センサノード209、211へ接続先変更メッセージを送信する場合は、メッセージ数は要求2つ、応答2つの合計4メッセージで、送信回数はホップ数の3回となり、総送信回数は12回となる。このことから、本実施形態では、送信回数で3分の1となり、ネットワークの通信負荷を抑えつつ、ツリートポロジのノード数の平準化、ネットワークの負荷分散を実現できる。
【0101】
[効果]
このように本実施形態は、以下に記載するような効果を奏する。
第1の効果は、ツリートポロジにおけるノード数の偏りを平準化するのに、接続先を切り替える下位のノードでなく、その上位のノードに対して、周囲に送信するホップ数を変更する要求メッセージを与えることで実施するため、ツリートポロジの平準化による負荷分散を実施する際の通信量を抑えられることである。
第2の効果は、ツリートポロジにおけるノード数の偏りを平準化する際に、どのセンサノードをどのセンサノードに接続換えすべきかを算出する必要がないため、計算量を少なくできることである。
第3の効果は、ホップ数を強制的に変更しても、各センサノードは上位接続先ノード候補の中からメトリック値が最も小さな上位接続先ノードを自律的に決定するため、通信可能な状態を維持したまま平準化が実施可能なことである。
【0102】
なお、本実施形態では、ホップ数を強制的に変更する例を示したが、第1の実施形態において既に説明したように、ホップ数以外のデータ、例えば子ノード数やメトリック値やハンディキャップ値を変更対象とすることも可能である。
【0103】
また設定した強制変更値の設定を解除する方法は任意で良い。例えば、設定してから一定期間経過後に自動的に解除するようにしてもよい。
【0104】
[第3の実施形態]
本実施形態は、電力、ガス、水道の使用量を無線により検針する自動検針システムなどへ適用するのに好適な実施形態を示す。自動検針システムにおいては、シンクノードが複数ある大規模ネットワークとなる。そのため、シンクノード間での帰属ノード数の平準化が必要になる。
【0105】
第2の実施形態においては、シンクノードが1台のみ存在し、ツリートポロジを1つ構成し、ツリートポロジにおけるノード数の偏りの平準化を実施した。本実施形態では、シンクノードが2台存在する場合について説明を行う。また、シンクノードの数が3台以上となった場合も同様に実現できる。
【0106】
図10を参照すると、シンクノードが2台存在する。シンクノード1000、1021は、有線ネットワークへ接続され、トポロジデータベース1030と有線を介して接続する。トポロジデータベース1030は、ネットワーク情報とセンシングデータとを格納する機能と、偏り是正機能とを有する。図10において、各ノード間の無線リンクは折れ線で示し、各リンク上に記述した数値は、下位ノードの上位接続先ノードに対するメトリック値を示す。また、破線のリンクは接続に使用されていないが、通信が可能である予備リンクを示す。
【0107】
図11は、偏り是正前のトポロジデータベース上のトポロジ情報110を示している。図11を参照すると、トポロジ情報110は、各ノードの識別子に対応して、シンクノードまでのホップ数、シンクノードと通信する際の上位接続先ノード、この上位接続先ノードを選定する際に計算したメトリック値、情報送信先のシンクノードの番号、変更フラグ、変更値を格納している。しかし、トポロジ情報110に格納される情報は、これに限定されるものではない。例えば周辺ノードの情報を含んでいても良い。図11のツリートポロジ情報110から、シンクノード1021に帰属しているセンサノード数は13台、シンクノード1000に帰属しているノード数は7台であり、シンクノード間の帰属台数に偏りがあることがわかる。トポロジデータベース1030には、トポロジの偏り調査機能や平準化機能が実装されており、シンクノード間のノード数の平準化動作を実施する。
【0108】
トポロジデータベース1030では、トポロジ偏り周期監視701を実施し、周期的にシンクノード間の帰属ノード数を比較し偏りを検査する。図10の例では、ネットワーク内にセンサノードは全部で20台存在する。
【0109】
ネットワーク上のツリートポロジ間のノード数の偏りを検出する方法の一例を以下に説明する。まず、全センサノード数をシンクノード数で割った商(10台)を平均帰属ノード数とする(式6)。帰属ノード数と平均帰属ノード数の差分許容をある量に設定(本例では2割)し、平均帰属ノード数から差分許容数(2台)を算出する(式7)。平準化実行判定閾値ノード数を、平均帰属ノード数と差分許容数とに基づいて算出し(式8)、結果を用いて判定を行う。本実施形態では、平準化実行判定閾値台数を下限は8台、上限は12台と設定する。
全ノード数 ÷ 全シンクノード数 = 平均帰属ノード数・・・・・(式6)
平均帰属ノード数 × 0.2 = 差分許容数・・・・(式7)
平均帰属ノード数 ± 差分許容数 = 平準化実行判定閾値ノード数・・・・(式8)
【0110】
上記算出方法について、差分許容量や判定実施時に平準化実行判定閾値ノード数を含むか否か、等については、特に限定するものではない。
【0111】
算出した平準化実行判定閾値ノード数を用いて、トポロジ偏り判定(703)を実施すると、シンクノード毎の帰属ノード数に偏りがあると判定する。
【0112】
次に、トポロジデータベース1030は、シンクノード1000に比べて下位ノード数が多いシンクノード1021を目的のノードとして選択し、このノード1021から周囲のノードに送信するホップ数を実際の値とは異なる値に故意に変更する。ここでは、例えば実際のホップ数が0であるところを、ホップ数1に強制的に変更する。
【0113】
図12は、シンクノード1021のホップ数を1に変更した後、一定期間経過後のトポロジデータベース上のトポロジ情報120を示している。なお、トポロジ情報120では、メトリック値や上位接続先ノードが変更となった箇所に下線を引いている。また図13は、シンクノード1021のホップ数を1に変更した後、一定期間経過後のツリートポロジを示している。
【0114】
図12および図13を参照すると、シンクノード1021の送信するホップ数が0から1に変化することにより、センサノード1019、1020のシンクノード1021に対するメトリック値が変化している。また、センサノード1019、1020から周囲に送信するホップ数が1から2へと変化するため、センサノード1018、1015のセンサノード1019に対するメトリック値、センサノード1016、1017のセンサノード1020に対するメトリック値が変化している。さらに、センサノード1018、1015、1016、1017、1013が周囲に送信するホップ数が2から3へと変化するため、センサノード1014、1008、1009、1010のセンサノード1015に対するメトリック値が変化し、センサノード1011、1012、1013のセンサノード1017に対するメトリック値が変化している。この結果、センサノード1009、1010は、センサノード1015からメトリック値のより小さなセンサノード1003に上位接続先ノードを切り替えている。また、センサノード1011は、センサノード1017からメトリック値のより小さなセンサノード1004に上位接続先ノードを切り替えている。
【0115】
以上の結果、シンクノード1000、1021に帰属しているセンサノード数は各10台になり、平準化されている。
【0116】
また、シンクノード1000、1021それぞれに帰属のトポロジ(シンクノードの内のトポロジ)に偏りがあると判断した場合は、第2の実施形態と同様の手順で平準化されることになる。
【0117】
なお、本実施形態では、ホップ数を強制的に変更する例を示したが、第1の実施形態において既に説明したように、ホップ数以外のデータ、例えば子ノード数やメトリック値やハンディキャップ値を変更対象とすることも可能である。
【0118】
以上本発明を幾つかの実施形態を挙げて説明したが、本発明は以上の実施形態にのみ限定されず、その他各種の付加変更が可能である。また、本発明の無線ノードは、その有する機能をハードウェア的に実現することは勿論、コンピュータとプログラムとで実現することができる。プログラムは、磁気ディスクや半導体メモリ等のコンピュータ可読記録媒体に記録されて提供され、コンピュータの立ち上げ時などにコンピュータに読み取られ、そのコンピュータの動作を制御することにより、そのコンピュータを前述した各実施の形態における無線ノードとして機能させる。
【産業上の利用可能性】
【0119】
本発明は、環境計測システム、自動検針システム、無線センサネットワーク、無線マルチホップネットワーク、無線基地局と無線端末などに適用可能である。
【符号の説明】
【0120】
1〜10…無線ノード
11…周辺ノード情報取得部
12…メトリック計算部
13…上位接続先ノード決定部
14…ネットワーク管理部
【特許請求の範囲】
【請求項1】
複数の無線ノードから構成され、それぞれの無線ノードが、周囲の無線ノードから受信するノード情報に関する周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、前記上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出し、該算出したメトリック値に基づいて前記上位接続先ノードを決定する、マルチホップ無線ネットワークの経路制御方法であって、
前記マルチホップ無線ネットワークにおける前記特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、該目的の無線ノードから周囲の無線ノードに送信する前記ノード情報の値を故意に変更する、
ことを特徴とするマルチホップ無線ネットワークの経路制御方法。
【請求項2】
前記目的の無線ノードは、前記木構造のネットワークトポロジにおける同階層の他の無線ノードに比較して、下位の無線ノード数が多い無線ノードであり、
前記変更では、前記ノード情報の値を、前記目的の無線ノードを前記上位接続先ノードの候補として計算される前記メトリック値がリンクの通信コスト的に大きくなるように変更する
ことを特徴とする請求項1に記載のマルチホップ無線ネットワークの経路制御方法。
【請求項3】
前記目的の無線ノードは、前記木構造のネットワークトポロジにおける同階層の他の無線ノードに比較して、下位の無線ノード数が少ない無線ノードであり、
前記変更では、前記ノード情報の値を、前記目的の無線ノードを前記上位接続先ノードの候補として計算される前記メトリック値がリンクの通信コスト的に小さくなるように変更する
ことを特徴とする請求項1に記載のマルチホップ無線ネットワークの経路制御方法。
【請求項4】
前記変更では、前記ノード情報に含まれる実際の値を異なる値に変更する
ことを特徴とする請求項1乃至3の何れかに記載のマルチホップ無線ネットワークの経路制御方法。
【請求項5】
前記実際の値が、前記目的の無線ノードから前記特定の無線ノードまでのホップ数、前記目的の無線ノードを前記上位接続先ノードに決定している前記無線ノードの数である子ノード数、前記目的の無線ノードが前記上位接続先ノードを決定する際に計算した当該上位接続先ノードの前記メトリック値のうちの少なくとも一つである
ことを特徴とする請求項4に記載のマルチホップ無線ネットワークの経路制御方法。
【請求項6】
前記変更では、前記メトリック値を計算する際に使用する重み付けパラメータの値であるハンディキャップ値を設定・変更する
ことを特徴とする請求項1乃至3の何れかに記載のマルチホップ無線ネットワークの経路制御方法。
【請求項7】
複数の無線ノードと制御ノードとから構成され、
それぞれの前記無線ノードは、
周囲の無線ノードに対して自無線ノードに関するノード情報を送信すると共に、周囲の無線ノードから受信する前記ノード情報に関する周辺ノード情報を取得する周辺ノード情報取得手段と、
前記取得された周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、前記上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出するメトリック計算手段と、
前記算出されたメトリック値に基づいて前記上位接続先ノードを決定する上位接続先ノード決定手段とを備え、
前記制御ノードは、
前記マルチホップ無線ネットワークにおける前記特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジを生成し、該生成した木構造のネットワークトポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、該目的の無線ノードから周囲の無線ノードに送信する前記ノード情報の値を故意に変更するネットワーク管理手段を備える
ことを特徴とするマルチホップ無線ネットワーク。
【請求項8】
前記マルチホップ無線ネットワークに接続される無線ノードであって、
周囲の無線ノードに対して自無線ノードに関するノード情報を送信すると共に、周囲の無線ノードから受信する前記ノード情報に関する周辺ノード情報を取得する周辺ノード情報取得手段と、
前記取得された周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、前記上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出するメトリック計算手段と、
前記算出されたメトリック値に基づいて前記上位接続先ノードを決定する上位接続先ノード決定手段と、
前記マルチホップ無線ネットワークにおける前記特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジを生成し、該生成した木構造のネットワークトポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、該目的の無線ノードから周囲の無線ノードに送信する前記ノード情報の値を故意に変更するネットワーク管理手段とを備えることを特徴とする無線ノード。
【請求項9】
マルチホップ無線ネットワークに接続される無線ノードを構成する装置を、
周囲の無線ノードに対して自無線ノードに関するノード情報を送信すると共に、周囲の無線ノードから受信する前記ノード情報に関する周辺ノード情報を取得する周辺ノード情報取得手段と、
前記取得された周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、前記上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出するメトリック計算手段と、
前記算出されたメトリック値に基づいて前記上位接続先ノードを決定する上位接続先ノード決定手段と、
前記マルチホップ無線ネットワークにおける前記特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジを生成し、該生成した木構造のネットワークトポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、該目的の無線ノードから周囲の無線ノードに送信する前記ノード情報の値を故意に変更するネットワーク管理手段として機能させるためのプログラム。
【請求項1】
複数の無線ノードから構成され、それぞれの無線ノードが、周囲の無線ノードから受信するノード情報に関する周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、前記上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出し、該算出したメトリック値に基づいて前記上位接続先ノードを決定する、マルチホップ無線ネットワークの経路制御方法であって、
前記マルチホップ無線ネットワークにおける前記特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、該目的の無線ノードから周囲の無線ノードに送信する前記ノード情報の値を故意に変更する、
ことを特徴とするマルチホップ無線ネットワークの経路制御方法。
【請求項2】
前記目的の無線ノードは、前記木構造のネットワークトポロジにおける同階層の他の無線ノードに比較して、下位の無線ノード数が多い無線ノードであり、
前記変更では、前記ノード情報の値を、前記目的の無線ノードを前記上位接続先ノードの候補として計算される前記メトリック値がリンクの通信コスト的に大きくなるように変更する
ことを特徴とする請求項1に記載のマルチホップ無線ネットワークの経路制御方法。
【請求項3】
前記目的の無線ノードは、前記木構造のネットワークトポロジにおける同階層の他の無線ノードに比較して、下位の無線ノード数が少ない無線ノードであり、
前記変更では、前記ノード情報の値を、前記目的の無線ノードを前記上位接続先ノードの候補として計算される前記メトリック値がリンクの通信コスト的に小さくなるように変更する
ことを特徴とする請求項1に記載のマルチホップ無線ネットワークの経路制御方法。
【請求項4】
前記変更では、前記ノード情報に含まれる実際の値を異なる値に変更する
ことを特徴とする請求項1乃至3の何れかに記載のマルチホップ無線ネットワークの経路制御方法。
【請求項5】
前記実際の値が、前記目的の無線ノードから前記特定の無線ノードまでのホップ数、前記目的の無線ノードを前記上位接続先ノードに決定している前記無線ノードの数である子ノード数、前記目的の無線ノードが前記上位接続先ノードを決定する際に計算した当該上位接続先ノードの前記メトリック値のうちの少なくとも一つである
ことを特徴とする請求項4に記載のマルチホップ無線ネットワークの経路制御方法。
【請求項6】
前記変更では、前記メトリック値を計算する際に使用する重み付けパラメータの値であるハンディキャップ値を設定・変更する
ことを特徴とする請求項1乃至3の何れかに記載のマルチホップ無線ネットワークの経路制御方法。
【請求項7】
複数の無線ノードと制御ノードとから構成され、
それぞれの前記無線ノードは、
周囲の無線ノードに対して自無線ノードに関するノード情報を送信すると共に、周囲の無線ノードから受信する前記ノード情報に関する周辺ノード情報を取得する周辺ノード情報取得手段と、
前記取得された周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、前記上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出するメトリック計算手段と、
前記算出されたメトリック値に基づいて前記上位接続先ノードを決定する上位接続先ノード決定手段とを備え、
前記制御ノードは、
前記マルチホップ無線ネットワークにおける前記特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジを生成し、該生成した木構造のネットワークトポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、該目的の無線ノードから周囲の無線ノードに送信する前記ノード情報の値を故意に変更するネットワーク管理手段を備える
ことを特徴とするマルチホップ無線ネットワーク。
【請求項8】
前記マルチホップ無線ネットワークに接続される無線ノードであって、
周囲の無線ノードに対して自無線ノードに関するノード情報を送信すると共に、周囲の無線ノードから受信する前記ノード情報に関する周辺ノード情報を取得する周辺ノード情報取得手段と、
前記取得された周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、前記上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出するメトリック計算手段と、
前記算出されたメトリック値に基づいて前記上位接続先ノードを決定する上位接続先ノード決定手段と、
前記マルチホップ無線ネットワークにおける前記特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジを生成し、該生成した木構造のネットワークトポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、該目的の無線ノードから周囲の無線ノードに送信する前記ノード情報の値を故意に変更するネットワーク管理手段とを備えることを特徴とする無線ノード。
【請求項9】
マルチホップ無線ネットワークに接続される無線ノードを構成する装置を、
周囲の無線ノードに対して自無線ノードに関するノード情報を送信すると共に、周囲の無線ノードから受信する前記ノード情報に関する周辺ノード情報を取得する周辺ノード情報取得手段と、
前記取得された周辺ノード情報に基づいて、特定の無線ノードとマルチホップ無線通信を行う際の上位接続先ノードの候補毎に、前記上位接続先ノードを選定するための指針を与える量を示すメトリック値を算出するメトリック計算手段と、
前記算出されたメトリック値に基づいて前記上位接続先ノードを決定する上位接続先ノード決定手段と、
前記マルチホップ無線ネットワークにおける前記特定の無線ノードを根、その他の無線ノードを節および葉とする木構造のネットワークトポロジを生成し、該生成した木構造のネットワークトポロジにおける何れかの無線ノードを目的の無線ノードとして選択し、該目的の無線ノードから周囲の無線ノードに送信する前記ノード情報の値を故意に変更するネットワーク管理手段として機能させるためのプログラム。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図14】
【図15】
【図16】
【図17】
【公開番号】特開2013−65957(P2013−65957A)
【公開日】平成25年4月11日(2013.4.11)
【国際特許分類】
【出願番号】特願2011−202237(P2011−202237)
【出願日】平成23年9月15日(2011.9.15)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.ZIGBEE
2.Bluetooth
【出願人】(000004237)日本電気株式会社 (19,353)
【出願人】(000232254)日本電気通信システム株式会社 (586)
【Fターム(参考)】
【公開日】平成25年4月11日(2013.4.11)
【国際特許分類】
【出願日】平成23年9月15日(2011.9.15)
【公序良俗違反の表示】
(特許庁注:以下のものは登録商標)
1.ZIGBEE
2.Bluetooth
【出願人】(000004237)日本電気株式会社 (19,353)
【出願人】(000232254)日本電気通信システム株式会社 (586)
【Fターム(参考)】
[ Back to top ]