JP2007187652A - 位置決め技法 - Google Patents

Abstract

【課題】無線通信環境下で目標物体(TO)の位置決めを行うための技法。計算負担を小さくする。
【解決手段】データモデルが複数のサンプル点(S1〜S9)をモデル化する。各サンプル点は、１つの位置と該サンプル点における期待信号値の集合とから成る。適合性インジケータ(121A〜123B;131A〜133B)の集合が、適合サンプル点の１つ以上の集合(R1〜R3)を表示し、該１つ以上の集合が前記データモデルのサンプル点(S1〜S9)の部分集合である。信号値(102)が、前記目標物体の位置において観測される。前記信号値の観測値と適合性インジケータの前記集合とにもとづいて、適合サンプル点の最新集合(R)を決定し、該最新集合を前記信号値の観測値とともに使用して、前記目標物体の位置を評価する。計算の負担が減少する。なぜならば、適合サンプル点の最新集合(R)に含まれないサンプル点(S1〜S5;S7)を、計算から除外することができるからである。
【選択図】図１Ａ

Description

本発明は、包括的に言えば、位置決め技法に関する。この技法においては、目標物体の位置が、ある環境下たとえば無線通信ネットワーク下での１つ以上の物理量の観測値たとえばRF信号パラメータ値にもとづいて、評価される。目標物体は、１つ以上の物理量を観測しうる電子装置である。これは、汎用コンピュータその他の通信装置とすることができ、あるいは、俗に“タグ(tag)”と呼ばれる専用の位置決め装置とすることができる。このような位置決め技法は、たとえば、米国特許第6 393 294号および国際公開(publication)WO2004/102936号に記載されている。

先行技術に共通の特徴は、複数の位置での期待信号パラメータ値にもとづくデータベースである。これらの複数の位置は、前記国際公開明細書でも、本明細書と同様にサンプル点と呼ばれている。前記データベースは、複数のサンプル点のそれぞれに対して、該サンプル点で検出されうる各無線送信機(基地局またはアクセス点とも呼ばれる)に対する期待RF信号パラメータ値を含む。期待信号パラメータ値は、実際の測定、伝搬シミュレーション、補間、またはこれらの技法の任意の組合せによって得ることができる。信号パラメータは、非限定例として、たとえばRF信号強度、位相、ビット誤り率(bit error rate/ratio)、その他とすることができる。先行技術の位置決め技法の普通の動作原理は、目標物体が無線通信環境下でRF信号パラメータ観測値を生成し、目標物体の位置がRF信号パラメータ観測値と期待RF信号パラメータ値のデータベースとにもとづいて評価される、というものである。

先行技術の技法に伴う問題は、目標物体の位置決めのために大きな計算負担が必要になるということである。

本発明の目的は、前記欠点を小さくするための１つの方法と該方法を実施するための装置とを提供することである。本発明のこの目的は、独立クレームに述べることを特徴とする方法と装置によって実現される。本発明の好ましい実施形態は、従属クレームに述べられる。

本発明の１つの側面は、無線通信環境下で目標物体の位置決めを行うための方法である。この方法は、下記のステップまたは作業から成る。
a)複数のサンプル点に関してデータモデルを維持し、このとき各サンプル点が、サンプル位置と該サンプル点における１つ以上の物理量の期待値の集合とから成り、
b)適合サンプル点の１つ以上の集合を表示するための適合性インジケータの集合を維持し、ここで、適合サンプル点の前記１つ以上の集合が前記データモデルのサンプル点の部分集合であり、
c)前記目標物体の位置における少なくとも１つの物理量の観測値を得て、
d)前記目標物体の位置における前記観測値と適合性インジケータの前記集合とにもとづいて、適合サンプル点の最新集合を決定し、
e)前記目標物体の位置における前記観測値と適合サンプル点の前記最新集合とにもとづいて、前記目標物体の位置を評価する。

この技法の利点は、適合サンプル点の前記最新集合に含まれないサンプル点を計算から除外できるということであり、したがって計算の負担とバッテリーの消耗とを小さくできる。あるいは、本発明の技法によって節約できたリソースを使用して、さらなる計算によるより正確な、および/またはより確実な位置評価を得ることができる。

ステップa)およびc)は、前記の先行技術文献に述べられているように実施することができる。当該サンプル点での物理量の期待値は、スカラー値、確率分布(たとえば、正規分布)、ヒストグラム構成、その他とすることができる。ステップb)は、データモデルのサンプル点の部分集合である適合サンプル点の集合を示す適合性インジケータの集合を決定することから成る。このステップについては、以下でさらに詳しく述べる。ステップd)においては、目標物体の位置における観測値と適合性インジケータの集合とを使用して、適合サンプル点の最新集合を決定する。ステップe)においては、目標物体の位置が、目標物体の位置における観測値と適合サンプル点の最新集合とにもとづいて評価される。サンプル点に対応する位置は、点、円、領域、経路の部分、名前のついた場所(たとえば、“123号室”)、その他とすることができる。

本発明の他の側面は、前記方法を実施するための、コンパクトな、もしくは分散した位置決め装置、またはコンピュータプログラム製品に関する。

１つの実施形態においては、適合サンプル点の最新集合を決定するステップが、物理量の期待値の集合が所定の適合条件を満たす目標物体の位置における観測値全体を含むサンプル点を選択することを含む。

