云計算中基于隨機游走的數據查詢方法研究

劉淑英

云計算中基于隨機游走的數據查詢方法研究

劉淑英

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

云計算；數字圖書館；Random Walk；數據查詢；相似節點集；等價節點集

0 引言

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

1 相關工作

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

2 問題描述與建模

2.1 相關定義

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

定義1 云計算環境（CC）可以表示為多個分布式數據中心組成的集合其中dci表示第i個數據中心，CC中各數據中心間網絡帶寬可以表示為[2]公式（1）：

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

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

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

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

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

對于滿足以上規則的x和y，設x和y所在的服務節點為p和q，則兩節點間的相似關系可以表示為公式（3）：

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

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

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

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

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

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

2.2 節點狀態的更新

在面向數字圖書館應用的云計算環境中，每個服務節點的狀態并非固定不變的，而是一個逐漸更新、優化的過程。為了得到更好的查詢數據質量，需要對節點的狀態進行更新，下面分別給出了相似節點集（SNS）和等價節點集（ENS）的更新算法。

算法1 SNS 更新算法

輸入：當前節點p，更新周期t

輸出：p的SNS

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

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

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

算法2 ENS 更新算法

輸入：當前節點p，更新周期t

輸出：p的ENS

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

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

3 基于節點狀態的數據查詢

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

算法3 基于節點狀態的數據查詢算法

輸入：查詢請求qreq，查詢開始節點p

輸出：目標節點和目標數據

Step1. 對于任意節點q發送的查詢請求q_qreq，如果節點p上存在能滿足q_qreq的數據x（記為，q_qreq=x），則p即為q的目標節點，轉Step3，否則轉Step2；

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

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

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

4 實驗結果與分析

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

查詢目標數據的質量比較，如圖1所示：

圖1 不同查詢方法的目標數據質量比較

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

如圖2所示：

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

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

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

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

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

5 總結

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

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

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

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

[4] 葛君偉，張博，方義秋. 云計算環境下的資源監測模型研究[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] 胡小菁，范并思. 云計算給圖書館管理帶來挑戰[J]. 大學圖書館學報, 2009, 27(4):7-12.

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

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

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

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

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

[12] 姚婧, 何聚厚. 基于模糊聚類分析的云計算負載平衡策略[J]. 計算機應用, 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