P2P情境下基于用戶興趣的個(gè)人數(shù)字圖書館資源定位

，

近年來，個(gè)人計(jì)算機(jī)上存儲(chǔ)的個(gè)性化信息資源數(shù)量大幅增長(zhǎng)，有效管理和使用這些資源成為亟待解決的問題，因此個(gè)人數(shù)字圖書館應(yīng)運(yùn)而生。目前個(gè)人數(shù)字圖書館有兩種形式：一種是基于服務(wù)器的個(gè)人信息空間，一般稱作“My library”(我的圖書館)[1]；另一種是基于PC的數(shù)字信息資源庫(kù)，一般稱作“Personal Digital Libraries”(PDLs)[2]。本文研究的是第二種形式。

作為個(gè)人信息工具，個(gè)人數(shù)字圖書館的職能主要有兩種：一種是有效管理和使用個(gè)人計(jì)算機(jī)上的信息資源，這是個(gè)人數(shù)字圖書館最基本的職能；另一種是共享個(gè)人計(jì)算機(jī)上的信息資源，促進(jìn)資源的有效利用和知識(shí)再生，這是個(gè)人數(shù)字圖書館的核心功能。信息搜索是資源共享的基礎(chǔ)，沒有合適的信息搜索機(jī)制就無法構(gòu)建高效的資源共享平臺(tái)。由于個(gè)人數(shù)字圖書館的分散性特點(diǎn)，其信息搜索及共享研究在傳統(tǒng)的客戶機(jī)/服務(wù)器模式下難以突破。為了解決這個(gè)問題，P2P(Peer to Peer)技術(shù)被引入了個(gè)人數(shù)字圖書館領(lǐng)域。

1 個(gè)人數(shù)字圖書館與P2P技術(shù)簡(jiǎn)介

大量學(xué)者對(duì)個(gè)人數(shù)字圖書館的資源共享進(jìn)行了研究。王小立指出資源共享是個(gè)人數(shù)字圖書館的本質(zhì)屬性，其發(fā)展仍處于初始階段，具有廣闊的前景[3]；陳春艷分析了阻礙個(gè)人數(shù)字圖書館資源共享的因素，指出傳統(tǒng)的集中式模式(客戶機(jī)/服務(wù)器和瀏覽器/服務(wù)器)阻礙了個(gè)人數(shù)字圖書館資源共享的發(fā)展[4]；張哲對(duì)比了集中式和P2P兩種模式，指出集中式模式共享成本高、效率低，不適合個(gè)人數(shù)字圖書館資源共享的發(fā)展，而P2P模式的去中心化與個(gè)人數(shù)字圖書館的分散性不謀而合，不需要服務(wù)器的參與，能充分發(fā)揮個(gè)人數(shù)字圖書館的能力，適合個(gè)人數(shù)字圖書館的發(fā)展[5]。

P2P即對(duì)等網(wǎng)絡(luò)，是相對(duì)傳統(tǒng)的客戶機(jī)/服務(wù)器模式而言的。系統(tǒng)中每個(gè)節(jié)點(diǎn)的作用都是對(duì)等的，既可以充當(dāng)服務(wù)器為其他節(jié)點(diǎn)提供資源和服務(wù)，也可以充當(dāng)客戶機(jī)享用其他節(jié)點(diǎn)的資源和服務(wù)。P2P技術(shù)因其良好的自組織能力和可擴(kuò)展性，而受到業(yè)界的廣泛關(guān)注，主要應(yīng)用于搜索引擎、資源共享、協(xié)同工作和實(shí)時(shí)通訊等領(lǐng)域。目前，P2P技術(shù)在個(gè)人數(shù)字圖書館方面的應(yīng)用研究較少，主要集中于文件共享模型的構(gòu)建和信息搜索。王春梅等介紹了個(gè)人數(shù)字圖書館的共享現(xiàn)狀，嘗試用P2P技術(shù)構(gòu)建簡(jiǎn)單的個(gè)人數(shù)字圖書館共享架構(gòu)，并通過模擬實(shí)驗(yàn)驗(yàn)證了P2P應(yīng)用于個(gè)人數(shù)字圖書館的可行性[6]；廈門大學(xué)Xu Yanfei利用具有相同興趣的個(gè)人數(shù)字圖書館形成社區(qū)，探討了適合個(gè)人數(shù)字圖書館的P2P網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[7]。資源定位是P2P技術(shù)應(yīng)用于個(gè)人數(shù)字圖書館需要突破的一個(gè)難題。張銀犬等指出在分布式環(huán)境下個(gè)人數(shù)字圖書館的信息檢索還是一個(gè)研究空白和難點(diǎn)，并結(jié)合P2P技術(shù)和Z39.50協(xié)議，對(duì)個(gè)人數(shù)字圖書館信息檢索策略進(jìn)行了初步探索[8]。

