(57)【要約】【課題】ワイヤレスセンサネットワークにおける中継装置の適切な配置位置の決定を支援できるようにすること。【解決手段】配置数別の中継装置５の配置位置の組み合わせである解候補のうちから、各センサノード３から集約装置７まで、ノード間の距離が無線通信可能距離以下であり、且つ、当該ノード間の見通し線が障害範囲１１と重ならないノードを辿るようにして、通信経路を構築できるといった到達可能条件を満たし、且つ、中継装置の配置数が最小となる解候補を探索する。解の探索では、解候補に設定された探索優先度に従って解候補を順次選択して、到達可能条件を満たすかを判定する。解候補の探索優先度は、当該解候補を適用したワイヤレスセンサネットワークに、ノード間の距離が通信可能距離以下であるが、ノード間の見通し線が障害範囲１１に重なる見通し無しノード組に対して近傍条件を満たす近傍ノード組が含まれる場合に、その近傍度合に応じて設定される。【選択図】図１
2019118030.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータに、センサノード、中継装置及び集約装置（以下包括して「ノード」という）のうちのセンサノード及び集約装置の配置位置が与えられたワイヤレスセンサネットワーク（以下「ＷＳＮ」という）における中継装置の配置位置の決定を支援させるためのプログラムであって、
前記ノード間を直接無線通信する場合の直接波の障害となり得る障害範囲を設定する障害範囲設定手段、
配置数別に前記中継装置の配置位置の組み合わせである解候補を設定する解候補設定手段、
前記解候補を適用した前記ＷＳＮについて、各センサノードから集約装置まで、ノード間の距離が所与の無線通信可能距離以下であり、且つ、ノード間の見通し線と前記障害範囲とが重ならないノードを辿るようにして通信経路を構築できる到達可能条件を満たすか否かを判定する判定手段を有し、当該判定手段により満たすと判定され、且つ、前記中継装置の配置数が最小となる前記解候補を探索する探索手段、
として前記コンピュータを機能させたプログラム。
【請求項２】
前記探索手段は、前記解候補に設定された所与の探索優先度に従って前記判定手段が前記解候補を順次判定していく探索の過程で、ノード間の見通し線と前記障害範囲とが重なる見通し無しノード組が判明した場合に、当該見通し無しノード組の２つのノードの配置位置と、前記探索優先度の設定対象の解候補（以下「設定対象解候補」という）を適用した前記ＷＳＮに含まれるノードの配置位置とに基づいて、当該設定対象解候補の前記探索優先度を設定する、
請求項１に記載のプログラム。
【請求項３】
前記探索手段は、前記設定対象解候補を適用した前記ＷＳＮが、前記見通し無しノード組の２つのノードの配置位置に対して所定の近傍条件を満たす配置位置となる２つのノードを含む場合に、含まない場合に比べて前記探索優先度を低く設定する、
請求項２に記載のプログラム。
【請求項４】
前記探索手段は、前記見通し無しノード組の２つのノードの配置位置と、前記近傍条件を満たす配置位置となる２つのノードとの近傍度合に基づいて、前記設定対象解候補の前記探索優先度を設定する、
請求項３に記載のプログラム。
【請求項５】
前記探索手段は、前記近傍度合が高いほど、前記探索優先度を低く設定する、
請求項４に記載のプログラム。
【請求項６】
前記探索手段は、
前記配置数の少ない順に、当該配置数の前記解候補の一部について前記判定手段による判定を行う事前探索を行い、
前記事前探索において前記判定手段により前記到達可能条件を満たすと判定された解候補の配置数を配置数の上限とし、当該上限の配置数から降順に、当該配置数の前記解候補について前記判定手段による判定を行う本探索を行う、
請求項１〜５の何れか一項に記載のプログラム。
【請求項７】
前記判定手段は、判定対象の解候補を適用した前記ＷＳＮに係る各ノード間の通信可否を表す隣接行列を用いて、当該解候補が前記到達可能条件を満たす解候補であるか否かを判定する、
請求項１〜６の何れか一項に記載のプログラム。
【請求項８】
センサノード、中継装置及び集約装置（以下包括して「ノード」という）のうちのセンサノード及び集約装置の配置位置が与えられたワイヤレスセンサネットワーク（以下「ＷＳＮ」という）における中継装置の配置位置の決定を支援する配置位置決定支援装置であって、
前記ノード間を直接無線通信する場合の直接波の障害となり得る障害範囲を設定する障害範囲設定手段と、
配置数別に前記中継装置の配置位置の組み合わせである解候補を設定する解候補設定手段と、
前記解候補を適用した前記ＷＳＮについて、各センサノードから集約装置まで、ノード間の距離が所与の無線通信可能距離以下であり、且つ、ノード間の見通し線と前記障害範囲とが重ならないノードを辿るようにして通信経路を構築できる到達可能条件を満たすか否かを判定する判定手段を有し、当該判定手段により満たすと判定され、且つ、前記中継装置の配置数が最小となる前記解候補を探索する探索手段と、
を備えた配置位置決定支援装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ワイヤレスセンサネットワークにおける中継装置の配置位置の決定を支援する配置位置決定支援装置等に関する。
【背景技術】
【０００２】
トンネル等の監視対象物に分散配置した多数のセンサノードを有するワイヤレスセンサネットワークが知られている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１３−１０９４３１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ワイヤレスセンサネットワークにおいては、中継装置を利用することでより長距離の伝送が可能となる。但し、中継装置の配置位置はセンサノードや集約装置の後に設計されるのが通常である。すなわち、ワイヤレスセンサネットワークの構築の際には、センサノードの配置位置は監視すべき部材や監視すべき位置によって決定され、また、集約装置の配置位置も電源や外部装置との通信回線の敷設箇所等によって決定される。その上で、中継装置の配置位置を決定することになる。中継装置の配置位置は様々な位置が考えられるが、全てのセンサノードから集約装置へ至る通信経路が構築されるように中継装置を配置する必要がある。また、通常、コストやメンテナンスの観点から、中継装置の配置数は少ないほうが望ましい。
【０００５】
ところが、例えば鉄道施設を監視するためのワイヤレスセンサネットワークを設計する場合といった具体的な設計をする段階においては様々な制約が生じ得た。例えば、鉄道沿線には、樹木や建造物のほか、軌道を走行する列車といった、無線通信に影響を与える障害物が多数存在する。また、橋りょうやトンネル等を監視するためのワイヤレスセンサネットワークの設計においては、外形の凹凸形状や各種の構造部材によって無線通信の見通しが確保し難く無線通信に影響が生じ得る場所が存在する。また、中継装置の配置が不可能或いは困難な場所も多数存在する。しかしながら、従来の中継装置の配置位置の決定手法では、このような個別具体的な設置位置の環境は考慮されていなかった。鉄道施設の例を挙げたが、鉄道施設以外の施設（例えば発電所や化学プラントなど）にワイヤレスセンサネットワークを構築する場合も同様の問題があった。
【０００６】
本発明は、上記事情に鑑みてなされたものであり、その目的とするところは、ワイヤレスセンサネットワークにおける中継装置の適切な配置位置の決定を支援できるようにすること、である。
【課題を解決するための手段】
【０００７】
上記課題を解決するための第１の発明は、
コンピュータに、センサノード、中継装置及び集約装置（以下包括して「ノード」という）のうちのセンサノード及び集約装置の配置位置が与えられたワイヤレスセンサネットワーク（以下「ＷＳＮ」という）における中継装置の配置位置の決定を支援させるためのプログラムであって、
前記ノード間を直接無線通信する場合の直接波の障害となり得る障害範囲を設定する障害範囲設定手段（例えば、図１０の初期設定部２０２）、
配置数別に前記中継装置の配置位置の組み合わせである解候補を設定する解候補設定手段（例えば、図１０の解候補設定部２０４）、
前記解候補を適用した前記ＷＳＮについて、各センサノードから集約装置まで、ノード間の距離が所与の無線通信可能距離以下であり、且つ、ノード間の見通し線と前記障害範囲とが重ならないノードを辿るようにして通信経路を構築できる到達可能条件を満たすか否かを判定する判定手段（例えば、図１０の条件判定部２０８）を有し、当該判定手段により満たすと判定され、且つ、前記中継装置の配置数が最小となる前記解候補を探索する探索手段（例えば、図１０の探索部２０６）、
として前記コンピュータを機能させたプログラム（例えば、図１０の配置位置決定支援プログラム３０２）である。
【０００８】
また、他の発明として、
センサノード、中継装置及び集約装置（以下包括して「ノード」という）のうちのセンサノード及び集約装置の配置位置が与えられたワイヤレスセンサネットワーク（以下「ＷＳＮ」という）における中継装置の配置位置の決定を支援する配置位置決定支援装置であって、
前記ノード間を直接無線通信する場合の直接波の障害となり得る障害範囲を設定する障害範囲設定手段と、
配置数別に前記中継装置の配置位置の組み合わせである解候補を設定する解候補設定手段と、
前記解候補を適用した前記ＷＳＮについて、各センサノードから集約装置まで、ノード間の距離が所与の無線通信可能距離以下であり、且つ、ノード間の見通し線と前記障害範囲とが重ならないノードを辿るようにして通信経路を構築できる到達可能条件を満たすか否かを判定する判定手段を有し、当該判定手段により満たすと判定され、且つ、前記中継装置の配置数が最小となる前記解候補を探索する探索手段と、
を備えた配置位置決定支援装置（例えば、図１０の配置位置決定支援装置１０００）を構成しても良い。
【０００９】
第１の発明等によれば、無線通信に影響を与える障害範囲を考慮した、ワイヤレスセンサネットワークにおける中継装置の適切な配置位置の決定を支援することができる。すなわち、配置数別の中継装置の配置位置の組み合わせである解候補のうちから、ノード間の距離が通信可能距離以下であり、且つ、ノード間の見通し線が障害範囲に重ならないノードを辿るようにして、各センサノードから集約装置に至る通信経路を構築でき、且つ、中継装置の配置数が最小となる解候補を探索することができる。また、解候補の設定の際に、例えば、中継装置の配置が不可能或いは困難な場所を除く位置を、中継装置の配置位置とすることができる。
【００１０】
第２の発明として、第１の発明のプログラムであって、
前記探索手段は、前記解候補に設定された所与の探索優先度に従って前記判定手段が前記解候補を順次判定していく探索の過程で、ノード間の見通し線と前記障害範囲とが重なる見通し無しノード組が判明した場合に、当該見通し無しノード組の２つのノードの配置位置と、前記探索優先度の設定対象の候補解（以下「設定対象解候補」という）を適用した前記ＷＳＮに含まれるノードの配置位置とに基づいて、当該設定対象解候補の前記探索優先度を設定する、
プログラムを構成してもよい。
【００１１】
第２の発明によれば、解候補に設定された探索優先度に従って、解候補が到達可能条件を満たすかを順次判定することで、効率的な解の探索を実現することができる。解候補の探索優先度は、ノード間の見通し線が障害範囲と重なる見通し無しノード組の２つの配置位置と、当該解候補を適用したＷＳＮに含まれるノードの配置位置と、に基づいて設定することができる。
【００１２】
第３の発明として、第２の発明のプログラムであって、
前記探索手段は、前記設定対象候補解を適用した前記ＷＳＮが、前記見通し無しノード組の２つのノードの配置位置に対して所定の近傍条件を満たす配置位置となる２つのノードを含む場合に、含まない場合に比べて前記探索優先度を低く設定する、
プログラムを構成しても良い。
【００１３】
第３の発明によれば、設定対象解候補を適用したＷＳＮが、見通し無しノード組の２つのノードの配置位置に対して近傍条件を満たす配置位置となる２つのノードを含む場合には、当該設定解候補の探索優先度を低くすることで、効率的な解の探索が可能となる。これは、近傍条件を満たす配置位置となる２つのノードは、見通し無しノード組と同様に見通し線が障害範囲に重なる可能性が高く、その２つのノード間は通信不可能となる可能性が高いためである。
【００１４】
第４の発明として、第３の発明のプログラムであって、
前記探索手段は、前記見通し無しノード組の２つのノードの配置位置と、前記近傍条件を満たす配置位置となる２つのノードとの近傍度合に基づいて、前記設定対象解候補の前記探索優先度を設定する、
プログラムを構成しても良い。
【００１５】
第４の発明によれば、設定対象解候補の探索優先度を、見通し無しノード組の２つのノードの配置位置と、近傍条件を満たす配置位置となる２つのノードとの近傍度合に基づいて設定することができる。
【００１６】
第５の発明として、第４の発明のプログラムであって、
前記探索手段は、前記近傍度合が高いほど、前記探索優先度を低く設定する、
プログラムを構成しても良い。
【００１７】
第５の発明によれば、近傍度合が高いほど探索優先度を低く設定することで、より効率的な解の探索が可能となる。これは、見通し無しノード組の２つのノードの配置位置に近いほど、近傍条件を満たす配置位置となる２つのノードについても、そのノード間の見通し線が障害範囲と重なる可能性が高いためである。
【００１８】
第６の発明として、第１〜第５の何れかの発明のプログラムであって、
前記探索手段は、
前記配置数の少ない順に、当該配置数の前記解候補の一部について前記判定手段による判定を行う事前探索を行い、
前記事前探索において前記判定手段により前記到達可能条件を満たすと判定された解候補の配置数を配置数の上限とし、当該上限の配置数から降順に、当該配置数の前記解候補について前記判定手段による判定を行う本探索を行う、
プログラムを構成しても良い。
【００１９】
第６の発明によれば、事前探索によって到達可能条件を満たすと判定した解候補の配置数を中継装置の配置数の上限とし、この上限の配置数から降順に、当該配置数の解候補について到達可能条件を満たすかを判定する本探索を行うことで、より効率的な解の探索を実現することができる。これは、配置数が最小となる解を探索するため、ある解候補が到達可能条件を満たす場合、その解候補の配置数より大きい解候補については判定する必要が無いからである。特に、解候補が膨大である場合に演算量の省略化を簡単に実現することができ、効果的である。
【００２０】
第７の発明として、第１〜第６の何れかの発明のプログラムであって、
前記判定手段は、判定対象の解候補を適用した前記ＷＳＮに係る各ノード間の通信可否を表す隣接行列を用いて、当該解候補が前記到達可能条件を満たす解候補であるか否かを判定する、
プログラムを構成しても良い。
【００２１】
第７の発明によれば、解候補を適用したＷＳＮに係る各ノード間の通信可否を表す隣接行列を用いて、到達可能条件を満たすかを判定することができる。例えば、隣接行列に対する行列演算によって、ノード間の通信経路を表す到達可能性行列を生成することができ、この到達可能性行列から、各センサノードから集約装置までの通信経路を構築できるかを判定することができる。
【図面の簡単な説明】
【００２２】
【図１】ワイヤレスセンサネットワークの配置構成を俯瞰的に示した概要図。
【図２】解候補リストの一例。
【図３】隣接行列の説明図。
【図４】ノード間の通信可否の説明図。
【図５】ノード間の見通し線と障害範囲との重なり判定の説明図。
【図６】到達可能性行列の生成の説明図。
【図７】事前探索の説明図。
【図８】見通し無しノード組及び近傍ノード組の説明図。
【図９】探索優先度の設定の説明図。
【図１０】配置位置決定支援装置の機能構成図。
【図１１】探索過程データの一例。
【図１２】探索結果データの一例。
【図１３】見通し無しノード組データの一例。
【図１４】配置位置決定支援処理のフローチャート。
【図１５】事前探索処理のフローチャート。
【図１６】判定処理のフローチャート。
【図１７】探索優先度設定処理のフローチャート。
【発明を実施するための形態】
【００２３】
以下、図面を参照して本発明の好適な実施形態について説明する。なお、以下に説明する実施形態によって本発明が限定されるものではなく、本発明を適用可能な形態が以下の実施形態に限定されるものでもない。また、図面の記載において、同一要素には同一符号を付す。
【００２４】
［原理］
本実施形態は、ワイヤレスセンサネットワークにおける中継装置の配置位置の決定を支援するものである。
【００２５】
（Ａ）ワイヤレスセンサネットワーク
図１は、本実施形態のワイヤレスセンサネットワーク（以下、適宜「ＷＳＮ」という）１の配置構成を俯瞰的に示した概要図である。本実施形態のワイヤレスセンサネットワーク１は、鉄道施設の監視用であり、図１に示すように、監視対象物の各所に配置された多数のセンサノード３と、センサノード３の計測データを中継する中継装置５と、各センサノード３の計測データを集約する集約装置７と、を有して構成される。監視対象物は、トンネルや橋梁、高架線、地盤、路盤、線路といった鉄道施設とすることができる。
【００２６】
センサノード３は、所与のセンシングタイミングでセンシング動作（計測動作）を行い、得られた計測データは、他のセンサノード３や中継装置５を経由したマルチホップ無線通信によって集約装置７へ転送される。集約装置７に集約された各センサノードの計測データは、公衆網或いは専用回線である所与の通信回線を介して所与の外部装置へ送信される。
【００２７】
また、ワイヤレスセンサネットワーク１の監視対象範囲には、無線通信に影響を与える障害範囲１１、及び、センサノード３、中継装置５、及び、集約装置７（以下、包括して「ノード」という）を配置できない配置不可範囲１３が存在する。障害範囲１１は、ノード間を直接無線通信する場合の直接波が通過する際の障害となり得る障害物の存在範囲である。配置不可範囲１３は、長期間の安定した設置状態の維持が困難な場所や、急斜面や高所といった、作業員の安全性の観点から設置・保守作業が困難な場所等である。
【００２８】
本実施形態では、このような構成のワイヤレスセンサネットワーク１に対して、センサノード３、及び、集約装置７の配置位置は予め与えられるとして、無線通信に影響を与える障害範囲１１を考慮しつつ、適切な中継装置５の配置位置の決定を支援する。具体的には、「全てのセンサノード３から集約装置７に至る通信経路が構築できる」ことである到達可能条件を満たし、且つ、中継装置５の配置数が最小となるような、中継装置５の配置数、及び、配置位置を算出する。
【００２９】
なお、本実施形態では、ワイヤレスセンサネットワーク１の監視対象範囲を二次元平面とみなし、各ノードの配置位置は二次元座標値（ｘ，ｙ）で表現されるものとする。そして、各ノードの配置位置は、Ｘ，Ｙ座標値それぞれを所定間隔Δｘ，Δｙ毎の値に定めた離散的な配置可能位置から選ばれるものとする。また、各ノードは、障害範囲１１及び配置不可範囲１３を除く範囲に配置されるものとする。障害範囲１１及び配置不可範囲１３は、各辺がＸ，Ｙ軸に平行な長方形状の範囲とし、その範囲は長方形状の４つの頂点の座標値（ｘ，ｙ）によって表現されるものとする。
【００３０】
（Ｂ）解候補
先ず、図２に示すように、中継装置５の配置位置の組み合わせである解候補を列挙する。図２は、中継装置５の配置数別に、取り得る中継装置５の配置位置の組み合わせを解候補として列挙した解候補リスト３２０を示している。とり得る中継装置５の配置位置は、ワイヤレスセンサネットワーク１の監視対象範囲のうち、センサノード３の配置位置、集約装置７の配置位置、障害範囲１１、及び、配置不可範囲１３を除く位置とする。そして、中継装置５の配置数毎に、当該配置数だけの取り得る配置位置の全ての組み合わせを生成することで、解候補を生成する。
【００３１】
（Ｃ）到達可能条件の判定
ある１つの解候補について到達可能条件を満たすかの判定は、次のように行う。先ず、解候補である各配置位置に中継装置５を配置したとして、当該解候補を適用したワイヤレスセンサネットワーク１を生成し、このワイヤレスセンサネットワーク１における各ノード間の通信可否を表す隣接行列を生成する。
【００３２】
図３は、隣接行列の一例である。図３（ａ）に示すように、ノード数ｎのワイヤレスセンサネットワーク１についての隣接行列は、ｎ行ｎ列の正方行列となり、ｉ行ｊ列の成分ｒｉｊは、ノードｉ，ｊの間の無線通信の可否（可能（「１」）／不可能（「０」））を表す。つまり、隣接行列は２値行列である。図３（ｂ）は、３つのノード９−１〜９−３でなるワイヤレスセンサネットワーク１の例を示している。ノード９−１，９−２間、及び、ノード９−２，９−３間の無線通信は可能（「１」）であるが、ノード９−１，９−３間の無線通信は不可能（「０」）である。本実施形態では、ノード間の無線通信は送信側・受信側を区別しないため、隣接行列は対称行列となる。また、隣接行列の対角成分は、全て通信不可能（「０」）とする。
【００３３】
ノード間の無線通信の可否は、無線通信可能距離、及び、見通しによって決まる。すなわち、ノード間の距離が無線通信可能距離以下であり、且つ、ノード間の見通し線が障害範囲１１と重ならないならば、当該ノード間の無線通信は可能とし、それ以外ならば、無線通信は不可能とする。
【００３４】
例えば、図４は、３つのノード９−１〜９−３でなるワイヤレスセンサネットワーク１の例である。ノード９−１，９−２間、ノード９−２，９−３間、及び、ノード９−１，９−３間それぞれの距離は、全て無線通信可能距離以下である。
【００３５】
そして、図４（ａ）に示すように、ノード９−１，９−２間、ノード９−２，９−３間、及び、ノード９−１，９−３間の全ての見通し線が障害範囲１１に重ならない場合、ノード９−１，９−２間、ノード９−２，９−３間、及び、ノード９−１，９−３間の全てにおいて、無線通信は可能である。従って、隣接行列は、対角成分を除く他の全ての成分が「１（可能）」となる。
【００３６】
一方、図４（ｂ）に示すように、ノード９−２，９−３間、及び、ノード９−１，９−３間それぞれの見通し線は障害範囲１１と重ならないが、ノード９−１，９−２間の見通し線が障害範囲１１と重なる場合には、ノード９−２，９−３間、及び、ノード９−１，９−３間それぞれの無線通信は可能であるが、ノード９−１，９−２間の無線通信は不可能となる。従って、この場合の隣接行列は、図４（ａ）の場合の隣接行列に対して、ノード９−１，９−２間に相当する成分を「０（不可能）」に変更したものとなる。
【００３７】
なお、ノード間の見通し線と障害範囲１１とが重なるかの判定は、例えば、図５に示すように、ノード間の見通し線に該当する線分Ｌ１と、障害範囲１１を表す長方形状の４つの辺それぞれに該当する線分Ｌ２との交差判定によって行うことができる。すなわち、線分Ｌ１の両端の位置座標を、それぞれ、Ｐ１（ｘ１，ｙ１），Ｐ２（ｘ２，ｙ２）とし、線分Ｌ２の両端の位置座標を、それぞれ、Ｐ３（ｘ３，ｙ３），Ｐ４（ｘ４，ｙ４）、とすると、次式（１）が成立する場合、線分Ｌ１，Ｌ２は交差する。
ｔｃ×ｔｄ＜０    ・・・式（１）
ｔｃ＝（ｘ１−ｘ２）×（ｙ３−ｙ１）＋（ｙ１−ｙ２）×（ｘ１−ｘ３）
ｔｄ＝（ｘ１−ｘ２）×（ｙ４−ｙ１）＋（ｙ１−ｙ２）×（ｘ１−ｘ４）
【００３８】
そして、ノード間の見通し線に該当する線分Ｌ１が、障害範囲１１の４つの辺のうちの少なくとも一辺に該当する線分Ｌ２と交差するならば、当該ノード間の見通し線は、当該障害範囲１１と重なると判定する。
【００３９】
このような解候補に対応する隣接行列を用いて、当該解候補が到達可能条件を満たすかを判定する。具体的には、図６に示すように、ある解候補に対応する隣接行列から到達可能性行列を生成する。すなわち、図６に示すように、隣接行列Ａに単位行列Ｉを加算した行列「Ａ＋Ｉ」を生成する。これは、隣接行列Ａの対角成分を全て「１」に変更する操作に相当する。次いで、この行列「Ａ＋Ｉ」を順次自乗して、次式（２）が成立するような行列「（Ａ＋Ｉ）ｋ＋１」を、到達可能性行列とする。但し、ｋは自然数である。
（Ａ＋Ｉ）ｋ−１≠（Ａ＋Ｉ）ｋ＝（Ａ＋Ｉ）ｋ＋１  ・・式（２）
なお、このときの隣接行列に対する行列演算は、ブール代数演算によって行うこととする。従って、生成される到達可能性行列も、各成分が二値（１，０）の２値行列となる。
【００４０】
到達可能性行列は、隣接行列と同じくｎ行ｎ列の正方行列であり、ｉ行ｊ列の成分ｒｉｊは、ノードｉ，ｊの間の通信経路の有無（有り（「１」）／無し（０））を表す。この到達可能性行列によって、センサノード３から集約装置７への通信経路の有無を判断することができる。例えば、センサノード３に対応するノードｉから、集約装置７に対応するノードｊに至る通信経路は、到達可能性行列のｉ行ｊ列の成分ｒｉｊ（到達可能性行列は対称行列であるので、成分ｒｊｉでも良い）が「１」ならば有り、「０」ならば無し、である。そして、全てのセンサノード３について通信経路が有るならば、当該解候補は、到達可能条件を満たすと判定することができる。
【００４１】
（Ｄ）効率的な解の探索
ところで、列挙される解候補は非常に多い。より適切な中継装置５の配置位置を求めるには、その配置可能な位置の間隔Δｘ，Δｙを短く定めることが望ましいが、そうすると、ワイヤレスセンサネットワーク１の監視対象範囲は広大であるため、監視対象範囲におけるこれらの配置可能な位置が増加し、その結果、これらの組み合わせとなる解候補の数は膨大なものとなる。そこで、本実施形態では、先ず、解候補の探索範囲を絞り込むための事前探索を行い、次いで本探索を行うといった二段階の探索によって、演算量を低減させた効率的な解の探索を実現する。
【００４２】
（Ｅ）事前探索
事前探索では、探索対象とする中継装置５の配置数の上限（探索上限配置数）を設定することで、探索範囲を設定する。
【００４３】
図７は、探索範囲の設定を説明する図である。事前探索では、図７に示すように、配置数が少ない順に当該配置数の解候補の一部について到達可能条件を満たすかの判定を行うことで、探索範囲を設定する。すなわち、全ての解候補を、中継装置５の配置数別のグループに分類する。そして、配置数が小さいグループから順に対象グループとして、当該グループ内の総数より小さい所定数（Ｎ個）の解候補を選択し、それぞれについて到達可能条件を満たすかを判定する。その結果、選択したＮ個全ての解候補が到達可能条件を満たさないならば、配置数が「１」だけ大きいグループを次の対象グループとして、同様に、解候補の選択、及び、到達可能条件を満たすかの判定を行う。一方、１つでも到達可能条件を満たす解候補があるならば、その対象グループの配置数ｉを探索上限配置数として、この探索上限配置数ｉ以下の配置数の解候補を、本探索における探索範囲とする。
【００４４】
これは、本実施形態では、中継装置の配置数が最小となるような解を求めるため、配置数ｉの解候補が到達可能条件を満たすことが判明した時点で、配置数がそれより多い解候補は、最適解となり得ないために探索対象から外すことができるからである。また、配置数がそれより少ない未判定の解候補の中に到達可能条件を満たす解候補が含まれる可能性が有るため、ということもできる。
【００４５】
（Ｆ）本探索
本探索では、事前探索によって設定した探索上限配置数ｉ以下の解候補を対象として、配置数が最小であり、且つ、到達可能条件を満たす解候補を探索する。具体的には、探索上限配置数ｉから降順に、当該配置数の解候補について、到達可能条件を満たすかの判定を行う。ここで、探索上限配置数ｉの解候補については、事前探索によって少なくとも１つの解候補が到達可能条件を満たすことが判定されているため、配置数「ｉ−１」から降順に、当該配置数の解候補であって事前探索において到達可能施条件の判定がなされていない解候補を順次選択して、到達可能条件を満たすかを判定する。探索の結果、探索上限配置数ｉより小さい解候補の全てが到達可能条件を満たさないならば、探索上限配置数ｉが最小の配置数となり、事前探索において到達可能条件を満たすと判定した当該探索上限配置数ｉの解候補を、最適解の１つとすることができる。
【００４６】
（Ｇ）探索優先度の設定
また、本探索では、探索対象の各解候補に探索優先度を設定し、この探索優先度に従って解候補を順次選択するようにする。探索優先度は、障害範囲１１によるノード間の見通しの有無の可能性に基づいて設定する。
【００４７】
図８において、２つのノード９−ａ，９−ｂは、ノード間の距離は無線通信可能距離以下であるが、見通し線が障害範囲１１に重なる、つまり、無線通信は不可能な組み合わせである。このような２つのノードの組み合わせを、見通し無しノード組と呼ぶ。そして、この見通し無しノード組の２つのノードの配置位置に対して、所定の近傍条件を満たす配置位置となる２つのノードの組み合わせを、近似ノード組と呼ぶ。近傍条件とは、見通し無しノード組の２つのノードそれぞれの配置位置に一致或いは近いことであり、具体的には、２つのノードそれぞれとの配置位置間の距離の合計が、所定の閾値距離以下であることである。
【００４８】
図８では、見通し無しノード組である２つのノード９−ａ，９−ｂそれぞれの配置位置に近いノードとして、ノード９−ｃ，９−ｄがある。ノード９−ａ，９−ｃの間の距離ＷＡＣと、ノード９−ｂ，９−ｄの間の距離ＷＢＤとの合計距離が、所定の閾値以下であるならば、ノード９−ｃ，９−ｄの組み合わせは、見通し無しノード組であるノード９−ａ，９−ｃに対して近傍条件を満たし、これに対応する近傍ノード組となる。
【００４９】
そして、ある解候補を適用したワイヤレスセンサネットワーク１における見通し無しノード組に対する近傍ノード組が、他の解候補を適用したワイヤレスセンサネットワーク１に含まれる場合、当該他の解候補の探索優先度を相対的に低くするように設定する。これは、障害範囲１１は広さをもった範囲であるため、ある２つのノード間の見通し線が障害範囲１１に重なる場合、その近傍の他の２つのノードの組み合わせについても、同様に、ノード間の見通し線がその障害範囲１１に重なる可能性が高いからである。
【００５０】
また、見通し無しノード組の２つのノードと、近傍ノード組の２つのノードとの対応するノード同士の配置位置間の合計距離は、その近傍度合を表す。この合計距離が短いほど、近傍ノード組の２つのノード間の見通し線が障害範囲１１に重なる可能性が高いため、探索優先度を低くするように設定する。本実施形態では、近傍度合である合計距離を、探索優先度として設定する。従って、本探索では、探索対象として、先ず、探索優先度が未設定の解候補が最優先に選択され、その後に、探索優先度が大きい、つまり、合計距離が大きい解候補から順に選択されることになる。
【００５１】
図９は、探索優先度の設定の一例である。図９において、解候補αを適用したワイヤレスセンサネットワーク１に含まれるノード９−ａ，９−ｂの組み合わせは、見通し無しノード組である。また、探索優先度の設定対象解候補である解候補βを適用したワイヤレスセンサネットワーク１に含まれるノード９−ｃ，９−ｄの組み合わせは、この見通し無しノード組に対応する近似ノード組である。この場合、ノード９−ａ，９−ｃの間の距離ＷＡＣと、ノード９−ｂ，９−ｄの間の距離ＷＢＤとの合計距離を、設定対象解候補である解候補βの探索優先度として設定する。なお、解候補βに探索優先度が既に設定されている場合、小さい方の値とする。
【００５２】
［機能構成］
図１０は、配置位置決定支援装置１０００の機能構成の一例である。配置位置決定支援装置１０００は、所与のワイヤレスセンサネットワークにおける中継装置の配置位置の決定を支援する装置であり、図１０によれば、操作部１０２と、表示部１０４と、音出力部１０６と、通信部１０８と、処理部２００と、記憶部３００とを備えて構成され、一種のコンピュータとして実現される。
【００５３】
操作部１０２は、例えばキーボードやマウス、タッチパネル、各種スイッチ等の入力装置で実現され、なされた操作入力に応じた操作信号を処理部２００に出力する。表示部１０４は、例えば液晶ディスプレイやタッチパネル等の表示装置で実現され、処理部２００からの表示信号に基づく各種表示を行う。音出力部１０６は、例えばスピーカ等の音声出力装置で実現され、処理部２００からの音信号に基づく各種音声出力を行う。通信部１０８は、例えば無線通信モジュールやルータ、モデム、有線用の通信ケーブルのジャックや制御回路等で実現される通信装置であり、外部装置とのデータ通信を行う。
【００５４】
処理部２００は、ＣＰＵ（Central Processing Unit）やＦＰＧＡ（Field Programmable Gate Array）等の演算装置や演算回路で実現されるプロセッサーであり、記憶部３００に記憶されたプログラムやデータ、操作部１０２や通信部１０８による入力データ等に基づいて、配置位置決定支援装置１０００の全体制御を行う。また、処理部２００は、機能的な処理ブロックとして、初期設定部２０２と、解候補設定部２０４と、探索部２０６と、を有する。処理部２００が有するこれらの各機能部は、処理部２００がプログラムを実行することでソフトウェア的に実現することも、専用の演算回路で実現することも可能である。本実施形態では、前者のソフトウェア的に実現することとして説明する。
【００５５】
初期設定部２０２は、センサノード３、及び、集約装置７の配置位置を含む、対象とするワイヤレスセンサネットワーク１の構成や、ワイヤレスセンサネットワーク１の監視対象範囲におけるノードの配置不可範囲１３、ノード間を直接通信する場合の直接波の障害となり得る障害範囲１１等の初期設定を行う。
【００５６】
設定したワイヤレスセンサネットワーク１の構成に関しては、ＷＳＮ設定データ３０４として、障害範囲１１に関しては、障害範囲設定データ３１２として、配置不可範囲１３に関しては、配置不可範囲設定データ３１４として、それぞれ記憶される。
【００５７】
ＷＳＮ設定データ３０４は、各センサノード３の配置位置を含むセンサノード設定データ３０６と、各集約装置７の配置位置を含む集約装置設定データ３０８と、各ノードの無線通信可能距離を含む通信性能データ３１０と、を含む。無線通信可能距離は、全てのノードについて同一であるとする。
【００５８】
解候補設定部２０４は、配置数別に、中継装置５の配置位置の組み合わせである解候補を設定する。すなわち、ワイヤレスセンサネットワーク１の監視対象範囲のうち、センサノード３の配置位置、集約装置７の配置位置、障害範囲１１、及び、配置不可範囲１３を除く、中継装置５を配置し得る位置を抽出し、配置数別に、これらの各位置を組み合わせて解候補とすることで、解候補リスト３２０を生成する。
【００５９】
探索部２０６は、解候補設定部２０４に設定された解候補のうちから、到達可能条件を満たし、且つ、中継装置５の配置数が最小となる解候補を探索する。すなわち、中継装置５の配置数が少ない順に、当該配置数の解候補の一部について、到達可能条件を満たすかの事前探索を行い、事前探索において到達可能条件を満たすと判定した解候補の配置数を配置数の上限とし、当該上限の配置数から降順に、当該配置数の解候補について、到達可能条件を満たすかの判定を行う本探索を行う。探索部２０６による探索の過程は探索過程データ３２６として、探索の結果は探索結果データ３２８として、それぞれ記憶される。
【００６０】
図１１は、探索過程データ３２６の一例である。図１１によれば、探索過程データ３２６は、解候補設定部２０４に設定されたすべての解候補それぞれについて、配置数３２６ａと、解候補Ｎｏ．３２６ｂと、探索優先度３２６ｃと、判定済みフラグ３２６ｄと、判定結果３２６ｅと、不可能フラグ３２６ｆと、を対応付けて格納している。探索優先度３２６ｃは、優先度設定部２１０によって設定された値であり、未設定を含む。判定済みフラグ３２６ｄは、条件判定部２０８による到達可能条件を満たすかの判定がなされたか否かを示すフラグである。判定結果３２６ｅは、条件判定部２０８による到達可能条件を満たすか否かの判定結果である。不可能フラグ３２６ｆは、不可能解であるか否かを示すフラグである。到達可能条件を満たさないと判定された場合や、対応する解候補を適用したワイヤレスセンサネットワークがどのノードとも通信不可能な孤立ノードを含むと判定された場合に、当該解候補は不可能解となり、以降の探索から除外されることになる。
【００６１】
図１２は、探索結果データ３２８の一例である。図１２によれば、探索結果データ３２８は、最小配置数３２８ａと、最適解リスト３２８ｂとを格納する。最適解リスト３２８ｂは、最小配置数３２８ａの解候補であって、到達可能条件を満たす１又は複数の解候補の解候補Ｎｏ．の一覧である。
【００６２】
また、探索部２０６は、解候補が到達可能条件を満たすかを判定する条件判定部２０８と、解候補に探索優先度を設定する優先度設定部２１０とを有する。
【００６３】
条件判定部２０８は、解候補を適用したワイヤレスセンサネットワーク１について、各センサノード３から集約装置７まで、ノード間の距離が無線通信可能距離以下であり、且つ、ノード間の見通し線が障害範囲１１に重ならないノードを辿るようにして通信経路を構築できる到達可能条件を満たすかを判定する。具体的には、ある解候補を適用したワイヤレスセンサネットワーク１について、各ノード間の通信可否を表す隣接行列を生成し、更に、この隣接行列に基づいて到達可能性行列を生成する。そして、この到達可能性行列に基づき、各センサノード３から集約装置７に至る通信経路の有無を判定し、全てのセンサノード３から集約装置７に至る通信経路が有るならば、当該解候補は到達可能条件を満たすと判定する。
【００６４】
また、条件判定部２０８は、解候補についての隣接行列の生成に当たり、各ノード間の通信可否を判断するが、このとき、ノード間の距離は無線通信距離以下であるが、ノード間の見通し線が障害範囲１１と重なる２つのノードの組み合わせである見通し無しノード組を見つけた場合には、当該見通し無しノード組についての見通し無しノード組データ３２２を生成しておく。
【００６５】
図１３は、見通し無しノード組データ３２２の一例である。図１３によれば、見通し無しノード組データ３２２は、ノード組Ｎｏ．３２２ａに対応付けて、当該見通し無しノード組の２つのノードの配置位置３２２ｂと、近傍位置ペアリスト３２４と、を格納している。近傍位置ペアリスト３２４は、当該見通し無しノード組の２つのノードそれぞれの配置位置との距離の合計が所定の閾値距離以下となる２つの配置位置の組み合わせである近傍位置ペアそれぞれについて、ペアＮｏ．３２４ａと、２つの近傍位置３２４ｂ，３２４ｃと、合計距離３２４ｄと、を対応付けて格納している。
【００６６】
優先度設定部２１０は、解候補に探索優先度を設定する。すなわち、条件判定部２０８による解候補が到達可能条件を満たすかを順次判定していく探索の過程で、ノード間の距離は無線通信可能距離以下であるが、ノード間の見通し線が障害範囲１１と重なる見通し無しノード組が判明した場合に、当該見通し無しノード組の２つのノードの配置位置と、探索優先度の設定対象の候補解である設定対象解候補を適用したワイヤレスセンサネットワークに含まれるノードの配置位置とに基づいて、当該設定対象解候補の探索優先度を設定する。
【００６７】
具体的には、見通し無しノード組の２つのノードそれぞれの配置位置との間の距離の合計が所定の閾値距離以下であることを近傍条件とし、設定対象解候補を適用したワイヤレスセンサネットワークが、この近傍条件を満たす近傍ノード組を含む場合に、近傍度合である合計距離を探索優先度として設定対象解候補に設定する。
【００６８】
詳細には、見通し無しノード組データ３２２を参照し、設定対象解候補を適用したワイヤレスセンサネットワークが、ある見通し無しノード組に対応する近傍位置ペアの２つの近傍位置を配置位置とする２つのノードの組み合わせである近傍ノード組を含む場合に、当該近傍位置ペアに対応する合計距離を、探索優先度として設定する。ここで、見通し無しノード組に対する近傍ノード組の近傍条件となる、２つのノードそれぞれの配置位置との距離の合計の閾値は、近傍条件データ３１６として記憶されている。
【００６９】
記憶部３００は、ＲＯＭ（Read Only Memory）やＲＡＭ（Random Access Memory）等のＩＣ（Integrated Circuit）メモリやハードディスク等の記憶装置で実現され、処理部２００が配置位置決定支援装置１０００を統合的に制御するためのプログラムやデータ等を記憶しているとともに、処理部２００の作業領域として用いられ、処理部２００が実行した演算結果や、操作部１０２や通信部１０８からの入力データ等が一時的に格納される。本実施形態では、記憶部３００には、配置位置決定支援プログラム３０２と、ＷＳＮ設定データ３０４と、障害範囲設定データ３１２と、配置不可範囲設定データ３１４と、近傍条件データ３１６と、解候補リスト３２０と、見通し無しノード組データ３２２と、探索過程データ３２６と、探索結果データ３２８と、が記憶される。
【００７０】
［処理の流れ］
図１４は、配置位置決定支援処理の流れを説明するフローチャートである。この処理は、処理部２００が、配置位置決定支援プログラム３０２に従った処理を行うことで実現される。
【００７１】
先ず、初期設定部２０２が、各センサノード３、及び、集約装置７の配置位置を含む、対象となるワイヤレスセンサネットワーク１の構成や、ワイヤレスセンサネットワーク１の監視対象範囲における障害範囲１１や、配置不可範囲１３の設定といった、初期設定を行う（ステップＳ１）。次いで、解候補設定部２０４が、センサノード３や集約装置７の配置位置、障害範囲１１や配置不可範囲１３を除く位置を中継装置５の配置可能な位置として、配置数別に、これらの配置可能な位置の組み合わせを生成することで解候補を設定して、解候補リスト３２０を生成する（ステップＳ３）。このとき、各解候補の探索優先度は、ゼロに初期設定しておく。
【００７２】
続いて、探索部２０６が、事前探索処理（図１５参照）を行う（ステップＳ５）。事前探索処理を終了すると、続いて、本探索を行う。すなわち、探索対象配置数ｉを、事前探索処理において設定した探索上限配置数より「１」小さい値に設定する（ステップＳ７）。また、最小配置数候補を、探索上限配置数に設定する（ステップＳ９）。次いで、探索対象配置数ｉの解候補のうちから、探索優先度に従って未判定の１つの解候補を選択する（ステップＳ１１）。このとき、探索優先度に従うとは、先ずはゼロを最優先とし、以降は、探索優先度が大きい順に選択する。そして、条件判定部２０８が、選択した解候補についての判定処理（図１６参照）を行う（ステップＳ１３）。選択解候補についての判定処理を終了すると、続いて、探索優先度設定処理（図１７参照）を行う（ステップＳ１５）。
【００７３】
探索優先度設定処理を終了すると、続いて、判定処理によって、選択解候補が到達可能条件を満たすと判定されているならば（ステップＳ１７：ＹＥＳ）、最小配置数候補を、探索対象配置数ｉに更新する（ステップＳ２１）。次いで、探索対象配置数ｉが「１」でないならば（ステップＳ２３：ＮＯ）、探索対象配置数ｉを「１」だけ小さい値に変更した後（ステップＳ２５）、ステップＳ１１に戻る。探索対象配置数ｉが「１」ならば（ステップＳ２３：ＹＥＳ）、最小配置数を最小配置数候補とし、当該最小配置数の可能解を最適解とする（ステップＳ２７）。
【００７４】
また、判定処理によって、選択解候補が到達可能条件を満たさないと判定されたならば（ステップＳ１７：ＮＯ）、探索対象配置数ｉの解候補の全てが判定済みかを判断し、未判定の解候補が有るならば（ステップＳ１９：ＮＯ）、ステップＳ１１に戻る。
【００７５】
一方、探索対象配置数ｉの解候補の全てが判定済みならば（ステップＳ１９：ＹＥＳ）、探索対象配置数ｉを判断する。探索対象配置数ｉが「１」でないならば（ステップＳ２３：ＮＯ）、探索対象配置数ｉを「１」だけ小さい値に変更した後（ステップＳ２５）、ステップＳ１１に戻る。探索対象配置数ｉが「１」ならば（ステップＳ２３：ＹＥＳ）、最小配置数を最小配置数候補とし、当該最小配置数の可能解を最適解とする（ステップＳ２７）。ここまでが、本探索となる。
【００７６】
そして、本探索によって決定した最小配置数、及び、最適解を、探索結果として、例えば表示部１０４に表示するといった所定の出力処理を行う（ステップＳ２９）。以上の処理を行うと、配置位置決定支援処理は終了となる。
【００７７】
図１５は、事前探索処理を説明するフローチャートである。事前探索処理では、先ず、全ての解候補について、当該解候補を適用したワイヤレスセンサネットワークに、どのノードともノード間距離が無線通信可能距離を超えて通信不可能となる孤立ノードが含まれるかを判断し、孤立ノードを含むこととなる解候補を不可能解として以降の探索から除外する（ステップＳ３１）。
【００７８】
次いで、配置数ｉを、初期値「１」に設定し（ステップＳ３３）、判定回数ｎを初期値「１」に設定する（ステップＳ３５）。続いて、配置数ｉの解候補のうち、未判定の１つの解候補をランダム選択し（ステップＳ３７）、条件判定部２０８が、選択した解候補についての判定処理（図１６参照）を行う（ステップＳ３９）。判定処理の結果、選択解候補が到達可能条件を満たすと判定されたならば（ステップＳ４１：ＹＥＳ）、配置数ｉを、探索上限配置数に設定する（ステップＳ５１）。
【００７９】
一方、選択解候補が到達可能条件を満たさないと判定されたならば（ステップＳ４１：ＮＯ）、判定回数ｎが所定回数Ｎに達したかを判断する。判定回数ｎが所定回数Ｎに達していないならば（ステップＳ４３：ＮＯ）、判定回数ｎを「１」加算した値に更新した後（ステップＳ４５）、ステップＳ３７に戻る。判定回数ｎが所定回数Ｎに達したならば（ステップＳ４３：ＹＥＳ）、配置数ｉが最大配置数Ｍに達したかを判断する。最大配置数Ｍは、解候補として設定した中継装置５の配置数の最大値である。
【００８０】
配置数ｉが最大配置数Ｍに達していないならば（ステップＳ４７：ＮＯ）、配置数ｉを「１」加算した値に更新した後（ステップＳ４９）、ステップＳ３５に戻る。配置数ｉが最大配置数Ｍに達したならば（ステップＳ４７：ＹＥＳ）、配置数ｉを、探索上限配置数に設定する（ステップＳ５１）。以上の処理を行うと、事前探索処理は終了となる。
【００８１】
図１６は、判定処理を説明するフローチャートである。判定処理では、対象の解候補を適用したワイヤレスセンサネットワークにおける各ノード間の通信可否を、当該ノード間の距離が無線通信可能距離以下であるか否かによって判断して、対象解候補に対応する隣接行列を生成する（ステップＳ６１）。次いで、ノード間の距離が無線通信可能距離以下であるノード間それぞれについて、当該ノード間の見通し線が障害範囲１１と重なるか否かに応じて通信可否を再判断して、隣接行列を更新する（ステップＳ６３）。続いて、この隣接行列に基づいて、到達可能性行列を生成する（ステップＳ６５）。
【００８２】
そして、生成した到達可能性行列に基づき、対象の解候補が到達可能条件を満たすか否かを判定する（ステップＳ６７）。すなわち、センサノード３及び集約装置７の組み合わせに該当する到達可能性行列の成分が「１」であるか否かによって、当該センサノード３から当該集約装置７に至る通信経路の有無を判断し、全てのセンサノード３及び集約装置７の組み合わせについて通信経路が有るならば、対象の解候補は到達可能条件を満たすと判定し、そうでないならば、到達可能条件を満たさないと判定する。以上の処理を行うと、判定処理は終了となる。
【００８３】
図１７は、探索優先度設定処理を説明するフローチャートである。探索優先度設定処理では、選択解候補に見通し無しノード組が含まれる場合に（ステップＳ７１：ＹＥＳ）、これらの見通し無しノード組それぞれを対象としたループＡの繰り返し処理を行う。
【００８４】
ループＡの処理では、先ず、対象見通し無しノード組を含む未判定の解候補について、対象見通し無しノード組の２つのノード間が通不可能であることによって、当該解候補を適用したワイヤレスセンサネットワークに、どのノードとも通信不可能となる孤立ノードが含まれるかを判断し、孤立ノードを含むこととなる解候補を不可能解として以降の探索から除外する（ステップＳ７３）。
【００８５】
次いで、対象見通し無しノード組の２つのノードの配置位置に対して、配置位置の間の合計距離が所定の閾値距離以下である近傍条件を満たす２つの配置位置の組み合わせである近傍位置ペアを算出する（ステップＳ７５）。続いて、未判定の解候補のうち、当該解候補を適用したワイヤレスセンサネットワークに、配置位置が近傍位置ペアである２つのノードの組み合わせである近傍ノード組が含まれる解候補に対して、対象見通し無しノード組と近傍ノード組との近傍度合である合計距離を探索優先度として設定する（ステップＳ７７）。このとき、当該解候補に既に探索優先度が設定されている場合には、今回の探索優先度と設定済みの探索優先度とのうちの小さい方の値に設定する。ループＡの処理はこのように行われる。全ての見通し無しノード組を対象としたループＡの処理を行うと、探索優先度設定処理は終了となる。
【００８６】
［作用効果］
このように、本実施形態によれば、無線通信に影響を与える障害範囲１１を考慮した、ワイヤレスセンサネットワーク１における中継装置５の適切な配置位置の決定を支援することができる。すなわち、配置数別の中継装置５の配置位置の組み合わせである解候補のうちから、各センサノード３から集約装置７に至る通信経路を構築でき、且つ、中継装置５の配置数が最小となる解候補を探索することができる。
【００８７】
また、全ての解候補を対象として、中継装置５の配置数の少ない順に当該配置数の一部の解候補について到達可能条件を満たすかを判定する事前探索を行い、事前探索において到達可能条件を満たした解候補の配置数を探索上限配置数とし、この探索上限配置数以下の配置数の解候補を対象とした本探索を行うことで、より効率的な解の探索を実現することができる。これは、中継装置の配置数が最小となる解を探索するため、ある解候補が到達可能条件を満たす場合、その解候補の配置数より大きい解候補については判定する必要が無いからである。特に、解候補が膨大である場合に効果的である。
【００８８】
また、本探索では、解候補に設定された探索優先度に従って解候補を順次選択して、到達可能条件を満たすかを判定する。ある解候補の探索優先度は、当該解候補を適用したワイヤレスセンサネットワークに、ノード間の距離が通信可能距離以下であるが、ノード間の見通し線が障害範囲１１に重なる見通し無しノード組の２つのノードの配置位置に対して近傍条件を満たす配置位置となる近傍ノード組が含まれる場合に、その近傍度合に応じて設定される。これは、近傍ノード組は、見通し無しノード組と同様に見通し線が障害範囲１１に重なる可能性が高く、その２つのノード間は通信不可能となる可能性が高いためである。
【００８９】
［変形例］
なお、本発明の適用可能な実施形態は上述の実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で適宜変更可能なのは勿論である。
【００９０】
（Ａ）最適解の数
例えば、上述の実施形態では、本探索において（図１４参照）、ある解候補が到達可能条件を満たすと判定した場合、その時点で探索を終了して当該解候補を最適解としたが、複数の最適解を求めるようにしても良い。
【００９１】
（Ｂ）到達可能性行列
また、上述の実施形態では、隣接行列に基づく到達可能性行列の生成において（図６参照）、センサノード３から集約装置７への通信経路が構築できるか否かを判定するため、隣接行列に対する行列演算をブール代数演算によって行うことにしたが、これを、十進数の演算としても良い。この場合、到達可能性行列の成分値は、該当するノード間の通信経路の数となるため、所定数以上の通信経路が構築できることを到達可能条件とすることができる。
【００９２】
また、到達可能性行列の生成の際の行列（Ａ＋Ｉ）に対する階乗数ｋに上限を設けることにしても良い。行列（Ａ＋Ｉ）をｋ乗した行列「（Ａ＋Ｉ）ｋ」における成分値は、該当するノード間の通信経路として、ホップ数がｋ以下の通信経路が構築できるか否かを表すことになる。この場合、到達可能条件として、センサノードから集約装置に至る通信経路として、「ホップ数がｋ以下の通信経路」といった条件を追加することができる。
【００９３】
（Ｃ）監視対象範囲
また、上述の実施形態では、ワイヤレスセンサネットワーク１の監視対象範囲を二次元平面とし、各ノードの配置位置は二次元座標値で表現されることとしたが、監視対象範囲を三次元空間とし、各ノードの配置位置は三次元座標値で表現され、障害範囲１１、及び、配置不可範囲１３は、高さを持つ物体であるとしても良い。
【００９４】
（Ｄ）ワイヤレスセンサネットワーク１による監視対象
上述の実施形態では、ワイヤレスセンサネットワーク１の監視対象を鉄道施設としたが、発電所や化学プラントなどの他の施設などとしてもよいことは勿論である。
【符号の説明】
【００９５】
１…ワイヤレスセンサネットワーク（ＷＳＮ）
３…センサノード、５…中継装置、７…集約装置
１１…障害範囲、１３…配置不可範囲
１０００…配置位置決定支援装置
２００…処理部
２０２…初期設定部、２０４…解候補設定部
２０６…探索部、２０８…条件判定部、２１０…優先度設定部
３００…記憶部
３０２…配置位置決定支援プログラム
３０４…ＷＳＮ設定データ
３１２…障害範囲設定データ、３１４…配置不可範囲設定データ
３１６…近傍条件データ、３２０…解候補リスト
３２２…見通し無しノード組データ
３２６…探索過程データ、３２８…探索結果データ
【図１】
2019118030.tif 000003
【図２】
2019118030.tif 000004
【図３】
2019118030.tif 000005
【図４】
2019118030.tif 000006
【図５】
2019118030.tif 000007
【図６】
2019118030.tif 000008
【図７】
2019118030.tif 000009
【図８】
2019118030.tif 000010
【図９】
2019118030.tif 000011
【図１０】
2019118030.tif 000012
【図１１】
2019118030.tif 000013
【図１２】
2019118030.tif 000014
【図１３】
2019118030.tif 000015
【図１４】
2019118030.tif 000016
【図１５】
2019118030.tif 000017
【図１６】
2019118030.tif 000018
【図１７】
2019118030.tif 000019