劉淑英

云計算中基于隨機游走的數(shù)據(jù)查詢方法研究

劉淑英

針對數(shù)字圖書館應(yīng)用服務(wù)中的數(shù)據(jù)查詢問題，提出了一種基于云計算的數(shù)據(jù)查詢方法。首先，基于Random Walk方法找到查詢請求的目標節(jié)點，然后，通過定義服務(wù)節(jié)點的相似節(jié)點集和等價節(jié)點集來進行二次搜索，返回具有最大評價值和最低負載的節(jié)點和數(shù)據(jù)作為所需的目標節(jié)點及數(shù)據(jù)。實驗結(jié)果表明，在查詢的數(shù)據(jù)質(zhì)量、服務(wù)節(jié)點的負載能力以及查詢的效率方法都優(yōu)于傳統(tǒng)的方法。

云計算；數(shù)字圖書館；Random Walk；數(shù)據(jù)查詢；相似節(jié)點集；等價節(jié)點集

0 引言

云計算（Cloud Computing）[1]是近年來新興的信息技術(shù)之一，它將能更好地使用計算資源，更智能地進行大規(guī)模的數(shù)據(jù)處理?；诟咝У奶摂M計算資源，應(yīng)用程序能以一種靈活且安全的方式實現(xiàn)快速擴展和縮減．從而交付高品質(zhì)服務(wù)。在面向用戶的數(shù)字圖書應(yīng)用中，如何利用現(xiàn)有的圖書館資源，為讀者或用戶提供更快捷、更便利的圖書數(shù)據(jù)查詢服務(wù)是目前數(shù)字化圖書館建設(shè)中必須要考慮的問題，而云計算技術(shù)由于其高可靠性、通用性、高可擴展性、按需服務(wù)以及及其廉價的特點，使它成為解決數(shù)字圖書館中高效數(shù)據(jù)查詢服務(wù)的一種有效手段，它能夠極大的降低數(shù)字圖書館建設(shè)成本，實現(xiàn)圖書館資源的有效共享。因此，本文基于云計算技術(shù)，主要研究數(shù)字圖書館中的數(shù)據(jù)查詢策略，從而為讀者提供更為高效、可靠的服務(wù)。

1 相關(guān)工作

云計算及其應(yīng)用研究是目前的熱點問題，相繼有眾多的學者提出了一系列的面向數(shù)據(jù)應(yīng)用的方法，如鄭湃等[2]針對數(shù)據(jù)密集型應(yīng)用中面臨的時間開銷較高、數(shù)據(jù)依賴性強以及無法有效實現(xiàn)全局的負載均衡等問題，文中在充分考慮了數(shù)據(jù)本身特性和網(wǎng)絡(luò)因素的基礎(chǔ)上，提出了一種有效的數(shù)據(jù)布局策略。實驗結(jié)果表明該策略要優(yōu)于已有的方法，能顯著地降低數(shù)據(jù)傳輸?shù)臅r間開銷，然而文中基于遺傳算法進行數(shù)據(jù)布局的實現(xiàn)過程比較復雜，且不能很好的解決大規(guī)模計算量問題；田冠華等[3]研究了動態(tài)資源的可靠性問題，提出了一種基于失效規(guī)律的策略來保證動態(tài)提供的節(jié)點資源的可靠性。實驗結(jié)果表明該策略可以屏蔽掉大量節(jié)點資源的失效,與不考慮資源失效規(guī)律的策略相比，文中策略能夠提供更高的可靠性。葛君偉等[4]針對云計算環(huán)境中現(xiàn)有的資源監(jiān)測方法的不足，提出一種改進的資源監(jiān)測模型，它通過虛擬機監(jiān)測器和Java調(diào)用C/C++得到資源的狀態(tài)信息。實驗結(jié)果表明該模型能夠有效獲取資源監(jiān)測信息；Rankova等人[5]提出了一種匿名數(shù)據(jù)搜索引擎，可以使得交互雙方搜索對方的數(shù)據(jù)，獲取自己所需要的部分，同時保證搜索詢問的內(nèi)容不被對方所知，搜索時與請求不相關(guān)的內(nèi)容不會被獲取。另外還有文獻[6-11]探討了云計算技術(shù)在數(shù)字圖書館建設(shè)方面的優(yōu)勢和挑戰(zhàn)，并提出了應(yīng)對挑戰(zhàn)的一系列措施和方法，為進一步推動云計算技術(shù)的應(yīng)用指明了方向。借鑒前人的工作，本文基于云計算技術(shù)，研究了數(shù)字圖書館中的數(shù)據(jù)查詢服務(wù)，提出了一種改進的數(shù)據(jù)查詢方法。模擬實驗結(jié)果表明，本文提出的數(shù)據(jù)查詢方法在數(shù)據(jù)查詢質(zhì)量和效率方面都能獲得預期效果，滿足用戶對于數(shù)字圖書館搜索服務(wù)的目標。

