基于资源路由环的对等云区间搜索技术①

贺道德，胡如会

贵州工程应用技术学院 信息工程学院，贵州 毕节 551700

云计算是基于Internet来共享软硬件资源与数据的一种计算方式[1-2]，它运用虚拟的方式来整合资源，以实现用户便捷地使用共享资源． 目前，云计算中的服务与资源都由服务提供商控制，具有较好的可靠性与可控性，但由于云资源由少数服务提供商垄断，使得云的可扩展性不好，且成本偏高． 对等计算整合互联网中用户提供的资源来实现资源的共享，各用户的地位对等，资源的利用率高，且网络的可扩展性好[3]；但由于对等网络中的用户具有会话异构等特征，使得网络稳定性和可控性不够好． 由上述描述可知，对等计算技术和云计算技术相互补；运用对等计算技术架构底层网络，可充分利用资源且可扩展性好；然后利用云计算的虚拟技术以确保服务的可靠性与可用性，从而形成了对等云技术[4-6]．

运用结构化的对等计算系统构成的对等云采用分布式哈希表[7](DHT，Distributed Hash Table)来进行资源的发布与定位． 在资源发布时，先将资源关键字运用哈希算法(例如 SHA-1)计算出对象标识objId，然后将资源发布到与节点标识nodeId相近的节点上；在资源搜索时，亦依据哈希值来搜索． 由于哈希算法往往将属性值相近的资源映射成完全不相关的objId，然后将其发布到不相关的节点上，从而使其难以支持资源关键字区间搜索． 为实现在结构化对等云系统中进行区间搜索，本文提出如下思想：在资源发布时，运用同态加密[8-10]具有在密文状态下可进行操作的特征，首先将属性值VALUE使用具有同态特性的加密算法计算出FHVALUE，并运用此值计算出一个资源标记，拥有相似属性值的资源具有相同的资源标记；然后，再哈希FHVALUE得到objId，并将资源发布到对应nodeId的节点上；节点除存储资源外，还需依据资源标记将相同标记的资源节点链接成资源路由环． 在区间搜索时，运用同态加密过的属性值计算出资源标记，从而进行区间搜索． 为实现上述思想，本文采用典型的结构化对等系统Pastry[11]来构建对等云，运用同态加密算法GSW[12]来计算资源标记从而形成资源路由环．

1 相关研究

1.1 Pastry

莱斯大学与微软研究院共同提出的Pastry是采用DHT构造的结构化对等系统． 该系统中的每个节点都拥有一个128 b的nodeId，且为自组织重叠网络． 节点的nodeId在节点空间中(0～2128-1)标识节点的位置，由于散列值的随机性，使得节点nodeId在节点空间中能均匀分布． 当需要发布资源时，对资源属性值运用散列算法计算出资源objId，然后运用Pastry的路由算法将资源发布到节点nodeId与资源objId在数值上最接近的那个节点；在资源定位时，按此路由算法查找资源． 由于Pastry具有完全分布式特性，且自组织、扩展性好，因此，用其作为云系统的底层架构，可克服普通云系统扩展性不好、成本高的不足．

在Pastry系统中，每个节点维护3个状态表，包括一个路由表(R，Routing Table)，一个邻居节点集(N，Neighborhood Set)和一个叶子节点集(L，Leaf Set)． 系统运用上述状态表来维护网络的拓扑信息，文献[11]列举了节点标识为10233102的状态表，如图1所示．

图1 节点标识为10233102的状态表

图1中描述的节点标识为10233102，标识的构成采用2b进制，b取值为2． 路由表R中的每行包含2b-1个表项，R中的第n行的节点标识和当前节点标识的前n位相同(n从0开始)． 叶子节点集L存储的节点标识与当前节点标识值相近，其中包含两部分，前半部分的值略大于当前节点标识，后半部分的值则略小于当前节点标识． 邻居节点集N存放与当前节点物理位置相近的节点的nodeId，它主要用于维护路由的本地性[13]，在正常路由过程中并不被使用．

