基于GNP算法的分布式爬蟲調(diào)度策略

摘 要:針對分布式搜索引擎的任務調(diào)度及負載均衡問題，提出了基于GNP算法的分布式爬蟲調(diào)度策略和負載均衡的方法。利用網(wǎng)絡距離預估取代大規(guī)模的網(wǎng)絡距離測量，不僅提高了系統(tǒng)的響應速度，還減少了系統(tǒng)對廣域網(wǎng)造成的壓力。通過在廣域網(wǎng)上部署爬蟲節(jié)點，構建分布式搜索引擎，應用該調(diào)度策略進行實驗，驗證了系統(tǒng)性能有較大提高。

關鍵詞:分布式爬蟲; 任務調(diào)度; 負載均衡; 網(wǎng)絡測量; 全局網(wǎng)絡定位

中圖分類號:TP309

文獻標志碼:A

文章編號:1001-3695(2010)02-0446-04

doi:10.3969/j.issn.1001-3695.2010.02.011

GNP-based scheduling strategy for distributed crawling

LIU Shuang1， JIANG Chun-xiang2， ZHANG Wei-zhe1， LI Dong1， ZHANG Hong3

(1.School of Computer Science Technology， Harbin Institute of Technology， Harbin 150001， China; 2.Heilongjiang Branch of National Computer Network Emergency Response Technical Team/Coordination center of China， Harbin 150001， China; 3.National Computer Network Emergency Response Technical Team/Coordination Center of China， Beijing 100029， China)

Abstract:In order to solve task scheduling and load balancing problems of distributed search engines， this paper proposed a GNP-based scheduling strategy for distributed crawling and a load balancing method. Adopted internet distance estimating mechanism as a replacement for large-scale network distance measurement， which not only improved response time of the system， but also reduced WAN pressure caused by the system. Through deploying crawling nodes at WANs， built a distributed search engine， and implemented several scheduling strategies. The online experiment shows great improvement in system’s performance.

Key words:distributed crawling; scheduling strategies; load balancing; network measurement; GNP(global network positioning)

0 引言

目前搜索引擎遇到的瓶頸問題在很大程度上是由其集中式結(jié)構造成的，一般的商用搜索引擎只有一個或多個大的數(shù)據(jù)中心，在本地執(zhí)行全部的網(wǎng)頁下載和索引工作。即使是地理上分布的搜索引擎，各個分系統(tǒng)之間也不能實現(xiàn)信息共享。受網(wǎng)絡基礎條件等方面的限制，隨著網(wǎng)站數(shù)目與規(guī)模的迅速膨脹，集中式搜索系統(tǒng)逐步會被分布式搜索系統(tǒng)取代。分布式搜索引擎在廣域網(wǎng)上部署爬蟲節(jié)點，其優(yōu)勢主要表現(xiàn)在:a)分散系統(tǒng)的網(wǎng)絡負載，同時在多個地理位置上工作的爬蟲分別分擔系統(tǒng)的網(wǎng)絡總負載;b)減小對廣域網(wǎng)增加的負載，選擇最優(yōu)的爬蟲抓取網(wǎng)頁，將會大大減少由于網(wǎng)頁數(shù)據(jù)在廣域網(wǎng)上路由造成的對廣域網(wǎng)的負載;c)分布式地存儲大規(guī)模數(shù)據(jù)，尤其是索引數(shù)據(jù)[1，2]。

如何將被獲取站點調(diào)度至網(wǎng)絡距離較近爬蟲，同時保證系統(tǒng)負載均衡是分布式搜索引擎調(diào)度系統(tǒng)的重要研究內(nèi)容。GNP算法[3]通過將網(wǎng)絡主機間的網(wǎng)絡距離映射為歐幾里德空間的坐標距離，可以有效地預估主機間網(wǎng)絡距離，具有較高的準確性。因此，GNP技術是分布式搜索引擎任務調(diào)度與負載均衡的基礎。本文針對分布式搜索引擎調(diào)度系統(tǒng)提出了基于GNP算法的分布式爬蟲調(diào)度策略，可以有效地提高調(diào)度系統(tǒng)的響應速度，同時減少系統(tǒng)對廣域網(wǎng)的負載。

