TOP > 国内特許検索 > 位置推定装置 > 明細書

明細書 :位置推定装置

発行国 日本国特許庁(JP)
公報種別 再公表特許(A1)
発行日 平成31年2月28日(2019.2.28)
発明の名称または考案の名称 位置推定装置
国際特許分類 G01S   5/02        (2010.01)
H04W  64/00        (2009.01)
H04W  84/18        (2009.01)
FI G01S 5/02 Z
H04W 64/00
H04W 84/18
国際予備審査の請求
全頁数 61
出願番号 特願2018-518315 (P2018-518315)
国際出願番号 PCT/JP2017/018411
国際公開番号 WO2017/199972
国際出願日 平成29年5月16日(2017.5.16)
国際公開日 平成29年11月23日(2017.11.23)
優先権出願番号 2016099547
優先日 平成28年5月18日(2016.5.18)
優先権主張国 日本国(JP)
指定国 AP(BW , GH , GM , KE , LR , LS , MW , MZ , NA , RW , SD , SL , ST , SZ , TZ , UG , ZM , ZW) , EA(AM , AZ , BY , KG , KZ , RU , TJ , TM) , EP(AL , AT , BE , BG , CH , CY , CZ , DE , DK , EE , ES , FI , FR , GB , GR , HR , HU , IE , IS , IT , LT , LU , LV , MC , MK , MT , NL , NO , PL , PT , RO , RS , SE , SI , SK , SM , TR) , OA(BF , BJ , CF , CG , CI , CM , GA , GN , GQ , GW , KM , ML , MR , NE , SN , TD , TG) , AE , AG , AL , AM , AO , AT , AU , AZ , BA , BB , BG , BH , BN , BR , BW , BY , BZ , CA , CH , CL , CN , CO , CR , CU , CZ , DE , DJ , DK , DM , DO , DZ , EC , EE , EG , ES , FI , GB , GD , GE , GH , GM , GT , HN , HR , HU , ID , IL , IN , IR , IS , JP , KE , KG , KH , KN , KP , KR , KW , KZ , LA , LC , LK , LR , LS , LU , LY , MA , MD , ME , MG , MK , MN , MW , MX , MY , MZ , NA , NG , NI , NO , NZ , OM , PA , PE , PG , PH , PL , PT , QA , RO , RS , RU , RW , SA , SC , SD , SE , SG , SK , SL , SM , ST , SV , SY , TH , TJ , TM , TN , TR , TT , TZ
発明者または考案者 【氏名】滝沢 泰久
【氏名】北之馬 貴正
出願人 【識別番号】399030060
【氏名又は名称】学校法人 関西大学
個別代理人の代理人 【識別番号】100125704、【弁理士】、【氏名又は名称】坂根 剛
審査請求
テーマコード 5J062
5K067
Fターム 5J062AA08
5J062AA09
5J062CC11
5J062DD23
5K067EE02
5K067EE25
5K067JJ51
要約 【課題】無線ノードの位置を高精度に推定可能な位置推定装置を提供することを課題とする。
【解決手段】位置推定装置5において、位置更新部63は、各固定ノードの配置関係を示す固定トポロジと各固定ノードの仮の自己位置とに基づいて、各固定ノードの推定位置を取得する。トポロジ矛盾判定部65は、固定トポロジに基づく各固定ノードの推定位置を用いて、トポロジ矛盾の発生頻度を示す領域判定値を計算する。仮想トポロジ生成部66は、固定ノード間の無線通信距離を仮想的に変更することにより仮想トポロジを生成する。仮想トポロジ生成部66は、固定トポロジに対応する領域判定値と、複数の仮想トポロジに対応する複数の領域判定値とに基づいて、固定トポロジ及び複数の仮想トポロジの中からいずれか1つのトポロジを特定し、特定したトポロジに基づく各固定ノードの推定位置を、各固定ノードの位置推定結果として出力する。
【選択図】図7
特許請求の範囲 【請求項1】
1つの無線ノードから1ホップの位置に存在する1次近傍ノードの情報である隣接ノード情報をm(mは、4以上の整数)個の無線ノードの各々から取得する取得部と、
前記m個の無線ノードの各々についての隣接ノード情報に基づいて、前記m個の無線ノードの配置関係を示す固定トポロジを生成する固定トポロジ生成部と、
前記m個の無線ノードの仮の自己位置を生成する自己位置生成部と、
前記固定トポロジに基づいて前記m個の無線ノードの仮の自己位置を更新することにより、前記m個の無線ノードの位置を推定する位置更新部と、
前記位置更新部により推定された一の無線ノードの位置が前記一の無線ノードから1ホップの位置に存在する無線ノードよりも前記一の無線ノードから2ホップの位置に存在する無線ノードに近いことを示すトポロジ矛盾が発生しているか否かを判定し、前記固定トポロジに対応するとともに前記m個の無線ノードにおけるトポロジ矛盾の発生頻度を示す領域判定値を計算するトポロジ矛盾判定部と、
1ホップの位置に存在する2つの無線ノード間の仮想無線通信距離を設定し、前記仮想無線通信距離に基づいて前記一の無線ノードから1ホップの位置にある1次近傍ノードを再設定し、再設定された1次近傍ノードに基づいて前記m個の無線ノードの仮想的な配置関係を示す少なくとも1つの仮想トポロジを生成する仮想トポロジ生成部と、
を備え、
前記位置更新部は、前記少なくとも1つの仮想トポロジの各々に基づいて、前記m個の無線ノードの位置を推定し、
前記トポロジ矛盾判定部は、前記少なくとも1つ仮想トポロジの各々に対応する前記m個の無線ノードの推定位置に基づいて、前記少なくとも1つ仮想トポロジの各々に対応する領域判定値を計算し、
前記仮想トポロジ生成部は、前記固定トポロジに対応する領域判定値と前記少なくとも1つの仮想トポロジの各々に対応する領域判定値とに基づいて、前記固定トポロジに基づく前記m個の無線ノードの推定位置と、前記少なくとも1つの仮想トポロジの各々に基づく前記m個の無線ノードの推定位置とのうちいずれかを、前記m個の無線ノードの位置の推定結果として出力する位置推定装置。
【請求項2】
請求項1に記載の位置推定装置であって、
前記トポロジ矛盾判定部は、
前記トポロジ矛盾判定部から最後に受けた現在の領域判定値を、前記現在の領域判定値よりも1つ前に入力された直前の領域判定値と比較する判定値比較部と、
前記直前の領域判定値に対応する第1トポロジで用いられた仮想無線通信距離を、前記現在の領域判定値に対応する第2トポロジで用いられた仮想無線通信距離と比較する距離比較部と、
前記判定値比較部による前記現在の領域判定値と前記直前の領域判定値との比較結果と、前記距離比較部による前記第1トポロジで用いられた仮想無線通信距離と前記第2トポロジで用いられた仮想無線通信距離との比較結果とに基づいて、新たな仮想トポロジの生成に用いられる仮想無線通信距離を設定する距離設定部と、
を備える位置推定装置。
【請求項3】
請求項2に記載の位置推定装置であって、
前記距離設定部は、前記第2トポロジで用いられた仮想無線通信距離が前記第1トポロジで用いられた仮想無線通信距離よりも小さいと距離比較部により判断され、かつ、前記現在の領域判定値が前記直前の領域判定値よりも小さいと前記判定値比較部により判断された場合、前記新たな仮想トポロジの生成に用いられる仮想無線通信距離を、前記第2トポロジで用いられた仮想無線通信距離よりも小さくし、
前記距離設定部は、前記第2トポロジで用いられた仮想無線通信距離が前記第1トポロジで用いられた仮想無線通信距離よりも小さいと距離比較部により判断され、かつ、前記現在の領域判定値が前記直前の領域判定値以上であると前記判定値比較部により判断された場合、前記新たな仮想トポロジの生成に用いられる仮想無線通信距離を、前記第2トポロジで用いられた仮想無線通信距離よりも大きくする位置推定装置。
【請求項4】
請求項2または請求項3に記載の位置推定装置であって、
前記距離設定部は、前記第2トポロジで用いられた仮想無線通信距離が前記第1トポロジで用いられた仮想無線通信距離以上である距離比較部により判断され、かつ、前記現在の領域判定値が前記直前の領域判定値よりも大きいと前記判定値比較部により判断された場合、前記新たな仮想トポロジの生成に用いられる仮想無線通信距離を、前記第2トポロジで用いられた仮想無線通信距離よりも小さくし、
前記距離設定部は、前記第2トポロジで用いられた仮想無線通信距離が前記第1トポロジで用いられた仮想無線通信距離以上であると距離比較部により判断され、かつ、前記現在の領域判定値が前記直前の領域判定値以下である前記判定値比較部により判断された場合、前記新たな仮想トポロジの生成に用いられる仮想無線通信距離を、前記第2トポロジで用いられた仮想無線通信距離よりも大きくする位置推定装置。
【請求項5】
請求項1ないし請求項4のいずれかに記載の位置推定装置であって、
前記固定トポロジに対応する領域判定値と、第1仮想トポロジから第k(kは2以上の整数)仮想トポロジまでの各々の領域判定値との中から、領域判定値の最小値を決定する最小値決定部と、
第(k+1)仮想トポロジに対応する領域判定値を新たに前記トポロジ矛盾判定部から受けた場合、第(k+1)仮想トポロジに対応する領域判定値を前記最小値と比較する最小値比較部と、
第(k+1)仮想トポロジに対応する領域判定値が前記最小値よりも大きい場合、前記最小値の更新率を所定の閾値と比較する更新率比較部と、
を備え、
前記仮想トポロジ生成部は、前記更新率が前記閾値よりも小さいと前記更新率比較部により判定された場合、前記最小値に対応するトポロジに基づく前記m個の無線ノードの推定位置を、前記m個の無線ノードの位置推定結果として出力することを決定する位置推定装置。
【請求項6】
1つの無線ノードから1ホップの位置に存在する1次近傍ノードの情報である隣接ノード情報を、無線通信空間内を移動する移動無線ノードと前記無線通信空間内を移動しないm(mは、4以上の整数)個の固定無線ノードとの各々から取得する取得部と、
前記m個の固定無線ノードの各々についての隣接ノード情報に基づいて、前記m個の固定無線ノードの位置を推定する固定ノード位置推定部と、
前記移動無線ノードの隣接ノード情報と前記固定ノード位置推定部による前記m個の固定無線ノードの推定位置とに基づいて、前記移動無線ノードの位置を推定する移動ノード位置推定部と、
を備え、
前記固定ノード位置推定部は、
前記m個の固定無線ノードの各々についての隣接ノード情報に基づいて、前記m個の固定無線ノードの配置関係を示す固定トポロジを生成する固定トポロジ生成部と、
前記m個の固定無線ノードの仮の自己位置を生成する第1自己位置生成部と、
前記固定トポロジに基づいて前記m個の固定無線ノードの仮の自己位置を更新することにより、前記m個の固定無線ノードの位置を推定する第1位置更新部と、
を備え、
前記移動ノード位置推定部は、
前記m個の固定無線ノードのうち前記移動無線ノードの隣接ノード情報に記録された固定無線ノードである隣接固定ノードの隣接ノード情報を前記取得部から取得し、前記移動無線ノードの隣接ノード情報と前記隣接固定ノードの隣接ノード情報とに基づいて、前記移動無線ノードのトポロジを生成する移動トポロジ生成部と、
前記移動無線ノードの仮の自己位置を生成する第2自己位置生成部と、
前記移動トポロジと前記隣接固定ノードの推定位置とに基づいて、前記移動無線ノードの仮の自己位置を更新することにより、前記移動無線ノードの位置を推定する第2位置更新部と、
を備える位置推定装置。
【請求項7】
請求項6に記載の位置推定装置であって、
前記移動トポロジの生成に用いられる隣接ノード情報の数は、前記固定トポロジの生成に用いられる隣接ノード情報の数よりも少ない位置推定装置。
【請求項8】
請求項6または請求項7に記載の位置推定装置であって、
前記取得部は、前記m個の固定無線ノードの各々についての隣接ノード情報と前記移動無線ノードの隣接ノード情報とを定期的に取得し、
前記固定ノード位置推定部は、前記m個の固定無線ノードの位置を第1周期で繰り返し推定し、
前記移動ノード位置推定部は、前記移動無線ノードの位置を前記第1周期よりも短い第2周期で繰り返し推定する位置推定装置。
【請求項9】
請求項6ないし請求項8のいずれかに記載の位置推定装置であって、
前記固定トポロジ生成部は、前記移動無線ノードの位置推定に既に用いられた前記移動無線ノードの隣接ノード情報を仮想的な固定無線ノードの隣接ノード情報に設定し、前記m個の固定無線ノードの各々についての隣接ノード情報と、前記仮想的な固定無線ノードの隣接ノード情報とに基づいて、固定トポロジを生成する位置推定装置。
【請求項10】
無線ノードの位置推定をコンピュータに実行させるための位置推定プログラムであって、
1つの無線ノードから1ホップの位置に存在する1次近傍ノードの情報である隣接ノード情報をm(mは、4以上の整数)個の無線ノードの各々から取得する取得ステップと、
前記m個の無線ノードの各々についての隣接ノード情報に基づいて、前記m個の無線ノードの配置関係を示す固定トポロジを生成する固定トポロジ生成ステップと、
前記m個の無線ノードの仮の自己位置を生成する自己位置生成ステップと、
前記固定トポロジに基づいて前記m個の無線ノードの仮の自己位置を更新することにより、前記m個の無線ノードの位置を推定する位置更新ステップと、
前記位置更新ステップにより推定された一の無線ノードの位置が前記一の無線ノードから1ホップの位置に存在する無線ノードよりも前記一の無線ノードから2ホップの位置に存在する無線ノードに近いことを示すトポロジ矛盾が発生しているか否かを判定し、前記固定トポロジに対応するとともに前記m個の無線ノードにおけるトポロジ矛盾の発生頻度を示す領域判定値を計算するトポロジ矛盾判定ステップと、
1ホップの位置に存在する2つの無線ノード間の仮想無線通信距離を設定し、前記仮想無線通信距離に基づいて前記一の無線ノードから1ホップの位置にある1次近傍ノードを再設定し、再設定された1次近傍ノードに基づいて前記m個の無線ノードの仮想的な配置関係を示す少なくとも1つの仮想トポロジを生成する仮想トポロジ生成ステップと、
を備え、
前記位置更新ステップは、前記少なくとも1つの仮想トポロジの各々に基づいて、前記m個の無線ノードの位置を推定し、
前記トポロジ矛盾判定ステップは、前記少なくとも1つ仮想トポロジの各々に対応する前記m個の無線ノードの推定位置に基づいて、前記少なくとも1つ仮想トポロジの各々に対応する領域判定値を計算し、
前記仮想トポロジ生成ステップは、前記固定トポロジに対応する領域判定値と前記少なくとも1つの仮想トポロジの各々に対応する領域判定値とに基づいて、前記固定トポロジに基づく前記m個の無線ノードの推定位置と、前記少なくとも1つの仮想トポロジの各々に基づく前記m個の無線ノードの推定位置とのうちいずれかを、前記m個の無線ノードの位置の推定結果として出力する位置推定プログラム。
【請求項11】
無線通信空間内を移動する移動無線ノードの位置推定をコンピュータに実行させる位置推定プログラムであって、
1つの無線ノードから1ホップの位置に存在する1次近傍ノードの情報である隣接ノード情報を、前記移動無線ノードと、前記無線通信空間内を移動しないm(mは、4以上の整数)個の固定無線ノードとの各々から取得する取得ステップと、
前記m個の固定無線ノードの各々についての隣接ノード情報に基づいて、前記m個の固定無線ノードの位置を推定する固定ノード位置推定ステップと、
前記移動無線ノードの隣接ノード情報と前記固定ノード位置推定ステップによる前記m個の固定無線ノードの推定位置とに基づいて、前記移動無線ノードの位置を推定する移動ノード位置推定ステップと、
を備え、
前記固定ノード位置推定ステップは、
前記m個の固定無線ノードの各々についての隣接ノード情報に基づいて、前記m個の固定無線ノードの配置関係を示す固定トポロジを生成する固定トポロジ生成ステップと、
前記m個の固定無線ノードの仮の自己位置を生成する第1自己位置生成ステップと、
前記固定トポロジに基づいて前記m個の固定無線ノードの仮の自己位置を更新することにより、前記m個の固定無線ノードの位置を推定する第1位置更新ステップと、
を備え、
前記移動ノード位置推定ステップは、
前記m個の固定無線ノードのうち前記移動無線ノードの隣接ノード情報に記録された固定無線ノードである隣接固定ノードの隣接ノード情報を前記取得ステップから取得し、前記移動無線ノードの隣接ノード情報と前記隣接固定ノードの隣接ノード情報とに基づいて、前記移動無線ノードのトポロジを生成する移動トポロジ生成ステップと、
前記移動無線ノードの仮の自己位置を生成する第2自己位置生成ステップと、
前記移動トポロジと前記隣接固定ノードの推定位置とに基づいて、前記移動無線ノードの仮の自己位置を更新することにより、前記移動ノードの位置を推定する第2位置更新ステップと、
を備える位置推定プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、自己組織化マップを用いて無線ノードの位置を推定する位置推定装置に関する。
【背景技術】
【0002】
複数の無線ノードにより構成される無線センサネットワークにおいて、無線ノードの位置は、無線ノードに搭載されたセンサのセンシングデータの取得位置として重要な情報である。従来、無線ノードの位置を推定する方式として、自己組織化マップ(SOM)を用いた無線ノード位置推定方式(SOL:Self-Organizing Localization)が知られている。
【0003】
SOLは、極少数のアンカーノードを使用し、測距デバイスを用いずに、高精度な位置推定が可能である。また、SOLは、障害物による見通し内(LOS:Line-Of-Sight)と見通し外(NLOS:Non-Line-Of-Sight)が混在する環境においても位置精度の劣化が少ない(例えば、非特許文献1参照)。
【先行技術文献】
【0004】

