管理用於基於網絡的定位系統的位置資料庫的製作方法

2023-05-15 03:12:01

管理用於基於網絡的定位系統的位置資料庫的製作方法
【專利摘要】本公開涉及管理用於基於網絡的定位系統的位置資料庫。描述了用於管理位置資料庫的方法、程序產品和系統。伺服器可以從位於無線通信網絡的接入點的通信範圍內的知道位置的行動裝置(例如，能夠使用GPS的設備)接收位置信息。伺服器可以為每個接入點利用接收到的位置計算平均地理位置。基於平均地理位置，伺服器可以將接入點分配給地理網格的單元。伺服器可以基於接收的數據和接入點的流行度、穩定性、壽命和新鮮度，對每個單元中的接入點進行過濾。當第二行動裝置連接到單元中的接入點時，可以基於該單元和鄰近單元中的接入點的位置確定第二行動裝置的位置。
【專利說明】管理用於基於網絡的定位系統的位置資料庫
[0001] 本申請是申請日為2010年8月25日、申請號為201080001301. 6、名稱為"管理用 於基於網絡的定位系統的位置資料庫"的發明專利申請的分案申請。

【技術領域】
[0002] 本公開一般地涉及為行動裝置確定地理位置。

【背景技術】
[0003] 無線通信網絡可以採用各種技術，以便設備無線地通信。例如，無線區域網（WLAN) 可以包括使用無線電波而不是導線在網絡的節點（例如，設備）之間進行通信的區域網 (例如，覆蓋相對小的物理區域的計算機網絡，這樣的物理區域例如家庭、辦公室、或一小群 建築物，諸如學校）。WLAN技術的某些例子包括WiFi，其可以包括基於任何電氣和電子工程 師協會（IEEE) 802. 11標準的任何WLAN產品。
[0004] 發送方和接收方之間的無線連接可以採用射頻（RF)技術，S卩，採用與無線電波傳 播相關聯的電磁頻譜中的頻率。WiFi中使用的某些示例性無線電頻率是2. 5吉赫茲（GHz) 或5GHz。當RF電流被提供給天線時，可以產生電磁場。該電磁場可以在空中傳播。一種 無線通信網絡的組件可以是接入點（AP)。接入點可以允許無線行動裝置與有線網絡通信。 接入點的一種功能可以是廣播可以由具有無線適配器的計算機或無線行動裝置檢測和"收 聽"到的無線信號。
[0005] WiFi網絡的接入點可以覆蓋某個地理區域，該地理區域由接入點發送和接收的信 號的強度和該地理區域的物理特性確定。數量可變的行動裝置可以位於接入點的通信範圍 內。一個行動裝置可以同時位於多個接入點的通信範圍內。如果接入點的位置是已知的， 通過基於所接收的來自接入點的信號的強度對行動裝置的位置進行三角測量，行動裝置有 時可以利用該行動裝置能夠與之通信的接入點的位置來確定該行動裝置的位置。


【發明內容】

[0006] 描述了用於管理基於網絡的定位系統的位置資料庫的方法、程序產品和 系統。伺服器計算機可以從位於無線通信網絡的接入點的通信範圍內的知道位置 (location-aware)的行動裝置（例如，能夠使用GPS的設備）接收位置信息。伺服器計算 機可以為每個接入點利用接收到的位置來計算平均地理位置。基於所述平均地理位置，月艮 務器計算機可以將接入點分配給地理網格的單元。伺服器計算機可以基於接收的數據和接 入點的流行度、穩定性、壽命和新鮮度，對每個單元中的接入點進行過濾。伺服器計算機可 以將接入點的標識符與所述平均地理位置相關聯地存儲在位置資料庫中。
[0007] 行動裝置可以使用該行動裝置可以與之連接的接入點的位置確定該行動裝置的 位置。在連接到地理網格上的單元中的接入點後，行動裝置可以請求和接收該接入點的位 置信息、該單元中的其它接入點的位置、以及與該單元鄰近的單元中的接入點的位置。移動 設備可以基於接收到的信息識別與該行動裝置的通信範圍內的接入點相關聯的位置。移動 設備可以使用識別出的位置計算平均地理位置。行動裝置還可以計算每個位置與所計算出 的平均值之間的距離。行動裝置可以排除與平均值相距足夠遠的位置。行動裝置可以重複 所述計算和排除，直到為該平均地理位置實現了某個精度級別。行動裝置可以在行動裝置 的地圖顯示上顯示該信息。
[0008] 可以實施用於管理基於網絡的定位系統的位置資料庫的技術，以實現下列示例性 優點。當無線通信網絡的某個接入點的實際位置未知時，一個地理區域可以與該接入點相 關聯。該地理區域可以對應於位於該接入點的通信範圍內的實際行動裝置可能位於的區 域，而不是該接入點的實際位置。可以基於來自行動裝置的實時數據估計該地理區域，該實 時數據可被頻繁更新，並且因此可以提供最新的位置信息。如果接入點已離開或被關閉，該 接入點可從資料庫中被去除，以避免無效的位置確定。可以基於在一天中的各個時間從移 動設備接收的數據來計算地理區域，從而地理區域可以對應於各種使用模式，例如，路上時 間（commute hour)、工作時間、或晚上。
[0009] 與地理區域相關聯的接入點可用於確定位於該接入點的通信範圍內的不能使用 GPS的行動裝置的位置。接入點和行動裝置之間的數據傳輸可以在行動裝置空閒時進行，以 避免幹擾行動裝置和接入點之間的正常通信。由於利用接入點的位置來確定行動裝置的位 置的系統可以傳輸直接位於行動裝置的通信範圍內的接入點的位置以及在鄰近區域中的 接入點的位置，因此，該系統可以自我限制對行動裝置的帶寬的消耗。因此，即使當移動設 備移動時，頻繁更新和重傳也是不必要的。每個單元中的接入點的過濾機制可以進一步限 制在每次傳輸中傳輸給行動裝置的數據量。與例如使用信號強度來估計位置相比，移動設 備可以更準確地估計其位置，這是由於信號強度可能由於各種幹擾而改變。當例如GPS信 號弱時（例如，在建築物內），能夠使用GPS的行動裝置可以利用無線接入點的位置。
[0010] 在下面的附圖和描述中提出了管理基於網絡的定位系統的位置資料庫的一種或 多種實現方式的細節。從該描述、附圖和權利要求書中，將明了管理位置資料庫的其它特 徵、方面和優點。

【專利附圖】

【附圖說明】
[0011] 圖1A是管理位置資料庫的技術的概覽。
[0012] 圖1B示出了管理三維空間中的位置資料庫的技術。
[0013] 圖2A - 2C不出了利用行動裝置確定與WLAN中的接入點相關聯的位置的不例性 階段。
[0014] 圖2D示出了在三維空間中利用行動裝置確定與WLAN中的接入點相關聯的位置的 示例性階段。
[0015] 圖3A和3B是示出了利用行動裝置確定與WLAN中的接入點相關聯的位置的示例 性處理的流程圖。
[0016] 圖3C是示出了實現管理位置資料庫的技術的示例性系統的框圖。
[0017] 圖4A示出了利用基於網絡的定位系統中的位置資料庫來確定行動裝置的位置的 技術。
[0018] 圖4B是示出了利用位置資料庫來確定行動裝置的位置的示例性處理的流程圖。
[0019] 圖4C是示出了確定行動裝置的位置的示例性自適應多遍處理的流程圖。
[0020] 圖5示出了利用無線接入點的位置確定行動裝置的位置的示例性用戶界面。
[0021] 圖6是用於實現參考圖1 一 5描述的特徵和操作的示例性系統體系結構的框圖。
[0022] 圖7是行動裝置的示例性體系結構的框圖。
[0023] 在各個附圖中，類似的附圖標記表示類似的元件。