もう１つの実施形態においては、得られる適合サンプル点の集合が所定の最小サイズよりも小さい場合、所定の適合条件を緩和する。そのような状態は、異常を示している可能性があるので、警報を発する必要があり、この異常が持続的である場合には特にそうである。実施形態によっては、適合条件をシステム負荷に応じて調節する。システム負荷が大きいほど、適合条件は厳しく、また逆も同様である。

さらにもう一つの実施形態には、無線通信環境の配置をモデル化する配置グラフ(topology graph)を生成させることが含まれる。ここで、この配置グラフは、節点の集合と弧の集合とを示し、各節点が許容位置を示し、また各弧が二つの節点間の許容目標物体移動を示すようになっている。配置グラフを使用して、目標物体の位置が評価される。たとえば、配置グラフは、目標物体の移動履歴を記録し、目標物体の該移動履歴にもとづいて選択サンプル点の一部を除外するために使用することができる。

本発明の１つの非限定実施形態においては、目標物体は、単に、無線ネットワーク内で信号特性値を観測する装置である。別の適用においては、目標物体を、実際の観測を行う１つ以上の検出装置とは別のものとして扱うやり方が有利でありうる。たとえば、この検出装置は、無線受信機内で信号強度測定を行う電子回路とすることができ、目標物体はこの検出装置と同じ位置の人間または物品(piece)または装置である。また、本発明は信号強度測定のみには限定されない。逆に、本発明の位置決め技法は、下記のようないろいろな種類の位置依存物理量と関連させて使用することができる。
-放射に関して測定される信号特性値、たとえば信号強度、SN比、ビット誤り率、タイミングの進み(timing advance)、その他。そのような信号特性値は、使用する場合、好ましくは、いくつかの周波数帯、チャンネル、セル、基地局、その他の各々に関して、個別に決定される。
-大気の物理量、たとえば大気圧、温度、湿度、その他。
-音響物理量、たとえば雑音レベル、好ましくはいくつかの周波数帯の各々に関して個別に決定されたもの。
-光学物理量、たとえば光強度、色、スペクトル、その他。
-静止もしくは運動している像の認識された形状、または認識された音。

目標物体(または、該目標物体に取りつけられた検出装置)の観測値は、必ずしも生の測定データである必要はなく、該測定データから導かれる任意の値で良い。たとえば、観測値は、数値計算処理たとえば平滑化によって、測定データから導くことができる。さらに、本発明のいくつかの実施形態においては、検出装置の観測値を補正するために装置モデルを使用する。このやり方は、検出装置が正確な測定のために特別に設計されたものでない場合に、特に有効に使用できる。

以下、本発明を、添付の図面を参照しつつ、特定実施形態によって、さらに詳しく説明する。

図１Ａは、１つの目標物体、および３つのアクセス点を有する無線ネットワークの部分、およびいくつかのサンプル点を示す。A1〜A3の番号を付けた三角形は、３つのアクセス点を示す。S1〜S9の番号を付けた+記号は、無線ネットワーク内の信号パラメータ値たとえば信号強度をモデル化するデータモデルの９つのサンプル点を示す。参照記号TOは、目標物体の位置を示す。文脈により、参照記号TOは目標物体そのものまたはその位置を示すものとする。目標物体の位置は、位置決めが開始されたときには未知であり、位置決めが完了したときには単なる１つの評価値である。参照番号102は、目標物体TOによって得られたRF信号パラメータ観測値の集合(ベクトル)を示す。この例の場合、アクセス点A1、A2、およびA3における信号パラメータたとえば信号強度の観測値は、それぞれ2、8、および9である。目標物体TOは位置決めエンジンPEによって位置決めされる。PEは、実施形態によっては、目標物体そのものに備えることができる。しかし、本発明のリソース節約という特徴は、多数の目標物体を一つの共通の位置決めエンジンで位置決めする場合に、もっとも十分に発揮される。代表的な実施形態においては、この位置決めエンジンは、データ処理装置たとえばサーバーまたは一組のサーバーであり、位置決め環境のデータモデル、目標物体位置における信号パラメータ観測値を受信する手段、および本発明による方法を実施するための手段を備えている。

図１Ａには、説明のために、３つのアクセス点のそれぞれに関して、信号パラメータ値が等しい３つの線も示してある。これらの等値線は、アクセス点の信号値が10(最内側の線)、5(中間の線)、および1(最外側の線)である位置を示す。これらの線は、本発明のより良い理解のために示してあるだけであり、計算のために使用されるものではない。図１Ａ〜１Ｃは、信号パラメータを、人である読み手に理解しやすく説明するために、簡単な0〜12のスカラー値として示す。現実のケースでは、信号パラメータ値は、たとえばdBm単位で示された信号強度とすることができる。

図１Ｂおよび１Ｃは、適合サンプル点の集合を示すための適合インジケータの典型的な集合をまとめて示す。