2 問題描述與建模

2.1 相關(guān)定義

以數(shù)字圖書館中的圖書搜索服務(wù)作為研究對象，假定云計算環(huán)境中提供數(shù)據(jù)的服務(wù)節(jié)點數(shù)為n，所有節(jié)點基于Internet構(gòu)成一個無中心、非結(jié)構(gòu)化的覆蓋網(wǎng)絡(luò)：令節(jié)點si上的數(shù)據(jù)對象集合用表示，數(shù)據(jù)對象的數(shù)目為對于S中的任意節(jié)點s，用Neighbor( s)表示節(jié)點s的鄰節(jié)點，其獲取、更新方法與P2P網(wǎng)絡(luò)中節(jié)點的探測、感知相同。為了描述方便，下面給出幾個相關(guān)定義：

定義1 云計算環(huán)境（CC）可以表示為多個分布式數(shù)據(jù)中心組成的集合其中dci表示第i個數(shù)據(jù)中心，CC中各數(shù)據(jù)中心間網(wǎng)絡(luò)帶寬可以表示為[2]公式（1）：

定義2 以圖書數(shù)據(jù)為例，不失一般性，假定其中的數(shù)據(jù)是同構(gòu)的。設(shè)每個數(shù)據(jù)對象包含m個屬性，則可定義描述數(shù)據(jù)對象的元數(shù)據(jù)為：

其中Ei是包含iχ個屬性成員的集合：。因此，每個數(shù)據(jù)對象可用一個m元組表示為公式（2）：

定義3 相似節(jié)點（SN, Similarity Nodes）。對于任意的兩個不相同的數(shù)據(jù)對象x和y，當且僅當它們滿足以下兩條規(guī)則時，則認為它們互為相似節(jié)點。

規(guī)則1：x和y在它們的屬性Ei上有相同的屬性值ni；

規(guī)則2：x和y的屬性間的相似度大于某一規(guī)定閾值；

對于滿足以上規(guī)則的x和y，設(shè)x和y所在的服務(wù)節(jié)點為p和q，則兩節(jié)點間的相似關(guān)系可以表示為公式（3）：

定義4 相似節(jié)點集（SNS, Similarity Nodes Set）。對于任意一個服務(wù)節(jié)點x的相似節(jié)點集是這樣的一個節(jié)點集合：集合中的每個成員節(jié)點都與節(jié)點x是相似關(guān)系為公式（4）：

在面向數(shù)字圖書館數(shù)據(jù)查詢服務(wù)的云計算環(huán)境中，處于同一個SNS中的資源服務(wù)節(jié)點有更大的概率被同一搜索請求訪問，以便返回更高質(zhì)量的目標數(shù)據(jù)。為此，需要為每個節(jié)點的SNS附加上質(zhì)量評價信息，我們用Q(x,t)表示在一段時間t內(nèi)數(shù)據(jù)對象x的查詢者對該數(shù)據(jù)質(zhì)量的評價（如某一次查詢服務(wù)中用戶對該服務(wù)質(zhì)量的評價）如公式（5）：

定義5 等價節(jié)點（ENy,Equivalent Nodes）對于任意的兩個相同的數(shù)據(jù)對象x和，如果分別位于不同的服務(wù)節(jié)點p和q上，則稱p和q互為x和y的等價節(jié)點。可以表示為公式（6）：

定義6 等價節(jié)點集（ENS, Equivalent Nodes Set） 對于任意一個服務(wù)節(jié)點x的等價節(jié)點集是這樣的一個節(jié)點集合：集合中的每個成員節(jié)點都與節(jié)點x是等價關(guān)系為公式（7）：