【非特許文献1】北之馬 貴正、高島 優斗、安達 直世、滝沢 泰久,“NLOS混在環境における無線センサネットワークの集約型自己組織化ノード位置推定方式とその精度評価”,情報処理学会論文誌,Vol.57,No.2,494-506
【発明の概要】
【発明が解決しようとする課題】
【0005】
従来のSOLに基づく位置推定方式を用いて無線ノードの位置を推定した場合、無線ノードの推定位置が1次近傍ノードよりも2次近傍ノードに近いトポロジ矛盾が発生することがある。トポロジ矛盾が発生した場合、無線ノード、1次近傍ノード及び2次近傍ノードのいずれかの位置が誤って推定された可能性が高いため、位置推定処理が再度実行される。
【0006】
しかし、位置推定処理が再度実行された場合、新たなトポロジ矛盾が発生する可能性がある。従来のSOLに基づく位置推定方式では、トポロジ矛盾の発生を抑制することが困難であるため、無線ノードの位置推定の精度を向上させることが困難であった。
【0007】
そこで、本発明は、上記問題点に鑑み、無線ノードの位置を高精度に推定可能な位置推定装置を提供することを課題とする。
【課題を解決するための手段】
【0008】
本発明に係る位置推定装置は、取得部と、固定トポロジ生成部と、自己位置生成部と、位置更新部と、トポロジ矛盾判定部と、仮想トポロジ生成部とを備える。取得部は、1つの無線ノードから1ホップの位置に存在する1次近傍ノードの情報である隣接ノード情報をm(mは、4以上の整数)個の無線ノードの各々から取得する。固定トポロジ生成部は、m個の無線ノードの各々についての隣接ノード情報に基づいて、m個の無線ノードの配置関係を示す固定トポロジを生成する。自己位置生成部は、m個の無線ノードの仮の自己位置を生成する。位置更新部は、固定トポロジに基づいてm個の無線ノードの仮の自己位置を更新することにより、m個の無線ノードの位置を推定する。トポロジ矛盾判定部は、位置更新部により推定された一の無線ノードの位置が一の無線ノードから1ホップの位置に存在する無線ノードよりも一の無線ノードから2ホップの位置に存在する無線ノードに近いことを示すトポロジ矛盾が発生しているか否かを判定し、固定トポロジに対応するとともにm個の無線ノードにおけるトポロジ矛盾の発生頻度を示す領域判定値を計算する。仮想トポロジ生成部は、1ホップの位置に存在する2つの無線ノード間の仮想無線通信距離を設定し、仮想無線通信距離に基づいて一の無線ノードから1ホップの位置にある1次近傍ノードを再設定し、再設定された1次近傍ノードに基づいてm個の無線ノードの仮想的な配置関係を示す少なくとも1つの仮想トポロジを生成する。位置更新部は、少なくとも1つの仮想トポロジの各々に基づいて、m個の無線ノードの位置を推定する。トポロジ矛盾判定部は、少なくとも1つ仮想トポロジの各々に対応するm個の無線ノードの推定位置に基づいて、少なくとも1つ仮想トポロジの各々に対応する領域判定値を計算する。仮想トポロジ生成部は、固定トポロジに対応する領域判定値と少なくとも1つの仮想トポロジの各々に対応する領域判定値とに基づいて、固定トポロジに基づくm個の無線ノードの推定位置と、少なくとも1つの仮想トポロジの各々に基づくm個の無線ノードの推定位置とのうちいずれかを、m個の無線ノードの位置の推定結果として出力する。
【0009】
好ましくは、位置推定装置において、トポロジ矛盾判定部は、判定値比較部と、距離比較部と、離設定部とを備える。判定値比較部は、トポロジ矛盾判定部から最後に受けた現在の領域判定値を、現在の領域判定値よりも1つ前に入力された直前の領域判定値と比較する。距離比較部は、直前の領域判定値に対応する第1トポロジで用いられた仮想無線通信距離を、現在の領域判定値に対応する第2トポロジで用いられた仮想無線通信距離と比較する。距離設定部は、判定値比較部による現在の領域判定値と直前の領域判定値との比較結果と、距離比較部による第1トポロジで用いられた仮想無線通信距離と第2トポロジで用いられた仮想無線通信距離との比較結果とに基づいて、新たな仮想トポロジの生成に用いられる仮想無線通信距離を設定する。
【0010】
好ましくは、位置推定装置において、距離設定部は、第2トポロジで用いられた仮想無線通信距離が第1トポロジで用いられた仮想無線通信距離よりも小さいと距離比較部により判断され、かつ、現在の領域判定値が直前の領域判定値よりも小さいと判定値比較部により判断された場合、新たな仮想トポロジの生成に用いられる仮想無線通信距離を、第2トポロジで用いられた仮想無線通信距離よりも小さくする。距離設定部は、第2トポロジで用いられた仮想無線通信距離が第1トポロジで用いられた仮想無線通信距離よりも小さいと距離比較部により判断され、かつ、現在の領域判定値が直前の領域判定値以上であると判定値比較部により判断された場合、新たな仮想トポロジの生成に用いられる仮想無線通信距離を、第2トポロジで用いられた仮想無線通信距離よりも大きくする。
【0011】
好ましくは、位置推定装置において、距離設定部は、第2トポロジで用いられた仮想無線通信距離が第1トポロジで用いられた仮想無線通信距離以上である距離比較部により判断され、かつ、現在の領域判定値が直前の領域判定値よりも大きいと判定値比較部により判断された場合、新たな仮想トポロジの生成に用いられる仮想無線通信距離を、第2トポロジで用いられた仮想無線通信距離よりも小さくする。距離設定部は、第2トポロジで用いられた仮想無線通信距離が第1トポロジで用いられた仮想無線通信距離以上であると距離比較部により判断され、かつ、現在の領域判定値が直前の領域判定値以下である判定値比較部により判断された場合、新たな仮想トポロジの生成に用いられる仮想無線通信距離を、第2トポロジで用いられた仮想無線通信距離よりも大きくする。
【0012】
好ましくは、位置推定装置は、さらに、最小値決定部と、最小値比較部と、更新率比較部とを備える。最小値決定部は、固定トポロジに対応する領域判定値と、第1仮想トポロジから第k(kは2以上の整数)仮想トポロジまでの各々の領域判定値との中から、領域判定値の最小値を決定する。最小値比較部は、第(k+1)仮想トポロジに対応する領域判定値を新たにトポロジ矛盾判定部から受けた場合、第(k+1)仮想トポロジに対応する領域判定値を最小値と比較する。更新率比較部は、第(k+1)仮想トポロジに対応する領域判定値が最小値よりも大きい場合、最小値の更新率を所定の閾値と比較する。仮想トポロジ生成部は、更新率が閾値よりも小さいと更新率比較部により判定された場合、最小値に対応するトポロジに基づくm個の無線ノードの推定位置を、m個の無線ノードの位置推定結果として出力することを決定する。
【0013】
また、本発明に係る位置推定装置は、取得部と、固定ノード位置推定部と、移動ノード位置推定部とを備える。取得部は、1つの無線ノードから1ホップの位置に存在する1次近傍ノードの情報である隣接ノード情報を、無線通信空間内を移動する移動無線ノードと無線通信空間内を移動しないm(mは、4以上の整数)個の固定無線ノードとの各々から取得する。固定ノード位置推定部は、m個の固定無線ノードの各々についての隣接ノード情報に基づいて、m個の固定無線ノードの位置を推定する。移動ノード位置推定部は、移動無線ノードの隣接ノード情報と固定ノード位置推定部によるm個の固定無線ノードの推定位置とに基づいて、移動無線ノードの位置を推定する。固定ノード位置推定部は、固定トポロジ生成部と、第1自己位置生成部と、第1位置更新部と、を備える。固定トポロジ生成部は、m個の固定無線ノードの各々についての隣接ノード情報に基づいて、m個の固定無線ノードの配置関係を示す固定トポロジを生成する。第1自己位置生成部は、m個の固定無線ノードの仮の自己位置を生成する。第1位置更新部は、固定トポロジに基づいてm個の固定無線ノードの仮の自己位置を更新することにより、m個の固定無線ノードの位置を推定する。移動ノード位置推定部は、移動トポロジ生成部と、第2自己位置生成部と、第2位置更新部とを備える。移動トポロジ生成部は、m個の固定無線ノードのうち移動無線ノードの隣接ノード情報に記録された固定無線ノードである隣接固定ノードの隣接ノード情報を取得部から取得し、移動無線ノードの隣接ノード情報と隣接固定ノードの隣接ノード情報とに基づいて、移動無線ノードのトポロジを生成する。第2自己位置生成部は、移動無線ノードの仮の自己位置を生成する。第2位置更新部は、移動トポロジと隣接固定ノードの推定位置とに基づいて、移動無線ノードの仮の自己位置を更新することにより、移動無線ノードの位置を推定する。
【0014】
好ましくは、位置推定装置において、移動トポロジの生成に用いられる隣接ノード情報の数は、固定トポロジの生成に用いられる隣接ノード情報の数よりも少ない。
【0015】
好ましくは、位置推定装置において、取得部は、m個の固定無線ノードの各々についての隣接ノード情報と移動無線ノードの隣接ノード情報とを定期的に取得する。固定ノード位置推定部は、m個の固定無線ノードの位置を第1周期で繰り返し推定する。移動ノード位置推定部は、移動無線ノードの位置を第1周期よりも短い第2周期で繰り返し推定する。
【0016】
好ましくは、固定トポロジ生成部は、移動無線ノードの位置推定に既に用いられた移動無線ノードの隣接ノード情報を仮想的な固定無線ノードの隣接ノード情報に設定し、m個の固定無線ノードの各々についての隣接ノード情報と、仮想的な固定無線ノードの隣接ノード情報とに基づいて、固定トポロジを生成する。
【0017】
本発明に係る位置推定プログラムは、無線ノードの位置推定をコンピュータに実行させるためのプログラムである。位置推定プログラムは、取得ステップと、固定トポロジ生成ステップと、自己位置生成ステップと、位置更新ステップと、トポロジ矛盾判定ステップと、仮想トポロジ生成ステップとを備える。取得ステップは、1つの無線ノードから1ホップの位置に存在する1次近傍ノードの情報である隣接ノード情報をm(mは、4以上の整数)個の無線ノードの各々から取得する。固定トポロジ生成ステップは、m個の無線ノードの各々についての隣接ノード情報に基づいて、m個の無線ノードの配置関係を示す固定トポロジを生成する。自己位置生成ステップは、m個の無線ノードの仮の自己位置を生成する。位置更新ステップは、固定トポロジに基づいてm個の無線ノードの仮の自己位置を更新することにより、m個の無線ノードの位置を推定する。トポロジ矛盾判定ステップは、位置更新ステップにより推定された一の無線ノードの位置が一の無線ノードから1ホップの位置に存在する無線ノードよりも一の無線ノードから2ホップの位置に存在する無線ノードに近いことを示すトポロジ矛盾が発生しているか否かを判定し、固定トポロジに対応するとともにm個の無線ノードにおけるトポロジ矛盾の発生頻度を示す領域判定値を計算する。仮想トポロジ生成ステップは、1ホップの位置に存在する2つの無線ノード間の仮想無線通信距離を設定し、仮想無線通信距離に基づいて一の無線ノードから1ホップの位置にある1次近傍ノードを再設定し、再設定された1次近傍ノードに基づいてm個の無線ノードの仮想的な配置関係を示す少なくとも1つの仮想トポロジを生成する。位置更新ステップは、少なくとも1つの仮想トポロジの各々に基づいて、m個の無線ノードの位置を推定する。トポロジ矛盾判定ステップは、少なくとも1つ仮想トポロジの各々に対応するm個の無線ノードの推定位置に基づいて、少なくとも1つ仮想トポロジの各々に対応する領域判定値を計算する。仮想トポロジ生成ステップは、固定トポロジに対応する領域判定値と少なくとも1つの仮想トポロジの各々に対応する領域判定値とに基づいて、固定トポロジに基づくm個の無線ノードの推定位置と、少なくとも1つの仮想トポロジの各々に基づくm個の無線ノードの推定位置とのうちいずれかを、m個の無線ノードの位置の推定結果として出力する。
【0018】
本発明に係る位置推定プログラムは、無線通信空間内を移動する移動無線ノードの位置推定をコンピュータに実行させるためのプログラムである。位置推定プログラムは、取得ステップと、固定ノード位置推定ステップと、移動ノード位置推定ステップと、を備える。取得ステップは、1つの無線ノードから1ホップの位置に存在する1次近傍ノードの情報である隣接ノード情報を、移動無線ノードと、無線通信空間内を移動しないm(mは、4以上の整数)個の固定無線ノードとの各々から取得する。固定ノード位置推定ステップは、m個の固定無線ノードの各々についての隣接ノード情報に基づいて、m個の固定無線ノードの位置を推定する。移動ノード位置推定ステップは、移動無線ノードの隣接ノード情報と固定ノード位置推定ステップによるm個の固定無線ノードの推定位置とに基づいて、移動無線ノードの位置を推定する。固定ノード位置推定ステップは、固定トポロジ生成ステップと、第1自己位置生成ステップと、第1位置更新ステップとを備える。固定トポロジ生成ステップは、m個の固定無線ノードの各々についての隣接ノード情報に基づいて、m個の固定無線ノードの配置関係を示す固定トポロジを生成する。第1自己位置生成ステップは、m個の固定無線ノードの仮の自己位置を生成する。第1位置更新ステップは、固定トポロジに基づいてm個の固定無線ノードの仮の自己位置を更新することにより、m個の固定無線ノードの位置を推定する。移動ノード位置推定ステップは、移動トポロジ生成ステップと、第2自己位置生成ステップと、第2位置更新ステップと、を備える。移動トポロジ生成ステップは、m個の固定無線ノードのうち移動無線ノードの隣接ノード情報に記録された固定無線ノードである隣接固定ノードの隣接ノード情報を取得ステップから取得し、移動無線ノードの隣接ノード情報と隣接固定ノードの隣接ノード情報とに基づいて、移動無線ノードのトポロジを生成する。第2自己位置生成ステップは、移動無線ノードの仮の自己位置を生成する。第2位置更新ステップは、移動トポロジと隣接固定ノードの推定位置とに基づいて、移動無線ノードの仮の自己位置を更新することにより、移動ノードの位置を推定する。
【発明の効果】
【0019】
本発明に係る位置更新装置は、m個の無線ノードの隣接ノード情報に基づいて固定トポロジを生成し、固定トポロジに基づいてm個の無線ノードの仮の自己位置を更新することによりm個の無線ノードの位置を推定する。この位置更新装置は、1ホップの位置に存在する2つの無線ノード間の仮想無線通信距離を設定し、仮想無線通信距離に基づいて前記一の無線ノードから1ホップの位置にある1次近傍ノードを再設定し、再設定された1次近傍ノードに基づいて少なくとも1つ以上の仮想トポロジを生成する。この位置更新装置は、少なくとも1つの仮想トポロジに基づいてm個の無線ノードの位置を推定する。m個の無線ノードの推定位置におけるトポロジ矛盾の発生頻度を示す領域判定値が、固定トポロジ及び少なくとも1つの仮想トポロジの各々について計算される。この位置推定装置は、計算された領域判定値のうち最小の領域判定値を特定し、特定した最小の領域判定値に対応するトポロジの推定位置を、位置推定結果として出力する。これにより、トポロジ矛盾の少ないm個の無線ノードの推定位置を特定することができるため、m個の無線ノードの位置を高精度で推定することができる。
【0020】
また、本発明に係る位置推定装置は、m個の無線ノードの隣接ノード情報に基づいて固定トポロジを生成し、生成した固定トポロジに基づいてm個の固定無線ノードの仮の自己位置を更新することよりm個の固定無線ノードの位置を推定する。この位置推定装置は、移動ノードの隣接ノード情報と、移動ノードの隣接ノード情報に記録された隣接固定ノードの隣接ノード情報とに基づいて、移動ノードの移動トポロジを生成する。この位置推定装置は、移動ノードの仮の自己位置を移動トポロジ及び隣接固定ノードの推定位置に基づいて更新することにより、移動ノードの位置を推定する。固定ノードの位置を推定した後に移動ノードの位置を推定することにより、移動ノードの位置を高精度で推定することができる。
【図面の簡単な説明】
【0021】
【図1】この発明の実施の形態に係る無線ネットワークの構成を示す概略図である。
【図2】図1に示す無線ノードにより生成される隣接ノード情報の一例を示す図である。
【図3】図1に示す固定ノードの構成を示す機能ブロック図である。
【図4】図1に示す移動ノードの構成を示す機能ブロック図である。
【図5】図1に示すシンクの構成を示す機能ブロック図である。
【図6】図1に示す位置推定装置の構成を示す機能ブロック図である。
【図7】図6に示す固定ノード位置推定部の構成を示す機能ブロック図である。
【図8】図6に示す移動ノード位置推定部の構成を示す機能ブロック図である。
【図9】図1に示す位置推定装置の動作を示すフローチャートである。
【図10】図6に示す固定ノード位置推定部の動作を示すフローチャートである。
【図11】図1に示す固定ノードの位置を推定した場合に生じるトポロジ矛盾を説明する概念図である。
【図12】図1に示す固定ノードの推定位置においてトポロジ矛盾が発生しているか否かを判定する手順を説明するための概念図である。
【図13】従来技術を用いて予め位置が指定された固定ノードの位置を推定した場合における固定ノードの通信範囲と、位置推定誤差との関係を示すグラフである。
【図14】固定ノードの位置推定誤差と、図7に示すトポロジ矛盾判定部により計算される領域判定値との関係を示すグラフである。
【図15】図1に示す固定ノードのカバレッジの一例を示す図である。
【図16】図1に示す固定ノードの仮想的なカバレッジの一例を示す図である。
【図17】図7に示す仮想トポロジ生成部の動作を示すフローチャートである。
【図18】図7に示す仮想トポロジ生成部の動作を示すフローチャートである。
【図19】図18に示すステップS116で使用される確率分布関数の一例を示すグラフである。
【図20】図18に示すステップS116で使用される確率分布関数の一例を示すグラフである。
【図21】図6に示す移動ノード位置推定部の動作を示すフローチャートである。
【図22】図1に示す移動ノードと固定ノードとの位置関係の一例を示す図である。
【図23】図1に示す移動ノードの位置の変化の一例を示す図である。
【図24】図1に示す固定ノード及び無線ノードの位置推定のシミュレーション結果を示すグラフである。
【図25】図1に示す位置推定装置の構成の他の例を示す機能ブロック図である。
【発明を実施するための形態】
【0022】
以下、図面を参照し、本発明の実施の形態を詳しく説明する。図中同一又は相当部分には同一符号を付してその説明は繰り返さない。

