TOP > 国内特許検索 > プログラム、中継ノード位置算出装置及び中継ノード位置算出方法 > 明細書

明細書 :プログラム、中継ノード位置算出装置及び中継ノード位置算出方法

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第5038215号 (P5038215)
公開番号 特開2009-246654 (P2009-246654A)
登録日 平成24年7月13日(2012.7.13)
発行日 平成24年10月3日(2012.10.3)
公開日 平成21年10月22日(2009.10.22)
発明の名称または考案の名称 プログラム、中継ノード位置算出装置及び中継ノード位置算出方法
国際特許分類 H04W  16/20        (2009.01)
H04W   4/04        (2009.01)
FI H04Q 7/00 222
H04Q 7/00 113
請求項の数または発明の数 11
全頁数 23
出願番号 特願2008-090387 (P2008-090387)
出願日 平成20年3月31日(2008.3.31)
審査請求日 平成22年8月13日(2010.8.13)
特許権者または実用新案権者 【識別番号】000173784
【氏名又は名称】公益財団法人鉄道総合技術研究所
発明者または考案者 【氏名】平井 力
【氏名】曽我 健一
個別代理人の代理人 【識別番号】100124682、【弁理士】、【氏名又は名称】黒田 泰
【識別番号】100104710、【弁理士】、【氏名又は名称】竹腰 昇
【識別番号】100090479、【弁理士】、【氏名又は名称】井上 一
審査官 【審査官】田中 寛人
参考文献・文献 特開2006-101497(JP,A)
特開2007-074564(JP,A)
特開2006-086849(JP,A)
特開2002-109675(JP,A)
特開2005-260729(JP,A)
調査した分野 G08C13/00-17/02、19/00-23/04、
25/00-25/04
H04B7/14-7/22、7/24-7/26
H04W4/00-99/00
特許請求の範囲 【請求項1】
監視対象の構造物の状態を監視するために予め設置位置が決定された複数のセンサノード及びデータ集約装置を備えたワイヤレスセンサネットワークにおいて、前記センサノードと前記データ集約装置間に介在して前記センサノードからのセンサデータを中継して転送す中継ノードを、前記構造物のどこへ設置すべきか求める処理をコンピュータに実行させるためのプログラムであって、
前記中継ノードを設置可能な前記構造物中の複数の位置候補を設定する位置候補設定手段、
前記センサノードそれぞれについて、当該センサノードから前記位置候補に設置されると仮定した中継ノードを経由して前記データ集約装置に至る通信経路であって、所定の経路条件を満たす通信経路候補を生成する経路候補生成手段、
前記生成された通信経路候補のうちから互いに同じ中継ノードを経由しない所定数の通信経路候補の組合せを前記センサノードそれぞれについて選出することで、全ての前記センサノードから前記データ集約装置に至る前記所定数分冗長な通信経路を含んだ通信経路網を算出する経路網算出手段、
前記算出された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定する設置位置決定手段、
として前記コンピュータを機能させるとともに、
前記経路網算出手段が、当該通信経路網に含まれる中継ノードの総数が少ない程高く評価する評価基準に従って当該通信経路網を評価する評価手段と、当該評価手段の評価結果に基づいて通信経路網を決定する手段とを有し、
前記設置位置決定手段が、前記経路網算出手段により決定された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定する、
ように前記コンピュータを機能させるためのプログラム。
【請求項2】
前記評価手段が、当該通信経路網を構成する経路の総経路長が短い程高く評価する基準を前記評価基準に含めて当該通信経路網を評価するように前記コンピュータを機能させるための請求項1に記載のプログラム。
【請求項3】
前記経路網算出手段が、前記中継ノードそれぞれに予め定められた最大通信容量を超えないよう、通信経路候補の組合せを選出する、
ように前記コンピュータを機能させるための請求項1又は2に記載のプログラム。
【請求項4】
前記経路条件には、センサノードから前記データ集約装置までの距離に応じた転送回数の上限である転送回数条件が少なくとも含まれ、
前記経路候補生成手段が、前記センサノードそれぞれについての通信経路候補を、当該センサノードから前記データ集約装置までの距離に対応する前記転送回数条件に定められた転送回数の上限を超えないように生成する、
ように前記コンピュータを機能させるための請求項1~3の何れか一項に記載のプログラム。
【請求項5】
前記構造物は立体的な構造物であり、
前記センサノードは前記構造物の各所の監視対象部分に設置され、
前記コンピュータは、前記複数のセンサノード及び前記データ集約装置の前記構造物への設置位置の3次元座標を記憶する記憶部を備えており、
前記位置候補設定手段が、前記複数の位置候補の3次元座標を設定し、
前記経路候補生成手段が、前記複数のセンサノード及び前記データ集約装置の3次元座標並びに前記複数の位置候補の3次元座標を用いて、前記センサノードそれぞれについて、当該センサノードから前記データ集約装置への基準方向に沿った順方向の経路のみで到達する通信経路を、当該基準方向と当該経路とのなす角度に基づいて選択することで通信経路候補として生成する
ように前記コンピュータを機能させるための請求項1~の何れか一項に記載のプログラム。
【請求項6】
前記経路網算出手段が、
前記評価基準に従った評価が最良となる前記通信経路網の厳密解を、探索的手法又は列挙的手法に基づく厳密解算出処理によって算出する厳密解算出処理手段と、
前記通信経路網の暫定解を繰り返し求め、前記評価基準に従った評価がより良い解を算出していく発見的手法に基づくヒューリスティクス処理によって前記通信経路網の準最適解を算出するヒューリスティクス処理手段と、
を有するように前記コンピュータを機能させるための請求項1~の何れか一項に記載のプログラム。
【請求項7】
前記経路網算出手段が、前記厳密解算出処理手段による前記厳密解算出処理を先に実行し、前記厳密解の算出に至らずに処理開始からの経過時間が所定時間に到達した場合に前記厳密解算出処理を中止し、前記ヒューリスティクス処理手段による前記ヒューリスティクス処理を実行するように前記コンピュータを機能させるための請求項に記載のプログラム。
【請求項8】
既存の通信経路網に対する新たなセンサノードの設置位置を設定する新センサ設置位置設定手段、
前記新たなセンサノードから前記データ集約装置に至る通信経路であって、前記所定の経路条件を満たす通信経路候補を生成する新センサ用経路候補生成手段、
前記新たなセンサノードそれぞれについて、前記新センサ用経路候補生成手段により生成された通信経路候補のうちから互いに同じ中継ノードを経由しない所定数の通信経路候補の組合せであって、前記既存の通信経路網に含まれる既存の中継ノード以外の新たな中継ノードの数がより少ない組合せを選出することで、前記新たなセンサノードから前記データ集約装置に至る前記所定数分冗長な通信経路を含んだ通信経路網を算出する新センサ包含経路網算出手段、
として前記コンピュータを機能させるための請求項1~の何れか一項に記載のプログラム。
【請求項9】
前記位置候補設定手段が、前記中継ノードを前記構造物に配置可能な範囲を格子状に区切り、該格子位置を前記位置候補として設定するように前記コンピュータを機能させるための請求項1~の何れか一項に記載のプログラム。
【請求項10】
監視対象の構造物の状態を監視するために予め設置位置が決定された複数のセンサノード及びデータ集約装置を備えたワイヤレスセンサネットワークにおいて、前記センサノードと前記データ集約装置間に介在して前記センサノードからのセンサデータを中継して転送す中継ノードを、前記構造物のどこへ設置すべきかを算出する中継ノード位置算出装置であって、
前記中継ノードを設置可能な前記構造物中の複数の位置候補を設定する位置候補設定手段と、
前記センサノードそれぞれについて、当該センサノードから前記位置候補に設置されると仮定した中継ノードを経由して前記データ集約装置に至る通信経路であって、所定の経路条件を満たす通信経路候補を生成する経路候補生成手段と、
前記生成された通信経路候補のうちから互いに同じ中継ノードを経由しない所定数の通信経路候補の組合せを前記センサノードそれぞれについて選出することで、全ての前記センサノードから前記データ集約装置に至る前記所定数分冗長な通信経路を含んだ通信経路網を算出する経路網算出手段と、
前記算出された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定する設置位置決定手段と、
を備え
前記経路網算出手段は、当該通信経路網に含まれる中継ノードの総数が少ない程高く評価する評価基準に従って当該通信経路網を評価する評価手段と、当該評価手段の評価結果に基づいて通信経路網を決定する手段とを有し、
前記設置位置決定手段は、前記経路網算出手段により決定された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定する、
中継ノード位置算出装置。
【請求項11】
監視対象の構造物の状態を監視するために予め設置位置が決定された複数のセンサノード及びデータ集約装置を備えたワイヤレスセンサネットワークにおいて、前記センサノードと前記データ集約装置間に介在して前記センサノードからのセンサデータを中継して転送す中継ノードを、前記構造物のどこへ設置すべきかを算出する中継ノード位置算出方法であって、
前記中継ノードを設置可能な前記構造物中の複数の位置候補を設定するステップと、
前記センサノードそれぞれについて、当該センサノードから前記位置候補に設置されると仮定した中継ノードを経由して前記データ集約装置に至る通信経路であって、所定の経路条件を満たす通信経路候補を生成するステップと、
前記生成された通信経路候補のうちから互いに同じ中継ノードを経由しない所定数の通信経路候補の組合せを前記センサノードそれぞれについて選出することで、全ての前記センサノードから前記データ集約装置に至る前記所定数分冗長な通信経路を含んだ通信経路網を算出するステップと、
前記算出された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定するステップと、
を含み、
前記通信経路網を算出するステップは、当該通信経路網に含まれる中継ノードの総数が少ない程高く評価する評価基準に従って当該通信経路網を評価する評価ステップと、当該評価ステップでの評価結果に基づいて通信経路網を決定するステップとを含み、
前記設置位置を決定するステップは、前記決定された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定するステップである、
中継ノード位置算出方法。
発明の詳細な説明 【技術分野】
【0001】
本発明は、ワイヤレスセンサネットワークにおける中継ノードの設置位置を算出する中継ノード位置算出方法等に関する。
【背景技術】
【0002】
ワイヤレスセンサネットワークは、各所に設置されたセンサノードによる観測データ(センサデータ)を集約することで、対象物の状態を監視するためのネットワークシステムである。ワイヤレスセンサネットワークの一形態として、ワイヤレス通信機能及びルーティング機能を有する複数のセンサノードが、センサデータを収集するシンクノードを頂点として経路木状にワイヤレス接続されたセンサネットワークが知られている。このネットワークでは、各ノードが子ノードから受信したデータ及び自身のデータを集約して親データに送信することで、センサノードからのセンサデータを、その上位に位置している親ノードに集約しながらシンクノードまで転送される(例えば、特許文献1参照)。

