用于广告中的服务提示信息的布隆过滤器

摘要

本公开的某些方面通常涉及使用布隆过滤器哈希函数用于诸如信标和探测响应的广告中的服务提示信息。某些方面提供用于无线通信的装置，例如接入点(AP)。该装置通常包括处理系统，其被配置为生成指示由装置所知的一个或多个服务的多个位图，每个位图是通过将不同的一组一个或多个基于循环冗余校验(CRC)的哈希函数应用于每个服务的一个或多个服务标识(ID)来生成的，以及被配置为生成一个或多个帧，每个帧包括多个位图中的一个位图、以及对用于生成在所述帧中包括的所述位图的一组一个或多个基于CRC的哈希函数的指示；以及接口，被配置为输出所述一个或多个帧用于传输。

说明书

相关申请的交叉引用

本申请要求享受2015年9月22日提交的美国专利申请14/861,325的优先权，该专利申请要求享受2014年10月17日提交的美国临时专利申请序列号62/065,001的优先权，其全部内容通过引用并入本文。

技术领域

本公开内容的某些方面通常涉及无线通信，并且具体地涉及使用布隆过滤器哈希函数用于诸如信标和探测响应的广告中的服务提示信息(service hint information)。

背景技术

无线通信网络被广泛部署以提供诸如语音、视频、分组数据、消息收发、广播等的各种通信服务。这些无线网络可以是能够通过共享可用网络资源来支持多个用户的多址网络。这种多址网络的示例包括码分多址(CDMA)网络、时分多址(TDMA)网络、频分多址(FDMA)网络、正交FDMA(OFDMA)网络和单载波FDMA(SC-FDMA)网络。

通常，无线多址通信系统可以同时支持多个无线终端的通信。每个终端经由前向链路和反向链路上的传输与一个或多个基站进行通信。前向链路(或下行链路)是指从基站到终端的通信链路，反向链路(或上行链路)是指从终端到基站的通信链路。该通信链路可以通过单输入单输出、多输入单输出或多输入多输出(MIMO)系统建立。

为了解决对于更广泛的覆盖和增加的通信范围的期望，正在开发各种方案。一个这样的方案是由电气和电子工程师协会(IEEE)802.11ah工作组开发的亚1GHz频率范围(例如，在美国的902-928MHz范围内工作)。这种发展是由对利用具有比与其它IEEE 802.11技术的频率范围相关联的无线范围更大的无线范围的频率范围的期望以及与由于障碍引起的路径损耗相关联的潜在较少的问题驱使的。

发明内容

本公开内容的系统、方法和装置各自具有几个方面，其中没有一个单独的方面仅仅负责其期望的属性。在不限制本公开内容的由所附权利要求书表示的范围的情况下，现在将简要讨论一些特征。在考虑这一讨论之后，特别是在阅读了“具体实施方式”一节之后，技术人员将会理解本公开内容的特征如何提供包括无线网络中的接入点和站之间的改进通信的优点。

本公开内容的某些方面通常涉及对于诸如信标和探测响应的广告中的服务提示信息使用布隆过滤器哈希函数。

本公开内容的某些方面提供了一种用于无线通信的装置。该装置通常包括：处理系统，被配置为：生成指示由所述装置所知的一个或多个服务的多个位图，每个位图是通过将不同的一组一个或多个基于循环冗余校验(CRC)的哈希函数应用于每个服务的一个或多个服务标识(ID)来生成的，以及生成一个或多个帧，每个帧包括所述多个位图中的一个位图、以及对用于生成在所述帧中包括的所述位图的所述一组一个或多个基于CRC的哈希函数的指示；以及接口，被配置为输出所述一个或多个帧用于传输。

本公开内容的某些方面提供了一种用于无线通信的装置。该装置通常包括：接口，被配置为从另一装置获得帧，所述帧包括指示由所述另一装置所知的一个或多个服务的位图、以及对用于生成在所述帧中包括的所述位图的一组一个或多个基于CRC的哈希函数的指示；以及处理系统，被配置为：通过将所指示的一组一个或多个基于CRC的哈希函数应用于所述装置所期望的服务的一个或多个服务ID来确定位图位置，比较所确定的位图位置和在所述帧中包括的所述位图的位图位置，以及如果所述比较指示关于所述装置所期望的服务由所述另一装置所知的概率则与所述另一装置相关联、或者如果所述比较指示所述一个或多个服务不由所述另一装置所知则避免与所述另一装置相关联。

本公开内容的某些方面提供了一种由装置用于无线通信的方法。该方法通常包括：生成指示由所述装置所知的一个或多个服务的多个位图，每个位图是通过将不同的一组一个或多个基于CRC的哈希函数应用于每个服务的一个或多个服务ID来生成的；生成一个或多个帧，每个帧包括所述多个位图中的一个位图、以及对用于生成在所述帧中包括的所述位图的所述一组一个或多个基于CRC的哈希函数的指示；以及输出所述一个或多个帧用于传输。

本公开内容的某些方面提供了一种由装置用于无线通信的方法。该方法通常包括：从另一装置获得帧，所述帧包括指示由所述另一装置所知的一个或多个服务的位图、以及对用于生成在所述帧中包括的所述位图的一组一个或多个基于CRC的哈希函数的指示，通过将所指示的一组一个或多个基于CRC的哈希函数应用于所述装置所期望的服务的一个或多个服务ID来确定位图位置，比较所确定的位图位置和在所述帧中包括的所述位图的位图位置，以及如果所述比较指示关于所述装置所期望的服务由所述另一装置所知的概率则与所述另一装置相关联、或者如果所述比较指示所述一个或多个服务不由所述另一装置所知则避免与所述另一装置相关联。

本公开内容的某些方面提供了一种用于无线通信的装置。该装置通常包括：用于生成指示由所述装置所知的一个或多个服务的多个位图的单元，每个位图是通过将不同的一组一个或多个基于CRC的哈希函数应用于每个服务的一个或多个服务ID来生成的；用于生成一个或多个帧的单元，每个帧包括所述多个位图中的一个位图、以及对用于生成在所述帧中包括的所述位图的所述一组一个或多个基于CRC的哈希函数的指示；以及用于输出所述一个或多个帧用于传输的单元。