【0023】
[1.全体構成]
[1.1.無線ネットワークの構成]
図1は、本発明の実施の形態に係る無線ネットワーク10の構成を示す概略図である。図1に示すように、無線ネットワーク10は、固定無線ノードN-1,N-2,・・・,N-kと、移動無線ノードM-1,M-2,・・・,M-pと、シンク4と、位置推定装置5とを備える。kは4以上の整数であり、pは1以上の整数である。

【0024】
図1では、固定無線ノードの一部と、移動無線ノードの一部に対する符号の表示を省略している。また、固定無線ノードの一部と、移動無線ノードの一部とが、通知パケットDTGをシンク4に送信している様子を図示しているが、他の固定無線ノード及び移動無線ノードも、通知パケットDTGをシンク4に送信する。通知パケットDTGの詳細については、後述する。

【0025】
以下の説明において、「固定無線ノード」を「固定ノード」と記載し、「移動無線ノード」を「移動ノード」と記載する。また、固定ノードN-1~N-k及び移動ノードM-1~M-pを総称する場合、「無線ノード」と記載する。

【0026】
無線ノード及びシンク4は、近距離無線通信を行うことにより、無線ネットワーク10を構成する。無線ノード及びシンク4は、例えば、近距離無線通信として、例えば、BLE(Bluetooth(登録商標)Low Energy)や、IEEE802.15.4などの通信規格に準拠した無線通信を行う。

【0027】
固定ノードN-1~N-kは、無線通信空間(例えば、ショッピングセンターや駅などの商業施設など)に配置される。固定ノードN-1~N-kは、例えば、センサを搭載したセンシングデバイスである。固定ノードN-1~N-kの各々に搭載されたセンサは、温度、湿度などを検出し、これらの検出値を無線通信によってシンク4に送信する。

【0028】
固定ノードN-1~N-kのうち3個の固定ノードは、絶対位置が予め指定されたアンカーノードである。絶対位置は、例えば、緯度及び経度によって指定される。

【0029】
移動ノードM-1~M-kは、例えば、スマートフォン、携帯電話、タブレット型端末などの移動通信端末である。また、無線ノードM-1~M-kは、後述するように、加速度センサを備えており、加速度を計測する。

【0030】
無線ノードの各々は、自己の識別情報(例えば、アドレス)を含む広告パケットを生成し、その生成した広告パケットをブロードキャストする。そして、無線ノードの各々は、他の無線ノードから広告パケットを受信した場合、その受信した広告パケットを復調し、復調した広告パケットに含まれる識別情報を検出する。

【0031】
図2は、移動ノードM-1において生成される隣接ノード情報21Mの一例を示す図である。図2に示すように、隣接ノード情報21Mは、自己の識別情報と、移動ノードM-1において検出された加速度と、受信した広告パケットから検出した他の無線ノードの識別情報とを記録したデータである。

【0032】
隣接ノード情報21Mにおいて、移動ノードM-1の識別情報が、「Address M-1」であり、移動ノードM-1で検出された加速度は、2.0(m/sec)である。また、隣接ノードの欄には、他の無線ノードから受信した広告パケットから検出された識別情報が記録される。具体的には、固定ノードN-1の識別情報「Address N-1」と、固定ノードN-5の識別情報「Address N-5」と、移動ノードM-2の識別情報「Address M-2」とが記載されている。

【0033】
移動ノードM-1以外の無線ノードも、図2に示す隣接ノード情報21Mと同様の隣接ノード情報を生成する。つまり、全ての固定ノード及び移動ノードは、隣接ノード情報を生成する。ただし、固定ノードの各々は、加速度センサを備えていないため、固定ノードの各々により生成される隣接ノード情報は、加速度を含まない。

【0034】
このように、無線ノードの各々は、少なくとも、自己の識別情報と、受信した広告パケットから検出した他の無線ノードの識別情報とを記録した隣接ノード情報を生成する。無線ノードの各々は、生成した隣接ノード情報を含む通知パケットDTGを生成してシンク4へ送信する。隣接ノード情報は、無線ノードの各々が他の無線ノードから直接受信した広告パケットから検出した識別情報を含む。つまり、隣接ノード情報は、無線ノードの各々から1ホップの位置に存在する無線ノードの情報を含む。1ホップとは、2つの無線ノードが他の無線ノードを介することなく通信することを示す。

【0035】
なお、図1において、無線ノードの一部が通知パケットDTGをシンク4に直接送信するように図示している。しかし、無線ノードが、通知パケットDTGをシンク4に直接送信できない場合がある。この場合、通知パケットDTGは、マルチホップで無線ノードからシンク4へ送信される。マルチホップとは、2つの無線ノードが他の無線ノードを介して通信することを示す。例えば、2ホップは、2つの無線ノードを中継する他の無線ノードの数が1つであることを意味する。つまり、通知パケットDTGが、無線ノードからシンク4へ送信される場合、通知パケットDTGの通信経路は特に限定されない。シンク4は、各無線ノードから送信される通知パケットDTGを受信することができればよい。

【0036】
シンク4は、無線ノードの各々から通知パケットDTGを受信し、その受信した通知パケットDTGから隣接ノード情報を検出する。シンク4は、その検出した隣接ノード情報を位置推定装置5へ送信する。

【0037】
位置推定装置5は、例えば、クラウド上に設置され、シンク4から隣接ノード情報を受信する。これによって、位置推定装置5は、無線ノードの全てから隣接ノード情報を取得し、その取得した隣接ノード情報に基づいて、無線ノードの各々の位置を推定する。

【0038】
位置推定装置5は、固定ノードの各々の隣接ノード情報を用いて、固定ノードN-1~N-kの配置関係を示すトポロジ(以下、「固定トポロジ」と記載する。)を作成する。その後、位置推定装置5は、その作成した固定トポロジに基づいて、後述する方法によって固定ノードN-1~N-kの位置を推定する。固定ノードの各々の位置を推定した後に、位置推定装置5は、後述する方法によって、移動ノードM-1~M-kの位置を推定する。詳細については後述するが、固定ノードの位置推定と、移動ノードの位置推定では、位置を推定する処理の一部が異なる。

【0039】
無線ノードの各々において、広告パケットは、予め設定された時間間隔でブロードキャストされる。無線ノードの各々は、隣接ノード情報を含む通知パケットDTGを定期的に送信する。これにより、位置推定装置5は、各無線ノードから隣接ノード情報を定期的に取得することができるため、固定ノードN-1~N-k及び移動ノードM-1~M-pの位置推定を繰り返し行う。固定ノードN-1~N-kの位置推定を行う時間間隔は、移動ノードM-1~M-kの位置推定を行う時間間隔よりも長く設定される。

【0040】
[1.2.固定ノードの構成]
図3は、図1に示す固定ノードN-1の構成を示す機能ブロック図である。図3に示すように、固定ノードN-1は、アンテナ11と、送受信部12と、制御部13とを含む。

【0041】
送受信部12は、アンテナ11を介して広告パケットを受信し、その受信した広告パケットを制御部13へ出力する。また、送受信部12は、固定ノードN-1の識別情報を含む広告パケットを制御部13から受けた場合、その受けた広告パケットをアンテナ11を介してブロードキャストする。送受信部12は、隣接ノード情報を含む通知パケットDTGを制御部13から受けると、その受けた通知パケットDTGの宛先をシンク4に設定し、宛先がシンク4に設定された通知パケットDTGをアンテナ11を介して送出する。

【0042】
制御部13は、固定ノードN-1の識別情報を予め保持している。制御部13は、固定ノードN-1の識別情報を含む広告パケットを生成し、その生成した広告パケットを送受信部12へ出力する。

【0043】
制御部13は、送受信部12から広告パケットを受けると、その受けた広告パケットから、他の無線ノードの識別情報を検出する。例えば、固定ノードN-1が固定ノードN-2、N-4及び移動ノードM-3から広告パケットを受信した場合、制御部13は、受信した3個のパケットからそれぞれ、固定ノードN-2の識別情報、固定ノードN-4の識別情報、移動ノードM-3の識別情報を検出する。そして、制御部13は、固定ノードN-2の識別情報と、固定ノードN-4の識別情報と、移動ノードM-3の識別情報とを、自己(固定ノードN-1)の識別情報に対応付けた隣接ノード情報を生成する。制御部13は、その生成した隣接ノード情報を含む通知パケットDTGを生成して送受信部12へ出力する。

【0044】
なお、図1に示す固定ノードN-2~N-kの構成は、図3に示す固定ノードN-1の構成と同じである。

【0045】
[1.3.移動ノードの構成]
図4は、図1に示す移動ノードM-1の構成を示す機能ブロック図である。図4に示すように、移動ノードM-1は、アンテナ21と、送受信部22と、制御部23と、加速度センサ24とを含む。

【0046】
送受信部22は、アンテナ21を介して広告パケットを受信し、その受信した広告パケットを制御部23へ出力する。また、送受信部22は、移動ノードM-1の識別情報を含む広告パケットを制御部23から受けた場合、その受けた広告パケットをアンテナ21を介してブロードキャストする。送受信部22は、隣接ノード情報21Mを含む通知パケットDTGを制御部23から受けると、その受けた通知パケットDTGをアンテナ11を介してシンク4へ送信する。

【0047】
制御部23は、移動ノードM-1の識別情報を予め保持している。制御部13は、移動ノードM-1の識別情報を含む広告パケットを生成し、その生成した広告パケットを送受信部22へ出力する。

【0048】
制御部23は、送受信部22から広告パケットを受けると、その受けた広告パケットから、他の無線ノードの識別情報を検出する。固定ノードN-1、固定ノードN-5、移動ノードM-2から広告パケットを受信した場合、制御部23は、受信した3個のパケットからそれぞれ、固定ノードN-1の識別情報、固定ノードN-5の識別情報、移動ノードM-2の識別情報を取得する。また、制御部23は、加速度センサ24により検出された加速度を取得する。制御部23は、固定ノードN-1の識別情報と、固定ノードN-5の識別情報と、移動ノードM-2の識別情報と、加速度センサ24から取得した加速度を用いて、図2に示す隣接ノード情報21Mを生成する。制御部23は、その生成した隣接ノード情報を含む通知パケットDTGを生成して送受信部22へ出力する。

【0049】
[1.4.シンク4の構成]
図5は、図1に示すシンク4の構成を示す機能ブロック図である。図5に示すように、シンク4は、アンテナ41と、送受信部42と、制御部43とを含む。

【0050】
送受信部42は、アンテナ41を介して通知パケットDTGを受信し、その受信した通知パケットDTGを制御部43へ出力する。また、送受信部42は、制御部43から隣接ノード情報を受けると、その受けた隣接ノード情報をアンテナ41及び図示しないインターネットを介して位置推定装置5へ送信する。

【0051】
制御部43は、送受信部42から通知パケットDTGを受けると、その受けた通知パケットDTGから隣接ノード情報を検出し、その検出した隣接ノード情報を送受信部42へ出力する。

【0052】
[1.5.位置推定装置5の構成]
図6は、図1に示す位置推定装置5の構成を示す機能ブロック図である。図6に示すように、位置推定装置5は、取得部51と、分類部52と、固定ノード位置推定部60と、移動ノード位置推定部70とを備える。

【0053】
取得部51は、シンク4からインターネットを介して各無線ノードの隣接ノード情報を受信することにより、各無線ノードの隣接ノード情報を取得する。取得部51は、その受信した隣接ノード情報を分類部52へ出力する。

【0054】
分類部52は、取得部51から各無線ノードの隣接ノード情報を受ける。分類部52は、その受けた隣接ノード情報を、固定ノードN-1~N-kの隣接ノード情報と、移動ノードM-1~M-pの隣接ノード情報とに分類する。分類部52は、固定ノードN-1~N-kの隣接ノード情報を固定ノード位置推定部60に出力する。また、分類部52は、移動ノードM-1~M-pの隣接ノード情報と、固定ノードN-1~N-kのうち所定の条件を満たす固定ノードの隣接ノード情報とを移動ノード位置推定部70に出力する。

【0055】
固定ノード位置推定部60は、分類部52から固定ノードN-1~N-kの隣接ノード情報を受け、その受けた隣接ノード情報に基づいて、固定ノードN-1~N-kの配置関係を示す固定トポロジを生成する。固定ノード位置推定部60は、その生成した固定トポロジに基づいて、固定ノードN-1~N-kの位置を推定して、固定ノードN-1~N-kの推定位置を取得する。固定ノード位置推定部60は、取得した固定ノードN-1~N-kの推定位置を絶対位置に変換する。

【0056】
また、固定ノード位置推定部60は、移動ノードM-u(uは1以上p以下の整数)の隣接ノード情報が移動ノードM-uの位置の推定に用いられた後に、移動ノードM-uの隣接ノード情報を仮想的な固定ノードの隣接ノード情報として、移動ノード位置推定部70から取得する。

【0057】
固定ノード位置推定部60は、再び固定ノードN-1~N-kの位置を推定する際に、移動ノード位置推定部70から取得した移動ノードM-uの隣接ノード情報を、仮想的な固定ノードの隣接ノード情報として使用する。

【0058】
移動ノード位置推定部70は、分類部52から移動ノードM-1~M-pの隣接ノード情報を受け、固定ノード位置推定部60から固定ノードN-1~N-kのうち一部の固定ノードの推定位置を受ける。移動ノード位置推定部70は、その受けた隣接ノード情報と、その受けた固定ノードの推定位置とに基づいて、移動ノードM-1~M-pの推定位置を取得する。移動ノード位置推定部70は、移動ノードM-1~M-pの推定位置を絶対位置に変換する。また、移動ノード位置推定部70は、移動ノードM-uの位置を推定した後に、位置の推定に用いた移動ノードM-uの隣接ノード情報を、固定ノード位置推定部60に出力する。

【0059】
[1.6.固定ノード位置推定部60の構成]
図7は、図6に示す固定ノード位置推定部60の構成を示す機能ブロック図である。図7に示すように、固定ノード位置推定部60は、固定トポロジ生成部61と、自己位置生成部62と、位置更新部63と、変換部64と、トポロジ矛盾判定部65と、仮想トポロジ生成部66とを含む。

【0060】
固定トポロジ生成部61は、固定ノードN-1~N-kの隣接ノード情報を分類部52から受け、その受けた隣接ノード情報に基づいて、固定トポロジを生成する。固定トポロジは、固定ノードN-1~N-kの配置関係を示し、固定ノードN-1~N-kの各々に対して生成される。固定トポロジ生成部61は、その生成したトポロジを位置更新部63へ出力する。

【0061】
また、固定トポロジ生成部61は、移動ノード位置推定部70から移動ノードの隣接ノード情報を受けた場合、その受けた移動ノードの隣接ノード情報を、仮想的な固定ノードの隣接ノード情報として、固定トポロジの生成に使用する。

【0062】
なお、以下の説明では、固定ノードN-1~N-kの隣接ノード情報を使用し、仮想的な固定ノードの隣接ノード情報を使用しない場合を例に説明する。

