云环境下基于动态聚类及相似树查询的无线体域网隐私数据检索算法研究∗

姚 兰 金钰博 顾佳良

（1.东北大学计算机科学与工程学院 沈阳 110819）（2.辽宁工程技术大学电子与信息工程学院 葫芦岛 125000）

1 引言

随着无线通信及计算机技术的不断发展，WBAN的应用越来越广泛，数据量也越来越庞大，同时WBAN在医疗诊断领域应用最为突出，这就带来医疗数据的机密性、隐私性等安全问题。无线体域网技术应用主要面临两类隐私侵犯，位置隐私与信息隐私。由于在无线体域网技术应用中，位置隐私带有高度的个人性，用户的位置信息很容易被探知。信息隐私包括用户的各项生理参数，如果这些重要的数被第三方查阅或截获，将为用户带来重大损失。通常云存储服务提供商并不提供机密的数据存储服务［2～4］，为保证数据机密性，用户的隐私数据通常以密文形式存储在数据服务方，另一方面，WBAN的用户量大，数据采集周期短，形成了海量生理数据。如何在海量的涉密信息中进行高效准确的密文检索已经成为一种迫切的需求。密文检索作为一种云环境下访问数据的一种主要方式已经变得越来越重要，并且在其安全性和加密方式上显得尤为突出［1］。但是随之而来的问题是，传统的检索方式对加密后的数据失效，那么随着密文量的增加，怎样检索密文已经越来越受到人们的重视。在传统的存储服务中，所有的数据存储都是本地化，并且所有的安全策略都隶属于数据的拥有者。数据的所有权和管理权是统一的。然而在云存储服务中，数据所有权和管理权是分开的，并且用户对数据的管理操作是非常有限的。云存储服务提供商对用户所有数据都是可见的，这必定会产生用户隐私数据泄露的安全问题，因此，考虑到的云供应商不完全可信，如何保证云存储中的用户数据隐私，如何提高数据的用户控制和如何利用云计算和存储能力，解决了密文检索的安全性，是本文的重要研究内容。

当前的数据保护技术中，加密算法［2］能够较好地保护数据，但加解密计算会对系统效率产生极大的影响；数据拆分重装策略的效率较高，但其对云平台的结构和物理层次依赖性过大。因此，找到数据的实用性与安全性的平衡点是云存储平台应用中最为关键的问题。文献［3］提出基于多身份、多密钥的层次全同态加密方案，满足多用户共享，不同身份密文计算。文献［4］提出了适用于多机构系统的访问控制方案。文献［5］提出基于身份的纯全同态加密方案，满足多用户共享和不同身份、不同属性密文计算。文献［6］中提出了一种加密方式和密文顺序检索架构，该方法证明，在只知道密文的情况下，云存储服务提供商不能截取任何明文的信息。但是，该方案的加密和查询算法的时间复杂度为O（n），其中n表示文档长度。文献［7］形式化地定义了安全索引结构—Z索引，该索引模型通过伪随机函数和布隆过滤器（Bloom Filter）实现，可以抵抗适应性选择关键字攻击，然而，Z索引并不提供查询排序机制，若查询词出现在大量文档中，用户需要从大量的结果集中筛选所需文档。通过在倒排表中加入相关度分数，文献［8］实现了支持结果集排序的密文检索方法。在查询阶段，云服务器仅需返回与查询条件匹配的前k个相关文档，而不是所有满足条件的文档，这不但减少了带宽的消耗，还改善了用户体验。然而，上述工作仅能解决单关键词密文检索的问题，即用户在一次查询中仅能提交一个查询检索词。

相比单关键字检索，多关键字检索能够更全面地表达用户的查询意图。文献［9］提出一种新的密文检索框架MRSE以解决多关键字密文检索问题。在索引建立阶段，每个文档被表示成一个二进制向量，其中每一位的值代表当前文档是否包含该关键字。查询向量以同样的方式被表示成一个二进制向量。云服务器通过执行矩阵运算和安全k近邻算法获取排序的结果集并返回给用户。然而，MRSE框架的查询响应时间随着文档集的扩大而增长，难以适应大数据时代数据迅速增长的需求。文献［10］将密文检索框架MRSE进行优化，提出一种新型的密文索引结构：MRSE-SS，将相似查询树结构引入密文索引框架用于提升多关键字排序检索的效率，并且提出一种动态聚类算法DK-MEDOIDS，聚类过程随文档量增加而动态变化，适用于云计算环境下的密文检索场景。