図１Ｂは、１つのサンプル点すなわちS1と図１Ａに示す３つのアクセス点A1〜A3とにおいて可能な信号特性値の系列を示す。ここに示す実施形態の場合、信号パラメータ値は離散値として処理される。当然のことながら、任意のディジタル測定システムにより、“離散”値が生成されるが、ここで使用する“離散”という言葉は、可能な値の系列を、ディジタル数の仮想連続体ではなく割合に少数の値域として処理するということを意味する。注意すべきことは、“離散”の厳密な定義が本質的だというわけではないということである。なぜならば、本発明は、可能な信号特性値が連続(非離散)であると考えられる技法に対しても適用できるからである。

図１Ｂは、データモデルが確率モデルである実施形態に関するものである。確率モデルは、測定可能な物理量の確率分布を示す。この物理量はここでは信号パラメータ値である。参照番号121Aは、アクセス点A1からの、サンプル点S1での信号パラメータ値の確率分布を示す。代表的な、しかし非限定的な実施形態においては、これは、A1からの、サンプル点(位置)S1での信号の信号強度の確率分布である。この量をD(A1/S1)で示す。この信号強度分布は、実際の測定、コンピュータシミュレーション、またはそのような技法の任意の組合せによって決定することができる。

水平棒121Bは、A1とS1との組合せに関して可能な信号パラメータ値の系列を示す。信号パラメータ値は、統計的に有意の限界値だけゼロからずれている確率を有する場合には、可能なものであるとみなされる。統計的有意性にかかわる問題には、計算最適化と正確性/信頼性との妥協点を探ることが含まれる。必要な限界値が大きい(信号値は、“非常に”高い確率を有するときにのみ、受け入れられる)場合には、少数のサンプル点のみが適合すると考えられ、大きく計算リソースが節約される。一方、位置決めに影響しうるサンプル点を無視してしまう危険がある。

参照番号122Aと123Aとは、それぞれ、他のアクセス点A2とA3に関する対応する分布を示す。参照番号122Bと123Bとは、可能な信号パラメータ値の対応する値を示す。

図１Ｂは、簡明なように、１つのサンプル点(S1)と３つのアクセス点(A1〜A3)に関してだけ、可能な信号パラメータ値の系列を示す。現実のシステムにおいては、可能な信号パラメータ値の系列は、データモデル(データベース)により、各サンプル点に関して個別に決定する必要がある。

図１Ｃは、適合サンプル点の集合を得るプロセスを示す。参照番号131Aは、図１Ａに示す、アクセス点A1と９つのサンプル点S1〜S9のそれぞれとに関して、可能な信号パラメータ値の系列の集合を示す。参照番号132Aと133Aとは、他の２つのアクセス点A2とA3に関して、同様の系列の集合を示す。データ構成131A〜133Aのそれぞれにおいて、一番上のサンプル点S1に関する系列は、すでに図１Ｂに示したものと同じものであり、残りのサンプル点S2〜S9に関する系列も同様に決定される。たとえば、データ構成131Aは、サンプル点S3から見た、アクセス点A1のRF信号パラメータ値が1〜5の範囲(近似値)にある、ということを示している。

参照番号131B〜133Bは、それぞれ３つのアクセス点の１つに対応する３つの数値ウィンドウを示す。各数値ウィンドウ131B〜133Bは、対応するアクセス点の信号パラメータ値のところに配置されている。図１Ａに関して前述したように、目標物体は、それぞれ、アクセス点A1、A2、およびA3から、信号パラメータ値2、8、および9を観測している。したがって、数値ウィンドウ131B〜133Bが、データ構成131A〜133Aの位置2、8、および9に配置される。この説明においては、まず、数値ウィンドウの幅を1であると仮定することができる。この幅に関しては以下でさらに述べる。

ここでの意図は、データ構成131A〜133Aと数値ウィンドウ131B〜133Bを使用して、適合サンプル点の集合を決定するというものである。目標物体の位置で観測されたアクセス点A1の信号パラメータ値は、2である(v_A1=2)。サンプル点S3、S6、S8、およびS9に関する可能な信号パラメータ値の範囲が、数値ウィンドウ131Bに重なっている。言い換えると、観測値v_A1=2の場合、サンプル点S3、S6、S8、およびS9が適合サンプル点の候補となる。サンプル点Aiによって与えられる、候補サンプル点の集合をRiで示すことにする。位置決めエンジンは、他の２つのアクセス点に関しても同じ手順を繰り返すことにより、下記の適合サンプル点の集合を決定する。
R1={S3、S6、S8、S9}
R2={S2、S3、S5、S6、S8、S9}
R3={S5、S6、S7、S8、S9}

位置決めエンジンは、各アクセス点と信号値に関して、あらかじめ適合サンプル点の前記集合を決定し、この集合を記憶して、いくつかの後続位置決めサイクルで使用する。この記憶された集合は、位置決め環境が再検量される(測定および/またはシミュレーションによって)まで、使用することができる。

次に、位置決めエンジンは、前記３つの集合R1、R2、およびR3の交わりを決定して、３つの観測値{v_A1=2,v_A2=8,v_A3=9}のそれぞれが与えられたときの、適合アクセス点の集合を決定する。得られる集合は下記のRで示される。
R=R1∩R2∩R3
={S3、S6、S8、S9}∩{S2、S3、S5、S6、S8、S9}∩{S5、S6、S7、S8、S9}
={S3、S8、S9}