本文介紹了GNP算法和分布式搜索引擎常用的調(diào)度策略，詳細討論了基于GNP算法的分布式爬蟲調(diào)度策略的基本思想和具體實現(xiàn)，并給出驗證調(diào)度策略性能的實驗。

1 相關研究

1.1 GNP算法的基本思想

GNP是最早被提出來的基于絕對坐標的網(wǎng)絡距離預測算法[4]，它把Internet模型化為幾何空間(如三維的歐幾里德空間)，并把Internet上任何一個節(jié)點的位置都對應到這個幾何空間的一點上去。這樣，任何兩個節(jié)點的網(wǎng)絡距離都可以通過兩個節(jié)點間的被模型化的幾何距離來估算[5]。

為了使Internet中的節(jié)點在幾何模型中的坐標得以計算，GNP算法提出了一種兩階段式的結(jié)構。在第一個階段里，被稱為路標節(jié)點(landmark)的一組位置分散的主機，在一個維度被預先設定的幾何空間里首先計算它們自己的坐標;然后這些landmarks的坐標將作為參考結(jié)構，被傳送給任何一個想要加入的節(jié)點。在第二個階段里，任何一個擁有l(wèi)andmarks的坐標節(jié)點，都能夠計算自己相對于這些landmarks的坐標。

GNP的坐標計算主要使用爬山法，并用三角不等式原理保證網(wǎng)絡距離預測的準確性。文獻[3]描述了GNP算法的具體實現(xiàn)，實驗表明在三維空間以上，GNP的距離預測都有較高的準確率。

網(wǎng)絡中主機節(jié)點間的距離可以通過GNP坐標按照歐幾里德公式計算得到，計算值就可以作為實際網(wǎng)絡距離的估計值。一旦得到一臺主機在GNP坐標系中的坐標值，就可以立刻計算出該主機與坐標系中其他主機間的網(wǎng)絡距離，而不需要進行實際測量，從而減少了主機和網(wǎng)絡的負擔，提高了網(wǎng)絡距離測量的效率。

本文將使用GNP算法進行網(wǎng)絡距離預測，根據(jù)廣域網(wǎng)上爬蟲與網(wǎng)站之間的網(wǎng)絡距離預測值來估計爬蟲下載該網(wǎng)頁的速度，根據(jù)此結(jié)果進行分布式搜索引擎的任務調(diào)度。

1.2 分布式爬蟲調(diào)度的主要策略及問題

分布式爬蟲調(diào)度的策略主要有四種。

1)隨機哈希調(diào)度[6]

最早的分布式爬蟲系統(tǒng)大多是對URL或主機名哈希，在此基礎上進行調(diào)度。這種調(diào)度策略非常容易計算，系統(tǒng)開銷較小;同時，由于哈希函數(shù)具有隨機性，可以保證爬蟲間的負載均衡。另外，這種將字符串映射為隨機數(shù)的方法非常易于與采用DHT的P2P系統(tǒng)集成。但是隨機哈希法不對分布式爬蟲進行區(qū)分，不能有效地利用分布式爬蟲抓取不同網(wǎng)站效率不同的特點。

2)根據(jù)網(wǎng)站的域名后綴及文件類型調(diào)度

這種調(diào)度方法根據(jù)網(wǎng)站域名后綴的不同，將具有相同域名后綴的網(wǎng)站分配給同一個或一組爬蟲抓取。例如，根據(jù)網(wǎng)站的域名中諸如.net、.org、.com等表示組織性質(zhì)的后綴進行分類;還可以根據(jù)URL字符串中的文件類型如.html、.jpg、.mp3等進行分類。SE4SEE(South-East Europe search engine，東—南歐搜索引擎)還提出了根據(jù)表示語言類型或國家、區(qū)域的域名后綴如.cn、.jp、.fr等進行分類[7]。這種方法的優(yōu)點是網(wǎng)頁數(shù)據(jù)在抓取時就已經(jīng)進行了初步的分類，為以后的數(shù)據(jù)分析工作奠定了比較好的基礎，但還是存在諸多缺陷:a)并非每個URL或域名都是遵守傳統(tǒng)后綴命名規(guī)范的，如有的學校域名就是.com而不是大家普遍認同的.edu;b)由于各種類型的網(wǎng)站數(shù)量或文件數(shù)量分布不均，將造成系統(tǒng)中各個爬蟲的負載不均，如按照語言類型分類中，小語種網(wǎng)站的數(shù)量非常少，而擁有諸如.cn、.de這類域名后綴的網(wǎng)站數(shù)量則非常大。