为了加快查询的速度，树形结构普遍应用于索引的构建，如文献［11］使用B树来加快查询速度；文献［12］通过构造M树加快了对度量空间的索引过程。文献［10］提出一种基于相似查询树（SS树）的高效索引结构MRSE-SS。采用动态DK-MEDOIDS算法，通过限制中心点到最远成员之间的距离控制聚类的大小，在查询阶段，将用户提交的查询向量表示为一个超球体，云服务器通过判断查询向量所代表的超球体与相似查询树中节点所代表的超球体之间的位置关系进行判定，仅当查询向量与某领域构成的超球体有交集时才将该领域纳入结果集评价范围，递归执行这一步骤直至叶子节点，即可返回叶子节点中k个最相关的文档列表。但是在该方法中在构建超球体时最坏的时间复杂度会达到O（n2），且在查询算法传递回文档时，若最相关的超球体中文档数少于所查询的k个，则该方法不能解决这个问题，针对这两个问题，本文提出一种基于相似查询树的新型树形结构，该方法在索引建立阶段将聚类算法进行改进，与相似查询树进行结合，按照领域相关度将文档集合组织起来，采用动态的MDB算法，在文档初始化聚类时，通过该文档集的最大和最小文档向量差，等量的划分为k个槽，槽的大小为超球体的直径，把最接近槽中间向量的文档设置为超球体的中心，每个文档槽的大小视文档集的多少而定，随着文档数量的增加，对槽进行动态划分。同时使用相似查询树将不同领域的聚类组织起来，通过控制上级超球体中子节点超球体的数量，动态调整结构以达到新增体积最小的目标，直至生成根节点，与文献［10］在查询阶段相同，将用户提交的查询向量表示为一个超球体，云服务器通过判断查询向量所代表的超球体与相似查询树中节点所代表的超球体之间的位置关系进行判定，仅当查询向量与某领域构成的超球体有交集时才将该领域纳入结果集评价范围，递归执行这一步骤直至叶子节点，但在叶子节点本文算法不仅查询当前节点，并查询其左右邻居节点，按照相关比例返回节点中k个最相关的文档列表。

本文的贡献主要体现在以下两个方面：

1）对现有的MRSE-SS算法进行改进，提出相似查询树结构，提升多关键字排序检索的结果命中率。

2）提出一种基于极值差的动态聚类算法MDB，聚类过程随文档量增加而动态变化，其初始化时间复杂度为O（n），适用于大数据环境下的密文检索场景。

2 问题定义

2.1 系统模型

在本文中系统涉及三个实体，分别为数据拥有者，数据使用者和云服务器（如图1所示）。数据拥有者负责搜集数据，建立索引，并把数据和索引加密外包到云服务器上。除了关于数据的操作外，数据拥有者还具有为数据使用者授权的功能。数据使用者是查询请求的发起者和结果的接收者。云服务器提供了密文检索所需的大量存储空间和计算资源。一旦收到数据使用者的合法请求，云服务器需要返回和查询最相关的前k个文档，其中k值是由用户设定。系统的设计目标就是在不向服务器泄露文档信息的前提下，提高密文检索效率和命中率。

本文假定数据使用者是可信的，但是云服务器是半可信的。即云服务器会严格按照指令执行用户的操作请求，但会尽量观察和分析服务器上的数据和索引结构以期获知用户文档的内容。根据云服务器可以获得的信息，主要有以下的两种安全模型［8～9］。

已知密文模型：云服务器只知道用户外包到云上的数据，即加密后的文档集，相似查询树和加密后的查询超球体。

图1 密文检索的基本架构

已知背景信息模型：在这个模型中，云服务器不仅知道第一个模型中的所有信息，还可以统计和分析云服务器上的数据，例如：知道文档集的统计信息，进而推测出明文关键字。

2.2 评价标准

2.2.1 相似度

相似度评价中，本文采用了欧氏距离的方式进行度量。归一化后的向量内积值等价于两个向量之间的余弦值。计算方法如式（1）所示，其中x和y分别表示归一化后的两个不同的文档的向量。

2.2.2 检索结果集评价

较好的查询结果应该保持文档与文档之间的相似度。相似度高的文件容易同时被查询到，所以文档集中文档与文档之间的相似度可以由下式度量：

其中k′表示最终密文查询返回的k个文件，k表示明文查询中的top k个文件。

2.2 .3 信息泄露评价

本文采用了文献［11］中定义的信息泄露评价方法，即：使云服务器返回前k个文档，同时尽量少的向云服务器泄漏排序结果的信息。评估排序结果的信息泄露量按以下公式计算：其中Ci表示文档i在排序结果Top k中的位置，Ci′表示文档i在未添加随机值情况下的真实排序位置，从公式中可以看出，当Pk的值越大，说明查询结果隐藏的越好，信息泄露的越少。