本公开内容的某些方面提供了一种用于无线通信的装置。该装置通常包括：用于从另一装置获取帧的单元，所述帧包括指示由所述另一装置所知的一个或多个服务的位图、以及对用于生成在所述帧中包括的所述位图的一组一个或多个基于CRC的哈希函数的指示；用于通过将所指示的一组一个或多个基于CRC的哈希函数应用于所述装置所期望的服务的一个或多个服务ID来确定位图位置的单元；用于比较所确定的位图位置和在所述帧中包括的所述位图的位图位置的单元；以及用于如果所述比较指示关于所述装置所期望的服务由所述另一装置所知的概率则与所述另一装置相关联、或者如果所述比较指示所述一个或多个服务不由所述另一装置所知则避免与所述另一装置相关联的单元。

本公开内容的某些方面提供了一种计算机可读介质。计算机可读介质通常包括存储在其上的计算机可执行代码，用于：在装置处生成指示由所述装置所知的一个或多个服务的多个位图，每个位图是通过将不同的一组一个或多个基于CRC的哈希函数应用于每个服务的一个或多个服务ID来生成的；生成一个或多个帧，每个帧包括所述多个位图中的一个位图、以及对用于生成在所述帧中包括的所述位图的所述一组一个或多个基于CRC的哈希函数的指示；以及输出所述一个或多个帧用于传输。

本公开内容的某些方面提供计算机可读介质。计算机可读介质通常包括存储在其上的计算机可执行代码，用于：从另一装置获取帧，所述帧包括指示由所述另一装置所知的一个或多个服务的位图、以及对用于生成在所述帧中包括的所述位图的一组一个或多个基于CRC的哈希函数的指示；通过将所指示的一组一个或多个基于CRC的哈希函数应用于所述装置所期望的服务的一个或多个服务ID来确定位图位置；比较所确定的位图位置和在所述帧中包括的所述位图的位图位置；以及如果所述比较指示关于所述装置所期望的服务由所述另一装置所知的概率则与所述另一装置相关联、或者如果所述比较指示所述一个或多个服务不由所述另一装置所知则避免与所述另一装置相关联。

本公开内容的某些方面提供接入点(AP)。所述AP通常包括：至少一个天线；处理系统，被配置为生成指示由所述AP所知的一个或多个服务的多个位图，每个位图是通过将不同的一组一个或多个基于CRC的哈希函数应用于每个服务的一个或多个服务ID来生成的，以及生成一个或多个帧，每个帧包括所述多个位图中的一个位图、以及对用于生成在所述帧中包括的所述位图的所述一组一个或多个基于CRC的哈希函数的指示；以及发射机，被配置为经由所述至少一个天线发送所述一个或多个帧。

本公开内容的某些方面提供接入终端。所述接入终端通常包括：至少一个天线；接收机，被配置为经由所述至少一个天线从AP接收帧，所述帧包括指示由所述AP所知的一个或多个服务的位图、以及对用于生成在所述帧中包括的所述位图的一组一个或多个基于CRC的哈希函数的指示；以及处理系统，被配置为：通过将所指示的一组一个或多个基于CRC的哈希函数应用于所述接入终端所期望的服务的一个或多个服务ID来确定位图位置，比较所确定的位图位置和在所述帧中包括的所述位图的位图位置，以及如果所述比较指示关于所述接入终端所期望的服务由所述AP所知的概率则与所述AP相关联、或者如果所述比较指示所述一个或多个服务不由所述AP所知则避免与所述AP相关联。

为了实现前述和相关目的，所述一个或多个方面包括下面充分描述并在权利要求书中特别指出的特征。以下描述和附图详细阐述了一个或多个方面的某些说明性特征。然而，这些特征仅仅是可以采用各个方面的原理的各种方式中的一些，并且该描述旨在包括所有这些方面及其等同物。

附图说明

图1示出了根据本公开内容的某些方面的示例性无线通信网络的图。

图2示出了根据本公开内容的某些方面的示例接入点和用户终端的框图。

图3示出了根据本公开内容的某些方面的示例无线设备的框图。

图4示出了根据本公开内容的某些方面的服务提示信息元素(IE)的示例性帧格式。

图4A示出了根据本公开内容的某些方面的可以在服务提示IE的字段中指示的多组示例布隆过滤器哈希函数。

图4B示出了根据本公开内容的某些方面的图5所示的示例性服务提示信息IE的示例性布隆过滤器信息字段子字段。

图5示出了根据本公开内容的某些方面的由接入点(AP)用于无线通信的示例操作的框图。

图5A示出能够执行图5所示的操作的示例性单元。

图6示出了根据本公开内容的某些方面的由站(STA)用于无线通信的示例操作的框图。

图6A示出能够执行图6所示的操作的示例性单元。

具体实施方式

在下文中将参照附图更全面地描述本公开内容的各个方面。然而，本公开内容可以以许多不同的形式实施，并且不应被解释为限于在本公开内容中呈现的任何具体结构或功能。而是，这些方面被提供，使得本公开内容将是彻底和完整的，并且将向本领域技术人员充分地传达本公开内容的范围。基于本文的教导，一名本领域技术人员应当理解，本公开内容的范围旨在涵盖本文公开的本公开内容的任何方面，而无论是独立于或结合本公开内容的任何其它方面实现。例如，可以使用本文所阐述的任何数量的方面来实现装置或者来实施方法。此外，本公开内容的范围旨在覆盖除了本文所阐述的本公开内容的各个方面之外或除了本文所阐述的本公开内容的各个方面之外的，使用其它结构、功能或结构和功能来实践的这种装置或方法。应当理解，本文公开的本公开内容的任何方面可以由权利要求书的一个或多个要素体现。