3)根據(jù)地理位置調(diào)度[8]

即就近抓取。對每個網(wǎng)站，由地理上距離它最近的爬蟲抓取。例如，部署在法國的爬蟲只抓取法國境內(nèi)的網(wǎng)站，部署在中國黑龍江省的爬蟲只抓取黑龍江省內(nèi)的網(wǎng)站。這種方法具有一定的可行性，因為網(wǎng)絡數(shù)據(jù)的傳輸都要經(jīng)過物理線路，所以地理距離較近的兩點，數(shù)據(jù)傳輸時間也相對較短。但是由于運營商的商業(yè)利益等因素，同一爬蟲抓取地理上距離接近的不同網(wǎng)站可能要經(jīng)過非常不同的路由器，真正的網(wǎng)絡距離相差可能很大。

4)根據(jù)網(wǎng)絡位置調(diào)度[9]

直觀的想法就是利用網(wǎng)站的IP地址，因為IP地址本身就具有層級關系，很容易建立樹狀結(jié)構。但是由于IP地址分配時的隨機性，IP地址并不能代表網(wǎng)絡位置。另一個想法是利用網(wǎng)絡中的自治域(AS)，但是自治域的構建過程綜合了人力、物力、財力等諸多因素，在同一個自治域中的節(jié)點并不能保證其網(wǎng)絡距離相對較近。

目前用分布式爬蟲對網(wǎng)站進行測量來計算網(wǎng)絡坐標方面的工作很少，而將其結(jié)果應用在分布式爬蟲調(diào)度上的研究幾乎沒有。

2 基于GNP的分布式爬蟲調(diào)度策略

2.1 調(diào)度策略的基本思想

分布在廣域網(wǎng)上的爬蟲抓取不同網(wǎng)站的性能差異巨大，筆者認為網(wǎng)絡距離較近的爬蟲與網(wǎng)站之間的通信時間較短，爬蟲下載網(wǎng)頁的速度也相對較快。

分布式搜索引擎的調(diào)度器首先測量若干組選定爬蟲節(jié)點之間網(wǎng)絡時延，匯總后建立GNP坐標系統(tǒng);然后通過坐標值計算其余網(wǎng)站與爬蟲節(jié)點間的網(wǎng)絡時延;最后挑選時延值最小的K個爬蟲作為調(diào)度對象。分布式爬蟲調(diào)度系統(tǒng)的模塊圖如圖1所示，這里忽略了爬蟲模塊的內(nèi)部實現(xiàn)。

調(diào)度策略的基本思想是利用GNP算法，通過測量較少組Web節(jié)點(爬蟲和Web網(wǎng)站)之間的網(wǎng)絡距離，估算大量節(jié)點間的網(wǎng)絡距離，利用網(wǎng)絡距離來預測爬蟲下載網(wǎng)頁的速度進行調(diào)度，從而有效地減少了大規(guī)模網(wǎng)絡測量的時間開銷及其對廣域網(wǎng)造成的負載。具體做法如下:

a)以網(wǎng)絡時延為距離，選擇若干爬蟲節(jié)點作為路標節(jié)點，所有路標節(jié)點彼此雙向測量網(wǎng)絡時延;普通爬蟲節(jié)點測量到所有路標節(jié)點的網(wǎng)絡時延。

b)利用路標節(jié)點間的網(wǎng)絡時延構建GNP基本坐標系;通過普通爬蟲節(jié)點到路標節(jié)點的網(wǎng)絡時延完善GNP坐標系。

c)需要確定調(diào)度策略的網(wǎng)站加入GNP坐標系。路標節(jié)點測量到該網(wǎng)站的網(wǎng)絡時延，確定該網(wǎng)站在GNP坐標系中的坐標值。