2.3 关键词权重计算方法

本文使用了文献［3］定义的关键词的权重计算方法：

其中TF是特征项频率，即关键词在文档中出现的次数；IDF是逆文档频率，即和出现该关键词的文档个数成反比；ti表示关键词，N表示词典中词的个数，ni表示出现该词的文档个数。

2.4 符号定义

为使表达简洁和准确，我们定义了以下符号：

DC为明文文档向量集，表示为DC=｛d|d1，d2，…，dm｝，m表示文档数；

C为密文文档向量集，对应于明文文档集，表示为C=｛c|c1，c2，…，cm｝；

WC为词典，其中有n个关键字，表示为WC=｛w|w1，w2，…，wn｝；

m-SS树中非叶子节点的最少子元素个数，根节点除外；

M-SS树中非叶子节点的最多子元素个数，根节点除外；

D（Oi，Oj）表示两超球体球心Oi，Oj之间的距离；

Qw表示查询向量；

T表示一个聚类中能够容纳的最大文档向量个数；

r为最小超球面体的半径；

n为词典中关键字个数；

u是为了维护文档向量的安全性，添加的维度数目；

v是从u维度中随机选取的维度数目；

k是用户指定的返回文档数目；

2.5 DK-MEDOIDS聚类算法

传统算法［10］K-MEDOIDS的k值需要提前确定，可以在聚类的过程中随着文档数量的变化而动态变化，其标准测量函数如下：

其中p为聚类Ci中的点，Oi为聚类i的代表对象，即聚类中心，D（p，i）函数用于计算点p和点Oi之间的距离。算法分为以下几个步骤：

1）设置聚类中心和它的成员之间的距离门限值r，以及单个聚类中元素的门限值T。

2）在DC中随机的选择k个对象，每个对象代表一个簇的初始均值或中心。

3）在每个簇中，顺序选取一个元素，用该元素代替原来的聚类中心，计算得到各个元素和当前聚类中心的距离总和，选取距离和最小的元素作为中心。

4）检测各个聚类，是否存在元素和聚类中心距离大于r的情况，若存在则k=k+1，即加入一个新的聚类中心，并将异常点作为此新的聚类中心，重新执行第2）步。

5）直到所有的聚类中心不再变化。

6）检测所有聚类，成员元素是否超过门限值T，若存在，则对该聚类调用DK-MEDOIDS算法，生成子聚类。

7）检测所有元素和各个聚类中心之间的距离，若元素和当前聚类中心之间的距离小于r，并且该元素未在当前聚类中出现，则将该元素加入到当前聚类中。

在初始无序的文档中使用该算法将计算各个文档的相似度，也就是文档向量化后之间的距离，把相似的文档（向量距离度量小）聚类到一起，形成一个一个的聚类，每个聚类所包含的文档都是相似的，通过这样的方法将杂乱的文档进行分类，极大地提高了搜索文档的效率。

3 算法框架与算法设计

3.1 索引框架

索引框架主要由以下四个算法组成：生成密钥算法Keygen（1nu）；建立密文索引算法Build-index（DC，SK）；生成陷门算法Trapdoor（w，SK）；查询算法Search（Tw，k，I）。

Keygen（1n，u）：数据拥有者随机地生成了一个（n+u+1）位的向量作为分割指示向量S，同时生成两个（n+u+1）*（n+u+1）的可逆矩阵（M1，M2），组成密钥SK=｛S，M1，M2｝。

Build-index（DC，SK）：数据拥有者对每个文档生成一个n维的文档向量DC［i］，其中的每一位DC［i］［j］（0＜j＜n）记录关键词wj对应当前文档的权重［2］。调用BDM构建算法，对文档向量集DC建立B-SS索引I。其次将索引中所有节点的中心向量（包括每个超球体的球心向量和所有文档向量）从n维扩展到（n+u+1）维，其中（n+j）（0＜j＜u+1）为随机值Rj，最后一维（n+u+1）为1。然后通过向量S将索引所有节点的中心向量分割为两个子向量DC［i］［j］'和DC［i］［j］''，若Si为1，则DC［i］［j］'和DC［i］［j］''都为随机值，且它们之和为DC［i］［j］；若Si为0，则DC［i］［j］'=DC［i］［j］''=DC［i］［j］。此时索引向量I=｛I'，I''｝。最后通过两个矩阵M1和M2对索引I加密，即I=｛M1TI'，M2TI''｝，加密后的索引被上传到云端。