本公开内容的某些方面通常涉及使用布隆过滤器哈希函数用于诸如信标和探测响应的广告中的服务提示信息。接入点(AP)可以通过将不同组的哈希函数(例如，CRC32哈希函数)应用于每个服务的服务标识(ID)来生成指示由AP所知的服务的多个不同的位图。AP可以将位图发送给站(STA)连同对用于生成位图的一组哈希函数的指示。接收到帧的STA可以将该组哈希函数应用于STA所期望的服务的服务ID以计算位图位置。通过将所计算的位图位置与从AP接收到的帧中的位图进行比较，STA可以确定是否存在关于期望服务可用的高概率，并且可以基于该确定来决定是否与AP相关联。词语“示例性”在本文中用于表示“用作示例、实例或说明”。本文描述为“示例性”的任何方面不必被解释为比其它方面优选或有利。

尽管本文描述了特定方面，但是这些方面的许多变化和排列都在本公开内容的范围内。虽然提及了优选方面的一些益处和优点，但是本公开内容的范围并不旨在限于特定的益处、用途或目的。而是，本公开内容的方面旨在广泛地应用于不同的无线技术、系统配置、网络和传输协议，其中一些在附图中以示例并在优选方面的以下描述中示出。具体实施方式和附图仅仅是对本公开内容的说明而不是限制，本发明的范围由所附权利要求书及其等同物限定。

本文描述的技术可以用于各种无线通信网络，例如，码分多址(CDMA)网络、时分多址(TDMA)网络、频分多址(FDMA)网络、正交FDMA(OFDMA)网络、单载波FDMA(SC-FDMA)网络等。术语“网络”和“系统”通常可互换使用。CDMA网络可以实现诸如通用陆地无线电接入(UTRA)、CDMA2000等的无线电技术。UTRA包括宽带CDMA(W-CDMA)和低码片速率(LCR)。CDMA2000涵盖IS-2000、IS-95和IS-856标准。TDMA网络可以实现诸如全球移动通信系统(GSM)的无线电技术。OFDMA网络可以实现诸如演进UTRA(E-UTRA)、IEEE 802.11、IEEE 802.16、IEEE 802.20、等的无线电技术。UTRA、E-UTRA和GSM是通用移动电信系统(UMTS)的部分。长期演进(LTE)是即将推出的使用E-UTRA的UMTS版本。UTRA、EUTRA、GSM、UMTS和LTE在来自名为“第三代合作伙伴计划”(3GPP)的组织的文档中被描述。在来自名为“第三代合作伙伴计划2”(3GPP2)的组织的文档中描述了CDMA2000。

单载波频分多址(SC-FDMA)是在发射机侧利用单载波调制和在接收机侧进行频域均衡的传输技术。SC-FDMA技术具有与OFDMA系统相似的性能和基本上相同的总体复杂度。然而，由于其固有的单载波结构，SC-FDMA信号具有较低的峰均功率比(PAPR)。SC-FDMA技术引起了人们的极大关注，特别是在传输功率效率方面，较低的PAPR对移动终端的益处较大。目前，使用SC-FDMA是3GPP LTE和演进型UTRA中的上行链路多址方案的工作设想。

接入点(“AP”)可以包括、被实现为或称为节点B、无线电网络控制器(“RNC”)、e节点B、基站控制器(“BSC”)、基站收发机站(“BTS”)、基站(“BS”)、收发机功能体(“TF”)、无线电路由器、无线电收发机、基本服务集(“BSS”)、扩展服务集(“ESS”)、无线电基站(“RBS“)或其它某个术语。

接入终端(“AT”)可以包括、实现为或称为接入终端、订户站、订户单元、移动站、远程站、远程终端、用户终端、用户代理、用户设备、用户装置、用户站或某个其它术语。在一些实现中，接入终端可以包括蜂窝电话、无绳电话、会话发起协议(“SIP”)电话、无线本地环路(“WLL”)站、个人数字助理(“PDA”)、具有无线连接能力的手持设备、站(“STA”)或连接到无线调制解调器的某个其它合适的处理设备。因此，本文教导的一个或多个方面可以并入到电话(例如，蜂窝电话或智能电话)、计算机(例如，膝上型计算机)、便携式通信设备、便携式计算设备(例如，个人数据助理)、娱乐设备(例如，音乐或视频设备或卫星无线电)、全球定位系统设备或被配置为经由无线或有线介质进行通信的任何其它合适的设备。在一些方面，节点是无线节点。这样的无线节点可以经由有线或无线通信链路提供例如对于或去往网络(例如，诸如因特网或蜂窝网络的广域网)的连接。

示例无线通信系统

图1示出了可以执行本公开内容的各方面的系统100。例如，接入点110可以使用布隆过滤器来在广告中提供服务提示信息。用户终端120可以接收服务提示信息，并基于可用服务来确定是否与接入点110相关联。

系统100可以是例如具有接入点和用户终端的多址多输入多输出(MIMO)系统100。为了简单起见，图1中仅示出了一个接入点110。接入点通常是与用户终端通信的固定站，也可以称为基站或某个其它术语。用户终端可以是固定的或移动的，并且也可以被称为移动站、无线设备或某个其它术语。接入点110可以在下行链路和上行链路上在任何给定时刻与一个或多个用户终端120进行通信。下行链路(即前向链路)是从接入点到用户终端的通信链路，上行链路(即反向链路)是从用户终端到接入点的通信链路。用户终端还可以与另一用户终端进行对等通信。系统控制器130耦合到接入点并提供对接入点的协调和控制。

系统控制器130可以为这些AP和/或其它系统提供协调和控制。AP可以由系统控制器130管理，例如，系统控制器130可以处理对射频功率、信道、认证和安全性的调整。系统控制器130可以经由回程与AP通信。AP还可以例如通过无线或有线回程直接或间接地彼此通信。

虽然以下公开的部分将描述能够经由空分多址(SDMA)通信的用户终端120，但是对于某些方面，用户终端120还可以包括不支持SDMA的一些用户终端。因此，对于这些方面，AP 110可以被配置为与SDMA和非SDMA用户终端进行通信。这种方法可以方便地允许旧版本的用户终端(“传统”站)在企业中保持部署，这延长了其使用寿命，同时允许在适当的情况下引入较新的SDMA用户终端。

