大規(guī)模對等搜索及應(yīng)用研究.pdf

1、對等(P2P)計算模型的出現(xiàn)啟迪了很多高效的大規(guī)模分布式應(yīng)用的構(gòu)建。由于P2P模式具有低成本、自組織、魯棒性、可擴(kuò)展、隱私保護(hù)等優(yōu)點，已成為構(gòu)建大規(guī)模互聯(lián)網(wǎng)應(yīng)用的良好架構(gòu)。自從P2P技術(shù)誕生以來，P2P應(yīng)用越來越普及，無數(shù)用戶開始利用P2P技術(shù)在互聯(lián)網(wǎng)上共享資源。 區(qū)別于傳統(tǒng)的集中式信息系統(tǒng)，基于P2P架構(gòu)的信息共享系統(tǒng)，如P2PWEB、基于P2P的WlKI系統(tǒng)等，帶來了新的挑戰(zhàn)：由于P2P系統(tǒng)的完全分布式特點，高效的分布式資源

2、搜索成為首要的難點；同時，基于P2P模型自主公平的原則，用戶需要一種公平交換的方式進(jìn)行信息共享，而在P2P環(huán)境中缺少可信第三方的條件下公平交換是非常困難的。 針對上述問題，本文研究采用復(fù)制策略和緩存策略來提高大規(guī)模對等搜索的性能，并且提出了對等網(wǎng)絡(luò)環(huán)境下無需專用TTP的公平交換協(xié)議。主要貢獻(xiàn)包括： 1．提出一種基于復(fù)制策略的概率窮盡搜索P2P系統(tǒng)RPXS。首先分析了窮盡搜索概率模型，證明了隨機(jī)復(fù)制策略具有最優(yōu)的搜索成功率

3、，通過將優(yōu)化數(shù)量的副本隨機(jī)復(fù)制到無結(jié)構(gòu)P2P網(wǎng)絡(luò)中，能夠以高概率保證窮盡搜索；分析結(jié)果還表明復(fù)制策略的成本取決于網(wǎng)絡(luò)的規(guī)模?；诟F盡搜索概率模型設(shè)計了一種混合式P2P結(jié)構(gòu)——RPXS，成功解決了隨機(jī)復(fù)制問題。RPXS通過構(gòu)建一個輕量級的分布式哈希表(DHT)子系統(tǒng)提供網(wǎng)絡(luò)規(guī)模估計和隨機(jī)結(jié)點子集選取服務(wù)，基于此服務(wù)，RPXS復(fù)制數(shù)據(jù)項/查詢到網(wǎng)絡(luò)中的隨機(jī)結(jié)點子集，從而有效實現(xiàn)了概率窮盡搜索。分析表明RPXS具有合理的系統(tǒng)開銷，非常適合大規(guī)

4、模P2P網(wǎng)絡(luò)環(huán)境下的文本搜索應(yīng)用。全面的模擬實驗結(jié)果表明RPXS能夠以較低的消息開銷獲得接近優(yōu)化的搜索成功率和較好的容錯性。 2．為了進(jìn)一步降低資源搜索的成本，本文提出了基于副本網(wǎng)絡(luò)的多命中查詢策略。設(shè)計多種策略關(guān)聯(lián)副本，使得同一資源的不同副本之間相互感知，并通過數(shù)學(xué)分析和實驗確定相關(guān)參數(shù)，針對不同的資源分別構(gòu)建邏輯上的副本網(wǎng)絡(luò)。查詢請求命中副本網(wǎng)絡(luò)中任一副本，通過副本關(guān)聯(lián)信息可以容易地訪問其它副本，從而能夠有效獲得多命中查詢。

5、所提出的副本管理策略可與RPXS相結(jié)合，從而實現(xiàn)低開銷的窮盡搜索。 3．提出一種興趣感知的緩存策略用于提高資源搜索的性能。資源結(jié)點廣告資源信息，其它結(jié)點接收資源廣告信息，并根據(jù)該廣告信息對當(dāng)前結(jié)點的可用潛能確定是否緩存該信息。設(shè)計了基于GOSSIP的資源廣告算法，采用布隆過濾器來表示結(jié)點的興趣，并提出了可用潛能的量化方法。實驗結(jié)果表明所提出的緩存策略顯著提高了無結(jié)構(gòu)對等網(wǎng)絡(luò)的搜索性能。 4．提出一種基于采樣網(wǎng)絡(luò)上隨機(jī)游走

6、的結(jié)點采樣算法。分析了結(jié)點采樣的參數(shù)設(shè)置，基于此分析提出了采樣網(wǎng)絡(luò)構(gòu)建算法和基于隨機(jī)游走的采樣算法。模擬實驗結(jié)果表明，所提出的結(jié)點采樣算法具有低消息開銷、低時延和低偏差的優(yōu)勢。結(jié)點采樣算法能夠用于解決公平交換中分布式TTP構(gòu)建問題。 5．提出一種P2P環(huán)境下的無需專用可信第三方(TTP)的公平交換協(xié)議P2PFair。通過交易雙方共同選擇系統(tǒng)中的n個隨機(jī)結(jié)點合成一個分布式的可信第三方提供交換的公平性保證；采用基于身份的加密算法(I