Top > Search of Japanese Patents > POSITION ESTIMATION DEVICE, PROGRAM TO ENABLE COMPUTER TO EXECUTE POSITION ESTIMATION, AND COMPUTER-READABLE RECORDING MEDIUM RECORDING THE SAME PROGRAM > Specification

Specification :(In Japanese)位置推定装置、位置推定をコンピュータに実行させるためのプログラムおよびそのプログラムを記録したコンピュータ読み取り可能な記録媒体

Country (In Japanese)日本国特許庁(JP)
Gazette (In Japanese)特許公報(B2)
Patent Number P6467334
Publication number P2017-108257A
Date of registration Jan 18, 2019
Date of issue Feb 13, 2019
Date of publication of application Jun 15, 2017
Title of the invention, or title of the device (In Japanese)位置推定装置、位置推定をコンピュータに実行させるためのプログラムおよびそのプログラムを記録したコンピュータ読み取り可能な記録媒体
IPC (International Patent Classification) H04W  64/00        (2009.01)
H04W  84/22        (2009.01)
G01S   5/02        (2010.01)
FI (File Index) H04W 64/00 130
H04W 64/00 173
H04W 84/22
G01S 5/02
Number of claims or invention 11
Total pages 38
Application Number P2015-239884
Date of filing Dec 9, 2015
Date of request for substantive examination Nov 1, 2018
Patentee, or owner of utility model right (In Japanese)【識別番号】399030060
【氏名又は名称】学校法人 関西大学
Inventor, or creator of device (In Japanese)【氏名】滝沢 泰久
【氏名】北之馬 貴正
【氏名】毛利 友紀
【氏名】安達 直世
Accelerated examination, or accelerated appeal examination (In Japanese)早期審査対象出願
Representative (In Japanese)【識別番号】100125704、【弁理士】、【氏名又は名称】坂根 剛
【識別番号】100104444、【弁理士】、【氏名又は名称】上羽 秀敏
【識別番号】100112715、【弁理士】、【氏名又は名称】松山 隆夫
【識別番号】100120662、【弁理士】、【氏名又は名称】川上 桂子
Examiner (In Japanese)【審査官】田畑 利幸
Document or reference (In Japanese)特開2010-008237(JP,A)
毛利 友紀、北之馬 貴正、安達 直世、滝沢 泰久,3次元環境における無線センサネットワークの集約型自己組織化ノード位置推定方式とその精度評価,情報処理学会 研究報告 マルチメディア通信と分散処理(DPS) 2015-DPS-165 [online],日本,情報処理学会,2015年12月 3日,2015-DPS-165(19),第1頁-第8頁
礒川 悌次郎,センサネットワークにおけるセンサノード位置推定,システム/制御/情報 第58巻 第5号 SYSTEMS,CONTROL AND INFORMATION,日本,システム制御情報学会,2014年 5月15日,第58巻 第5号,第7頁-第12頁
朝倉 茂、梅原 大祐、川合 誠,SOMアルゴリズムによる携帯端末の分散型位置推定法に関する検討(その2),電子情報通信学会2001年通信ソサイエティ大会講演論文集1,日本,社団法人電子情報通信学会,2001年 8月29日,第486頁-第486頁,B-5-200
Field of search H04W 4/00-99/00
H04L 12/28-12/955
G01S 5/00-5/14
Scope of claims (In Japanese)【請求項1】
1つの無線装置から1ホップの位置に存在する1次近傍無線装置の情報である隣接無線装置情報をm(mは、4以上の整数)個の無線装置の各々から取得する取得手段と、
前記m個の無線装置についての隣接無線装置情報に基づいて前記m個の無線装置によって構成される無線ネットワークのトポロジーを生成するトポロジー生成手段と、
前記m個の無線装置の仮の自己位置を示すm個の仮の自己位置情報を生成する位置情報生成処理を行う位置情報生成手段と、
前記位置情報生成手段によって前記位置情報生成処理が実行されると、前記無線ネットワークのトポロジーおよび前記m個の仮の自己位置情報に基づいて前記m個の無線装置の各々について位置推定処理を所望回数実行してm個の無線装置の位置を更新する更新処理を行う位置更新手段と、
前記位置更新手段によって前記更新処理が実行されると、1つの無線装置の推定された位置が前記1つの無線装置の隣接無線装置よりも前記1つの無線装置から2ホップの位置に存在する2次近傍無線装置に近いことを示すトポロジー矛盾の有無を領域判定処理によって判定する判定処理を行う判定手段と、
前記判定手段によって前記トポロジー矛盾が無いと判定されると、前記m個の無線装置の更新されたm個の更新位置を用いてn(nは1以上の整数)ホップの無線装置間の距離、前記nホップの無線装置間の距離の平均値および前記nホップの無線装置間の距離の期待値を演算する演算手段と、
前記演算手段によって演算されたnホップの無線装置間の距離の平均値とnホップの無線装置間の距離の期待値とに基づいて前記m個の無線装置のうちの位置推定の対象となる対象無線装置からnホップ目までの各位置における無線通信のカバレッジを求め、追加された仮想の無線装置の隣接無線装置情報と前記m個の無線装置の更新された隣接無線装置情報とを前記カバレッジを用いて作成し、その作成した仮想の無線装置の隣接無線装置情報と前記m個の無線装置の更新された隣接無線装置情報とを用いて前記無線ネットワークの仮想トポロジーを生成する仮想トポロジー生成手段とを備え、
前記位置情報生成手段は、前記判定手段によって前記トポロジー矛盾が有ると判定される毎、または前記仮想トポロジー生成手段によって前記仮想トポロジーが生成される毎に前記位置情報生成処理を実行し、
前記位置推定処理は、位置推定の対象となる対象無線装置の仮の自己位置情報と前記対象無線装置からnホップの位置に存在するn次近傍無線装置の仮の自己位置情報とに基づいて計算された前記対象無線装置と前記n次近傍無線装置との間の距離がnホップのホップ数からなる距離に近づくように前記対象無線装置の仮の自己位置を前記対象無線装置からのホップ数nに応じてそれぞれ修正するための1次修正ベクトル、2次修正ベクトル、・・・及びn次修正ベクトルからなるn個の修正ベクトルを、1次修正ベクトルとn次修正ベクトルとからなる第1番目の修正ベクトル、1次修正ベクトルとn-1次修正ベクトルとからなる第2番目の修正ベクトル、・・・、1次修正ベクトルと2次修正ベクトルとからなる第n-1番目の修正ベクトルの順に適用して前記対象無線装置の仮の自己位置を推定する処理であり、
前記領域判定処理は、前記対象無線装置の推定された位置と前記対象無線装置の1次近傍無線装置の推定された位置との間の線分の垂直二等分線を基準として前記対象無線装置の2次近傍無線装置の推定された位置が前記対象無線装置および前記対象無線装置の1次近傍無線装置のいずれに近いかを判定し、当該判定に引き続いて、前記対象無線装置と前記対象無線装置の2次近傍無線装置との共通の1次近傍無線装置の推定された位置と前記対象無線装置の推定された位置との間の線分の垂直二等分線を基準として前記対象無線装置の2次近傍無線装置の推定された位置が前記対象無線装置および前記共通の1次近傍無線装置のいずれに近いかを前記共通の1次近傍無線装置を複数回変えて判定する処理であり、
前記位置更新手段は、前記仮想トポロジー生成手段によって前記仮想トポロジーが生成されると、前記位置推定処理において、前記対象無線装置と前記n次近傍無線装置との間の距離が前記演算手段によって演算された前記nホップの無線装置間の距離に近づくように前記第1番目の修正ベクトル、前記第2番目の修正ベクトル、・・・、前記第n-1番目の修正ベクトルを順次適用して前記対象無線装置の仮の自己位置を推定する、位置推定装置。
【請求項2】
前記判定手段は、距離矛盾判定処理および前記領域判定処理を順次適用して前記トポロジー矛盾の有無を判定し、
前記距離矛盾判定処理は、前記対象無線装置の複数の1次近傍無線装置と複数の2次近傍無線装置とを用いて、前記対象無線装置の推定された位置が前記対象無線装置の1次近傍無線装置よりも前記対象無線装置の2次近傍無線装置に近いと判定されたとき、トポロジー矛盾があると判定する処理である、請求項1に記載の位置推定装置。
【請求項3】
前記m個の無線装置のうち、k(kは3以上の整数または4以上の整数)個の無線装置のk個の絶対位置情報に基づいて相対位置を絶対位置に変換するための変換行列を求め、その求めた変換行列を用いて前記m個の無線装置の推定された位置を絶対位置に変換する変換手段を更に備える、請求項1または請求項2に記載の位置推定装置。
【請求項4】
前記m個の仮の自己位置情報の各々は、2次元の位置情報からなる、請求項1から請求項3のいずれか1項に記載の位置推定装置。
【請求項5】
前記m個の仮の自己位置情報の各々は、3次元の位置情報からなる、請求項1から請求項3のいずれか1項に記載の位置推定装置。
【請求項6】
m(mは、4以上の整数)個の無線装置の位置推定をコンピュータに実行させるためのプログラムであって、
取得手段が、1つの無線装置から1ホップの位置に存在する1次近傍無線装置の情報である隣接無線装置情報をm(mは、4以上の整数)個の無線装置の各々から取得する第1のステップと、
トポロジー生成手段が、前記m個の無線装置についての隣接無線装置情報に基づいて前記m個の無線装置によって構成される無線ネットワークのトポロジーを生成する第2のステップと、
位置情報生成手段が、前記m個の無線装置の仮の自己位置を示すm個の仮の自己位置情報を生成する位置情報生成処理を行う第3のステップと、
位置更新手段が、前記第3のステップにおいて前記位置情報生成処理が実行されると、前記無線ネットワークのトポロジーおよび前記m個の仮の自己位置情報に基づいて前記m個の無線装置の各々について位置推定処理を所望回数実行してm個の無線装置の位置を更新する更新処理を行う第4のステップと、
判定手段が、前記第4のステップにおいて前記更新処理が実行されると、1つの無線装置の推定された位置が前記1つの無線装置の隣接無線装置よりも前記1つの無線装置から2ホップの位置に存在する2次近傍無線装置に近いことを示すトポロジー矛盾の有無を領域判定処理によって判定する判定処理を行う第5のステップと、
演算手段が、前記第5のステップにおいて前記トポロジー矛盾が無いと判定されると、前記m個の無線装置の更新されたm個の更新位置を用いてn(nは1以上の整数)ホップの無線装置間の距離、前記nホップの無線装置間の距離の平均値および前記nホップの無線装置間の距離の期待値を演算する第6のステップと、
仮想トポロジー生成手段が、前記第6のステップにおいて演算されたnホップの無線装置間の距離の平均値とnホップの無線装置間の距離の期待値とに基づいて前記m個の無線装置のうちの位置推定の対象となる対象無線装置からnホップ目までの各位置における無線通信のカバレッジを求め、追加された仮想の無線装置の隣接無線装置情報と前記m個の無線装置の更新された隣接無線装置情報とを前記カバレッジを用いて作成し、その作成した仮想の無線装置の隣接無線装置情報と前記m個の無線装置の更新された隣接無線装置情報とを用いて前記無線ネットワークの仮想トポロジーを生成する第7のステップとを備え、
前記位置情報生成手段は、前記第5のステップにおいて前記トポロジー矛盾が有ると判定される毎、または前記第7のステップにおいて前記仮想トポロジーが生成される毎に前記位置情報生成処理を実行し、
前記位置推定処理は、前記対象無線装置の仮の自己位置情報と前記対象無線装置からnホップの位置に存在するn次近傍無線装置の仮の自己位置情報とに基づいて計算された前記対象無線装置と前記n次近傍無線装置との間の距離がnホップのホップ数からなる距離に近づくように前記対象無線装置の仮の自己位置を前記対象無線装置からのホップ数nに応じてそれぞれ修正するための1次修正ベクトル、2次修正ベクトル、・・・及びn次修正ベクトルからなるn個の修正ベクトルを、1次修正ベクトルとn次修正ベクトルとからなる第1番目の修正ベクトル、1次修正ベクトルとn-1次修正ベクトルとからなる第2番目の修正ベクトル、・・・、1次修正ベクトルと2次修正ベクトルとからなる第n-1番目の修正ベクトルの順に適用して前記対象無線装置の仮の自己位置を推定する処理であり、
前記領域判定処理は、前記対象無線装置の推定された位置と前記対象無線装置の1次近傍無線装置の推定された位置との間の線分の垂直二等分線を基準として前記対象無線装置の2次近傍無線装置の推定された位置が前記対象無線装置および前記対象無線装置の1次近傍無線装置のいずれに近いかを判定し、当該判定に引き続いて、前記対象無線装置と前記対象無線装置の2次近傍無線装置との共通の1次近傍無線装置の推定された位置と前記対象無線装置の推定された位置との間の線分の垂直二等分線を基準として前記対象無線装置の2次近傍無線装置の推定された位置が前記対象無線装置および前記共通の1次近傍無線装置のいずれに近いかを前記共通の1次近傍無線装置を複数回変えて判定する処理であり、
前記位置更新手段は、前記第7のステップにおいて前記仮想トポロジーが生成されると、前記第4のステップの前記位置推定処理において、前記対象無線装置と前記n次近傍無線装置との間の距離が前記第6のステップにおいて演算された前記nホップの無線装置間の距離に近づくように前記第1番目の修正ベクトル、前記第2番目の修正ベクトル、・・・、前記第n-1番目の修正ベクトルを順次適用して前記対象無線装置の仮の自己位置を推定する、コンピュータに実行させるためのプログラム。
【請求項7】
前記判定手段は、前記第5のステップにおいて、距離矛盾判定処理および前記領域判定処理を順次適用して前記トポロジー矛盾の有無を判定し、
前記距離矛盾判定処理は、前記対象無線装置の複数の1次近傍無線装置と複数の2次近傍無線装置とを用いて、前記対象無線装置の推定された位置が前記対象無線装置の1次近傍無線装置よりも前記対象無線装置の2次近傍無線装置に近いと判定されたとき、トポロジー矛盾があると判定する処理である、請求項6に記載のコンピュータに実行させるためのプログラム。
【請求項8】
変換手段が、前記m個の無線装置のうち、k(kは3以上の整数または4以上の整数)個の無線装置のk個の絶対位置情報に基づいて相対位置を絶対位置に変換するための変換行列を求め、その求めた変換行列を用いて前記m個の無線装置の推定された位置を絶対位置に変換する第8のステップを更にコンピュータに実行させる、請求項6または請求項7に記載のコンピュータに実行させるためのプログラム。
【請求項9】
前記m個の仮の自己位置情報の各々は、2次元の位置情報からなる、請求項6から請求項8のいずれか1項に記載のコンピュータに実行させるためのプログラム。
【請求項10】
前記m個の仮の自己位置情報の各々は、3次元の位置情報からなる、請求項6から請求項8のいずれか1項に記載のコンピュータに実行させるためのプログラム。
【請求項11】
請求項6から請求項10のいずれか一項に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体。
Detailed description of the invention (In Japanese)【技術分野】
【0001】
この発明は、位置推定装置、位置推定をコンピュータに実行させるためのプログラムおよびそのプログラムを記録したコンピュータ読み取り可能な記録媒体に関するものである。
【背景技術】
【0002】
無線センサーネットワークにおいて、センシングデータの取得位置は、重要な情報である。従来、センサーノードの位置を推定する方式として、自己組織化マップ(SOM)を用いたセンサーノード位置推定方式(SOL:Self-Organizing Localization)が知られている(非特許文献1)。
【0003】
SOLは、極少数のアンカーノードを使用し、測距デバイスを用いずに、高精度な位置推定が可能であり、障害物による見通し内(LOS:Line-Of-Sight)と見通し外(NLOS:Non-Line-Of-Sight)が混在する環境においても従来方式と比較して位置精度の劣化が少ない。
【先行技術文献】
【0004】