d)利用歐幾里德公式計算網(wǎng)站到普通爬蟲節(jié)點的估計網(wǎng)絡時延。

e)統(tǒng)計少數(shù)測量時延(網(wǎng)站到路標爬蟲節(jié)點的網(wǎng)絡時延)和大量計算時延(網(wǎng)站到普通爬蟲節(jié)點的網(wǎng)絡時延)，從中挑選與該網(wǎng)站的網(wǎng)絡時延最短的若干個爬蟲作為它的調(diào)度結(jié)果。

f)根據(jù)調(diào)度結(jié)果抓取網(wǎng)站。

2.2 調(diào)度方案的具體實現(xiàn)

2.2.1 算法設置

1)關于路標節(jié)點的選擇 路標節(jié)點必須全部是完全可控制的節(jié)點，因為路標節(jié)點之間的距離需要雙向測量以準確地計算出基本的GNP坐標系。在本系統(tǒng)中從爬蟲節(jié)點中選出部分節(jié)點作為路標節(jié)點。由于Internet上的網(wǎng)站并不是可控節(jié)點，對其進行的測量只能是單向測量，不能選擇網(wǎng)站作為路標工點。

通常選擇具有區(qū)域代表性的一組爬蟲作為坐標節(jié)點。一個實際的選擇方案是根據(jù)爬蟲的地理位置確定它的區(qū)域性，認為地理上分布均勻的坐標節(jié)點彼此間的網(wǎng)絡距離也比較均勻，更能代表空間坐標系，由此構建的基礎坐標系更加可靠。但是爬蟲的部署會受到各種因素影響，所以所選的路標節(jié)點的分布未必會完全均勻。另一種理想方案是根據(jù)爬蟲的網(wǎng)絡距離進行劃分，選擇劃分集合的中心節(jié)點作為路標節(jié)點。根據(jù)實際的可操作性，本系統(tǒng)采用第一種選擇方案，選擇不同城市、不同運營商的若干爬蟲作為路標節(jié)點。

2)關于網(wǎng)絡時延值的準確性 為了得到比較準確的網(wǎng)絡時延值，簡單直接的方法是對一個網(wǎng)站或爬蟲進行多次時延測量，取多個網(wǎng)絡時延的平均值作為準確時延值。但是時延值不絕對穩(wěn)定，對同一個目標的多次測量中，存在數(shù)目不定的由丟包造成的過大時延值，這些值是時延的噪聲，不能簡單地取所有時延值的平均值。

本文的辦法是計算網(wǎng)絡時延的統(tǒng)計加權平均值。首先根據(jù)時延值的分布確定一個統(tǒng)一的模值;再將所有時延值按前述統(tǒng)一的標準取模;然后對概率最大的三個取模整數(shù)值對應的時延值計算平均值，即可得到比較準確的時延值。由這種方法計算出的平均值稱為統(tǒng)計加權平均值，它有效地排除了時延序列中的噪聲，保證了平均值計算的準確性。計算網(wǎng)絡時延的統(tǒng)計加權平均值的公式可以表示為

=∑ni=1m1i+∑pj=1m2j+∑qk=1m3kn+p+q

其中:m1i、m2j和m3k分別是最大的三個取模整數(shù)值對應的三組時延值，m1i有n個，m2j有p個，m3k有q個;是統(tǒng)計加權平均值。

2.2.2 應用層網(wǎng)絡時延的測量

本文考慮采用應用層的測量來代替?zhèn)鹘y(tǒng)網(wǎng)絡層的測量作為坐標點的距離量度:a)系統(tǒng)更關心的是網(wǎng)頁的下載速率，它更加直接，并且本身就包含了網(wǎng)絡延遲、丟包率等問題;b)測量下載速率是單端的，不需要采用雙端式測量工具，即不需要對方服務器安裝應答程序作配合。即使是最簡潔的ICMP的ping操作，也可能因為防火墻、代理服務器等問題受到阻斷(在本文的實驗中，大約有30%的網(wǎng)站無法ping通)。

考慮到正常運行的網(wǎng)站必定會打開80端口，所以可以測量網(wǎng)站對于HTTP請求的響應時間，將這個時延近似作為網(wǎng)絡時延，稱以這種原理工作的測量程序為httpping。

