"対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び/又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、該バッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアンヒューリスティック法に基づく近似最適解法を用いてセンサネットワークの設計をすることを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。請求項1記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記対象構造物が、鉄道土木構造物であることを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。請求項2記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記総和の最小化を行うためリレーの設置数とその設置場所、各センサと各リレーにおける送信電力レベル、前記センサからのデータを前記ゲートウェイにマルチホップで送信するための伝送経路を同時に設定することを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。請求項3記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記センサと前記ゲートウェイの設置場所と、前記リレー設置候補場所と、各種電力情報と、各種費用情報を入力情報として与え、前記リレーの設置費用と前記バッテリーの消費費用と前記バッテリーの交換作業費用との総和が最小になるような前記リレーの設置場所と、前記データの伝送経路と、前記センサと前記リレーの送信電力レベル、前記無線センサネットワーク1日あたりの費用と、ネットワーク寿命を出力し、これに基づき前記無線センサネットワークを構築することを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。上記WSNの設計においては、伝送遅延や伝送成功率などに関する技術的な検討と共に、設置初期投資費用と運用費用の総和を最小にするための方策が種々検討された。しかしながら、WSNを構築し運用する際に発生する諸費用は互いに密接に関係しており、それらの間には様々なトレードオフ関係が存在する。例えば、リレーを多く設置すると、ネットワーク内の各バッテリーの消費電力量が平準化され、バッテリー交換のための巡回間隔を長くできる傾向にある。つまり、リレー設置の初期投資費用を多く少なくすると、バッテリー交換のための運用費用は少なく多くなる。そのため、初期投資費用と運用費用の検討には多くの時間を要した。さらに、センサやリレーにおける送信電力レベルtransmissionpowerlevel以下、TPLと記すの設定やセンシングデータを送信するためのルート計画も、ネットワーク内の電力消費費用、バッテリー交換費用、リレー設置の初期費用などに大きく関係するはずであるが、これらの要素まで全て含めて、設置費用と運用費用の総和が最小となるようなWSNを系統的に設計できる具体的な方法は開発されていなかった。本発明では、上記状況に鑑みて、WSNの設置運用に要する費用の総和を最小にすることができる、対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法を提供することを目的とする。より具体的には、埋没費用と考えられるセンサとゲートウェイの設置費用を除いた、設置費用リレー設置費用と運用費用バッテリー消費費用、バッテリー交換作業費用の総和の最小化を図るように無線センサネットワークの設計を行うことを目的とする。なお、リレーの設置計画、TPLの設定計画、センシングデータのルート計画は、鉄道構造物以外を対象とするWSNの設計においても主要な課題であり、多くの場合、それらの計画がWSNの効率性経済性に大きく関係する。このため、以下で提案するWSNの設計アルゴリズムは、鉄道構造物に限らず、その他の構造物の状態監視に用いられるWSNにも幅広く適用できる。本発明は、上記目的を達成するために、1対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び/又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、このバッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアンヒューリスティック法Lagrangianheuristicmethodに基づく近似最適解法を用いてセンサネットワークを設計することを特徴とする。2上記1記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記対象構造物が、鉄道土木構造物であることを特徴とする。3上記2記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記総和の最小化を行うため、リレーの設置数とその設置場所、各センサと各リレーにおける送信電力レベル、前記センサからのデータを前記ゲートウェイにマルチホップで送信するための伝送経路を同時に設定することを特徴とする。4上記3記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記センサと前記ゲートウェイの設置場所と、前記リレー設置候補場所と、各種電力情報と、各種費用情報を入力情報として与え、前記リレーの設置費用と前記バッテリーの消費費用と前記バッテリーの交換作業費用との総和が最小になるような前記リレーの設置場所と、前記データの伝送経路と、前記センサと前記リレーの送信電力レベル、ならびに前記無線センサネットワーク1日あたりの費用と、ネットワーク寿命を出力し、これに基づき前記無線センサネットワークを構築することを特徴とする。本発明によれば、次のような効果を奏することができる。1軍事モニタリング、フィールドモニタリング、構造物モニタリングなど活用範囲の広いセンサネットワークを構築運用する際の費用評価が可能となることにより、センサネットワークの導入による効果と費用の関係費用対効果が明らかになる。2総費用が少ないセンサネットワークを設計できることにより、事業者にとっても経費削減を図ることができる。本発明の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法は、対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び/又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、このバッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアンヒューリスティック法Lagrangianheuristicmethodに基づく近似最適解法を用いてセンサネットワークを設計する。本発明は、対象構造物の状態監視のためのWSNの設置及び運用費用評価方法であるが、これは所与の条件の下、設置及び運用費用の総和が最も小さくなるようなWSNを設計し、その設置運用費用に加えてネットワーク寿命をも評価するものである。このような本発明では、設置及び運用費用の総和が最も小さくなるようなWSNを設計するため、リレー設置費用とバッテリー消費費用とバッテリー交換費用の総和を最小とすることを目的とする。そのために、まず、最初に、リレーの設置数とその設置場所、各センサと各リレーにおけるTPLのレベル、センシングデータをゲートウェイにマルチホップで送信するための伝送ルートを同時に計画する問題を設定する。次いで、その問題を数理計画問題に定式化した後、ラグランジアンヒューリスティック法Lagrangianheuristicmethodに基づく、その問題の近似最適解法を用いて問題の解を得る。本明細書では、最後に、本発明の有効性を鉄道土木構造物の状態監視における実例を用いた数値実験により検証する。以下、本発明の実施の形態について詳細に説明する。図1は本発明の評価対象である鉄道土木構造物の状態監視のためのWSNの模式図である。図1において、1は鉄道土木構造物としてのトンネル、2は軌道、3はセンサ、4はゲートウェイ、5は携帯電話網、6は管理局である。ここでは、センサ3が所定間隔でトンネル1の内壁に複数個ずつ配置されている。また、点線は、データの流れを示している。なお、ここでは、リレーが配置されていないものを示す。マルチホップ無線通信により、センサ3からのセンシングデータの収集が行われ、その収集データはゲートウェイ4を介して携帯電話網5を通じて管理局6へと伝送される。センサ3としては、地下鉄においては、バッテリーで駆動される傾斜計センサや変位計センサが配置され、ゲートウェイ4はAC電源で駆動される。このような構成のWSNでトンネルの状態監視が行われる。ここで、上記したように、WSNは複数個のセンサ3と単一のゲートウェイ4を有するが、それらの設置場所は予め決められているものとする。また、リレーを設置できる場所の候補も幾つかあり、これらの場所も予め決められているものとする。さらに、各センサ3と各リレーにおいてはデータを出力する際のTPLを数段階の水準の中の1つに設定でき、各センサ3と各リレーから送信できる範囲と送信のための消費電力量は設定したTPLに依存するものとする。加えて、各センサ3と各リレーの電源はそれぞれに配置されたバッテリーであり、各バッテリーは電力が枯渇したものと次の交換作業までに電力が枯渇するものを交換しなければならないものとする。このような前提のもと、鉄道土木構造物の状態監視を行うためのWSNとして、以下のようなシステムの構築について考える。1各センサ3では単位期間毎に1回データを収集する。2各センサ3で収集したデータは、マルチホップ通信でゲートウェイ4に無線伝送される。3ゲートウェイ4に伝送されたデータは、携帯電話やインターネットなどの一般の通信手段を用いて管理局6の中央の管理サーバに転送される。図2は本発明に係る鉄道土木構造物を対象とするWSNシステムの設置運用にかかる費用の分類を示す図である。この図に示すように、WSNの設置及び運用にはさまざまな費用が必要であり、例えば、バッテリー消費費用、バッテリー交換作業費用、リレー設置費用、ゲートウェイ設置費用、センサ設置費用などが挙げられる。これらの費用を分類すると、バッテリー消費費用、バッテリー交換作業費用は運用費用Aであり、リレー設置費用、ゲートウェイ設置費用、センサ設置費用は、設置費用Bであり、運用費用Aと設置費用Bの総和が全体費用Cである。このように、上記WSNシステムの構築においては、まずセンサ3、ゲートウェイ4、リレーを設置するための設置費用が発生する。しかし、センサ3とゲートウェイ4の設置場所は上記したように予め定められていることから、それらの設置費用は埋没費用sunkcostであると見なすことができる。そこで、本発明においてはシステム構築の設置費用としては残りのリレー設置費用だけを考慮することにする。また、このシステムの運用においては、システム内の各センサと各リレーのバッテリーを保守作業員が現場を巡回して交換する必要がある。つまり、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーを保守作業員が現場を巡回して交換する必要がある。よって、システムの運用段階においてはバッテリー交換のための作業費用が発生する。加えて、システムの運用段階においては、当然のことながら、各バッテリーの電力消費費用についても考慮する必要がある。したがって、このシステムの構築段階においてはリレー設置費用が、そして運用段階においてはバッテリー消費費用とバッテリー交換作業費用が発生することになる。なお、各センサに設けられる無線通信機器では、35Ah、3.6Vのバッテリーを使用しているが、バッテリー寿命は約1年半である。一方、傾斜計は無線通信機器とは異なる2.4Ah、3.6Vのバッテリーを2個使用しており、そのバッテリー寿命は約1年である。変位計は無線通信機器のバッテリーより電源が供給される。変位計ノードの寿命は約1年である。ノード障害は、突発的である一方、バッテリーの枯渇は定期的に発生する。また、ノード復旧よりもバッテリー交換の方が高コストであるので、WSNを長期間運用するためにも、効率的にバッテリーを利用する必要がある。したがって、最適化技術を活用して効率的にWSNを設計する。そこで、本発明の問題の設定としては、運用費用Aバッテリー消費費用、バッテリー交換作業費用と設置費用Bリレー設置費用の総和が最小となるように、リレーの設置数とその設置場所、各センサと各リレーのTPLの水準、各センシングデータの送信経路を決定する。すなわち、リレーをそれらを設置可能な場所の中のどこにいくつ配置するかを決定する問題と、各センサと各リレーでのTPLの水準を決定する問題と、各センサで収集したデータをゲートウェイに送信するためのルートを決定する問題である。これら3つの問題は先に示した3つの費用すべてに関係している。つまり、これら3つの問題は互に密接に関係しており、各問題を個別に解いても総費用の最小化を保証することはできない。そこで本発明では、リレー設置費用とバッテリー消費費用とバッテリー交換作業費用の総和が最小となるように、これら3つの問題を同時に解くようにする。図3は本発明のアルゴリズムであるラグランジアンヒューリスティック法Lagrangianheuristicmethodに基づく近似最適解法の説明図であり、図3aはそのラグランジアンヒューリスティック法の実行フローチャート、図3bはアルゴリズムの繰り返し回数に対する目的関数値を示す図、図3cは最適解の存在範囲を示す模式図である。本発明では、上記した問題を解くため、以下のようなアルゴリズムを用いる。図3aに示すように、まず、初期解と初期ラグランジュ乗数の決定を行うステップS1。次に、ラグランジュ緩和問題を利用した下界値の生成を行うステップS2。次に、ラグランジュ乗数を利用した上界値の生成を行うステップS3。終了条件ステップS4を満足しなければ、ラグランジュ乗数の更新を行いステップS5、ステップS2へ戻り、終了条件ステップS4を満足したら、アルゴリズムの繰り返しを停止するステップS6。つまり、図3bに示すように、上界値と下界値の情報を利用して最適解に近い解を求める。ここで、上界値はアルゴリズムが出力した解、下界値は最適値以下であることが理論的に保証された値であり、図3cの下段に示すように、上界値と下界値の間の最適値の存在範囲が狭まるようにすることが望ましい。図4は本発明に係るWSNの設置及び運用費用評価方法によるWSNシステム設計における入力例と出力例を示す図であり、図4aはその入力例を示す図、図4bはその出力例を示す図である。本発明に係るWSNの設置及び運用費用評価方法においては、図4aに示すように、センサの配置場所、ゲートウェイの設置場所、リレーの設置候補場所、各電力送信受信センシング、各費用リレー設置、バッテリー消費、バッテリー交換作業を評価条件として入力すると、この入力条件にしたがって、図4bに示すように、リレーの設置場所、各センシングデータの伝送経路、各センサと各リレーのTPLの水準、ネットワーク寿命、WSNの単位期間あたりの費用が出力される。図5は既存WSNのネットワーク設計ロンドン地下鉄の説明図である。図5aは現在のWSN図13と対応であり、横軸がリングの位置、縦軸はセグメントA~Mを示しており、図5bは現在のWSNの条件の下、本発明の評価方法により提案されるWSNであり、横軸はトンネルリングの位置、縦軸はセグメントA~Mを示している。なお、図中のひし形及び丸はセンサの位置、四角はゲートウェイの位置を示している。また、図5aの横軸の数字はリング番号を示しており、1640は0m、1650は6.6m、1660は12.6m、1670は18.6m、1680は24.6m、1690は30.6m、1700は36.6m、1710は42.6m、1720は48.6mにそれぞれ対応しており、リング番号が示される他の図でも同様である。図5aの現在のWSNでは、一日あたりの全体の費用は1560円であり、ネットワーク寿命が123日であるのに対して、図5bの本発明による評価に基づくWSNでは、一日あたりの全体の費用は1349円となり、ネットワーク寿命も219日となった。このように、本発明によれば、15の費用低減を達成し、ネットワーク寿命を78延ばすことができた後出の表1参照。図6は拡張WSNのネットワーク設計ロンドン地下鉄の説明図である。図6aはリレー設置、TPL水準調整なしの場合であり、横軸がリングの位置、縦軸はセグメントA~Mを示しており、図6bはリレー設置、TPL水準調整ありの場合であり、横軸はリングの位置、縦軸はセグメントA~Mを示している。なお、図中のひし形及び丸はセンサの位置、四角はゲートウェイの位置を示しており、図6bの三角はリレーの位置を示している。図6aでは、一日あたりの全体の費用は8584円であり、ネットワーク寿命が69日であるのに対し、図6bでは、一日あたりの全体の費用は8230円となり、ネットワーク寿命は98日となった。このように本発明によれば、4.3の費用低減を達成し、ネットワーク寿命を42延ばすことができた後出の表2参照。上記したように本発明によれば、鉄道土木構造物の状態監視に用いる無線センサネットワークを、総費用が最小になるように設計できた。すなわち、本発明では最初にリレーの設置数とその設置場所、各センサーと各リレーにおける送信電力レベル、センシングデータをゲートウェイにマルチホップで送信するためのルートを同時に計画する問題を設定し、次いで、その問題を数理計画問題に定式化した後、ラグランジアンヒューリスティック法に基づくその問題の近似最適解法により解くことで設置及び運用費用の評価を行った。そして最後にその有効性を鉄道土木構造物の状態監視に用いる無線センサネットワークの実例を用いた数値実験により検証した。以下、より具体的に本発明の実施例を示す鉄道土木構造物の状態監視に用いるWSN無線センサネットワークの設置及び運用費用評価方法について説明する。既述のように、各センサや各リレーから送信できる範囲と送信のためのバッテリー消費量は、各センサや各リレーで設定するTPLの出力水準に依存する。図7は本発明に係るリレーからセンサへのTPLの出力水準と送信可能範囲との関係を示す図である。リレーからセンサへのTPLの出力水準ごとの送信可能範囲は図7に示すようになる。ただし、図7に関しては以下の通りである。1円はセンサ、三角はリレー、四角はゲートウェイで、円と三角内の数字はそれぞれセンサ番号、リレー番号である。2各センサと各リレーではTPLを1、2、3の何れかに設定でき、TPL1が最小送信出力、TPL3が最大送信出力、TPL2がその中間の送信出力である。3リレー6を設置した場合に、それからTPL1、2、3で送信できる範囲を、それぞれa、b、cの点線で示している。4リレー6からTPL1、2、3で送信できる箇所を、それぞれd、e、fの矢印で示している。この例においては、リレー6からセンサ2へ送信できるのはTPL3の場合だけである。よって、リレー6からセンサ2へ送信するには、リレー6のTPLを3に設定しなければならないことになる。また、リレー6からセンサ4へは、リレー6のTPLを1、2、3の中の何れに設定しても送信できるが、リレー6からセンサ1へは最大送信出力のTPL3でも送信できないことを示している。なお、本発明では、さらに以下を仮定する。i1つのセンサで収集したデータは1つにまとめ、それを途中の中継点で分割することなくゲートウェイに伝送するものとする。iiネットワーク内に設置する各リレーはすべて同一のものであるとする。iii鉄道土木構造物の状態監視において設置するセンサは、リレーにデータ収集機能を付加したものである場合が多い。つまり、センサも中継機能を持ち、センサとリレーの機能はデータ収集機能を除けば同一である場合が多い。そこで、各センサと各リレーにおけるTPLの水準数図7の場合は3は全て同一であるとする。ivバッテリー交換作業において交換するバッテリーは、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーだけで、次の巡回まで寿命のあるバッテリーは交換しないで良いものとする。つまり、システム内のあるバッテリーの寿命交換してから電力が枯渇するまでの期間がネットワーク寿命のθ>1倍以上でかつθ1倍未満である場合は、そのバッテリーはθ回の巡回に一度の割合で交換すれば良いものとする。次に、本発明と関連する研究について説明する。センサネットワークの長寿命化に関してはこれまでに多くの研究がなされている。例えば、Alfieriら上記非特許文献3参照は与えられたセンサを分割して複数の部分センサネットワークを構成し、それらの運用時間帯を調整することによりネットワーク寿命を長期化する手法を提案している。また、Tangら上記非特許文献4参照は伝送データの信頼性を考慮して、Kimら上記非特許文献5参照はセンシングデータの伝送遅延を考慮してネットワーク寿命を最大化する方法を提案している。しかしながら、これらの研究においては、ネットワーク内の総消費電力量について考慮していない。つまり、ネットワーク寿命と総消費電力量はトレードオフの関係にあることから、ネットワーク寿命について考える場合は同時に総消費電力量についても考慮すべきであるが、これらの研究においてはそれを明白には考慮していない。センサネットワーク内のリレー配置問題に関しても多くの研究がある。例えば、Houら上記非特許文献6参照はリレーの配置問題とゲートウェイやリレーへの電力の割当問題を同時に解く方法を提案している。また、Lloydら上記非特許文献7参照はセンサ間の通信を確保するために必要な最小のリレー数を求める問題を取り上げ、この問題に対する近似アルゴリズムapproximationalgorithmを提案している。Haoら上記非特許文献8参照は、各センサ間に少なくとも2本のルートが存在するような故障に強いネットワークトポロジーfault-tolerantnetworktopologyを構築するためのリレー配置問題を取り上げ、この問題に対する多項式時間近似アルゴリズムpolynomialtimeapproximationalgorithmを提案している。しかし、これらの研究においては送信範囲や電力消費に大きく関係するTPLの調整について考慮していない。他方、Correiaら上記非特許文献9参照は通信と消費電力量を考慮してTPLを決定する方法を提案している。しかし、彼らの研究においてはリレー配置を考慮していない。また、彼らの研究においてはネットワーク寿命についても考慮していない。WSNの構築費用を考慮したモデルも提案されている。Katenkaら上記非特許文献10参照は平面上にセンサを配置する際に、配置するセンサ数と各センサに付随するコストを最小化する問題を取り上げている。Mhatreら上記非特許文献11参照は通信と拘束有効範囲coverageconstraintsを考慮して、ノード設置費用とバッテリー設置費用の総和を最小化する問題に取り組んでいる。また、Chengら上記非特許文献12参照はWSN設置に必要なコストを、複数のWSN設置戦略を適用した場合の様々なシナリオにおいて算出比較している。しかしながら、これらの研究においてはWSNの運用費用について考慮していない。つまり、WSNを構築し運用する際に発生する総費用を最小にするためには、WSNの設置費用に加えてその運用費用につても考慮しなければならないが、これらの研究ではそれについて明白には触れていない。既述のように、リレーの設置計画、TPLの設定計画、センシングデータのルート計画は互に密接に関係しており、それらを個別に計画しても総費用の最小化を保証することはできない。それゆえ、総費用が最小となるようにそれらを同時に計画する問題は、WSNの設計においても、そしてその運用においても極めて重要であると思われる。しかしながら、上で見たように、そのような問題は未だ取り扱われていない。以下、本発明にかかるWSNの設置及び運用費用評価方法のアルゴリズムについて詳述する。まず、定式化Formulationを行う。ここでは、センサの集合をS={1,2...|S|}、リレー設置候補場所の集合をR={|S|1|S|2...|S||R|}とする。また、ゲートウェイを0で表し、各センサで収集したデータはマルチホップ通信でそこに伝送するものとする。また、M=S∪R∪、N=S∪R∪{0}とおき、MやNについて考える場合はそれらの要素を特にノードと呼ぶ。また、各バッテリーで消費可能な最大電力量をバッテリー容量と呼び、ノードi∈Mのバッテリー容量をEiとする。加えて、各センサと各リレーにおけるTPLの集合をP={1,2...|P|}とし、一般性を失うことなく、送信出力は1<2<...<|P|の順序で大きくなるものとする。つまり、TPL1が最小送信出力で、TPL|P|が最大送信出力であるものとする。ここで、伝送ルートとTPLについて説明する。あるノードi∈Mとあるノードj∈Nを考えると、ノードiからノードjへ他のノードを経由しないで直接送信できるノードiにおけるTPLの集合が定まる。そこで、Pij:ノードi∈Mからノードj∈Nへ直接送信できる、ノードiにおけるTPLのl∈Pの集合と定義する。そして、このAをアーク集合とし、Nをノード集合とする有向グラフをG=N,Aとする。ここで、|Pij|>2である場合は、Gにはノードiからノードjへの|Pij|本のマルチプルアークmultiplearcが存在することに注意する。Gにマルチプルアークが存在する状況を図示すると図8のようになる。ただし、図8に関しては以下の通りであり、円形、三角、四角の意味は図7と同じである。1図7のノード間に存在する全てのアークを図示した場合の例である。2d,e,fのアークは、図7の場合と同様に、それぞれTPL1、2、3で送信できることを示している。3双方向アークは、その両端のノードは相互に送信可能であることを示している。この例においては、幾つかのノード間にマルチプルアークが存在する。例えば、ノード6からノード5へは2本のアーク6,5,2、6,5,3つまり、ノード6からノード5へTPL2で送信するアークと、ノード6からノード5へTPL3で送信するアークが、逆にノード5からノード6へも2本のアーク5,6,2、5,6,3が存在する。また、ノード6からノード0へは2本のアーク、6,0,2、6,0,3が存在する。なお、ノード0はゲートウェイであり、ゲートウェイは受信だけであるから、ノード0へのアークは全て片方向であることに注意。あるセンサi∈Sを始ノードとし、ゲートウェイ0を終ノードとするG=N,A上のルートを特に伝送ルートと呼び、それをアークの集合で示す。このとき、Gにあるセンサを始ノードとする伝送ルートが存在しなければ、リレーをどのように配置しても、そのセンサからはゲートウェイにデータを送信することができない。そこで、Gには各センサを始ノードとする伝送ルートが少なくとも1本は存在するものとする。また以下では、Gにおけるノードi∈Mの入次数と出次数は共に1以上であると仮定する。つまり、ノードi∈Mは少なくとも他の1つのノードから受信可能で、かつ少なくとも他の1つのノードへあるTPLで送信可能であると仮定する。と定義する。そして、このxkijlとyilをそれらに対応したルート案が実行可能であるように定めた場合について考える。つまり、それらを次のように定めた場合について考える。i各k∈Sについて{ijl∈A|xkijl=1}はノードkからノード0へのルートである。すなわち、各センサを始ノードとする|S|個の伝送ルートが生成されている。iiあるxkijlが1ならばyil=1である。すなわち、ある伝送ルートにアークijlが含まれている場合は、ノードiのTPLがlに設定されている。iiiあるyilが1ならばyil ́=0l ́∈P\{l}である。すなわち、各ノードにおいてはTPLが同時に2つ以上の水準に設定されていない。次に、バッテリー交換作業費用について説明する。各センサでは単位期間に1回データを収集し、それを処理後ゲートウェイへ伝送する。そこで、各センサで単位期間に収集するすべてのデータを、収集処理し、受信し、送信するのに必要な電力量を次のように記す。sk:センサk∈Sでデータを収集処理するのに必要な電力量rk:センサk∈Sで収集したデータを各ノードで受信するのに必要な電力量tkl:センサで収集したデータを各ノードからTPLl∈Pで送信するのに必要な電力量このとき、ノードi∈Mで単位期間に必要な電力量Fixは次のようになる。ただし、eiはi∈Sである場合はei=siであり、i∈Rである場合はei=0であるものとする。ここで、式の右辺第1項はデータの送信に、第2項はデータの受信に、そして第3項はセンサでデータを収集処理するのに必要な電力量である。上記式1によって各ノードで単位期間に必要な電力量が定まれば、その電力量と各ノードのバッテリー容量よりネットワーク寿命が定まる。つまり、ネットワーク寿命をdxとすると、それはバッテリー容量Eiと式より次で定まる。加えて、1回当りのバッテリー交換作業費用をc1、1J当りのバッテリー消費費用をc2、リレーを1個設置した場合の単位期間当りの費用をc3とする。ここで、容量がEiJであるバッテリーの価格がaiである場合はc2=ai/Eii∈Mと算出され各バッテリーにおける1J当りのバッテリー消費費用は全て同一であるとしていることに注意、リレー1個当たりの設置費用がbで各リレーの使用可能期間がT期間である場合はc3=b/Tと算出される。また、1回当りのバッテリー交換作業費用がc1で、ネットワーク寿命がdx期間ならば、単位期間当りのバッテリー交換作業費用はc1/dxとなる。つまり、式よりであるから、単位期間当りのバッテリー交換作業費用は、次のようになる。定式化の準備の最後に、電力消費費用について説明する。本発明においては、バッテリー交換作業において交換するバッテリーは、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーだけで、次の巡回まで寿命のあるバッテリーは交換しないで良いものとした。となる。しかしながら、上式はかなり煩雑でこのままでは取り扱いが困難である。そこで、ここでは、式のフロア関数を緩和し、式の分母はEi/Fix1/dxdxであるものと近似する。すると、ノードi∈Mのバッテリーの単位期間当たりの電力消費費用は、となる。つまり、ノードi∈Mのバッテリーの単位期間当たりの電力消費費用はc2Fixとなる。このとき、さらに変数zを導入すると、単位期間当たりの総費用が最小となるようにWSNを設計する問題は、次のような混合整数計画問題mixedintegerprogrammingproblemに定式化される。xkijl≦yilijl∈A,k∈S...11xkijl∈{0,1}{ijl}∈A,k∈S...13yil∈{0,1}i∈M,l∈P...14ここで、目的関数である式7の第1項はバッテリー交換作業費用、第2項はネットワーク内の総バッテリー消費費用、第3項はリレー設置費用である。また式は、目的関数の第1項は式の右辺と等価であることを保証する。また、式と式は前述のiを、式は前述のiiを、そして式は前述のiiiを保証する。i~iiiについては、伝送ルートとTPLの定式化の説明部分を参照。なお、ノードi∈Rには、それが生成された何れかの伝送ルートに含まれている場合に限りリレーを設置することになる。また、式よりzの最小化はネットワーク寿命dxの最大化と等価である。よって、上述の問題はc1=1としc2=c3=0とすればネットワーク寿命を最長化する問題となる。また、c2=1、c1=c3=0とし、そしてバッテリー容量Ei=∞i∈Mとすれば、問題はネットワーク内の総電力使用量を最小化する問題となる。上記問題は明らかにNP困難な問題であり、実際問題の多くは、その最適解を求めるのは困難であると思われる。それゆえ、実際問題に対しては、メタヒューリスティックスmetaheuristicsや欲張りアルゴリズムgreedyalgorithmなどの近似解法が必要となるが、それらの近似解法では求めた解が最適解にどれだけ近似しているかを評価できない場合が多い。つまり、それらの近似解法では下界値を算出していないため、多くの場合、求めた解を相対誤差上界値-下界値/下界値で評価することができない。これに対して、求めた解を相対誤差で評価できる方法に、ラグランジアンヒューリスティック法Lagrangianheuristicmethodがある。この方法は、上界値と下界値の差を順次減少させながら対象問題の近似最適解を求める方法であり、実際規模の問題にも適用可能である。また、この方法によればラグランジュ緩和問題Lagrangianrelaxationproblemの最適解を利用して対象問題の近似解を効率的に探索することができる。そこで以下では、このラグランジアンヒューリスティック法に基づく問題の近似最適解法求めた解を相対誤差で評価できる解法について考える。ラグランジアンヒューリスティック法は、概略、次のような手順を繰り返し実行して、原問題の近似最適解near-optimalsolutionを求める方法である。ただし、原問題は最小化問題とする。手順1S1.原問題のラグランジュ緩和問題を解いて、原問題の下界値を求める。S2.ラグランジュ緩和問題の最適解を利用して、原問題の可能解とその目的関数値上界値を求める。S3.上界値と下界値を用いて相対誤差を算出する。相対誤差あるいは計算時間が所与の終了条件を満たしたならば計算を終了する。S4.ラグランジュ乗数Lagrangianmultipliersを適切な方法で更新して、S1に戻る。したがって、上記S1、S2、S4を実行する具体的な方法を示せば、問題のラグランジアンヒューリスティック法に基づく近似最適解法が構築される。そこで以下では、上記S1、S2、S4を実行する方法について順次説明する。まず、下界値の決定について説明する。ここでは、上記手順1のS1に示した、ラグランジュ緩和問題を解いて問題の下界値を生成する方法について説明する。ラグランジュ乗数u=ui>0i∈Mを用いて式を、ラグランジュ乗数v=vkijl>0ijl∈Ak∈Sを用いて式を、問題の目的関数に組み込み、それを整理すると次のようになる。よって、上式の変数xkijlとのyilに注目して、とおくと、次のような問題のラグランジュ緩和問題を得る。ここで、問題の最適値をcで記すと、ラグランジュ緩和法の原理よりcLuv<cPが成り立つ上記非特許文献13,14参照。つまり、問題Luvの最適値が問題の下界値を与える。ところで、問題Luvの変数zには非負条件が付いていない。それゆえ、最小化問題Luvにおいては、目的関数におけるzの係数が正の場合にはz=-∞とし、それが負の場合にはz=∞とすると、問題cLuvの目的関数値=-∞となる。つまり、zの係数が非ゼロの場合は、問題の有意な下界値を得ることができない。そこで以下では、uiはである場合に限定する。式よりLuvの目的関数の第1項は消える。よって、問題はLuvは、xkijlに関するとなる。ここで、LXuvにおけるk∈Sをあるkに固定した場合の問題をLXkuvとすると、LXuvはさらに|S|個の問題LXkuvk∈Sに分解される。そして、各LXkuvは明らかにノードkからノード0への最短ルート問題である。他方、LYvにおけるi∈Mをあるiに固定した場合の問題をLYivとすると、問題LYvもさらに|M|個の問題LYivi∈Mに分解され、そして各LYivは明らかに自明な問題である。よって、ラグランジュ緩和問題のLuv最適値は、つまり問題の下界値は、|S|個の最短ルート問題と|M|個の自明な問題を解くとで求めることができる。ここで、最短ルート問題については、その最適解を多項式時間で求めるアルゴリズムが既に数多く提示されている上記非特許文献15,16参照。次に、手順1のS2に示した、上界値可能解の決定について説明する。ここでは、ラグランジュ緩和問題LXuvの最適解を利用して、問題の可能解を求める方法について説明する。である。ただし、βはBii∈Mの和集合である。例えば、図9の場合は、B2={2,52,6}B4={4,0}、S2,5={1}S4,0={2,4}などのようになる。そこで、以下の手順で可能解を決定する。そこで、以下の手順で可能解を改善する。次に、手順1のS4に示した、ラグランジュ乗数の更新について説明する。問題Pの下界値cLuvは、当然のことながら、ラグランジュ乗数u=ui、v=vkijlに依存する。それゆえ、問題のよりよい下界値を求めるためにはcLuvが最大となるようなuvを求めることが望まれる。他方、そのようなラグランジュ乗数を漸近的に求める方法によく知られた劣勾配法がある上記非特許文献17参照。この方法は、これまでに種々の組合せ最適化問題に適用され、その有効性が多くの研究で検証されている上記非特許文献18、19参照。そこでここでは、この劣勾配法でcLuvが最大となるようなラグランジュ乗数を漸近的に求めるものとする。すなわち、次の手順でラグランジュ乗数uvを逐次更新するものとする。そこで、以下の手順でラグランジュ乗数の設定を行う。S4-1.cLuvのuivkijlにおける劣勾配λiμkijlを次で定める。S4-2.ステップレングスρσを次で定める。S4-3.乗数uivkijlを次で更新する。ui:=max{0uiρλi}i∈Mvkijl:=max{0vkijlσμkijl}ijl∈Ak∈SS4-4.乗数uiを次で調整する。なお、この手順のS4-4は、uiが式を満たすように調整するためのものである。また、劣勾配法においては、多くの場合、ステップレングスをρ=σとする。そして、それを次のように定める場合が多い。しかし、ステップレングスを上式で定めると、μkijlに比してλiがステップレングスの値の決定により強く反映してしまう懸念がある。つまり、S1における劣勾配法の決定方法より-1<μkijl<1であるから、λi≫1である場合には、μkijlに対してλiだけがステップレングスの決定により大きく反映してしまう懸念がある。そこで本発明では、ステップレングスρとσをS2で別々に定めるものとする。したがって、ここでの劣勾配法は正確には修正劣勾配法である。以上のようなアルゴリズムで、WSNの設置及び運用費用の評価を行う。上記してきた本発明にかかるWSNの設置及び運用費用の評価方法の有効性を検証するための、実例を用いた計算実験を以下に示す。上記したように、ロンドン地下鉄のジュビリー線には、トンネル内の状態監視のためのWSNが既に設置されている。そこでここでは、既設のWSNの条件の下、本発明のWSNの設置及び運用費用の評価方法で設計した場合のWSN案を作成し、それと現在のWSNとの比較検証を行う。また、ロンドン地下鉄のWSNに設置するセンサ数を、現在よりも増やした場合図6に示した拡張WSNと対応に、総費用がどのように変化するかを検証するための計算実験も行う。なお、ロンドン地下鉄の現在のWSNには、26個のセンサ傾斜計6台、クラックメータ16台、環境センサ4台と1台のゲートウェイが設置されている図13参照。以下の計算実験においては、データの送信受信電力と他の各費用に関する電力消費パラメータを次のように定めた。各センサでは5秒に1回データを取得するものとした。つまり、各センサの単位期間は5秒とした。各センサでデータを収集処理するのに必要な電流値、電圧値、収集処理時間は全て同一で、それぞれ7mA、3V、0.25秒であるとした。つまりsk=5.25×103k∈Sとした。各センサで収集したデータを受信するのに必要な電流値、電圧値、受信時間は各センサとリレーで全て同一で、それぞれ19.7mA、3V、0.5秒であるとした。つまりrk=29.55×103k∈Sとした。TPLは1、3、t2k=16.5×103、t3k=26.1×103とした。1回当たりのバッテリー交換作業費用c1は、各問題例のセンサ数に応じて個別に定めた。各センサと各リレーでは50Ah、3Vのバッテリーを使用するものとし、その価格は200£であるとした。つまり、Ei=5.4×105Ji∈Mとしc2=3.7×104とした。リレーの設置費用は1台当たり400£とし、各リレーの使用可能期間は10年とした。つまり、c3=6.34×106とした。また、以下での計算実験は全て次のような環境の下で実施した。ロンドン地下鉄のジュビリー線のトンネルに関しては、各TPLで与えられたノード間の無線通信が可能かを判定できる経験モデルempiricalmodel上記非特許文献20参照が既に提示されている。そこで、ノードiからノードjへ送信できるノードiにおけるTPLの集合Pijは、それを用いて定めた。ゲートウェイは現在のロンドン地下鉄と同じ位置に設置されているものとした。つまり、ゲートウェイは全て図13におけるトンネルの一端から27.6m離れた位置のリングのセグメントBに設置されているものとした。ラグランジュ乗数の初期値はui=1/|M|i∈Mとし、vijlk=1/|A|×|S|ijl∈Ak∈Sとした。本発明のアルゴリズムの終了条件は計算時間secondの最大許容値とし、各計算実験の計算時間はその実験における問題例のセンサ数に応じて定めた。使用計算機言語はC言語で、使用計算機の仕様はWindowsXPリレーは設置しない。各ノードのTPLは全て水準3に固定。リレーは設置しない。各ノードのTPLは調整可能。リレーの設置を検討。各ノードのTPLは全て水準3に固定。リレーの設置を検討。各ノードのTPLは調整可能。ここで上記は、現在のWSNを本発明のアルゴリズムを用いて評価するための実験である。また上記、におけるリレー設置候補場所は、図13におけるトンネルの一端から6.6、9.6、12.6、15.6、18.6、22.8、24.6、30.6、33.6、39.6m離れた位置のリングのセグメントA,C,E,G,J,L,Nとした。したがって、リレー設置候補場所数は10×7=70箇所となる。また、これらの実験においては、巡回1回当たりのバッテリー交換作業費用は全てc1=200£とし、計算時間を300sとした。上記~の場合の実験結果を表1に示す。ただし、表1と以下で示す表2に関しては以下の通りである。i|S|は設置センサ数、|R|はリレー設置候補場所数である。したがって、|R|=0である場合はリレーを設置できないことを示している。iiTPLに関しては、各ノードのTPLが全て最大出力水準に固定されている場合は3とし、それを調整可能な場合は1,2,3としている。iiicUとcLは、それぞれ本発明のアルゴリズムで得られた最良の上界値£/day、下界値£/dayである。ここで、cUとcLは単位期間当たりではなく、1日当たりに換算していることに注意する。iverrorは相対誤差で、cU-cL/cLである。vlifetimeは得られたWSNのネットワーク寿命日数:dayで、relayは設計されたWSNにおいて設置するリレーの数である。iterationはラグランジアンヒューリスティック法の繰返し回数、timeは計算時間secondである。また、上記手順3では可能解を改善するために確率変数を利用しているので、同一の問題例でも計算結果が異なる場合が存在する。そこで、同一の問題例を5回解いた。したがって、表1と表2の値は5回の解の平均値である。そのため表1及び表2のCU,CL,error,lifetime,relay,iterationの値は整数でないものがある。現在のWSNは、問題の1つの可能解であると見なすことができる。それゆえ、現在のWSNに対応した、xijlk、yilを定めるとzはxijlkより定まることに注意、それより現在のWSNに対する問題の目的関数値が求まる。そこで、現在のWSNに対する問題の目的関数値上界値Cuを求めて見ると、10.4035£/dayとなる。他方、本発明のアルゴリズムで求めた、現在のWSN表1の第1行に対する下界値Cuは9.2931である。つまり、本発明のアルゴリズムで求めた下界値Cuより、現在のWSNの総費用は改善できたとしても10.4035-9.2931=1.1104£/dayであることが分かる。そしてこれより、各センサのTPLは全て3に固定という前提の下では、現在のWSNは比較的良好なWSNであると評価することができる。なお表1の第1行より、本発明のアルゴリズムで求めたWSNの上界値も、現在のWSNのそれに等しく10.4035これが最適値である場合もあり得ることに注意である。これは、TPLを全て最大送信出力の3に固定していることに加えて、設置センサ数が26と比較的少ないことから、本発明のアルゴリズムにおいても現在のWSNとほぼ同様な伝送ルート案が出力されたためである。上述のように、TPLを全て3に固定した場合は、現存のWSNを改善できる余地は少ないと思われる。しかしながら表1をみると、TPLを調整すると現存のWSNをさらに改善できることを示している。すなわち表1の第2行は、TPLを調整すると、総費用を8.9923£/dayに改善できる上に、ネットワーク寿命も123.06日から219.07日に大きく改善できることを示している。また表1の第3、4行からは、現在のWSNに新たにリレーを設置する必要はないことがみてとれる。これは、各センサからの伝送ルートをリレーを使用しなくても確保できたことや、設置センサ数が比較的少ないために、リレーを使用しなくても各センサでの消費電力量をある程度平準化できたためであると推察される。図10は、本発明にかかるWSNの設置及び運用費用評価方法により評価構築されたWSNの出力結果の1例表1の第4行の|R|=70でTPLが1,2,3である場合である。ただし、図10と以下に示す図11、12において、円はセンサを、三角はリレーを示している。また、各センサと各リレーで設定するTPLを区別し、i、ii、iiiはそれぞれTPLを1、2、3に設定することを示しているここで、i、ii以外はiiiであり、iiiは数が多いので表記していない。なお、本図は図5bと同じ図である。また、四角はゲートウェイで、線は伝送ルートを構成するアークである。図10には、同じ位置での上部と下部の間の通信が、つまりトンネル内の片方の側壁から他方の側壁への通信がいくつか存在する。これは、トンネル内の無線通信においては、同じサイドに設置されているノード間よりも、異なるサイドに設置されているノード間の方が、一般的に通信を確立し易いためであると思われる。事実、ロンドン地下鉄のジュビリー線のトンネル内で実施された無線通信試験においても、そのような傾向にあることが確認されている。前述のように、設置センサ数が26である現在のWSNにおいては、リレー使用の効果を確認することができなかった。そこで、設置センサを現在のWSNよりも増やした場合の実験を行った図6の拡張WSNに対応。ただし、この実験においては、現在配置されている26個のセンサに加えて、図13におけるトンネルの一端から3.6、9.6、15.6、18.6、24.6、39.6m離れた位置のリングのセグメントC,E,J,Lにさらに24個のセンサが設置されている場合と、トンネルの一端から3.6、6.6、9.6、15.6、18.6、21.6、24.6、33.6、39.6、42.6m離れた位置のリングのセグメントA,C,E,G,J,L,Nにさらに70個のセンサが設置されている場合について実験を行った。つまり、|S|=50である場合と、|S|=96である場合について実験を行った。他方、リレー設置候補場所は、|S|=50である場合はトンネルの一端から3.6、6.6、9.6、15.6、18.6、24.6、33.6、39.6、42.6m離れた位置のリングのセグメントB,DF,H,K,Mに54箇所とし、|S|=96である場合はトンネルの一端から3.6、6.6、9.6、15.6、18.6、24.6、33.6、39.6、42.6m離れた位置のリングのセグメントB,DF,H,K,Mに54箇所と、トンネルの一端から21.6m離れた位置のリングのセグメントDF,H,Kに4箇所の計58箇所とした。また、バッテリー交換作業費用c1は|S|=50である場合は300£とし、|S|=96である場合は500£とした。さらに計算時間は、|S|=50である場合は600秒とし、センサ数がその約2倍の|S|=96である場合は1200秒とした。上記の場合の実験結果を表2に示す。また、この実験について本発明にかかるWSNの設置及び運用費用評価方法により評価構築されたWSNの出力結果の例を図11表2の第4行の|S|=50、|R|=54でTPLが1,2,3である場合、図12表2の最終行の|S|=96、|R|=58でTPLが1,2,3である場合に示す。なお、図12は図6bと同じ図である。表2に示された結果より、リレーの設置を考慮すると上界値を低減できること、そしてTPLを調整するとそれを更に改善できることがわかる。例えばセンサが50個の場合、上界値CUは32.4148£/dayから30.8223£/dayへ低減されることを示している。また表2は、リレーの設置とTPLの調整を同時に考慮すると、総費用をより低減できることを示している。さらに表2は、リレーの設置とTPLの調整が、lifetimeの長期化にも有効であることを示唆している。さらに表2における相対誤差は、多少バラツキがあるもののその平均値は0.0828である。これより、この実験で取り上げた規模の問題であれば、本発明のアルゴリズムで比較的良好な可能解が求まることが分かる。なお表2において、|S|=50、|R|=54である場合のlifetimeが、TPLを固定した場合よりもそれを調整した場合の方が短くなっているのは、本発明のアルゴリズムがライフタイムの長期化よりも総費用の最小化を優先しているためである事実、総費用はTPLを調整した方が少なくなっている。また図11,12において、左右方向に比較的長い距離の通信が発生しているのは、あるノードから送信する際の消費電力量は送信先のノードまでの距離ではなく、そのノードで設定するTPLの水準に依存することが大きく関係しているものと思われる。なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨に基づき種々の変形が可能であり、これらを本発明の範囲から排除するものではない。"