分布式環(huán)境下沒有集中式環(huán)境中掌管全局信息的中央服務(wù)器，資源定位成為一大難題。在非結(jié)構(gòu)化P2P網(wǎng)絡(luò)中，洪泛是最常使用的一種檢索策略。這種策略將查詢消息向所有鄰居進(jìn)行廣播，造成大量通訊開銷，嚴(yán)重影響了搜索效率[9]。為了減少消息數(shù)量，一些學(xué)者提出了啟發(fā)式搜索機(jī)制，利用搜索歷史、節(jié)點(diǎn)狀態(tài)等信息，將消息轉(zhuǎn)發(fā)范圍控制在局部存有目標(biāo)資源幾率較高的節(jié)點(diǎn)，可縮小搜索范圍，提高搜索效率?；谂d趣的搜索機(jī)制就是啟發(fā)式搜索中的一種[10]。文獻(xiàn)[11]根據(jù)節(jié)點(diǎn)之間的交流歷史創(chuàng)建興趣捷徑，從而改進(jìn)Gnutella的搜索性能。何可等采用基于興趣的完全二叉樹P2P拓?fù)浣Y(jié)構(gòu)，提出了一種基于Flooding機(jī)制的雙向資源搜索算法[12]；陳香香等根據(jù)節(jié)點(diǎn)共享文件的差異將網(wǎng)絡(luò)分域，并且利用預(yù)算值控制搜索范圍[13]。以上研究將最主要的興趣作為節(jié)點(diǎn)的唯一興趣，但是節(jié)點(diǎn)往往有多個(gè)興趣，當(dāng)節(jié)點(diǎn)搜索其他興趣的內(nèi)容時(shí)，就無法體現(xiàn)基于興趣搜索機(jī)制的優(yōu)勢(shì)。

在以上研究的基礎(chǔ)上，針對(duì)個(gè)人數(shù)字圖書館搜索機(jī)制尚不完善的問題，本文提出一種基于P2P技術(shù)采用多興趣的搜索機(jī)制的個(gè)人數(shù)字圖書館模型(Multi-Interest Personal Digital Library Model，MIPDLM)。

2 基于P2P技術(shù)的個(gè)人數(shù)字圖書館模型MIPDLM

2.1 興趣的表示

作為個(gè)性化特征突出的個(gè)人信息工具，個(gè)人數(shù)字圖書館(PDL)所存儲(chǔ)的資源(本文只研究文檔類的資源)往往表現(xiàn)出一定的興趣偏好。傳統(tǒng)的興趣表示通常只關(guān)注PDL最主要的興趣，這種單一的、靜態(tài)的興趣表示方法無法兼顧PDLs多樣的、動(dòng)態(tài)變化的興趣，導(dǎo)致PDL搜索效率低下。本文采用多興趣表示方法， PDL可以加入多個(gè)興趣簇，即使PDL擁有豐富的動(dòng)態(tài)變化的興趣，系統(tǒng)也能將搜索消息轉(zhuǎn)發(fā)到相似度較高的興趣簇，故可大大縮小搜索范圍，提高搜索效率。

本文采用經(jīng)典的向量空間模型(Vector Space Model，VSM)作為興趣表示模型，VSM模型將現(xiàn)實(shí)中無法相互比較的興趣轉(zhuǎn)化為可以計(jì)算彼此相似度的向量，如PDLi的興趣向量為{PDLi1,PDLi2,…,PDLik,…,PDLin}，表示PDLi共有n個(gè)興趣，其中PDLik是PDLi中第k(1≤k≤n)個(gè)興趣向量。兩個(gè)興趣之間的相似度采用夾角余弦表示，夾角余弦值越大，表示兩個(gè)興趣之間的相似度越大；反之，兩個(gè)興趣之間的相似度越小。同理，搜索消息向量與文檔向量之間的興趣相似度也取其夾角余弦值。興趣與PDL之間的相似度是指該興趣與PDL中所有興趣相似度的最大值。同理，搜索消息向量與PDL之間的興趣相似度也是如此計(jì)算。

2.2 興趣覆蓋網(wǎng)絡(luò)的構(gòu)建