在Pastry系统中，若当前节点V收到一条路由信息，则首先从叶子节点集L中查找与路由信息中目标节点D的节点标识更接近的nodeId，若查找到，则路由到此节点． 第二步，在叶子节点中查找失败的情况下，转去查路由表R，计算出目标节点D与当前节点V的相同前缀长度j． 第三步，如果R中第j行的第Dj表项(Dj为目标节点标识中的第j个数值)不为空，则路由到此节点去． 第四步，若查找路由表失败，则从3个状态集中找一个和目标节点D标识最接近的节点，并路由到此节点． Pastry的路由算法(PR，Pastry Routing)如下所示．

R(i，j)：表示路由表R中第j行第i项

Li：表示叶子节点集L中第i项存储的节点标识(若为负数，则表示该标识小于当前节点标识)

Dj：目标节点D的第j个数值

shl(D，V)：节点D与节点V具有相同标识的前缀长度

Function PR(nodeId D)

1){/*该算法为对等云覆盖网络Pastry的主路由算法*/

2)if(L-|L|/2<=D<=L|L|/2){/*如果目标节点D在叶子节点集中*/

3)路由到节点Li，其中|D-Li|为最小；}

4)else{/*叶子节点集查找失败，则转查路由表R*/

5)j=shl(D，V)；/*计算目标节点D与当前节点V的相同标识前缀长度*/

6)if(R(Dj，j)!=NULL){/* 若路由表R的第j行的第Dj项不为空*/

7)路由到R(Dj，j)所存储的节点标识对应的节点；}

8)else{/*路由表查找失败*/

9)路由到节点T，T∈L∪R∪M，shl(T，D)>=j，|T-D|<|V-D|；}}

10)/*算法结束*/}

1.2 GSW

GSW是文献[12]中提出的一种基于容错学习(Learining With Error，LWE)的同态加密方案． GSW是运用矩阵与近似特征向量构造出的基于身份的全同态系统，它与传统同态加密方案不同的是该方案无需同态操作密钥亦可实现同态加密． 其基本方案是一个基于公钥的密码体系，其组成包括Setup，SecretKeyGen，PublicKeyGen，Enc，Dec和MPDec这6部分．

1)Setup(1λ，1L)，这是一个初始化操作． 选择一个k位的模数q，其中，k=k(λ，L)，λ为安全参数，L为方案的层数；格的维度值n=n(λ，L)；误差分布χ=χ(λ，L)，以确保容错学习方案的安全强度在攻击情况已知条件下达到2λ． 再次，选取参数m=m(λ，L)=O(nlogq)，令params=(n，q，χ，m)，=⎣logq+1，N=(n+1)·．

2)SecretKeyGen(params)，该部分用于生成私钥，其输入为参数params，样本t向量随机均匀分布在n维的Zq上，输出的私钥sk为向量s=(1，-t1，…，-tn)∈Zq(n+1维)，并令向量v=Powersof2(s)，Powersof2函数的输入为私钥向量s，输出向量v用于相关同态计算．

3)PublicKeyGen(params，sk)，该部分用于生成公钥，其输入为参数params与私钥sk，生成一个m*n矩阵B，且随机均匀分布在Zq上，并依据误差分布χ选取m维误差向量e←χm，计算出b=B·t+e，然后输出公钥pk=A=[b|B] (该A是在Zq上的m*(n+1)维矩阵)． 由于矩阵A与私钥向量s的乘积为误差向量e，从而确保了密钥的安全性．

4)Enc(params，pk，μ)，该部分为加密函数，μ为明文，其在空间Zq之内，pk为公钥，params为参数，其输出为密文矩阵C．

5)Dec(params，sk，C)，该部分为解密函数，C为密文，sk为私钥，params为参数，它可以在足够小的空间内恢复出明文μ．

6)MPDec(params，sk，C)，该解密函数由Micciancio 和 Peikert在文献[14]中提出，它可以恢复出明文μ二进制表示的全部有效位．