このように、この例の場合には、適合サンプル点の集合が9から3に減少する。もっと多数のサンプル点を含む現実の状況においては、この減少比は3よりもかなり大きいと考えられる。単一の位置決めエンジンによって位置決めできる目標物体の数は、大体同じ比率で増大する。

上記説明においては、数値ウィンドウ131B〜133Bの幅は一定であると仮定した。しかし、割合に狭い幅で始めるのが好ましく、得られる適合サンプル点の集合が空であるかまたは小さすぎて信頼できる結果が得られない場合には、緩和した条件たとえば大きな数値ウィンドウにより別の集合を決定する。当然のことであるが、この物理的数値ウィンドウは説明のためだけに示したものであり、データプロセッサーは可視化せずに数値をチェックすることができる。

この例の場合、数学的に簡単な３つの集合R1、R2、およびR3の交わりを使用して、３つの観測値すべてに適合するアクセス点の単一集合を決定する。これは、観測値の組合せに適合させるためには、サンプル点が各観測値に適合しなければならない、ということを意味する。しかし、現実の測定値がこれほど簡単であることはめったになく、あとで図４に関連させて、サンプル点が１つ以上の観測値に適合すると思われない場合でも、適合サンプル点であると考えるアルゴリズムについて述べる。

本発明のいくつかの実施形態においては、経験的に適当であると知られている数値ウィンドウが適合サンプル点の空集合を生成する場合には、警報が発せられる。そのような状況は、目標物体そのものまたはアクセス点(基地局送信機)の１つにおける装置故障の兆候でありうる。あるいは、位置決め環境の伝搬特性が一時的妨害または壁構造物の永久的変化によって変化したのかもしれない。適合サンプル点が空集合となる原因が何であろうと、その原因を探究すべきである。

図２Ａおよび２Ｂは、信号パラメータ値を連続値として処理し、対称単一ピーク確率分布としてモデル化するケースを示す。複数ピークおよび非対称の確率分布への一般化については、図５によって説明する。下記の表記を使用する。
A={a₁,a₂,…,a_n}=アクセス点の集合
S={s₁,s₂,…,s_m}=サンプル点の集合

={ν₁,ν₂,…,ν_n}=観測された信号パラメータ値の集合(ベクトル)
ν_i=a_iに対する信号値
NA=使用できない数値(受信可能範囲外、走査の失敗、…)
P(V|s_i,a_j)= s_iにおけるa_jの信号パラメータ値の確率分布
ε(イプシロン)=検索が適合サンプル点を無視する危険度を指定するパラメータ;たとえば

図２Ａにおいて、参照番号202は、アクセス点から得られた信号パラメータ値を示すx軸を示す。y軸204は、サンプル点s_iにおけるアクセス点a_jの信号パラメータの確率分布P(V|s_i,a_j)を示す。この確率分布を参照番号206で示す。この技法の目的は、１つ以上の信号値範囲を決定して、該範囲外の値を観測する確率が所定の確率しきい値εを超えないようにすることである。図２Ａの確率分布は対称で単一ピークであるから、必要基準を満たす信号パラメータ値v_minおよびv_maxによって限られる信号値範囲を決定することができる。参照番号210および212は、それぞれ信号パラメータ値v_minおよびv_maxを示し、ここで、v_minとv_maxとの間の範囲の外にある観測信号パラメータ値の確率がεであり、下記の式が適用されるようにする。
P(V<v_min|s_i,a_j)=ε/2
P(V>v_max|s_i,a_j)=ε/2

言い換えると、最小および最大信号パラメータ値v_minおよびv_maxは、絶対的な最小値および最大値ではなく、確率P(V|s_i,a_j)の大部分を含む範囲の下端と上端を限る値である。この範囲をハッチングで示す。

図２Ｂは、図２Ａの確率分布206から導かれる累積確率分布226を示す。図２Ａにおいて、それぞれ参照番号210および212で示される最小および最大信号パラメータ値v_minおよびv_maxは、v_minとv_maxとの間にある信号値の累積確率が1−εとなるように、ハッチングされた範囲228を限っている。

上記の確率の考察から、あるサンプル点が観測ベクトル

を与える目標物体の位置決めに適合するかどうかを決定するための適合条件を導くことができる。

前述のように、ν_i=アクセス点

に対する信号値、である。サンプル点s_jは、v_iが、サンプル点s_jに関してアクセス点a_iにおいて決定される信号値範囲の１つの内部にある場合、適合すると考えられる。サンプル点s_jに対応する信号値分布が対称で単一ピークであって、v_minとv_maxがそれぞれ前述のように決定された信号値範囲の下限と上限である場合、適合条件は下記のように書かれる。
v_min≦v_i≦v_max

R_i[v]は、アクセス点a_iの観測信号パラメータ値がvである場合に得られる適合サンプル点の集合を示す。

図３は、適合サンプル点の集合を初期化するための初期化アルゴリズム300を示す。行302は、Begin…Endループを定義し、該ループはサンプル点の集合Aの各アクセス点a_jに関して実行される。行304は、信号パラメータ値vの各可能値に関して適合サンプル点の集合R_j[v]を空にする。行306は、Begin…Endループを定義し、該ループはサンプル点の集合Sの各サンプル点s_jに関して実行される。行308と310は、最小および最大信号パラメータ値それぞれv_minおよびv_maxを、v_minよりも小さいかまたはv_maxよりも大きな観測値の確率がεに等しくなるように、算出する。行314は、そのときのサンプル点s_iを信号パラメータ値vに関する適合サンプル点の集合R_j[v]に加える。