不同于網(wǎng)絡層的ping操作，httpping操作使用TCP/IP應用層協(xié)議HTTP請求—響應來工作，其本身就包含了網(wǎng)絡延遲、丟包率等。與單純的網(wǎng)絡層測量相比，它能夠更準確地反映分布式搜索引擎中爬蟲與網(wǎng)站之間的距離，因為搜索引擎關心的是爬蟲在應用層上的網(wǎng)頁下載速率。

將httpping測量的距離作為GNP的輸入，改變坐標系維度和路標節(jié)點數(shù)，得到20%和30%去噪率下的時延估計值的準確率如表1、2所示。觀察發(fā)現(xiàn)，當路標節(jié)點數(shù)固定，坐標系維度變化時，估計準確率隨著維度的增大(忽略維度為2時的情況，維度過小時，建立坐標系的準確度下降程度比較大)有略微的提升，但幅度不大;當維度固定，路標節(jié)點數(shù)變化時，估計準確率隨著路標數(shù)的增大而顯著提升。這些規(guī)律與ping在GNP算法下的結(jié)果一致，所以筆者認為將httpping的測量作為網(wǎng)絡時延的測量手段是可行的。

表1GNP坐標系路標數(shù)固定、維度變化下的估計準確率

維度(9個路標)去掉30%噪聲的準確率去掉20%噪聲的準確率

20.684 6790.493 873

30.737 5950.599 625

40.740 4720.602 797

50.741 8110.604 769

60.742 3440.605 146

70.743 1450.605 081

80.744 6490.607 787

表2 GNP坐標系維度固定、路標數(shù)變化下的估計準確率

維度和路標數(shù)去掉30%噪聲的準確率去掉20%噪聲的準確率

6維 9個路標0.742 3440.605 146

6維 7個路標0.505 9100.299 740

4維 7個路標0.505 9020.299 708

4維 5個路標0.420 9720.076 933

2.2.3 負載均衡的實現(xiàn)

負載均衡的一種實現(xiàn)方式是隨機散列法。當有一個服務請求時，從若干相同的備選服務器中隨機選擇其一對請求進行響應，從而避免單臺服務器的負載過重。許多DNS服務器都采用這種隨機的方法實現(xiàn)負載均衡。

為了使分布式搜索引擎實現(xiàn)負載均衡，確定一個網(wǎng)站的調(diào)度方案時，選擇坐標系中距離該網(wǎng)站最近的多個爬蟲作為備選調(diào)度節(jié)點，而不是只取最近的一個爬蟲作為單一調(diào)度節(jié)點。這樣，當需要抓取一個網(wǎng)站時，對該網(wǎng)站對應的若干個備選調(diào)度爬蟲進行隨機，選一個爬蟲抓取該網(wǎng)頁。這個方法可以在保證抓取效率的前提下，一定程度地實現(xiàn)系統(tǒng)的負載均衡。

3 實驗與分析

本文設計的分布式搜索引擎包括30個爬蟲，分別分布在北京(10個)、上海(10個)、廣州(9個)和哈爾濱(1個)。考慮到表1和2呈現(xiàn)出的規(guī)律，調(diào)度系統(tǒng)建立坐標系時，采用9個不同城市不同運營商的爬蟲作為路標節(jié)點(北京:電信1個、聯(lián)通1個、網(wǎng)通1個;上海:電信1個、聯(lián)通1個、網(wǎng)通1個;廣州:電信1個、聯(lián)通1個;哈爾濱:教育網(wǎng)1個)，建立8維坐標系。為了實現(xiàn)負載均衡，為每個網(wǎng)站選擇3個最優(yōu)的爬蟲作為備選調(diào)度節(jié)點。