在面向數(shù)字圖書館數(shù)據(jù)查詢服務(wù)的云計算環(huán)境中，某個數(shù)據(jù)對象的等價節(jié)點集（ENS）中的所有節(jié)點能夠為發(fā)起查詢請求的用戶提供相同的數(shù)據(jù)(比如圖書館藏信息)。為此，在每個節(jié)點的ENS附加上負載信息[12]，包括負載能力、實際負載等，用描述最近某段時間t內(nèi)對節(jié)點p上的數(shù)據(jù)對象x的請求次數(shù)，Capacity(p,t))表示節(jié)點p的負載能力，它可以表示為公式（8）：

聯(lián)立公式（8-10），包含了負載信息的等價節(jié)點集可以定義為公式（11）：

2.2 節(jié)點狀態(tài)的更新

在面向數(shù)字圖書館應(yīng)用的云計算環(huán)境中，每個服務(wù)節(jié)點的狀態(tài)并非固定不變的，而是一個逐漸更新、優(yōu)化的過程。為了得到更好的查詢數(shù)據(jù)質(zhì)量，需要對節(jié)點的狀態(tài)進行更新，下面分別給出了相似節(jié)點集（SNS）和等價節(jié)點集（ENS）的更新算法。

算法1 SNS 更新算法

輸入：當前節(jié)點p，更新周期t

輸出：p的SNS

Step1. 遍歷鄰節(jié)點集合，搜索到當前服務(wù)節(jié)點p的相似節(jié)點集合，記為SNS( p)；

Step3. 迭代執(zhí)行Step2，直到SNS( p)中的每一個節(jié)點都處理完畢。

算法1基于當前節(jié)點的鄰節(jié)點集合，因此并不需要在構(gòu)成云計算環(huán)境（CC）的服務(wù)節(jié)點之間進行額外的消息傳播[13]，影響其時間復雜性的因素還有相似節(jié)點集的最大容量、圖書數(shù)據(jù)的屬性及其取值規(guī)模，在現(xiàn)實應(yīng)用中這些數(shù)據(jù)都有較小上界并相對穩(wěn)定。

算法2 ENS 更新算法

輸入：當前節(jié)點p，更新周期t

輸出：p的ENS

Step1. 對當前服務(wù)節(jié)點p上數(shù)據(jù)對象x的負載情況和負載能力進行評價，根據(jù)公式（11）可得CENS( p, x)；

算法2的更新過程由各服務(wù)節(jié)點的請求負載超載或欠載事件觸發(fā)，以便數(shù)據(jù)對象能夠及時地在節(jié)點之間重新分配，達到使未來負載趨于平衡的目標。

3 基于節(jié)點狀態(tài)的數(shù)據(jù)查詢

基于2.1節(jié)給出的相關(guān)定義和2.2節(jié)給出的節(jié)點狀態(tài)更新方法，本文提出了一種基于節(jié)點狀態(tài)的數(shù)據(jù)查詢策略。它的基本思想是：首先，對于一般意義的鄰節(jié)點使用隨機游走[14]方法，盡快定位到符合查詢的目標節(jié)點；然后，基于目標節(jié)點的相似節(jié)點集，繼續(xù)搜索到一個具有更好質(zhì)量評價的目標節(jié)點；最后，基于新的目標節(jié)點的等價節(jié)點集，返回其中具有最小請求負載的服務(wù)節(jié)點，作為整個搜索服務(wù)的結(jié)果。

算法3 基于節(jié)點狀態(tài)的數(shù)據(jù)查詢算法

輸入：查詢請求qreq，查詢開始節(jié)點p

輸出：目標節(jié)點和目標數(shù)據(jù)

Step1. 對于任意節(jié)點q發(fā)送的查詢請求q_qreq，如果節(jié)點p上存在能滿足q_qreq的數(shù)據(jù)x（記為，q_qreq=x），則p即為q的目標節(jié)點，轉(zhuǎn)Step3，否則轉(zhuǎn)Step2；

Step3. 遍歷節(jié)點q的相似節(jié)點集SNS( q, E, n)，得到滿足q_qreq的、具有最大Q( q, t)的節(jié)點β及其數(shù)據(jù)對象δ；

Step4. 遍歷節(jié)點β的等價節(jié)點集ENS(β, δ)，得到具有最小負載的節(jié)點及其數(shù)據(jù)對象，返回該目標節(jié)點和數(shù)據(jù)對象，算法結(jié)束。