接入点110和用户终端120在下行链路和上行链路上使用多个发射和多个接收天线进行数据传输。对于下行链路MIMO传输，接入点110的N_ap个天线表示MIMO的多输入(MI)部分，而一组K个用户终端表示MIMO的多输出(MO)部分。相反，对于上行链路MIMO传输，该组K个用户终端表示MI部分，而接入点110的N_ap个天线表示MO部分。对于纯SDMA，期望在对于K个用户终端的数据符号流通过某种方式而不以码、频率或时间来复用时使得N_ap≥K≥1。当数据符号流可以使用TDMA技术、CDMA的不同码信道、OFDM的不相交子带集等等来复用时，K可以大于N_ap。每个选择的用户终端向接入点发射用户特定的数据和/或从接入点接收用户特定的数据。通常，每个选择的用户终端可以配备有一个或多个天线(即，N_ut≥1)。K个选择的用户终端可以具有相同或不同数量的天线。

系统100可以是时分双工(TDD)系统或频分双工(FDD)系统。对于TDD系统，下行链路和上行链路共享相同的频带。对于FDD系统，下行链路和上行链路使用不同的频带。MIMO系统100还可以使用单个载波或多个载波进行传输。每个用户终端可以配备单个天线(例如，为了保持成本低)或多个天线(例如，在可以支持额外的成本时)。如果用户终端120通过将发射/接收划分到不同的时隙来共享相同的频道，其中每个时隙被分配给不同的用户终端120，则系统100也可以是TDMA系统。

图2示出了图1所示的AP 110和UT 120的示例组件，其可以用于实现本公开内容的各方面。可以使用AP 110和UT 120的一个或多个组件来实施本公开内容的各方面。例如，可以使用天线224、Tx/Rx 222、处理器210、220、240、242和/或控制器230来执行本文所描述的并参照图5-5A进行说明的操作。类似地，UT 120的天线252、Tx/Rx 254、处理器260、270、288和290、和/或控制器280可以用于执行本文所述的并参照图6-6A进行说明的操作。

图2示出了MIMO系统100中的接入点110和两个用户终端120m和120x的框图。接入点110配备有N_t个天线224a至224t。用户终端120m配备N_ut,m个天线252ma至252mu，用户终端120x配备N_ut,x个天线252xa至252xu。接入点110是用于下行链路的发射实体和用于上行链路的接收实体。每个用户终端120是用于上行链路的发射实体和用于下行链路的接收实体。如本文所使用地，“发射实体”是能够经由无线信道发射数据的独立操作的装置或设备，并且“接收实体”是能够经由无线信道接收数据的独立操作的装置或设备。在下面的描述中，下标“dn”表示下行链路，下标“up”表示上行链路，N_up个用户终端被选择用于在上行链路上同时传输，N_dn个用户终端被选择用于下行链路上的同时传输，N_up可以或可以不等于N_dn，并且N_up和N_dn可以是静态值、或者可以针对每个调度间隔而改变。可以在接入点和用户终端处使用波束转向或某个其它空间处理技术。

在上行链路上，在用于上行链路传输的每个用户终端120处，发射(TX)数据处理器288从数据源286接收业务数据、以及接收来自控制器280的控制数据。控制器280可以与存储器282耦合。TX数据处理器288基于与为用户终端选择的速率相关联的编码和调制方案处理(例如，编码、交织和调制)用户终端的业务数据，并提供数据符号流。TX空间处理器290对数据符号流执行空间处理并提供N_ut,m个天线的N_ut,m个发射符号流。每个发射机单元(TMTR)254接收并处理(例如，转换成模拟、放大、滤波和上变频)相应的发射符号流以产生上行链路信号。N_ut,m个发射机单元254提供用于从N_ut,m个天线252到接入点的传输的N_ut,m个上行链路信号。

可以调度N_up个用户终端以在上行链路上同时传输。这些用户终端中的每一个对其数据符号流执行空间处理，并且在上行链路上将其发射符号流集合发送到接入点。

在接入点110处，N_ap个天线224a至224ap接收来自在上行链路上发射的所有N_up个用户终端的上行链路信号。每个天线224将接收到的信号提供给相应的接收机单元(RCVR)222。每个接收机单元222执行与由发射机单元254执行的处理互补的处理，并提供接收的符号流。RX空间处理器240对来自N_ap个接收机单元222的N_ap个接收到的符号流执行接收机空间处理，并提供N_up个恢复的上行链路数据符号流。根据信道相关矩阵逆(CCMI)、最小均方误差(MMSE)、软干扰消除(SIC)或其它某个技术来执行接收机空间处理。每个恢复的上行链路数据符号流是对由相应的用户终端发送的数据符号流的估计。RX数据处理器242根据用于每个恢复的上行链路数据符号流的速率来处理(例如，解调、解交织和解码)该流以获得解码数据。每个用户终端的解码数据可以被提供给用于存储的数据宿244和/或用于进一步处理的控制器230。控制器230可以与存储器232耦合。

在下行链路上，在接入点110处，TX数据处理器210从调度用于下行链路传输的针对N_dn个用户终端的数据源208接收业务数据，从控制器230接收控制数据，以及从调度器234接收可能的其它数据。各种类型的数据可以在不同的传输信道上发送。TX数据处理器210基于为该用户终端选择的速率处理(例如，编码、交织和调制)每个用户终端的业务数据。TX数据处理器210为N_dn个用户终端提供N_dn个下行链路数据符号流。TX空间处理器220对N_dn个下行链路数据符号流执行空间处理(诸如本公开内容中所描述的预编码或波束成形)，并且为N_ap个天线提供N_ap个发射符号流。每个发射机单元222接收并处理相应的发射符号流以产生下行链路信号。N_ap个发射机单元222提供用于从N_ap个天线224传输到用户终端的N_ap个下行链路信号。

