基于位置的服务(location-based service，LBS)是指移动终端利用各种定位技术，获取用户的位置信息，然后将这些信息传输给服务提供商，服务提供商根据用户的位置信息提供个性化服务。随着智能设备广泛地进入人们的生活，LBS技术得到了突飞猛进的发展。例如，用户逛街的时候用手机查找附近有哪些打折的商店。随着LBS应用的普及，用户对个人隐私以及LBS的服务质量越来越关注，因此LBS服务中查询结果的验证技术成为了研究的热点问题。

LBS服务中用户的地理位置数据形成了庞大的数据集即LBS大数据。一种常见的LBS大数据商业模型见图 1，主要由3部分组成： 数据拥有者(data owner，DO)、 服务提供商(service provider，SP)和用户。DO将所有的数据以及额外的信息外包给第三方的SP，从而得到专业的服务，同时节省运行成本。所有用户向第三方SP发送数据访问操作请求，SP返回用户的查询结果和必要的额外信息，称这些额外信息为验证对象(verification object,VO)。

但是第三方的SP有可能是不可信的，它可能受到来自内部或外部的攻击。因此会导致以下问题的出现： 1) 数据的篡改，2) 查询结果的篡改，3) 数据遗漏。如果缺乏有效的措施，一旦出现这些问题，用户又无法证明数据的真伪，往往会给用户甚至数据拥有者带来很严重的后果。因此，需要为用户提供一种有效的手段，使其能够快速准确地对查询结果进行验证。查询结果验证的目标包括： 1) 真实性，即数据拥有者的数据没有被篡改； 2) 正确性，即返回的查询结果满足查询要求； 3) 完整性，即查询结果全部返回客户端，没有缺失任何有效结果。

为了验证这些目标，SP向客户端返回查询结果和VO。客户端根据查询结果和SP返回的验证对象对查询结果进行验证。例如对查询结果的完整性进行验证(见图 2)，范围查询Q的范围是[α，β]，查询结果集合为R_S={r₂，r₃，…，r₉}，在对结果进行验证时，需要验证r₁<α,r₃≥α,r₉≤β,r₁₀>β。这样会将边界数据r₁和r₁₀返回给客户端，而该数据可能会泄漏其他用户隐私，因此在查询验证过程中会出现隐私泄露的问题。本文的主要工作是在确保数据隐私不被泄露的情况下，进行用户查询结果的真实性、正确性和完整性的验证。

本文针对上述问题，提出了一种基于固定网格划分四叉树上的查询结果验证技术。文^[2]采用R树^[3]索引结果对LBS大数据进行索引，并在该索引结构上进行查询验证。本文提出采用网格划分的方法对空间数据进行划分，并采用四叉树^[4]对划分后的网格进行索引。二维的LBS大数据可以被固定网格划分，并且，采用递归划分的方法，可以被四叉树数据结构自然地索引起来。LBS大数据中移动对象的位置随时间而变化，因此数据的动态性导致了索引结构大量的更新操作，本文提出的空间索引结构更新代价低，方便了数据的管理，缩短了检索的时间，四叉树索引对于范围查询具有较高的查询验证效率。

1 相关工作

目前，LBS大数据商业模型中保护数据正确性、真实性和完整性的方法主要有基于概率理论^[5]的方法、基于验证数据结构(authenticated data structure，ADS)的方法、基于挑战-响应模式^[11]的方法等。

1.1 基于概率理论的方法

文^[5]提出了一种基于概率的结果正确性、真实性和完整性验证方法，其基本思想是： DO在将数据外包给第三方SP时，在数据中混入一些特别的监听元组。这些混在原始数据中的监听元组以一定概率出现在查询结果中，并和结果一起返回给提交查询的客户端。客户端可以通过监控这些混入的元组来监控外包数据库的完整性。如果一个满足查询条件的监控元组没有被返回，那么客户端就可以知道数据库已经遭到攻击，不能满足完整性。反之，如果所有满足查询条件的监控元组都完整地返回，则以一定概率称完整性没有受到攻击。

1.2 基于验证数据结构的方法

数字签名是指只有信息的发送者才能产生的别人无法伪造的一段数字串，这段数字串同时也是对信息发送者所发送信息真实性的一个有效证明。它是消息摘要^[6]和非对称加密技术^[7]的综合应用。

目前的数字签名大多基于公钥密码。但这种方法只能验证真实性，无法验证查询结果的完整性。服务器可能只返回了正确结果集中的一部分结果。