此外，GSW提供了一系列同态操作函数，包括同态数乘MultConst、同态加法Add、同态乘法Mult以及同态NAND门操作等．

2 基于资源路由环的对等云区间搜索拓扑模型

2.1 网络架构基础

为了在结构化的对等云中进行区间搜索，本文以如下网络架构为基础：

1)为了克服传统云存储系统因中心化而存在对云服务提供者信任依赖等问题，本文所提网络架构中的节点地位对等．

2)网络中的节点为稳定节点，以适应云存储的需求；为了描述区间搜索技术，本文对节点失效、会话异构等问题不做讨论．

3)本文以Pastry系统为基础构建网络，运用分布式哈希表来发布资源与定位，本文运用的哈希函数具有抗原像性、抗第二原像性以及强抗碰撞性等特征．

4)因考虑到目前流行的全同态算法存在加密速度慢，以及受搜索算法的搜索效率影响等问题，本文所提算法仅对资源属性值进行同态加密．

2.2 相关定义

为准确描述区间搜索模型及技术，本文对所涉及的相关定义描述如下：

定义1：节点标识，用以标识对等云网络中不同的节点，记为nodeId．

定义2：资源属性值，能够代表某资源相关特征的值，主要包括资源关键字、资源名以及所有者身份标识等，记为VALUE；同态加密后的资源属性值记为HFVALUE．

定义3：对象标识，用以唯一标识对等云网络中存储的资源对象，记为objId．

定义4：资源标记，又称为资源类型，具有相同类型的资源拥有相同的资源标记，记为TYPE．

定义5：路由环节点信息表(RRNT，Routing Ring Node Table)，用于构建资源路由环的数据结构，其中包括下一个存储同类型资源节点的节点标识、对象标识，具体定义如表1所示．

表1 路由环节点信息表

定义6：节点的资源信息表(SNT，Source Node Table)，用于对等云节点存储资源相关信息的数据结构，其中包括资源对象标识、资源密文属性值、资源标记，具体定义如表2所示．

表2 节点的资源信息表

2.3 网络拓扑模型

在结构化的对等系统中，由于采用散列函数的散列属性值来生成对象Id或节点Id，因此Id间没有关联性，仅适用于精确搜索．

为实现区间搜索，本对等云系统在Pastry系统的基础上，首先采用同态加密算法GSW对属性值进行加密，并且以密文的形式计算出资源标记；然后将相同资源标记的节点链在一起形成路由环以便区间搜索． 具体举例如下：现有相似资源(A，B，C，D)，为保证其机密性，运用GSW算法计算出密文属性(A′，B′，C′，D′)，再通过哈希函数计算得到其对象objId为(126，359，87，98)，并确定其资源标记为S；然后，将这些资源及其资源标记S发布到节点nodeId为(127，400，87，100)的节点上，并将这些节点构造成一个路由环，以便实现区间搜索，具体如图2所示．

图2 基于资源路由环的对等云区间搜索拓扑图

图2给出了基于资源路由环的对等云区间搜索拓扑图，从图中可以看出，相似属性的资源被发布到nodeId没有关联性的节点上，因此，不适合进行区间搜索． 为实现区间搜索，将存储相似资源的节点存储一个相同的资源标记S，然后通过链接形成一个路由环，本模型的具体构建方法如下所示．

1)运用Pastry系统的网络架构方案来构建对等网络．

2)结合同态加密算法计算出基于密文的资源标记．

3)在资源发布时，依据资源标记，将资源标记相同的同类型资源采用链式环的方法链接在一起，形成资源路由环．

3 基于资源路由环的对等云资源发布算法

