対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法
【課題】 埋没費用と考えられるセンサとゲートウェイの設置費用を除いた、初期投資費用（リレー設置費用）と運用費用（バッテリー消費費用、バッテリー交換作業費用）の費用の最小化を図ることができる無線センサネットワークの設置及び運用費用評価方法を提供する。
【解決手段】 対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、対象構造物内に配置された複数のセンサ３で得られたデータをこのセンサ及び／又はリレーでゲートウェイ４に転送し、その転送されたデータを管理局６にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、このバッテリー交換作業費用との総和を最小とするために、数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法に基づく近似最適解法を用いてセンサネットワークを設計する。
【解決手段】 対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、対象構造物内に配置された複数のセンサ３で得られたデータをこのセンサ及び／又はリレーでゲートウェイ４に転送し、その転送されたデータを管理局６にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、このバッテリー交換作業費用との総和を最小とするために、数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法に基づく近似最適解法を用いてセンサネットワークを設計する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、対象構造物の状態監視のための無線センサネットワーク（Ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ，ＷＳＮ）の設置及び運用費用評価方法に係り、特に鉄道土木構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法に関するものである。
【背景技術】
【０００２】
本発明では、対象構造物の状態監視に用いられる無線センサネットワークを、総費用が最小となるように設計する方法を提案する。
特に、鉄道土木構造物に対する保守管理は、これまで人手による目視検査を中心に行われてきた。
しかしながら、現状の人手による目視での状態監視方法には、
（１）作業に多大な労力と時間が必要である
（２）見落としや見間違いなどのヒューマンエラーがつきものである
（３）検査結果の客観性の欠如があり、検査技術の承継も困難である
（４）危険な現場での検査業務となる、などの問題があった。
【０００３】
近年、これらの問題点を克服する目的で、無線センサネットワークを活用した鉄道土木構造物の保守管理が注目を集めている。
ここで、無線センサネットワーク（ＷＳＮ）とは、無線通信機能を持つ多数の小型センサによる自動的なネットワークのことであり、土木構造物の状態監視へ適用した場合の利点として、（１）センサ同士がリレーしてデータを転送することができるので、配線が不要であり、冗長性が高い、（２）デバイスが小型であるので設置場所を選ぶことなく、多様な測定ができる、などがある。実際に、ロンドン地下鉄、プラハ地下鉄、バルセロナ地下鉄の一部区間では既にＷＳＮを利用した鉄道構造物の状態監視システムが導入されている（下記非特許文献１，２参照）。
【０００４】
図１３はロンドン地下鉄のジュビリー線に設置されたＷＳＮの模式図であり、図１３（ａ）はその全体模式図、図１３（ｂ）は図１３（ａ）のＡ部拡大図である。
ロンドン地下鉄は世界でも最も広範囲に老朽化が進んでいる地下鉄の１つであり、全長１８１ｋｍのトンネルの多くが建設から既に７５−１００年が経過している。このため、トンネル内のライニングの劣化や経時的な土圧の変化などが懸念されていた。
【０００５】
そこで、２００７年にそれらをモニタリングするため、図１３〔拡大部分の英大文字はトンネル内壁のセグメント（ｓｅｇｍｅｎｔ）〕に示すようなＷＳＮがベーカーストリート駅からボンドストリート駅間に設置された（下記非特許文献１，２参照）。なお、図１３（ａ）の黒丸はゲートウェイであり、図１３（ｂ）の２７．６ｍに位置するリングのセグメントＢに配置されている。また、ロンドン地下鉄のハマースミス駅構内では、２００３年にレール折れによる脱線事故が発生しており、このレール折れの発生原因は、線路両脇にある擁壁の変状にあると推測された。そこで、このような事故の再発を防止すべく、現場の擁壁変状をモニタリングするためのＷＳＮが２００９年にハマースミス駅構内に設置された。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｐｅｔｅｒ Ｊ．Ｂｅｎｎｅｔｔ，Ｋｅｎｉｃｈｉ Ｓｏｇａ，Ｉａｎ Ｗａｓｓｅｌｌ，Ｐａｕｌ Ｆｉｄｌｅｒ，Ｋｅｉｔａ Ａｂｅ，Ｙｕｓｕｋｅ Ｋｏｂａｙａｓｈｉ，Ｍａｒｔｉｎ Ｖａｎｉｃｅｋ，“Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ ｆｏｒ Ｕｎｄｅｒｇｒｏｕｎｄ Ｒａｉｌｗａｙ Ａｐｐｌｉｃａｔｉｏｎｓ：Ｃａｓｅ Ｓｔｕｄｉｅｓ ｉｎ Ｐｒａｇｕｅ ａｎｄ Ｌｏｎｄｏｎ”，Ｓｍａｒｔ Ｓｔｒｕｃｔｕｒｅｓ ａｎｄ Ｓｙｓｔｅｍｓ，Ｖｏｌ．６，Ｎｏ．５−６，ｐｐ．６１９−６３９，２０１０．
【非特許文献２】Ｆ．Ｓｔａｊａｎｏ，Ｎ．Ｈｏｕｌｔ，Ｉ．Ｊ．Ｗａｓｓｅｌ，Ｐ．Ｊ．Ｂｅｎｎｅｔｔ，Ｃ，Ｍｉｄｄｌｅｔｏｎ，Ｋ．Ｓｏｇａ，Ｓｍａｒｔ ｂｒｉｄｇｅ，ｓｍａｒｔ ｔｕｎｎｅｌｓ；ｔｒａｎｓｆｏｒｍｉｎｇ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｆｒｏｍ ｒｅｓｅａｒｃｈ ｐｒｏｔｏｔｙｐｅｓ ｉｎｔｏ ｒｏｂｕｓｔ ｅｎｇｉｎｅｅｒｉｎｇ ｉｎｆｒａｓｔｒｕｃｔｕｒｅ，Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｓ ８（８）（２０１０），ｐｐ．８７２−８８８
【非特許文献３】Ａ．Ａｌｆｉｅｒｉ，Ａ．Ｂｉａｎｃｏ，Ｐ．Ｂｒａｎｄｉｍａｒｔｅ ａｎｄ Ｃ．Ｆ．Ｃｈｉａｓｓｅｒｉｎｉ，“Ｍａｘｉｍｉｚｉｎｇ ｓｙｓｔｅｍ ｌｉｆｅｔｉｍｅ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ，”Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，ｖｏｌ．１８１，ｐｐ．３９０−４０２，２００７.
【非特許文献４】Ｘ．Ｔａｎｇ ａｎｄ Ｊ．Ｘｕ，“Ｅｘｔｅｎｄｉｎｇ ｎｅｔｗｏｒｋ ｌｉｆｅｔｉｍｅ ｆｏｒ ｐｒｅｃｉｓｉｏｎ−ｃｏｎｓｔｒａｉｎｅｄ ｄａｔａ ａｇｇｒｅｇａｔｉｏｎ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ，”ｉｎ Ｐｒｏｃ．ｔｈｅ ２５th ＩＥＥＥ ＩＮＦＯＣＯＭ’０６，ｐｐ．１−１２，Ａｐｒ．２００６．
【非特許文献５】Ｊ．Ｋｉｍ，Ｘ．Ｌｉｎ，Ｎ．Ｂ．Ｓｈｒｏｆｆ ａｎｄ Ｐ．Ｓｉｎｈａ，“Ｏｎ ｍａｘｉｍｉｚｉｎｇ ｔｈｅ ｌｉｆｅｔｉｍｅ ｏｆ ｄｅｌａｙ−ｓｅｎｓｉｔｉｖｅ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ａｎｙｃａｓｔ，”ｉｎ Ｐｒｏｃ．ｔｈｅ ２７th ＩＥＥＥ ＩＮＦＯＣＯＭ’０８，ｐｐ．８０７−８１５，Ａｐｒ．２００８．
【非特許文献６】Ｙ．Ｔ．Ｈｏｕ，Ｙ．Ｓｈｉ，Ｈ．Ｄ．Ｓｈｅｒａｌｉ ａｎｄ Ｓ．Ｆ．Ｍｉｄｋｉｆｆ, “Ｐｒｏｌｏｎｇｉｎｇ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｌｉｆｅｔｉｍｅ ｗｉｔｈ ｅｎｅｒｇｙ ｐｒｏｖｉｓｉｏｎｉｎｇ ａｎｄ ｒｅｌａｙ ｎｏｄｅ ｐｌａｃｅｍｅｎｔ，”ｉｎ Ｐｒｏｃ．ＩＥＥＥ ＳＥＣＯＮ’０５，ｐｐ．２９５−３０４，Ｓｅｐ．２００５．
【非特許文献７】Ｅ．Ｌ．Ｌｌｏｙｄ，Ｇ．Ｘｕｅ，“Ｒｅｌａｙ Ｎｏｄｅ Ｐｌａｃｅｍｅｎｔ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ”，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ，Ｖｏｌ．５６，Ｉｓｓｕｅ．１，ｐｐ．１３４−１３８，２００７．
【非特許文献８】Ｂ．Ｈａｏ，Ｈ．Ｔａｎｇ，Ｇ．Ｘｕｅ，“Ｆａｕｌｔ−ｔｏｌｅｒａｎｔ Ｒｅｌａｙ Ｎｏｄｅ Ｐｌａｃｅｍｅｎｔ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ”，ｉｎ Ｐｒｏｃ．Ｔｈｅ Ｗｏｒｋｓｈｏｐ ｏｎ Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｓｗｉｔｃｈｉｎｇ ａｎｄ Ｒｏｕｔｉｎｇ，ｐｐ．２４６−２５０，２００４．
【非特許文献９】Ｌｕｉｚ Ｈ．Ａ．Ｃｏｒｒｅｉａ，Ｄａｎｉｅｌ Ｆ．Ｍａｃｅｄｏ，Ａｌｄｒｉ Ｌ．ｄｏｓ Ｓａｎｔｏｓ，Ａｎｔｏｎｉｏ Ａ．Ｆ．Ｌｏｕｒｅｉｒｏ，Ｊｏｓｅ Ｍａｒｃｏｓ Ｓ．Ｎｏｇｕｅｉｒａ，“Ｔｒａｎｓｍｉｓｓｉｏｎ Ｐｏｗｅｒ Ｃｏｎｔｒｏｌ Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ”，Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ, Ｖｏｌ．５１，ｐｐ．４７６５−４７７９，２００７．（ただし、ｅはアキュートアクセント付き）
【非特許文献１０】Ｎａｔａｌｌｉａ Ｋａｔｅｎｋａ，Ｅｌｉｚａｖｅｔａ Ｌｅｖｉｎａ，Ｇｅｏｒｇｅ Ｍｉｃｈａｉｌｉｄｉｓ，“Ａ Ｃｏｓｔ−Ｅｆｆｉｃｉｅｎｔ Ａｐｐｒｏａｃｈ ｔｏ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ”，Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ Ｎｏ．４７４，Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｓｔａｔｉｓｔｉｃｓ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍｉｃｈｉｇａｎ，２００７．
【非特許文献１１】Ｖｉｖｅｋ Ｐ．Ｍｈａｔｒｅ，Ｃａｔｈｅｒｉｎｅ Ｒｏｓｅｎｂｅｒｇ，Ｄａｎｉｅｌ Ｋｏｆｍａｎ，Ｒａｖｉ Ｍａｚｕｍｄａｒ，Ｎｅｓｓ Ｓｈｏｆｆ，“Ａ Ｍｉｎｉｍｕｍ Ｃｏｓｔ Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ ｗｉｔｈ ａ Ｌｉｆｅｔｉｍｅ”ｃｏｎｓｔｒａｉｎｔ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ，Ｖｏｌ．４，Ｎｏ．１，ｐｐ．４−１５，２００５．
【非特許文献１２】Ｚｈａｏ Ｃｈｅｎｇ，Ｍａｒｋ Ｐｅｒｉｌｌｏ，Ｗｅｎｄｉ Ｂ．Ｈｅｉｎｚｅｌｍａｎ，“Ｇｅｎｅｒａｌ Ｎｅｔｗｏｒｋ Ｌｉｆｅｔｉｍｅ ａｎｄ Ｃｏｓｔ Ｍｏｄｅｌｓ ｆｏｒ Ｅｖａｌｕａｔｉｎｇ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ Ｄｅｐｌｏｙｍｅｎｔ Ｓｔｒａｔｅｇｉｅｓ”，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ，Ｖｏｌ．８，Ｎｏ. ４，ｐｐ．４８４−４９７，２００８．
【非特許文献１３】Ａ．Ｍ．Ｇｅｏｆｆｒｉｏｎ，“Ｌａｇｒａｎｇｉａｎ ｒｅｌａｘａｔｉｏｎ ｆｏｒ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ”，Ｍａｔｈｅｍａｔｉｃａｌ Ｐｒｏｇｒａｍｍｉｎｇ Ｓｔｕｄｙ ２（１９７４），ｐｐ．８２−１１４
【非特許文献１４】Ｊ．Ｅ．Ｂｅａｓｌｅｙ，“Ｌａｇｒａｎｇｅａｎ ｈｅｕｒｉｓｔｉｃｓ ｆｏｒ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍｓ”，Ｔｈｅｏｒｙ ａｎｄ Ｍｅｔｈｏｄｏｌｏｇｙ ６５（３）（１９９３），ｐｐ．３８３−３９９
【非特許文献１５】Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ，Ａ ｎｏｔｅ ｏｎ ｔｗｏ ｐｒｏｂｌｅｍｓ ｉｎ ｃｏｎｎｅｘｉｏｎ ｗｉｔｈ ｇｒａｐｈｓ Ｎｕｍｅｒｉｓｃｈｅ Ｍａｔｈｅｍａｔｉｋ １（１）（１９５９）２６９−３０６．
【非特許文献１６】Ｒ．Ｅ．Ｂｅｌｌｍａｎ，Ｏｎ ａ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ，Ｑｕａｒｔｅｒｌｙ ｏｆ Ａｐｐｌｉｅｄ ｍａｔｈｅｍａｔｉｃｓ １６（１）（１９５８）８７−９０．
【非特許文献１７】Ｍ．Ｌ．Ｆｉｓｈｅｒ，Ｔｈｅ Ｌａｇｒａｎｇｉａｎ ｒｅｌａｘａｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｓｏｌｖｉｎｇ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ ｐｒｏｂｌｅｍｓ，Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ ２７（１）（１９８１）１−１８．
【非特許文献１８】Ｓ．Ｍａｒｔｅｌｌｏ，Ｐ．Ｔｏｔｈ Ｅｘａｃｔ ａｎｄ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｍａｋｅｓｐａｎ ｍｉｎｉｍｉｚａｔｉｏｎ ｏｎ ｕｎｒｅｌａｔｅｄ ｐａｒａｌｌｅｌ ｍａｃｈｉｎｅｓ，Ｄｉｓｃｒｅｔｅ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ ７５（２）（１９９７）１６９−１８８．
【非特許文献１９】Ｋ．Ｊｏｒｎｓｔｅｎ，Ｍ．Ｎａｓｂｅｒｇ，Ａ ｎｅｗ Ｌａｇｒａｎｇｉａｎ ｒｅｌａｘａｔｉｏｎ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ａｓｓｉｇｎｍｅｎｔ ｐｒｏｂｌｅｍ，Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅｒｃｈ ２７（３）（１９８６）３１３−３２３（ただし、ｏとａウムラウト付き）
【非特許文献２０】Ｒ．Ｌｉｕ，Ｉ．Ｊ．Ｗａｓｅｌｌ，Ｋ．Ｓｏｇａ，Ｒｅｌａｙ ｎｏｄｅ ｐｌａｃｅｍｅｎｔ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｄｅｐｌｏｙｅｄ ｉｎ ｔｕｎｎｅｌｓ，ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｗｉｒｅｌｅｓｓ ａｎｄ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ，Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２０１０，ｐｐ．１４４−１５０.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記ＷＳＮの設計においては、伝送遅延や伝送成功率などに関する技術的な検討と共に、設置（初期投資）費用と運用費用の総和を最小にするための方策が種々検討された。しかしながら、ＷＳＮを構築し運用する際に発生する諸費用は互いに密接に関係しており、それらの間には様々なトレードオフ関係が存在する。例えば、リレーを多く設置すると、ネットワーク内の各バッテリーの消費電力量が平準化され、バッテリー交換のための巡回間隔を長くできる傾向にある。つまり、リレー設置の初期投資費用を多く（少なく）すると、バッテリー交換のための運用費用は少なく（多く）なる。そのため、初期投資費用と運用費用の検討には多くの時間を要した。さらに、センサやリレーにおける送信電力レベル（ｔｒａｎｓｍｉｓｓｉｏｎ ｐｏｗｅｒ ｌｅｖｅｌ）（以下、ＴＰＬと記す）の設定やセンシングデータを送信するためのルート計画も、ネットワーク内の電力消費費用、バッテリー交換費用、リレー設置の初期費用などに大きく関係するはずであるが、これらの要素まで全て含めて、設置費用と運用費用の総和が最小となるようなＷＳＮを系統的に設計できる具体的な方法は開発されていなかった。
【０００８】
本発明では、上記状況に鑑みて、ＷＳＮの設置・運用に要する費用の総和を最小にすることができる、対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法を提供することを目的とする。
より具体的には、埋没費用と考えられるセンサとゲートウェイの設置費用を除いた、設置費用（リレー設置費用）と運用費用（バッテリー消費費用、バッテリー交換作業費用）の総和の最小化を図るように無線センサネットワークの設計を行うことを目的とする。
【０００９】
なお、リレーの設置計画、ＴＰＬの設定計画、センシングデータのルート計画は、鉄道構造物以外を対象とするＷＳＮの設計においても主要な課題であり、多くの場合、それらの計画がＷＳＮの効率性・経済性に大きく関係する。
このため、以下で提案するＷＳＮの設計アルゴリズムは、鉄道構造物に限らず、その他の構造物の状態監視に用いられるＷＳＮにも幅広く適用できる。
【課題を解決するための手段】
【００１０】
本発明は、上記目的を達成するために、
〔１〕対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び／又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、このバッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) を用いてセンサネットワークを設計することを特徴とする。
【００１１】
〔２〕上記〔１〕記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記対象構造物が、鉄道土木構造物であることを特徴とする。
〔３〕上記〔２〕記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記総和の最小化を行うため、リレーの設置数とその設置場所、各センサと各リレーにおける送信電力レベル、前記センサからのデータを前記ゲートウェイにマルチホップで送信するための伝送経路を同時に設定することを特徴とする。
【００１２】
〔４〕上記〔３〕記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記センサと前記ゲートウェイの設置場所と、前記リレー設置候補場所と、各種電力情報と、各種費用情報を入力情報として与え、前記リレーの設置費用と前記バッテリーの消費費用と前記バッテリーの交換作業費用との総和が最小になるような前記リレーの設置場所と、前記データの伝送経路と、前記センサと前記リレーの送信電力レベル、ならびに前記無線センサネットワーク１日あたりの費用と、ネットワーク寿命を出力し、これに基づき前記無線センサネットワークを構築することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、次のような効果を奏することができる。
（１）軍事モニタリング、フィールドモニタリング、構造物モニタリングなど活用範囲の広いセンサネットワークを構築・運用する際の費用評価が可能となることにより、センサネットワークの導入による効果と費用の関係（費用対効果）が明らかになる。
（２）総費用が少ないセンサネットワークを設計できることにより、事業者にとっても経費削減を図ることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の評価対象である鉄道土木構造物の状態監視のためのＷＳＮの模式図である。
【図２】本発明に係る鉄道土木構造物を対象とするのＷＳＮシステムの設置・運用にかかる費用の分類を示す図である。
【図３】本発明のアルゴリズムであるラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｅａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) の説明図である。
【図４】本発明に係るＷＳＮの設置及び運用費用評価方法によるＷＳＮシステム設計における入力例と出力例を示す図である。
【図５】既存ＷＳＮのネットワーク設計（ロンドン地下鉄）の説明図である。
【図６】拡張ＷＳＮのネットワーク設計（ロンドン地下鉄）の説明図である。
【図７】本発明に係るリレーからセンサへのＴＰＬの出力水準と送信可能範囲との関係を示す図である。
【図８】本発明に係るＧ＝（Ｎ，Ａ）にマルチプルアークが存在している状況を示す説明図である。
【図９】本発明にかかる（ＬＸ（ｕ, ｖ））と（ＬＹ（ｖ））に関する伝送ルートを示す図である。
【図１０】本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮ設計案（２６個のセンサ及び７０個のリレー候補場所を有する場合）を示す図である。
【図１１】本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮ設計案（５０個のセンサ及び５４個のリレー候補場所を有する場合）を示す図である。
【図１２】本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮ設計案（９６個のセンサ及び５８個のリレー候補場所を有する場合）を示す図である。
【図１３】従来のロンドン地下鉄のジュビリー線に設置されたＷＳＮを示す図である。
【発明を実施するための形態】
【００１５】
本発明の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法は、対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び／又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、このバッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) を用いてセンサネットワークを設計する。
【実施例】
【００１６】
本発明は、対象構造物の状態監視のためのＷＳＮの設置及び運用費用評価方法であるが、これは所与の条件の下、設置及び運用費用の総和が最も小さくなるようなＷＳＮを設計し、その設置・運用費用に加えてネットワーク寿命をも評価するものである。このような本発明では、設置及び運用費用の総和が最も小さくなるようなＷＳＮを設計するため、リレー設置費用とバッテリー消費費用とバッテリー交換費用の総和を最小とすることを目的とする。そのために、まず、最初に、リレーの設置数とその設置場所、各センサと各リレーにおけるＴＰＬのレベル、センシングデータをゲートウェイにマルチホップで送信するための伝送ルートを同時に計画する問題を設定する。
【００１７】
次いで、その問題を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく、その問題の近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) を用いて問題の解を得る。
本明細書では、最後に、本発明の有効性を鉄道土木構造物の状態監視における実例を用いた数値実験により検証する。
【００１８】
以下、本発明の実施の形態について詳細に説明する。
図１は本発明の評価対象である鉄道土木構造物の状態監視のためのＷＳＮの模式図である。
図１において、１は鉄道土木構造物としてのトンネル、２は軌道、３はセンサ、４はゲートウェイ、５は携帯電話網、６は管理局である。ここでは、センサ３が所定間隔でトンネル１の内壁に複数個ずつ配置されている。また、点線は、データの流れを示している。なお、ここでは、リレーが配置されていないものを示す。
【００１９】
マルチホップ無線通信により、センサ３からのセンシングデータの収集が行われ、その収集データはゲートウェイ４を介して携帯電話網５を通じて管理局６へと伝送される。センサ３としては、地下鉄においては、バッテリーで駆動される傾斜計センサや変位計センサが配置され、ゲートウェイ４はＡＣ電源で駆動される。このような構成のＷＳＮでトンネルの状態監視が行われる。
【００２０】
ここで、上記したように、ＷＳＮは複数個のセンサ３と単一のゲートウェイ４を有するが、それらの設置場所は予め決められているものとする。また、リレーを設置できる場所の候補も幾つかあり、これらの場所も予め決められているものとする。さらに、各センサ３と各リレーにおいてはデータを出力する際のＴＰＬを数段階の水準の中の１つに設定でき、各センサ３と各リレーから送信できる範囲と送信のための消費電力量は設定したＴＰＬに依存するものとする。加えて、各センサ３と各リレーの電源はそれぞれに配置されたバッテリーであり、各バッテリーは電力が枯渇したものと次の交換作業までに電力が枯渇するものを交換しなければならないものとする。
【００２１】
このような前提のもと、鉄道土木構造物の状態監視を行うためのＷＳＮとして、以下のようなシステムの構築について考える。
（１）各センサ３では単位期間毎に１回データを収集する。
（２）各センサ３で収集したデータは、マルチホップ通信でゲートウェイ４に無線伝送される。
（３）ゲートウェイ４に伝送されたデータは、携帯電話やインターネットなどの一般の通信手段を用いて管理局６の中央の管理サーバに転送される。
【００２２】
図２は本発明に係る鉄道土木構造物を対象とするＷＳＮシステムの設置・運用にかかる費用の分類を示す図である。
この図に示すように、ＷＳＮの設置及び運用にはさまざまな費用が必要であり、例えば、バッテリー消費費用、バッテリー交換作業費用、リレー設置費用、ゲートウェイ設置費用、センサ設置費用などが挙げられる。
【００２３】
これらの費用を分類すると、バッテリー消費費用、バッテリー交換作業費用は運用費用Ａであり、リレー設置費用、ゲートウェイ設置費用、センサ設置費用は、設置費用Ｂであり、運用費用Ａと設置費用Ｂの総和が全体費用Ｃである。
このように、上記ＷＳＮシステムの構築においては、まずセンサ３、ゲートウェイ４、リレーを設置するための設置費用が発生する。しかし、センサ３とゲートウェイ４の設置場所は上記したように予め定められていることから、それらの設置費用は埋没費用（ｓｕｎｋ ｃｏｓｔ）であると見なすことができる。そこで、本発明においてはシステム構築の設置費用としては残りのリレー設置費用だけを考慮することにする。また、このシステムの運用においては、システム内の各センサと各リレーのバッテリーを保守作業員が現場を巡回して交換する必要がある。つまり、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーを保守作業員が現場を巡回して交換する必要がある。よって、システムの運用段階においてはバッテリー交換のための作業費用が発生する。加えて、システムの運用段階においては、当然のことながら、各バッテリーの電力消費費用についても考慮する必要がある。したがって、このシステムの構築段階においてはリレー設置費用が、そして運用段階においてはバッテリー消費費用とバッテリー交換作業費用が発生することになる。
【００２４】
なお、各センサに設けられる無線通信機器では、３５Ａｈ、３．６Ｖのバッテリーを使用しているが、バッテリー寿命は約１年半である。一方、傾斜計は無線通信機器とは異なる２．４Ａｈ、３．６Ｖのバッテリーを２個使用しており、そのバッテリー寿命は約１年である。変位計は無線通信機器のバッテリーより電源が供給される。変位計ノードの寿命は約１年である。
ノード障害は、突発的である一方、バッテリーの枯渇は定期的に発生する。また、ノード復旧よりもバッテリー交換の方が高コストであるので、ＷＳＮを長期間運用するためにも、効率的にバッテリーを利用する必要がある。したがって、最適化技術を活用して効率的にＷＳＮを設計する。
【００２５】
そこで、本発明の問題の設定としては、運用費用Ａ（バッテリー消費費用、バッテリー交換作業費用）と設置費用Ｂ（リレー設置費用）の総和が最小となるように、リレーの設置数とその設置場所、各センサと各リレーのＴＰＬの水準、各センシングデータの送信経路を決定する。すなわち、リレーをそれらを設置可能な場所の中のどこにいくつ配置するかを決定する問題と、各センサと各リレーでのＴＰＬの水準を決定する問題と、各センサで収集したデータをゲートウェイに送信するためのルートを決定する問題である。これら３つの問題は先に示した３つの費用すべてに関係している。つまり、これら３つの問題は互に密接に関係しており、各問題を個別に解いても総費用の最小化を保証することはできない。そこで本発明では、リレー設置費用とバッテリー消費費用とバッテリー交換作業費用の総和が最小となるように、これら３つの問題を同時に解くようにする。
【００２６】
図３は本発明のアルゴリズムであるラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) の説明図であり、図３（ａ）はそのラグランジアン・ヒューリスティック法の実行フローチャート、図３（ｂ）はアルゴリズムの繰り返し回数に対する目的関数値を示す図、図３（ｃ）は最適解の存在範囲を示す模式図である。
【００２７】
本発明では、上記した問題を解くため、以下のようなアルゴリズムを用いる。
図３（ａ）に示すように、まず、初期解と初期ラグランジュ乗数の決定を行う（ステップＳ１）。次に、ラグランジュ緩和問題を利用した下界値の生成を行う（ステップＳ２）。次に、ラグランジュ乗数を利用した上界値の生成を行う（ステップＳ３）。終了条件（ステップＳ４）を満足しなければ、ラグランジュ乗数の更新を行い（ステップＳ５）、ステップＳ２へ戻り、終了条件（ステップＳ４）を満足したら、アルゴリズムの繰り返しを停止する（ステップＳ６）。
【００２８】
つまり、図３（ｂ）に示すように、上界値と下界値の情報を利用して最適解に近い解を求める。ここで、上界値はアルゴリズムが出力した解、下界値は最適値以下であることが理論的に保証された値であり、図３（ｃ）の下段に示すように、上界値と下界値の間の最適値の存在範囲が狭まるようにすることが望ましい。
【００２９】
図４は本発明に係るＷＳＮの設置及び運用費用評価方法によるＷＳＮシステム設計における入力例と出力例を示す図であり、図４（ａ）はその入力例を示す図、図４（ｂ）はその出力例を示す図である。
本発明に係るＷＳＮの設置及び運用費用評価方法においては、図４（ａ）に示すように、センサの配置場所、ゲートウェイの設置場所、リレーの設置候補場所、各電力（送信・受信・センシング）、各費用（リレー設置、バッテリー消費、バッテリー交換作業）を評価条件として入力すると、この入力条件にしたがって、図４（ｂ）に示すように、リレーの設置場所、各センシングデータの伝送経路、各センサと各リレーのＴＰＬの水準、ネットワーク寿命、ＷＳＮの単位期間あたりの費用が出力される。
【００３０】
図５は既存ＷＳＮのネットワーク設計（ロンドン地下鉄）の説明図である。図５（ａ）は現在のＷＳＮ（図１３と対応）であり、横軸がリングの位置、縦軸はセグメントＡ〜Ｍを示しており、図５（ｂ）は現在のＷＳＮの条件の下、本発明の評価方法により提案されるＷＳＮであり、横軸はトンネルリングの位置、縦軸はセグメントＡ〜Ｍを示している。なお、図中のひし形及び丸はセンサの位置、四角はゲートウェイの位置を示している。また、図５（ａ）の横軸の数字はリング番号を示しており、１６４０は０ｍ、１６５０は６．６ｍ、１６６０は１２．６ｍ、１６７０は１８．６ｍ、１６８０は２４．６ｍ、１６９０は３０．６ｍ、１７００は３６．６ｍ、１７１０は４２．６ｍ、１７２０は４８．６ｍにそれぞれ対応しており、リング番号が示される他の図でも同様である。
図５（ａ）の現在のＷＳＮでは、一日あたりの全体の費用は１５６０円であり、ネットワーク寿命が１２３日であるのに対して、図５（ｂ）の本発明による評価に基づくＷＳＮでは、一日あたりの全体の費用は１３４９円となり、ネットワーク寿命も２１９日となった。このように、本発明によれば、１５％の費用低減を達成し、ネットワーク寿命を７８％延ばすことができた（後出の表１参照）。
【００３１】
図６は拡張ＷＳＮのネットワーク設計（ロンドン地下鉄）の説明図である。図６（ａ）はリレー設置、ＴＰＬ水準調整なしの場合であり、横軸がリングの位置、縦軸はセグメントＡ〜Ｍを示しており、図６（ｂ）はリレー設置、ＴＰＬ水準調整ありの場合であり、横軸はリングの位置、縦軸はセグメントＡ〜Ｍを示している。なお、図中のひし形及び丸はセンサの位置、四角はゲートウェイの位置を示しており、図６（ｂ）の三角はリレーの位置を示している。図６（ａ）では、一日あたりの全体の費用は８５８４円であり、ネットワーク寿命が６９日であるのに対し、図６（ｂ）では、一日あたりの全体の費用は８２３０円となり、ネットワーク寿命は９８日となった。このように本発明によれば、４．３％の費用低減を達成し、ネットワーク寿命を４２％延ばすことができた（後出の表２参照）。
【００３２】
上記したように本発明によれば、鉄道土木構造物の状態監視に用いる無線センサネットワークを、総費用が最小になるように設計できた。すなわち、本発明では最初にリレーの設置数とその設置場所、各センサーと各リレーにおける送信電力レベル、センシングデータをゲートウェイにマルチホップで送信するためのルートを同時に計画する問題を設定し、次いで、その問題を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法に基づくその問題の近似最適解法により解くことで設置及び運用費用の評価を行った。そして最後にその有効性を鉄道土木構造物の状態監視に用いる無線センサネットワークの実例を用いた数値実験により検証した。
【００３３】
以下、より具体的に本発明の実施例を示す鉄道土木構造物の状態監視に用いるＷＳＮ（無線センサネットワーク）の設置及び運用費用評価方法について説明する。
既述のように、各センサや各リレーから送信できる範囲と送信のためのバッテリー消費量は、各センサや各リレーで設定するＴＰＬの出力水準に依存する。
【００３４】
図７は本発明に係るリレーからセンサへのＴＰＬの出力水準と送信可能範囲との関係を示す図である。
リレーからセンサへのＴＰＬの出力水準ごとの送信可能範囲は図７に示すようになる。ただし、図７に関しては以下の通りである。
（１）円はセンサ、三角はリレー、四角はゲートウェイで、円と三角内の数字はそれぞれセンサ番号、リレー番号である。
（２）各センサと各リレーではＴＰＬを１、２、３の何れかに設定でき、ＴＰＬ１が最小送信出力、ＴＰＬ３が最大送信出力、ＴＰＬ２がその中間の送信出力である。
（３）リレー６を設置した場合に、それからＴＰＬ１、２、３で送信できる範囲を、それぞれａ、ｂ、ｃの点線で示している。
（４）リレー６からＴＰＬ１、２、３で送信できる箇所を、それぞれｄ、ｅ、ｆの矢印で示している。
【００３５】
この例においては、リレー６からセンサ２へ送信できるのはＴＰＬ３の場合だけである。よって、リレー６からセンサ２へ送信するには、リレー６のＴＰＬを３に設定しなければならないことになる。また、リレー６からセンサ４へは、リレー６のＴＰＬを１、２、３の中の何れに設定しても送信できるが、リレー６からセンサ１へは最大送信出力のＴＰＬ３でも送信できないことを示している。
【００３６】
なお、本発明では、さらに以下を仮定する。
（ｉ）１つのセンサで収集したデータは１つにまとめ、それを途中の中継点で分割することなくゲートウェイに伝送するものとする。
（ｉｉ）ネットワーク内に設置する各リレーはすべて同一のものであるとする。
（ｉｉｉ)鉄道土木構造物の状態監視において設置するセンサは、リレーにデータ収集機能を付加したものである場合が多い。つまり、センサも中継機能を持ち、センサとリレーの機能はデータ収集機能を除けば同一である場合が多い。そこで、各センサと各リレーにおけるＴＰＬの水準数（図７の場合は３）は全て同一であるとする。
【００３７】
（ｉｖ）バッテリー交換作業において交換するバッテリーは、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーだけで、次の巡回まで寿命のあるバッテリーは交換しないで良いものとする。つまり、システム内のあるバッテリーの寿命（交換してから電力が枯渇するまでの期間）がネットワーク寿命のθ（＞１）倍以上でかつ（θ＋１）倍未満である場合は、そのバッテリーはθ回の巡回に一度の割合で交換すれば良いものとする。
【００３８】
次に、本発明と関連する研究について説明する。
センサネットワークの長寿命化に関してはこれまでに多くの研究がなされている。例えば、Ａｌｆｉｅｒｉら（上記非特許文献３参照）は与えられたセンサを分割して複数の部分センサネットワークを構成し、それらの運用時間帯を調整することによりネットワーク寿命を長期化する手法を提案している。また、Ｔａｎｇら（上記非特許文献４参照）は伝送データの信頼性を考慮して、Ｋｉｍら（上記非特許文献５参照）はセンシングデータの伝送遅延を考慮してネットワーク寿命を最大化する方法を提案している。しかしながら、これらの研究においては、ネットワーク内の総消費電力量について考慮していない。つまり、ネットワーク寿命と総消費電力量はトレードオフの関係にあることから、ネットワーク寿命について考える場合は同時に総消費電力量についても考慮すべきであるが、これらの研究においてはそれを明白には考慮していない。
【００３９】
センサネットワーク内のリレー配置問題に関しても多くの研究がある。例えば、Ｈｏｕら（上記非特許文献６参照）はリレーの配置問題とゲートウェイやリレーへの電力の割当問題を同時に解く方法を提案している。また、Ｌｌｏｙｄら（上記非特許文献７参照）はセンサ間の通信を確保するために必要な最小のリレー数を求める問題を取り上げ、この問題に対する近似アルゴリズム（ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ）を提案している。Ｈａｏら（上記非特許文献８参照）は、各センサ間に少なくとも２本のルートが存在するような故障に強いネットワークトポロジー（ｆａｕｌｔ−ｔｏｌｅｒａｎｔ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｙ）を構築するためのリレー配置問題を取り上げ、この問題に対する多項式時間近似アルゴリズム（ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ）を提案している。しかし、これらの研究においては送信範囲や電力消費に大きく関係するＴＰＬの調整について考慮していない。他方、Ｃｏｒｒｅｉａら（上記非特許文献９参照）は通信と消費電力量を考慮してＴＰＬを決定する方法を提案している。しかし、彼らの研究においてはリレー配置を考慮していない。また、彼らの研究においてはネットワーク寿命についても考慮していない。
【００４０】
ＷＳＮの構築費用を考慮したモデルも提案されている。Ｋａｔｅｎｋａら（上記非特許文献１０参照）は平面上にセンサを配置する際に、配置するセンサ数と各センサに付随するコストを最小化する問題を取り上げている。Ｍｈａｔｒｅら（上記非特許文献１１参照）は通信と拘束有効範囲（ｃｏｖｅｒａｇｅ ｃｏｎｓｔｒａｉｎｔｓ）を考慮して、ノード設置費用とバッテリー設置費用の総和を最小化する問題に取り組んでいる。また、Ｃｈｅｎｇら（上記非特許文献１２参照）はＷＳＮ設置に必要なコストを、複数のＷＳＮ設置戦略を適用した場合の様々なシナリオにおいて算出・比較している。しかしながら、これらの研究においてはＷＳＮの運用費用について考慮していない。つまり、ＷＳＮを構築し運用する際に発生する総費用を最小にするためには、ＷＳＮの設置費用に加えてその運用費用につても考慮しなければならないが、これらの研究ではそれについて明白には触れていない。
【００４１】
既述のように、リレーの設置計画、ＴＰＬの設定計画、センシングデータのルート計画は互に密接に関係しており、それらを個別に計画しても総費用の最小化を保証することはできない。それゆえ、総費用が最小となるようにそれらを同時に計画する問題は、ＷＳＮの設計においても、そしてその運用においても極めて重要であると思われる。しかしながら、上で見たように、そのような問題は未だ取り扱われていない。
【００４２】
以下、本発明にかかるＷＳＮの設置及び運用費用評価方法のアルゴリズムについて詳述する。
まず、定式化（Ｆｏｒｍｕｌａｔｉｏｎ）を行う。
ここでは、センサの集合をＳ＝｛１，２, …, ｜Ｓ｜｝、リレー設置候補場所の集合をＲ＝｛｜Ｓ｜＋１, ｜Ｓ｜＋２, …, ｜Ｓ｜＋｜Ｒ｜｝とする。また、ゲートウェイを０で表し、各センサで収集したデータはマルチホップ通信でそこに伝送するものとする。また、Ｍ＝Ｓ∪Ｒ∪、Ｎ＝Ｓ∪Ｒ∪｛０｝とおき、ＭやＮについて考える場合はそれらの要素を特にノードと呼ぶ。また、各バッテリーで消費可能な最大電力量をバッテリー容量と呼び、ノードｉ∈Ｍのバッテリー容量をＥi とする。加えて、各センサと各リレーにおけるＴＰＬの集合をＰ＝｛１，２, …, ｜Ｐ｜｝とし、一般性を失うことなく、送信出力は１＜２＜…＜｜Ｐ｜の順序で大きくなるものとする。つまり、ＴＰＬ１が最小送信出力で、ＴＰＬ｜Ｐ｜が最大送信出力であるものとする。
【００４３】
ここで、伝送ルートとＴＰＬについて説明する。
あるノードｉ∈Ｍとあるノードｊ∈Ｎを考えると、ノードｉからノードｊへ（他のノードを経由しないで）直接送信できるノードｉにおけるＴＰＬの集合が定まる。そこで、
Ｐij：ノードｉ∈Ｍからノードｊ∈Ｎへ直接送信できる、ノードｉにおけるＴＰＬのｌ∈Ｐの集合
【００４４】
と定義する。そして、このＡをアーク集合とし、Ｎをノード集合とする有向グラフをＧ＝（Ｎ，Ａ）とする。ここで、｜Ｐij｜＞２である場合は、Ｇにはノードｉからノードｊへの｜Ｐij｜本のマルチプルアーク（ｍｕｌｔｉｐｌｅ ａｒｃ）が存在することに注意する。Ｇにマルチプルアークが存在する状況を図示すると図８のようになる。ただし、図８に関しては以下の通りであり、円形、三角、四角の意味は図７と同じである。
（１）図７のノード間に存在する全てのアークを図示した場合の例である。
（２）ｄ，ｅ，ｆのアークは、図７の場合と同様に、それぞれＴＰＬ１、２、３で送信できることを示している。
（３）双方向アークは、その両端のノードは相互に送信可能であることを示している。
【００４５】
この例においては、幾つかのノード間にマルチプルアークが存在する。例えば、ノード６からノード５へは２本のアーク（６，５，２）、（６，５，３）つまり、ノード６からノード５へＴＰＬ２で送信するアークと、ノード６からノード５へＴＰＬ３で送信するアークが、逆にノード５からノード６へも２本のアーク（５，６，２）、（５，６，３）が存在する。また、ノード６からノード０へは２本のアーク、（６，０，２）、（６，０，３）が存在する。なお、ノード０はゲートウェイであり、ゲートウェイは受信だけであるから、ノード０へのアークは全て片方向であることに注意。
【００４６】
あるセンサｉ∈Ｓを始ノードとし、ゲートウェイ０を終ノードとするＧ＝（Ｎ，Ａ）上のルートを特に伝送ルートと呼び、それをアークの集合で示す。このとき、Ｇにあるセンサを始ノードとする伝送ルートが存在しなければ、リレーをどのように配置しても、そのセンサからはゲートウェイにデータを送信することができない。そこで、Ｇには各センサを始ノードとする伝送ルートが少なくとも１本は存在するものとする。また以下では、Ｇにおけるノードｉ∈Ｍの入次数と出次数は共に１以上であると仮定する。つまり、ノードｉ∈Ｍは少なくとも他の１つのノードから受信可能で、かつ少なくとも他の１つのノードへ（あるＴＰＬで）送信可能であると仮定する。
【００４７】
と定義する。そして、この（ｘk ijl ）と（ｙil）をそれらに対応したルート案が実行可能であるように定めた場合について考える。つまり、それらを次のように定めた場合について考える。
【００４８】
（ｉ) 各ｋ∈Ｓについて｛（ｉ, ｊ, ｌ）∈Ａ｜ｘk ijl ＝１｝はノードｋからノード０へのルートである。すなわち、各センサを始ノードとする｜Ｓ｜個の伝送ルートが生成されている。
（ｉｉ) あるｘk ijl が１ならばｙil＝１である。すなわち、ある伝送ルートにアーク（ｉ, ｊ, ｌ）が含まれている場合は、ノードｉのＴＰＬがｌに設定されている。
（ｉｉｉ)あるｙilが１ならばｙil´＝０, ｌ´∈Ｐ＼｛ｌ｝である。すなわち、各ノードにおいてはＴＰＬが同時に２つ以上の水準に設定されていない。
【００４９】
次に、バッテリー交換作業費用について説明する。
各センサでは単位期間に１回データを収集し、それを処理後ゲートウェイへ伝送する。そこで、各センサで単位期間に収集するすべてのデータを、収集・処理し、受信し、送信するのに必要な電力量を次のように記す。
ｓk ：センサｋ∈Ｓでデータを収集・処理するのに必要な電力量
ｒk ：センサｋ∈Ｓで収集したデータを各ノードで受信するのに必要な電力量
ｔk l ：センサで収集したデータを各ノードからＴＰＬｌ∈Ｐで送信するのに必要な電力量
このとき、ノードｉ∈Ｍで単位期間に必要な電力量Ｆi （ｘ）は次のようになる。ただし、ｅi はｉ∈Ｓである場合はｅi ＝ｓi であり、ｉ∈Ｒである場合はｅi ＝０であるものとする。
【００５０】
【数１】
【００５１】
ここで、式 (１) の右辺第１項はデータの送信に、第２項はデータの受信に、そして第３項はセンサでデータを収集・処理するのに必要な電力量である。
上記式（１）によって各ノードで単位期間に必要な電力量が定まれば、その電力量と各ノードのバッテリー容量よりネットワーク寿命が定まる。つまり、ネットワーク寿命をｄ（ｘ）とすると、それはバッテリー容量Ｅi と式 (１) より次で定まる。
【００５２】
【数２】
【００５３】
加えて、１回当りのバッテリー交換作業費用をｃ1 、１Ｊ当りのバッテリー消費費用をｃ2 、リレーを１個設置した場合の単位期間当りの費用をｃ3 とする。ここで、容量がＥi Ｊであるバッテリーの価格がａi である場合はｃ2 ＝ａi ／Ｅi , ｉ∈Ｍと算出され（各バッテリーにおける１Ｊ当りのバッテリー消費費用は全て同一であるとしていることに注意）、リレー１個当たりの設置費用がｂで各リレーの使用可能期間がＴ期間である場合はｃ3 ＝ｂ／Ｔと算出される。また、１回当りのバッテリー交換作業費用がｃ1 で、ネットワーク寿命がｄ（ｘ）期間ならば、単位期間当りのバッテリー交換作業費用は（ｃ1 ／ｄ（ｘ））となる。つまり、式 (２) より
【００５４】
【数３】
【００５５】
であるから、単位期間当りのバッテリー交換作業費用は、次のようになる。
【数４】
【００５６】
定式化の準備の最後に、電力消費費用について説明する。
本発明においては、バッテリー交換作業において交換するバッテリーは、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーだけで、次の巡回まで寿命のあるバッテリーは交換しないで良いものとした。
【００５７】
となる。しかしながら、上式はかなり煩雑でこのままでは取り扱いが困難である。そこで、ここでは、式 (５) のフロア関数を緩和し、式 (５) の分母は
〔Ｅi ／Ｆi （ｘ）〕・〔１／ｄ（ｘ）〕・ｄｘ
であるものと近似する。すると、ノードｉ∈Ｍのバッテリーの単位期間当たりの電力消費費用は、
【００５８】
【数５】
となる。つまり、ノードｉ∈Ｍのバッテリーの単位期間当たりの電力消費費用はｃ2 ・Ｆi （ｘ）となる。
【００５９】
このとき、さらに変数ｚを導入すると、単位期間当たりの総費用が最小となるようにＷＳＮを設計する問題は、次のような混合整数計画問題（ｍｉｘｅｄ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ ｐｒｏｂｌｅｍ）に定式化される。
【００６０】
【００６１】
ｘk ijl ≦ｙil, （ｉ, ｊ, ｌ）∈Ａ，ｋ∈Ｓ …（１１）
【数６】
ｘk ijl ∈｛０，１｝, ｛ｉ, ｊ, ｌ｝∈Ａ，ｋ∈Ｓ …（１３）
ｙil∈｛０，１｝, ｉ∈Ｍ，ｌ∈Ｐ …（１４）
【００６２】
ここで、目的関数である式（７）の第１項はバッテリー交換作業費用、第２項はネットワーク内の総バッテリー消費費用、第３項はリレー設置費用である。また式 (８) は、目的関数の第１項は式 (４) の右辺と等価であることを保証する。また、式 (９) と式 (１０) は前述の（ｉ) を、式 (１１) は前述の（ｉｉ) を、そして式 (１２) は前述の（ｉｉｉ) を保証する。〔（ｉ）〜（ｉｉｉ)については、伝送ルートとＴＰＬの定式化の説明部分を参照〕。なお、ノードｉ∈Ｒには、それが生成された何れかの伝送ルートに含まれている場合に限りリレーを設置することになる。また、式 (３) よりｚの最小化はネットワーク寿命ｄ（ｘ）の最大化と等価である。よって、上述の問題 (Ｐ) はｃ1 ＝１としｃ2 ＝ｃ3 ＝０とすればネットワーク寿命を最長化する問題となる。また、ｃ2 ＝１、ｃ1 ＝ｃ3 ＝０とし、そしてバッテリー容量Ｅi ＝∞, ｉ∈Ｍとすれば、問題 (Ｐ) はネットワーク内の総電力使用量を最小化する問題となる。
【００６３】
上記問題 (Ｐ) は明らかにＮＰ困難な問題であり、実際問題の多くは、その最適解を求めるのは困難であると思われる。それゆえ、実際問題に対しては、メタヒューリスティックス（ｍｅｔａｈｅｕｒｉｓｔｉｃｓ）や欲張りアルゴリズム（ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ）などの近似解法が必要となるが、それらの近似解法では求めた解が最適解にどれだけ近似しているかを評価できない場合が多い。つまり、それらの近似解法では下界値を算出していないため、多くの場合、求めた解を相対誤差（（上界値−下界値）／下界値）で評価することができない。これに対して、求めた解を相対誤差で評価できる方法に、ラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）がある。この方法は、上界値と下界値の差を順次減少させながら対象問題の近似最適解を求める方法であり、実際規模の問題にも適用可能である。また、この方法によればラグランジュ緩和問題（Ｌａｇｒａｎｇｉａｎ ｒｅｌａｘａｔｉｏｎ ｐｒｏｂｌｅｍ）の最適解を利用して対象問題の近似解を効率的に探索することができる。そこで以下では、このラグランジアン・ヒューリスティック法に基づく問題 (Ｐ) の近似最適解法（求めた解を相対誤差で評価できる解法）について考える。
【００６４】
ラグランジアン・ヒューリスティック法は、概略、次のような手順を繰り返し実行して、原問題の近似最適解（ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ）を求める方法である。ただし、原問題は最小化問題とする。
【００６５】
〔手順１〕
Ｓ１．原問題のラグランジュ緩和問題を解いて、原問題の下界値を求める。
Ｓ２．ラグランジュ緩和問題の最適解を利用して、原問題の可能解とその目的関数値（上界値）を求める。
Ｓ３．上界値と下界値を用いて相対誤差を算出する。相対誤差あるいは計算時間が所与の終了条件を満たしたならば計算を終了する。
Ｓ４．ラグランジュ乗数（Ｌａｇｒａｎｇｉａｎ ｍｕｌｔｉｐｌｉｅｒｓ）を適切な方法で更新して、Ｓ１に戻る。
【００６６】
したがって、上記Ｓ１、Ｓ２、Ｓ４を実行する具体的な方法を示せば、問題 (Ｐ) のラグランジアン・ヒューリスティック法に基づく近似最適解法が構築される。そこで以下では、上記Ｓ１、Ｓ２、Ｓ４を実行する方法について順次説明する。
まず、下界値の決定について説明する。
ここでは、上記手順１のＳ１に示した、ラグランジュ緩和問題を解いて問題 (Ｐ) の下界値を生成する方法について説明する。
【００６７】
ラグランジュ乗数ｕ＝（ｕi ）＞０, ｉ∈Ｍを用いて式 (８) を、ラグランジュ乗数ｖ＝（ｖk ijl ）＞０, （ｉ, ｊ, ｌ）∈Ａ, ｋ∈Ｓ を用いて式 (１１) を、問題 (Ｐ) の目的関数に組み込み、それを整理すると次のようになる。
【００６８】
【数７】
【００６９】
よって、上式の変数（ｘk ijl ）との（ｙil）に注目して、
【００７０】
とおくと、次のような問題 (Ｐ) のラグランジュ緩和問題を得る。
【数８】
【００７１】
ここで、問題（・）の最適値をｃ（・）で記すと、ラグランジュ緩和法の原理よりｃ（Ｌ（ｕ, ｖ））＜ｃ（Ｐ）が成り立つ（上記非特許文献１３，１４参照）。つまり、問題（Ｌ（ｕ, ｖ））の最適値が問題 (Ｐ) の下界値を与える。
ところで、問題（Ｌ（ｕ, ｖ））の変数ｚには非負条件が付いていない。それゆえ、最小化問題（Ｌ（ｕ, ｖ））においては、目的関数におけるｚの係数が正の場合にはｚ＝−∞とし、それが負の場合にはｚ＝＋∞とすると、問題ｃ〔Ｌ（ｕ, ｖ）〕の目的関数値＝−∞となる。つまり、ｚの係数が非ゼロの場合は、問題 (Ｐ) の有意な下界値を得ることができない。そこで以下では、（ｕi ）は
【００７２】
【数９】
【００７３】
である場合に限定する。式 (１７) より（Ｌ（ｕ, ｖ））の目的関数の第１項は消える。よって、問題は（Ｌ（ｕ, ｖ））は、（ｘk ijl ）に関する
【００７４】
となる。ここで、（ＬＸ（ｕ, ｖ））におけるｋ∈Ｓをあるｋに固定した場合の問題を（ＬＸk （ｕ, ｖ））とすると、（ＬＸ（ｕ, ｖ））はさらに｜Ｓ｜個の問題（ＬＸk （ｕ, ｖ））, ｋ∈Ｓに分解される。そして、各（ＬＸk （ｕ, ｖ））は明らかにノードｋからノード０への最短ルート問題である。他方、（ＬＹ（ｖ））におけるｉ∈Ｍをあるｉに固定した場合の問題を（ＬＹi （ｖ））とすると、問題（ＬＹ（ｖ））もさらに｜Ｍ｜個の問題（ＬＹi （ｖ））, ｉ∈Ｍに分解され、そして各（ＬＹi （ｖ））は明らかに自明な問題である。よって、ラグランジュ緩和問題の（Ｌ（ｕ, ｖ））最適値は、つまり問題 (Ｐ) の下界値は、｜Ｓ｜個の最短ルート問題と｜Ｍ｜個の自明な問題を解くと
【００７５】
【数１０】
で求めることができる。ここで、最短ルート問題については、その最適解を多項式時間で求めるアルゴリズムが既に数多く提示されている（上記非特許文献１５，１６参照）。
【００７６】
次に、手順１のＳ２に示した、上界値（可能解）の決定について説明する。
ここでは、ラグランジュ緩和問題（ＬＸ（ｕ, ｖ））の最適解を利用して、問題 (Ｐ) の可能解を求める方法について説明する。
【００７７】
【００７８】
である。ただし、βはＢ（ｉ）, ｉ∈Ｍの和集合である。例えば、図９の場合は、Ｂ（２）＝｛（２，５）, （２，６）｝, Ｂ（４）＝｛（４，０）｝、Ｓ（２，５）＝｛１｝, Ｓ（４，０）＝｛２，４｝などのようになる。
【００７９】
そこで、以下の手順で可能解を決定する。
【００８０】
【００８１】
【００８２】
【００８３】
そこで、以下の手順で可能解を改善する。
【００８４】
次に、手順１のＳ４に示した、ラグランジュ乗数の更新について説明する。
問題（Ｐ）の下界値ｃ〔Ｌ（ｕ, ｖ）〕は、当然のことながら、ラグランジュ乗数ｕ＝（ｕi ）、ｖ＝（ｖk ijl ）に依存する。それゆえ、問題 (Ｐ) のよりよい下界値を求めるためにはｃ〔Ｌ（ｕ, ｖ）〕が最大となるようなｕ, ｖを求めることが望まれる。他方、そのようなラグランジュ乗数を漸近的に求める方法によく知られた劣勾配法がある（上記非特許文献１７参照）。この方法は、これまでに種々の組合せ最適化問題に適用され、その有効性が多くの研究で検証されている（上記非特許文献１８、１９参照）。そこでここでは、この劣勾配法でｃ〔Ｌ（ｕ, ｖ）〕が最大となるようなラグランジュ乗数を漸近的に求めるものとする。すなわち、次の手順でラグランジュ乗数ｕ, ｖを逐次更新するものとする。
【００８５】
【００８６】
そこで、以下の手順でラグランジュ乗数の設定を行う。
Ｓ４−１．ｃ（Ｌ（ｕ, ｖ））の（ｕi ）, （ｖk ijl ）における劣勾配（λi ）, （μk ijl ）を次で定める。
【００８７】
Ｓ４−２．ステップレングスρ, σを次で定める。
【００８８】
Ｓ４−３．乗数（ｕi ）, （ｖk ijl ）を次で更新する。
ｕi ：＝ｍａｘ｛０, ｕi ＋ρλi ｝, ｉ∈Ｍ
ｖk ijl ：＝ｍａｘ｛０, ｖk ijl ＋σμk ijl ｝, （ｉ, ｊ, ｌ）∈Ａ, ｋ∈Ｓ
【００８９】
Ｓ４−４．乗数（ｕi ）を次で調整する。
【数１１】
【００９０】
なお、この手順のＳ４−４は、（ｕi ）が式 (１７) を満たすように調整するためのものである。また、劣勾配法においては、多くの場合、ステップレングスをρ＝σとする。そして、それを次のように定める場合が多い。
【００９１】
【数１２】
【００９２】
しかし、ステップレングスを上式で定めると、（μk ijl ）に比して（λi ）がステップレングスの値の決定により強く反映してしまう懸念がある。つまり、Ｓ１における劣勾配法の決定方法より−１＜μk ijl ＜１であるから、λi ≫１である場合には、（μk ijl ）に対して（λi ）だけがステップレングスの決定により大きく反映してしまう懸念がある。そこで本発明では、ステップレングスρとσをＳ２で別々に定めるものとする。したがって、ここでの劣勾配法は正確には修正劣勾配法である。
以上のようなアルゴリズムで、ＷＳＮの設置及び運用費用の評価を行う。
【００９３】
上記してきた本発明にかかるＷＳＮの設置及び運用費用の評価方法の有効性を検証するための、実例を用いた計算実験を以下に示す。
上記したように、ロンドン地下鉄のジュビリー線には、トンネル内の状態監視のためのＷＳＮが既に設置されている。そこでここでは、既設のＷＳＮの条件の下、本発明のＷＳＮの設置及び運用費用の評価方法で設計した場合のＷＳＮ案を作成し、それと現在のＷＳＮとの比較検証を行う。また、ロンドン地下鉄のＷＳＮに設置するセンサ数を、現在よりも増やした場合（図６に示した拡張ＷＳＮと対応）に、総費用がどのように変化するかを検証するための計算実験も行う。なお、ロンドン地下鉄の現在のＷＳＮには、２６個のセンサ（傾斜計６台、クラックメータ１６台、環境センサ４台）と１台のゲートウェイが設置されている（図１３参照）。
【００９４】
以下の計算実験においては、データの送信・受信電力と他の各費用に関する電力消費パラメータを次のように定めた。
・各センサでは５秒に１回データを取得するものとした。つまり、各センサの単位期間は５秒とした。
・各センサでデータを収集・処理するのに必要な電流値、電圧値、収集・処理時間は全て同一で、それぞれ７ｍＡ、３Ｖ、０．２５秒であるとした。つまりｓk ＝５．２５×１０-3 (Ｊ) , ｋ∈Ｓとした。
・各センサで収集したデータを受信するのに必要な電流値、電圧値、受信時間は各センサとリレーで全て同一で、それぞれ１９．７ｍＡ、３Ｖ、０．５秒であるとした。つまりｒk ＝２９．５５×１０-3 (Ｊ) , ｋ∈Ｓとした。
・ＴＰＬは１ (−２５ｄＢｍ）、２ (−１０ｄＢｍ) 、３ (０ｄＢｍ）の３水準とし、それぞれの電流値は４ｍＡ、１１ｍＡ、１７．４ｍＡであるとした。また、各センサで収集したデータを送信するのに必要な電圧値、送信時間は各センサとリレーで全て同一で、それぞれ３Ｖ、０．５秒であるとした。つまり、各ｋ∈Ｓについてｔ1 k ＝６．０×１０-3(Ｊ) 、ｔ2 k ＝１６．５×１０-3 (Ｊ) 、ｔ3 k ＝２６．１×１０-3 (Ｊ) とした。
・１回当たりのバッテリー交換作業費用ｃ1 は、各問題例のセンサ数に応じて個別に定めた。
・各センサと各リレーでは５０Ａｈ、３Ｖのバッテリーを使用するものとし、その価格は２００（£) であるとした。つまり、Ｅi ＝５．４×１０5 （Ｊ）, ｉ∈Ｍとしｃ2 ＝３．７×１０-4 (£／Ｊ) とした。
・リレーの設置費用は１台当たり４００（£) とし、各リレーの使用可能期間は１０年とした。つまり、ｃ3 ＝６．３４×１０-6 (£／ｕｎｉｔ ｐｅｒｉｏｄ) とした。
【００９５】
また、以下での計算実験は全て次のような環境の下で実施した。
・ロンドン地下鉄のジュビリー線のトンネルに関しては、各ＴＰＬで与えられたノード間の無線通信が可能かを判定できる経験モデル（ｅｍｐｉｒｉｃａｌ ｍｏｄｅｌ）（上記非特許文献２０参照）が既に提示されている。そこで、ノードｉからノードｊへ送信できる（ノードｉにおける）ＴＰＬの集合Ｐijは、それを用いて定めた。
・ゲートウェイは現在のロンドン地下鉄と同じ位置に設置されているものとした。つまり、ゲートウェイは全て図１３におけるトンネルの一端から２７．６ｍ離れた位置のリングのセグメントＢに設置されているものとした。
・ラグランジュ乗数の初期値はｕi ＝１／｜Ｍ｜, ｉ∈Ｍとし、ｖijl k ＝１／（｜Ａ｜×｜Ｓ｜）, （ｉ, ｊ, ｌ）∈Ａ, ｋ∈Ｓとした。
・本発明のアルゴリズムの終了条件は計算時間（ｓｅｃｏｎｄ）の最大許容値とし、各計算実験の計算時間はその実験における問題例のセンサ数に応じて定めた。
・使用計算機言語はＣ言語で、使用計算機の仕様はＷｉｎｄｏｗｓ ＸＰ(登録商標）、３．６ＧＨｚ、２．９９ＧＢ ＲＡＭである。
【００９６】
なお、ロンドン地下鉄のＷＳＮにおいては、現在、リレーを使用していない。また、ＴＰＬの調整については未だ検討段階であり、現在、通信の確保を優先して各センサのＴＰＬは全て最大送信出力の３（０ｄＢｍ）に固定して通信を行っている。そこで、リレーを設置すべきかどうかの検証と、ＴＰＬを調整した場合の効果を検証するために、先ず次のような場合について実験を行った。
【００９７】
(１) リレーは設置しない。各ノードのＴＰＬは全て水準３に固定。
(２) リレーは設置しない。各ノードのＴＰＬは調整可能。
(３) リレーの設置を検討。各ノードのＴＰＬは全て水準３に固定。
(４) リレーの設置を検討。各ノードのＴＰＬは調整可能。
ここで上記 (１) は、現在のＷＳＮを本発明のアルゴリズムを用いて評価するための実験である。また上記 (３) 、 (４) におけるリレー設置候補場所は、図１３におけるトンネルの一端から６．６、９．６、１２．６、１５．６、１８．６、２２．８、２４．６、３０．６、３３．６、３９．６ｍ離れた位置のリングのセグメントＡ，Ｃ，Ｅ，Ｇ，Ｊ，Ｌ，Ｎとした。したがって、リレー設置候補場所数は１０×７＝７０箇所となる。また、これらの実験においては、巡回１回当たりのバッテリー交換作業費用は全てｃ1 ＝２００（£) とし、計算時間を３００ｓとした。
【００９８】
上記 (１) 〜 (４) の場合の実験結果を表１に示す。ただし、表１と以下で示す表２に関しては以下の通りである。
（ｉ）｜Ｓ｜は設置センサ数、｜Ｒ｜はリレー設置候補場所数である。したがって、｜Ｒ｜＝０である場合はリレーを設置できないことを示している。
（ii) ＴＰＬに関しては、各ノードのＴＰＬが全て最大出力水準に固定されている場合は３とし、それを調整可能な場合は１，２，３としている。
（iii) ｃU とｃL は、それぞれ本発明のアルゴリズムで得られた最良の上界値（£／ｄａｙ）、下界値（£／ｄａｙ）である。ここで、ｃU とｃL は単位期間当たりではなく、１日当たりに換算していることに注意する。
（iv）ｅｒｒｏｒは相対誤差で、（ｃU −ｃL ）／ｃL である。
（v)ｌｉｆｅｔｉｍｅは得られたＷＳＮのネットワーク寿命（日数：ｄａｙ）で、ｒｅｌａｙは設計されたＷＳＮにおいて設置するリレーの数である。
【００９９】
(vi) ｉｔｅｒａｔｉｏｎはラグランジアン・ヒューリスティック法の繰返し回数、ｔｉｍｅは計算時間（ｓｅｃｏｎｄ）である。
また、上記手順３では可能解を改善するために確率変数を利用しているので、同一の問題例でも計算結果が異なる場合が存在する。そこで、同一の問題例を５回解いた。したがって、表１と表２の値は５回の解の平均値である。
【０１００】
そのため表１及び表２のＣU ，ＣL ，“ｅｒｒｏｒ”，“ｌｉｆｅｔｉｍｅ”，“ｒｅｌａｙ”，“ｉｔｅｒａｔｉｏｎ”の値は整数でないものがある。
【０１０１】
【表１】
【０１０２】
現在のＷＳＮは、問題 (Ｐ) の１つの可能解であると見なすことができる。それゆえ、現在のＷＳＮに対応した、（ｘijl k ）、（ｙil）を定めると（ｚは（ｘijl k ）より定まることに注意）、それより現在のＷＳＮに対する問題 (Ｐ) の目的関数値が求まる。そこで、現在のＷＳＮに対する問題 (Ｐ) の目的関数値（上界値Ｃu ）を求めて見ると、１０．４０３５（£／ｄａｙ）となる。他方、本発明のアルゴリズムで求めた、現在のＷＳＮ（表１の第１行）に対する下界値Ｃu は９．２９３１である。つまり、本発明のアルゴリズムで求めた下界値Ｃu より、現在のＷＳＮの総費用は改善できたとしても１０．４０３５−９．２９３１＝１．１１０４（£／ｄａｙ）であることが分かる。そしてこれより、「各センサのＴＰＬは全て３に固定」という前提の下では、現在のＷＳＮは比較的良好なＷＳＮであると評価することができる。なお表１の第１行より、本発明のアルゴリズムで求めたＷＳＮの上界値も、現在のＷＳＮのそれに等しく１０．４０３５（これが最適値である場合もあり得ることに注意）である。これは、ＴＰＬを全て最大送信出力の３に固定していることに加えて、設置センサ数が２６と比較的少ないことから、本発明のアルゴリズムにおいても現在のＷＳＮとほぼ同様な伝送ルート案が出力されたためである。
【０１０３】
上述のように、ＴＰＬを全て３に固定した場合は、現存のＷＳＮを改善できる余地は少ないと思われる。しかしながら表１をみると、ＴＰＬを調整すると現存のＷＳＮをさらに改善できることを示している。すなわち表１の第２行は、ＴＰＬを調整すると、総費用を８．９９２３（£／ｄａｙ）に改善できる上に、ネットワーク寿命も１２３．０６日から２１９．０７日に大きく改善できることを示している。また表１の第３、４行からは、現在のＷＳＮに新たにリレーを設置する必要はないことがみてとれる。これは、各センサからの伝送ルートをリレーを使用しなくても確保できたことや、設置センサ数が比較的少ないために、リレーを使用しなくても各センサでの消費電力量をある程度平準化できたためであると推察される。
【０１０４】
図１０は、本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮの出力結果の１例（表１の第４行の｜Ｒ｜＝７０でＴＰＬが１，２，３である場合）である。ただし、図１０と以下に示す図１１、１２において、円はセンサを、三角はリレーを示している。また、各センサと各リレーで設定するＴＰＬを区別し、ｉ、ii、iii はそれぞれＴＰＬを1 、2 、3 に設定することを示している（ここで、ｉ、ii以外はiii であり、iii は数が多いので表記していない。なお、本図は図５（ｂ）と同じ図である）。また、四角はゲートウェイで、線は伝送ルートを構成するアークである。
【０１０５】
図１０には、同じ位置での上部と下部の間の通信が、つまりトンネル内の片方の側壁から他方の側壁への通信がいくつか存在する。これは、トンネル内の無線通信においては、同じサイドに設置されているノード間よりも、異なるサイドに設置されているノード間の方が、一般的に通信を確立し易いためであると思われる。事実、ロンドン地下鉄のジュビリー線のトンネル内で実施された無線通信試験においても、そのような傾向にあることが確認されている。
【０１０６】
前述のように、設置センサ数が２６である現在のＷＳＮにおいては、リレー使用の効果を確認することができなかった。そこで、設置センサを現在のＷＳＮよりも増やした場合の実験を行った（図６の拡張ＷＳＮに対応）。ただし、この実験においては、現在配置されている２６個のセンサに加えて、図１３におけるトンネルの一端から３．６、９．６、１５．６、１８．６、２４．６、３９．６ｍ離れた位置のリングのセグメントＣ，Ｅ，Ｊ，Ｌにさらに２４個のセンサが設置されている場合と、トンネルの一端から３．６、６．６、９．６、１５．６、１８．６、２１．６、２４．６、３３．６、３９．６、４２．６ｍ離れた位置のリングのセグメントＡ，Ｃ，Ｅ，Ｇ，Ｊ，Ｌ，Ｎにさらに７０個のセンサが設置されている場合について実験を行った。つまり、｜Ｓ｜＝５０である場合と、｜Ｓ｜＝９６である場合について実験を行った。他方、リレー設置候補場所は、｜Ｓ｜＝５０である場合はトンネルの一端から３．６、６．６、９．６、１５．６、１８．６、２４．６、３３．６、３９．６、４２．６ｍ離れた位置のリングのセグメントＢ，Ｄ, Ｆ，Ｈ，Ｋ，Ｍに５４箇所とし、｜Ｓ｜＝９６である場合はトンネルの一端から３．６、６．６、９．６、１５．６、１８．６、２４．６、３３．６、３９．６、４２．６ｍ離れた位置のリングのセグメントＢ，Ｄ, Ｆ，Ｈ，Ｋ，Ｍに５４箇所と、トンネルの一端から２１．６ｍ離れた位置のリングのセグメントＤ, Ｆ，Ｈ，Ｋに４箇所の計５８箇所とした。また、バッテリー交換作業費用ｃ1 は｜Ｓ｜＝５０である場合は３００（£) とし、｜Ｓ｜＝９６である場合は５００（£) とした。さらに計算時間は、｜Ｓ｜＝５０である場合は６００秒とし、センサ数がその約２倍の｜Ｓ｜＝９６である場合は１２００秒とした。
【０１０７】
上記の場合の実験結果を表２に示す。また、この実験について本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮの出力結果の例を図１１（表２の第４行の｜Ｓ｜＝５０、｜Ｒ｜＝５４でＴＰＬが１，２，３である場合）、図１２（表２の最終行の｜Ｓ｜＝９６、｜Ｒ｜＝５８でＴＰＬが１，２，３である場合）に示す。なお、図１２は図６（ｂ）と同じ図である。
【０１０８】
【表２】
【０１０９】
表２に示された結果より、リレーの設置を考慮すると上界値を低減できること、そしてＴＰＬを調整するとそれを更に改善できることがわかる。例えばセンサが５０個の場合、上界値ＣU は３２．４１４８（£／ｄａｙ）から３０．８２２３（£／ｄａｙ）へ低減されることを示している。また表２は、リレーの設置とＴＰＬの調整を同時に考慮すると、総費用をより低減できることを示している。さらに表２は、リレーの設置とＴＰＬの調整が、ｌｉｆｅｔｉｍｅの長期化にも有効であることを示唆している。さらに表２における相対誤差は、多少バラツキがあるもののその平均値は０．０８２８である。これより、この実験で取り上げた規模の問題であれば、本発明のアルゴリズムで比較的良好な可能解が求まることが分かる。なお表２において、｜Ｓ｜＝５０、｜Ｒ｜＝５４である場合のｌｉｆｅｔｉｍｅが、ＴＰＬを固定した場合よりもそれを調整した場合の方が短くなっているのは、本発明のアルゴリズムがライフタイムの長期化よりも総費用の最小化を優先しているためである（事実、総費用はＴＰＬを調整した方が少なくなっている）。また図１１，１２において、左右方向に比較的長い距離の通信が発生しているのは、あるノードから送信する際の消費電力量は送信先のノードまでの距離ではなく、そのノードで設定するＴＰＬの水準に依存することが大きく関係しているものと思われる。
【０１１０】
なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨に基づき種々の変形が可能であり、これらを本発明の範囲から排除するものではない。
【産業上の利用可能性】
【０１１１】
本発明の対象構造物の無線センサネットワークの設置及び運用費用評価方法は、埋没費用と考えられるセンサとゲートウェイの設置費用を除いた、初期設置費用（リレー設置費用）と運用費用（バッテリー消費費用、バッテリー交換作業費用）の費用の最小化を図ることができる無線センサネットワークの設置及び運用費用評価方法に利用することができる。
【符号の説明】
【０１１２】
１ トンネル
２ 軌道
３ センサ
４ ゲートウェイ
５ 携帯電話網
６ 管理局
【技術分野】
【０００１】
本発明は、対象構造物の状態監視のための無線センサネットワーク（Ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ，ＷＳＮ）の設置及び運用費用評価方法に係り、特に鉄道土木構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法に関するものである。
【背景技術】
【０００２】
本発明では、対象構造物の状態監視に用いられる無線センサネットワークを、総費用が最小となるように設計する方法を提案する。
特に、鉄道土木構造物に対する保守管理は、これまで人手による目視検査を中心に行われてきた。
しかしながら、現状の人手による目視での状態監視方法には、
（１）作業に多大な労力と時間が必要である
（２）見落としや見間違いなどのヒューマンエラーがつきものである
（３）検査結果の客観性の欠如があり、検査技術の承継も困難である
（４）危険な現場での検査業務となる、などの問題があった。
【０００３】
近年、これらの問題点を克服する目的で、無線センサネットワークを活用した鉄道土木構造物の保守管理が注目を集めている。
ここで、無線センサネットワーク（ＷＳＮ）とは、無線通信機能を持つ多数の小型センサによる自動的なネットワークのことであり、土木構造物の状態監視へ適用した場合の利点として、（１）センサ同士がリレーしてデータを転送することができるので、配線が不要であり、冗長性が高い、（２）デバイスが小型であるので設置場所を選ぶことなく、多様な測定ができる、などがある。実際に、ロンドン地下鉄、プラハ地下鉄、バルセロナ地下鉄の一部区間では既にＷＳＮを利用した鉄道構造物の状態監視システムが導入されている（下記非特許文献１，２参照）。
【０００４】
図１３はロンドン地下鉄のジュビリー線に設置されたＷＳＮの模式図であり、図１３（ａ）はその全体模式図、図１３（ｂ）は図１３（ａ）のＡ部拡大図である。
ロンドン地下鉄は世界でも最も広範囲に老朽化が進んでいる地下鉄の１つであり、全長１８１ｋｍのトンネルの多くが建設から既に７５−１００年が経過している。このため、トンネル内のライニングの劣化や経時的な土圧の変化などが懸念されていた。
【０００５】
そこで、２００７年にそれらをモニタリングするため、図１３〔拡大部分の英大文字はトンネル内壁のセグメント（ｓｅｇｍｅｎｔ）〕に示すようなＷＳＮがベーカーストリート駅からボンドストリート駅間に設置された（下記非特許文献１，２参照）。なお、図１３（ａ）の黒丸はゲートウェイであり、図１３（ｂ）の２７．６ｍに位置するリングのセグメントＢに配置されている。また、ロンドン地下鉄のハマースミス駅構内では、２００３年にレール折れによる脱線事故が発生しており、このレール折れの発生原因は、線路両脇にある擁壁の変状にあると推測された。そこで、このような事故の再発を防止すべく、現場の擁壁変状をモニタリングするためのＷＳＮが２００９年にハマースミス駅構内に設置された。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Ｐｅｔｅｒ Ｊ．Ｂｅｎｎｅｔｔ，Ｋｅｎｉｃｈｉ Ｓｏｇａ，Ｉａｎ Ｗａｓｓｅｌｌ，Ｐａｕｌ Ｆｉｄｌｅｒ，Ｋｅｉｔａ Ａｂｅ，Ｙｕｓｕｋｅ Ｋｏｂａｙａｓｈｉ，Ｍａｒｔｉｎ Ｖａｎｉｃｅｋ，“Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ ｆｏｒ Ｕｎｄｅｒｇｒｏｕｎｄ Ｒａｉｌｗａｙ Ａｐｐｌｉｃａｔｉｏｎｓ：Ｃａｓｅ Ｓｔｕｄｉｅｓ ｉｎ Ｐｒａｇｕｅ ａｎｄ Ｌｏｎｄｏｎ”，Ｓｍａｒｔ Ｓｔｒｕｃｔｕｒｅｓ ａｎｄ Ｓｙｓｔｅｍｓ，Ｖｏｌ．６，Ｎｏ．５−６，ｐｐ．６１９−６３９，２０１０．
【非特許文献２】Ｆ．Ｓｔａｊａｎｏ，Ｎ．Ｈｏｕｌｔ，Ｉ．Ｊ．Ｗａｓｓｅｌ，Ｐ．Ｊ．Ｂｅｎｎｅｔｔ，Ｃ，Ｍｉｄｄｌｅｔｏｎ，Ｋ．Ｓｏｇａ，Ｓｍａｒｔ ｂｒｉｄｇｅ，ｓｍａｒｔ ｔｕｎｎｅｌｓ；ｔｒａｎｓｆｏｒｍｉｎｇ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｆｒｏｍ ｒｅｓｅａｒｃｈ ｐｒｏｔｏｔｙｐｅｓ ｉｎｔｏ ｒｏｂｕｓｔ ｅｎｇｉｎｅｅｒｉｎｇ ｉｎｆｒａｓｔｒｕｃｔｕｒｅ，Ａｄ Ｈｏｃ Ｎｅｔｗｏｒｋｓ ８（８）（２０１０），ｐｐ．８７２−８８８
【非特許文献３】Ａ．Ａｌｆｉｅｒｉ，Ａ．Ｂｉａｎｃｏ，Ｐ．Ｂｒａｎｄｉｍａｒｔｅ ａｎｄ Ｃ．Ｆ．Ｃｈｉａｓｓｅｒｉｎｉ，“Ｍａｘｉｍｉｚｉｎｇ ｓｙｓｔｅｍ ｌｉｆｅｔｉｍｅ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ，”Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅａｒｃｈ，ｖｏｌ．１８１，ｐｐ．３９０−４０２，２００７.
【非特許文献４】Ｘ．Ｔａｎｇ ａｎｄ Ｊ．Ｘｕ，“Ｅｘｔｅｎｄｉｎｇ ｎｅｔｗｏｒｋ ｌｉｆｅｔｉｍｅ ｆｏｒ ｐｒｅｃｉｓｉｏｎ−ｃｏｎｓｔｒａｉｎｅｄ ｄａｔａ ａｇｇｒｅｇａｔｉｏｎ ｉｎ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ，”ｉｎ Ｐｒｏｃ．ｔｈｅ ２５th ＩＥＥＥ ＩＮＦＯＣＯＭ’０６，ｐｐ．１−１２，Ａｐｒ．２００６．
【非特許文献５】Ｊ．Ｋｉｍ，Ｘ．Ｌｉｎ，Ｎ．Ｂ．Ｓｈｒｏｆｆ ａｎｄ Ｐ．Ｓｉｎｈａ，“Ｏｎ ｍａｘｉｍｉｚｉｎｇ ｔｈｅ ｌｉｆｅｔｉｍｅ ｏｆ ｄｅｌａｙ−ｓｅｎｓｉｔｉｖｅ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｗｉｔｈ ａｎｙｃａｓｔ，”ｉｎ Ｐｒｏｃ．ｔｈｅ ２７th ＩＥＥＥ ＩＮＦＯＣＯＭ’０８，ｐｐ．８０７−８１５，Ａｐｒ．２００８．
【非特許文献６】Ｙ．Ｔ．Ｈｏｕ，Ｙ．Ｓｈｉ，Ｈ．Ｄ．Ｓｈｅｒａｌｉ ａｎｄ Ｓ．Ｆ．Ｍｉｄｋｉｆｆ, “Ｐｒｏｌｏｎｇｉｎｇ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋ ｌｉｆｅｔｉｍｅ ｗｉｔｈ ｅｎｅｒｇｙ ｐｒｏｖｉｓｉｏｎｉｎｇ ａｎｄ ｒｅｌａｙ ｎｏｄｅ ｐｌａｃｅｍｅｎｔ，”ｉｎ Ｐｒｏｃ．ＩＥＥＥ ＳＥＣＯＮ’０５，ｐｐ．２９５−３０４，Ｓｅｐ．２００５．
【非特許文献７】Ｅ．Ｌ．Ｌｌｏｙｄ，Ｇ．Ｘｕｅ，“Ｒｅｌａｙ Ｎｏｄｅ Ｐｌａｃｅｍｅｎｔ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ”，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｃｏｍｐｕｔｅｒｓ，Ｖｏｌ．５６，Ｉｓｓｕｅ．１，ｐｐ．１３４−１３８，２００７．
【非特許文献８】Ｂ．Ｈａｏ，Ｈ．Ｔａｎｇ，Ｇ．Ｘｕｅ，“Ｆａｕｌｔ−ｔｏｌｅｒａｎｔ Ｒｅｌａｙ Ｎｏｄｅ Ｐｌａｃｅｍｅｎｔ ｉｎ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ”，ｉｎ Ｐｒｏｃ．Ｔｈｅ Ｗｏｒｋｓｈｏｐ ｏｎ Ｈｉｇｈ Ｐｅｒｆｏｒｍａｎｃｅ Ｓｗｉｔｃｈｉｎｇ ａｎｄ Ｒｏｕｔｉｎｇ，ｐｐ．２４６−２５０，２００４．
【非特許文献９】Ｌｕｉｚ Ｈ．Ａ．Ｃｏｒｒｅｉａ，Ｄａｎｉｅｌ Ｆ．Ｍａｃｅｄｏ，Ａｌｄｒｉ Ｌ．ｄｏｓ Ｓａｎｔｏｓ，Ａｎｔｏｎｉｏ Ａ．Ｆ．Ｌｏｕｒｅｉｒｏ，Ｊｏｓｅ Ｍａｒｃｏｓ Ｓ．Ｎｏｇｕｅｉｒａ，“Ｔｒａｎｓｍｉｓｓｉｏｎ Ｐｏｗｅｒ Ｃｏｎｔｒｏｌ Ｔｅｃｈｎｉｑｕｅｓ ｆｏｒ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋｓ”，Ｃｏｍｐｕｔｅｒ Ｎｅｔｗｏｒｋｓ, Ｖｏｌ．５１，ｐｐ．４７６５−４７７９，２００７．（ただし、ｅはアキュートアクセント付き）
【非特許文献１０】Ｎａｔａｌｌｉａ Ｋａｔｅｎｋａ，Ｅｌｉｚａｖｅｔａ Ｌｅｖｉｎａ，Ｇｅｏｒｇｅ Ｍｉｃｈａｉｌｉｄｉｓ，“Ａ Ｃｏｓｔ−Ｅｆｆｉｃｉｅｎｔ Ａｐｐｒｏａｃｈ ｔｏ Ｗｉｒｅｌｅｓｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ Ｄｅｓｉｇｎ”，Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ Ｎｏ．４７４，Ｄｅｐａｒｔｍｅｎｔ ｏｆ Ｓｔａｔｉｓｔｉｃｓ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｍｉｃｈｉｇａｎ，２００７．
【非特許文献１１】Ｖｉｖｅｋ Ｐ．Ｍｈａｔｒｅ，Ｃａｔｈｅｒｉｎｅ Ｒｏｓｅｎｂｅｒｇ，Ｄａｎｉｅｌ Ｋｏｆｍａｎ，Ｒａｖｉ Ｍａｚｕｍｄａｒ，Ｎｅｓｓ Ｓｈｏｆｆ，“Ａ Ｍｉｎｉｍｕｍ Ｃｏｓｔ Ｈｅｔｅｒｏｇｅｎｅｏｕｓ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ ｗｉｔｈ ａ Ｌｉｆｅｔｉｍｅ”ｃｏｎｓｔｒａｉｎｔ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ，Ｖｏｌ．４，Ｎｏ．１，ｐｐ．４−１５，２００５．
【非特許文献１２】Ｚｈａｏ Ｃｈｅｎｇ，Ｍａｒｋ Ｐｅｒｉｌｌｏ，Ｗｅｎｄｉ Ｂ．Ｈｅｉｎｚｅｌｍａｎ，“Ｇｅｎｅｒａｌ Ｎｅｔｗｏｒｋ Ｌｉｆｅｔｉｍｅ ａｎｄ Ｃｏｓｔ Ｍｏｄｅｌｓ ｆｏｒ Ｅｖａｌｕａｔｉｎｇ Ｓｅｎｓｏｒ Ｎｅｔｗｏｒｋ Ｄｅｐｌｏｙｍｅｎｔ Ｓｔｒａｔｅｇｉｅｓ”，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ，Ｖｏｌ．８，Ｎｏ. ４，ｐｐ．４８４−４９７，２００８．
【非特許文献１３】Ａ．Ｍ．Ｇｅｏｆｆｒｉｏｎ，“Ｌａｇｒａｎｇｉａｎ ｒｅｌａｘａｔｉｏｎ ｆｏｒ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ”，Ｍａｔｈｅｍａｔｉｃａｌ Ｐｒｏｇｒａｍｍｉｎｇ Ｓｔｕｄｙ ２（１９７４），ｐｐ．８２−１１４
【非特許文献１４】Ｊ．Ｅ．Ｂｅａｓｌｅｙ，“Ｌａｇｒａｎｇｅａｎ ｈｅｕｒｉｓｔｉｃｓ ｆｏｒ ｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍｓ”，Ｔｈｅｏｒｙ ａｎｄ Ｍｅｔｈｏｄｏｌｏｇｙ ６５（３）（１９９３），ｐｐ．３８３−３９９
【非特許文献１５】Ｅ．Ｗ．Ｄｉｊｋｓｔｒａ，Ａ ｎｏｔｅ ｏｎ ｔｗｏ ｐｒｏｂｌｅｍｓ ｉｎ ｃｏｎｎｅｘｉｏｎ ｗｉｔｈ ｇｒａｐｈｓ Ｎｕｍｅｒｉｓｃｈｅ Ｍａｔｈｅｍａｔｉｋ １（１）（１９５９）２６９−３０６．
【非特許文献１６】Ｒ．Ｅ．Ｂｅｌｌｍａｎ，Ｏｎ ａ ｒｏｕｔｉｎｇ ｐｒｏｂｌｅｍ，Ｑｕａｒｔｅｒｌｙ ｏｆ Ａｐｐｌｉｅｄ ｍａｔｈｅｍａｔｉｃｓ １６（１）（１９５８）８７−９０．
【非特許文献１７】Ｍ．Ｌ．Ｆｉｓｈｅｒ，Ｔｈｅ Ｌａｇｒａｎｇｉａｎ ｒｅｌａｘａｔｉｏｎ ｍｅｔｈｏｄ ｆｏｒ ｓｏｌｖｉｎｇ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ ｐｒｏｂｌｅｍｓ，Ｍａｎａｇｅｍｅｎｔ Ｓｃｉｅｎｃｅ ２７（１）（１９８１）１−１８．
【非特許文献１８】Ｓ．Ｍａｒｔｅｌｌｏ，Ｐ．Ｔｏｔｈ Ｅｘａｃｔ ａｎｄ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ｍａｋｅｓｐａｎ ｍｉｎｉｍｉｚａｔｉｏｎ ｏｎ ｕｎｒｅｌａｔｅｄ ｐａｒａｌｌｅｌ ｍａｃｈｉｎｅｓ，Ｄｉｓｃｒｅｔｅ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ ７５（２）（１９９７）１６９−１８８．
【非特許文献１９】Ｋ．Ｊｏｒｎｓｔｅｎ，Ｍ．Ｎａｓｂｅｒｇ，Ａ ｎｅｗ Ｌａｇｒａｎｇｉａｎ ｒｅｌａｘａｔｉｏｎ ａｐｐｒｏａｃｈ ｔｏ ｔｈｅ ｇｅｎｅｒａｌｉｚｅｄ ａｓｓｉｇｎｍｅｎｔ ｐｒｏｂｌｅｍ，Ｅｕｒｏｐｅａｎ Ｊｏｕｒｎａｌ ｏｆ Ｏｐｅｒａｔｉｏｎａｌ Ｒｅｓｅｒｃｈ ２７（３）（１９８６）３１３−３２３（ただし、ｏとａウムラウト付き）
【非特許文献２０】Ｒ．Ｌｉｕ，Ｉ．Ｊ．Ｗａｓｅｌｌ，Ｋ．Ｓｏｇａ，Ｒｅｌａｙ ｎｏｄｅ ｐｌａｃｅｍｅｎｔ ｆｏｒ ｗｉｒｅｌｅｓｓ ｓｅｎｓｏｒ ｎｅｔｗｏｒｋｓ ｄｅｐｌｏｙｅｄ ｉｎ ｔｕｎｎｅｌｓ，ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｗｉｒｅｌｅｓｓ ａｎｄ Ｍｏｂｉｌｅ Ｃｏｍｐｕｔｉｎｇ，Ｎｅｔｗｏｒｋｉｎｇ ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，２０１０，ｐｐ．１４４−１５０.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上記ＷＳＮの設計においては、伝送遅延や伝送成功率などに関する技術的な検討と共に、設置（初期投資）費用と運用費用の総和を最小にするための方策が種々検討された。しかしながら、ＷＳＮを構築し運用する際に発生する諸費用は互いに密接に関係しており、それらの間には様々なトレードオフ関係が存在する。例えば、リレーを多く設置すると、ネットワーク内の各バッテリーの消費電力量が平準化され、バッテリー交換のための巡回間隔を長くできる傾向にある。つまり、リレー設置の初期投資費用を多く（少なく）すると、バッテリー交換のための運用費用は少なく（多く）なる。そのため、初期投資費用と運用費用の検討には多くの時間を要した。さらに、センサやリレーにおける送信電力レベル（ｔｒａｎｓｍｉｓｓｉｏｎ ｐｏｗｅｒ ｌｅｖｅｌ）（以下、ＴＰＬと記す）の設定やセンシングデータを送信するためのルート計画も、ネットワーク内の電力消費費用、バッテリー交換費用、リレー設置の初期費用などに大きく関係するはずであるが、これらの要素まで全て含めて、設置費用と運用費用の総和が最小となるようなＷＳＮを系統的に設計できる具体的な方法は開発されていなかった。
【０００８】
本発明では、上記状況に鑑みて、ＷＳＮの設置・運用に要する費用の総和を最小にすることができる、対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法を提供することを目的とする。
より具体的には、埋没費用と考えられるセンサとゲートウェイの設置費用を除いた、設置費用（リレー設置費用）と運用費用（バッテリー消費費用、バッテリー交換作業費用）の総和の最小化を図るように無線センサネットワークの設計を行うことを目的とする。
【０００９】
なお、リレーの設置計画、ＴＰＬの設定計画、センシングデータのルート計画は、鉄道構造物以外を対象とするＷＳＮの設計においても主要な課題であり、多くの場合、それらの計画がＷＳＮの効率性・経済性に大きく関係する。
このため、以下で提案するＷＳＮの設計アルゴリズムは、鉄道構造物に限らず、その他の構造物の状態監視に用いられるＷＳＮにも幅広く適用できる。
【課題を解決するための手段】
【００１０】
本発明は、上記目的を達成するために、
〔１〕対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び／又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、このバッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) を用いてセンサネットワークを設計することを特徴とする。
【００１１】
〔２〕上記〔１〕記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記対象構造物が、鉄道土木構造物であることを特徴とする。
〔３〕上記〔２〕記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記総和の最小化を行うため、リレーの設置数とその設置場所、各センサと各リレーにおける送信電力レベル、前記センサからのデータを前記ゲートウェイにマルチホップで送信するための伝送経路を同時に設定することを特徴とする。
【００１２】
〔４〕上記〔３〕記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記センサと前記ゲートウェイの設置場所と、前記リレー設置候補場所と、各種電力情報と、各種費用情報を入力情報として与え、前記リレーの設置費用と前記バッテリーの消費費用と前記バッテリーの交換作業費用との総和が最小になるような前記リレーの設置場所と、前記データの伝送経路と、前記センサと前記リレーの送信電力レベル、ならびに前記無線センサネットワーク１日あたりの費用と、ネットワーク寿命を出力し、これに基づき前記無線センサネットワークを構築することを特徴とする。
【発明の効果】
【００１３】
本発明によれば、次のような効果を奏することができる。
（１）軍事モニタリング、フィールドモニタリング、構造物モニタリングなど活用範囲の広いセンサネットワークを構築・運用する際の費用評価が可能となることにより、センサネットワークの導入による効果と費用の関係（費用対効果）が明らかになる。
（２）総費用が少ないセンサネットワークを設計できることにより、事業者にとっても経費削減を図ることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の評価対象である鉄道土木構造物の状態監視のためのＷＳＮの模式図である。
【図２】本発明に係る鉄道土木構造物を対象とするのＷＳＮシステムの設置・運用にかかる費用の分類を示す図である。
【図３】本発明のアルゴリズムであるラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｅａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) の説明図である。
【図４】本発明に係るＷＳＮの設置及び運用費用評価方法によるＷＳＮシステム設計における入力例と出力例を示す図である。
【図５】既存ＷＳＮのネットワーク設計（ロンドン地下鉄）の説明図である。
【図６】拡張ＷＳＮのネットワーク設計（ロンドン地下鉄）の説明図である。
【図７】本発明に係るリレーからセンサへのＴＰＬの出力水準と送信可能範囲との関係を示す図である。
【図８】本発明に係るＧ＝（Ｎ，Ａ）にマルチプルアークが存在している状況を示す説明図である。
【図９】本発明にかかる（ＬＸ（ｕ, ｖ））と（ＬＹ（ｖ））に関する伝送ルートを示す図である。
【図１０】本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮ設計案（２６個のセンサ及び７０個のリレー候補場所を有する場合）を示す図である。
【図１１】本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮ設計案（５０個のセンサ及び５４個のリレー候補場所を有する場合）を示す図である。
【図１２】本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮ設計案（９６個のセンサ及び５８個のリレー候補場所を有する場合）を示す図である。
【図１３】従来のロンドン地下鉄のジュビリー線に設置されたＷＳＮを示す図である。
【発明を実施するための形態】
【００１５】
本発明の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法は、対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び／又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、このバッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) を用いてセンサネットワークを設計する。
【実施例】
【００１６】
本発明は、対象構造物の状態監視のためのＷＳＮの設置及び運用費用評価方法であるが、これは所与の条件の下、設置及び運用費用の総和が最も小さくなるようなＷＳＮを設計し、その設置・運用費用に加えてネットワーク寿命をも評価するものである。このような本発明では、設置及び運用費用の総和が最も小さくなるようなＷＳＮを設計するため、リレー設置費用とバッテリー消費費用とバッテリー交換費用の総和を最小とすることを目的とする。そのために、まず、最初に、リレーの設置数とその設置場所、各センサと各リレーにおけるＴＰＬのレベル、センシングデータをゲートウェイにマルチホップで送信するための伝送ルートを同時に計画する問題を設定する。
【００１７】
次いで、その問題を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく、その問題の近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) を用いて問題の解を得る。
本明細書では、最後に、本発明の有効性を鉄道土木構造物の状態監視における実例を用いた数値実験により検証する。
【００１８】
以下、本発明の実施の形態について詳細に説明する。
図１は本発明の評価対象である鉄道土木構造物の状態監視のためのＷＳＮの模式図である。
図１において、１は鉄道土木構造物としてのトンネル、２は軌道、３はセンサ、４はゲートウェイ、５は携帯電話網、６は管理局である。ここでは、センサ３が所定間隔でトンネル１の内壁に複数個ずつ配置されている。また、点線は、データの流れを示している。なお、ここでは、リレーが配置されていないものを示す。
【００１９】
マルチホップ無線通信により、センサ３からのセンシングデータの収集が行われ、その収集データはゲートウェイ４を介して携帯電話網５を通じて管理局６へと伝送される。センサ３としては、地下鉄においては、バッテリーで駆動される傾斜計センサや変位計センサが配置され、ゲートウェイ４はＡＣ電源で駆動される。このような構成のＷＳＮでトンネルの状態監視が行われる。
【００２０】
ここで、上記したように、ＷＳＮは複数個のセンサ３と単一のゲートウェイ４を有するが、それらの設置場所は予め決められているものとする。また、リレーを設置できる場所の候補も幾つかあり、これらの場所も予め決められているものとする。さらに、各センサ３と各リレーにおいてはデータを出力する際のＴＰＬを数段階の水準の中の１つに設定でき、各センサ３と各リレーから送信できる範囲と送信のための消費電力量は設定したＴＰＬに依存するものとする。加えて、各センサ３と各リレーの電源はそれぞれに配置されたバッテリーであり、各バッテリーは電力が枯渇したものと次の交換作業までに電力が枯渇するものを交換しなければならないものとする。
【００２１】
このような前提のもと、鉄道土木構造物の状態監視を行うためのＷＳＮとして、以下のようなシステムの構築について考える。
（１）各センサ３では単位期間毎に１回データを収集する。
（２）各センサ３で収集したデータは、マルチホップ通信でゲートウェイ４に無線伝送される。
（３）ゲートウェイ４に伝送されたデータは、携帯電話やインターネットなどの一般の通信手段を用いて管理局６の中央の管理サーバに転送される。
【００２２】
図２は本発明に係る鉄道土木構造物を対象とするＷＳＮシステムの設置・運用にかかる費用の分類を示す図である。
この図に示すように、ＷＳＮの設置及び運用にはさまざまな費用が必要であり、例えば、バッテリー消費費用、バッテリー交換作業費用、リレー設置費用、ゲートウェイ設置費用、センサ設置費用などが挙げられる。
【００２３】
これらの費用を分類すると、バッテリー消費費用、バッテリー交換作業費用は運用費用Ａであり、リレー設置費用、ゲートウェイ設置費用、センサ設置費用は、設置費用Ｂであり、運用費用Ａと設置費用Ｂの総和が全体費用Ｃである。
このように、上記ＷＳＮシステムの構築においては、まずセンサ３、ゲートウェイ４、リレーを設置するための設置費用が発生する。しかし、センサ３とゲートウェイ４の設置場所は上記したように予め定められていることから、それらの設置費用は埋没費用（ｓｕｎｋ ｃｏｓｔ）であると見なすことができる。そこで、本発明においてはシステム構築の設置費用としては残りのリレー設置費用だけを考慮することにする。また、このシステムの運用においては、システム内の各センサと各リレーのバッテリーを保守作業員が現場を巡回して交換する必要がある。つまり、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーを保守作業員が現場を巡回して交換する必要がある。よって、システムの運用段階においてはバッテリー交換のための作業費用が発生する。加えて、システムの運用段階においては、当然のことながら、各バッテリーの電力消費費用についても考慮する必要がある。したがって、このシステムの構築段階においてはリレー設置費用が、そして運用段階においてはバッテリー消費費用とバッテリー交換作業費用が発生することになる。
【００２４】
なお、各センサに設けられる無線通信機器では、３５Ａｈ、３．６Ｖのバッテリーを使用しているが、バッテリー寿命は約１年半である。一方、傾斜計は無線通信機器とは異なる２．４Ａｈ、３．６Ｖのバッテリーを２個使用しており、そのバッテリー寿命は約１年である。変位計は無線通信機器のバッテリーより電源が供給される。変位計ノードの寿命は約１年である。
ノード障害は、突発的である一方、バッテリーの枯渇は定期的に発生する。また、ノード復旧よりもバッテリー交換の方が高コストであるので、ＷＳＮを長期間運用するためにも、効率的にバッテリーを利用する必要がある。したがって、最適化技術を活用して効率的にＷＳＮを設計する。
【００２５】
そこで、本発明の問題の設定としては、運用費用Ａ（バッテリー消費費用、バッテリー交換作業費用）と設置費用Ｂ（リレー設置費用）の総和が最小となるように、リレーの設置数とその設置場所、各センサと各リレーのＴＰＬの水準、各センシングデータの送信経路を決定する。すなわち、リレーをそれらを設置可能な場所の中のどこにいくつ配置するかを決定する問題と、各センサと各リレーでのＴＰＬの水準を決定する問題と、各センサで収集したデータをゲートウェイに送信するためのルートを決定する問題である。これら３つの問題は先に示した３つの費用すべてに関係している。つまり、これら３つの問題は互に密接に関係しており、各問題を個別に解いても総費用の最小化を保証することはできない。そこで本発明では、リレー設置費用とバッテリー消費費用とバッテリー交換作業費用の総和が最小となるように、これら３つの問題を同時に解くようにする。
【００２６】
図３は本発明のアルゴリズムであるラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）に基づく近似最適解法 (ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ) の説明図であり、図３（ａ）はそのラグランジアン・ヒューリスティック法の実行フローチャート、図３（ｂ）はアルゴリズムの繰り返し回数に対する目的関数値を示す図、図３（ｃ）は最適解の存在範囲を示す模式図である。
【００２７】
本発明では、上記した問題を解くため、以下のようなアルゴリズムを用いる。
図３（ａ）に示すように、まず、初期解と初期ラグランジュ乗数の決定を行う（ステップＳ１）。次に、ラグランジュ緩和問題を利用した下界値の生成を行う（ステップＳ２）。次に、ラグランジュ乗数を利用した上界値の生成を行う（ステップＳ３）。終了条件（ステップＳ４）を満足しなければ、ラグランジュ乗数の更新を行い（ステップＳ５）、ステップＳ２へ戻り、終了条件（ステップＳ４）を満足したら、アルゴリズムの繰り返しを停止する（ステップＳ６）。
【００２８】
つまり、図３（ｂ）に示すように、上界値と下界値の情報を利用して最適解に近い解を求める。ここで、上界値はアルゴリズムが出力した解、下界値は最適値以下であることが理論的に保証された値であり、図３（ｃ）の下段に示すように、上界値と下界値の間の最適値の存在範囲が狭まるようにすることが望ましい。
【００２９】
図４は本発明に係るＷＳＮの設置及び運用費用評価方法によるＷＳＮシステム設計における入力例と出力例を示す図であり、図４（ａ）はその入力例を示す図、図４（ｂ）はその出力例を示す図である。
本発明に係るＷＳＮの設置及び運用費用評価方法においては、図４（ａ）に示すように、センサの配置場所、ゲートウェイの設置場所、リレーの設置候補場所、各電力（送信・受信・センシング）、各費用（リレー設置、バッテリー消費、バッテリー交換作業）を評価条件として入力すると、この入力条件にしたがって、図４（ｂ）に示すように、リレーの設置場所、各センシングデータの伝送経路、各センサと各リレーのＴＰＬの水準、ネットワーク寿命、ＷＳＮの単位期間あたりの費用が出力される。
【００３０】
図５は既存ＷＳＮのネットワーク設計（ロンドン地下鉄）の説明図である。図５（ａ）は現在のＷＳＮ（図１３と対応）であり、横軸がリングの位置、縦軸はセグメントＡ〜Ｍを示しており、図５（ｂ）は現在のＷＳＮの条件の下、本発明の評価方法により提案されるＷＳＮであり、横軸はトンネルリングの位置、縦軸はセグメントＡ〜Ｍを示している。なお、図中のひし形及び丸はセンサの位置、四角はゲートウェイの位置を示している。また、図５（ａ）の横軸の数字はリング番号を示しており、１６４０は０ｍ、１６５０は６．６ｍ、１６６０は１２．６ｍ、１６７０は１８．６ｍ、１６８０は２４．６ｍ、１６９０は３０．６ｍ、１７００は３６．６ｍ、１７１０は４２．６ｍ、１７２０は４８．６ｍにそれぞれ対応しており、リング番号が示される他の図でも同様である。
図５（ａ）の現在のＷＳＮでは、一日あたりの全体の費用は１５６０円であり、ネットワーク寿命が１２３日であるのに対して、図５（ｂ）の本発明による評価に基づくＷＳＮでは、一日あたりの全体の費用は１３４９円となり、ネットワーク寿命も２１９日となった。このように、本発明によれば、１５％の費用低減を達成し、ネットワーク寿命を７８％延ばすことができた（後出の表１参照）。
【００３１】
図６は拡張ＷＳＮのネットワーク設計（ロンドン地下鉄）の説明図である。図６（ａ）はリレー設置、ＴＰＬ水準調整なしの場合であり、横軸がリングの位置、縦軸はセグメントＡ〜Ｍを示しており、図６（ｂ）はリレー設置、ＴＰＬ水準調整ありの場合であり、横軸はリングの位置、縦軸はセグメントＡ〜Ｍを示している。なお、図中のひし形及び丸はセンサの位置、四角はゲートウェイの位置を示しており、図６（ｂ）の三角はリレーの位置を示している。図６（ａ）では、一日あたりの全体の費用は８５８４円であり、ネットワーク寿命が６９日であるのに対し、図６（ｂ）では、一日あたりの全体の費用は８２３０円となり、ネットワーク寿命は９８日となった。このように本発明によれば、４．３％の費用低減を達成し、ネットワーク寿命を４２％延ばすことができた（後出の表２参照）。
【００３２】
上記したように本発明によれば、鉄道土木構造物の状態監視に用いる無線センサネットワークを、総費用が最小になるように設計できた。すなわち、本発明では最初にリレーの設置数とその設置場所、各センサーと各リレーにおける送信電力レベル、センシングデータをゲートウェイにマルチホップで送信するためのルートを同時に計画する問題を設定し、次いで、その問題を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法に基づくその問題の近似最適解法により解くことで設置及び運用費用の評価を行った。そして最後にその有効性を鉄道土木構造物の状態監視に用いる無線センサネットワークの実例を用いた数値実験により検証した。
【００３３】
以下、より具体的に本発明の実施例を示す鉄道土木構造物の状態監視に用いるＷＳＮ（無線センサネットワーク）の設置及び運用費用評価方法について説明する。
既述のように、各センサや各リレーから送信できる範囲と送信のためのバッテリー消費量は、各センサや各リレーで設定するＴＰＬの出力水準に依存する。
【００３４】
図７は本発明に係るリレーからセンサへのＴＰＬの出力水準と送信可能範囲との関係を示す図である。
リレーからセンサへのＴＰＬの出力水準ごとの送信可能範囲は図７に示すようになる。ただし、図７に関しては以下の通りである。
（１）円はセンサ、三角はリレー、四角はゲートウェイで、円と三角内の数字はそれぞれセンサ番号、リレー番号である。
（２）各センサと各リレーではＴＰＬを１、２、３の何れかに設定でき、ＴＰＬ１が最小送信出力、ＴＰＬ３が最大送信出力、ＴＰＬ２がその中間の送信出力である。
（３）リレー６を設置した場合に、それからＴＰＬ１、２、３で送信できる範囲を、それぞれａ、ｂ、ｃの点線で示している。
（４）リレー６からＴＰＬ１、２、３で送信できる箇所を、それぞれｄ、ｅ、ｆの矢印で示している。
【００３５】
この例においては、リレー６からセンサ２へ送信できるのはＴＰＬ３の場合だけである。よって、リレー６からセンサ２へ送信するには、リレー６のＴＰＬを３に設定しなければならないことになる。また、リレー６からセンサ４へは、リレー６のＴＰＬを１、２、３の中の何れに設定しても送信できるが、リレー６からセンサ１へは最大送信出力のＴＰＬ３でも送信できないことを示している。
【００３６】
なお、本発明では、さらに以下を仮定する。
（ｉ）１つのセンサで収集したデータは１つにまとめ、それを途中の中継点で分割することなくゲートウェイに伝送するものとする。
（ｉｉ）ネットワーク内に設置する各リレーはすべて同一のものであるとする。
（ｉｉｉ)鉄道土木構造物の状態監視において設置するセンサは、リレーにデータ収集機能を付加したものである場合が多い。つまり、センサも中継機能を持ち、センサとリレーの機能はデータ収集機能を除けば同一である場合が多い。そこで、各センサと各リレーにおけるＴＰＬの水準数（図７の場合は３）は全て同一であるとする。
【００３７】
（ｉｖ）バッテリー交換作業において交換するバッテリーは、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーだけで、次の巡回まで寿命のあるバッテリーは交換しないで良いものとする。つまり、システム内のあるバッテリーの寿命（交換してから電力が枯渇するまでの期間）がネットワーク寿命のθ（＞１）倍以上でかつ（θ＋１）倍未満である場合は、そのバッテリーはθ回の巡回に一度の割合で交換すれば良いものとする。
【００３８】
次に、本発明と関連する研究について説明する。
センサネットワークの長寿命化に関してはこれまでに多くの研究がなされている。例えば、Ａｌｆｉｅｒｉら（上記非特許文献３参照）は与えられたセンサを分割して複数の部分センサネットワークを構成し、それらの運用時間帯を調整することによりネットワーク寿命を長期化する手法を提案している。また、Ｔａｎｇら（上記非特許文献４参照）は伝送データの信頼性を考慮して、Ｋｉｍら（上記非特許文献５参照）はセンシングデータの伝送遅延を考慮してネットワーク寿命を最大化する方法を提案している。しかしながら、これらの研究においては、ネットワーク内の総消費電力量について考慮していない。つまり、ネットワーク寿命と総消費電力量はトレードオフの関係にあることから、ネットワーク寿命について考える場合は同時に総消費電力量についても考慮すべきであるが、これらの研究においてはそれを明白には考慮していない。
【００３９】
センサネットワーク内のリレー配置問題に関しても多くの研究がある。例えば、Ｈｏｕら（上記非特許文献６参照）はリレーの配置問題とゲートウェイやリレーへの電力の割当問題を同時に解く方法を提案している。また、Ｌｌｏｙｄら（上記非特許文献７参照）はセンサ間の通信を確保するために必要な最小のリレー数を求める問題を取り上げ、この問題に対する近似アルゴリズム（ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ）を提案している。Ｈａｏら（上記非特許文献８参照）は、各センサ間に少なくとも２本のルートが存在するような故障に強いネットワークトポロジー（ｆａｕｌｔ−ｔｏｌｅｒａｎｔ ｎｅｔｗｏｒｋ ｔｏｐｏｌｏｇｙ）を構築するためのリレー配置問題を取り上げ、この問題に対する多項式時間近似アルゴリズム（ｐｏｌｙｎｏｍｉａｌ ｔｉｍｅ ａｐｐｒｏｘｉｍａｔｉｏｎ ａｌｇｏｒｉｔｈｍ）を提案している。しかし、これらの研究においては送信範囲や電力消費に大きく関係するＴＰＬの調整について考慮していない。他方、Ｃｏｒｒｅｉａら（上記非特許文献９参照）は通信と消費電力量を考慮してＴＰＬを決定する方法を提案している。しかし、彼らの研究においてはリレー配置を考慮していない。また、彼らの研究においてはネットワーク寿命についても考慮していない。
【００４０】
ＷＳＮの構築費用を考慮したモデルも提案されている。Ｋａｔｅｎｋａら（上記非特許文献１０参照）は平面上にセンサを配置する際に、配置するセンサ数と各センサに付随するコストを最小化する問題を取り上げている。Ｍｈａｔｒｅら（上記非特許文献１１参照）は通信と拘束有効範囲（ｃｏｖｅｒａｇｅ ｃｏｎｓｔｒａｉｎｔｓ）を考慮して、ノード設置費用とバッテリー設置費用の総和を最小化する問題に取り組んでいる。また、Ｃｈｅｎｇら（上記非特許文献１２参照）はＷＳＮ設置に必要なコストを、複数のＷＳＮ設置戦略を適用した場合の様々なシナリオにおいて算出・比較している。しかしながら、これらの研究においてはＷＳＮの運用費用について考慮していない。つまり、ＷＳＮを構築し運用する際に発生する総費用を最小にするためには、ＷＳＮの設置費用に加えてその運用費用につても考慮しなければならないが、これらの研究ではそれについて明白には触れていない。
【００４１】
既述のように、リレーの設置計画、ＴＰＬの設定計画、センシングデータのルート計画は互に密接に関係しており、それらを個別に計画しても総費用の最小化を保証することはできない。それゆえ、総費用が最小となるようにそれらを同時に計画する問題は、ＷＳＮの設計においても、そしてその運用においても極めて重要であると思われる。しかしながら、上で見たように、そのような問題は未だ取り扱われていない。
【００４２】
以下、本発明にかかるＷＳＮの設置及び運用費用評価方法のアルゴリズムについて詳述する。
まず、定式化（Ｆｏｒｍｕｌａｔｉｏｎ）を行う。
ここでは、センサの集合をＳ＝｛１，２, …, ｜Ｓ｜｝、リレー設置候補場所の集合をＲ＝｛｜Ｓ｜＋１, ｜Ｓ｜＋２, …, ｜Ｓ｜＋｜Ｒ｜｝とする。また、ゲートウェイを０で表し、各センサで収集したデータはマルチホップ通信でそこに伝送するものとする。また、Ｍ＝Ｓ∪Ｒ∪、Ｎ＝Ｓ∪Ｒ∪｛０｝とおき、ＭやＮについて考える場合はそれらの要素を特にノードと呼ぶ。また、各バッテリーで消費可能な最大電力量をバッテリー容量と呼び、ノードｉ∈Ｍのバッテリー容量をＥi とする。加えて、各センサと各リレーにおけるＴＰＬの集合をＰ＝｛１，２, …, ｜Ｐ｜｝とし、一般性を失うことなく、送信出力は１＜２＜…＜｜Ｐ｜の順序で大きくなるものとする。つまり、ＴＰＬ１が最小送信出力で、ＴＰＬ｜Ｐ｜が最大送信出力であるものとする。
【００４３】
ここで、伝送ルートとＴＰＬについて説明する。
あるノードｉ∈Ｍとあるノードｊ∈Ｎを考えると、ノードｉからノードｊへ（他のノードを経由しないで）直接送信できるノードｉにおけるＴＰＬの集合が定まる。そこで、
Ｐij：ノードｉ∈Ｍからノードｊ∈Ｎへ直接送信できる、ノードｉにおけるＴＰＬのｌ∈Ｐの集合
【００４４】
と定義する。そして、このＡをアーク集合とし、Ｎをノード集合とする有向グラフをＧ＝（Ｎ，Ａ）とする。ここで、｜Ｐij｜＞２である場合は、Ｇにはノードｉからノードｊへの｜Ｐij｜本のマルチプルアーク（ｍｕｌｔｉｐｌｅ ａｒｃ）が存在することに注意する。Ｇにマルチプルアークが存在する状況を図示すると図８のようになる。ただし、図８に関しては以下の通りであり、円形、三角、四角の意味は図７と同じである。
（１）図７のノード間に存在する全てのアークを図示した場合の例である。
（２）ｄ，ｅ，ｆのアークは、図７の場合と同様に、それぞれＴＰＬ１、２、３で送信できることを示している。
（３）双方向アークは、その両端のノードは相互に送信可能であることを示している。
【００４５】
この例においては、幾つかのノード間にマルチプルアークが存在する。例えば、ノード６からノード５へは２本のアーク（６，５，２）、（６，５，３）つまり、ノード６からノード５へＴＰＬ２で送信するアークと、ノード６からノード５へＴＰＬ３で送信するアークが、逆にノード５からノード６へも２本のアーク（５，６，２）、（５，６，３）が存在する。また、ノード６からノード０へは２本のアーク、（６，０，２）、（６，０，３）が存在する。なお、ノード０はゲートウェイであり、ゲートウェイは受信だけであるから、ノード０へのアークは全て片方向であることに注意。
【００４６】
あるセンサｉ∈Ｓを始ノードとし、ゲートウェイ０を終ノードとするＧ＝（Ｎ，Ａ）上のルートを特に伝送ルートと呼び、それをアークの集合で示す。このとき、Ｇにあるセンサを始ノードとする伝送ルートが存在しなければ、リレーをどのように配置しても、そのセンサからはゲートウェイにデータを送信することができない。そこで、Ｇには各センサを始ノードとする伝送ルートが少なくとも１本は存在するものとする。また以下では、Ｇにおけるノードｉ∈Ｍの入次数と出次数は共に１以上であると仮定する。つまり、ノードｉ∈Ｍは少なくとも他の１つのノードから受信可能で、かつ少なくとも他の１つのノードへ（あるＴＰＬで）送信可能であると仮定する。
【００４７】
と定義する。そして、この（ｘk ijl ）と（ｙil）をそれらに対応したルート案が実行可能であるように定めた場合について考える。つまり、それらを次のように定めた場合について考える。
【００４８】
（ｉ) 各ｋ∈Ｓについて｛（ｉ, ｊ, ｌ）∈Ａ｜ｘk ijl ＝１｝はノードｋからノード０へのルートである。すなわち、各センサを始ノードとする｜Ｓ｜個の伝送ルートが生成されている。
（ｉｉ) あるｘk ijl が１ならばｙil＝１である。すなわち、ある伝送ルートにアーク（ｉ, ｊ, ｌ）が含まれている場合は、ノードｉのＴＰＬがｌに設定されている。
（ｉｉｉ)あるｙilが１ならばｙil´＝０, ｌ´∈Ｐ＼｛ｌ｝である。すなわち、各ノードにおいてはＴＰＬが同時に２つ以上の水準に設定されていない。
【００４９】
次に、バッテリー交換作業費用について説明する。
各センサでは単位期間に１回データを収集し、それを処理後ゲートウェイへ伝送する。そこで、各センサで単位期間に収集するすべてのデータを、収集・処理し、受信し、送信するのに必要な電力量を次のように記す。
ｓk ：センサｋ∈Ｓでデータを収集・処理するのに必要な電力量
ｒk ：センサｋ∈Ｓで収集したデータを各ノードで受信するのに必要な電力量
ｔk l ：センサで収集したデータを各ノードからＴＰＬｌ∈Ｐで送信するのに必要な電力量
このとき、ノードｉ∈Ｍで単位期間に必要な電力量Ｆi （ｘ）は次のようになる。ただし、ｅi はｉ∈Ｓである場合はｅi ＝ｓi であり、ｉ∈Ｒである場合はｅi ＝０であるものとする。
【００５０】
【数１】
【００５１】
ここで、式 (１) の右辺第１項はデータの送信に、第２項はデータの受信に、そして第３項はセンサでデータを収集・処理するのに必要な電力量である。
上記式（１）によって各ノードで単位期間に必要な電力量が定まれば、その電力量と各ノードのバッテリー容量よりネットワーク寿命が定まる。つまり、ネットワーク寿命をｄ（ｘ）とすると、それはバッテリー容量Ｅi と式 (１) より次で定まる。
【００５２】
【数２】
【００５３】
加えて、１回当りのバッテリー交換作業費用をｃ1 、１Ｊ当りのバッテリー消費費用をｃ2 、リレーを１個設置した場合の単位期間当りの費用をｃ3 とする。ここで、容量がＥi Ｊであるバッテリーの価格がａi である場合はｃ2 ＝ａi ／Ｅi , ｉ∈Ｍと算出され（各バッテリーにおける１Ｊ当りのバッテリー消費費用は全て同一であるとしていることに注意）、リレー１個当たりの設置費用がｂで各リレーの使用可能期間がＴ期間である場合はｃ3 ＝ｂ／Ｔと算出される。また、１回当りのバッテリー交換作業費用がｃ1 で、ネットワーク寿命がｄ（ｘ）期間ならば、単位期間当りのバッテリー交換作業費用は（ｃ1 ／ｄ（ｘ））となる。つまり、式 (２) より
【００５４】
【数３】
【００５５】
であるから、単位期間当りのバッテリー交換作業費用は、次のようになる。
【数４】
【００５６】
定式化の準備の最後に、電力消費費用について説明する。
本発明においては、バッテリー交換作業において交換するバッテリーは、電力が枯渇したバッテリーと次の巡回までに電力が枯渇するバッテリーだけで、次の巡回まで寿命のあるバッテリーは交換しないで良いものとした。
【００５７】
となる。しかしながら、上式はかなり煩雑でこのままでは取り扱いが困難である。そこで、ここでは、式 (５) のフロア関数を緩和し、式 (５) の分母は
〔Ｅi ／Ｆi （ｘ）〕・〔１／ｄ（ｘ）〕・ｄｘ
であるものと近似する。すると、ノードｉ∈Ｍのバッテリーの単位期間当たりの電力消費費用は、
【００５８】
【数５】
となる。つまり、ノードｉ∈Ｍのバッテリーの単位期間当たりの電力消費費用はｃ2 ・Ｆi （ｘ）となる。
【００５９】
このとき、さらに変数ｚを導入すると、単位期間当たりの総費用が最小となるようにＷＳＮを設計する問題は、次のような混合整数計画問題（ｍｉｘｅｄ ｉｎｔｅｇｅｒ ｐｒｏｇｒａｍｍｉｎｇ ｐｒｏｂｌｅｍ）に定式化される。
【００６０】
【００６１】
ｘk ijl ≦ｙil, （ｉ, ｊ, ｌ）∈Ａ，ｋ∈Ｓ …（１１）
【数６】
ｘk ijl ∈｛０，１｝, ｛ｉ, ｊ, ｌ｝∈Ａ，ｋ∈Ｓ …（１３）
ｙil∈｛０，１｝, ｉ∈Ｍ，ｌ∈Ｐ …（１４）
【００６２】
ここで、目的関数である式（７）の第１項はバッテリー交換作業費用、第２項はネットワーク内の総バッテリー消費費用、第３項はリレー設置費用である。また式 (８) は、目的関数の第１項は式 (４) の右辺と等価であることを保証する。また、式 (９) と式 (１０) は前述の（ｉ) を、式 (１１) は前述の（ｉｉ) を、そして式 (１２) は前述の（ｉｉｉ) を保証する。〔（ｉ）〜（ｉｉｉ)については、伝送ルートとＴＰＬの定式化の説明部分を参照〕。なお、ノードｉ∈Ｒには、それが生成された何れかの伝送ルートに含まれている場合に限りリレーを設置することになる。また、式 (３) よりｚの最小化はネットワーク寿命ｄ（ｘ）の最大化と等価である。よって、上述の問題 (Ｐ) はｃ1 ＝１としｃ2 ＝ｃ3 ＝０とすればネットワーク寿命を最長化する問題となる。また、ｃ2 ＝１、ｃ1 ＝ｃ3 ＝０とし、そしてバッテリー容量Ｅi ＝∞, ｉ∈Ｍとすれば、問題 (Ｐ) はネットワーク内の総電力使用量を最小化する問題となる。
【００６３】
上記問題 (Ｐ) は明らかにＮＰ困難な問題であり、実際問題の多くは、その最適解を求めるのは困難であると思われる。それゆえ、実際問題に対しては、メタヒューリスティックス（ｍｅｔａｈｅｕｒｉｓｔｉｃｓ）や欲張りアルゴリズム（ｇｒｅｅｄｙ ａｌｇｏｒｉｔｈｍ）などの近似解法が必要となるが、それらの近似解法では求めた解が最適解にどれだけ近似しているかを評価できない場合が多い。つまり、それらの近似解法では下界値を算出していないため、多くの場合、求めた解を相対誤差（（上界値−下界値）／下界値）で評価することができない。これに対して、求めた解を相対誤差で評価できる方法に、ラグランジアン・ヒューリスティック法（Ｌａｇｒａｎｇｉａｎ ｈｅｕｒｉｓｔｉｃ ｍｅｔｈｏｄ）がある。この方法は、上界値と下界値の差を順次減少させながら対象問題の近似最適解を求める方法であり、実際規模の問題にも適用可能である。また、この方法によればラグランジュ緩和問題（Ｌａｇｒａｎｇｉａｎ ｒｅｌａｘａｔｉｏｎ ｐｒｏｂｌｅｍ）の最適解を利用して対象問題の近似解を効率的に探索することができる。そこで以下では、このラグランジアン・ヒューリスティック法に基づく問題 (Ｐ) の近似最適解法（求めた解を相対誤差で評価できる解法）について考える。
【００６４】
ラグランジアン・ヒューリスティック法は、概略、次のような手順を繰り返し実行して、原問題の近似最適解（ｎｅａｒ−ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ）を求める方法である。ただし、原問題は最小化問題とする。
【００６５】
〔手順１〕
Ｓ１．原問題のラグランジュ緩和問題を解いて、原問題の下界値を求める。
Ｓ２．ラグランジュ緩和問題の最適解を利用して、原問題の可能解とその目的関数値（上界値）を求める。
Ｓ３．上界値と下界値を用いて相対誤差を算出する。相対誤差あるいは計算時間が所与の終了条件を満たしたならば計算を終了する。
Ｓ４．ラグランジュ乗数（Ｌａｇｒａｎｇｉａｎ ｍｕｌｔｉｐｌｉｅｒｓ）を適切な方法で更新して、Ｓ１に戻る。
【００６６】
したがって、上記Ｓ１、Ｓ２、Ｓ４を実行する具体的な方法を示せば、問題 (Ｐ) のラグランジアン・ヒューリスティック法に基づく近似最適解法が構築される。そこで以下では、上記Ｓ１、Ｓ２、Ｓ４を実行する方法について順次説明する。
まず、下界値の決定について説明する。
ここでは、上記手順１のＳ１に示した、ラグランジュ緩和問題を解いて問題 (Ｐ) の下界値を生成する方法について説明する。
【００６７】
ラグランジュ乗数ｕ＝（ｕi ）＞０, ｉ∈Ｍを用いて式 (８) を、ラグランジュ乗数ｖ＝（ｖk ijl ）＞０, （ｉ, ｊ, ｌ）∈Ａ, ｋ∈Ｓ を用いて式 (１１) を、問題 (Ｐ) の目的関数に組み込み、それを整理すると次のようになる。
【００６８】
【数７】
【００６９】
よって、上式の変数（ｘk ijl ）との（ｙil）に注目して、
【００７０】
とおくと、次のような問題 (Ｐ) のラグランジュ緩和問題を得る。
【数８】
【００７１】
ここで、問題（・）の最適値をｃ（・）で記すと、ラグランジュ緩和法の原理よりｃ（Ｌ（ｕ, ｖ））＜ｃ（Ｐ）が成り立つ（上記非特許文献１３，１４参照）。つまり、問題（Ｌ（ｕ, ｖ））の最適値が問題 (Ｐ) の下界値を与える。
ところで、問題（Ｌ（ｕ, ｖ））の変数ｚには非負条件が付いていない。それゆえ、最小化問題（Ｌ（ｕ, ｖ））においては、目的関数におけるｚの係数が正の場合にはｚ＝−∞とし、それが負の場合にはｚ＝＋∞とすると、問題ｃ〔Ｌ（ｕ, ｖ）〕の目的関数値＝−∞となる。つまり、ｚの係数が非ゼロの場合は、問題 (Ｐ) の有意な下界値を得ることができない。そこで以下では、（ｕi ）は
【００７２】
【数９】
【００７３】
である場合に限定する。式 (１７) より（Ｌ（ｕ, ｖ））の目的関数の第１項は消える。よって、問題は（Ｌ（ｕ, ｖ））は、（ｘk ijl ）に関する
【００７４】
となる。ここで、（ＬＸ（ｕ, ｖ））におけるｋ∈Ｓをあるｋに固定した場合の問題を（ＬＸk （ｕ, ｖ））とすると、（ＬＸ（ｕ, ｖ））はさらに｜Ｓ｜個の問題（ＬＸk （ｕ, ｖ））, ｋ∈Ｓに分解される。そして、各（ＬＸk （ｕ, ｖ））は明らかにノードｋからノード０への最短ルート問題である。他方、（ＬＹ（ｖ））におけるｉ∈Ｍをあるｉに固定した場合の問題を（ＬＹi （ｖ））とすると、問題（ＬＹ（ｖ））もさらに｜Ｍ｜個の問題（ＬＹi （ｖ））, ｉ∈Ｍに分解され、そして各（ＬＹi （ｖ））は明らかに自明な問題である。よって、ラグランジュ緩和問題の（Ｌ（ｕ, ｖ））最適値は、つまり問題 (Ｐ) の下界値は、｜Ｓ｜個の最短ルート問題と｜Ｍ｜個の自明な問題を解くと
【００７５】
【数１０】
で求めることができる。ここで、最短ルート問題については、その最適解を多項式時間で求めるアルゴリズムが既に数多く提示されている（上記非特許文献１５，１６参照）。
【００７６】
次に、手順１のＳ２に示した、上界値（可能解）の決定について説明する。
ここでは、ラグランジュ緩和問題（ＬＸ（ｕ, ｖ））の最適解を利用して、問題 (Ｐ) の可能解を求める方法について説明する。
【００７７】
【００７８】
である。ただし、βはＢ（ｉ）, ｉ∈Ｍの和集合である。例えば、図９の場合は、Ｂ（２）＝｛（２，５）, （２，６）｝, Ｂ（４）＝｛（４，０）｝、Ｓ（２，５）＝｛１｝, Ｓ（４，０）＝｛２，４｝などのようになる。
【００７９】
そこで、以下の手順で可能解を決定する。
【００８０】
【００８１】
【００８２】
【００８３】
そこで、以下の手順で可能解を改善する。
【００８４】
次に、手順１のＳ４に示した、ラグランジュ乗数の更新について説明する。
問題（Ｐ）の下界値ｃ〔Ｌ（ｕ, ｖ）〕は、当然のことながら、ラグランジュ乗数ｕ＝（ｕi ）、ｖ＝（ｖk ijl ）に依存する。それゆえ、問題 (Ｐ) のよりよい下界値を求めるためにはｃ〔Ｌ（ｕ, ｖ）〕が最大となるようなｕ, ｖを求めることが望まれる。他方、そのようなラグランジュ乗数を漸近的に求める方法によく知られた劣勾配法がある（上記非特許文献１７参照）。この方法は、これまでに種々の組合せ最適化問題に適用され、その有効性が多くの研究で検証されている（上記非特許文献１８、１９参照）。そこでここでは、この劣勾配法でｃ〔Ｌ（ｕ, ｖ）〕が最大となるようなラグランジュ乗数を漸近的に求めるものとする。すなわち、次の手順でラグランジュ乗数ｕ, ｖを逐次更新するものとする。
【００８５】
【００８６】
そこで、以下の手順でラグランジュ乗数の設定を行う。
Ｓ４−１．ｃ（Ｌ（ｕ, ｖ））の（ｕi ）, （ｖk ijl ）における劣勾配（λi ）, （μk ijl ）を次で定める。
【００８７】
Ｓ４−２．ステップレングスρ, σを次で定める。
【００８８】
Ｓ４−３．乗数（ｕi ）, （ｖk ijl ）を次で更新する。
ｕi ：＝ｍａｘ｛０, ｕi ＋ρλi ｝, ｉ∈Ｍ
ｖk ijl ：＝ｍａｘ｛０, ｖk ijl ＋σμk ijl ｝, （ｉ, ｊ, ｌ）∈Ａ, ｋ∈Ｓ
【００８９】
Ｓ４−４．乗数（ｕi ）を次で調整する。
【数１１】
【００９０】
なお、この手順のＳ４−４は、（ｕi ）が式 (１７) を満たすように調整するためのものである。また、劣勾配法においては、多くの場合、ステップレングスをρ＝σとする。そして、それを次のように定める場合が多い。
【００９１】
【数１２】
【００９２】
しかし、ステップレングスを上式で定めると、（μk ijl ）に比して（λi ）がステップレングスの値の決定により強く反映してしまう懸念がある。つまり、Ｓ１における劣勾配法の決定方法より−１＜μk ijl ＜１であるから、λi ≫１である場合には、（μk ijl ）に対して（λi ）だけがステップレングスの決定により大きく反映してしまう懸念がある。そこで本発明では、ステップレングスρとσをＳ２で別々に定めるものとする。したがって、ここでの劣勾配法は正確には修正劣勾配法である。
以上のようなアルゴリズムで、ＷＳＮの設置及び運用費用の評価を行う。
【００９３】
上記してきた本発明にかかるＷＳＮの設置及び運用費用の評価方法の有効性を検証するための、実例を用いた計算実験を以下に示す。
上記したように、ロンドン地下鉄のジュビリー線には、トンネル内の状態監視のためのＷＳＮが既に設置されている。そこでここでは、既設のＷＳＮの条件の下、本発明のＷＳＮの設置及び運用費用の評価方法で設計した場合のＷＳＮ案を作成し、それと現在のＷＳＮとの比較検証を行う。また、ロンドン地下鉄のＷＳＮに設置するセンサ数を、現在よりも増やした場合（図６に示した拡張ＷＳＮと対応）に、総費用がどのように変化するかを検証するための計算実験も行う。なお、ロンドン地下鉄の現在のＷＳＮには、２６個のセンサ（傾斜計６台、クラックメータ１６台、環境センサ４台）と１台のゲートウェイが設置されている（図１３参照）。
【００９４】
以下の計算実験においては、データの送信・受信電力と他の各費用に関する電力消費パラメータを次のように定めた。
・各センサでは５秒に１回データを取得するものとした。つまり、各センサの単位期間は５秒とした。
・各センサでデータを収集・処理するのに必要な電流値、電圧値、収集・処理時間は全て同一で、それぞれ７ｍＡ、３Ｖ、０．２５秒であるとした。つまりｓk ＝５．２５×１０-3 (Ｊ) , ｋ∈Ｓとした。
・各センサで収集したデータを受信するのに必要な電流値、電圧値、受信時間は各センサとリレーで全て同一で、それぞれ１９．７ｍＡ、３Ｖ、０．５秒であるとした。つまりｒk ＝２９．５５×１０-3 (Ｊ) , ｋ∈Ｓとした。
・ＴＰＬは１ (−２５ｄＢｍ）、２ (−１０ｄＢｍ) 、３ (０ｄＢｍ）の３水準とし、それぞれの電流値は４ｍＡ、１１ｍＡ、１７．４ｍＡであるとした。また、各センサで収集したデータを送信するのに必要な電圧値、送信時間は各センサとリレーで全て同一で、それぞれ３Ｖ、０．５秒であるとした。つまり、各ｋ∈Ｓについてｔ1 k ＝６．０×１０-3(Ｊ) 、ｔ2 k ＝１６．５×１０-3 (Ｊ) 、ｔ3 k ＝２６．１×１０-3 (Ｊ) とした。
・１回当たりのバッテリー交換作業費用ｃ1 は、各問題例のセンサ数に応じて個別に定めた。
・各センサと各リレーでは５０Ａｈ、３Ｖのバッテリーを使用するものとし、その価格は２００（£) であるとした。つまり、Ｅi ＝５．４×１０5 （Ｊ）, ｉ∈Ｍとしｃ2 ＝３．７×１０-4 (£／Ｊ) とした。
・リレーの設置費用は１台当たり４００（£) とし、各リレーの使用可能期間は１０年とした。つまり、ｃ3 ＝６．３４×１０-6 (£／ｕｎｉｔ ｐｅｒｉｏｄ) とした。
【００９５】
また、以下での計算実験は全て次のような環境の下で実施した。
・ロンドン地下鉄のジュビリー線のトンネルに関しては、各ＴＰＬで与えられたノード間の無線通信が可能かを判定できる経験モデル（ｅｍｐｉｒｉｃａｌ ｍｏｄｅｌ）（上記非特許文献２０参照）が既に提示されている。そこで、ノードｉからノードｊへ送信できる（ノードｉにおける）ＴＰＬの集合Ｐijは、それを用いて定めた。
・ゲートウェイは現在のロンドン地下鉄と同じ位置に設置されているものとした。つまり、ゲートウェイは全て図１３におけるトンネルの一端から２７．６ｍ離れた位置のリングのセグメントＢに設置されているものとした。
・ラグランジュ乗数の初期値はｕi ＝１／｜Ｍ｜, ｉ∈Ｍとし、ｖijl k ＝１／（｜Ａ｜×｜Ｓ｜）, （ｉ, ｊ, ｌ）∈Ａ, ｋ∈Ｓとした。
・本発明のアルゴリズムの終了条件は計算時間（ｓｅｃｏｎｄ）の最大許容値とし、各計算実験の計算時間はその実験における問題例のセンサ数に応じて定めた。
・使用計算機言語はＣ言語で、使用計算機の仕様はＷｉｎｄｏｗｓ ＸＰ(登録商標）、３．６ＧＨｚ、２．９９ＧＢ ＲＡＭである。
【００９６】
なお、ロンドン地下鉄のＷＳＮにおいては、現在、リレーを使用していない。また、ＴＰＬの調整については未だ検討段階であり、現在、通信の確保を優先して各センサのＴＰＬは全て最大送信出力の３（０ｄＢｍ）に固定して通信を行っている。そこで、リレーを設置すべきかどうかの検証と、ＴＰＬを調整した場合の効果を検証するために、先ず次のような場合について実験を行った。
【００９７】
(１) リレーは設置しない。各ノードのＴＰＬは全て水準３に固定。
(２) リレーは設置しない。各ノードのＴＰＬは調整可能。
(３) リレーの設置を検討。各ノードのＴＰＬは全て水準３に固定。
(４) リレーの設置を検討。各ノードのＴＰＬは調整可能。
ここで上記 (１) は、現在のＷＳＮを本発明のアルゴリズムを用いて評価するための実験である。また上記 (３) 、 (４) におけるリレー設置候補場所は、図１３におけるトンネルの一端から６．６、９．６、１２．６、１５．６、１８．６、２２．８、２４．６、３０．６、３３．６、３９．６ｍ離れた位置のリングのセグメントＡ，Ｃ，Ｅ，Ｇ，Ｊ，Ｌ，Ｎとした。したがって、リレー設置候補場所数は１０×７＝７０箇所となる。また、これらの実験においては、巡回１回当たりのバッテリー交換作業費用は全てｃ1 ＝２００（£) とし、計算時間を３００ｓとした。
【００９８】
上記 (１) 〜 (４) の場合の実験結果を表１に示す。ただし、表１と以下で示す表２に関しては以下の通りである。
（ｉ）｜Ｓ｜は設置センサ数、｜Ｒ｜はリレー設置候補場所数である。したがって、｜Ｒ｜＝０である場合はリレーを設置できないことを示している。
（ii) ＴＰＬに関しては、各ノードのＴＰＬが全て最大出力水準に固定されている場合は３とし、それを調整可能な場合は１，２，３としている。
（iii) ｃU とｃL は、それぞれ本発明のアルゴリズムで得られた最良の上界値（£／ｄａｙ）、下界値（£／ｄａｙ）である。ここで、ｃU とｃL は単位期間当たりではなく、１日当たりに換算していることに注意する。
（iv）ｅｒｒｏｒは相対誤差で、（ｃU −ｃL ）／ｃL である。
（v)ｌｉｆｅｔｉｍｅは得られたＷＳＮのネットワーク寿命（日数：ｄａｙ）で、ｒｅｌａｙは設計されたＷＳＮにおいて設置するリレーの数である。
【００９９】
(vi) ｉｔｅｒａｔｉｏｎはラグランジアン・ヒューリスティック法の繰返し回数、ｔｉｍｅは計算時間（ｓｅｃｏｎｄ）である。
また、上記手順３では可能解を改善するために確率変数を利用しているので、同一の問題例でも計算結果が異なる場合が存在する。そこで、同一の問題例を５回解いた。したがって、表１と表２の値は５回の解の平均値である。
【０１００】
そのため表１及び表２のＣU ，ＣL ，“ｅｒｒｏｒ”，“ｌｉｆｅｔｉｍｅ”，“ｒｅｌａｙ”，“ｉｔｅｒａｔｉｏｎ”の値は整数でないものがある。
【０１０１】
【表１】
【０１０２】
現在のＷＳＮは、問題 (Ｐ) の１つの可能解であると見なすことができる。それゆえ、現在のＷＳＮに対応した、（ｘijl k ）、（ｙil）を定めると（ｚは（ｘijl k ）より定まることに注意）、それより現在のＷＳＮに対する問題 (Ｐ) の目的関数値が求まる。そこで、現在のＷＳＮに対する問題 (Ｐ) の目的関数値（上界値Ｃu ）を求めて見ると、１０．４０３５（£／ｄａｙ）となる。他方、本発明のアルゴリズムで求めた、現在のＷＳＮ（表１の第１行）に対する下界値Ｃu は９．２９３１である。つまり、本発明のアルゴリズムで求めた下界値Ｃu より、現在のＷＳＮの総費用は改善できたとしても１０．４０３５−９．２９３１＝１．１１０４（£／ｄａｙ）であることが分かる。そしてこれより、「各センサのＴＰＬは全て３に固定」という前提の下では、現在のＷＳＮは比較的良好なＷＳＮであると評価することができる。なお表１の第１行より、本発明のアルゴリズムで求めたＷＳＮの上界値も、現在のＷＳＮのそれに等しく１０．４０３５（これが最適値である場合もあり得ることに注意）である。これは、ＴＰＬを全て最大送信出力の３に固定していることに加えて、設置センサ数が２６と比較的少ないことから、本発明のアルゴリズムにおいても現在のＷＳＮとほぼ同様な伝送ルート案が出力されたためである。
【０１０３】
上述のように、ＴＰＬを全て３に固定した場合は、現存のＷＳＮを改善できる余地は少ないと思われる。しかしながら表１をみると、ＴＰＬを調整すると現存のＷＳＮをさらに改善できることを示している。すなわち表１の第２行は、ＴＰＬを調整すると、総費用を８．９９２３（£／ｄａｙ）に改善できる上に、ネットワーク寿命も１２３．０６日から２１９．０７日に大きく改善できることを示している。また表１の第３、４行からは、現在のＷＳＮに新たにリレーを設置する必要はないことがみてとれる。これは、各センサからの伝送ルートをリレーを使用しなくても確保できたことや、設置センサ数が比較的少ないために、リレーを使用しなくても各センサでの消費電力量をある程度平準化できたためであると推察される。
【０１０４】
図１０は、本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮの出力結果の１例（表１の第４行の｜Ｒ｜＝７０でＴＰＬが１，２，３である場合）である。ただし、図１０と以下に示す図１１、１２において、円はセンサを、三角はリレーを示している。また、各センサと各リレーで設定するＴＰＬを区別し、ｉ、ii、iii はそれぞれＴＰＬを1 、2 、3 に設定することを示している（ここで、ｉ、ii以外はiii であり、iii は数が多いので表記していない。なお、本図は図５（ｂ）と同じ図である）。また、四角はゲートウェイで、線は伝送ルートを構成するアークである。
【０１０５】
図１０には、同じ位置での上部と下部の間の通信が、つまりトンネル内の片方の側壁から他方の側壁への通信がいくつか存在する。これは、トンネル内の無線通信においては、同じサイドに設置されているノード間よりも、異なるサイドに設置されているノード間の方が、一般的に通信を確立し易いためであると思われる。事実、ロンドン地下鉄のジュビリー線のトンネル内で実施された無線通信試験においても、そのような傾向にあることが確認されている。
【０１０６】
前述のように、設置センサ数が２６である現在のＷＳＮにおいては、リレー使用の効果を確認することができなかった。そこで、設置センサを現在のＷＳＮよりも増やした場合の実験を行った（図６の拡張ＷＳＮに対応）。ただし、この実験においては、現在配置されている２６個のセンサに加えて、図１３におけるトンネルの一端から３．６、９．６、１５．６、１８．６、２４．６、３９．６ｍ離れた位置のリングのセグメントＣ，Ｅ，Ｊ，Ｌにさらに２４個のセンサが設置されている場合と、トンネルの一端から３．６、６．６、９．６、１５．６、１８．６、２１．６、２４．６、３３．６、３９．６、４２．６ｍ離れた位置のリングのセグメントＡ，Ｃ，Ｅ，Ｇ，Ｊ，Ｌ，Ｎにさらに７０個のセンサが設置されている場合について実験を行った。つまり、｜Ｓ｜＝５０である場合と、｜Ｓ｜＝９６である場合について実験を行った。他方、リレー設置候補場所は、｜Ｓ｜＝５０である場合はトンネルの一端から３．６、６．６、９．６、１５．６、１８．６、２４．６、３３．６、３９．６、４２．６ｍ離れた位置のリングのセグメントＢ，Ｄ, Ｆ，Ｈ，Ｋ，Ｍに５４箇所とし、｜Ｓ｜＝９６である場合はトンネルの一端から３．６、６．６、９．６、１５．６、１８．６、２４．６、３３．６、３９．６、４２．６ｍ離れた位置のリングのセグメントＢ，Ｄ, Ｆ，Ｈ，Ｋ，Ｍに５４箇所と、トンネルの一端から２１．６ｍ離れた位置のリングのセグメントＤ, Ｆ，Ｈ，Ｋに４箇所の計５８箇所とした。また、バッテリー交換作業費用ｃ1 は｜Ｓ｜＝５０である場合は３００（£) とし、｜Ｓ｜＝９６である場合は５００（£) とした。さらに計算時間は、｜Ｓ｜＝５０である場合は６００秒とし、センサ数がその約２倍の｜Ｓ｜＝９６である場合は１２００秒とした。
【０１０７】
上記の場合の実験結果を表２に示す。また、この実験について本発明にかかるＷＳＮの設置及び運用費用評価方法により評価・構築されたＷＳＮの出力結果の例を図１１（表２の第４行の｜Ｓ｜＝５０、｜Ｒ｜＝５４でＴＰＬが１，２，３である場合）、図１２（表２の最終行の｜Ｓ｜＝９６、｜Ｒ｜＝５８でＴＰＬが１，２，３である場合）に示す。なお、図１２は図６（ｂ）と同じ図である。
【０１０８】
【表２】
【０１０９】
表２に示された結果より、リレーの設置を考慮すると上界値を低減できること、そしてＴＰＬを調整するとそれを更に改善できることがわかる。例えばセンサが５０個の場合、上界値ＣU は３２．４１４８（£／ｄａｙ）から３０．８２２３（£／ｄａｙ）へ低減されることを示している。また表２は、リレーの設置とＴＰＬの調整を同時に考慮すると、総費用をより低減できることを示している。さらに表２は、リレーの設置とＴＰＬの調整が、ｌｉｆｅｔｉｍｅの長期化にも有効であることを示唆している。さらに表２における相対誤差は、多少バラツキがあるもののその平均値は０．０８２８である。これより、この実験で取り上げた規模の問題であれば、本発明のアルゴリズムで比較的良好な可能解が求まることが分かる。なお表２において、｜Ｓ｜＝５０、｜Ｒ｜＝５４である場合のｌｉｆｅｔｉｍｅが、ＴＰＬを固定した場合よりもそれを調整した場合の方が短くなっているのは、本発明のアルゴリズムがライフタイムの長期化よりも総費用の最小化を優先しているためである（事実、総費用はＴＰＬを調整した方が少なくなっている）。また図１１，１２において、左右方向に比較的長い距離の通信が発生しているのは、あるノードから送信する際の消費電力量は送信先のノードまでの距離ではなく、そのノードで設定するＴＰＬの水準に依存することが大きく関係しているものと思われる。
【０１１０】
なお、本発明は上記実施例に限定されるものではなく、本発明の趣旨に基づき種々の変形が可能であり、これらを本発明の範囲から排除するものではない。
【産業上の利用可能性】
【０１１１】
本発明の対象構造物の無線センサネットワークの設置及び運用費用評価方法は、埋没費用と考えられるセンサとゲートウェイの設置費用を除いた、初期設置費用（リレー設置費用）と運用費用（バッテリー消費費用、バッテリー交換作業費用）の費用の最小化を図ることができる無線センサネットワークの設置及び運用費用評価方法に利用することができる。
【符号の説明】
【０１１２】
１ トンネル
２ 軌道
３ センサ
４ ゲートウェイ
５ 携帯電話網
６ 管理局
【特許請求の範囲】
【請求項１】
対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び／又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、該バッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法に基づく近似最適解法を用いてセンサネットワークの設計をすることを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。
【請求項２】
請求項１記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記対象構造物が、鉄道土木構造物であることを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。
【請求項３】
請求項２記載の対象構造物の状態監視のための無線センサネッ トワークの設置及び運用費用評価方法において、前記総和の最小化を行うためリレーの設置数とその設置場所、各センサと各リレーにおける送信電力レベル、前記センサからのデータを前記ゲートウェイにマルチホップで送信するための伝送経路を同時に設定することを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。
【請求項４】
請求項３記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記センサと前記ゲートウェイの設置場所と、前記リレー設置候補場所と、各種電力情報と、各種費用情報を入力情報として与え、前記リレーの設置費用と前記バッテリーの消費費用と前記バッテリーの交換作業費用との総和が最小になるような前記リレーの設置場所と、前記データの伝送経路と、前記センサと前記リレーの送信電力レベル、前記無線センサネットワーク１日あたりの費用と、ネットワーク寿命を出力し、これに基づき前記無線センサネットワークを構築することを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。
【請求項１】
対象構造物内に配置された複数のセンサで得られたデータをこのセンサ及び／又はリレーでゲートウェイに転送し、その転送されたデータを管理局にて収集する無線センサネットワークに関して、前記リレーの設置費用と、前記センサと前記リレーを駆動するバッテリーの消費費用と、該バッテリーの交換作業費用との総和を最小とするために、前記総和の最小化を数理計画問題に定式化した後、ラグランジアン・ヒューリスティック法に基づく近似最適解法を用いてセンサネットワークの設計をすることを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。
【請求項２】
請求項１記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記対象構造物が、鉄道土木構造物であることを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。
【請求項３】
請求項２記載の対象構造物の状態監視のための無線センサネッ トワークの設置及び運用費用評価方法において、前記総和の最小化を行うためリレーの設置数とその設置場所、各センサと各リレーにおける送信電力レベル、前記センサからのデータを前記ゲートウェイにマルチホップで送信するための伝送経路を同時に設定することを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。
【請求項４】
請求項３記載の対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法において、前記センサと前記ゲートウェイの設置場所と、前記リレー設置候補場所と、各種電力情報と、各種費用情報を入力情報として与え、前記リレーの設置費用と前記バッテリーの消費費用と前記バッテリーの交換作業費用との総和が最小になるような前記リレーの設置場所と、前記データの伝送経路と、前記センサと前記リレーの送信電力レベル、前記無線センサネットワーク１日あたりの費用と、ネットワーク寿命を出力し、これに基づき前記無線センサネットワークを構築することを特徴とする対象構造物の状態監視のための無線センサネットワークの設置及び運用費用評価方法。
【図３】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１】
【図２】
【図４】
【図５】
【図６】
【図１３】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１】
【図２】
【図４】
【図５】
【図６】
【図１３】
【公開番号】特開２０１３−１０９４３１（Ｐ２０１３−１０９４３１Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５２２０２（Ｐ２０１１−２５２２０２）
【出願日】平成２３年１１月１８日（２０１１．１１．１８）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ｈｔｔｐ：／／ｗｗｗ．ｓｃｉｅｎｃｅｄｉｒｅｃｔ．ｃｏｍ／ｓｃｉｅｎｃｅ？＿ｏｂ＝ＡｒｔｉｃｌｅＬｉｓｔＵＲＬ＆＿ｍｅｔｈｏｄ＝ｌｉｓｔ＆＿ＡｒｔｉｃｌｅＬｉｓｔＩＤ＝１８４６７１５０２５＆＿ｓｏｒｔ＝ｒ＆＿ｓｔ＝４＆＿ａｃｃｔ＝Ｃ０００２２８５９８＆＿ｖｅｒｓｉｏｎ＝１＆＿ｕｒｌＶｅｒｓｉｏｎ＝０＆＿ｕｓｅｒｉｄ＝１０＆ｍｄ５＝３７ｂｆｃ６９９ｅ７ｂｃｂ９ｄ３１ｃ９５ｃ３９ａｅｄ０ｄ４９ｄ０＆ｓｅａｒｃｈｔｙｐｅ＝ａ（平成２３年６月２３日）
【出願人】（０００１７３７８４）公益財団法人鉄道総合技術研究所 (1,666)
【Ｆターム（参考）】
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月１８日（２０１１．１１．１８）
【新規性喪失の例外の表示】特許法第３０条第１項適用申請有り ｈｔｔｐ：／／ｗｗｗ．ｓｃｉｅｎｃｅｄｉｒｅｃｔ．ｃｏｍ／ｓｃｉｅｎｃｅ？＿ｏｂ＝ＡｒｔｉｃｌｅＬｉｓｔＵＲＬ＆＿ｍｅｔｈｏｄ＝ｌｉｓｔ＆＿ＡｒｔｉｃｌｅＬｉｓｔＩＤ＝１８４６７１５０２５＆＿ｓｏｒｔ＝ｒ＆＿ｓｔ＝４＆＿ａｃｃｔ＝Ｃ０００２２８５９８＆＿ｖｅｒｓｉｏｎ＝１＆＿ｕｒｌＶｅｒｓｉｏｎ＝０＆＿ｕｓｅｒｉｄ＝１０＆ｍｄ５＝３７ｂｆｃ６９９ｅ７ｂｃｂ９ｄ３１ｃ９５ｃ３９ａｅｄ０ｄ４９ｄ０＆ｓｅａｒｃｈｔｙｐｅ＝ａ（平成２３年６月２３日）
【出願人】（０００１７３７８４）公益財団法人鉄道総合技術研究所 (1,666)
【Ｆターム（参考）】
[ Back to top ]