针对数字签名不能进行完整性验证的问题，文^[8]提出了一种数字签名链技术，数据的签名与近邻的值有关。为了方便验证，在第一个数据前和最后一个数据后添加两个特殊的对象。

图 3中，对于排好序的a₁、 a₂、 a₃、 a₄，它们的签名是自己和左右相邻的值的签名。在a₁的左面加一个a₀，值为－； 在a₄的右面添加一个a₅，其值是+。例如，客户端的查询结果是a₂和a₃。返回给客户端的VO为： 1) a₂的数字签名sign(a₂)，a₃的数字签名sign (a₃)； 2) 边界值a₁和a₄。验证过程： 边界值a₁和a₄在查询范围之外保证了结果的完整性，签名sign(a₂)和sign (a₃)有效保证了结果的正确性、真实性。

文^[9-11]提出了一种Merkle哈希树上的查询验证技术。首先对数据库中所有的记录按照关键字的值从小到大排好序，然后构建一个B树，B树的每个叶子节点对应一个数据元组，每个叶子节点存储对应元组的哈希值，这样就构建了Merkle哈希树，然后从低向上计算根节点的数字签名，用于查询结果正确性的验证。图 4中，根据a₁、 a₂、 a₃、 a₄建立哈希树。

叶子结点是每个值的摘要，由一个单向哈希函数求得，如N₁₁=H(a₁)、 N₁₂=H(a₂)、 N₁₃=H(a₃)、 N₁₄=H (a₄)。中间结点是其所有孩子结点的联接N₁=H (N₁₁|N₁₂)，即N₁=H (H(a₁)|H(a₂))，其中|表示联接。例如，客户端的查询结果是a₁和a₂。返回给客户端的VO为： 1) N₂的摘要; 2) 根结点N的签名。验证过程： 客户端首先计算出a₁、 a₂的摘要值，然后计算其父亲结点的摘要值N₁，联合验证对象N₂计算出N，将计算结果与根节点的签名解密后的摘要进行比较，如果相同则说明数据没有被篡改。这样Merkle哈希树保证了结果的正确性和真实性，但由于叶子结点的无序使其不能保证结果的完整性。

1.3 基于挑战-响应模式的方法

针对SP恶意篡改查询结果，文^[12]提出了一种对任意查询都确保查询正确执行的解决方法。它是建立在挑战—响应协议上的查询验证机制，计算和传输代价低。但这种方法只能保证SP为客户端提供了服务，无法检测到不可信的SP篡改数据。

文^[13]讨论了外包数据库中数据的完整性验证，但这只是针对一维数据的查询验证； 文^[14]是对Skyline查询进行验证； 文^[15]是对移动近邻(moving KNN)查询进行验证； 文^[16]在对查询结果进行验证时考虑了隐私保护； 文^[17]在路网中对KNN查询进行验证； 而^[18]提出了针对数据桶的一种验证方法，该方法简单但是不能应对LBS对数据实时更新的要求。

2 LBS大数据的四叉树索引

文^[2]中针对R-tree不适用小范围查询而提出的网格索引是一种哈希存储方式，在数据增多时目录会慢慢变大，由于目录被存储在磁盘中，这样在查询时会进行多次I/O操作。因此本文提出了一种基于固定网格划分四叉树上的查询验证。这种四叉树是一种改进的四叉树，每个空间对象只在四叉树中存储一次，避免了存储空间的浪费。基于网格划分的四叉树是一棵满四叉树避免空间对象加入时需要重新分配内存，加快了插入速度，提高了查询的速度，改善了LBS大数据查询验证的性能。由于这种满四叉树，采用顺序的数组存储方式，内存耗费是链表结构的四分之一，而且其索引结构可以放在内存中，因此无需I/O方面的耗费。该查询验证技术可以在查询验证的同时提高查询的速度，因此提高了LBS大数据中的查询性能。在不泄露用户位置的情况下，保证了用户查询结果的真实性、正确性、完整性。

索引技术是移动对象数据库的核心技术，决定了LBS大数据的查询性能。LBS大数据要求更新代价低及快速地响应不同用户的在线查询请求。因此如何选取空间索引技术是LBS大数据技术的关键，是快速高效查询空间数据的重要指标。针对LBS中的大数据，本文采用四叉树这种可以有效压缩栅格数据的索引机制，提出一种基于固定网格划分四叉树索引机制的范围查询验证技术。这样在提高查询速度的同时，保证了查询结果的正确性、真实性和完整性。