【非特許文献1】高島 優斗、北之馬 貴正、安達 直世、滝沢 泰久,“NLOS混在環境における無線ネットワークの集約型自己組織化ノード位置推定方式”,情報処理学会研究報告マルチメディア通信と分散処理(DPS),Vol.2015-DPS-162,No.18,pp.1-6,2015.
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかし、SOLでは、位置推定の対象となる対象センサーノードの推定位置が対象センサーノードから1ホップの位置に存在する1次近傍ノードよりも対象センサーノードから2ホップの位置に存在する2次近傍ノードに近くなるトポロジー矛盾を十分に解決できないため、各センサーノードの位置を高精度に推定することが困難である。
【0006】
そこで、この発明の実施の形態によれば、各無線装置の位置を高精度に推定可能な位置推定装置を提供する。
【0007】
また、この発明の実施の形態によれば、各無線装置の高精度な位置推定をコンピュータに実行させるためのプログラムを提供する。
【0008】
さらに、この発明の実施の形態によれば、各無線装置の高精度な位置推定をコンピュータに実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体を提供する。
【課題を解決するための手段】
【0009】
この発明の実施の形態によれば、位置推定装置は、取得手段と、トポロジー生成手段と、位置情報生成手段と、位置更新手段と、判定手段と、演算手段と、仮想トポロジー生成手段とを備える。
【0010】
取得手段は、1つの無線装置から1ホップの位置に存在する1次近傍無線装置の情報である隣接無線装置情報をm(mは、4以上の整数)個の無線装置の各々から取得する。トポロジー生成手段は、m個の無線装置についての隣接無線装置情報に基づいてm個の無線装置によって構成される無線ネットワークのトポロジーを生成する。位置情報生成手段は、m個の無線装置の仮の自己位置を示すm個の仮の自己位置情報を生成する位置情報生成処理を行う。位置更新手段は、位置情報生成手段によって位置情報生成処理が実行されると、無線ネットワークのトポロジーおよびm個の仮の自己位置情報に基づいてm個の無線装置の各々について位置推定処理を所望回数実行してm個の無線装置の位置を更新する更新処理を行う。判定手段は、位置更新手段によって更新処理が実行されると、1つの無線装置の推定された位置が1つの無線装置の隣接無線装置よりも1つの無線装置から2ホップの位置に存在する2次近傍無線装置に近いことを示すトポロジー矛盾の有無を領域判定処理によって判定する判定処理を行う。演算手段は、判定手段によってトポロジー矛盾が無いと判定されると、m個の無線装置の更新されたm個の更新位置を用いてn(nは1以上の整数)ホップの無線装置間の距離、nホップの無線装置間の距離の平均値およびnホップの無線装置間の距離の期待値を演算する。仮想トポロジー生成手段は、演算手段によって演算されたnホップの無線装置間の距離の平均値とnホップの無線装置間の距離の期待値とに基づいてm個の無線装置のうちの位置推定の対象となる対象無線装置からnホップ目までの各位置における無線通信のカバレッジを求め、追加された仮想の無線装置の隣接無線装置情報とm個の無線装置の更新された隣接無線装置情報とをカバレッジを用いて作成し、その作成した仮想の無線装置の隣接無線装置情報とm個の無線装置の更新された隣接無線装置情報とを用いて無線ネットワークの仮想トポロジーを生成する。
【0011】
そして、位置情報生成手段は、判定手段によってトポロジー矛盾が有ると判定される毎、または仮想トポロジー生成手段によって仮想トポロジーが生成される毎に位置情報生成処理を実行する。位置推定処理は、位置推定の対象となる対象無線装置の仮の自己位置情報と前記対象無線装置からnホップの位置に存在するn次近傍無線装置の仮の自己位置情報とに基づいて計算された対象無線装置とn次近傍無線装置との間の距離がnホップのホップ数からなる距離に近づくように対象無線装置の仮の自己位置を対象無線装置からのホップ数nに応じてそれぞれ修正するための1次修正ベクトル、2次修正ベクトル、・・・及びn次修正ベクトルからなるn個の修正ベクトルを、1次修正ベクトルとn次修正ベクトルとからなる第1番目の修正ベクトル、1次修正ベクトルとn-1次修正ベクトルとからなる第2番目の修正ベクトル、・・・、1次修正ベクトルと2次修正ベクトルとからなる第n-1番目の修正ベクトルの順に適用して前記対象無線装置の仮の自己位置を推定する処理である。
【0012】
領域判定処理は、対象無線装置の推定された位置と対象無線装置の1次近傍無線装置の推定された位置との間の線分の垂直二等分線を基準として対象無線装置の2次近傍無線装置の推定された位置が対象無線装置および対象無線装置の1次近傍無線装置のいずれに近いかを判定し、当該判定に引き続いて、対象無線装置と対象無線装置の2次近傍無線装置との共通の1次近傍無線装置の推定された位置と対象無線装置の推定された位置との間の線分の垂直二等分線を基準として対象無線装置の2次近傍無線装置の推定された位置が対象無線装置および共通の1次近傍無線装置のいずれに近いかを共通の1次近傍無線装置を複数回変えて判定する処理である。
【0013】
位置更新手段は、仮想トポロジー生成手段によって仮想トポロジーが生成されると、位置推定処理において、対象無線装置とn次近傍無線装置との間の距離が演算手段によって演算されたnホップの無線装置間の距離に近づくように第1番目の修正ベクトル、第2番目の修正ベクトル、・・・、第n-1番目の修正ベクトルを順次適用して対象無線装置の仮の自己位置を推定する。
【0014】
また、この発明の実施の形態によれば、コンピュータに実行させるためのプログラムは、m(mは、4以上の整数)個の無線装置の位置推定をコンピュータに実行させるためのプログラムであって、取得手段が、1つの無線装置から1ホップの位置に存在する1次近傍無線装置の情報である隣接無線装置情報をm(mは、4以上の整数)個の無線装置の各々から取得する第1のステップと、トポロジー生成手段が、m個の無線装置についての隣接無線装置情報に基づいてm個の無線装置によって構成される無線ネットワークのトポロジーを生成する第2のステップと、位置情報生成手段が、m個の無線装置の仮の自己位置を示すm個の仮の自己位置情報を生成する位置情報生成処理を行う第3のステップと、位置更新手段が、第3のステップにおいて位置情報生成処理が実行されると、無線ネットワークのトポロジーおよびm個の仮の自己位置情報に基づいてm個の無線装置の各々について位置推定処理を所望回数実行してm個の無線装置の位置を更新する更新処理を行う第4のステップと、判定手段が、第4のステップにおいて更新処理が実行されると、1つの無線装置の推定された位置が1つの無線装置の隣接無線装置よりも1つの無線装置から2ホップの位置に存在する2次近傍無線装置に近いことを示すトポロジー矛盾の有無を領域判定処理によって判定する判定処理を行う第5のステップと、演算手段が、第5のステップにおいてトポロジー矛盾が無いと判定されると、m個の無線装置の更新されたm個の更新位置を用いてn(nは1以上の整数)ホップの無線装置間の距離、nホップの無線装置間の距離の平均値およびnホップの無線装置間の距離の期待値を演算する第6のステップと、仮想トポロジー生成手段が、第6のステップにおいて演算されたnホップの無線装置間の距離の平均値とnホップの無線装置間の距離の期待値とに基づいてm個の無線装置のうちの位置推定の対象となる対象無線装置からnホップ目までの各位置における無線通信のカバレッジを求め、追加された仮想の無線装置の隣接無線装置情報とm個の無線装置の更新された隣接無線装置情報とをカバレッジを用いて作成し、その作成した仮想の無線装置の隣接無線装置情報とm個の無線装置の更新された隣接無線装置情報とを用いて無線ネットワークの仮想トポロジーを生成する第7のステップとを備え、位置情報生成手段は、第5のステップにおいてトポロジー矛盾が有ると判定される毎、または第7のステップにおいて仮想トポロジーが生成される毎に位置情報生成処理を実行し、位置推定処理は、対象無線装置の仮の自己位置情報と対象無線装置からnホップの位置に存在するn次近傍無線装置の仮の自己位置情報とに基づいて計算された対象無線装置とn次近傍無線装置との間の距離がnホップのホップ数からなる距離に近づくように対象無線装置の仮の自己位置を対象無線装置からのホップ数nに応じてそれぞれ修正するための1次修正ベクトル、2次修正ベクトル、・・・及びn次修正ベクトルからなるn個の修正ベクトルを、1次修正ベクトルとn次修正ベクトルとからなる第1番目の修正ベクトル、1次修正ベクトルとn-1次修正ベクトルとからなる第2番目の修正ベクトル、・・・、1次修正ベクトルと2次修正ベクトルとからなる第n-1番目の修正ベクトルの順に適用して前記対象無線装置の仮の自己位置を推定する処理であり、領域判定処理は、対象無線装置の推定された位置と対象無線装置の1次近傍無線装置の推定された位置との間の線分の垂直二等分線を基準として対象無線装置の2次近傍無線装置の推定された位置が対象無線装置および対象無線装置の1次近傍無線装置のいずれに近いかを判定し、当該判定に引き続いて、対象無線装置と対象無線装置の2次近傍無線装置との共通の1次近傍無線装置の推定された位置と対象無線装置の推定された位置との間の線分の垂直二等分線を基準として対象無線装置の2次近傍無線装置の推定された位置が対象無線装置および共通の1次近傍無線装置のいずれに近いかを共通の1次近傍無線装置を複数回変えて判定する処理であり、位置更新手段は、第7のステップにおいて仮想トポロジーが生成されると、第4のステップの位置推定処理において、対象無線装置とn次近傍無線装置との間の距離が第6のステップにおいて演算されたnホップの無線装置間の距離に近づくように第1番目の修正ベクトル、第2番目の修正ベクトル、・・・、第n-1番目の修正ベクトルを順次適用して対象無線装置の仮の自己位置を推定する、コンピュータに実行させるためのプログラムである。
【0015】
さらに、この発明の実施の形態によれば、コンピュータ読み取り可能な記録媒体は、請求項6から請求項10のいずれか一項に記載のプログラムを記録したコンピュータ読み取り可能な記録媒体である。
【発明の効果】
【0016】
この発明の実施の形態によれば、領域判定を用いてトポロジーの折れ曲がりによるトポロジー矛盾の有無を検出し、トポロジー矛盾が有ると、そのトポロジー矛盾が無いようにm個の無線装置の位置を推定するので、m個の無線装置の位置を高精度に推定できる。
【図面の簡単な説明】
【0017】
【図1】この発明の実施の形態による無線ネットワークの構成を示す概略図である。
【図2】図1に示すセンサーノードの構成を示す概略図である。
【図3】図1に示すシンクの構成を示す概略図である。
【図4】図1に示す位置推定装置の構成を示す概略図である。
【図5】トポロジー矛盾を示す概念図である。
【図6】領域判定を説明するための概念図である。
【図7】推定カバレッジの概念図である。
【図8】ホップ数とセンサーノード間の距離の期待値との関係を示す図である。
【図9】カバレッジRを用いて仮想センサーノードの隣接センサーノード情報の作成および実センサーノードの隣接センサーノード情報の更新を行う方法を説明するための図である。
【図10】図1に示す位置推定装置におけるセンサーノードの位置の推定方法を説明するためのフローチャートである。
【図11】図10に示すステップS10の詳細な動作を説明するためのフローチャートである。
【図12】位置推定の誤りの平均とセンサーノードの個数との関係を示す図である。
【図13】距離のエラーとセンサーノードの個数との関係を示す図である。
【図14】シミュレーションの諸元を示す図である。
【図15】本発明の実施の形態による位置推定方法におけるパラメータ諸元を示す図である。
【図16】通信回数とセンサーノードの個数との関係を示す図である。
【図17】障害物により構成されるネットワークのトポロジーの形状を示す図である。
【図18】C型トポロジーにおける相対位置評価と絶対位置評価を示す図である。
【図19】L型トポロジーにおける相対位置評価と絶対位置評価を示す図である。
【図20】H型トポロジーにおける相対位置評価と絶対位置評価を示す図である。
【図21】O型トポロジーにおける相対位置評価と絶対位置評価を示す図である。
【図22】C型トポロジーにおけるアンカーノードの個数に応じたDV-hopの位置推定誤差を示す図である。
【図23】C型トポロジーにおけるオリジナルのトポロジーと本発明の位置推定方法とDV-hopそれぞれの推定トポロジーを示す図である。
【図24】L型トポロジーにおけるオリジナルのトポロジーと本発明の位置推定方法とDV-hopそれぞれの推定トポロジーを示す図である。
【図25】H型トポロジーにおけるオリジナルのトポロジーと本発明の位置推定方法とDV-hopそれぞれの推定トポロジーを示す図である。
【図26】O型トポロジーにおけるオリジナルのトポロジーと本発明の位置推定方法とDV-hopそれぞれの推定トポロジーを示す図である。
【発明を実施するための形態】
【0018】
本発明の実施の形態について図面を参照しながら詳細に説明する。なお、図中同一または相当部分には同一符号を付してその説明は繰返さない。