図４は、適合サンプル点、すなわち観測値

に対応する位置を決定するのに適合するサンプル点、の集合R⊆Sを見出すためのアルゴリズム400を示す。行402は、空集合Cを生成させ、これには、候補サンプル点の集合が収容されることになる。行404は、可聴(検出可能)アクセス点の数に関する変数F_maxを初期化する。行406は、Forループを開始させ、このループは、観測ベクトル

の各信号パラメータ値v_iが“NA”(使用できない)でない場合に、該信号パラメータ値v_iに関して実行される。行408においては、可聴アクセス点の数に関する変数F_maxが1だけ増分される。行410においては、Forループを開始させ、このループは、図１Ａ〜１Ｃに関して述べた範囲の考察にもとづいて、観測値R_i[v_i]に対して可能なサンプル点である各サンプル点s_jに関して実行される。

行412は、If…Then構文(construct)を開始させ、これのThen部分は、サンプル点s_jが候補サンプル点の集合Cの要素でない場合に、実行される。行414では、サンプル点s_jが候補サンプル点の集合Cに加えられる。行416では、ヒットカウンター(hit counter)F[j]が初期化されて1になる。If…Then構文の残りの部分は、行418を含み、この行では、ヒットカウンターF[j]が1だけ増分される。実施形態によっては、ヒットカウンターF[j]に加えられる値は、1に固定されてはおらず、観測される値の尤度に応じて変えられる。

行420は、アルゴリズム400の第二の部分を開始させる。行420では、適合サンプル点の集合が初期化されて、空集合となる。行422は、Forループを開始させ、該ループは、候補サンプル点の集合Cに含まれる各サンプル点s_jに関して計算される。行424は、If…Then構文であり、該構文は、可聴アクセス点の数F_maxからヒットカウンターF[j]を引いたものがある許容限界K以下である場合に、実行される。行426では、サンプル点s_jが集合Rに加えられる。最後に、行428において、得られる適合サンプル点の集合Rが呼び出しアプリケーションに戻される。

許容限界Kの意味は以下のようである。K=0のとき、アルゴリズム400は、図１Ａ〜１Ｃ特に１Ｃに示す手順と同様の演算を行う。すなわち、サンプル点は、該サンプル点が観測ベクトル

内のすべての信号パラメータ値に対して可能なサンプル点であると考えられる場合にのみ、適合するということである。しかし、K=0という値が厳しすぎる条件であって、適合アクセス点の空集合または非常に小さな集合が生成されるということが起こりうる。K=n;n=1,2,…という値が意味するのは、当該サンプル点は、図1Cに示されるn個の集合R1…R3に含まれない場合でも、適合するとみなされるということである。

図５は、図２Ａ〜４に示す単一ピークの例の複数ピークへの展開を示す。参照番号502は、X-Y座標系を示し、この座標系において、しきい値レベル504が曲線506と交差する。図５は、曲線506がしきい値レベル504よりも上にある二つの範囲を示す。範囲A₁はx₁からx₂まで広がっており、範囲A₂はx₃からx₄まで広がっている。ここでの意図は、しきい値504を、参照番号508で示される条件が満たされるように設定する、というものである。言葉で言えば、条件508は、ピーク範囲A1、A2、…に関して計算した確率の積分P(V=x)が1−εに等しいということを意味する。

本発明のいくつかの実施形態においては、データモデルは確率モデルではない。たとえば、サンプル点には、測定可能な物理量の統計的要約、たとえば平均値、メディアン、最小値、または最大値のみを含ませることができる。また、サンプル点は、１つ以上の、測定されたままの観測値または観測値から導かれたいくつかの値を含むこともできる。もう１つの可能性は、サンプル点がコンピュータシミュレーションたとえば光線追跡法で得られた値を含むというものである。

本発明のいくつかの実施形態においては、適合条件を、サンプル点に対応する値までの隔たりを基準に定めることができる。たとえば、x_iがサンプル点s_jに対応するアクセス点a_iにおける信号値である場合、信号値範囲の下限と上限を、所定の限界zを用いて下記のように定めることができる。
v_min=x_i−z
v_max=x_i＋z
グラフおよび履歴にもとづく位置決め

位置決めの不確かさは、出願人の国際公開WO2004/008795号明細書に開示されているグラフにもとづく位置決め法とともに、本発明の適合性インジケータを使用することにより、さらに低下させることができる。同明細書の教示内容を参照されたい。前記国際公開明細書は、隠れマルコフモデルと組み合わせたグラフにもとづく位置決め法を開示しているが、本発明は隠れマルコフモデルに限定されるものではない。グラフにもとづく位置決めは次のようにまとめることができる。配置グラフが、無線通信環境の配置をモデル化する。この配置グラフは、節点の集合を示し、各節点が位置決め環境内で許容される位置を示す。配置グラフは、また弧の集合をも示し、各弧が２つの節点の間で許容される目標物体の移動を示す。この配置グラフを使用して、データモデルと観測値の系列とにもとづいて目標物体の位置が評価される。たとえば、位置決め環境の配置をモデル化する配置グラフを使用して、不可能な位置および/または位置間の不可能な移動を排除することができる。