構(gòu)建適合個(gè)人數(shù)字圖書館資源共享的興趣覆蓋網(wǎng)絡(luò)。在MIPDLM模型動(dòng)態(tài)構(gòu)建過程中，系統(tǒng)需用到個(gè)人數(shù)字圖書館的一些數(shù)據(jù)信息。每個(gè)PDLi存儲(chǔ)如下3方面的信息：一是PDLi共享文檔的集合，二是PDLi的興趣向量集合，三是兩種鄰居集合即簇內(nèi)鄰居集合和簇外鄰居集合。簇內(nèi)鄰居集合存儲(chǔ)與PDLi興趣相似度較高的PDLs，簇外鄰居集合存儲(chǔ)與PDLi興趣相似度較低的PDLs。簇內(nèi)鄰居和簇外鄰居都包含一組(ip(PDLj),PDLjr)信息，其中簇內(nèi)鄰居集合中ip(PDLj)是PDLi簇內(nèi)鄰居PDLj的IP地址，PDLjr是與PDLi的第k個(gè)興趣相對(duì)應(yīng)的興趣向量。相反，簇外鄰居集合中ip(PDLj)是PDLi的簇外鄰居PDLj的IP地址，PDLjr是與PDLi的第k個(gè)興趣相對(duì)應(yīng)的興趣向量。大量的PDLs根據(jù)簇內(nèi)鄰居形成一個(gè)個(gè)興趣簇，這些興趣簇緊密地結(jié)合在一起組成一個(gè)興趣覆蓋網(wǎng)，這種網(wǎng)絡(luò)類似于一個(gè)規(guī)則網(wǎng)絡(luò)。為了保證“小世界”特性，PDLs通過少量的簇外鄰居鏈接到其他的興趣簇[14]。

本文采用全分布式非結(jié)構(gòu)化的P2P網(wǎng)絡(luò)結(jié)構(gòu)。當(dāng)PDLi加入網(wǎng)絡(luò)時(shí)，首先初始化興趣向量{PDLi1,PDLi2,…,PDLik,…,PDLin}，針對(duì)每個(gè)興趣PDLik，PDLi維護(hù)兩個(gè)路由表CRPDLik和NCRPDLik，CRPDLik存儲(chǔ)簇內(nèi)鄰居信息，NCRPDLik存儲(chǔ)簇外鄰居信息。PDLi利用隨機(jī)漫步算法在網(wǎng)絡(luò)中發(fā)出一個(gè)消息，選取收到消息的2m個(gè)PDLs作為初始值，分別將m個(gè)PDLs的IP和興趣向量存入CRPDLik和NCRPDLik。PDLs的興趣一直處于動(dòng)態(tài)變化過程中，為了確保網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)適應(yīng)個(gè)人數(shù)字圖書館興趣的變化，使興趣相似度較高的PDLs始終聚集在一起，PDL定期檢測(cè)每個(gè)興趣PDLik的聚合度DPDLik。聚合度DPDLik的大小是PDLi與所有PDLik相應(yīng)的簇內(nèi)鄰居興趣相似度的平均值，如果DPDLik高于或等于某一臨界值γ，說明當(dāng)前PDLi與簇內(nèi)鄰居興趣相似度較高，PDLi不需要搜尋新的簇內(nèi)鄰居；如果DPDLik低于某一臨界值γ，說明當(dāng)前PDLi與簇內(nèi)鄰居關(guān)于PDLik的興趣相似度較低，系統(tǒng)會(huì)重新搜尋興趣相似度較高的PDLs并加入CRPDLik中。

2.3 基于多興趣的搜索機(jī)制

哈佛大學(xué)社會(huì)心理學(xué)教授Stanley Milgram在著名的連鎖信實(shí)驗(yàn)中發(fā)現(xiàn)了典型的小世界現(xiàn)象。受該實(shí)驗(yàn)的啟發(fā)，在搜索過程中，PDL將消息轉(zhuǎn)發(fā)到與搜索信息興趣相似度較高的PDL中，這些通過興趣連接在一起的PDLs不停地將消息轉(zhuǎn)發(fā)到它們認(rèn)為最有可能擁有目標(biāo)資源的PDLs中，可大幅度減少搜索范圍。