为实现在对等云中进行区间搜索，资源应依据基于资源路由环的对等云区间搜索拓扑模型来进行发布． 第一步，首先依据资源的属性值VALUE按同态加密算法GSW计算出密文属性FHVALUE，然后对密文运用同态算法计算出资源标记，同种类型的资源拥有相同的资源标记S． 这样处理既确保属性值的机密性，又便于链接相同类型的资源形成资源路由环． 第二步，将资源密文属性FHVALUE按SHA-1算法哈希出对象标识objId；然后运用Pastry的路由算法PR发布路由消息，查找到与objId值相近的nodeId的网络节点N，然后将资源、资源标记以及资源其他信息发布到该节点上． 第三步，依据资源标记值，在对等云系统中查找一个拥有相同资源标记值的节点K；如果找到这样的节点K，则把K的路由环节点信息表(RRNT，Routing Ring Node Table)中记载的节点M的路由信息发送给节点N；节点N据此信息生成自己的RRNT，并将自己的路由信息发送给节点K，节点K依此信息更新RRNT表，从而实现节点N加入资源路由环． 如果在查找时，没有找到拥有相同资源标记的节点，说明该类型资源是第一次加入系统，则将自己的路由信息放入RRNT中． 基于资源路由环的对等云资源发布算法(RPARRR，Resource Publishing Algorithm based on Resource Routing Ring)如下所示．

Function RPARRR (VALUE V)

1){/* 该算法用于对等云系统资源发布，输入为资源属性值V */

2)/* 运用同态加密算法GSW计算出密文属性值FHV */

3)FHV=GSW(V)；

4)/*调用密文计算函数getSouTy计算资源标记S，并计算该类型数据区间最小值MIN与最大值MAX */

5)S=getSouTy(FHV)；

6)/* 运用SHA-1算法计算出对象标识objId */

7)objId=SHA-1(FHV)；

8)/*调用Pastry的路由算法PR，查找到资源存储节点N*/

9)N=PR(objId)；

10)将资源发布到节点N中；

11)/*调用资源定位算法RLART，查找具有相似标记S的资源节点*/

12)/* MIN至MAX为资源的属性区间*/

13)K=RLART(S，MIN，MAX)；

14)if(K!=NULL)

15){/* 如果查找到的节点K不为空*/

16)将K节点的路由环节点信息表RRNT中记载的路由信息发送给节点N；

17)节点N据此信息生成自己的RRNT；

18)将节点N的路由信息发送给节点K，节点K依据此信息更新其RRNT表；}

19)else{/*如果没有找到这样的节点，表示该节点是第一个节点*/

20)将节点N自己的路由信息存入RRNT；}

21)/*算法结束*/ }

4 基于资源路由环的对等云区间搜索技术

在基于资源路由环的对等云资源发布算法中，我们可以在不改变原有对等云结构的基础上，将存储相同类型资源的节点链接成一个资源路由环． 完成资源路由环设计后，下面的任务就是如何在基于资源路由环的对等云系统中进行资源的区间搜索．

4.1 依据资源类型进行资源定位

在资源发布算法中，节点在插入到某资源路由环之前，需按资源类型定位到该资源路由环． 因此，在给定一种资源类型后，如何在系统中查找到这种资源是本区间搜索技术的主要算法之一． 为实现该算法，本文提出了如下思想：由于本文所提的同类型资源定位算法采用基于密文搜索的机制，因此，若用户已知资源类型为明文M，则在其明文区间[MMIN，MMAX]中随机选择一个值V，运用同态加密机制运算出其资源标记S，及其属性值区间[MIN，MAX]． 第一步，用户在资源属性值区间中运用随机函数计算得到一个密文属性值FHV，然后，依据SHA-1算法计算出该属性值的对象标识objId． 第二步，运用对等云系统的路由算法PR路由到节点K，查看K节点是否存在资源标记为S的资源，如果存在，则查找结束并返回成功． 第三步，如果没有找到，则重新在属性区间中随机产生一个新的密文属性值FHV′，重新搜索． 第四步，直到搜索到此种类型的资源，返回成功算法结束；或者搜索次数超限返回失败算法结束． 依据资源类型进行资源定位的算法(RLART，Resource Location Algorithm based on Resource Type)如下所示．

Function RLART(TYPE S，FHVALUE MIN ，FHVALUE MAX)

1){/*该算法在给定资源类型标记的情况下进行资源定位，算法返回值为资源存储所在节点的标识*/

2)count=0；/*count变量用来记载搜索次数，最大值为MaxCount */