【具體實施方式】
[0024] 管理位置資料庫的概述
[0025] 圖1A是管理基於網絡的定位系統的位置資料庫的技術的概覽。無線區域網 (WLAN)可以是包括若干接入點105的無線通信網絡。接入點105可以包括能夠作為用於使 無線設備連接到有線網絡的通信集線器的硬體設備或計算機軟體。多個接入點105可分布 在一個區域中（例如，辦公樓或機場）。
[0026] 接入點105可以使用各種通信協議與無線設備（例如，行動裝置108和110)通 信。在某些實現中，接入點105可以是WiFi?網絡的接入點，其執行基於電氣和電子工程 師協會（ΙΕΕΕ)802· 11的協議（例如，IEEE802. 11a)。在某些實現中，接入點105可以是 全球微波接入互操作性（WiMAX)網絡的接入點，其執行基於IEEE802. 16的協議（例如， IEEE802. 16-2004或IEEE802. 16e-2005)。接入點105可以具有一定通信範圍，取決於包括 接入點105的配置和物理環境的因素，該通信範圍可以從接入點105的位置到達從小於數 十米到數百米的任何位置。當多個行動裝置108和110位於接入點105的通信範圍內時， 行動裝置108和110可以連接到接入點。相應地，單個行動裝置108或110可以訪問多個 接入點105以便連接。行動裝置108和110可以基於各種因素選擇行動裝置108和110可 以連接到的特定接入點105。例如，該選擇可以基於行動裝置108是否被授權連接到接入點 105a，或接入點105a是否可以為到行動裝置108的無線連接提供最強的信號。
[0027] 系統可以確定與接入點105相關聯的位置區域115。可以這樣計算位置區域115， 使得它們指示位於接入點105通信範圍內的行動裝置108可能位於何處。系統可以基於 來自位於接入點105通信範圍內的行動裝置108的已知位置來進行該確定。行動裝置108 可以是知道位置（location-aware)的行動裝置，例如，能夠使用GPS的行動裝置，其內置有 或連接到可以接收全球定位系統（GPS)信號並利用GPS信號確定位置的接收器。知道位置 的行動裝置108在圖1A中被表示為黑三角。當知道位置的行動裝置108位於特定接入點 1〇5(例如，接入點105a)的通信範圍內時，知道位置的行動裝置108可以將這些設備的位 置傳輸給接入點l〇5a。接入點105a可以將該傳輸以及接入點105a的標識符轉發到系統。 系統可以確定位於接入點l〇5a的通信範圍內的任何行動裝置108或110最可能位於的估 計位置區域115a。在本說明書中，估計的位置區域115被稱為存在區域（presence area)， 以表明，當位於特定接入點105的通信範圍內時行動裝置108或110可能存在。
[0028] 為了計算存在區域115,系統可以應用迭代過程（例如，通過執行多遍分析）。該 迭代過程可以以圓的形式確定與接入點（例如，接入點105)相關聯的存在區域（例如，存 在區域115)。該圓可以具有與基於位於接入點105通信範圍內的知道位置的行動裝置108 的位置而計算的平均地理位置相對應的中心。該圓可以具有與誤差幅度（error margin) 相對應的半徑，可以根據例如行動裝置108的位置和平均地理位置之間的距離確定該誤差 幅度。下面將參考圖2和3描述關於該迭代過程的進一步細節。可以周期性地執行該迭代 過程（例如，每6個小時），以便捕捉在一天的不同時間期間的不同的無線接入使用模式，以 及捕捉接入點105的可能的移動。
[0029] 該系統可將存在區域115的信息發送給位於接入點105通信範圍內的行動裝置， 包括不能使用GPS的行動裝置（例如行動裝置110)，從而進行接收的行動裝置可以確定使 用存在區域115的設備的估計位置。例如，如果行動裝置110位於接入點105b的通信範圍 內，則行動裝置110的位置可被估計為與跟接入點l〇5b相關聯的存在區域115b相一致。
[0030] 在給定區域中（例如，機場），可能存在大量接入點105。另外，由於行動裝置110 可以移動，發送不直接位於行動裝置110的通信範圍內、但是與行動裝置110足夠靠近的接 入點的位置可能是合乎常理的，從而行動裝置110可以使用這些位置來跟蹤其移動。為了 避免向行動裝置110發送大量位置數據，系統可以對接入點105和存在區域115進行過濾， 從而僅有有限數目的接入點（例如，接入點l〇5a)的位置數據而不是世界上存在的每個接 入點的位置數據被傳輸。過濾可以基於各種因素，包括位置115和接入點105的流行度、穩 定性、壽命和新鮮度。
[0031] 為了過濾位置115和接入點105,系統可以創建包含單元102的地理網格100。單 元102可以是形狀大體為矩形的多邊形，該多邊形對應於地理網格100上可由地理區域的 標識點（例如，中心或拐角）的緯度和經度、以及大小（例如，以經度度數衡量的長度和以 維度度數衡量的寬度）來標識的地理區域。每個單元102可被用作可包含一定數量的位置 的容器。例如，單元102可以是矩形，其長度是0.0005度子午線（近似為56米），並且其寬 度是0. 0005度緯線（以米為單位的寬度可以根據緯度而改變）。單元102可被配置為擁有 與接入點105相對應的若干（例如3個）存在區域115。在某些實現中，如果存在區域115 的中心位於單元102的邊界內，則單元102可以"擁有"存在區域115。可以基於一個或多 個可靠性因素，從位於單元102中的所有存在區域115中選擇存在區域115。該選擇可以基 於各種準則，諸如，流行度、穩定性、壽命和新鮮度。
[0032] 特定接入點（例如，接入點105b)和與該接入點相關聯的存在區域（例如，存在區 域115)不必位於相同單元102中。例如當接入點105b位於單元102a中的一個建築上，並 且位於接入點105b的通信範圍內的大部分行動裝置108位於單元102b中的另一個建築中 時，這可能發生。在某些實現中，系統可以忽略接入點105b的實際位置。
[0033] 當行動裝置110連接到接入點（例如，接入點105a，其相關聯的存在區域115a位 於單元102c中）時，或以其它方式（例如，通過蜂窩網絡）連接到系統時，行動裝置110可 以從系統接收位置更新。位置更新可以包括位於存在區域115a所位於的相同單元（例如， 單元102c)中的所有存在區域115。位置更新還可以包括位於在地理網格100上與單元 102c鄰近的其它單元102 (例如，單元102a和單元102b)中的存在區域115。
[0034] 當行動裝置110連接到接入點105a時，行動裝置110可以檢測可用的其它接入點 1〇5(例如，接入點105b)。行動裝置110可以識別可用的接入點的存在區域（例如，存在區 域115a和115b)。行動裝置110可以使用各種算法計算行動裝置110的當前位置。例如， 當僅識別出一個存在區域115a時，行動裝置110可以將存在區域115a指定為行動裝置110 的當前位置。當識別出兩個或更多個存在區域115時，行動裝置110可以使用迭代過程（例 如，多遍分析）來計算其當前位置。該迭代過程可以計算這些存在區域的平均位置，計算這 些存在區域與該平均位置之間的距離，並且排除與該平均位置相距最遠的存在區域。移動 設備110可以重複該迭代，直到滿足用於確定行動裝置110的位置的精度要求。行動裝置 110可以將該平均位置指定為行動裝置110的當前位置，並且在地圖顯示設備上顯示該平 均位置。
[0035] 在某些實現中，在行動裝置110上從系統接收的位置更新可以包括許多鄰近單 元，從而可以覆蓋圍繞存在區域115a的足夠大的區域（例如，1或2平方公裡）。基於覆蓋 該大區域的位置更新，行動裝置110可以避免在行動裝置110移動時必須請求頻繁的更新。 當例如行動裝置110空閒或具有可用通信帶寬時，行動裝置110可以有機會接收更新的存 在區域信息。
[0036] 圖1B示出了管理三維空間中的位置資料庫。某些知道位置的行動裝置108(例如， 能夠使用GPS的設備）可以在三維空間中標識位置。這些位置可以以緯度、經度和高度表 示。高度可被表示為例如從海平面以米測量的海拔。當需要行動裝置的高度來定位該移動 設備時，可能希望在三維空間中定位行動裝置。例如，可以使用高度來確定行動裝置處於高 層建築中的哪一層。行動裝置108在三維空間中的位置可被顯示在將海拔作為注釋的二維 地圖上，或被顯示在三維地圖上。
[0037] 行動裝置108可以連接到接入點126。行動裝置108可以是可將其位置傳輸給系 統的知道位置的行動裝置，所述位置包括緯度、經度和高度坐標。該系統可以基於從移動設 備108接收的緯度、經度和高度坐標來計算平均位置。以平均位置為中心並且以誤差幅度 為半徑的三維空間124可與接入點126相關聯。空間124可以表示當行動裝置位於接入點 126的通信範圍內時，該行動裝置可能位於的空間。在本說明書中，空間124被稱為存在空 間。
[0038] 系統向位於接入點126通信範圍內的行動裝置發送關於存在空間124的信息。接 收到該信息的行動裝置可以利用該信息來確定其地理位置。系統可以將三維地理空間劃分 為三維網格120。三維網格120可以由三維單元122組成。每個三維單元122可以具有與 地理網格100的單元102相對應的基底。每個三維單元122可以具有作為一個維度的高度 (例如，以米衡量）。如果存在空間124的中心在單元122中，則存在空間124可被稱為位於 單元122中。系統可以基於存在空間的流行度（例如，形成了多少從存在空間中的移動設 備108到接入點126的連接）、存在空間124的穩定性（例如，存在空間124有多麼穩定）、 接入點126的壽命（例如，接入點126已經存在了多久）、和存在空間124的新鮮度（例如， 來自位於接入點126通信範圍內的行動裝置108的最新位置傳輸是何時接收到的），來限制 單元122中的存在空間的數目。
[0039] 系統可以基於三維網格120的三維單元122將關於存在空間124和鄰近存在空間 的信息傳輸給位於接入點126通信範圍內的行動裝置（例如，行動裝置110)。行動裝置110 可以利用該信息估計行動裝置110在三維空間中的當前位置，並且在三維地圖上顯示所估 計的當前位置。
[0040] 示例性的用於管理位置資料庫的伺服器端處理和系統
[0041] 圖2A - 2C示出了管理位置資料庫的示例性階段。為了方便起見，將藉助於包括 實現這些技術的伺服器的基於網絡的定位系統來描述這些技術。
[0042] 圖2A示出了可用於確定與接入點105相關聯的存在區域的多遍分析的示例性階 段。接入點105可以具有覆蓋區域202,該覆蓋區域202可以由接入點105的發射器的信號 強度和其它因素（例如，接入點105周圍的地理區域的物理特性）來確定。位於覆蓋區域 202內的行動裝置108可以無線地連接到接入點105。接入點105可以允許行動裝置108 通過各種網關連接到有線網絡。有線網絡可以包括數據網絡（例如，Internet)、公共交換 電話網絡（PSTN)、其它數字或模擬網絡、或以上的組合。
[0043] 行動裝置108可以包括知道位置的行動裝置（例如，能夠使用GPS的行動裝置）。 每個知道位置的行動裝置108 (以圖2A的黑三角表示）可以檢測其當前地理位置。該當前 地理位置可以用包括行動裝置108的緯度和經度的地理坐標來表示。當行動裝置108與接 入點105通信時，行動裝置108可以通過接入點105將位置信息傳輸給系統。該位置信息 可以與接入點105的標識符（例如，接入點105的媒體訪問控制（MAC)地址）相關聯。系 統可以利用從多個行動裝置108接收的位置信息來確定可以與接入點105相關聯的存在區 域。該存在區域不一定圍住了接入點100實際位於的位置。該存在區域也不一定與覆蓋區 域202的幾何位置或形狀相對應，儘管存在區域可以位於覆蓋區域202內。
[0044] 具有覆蓋區域202的行動裝置108的分布可以對應於行動裝置108在特定時刻 (例如，接入點105所位於的時區的本地時間上午8:30)的快照（snapshot)。每個移動設 備108可以與單個位置相關聯。具有覆蓋區域202的行動裝置108的分布也可以對應於移 動設備108在一段時間（例如，從上午4點到上午10點的6個小時）上的位置。每個移動 設備108可以與多個位置相關聯（例如，當行動裝置108移動時）。與多個位置相關聯的單 個行動裝置108可以由系統中的多個位置表示，如圖2A中的多個三角形所示的。
[0045] 伺服器可以確定從行動裝置108接收的一組位置的平均地理位置。這一組位置可 以包括在特定時刻或在特定時間段期間從行動裝置108接收的位置。平均地理位置可被指 定作為圓204a所包圍的區域的中心205。圓204a的中心不必與接入點105的位置一致。 伺服器可以計算平均地理位置與這一組位置中的每個位置之間的距離，並且識別一個或多 個離群點（outlier)。離群點可以是這一組位置中與平均地理位置相距最遠的位置。到中 心的距離超過某個閾值的離群點（例如，位置210)可以從該組位置中被排除。圓204a可 以具有半徑206,半徑206對應於平均地理位置與排除離群點之後的當前一組位置中的位 置之間的最長距離。
[0046] 圖2B示出了多遍分析中在圖2A的階段之後的示例性階段。到圖2A的平均地理 位置（圓204a的中心205)的距離超過某個閾值的位置已從該組位置中被排除。所述閾值 可被配置為使得排除某個百分比的位置（例如，圖2A的位置中的5% )。可以基於該組位 置中剩下的位置（例如，剩下的95%的位置）來計算新的平均地理位置。新的平均地理位 置可以是例如圓204b的中心225。在各種實現中，計算新的平均地理位置可以包括對該組 位置中的剩餘位置進行平均，選擇該組位置中的中間地理位置（例如，通過選擇中間緯度 或中間經度），或應用其它算法。用於計算平均地理位置的算法在多遍分析的每一遍中可以 是相同的，或可以在每遍中彼此不同。
[0047] 當排除了離群點位置時，由圓204b包含的區域可以小於在前一遍中確定的由圓 204a包含的區域。該較小的區域可以反映增加的計算精度。圓204b的中心225不一定與 圓204a的中心205 -致。在某些實現中，圓204b的半徑216可以對應於與圓204b的中心 225相距最遠的行動裝置108的剩餘位置。半徑216可以表示在當前這一遍中計算的存在 區域的新的估計的誤差幅度。
[0048] 圖2C示出了多遍分析的示例性的最終階段。當滿足一定的退出條件時，系統可以 在最終階段之後終止迭代過程。最終階段可以產生與一群聚集的行動裝置108的位置相對 應的最終平均地理位置。最終平均地理位置可被表示為圓204c的中心235。圓204c可以 具有與最終誤差幅度相對應的半徑，該半徑基於最終平均地理位置與這一群聚集的位置中 的位置之間的距離。通過接入點105的標識符（例如，MAC地址），圓204c可被指定為與接 入點105相關聯的存在區域。
[0049] 伺服器可以基於各種因素確定是否要在位置資料庫中包括接入點105的標識符 和相關聯的存在區域。例如，伺服器可以對地理網格100的單元102中的存在區域的數目 進行計數，並且基於流行度、穩定性和壽命來選擇若干存在區域。伺服器可以將位置資料庫 中的存在區域（包括存在區域204c，如果選擇了存在區域204c的話）的信息發送給移動設 備（例如，行動裝置215)，不論行動裝置215是否能夠使用GPS。
[0050] 圖2D示出了管理三維空間中的位置資料庫的示例性階段。在圖2D中，軸X、Y和Z 可用於指示三維空間。例如，軸Χ、Υ和Ζ可以分別表示經度、緯度和高度。為了方便，接入 點126的位置被示出為與圖2D中的Χ、Υ和Ζ軸上的零點重合。在某些實現中，接入點126 的實際位置（例如，緯度、經度和高度坐標）在計算中是可選的。
[0051] 圖2D的每個三角可以表示位於三維空間中的行動裝置的位置。這些位置可以在 三維空間的一個平面上具有投影（例如，投影226)。該平面可被定義在任意高度（例如， 接入點126的高度）。例如，可由軸X和Υ定義該平面。接入點126可以對應於覆蓋區域 222,覆蓋區域222可以由接入點126的信號強度和其它限制因素（例如，信號路徑中的地 板、天花板、建築）來確定。
[0052] -種多遍分析可以基於從位於單元空間202中的知道位置的行動裝置108接收的 一組位置，將地理空間與WLAN的接入點126相關聯。在該多遍分析的一遍中，可以通過例如 對該組位置中的位置的緯度、經度和高度坐標進行平均來確定平均地理位置（例如，空間 224的中心）。可以計算平均地理位置與覆蓋區域222中的位置之間的距離。位於覆蓋區 域222內但是與平均地理位置相距足夠遠的位置可從該組位置和進一步計算中被排除。空 間224的半徑可以由例如該組位置中的剩餘位置與平均地理位置之間的最遠距離來確定。
[0053] 系統可以重複以下階段：計算一組位置中的平均地理位置、計算該平均地理位置 與該組位置中的位置之間的距離、以及基於計算的距離從這組位置中進行排除。可以繼續 該重複，直到滿足退出條件為止。以平均地理位置為中心、其半徑基於平均地理位置與該組 位置中剩餘位置之間的距離的空間可被指定為可以與接入點126相關聯的存在空間。
[0054] 圖3A是示出了管理位置資料庫的示例性處理300的流程圖。可以使用處理300， 以便例如確定與WLAN的接入點相關聯的存在區域或存在空間。存在區域或存在空間可用 於確定不能使用GPS的行動裝置的位置。為了方便，將藉助於執行處理300的系統來描述 處理300。
[0055] 系統可以從位於接入點105通信範圍內的一個或多個第一行動裝置108接收 (302) -組位置。每個位置可以由一組地理坐標（例如，緯度、經度和高度）表示。該位置 可被與接入點105的標識符（例如，MAC地址）相關聯。當接入點105與系統通信時，接入 點105可自動提供接入點的標識符。在各種實現中，這一組位置可以對應於一個時間段（例 如,6個小時,或者從接入點105所位於的時區的上午6點到上午10點）。
[0056] 在某些實現中，該時間段可被配置為反映一天中各個時間的特定使用模式的特 性。位於接入點105通信範圍內的行動裝置最可能位於的區域可以在一天當中改變，從而 指示在特定時間的各種使用模式。例如，該時間段可以對應於"路上時間"、"工作時間"、"夜 晚時間"，等等。一天中的時間的特性可以對應於行動裝置108的各種使用模式。例如，在路 上時間期間，與接入點105相關聯的存在區域可以處於或接近高速公路；在工作時間期間， 與接入點105相關聯的存在區域可以處於或接近辦公大樓；在夜晚時間，與接入點105相關 聯的存在區域可以散開而沒有特定的集中點。系統可以基於例如從上午4點到上午10點 接收到的位置計算存在區域，並且基於從上午10點到下午4點接收到的位置重新計算，等 等。在每個特徵時間段中接收到的位置可以集合成系統中的一組位置。這些位置可以任何 數據結構（例如，集合、列表、關係型資料庫中的數據記錄等）存儲在耦接到伺服器的存儲 設備上。
[0057] 系統可以基於接收到的位置的平均值來確定（304)與接入點105相關聯的地理位 置。該地理位置可以包括上述的存在區域或存在空間。存在區域或存在空間可以通過例如 接入點105的MAC地址與接入點105相關聯。在某些實現中，確定地理位置可以包括對接 收到的一組位置應用多遍算法，包括每一遍從該組位置中排除至少一個位置。確定地理位 置可以包括周期性地應用多遍算法。
[0058] 系統可以基於各種因素，包括接入點105的流行度、地理位置的穩定性和接入點 105的壽命，將接入點105和與接入點105相關聯的地理位置分配（306)給地理網格上的 一個單元（例如，單元102)。在某些實現中，接入點105的流行度可以衡量有多少移動設 備108位於接入點105的通信範圍內。可以通過例如系統在一段時間內接收到位於接入點 105通信範圍內的多少行動裝置108位置，來測量接入點的流行度。
[0059] 與接入點105相關聯的存在區域的穩定性可以反映，如果該存在區域被用於估計 位於接入點105通信範圍內的設備的位置，那麼該存在區域的可靠性如何。可以通過例如 比較由最後兩次計算計算出的存在區域，並且確定這些存在區域之間的重疊程度，來測量 與接入點105相關聯的存在區域的穩定性。重疊程度越高，存在區域越穩定。
[0060] 接入點105的壽命可以反映與接入點105相關聯的數據的質量。例如，在資料庫 中存在了更長時間的接入點可能比最近添加的接入點更可靠。可以通過位置資料庫中的數 據的歷史來測量接入點105的壽命。
[0061] 在某些實現中，還可以使用數據的新鮮度來確定是否將與接入點105相關聯的存 在區域分配給地理網格100的單元102。可以通過系統在多久以前從行動裝置108接收到 最新位置，來測量數據的新鮮度。
[0062] 系統可以基於流行度、穩定性、壽命和新鮮度，為位於地理網格100的單元102中 的每個存在區域評分。位於單元102中的所有存在區域的至少一部分（例如，三個存在區 域，包括與接入點105相關聯的存在區域）可被分配給單元102。被分配的接入點和存在區 域可用於定位位於接入點105通信範圍內的行動裝置（例如，行動裝置110)。未被分配的 存在區域可被存儲在位置資料庫中以供將來使用。
[0063] 系統可以將與接入點105相關聯的地理位置提供（308)給位於接入點105通信範 圍內的第二行動裝置（例如，行動裝置110)。系統還可以向第二行動裝置提供位於相同單 元中的其它地理位置，以及與分配給鄰近單元的接入點相關聯的地理位置。這些位置可以 根據請求或使用各種推送或廣播技術從接入點105被傳輸給第二行動裝置。
[0064] 在某些實現中，系統可以接收、處理和傳輸三維位置信息。存在空間（例如，存在 空間124)可被分配給地理三維網格（例如，三維網格120)上的三維單元（例如，三維單元 122)。這些位置可以根據請求或使用各種推送或廣播技術，從接入點126被傳輸給位於接 入點126通信範圍內的第二行動裝置。
[0065] 圖3B是示出了利用一組位置計算平均地理位置的示例性處理304的流程圖。為 了方便，將藉助於執行處理304的系統來描述處理304。
[0066] 系統可以利用這一組位置中的位置計算（324)平均地理位置。計算平均地理位置 可以包括計算該組中的位置的緯度、經度和高度的平均，並且將位於所計算的平均緯度、經 度和高度的位置指定為平均地理位置。在某些實現中，計算平均地理位置可以包括將位於 該組中的位置的中間緯度、中間經度和中間高度處的位置指定為平均地理位置。
[0067] 系統可以計算（326)這一組位置中的位置與平均地理位置之間的距離。在某些實 現中，系統可以在歐幾裡得空間中計算該組中每個位置與平均地理位置之間的線性距離。 在某些實現中，系統可以考慮地球的曲率，計算該組中每個位置與平均地理位置之間的測 地距離。
[0068] 在階段326中計算出的距離可被指定為與一個中心相關聯的半徑。該中心可以是 在階段324中計算出的平均地理位置，其可以是圓（例如，圓204a)的中心。可以基於該組 位置中的一個位置與平均地理位置之間的至少一個距離確定圓的半徑。在某些實現中，該 半徑可以等於平均地理位置和該組中剩餘的位置之間的最長距離。在某些實現中，該半徑 可以是這樣的距離：當使用該半徑並以該平均地理位置為中心畫圓l〇6d時，該圓可以包含 該組中一定百分比（例如，80%)的剩餘位置。該半徑可以表示誤差幅度，超出該誤差幅度， 對不能使用GPS的行動裝置的位置估計不太可能在統計上有意義。
[0069] 系統可以基於平均地理位置和至少一個位置之間的距離從該組中排除（328)該 至少一個位置。在某些實現中，系統可以排除到平均地理位置的距離超過某個閾值距離的 位置。在多遍分析的每一遍中，通過排除表現為遠離位置集群（例如，一群聚集的位置）的 位置，系統可以增加所估計的平均地理位置的精度。遠離一群聚集位置的位置在估計與接 入點105相關聯的存在區域時不太有用，並且可被排除。在各種實現中，閾值距離可以從一 遍到下一遍改變。在某些實現中，閾值距離可以是到平均地理位置的這樣一個距離，其中這 一組位置中某個百分比（例如，95%)的位置位於該距離以內。在某些實現中，閾值距離可 以是與遍相對應的一組距離（例如，第一遍250米，第二遍150米，等等）。當平均地理位置 和至少一個位置之間的距離超出該閾值距離時，系統可以從這一組位置中排除該至少一個 位置。
[0070] 系統可以重複處理304的階段324、326和328,直到滿足退出條件為止。系統可以 確定（330)是否滿足退出條件以便終止重複。在某些實現中，當重複次數達到某個閾值次 數（例如，10次）時，退出條件被滿足。該閾值次數以及用於排除位置的百分比可以是可配 置的，以便精細調節在確定度（例如，較大的存在區域可以得到單元中的行動裝置實際上 位於該存在區域中的更大置信度）和精度（例如，較小的存在區域可以得到行動裝置的更 準確位置）之間的平衡。例如，當百分比被設置為95%並且遍數被設置為10時，最後一遍 可以產生包含所有位置數據點的大約60%的圓。
[0071] 在某些實現中，當存在區域或存在空間足夠小時，階段330的退出條件可被滿足。 在行動裝置高度集中的單元中，存在區域可能足夠小，以至於更多的遍將不一定會增加精 度。當圓的半徑達到低於閾值半徑時，階段324、326和328的重複可以終止。例如，閾值半 徑可以是8 - 10米。基於接收到的一組位置中的位置的分布模式（例如，接收到的位置數 據點的數目、位置數據點的密度、以及單元中的集中區域），閾值半徑可以隨著接入點的不 同而不同。
[0072] 系統可以將地理區域指定（332)為以平均地理位置為中心、其半徑基於至少一個 計算出的距離的圓。該地理區域可以與接入點（例如，接入點105)相關聯。伺服器可以將 該地理區域（例如，中心和半徑）提供給行動裝置，以便計算該行動裝置的當前位置。中心 可以用緯度和經度表示。在某些在三維空間中計算距離的實現中，中心可以進一步用高度 表不。
[0073] 圖3C是示出了實施管理位置資料庫的技術的示例性系統的框圖。該系統可以包 括一個或多個處理器、一個或多個存儲指令的存儲器設備、和其它硬體或軟體組件。該系統 可以包括位置引擎350,其可被用於確定將與接入點（例如，接入點105)相關聯的存在區域 或存在空間。
[0074] 位置引擎350可以包括數據收集模塊352,其可以通過各個接入點從各個移動設 備接收數據。該數據可以包括多個數據點，這些數據點可以指示一個或多個知道位置的移 動設備（例如，行動裝置108)的位置，以及表明行動裝置108連接到哪個接入點的接入點 標識符（例如，接入點105的MAC地址）。在某些實現中，數據點還可以包括關於行動裝置 108所在時區的信息。數據收集模塊352可以包括數據接收模塊354和數據索引模塊356， 數據接收模塊354可以接收從行動裝置108傳輸的數據。數據索引模塊356可以對接收到 的數據點執行各種處理。例如，數據索引模塊356可以基於單元ID對緯度、經度和高度排 序。數據索引模塊356還可以基於時間段將數據分組。例如，可以為一個可配置的時間段 (例如，6小時）創建新的一組接收位置。
[0075] 各組接收到的行動裝置108的位置可被存儲在數據點資料庫360中。數據點數據 庫360可以存儲各個行動裝置108的當前和歷史位置。數據點資料庫360可以包括ad-hoc 資料庫、關係資料庫、面向對象資料庫。數據點資料庫360可相對於位置引擎350在本地或 遠程託管。
[0076] 可以利用位置計算模塊364計算數據點資料庫中的各組數據點中的平均地理位 置，計算平均地理位置和各個數據點的位置之間的距離，以及為進一步的計算從組中排除 位置。位置計算模塊364可以為特定組（例如，與一個單元ID相關聯的一組數據點）執行 計算，直到達到該特定組的退出條件為止。位置計算模塊364可以為每個接入點（例如，接 入點105)確定存在區域或存在空間。
[0077] 在某些實現中，位置計算模塊364可以使用有效性檢查器366,基於各種準則和數 據點中的各種數據，對存在區域或存在空間執行有效性檢查。例如，從行動裝置108接收的 數據點可以包括移動國家代碼（MCC)和時區信息。有效性檢查器366可以將計算的存在區 域或存在空間與對應於以MCC表示的國家的多邊形和對應於時區的多邊形進行比較。如 果計算的存在區域或存在空間位於這些多邊形之外，則有效性檢查器366可以記錄一個異 常，並且去除該接入點。
[0078] 位置過濾引擎368可以確定存在區域或存在空間是否可被用於估計當前位於接 入點通信範圍內的行動裝置的位置。位置過濾引擎368可以將地理區域劃分為地理網格 100的單元102或三維網格120的三維單元122。位置過濾引擎368可以基於流行度、穩 定性、壽命和新鮮度，給存在區域或存在空間評分。位置過濾引擎368可以將位於每個單元 102或三維單元122中得分最高的存在區域或存在空間分配給單元102或三維單元。
[0079] 存在區域或存在空間可以由具有一組位置的平均緯度、經度和高度坐標的中心來 定義。存在區域或存在空間還可以由基於這一組位置中的位置到該中心的距離所確定的半 徑來定義。存在區域或存在空間的中心的緯度、經度和高度坐標以及存在區域或存在空間 的半徑可被存儲在位置資料庫372中。位置資料庫372可以存儲已分配和未分配的存在區 域和存在空間。位置計算模塊364可以在後續計算中分配未分配的存在區域或存在空間。 位置資料庫372可由位置計算模塊364周期性地更新。
[0080] 位置資料庫372的數據可利用數據分發模塊376被分發到行動裝置。數據分發模 塊376可以根據請求、通過廣播、或使用無需從行動裝置接收請求的各種推送技術，將已分 配的與接入點相關聯的存在區域和存在空間的信息（例如，中心坐標和半徑）發送給移動 設備（例如，不能使用GPS的行動裝置110)。
[0081] 在某些實現中，數據分發模塊376可以在一個傳輸會話中向行動裝置發送多個存 在區域和存在空間。為了減少可能消耗行動裝置通信帶寬的到行動裝置的位置傳輸的數 目，數據分發模塊376可以使用鄰居定位器378來定位行動裝置110所處單元的鄰居。鄰 近單元可以包括，例如，圍繞行動裝置110所處單元的若干單元，從而該單元和周圍單元的 總區域覆蓋一定地理區域（例如，1或2平方公裡）。向行動裝置110發送關於與多個單元 (例如，400個單元）相關聯的存在區域和存在空間的信息可以減少當行動裝置110跨單元 移動時的傳輸數目。在某些實現中，當行動裝置110移動到以前發送過的所有單元之外時， 數據分發模塊376僅需要向行動裝置110發送更新。
[0082] 利用無線接入點的位置確定行動裝置的位置的示例性處理
[0083] 圖4A示出了用於利用無線接入點的位置確定行動裝置的位置的技術。行動裝置 400可以是可以利用無線接入點的位置來確定其位置的示例性行動裝置。示出了包括接入 點404的通信網絡的示例性部分。
[0084] 行動裝置400可以位於接入點404a的通信範圍內。行動裝置400可以從接入點 404a接收包括關於鄰近接入點的存在區域或存在空間（包括存在區域406)的信息的數據。 行動裝置400可以將接收到的數據存儲在存儲設備上。存儲的數據可周期性地更新。
[0085] 在不出的例子中，行動裝置400位於接入點404a的通信範圍內。此外，行動裝置 400在接入點404b、404c和404d的通信範圍內。行動裝置400可以在WLAN中使用的無線通 信協議（例如，IEEE802. 11a)下識別接入點404a、404b、404c和404d。接入點404a、404b、 404c和404d可以由接入點的MAC地址或其它標識符（例如，Bluetooth?標識符）來標識。
[0086] 行動裝置400可以識別分別與接入點404a - d相關聯的存在區域406a、406b、 406c和406d。識別存在區域406a - d可以包括從耦接到行動裝置400的存儲器設備中檢 索關於存在區域406a - d的信息。在某些實現中，行動裝置400可以通過向伺服器發送接 入點404a - d的標識符，從伺服器請求存在區域406a - d。
[0087] 基於存在區域406a - d，行動裝置400可以對存在區域406a - d執行迭代過程 (例如，多遍分析）。該迭代過程可以產生地理區域402,其可以是對行動裝置400的當前地 理位置的估計。當使用三維位置信息時，地理區域402可以是地理空間。行動裝置400可 以在顯示設備上（例如，在地圖顯示器上）顯示估計的當前位置。
[0088] 圖4B是示出了使用位置資料庫確定行動裝置的位置的示例性處理410的流程圖。 為了方便，將藉助於執行處理410的行動裝置400來描述處理410。
[0089] 行動裝置400可以識別（412)行動裝置400與之連接的當前接入點。行動裝置 400可以使用當前接入點來確定是否要請求位於行動裝置400上的位置資料庫的更新。位 於行動裝置400上的位置資料庫可以包括以前下載到行動裝置400的接入點的記錄。位於 行動裝置400上的位置資料庫中的記錄可以包括接入點的標識符（例如，MAC地址）和相 對應的位置（例如，緯度/經度坐標）。
[0090] 在階段412,行動裝置400可以確定當前接入點是否被包括在位置資料庫的記錄 中。行動裝置可以使用行動裝置400與之連接的當前接入點的標識符（例如，MAC地址）執 行位置資料庫查找。如果當前接入點被包括在位置資料庫的記錄中，則行動裝置可以確定 位置資料庫是最新的。如果當前接入點未被包括在位置資料庫的記錄中，則行動裝置400 可以確定位置資料庫需要更新。
[0091] 行動裝置400可以使用當前接入點的標識符從伺服器請求（414)行動裝置400的 位置資料庫的更新。位置資料庫中的記錄，包括接入點的標識符和位置，可利用新接入點的 新標識符和位置被刷新。行動裝置400可將當前接入點的標識符發送到伺服器。伺服器可 以將某個單位識別為地理網格中的中心單元。中心單元可以是這樣的單元，其包括與當前 接入點的標識符相關聯的位置，並且將該單元和鄰近單元中的所有接入點位置發送給移動 設備400。
[0092] 行動裝置400可以接收（416)與第二接入點相關聯的一組第二位置。第二接入點 可以分布在中心單元和在地理網格上與該中心單元鄰近的單元中。與當前接入點相關聯的 位置（例如，圓區域的中心）可以位於中心單元中。鄰近單元可以是在地理網格上位於中心 單元旁邊或與中心單元最近的單元。鄰近單元的數目可以具有這樣的值，即，使得中心單元 和鄰近單元可以覆蓋預定的地理區域（例如，1. 5平方公裡）。當與接入點相關聯的位置處 於由中心單元和鄰近單元覆蓋的地理區域內時，這些接入點的標識符和與這些接入點相關 聯的位置可被包括在更新中。在當前接入點未被包括在位置資料庫的記錄中時更新移動設 備400上的位置的一個示例性優點是，當行動裝置400在單元之間移動時不需要更新，直到 行動裝置400移動到一個與單個接入點的覆蓋區域相比的大區域之外為止。因此，可以避 免頻繁更新，為行動裝置400和伺服器兩者節省了資源（例如，對行動裝置而言，節省了帶 寬、CPU周期、電池電能；對伺服器而言，當大量行動裝置從一個街區移動到下一個街區時， 伺服器不需要向這些設備發送頻繁的更新）。
[0093] 行動裝置400可以使用接收到的一組接入點位置和標識符來更新（418)位於移動 設備400上的位置資料庫。更新可以將行動裝置400 "定位"在由中心單元和鄰近單元覆 蓋的地理區域的"中心"。行動裝置400可以不需要請求另一個更新，直到行動裝置400從 該中心單元移動到未被鄰近單元之一覆蓋的單元。例如，如果每個單元大約為50米乘50 米，並且該預定地理區域是1. 5平方公裡，則每次更新可以將大約600個單元注入行動裝置 400的位置資料庫中。行動裝置400不需要請求另一個更新，除非行動裝置移動到該600個 單元覆蓋的區域之外。
[0094] 行動裝置400可以使用位於行動裝置400上的位置資料庫來計算（420)行動裝置 400的當前位置。可以使用由行動裝置400執行的自適應多遍處理執行該計算。下面將參 考圖4C描述多遍處理的進一步細節。雖然其它因素（例如，來自各個接入點的信號強度） 可以幫助對當前位置的計算，但是在該計算中不需要這些因素。
[0095] 行動裝置400可以可選地在行動裝置400的地圖顯示設備上顯示（422)行動裝置 400的當前位置。在下文會參考圖5更詳細地描述當前位置的示例性顯示。
[0096] 圖4C是示出了確定行動裝置的位置的示例性自適應多遍處理430的流程圖。為 了方便，將藉助於執行處理430的行動裝置400來描述處理430。
[0097] 行動裝置400可以接收（432)無線通信網絡（例如，WLAN)的接入點（例如接入 點404)的標識符。這些接入點可以位於行動裝置400的通信範圍內。所述標識符不必與 行動裝置400與之連接或可以連接的接入點相關聯。例如，在特定位置，行動裝置400可以 處於3到20個接入點之間的通信範圍內。行動裝置400可能僅僅能夠連接到兩個接入點 (由於例如接入點和行動裝置400的安全設置）。行動裝置400可能僅僅有效地連接到這 兩個接入點中的一個接入點。然而，在計算中可以使用行動裝置400接收到的所有接入點 標識符。
[0098] 行動裝置400可以從行動裝置400的位置資料庫中識別（433)與這些接入點相關 聯的一組位置。該組位置可以對應於與接入點相關聯的存在區域406或存在空間。每個位 置可以由地理坐標（例如，緯度、經度和高度）表示。每個位置可以與一個接入點404的標 識符（例如，MAC地址）相關聯。行動裝置400可以使用資料庫查找來識別這些位置。
[0099] 行動裝置400可以使用該組中的位置來計算（434)平均地理位置。計算平均地理 位置可以包括計算該組中的位置的緯度、經度和高度的平均值，並且將位於計算出的平均 緯度、經度和高度處的位置指定為平均地理位置。在某些實現中，計算平均地理位置可以包 括將該組中的位置的中間緯度、中間經度和中間高度指定為平均地理位置。
[0100] 行動裝置400可以計算（436)該組中的位置與平均地理位置之間的距離。在某些 實現中，系統可以在歐幾裡得空間中計算該組中的每個位置與平均地理位置之間的線性距 離。在某些實現中，系統可以考慮地球的曲率，計算該組中的每個位置與平均地理位置之間 的測地距離。
[0101] 在階段436中計算出的距離可被指定為與一個中心相關聯的半徑。該中心可以是 在階段434中計算出的平均地理位置，其可以是圓（例如，圍繞地理區域402的圓）的中心。 可以基於該組位置中的一個位置與平均地理位置之間的至少一個距離確定圓的半徑。在某 些實現中，該半徑可以等於平均地理位置和該組中剩餘的位置之間的最長距離。在某些實 現中，該半徑可以是這樣的距離：當使用該半徑並以該平均地理位置為中心畫圓時，該圓可 以包含該組中一定百分比（例如，80%)的剩餘位置。該半徑可以表示誤差幅度，超出該誤 差幅度，對不能使用GPS的行動裝置的位置估計不太可能在統計上有意義。
[0102] 行動裝置400可以基於平均地理位置和至少一個位置之間的距離從該組中排除 (438)該至少一個位置。在某些實現中，系統可以排除到平均地理位置的距離超過某個閾值 距離的位置。在多遍分析的每一遍中，通過排除表現為遠離位置集群（例如，一群聚集的位 置）的位置，系統可以增加所估計的平均地理位置的精度。遠離一群聚集位置的位置在估 計行動裝置400的當前位置時不太有用，並且可被排除。在各種實現中，閾值距離可以從一 遍到下一遍改變。例如，閾值距離可以是與遍相對應的一組距離（例如，第一遍50米，第二 遍30米，等等）。當平均地理位置和至少一個位置之間的距離超過該閾值距離時，系統可以 從這一組位置中排除該至少一個位置。
[0103] 在某些實現中，行動裝置400可以確定將被排除的位置的閾值百分比。該閾值百 分比可以具有預先指定的值（例如，5%)。在每一遍中，行動裝置400可以排除閾值百分比 的與平均地理位置相距最遠的位置。
[0104] 行動裝置400可以重複處理430的階段434、436和438,直到滿足退出條件為止。 系統可以確定（440)是否滿足退出條件以便終止重複。在某些實現中，當重複次數達到某 個閾值次數（例如5次）時，退出條件被滿足。該閾值次數可以與原始接收的組中的位置數 目有關。該閾值數目以及排除位置的百分比可以是可配置的，以便精細調節在確定度（例 如，較大的存在區域可以得到單元中的行動裝置實際上位於該存在區域中的更大置信度） 和精度（例如，較小的存在區域可以得到行動裝置的更準確位置）之間的平衡。例如，當百 分比被設置為95%並且遍數被設置為10時，最後一遍可以產生包含所有位置數據點的大 約60%的圓。
[0105] 在某些實現中，當存在區域或存在空間足夠小時，階段330的退出條件可被滿足。 在接入點404高度集中的區域中，估計的當前位置可能包括足夠小的區域，以至於更多的 遍將不一定會增加精度。當圓的半徑達到低於閾值半徑時，階段434、436和438的重複可 以終止。例如，閾值半徑可以是8 - 10米。該閾值半徑可以基於存在區域406的半徑。在 某些實現中，如果某些存在區域406的半徑足夠小，則閾值半徑可以很小，以便反映估計的 置信度。
[0106] 行動裝置400可以利用以平均地理位置為中心、其半徑基於至少一個計算出的距 離的圓，來指定（442)行動裝置400的當前位置。該中心可以用緯度和經度表示。在某些 在三維空間中計算距離的實現中，中心可以進一步用高度表示。在某些實現中，行動裝置還 可以在顯示設備上在地圖用戶界面上顯示當前位置。下面將參考圖5描述示例性的地圖用 戶界面。
[0107] 用於確定行動裝置的位置的示例性用戶界面
[0108] 圖5示出了用於利用無線接入點的位置確定行動裝置的位置的示例性用戶界面。 在圖5中，在行動裝置500上顯示地理區域的示例地圖502。在某些實現中，行動裝置500 可以在行動裝置500的觸敏顯示器530上顯示地圖502。當用戶選擇地圖對象以便觀看基 於地圖和位置的服務時，可以顯示地圖502。在某些實現中，可以通過語音激活來選擇諸如 地圖對象之類的對象。可以在地圖502的頂部顯示搜索欄504和書籤列表對象506。可以 在地圖底部下面顯示一個或多個顯示對象，例如，搜索對象508、路線對象510、地圖觀看對 象512和當前位置對象514。
[0109] 搜索欄504可用於在地圖上尋找地址或其它位置。例如，用戶可以在搜索欄504 中輸入其家庭地址，從而包含該地址的區域將顯示在地圖502上。書籤列表對象506可以 例如給出包含頻繁訪問的地址（諸如，用戶的家庭地址）的書籤列表。書籤列表還可以例 如包含特別的書籤，諸如當前位置（例如，行動裝置500的當前位置）。
[0110] 搜索對象508可用於顯示搜索欄504和其它與地圖有關的搜索菜單。路線對象510 可以例如給出允許用戶輸入開始和結束位置的菜單界面。然後該界面可以顯示信息（例 如，從開始位置到結束位置的路線的方向和行進時間）。地圖觀看對象512可以給出允許用 戶選擇地圖502的顯示選項的菜單。例如，可以將地圖502從黑白變成彩色，可以改變地圖 的背景，或用戶可以改變地圖的亮度。
[0111] 當前位置對象514可以允許用戶在地圖502上觀看表明設備500當前處於何處的 地理區域516。地理區域516可以對應於估計的地理區域（例如，地理區域402)，該估計的 地理區域的中心是與處於行動裝置500通信範圍內的接入點相關聯的數據點的平均地理 位置。可以基於該平均地理位置和與這些接入點相關聯的一個或多個位置之間的距離確定 地理區域516的半徑。當選擇當前位置對象514時，特別的當前位置書籤可被置於書籤列 表中。如果該特別的當前位置書籤以前已被設置在書籤列表中，則該舊的書籤信息可以例 如被新的當前位置信息所取代。在某些實現中，該特別的當前位置書籤被綁定到地理區域 516的形心。即，該特別的當前位置書籤可以包括地理區域516的形心的坐標。地理區域 516可以基於利用存儲在行動裝置500的存儲器設備中的位置指令而確定或估計的位置數 據。地理區域516可以例如由具有十字準線的圓、矩形、正方形、六邊形或其它封閉區域，或 者由某些其它區別元素來示出，以便區分地理區域516和地圖502。
[0112] 在某些實現中，地理區域516可以指示行動裝置500被確定或被估計位於其中的 區域，並且該地理區域可以不一定以行動裝置500的實際當前位置為中心。在這個例子中， 行動裝置500可以處於該地理區域內偏離中心的位置。在另一個例子中，地理區域516可 以以行動裝置500的估計的當前位置為中心。
[0113] 當輕擊或選擇當前位置對象514時，行動裝置500可以使地圖視圖以地理區域516 為中心。在某些實現中，可以基於位置數據或提供位置數據的技術、系統或服務的準確度或 精度，調整地圖的縮放級別。例如，當行動裝置500不能接收GPS信號時，可以由於較低的 準確度而縮小地圖，並且使用接入點數據確定其位置。如果行動裝置500能夠使用GPS位 置數據確定其當前位置，則可以由於較高的準確度而放大地圖。在某些實現中，縮放級別可 以基於行動裝置500的速度（例如，可以在較高速度時縮小地圖，在行動裝置500不移動時 放大地圖）。還可以使用準確度或精度與速度的組合。
[0114] 如果用於檢索基於位置的數據的所有方法都失敗了（例如，當行動裝置500不在 任何接入點的通信範圍內時，或者當有效性檢查器366確定沒有存在區域能夠與行動裝置 500可連接的任何接入點相關聯時），並且沒有其它系統或服務可用於確定或估計移動設 備500的當前位置，則可以向用戶顯示一個錯誤，並且不在地圖502上顯示地理區域。該錯 誤可以例如包含將失敗和可能的一個或多個失敗原因通知給用戶的消息。
[0115] 可以選擇當前位置對象514以便例如激活地圖502上的地理區域516的估計和顯 示，從而獲得去往或始於估計的當前位置（即，地理區域516的形心）的路線，將行動裝置 500的估計的當前位置發送給朋友（例如，使得該朋友可以到該相同位置），或者為估計的 當前位置創建書籤。
[0116] 示例性系統體系結構
[0117] 圖6是用於實現參考圖1 一 5所描述的特徵和操作的示例性系統體系結構600的 框圖。其它體系結構也是可能的，包括具有更多或更少組件的體系結構。在某些實現中，體 繫結構600包括一個或多個處理器602 (例如，雙核心]ntel? Xeon?處理器）、一個或多 個輸出設備604(例如，LCD)、一個或多個網絡接口 606、一個或多個輸入設備608(例如，鼠 標、鍵盤、觸敏顯示器）、和一個或多個計算機可讀介質612(例如，狀11、1?01、50狀1、硬碟、光 盤、快閃記憶體等）。這些組件可以通過一個或多個通信通道610(例如，總線）交換通信和數據， 通信通道610可以使用各種硬體和軟體，以幫助實現組件之間的數據和控制信號的傳輸。
[0118] 術語"計算機可讀介質"指參與向處理器602提供用於執行的指令的任何介質，包 括但不限於，非易失介質（例如，光碟或磁碟）、易失介質（例如，存儲器）和傳輸介質。傳 輸介質包括但不限於同軸電纜、銅線和光纖。
[0119] 如參考圖1 一 5所述，計算機可讀介質612還可以包括作業系統614(例如， Mac OS? server, WilldOWS? NT server)、網絡通信模塊 616、資料庫接口 620、數據收 集模塊630、數據分發模塊640和位置計算模塊650。作業系統614可以是多用戶的、多處 理的、多任務的、多線程的、實時的，等等。作業系統614執行基本任務，包括但不限於：識別 來自設備606、608的輸入以及向設備606、608提供輸出；在計算機可讀介質612(例如，存 儲器或存儲設備）上記錄和管理文件和目錄；控制外圍設備；以及管理一個或多個通信通 道610上的業務。網絡通信模塊616包括用於建立和保持網絡連接的各種組件（例如，用 於實現諸如TCP/IP、HTTP等通信協議的軟體）。資料庫接口 620可以包括到文件系統上的 一個或多個資料庫（例如，數據點資料庫360和位置資料庫372)的接口。可以按照分層文 件夾結構來組織資料庫，所述文件夾映射到文件系統中的目錄。數據收集模塊630可以包 括用於從通過接入點或通過其它通信通道（例如，蜂窩網絡）無線連接到系統600的多個 行動裝置收集數據的組件。數據分發模塊640可以執行用於向計算設備傳輸與無線通信網 絡的接入點相關聯的位置數據的各種功能，所述計算設備包括行動裝置108和110。位置計 算模塊650可以包括用於對從行動裝置108接收的位置執行多遍分析的一個或多個組件。
[0120] 體系結構600可被包括在能夠持有（host)資料庫應用程式的任何設備中。可以以 並行處理或對等基礎結構或者在具有一個或多個處理器的單個設備上實現體系結構600。 軟體可以包括多個軟體組件，或者可以是單段代碼。
[0121] 描述的特徵可被有利地以可在可編程系統上執行的一個或多個電腦程式實現， 所述可編程系統包括至少一個可編程處理器、至少一個輸入設備和至少一個輸出設備，所 述可編程處理器被耦接為從數據存儲系統接收數據和指令，並且向數據存儲系統傳輸數據 和指令。電腦程式是可以在計算機中直接或間接使用以便執行某個活動或帶來某個結果 的指令集。電腦程式可被以任何形式的程式語言編寫（例如，〇b jective-C、Java)，包括 編譯或解釋語言，並且可被以任何形式部署，包括作為獨立程序或作為模塊、組件、子例程、 基於瀏覽器的網絡應用、或適合於在計算環境中使用的其它單元。
[0122] 舉例而言，用於執行指令程序的適當處理器包括通用和專用微處理器兩者，以及 任何類型計算機的單個處理器或者多個處理器或核之一。一般地，處理器將從只讀存儲器 或隨機訪問存儲器或這兩者接收指令和數據。計算機的基本元件是用於執行指令的處理 器和用於存儲指令和數據的一個或多個存儲器。一般地，計算機還將包括用於存儲數據文 件的一個或多個大容量存儲設備，或計算機可操作地被耦接以與其通信；這些設備包括磁 盤，諸如內部硬碟和可移動盤；磁光碟；和光碟。適用於有形地包含電腦程式指令和數據 的存儲設備包括所有形式的非易失存儲器，作為例子，包括半導體存儲器設備，諸如EPROM、 EEPR0M和快閃記憶體設備；磁碟，諸如內部硬碟和可移動盤；磁光碟；以及CD-ROM和DVD-ROM盤。 處理器和存儲器可被輔以ASIC (專用集成電路）或被結合在ASIC中。
[0123] 為了提供與用戶的交互，這些特徵可被實現在具有用於向用戶顯示信息的顯示設 備（諸如，CRT(陰極射線管）或LCD(液晶顯示器）監視器）和用戶可以藉以向計算機提 供輸入的鍵盤和指點設備（諸如，滑鼠或軌跡球）的計算機上。
[0124] 這些特徵可被實現在包括後端組件（諸如數據伺服器），或包括中間件組件（諸 如應用伺服器或Internet伺服器），或包括前端組件（諸如具有圖形用戶界面或Internet 瀏覽器的客戶計算機），或它們的任何組合的計算機系統中。系統的組件可以由數字數據通 信的任何形式或介質（諸如，通信網絡）來連接。通信網絡的例子包括，例如，LAN、WAN、和 形成Internet的計算機和網絡。
[0125] 該計算機系統可以包括客戶端和伺服器。客戶端和伺服器一般彼此遠離，並且通 常通過網絡交互。通過在各自計算機上運行並且彼此具有客戶端一伺服器關係的計算機程 序，產生了客戶端和伺服器的關係。
[0126] 示例性行動裝置體系結構
[0127] 圖7是行動裝置的示例性體系結構700的框圖。行動裝置可以例如是手持計算 機、個人數字助理、蜂窩電話、電子輸入板、網絡設備、照相機、智慧型電話、增強式通用分組無 線業務（EGPRS)行動電話、網絡基站、媒體播放器、導航設備、電子郵件設備、遊戲控制臺、 或這些數據處理設備或其它數據處理設備中的任意兩個或更多個的組合。
[0128] 行動裝置可以包括存儲器接口 702、一個或多個數據處理器、圖像處理器和/或中 央處理單元704、以及外圍設備接口 706。存儲器接口 702、一個或多個處理器704和/或外 圍設備接口 706可以是分離的組件，或可被集成在一個或多個集成電路中。行動裝置100 中的各種組件可由一個或多個通信總線或信號線耦接。
[0129] 傳感器、設備和子系統可被耦接到外圍設備接口 706,以幫助實現多個功能。例如， 運動傳感器710、光傳感器712和接近（proximity)傳感器714可稱接到外圍設備接口 706， 以幫助實現行動裝置的定向、光照和接近功能。位置處理器715(例如，GPS接收器）可連 接到外圍設備接口 706,以便提供地理定位。電子磁力計716 (例如，一個集成電路晶片）也 可連接到外圍設備接口 706,以便提供可用於確定磁北極方向的數據。
[0130] 照相機子系統720和光學傳感器722,例如，電荷耦合器件（CXD)或互補金屬氧化 物半導體（CMOS)光學傳感器，可用於幫助實現照相機功能，諸如，記錄照片和視頻剪輯。
[0131] 可以通過一個或多個無線通信子系統724來幫助實現通信功能，無線通信子系統 724可以包括射頻接收器和發射器和/或光學（例如，紅外線）接收器和發射器。通信子 系統724的具體設計和實現可取決於行動裝置要在其上操作的一個或多個通信網絡。例 如，行動裝置可以包括被設計為在GSM網絡、GPRS網絡、EDGE網絡、Wi-Fi或WiMax網絡、和 Bluetooth網絡上操作的通信子系統724。特別地，無線通信子系統724可以包括託管協議 (hosting protocol)，從而設備可被配置作為其它無線設備的基站。
[0132] 音頻子系統726可耦接到揚聲器728和麥克風730,以幫助實現能夠使用語音的功 能，諸如語音識別、語音複製、數字記錄、以及電話功能。
[0133] 1/0子系統740可以包括觸控螢幕控制器742和/或其它輸入控制器（一個或多 個）744。觸控螢幕控制器742可耦接到觸控螢幕746或觸摸板。觸控螢幕746和觸控螢幕控制器 742可以例如使用多種觸敏技術中的任何一種來檢測接觸和移動或其中斷，所述觸敏技術 包括但不限於電容、電阻、紅外線和表面聲波技術，以及用於確定與觸控螢幕746的一個或多 個接觸點的其它接近傳感器陣列或其它元件。
[0134] 其它輸入控制器（一個或多個）744可耦接到其它輸入/控制設備748,諸如一個 或多個按鈕、撥動開關、拇指輪、紅外線埠、USB埠、和/或諸如觸筆之類的指針設備。一 個或多個按鈕（未不出）可以包括用於揚聲器728和/或麥克風730的音量控制的上/下 按鈕。
[0135] 在一種實現中，將按鈕按壓第一持續時間可以解除觸控螢幕746的鎖定；將按鈕按 壓比第一持續時間長的第二持續時間可以接通或關閉行動裝置的電源。用戶可以定製一個 或多個按鈕的功能。觸控螢幕746還可以例如用於實現虛擬或軟按鈕和/或鍵盤。
[0136] 在某些實現中，行動裝置可以呈現記錄的音頻和/或視頻文件，諸如，MP3、AAC和 MPEG文件。在某些實現中，行動裝置可以包括MP3播放器（諸如iPod?)的功能。因此移 動設備可以包括與iPod兼容的針連接器。還可以使用其它輸入/輸出和控制設備。
[0137] 存儲器接口 702可耦接到存儲器750。存儲器750可以包括高速隨機訪問存儲器和 /或非易失存儲器，諸如一個或多個磁碟存儲設備、一個或多個光學存儲設備、和/或快閃記憶體 (例如，NAND、N0R)。存儲器750可以存儲作業系統752,諸如，Darwin、RTXC、LINUX、UNIX、 0S X、WINDOWS或嵌入式作業系統，諸如VxWorks。作業系統752可以包括用於處理基本系 統服務和用於執行硬體相關任務的指令。在某些實現中，作業系統752可以包括內核（例 如，UNIX內核）。
[0138] 存儲器750還可以存儲通信指令754,以幫助實現與一個或多個附加設備、一個 或多個計算機和/或一個或多個伺服器的通信。存儲器750可以包括：圖形用戶界面指令 756,以幫助實現圖形用戶界面處理；傳感器處理指令758,以幫助實現與傳感器有關的處 理和功能；電話指令760,以幫助實現與電話有關的處理和功能；電子消息收發指令762,以 幫助實現與電子消息收發有關的處理和功能；網絡瀏覽指令764,以幫助實現與網絡瀏覽 有關的處理和功能；媒體處理指令766,以幫助實現與媒體處理有關的處理和功能；GPS/導 航指令768,以幫助實現與GPS和導航有關的處理和功能；照相機指令770,以幫助實現與照 相機有關的處理和功能；磁力計數據772和校準指令774,以幫助實現磁力計校準。存儲器 750可以包括位置指令776,其可用於向接入點傳輸當前位置，以及基於與行動裝置處於其 通信範圍內的接入點相關聯的位置數據，確定估計的當前位置。存儲器750還可以存儲其 它軟體指令（未示出），諸如，安全指令；網絡視頻指令，以幫助實現與網絡視頻有關的處理 和功能；和/或網絡購物指令，以幫助實現與網絡購物有關的處理和功能。在某些實現中， 媒體處理指令766被劃分為音頻處理指令和視頻處理指令，以分別幫助實現與音頻處理有 關的處理和功能和與視頻處理有關的處理和功能。激活記錄和國際行動裝置標識（IMEI) 或類似的硬體標識符也可被存儲在存儲器750中。
[0139] 上面列出的指令和應用中的每一個可以對應於用於執行上述一個或多個功能的 一個指令集。這些指令不一定被實現為單獨的軟體程序、過程或模塊。存儲器750可以包 括附加的指令或更少的指令。另外，行動裝置的各種功能可以硬體和/或軟體實現，包括以 一個或多個信號處理和/或專用集成電路來實現。
[0140] 已經描述了本發明的若干實現。然而，應當理解，可以做出各種修改，而不脫離本 發明的精神和範圍。例如，知道位置的設備被稱為能夠使用GPS。知道位置的行動裝置也可 以基於三角測量或其它技術。單元被在圖中表示為大體是矩形形狀。單元的實際形狀可以 改變。位置被描述為"圓"。本說明書中使用的術語"圓"可以包括不一定是完美的圓、但是 是閉合的或具有封閉外觀的任何幾何形狀（例如，橢圓、正方形、凸或凹多邊形、或自由形 狀）。不是完美圓形的幾何形狀的半徑可以包括在該幾何形狀邊界上的各個點與幾何形狀 中心之間的平均距離。使用WiFi和WiMax網絡作為例子。也可以使用其它無線技術（例 如，蜂窩網絡）。因此，其它實現處於所附權利要求的範圍中。
【權利要求】
1. 一種由計算機實現的方法，包括： 從均位於無線通信網絡的一接入點的通信範圍內的多個第一行動裝置接收多組位置， 每組位置對應於一個不同的接入點； 基於接收到的對應於每個接入點的一組位置的平均值，確定與該接入點相關聯的地理 位置； 將與每個接入點相關聯的地理位置分配給地理網格上的單元； 對於所述地理網格上的每個單元，基於接收到的對應接入點的一組位置中的位置的數 目，對分配給該單元的各地理位置進行評分，其中，與數目較多的一組位置相關聯的接入點 所對應的地理位置得到較高的評分； 過濾分配給每個單元的各地理位置，包括保留該單元的具有最高評分的地理位置；和 將與所述接入點相關聯的地理位置和分配給在所述地理網格上與所述單元鄰近的單 元的接入點的地理位置提供給連接到所述接入點的第二行動裝置。
【文檔編號】G06F17/30GK104125638SQ201410245016
【公開日】2014年10月29日 申請日期:2010年8月25日 優先權日:2010年1月15日
【發明者】R·K·黃, M·菲斯徹, S·普拉潘 申請人:蘋果公司