【0063】
自己位置生成部62は、分類部52から固定ノードN-1~N-kの隣接ノード情報を受け、その受けた隣接ノード情報に基づいて、無線ネットワーク10を構成する固定ノードN-1~N-kを認識する。自己位置生成部62は、その認識した固定ノードN-1~N-kの仮の自己位置をランダムに生成する。

【0064】
位置更新部63は、固定トポロジ生成部61から固定トポロジを受け、自己位置生成部62から固定ノードN-1~N-kの仮の自己位置を受ける。位置更新部63は、その受けた固定トポロジ及び仮の自己位置に基づいて、後述する方法によって、固定ノードN-1~N-kの仮の自己位置を更新することにより、固定ノードN-1~N-kの相対推定位置を取得する。

【0065】
位置更新部63は、固定ノードN-1~N-kの相対推定位置を変換部64へ出力した後、仮想トポロジ及び仮想隣接ノード情報を仮想トポロジ生成部66から受ける。仮想トポロジ及び仮想隣接ノード情報の詳細については、後述する。位置更新部63は、その受けた仮想トポロジ及び仮想隣接ノード情報を用いて、後述する方法によって固定ノードN-1~N-kの相対推定位置を再び取得する。

【0066】
変換部64は、アンカーノードの絶対位置を予め保持している。変換部64は、固定ノードN-1~N-kの相対推定位置を位置更新部63から受ける。変換部64は、その受けた相対推定位置とアンカーノードの絶対位置とに基づいて、後述する方法によって固定ノードN-1~N-kの相対推定位置を絶対位置に変換する。変換部64は、その変換した固定ノードN-1~N-kの絶対位置をトポロジ矛盾判定部65及び仮想トポロジ生成部66へ出力する。

【0067】
トポロジ矛盾判定部65は、固定ノードN-1~N-kの絶対位置を変換部64から受け、その受けた固定ノードN-1~N-kの絶対位置に基づいて、各固定ノードにおけるトポロジ矛盾の有無を判定し、トポロジ矛盾の発生頻度を示す領域判定値VT_AVEを計算する。また、トポロジ矛盾判定部65は、後述する仮想トポロジに基づく固定ノードN-1~N-kの絶対位置に基づいて、仮想トポロジに対応する領域判定値VT_AVEを計算する。すなわち、領域判定値VT_AVEは、トポロジごとに計算される。トポロジ矛盾の有無の判定方法及び領域判定値VT_AVEの計算方法については、後述する。

【0068】
仮想トポロジ生成部66は、トポロジ矛盾判定部65から領域判定値VT_AVEを受け、その受けた領域判定値VT_AVEに対応する相対推定位置及び絶対位置を変換部64から取得する。

【0069】
仮想トポロジ生成部66は、その受けた領域判定値VT_AVEに基づいて、固定ノードN-1~N-kの無線通信距離を仮想的に変更する。仮想トポロジ生成部66は、その変更した仮想的な無線通信距離と固定ノードN-1~N-kの絶対位置とに基づいて、仮想的な1次近傍ノードを固定ノードN-1~N-kの各々に対して決定し、仮想隣接ノード情報を生成する。仮想隣接ノード情報は、固定ノードN-1~N-kの各々について生成され、固定ノードN-1~N-kの各々の仮想的な1次近傍ノードを示す。仮想トポロジ生成部66は、生成した仮想隣接ノード情報に基づいて、後述する方法によって固定ノードN-1~N-kの各々の仮想トポロジを生成する。仮想トポロジは、少なくとも1つ生成される。仮想トポロジ生成部66は、その生成した仮想トポロジを位置更新部63へ出力する。

【0070】
仮想トポロジ生成部66は、固定トポロジに対応する領域判定値VT_AVEと、少なくとも1つの仮想トポロジの各々に対応する領域判定値VT_AVEとを比較する。仮想トポロジ生成部66は、その比較結果に基づいて、固定トポロジに基づく固定ノードの絶対位置と、少なくとも1つの仮想トポロジの各々に基づく固定ノードの絶対位置とのうちいずれかを、固定ノードの位置推定結果として出力する。また、仮想トポロジ生成部66は、位置推定結果として出力された固定ノードの絶対位置に対応する固定ノードの相対推定位置を、移動ノード位置推定部70へ出力する。

【0071】
[1.7.移動ノード位置推定部70の構成]
図8は、図6に示す移動ノード位置推定部70の構成を示す機能ブロック図である。図7に示すように、移動ノード位置推定部70は、移動トポロジ生成部71と、自己位置生成部72と、位置更新部73と、変換部74とを含む。

【0072】
移動トポロジ生成部71は、移動ノードM-1~M-pの隣接ノード情報を取得し、移動ノードM-1~M-pの中から、位置推定の対象となる移動ノードM-u(uは1以上p以下の整数)を選択する。移動トポロジ生成部71は、移動ノードM-uの隣接ノード情報に記録されている固定ノードを特定し、特定した固定ノードの隣接ノード情報を分類部52から取得する。移動トポロジ生成部71は、移動ノードM-uの隣接ノード情報と、特定した固定ノードの隣接ノード情報とに基づいて、移動ノードM-uのトポロジ(移動トポロジ)を生成する。

【0073】
また、移動トポロジ生成部71は、移動ノードM-uの位置推定が終了した後に、移動ノードM-uの隣接ノード情報を固定ノード位置推定部60に出力する。この移動ノードM-uの隣接ノード情報は、仮想的な固定ノードの隣接ノード情報として用いられる。

【0074】
自己位置生成部72は、移動ノードM-uの仮の自己位置をランダムに生成する。

【0075】
位置更新部73は、移動ノードM-uの移動トポロジを移動トポロジ生成部71から受け、移動ノードM-uの仮の自己位置を自己位置生成部72から受ける。位置更新部73は、その受けた移動トポロジ及び仮の自己位置に基づいて、後述する方法によって、移動ノードM-uの仮の自己位置を更新することにより、移動ノードM-uの相対推定位置を取得する。

【0076】
変換部74は、アンカーノードの絶対位置を予め保持している。変換部74は、移動ノードM-uの相対推定位置を位置更新部73から受ける。変換部74は、変換部64(図7参照)と同様に、その受けた移動ノードM-uの相対推定位置とアンカーノードの絶対位置とに基づいて、後述する方法によって移動ノードM-uの相対推定位置を絶対位置に変換する。変換部74は、その変換した移動ノードM-uの絶対位置を、移動ノードM-uの位置推定結果として出力する。

【0077】
[2.位置推定装置5の動作の概略]
図9は、位置推定装置5の基本的な動作を示すフローチャートである。無線ノードの位置推定が開始された場合、取得部51が、無線ノードの各々の隣接ノード情報をシンク4から受ける。分類部52は、全ての無線ノードの隣接ノード情報を取得部51から取得する(ステップS1)。

【0078】
分類部52は、その取得した隣接ノード情報を、固定ノードの隣接ノード情報と、移動ノードの隣接ノード情報とに分類する(ステップS2)。分類部52は、例えば、分類対象の隣接ノード情報が加速度を含まない場合、その隣接ノード情報を固定ノードの隣接ノード情報に分類し、分類対象の隣接ノード情報が加速度を含む場合、その隣接ノード情報を移動ノードの隣接ノード情報に分類する。

【0079】
なお、隣接ノード情報の分類条件は、上記に限定しなくてもよい。例えば、固定ノードの識別情報と移動ノードの識別情報とが予め分類部52に設定されている場合、分類部52は、隣接ノード情報に含まれる自己の識別情報に基づいて、隣接ノード情報を分類してもよい。

【0080】
また、分類部52は、予め設定された閾値よりも大きい加速度を含む隣接ノード情報を移動ノードの隣接ノード情報に分類し、閾値以下の加速度を含む隣接ノード情報を固定ノードの隣接ノード情報に分類してもよい。この場合、移動ノードM-1~M-kが、固定ノードとして扱われる場合が発生する。

【0081】
本実施の形態では、説明の便宜上、無線ノードが固定ノードから移動ノードに変化したり、移動ノードから固定ノードに変化したりする場合がないものとして説明する。なお、移動ノードの隣接ノード情報が事後的に仮想的な固定ノードの隣接ノード情報として扱われる場合が存在するが、これについては、別途説明する。

【0082】
固定ノード位置推定部60は、分類部52から受けた固定ノードN-1~N-kの隣接ノード情報に基づいて、固定ノードN-1~N-kの位置を推定し、相対推定値を取得する(ステップS3)。固定ノード位置推定部60は、固定ノードN-1~N-kの相対推定位置を絶対位置に変換する。

【0083】
移動ノード位置推定部70は、分類部52から移動ノードの隣接ノード情報を受け、固定ノード位置推定部60から固定ノードN-1~N-kの相対推定位置を受ける。移動ノード位置推定部70は、移動ノードの隣接ノード情報及び固定ノードN-1~N-kの相対推定位置に基づいて、移動ノードM-1~M-pの位置を推定する(ステップS4)。

【0084】
ステップS4において、移動ノード位置推定部70は、移動ノードM-u(uは、1以上p以下の整数)の位置を推定する際に、固定ノードN-1~N-kの隣接ノード情報のうち、移動ノードM-uの1次近傍固定ノードの隣接ノード情報を使用する。移動ノードM-uの1次近傍固定ノードに該当しない固定ノードの隣接ノード情報は、移動ノードM-uの位置推定に使用されない。つまり、移動ノード位置推定部70は、移動ノードM-uの位置を推定する際に、移動ノードM-uから2ホップ以内の距離にある固定ノードに関する情報を用いる。従って、移動ノードM-uの位置は、固定ノードN-1~N-kの位置推定と比べて、局所的な範囲内で推定される。

【0085】
各無線ノードは、隣接ノード情報を含む通知パケットDTGを定期的に送信する。分類部52は、新たな隣接ノード情報を取得部51から取得した場合、無線ノードの位置推定に用いられる隣接ノード情報を更新する。このため、位置推定装置5は、ステップS3~S7を繰り返すことにより、固定ノードの推定位置及び移動ノードの推定位置を定期的に更新する。

【0086】
具体的には、移動ノードの位置推定(ステップS4)の後に、位置推定装置5は、固定ノードの位置更新タイミングであるか否かを判断する(ステップS5)。固定ノードの位置更新タイミングは、例えば、20秒おきに設定される。固定ノードの位置更新タイミングである場合(ステップS5においてYes)、固定ノード位置推定部60は、分類部52により更新された隣接ノード情報に基づいて、固定ノードの位置を再び推定する(ステップS3)。

【0087】
固定ノードの位置更新タイミングでない場合(ステップS5においてNo)、位置推定装置5は、移動ノードの位置更新タイミングであるか否かを判断する(ステップS6)。移動ノードの位置更新タイミングは、例えば、5秒おきに設定される。つまり、移動ノードの推定位置の更新頻度は、固定ノードの推定位置の更新頻度よりも高い。これは、移動ノードの推定位置を、移動ノードの実際に移動に合わせてリアルタイムで追随させる必要があるためである。

【0088】
移動ノード位置推定部70は、移動ノードの位置更新タイミングである場合(ステップS6においてYes)、分類部52により更新された隣接ノード情報に基づいて、移動ノードの位置推定を再び行う(ステップS4)。

【0089】
位置推定装置5は、移動ノードの位置更新タイミングでない場合(ステップS6においてNo)、位置推定処理を終了するか否かを判断する(ステップS7)。位置推定処理を継続する場合(ステップS7においてNo)、位置推定装置5は、ステップS5の処理に戻る。一方、位置推定処理を終了する場合(ステップS7においてYes)、位置推定装置5は、図9に示す処理を終了する。

【0090】
[3.固定ノードの位置推定処理(ステップS3)]
図10は、固定ノード位置推定部60の動作を示すフローチャートである。以下、図10を参照しながら、固定ノードN-1~N-kの位置を推定する処理(ステップS3)について詳しく説明する。

【0091】
[3.1.トポロジの生成]
固定ノード位置推定部60は、固定ノードN-1~N-kの隣接ノード情報を分類部52から取得する(ステップS31)。

【0092】
固定トポロジ生成部61は、ステップS31で取得した隣接ノード情報に基づいて、各固定ノードに対応する固定トポロジを生成し(ステップS32)、その生成した固定トポロジを位置更新部63へ出力する。

【0093】
具体的には、固定トポロジ生成部61は、以下の(1)~(3)の処理を実行して、各固定ノードに対応する固定トポロジを生成する。以下の説明において、iは、1以上k以下の整数である。
(1)固定ノードN-iの隣接ノード情報に含まれる固定ノードを固定ノードN-iの1次近傍ノードN-j(jは、i≠jを満たし、1以上k以下の整数)とする。
(2)1次近傍ノードN-jの隣接ノード情報に含まれる固定ノードで、固定ノードN-iの隣接ノード情報に含まれない固定ノードを、固定ノードN-jを中継ノードとする固定ノードN-iの2次近傍ノードとする。
(3)同様に、n次近傍ノードの隣接ノード情報に含まれる固定ノードで、(n-1)次までの近傍ノード群の隣接ノード情報に含まれない固定ノードを、n次近傍ノードを中継ノードとする固定ノードN-iの(n+1)次近傍ノードとする。ここで、nは、3以上であることが望ましい。
(4)上記(1)~(3)を再帰的に繰り返すことにより、無線ネットワーク10における固定ノードN-iの多次近傍ノードを設定する。このようにして設定された固定ノードN-iの多次近傍ノードが、固定ノードN-iの固定トポロジに相当する。

【0094】
固定トポロジ生成部61は、上記(1)~(4)を固定ノードN-1~N-kの各々について実行し、固定ノードN-1~N-kの各々についての固定トポロジを生成する。

【0095】
[3.2.通信距離の設定(ステップS33)]
位置更新部63は、各固定ノードの固定トポロジを参照して、各固定ノード間の距離をホップ数を用いて設定する(ステップS33)。

【0096】
以下、ステップS33を詳しく説明する。固定トポロジの生成において説明したように、固定ノードN-iに対応する固定トポロジは、固定ノードN-iのn次近傍ノードを示す情報である。固定トポロジは、固定ノードN-iを基準にした多次近傍ノードのホップ数に基づいて構成されている。従って、1ホップの固定ノード間の距離を一定距離dとした場合、位置更新部63は、固定ノードN-iからn次近傍ノードまでの距離を、一定距離dとホップ数nとの乗算値(一定距離d×ホップ数n=nd)を計算することにより設定する。

【0097】
[3.3.固定ノードの位置推定(ステップS34~S36)]
次に、固定ノード位置推定部60は、ステップS34~S36を実行して、各固定ノードの絶対位置の1回目の推定を行う。1回目の推定では、ステップS2で生成された固定トポロジが用いられる。2回目以降の推定では、ステップS38で生成された仮想トポロジが用いられる。固定トポロジ及び仮想トポロジのいずれを用いる場合であっても、各固定ノードの位置推定処理は同じである。

【0098】
ここでは、ステップS32で生成された固定トポロジに基づく位置推定について詳しく説明する。

【0099】
(仮の自己位置の設定)
自己位置生成部62は、ステップS31で取得された隣接ノード情報に基づいて、無線ネットワーク10を構成する固定ノードN-1~N-kを認識する。自己位置生成部62は、その認識した固定ノードN-1~N-kの仮の自己位置w(t)をランダムに生成する(ステップS34)。仮の自己位置は、所定の2次元座標上に設定される。仮の自己位置w(t)において、iは、1以上k以下の整数であり、固定ノードN-1~N-kのいずれかを示す。tは、仮の自己位置の更新回数を示す。

【0100】
(仮の自己位置の更新)
位置更新部63は、自己位置生成部62により生成された固定ノードN-iの仮の自己位置w(t)を取得し、その取得した仮の自己位置を所定の更新回数で更新する(ステップS35)。所定の更新回数で更新された後の仮の自己位置が、固定ノードN-iの相対推定位置として決定される。

【0101】
具体的には、固定ノードN-iの仮の自己位置w(t)は、固定ノードN-iの仮の自己位置w(t)とn次近傍ノードの仮の自己位置w(t)とを用いて計算された距離|w(t)-w(t)|が固定ノードN-iからn次近傍ノードまでのホップ数からなる距離ndに近づくように修正される。

【0102】
n次近傍ノードの仮の自己位置w(t)を用いて固定ノードN-iの仮の自己位置w(t)を修正するときのn次修正ベクトルは、式(1)によって求められる。

【0103】
【数1】
JP2017199972A1_000003t.gif

【0104】
また、位置更新部63は、仮の自己位置の更新の初期段階においては、広い範囲の近傍ノードを使用する。そして、位置更新部63は、仮の自己位置の更新の進行に伴い、更新に使用する近傍ノードのホップ数を減少させて、局所的かつ詳細なトポロジを用いて更新を収束させる。

【0105】
従って、次式(2)に従って固定ノードN-iの仮の自己位置w(t)を更新する。

【0106】
【数2】
JP2017199972A1_000004t.gif

【0107】
式(2)において、τは、ホップ数nにおける更新終了の閾値を示し、τn-1は、ホップ数nにおける更新開始の閾値を示す。また、式(2)において、α(t)は、t回目の修正における固定ノードN-iの学習関数であり、次式(3)によって決定される。

【0108】
【数3】
JP2017199972A1_000005t.gif