【0019】
図1は、この発明の実施の形態による無線ネットワークの構成を示す概略図である。図1を参照して、この発明の実施の形態による無線ネットワーク10は、センサーノード1~7と、シンク8とを備える。

【0020】
センサーノード1~7のうちの3個のセンサーノードは、アンカーノードである。センサーノード1~7は、無線通信空間に配置される。センサーノード1~7の各々は、温度、湿度、および回転速度等のセンサー値を検出し、その検出したセンサー値を無線通信によってシンク8へ送信する。

【0021】
また、センサーノード1~7の各々は、自己の識別情報(例えば、アドレス)を含む広告パケットを生成し、その生成した広告パケットをブロードキャストする。そして、センサーノード1~7の各々は、他のセンサーノードから広告パケットを受信すると、その受信した広告パケットに含まれる識別情報を検出する。この場合、センサーノード1~7の各々は、複数の広告パケットを受信した場合、複数の広告パケットから複数の識別情報を検出する。

【0022】
そうすると、センサーノード1~7の各々は、その検出した少なくとも1つの識別情報からなる識別情報リストを作成し、その作成した識別情報リストと自己の識別情報とを対応付けた隣接センサーノード情報を生成し、その生成した隣接センサーノード情報を含むパケットPKT_DTGを生成してシンク8へ送信する。この隣接センサーノード情報は、各センサーノード1~7が他のセンサーノードから直接受信した広告パケットから検出した識別情報を含むので、各センサーノード1~7から1ホップの位置に存在するセンサーノードの情報を示す。

【0023】
なお、図1においては、センサーノード1~7の全てがパケットPKT_DTGをシンク8へ直接送信するように図示しているが、パケットPKT_DTGがセンサーノード1~7からシンク8へ直接送信できない場合、センサーノード1~7からのパケットPKT_DTGをマルチホップでシンク8へ送信する。

【0024】
シンク8は、センサーノード1~7の各々からパケットPKT_DTGを受信し、その受信したパケットPKT_DTGから隣接センサーノード情報を検出し、その検出した隣接センサーノード情報を位置推定装置9へ送信する。

【0025】
位置推定装置9は、例えば、クラウド上に設置される。そして、位置推定装置9は、シンク8から隣接センサーノード情報を受信する。これによって、位置推定装置9は、センサーノード1~7の全てから隣接センサーノード情報を取得する。位置推定装置9は、隣接センサーノード情報を取得すると、その取得した隣接センサーノード情報に基づいて、センサーノード1~7の配置関係を示すトポロジーを作成する。その後、位置推定装置9は、その作成したトポロジーに基づいて、後述する方法によってセンサーノード1~7の位置を推定する。

【0026】
図2は、図1に示すセンサーノード1の構成を示す概略図である。図2を参照して、センサーノード1は、アンテナ11と、送受信部12と、制御部13とを含む。なお、図2においては、センサーノード1が搭載するセンサーを図示していないが、センサーノード1は、センサーを搭載している。

【0027】
送受信部12は、アンテナ11を介して広告パケットを受信し、その受信した広告パケットを制御部13へ出力する。

【0028】
また、送受信部12は、センサーノード1の識別情報を含む広告パケットを制御部13から受けると、その受けた広告パケットをアンテナ11を介してブロードキャストする。

【0029】
さらに、送受信部12は、隣接センサーノード情報を含むパケットPKT_DTGを制御部13から受けると、その受けたパケットPKT_DTGをアンテナ11を介してシンク8へ送信する。

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

【0031】
制御部13は、送受信部12から広告パケットを受けると、その受けた広告パケットから識別情報を検出する。例えば、センサーノード1がセンサーノード2,4,5から広告パケットを受信した場合、制御部13は、3個の広告パケットからそれぞれ識別情報Address2,Address4,Address5を検出する。そして、制御部13は、識別情報Address1と識別情報Address2,Address4,Address5とを対応付けた隣接センサーノード情報を生成し、その生成した隣接センサーノード情報を含むパケットPKT_DTGを生成して送受信部12へ出力する。

【0032】
なお、図1に示すセンサーノード2~7の各々も、図2に示すセンサーノード1と同じ構成からなる。

【0033】
図3は、図1に示すシンク8の構成を示す概略図である。図3を参照して、シンク8は、アンテナ81と、送受信部82と、制御部83とを含む。

【0034】
送受信部82は、アンテナ81を介してパケットPKT_DTGを受信し、その受信したパケットPKT_DTGを制御部83へ出力する。

【0035】
また、送受信部82は、制御部83から隣接センサーノード情報を受けると、その受けた隣接センサーノード情報をアンテナ81およびインターネットを介して位置推定装置9へ送信する。

【0036】
制御部83は、送受信部82からパケットPKT_DTGを受けると、その受けたパケットPKT_DTGから隣接センサーノード情報を検出し、その検出した隣接センサーノード情報を送受信部82へ出力する。

【0037】
図4は、図1に示す位置推定装置9の構成を示す概略図である。図4を参照して、位置推定装置9は、受信部91と、取得手段92と、トポロジー生成手段93と、位置更新手段94と、位置情報生成手段95と、変換手段96と、判定手段97と、演算手段98と、仮想トポロジー生成手段99とを含む。

【0038】
受信部91は、シンク8からインターネットを介して隣接センサーノード情報を受信し、その受信した隣接センサーノード情報を取得手段92へ出力する。

【0039】
取得手段92は、受信部91から隣接センサーノード情報を受ける。そして、取得手段92は、全ての隣接センサーノード情報を受信部91から受けると、その受けた全ての隣接センサーノード情報をトポロジー生成手段93および位置情報生成手段95へ出力する。

【0040】
トポロジー生成手段93は、隣接センサーノード情報を取得手段92から受ける。そして、トポロジー生成手段93は、隣接センサーノード情報に基づいて、無線ネットワーク10におけるセンサーノード1~7の配置関係を示すトポロジーを生成する。そうすると、トポロジー生成手段93は、その生成したトポロジーを位置更新手段94へ出力する。

【0041】
位置更新手段94は、トポロジー生成手段93からセンサーノード1~7のトポロジーを受け、位置情報生成手段95からセンサーノード1~7の仮の自己位置情報を受ける。そして、位置更新手段94は、センサーノード1~7のトポロジーおよび仮の自己位置情報に基づいて、後述する方法によってセンサーノード1~7の位置を推定する。