3)flag=0；/* flag变量为是否搜索成功标记，查找成功时，该值为1*/

4)while(count<=MaxCount)

5){/*在S类资源的属性值区间内随机产生一个属性值FHV */

6)FHV=random(S，MIN，MAX)；

7)objId=SHA-1(FHV)；/* 运用SHA-1算法计算出对象标识objId */

8)/*调用Pastry的路由算法PR，将资源发布到路由到的节点K*/

9)K=PR(objId)；

10)forEach(id in 节点K的SNT)

11){/* 遍历K节点的资源信息表*/

12)if(id==objId)/* 如果查找的资源对象标识找到 */

13){flag=1；

14)break；/*在查找成功时，中止循环*/}}

15)if(flag==1)break；

16)count++；/*计数器自加*/}

17)if(flag==0){/*没有查找到对应资源的节点时，返回空值*/

18)return NULL；}

19)else{/* 若找到对应资源的节点时，返回节点的标识 */

20)return K.nodeId；}

21)/*算法结束*/ }

该算法在不改变对等云覆盖网络结构的基础上构建，具有较强的自适应性，既支持密文资源定位，也支持明文资源定位；用户在拥有明文的情况下进行定位时，为确保操作过程的机密性，只需在调用该算法前进行一次同态密码运算即可完成．

4.2 基于资源路由环的区间定位

在以资源路由环的方式发布资源后，在对等云系统中，拥有相同资源的节点通过存储相同资源标记的路由信息后，形成资源路由环；本小节将描述在资源路由环中如何进行区间搜索． 首先，当用户搜索关键字区间为[V1，V2] 时，若关键字为明文，则运用同态加密机制计算出密文区间[FHV1，FHV2]，并计算出资源标记S． 第二步，依据资源标记值S，通过资源定位算法RLART搜索到存储该类型资源的节点N． 第三步，以节点N为起始节点，在资源路由环中比对搜索区间关键字；若在此区间，则将存储资源节点的节点标识返回给用户，直至遍历资源路由环结束． 基于资源路由环的区间定位算法(ILARRR，Interval Location Algorithm based on Resource Routing Ring)如下所示．

Function ILARRR(FHVALUE FHV1，FHVALUE FHV2)

1){/*该算法实现在对等云系统中进行区间搜索，区间为[FHV1，FHV2]，FHVALUE为同态密文属性类型*/

2)/*调用密文计算函数getSouTy计算出资源标记S，并计算出该类型数据区间最值MIN与MAX */

3)S=getSouTy(FHV1)；

4)/* 调用依据资源标记定位资源算法RLART查找第一个存储S类资源的节点N */

5)N=RLART(S，MIN，MAX)；

6)if(N!=NULL){/*如N节点不为空，以N为第一个节点遍历资源路由环*/

7)I=N；/*用临时变量I存储拥有S类资源的节点的路由信息*/

8)定义集合SourNode[]存储资源节点的路由信息；

9)j=0；

10)do{

11)forEach(id in节点I的SNT)

12){/*遍历I节点的资源信息表*/

13)if(id>=FHV1&&id<=FHV2)/* 如果查找的资源属性值在搜索区间之内 */

14){SourNode[j].nodeId =I.nodeId；/*将I节点的路由信息存入资源节点集合SourNode*/

15)j++；

16)break；}}

17)I=I.RRNT.nodeId；/* 取出I节点的路由环节点信息表中的路由节点作为下一查找的节点 */

18)}while(I.nodeId !=N.nodeId)；/* 循环到路由起点结束*/

19)}else return NULL；/*搜索失败，返回空值*/

20)if(j>0){

21)/*搜索成功，返回资源节点集合*/

22)return SourNode；

23)}else{/*搜索失败，返回空值*/

24)return NULL；}

25)/*算法结束*/}

上述算法的输入为密文属性区间，若用户在已知明文区间的情况下进行区间搜索，则需运用同态加密机制计算出密文区间，然后调用此算法来完成基于资源路由环的区间定位．