從算法3中可以看到，它的效率主要取決于Step2的Random Walk方法。算法3的Step1和Step2的目標是獲得一個滿足查詢請求的數(shù)據(jù)副本，然后在Step3和Step4分別基于相似節(jié)點集和等價節(jié)點集在數(shù)據(jù)質(zhì)量、負載方面對查詢結(jié)果進行優(yōu)化，最終返回更好的服務(wù)節(jié)點和數(shù)據(jù)對象。而Step3和Step4時間復雜度為常數(shù)，這是因為在SNS 更新算法和ENS 更新算法中，對相似節(jié)點集和等價節(jié)點集中的節(jié)點分別按評價質(zhì)量和負載進行了有序組織或建立索引。

4 實驗結(jié)果與分析

在模擬實驗中，我們使用進程實例模擬數(shù)字圖書館云計算環(huán)境中的服務(wù)節(jié)點，這樣，可以在少數(shù)主機上執(zhí)行大量Java進程模擬圖書館查詢服務(wù)云環(huán)境；類似的，很多發(fā)出不同搜索請求的云用戶通過隨機創(chuàng)建的客戶線程模擬。實驗環(huán)境為Inter(R)Core(TM)2 Duo 2.93GHz，RAM 2GB，硬盤160GB，100MB網(wǎng)絡(luò)帶寬。基于此模擬實驗環(huán)境，我們主要從查詢服務(wù)返回結(jié)果的質(zhì)量、負載和搜索路徑等方面進行了相關(guān)實驗，并與P2P中的Random Walk方法進行了比較，在每個實驗中，不少于100個模擬云用戶的線程發(fā)出搜索請求并通過日志對返回結(jié)果進行記錄，每個搜索請求對目標數(shù)據(jù)在各屬性上的限制是隨機產(chǎn)生的。

查詢目標數(shù)據(jù)的質(zhì)量比較，如圖1所示：

圖1 不同查詢方法的目標數(shù)據(jù)質(zhì)量比較

從圖1可以看到，本文提出的查詢算法得到的目標數(shù)據(jù)的質(zhì)量要好于Random Walk方法。而且隨著服務(wù)節(jié)點數(shù)目的增加，本文方法對于提高查詢質(zhì)量的作用更為明顯。這主要是因為本文方法定義了節(jié)點的相似節(jié)點集（SNS）和等價節(jié)點集（ENS），每次查詢首先找到滿足查詢請求的目標節(jié)點，然后，分別從SNS和ENS出發(fā)找到具有最大Q值的數(shù)據(jù)，因此，得到的數(shù)據(jù)質(zhì)量較好。

如圖2所示：

圖2 不同方法的負載情況比較

圖2（a）和（b）給出了兩種方法查詢目標節(jié)點的負載情況。從圖2（a）可以看到，服務(wù)節(jié)點A，B，C，D，E，F(xiàn)的負載極不均衡，節(jié)點A承擔了78%的數(shù)據(jù)，而其他5個節(jié)點的負載則不足10%。而圖2（b）中6個節(jié)點的負載都在10%-20%之間，這表明本文提出的查詢算法在大量服務(wù)節(jié)點間的負載更為均衡。這主要是因為本文方法對于服務(wù)節(jié)點的負載情況進行了衡量，通過定義超載因子和欠載因子，從而能夠?qū)⒇撦d相對較高的節(jié)點的數(shù)據(jù)轉(zhuǎn)移到負載相對較低的節(jié)點上去，達到負載均衡的目的。

兩種不同方法的查詢路徑長短比較如圖3所示：

圖3 不同查詢方法的路徑長度比較

從圖3可以看到，兩種方法的結(jié)果較為接近，本文方法略有優(yōu)勢。這主要是因為，在實際的數(shù)字圖書館云計算環(huán)境中，具有相似性的數(shù)據(jù)更有可能聚集在一起，因此本文的方法總是能夠更快的查詢到目標。

5 總結(jié)