【0042】
位置更新手段94は、センサーノード1~7の位置推定を予め設定された設定回数行うと、その推定したセンサーノード1~7の位置を変換手段96へ出力する。

【0043】
位置更新手段94は、センサーノード1~7の推定位置を1回目に変換手段96へ出力した後、後述する距離D_calを演算手段98から受け、仮想トポロジーを仮想トポロジー生成手段99から受けると、その受けた距離D_calおよび仮想トポロジーを用いて後述する方法によってセンサーノード1~7の位置推定を予め設定された設定回数行う。

【0044】
位置情報生成手段95は、取得手段92から隣接センサーノード情報を受け、その受けた隣接センサーノード情報に基づいて、無線ネットワーク10を構成するセンサーノード1~7を認識する。

【0045】
そして、位置情報生成手段95は、その認識したセンサーノード1~7の仮の自己位置を示す仮の自己位置情報をランダムに生成する。この場合、位置情報生成手段95は、センサーノードi(i=1~7)の仮の自己位置のt(tは正の整数)回目の更新時に仮の自己位置wi(t)をランダムに生成する。仮の自己位置wi(t)は、2次元の位置情報からなる。

【0046】
また、位置情報生成手段95は、後述するトポロジー矛盾が有ることを示す信号TP_incosを判定手段97から受けたとき、または仮想トポロジーを生成したことを示す信号VTPを仮想トポロジー生成手段99から受けたとき、センサーノード1~7の仮の自己位置情報をランダムに生成する。

【0047】
そうすると、位置情報生成手段95は、その生成したセンサーノード1~7の仮の自己位置情報を位置更新手段94へ出力する。

【0048】
変換手段96は、アンカーノードの絶対位置を予め保持している。変換手段96は、センサーノード1~7の推定された推定位置を位置更新手段94から受け、その受けたセンサーノード1~7の推定位置とアンカーノードの絶対位置とに基づいて、後述する方法によってセンサーノード1~7の推定位置を絶対位置に変換する。そして、変換手段96は、その変換したセンサーノード1~7の絶対位置を判定手段97へ出力する。

【0049】
判定手段97は、センサーノード1~7の絶対位置を変換手段96から受け、その受けたセンサーノード1~7の絶対位置に基づいて、後述する方法によってトポロジー矛盾の有無を判定する。

【0050】
そして、判定手段97は、トポロジー矛盾が有ると判定したとき、信号TP_incosを位置情報生成手段95へ出力する。

【0051】
一方、判定手段97は、トポロジー矛盾が無いと判定したとき、トポロジー矛盾が無いことを示す信号TP_cosおよびセンサーノード1~7の絶対位置を演算手段98および仮想トポロジー生成手段99へ出力する。

【0052】
演算手段98は、信号TP_cosおよびセンサーノード1~7の絶対位置を判定手段97から受けると、センサーノード1~7の絶対位置に基づいて、センサーノード1~7の各々を位置推定の対象とした対象センサーノードからn(nは1≦n≦最大ホップ数)ホップの位置までの距離D_cal、対象センサーノードからnホップの位置までの距離D_calの平均M、および対象センサーノードからnホップの位置までの距離D_calの期待値Eを演算する。

【0053】
そして、演算手段98は、その演算した距離D_calを位置更新手段94へ出力し、その演算した平均Mおよび期待値Eを仮想トポロジー生成手段99へ出力する。

【0054】
仮想トポロジー生成手段99は、判定手段97から信号TP_cosおよびセンサーノード1~7の絶対位置を受け、演算手段98から平均Mおよび期待値Eを受ける。そして、仮想トポロジー生成手段98は、平均Mおよび期待値Eに基づいて後述する方法によって無線通信のカバレッジを求め、その求めた無線通信のカバレッジおよびセンサーノード1~7の絶対位置に基づいて、後述する方法によって仮想トポロジーを生成する。そして、仮想トポロジー生成手段99は、その生成した仮想トポロジーを位置更新手段94へ出力する。

【0055】
[トポロジーの生成]
トポロジー生成手段93におけるトポロジーの生成方法について説明する。

【0056】
(1)センサーノードiの隣接センサーノード情報に含まれるセンサーノードをセンサーノードiの1次近傍センサーノードj(jは、i≠jを満たし、1~7)とする。

【0057】
(2)1次近傍センサーノードjの隣接センサーノード情報に含まれるセンサーノードで、センサーノードiの隣接センサーノード情報に含まれないセンサーノードを、センサーノードjを中継センサーノードとするセンサーノードiの2次近傍センサーノードとする。

【0058】
(3)同様に、n次近傍センサーノードxの隣接センサーノード情報に含まれて、(n-1)次までの近傍センサーノード群の隣接センサーノード情報に含まれないセンサーノードを、センサーノードxを中継センサーノードとするセンサーノードiの(n+1)次近傍センサーノードとする。

【0059】
(4)上記(1)~(3)を再帰的に繰り返し、センサーノードiの近傍トポロジーを拡大し、ネットワーク全体を通してセンサーノードiの多次近傍センサーノードを設定する。

【0060】
トポロジー生成手段93は、上記(1)~(4)をセンサーノード1~7の全体について実行し、センサーノード1~7のトポロジーを生成する。

【0061】
[位置推定方法]
位置更新手段94における位置推定方法について説明する。

【0062】
トポロジーの生成において説明したように、トポロジーは、センサーノードiからn次近傍センサーノードまでを考慮して生成されるので、位置更新手段94は、センサーノード1~7のトポロジーを用いてセンサーノードiの仮の自己位置wi(t)を更新する場合、センサーノードiからnホップ目の位置に存在するn次近傍センサーノード以下のセンサーノード(=多次近傍センサーノード)を認識できる。

【0063】
多次近傍センサーノードの情報は、ホップ数に応じてセンサーノード間の距離が増加するように構成されている。すなわち、センサーノードiの位置更新のために選択されるセンサーノードは、センサーノードiからn次近傍センサーノード以下であり、かつ、センサーノードiからの(n-1)次近傍センサーノードのいずれのセンサーノードよりもセンサーノードiから遠方に位置する条件を満たす。

【0064】
従って、1ホップのセンサーノード間の距離を一定距離dとすると、センサーノードiからn次近傍センサーノードまでの距離は、一定距離d×ホップn=ndで表される。

【0065】
そして、この発明の実施の形態においては、位置推定の対象となるセンサーノードiの仮の自己位置を更新する場合、センサーノードiの仮の自己位置wi(t)とn次近傍センサーノードの仮の自己位置wn(t)とを用いて計算された距離|wi(t)-wn(t)|がセンサーノードiからn次近傍センサーノードまでのホップ数からなる距離ndに近づくようにセンサーノードiの仮の自己位置wi(t)を修正する。

【0066】
この場合、n次近傍センサーノードの仮の自己位置wn(t)を用いてセンサーノードiの仮の自己位置wi(t)を修正するときのn次修正ベクトルは、次式によって求められる。

【0067】
【数1】
JP0006467334B2_000002t.gif

【0068】
そして、この発明の実施の形態においては、位置修正の初期段階においては、広い範囲の近傍センサーノードを用いて大域的にトポロジーを形成し、修正段階の進行に伴い、位置修正に使用する近傍センサーノードのホップ数を減少させて、局所的かつ詳細なトポロジーを形成し、収束させる。

【0069】
従って、次式(2)に従ってセンサーノードiの仮の自己位置wi(t)を更新する。

【0070】
【数2】
JP0006467334B2_000003t.gif

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

【0072】
【数3】
JP0006467334B2_000004t.gif

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

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

【0075】
そして、位置更新手段94は、式(2)の右辺の最上段の修正ベクトルから最下段の修正ベクトルまでを順次適用して式(2)に従ってセンサーノードiの仮の自己位置wi(t)を更新する。

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

【0077】
従って、位置更新手段94は、センサーノード1の1次近傍センサーノードとn次近傍センサーノードとを用いてセンサーノードiの仮の自己位置wi(t)を更新し、その後、センサーノード1の1次近傍センサーノードと(n-1)次近傍センサーノードとを用いてセンサーノードiの仮の自己位置wi(t)を更新し、以下、同様にして、センサーノード1の1次近傍センサーノードと3次近傍センサーノードとを用いてセンサーノードiの仮の自己位置wi(t)を更新し、最終的に、センサーノード1の1次近傍センサーノードと2次近傍センサーノードとを用いてセンサーノードiの仮の自己位置wi(t)を更新する。

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

【0079】
修正ベクトル(Vi{1}(t)+Vi{n}(t))、(Vi{1}(t)+Vi{n-1}(t))、・・・、(Vi{1}(t)+Vi{3}(t))を用いた仮の自己位置wi(t)の更新回数は、相互に均等であり、修正ベクトル(Vi{1}(t)+Vi{2}(t))を用いた仮の自己位置wi(t)の更新回数は、修正ベクトル(Vi{1}(t)+Vi{n}(t))、(Vi{1}(t)+Vi{n-1}(t))、・・・、(Vi{1}(t)+Vi{3}(t))を用いた仮の自己位置wi(t)の更新回数の2倍である。

【0080】
従って、10次修正ベクトル(n=10)までを用いてセンサーノードiの仮の自己位置wi(t)を更新する場合、修正ベクトル(Vi{1}(t)+Vi{10}(t))、(Vi{1}(t)+Vi{9}(t))、・・・、(Vi{1}(t)+Vi{3}(t))を用いた更新回数を1回とすれば、修正ベクトル(Vi{1}(t)+Vi{2}(t))を用いた更新回数は、2回である。その結果、全ての修正ベクトルを用いた更新回数は、10回となる。

【0081】
また、修正ベクトル(Vi{1}(t)+Vi{10}(t))、(Vi{1}(t)+Vi{9}(t))、・・・、(Vi{1}(t)+Vi{3}(t))を用いた更新回数を2回とすれば、修正ベクトル(Vi{1}(t)+Vi{2}(t))を用いた更新回数は、4回である。その結果、全ての修正ベクトルを用いた更新回数は、20回となる。

【0082】
更に、修正ベクトル(Vi{1}(t)+Vi{10}(t))、(Vi{1}(t)+Vi{9}(t))、・・・、(Vi{1}(t)+Vi{3}(t))を用いた更新回数を3回とすれば、修正ベクトル(Vi{1}(t)+Vi{2}(t))を用いた更新回数は、6回である。その結果、全ての修正ベクトルを用いた更新回数は、30回となる。

【0083】
従って、修正ベクトル(Vi{1}(t)+Vi{10}(t))、(Vi{1}(t)+Vi{9}(t))、・・・、(Vi{1}(t)+Vi{3}(t))を用いた更新回数をp(pは整数)回とすれば、全ての修正ベクトルを用いた更新回数は、一般的には、8p+2p=10p回となる。

【0084】
更新回数10pにおける”10”は、n次修正ベクトルのn=10に等しいので、式(2)の右辺における全ての修正ベクトルを用いた更新回数は、一般的には、np回となる。

【0085】
従って、式(2)を用いた仮の自己位置wi(t)の更新回数は、nを決定し、その後、pを決定することにより、決定される。nを決定することは、センサーノードiからどの程度のホップ数の位置に存在する近傍センサーノードの仮の自己位置を仮の自己位置wi(t)の更新に用いるかを決定することに相当する。また、pを決定することは、仮の自己位置wi(t)を大局的に更新する回数を決定することに相当する。

【0086】
[トポロジー矛盾の判定]
(I)距離判定
図5は、トポロジー矛盾を示す概念図である。図5を参照して、センサーノードiは、仮の自己位置wi(t)に存在する。そして、センサーノードiから距離d1の位置に1次近傍センサーノードが存在し、センサーノードiから距離d2の位置に2次近傍センサーノードが存在する。