基于多興趣的算法流程見圖1。其搜索過程如下：步驟①PDLi發(fā)起一個(gè)搜索消息q時(shí)，首先將q的搜索內(nèi)容初始化為向量d，定義q的最大轉(zhuǎn)發(fā)跳數(shù)TTLq，初始化q所經(jīng)過的PDLs列表ADD和搜索到的文檔列表DOC。其中，ADD存放消息q所經(jīng)過的PDLs的IP，DOC存放搜索到的文檔向量以及相應(yīng)PDL的IP。計(jì)算PDLi中與d相似度最大的興趣PDLik，在路由表CRPDLik中計(jì)算與d興趣相似度最大的興趣PDLjr。步驟②將搜索消息q轉(zhuǎn)發(fā)到PDLj，把PDLj的IP添加到ADD中，計(jì)算d與PDLj中所有的共享文檔的興趣相似度。當(dāng)高于閾值θ時(shí)，把該文檔向量和IP添加到文檔列表DOC中，將ttlq減1。如果TTLq等于0，搜索消息q返回PDLi，否則轉(zhuǎn)到步驟③。步驟③計(jì)算CRPDLjr中與d相似度最大的興趣PDLlm。如果列表ADD中含有PDLl的IP，說明消息q已經(jīng)到達(dá)過PDLl。為了防止環(huán)路的產(chǎn)生，舍棄PDLl，按興趣相似度由大到小的順序繼續(xù)在CRPDLjr中尋找，直到找到IP不在ADD中的PDLlm(如果CRPDLjr和NCRPDLjr中所有PDLs的IP都在列表ADD中，則搜索結(jié)束，消息q返回PDLi)，其興趣相似度值為value。如果value小于閾值λ，表明CRPDLjr中的PDLs與d興趣相似度不高。在NCRPDLjr中搜尋與d相似度最大的興趣PDLsn(檢查相應(yīng)的IP是否在列表ADD中，如果在列表ADD中則利用上面的方法尋找下一個(gè)興趣)，從PDLlm與PDLsn中選取與d興趣相似度較大的那個(gè)興趣作為PDLjr。如果value大于或等于閾值λ，表明CRPDLjr中的PDLs與d興趣相似度較高，不必再去NCRPDLjr中尋找相似度更高的興趣而將PDLlm作為新的PDLjr，重復(fù)步驟②。當(dāng)消息返回到PDLi時(shí)，搜索到的文檔將按與d興趣相似度由大到小的順序顯示出來。

圖1 個(gè)人數(shù)字圖書館基于多興趣的資源定位算法流程

3 仿真實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

從中國(guó)知網(wǎng)期刊論文數(shù)據(jù)庫(kù)中選取實(shí)驗(yàn)文檔。根據(jù)中國(guó)知網(wǎng)期刊論文數(shù)據(jù)庫(kù)的學(xué)科分類，從基礎(chǔ)科學(xué)、經(jīng)濟(jì)與管理科學(xué)等10個(gè)學(xué)科分類中分別選取20個(gè)興趣主題，每個(gè)興趣主題下載50篇論文。實(shí)驗(yàn)工具采用P2P通用網(wǎng)絡(luò)模擬器PeerSim。

在PeerSim中生成一個(gè)網(wǎng)絡(luò)規(guī)模為1 000個(gè)PDLs的全分布式非結(jié)構(gòu)化P2P網(wǎng)絡(luò)，將選取的10 000份文檔散布在1 000個(gè)PDLs中，每個(gè)PDL的文檔所涉及的興趣數(shù)量不超過3個(gè)。

3.2 興趣聚合度的確定

系統(tǒng)開始運(yùn)行后，每個(gè)PDL都嘗試啟動(dòng)聚合度檢測(cè)程序，尋找興趣相似度較高的PDLs。為了使PDLs不在同一時(shí)刻啟動(dòng)檢測(cè)程序，所有PDLs在0-30分鐘內(nèi)隨機(jī)選擇某一時(shí)刻啟動(dòng)檢測(cè)程序。第一次啟動(dòng)檢測(cè)程序后，系統(tǒng)設(shè)定PDL定期啟動(dòng)一次檢測(cè)程序，運(yùn)行10個(gè)周期，計(jì)算搜索成功率。興趣相似度較高的PDLs聚集在一起是MIPDLM模型正常運(yùn)行的基礎(chǔ)。閾值γ決定最小聚合度，選取合適的γ值是MIPDLM模型提高搜索效率的前提。為了驗(yàn)證閾值γ如何取值合適，實(shí)驗(yàn)測(cè)試了不同γ值下的搜索成功率，實(shí)驗(yàn)重復(fù)10次，每次系統(tǒng)都重新初始化網(wǎng)絡(luò)，為每個(gè)PDL分配文檔，TTL=6，實(shí)驗(yàn)結(jié)果取平均值(圖2)

圖2 不同γ值下的搜索成功率