在每个用户终端120处，N_ut,m个天线252接收来自接入点110的N_ap个下行链路信号。每个接收机单元254处理来自相关的天线252的接收信号并提供接收的符号流。RX空间处理器260对来自N_ut,m个接收机单元254的N_ut,m个接收符号流执行接收机空间处理，并为用户终端提供恢复的下行链路数据符号流。根据CCMI、MMSE或其它某个技术来执行接收机空间处理。RX数据处理器270处理(例如，解调、解交织和解码)恢复的下行链路数据符号流，以获得用户终端的解码数据。每个用户终端的解码数据可以被提供给用于存储的数据宿272和/或用于进一步处理的控制器280。

在每个用户终端120处，信道估计器278估计下行链路信道响应并提供下行链路信道估计，其可以包括信道增益估计、SNR估计、噪声方差等。类似地，在接入点110处，信道估计器228估计上行链路信道响应并提供上行链路信道估计。对于每个用户终端的控制器280通常基于用户终端的下行链路信道响应矩阵Hdn,m导出用户终端的空间滤波器矩阵。控制器230基于有效的上行链路信道响应矩阵Hup,eff导出接入点的空间滤波器矩阵。每个用户终端的控制器280可以向接入点发送反馈信息(例如，下行链路和/或上行特征向量、特征值、SNR估计等)。控制器230和280还分别控制接入点110和用户终端120处的各种处理单元的操作。

图3示出了可以在AP 110和/或UT 120中使用以实现本公开内容的各方面的示例组件。例如，发射机310、天线316、处理器304和/或DSP 320可以用于实施由AP实现的本公开内容的各方面。此外，接收机312、天线316、处理器304和/或DSP 320可以用于实施由UT实现的本公开内容的方面。

无线设备302可以包括控制无线设备302的操作的处理器304。处理器304也可以被称为中央处理单元(CPU)。可以包括只读存储器(ROM)和随机存取存储器(RAM)的存储器306向处理器304提供指令和数据。存储器306的一部分还可以包括非易失性随机存取存储器(NVRAM)。处理器304通常基于存储在存储器306内的程序指令执行逻辑和算术运算。存储器306中的指令可以是可执行的，以实现本文描述的方法。

无线设备302还可以包括壳体308，其可以包括发射机310和接收机312，以允许无线设备302和远程位置之间的数据的发送和接收。发射机310和接收机312可以组合成收发机314。单个或多个发射天线316可以附接到壳体308并且电耦合到收发机314。无线设备302还可以包括(未示出)多个发射机、多个接收机和多个收发机。

无线设备302还可以包括信号检测器318，其可以用于尝试检测和量化由收发机314接收的信号的电平。信号检测器318可以检测这样的信号，诸如总能量、每子载波每符号的能量、功率谱密度和其它信号。无线设备302还可包括用于处理信号的数字信号处理器(DSP)320。

除了数据总线之外，无线设备302的各种组件可以由总线系统322耦合在一起，总线系统322可以包括电源总线、控制信号总线和状态信号总线。

UE可以通过执行通常包括被动扫描和主动扫描的如在电气和电子工程师协会(IEEE)规范IEEE 802.11中规定的扫描过程来知悉AP。例如如IEEE 802.11所定义的被动扫描对于UE而言是低效的，因为其上具有接收机的该UE等待对AP信标的接收。由于信标传输间隔大约为几百毫秒，这可能由于数十个信道要进行扫描而导致高扫描能量和高扫描延迟。主动扫描可能会更快，但会增加到网络的业务，例如探测请求和探测响应。主动扫描也耗电。

IEEE 802.11u已经定义了供UE发现关于AP的更多信息而不与AP相关联的额外机制。例如，通用广告服务(GAS)可以在UE和网络中的服务器之间传送广告协议的帧。AP可以负责将移动设备的查询中继给运营商网络中的服务器，并将服务器的响应传递回给移动设备。供UE发现关于AP的信息而不与AP相关联的另一示例性机制是服务发现协议，例如，在Wi-Fi的情况下的接入网络查询协议(ANQP)，其通常是由UE/STA用于接入网络信息获取的查询广告协议。在Wi-Fi的情况下，ANQP可以通过GAS传输。ANQP可以包括Hotspot运营商的域名、可通过热点访问的漫游合作伙伴连同其针对认证所支持的凭证类型和可扩展身份认证协议(EAP)方法、IP地址类型可用性、以及UE网络选择过程中有用的其它元数据。

IEEE 802.11aq扩展了IEEE 802.11u的一些机制以实现对由AP提供的服务的预关联发现(PAD)。

用于广告中的服务提示信息的示例布隆过滤器

互通通常是指无线设备(例如，Wi-Fi设备)在加入之前了解在网络中提供的服务的能力。可以实现互通的一种机制是服务的预关联发现(PAD)。

PAD允许诸如接入终端(AT)(例如，AT 250)的站点在与AP关联之前发现网络中的关于由网络(例如，由接入点(AP)(例如，AP 210))提供的服务的服务信息。AP可以例如在发送到STA或被广播的诸如信标、探测响应或通用广告服务(GAS)的广告中指示可用的服务。STA可以基于如下来确定与AP相关联：期望的服务是否由AP所知(例如由AP或另一个STA提供/支持)，这可以被STA基于在来自AP的广播中接收到的信息而知道。

通常，服务信息可以根据请求或未经请求的PAD协议来提供。在未经请求的PAD协议中，基本服务信息可以被包括在由AP发射的信标和/或广播帧(例如，PADP服务公告)中。在接收到信标和/或广播帧时，非AP STA可以做出要与AP关联、或者要在关联之前(例如，通过发送PADP服务信息请求并接收PADP服务信息响应)查询更详细的服务信息的明智决定。

在请求的PAD协议中，基本服务信息可以包括在由非AP STA发送的探测请求中。例如，探测请求可以包括包含一个或多个服务哈希的服务哈希元素。服务哈希可以是全局唯一地标识服务的唯一服务标识符(USID)的短标识符(48位)。在接收到探测请求时，仅当非AP STA的探测请求中包含的服务与AP支持的服务之间存在服务匹配(例如，通过比较哈希)时，AP才用探测响应进行响应。基于非AP STA是否接收到探测响应或者在接收到探测响应时，非AP STA可以做出要与AP相关联、或要在关联之前(例如，通过发送PADP服务信息请求并接收PADP服务信息响应)查询更详细的服务信息的明智决定。