【0087】
その結果、センサーノードiの仮の自己位置wi(t)は、1次近傍センサーノードよりも2次近傍センサーノードに近い。これは、2次近傍センサーノードがセンサーノードiから1次近傍センサーノードよりも遠い位置に存在すると言う本来のトポロジーに明らかに矛盾する。

【0088】
従って、位置推定の対象であるセンサーノードiの仮の自己位置wi(t)が1次近傍センサーノードよりも2次近傍センサーノードに近いことをトポロジー矛盾と言う。

【0089】
そして、位置推定の対象であるセンサーノードiの仮の自己位置wi(t)が1次近傍センサーノードよりも2次近傍センサーノードに近いか否かの判定を複数の1次近傍センサーノードと2次近傍センサーノードで実施し、次式を満たさない場合、センサーノードiの推定位置は、トポロジー矛盾有りと判定する。

【0090】
【数4】
JP0006467334B2_000005t.gif

【0091】
式(4)において、Ii{2}は、センサーノードiにおいてトポロジー矛盾と判定した2次近傍センサーノードの個数を示し、Ni{2}は、トポロジー矛盾の判定に用いた2次近傍センサーノードの個数を示し、λは、トロポジー矛盾の閾値である。

【0092】
上記の判定は、距離を用いて行われるので、距離判定と言う。

【0093】
(II)領域判定
図6は、領域判定を説明するための概念図である。

【0094】
図5に示すように、トポロジー矛盾有りと判定される場合、トポロジーの折れ曲がりが発生する。そして、このトポロジーの折れ曲がりは、センサーノードiから1次近傍センサーノードまでの距離と、センサーノードiから2次近傍センサーノードまでの距離とを用いた判定(上述の距離判定)によって検知できない場合がある。

【0095】
図6の(a)に示すように、センサーノードi、センサーノードiの1次近傍センサーノードj、およびセンサーノードiの2次近傍センサーノードであり、かつ、1次近傍センサーノードjの1次近傍センサーノードであるセンサーノードlの推定位置をそれぞれwi,wj,wlとし、センサーノードlの真の位置をWlとすると、wlは、折れ曲がりトポロジーの要因となる。

【0096】
この場合、wi,wjを基準点とするwlのトポロジー矛盾判定は、wlのトポロジー矛盾を検知できる範囲|wl-wi|≦|wj-wi|の外にある(=トポロジー矛盾無しの条件を満たす)ので、wlによる折れ曲がりを検知できない。すなわち、上述した距離判定によるトポロジー矛盾判定は、折れ曲がりトポロジーを十分に検知可能とする領域をカバーできていない。

【0097】
そこで、次のように、トポロジー矛盾判定の適応領域を拡大する。

【0098】
図6の(b)を参照して、基準点wi,wjにおいて、線分L1=wj-wiの垂直2等分線L1Hを用いてwlがwi,wjのいずれかに近い領域に空間を2分割する。

【0099】
この場合、垂直2等分線L1Hの左側の領域(斜線を施した領域)は、wlがwiに近い領域であり、垂直2等分線L1Hの右側の領域は、wlがwjに近い領域である。

【0100】
センサーノードlは、センサーノードiの2次近傍センサーノードであるので、wlは、wjに近い領域内に位置しなければならない。

【0101】
従って、wlがwiに近い領域(斜線を施した領域)に位置する場合(|wl—wi|≦|wl—wj|)、トポロジー矛盾有りと判定する。

【0102】
更に、折れ曲がりによるトポロジー矛盾の検知領域を拡大するために、図6の(c)に示すように、センサーノードjに加えてセンサーノードiとセンサーノードlの共通の1次近傍センサーノードkを基準点として用いる。そして、基準点wi,wkにおいて、線分L2=wk-wiの垂直2等分線L2Hを用いてwlがwi,wkのいずれかに近い領域に空間を2分割する。

【0103】
この場合、垂直2等分線L2Hの左側の領域(斜線を施した領域)は、wlがwiに近い領域であり、垂直2等分線L2Hの右側の領域は、wlがwkに近い領域である。

【0104】
センサーノードlは、センサーノードiの2次近傍センサーノードであるので、wlは、wkに近い領域内に位置しなければならない。

【0105】
従って、wlがwiに近い領域(斜線を施した領域)に位置する場合(|wl—wi|≦|wl—wk|)、トポロジー矛盾有りと判定する。

【0106】
図6の(c)に示す領域判定は、共通の1次近傍センサーノードの組み合わせを複数回変えて実施される。そして、複数回実施した結果において、式(5)を満たさない場合、トポロジー矛盾有りと判定する。

【0107】
【数5】
JP0006467334B2_000006t.gif

【0108】
式(5)において、Aは、共通1次近傍群を用いた領域判定を行った回数を示し、aは、トポロジー矛盾の発生回数を示し、βは、閾値である。

【0109】
図6の(b),(c)に示す2つの領域判定を順次適用することにより、折れ曲がりによるトポロジー矛盾の検知領域を拡大でき、折れ曲がりによるトポロジー矛盾を効果的に検知できる。

【0110】
上述した距離判定および領域判定の少なくとも1つによってトポロジー矛盾有りと判定された場合、センサーノードiの学習関数αi(t)を初期値(=1)に戻し、位置推定処理を再度実行する。

【0111】
[仮想トポロジーの生成]
上述したトポロジー矛盾の判定において、トポロジー矛盾無しと判定された場合、推定位置は、高い精度で推定された位置となる。すなわち、各センサーノードの推定位置から得られるセンサーノード間の距離も、精度が高いと仮定できる。

【0112】
そこで、センサーノード間の距離を用いて次のようにネットワークのトポロジーを再設定する。

【0113】
(I)センサーノード間の距離の変更
センサーノード間の距離をホップ数から推定位置に基づいて得られるセンサーノード間の距離に変更する。すなわち、高い精度を有するセンサーノード間の距離を用いることによって位置推定の精度を向上させる。

【0114】
(II)仮想センサーノードの追加
センサーノードの推定位置に基づいて、各センサーノードの隣接(1ホップ)センサーノードとの間の距離の平均M(1)を算出する。

【0115】
無線通信のカバレッジをRとすると、カバレッジR内にセンサーノードが一様に分布する場合、カバレッジRを有するセンサーノードの近傍センサーノードまでの距離の期待値d{n}は、次式によって決定される。

【0116】
【数6】
JP0006467334B2_000007t.gif

【0117】
式(6)において、xは、(n-1)R≦x≦nRを満たす。

【0118】
カバレッジRを有するセンサーノードと、そのセンサーノードから1ホップの位置に存在するセンサーノードとの間の距離の期待値d{1}と平均M{1}とからカバレッジRを求める。この求めたカバレッジRを推定カバレッジRとする。

【0119】
そして、任意の仮想センサーノードを既に作成されたトポロジー内に配置し、推定カバレッジRを用いて仮想センサーノードの隣接センサーノード情報の作成と、実際のセンサーノードの隣接センサーノード情報の更新を行い、仮想トポロジーを生成する。

【0120】
図7は、推定カバレッジの概念図である。また、図8は、ホップ数とセンサーノード間の距離の期待値との関係を示す図である。

【0121】
図8におけるセンサーノード間の距離の期待値d{n}は、式(6)を用いて計算された期待値である。

【0122】
図7を参照して、センサーノードiから(n-1)ホップまでのカバレッジは、(n-1)Rによって表され、センサーノードiからnホップまでのカバレッジは、nRによって表される。そして、カバレッジ(n-1)R,nRは、同心円状に配置される。

【0123】
その結果、センサーノードiからnホップのセンサーノードは、カバレッジnRからカバレッジ(n-1)Rを除いた領域内に位置する。

【0124】
各センサーノードの推定位置に基づいて、1ホップの位置に存在するセンサーノードまでの距離の平均M{1}、2ホップの位置に存在するセンサーノードまでの距離の平均M{2}、・・・、nホップの位置に存在するセンサーノードまでの距離の平均M{n}を計算することができる。

【0125】
図8に示す期待値d{n}によれば、1ホップの位置に存在するセンサーノードまでの距離の期待値d{1}は、d{1}=0.67Rによって表され、2ホップの位置に存在するセンサーノードまでの距離の期待値d{2}は、d{2}=1.56Rによって表され、3ホップの位置に存在するセンサーノードまでの距離の期待値d{3}は、d{3}=2.53Rによって表され、4ホップの位置に存在するセンサーノードまでの距離の期待値d{4}は、d{4}=3.52Rによって表され、5ホップの位置に存在するセンサーノードまでの距離の期待値d{5}は、d{5}=4.52Rによって表される。

【0126】
従って、計算した平均M{1}をd{1}=0.67Rの期待値d{1}に代入することにより、1ホップの位置におけるカバレッジR1を算出できる。また、計算した平均M{2}をd{2}=1.56Rの期待値d{2}に代入することにより、2ホップの位置におけるカバレッジR2を算出できる。以下、同様にして、3ホップの位置におけるカバレッジR3、4ホップの位置におけるカバレッジR4および5ホップの位置におけるカバレッジR5を算出できる。

【0127】
図9は、カバレッジRを用いて仮想センサーノードの隣接センサーノード情報の作成および実センサーノードの隣接センサーノード情報の更新を行う方法を説明するための図である。

【0128】
図9を参照して、実センサーノードであるセンサーノード1~7がそれぞれ推定位置w1~w7に配置されている。

【0129】
そして、4個の仮想センサーノードV1~V4をそれぞれ位置wV1~wV4に配置する。

【0130】
センサーノード1から1ホップ、2ホップ、3ホップ、4ホップおよび5ホップのカバレッジR1~R5は、センサーノード1を中心として同心円状に配置される。

【0131】
そして、領域REG1~REG5は、それぞれ、センサーノード1から1ホップのセンサーノード、2ホップのセンサーノード、3ホップのセンサーノード、4ホップのセンサーノード、および5ホップのセンサーノードが位置する領域である。

【0132】
センサーノード1を中心として同心円状のカバレッジR1~R5を配置すると、センサーノード2,7,3は、それぞれ、センサーノード1から1ホップ、2ホップおよび3ホップの位置に配置され、センサーノード4,5は、センサーノード1から4ホップの位置に配置され、センサーノード6は、センサーノード1から5ホップの位置に配置されていることが分かる。

【0133】
また、仮想センサーノードV1,V2は、それぞれ、センサーノード1から3ホップおよび4ホップの位置に配置され、仮想センサーノードV3,V4は、センサーノード1から5ホップの位置に配置されていることが分かる。

【0134】
そうすると、実センサーノード1~7および仮想センサーノードV1~V4が配置された状態で、仮想センサーノードV1~V4の隣接センサーノード情報を作成し、実センサーノード1~7の隣接センサーノード情報に仮想センサーノードV1~V4を追加して実センサーノード1~7の隣接センサーノード情報を更新する。

【0135】
そして、仮想センサーノードV1~V4の隣接センサーノード情報と、実センサーノード1~7の更新された隣接センサーノード情報とを用いて仮想トポロジーを生成する。

【0136】
演算手段98は、センサーノード1~7の推定された推定位置を用いて各センサーノードからnホップの位置に存在するセンサーノードまでの距離の平均M{n}および期待値d{n}を演算し、その演算した平均M{n}および期待値d{n}を仮想トポロジー生成手段99へ出力する。

【0137】
仮想トポロジー生成手段99は、平均M{n}および期待値d{n}を演算手段98から受け、その受けた平均M{n}および期待値d{n}を用いてカバレッジRを求め、その求めたカバレッジRを用いて、上述した方法によって、仮想トポロジーを生成する。そして、仮想トポロジー生成手段99は、その生成した仮想トポロジーを位置更新手段94へ出力する。

【0138】
なお、追加する仮想センサーノードの個数は、任意であり、仮想センサーノードの配置位置も任意である。

【0139】
[絶対位置への変換]
上述した位置推定処理によって推定される位置は、相対位置である。この相対位置をアンカーノードの推定位置と絶対位置とを用いて絶対位置へ変換する。

