基于資源路由環的對等云區間搜索技術①

賀道德，胡如會

貴州工程應用技術學院 信息工程學院，貴州 畢節 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 結束語

本文運用結構化的對等系統來構建云系統的覆蓋網絡，采用將存儲相同類型資源的節點鏈接成資源路由環，從而解決結構化的對等云系統不適合區間搜索的問題． 另外，為確保數據的機密性，運用同態加密機制來實現密文下的資源搜索． 同態加密時間復雜性較大，本系統僅對資源屬性值進行了同態加密． 下一步的工作將優化同態加密算法，以使其在對等云系統中進行密文運算時不受條件限制．