然而，由于越来越多的可用服务，简单地在广告(例如，信标、探测响应、广播帧或GAS)中携带服务名称可能不可扩展。因此，可能期望用于指示潜在大量的可用服务的压缩方法。

本文描述的技术和装置提供可扩展的服务提示信息元素(IE)。根据某些方面，提示IE携带被指示为比特位置的利用服务标识符(ID)的布隆过滤器(例如位图)、以及指示用于生成该位图的一组哈希函数(例如，CRC32哈希函数)的布隆过滤器IE。

根据某些方面，AP可以生成指示由AP提供的服务的多个不同的位图，这通过将不同组的哈希函数应用于每个服务的服务ID来实现。AP可以将位图连同对用于生成位图的一组哈希函数的指示发射给STA。

接收到帧的STA可以将该组哈希函数应用于STA所期望的服务的服务ID以计算位图位置。通过将所计算的位图位置与从AP接收到的帧中的位图进行比较，STA可以确定是否存在关于所期望的服务由AP提供的高概率，并可以基于该确定来决定是否与AP相关联。

服务可以由诸如唯一服务标识符(USID)的标识符来标识。可以通过使用哈希函数或一组哈希函数来压缩服务ID以计算服务ID的哈希值。根据某些方面，包括在AP处可用的服务的经哈希的服务ID的服务提示信息可以被包括在诸如信标、广播帧、GAS帧和/或探测响应的广告中提供的服务信息IE中。

图4示出了根据本公开内容的某些方面的可以包括在广告帧中的服务提示IE 400的示例性帧格式。如图4所示，服务提示IE 400可以包括元素ID字段402、长度字段404、布隆过滤器信息字段406和可变长度m位服务提示图字段408。

根据某些方面，m位服务提示图字段408可以包括表示可用服务的位图。根据某些方面，用于对可用服务ID进行哈希的哈希函数可以是布隆过滤器哈希函数。可以使用一组哈希函数(例如，一组四个哈希函数)将每个服务ID哈希到m位服务提示图字段408中的四个位位置。

成组的哈希函数可以是例如图4A中所示的表400A所示的成组的哈希函数中的任何一组。尽管表400A示出了可以用于对服务IE进行哈希的四组四个布隆过滤器哈希函数，但服务提示IE可以指示可用于对服务IE进行哈希的任意数量的布隆哈希函数。

符号H(j,X,m)表示哈希函数，其中j表示在计算中使用的可以在0x00到0x0F(十六进制符号)范围内的布隆过滤器哈希函数前置参数，其中X表示要在布隆过滤器中指示的服务哈希，其中m表示要以位表示的布隆过滤器的大小。在一个示例实现中，可以使用以下等式来计算使用具有前置参数j的长度为m位的布隆过滤器的用于服务哈希X的哈希函数H(j,X,m)：

A(j,X)＝[j||X](等式1)

其中||表示与操作。

B(j,X)＝CRC32(A(j,X))&0x0000FFFF(等式2)

以获得A(j，X)的32位CRC的最后两个字节，其中CRC操作用0xFFFFFFFF作种子。

H(j,X,m)＝B(j,X)mod m(等式3)

图4B示出了根据本公开内容的某些方面的示例服务提示信息IE 400的布隆过滤器信息字段406的示例子字段。根据某些方面，布隆过滤器信息字段406可以包括对用于生成在m位服务提示图字段408中携带的位图的一组哈希函数的指示，例如来自表1的布隆过滤器集索引。

如图4B所示，布隆过滤器信息字段406还可以包括指示所使用的该组哈希函数的索引的布隆过滤器哈希组索引子字段410。参考表1，例如，可以指示针对组1的00、针对组2的01、针对组3的10、针对组4的11。然而，布隆过滤器哈希组索引可以指示用于对服务ID进行哈希的哈希函数的任何组合。

在示例实现中，为了指示服务哈希X，可以计算与布隆过滤器信息字段406中指示的布隆过滤器组索引相对应的该组哈希函数集合的值。在m位服务提示图字段408中携带的位图中，可以使针对所指示的每个哈希函数计算的比特位置等于1。

图5示出了根据本公开内容的某些方面的用于无线通信的示例操作500的框图。操作500可以例如由接入点(例如，AP 110)执行。操作500在502处通过生成指示由该装置所知的一个或多个服务的多个位图开始，每个位图通过将不同的一组一个或多个基于CRC的哈希函数(例如，CRC32哈希函数)应用到每个服务的一个或多个服务标识(ID)来生成。

在504，AP生成一个或多个帧(例如，信标帧、广播帧、GAS帧或探测响应帧)，每个帧包括多个位图中的一个位图、以及对用于生成包括在该帧中的该位图的该组一个或多个基于CRC的哈希函数的指示。

根据某些方面，可以基于关于提供对AP提供特定服务的误报(false positive)指示的期望概率来选择用于位图的位的数量、成组的基于CRC的哈希函数的数量、或者每一组中的基于CRC的哈希函数的数量。根据某些方面，当生成帧时，AP可以循环遍历多个位图中的不同的位图。AP可以基于对所有多个位图的分析来选择要包括在帧中的位图。例如，AP可以利用在位图中设置的位来分析位置的分布，这可以有助于减少具有指示实际未被提供的服务的位位置。

在506，AP输出一个或多个帧用于传输(例如，作为PAD协议的一部分)。

图6示出了根据本公开内容的某些方面的用于无线通信的示例操作600的框图。操作600可以例如由接入终端(例如，用户终端120)来执行。换句话说，操作600可以由接收到根据上述操作500发送的广告帧的STA执行。

操作600在602通过从另一装置(例如，AP)获得(例如，作为PAD协议的一部分的)帧(例如，信标帧、管理帧、GAS帧或探测响应帧)开始，该帧包括指示由另一装置所知的一个或多个服务的位图以及、对用于生成在帧中包括的位图的一组一个或多个基于CRC的哈希函数(例如，CRC32哈希函数)的指示。