【0109】
式(3)において、ηは、正の減衰定数である。また、学習関数α(t)の初期値α(0)は、1である。

【0110】
最大ホップ数から3ホップまでは、更新回数を均等とし、2ホップは、局所的な位置推定を行うため、他のホップ数における更新回数の2倍の割合として、最大ホップ数から降順に更新開始及び更新終了の閾値を設定する。

【0111】
そして、位置更新部63は、式(2)の右辺の最上段の修正ベクトルから最下段の修正ベクトルまでを順次適用することにより、固定ノードN-iの仮の自己位置w(t)を更新する。

【0112】
式(2)の右辺の最上段の修正ベクトル(V{1}(t)+V{n}(t))は、1次修正ベクトルとn次修正ベクトルとの和からなる。式(2)の右辺の上から2番目の修正ベクトル(V{1}(t)+V{n-1}(t))は、1次修正ベクトルと(n-1)次修正ベクトルとの和からなる。以下同様にして、式(2)の右辺の下から2番目の修正ベクトル(V{1}(t)+V{3}(t))は、1次修正ベクトルと3次修正ベクトルとの和からなる。式(2)の右辺の最下段の修正ベクトル(V{1}(t)+V{2}(t))は、1次修正ベクトルと2次修正ベクトルとの和からなる。

【0113】
従って、位置更新部63は、固定ノードN-iの1次近傍ノードとn次近傍ノードとを用いて固定ノードN-iの仮の自己位置w(t)を更新し、その後、固定ノードN-iの1次近傍ノードと(n-1)次近傍ノードとを用いて固定ノードN-iの仮の自己位置w(t)を更新し、以下、同様にして、固定ノードN-iの1次近傍ノードと3次近傍ノードとを用いて固定ノードN-iの仮の自己位置w(t)を更新し、最終的に、固定ノードN-iの1次近傍ノードと2次近傍ノードとを用いて固定ノードN-iの仮の自己位置w(t)を更新する。

【0114】
これによって、固定ノードN-iの仮の自己位置w(t)を大局的から局所的に更新でき、固定ノードN-iの仮の自己位置w(t)を一定の位置に収束させることができる。

【0115】
例えば、10次修正ベクトル(n=10)までを用いて固定ノードN-iの仮の自己位置w(t)を更新する場合、修正ベクトル(V{1}(t)+V{10}(t))、(V{1}(t)+V{9}(t))、・・・、(V{1}(t)+V{3}(t))を用いた更新回数を1回とすれば、修正ベクトル(V{1}(t)+V{2}(t))を用いた更新回数は、2回である。その結果、全ての修正ベクトルを用いた更新回数は、10回となる。つまり、修正ベクトル(V{1}(t)+V{10}(t))、(V{1}(t)+V{9}(t))、・・・、(V{1}(t)+V{3}(t))を用いた更新回数をp(pは整数)回とすれば、全ての修正ベクトルを用いた更新回数は、一般的には、8p+2p=10p回となる。

【0116】
更新回数10pにおける”10”は、n次修正ベクトルのn=10に等しいので、式(2)の右辺における全ての修正ベクトルを用いた更新回数は、一般的には、np回となる。従って、式(2)を用いた仮の自己位置w(t)の更新回数は、nを決定し、その後、pを決定することにより決定される。

【0117】
(絶対座標への変換)
変換部64は、ステップS35によって得られた各固定ノードの相対推定位置(更新が完了した固定ノードの仮の自己位置W(t))を、位置更新部63から受ける。変換部64は、その受けた各固定ノードの相対推定位置を、アンカーノードの相対推定位置と絶対位置とを用いて絶対位置へ変換する(ステップS36)。

【0118】
アンカーノードの真位置(=絶対位置)をW=(X,Y)とし、相対推定位置をw=(x,y)とすると、真位置W=(X,Y)は、推定位置w=(x,y)を用いて次式のように表される。

【0119】
【数4】
JP2017199972A1_000006t.gif

【0120】
3つのアンカーノードそれぞれについて立てられた連立方程式(4)から6つの係数a,b,c,d,t,tを得ることにより、全ての固定ノードの推定位置w=(x,y)は、次式によって絶対位置W=(X,Y)へ変換される。

【0121】
【数5】
JP2017199972A1_000007t.gif

【0122】
変換部64は、式(4)から係数a,b,c,d,t,tを決定し、その決定した係数a,b,c,d,t,tを式(5)に代入して固定ノードN-1~N-kの全ての相対推定位置を絶対位置に変換する。

【0123】
[3.4.トポロジ矛盾の判定(ステップS37)]
トポロジ矛盾判定部65は、固定ノードN-1~N-kの絶対位置を変換部64から受ける。トポロジ矛盾判定部65は、その受けた固定ノードN-1~N-kの絶対位置に基づいて、各固定ノードにおけるトポロジ矛盾の有無を判定して領域判定値VT_AVEを計算する(ステップS37)。

【0124】
(トポロジ矛盾の定義)
図11は、図1に示す固定ノードN-1~N-kの位置を推定した場合に生じるトポロジ矛盾を示す概念図である。図11に示すように、固定ノードN-iは、仮の自己位置w(t)に存在する。固定ノードN-iから距離dの位置に1次近傍ノード(固定ノード)が存在し、固定ノードN-iから距離dの位置に2次近傍ノード(固定ノード)が存在する。

【0125】
1次近傍ノードのホップ数は、1であり、2次近傍ノードのホップ数は2である。ノード間距離は、上述のように、ホップ数に基づいて設定される。従って、本来のトポロジでは、固定ノードN-iの仮の自己位置w(t)は、2次近傍ノードよりも1次近傍ノードに近くなる。

【0126】
しかし、図11において、距離dが距離dより小さいため、固定ノードN-iの仮の自己位置w(t)は、1次近傍ノードよりも2次近傍ノードに近い。これは、2次近傍ノードが固定ノードN-iから1次近傍ノードよりも遠い位置に存在する本来のトポロジに明らかに矛盾する。このように、位置推定の対象である固定ノードN-iの仮の自己位置w(t)が1次近傍ノードよりも2次近傍ノードに近いことをトポロジ矛盾と呼ぶ。

【0127】
図11に示すように、トポロジ矛盾が発生している場合、トポロジの折れ曲がりが発生する。ここで、「トポロジの折れ曲がり」とは、固定ノードN-iから1次近傍ノードへ向かうベクトルと1次近傍ノードから2近傍ノードへ向かうベクトルとがなす角が、90度から270度の範囲内にあることを示す。

【0128】
(トポロジ矛盾の有無の判定)
図12は、トポロジ矛盾が発生しているか否かを判定する処理を説明するための概念図である。

【0129】
図12(a)に示すように、固定ノードN-i、固定ノードN-iの1次近傍ノードN-j、及び固定ノードN-iの2次近傍ノードであり、かつ、1次近傍ノードN-jの1次近傍ノードである固定ノードN-hの推定位置をそれぞれw,w,wとする。ここで、i,j,hは、いずれも1以上k以下の整数であり、i≠j,j≠h,h≠iの条件を満たす。

【0130】
固定ノードN-hの真の位置をWとした場合、固定ノードN-hの推定位置wは、トポロジの折れ曲がりの要因となる。この場合、w,wを基準点とするwのトポロジ矛盾判定は、wのトポロジ矛盾を検知できる範囲|w-w|≦|w-w|の外にある(=トポロジ矛盾無しの条件を満たす)。ここで、範囲|w-w|は、図11に示す距離dに相当し、範囲|w-w|は、図11に示す距離dに相当する。つまり、距離dと距離dとを単純に比較するだけでは、推定位置wによる折れ曲がりを検知できない。

【0131】
そこで、図12(b)及び図12(c)に示すように、トポロジ矛盾判定の適応領域を拡大する。図12(b)に示すように、固定ノードN-i,N-jの推定位置w,wを基準点に設定する。そして、この2つの基準点を結ぶ線分L1(L1=w-w)の垂直2等分線L1を用いて、固定ノードN-iが配置されている空間を、固定ノードN-iの推定位置wに近い領域と、N-jの推定位置wに近い領域とに分割し、固定ノードN-hの推定位置wが、分割された2つの領域のどちらに存在するかを判断する。

【0132】
この場合、垂直2等分線L1の左側の領域(斜線を施した領域)は、固定ノードN-hの推定位置wが、固定ノードN-iの推定位置wに近い領域であり、垂直2等分線L1の右側の領域は、固定ノードN-hの推定位置wが固定ノードN-jの推定位置wに近い領域である。固定ノードN-hは、固定ノードN-iの2次近傍ノードであるので、wは、wに近い領域内に位置しなければならない。従って、固定ノードN-hの推定位置wが固定ノードN-iの推定位置wに近い領域(斜線を施した領域)に位置する場合(|w—w|≦|w—w|)、トポロジ矛盾が発生していると判定する。

【0133】
さらに、折れ曲がりによるトポロジ矛盾の検知領域を拡大するために、図12(c)に示すように、固定ノードN-jに加えて固定ノードN-iと固定ノードN-jの共通の1次近傍ノードN-gを基準点として用いる。そして、固定ノードN-i,N-gの推定位置w,wを基準点に設定し、この2つの基準点を結ぶ線分L2(L2=w-w)の垂直2等分線L2を用いて、固定ノードN-hが配置されている空間を、固定ノードN-iの推定位置wに近い領域と、固定ノードN-gの推定位置wに近い領域とに分割し、固定ノードN-hの推定位置wが、分割された2つの領域のどちらに存在するかを判断する。

【0134】
この場合、垂直2等分線L2の左側の領域(斜線を施した領域)は、固定ノードN-hの推定位置wが固定ノードN-iの推定位置wに近い領域であり、垂直2等分線L2の右側の領域は、固定ノードN-hの推定位置wが固定ノードgの推定位置wに近い領域である。

【0135】
固定ノードN-hは、固定ノードN-iの2次近傍ノードであるので、wは、wに近い領域内に位置しなければならない。従って、固定ノードN-hの推定位置wが固定ノードN-iの推定位置wに近い領域(斜線を施した領域)に位置する場合(|w—w|≦|w—w|)、トポロジ矛盾判定部65は、トポロジ矛盾が発生していると判定する。

【0136】
図12(c)に示す領域判定は、共通の1次近傍ノードの組み合わせを複数回変えて実施される。そして、複数回実施した結果において、式(6)により得られる領域判定値Vが所定の閾値よりも大きい場合、固定ノードN-iにおいてトポロジ矛盾が発生していると最終的に判定する。

【0137】
【数6】
JP2017199972A1_000008t.gif

【0138】
式(6)において、Vは、固定ノードN-iにおける領域判定値を示し、Aは、固定ノードN-iにおいて、共通1次近傍群を用いてトポロジ矛盾の有無の判定を行った回数を示し、aは、トポロジ矛盾の発生回数を示す。ここで、共通1次近傍群は、トポロジ矛盾の判定基準となる固定ノードN-iの1次近傍ノードであり、かつ、固定ノードN-iの2次近傍ノードである固定ノードN-hの1次近傍ノードである固定ノードにより構成される。領域判定値Vは、0以上1以下の数値であり、判定対象の固定ノードN-iにおいてトポロジ矛盾の発生回数が少ないほど、その値が0に近づく。

【0139】
このようにして、固定ノードN-1~N-kの各々でトポロジ矛盾の有無を判定することにより、折れ曲がりによるトポロジ矛盾の検知領域を拡大でき、折れ曲がりによるトポロジ矛盾を効果的に検出できる。

【0140】
トポロジ矛盾判定部65は、固定ノードN-1~N-kの各々を基準にしてトポロジ矛盾の有無の判定を行うことにより、固定ノードN-1~N-kの各々についての領域判定値Vを計算する。トポロジ矛盾判定部65は、固定ノードN-1~N-kの各々についての領域判定値Vの平均値である領域判定値VT_AVEを計算し、仮想トポロジ生成部66に出力する。領域判定値VT_AVEは、領域判定値Vと同様に、0以上1以下の数値であり、固定ノードN-1~N-kにおけるトポロジ矛盾の発生回数が少ないほど、その値が0に近づく。

【0141】
上述の手順で計算された領域判定値VT_AVEは、固定トポロジに基づく固定ノードN-1~N-kの推定位置から得られたものであるため、固定トポロジに対応する。後述するように、領域判定値VT_AVEは、仮想トポロジに基づく固定ノードN-1~N-kの推定位置からも得られる。つまり、領域判定値VT_AVEと、トポロジとは、1対1に対応する。

