基于資源路由環(huán)的對(duì)等云區(qū)間搜索技術(shù)①

賀道德，胡如會(huì)

貴州工程應(yīng)用技術(shù)學(xué)院 信息工程學(xué)院，貴州 畢節(jié) 551700

云計(jì)算是基于Internet來(lái)共享軟硬件資源與數(shù)據(jù)的一種計(jì)算方式[1-2]，它運(yùn)用虛擬的方式來(lái)整合資源，以實(shí)現(xiàn)用戶(hù)便捷地使用共享資源． 目前，云計(jì)算中的服務(wù)與資源都由服務(wù)提供商控制，具有較好的可靠性與可控性，但由于云資源由少數(shù)服務(wù)提供商壟斷，使得云的可擴(kuò)展性不好，且成本偏高． 對(duì)等計(jì)算整合互聯(lián)網(wǎng)中用戶(hù)提供的資源來(lái)實(shí)現(xiàn)資源的共享，各用戶(hù)的地位對(duì)等，資源的利用率高，且網(wǎng)絡(luò)的可擴(kuò)展性好[3]；但由于對(duì)等網(wǎng)絡(luò)中的用戶(hù)具有會(huì)話異構(gòu)等特征，使得網(wǎng)絡(luò)穩(wěn)定性和可控性不夠好． 由上述描述可知，對(duì)等計(jì)算技術(shù)和云計(jì)算技術(shù)相互補(bǔ)；運(yùn)用對(duì)等計(jì)算技術(shù)架構(gòu)底層網(wǎng)絡(luò)，可充分利用資源且可擴(kuò)展性好；然后利用云計(jì)算的虛擬技術(shù)以確保服務(wù)的可靠性與可用性，從而形成了對(duì)等云技術(shù)[4-6]．

運(yùn)用結(jié)構(gòu)化的對(duì)等計(jì)算系統(tǒng)構(gòu)成的對(duì)等云采用分布式哈希表[7](DHT，Distributed Hash Table)來(lái)進(jìn)行資源的發(fā)布與定位． 在資源發(fā)布時(shí)，先將資源關(guān)鍵字運(yùn)用哈希算法(例如 SHA-1)計(jì)算出對(duì)象標(biāo)識(shí)objId，然后將資源發(fā)布到與節(jié)點(diǎn)標(biāo)識(shí)nodeId相近的節(jié)點(diǎn)上；在資源搜索時(shí)，亦依據(jù)哈希值來(lái)搜索． 由于哈希算法往往將屬性值相近的資源映射成完全不相關(guān)的objId，然后將其發(fā)布到不相關(guān)的節(jié)點(diǎn)上，從而使其難以支持資源關(guān)鍵字區(qū)間搜索． 為實(shí)現(xiàn)在結(jié)構(gòu)化對(duì)等云系統(tǒng)中進(jìn)行區(qū)間搜索，本文提出如下思想：在資源發(fā)布時(shí)，運(yùn)用同態(tài)加密[8-10]具有在密文狀態(tài)下可進(jìn)行操作的特征，首先將屬性值VALUE使用具有同態(tài)特性的加密算法計(jì)算出FHVALUE，并運(yùn)用此值計(jì)算出一個(gè)資源標(biāo)記，擁有相似屬性值的資源具有相同的資源標(biāo)記；然后，再哈希FHVALUE得到objId，并將資源發(fā)布到對(duì)應(yīng)nodeId的節(jié)點(diǎn)上；節(jié)點(diǎn)除存儲(chǔ)資源外，還需依據(jù)資源標(biāo)記將相同標(biāo)記的資源節(jié)點(diǎn)鏈接成資源路由環(huán)． 在區(qū)間搜索時(shí)，運(yùn)用同態(tài)加密過(guò)的屬性值計(jì)算出資源標(biāo)記，從而進(jìn)行區(qū)間搜索． 為實(shí)現(xiàn)上述思想，本文采用典型的結(jié)構(gòu)化對(duì)等系統(tǒng)Pastry[11]來(lái)構(gòu)建對(duì)等云，運(yùn)用同態(tài)加密算法GSW[12]來(lái)計(jì)算資源標(biāo)記從而形成資源路由環(huán)．

1 相關(guān)研究

1.1 Pastry

萊斯大學(xué)與微軟研究院共同提出的Pastry是采用DHT構(gòu)造的結(jié)構(gòu)化對(duì)等系統(tǒng)． 該系統(tǒng)中的每個(gè)節(jié)點(diǎn)都擁有一個(gè)128 b的nodeId，且為自組織重疊網(wǎng)絡(luò)． 節(jié)點(diǎn)的nodeId在節(jié)點(diǎn)空間中(0～2128-1)標(biāo)識(shí)節(jié)點(diǎn)的位置，由于散列值的隨機(jī)性，使得節(jié)點(diǎn)nodeId在節(jié)點(diǎn)空間中能均勻分布． 當(dāng)需要發(fā)布資源時(shí)，對(duì)資源屬性值運(yùn)用散列算法計(jì)算出資源objId，然后運(yùn)用Pastry的路由算法將資源發(fā)布到節(jié)點(diǎn)nodeId與資源objId在數(shù)值上最接近的那個(gè)節(jié)點(diǎn)；在資源定位時(shí)，按此路由算法查找資源． 由于Pastry具有完全分布式特性，且自組織、擴(kuò)展性好，因此，用其作為云系統(tǒng)的底層架構(gòu)，可克服普通云系統(tǒng)擴(kuò)展性不好、成本高的不足．