為了測量整個系統(tǒng)的吞吐量，筆者精選了國內(nèi)分布在各省市自治區(qū)的203個較大型的網(wǎng)站。讓系統(tǒng)用三種調(diào)度方式抓取這203個網(wǎng)站。第一種調(diào)度方式是隨機調(diào)度法(random)，不對30個爬蟲作任何區(qū)分，對每個網(wǎng)站，隨機選擇30個爬蟲中的任意的一個進行抓取。第二種調(diào)度方式就是本文介紹的基于GNP算法的調(diào)度算法，每個網(wǎng)站選擇最優(yōu)的3個爬蟲隨機調(diào)度，這里將這種調(diào)度方法叫做Top3最優(yōu)調(diào)度法(Top3)。第三種調(diào)度方式也是基于GNP算法的調(diào)度算法，但只選擇最優(yōu)的1個爬蟲作為調(diào)度節(jié)點，因而叫做Top1最優(yōu)調(diào)度法(Top1)。圖2顯示了分布式搜索引擎在三種調(diào)度方式下抓取203個網(wǎng)站的吞吐量(throughput)。

如圖2所示，以幾個時間點為例，在第6 min，Top3調(diào)度的系統(tǒng)吞吐量比隨機調(diào)度的系統(tǒng)吞吐量高出436.5 MB，而Top1調(diào)度的系統(tǒng)吞吐量比隨機調(diào)度高出411.1 MB;在第12 min，Top3調(diào)度的系統(tǒng)吞吐量比隨機調(diào)度的系統(tǒng)吞吐量高出767.1 MB，而Top1調(diào)度的系統(tǒng)吞吐量比隨機調(diào)度高出674.5 MB。總體來看，隨著系統(tǒng)運行時間的增加，Top1和Top3調(diào)度的系統(tǒng)吞吐量與隨機調(diào)度的系統(tǒng)吞吐量的差值越來越大。隨機調(diào)度的系統(tǒng)吞吐量增長率大約為198.8 MB/min，而 Top3調(diào)度的系統(tǒng)吞吐量增長率大約為270.5 MB/min，比隨機調(diào)度高出36.1%;Top1調(diào)度的系統(tǒng)吞吐量增長率大約為242.6 MB/min，比隨機調(diào)度高出22.0%。可以看出，Top1和Top3調(diào)度明顯優(yōu)于隨機調(diào)度，顯示出按照網(wǎng)絡延遲進行爬蟲調(diào)度的優(yōu)勢。

直觀來說，Top1調(diào)度法選擇最優(yōu)的惟一一個爬蟲調(diào)度，Top3調(diào)度法隨機選擇最優(yōu)的三個爬蟲中的一個調(diào)度，那么Top1調(diào)度法就應該好于Top3調(diào)度法，但根據(jù)圖2顯示，Top1調(diào)度的系統(tǒng)性能反而略低于Top3調(diào)度的系統(tǒng)性能，這說明根據(jù)網(wǎng)絡時延的關系預測網(wǎng)頁下載速率的關系雖然有一定可行性，但并不能做到完全準確。網(wǎng)絡時延只是影響網(wǎng)頁下載速率的眾多因素之一，雖然這個因素的影響因子很大，但不能決定一切。

從203個網(wǎng)站中隨機挑選一個網(wǎng)站www.hljtele.com作單機吞吐量的測試，分布式搜索引擎只抓取該網(wǎng)站。這里只比較隨機調(diào)度法(random)和Top3最優(yōu)調(diào)度法(Top3)的吞吐量(throughput)，其結(jié)果如圖3所示。

圖3顯示的兩種調(diào)度方法的性能比較與系統(tǒng)吞吐量的性能比較結(jié)果相似，隨機調(diào)度的單機吞吐量增長率大約為0.45 MB/min，Top3調(diào)度的系統(tǒng)吞吐量增長率大約為2.38 MB/min，Top3調(diào)度方式的系統(tǒng)吞吐量增長率約為隨機調(diào)度的5倍。Top3最優(yōu)調(diào)度法應用在www.hljtele.com上的效果非常明顯，大大提升了爬蟲系統(tǒng)對該網(wǎng)站的抓取效率。

綜上，從系統(tǒng)吞吐量的實驗中可以看出，基于GNP算法的最優(yōu)調(diào)度方法相對于傳統(tǒng)方法有一定的優(yōu)勢。

4 結(jié)束語