【特許文献1】特開2006-287565号公報
【発明の開示】
【発明が解決しようとする課題】
【0003】
ワイヤレスセンサネットワークを、例えば地下鉄のトンネルや橋梁、水道管といった構造物の監視システムに適用することができる。例えば、地下鉄のトンネルを監視対象とする場合、このトンネルの内壁に、ひび割れの発生といった状態を検出するためのセンサノードを多数設置し、これらのセンサノードによるセンサデータをトンネルの内壁に設置された中継ノードを介して無線通信で転送することで、データ集約装置に集約する。データ集約装置で集約されたデータは、例えば既設の有線通信ケーブル等を介してサーバ等の外部装置に送信される。
【0004】
実際にワイヤレスセンサネットワークを構築する際には、先ず、構造物の監視対象部分を把握し、センサノード1つ1つの設置位置を決定する。また、データ集約装置の設置位置も、電源や外部装置との接続ケーブルの敷設位置等から決定される。そして、センサノードからデータ集約装置までの通信経路が構築されるように中継ノード1つ1つの設置位置を決定するが、このとき、ネットワーク全体の性能を考慮して中継ノードの配置位置を適切に決定する必要がある。具体的には、中継ノードの設置数をより少なくして設置コストを小さくする、センサノードからデータ集約装置に至る通信経路をより短くしてデータ劣化を防止するといったように、ネットワーク全体の性能を考慮して適切なネットワークが構築されるように、中継ノードの設置位置を決定する。
【0005】
本発明は、上記事情に鑑みてなされたものであり、ワイヤレスセンサネットワークを構成する中継ノードの適切な設置位置を算出することを目的としている。
【課題を解決するための手段】
【0006】
上記課題を解決するための第1の発明は、
コンピュータ(例えば、図2のリレー位置算出装置1)に、予め設置位置が決定されたセンサノード(例えば、図1のセンサS)からのセンサデータを中継ノード(例えば、図1のリレーR)が無線通信によってデータ集約装置(例えば、図1のゲートウェイG)に中継して転送するワイヤレスセンサネットワークにおける前記中継ノードの設置位置を算出する処理を実行させるためのプログラム(例えば、図2のリレー位置算出プログラム510)であって、
前記中継ノードを設置可能な複数の位置候補を設定する位置候補設定手段(例えば、図18のステップA3)、
前記センサノードそれぞれについて、当該センサノードから前記位置候補に設置されると仮定した中継ノードを経由して前記データ集約装置に至る通信経路であって、所定の経路条件を満たす通信経路候補を生成する経路候補生成手段(例えば、図19のステップB1,図20のステップC1)、
前記生成された通信経路候補のうちから互いに同じ中継ノードを経由しない所定数の通信経路候補の組合せを前記センサノードそれぞれについて選出することで、全ての前記センサノードから前記データ集約装置に至る前記所定数分冗長な通信経路網を算出する経路網算出手段(例えば、図19のステップB9、図20のステップC11)、
前記算出された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定する設置位置決定手段(例えば、図18のステップA11,A17)、
として前記コンピュータを機能させるためのプログラムである。
【0007】
また、他の発明として、
予め設置位置が決定されたセンサノードからのセンサデータを中継ノードが無線通信によってデータ集約装置に中継して転送するワイヤレスセンサネットワークにおける前記中継ノードの設置位置を算出する中継ノード位置算出装置(例えば、図2のリレー位置算出装置1)であって、
前記中継ノードを設置可能な複数の位置候補を設定する位置候補設定手段と、
前記センサノードそれぞれについて、当該センサノードから前記位置候補に設置されると仮定した中継ノードを経由して前記データ集約装置に至る通信経路であって、所定の経路条件を満たす通信経路候補を生成する経路候補生成手段と、
前記生成された通信経路候補のうちから互いに同じ中継ノードを経由しない所定数の通信経路候補の組合せを前記センサノードそれぞれについて選出することで、全ての前記センサノードから前記データ集約装置に至る前記所定数分冗長な通信経路網を算出する経路網算出手段と、
前記算出された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定する設置位置決定手段と、
を備える中継ノード位置算出装置を構成しても良い。
【0008】
また、他の発明として、
予め設置位置が決定されたセンサノードからのセンサデータを中継ノードが無線通信によってデータ集約装置に中継して転送するワイヤレスセンサネットワークにおける前記中継ノードの設置位置を算出する中継ノード位置算出方法であって、
前記中継ノードを設置可能な複数の位置候補を設定するステップと、
前記センサノードそれぞれについて、当該センサノードから前記位置候補に設置されると仮定した中継ノードを経由して前記データ集約装置に至る通信経路であって、所定の経路条件を満たす通信経路候補を生成するステップと、
前記生成された通信経路候補のうちから互いに同じ中継ノードを経由しない所定数の通信経路候補の組合せを前記センサノードそれぞれについて選出することで、全ての前記センサノードから前記データ集約装置に至る前記所定数分冗長な通信経路網を算出するステップと、
前記算出された通信経路網に含まれる中継ノードの位置候補を、中継ノードの設置位置として決定するステップと、
を含む中継ノード位置算出方法を構成しても良い。
【0009】
この第1の発明等によれば、中継ノードを設置可能な複数の位置候補が設定され、センサノードそれぞれについて、設定された位置候補に設置されると仮定した中継ノードを経由してデータ集約装置に至る所定の経路条件を満たす通信経路候補が生成される。そして、生成された通信経路候補のうちから、所定数の通信経路候補の組合せがセンサノードそれぞれについて選出されることで、全てのセンサノードからデータ集約装置に至る冗長な通信経路網が算出され、算出された通信経路網に含まれる中継ノードの位置候補が、ワイヤレスセンサネットワークにおける中継ノードの設置位置として決定される。すなわち、全てのセンサノードからデータ集約装置に至る通信経路網を生成し、この通信経路網に含まれる中継ノードの位置候補を中継ノードの設置位置として決定することで、ワイヤレスセンサネットワークにおける中継ノードの最適な設置位置の算出が可能となる。また、生成される通信経路網は、1つのセンサノードについて互いに同じ中継ノードを経由しない所定数の通信経路が確保されている。これにより、例えば中継ノードの故障によって1つの通信経路が遮断されたとしても他の通信経路を利用することができるといった、信頼性の高い通信経路網の構築が可能となる。
【0010】
第2の発明として、第1の発明のプログラムであって、
前記経路網算出手段が、前記中継ノードそれぞれに予め定められた最大通信容量を超えないよう、通信経路候補の組合せを選出する、
ように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0011】
この第2の発明によれば、中継ノードそれぞれに予め定められた最大通信容量を超えないよう、通信経路候補の組合せが選出されて通信経路網が算出される。これにより、設置される中継ノードの通信容量を考慮した最適な通信経路網の構築が可能となる。
【0012】
また、第3の発明として、第1又は第2の発明のプログラムであって、
前記経路条件には、センサノードから前記データ集約装置までの距離に応じた転送回数の上限である転送回数条件が少なくとも含まれ、
前記経路候補生成手段が、前記センサノードそれぞれについての通信経路候補を、当該センサノードから前記データ集約装置までの距離に対応する前記転送回数条件に定められた転送回数の上限を超えないように生成する、
ように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0013】
この第3の発明によれば、センサノードそれぞれについての通信経路候補は、当該センサノードからデータ集約装置までの距離に応じた転送回数の上限を超えないように生成される。転送回数に上限を設けることで、算出される通信経路候補の総数を制限し、通信経路網の算出時間が長くなり過ぎることを防止できる。また、センサノードからデータ集約装置までの通信経路における転送回数が多くなるほど、転送されるデータの劣化程度が大きくなるが、通信経路候補の転送回数に上限が設けられることで、冗長な通信経路候補が算出されることを防止し、信頼性の高い通信経路網の構築が可能となる。
【0014】
また、第4の発明として、第1~第3の何れかの発明のプログラムであって、
前記経路候補生成手段が、前記センサノードから前記データ集約装置へ順方向の経路のみで到達する通信経路を通信経路候補として生成するように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0015】
この第4の発明によれば、通信経路候補は、センサノードからデータ集約装置へ順方向のみで到達する通信経路として生成される。すなわち、通信経路候補は後戻りする経路ではないため、迂遠な通信経路候補が生成されることが防止される。
【0016】
また、第5の発明として、第1~第4の何れかの発明のプログラムであって、
前記経路網算出手段が、
所定の評価基準に従った評価が最良となる前記通信経路網の厳密解を、探索的手法又は列挙的手法に基づく厳密解算出処理によって算出する厳密解算出処理手段と、
前記通信経路網の暫定解を繰り返し求め、前記所定の評価基準に従った評価がより良い解を算出していく発見的手法に基づくヒューリスティクス処理によって前記通信経路網の準最適解を算出するヒューリスティクス処理手段と、
を有するように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0017】
この第5の発明によれば、通信経路網の算出として、1)所定の評価基準に従った評価が最良となる通信経路網の厳密解を探索的手法又は列挙的手法に基づいて算出する厳密解算出処理と、2)通信経路網の暫定解を繰り返し求め、所定の評価基準に従った評価がより良い解を算出していく発見的手法に基づいて通信経路網の準最適解を算出するヒューリスティクス処理とが行われる。
【0018】
また、第6の発明として、第5の発明のプログラムであって、
前記経路網算出手段が、前記厳密解算出処理手段による前記厳密解算出処理を先に実行し、前記厳密解の算出に至らずに処理開始からの経過時間が所定時間に到達した場合に前記厳密解算出処理を中止し、前記ヒューリスティクス処理手段による前記ヒューリスティクス処理を実行するように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0019】
この第6の発明によれば、通信経路網の算出は、1)厳密解算出処理が先に実行され、厳密解の算出に至らずに処理開始からの経過時間が所定時間に到達した場合に、厳密解算出処理が終了されて、2)ヒューリスティクス処理が実行される。つまり、厳密解算出処理による厳密解の算出の時間制限を設け、制限時間内に厳密解が算出されない場合にヒューリスティクス処理によって準最適解を算出することで、制限時間を超える厳密解の算出を中止し、算出にかける時間に見合った適切と思われる中継ノードの設置位置の算出が可能となる。
【0020】
また、第7の発明として、第5又は第6の発明のプログラムであって、
前記厳密解算出処理手段及び前記ヒューリスティクス処理手段が、総経路長及び/又は総中継ノード数に基づく評価基準に従って、対応する前記厳密解算出処理及び前記ヒューリスティクス処理を実行するように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0021】
この第7の発明によれば、総経路長及び/又は総中継ノード数に基づく評価基準に従って、厳密解算出処理及びヒューリスティクス処理が行われる。
【0022】
また、第8の発明として、第7の発明のプログラムであって、
前記厳密解算出処理手段及び前記ヒューリスティクス処理手段が、総経路長のより短い通信経路網をより高く評価する評価基準に従って、対応する前記厳密解算出処理及び前記ヒューリスティクス処理を実行するように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0023】
この第8の発明によれば、総経路長のより短い通信経路網をより高く評価する評価基準に従って、厳密解算出処理及びヒューリスティクス処理が行われる。総経路長が長くなるほど、中継ノードの数が増加し機器コスト及び設置コストが増加し得る。仮に、中継ノードの数が一定であったとしても、総経路長が長くなると、各中継ノードの通信電力の必要量が増加しバッテリ交換の頻度が上がる。何れの場合であっても、総経路長のより短い通信経路網をより高く評価することで、より適切な中継ノードの設置位置の算出が可能となる、
【0024】
また、第9の発明として、第7又は第8の発明であって、
前記厳密解算出処理手段及び前記ヒューリスティクス処理手段が、総中継ノード数のより少ない通信経路網をより高く評価する評価基準に従って、対応する前記厳密解算出処理及び前記ヒューリスティクス処理を実行するように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0025】
この第9の発明によれば、総中継ノード数のより少ない通信経路網をより高く評価する評価基準に従って、厳密解算出処理及びヒューリスティクス処理が行われる。総中継ノード数が少ないほど、通信経路網全体としての中継ノードの機器コスト及び設置コストが少なくてすむ。このため、総中継ノード数のより少ない通信経路網をより高く評価することで、より最適な中継ノードの設置位置の算出が可能となる。
【0026】
また、第10の発明として、第1~第9の何れかの発明のプログラムであって、
既存の通信経路網に対する新たなセンサノードの設置位置を設定する新センサ設置位置設定手段(たとえば、図21のステップD3)、
前記新たなセンサノードから前記データ集約装置に至る通信経路であって、前記所定の経路条件を満たす通信経路候補を生成する新センサ用経路候補生成手段(例えば、図21のステップD13)、
前記新たなセンサノードそれぞれについて、前記新センサ用経路候補生成手段により生成された通信経路候補のうちから互いに同じ中継ノードを経由しない所定数の通信経路候補の組合せであって、前記既存の通信経路網に含まれる既存の中継ノード以外の新たな中継ノードの数がより少ない組合せを選出することで、前記新たなセンサノードから前記データ集約装置に至る前記所定数分冗長な通信経路を含んだ通信経路網を算出する新センサ包含経路網算出手段(例えば、図21のステップD19)、
として前記コンピュータを機能させるためのプログラムを構成しても良い。
【0027】
この第10の発明によれば、既存の通信経路網に対して新たなセンサノードの設置位置が設定され、新たなセンサノードからデータ集約装置に至る所定の経路条件を満たす通信経路候補が生成される。そして、新たなセンサノードそれぞれについて、互いに同じ中継ノードを経由しない通信経路候補の組合せであって、既存の中継ノード以外の新たな中継ノードの数がより少ない組合せを選出することで、新たなセンサノードからデータ集約装置に至る所定数分冗長な通信経路を含んだ通信経路網が算出される。これにより、既存の通信経路網に対して新たなセンサノードを追加する際に、この新たなセンサノードからデータ集約装置に至る通信経路を既存の通信経路網に追加した通信経路網を生成し、生成した通信経路網に含まれる中継ノードの位置を新たに追加する中継ノードの設置位置として算出することができる。このとき、新たに追加する中継ノード数が最も少なくなるような通信経路網が生成されるため、新たな中継ノードの機器コスト及び設置コストを抑えることができる。また、新たなセンサノードについて互いに同じ中継ノードを経由しない所定数の通信経路が確保された通信経路網が生成されるため、信頼性の高い通信経路網の構築が可能となる。
【0028】
また、第11の発明として、第1~第10の何れかの発明のプログラムであって、
前記ワイヤレスセンサネットワークは、所定の構造物の検査用に前記センサノードを配設し、前記データ集約装置でセンサデータを集約して前記構造物を診断するためのネットワークであり、
前記位置候補設定手段が、前記中継ノードを前記構造物に配置可能な範囲を格子状に区切り、該格子位置を前記位置候補として設定するように前記コンピュータを機能させるためのプログラムを構成しても良い。
【0029】
この第11の発明によれば、ワイヤレスセンサネットワークを、構造物の検査用にセンサノードを配設し、データ集約装置でセンサデータを集約する構造物を診断するためのネットワークに適用することができる。また、中継ノードを設置可能な構造物の範囲を格子状に区切った格子位置が、中継ノードの位置候補として設置される。従って、中継ノードの位置候補が格子状に設定されることで、通信経路候補の算出等の演算処理が容易となり、また、設置後の中継ノード管理も容易となる。このとき、格子位置の間隔は中継ノードの通信可能距離よりも短く設定することが望ましい。
【発明の効果】
【0030】
本発明によれば、全てのセンサノードからデータ集約装置に至る通信経路網を生成し、この通信経路網に含まれる中継ノードの位置候補を中継ノードの設置位置として決定することで、ワイヤレスセンサネットワークにおける中継ノードの最適な設置位置の算出が可能となる。また、生成される通信経路網は、1つのセンサノードについて互いに同じ中継ノードを経由しない所定数の通信経路が確保されている。これにより、例えば中継ノードの故障によって1つの通信経路が遮断されたとしても他の通信経路を利用することができるといった、信頼性の高い通信経路網の構築が可能となる。
【発明を実施するための最良の形態】
【0031】
以下、図面を参照して、本発明の好適な実施形態を説明する。
【0032】
[原理]
本実施形態のリレー位置算出装置は、ワイヤレスセンサネットワークの構成要素の一つであるリレー(中継ノード)の最適と思われる設置位置を算出する装置である。ワイヤレスセンサネットワークは、例えば地下鉄のトンネルや橋梁といった構造物の状態を監視するために構築される。
【0033】
図1に、地下鉄のトンネルを検査対象の構造物としたワイヤレスセンサネットワークの概念を示す。同図によれば、ワイヤレスセンサネットワークNは、センサノードであるセンサSと、中継ノードであるリレーRと、データ集約装置であるゲートウェイGとから構成される。
【0034】
センサSは、トンネル内壁の監視対象部分に設置され、監視対象部分のひび割れや振動等を検出する。また、このセンサSは無線通信機能を有し、検出結果のデータ(センサデータ)を、送信先として予め定められたリレーR或いはゲートウェイGに送信する。リレーRは、無線通信機能を有し、センサSや他のリレーRからの受信データを、送信先として予め定められた他のリレーR或いはゲートウェイGに転送する。ゲートウェイGは、トンネル内の所定区間毎に設置され、例えば既設の外部ケーブルを介して外部の管理装置等に接続されている。そして、ゲートウェイGは、該当する区間内に設置されている各センサSによるセンサデータを集約して外部装置に転送する。つまり、ワイヤレスセンサネットワークNでは、センサSによるセンサデータは、リレーRを介した転送(ホッピング)を繰り返すことで、当該区間のセンサデータを集約するゲートウェイGまで送信される。
【0035】
ところで、ゲートウェイGの設置位置は、電源や外部ケーブルの敷設位置等によって制限される。つまり、ワイヤレスセンサネットワークの構築の際には、センサS及びゲートウェイGの設置位置を定めた後に、リレーRの適切な設置位置を決定することになる。なお、本実施形態において、ワイヤレスセンサネットワークは、各センサSそれぞれについて、同一のリレーRを経由しない2つの通信経路を有する冗長的なネットワークとして構築される。そして、本実施形態のリレー位置算出装置は、初期設定としてセンサS及びゲートウェイGの設置位置を先ず入力・設定した後に、最適と思われるリレーRの設置位置を算出するものである。
【0036】
[構成]
図2は、本実施形態のリレー位置算出装置1の内部構成を示すブロック図である。同図によれば、リレー位置算出装置1は、処理部100と、入力部200と、表示部300と、通信部400と、記憶部500とが、バスBにより互いにデータ通信可能に接続されて構成された公知のコンピュータシステムを用いて実現される。
【0037】
処理部100は、記憶部500に記憶されるプログラムやデータ、入力部200から入力されたデータ等に基づいて、リレー位置算出装置1を構成する各部への指示やデータ転送を行い、リレー位置算出装置1の全体制御を行う。また、本実施形態では、処理部100は、リレー位置算出プログラム510に従ったリレー位置算出処理を行う。
【0038】
リレー位置算出処理では、センサS及びゲートウェイGそれぞれの設置位置をもとに、複数の設置位置候補Pのうちから、リレーRの最適と思われる設置位置を決定する。なお、設置位置を含むゲートウェイGについてのデータはゲートウェイデータ521に格納されており、各センサSについてのデータはセンサデータ522に格納されている。
【0039】
図3に、センサデータ522の一例を示す。同図によれば、センサデータ522は、設置されているセンサ522aそれぞれについて、設置位置522bと、データ発信率522cと、最大データ転送率522dと、通信可能距離522eとを対応付けて格納している。
【0040】
具体的には、先ず、リレーRの設置位置の候補Pを設定する。図4に、設置位置候補Pの設定例を示す。ここで、リレーRの設置可能な位置には制限がある。すなわち、地下鉄の場合、リレーRはトンネルの内壁に設置されるが、既存設備や列車の運行の妨げにならず、設置作業や設置後の保守作業が容易といった所定の条件を満たす範囲を、リレーRの設置可能な範囲とする。そして、このようなリレーRの設置可能範囲内であって、トンネルの内壁面を格子状に区切った格子点に、リレーRの設置位置候補Pを設定する。格子点の間隔はリレーRの通信可能距離を考慮し、具体的には通信可能距離の1/3~1/4程度とする。例えばリレーRの通信可能距離が15~20m程度の場合、格子点の間隔を5m程度となるように設定する。ここで、設置位置候補Pは、設定可能範囲内の全ての格子点に設定しても良いし、或いは、設定可能範囲内の格子点のうちから、入力部200の指示に従って選択した格子点に設定しても良い。
【0041】
設定された設置位置候補Pについてのデータは、リレー位置候補データ523に格納される。図5に、リレー位置候補データ523のデータ構成の一例を示す。同図によれば、リレー位置候補データ523は、位置候補523aそれぞれについて、当該位置に設置されるリレー523bと、そのリレーの最大データ転送率523cと、通信可能距離523dを対応付けて格納している。
【0042】
位置候補Pを設定すると、これらの位置候補Pの全てにリレーRを配置したと仮定し、センサSからリレーRを経由してゲートウェイGに至る通信経路候補を算出する。このとき、センサS及びリレーRそれぞれに定められた通信可能距離を考慮し、あるノードの通信可能距離内にあるノードをその次のノードとするように、通信経路候補を算出する。
【0043】
図6に、通信経路候補の一例を示す。同図(a)では、センサSからゲートウェイGに至る通信経路候補として、リレーR1,R3を経由する経路1と、リレーR2,R5を経由する経路2とが生成されている。また、センサSはリレーRとしても機能する。つまり、同図(b)に示すように、センサS1からゲートウェイGに至る通信経路候補として、センサS2及びリレーR2を経由する経路を生成することも可能である。
【0044】
このとき、処理部100は、所定の経路条件を満たすように通信経路候補を生成する。経路条件とは、(1)後戻りしない、(2)転送回数が所定の上限を超えない、ことである。
【0045】
図7は、経路条件(1)を説明する図である。同図(a)では、センサSからゲートウェイGに至る通信経路候補として、リレーR1,R3を経由する経路1と、リレーR2,R6,R7を経由する経路2とが生成されている。「後戻りしない」経路とは、センサSからゲートウェイGに向かう順方向の経路のみで構成される通信経路である。具体的には、同図(b)に示すように、センサSからゲートウェイGに向かう方向を基準方向V0とし、経路中の各ノードからその次ノードに向かう経路方向Vnがこの基準方向V0に対して「順方向」であるか「逆方向」であるかを判定することで、当該経路が「後戻りしない」経路であるか否かを判定する。順方向であるか逆方向であるかは、センサSからゲートウェイGに向かう基準方向V0と、経路中の各ノードが次のノードに向かう経路方向Vnとが成す角度をもとに判定する。すなわち、この角度が90度以内ならば順方向と判定し、90度を超えるならば逆方向とする。
【0046】
同図(b)では、経路1において、センサSからリレーR1に向かう経路方向V1a、リレーR1からリレーR3に向かう経路方向V1b、及びリレーR3からゲートウェイGに向かう経路方向V1cは、何れも基準方向V0に対して「順方向」である。従って、経路1は「後戻りしない」経路であり、経路条件(1)を満たす。一方、経路2では、リレーR7からゲートウェイGに向かう経路方向V2dが、基準方向に対して「逆方向」となっている。従って、経路2は「後戻りする」経路であり、経路条件(1)を満たさない。
【0047】
また、図8は、経路条件(2)を説明する図である。同図では、センサSからゲートウェイGに至る通信経路として、リレーR2,R5を経由する経路1と、リレーR1,R3,R4,R6を経由する経路2とが生成されている。センサSには、ゲートウェイGからの距離Dに応じた転送回数の上限が定められる。この転送回数の上限は、距離Dが長いほど、大きい値に定められる。同図では、センサSとゲートウェイGとの間の距離Dは、D2<D<D3、であり、転送回数の上限は「3」である。従って、経路1の転送回数は「2」であり、転送回数の上限「3」以下であるため、経路条件(2)を満たす。一方、経路2の転送回数は「4」であり、転送回数の上限「3」を超えているため、経路条件(2)を満たさない。
【0048】
ここで、各センサSの最大転送回数は、最大転送回数テーブル524に従って算出される。図9に、最大転送回数テーブル524のデータ構成の一例を示す。同図によれば、最大転送回数テーブル524は、ゲートウェイからの距離524aと、最大転送回数524bとを対応付けて格納している。
【0049】
そして、算出された各センサSの最大転送回数は、最大転送回数データ525に格納される。図10に、最大転送回数データ525のデータ構成の一例を示す。同図によれば、最大転送回数データ525は、センサ525aそれぞれについて、算出された最大転送回数525bを対応付けて格納している。
【0050】
また、算出された通信経路候補についてのデータは、通信経路候補データ526に格納される。図11に、通信経路候補データ526のデータ構成の一例を示す。同図によれば、通信経路候補データ526は、センサ526aそれぞれについて、算出した通信経路候補526bと、その転送回数526cと、経路長526dとを対応付けて格納している。
【0051】
通信経路候補を算出すると、処理部100は、続いて、センサSそれぞれについて、互いに同じリレーRを経由しない2つの通信経路候補からなる経路組を算出する。算出された経路組についてのデータは、経路組データ527に格納される。図12に、経路組データ527のデータ構成の一例を示す。同図によれば、経路組データ527は、センサ527aそれぞれについて、算出した経路組527bを対応付けて格納している。
【0052】
そして、処理部100は、生成した経路組のうちから、各センサSについて1つの経路組を選出し、選出した経路組で構成される「通信経路網」を算出する。この通信経路網の算出は、(A)厳密解算出処理、(B)ヒューリスティクス処理、の2種類の処理を用いて行う。すなわち、先ず、(A)厳密解算出処理によって通信経路網の厳密解の算出を試みる。そして、この厳密解算出処理によって所定時間内に厳密解が算出されなかった場合には、続いて、(B)ヒューリスティクス処理によって通信経路網の準最適解を算出する。ここで「準最適解」としたのは、ヒューリスティクス処理による解が、必ずしも厳密な意味での最適な解であるとは限らないためである。
【0053】
厳密解算出処理では、全ての解を列挙し、これらのうちから所定の制約条件を満たし、且つ評価が最も良い解を探す列挙的手法によって通信経路網の厳密解を算出する。すなわち、センサSそれぞれについて全ての通信経路候補を算出し、これらの通信経路候補からなる全ての経路組を算出する。そして、各センサSについて1つの経路組を選出して構成される全ての通信経路網を算出し、これらの全ての通信経路網のうち、通信容量条件を満たし、且つ、評価が最良となる通信経路網を厳密解とする。なお、厳密解算出処理としては、列挙的方法ではなく、探索的手法を用いても良いのは勿論である。
【0054】
ここで、通信容量条件は、通信経路網に含まれる各ノードのデータ転送率が、当該ノードに定められた最大データ転送率(最大通信容量)βを超えないことである。図13は、通信容量条件を説明する図である。同図では、センサS1についての通信経路候補として、リレーR1,R6を経由する経路1と、リレーR4を経由する経路2と、センサS2についての通信経路候補として、リレーR3,R4を経由する経路3と、リレーR5を経由する経路4とから構成される通信経路網が生成されている。リレーRnのデータ転送率γnは、当該リレーRnを経由する経路それぞれの始点ノードであるセンサSmのデータ発信率αmの和となる。
【0055】
例えば、同図では、リレーR1のデータ転送率γ1は、当該リレーR1を経由する経路1の始点ノードであるセンサS1のデータ発信率α1となる。また、リレーR2は何れも経路にも用いられないので、そのデータ転送率γ2はゼロとなる。また、リレーR4のデータ転送率γ4は、経路2のセンサS1のデータ発信率α1と、経路3のセンサS2のデータ発信率α2との和となる。他のリレーR3,R5~R8それぞれについても同様である。そして、全てのリレーR1~R8それぞれのデータ転送率γ1~γ8が、定められた最大データ転送率β1~β8以下ならば、通信容量条件を満たすと判定される。
【0056】
また、通信経路網の「評価」は、当該通信経路網に含まれるリレーRの総数を基準として行う。具体的には、リレーの総数が少ないほど、良い評価とする。図14は、通信経路網の評価を説明する図である。同図では、2つのセンサS1,S2それぞれについて1つの経路組を選出して構成した通信経路網の一例を示している。
【0057】
同図(a)に示す通信経路網は、センサS1についての通信経路候補として、リレーR1,R6を経由する経路1と、リレーR2,R4を経由する経路2と、センサS2についての通信経路候補として、リレーR3,R7を経由する経路3と、リレーR5,R8を経由する経路4とから構成される。つまり、この通信経路網に含まれるリレーRの総数は「8」である。また、同図(b)に示す通信経路網は、センサS1の通信経路候補として、リレーR1,R6を経由する経路1と、リレーR4を経由する経路5と、センサS2の通信経路候補として、リレーR3,R4を経由する経路6と、リレーR5を経由する経路7とから構成される。つまり、この通信経路網に含まれるリレーRの総数は「5」である。従って、同図(b)に示す通信経路網の方が、同図(a)に示す通信経路網よりも良いと評価される。
【0058】
ヒューリスティクス処理では、通信経路網の暫定解を繰り返し求め、評価がより良い解に更新してゆく発見的手法によって準最適解を算出する。具体的には、先ず、各センサSについて所定数の経路組を算出する。そして、算出した所定数の経路組を対象として所定の選出条件を満たす通信経路網を算出し、これらのうちから評価が最良となるものを準最適解(準最適通信網)とする。
【0059】
選出条件は、(1)各センサについて1つの経路組を選出する、(2)各ノードのデータ転送率γが最大データ転送率αを超えない(通信容量条件)、である。すなわち、対象とする所定数の経路組それぞれに変数Xを割り当て、選出条件を満たす条件式を算出する。変数Xは対応する経路組を選択するか否かを示す変数であり、「1」は当該経路組を選択することを示し、「0」は選択しないことを示す。
【0060】
図15は、準最適解の算出を説明する図である。同図では、2つのセンサS1,S2それぞれにつき2つの経路組を対象とした場合を示している。センサS1の経路組1,2それぞれに変数X1,X2が割り当てられ、センサS2の経路組3,4それぞれに変数X3,X4が割り当てられている。そして、選出条件(1)を満たす条件式は、同図の場合には次式(1)となる。
【数1】
JP0005038215B2_000002t.gif
また、選出条件(2)を満たす条件式は、同図の場合には次式(2)となる。
【数2】
JP0005038215B2_000003t.gif
そして、式(1),(2)を満たす解を算出する。
【0061】
図16は、図15に対する解を示す図である。図16によれば、4つの解(1)~解(4)が算出されている。すなわち、解(1)は、センサS1の経路組1と、センサS2の経路組3とからなる通信経路網である。また、解(2)は、センサS1の経路組1と、センサS2の経路組4とからなる通信経路網である。また、解(3)は、センサS1の経路組2と、センサS2の経路組3とからなる通信経路網である。また、解(4)は、センサS1の経路組2と、センサS2の経路組4とからなる通信経路網である。そして、これらの解のうちから、評価が最良となる解を選択する。この評価は、上述の厳密解算出処理の場合と同様に、通信経路網におけるリレーRの総数を評価基準として行い、通信経路網に含まれるリレーRの総数が少ないほど、良い評価とする。
【0062】
算出された準最適解についてのデータは、準最適解データ528に格納される。図17に、準最適解データ528のデータ構成の一例を示す。同図によれば、準最適解データ528は、センサ528aそれぞれについて、選出された経路組528bを対応付けて格納している。
【0063】
準最適解を算出すると、処理部100は、続いて、暫定解を算出して準最適解を更新する処理を繰り返し行う。具体的には、1つのセンサSをランダムに選択し、この選択したセンサSについて新たな1つの経路組を算出する。ここで、新たな経路組は、準最適解の算出に用いた経路組とは異なる経路組とする。次いで、準最適解の通信経路網(準最適通信網)において、選択したセンサSについての経路組を、新たな経路組に置き換えた通信経路網を生成し、暫定解(暫定通信網)とする。そして、この暫定解(暫定通信網)を評価し、準最適解(準最適通信網)と比較して評価が良いならば、この暫定解を準最適解として更新する。処理部100は、この準最適解の更新の処理を繰り返し実行する。そして、繰り返し回数が所定回数に達すると、繰り返し実行を終了し、終了した時点での準最適解の通信経路網(準最適通信網)に含まれる各リレーRに対応する位置候補Pを、リレーRの最適な設置位置として決定する。
【0064】
図2に戻り、入力部200は、例えばキーボードやマウス、タッチパネル、各種スイッチ等によって実現される入力装置であり、操作入力に応じた入力信号を処理部100に出力する。表示部300は、例えばLCD(Liquid Crystal Display)やELD(Electronic Luminescent Display)等によって実現される表示装置であり、処理部100から入力される表示信号に基づく各種画面を表示する。通信部400は、例えば、無線通信モジュールやルータ、モデム、TA、有線用の通信ケーブルのジャックや制御回路等によって実現される通信装置であり、外部機器との間でデータ通信を行う。
【0065】
記憶部500は、処理部100がリレー位置算出装置1を統合的に制御するための諸機能を実現するためのシステムプログラムやデータ等を記憶しているとともに、処理部100の作業領域として用いられ、処理部100が各種プログラムに従って実行した演算結果や、入力部200からの入力信号等が一時的に格納される。本実施形態では、記憶部500は、プログラムとしてリレー位置算出プログラム510を記憶しているとともに、データとして、ゲートウェイデータ521と、センサデータ522と、リレー位置候補データ523と、最大転送回数テーブル524と、最大転送回数データ525と、通信経路候補データ526と、経路組データ527と、準最適解データ528とを記憶している。
【0066】
[処理の流れ]
図18は、処理部100が実行するリレー位置算出処理のフローチャートである。同図によれば、先ず、入力部200から、センサS及びゲートウェイGそれぞれの設置位置や最大データ転送率等のデータを入力・設定する(ステップA1)。また、入力部200からの入力指示に従って、リレーRの設置位置候補Pを設定する(ステップA3)。次いで、設置されるセンサSそれぞれについて、ゲートウェイGの設置位置からの距離Dをもとに、最大転送回数を算出・設定する(ステップA5)。その後、厳密解算出処理を開始する(ステップA7)。
【0067】
図19は、厳密解算出処理の流れを説明するフローチャートである。同図によれば、先ず、センサSそれぞれについて、経路条件を満たす全ての通信経路候補を算出する(ステップB1)。次いで、センサSそれぞれについて、算出した通信経路候補による全ての経路組を算出する(ステップB3)。続いて、算出した経路組のうちから、各センサSにつき1つの経路組を選出した全ての通信経路網を算出する(ステップB5)。そして、算出した通信経路網のうちから通信容量条件を満たすものを抽出し(ステップB7)、更に、抽出した通信経路網のうちから、評価が最良のものを選択して厳密解とする(ステップB9)。以上の処理を行うと、厳密解算出処理を終了する。
【0068】
そして、この厳密解算出処理によって、当該処理の開始から所定時間内に厳密解が算出されたならば(ステップA9:YES)、算出された厳密解の通信経路網に含まれる各リレーRに対応する位置候補Pを、リレーRの最適な設置位置として決定する(ステップA11)。
【0069】
一方、厳密解算出処理を開始したが所定時間内に厳密解が算出されないならば(ステップA9:NO)、実行中の厳密解算出処理を終了し(ステップA13)、ヒューリスティクス処理を行って準最適解を算出する(ステップA15)。
【0070】
図20は、ヒューリスティクス処理の流れを説明するフローチャートである。同図によれば、先ず、センサSそれぞれについて、所定数の通信経路候補を算出し(ステップC1)、次いで、これらの通信経路候補を用いて所定数の経路組を算出する(ステップC2)。ここで、所定数の通信経路候補及び経路組は、上述の厳密解算出処理において算出した通信経路候補及び経路組を用いても良い。次いで、算出した経路組を対象として、各センサSについて1つの経路組を選出した組み合わせのうち、通信容量条件を満たし、且つ、評価が最良、すなわちリレーRの総数が最も少ない組み合わせを算出し、準最適解(準最適通信網)とする(ステップC3)。
【0071】
その後、処理部100は、カウント値nを初期値「1」に設定する(ステップC5)。このカウント値nは、準最適解の更新の繰り返し回数をカウントするものである。次いで、1つのセンサSをランダムに選択し(ステップC7)、この選択したセンサSについて、新たな1つの経路組を算出する(ステップC9)。続いて、準最適解の通信経路網(準最適通信網)において、選択したセンサSの経路組を、新たに算出した経路組に置き換えた通信経路網を算出し、暫定解(暫定通信網)とする(ステップC11)。
【0072】
そして、処理部100は、この暫定解(暫定通信網)が通信容量条件を満たすかを判断する。通信容量を満たすならば(ステップC13:YES)、更に、暫定解(暫定通信網)の評価と、準最適解(準最適通信網)の評価とを比較し、暫定解の評価が準最適解の評価に比較して良いならば(ステップC15:YES)、暫定解を準最適解として更新する(ステップC17)。その後、カウント値nが所定の閾値Nに達したかを判断し、達していないならば(ステップC19:NO)、nを「1」加算した値に更新した後(ステップC21)、ステップC7に戻る。一方、カウント値nが閾値Nに達したならば(ステップC19:YES)、ヒューリスティクス処理を終了する。
【0073】
ヒューリスティクス処理を終了すると、算出した準最適解の通信経路網(準最適通信網)における各リレーRに対応する位置候補Pを、リレーRの最適な設置位置として決定する(ステップA17)。以上の処理を行うと、処理部100は、リレー位置算出処理を終了する。
【0074】
[作用・効果]
このように、本実施形態によれば、リレー位置算出装置1では、リレーRの設置位置候補Pを設定し、この設置位置候補Pに設置されると仮定したリレーRを経由してセンサSそれぞれからゲートウェイGに至る通信経路網を算出し、この通信経路網に含まれるリレーRに対応する位置候補PをリレーRの最適な設置位置とする。通信経路網の算出は、先ず、1)全ての通信経路候補を対象として、評価が最良の通信経路網の厳密解を算出する厳密解算出処理を実行する。そして、厳密解の算出に至らずに処理開始からの経過時間が所定時間に到達した場合に、2)所定数の通信経路候補を対象として通信経路網の暫定解を繰り返し求め、評価がより良い準最適解を算出するヒューリスティクス処理が実行される。つまり、厳密解算出処理による厳密解の算出の時間制限を設け、制限時間内に厳密解が算出されない場合にヒューリスティクス処理によって準最適解を算出することで、定められた時間内でより最適と思われるリレーの設置位置の算出が可能となる。また、通信経路網は、1つのセンサSについて互いに同じリレーRを経由しない2つの通信経路を選出して算出される。これにより、例えばリレーRの故障によって1つの通信経路が遮断されたとしても他の通信経路を利用することができるといった、信頼性の高い通信経路網の構築が可能となる。
【0075】
[変形例]
なお、本発明の適用可能な実施形態は上述の実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で適宜変更可能なことは勿論である。
【0076】
(A)評価基準
例えば、上述の実施形態では、通信経路網を評価する際の評価基準を、通信経路網に含まれるリレーRの総数としたが、これを、各通信経路候補の経路長の総和としても良い。この場合、総経路長が短いほど、良い評価とする。更に、評価基準を、リレーRの総数及び総経路長の両方としても良い。この場合、両者の評価値それぞれに重み付けを行い、どちらを優先させるかを変更可能としても良い。
【0077】
(B)既存のワイヤレスセンサネットワークに追加
また、上述の実施形態では、新たにワイヤレスセンサネットワークを構築する場合を説明したが、既に構築されているワイヤレスセンサネットワークに新たなセンサSを追加設置する場合にも適用可能である。この場合、既存のワイヤレスセンサネットワーク(既存通信網)における各センサSの通信経路を変更することなく、追加設置するリレーRの総数が最小となるように、リレーRの追加設置位置を決定する。
【0078】
図21は、このリレーRの追加設置位置を算出する処理(追加リレー位置算出処理)を説明するフローチャートである。同図によれば、処理部100は、先ず、入力部200から、既存通信網に含まれるセンサSやリレーR、ゲートウェイGの位置等のデータを入力・設定する(ステップD1)。また、入力部200から、新たに設置するセンサの位置データ等を入力・設定する(ステップD3)。
【0079】
次いで、新センサについて、既存のリレーRのみによる全ての通信経路候補を算出し(ステップD5)、これらの通信経路候補による全ての経路組を算出する(ステップD7)。そして、算出した経路組それぞれについて、既存通信網に追加した際に通信容量条件を満たすかを判断する。通信容量条件を満たす経路組が有るならば(ステップD9:YES)、新たなリレーRの設置は不要として、追加リレー位置算出処理を終了する。
【0080】
一方、通信容量条件を満たす経路組が無いならば(ステップD9:NO)、処理部100は、入力部200からの入力指示に従って、追加するリレーRの設置位置候補Pを設定する(ステップD11)。次いで、新センサについて、既存リレー及び位置候補Pに設置すると仮定した追加リレーによる全ての通信経路候補を算出し(ステップD13)、これらの通信経路候補による全ての経路組を算出する(ステップD15)。そして、これらの経路組のうちから、所定数の経路組を選択する(ステップD17)。選択した経路組のうちから、既存通信網に追加した際に、通信容量条件を満たし、且つ評価が最良となる経路組を選択し、最適経路組とする(ステップD19)。
【0081】
続いて、処理部100は、カウント値nを初期値「1」に設定する(ステップD21)。そして、新センサについての新たな1つの経路組を、例えばランダム選択し(ステップD23)、選択した経路組を既存通信網に追加して構成される通信経路網(暫定経路網)が通信容量条件を満たすかを判定する。暫定経路網が通信容量条件を満たすならば(ステップD25:YES)、更に、この暫定経路網の評価と、既存通信網に最適経路組を追加して構成される通信経路網の評価とを比較する。そして、暫定経路網の方が評価が良いならば(ステップD27:YES)、選択した経路組を最適経路組として更新する(ステップD29)。
【0082】
次いで、カウント値nが所定の閾値Nに達したかを判断し、カウント値nが閾値Nに達していないならば(ステップD31:NO)、カウント値nを「1」加算した値に更新した後(ステップD33)、ステップD23に戻る。一方、カウント値nが閾値Nに達したならば(ステップD31:YES)、最適経路組の各通信経路候補に含まれる各位置候補Pを、新たに追加するリレーRの設置位置として決定する(ステップD35)。以上の処理を行うと、処理部100は、追加リレー位置算出処理を終了する。
【0083】
(C)監視対象
また、上述の実施形態では、ワイヤレスセンサネットワークの監視対象をトンネルとしたが、橋梁やダム、プラント、船、塔等の他の建造物としても良い。
【図面の簡単な説明】
【0084】
【図1】ワイヤレスセンサネットワークの構成例。
【図2】リレー位置算出装置の内部構成図。
【図3】センサデータのデータ構成例。
【図4】リレーの設置位置候補Pの設定例。
【図5】リレー位置候補データのデータ構成例。
【図6】通信経路候補の一例。
【図7】経路条件(1)の説明図。
【図8】経路条件(2)の説明図。
【図9】最大転送回数テーブルのデータ構成例。
【図10】最大転送回数データのデータ構成例。
【図11】通信経路候補データのデータ構成例。
【図12】経路組データのデータ構成例。
【図13】通信容量条件の説明図。
【図14】通信経路網の評価の説明図。
【図15】準最適解の算出の説明図。
【図16】図15に対する解の一例。
【図17】準最適解データのデータ構成例。
【図18】リレー位置算出処理のフローチャート。
【図19】厳密解算出処理のフローチャート。
【図20】ヒューリスティクス処理のフローチャート。
【図21】追加リレー位置算出処理のフローチャート。
【符号の説明】
【0085】
N ワイヤレスセンサネットワーク
S センサ、R リレー、G ゲートウェイ
1 リレー位置算出装置
100 処理部、200 入力部、300 表示部、400 通信部
500 記憶部
510 リレー位置算出プログラム
521 ゲートウェイデータ、522 センサデータ
523 リレー位置候補データ
524 最大転送回数テーブル、525 最大転送回数データ
526 通信経路候補データ、527 経路組データ
528 準最適解データ
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20