從圖2可以看出，當(dāng)γ=0.5和γ=0.6時(shí)，聚合度太低，興趣相似度較高的PDLs沒能聚集在一起，搜索成功率較低；當(dāng)γ=0.8和γ=0.9時(shí)，興趣相似度較高的PDLs雖然聚集在一起，但是聚合度太高，節(jié)點(diǎn)無法通過興趣相似度較低的PDLs搜索資源，搜索成功率仍然不高；當(dāng)γ=0.7時(shí)，聚合度較為合適，興趣相似度度較高的PDLs聚集在一起，搜索效果較為理想。以下實(shí)驗(yàn)中γ值均取0.7。

3.3 實(shí)驗(yàn)結(jié)果及分析

搜索機(jī)制的優(yōu)劣主要取決于搜索成功率和平均路徑長(zhǎng)度等因素。搜索成功率是指搜索成功次數(shù)在搜索總次數(shù)中所占的比重，搜索成功率越高搜索性能越好；平均路徑長(zhǎng)度是指搜索路徑長(zhǎng)度的平均值，平均路徑長(zhǎng)度越長(zhǎng)需要搜索的PDLs越多，在增加延遲的同時(shí)也加重了網(wǎng)絡(luò)負(fù)載，較低的平均路徑長(zhǎng)度是搜索機(jī)制追求的重要目標(biāo)。

隨機(jī)漫步(Random Walk)是P2P網(wǎng)絡(luò)中性能較為優(yōu)越的一種搜索機(jī)制[15]。為了驗(yàn)證MIPDLM模型的性能，需對(duì)MIPDLM模型中搜索成功率和平均路徑長(zhǎng)度與Random Walk機(jī)制進(jìn)行比較。MIPDLM網(wǎng)絡(luò)模型運(yùn)行一段時(shí)間，興趣簇達(dá)到一個(gè)相對(duì)穩(wěn)定的階段后，隨機(jī)選取PDL根據(jù)自己的興趣進(jìn)行搜索，TTL從1增加到10，每個(gè)TTL搜索200次，計(jì)算結(jié)果平均值。

搜索成功率如圖3所示。在TTL相同的情況下，MIPDLM模型的搜索成功率明顯高于Random Walk的。隨著TTL不斷增加，Random Walk的搜索成功率一直處于緩慢上升的趨勢(shì)，并且在TTL<4之前搜索成功率上升的幅度較小。當(dāng)TTL=10時(shí)，Random Walk的搜索成功率只有80%左右；當(dāng)TTL=4時(shí)，MIPDLM模型的搜索成功率已接近80%，說明MIPDLM模型中由于PDLs形成興趣簇，興趣一致的PDLs聚集在一起，搜索消息轉(zhuǎn)發(fā)到興趣相似度較高的PDL中，可大大縮小搜索范圍，絕大部分PDLs能在4跳內(nèi)搜索到所需資源。搜索平均路徑長(zhǎng)度如圖4所示。MIPDLM模型的搜索平均路徑長(zhǎng)度明顯低于Random Walk的。Random Walk的平均路徑長(zhǎng)度隨著TTL的增加不斷攀升。當(dāng)TTL=10時(shí)，Random Walk的平均路徑長(zhǎng)度已接近7。隨著TTL的增加，MIPDLM模型的平均路徑長(zhǎng)度維持在4左右，再一次驗(yàn)證了MIPDLM模型中絕大部分PDLs能在4跳內(nèi)搜索到所需資源。MIPDLM模型較低的平均路徑長(zhǎng)度可減少網(wǎng)絡(luò)延遲，減輕網(wǎng)絡(luò)負(fù)載。

圖3 搜索成功率

圖4 平均路徑長(zhǎng)度

4 結(jié)語

本文提出了一種基于多興趣的P2P資源定位機(jī)制，個(gè)人數(shù)字圖書館可根據(jù)興趣分簇探討基于多興趣的搜索機(jī)制。隨著興趣的動(dòng)態(tài)變化，個(gè)人數(shù)字圖書館不斷調(diào)整簇內(nèi)鄰居，系統(tǒng)始終將興趣相似度較高的個(gè)人數(shù)字圖書館聚集在一起形成P2P興趣覆蓋網(wǎng)絡(luò)。仿真實(shí)驗(yàn)顯示，MIPDLM模型中搜索消息不停地往興趣相似度較高的個(gè)人數(shù)字圖書館轉(zhuǎn)發(fā)，個(gè)人數(shù)字圖書館基本能在4跳內(nèi)搜索到所需資源，可大大縮小搜索范圍，提高搜索成功率，減少平均路徑長(zhǎng)度，減輕網(wǎng)絡(luò)負(fù)載，提升個(gè)人數(shù)字圖書館的資源定位效率。本文為圖書和檔案共享系統(tǒng)的構(gòu)建提供的新思路，有助于建立高效的分布式資源定位機(jī)制和共享模型。