在Pastry系統(tǒng)中，每個(gè)節(jié)點(diǎn)維護(hù)3個(gè)狀態(tài)表，包括一個(gè)路由表(R，Routing Table)，一個(gè)鄰居節(jié)點(diǎn)集(N，Neighborhood Set)和一個(gè)葉子節(jié)點(diǎn)集(L，Leaf Set)． 系統(tǒng)運(yùn)用上述狀態(tài)表來(lái)維護(hù)網(wǎng)絡(luò)的拓?fù)湫畔ⅲ墨I(xiàn)[11]列舉了節(jié)點(diǎn)標(biāo)識(shí)為10233102的狀態(tài)表，如圖1所示．

圖1 節(jié)點(diǎn)標(biāo)識(shí)為10233102的狀態(tài)表

圖1中描述的節(jié)點(diǎn)標(biāo)識(shí)為10233102，標(biāo)識(shí)的構(gòu)成采用2b進(jìn)制，b取值為2． 路由表R中的每行包含2b-1個(gè)表項(xiàng)，R中的第n行的節(jié)點(diǎn)標(biāo)識(shí)和當(dāng)前節(jié)點(diǎn)標(biāo)識(shí)的前n位相同(n從0開(kāi)始)． 葉子節(jié)點(diǎn)集L存儲(chǔ)的節(jié)點(diǎn)標(biāo)識(shí)與當(dāng)前節(jié)點(diǎn)標(biāo)識(shí)值相近，其中包含兩部分，前半部分的值略大于當(dāng)前節(jié)點(diǎn)標(biāo)識(shí)，后半部分的值則略小于當(dāng)前節(jié)點(diǎn)標(biāo)識(shí)． 鄰居節(jié)點(diǎn)集N存放與當(dāng)前節(jié)點(diǎn)物理位置相近的節(jié)點(diǎn)的nodeId，它主要用于維護(hù)路由的本地性[13]，在正常路由過(guò)程中并不被使用．

在Pastry系統(tǒng)中，若當(dāng)前節(jié)點(diǎn)V收到一條路由信息，則首先從葉子節(jié)點(diǎn)集L中查找與路由信息中目標(biāo)節(jié)點(diǎn)D的節(jié)點(diǎn)標(biāo)識(shí)更接近的nodeId，若查找到，則路由到此節(jié)點(diǎn)． 第二步，在葉子節(jié)點(diǎn)中查找失敗的情況下，轉(zhuǎn)去查路由表R，計(jì)算出目標(biāo)節(jié)點(diǎn)D與當(dāng)前節(jié)點(diǎn)V的相同前綴長(zhǎng)度j． 第三步，如果R中第j行的第Dj表項(xiàng)(Dj為目標(biāo)節(jié)點(diǎn)標(biāo)識(shí)中的第j個(gè)數(shù)值)不為空，則路由到此節(jié)點(diǎn)去． 第四步，若查找路由表失敗，則從3個(gè)狀態(tài)集中找一個(gè)和目標(biāo)節(jié)點(diǎn)D標(biāo)識(shí)最接近的節(jié)點(diǎn)，并路由到此節(jié)點(diǎn)． Pastry的路由算法(PR，Pastry Routing)如下所示．

R(i，j)：表示路由表R中第j行第i項(xiàng)

Li：表示葉子節(jié)點(diǎn)集L中第i項(xiàng)存儲(chǔ)的節(jié)點(diǎn)標(biāo)識(shí)(若為負(fù)數(shù)，則表示該標(biāo)識(shí)小于當(dāng)前節(jié)點(diǎn)標(biāo)識(shí))

Dj：目標(biāo)節(jié)點(diǎn)D的第j個(gè)數(shù)值

shl(D，V)：節(jié)點(diǎn)D與節(jié)點(diǎn)V具有相同標(biāo)識(shí)的前綴長(zhǎng)度

Function PR(nodeId D)

1){/*該算法為對(duì)等云覆蓋網(wǎng)絡(luò)Pastry的主路由算法*/

2)if(L-|L|/2<=D<=L|L|/2){/*如果目標(biāo)節(jié)點(diǎn)D在葉子節(jié)點(diǎn)集中*/

3)路由到節(jié)點(diǎn)Li，其中|D-Li|為最?。粆

4)else{/*葉子節(jié)點(diǎn)集查找失敗，則轉(zhuǎn)查路由表R*/

5)j=shl(D，V)；/*計(jì)算目標(biāo)節(jié)點(diǎn)D與當(dāng)前節(jié)點(diǎn)V的相同標(biāo)識(shí)前綴長(zhǎng)度*/

6)if(R(Dj，j)!=NULL){/* 若路由表R的第j行的第Dj項(xiàng)不為空*/

7)路由到R(Dj，j)所存儲(chǔ)的節(jié)點(diǎn)標(biāo)識(shí)對(duì)應(yīng)的節(jié)點(diǎn)；}

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