【0140】
アンカーノードの真位置(=絶対位置)をWA=(XA,YA)とし、推定位置をwA=(xA,yA)とすると、真位置WA=(XA,YA)は、推定位置wA=(xA,yA)を用いて次式のように表される。

【0141】
【数7】
JP0006467334B2_000008t.gif

【0142】
3つのアンカーノードから構成される連立方程式(7)から6つの係数a,b,c,d,tx,tyを得ることにより、全てのセンサーノードの推定位置wi=(xi,yi)は、次式によって絶対位置Wi=(Xi,Yi)へ変換される。

【0143】
【数8】
JP0006467334B2_000009t.gif

【0144】
変換手段96は、式(7)から係数a,b,c,d,tx,tyを決定し、その決定した係数a,b,c,d,tx,tyを式(8)に代入してセンサーノード1~7の全ての推定位置を絶対位置に変換する。

【0145】
位置推定装置9におけるセンサーノード1~7の位置の推定方法について説明する。

【0146】
図10は、図1に示す位置推定装置9におけるセンサーノード1~7の位置の推定方法を説明するためのフローチャートである。

【0147】
図10を参照して、位置の推定が開始されると、位置推定装置9の取得手段92は、上述した方法によって全てのセンサーノード1~7の隣接センサーノード情報を取得する(ステップS1)。

【0148】
そして、取得手段92は、その取得した隣接センサーノード情報をトポロジー生成手段93および位置情報生成手段95へ出力する。

【0149】
トポロジー生成手段93は、隣接センサーノード情報を取得手段92から受け、その受けた隣接センサーノード情報に基づいて、上述した方法によってネットワーク(無線ネットワーク10)のトポロジーを生成し(ステップS2)、その生成したトポロジーを位置更新手段94へ出力する。

【0150】
位置更新手段94は、トポロジーをトポロジー生成手段93から受ける。そして、位置更新手段94は、トポロジーにおけるセンサーノード1~7間の距離をホップ数に設定し、位置の更新回数を設定し、トポロジー試行回数の上限を設定する(ステップS3)。ここで、センサーノード1~7間の距離をホップ数に設定するとは、センサーノード1~7間の距離をホップ数によって表すことであり、1ホップ間の距離をdで表し、2ホップ間の距離を2dで表し、以下、同様にしてnホップ間の距離をndで表すことを意味する。また、更新回数は、上述した[位置推定方法]の項目で説明した修正ベクトル(Vi{1}(t)+Vi{n}(t))、(Vi{1}(t)+Vi{n-1}(t))、・・・、(Vi{1}(t)+Vi{3}(t))を用いた仮の自己位置wi(t)の更新回数を設定することを意味する。更に、トポロジー試行回数の上限は、図10に示すフローチャートを用いてセンサーノード1~7の位置を推定する回数の上限値を意味する。

【0151】
ステップS3の後、位置情報生成手段95は、隣接センサーノード情報を取得手段92から受け、その受けた隣接センサーノード情報に基づいて、全てのセンサーノード1~7を認識し、その認識したセンサーノード1~7の仮の自己位置wi(t)をランダムに生成する(ステップS4)。

【0152】
位置更新手段94は、位置情報生成手段95から仮の自己位置wi(t)を受け、その受けた仮の自己位置wi(t)および式(1)~(3)を用いて仮の自己位置wi(t)を更新回数まで更新する(ステップS5)。

【0153】
そして、位置更新手段94は、その更新したセンサーノードiの位置を変換手段96へ出力し、変換手段96は、センサーノードiの推定位置を位置更新手段94から受ける。

【0154】
その後、変換手段96は、アンカーノードの真位置と推定位置とを用いて上述した方法によってセンサーノードiの推定位置を絶対位置に変換する(ステップS6)。

【0155】
そうすると、変換手段96は、センサーノードiの絶対位置を判定手段97へ出力する。

【0156】
判定手段97は、センサーノードiの絶対位置を変換手段96から受け、その受けたセンサーノードiの絶対位置に基づいて、上述した距離判定を行い、トポロジー矛盾が有るか否かを判定する(ステップS7)。

【0157】
ステップS7において、トポロジー矛盾が有ると判定されたとき、判定手段97は、信号TP_incosを生成して位置情報生成手段95へ出力し、その後、一連の動作は、ステップS4へ戻り、ステップS7において、トポロジー矛盾が無いと判定されるまで、ステップS4~ステップS7が繰り返し実行される。

【0158】
なお、ステップS4へ戻るとき、学習関数αi(t)は、初期値(=1)に戻される。また、ステップS4へ戻るとき、位置情報生成手段95は、信号TP_incosに応じて、センサーノードiの仮の自己位置wi(t)をランダムに生成して位置更新手段94へ出力する。

【0159】
そして、ステップS7において、トポロジー矛盾が無いと判定されると、判定手段97は、上述した領域判定を行い、トポロジー矛盾が有るか否かを判定する(ステップS8)。

【0160】
ステップS8において、トポロジー矛盾が有ると判定されたとき、判定手段97は、信号TP_incosを生成して位置情報生成手段95へ出力し、その後、一連の動作は、ステップS4へ戻り、ステップS8において、トポロジー矛盾が無いと判定されるまで、上述したステップS4~ステップS8が繰り返し実行される。

【0161】
なお、ステップS8からステップS4へ戻る場合も、学習関数αi(t)は、初期値(=1)に戻される。また、この場合も、位置情報生成手段95は、信号TP_incosに応じて、センサーノードiの仮の自己位置wi(t)をランダムに生成して位置更新手段94へ出力する。

【0162】
そして、ステップS8において、トポロジー矛盾が無いと判定されると、判定手段97は、試行回数がトポロジー試行回数の上限に等しいか否かを判定する(ステップS9)。

【0163】
ステップS9において、試行回数がトポロジー試行回数の上限に等しくないと判定されたとき、判定手段97は、信号TP_cosを生成し、その生成した信号TP_cosと、センサーノードiの絶対位置とを演算手段98および仮想トポロジー生成手段99へ出力する。

【0164】
仮想トポロジー生成手段99は、信号TP_cosおよびセンサーノードiの絶対位置を判定手段97から受ける。そして、仮想トポロジー生成手段99は、信号TP_cosに応じて、後述する方法によって、センサーノードi間の距離を推定位置に基づいて算出した距離に設定し、仮想センサーノードを設定して仮想トポロジーを生成する(ステップS10)。そして、仮想トポロジー生成手段99は、その生成した仮想トポロジーを位置更新手段94へ出力する。

【0165】
その後、一連の動作は、ステップS4へ戻り、ステップS9において、試行回数がトポロジー試行回数の上限に等しいと判定されるまで、上述したステップS4~ステップS10が繰り返し実行される。

【0166】
そして、ステップS9において、試行回数がトポロジー試行回数の上限に等しいと判定されると、センサーノードiの位置推定が終了する。

【0167】
図11は、図10に示すステップS10の詳細な動作を説明するためのフローチャートである。

【0168】
図11を参照して、図10のステップS9において、試行回数がトポロジー試行回数の上限に等しくないと判定されると、演算手段98は、信号TP_cosとセンサーノードiの絶対位置とを判定手段97から受ける。そして、演算手段98は、信号TP_cosに応じて、センサーノードiの絶対位置(推定位置)に基づいてセンサーノード間の距離を算出し、その算出したセンサーノード間の距離(センサーノード間演算距離)を位置更新手段94へ出力し、位置更新手段94は、演算手段98から受けたセンサーノード間の距離(センサーノード間演算距離)をセンサーノード間の距離に設定する(ステップS101)。

【0169】
その後、演算手段98は、センサーノード間の距離の平均および期待値を算出し(ステップS102)、その算出したセンサーノード間の距離の平均および期待値を仮想トポロジー生成手段99へ出力する。

【0170】
そして、仮想トポロジー生成手段99は、センサーノード間の距離の平均および期待値を演算手段98から受け、その受けたセンサーノード間の距離の平均および期待値を用いて上述した方法によって無線通信のカバレッジを算出する(ステップS103)。

【0171】
引き続いて、仮想トポロジー生成手段99は、任意の位置に任意の数の仮想センサーノードを配置し、センサーノードiの絶対位置(推定位置)と無線通信のカバレッジとを用いて、上述した方法によって仮想センサーノードの隣接センサーノード情報を作成する(ステップS104)。

【0172】
そして、仮想トポロジー生成手段99は、センサーノードiの絶対位置(推定位置)、無線通信のカバレッジ、および仮想センサーノードの位置に基づいて実センサーノードiの隣接センサーノード情報に仮想センサーノードを追加して実センサーノードiの隣接センサーノード情報を更新する(ステップS105)。

【0173】
その後、仮想トポロジー生成手段99は、実センサーノードの更新した隣接センサーノード情報と仮想センサーノードの隣接センサーノード情報とを用いて、トポロジー生成手段93におけるトポロジーの生成方法と同じ方法によって仮想トポロジーを生成する(ステップS106)。

【0174】
そして、一連の動作は、図10のステップS4へ移行する。

【0175】
図10に示すフローチャートにおいては、ステップS7においてトポロジー矛盾が有ると判定されたとき、またはステップS8においてトポロジー矛盾が有ると判定されたとき、センサーノードiの仮の自己位置wi(t)が新たにランダムに生成され(ステップS4参照)、その生成されたセンサーノードiの仮の自己位置wi(t)を用いてセンサーノードiの仮の自己位置wi(t)が更新される(ステップS5参照)。

【0176】
そして、ステップS7およびステップS8の両方において、トポロジー矛盾が無いと判定された場合、仮想センサーノードを追加して仮想トポロジーが生成される(ステップS10参照)。

【0177】
すなわち、折れ曲がりによるトポロジー矛盾が解消された場合(ステップS8参照)に仮想トポロジーが生成される。

【0178】
従って、折れ曲がりによるトポロジー矛盾の発生を抑制してセンサーノードiの位置を高精度に推定できる。

【0179】
また、図10に示すフローチャートにおいては、ステップS10からステップS4へ戻り、その後、ステップS5が実行される場合、ステップS10において、センサーノードiの推定位置を用いて算出した距離にセンサーノード間の距離を設定してセンサーノードiの仮の自己位置wi(t)を更新する(ステップS5参照)。

【0180】
従って、センサーノードiと1次近傍センサーノード~n次近傍センサーノードとの間の距離|wi(t)-w1(t)|,|wi(t)-w2(t)|,・・・,|wi(t)-wn(t)|が、それぞれ推定位置を用いて算出された1ホップ間の距離(1ホップ間の演算距離)、2ホップ間の距離(2ホップ間の演算距離)、・・・、nホップ間の距離(nホップ間の演算距離)に近づくようにセンサーノードiの仮の自己位置wi(t)を更新する。

【0181】
推定位置を用いて算出された距離(演算距離)は信頼性が高いので、推定位置を用いて算出された距離(演算距離)に近づくようにセンサーノードiの仮の自己位置wi(t)を更新することにより、センサーノードiの位置を高精度に推定できる。

【0182】
更に、図10に示すフローチャートにおいては、ステップS7が実行されなくてもよい。即ち、距離判定によるトポロジー矛盾の有無を判定せず、領域判定によるトポロジー矛盾の有無だけを判定してもよい。

【0183】
上述したように、領域判定によってトポロジー矛盾の有無を判定することによって、距離判定の対象領域よりも広い領域に判定対象の領域を拡大できるので、トポロジー矛盾の有無を高精度に判定できるからである。

【0184】
更に、図10に示すフローチャートにおいては、ステップS6が実行されなくてもよい。即ち、図10に示すフローチャートを用いてセンサーノード1~7の相対位置が推定されてもよい。

【0185】
センサーノード1~7の相対位置が推定された場合、その推定された相対位置に基づいて作成されたトポロジーは、センサーノード1~7の実際のトポロジーと相似になる。