LBS大数据的四叉树索引基本思想是： 将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成4个相等的子空间，如此递归下去，直至树的层次达到一定深度或者满足某种要求后停止分割。LBS移动对象的位置随时间发生变化，数据具有很大的变动性，这就要求LBS大数据的索引结构要适应这种频繁的更新操作，四叉树这种常见的空间索引结构与R树不同，是基于空间划分组织索引结构的一类索引机制。因此更适用于LBS大数据的频繁更新操作。N层基于固定网格划分四叉树的运行时间复杂度是O(N)。本文采用这种更加简单、高效、易于实现的固定网格四分树索引结构。

基于固定网格划分的四叉树是一个满四叉树空间索引。N层基于固定网格划分四叉树的叶子结点所对应的子空间是一个2^N×2^N的网状结构，如图 5a所示。

图 5b是固定网格划分索引结构，图 5c是N为2的基于固定网格划分的四叉树。树的非叶子结点数是$\sum\limits_{i=0}^{N-1}{{}}{{4}^{i}}$叶子结点数是2^N×2^N。空间对象D记录在叶子结点，但是当同一个父亲结点所有的叶子结点都要记录同一个对象时，就将它记录在父亲结点中，例如，图 5b中的R₁即图 5a中的体育馆占4个网格，叶子结点1、 2、 5、 6都要记录它，因此将它记录在其父亲结点。而对于对象R₂即图 5a中的远航楼，只要记录在叶子结点4和8中。线型对象L即图 5a中的凌水河占4个网格，叶子节点9、 10、 13、 14都要记录它，同样记录在父亲结点中。对于点对象P只要记录在叶子结点12。

基于固定网格划分的四叉树的构成方式和网格索引^[13]方式都是多对多的形式，但前者比后者有效地减少了空间对象在结点中的重复记录。它的插入和删除都相当简单，只要在其覆盖的叶子结点或者父亲结点删除或者插入对象即可，而R树的分裂和合并操作的时间代价比较大，这也是固定网格划分四叉树索引优于R树索引的一个方面。它的查询方式也很简单，例如对于范围查询Q，只需要检索出Q所覆盖的叶子结点和其父亲结点及祖先结点中所有的空间对象，然后再进行必要的空间运算从中检索出满足要求的空间对象。

3 基于固定网格划分索引的范围查询验证技术 3.1 LBS大数据查询结果验证过程

针对网格中的对象，本文先对其求摘要值。由于摘要函数是单向的，为了验证查询结果的正确性、真实性、完整性，本文采用RSA加密算法，生成一对公钥和私钥，用私钥对消息摘要加密生成数字签名。将数字签名和数据给SP，SP根据用户的请求范围，进行范围查询处理，并将验证对象和查询结果返回给客户端。

客户端根据VO和结果进行验证，利用RSA生成的公钥对数字签名进行解密，形成消息摘要。然后利用相同的哈希函数对结果生成消息摘要，对比2个摘要是否相同： 相同，则验证了查询结果的完整性、正确性和真实性； 不相同，则说明LBS大数据库受到了攻击，客户端将舍弃这一次的查询。

3.2 隐私保护的联合摘要技术

随着基于位置的服务在人们生活中的广泛应用，带来了一些隐私泄露的问题，客户端并不希望由于接受了服务而向外界泄露了自己的位置信息，这既包括客户端当前的位置，也包括它的移动习惯等。人们希望在对SP提供的查询结果进行验证的同时，保护自己的位置隐私。为了在验证LBS大数据的查询结果时不泄露用户的位置隐私，可以采用客户端和服务器共同计算摘要的技术。具体的设计思想如下：

假定LBS数据库中的关系数据表集合R={r₁,r₂,…,r_n}，每个记录拥有的属性是<K,A₁,A₂,…,A_m>，K是主关键字，并且L<K<U，L和U分别是K的下界和上界。假定客户端查询Q的范围为[α,β]，查询的结果是R_S={r_a,r_a+1,…,r_b}。为了验证结果需要满足：

1) 真实性，即r_a,r_a+1,…,r_b都是LBS中的数据。

2) 完整性，即查询结果是在α和β之间。

