位置データベースを用いた移動装置の位置の判定
位置データベースを用いて移動装置の位置を判定する方法、プログラム及びシステムを記載する。移動装置は、アクセスポイントに関連付けられた位置を記憶することができる位置データベースをホストする。位置は、地理的グリッドのセルのグループ内に分布しうる。移動装置が移動し、セルのグループから外れた位置に関連付けられたアクセスポイントに接続したとき、移動装置は位置データベースの更新を要求することができる。移動装置は、現在のアクセスポイントの識別子を用いて位置データベースのルックアップを実行することにより、移動装置の通信範囲内にある現在のアクセスポイントを用いて移動装置の現在位置を計算することができる。移動装置は、位置データベースにおける現在のアクセスポイントに対応する位置を用いて、現在位置を計算することができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般には、移動装置の地理的位置を特定する技術に関する。
【背景技術】
【０００２】
無線通信ネットワークは、装置が無線通信するために種々の技術を採用することができる。例えば無線ローカルエリアネットワーク（ＷＬＡＮ）は、ネットワークの複数のノード（例えば、複数の装置）間の通信のために、有線ではなく無線を使用するローカルエリアネットワーク（例えば、家、会社又は学校等の小規模な建物の集まり等の相対的に狭い物理的領域を範囲に含むコンピュータネットワーク）を含むことができる。ＷＬＡＮ技術のいくつかの例には、あらゆる米国電気電子学会（ＩＥＥＥ）８０２．１１規格に基づくあらゆるＷＬＡＮ製品を含むＷｉＦｉが含まれる。
【０００３】
送信側と受信側との間の無線接続は、無線周波数（ＲＦ）技術、電波伝搬と関連付けられた電磁スペクトル内の周波数を採用することができる。ＷｉＦｉにおいて使用される無線周波数は例えば、２．５ギガヘルツ（ＧＨｚ）又は５ＧＨｚである。アンテナにＲＦ電流が供給されると電磁場が生成される。電磁場は空間を伝播する。無線通信ネットワークの構成要素にアクセスポイント（ＡＰ）がある。アクセスポイントにより、無線移動装置は有線ネットワークと通信できる。アクセスポイントの１つの機能は、無線アダプタ又は無線移動装置を搭載したコンピュータが検出及び「同調」する無線信号をブロードキャストすることである。
【０００４】
ＷｉＦｉネットワークのアクセスポイントは、アクセスポイントにより送受信される信号の強度及び地理的エリア地理的エリアその地理的エリアの物理的特性により決定される地理的エリアをカバーすることができる。変化しうる数の移動装置がアクセスポイントの通信範囲内に位置しうる。移動装置は、同時に複数のアクセスポイントの通信範囲内に位置しうる。アクセスポイントの位置が既知である場合、移動装置は、アクセスポイントから受信した信号の強度に基づいて位置を三角法で測定することにより、移動装置が通信するアクセスポイントの位置を使用して位置を判定することもできる。
【発明の概要】
【０００５】
ネットワークベースのポジショニングシステムの位置データベースを管理する方法、プログラム及びシステムを記載する。サーバコンピュータは、無線通信ネットワークのアクセスポイントの通信範囲内に配置された位置認識移動装置（例えば、ＧＰＳ対応装置）から位置情報を受信することができる。サーバコンピュータは、アクセスポイント毎に受信した位置を使用して平均地理的位置を算出することができる。平均地理的位置に基づいて、サーバコンピュータは、アクセスポイントを地理グリッドのセルに割り当てることができる。サーバコンピュータは、アクセスポイント及び受信したデータのポピュラリティ、スタビリティ、ロンジェビティ、並びにフレッシュネスに基づいて、各セルにおけるアクセスポイントをフィルタリングすることができる。サーバコンピュータは、平均地理的位置と関連付けてアクセスポイントの識別子を位置データベースに格納することができる。
【０００６】
移動装置は、移動装置が接続するアクセスポイントの位置を使用して位置を判定することができる。移動装置は、地理グリッド上のセルにおけるアクセスポイントに接続すると、アクセスポイントの位置情報、セルにおける他のアクセスポイントの位置及びセルに隣接するセルにおけるアクセスポイントの位置を要求して受信することができる。移動装置は、移動装置の通信範囲内でアクセスポイントに関連付けられた受信した情報から位置を識別することができる。移動装置は、識別した位置を使用して平均地理的位置を算出することができる。移動装置は、各位置と算出された平均地理的位置との間の距離を更に算出することができる。移動装置は、平均地理的位置から十分に離れた位置を除外することができる。移動装置は、平均地理的位置に対してある精度レベルが達成されるまで計算と除外を繰り返すことができる。移動装置は、移動装置の地図ディスプレイに情報を表示することができる。
【０００７】
ネットワークベースのポジショニングシステムの位置データベースを管理する技術は、以下の例示的な利点を達成するように実現される。アクセスポイントの実際の位置が未知である場合、地理的エリアは、無線通信ネットワークのアクセスポイントに関連付けられる。地理的エリアは、アクセスポイントの実際の位置ではなく、アクセスポイントの通信範囲内に位置する実際の移動装置が位置する可能性が高い領域に対応する。地理的エリアは、頻繁に更新されるために最新の位置情報を提供する移動装置からの実際の時間データに基づいて推定される。アクセスポイントは、遠ざかっているかあるいは遮断される場合、不正な位置判定を回避するためにデータベースから削除される。地理的エリアは、一日の異なる時間において移動装置から受信したデータに基づいて算出されるよう、通勤時間、勤務時間又は夜間等の種々の使用パターンに対応する。
【０００８】
地理的エリアに関連付けられたアクセスポイントは、アクセスポイントの通信範囲内に位置する非ＧＰＳ対応移動装置の位置を判定するために使用される。移動装置とアクセスポイントとの間の通常の通信に対する干渉を回避するために、アクセスポイントと移動装置とのデータ伝送は、移動装置がアイドル状態の時に行われる。アクセスポイントの位置を使用して移動装置の位置を判定するシステムは、直接移動装置の通信範囲内にあるアクセスポイントの位置及び隣接領域におけるアクセスポイントの位置を伝送するため、移動装置の帯域幅の消費を自律的に制限することができる。従って、移動装置が移動する場合でも頻繁に更新及び再伝送する必要はない。各セルにおけるアクセスポイントのフィルタリング機構は、各伝送において移動装置に伝送されたデータの量を更に制限することができる。信号強度が種々の干渉により変動するため、移動装置は、例えば位置を推定するために信号強度を使用するより正確に位置を推定できる。例えばＧＰＳ信号が弱い（例えば、建物内部）場合、ＧＰＳ対応移動装置は、無線アクセスポイントの位置を利用することが可能である。
【０００９】
以下の添付の図面及び明細書において、ネットワークベースのポジショニングシステムの位置データベースを管理する１つ以上の実施例の詳細を説明する。位置データベース管理の他の特徴、態様及び利点は、明細書、図面及び特許請求の範囲から明らかとなるだろう。
【図面の簡単な説明】
【００１０】
【図１Ａ】位置データベースを管理する技術を示す概略図。
【図１Ｂ】３次元空間において位置データベースを管理する技術を示す図。
【図２Ａ】、
【図２Ｂ】、
【図２Ｃ】移動装置を使用してＷＬＡＮのアクセスポイントと関連付けられた位置を判定する処理の例を説明する図。
【図２Ｄ】３次元空間において移動装置を使用してＷＬＡＮのアクセスポイントと関連付けられた位置を判定する処理の例を説明する図。
【図３Ａ】、
【図３Ｂ】移動装置を使用してＷＬＡＮのアクセスポイントと関連付けられた位置を判定する処理の例を示すフローチャート。
【図３Ｃ】位置データベースを管理する技術を実現する例示的なシステムを示すブロック図。
【図４Ａ】ネットワークベースのポジショニングシステムにおいて位置データベースを使用して移動装置の位置を判定する技術を示す図。
【図４Ｂ】位置データベースを使用して移動装置の位置を判定する例示的な処理を示すフローチャート。
【図４Ｃ】移動装置の位置を判定する例示的な適応マルチパス処理を示すフローチャート。
【図５】無線アクセスポイントの位置を使用して移動装置の位置を判定する例示的なユーザインタフェースを示す図。
【図６】図１〜図５を参照して説明する機能及び動作を実現する例示的なシステムアーキテクチャを示すブロック図。
【図７】移動装置の例示的なアーキテクチャを示すブロック図。
【００１１】
各図面において、同一の参照符号は同一の構成要素を示すものとする。
【発明を実施するための形態】
【００１２】
＜位置データベース管理の概要＞
図１Ａは、ネットワークベースのポジショニングシステム用位置データベースを管理する技術を示す概略図である。無線ローカルエリアネットワーク（ＷＬＡＮ）は、多くのアクセスポイント１０５を含む無線通信ネットワークである。アクセスポイント１０５は、無線装置が有線ネットワークに接続するための通信ハブとして動作するハードワイヤ装置又はコンピュータソフトウェアを含みうる。多数のアクセスポイント１０５が、領域（例えば、オフィスビル又は空港）内に配置されうる。
【００１３】
アクセスポイント１０５は、種々の通信プロトコルを使用して無線装置（例えば、移動装置１０８及び１１０）と通信することができる。いくつかの実施例において、アクセスポイント１０５は、米国電気電子学会（ＩＥＥＥ）８０２．１１ベースのプロトコル（例えば、ＩＥＥＥ８０２．１１ａ）を実現するＷｉＦｉ（登録商標）ネットワークのアクセスポイントである。いくつかの実施例において、アクセスポイント１０５は、ＩＥＥＥ８０２．１６ベースのプロトコル（例えば、ＩＥＥＥ８０２．１６−２００４又はＩＥＥＥ８０２．１６ｅ−２００５）を実現するＷｉＭＡＸ（ｗｏｒｌｄｗｉｄｅ ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ ｆｏｒ ｍｉｃｒｏｗａｖｅ ａｃｃｅｓｓ）ネットワークのアクセスポイントである。アクセスポイント１０５は、アクセスポイント１０５の設定及び物理的な環境を含む要因に依存して、アクセスポイント１０５の位置から１０メートル乃至数百メートル内のあらゆる場所に及ぶ通信範囲を有することができる。複数の移動装置１０８及び１１０がアクセスポイント１０５の通信範囲内にある場合、それら複数の移動装置１０８及び１１０はアクセスポイントに接続することができる。さらに、複数のアクセスポイント１０５が、接続のために単一の移動装置１０８又は１１０によって使用されることも可能である。移動装置１０８及び１１０は、自身が種々の要因に基づいて接続する特定のアクセスポイント１０５を選択することができる。例えば選択は、移動装置１０８がアクセスポイント１０５ａに接続する許可を受けているか、あるいはアクセスポイント１０５ａが無線接続に対して最強の信号を移動装置１０８に提供するかに基づく。
【００１４】
システムは、アクセスポイント１０５に関連付けられる位置領域１１５を判定することができる。位置領域１１５は、アクセスポイント１０５の通信範囲内に配置された移動装置１０８が位置する可能性が高い場所を示すように算出される。システムは、アクセスポイント１０５の通信範囲内に位置する移動装置１０８から既知の位置に基づいて判定を行う。移動装置１０８は、グローバル・ポジショニング・システム（ＧＰＳ）信号を受信し、ＧＰＳ信号を使用して位置を判定する受信機に内蔵されているかあるいは受信機と結合されるＧＰＳ対応移動装置等の位置認識移動装置でありうる。位置認識移動装置１０８は、図１Ａにおいて黒色の三角形として示される。位置認識移動装置１０８は、特定のアクセスポイント１０５（例えば、アクセスポイント１０５ａ）の通信範囲内に位置する場合、装置の位置をアクセスポイント１０５ａに伝送する。アクセスポイント１０５ａは、伝送及びアクセスポイント１０５ａの識別子をシステムに中継する。システムは、アクセスポイント１０５ａの通信範囲内に位置する移動装置１０８又は１１０のいずれかが位置する可能性が最も高い推定位置エリア１１５ａを判定することができる。本明細書において、推定位置エリア１１５は存在エリア（presence area）と呼ばれ、移動装置１０８又は１１０が特定のアクセスポイント１０５の通信範囲内に位置する場合に存在する可能性が高いことを示す。
【００１５】
システムは、存在エリア１１５を算出するために反復処理を適用することができる（例えば、マルチパス解析を実行することで）。反復処理は、円としてアクセスポイント（例えば、アクセスポイント１０５）と関連付けられる存在エリア（例えば、存在エリア１１５）を判定する。円の中心は、アクセスポイント１０５に接続された位置認識移動装置１０８の各位置に基づいて算出された平均地理的位置に対応する。円の半径は、例えば移動装置１０８の位置と平均地理的位置との間の距離等により判定される誤差範囲に対応する。図２及び図３を参照して、反復処理に関する更なる詳細を以下において説明する。反復処理は、一日の異なる時間の間の種々の無線アクセス使用パターン及び潜在的なアクセスポイント１０５の移動を入手するために定期的に（例えば、６時間毎に）実行される。
【００１６】
受信移動装置が存在エリア１１５を使用して装置の推定位置を判定できるように、システムは、アクセスポイント１０５の通信範囲内に位置する非ＧＰＳ対応移動装置（例えば、移動装置１１０）を含む移動装置に存在エリア１１５の情報を送出することができる。例えば、移動装置１１０がアクセスポイント１０５ｂの通信範囲内に位置する場合、移動装置１１０の位置は、アクセスポイント１０５ｂと関連付けられる存在エリア１１５ｂと一致するものと推定される。
【００１７】
所定の領域（例えば、空港）においては、多くのアクセスポイント１０５が存在する場合がある。また、移動装置１１０はモバイルであるため、移動装置１１０が動きを追跡するために位置を使用できるように、即座に移動装置１１０の通信範囲内にはないが移動装置１１０に十分に近接するアクセスポイントの位置を送出することは理にかなっている。大量の位置データが移動装置１１０に送出されることを回避するため、システムは、世界に存在する全てのアクセスポイントの位置データではなく、限られた数のアクセスポイント（例えば、アクセスポイント１０５ａ）の位置データのみを伝送するように、アクセスポイント１０５及び位置領域１１５をフィルタリングすることができる。フィルタリングは、位置１１５及びアクセスポイント１０５のポピュラリティ（popularity）、スタビリティ（stability）、ロンジェビティ（longevity）、フレッシュネス（freshness）を含む種々の要因に基づくことができる。
【００１８】
システムは、位置１１５及びアクセスポイント１０５をフィルタリングするために、セル１０２を含む地理グリッド１００を作成することができる。セル１０２は、略矩形形状を有する多角形である。多角形は、地理的エリアの識別点（例えば、中心又は隅）の緯度及び経度、並びに大きさ（例えば、経度の尺度で測定された長さ及び緯度の尺度で測定された幅）により地理グリッド１００上で識別可能な地理的エリアに対応する。各セル１０２は、ある特定の数の位置を含むコンテナとして使用される。例えばセル１０２は、長さが経線０．０００５度（約５６メートル）及び幅が緯度０．０００５度（メートル単位の幅は緯度に依存して変動する）の矩形である。セル１０２は、アクセスポイント１０５に対応する数（例えば、３つ）の存在エリア１１５を保持するように構成される。いくつかの実施例において、存在エリア１１５の中心がセル１０２の境界内に配置される場合、セル１０２は存在エリア１１５を「保持する」。存在エリア１１５は、１つ以上の信頼性要因に基づいてセル１０２に配置される全ての存在エリア１１５から選択される。選択は、ポピュラリティ、スタビリティ、ロンジェビティ、フレッシュネス等の種々の基準に基づくことができる。
【００１９】
特定のアクセスポイント（例えば、アクセスポイント１０５ｂ）及びアクセスポイントに関連付けられた存在エリア（例えば、存在エリア１１５ｂ）は、同一のセル１０２に配置される必要はない。例えば、アクセスポイント１０５ｂがセル１０２ａの建物に配置され、アクセスポイント１０５ｂの通信範囲内に配置された殆どの移動装置１０８がセル１０２ｂの別の建物に位置する場合、このようなことが起こりうる。いくつかの実施例において、システムは、アクセスポイント１０５ｂの実際の位置を無視することができる。
【００２０】
移動装置１１０は、アクセスポイント（例えば、関連付けられた存在エリア１１５ａがセル１０２ｃに配置されるアクセスポイント１０５ａ）に接続するか、あるいは他の方法で（例えば、セルラネットワークを介して）システムに接続される場合、システムから位置更新を受信することができる。位置更新は、存在エリア１１５ａが配置される同一のセル（例えば、セル１０２ｃ）に配置される全ての存在エリア１１５を含むことができる。位置更新は、地理グリッド１００上のセル１０２ｃに隣接する他のセル１０２（例えば、セル１０２ａ及びセル１０２ｂ）に配置される存在エリア１１５を更に含むことができる。
【００２１】
移動装置１１０は、アクセスポイント１０５ａに接続する場合、使用可能な他のアクセスポイント１０５（例えば、アクセスポイント１０５ｂ）を検出することができる。移動装置１１０は、使用可能なアクセスポイントに対する存在エリア（例えば、存在エリア１１５ａ及び１１５ｂ）を識別することができる。移動装置１１０は、種々のアルゴリズムを使用して移動装置１１０の現在位置を算出することができる。例えば、１つの存在エリア１１５ａのみが識別される場合、移動装置１１０は、存在エリア１１５ａを移動装置１１０の現在位置として指定する。２つ以上の存在エリア１１５が識別される場合、移動装置１１０は、反復処理（例えば、マルチパス解析）を使用して現在位置を算出する。反復処理は、存在エリアの平均位置及び存在エリアと平均位置との間の距離を算出し、平均位置から最も遠く離れた存在エリアを除外する。移動装置１１０の位置を判定するために必要な精度が満たされるまで、移動装置１１０は反復処理を繰り返す。移動装置１１０は、平均位置を移動装置１１０の現在位置として指定し、地図表示装置に平均位置を表示する。
【００２２】
いくつかの実施例において、存在エリア１１５ａの周囲の十分に広い領域（例えば、１又は２平方キロメートル）をカバーできるよう、システムから移動装置１１０上で受信した位置更新には、多くの隣接するセルを含めることができる。広い領域をカバーする位置更新に基づいて、移動装置１１０は、自身が移動する場合に頻繁に更新を要求しなければならないことを回避することができる。移動装置１１０は、例えばアイドル状態であるかあるいは使用可能な通信帯域幅を有する場合、更新された存在エリア情報を受信する機会を有する。
【００２３】
図１Ｂは、３次元空間において位置データベースを管理することを示す。いくつかの位置認識移動装置１０８（例えば、ＧＰＳ対応装置）は、３次元空間において位置を識別することができる。位置は、緯度、経度及び高度により示される。例えば高度は、海面からメートル単位で測定された海抜として示される。移動装置の高度が移動装置を配置するために必要な場合、移動装置を３次元空間に配置することが望ましい。例えば高度は、移動装置が位置する高層ビルの階を判定するために使用される。３次元空間における移動装置１０８の位置は、注釈として海抜を含む２次元地図又は３次元地図に表示される。
【００２４】
移動装置１０８はアクセスポイント１２６に接続することができる。移動装置１０８は、緯度座標、経度座標及び高度座標を含む位置をシステムに伝送する位置認識移動装置でありうる。システムは、移動装置１０８から受信した緯度座標、経度座標及び高度座標に基づいて平均位置を算出する。中心である平均位置を有し且つ半径である誤差範囲を有する３次元空間１２４が、アクセスポイント１２６と関連付けられる。空間１２４は、移動装置がアクセスポイント１２６の通信範囲内に位置する場合に位置する可能性が高い空間であることを表している。本明細書において、空間１２４を存在空間と呼ぶ。
【００２５】
システムは、存在空間１２４に関する情報をアクセスポイント１２６の通信範囲内に位置する移動装置に送出することができる。情報を受信する移動装置は、地理的位置を判定するために情報を使用することができる。システムは、３次元地理空間を３次元グリッド１２０に分割することができる。３次元グリッド１２０は３次元セル１２２から構成される。各３次元セル１２２は、地理グリッド１００のセル１０２に対応するベースを有する。各３次元セル１２２は、１つの次元として高さ（例えば、メートル単位で測定された）を有する。存在空間１２４の中心がセル１２２にある場合、存在空間１２４は、セル１２２に配置されているものとして示される。システムは、存在空間のポピュラリティ（例えば、存在空間における移動装置１０８からアクセスポイント１２６に接続された回数）、存在空間１２４のスタビリティ（例えば、存在空間１２４がどれだけ安定しているか）、アクセスポイント１２６のロンジェビティ（例えば、アクセスポイント１２６が存在している期間）、及び、存在空間１２４のフレッシュネス（例えば、アクセスポイント１２６の通信範囲内に位置する移動装置１０８から最新の位置伝送が受信された時）に基づいてセル１２２における存在空間の数を制限することができる。
【００２６】
システムは、３次元グリッド１２０の３次元セル１２２に基づく存在空間１２４及び隣接する存在空間に関する情報をアクセスポイント１２６の通信範囲内に位置する移動装置（例えば、移動装置１１０）に伝送する。移動装置１１０は、３次元空間において移動装置１１０の現在位置を推定するために情報を使用し、推定された現在位置を３次元地図に表示する。
【００２７】
＜サーバ側処理及び位置データベースを管理するシステムの例＞
図２Ａ〜図２Ｃは、位置データベースを管理する処理の例を示す。便宜上、技術を実現するサーバを備えるネットワークベースのポジショニングシステムを参照して技術を説明する。
【００２８】
図２Ａは、アクセスポイント１０５と関連付けられた存在エリアを判定するために使用されるマルチパス解析の例示的な処理を示す。アクセスポイント１０５は、アクセスポイント１０５の送信機の信号強度及び他の要因（例えば、アクセスポイント１０５を取り囲む地理的エリアの物理的特性）により判定されるサービスエリア２０２を有する。サービスエリア２０２内に位置する移動装置１０８は、アクセスポイント１０５に無線接続する。アクセスポイント１０５により、移動装置１０８は、種々のゲートウェイを介して有線ネットワークに接続できる。有線ネットワークは、データネットワーク（例えば、インターネット）、公衆交換電話網（ＰＳＴＮ）、他のデジタルネットワーク又はアナログネットワーク、あるいはそれらの組合せを含む。
【００２９】
移動装置１０８は、位置認識移動装置（例えば、ＧＰＳ対応移動装置）を含みうる。各位置認識移動装置１０８（図２Ａの黒色の三角形として示される）は、現在の地理的位置を検出することができる。現在の地理的位置は、移動装置１０８の緯度及び経度を含む地理座標により示される。移動装置１０８は、アクセスポイント１０５と通信する場合、アクセスポイント１０５を介して位置情報をシステムに伝送することができる。位置情報は、アクセスポイント１０５の識別子（例えば、アクセスポイント１０５のメディアアクセス制御（ＭＡＣ）アドレス）に関連付けられる。システムは、複数の移動装置１０８から受信した位置情報を使用して、アクセスポイント１０５に関連付けられる存在エリアを判定することができる。存在エリアは、アクセスポイント１００が実際に配置される位置を取り囲む必要はない。存在エリアは、サービスエリア２０２内に配置されないが、サービスエリア２０２の幾何学的な位置又は形状に対応する必要もない。
【００３０】
サービスエリア２０２内で移動装置１０８を分布させることは、特定の時間（例えば、アクセスポイント１０５が配置されるタイムゾーンに対する現地時間午前８：３０）における移動装置１０８のスナップショットに対応する。各移動装置１０８は、単一の位置に関連付けられる。サービスエリア２０２内で移動装置１０８を分布させることは、ある期間（例えば、午前４時〜午前１０時の６時間）にわたる移動装置１０８の位置に更に対応する。各移動装置１０８は、複数の位置に関連付けられる（例えば、移動装置１０８が移動している場合）。図２Ａにおいて複数の三角形で示されるように、複数の位置に関連付けられる単一の移動装置１０８は、システムにおいて複数の位置で示される。
【００３１】
サーバは、移動装置１０８から受信した位置の集合の平均地理的位置を判定することができる。位置の集合は、特定の時間において又は特定の期間中に移動装置１０８から受信した位置を含む。平均地理的位置は、円２０４ａが含む領域の中心２０５として指定される。円２０４ａの中心は、アクセスポイント１０５の位置と一致する必要はない。サーバは、平均地理的位置と集合における各位置との間の距離を算出し、１つ以上の外れ値を識別することができる。外れ値は、平均地理的位置から最も遠くに配置される集合における位置である。中心までの距離が閾値を上回る外れ値（例えば、位置２１０）は、集合から除外される。外れ値が除外された後、円２０４ａは、平均地理的位置と現在の集合における位置との間の最長の距離に対応する半径２０６を有する。
【００３２】
図２Ｂは、図２Ａの処理に後続するマルチパス解析の処理の例を示す。図２Ａの平均地理的位置（円２０４ａの中心２０５）までの距離が閾値を上回る位置は、集合から除外されている。閾値は、位置の割合（例えば、図２Ａの位置の５％）が除外されるように構成される。新しい平均地理的位置は、集合に依然として存在するある割合（例えば、依然として存在する位置の９５％）の位置に基づいて算出される。例えば、新しい平均地理的位置は円２０４ｂの中心２１５である。種々の実施例において、新しい平均地理的位置を算出することは、集合における残りの位置を平均化すること、集合における中間地理的位置を選択すること（例えば、中緯度又は中経度を選択することにより）、あるいは他のアルゴリズムを適用することを含む。平均地理的位置を算出するアルゴリズムは、マルチパス解析の各パスにおいて同一であるか、あるいは各パスにおいて互いに異なる。
【００３３】
外れ値の位置が除外される場合、円２０４ｂに含まれた領域は、前のパスにおいて判定されたような円２０４ａが含む領域より狭い。より狭い領域は、向上した計算の精度を反映する。円２０４ｂの中心２１５は、円２０４ａの中心２０５と一致する必要はない。いくつかの実施例において、円２０４ｂの半径２１６は、円２０４ｂの中心２２５から最も遠く離れた移動装置１０８の残りの位置に対応する。半径２１６は、存在エリアが現在のパスにおいて算出した新しい推定位置の誤差範囲を示す。
【００３４】
図２Ｃは、マルチパス解析の最終処理の例を示す。ある特定の終了条件を満たす場合、システムは、最終処理後に反復処理を終了する。最終処理は、移動装置１０８の位置のクラスタに対応する最終的な平均地理的位置を生成する。最終的な平均地理的位置は、円２０４ｃの中心２３５として示される。円２０４ｃは、最終的な平均地理的位置とクラスタの位置との間の距離に基づいて最終的な誤差範囲に対応する半径を有する。円２０４ｃは、アクセスポイント１０５と関連付けられた存在エリア及びアクセスポイント１０５の識別子（例えば、ＭＡＣアドレス）として指定される。
【００３５】
サーバは、種々の要因に基づいてアクセスポイント１０５の識別子及び関連付けられた存在エリアを位置データベースに含むかを判定することができる。例えばサーバは、地理グリッド１００のセル１０２における存在エリアの数をカウントし、ポピュラリティ、スタビリティ及びロンジェビティに基づいて存在エリアの数を選択することができる。移動装置１０８がＧＰＳ対応装置であるかに関係なく、サーバは、位置データベースにおける存在エリア（存在エリア２０４ｃが選択される場合に存在エリア２０４ｃを含む）の情報を移動装置（例えば、移動装置１０８）に送出することができる。
【００３６】
図２Ｄは、３次元空間において位置データベースを管理する例示的な処理を示す。図２Ｄにおいて、軸Ｘ、Ｙ及びＺは、３次元空間を示すために使用される。例えば、軸Ｘ、Ｙ及びＺは、それぞれ、経度、緯度及び高度を示す。便宜上、アクセスポイント１２６の位置は、図２ＤにおいてＸ軸、Ｙ軸及びＺ軸上で原点と一致するように示される。いくつかの実施例において、アクセスポイント１２６の実際の位置（例えば、緯度座標、経度座標及び高度座標）の計算は必須でない。
【００３７】
図２Ｄの各三角形は、３次元空間に配置された移動装置の位置を示す。位置は、３次元空間において平面に投影（例えば、投影２２６）を有する。平面は、任意の緯度（例えば、アクセスポイント１２６の緯度）において規定される。例えば平面は、軸Ｘ及びＹにより規定される。アクセスポイント１２６は、アクセスポイント１２６の信号強度及び他の制限要因（例えば、信号路における階、天井、建物）により判定されるサービスエリア空間２２２に対応する。
【００３８】
マルチパス解析は、セル空間２０２に位置する位置認識移動装置１０８から受信した位置の集合に基づくＷＬＡＮのアクセスポイント１２６と地理空間を関連付ける。マルチパス解析のパスにおいて、平均地理的位置（例えば、空間２２４の中心）は、例えば集合における位置の緯度座標、経度座標及び高度座標を平均化することで判定される。サービスエリア空間２２２における平均地理的位置と位置との間の距離が算出される。サービスエリア空間２２２内にあるが平均地理的位置から十分に遠く離れた位置は、集合及び更なる計算から除外される。空間２２４の半径は、例えば集合における残りの位置と平均地理的位置との間の最も遠い距離で判定される。
【００３９】
システムは、集合における平均地理的位置を算出するステップ、平均地理的位置と集合における位置との間の距離を算出するステップ、及び算出された距離に基づいて集合から位置を除外するステップを繰り返す。終了条件が満たされるまで繰返しは継続する。平均地理的位置における中心及び平均地理的位置と集合における残りの位置との間の距離に基づく半径を有する空間は、アクセスポイント１２６と関連付けられる存在空間として指定される。
【００４０】
図３Ａは、位置データベースを管理する例示的な処理３００を示すフローチャートである。処理３００は、例えばＷＬＡＮのアクセスポイントと関連付けられた存在エリア又は存在空間を判定するために使用される。存在エリア又は存在空間は、非ＧＰＳ対応移動装置の位置を判定するために使用される。便宜上、処理３００を実現するシステムを参照して処理３００を説明する。
【００４１】
システムは、アクセスポイント１０５の通信範囲内に位置する１つ以上の第１の移動装置１０８から位置の集合を受信する（３０２）。各位置は、地理座標（例えば、緯度、経度及び高度）の集合により示される。位置は、アクセスポイント１０５の識別子（例えば、ＭＡＣアドレス）と関連付けられる。アクセスポイント１０５がシステムと通信する場合、アクセスポイントの識別子は、アクセスポイント１０５により自動的に供給される。種々の実施例において、位置の集合は、ある期間（例えば、６時間又はアクセスポイント１０５が配置されるタイムゾーンの午前６時〜午前１０時）に対応する。
【００４２】
いくつかの実施例において、ある期間は、一日の異なる時間における特定の使用パターンの特性を反映するように構成される。アクセスポイント１０５の通信範囲内に移動装置が位置する可能性が最も高い領域は、一日の間に変動し、特定の時間における種々の使用パターンを示す。例えばある期間は、「通勤時間」、「勤務時間」、「夜間」等に対応する。一日の時間の特性は、移動装置１０８の種々の使用パターンに対応する。例えば、アクセスポイント１０５と関連付けられた存在エリアは、通勤時間中は高速道路又はその周辺にあり、勤務時間中はオフィスビル又はその周辺にあり、夜間は特に集中点はなく拡散する。システムは、例えば午前４時〜午前１０時に受信した位置に基づいて存在エリアを算出し、例えば午前１０時〜午後４時に受信した位置に基づいて存在エリアを算出し直す。特徴的な期間の各々において受信した位置は、システムにおいて集合にグループ化される。位置は、サーバに結合された記憶装置上であらゆるデータ構造（例えば、リレーショナルデータベースにおける集合、リスト、アレイ、データレコード等）で格納される。
【００４３】
システムは、受信した位置の集合の平均に基づいてアクセスポイント１０５と関連付けられた地理的位置を判定することができる（３０４）。地理的位置は、上述したような存在エリア又は存在空間を含む。存在エリア又は存在空間は、例えばアクセスポイント１０５のＭＡＣアドレスによりアクセスポイント１０５と関連付けられる。いくつかの実施例において、地理的位置を判定することは、各パスにおいて集合から少なくとも１つの位置を除外することを含む受信した位置の集合に対してマルチパスアルゴリズムを適用することを含む。地理的位置を判定することは、定期的にマルチパスアルゴリズムを適用することを含む。
【００４４】
システムは、アクセスポイント１０５のポピュラリティ、地理的位置のスタビリティ及びアクセスポイント１０５のロンジェビティを含む種々の要因に基づいてアクセスポイント１０５及びアクセスポイント１０５と関連付けられた地理的位置を地理グリッド（例えば、地理グリッド１００）上のセル（例えば、セル１０２）に割り当てることができる（３０６）。いくつかの実施例において、アクセスポイント１０５のポピュラリティによって、アクセスポイント１０５の通信範囲内に位置する移動装置１０８の数を測定することができる。アクセスポイントのポピュラリティは、例えばアクセスポイント１０５の通信範囲内に存在する移動装置１０８の位置がある期間においてシステムにより受信される数により測定される。
【００４５】
存在エリアがアクセスポイント１０５の通信範囲内に配置された装置の位置を推定するために使用される場合、アクセスポイント１０５と関連付けられた存在エリアのスタビリティは、存在エリアの信頼性を反映する。アクセスポイント１０５と関連付けられた存在エリアのスタビリティは、例えば最後の２つの計算により算出された存在エリアを比較することで測定され、存在エリア間の重複の度合いを判定する。重複の度合いが高いほど、存在エリアはより安定する。
【００４６】
アクセスポイント１０５のロンジェビティは、アクセスポイント１０５と関連付けられたデータの品質を反映する。例えば、より長い時間データベースにあるアクセスポイントは、最近追加されたアクセスポイントより信頼性が高い。アクセスポイント１０５のロンジェビティは、位置データベースにおけるデータの履歴により測定される。
【００４７】
いくつかの実施例において、データのフレッシュネスは、アクセスポイント１０５と関連付けられた存在エリアが地理グリッド１００のセル１０２に割り当てられるかを判定するために更に使用される。データのフレッシュネスは、システムがどれくらい前に移動装置１０８から最新の位置を受信したかにより測定される。
【００４８】
システムは、ポピュラリティ、スタビリティ、ロンジェビティ及びフレッシュネスに基づいて地理グリッド１００のセル１０２に配置された各存在エリアをランク付けすることができる。セル１０２に配置された全ての存在エリアのうちの少なくとも一部（例えば、アクセスポイント１０５と関連付けられる存在エリアを含む３つの存在エリア）は、セル１０２に割り当てられる。割り当てられたアクセスポイント及び存在エリアは、アクセスポイント１０５の通信範囲内に位置する移動装置（例えば、移動装置１１０）を配置するために使用される。割り当てられない存在エリアは、今後使用するために位置データベースに格納される。
【００４９】
システムは、アクセスポイント１０５と関連付けられた地理的位置をアクセスポイント１０５の通信範囲内に位置する第２の移動装置（例えば、移動装置１１０）に提供することができる（３０８）。システムは、同一のセルに配置された他の地理的位置及び隣接するセルに割り当てられたアクセスポイントと関連付けられた地理的位置を第２の移動装置に更に提供することができる。位置は、種々のプッシュ又はブロードキャスト技術を要求あるいは使用することで、アクセスポイント１０５から第２の移動装置に伝送される。
【００５０】
いくつかの実施例において、システムは、３次元位置情報を受信、処理及び伝送する。存在空間（例えば、存在空間１２４）は、３次元地理グリッド（例えば、３次元グリッド１２０）上の３次元セル（例えば、３次元セル１２２）に割り当てられる。位置は、種々のプッシュ又はブロードキャスト技術を要求又は使用することで、アクセスポイント１２６からアクセスポイント１２６の通信範囲内に位置する第２の移動装置に伝送される。
【００５１】
図３Ｂは、位置の集合を使用して平均地理的位置を算出する例示的な処理３０４を示すフローチャートである。便宜上、処理３０４を実現するシステムを参照して処理３０４を説明する。
【００５２】
システムは、集合における位置を使用して平均地理的位置を算出することができる（３２４）。平均地理的位置の算出は、集合における位置の緯度、経度及び高度の平均を算出すること、並びに算出された平均の緯度、経度及び高度における位置を平均地理的位置として指定することを含むことができる。いくつかの実施例において、平均地理的位置の算出は、集合における位置の中緯度、中経度及び中高度における位置を平均地理的位置として指定することを含むことができる。
【００５３】
システムは、集合における位置と平均地理的位置との間の距離を算出することができる（３２６）。いくつかの実施例において、システムは、集合における各位置とユークリッド空間における平均地理的位置との間の直線距離を算出することができる。いくつかの実施例において、システムは、地球の曲率を考慮して集合における各位置と平均地理的位置との間の測地線距離を算出することができる。
【００５４】
ステップ３２６で算出された距離は、中心と関連付けられた半径として指定される。円（例えば、円２０４ａ）の中心である中心は、ステップ３２４で算出された平均地理的位置である。円の半径は、位置の集合における位置と平均地理的位置との間の少なくとも１つの距離に基づいて判定される。いくつかの実施例において、半径は、平均地理的位置と集合に依然として存在する位置との間の最長距離に等しい。いくつかの実施例において、円１０６ｄが半径及び中心である平均地理的位置を使用して描画される場合、半径は、円が集合に依然として存在するある割合（例えば、８０％）の位置を含む距離である。半径は誤差の範囲を示す。その誤差の範囲を超えると、非ＧＰＳ対応移動装置の位置の推定値は、統計的に有意義である可能性が低い。
【００５５】
システムは、平均位置と位置との間の距離に基づいて集合から少なくとも１つの位置を除外することができる（３２８）。いくつかの実施例において、システムは、平均地理的位置までの距離が閾値距離を上回る位置を除外する。マルチパス解析の各パスにおいて、システムは、位置の集中（例えば、クラスタ）から離れると考えられる位置を除外することにより、推定された平均地理的位置の精度を向上させることができる。位置のクラスタから離れた位置は、アクセスポイント１０５と関連付けられた存在エリアを推定するためにあまり有用ではなく、除外される。種々の実施例において、閾値距離は、１つのパスから次のパスに変動しうる。いくつかの実施例において、閾値距離は平均地理的位置までの距離である。閾値距離内において、集合のある割合（例えば、９５％）の位置が設けられる。いくつかの実施例において、閾値距離は、パスに対応する距離の集合である（例えば、第１のパスに対して２５０メートル、第２のパスに対して１５０メートル等）。平均地理的位置と位置との間の距離が閾値距離を上回る場合、システムは、集合から少なくとも１つの位置を除外することができる。
【００５６】
システムは、終了条件が満たされるまでステップ３０４におけるステップ３２４、３２６及び３２８を繰り返すことができる。システムは、繰返しを終了するための終了条件が満たされるかを判定することができる（３３０）。いくつかの実施例において、終了条件は、繰返しの回数が閾値回数（例えば、１０回）に達したときに満たされる。閾値回数及び除外すべき位置の割合は、確実性（例えば、より広い存在エリアにより、セルにおける移動装置が実際に存在エリアに位置する信頼度が高くなる）と精度（例えば、より狭い存在エリアにより、移動装置のより正確な位置が得られる）とのバランスを微調整するように構成可能である。例えば、割合が９５％に設定され、パスの数が１０に設定される場合、最終的なパスは、全ての位置データ点の約６０％を含む円を生成することができる。
【００５７】
いくつかの実施例において、存在エリア又は存在空間が十分に狭い場合に、ステップ３３０における終了条件が満たされる。移動装置が非常に集中するセルにおいて、存在エリアは、更なるパスが精度を向上させる必要がないほど十分に狭い。円の半径が閾値半径を下回る場合、ステップ３２４、３２６及び３２８の繰返しは終了する。例えば閾値半径は、８〜１０メートルである。閾値半径は、受信した集合における位置の分布パターン（例えば、受信した位置データ点の数、位置データ点の密度及びセルにおける集中領域）に基づいてアクセスポイント毎に異なる。
【００５８】
システムは、中心である平均地理的位置及び少なくとも１つの算出された距離に基づく半径を有する円として地理的エリアを指定することができる（３３２）。地理的エリアは、アクセスポイント（例えば、アクセスポイント１０５）と関連付けられる。サーバは、移動装置の現在位置を算出するために地理的エリア（例えば、中心及び半径）を移動装置に提供することができる。中心は緯度及び経度で示される。距離が３次元空間において算出されるいくつかの実施例において、中心は高度で更に示される。
【００５９】
図３Ｃは、位置データベースを管理する技術を実現する例示的なシステムを示すブロック図である。システムは、１つ以上のプロセッサ、命令を格納する１つ以上のメモリ素子及び他のハードウェアコンポーネント又はソフトウェアコンポーネントを含む。システムは、アクセスポイント（例えば、アクセスポイント１０５）と関連付けられる存在エリア又は存在空間を判定するために使用される位置特定エンジン３５０を備える。
【００６０】
位置特定エンジン３５０は、種々のアクセスポイントを介して種々の移動装置からデータを受信するデータ収集モジュール３５２を備える。データは、１つ以上の位置認識移動装置（例えば、移動装置１０８）の位置及び移動装置１０８が接続されるアクセスポイントを示すアクセスポイントの識別子（例えば、アクセスポイント１０５のＭＡＣアドレス）を示す多数のデータ点を含む。いくつかの実施例において、データ点は、移動装置１０８が位置するタイムゾーンに関する情報を更に含む。データ収集モジュール３５２は、移動装置１０８から伝送されたデータを受信するデータ受信モジュール３５４及びデータ・インデクシング・モジュール３５６を備える。データ・インデクシング・モジュール３５６は、受信したデータ点に対して種々の処理を実行する。例えばデータ・インデクシング・モジュール３５６は、セルＩＤに基づいて緯度、経度及び高度をソートする。データ・インデクシング・モジュール３５６は、期間に基づいてデータを集合に更にグループ化する。例えば、受信した位置の新しい集合は、構成可能な期間（例えば、６時間）にわたり作成される。
【００６１】
移動装置１０８の受信した位置の集合は、データ点データベース３６０に格納される。データ点データベース３６０は、種々の移動装置１０８の現在位置及び履歴位置を格納することができる。データ点データベース３６０は、アドホックデータベース、リレーショナルデータベース、オブジェクト指向データベースを含む。データ点データベース３６０は、位置特定エンジン３５０に関連してローカル又はリモートでホストされる。
【００６２】
位置計算モジュール３６４は、データ点データベースにおいてデータ点の集合における平均地理的位置及び平均地理的位置と種々のデータ点の位置との間の距離を算出し、更なる計算のために集合から位置を除外するために利用される。終了条件が特定の集合（例えば、セルＩＤと関連付けられたデータ点の集合）に到達するまで、位置計算モジュール３６４は、特定の集合に対する計算を実行する。位置計算モジュール３６４は、アクセスポイント（例えば、アクセスポイント１０５）毎に存在エリア又は存在空間を判定する。
【００６３】
いくつかの実施例において、位置計算モジュール３６４は、妥当性チェッカ３６６を使用して種々の基準及びデータ点の種々のデータに基づいて存在エリア又は存在空間に対する妥当性チェックを実行する。例えば、移動装置１０８から受信したデータ点は、国識別コード（ＭＣＣ：Mobile Country Code）及びタイムゾーンの情報を含む。妥当性チェッカ３６６は、算出された存在エリア又は存在空間をＭＣＣにより示された国に対応する多角形及びタイムゾーンに対応する多角形と比較する。算出された存在エリア又は存在空間が多角形の外側に配置される場合、妥当性チェッカ３６６は、異常を登録し、アクセスポイントを除外する。
【００６４】
位置フィルタリングエンジン３６８は、存在エリア又は存在空間が現在アクセスポイントの通信範囲内に配置されている移動装置の位置を推定するために使用されるかを判定することができる。位置フィルタリングエンジン３６８は、地理領域を地理グリッド１００のセル１０２又は３次元グリッド１２０の３次元セル１２２に分割することができる。位置フィルタリングエンジン３６８は、ポピュラリティ、スタビリティ、ロンジェビティ及びフレッシュネスに基づいて存在エリア又は存在空間をランク付けすることができる。位置フィルタリングエンジン３６８は、各セル１０２又は３次元セル１２２に配置されたトップレベルの存在エリア又は存在空間をセル１０２又は３次元セルに割り当てることができる。
【００６５】
存在エリア及び存在空間は、位置の集合の平均の緯度座標、経度座標及び高度座標を有する中心により規定される。存在エリア及び存在空間は、位置の集合における位置から中心までの距離に基づいて判定された半径により更に規定される。存在エリア及び存在空間に対する中心の緯度座標、経度座標及び高度座標、並びに存在エリアの半径及び存在空間の半径は、位置データベース３７２に格納される。位置データベース３７２は、割り当てられた存在エリア及び存在空間、並びに割り当てられない存在エリア及び存在空間を全て格納する。割り当てられない存在エリア又は存在空間は、位置計算モジュール３６４による後続の計算に割り当てられる。位置データベース３７２は、位置計算モジュール３６４により定期的に更新される。
【００６６】
位置データベース３７２のデータは、データ配信モジュール３７６を使用して移動装置に配信される。データ配信モジュール３７６は、ブロードキャストを介して要求されるか、あるいは移動装置から要求を受信せずに種々のプッシュ技術を使用して、アクセスポイントと関連付けられる割り当てられた存在エリア及び存在空間（例えば、中心座標及び半径）の情報を移動装置（例えば、非ＧＰＳ対応移動装置１１０）に送出する。
【００６７】
いくつかの実施例において、データ配信モジュール３７６は、１つの伝送セッションにおいて多数の存在エリア及び存在空間を移動装置に送出することができる。移動装置の通信帯域幅を消費する移動装置への位置伝送の回数を減少するために、データ配信モジュール３７６は、移動装置１１０が位置するセルに隣接するセルを配置するために隣接ロケータ３８０を使用することができる。例えば隣接するセルは、セル及び周囲のセルの全領域がある特定の地理的エリア（例えば、１又は２平方キロメートル）を範囲に含むように移動装置１１０が位置するセルを取り囲む多くのセルを含む。多数のセル（例えば、４００個のセル）と関連付けられた存在エリア及び存在空間に関する情報を移動装置１００に送出することにより、移動装置１１０がセルにわたって移動する場合の伝送の回数が減少する。そのような実施例において、データ配信モジュール３７６は、移動装置１１０が前に送出された全てのセルの外に出る場合に移動装置１１０に更新を送出するだけでよい。
【００６８】
＜位置データベースを用いて移動装置の位置を判定する処理の例＞
図４Ａは、無線アクセスポイントの位置を使用して移動装置の位置を判定する技術を示す。移動装置４００は、位置を判定するために無線アクセスポイントの位置を使用する例示的な移動装置である。アクセスポイント４０４を含む通信ネットワークの例示的な部分を示す。
【００６９】
移動装置４００は、アクセスポイント４０４ａの通信範囲内に位置しうる。移動装置４００は、隣接するアクセスポイントの存在エリア又は存在空間（存在エリア４０６を含む）に関する情報を含むデータをアクセスポイント４０４ａから受信する。移動装置４００は、受信したデータを位置データベースに格納する。位置データベースは、移動装置４００の記憶装置にホストされうる。格納されたデータは、定期的に、又は要求に応じて、更新されうる。
【００７０】
示された例において、移動装置４００は、アクセスポイント４００ａの通信範囲内に位置する。更に移動装置４００は、アクセスポイント４０４ｂ、４０４ｃ及び４０４ｄに対する通信範囲内にある。移動装置４００は、ＷＬＡＮ（例えば、ＩＥＥＥ８０２．１１ａ）において使用された無線通信プロトコル下でアクセスポイント４０４ａ、４０４ｂ、４０４ｃ及び４０４ｄを識別する。アクセスポイント４０４ａ、４０４ｂ、４０４ｃ及び４０４ｄは、アクセスポイントのＭＡＣアドレス又は他の識別子（例えば、Ｂｌｕｅｔｏｏｔｈ（登録商標）識別子）により識別される。
【００７１】
移動装置４００は、それぞれ、アクセスポイント４０４ａ〜４０４ｄと関連付けられる存在エリア４０６ａ、４０６ｂ、４０６ｃ及び４０６ｄを識別することができる。存在エリア４０６ａ〜４０６ｄを識別することは、移動装置４００に結合されたメモリ素子から存在エリア４０６ａ〜４０６ｄに関する情報を検索することを含む。いくつかの実施例において、移動装置４００は、アクセスポイント４０４ａ〜４０４ｄの識別子をサーバに送出することにより、サーバから存在エリア４０６ａ〜４０６ｄを要求することができる。
【００７２】
存在エリア４０６ａ〜４０６ｄに基づいて、移動装置４００は、存在エリア４０６ａ〜４０６ｄに対して反復処理（例えば、マルチパス解析）を実行することができる。反復処理によって、移動装置４００の現在の地理的位置の推定位置である地理的エリア４０２を生成することができる。３次元位置情報が利用される場合、地理的エリア４０２は地理空間である。移動装置４００は、表示装置（例えば、地図ディスプレイ）上に推定された現在位置を表示することができる。
【００７３】
図４Ｂは、位置データベースを使用して移動装置の位置を判定する例示的な処理４１０を示すフローチャートである。便宜上、処理４１０を実現する移動装置４００を参照して処理４１０を説明する。
【００７４】
移動装置４００は、移動装置４００が位置する通信範囲内の現在のアクセスポイントを識別することができる（４１２）。移動装置４００は、移動装置４００にホストされる位置データベースの更新を要求すべきかを判定するために現在のアクセスポイントを使用することができる。移動装置４００にホストされた位置データベースは、以前に移動装置４００にダウンロードされたアクセスポイントの記録を含む。移動装置４００にホストされた位置データベースにおける記録は、アクセスポイントの識別子（例えば、ＭＡＣアドレス）及び対応する位置（例えば、緯度座標／経度座標）を含む。
【００７５】
ステップ４１２において、移動装置４００は、現在のアクセスポイントが位置データベースの記録に含まれるかを判定することができる。移動装置は、移動装置４００が位置する通信範囲内の現在のアクセスポイントの識別子（例えば、ＭＡＣアドレス）を使用して位置データベースの検索を実行することができる。現在のアクセスポイントが位置データベースの記録に含まれる場合、移動装置は、位置データベースが最新であると判定することができる。現在のアクセスポイントが位置データベースの記録に含まれない場合、移動装置４００は、位置データベースの更新が必要であると判定することができる。
【００７６】
移動装置４００は、現在のアクセスポイントの識別子を使用して移動装置４００の位置データベースの更新をサーバから要求することができる（４１４）。アクセスポイントの識別子及び位置を含む位置データベースにおける記録は、新しいアクセスポイントの新しい識別子及び位置を使用してリフレッシュされる。移動装置４００は、現在のアクセスポイントの識別子をサーバに送出することができる。サーバは、地理グリッドにおいてセルを中心セルとして識別することができる。中心セルは、サーバに対して現在のアクセスポイントの識別子と関連付けられた位置を含むセルであり、セル及び隣接するセルにおける全てのアクセスポイント位置を移動装置４００に送出することができる。サーバは、中心セルを、隣接セルの位置決めのための始点として使用することができる。中心セルは、その中心セル及びその隣接セルを含むセルのグループのアンカーとなりうるが、その中心セルが、セルのグループの正確な地理的な中心に位置している必要はない。例えば、中心セルが臨海地上のセルであり、隣接セルが全て当該中心セルの片側に配置されることもある。
【００７７】
移動装置４００は、第２のアクセスポイントと関連付けられた第２の位置の集合を受信することができる（４１６）。第２のアクセスポイントは、地理グリッド上の中心セル及び中心セルに隣接するセルに配置される。現在のアクセスポイント（例えば、円形領域の中心）と関連付けられた位置は、中心セルに配置される。隣接するセルは、地理グリッド上の中心セルに隣接又は近接して配置されるセルである。隣接するセルの数は、中心セル及び隣接するセルが所定の地理的エリア（例えば、１．５平方キロメートル）を範囲に含むような値を有する。アクセスポイントと関連付けられた位置が中心セル及び隣接するセルが範囲に含む地理的エリア内にある場合、アクセスポイントの識別子及びアクセスポイントと関連付けられた位置は、更新に含まれる。現在のアクセスポイントが位置データベースの記録に含まれない場合に移動装置４００上で位置を更新する１つの例示的な利点は、移動装置４００がセルからセルに移動する場合に移動装置４００が単一のアクセスポイントのサービスエリアと比較して広い領域の外に出るまで更新が必要ないことである。従って、頻繁に更新することが回避され、移動装置４００（例えば、帯域幅、ＣＰＵサイクル、電池電源）及びサーバ（例えば、移動装置が１つのストリートブロックから次のストリートブロックに移動する場合、サーバは、頻繁に起きる更新を多くの装置に送出する必要はない）双方に対するリソースを節約することができる。
【００７８】
移動装置４００は、受信したアクセスポイントの位置の集合及び識別子を使用して移動装置４００にホストされた位置データベースを更新することができる（４１８）。更新により、中心セル及び隣接セルによってカバーされる地理的エリアにおいて移動装置４００を「中心に置く」ことができる。移動装置４００は、自身が中心セルから隣接するセルのうちの１つが範囲に含まないセルに移動するまで別の更新を要求する必要はない。例えば、各セルが約５０メートル×５０メートルであり、所定の地理的エリアが１．５平方キロメートルである場合、各更新は、約６００個のセルを移動装置４００の位置データベースに注入する。移動装置が６００個のセルが範囲に含む領域の外に出ない限り、移動装置４００は別の更新を要求する必要はない。
【００７９】
移動装置４００は、移動装置４００にホストされる位置データベースを使用して移動装置４００の現在位置を算出する（４２０）。計算は、移動装置４００により実行された適応マルチパス処理を使用して実行される。図４Ｃに関連して、マルチパス処理の更なる詳細を以下において説明する。他の要因（例えば、種々のアクセスポイントからの信号強度）が現在位置の計算を支援してよいが、これらの要因は計算には必要ない。
【００８０】
移動装置４００は、必要に応じて移動装置４００の地図表示装置に移動装置４００の現在位置を表示することができる（４２２）。図５に関連して、現在位置の表示例を以下において更に詳細に説明する。
【００８１】
図４Ｃは、移動装置の位置を判定する例示的な適応マルチパス処理４３０を示すフローチャートである。便宜上、処理４３０を実現する移動装置４００を参照して処理４３０を説明する。
【００８２】
移動装置４００は、無線通信ネットワーク（例えば、ＷＬＡＮ）のアクセスポイント（例えば、アクセスポイント４０４）の識別子を受信することができる（４３２）。アクセスポイントは、移動装置４００の通信範囲内に配置される。識別子は、移動装置４００が接続されるかあるいは接続するアクセスポイントと関連付けられる必要はない。例えば、特定の位置において、移動装置４００は、３個〜２０個のアクセスポイントの通信範囲内にある。移動装置４００は、アクセスポイントのうちの２つに接続できるだけでもよい（例えば、アクセスポイント及び移動装置４００のセキュリティ設定のために）。移動装置４００は、２つのアクセスポイントのうちの一方のみに能動的に接続されるか、又はいずれのアクセスポイントにも接続されない。しかし、移動装置４００が受信したアクセスポイントの全ての識別子は、計算に使用される。
【００８３】
移動装置４００は、移動装置４００の位置データベースからアクセスポイントと関連付けられた位置の集合を識別することができる（４３３）。位置の集合は、アクセスポイントと関連付けられた存在エリア４０６又は存在空間に対応する。各位置は、地理座標（例えば、緯度、経度及び高度）により示される。各位置は、アクセスポイント４０４の識別子（例えば、ＭＡＣアドレス）と関連付けられる。移動装置４００は、データベース検索を使用して位置を識別することができる。
【００８４】
移動装置４００は、集合における位置を使用して平均地理的位置を算出することができる（４３４）。平均地理的位置の算出は、集合における位置の緯度、経度及び高度の平均を算出すること、並びに算出された平均の緯度、経度及び高度における位置を平均地理的位置として指定することを含みうる。いくつかの実施例においては、平均地理的位置の算出は、集合における位置の中緯度、中経度及び中高度における位置を平均地理的位置として指定することを含む。
【００８５】
移動装置４００は、集合における位置と平均地理的位置との間の距離を算出することができる（４３６）。いくつかの実施例において、システムは、集合における各位置とユークリッド空間における平均地理的位置との間の直線距離を算出することができる。いくつかの実施例において、システムは、地球の曲率を考慮して集合における各位置と平均地理的位置との間の測地線距離を算出することができる。
【００８６】
ステップ４３６で算出された距離は、中心と関連付けられた半径として指定される。円（例えば、地理的エリア４０２を取り囲む円）の中心である中心は、ステップ４３４で算出された平均地理的位置である。円の半径は、位置の集合における位置と平均地理的位置との間の少なくとも１つの距離に基づいて判定される。いくつかの実施例において、半径は、平均地理的位置と集合に依然として存在する位置との間の最長距離に等しい。いくつかの実施例において、円が半径及び中心である平均地理的位置を使用して描画される場合、半径は、円が集合に依然として存在するある割合（例えば、８０％）の位置を含む距離である。半径は誤差の範囲を示す。その誤差の範囲を超えると、非ＧＰＳ対応移動装置の位置の推定値は、統計的に有意義である可能性が低い。
【００８７】
移動装置４００は、平均位置と位置との間の距離に基づいて集合から少なくとも１つの位置を除外することができる（４３８）。いくつかの実施例において、システムは、平均地理的位置までの距離が閾値距離を上回る位置を除外することができる。マルチパス解析の各パスにおいて、システムは、位置の集中（例えば、クラスタ）から離れると考えられる位置を除外することにより、推定された平均地理的位置の精度を向上させることができる。位置のクラスタから離れた位置は、移動装置４００の現在位置を推定するためにあまり有用ではなく、除外される。種々の実施例において、閾値距離は、１つのパスから次のパスに変動しうる。例えば閾値距離は、パスに対応する距離の集合である（例えば、第１のパスに対して５０メートル、第２のパスに対して３０メートル等）。平均地理的位置と位置との間の距離が閾値距離を上回る場合、システムは、集合から少なくとも１つの位置を除外することができる。
【００８８】
いくつかの実施例において、移動装置４００は、除外される位置の閾値割合を決定することができる。閾値割合は、予め指定された値（例えば、５％）を有することができる。各パスにおいて、移動装置４００は、平均地理的位置から遠くにある位置から、閾値割合の位置を除外することができる。
【００８９】
移動装置４００は、終了条件が満たされるまで処理４３０のステップ４３４、４３６及び４３８を繰り返すことができる。システムは、繰返しを終了するために終了条件が満たされるかを判定することができる（４４０）。いくつかの実施例において、終了条件は、繰返しの回数が閾値回数（例えば、５回）に達したときに満たされる。閾値回数は、元々受信した集合における多くの位置に関連する。閾値回数及び除外すべき位置の割合は、確実性（例えば、より広い存在エリアにより、セルにおける移動装置が実際に存在エリアに位置する信頼度が高くなる）と精度（例えば、より狭い存在エリアにより、移動装置のより正確な位置が得られる）とのバランスを微調整するように構成可能である。例えば、割合が９５％に設定され、パスの数が１０に設定される場合、最終的なパスは、全ての位置データ点の約６０％を含む円を生成することができる。
【００９０】
いくつかの実施例において、存在エリア又は存在空間が十分に狭い場合、ステップ３３０の終了条件は満たされる。アクセスポイント４０４が非常に集中する領域において、推定された現在位置は、更なるパスが精度を向上させる必要がないほど十分に狭い。円の半径が閾値半径を下回る場合、ステップ４３４、４３６及び４３８の繰返しは終了する。例えば閾値半径は、８メートル〜１０メートルである。閾値半径は、存在エリア４０６の半径に基づく。いくつかの実施例において、存在エリア４０６のいくつかの半径が十分に小さい場合、閾値半径は小さく、推定値に対する信頼度を反映する。
【００９１】
移動装置４００は、中心である平均地理的位置及び少なくとも１つの算出された距離に基づく半径を有する円を使用して移動装置４００の現在位置を指定することができる（４４２）。中心は緯度及び経度で示される。距離が３次元空間において算出されるいくつかの実施例において、中心は高度で更に示される。いくつかの実施例において、移動装置は、地図ユーザインタフェース上の表示装置に現在位置を更に表示することができる。図５を参照して、例示的な地図ユーザインタフェースを以下において説明する。
【００９２】
＜移動装置の位置を判定するためのユーザインタフェースの例＞
図５は、無線アクセスポイントの位置を使用して移動装置の位置を判定するための例示的なユーザインタフェースを示す。図５において、地理的エリアの例示的な地図５０２が移動装置５００に表示される。いくつかの実施例において、移動装置５００は、移動装置５００のタッチセンシティブディスプレイ５３０に地図５０２を表示することができる。地図５０２は、ユーザがマッピング及び位置を用いたサービスを表示するために地図オブジェクトを選択する場合に表示される。いくつかの実施例において、地図オブジェクト等のオブジェクトは、音声起動により選択される。検索バー５０４及びブックマークリストオブジェクト５０６は、地図５０２の上部に表示される。検索オブジェクト５０８、経路オブジェクト５１０、地図表示オブジェクト５１２及び現在位置オブジェクト５１４等の１つ以上の表示オブジェクトが地図の下部の下に表示される。
【００９３】
検索バー５０４は、地図上の住所又は他の位置を見つけるために使用される。例えば、ユーザが検索バー５０４に自宅の住所を入力すると、住所を含む領域が地図５０２に表示される。例えばブックマークリストオブジェクト５０６は、ユーザの自宅の住所等の頻繁に訪問する住所を含むブックマークリストを画面に表示させる。例えばブックマークリストは、現在位置（例えば、移動装置５００の現在位置）等の特殊なブックマークを更に含むことができる。
【００９４】
検索オブジェクト５０８は、検索バー５０４及び他の地図に関連した検索メニューを表示するために使用される。例えば経路オブジェクト５１０は、ユーザが出発地及び目的地を入力できるようにするメニューインタフェースを画面に表示させる。次にインタフェースは、情報（例えば、出発地から目的地までの経路の方向及び移動時間）を表示する。地図表示オブジェクト５１２は、ユーザが地図５０２に対する表示オプションを選択できるようにするメニューを画面に表示させる。例えば、地図５０２は白黒からカラーに変更され、地図の背景が変更され、あるいは、ユーザは地図の輝度を変更することができる。
【００９５】
現在位置オブジェクト５１４により、ユーザは、移動装置５００が現在配置されている場所を示す地図５０２上の地理的エリア５１６を確認できる。地理的エリア５１６は、中心が移動装置５００の通信範囲内にあるアクセスポイントと関連付けられたデータ点の平均地理的位置である推定地理的エリア（例えば、地理的エリア４０２）に対応する。地理的エリアの半径は、平均地理的位置とアクセスポイントと関連付けられた１つ以上の位置との間の距離に基づいて判定される。特殊な現在位置のブックマークは、現在位置オブジェクト５１４が選択される際にブックマークリストに置かれる。特殊な現在位置のブックマークが事前にブックマークリストに設定された場合、例えば古いブックマーク情報は、新しい現在位置情報で置換される。いくつかの実施例において、特殊な現在位置のブックマークは、地理的エリア５１６の重心と結び付けられる。すなわち、特殊な現在位置のブックマークは、地理的エリア５１６の重心に対する座標を含む。地理的エリア５１６は、移動装置５００のメモリ素子に格納された位置命令を使用して判定又は推定された位置データに基づく。例えば地理的エリア５１６は、円、長方形、正方形、六角形又は丸十字、あるいは地理的エリア５１６と地図５０２とを区別する他の何らかの特徴的な要素で示される。
【００９６】
いくつかの実施例において、地理的エリア５１６は、移動装置５００が位置すると判定又は推定される領域を含み、移動装置５００の実際の現在位置上の中心に置かれる必要はない。この例において、移動装置５００は、地理的エリア内で中心から外れて位置する。別の例において、地理的エリア５１６は、移動装置５００の推定された現在位置上の中心に置かれる。
【００９７】
現在位置オブジェクト５１４がタップ又は別の方法で選択される場合、例えば移動装置５００は、地理的エリア５１６上で地図表示を中心に置く。いくつかの実施例において、地図のズームレベルは、位置データの正確度又は精度、あるいは位置データを提供した技術、システム又はサービスに基づいて調整される。例えば、移動装置５００がより低い正確度のためにＧＰＳ信号を受信できず、位置を判定するためにアクセスポイントデータを使用する場合、地図は縮小される。移動装置５００が現在位置を判定するためにＧＰＳ位置データを使用できる場合、より高い正確度のために地図は拡大される。いくつかの実施例において、ズームレベルは、移動装置５００の速さに基づく（例えば地図は、より速い速さで縮小され、移動装置５００が移動していない場合に拡大される）。正確度又は精度と速さとの組合せが更に使用される。
【００９８】
位置情報データを検索する全ての方法が失敗し（例えば、移動装置５００があらゆるアクセスポイントの通信範囲内にない場合又は移動装置５００が接続されるあらゆるアクセスポイントと存在エリアが関連付けられないことを妥当性チェッカ３６６が判定する場合）、移動装置５００の現在位置を判定又は推定するために使用可能な他のシステム又はサービスがない場合、ユーザに対してエラーが表示され、地理的エリアが地図５０２に表示されない。例えばエラーは、失敗及び考えられる１つ又は複数の失敗の理由を通知するユーザに対するメッセージを含むことができる。
【００９９】
例えば現在位置オブジェクト５１４は、地図５０２上で地理的エリア５１６を推定及び表示することを起動するか、推定された現在位置（すなわち、地理的エリア５１６の重心）に対する経路を取得するか、移動装置５００の推定された現在位置を友人に送出するか（例えば、友人が同一の位置に行けるように）、あるいは推定された現在位置に対するブックマークを作成するために選択される。
【０１００】
＜システムアーキテクチャの例＞
図６は、図１〜図５を参照して説明する機能及び動作を実現する例示的なシステムアーキテクチャ６００を示すブロック図である。より多くの構成要素又はより少ない構成要素を有するアーキテクチャを含む他のアーキテクチャが可能である。いくつかの実施例において、アーキテクチャ６００は、１つ以上のプロセッサ６０２（例えば、デュアルコアインテルＸｅｏｎプロセッサ）、１つ以上の出力装置６０４（例えば、ＬＣＤ）、１つ以上のネットワークインタフェース６０６、１つ以上の入力装置６０８（例えば、マウス、キーボード、タッチセンシティブディスプレイ）及び１つ以上のコンピュータ可読媒体６１２（例えば、ＲＡＭ、ＲＯＭ、ＳＤＲＡＭ、ハードディスク、光ディスク、フラッシュメモリ等）を備える。これらの構成要素は、データの転送及び構成要素間の信号の制御を容易にするために種々のハードウェア及びソフトウェアを利用する１つ以上の通信チャネル６１０（例えば、バス）を介して通信及びデータを交換する。
【０１０１】
「コンピュータ可読媒体」という用語は、実行するために命令をプロセッサ６０２に提供することに関係する不揮発性媒体（例えば、光ディスク又は磁気ディスク）、揮発性媒体（例えば、メモリ）及び伝送媒体を含むがそれらに限定されないあらゆる媒体を示す。伝送媒体は、同軸ケーブル、銅線及び光ファイバを含むがそれらに限定されない。
【０１０２】
図１〜図５を参照して説明したように、コンピュータ可読媒体６１２は、オペレーティングシステム６１４（例えば、Ｍａｃ ＯＳ（登録商標）サーバ、Ｗｉｎｄｏｗｓ（登録商標）ＮＴサーバ）、ネットワーク通信モジュール６１６、データベースインタフェース６２０、データ収集モジュール６３０、データ配信モジュール６４０及び位置計算モジュール６５０を更に備える。オペレーティングシステム６１４は、マルチユーザ、マルチプロセシング、マルチタスキング、マルチリーディング、リアルタイム等である。オペレーティングシステム６１４は、装置６０６、６０８からの入力を認識し、出力を装置６０６、６０８に提供すること、コンピュータ可読媒体６１２（例えば、メモリ又は記憶装置）上でファイル及び経路を追跡し、管理すること、周辺装置を制御すること、並びに１つ以上の通信チャネル６１０上のトラフィックを管理することを含むがそれらに限定されない基本タスクを実行する。ネットワーク通信モジュール６１６は、ネットワーク接続を確立及び維持する種々の構成要素（例えば、ＴＣＰ／ＩＰ、ＨＴＴＰ等の通信プロトコルを実現するソフトウェア）を含む。データベースインタフェース６２０は、ファイルシステムに１つ以上のデータベース（例えば、データ点データベース３６０及び位置データベース３７２）に対するインタフェースを含む。データベースは、階層フォルダ構造下で編成される。フォルダは、ファイルシステムにおいて経路にマッピングする。データ収集モジュール６３０は、アクセスポイント又は他の通信チャネル（例えば、セルラネットワーク）を介してシステム６００に無線接続された多数の移動装置からデータを収集する構成要素を含む。データ配信モジュール６４０は、無線通信ネットワークのアクセスポイントと関連付けられた位置データを移動装置１０８及び１１０を含むコンピューティング装置に伝送する種々の機能を実行する。位置計算モジュール６５０は、移動装置１０８から受信した位置に対してマルチパス解析を実行する１つ以上の構成要素を含む。
【０１０３】
アーキテクチャ６００は、データベースアプリケーションプログラムをホストできるあらゆる装置に含まれる。アーキテクチャ６００は、並行処理又はピアツーピアインフラストラクチャにおいて、あるいは１つ以上のプロセッサを備える単一の装置上で実現される。ソフトウェアは、多数のソフトウェアコンポーネントを含むか、あるいはコードの単一のボディーである。
【０１０４】
説明した機能は、データ記憶システムに対してデータ及び命令を送受信するように結合された少なくとも１つのプログラム可能なプロセッサ、少なくとも１つの入力装置、並びに少なくとも１つの出力装置を備えるプログラム可能なシステム上で実行可能な１つ以上のコンピュータプログラムにおいて有利に実現される。コンピュータプログラムは、ある特定の動作を実行するかあるいはある特定の結果をもたらすためにコンピュータにおいて直接又は間接的に使用される命令の集合である。コンピュータプログラムは、コンパイル又は解釈された言語を含むあらゆる形態のプログラミング言語（例えば、オブジェクティブＣ、Ｊａｖａ（登録商標））で書かれ、スタンドアロンプログラム、あるいはモジュール、構成要素、サブルーチン、ブラウザベースのウェブアプリケーション又はコンピューティング環境において使用するのに適した他のユニットのようなものを含むあらゆる形態で展開される。
【０１０５】
命令のプログラムを実行するのに適したプロセッサは、例として、あらゆる種類のコンピュータの汎用マイクロプロセッサと専用マイクロプロセッサの双方及び単独のプロセッサ、あるいは多数のプロセッサ又はコアのうちの１つを備える。一般にプロセッサは、読み出し専用メモリ又はランダムアクセスメモリ、あるいはそれら双方から命令及びデータを受信する。コンピュータの必須要素は、命令を実行するプロセッサ、並びに命令及びデータを格納する１つ以上のメモリである。一般にコンピュータは、データファイルを格納する１つ以上の大容量記憶装置を更に備えるか、あるいはそのような装置と通信するように動作可能に結合される。そのような装置は、内部のハードディスク及び取り外し可能ディスク等の磁気ディスク、光磁気ディスク、並びに光ディスクを含む。コンピュータプログラムの命令及びデータを明白に具体化するのに適した記憶装置は、例としてＥＰＲＯＭ素子、ＥＥＰＲＯＭ素子及びフラッシュメモリ素子等の半導体メモリ素子、内部のハードディスク及び取り外し可能ディスク等の磁気ディスク、光磁気ディスク、並びにＣＤ−ＲＯＭディスク及びＤＶＤ−ＲＯＭディスクを含む全ての形態の不揮発性メモリを含む。プロセッサ及びメモリは、ＡＳＩＣ（特定用途向け集積回路）により補足されるか、あるいはＡＳＩＣに組み込まれる。
【０１０６】
ユーザとの対話を提供するために、機能は、ユーザに対して情報を表示するＣＲＴ（ブラウン管）モニタ又はＬＣＤ（液晶ディスプレイ）モニタ等の表示装置、並びにユーザがコンピュータに入力を提供するキーボード及びマウス又はトラックボール等のポインティング装置を有するコンピュータ上で実現される。
【０１０７】
機能は、データサーバ等のバックエンドコンポーネントを備えるコンピュータシステム、あるいはアプリケーションサーバ又はインターネットサーバ等のミドルウェアコンポーネントを備えるコンピュータシステム、あるいはグラフィカルユーザインタフェース又はインターネットブラウザを有するクライアントコンピュータ等のフロントエンドコンポーネントを備えるコンピュータシステム、あるいはそれらのあらゆる組合せにおいて実現される。システムのコンポーネントは、通信ネットワーク等のあらゆる形態又は媒体のデジタルデータ通信により接続される。通信ネットワークの例には、ＬＡＮ、ＷＡＮ、並びにインターネットを形成するコンピュータ及びネットワーク等が含まれる。
【０１０８】
コンピュータシステムは、クライアント及びサーバを含む。クライアント及びサーバは、一般に、互いに離れ、ネットワークを介して対話する。クライアントとサーバとの関係は、それぞれのコンピュータ上で実行し且つ互いにクライアント−サーバ関係を有するコンピュータプログラムにより生じる。
【０１０９】
＜移動装置のアーキテクチャの例＞
図７は、移動装置の例示的なアーキテクチャ７００を示すブロック図である。例えば移動装置は、ハンドヘルドコンピュータ、パーソナルデジタルアシスタント、携帯電話、電子タブレット、ネットワーク機器、カメラ、スマートフォン、ＥＧＰＲＳ（enhanced general packet radio service）移動電話、ネットワーク基地局、メディアプレーヤ、ナビゲーション装置、電子メール装置、ゲーム機、あるいはこれらのデータ処理装置又は他のデータ処理装置のうちのいずれか２つ以上の組合せである。
【０１１０】
移動装置は、メモリインタフェース７０２、１つ以上のデータプロセッサ、画像プロセッサ及び／又は中央処理装置７０４、並びに周辺インタフェース７０６を備える。メモリインタフェース７０２、１つ以上のプロセッサ７０４及び／又は周辺インタフェース７０６は、別個の構成要素であるか、あるいは１つ以上の集積回路に内蔵される。移動装置の種々の構成要素は、１つ以上の通信バス又は信号線で結合される。
【０１１１】
センサ、装置及びサブシステムは、周辺インタフェース７０６に結合され、多数の機能性を容易にする。例えば、モーションセンサ７１０、光センサ７１２及び近接センサ７１４は、周辺インタフェース７０６に結合され、移動装置の姿勢機能、照明機能及び近接機能を容易にする。位置特定プロセッサ７１５（例えば、ＧＰＳ受信機）は、周辺インタフェース７０６に接続され、無線位置測定を実行する。電磁力計７１６（例えば、集積回路チップ）は、周辺インタフェース７０６に更に接続され、磁北の方向を判定するために使用されるデータを提供する。
【０１１２】
カメラサブシステム７２０、並びに電荷結合素子（ＣＣＤ）又は相補型金属酸化物半導体（ＣＭＯＳ）光学センサ等の光学センサ７２２は、例えば写真及びビデオクリップを記録するカメラ機能を容易にするために利用される。
【０１１３】
通信機能は、無線周波数送受信機及び／又は光（例えば、赤外線）送受信機を備える１つ以上の通信サブシステム７２４により容易になる。通信サブシステム７２４の特定の設計及び実施例は、通信ネットワークに依存する。移動装置は、通信ネットワークを介して動作することを意図する。例えば移動装置は、ＧＳＭ（登録商標）ネットワーク、ＧＰＲＳネットワーク、ＥＤＧＥネットワーク、ＷｉＦｉネットワーク又はＷｉＭａｘネットワーク及びＢｌｕｅｔｏｏｔｈネットワークを介して動作するように設計された通信サブシステム７２４を含む。特に、無線通信サブシステム７２４は、装置が他の無線装置に対する基地局として構成されるようにホスティングプロトコルを含む。
【０１１４】
オーディオサブシステム７２６は、スピーカ７２８及びマイク７３０に結合され、音声認識機能、音声複製機能、デジタル記録機能及び電話機能等の音声機能を容易にする。
【０１１５】
Ｉ／Ｏサブシステム７４０は、タッチスクリーンコントローラ７４２及び／又は他の入力コントローラ７４４を備える。タッチスクリーンコントローラ７４２は、タッチスクリーン７４６又はタッチパッドに結合される。例えば、タッチスクリーン７４６及びタッチスクリーンコントローラ７４２は、容量性、抵抗性、赤外線及び表面弾性波の技術を含むがそれらに限定されない複数のタッチセンシティブ技術のうちのいずれか、並びにタッチスクリーン７４６との１つ以上の接触点を判定する他の近接センサアレイ又は他の要素を使用してそれらの接触及び動き又は中止を検出する。
【０１１６】
他の入力コントローラ７４４は、他の入力／制御装置７４８、例えば１つ以上のボタン、ロッカースイッチ、サムホイール、赤外線ポート、ＵＳＢポート及び／又はスタイラス等のポインタ装置に結合される。１つ以上のボタン（不図示）は、スピーカ７２８及び／又はマイク７３０の音量調節のためのアップ／ダウンボタンを含む。
【０１１７】
一実施例において、第１の期間中ボタンを押下することでタッチスクリーン７４６のロックを解除し、第１の期間より長い第２の期間中ボタンを押下することで移動装置の電源をｏｎ又はｏｆｆする。ユーザは、１つ以上のボタンの機能性をカスタマイズできる。例えばタッチスクリーン７４６は、仮想ボタン又はソフトボタン、並びに／あるいはキーボードを実現するために更に使用される。
【０１１８】
いくつかの実施例において、移動装置は、ＭＰ３ファイル、ＡＡＣファイル及びＭＰＥＧファイル等の記録されたオーディオファイル及び／又はビデオファイルを提示する。いくつかの実施例において、移動装置は、ｉＰｏｄ（登録商標）等のＭＰ３プレーヤの機能性を含む。従って、移動装置は、ｉＰｏｄと互換性のあるピンコネクタを含む。他の入出力装置及び制御装置も使用できる。
【０１１９】
メモリインタフェース７０２はメモリ７５０に結合される。メモリ７５０は、１つ以上の磁気ディスク記憶装置、１つ以上の光記憶装置及び／又はフラッシュメモリ（例えば、ＮＡＮＤ、ＮＯＲ）等の高速ランダムアクセスメモリ及び／又は不揮発性メモリを含む。メモリ７５０は、Ｄａｒｗｉｎ、ＲＴＸＣ、ＬＩＮＵＸ（登録商標）、ＵＮＩＸ（登録商標）、ＯＳ Ｘ、ＷＩＮＤＯＷＳ（登録商標）等のオペレーティングシステム７５２又はＶｘＷｏｒｋｓ等の組み込みオペレーティングシステムを格納する。オペレーティングシステム７５２は、基本システムサービスを処理する命令及びハードウェア依存タスクを実行する命令を含む。いくつかの実施例において、オペレーティングシステム７５２はカーネル（例えば、ＵＮＩＸカーネル）を含む。
【０１２０】
メモリ７５０は、通信命令７５４を更に格納し、１つ以上の追加装置、１つ以上のコンピュータ及び／又は１つ以上のサーバとの通信を容易にする。メモリ７５０は、グラフィックユーザインタフェース処理を容易にするためのグラフィカルユーザインタフェース命令７５６、センサに関連する処理及び機能を容易にするためのセンサ処理命令７５８、電話に関連する処理及び機能を容易にするための電話命令７６０、電子メッセージングに関連する処理及び機能を容易にするための電子メッセージング命令７６２、ウェブ閲覧に関連する処理及び機能を容易にするためのウェブ閲覧命令７６４、メディア処理に関連する処理及び機能を容易にするためのメディア処理命令７６６、ＧＰＳ及びナビゲーションに関連する処理及び機能を容易にするためのＧＰＳ／ナビゲーション命令７６８、カメラに関連する処理及び機能を容易にするためのカメラ命令７７０、磁力計の校正を容易にするための磁力計データ７７２及び校正命令７７４を含む。メモリ７５０は、現在位置をアクセスポイントに伝送し、移動装置が通信範囲内にあるアクセスポイントと関連付けられた位置データに基づいて推定された現在位置を判定するために使用される位置命令７７６を含む。メモリ７５０は、セキュリティ命令等の他のソフトウェア命令（不図示）、ウェブビデオに関連する処理及び機能を容易にするためのウェブビデオ命令、並びに／あるいはウェブショッピングに関連する処理及び機能を容易にするためのウェブショッピング命令を更に格納する。いくつかの実施例において、メディア処理命令７６６は、それぞれ、オーディオ処理に関連する処理及び機能を容易にするためのオーディ処理命令、並びにビデオ処理に関連する処理及び機能を容易にするためのビデオ処理命令に分類される。活性化レコード及び国際移動体装置識別番号（ＩＭＥＩ）等のハードウェア識別子は、メモリ７５０に更に格納される。
【０１２１】
先に識別された命令及びアプリケーションの各々は、上述の１つ以上の機能を実行する命令の集合に対応する。これらの命令は、別個のソフトウェアのプログラム、手順又はモジュールとして実現される必要はない。メモリ７５０は、更なる命令又はより少ない命令を含む。また、移動装置の種々の機能は、１つ以上の信号処理回路及び／又は特定用途向け集積回路を含むハードウェア及び／又はソフトウェアで実現される。
【０１２２】
本発明の種々の実施例を説明したが、本発明の主旨の範囲から逸脱することなしに種々の変形を行うことができることは理解されよう。例えば、位置認識装置はＧＰＳ対応と呼ばれる。また、位置認識移動装置は、三角法又は他の技術に基づくことができる。図面においては、セルは略矩形形状で示されたが、セルの実際の形状は変動しうる。位置は「円」で示されたが、本明細書において使用された「円」という用語は、完全に円形である必要はなく、閉じられているかあるいはエンクロージャの外形を有するあらゆる幾何学的形状（例えば、楕円、正方形、凸多角形又は凹多角形、あるいは自由型形状）を含む。完全に円形ではない幾何学的形状の半径は、幾何学的形状の境界上の種々の点と幾何学的形状の中心との間の平均距離を含む。ＷｉＦｉ、ＷｉＭａｘネットワークは、例として使用したものであり、他の無線技術（例えば、セルラネットワーク）を使用してもよい。従って、他の実施例も、以下の特許請求の範囲の範疇に含まれる。
【技術分野】
【０００１】
本発明は、一般には、移動装置の地理的位置を特定する技術に関する。
【背景技術】
【０００２】
無線通信ネットワークは、装置が無線通信するために種々の技術を採用することができる。例えば無線ローカルエリアネットワーク（ＷＬＡＮ）は、ネットワークの複数のノード（例えば、複数の装置）間の通信のために、有線ではなく無線を使用するローカルエリアネットワーク（例えば、家、会社又は学校等の小規模な建物の集まり等の相対的に狭い物理的領域を範囲に含むコンピュータネットワーク）を含むことができる。ＷＬＡＮ技術のいくつかの例には、あらゆる米国電気電子学会（ＩＥＥＥ）８０２．１１規格に基づくあらゆるＷＬＡＮ製品を含むＷｉＦｉが含まれる。
【０００３】
送信側と受信側との間の無線接続は、無線周波数（ＲＦ）技術、電波伝搬と関連付けられた電磁スペクトル内の周波数を採用することができる。ＷｉＦｉにおいて使用される無線周波数は例えば、２．５ギガヘルツ（ＧＨｚ）又は５ＧＨｚである。アンテナにＲＦ電流が供給されると電磁場が生成される。電磁場は空間を伝播する。無線通信ネットワークの構成要素にアクセスポイント（ＡＰ）がある。アクセスポイントにより、無線移動装置は有線ネットワークと通信できる。アクセスポイントの１つの機能は、無線アダプタ又は無線移動装置を搭載したコンピュータが検出及び「同調」する無線信号をブロードキャストすることである。
【０００４】
ＷｉＦｉネットワークのアクセスポイントは、アクセスポイントにより送受信される信号の強度及び地理的エリア地理的エリアその地理的エリアの物理的特性により決定される地理的エリアをカバーすることができる。変化しうる数の移動装置がアクセスポイントの通信範囲内に位置しうる。移動装置は、同時に複数のアクセスポイントの通信範囲内に位置しうる。アクセスポイントの位置が既知である場合、移動装置は、アクセスポイントから受信した信号の強度に基づいて位置を三角法で測定することにより、移動装置が通信するアクセスポイントの位置を使用して位置を判定することもできる。
【発明の概要】
【０００５】
ネットワークベースのポジショニングシステムの位置データベースを管理する方法、プログラム及びシステムを記載する。サーバコンピュータは、無線通信ネットワークのアクセスポイントの通信範囲内に配置された位置認識移動装置（例えば、ＧＰＳ対応装置）から位置情報を受信することができる。サーバコンピュータは、アクセスポイント毎に受信した位置を使用して平均地理的位置を算出することができる。平均地理的位置に基づいて、サーバコンピュータは、アクセスポイントを地理グリッドのセルに割り当てることができる。サーバコンピュータは、アクセスポイント及び受信したデータのポピュラリティ、スタビリティ、ロンジェビティ、並びにフレッシュネスに基づいて、各セルにおけるアクセスポイントをフィルタリングすることができる。サーバコンピュータは、平均地理的位置と関連付けてアクセスポイントの識別子を位置データベースに格納することができる。
【０００６】
移動装置は、移動装置が接続するアクセスポイントの位置を使用して位置を判定することができる。移動装置は、地理グリッド上のセルにおけるアクセスポイントに接続すると、アクセスポイントの位置情報、セルにおける他のアクセスポイントの位置及びセルに隣接するセルにおけるアクセスポイントの位置を要求して受信することができる。移動装置は、移動装置の通信範囲内でアクセスポイントに関連付けられた受信した情報から位置を識別することができる。移動装置は、識別した位置を使用して平均地理的位置を算出することができる。移動装置は、各位置と算出された平均地理的位置との間の距離を更に算出することができる。移動装置は、平均地理的位置から十分に離れた位置を除外することができる。移動装置は、平均地理的位置に対してある精度レベルが達成されるまで計算と除外を繰り返すことができる。移動装置は、移動装置の地図ディスプレイに情報を表示することができる。
【０００７】
ネットワークベースのポジショニングシステムの位置データベースを管理する技術は、以下の例示的な利点を達成するように実現される。アクセスポイントの実際の位置が未知である場合、地理的エリアは、無線通信ネットワークのアクセスポイントに関連付けられる。地理的エリアは、アクセスポイントの実際の位置ではなく、アクセスポイントの通信範囲内に位置する実際の移動装置が位置する可能性が高い領域に対応する。地理的エリアは、頻繁に更新されるために最新の位置情報を提供する移動装置からの実際の時間データに基づいて推定される。アクセスポイントは、遠ざかっているかあるいは遮断される場合、不正な位置判定を回避するためにデータベースから削除される。地理的エリアは、一日の異なる時間において移動装置から受信したデータに基づいて算出されるよう、通勤時間、勤務時間又は夜間等の種々の使用パターンに対応する。
【０００８】
地理的エリアに関連付けられたアクセスポイントは、アクセスポイントの通信範囲内に位置する非ＧＰＳ対応移動装置の位置を判定するために使用される。移動装置とアクセスポイントとの間の通常の通信に対する干渉を回避するために、アクセスポイントと移動装置とのデータ伝送は、移動装置がアイドル状態の時に行われる。アクセスポイントの位置を使用して移動装置の位置を判定するシステムは、直接移動装置の通信範囲内にあるアクセスポイントの位置及び隣接領域におけるアクセスポイントの位置を伝送するため、移動装置の帯域幅の消費を自律的に制限することができる。従って、移動装置が移動する場合でも頻繁に更新及び再伝送する必要はない。各セルにおけるアクセスポイントのフィルタリング機構は、各伝送において移動装置に伝送されたデータの量を更に制限することができる。信号強度が種々の干渉により変動するため、移動装置は、例えば位置を推定するために信号強度を使用するより正確に位置を推定できる。例えばＧＰＳ信号が弱い（例えば、建物内部）場合、ＧＰＳ対応移動装置は、無線アクセスポイントの位置を利用することが可能である。
【０００９】
以下の添付の図面及び明細書において、ネットワークベースのポジショニングシステムの位置データベースを管理する１つ以上の実施例の詳細を説明する。位置データベース管理の他の特徴、態様及び利点は、明細書、図面及び特許請求の範囲から明らかとなるだろう。
【図面の簡単な説明】
【００１０】
【図１Ａ】位置データベースを管理する技術を示す概略図。
【図１Ｂ】３次元空間において位置データベースを管理する技術を示す図。
【図２Ａ】、
【図２Ｂ】、
【図２Ｃ】移動装置を使用してＷＬＡＮのアクセスポイントと関連付けられた位置を判定する処理の例を説明する図。
【図２Ｄ】３次元空間において移動装置を使用してＷＬＡＮのアクセスポイントと関連付けられた位置を判定する処理の例を説明する図。
【図３Ａ】、
【図３Ｂ】移動装置を使用してＷＬＡＮのアクセスポイントと関連付けられた位置を判定する処理の例を示すフローチャート。
【図３Ｃ】位置データベースを管理する技術を実現する例示的なシステムを示すブロック図。
【図４Ａ】ネットワークベースのポジショニングシステムにおいて位置データベースを使用して移動装置の位置を判定する技術を示す図。
【図４Ｂ】位置データベースを使用して移動装置の位置を判定する例示的な処理を示すフローチャート。
【図４Ｃ】移動装置の位置を判定する例示的な適応マルチパス処理を示すフローチャート。
【図５】無線アクセスポイントの位置を使用して移動装置の位置を判定する例示的なユーザインタフェースを示す図。
【図６】図１〜図５を参照して説明する機能及び動作を実現する例示的なシステムアーキテクチャを示すブロック図。
【図７】移動装置の例示的なアーキテクチャを示すブロック図。
【００１１】
各図面において、同一の参照符号は同一の構成要素を示すものとする。
【発明を実施するための形態】
【００１２】
＜位置データベース管理の概要＞
図１Ａは、ネットワークベースのポジショニングシステム用位置データベースを管理する技術を示す概略図である。無線ローカルエリアネットワーク（ＷＬＡＮ）は、多くのアクセスポイント１０５を含む無線通信ネットワークである。アクセスポイント１０５は、無線装置が有線ネットワークに接続するための通信ハブとして動作するハードワイヤ装置又はコンピュータソフトウェアを含みうる。多数のアクセスポイント１０５が、領域（例えば、オフィスビル又は空港）内に配置されうる。
【００１３】
アクセスポイント１０５は、種々の通信プロトコルを使用して無線装置（例えば、移動装置１０８及び１１０）と通信することができる。いくつかの実施例において、アクセスポイント１０５は、米国電気電子学会（ＩＥＥＥ）８０２．１１ベースのプロトコル（例えば、ＩＥＥＥ８０２．１１ａ）を実現するＷｉＦｉ（登録商標）ネットワークのアクセスポイントである。いくつかの実施例において、アクセスポイント１０５は、ＩＥＥＥ８０２．１６ベースのプロトコル（例えば、ＩＥＥＥ８０２．１６−２００４又はＩＥＥＥ８０２．１６ｅ−２００５）を実現するＷｉＭＡＸ（ｗｏｒｌｄｗｉｄｅ ｉｎｔｅｒｏｐｅｒａｂｉｌｉｔｙ ｆｏｒ ｍｉｃｒｏｗａｖｅ ａｃｃｅｓｓ）ネットワークのアクセスポイントである。アクセスポイント１０５は、アクセスポイント１０５の設定及び物理的な環境を含む要因に依存して、アクセスポイント１０５の位置から１０メートル乃至数百メートル内のあらゆる場所に及ぶ通信範囲を有することができる。複数の移動装置１０８及び１１０がアクセスポイント１０５の通信範囲内にある場合、それら複数の移動装置１０８及び１１０はアクセスポイントに接続することができる。さらに、複数のアクセスポイント１０５が、接続のために単一の移動装置１０８又は１１０によって使用されることも可能である。移動装置１０８及び１１０は、自身が種々の要因に基づいて接続する特定のアクセスポイント１０５を選択することができる。例えば選択は、移動装置１０８がアクセスポイント１０５ａに接続する許可を受けているか、あるいはアクセスポイント１０５ａが無線接続に対して最強の信号を移動装置１０８に提供するかに基づく。
【００１４】
システムは、アクセスポイント１０５に関連付けられる位置領域１１５を判定することができる。位置領域１１５は、アクセスポイント１０５の通信範囲内に配置された移動装置１０８が位置する可能性が高い場所を示すように算出される。システムは、アクセスポイント１０５の通信範囲内に位置する移動装置１０８から既知の位置に基づいて判定を行う。移動装置１０８は、グローバル・ポジショニング・システム（ＧＰＳ）信号を受信し、ＧＰＳ信号を使用して位置を判定する受信機に内蔵されているかあるいは受信機と結合されるＧＰＳ対応移動装置等の位置認識移動装置でありうる。位置認識移動装置１０８は、図１Ａにおいて黒色の三角形として示される。位置認識移動装置１０８は、特定のアクセスポイント１０５（例えば、アクセスポイント１０５ａ）の通信範囲内に位置する場合、装置の位置をアクセスポイント１０５ａに伝送する。アクセスポイント１０５ａは、伝送及びアクセスポイント１０５ａの識別子をシステムに中継する。システムは、アクセスポイント１０５ａの通信範囲内に位置する移動装置１０８又は１１０のいずれかが位置する可能性が最も高い推定位置エリア１１５ａを判定することができる。本明細書において、推定位置エリア１１５は存在エリア（presence area）と呼ばれ、移動装置１０８又は１１０が特定のアクセスポイント１０５の通信範囲内に位置する場合に存在する可能性が高いことを示す。
【００１５】
システムは、存在エリア１１５を算出するために反復処理を適用することができる（例えば、マルチパス解析を実行することで）。反復処理は、円としてアクセスポイント（例えば、アクセスポイント１０５）と関連付けられる存在エリア（例えば、存在エリア１１５）を判定する。円の中心は、アクセスポイント１０５に接続された位置認識移動装置１０８の各位置に基づいて算出された平均地理的位置に対応する。円の半径は、例えば移動装置１０８の位置と平均地理的位置との間の距離等により判定される誤差範囲に対応する。図２及び図３を参照して、反復処理に関する更なる詳細を以下において説明する。反復処理は、一日の異なる時間の間の種々の無線アクセス使用パターン及び潜在的なアクセスポイント１０５の移動を入手するために定期的に（例えば、６時間毎に）実行される。
【００１６】
受信移動装置が存在エリア１１５を使用して装置の推定位置を判定できるように、システムは、アクセスポイント１０５の通信範囲内に位置する非ＧＰＳ対応移動装置（例えば、移動装置１１０）を含む移動装置に存在エリア１１５の情報を送出することができる。例えば、移動装置１１０がアクセスポイント１０５ｂの通信範囲内に位置する場合、移動装置１１０の位置は、アクセスポイント１０５ｂと関連付けられる存在エリア１１５ｂと一致するものと推定される。
【００１７】
所定の領域（例えば、空港）においては、多くのアクセスポイント１０５が存在する場合がある。また、移動装置１１０はモバイルであるため、移動装置１１０が動きを追跡するために位置を使用できるように、即座に移動装置１１０の通信範囲内にはないが移動装置１１０に十分に近接するアクセスポイントの位置を送出することは理にかなっている。大量の位置データが移動装置１１０に送出されることを回避するため、システムは、世界に存在する全てのアクセスポイントの位置データではなく、限られた数のアクセスポイント（例えば、アクセスポイント１０５ａ）の位置データのみを伝送するように、アクセスポイント１０５及び位置領域１１５をフィルタリングすることができる。フィルタリングは、位置１１５及びアクセスポイント１０５のポピュラリティ（popularity）、スタビリティ（stability）、ロンジェビティ（longevity）、フレッシュネス（freshness）を含む種々の要因に基づくことができる。
【００１８】
システムは、位置１１５及びアクセスポイント１０５をフィルタリングするために、セル１０２を含む地理グリッド１００を作成することができる。セル１０２は、略矩形形状を有する多角形である。多角形は、地理的エリアの識別点（例えば、中心又は隅）の緯度及び経度、並びに大きさ（例えば、経度の尺度で測定された長さ及び緯度の尺度で測定された幅）により地理グリッド１００上で識別可能な地理的エリアに対応する。各セル１０２は、ある特定の数の位置を含むコンテナとして使用される。例えばセル１０２は、長さが経線０．０００５度（約５６メートル）及び幅が緯度０．０００５度（メートル単位の幅は緯度に依存して変動する）の矩形である。セル１０２は、アクセスポイント１０５に対応する数（例えば、３つ）の存在エリア１１５を保持するように構成される。いくつかの実施例において、存在エリア１１５の中心がセル１０２の境界内に配置される場合、セル１０２は存在エリア１１５を「保持する」。存在エリア１１５は、１つ以上の信頼性要因に基づいてセル１０２に配置される全ての存在エリア１１５から選択される。選択は、ポピュラリティ、スタビリティ、ロンジェビティ、フレッシュネス等の種々の基準に基づくことができる。
【００１９】
特定のアクセスポイント（例えば、アクセスポイント１０５ｂ）及びアクセスポイントに関連付けられた存在エリア（例えば、存在エリア１１５ｂ）は、同一のセル１０２に配置される必要はない。例えば、アクセスポイント１０５ｂがセル１０２ａの建物に配置され、アクセスポイント１０５ｂの通信範囲内に配置された殆どの移動装置１０８がセル１０２ｂの別の建物に位置する場合、このようなことが起こりうる。いくつかの実施例において、システムは、アクセスポイント１０５ｂの実際の位置を無視することができる。
【００２０】
移動装置１１０は、アクセスポイント（例えば、関連付けられた存在エリア１１５ａがセル１０２ｃに配置されるアクセスポイント１０５ａ）に接続するか、あるいは他の方法で（例えば、セルラネットワークを介して）システムに接続される場合、システムから位置更新を受信することができる。位置更新は、存在エリア１１５ａが配置される同一のセル（例えば、セル１０２ｃ）に配置される全ての存在エリア１１５を含むことができる。位置更新は、地理グリッド１００上のセル１０２ｃに隣接する他のセル１０２（例えば、セル１０２ａ及びセル１０２ｂ）に配置される存在エリア１１５を更に含むことができる。
【００２１】
移動装置１１０は、アクセスポイント１０５ａに接続する場合、使用可能な他のアクセスポイント１０５（例えば、アクセスポイント１０５ｂ）を検出することができる。移動装置１１０は、使用可能なアクセスポイントに対する存在エリア（例えば、存在エリア１１５ａ及び１１５ｂ）を識別することができる。移動装置１１０は、種々のアルゴリズムを使用して移動装置１１０の現在位置を算出することができる。例えば、１つの存在エリア１１５ａのみが識別される場合、移動装置１１０は、存在エリア１１５ａを移動装置１１０の現在位置として指定する。２つ以上の存在エリア１１５が識別される場合、移動装置１１０は、反復処理（例えば、マルチパス解析）を使用して現在位置を算出する。反復処理は、存在エリアの平均位置及び存在エリアと平均位置との間の距離を算出し、平均位置から最も遠く離れた存在エリアを除外する。移動装置１１０の位置を判定するために必要な精度が満たされるまで、移動装置１１０は反復処理を繰り返す。移動装置１１０は、平均位置を移動装置１１０の現在位置として指定し、地図表示装置に平均位置を表示する。
【００２２】
いくつかの実施例において、存在エリア１１５ａの周囲の十分に広い領域（例えば、１又は２平方キロメートル）をカバーできるよう、システムから移動装置１１０上で受信した位置更新には、多くの隣接するセルを含めることができる。広い領域をカバーする位置更新に基づいて、移動装置１１０は、自身が移動する場合に頻繁に更新を要求しなければならないことを回避することができる。移動装置１１０は、例えばアイドル状態であるかあるいは使用可能な通信帯域幅を有する場合、更新された存在エリア情報を受信する機会を有する。
【００２３】
図１Ｂは、３次元空間において位置データベースを管理することを示す。いくつかの位置認識移動装置１０８（例えば、ＧＰＳ対応装置）は、３次元空間において位置を識別することができる。位置は、緯度、経度及び高度により示される。例えば高度は、海面からメートル単位で測定された海抜として示される。移動装置の高度が移動装置を配置するために必要な場合、移動装置を３次元空間に配置することが望ましい。例えば高度は、移動装置が位置する高層ビルの階を判定するために使用される。３次元空間における移動装置１０８の位置は、注釈として海抜を含む２次元地図又は３次元地図に表示される。
【００２４】
移動装置１０８はアクセスポイント１２６に接続することができる。移動装置１０８は、緯度座標、経度座標及び高度座標を含む位置をシステムに伝送する位置認識移動装置でありうる。システムは、移動装置１０８から受信した緯度座標、経度座標及び高度座標に基づいて平均位置を算出する。中心である平均位置を有し且つ半径である誤差範囲を有する３次元空間１２４が、アクセスポイント１２６と関連付けられる。空間１２４は、移動装置がアクセスポイント１２６の通信範囲内に位置する場合に位置する可能性が高い空間であることを表している。本明細書において、空間１２４を存在空間と呼ぶ。
【００２５】
システムは、存在空間１２４に関する情報をアクセスポイント１２６の通信範囲内に位置する移動装置に送出することができる。情報を受信する移動装置は、地理的位置を判定するために情報を使用することができる。システムは、３次元地理空間を３次元グリッド１２０に分割することができる。３次元グリッド１２０は３次元セル１２２から構成される。各３次元セル１２２は、地理グリッド１００のセル１０２に対応するベースを有する。各３次元セル１２２は、１つの次元として高さ（例えば、メートル単位で測定された）を有する。存在空間１２４の中心がセル１２２にある場合、存在空間１２４は、セル１２２に配置されているものとして示される。システムは、存在空間のポピュラリティ（例えば、存在空間における移動装置１０８からアクセスポイント１２６に接続された回数）、存在空間１２４のスタビリティ（例えば、存在空間１２４がどれだけ安定しているか）、アクセスポイント１２６のロンジェビティ（例えば、アクセスポイント１２６が存在している期間）、及び、存在空間１２４のフレッシュネス（例えば、アクセスポイント１２６の通信範囲内に位置する移動装置１０８から最新の位置伝送が受信された時）に基づいてセル１２２における存在空間の数を制限することができる。
【００２６】
システムは、３次元グリッド１２０の３次元セル１２２に基づく存在空間１２４及び隣接する存在空間に関する情報をアクセスポイント１２６の通信範囲内に位置する移動装置（例えば、移動装置１１０）に伝送する。移動装置１１０は、３次元空間において移動装置１１０の現在位置を推定するために情報を使用し、推定された現在位置を３次元地図に表示する。
【００２７】
＜サーバ側処理及び位置データベースを管理するシステムの例＞
図２Ａ〜図２Ｃは、位置データベースを管理する処理の例を示す。便宜上、技術を実現するサーバを備えるネットワークベースのポジショニングシステムを参照して技術を説明する。
【００２８】
図２Ａは、アクセスポイント１０５と関連付けられた存在エリアを判定するために使用されるマルチパス解析の例示的な処理を示す。アクセスポイント１０５は、アクセスポイント１０５の送信機の信号強度及び他の要因（例えば、アクセスポイント１０５を取り囲む地理的エリアの物理的特性）により判定されるサービスエリア２０２を有する。サービスエリア２０２内に位置する移動装置１０８は、アクセスポイント１０５に無線接続する。アクセスポイント１０５により、移動装置１０８は、種々のゲートウェイを介して有線ネットワークに接続できる。有線ネットワークは、データネットワーク（例えば、インターネット）、公衆交換電話網（ＰＳＴＮ）、他のデジタルネットワーク又はアナログネットワーク、あるいはそれらの組合せを含む。
【００２９】
移動装置１０８は、位置認識移動装置（例えば、ＧＰＳ対応移動装置）を含みうる。各位置認識移動装置１０８（図２Ａの黒色の三角形として示される）は、現在の地理的位置を検出することができる。現在の地理的位置は、移動装置１０８の緯度及び経度を含む地理座標により示される。移動装置１０８は、アクセスポイント１０５と通信する場合、アクセスポイント１０５を介して位置情報をシステムに伝送することができる。位置情報は、アクセスポイント１０５の識別子（例えば、アクセスポイント１０５のメディアアクセス制御（ＭＡＣ）アドレス）に関連付けられる。システムは、複数の移動装置１０８から受信した位置情報を使用して、アクセスポイント１０５に関連付けられる存在エリアを判定することができる。存在エリアは、アクセスポイント１００が実際に配置される位置を取り囲む必要はない。存在エリアは、サービスエリア２０２内に配置されないが、サービスエリア２０２の幾何学的な位置又は形状に対応する必要もない。
【００３０】
サービスエリア２０２内で移動装置１０８を分布させることは、特定の時間（例えば、アクセスポイント１０５が配置されるタイムゾーンに対する現地時間午前８：３０）における移動装置１０８のスナップショットに対応する。各移動装置１０８は、単一の位置に関連付けられる。サービスエリア２０２内で移動装置１０８を分布させることは、ある期間（例えば、午前４時〜午前１０時の６時間）にわたる移動装置１０８の位置に更に対応する。各移動装置１０８は、複数の位置に関連付けられる（例えば、移動装置１０８が移動している場合）。図２Ａにおいて複数の三角形で示されるように、複数の位置に関連付けられる単一の移動装置１０８は、システムにおいて複数の位置で示される。
【００３１】
サーバは、移動装置１０８から受信した位置の集合の平均地理的位置を判定することができる。位置の集合は、特定の時間において又は特定の期間中に移動装置１０８から受信した位置を含む。平均地理的位置は、円２０４ａが含む領域の中心２０５として指定される。円２０４ａの中心は、アクセスポイント１０５の位置と一致する必要はない。サーバは、平均地理的位置と集合における各位置との間の距離を算出し、１つ以上の外れ値を識別することができる。外れ値は、平均地理的位置から最も遠くに配置される集合における位置である。中心までの距離が閾値を上回る外れ値（例えば、位置２１０）は、集合から除外される。外れ値が除外された後、円２０４ａは、平均地理的位置と現在の集合における位置との間の最長の距離に対応する半径２０６を有する。
【００３２】
図２Ｂは、図２Ａの処理に後続するマルチパス解析の処理の例を示す。図２Ａの平均地理的位置（円２０４ａの中心２０５）までの距離が閾値を上回る位置は、集合から除外されている。閾値は、位置の割合（例えば、図２Ａの位置の５％）が除外されるように構成される。新しい平均地理的位置は、集合に依然として存在するある割合（例えば、依然として存在する位置の９５％）の位置に基づいて算出される。例えば、新しい平均地理的位置は円２０４ｂの中心２１５である。種々の実施例において、新しい平均地理的位置を算出することは、集合における残りの位置を平均化すること、集合における中間地理的位置を選択すること（例えば、中緯度又は中経度を選択することにより）、あるいは他のアルゴリズムを適用することを含む。平均地理的位置を算出するアルゴリズムは、マルチパス解析の各パスにおいて同一であるか、あるいは各パスにおいて互いに異なる。
【００３３】
外れ値の位置が除外される場合、円２０４ｂに含まれた領域は、前のパスにおいて判定されたような円２０４ａが含む領域より狭い。より狭い領域は、向上した計算の精度を反映する。円２０４ｂの中心２１５は、円２０４ａの中心２０５と一致する必要はない。いくつかの実施例において、円２０４ｂの半径２１６は、円２０４ｂの中心２２５から最も遠く離れた移動装置１０８の残りの位置に対応する。半径２１６は、存在エリアが現在のパスにおいて算出した新しい推定位置の誤差範囲を示す。
【００３４】
図２Ｃは、マルチパス解析の最終処理の例を示す。ある特定の終了条件を満たす場合、システムは、最終処理後に反復処理を終了する。最終処理は、移動装置１０８の位置のクラスタに対応する最終的な平均地理的位置を生成する。最終的な平均地理的位置は、円２０４ｃの中心２３５として示される。円２０４ｃは、最終的な平均地理的位置とクラスタの位置との間の距離に基づいて最終的な誤差範囲に対応する半径を有する。円２０４ｃは、アクセスポイント１０５と関連付けられた存在エリア及びアクセスポイント１０５の識別子（例えば、ＭＡＣアドレス）として指定される。
【００３５】
サーバは、種々の要因に基づいてアクセスポイント１０５の識別子及び関連付けられた存在エリアを位置データベースに含むかを判定することができる。例えばサーバは、地理グリッド１００のセル１０２における存在エリアの数をカウントし、ポピュラリティ、スタビリティ及びロンジェビティに基づいて存在エリアの数を選択することができる。移動装置１０８がＧＰＳ対応装置であるかに関係なく、サーバは、位置データベースにおける存在エリア（存在エリア２０４ｃが選択される場合に存在エリア２０４ｃを含む）の情報を移動装置（例えば、移動装置１０８）に送出することができる。
【００３６】
図２Ｄは、３次元空間において位置データベースを管理する例示的な処理を示す。図２Ｄにおいて、軸Ｘ、Ｙ及びＺは、３次元空間を示すために使用される。例えば、軸Ｘ、Ｙ及びＺは、それぞれ、経度、緯度及び高度を示す。便宜上、アクセスポイント１２６の位置は、図２ＤにおいてＸ軸、Ｙ軸及びＺ軸上で原点と一致するように示される。いくつかの実施例において、アクセスポイント１２６の実際の位置（例えば、緯度座標、経度座標及び高度座標）の計算は必須でない。
【００３７】
図２Ｄの各三角形は、３次元空間に配置された移動装置の位置を示す。位置は、３次元空間において平面に投影（例えば、投影２２６）を有する。平面は、任意の緯度（例えば、アクセスポイント１２６の緯度）において規定される。例えば平面は、軸Ｘ及びＹにより規定される。アクセスポイント１２６は、アクセスポイント１２６の信号強度及び他の制限要因（例えば、信号路における階、天井、建物）により判定されるサービスエリア空間２２２に対応する。
【００３８】
マルチパス解析は、セル空間２０２に位置する位置認識移動装置１０８から受信した位置の集合に基づくＷＬＡＮのアクセスポイント１２６と地理空間を関連付ける。マルチパス解析のパスにおいて、平均地理的位置（例えば、空間２２４の中心）は、例えば集合における位置の緯度座標、経度座標及び高度座標を平均化することで判定される。サービスエリア空間２２２における平均地理的位置と位置との間の距離が算出される。サービスエリア空間２２２内にあるが平均地理的位置から十分に遠く離れた位置は、集合及び更なる計算から除外される。空間２２４の半径は、例えば集合における残りの位置と平均地理的位置との間の最も遠い距離で判定される。
【００３９】
システムは、集合における平均地理的位置を算出するステップ、平均地理的位置と集合における位置との間の距離を算出するステップ、及び算出された距離に基づいて集合から位置を除外するステップを繰り返す。終了条件が満たされるまで繰返しは継続する。平均地理的位置における中心及び平均地理的位置と集合における残りの位置との間の距離に基づく半径を有する空間は、アクセスポイント１２６と関連付けられる存在空間として指定される。
【００４０】
図３Ａは、位置データベースを管理する例示的な処理３００を示すフローチャートである。処理３００は、例えばＷＬＡＮのアクセスポイントと関連付けられた存在エリア又は存在空間を判定するために使用される。存在エリア又は存在空間は、非ＧＰＳ対応移動装置の位置を判定するために使用される。便宜上、処理３００を実現するシステムを参照して処理３００を説明する。
【００４１】
システムは、アクセスポイント１０５の通信範囲内に位置する１つ以上の第１の移動装置１０８から位置の集合を受信する（３０２）。各位置は、地理座標（例えば、緯度、経度及び高度）の集合により示される。位置は、アクセスポイント１０５の識別子（例えば、ＭＡＣアドレス）と関連付けられる。アクセスポイント１０５がシステムと通信する場合、アクセスポイントの識別子は、アクセスポイント１０５により自動的に供給される。種々の実施例において、位置の集合は、ある期間（例えば、６時間又はアクセスポイント１０５が配置されるタイムゾーンの午前６時〜午前１０時）に対応する。
【００４２】
いくつかの実施例において、ある期間は、一日の異なる時間における特定の使用パターンの特性を反映するように構成される。アクセスポイント１０５の通信範囲内に移動装置が位置する可能性が最も高い領域は、一日の間に変動し、特定の時間における種々の使用パターンを示す。例えばある期間は、「通勤時間」、「勤務時間」、「夜間」等に対応する。一日の時間の特性は、移動装置１０８の種々の使用パターンに対応する。例えば、アクセスポイント１０５と関連付けられた存在エリアは、通勤時間中は高速道路又はその周辺にあり、勤務時間中はオフィスビル又はその周辺にあり、夜間は特に集中点はなく拡散する。システムは、例えば午前４時〜午前１０時に受信した位置に基づいて存在エリアを算出し、例えば午前１０時〜午後４時に受信した位置に基づいて存在エリアを算出し直す。特徴的な期間の各々において受信した位置は、システムにおいて集合にグループ化される。位置は、サーバに結合された記憶装置上であらゆるデータ構造（例えば、リレーショナルデータベースにおける集合、リスト、アレイ、データレコード等）で格納される。
【００４３】
システムは、受信した位置の集合の平均に基づいてアクセスポイント１０５と関連付けられた地理的位置を判定することができる（３０４）。地理的位置は、上述したような存在エリア又は存在空間を含む。存在エリア又は存在空間は、例えばアクセスポイント１０５のＭＡＣアドレスによりアクセスポイント１０５と関連付けられる。いくつかの実施例において、地理的位置を判定することは、各パスにおいて集合から少なくとも１つの位置を除外することを含む受信した位置の集合に対してマルチパスアルゴリズムを適用することを含む。地理的位置を判定することは、定期的にマルチパスアルゴリズムを適用することを含む。
【００４４】
システムは、アクセスポイント１０５のポピュラリティ、地理的位置のスタビリティ及びアクセスポイント１０５のロンジェビティを含む種々の要因に基づいてアクセスポイント１０５及びアクセスポイント１０５と関連付けられた地理的位置を地理グリッド（例えば、地理グリッド１００）上のセル（例えば、セル１０２）に割り当てることができる（３０６）。いくつかの実施例において、アクセスポイント１０５のポピュラリティによって、アクセスポイント１０５の通信範囲内に位置する移動装置１０８の数を測定することができる。アクセスポイントのポピュラリティは、例えばアクセスポイント１０５の通信範囲内に存在する移動装置１０８の位置がある期間においてシステムにより受信される数により測定される。
【００４５】
存在エリアがアクセスポイント１０５の通信範囲内に配置された装置の位置を推定するために使用される場合、アクセスポイント１０５と関連付けられた存在エリアのスタビリティは、存在エリアの信頼性を反映する。アクセスポイント１０５と関連付けられた存在エリアのスタビリティは、例えば最後の２つの計算により算出された存在エリアを比較することで測定され、存在エリア間の重複の度合いを判定する。重複の度合いが高いほど、存在エリアはより安定する。
【００４６】
アクセスポイント１０５のロンジェビティは、アクセスポイント１０５と関連付けられたデータの品質を反映する。例えば、より長い時間データベースにあるアクセスポイントは、最近追加されたアクセスポイントより信頼性が高い。アクセスポイント１０５のロンジェビティは、位置データベースにおけるデータの履歴により測定される。
【００４７】
いくつかの実施例において、データのフレッシュネスは、アクセスポイント１０５と関連付けられた存在エリアが地理グリッド１００のセル１０２に割り当てられるかを判定するために更に使用される。データのフレッシュネスは、システムがどれくらい前に移動装置１０８から最新の位置を受信したかにより測定される。
【００４８】
システムは、ポピュラリティ、スタビリティ、ロンジェビティ及びフレッシュネスに基づいて地理グリッド１００のセル１０２に配置された各存在エリアをランク付けすることができる。セル１０２に配置された全ての存在エリアのうちの少なくとも一部（例えば、アクセスポイント１０５と関連付けられる存在エリアを含む３つの存在エリア）は、セル１０２に割り当てられる。割り当てられたアクセスポイント及び存在エリアは、アクセスポイント１０５の通信範囲内に位置する移動装置（例えば、移動装置１１０）を配置するために使用される。割り当てられない存在エリアは、今後使用するために位置データベースに格納される。
【００４９】
システムは、アクセスポイント１０５と関連付けられた地理的位置をアクセスポイント１０５の通信範囲内に位置する第２の移動装置（例えば、移動装置１１０）に提供することができる（３０８）。システムは、同一のセルに配置された他の地理的位置及び隣接するセルに割り当てられたアクセスポイントと関連付けられた地理的位置を第２の移動装置に更に提供することができる。位置は、種々のプッシュ又はブロードキャスト技術を要求あるいは使用することで、アクセスポイント１０５から第２の移動装置に伝送される。
【００５０】
いくつかの実施例において、システムは、３次元位置情報を受信、処理及び伝送する。存在空間（例えば、存在空間１２４）は、３次元地理グリッド（例えば、３次元グリッド１２０）上の３次元セル（例えば、３次元セル１２２）に割り当てられる。位置は、種々のプッシュ又はブロードキャスト技術を要求又は使用することで、アクセスポイント１２６からアクセスポイント１２６の通信範囲内に位置する第２の移動装置に伝送される。
【００５１】
図３Ｂは、位置の集合を使用して平均地理的位置を算出する例示的な処理３０４を示すフローチャートである。便宜上、処理３０４を実現するシステムを参照して処理３０４を説明する。
【００５２】
システムは、集合における位置を使用して平均地理的位置を算出することができる（３２４）。平均地理的位置の算出は、集合における位置の緯度、経度及び高度の平均を算出すること、並びに算出された平均の緯度、経度及び高度における位置を平均地理的位置として指定することを含むことができる。いくつかの実施例において、平均地理的位置の算出は、集合における位置の中緯度、中経度及び中高度における位置を平均地理的位置として指定することを含むことができる。
【００５３】
システムは、集合における位置と平均地理的位置との間の距離を算出することができる（３２６）。いくつかの実施例において、システムは、集合における各位置とユークリッド空間における平均地理的位置との間の直線距離を算出することができる。いくつかの実施例において、システムは、地球の曲率を考慮して集合における各位置と平均地理的位置との間の測地線距離を算出することができる。
【００５４】
ステップ３２６で算出された距離は、中心と関連付けられた半径として指定される。円（例えば、円２０４ａ）の中心である中心は、ステップ３２４で算出された平均地理的位置である。円の半径は、位置の集合における位置と平均地理的位置との間の少なくとも１つの距離に基づいて判定される。いくつかの実施例において、半径は、平均地理的位置と集合に依然として存在する位置との間の最長距離に等しい。いくつかの実施例において、円１０６ｄが半径及び中心である平均地理的位置を使用して描画される場合、半径は、円が集合に依然として存在するある割合（例えば、８０％）の位置を含む距離である。半径は誤差の範囲を示す。その誤差の範囲を超えると、非ＧＰＳ対応移動装置の位置の推定値は、統計的に有意義である可能性が低い。
【００５５】
システムは、平均位置と位置との間の距離に基づいて集合から少なくとも１つの位置を除外することができる（３２８）。いくつかの実施例において、システムは、平均地理的位置までの距離が閾値距離を上回る位置を除外する。マルチパス解析の各パスにおいて、システムは、位置の集中（例えば、クラスタ）から離れると考えられる位置を除外することにより、推定された平均地理的位置の精度を向上させることができる。位置のクラスタから離れた位置は、アクセスポイント１０５と関連付けられた存在エリアを推定するためにあまり有用ではなく、除外される。種々の実施例において、閾値距離は、１つのパスから次のパスに変動しうる。いくつかの実施例において、閾値距離は平均地理的位置までの距離である。閾値距離内において、集合のある割合（例えば、９５％）の位置が設けられる。いくつかの実施例において、閾値距離は、パスに対応する距離の集合である（例えば、第１のパスに対して２５０メートル、第２のパスに対して１５０メートル等）。平均地理的位置と位置との間の距離が閾値距離を上回る場合、システムは、集合から少なくとも１つの位置を除外することができる。
【００５６】
システムは、終了条件が満たされるまでステップ３０４におけるステップ３２４、３２６及び３２８を繰り返すことができる。システムは、繰返しを終了するための終了条件が満たされるかを判定することができる（３３０）。いくつかの実施例において、終了条件は、繰返しの回数が閾値回数（例えば、１０回）に達したときに満たされる。閾値回数及び除外すべき位置の割合は、確実性（例えば、より広い存在エリアにより、セルにおける移動装置が実際に存在エリアに位置する信頼度が高くなる）と精度（例えば、より狭い存在エリアにより、移動装置のより正確な位置が得られる）とのバランスを微調整するように構成可能である。例えば、割合が９５％に設定され、パスの数が１０に設定される場合、最終的なパスは、全ての位置データ点の約６０％を含む円を生成することができる。
【００５７】
いくつかの実施例において、存在エリア又は存在空間が十分に狭い場合に、ステップ３３０における終了条件が満たされる。移動装置が非常に集中するセルにおいて、存在エリアは、更なるパスが精度を向上させる必要がないほど十分に狭い。円の半径が閾値半径を下回る場合、ステップ３２４、３２６及び３２８の繰返しは終了する。例えば閾値半径は、８〜１０メートルである。閾値半径は、受信した集合における位置の分布パターン（例えば、受信した位置データ点の数、位置データ点の密度及びセルにおける集中領域）に基づいてアクセスポイント毎に異なる。
【００５８】
システムは、中心である平均地理的位置及び少なくとも１つの算出された距離に基づく半径を有する円として地理的エリアを指定することができる（３３２）。地理的エリアは、アクセスポイント（例えば、アクセスポイント１０５）と関連付けられる。サーバは、移動装置の現在位置を算出するために地理的エリア（例えば、中心及び半径）を移動装置に提供することができる。中心は緯度及び経度で示される。距離が３次元空間において算出されるいくつかの実施例において、中心は高度で更に示される。
【００５９】
図３Ｃは、位置データベースを管理する技術を実現する例示的なシステムを示すブロック図である。システムは、１つ以上のプロセッサ、命令を格納する１つ以上のメモリ素子及び他のハードウェアコンポーネント又はソフトウェアコンポーネントを含む。システムは、アクセスポイント（例えば、アクセスポイント１０５）と関連付けられる存在エリア又は存在空間を判定するために使用される位置特定エンジン３５０を備える。
【００６０】
位置特定エンジン３５０は、種々のアクセスポイントを介して種々の移動装置からデータを受信するデータ収集モジュール３５２を備える。データは、１つ以上の位置認識移動装置（例えば、移動装置１０８）の位置及び移動装置１０８が接続されるアクセスポイントを示すアクセスポイントの識別子（例えば、アクセスポイント１０５のＭＡＣアドレス）を示す多数のデータ点を含む。いくつかの実施例において、データ点は、移動装置１０８が位置するタイムゾーンに関する情報を更に含む。データ収集モジュール３５２は、移動装置１０８から伝送されたデータを受信するデータ受信モジュール３５４及びデータ・インデクシング・モジュール３５６を備える。データ・インデクシング・モジュール３５６は、受信したデータ点に対して種々の処理を実行する。例えばデータ・インデクシング・モジュール３５６は、セルＩＤに基づいて緯度、経度及び高度をソートする。データ・インデクシング・モジュール３５６は、期間に基づいてデータを集合に更にグループ化する。例えば、受信した位置の新しい集合は、構成可能な期間（例えば、６時間）にわたり作成される。
【００６１】
移動装置１０８の受信した位置の集合は、データ点データベース３６０に格納される。データ点データベース３６０は、種々の移動装置１０８の現在位置及び履歴位置を格納することができる。データ点データベース３６０は、アドホックデータベース、リレーショナルデータベース、オブジェクト指向データベースを含む。データ点データベース３６０は、位置特定エンジン３５０に関連してローカル又はリモートでホストされる。
【００６２】
位置計算モジュール３６４は、データ点データベースにおいてデータ点の集合における平均地理的位置及び平均地理的位置と種々のデータ点の位置との間の距離を算出し、更なる計算のために集合から位置を除外するために利用される。終了条件が特定の集合（例えば、セルＩＤと関連付けられたデータ点の集合）に到達するまで、位置計算モジュール３６４は、特定の集合に対する計算を実行する。位置計算モジュール３６４は、アクセスポイント（例えば、アクセスポイント１０５）毎に存在エリア又は存在空間を判定する。
【００６３】
いくつかの実施例において、位置計算モジュール３６４は、妥当性チェッカ３６６を使用して種々の基準及びデータ点の種々のデータに基づいて存在エリア又は存在空間に対する妥当性チェックを実行する。例えば、移動装置１０８から受信したデータ点は、国識別コード（ＭＣＣ：Mobile Country Code）及びタイムゾーンの情報を含む。妥当性チェッカ３６６は、算出された存在エリア又は存在空間をＭＣＣにより示された国に対応する多角形及びタイムゾーンに対応する多角形と比較する。算出された存在エリア又は存在空間が多角形の外側に配置される場合、妥当性チェッカ３６６は、異常を登録し、アクセスポイントを除外する。
【００６４】
位置フィルタリングエンジン３６８は、存在エリア又は存在空間が現在アクセスポイントの通信範囲内に配置されている移動装置の位置を推定するために使用されるかを判定することができる。位置フィルタリングエンジン３６８は、地理領域を地理グリッド１００のセル１０２又は３次元グリッド１２０の３次元セル１２２に分割することができる。位置フィルタリングエンジン３６８は、ポピュラリティ、スタビリティ、ロンジェビティ及びフレッシュネスに基づいて存在エリア又は存在空間をランク付けすることができる。位置フィルタリングエンジン３６８は、各セル１０２又は３次元セル１２２に配置されたトップレベルの存在エリア又は存在空間をセル１０２又は３次元セルに割り当てることができる。
【００６５】
存在エリア及び存在空間は、位置の集合の平均の緯度座標、経度座標及び高度座標を有する中心により規定される。存在エリア及び存在空間は、位置の集合における位置から中心までの距離に基づいて判定された半径により更に規定される。存在エリア及び存在空間に対する中心の緯度座標、経度座標及び高度座標、並びに存在エリアの半径及び存在空間の半径は、位置データベース３７２に格納される。位置データベース３７２は、割り当てられた存在エリア及び存在空間、並びに割り当てられない存在エリア及び存在空間を全て格納する。割り当てられない存在エリア又は存在空間は、位置計算モジュール３６４による後続の計算に割り当てられる。位置データベース３７２は、位置計算モジュール３６４により定期的に更新される。
【００６６】
位置データベース３７２のデータは、データ配信モジュール３７６を使用して移動装置に配信される。データ配信モジュール３７６は、ブロードキャストを介して要求されるか、あるいは移動装置から要求を受信せずに種々のプッシュ技術を使用して、アクセスポイントと関連付けられる割り当てられた存在エリア及び存在空間（例えば、中心座標及び半径）の情報を移動装置（例えば、非ＧＰＳ対応移動装置１１０）に送出する。
【００６７】
いくつかの実施例において、データ配信モジュール３７６は、１つの伝送セッションにおいて多数の存在エリア及び存在空間を移動装置に送出することができる。移動装置の通信帯域幅を消費する移動装置への位置伝送の回数を減少するために、データ配信モジュール３７６は、移動装置１１０が位置するセルに隣接するセルを配置するために隣接ロケータ３８０を使用することができる。例えば隣接するセルは、セル及び周囲のセルの全領域がある特定の地理的エリア（例えば、１又は２平方キロメートル）を範囲に含むように移動装置１１０が位置するセルを取り囲む多くのセルを含む。多数のセル（例えば、４００個のセル）と関連付けられた存在エリア及び存在空間に関する情報を移動装置１００に送出することにより、移動装置１１０がセルにわたって移動する場合の伝送の回数が減少する。そのような実施例において、データ配信モジュール３７６は、移動装置１１０が前に送出された全てのセルの外に出る場合に移動装置１１０に更新を送出するだけでよい。
【００６８】
＜位置データベースを用いて移動装置の位置を判定する処理の例＞
図４Ａは、無線アクセスポイントの位置を使用して移動装置の位置を判定する技術を示す。移動装置４００は、位置を判定するために無線アクセスポイントの位置を使用する例示的な移動装置である。アクセスポイント４０４を含む通信ネットワークの例示的な部分を示す。
【００６９】
移動装置４００は、アクセスポイント４０４ａの通信範囲内に位置しうる。移動装置４００は、隣接するアクセスポイントの存在エリア又は存在空間（存在エリア４０６を含む）に関する情報を含むデータをアクセスポイント４０４ａから受信する。移動装置４００は、受信したデータを位置データベースに格納する。位置データベースは、移動装置４００の記憶装置にホストされうる。格納されたデータは、定期的に、又は要求に応じて、更新されうる。
【００７０】
示された例において、移動装置４００は、アクセスポイント４００ａの通信範囲内に位置する。更に移動装置４００は、アクセスポイント４０４ｂ、４０４ｃ及び４０４ｄに対する通信範囲内にある。移動装置４００は、ＷＬＡＮ（例えば、ＩＥＥＥ８０２．１１ａ）において使用された無線通信プロトコル下でアクセスポイント４０４ａ、４０４ｂ、４０４ｃ及び４０４ｄを識別する。アクセスポイント４０４ａ、４０４ｂ、４０４ｃ及び４０４ｄは、アクセスポイントのＭＡＣアドレス又は他の識別子（例えば、Ｂｌｕｅｔｏｏｔｈ（登録商標）識別子）により識別される。
【００７１】
移動装置４００は、それぞれ、アクセスポイント４０４ａ〜４０４ｄと関連付けられる存在エリア４０６ａ、４０６ｂ、４０６ｃ及び４０６ｄを識別することができる。存在エリア４０６ａ〜４０６ｄを識別することは、移動装置４００に結合されたメモリ素子から存在エリア４０６ａ〜４０６ｄに関する情報を検索することを含む。いくつかの実施例において、移動装置４００は、アクセスポイント４０４ａ〜４０４ｄの識別子をサーバに送出することにより、サーバから存在エリア４０６ａ〜４０６ｄを要求することができる。
【００７２】
存在エリア４０６ａ〜４０６ｄに基づいて、移動装置４００は、存在エリア４０６ａ〜４０６ｄに対して反復処理（例えば、マルチパス解析）を実行することができる。反復処理によって、移動装置４００の現在の地理的位置の推定位置である地理的エリア４０２を生成することができる。３次元位置情報が利用される場合、地理的エリア４０２は地理空間である。移動装置４００は、表示装置（例えば、地図ディスプレイ）上に推定された現在位置を表示することができる。
【００７３】
図４Ｂは、位置データベースを使用して移動装置の位置を判定する例示的な処理４１０を示すフローチャートである。便宜上、処理４１０を実現する移動装置４００を参照して処理４１０を説明する。
【００７４】
移動装置４００は、移動装置４００が位置する通信範囲内の現在のアクセスポイントを識別することができる（４１２）。移動装置４００は、移動装置４００にホストされる位置データベースの更新を要求すべきかを判定するために現在のアクセスポイントを使用することができる。移動装置４００にホストされた位置データベースは、以前に移動装置４００にダウンロードされたアクセスポイントの記録を含む。移動装置４００にホストされた位置データベースにおける記録は、アクセスポイントの識別子（例えば、ＭＡＣアドレス）及び対応する位置（例えば、緯度座標／経度座標）を含む。
【００７５】
ステップ４１２において、移動装置４００は、現在のアクセスポイントが位置データベースの記録に含まれるかを判定することができる。移動装置は、移動装置４００が位置する通信範囲内の現在のアクセスポイントの識別子（例えば、ＭＡＣアドレス）を使用して位置データベースの検索を実行することができる。現在のアクセスポイントが位置データベースの記録に含まれる場合、移動装置は、位置データベースが最新であると判定することができる。現在のアクセスポイントが位置データベースの記録に含まれない場合、移動装置４００は、位置データベースの更新が必要であると判定することができる。
【００７６】
移動装置４００は、現在のアクセスポイントの識別子を使用して移動装置４００の位置データベースの更新をサーバから要求することができる（４１４）。アクセスポイントの識別子及び位置を含む位置データベースにおける記録は、新しいアクセスポイントの新しい識別子及び位置を使用してリフレッシュされる。移動装置４００は、現在のアクセスポイントの識別子をサーバに送出することができる。サーバは、地理グリッドにおいてセルを中心セルとして識別することができる。中心セルは、サーバに対して現在のアクセスポイントの識別子と関連付けられた位置を含むセルであり、セル及び隣接するセルにおける全てのアクセスポイント位置を移動装置４００に送出することができる。サーバは、中心セルを、隣接セルの位置決めのための始点として使用することができる。中心セルは、その中心セル及びその隣接セルを含むセルのグループのアンカーとなりうるが、その中心セルが、セルのグループの正確な地理的な中心に位置している必要はない。例えば、中心セルが臨海地上のセルであり、隣接セルが全て当該中心セルの片側に配置されることもある。
【００７７】
移動装置４００は、第２のアクセスポイントと関連付けられた第２の位置の集合を受信することができる（４１６）。第２のアクセスポイントは、地理グリッド上の中心セル及び中心セルに隣接するセルに配置される。現在のアクセスポイント（例えば、円形領域の中心）と関連付けられた位置は、中心セルに配置される。隣接するセルは、地理グリッド上の中心セルに隣接又は近接して配置されるセルである。隣接するセルの数は、中心セル及び隣接するセルが所定の地理的エリア（例えば、１．５平方キロメートル）を範囲に含むような値を有する。アクセスポイントと関連付けられた位置が中心セル及び隣接するセルが範囲に含む地理的エリア内にある場合、アクセスポイントの識別子及びアクセスポイントと関連付けられた位置は、更新に含まれる。現在のアクセスポイントが位置データベースの記録に含まれない場合に移動装置４００上で位置を更新する１つの例示的な利点は、移動装置４００がセルからセルに移動する場合に移動装置４００が単一のアクセスポイントのサービスエリアと比較して広い領域の外に出るまで更新が必要ないことである。従って、頻繁に更新することが回避され、移動装置４００（例えば、帯域幅、ＣＰＵサイクル、電池電源）及びサーバ（例えば、移動装置が１つのストリートブロックから次のストリートブロックに移動する場合、サーバは、頻繁に起きる更新を多くの装置に送出する必要はない）双方に対するリソースを節約することができる。
【００７８】
移動装置４００は、受信したアクセスポイントの位置の集合及び識別子を使用して移動装置４００にホストされた位置データベースを更新することができる（４１８）。更新により、中心セル及び隣接セルによってカバーされる地理的エリアにおいて移動装置４００を「中心に置く」ことができる。移動装置４００は、自身が中心セルから隣接するセルのうちの１つが範囲に含まないセルに移動するまで別の更新を要求する必要はない。例えば、各セルが約５０メートル×５０メートルであり、所定の地理的エリアが１．５平方キロメートルである場合、各更新は、約６００個のセルを移動装置４００の位置データベースに注入する。移動装置が６００個のセルが範囲に含む領域の外に出ない限り、移動装置４００は別の更新を要求する必要はない。
【００７９】
移動装置４００は、移動装置４００にホストされる位置データベースを使用して移動装置４００の現在位置を算出する（４２０）。計算は、移動装置４００により実行された適応マルチパス処理を使用して実行される。図４Ｃに関連して、マルチパス処理の更なる詳細を以下において説明する。他の要因（例えば、種々のアクセスポイントからの信号強度）が現在位置の計算を支援してよいが、これらの要因は計算には必要ない。
【００８０】
移動装置４００は、必要に応じて移動装置４００の地図表示装置に移動装置４００の現在位置を表示することができる（４２２）。図５に関連して、現在位置の表示例を以下において更に詳細に説明する。
【００８１】
図４Ｃは、移動装置の位置を判定する例示的な適応マルチパス処理４３０を示すフローチャートである。便宜上、処理４３０を実現する移動装置４００を参照して処理４３０を説明する。
【００８２】
移動装置４００は、無線通信ネットワーク（例えば、ＷＬＡＮ）のアクセスポイント（例えば、アクセスポイント４０４）の識別子を受信することができる（４３２）。アクセスポイントは、移動装置４００の通信範囲内に配置される。識別子は、移動装置４００が接続されるかあるいは接続するアクセスポイントと関連付けられる必要はない。例えば、特定の位置において、移動装置４００は、３個〜２０個のアクセスポイントの通信範囲内にある。移動装置４００は、アクセスポイントのうちの２つに接続できるだけでもよい（例えば、アクセスポイント及び移動装置４００のセキュリティ設定のために）。移動装置４００は、２つのアクセスポイントのうちの一方のみに能動的に接続されるか、又はいずれのアクセスポイントにも接続されない。しかし、移動装置４００が受信したアクセスポイントの全ての識別子は、計算に使用される。
【００８３】
移動装置４００は、移動装置４００の位置データベースからアクセスポイントと関連付けられた位置の集合を識別することができる（４３３）。位置の集合は、アクセスポイントと関連付けられた存在エリア４０６又は存在空間に対応する。各位置は、地理座標（例えば、緯度、経度及び高度）により示される。各位置は、アクセスポイント４０４の識別子（例えば、ＭＡＣアドレス）と関連付けられる。移動装置４００は、データベース検索を使用して位置を識別することができる。
【００８４】
移動装置４００は、集合における位置を使用して平均地理的位置を算出することができる（４３４）。平均地理的位置の算出は、集合における位置の緯度、経度及び高度の平均を算出すること、並びに算出された平均の緯度、経度及び高度における位置を平均地理的位置として指定することを含みうる。いくつかの実施例においては、平均地理的位置の算出は、集合における位置の中緯度、中経度及び中高度における位置を平均地理的位置として指定することを含む。
【００８５】
移動装置４００は、集合における位置と平均地理的位置との間の距離を算出することができる（４３６）。いくつかの実施例において、システムは、集合における各位置とユークリッド空間における平均地理的位置との間の直線距離を算出することができる。いくつかの実施例において、システムは、地球の曲率を考慮して集合における各位置と平均地理的位置との間の測地線距離を算出することができる。
【００８６】
ステップ４３６で算出された距離は、中心と関連付けられた半径として指定される。円（例えば、地理的エリア４０２を取り囲む円）の中心である中心は、ステップ４３４で算出された平均地理的位置である。円の半径は、位置の集合における位置と平均地理的位置との間の少なくとも１つの距離に基づいて判定される。いくつかの実施例において、半径は、平均地理的位置と集合に依然として存在する位置との間の最長距離に等しい。いくつかの実施例において、円が半径及び中心である平均地理的位置を使用して描画される場合、半径は、円が集合に依然として存在するある割合（例えば、８０％）の位置を含む距離である。半径は誤差の範囲を示す。その誤差の範囲を超えると、非ＧＰＳ対応移動装置の位置の推定値は、統計的に有意義である可能性が低い。
【００８７】
移動装置４００は、平均位置と位置との間の距離に基づいて集合から少なくとも１つの位置を除外することができる（４３８）。いくつかの実施例において、システムは、平均地理的位置までの距離が閾値距離を上回る位置を除外することができる。マルチパス解析の各パスにおいて、システムは、位置の集中（例えば、クラスタ）から離れると考えられる位置を除外することにより、推定された平均地理的位置の精度を向上させることができる。位置のクラスタから離れた位置は、移動装置４００の現在位置を推定するためにあまり有用ではなく、除外される。種々の実施例において、閾値距離は、１つのパスから次のパスに変動しうる。例えば閾値距離は、パスに対応する距離の集合である（例えば、第１のパスに対して５０メートル、第２のパスに対して３０メートル等）。平均地理的位置と位置との間の距離が閾値距離を上回る場合、システムは、集合から少なくとも１つの位置を除外することができる。
【００８８】
いくつかの実施例において、移動装置４００は、除外される位置の閾値割合を決定することができる。閾値割合は、予め指定された値（例えば、５％）を有することができる。各パスにおいて、移動装置４００は、平均地理的位置から遠くにある位置から、閾値割合の位置を除外することができる。
【００８９】
移動装置４００は、終了条件が満たされるまで処理４３０のステップ４３４、４３６及び４３８を繰り返すことができる。システムは、繰返しを終了するために終了条件が満たされるかを判定することができる（４４０）。いくつかの実施例において、終了条件は、繰返しの回数が閾値回数（例えば、５回）に達したときに満たされる。閾値回数は、元々受信した集合における多くの位置に関連する。閾値回数及び除外すべき位置の割合は、確実性（例えば、より広い存在エリアにより、セルにおける移動装置が実際に存在エリアに位置する信頼度が高くなる）と精度（例えば、より狭い存在エリアにより、移動装置のより正確な位置が得られる）とのバランスを微調整するように構成可能である。例えば、割合が９５％に設定され、パスの数が１０に設定される場合、最終的なパスは、全ての位置データ点の約６０％を含む円を生成することができる。
【００９０】
いくつかの実施例において、存在エリア又は存在空間が十分に狭い場合、ステップ３３０の終了条件は満たされる。アクセスポイント４０４が非常に集中する領域において、推定された現在位置は、更なるパスが精度を向上させる必要がないほど十分に狭い。円の半径が閾値半径を下回る場合、ステップ４３４、４３６及び４３８の繰返しは終了する。例えば閾値半径は、８メートル〜１０メートルである。閾値半径は、存在エリア４０６の半径に基づく。いくつかの実施例において、存在エリア４０６のいくつかの半径が十分に小さい場合、閾値半径は小さく、推定値に対する信頼度を反映する。
【００９１】
移動装置４００は、中心である平均地理的位置及び少なくとも１つの算出された距離に基づく半径を有する円を使用して移動装置４００の現在位置を指定することができる（４４２）。中心は緯度及び経度で示される。距離が３次元空間において算出されるいくつかの実施例において、中心は高度で更に示される。いくつかの実施例において、移動装置は、地図ユーザインタフェース上の表示装置に現在位置を更に表示することができる。図５を参照して、例示的な地図ユーザインタフェースを以下において説明する。
【００９２】
＜移動装置の位置を判定するためのユーザインタフェースの例＞
図５は、無線アクセスポイントの位置を使用して移動装置の位置を判定するための例示的なユーザインタフェースを示す。図５において、地理的エリアの例示的な地図５０２が移動装置５００に表示される。いくつかの実施例において、移動装置５００は、移動装置５００のタッチセンシティブディスプレイ５３０に地図５０２を表示することができる。地図５０２は、ユーザがマッピング及び位置を用いたサービスを表示するために地図オブジェクトを選択する場合に表示される。いくつかの実施例において、地図オブジェクト等のオブジェクトは、音声起動により選択される。検索バー５０４及びブックマークリストオブジェクト５０６は、地図５０２の上部に表示される。検索オブジェクト５０８、経路オブジェクト５１０、地図表示オブジェクト５１２及び現在位置オブジェクト５１４等の１つ以上の表示オブジェクトが地図の下部の下に表示される。
【００９３】
検索バー５０４は、地図上の住所又は他の位置を見つけるために使用される。例えば、ユーザが検索バー５０４に自宅の住所を入力すると、住所を含む領域が地図５０２に表示される。例えばブックマークリストオブジェクト５０６は、ユーザの自宅の住所等の頻繁に訪問する住所を含むブックマークリストを画面に表示させる。例えばブックマークリストは、現在位置（例えば、移動装置５００の現在位置）等の特殊なブックマークを更に含むことができる。
【００９４】
検索オブジェクト５０８は、検索バー５０４及び他の地図に関連した検索メニューを表示するために使用される。例えば経路オブジェクト５１０は、ユーザが出発地及び目的地を入力できるようにするメニューインタフェースを画面に表示させる。次にインタフェースは、情報（例えば、出発地から目的地までの経路の方向及び移動時間）を表示する。地図表示オブジェクト５１２は、ユーザが地図５０２に対する表示オプションを選択できるようにするメニューを画面に表示させる。例えば、地図５０２は白黒からカラーに変更され、地図の背景が変更され、あるいは、ユーザは地図の輝度を変更することができる。
【００９５】
現在位置オブジェクト５１４により、ユーザは、移動装置５００が現在配置されている場所を示す地図５０２上の地理的エリア５１６を確認できる。地理的エリア５１６は、中心が移動装置５００の通信範囲内にあるアクセスポイントと関連付けられたデータ点の平均地理的位置である推定地理的エリア（例えば、地理的エリア４０２）に対応する。地理的エリアの半径は、平均地理的位置とアクセスポイントと関連付けられた１つ以上の位置との間の距離に基づいて判定される。特殊な現在位置のブックマークは、現在位置オブジェクト５１４が選択される際にブックマークリストに置かれる。特殊な現在位置のブックマークが事前にブックマークリストに設定された場合、例えば古いブックマーク情報は、新しい現在位置情報で置換される。いくつかの実施例において、特殊な現在位置のブックマークは、地理的エリア５１６の重心と結び付けられる。すなわち、特殊な現在位置のブックマークは、地理的エリア５１６の重心に対する座標を含む。地理的エリア５１６は、移動装置５００のメモリ素子に格納された位置命令を使用して判定又は推定された位置データに基づく。例えば地理的エリア５１６は、円、長方形、正方形、六角形又は丸十字、あるいは地理的エリア５１６と地図５０２とを区別する他の何らかの特徴的な要素で示される。
【００９６】
いくつかの実施例において、地理的エリア５１６は、移動装置５００が位置すると判定又は推定される領域を含み、移動装置５００の実際の現在位置上の中心に置かれる必要はない。この例において、移動装置５００は、地理的エリア内で中心から外れて位置する。別の例において、地理的エリア５１６は、移動装置５００の推定された現在位置上の中心に置かれる。
【００９７】
現在位置オブジェクト５１４がタップ又は別の方法で選択される場合、例えば移動装置５００は、地理的エリア５１６上で地図表示を中心に置く。いくつかの実施例において、地図のズームレベルは、位置データの正確度又は精度、あるいは位置データを提供した技術、システム又はサービスに基づいて調整される。例えば、移動装置５００がより低い正確度のためにＧＰＳ信号を受信できず、位置を判定するためにアクセスポイントデータを使用する場合、地図は縮小される。移動装置５００が現在位置を判定するためにＧＰＳ位置データを使用できる場合、より高い正確度のために地図は拡大される。いくつかの実施例において、ズームレベルは、移動装置５００の速さに基づく（例えば地図は、より速い速さで縮小され、移動装置５００が移動していない場合に拡大される）。正確度又は精度と速さとの組合せが更に使用される。
【００９８】
位置情報データを検索する全ての方法が失敗し（例えば、移動装置５００があらゆるアクセスポイントの通信範囲内にない場合又は移動装置５００が接続されるあらゆるアクセスポイントと存在エリアが関連付けられないことを妥当性チェッカ３６６が判定する場合）、移動装置５００の現在位置を判定又は推定するために使用可能な他のシステム又はサービスがない場合、ユーザに対してエラーが表示され、地理的エリアが地図５０２に表示されない。例えばエラーは、失敗及び考えられる１つ又は複数の失敗の理由を通知するユーザに対するメッセージを含むことができる。
【００９９】
例えば現在位置オブジェクト５１４は、地図５０２上で地理的エリア５１６を推定及び表示することを起動するか、推定された現在位置（すなわち、地理的エリア５１６の重心）に対する経路を取得するか、移動装置５００の推定された現在位置を友人に送出するか（例えば、友人が同一の位置に行けるように）、あるいは推定された現在位置に対するブックマークを作成するために選択される。
【０１００】
＜システムアーキテクチャの例＞
図６は、図１〜図５を参照して説明する機能及び動作を実現する例示的なシステムアーキテクチャ６００を示すブロック図である。より多くの構成要素又はより少ない構成要素を有するアーキテクチャを含む他のアーキテクチャが可能である。いくつかの実施例において、アーキテクチャ６００は、１つ以上のプロセッサ６０２（例えば、デュアルコアインテルＸｅｏｎプロセッサ）、１つ以上の出力装置６０４（例えば、ＬＣＤ）、１つ以上のネットワークインタフェース６０６、１つ以上の入力装置６０８（例えば、マウス、キーボード、タッチセンシティブディスプレイ）及び１つ以上のコンピュータ可読媒体６１２（例えば、ＲＡＭ、ＲＯＭ、ＳＤＲＡＭ、ハードディスク、光ディスク、フラッシュメモリ等）を備える。これらの構成要素は、データの転送及び構成要素間の信号の制御を容易にするために種々のハードウェア及びソフトウェアを利用する１つ以上の通信チャネル６１０（例えば、バス）を介して通信及びデータを交換する。
【０１０１】
「コンピュータ可読媒体」という用語は、実行するために命令をプロセッサ６０２に提供することに関係する不揮発性媒体（例えば、光ディスク又は磁気ディスク）、揮発性媒体（例えば、メモリ）及び伝送媒体を含むがそれらに限定されないあらゆる媒体を示す。伝送媒体は、同軸ケーブル、銅線及び光ファイバを含むがそれらに限定されない。
【０１０２】
図１〜図５を参照して説明したように、コンピュータ可読媒体６１２は、オペレーティングシステム６１４（例えば、Ｍａｃ ＯＳ（登録商標）サーバ、Ｗｉｎｄｏｗｓ（登録商標）ＮＴサーバ）、ネットワーク通信モジュール６１６、データベースインタフェース６２０、データ収集モジュール６３０、データ配信モジュール６４０及び位置計算モジュール６５０を更に備える。オペレーティングシステム６１４は、マルチユーザ、マルチプロセシング、マルチタスキング、マルチリーディング、リアルタイム等である。オペレーティングシステム６１４は、装置６０６、６０８からの入力を認識し、出力を装置６０６、６０８に提供すること、コンピュータ可読媒体６１２（例えば、メモリ又は記憶装置）上でファイル及び経路を追跡し、管理すること、周辺装置を制御すること、並びに１つ以上の通信チャネル６１０上のトラフィックを管理することを含むがそれらに限定されない基本タスクを実行する。ネットワーク通信モジュール６１６は、ネットワーク接続を確立及び維持する種々の構成要素（例えば、ＴＣＰ／ＩＰ、ＨＴＴＰ等の通信プロトコルを実現するソフトウェア）を含む。データベースインタフェース６２０は、ファイルシステムに１つ以上のデータベース（例えば、データ点データベース３６０及び位置データベース３７２）に対するインタフェースを含む。データベースは、階層フォルダ構造下で編成される。フォルダは、ファイルシステムにおいて経路にマッピングする。データ収集モジュール６３０は、アクセスポイント又は他の通信チャネル（例えば、セルラネットワーク）を介してシステム６００に無線接続された多数の移動装置からデータを収集する構成要素を含む。データ配信モジュール６４０は、無線通信ネットワークのアクセスポイントと関連付けられた位置データを移動装置１０８及び１１０を含むコンピューティング装置に伝送する種々の機能を実行する。位置計算モジュール６５０は、移動装置１０８から受信した位置に対してマルチパス解析を実行する１つ以上の構成要素を含む。
【０１０３】
アーキテクチャ６００は、データベースアプリケーションプログラムをホストできるあらゆる装置に含まれる。アーキテクチャ６００は、並行処理又はピアツーピアインフラストラクチャにおいて、あるいは１つ以上のプロセッサを備える単一の装置上で実現される。ソフトウェアは、多数のソフトウェアコンポーネントを含むか、あるいはコードの単一のボディーである。
【０１０４】
説明した機能は、データ記憶システムに対してデータ及び命令を送受信するように結合された少なくとも１つのプログラム可能なプロセッサ、少なくとも１つの入力装置、並びに少なくとも１つの出力装置を備えるプログラム可能なシステム上で実行可能な１つ以上のコンピュータプログラムにおいて有利に実現される。コンピュータプログラムは、ある特定の動作を実行するかあるいはある特定の結果をもたらすためにコンピュータにおいて直接又は間接的に使用される命令の集合である。コンピュータプログラムは、コンパイル又は解釈された言語を含むあらゆる形態のプログラミング言語（例えば、オブジェクティブＣ、Ｊａｖａ（登録商標））で書かれ、スタンドアロンプログラム、あるいはモジュール、構成要素、サブルーチン、ブラウザベースのウェブアプリケーション又はコンピューティング環境において使用するのに適した他のユニットのようなものを含むあらゆる形態で展開される。
【０１０５】
命令のプログラムを実行するのに適したプロセッサは、例として、あらゆる種類のコンピュータの汎用マイクロプロセッサと専用マイクロプロセッサの双方及び単独のプロセッサ、あるいは多数のプロセッサ又はコアのうちの１つを備える。一般にプロセッサは、読み出し専用メモリ又はランダムアクセスメモリ、あるいはそれら双方から命令及びデータを受信する。コンピュータの必須要素は、命令を実行するプロセッサ、並びに命令及びデータを格納する１つ以上のメモリである。一般にコンピュータは、データファイルを格納する１つ以上の大容量記憶装置を更に備えるか、あるいはそのような装置と通信するように動作可能に結合される。そのような装置は、内部のハードディスク及び取り外し可能ディスク等の磁気ディスク、光磁気ディスク、並びに光ディスクを含む。コンピュータプログラムの命令及びデータを明白に具体化するのに適した記憶装置は、例としてＥＰＲＯＭ素子、ＥＥＰＲＯＭ素子及びフラッシュメモリ素子等の半導体メモリ素子、内部のハードディスク及び取り外し可能ディスク等の磁気ディスク、光磁気ディスク、並びにＣＤ−ＲＯＭディスク及びＤＶＤ−ＲＯＭディスクを含む全ての形態の不揮発性メモリを含む。プロセッサ及びメモリは、ＡＳＩＣ（特定用途向け集積回路）により補足されるか、あるいはＡＳＩＣに組み込まれる。
【０１０６】
ユーザとの対話を提供するために、機能は、ユーザに対して情報を表示するＣＲＴ（ブラウン管）モニタ又はＬＣＤ（液晶ディスプレイ）モニタ等の表示装置、並びにユーザがコンピュータに入力を提供するキーボード及びマウス又はトラックボール等のポインティング装置を有するコンピュータ上で実現される。
【０１０７】
機能は、データサーバ等のバックエンドコンポーネントを備えるコンピュータシステム、あるいはアプリケーションサーバ又はインターネットサーバ等のミドルウェアコンポーネントを備えるコンピュータシステム、あるいはグラフィカルユーザインタフェース又はインターネットブラウザを有するクライアントコンピュータ等のフロントエンドコンポーネントを備えるコンピュータシステム、あるいはそれらのあらゆる組合せにおいて実現される。システムのコンポーネントは、通信ネットワーク等のあらゆる形態又は媒体のデジタルデータ通信により接続される。通信ネットワークの例には、ＬＡＮ、ＷＡＮ、並びにインターネットを形成するコンピュータ及びネットワーク等が含まれる。
【０１０８】
コンピュータシステムは、クライアント及びサーバを含む。クライアント及びサーバは、一般に、互いに離れ、ネットワークを介して対話する。クライアントとサーバとの関係は、それぞれのコンピュータ上で実行し且つ互いにクライアント−サーバ関係を有するコンピュータプログラムにより生じる。
【０１０９】
＜移動装置のアーキテクチャの例＞
図７は、移動装置の例示的なアーキテクチャ７００を示すブロック図である。例えば移動装置は、ハンドヘルドコンピュータ、パーソナルデジタルアシスタント、携帯電話、電子タブレット、ネットワーク機器、カメラ、スマートフォン、ＥＧＰＲＳ（enhanced general packet radio service）移動電話、ネットワーク基地局、メディアプレーヤ、ナビゲーション装置、電子メール装置、ゲーム機、あるいはこれらのデータ処理装置又は他のデータ処理装置のうちのいずれか２つ以上の組合せである。
【０１１０】
移動装置は、メモリインタフェース７０２、１つ以上のデータプロセッサ、画像プロセッサ及び／又は中央処理装置７０４、並びに周辺インタフェース７０６を備える。メモリインタフェース７０２、１つ以上のプロセッサ７０４及び／又は周辺インタフェース７０６は、別個の構成要素であるか、あるいは１つ以上の集積回路に内蔵される。移動装置の種々の構成要素は、１つ以上の通信バス又は信号線で結合される。
【０１１１】
センサ、装置及びサブシステムは、周辺インタフェース７０６に結合され、多数の機能性を容易にする。例えば、モーションセンサ７１０、光センサ７１２及び近接センサ７１４は、周辺インタフェース７０６に結合され、移動装置の姿勢機能、照明機能及び近接機能を容易にする。位置特定プロセッサ７１５（例えば、ＧＰＳ受信機）は、周辺インタフェース７０６に接続され、無線位置測定を実行する。電磁力計７１６（例えば、集積回路チップ）は、周辺インタフェース７０６に更に接続され、磁北の方向を判定するために使用されるデータを提供する。
【０１１２】
カメラサブシステム７２０、並びに電荷結合素子（ＣＣＤ）又は相補型金属酸化物半導体（ＣＭＯＳ）光学センサ等の光学センサ７２２は、例えば写真及びビデオクリップを記録するカメラ機能を容易にするために利用される。
【０１１３】
通信機能は、無線周波数送受信機及び／又は光（例えば、赤外線）送受信機を備える１つ以上の通信サブシステム７２４により容易になる。通信サブシステム７２４の特定の設計及び実施例は、通信ネットワークに依存する。移動装置は、通信ネットワークを介して動作することを意図する。例えば移動装置は、ＧＳＭ（登録商標）ネットワーク、ＧＰＲＳネットワーク、ＥＤＧＥネットワーク、ＷｉＦｉネットワーク又はＷｉＭａｘネットワーク及びＢｌｕｅｔｏｏｔｈネットワークを介して動作するように設計された通信サブシステム７２４を含む。特に、無線通信サブシステム７２４は、装置が他の無線装置に対する基地局として構成されるようにホスティングプロトコルを含む。
【０１１４】
オーディオサブシステム７２６は、スピーカ７２８及びマイク７３０に結合され、音声認識機能、音声複製機能、デジタル記録機能及び電話機能等の音声機能を容易にする。
【０１１５】
Ｉ／Ｏサブシステム７４０は、タッチスクリーンコントローラ７４２及び／又は他の入力コントローラ７４４を備える。タッチスクリーンコントローラ７４２は、タッチスクリーン７４６又はタッチパッドに結合される。例えば、タッチスクリーン７４６及びタッチスクリーンコントローラ７４２は、容量性、抵抗性、赤外線及び表面弾性波の技術を含むがそれらに限定されない複数のタッチセンシティブ技術のうちのいずれか、並びにタッチスクリーン７４６との１つ以上の接触点を判定する他の近接センサアレイ又は他の要素を使用してそれらの接触及び動き又は中止を検出する。
【０１１６】
他の入力コントローラ７４４は、他の入力／制御装置７４８、例えば１つ以上のボタン、ロッカースイッチ、サムホイール、赤外線ポート、ＵＳＢポート及び／又はスタイラス等のポインタ装置に結合される。１つ以上のボタン（不図示）は、スピーカ７２８及び／又はマイク７３０の音量調節のためのアップ／ダウンボタンを含む。
【０１１７】
一実施例において、第１の期間中ボタンを押下することでタッチスクリーン７４６のロックを解除し、第１の期間より長い第２の期間中ボタンを押下することで移動装置の電源をｏｎ又はｏｆｆする。ユーザは、１つ以上のボタンの機能性をカスタマイズできる。例えばタッチスクリーン７４６は、仮想ボタン又はソフトボタン、並びに／あるいはキーボードを実現するために更に使用される。
【０１１８】
いくつかの実施例において、移動装置は、ＭＰ３ファイル、ＡＡＣファイル及びＭＰＥＧファイル等の記録されたオーディオファイル及び／又はビデオファイルを提示する。いくつかの実施例において、移動装置は、ｉＰｏｄ（登録商標）等のＭＰ３プレーヤの機能性を含む。従って、移動装置は、ｉＰｏｄと互換性のあるピンコネクタを含む。他の入出力装置及び制御装置も使用できる。
【０１１９】
メモリインタフェース７０２はメモリ７５０に結合される。メモリ７５０は、１つ以上の磁気ディスク記憶装置、１つ以上の光記憶装置及び／又はフラッシュメモリ（例えば、ＮＡＮＤ、ＮＯＲ）等の高速ランダムアクセスメモリ及び／又は不揮発性メモリを含む。メモリ７５０は、Ｄａｒｗｉｎ、ＲＴＸＣ、ＬＩＮＵＸ（登録商標）、ＵＮＩＸ（登録商標）、ＯＳ Ｘ、ＷＩＮＤＯＷＳ（登録商標）等のオペレーティングシステム７５２又はＶｘＷｏｒｋｓ等の組み込みオペレーティングシステムを格納する。オペレーティングシステム７５２は、基本システムサービスを処理する命令及びハードウェア依存タスクを実行する命令を含む。いくつかの実施例において、オペレーティングシステム７５２はカーネル（例えば、ＵＮＩＸカーネル）を含む。
【０１２０】
メモリ７５０は、通信命令７５４を更に格納し、１つ以上の追加装置、１つ以上のコンピュータ及び／又は１つ以上のサーバとの通信を容易にする。メモリ７５０は、グラフィックユーザインタフェース処理を容易にするためのグラフィカルユーザインタフェース命令７５６、センサに関連する処理及び機能を容易にするためのセンサ処理命令７５８、電話に関連する処理及び機能を容易にするための電話命令７６０、電子メッセージングに関連する処理及び機能を容易にするための電子メッセージング命令７６２、ウェブ閲覧に関連する処理及び機能を容易にするためのウェブ閲覧命令７６４、メディア処理に関連する処理及び機能を容易にするためのメディア処理命令７６６、ＧＰＳ及びナビゲーションに関連する処理及び機能を容易にするためのＧＰＳ／ナビゲーション命令７６８、カメラに関連する処理及び機能を容易にするためのカメラ命令７７０、磁力計の校正を容易にするための磁力計データ７７２及び校正命令７７４を含む。メモリ７５０は、現在位置をアクセスポイントに伝送し、移動装置が通信範囲内にあるアクセスポイントと関連付けられた位置データに基づいて推定された現在位置を判定するために使用される位置命令７７６を含む。メモリ７５０は、セキュリティ命令等の他のソフトウェア命令（不図示）、ウェブビデオに関連する処理及び機能を容易にするためのウェブビデオ命令、並びに／あるいはウェブショッピングに関連する処理及び機能を容易にするためのウェブショッピング命令を更に格納する。いくつかの実施例において、メディア処理命令７６６は、それぞれ、オーディオ処理に関連する処理及び機能を容易にするためのオーディ処理命令、並びにビデオ処理に関連する処理及び機能を容易にするためのビデオ処理命令に分類される。活性化レコード及び国際移動体装置識別番号（ＩＭＥＩ）等のハードウェア識別子は、メモリ７５０に更に格納される。
【０１２１】
先に識別された命令及びアプリケーションの各々は、上述の１つ以上の機能を実行する命令の集合に対応する。これらの命令は、別個のソフトウェアのプログラム、手順又はモジュールとして実現される必要はない。メモリ７５０は、更なる命令又はより少ない命令を含む。また、移動装置の種々の機能は、１つ以上の信号処理回路及び／又は特定用途向け集積回路を含むハードウェア及び／又はソフトウェアで実現される。
【０１２２】
本発明の種々の実施例を説明したが、本発明の主旨の範囲から逸脱することなしに種々の変形を行うことができることは理解されよう。例えば、位置認識装置はＧＰＳ対応と呼ばれる。また、位置認識移動装置は、三角法又は他の技術に基づくことができる。図面においては、セルは略矩形形状で示されたが、セルの実際の形状は変動しうる。位置は「円」で示されたが、本明細書において使用された「円」という用語は、完全に円形である必要はなく、閉じられているかあるいはエンクロージャの外形を有するあらゆる幾何学的形状（例えば、楕円、正方形、凸多角形又は凹多角形、あるいは自由型形状）を含む。完全に円形ではない幾何学的形状の半径は、幾何学的形状の境界上の種々の点と幾何学的形状の中心との間の平均距離を含む。ＷｉＦｉ、ＷｉＭａｘネットワークは、例として使用したものであり、他の無線技術（例えば、セルラネットワーク）を使用してもよい。従って、他の実施例も、以下の特許請求の範囲の範疇に含まれる。
【特許請求の範囲】
【請求項１】
移動装置によって実行される方法であって、
前記移動装置が位置する通信範囲内の現在のアクセスポイントを識別するステップと、
サーバから、前記移動装置の位置データベースであって第１のアクセスポイントに関連付けられた第１の位置を記憶する位置データベースの更新を、前記現在のアクセスポイントの識別子を用いて要求するステップと、
第２のアクセスポイントに関連付けられた第２の位置の集合を受信するステップと、を有し、前記第２の位置は、地理的グリッドの中心セル及び該地理的グリッドの該中心セルに隣接するセルに分布し、前記現在のアクセスポイントは、前記中心セル内の位置に対応し、前記中心セル及び該中心セルに隣接するセルは所定の地理的エリアをカバーしており、
前記方法は更に、
前記受信した位置の集合を用いて前記位置データベースを更新するステップと、
前記位置データベースを用いて前記移動装置の現在位置を計算するステップと、
を有することを特徴とする方法。
【請求項２】
前記位置データベースを用いて前記移動装置の現在位置を計算するステップは、
（ａ）前記移動装置の通信範囲内にあるアクセスポイントの識別子を受信するステップと、
（ｂ）前記移動装置の前記位置データベースから、前記アクセスポイントに関連付けられた第３の位置の集合を識別するステップと、
（ｃ）前記第３の位置の集合を用いて平均地理的位置を計算するステップと、
（ｄ）前記平均地理的位置と前記第３の位置の集合における各位置との間の距離を計算するステップと、
（ｅ）前記平均地理的位置と前記第３の位置のうちの少なくとも１つとの間の距離に基づいて、前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップと、
（ｆ）終了条件が満たされるまで、ステップ（ｃ）、（ｄ）、（ｅ）を繰り返すステップと、
（ｇ）前記平均地理的位置を中心とし、少なくとも１つの前記算出された距離に基づく半径に有する円を用いて、前記移動装置の前記現在位置を指定するステップと、
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップは、
前記第３の位置の集合から除外する閾値割合を決定するステップと、
前記平均地理的位置から遠くに位置するものから、前記閾値割合の前記第３の位置を除外するステップと、
を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記終了条件は、前記繰返しの回数が閾値回数に達したときに満たされることを特徴とする請求項２に記載の方法。
【請求項５】
前記終了条件は、前記円の前記半径が閾値半径を下回ったときに満たされることを特徴とする請求項２に記載の方法。
【請求項６】
前記第３の位置の集合における各第３の位置は、緯度、経度、高度を含むことを特徴とする請求項２に記載の方法。
【請求項７】
前記移動装置の前記現在位置を、前記移動装置の地図表示装置に表示するステップを更に有することを特徴とする請求項１に記載の方法。
【請求項８】
前記アクセスポイントの前記識別子は、当該アクセスポイントのメディアアクセス制御（ＭＡＣ）アドレスを含むことを特徴とする請求項１に記載の方法。
【請求項９】
移動装置を含むシステムであって、
前記移動装置は、
前記移動装置が位置する通信範囲内の現在のアクセスポイントを識別するステップと、
サーバから、前記移動装置の位置データベースであって第１のアクセスポイントに関連付けられた第１の位置を記憶する位置データベースの更新を、前記現在のアクセスポイントの識別子を用いて要求するステップと、
第２のアクセスポイントに関連付けられた第２の位置の集合を受信するステップと、含む処理を実行するように構成され、前記第２の位置は、地理的グリッドの中心セル及び該地理的グリッドの該中心セルに隣接するセルに分布し、前記現在のアクセスポイントは、前記中心セル内の位置に対応し、前記中心セル及び該中心セルに隣接するセルは所定の地理的エリアをカバーしており、
前記移動装置は更に、
前記受信した位置の集合を用いて前記位置データベースを更新するステップと、
前記位置データベースを用いて前記移動装置の現在位置を計算するステップと、
を含む処理を実行するように構成されることを特徴とするシステム。
【請求項１０】
前記位置データベースを用いて前記移動装置の現在位置を計算するステップは、
（ａ）前記移動装置の通信範囲内にあるアクセスポイントの識別子を受信するステップと、
（ｂ）前記移動装置の前記位置データベースから、前記アクセスポイントに関連付けられた第３の位置の集合を識別するステップと、
（ｃ）前記第３の位置の集合を用いて平均地理的位置を計算するステップと、
（ｄ）前記平均地理的位置と前記第３の位置の集合における各位置との間の距離を計算するステップと、
（ｅ）前記平均地理的位置と前記第３の位置のうちの少なくとも１つとの間の距離に基づいて、前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップと、
（ｆ）終了条件が満たされるまで、ステップ（ｃ）、（ｄ）、（ｅ）を繰り返すステップと、
（ｇ）前記平均地理的位置を中心とし、少なくとも１つの前記算出された距離に基づく半径に有する円を用いて、前記移動装置の前記現在位置を指定するステップと、
を含むことを特徴とする請求項９に記載のシステム。
【請求項１１】
前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップは、
前記第３の位置の集合から除外する閾値割合を決定するステップと、
前記平均地理的位置から遠くに位置するものから、前記閾値割合の前記第３の位置を除外するステップと、
を含むことを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記終了条件は、前記繰返しの回数が閾値回数に達したときに満たされることを特徴とする請求項１０に記載のシステム。
【請求項１３】
前記終了条件は、前記円の前記半径が閾値半径を下回ったときに満たされることを特徴とする請求項１０に記載のシステム。
【請求項１４】
前記第３の位置の集合における各第３の位置は、緯度、経度、高度を含むことを特徴とする請求項１０に記載のシステム。
【請求項１５】
前記処理は、前記移動装置の前記現在位置を、前記移動装置の地図表示装置に表示するステップを更に含むことを特徴とする請求項９に記載のシステム。
【請求項１６】
前記アクセスポイントの前記識別子は、当該アクセスポイントのメディアアクセス制御（ＭＡＣ）アドレスを含むことを特徴とする請求項９に記載のシステム。
【請求項１７】
移動装置に方法を実行させるためのプログラムであって、前記方法は、
前記移動装置が位置する通信範囲内の現在のアクセスポイントを識別するステップと、
サーバから、前記移動装置の位置データベースであって第１のアクセスポイントに関連付けられた第１の位置を記憶する位置データベースの更新を、前記現在のアクセスポイントの識別子を用いて要求するステップと、
第２のアクセスポイントに関連付けられた第２の位置の集合を受信するステップと、を含み、前記第２の位置は、地理的グリッドの中心セル及び該地理的グリッドの該中心セルに隣接するセルに分布し、前記現在のアクセスポイントは、前記中心セル内の位置に対応し、前記中心セル及び該中心セルに隣接するセルは所定の地理的エリアをカバーしており、
前記方法は更に、
前記受信した位置の集合を用いて前記位置データベースを更新するステップと、
前記位置データベースを用いて前記移動装置の現在位置を計算するステップと、
を有することを特徴とするプログラム。
【請求項１８】
前記位置データベースを用いて前記移動装置の現在位置を計算するステップは、
（ａ）前記移動装置の通信範囲内にあるアクセスポイントの識別子を受信するステップと、
（ｂ）前記移動装置の前記位置データベースから、前記アクセスポイントに関連付けられた第３の位置の集合を識別するステップと、
（ｃ）前記第３の位置の集合を用いて平均地理的位置を計算するステップと、
（ｄ）前記平均地理的位置と前記第３の位置の集合における各位置との間の距離を計算するステップと、
（ｅ）前記平均地理的位置と前記第３の位置のうちの少なくとも１つとの間の距離に基づいて、前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップと、
（ｆ）終了条件が満たされるまで、ステップ（ｃ）、（ｄ）、（ｅ）を繰り返すステップと、
（ｇ）前記平均地理的位置を中心とし、少なくとも１つの前記算出された距離に基づく半径に有する円を用いて、前記移動装置の前記現在位置を指定するステップと、
を含むことを特徴とする請求項１７に記載のプログラム。
【請求項１９】
前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップは、
前記第３の位置の集合から除外する閾値割合を決定するステップと、
前記平均地理的位置から遠くに位置するものから、前記閾値割合の前記第３の位置を除外するステップと、
を含むことを特徴とする請求項１８に記載のプログラム。
【請求項２０】
前記終了条件は、前記繰返しの回数が閾値回数に達したときに満たされることを特徴とする請求項１８に記載のプログラム。
【請求項２１】
前記終了条件は、前記円の前記半径が閾値半径を下回ったときに満たされることを特徴とする請求項１８に記載のプログラム。
【請求項２２】
前記第３の位置の集合における各第３の位置は、緯度、経度、高度を含むことを特徴とする請求項１８に記載のプログラム。
【請求項２３】
前記方法は、前記移動装置の前記現在位置を、前記移動装置の地図表示装置に表示するステップを更に有することを特徴とする請求項１７に記載のプログラム。
【請求項２４】
前記アクセスポイントの前記識別子は、当該アクセスポイントのメディアアクセス制御（ＭＡＣ）アドレスを含むことを特徴とする請求項１７に記載のプログラム。
【請求項１】
移動装置によって実行される方法であって、
前記移動装置が位置する通信範囲内の現在のアクセスポイントを識別するステップと、
サーバから、前記移動装置の位置データベースであって第１のアクセスポイントに関連付けられた第１の位置を記憶する位置データベースの更新を、前記現在のアクセスポイントの識別子を用いて要求するステップと、
第２のアクセスポイントに関連付けられた第２の位置の集合を受信するステップと、を有し、前記第２の位置は、地理的グリッドの中心セル及び該地理的グリッドの該中心セルに隣接するセルに分布し、前記現在のアクセスポイントは、前記中心セル内の位置に対応し、前記中心セル及び該中心セルに隣接するセルは所定の地理的エリアをカバーしており、
前記方法は更に、
前記受信した位置の集合を用いて前記位置データベースを更新するステップと、
前記位置データベースを用いて前記移動装置の現在位置を計算するステップと、
を有することを特徴とする方法。
【請求項２】
前記位置データベースを用いて前記移動装置の現在位置を計算するステップは、
（ａ）前記移動装置の通信範囲内にあるアクセスポイントの識別子を受信するステップと、
（ｂ）前記移動装置の前記位置データベースから、前記アクセスポイントに関連付けられた第３の位置の集合を識別するステップと、
（ｃ）前記第３の位置の集合を用いて平均地理的位置を計算するステップと、
（ｄ）前記平均地理的位置と前記第３の位置の集合における各位置との間の距離を計算するステップと、
（ｅ）前記平均地理的位置と前記第３の位置のうちの少なくとも１つとの間の距離に基づいて、前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップと、
（ｆ）終了条件が満たされるまで、ステップ（ｃ）、（ｄ）、（ｅ）を繰り返すステップと、
（ｇ）前記平均地理的位置を中心とし、少なくとも１つの前記算出された距離に基づく半径に有する円を用いて、前記移動装置の前記現在位置を指定するステップと、
を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップは、
前記第３の位置の集合から除外する閾値割合を決定するステップと、
前記平均地理的位置から遠くに位置するものから、前記閾値割合の前記第３の位置を除外するステップと、
を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記終了条件は、前記繰返しの回数が閾値回数に達したときに満たされることを特徴とする請求項２に記載の方法。
【請求項５】
前記終了条件は、前記円の前記半径が閾値半径を下回ったときに満たされることを特徴とする請求項２に記載の方法。
【請求項６】
前記第３の位置の集合における各第３の位置は、緯度、経度、高度を含むことを特徴とする請求項２に記載の方法。
【請求項７】
前記移動装置の前記現在位置を、前記移動装置の地図表示装置に表示するステップを更に有することを特徴とする請求項１に記載の方法。
【請求項８】
前記アクセスポイントの前記識別子は、当該アクセスポイントのメディアアクセス制御（ＭＡＣ）アドレスを含むことを特徴とする請求項１に記載の方法。
【請求項９】
移動装置を含むシステムであって、
前記移動装置は、
前記移動装置が位置する通信範囲内の現在のアクセスポイントを識別するステップと、
サーバから、前記移動装置の位置データベースであって第１のアクセスポイントに関連付けられた第１の位置を記憶する位置データベースの更新を、前記現在のアクセスポイントの識別子を用いて要求するステップと、
第２のアクセスポイントに関連付けられた第２の位置の集合を受信するステップと、含む処理を実行するように構成され、前記第２の位置は、地理的グリッドの中心セル及び該地理的グリッドの該中心セルに隣接するセルに分布し、前記現在のアクセスポイントは、前記中心セル内の位置に対応し、前記中心セル及び該中心セルに隣接するセルは所定の地理的エリアをカバーしており、
前記移動装置は更に、
前記受信した位置の集合を用いて前記位置データベースを更新するステップと、
前記位置データベースを用いて前記移動装置の現在位置を計算するステップと、
を含む処理を実行するように構成されることを特徴とするシステム。
【請求項１０】
前記位置データベースを用いて前記移動装置の現在位置を計算するステップは、
（ａ）前記移動装置の通信範囲内にあるアクセスポイントの識別子を受信するステップと、
（ｂ）前記移動装置の前記位置データベースから、前記アクセスポイントに関連付けられた第３の位置の集合を識別するステップと、
（ｃ）前記第３の位置の集合を用いて平均地理的位置を計算するステップと、
（ｄ）前記平均地理的位置と前記第３の位置の集合における各位置との間の距離を計算するステップと、
（ｅ）前記平均地理的位置と前記第３の位置のうちの少なくとも１つとの間の距離に基づいて、前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップと、
（ｆ）終了条件が満たされるまで、ステップ（ｃ）、（ｄ）、（ｅ）を繰り返すステップと、
（ｇ）前記平均地理的位置を中心とし、少なくとも１つの前記算出された距離に基づく半径に有する円を用いて、前記移動装置の前記現在位置を指定するステップと、
を含むことを特徴とする請求項９に記載のシステム。
【請求項１１】
前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップは、
前記第３の位置の集合から除外する閾値割合を決定するステップと、
前記平均地理的位置から遠くに位置するものから、前記閾値割合の前記第３の位置を除外するステップと、
を含むことを特徴とする請求項１０に記載のシステム。
【請求項１２】
前記終了条件は、前記繰返しの回数が閾値回数に達したときに満たされることを特徴とする請求項１０に記載のシステム。
【請求項１３】
前記終了条件は、前記円の前記半径が閾値半径を下回ったときに満たされることを特徴とする請求項１０に記載のシステム。
【請求項１４】
前記第３の位置の集合における各第３の位置は、緯度、経度、高度を含むことを特徴とする請求項１０に記載のシステム。
【請求項１５】
前記処理は、前記移動装置の前記現在位置を、前記移動装置の地図表示装置に表示するステップを更に含むことを特徴とする請求項９に記載のシステム。
【請求項１６】
前記アクセスポイントの前記識別子は、当該アクセスポイントのメディアアクセス制御（ＭＡＣ）アドレスを含むことを特徴とする請求項９に記載のシステム。
【請求項１７】
移動装置に方法を実行させるためのプログラムであって、前記方法は、
前記移動装置が位置する通信範囲内の現在のアクセスポイントを識別するステップと、
サーバから、前記移動装置の位置データベースであって第１のアクセスポイントに関連付けられた第１の位置を記憶する位置データベースの更新を、前記現在のアクセスポイントの識別子を用いて要求するステップと、
第２のアクセスポイントに関連付けられた第２の位置の集合を受信するステップと、を含み、前記第２の位置は、地理的グリッドの中心セル及び該地理的グリッドの該中心セルに隣接するセルに分布し、前記現在のアクセスポイントは、前記中心セル内の位置に対応し、前記中心セル及び該中心セルに隣接するセルは所定の地理的エリアをカバーしており、
前記方法は更に、
前記受信した位置の集合を用いて前記位置データベースを更新するステップと、
前記位置データベースを用いて前記移動装置の現在位置を計算するステップと、
を有することを特徴とするプログラム。
【請求項１８】
前記位置データベースを用いて前記移動装置の現在位置を計算するステップは、
（ａ）前記移動装置の通信範囲内にあるアクセスポイントの識別子を受信するステップと、
（ｂ）前記移動装置の前記位置データベースから、前記アクセスポイントに関連付けられた第３の位置の集合を識別するステップと、
（ｃ）前記第３の位置の集合を用いて平均地理的位置を計算するステップと、
（ｄ）前記平均地理的位置と前記第３の位置の集合における各位置との間の距離を計算するステップと、
（ｅ）前記平均地理的位置と前記第３の位置のうちの少なくとも１つとの間の距離に基づいて、前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップと、
（ｆ）終了条件が満たされるまで、ステップ（ｃ）、（ｄ）、（ｅ）を繰り返すステップと、
（ｇ）前記平均地理的位置を中心とし、少なくとも１つの前記算出された距離に基づく半径に有する円を用いて、前記移動装置の前記現在位置を指定するステップと、
を含むことを特徴とする請求項１７に記載のプログラム。
【請求項１９】
前記第３の位置のうちの当該少なくとも１つを前記第３の位置の集合から除外するステップは、
前記第３の位置の集合から除外する閾値割合を決定するステップと、
前記平均地理的位置から遠くに位置するものから、前記閾値割合の前記第３の位置を除外するステップと、
を含むことを特徴とする請求項１８に記載のプログラム。
【請求項２０】
前記終了条件は、前記繰返しの回数が閾値回数に達したときに満たされることを特徴とする請求項１８に記載のプログラム。
【請求項２１】
前記終了条件は、前記円の前記半径が閾値半径を下回ったときに満たされることを特徴とする請求項１８に記載のプログラム。
【請求項２２】
前記第３の位置の集合における各第３の位置は、緯度、経度、高度を含むことを特徴とする請求項１８に記載のプログラム。
【請求項２３】
前記方法は、前記移動装置の前記現在位置を、前記移動装置の地図表示装置に表示するステップを更に有することを特徴とする請求項１７に記載のプログラム。
【請求項２４】
前記アクセスポイントの前記識別子は、当該アクセスポイントのメディアアクセス制御（ＭＡＣ）アドレスを含むことを特徴とする請求項１７に記載のプログラム。
【図１Ａ】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図２Ｄ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５】
【図６】
【図７】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図２Ｃ】
【図２Ｄ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５】
【図６】
【図７】
【公表番号】特表２０１３−５１７６９７（Ｐ２０１３−５１７６９７Ａ）
【公表日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願番号】特願２０１２−５４９０８６（Ｐ２０１２−５４９０８６）
【出願日】平成２３年１月１３日（２０１１．１．１３）
【国際出願番号】ＰＣＴ／ＵＳ２０１１／０２１１７２
【国際公開番号】ＷＯ２０１１／０８８２３３
【国際公開日】平成２３年７月２１日（２０１１．７．２１）
【出願人】（５０３２６０９１８）アップル インコーポレイテッド (568)
【Ｆターム（参考）】
【公表日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願日】平成２３年１月１３日（２０１１．１．１３）
【国際出願番号】ＰＣＴ／ＵＳ２０１１／０２１１７２
【国際公開番号】ＷＯ２０１１／０８８２３３
【国際公開日】平成２３年７月２１日（２０１１．７．２１）
【出願人】（５０３２６０９１８）アップル インコーポレイテッド (568)
【Ｆターム（参考）】
[ Back to top ]