使用壓縮指紋檔案的設備上定位的方法和設備的製作方法

2023-06-01 21:33:26

專利名稱：使用壓縮指紋檔案的設備上定位的方法和設備的製作方法
技術領域：
本發明的實施例一般涉及計算技術，並且更特別地，涉及用於位置發現的方法和設備。
背景技術：
很多類型的計算和/或通信設備能夠在設備從一個地方移動到另一地方的同時提供各種各樣的功能。此處通常將這些設備稱為「行動裝置」。出於各種原因，行動裝置能夠確定其當前位置可能是有利的。例如，一些行動裝置執行應用，例如日曆、提醒、導航助手以及具有可以取決於行動裝置的位置而被改變或增強的功能性的通信工具。多數室外定位系統使用全球定位系統(GPS)，其通過三角測量到一組衛星的距離來計算設備的位置。GPS基礎設施包括衛星集群以及地面跟蹤站，並且取決於公布的衛星星曆表(ephemeride)的更新。為了確定其位置,行動裝置可以包括具有用於接收GPS衛星傳輸的無線電以及估算其地理基準(geo-referenced)諱度、經度以及海拔(LLE)的足夠的計算和存儲資源的GPS接收機。在地圖背景中可以更容易地觀看行動裝置的LLE。因為GPS僅在具有大的天空能見度的室外區域中運行良好，所以期望具有對於典型地與GPS不兼容的環境的替代方案。

發明內容
因此，提供了一種使用壓縮的指紋檔案的設備上定位的方法、設備和電腦程式產品。通常，除了別的外，本發明的示例實施例還通過提供一種壓縮用於例如在行動裝置上存儲的定位(localization)指紋的方法來提供改進。還提供了用於基於射頻指紋模型的高效設備上定位的方法以及一種用於估算兩個或更多個設備之間的物理距離的方法。在此使用的「指紋」也可以被稱為「籤名」。在本發明的一個實施例中，提供了一種方法，包括接收與在空間中觀測的接入點對應的空間到接入點柱狀圖。歸一化所述柱狀圖，並且從所述柱狀圖計算均值和標準偏差。向所述接入點分配權重，其中，所述權重與所述接入點在所述空間內被觀測的頻率對應。組合所述均值、所述標準偏差和所述權重以形成表示所述空間內觀測的所述接入點的數據三元組。可以對於所述空間內觀測的每個接入點重複前述方法，從而在所述空間中觀測的多個接入點每個都由數據三元組表示。空間的多個數據三元組形成該空間的指紋。可以從所述指紋中移除具有最低分配的權重的數據三元組或多個數據三元組。可以從所述指紋中移除低於閾值權重的數據三元組。根據本發明的另一實施例，提供了一種裝置，其包括至少一個處理器和包括電腦程式代碼的至少一個存儲器。所述至少一個存儲器和所述電腦程式代碼被配置為通過所述至少一個處理器使所述裝置接收與空間中觀測的接入點對應的空間到接入點柱狀圖。歸一化所述空間到接入點柱狀圖，並且計算均值和標準偏差。可以向所述接入點分配權重，所述權重與所述接入點在所述空間內被觀測的頻率對應。可以對在相同空間中各自生成的多個空間到接入點柱狀圖計算均值、標準偏差和權重。組合每一個均值、標準偏差和權重以形成每一個所述空間中觀測到的接入點的數據三元組。所述多個數據三元組組合以形成指紋。可以從所述指紋移中除具有最低分配的權重的數據三元組或多個數據三元組。可以從所述指紋中移除低於閾值權重的數據三元組。根據本發明的又一實施例，提供了一種電腦程式產品，其包括具有在其中存儲的計算機可執行程序代碼指令的至少一個計算機可讀存儲介質。該實施例的計算機可執行程序代碼指令包括用於接收與空間中觀測到的接入點對應的空間到接入點柱狀圖的程序代碼指令以及用於歸一化所述空間到接入點柱狀圖的計算機代碼指令。也可以包括用於計算所述柱狀圖的均值和標準偏差的程序代碼指令以及向所述接入點分配權重的程序代碼指令，其中，所述權重與所述接入點在所述空間內被觀測的頻率對應。所述電腦程式代碼 指令可以被配置為計算多個空間到接入點柱狀圖的均值、標準偏差和權重。組合特定接入點的均值、標準偏差和權重以形成表示所述空間中觀測到的接入點的數據三元組。所述多個數據三元組組合以形成指紋。可以從所述指紋中移除與所述最低分配的權重對應的數據三元組或多個數據三元組。可以從所述指紋中移除低於閾值權重的數據三元組。