3) 正确性，即r_a和r_b分别是查询结果的第一条记录和最后一条记录。需要证明r_a-1.K<α且r_b+1.K>β，但是为了保护客户端的隐私，服务器不能够将r_a-1.K和r_b+1.K直接返回给客户端，并且要确保攻击者不能使用验证信息计算出它们的值。以对r_a-1.K<α的验证为例，可以用客户端和服务器联合计算出的U-r_a-1.K摘要值，其中定义一个g函数，并且满足gx+y=gx-ag(a+y)。这样为了验证r_a-1.K<α而不泄露r_a-1，服务器可以返回g(α-r_a-1.K)，客户端计算g(U-α)，然后联合起来计算gU-r_a-1.K=g(U-α)g(α-r_a-1.K)。只要g(x)对于x<=0是未定义的或者计算是不可行的，那么，当r_a-1.K≥α时，服务器就不能够返回g(α-r_a-1.K)来欺骗客户端。对r_b+1.K>β的验证方式与此类似。

但现在还没有一个满足这样性质的g(x)，即对于x<0没有简单的方法来生成g(x)，因此采用迭代哈希函数h^y(x) 来代替，h^y(x)表示对h(x)进行y次迭代哈希运算。例如，hⁱ(r)=h^i-1(h(r))。

重新定义摘要函数g(r)=h^U-r-1(r)，为证明r_a-1.K<α，客户端对h^α-r_a-1-1(r_a-1.K)进行(U-α)次哈希运算从而得到gr_a-1=h^U-α+α-r_a-1.K-1(r_a-1.K)。

例如，R={2,4,5,7,8}，查询Q的范围是^{[3, 6]}。L是1，U是10。g(r)=h^U-r-1(r)，计算g(2)=h^10-2-1(2)、 g(4)=h^10-4-1(4)、 g(5)=h^10-5-1(5)，以此类推得到g(r)。R_S=^{[4, 5]}，边界是2和7。为了不泄露边界数据，服务器返回h^α-r_a-1-1(r_a-1.K)即h^3-2-1(2)，客户端进行验证时对其进行 (U-α)即(10-3)次哈希运算。得到gr_a-1=h^U-α+α-r_a-1.K-1(r_a-1.K)，因此得到g(2)=h^{(10-3)+(3-2-1)}(2)即g(2)=h⁷(2)。

本文利用这种服务器和客户端共同计算摘要的方法，以客户端进行多次哈希运算的方式保护了边界数据的隐私。在不泄露用户边界数据的情况下，对LBS大数据中基于固定划分四叉树索引的查询结果进行了验证。

3.3 基于四叉树索引的验证

二维的LBS大数据可以被固定网格划分，并且采用递归划分的方法可以被四叉树数据结构自然地索引起来。因此，本文提出基于固定网格划分四叉树索引机制的范围查询验证技术。文^[2]提出了基于R树的查询验证技术，但是R树索引机制可能不会保护客户端的位置隐私，它的叶子层实体不是线性的，而不像B+树上只要验证边界结点即可。而对于网格索引需要对每一个网格进行签名，这样的计算量会很大，不能快速地对查询结果进行验证。因此本文提出了基于固定网格划分四叉树的验证方案，在保护用户位置隐私不被泄露的同时，完成LBS大数据查询结果的正确性、真实性、完整性验证。

图 6a中，首先对平面进行递归划分，用x₀、 x₁、 x₂、 x₃、 x₄进行水平划分，用y₀、 y₁、 y₂、 y₃、 y₄进行垂直划分，形成一个2^N×2^N的网状结构。然后对网格建立四叉树空间索引(见图 6b)，其中NW、 NE、 SW、 SE分别代表 4个子象限，也就是四叉树的4个分支。

为了对LBS大数据的内容数据进行隐私保护，其中网格划分的数量和空间对象的坐标对客户端保密。给定范围查询Q，满足条件α≤K≤β。检索时首先从四叉树的根结点开始，若根结点的数据在Q内则将数据记录在R_S中，然后比较范围Q与根结点的4个子结点是否有交集，如果有交集则记录在结果中，如果没有则这个子树不予考虑，这样递归找到查询结果。具体的执行算法如图 7和8所示。

客户端通过验证x₁≤α_x≤x₂，x₃≤β_x≤x₄，y₁≤α_y≤y₂，y₃≤β_y≤y₄来对边界线进行验证，确保查询结果的完整性。为了进行边界验证来确保数据的正确性和真实性，本文定义每个节点的摘要，它包含了对象r₁，r₂，…，r_n。每个对象的摘要定义为dig(r)=h(h(r.id)|g(U.x-r.x)|g(r.x-L.x)|g(U.y-r.y)|g(r.y-L.y)), 每个结点的摘要定义为dig(C)=H(dig(r₁)|dig(r₂)|… dig(r_i)… |dig(r_n)),每一个叶子结点的签名定义为sign(C)=sign(dig(c₁)|dig(c₂)|dig(c₃)|dig(c₄))。

