ロケーションビーコンデータベースおよびサーバ、ロケーションビーコンデータベースを構築する方法、ならびにこれを使用するロケーションベースのサービス
【課題】ロケーションビーコンデータベースおよびサーバ、ロケーションビーコンデータベースを構築する方法、ならびにこれを使用するロケーションベースのサービスの提供。
【解決手段】少なくとも一の車両が、GPS装置およびWi−Fi無線装置を有する少なくとも一つのスキャニング装置と、Wi−Fiアンテナシステムとを備えて展開される。複数のWi−FiアクセスポイントからのWi−Fi信号を検出し、車両のGPS位置情報に関連して検出されたWi−Fiアクセスポイントの認識情報を記録する。Wi−Fi無線装置を備えるユーザ装置を測位することができる。目標エリアにおいて複数のWi−Fiアクセスポイントの算出された位置のリファレンスデータベースが提供される。このデータベースは、先に決定された位置の質を向上するために新しく加えられた位置情報で変更することができ、エラーを起こしやすい情報を避ける。
【解決手段】少なくとも一の車両が、GPS装置およびWi−Fi無線装置を有する少なくとも一つのスキャニング装置と、Wi−Fiアンテナシステムとを備えて展開される。複数のWi−FiアクセスポイントからのWi−Fi信号を検出し、車両のGPS位置情報に関連して検出されたWi−Fiアクセスポイントの認識情報を記録する。Wi−Fi無線装置を備えるユーザ装置を測位することができる。目標エリアにおいて複数のWi−Fiアクセスポイントの算出された位置のリファレンスデータベースが提供される。このデータベースは、先に決定された位置の質を向上するために新しく加えられた位置情報で変更することができ、エラーを起こしやすい情報を避ける。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、概してロケーションベースのサービスに関し、より詳しくは、Wi−Fiアクセスポイントの位置を決定し、この情報をWi−Fi対応装置の位置を検出するために使用する方法およびシステムに関する。
【背景技術】
【0002】
関連出願についてのクロス・リファレンス
本出願は、2004年10月29日に出願された米国仮特許出願第60/623,108号、「ロケーションビーコンデータベースを構築するためのワイヤレスデータスキャニングネットワーク」(本明細書に組み込まれる)の利益を35U.S.C. § 119(e)に基づき請求する。
【0003】
本出願は、上記出願と同日に出願された下記の発明の名称の米国特許出願に関する:
ロケーションビーコンデータベース;
ロケーションビーコンデータベースをアップデートするためのサーバ;
ユーザ装置の範囲内に検出されたアクセスポイントの数に基づきロケーションアルゴリズムを選択するロケーションベースのサービス;および
ロケーションビーコンデータベースのための方法およびシステム
【0004】
関連技術
近年、モバイルコンピュータの数が劇的に増加しており、より高度なモバイルおよびワイヤレスサービスの必要性が生じている。モバイルEメール、ウォーキートーキーサービス、マルチプレイヤ・ゲームおよびコールフォロイング(callfollowing)が、新しいアプリケーションがどのようにモバイル機器に現れているかを示す例である。更に、ユーザは、その現在地を利用するだけではなく、他人とその位置情報を共有するアプリケーションを求め始めている。親が子供の行方を監視したり、会社の管理者がこの会社の配達車両の位置を監視する必要があったり、出張旅行者が処方箋を受け取るため、最も近い薬局を見つけるために調べたりする。これらの例全ては、かれらが自身のまたは関係する他者の居場所を知る必要がある。現在に至るまで、我々は、誰かに方向を尋ねたり、我々の所在を尋ねるために誰かに電話したり、従業員に彼らの位置を時々報告させたりすることに全て依存している。
【0005】
ロケーションベースのサービスは、モバイルアプリケーションの新たに出現してきている分野であって、現在地を算出し、ユーザに報告する新しい装置の機能に影響している。これらのサービスの例としては、付近の天気、最新交通情報、走行方向、子供の追跡、位置特定(friendfinder)、都市案内サービスが含まれる。これらの新しい位置検出装置は、全て同じ一般的な概念を使用する様々な技術に依存している。既知のリファレンスポイント(基準点)から来る無線信号を使用して、これらの装置はこれらのリファレンスポイントと比較してユーザの位置を数学的に算出することができる。これらの方法はそれぞれ、無線技術および、測位アルゴリズムに基づく強みまたは弱点がある。
【発明の開示】
【発明が解決しようとする課題】
【0006】
米国政府が運用するグローバルポジショニングシステム(GPS)は、リファレンスポイントとして何ダースもの軌道衛星を利用している。これらの衛星は、複数のGPSレシーバによって受信される無線信号を同報する。レシーバは、信号がレシーバに届くまでの時間を測定する。3つ以上のGPS衛星から信号を受信した後、レシーバは地球上でその位置を三角測量することができる。このシステムが効率的に動作するために、無線信号は、その信号がほとんどまたは全く干渉されることなくレシーバに届かなくてはならない。レシーバは3つ以上の衛星へのクリアな見通しを必要とするため、天気、建築物および植物の葉が干渉となり得る。干渉は、多重通路として知られる現象によっても引き起こされ得る。衛星からの無線信号が物理的構造物に反射し、同一の衛星からの多重信号を異なる時間にレシーバに到達させてしまう。レシーバの算出は、信号がレシーバに届くまでの時間に基づいてなされるため、多重通路信号は、レシーバを混乱させ、重大なエラーを発生させてしまう。
【0007】
携帯電話中継地を利用した三角測量法は、ユーザまたは装置の位置を決定するために無線会社および携帯電話会社によって使用される別の方法である。無線ネットワークおよび携帯装置は、ネットワークがこの装置の位置を算出するために使用することができる信号情報を共有するために互いに通信する。これらの信号は目標地点への直線的見通しを必要とすることなく、建築物をより透過することができるため、この方法は、GPSに対する優位モデルとして当初は見られた。残念なことに、これらの方法は、多重通路信号の問題および携帯電話中継地の測位においての画一性の欠如の問題に加え、携帯電話中継地は本質的に不均一なために最適ではないことが証明されている。
【0008】
アシスト付きGPS(Assisted GPS(A−GPS))はGPSと携帯電話中継地の両方の技術を組み合わせた更に新しいモデルであって、モバイルユーザのより正確かつ信頼性の高い位置の算出を行う。このモデルにおいて、無線ネットワークは、GPS衛星の時計オフセットについての情報と、接続された携帯電話中継地の位置に基づくユーザの一般的な位置についての情報とを送信することによってGPSが信号受信を改善することを助ける試みである。これらの技術は、GPSレシーバが、屋内にいるときなどに経験する弱い信号を処理することを助け、レシーバが最も近い衛星の「固定(fix)」を迅速に得て、より速い「第1の読み込み(firstreading)」をする。これらのシステムは、都心から100メートル以上離れた所では応答時間が遅く、正確性に欠けるという問題に悩まされている。
【0009】
GPS、A−GPSおよび携帯電話中継地を利用した測位の公知の問題を解決すべく開発された最近の代替モデルがいくつかある。その一つとして、TV−GPSとして知られるものは、テレビ塔からの信号を利用する。(例えば、Muthukrishnan,MariaLijding,Paul Havinga,TowardsSmart Surroundings:EnablingTechniques および Technologies for Localization,Lecture Notes in Computer Science,Volume3479,Jan 2Hazas,M.,Scott,J.,Krumm,J.:Location−AwareComputing Comes of Age. IEEEComputer, 37(2):95−97,Feb2004 005,Pa005,Pages350−362を参照。)このコンセプトは、ほとんどの都市部には3つ以上のテレビ塔があるという実状に依存している。専用のハードウェアチップが、様々なテレビ塔から出るテレビ信号を受信し、リファレンスポイントとしてこれらのテレビ塔の既知の位置を利用する。この方式に直面する問題は、新しいハードウェアレシーバのコストと、リファレンスポイントの少ない一組を使用することによる制約である。例えば、ユーザがテレビ塔の周辺部の外にいる場合、このシステムは妥当な精度を出すのに困難な場合が見られる。この典型的な例は、海岸線にいるユーザである。海にはテレビ塔がないため、リファレンスポイントにおいて基準対称性(referencesymmetry)を提供することができず、内陸のユーザのほうがより正確に位置を算出することができる。
【0010】
マイクロソフト社およびインテル社は(PlaceLabとして知られる調査団体を介して)、Wi−Fiスキャンデータを公衆の共有ウェブに提供するアマチュアユーザ(「ウォードライバー」(wardrivers)として知られる)から得られるアクセスポイントの位置を使用するWi−Fi測位システムを開発した。(例えば、LaMarca,A.,et.al.,PlaceLab: Device Radio Using RadioBeacons in the Wildを参照。) 例としてはWiGLE、Wi−FiMaps.com、Netstumbler.comおよびNodeDBが含まれる。マイクロソフト社およびインテル社の両社は、公衆のウォードライビングデータを基準位置として利用する同社のクライアントソフトウェアを開発した。個人がそのデータを自発的に供給するため、このシステムは、多くの性能および信頼性の問題が生じる。第1に、データベースのデータは、同時期に存在しておらず、一部のデータは、新しく、別の部分は3〜4年前のデータである。時間が経過すると、アクセスポイントは移動され、削除されるため、アクセスポイントの位置の新しさが重要となる。第2に、そのデータは、様々なハードウェアおよびソフトウェアを使用して作られていることである。全ての802.11無線装置およびアンテナは、信号の強さの表示に影響を及ぼす異なる信号受信特性を備えている。各スキャニングソフトウェアインプリメンテーションは異なる時間間隔に異なる様式でWi−Fi信号をスキャンする。第3に、ユーザによって供給されたデータは、幹線の偏り(arterialbias)を被る。望ましいスキャンルートに従わない個人によって自己申告されているので、そのデータは交通量の激しい地域周辺に集まる傾向がある。幹線の偏りは、ユーザが現在どこにいるかに関わらず、結果として得られる位置を主要幹線道路に向かって引っ張ってしまい、重大なエラーを引き起こしてしまう。第4に、これらのデータベースは、スキャンされたアクセスポイントの算出された位置を含んでおり、802.11ハードウェアで得られる未処理のスキャンデータではない。これらのデータベースのそれぞれは、アクセスポイントの位置を異なって算出し、基礎的な重み付き平均方程式で算出される。結果として、多くのアクセスポイントは実際の位置から離れた位置であるように表示され、それらには、あたかも水中に位置しているように間違って表示されたいくつかのアクセスポイントも含まれる。
【0011】
屋内測位用のWi−Fi測位システムは商業的に多く出回っている。(例えば、Kavitha Muthukrishnan,MariaLijding,Paul Havinga,TowardsSmart Surroundings:EnablingTechniques および Technologies for Localization,Lecture Notes in Computer Science,Volume3479,Jan 2Hazas,M.,Scott,J.,Krumm,J.:Location−Aware Computing Comes ofAge.IEEE Computer,37(2):95−97,Feb2004005,Pa005,Pages 350−362を参照。)これらのシステムは、資産(asset)および人をアドレス指定し、会社の敷地、病院、出荷所といった管理される環境内で監視するように設計されている。この典型的な例は、病院内で緊急用カートの正確な位置を監視することができるシステムであって、心停止があった場合に病院のスタッフが時間を無駄にすることなくそのカートを見つけることができるようにするものである。こうした使用の場合に要求される精度は、一般的に1〜3メートルの精度を要求する非常に高いものである。これらのシステムは、精度を微調整するための様々な技術を使用し、それには無線信号伝搬を測定するために敷地の1平方フィート毎の詳細な実地調査を行うことが含まれる。それらは、一定のネットワーク接続が必要であり、アクセスポイントおよびクライアント無線装置が、A−GPSの作動の仕方に類似する同期情報を交換する。これらのシステムがこれらの屋内の場面で信頼性を高めてきたが、広域にて展開するには効果的ではない。一都市全体に亘って求められるそのような詳細な実地調査を行うことは、不可能であり、都市圏全体に亘って802.11アクセスポイントと一定に通信するチャネルを、これらのシステムに要求されるようには信頼することができない。最も重要なこととして、屋外の電波の伝搬は、屋内の電波の伝搬とは基本的に異なっており、これらの屋内測位アルゴリズムは広域のケースにおいてはほぼ役に立たない。
【0012】
GPS位置の読み込み値と共に802.11信号の存在を記録するのに利用可能である数多くの802.11位置スキャニングクライアントがある。これらのソフトウェアアプリケーションは、手動で操作され、読み取り値のログファイルを生成する。これらのアプリケーションの例としては、Netstumber、KismetおよびWi−FiFoFumがある。一部の愛好者は、かれらが検出して互いに共有する802.11アクセスポイントの位置をマーキングするためにこれらのアプリケーションを使用する。このデータの管理および情報の提供は、全て手動でなされる。これらのアプリケーションは、アクセスポイントの物理的な位置について計算を行なわず、アクセスポイントが検出される位置を単にマーキングするのみである。
【0013】
基礎をなす測位システムの性能および信頼性は、ロケーションベースのサービスが良好に展開する重要な要素である。性能とは、所与の使用の場合にこのシステムが達成する精度レベルのことを指す。信頼性とは、所望の性能レベルが達成される時間率(percentageof time)のことを指す。
【課題を解決するための手段】
【0014】
本発明は、ロケーションビーコンデータベースおよびサーバを提供し、ロケーションビーコンデータベースの構築およびこれを使用するロケーションベースのサービスの方法である。
【0015】
本発明の一態様において、Wi−Fiアクセスポイントが、Wi−Fiアクセスポイントの位置のリファレンスデータベースを構築するために、地理的標的エリアに測位される。少なくとも一の車両が、GPS装置およびWi−Fi無線装置を有する少なくとも一つのスキャニング装置と、Wi−Fiアンテナシステムとを備えて展開される。この目標エリア内を、幹線の偏りを避けるためにプログラムされたルートで移動する。このプラグラムに基づいたルートは、地理的目標エリアの実質的に全ての走行可能な道路を含み、かつ、前記走行可能な道路によって示されるグラフのオイラーサイクル(Euleriancycle)問題を解くものである。目標地エリア内を移動する間、GPS装置のGPS座標を周期的に受信する。目標地域を移動する間、Wi−Fi装置の範囲において複数のWi−FiアクセスポイントからのWi−Fi信号を検出し、これらのWi−FiアクセスポイントからのWi−Fi信号が検出された場合に、車両のGPS位置情報に関連して検出されたWi−Fiアクセスポイントの認識情報を記録する。この位置情報は、検出されたWi−Fiアクセスポイントの位置を逆三角測量(reversetriangulate)するために使用され、検出されたアクセスポイントの位置は、リファレンスデータベースに記録される。
【0016】
本発明別の態様において、地理的目標エリアは、およそ数十マイルの半径を有する。
【0017】
本発明別の態様において、プログラムに基づいたルートは、チャイニーズポストマンルーティングアルゴリズムを使用して決定される。
【0018】
本発明別の態様において、Wi−Fi信号を検出した場合に、一組の読み取り値がこの所与のWi−Fiアクセスポイントのために生成されるように複数のWi−Fi信号の読み取りが所与のWi−Fiアクセスポイントのためになされ、この一組の読み取り値は、検出されたWi−Fiアクセスポイントの位置を決定するときに使用される。
【0019】
本発明別の態様において、Wi−Fiアクセスポイントを検出した場合、このWi−Fiアクセスポイントからの信号についての信号強度情報がスキャニング装置によって算出され、記録される。
【0020】
本発明別の態様において、走行可能な道路の組織が与えられる場合に可能な限り多くの異なる角度から検出される。
【0021】
本発明別の態様において、所与のWi−Fiアクセスポイントは、走行可能な道路の組織が与えられる場合に可能な限り多くの異なる角度から検出されて、所与のWi−Fiアクセスポイントのための信号強度の電力プロファイルが決定され、記録される。
【0022】
本発明別の態様において、Wi−Fiアンテナシステムは、複数の指向性アンテナを含んでおり、スキャニング装置は、この指向性アンテナ上でWi−Fiアクセスポイントによって受信される異なる信号強度に基づき、前記Wi−Fiアクセスポイントの出所のベクトルを記録する。
【0023】
本発明別の態様において、アクセスポイントは、複数の目標エリアのために測位される。
【0024】
本発明別の態様において、Wi−Fi無線装置を備えるユーザ装置を測位することができる。目標エリアにおいて複数のWi−Fiアクセスポイントの算出された位置のリファレンスデータベースが提供される。Wi−Fi無線装置を備えるユーザ装置の位置を決定するためのユーザアプリケーション要求に応答して、Wi−Fi無線装置の範囲内の全てのWi−Fiアクセスポイントに要求を送信するためにWi−Fi無線装置を起動させる。Wi−Fi装置の範囲内において前記Wi−Fiアクセスポイントからからのメッセージを受信する(ここで、各メッセージはこのメッセージを送るWi−Fiアクセスポイントを特定するものである)。前記Wi−Fiアクセスポイントによって受信されたメッセージの信号強度を算出する。認識されたWi−Fiアクセスポイントの算出された位置を獲得するためにリファレンスデータベースにアクセスする。受信されたメッセージを介して認識されたWi−Fiアクセスポイントの数に基づいて、複数の位置決定アルゴリズムから対応する位置決定アルゴリズムを選択する(ここで、この選択されたアルゴリズムは、認識されたWi−Fiアクセスポイントの数に適するものである)。前記ユーザ装置の位置を決定するために、前記認識されたWi−Fiアクセスポイントの算出された位置、前記受信されたメッセージの信号強度、および前記選択された位置決定アルゴリズムを使用する。
【0025】
本発明の別の態様において、認識されたWi−Fiアクセスポイントの算出された位置は、Wi−Fiアクセスポイントについての時間情報が前記リファレンスデータベースに含まれているため、前記対応するWi−Fアクセスポイントが移動したか否かを決定するためにフィルタにかけられる。
【0026】
本発明の別の態様において、複数の位置決定アルゴリズムは、簡素な信号強度の重み付き平均モデルを含む。
【0027】
本発明の別の態様において、複数の位置決定アルゴリズムは、直近のモデルを含む。
【0028】
本発明の別の態様において、複数の位置決定アルゴリズムは、三角測量技術を含む。
【0029】
本発明の別の態様において、複数の位置決定アルゴリズムは、装置の速度に基づき適応可能な平滑化技術を含む。
【0030】
本発明の別の態様において、位置決定アルゴリズムの選択は、更に、位置要求を生成するユーザアプリケーションに基づく。
【0031】
本発明の別の態様において、およそ数十マイルの半径を有する少なくとも一つの目標地域のためのWi−Fiアクセスポイントのデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのWi−Fiアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するWi−Fiアクセスポイントの認識情報と、この対応するWi−Fiアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Wi−Fiアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Wi−Fiアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぐ。
【0032】
本発明の別の態様において、Wi−Fi位置サーバは、およそ数十マイルの半径を有する少なくとも一つの目標地域のためのWi−Fiアクセスポイントのデータベースを備えており、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのWi−Fiアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するWi−Fiアクセスポイントの認識情報と、この対応するWi−Fiアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Wi−Fiアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Wi−Fiアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぎ、新しく発見されたWi−Fiアクセスポイントのために前記データベースに記録を加えるためのコンピュータで実行される論理を備えており、このコンピュータ論理は、新しく発見されたWi−Fiアクセスポイントのための前記位置情報を利用するため、前記データベースに以前格納されたWi−Fiアクセスポイントの位置情報を再算出するための論理を含む。
【0033】
本発明の別の態様において、サーバは、エラーを起こしやすいGPS情報に基づき位置情報を認識するために、コンピュータで実行されるクラスター化論理を更に備える。
【0034】
本発明の別の態様において、クラスター論理は、アクセスポイントのために報告された全ての位置情報のために重み付けされた重心位置を決定するための論理と、前記重心から離れる統計に基づく偏差の閾値を超える位置情報を認識する論理とを含み、偏っている位置情報をデータベースから除外し、Wi−Fiアクセスポイントの算出された位置に影響を与えないようにする。
【図面の簡単な説明】
【0035】
【図1】図1は、Wi−Fi測位システムの特定の実施例を示す。
【図2】図2は、本発明の特定の実施例による、スキャニング装置を備えるスキャニング車両を示す。
【図3】図3は、データ収集における幹線の偏りの問題点を示すためのスキャニングシナリオの一例を示す。
【図4】図4は、本発明の特定の実施例によるスキャニング車両用のプログラムに基づいたルートを使用する一例を示す。
【図5】図5は、ユーザ装置の測位においてWi−Fiアクセスポイントの基準対称性(referencesymmetry)の欠如の問題を例示するためのシナリオの一例を示す。
【図6】図6は、ユーザ装置の測位においてWi−Fiアクセスポイントの基準対称性を例示するためのシナリオの一例を示す。
【図7】図7は、本発明の特定の実施例による、スキャニング装置を備えるスキャニング車両を示す。
【図8】図8は、本発明の特定の実施例による、Wi−Fiアクセスポイントの中央データベースを有する中央ネットワークサーバを示す。
【図9】図9は、本発明の特定の実施例による、測位ソフトウェアの例示的な構造を示す。
【図10】図10は、本発明の特定の実施例による、スキャニングクライアントの例示的な構造を示す。
【図11】図11は、ランダムスキャニングモデルの効果をチャイニーズポストマンルーティングアルゴリズムのモデルを使用するものとの比較、対比を示す。
【発明を実施するための最良の形態】
【0036】
本発明の好適な実施例は、公共および個人の802.11アクセスポイントを使用して、商業的な測位システムを可能とするために基準位置データを収集するためのシステムおよび方法を提供する。好適には、このデータは、目標地域の道路を完全に探査し、カバーするためにプログラムに基づいた方法で収集される。このプログラムに基づいた方法によって、可能な限り多くのWi−Fiアクセスポイントを認識する。より多くのアクセスポイントについての位置情報を収集することによって、好適な実施例は、このアクセスポイントについての位置情報の多大な収集を提供するだけではなく、各アクセスポイントのための位置情報をより精度を増して算出することができる。その後、この精度の高いデータの大きな1セットは、本発明の好適な実施例を利用して、ユーザ装置をより正確に測位するようにロケーションサービスによって使用される。特定の実施例は、Wi−Fi位置の決定において間違ったデータを避けるための技術を使用し、かつ先に収集され決定された位置情報の質を改善するために、新しく発見された位置を利用する。特定の実施例は、ユーザが位置を要求した時にユーザ装置の状況に基づき位置決定アルゴリズムを使用する。例えば、この位置決定アルゴリズムは、位置要求がなされたときに認識または検出されるWi−Fiアクセスポイントの数に基づくか、またはその要求を出すアプリケーションに基づく。
【0037】
図1は、Wi−Fi測位システム(Wi−Fi positioning system (WPS))の好適な実施例の一部を示す。この測位システムは、コンピュータであるユーザ装置101に収容されている測位ソフトウェア103を含む。特定のカバレージエリア(有効範囲)全体に亘って、制御/共通チャネル同報信号を使用して情報を同報する複数の固定ワイヤレスアクセスポイント102がある。このクライアント装置は、同報信号を監視するか、または、精査要求(proberequest)を経てその送信を要求する。各アクセスポイントは、MACアドレスとして知られる固有のハードウェア識別子を含む。クライアント測位ソフトウェアは、範囲内にある802.11アクセスポイントから信号ビーコンを受信し、信号ビーコンからの特性を利用してコンピュータの地理的位置を算出する。これらの特性には、MACアドレスとして知られる802.11アクセスポイントの固有の識別子と、クライアント装置に達する信号の強度が含まれる。クライアントソフトウェアは、観測された802.11アクセスポイントをアクセスポイントのリファレンスデータベース104内のものと比較する。このリファレンスデータベース104は、その装置に収容されていてもされなくてもよい。このリファレンスデータベースには、算出された地理的位置または、収集システムが収集した全てのアクセスポイントの電力プロファイルが含まれる。この電力プロファイルは、様々な位置から出る信号の電力を表示する読み取り値の集合である。これらの既知の位置を利用して、クライアントソフトウェアはユーザ装置101の相対位置を算出し、緯度と経度の読み取り値でその地理的座標を決定する。次に、これらの読み取り値は、ロケーションベースのアプリケーション(例えば、位置特定(フレンドファインダー)、ローカルサーチウェブサイト、フリートマネジメントシステムおよびE911サービス)に供給される。
【0038】
この測位ソフトウェア103は、図9により詳細に記載されており、この構成要素が例示されている。位置読み取り値を利用して、エンドユーザにある値(例えば走行方向)を提供する、アプリケーションもしくはサービス901が一般的に存在する。この位置(ロケーション)アプリケーションは、瞬間的にその装置の位置を測位ソフトウェアに求める。この要求によって、その装置の802.11無線装置903に「スキャン要求」を行うスキャナー902が起動される。この802.11無線装置は、その範囲内の全ての802.11アクセスポイント904に探査要求(proberequest)を送る。802.11プロトコルに従って、探査要求を受信したこれらのアクセスポイントは、アクセスポイントについての情報を含む同報ビーコン(broadcastbeacon)を発信する。このビーコンには、装置のMACアドレス、ネットワーク名、それがサポートするプロトコルの正確なバージョン、およびその装置にどのように接続するかについての情報と共にセキュリティ構成が含まれる。この802.11無線装置は、応答する各アクセスポイントからこの情報を収集し、各アクセスポイントの信号強度を算出し、それをスキャナーに返送する。
【0039】
このスキャナーは、この複数のアクセスポイントの配置情報をロケータ906に渡し、このロケータ906は、アクセスポイントレファレンスデータベース905に対して、観測された各アクセスポイントのMACアドレスをチェックする。このデータベースは、その装置に収容されているか、またはネットワーク接続上に離れて収容されている。このアクセスポイントレファレンスデータベースは、このシステムに既知である観測された各アクセスポイントの位置データを戻す。このロケータは、各アクセスポイントから返信される信号特性と共にこの位置情報の集積を不良データフィルタ(BadData Filter)907に渡す。いずれかのアクセスポイントがアクセスポイントデータベースに加えられてから移動したか否かを決定するために、このフィルタは、各アクセスポイントに対して多くの比較テストを行う。不良データ記録を取り除いた後に、フィルタは、残りのアクセスポイントを位置算出要素908に送る。アクセスポイントデータベースから提供されるリファレンスデータおよびスキャナーから提供される信号強度読み取り値を用いて、位置算出要素がその時のこの装置の位置を計算する。ロケータに返信される前に、この位置データは、過去の一連の位置読み取り値を平均し、先の算出からの読み取り誤差を除去するために平滑化(スムージング)エンジン909によって処理される。調整された位置データは、次にロケータに返信される。
【0040】
ロケータによって生成されたこの算出された読み取り値は、アプリケーションプログラミングインターフェース(API)を含むアプリケーションインターフェイス910を通して、またはバーチャルGPS機能911を介して、これらのロケーションベースのアプリケーションに伝達される。GPSレシーバは、独自のメッセージを使用して、または、ナショナル・マリン・エレクトロニクス・アソシエーション(NationalMarine ElectronicsAssociation(NMEA)) によって開発されたような測位規格を使用して、位置読み取り値を伝達する。機器のCOMポートといった標準インターフェースを使用する装置に接続することによってメッセージを読み出す。本発明の特定の実施例には、いかなるGPS汎用アプリケーションも通信モデルまたはメッセージを変化させることなくこの新しい測位システムと通信することができるバーチャルGPS機能が含まれる。
【0041】
この位置算出は、ノイズの多いデータフローを信頼性かつ安定性のある位置読み取り値に変えることを目的とする一連の測位アルゴリズムを使用してなされる。クライアントソフトウェアは、観測されたアクセスポイントのリストを算出された信号強度と共に比較し、この装置のユーザの正確な位置を決定するためにユーザの位置を重み付けする。様々な技術が使用され、これには、簡潔な信号強度に重み付けされた平均モデルと、三角測量方式技術と組み合わされる最近傍モデルと、装置速度に基づいて適合可能な平滑化とが含まれる。シナリオが異なる場合は、異なるアルゴリズムの方がうまく機能し、最も正確な最終読み取り値を生成するために混成して使用される傾向にある。本発明の好適な実施例は、多くの測位アルゴリズムを使用することができる。どのアルゴリズムを使用するかの決定は、観測されたアクセスポイントの数と、それを使用しているユーザケースアプリケーションとによる。従来のシステムは、移動することのない既知のリファレンスポイントに頼っているため、このフィルタモデルは従来の測位システムとは異なる。好適な実施例のモデルにおいて、アクセスポイントが固定された位置にあるという仮定はなされず、アクセスポイントは測位システムによって所有されておらず、これらのアクセスポイントを移動またはオフラインにしてもよい。このフィルタリング技術は、もはやいくつかのアクセスポイントが同じ場所に位置しなくてもよく、位置が不良算出されてもよい。よって、このフィルタアルゴリズムは、アクセスポイントの位置が記録された後に移動したアクセスポイントを隔離しようとする。このフィルタは、動的であって、その時に観測されたアクセスポイントの数に基づき変更する。平滑化アルゴリズムは、単純な平均位置算出と、カルマンフィルタを含む高度なベイズの論理とを含む。速度アルゴリズムは、各アクセスポイントの信号強度観測値からドップラー効果を推定することによって装置の速度を算出する。
【0042】
基準データベースを構築するためのスキャンデータの収集
図2は、様々なアクセスポイントの位置情報を収集するために使用される要素を示している。多くの車両201からなる一隊が、測位システムのためのリファレンスデータベース(図1の104)を構築するために展開される。これらの車両201は、目標スキャンエリアを通してプログラムに基づいたルートをたどり、質の高いデータを生成する最適な方法でデータを収集する。この目標スキャンエリアは典型的に、半径15〜20マイル内の全ての走行可能な道路を含む大都市圏である。これらの車両は、カバレージエリアを移動する間に802.11信号の位置および特性を記録するように設計されたスキャニング装置202を備えている。このスキャニング装置は、GPS衛星204からの信号を使用して毎秒スキャニング車両の位置を追跡する。このスキャニング装置は、カバレージエリア内のいかなる802.11アクセスポイントの所在も追跡し、スキャン車両のGPS位置と、アクセスポイント信号の無線特性とを記録する。収集されたデータの品質は、スキャン車両に備えられるスキャン方法によって多大に影響される。各モデルは、それぞれ利点および制限がある。ランダムモデル(RandomModel)として知られる一つの方法は、車両は商用または私用で日常的に稼動することから、車両にスキャニング装置を配置するものである。これらの車両は、配達用トラック、タクシー、セールスマンまたは単に愛好家となり得る。このコンセプトは、これらの車両が、信頼性のあるリファレンスデータベースを構築するためにそれら自体のランダムな方法で時間が経つにつれて十分な道路をカバーしているであろうとするものである。このモデルは、データを収集するための簡略的な手段を実際に提供するが、結果として得られるデータの品質は、「幹線の偏り(arterialbias)」の問題のために悪影響を受ける。図3は、このランダムモデルの課題を示している。スキャニング車両が、データを収集するよりもむしろ他の課題を解決するために設計されたルートを移動する場合(例えば、荷物の配達、出勤、帰宅)、それらは、「目的地ルート」をたどる傾向にある。目的地ルートは、ドライバーがAからBに行く必要がある場合であってかつそこに行くための最速ルートを求める場合のルートである。よって、ドライバーは、それが高速道路であるか大通りであるかに関わらず、最も近い主要幹線に行くための最短ルートを探す。結果として、時が経つにつれて、このランダム走行は、累積的なカバレージによってますます多くの面積をカバーし、主要道路または幹線道路に偏っておりすなわちバイアスがかかっており、より小さい周囲の道路をなおざりにしている。図3において、幹線道路304および305は、スキャニング車両が非常に激しく通過しており、これらの道路用に好ましい量のスキャニングデータが得られる。しかし、道路306および307は、カバーされることがあるとしてもまれであって、なぜなら、これらの道路上には頻繁に訪れるような目的地がなく、かつ幹線道路のほうが移動に使う道としては適しているからである。結果として、アクセスポイント308および309は、スキャニング車両によって全くスキャンされておらず、この測位システムは、この道路306および307を移動するユーザを認識するのに苦戦する。その結果として、システムがスキャンデータからアクセスポイントの位置を算出することを試みる場合、入力データの偏って収集したものに限定される。図11は、結果として得られるデータ品質の相違を示す。スキャニング車両のドライバーがアクセスポイント1101の近くを通過したときに、読み取り値およびその位置を連続的に記録する。この測位システムは、次に、全ての観測されたデータ1103のセットを用いてアクセスポイント1102の位置を算出しなくてはならない。ランダムスキャニングモデルにおいては、このデータのセットはアクセスポイントを通り過ぎる一本の主要道路に限定される。それによって、このシステムにアクセスポイントの位置をこのアクセスポイント自体の近辺ではなくむしろその道の近くになるように強制的に算出させてしまう。
【0043】
別の方法としては、結果として得られるデータの収集において偏りを避けるために、目標地域のありとあらゆる道路を含むルーティングアルゴリズムを開発することであって、よってエンドユーザのためにより信頼性のある測位システムを構成することである。図4は、目標地域においてありとあらゆる道路をカバーするために最も効率的な走行ルートを算出するために、チャイニーズポストマンとして知られる最適化されたルーティングアルゴリズムを記載する。このチャイニーズポストマンルーティングアルゴリズムは、郵便機関、公共事業および国勢調査機関によって使用される公知の技術であって、オイラーサイクル問題の異型である。このオイラーサイクルは、各縁部を少なくも一回訪れる、図の最短移動を求める問題である(例として、Kwan,M.K.”Graphic ProgrammingUsing Odd or Even Points.”ChineseMath. 1,273−277,1962.を参照)。本発明の好適な実施例は、カバレージのための目標領域を認識して、車両ルートを設計するためにチャイニーズポストマンルーティングアルゴリズムを使用するための方法を含む。このスキャニング車両401は、アルゴリズムによる最適なルートをたどり、全ての観測可能なアクセスポイントがそのシステムによって検出されて地図にされることを確実にし、全ての道路に偏りがないことを示す。よって、例えば、アクセスポイント408および409は、チャイニーズポストマンモデルを使用してアクセスポイントデータベースに加えられるが、ランダムモデルを使用していたら、欠落していたかもしれない。図11を参照すると、チャイニーズポストマンスキャニングモデルでは、車両はありとあらゆる道路を通過し、アクセスポイント1104用の1セットのスキャニング記録1106を完成させる。このシステムは、次にアクセスポイントの位置1105をエラーを少なくして算出することができ、なぜならそれは、アクセスポイント1102に比してアクセスポイント1104のスキャンデータがより画一的に分布しているためである。よって、このチャイニーズポストマンスキャニングモデルは、目標地域に亘ってより画一的により多くのアクセスポイントを収集するだけではなく、結果として得られるデータによってアクセスポイント位置がより正確に算出されるのである。
【0044】
高品質APロケーション
このスキャニングデータは、一旦収集(または部分的に収集)されると、中央アクセスポイントデータベース(後述される)に戻ってアップロードされ、そこで処理される。各アクセスポイントのための未処理の観測点は、アクセスポイントの実際の物理的な位置を逆三角測量(reversetriangulate)するために使用されるか、アクセスポイントの電波の伝搬を示す電力プロファイルを生成するために使用される。特定のアクセスポイント用に最も正確に算出された位置を生成するかまたは最も正確な電力プロファイルを生成するために、スキャニング車両は出来る限り多くの異なる角度からアクセスポイントを観測しなくてはならない。ランダムモデル(図3)において、多くのアクセスポイントがたった一つの道路から観測され、このシステムは道路303上で直接それらの位置を算出しなくてはならない。これらの位置は、方向の偏り呈し、これらのアクセスポイント302の実際の位置とは著しく異なる。そのリファレンスポイントの位置が不正確である場合、測位システムにエラーがもたらされる。よって、この測位システムにおいて、アクセスポイント位置の精度がエンドユーザ測位の精度に大きな役割を果たす。チャイニーズポストマンモデル(図4)を使用して、スキャニング車両は、アクセスポイントを収容している建物に対して可能な限り多くの方向から特定のアクセスポイントを検出する。この追加データは、アクセスポイント403の位置を算出するために使用される逆三角測量公式によって導き出される結果を著しく改善する。アクセスポイント位置品質は図11により詳細に記載されている。
【0045】
このシステムから収集されたスキャニングデータは、その特定の環境において各アクセスポイントの信号伝搬パターン用の信頼性のあるプロキシを示す。全ての無線装置および関連する周囲環境は、固有の信号指紋(signalfingerprint)を生成し、この信号指紋は、信号がどのくらい遠くまで届くか、信号指紋内の様々な位置において信号がどのくらい強いかを示す。この指紋データは、測位システムが高精度に機能するように、算出されたアクセスポイント位置に関連して使用される。この指紋は、「電力プロファイル」としても知られており、それは、各位置の信号強度が信号電力としてワットで測定されるからである。この測位システムは、802.11アクセスポイント無線装置の特定の信号強度がそのアクセスポイントからの特定の距離を関係していることを示すために指紋データを解析する。信号指紋技術が屋内Wi−Fi測位において使用されるが、その指紋の収集に関連して難点があるため、より広いエリアの屋外環境において再現することが困難であることが分かった。複数のアクセスポイントの指紋または電力プロファイルがオーバーレイする場合に、この測位システムは、観測された複数の信号強度が、結合された複数の指紋にマッチする一地点をみつけることのみによって、その装置の位置を決定することができる。本発明の好適な実施例は、指紋に基づく測位アルゴリズムを使用するために何百万ものアクセスポイントを伴う巨大なカバレージエリアに亘ってこの指紋データを獲得するために信頼性のあるシステムを提供する。
【0046】
基準対称性
測位システムは一般的に、追跡される装置の周囲の3つ以上のリファレンスポイントを備えることによって動作する。この測位システムは、その装置の現在位置を算出するために様々な方法においてこれらのリファレンスポイントからの無線信号を使用する。リファレンスポイントの数が十分でない場合、またはリファレンスポイントがユーザの周囲のバランスもしくは対称性を欠く場合に、顕著なエラーが発生する。図5において例示されるように、ランダムなモデルから現れる幹線の偏りにおいて、エンドユーザ501が、その一方向にのみ記録されたアクセスポイント位置502がある物理的エリア内に移動する場合が多く考えられる。エンドユーザの周囲のリファレンスポイントの分布におけるこの対称性の欠如によって、測位アルゴリズムは多大なエラーを伴って装置位置503を算出してしまう。アクセスポイント用にスキャニングのチャイニーズポストマンモデルを使用することによって、ユーザは一般的に、その装置の802.11無線装置の範囲604内のユーザ601の全ての方向に多くのアクセスポイント位置602が存在する物理的な位置(図6)に出る。結果として得られた位置算出603は、位置の偏りを減少させ、より正確になる。図11は、位置算出の品質における影響を示す別の例である。
【0047】
スキャニング装置
図7は、様々なWi−Fiアクセスポイントを検出し、認識するために使用されるスキャニング装置702の好適な実施例の詳細を記載している。スキャニング車両701は、GPS衛星708および802.11アクセスポイント707からの無線信号のチャンネルを連続的にスキャンするスキャニング装置702を備えている。このスキャニング装置は、全工程を制御するスキャニングクライアントソフトウェア704を作動する。このスキャニングクライアントは、GPSレシーバ705および802.11無線装置706の両方を作動させる。このGPSレシーバは、2秒毎にその装置の地理的位置を算出する連続的な受信モードにセットされる。その算出は、スキャニングクライアントによって読み込まれ、ローカルデータ格納部703に格納される。スキャニングクライアントは、802.11無線装置を起動し、指向性アンテナ709を用いて802.11探査要求(proberequest)を送信し始める。そのプローブ要求の範囲内の802.11アクセスポイント707が802.11プロトコルに従って信号ビーコンを伴って応答する。この応答する信号ビーコンには、アクセスポイントのネットワーク名(SSIDとして知られる)と、アクセスポイント装置のMACアドレスと、アクセスポイントについての他のメタ情報とが含まれる。応答する信号は、出所のベクトルおよびアクセスポイントの近接度に基づき、信号の異なる強度を伴って指向性アンテナに到達する。そのベクトルは、その特定のアンテナの認識と、アクセスポイントについてのメタ情報と共に記録される。この探査−受信‐記録処理は、10分の一秒毎に連続してなされる。配備されるスキャニング装置は、XTracv.2.0 firmwareを備える一体化されたSiRFII type GPS レシーバを備えるiPAQ 4155 Pocket PCとPowered GPS PDA Mount Cradleとの組合せである。
【0048】
特定の実施例のスキャニングクライアント704は、図10に記載されている。クライアントは、データマネージャ(DataManager)1001、システムマネージャ(System Manager)1002およびアップロードマネージャ(Upload Manager)1003の3つの主要部からなる。データマネージャ1001は、GPS無線装置1006および802.11無線装置1007の両方の動作を制御する。データマネージャは、いつ、どのくらいの頻度で、これらの無線装置が信号をスキャンし、これらの信号を処理するかを制御する。一旦起動されたGPS無線装置は、複数のGPS衛星1004から信号を受信し、このGPS無線装置の地理的位置を算出する。GPSレコーダ1008は、2秒毎にこれらの読み取り値の全てをログ記録し、それらをファイルマネージャ1010に送る。Wi−Fiレコーダ1009は、802.11無線装置を一秒の10分の一秒毎にスキャンするように起動させ、これらの802.11読み取り値をGPS無線装置から来るGPS読み取り値に関連付け、結果として得られたデータをファイルマネージャに送る。ファイルマネージャは、GPSレコーダおよびWi−Fiレコーダの両方からスキャンデータを受け取り、この装置に保管ファイルを生成する。この処理は、その装置が動作しており、かつ両方の無線装置が機能しているときはずっと続く。
【0049】
アップロードマネージャ1003にはホットスポット検出器1017があり、このホットスポット検出器1017は、その装置がアクセスを許可された公共のホットスポット1024(例えばT−モバイル)のネットワークを探すために802.11スキャニングの結果を監視する。一旦それが有効なホットスポットを検出すると、その存在をユーザに知らせる。そのユーザは、クリエイトコネクション要素(CreateConnection component)1018を起動することによってそのホットスポットに接続することを選択できる。この要素は、ホットスポットのアクセスポイントに関連し、802.11接続をつくる。次に、ホットスポット認証モジュール(HotspotAuthentication module)1019は、この装置のための有効な認証情報を供給する。このホットスポットは、アカウントを確認し、次にこの装置にネットワークアクセスを提供する。アップロードマネージャは、次に中央ネットワークサーバ1025に接続するためにアップロードサーバ認証処理1020を開始し、有効な認証情報を提供する。一旦認証されると、アップロード・アンド・データ検証モジュール(Upload& Data Verification module)1021が作動し始める。このモジュールは、スキャニングデータ記憶装置1011からスキャンデータを検索し、FTPを使用する中央ネットワークサーバにデータをアップロードする。この中央ネットワークサーバは、全てのデータを中央アクセスポイントデータベースに格納するために処理を開始する。アップロードが完了したのち、このアップロード処理は、スキャンデータをスキャニングデータ記憶装置1011からこの装置のバックアップデータ記憶装置1012に移動する。一旦このアップロードが完了し、検証されると、ニューバージョンモジュール1022が、この装置のために利用可能なクライアントソフトウェアの新しいバージョンがあるかどうかを決定するために、中央ネットワークサーバをチェックする。新しいバージョンがある場合には、このソフトウェアはダウンロードされ、ニューバージョンインストール1023処理がこのクライアントソフトウェアをアップグレードするのを開始する。一旦このインストール処理が完了すると、中央ネットワークサーバへの接続が終了し、ホットスポットへの接続が終了し、この装置は通常のスキャニング動作に戻る。
【0050】
スキャニングクライアント704には、この装置を管理し、システムエラーを減らすことを助ける1セットのユーティリティが備えられている。無線装置マネージャ1013は、GPS無線装置およびWi−Fi無線装置の動作を監視し、それらが正しく機能していることを確実にする。この無線装置マネージャは、無線装置のひとつに問題があることを発見すると、その無線装置を再起動する。ユーザインターフェイスコントローラ1014は、ユーザにツールを示し、アップデートして、ユーザがこの装置を効果的に操作できるようにする。エラーハンドリングおよびロギング1015は、全てのシステム問題を装置に記録し、ユーザに警告をして、対処できるようにする。システム再起動モジュール1016は、問題が解決できない場合に呼び出される。このモジュールは、装置をシャットダウンして、ハードウェア、オペレーティングシステムおよびスキャニングクライアンを再起動させ、正しく作動することを確実にする。
【0051】
1秒の十分の一秒の802.11スキャニングインターバルが選択された。それは、既製品のハードウェアを使用した場合にこれらの条件のもとで802.11のための最適なスキャン期間であるからである。802.11b/g/nは、無許可のスペクトラムの14チャネルを用いて動作する。各アクセスポイントは、所定の時間に、これらのチャンネルの一つにその信号ビーコンを同報する。このスキャニング装置は、可能な限り多くのアクセスポイントを観測するために各チャネルを調査する必要がある。このスキャニングインターバルは、スキャニング車両の平均速度に相関しており、スキャニングクライアントがどのように特定の領域の頻繁に訪れる場所(frequencyreal estate)をカバーするかを最適化する。
【0052】
中央ネットワークサーバ
図8を参照すると、車両の一隊は、予め設計されたルートを走行する間、スキャニングルーチンを実行する。周期的に各車両801は、利用可な802.11アクセスポイントに接続し、中央ネットワークサーバのデータコミュニケーションモジュール807で認証する。一般には、中央ネットワークサーバと通信するために使用されるアクセスポイントは、メーターで測定された信頼性のあるアクセスを確実にするT−Mobileによって操作されるような公共のホットスポットである。この接続の提供は使用可能な公共のアクセスポイントのいずれかを介してなされる。このスキャニング車両は、近くのホットスポット位置で止まり、アクセスポイントへの接続の処理を開始する。一旦認証されると、スキャニングクライアント704は、ローカル格納部703から最近収集されたスキャンデータの全てを認識し、このデータを中央ネットワークデータベース802にアップロードする。
【0053】
一旦このデータがデータベースにアップロードされると、パーサおよびフィルタ処理803が始まる。このパーサおよびフィルタ処理は、アップロードスキャニングデータの全てを読み取り、データベースの適当なテーブルにそれをロードする。この実行の間、データは、品質問題において評価される。場合によっては、GPSレシーバは、ある期間、誤りまたはエラー記録を記録することもできるが、これによって最終アクセスポイント位置算出によくない影響がでる恐れがある。パーサおよびフィルタ処理は、これらの不良記録を認識し、修正するか、またはシステムから除去する。フィルタ処理は、クラスター化技術を使用し、エラーを起こしやすいGPS読み取り値を除去する。例えば、読み取り値の90%が互いに200メートル内であるが、読み取り値の10%が互いに5キロメートルより離れている場合、これらの分離された値はフィルタによって除去され、更なる分析のためにデータベースの損傷を受けたテーブルに保存される。特に、このシステムは、まず、全ての報告されたデータを使用してアクセスポイントのために重み付けされた重心を算出する。次に、報告された位置の分布に基づいて、標準偏差を決定する。このシステムは、エラーとなっているアクセスポイントを除去するためにこの分布のシグマ(標準偏差)に基づいて、設定可能な閾値を使用する。一旦これらのエラー記録がマーキングされると、この重心は、後述の逆三角測定法を用いて、最終重心を決定するために残りの位置記録によって再算出される。
【0054】
アクセスポイントが移動した結果、エラー記録ができることに留意されたい。この場合、複数のアクセスポイントの重心は、記録の優勢に基づき、新しい場所に迅速に「スナップ(瞬時に飛ぶ)」する。更に向上したアルゴリズムには、新しい記録が所与のアクセスポイントの現在位置をより強く表示するように記録の新旧に基づく重み付けの値が含まれるであろう。
【0055】
一旦、パーサ(構文解析)処理が完了すると、中心ネットワークシステムは、逆三角測量モデル804に新しいデータの処理を開始させる。この処理の間、1)新しいアクセスポイントがデータベースに加えられ、それらの物理的な位置が算出され、2)現存のアクセスポイントが、スキャナーによって記録された新しいデータに基づいて再測位される。逆三角測量アルゴリズムは、準重み付けされた平均モデルを備える弱い信号より強い信号読み取りを重み付けするために、記録の数と、関連する信号読み取り値とを計算に入れる。
【0056】
データ収集の間、WPSユーザは、利用可能なWi−Fiアクセスポイントから受信された信号強度(ReceivedSignal Strength(RSS))を測定し、対応するアクセスポイントの位置情報を抽出する、Wi−Fiレシーバ装置を備える。アクセスポイントのRSS値は、下記のようである:
{RSS1, RSS2,...RSSn}
【0057】
アクセスポイントiの対応して記録されたGPS位置が{Lati,Longi}で表示され、算出されたアクセスポイント位置が{Lati,Longi}で表示され、三角測量された位置が下記のようなアルゴリズムを適用することによって求められる:
【0058】
電力の4平方根は、アルゴリズムの実現を容易にするために選択される。それは、4平方根は、2平方根をとるのと同義であるからである。
【0059】
二つ目は、係数のダイナミックレンジを調整することに関する。係数のダイナミックレンジが問題となっている場合、アルゴリズムの係数を例えば下記の定数によって割ることができる。
【0060】
パラメータCは、どのような数字であってもよく、理論的には結果には影響しない。重み付けされた平均が係数の比率に基づいており、絶対値ではないため、理論的には、全ての係数を定数Cで割ることによって、結果に影響することはないが、係数の値のダイナミックレンジを変える。
【0061】
この最終の{Lati,Longi}は次に、そのアクセスポイントの位置のための最終重心値として使用される。次に、緯度および経度が、三角測定値がどのくらい新しいかを表示するためのタイムスタンプを含んで、データベースに格納される。
【0062】
中央ネットワークデータベースがアップデートされて、各アクセスポイントが再測位された後に、データパックビルダー(DataPack Builder)805は国または世界の複数域に基づいてデータベースのサブセットを作る。このパックビルダーは、様々な使用において特定の地域のみが必要である場合にデータベースの提供を容易にする。パックビルダーは、国、タイムゾーンおよび都市圏を示す地域座標によって構成される。この技術を利用して、例えばユーザは、米国の西海岸用の位置データのみをダウンロードすることができる。パックビルダーは、複数のデータ記録を分割し、圧縮する。
【0063】
フリートマネジメントモジュール806は、業務職員がスキャニング車両を管理するのを助け、経路選択を固守するのを確実にする。このモジュールは、全てのスキャンデータを処理し、このシステムにおいて各車両の位置軌道を構築する。業務管理者は、特定の地域のためのカバレージを視覚的に検査するためにマップビルダー808を使用して車両軌道のマップを作成することができる。各装置からのGPSトラッキングデータは、カバレージの完成を確認し欠落したエリアを認識するために、ルートマッピングソフトウェアでチェックされる。均一のカバレージを検査して確認するこの機能によって、このシステムが可能な限り最良のデータを得ることが確実になる。このモジュールは更に、平均速度を測定しかつアイドルタイムを差し引くために、車両の走行時間を算出する。これらのアウトプットは、システム全体の効率の監視および将来のカバレージの計画のために使用される。
【0064】
本発明の範囲は、上記実施例に限定されず、むしろ、添付の請求の範囲によって決定され、かつ、これらの請求項には、上記記載のものを変形、改良したものも含まれるべきである。
【技術分野】
【0001】
本発明は、概してロケーションベースのサービスに関し、より詳しくは、Wi−Fiアクセスポイントの位置を決定し、この情報をWi−Fi対応装置の位置を検出するために使用する方法およびシステムに関する。
【背景技術】
【0002】
関連出願についてのクロス・リファレンス
本出願は、2004年10月29日に出願された米国仮特許出願第60/623,108号、「ロケーションビーコンデータベースを構築するためのワイヤレスデータスキャニングネットワーク」(本明細書に組み込まれる)の利益を35U.S.C. § 119(e)に基づき請求する。
【0003】
本出願は、上記出願と同日に出願された下記の発明の名称の米国特許出願に関する:
ロケーションビーコンデータベース;
ロケーションビーコンデータベースをアップデートするためのサーバ;
ユーザ装置の範囲内に検出されたアクセスポイントの数に基づきロケーションアルゴリズムを選択するロケーションベースのサービス;および
ロケーションビーコンデータベースのための方法およびシステム
【0004】
関連技術
近年、モバイルコンピュータの数が劇的に増加しており、より高度なモバイルおよびワイヤレスサービスの必要性が生じている。モバイルEメール、ウォーキートーキーサービス、マルチプレイヤ・ゲームおよびコールフォロイング(callfollowing)が、新しいアプリケーションがどのようにモバイル機器に現れているかを示す例である。更に、ユーザは、その現在地を利用するだけではなく、他人とその位置情報を共有するアプリケーションを求め始めている。親が子供の行方を監視したり、会社の管理者がこの会社の配達車両の位置を監視する必要があったり、出張旅行者が処方箋を受け取るため、最も近い薬局を見つけるために調べたりする。これらの例全ては、かれらが自身のまたは関係する他者の居場所を知る必要がある。現在に至るまで、我々は、誰かに方向を尋ねたり、我々の所在を尋ねるために誰かに電話したり、従業員に彼らの位置を時々報告させたりすることに全て依存している。
【0005】
ロケーションベースのサービスは、モバイルアプリケーションの新たに出現してきている分野であって、現在地を算出し、ユーザに報告する新しい装置の機能に影響している。これらのサービスの例としては、付近の天気、最新交通情報、走行方向、子供の追跡、位置特定(friendfinder)、都市案内サービスが含まれる。これらの新しい位置検出装置は、全て同じ一般的な概念を使用する様々な技術に依存している。既知のリファレンスポイント(基準点)から来る無線信号を使用して、これらの装置はこれらのリファレンスポイントと比較してユーザの位置を数学的に算出することができる。これらの方法はそれぞれ、無線技術および、測位アルゴリズムに基づく強みまたは弱点がある。
【発明の開示】
【発明が解決しようとする課題】
【0006】
米国政府が運用するグローバルポジショニングシステム(GPS)は、リファレンスポイントとして何ダースもの軌道衛星を利用している。これらの衛星は、複数のGPSレシーバによって受信される無線信号を同報する。レシーバは、信号がレシーバに届くまでの時間を測定する。3つ以上のGPS衛星から信号を受信した後、レシーバは地球上でその位置を三角測量することができる。このシステムが効率的に動作するために、無線信号は、その信号がほとんどまたは全く干渉されることなくレシーバに届かなくてはならない。レシーバは3つ以上の衛星へのクリアな見通しを必要とするため、天気、建築物および植物の葉が干渉となり得る。干渉は、多重通路として知られる現象によっても引き起こされ得る。衛星からの無線信号が物理的構造物に反射し、同一の衛星からの多重信号を異なる時間にレシーバに到達させてしまう。レシーバの算出は、信号がレシーバに届くまでの時間に基づいてなされるため、多重通路信号は、レシーバを混乱させ、重大なエラーを発生させてしまう。
【0007】
携帯電話中継地を利用した三角測量法は、ユーザまたは装置の位置を決定するために無線会社および携帯電話会社によって使用される別の方法である。無線ネットワークおよび携帯装置は、ネットワークがこの装置の位置を算出するために使用することができる信号情報を共有するために互いに通信する。これらの信号は目標地点への直線的見通しを必要とすることなく、建築物をより透過することができるため、この方法は、GPSに対する優位モデルとして当初は見られた。残念なことに、これらの方法は、多重通路信号の問題および携帯電話中継地の測位においての画一性の欠如の問題に加え、携帯電話中継地は本質的に不均一なために最適ではないことが証明されている。
【0008】
アシスト付きGPS(Assisted GPS(A−GPS))はGPSと携帯電話中継地の両方の技術を組み合わせた更に新しいモデルであって、モバイルユーザのより正確かつ信頼性の高い位置の算出を行う。このモデルにおいて、無線ネットワークは、GPS衛星の時計オフセットについての情報と、接続された携帯電話中継地の位置に基づくユーザの一般的な位置についての情報とを送信することによってGPSが信号受信を改善することを助ける試みである。これらの技術は、GPSレシーバが、屋内にいるときなどに経験する弱い信号を処理することを助け、レシーバが最も近い衛星の「固定(fix)」を迅速に得て、より速い「第1の読み込み(firstreading)」をする。これらのシステムは、都心から100メートル以上離れた所では応答時間が遅く、正確性に欠けるという問題に悩まされている。
【0009】
GPS、A−GPSおよび携帯電話中継地を利用した測位の公知の問題を解決すべく開発された最近の代替モデルがいくつかある。その一つとして、TV−GPSとして知られるものは、テレビ塔からの信号を利用する。(例えば、Muthukrishnan,MariaLijding,Paul Havinga,TowardsSmart Surroundings:EnablingTechniques および Technologies for Localization,Lecture Notes in Computer Science,Volume3479,Jan 2Hazas,M.,Scott,J.,Krumm,J.:Location−AwareComputing Comes of Age. IEEEComputer, 37(2):95−97,Feb2004 005,Pa005,Pages350−362を参照。)このコンセプトは、ほとんどの都市部には3つ以上のテレビ塔があるという実状に依存している。専用のハードウェアチップが、様々なテレビ塔から出るテレビ信号を受信し、リファレンスポイントとしてこれらのテレビ塔の既知の位置を利用する。この方式に直面する問題は、新しいハードウェアレシーバのコストと、リファレンスポイントの少ない一組を使用することによる制約である。例えば、ユーザがテレビ塔の周辺部の外にいる場合、このシステムは妥当な精度を出すのに困難な場合が見られる。この典型的な例は、海岸線にいるユーザである。海にはテレビ塔がないため、リファレンスポイントにおいて基準対称性(referencesymmetry)を提供することができず、内陸のユーザのほうがより正確に位置を算出することができる。
【0010】
マイクロソフト社およびインテル社は(PlaceLabとして知られる調査団体を介して)、Wi−Fiスキャンデータを公衆の共有ウェブに提供するアマチュアユーザ(「ウォードライバー」(wardrivers)として知られる)から得られるアクセスポイントの位置を使用するWi−Fi測位システムを開発した。(例えば、LaMarca,A.,et.al.,PlaceLab: Device Radio Using RadioBeacons in the Wildを参照。) 例としてはWiGLE、Wi−FiMaps.com、Netstumbler.comおよびNodeDBが含まれる。マイクロソフト社およびインテル社の両社は、公衆のウォードライビングデータを基準位置として利用する同社のクライアントソフトウェアを開発した。個人がそのデータを自発的に供給するため、このシステムは、多くの性能および信頼性の問題が生じる。第1に、データベースのデータは、同時期に存在しておらず、一部のデータは、新しく、別の部分は3〜4年前のデータである。時間が経過すると、アクセスポイントは移動され、削除されるため、アクセスポイントの位置の新しさが重要となる。第2に、そのデータは、様々なハードウェアおよびソフトウェアを使用して作られていることである。全ての802.11無線装置およびアンテナは、信号の強さの表示に影響を及ぼす異なる信号受信特性を備えている。各スキャニングソフトウェアインプリメンテーションは異なる時間間隔に異なる様式でWi−Fi信号をスキャンする。第3に、ユーザによって供給されたデータは、幹線の偏り(arterialbias)を被る。望ましいスキャンルートに従わない個人によって自己申告されているので、そのデータは交通量の激しい地域周辺に集まる傾向がある。幹線の偏りは、ユーザが現在どこにいるかに関わらず、結果として得られる位置を主要幹線道路に向かって引っ張ってしまい、重大なエラーを引き起こしてしまう。第4に、これらのデータベースは、スキャンされたアクセスポイントの算出された位置を含んでおり、802.11ハードウェアで得られる未処理のスキャンデータではない。これらのデータベースのそれぞれは、アクセスポイントの位置を異なって算出し、基礎的な重み付き平均方程式で算出される。結果として、多くのアクセスポイントは実際の位置から離れた位置であるように表示され、それらには、あたかも水中に位置しているように間違って表示されたいくつかのアクセスポイントも含まれる。
【0011】
屋内測位用のWi−Fi測位システムは商業的に多く出回っている。(例えば、Kavitha Muthukrishnan,MariaLijding,Paul Havinga,TowardsSmart Surroundings:EnablingTechniques および Technologies for Localization,Lecture Notes in Computer Science,Volume3479,Jan 2Hazas,M.,Scott,J.,Krumm,J.:Location−Aware Computing Comes ofAge.IEEE Computer,37(2):95−97,Feb2004005,Pa005,Pages 350−362を参照。)これらのシステムは、資産(asset)および人をアドレス指定し、会社の敷地、病院、出荷所といった管理される環境内で監視するように設計されている。この典型的な例は、病院内で緊急用カートの正確な位置を監視することができるシステムであって、心停止があった場合に病院のスタッフが時間を無駄にすることなくそのカートを見つけることができるようにするものである。こうした使用の場合に要求される精度は、一般的に1〜3メートルの精度を要求する非常に高いものである。これらのシステムは、精度を微調整するための様々な技術を使用し、それには無線信号伝搬を測定するために敷地の1平方フィート毎の詳細な実地調査を行うことが含まれる。それらは、一定のネットワーク接続が必要であり、アクセスポイントおよびクライアント無線装置が、A−GPSの作動の仕方に類似する同期情報を交換する。これらのシステムがこれらの屋内の場面で信頼性を高めてきたが、広域にて展開するには効果的ではない。一都市全体に亘って求められるそのような詳細な実地調査を行うことは、不可能であり、都市圏全体に亘って802.11アクセスポイントと一定に通信するチャネルを、これらのシステムに要求されるようには信頼することができない。最も重要なこととして、屋外の電波の伝搬は、屋内の電波の伝搬とは基本的に異なっており、これらの屋内測位アルゴリズムは広域のケースにおいてはほぼ役に立たない。
【0012】
GPS位置の読み込み値と共に802.11信号の存在を記録するのに利用可能である数多くの802.11位置スキャニングクライアントがある。これらのソフトウェアアプリケーションは、手動で操作され、読み取り値のログファイルを生成する。これらのアプリケーションの例としては、Netstumber、KismetおよびWi−FiFoFumがある。一部の愛好者は、かれらが検出して互いに共有する802.11アクセスポイントの位置をマーキングするためにこれらのアプリケーションを使用する。このデータの管理および情報の提供は、全て手動でなされる。これらのアプリケーションは、アクセスポイントの物理的な位置について計算を行なわず、アクセスポイントが検出される位置を単にマーキングするのみである。
【0013】
基礎をなす測位システムの性能および信頼性は、ロケーションベースのサービスが良好に展開する重要な要素である。性能とは、所与の使用の場合にこのシステムが達成する精度レベルのことを指す。信頼性とは、所望の性能レベルが達成される時間率(percentageof time)のことを指す。
【課題を解決するための手段】
【0014】
本発明は、ロケーションビーコンデータベースおよびサーバを提供し、ロケーションビーコンデータベースの構築およびこれを使用するロケーションベースのサービスの方法である。
【0015】
本発明の一態様において、Wi−Fiアクセスポイントが、Wi−Fiアクセスポイントの位置のリファレンスデータベースを構築するために、地理的標的エリアに測位される。少なくとも一の車両が、GPS装置およびWi−Fi無線装置を有する少なくとも一つのスキャニング装置と、Wi−Fiアンテナシステムとを備えて展開される。この目標エリア内を、幹線の偏りを避けるためにプログラムされたルートで移動する。このプラグラムに基づいたルートは、地理的目標エリアの実質的に全ての走行可能な道路を含み、かつ、前記走行可能な道路によって示されるグラフのオイラーサイクル(Euleriancycle)問題を解くものである。目標地エリア内を移動する間、GPS装置のGPS座標を周期的に受信する。目標地域を移動する間、Wi−Fi装置の範囲において複数のWi−FiアクセスポイントからのWi−Fi信号を検出し、これらのWi−FiアクセスポイントからのWi−Fi信号が検出された場合に、車両のGPS位置情報に関連して検出されたWi−Fiアクセスポイントの認識情報を記録する。この位置情報は、検出されたWi−Fiアクセスポイントの位置を逆三角測量(reversetriangulate)するために使用され、検出されたアクセスポイントの位置は、リファレンスデータベースに記録される。
【0016】
本発明別の態様において、地理的目標エリアは、およそ数十マイルの半径を有する。
【0017】
本発明別の態様において、プログラムに基づいたルートは、チャイニーズポストマンルーティングアルゴリズムを使用して決定される。
【0018】
本発明別の態様において、Wi−Fi信号を検出した場合に、一組の読み取り値がこの所与のWi−Fiアクセスポイントのために生成されるように複数のWi−Fi信号の読み取りが所与のWi−Fiアクセスポイントのためになされ、この一組の読み取り値は、検出されたWi−Fiアクセスポイントの位置を決定するときに使用される。
【0019】
本発明別の態様において、Wi−Fiアクセスポイントを検出した場合、このWi−Fiアクセスポイントからの信号についての信号強度情報がスキャニング装置によって算出され、記録される。
【0020】
本発明別の態様において、走行可能な道路の組織が与えられる場合に可能な限り多くの異なる角度から検出される。
【0021】
本発明別の態様において、所与のWi−Fiアクセスポイントは、走行可能な道路の組織が与えられる場合に可能な限り多くの異なる角度から検出されて、所与のWi−Fiアクセスポイントのための信号強度の電力プロファイルが決定され、記録される。
【0022】
本発明別の態様において、Wi−Fiアンテナシステムは、複数の指向性アンテナを含んでおり、スキャニング装置は、この指向性アンテナ上でWi−Fiアクセスポイントによって受信される異なる信号強度に基づき、前記Wi−Fiアクセスポイントの出所のベクトルを記録する。
【0023】
本発明別の態様において、アクセスポイントは、複数の目標エリアのために測位される。
【0024】
本発明別の態様において、Wi−Fi無線装置を備えるユーザ装置を測位することができる。目標エリアにおいて複数のWi−Fiアクセスポイントの算出された位置のリファレンスデータベースが提供される。Wi−Fi無線装置を備えるユーザ装置の位置を決定するためのユーザアプリケーション要求に応答して、Wi−Fi無線装置の範囲内の全てのWi−Fiアクセスポイントに要求を送信するためにWi−Fi無線装置を起動させる。Wi−Fi装置の範囲内において前記Wi−Fiアクセスポイントからからのメッセージを受信する(ここで、各メッセージはこのメッセージを送るWi−Fiアクセスポイントを特定するものである)。前記Wi−Fiアクセスポイントによって受信されたメッセージの信号強度を算出する。認識されたWi−Fiアクセスポイントの算出された位置を獲得するためにリファレンスデータベースにアクセスする。受信されたメッセージを介して認識されたWi−Fiアクセスポイントの数に基づいて、複数の位置決定アルゴリズムから対応する位置決定アルゴリズムを選択する(ここで、この選択されたアルゴリズムは、認識されたWi−Fiアクセスポイントの数に適するものである)。前記ユーザ装置の位置を決定するために、前記認識されたWi−Fiアクセスポイントの算出された位置、前記受信されたメッセージの信号強度、および前記選択された位置決定アルゴリズムを使用する。
【0025】
本発明の別の態様において、認識されたWi−Fiアクセスポイントの算出された位置は、Wi−Fiアクセスポイントについての時間情報が前記リファレンスデータベースに含まれているため、前記対応するWi−Fアクセスポイントが移動したか否かを決定するためにフィルタにかけられる。
【0026】
本発明の別の態様において、複数の位置決定アルゴリズムは、簡素な信号強度の重み付き平均モデルを含む。
【0027】
本発明の別の態様において、複数の位置決定アルゴリズムは、直近のモデルを含む。
【0028】
本発明の別の態様において、複数の位置決定アルゴリズムは、三角測量技術を含む。
【0029】
本発明の別の態様において、複数の位置決定アルゴリズムは、装置の速度に基づき適応可能な平滑化技術を含む。
【0030】
本発明の別の態様において、位置決定アルゴリズムの選択は、更に、位置要求を生成するユーザアプリケーションに基づく。
【0031】
本発明の別の態様において、およそ数十マイルの半径を有する少なくとも一つの目標地域のためのWi−Fiアクセスポイントのデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのWi−Fiアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するWi−Fiアクセスポイントの認識情報と、この対応するWi−Fiアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Wi−Fiアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Wi−Fiアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぐ。
【0032】
本発明の別の態様において、Wi−Fi位置サーバは、およそ数十マイルの半径を有する少なくとも一つの目標地域のためのWi−Fiアクセスポイントのデータベースを備えており、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのWi−Fiアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するWi−Fiアクセスポイントの認識情報と、この対応するWi−Fiアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Wi−Fiアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Wi−Fiアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぎ、新しく発見されたWi−Fiアクセスポイントのために前記データベースに記録を加えるためのコンピュータで実行される論理を備えており、このコンピュータ論理は、新しく発見されたWi−Fiアクセスポイントのための前記位置情報を利用するため、前記データベースに以前格納されたWi−Fiアクセスポイントの位置情報を再算出するための論理を含む。
【0033】
本発明の別の態様において、サーバは、エラーを起こしやすいGPS情報に基づき位置情報を認識するために、コンピュータで実行されるクラスター化論理を更に備える。
【0034】
本発明の別の態様において、クラスター論理は、アクセスポイントのために報告された全ての位置情報のために重み付けされた重心位置を決定するための論理と、前記重心から離れる統計に基づく偏差の閾値を超える位置情報を認識する論理とを含み、偏っている位置情報をデータベースから除外し、Wi−Fiアクセスポイントの算出された位置に影響を与えないようにする。
【図面の簡単な説明】
【0035】
【図1】図1は、Wi−Fi測位システムの特定の実施例を示す。
【図2】図2は、本発明の特定の実施例による、スキャニング装置を備えるスキャニング車両を示す。
【図3】図3は、データ収集における幹線の偏りの問題点を示すためのスキャニングシナリオの一例を示す。
【図4】図4は、本発明の特定の実施例によるスキャニング車両用のプログラムに基づいたルートを使用する一例を示す。
【図5】図5は、ユーザ装置の測位においてWi−Fiアクセスポイントの基準対称性(referencesymmetry)の欠如の問題を例示するためのシナリオの一例を示す。
【図6】図6は、ユーザ装置の測位においてWi−Fiアクセスポイントの基準対称性を例示するためのシナリオの一例を示す。
【図7】図7は、本発明の特定の実施例による、スキャニング装置を備えるスキャニング車両を示す。
【図8】図8は、本発明の特定の実施例による、Wi−Fiアクセスポイントの中央データベースを有する中央ネットワークサーバを示す。
【図9】図9は、本発明の特定の実施例による、測位ソフトウェアの例示的な構造を示す。
【図10】図10は、本発明の特定の実施例による、スキャニングクライアントの例示的な構造を示す。
【図11】図11は、ランダムスキャニングモデルの効果をチャイニーズポストマンルーティングアルゴリズムのモデルを使用するものとの比較、対比を示す。
【発明を実施するための最良の形態】
【0036】
本発明の好適な実施例は、公共および個人の802.11アクセスポイントを使用して、商業的な測位システムを可能とするために基準位置データを収集するためのシステムおよび方法を提供する。好適には、このデータは、目標地域の道路を完全に探査し、カバーするためにプログラムに基づいた方法で収集される。このプログラムに基づいた方法によって、可能な限り多くのWi−Fiアクセスポイントを認識する。より多くのアクセスポイントについての位置情報を収集することによって、好適な実施例は、このアクセスポイントについての位置情報の多大な収集を提供するだけではなく、各アクセスポイントのための位置情報をより精度を増して算出することができる。その後、この精度の高いデータの大きな1セットは、本発明の好適な実施例を利用して、ユーザ装置をより正確に測位するようにロケーションサービスによって使用される。特定の実施例は、Wi−Fi位置の決定において間違ったデータを避けるための技術を使用し、かつ先に収集され決定された位置情報の質を改善するために、新しく発見された位置を利用する。特定の実施例は、ユーザが位置を要求した時にユーザ装置の状況に基づき位置決定アルゴリズムを使用する。例えば、この位置決定アルゴリズムは、位置要求がなされたときに認識または検出されるWi−Fiアクセスポイントの数に基づくか、またはその要求を出すアプリケーションに基づく。
【0037】
図1は、Wi−Fi測位システム(Wi−Fi positioning system (WPS))の好適な実施例の一部を示す。この測位システムは、コンピュータであるユーザ装置101に収容されている測位ソフトウェア103を含む。特定のカバレージエリア(有効範囲)全体に亘って、制御/共通チャネル同報信号を使用して情報を同報する複数の固定ワイヤレスアクセスポイント102がある。このクライアント装置は、同報信号を監視するか、または、精査要求(proberequest)を経てその送信を要求する。各アクセスポイントは、MACアドレスとして知られる固有のハードウェア識別子を含む。クライアント測位ソフトウェアは、範囲内にある802.11アクセスポイントから信号ビーコンを受信し、信号ビーコンからの特性を利用してコンピュータの地理的位置を算出する。これらの特性には、MACアドレスとして知られる802.11アクセスポイントの固有の識別子と、クライアント装置に達する信号の強度が含まれる。クライアントソフトウェアは、観測された802.11アクセスポイントをアクセスポイントのリファレンスデータベース104内のものと比較する。このリファレンスデータベース104は、その装置に収容されていてもされなくてもよい。このリファレンスデータベースには、算出された地理的位置または、収集システムが収集した全てのアクセスポイントの電力プロファイルが含まれる。この電力プロファイルは、様々な位置から出る信号の電力を表示する読み取り値の集合である。これらの既知の位置を利用して、クライアントソフトウェアはユーザ装置101の相対位置を算出し、緯度と経度の読み取り値でその地理的座標を決定する。次に、これらの読み取り値は、ロケーションベースのアプリケーション(例えば、位置特定(フレンドファインダー)、ローカルサーチウェブサイト、フリートマネジメントシステムおよびE911サービス)に供給される。
【0038】
この測位ソフトウェア103は、図9により詳細に記載されており、この構成要素が例示されている。位置読み取り値を利用して、エンドユーザにある値(例えば走行方向)を提供する、アプリケーションもしくはサービス901が一般的に存在する。この位置(ロケーション)アプリケーションは、瞬間的にその装置の位置を測位ソフトウェアに求める。この要求によって、その装置の802.11無線装置903に「スキャン要求」を行うスキャナー902が起動される。この802.11無線装置は、その範囲内の全ての802.11アクセスポイント904に探査要求(proberequest)を送る。802.11プロトコルに従って、探査要求を受信したこれらのアクセスポイントは、アクセスポイントについての情報を含む同報ビーコン(broadcastbeacon)を発信する。このビーコンには、装置のMACアドレス、ネットワーク名、それがサポートするプロトコルの正確なバージョン、およびその装置にどのように接続するかについての情報と共にセキュリティ構成が含まれる。この802.11無線装置は、応答する各アクセスポイントからこの情報を収集し、各アクセスポイントの信号強度を算出し、それをスキャナーに返送する。
【0039】
このスキャナーは、この複数のアクセスポイントの配置情報をロケータ906に渡し、このロケータ906は、アクセスポイントレファレンスデータベース905に対して、観測された各アクセスポイントのMACアドレスをチェックする。このデータベースは、その装置に収容されているか、またはネットワーク接続上に離れて収容されている。このアクセスポイントレファレンスデータベースは、このシステムに既知である観測された各アクセスポイントの位置データを戻す。このロケータは、各アクセスポイントから返信される信号特性と共にこの位置情報の集積を不良データフィルタ(BadData Filter)907に渡す。いずれかのアクセスポイントがアクセスポイントデータベースに加えられてから移動したか否かを決定するために、このフィルタは、各アクセスポイントに対して多くの比較テストを行う。不良データ記録を取り除いた後に、フィルタは、残りのアクセスポイントを位置算出要素908に送る。アクセスポイントデータベースから提供されるリファレンスデータおよびスキャナーから提供される信号強度読み取り値を用いて、位置算出要素がその時のこの装置の位置を計算する。ロケータに返信される前に、この位置データは、過去の一連の位置読み取り値を平均し、先の算出からの読み取り誤差を除去するために平滑化(スムージング)エンジン909によって処理される。調整された位置データは、次にロケータに返信される。
【0040】
ロケータによって生成されたこの算出された読み取り値は、アプリケーションプログラミングインターフェース(API)を含むアプリケーションインターフェイス910を通して、またはバーチャルGPS機能911を介して、これらのロケーションベースのアプリケーションに伝達される。GPSレシーバは、独自のメッセージを使用して、または、ナショナル・マリン・エレクトロニクス・アソシエーション(NationalMarine ElectronicsAssociation(NMEA)) によって開発されたような測位規格を使用して、位置読み取り値を伝達する。機器のCOMポートといった標準インターフェースを使用する装置に接続することによってメッセージを読み出す。本発明の特定の実施例には、いかなるGPS汎用アプリケーションも通信モデルまたはメッセージを変化させることなくこの新しい測位システムと通信することができるバーチャルGPS機能が含まれる。
【0041】
この位置算出は、ノイズの多いデータフローを信頼性かつ安定性のある位置読み取り値に変えることを目的とする一連の測位アルゴリズムを使用してなされる。クライアントソフトウェアは、観測されたアクセスポイントのリストを算出された信号強度と共に比較し、この装置のユーザの正確な位置を決定するためにユーザの位置を重み付けする。様々な技術が使用され、これには、簡潔な信号強度に重み付けされた平均モデルと、三角測量方式技術と組み合わされる最近傍モデルと、装置速度に基づいて適合可能な平滑化とが含まれる。シナリオが異なる場合は、異なるアルゴリズムの方がうまく機能し、最も正確な最終読み取り値を生成するために混成して使用される傾向にある。本発明の好適な実施例は、多くの測位アルゴリズムを使用することができる。どのアルゴリズムを使用するかの決定は、観測されたアクセスポイントの数と、それを使用しているユーザケースアプリケーションとによる。従来のシステムは、移動することのない既知のリファレンスポイントに頼っているため、このフィルタモデルは従来の測位システムとは異なる。好適な実施例のモデルにおいて、アクセスポイントが固定された位置にあるという仮定はなされず、アクセスポイントは測位システムによって所有されておらず、これらのアクセスポイントを移動またはオフラインにしてもよい。このフィルタリング技術は、もはやいくつかのアクセスポイントが同じ場所に位置しなくてもよく、位置が不良算出されてもよい。よって、このフィルタアルゴリズムは、アクセスポイントの位置が記録された後に移動したアクセスポイントを隔離しようとする。このフィルタは、動的であって、その時に観測されたアクセスポイントの数に基づき変更する。平滑化アルゴリズムは、単純な平均位置算出と、カルマンフィルタを含む高度なベイズの論理とを含む。速度アルゴリズムは、各アクセスポイントの信号強度観測値からドップラー効果を推定することによって装置の速度を算出する。
【0042】
基準データベースを構築するためのスキャンデータの収集
図2は、様々なアクセスポイントの位置情報を収集するために使用される要素を示している。多くの車両201からなる一隊が、測位システムのためのリファレンスデータベース(図1の104)を構築するために展開される。これらの車両201は、目標スキャンエリアを通してプログラムに基づいたルートをたどり、質の高いデータを生成する最適な方法でデータを収集する。この目標スキャンエリアは典型的に、半径15〜20マイル内の全ての走行可能な道路を含む大都市圏である。これらの車両は、カバレージエリアを移動する間に802.11信号の位置および特性を記録するように設計されたスキャニング装置202を備えている。このスキャニング装置は、GPS衛星204からの信号を使用して毎秒スキャニング車両の位置を追跡する。このスキャニング装置は、カバレージエリア内のいかなる802.11アクセスポイントの所在も追跡し、スキャン車両のGPS位置と、アクセスポイント信号の無線特性とを記録する。収集されたデータの品質は、スキャン車両に備えられるスキャン方法によって多大に影響される。各モデルは、それぞれ利点および制限がある。ランダムモデル(RandomModel)として知られる一つの方法は、車両は商用または私用で日常的に稼動することから、車両にスキャニング装置を配置するものである。これらの車両は、配達用トラック、タクシー、セールスマンまたは単に愛好家となり得る。このコンセプトは、これらの車両が、信頼性のあるリファレンスデータベースを構築するためにそれら自体のランダムな方法で時間が経つにつれて十分な道路をカバーしているであろうとするものである。このモデルは、データを収集するための簡略的な手段を実際に提供するが、結果として得られるデータの品質は、「幹線の偏り(arterialbias)」の問題のために悪影響を受ける。図3は、このランダムモデルの課題を示している。スキャニング車両が、データを収集するよりもむしろ他の課題を解決するために設計されたルートを移動する場合(例えば、荷物の配達、出勤、帰宅)、それらは、「目的地ルート」をたどる傾向にある。目的地ルートは、ドライバーがAからBに行く必要がある場合であってかつそこに行くための最速ルートを求める場合のルートである。よって、ドライバーは、それが高速道路であるか大通りであるかに関わらず、最も近い主要幹線に行くための最短ルートを探す。結果として、時が経つにつれて、このランダム走行は、累積的なカバレージによってますます多くの面積をカバーし、主要道路または幹線道路に偏っておりすなわちバイアスがかかっており、より小さい周囲の道路をなおざりにしている。図3において、幹線道路304および305は、スキャニング車両が非常に激しく通過しており、これらの道路用に好ましい量のスキャニングデータが得られる。しかし、道路306および307は、カバーされることがあるとしてもまれであって、なぜなら、これらの道路上には頻繁に訪れるような目的地がなく、かつ幹線道路のほうが移動に使う道としては適しているからである。結果として、アクセスポイント308および309は、スキャニング車両によって全くスキャンされておらず、この測位システムは、この道路306および307を移動するユーザを認識するのに苦戦する。その結果として、システムがスキャンデータからアクセスポイントの位置を算出することを試みる場合、入力データの偏って収集したものに限定される。図11は、結果として得られるデータ品質の相違を示す。スキャニング車両のドライバーがアクセスポイント1101の近くを通過したときに、読み取り値およびその位置を連続的に記録する。この測位システムは、次に、全ての観測されたデータ1103のセットを用いてアクセスポイント1102の位置を算出しなくてはならない。ランダムスキャニングモデルにおいては、このデータのセットはアクセスポイントを通り過ぎる一本の主要道路に限定される。それによって、このシステムにアクセスポイントの位置をこのアクセスポイント自体の近辺ではなくむしろその道の近くになるように強制的に算出させてしまう。
【0043】
別の方法としては、結果として得られるデータの収集において偏りを避けるために、目標地域のありとあらゆる道路を含むルーティングアルゴリズムを開発することであって、よってエンドユーザのためにより信頼性のある測位システムを構成することである。図4は、目標地域においてありとあらゆる道路をカバーするために最も効率的な走行ルートを算出するために、チャイニーズポストマンとして知られる最適化されたルーティングアルゴリズムを記載する。このチャイニーズポストマンルーティングアルゴリズムは、郵便機関、公共事業および国勢調査機関によって使用される公知の技術であって、オイラーサイクル問題の異型である。このオイラーサイクルは、各縁部を少なくも一回訪れる、図の最短移動を求める問題である(例として、Kwan,M.K.”Graphic ProgrammingUsing Odd or Even Points.”ChineseMath. 1,273−277,1962.を参照)。本発明の好適な実施例は、カバレージのための目標領域を認識して、車両ルートを設計するためにチャイニーズポストマンルーティングアルゴリズムを使用するための方法を含む。このスキャニング車両401は、アルゴリズムによる最適なルートをたどり、全ての観測可能なアクセスポイントがそのシステムによって検出されて地図にされることを確実にし、全ての道路に偏りがないことを示す。よって、例えば、アクセスポイント408および409は、チャイニーズポストマンモデルを使用してアクセスポイントデータベースに加えられるが、ランダムモデルを使用していたら、欠落していたかもしれない。図11を参照すると、チャイニーズポストマンスキャニングモデルでは、車両はありとあらゆる道路を通過し、アクセスポイント1104用の1セットのスキャニング記録1106を完成させる。このシステムは、次にアクセスポイントの位置1105をエラーを少なくして算出することができ、なぜならそれは、アクセスポイント1102に比してアクセスポイント1104のスキャンデータがより画一的に分布しているためである。よって、このチャイニーズポストマンスキャニングモデルは、目標地域に亘ってより画一的により多くのアクセスポイントを収集するだけではなく、結果として得られるデータによってアクセスポイント位置がより正確に算出されるのである。
【0044】
高品質APロケーション
このスキャニングデータは、一旦収集(または部分的に収集)されると、中央アクセスポイントデータベース(後述される)に戻ってアップロードされ、そこで処理される。各アクセスポイントのための未処理の観測点は、アクセスポイントの実際の物理的な位置を逆三角測量(reversetriangulate)するために使用されるか、アクセスポイントの電波の伝搬を示す電力プロファイルを生成するために使用される。特定のアクセスポイント用に最も正確に算出された位置を生成するかまたは最も正確な電力プロファイルを生成するために、スキャニング車両は出来る限り多くの異なる角度からアクセスポイントを観測しなくてはならない。ランダムモデル(図3)において、多くのアクセスポイントがたった一つの道路から観測され、このシステムは道路303上で直接それらの位置を算出しなくてはならない。これらの位置は、方向の偏り呈し、これらのアクセスポイント302の実際の位置とは著しく異なる。そのリファレンスポイントの位置が不正確である場合、測位システムにエラーがもたらされる。よって、この測位システムにおいて、アクセスポイント位置の精度がエンドユーザ測位の精度に大きな役割を果たす。チャイニーズポストマンモデル(図4)を使用して、スキャニング車両は、アクセスポイントを収容している建物に対して可能な限り多くの方向から特定のアクセスポイントを検出する。この追加データは、アクセスポイント403の位置を算出するために使用される逆三角測量公式によって導き出される結果を著しく改善する。アクセスポイント位置品質は図11により詳細に記載されている。
【0045】
このシステムから収集されたスキャニングデータは、その特定の環境において各アクセスポイントの信号伝搬パターン用の信頼性のあるプロキシを示す。全ての無線装置および関連する周囲環境は、固有の信号指紋(signalfingerprint)を生成し、この信号指紋は、信号がどのくらい遠くまで届くか、信号指紋内の様々な位置において信号がどのくらい強いかを示す。この指紋データは、測位システムが高精度に機能するように、算出されたアクセスポイント位置に関連して使用される。この指紋は、「電力プロファイル」としても知られており、それは、各位置の信号強度が信号電力としてワットで測定されるからである。この測位システムは、802.11アクセスポイント無線装置の特定の信号強度がそのアクセスポイントからの特定の距離を関係していることを示すために指紋データを解析する。信号指紋技術が屋内Wi−Fi測位において使用されるが、その指紋の収集に関連して難点があるため、より広いエリアの屋外環境において再現することが困難であることが分かった。複数のアクセスポイントの指紋または電力プロファイルがオーバーレイする場合に、この測位システムは、観測された複数の信号強度が、結合された複数の指紋にマッチする一地点をみつけることのみによって、その装置の位置を決定することができる。本発明の好適な実施例は、指紋に基づく測位アルゴリズムを使用するために何百万ものアクセスポイントを伴う巨大なカバレージエリアに亘ってこの指紋データを獲得するために信頼性のあるシステムを提供する。
【0046】
基準対称性
測位システムは一般的に、追跡される装置の周囲の3つ以上のリファレンスポイントを備えることによって動作する。この測位システムは、その装置の現在位置を算出するために様々な方法においてこれらのリファレンスポイントからの無線信号を使用する。リファレンスポイントの数が十分でない場合、またはリファレンスポイントがユーザの周囲のバランスもしくは対称性を欠く場合に、顕著なエラーが発生する。図5において例示されるように、ランダムなモデルから現れる幹線の偏りにおいて、エンドユーザ501が、その一方向にのみ記録されたアクセスポイント位置502がある物理的エリア内に移動する場合が多く考えられる。エンドユーザの周囲のリファレンスポイントの分布におけるこの対称性の欠如によって、測位アルゴリズムは多大なエラーを伴って装置位置503を算出してしまう。アクセスポイント用にスキャニングのチャイニーズポストマンモデルを使用することによって、ユーザは一般的に、その装置の802.11無線装置の範囲604内のユーザ601の全ての方向に多くのアクセスポイント位置602が存在する物理的な位置(図6)に出る。結果として得られた位置算出603は、位置の偏りを減少させ、より正確になる。図11は、位置算出の品質における影響を示す別の例である。
【0047】
スキャニング装置
図7は、様々なWi−Fiアクセスポイントを検出し、認識するために使用されるスキャニング装置702の好適な実施例の詳細を記載している。スキャニング車両701は、GPS衛星708および802.11アクセスポイント707からの無線信号のチャンネルを連続的にスキャンするスキャニング装置702を備えている。このスキャニング装置は、全工程を制御するスキャニングクライアントソフトウェア704を作動する。このスキャニングクライアントは、GPSレシーバ705および802.11無線装置706の両方を作動させる。このGPSレシーバは、2秒毎にその装置の地理的位置を算出する連続的な受信モードにセットされる。その算出は、スキャニングクライアントによって読み込まれ、ローカルデータ格納部703に格納される。スキャニングクライアントは、802.11無線装置を起動し、指向性アンテナ709を用いて802.11探査要求(proberequest)を送信し始める。そのプローブ要求の範囲内の802.11アクセスポイント707が802.11プロトコルに従って信号ビーコンを伴って応答する。この応答する信号ビーコンには、アクセスポイントのネットワーク名(SSIDとして知られる)と、アクセスポイント装置のMACアドレスと、アクセスポイントについての他のメタ情報とが含まれる。応答する信号は、出所のベクトルおよびアクセスポイントの近接度に基づき、信号の異なる強度を伴って指向性アンテナに到達する。そのベクトルは、その特定のアンテナの認識と、アクセスポイントについてのメタ情報と共に記録される。この探査−受信‐記録処理は、10分の一秒毎に連続してなされる。配備されるスキャニング装置は、XTracv.2.0 firmwareを備える一体化されたSiRFII type GPS レシーバを備えるiPAQ 4155 Pocket PCとPowered GPS PDA Mount Cradleとの組合せである。
【0048】
特定の実施例のスキャニングクライアント704は、図10に記載されている。クライアントは、データマネージャ(DataManager)1001、システムマネージャ(System Manager)1002およびアップロードマネージャ(Upload Manager)1003の3つの主要部からなる。データマネージャ1001は、GPS無線装置1006および802.11無線装置1007の両方の動作を制御する。データマネージャは、いつ、どのくらいの頻度で、これらの無線装置が信号をスキャンし、これらの信号を処理するかを制御する。一旦起動されたGPS無線装置は、複数のGPS衛星1004から信号を受信し、このGPS無線装置の地理的位置を算出する。GPSレコーダ1008は、2秒毎にこれらの読み取り値の全てをログ記録し、それらをファイルマネージャ1010に送る。Wi−Fiレコーダ1009は、802.11無線装置を一秒の10分の一秒毎にスキャンするように起動させ、これらの802.11読み取り値をGPS無線装置から来るGPS読み取り値に関連付け、結果として得られたデータをファイルマネージャに送る。ファイルマネージャは、GPSレコーダおよびWi−Fiレコーダの両方からスキャンデータを受け取り、この装置に保管ファイルを生成する。この処理は、その装置が動作しており、かつ両方の無線装置が機能しているときはずっと続く。
【0049】
アップロードマネージャ1003にはホットスポット検出器1017があり、このホットスポット検出器1017は、その装置がアクセスを許可された公共のホットスポット1024(例えばT−モバイル)のネットワークを探すために802.11スキャニングの結果を監視する。一旦それが有効なホットスポットを検出すると、その存在をユーザに知らせる。そのユーザは、クリエイトコネクション要素(CreateConnection component)1018を起動することによってそのホットスポットに接続することを選択できる。この要素は、ホットスポットのアクセスポイントに関連し、802.11接続をつくる。次に、ホットスポット認証モジュール(HotspotAuthentication module)1019は、この装置のための有効な認証情報を供給する。このホットスポットは、アカウントを確認し、次にこの装置にネットワークアクセスを提供する。アップロードマネージャは、次に中央ネットワークサーバ1025に接続するためにアップロードサーバ認証処理1020を開始し、有効な認証情報を提供する。一旦認証されると、アップロード・アンド・データ検証モジュール(Upload& Data Verification module)1021が作動し始める。このモジュールは、スキャニングデータ記憶装置1011からスキャンデータを検索し、FTPを使用する中央ネットワークサーバにデータをアップロードする。この中央ネットワークサーバは、全てのデータを中央アクセスポイントデータベースに格納するために処理を開始する。アップロードが完了したのち、このアップロード処理は、スキャンデータをスキャニングデータ記憶装置1011からこの装置のバックアップデータ記憶装置1012に移動する。一旦このアップロードが完了し、検証されると、ニューバージョンモジュール1022が、この装置のために利用可能なクライアントソフトウェアの新しいバージョンがあるかどうかを決定するために、中央ネットワークサーバをチェックする。新しいバージョンがある場合には、このソフトウェアはダウンロードされ、ニューバージョンインストール1023処理がこのクライアントソフトウェアをアップグレードするのを開始する。一旦このインストール処理が完了すると、中央ネットワークサーバへの接続が終了し、ホットスポットへの接続が終了し、この装置は通常のスキャニング動作に戻る。
【0050】
スキャニングクライアント704には、この装置を管理し、システムエラーを減らすことを助ける1セットのユーティリティが備えられている。無線装置マネージャ1013は、GPS無線装置およびWi−Fi無線装置の動作を監視し、それらが正しく機能していることを確実にする。この無線装置マネージャは、無線装置のひとつに問題があることを発見すると、その無線装置を再起動する。ユーザインターフェイスコントローラ1014は、ユーザにツールを示し、アップデートして、ユーザがこの装置を効果的に操作できるようにする。エラーハンドリングおよびロギング1015は、全てのシステム問題を装置に記録し、ユーザに警告をして、対処できるようにする。システム再起動モジュール1016は、問題が解決できない場合に呼び出される。このモジュールは、装置をシャットダウンして、ハードウェア、オペレーティングシステムおよびスキャニングクライアンを再起動させ、正しく作動することを確実にする。
【0051】
1秒の十分の一秒の802.11スキャニングインターバルが選択された。それは、既製品のハードウェアを使用した場合にこれらの条件のもとで802.11のための最適なスキャン期間であるからである。802.11b/g/nは、無許可のスペクトラムの14チャネルを用いて動作する。各アクセスポイントは、所定の時間に、これらのチャンネルの一つにその信号ビーコンを同報する。このスキャニング装置は、可能な限り多くのアクセスポイントを観測するために各チャネルを調査する必要がある。このスキャニングインターバルは、スキャニング車両の平均速度に相関しており、スキャニングクライアントがどのように特定の領域の頻繁に訪れる場所(frequencyreal estate)をカバーするかを最適化する。
【0052】
中央ネットワークサーバ
図8を参照すると、車両の一隊は、予め設計されたルートを走行する間、スキャニングルーチンを実行する。周期的に各車両801は、利用可な802.11アクセスポイントに接続し、中央ネットワークサーバのデータコミュニケーションモジュール807で認証する。一般には、中央ネットワークサーバと通信するために使用されるアクセスポイントは、メーターで測定された信頼性のあるアクセスを確実にするT−Mobileによって操作されるような公共のホットスポットである。この接続の提供は使用可能な公共のアクセスポイントのいずれかを介してなされる。このスキャニング車両は、近くのホットスポット位置で止まり、アクセスポイントへの接続の処理を開始する。一旦認証されると、スキャニングクライアント704は、ローカル格納部703から最近収集されたスキャンデータの全てを認識し、このデータを中央ネットワークデータベース802にアップロードする。
【0053】
一旦このデータがデータベースにアップロードされると、パーサおよびフィルタ処理803が始まる。このパーサおよびフィルタ処理は、アップロードスキャニングデータの全てを読み取り、データベースの適当なテーブルにそれをロードする。この実行の間、データは、品質問題において評価される。場合によっては、GPSレシーバは、ある期間、誤りまたはエラー記録を記録することもできるが、これによって最終アクセスポイント位置算出によくない影響がでる恐れがある。パーサおよびフィルタ処理は、これらの不良記録を認識し、修正するか、またはシステムから除去する。フィルタ処理は、クラスター化技術を使用し、エラーを起こしやすいGPS読み取り値を除去する。例えば、読み取り値の90%が互いに200メートル内であるが、読み取り値の10%が互いに5キロメートルより離れている場合、これらの分離された値はフィルタによって除去され、更なる分析のためにデータベースの損傷を受けたテーブルに保存される。特に、このシステムは、まず、全ての報告されたデータを使用してアクセスポイントのために重み付けされた重心を算出する。次に、報告された位置の分布に基づいて、標準偏差を決定する。このシステムは、エラーとなっているアクセスポイントを除去するためにこの分布のシグマ(標準偏差)に基づいて、設定可能な閾値を使用する。一旦これらのエラー記録がマーキングされると、この重心は、後述の逆三角測定法を用いて、最終重心を決定するために残りの位置記録によって再算出される。
【0054】
アクセスポイントが移動した結果、エラー記録ができることに留意されたい。この場合、複数のアクセスポイントの重心は、記録の優勢に基づき、新しい場所に迅速に「スナップ(瞬時に飛ぶ)」する。更に向上したアルゴリズムには、新しい記録が所与のアクセスポイントの現在位置をより強く表示するように記録の新旧に基づく重み付けの値が含まれるであろう。
【0055】
一旦、パーサ(構文解析)処理が完了すると、中心ネットワークシステムは、逆三角測量モデル804に新しいデータの処理を開始させる。この処理の間、1)新しいアクセスポイントがデータベースに加えられ、それらの物理的な位置が算出され、2)現存のアクセスポイントが、スキャナーによって記録された新しいデータに基づいて再測位される。逆三角測量アルゴリズムは、準重み付けされた平均モデルを備える弱い信号より強い信号読み取りを重み付けするために、記録の数と、関連する信号読み取り値とを計算に入れる。
【0056】
データ収集の間、WPSユーザは、利用可能なWi−Fiアクセスポイントから受信された信号強度(ReceivedSignal Strength(RSS))を測定し、対応するアクセスポイントの位置情報を抽出する、Wi−Fiレシーバ装置を備える。アクセスポイントのRSS値は、下記のようである:
{RSS1, RSS2,...RSSn}
【0057】
アクセスポイントiの対応して記録されたGPS位置が{Lati,Longi}で表示され、算出されたアクセスポイント位置が{Lati,Longi}で表示され、三角測量された位置が下記のようなアルゴリズムを適用することによって求められる:
【0058】
電力の4平方根は、アルゴリズムの実現を容易にするために選択される。それは、4平方根は、2平方根をとるのと同義であるからである。
【0059】
二つ目は、係数のダイナミックレンジを調整することに関する。係数のダイナミックレンジが問題となっている場合、アルゴリズムの係数を例えば下記の定数によって割ることができる。
【0060】
パラメータCは、どのような数字であってもよく、理論的には結果には影響しない。重み付けされた平均が係数の比率に基づいており、絶対値ではないため、理論的には、全ての係数を定数Cで割ることによって、結果に影響することはないが、係数の値のダイナミックレンジを変える。
【0061】
この最終の{Lati,Longi}は次に、そのアクセスポイントの位置のための最終重心値として使用される。次に、緯度および経度が、三角測定値がどのくらい新しいかを表示するためのタイムスタンプを含んで、データベースに格納される。
【0062】
中央ネットワークデータベースがアップデートされて、各アクセスポイントが再測位された後に、データパックビルダー(DataPack Builder)805は国または世界の複数域に基づいてデータベースのサブセットを作る。このパックビルダーは、様々な使用において特定の地域のみが必要である場合にデータベースの提供を容易にする。パックビルダーは、国、タイムゾーンおよび都市圏を示す地域座標によって構成される。この技術を利用して、例えばユーザは、米国の西海岸用の位置データのみをダウンロードすることができる。パックビルダーは、複数のデータ記録を分割し、圧縮する。
【0063】
フリートマネジメントモジュール806は、業務職員がスキャニング車両を管理するのを助け、経路選択を固守するのを確実にする。このモジュールは、全てのスキャンデータを処理し、このシステムにおいて各車両の位置軌道を構築する。業務管理者は、特定の地域のためのカバレージを視覚的に検査するためにマップビルダー808を使用して車両軌道のマップを作成することができる。各装置からのGPSトラッキングデータは、カバレージの完成を確認し欠落したエリアを認識するために、ルートマッピングソフトウェアでチェックされる。均一のカバレージを検査して確認するこの機能によって、このシステムが可能な限り最良のデータを得ることが確実になる。このモジュールは更に、平均速度を測定しかつアイドルタイムを差し引くために、車両の走行時間を算出する。これらのアウトプットは、システム全体の効率の監視および将来のカバレージの計画のために使用される。
【0064】
本発明の範囲は、上記実施例に限定されず、むしろ、添付の請求の範囲によって決定され、かつ、これらの請求項には、上記記載のものを変形、改良したものも含まれるべきである。
【特許請求の範囲】
【請求項1】
およそ数十マイルの半径を有する少なくとも一つの目標地域のためのWi−Fiアクセスポイントのデータベースであって、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのWi−Fiアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するWi−Fiアクセスポイントの認識情報と、この対応するWi−Fiアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Wi−Fiアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Wi−Fiアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぐことを特徴とするデータベース。
【請求項2】
複数の目標エリアのための複数のデータベース記録を有しており、これらのデータベース記録は複数の目標エリアによって編成されることを特徴とする請求項1に記載のデータベース。
【請求項3】
Wi−Fi位置サーバであって、
およそ数十マイルの半径を有する少なくとも一つの目標地域のためのWi−Fiアクセスポイントのデータベースを備えており、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのWi−Fiアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するWi−Fiアクセスポイントの認識情報と、この対応するWi−Fiアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Wi−Fiアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Wi−Fiアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぎ、
新しく発見されたWi−Fiアクセスポイントのために前記データベースに記録を加えるためのコンピュータで実行される論理を備えており、このコンピュータ論理は、新しく発見されたWi−Fiアクセスポイントのための前記位置情報を利用するため、前記データベースに以前格納されたWi−Fiアクセスポイントの位置情報を再算出するための論理を含むことを特徴とするWi−Fi位置サーバ。
【請求項4】
エラーを起こしやすいGPS情報に基づき位置情報を認識するために、コンピュータで実行されるクラスター化論理を更に備えることを特徴とする請求項3に記載のサーバ。
【請求項5】
クラスター論理は、アクセスポイントのために報告された全ての位置情報のために重み付けされた重心位置を決定するための論理と、前記重心から離れる統計に基づく偏差の閾値を超える位置情報を認識する論理とを含み、偏っている位置情報をデータベースから除外し、Wi−Fiアクセスポイントの算出された位置に影響を与えないようにすることを特徴とする請求項4に記載のサーバ。
【請求項1】
およそ数十マイルの半径を有する少なくとも一つの目標地域のためのWi−Fiアクセスポイントのデータベースであって、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのWi−Fiアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するWi−Fiアクセスポイントの認識情報と、この対応するWi−Fiアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Wi−Fiアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Wi−Fiアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぐことを特徴とするデータベース。
【請求項2】
複数の目標エリアのための複数のデータベース記録を有しており、これらのデータベース記録は複数の目標エリアによって編成されることを特徴とする請求項1に記載のデータベース。
【請求項3】
Wi−Fi位置サーバであって、
およそ数十マイルの半径を有する少なくとも一つの目標地域のためのWi−Fiアクセスポイントのデータベースを備えており、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのWi−Fiアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するWi−Fiアクセスポイントの認識情報と、この対応するWi−Fiアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Wi−Fiアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Wi−Fiアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぎ、
新しく発見されたWi−Fiアクセスポイントのために前記データベースに記録を加えるためのコンピュータで実行される論理を備えており、このコンピュータ論理は、新しく発見されたWi−Fiアクセスポイントのための前記位置情報を利用するため、前記データベースに以前格納されたWi−Fiアクセスポイントの位置情報を再算出するための論理を含むことを特徴とするWi−Fi位置サーバ。
【請求項4】
エラーを起こしやすいGPS情報に基づき位置情報を認識するために、コンピュータで実行されるクラスター化論理を更に備えることを特徴とする請求項3に記載のサーバ。
【請求項5】
クラスター論理は、アクセスポイントのために報告された全ての位置情報のために重み付けされた重心位置を決定するための論理と、前記重心から離れる統計に基づく偏差の閾値を超える位置情報を認識する論理とを含み、偏っている位置情報をデータベースから除外し、Wi−Fiアクセスポイントの算出された位置に影響を与えないようにすることを特徴とする請求項4に記載のサーバ。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2012−39628(P2012−39628A)
【公開日】平成24年2月23日(2012.2.23)
【国際特許分類】
【出願番号】特願2011−185773(P2011−185773)
【出願日】平成23年8月29日(2011.8.29)
【分割の表示】特願2007−539226(P2007−539226)の分割
【原出願日】平成17年10月28日(2005.10.28)
【出願人】(507135744)スカイフック ワイヤレス,インク. (12)
【Fターム(参考)】
【公開日】平成24年2月23日(2012.2.23)
【国際特許分類】
【出願日】平成23年8月29日(2011.8.29)
【分割の表示】特願2007−539226(P2007−539226)の分割
【原出願日】平成17年10月28日(2005.10.28)
【出願人】(507135744)スカイフック ワイヤレス,インク. (12)
【Fターム(参考)】
[ Back to top ]