Trapdoor（w，SK）：用户根据关键字在词典中是否出现，设置Qw，如果在词典中出现，则对应位置的Qw［i］值为1，否则为0。随机的从u个关键字中选择v个，在Qw对应位置中设为1，其余位置设为0，最后一维取随机值t。再生成一个随机值q对Qw的前（n+u）维进行整体变化，即Qw=（q*Qw（n+u），t）。然后通过向量S对Qw进行分割，当Si值为1，Qw［i］'=Qw［i］''=Qw［i］，当Si值为0的时候，Qw［i］'和Qw［i］''取随机值，但它们的和为Qw［i］。通过矩阵M1和M2对Qw'和Qw''进行加密，陷门可以表示为三元组，Tw=｛M1-1Qw'，M2-1Qw''，r｝，其中r表示最小超球体的半径。

Search（Tw，k，I）：通过陷门Tw，服务器首先计算查询超球体和根节点各个超球体之间的关系，得到交集最多的某个超球体，然后根据得到的超球体，继续向下一层节点寻找，直到叶子节点。计算叶子节点中的文档向量和查询向量超球体的中心向量之间的距离，并计算邻近叶子节点的兄弟节点的距离，得到距离最近的前k个文档向量，并返回这k个文档向量的列表。

3.2 MDB聚类算法

DK-MEDOIDS算法［10］虽然解决了k值随文档的数量增加而动态的变化，但是在聚类初始化时，时间复杂度很高，并且随着文档数量变化时间复杂度也随之增高，因而在大数据的环境下并不适用，本文设计了基于极值差度量的聚类算法——MDB，其标准测量函数如下：

其中p为文档集中的点，Omax为文档集中向量最大的对象，Omin为文档集中向量最小的对象。

算法设计如下：

1）设置单个槽中元素的门限值T。

2）在初始化DC中选择向量值最大和最小的对象，分别做所有槽的上下界。

3）确定初始k值将DC化为等大小区间槽，利用式（6）将所有文档集放入对应槽中，选取其中与槽中心点最近的对象作为该聚类中心。

4）对于新加入DC的文档对象，检测与各个槽之间的距离，决定加入槽，并与当前中心点比较，若其与槽中心点向量差小于当前中心点，则将该对象替换为中心点，若超出原聚类的上下界则以该对象作为中心点，按比例建立新槽。

5）检测所有槽，成员元素是否超过门限值T，若存在，则对该槽调用MDB算法，生成子槽。

3.3 基于相似查询树的兄弟叶节点查询结构B-SS设计

相似查询树是R树的变形，它采用超球体进行空间的分割，相似查询树从下到上构建而成，上层节点为恰好覆盖下层节点的所有元素的超球体，每个节点由一个中心点和半径表示，若该节点为叶子节点，则中心点即为文档向量值，若为中间节点则表示超球体的球心。

因为算法MRSE-SS中对于查询返回的k个文档只是查询与查询超球体交集最大的超球体，对于有小部分交集的超球体并没有返回查询内容，然而用户所需文档可能在交集较小的超球体中出现，这样MRSE-SS就不能满足用户的需求，因此本文在设计索引框架时，将SS树的叶子节点加入指向其左右兄弟节点指针，因为当查询超球体与文档超球体所有交集最大时，其该文档超球体所相邻的超球体也必然有所交集（因为每个相邻超球体都是较相似的），所以当查询至叶子节点时（交集最大的超球体）同时查询其k个兄弟节点，按比例返回文档列表。

3.4 查询算法

文献［10］所提出查询算法是寻找和查询超球体有最大交集的超球体。但在实际查询中，文档也可能在其交集较小的超球体中命中，因而本文提出的查询算法的核心思想是寻找和查询超球体最大交集的超球体和其相邻的超球体，并按比例返回文档，查询超球体和相似查询树中的超球体的位置情况可分为包含、相交和不相交。用RQw表示查询超球体的半径，Rn表示相似查询树中的超球体半径。

相交的判定方法，如图2和式（7）所示。

包含的判定方法，如图2和式（8）所示。

不相交的判定方法，如图3和式（9）所示。

图2 两个超球体之间的相交和包含关系

图3 两个超球体之间的不相交关系

查询算法如下：

1）服务器首先计算查询超球体和根节点各个超球体之间的关系，得到交集最多的某个超球体。

2）根据得到的超球体，继续向下一层节点寻找交集最多的超球体。

3）重复步骤2），直到叶子节点，计算叶子节点和查询超球体球心OQw之间的距离。

4）找该叶子节点的左右邻居节点，按比例范围查找最近的k个文档。

4 性能分析