4.3 区间搜索效率分析

本文提出的区间搜索算法通过改进Pastry对等系统，运用资源路由环实现了密文资源区间的搜索，本搜索算法的路由开销包括在Pastry网络中的路由开销以及在路由环中的路由开销，现就其搜索效率分析如下：

2)找到资源路由环入口后，ILARRR算法运用遍历环中资源节点的方法搜索资源，因此，其路由开销与环的大小成正比；在资源规模较小的情况下，环内路由开销远远小于该算法调用RLART算法搜索环入口的路由开销． 但若资源规模增大，环内搜索势必成为主要的搜索开销之一，因此，为提高搜索效率，本文提出如下改进措施：

① 在资源发布时，以资源属性值为关键字来构建有序链表的资源路由环；

② 在资源定位时，运用资源路由环的有序性，优化查找算法，以达到在资源路由环内的搜索效率最优．

5 仿真与性能分析

为了验证运用结构化对等系统Pastry作为对等云覆盖网络的有效性，我们选择FreePastry为原型仿真器[15]来进行仿真测试，网络规模确定其最大值为10 000个网络节点；节点标识的构成采用16进制，N的大小为|N|=32，L的大小为|L|=16． 为了实现密文下的区间搜索，运用资源发布算法发布资源，设定算法RLART的最大搜索次数为10次，资源类型数量为200种；搜索区间的确定方法为从不同类型资源的属性区间中随机抽取． 实验主要测试了网络规模与路由开销之间的关系，以及路由开销与搜索区间长度之间的关系．

在测试网络规模与路由开销之间的关系时，从200种资源中随机抽取资源，并确定搜索区间的长度为20个节点，网络节点数量从1 000个增加至最大值10 000个，增值长度为500；最终在不同网络规模下进行了100次实验，取其均值，获得的平均路由开销与网络规模的关系如图3所示．

图3为网络节点个数与平均路由跳数之间的关系，其中横坐标为网络节点数(个)，纵坐标为平均路由开销，单位为步跳数(hops)． 从图3可以看出，网络规模从1 000增至10 000个节点的过程中，区间搜索的平均路由开销的增长接近线性增长趋势． 得到上述实验结果的原因是：本文所提的对等云系统采用资源路由环进行构造，即将存储同种类型资源的节点运用链接的方式形成一个资源环，在路由查找过程中，主要开销为基本覆盖网络的路由开销，因此，平均路由开销与网络规模成正比关系．

图3 平均路由开销与网络规模关系图

区间搜索相比于精确搜索，其搜索的数据量大；常规情况下，搜索区间包含的节点个数越多，则路由开销也会越大． 因此，搜索区间长度与路由开销间的关系是区间搜索的重要评估指标． 在测试时，我们确定网络规模为2 000个节点，搜索区间长度从10个节点增至100个节点，增值长度为10；从200种资源中随机抽取资源，在不同的搜索区间长度下完成了100次实验，取其平均路由开销． 平均路由开销与搜索区间长度之间的关系如图4所示．

图4 平均路由开销与搜索区间长度关系图

图4为搜索区间长度与平均路由跳数之间的关系，横坐标为搜索区间长度，单位为搜索区间内资源数量(个)，纵坐标为平均路由跳数，单位为hops． 从图中可以看出，随着搜索区间的增大，其平均路由跳数的增长趋于平缓． 出现上述实验结果的原因是：本系统运用资源路由环构造，在路由过程中，主要开销在于查找第一个资源，并且资源路由环中的路由开销不大．

6 结束语

本文运用结构化的对等系统来构建云系统的覆盖网络，采用将存储相同类型资源的节点链接成资源路由环，从而解决结构化的对等云系统不适合区间搜索的问题． 另外，为确保数据的机密性，运用同态加密机制来实现密文下的资源搜索． 同态加密时间复杂性较大，本系统仅对资源属性值进行了同态加密． 下一步的工作将优化同态加密算法，以使其在对等云系统中进行密文运算时不受条件限制．