【0186】
従って、センサーノード1~7のトポロジー形状が実際のトポロジー形状と根本的に異ならない限り、相対位置を用いて作成されたトポロジーの実用性がある。

【0187】
図12は、位置推定の誤りの平均とセンサーノードの個数との関係を示す図である。図12において、縦軸は、位置推定の誤りの平均ERRaveを表し、横軸は、センサーノードの個数を表す。

【0188】
そして、図12は、上述した領域判定によるトポロジー矛盾の有無の判定において、共通1次近傍センサーノードの個数を変えたときの位置推定の誤りの平均とセンサーノードの個数との関係を示す。

【0189】
図12を参照して、共通1次近傍センサーノードの個数を変えた場合、位置推定の誤りの平均ERRaveは、共通1次近傍センサーノードの個数によって大きな違いがなく、領域判定を行わない場合よりも低くなっている。

【0190】
従って、この発明の実施の形態においては、領域判定によってトポロジー矛盾の有無を判定する場合、共通1次近傍センサーノードの個数を特に制限することなく、共通1次近傍センサーノードの個数を任意の個数に設定することにした。

【0191】
図13は、距離のエラーとセンサーノードの個数との関係を示す図である。図13において、縦軸は、距離のエラーを表し、横軸は、センサーノードの個数を表す。

【0192】
また、黒三角は、実センサーノードであるセンサーノード1~7の隣接センサーノード情報を用いて作成したトポロジーを用いたときの距離のエラーとセンサーノードの個数との関係を示し、黒丸は、実センサーノードであるセンサーノード1~7の隣接センサーノード情報と仮想センサーノードの隣接センサーノード情報とを用いて作成した仮想トポロジーを用いたときの距離のエラーとセンサーノードの個数との関係を示す。

【0193】
図13を参照して、仮想トポロジーを用いたときの距離のエラーは、センサーノードの個数が増加するに従って、実センサーノードだけのトポロジーを用いたときの距離のエラーよりも大きく低下する。

【0194】
従って、仮想センサーノードを追加して作成した仮想トポロジーを用いてセンサーノード1~7の位置を推定することによって、距離のエラーを大きく低減できることが分かった。

【0195】
[シミュレーション評価]
シミュレーション評価について説明する。

【0196】
図14は、シミュレーションの諸元を示す図である。図15は、本発明の実施の形態による位置推定方法におけるパラメータ諸元を示す図である。図16は、通信回数とセンサーノードの個数との関係を示す図である。図17は、障害物により構成されるネットワークのトポロジーの形状を示す図である。

【0197】
シミュレーションを繰り返し、経験的に得た本発明の実施の形態による位置推定方法に用いる各パラメータを図15に示す。NLOS混在環境の2次元フィールドを図17に示す。障害物の配置を4通りとし、それぞれの障害物により構成されるネットワークのトポロジーの形状からC型トポロジー、L型トポロジー、H型トポロジー、O型トポロジーと呼ぶ。センサーノード間を結ぶ直線上に障害物がある場合をNLOSとし、センサーノード間の通信を不可とする。その他の場合は、LOSとし、センサーノード間の通信を可能とする。また、位置推定においては、フィールド範囲は未知とする。

【0198】
図16に、SOLと本発明による位置推定方法のそれぞれの位置推定までの全センサーノードの送信回数を示す。図16を参照して、本発明による位置推定方法は、大幅に送信回数を削減する。SOLは、位置更新を各センサーノードで実施するため、センサーノード間で更新された仮の自己位置を頻繁に交換する。そのため、通信量は、大きくなる。一方、本発明による位置推定方法は、位置更新をクラウド環境の仮想の無線ネットワークで実施するため、各センサーノードは、位置更新時の仮の自己位置の交換は不要であり、仮想の無線ネットワークの構成のために、自身の隣接センサーノード情報をクラウドサーバへ転送するだけである。従って、通信回数を大幅に低減できる。

【0199】
(相対位置評価と絶対位置評価)
以下の方式での比較評価を行う。DV-hopは、アンカーノードの個数が3個でも、推定可能なRange-Free方式であるため比較対象とする。他の方式は、各センサーノードが少なくとも3個のアンカーノードとLOSである必要があり、評価条件では適用できない。

【0200】
・本発明による位置推定方法
・SOL
・DV-hop
評価は、相対位置評価と絶対位置評価の2通り行う。相対位置評価は、推定されたセンサーノードの位置により構成されるネットワークの形状(推定ネットワーク形状)とオリジナルネットワークの形状の相似性を次式(11),(12)により評価する。

【0201】
【数11】
JP0006467334B2_000010t.gif

【0202】
【数12】
JP0006467334B2_000011t.gif

【0203】
dijは、推定位置におけるセンサーノードiとセンサーノードjの距離(推定距離)であり、Dijは、オリジナルのネットワークにおけるセンサーノードiとセンサーノードjの距離であり、Nは、位置推定センサーノードの集合であり、|N|は、センサーノードの数(集合Nの要素数)を示す。V[rij]が0に近づけば、推定ネットワーク形状は、オリジナルのネットワーク形状と相似となる。すなわち、V[rij]が0の場合、推定ネットワーク形状は、オリジナルのネットワーク形状にばらつきなく完全に一致する.
絶対位置評価は、推定された各センサーノードの位置と真位置のユークリッド距離の総和の平均である位置推定誤差Erraveを用いて評価する。Erraveは、次式によって求められる。

【0204】
【数13】
JP0006467334B2_000012t.gif

【0205】
Wiは、センサーノードiの真位置であり、wiは、推定位置を示す。以上の2つの評価を用いて、センサーノード間の相対位置関係が正しく、かつ、個々のセンサーノード位置が絶対位置として正しく推定されて有用な位置であるかを評価する。

【0206】
図18、図19、図20、および図21は、それぞれ、C型トポロジー、L型トポロジー、H型トポロジー、およびO型トポロジーにおける相対位置評価と絶対位置評価を示す図である。

【0207】
各図は、それぞれの評価ごとに全体スケール(左側)と詳細スケール(右側)とを示す。

【0208】
先ず、相対評価について説明する。図18のC型トポロジーの相対位置評価において、本発明の位置推定方法のV[rij]は、SOLのV[rij]より低く、かつ、0に極めて近い。一方、DV-hopのV[rij]は、SOLや本発明の位置推定方法と比較すると非常に大きい。この原因は、NLOS混在環境においては、DV-hopでは、算出された1ホップの距離精度が低いため、多角測量の最小二乗法から解が得られず、その場合には、センサーノードの位置を3個のアンカーノード重心として推定するためである。すなわち、NLOS混在環境においてアンカーノードの個数が3個では、DV-hopは、ほぼ機能しない。本発明の位置推定方法とSOLとを比較すると、本発明の位置推定方法のV[rij]は、SOLよりも常に低く、極めて0に近い。すなわち、本発明の位置推定方法は、SOLよりも高精度なトポロジー形状を再現でき、そのばらつきも極めて小さい。SOLは、いくつかのケースで折れ曲がりが発生し、V[rij]が高くなる。

【0209】
図19のL型トポロジーの相対評価V[rij]も、C型トポロジーと同等の傾向(本発明の位置推定方法は、SOLよりも常に低く極めて0に近く、DV-hopは、この2方式と比較して非常に高い)であるが、SOLのV[rij]がC型トポロジーの場合より低い値になっている。L型トポロジーは、縦方向と横方向の2つのブロックの組み合わせであり、比較的少ないホップ数でも形状の識別が可能である。一方、C型トポロジーは、上部と下部の横方向のブロックと左側の縦方向のブロックの3つのブロックの組み合わせであり、L型トポロジーと比較すると、ホップ数を重ねないと、その形状が識別できない。従って、SOLは、C型トポロジーよりL型トポロジーにおいて比較的折れ曲がりを抑制でき、そのV[rij]が低くなると考えられる。

【0210】
図20のH型トポロジーの相対評価は、C型トポロジーとほぼ同等の結果となる。H型トポロジーは、左右の縦方向のブロックと中央の横方向のブロックの3つのブロックの組み合わせであることから、C型トポロジーと同等の結果になると考えられる。

【0211】
図21のO型トポロジーの相対評価も同様の傾向であるが、SOLのV[rij]が他の型のトポロジーの場合より高く、DV-hopは、やはり他の2方式と比較すると非常に高い値であるが、V[rij]がセンサーノード数の増加に従って減少する。SOLのV[rij]が高くなる原因は、O型トポロジーが上下の横方向のブロックと左右の縦方向のブロックの4つのブロックの組み合わせであり、他の型のトポロジーより形状を識別するにはより多くのホップ数が必要なためと考えられる。DV-hopがセンサーノード数の増加とともにV[rij]が減少するのは、多角測量の最小二乗法が収束しないケースが少なくなっているためであるが、その値は、他の2方式と比較して圧倒的に高いことは変わらない。

【0212】
以上のことから、
・DV-hopは、いずれの型のトポロジーにおいてもオリジナルの形状を再現できない。すなわち、センサーノード間の相対的位置関係は、著しく不正である。

【0213】
・SOLは、トポロジーの型に依存して形状再現の精度が変動する。すなわち、トポロジーの型に依存してセンサーノード間の相対的位置関係が不正となる場合がある。

【0214】
・本発明の位置推定方法は、トポロジーの型に関わらず、高精度に形状を再現する。すなわち、トポロジーの型に依存せずに高精度なセンサーノード間の相対的位置関係を推定できる。
といえる。

【0215】
次に、絶対位置評価について述べる。図18の絶対位置評価において、本発明の位置推定方法は、SOLと比較して、位置推定誤差が非常に小さく、位置推定精度が圧倒的に高い。SOLは、少数のネットワークのトポロジーにおいて、部分的な形状は、正しく推定されているが、折れ曲がりが発生し、トポロジー全体として大きな誤差となる。数は少ないが、誤差が非常に大きなケースがあり、これが全トポロジーの平均誤差を大きく引き上げる。

【0216】
一方、本発明の位置推定方法は、完全に折れ曲がりトポロジーを抑制し、安定して低い誤差を維持する。DV-hopの位置推定誤差は、SOLより低くなっているが、相対位置評価で述べたように、DV-hopは、センサーノード間の相対位置関係が全く再現されておらず、位置推定誤差以上に位置情報としての有用性は非常に低い。

【0217】
図19の絶対位置評価では、SOLの位置推定誤差は、ノード数が増えると小さくなって安定し、DV-hopより良くなる。これは、前述したようにL型トポロジーは、少ないホップ数でも形状を識別できるため、SOLにおいても折れ曲がりが抑制され、C型トポロジーの場合より改善したためと考えられる。DV-hopは、C型トポロジーと同様に0.2から0.25となる。これは、大部分のセンサーノードが3個のアンカーノードの重心位置として推定しているためである。本発明の位置推定方法は、図18と同様に、その位置推定誤差は、安定して非常に小さい。

【0218】
図20の絶対位置評価では、SOLの値は、大きく変動し、図19のL型トポロジーの場合と明らかに異なる。大きな値となる場合は、折れ曲がりが多く発生しており、その原因は、相対評価で述べたように、H型トポロジーは、L型トポロジーと比較すると、その形状を識別するには多くのホップ数を必要とするためである。DV-hopの位置推定誤差は、上述したのと同様の結果となる。本発明の位置推定方法は、上述したのと同様に安定して非常に低い。

【0219】
図21のO型トポロジーの絶対位置評価では、SOLのH型トポロジーと同様に変動する。その原因は、C型トポロジー、H型トポロジーと同じ要因による。DV-hopの傾向が異なるが、これは、多角測量における最小二乗法から解が得られるケースが増えているためである。

