摘要: 1. 扩展摘要
当前对于基于位置的服务（LBS）的大多数研究假设点对点的无线通信，即服务器处理请求然后通过一个点对点的无线信道返回给用户请求结果。然而，利用点对点无线信道的LBS具有巨大的流量负担和大量的用户服务请求，因而导致了较差的性能。

在本文中，我们提出了基于广播的空间请求处理算法。该算法支持在无线网络中的空间请求。我们首先提出一个一般性的框架，该框架通过无线数据广播处理连续的范围请求。然后我们提出了一个基于广播的空间请求处理方法，该方法通过无线数据广播支持K-NN（K近邻）请求。和已有的工作相比，这个框架最先处理了连续空间请求的问题，不使用索引，有效地利用了低无限带宽，因此很理想地以最快访问速度达到了最大的可扩展性。

请求处理器的任务是当服务器根据数据项的位置传播数据时，选择性地监视无线广播信道。我们做了实验以评价所提出算法的性能。详尽的实验显示我们提出的算法具有高度的可扩展性，并且比以前的技术在访问时间和能耗上更优越。
2. 技术背景
传统的通过无线网络的数据传送技术是基于两种方法：推送式和拉取式（push-based and pull-based）。在推送式方法中，数据项被周期性地在下行信道中广播。服务器通过无线信道传播信息至任意大数量的移动客户端。推送式的最大优点是它可以被任意数量的客户端并行地访问而不会导致任何性能下降。在拉取式方法中，客户端通过上行信道请求一个数据项，服务器通过从下行信道传输数据至客户端回复。平均数据访问时间取决于累计的工作负荷和网络负荷，但和数据库的大小无关。当客户端数量比较小的时候，拉取式模型是有效地。然而这个方法没有很好的扩展性，因为随着客户端数量增加，信道带宽和服务器会很快导致瓶颈。也就是说，和点对点连接相比，无线广播系统提供了一种更高效的数据传递方法，并允许大量客户端同时的信息检索。因此，这是一种很有前途的并且令人满意的为未来普适计算环境设计的数据传播方法。在未来普适计算环境中，我们预期客户端的基数是非常大的。借助于加油站，高速公路出入口，酒店，餐厅等的位置信息在无线广播信道中的广播，移动客户端在高速公路上旅行时，他们将能够收听并找到加油站或酒店，以及其他信息。

在基于广播的模型中，数据的广播加上索引结构是一种在无线移动环境下有效的传播数据的方法。索引（例如文件的目录）可以在监听阶段用来引导客户端。通过首先访问广播索引，客户端可以预测需要的数据的到达时间。这个基数允许移动客户端只有在感兴趣的空间数据和相关内容在信道中可利用时，才收听连续的广播信道，这样就最小化了功耗。使用在广播信道中恰当地交织索引信息和数据的广播技术可以显著地改进能量效率和访问时间。因此，使用索引可以帮助客户端降低监听广播信道的时间。基本思想是组织广播数据的使得CPU在大多数时间能在低功耗模式下工作，并且只有当感兴趣的数据被广播时才醒来监听信道。
3. 动机
现存的索引结构并不适用于在无线数据环境下的LBS。我们考虑的主要问题是三方面的。首先，由于附加的消息，广播周期变长了。增长了的广播周期增加了平均访问延迟。其次，搜索检索需要的数据项的到达时间的努力增加了调谐时间和访问延迟。第三，现有的搜索算法是为传统的空间数据库设计的，并没有考虑空间索引的时间序列特性。因此，现有的索引方法不适于无线广播系统中的LBS。
4. 本文贡献
本文的主要贡献总结如下：
•我们提出了简单且易懂的算法来支持无线广播环境中的范围和k-NN搜索。我们提出的算法具有最有访问延迟，因为广播的顺序是基于数据对象的位置并且客户端不需要进行映射过程（例如从Hilbert-Curve值映射到点的实际坐标）以得到数据对象的实际位置，也不需要等待广播信道以接受索引。所提出的空间请求处理算法适合于顺序访问的广播信道。
•我们提出了数据传播和基于数据对象位置的选择性调谐算法。利用所提出的算法，客户端不需要依靠传统的索引或者搜索算法用来做空间搜索。该算法高度可扩展，且比以前的技术在访问时间和能耗方面更高效。
•我们提出了一个成本模型以验证我们算法的性能，并用生成的数据和实际数据将我们的算法和当前的算法进行了比较。

由于数据广播模型在可扩展性方面的优势，我们在本文中充分利用了该模型的特点。我们的目标是最小化两个参数：访问时间和能耗。能耗是以在执行请求过程中服务器广播的节点数量计算的。