(57)【要約】  ロケーションビーコンデータベースおよびサーバ、ロケーションビーコンデータベースを構築する方法、ならびにこれを使用するロケーションベースのサービス。Ｗｉ−Ｆｉアクセスポイントが、Ｗｉ−Ｆｉアクセスポイントの位置のリファレンスデータベースを構築するために、地理的標的エリアに測位される。  少なくとも一の車両が、ＧＰＳ装置およびＷｉ−Ｆｉ無線装置を有する少なくとも一つのスキャニング装置と、Ｗｉ−Ｆｉアンテナシステムとを備えて展開される。この目標エリア内を、幹線の偏りを避けるためにプログラムされたルートで移動する。このプラグラムに基づいたルートは、地理的目標エリアの実質的に全ての走行可能な道路を含み、かつ、前記走行可能な道路によって示されるグラフのオイラーサイクル（Ｅｕｌｅｒｉａｎ  ｃｙｃｌｅ）問題を解くものである。目標地エリア内を移動する間、ＧＰＳ装置のＧＰＳ座標を周期的に受信する。目標地域を移動する間、Ｗｉ−Ｆｉ装置の範囲において複数のＷｉ−ＦｉアクセスポイントからのＷｉ−Ｆｉ信号を検出し、これらのＷｉ−ＦｉアクセスポイントからのＷｉ−Ｆｉ信号が検出された場合に、車両のＧＰＳ位置情報に関連して検出されたＷｉ−Ｆｉアクセスポイントの認識情報を記録する。この位置情報は、検出されたＷｉ−  Ｆｉアクセスポイントの位置を逆三角測量（ｒｅｖｅｒｓｅ  ｔｒｉａｎｇｕｌａｔｅ）するために使用され、検出されたアクセスポイントの位置は、リファレンスデータベースに記録される。Ｗｉ−Ｆｉ無線装置を備えるユーザ装置を測位することができる。目標エリアにおいて複数のＷｉ−Ｆｉアクセスポイントの算出された位置のリファレンスデータベースが提供される。Ｗｉ−Ｆｉ無線装置を備えるユーザ装置の位置を決定するためのユーザアプリケーション要求に応答して、Ｗｉ−Ｆｉ無線装置の範囲内の全てのＷｉ−Ｆｉアクセスポイントに要求を送信するためにＷｉ−Ｆｉ無線装置を起動させる。Ｗｉ−Ｆｉ装置の範囲内において前記Ｗｉ−Ｆｉアクセスポイントからからのメッセージを受信する（ここで、各メッセージはこのメッセージを送るＷｉ−Ｆｉアクセスポイントを特定するものである）。前記Ｗｉ−Ｆｉアクセスポイントによって受信されたメッセージの信号強度を算出する。認識されたＷｉ−Ｆｉアクセスポイントの算出された位置を獲得するためにリファレンスデータベースにアクセスする。受信されたメッセージを介して認識されたＷｉ−Ｆｉアクセスポイントの数に基づいて、複数の位置決定アルゴリズムから対応する位置決定アルゴリズムを選択する（ここで、この選択されたアルゴリズムは、認識されたＷｉ−Ｆｉアクセスポイントの数に適するものである）。前記ユーザ装置の位置を決定するために、前記認識されたＷｉ−Ｆｉアクセスポイントの算出された位置、前記受信されたメッセージの信号強度、および前記選択された位置決定アルゴリズムを使用する。このデータベースは、先に決定された位置の質を向上するために新しく加えられた位置情報で変更することができ、エラーを起こしやすい情報を避ける。  【選択図】  図２
2008519495.tif 000002
【特許請求の範囲】
【請求項１】
Ｗｉ−Ｆｉアクセスポイントの位置のリファレンスデータベースを構築するために地理的目標エリアにおいて複数のＷｉ−Ｆｉアクセスポイントを測位する方法であって、
ＧＰＳ装置およびＷｉ−Ｆｉ無線装置を備える少なくとも一つのスキャニング装置と、Ｗｉ−Ｆｉアンテナシステムとを含む少なくとも一つの車両を配備する工程、
幹線の偏りを避けるためにプログラムに基づいたルートで前記目標エリアを移動する工程、ここで、前記プログラムに基づいたルートは、前記目標エリアにおいて実質的に全ての走行可能な道路を含み、この走行可能な道路によって示される図のオイラーサイクル問題を解くものであり、
前記目標エリアを移動する間、ＧＰＳ装置のＧＰＳ座標を周期的に受信する工程、
前記目標エリアを移動する間、前記Ｗｉ−Ｆｉ無線装置の範囲において複数のＷｉ−ＦｉアクセスポイントからのＷｉ−Ｆｉ信号を検出し、これらのＷｉ−ＦｉアクセスポイントからのＷｉ−Ｆｉ信号が検出された場合に、車両のＧＰＳ位置情報に関連して検出されたＷｉ−Ｆｉアクセスポイントの認識情報を記録する工程、
前記検出されたＷｉ−Ｆｉアクセスポイントの位置を逆三角測量するために前記位置情報を使用する工程、
前記検出されたアクセスポイントの位置をリファレンスデータベースに記録する工程、
とを備えることを特徴とする方法。
【請求項２】
目標エリアは、およそ数十マイルの半径を有することを特徴とする請求項１に記載の方法。
【請求項３】
プログラムに基づいたルートは、チャイニーズポストマンルーティングアルゴリズムを使用して決定されることを特徴とする請求項１に記載の方法。
【請求項４】
リファレンスデータベースは、離れて配置されており、Ｗｉ−Ｆｉアクセスポイントの位置情報は、Ｗｉ−Ｆｉネットワークを介してリファレンスデータベース内にロードされることを特徴とする請求項１に記載の方法。
【請求項５】
Ｗｉ−Ｆｉ信号を検出した場合に、一組の読み取り値がこの所与のＷｉ−Ｆｉアクセスポイントのために生成されるように複数のＷｉ−Ｆｉ信号の読み取りが所与のＷｉ−Ｆｉアクセスポイントのためになされ、この一組の読み取り値は、検出されたＷｉ−Ｆｉアクセスポイントの位置を決定するときに使用されることを特徴とする請求項１に記載の方法。
【請求項６】
Ｗｉ−Ｆｉアクセスポイントを検出した場合、このＷｉ−Ｆｉアクセスポイントからの信号についての信号強度情報がスキャニング装置によって算出され、記録されることを特徴とする請求項１に記載の方法。
【請求項７】
所与のＷｉ−Ｆｉアクセスポイントは、走行可能な道路の組織が与えられる場合に可能な限り多くの異なる角度から検出されることを特徴とする請求項１に記載の方法。
【請求項８】
所与のＷｉ−Ｆｉアクセスポイントは、走行可能な道路の組織が与えられる場合に可能な限り多くの異なる角度から検出されて、所与のＷｉ−Ｆｉアクセスポイントのための信号強度の電力プロファイルが決定され、記録されることを特徴とする請求項６に記載の方法。
【請求項９】
Ｗｉ−Ｆｉアンテナシステムは、複数の指向性アンテナを含んでおり、スキャニング装置は、この指向性アンテナ上でＷｉ−Ｆｉアクセスポイントによって受信される異なる信号強度に基づき、前記Ｗｉ−Ｆｉアクセスポイントの出所のベクトルを記録することを特徴とする請求項１に記載の方法。
【請求項１０】
車両のＧＰＳ座標は、連続モードで作動するＧＰＳ装置で約一秒毎に監視されることを特徴とする請求項１に記載の方法。
【請求項１１】
Ｗｉ−Ｆｉ装置は、プローブ要求を送り、約１０分の１秒毎にＧＰＳ位置情報を記録することを特徴とする請求項１に記載の方法。
【請求項１２】
複数のアクセスポイントは、複数の目標エリアのために測位されることを特徴とする請求項１に記載の方法。
【請求項１３】
リファレンスデータベースは、複数の目標エリアのための検出された複数のアクセスポイントのための位置情報を保持し、この情報は前記目標エリアに基づき編成されることを特徴とする請求項１２に記載の方法。
【請求項１４】
Ｗｉ−Ｆｉ無線装置を備えるユーザ装置を測位する方法であって、
目標エリアにおいて複数のＷｉ−Ｆｉアクセスポイントの算出された位置のリファレンスデータベースを提供する工程、
Ｗｉ−Ｆｉ無線装置を備えるユーザ装置の位置を決定するためのユーザアプリケーション要求に応答して、Ｗｉ−Ｆｉ無線装置の範囲内の全てのＷｉ−Ｆｉアクセスポイントに要求を送信するためにＷｉ−Ｆｉ無線装置を起動させる工程、
Ｗｉ−Ｆｉ装置の範囲内において前記Ｗｉ−Ｆｉアクセスポイントからからのメッセージを受信する工程、ここで、各メッセージはこのメッセージを送るＷｉ−Ｆｉアクセスポイントを特定するものであり、
前記Ｗｉ−Ｆｉアクセスポイントによって受信されたメッセージの信号強度を算出する工程、
認識されたＷｉ−Ｆｉアクセスポイントの算出された位置を獲得するためにリファレンスデータベースにアクセスする工程、
受信されたメッセージを介して認識されたＷｉ−Ｆｉアクセスポイントの数に基づいて、複数の位置決定アルゴリズムから対応する位置決定アルゴリズムを選択する工程、ここで、この選択されたアルゴリズムは、認識されたＷｉ−Ｆｉアクセスポイントの数に適するものであって、
前記ユーザ装置の位置を決定するために、前記認識されたＷｉ−Ｆｉアクセスポイントの算出された位置、前記受信されたメッセージの信号強度、および前記選択された位置決定アルゴリズムを使用する工程、
とを備えることを特徴とする方法。
【請求項１５】
認識されたＷｉ−  Ｆｉアクセスポイントの算出された位置は、Ｗｉ−Ｆｉアクセスポイントについての時間情報が前記リファレンスデータベースに含まれているため、前記対応するＷｉ−Ｆアクセスポイントが移動したか否かを決定するためにフィルタにかけられることを特徴とする請求項１４に記載の方法。  
【請求項１６】
リファレンスデータベースは、ユーザ装置に対して近くに配置されることを特徴とする請求項１４に記載の方法。
【請求項１７】
リファレンスデータベースは、ユーザ装置に対して離れて配置されることを特徴とする請求項１４に記載の方法。
【請求項１８】
ユーザ装置の位置は、緯度および経度座標を備えることを特徴とする請求項１４に記載の方法。
【請求項１９】
複数の位置決定アルゴリズムは、簡素な信号強度の重み付き平均モデルを含むことを特徴とする請求項１４に記載の方法。
【請求項２０】
複数の位置決定アルゴリズムは、直近のモデルを含むことを特徴とする請求項１４に記載の方法。
【請求項２１】
複数の位置決定アルゴリズムは、三角測量技術を含むことを特徴とする請求項１４に記載の方法。  
【請求項２２】
複数の位置決定アルゴリズムは、装置の速度に基づき適応可能な平滑化技術を含むことを特徴とする請求項１４に記載の方法。  
【請求項２３】
位置決定アルゴリズムの選択は、更に、位置要求を生成するユーザアプリケーションに基づくことを特徴とする請求項１４に記載の方法。
【請求項２４】
およそ数十マイルの半径を有する少なくとも一つの目標地域のためのＷｉ−Ｆｉ  アクセスポイントのデータベースであって、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのＷｉ−Ｆｉアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するＷｉ−Ｆｉアクセスポイントの認識情報と、この対応するＷｉ−Ｆｉ  アクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Ｗｉ−Ｆｉアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Ｗｉ−Ｆｉアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぐことを特徴とするデータベース。
【請求項２５】
複数の目標エリアのための複数のデータベース記録を有しており、これらのデータベース記録は複数の目標エリアによって編成されることを特徴とする請求項２４に記載のデータベース。
【請求項２６】
Ｗｉ−Ｆｉ位置サーバであって、
およそ数十マイルの半径を有する少なくとも一つの目標地域のためのＷｉ−Ｆｉアクセスポイントのデータベースを備えており、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのＷｉ−Ｆｉアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するＷｉ−Ｆｉアクセスポイントの認識情報と、この対応するＷｉ−Ｆｉアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Ｗｉ−Ｆｉアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Ｗｉ−Ｆｉアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぎ、
新しく発見されたＷｉ−Ｆｉアクセスポイントのために前記データベースに記録を加えるためのコンピュータで実行される論理を備えており、このコンピュータ論理は、新しく発見されたＷｉ−Ｆｉアクセスポイントのための前記位置情報を利用するため、前記データベースに以前格納されたＷｉ−Ｆｉアクセスポイントの位置情報を再算出するための論理を含むことを特徴とするＷｉ−Ｆｉ位置サーバ。
【請求項２７】
エラーを起こしやすいＧＰＳ情報に基づき位置情報を認識するために、コンピュータで実行されるクラスター化論理を更に備えることを特徴とする請求項２７に記載のサーバ。
【請求項２８】
クラスター論理は、アクセスポイントのために報告された全ての位置情報のために重み付けされた重心位置を決定するための論理と、前記重心から離れる統計に基づく偏差の閾値を超える位置情報を認識する論理とを含み、偏っている位置情報をデータベースから除外し、Ｗｉ−Ｆｉ  アクセスポイントの算出された位置に影響を与えないようにすることを特徴とする請求項２７に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概してロケーションベースのサービスに関し、より詳しくは、Ｗｉ−Ｆｉアクセスポイントの位置を決定し、この情報をＷｉ−Ｆｉ対応装置の位置を検出するために使用する方法およびシステムに関する。
【背景技術】
【０００２】
関連出願についてのクロス・リファレンス
本出願は、２００４年１０月２９日に出願された米国仮特許出願第６０／６２３，１０８号、「ロケーションビーコンデータベースを構築するためのワイヤレスデータスキャニングネットワーク」（本明細書に組み込まれる）の利益を３５  Ｕ．Ｓ．Ｃ．  §  １１９（ｅ）に基づき請求する。 
【０００３】
本出願は、上記出願と同日に出願された下記の発明の名称の米国特許出願に関する：
ロケーションビーコンデータベース；
ロケーションビーコンデータベースをアップデートするためのサーバ；
ユーザ装置の範囲内に検出されたアクセスポイントの数に基づきロケーションアルゴリズムを選択するロケーションベースのサービス；および
ロケーションビーコンデータベースのための方法およびシステム 
【０００４】
関連技術
近年、モバイルコンピュータの数が劇的に増加しており、より高度なモバイルおよびワイヤレスサービスの必要性が生じている。モバイルＥメール、ウォーキートーキーサービス、マルチプレイヤ・ゲームおよびコールフォロイング（ｃａｌｌ  ｆｏｌｌｏｗｉｎｇ）が、新しいアプリケーションがどのようにモバイル機器に現れているかを示す例である。更に、ユーザは、その現在地を利用するだけではなく、他人とその位置情報を共有するアプリケーションを求め始めている。親が子供の行方を監視したり、会社の管理者がこの会社の配達車両の位置を監視する必要があったり、出張旅行者が処方箋を受け取るため、最も近い薬局を見つけるために調べたりする。これらの例全ては、かれらが自身のまたは関係する他者の居場所を知る必要がある。現在に至るまで、我々は、誰かに方向を尋ねたり、我々の所在を尋ねるために誰かに電話したり、従業員に彼らの位置を時々報告させたりすることに全て依存している。
【０００５】
ロケーションベースのサービスは、モバイルアプリケーションの新たに出現してきている分野であって、現在地を算出し、ユーザに報告する新しい装置の機能に影響している。これらのサービスの例としては、付近の天気、最新交通情報、走行方向、子供の追跡、位置特定（ｆｒｉｅｎｄ  ｆｉｎｄｅｒ）、都市案内サービスが含まれる。これらの新しい位置検出装置は、全て同じ一般的な概念を使用する様々な技術に依存している。既知のリファレンスポイント（基準点）から来る無線信号を使用して、これらの装置はこれらのリファレンスポイントと比較してユーザの位置を数学的に算出することができる。これらの方法はそれぞれ、無線技術および、測位アルゴリズムに基づく強みまたは弱点がある。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
米国政府が運用するグローバルポジショニングシステム（ＧＰＳ）は、リファレンスポイントとして何ダースもの軌道衛星を利用している。これらの衛星は、複数のＧＰＳレシーバによって受信される無線信号を同報する。レシーバは、信号がレシーバに届くまでの時間を測定する。３つ以上のＧＰＳ衛星から信号を受信した後、レシーバは地球上でその位置を三角測量することができる。このシステムが効率的に動作するために、無線信号は、その信号がほとんどまたは全く干渉されることなくレシーバに届かなくてはならない。レシーバは３つ以上の衛星へのクリアな見通しを必要とするため、天気、建築物および植物の葉が干渉となり得る。干渉は、多重通路として知られる現象によっても引き起こされ得る。衛星からの無線信号が物理的構造物に反射し、同一の衛星からの多重信号を異なる時間にレシーバに到達させてしまう。レシーバの算出は、信号がレシーバに届くまでの時間に基づいてなされるため、多重通路信号は、レシーバを混乱させ、重大なエラーを発生させてしまう。
【０００７】
携帯電話中継地を利用した三角測量法は、ユーザまたは装置の位置を決定するために無線会社および携帯電話会社によって使用される別の方法である。無線ネットワークおよび携帯装置は、ネットワークがこの装置の位置を算出するために使用することができる信号情報を共有するために互いに通信する。これらの信号は目標地点への直線的見通しを必要とすることなく、建築物をより透過することができるため、この方法は、ＧＰＳに対する優位モデルとして当初は見られた。残念なことに、これらの方法は、多重通路信号の問題および携帯電話中継地の測位においての画一性の欠如の問題に加え、携帯電話中継地は本質的に不均一なために最適ではないことが証明されている。
【０００８】
アシスト付きＧＰＳ（Ａｓｓｉｓｔｅｄ  ＧＰＳ（Ａ−ＧＰＳ））はＧＰＳと携帯電話中継地の両方の技術を組み合わせた更に新しいモデルであって、モバイルユーザのより正確かつ信頼性の高い位置の算出を行う。このモデルにおいて、無線ネットワークは、ＧＰＳ衛星の時計オフセットについての情報と、接続された携帯電話中継地の位置に基づくユーザの一般的な位置についての情報とを送信することによってＧＰＳが信号受信を改善することを助ける試みである。これらの技術は、ＧＰＳレシーバが、屋内にいるときなどに経験する弱い信号を処理することを助け、レシーバが最も近い衛星の「固定（ｆｉｘ）」を迅速に得て、より速い「第１の読み込み（ｆｉｒｓｔ  ｒｅａｄｉｎｇ）」をする。これらのシステムは、都心から１００メートル以上離れた所では応答時間が遅く、正確性に欠けるという問題に悩まされている。
【０００９】
ＧＰＳ、Ａ−ＧＰＳおよび携帯電話中継地を利用した測位の公知の問題を解決すべく開発された最近の代替モデルがいくつかある。その一つとして、ＴＶ−ＧＰＳとして知られるものは、テレビ塔からの信号を利用する。（例えば、Ｍｕｔｈｕｋｒｉｓｈｎａｎ，Ｍａｒｉａ  Ｌｉｊｄｉｎｇ，Ｐａｕｌ  Ｈａｖｉｎｇａ，Ｔｏｗａｒｄｓ  Ｓｍａｒｔ  Ｓｕｒｒｏｕｎｄｉｎｇｓ：Ｅｎａｂｌｉｎｇ  Ｔｅｃｈｎｉｑｕｅｓ  および  Ｔｅｃｈｎｏｌｏｇｉｅｓ  ｆｏｒ  Ｌｏｃａｌｉｚａｔｉｏｎ，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ｖｏｌｕｍｅ  ３４７９，Ｊａｎ  ２Ｈａｚａｓ，Ｍ．，Ｓｃｏｔｔ，Ｊ．，Ｋｒｕｍｍ，Ｊ．：Ｌｏｃａｔｉｏｎ−Ａｗａｒｅ  Ｃｏｍｐｕｔｉｎｇ  Ｃｏｍｅｓ  ｏｆ  Ａｇｅ．  ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ，  ３７（２）：９５−９７，Ｆｅｂ  ２００４  ００５，Ｐａ００５，Ｐａｇｅｓ  ３５０−３６２を参照。）このコンセプトは、ほとんどの都市部には３つ以上のテレビ塔があるという実状に依存している。専用のハードウェアチップが、様々なテレビ塔から出るテレビ信号を受信し、リファレンスポイントとしてこれらのテレビ塔の既知の位置を利用する。この方式に直面する問題は、新しいハードウェアレシーバのコストと、リファレンスポイントの少ない一組を使用することによる制約である。例えば、ユーザがテレビ塔の周辺部の外にいる場合、このシステムは妥当な精度を出すのに困難な場合が見られる。この典型的な例は、海岸線にいるユーザである。海にはテレビ塔がないため、リファレンスポイントにおいて基準対称性（ｒｅｆｅｒｅｎｃｅ  ｓｙｍｍｅｔｒｙ）を提供することができず、内陸のユーザのほうがより正確に位置を算出することができる。
【００１０】
マイクロソフト社およびインテル社は（ＰｌａｃｅＬａｂとして知られる調査団体を介して）、Ｗｉ−Ｆｉスキャンデータを公衆の共有ウェブに提供するアマチュアユーザ（「ウォードライバー」（ｗａｒｄｒｉｖｅｒｓ）として知られる）から得られるアクセスポイントの位置を使用するＷｉ−Ｆｉ測位システムを開発した。（例えば、ＬａＭａｒｃａ，Ａ．，ｅｔ．ａｌ．，Ｐｌａｃｅ  Ｌａｂ：  Ｄｅｖｉｃｅ  Ｒａｄｉｏ  Ｕｓｉｎｇ  Ｒａｄｉｏ  Ｂｅａｃｏｎｓ  ｉｎ  ｔｈｅ  Ｗｉｌｄを参照。）  例としてはＷｉＧＬＥ、Ｗｉ−ＦｉＭａｐｓ．ｃｏｍ、Ｎｅｔｓｔｕｍｂｌｅｒ．ｃｏｍおよびＮｏｄｅＤＢが含まれる。マイクロソフト社およびインテル社の両社は、公衆のウォードライビングデータを基準位置として利用する同社のクライアントソフトウェアを開発した。個人がそのデータを自発的に供給するため、このシステムは、多くの性能および信頼性の問題が生じる。第１に、データベースのデータは、同時期に存在しておらず、一部のデータは、新しく、別の部分は３〜４年前のデータである。時間が経過すると、アクセスポイントは移動され、削除されるため、アクセスポイントの位置の新しさが重要となる。第２に、そのデータは、様々なハードウェアおよびソフトウェアを使用して作られていることである。全ての８０２．１１無線装置およびアンテナは、信号の強さの表示に影響を及ぼす異なる信号受信特性を備えている。各スキャニングソフトウェアインプリメンテーションは異なる時間間隔に異なる様式でＷｉ−Ｆｉ信号をスキャンする。第３に、ユーザによって供給されたデータは、幹線の偏り（ａｒｔｅｒｉａｌ  ｂｉａｓ）を被る。望ましいスキャンルートに従わない個人によって自己申告されているので、そのデータは交通量の激しい地域周辺に集まる傾向がある。幹線の偏りは、ユーザが現在どこにいるかに関わらず、結果として得られる位置を主要幹線道路に向かって引っ張ってしまい、重大なエラーを引き起こしてしまう。第４に、これらのデータベースは、スキャンされたアクセスポイントの算出された位置を含んでおり、８０２．１１ハードウェアで得られる未処理のスキャンデータではない。これらのデータベースのそれぞれは、アクセスポイントの位置を異なって算出し、基礎的な重み付き平均方程式で算出される。結果として、多くのアクセスポイントは実際の位置から離れた位置であるように表示され、それらには、あたかも水中に位置しているように間違って表示されたいくつかのアクセスポイントも含まれる。
【００１１】
屋内測位用のＷｉ−Ｆｉ測位システムは商業的に多く出回っている。（例えば、  Ｋａｖｉｔｈａ  Ｍｕｔｈｕｋｒｉｓｈｎａｎ，Ｍａｒｉａ  Ｌｉｊｄｉｎｇ，Ｐａｕｌ  Ｈａｖｉｎｇａ，Ｔｏｗａｒｄｓ  Ｓｍａｒｔ  Ｓｕｒｒｏｕｎｄｉｎｇｓ：Ｅｎａｂｌｉｎｇ  Ｔｅｃｈｎｉｑｕｅｓ  および  Ｔｅｃｈｎｏｌｏｇｉｅｓ  ｆｏｒ  Ｌｏｃａｌｉｚａｔｉｏｎ，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ｖｏｌｕｍｅ  ３４７９，Ｊａｎ  ２Ｈａｚａｓ，Ｍ．，Ｓｃｏｔｔ，Ｊ．，  Ｋｒｕｍｍ，Ｊ．：Ｌｏｃａｔｉｏｎ−Ａｗａｒｅ  Ｃｏｍｐｕｔｉｎｇ  Ｃｏｍｅｓ  ｏｆ  Ａｇｅ．ＩＥＥＥ  Ｃｏｍｐｕｔｅｒ，３７（２）：９５−９７，Ｆｅｂ  ２００４００５，Ｐａ００５，Ｐａｇｅｓ  ３５０−３６２を参照。）これらのシステムは、資産（ａｓｓｅｔ）および人をアドレス指定し、会社の敷地、病院、出荷所といった管理される環境内で監視するように設計されている。この典型的な例は、病院内で緊急用カートの正確な位置を監視することができるシステムであって、心停止があった場合に病院のスタッフが時間を無駄にすることなくそのカートを見つけることができるようにするものである。こうした使用の場合に要求される精度は、一般的に１〜３メートルの精度を要求する非常に高いものである。これらのシステムは、精度を微調整するための様々な技術を使用し、それには無線信号伝搬を測定するために敷地の１平方フィート毎の詳細な実地調査を行うことが含まれる。それらは、一定のネットワーク接続が必要であり、アクセスポイントおよびクライアント無線装置が、Ａ−ＧＰＳの作動の仕方に類似する同期情報を交換する。これらのシステムがこれらの屋内の場面で信頼性を高めてきたが、広域にて展開するには効果的ではない。一都市全体に亘って求められるそのような詳細な実地調査を行うことは、不可能であり、都市圏全体に亘って８０２．１１アクセスポイントと一定に通信するチャネルを、これらのシステムに要求されるようには信頼することができない。最も重要なこととして、屋外の電波の伝搬は、屋内の電波の伝搬とは基本的に異なっており、これらの屋内測位アルゴリズムは広域のケースにおいてはほぼ役に立たない。
【００１２】
ＧＰＳ位置の読み込み値と共に８０２．１１信号の存在を記録するのに利用可能である数多くの８０２．１１位置スキャニングクライアントがある。これらのソフトウェアアプリケーションは、手動で操作され、読み取り値のログファイルを生成する。これらのアプリケーションの例としては、Ｎｅｔｓｔｕｍｂｅｒ、ＫｉｓｍｅｔおよびＷｉ−ＦｉＦｏＦｕｍがある。一部の愛好者は、かれらが検出して互いに共有する８０２．１１アクセスポイントの位置をマーキングするためにこれらのアプリケーションを使用する。このデータの管理および情報の提供は、全て手動でなされる。これらのアプリケーションは、アクセスポイントの物理的な位置について計算を行なわず、アクセスポイントが検出される位置を単にマーキングするのみである。
【００１３】
基礎をなす測位システムの性能および信頼性は、ロケーションベースのサービスが良好に展開する重要な要素である。性能とは、所与の使用の場合にこのシステムが達成する精度レベルのことを指す。信頼性とは、所望の性能レベルが達成される時間率（ｐｅｒｃｅｎｔａｇｅ  ｏｆ  ｔｉｍｅ）のことを指す。 
2008519495.tif 000003
【課題を解決するための手段】
【００１４】
本発明は、ロケーションビーコンデータベースおよびサーバを提供し、ロケーションビーコンデータベースの構築およびこれを使用するロケーションベースのサービスの方法である。
【００１５】
本発明の一態様において、Ｗｉ−Ｆｉアクセスポイントが、Ｗｉ−Ｆｉアクセスポイントの位置のリファレンスデータベースを構築するために、地理的標的エリアに測位される。少なくとも一の車両が、ＧＰＳ装置およびＷｉ−Ｆｉ無線装置を有する少なくとも一つのスキャニング装置と、Ｗｉ−Ｆｉアンテナシステムとを備えて展開される。この目標エリア内を、幹線の偏りを避けるためにプログラムされたルートで移動する。このプラグラムに基づいたルートは、地理的目標エリアの実質的に全ての走行可能な道路を含み、かつ、前記走行可能な道路によって示されるグラフのオイラーサイクル（Ｅｕｌｅｒｉａｎ  ｃｙｃｌｅ）問題を解くものである。目標地エリア内を移動する間、ＧＰＳ装置のＧＰＳ座標を周期的に受信する。目標地域を移動する間、Ｗｉ−Ｆｉ装置の範囲において複数のＷｉ−ＦｉアクセスポイントからのＷｉ−Ｆｉ信号を検出し、これらのＷｉ−ＦｉアクセスポイントからのＷｉ−Ｆｉ信号が検出された場合に、車両のＧＰＳ位置情報に関連して検出されたＷｉ−Ｆｉアクセスポイントの認識情報を記録する。この位置情報は、検出されたＷｉ−Ｆｉアクセスポイントの位置を逆三角測量（ｒｅｖｅｒｓｅ  ｔｒｉａｎｇｕｌａｔｅ）するために使用され、検出されたアクセスポイントの位置は、リファレンスデータベースに記録される。
【００１６】
本発明別の態様において、地理的目標エリアは、およそ数十マイルの半径を有する。       
【００１７】
本発明別の態様において、プログラムに基づいたルートは、チャイニーズポストマンルーティングアルゴリズムを使用して決定される。
【００１８】
本発明別の態様において、Ｗｉ−Ｆｉ信号を検出した場合に、一組の読み取り値がこの所与のＷｉ−Ｆｉアクセスポイントのために生成されるように複数のＷｉ−Ｆｉ信号の読み取りが所与のＷｉ−Ｆｉアクセスポイントのためになされ、この一組の読み取り値は、検出されたＷｉ−Ｆｉアクセスポイントの位置を決定するときに使用される。
【００１９】
本発明別の態様において、Ｗｉ−Ｆｉアクセスポイントを検出した場合、このＷｉ−Ｆｉアクセスポイントからの信号についての信号強度情報がスキャニング装置によって算出され、記録される。
【００２０】
本発明別の態様において、走行可能な道路の組織が与えられる場合に可能な限り多くの異なる角度から検出される。
【００２１】
本発明別の態様において、所与のＷｉ−Ｆｉアクセスポイントは、走行可能な道路の組織が与えられる場合に可能な限り多くの異なる角度から検出されて、所与のＷｉ−Ｆｉアクセスポイントのための信号強度の電力プロファイルが決定され、記録される。
【００２２】
本発明別の態様において、Ｗｉ−Ｆｉアンテナシステムは、複数の指向性アンテナを含んでおり、スキャニング装置は、この指向性アンテナ上でＷｉ−Ｆｉアクセスポイントによって受信される異なる信号強度に基づき、前記Ｗｉ−Ｆｉアクセスポイントの出所のベクトルを記録する。
【００２３】
本発明別の態様において、アクセスポイントは、複数の目標エリアのために測位される。
【００２４】
本発明別の態様において、Ｗｉ−Ｆｉ無線装置を備えるユーザ装置を測位することができる。目標エリアにおいて複数のＷｉ−Ｆｉアクセスポイントの算出された位置のリファレンスデータベースが提供される。Ｗｉ−Ｆｉ無線装置を備えるユーザ装置の位置を決定するためのユーザアプリケーション要求に応答して、Ｗｉ−Ｆｉ無線装置の範囲内の全てのＷｉ−Ｆｉアクセスポイントに要求を送信するためにＷｉ−Ｆｉ無線装置を起動させる。Ｗｉ−Ｆｉ装置の範囲内において前記Ｗｉ−Ｆｉアクセスポイントからからのメッセージを受信する（ここで、各メッセージはこのメッセージを送るＷｉ−Ｆｉアクセスポイントを特定するものである）。前記Ｗｉ−Ｆｉアクセスポイントによって受信されたメッセージの信号強度を算出する。認識されたＷｉ−Ｆｉアクセスポイントの算出された位置を獲得するためにリファレンスデータベースにアクセスする。受信されたメッセージを介して認識されたＷｉ−Ｆｉアクセスポイントの数に基づいて、複数の位置決定アルゴリズムから対応する位置決定アルゴリズムを選択する（ここで、この選択されたアルゴリズムは、認識されたＷｉ−Ｆｉアクセスポイントの数に適するものである）。前記ユーザ装置の位置を決定するために、前記認識されたＷｉ−Ｆｉアクセスポイントの算出された位置、前記受信されたメッセージの信号強度、および前記選択された位置決定アルゴリズムを使用する。
【００２５】
本発明の別の態様において、認識されたＷｉ−Ｆｉアクセスポイントの算出された位置は、Ｗｉ−Ｆｉアクセスポイントについての時間情報が前記リファレンスデータベースに含まれているため、前記対応するＷｉ−Ｆアクセスポイントが移動したか否かを決定するためにフィルタにかけられる。
【００２６】
本発明の別の態様において、複数の位置決定アルゴリズムは、簡素な信号強度の重み付き平均モデルを含む。
【００２７】
本発明の別の態様において、複数の位置決定アルゴリズムは、直近のモデルを含む。
【００２８】
本発明の別の態様において、複数の位置決定アルゴリズムは、三角測量技術を含む。
【００２９】
本発明の別の態様において、複数の位置決定アルゴリズムは、装置の速度に基づき適応可能な平滑化技術を含む。
【００３０】
本発明の別の態様において、位置決定アルゴリズムの選択は、更に、位置要求を生成するユーザアプリケーションに基づく。  
【００３１】
本発明の別の態様において、およそ数十マイルの半径を有する少なくとも一つの目標地域のためのＷｉ−Ｆｉ  アクセスポイントのデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのＷｉ−Ｆｉアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するＷｉ−Ｆｉアクセスポイントの認識情報と、この対応するＷｉ−Ｆｉアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Ｗｉ−Ｆｉアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Ｗｉ−Ｆｉアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぐ。
【００３２】
本発明の別の態様において、Ｗｉ−Ｆｉ位置サーバは、およそ数十マイルの半径を有する少なくとも一つの目標地域のためのＷｉ−Ｆｉアクセスポイントのデータベースを備えており、このデータベースは、コンピュータ可読媒体に記録されていると共に目標エリア内の実質的に全てのＷｉ−Ｆｉアクセスポイントのためのデータベース記録を含んでおり、各記録は、対応するＷｉ−Ｆｉアクセスポイントの認識情報と、この対応するＷｉ−Ｆｉアクセスポイントの算出された位置情報とを含んでおり、この算出された位置情報は、Ｗｉ−Ｆｉアクセスポイントの複数の読み取り値を記録することから得られ、これによって、Ｗｉ−Ｆｉアクセスポイントの位置を算出する場合に基準対称を提供し、算出された位置情報における幹線の偏りを防ぎ、新しく発見されたＷｉ−Ｆｉアクセスポイントのために前記データベースに記録を加えるためのコンピュータで実行される論理を備えており、このコンピュータ論理は、新しく発見されたＷｉ−Ｆｉアクセスポイントのための前記位置情報を利用するため、前記データベースに以前格納されたＷｉ−Ｆｉアクセスポイントの位置情報を再算出するための論理を含む。
【００３３】
本発明の別の態様において、サーバは、エラーを起こしやすいＧＰＳ情報に基づき位置情報を認識するために、コンピュータで実行されるクラスター化論理を更に備える。
【００３４】
本発明の別の態様において、クラスター論理は、アクセスポイントのために報告された全ての位置情報のために重み付けされた重心位置を決定するための論理と、前記重心から離れる統計に基づく偏差の閾値を超える位置情報を認識する論理とを含み、偏っている位置情報をデータベースから除外し、Ｗｉ−Ｆｉ  アクセスポイントの算出された位置に影響を与えないようにする。
【発明を実施するための最良の形態】
【００３５】
本発明の好適な実施例は、公共および個人の８０２．１１アクセスポイントを使用して、商業的な測位システムを可能とするために基準位置データを収集するためのシステムおよび方法を提供する。好適には、このデータは、目標地域の道路を完全に探査し、カバーするためにプログラムに基づいた方法で収集される。このプログラムに基づいた方法によって、可能な限り多くのＷｉ−Ｆｉアクセスポイントを認識する。より多くのアクセスポイントについての位置情報を収集することによって、好適な実施例は、このアクセスポイントについての位置情報の多大な収集を提供するだけではなく、各アクセスポイントのための位置情報をより精度を増して算出することができる。その後、この精度の高いデータの大きな１セットは、本発明の好適な実施例を利用して、ユーザ装置をより正確に測位するようにロケーションサービスによって使用される。特定の実施例は、Ｗｉ−Ｆｉ位置の決定において間違ったデータを避けるための技術を使用し、かつ先に収集され決定された位置情報の質を改善するために、新しく発見された位置を利用する。特定の実施例は、ユーザが位置を要求した時にユーザ装置の状況に基づき位置決定アルゴリズムを使用する。例えば、この位置決定アルゴリズムは、位置要求がなされたときに認識または検出されるＷｉ−Ｆｉアクセスポイントの数に基づくか、またはその要求を出すアプリケーションに基づく。
【００３６】
図１は、Ｗｉ−Ｆｉ測位システム（Ｗｉ−Ｆｉ  ｐｏｓｉｔｉｏｎｉｎｇ  ｓｙｓｔｅｍ  （ＷＰＳ））の好適な実施例の一部を示す。この測位システムは、コンピュータであるユーザ装置１０１に収容されている測位ソフトウェア１０３を含む。特定のカバレージエリア（有効範囲）全体に亘って、制御／共通チャネル同報信号を使用して情報を同報する複数の固定ワイヤレスアクセスポイント１０２がある。このクライアント装置は、同報信号を監視するか、または、精査要求（ｐｒｏｂｅ  ｒｅｑｕｅｓｔ）を経てその送信を要求する。各アクセスポイントは、ＭＡＣアドレスとして知られる固有のハードウェア識別子を含む。クライアント測位ソフトウェアは、範囲内にある８０２．１１アクセスポイントから信号ビーコンを受信し、信号ビーコンからの特性を利用してコンピュータの地理的位置を算出する。これらの特性には、ＭＡＣアドレスとして知られる８０２．１１アクセスポイントの固有の識別子と、クライアント装置に達する信号の強度が含まれる。クライアントソフトウェアは、観測された８０２．１１アクセスポイントをアクセスポイントのリファレンスデータベース１０４内のものと比較する。このリファレンスデータベース１０４は、その装置に収容されていてもされなくてもよい。このリファレンスデータベースには、算出された地理的位置または、収集システムが収集した全てのアクセスポイントの電力プロファイルが含まれる。この電力プロファイルは、様々な位置から出る信号の電力を表示する読み取り値の集合である。これらの既知の位置を利用して、クライアントソフトウェアはユーザ装置１０１の相対位置を算出し、緯度と経度の読み取り値でその地理的座標を決定する。次に、これらの読み取り値は、ロケーションベースのアプリケーション（例えば、位置特定（フレンドファインダー）、ローカルサーチウェブサイト、フリートマネジメントシステムおよび  Ｅ９１１サービス）に供給される。
【００３７】
この測位ソフトウェア１０３は、図９により詳細に記載されており、この構成要素が例示されている。位置読み取り値を利用して、エンドユーザにある値（例えば走行方向）を提供する、アプリケーションもしくはサービス９０１が一般的に存在する。この位置（ロケーション）アプリケーションは、瞬間的にその装置の位置を測位ソフトウェアに求める。この要求によって、その装置の８０２．１１無線装置９０３に「スキャン要求」を行うスキャナー９０２が起動される。この８０２．１１無線装置は、その範囲内の全ての８０２．１１アクセスポイント９０４に探査要求（ｐｒｏｂｅ  ｒｅｑｕｅｓｔ）を送る。８０２．１１プロトコルに従って、探査要求を受信したこれらのアクセスポイントは、アクセスポイントについての情報を含む同報ビーコン（ｂｒｏａｄｃａｓｔ  ｂｅａｃｏｎ）を発信する。このビーコンには、装置のＭＡＣアドレス、ネットワーク名、それがサポートするプロトコルの正確なバージョン、およびその装置にどのように接続するかについての情報と共にセキュリティ構成が含まれる。この８０２．１１無線装置は、応答する各アクセスポイントからこの情報を収集し、各アクセスポイントの信号強度を算出し、それをスキャナーに返送する。
【００３８】
このスキャナーは、この複数のアクセスポイントの配置情報をロケータ９０６に渡し、このロケータ９０６は、アクセスポイントレファレンスデータベース９０５に対して、観測された各アクセスポイントのＭＡＣアドレスをチェックする。このデータベースは、その装置に収容されているか、またはネットワーク接続上に離れて収容されている。このアクセスポイントレファレンスデータベースは、このシステムに既知である観測された各アクセスポイントの位置データを戻す。このロケータは、各アクセスポイントから返信される信号特性と共にこの位置情報の集積を不良データフィルタ（Ｂａｄ  Ｄａｔａ  Ｆｉｌｔｅｒ）９０７に渡す。いずれかのアクセスポイントがアクセスポイントデータベースに加えられてから移動したか否かを決定するために、このフィルタは、各アクセスポイントに対して多くの比較テストを行う。不良データ記録を取り除いた後に、フィルタは、残りのアクセスポイントを位置算出要素９０８に送る。アクセスポイントデータベースから提供されるリファレンスデータおよびスキャナーから提供される信号強度読み取り値を用いて、位置算出要素がその時のこの装置の位置を計算する。ロケータに返信される前に、この位置データは、過去の一連の位置読み取り値を平均し、先の算出からの読み取り誤差を除去するために平滑化（スムージング）エンジン９０９によって処理される。調整された位置データは、次にロケータに返信される。
【００３９】
ロケータによって生成されたこの算出された読み取り値は、アプリケーションプログラミングインターフェース（ＡＰＩ）を含むアプリケーションインターフェイス９１０を通して、またはバーチャルＧＰＳ機能  ９１１を介して、これらのロケーションベースのアプリケーションに伝達される。ＧＰＳレシーバは、独自のメッセージを使用して、または、ナショナル・マリン・エレクトロニクス・アソシエーション（Ｎａｔｉｏｎａｌ  Ｍａｒｉｎｅ  Ｅｌｅｃｔｒｏｎｉｃｓ  Ａｓｓｏｃｉａｔｉｏｎ（ＮＭＥＡ））  によって開発されたような測位規格を使用して、位置読み取り値を伝達する。機器のＣＯＭポートといった標準インターフェースを使用する装置に接続することによってメッセージを読み出す。本発明の特定の実施例には、いかなるＧＰＳ汎用アプリケーションも通信モデルまたはメッセージを変化させることなくこの新しい測位システムと通信することができるバーチャルＧＰＳ機能が含まれる。
【００４０】
この位置算出は、ノイズの多いデータフローを信頼性かつ安定性のある位置読み取り値に変えることを目的とする一連の測位アルゴリズムを使用してなされる。クライアントソフトウェアは、観測されたアクセスポイントのリストを算出された信号強度と共に比較し、この装置のユーザの正確な位置を決定するためにユーザの位置を重み付けする。様々な技術が使用され、これには、簡潔な信号強度に重み付けされた平均モデルと、三角測量方式技術と組み合わされる最近傍モデルと、装置速度に基づいて適合可能な平滑化とが含まれる。シナリオが異なる場合は、異なるアルゴリズムの方がうまく機能し、最も正確な最終読み取り値を生成するために混成して使用される傾向にある。本発明の好適な実施例は、多くの測位アルゴリズムを使用することができる。どのアルゴリズムを使用するかの決定は、観測されたアクセスポイントの数と、それを使用しているユーザケースアプリケーションとによる。従来のシステムは、移動することのない既知のリファレンスポイントに頼っているため、このフィルタモデルは従来の測位システムとは異なる。好適な実施例のモデルにおいて、アクセスポイントが固定された位置にあるという仮定はなされず、アクセスポイントは測位システムによって所有されておらず、これらのアクセスポイントを移動またはオフラインにしてもよい。このフィルタリング技術は、もはやいくつかのアクセスポイントが同じ場所に位置しなくてもよく、位置が不良算出されてもよい。よって、このフィルタアルゴリズムは、アクセスポイントの位置が記録された後に移動したアクセスポイントを隔離しようとする。このフィルタは、動的であって、その時に観測されたアクセスポイントの数に基づき変更する。平滑化アルゴリズムは、単純な平均位置算出と、カルマンフィルタを含む高度なベイズの論理とを含む。速度アルゴリズムは、各アクセスポイントの信号強度観測値からドップラー効果を推定することによって装置の速度を算出する。
【００４１】
基準データベースを構築するためのスキャンデータの収集
図２は、様々なアクセスポイントの位置情報を収集するために使用される要素を示している。多くの車両２０１からなる一隊が、測位システムのためのリファレンスデータベース  （図１の１０４）を構築するために展開される。これらの車両２０１は、目標スキャンエリアを通してプログラムに基づいたルートをたどり、質の高いデータを生成する最適な方法でデータを収集する。この目標スキャンエリアは典型的に、半径１５〜２０マイル内の全ての走行可能な道路を含む大都市圏である。これらの車両は、カバレージエリアを移動する間に８０２．１１信号の位置および特性を記録するように設計されたスキャニング装置２０２を備えている。このスキャニング装置は、ＧＰＳ衛星２０４からの信号を使用して毎秒スキャニング車両の位置を追跡する。このスキャニング装置は、カバレージエリア内のいかなる８０２．１１アクセスポイントの所在も追跡し、スキャン車両のＧＰＳ位置と、アクセスポイント信号の無線特性とを記録する。収集されたデータの品質は、スキャン車両に備えられるスキャン方法によって多大に影響される。各モデルは、それぞれ利点および制限がある。ランダムモデル（Ｒａｎｄｏｍ  Ｍｏｄｅｌ）として知られる一つの方法は、車両は商用または私用で日常的に稼動することから、車両にスキャニング装置を配置するものである。これらの車両は、配達用トラック、タクシー、セールスマンまたは単に愛好家となり得る。このコンセプトは、これらの車両が、信頼性のあるリファレンスデータベースを構築するためにそれら自体のランダムな方法で時間が経つにつれて十分な道路をカバーしているであろうとするものである。このモデルは、データを収集するための簡略的な手段を実際に提供するが、結果として得られるデータの品質は、「幹線の偏り（ａｒｔｅｒｉａｌ  ｂｉａｓ）」の問題のために悪影響を受ける。図３は、このランダムモデルの課題を示している。スキャニング車両が、データを収集するよりもむしろ他の課題を解決するために設計されたルートを移動する場合（例えば、荷物の配達、出勤、帰宅）、それらは、「目的地ルート」をたどる傾向にある。目的地ルートは、ドライバーがＡからＢに行く必要がある場合であってかつそこに行くための最速ルートを求める場合のルートである。よって、ドライバーは、それが高速道路であるか大通りであるかに関わらず、最も近い主要幹線に行くための最短ルートを探す。結果として、時が経つにつれて、このランダム走行は、累積的なカバレージによってますます多くの面積をカバーし、主要道路または幹線道路に偏っておりすなわちバイアスがかかっており、より小さい周囲の道路をなおざりにしている。  図３において、幹線道路３０４および３０５は、スキャニング車両が非常に激しく通過しており、これらの道路用に好ましい量のスキャニングデータが得られる。しかし、道路３０６および３０７は、カバーされることがあるとしてもまれであって、なぜなら、これらの道路上には頻繁に訪れるような目的地がなく、かつ幹線道路のほうが移動に使う道としては適しているからである。結果として、アクセスポイント３０８および３０９は、スキャニング車両によって全くスキャンされておらず、この測位システムは���この道路３０６および３０７を移動するユーザを認識するのに苦戦する。その結果として、システムがスキャンデータからアクセスポイントの位置を算出することを試みる場合、入力データの偏って収集したものに限定される。図１１は、結果として得られるデータ品質の相違を示す。スキャニング車両のドライバーがアクセスポイント１１０１の近くを通過したときに、読み取り値およびその位置を連続的に記録する。この測位システムは、次に、全ての観測されたデータ１１０３のセットを用いてアクセスポイント１１０２の位置を算出しなくてはならない。ランダムスキャニングモデルにおいては、このデータのセットはアクセスポイントを通り過ぎる一本の主要道路に限定される。それによって、このシステムにアクセスポイントの位置をこのアクセスポイント自体の近辺ではなくむしろその道の近くになるように強制的に算出させてしまう。
【００４２】
別の方法としては、結果として得られるデータの収集において偏りを避けるために、目標地域のありとあらゆる道路を含むルーティングアルゴリズムを開発することであって、よってエンドユーザのためにより信頼性のある測位システムを構成することである。図４は、目標地域においてありとあらゆる道路をカバーするために最も効率的な走行ルートを算出するために、チャイニーズポストマンとして知られる最適化されたルーティングアルゴリズムを記載する。このチャイニーズポストマンルーティングアルゴリズムは、郵便機関、公共事業および国勢調査機関によって使用される公知の技術であって、オイラーサイクル問題の異型である。このオイラーサイクルは、各縁部を少なくも一回訪れる、図の最短移動を求める問題である（例として、Ｋｗａｎ，  Ｍ．Ｋ．”Ｇｒａｐｈｉｃ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｕｓｉｎｇ  Ｏｄｄ  ｏｒ  Ｅｖｅｎ  Ｐｏｉｎｔｓ．”Ｃｈｉｎｅｓｅ  Ｍａｔｈ．  １，２７３−２７７，１９６２．を参照）。本発明の好適な実施例は、カバレージのための目標領域を認識して、車両ルートを設計するためにチャイニーズポストマンルーティングアルゴリズムを使用するための方法を含む。このスキャニング車両４０１は、アルゴリズムによる最適なルートをたどり、全ての観測可能なアクセスポイントがそのシステムによって検出されて地図にされることを確実にし、全ての道路に偏りがないことを示す。よって、例えば、アクセスポイント４０８および４０９は、チャイニーズポストマンモデルを使用してアクセスポイントデータベースに加えられるが、ランダムモデルを使用していたら、欠落していたかもしれない。図１１を参照すると、チャイニーズポストマンスキャニングモデルでは、車両はありとあらゆる道路を通過し、アクセスポイント１１０４用の１セットのスキャニング記録１１０６を完成させる。このシステムは、次にアクセスポイントの位置１１０５をエラーを少なくして算出することができ、なぜならそれは、アクセスポイント１１０２に比してアクセスポイント１１０４のスキャンデータがより画一的に分布しているためである。よって、このチャイニーズポストマンスキャニングモデルは、目標地域に亘ってより画一的により多くのアクセスポイントを収集するだけではなく、結果として得られるデータによってアクセスポイント位置がより正確に算出されるのである。
【００４３】
高品質ＡＰロケーション
このスキャニングデータは、一旦収集（または部分的に収集）されると、中央アクセスポイントデータベース（後述される）に戻ってアップロードされ、そこで処理される。各アクセスポイントのための未処理の観測点は、アクセスポイントの実際の物理的な位置を逆三角測量（ｒｅｖｅｒｓｅ  ｔｒｉａｎｇｕｌａｔｅ）するために使用されるか、アクセスポイントの電波の伝搬を示す電力プロファイルを生成するために使用される。特定のアクセスポイント用に最も正確に算出された位置を生成するかまたは最も正確な電力プロファイルを生成するために、スキャニング車両は出来る限り多くの異なる角度からアクセスポイントを観測しなくてはならない。ランダムモデル（図３）において、多くのアクセスポイントがたった一つの道路から観測され、このシステムは道路３０３上で直接それらの位置を算出しなくてはならない。これらの位置は、方向の偏り呈し、これらのアクセスポイント３０２の実際の位置とは著しく異なる。そのリファレンスポイントの位置が不正確である場合、測位システムにエラーがもたらされる。よって、この測位システムにおいて、アクセスポイント位置の精度がエンドユーザ測位の精度に大きな役割を果たす。チャイニーズポストマンモデル（図４）を使用して、スキャニング車両は、アクセスポイントを収容している建物に対して可能な限り多くの方向から特定のアクセスポイントを検出する。この追加データは、アクセスポイント４０３の位置を算出するために使用される逆三角測量公式によって導き出される結果を著しく改善する。アクセスポイント位置品質は図１１により詳細に記載されている。
【００４４】
このシステムから収集されたスキャニングデータは、その特定の環境において各アクセスポイントの信号伝搬パターン用の信頼性のあるプロキシを示す。全ての無線装置および関連する周囲環境は、固有の信号指紋（ｓｉｇｎａｌ  ｆｉｎｇｅｒｐｒｉｎｔ）を生成し、この信号指紋は、信号がどのくらい遠くまで届くか、信号指紋内の様々な位置において信号がどのくらい強いかを示す。この指紋データは、測位システムが高精度に機能するように、算出されたアクセスポイント位置に関連して使用される。この指紋は、「電力プロファイル」としても知られており、それは、各位置の信号強度が信号電力としてワットで測定されるからである。この測位システムは、８０２．１１アクセスポイント無線装置の特定の信号強度がそのアクセスポイントからの特定の距離を関係していることを示すために指紋データを解析する。信号指紋技術が屋内Ｗｉ−Ｆｉ測位において使用されるが、その指紋の収集に関連して難点があるため、より広いエリアの屋外環境において再現することが困難であることが分かった。複数のアクセスポイントの指紋または電力プロファイルがオーバーレイする場合に、この測位システムは、観測された複数の信号強度が、結合された複数の指紋にマッチする一地点をみつけることのみによって、その装置の位置を決定することができる。本発明の好適な実施例は、指紋に基づく測位アルゴリズムを使用するために何百万ものアクセスポイントを伴う巨大なカバレージエリアに亘ってこの指紋データを獲得するために信頼性のあるシステムを提供する。
【００４５】
基準対称性
測位システムは一般的に、追跡される装置の周囲の３つ以上のリファレンスポイントを備えることによって動作する。この測位システムは、その装置の現在位置を算出するために様々な方法においてこれらのリファレンスポイントからの無線信号を使用する。リファレンスポイントの数が十分でない場合、またはリファレンスポイントがユーザの周囲のバランスもしくは対称性を欠く場合に、顕著なエラーが発生する。図５において例示されるように、ランダムなモデルから現れる幹線の偏りにおいて、エンドユーザ５０１が、その一方向にのみ記録されたアクセスポイント位置５０２がある物理的エリア内に移動する場合が多く考えられる。エンドユーザの周囲のリファレンスポイントの分布におけるこの対称性の欠如によって、測位アルゴリズムは多大なエラーを伴って装置位置５０３を算出してしまう。アクセスポイント用にスキャニングのチャイニーズポストマンモデルを使用することによって、ユーザは一般的に、その装置の８０２．１１無線装置の範囲６０４内のユーザ６０１の全ての方向に多くのアクセスポイント位置６０２が存在する物理的な位置（図６）に出る。結果として得られた位置算出６０３は、位置の偏りを減少させ、より正確になる。図１１は、位置算出の品質における影響を示す別の例である。
【００４６】
スキャニング装置
図７は、様々なＷｉ−Ｆｉアクセスポイントを検出し、認識するために使用されるスキャニング装置７０２の好適な実施例の詳細を記載している。スキャニング車両７０１は、ＧＰＳ衛星７０８および８０２．１１アクセスポイント７０７からの無線信号のチャンネルを連続的にスキャンするスキャニング装置７０２を備えている。このスキャニング装置は、全工程を制御するスキャニングクライアントソフトウェア７０４を作動する。このスキャニングクライアントは、ＧＰＳレシーバ７０５および８０２．１１無線装置７０６の両方を作動させる。このＧＰＳレシーバは、２秒毎にその装置の地理的位置を算出する連続的な受信モードにセットされる。その算出は、スキャニングクライアントによって読み込まれ、ローカルデータ格納部７０３に格納される。スキャニングクライアントは、８０２．１１無線装置を起動し、指向性アンテナ７０９を用いて８０２．１１探査要求（ｐｒｏｂｅ  ｒｅｑｕｅｓｔ）を送信し始める。そのプローブ要求の範囲内の８０２．１１アクセスポイント７０７が８０２．１１プロトコルに従って信号ビーコンを伴って応答する。この応答する信号ビーコンには、アクセスポイントのネットワーク名（ＳＳＩＤとして知られる）と、アクセスポイント装置のＭＡＣアドレスと、アクセスポイントについての他のメタ情報とが含まれる。応答する信号は、出所のベクトルおよびアクセスポイントの近接度に基づき、信号の異なる強度を伴って指向性アンテナに到達する。そのベクトルは、その特定のアンテナの認識と、アクセスポイントについてのメタ情報と共に記録される。この探査−受信‐記録処理は、１０分の一秒毎に連続してなされる。配備されるスキャニング装置は、ＸＴｒａｃ  ｖ．２．０  ｆｉｒｍｗａｒｅを備える一体化されたＳｉＲＦ  ＩＩ  ｔｙｐｅ  ＧＰＳ  レシーバを備えるｉＰＡＱ  ４１５５  Ｐｏｃｋｅｔ  ＰＣ  とＰｏｗｅｒｅｄ  ＧＰＳ  ＰＤＡ  Ｍｏｕｎｔ  Ｃｒａｄｌｅとの組合せである。
【００４７】
特定の実施例のスキャニングクライアント７０４は、図１０に記載されている。クライアントは、データマネージャ（Ｄａｔａ  Ｍａｎａｇｅｒ）１００１、システムマネージャ（Ｓｙｓｔｅｍ  Ｍａｎａｇｅｒ）１００２およびアップロードマネージャ（Ｕｐｌｏａｄ  Ｍａｎａｇｅｒ）１００３の３つの主要部からなる。データマネージャ１００１は、ＧＰＳ無線装置１００６および  ８０２．１１無線装置１００７の両方の動作を制御する。データマネージャは、いつ、どのくらいの頻度で、これらの無線装置が信号をスキャンし、これらの信号を処理するかを制御する。一旦起動されたＧＰＳ無線装置は、複数のＧＰＳ衛星１００４から信号を受信し、このＧＰＳ無線装置の地理的位置を算出する。ＧＰＳレコーダ１００８は、２秒毎にこれらの読み取り値の全てをログ記録し、それらをファイルマネージャ１０１０に送る。Ｗｉ−Ｆｉレコーダ１００９は、８０２．１１無線装置を一秒の１０分の一秒毎にスキャンするように起動させ、これらの８０２．１１読み取り値をＧＰＳ無線装置から来るＧＰＳ読み取り値に関連付け、結果として得られたデータをファイルマネージャに送る。ファイルマネージャは、ＧＰＳレコーダおよびＷｉ−Ｆｉレコーダの両方からスキャンデータを受け取り、この装置に保管ファイルを生成する。この処理は、その装置が動作しており、かつ両方の無線装置が機能しているときはずっと続く。
【００４８】
アップロードマネージャ１００３にはホットスポット検出器１０１７があり、このホットスポット検出器１０１７は、その装置がアクセスを許可された公共のホットスポット１０２４（例えばＴ−モバイル）のネットワークを探すために８０２．１１スキャニングの結果を監視する。一旦それが有効なホットスポットを検出すると、その存在をユーザに知らせる。そのユーザは、クリエイトコネクション要素（Ｃｒｅａｔｅ  Ｃｏｎｎｅｃｔｉｏｎ  ｃｏｍｐｏｎｅｎｔ）１０１８を起動することによってそのホットスポットに接続することを選択できる。この要素は、ホットスポットのアクセスポイントに関連し、８０２．１１接続をつくる。次に、ホットスポット認証モジュール（Ｈｏｔｓｐｏｔ  Ａｕｔｈｅｎｔｉｃａｔｉｏｎ  ｍｏｄｕｌｅ）１０１９は、この装置のための有効な認証情報を供給する。このホットスポットは、アカウントを確認し、次にこの装置にネットワークアクセスを提供する。アップロードマネージャは、次に中央ネットワークサーバ１０２５に接続するためにアップロードサーバ認証処理１０２０を開始し、有効な認証情報を提供する。一旦認証されると、アップロード・アンド・データ検証モジュール（Ｕｐｌｏａｄ  ＆  Ｄａｔａ  Ｖｅｒｉｆｉｃａｔｉｏｎ  ｍｏｄｕｌｅ）１０２１が作動し始める。このモジュールは、スキャニングデータ記憶装置１０１１からスキャンデータを検索し、ＦＴＰを使用する中央ネットワークサーバにデータをアップロードする。この中央ネットワークサーバは、全てのデータを中央アクセスポイントデータベースに格納するために処理を開始する。アップロードが完了したのち、このアップロード処理は、スキャンデータをスキャニングデータ記憶装置１０１１からこの装置のバックアップデータ記憶装置１０１２に移動する。一旦このアップロードが完了し、検証されると、ニューバージョンモジュール１０２２が、この装置のために利用可能なクライアントソフトウェアの新しいバージョンがあるかどうかを決定するために、中央ネットワークサーバをチェックする。新しいバージョンがある場合には、このソフトウェアはダウンロードされ、ニューバージョンインストール１０２３処理がこのクライアントソフトウェアをアップグレードするのを開始する。一旦このインストール処理が完了すると、中央ネットワークサーバへの接続が終了し、ホットスポットへの接続が終了し、この装置は通常のスキャニング動作に戻る。
【００４９】
スキャニングクライアント７０４には、この装置を管理し、システムエラーを減らすことを助ける１セットのユーティリティが備えられている。無線装置マネージャ１０１３は、ＧＰＳ無線装置およびＷｉ−Ｆｉ無線装置の動作を監視し、それらが正しく機能していることを確実にする。この無線装置マネージャは、無線装置のひとつに問題があることを発見すると、その無線装置を再起動する。ユーザインターフェイスコントローラ１０１４は、ユーザにツールを示し、アップデートして、ユーザがこの装置を効果的に操作できるようにする。エラーハンドリングおよびロギング１０１５は、全てのシステム問題を装置に記録し、ユーザに警告をして、対処できるようにする。システム再起動モジュール１０１６は、問題が解決できない場合に呼び出される。このモジュールは、装置をシャットダウンして、ハードウェア、オペレーティングシステムおよびスキャニングクライアンを再起動させ、正しく作動することを確実にする。
【００５０】
１秒の十分の一秒の８０２．１１スキャニングインターバルが選択された。それは、既製品のハードウェアを使用した場合にこれらの条件のもとで８０２．１１のための最適なスキャン期間であるからである。８０２．１１ｂ／ｇ／ｎは、無許可のスペクトラムの１４チャネルを用いて動作する。各アクセスポイントは、所定の時間に、これらのチャンネルの一つにその信号ビーコンを同報する。このスキャニング装置は、可能な限り多くのアクセスポイントを観測するために各チャネルを調査する必要がある。このスキャニングインターバルは、スキャニング車両の平均速度に相関しており、スキャニングクライアントがどのように特定の領域の頻繁に訪れる場所（ｆｒｅｑｕｅｎｃｙ  ｒｅａｌ  ｅｓｔａｔｅ）をカバーするかを最適化する。
【００５１】
中央ネットワークサーバ
図８を参照すると、車両の一隊は、予め設計されたルートを走行する間、スキャニングルーチンを実行する。周期的に各車両８０１は、利用可な８０２．１１アクセスポイントに接続し、中央ネットワークサーバのデータコミュニケーションモジュール８０７で認証する。一般には、中央ネットワークサーバと通信するために使用されるアクセスポイントは、メーターで測定された信頼性のあるアクセスを確実にするＴ−Ｍｏｂｉｌｅによって操作されるような公共のホットスポットである。この接続の提供は使用可能な公共のアクセスポイントのいずれかを介してなされる。このスキャニング車両は、近くのホットスポット位置で止まり、アクセスポイントへの接続の処理を開始する。一旦認証されると、スキャニングクライアント７０４は、ローカル格納部７０３から最近収集されたスキャンデータの全てを認識し、このデータを中央ネットワークデータベース８０２にアップロードする。  
【００５２】
一旦このデータがデータベースにアップロードされると、パーサおよびフィルタ処理８０３が始まる。このパーサおよびフィルタ処理は、アップロードスキャニングデータの全てを読み取り、データベースの適当なテーブルにそれをロードする。この実行の間、データは、品質問題において評価される。場合によっては、ＧＰＳレシーバは、ある期間、誤りまたはエラー記録を記録することもできるが、これによって最終アクセスポイント位置算出によくない影響がでる恐れがある。パーサおよびフィルタ処理は、これらの不良記録を認識し、修正するか、またはシステムから除去する。フィルタ処理は、クラスター化技術を使用し、エラーを起こしやすいＧＰＳ読み取り値を除去する。例えば、読み取り値の９０％が互いに２００メートル内であるが、読み取り値の１０％が互いに５キロメートルより離れている場合、これらの分離された値はフィルタによって除去され、更なる分析のためにデータベースの損傷を受けたテーブルに保存される。特に、このシステムは、まず、全ての報告されたデータを使用してアクセスポイントのために重み付けされた重心を算出する。次に、報告された位置の分布に基づいて、標準偏差を決定する。このシステムは、エラーとなっているアクセスポイントを除去するためにこの分布のシグマ（標準偏差）に基づいて、設定可能な閾値を使用する。一旦これらのエラー記録がマーキングされると、この重心は、後述の逆三角測定法を用いて、最終重心を決定するために残りの位置記録によって再算出される。
【００５３】
アクセスポイントが移動した結果、エラー記録ができることに留意されたい。この場合、複数のアクセスポイントの重心は、記録の優勢に基づき、新しい場所に迅速に「スナップ（瞬時に飛ぶ）」する。更に向上したアルゴリズムには、新しい記録が所与のアクセスポイントの現在位置をより強く表示するように記録の新旧に基づく重み付けの値が含まれるであろう。
【００５４】
一旦、パーサ（構文解析）処理が完了すると、中心ネットワークシステムは、逆三角測量モデル８０４に新しいデータの処理を開始させる。この処理の間、１）新しいアクセスポイントがデータベースに加えられ、それらの物理的な位置が算出され、２）現存のアクセスポイントが、スキャナーによって記録された新しいデータに基づいて再測位される。逆三角測量アルゴリズムは、準重み付けされた平均モデルを備える弱い信号より強い信号読み取りを重み付けするために、記録の数と、関連する信号読み取り値とを計算に入れる。
【００５５】
データ収集の間、ＷＰＳユーザは、利用可能なＷｉ−Ｆｉアクセスポイントから受信された信号強度（Ｒｅｃｅｉｖｅｄ  Ｓｉｇｎａｌ  Ｓｔｒｅｎｇｔｈ（ＲＳＳ））を測定し、対応するアクセスポイントの位置情報を抽出する、Ｗｉ−Ｆｉレシーバ装置を備える。アクセスポイントのＲＳＳ値は、下記のようである：
｛ＲＳＳ１，  ＲＳＳ２，  ．．．ＲＳＳｎ｝
【００５６】
アクセスポイントｉの対応して記録されたＧＰＳ位置が｛Ｌａｔｉ，Ｌｏｎｇｉ｝で表示され、算出されたアクセスポイント位置が｛Ｌａｔｉ，Ｌｏｎｇｉ｝で表示され、三角測量された位置が下記のようなアルゴリズムを適用することによって求められる：
2008519495.tif 000004
【００５７】
電力の４平方根は、アルゴリズムの実現を容易にするために選択される。それは、４平方根は、２平方根をとるのと同義であるからである。
【００５８】
二つ目は、係数のダイナミックレンジを調整することに関する。係数のダイナミックレンジが問題となっている場合、アルゴリズムの係数を例えば下記の定数によって割ることができる。
2008519495.tif 000005
【００５９】
パラメータＣは、どのような数字であってもよく、理論的には結果には影響しない。重み付けされた平均が係数の比率に基づいており、絶対値ではないため、理論的には、全ての係数を定数Ｃで割ることによって、結果に影響することはないが、係数の値のダイナミックレンジを変える。
【００６０】
この最終の｛Ｌａｔｉ，Ｌｏｎｇｉ｝は次に、そのアクセスポイントの位置のための最終重心値として使用される。次に、緯度および経度が、三角測定値がどのくらい新しいかを表示するためのタイムスタンプを含んで、データベースに格納される。
【００６１】
中央ネットワークデータベースがアップデートされて、各アクセスポイントが再測位された後に、データパックビルダー（Ｄａｔａ  Ｐａｃｋ  Ｂｕｉｌｄｅｒ）８０５は国または世界の複数域に基づいてデータベースのサブセットを作る。このパックビルダーは、様々な使用において特定の地域のみが必要である場合にデータベースの提供を容易にする。パックビルダーは、国、タイムゾーンおよび都市圏を示す地域座標によって構成される。この技術を利用して、例えばユーザは、米国の西海岸用の位置データのみをダウンロードすることができる。パックビルダーは、複数のデータ記録を分割し、圧縮する。
【００６２】
フリートマネジメントモジュール８０６は、業務職員がスキャニング車両を管理するのを助け、経路選択を固守するのを確実にする。このモジュールは、全てのスキャンデータを処理し、このシステムにおいて各車両の位置軌道を構築する。業務管理者は、特定の地域のためのカバレージを視覚的に検査するためにマップビルダー８０８を使用して車両軌道のマップを作成することができる。各装置からのＧＰＳトラッキングデータは、カバレージの完成を確認し欠落したエリアを認識するために、ルートマッピングソフトウェアでチェックされる。均一のカバレージを検査して確認するこの機能によって、このシステムが可能な限り最良のデータを得ることが確実になる。このモジュールは更に、平均速度を測定しかつアイドルタイムを差し引くために、車両の走行時間を算出する。これらのアウトプットは、システム全体の効率の監視および将来のカバレージの計画のために使用される。  
【００６３】
本発明の範囲は、上記実施例に限定されず、むしろ、添付の請求の範囲によって決定され、かつ、これらの請求項には、上記記載のものを変形、改良したものも含まれるべきである。
【図面の簡単な説明】
【００６４】
【図１】図１は、Ｗｉ−Ｆｉ測位システムの特定の実施例を示す。
【図２】図２は、本発明の特定の実施例による、スキャニング装置を備えるスキャニング車両を示す。
【図３】図３は、データ収集における幹線の偏りの問題点を示すためのスキャニングシナリオの一例を示す。
【図４】図４は、本発明の特定の実施例によるスキャニング車両用のプログラムに基づいたルートを使用する一例を示す。
【図５】図５は、ユーザ装置の測位においてＷｉ−Ｆｉアクセスポイントの基準対称性（ｒｅｆｅｒｅｎｃｅ  ｓｙｍｍｅｔｒｙ）の欠如の問題を例示するためのシナリオの一例を示す。
【図６】図６は、ユーザ装置の測位においてＷｉ−Ｆｉアクセスポイントの基準対称性を例示するためのシナリオの一例を示す。
【図７】図７は、本発明の特定の実施例による、スキャニング装置を備えるスキャニング車両を示す。
【図８】図８は、本発明の特定の実施例による、Ｗｉ−Ｆｉアクセスポイントの中央データベースを有する中央ネットワークサーバを示す。
【図９】図９は、本発明の特定の実施例による、測位ソフトウェアの例示的な構造を示す。
【図１０】図１０は、本発明の特定の実施例による、スキャニングクライアントの例示的な構造を示す。
【図１１】図１１は、ランダムスキャニングモデルの効果をチャイニーズポストマンルーティングアルゴリズムのモデルを使用するものとの比較、対比を示す。
【図１】
2008519495.tif 000006
【図２】
2008519495.tif 000007
【図３】
2008519495.tif 000008
【図４】
2008519495.tif 000009
【図５】
2008519495.tif 000010
【図６】
2008519495.tif 000011
【図７】
2008519495.tif 000012
【図８】
2008519495.tif 000013
【図９】
2008519495.tif 000014
【図１０】
2008519495.tif 000015
【図１１】
2008519495.tif 000016