【0220】
図22は、C型トポロジーにおけるアンカーノードの個数に応じたDV-hopの位置推定誤差を示す図である。この図から分かるようにアンカーノードの個数を増やしても、DV-hopの精度は改善しない。DV-hopでは、アンカーノード間にNLOSが混在すれば、1ホップの見積もり距離の精度が劣化し、多角測量のセンサーノードとアンカーノードとの間にNLOSが混在すると、精度の低い1ホップ距離に基づくセンサーノードとアンカーノードとの間の距離の精度は、さらに劣化する。この距離見積もり手法は、アンカーノードを増やしてもアンカーノード間を含むすべてのセンサーノード間においてNLOSとなる空間を排除できないため、改善されない。すなわち、多角測量は、LOS環境の距離を想定しており、DV-hopは、障害物がある環境ではアンカーノードを増やしてもセンサーノード間のNLOS環境を排除できないため、位置推定誤差の改善は困難となる。以上のことから、
・DV-hopは、NLOS混在環境では有用な位置推定ができない。

【0221】
・SOLは、トポロジーの型に依存して折れ曲がりが発生し、その位置精度が劣化する。

【0222】
・本発明の位置推定方法は、トポロジーの型に依存せず、高精度な位置を推定可能である。
といえる。

【0223】
図23、図24、図25および図26は、それぞれ、C型トポロジー、L型トポロジー、H型トポロジーおよびO型トポロジーにおけるオリジナルのトポロジーと本発明の位置推定方法とDV-hopそれぞれの推定トポロジーを示す図である。

【0224】
図23において、図18の相対位置評価が示すように、DV-hopの推定センサーノードの位置により構成されるネットワーク形状は、オリジナルネットワークの形状と著しく異なる。

【0225】
一方、本発明の位置推定方法により推定された形状は、オリジナルのネットワーク形状にほぼ一致する。図24、図25および図26に示すネットワーク形状においても、同様に、DV-hopにより推定された形状は、オリジナルのネットワークと著しく異なり、本発明の位置推定方法により推定された形状は、オリジナルのネットワーク形状にほぼ一致する。従って、C型トポロジー、L型トポロジー、H型トポロジー、O型トポロジーとなるNLOS混在環境において、本発明の位置推定方法は、ネットワークのトポロジーの形状再現に圧倒的に優れている。

【0226】
以上のことから、本発明の位置推定方法は、SOLでは折れ曲がる可能性があり、DV-hopでは推定困難であるNLOS環境においてもネットワーク全体の高精度な形状再現と高精度なセンサーノードの位置推定が維持可能である。

【0227】
上述したシミュレーション評価によって、本発明の位置推定方法は、センサーノードの位置を高精度に推定できることが分かった。

【0228】
上記においては、仮の自己位置wi(t)は、2次元の位置情報からなると説明したが、この発明の実施の形態においては、これに限らず、仮の自己位置wi(t)は、3次元の位置情報からなっていてもよい。

【0229】
この場合、センサーノード1~7のうち、4個のセンサーノードがアンカーノードであり、アンカーノードの真位置WA=(XA,YA,ZA)と推定位置wA=(xA,yA,zA)との関係は、次式のようになる。

【0230】
【数9】
JP0006467334B2_000013t.gif

【0231】
式(9)を用いて、4つのアンカーノードの真位置と推定位置とから12個の連立方程式を作成し、12個の連立方程式を解くことにより、係数a,b,c,d,e,f,g,h,i,tx,ty,tzを得る。

【0232】
そして、得られた係数a,b,c,d,e,f,g,h,i,tx,ty,tzを用いて、全てのセンサーノードiについて、次式によって推定位置wi=(xi,yi,zi)を絶対位置Wi=(Xi,Yi,Zi)に変換する。

【0233】
【数10】
JP0006467334B2_000014t.gif

【0234】
従って、仮の自己位置wi(t)が3次元の位置情報からなる場合、変換手段96は、式(9),(10)を用いてセンサーノードiの推定位置wi=(xi,yi,zi)を絶対位置Wi=(Xi,Yi,Zi)に変換する。

【0235】
また、上記においては、無線ネットワーク10は、センサーノード1~7を備えると説明したが、この発明の実施の形態においては、これに限らず、無線ネットワーク10は、一般的には、m(mは4以上の整数)個の無線装置を備えていればよい。上述した領域判定によってトポロジー矛盾の有無を判定するためには、位置推定の対象となる対象無線装置と、対象無線装置の1次近傍無線装置と、対象無線装置の2次近傍無線装置と、対象無線装置と2次近傍無線装置との共通1次近傍無線装置とが必要であるので、無線ネットワーク10は、少なくとも4個の無線装置を備えている必要があるからである。

【0236】
位置推定の対象が無線装置である場合、図10に示すフローチャートのステップS5において実行される位置推定処理は、次のように定義される。

【0237】
位置推定処理は、前記対象無線装置の仮の自己位置情報と前記対象無線装置からnホップの位置に存在するn次近傍無線装置の仮の自己位置情報とに基づいて計算された前記対象無線装置と前記n次近傍無線装置との間の距離がnホップのホップ数からなる距離に近づくように前記対象無線装置の仮の自己位置を前記対象無線装置からのホップ数nに応じてそれぞれ修正するための1次修正ベクトルVi{1}(t)、2次修正ベクトルVi{2}(t)、・・・及びn次修正ベクトルVi{n}(t)からなるn個の修正ベクトルVi{1}(t)~Vi{n}(t)を、1次修正ベクトルVi{1}(t)とn次修正ベクトルとVi{n}(t)からなる第1番目の修正ベクトル(Vi{1}(t)+Vi{n}(t))、1次修正ベクトルVi{1}(t)とn-1次修正ベクトルVi{n-1}(t)とからなる第2番目の修正ベクトル(Vi{1}(t)+Vi{n-1}(t))、・・・、1次修正ベクトルVi{1}(t)と2次修正ベクトルVi{2}(t)とからなる第n-1番目の修正ベクトル(Vi{1}(t)+Vi{2}(t))の順に適用して前記対象無線装置の仮の自己位置を推定する処理である。

【0238】
また、図10に示すフローチャートにおいて、ステップS10の後にステップS5が実行される場合、推定された位置を用いて算出された無線装置間の演算距離が用いられるので、位置推定処理は、前記対象無線装置の仮の自己位置情報と前記対象無線装置からnホップの位置に存在するn次近傍無線装置の仮の自己位置情報とに基づいて計算された前記対象無線装置と前記n次近傍無線装置との間の距離が推定位置を用いて算出された前記対象無線装置と前記n次近傍無線装置との間の演算距離に近づくように前記対象無線装置の仮の自己位置を前記対象無線装置からのホップ数nに応じてそれぞれ修正するための1次修正ベクトルVi{1}(t)、2次修正ベクトルVi{2}(t)、・・・及びn次修正ベクトルVi{n}(t)からなるn個の修正ベクトルVi{1}(t)~Vi{n}(t)を、1次修正ベクトルVi{1}(t)とn次修正ベクトルとVi{n}(t)からなる第1番目の修正ベクトル(Vi{1}(t)+Vi{n}(t))、1次修正ベクトルVi{1}(t)とn-1次修正ベクトルVi{n-1}(t)とからなる第2番目の修正ベクトル(Vi{1}(t)+Vi{n-1}(t))、・・・、1次修正ベクトルVi{1}(t)と2次修正ベクトルVi{2}(t)とからなる第n-1番目の修正ベクトル(Vi{1}(t)+Vi{2}(t))の順に適用して前記対象無線装置の仮の自己位置を推定する処理である。

【0239】
また、領域判定処理は、次のように定義される。領域判定処理は、対象無線装置の推定された位置と対象無線装置の1次近傍無線装置の推定された位置との間の線分の垂直二等分線を基準として対象無線装置の2次近傍無線装置の推定された位置が対象無線装置および対象無線装置の1次近傍無線装置のいずれに近いかを判定し、当該判定に引き続いて、対象無線装置と対象無線装置の2次近傍無線装置との共通の1次近傍無線装置の推定された位置と対象無線装置の推定された位置との間の線分の垂直二等分線を基準として対象無線装置の2次近傍無線装置の推定された位置が対象無線装置および共通の1次近傍無線装置のいずれに近いかを共通の1次近傍無線装置を複数回変えて判定する処理である。

【0240】
更に、距離矛盾判定処理は、次のように定義される。距離矛盾判定処理は、対象無線装置の複数の1次近傍無線装置と複数の2次近傍無線装置とを用いて、対象無線装置の推定された位置が対象無線装置の1次近傍無線装置よりも対象無線装置の2次近傍無線装置に近いと判定されたとき、トポロジー矛盾があると判定する処理である。

【0241】
図4に示す位置推定装置9の取得手段92、トポロジー生成手段93、位置更新手段94、位置情報生成手段95、変換手段96、判定手段97、演算手段98および仮想トポロジー生成手段99は、ソフトウェアによって実現されてもよい。

【0242】
この場合、位置推定装置9は、CPU(Central Processing Unit)、ROM(Read Only Memory)およびRAM(Random Access Memory)を備える。そして、ROMは、図10および図11に示すフローチャートからなるプログラムPROGを記憶する。

【0243】
CPUは、プログラムPROGをROMから読み出して実行し、上述した方法によってm個の無線装置の位置を推定する。そして、CPUは、ステップS10の後にステップS5を実行する場合、既に推定された位置を用いて対象無線装置とn次近傍無線装置との間の距離を演算し、その演算した演算距離をRAMに記憶しておき、対象無線装置の仮の自己位置とn次近傍無線装置の仮の自己位置とを用いて算出された距離が対象無線装置とn次近傍無線装置との間の演算距離に近づくように対象無線装置の仮の自己位置を更新する。

【0244】
従って、プログラムPROGは、m個の無線装置の位置の推定をコンピュータ(CPU)に実行させるためのプログラムである。

【0245】
この発明の実施の形態においては、プログラムPROGは、CDおよびDVD等の記録媒体に記憶されていてもよい。そして、無線装置の位置を推定しようとするユーザは、その記録媒体をコンピュータにセットし、記録媒体からプログラムPROGを読み出して実行する。

【0246】
従って、プログラムPROGを記録した記録媒体は、コンピュータが読み取り可能な記録媒体である。

【0247】
上記においては、位置推定装置9は、クラウド上に配置されると説明したが、この発明の実施の形態においては、これに限らず、位置推定装置9は、シンク8に設置されてもよい。

【0248】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した実施の形態の説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【0249】
この発明は、位置推定装置、位置推定をコンピュータに実行させるためのプログラムおよびそのプログラムを記録したコンピュータ読み取り可能な記録媒体に適用される。
【符号の説明】
【0250】
1~7 センサーノード、8 シンク、9 位置推定装置、10 無線ネットワーク、11,81 アンテナ、12,82 送受信部、13,83 制御部、91 受信部、92 取得手段、93 トポロジー生成手段、94 位置更新手段94、95 位置情報生成手段、96 変換手段、97 判定手段、98 演算手段、99 仮想トポロジー生成手段。
Drawing
(In Japanese)【図1】
0
(In Japanese)【図2】
1
(In Japanese)【図3】
2
(In Japanese)【図4】
3
(In Japanese)【図5】
4
(In Japanese)【図6】
5
(In Japanese)【図7】
6
(In Japanese)【図8】
7
(In Japanese)【図9】
8
(In Japanese)【図10】
9
(In Japanese)【図11】
10
(In Japanese)【図12】
11
(In Japanese)【図13】
12
(In Japanese)【図14】
13
(In Japanese)【図15】
14
(In Japanese)【図16】
15
(In Japanese)【図17】
16
(In Japanese)【図18】
17
(In Japanese)【図19】
18
(In Japanese)【図20】
19
(In Japanese)【図21】
20
(In Japanese)【図22】
21
(In Japanese)【図23】
22
(In Japanese)【図24】
23
(In Japanese)【図25】
24
(In Japanese)【図26】
25