GNP算法是一種有效的進行網(wǎng)絡估計的方法。它將廣域網(wǎng)模擬為幾何坐標系，并賦予廣域網(wǎng)中的主機節(jié)點惟一的坐標值，將主機間網(wǎng)絡距離的測量轉(zhuǎn)換為坐標系中節(jié)點間距離的計算。由于GNP的實用性，本文提出將其應用于分布式搜索引擎的爬蟲調(diào)度上，并首次嘗試用應用層網(wǎng)絡距離測量代替?zhèn)鹘y(tǒng)的網(wǎng)絡層距離測量。分布式搜索引擎中不同的爬蟲節(jié)點抓取不同網(wǎng)站的性能各異，調(diào)度算法需要得到抓取某個網(wǎng)站的最優(yōu)爬蟲，因而需要測量所有爬蟲到該網(wǎng)站的距離。基于GNP算法的調(diào)度策略是對直接測量法的改進，它可以較準確地通過少量的測量值計算出所有網(wǎng)絡時延，有助于提高抓取任務的響應速度，同時減少了對廣域網(wǎng)流量的占用，進而提高整個系統(tǒng)的服務質(zhì)量。本文給出的實驗充分證明了基于GNP算法的調(diào)度策略相較于傳統(tǒng)方法有比較明顯的優(yōu)勢。

參考文獻:

[1]BAEZA-YATES R， CASTILLO C， JUNQUEIRA F， et al. Challenges in distributed information retrieval[C]//Proc of International Confe-rence on Data Engineering. Istanbul， Turkey: IEEE CS Press， 2007.

[2]BOSWELL D. Distributed high-performance Web crawlers: a survey of the state of the art[EB/OL].(2003)[2009-05-15]. http://www.cs.ucsd. edu/dboswell/PastWork/WebCrawlingSurvey.pdf.

[3]NG T S E ， ZHANG Hui. Towards global network positioning [C]//Proc of the 1st ACM SIGCOMM Conference on Internet Measurement. New York:ACM Press， 2001:25-29.

[4]FRANCIS P， JAMIN S， PAXSON V， et al. An architecture for a global internet host distance estimation service[C]//Proc of IEEE INFOCOM’99. New York:ACM Press， 1999: 210-217.

[5]柯怡， 林宇， 金躍輝，等. GNP算法與基于GNP的全局負載均衡技術[C]//第九屆全國青年通信學術會議論文集. 2004.

[6]KARGER D， LEHMAN E， LEIGHTON T， et al. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web[C]//Proc of the 29th Annual ACM Symposium on Theory of Computing. New York:ACM Press， 1997: 654-663.

[7]CAMBAZOGLU B ， KARACA E， KUCUKYILMAZ T， et al. Architecture of a grid-enabled Web search engine[J]. Information Processing and Management， 2007， 43(3):609-623.

[8]EXPOSTO J， MACEDO J， PINA A， et al. Geographical partition for distributed Web crawling[C]//Proc of the Workshop on Geographic Information Retrieval. New York:ACM Press， 2005:55-60.

[9]GOVINDAN R， TANGMUNARUNKIT H. Heuristics for Internet map discovery[C]//Proc of IEEE INFOCOM Conference. Tel Aviv， Israel: IEEE Press， 2000:1371-1380.

(上接第445頁)

[4]SHAHBAZIAN E， ROGOVA G， VALIN P. Data fusion for situation monitoring， incident detection， alert and response management [M]. Washington DC:IOS Press， 2005.

[5]KOES M， SYCARA K， NOURBAKHSH I. A constraint optimization framework for fractured robot teams[C]//Proc of the 5th International Joint Conference on Autonomous Agents and Multi-agent Systems. New York:ACM Press， 2006:491-493.

[6]STROMBERG D， ANDERSSON M， LANTZ F. On platform-based sensor management[C]//Proc of the 5th International Conference on Information Fusion. [S.l.]:ISIF IEEE Press， 2002:600-607.

[7]KNOLL A， MEINKOEHN J. Data fusion using large multi-agent networks: an analysis of network structure and performance[C]//Proc of IEEE International Conference on Multisensor Fusion and Integration for Intelligent Systems. Las Vegas:IEEE Press， 1994:113-120.

[8]SMETS P. Decision making in the TBM: the necessity of the Pignistic transformation [J]. International Journal of Approximate Reasoning， 2005， 38(2):133-147.

[9][EB/OL]. http://www.fira.net/.