4.1 生成效率分析

在MRSE算法中，初始化生成超球体的算法时间复杂度在最坏的情况下，n代表文档个数。在MRSE-SS算法中，加入阈值r，从而初始化生成超球体算法的时间复杂度最坏情况下大于O（2n2），这显然在初始数据集数量庞大的情况下并不适用，而在本文所设计的算法中，初始化的工作时间复杂度仅为O（n），也就是说随着文档集的增加，初始化时间呈线性增长，这是可以接受的。

4.2 查询效率分析

相比于MRSE-SS算法查询阶段，云服务器使用新型的相似查询树索引文档，MRSE-SS所需要的操作如式（10）：

其中Bi表示相似查询树中第i层需要计算的节点的个数，l表示相似查询树的最大层数，m表示文档向量的个数，n表示词典里关键字的个数，t表示超球体中最小成员的个数，且t≤T，在本文算法中，所需查询时间为

其中k为交集最大叶子节点的左右兄弟节点的个数。通过公式表明与算法MRSE-SS一样，随着文档向量集DC呈指数增长，B-SS时间复杂度仅为O（l）。

4.3 性能分析

为了测试动态区间聚类算法MDB在真实数据集上的性能，我们建立了实验平台验证算法的效率。测试平台建立在Intel Core E3-v1230 3.30GZ的Windows上，采用模拟的不同的文档集个数和关键词数量，分别为256～8192篇文档，10～50个关键词。图4展示了DK-MEDOIDS算法与MDB算法的效率对比情况。

图4 不同文档的数量对算法初始化时间的影响

在图4中，当文档的个数呈指数增加时，DK-MEDOIDS算法的初始索引响应时间也是呈指数级增加，而MDB算法的响应时间近似线性增加并且时间很短，在文档数为3000个时，DK-MEDOIDS算法运行时间为20s左右，但MDB算法仅为0.13s；在图5中，文档数目固定为2000个时，当文档中关键词数目变化时，DK-MEDOIDS算法和MDB算法的初始索引时间相差也极大，但是当关键词数量在40个以内时，两个算法时间变化都很稳定，当关键词多于40时，DK-MEDOIDS算法时间变化较明显，而MDB算法时间依然稳定在很低的范围之内，说明MDB算法的初始时间不随文档中关键词数量变化而变化；图6中，文档数目依然固定为2000并且关键词数量为20个，当初始簇的个数变化时，DK-MEDOIDS算法生成时间随着簇的数目增多而递减（少于30时呈指数递减，多于30时呈线性递减）。MDB算法的生成时间随着槽的数目增多而呈线性增长。本次实验的模拟文档都采用归一化处理，并且数目控制在10000以内，因为文档数目过大时（例如100000），DK-MEDOIDS算法时间将变得无法估计，在长时间内无法完成运算，但是MDB算法依然在很短时间内运算完毕（1s之内），这说明MDB算法在时间效率方面要远远高于DK-MEDOIDS算法，但是MDB算法在运行中也出现无法解释的问题，初始文档多数都集中在某一个槽内，这样使MDB算法的查询效率要远远小于DK-MEDOIDS算法。

图5 不同关键词数量对算法初始化时间的影响

图6 不同簇的数目对算法初始化时间的影响

综合了以上对本文方案进行的正确性和效率的分析，可以看出本文提出MDB算法，具有如下特点：

1）MDB算法执行时间上远远小于DK-MEDOIDS算法，在三个影响因子（文档数量、关键词个数、槽个数）的不同取值下，MDB算法平均执行时间不足1s，针对大量的数据集来说，MDB算法具有明显的优势。

2）对MDB算法来说影响较大的因素是初始槽的个数，随着槽的个数的增加算法的执行时间也线性增加，对MDB算法来说执行时间受文档数量影响要远小于槽个数的影响，说明MDB算法适用于数据集大且槽个数偏小的情况。

3）MDB算法由于在分槽时过多的数据集中在某一个槽中，导致在执行效率上不如DK-MEDOIDS算法出色。

5 结语

针对初始超球体构建时间和查询超球体文档的问题，本文在MRSE-SS上进行改进，提出一种基于相似查询树的新型树形结构，并以MRSE-SS基础算法结构进行算法实现提出了动态的MDB算法，并建立了密文检索实验平台验证了本文所提方案的有效性。在实验中通过对文档数量、关键词个数、槽个数三个影响初始化执行时间的变量取不同的值，并对实验结果进行分析，实验结果证明MDB算法在初始化效率较传统的DK-MEDOIDS算法有了较大的提升，在大数据的环境下MDB算法具有明显的优势。