図６は、グラフにもとづく位置決め法を、本発明の適合性インジケータと組み合わせて使用するやり方を示す。図６に示す例では、配置グラフTGが位置決め環境内での許容される位置と移動とをモデル化する。この簡単な例に示す配置グラフTGは、20個の節点を有し、これらを参照記号N1〜N20で示す。この例では、節点N1〜N20はデータモデルのサンプル点でもある。参照記号T1〜T4は、４つの異なる時刻における目標物体の位置を示す。参照記号S11〜S14は、適合サンプル点の４つの異なる集合を示し、各集合は異なる時刻T1〜T4に対応する。これらの適合サンプル点の集合は、本明細書で前述した適合性インジケータによって決定することができる。

図式610は、時刻T1〜T4において可能な目標物体位置の決定を示す。時刻T1においては、適合点の集合S11は、サンプル点(節点)N3〜N6から成り、これらを４つの×記号で示す。時刻T2においては、適合サンプル点の集合S12は、節点N6、N7、N14、およびN15から成る。時刻T3においては、適合サンプル点の集合S13は、節点N6〜N9から成る。最後に、時刻T4においては、適合サンプル点の集合S14は、節点N1、N9〜N13、およびN18から成る。

この例の場合、目標物体は、一単位の時間内に、静止しているか、または一つの節点からそれに隣接する節点に移動できるが、一単位の時間内に二つ以上の節点間弧を飛び越えるのに十分な速さでは移動できない、と仮定している。時刻T1に使用できる情報にもとづいて、節点N3〜N6の各々が可能な目標物体位置となる。しかし、これらの位置が同程度の可能性を有するというわけではない。しかし、時刻T2においては、一単位の時間内にたかだか１つの節点間ジャンプしかできないという規則から、時刻T1における節点N3およびN4が除外される。目標物体は、これらの節点のどちらからも、時刻T2において可能な節点に移動できなかったはずだからである。同じ規則により、時刻T2における節点N14およびN15も除外される。これらの節点はT1において可能な節点の集合からは到達できないからである。

時刻T3においては、適合サンプル点の集合S13は節点N6〜N9から成る。しかし、一単位の時間内にたかだか１つの節点間ジャンプしかできないという規則から、節点N9が除外される。N9は、時刻T2に可能な節点から２つ以上の節点間ジャンプだけ離れているからである。最後に、時刻T4には、適合サンプル点の集合S14は、節点N1、N10〜N13、およびN18をも含んでいるが、目標物体の位置を節点N9であると決定できる。というのは、N9は、T3において可能な節点から一回の節点間ジャンプで到達できるただ一つの節点であるからである。

これからわかるように、時刻T1〜T4における目標物体の移動履歴を利用して、目標物体の現在位置に関する不確かさを減少させるばかりでなく、目標物体の以前の位置に関する不確かさを低下(または、消滅)させることができる。前述のように、時刻T1において利用できる情報にもとづけば、目標物体は節点N3〜N6のいずれにも存在する可能性がある。しかし、位置決めエンジンが全移動履歴(この例の場合、４つのステップ)を自由に利用できるならば、位置決めエンジンは、図式610に４つの円で示すように、目標物体の経路をN6-N7-N8-N9と決定できる。

ここで図６を参照して説明した、前記国際出願明細書により詳細に説明してある、グラフにもとづく位置決めは、位置決めの不確かさをさらに減少させるために使用することができる。不可能な移動を必要とする節点は除外することができるからである。グラフにもとづく位置決めは、また、本発明の主要目的である計算負担の減少のためにも使用できる。不可能な移動を必要とするサンプル点(節点)は、計算から除外することができるからである。この例の場合、時刻T4における適合サンプル点の集合S14は、７つの節点(N1、N9〜N13、およびN18)から成るが、目標物体の全移動履歴を考慮すると、ただ１つの節点すなわちN9のみが可能な節点となる。

前記例は、形式的には、隠れマルコフモデルにもとづく方法によって述べることができる。L(s_i)が、集合s_iのサンプル点の隣接点の集合、すなわち集合s_iのサンプル点から１ステップで到達できるサンプル点の集合、を示すものとする。L(R)は適合サンプル点の隣接点の集合を示す。

以下では、HMM₁、HMM₂、…HMM_iは、隠れマルコフモデルの連続観測サイクルを示す。適合サンプル点の集合(R)は下記のようである。

図式610では、この特性を水平バーで示してある。破線の水平バーは、適合サンプル点の隣接点を示し、実線の水平バーは、不可能な移動を排除したあとの適合サンプル点の隣接点を示す。これからわかるように、本発明の方法により計算負担が減少する。というのは、HMM考察により、適合すると思われるサンプル点の集合R_HMM/1…iに属するサンプル点に関してのみ、観測確率を計算する必要があるだけだからである。

適合サンプル点の集合R_HMM/kが空集合または非常に空に近い集合である場合、それは、何か予期されなかったことが起こっているということであり、何か対策を講じてから、位置決めを再開すべきである。たとえば、観測信号が一時的に妨害されているとか、データモデルにデータが含まれないとか、目標物体に備えられた検出装置が誤動作しているとか、といったことが考えられる。問題が持続する場合には、警報を発すべきである。