9)路由到節(jié)點(diǎn)T，T∈L∪R∪M，shl(T，D)>=j，|T-D|<|V-D|；}}

10)/*算法結(jié)束*/}

1.2 GSW

GSW是文獻(xiàn)[12]中提出的一種基于容錯(cuò)學(xué)習(xí)(Learining With Error，LWE)的同態(tài)加密方案． GSW是運(yùn)用矩陣與近似特征向量構(gòu)造出的基于身份的全同態(tài)系統(tǒng)，它與傳統(tǒng)同態(tài)加密方案不同的是該方案無(wú)需同態(tài)操作密鑰亦可實(shí)現(xiàn)同態(tài)加密． 其基本方案是一個(gè)基于公鑰的密碼體系，其組成包括Setup，SecretKeyGen，PublicKeyGen，Enc，Dec和MPDec這6部分．

1)Setup(1λ，1L)，這是一個(gè)初始化操作． 選擇一個(gè)k位的模數(shù)q，其中，k=k(λ，L)，λ為安全參數(shù)，L為方案的層數(shù)；格的維度值n=n(λ，L)；誤差分布χ=χ(λ，L)，以確保容錯(cuò)學(xué)習(xí)方案的安全強(qiáng)度在攻擊情況已知條件下達(dá)到2λ． 再次，選取參數(shù)m=m(λ，L)=O(nlogq)，令params=(n，q，χ，m)，=?logq+1，N=(n+1)·．

2)SecretKeyGen(params)，該部分用于生成私鑰，其輸入為參數(shù)params，樣本t向量隨機(jī)均勻分布在n維的Zq上，輸出的私鑰sk為向量s=(1，-t1，…，-tn)∈Zq(n+1維)，并令向量v=Powersof2(s)，Powersof2函數(shù)的輸入為私鑰向量s，輸出向量v用于相關(guān)同態(tài)計(jì)算．

3)PublicKeyGen(params，sk)，該部分用于生成公鑰，其輸入為參數(shù)params與私鑰sk，生成一個(gè)m*n矩陣B，且隨機(jī)均勻分布在Zq上，并依據(jù)誤差分布χ選取m維誤差向量e←χm，計(jì)算出b=B·t+e，然后輸出公鑰pk=A=[b|B] (該A是在Zq上的m*(n+1)維矩陣)． 由于矩陣A與私鑰向量s的乘積為誤差向量e，從而確保了密鑰的安全性．

4)Enc(params，pk，μ)，該部分為加密函數(shù)，μ為明文，其在空間Zq之內(nèi)，pk為公鑰，params為參數(shù)，其輸出為密文矩陣C．

5)Dec(params，sk，C)，該部分為解密函數(shù)，C為密文，sk為私鑰，params為參數(shù)，它可以在足夠小的空間內(nèi)恢復(fù)出明文μ．

6)MPDec(params，sk，C)，該解密函數(shù)由Micciancio 和 Peikert在文獻(xiàn)[14]中提出，它可以恢復(fù)出明文μ二進(jìn)制表示的全部有效位．

此外，GSW提供了一系列同態(tài)操作函數(shù)，包括同態(tài)數(shù)乘MultConst、同態(tài)加法Add、同態(tài)乘法Mult以及同態(tài)NAND門(mén)操作等．

2 基于資源路由環(huán)的對(duì)等云區(qū)間搜索拓?fù)淠Ｐ?/h2>

2.1 網(wǎng)絡(luò)架構(gòu)基礎(chǔ)

為了在結(jié)構(gòu)化的對(duì)等云中進(jìn)行區(qū)間搜索，本文以如下網(wǎng)絡(luò)架構(gòu)為基礎(chǔ)：

1)為了克服傳統(tǒng)云存儲(chǔ)系統(tǒng)因中心化而存在對(duì)云服務(wù)提供者信任依賴(lài)等問(wèn)題，本文所提網(wǎng)絡(luò)架構(gòu)中的節(jié)點(diǎn)地位對(duì)等．

2)網(wǎng)絡(luò)中的節(jié)點(diǎn)為穩(wěn)定節(jié)點(diǎn)，以適應(yīng)云存儲(chǔ)的需求；為了描述區(qū)間搜索技術(shù)，本文對(duì)節(jié)點(diǎn)失效、會(huì)話異構(gòu)等問(wèn)題不做討論．

3)本文以Pastry系統(tǒng)為基礎(chǔ)構(gòu)建網(wǎng)絡(luò)，運(yùn)用分布式哈希表來(lái)發(fā)布資源與定位，本文運(yùn)用的哈希函數(shù)具有抗原像性、抗第二原像性以及強(qiáng)抗碰撞性等特征．

4)因考慮到目前流行的全同態(tài)算法存在加密速度慢，以及受搜索算法的搜索效率影響等問(wèn)題，本文所提算法僅對(duì)資源屬性值進(jìn)行同態(tài)加密．

2.2 相關(guān)定義

為準(zhǔn)確描述區(qū)間搜索模型及技術(shù)，本文對(duì)所涉及的相關(guān)定義描述如下：

定義1：節(jié)點(diǎn)標(biāo)識(shí)，用以標(biāo)識(shí)對(duì)等云網(wǎng)絡(luò)中不同的節(jié)點(diǎn)，記為nodeId．