在604，AT通过将所指示的一组一个或多个基于CRC的哈希函数应用于AT所期望的服务的一个或多个服务标识(ID)来确定位图位置。

在606，AT比较所确定的位图位置和包括在帧中的位图位置。在608，如果所述比较指示关于所述装置所期望的服务由所述另一装置所知的概率则AT与所述另一装置相关联、或者如果所述比较指示所述一个或多个服务不由所述另一装置所知则AT避免与所述另一装置相关联。

根据某些方面，上述用于使用布隆过滤器来指示广告中的服务提示信息的技术可以为网络提供压缩格式，以向非AP STA指示大量支持的服务，使得非AP STA可以基于网络是否支持非AP STA所期望的服务来确定是否与AP相关联。

本文公开的方法包括用于实现所述方法的一个或多个步骤或动作。在不脱离权利要求书的范围的情况下，方法步骤和/或动作可以彼此互换。换句话说，除非指定了特定的步骤或动作的顺序，否则在不脱离权利要求书的范围的情况下可以修改特定步骤和/或动作的顺序和/或使用。

如本文所使用地，指一列项目中的“至少一个”的短语是指这些项目的任何组合，包括单个成员。作为示例，“a、b或c中的至少一个”旨在涵盖a、b、c、a-b、a-c、b-c和a-b-c、以及具有多个相同元素的任何组合(例如，a-a、a-a-a、a-a-b、a-a-c、a-b-b、a-c-c、b-b、b-b-b、b-b-c、c-c和c-c-c或a、b和c的任何其它排序。

如本文所使用地，术语“确定”包括各种各样的动作。例如，“确定”可以包括估算、计算、处理、导出、调查、查找(例如，查找表、数据库或其它数据结构)、确认等。此外，“确定”可以包括接收(例如，接收信息)，访问(例如，访问存储器中的数据)等。此外，“确定”可以包括解决、选择、选取、建立等。

在一些情况下，与实际发送帧不同，设备可以具有输出用于传输的帧的接口(用于输出的单元)。例如，处理器可以经由总线接口将帧输出到射频(RF)前端用于传输。类似地，设备可以具有用于获得从另一设备接收到的帧的接口(用于获得的单元)而不是实际接收帧。例如，处理器可以经由总线接口从RF前端获得(或接收)针对接收的帧。

上述方法的各种操作可以通过能够执行相应功能的任何合适的单元来执行。该单元可以包括各种硬件和/或软件组件和/或模块，包括但不限于电路、专用集成电路(ASIC)或处理器。通常，在图中示出操作的情况下，这些操作可以具有采用类似编号的对应的对等功能模块。例如，图5和图6所示的操作500和600对应于图5A和6A所示的单元500A和600A。

例如，用于发射的单元可以包括图2所示的接入点110的发射机(例如，发射机单元222a-222ap)和/或天线224a-224ap、图2所示的用户终端120m的发射机(例如，发射机单元254m-254mu)和/或天线252到图2所示的用户终端120x的发射机(例如，发射机单元254xa-254xu)和/或天线254xa-254xu、和/或图3所示的无线设备302的收发机314的接收机312。用于接收的单元可以包括图2所示的接入点110的接收机(例如，接收机单元222a-222ap)和/或天线224a-224ap、图2所示的用户终端120m的接收机(例如，接收机单元254m-254mu)和/或天线252ma-252mu到图2所示的用户终端120x的接收机(例如，接收机单元254xa-254xu)和/或天线252xa-252xu、和/或图3所示的无线设备302的收发机314的发射机310。

用于处理的单元、用于确定的单元、用于获得的单元、用于输出的单元、用于决定的单元、用于生成的单元、用于比较的单元、用于选择的单元和/或用于分析的单元可以包括处理系统，其可以包括一个或多个处理器，诸如：图2中示出的接入点110的TX空间处理器220、RX空间处理器240、RX数据处理器242、TX数据处理器210、调度器234和/或控制器230、TX MIMO处理器230，图2中示出的用户终端120m的RX空间处理器260m、RX数据处理器270m、TX数据处理器288m、TX空间处理器290m和/或控制器280m到图2所示的用户终端120x的RX空间处理器260x、RX数据处理器270x、TX数据处理器288x、TX空间处理器290x和/或控制器280x；和/或图3所示的无线设备302的处理器304。

根据某些方面，这种单元可以通过处理系统实现，该处理系统被配置为通过实现上述用于使用布隆过滤器来提供广告中的服务提示信息的算法(例如，以硬件或通过执行软件指令)执行对应功能。例如，用于生成指示由装置所知的一个或多个服务的多个位图的算法，每个位图是通过将不同的一组一个或多个基于CRC的哈希函数应用于每个服务的一个或多个服务ID来生成的，用于生成一个或多个帧的算法，每个帧包括多个位图中的一个位图、以及对用于生成在该帧中包括的该位图的该组一个或多个基于CRC的哈希函数的指示，以及用于输出一个或多个帧用于传输的算法。作为另一示例，用于从另一装置获得帧的算法，该帧包括指示由该另一装置所知的一个或多个服务的位图、以及对用于生成在该帧中包括的位图的一组一个或多个基于CRC的哈希函数的指示，用于通过将所指示的一组一个或多个基于CRC的哈希函数应用于装置所期望的服务的一个或多个服务标识(ID)来确定位图位置的算法，用于比较位图位置和帧中包括的位图的算法，以及用于如果比较指示关于该装置所期望的服务由该另一装置所知的概率则与该另一装置相关联、或者如果比较指示一个或多个服务不被该另一装置所知则避免与该另一装置相关联的算法。

结合本公开内容描述的各种说明性逻辑框、模块和电路可以用被设计用于执行本文所述的功能的通用处理器、数字信号处理器(DSP)、专用集成电路(ASIC)、现场可编程门阵列(FPGA)或其它可编程逻辑器件(PLD)、离散门或晶体管逻辑、离散硬件组件或其任何组合来实现。通用处理器可以是微处理器，但是在替代方案中，处理器可以是任何可商用的处理器、控制器、微控制器或状态机。处理器还可以被实现为计算设备的组合，例如DSP和微处理器的组合、多个微处理器、与DSP核结合的一个或多个微处理器、或任何其它此类配置。

如果在硬件中实现，则示例硬件配置可以包括无线节点中的处理系统。处理系统可以用总线架构来实现。总线可以包括任何数量的互连总线和桥接器，这取决于处理系统的具体应用和总体设计约束。总线可以链接各种电路，包括处理器、机器可读介质和总线接口。除了其它，总线接口可以用于通过总线将网络适配器连接到处理系统。网络适配器可以用于实现PHY层的信号处理功能。在用户终端120(参见图1)的情况下，用户接口(例如，键盘、显示器、鼠标、操纵杆等)也可以连接到总线。总线也可以链接诸如定时源、外围设备、电压调节器、功率管理电路等各种其它电路，这在本领域中是众所周知地，因此将不再进一步描述。处理器可以用一个或多个通用和/或专用处理器实现。示例包括微处理器、微控制器、DSP处理器以及可执行软件的其它电路。本领域技术人员将认识到，根据特定应用和施加在整个系统上的总体设计约束，如何最佳地实现所述处理系统的功能。

如果以软件实现，则功能可以作为一个或多个指令或代码在计算机可读介质上存储或传输。软件应被宽泛地解释为指代指令、数据或其任何组合，无论被称为软件、固件、中间件、微代码、硬件描述语言还是其它。计算机可读介质包括计算机存储介质和通信介质，包括便于将计算机程序从一个地方传送到另一个地方的任何介质。处理器可能负责管理总线和一般处理，包括执行存储在机器可读存储介质上的软件模块。计算机可读存储介质可以耦合到处理器，使得处理器可以从存储介质读取信息和向存储介质写入信息。在替代方案中，存储介质可以与处理器成一体。作为示例，机器可读介质可以包括传输线、由数据调制的载波、和/或其上存储有指令的与无线节点分离的计算机可读存储介质，所有这些可由处理器通过总线接口访问。或者或另外，机器可读介质或其任何部分可以集成到处理器中，例如在可以使用高速缓存和/或通用寄存器文件的情况下。机器可读存储介质的示例可以包括例如RAM(随机存取存储器)、闪存、ROM(只读存储器)、PROM(可编程只读存储器)、EPROM(可擦除可编程只读存储器)、EEPROM(电可擦除可编程只读存储器)、寄存器、磁盘、光盘、硬盘驱动器或任何其它合适的存储介质、或其任何组合。机器可读介质可以体现在计算机程序产品中。

软件模块可以包括单个指令或许多指令，并且可以分布在多个不同代码段之间、不同程序之间、以及跨多个存储介质。计算机可读介质可以包括多个软件模块。软件模块包括当由诸如处理器的设备执行时使得处理系统执行各种功能的指令。软件模块可以包括发射模块和接收模块。每个软件模块可以驻留在单个存储设备中或者分布在多个存储设备上。例如，当触发事件发生时，软件模块可以从硬盘驱动器加载到RAM中。在执行软件模块期间，处理器可以将一些指令加载到高速缓存中以增加访问速度。然后可以将一个或多个高速缓存行加载到通用寄存器文件中以供处理器执行。当参考下面的软件模块的功能时，应当理解，当执行来自该软件模块的指令时，这种功能由处理器实现。

而且，任何连接被适当地称为计算机可读介质。例如，如果使用同轴电缆、光纤电缆、双绞线、数字用户线(DSL)或诸如红外(IR)、无线电和微波的无线技术从网站、服务器或其它远程源发送软件，则同轴电缆、光纤电缆、双绞线、DSL或如红外线、无线电和微波的无线技术都包含在介质的定义中。如本文所使用地，磁盘和光盘包括光盘(CD)、激光盘、光盘、数字通用光盘(DVD)、软盘和其中磁盘通常磁性地再现数据，而光盘以光学方式再现数据。因此，在一些方面，计算机可读介质可以包括非暂时的计算机可读介质(例如有形介质)。此外，对于其它方面，计算机可读介质可以包括暂时的计算机可读介质(例如，信号)。上述的组合也应包括在计算机可读介质的范围内。

因此，某些方面可以包括用于执行本文给出的操作的计算机程序产品。例如，这样的计算机程序产品可以包括具有在其上存储(和/或编码)的指令的计算机可读介质，所述指令可由一个或多个处理器执行以执行本文所述的操作。例如，用于生成指示该装置所知的一个或多个服务的多个位图的指令，每个位图通过将不同的一组一个或多个基于CRC的哈希函数应用于每个服务的一个或多个服务ID来生成，用于生成一个或多个帧的指令，每个帧包括所述多个位图之一以及对用于生成包括在所述帧中的该位图的该组一个或多个基于CRC的哈希函数的指示，以及用于输出所述一个或多个帧用于传输的指令。作为另一示例，用于从另一装置获得帧的指令，所述帧包括指示由另一装置所知的一个或多个服务的位图以及对用于生成包括在帧中的位图的一组一个或多个基于CRC的哈希函数的指示，用于通过将所指示的一组一个或多个基于CRC的哈希函数应用于所述装置所期望的服务的一个或多个服务ID来确定位图位置的指令，用于比较位图位置和所述帧中包括的位图的指令，以及用于基于比较来决定是否与另一装置相关联的指令。

此外，应当理解，用于执行本文描述的方法和技术的模块和/或其它适当的单元可以由用户终端和/或基站适当地下载和/或以其它方式获得。例如，这样的设备可以耦合到服务器以便于传送用于执行本文描述的方法的单元。或者，可以经由存储单元(例如RAM、ROM、诸如光盘(CD)或软盘等的物理存储介质等)来提供本文描述的各种方法，使得用户终端和/或基站可以在将存储单元耦合或提供给设备时获得各种方法。此外，可以利用用于将本文所述的方法和技术提供给设备的任何其它合适的技术。

应当理解，权利要求书不限于上述精确的配置和组件。在不脱离权利要求书的范围的情况下，可以对上述方法和装置的布置、操作和细节进行各种修改、改变和变化。