図６に即して述べた例においては、配置グラフTGを、目標物体TOの位置が配置グラフTGに沿う節点の１つであると考えるように、使用している。代替実施形態においては、目標物体の位置を、必ずしも所定の節点N1〜N20の１つではなく、配置グラフTGに沿う任意の点であると解釈する。もう一つの実施形態では、目標物体の位置を、所定の限界以下たとえば通路の幅の半分以下だけ配置グラフTGから離れた任意の点であると解釈する。さらに、配置グラフTGは、長い通路をモデル化するのに適した弧と、広々した空間たとえば大きな部屋をモデル化するのに適した領域との組合せを含むことができる。
装置モデル

本発明のいくつかの実施形態においては、検出装置の観測値を補正するために装置モデルを使用する。この機能は、検出装置が正確な測定のために特別に設計されたものではない場合に、特に有効に使用できる。たとえば、無線通信端末は受信信号強度インジケータ(RSSI)を含むことができるが、測定される信号強度は非常に不正確でありうる。そのため、各装置モデルは、それぞれの検出装置の観測値を補正するために、適当な補正パラメータを含む。たとえば、補正パラメータは、一定のスケール変更(scaling)パラメータおよび/または線形化パラメータから成ることができる。それぞれの目標物体に複数の検出装置が備えられるか、または付随している場合には、それぞれの装置の観測値に別々の装置モデルを適用するのが有利である。

場合によっては、最適装置モデルに関する事前(a priori)情報を使用することができる。たとえば、検出装置を検量して、装置モデルを作ることができ、あるいは既存の装置モデルの１つを選択して、あとで使用するために当該検出装置に対応させることができる。

同様に、検出装置を、複数の装置モデルに対応させて、異なる装置モデルのそれぞれが検出装置の観測値を補正するために異なる補正パラメータを有するようにすることができる。一つの実施形態においては、それぞれの異なる装置モデルが異なる検量曲線となるようにすることができる。

目標物体(または、それに取りつけられた検出装置)が実験室条件下ではほぼ完全な測定を行うことができたとしても、その見かけの測定能力は、近くの物体に対する配置および/もしくは配向、または高さによって影響を受けうる。たとえば、問題の目標物体が、検出装置となる識別タグを装着した病院患者であることがある。この患者が床に倒れた場合には、検出装置の配向と高さとが変化する。あるいは、検出装置のアンテナが壊れた場合には、感度に影響がある。そのような状況は、実験から導かれた適当な補正を加える装置モデルを使用することによって当該検出装置の観測値がもっとも良く説明されるということに注意することにより、検出することができる。

本発明のいくつかの実施形態においては、検出装置に対する最適装置モデルに関する事前情報が使用できず、適合サンプル点法が最適装置モデルの選択に使用される。この方法は、信号値が大きく損なわれているか、または偏っている場合に、適合サンプル点の数が非常に小さくなるかまたはゼロにさえなる傾向がある、という発見にもとづく。一方、観測信号がサンプル点に対応するデータに良く対応する場合には、適合サンプル点の数が大きい。

したがって、ある装置モデルを適用することにより適合サンプル点の数が増大する場合には、その装置モデルは当該装置に固有の偏りの一部を取り去ることができる、と結論できる。最適選択装置モデルは、適合サンプル点の数を最大にするものである。装置モデル選択の正確さは、一連の観測値を解析することによりさらに高めることができる。たとえば、一連の観測値に対する適合サンプル点の平均数が最大になる装置モデルを選択することができるであろう。

装置モデルを作成し、使用するためのさらなる技法については、位置決め技法を開示する、本件とともに権利を有する(commonly-owned)特許出願WO2004/008796号に開示してある。該技法は、信号特性パラメータの、異なる目標物体での観測値の差異を補正する複数の装置モデルを決定し、これらの複数の装置モデルの中から、特定目標物体に対して特定装置モデルを選択することを含む。

最初の段落と本発明の開示実施形態のいくつかとで挙げた先行技術文献は確率技法に関するものであるが、本発明は非確率技法、たとえば最近接タイプの位置決めアルゴリズムにも同様に適用できる。当業者には容易にわかるように、ここでの発明的概念は、技術の進歩につれて、いろいろなやり方で具体化することができる。本発明とその実施形態とは、上で例として示した実施形態に限定されるものではなく、特許請求の範囲に示す範囲内で変更することができる。

１つの目標物体、および３つのアクセス点を有する無線ネットワークの部分、およびいくつかのサンプル点を示す。 １つのサンプル点と３つのアクセス点に関する可能な信号特性値の系列を示す。 適合サンプル点の集合を得るプロセスを示す。 信号パラメータ値が連続値として処理されるケースを示す。 信号パラメータ値が連続値として処理されるケースを示す。 適合サンプル点の集合を初期化するための初期化アルゴリズムを示す。 適合サンプル点の集合を見出すためのアルゴリズムを示す。 図２Ａ〜４に示す単一ピーク例の複数ピークへの展開を示す。 グラフにもとづく位置決め技法を本発明の適合インジケータとともに使用する例を示す。

符号の説明