定義2：資源屬性值，能夠代表某資源相關(guān)特征的值，主要包括資源關(guān)鍵字、資源名以及所有者身份標(biāo)識(shí)等，記為VALUE；同態(tài)加密后的資源屬性值記為HFVALUE．

定義3：對(duì)象標(biāo)識(shí)，用以唯一標(biāo)識(shí)對(duì)等云網(wǎng)絡(luò)中存儲(chǔ)的資源對(duì)象，記為objId．

定義4：資源標(biāo)記，又稱(chēng)為資源類(lèi)型，具有相同類(lèi)型的資源擁有相同的資源標(biāo)記，記為T(mén)YPE．

定義5：路由環(huán)節(jié)點(diǎn)信息表(RRNT，Routing Ring Node Table)，用于構(gòu)建資源路由環(huán)的數(shù)據(jù)結(jié)構(gòu)，其中包括下一個(gè)存儲(chǔ)同類(lèi)型資源節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識(shí)、對(duì)象標(biāo)識(shí)，具體定義如表1所示．

表1 路由環(huán)節(jié)點(diǎn)信息表

定義6：節(jié)點(diǎn)的資源信息表(SNT，Source Node Table)，用于對(duì)等云節(jié)點(diǎn)存儲(chǔ)資源相關(guān)信息的數(shù)據(jù)結(jié)構(gòu)，其中包括資源對(duì)象標(biāo)識(shí)、資源密文屬性值、資源標(biāo)記，具體定義如表2所示．

表2 節(jié)點(diǎn)的資源信息表

2.3 網(wǎng)絡(luò)拓?fù)淠Ｐ?/h3>

在結(jié)構(gòu)化的對(duì)等系統(tǒng)中，由于采用散列函數(shù)的散列屬性值來(lái)生成對(duì)象Id或節(jié)點(diǎn)Id，因此Id間沒(méi)有關(guān)聯(lián)性，僅適用于精確搜索．

為實(shí)現(xiàn)區(qū)間搜索，本對(duì)等云系統(tǒng)在Pastry系統(tǒng)的基礎(chǔ)上，首先采用同態(tài)加密算法GSW對(duì)屬性值進(jìn)行加密，并且以密文的形式計(jì)算出資源標(biāo)記；然后將相同資源標(biāo)記的節(jié)點(diǎn)鏈在一起形成路由環(huán)以便區(qū)間搜索． 具體舉例如下：現(xiàn)有相似資源(A，B，C，D)，為保證其機(jī)密性，運(yùn)用GSW算法計(jì)算出密文屬性(A′，B′，C′，D′)，再通過(guò)哈希函數(shù)計(jì)算得到其對(duì)象objId為(126，359，87，98)，并確定其資源標(biāo)記為S；然后，將這些資源及其資源標(biāo)記S發(fā)布到節(jié)點(diǎn)nodeId為(127，400，87，100)的節(jié)點(diǎn)上，并將這些節(jié)點(diǎn)構(gòu)造成一個(gè)路由環(huán)，以便實(shí)現(xiàn)區(qū)間搜索，具體如圖2所示．

圖2 基于資源路由環(huán)的對(duì)等云區(qū)間搜索拓?fù)鋱D

圖2給出了基于資源路由環(huán)的對(duì)等云區(qū)間搜索拓?fù)鋱D，從圖中可以看出，相似屬性的資源被發(fā)布到nodeId沒(méi)有關(guān)聯(lián)性的節(jié)點(diǎn)上，因此，不適合進(jìn)行區(qū)間搜索． 為實(shí)現(xiàn)區(qū)間搜索，將存儲(chǔ)相似資源的節(jié)點(diǎn)存儲(chǔ)一個(gè)相同的資源標(biāo)記S，然后通過(guò)鏈接形成一個(gè)路由環(huán)，本模型的具體構(gòu)建方法如下所示．

1)運(yùn)用Pastry系統(tǒng)的網(wǎng)絡(luò)架構(gòu)方案來(lái)構(gòu)建對(duì)等網(wǎng)絡(luò)．

2)結(jié)合同態(tài)加密算法計(jì)算出基于密文的資源標(biāo)記．

3)在資源發(fā)布時(shí)，依據(jù)資源標(biāo)記，將資源標(biāo)記相同的同類(lèi)型資源采用鏈?zhǔn)江h(huán)的方法鏈接在一起，形成資源路由環(huán)．

3 基于資源路由環(huán)的對(duì)等云資源發(fā)布算法