【0142】
[3.5.位置推定結果の出力(ステップS38~S40)]
ここで、ステップS38~S40の流れを説明する。なお、仮想トポロジ生成処理(ステップS38の詳細については、後述する。

【0143】
図10に示すように、仮想トポロジ生成部66は、領域判定値VT_AVEを受け、その受けた領域判定値VT_AVEを用いて仮想トポロジを新たに生成する(ステップS38)。仮想トポロジで示される固定ノードN-1の配置関係は、固定トポロジで示される固定ノードの配置関係と異なる。ステップS38の詳細については、後述する。

【0144】
仮想トポロジ生成部66が仮想トポロジを生成した場合(ステップS39においてNo)、位置推定装置5は、生成された仮想トポロジを用いて各固定ノードの位置を再び推定し(ステップS34~36)、固定ノードの推定位置に基づいて、領域判定値VT_AVEを再計算する(ステップS37)。つまり、位置推定装置5は、仮想トポロジに対応する領域判定値VT_AVEを計算する。

【0145】
位置推定装置5は、仮想トポロジ生成部66が仮想トポロジの生成終了を決定するまで(ステップS39においてYes)、ステップS34~S39を繰り返す。仮想トポロジ生成部66が仮想トポロジの生成終了を決定した場合(ステップS39においてYes)、位置推定装置5は、固定ノードN-i~N-kの位置推定結果を出力する(ステップS40)。具体的には、仮想トポロジ生成部66は、これまでに得られた領域判定値VT_AVEの中で得られた最小の領域判定値VT_AVEを特定し、固定トポロジ及び仮想トポロジの中から、最小の領域判定値VT_AVEに対応するトポロジを特定する。仮想トポロジ生成部66は、特定したトポロジから得られた固定ノードN-i~N-kの絶対位置を、位置推定結果として出力する(ステップS40)。これにより、固定ノード位置推定処理(ステップS3)が終了する。

【0146】
[3.6.仮想トポロジの生成(ステップS38)]
以下、ステップS38について詳しく説明する。仮想トポロジ生成部66は、トポロジ矛盾判定部65から領域判定値VT_AVEを受け、その受けた領域判定値VT_AVEに基づいて、固定ノードの仮想トポロジを生成する(ステップS38)。仮想トポロジは、各固定ノードが他の固定ノードから広告パケットを直接受信することが可能な距離として仮想的に設定される仮想無線通信距離に基づいて設定される。以下、仮想無線通信距離を、「仮想ノード間距離」と呼ぶ。

【0147】
仮想トポロジ生成部66は、領域判定値VT_AVEを受けるたびに、仮想ノード間距離を更新し、更新された仮想ノード間距離に基づく仮想トポロジを生成する。そして、上述のように、各固定ノードの位置が、生成された仮想トポロジに基づいて再び推定され、生成された仮想トポロジに対応する領域判定値VT_AVEが計算される。

【0148】
[3.6.1.位置推定誤差と無線通信距離との関係]
最初に、固定ノードN-1~N-kの位置推定誤差を最小にすることができる最適な無線通信距離について説明する。

【0149】
図13は、固定ノードの絶対位置を予め設定した場合において、非特許文献1に示す方法により各固定ノードの位置を推定したときにおける固定ノードの無線通信距離と位置推定誤差との関係を示すグラフである。具体的には、非特許文献1に示す方法では、各固定ノードの位置が、図10に示すステップのうちステップS31~S36のみを用いて推定される。図13において、横軸は、1ホップの無線通信距離(広告パケットを直接受信することが可能な無線通信距離)を示し、縦軸は、位置推定誤差である。

【0150】
図13に示すように、ノードの数が50個、100個及び150個のいずれの場合であっても、位置推定誤差が無線通信距離に対して概ね下に凸となっていることが分かる。これは、固定ノードの位置推定誤差を最小にすることができる最適な無線通信距離が存在することを意味する。

【0151】
無線通信距離が最適な無線通信距離よりも短い場合、各固定ノードにおける1次近傍ノードの数が少なくなり、固定ノードの位置推定に用いられる1次近傍ノードのトポロジ情報が不十分となる。この結果、無線通信距離が最適な無線通信距離よりも短くなるにつれて、位置推定精度が急激に劣化する。

【0152】
一方、無線通信距離が最適な無線通信距離よりも長い場合、ある固定ノードを基準にして、1ホップの位置にある固定ノードの数が増加する。この場合、基準となる固定ノードの1次近傍ノードのトポロジ情報において、ホップ解像度が低くなる。つまり、基準固定ノードから様々な距離にある複数の固定ノードが、1次近傍ノードとしてまとめて扱われるため、ホップ数から求められる通信距離(ステップS33。図10参照)と、実際の無線通信距離との間に乖離が拡大する。この結果、無線通信距離が最適な無線通信距離よりも長くなるにつれて、位置推定精度が劣化する。

【0153】
従って、最小の位置推定誤差または最適な無線通信距離を特定することができれば、固定ノードの位置を高精度で推定することができる。しかし、各固定ノードの真の位置は、アンカーノードを除いて不明であるため、位置推定装置5は、位置推定誤差を取得することができない。また、最適な無線通信距離を特定するために、各固定ノードの送信電力を制御して各固定ノードの無線通信距離を制御する方法が考えられる。しかし、各固定ノードの送信電力を位置推定のために制御することは、各固定ノードの処理負荷を考慮した場合、現実的ではない。

【0154】
そこで、位置推定装置5は、実際の無線通信距離に代えて仮想ノード間距離を使用し、位置推定誤差に代えて領域判定値VT_AVEを使用する。位置推定装置5は、最適な無線通信距離に対応する最小の領域判定値VT_AVEを探索し、探索の結果得られた最小の領域判定値VT_AVEに対応するトポロジから得られる絶対位置を、位置推定結果として出力する。

【0155】
位置推定誤差に代えて領域判定値VT_AVEを使用できる理由を説明する。領域判定値VT_AVEは、無線ネットワーク10における各固定ノードの位置を推定した場合におけるトポロジ矛盾の発生頻度を示す。領域判定値VT_AVEが0に近づくにつれて、各センサノートの推定位置に関してトポロジ矛盾が少なくなり、各固定ノードの位置が高精度で推定されていると考えることができる。

【0156】
図14は、通信距離を0.15~0.5に設定した場合における、固定ノードの位置推定誤差と、領域判定値との関係を示すグラフである。図14に示す固定ノードの位置推定誤差は、図13に示す位置推定誤差と同じである。図14に示すように、領域判定値の低下に伴って、位置推定誤差が低下するという一定の相関関係が表れている。従って、最小の領域判定値VT_AVEを特定し、特定した領域判定値VT_AVEに対応する仮想トポロジに基づいて各固定ノードの位置を推定した場合、その推定位置の誤差は非常に小さいと想定される。

【0157】
[3.6.2.仮想トポロジの概略]
固定トポロジと仮想トポロジとの違いについて説明する。図15は、固定ノードN-1のカバレッジの一例を示す図である。図15において、固定ノードN-1~N-10を結ぶ実線は、実際の無線通信リンクを示す。領域R1は、固定ノードN-1の実際のカバレッジを示す。固定ノードN-1の実際の無線通信距離は、領域R1の半径に相当する。

【0158】
図15に示すように、固定ノードN-1は、領域R1内に位置する固定ノードN-2~N-8と直接通信可能である。つまり、固定ノードN-2~N-8が、固定ノードN-1の1次近傍ノードであり、固定ノードN-2~N-8の識別情報が、固定ノードN-1の隣接ノード情報に登録される。領域R1の外に位置する固定ノードN-9,N-10は、固定ノードN-1の2次近傍ノードである。

【0159】
図16は、仮想ノード間距離に基づく固定ノードN-1の仮想的なカバレッジを示す図である。図16において、領域R2が、固定ノードN-1の仮想的なカバレッジであり、領域R2の半径が仮想ノード間距離に相当する。つまり、図16は、仮想ノード間距離を実際の無線通信距離よりも小さくした場合における、固定ノードN-1の仮想的な1次近傍ノードを示す。固定ノードN-1の仮想的な1次近傍ノードは、固定ノードN-2,N-4,N-6,N-8である。

【0160】
つまり、仮想ノード間距離を実際の無線通信距離よりも短くすることにより、固定ノードN-1の1次近傍ノードを仮想的に減少させることができる。また、仮想ノード間距離を実際の無線通信距離を長くすることにより、固定ノードN-1の1次近傍ノードを仮想的に増加させることができる。

【0161】
このように、固定ノードN-1の1次近傍ノードを仮想的に変更することによって、ステップS32で生成される固定トポロジ(隣接ノード情報に基づいて生成されるトポロジ)と異なる複数の仮想トポロジを生成することが可能となる。

【0162】
[3.6.3.仮想トポロジの生成(ステップS38)の手順の概略]
上述のように、位置推定装置5は、最小の領域判定値VT_AVEを探索する。しかし、図13に示すグラフは、位置推定誤差の平均を用いており、位置推定誤差の実際の振れ幅は、図13に示す振れ幅よりも大きい。このため、最急降下法を用いて領域判定値VT_AVEの最小値を特定した場合、領域判定値VT_AVEの局所解が、誤って最小値として特定されるおそれがある。

【0163】
そこで、仮想トポロジ生成部66は、以下の手順に基づいて、最小の領域判定値VT_AVEの探索を行う。具体的には、仮想トポロジ生成部66は、これまでに計算された領域判定値VT_AVEの中で最小の領域判定値VT_AVEを記憶する。仮想トポロジ生成部66は、現在記憶している領域判定値VT_AVEに対応する仮想ノード間距離の近傍に、現在記憶している領域判定値VT_AVEをより小さくすることのできる仮想ノード間距離が存在すると仮定する。

【0164】
仮想トポロジ生成部66は、現在記憶している領域判定値VT_AVEがより小さくなる方向に仮想ノード間距離を更新し、更新した仮想ノード間距離に基づいて仮想トポロジを新たに生成する。仮想トポロジ生成部66は、新たな仮想トポロジから得られる領域判定値VT_AVEを、現在記憶している領域判定値VT_AVEと比較する。仮想トポロジ生成部66は、これらの処理を繰り返すことにより、最小の領域判定値VT_AVEを探索する。

【0165】
仮想トポロジ生成部66は、以下の(1)及び(2)の考えに基づいて、最小の領域判定値VT_AVEの探索を継続するか否かを判断する。
(1)領域判定値VT_AVEの最小値の更新率が高い場合、新たな最小値が発見される可能性が高いため、最小値の探索を継続する必要がある。
(2)領域判定値VT_AVEの最小値の更新率が低い場合、領域判定値VT_AVEの最小値を発見した可能性が高い。
つまり、領域判定値VT_AVEの最小値の更新率が予め設定された閾値以上である場合、仮想トポロジ生成部66は、新たな仮想トポロジの探索を継続する。一方、領域判定値VT_AVEの最小値の更新率が上記の閾値よりも低い場合、仮想トポロジ生成部66は、最小の領域判定値VT_AVEを特定できたと判断し、仮想トポロジの生成終了を決定する。

【0166】
[3.7.仮想トポロジの生成(ステップS38)の具体的な処理]
[3.7.1.1回目の仮想トポロジの設定)
図17及び図18は、仮想トポロジ生成部66の動作を示すフローチャートである。以下、図17及び図18を参照しながら、仮想トポロジの生成(ステップS38。図10参照)について詳しく説明する。

【0167】
仮想トポロジ生成部66は、固定トポロジに対応する領域判定値VT_AVEをトポロジ矛盾判定部65から受けた場合、仮想トポロジが既に生成されたか否かを判断する(ステップS101)。固定ノードの位置推定において、仮想トポロジの生成が行われていないため(ステップS101においてYes)、仮想トポロジ生成部66は、最小の領域判定値VT_AVEの探索に用いるパラメータを初期化する(ステップS102)。

【0168】
具体的には、仮想トポロジ生成部66は、ステップS102において、最良領域判定値、最良領域判定値更新率、終了基準更新率、確率変数a,b、及び仮想ノード間距離を設定する。

【0169】
最良領域判定値は、仮想トポロジ及び固定トポロジの各々に対応する領域判定値VT_AVEのうち、最小の領域判定値VT_AVEである。ステップS102では、仮想トポロジ生成部66に最初に入力された領域判定値VT_AVEが、最良領域判定値として設定される。

【0170】
最良領域判定値更新率は、最良領域判定値の更新頻度を示し、0以上1以下の数値である。具体的には、最良領域判定値更新率は、最良領域判定値の更新回数を、固定トポロジとこれまでに生成された仮想トポロジの合計数で除算することにより得られる。ステップS102では、最良領域判定値が、最初の領域判定値VT_AVEの入力により更新されるため、最良領域判定値更新率は、1に設定される。

【0171】
終了基準更新率は、仮想トポロジの生成を終了するか否かを判断するための閾値である。仮想トポロジ生成部66は、ステップS102において、確率分布関数P(a,b)の確率変数a,bを0に初期化する。確率分布関数P(a,b)の詳細については、後述する。

【0172】
また、仮想トポロジ生成部66は、仮想ノード間距離の初期値を設定する。仮想トポロジ生成部66は、変換部64により変換された各固定ノードの絶対位置と、固定ノードの隣接ノード情報とに基づいて、固定ノードと隣接ノード情報に登録された1次近傍ノードとの距離の平均値を計算する。計算により得られた平均距離が、仮想ノード間距離の初期値として用いられる。このようにして設定された仮想ノード間距離の初期値は、固定トポロジの仮想無線通信距離に相当する。

【0173】
ステップS102の後に、仮想トポロジ生成部66は、図18に示すステップS116に進む。仮想トポロジ生成部66は、0以上1以下の一様な乱数を生成し、生成した乱数を確率分布関数P(a,b)と比較する(ステップS116)。

【0174】
確率分布関数P(a,b)が乱数よりも大きい場合(ステップS116においてYes)、仮想トポロジ生成部66は、仮想ノード間距離を現在の仮想ノード間距離よりも小さくする(ステップS117)。一方、確率分布関数P(a,b)が乱数以下である場合(ステップS116においてNo)、仮想ノード間距離を現在の仮想ノード間距離よりも大きくする(ステップS118)。

【0175】
ここで、確率分布関数P(a,b)について詳しく説明する。上述のように、確率分布関数P(a,b)は、仮想ノード間距離を小さくするか、あるいは、大きくするかを決定するために用いられる。確率分布関数P(a,b)は、式(7)により表される。

【0176】
【数7】
JP2017199972A1_000009t.gif

【0177】
式(7)において、確率変数aは、仮想ノード間距離を小さくした場合に領域判定値VT_AVEが減少したケースの数と、仮想ノード間距離を大きくした場合に領域判定値VT_AVEが増加したケースとの和である。つまり、確率変数aは、仮想ノード間距離を小さくした場合において、領域判定値VT_AVEがより小さくなった回数を示す。

【0178】
確率変数bは、仮想ノード間距離を大きくした場合に領域判定値VT_AVEが減少したケースの数と、仮想ノード間距離を小さく場合に領域判定値VT_AVEが増加したケースとの和である。つまり、確率変数bは、仮想ノード間距離を大きくした場合において、領域判定値VT_AVEがより大きくなった回数を示す。

【0179】
仮想ノード間距離を小さくするか否かは、ステップS116に示すように、確率分布関数P(a,b)と乱数との比較結果に基づいて決定される。確率分布関数P(a,b)が1に近づくほど、仮想ノード間距離を小さくする確率が高くなり、確率分布関数P(a,b)が0に近づくほど、仮想ノード間距離を大きくする確率が高くなる。

【0180】
確率分布関数が0.5に近い場合、仮想ノード間距離を小さくするか大きくするかはランダムに決定される。仮想ノード間距離を小さくすればよいのか、大きくすればよいのかは、仮想トポロジの最初に生成する時点では決まっていない。このため、仮想トポロジ生成部66は、ステップS102において、確率変数a,bを0に設定することにより、仮想ノード間距離を小さくするか大きくするかをランダムに決定する。

【0181】
次に、仮想ノード間距離を小さくする処理(ステップS117)について説明する。仮想トポロジ生成部66は、図17及び図18に示す処理を開始する際に、固定ノードの隣接ノード情報を取得し、変換部64から各固定ノードの絶対位置を取得する。

【0182】
そして、仮想トポロジ生成部66は、固定ノードN-1~N-kのうち、少なくとも1つの固定ノードにおける1次近傍ノードの数が減少するように、仮想ノード間距離を小さくする。1次近傍ノードの減少数は、1以上であればよい。例えば、図16に示すように、仮想ノード間距離が、領域R1の半径に設定されている場合を考える。この場合において、仮想ノード間距離を領域R1の半径から領域R2の半径に減少させた場合、固定ノードN-1の1次近傍ノードの数は、7から4に減少する。

【0183】
一方、仮想ノード間距離を大きくする処理(ステップS118)を実行する場合、仮想トポロジ生成部66は、仮想トポロジ生成部66は、固定ノードN-1~N-kのうち、少なくとも1つの固定ノードにおける1次近傍ノードの数が増加するように、仮想ノード間距離を大きくする。1次近傍ノードの増加数は、1以上であればよい。例えば、図16に示すように、仮想ノード間距離が、領域R1の半径に設定されている場合を考える。この場合、固定ノードN-9が固定ノードN-1の1次近傍ノードとなるように、仮想ノード間距離を、領域R1の半径から大きくすればよい。

【0184】
仮想トポロジ生成部66は、変更された仮想ノード間距離に基づいて、仮想トポロジを生成する(ステップS119)。具体的には、仮想トポロジ生成部66は、固定ノードN-iの絶対位置を基準として、ステップS117又はS118で変更された仮想ノード間距離の範囲内にある他の固定ノードを、固定ノードN-iの1次近傍ノードを特定することにより、固定ノードN-iについての仮想的な隣接ノード情報を生成する。そして、仮想トポロジ生成部66は、ステップS2と同様の手順で、仮想的な隣接ノード情報に基づいて、各固定ノードの仮想トポロジを生成する。

【0185】
位置更新部63は、仮想トポロジ生成部66から仮想トポロジを受け、その受けた仮想トポロジに基づいて、各固定ノードの仮の自己位置を更新することにより、各固定ノードの位置を推定する。仮想トポロジに基づいて各固定ノードの位置を推定する場合、位置更新部63は、自己位置生成部62により新たに生成されたランダムな仮の自己位置を用いてもよいし、直前のトポロジ又は仮想トポロジに基づいて推定された推定位置を用いてもよい。

【0186】
[3.7.2.最良領域判定値を更新する場合]
2回目以降の仮想トポロジの生成について説明する。以下、仮想トポロジ生成部66がトポロジ矛盾判定部65から受ける領域判定値VT_AVEを、「現在の領域判定値」と呼び、現在の領域判定値に対応する仮想トポロジを「現在の仮想トポロジ」と呼ぶ。

【0187】
図17に示すように、仮想トポロジ生成部66は、現在の領域判定値をトポロジ矛盾判定部65から受けた場合、1回目の仮想トポロジの生成であるか否かを判断する(ステップS101)。仮想トポロジの生成が既に行われているため(ステップS101においてNo)、仮想トポロジ生成部66は、現在の領域判定値を最良領域判定値と比較する(ステップS103)。

【0188】
現在の領域判定値が最良領域判定値よりも小さい場合(ステップS103においてYes)、仮想トポロジ生成部66は、最良領域判定値を現在の領域判定値で更新し(ステップS104)、最良領域判定値更新率を更新する(ステップS105)。

【0189】
最良領域判定値が更新された場合、上述のように、現在の仮想トポロジの生成に用いられた仮想ノード間距離の近傍に、より小さい領域判定値VT_AVEを得ることのできる仮想ノード間距離が存在する可能性がある。仮想トポロジ生成部66は、より小さい領域判定値VT_AVEを探索するために、確率変数a,bをそれぞれ0に再初期化する(ステップS106)。これにより、確率分布関数P(a,b)の値は0.5となるため、現在の仮想トポロジに設定に用いられた仮想ノード間距離の修正方向はランダムに決定される。

【0190】
仮想トポロジ生成部66は、確率分布関数P(a,b)を乱数と比較し(ステップS116)、その比較結果に基づいて、仮想ノード間距離を小さくする処理(ステップS117)及び仮想ノード間距離を大きくする処理(ステップS118)を実行する。

【0191】
[3.7.3.最良領域判定値が更新されない場合]
図17に示すように、仮想トポロジ生成部66は、現在の領域判定値をトポロジ矛盾判定部65から受けた場合、1回目の仮想トポロジの生成であるか否かを判断する(ステップS101)。仮想トポロジの生成が既に行われているため(ステップS101においてNo)、仮想トポロジ生成部66は、現在の領域判定値を最良領域判定値と比較する(ステップS103)。

【0192】
現在の領域判定値が最良領域判定値以上である場合(ステップS103においてNo)、仮想トポロジ生成部66は、最良領域判定値更新率を終了基準更新率と比較する(ステップS107)。最良領域判定値更新率が終了基準更新率よりも小さい場合(ステップS107においてYes)については、後述する。

【0193】
最良領域判定値更新率が終了基準更新率以上である場合(ステップS107においてNo)、仮想トポロジ生成部66は、新たな最小値が発見される可能性が高いため、最小値の探索を継続する。

【0194】
具体的には、仮想トポロジ生成部66は、現在の仮想トポロジを生成する際に、仮想ノード間距離を減少させたか否かを判断する(ステップS109)。つまり、仮想トポロジ生成部66は、現在の仮想トポロジの生成に用いた仮想ノード間距離と、直前のトポロジの生成に用いた仮想ノード間距離とを比較する。ここで、直前のトポロジとは、現在の仮想トポロジよりも1つ前に生成されたトポロジ(固定トポロジ又は仮想トポロジ)のことである。

【0195】
現在の仮想トポロジの生成に用いた仮想ノード間距離が直前のトポロジの生成に用いた仮想ノード間距離よりも小さい場合、仮想トポロジ生成部66は、現在の仮想トポロジを生成する際に、仮想ノード間距離を減少させたと判断する。

【0196】
仮想ノード間距離を減少させていた場合(ステップS109においてYes)、仮想トポロジ生成部66は、図18に示すステップS110に進み、現在の領域判定値を、前回の領域判定値と比較する(ステップS110)。前回の領域判定値は、直前の仮想トポロジに対応する。現在の領域判定値を前回の領域判定値と比較することにより、領域判定値VT_AVEが減少傾向にあるのか、増加傾向にあるのかが判断される。

【0197】
前回の領域判定値が現在の領域判定値よりも大きい場合(ステップS110においてYes)、仮想ノード間距離を小さくして領域判定値VT_AVEが減少したケースに該当する。この場合、仮想ノード間距離をさらに小さくすることにより、さらに小さい領域判定値VT_AVEが得られる可能性が高い。確率変数aを増加させた場合、確率分布関数P(a,b)が1に近づくため、確率分布関数P(a,b)が、一様乱数よりも大きくなる確率が高まる。この結果、ノード間通信距離を減少させる処理(ステップS117)が実行される確率が高まる。仮想トポロジ生成部66は、仮想ノード間距離を減少させるために、確率変数aに1を加える(ステップS111)。

【0198】
一方、ステップS110において、前回の領域判定値が現在の領域判定値以下である場合(ステップS110においてNo)、仮想ノード間距離を小さくして領域判定値が増加したケースに該当する。この場合、仮想ノード間距離を大きくすることにより、より小さい領域判定値VT_AVEが得られる可能性が高い。確率変数bを増加させた場合、確率分布関数P(a,b)が0に近づくため、確率分布関数P(a,b)が、一様乱数以下となる確率が高まる。この結果、仮想ノード間距離を増加させる処理(ステップS118)が実行される確率が高まる。仮想トポロジ生成部66は、仮想ノード間距離を増加させるために、確率変数bに1を加える(ステップS112)。

【0199】
仮想トポロジ生成部66は、更新された確率変数a又はbを用いて確率分布関数P(a,b)を計算し、計算した確率分布関数P(a,b)を一様乱数と比較する(ステップS116)。仮想トポロジ生成部66は、上述のように、比較結果に応じて、仮想ノード間距離を減少させる処理(ステップS117)、又は、仮想ノード間距離を増加させる処理(ステップS118)を実行する。

【0200】
なお、仮想トポロジ生成部66は、ステップS117又はS118を実行するにあたり、直前に生成された仮想トポロジを参照する。具体的には、仮想トポロジ生成部66は、直前に生成された仮想トポロジにおける固定ノードN-iの1次近傍ノードを参照して、仮想ノード間距離の変更量を決定する。

【0201】
仮想トポロジ生成部66は、ステップS117又はS118により変更されたノード間距離に基づいて、仮想トポロジを生成する(ステップS119)。このように、確率分布関数P(a,b)における確率変数a,bを用いることにより、仮想ノード間距離の増減を制御することが可能となる。

【0202】
ここで、ステップS109(図17参照)の説明に戻る。前回の仮想トポロジの設定時において、仮想ノード間距離を増加させていた場合(ステップS109においてNo)、仮想トポロジ生成部66は、図18に示すステップS113に進み、現在の領域判定値を、前回の領域判定値と比較する。現在の領域判定値を前回の領域判定値と比較することにより、領域判定値VT_AVEが減少傾向にあるのか、増加傾向にあるのかが判断される。

【0203】
前回の領域判定値が現在の領域判定値よりも大きい場合(ステップS113においてYes)、仮想ノード間距離を小さくして領域判定値が減少したケースに該当する。この場合、ステップS111と同様に、仮想ノード間距離を小さくすることにより、さらに小さい領域判定値VT_AVEが得られる可能性が高い。従って、仮想トポロジ生成部66は、確率変数aに1を加える(ステップS114)。

【0204】
一方、前回の領域判定値が現在の領域判定値以下である場合(ステップS113においてNo)、仮想ノード間距離を小さくして領域判定値VT_AVEが増加したケースに該当する。この場合、ステップS112と同様に、仮想ノード間距離を大きくすることにより、さらに小さい領域判定値が得られる可能性が高い。従って、仮想トポロジ生成部66は、確率変数bに1を加える(ステップS115)。

【0205】
仮想トポロジ生成部66は、更新された確率変数a又はbを用いて確率分布関数P(a,b)を計算し、計算した確率分布関数P(a,b)を一様乱数と比較する(ステップS116)。仮想トポロジ生成部66は、上述のように、比較結果に応じて、仮想ノード間距離を減少させる処理(ステップS117)、又は、仮想ノード間距離を増加させる処理(ステップS118)を実行する。仮想トポロジ生成部66は、ステップS117又はS118により変更されたノード間距離に基づいて、仮想トポロジを生成する(ステップS119)。

【0206】
ここで、確率分布関数P(a,b)の具体例について説明する。図19及び図20は、確率分布関数P(a,b)の具体例を示すグラフである。図19は、確率変数a,bの比(a/b)が1から遠い場合における確率分布関数P(a,b)の分布形状を示す。図18は、確率変数a,bの比(a/b)が1から近い場合における確率分布関数P(a,b)の分布形状を示す。

【0207】
図19及び図20に示すように、確率変数a,bを初期化してから、s回目(sは2以上の整数)の領域判定値VT_AVEの探索時において、確率分布関数P(a,b)の挙動は、確率変数a,bの比(a/b)によって変動する。

【0208】
確率変数a,bの比(a/b)が1から遠い場合、確率分布関数P(a,b)は、図19に示すように、仮想ノード間距離を減少させる方向又は増加させる方向に強く作用する。具体的には、確率変数a,bの比(a/b)が1より大きい場合、確率分布関数P(a,b)が1に近づくため、仮想ノード間距離を小さくする確率が高くなる。つまり、領域判定値VT_AVEの探索が、仮想ノード間距離を小さくする方向で行われる。一方、確率変数a,bの比(a/b)が1より小さい場合、確率分布関数P(a,b)が0に近づくため、仮想ノード間距離を大きくする確率が高くなる。つまり、つまり、領域判定値VT_AVEの探索が、仮想ノード間距離を大きくする方向で行われる。

【0209】
また、確率変数a,bの比(a/b)が1に近い場合、確率分布関数P(a,b)は、図20に示すように、仮想ノード間距離を減少させる確率及び増加させる確率がともに0.5に近づく。この場合、仮想ノード間距離を変化させる方向が明確ではないため、いずれの方向にも探索が行われる。

【0210】
[3.7.4.仮想トポロジの生成の終了]
図17に示すように、仮想トポロジ生成部66は、現在の領域判定値をトポロジ矛盾判定部65から受けた場合、1回目の仮想トポロジの生成であるか否かを判断する(ステップS101)。仮想トポロジの生成が既に行われているため(ステップS101においてNo)、仮想トポロジ生成部66は、現在の領域判定値を最良領域判定値と比較する(ステップS103)。

【0211】
最良領域判定値が現在の領域判定値以下である場合(ステップS103においてNo)、仮想トポロジ生成部66は、領域判定値VT_AVEの最小値の探索が終了した可能性があると判断し、ステップS107に進む。

【0212】
仮想トポロジ生成部66は、終了基準更新率を最良領域判定値更新率と比較する(ステップS107)。最良領域判定値更新率が終了基準更新率よりも低い場合(ステップS107においてYes)、仮想トポロジ生成部66は、現在の最良領域判定値よりも小さい領域判定値VT_AVEが発見される可能性が低いと判断し、仮想トポロジの生成終了を決定する(ステップS108)。

【0213】
仮想トポロジの生成終了を決定した場合、仮想トポロジ生成部66は、図10のステップS40において、最小の領域判定値VT_AVEに対応するトポロジを特定する。仮想トポロジ生成部66は、特定したトポロジから得られた固定ノードN-i~N-kの絶対位置を、位置推定結果として出力する。

【0214】
このように、位置推定装置5は、固定トポロジに基づく各固定ノードの位置推定を行い、固定トポロジに対応する領域判定値VT_AVEを計算する。位置推定装置5は、複数の仮想ノード間距離を設定して複数の仮想トポロジを設定し、各仮想トポロジに基づく各固定ノードの位置推定を行う。位置推定装置5は、各仮想トポロジにおけるトポロジ矛盾の発生頻度を示す領域判定値VT_AVEを計算する。位置推定装置5は、複数の領域判定値VT_AVEの中から最小の領域判定値VT_AVEを特定し、特定した最小の領域判定値VT_AVEに対応するトポロジに基づく位置推定結果を、最終の位置推定結果として出力する。これにより、従来の方法に比べて、停止中の固定ノードの位置推定精度を向上させることができる。

【0215】
[4.移動ノードの位置推定処理(ステップS4)]
図21は、移動ノード位置推定部70の動作を示すフローチャートである。以下、図21を参照しながら、移動ノードM-1~M-pの位置を推定する処理(ステップS4)について詳しく説明する。

【0216】
[4.1.移動ノードの選択]
移動ノード位置推定部70は、分類部52により分類された移動ノードM-1~M-pの隣接ノード情報を取得する(ステップS41)。移動トポロジ生成部71は、取得した隣接ノード情報に基づいて、移動ノードM-1~M-pを認識する。移動トポロジ生成部71は、移動ノードM-1~M-pのうち、位置推定の対象となる移動ノードM-u(uは、1以上p以下の整数)を選択する(ステップS42)。

【0217】
[4.2.移動トポロジの生成]
移動トポロジ生成部71は、移動ノードM-uの近傍に位置する固定ノードの隣接ノード情報を取得する(ステップS43)。具体的には、移動トポロジ生成部71は、移動ノードM-uの隣接ノード情報に記録されている固定ノードを特定する。移動トポロジ生成部71は、特定した固定ノードの隣接ノード情報を分類部52から取得する。

【0218】
例えば、移動ノードM-1がステップS42で選択された場合、移動トポロジ生成部71は、図2に示す隣接ノード情報21Mを参照して、固定ノードN-1及び固定ノードN-5を特定し、特定した固定ノードN-1及びN-5の隣接ノード情報を、分類部52から取得する。

【0219】
移動トポロジ生成部71は、移動ノードM-uの隣接ノード情報と、ステップS43において取得した隣接ノード情報とに基づいて、移動ノードM-uのトポロジ(移動トポロジ)を生成する(ステップS44)。移動トポロジの生成手順は、固定トポロジの生成手順(ステップS32。図10参照)と同じである。ただし、移動トポロジ生成部71は、移動ノードM-uの1次近傍ノード及び2次近傍ノードのみを特定し、3次以上の近傍ノードを特定しない。

【0220】
つまり、移動トポロジ生成部71は、ステップS44において、移動ノードM-uの移動トポロジとして、移動ノードM-uの1次近傍ノード及び2次近傍ノードのみを記録したトポロジを生成する。また、移動ノードM-uの移動トポロジにおいて、1次近傍ノード及び2次近傍ノードは、全て固定ノードであり、移動ノードを含まない。

【0221】
図22は、移動ノードM-1と、固定ノードN-1~N-12との位置関係の一例を示す図である。以下、図22を参照しながら、移動ノードM-1がステップS42で選択された場合における、移動ノードM-1の移動トポロジについて説明する。

【0222】
図22に示すように、領域R11は、移動ノードM-1のカバレッジであり、移動ノードM-1の1次近傍ノードが設定される範囲に相当する。このため、移動ノードM-1の移動トポロジにおいて、領域R11内に存在する固定ノードN-1~N-5が、移動ノードM-1の1次近傍ノードとして設定される。

【0223】
領域R12は、移動ノードM-1の2次近傍ノードが設定される範囲に相当する。移動ノードM-1の移動トポロジにおいて、固定ノードN-6~N-8が、移動ノードM-1の2次近傍ノードとして設定される。固定ノードN-9~N-12は、領域R12の範囲外にあり、移動ノードM-uの3次近傍ノードに相当する。このため、固定ノードN-9~N-12は、移動ノードM-1の移動トポロジに含まれない。固定ノードN-9~N-12は、移動ノードM-1の位置推定に用いられない。

【0224】
つまり、移動ノードM-uの移動トポロジは、無線ネットワーク10全体の大局的なトポロジを構成するのではなく、移動ノードM-uを中心にした局所的なトポロジを構成する。

【0225】
また、図22では、移動ノードM-1以外の移動ノードを示していない。移動ノードM-1の移動トポロジは、移動ノードM-1以外の他の移動ノードを、1次近傍ノード及び2次近傍ノードとして含まない。この理由は、移動ノードの位置が推定されていないため、他の移動ノードを移動トポロジに含めた場合、移動ノードM-1の位置推定精度が低下するためである。

【0226】
[4.3.移動ノードの仮の自己位置の更新]
再び、図21を参照する。自己位置生成部72は、ステップS42で選択された移動ノードM-uの仮の自己位置x(t)をランダムに生成する(ステップS45)。仮の自己位置は、所定の2次元座標上に設定される。tは、仮の自己位置の更新回数を示す。

【0227】
位置更新部73は、移動トポロジを移動トポロジ生成部71から取得し、移動ノードM-uの仮の自己位置x(t)を自己位置生成部72から取得する。位置更新部73は、その取得した移動トポロジに基づいて、1次近傍ノード及び2次近傍ノードの相対推定位置を固定ノード位置推定部60から取得する(ステップS46)。

【0228】
位置更新部73は、取得した仮の自己位置x(t)を所定の更新回数で更新する(ステップS47)。仮の自己位置x(t)の更新手順は、ステップS35(図10参照)における仮の自己位置の更新手順と同じである。ただし、移動トポロジは、1次近傍ノード及び2次近傍ノードのみを記録しているため、上記式(2)において、nは、2に設定される。つまり、移動ノードの仮の自己位置x(t)を更新する場合、式(2)のうち、最下段の式のみが用いられる。移動ノードM-uの仮の自己位置x(t)の更新が終了した場合、位置更新部73は、更新の終了した移動ノードM-uの仮の自己位置x(t)を、移動ノードM-uの推定位置として出力する。

【0229】
ステップS47では、移動トポロジにおいて設定された1次近傍ノード及び2次近傍ノード(固定ノード)の位置は更新されない。この理由は、固定ノードの位置推定処理(ステップS3)において、固定ノードの位置が既に十分な精度で推定されており、移動ノードの位置推定(ステップS4)の際に、固定ノードの位置を改めて推定する必要がないためである。

【0230】
上述のように、移動ノードM-uの位置推定では、移動ノードM-uの1次近傍ノード及び2次近傍ノードを使用し、3次以上の近傍ノードを使用しない。これにより、固定ノードの位置推定に比べて、移動ノードの位置推定に要する演算量を削減することができる。移動ノードの位置推定では、その精度よりも、移動ノードの移動に伴う追随性が優先される。このため、移動ノードM-uの位置推定に使用する近傍ノードの数を抑制することにより、移動ノードM-uの位置を迅速に推定することができる。

【0231】
なお、上記では、移動トポロジが1次近傍ノード及び2次近傍ノードのみを定義している例を説明しているが、これに限られない。移動トポロジは、3次以上の近傍ノードを含んでいてもよい。ただし、移動ノードM-uの位置を迅速に推定するという観点から、移動トポロジは、固定トポロジが1次近傍ノードからn次近傍ノードまでを含んでいる場合、移動トポロジは、1次近傍ノードから(n-1)次近傍ノードを含んでいることが望ましい。つまり、移動トポロジにおける近傍ノードの数が、固定トポロジにおける近傍ノードの数よりも少なければよい。

【0232】
[4.4.移動ノードの推定位置の変換]
変換部74は、更新が完了した移動ノードM-uの仮の自己位置(x(t))を位置更新部73から受ける。変換部74は、その受けた移動ノードM-uの装置推定位置を、アンカーノードの推定位置と絶対位置とを用いて絶対位置へ変換する(ステップS48)。ステップS47における移動ノードM-uの絶対位置の変換手順は、ステップS36(図10参照)と同様である。変換部74は、ステップS47により得られた移動ノードM-uの絶対位置を、移動ノードM-uの位置推定結果として出力する。

【0233】
[4.5.移動ノードの位置推定の終了判断]
移動ノードM-uの絶対位置が出力された後に、移動トポロジ生成部71は、未選択の移動ノードがあるか否かを判定する(ステップS49)。

【0234】
未選択の移動ノードがある場合(ステップS49においてYes)、移動トポロジ生成部71は、未選択の移動ノードの中から、移動ノードを新たに選択する(ステップS42)。その後、新たに選択された移動ノードの位置推定が行われる。全ての移動ノードを選択した場合(ステップS49においてNo)、移動ノード位置推定部70は、図21に示す処理を終了する。

【0235】
このように、移動ノード位置推定部70は、移動ノードM-uの位置を推定する際に、移動ノードM-uの1次近傍ノード及び2次近傍ノードを使用し、3次以上の近傍ノードを使用しない。これにより、移動ノードM-uの位置推定に要する演算量を削減できるため、移動ノードM-uの位置を速やかに推定することができる。また、移動トポロジは、1次近傍ノード及び2次近傍ノードとして固定ノードを含み、移動ノードM-u以外の移動ノードを含まない。これにより、位置推定が行われていない移動ノードが、移動ノードM-uの位置推定に使用されないため、移動ノードM-uの位置推定精度を向上させることができる。

【0236】
[4.6.移動ノードの隣接ノード情報の再利用]
上述のように、移動ノードM-uの位置推定を終了した場合、移動ノードM-uの隣接ノード情報は、仮想的な固定ノードの隣接ノード情報として再利用される。これにより、無線ネットワーク10(図1参照)における固定ノードの数を仮想的に増加させることができるため、無線ネットワーク10における無線ノードの位置推定精度を向上させることができる。以下、詳しく説明する。

【0237】
移動ノードM-uは、時間の経過とともに移動しながら、定期的に隣接ノード情報を含む通知パケットDTGを送信する。従って、移動ノードを離散時間で見た場合、移動ノードを、異なる複数の時刻における複数の固定ノードとみなすことが可能である。

【0238】
図23は、移動ノードM-1の位置の変化の一例を示す図である。図23において、移動ノードM-1の符号のみを表示し、固定ノードの符号の表示を省略している。

【0239】
図23に示すように、移動ノードM-1が、時間の経過とともに、左から右方向へ移動している。この場合、位置推定装置5は、時刻T1における移動ノードM-1の位置を、時刻T1における移動ノードM-1の隣接ノード情報を用いて推定する。その後、位置推定装置5は、時刻T2における移動ノードM-1の位置を、時刻T2における移動ノードM-1の隣接ノード情報を用いて推定し、時刻T3における移動ノードM-1の位置を、時刻T3における移動ノードM-1の隣接ノード情報を用いて推定する。

【0240】
時刻T2における移動ノードM-1の位置推定の際に、時刻T1における移動ノードM-1の隣接ノード情報は使用されない。また、時刻T3における移動ノードM-1の位置推定の際に、時刻T1及びT2における移動ノードM-1の隣接ノード情報は使用されない。しかし、時刻T1及びT2における移動ノードM-1の隣接ノード情報は、時刻T1及び時刻T2における移動ノードM-1の位置に固定ノードを設置した仮定した場合、この固定ノードにより生成された隣接ノード情報であると考えることができる。つまり、移動ノードM-1を時刻T1、T2、及びT3という離散時間で見た場合、移動ノードM-1は、これらの時刻における固定ノードであると考えることができる。

【0241】
位置推定装置5は、この考えに従って、移動ノードM-1の位置推定に使用した隣接ノード情報を、仮想的な固定ノードの隣接ノード情報として使用する。具体的には、移動トポロジ生成部71(図8参照)は、移動ノードM-uの位置推定が完了した場合、移動ノードM-uの隣接ノード情報を、固定ノード位置推定部60(図7参照)の固定トポロジ生成部61へ出力する。固定トポロジ生成部61は、固定トポロジを生成する際に、分類部52から受ける固定ノードN-1~N-kの隣接ノード情報に加えて、移動トポロジ生成部71から受けた移動ノードM-uの隣接ノード情報を仮想的な固定ノードの隣接ノード情報として使用する。

【0242】
これにより、無線ネットワーク10における固定ノードの数を、仮想的に増加させることができる。固定ノードの位置推定精度は、固定ノードの数の増加に応じて向上する。この理由は、固定ノードの数が増加するにつれて、固定ノードの位置を推定する際に用いられる固定トポロジがより詳細化するためである。

【0243】
このように、移動ノードM-uを離散時間で扱うことにより、移動ノードM-uの過去の隣接ノード情報を、仮想的な固定ノードの隣接ノード情報として扱うことが可能となる。つまり、移動ノードM-uを時間分割による多重化ノードとして扱うことにより、無線ノードの位置推定精度をさらに向上させることができる。

【0244】
[4.7.シミュレーション評価]
(1)仮想的な固定ノードの使用による位置精度の評価
上述のように、固定ノード位置推定部60は、固定ノードN-1~N-kの位置を推定する際に、位置推定が完了した移動ノードM-uの隣接ノード情報を、仮想的な固定ノードの隣接ノード情報として使用する。

【0245】
仮想的な固定ノードを使用した場合における固定ノードの位置推定精度を評価するために、シミュレーションを行った。具体的には、仮想的な固定ノードを使用した場合と、仮想的な固定ノードを使用しない場合にとにおける固定ノードの位置推定精度を比較した。

【0246】
シミュレーション条件は、以下の通りである。仮想的な2次元のフィールドを想定した。2次元のフィールドの範囲は、縦300m及び横300mである。固定ノード及び移動ノードを含む無線ノードの通信半径は、1mである。無線ノードの数は、50である。アンカーノードの数は、3であり、固定ノード又は移動ノードの位置推定における仮の自己位置の更新回数は、300回である。

【0247】
そして、仮想的な固定ノードを使用した場合における無線ノードの位置推定誤差を下記の式(8)を用いて算出した。

【0248】
【数8】
JP2017199972A1_000010t.gif

【0249】
式(8)において、Eave_1は、仮想的な固定ノードを使用した場合における位置推定誤差である。Nは、無線ノードの数である。Wは、無線ノードの各々の真位置である。wは、無線ノードの各々の推定位置である。仮想的な固定ノードを使用しない場合における位置推定誤差Eave_2についても、式(8)を用いて算出した。

【0250】
この結果、仮想的な固定ノードを使用した場合における位置推定誤差Eave_1は、約11mであった。仮想的な固定ノードを使用しない場合における位置推定誤差Eave_2は、約18mであった。仮想的な固定ノードを使用した場合における位置推定誤差Eave_1は、仮想的な固定ノードを使用しない場合における位置推定誤差Eave_2の3分の2以下に改善されている。つまり、仮想的な固定ノードを用いて無線ノードの位置を推定することにより、無線ノードの位置推定精度を向上できることが確認された。

【0251】
(2)位置推定誤差の経時変化
上述のように、位置推定装置5による無線ノードの位置推定において、移動ノードの推定位置の更新頻度は、固定ノードの推定位置の更新頻度よりも高い。例えば、位置推定装置5は、1回目の固定ノードの位置推定を行ってから、2回目の固定ノードの位置推定を行うまでの間に、移動ノードの位置推定を20回行う。

【0252】
上述のように移動ノードの位置推定を繰り返し行う場合における位置推定誤差の経時変化を評価するために、シミュレーションを行った。シミュレーション条件は、以下の通りである。仮想的な2次元のフィールドを想定した。2次元のフィールドの範囲は、縦300m及び横300mである。固定ノード及び移動ノードを含む無線ノードの通信半径は、1mである。無線ノードの数は、300である。具体的には、位置推定開始時における固定ノード及び移動ノードの各々の数を150に設定した。アンカーノードの数は、3である。固定ノード及び移動ノードの各々の位置推定における仮の自己位置の更新回数は、300回である。固定ノードの位置推定を5回繰り返した後に、移動ノードの位置推定を25回繰り返した。

【0253】
また、固定ノード又は移動ノードの位置推定が行われるたびに、一定の確率(0.5)で固定ノードを移動ノードに変化させ、無線ノードを移動ノードに変化させた。移動ノードを上記のフィールド範囲内でランダムに移動させた。移動ノードの位置推定を行うにあたって、移動ノードに変化した固定ノードの推定位置を使用しなかった。

【0254】
そして、固定ノードの位置推定及び移動ノードの位置推定を行うたびに、無線ノードの位置推定誤差を上記の式(8)を用いて算出した。上記式(8)において、Nは、固定ノード及び移動ノードを含む無線ノードの数である。Wは、無線ノードの各々の真位置である。wは、無線ノードの各々の推定位置である。

【0255】
図24は、シミュレーションによる位置推定誤差の経時変化を示すグラフである。図23において、横軸の「サイクル」は、固定ノード又は移動ノードの位置推定を行った回数を示す。

【0256】
図24を参照して、位置推定回数が10回までは、位置推定誤差が3.5以上であり、位置推定回数が10回~15回において、位置推定誤差が2.0以下に低下している。これは、位置推定がされていない状態から位置推定を繰り返すことにより、各無線ノードの位置推定の精度が向上していることを示している。

【0257】
図24において、位置推定誤差が2.0m以下に低下している期間が周期的に現れている。位置推定誤差が2.0m以下に低下している期間は、固定ノードの位置推定が行われている期間である。固定ノードの位置推定では、全ての固定ノードの隣接ノード情報が参照されるため、固定ノードの推定位置の精度が上がり、位置推定誤差が2.0m以下に抑制されていることが示されている。

【0258】
位置推定誤差が2.0よりも高い期間は、移動ノードの位置推定が行われている期間に相当する。移動ノードの位置が推定されている期間における位置推定誤差は、概ね2~2.5mである。固定ノードが所定の確率で移動ノードに変化するため、移動ノードの位置推定に利用することができる固定ノードの数が時間の経過とともに減少する。この結果、移動ノードの位置推定誤差が上昇すると考えられる。しかし、移動ノードの位置推定誤差が上昇したとしても、固定ノードの位置推定が定期的に行われるため、位置推定誤差が3m以下に抑制されている。つまり、移動ノードの位置推定を行うにあたって、固定ノードの位置を定期的に推定することによって、位置推定誤差が3m以下に抑制できることを確認できた。

【0259】
[変形例]
なお、上記実施の形態において、移動ノードM-1~M-pが加速度センサ24を備える例を説明したが、これに限られない。移動ノードM-1~M-pは、加速度センサに代えて、地磁気センサ、ジャイロセンサなどを備えていてもよい。つまり、移動ノードM-1~M-pは、自装置が移動しているか否かを判断することができるセンサを備えていればよい。

【0260】
また、上記実施の形態において、無線ノード及びシンク4が近距離無線通信を行う例を説明したが、これに限られない。無線ノードは、2つ以上の通信規格に対応していてもよい。例えば、無線ノードは、BLE又はIEEE802.15.4を用いて、他の無線ノードと広告パケットの送受信を行う。そして、無線ノードは、BLEや、IEEE802.15.4などよりも無線通信距離の長い通信規格(例えば、無線LAN(Local Area Network)や、携帯電話通信網など)に準拠した無線通信を用いて、隣接ノード情報を含む通知パケットDTGをシンク4に送信してもよい。無線ノードが通知パケットDTGを送信する際に、無線LANが用いられる場合、シンク4は、アクセスポイントに相当し、携帯電話通信網が用いられる場合、シンク4は、基地局に相当する。ここに挙げた通信規格は一例であり、無線ノードが使用する無線通信の通信規格は特に限定されない。また、図1では、シンク4が1つである場合を示しているが、無線ネットワーク10は、2つ以上のシンク4を備えていてもよい。

【0261】
また、上記実施の形態において、無線ノードが固定ノードから移動ノードに変化したり、移動ノードから固定ノードに変化したりすることがない例を説明したが、これに限られない。上述のように、例えば、移動ノードM-1の隣接ノード情報21Mに記録された移動ノードM-1の加速度が、所定の加速度以下である場合、分類部52は、移動ノードM-1が固定ノードであると判断し、移動ノードM-1の隣接ノード情報を、固定ノード位置推定部60に出力してもよい。この場合、固定ノード位置推定部60は、固定ノードN-1~N-kの隣接ノード情報に加えて、移動ノードM-1の隣接情報を用いて、固定ノードN-1~N-kの各々についての固定トポロジと、移動ノードM-1についての固定トポロジとを生成すればよい。この結果、移動ノードM-1の位置についても、固定ノード位置推定処理(ステップS3)において推定される。

【0262】
また、固定ノードN-1~N-kのうち、アンカーノードを除く固定ノードが、無線ノードに変化してもよい。例えば、固定ノードN-1がアンカーノードではなく、固定ノードN-1が加速度センサを備えていると仮定する。この場合、固定ノードN-1は、加速度センサにより検出された加速度を記録した隣接ノード情報を生成する。位置推定装置5において、分類部52は、固定ノードN-1から送信された隣接ノード情報に記録されている加速度が所定の加速度以下である場合、固定ノードN-1が移動していないと判断する。一方、分類部52は、固定ノードN-1から送信された隣接ノード情報に記録されている加速度が所定の加速度よりも大きい場合、固定ノードN-1が移動中であると判断し、固定ノードN-1を移動ノードとして扱うことを決定する。

【0263】
また、分類部52は、各無線ノードの隣接ノード情報の時間的な変化に基づいて、各無線ノードが固定ノードであるか移動ノードであるかを決定してもよい。例えば、分類部52は、固定ノードN-1の隣接ノード情報を新たに取得した場合、新たに取得した隣接ノード情報と、新たに取得した隣接ノード情報の直前に取得した固定ノードN-1の隣接ノード情報とを比較する。新たに取得した隣接ノード情報の内容が、直前に取得した隣接ノード情報の内容から変化している場合、分類部52は、固定ノードN-1が移動中であると判断する。一方、新たに取得した隣接ノード情報の内容が、直前に取得した隣接ノード情報の内容から変化していない場合、分類部52は、固定ノードN-1が移動していないと判断する。

【0264】
また、上記実施の形態において、仮想トポロジ生成部66が、仮想トポロジを生成する際に用いられる仮想ノード間距離として、固定ノードの絶対座標から計算された距離を使用する場合を説明したが、これに限られない。仮想トポロジ生成部66は、仮想ノード間距離として、IEEE802.15.4でサポートされているLQI(Link Quality Indicator)を使用してもよい。LQIは、各無線ノードから送信されるパケットなどの無線通信品質を示すパラメータであり、各無線ノードの電界強度に相当する。例えば、移動ノードM-1は、図2に示す隣接ノード情報21Mにおいて、隣接ノードの欄に、無線ノードの識別情報に加えて、広告パケット受信時のLQIを記述してもよい。電界強度の大きさは、無線通信距離と相関関係があるため、仮想トポロジ生成部66は、各無線ノードの隣接ノード情報に記録された全てのLQIの代表値(平均値、中間値)を、仮想ノード間距離の初期値として使用することが可能である。

【0265】
また、上記実施の形態において、位置推定装置5は、仮想トポロジを用いることなく固定ノードN-1~N-kの位置を推定してもよい。この場合、固定ノードN-1~N-kの位置推定の演算量を削減することができるため、移動ノードM-1~M-pの位置を迅速に推定することができる。

【0266】
また、上記実施の形態において、位置推定装置5が、移動ノードM-1~M-kの位置を推定する例を説明したが、これに限られない。位置推定装置5は、移動ノードM-1~M-pの位置を推定しなくてもよい。例えば、固定ノードのみが無線通信空間に配置されている場合においても、位置推定装置5を使用することが可能である。

【0267】
また、上記実施の形態に係る位置推定装置5の各機能ブロック(各機能部)の処理の一部または全部は、プログラムにより実現されるものであってもよい。そして、上記実施の形態に係る位置推定装置5において、各機能ブロックの処理の一部または全部は、コンピュータにおいて、中央演算装置(CPU)により行われる。また、それぞれの処理を行うためのプログラムは、ハードディスク、ROMなどの記憶装置に格納されており、ROMにおいて、あるいはRAMに読み出されて実行される。例えば、位置推定装置5の構成を、図25に示すような構成とすることにより、上記実施の形態に係る位置推定装置5の各機能ブロック(各機能部)の処理の一部または全部が実行されるものであってもよい。

【0268】
また、上記実施の形態の各処理をハードウェアにより実現してもよいし、ソフトウェア(OS(オペレーティングシステム)、ミドルウェア、あるいは、所定のライブラリとともに実現される場合を含む。)により実現してもよい。さらに、ソフトウェアおよびハードウェアの混在処理により実現してもよい。

【0269】
また、上記実施の形態における処理方法の実行順序は、必ずしも、上記実施形態の記載に制限されるものではなく、発明の要旨を逸脱しない範囲で、実行順序を入れ替えることができるものである。

【0270】
前述した方法をコンピュータに実行させるコンピュータプログラム及びそのプログラムを記録したコンピュータ読み取り可能な記録媒体は、本発明の範囲に含まれる。ここで、コンピュータ読み取り可能な記録媒体としては、例えば、フレキシブルディスク、ハードディスク、CD-ROM、MO、DVD、DVD-ROM、DVD-RAM、大容量DVD、次世代DVD、半導体メモリを挙げることができる。

【0271】
上記コンピュータプログラムは、上記記録媒体に記録されたものに限られず、電気通信回線、無線又は有線通信回線、インターネットを代表とするネットワーク等を経由して伝送されるものであってもよい。

【0272】
以上、本発明の実施の形態を説明したが、上述した実施の形態は本発明を実施するための例示に過ぎない。よって、本発明は上述した実施の形態に限定されることなく、その趣旨を逸脱しない範囲内で上述した実施の形態を適宜変形して実施することが可能である。
【符号の説明】
【0273】
N-1~N-k 固定無線ノード(固定ノード)
M-1~M-p 移動無線ノード(移動ノード)
4 シンク
5 位置推定装置
51 取得部
52 分類部
60 固定ノード位置推定部
61 固定トポロジ生成部
62,72 自己位置生成部
63,73 位置更新部
64,74 変換部
65 トポロジ矛盾判定部
66 仮想トポロジ生成部
70 移動ノード位置推定部
71 固定トポロジ生成部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10
【図12】
11
【図13】
12
【図14】
13
【図15】
14
【図16】
15
【図17】
16
【図18】
17
【図19】
18
【図20】
19
【図21】
20
【図22】
21
【図23】
22
【図24】
23
【図25】
24