102 RF信号パラメータ観測値の集合
121A アクセス点A1からのサンプル点S1での信号パラメータ値の確率分布
121B 121Aに対応する可能な信号パラメータ値の系列
122A A2に関する121Aと同様のもの
122B 122Aに対応する可能な信号パラメータ値の系列
123A A3に関する121Aと同様のもの
123B 123Aに対応する可能な信号パラメータ値の系列
131A A1とS1〜S9とに関して可能な信号パラメータ値の系列の集合
131B 数値ウィンドウ
132A A2に関する131Aと同様のもの
132B 数値ウィンドウ
133A A3に関する131Aと同様のもの
133B 数値ウィンドウ
202 アクセス点から得られた信号パラメータ値を示すx軸
204 信号パラメータ値の確率分布を示すy軸
206 確率分布
210 信号パラメータ値v_min
212 信号パラメータ値v_max
226 累積確率分布
228 ハッチングされた範囲
300 初期化アルゴリズム
302 行
304 行
306 行
308 行
310 行
314 行
400 アルゴリズム
402 行
404 行
406 行
408 行
410 行
412 行
414 行
416 行
418 行
420 行
422 行
424 行
426 行
428 行
502 X-Y座標系
504 しきい値レベル
506 曲線
508 確率に関する条件
610 図式
TO 目標物体の位置

Claims (9)

1. 無線通信環境下で目標物体(TO)の位置決めを行うための方法であって、
   複数のサンプル点(S1~S9)に関してデータモデルを維持し、このとき各サンプル点が、サンプル位置と該サンプル点における１つ以上の物理量の期待値の集合とから成り、
   適合サンプル点の１つ以上の集合(R1〜R3)を表示するための適合性インジケータ(121A〜123B;131A〜133B)の集合を維持し、ここで、適合サンプル点の前記１つ以上の集合が前記データモデルのサンプル点(S1〜S9)の部分集合であり、
   前記目標物体の位置における少なくとも１つの物理量の観測値(102)を得て、
   前記目標物体の位置における前記観測値と適合性インジケータの前記集合とにもとづいて、適合サンプル点の最新集合(R)を決定し、
   前記目標物体の位置における前記観測値と適合サンプル点の前記最新集合(R)とにもとづいて、前記目標物体の位置を評価する、
   ことから成り、
   適合サンプル点の前記最新集合に含まれないサンプル点(S1〜S5;S7)を前記評価ステップから除外できる、
   ことを特徴とする方法。
2. 適合サンプル点の最新集合(R)を決定するステップが、物理量の期待値の集合が所定の適合条件(228)を満たす目標物体の位置における観測値全体を含むサンプル点を選択することを含むことを特徴とする請求項１に記載の方法。
3. 得られる適合サンプル点の集合が所定の最小サイズよりも小さい場合、所定の適合条件(228)を緩和することをさらに含むことを特徴とする請求項２に記載の方法。
4. 得られる適合サンプル点の集合が所定の最小サイズよりも小さい場合、警報を発することをさらに含む請求項１から３の中のいずれか１つに記載の方法。
5. さらに、
   無線通信環境の配置をモデル化する配置グラフ(TG)を生成させ、ここで、該配置グラフが、節点(N1〜N20)の集合と弧の集合とを示し、各節点が無線環境下の許容位置を示し、また各弧が、二つの節点間の許容目標物体移動を示し、
   配置グラフ(TG)を使用して、目標物体の位置を評価する、
   ことをさらに含むことを特徴とする請求項２に記載の方法。
6. 目標物体の移動履歴(610)を記録し、目標物体の該移動履歴にもとづいて選択サンプル点の一部を除外するために、前記配置グラフを使用することをさらに含むことを特徴とする請求項５に記載の方法。
7. 各装置モデルが１つ以上の検出装置(SD)の観測値を補正することができる、いくつかの装置モデル(DM)の各々に関して、
   -前記装置モデルを使用して、少なくとも一つの検出装置(SD)の観測値を補正し、
   -このように補正された観測値を使用することによって、適合サンプル点の最新集合(R)を決定する、
   ステップをさらに含み、またさらに、
   適合サンプル点の数が最大になる装置モデルを選択する、
   ことをさらに含む、
   ことを特徴とする請求項１から６の中のいずれか１つに記載の方法。
8. １つ以上の物理量が少なくとも１つの信号値から成ることを特徴とする請求項１から７の中のいずれか１つに記載の方法。
9. 無線環境下で目標物体(TO)の位置決めを行う位置決めエンジン(PE)であって、
   複数のサンプル点(S1〜S9)に関するデータモデルであって、各サンプル点が、サンプル位置と該サンプル点における１つ以上の物理量の期待値の集合とから成るデータモデル、
   適合サンプル点の１つ以上の集合(R1〜R3)を表示するための適合性インジケータ(121A〜123B;131A〜133B)の集合であって、ここで、適合サンプル点の前記１つ以上の集合が前記データモデルのサンプル点(S1〜S9)の部分集合である集合、
   前記目標物体の位置において得られる少なくとも１つの物理量の観測値(102)を受信する手段、
   前記観測値と適合性インジケータの前記集合とにもとづいて、適合サンプル点の最新集合(R)を決定する手段、
   前記観測値と適合サンプル点の前記最新集合(R)とにもとづいて、前記目標物体の位置を評価する手段、
   から成ることを特徴とする位置決めエンジン。

Images