為實(shí)現(xiàn)在對(duì)等云中進(jìn)行區(qū)間搜索，資源應(yīng)依據(jù)基于資源路由環(huán)的對(duì)等云區(qū)間搜索拓?fù)淠Ｐ蛠?lái)進(jìn)行發(fā)布． 第一步，首先依據(jù)資源的屬性值VALUE按同態(tài)加密算法GSW計(jì)算出密文屬性FHVALUE，然后對(duì)密文運(yùn)用同態(tài)算法計(jì)算出資源標(biāo)記，同種類(lèi)型的資源擁有相同的資源標(biāo)記S． 這樣處理既確保屬性值的機(jī)密性，又便于鏈接相同類(lèi)型的資源形成資源路由環(huán)． 第二步，將資源密文屬性FHVALUE按SHA-1算法哈希出對(duì)象標(biāo)識(shí)objId；然后運(yùn)用Pastry的路由算法PR發(fā)布路由消息，查找到與objId值相近的nodeId的網(wǎng)絡(luò)節(jié)點(diǎn)N，然后將資源、資源標(biāo)記以及資源其他信息發(fā)布到該節(jié)點(diǎn)上． 第三步，依據(jù)資源標(biāo)記值，在對(duì)等云系統(tǒng)中查找一個(gè)擁有相同資源標(biāo)記值的節(jié)點(diǎn)K；如果找到這樣的節(jié)點(diǎn)K，則把K的路由環(huán)節(jié)點(diǎn)信息表(RRNT，Routing Ring Node Table)中記載的節(jié)點(diǎn)M的路由信息發(fā)送給節(jié)點(diǎn)N；節(jié)點(diǎn)N據(jù)此信息生成自己的RRNT，并將自己的路由信息發(fā)送給節(jié)點(diǎn)K，節(jié)點(diǎn)K依此信息更新RRNT表，從而實(shí)現(xiàn)節(jié)點(diǎn)N加入資源路由環(huán)． 如果在查找時(shí)，沒(méi)有找到擁有相同資源標(biāo)記的節(jié)點(diǎn)，說(shuō)明該類(lèi)型資源是第一次加入系統(tǒng)，則將自己的路由信息放入RRNT中． 基于資源路由環(huán)的對(duì)等云資源發(fā)布算法(RPARRR，Resource Publishing Algorithm based on Resource Routing Ring)如下所示．

Function RPARRR (VALUE V)

1){/* 該算法用于對(duì)等云系統(tǒng)資源發(fā)布，輸入為資源屬性值V */

2)/* 運(yùn)用同態(tài)加密算法GSW計(jì)算出密文屬性值FHV */

3)FHV=GSW(V)；

4)/*調(diào)用密文計(jì)算函數(shù)getSouTy計(jì)算資源標(biāo)記S，并計(jì)算該類(lèi)型數(shù)據(jù)區(qū)間最小值MIN與最大值MAX */

5)S=getSouTy(FHV)；

6)/* 運(yùn)用SHA-1算法計(jì)算出對(duì)象標(biāo)識(shí)objId */

7)objId=SHA-1(FHV)；

8)/*調(diào)用Pastry的路由算法PR，查找到資源存儲(chǔ)節(jié)點(diǎn)N*/

9)N=PR(objId)；

10)將資源發(fā)布到節(jié)點(diǎn)N中；

11)/*調(diào)用資源定位算法RLART，查找具有相似標(biāo)記S的資源節(jié)點(diǎn)*/

12)/* MIN至MAX為資源的屬性區(qū)間*/

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

14)if(K!=NULL)

15){/* 如果查找到的節(jié)點(diǎn)K不為空*/

16)將K節(jié)點(diǎn)的路由環(huán)節(jié)點(diǎn)信息表RRNT中記載的路由信息發(fā)送給節(jié)點(diǎn)N；

17)節(jié)點(diǎn)N據(jù)此信息生成自己的RRNT；

18)將節(jié)點(diǎn)N的路由信息發(fā)送給節(jié)點(diǎn)K，節(jié)點(diǎn)K依據(jù)此信息更新其RRNT表；}

19)else{/*如果沒(méi)有找到這樣的節(jié)點(diǎn)，表示該節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)*/

20)將節(jié)點(diǎn)N自己的路由信息存入RRNT；}

21)/*算法結(jié)束*/ }

4 基于資源路由環(huán)的對(duì)等云區(qū)間搜索技術(shù)

在基于資源路由環(huán)的對(duì)等云資源發(fā)布算法中，我們可以在不改變?cè)袑?duì)等云結(jié)構(gòu)的基礎(chǔ)上，將存儲(chǔ)相同類(lèi)型資源的節(jié)點(diǎn)鏈接成一個(gè)資源路由環(huán)． 完成資源路由環(huán)設(shè)計(jì)后，下面的任務(wù)就是如何在基于資源路由環(huán)的對(duì)等云系統(tǒng)中進(jìn)行資源的區(qū)間搜索．

4.1 依據(jù)資源類(lèi)型進(jìn)行資源定位