正确性具体的验证过程： 图 6中，服务器经过查询处理后将结果R_S即{r₅,r_6,r₇,r₉}和VO 即{r₁₀,r₁₁}返回给客户端。查询结果是{r₅,r₆,r₇,r₉}，对于r₅的验证过程为，根据服务器返回的验证对象h^{β.x-r₁₀.x}(r₁₀)、 h^{β.y-r₁₀.y}(r₁₀)、 h^{r₁₀.x-α.x}(r₁₀)和h^{r₁₀.y-α.y}(r₁₀)来计算摘要值g(u.x-r.x)=h^u.x-r.x(r)即对h^{β.x-r₁₀.x}(r₁₀)进行(u.x-β.x)次哈希运算。类似的得到g(u.y-r.y)。从而计算出dig(r₁₀)=h(h(r.id)|g(u.x-r.x)|g(u.y-r.y))。计算结点摘要dig(C)=H(dig(r₅)|dig(r₁₀))对于每一个叶子结点的签名如下： 用非对称加密算法(RSA)生成的私钥进行解密形成消息摘要，对比两个摘要是否相同。其中h是哈希函数，g是摘要函数。

通过服务器返回边界对象r₁₀的摘要，客户端和服务器共同计算结点的摘要来保护客户端的隐私。同样对于对象r₆的验证是服务器返回dig(r₁₁)，客户端计算出dig(r₆)，然后和服务器返回的VO共同计算出dig(C)和所在的单元格进行对比。由于空间对象r₇和r₉所在的结点只有一个数据，不涉及边界数据，因此对于r₇和r₉的验证，由客户端自己计算出，然后计算dig(C)与本单元格的签名进行对比。

图 6b中用不同的灰度来表示摘要的得到方式，其中深灰色表示由服务器返回，浅灰色表示由客户端自己计算。如果四叉树的叶子节点有多个对象，那么服务器和客户端共同计算。由于四叉树的每一个叶子节点可能包含多个对象即不同用户的位置信息，用户不希望将与查询结果无关的边界信息泄露给客户端如对象r₁₀和r₁₁。因此，本文采用这种服务器和客户端共同计算摘要的形式，在不需要知道节点中其他对象值的情况下，对LBS大数据中查询结果进行了验证。这样就确保了用户数据在进行查询验证的时候不被泄露，同时验证了查询结果的正确性、真实性、完整性。

4 实验和性能分析 4.1 实验准备

本文的实验使用的计算机配置为Intel i5-4590 3.3 GHz CPU，4 GB内存，算法使用Java实现。实验数据采用随机数据发生器在二维空间内产生2 000、 4 000、 6 000、 8 000、 10 000个点的数据集。这些数据集均匀分布在二维空间内。实验采用范围查询，随机地选取几个点如2 km内的餐厅，将圆形的范围近似为矩形的查询范围。实验主要的测试指标是CPU的响应时间和数据集大小对查询时间、查询结果的影响。

4.2 效率和成本分析

通过实验将网格索引上的和本文中提出的基于固定网格划分四叉树上的查询验证进行了对比。由于基于固定网格划分四叉树上的查询验证对网格进行了索引，可以快速查找指定空间内的对象，也可以快速查找对象所在的空间，提高了运行速度，缩短了查询验证的时间。

实验中查询位置是随机指定的，随着数据集大小的不断增加，查询结果和VO大小也随之增加，实验结果如图 9所示。

针对不同的数据集大小，服务器查询时间和客户端验证时间都随着数据集的大小的增加基本呈线性增长，实验结果如图 10所示。

影响查询和验证时间的主要因素是查询验证对象的结构以及客户端验证过程中消耗的资源等。针对验证对象进行多次哈希运算带来的大计算量问题，本文采用聚集签名技术^[14]生成单个聚集签名，提高用户验证速度。在相同的实验条件下，网格索引和四叉树索引的实验结果见图 11，可以看出四叉树索引方案的响应时间低于网格索引的。

5 结 论

本文根据基于网格划分四叉树的快速查询特点，提出了一种LBS大数据中基于固定网格划分四叉树上的查询验证技术。通过对网格进行四叉树索引，提高了查询速度，可以在LBS大数据中在保护用户的隐私的同时对查询结果进行验证。

下一步将研究在查询验证的同时如何尽量减少摘要函数的计算和提高查询验证的效率，进一步保证查询结果的真实性、正确性和完整性。