[go: up one dir, main page]

CN102170696A - 用于存储信标基准数据的cuckoo散列 - Google Patents

用于存储信标基准数据的cuckoo散列 Download PDF

Info

Publication number
CN102170696A
CN102170696A CN2011100722220A CN201110072222A CN102170696A CN 102170696 A CN102170696 A CN 102170696A CN 2011100722220 A CN2011100722220 A CN 2011100722220A CN 201110072222 A CN201110072222 A CN 201110072222A CN 102170696 A CN102170696 A CN 102170696A
Authority
CN
China
Prior art keywords
beacon
reference data
hash table
verification
identifier
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Granted
Application number
CN2011100722220A
Other languages
English (en)
Other versions
CN102170696B (zh
Inventor
J·李
J-H·林
A·K·瑟沙德瑞
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Microsoft Technology Licensing LLC
Original Assignee
Microsoft Corp
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Microsoft Corp filed Critical Microsoft Corp
Publication of CN102170696A publication Critical patent/CN102170696A/zh
Application granted granted Critical
Publication of CN102170696B publication Critical patent/CN102170696B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01S—RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
    • G01S5/00—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations
    • G01S5/02—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations using radio waves
    • G01S5/0205—Details
    • G01S5/0236—Assistance data, e.g. base station almanac
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01S—RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
    • G01S1/00—Beacons or beacon systems transmitting signals having a characteristic or characteristics capable of being detected by non-directional receivers and defining directions, positions, or position lines fixed relatively to the beacon transmitters; Receivers co-operating therewith
    • G01S1/02—Beacons or beacon systems transmitting signals having a characteristic or characteristics capable of being detected by non-directional receivers and defining directions, positions, or position lines fixed relatively to the beacon transmitters; Receivers co-operating therewith using radio waves
    • G01S1/04—Details
    • G01S1/042—Transmitters
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01S—RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
    • G01S5/00—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations
    • G01S5/02—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations using radio waves
    • G01S5/0205—Details
    • G01S5/0226—Transmitters
    • G—PHYSICS
    • G01—MEASURING; TESTING
    • G01S—RADIO DIRECTION-FINDING; RADIO NAVIGATION; DETERMINING DISTANCE OR VELOCITY BY USE OF RADIO WAVES; LOCATING OR PRESENCE-DETECTING BY USE OF THE REFLECTION OR RERADIATION OF RADIO WAVES; ANALOGOUS ARRANGEMENTS USING OTHER WAVES
    • G01S5/00—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations
    • G01S5/02—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations using radio waves
    • G01S5/0278—Position-fixing by co-ordinating two or more direction or position line determinations; Position-fixing by co-ordinating two or more distance determinations using radio waves involving statistical or probabilistic considerations
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04L—TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION
    • H04L1/00—Arrangements for detecting or preventing errors in the information received
    • H04L1/004—Arrangements for detecting or preventing errors in the information received by using forward error control
    • H04L1/0056—Systems characterized by the type of code used
    • H04L1/0061—Error detection codes
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W48/00—Access restriction; Network selection; Access point selection
    • H04W48/08—Access restriction or access information delivery, e.g. discovery data delivery
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W48/00—Access restriction; Network selection; Access point selection
    • H04W48/16—Discovering, processing access restriction or access information
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W64/00—Locating users or terminals or network equipment for network management purposes, e.g. mobility management
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W88/00—Devices specially adapted for wireless communication networks, e.g. terminals, base stations or access point devices
    • H04W88/08—Access point devices

Landscapes

  • Physics & Mathematics (AREA)
  • Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Probability & Statistics with Applications (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Mobile Radio Communication Systems (AREA)

Abstract

存储和检索被截短的cuckoo散列表中的信标基准数据。使用与信标相关联的信标标识符的校验和来检索散列表中描述信标的位置的信标基准数据。数据通过cuckoo散列被存储在一个或多个散列表中以消除混叠。将散列表提供给诸如移动设备这样的设备。设备使用所观察到的信标的信标标识符从表中检索信标基准数据。使用所检索的信标基准数据来推断设备的位置信息。Cuckoo散列表消耗较少的存储器存储空间并且模糊信标基准数据。

Description

用于存储信标基准数据的CUCKOO散列
技术领域
本发明涉及无线通信，尤其涉及存储信标基准数据。
背景
现有的系统收集或确定描述信标或其他无线接入点的位置的信标基准数据。信标基准数据包括例如信标的位置信息。信标基准数据被分发给移动设备以使移动设备能基于它们所观察到的信标的位置来估计它们的位置。根据现有的系统，信标基准数据耗用了移动设备上可用的大量有限存储器，还耗用了大量带宽用于进行分发。
一些现有的系统已经尝试通过压缩信标基准数据来减小信标基准数据的大小。这些系统还将信标标识符与经压缩的信标基准数据一起存储。由于信标标识符通常比信标基准数据耗用更多存储器，因此这种现有的系统在存储器消耗方面提供了极小的减少。其他现有的系统使用信标标识符作为键来将信标基准数据存储在散列表中。除了在存储器消耗方面提供的减少极小以外，这些系统还有隐私问题，因为移动设备的用户能够迭代地通过散列表以获得信标基准数据。
概述
本发明的各实施例从被截短的cuckoo(布谷鸟)散列表获得信标的信标基准数据以推断计算设备的位置。访问与信标相关联的数据。该数据包括信标标识符和描述信标位置的信标基准数据。散列表中的多个潜在位置由第一计算设备所标识。计算信标标识符的校验和。第一计算设备执行cuckoo散列来将信标基准数据和所计算的校验和存储在散列表中多个潜在位置之一中。第一计算设备将散列表分发给第二计算设备，后者经由所计算的校验和从散列表检索信标基准数据。
提供本发明内容是为了以简化的形式介绍将在以下详细描述中进一步描述的一些概念。本发明内容不旨在标识出所要求保护的主题的关键特征或必要特征，也不旨在用于帮助确定所要求保护的主题的范围。
附图简述
图1是示出移动计算设备存储从服务器计算设备接收到的被截短的cuckoo散列表的示例性框图。
图2是示出通过对信标基准数据进行cuckoo散列来进行散列表的创建和分发的示例性流程图。
图3是示出被截短的cuckoo散列表中的混叠的示例性框图。
在附图中，对应的附图标记指示对应的部分。
详细描述
参考附图，本发明的各实施例将信标104的信标基准数据108存储在被截短的cuckoo散列表中。在一些实施例中，用于位置检索的无线接入点(WAP)的小块被预先分发给诸如客户机设备的设备。当客户机设备之一观察到附近的信标104时，使用信标104的信标标识符来获得所观察到的信标104的信标基准数据108。使用所获得的信标基准数据108来推断客户机设备的位置。
本发明的各方面通过将每个信标标识符的校验和而不是实际信标标识符存储在散列表中，从而减少信标基准数据108的存储器存储量。而且，通过存储信标标识符的校验和，本发明的各方面通过防止用户挖掘预先分发的小块来推断什么信标104位于什么位置，从而模糊信标基准数据108。为了减少散列表中的混叠，本发明的各实施例使用cuckoo散列来消除冲突。
虽然参照校验和被描述为用于散列、模糊或以其他方式将一个值转换成另一个值的手段，本发明的各方面不限于计算信标标识符的校验和。相反，构想了其他计算并且它们在本发明的范围内。
再次参照图1，一示例性框图示出移动计算设备102存储从服务器计算设备112接收到的被截短的cuckoo散列表106。移动计算设备102例如包括移动计算设备#1至移动计算设备#N。示例性的移动计算设备102包括装备有全球定位系统(GPS)接收机的移动电话。然而，移动计算设备102包括执行指令(例如应用程序)以存储和访问被截短的cuckoo散列表106的任何设备。例如，移动计算设备102包括诸如膝上型计算机、上网本、游戏设备和/或便携式媒体播放器之类的便携式计算设备。此外，移动计算设备102的每一个可以表示一组处理单元或其他计算设备。
移动计算设备102检测或观察包括蜂窝塔(或在采用有向天线时的扇区)以及无线保真(Wi-Fi)接入点或其他无线接入点(WAP)在内的一个或多个信标104。如下详述，移动计算设备102然后基于存储在散列表106中的和所观察到的信标104相关联的信标基准数据108来推断其位置。虽然本公开的各方面可以参考实现诸如蜂窝传输协议和802.11系列协议之类的协议的信标104来描述，但本发明的各实施例可与能进行无线通信的任何信标104一起操作。
服务器计算设备112经由网络110与移动计算设备102进行通信。虽然在客户机-服务器通信的上下文中描述，本发明的各方面也可以在诸如对等实施例等其他环境中操作。服务器计算设备112存储或可以访问描述一个或多个信标104的大致位置的数据。该数据被称为信标基准数据108。或者或另外，信标基准数据108可以被存储在服务器计算设备112内部。在一些实施例中，信标基准数据108包括例如信标104的经度值、纬度值和海拔值。
服务器计算设备112包括基于信标基准数据108来创建被截短的cuckoo散列表106的任何计算设备。在图1的例子中，服务器计算设备112还将所创建的散列表106分发给移动计算设备102。
示例性网络110包括有线和/或无线网络，并且可以表示局域网或诸如提供对因特网的访问的全球网络。在其中网络110包括无线网络的实施例中，服务器计算设备112和移动计算设备102可以启用各种技术，诸如蓝牙(商标)无线通信服务(受保护或不受保护)、射频识别(RFID)、诸如对等Wi-Fi之类的Wi-Fi、ZIGBEE(商标)无线通信服务、Z-WAVE(商标)无线通信服务、近场通信(NFC)、以及其他启用近程或远程无线通信的技术。
移动计算设备102的每一个还包括至少一个处理器114和诸如存储器区域116之类的一个或多个计算机可读介质。处理器114包括任何数量的处理单元，并且被编程为执行用于实现本发明的各方面的计算机可执行指令。指令可由处理器114或由在移动计算设备102内执行的多个处理器执行，或者由计算设备外部的处理器(例如，由云服务)来执行。在某些实施例中，处理器114被编程为执行诸如附图(例如，图3)中示出的那些指令。
存储器区域116包括与移动计算设备102相关联或可以由移动计算设备102访问的任意数量的介质。存储器区域116可以在移动计算设备102的内部(如图1所示)、在移动计算设备102的外部(未示出)、或两者(未示出)。
存储器区域116还存储用于实现本方面的各方面的一个或多个计算机可执行组件。示例性组件包括存储器组件120、检测组件122、评级组件124、检索组件126和位置组件128。移动计算设备102的每一个执行各组件以便从散列表106检索信标基准数据108并且确定移动计算设备102的位置。下面讨论各组件的操作。图1中的各元件的至少一部分功能可以由图1中的其他元件或图1中未示出的实体(例如，处理器、web服务、服务器、应用程序、计算设备等)执行。
接着参考图2，一示例性流程图示出服务器计算设备112通过对信标基准数据108进行cuckoo散列来创建和分发散列表106。在该例中，参考图2示出和描述的操作由服务器计算设备112(例如第一计算设备)执行。在202，访问与一个或多个信标104相关联的数据。对于每一个信标104，所访问的数据包括信标标识符和描述信标104的位置的信标基准数据108。信标标识符的每一个对应于信标104之一。例如，每个Wi-Fi信标具有一个基本服务集标识符(BSSID)。在另一例中，每个全球移动通信服务(GSM)蜂窝塔包括移动国家代码(MCC)、移动网络代码(MNC)、位置区域代码(LAC)和小区标识符。通用移动电信系统(UMTS)塔具有由MCC、MNC和小区标识符所组成的信标标识符。载波分集多址(CDMA)塔具有由系统标识符、网络标识符和基站标识符所组成的信标标识符。在一实施例中，信标标识符包括BSSID和服务集标识符(SSID)的一个或多个。
在一些实施例中，访问与多个信标104相关联的数据。例如，多个信标104表示位于同一地理区域内的信标104的小块。构想了其他信标104的组。每一个信标104可以被分配给散列表中的多个位置或条目之一。在203，标识散列表中的潜在位置。通过使用信标标识符作为输入来执行所定义数量的散列函数或其他计算，从而标识可用的位置。散列表函数的输出确定了散列表中的可能或潜在位置。增加散列函数的数量增加了散列表中潜在位置的数量。
在204，对于每一个位置，计算该位置的信标标识符的校验和。例如，该操作可由校验和(信标标识符)来表示。在206，执行cuckoo散列以将信标基准数据108和为每一个信标104计算的校验和存储在被截短的cuckoo散列表中。将所计算的校验和而不是信标标识符存储在散列表中。由于所计算的校验和相比信标标识符使用较少的存储器，因此所产生的散列表使用了较少的存储器。
在一些实施例中，cuckoo散列包括选择散列表中的所标识的潜在位置之一来存储所计算的校验和和相应的信标基准数据108。本发明的各方面评估特定信标104的每一个潜在位置以消除任何冲突。例如，分析每一个位置来确定所计算的校验和是否与已经被分配给该位置或可能被分配给该位置的另一校验和相同。如果可能用相同的校验和将不止一个信标标识符分配给相同的位置，则宣布冲突，并且不将任何信标标识符分配给该位置。在散列表的可用位置中，本发明的各方面确认每个位置中存储的校验和相对于彼此是唯一的。在标识和消除了冲突之后，本发明的各方面找到信标标识符和潜在位置之一之间的匹配，使得将每一个信标标识符分配给唯一的位置。以下图3示出和描述了cuckoo散列中的冲突消除。
在一些实施例中，信标104的信标基准数据108被存储在单个散列表中。在其他实施例中，为信标104的每个小块，即组，创建一个分开的散列表。
可以存储附加数据作为信标基准数据108的一部分。例如，可以存储信标104的无线信道和所观察的信号强度。
例如，每个信标具有6字节的BSSID、4字节的SSID、2字节的经度值和2字节的纬度值(例如，对于每个信标总共14个字节)。本发明的各实施例构想BSSID和/或SSID的2字节校验和，使得所存储的数据等于2字节校验和以及经度值和纬度值的4字节(例如，对于每个信标总共6个字节)。由此，本发明的各实施例使存储器消耗减少一半。
在将信标基准数据108和相应的校验和存储在一个或多个散列表中之后，在208，散列表106被分发或以其他方式被提供给移动计算设备102(例如第二计算设备)。一些实施例基于移动计算设备102的地理区域、移动计算设备102的移动模式、移动计算设备102的订阅简档或其他标准来分发散列表106。例如，将和每一个移动计算设备102的家庭区域代码相对应的小块提供给移动计算设备102。
每一个移动计算设备102将所接收的散列表106存储在其本地存储器区域中(例如存储器区域116)。在其他实施例中，所接收的散列表106被存储在距移动计算设备102远程但可由移动计算设备102访问的存储器区域中。
每一个移动计算设备102访问散列表106以推断移动计算设备102的位置。例如，移动计算设备102之一检测在移动计算设备102的邻近范围内的一个或多个信标104。移动计算设备102通过使用所检测的信标104的信标标识符作为输入来计算散列函数，从而计算多个潜在的位置。对于每一个潜在位置，计算与所检测的信标104相关联的信标标识符的校验和。通过使用所计算的校验和，移动计算设备102访问散列表106来检索、获得或以其他方式访问与每一个所检测的信标104相关联的信标基准数据108。例如，对于每一个潜在位置，如果存储在散列表中该位置处的校验和与该位置的信标标识符的所计算的校验和相匹配，则检索相关联的信标基准数据108。通过使用所检索的信标基准数据108，移动计算设备102基于所检测的信标104的位置来确定移动计算设备102的位置。如果没有一个从信标标识符计算的校验和与散列表中各个位置处存储的校验和相匹配，则本发明的各方面得出结论：信标标识符不存在于散列表中，且因此不检索任何信标基准数据108。
在一些实施例中，移动计算设备102将所检索的信标基准数据108与和移动计算设备102相关联的域信息相比较以确认或验证所检索的信标基准数据108。以此方式，信标基准数据108被过滤以避免错误的肯定响应。
参照图1所示的各组件，存储器组件120在由处理器114执行时使处理器114存储多个散列表106。每一个散列表106对应于一组信标104。各个组的每一个表示一地理区域(例如，小块)。散列表106存储与信标104相关联的信标基准数据108。信标104的每一个具有一信标标识符。通过执行cuckoo散列来将信标基准数据108和信标标识符的校验和存储在散列表106中的多个潜在位置之一，使得没有其他具有相同校验和的信标标识符被存储在该位置，从而创建多个散列表106。
检测组件112在由处理器114执行时使处理器114检测移动计算设备102邻近范围内的一个或多个信标104。评级组件124在由处理器114执行时使处理器114至少基于检测组件122所检测的信标104、信标覆盖率以及混叠率来为各组信标104的每一组计算一个分数。基于所计算的分数，评级组件124还选择多个散列表106中的至少一个。
在一些实施例中，分数反映了使用一组(例如小块)特定信标104会出现错误的肯定(例如，由于混叠而检索错误的信标基准数108)的概率，并且至少部分基于所检测的信标104是否在该组内。错误肯定的概率随着移动计算设备102所高速缓存的小块数量的增加而增加。而且，在低覆盖密度的区域(例如，以前未观察到更多信标104的区域)中更多地宣布混叠。
可以按以下公式(1)所示来计算小块Si的示例分数。
Qi＝概率(信标w是小块Si中的准确匹配|Si(w)＝真)
＝ci/(ci+α(1-ci))    (1)
在公式(1)中，α是混叠率(例如，如果用4次散列函数被截短为1字节时约为1.56％；用4次散列函数的2字节校验和时为0.006％)，ci是信标覆盖率(例如，对于小块Si的已知信标相对于信标总数的所估计的百分比)，w是所观察到的信标。分母中的第一项ci表示信标w在小块Si内并且是已知信标(例如，准确或真匹配)的条件概率。第二项α(1-ci)表示信标w在小块Si内并且是未知信标且Si(w)＝真(例如，与可能处在小块内很不同且远距位置处的已知信标的错误匹配)的条件概率。
给定一组k个所观察到的信标(w1，w2，…，wk)，每个小块Si的分数如下在公式(2)的例子中计算。
分数(Si|(w1，w2，...，wk))＝∑jQi×Si(wj)＝(ci/(ci+α(1-ci)))∑jSi(wj)    (2)
覆盖率越高且混叠率越低，则质量分数Qi就越高，如下表1中的示例数据所示。
  覆盖率   混叠率   质量分数
  90.000％   1.563％   0.998266898
  90.000％   0.006％   0.999993218
  50.000％   1.563％   0.984615385
  50.000％   0.006％   0.999938969
  10.000％   1.563％   0.876712329
  10.000％   0.006％   0.999450985
  1.000％   1.563％   0.392638037
  1.000％   0.006％   0.993993812
表1.示例质量分数。
本发明的各方面然后选择和具有最高分数的小块相对应的散列表。检索组件126在由处理器114执行时使处理器114标识所选择的散列表中的潜在位置，并且计算所标识的潜在位置处的信标标识符的校验和。检索组件126还从所选择的散列表中其校验和与位置的所计算校验和相匹配的各位置中，获得与检测组件122所检测的信标104相关联的信标基准数据108。位置组件128在由处理器114执行时使处理器114基于检索组件126所获得的信标基准数据108来确定移动计算设备102的位置。在一些实施例中，位置组件128通过在在确定移动计算设备102位置之前，通过离群消除来过滤所获得的信标基准数据108。
在某些实施例中，图2所示的操作由服务器计算设备112来执行。在其他实施例中，图2所示的操作中的一个或多个由另一计算设备(例如，作为web服务)来执行。在诸如对等实施例等其他实施例中，图2所示的操作中的一个或多个由移动计算设备102执行。
此外，图2所示的操作可以被实现为在计算机可读介质上编码的软件指令，以被编程或设计为执行操作的硬件来实现，或这两者。例如，图2中的操作可以被实现为计算机可执行组件或其他软件。
接着参考图3，一示例性框图示出被截短的cuckoo散列表中的混叠。Cuckoo散列在编码阶段避免了共享相同校验和值的信标标识符之间的冲突。接着描述用于cuckoo散列的示例性方法。
如图3所示，一列信标标识符被映射到散列表中的可用条目或位置。如果一条目带有具有同一校验和的不止一个信标标识符，则从具有该校验和的信标标识符中移除到该条目的链接，以消除冲突。在图3的例子中，校验和1(BI1)等于校验和1(BIn)，表示冲突，因此将移除从BI1和BIn到该条目的链接。由于在该例中校验和2(BI2)不等于校验和2(BIn)，因此在该位置中不存在冲突。在将多个散列表106提供给移动计算设备102的实施例中，跨多个散列表106执行所述的唯一性确认以避免混叠。
本发明的各方面前进至如下地寻找信标标识符和可用条目之间的匹配。信标标识符被(随机地或以其他方式)分配给未被占用的相应的、可用的(例如非冲突)条目之一。如果对于一给定信标标识符占用了可用条目，则评估其中的占用者以便重新定位至另一条目。重新定位评估以增加的深度继续，直到已经为该信标标识符和占用者找到可用条目。匹配过程继续，直到已经将信标标识符分配给非冲突条目或者当没有占用者能被重新定位(例如，提示出错消息)时。
附加示例
一些实施例基于覆盖率来调节混叠率。例如，当覆盖很高时，可以容忍较高的混叠率(例如较高压缩)来实现存储器存储耗用中的更大减少。或者或另外，基于不同应用程序场景中所观察到的错误肯定的成本，用因子λ对混叠率进行加权。例如，当错误肯定带有较高成本时，λ大于1，而如果错误肯定的成本低时，λ在0和1之间。在这一实施例中，上面的公式(2)被修改以包括λ，如公式(3)所示。
Qi＝概率(信标w是小块Si中的真匹配|Si(w)＝真)＝ci/(ci+λα(1-ci))    (3)
虽然参考从用户收集的数据来描述各实施例，但本发明的各方面向用户提供数据收集的通知(例如，经由对话框或偏好设置)以及给出或拒绝同意的机会。该同意可以采用加入同意或退出同意的形式。
示例性操作环境
示例性计算机可读介质包括闪存驱动器、数字多功能盘(DVD)、紧致盘(CD)、软盘以及磁带盒。作为示例而非限制，计算机可读介质包括计算机存储介质和通信介质。计算机存储介质存储诸如计算机可读指令、数据结构、程序模块或其他数据等信息。通信介质一般以诸如载波或其它传输机制等已调制数据信号来体现计算机可读指令、数据结构、程序模块或其它数据，并且包括任何信息传递介质。以上的任一种的组合也包括在计算机可读介质的范围之内。
尽管结合示例性计算系统环境进行了描述，但本发明的各实施例可用于众多其它通用或专用计算系统环境或配置。适用于本发明各方面的公知的计算系统、环境和/或配置的示例包括，但不限于：移动计算设备、个人计算机、服务器计算机、手持式或膝上型设备、多处理器系统、游戏控制台、基于微处理器的系统、机顶盒、可编程消费电子产品、移动电话、网络PC、小型机、大型计算机、包括上述系统或设备中的任一个的分布式计算机环境等等。
可以在由一台或多台计算机或其他设备执行的诸如程序模块之类的计算机可执行的指令的一般上下文中来描述本发明的各实施例。计算机可执行指令可以被组织成一个或多个计算机可执行组件或模块。一般而言，程序模块包括，但不限于，执行特定任务或实现特定抽象数据类型的例程、程序、对象、组件，以及数据结构。可以利用任何数量的这样的组件或模块及其组织来实现本发明的各方面。例如，本发明的各方面不仅限于附图中所示出并且在此处所描述的特定计算机可执行指令或特定组件或模块。本发明的其他实施例可以包括具有比此处所示出和描述的功能更多或更少功能的不同的计算机可执行指令或组件。
本发明的各方面当被配置成执行此处所描述的指令时将通用计算机变换成专用计算设备。
这里示出和描述的各实施例已经未在此特别描述但在本发明各方面范围内的各实施例构成了用于以下操作的示例性手段：用于从cuckoo散列表获得信标104的信标基准数据108以推断移动计算设备102的位置、以及用于使用信标标识符的校验和从cuckoo散列表获得信标104的信标基准数据108。
此处所示出和描述的本发明的各实施例中的操作的执行或实现的顺序不是必需的，除非另外指定。即，除非另外指定，否则操作可以按任何顺序执行，且本发明的各实施例可以包括比此处所公开的操作更多或更少的操作。例如，构想了在一个操作之前、同时或之后执行另一个操作是在本发明的各方面的范围之内的。
当介绍本发明的各方面的元素或其实施例时，冠词“一”、“一个”、“该”、“所述”旨在表示有元素中的一个或多个。术语“包括”、“包含”以及“具有”旨在是包含性的，并意味着除所列出的元素以外还可以有额外的元素。
已经详细地描述了本发明的各方面，显然，在不偏离所附权利要求书所定义的本发明的各方面的范围的情况下，可以进行各种修改和变化。在不偏离本发明的各方面的范围的情况下，可以对上面的构造、产品以及方法作出各种更改，上面的描述中所包含的和各个附图中所示出的所有主题应该解释为说明性的，而不是限制性的。

Claims (15)

1.一种用于获得从中推断移动计算设备(102)的位置的无线接入点的信标基准数据(108)的系统，所述系统包括：
用于存储散列表(106)的存储器区域(116)，所述散列表(106)存储与至少一个信标(104)相关联的信标基准数据(108)，所述信标(104)具有与其相关联的信标标识符，所述散列表(106)通过执行cuckoo散列以便将信标基准数据(108)和信标标识符的校验和存储在散列表(106)中多个潜在位置之一、使得没有其他具有所述校验和的信标标识符被存储在所述多个潜在位置中的所述一个中来创建；以及
处理器(114)，被编程以：
由所述移动计算设备(102)检测所述移动计算设备(102)邻近范围内的信标(104)；
基于所检测的信标(104)的信标标识符来标识存储在所述存储器区域(116)中的散列表(106)中的所述多个潜在位置；
为所标识的多个潜在位置的每一个计算所述信标标识符的校验和；
将所标识的多个潜在位置中的每一个的所计算的校验和与存储在散列表(106)中相应位置处的校验和进行比较，以便在所述多个潜在位置之一处标识匹配；
在存储在所述存储器区域(116)中的散列表(106)中的所述多个位置的所述一个处获得与所计算的校验和相关联的信标基准数据(108)，其中所述移动计算设备(102)基于所获得的信标基准数据(108)来确定所述移动计算设备(102)的位置。
2.如权利要求1所述的系统，其特征在于，所述存储器区域存储多个散列表，其中所述多个散列表中的每一个表示位于地理区域内的一组一个或多个信标。
3.如权利要求1所述的系统，其特征在于，所述散列表存储位于预定义的地理区域内的一个或多个信标的信标基准数据。
4.如权利要求1所述的系统，其特征在于，所述信标基准数据包括以下的一个或多个：经度值、纬度值和海拔值。
5.如权利要求1所述的系统，其特征在于，所述处理器还被编程以便将所获得的信标基准数据与和所述移动计算设备相关联的域信息相比较以确认所述所获得的信标基准数据。
6.如权利要求1所述的系统，还包括基于所获得的信标基准数据来确定所述移动计算设备的位置。
7.如权利要求1所述的系统，还包括用于从cuckoo散列表获得信标的信标基准数据以推断所述移动计算设备的位置的装置。
8.如权利要求1所述的系统，还包括使用信标标识符的校验和从cuckoo散列表获得信标的信标基准数据的装置。
9.一种方法，包括：
访问与信标(104)相关联的数据，所述数据包括信标标识符和描述所述信标(104)的位置的信标基准数据(108)；
由第一计算设备标识散列表(106)中的多个潜在位置以便与所述信标标识符相关联；
为每一个所标识的位置计算所述信标标识符的校验和；
由所述第一计算设备执行cuckoo散列来将信标基准数据(108)和信标标识符的所计算的校验和存储在所述散列表(106)中所标识的多个潜在位置中的一个中；以及
将所述散列表(106)提供给第二计算设备，所述第二计算设备经由所述多个所标识的位置的所述一个中的所计算的校验和从所述散列表检索信标基准数据(108)。
10.如权利要求9所述的方法，其特征在于，访问所述数据包括访问与表示无线接入点小块的多个信标相关联的数据。
11.如权利要求9所述的方法，还包括将所述散列表提供给多个移动计算设备。
12.如权利要求9所述的方法，其特征在于，所述信标标识符包括以下各项的一个或多个：基本服务集标识符(BSSID)和服务集标识符(SSID)。
13.如权利要求9所述的方法，其特征在于，执行cuckoo散列包括查找所述信标标识符和所标识的多个潜在位置之一之间的匹配，使得没有其他信标标识符与所标识的多个潜在位置的所述一个相匹配。
14.如权利要求9所述的方法，其特征在于，标识多个潜在位置包括计算多个散列函数。
15.如权利要求9所述的方法，其特征在于，一种或多种计算机可读介质具有计算机可执行组件，所述组件包括：
在由至少一个处理器执行时使所述至少一个处理器存储多个散列表的存储器组件，所述散列表对应于信标组，每个组表示一地理区域，所述散列表存储描述信标位置的信标基准数据，其中每一个信标具有与其相关联的信标标识符，所述多个散列表通过执行cuckoo散列以便将所述信标基准数据和信标标识符的校验和存储在所述散列表中多个潜在位置之一、使得没有其他具有所述校验和的信标标识符被存储在所述多个潜在位置的所述一个来创建；
在由至少一个处理器执行时使所述至少一个处理器检测计算设备的邻近范围内的一个或多个信标的检测组件；
评级组件，所述评级组件在由至少一个处理器执行时使所述至少一个处理器至少基于所述检测组件所检测的信标、信标覆盖率以及混叠率来为多组信标的每一组计算分数，所述评级组件还基于所计算的分数来选择所述多个散列表中的至少一个；
检索组件，所述检索组件在由至少一个处理器执行时使所述至少一个处理器使用所述信标标识符的校验和，从所述评级组件所选择的散列表中获得与所述检测组件所检测的信标相关联的信标基准数据；以及
在由至少一个处理器执行时使所述至少一个处理器基于所述检索组件所获得的信标基准数据来确定所述计算设备的位置的位置组件。
CN201110072222.0A 2010-03-17 2011-03-16 用于存储信标基准数据的cuckoo散列 Expired - Fee Related CN102170696B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US12/725,840 US8305271B2 (en) 2010-03-17 2010-03-17 Cuckoo hashing to store beacon reference data
US12/725,840 2010-03-17

Publications (2)

Publication Number Publication Date
CN102170696A true CN102170696A (zh) 2011-08-31
CN102170696B CN102170696B (zh) 2014-11-26

Family

ID=44491631

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201110072222.0A Expired - Fee Related CN102170696B (zh) 2010-03-17 2011-03-16 用于存储信标基准数据的cuckoo散列

Country Status (2)

Country Link
US (1) US8305271B2 (zh)
CN (1) CN102170696B (zh)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103425725A (zh) * 2012-05-20 2013-12-04 国际商业机器公司 散列冲突降低系统
CN106416316A (zh) * 2014-04-25 2017-02-15 汤森路透全球资源公司 用于生成基于位置的权限的系统和方法
CN111460510A (zh) * 2020-04-17 2020-07-28 支付宝(杭州)信息技术有限公司 基于隐私保护确定相同业务数据的方法及装置

Families Citing this family (53)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US9035829B2 (en) 2008-09-10 2015-05-19 Nextnav, Llc Wide area positioning systems and methods
US9057606B2 (en) 2009-09-10 2015-06-16 Nextnav, Llc Wide area positioning system
US8917209B2 (en) 2009-09-10 2014-12-23 Nextnav, Llc Coding in a wide area positioning system (WAPS)
CA2736768A1 (en) 2008-09-10 2010-03-18 Commlabs, Inc. Wide area positioning system
US9372266B2 (en) 2009-09-10 2016-06-21 Nextnav, Llc Cell organization and transmission schemes in a wide area positioning system (WAPS)
US9291712B2 (en) 2009-09-10 2016-03-22 Nextnav, Llc Cell organization and transmission schemes in a wide area positioning system (WAPS)
US8700053B2 (en) * 2010-06-11 2014-04-15 Skyhook Wireless, Inc. Systems for and methods of determining likelihood of relocation of reference points in a positioning system
CN103119998B (zh) * 2010-10-06 2016-09-07 索尼移动通信株式会社 用于识别本地信标系统的方法和设备
JP2014519604A (ja) * 2011-05-23 2014-08-14 ワイズ−セック リミテッド 測位システムおよび測位方法、ならびにコンピューティング装置アプリケーションの位置ベースの変更
US9883326B2 (en) * 2011-06-06 2018-01-30 autoGraph, Inc. Beacon based privacy centric network communication, sharing, relevancy tools and other tools
KR101961504B1 (ko) 2011-06-06 2019-03-22 엔플루언스 미디어 인코포레이티드 소비자 주도형 광고 시스템
US9642171B2 (en) * 2011-07-10 2017-05-02 Qualcomm Incorporated Systems and methods for low-overhead wireless beacons having compressed network identifiers
US9176217B2 (en) 2011-08-02 2015-11-03 Nextnav, Llc Cell organization and transmission schemes in a wide area positioning system (WAPS)
US8930307B2 (en) * 2011-09-30 2015-01-06 Pure Storage, Inc. Method for removing duplicate data from a storage array
US8589640B2 (en) 2011-10-14 2013-11-19 Pure Storage, Inc. Method for maintaining multiple fingerprint tables in a deduplicating storage system
CN104081843B (zh) 2011-09-23 2018-04-03 Rx网络股份有限公司 移动设备的基于地理基准的定位
US8923763B2 (en) 2012-02-28 2014-12-30 Qualcomm Incorporated Methods and apparatuses for reducing the nonvolatile memory used to support application identifier routing in an NFC controller
JP2015528099A (ja) * 2012-06-05 2015-09-24 ネクストナヴ，エルエルシー ユーザ装置の測位システムおよび方法
US9306921B2 (en) * 2012-07-31 2016-04-05 Aruba Networks, Inc. Method and system for storing and accessing client device information in a distributed set of nodes
WO2014028060A1 (en) 2012-08-15 2014-02-20 Brian Roundtree Tools for interest-graph driven personalization
CN110233646B (zh) * 2012-09-04 2022-07-01 韩国电子通信研究院 进行扇区训练操作的方法和装置
US9390279B2 (en) 2012-09-11 2016-07-12 Nextnav, Llc Systems and methods for providing conditional access to transmitted information
US9286490B2 (en) 2013-09-10 2016-03-15 Nextnav, Llc Systems and methods for providing conditional access to transmitted information
US10467217B2 (en) * 2013-03-19 2019-11-05 Texas Instruments Incorporated Loop detection in cuckoo hashtables
EP2979108B1 (en) * 2013-03-26 2018-07-25 Nokia Technologies OY Utilizing shortened derivatives of identifiers of entities of communication systems for retrieving positioning information
WO2015007756A1 (en) * 2013-07-18 2015-01-22 Here Global B.V. Method and apparatus for efficiently compressing access point identifiers
GB2516461A (en) * 2013-07-23 2015-01-28 Here Global Bv Method and apparatus for associating information with access points with compressed identifiers
KR20150045073A (ko) * 2013-10-18 2015-04-28 ㈜윈웨이시스템 데이터 운용 방법 및 이를 지원하는 시스템
US9544744B2 (en) * 2013-11-15 2017-01-10 Richard Postrel Method and system for pre and post processing of beacon ID signals
WO2015149032A1 (en) 2014-03-28 2015-10-01 Brian Roundtree Beacon based privacy centric network communication, sharing, relevancy tools and other tools
US9912594B2 (en) * 2014-06-10 2018-03-06 Google Llc Probabilistic message filtering and grouping
US20160019622A1 (en) * 2014-07-18 2016-01-21 Collectors Universe, Inc. System for aggregating, comparing and acquiring collectibles, methods and uses thereof
US10496680B2 (en) 2015-08-17 2019-12-03 Mellanox Technologies Tlv Ltd. High-performance bloom filter array
US9984144B2 (en) 2015-08-17 2018-05-29 Mellanox Technologies Tlv Ltd. Efficient lookup of TCAM-like rules in RAM
US10049126B2 (en) * 2015-09-06 2018-08-14 Mellanox Technologies Tlv Ltd. Cuckoo hashing with selectable hash
US10222987B2 (en) 2016-02-11 2019-03-05 Dell Products L.P. Data deduplication with augmented cuckoo filters
US10285054B2 (en) 2016-03-18 2019-05-07 Hewlett Packard Enterprise Development Lp Method and system for storing and accessing client device information in a distributed set of nodes
US9892057B2 (en) 2016-03-31 2018-02-13 Mellanox Technologies Tlv Ltd. Single double cuckoo hash
US10594787B2 (en) 2016-04-12 2020-03-17 Disney Enterprises, Inc. System and method for presence or proximity-based sorting
US10068034B2 (en) 2016-09-07 2018-09-04 Mellanox Technologies Tlv Ltd. Efficient matching of TCAM rules using hash tables in RAM
US10491521B2 (en) 2017-03-26 2019-11-26 Mellanox Technologies Tlv Ltd. Field checking based caching of ACL lookups to ease ACL lookup search
US11113159B2 (en) * 2017-06-30 2021-09-07 Intel Corporation Log structure with compressed keys
US10476794B2 (en) 2017-07-30 2019-11-12 Mellanox Technologies Tlv Ltd. Efficient caching of TCAM rules in RAM
EP3769568B1 (en) 2018-03-20 2022-11-02 HERE Global B.V. Positioning of low power devices
US11327974B2 (en) 2018-08-02 2022-05-10 Mellanox Technologies, Ltd. Field variability based TCAM splitting
US11003715B2 (en) 2018-09-17 2021-05-11 Mellanox Technologies, Ltd. Equipment and method for hash table resizing
US11455318B2 (en) 2019-02-19 2022-09-27 Microsoft Technology Licensing, Llc Data replication using probabilistic replication filters
US10944675B1 (en) 2019-09-04 2021-03-09 Mellanox Technologies Tlv Ltd. TCAM with multi region lookups and a single logical lookup
US11539622B2 (en) 2020-05-04 2022-12-27 Mellanox Technologies, Ltd. Dynamically-optimized hash-based packet classifier
US11782895B2 (en) 2020-09-07 2023-10-10 Mellanox Technologies, Ltd. Cuckoo hashing including accessing hash tables using affinity table
US11917042B2 (en) 2021-08-15 2024-02-27 Mellanox Technologies, Ltd. Optimizing header-based action selection
US11929837B2 (en) 2022-02-23 2024-03-12 Mellanox Technologies, Ltd. Rule compilation schemes for fast packet classification
US11968285B2 (en) 2022-02-24 2024-04-23 Mellanox Technologies, Ltd. Efficient memory utilization for cartesian products of rules

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020080063A1 (en) * 2000-12-26 2002-06-27 Ericsson Inc. Mobile terminal and system and method for determining the geographic location of a mobile terminal
US20080228691A1 (en) * 2007-03-12 2008-09-18 Shavit Nir N Concurrent extensible cuckoo hashing
US20090016219A1 (en) * 2007-07-10 2009-01-15 Qualcomm Incorporated APPARATUS AND METHOD OF GENERATING AND MAINTAINING ORTHOGONAL CONNECTION IDENTIFICATIONS (CIDs) FOR WIRELESS NETWORKS

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20050187898A1 (en) * 2004-02-05 2005-08-25 Nec Laboratories America, Inc. Data Lookup architecture
US7650429B2 (en) * 2005-02-04 2010-01-19 Cisco Technology, Inc. Preventing aliasing of compressed keys across multiple hash tables
JP2008532177A (ja) * 2005-03-03 2008-08-14 ワシントン ユニヴァーシティー 生物学的配列類似検索を実行するための方法および装置

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20020080063A1 (en) * 2000-12-26 2002-06-27 Ericsson Inc. Mobile terminal and system and method for determining the geographic location of a mobile terminal
US20080228691A1 (en) * 2007-03-12 2008-09-18 Shavit Nir N Concurrent extensible cuckoo hashing
US20090016219A1 (en) * 2007-07-10 2009-01-15 Qualcomm Incorporated APPARATUS AND METHOD OF GENERATING AND MAINTAINING ORTHOGONAL CONNECTION IDENTIFICATIONS (CIDs) FOR WIRELESS NETWORKS

Cited By (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN103425725A (zh) * 2012-05-20 2013-12-04 国际商业机器公司 散列冲突降低系统
CN103425725B (zh) * 2012-05-20 2017-04-12 国际商业机器公司 散列冲突降低系统
CN106416316A (zh) * 2014-04-25 2017-02-15 汤森路透全球资源公司 用于生成基于位置的权限的系统和方法
CN106416316B (zh) * 2014-04-25 2020-01-07 汤森路透全球资源无限公司 在ble协议下提供安全措施的系统、方法和计算机可读媒体
CN111460510A (zh) * 2020-04-17 2020-07-28 支付宝(杭州)信息技术有限公司 基于隐私保护确定相同业务数据的方法及装置

Also Published As

Publication number Publication date
US20110227790A1 (en) 2011-09-22
CN102170696B (zh) 2014-11-26
US8305271B2 (en) 2012-11-06

Similar Documents

Publication Publication Date Title
CN102170696B (zh) 用于存储信标基准数据的cuckoo散列
US11231479B2 (en) Frequency channel diversity for real-time locating systems, methods, and computer program products
US8618984B2 (en) Selecting beacons for location inference
US7969348B2 (en) Systems and methods for obtaining and using data from a localized location and telemetry system in a wide area location and telemetry system
US8058988B1 (en) Systems and methods for wireless object tracking
US8866674B2 (en) Concept of generating experience messages for updating a reference database
US20140118113A1 (en) Detecting rogue radio frequency based tags based on locationing
US10210356B2 (en) Multi signal diffusion integrated system and method
CN105848099B (zh) 识别地理围栏的方法、系统、服务器及移动终端
US20110205125A1 (en) Inferring beacon positions based on spatial relationships
CN103596199A (zh) 向移动站提供基站历书
EP3852487A1 (en) Beacon addressing
JP6238446B2 (ja) 少なくとも一つのアクセスポイントを有する無線ネットワークを備えた環境で無線デバイスの位置を特定する方法
US20140171104A1 (en) Mobile Communication System
CN104080043A (zh) 兴趣点的位置信息的校正方法及设备
CN102918899A (zh) 用于定位pCell的数据库更新方法和设备
CN113709859A (zh) 一种定位方法、装置、设备和计算机可读存储介质
Cheng et al. A New Three‐Dimensional Indoor Positioning Mechanism Based on Wireless LAN
Rahimi et al. Indoor geo-fencing and access control for wireless networks
CN104936285A (zh) 一种wifi定位方法及装置
JP2014052208A (ja) 位置推定装置、位置推定システム、および、位置推定方法
TW202135548A (zh) 使用無線保真(Wi-Fi)存取點之觀測進行的被動感測器追蹤
Mok et al. A study on the use of Wi-Fi positioning technology for wayfinding in large shopping centers
JP5942404B2 (ja) 情報解析装置、情報解析方法及びプログラム
KR101466514B1 (ko) 위치 측위 방법 및 그 장치

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
C14 Grant of patent or utility model
GR01 Patent grant
ASS Succession or assignment of patent right

Owner name: MICROSOFT TECHNOLOGY LICENSING LLC

Free format text: FORMER OWNER: MICROSOFT CORP.

Effective date: 20150429

C41 Transfer of patent application or patent right or utility model
TR01 Transfer of patent right

Effective date of registration: 20150429

Address after: Washington State

Patentee after: Micro soft technique license Co., Ltd

Address before: Washington State

Patentee before: Microsoft Corp.

CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20141126

Termination date: 20210316

CF01 Termination of patent right due to non-payment of annual fee