在資源發(fā)布算法中，節(jié)點(diǎn)在插入到某資源路由環(huán)之前，需按資源類(lèi)型定位到該資源路由環(huán)． 因此，在給定一種資源類(lèi)型后，如何在系統(tǒng)中查找到這種資源是本區(qū)間搜索技術(shù)的主要算法之一． 為實(shí)現(xiàn)該算法，本文提出了如下思想：由于本文所提的同類(lèi)型資源定位算法采用基于密文搜索的機(jī)制，因此，若用戶(hù)已知資源類(lèi)型為明文M，則在其明文區(qū)間[MMIN，MMAX]中隨機(jī)選擇一個(gè)值V，運(yùn)用同態(tài)加密機(jī)制運(yùn)算出其資源標(biāo)記S，及其屬性值區(qū)間[MIN，MAX]． 第一步，用戶(hù)在資源屬性值區(qū)間中運(yùn)用隨機(jī)函數(shù)計(jì)算得到一個(gè)密文屬性值FHV，然后，依據(jù)SHA-1算法計(jì)算出該屬性值的對(duì)象標(biāo)識(shí)objId． 第二步，運(yùn)用對(duì)等云系統(tǒng)的路由算法PR路由到節(jié)點(diǎn)K，查看K節(jié)點(diǎn)是否存在資源標(biāo)記為S的資源，如果存在，則查找結(jié)束并返回成功． 第三步，如果沒(méi)有找到，則重新在屬性區(qū)間中隨機(jī)產(chǎn)生一個(gè)新的密文屬性值FHV′，重新搜索． 第四步，直到搜索到此種類(lèi)型的資源，返回成功算法結(jié)束；或者搜索次數(shù)超限返回失敗算法結(jié)束． 依據(jù)資源類(lèi)型進(jìn)行資源定位的算法(RLART，Resource Location Algorithm based on Resource Type)如下所示．

Function RLART(TYPE S，F(xiàn)HVALUE MIN ，F(xiàn)HVALUE MAX)

1){/*該算法在給定資源類(lèi)型標(biāo)記的情況下進(jìn)行資源定位，算法返回值為資源存儲(chǔ)所在節(jié)點(diǎn)的標(biāo)識(shí)*/

2)count=0；/*count變量用來(lái)記載搜索次數(shù)，最大值為MaxCount */

3)flag=0；/* flag變量為是否搜索成功標(biāo)記，查找成功時(shí)，該值為1*/

4)while(count<=MaxCount)

5){/*在S類(lèi)資源的屬性值區(qū)間內(nèi)隨機(jī)產(chǎn)生一個(gè)屬性值FHV */

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

7)objId=SHA-1(FHV)；/* 運(yùn)用SHA-1算法計(jì)算出對(duì)象標(biāo)識(shí)objId */

8)/*調(diào)用Pastry的路由算法PR，將資源發(fā)布到路由到的節(jié)點(diǎn)K*/

9)K=PR(objId)；

10)forEach(id in 節(jié)點(diǎn)K的SNT)

11){/* 遍歷K節(jié)點(diǎn)的資源信息表*/

12)if(id==objId)/* 如果查找的資源對(duì)象標(biāo)識(shí)找到 */

13){flag=1；

14)break；/*在查找成功時(shí)，中止循環(huán)*/}}

15)if(flag==1)break；

16)count++；/*計(jì)數(shù)器自加*/}

17)if(flag==0){/*沒(méi)有查找到對(duì)應(yīng)資源的節(jié)點(diǎn)時(shí)，返回空值*/

18)return NULL；}

19)else{/* 若找到對(duì)應(yīng)資源的節(jié)點(diǎn)時(shí)，返回節(jié)點(diǎn)的標(biāo)識(shí) */

20)return K.nodeId；}

21)/*算法結(jié)束*/ }

該算法在不改變對(duì)等云覆蓋網(wǎng)絡(luò)結(jié)構(gòu)的基礎(chǔ)上構(gòu)建，具有較強(qiáng)的自適應(yīng)性，既支持密文資源定位，也支持明文資源定位；用戶(hù)在擁有明文的情況下進(jìn)行定位時(shí)，為確保操作過(guò)程的機(jī)密性，只需在調(diào)用該算法前進(jìn)行一次同態(tài)密碼運(yùn)算即可完成．

4.2 基于資源路由環(huán)的區(qū)間定位

在以資源路由環(huán)的方式發(fā)布資源后，在對(duì)等云系統(tǒng)中，擁有相同資源的節(jié)點(diǎn)通過(guò)存儲(chǔ)相同資源標(biāo)記的路由信息后，形成資源路由環(huán)；本小節(jié)將描述在資源路由環(huán)中如何進(jìn)行區(qū)間搜索． 首先，當(dāng)用戶(hù)搜索關(guān)鍵字區(qū)間為[V1，V2] 時(shí)，若關(guān)鍵字為明文，則運(yùn)用同態(tài)加密機(jī)制計(jì)算出密文區(qū)間[FHV1，F(xiàn)HV2]，并計(jì)算出資源標(biāo)記S． 第二步，依據(jù)資源標(biāo)記值S，通過(guò)資源定位算法RLART搜索到存儲(chǔ)該類(lèi)型資源的節(jié)點(diǎn)N． 第三步，以節(jié)點(diǎn)N為起始節(jié)點(diǎn)，在資源路由環(huán)中比對(duì)搜索區(qū)間關(guān)鍵字；若在此區(qū)間，則將存儲(chǔ)資源節(jié)點(diǎn)的節(jié)點(diǎn)標(biāo)識(shí)返回給用戶(hù)，直至遍歷資源路由環(huán)結(jié)束． 基于資源路由環(huán)的區(qū)間定位算法(ILARRR，Interval Location Algorithm based on Resource Routing Ring)如下所示．

Function ILARRR(FHVALUE FHV1，F(xiàn)HVALUE FHV2)