已經因此概括地描述了本發明的實施例，現在將參考不必按比例繪製的附圖，其中圖I是圖示了行動裝置和多個信號源的建築的一部分的示意性平面圖；圖2是根據本發明的一個實施例的行動裝置的框圖；圖3是用於支持本發明的實施例的系統的圖解表示；圖4是根據本發明的一個實施例執行的操作的流程圖；圖5是四個不同空間的每一個中的無線指紋的圖解表示；圖6是根據本發明的示例實施例的一些示例信號強度與加權高斯方法的概率繪圖比較的圖示；圖7是根據本發明的示例實施例的加權高斯方法的示例仿真的結果的繪圖；圖8是根據本發明的示例實施例的加權高斯方法的示例仿真的結果的繪圖；圖9是根據一個實施例的用於設置一個或多個虛擬消息以及用於檢索一個或多個基於虛擬位置的消息的過程的流程圖；圖10是根據一個實施例的圖示了室內覆蓋/通知區域的建築的一部分的示意圖；圖11是可以用於實現本發明的實施例的晶片集的示意圖；圖12A-12C是根據各個實施例的圖9的過程中使用的用戶接口的示意圖；以及圖13A和圖13B是根據各個實施例的圖9的過程中使用的對話框的示意圖。
具體實施例方式現在將在下文中參照附圖更全面地描述本發明的一些實施例，其中示出了本發明的一些而不是所有實施例。實際上，本發明的各種實施例可以體現為很多不同形式，並且不應解釋為受限於在此闡述的實施例；而是，提供這些實施例以使得本公開將滿足可應用的法律要求。相同的參考標記通篇指代相同的部件。在此處使用時，術語「數據」、「內容」、「信息」和相似術語可以可互換地使用，以指代能夠根據本發明實施例被發射、接收和/或存儲的數據。此外，在此使用的術語「示例性」並非被提供為傳達任何質量評估，而是僅傳達示例的說明。因此，任何這種術語的使用不應被認為限制本發明的實施例的精神和範圍。此外，在此處使用時，術語「電路」指代(a)僅硬體電路實現(例如在模擬電路和/或數字電路中的實現)；(b)電路和電腦程式產品的組合，電腦程式產品包括一起運行以使裝置執行在此描述的一個或多個功能的存儲在一個或多個計算機可讀存儲器上的軟體和/或固件指令；以及(C)諸如像微處理器或微處理器的一部分的電路，其需要軟體或固件以進行操作，即使軟體或固件物理上不存在。「電路」的該定義應用於該術語在此處的所有使用，包括任何權利要求中的使用。作為進一步的示例，在此處使用時，術語「電路」還包 括包含一個或多個處理器和/或其部分以及伴隨的軟體和/或固件的實現。作為另一示例，在此使用的術語「電路」還包括例如用於行動電話的基帶集成電路或應用處理器集成電路或伺服器、蜂窩網絡設備、其它網絡設備和/或其它計算設備中的類似的集成電路。圖I描述了建築的一部分的平面圖。如圖所示，建築被牆壁、門、窗等劃分為多個空間。例如，其可以是辦公室區域、住宅區域、購物區域等的一部分。根據本發明的實施例，建築內的行動裝置10可以有利地確定其位置，諸如關於行動裝置當前位於的房間的位置。如下所述，行動裝置可以識別出現在其當前地理位置處的無線指紋，並且可以基於該無線指紋和其與預定地理位置的關聯確定當前位置為無線指紋已經事先與其關聯的預定地理位置。通過示例的方式，圖I描述了三個無線信號源12，例如無線區域網等的接入點，其發出無線信號，無線信號組合以定義行動裝置在房間235中檢測的無線指紋。可以通過表徵無線電信號(例如802. 11和蜂窩廣播)中可用的空間變化的基於指紋的定位並且將該信息編譯到虛擬地圖中而在室內環境中執行定位。然後每個行動裝置可以通過識別地圖內其指紋最接近地匹配設備最近觀測到的任何指紋的空間來估算其位置。因為無線電地圖可能由於多徑效應而在室內經歷大誤差，因此基於指紋的定位可以比無線電地圖更可取。除了確定行動裝置10檢測的無線指紋是否已經事先與預定的地理位置關聯之夕卜，本發明的實施例還可以允許例如經由到行動裝置的用戶輸入對當前位置的識別，以及隨後的對行動裝置檢測的無線指紋與標識的位置的關聯，由此允許從其進行隨後的比較的資料庫的填充(population)。通過基於先前觀測的無線指紋提供對當前位置的自動確定以及對當前位置的用戶識別，本發明的實施例的方法、裝置和電腦程式產品可以有利地結合位置發現技術的調查和使用方面，從而同時支持位置發現技術的使用和從其進行隨後的比較的資料庫的進一步的填充。雖然可以通過各種方式配置行動裝置10，但圖2的框圖中描述了可以受益於本發明的實施例的行動裝置的一個示例。雖然為了示例的目的將圖示並且在下文中描述行動裝置的一個實施例，但其它類型的行動裝置(例如可攜式數字助理(PDA)、尋呼機、移動電視、遊戲設備、所有類型的計算機(例如膝上型或移動計算機)、相機、音頻/視頻播放器、收音機或上述任何組合以及其它類型的行動裝置)可以採用本發明的實施例。如所描述的，行動裝置可以包括用於執行根據本發明的實施例的一個或多個功能的各種裝置，包括在此更具體地示出和描述的。然而，應理解的是，在不脫離本發明的精神和範圍的情況下，行動裝置可以包括用於執行一個或多個類似功能的替代裝置。
圖示的實施例的行動裝置10包括與發射機24和接收機26可操作的通信的天線22 (或多個天線)。行動裝置可以進一步包括分別將信號提供給發射機和接收機並且從發射機和接收機接收信號的裝置(例如處理器30 )。信號可以包括根據可應用的蜂窩系統的空中接口標準的信令信息，和/或還可以包括與用戶語音對應的數據、接收的數據和/或用戶生成的數據。在這點上，行動裝置可能能夠以一個或多個空中接口標準、通信協議、調製類型和接入類型進行操作。舉例說明，行動裝置可能能夠根據多個第一、第二、第三和/或第四代通信協議等中的任一個進行操作。例如，行動裝置可能能夠根據第二代(2G)無線通信協議IS-136、全球移動通信系統(GSM)和IS-95、或諸如通用移動通信系統(UMTS)、碼分多址2000 (CDMA2000)、寬帶CDMA (WCDMA)和時分同步碼分多址(TD-SCDMA))的第三代(3G)無線通信協議、諸如E-UTRAN (演進的UMTS地面無線接入網)的3. 9G無線通信協議、第四代(4G)無線通信協議等進行操作。應理解的是，諸如處理器30的裝置可以包括，除了別的外，實現行動裝置10的音頻和邏輯功能的電路。處理器可以體現在多種不同的方式中。例如，處理器可以體現為各種處理裝置，諸如處理電路、協處理器、控制器或包括集成電路(諸如像專用集成電路(ASIC)、現場可編程門陣列(FPGA)、硬體加速器等)的各種其它處理設備。在示例實施例中，處理器被配置為執行存儲在存儲器設備中或處理器可以其它方式獲取的指令。這樣，無論通過硬體或軟體方法還是其組合而配置，在被相應地具體配置後，處理器30可以表示能夠執行根據本發明的實施例的操作的實體，包括圖4中描述的。處理器還可以包括在調製和傳輸之前對消息和數據進行卷積編碼和交織的功能性。行動裝置10還可以包括可以耦合到處理器30的用戶接口以及用戶輸入接口，用戶接口包括輸出設備，諸如耳機或揚聲器34、振鈴器32、擴音器36、顯示器38。允許行動裝置接收數據的用戶輸入接口可以包括允許行動裝置接收數據的多種設備中的任一種，諸如鍵區40、觸摸顯示器(未示出)或其它輸入設備。在包括鍵區的實施例中，鍵區可以包括數字的(0-9)和有關的鍵(#、*)和用於操作移動終端的其它硬和軟鍵。可選地，鍵區可以包括傳統的QWERTY鍵區布置。鍵區還可以包括具有關聯功能的各種軟鍵。此外，或可選地，行動裝置可以包括諸如操縱杆或其它用戶輸入接口的接口設備。行動裝置可以進一步包括電池44 (諸如振蕩電池組)以向用於操作行動裝置的各種電路供電，並且可選地提供機械振動作為可檢測的輸出。行動裝置10可以進一步包括用戶身份模塊(UTM) 48，其通常可以被稱為智慧卡。UM可以是具有內置處理器的存儲器設備。UM可以包括例如訂戶身份模塊(SM)、通用集成電路卡(UICC)、通用訂戶身份模塊(USM)、可移除用戶身份模塊(R-UM)或任何其它智慧卡。UIM可以存儲與移動訂戶有關的信息要素。除了 UIM之外，行動裝置可以配備有存儲器。例如，行動裝置可以包括易失性存儲器50，諸如包括用於臨時存儲數據的緩存區域的易失性隨機存取存儲器(RAM)。行動裝置還可以包括其它非易失性存儲器52，其可以是內嵌的和/或可以是可移除的。非易失性存儲器可以附加地或可選地包括電可擦編程只讀存儲器(EEPROM)、快閃記憶體等。存儲器可以存儲行動裝置用於實現行動裝置的功能的任何多個信息和數據。例如，存儲器可以包括能夠唯一地標識行動裝置的標識符，諸如國際移動裝備識別(MEI)碼。例如，行動裝置10可以被配置為經由網絡14與網絡實體16 (例如圖3的系統100所示的伺服器)通信。網絡可以是被配置為支持各種行動裝置與各種網絡實體之間的通信的任何類型的有線和/或無線網絡。例如，網絡可以包括各種不同節點、設備或功能的集合，例如伺服器，並且可以經由對應的有線和/或無線接口而彼此通信。雖然並非必要，但在一些實施例中，網絡可能能夠支持根據多個第一代(1G)、第二代(2G)、2. 5G、第三代(3G)、3. 5G、3. 9G、第四代(4G)級別通信協議、長期演進(LTE)等中的任一種的通信。如下將描述的，伺服器16可以包括或關聯於多個行動裝置10經由網絡14可以訪問的資料庫。該資料庫可以保存與它們各自的預定地理位置關聯的多個預定無線指紋(例 如(在此作為示例使用的)先前觀測的無線指紋)。基於對資料庫內的信息的至少一個子集的分析，行動裝置可以通過比較當前無線指紋和與預定地理位置關聯的先前觀測的無線指紋來識別其當前位置。在一個實施例中，資料庫可由多個行動裝置共同存取。在另一實施例中，資料庫是半專用的，其中資料庫僅可由行動裝置的子集(例如特定公司的僱員的行動裝置)而不是其它行動裝置存取。在又一實施例中，資料庫可以是專用的，其中，行動裝置僅能夠存取各個行動裝置已經貢獻的無線指紋。如圖3所示，根據本發明的實施例圖示了能夠操作為伺服器等的網絡實體16的框圖。網絡實體可以包括用於執行根據本發明實施例的一個或多個功能的各種裝置，包括在此更特別地示出和描述的那些裝置。然而，應理解的是，在不脫離本發明的精神和範圍的情況下，網絡實體可以包括用於執行一個或多個類似功能的替代裝置。在圖示的實施例中，網絡實體16包括用於執行或控制其各種功能的裝置，諸如處 理器60。可以通過多個不同方式實施處理器。例如，處理器可以體現為各種處理裝置，諸如處理電路、協處理器、控制器或包括集成電路(諸如像ASIC、FPGA、硬體加速器等)的各種其它處理裝置。在示例實施例中，處理器被配置為執行存儲在存儲器中的或處理器以其它方式可獲取的指令。這樣，無論通過硬體或軟體方法還是其組合而配置，在被相應地具體配置後，處理器60可以表示能夠執行根據本發明的實施例的操作的實體。在一個實施例中，處理器60與存儲器62 (諸如存儲內容、數據等的易失性和/或非易失性存儲器)通信或包括存儲器62。例如，存儲器可以存儲從網絡實體發射和/或由網絡實體接收的內容。又例如，存儲器可以存儲處理器用於執行與根據本發明的實施例的網絡實體16的操作關聯的操作的軟體應用、指令等。具體地說，存儲器可以存儲處理器用於執行以上和以下關於圖4描述的操作的軟體應用(例如位置應用107c)、指令等。在一個實施例中，存儲器存儲與它們各自的預定地理位置關聯的先前觀測的無線指紋的資料庫。在另一實施例中，位置應用107c和或網絡實體16的其它軟體應用可以根據在此描述的方法至少部分地基於無線指紋而實施或執行功能。通過示例的方式，功能(如下更詳細地描述的)可以包括但不限於(I)基於物理接近性的設備配對；(2)執行「鄰域搜索」；和/或(3)提供基於位置的消息傳送(messaging)，包括廣告。在一些實施例中，位置應用107c可以連同執行行動裝置10或相反駐留在行動裝置10上的位置客戶機應用107a —起操作。例如，位置客戶機應用107a可以執行關於位置應用107c描述的功能的所有或部分。除了存儲器62之外，處理器60還可以連接到用於發射和/或接收數據、內容等的至少一個接口或其它裝置。在這點上，接口可以包括用於(諸如在網絡實體16與行動裝置10之間和/或在網絡實體與網絡14的其餘部分之間)發射和/或接收數據、內容等的至少一個通信接口 64或其它裝置。根據示例實施例，為了確定其位置，行動裝置10可以識別出現在其當前地理位置處的無線信號。為了識別無線指紋，行動裝置可以掃描無線信號，諸如具有預定頻率或在預定的頻率範圍內的無線信號。在一個實施例中，例如，處理器30指引接收機26捕獲進入的無線信號，接收機自身被配置為接收具有預定頻率或在預定的頻率範圍內的信號。在無線區域網的接入點12已經貫穿建築部署從而無線指紋將由接入點發出的無線信號組成的一個實施例中，行動裝置可以被配置為檢測在接入點的操作頻率處在行動裝置處入射的無線信號。可選地，在採用在其它頻率處發出無線信號的其它類型的源的實施例中，行動裝置可以類似地被配置為檢測在感興趣的其它頻率處的無線信號。
行動裝置10識別的無線指紋可以包括接收的信號強度或從與每個接入點的地址(例如媒體訪問控制(MAC)地址)關聯的每個接入點接收的無線信號的其它信號參數。參照圖5的實施例，例如，四個信號源12 (諸如四個接入點)貫穿建築的一部分而安置。該實施例的每個接入點具有唯一地址，諸如0xa3b、0x6d2、0xbc4和0x5fe。因為關於距離以及關於其間的結構(intervening structure,諸如牆壁、門、窗等)而言，每個房間或空間處於關於信號源12的不同位置，所以行動裝置10在每個空間內接收的無線指紋通常不同，例如圖5所示。通過將特定的無線指紋與具體空間關聯，可以通過將行動裝置接收的當前無線指紋和與空間關聯的特定的無線指紋進行比較來識別行動裝置當前所位於的空間。第一空間或區域334具有與0xa3b、0x5fe、0xbc4和0x6d2的信號強度對應的指紋，0xa3b、0x5fe、0xbc4和0x6d2是圖示的空間中可用的四個信號的標識符，為了便於參考也可標識為(A)、(B)、(C)和(D)。每個信號具有由對應的水平條表示的不同強度。每個空間333、335和337也具有它們自己的指紋，其帶有與可用的四個信號對應的四個信號強度。由於信號D的強度在該特定空間中可忽略，因此區域337示出了信號強度A、B和C。可以通過創建和填充(populate)信號強度映射並且產生每個空間的指紋的初始實地調查來生成現有無線指紋的資料庫。特定空間的指紋可以基於接入點的重新配置、重新定位或替換而隨著時間改變，從該接入點測量用於指紋的信號。此外，通過使用有機用戶輸入可以改動或修改指紋，以隨著時間而擴充資料庫。例如，已知在特定空間中的用戶可以將用戶設備(例如圖3，標號10)在該空間處觀測的指紋發射到伺服器(例如16)，從而所觀測的指紋可以替換或擴充伺服器上的資料庫中存儲的指紋。在本發明的示例實施例中，可以使用到每個接入點(AP)的加權高斯距離或WGD來創建無線指紋。由於加權高斯距離對於計算和提供常規的掃描距離函數相對簡單，因此無線指紋受益於WGD的使用。由於定位算法可以在行動裝置的背景中連續地運行，因此WGD計算的簡單性可以轉變為較長的電池壽命。掃描距離函數對於聚類掃描可能是有用的。反過來，聚類可以用於異常值檢測以及清理掃描資料庫。距離函數也可能對於估算進行掃描的位置之間的物理距離有用，如以下進一步討論的那樣。因此，在識別出現在特定地理位置處的無線指紋之後，行動裝置10並且更具體地，一個實施例的處理器30確定當前無線指紋是否和與預定地理位置關聯的先前觀測的無線指紋對應，如果是，則確定預定地理位置為當前位置。這樣，行動裝置識別的當前無線指紋可以與(例如資料庫中保存的)多個先前觀測的無線指紋比較，以確定必要的一致性(correspondence)是否存在。雖然根據伺服器確定當前無線指紋是否與網絡實體保存的或可以其它方式獲取的資料庫中存儲的任何先前觀測的無線指紋對應的請求，行動裝置可以將當前無線指紋的表示發射到網絡實體16，但這種對於網絡實體的依賴性可能不期望地引入等待時間。因此，在一個實施例中，行動裝置將與各個預定地理位置關聯的多個先前觀測的無線指紋存儲在本地存儲器(例如易失性存儲器50)中。以此方式，用戶設備可以下載與建築、樓層或用戶設備所處的地理區域有關的指紋檔案或資料庫，從而如果用戶設備與網絡失去聯繫(即脫機)，則指紋資料庫在用戶設備上仍然可用，以用於確定用戶的位置。行動裝置10可以通過各種方式獲得多個先前觀測的無線指紋。在一個實施例中，網絡實體16在例如存儲器62中保存用於各個預定地理位置的先前觀測的無線指紋的資料庫，供多個行動裝置使用。因此，行動裝置可以與網絡實體通信，以從將先前觀測的無線指紋與各個預定地理位置配對的資料庫獲得數據的潛在關聯子集。可以通過各種方式來定義 數據的潛在關聯子集，諸如除了別的外還包括建築、地理區域或建築樓層內的所有已知位置的子集。行動裝置可以通過下載與用戶可能拜訪的位置對應的已知指紋的檔案來限制與網絡的通信。可選地，行動裝置可以僅偶爾與網絡進行通信，諸如當進入或離開特定區域時，或當在行動裝置上存儲的檔案內未發現觀測的指紋時。這些實施例可以減少網絡通信，這可以導致改進的網絡容量和/或行動裝置的更長的電池壽命。實施例還可以通過僅在用戶設備上保存位置信息而不是將位置發射到伺服器來增加用戶隱私。其中無線指紋表示與每個信號源關聯的信號強度的方式可以考慮無線指紋基於各種參數而稍微變化的可能性。在這點上，雖然可以通過各種方式來表示空間內可見的每個信號源發射的信號的信號強度，但信號強度在一個實施例中由其接收的信號強度指示(RSSI)表示，儘管可以可選地採用其它測量，諸如信噪比(SNR)。可以對RSSI值進行歸一化或縮放(scaled)，從而位於預定範圍(諸如O至100)內。對於每個空間以及對於空間內可見的每個信號源，一個實施例的處理器30從具有各個RSSI的各個信號源構建空間內接收的信號的數量(即計數)的柱狀圖。在本發明的示例實施例中，通過WGD定位生成的無線指紋可以比生成無線指紋的現有方法更容易地被計算，並且它們可能需要明顯更少的存儲空間，從而存儲與各個預定地理位置關聯的先前觀測的無線指紋的資料庫可能在具有有限的存儲器容量的設備(例如行動裝置10)上更有效。為了生成WGD無線指紋，可以使用空間到接入點柱狀圖，如在基本無線指紋中使用的；然而，這些柱狀圖中的每一個可以概括為單個高斯。被歸一化時，可以通過均值μ和標準偏差σ來概括每個柱狀圖。這可以將對柱狀圖的域(典型地O-IOOdBm)乘以柱狀圖的最大高度的存儲和網絡傳輸要求減少至兩個浮點數。因此，環境中的每個空間可以被分配無線指紋，其可以是從接入點(AP)到數據三元組的映射的集合APi => (WilPf5Oi)其中，Wi是APi的權重，可觀測的AP的數量是τ，每個指紋的總權重是=1
O
用戶的最新k個(所執行的掃描數量)掃描也可以使用相同方法來形成指紋。
確定應用於每個可見AP的權重w可能是算法的重要部分。在示例實施例中，稻草人(strawman)方法可以是簡單地相等地加權每個可見的AP :1/ τ。在替代實施例中，權重可以基於給定AP實際上在空間中被觀測的概率。當空間被多次掃描時，一些AP可在每個掃描中被看見，而一些僅很少被看見。當在相同空間中時，用戶的指紋將趨向於具有AP的相同分布如果用戶的指紋不包含當在特定空間中時幾乎總是被觀測到的ΑΡ，則用戶不太可能在該空間中。根據掃描檢測頻率的加權反映了這種概念。具體地說，權重可以是Wi = TiZR其中，A是APi的讀數(the number of readings) ;R是構成該指紋的總讀數，
=λ。雖然在此關於接入點對於整個指紋的貢獻使用術語「權重」，但加權函數可以是
確定最關聯的接入點的任何特徵選擇函數。例如，接入點可以包括與區域內的接入點的可見性對應的可靠性標稱值(rating)。該可靠性標稱值可以用作特徵選擇函數，從而僅最可 靠的接入點被用於貢獻位置的指紋。「總是在線」接入點可能具有十分高的可靠性標稱值，而間歇性接入點可能具有低可靠性標稱值。特徵選擇函數可以生成與每個接入點對應的值，並且該值可以用於確定該特定接入點對於特定位置的指紋的有效性(significance)。本發明的實施例可以提供通過移除對指紋最低有效的數據三元組來從位置的指紋中移除數據三元組的方法。如上所述，每個數據三元組具有應用於接入點的與特徵選擇函數對應的值。可以從指紋中移除與最低有效值對應的數據三元組或多個數據三元組，由此壓縮指紋並且允許更多的指紋存儲在比本應先前已可能的更少量的存儲器中。最低有效值可以與具有最低權重(最低觀測頻率)的數據三元組對應，或其可以是具有最低可靠性標稱值的數據三元組。可以使用對該值的有效性的其它測量。實施例也可以使用對於值的閾值，從而可以從指紋中移除具有落入該閾值之下的值的任何數據三元組。圖4圖示了根據本發明的方法的示例實施例的操作。在塊401處接收空間到接入點柱狀圖。然後在塊402處歸一化該柱狀圖。然後可以在403處計算柱狀圖的均值。可以在塊404處計算標準偏差。在塊405處,如上所述將權重分配給接入點。在塊406處,權重、均值和標準偏差一起形成表示空間內觀測的接入點的數據三元組。如果在空間內觀測到更多的接入點，則塊401-406的處理可以重複，直到沒有進一步的接入點。在塊408處，一旦所有接入點都已經分配有數據三元組，則組合數據三元組以形成空間的指紋。為了找到兩個指紋之間的距離，可以確定存在於兩個指紋中的AP的信號強度的相似度，同時對缺失的(Hiissing)AP進行處罰。例如可以通過處理器60執行這些計算。任何兩個指紋的比較可以返回距離度量-KsS 1，其中，相同指紋的比較返回值1，脫離的指紋的比較返回-I的距離度量。脫離的指紋是不共享接入點的那些指紋。對於指紋A和B，每個APi的效果δ是
竹，I
.....................a...........;..........................k.....if Ie AJeBJ
JmiIδ<if i Λ,B, I
if ι AJe B其中，0是兩個高斯分布之間的重疊係數。總距離是每個δ之和。圖6圖示了計算一對指紋之間的距離的示例實施例。在圖示的實施例中，空間I中的二十次掃描已經觀測到三個不同的接入點(APp AP2和AP3)。空間2中的25次掃描已經觀測到兩個不同的接入點，其中的兩個與空間I中看見的接入點=APpAP2相同。在空間2中未觀測到AP3。為了計算空間I的權重，每個AP的觀測被觀測的總數相除20+15+5=40。相同行圖示了空間I和2的兩個指紋之間的距離是如何計算的
權利要求
1.一種方法，包括 接收與空間中觀測到的接入點對應的空間到接入點柱狀圖； 歸一化所述空間到接入點柱狀圖； 計算歸一化的空間到接入點柱狀圖的參數；以及 將特徵選擇函數應用到所述接入點以向所述接入點分配值。
2.如權利要求I所述的方法，其中所述特徵選擇函數是加權函數，並且其中所述值是與所述接入點在所述空間內被觀測的頻率對應的權重。
3.如權利要求I和2中任一所述的方法，其中所述參數包括所述歸一化的空間到接入點柱狀圖的均值和所述歸一化的空間到接入點柱狀圖的標準偏差。
4.如權利要求3所述的方法，其中每一個所述均值、所述標準偏差和所述值被組合以 形成表示在所述空間中觀測到的所述接入點的數據三元組。
5.如權利要求4所述的方法，其中對所述空間中觀測到的每個接入點重複所述方法，這樣所述空間中觀測到的多個接入點每個都由數據三元組表示。
6.如權利要求5所述的方法，其中所述多個數據三元組包括指紋。
7.如權利要求6所述的方法，其中從所述指紋中移除與所述最低有效值對應的至少一個數據三元組以創建壓縮的指紋。
8.如權利要求7所述的方法，其中所述壓縮的指紋被發送到行動裝置。
9.一種包括至少一個處理器和包括用於一個或多個程序的電腦程式代碼的至少一個存儲器的設備，所述至少一個存儲器和所述電腦程式代碼被配置為通過所述至少一個處理器使所述設備 接收與空間中觀測到的接入點對應的空間到接入點柱狀圖； 歸一化所述空間到接入點柱狀圖； 計算歸一化的空間到接入點柱狀圖的參數；以及 將特徵選擇函數應用到所述接入點以向所述接入點分配值。
10.如權利要求9所述的設備，其中所述電腦程式代碼通過所述至少一個處理器被進一步配置為使所述設備 接收與所述空間中觀測到的多個接入點對應的多個空間到接入點柱狀圖； 歸一化所述多個空間到接入點柱狀圖中的每一個空間到接入點柱狀圖； 計算所述多個歸一化的空間到接入點柱狀圖中的每一個空間到接入點柱狀圖的參數；以及 將特徵選擇函數應用到所述多個接入點中的每一個接入點以向所述多個接入點中的每一個接入點分配值。
11.如權利要求9和10中任一所述的設備，其中所述特徵選擇函數是加權函數，並且其中所述值是與所述接入點在所述空間內被觀測的頻率對應的權重。
12.如權利要求10所述的設備，其中計算所述多個歸一化的空間到接入點柱狀圖的參數包括計算所述多個歸一化的空間到接入點柱狀圖中的每一個空間到接入點柱狀圖的均值以及計算所述多個歸一化的空間到接入點柱狀圖中的每一個空間到接入點柱狀圖的標準偏差。
13.如權利要求12所述的設備，其中與接入點對應的每一個所述均值、標準偏差和值被組合以形成表示在所述空間中觀測到的所述接入點的數據三元組。
14.如權利要求13所述的方法，其中所述多個數據三元組包括指紋。
15.如權利要求14所述的方法，其中從所述指紋中移除與最低有效值對應的至少一個數據三元組以創建壓縮的指紋。
16.如權利要求15所述的方法，其中所述壓縮的指紋被發送到行動裝置。
17.—種包括具有在其中存儲的計算機可執行程序代碼指令的至少一個計算機可讀存儲介質的電腦程式產品，所述計算機可執行程序代碼指令包括 用於接收與空間中觀測到的接入點對應的空間到接入點柱狀圖的程序代碼指令； 用於歸一化所述空間到接入點柱狀圖的程序代碼指令； 用於計算歸一化的空間到接入點柱狀圖的參數的程序代碼指令；以及 用於將特徵選擇函數應用到所述接入點以向所述接入點分配值的程序代碼指令。
18.如權利要求17所述的電腦程式產品，其中所述計算機可執行程序代碼指令進一步包括 用於接收與所述空間中觀測到的多個接入點對應的多個空間到接入點柱狀圖的程序代碼指令； 用於歸一化所述多個空間到接入點柱狀圖中的每一個空間到接入點柱狀圖的程序代碼指令； 用於計算所述多個歸一化的空間到接入點柱狀圖中的每一個空間到接入點柱狀圖的參數的程序代碼指令；以及 用於將特徵選擇函數應用到所述多個接入點中的每一個接入點以向所述多個接入點中的每一個接入點分配值的程序代碼指令。
19.如權利要求17和18中任一所述的電腦程式，其中所述特徵選擇函數是加權函數，並且其中所述值是與所述接入點在所述空間內被觀測的頻率對應的權重。
20.如權利要求17-19中任一所述的電腦程式，其中用於計算所述多個歸一化的空間到接入點柱狀圖的參數的所述程序代碼指令包括用於計算所述多個歸一化的空間到接入點柱狀圖中的每一個空間到接入點柱狀圖的均值以及計算所述多個歸一化的空間到接入點柱狀圖中的每一個空間到接入點柱狀圖的標準偏差的程序代碼指令。
21.如權利要求20所述的電腦程式產品，其中與接入點對應的每一個所述均值、標準偏差和權重被組合以形成表示所述空間中觀測到的所述接入點的數據三元組。
22.如權利要求21所述的電腦程式產品，其中所述多個數據三元組包括指紋。
23.如權利要求22所述的電腦程式產品，進一步包括用於從所述指紋中移除與最低有效值對應的至少一個數據三元組以創建壓縮的指紋的程序代碼指令。
24.如權利要求23所述的電腦程式產品，進一步包括用於將所述壓縮的指紋發送到行動裝置的程序代碼指令。
25.—種方法,包括 確定第一指紋的接入點； 確定第二指紋的接入點； 計算所述第一指紋和所述第二指紋共有的接入點的信號強度中的相似度； 確定每一個所述第一指紋和所述第二指紋獨有的接入點；以及通過使用所述第一指紋和所述第二指紋共有的接入點的所述信號強度中的相似度指示接近距離以及獨有的接入點指示遠離距離來計算所述第一指紋和所述第二指紋之間的距離。
26.如權利要求25所述的方法，其中第一行動裝置觀測所述第一指紋，並且其中第二行動裝置觀測所述第二指紋。
27.如權利要求26所述的方法，所述方法進一步包括估算所述第一行動裝置和所述第二行動裝置是否正佔有同一空間。
28.如權利要求26和27中任一所述的方法,所述方法進一步包括基於所述第一行動裝置與所述第二行動裝置之間的距離而向所述第一行動裝置和所述第二行動裝置分配許可。
29.如權利要求26-28中任一所述的方法，所述方法進一步包括如果所述第一行動裝置與所述第二行動裝置之間的距離超過閾值，則阻止所述第一行動裝置與所述第二行動裝置之間的信息的交換。
30.如權利要求25所述的方法，其中行動裝置觀測所述第一指紋，並且其中在與虛擬消息關聯的位置處觀測所述第二指紋。
31.如權利要求30所述的方法，所述方法進一步包括 確定所述距離何時在與所述虛擬消息關聯的位置的半徑內；以及 至少部分地基於所述確定而至少部分地引起所述行動裝置的告警。
32.如權利要求31所述的方法，所述方法進一步包括 接收用於指定一個或多個準則的輸入， 其中所述行動裝置的告警進一步至少部分地基於所述一個或多個準則。
33.如權利要求30-32中任一所述的方法，所述方法進一步包括 至少部分地基於所述第一指紋而確定第一命名位置； 至少部分地基於所述第二指紋而確定第二命名位置； 確定所述第一名稱位置是否基本上匹配所述第二命名位置；以及 基於基本的匹配而至少部分地引起所述行動裝置的告警。
34.一種承載一個或多個指令的一個或多個序列的計算機可讀存儲介質，當被一個或多個處理器執行時所述一個或多個指令的一個或多個序列使設備執行至少如權利要求1-8中任一所述的方法。
35.一種設備，包括用於執行如權利要求1-8中任一所述的方法的裝置。
36.如權利要求35所述的設備，其中所述設備是行動電話，其進一步包括 配置為通過使用顯示器促進所述行動電話的至少一些功能的用戶控制以及配置為響應用戶輸入的用戶接口電路和用戶接口軟體；以及 配置為顯示所述行動電話的用戶接口的至少一部分的顯示器和顯示器電路，所述顯示器和顯示器電路被配置為促進所述行動電話的至少一些功能的用戶控制。
37.一種包括一個或多個指令的一個或多個序列的電腦程式產品，當被一個或多個處理器執行時所述一個或多個指令的一個或多個序列使設備至少執行如權利要求1-8中任一所述的方法的步驟。
38.一種方法，包括促進對至少一個接口的訪問，所述至少一個接口被配置為允許對至少一種服務的訪問，所述至少一種服務被配置為執行如權利要求1-8中任一所述的方法。
39.一種承載一個或多個指令的一個或多個序列的計算機可讀存儲介質，當被一個或多個處理器執行時所述一個或多個指令的一個或多個序列使設備執行至少如權利要求14-16中任一所述的方法。
40.一種設備，包括用於執行如權利要求14-16中任一所述的方法的裝置。
41.如權利要求40所述的設備，其中所述設備是行動電話，其進一步包括 配置為通過使用顯示器促進所述行動電話的至少一些功能的用戶控制以及配置為響應用戶輸入的用戶接口電路和用戶接口軟體；以及 配置為顯示所述行動電話的用戶接口的至少一部分的顯示器和顯示器電路，所述顯示器和顯示器電路被配置為促進所述行動電話的至少一些功能的用戶控制。
42.一種包括一個或多個指令的一個或多個序列的電腦程式產品，當被一個或多個處理器執行時所述一個或多個指令的一個或多個序列使設備至少執行如權利要求14-16中任一所述的方法的步驟。
43.一種方法，包括促進對至少一個接口的訪問，所述至少一個接口被配置為允許對至少一種服務的訪問，所述至少一種服務被配置為執行如權利要求14-16中任一所述的方法。
44.一種包括至少一個處理器和包括用於一個或多個程序的電腦程式代碼的至少一個存儲器的設備，所述至少一個存儲器和所述電腦程式代碼被配置為通過所述至少一個處理器使所述設備 確定第一指紋的接入點； 確定第二指紋的接入點； 計算所述第一指紋和所述第二指紋共有的接入點的信號強度中的相似度； 確定每一個所述第一指紋和所述第二指紋獨有的接入點；以及 通過使用所述第一指紋和所述第二指紋共有的接入點的信號強度中的相似度指示接近距離以及獨有的接入點指示遠離距離來計算所述第一指紋和所述第二指紋之間的距離。
45.如權利要求44所述的設備，其中第一行動裝置觀測所述第一指紋，並且其中第二行動裝置觀測所述第二指紋。
46.如權利要求44-45中任一所述的設備，其中所述電腦程式代碼通過所述至少一個處理器被進一步配置為使所述設備 估算所述第一行動裝置和所述第二行動裝置是否正佔有同一空間。
47.如權利要求45所述的設備，其中所述電腦程式代碼通過所述至少一個處理器被進一步配置為使所述設備 基於所述第一行動裝置與所述第二行動裝置之間的距離而向所述第一行動裝置和所述第二行動裝置分配許可。
48.如權利要求45所述的設備，其中所述電腦程式代碼通過所述至少一個處理器被進一步配置為使所述設備 如果所述第一行動裝置與所述第二行動裝置之間的距離超過閾值，則阻止所述第一行動裝置與所述第二行動裝置之間的信息的交換。
49.如權利要求44所述的設備，其中行動裝置觀測所述第一指紋，並且其中在與虛擬消息關聯的位置處觀測所述第二指紋。
50.如權利要求49所述的設備，其中所述電腦程式代碼通過所述至少一個處理器被進一步配置為使所述設備 確定所述距離何時在與所述虛擬消息關聯的位置的半徑內；以及 至少部分地基於所述確定而至少部分地引起所述行動裝置的告警。
51.如權利要求50所述的設備，其中所述電腦程式代碼通過所述至少一個處理器被進一步配置為使所述設備 接收用於指定一個或多個準則的輸入， 其中所述行動裝置的告警進一步至少部分地基於所述一個或多個準則。
52.如權利要求49所述的設備，其中所述電腦程式代碼通過所述至少一個處理器被 進一步配置為使所述設備 至少部分地基於所述第二指紋確定第二命名位置； 確定所述第一命名位置是否基本上匹配所述第二命名位置；以及 基於基本的匹配而至少部分地引起所述行動裝置的告警。
53.如權利要求44-52中任一所述的設備，其中所述設備是行動電話，其進一步包括 配置為通過使用顯示器促進所述行動電話的至少一些功能的用戶控制以及配置為響應用戶輸入的用戶接口電路和用戶接口軟體；以及 配置為顯示所述行動電話的用戶接口的至少一部分的顯示器和顯示器電路，所述顯示器和顯示器電路被配置為促進所述行動電話的至少一些功能的用戶控制。
54.一種方法，包括促進創建和/或促進修改至少一個設備用戶接口部件和/或功能性，所述至少一個設備用戶接口部件和/或功能性至少部分地基於以下 由如權利要求1-8中任一所述的方法產生的數據和/或信息，和/或 由如權利要求1-8中任一所述的方法產生的至少一個信號。
55.一種方法，包括促進創建和/或促進修改至少一個設備用戶接口部件和/或功能性，所述至少一個設備用戶接口部件和/或功能性至少部分地基於以下 由如權利要求14-16中任一所述的方法產生的數據和/或信息，和/或 由如權利要求14-16中任一所述的方法產生的至少一個信號。
56.一種方法，包括促進處理和/或處理(I)數據和/或(2)信息和/或(3)至少一個信號；所述(I)數據和/或(2)信息和/或(3)至少一個信號至少部分地基於如權利要求1-8中任一所述的方法。
57.一種方法，包括促進處理和/或處理(I)數據和/或(2)信息和/或(3)至少一個信號；所述(I)數據和/或(2)信息和/或(3)至少一個信號至少部分地基於如權利要求14-16中任一所述的方法。
58.一種方法，包括促進對至少一個接口的訪問，所述至少一個接口被配置為允許對至少一種服務的訪問，所述至少一種服務被配置為執行如權利要求1-8中任一所述的方法。
59.一種方法，包括促進對至少一個接口的訪問，所述至少一個接口被配置為允許對至少一種服務的訪問，所述至少一種服務被配置為執行如權利要求14-16中任一所述的方法。
全文摘要
提供了一種使用壓縮的指紋檔案的設備上定位的方法和設備。所述方法和設備可以被配置為提供對定位指紋的壓縮，促進基於RF指紋模型的高效設備上定位，並且估算兩個或更多個設備之間的物理距離。所述方法的實施例可以接收與空間中觀測到的接入點對應的空間到接入點柱狀圖。可以歸一化所述柱狀圖，並且可以從所述柱狀圖計算均值和標準偏差。可以將權重分配給與接入點在空間內被觀測的頻率對應的接入點。可以對於空間內觀測的多個接入點中的每一個計算並且分配均值、標準偏差和權重。可以組合每個接入點的均值、標準偏差和權重以形成數據三元組。可以組合數據三元組以形成從該空間觀測的接入點的指紋。可以從所述指紋中移除具有最低分配的權重的數據三元組或多個數據三元組。
文檔編號G01S5/14GK102741701SQ201080063134
公開日2012年10月17日 申請日期2010年11月30日 優先權日2009年12月4日
發明者J·萊德利 申請人:諾基亞公司