(57)【特許請求の範囲】
【請求項１】
移動体処理デバイスの計算位置を決定するコンピューター実装方法であって、
前記移動体処理デバイスの位置を決定する要求を受けるステップであって、該要求が観察されたビーコンを含む、ステップと、
少なくとも以前に観察されたビーコンを含む現場フィンガープリント・データーに基づいて、利用可能な方法から位置計算方法を選択するステップであって、前記現場フィンガープリント・データーと前記要求に含まれた前記観察されたビーコンとから、現場検出及びフロア検出が成功した場合、第１方法を選択し、前記現場検出または前記フロア検出が不成功の場合、前記計算位置を推論する第２方法を選択し、現場が、閾値数の検出されかつ現場識別されたビーコンに基づいて決定される、ステップと、
選択した前記方法と、データー・モデルとを使用して、前記移動体処理デバイスの前記計算位置を計算するステップであって、前記データー・モデルが、ビーコンの特性および該ビーコンに関連する位置データーを含み、前記位置データーが現場識別子およびフロア識別子を含む、ステップと、
を含む、コンピューター実装方法。
【請求項２】
請求項１記載のコンピューター実装方法において、選択するステップが、
前記観察されたビーコンから現場を決定し、続いて前記観察されたビーコンからフロアを決定するステップを含む、コンピューター実装方法。
【請求項３】
ワイヤレス通信チャネルを含む移動体処理デバイスであって、
プロセッサーと、
コードを含むメモリーと、
を含み、前記コードが前記プロセッサーに、前記移動体処理デバイスの計算位置を決定する方法を実行させ、該方法が、
前記移動体処理デバイスの位置を決定する要求を受けるステップであって、該要求が観察されたビーコンを含む、ステップと、
少なくとも以前に観察されたビーコンを含む現場フィンガープリント・データーに基づいて、利用可能な方法から位置計算方法を選択するステップであって、前記現場フィンガープリント・データーと前記要求に含まれた前記観察されたビーコンとから、現場検出及びフロア検出が成功した場合、第１方法を選択し、前記現場検出または前記フロア検出が不成功の場合、前記計算位置を推論する第２方法を選択し、現場が、閾値数の検出されかつ現場識別されたビーコンに基づいて決定される、ステップと、
選択された前記方法と、データー・モデルとを使用して、前記移動体処理デバイスの前記計算位置を計算するステップであって、前記データー・モデルが、ビーコンの特性および該ビーコンに関連する位置データーを含み、前記位置データーが現場識別子およびフロア識別子を含む、ステップと、
を含む、移動体処理デバイス。
【請求項４】
請求項３記載の移動体処理デバイスにおいて、前記第１方法がＥＺアルゴリズム方法であり、前記第２方法がカルマン・アルゴリズムであり、前記第１および第２方法が、フロア・データーおよび現場データーを含むデーターを使用する、移動体処理デバイス。
【発明の詳細な説明】
【背景技術】
【０００１】
[0001]  位置推定は、デバイス位置を確定するために、移動体処理デバイスによって使用され、デバイスにおける複数の用途に有用な機能(feature)である。位置推定技法は、位置を計算するために複数の異なる方法の内任意のものを使用することができる。全地球ナビゲーション衛星システム（ＧＮＳＳ）のような衛星システムは位置を決定するときに補助することができるが、計算技法におけるＷｉ−Ｆｉビーコンの使用により、一層精度が高い位置解決(position fix)を行うこと、および／または衛星システムにアクセスできないエリアにおいて位置解決を行うことができる。移動体計算デバイスの位置は、ビーコンからの無線信号の強度を使用することによって推定することができる。しかしながら、屋内環境を介した信号伝搬が予測できないことは、位置解決を判定するときの課題である。信号強度測定値の適当な統計的モデルを設けるのは難しい場合があり得る。検査エリアにおいて収集された訓練データー、および移動体処理デバイスに対するリアルタイムの推定から高精度の経験的モデルを生成することができる技法に、努力が向けられたことがある。このような手法の精度は、測位アルゴリズムに分かっている位置の数に少なくとも部分的に依存する。しかしながら、起こり得る可能な信号変動が、ユーザーの経路(path)における誤差および不正確さ(inaccuracy)を増大させる可能性がある。デバイスの位置に依存して、位置精度を得るには、１つの計算方法が他の方法よりも勝ることもあり得る。
【発明の概要】
【０００２】
[0002]  位置要求に応答して位置を計算する技術を提供する。位置要求は、この要求に関連する観察ビーコン・データーを含むことができ、計算は、この観察ビーコン・データーに部分的に基づかなければならない。位置計算要求に応答して、測位アルゴリズム、ならびに異なる可能性があるデーター・ソースおよびモデル間で選択が行われる。データー・モデルおよびアルゴリズムの選択は、複数の要素に依存し、これらの要素は、デバイスが処理を実行する能力、観察ビーコンの数、および現地で位置を解明するためのデーターの入手可能性が含まれる。
【０００３】
[0003]  この摘要は、詳細な説明において以下で更に説明する概念から選択したものを、簡略化した形態で紹介するために設けられている。この摘要は、特許請求する主題の主要な特徴や必須の特徴を特定することを意図するのではなく、特許請求する主題の範囲を判定するときに補助として使用されることを意図するのでもない。
【図面の簡単な説明】
【０００４】
【図１】図１は、位置計算に利用されるワイヤレス・ビーコンに関係する移動体計算デバイスを示すブロック図である。
【図２】図２は、複数のワイヤレス・ビーコンがある屋内位置の分解斜視図である。
【図３】図３は、選択された方法を使用して位置を決定する本技術による方法を表すフロー・チャートである。
【図４】図４は、最も精度が高い計算方法を選択するステップを示すフロー・チャートである。
【図５】図５は、図３の方法のためのデーター・モデルの作成を示すフロー・チャートである。
【図６】図６は、投票特徴間隔(voting features interval)に基づくフロアの選択を示すフロー・チャートである。
【図７】図７は、ＥＺアルゴリズムを使用して位置を計算するシナリオを示すブロック図である。
【図８】図８は、第１ＡＰモデルを示す表である。
【図９】図９は、混成ＡＰモデルを示す表である。
【図１０】図１０は、投票特徴間隔データーを示す表である。
【図１１】図１１は、ＸＭＬで表された「フィンガープリントを使用して位置を得る」（ＧＬＵＦ）要求に対する応答例である。
【図１２】図１２は、第１処理デバイスおよび計算デバイスの機能的表現のブロック図である。
【図１３】図１３は、第２処理デバイスおよび計算デバイスの機能的表現のブロック図である。
【図１４】図１４は、処理システムのブロック図である。
【発明を実施するための形態】
【０００５】
[0018]  位置要求に応答して位置を決定または計算する技術を提供する。位置要求は、この要求に関連する観察ビーコン・データーを含むことができ、計算はこの観察ビーコン・データーに部分的に基づかなければならない。位置計算要求に応答して、代替測位アルゴリズム、ならびに潜在的に異なるデーター・ソースおよびモデルの間で選択が行われる。複数の異なるアルゴリズムを設けることによって、位置要求における観察データーに基づいて位置を計算する最適な方法が得られる。
【０００６】
[0019]  この技術にしたがって、位置計算システムは、少なくとも２つのアルゴリズムの内１つ、および２つのデーター・モデルを使用して位置を計算し、この位置に基づいて、アルゴリズムが一層精度が高い位置計算を行う。データー・モデルおよびアルゴリズムの選択は多数の要素に依存し、デバイスが処理を実行する能力、観察ビーコンの数、および現場で位置を解明するためのデーターの入手可能性が含まれる。本明細書における開示では、使用されるビーコンは、１つ以上の基本サービス・セット識別子（ＢＳＳＩＤ：basic service set identifier）を有するワイヤレス・フィデリティ（Ｗｉ−Ｆｉ）アクセス・ポイントとすることができる。（尚、１つの物理アクセス・ポイントが複数のＢＳＳＩＤをサポートするように構成されてもよいことは、記してしかるべきである）。
【０００７】
[0020]  第１タイプのアルゴリズムは、Ｗｉ−Ｆｉアクセス・ポイント・フィンガープリントから成るデーター、および二次元（２Ｄ）アクセス・ポイント・モデルに基づくＧＰＳ位置解明(GPS position fixes)を使用する。二次元モデルは、既知の位置を有する種々のアクセス・ポイントの緯度および経度を含む。アクセス・ポイント位置の２Ｄデーター・ストアが、全てのＷｉ−Ｆｉアクセス・ポイントの位置と共に、全ての観察位置のほぼ中心に設けられるモデル内に維持される。このように、アクセス・ポイントに関連する位置は、検出されたアクセス・ポイントの、統計的に最も可能性が高い(likely)位置を含むのであって、アクセス・ポイントが実際に位置し得る場所ではない。位置要求に応答して、位置計算の間ビーコン検出を使用して複数の測定値を組み合わせて、位置および誤差半径を計算する。本明細書では、代わりに、「推論された」位置を求めるものとして、この方法を参照する。この第１の方法はＲＦ環境の特性には敏感でない。何故なら、ＲＦ環境は、ビーコンを観察できるか否かのみに影響を及ぼし、ビーコン密度が低いときに有効であるからである。第１の方法は、より密度が高くＲＦ特性が予測可能な環境において使用してもよい。しかしながら、以下で説明する第２測位アルゴリズムは、このような密度が高い環境程、統計的により良い測位結果を提供する。
【０００８】
[0021]  第２測位アルゴリズムは、Ｗｉ−Ｆｉフィンガープリントから成るビーコン観察、現場(venue)、フロア、および既知の位置に対してユーザーによって供給されたグラウンド・トルス(ground truth)に基づく、三次元Ｗｉ−Ｆｉフィンガープリントを使用する。３Ｄデーター・ストアが設けられ、この中に、緯度、経度、現場、および現場フロア特性を有するアクセス・ポイント・モデルを供給することができる。このモデルは、信号強度を使用して、アクセス・ポイントが位置すると確信されるＷｉ−Ｆｉアクセス・ポイントを測位して、位置を測距する(range)。位置を計算するために、この測位アルゴリズムは、三角測量法を使用してデバイスを測位し、信号強度を使用して、３Ｄストアにおける公開アクセス・ポイントからの距離を決定する。デバイスの受信機利得が自動的に決定され、位置を測定するために４つの観察Ｗｉ−Ｆｉアクセス・ポイントが使用される。Ｗｉ−Ｆｉフィンガープリントからフロアを決定するために、信号強度分布に基づくフロア検出モデルが使用される。この計算システムは、ＲＦ環境が予測可能である程（即ち、ほぼ伝搬経路損失曲線に従う程）有利であり、そしてビーコン密度が高いときに有利である。
【０００９】
[0022]  本開示のコンテキストにおいて、計算された位置は、緯度、経度、ならびに現場識別子、および現場内部のフロア識別子というような他の論理位置情報を含むことができる。
【００１０】
[0023]  図１は、本明細書において説明する技術を利用することができるコンテキスト例を示す。図１は、複数の移動体計算デバイス１０２、１０４のブロック図を示す。移動体計算デバイス１０２、１０４は、これらの移動体デバイスの位置を計算するために、１つ以上のビーコン１１０ａ〜１１０ｄまたは他のセル・サイト１２０ａ、１２０ｂを利用する。移動体計算デバイス１０２、１０４は、ビーコン１１０、１２０の内１つ以上を観察しまたそうでなければ検出し、これらのビーコンからの信号を利用して位置を計算する。ビーコンの例には、セルラ・タワー、基地局、基地送受信局、基地局サイト、および／または任意の品質およびタイプのベケーション・モード(vacation mode)をサポートする任意の他のネットワーク・エレメントが含まれる。通例、ビーコン１１０ａ〜１１０ｄはＷｉ−Ｆｉビーコンを表す。Ｗｉ−Ｆｉビーコンは、既知の伝搬特性および信号を有し、例えば、建物の内部等のような、他のタイプの信号が存在し得ないエリアにおいて移動体デバイスが位置を計算することを可能にする情報を提供する。移動体計算デバイス１０２、１０４の各々は、ビーコン１１０、１２０毎にプロパティを格納することができる。ある実施形態では、プロパティの例には、観察している移動体計算デバイスの緯度および経度、ならびに観察時刻が含まれる。現場のような内部位置では、観察は、フロア位置のような、更に木目が細かい情報を含むこともできる。
【００１１】
[0024]  各移動体計算デバイスは、それ自体が位置計算を実行することができ、または情報をロケーション・サービス１２５にネットワーク５０を介して提供し、ロケーション・サービス１２５が、計算したデバイスの位置をデバイスに戻すこともできる。各位置計算は、推論デバイス位置を生成するために、ビーコン・フィンガープリント（例えば、計算デバイスによって観察される１組のビーコン）に対してカルマン・フィルタ（または他の方法）を利用することができる。また、誤差半径も計算することができる。誤差半径は、推定デバイス誤差半径をその半径として有する円として表す(reflect)ことができる。その結果、特定のビーコンが所与の信頼度で検出された場合、推定ビーコン位置を中心とする円内において、図１２の４１８において示すように、推定ビーコン半径と共に、推論デバイス位置を生成することができる。
【００１２】
[0025]  ロケーション・サービス１２５は、移動体計算デバイス（１０２、１０４）の観察、以前の位置調査、およびロケーション・サービス１２５において収集そして格納された他のデーターに基づいて、位置計算を実行することができる。ある実施形態では、ロケーション・サービス１２５は、複数の異なる移動体計算デバイスからのデーター、ならびに既知の実際の位置に関するビーコンの観察を収集することができる。この観察をここではグラウンド・トルスと呼ぶ。移動体計算デバイス１０２、１０４は、観察された位置のプロパティ、および種々の位置において観察されたビーコンのプロパティをロケーション・サービスに、ネットワーク５０を介して送ることができる。ロケーション・サービス１２５は、本明細書において例示するように、１つ以上の計算デバイスを動作させて、位置決定サービスを移動体処理デバイスにネットワーク５０を介して提供することができる。
【００１３】
[0026]  計算または推論された位置は、位置を含むこと、および関連する誤差半径を有することという双方が可能である。誤差半径とは、位置の計算において存在し得る不確実さまたは誤差の指示(reflection)である。計算された位置を使用してマッピング・アプリケーションによって表示されたときの誤差半径の図を、図１２において説明する。一般に、誤差半径は、計算された位置の周囲のエリアを表し、計算された位置のユーザーに、計算の相対的な精度を示す。
【００１４】
[0027]  観察は、ＧＰＳサービスと併せて、位置を決定するために使用することができる。場合によっては、ＧＰＳデーターが入手できないこともある。移動体計算デバイスが建物の現場(building venue)内部に存在するとき、一般に、ＧＰＳデーターへのアクセスは受けるのが難しい。このため、Ｗｉ−Ｆｉまたは他の情報の使用によって、一層正確な推論位置データーを生成することができる。
【００１５】
[0028]  図２は、構造の内部に位置付けられた複数のＷｉ−Ｆｉビーコンを有する現場２００の分解斜視図を示す。現場２００は、例えば、ショッピング・モール、学校、事務所用建物、空港、またはＧＳＰデーターへのアクセスが容易にできない他の建物であってもよい。図２は、現場２００の第１フロア２１０および第２フロア２１２を示す。複数の壁２２０が、現場２００内部にある種々の部屋２２５を分離する。ビーコン１１０は、現場２００の双方のフロアにわたって配置されている。処理デバイスは、この現場２００内部にあるビーコンのプロパティを使用して、当該処理デバイスの位置を計算することができる。一般に、計算された位置はアプリケーションに返され、アプリケーションは、この計算された位置を利用して情報をユーザーに提供する。複数の異なるタイプのロケーション・アプリケーションがあるが、マッピング・アプリケーションが、計算された位置を使用する典型である。
【００１６】
[0029]  ローカル測位は、多くの異なるプロパティを利用して実行することができる。ある方法は信号の物理的プロパティを使用し、一方他の方法は、信号が宛先ノードに到達するのに要する時間を使用する。一般的な測位システムには、到達角度、セルの識別、到達時刻、到達時間差、および電力に基づくワイヤレス測位方法を含むものがある。一般的な手法の１つでは、特定のエリアにおける信号強度情報の調査を採用する。この情報は、そのエリアの信号強度フィンガープリントを記述するデーターベースを形成する。このデーターベースは、後に、特定のパターン照合アルゴリズムによって移動体デバイスの位置を決定するために使用される。他の電力に基づくワイヤレス測位方法は、信号強度と送信機からの距離との間の関係を推定するために、伝搬損失モデル(path-loss model)を使用する。３台以上の送信機からの推定された距離が、デバイスの最終位置を三角測量するために使用される。ここでは特定の測位方法およびアルゴリズムについて説明するが、本技術は、複数の異なる位置計算方法の内任意のものを、本技術の教示と併せて組み込むこともできる。
【００１７】
[0030]  図３は、計算された位置を決定するための本技術による方法を示すフロー・チャートである。１つのコンテキストでは、位置要求に応答して位置が計算される。位置要求は、例えば、移動体処理デバイスにおいて１つ以上の位置照会アプリケーション(location aware applications)のために、計算された位置を決定することを求める移動体処理デバイスによって生成することができる。この方法は、全体的または部分的に、移動体処理デバイスのみにおいて実行することができ、またはロケーション・サービス１２５と通信しこれと協働して実行することもできる。
【００１８】
[0031]  ステップ３２０において、現場ビーコン情報を１つ以上の現場のために取得する。現場(venue)とは、建物のような、物理的設備がある場所、あるいは「アクセス・ポイント」（ＡＰ）の１つ以上のビーコンが位置する任意の場所であればよい。現場情報は、位置調査から得ることができ、位置調査の間に、現場において検出されたビーコンの位置のビーコン・フィンガープリントを含む情報が収集される。ビーコンは、移動体計算デバイス１０２、１０４によって所与の時点において検出することができ、位置観察を表し、ビーコン・フィンガープリントを含む。また、ビーコン・フィンガープリントは、信号強度、ならびに観察の日付けおよび時刻のような、検出の他の属性も含むことができる。サイト情報を収集するための１つのメカニズムが、米国特許出願第ＵＳ２０１４００５７６５１Ａ１号に開示されている。
【００１９】
[0032]  一般に、位置調査情報は、移動体処理デバイスを使用するサイト(site)を物理的に調査し、その場所のビーコン・フィンガープリントを決定し、現場のビーコン・フィンガープリントに関連する実際の位置の１組のグラウンド・トルス・データーを作ることによって収集することができる。特定の現場のためにグラウンド・トルスを作るためには、現場についての観察データーを、観察データーに対する既知の位置と関連付ける。観察データーは、所与の時点においてビーコン・フィンガープリントにマッピングされる既知の位置情報を使用して、調査によって関連付けることができる（既知の緯度、経度、およびフロア位置に関して）。１組のマップ位置の各々における既知のビーコンのフィンガープリントが作られる。推論された位置間の相関付けを使用して、この推論された位置をグラウンド・トルスと比較することによって、位置決定の精度を評価する。
【００２０】
[0033]  ３３０において、そしてステップ３２０における位置フィンガープリントの取得と同時またはその後でもよい時点において、位置を決定する要求を受けることができる。この要求は、例えば、移動体処理デバイスにおける位置照会アプリケーションから受けるのでもよい。この要求は、移動体処理デバイスにおける計算によって受けられてもよく、または移動体デバイスから送信されロケーション・サービス１２５によって受けられてもよい。移動体処理デバイスにおける複数のこのようなロケーション・アプリケーションが、計算された位置を使用して、移動体処理デバイスのユーザーに情報およびサービスを提供することができる。一旦位置決定要求が３３０において受け入れられたなら、この要求を開始した移動体測位デバイスによって観察されたビーコンの決定を３４０において行う。観察可能なビーコンが、位置フィンガープリントに関するデバイスの位置を計算するときに使用される。一実施形態では、３３０における要求が、３４０における１組の観察ビーコンを要求の一部として含んでもよい。
【００２１】
[0034]  ３５０において、１つ以上の代替位置計算方法の内どれが最も精度が高い位置計算を行うかについて、複数の要素に基づいて決定を行う。位置を計算するために使用される方法の決定については、図４に関して以下で説明する。
【００２２】
[0035]  ３６０において、選択した方法を使用して位置を計算し、３７０において、要求に応答して計算した位置を戻す。
[0036]  図４は、図３のステップ３５０において、複数の代替方法の内どれが最良の位置計算を行うか決定する１つの方法を示すフロー・チャートである。一実施形態では、２つの潜在的に可能な計算方法を利用することができる。しかしながら、異なるタイプの計算方法の数を限定する必要はないことは理解されよう。更に、本技術は屋内測位計算に適用可能であり、したがって、特定の計算方法に対して十分な数の現場ビーコンの存在が必要とされる場合もある。
【００２３】
[0037]  最初に、３６０Ａにおいて、２Ｄビーコン・モデル・データーによるカルマン・アルゴリズムに基づく推論アルゴリズムを使用するデフォルト方法が示されることは記してしかるべきである。３０６Ａのデフォルト方法は、他にもっとロバストな測位方法が本明細書において説明するように使用できない場合に、計算された位置を決定するために使用される。このアルゴリズムからの推論位置結果は３７２において得られる。１つの形態では、カルマン・アルゴリズムが３６０Ａにおいて使用されるが、位置を計算する他の方法も、本技術にしたがって、デフォルト方法として使用することができる。
【００２４】
[0038]  ３４４において、デバイスが位置する現場を決定する試みを行う。現場は、例えば、先の３４０においてデバイスによって行われた観察において存在し、検出され現場が識別された少なくとも２つのビーコンの閾値に基づいて決定することができる。一実施形態では、最小検出閾値信号強度を有する２つのビーコンが観察３４０内に存在する場合、現場が正しいことが確認される。３４６において現場検出が不成功の場合、本方法は３６０Ａにおけるデフォルト計算方法に戻る。
【００２５】
[0039]  ３４６において現場検出が成功した場合、３４８において、現場内部でフロアを検出する試みを行う。一実施形態では、フロア検出は、図６に関して以下で説明する投票プロセスによって決定することができる。
【００２６】
[0040]  フロア検出が失敗した場合、本方法は３６０Ａにおけるデフォルト計算方法に戻る。
[0041]  他の代案では、現場およびフロア検出３５５は、フロア検出ステップ３４８および３５２を使用して行われてもよい。この代案では、所与のフロアのビーコン・フィンガープリントの検出が、フロアが位置する現場を固有に(inherently)導き出す(yield)ように、フロアの検出がフロアが位置する現場を識別するデーターを含んでもよい。
【００２７】
[0042]  ３５２においてフロア検出が成功した場合、計算位置を決定するために、３Ｄ現場ベース混成アクセス・ポイント（ＡＰ）モデルを使用する推論アルゴリズム（３６０Ｂ）、または３Ｄ現場ＡＰモデルを使用する「ＥＺ」測位アルゴリズムに基づくアルゴリズム（３６０Ｃ）の内１つを使用することができる。ＥＺアルゴリズムは、K. Chintalapudi and V. Padmanabhan, "Indoor Localization Without the Pain"（区画がない屋内位置判定）、MOBICOM, Association for Computing Machinery, Inc., September 2010 (http://research.microsoft.com/pubs/135721/ez-mobicom.pdf)に、詳細が記載されている。
【００２８】
[0043]  ３５２においてフロア検出が成功した場合、最初に３６０Ｃにおいて、ＥＺアルゴリズムを使用して位置を計算する試みを行う。３７４において計算が成功した場合、３７６において、計算された位置を解明する。計算が成功しなかった場合、フロアおよび現場データーを組み込んだ混成ＡＰモデルを使用する推論アルゴリズムを使用して、３６０Ｂにおいて位置を計算する。３７８において、計算された位置を戻す。
【００２９】
[0044]  ３８０において、計算結果に対して、コヒーレンシーおよびプライバシー・チェックを行うことができる。コヒーレンシーおよびプライバシー・チェックは、結果が、指定された最小データー規格と一致する(agree with)か否か判定する。例えば、観察データーにおいて１つのＷｉ−Ｆｉビーコンしか発見されず、ビーコンには２Ｄデーターが入手できなかった場合、コヒーレンシー・チェックによって、プライバシーの懸念のために、位置結果を提供しないことを確認する。
【００３０】
[0045]  一般に、ＥＺアルゴリズムは、初期調査から報告された全ての観察、および位置計算に使用される観察が、ＲＦ伝搬の基礎となる物理特性(underlying physics)による制約を受けるという仮定を使用する。ＥＺアルゴリズムはこれらの制約をモデル化し、次いでこれらを使用して、ＡＰモデルおよび未知の位置を同時に決定する。図７を参照して、２人のユーザー（Ｍ１、Ｍ２）および２つのＡＰ（ＡＰ１、ＡＰ２）があり、４箇所のＡＰ／ユーザー間距離の全てが分かっていると仮定する（図７のシナリオＩ−Ａに示す通り）。この情報に基づいて、シナリオＩ−ＡおよびＩ−Ｂに図示するように、ＡＰおよびユーザーの位置を頂点とする様々な異なる四辺形を組み立てることができる。ＡＰおよびユーザーの相対的位置（モジュロ変換(modulo translation)、回転、および反射）の認識(realization)は一意ではない。しかしながら、３つのＡＰおよび３人の移動体ユーザーがある場合、ＡＰおよびユーザーの相対的位置に対しては、一意の認識しかあり得ない（シナリオＩＩ）ことを証明することができる。これは、ＡＰおよび移動体ユーザー間に十分な距離制約を仮定すると、相対的な意味でこれらの位置を一意に決定できることを実証する。
【００３１】
[0046]  実際には、ＡＰと移動体ユーザーとの間の距離は、受信信号強度（ＲＳＳ）によって推論することができる。距離をＲＳＳに関係付ける一般向けモデルが、次の式によって示される。
【００３２】
【数１】
0006701094.tif 000002
【００３３】
[0047]  以上の式において、ｐｉｊはｊ番目の移動体ユーザーにおけるｉ番目のＡＰからの受信ＲＳＳであり、Ｐｉは、ｉ番目のＡＰの送信電力であり、ｃｉはｉ番目のＡＰの位置であり、ｘｊはｊ番目の移動体ユーザーの位置であり、γｉはｉ番目のＡＰの近傍における伝搬損失指数(path loss exponent)であり、Ｇｊはｊ番目の移動体受信機の利得である。
【００３４】
[0048]  ＲＳＳ観察毎に、以上の形式の１つの式が得られる。移動体処理デバイス毎に、それが移動するに連れて、大多数の観察を異なる位置から収集することができるので（一部は知られている位置であるが、殆どは知られていない位置）、最終的には全ての変数を解くのに十分な式（即ち、制約）が得られる。
【００３５】
[0049]  このような式を解くことは容易くないので、特殊な汎用アルゴリズムが、これらを説くために開発された。混成方法を汎用アルゴリズムおよび確率的勾配降下法(gradient descent)と共に使用することによって、解の発見は最適化問題となる。
【００３６】
【数２】
0006701094.tif 000003
【００３７】
[0050]  以上の問題には既知の分析解がなく、大多数の極小値を有する。以上の式を解くために、２Ｄ検索空間に対する制約を使用して、ＥＺアルゴリズムを使用して位置を解明する。現場のバウンディング・ボックスを制約として使用することもできる。ＢＩＮＧ（登録商標）マップのような市販のマッピング・システムは、制約に組み込むことができる現場メタデーターを提供する。バウンディング・ボックスは、現場のエリアを覆う矩形の左下および右上を指定する２つの位置の集合である。
【００３８】
[0051]  図５は、本技術にしたがって２Ｄおよび３Ｄビーコン・ストアを収集し構築する方法を示す。一実施形態では、図５は、図３におけるステップ３２０を実行する方法を表す。５１０において、複数の既知の技法の内任意のものを使用して、現場ビーコン情報を収集する。ロケーション・サービス１２５は、本明細書において説明する種々のビーコン・ストアを収集し維持することができ、作成され本明細書において説明するモデルの全部または一部を移動体計算デバイスに供給することができる。ある実施形態では、ロケーション・サービス１２５は、複数の異なる移動体計算デバイスからのデーター、およびここではグラウンド・トルスと呼ばれる、既知の実際の位置に対するビーコンの計画的観察(scheduled observations)からのデーターを収集することができる。移動体計算デバイス１０２、１０４は、観察をロケーション・サービス１２５にネットワーク５０を介して送信することができる。
【００３９】
[0052]  ５２０において、グラウンド・トルスの位置に対するビーコン観察を使用して、現場ビーコン・ストアに入力する(populate)ことができる。一般に、現場調査情報は、移動体処理デバイスを使用して物理的にサイトを調査し、位置に対するビーコン・フィンガープリントを決定し、現場に対するビーコン・フィンガープリントに関連する実際の位置の１組のグラウンド・トルス・データーを作ることによって収集することができる。特定のビーコンに対してグラウンド・トルスを作るには、ビーコンに対して観察されたデーターを、観察されたデーターに対する既知の位置と関連付ける。観察されたデーターは、既知の位置情報を使用する調査によって関連付けることができ（既知の緯度、経度、およびフロア位置に関して）、所与の時点においてビーコン・フィンガープリントにマッピングされる。１組のマップ位置の各々における既知のビーコンのフィンガープリントが作成される。推論された位置間の相関が、位置決定の精度を評価するために使用される。
【００４０】
[0053]  ５３０において、５１０において収集した現場ＡＰデーターに基づいて、現場ＡＰモデルを作成する。
[0054]  ＡＰに対する２Ｄ（緯度および経度）観察も同様に、５１５において複数の現場に対してデーター・ストアに存在することができる。２Ｄ観察５１５は、位置データーを参照するがフロア観察をしないＡＰの観察を含むことができ、ＡＰに関連する位置データーの精度に基づいて、現場と関連付けられても、付けられなくてもよい。ＡＰ測定値を位置に相関付けることができる場合、５２５において２Ｄモデルを生成することができる。
【００４１】
[0055]  ３６０ＣにおけるＥＺアルゴリズム、および３６０Ｂにおける推論（内部カルマン）アルゴリズム双方のために、３Ｄ現場アクセス・ポイント・モデルが使用される。一実施形態では、３Ｄ現場アクセス・ポイント・モデルは、図１の移動体処理デバイスまたはロケーション・サービス１２５によって生成することができる。図８に示すように、３Ｄ現場ＡＰモデルは、以下の列、すなわちＢＳＳＩＤ（ベース・サービス・セットＩＤ）、緯度、経度、電力、ガンマ、現場ＩＤ、およびフロアＩＤから成るデーター・テーブルである。
【００４２】
[0056]  先に記したように、閾値数のビーコンが存在する場合、３６０Ｃにおいて３Ｄ  ＡＰモデルを使用して、ＥＺアルゴリズム計算を使用する試みが行われる。ＥＺアルゴリズムが位置を推論し損ねた場合（３７４において）、本システムは、位置を推論するために、３６０Ｂにおける推論アルゴリズムの使用に逆戻りする。この目的のために、現場ベース３Ｄビーコン・ストアがＡＰモデルの一部として使用される。
【００４３】
[0057]  本技術にしたがって、５３５において現場ベース３Ｄビーコン・ストアを生成する。この生成は、ロケーション・サービス１２５によって実行することができる。混成モデルの一例を図９に示す。遂行するために、屋内ＡＰモデル（図８）および現場のための３Ｄビーコン・ストアを生成するために使用される同じ訓練データーを使用して、屋内観察に対してＥＺモデルを使用して混成現場ベースＡＰモデルを生成する。この情報は、混成屋内モデルを作成するために、屋内高精度化技法(indoor refining technique)によって生成される現場ＡＰモデルと合体される。ＥＺアルゴリズムは、現場の内側におけるＡＰの位置（緯度、経度）、電力、および伝搬損失指数（ガンマ）を求めるために使用される。フィンガープリントに対して、受信信号強度を有する各ビーコンを、位置（緯度、経度）を未知数とした式として書き込むことができる。位置（緯度、経度）を解くために、少なくとも３つのビーコンが三角測量法のために使用される。しかしながら、種々のデバイスでは、受信信号強度に影響を及ぼす受信機利得も未知である。これは解に他のディメンションを追加し、したがって、少なくとも１つの余分なビーコンをフィンガープリントにおいて使用して、式を解く。したがって、一実施形態では、その位置を解くためのフィンガープリントにおけるビーコンの最小数は４つのビーコンである。この混成モデルを構築するために、観察に基づくＡＰの未知量の解（各観察はこれらの未知数を有する式となる）。この解を求める方法は、確率的勾配降下法アルゴリズムであり、誤差を最小に抑えるために、式に対する未知数の異なる組み合わせを検索することによって、解を求めようとする。この生成ＥＺアルゴリズムは、３６０Ｃにおいて位置を計算するために使用される測位アルゴリズムに相当し、同じ原理に基づく。
【００４４】
[0058]  図６は、ステップ３６０Ｃを実行する方法を示す。６１０において、少なくとも２つのビーコンが存在することを確認するために、初期決定を行う。６２０において、現場に関連する２つのビーコンが、位置要求からの観察データー（３４０）において発見されたという現場決定の判定を行うことができる。
【００４５】
[0059]  ６３０において、観察フィンガープリントにおける各ビーコンを引き出し、６４０においてフロア検出プロセスによってフロア検出を判定する。フロアは、例えば、投票アルゴリズムまたは最尤アルゴリズムによって決定することができる。
【００４６】
[0060]  最尤アルゴリズムでは、統計的確率計算が行われ、受信機利得オフセット推定最尤方法を使用して、所与のフロアがＷｉ−Ｆｉフィンガープリントを「生成する」確率を最大化するフロアおよび受信機利得を選択する。フロアを選択するために、本方法は以下の式にしたがって最大確率を解く。
【００４７】
【数３】
0006701094.tif 000004
【００４８】
ここで、Ｒは受信機利得オフセットであり、
ｆｌｏｏｒ＿ｉはｉ番目のフロアであり、
ＡＰ＿ｉｊは、ｆｌｏｏｒ＿ｉにおけるＡＰ＿ｊからの受信電力であり（ここで、ＡＰは「アクセス・ポイント」である）、
ｒｓｓｉ＿ｊは、フィンガープリントにおけるＡＰ＿ｊからの受信電力である。
【００４９】
[0061]  投票モデルでは、着信する要求からのＷｉ−Ｆｉフィンガープリントにおける各ビーコンは、屋内ビーコン・ストアにおいて（全ての現場にわたって）フロア毎に投票権を有し、最も得票が多いフロアが選ばれる(win)。また、選ばれたフロアから、現場が正しいことも確かめられる(verify)。いずれのフロアも投票を受けない場合、フロアを決定することができず、現場が正しいことが確かめられない。つまり、フロア／現場情報を応答において提供することができない。投票モデルは、G. Demiroz and H. Guvenir, "Classification by Voting Feature Intervals" （投票特徴間隔による分類）、Proceedings of the 9th European Conference on Machine Learning, pp. 85-92, 1997に記載されているような、投票特徴間隔（ＶＦＩ： Voting Feature Intervals）モデルに基づく。ＶＦＩモデルは、現場におけるビーコンについて以下の情報を収容する表である。Ｂｓｓｉｄ、ＶｅｎｕｅＩｄ、ＦｌｏｏｒＩｄ、ＩｎｔｅｒｖａｌＳｔａｒｔ、ＩｎｔｅｒｖａｌＥｎｄ、および重み。部分的ＶＦＩモデルを図１０に示す。この表における各エントリーは、フィンガープリントにおけるビーコンのＲＳＳがＩｎｔｅｒｖａｌＳｔａｒｔおよびＩｎｔｅｒｖａｌＥｎｄによって指定される間隔に入る場合に、ビーコン（Ｂｓｓｉｄ）、ＦｌｏｏｒＩｄおよびＶｅｎｕｅＩｄに対する投票（重み）（０と１の間）を 表す。ビーコンは同じフロアにおいて複数の重複しない間隔を有することができ、または異なるフロアに対して間隔を有することができる。したがって、同じビーコンに対してこの表には複数のエントリーがあることが可能である。
【００５０】
[0062]  ６５０において、以上の方法のいずれかによって決定されたフロアを戻す。
[0063]  一実施形態では、ロケーション・サービス１２５が移動体デバイスからの位置要求  に応答して位置情報を提供することもできる。このような場合、戻されるデーターは、拡張可能マークアップ言語（ＸＭＬ）で表現され、フロアおよび現場が解明されたときに「フィンガープリントを使用して位置を得る」（ＧＬＵＦ）要求に応答して提供されてもよい。この要求に応答して提供されるＸＭＬの一例を図１１に示す。品目 <ResolvedLocation>は、<LocationResult>におけるXmlElementであり、プロパティ・キャリア(property carrier)である。これは、現場の更に詳細な品目を追加することができる論理位置を表す。例えば、「ストア」(store)、「島」(isle)、「門」(gate)等の詳細な品目を追加することができる。屋内結果がない場合、<ResolvedLocation>には入力されない。また、フロア結果がなく、現場（ＶＥＮＵＩＤ）だけを戻すことも可能であり、ＶｅｎｕｅＩｄプロパティだけが <ResolvedLocation>に入力される。改良されたＧＬＵＦ応答は下位互換性があり、ＶｅｎｕｅＩｄおよびＦｌｏｏｒＩｄのような論理位置エンティティを含む追加のＸＭＬノードが１つあるだけである。
【００５１】
[0064]  図１２は、移動体計算デバイス４００のブロック図を示す。移動体計算デバイス４００は、図１の移動体計算デバイス１０２、１０４の内の１つを含むことができ、更に、以下で図１０に示すような、移動体デバイスのエレメントを含むことができる。計算デバイス４００は、例えば、プロセッサー４１２とユーザー・インターフェース４１８とを含むことができる。ユーザー・インターフェース４１８の表示の分解図が、現場２００のような、現場のマップ２００ａの平面図を示し、推論された位置の指示４１５が、この推論された位置の指示４１５の周囲にある誤差半径４１７と共に、マップ上に表示されている。
【００５２】
[0065]  デバイス４００は、複数の位置観察４１１、４２２を格納することができるメモリー４１０を含む。２つの位置観察４１１および４２２のみを示すが、メモリー４１０には複数の位置観察が存在することは理解されよう。各位置観察は、ビーコン４０２のフィンガープリントと、関連するビーコン・データー４０４とを含む。位置観察は、位置計算アプリケーション４２０によって利用することができる。位置計算アプリケーション４２０は、位置観察４１１、４２２から位置を計算するために利用することができる。位置照会アプリケーション４３０は、計算アプリケーションの位置によって計算された推論位置を、複数の目的のいずれにも利用する。一実施形態（図４に示す）では、位置照会アプリケーションは、マップ・アプリケーションでもよく、推論位置を誤差半径と共にユーザー・インターフェース上に表示することができる。尚、複数の他のタイプのアプリケーションが推論位置を利用するのであり、本明細書において説明した技術は、マッピング・アプリケーションである位置照会アプリケーションに限定されないことは理解されよう。
【００５３】
[0066]  図１３は、一実施形態においてロケーション・サービス１２５を提供するために利用することができる計算デバイス１４００の機能コンポーネントのブロック図を示す。計算デバイス１４００は、プロセッサー１４１２とユーザー・インターフェース１４１８とを含む。更に、デバイス１４００は、デフォルト・ビーコン・ストア１４１１および現場ＡＰビーコン・ストア１４２２を含むコンポーネントを内部に設けられたメモリー１４１０も含むことができる。デフォルト・ビーコン・ストア１４１１は、デフォルト・アルゴリズム処理（ステップ３６０Ａ）に使用される２Ｄ観察を含むことができ、一方現場ビーコン・ストア１４２２は、先に説明したＥＺおよび屋内推論方法のためのデーターを含むことができる。更に、メモリー１４１０は位置計算アプリケーション１４３０、１４３５と、相関付けアプリケーション１４７２とを含むことができる。必要に応じて、移動体処理デバイスにおいて使用されるような、位置照会アプリケーション１４７８もメモリー１４１０に存在することもできる。
【００５４】
[0067]  図１４は、開示した技術の動作を実現する移動体デバイスのブロック図例を示す。図１４のデバイスは、例えば、図１のデバイス１０２、１０４を更に詳細に示す実証例である。典型的な移動体処理デバイスの電子回路例が示されている。移動体デバイス１０００は、１つ以上のマイクロプロセッサー１０１２と、メモリー１０１０（例えば、ＲＯＭのような不揮発性メモリー、およびＲＡＭのような揮発性メモリー）とを含む。メモリー１０１０は、本明細書において説明した機能を実現するために制御プロセッサー１０１２の１つ以上のプロセッサーによって実行されるプロセッサー読み取り可能コードを格納する。  
【００５５】
[0068]  移動体デバイス１０００は、例えば、プロセッサー１０１２、アプリケーションを含むメモリー１０１０、および不揮発性ストレージを含むことができる。プロセッサー１０１２は、通信、および本明細書で説明したアプリケーションを含む任意の数のアプリケーションを実現することができる。メモリー１０１０は、不揮発性および揮発性メモリーを含む、任意の種々のメモリー記憶媒体タイプが可能である。デバイス・オペレーティング・システムが、移動体デバイス１０００の異なる動作を処理し、発呼および着呼、テキスト・メッセージング、音声メールのチェック等のような動作のためにユーザー・インターフェースを内蔵することができる。アプリケーション１０３０は、写真および／またはビデオのためのカメラ・アプリケーション、住所録、カレンダー・アプリケーション、メディア・プレーヤー、インターネット・ブラウザー、ゲーム、警報アプリケーション、または他のサード・パーティ・アプリケーションのような、プログラムの任意の取り合わせとすることができる。メモリー１０１０における不揮発性記憶コンポーネント１０４０は、ウェブ・キャッシュ、音楽、写真、連絡先データー、日程計画データー、および他のファイルのようなデーターを収容する。
【００５６】
[0069]  また、プロセッサー１０１２は、アンテナ１００２に結合されたＲＦ送信／受信回路１００６と通信し、赤外線送信／受信機１００８と通信し、更に加速度計および磁力計１０１５のような動き／方位センサー１０１４と通信する。加速度計は、ジェスチャによってユーザーにコマンドを入力させるインテリジェント・ユーザー・インターフェース、ＧＰＳ衛星との連絡が中断した後にデバイスの動きおよび方向を計算する屋内ＧＰＳ機能のようなアプリケーションを可能にし、デバイスの向きを検出し、電話機が回されたときに表示を縦型から横型に自動的に変更するために、移動体デバイスに組み込まれている。加速度計は、例えば、微小電気機械システム（ＭＥＭＳ）によって設けることができる。これは、半導体チップ上に組み立てられた小さな（マイクロメートル寸法の）機械的デバイスである。加速方向、ならびに方位、振動、および衝撃を検知することができる。更に、プロセッサー１０１２は、リンガー／バイブレーター１０１６、ユーザー・インターフェース・キーパッド／スクリーン１０１８、スピーカー１０２０、マイクロフォン１０２２、カメラ１０２４、光センサー１０２６、および温度センサー１０２８と通信する。磁力計は、ディジタル・コンパスのようなアプリケーションを可能にするために移動体デバイスに組み込まれている。ディジタル・コンパスは、移動体デバイス近傍の磁場の方向および大きさを測定し、磁場に対する変化を追跡し、磁場の方向をユーザーに表示する。
【００５７】
[0070]  プロセッサー１０１２は、ワイヤレス信号の送信および受信を制御する。送信モードの間、プロセッサー１０１２はマイクロフォン１０２２からの音声信号、または他のデーター信号を送信／受信回路１００６に供給する。送信／受信回路１００６は、この信号を、アンテナ１００２を介した通信のために、離れた局（例えば、固定局、オペレーター(operator)、他のセルラ・フォン等）に送信する。リンガー／バイブレーター１０１６は、着信呼、テキスト・メッセージ、カレンダー・リマインダー、アラーム・クロック・リマインダー、またはユーザーへの他の通知を知らせるために使用される。受信モードの間、送信／受信回路１００６は離れた局からの音声または他のデーター信号をアンテナ１００２を介して受信する。受信された音声信号は、スピーカー１０２０に供給され、一方他の受信されたデーター信号もしかるべく処理される。
【００５８】
[0071]  加えて、移動体デバイス１００をＡＣアダプタまたは給電ドッキング・ステーションのような外部電源に接続するために、物理コネクター１０８８を使用することができる。また、物理コネクター１０８８は、計算デバイスへのデーター接続として使用することもできる。このデーター接続は、移動体デバイス・データーを他のデバイスにおける計算データーと同期させるというような動作を可能にする。衛星ベースの無線ナビゲーションを利用してユーザー・アプリケーションの位置を中継する全地球測位サービス（ＧＰＳ）受信機１０６５が、このようなサービスのためにイネーブルされる。
【００５９】
[0072]  本技術は、複数の他の汎用または特殊目的計算システム環境あるいは構成でも動作する。本技術と共に使用するのに適していると考えられる周知の計算システム、環境、および／または構成の例には、パーソナル・コンピューター、サーバ・コンピューター、ハンドヘルドまたはラップトップ・デバイス、マルチプロセッサー・システム、マイクロプロセッサー・ベースシステム、セット・トップ・ボックス、プログラマブル消費者電子機器、ネットワークＰＣ、ミニコンピューター、メインフレーム・コンピューター、以上のシステムまたはデバイスの内任意のものを含む分散型計算環境等が含まれるがこれらに限定されるのではない。
【００６０】
[0073]  本技術は、コンピューターによって実行される、プログラム・モジュールのような、コンピューター実行可能命令という一般的なコンテキストで説明することができる。一般に、プログラム・モジュールは、ルーチン、プログラム、オブジェクト、コンポーネント、データー構造等を含み、特定のタスクを実行するか、または特定の抽象データー型を実装する。また、本技術は分散型計算環境においても実施することができ、この場合、タスクは、通信ネットワークを介してリンクされたリモート処理デバイスによって実行される。分散型計算環境では、プログラム・モジュールは、メモリー記憶デバイスを含むローカルおよびリモート双方のコンピューター記憶媒体に配置されてもよい。
【００６１】
[0074]  以上、主題について構造的特徴および／または方法論的アクトに特定の文言で説明したが、添付した特許請求の範囲において定められる主題は必ずしも以上で説明した具体的な特徴やアクトには限定されないことは理解されてしかるべきである。逆に、以上で説明した具体的な特徴およびアクトは、特許請求の範囲を実現する形態例として開示されたまでである。
【図１】
0006701094.tif 000005
【図２】
0006701094.tif 000006
【図３】
0006701094.tif 000007
【図４】
0006701094.tif 000008
【図５】
0006701094.tif 000009
【図６】
0006701094.tif 000010
【図７】
0006701094.tif 000011
【図８】
0006701094.tif 000012
【図９】
0006701094.tif 000013
【図１０】
0006701094.tif 000014
【図１１】
0006701094.tif 000015
【図１２】
0006701094.tif 000016
【図１３】
0006701094.tif 000017
【図１４】
0006701094.tif 000018