1){/*該算法實(shí)現(xiàn)在對(duì)等云系統(tǒng)中進(jìn)行區(qū)間搜索，區(qū)間為[FHV1，F(xiàn)HV2]，F(xiàn)HVALUE為同態(tài)密文屬性類(lèi)型*/

2)/*調(diào)用密文計(jì)算函數(shù)getSouTy計(jì)算出資源標(biāo)記S，并計(jì)算出該類(lèi)型數(shù)據(jù)區(qū)間最值MIN與MAX */

3)S=getSouTy(FHV1)；

4)/* 調(diào)用依據(jù)資源標(biāo)記定位資源算法RLART查找第一個(gè)存儲(chǔ)S類(lèi)資源的節(jié)點(diǎn)N */

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

6)if(N!=NULL){/*如N節(jié)點(diǎn)不為空，以N為第一個(gè)節(jié)點(diǎn)遍歷資源路由環(huán)*/

7)I=N；/*用臨時(shí)變量I存儲(chǔ)擁有S類(lèi)資源的節(jié)點(diǎn)的路由信息*/

8)定義集合SourNode[]存儲(chǔ)資源節(jié)點(diǎn)的路由信息；

9)j=0；

10)do{

11)forEach(id in節(jié)點(diǎn)I的SNT)

12){/*遍歷I節(jié)點(diǎn)的資源信息表*/

13)if(id>=FHV1&&id<=FHV2)/* 如果查找的資源屬性值在搜索區(qū)間之內(nèi) */

14){SourNode[j].nodeId =I.nodeId；/*將I節(jié)點(diǎn)的路由信息存入資源節(jié)點(diǎn)集合SourNode*/

15)j++；

16)break；}}

17)I=I.RRNT.nodeId；/* 取出I節(jié)點(diǎn)的路由環(huán)節(jié)點(diǎn)信息表中的路由節(jié)點(diǎn)作為下一查找的節(jié)點(diǎn) */

18)}while(I.nodeId !=N.nodeId)；/* 循環(huán)到路由起點(diǎn)結(jié)束*/

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

20)if(j>0){

21)/*搜索成功，返回資源節(jié)點(diǎn)集合*/

22)return SourNode；

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

24)return NULL；}

25)/*算法結(jié)束*/}

上述算法的輸入為密文屬性區(qū)間，若用戶(hù)在已知明文區(qū)間的情況下進(jìn)行區(qū)間搜索，則需運(yùn)用同態(tài)加密機(jī)制計(jì)算出密文區(qū)間，然后調(diào)用此算法來(lái)完成基于資源路由環(huán)的區(qū)間定位．

4.3 區(qū)間搜索效率分析

本文提出的區(qū)間搜索算法通過(guò)改進(jìn)Pastry對(duì)等系統(tǒng)，運(yùn)用資源路由環(huán)實(shí)現(xiàn)了密文資源區(qū)間的搜索，本搜索算法的路由開(kāi)銷(xiāo)包括在Pastry網(wǎng)絡(luò)中的路由開(kāi)銷(xiāo)以及在路由環(huán)中的路由開(kāi)銷(xiāo)，現(xiàn)就其搜索效率分析如下：

2)找到資源路由環(huán)入口后，ILARRR算法運(yùn)用遍歷環(huán)中資源節(jié)點(diǎn)的方法搜索資源，因此，其路由開(kāi)銷(xiāo)與環(huán)的大小成正比；在資源規(guī)模較小的情況下，環(huán)內(nèi)路由開(kāi)銷(xiāo)遠(yuǎn)遠(yuǎn)小于該算法調(diào)用RLART算法搜索環(huán)入口的路由開(kāi)銷(xiāo)． 但若資源規(guī)模增大，環(huán)內(nèi)搜索勢(shì)必成為主要的搜索開(kāi)銷(xiāo)之一，因此，為提高搜索效率，本文提出如下改進(jìn)措施：

① 在資源發(fā)布時(shí)，以資源屬性值為關(guān)鍵字來(lái)構(gòu)建有序鏈表的資源路由環(huán)；

② 在資源定位時(shí)，運(yùn)用資源路由環(huán)的有序性，優(yōu)化查找算法，以達(dá)到在資源路由環(huán)內(nèi)的搜索效率最優(yōu)．

5 仿真與性能分析

為了驗(yàn)證運(yùn)用結(jié)構(gòu)化對(duì)等系統(tǒng)Pastry作為對(duì)等云覆蓋網(wǎng)絡(luò)的有效性，我們選擇FreePastry為原型仿真器[15]來(lái)進(jìn)行仿真測(cè)試，網(wǎng)絡(luò)規(guī)模確定其最大值為10 000個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)；節(jié)點(diǎn)標(biāo)識(shí)的構(gòu)成采用16進(jìn)制，N的大小為|N|=32，L的大小為|L|=16． 為了實(shí)現(xiàn)密文下的區(qū)間搜索，運(yùn)用資源發(fā)布算法發(fā)布資源，設(shè)定算法RLART的最大搜索次數(shù)為10次，資源類(lèi)型數(shù)量為200種；搜索區(qū)間的確定方法為從不同類(lèi)型資源的屬性區(qū)間中隨機(jī)抽?。?實(shí)驗(yàn)主要測(cè)試了網(wǎng)絡(luò)規(guī)模與路由開(kāi)銷(xiāo)之間的關(guān)系，以及路由開(kāi)銷(xiāo)與搜索區(qū)間長(zhǎng)度之間的關(guān)系．