云計算作為一種新的技術(shù)，在現(xiàn)實領(lǐng)域中有著廣泛的應(yīng)用，本文以數(shù)字圖書館的查詢服務(wù)為研究對象，提出了一種基于云計算的數(shù)據(jù)查詢方法。在該方法中，首先，通過定義相似節(jié)點集和相等節(jié)點集來衡量節(jié)點的狀態(tài)，然后，通過Q值計算和負載大小比較，來為查詢請求找到最適合的目標節(jié)點及數(shù)據(jù)。仿真實驗結(jié)果表明，本文方法在查詢的數(shù)據(jù)質(zhì)量、服務(wù)節(jié)點的負載能力以及查詢的效率方法要優(yōu)于傳統(tǒng)的方法。我們下一步研究工作的重點在于：面向數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)分布方法研究，主要考慮如何減少跨數(shù)據(jù)中心的數(shù)據(jù)傳輸，如何在提供效率的同時兼顧全局的負載平衡。

[1] 陳康，鄭緯民. 元計算：系統(tǒng)實例與研究現(xiàn)狀[J]. 軟件學報, 2009,20（5）：1337-1348.

[2] 鄭湃，崔立真，王海洋，徐猛. 云計算環(huán)境下面向數(shù)據(jù)密集型應(yīng)用的數(shù)據(jù)布局策略與方法[J]. 計算機學報, 2010, 33(8):1472-1480.

[3] 田冠華，孟丹，詹劍鋒. 云計算環(huán)境下基于失效規(guī)則的資源動態(tài)提供策略[J]. 計算機學報，2010，2008,33(10):1859-1871.

[4] 葛君偉，張博，方義秋. 云計算環(huán)境下的資源監(jiān)測模型研究[J]. 計算機工程，2011,37（11）：31-33

[5] Raykova M, Vo B, Bellovin SM, Malkin T. Secure anonymous database search[C]. In: Sion R, ed. Proc. of the 2009 ACM Workshop on Cloud Computing Security, CCSW 2009, Co-Located with the 16th ACM Computer and Communications Security Conf., CCS2009. New York: Association for Computing Machinery, 2009. 115?126. [doi: 10.1145/1655008.1655025]

[6] 胡小菁，范并思. 云計算給圖書館管理帶來挑戰(zhàn)[J]. 大學圖書館學報, 2009, 27(4):7-12.

[7] 朱一紅. 云計算在圖書館的應(yīng)用與潛在風險[J]. 圖書館理論與實踐，2011，（3）：32-35

[8] 潘文宇，段勇. 云計算在電信行業(yè)的應(yīng)用研究[J]. 電信科學, 2010, 26(6):25-29

[9] 王長全, 艾棼. 云計算環(huán)境下的數(shù)字圖書館信息資源整合與服務(wù)模式創(chuàng)新[J]. 圖書館工作與研究, 2011 (001): 48-51

[10] 王長全, 艾霧, 姚建文. 云計算環(huán)境下數(shù)字圖書館信息資源安全策略研究[J]. 情報雜志, 2010, 3: 184-186

[11] 張凌超. 基于 “云計算” 的數(shù)字圖書館建設(shè)模式初探[J]. 圖書館學研究, 2010 (011): 39-42

[12] 姚婧, 何聚厚. 基于模糊聚類分析的云計算負載平衡策略[J]. 計算機應(yīng)用, 2012, 32(1): 213-217

[13] 房晶, 吳昊, 白松林. 云計算安全研究綜述[J]. 電信科學, 2011, 27(4): 37-42

[14] 鄭偉, 王朝坤, 劉璋, 等. 一種基于隨機游走模型的多標簽分類算法[J]. 計算機學報, 2010, 33(8): 1418-1426

Research on Data Query Method Based on Random Walk in Cloud Computing

Liu Shuying
(The Institute of Information Engineering of XianYang normal university, xianyang 712000, China)

Aiming at the data query problem in the digital library application service, this paper propose a data query method based on cloud computing. Firstly, the target node of the query request is found based on the Random Walk, and then the second search is proceeded through defining the similarity nodes set and the equivalent nodes set of the service node, finally, the node and data with maximum evaluation value and the minimum load is returned. The experimental results show that the performance of our method is superior to the traditional methods in terms of the quality of data, the load capacity of service node and the efficiency of query method.

Cloud Computing; Digital Library; Random Walk; Data Query; Similarity Nodes set; Equivalent Nodes Set

TP391

A

2014.04.25）

1007-757X(2014)09-0030-04

咸陽師范學院基金項目（13XSYK054）；陜西省教學改革項目（13BY90）

劉淑英（1982-），女，漢，陜西府谷人，咸陽師范學院信息工程學院，碩士，講師，研究方向：信息檢索、云計算，咸陽，712000