在測(cè)試網(wǎng)絡(luò)規(guī)模與路由開(kāi)銷(xiāo)之間的關(guān)系時(shí)，從200種資源中隨機(jī)抽取資源，并確定搜索區(qū)間的長(zhǎng)度為20個(gè)節(jié)點(diǎn)，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)量從1 000個(gè)增加至最大值10 000個(gè)，增值長(zhǎng)度為500；最終在不同網(wǎng)絡(luò)規(guī)模下進(jìn)行了100次實(shí)驗(yàn)，取其均值，獲得的平均路由開(kāi)銷(xiāo)與網(wǎng)絡(luò)規(guī)模的關(guān)系如圖3所示．

圖3為網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)與平均路由跳數(shù)之間的關(guān)系，其中橫坐標(biāo)為網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)(個(gè))，縱坐標(biāo)為平均路由開(kāi)銷(xiāo)，單位為步跳數(shù)(hops)． 從圖3可以看出，網(wǎng)絡(luò)規(guī)模從1 000增至10 000個(gè)節(jié)點(diǎn)的過(guò)程中，區(qū)間搜索的平均路由開(kāi)銷(xiāo)的增長(zhǎng)接近線性增長(zhǎng)趨勢(shì)． 得到上述實(shí)驗(yàn)結(jié)果的原因是：本文所提的對(duì)等云系統(tǒng)采用資源路由環(huán)進(jìn)行構(gòu)造，即將存儲(chǔ)同種類(lèi)型資源的節(jié)點(diǎn)運(yùn)用鏈接的方式形成一個(gè)資源環(huán)，在路由查找過(guò)程中，主要開(kāi)銷(xiāo)為基本覆蓋網(wǎng)絡(luò)的路由開(kāi)銷(xiāo)，因此，平均路由開(kāi)銷(xiāo)與網(wǎng)絡(luò)規(guī)模成正比關(guān)系．

圖3 平均路由開(kāi)銷(xiāo)與網(wǎng)絡(luò)規(guī)模關(guān)系圖

區(qū)間搜索相比于精確搜索，其搜索的數(shù)據(jù)量大；常規(guī)情況下，搜索區(qū)間包含的節(jié)點(diǎn)個(gè)數(shù)越多，則路由開(kāi)銷(xiāo)也會(huì)越大． 因此，搜索區(qū)間長(zhǎng)度與路由開(kāi)銷(xiāo)間的關(guān)系是區(qū)間搜索的重要評(píng)估指標(biāo)． 在測(cè)試時(shí)，我們確定網(wǎng)絡(luò)規(guī)模為2 000個(gè)節(jié)點(diǎn)，搜索區(qū)間長(zhǎng)度從10個(gè)節(jié)點(diǎn)增至100個(gè)節(jié)點(diǎn)，增值長(zhǎng)度為10；從200種資源中隨機(jī)抽取資源，在不同的搜索區(qū)間長(zhǎng)度下完成了100次實(shí)驗(yàn)，取其平均路由開(kāi)銷(xiāo)． 平均路由開(kāi)銷(xiāo)與搜索區(qū)間長(zhǎng)度之間的關(guān)系如圖4所示．

圖4 平均路由開(kāi)銷(xiāo)與搜索區(qū)間長(zhǎng)度關(guān)系圖

圖4為搜索區(qū)間長(zhǎng)度與平均路由跳數(shù)之間的關(guān)系，橫坐標(biāo)為搜索區(qū)間長(zhǎng)度，單位為搜索區(qū)間內(nèi)資源數(shù)量(個(gè))，縱坐標(biāo)為平均路由跳數(shù)，單位為hops． 從圖中可以看出，隨著搜索區(qū)間的增大，其平均路由跳數(shù)的增長(zhǎng)趨于平緩． 出現(xiàn)上述實(shí)驗(yàn)結(jié)果的原因是：本系統(tǒng)運(yùn)用資源路由環(huán)構(gòu)造，在路由過(guò)程中，主要開(kāi)銷(xiāo)在于查找第一個(gè)資源，并且資源路由環(huán)中的路由開(kāi)銷(xiāo)不大．

6 結(jié)束語(yǔ)

本文運(yùn)用結(jié)構(gòu)化的對(duì)等系統(tǒng)來(lái)構(gòu)建云系統(tǒng)的覆蓋網(wǎng)絡(luò)，采用將存儲(chǔ)相同類(lèi)型資源的節(jié)點(diǎn)鏈接成資源路由環(huán)，從而解決結(jié)構(gòu)化的對(duì)等云系統(tǒng)不適合區(qū)間搜索的問(wèn)題． 另外，為確保數(shù)據(jù)的機(jī)密性，運(yùn)用同態(tài)加密機(jī)制來(lái)實(shí)現(xiàn)密文下的資源搜索． 同態(tài)加密時(shí)間復(fù)雜性較大，本系統(tǒng)僅對(duì)資源屬性值進(jìn)行了同態(tài)加密． 下一步的工作將優(yōu)化同態(tài)加密算法，以使其在對(duì)等云系統(tǒng)中進(jìn)行密文運(yùn)算時(shí)不受條件限制．