第２８卷第５期２００８年５月?文章編號(hào)：１００１—９０８１（２００８）０５—１１１４—０３計(jì)算機(jī)應(yīng)用ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓＶ０１．２８Ｎｏ．５Ｍａｙ２００８網(wǎng)絡(luò)爬蟲效率瓶頸的分析與解

第２８卷第５期２００８年５月?

文章編號(hào)：１００１—９０８１（２００８）０５—１１１４—０３

計(jì)算機(jī)應(yīng)用

ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓ

Ｖ０１．２８Ｎｏ．５

Ｍａｙ２００８

網(wǎng)絡(luò)爬蟲效率瓶頸的分析與解決方案

尹江，尹治本，黃洪

（西南交通大學(xué)信息科學(xué)與技術(shù)學(xué)院，成都６１００３１）

（ｊ＿ｙｅｅｎ＠１６３．ｃｏｒｎ）

‘

摘要：網(wǎng)絡(luò)爬蟲的效率，直接關(guān)系到搜索引擎系統(tǒng)為用戶提的供服務(wù)質(zhì)量。如何設(shè)計(jì)高效、快速的網(wǎng)絡(luò)爬蟲，成為目前網(wǎng)絡(luò)爬蟲研究的熱點(diǎn)。要提高網(wǎng)絡(luò)爬蟲的爬行效率，除了需要改進(jìn)網(wǎng)絡(luò)爬蟲的爬行策略之外，還需要優(yōu)化網(wǎng)絡(luò)爬自身的設(shè)計(jì)，改進(jìn)網(wǎng)絡(luò)爬蟲自身的結(jié)構(gòu)，消除效率瓶頸。通過(guò)對(duì)網(wǎng)絡(luò)爬蟲結(jié)構(gòu)、應(yīng)用環(huán)境以及用戶要求的分析，提出一個(gè)通用網(wǎng)絡(luò)爬蟲的改進(jìn)設(shè)計(jì)方案，并通過(guò)實(shí)驗(yàn)得到較好的測(cè)試結(jié)果。

關(guān)鍵詞：爬行策略；套接字；多線程；網(wǎng)絡(luò)爬蟲中圖分類號(hào)：ＴＰ３１１

文獻(xiàn)標(biāo)志碼：Ａ

Ｅｆｆｉｃｉｅｎｃｙｂｏｔｔｌｅｎｅｃｋｓａｎａｌｙｓｉｓａｎｄｓｏｌｕｔｉｏｎｏｆ

ＹＩＮＪｉａｎｇ，ＹＩＮＺｈｉ—ｂｅｎ，ＨＵＡＮＧＨｏｎｇ

Ｗｅｂ

ｃｒａｗｌｅｒ

（ＳｃｈｏｏｌｏｆＩｎｆｏｒｍａｔｉｏｎ

Ａｂｓｔｒａｃｔ：Ｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆ

Ｈｏｗ

ｔｏ

ＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，ＣｈｅｎｇｄｕＳｉｃｈｕａｎ６１００３１，Ｃｈｉｎａ）

ｔｏ

ａ

ｗｅｂｃｒａｗｌｅｒｄｅｔｅｒｍｉｎｅｓｔｈｅｑｕａｌｉｔｙｏｆｓｅｒｖｉｃｅｓ

ａ

ａ

ｗｅｂｓｅａｒｃｈｉｎｇｓｙｓｔｅｍｏｆｆｅｒｓ

ｉｔｓｕｓｅｒｓ．ｔｏ

ｄｅｓｉｇｎ

ａ

ｍｏｒｅｅｆｆｉｃｉｅｎｔａｎｄｆａｓｔｅｒｗｅｂｃｒａｗｌｅｒｉＳｂｅｃｏｍｉｎｇ

ａ

ｈｏｔｉｓｓｕｅｉｎｔｈｅｒｅｓｅａｒｃｈｏｆｗｅｂｃｒａｗｌｅｒ．Ｉｎｏｒｄｅｒｒａｉｓｅ

ｔｈｅｃｒａｗｌｉｎｇｅｆｆｉｃｉｅｎｃｙｏｆｓｙｓｔｅｍ

ｗｅｂｃｒａｗｌｅｒ，ｔｈｅｃｒａｗｌｉｎｇ

ｓｔｒｕｃｔｕｒｅ

ｓｔｒａｔｅｇｙｔｏ

ｎｅｅｄｓ．ｔｏ

ｂｅｒｅｆｏｒｍｅｄ．Ｂｅｓｉｄｅｓ，ｔｈｅｄｅｓｉｇｎｏｆｔｈｅｗｅｂｃｒａｗｌｅｒ

ｔｏ

ｈａｓｔｏｂｅｏｐｔｉｍｉｚｅｄａｎｄｉｔｓ

ａ

ａｌｓｏｎｅｅｄｓ

ｂｅｉｍｐｒｏｖｅｄｅｌｉｍｉｎａｔｅｂｏｔｔｌｅｎｅｃｋｓ．Ｉｎｔｈｉｓｐａｐｅｒ，ａｎｉｍｐｒｏｖｅｄ

ｓｃｈｅｍｅｏｆｄｅｓｉｇｎｉｎｇ

ｕｓｅｒ

ｇｅｎｅｒａｌｗｅｂｃｒａｗｌｅｒＷａｓｐｒｅｓｅｎｔｅｄｔｈｒｏｖｌｇｈａｎａｌｙｚｉｎｇｃｒａｗｌｅｒ＇ｓｓｔｍｃｔｕｒｅ，ａｐｐｌｉｃａｔｉｏｎｅｎｖｉｒｏｎｍｅｎｔａｎｄ

ｂｅｔｔｅｒｅｆｆｉｃｉｅｎｃｙｉｔｈａｓ．

ｒｅｑｕｉｒｅｍｅｎｔ，ａｎｄｔｈｅｐｒｅｆｅｒａｂｌｅｔｅｓｔｉｎｇｒｅｓｕｌｔｈａｓｐｒｏｖｅｎＫｅｙｗｏｒｄｓ：ｃｒａｗｌ

ｓｔｒａｔｅｇｙ；ｓｏｃｋｅｔ；ｍｕｌｔｉ—ｔｈｒｅａｄ；Ｗｅｂｃｒａｗｌｅｒ

網(wǎng)絡(luò)爬蟲是搜索引擎的重要組成部分。目前爬蟲系統(tǒng)的基本設(shè)計(jì)原則為：在遵循ＲＥＰ原則以及對(duì)服務(wù)器不造成致命沖擊的前提下‘¨，盡可能使爬蟲爬行速度快、數(shù)據(jù)下載量大及信息抓取準(zhǔn)確。必須要消除制約爬蟲自身爬行效率的瓶頸，使爬蟲達(dá)到高效。１

快但針對(duì)性較差，不能提高搜索的查準(zhǔn)率。１．２基于價(jià)值回報(bào)的爬行策略

網(wǎng)絡(luò)爬蟲理想的設(shè)計(jì)是高速、完整地遍歷整個(gè)Ｉｎｔｅｍｅｔ。往往需要對(duì)單純的圖算法爬行策略進(jìn)行改進(jìn)，合理地對(duì)資源（網(wǎng)站、頁(yè)面及ＵＲＬ）進(jìn)行價(jià)值評(píng)價(jià)，優(yōu)先處理值高的資源，滯后處理甚至忽略價(jià)值低的資源。目前實(shí)際應(yīng)用的策略主要有：基于鏈接自身質(zhì)量評(píng)價(jià)的ＰａｇｅＲａｎｋ算法以及ＨＩＴＳ算法、基于ＵＲＬ主題相關(guān)性評(píng)價(jià)的ＢｅｓｔＳｅａｒｃｈ算法及Ｆｉｓｈ算法等忙１。除此以外機(jī)器學(xué)習(xí)理論、人工神經(jīng)網(wǎng)絡(luò)算法、螞蟻算法等方法也在不斷地應(yīng)用到網(wǎng)絡(luò)爬蟲尋路優(yōu)化策略中＂１。

網(wǎng)絡(luò)爬蟲簡(jiǎn)介

通用網(wǎng)絡(luò)爬蟲爬行的基本策略是將Ｉｎｔｅｒｎｅｔ視為一幅復(fù)

雜的有向圖。利用這樣的模型，網(wǎng)絡(luò)爬蟲可以采用圖的廣度優(yōu)先搜索算法或圖的深度優(yōu)先搜索算法爬行Ｉｎｔｅｒａｃｔ并下載數(shù)據(jù)。

１．１廣度優(yōu)先、深度優(yōu)先爬行策略

一個(gè)網(wǎng)頁(yè)即為一個(gè)節(jié)點(diǎn)，網(wǎng)頁(yè)中指向其他頁(yè)面的ＵＲＬ為該節(jié)點(diǎn)到其他節(jié)點(diǎn)的路徑，整個(gè)Ｉｎｔｅｒｎｅｔ由大量這樣的節(jié)點(diǎn)構(gòu)成一幅龐大的有向圖Ｇ（Ｅ，ｙ），如圖１所示。

。

２爬蟲的瓶頸分析與解決方案

２．１效率瓶頸分析

爬蟲的效率主要受到以下因素的制約：網(wǎng)絡(luò)延時(shí)和爬蟲本地運(yùn)行效率，如圖２所示。

圖１Ｉｎｔｅｍｅｔ的有向圖模型不意圖

圖２網(wǎng)絡(luò)爬蟲的效率瓶頸示意

其中矩形代表頁(yè)面，箭頭線為ＵＲＬ，該圖顯示了網(wǎng)頁(yè)間相互鏈接的關(guān)系。無(wú)論是廣度優(yōu)先還是深度優(yōu)先策略，其時(shí)間漸近復(fù)雜度都為０（ｅ＋。），其中”，ｅ分別為圖的節(jié)點(diǎn)與邊的數(shù)量，即與Ｉｎｔｅｒｎｅｔ中的網(wǎng)頁(yè)規(guī)模直接相關(guān)。上述爬行策略對(duì)各個(gè)網(wǎng)站、頁(yè)面和ＵＲＬ的價(jià)值回報(bào)并不評(píng)估篩選，爬行速度

收稿日期：２００７—１１—１２；修回日期：２００８一Ｏｌ—０４。

網(wǎng)絡(luò)爬蟲最主要的效率瓶頸在于網(wǎng)絡(luò)帶寬利用率低、適應(yīng)性差；功能模塊設(shè)計(jì)不良；各個(gè)功能模塊協(xié)同工作效率低下等。

目前絕大多數(shù)爬蟲系統(tǒng)都采用并發(fā)工作流的設(shè)計(jì)，以充分利用網(wǎng)絡(luò)帶寬。由于基于進(jìn)程的并發(fā)代價(jià)較基于線程的并

作者簡(jiǎn)介：尹江（１９８１一）。男，四川成都人，碩士研究生，主要研究方向：計(jì)算機(jī)算法理論、軟件工程；尹治本（１９５４一）．男，云南騰沖人。教

授，主要研究方向：計(jì)算機(jī)算法設(shè)計(jì)、軟件工程；黃洪（１９５９一）。男，四川達(dá)州人，副教授，主要研究方向：數(shù)據(jù)庫(kù)、辦公自動(dòng)化。

萬(wàn)方數(shù)據(jù)　

第５期

尹江等：網(wǎng)絡(luò)爬蟲效率瓶頸的分析與解決方案

１１１５

發(fā)而言相對(duì)較高，故大部分網(wǎng)絡(luò)爬蟲都是多線程架構(gòu)設(shè)計(jì)＂’。然而這并不能完全疏通爬蟲的效率瓶頸。

２．２

網(wǎng)絡(luò)資源利用率的提升策略

基于Ｓｏｃｋｅｔ（以下統(tǒng)稱套接字）的網(wǎng)絡(luò)爬蟲使用套接字，

通過(guò)發(fā)送ＨＥＡＤ、ＧＥＴ、ＰＯＳＴ等Ｈ１．ｒＰ方法，爬蟲能在ＨｒｌｌＰ協(xié)議上通過(guò)指定的端口與服務(wù)器進(jìn)行數(shù)據(jù)信息交換＂Ｊ。爬行過(guò)程中爬蟲需要兩次使用網(wǎng)絡(luò)資源：域名解析與頁(yè)面采集，致使網(wǎng)絡(luò)延時(shí)占據(jù)絕大部分爬蟲運(yùn)行時(shí)間，形成爬蟲運(yùn)行效率的瓶頸ｊ在實(shí)際測(cè)試中，對(duì)１００個(gè)主機(jī)名通過(guò)查詢ＤＮＳ服務(wù)器得到ＩＰ地址，平局時(shí)間為３２７毫秒／個(gè)。其中有少數(shù)域名的查詢返回時(shí)間甚至超過(guò)數(shù)秒。同時(shí)，某些數(shù)據(jù)量大的網(wǎng)頁(yè)的傳輸?shù)却龝r(shí)間也會(huì)超過(guò)數(shù)秒。

２．２．１

ＤＮＳ解析

引入并優(yōu)化ＤＮＳ緩存模塊。ＵＲＬ中重復(fù)的域名使用頻繁，ＤＮＳ本地緩存能大量減少因重復(fù)的域名解析造成的網(wǎng)絡(luò)占用及等待時(shí)間。為提高域名緩存模塊的效率，本文設(shè)計(jì)了一個(gè)使用哈希表為表頭、以線性指針序列作為索引并以域名長(zhǎng)度為跳躍單位的數(shù)據(jù)結(jié)構(gòu)保存域名，暫命名為“域名跳檢哈希表”，能夠高效的寫入域名、檢索域名、為域名排序以及高效地按需求替換域名。其表結(jié)構(gòu)的一個(gè)環(huán)節(jié)如圖３所示。

Ｉｄｘ

＿＿一指引數(shù)組

＿＿一２３權(quán)值

＿＿一Ｐ１＼

域名池

＿＿一

Ｐ２域名ＩＩＰｌ域名ＩＩＰＪ域名ＪｌＰ

。●一

Ｃ

●●●

＿＿——

域名計(jì)數(shù)

圖３用于ＤＮＳ緩存的域名表結(jié)構(gòu)

圖３展示了域名表的構(gòu)造與關(guān)鍵環(huán)節(jié)。改進(jìn)后域名解析過(guò)程大致如下：使用域名首字符ＡＳＣＩＩ碼值與域名長(zhǎng)度散列域名到哈希表頭。依照線性指針序列的下標(biāo)索引，通過(guò)域名頭指針依次檢索已存在ＩＰ映射的域名，若該域名還未在表中則調(diào)用ＤＮＳ解析過(guò)程。解析成功便將域名寫入域名表最后空位，ＩＰ則寫入對(duì)應(yīng)ＩＰ段內(nèi)，并更新域名池信息（包括權(quán)信息、數(shù)量信息等）；失敗則返回錯(cuò)誤代碼通知調(diào)用者。在寫入時(shí)若發(fā)現(xiàn)域名池滿則替換掉部分權(quán)值低的域名。若該域名已經(jīng)過(guò)解析則使用對(duì)應(yīng)ＩＰ，并對(duì)域名進(jìn)行相應(yīng)的加權(quán)（如使用頻率、最近使用時(shí)間等）。為保證權(quán)值高的域名能夠被快速地映射出ＩＰ，在若干次域名解析與寫入過(guò)程后需要為域名排序。排序時(shí)以線性指針鏈索引遍歷所有存在域名的權(quán)值，需要改變域名順序時(shí)僅僅交換域名指針域與權(quán)值域。該結(jié)構(gòu)兼有哈希表、鏈表與線性表的優(yōu)點(diǎn)，下面是主要操作的算法時(shí)間效率分析：

插入域名：新域名ｈ到達(dá)時(shí)，計(jì)算其ＨＡＳＨ索引的時(shí)間為固定常數(shù)，計(jì)為Ｌ。由于域名池空位地址＝域名池基址十域名個(gè)數(shù)×域名長(zhǎng)度，故尋址域名池空位時(shí)間為固定常數(shù)乃。另計(jì)域名的寫入操作時(shí)間為乃＝Ｉ（ｚ），ｚ為域名長(zhǎng)度。則可知一個(gè)新域名的插入時(shí)間復(fù)雜度為瓦＋疋＋瓦一Ｄ（ｃ）。

域名排序：為域名按權(quán)值排序時(shí)僅僅做指針交換操作，大大優(yōu)于單純的線性表結(jié)構(gòu)。設(shè)某個(gè)域名池存放長(zhǎng)度為ｎ的域名ｍ個(gè)，若單純使用線性表結(jié)構(gòu)操作則每次移動(dòng)一個(gè)域名需要移動(dòng)Ｉｔ個(gè)元素３次，若每個(gè)元素都需換位且僅需１次，則至少需要３ｎｍ次移動(dòng)操作，而在本文所采用策略下ｍ—ｌ，即效率為普通線性結(jié)構(gòu)的約ｍ倍。

域名映射：新域名ｈ到達(dá)時(shí)，根據(jù)其首字符編碼以及ｈ的

萬(wàn)　

方數(shù)據(jù)長(zhǎng)度ｆ計(jì)算ＨＡＳＨ索引，探測(cè)ｈ可能存在映射的域名池的時(shí)間計(jì)為固定常數(shù)正?，F(xiàn)在分析ｈ在池中尋找匹配的平均時(shí)間疋。設(shè)域名池已有ｎ個(gè)域名，每個(gè)域名固定長(zhǎng)度為２，ｈ中第ｉ個(gè)字符失配而前ｉ一１個(gè)字符匹配的概率為Ｐｉ，ｉ＝１，２…Ｚ，又設(shè)ｈ

ｆ

被某個(gè)域名完全匹配的概率為Ｐ，則有Ｐ＋乏：Ｐｌ，且第ｉ個(gè)字

哥

符匹配后已經(jīng)比較過(guò)的字符數(shù)為厶。設(shè)Ｐ’；為ｈ與域名池中前ｉ—１個(gè)域名失配但與第ｉ個(gè)域名匹配的概率?，F(xiàn)做Ｊ７＼『次域名映射操作，則可知：

ｌ

２

疋＝——１尹一＋——１蘆—一”．＋

Ｎ×Ｐ’，×∑甄（￡）Ｎ×Ｐ’２×∑甌（己）＾

?

Ｎ×Ｐ’?！痢飘T（Ｌ）

———１Ｐ—一

Ⅳ

（１）

、１

７

ｌ

其中ＥＸ。＝Ｐ

Ｘ

Ｌ＋乏：（（１一Ｐｉ）ב），ｉ＝１，２，…，ｎ為

骨

域名池中每個(gè)域名與ｈ失配所移動(dòng)的字符數(shù)的數(shù)學(xué)期望。該結(jié)構(gòu)的優(yōu)勢(shì)體現(xiàn)在當(dāng)池中域名某個(gè)字符與ｈ中字符失配時(shí)，可以直接跳到下一個(gè)域名起始處比對(duì)，即每次映射操作比較字符數(shù)遠(yuǎn)小于廳×Ｚ，同時(shí)還可以加入模式匹配優(yōu)化策略，域名越長(zhǎng)，效果越好。

多線程、非阻塞套接字與ＷＳＡＥｖｅｎｔＳｅｌｅｃｔ（異步）模型的組合設(shè)計(jì)。核心思想是采用適應(yīng)性更強(qiáng)的方法，最大限度利用網(wǎng)絡(luò)資源埔Ｊ，同時(shí)縮短線程執(zhí)行周期。在采集頁(yè)面的過(guò)程中，爬蟲需要長(zhǎng)時(shí)間等待數(shù)據(jù)到達(dá)協(xié)議緩沖區(qū)。若采用多線程并發(fā)爬行的設(shè)計(jì)，應(yīng)開啟多個(gè)爬行線程并讓等待中的線程阻塞，既能充分地利用閑置的網(wǎng)絡(luò)資源，又盡可能地減少了同時(shí)占有ＣＰＵ的線程數(shù)量，縮短線程執(zhí)行周期。雖然事件選擇模型本身支持套接字組管理方式，但套接字組中的最大套節(jié)字?jǐn)?shù)極為有限（６４個(gè)），且必須維護(hù)線程池使系統(tǒng)達(dá)到高效。此外，套接字組管理增加了套接字行為的管理難度。本文采用每個(gè)異步套接字綁定一個(gè)工作線程的創(chuàng)新設(shè)計(jì)，線程隊(duì)列在爬蟲開始爬行前創(chuàng)建，在爬行過(guò)程中不會(huì)被撤銷，無(wú)需線程池且讀寫操作不分離，既提高了效率又方便管理。具體實(shí)施方案如下：１）將套接字設(shè)定為非阻塞方式，并綁定在一個(gè)ＷＳＡＥＶＥＮＴ對(duì)象上，通過(guò)探察這個(gè)對(duì)象的狀態(tài)以獲知發(fā)生了哪些需要處理的網(wǎng)絡(luò)事件，如可讀取、可發(fā)送、關(guān)閉連接等等。２）在沒(méi)有相關(guān)的事件發(fā)生且不滿足采集工作結(jié)束條件時(shí)，線程被阻塞一個(gè)超時(shí)。３）若在系統(tǒng)阻塞線程等待數(shù)據(jù)的過(guò)程中有數(shù)據(jù)到達(dá)，系統(tǒng)會(huì)喚醒線程繼續(xù)讀取所有到達(dá)數(shù)據(jù)，同時(shí)超時(shí)計(jì)數(shù)器復(fù)位。４）否則超時(shí)計(jì)數(shù)器加１，繼續(xù)探察事件對(duì)象。同時(shí)每次阻塞前首先檢查采集工作結(jié)束條件（如超時(shí)計(jì)數(shù)器為０、對(duì)方關(guān)閉連接等以及文件已結(jié)尾），判斷是否中止數(shù)據(jù)讀取操作，盡可能縮短線程執(zhí)行周期。通過(guò)此種設(shè)計(jì)，一方面線程因等待數(shù)據(jù)阻塞時(shí)，ＣＰＵ得以盡可能多地執(zhí)行有效運(yùn)算；同時(shí)，通過(guò)事件機(jī)制，使得套接字工作能適應(yīng)更加復(fù)雜的網(wǎng)絡(luò)環(huán)境。

圖４為爬行線程工作隊(duì)列的時(shí)間片分布示意圖，圖中每組矩形表示一個(gè)爬行線程工作隊(duì)列，其豎直方向的長(zhǎng)度顯示了一個(gè)頁(yè)面采集過(guò)程的周期長(zhǎng)度。矩形中的灰色部分為線程阻塞時(shí)間，白色部分為多個(gè)線程共享的ＣＰＵ時(shí)間，黑色部分為線程獨(dú)占的ＣＰＵ時(shí)間，線程隊(duì)列旁的箭頭線長(zhǎng)短表示線程

２．２．２頁(yè)面采集

１１１６

計(jì)算機(jī)應(yīng)用第２８卷

的執(zhí)行時(shí)間。圖４（ｃ）顯示了一種理想狀態(tài)（規(guī)定線程必有一次阻塞）：每個(gè)線程的ＣＰＵ時(shí)間獨(dú)享，且阻塞的時(shí)間最短并只阻塞一次。從圖４（ｂ）中可以看出，由于事件機(jī)制能及時(shí)喚醒阻塞中的線程，減少了線程的不必要的阻塞時(shí)間。設(shè)ｎｉ為某頁(yè)面分次傳輸?shù)恼鎸?shí)耗時(shí)，并且發(fā)生ｍ次。又設(shè)疋；為人工設(shè)定超時(shí)上限，超時(shí)等待次數(shù)為ｎ次?；谙旅娴氖聦?shí)：（１）超時(shí)等待總時(shí)間必須大于或等于頁(yè)面?zhèn)鬏斦鎸?shí)耗時(shí)才可能正確的下載頁(yè)面；（２）每次數(shù)據(jù)到達(dá)前人工的超時(shí)等待必至少發(fā)生一次；（３）探查到數(shù)據(jù)未到達(dá)后的等待超時(shí)應(yīng)至少等于頁(yè)面?zhèn)鬏敃r(shí)間¨１。則有對(duì)任意的ｉ，ｎ≥ｍ，Ｔ２ｉ≥ＴＩ；，可知浪費(fèi)的等待時(shí)間為：

?

ｒ＝∑（疋ｉ一瓦；）＋ｙ×∑瓦ｉ

（２）

其中引入文檔結(jié)束標(biāo)志檢測(cè)機(jī)制時(shí)，概率等于０，否則等于１。通過(guò)優(yōu)化設(shè)計(jì)，由于事件通知機(jī)制會(huì)使得砭ｉ逼近Ｌ。，使得方程右邊第一項(xiàng)遠(yuǎn)小于普通設(shè)計(jì)方式下的結(jié)果，大大縮短單次頁(yè)面采集周期。

（ａ）普通設(shè)計(jì)

（ｂ）改進(jìn)設(shè)計(jì)

（ｃ）理想狀態(tài)

圖４改進(jìn)機(jī)制的效率提升示意

２．３爬蟲本地運(yùn)行效率的優(yōu)化方案

ｒ除網(wǎng)絡(luò)資源外，爬蟲自身各部分的運(yùn)行效率也可能成為爬蟲工作效率的瓶頸。

多線程工作同步是爬蟲系統(tǒng)正常工作的必要前提悼Ｊ，但大量工作線程同步意味著排隊(duì)等待時(shí)間增加，在共享數(shù)據(jù)操作頻繁的環(huán)境下，系統(tǒng)工作效率甚至?xí)蚓€程數(shù)量的增加而下降，同時(shí)還會(huì)帶來(lái)大量的系統(tǒng)開銷來(lái)實(shí)現(xiàn)Ｉ臨界區(qū)操作，造成效率瓶頸。本文采用ＵＲＬ隊(duì)列獨(dú)享，ＵＲＬ散列結(jié)構(gòu)共享的結(jié)構(gòu)設(shè)計(jì)。實(shí)際測(cè)試發(fā)現(xiàn)，ＵＲＬ隊(duì)列是整個(gè)爬蟲中訪問(wèn)最頻繁的部分，應(yīng)盡量避免同步問(wèn)題?，F(xiàn)有線程工作隊(duì)列Ｐ．…Ｐｎ，若其中有一半的線程在做ｍ（所有線程的平均值）個(gè)ＵＲＬ入隊(duì)列操作，并且其中有２０％的操作重疊，另設(shè)平均一次人隊(duì)列操作時(shí)間為ｔ。假定ＣＰＵ線程調(diào)度均勻（此時(shí)線程入隊(duì)列操作排隊(duì)等待時(shí)間平均分?jǐn)偟矫總€(gè)線程上），則得到同步等待時(shí)間，如式（３）：

ｎ

瓦＝ａ

Ｉ－－１≯‘

Ｅ（Ｂｍ；ｔ。）

（３）

其中口為試圖訪問(wèn)臨界區(qū)線程的比例，盧為人隊(duì)列操作的平均重疊率，／７／，。、ｔ１分別由平均值ｍ、ｔ取代。按上述條件粗略地計(jì)算出線程Ｐ；在ＵＲＬ人隊(duì)列的過(guò)程中，由于同步浪費(fèi)的等待時(shí)

間為Ｅ＝ｎｍｔ／１０。由此可看出每個(gè)線程包含胄己的ＵＲＬ隊(duì)

列是非常合理的。另一方面，ＵＲＬ散列結(jié)構(gòu)必須共享，原因是ＵＲＬ消重效果不能犧牲，若作為線程獨(dú)立的結(jié)構(gòu)，需要大量額外的時(shí)間、空間上的開銷來(lái)為每個(gè)線程同步ＵＲＬ消重散列結(jié)構(gòu)的數(shù)據(jù)。其次，ＵＲＬ消重操作較為分散（本文設(shè)計(jì)的爬蟲消重工作只在頁(yè)面采集過(guò)程前端進(jìn)行），操作時(shí)間短且各線程的重疊操作很少，對(duì)整個(gè)工作隊(duì)列的運(yùn)行效率影響不

明顯。

萬(wàn)　

方數(shù)據(jù)３測(cè)試與小結(jié)

綜合以上論述，筆者在Ｖｉｓｕａｌ

Ｓｔｕｄｉｏ

６．０環(huán)境下用ｃ＋＋

語(yǔ)言開發(fā)了一個(gè)工作在Ｗｉｎｄｏｗｓ系統(tǒng)上采用廣度優(yōu)先策略的通用爬蟲，主要目的在于測(cè)試在選定爬行策略的前提下，爬蟲自身設(shè)計(jì)的改進(jìn)以及主要瓶頸的消除所帶來(lái)的爬行效率提升。測(cè)試環(huán)境如下：ＩｎｔｅｌＰ４２．８

ＧＨｚ（ＣＰＵ）；ＤＤＲ４００１ＧＢ（內(nèi)

存）；７２００

Ｒｐｍ８０

ＧＢ串口（硬盤）；ＷｉｎｄｏｗｓｘＰ（操作系統(tǒng)）；

校園網(wǎng)網(wǎng)通（網(wǎng)絡(luò)）。該系統(tǒng)結(jié)構(gòu)如圖５所示。

圖５ＳＰＩＤＥＲ爬蟲系統(tǒng)結(jié)構(gòu)

通過(guò)該系統(tǒng)對(duì)ＤＮＳ緩存模塊的引入、網(wǎng)絡(luò)交互模型選擇、并發(fā)優(yōu)化閾值以及ＵＲＬ隊(duì)列構(gòu)造策略等對(duì)爬蟲效率的影響進(jìn)行測(cè)試。

表ｌ三大門戶網(wǎng)站首頁(yè)下載測(cè)試數(shù)據(jù)（２００７年６月７日）

表１為對(duì)三大門戶網(wǎng)站的首頁(yè)的下載采用不同設(shè)計(jì)所得到的結(jié)果比較?？梢钥闯?，在Ｓｅｒｖｅｒ不與Ｃｌｉｅｎｔ保持長(zhǎng)連接時(shí)，優(yōu)化效果最為明顯，采集周期縮短近７０％；而保持長(zhǎng)連接的情況中，若引入文檔結(jié)束檢查機(jī)制，也有頗為明顯的改善。

圖６顯示了ＤＮＳ緩存的引入及ＷＳＡ事件機(jī)制對(duì)爬蟲效率的影響，其中橫坐標(biāo)表示爬蟲的運(yùn)行時(shí)間，以１５ｍｉｎ為單位間隔；縱坐標(biāo)為爬蟲的數(shù)據(jù)采集量，以千兆字節(jié)計(jì)?？梢钥吹?，引入ＤＮＳ緩存使爬蟲效率提升了近兩倍，而事件選擇模型與套接字綁定工作線程的組合設(shè)計(jì)也大大提升爬蟲的爬行效率，達(dá)到了設(shè)計(jì)目的。

（ａ）緩存帶來(lái)的效率差異

Ｃｏ）網(wǎng)絡(luò)１０模型選擇帶來(lái)的效率差異

圖６測(cè)試數(shù)據(jù)比較

表２列出了不同結(jié)構(gòu)的爬蟲在本文所述測(cè)試環(huán)境下爬行可以看到ＵＲＬ隊(duì)列共享對(duì)爬蟲工作效率的負(fù)面影響也頗為明

（下轉(zhuǎn)第１１１９頁(yè)）

３０ｍｉｎ所測(cè)得的關(guān)鍵綜合數(shù)據(jù)。從上面的數(shù)據(jù)中，還

第５期張磊等：一個(gè)新的基于能量和距離的傳感器網(wǎng)絡(luò)協(xié)議１１１９而不是如ＬＥＡＣＨ那樣隨機(jī)地輪循簇首。充分說(shuō)明ＥＤＢＣＭ首選擇時(shí)充分考慮了節(jié)點(diǎn)能量和到基站的距離，簇首質(zhì)量較協(xié)議提高了網(wǎng)絡(luò)的能量有效性，能提供更多數(shù)據(jù)來(lái)刻畫傳感高；數(shù)據(jù)發(fā)送采用了改進(jìn)的多跳路由。仿真結(jié)果表明，與區(qū)域，更好地完成網(wǎng)絡(luò)所擔(dān)負(fù)的任務(wù)。ＬＥＡＣＨ協(xié)議相比，該算法提高了基站接收的數(shù)據(jù)量，明顯延

長(zhǎng)了網(wǎng)絡(luò)的生存壽命。今后，可用ＭＡＴＬＡＢ／ＯＰＮＥＴ在大型

矗ｌ網(wǎng)絡(luò)中做進(jìn)一步的仿真測(cè)試。另外，數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中潛在的啦

瓤數(shù)據(jù)包丟失和時(shí)延問(wèn)題，也是要研究的問(wèn)題。

Ｓ

娶參考文獻(xiàn)：

幫

磐【１】宋文，王兵．周應(yīng)賓，等．無(wú)線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用【Ｍ】．北瑚京：電子工業(yè)出版社，２００７．

【２】ＨＥＩＮＺＥＬＭＡＮＷＲ，ＣＨＡＮＤＲＡＫＡＳＡＮＡ，ＢＡＬＡＫＲＩＳＨＮＡＮＨ．

Ａｎａｐｐｌｉｃａｔｉｏｎ－ｓｐｅｃｉｆｉｃｐｒｏｔｏｃｏｌａｒｃｈｉｔｅｃｔｕｒｅｆｏｒｗｉｒｅｌｅｓｓｍｉｃｒｏｓｅｎｓｏｒ

仿真時(shí)Ｉ’日Ｊ／ｓｎｅｔｗｏｒｋｓ【Ｊ】．ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓＯｎＷｉｒｅｌｅｓｓＣｏｍｍｕｎｉｃａｔｉｏｎｓ，

圖４ＬＥＡＣＨ和ＥＤＢＣＭ基站數(shù)據(jù)量比較２００２，１（４）：６６０—６７０．

【３】ＬＩＮＤＳＥＹＳ，ＲＡＧＨＡＶＥＮＤＲＡＣ．ＳＩＶＡＬＩＮＧＡＭＫＭ．Ｄａｔａｇａｔｈ—

ｅＩｉＩｌｇａｌｇｏｒｉｔｈｍｓｉｎ靶ｕｓｏｒｎｅｔｗｏｒｋｓｕｓｉｎｇｅｎｅｒｇｙｍｅｔｒｉｃｓ【Ｊ】．ＩＥＥＥ

皿ＴｒａｎｓａｃｔｉｏｎｓｏｎＰａｒａｌｌｅｌａｎｄＤｉｓｔｒｉｂｕｔｅｄＳｙｓｔｅｍｓ，２００２，１３（９）：９２４

黎—９３５．

蜒

社［４ＪＭＡＮＪＥＳＨＷＡＲＡ，ＡＧＡＲＷＡＬＤＰ．ＡＰＴＥＥＮ：Ａｈｙｂｒｉｄｐｒｏｔｏｃｏｌ

《

拉ｆｏｒｅｆｆｉｃｉｅｎｔｍｕｔｉｎｇａｎｄｃｏｍｐｒｅｈｅｎｓｉｖｅｉｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌｉｎｗｉｒｅ—

ｌｅｓｓｓｅｎｓｏｒｎｅｔｗｏｒｋｓ【Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ１６ｔｈＩｎｔｅｒｎａｔｉｏｎａｌＰａｒ－

ａｌｈｌａｎｄＤｉｓｔｒｉｂｕｔｅｄＰｒｏｃｅｓｓｉｎｇＳｙｍｐｏｓｉｕｍ（ＩＰＤＰＳ２００２）．Ｗａｓｈ－

ｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥＣｏｍｐｕｔｅｒＳｏｃｉｅｔｙ，２００２：１９５—２０２．

仿真時(shí)｜日Ｊ／ｓ【５】ＺＨＡＮＧＨＡｌ?ＢＯ，ＣＨＥＮＤＩ，Ｌｏｗｅｓｔｅｎｅｒｇｙｐｒｏｔｅｃｔｉｖｅｃｌｕｓｔｅｒｉｎｇａｌ?

圖５ＬＥＡＣＨ和ＥＤＢＣＭ節(jié)點(diǎn)存活數(shù)比較

ｇｏｒｉｔｈｍｆｏｒｗｉｒｅｌｅｓｓ∞ｎ∞ｒｎｅｔｗｏｒｋｓ［Ｃ】／／ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅ陀ｎ∞

從圖５可以看出，ＥＤＢＣＭ中第一個(gè)節(jié)點(diǎn)死亡的時(shí)刻為ｏｎＳｅｎｓｉｎｇ。ＣｏｍｐｕｔｉｎｇａｎｄＡｕｔｏｍａｔｉｏｎ（ＩＣＳＣＡ２００６）．Ｃｈｏｎｇｑｉｎｇ：３７０ｓ，ＬＥＡＣＨ為３２０ｓ，比ＬＥＡＣＨ延后了１５．６％；第２０個(gè)節(jié)【Ｓ．ｎ．１，２００６：２８５６—２８５９．

點(diǎn)的死亡時(shí)刻為４６０ｓ，ＬＥＡＣＨ為３７５８，延后了２２．７％。與【６】ＨＥＩＮＺＥＬＭＡＮＷ，ＣＨＡＮＤＲＡＫＡＮＳＡＮＡ，ＢＡＬＡＫＲＩＳＨＮＡＮＨ．ＬＥＡＣＨ相比，ＥＤＢＣＭ中節(jié)點(diǎn)死亡的時(shí)刻明顯延后。讓剩余Ｅｎｅｒｇｙ—ｅｆｆｉｃｉｅｎｔｃｏｍｍｕｎｉｃａｔｉｏｎｐｒｏｔｏｃｏｌｆｏｒｗｉｒｅｌｅｓｓｍｉｒｅｒｎｓｅｎｓｏｒ能量較多、距離基站較近的節(jié)點(diǎn)擔(dān)當(dāng)簇首，有效地保護(hù)了能量ｎｅｔｗｏｒｋｓ［Ｃ１／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ３３ｒｄＨａｗａｉｉＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒ－較低的節(jié)點(diǎn)，使節(jié)點(diǎn)間的剩余能量差別不大。另外，多跳的數(shù)ｅｎｃｅｏｎＳｙｓｔｅｍＳｃｉｅｎｃｅｓ（ＨＩＣＳＳ＇００）．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥＣｏｒｎ－據(jù)轉(zhuǎn)發(fā)路由，減少了通信能耗，同樣也延緩了節(jié)點(diǎn)的死亡時(shí)ｐｕｔｅｒＳｏｃｉｅｔｙ，２０００：３００５—３０１４．

【７】ＺＨＡＮＧＷＥＮ—ＹＡ，ＨＡＮＧＺＩ—ＺＥ．Ａｐｏｗｅｒｅｆｆｉｃｉｅｎｔｒｏｕｔｉｎｇｐｒｏｔｏ－

間，有效提高了傳感器網(wǎng)絡(luò)的工作壽命。ｃｏｌｆｏｒｗｉｒｅｌｅｓｓ∞ｌｌｓｏｒｎｅｔｗｏｒｋ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００７ＩＥＥＥ４結(jié)語(yǔ)ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅＯｉｌＮｅｔｗｏｒｋｉｎｇ，ｓｅ鵬ｉｎｇａｎｄＣｏｎｔｒｏｌ

（ＩＣＮＳＣ＇０７）．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥＣｏｍｐｕｔｅｒＳｏｃｉｅｔｙ，２００７：２０

本文提出一種基于能量和距離分簇的多跳路由協(xié)議。簇—２５．

（．ｖ＿ｇｇ１１１６頁(yè)）

顯。另外，為了進(jìn)一步提高爬蟲在本地的運(yùn)行效率，還需要找研究正在不斷深入，許多針對(duì)爬蟲爬行效率提升的改進(jìn)方案出并發(fā)工作線程數(shù)量在某個(gè)確定運(yùn)行環(huán)境下最優(yōu)的閾值。也不斷被提出并被廣泛采用。

表２爬蟲的測(cè)試數(shù)據(jù)比較參考文獻(xiàn)：

【１１苗長(zhǎng)芬，馮偉華．面向主題Ｃｒａｗｌｅｒ的設(shè)計(jì)與實(shí)現(xiàn)【Ｊ】．平原大學(xué)

學(xué)報(bào)，２００５，２２（３）：１１０—１１２．

㈦黃河燕．基于增量反饋和自適應(yīng)機(jī)制的主題爬蟲系統(tǒng)的設(shè)計(jì)與

實(shí)現(xiàn)【ＤＪ．南京：南京理工大學(xué)．２００５．

㈣劉金紅，陸余良．主題網(wǎng)絡(luò)爬蟲研究綜述【Ｊ】．計(jì)算機(jī)應(yīng)用研究，

２００７，２４（１０）：２６—２９．

吲陳杰．主題搜索引擎中網(wǎng)絡(luò)蜘蛛搜索策略研究（Ｄ】．杭州：浙江

大學(xué)，２００６．

㈣ＢＥＨＲＯＵＺＡＦ．ＴＣＰ／ＩＰＰｒｏｔｏｃｏｌＳｕｉｔｅ【Ｍ】．２ｎｄｅｄ．謝希仁，譯．

北京：清華大學(xué)出版社，２００３．

４結(jié)語(yǔ)嘲李曉明，目宏飛，王繼明．搜索引擎一原理、技術(shù)與系統(tǒng)【Ｍ】．北

京：科學(xué)出版社，２００４．

網(wǎng)絡(luò)爬蟲的策略選擇不當(dāng)以及自身結(jié)構(gòu)設(shè)計(jì)不良，都會(huì)Ⅲ朱玉麗．基于網(wǎng)格技術(shù)的主題爬蟲算法優(yōu)化的研究與實(shí)現(xiàn)【Ｄ１．給爬蟲工作效率造成不良影響。通過(guò)改進(jìn)模塊本身設(shè)計(jì)及協(xié)沈陽(yáng)：沈陽(yáng)工業(yè)大學(xué)，２００７．

調(diào)各個(gè)模塊的工作等方法，可以消除部分爬蟲系統(tǒng)工作效率吲何世林．基于Ｊａｖａ技術(shù)的搜索引擎研究與實(shí)現(xiàn)【ＤＩ．成都：西南的瓶頸，提高爬蟲系統(tǒng)的爬行效率。目前對(duì)網(wǎng)絡(luò)爬蟲系統(tǒng)的交通大學(xué)。２００６．

萬(wàn)　方數(shù)據(jù)

網(wǎng)絡(luò)爬蟲效率瓶頸的分析與解決方案

作者：

作者單位：

刊名：

英文刊名：

年，卷(期)：尹江， 尹治本， 黃洪， YIN Jiang， YIN Zhi-ben， HUANG Hong西南交通大學(xué),信息科學(xué)與技術(shù)學(xué)院,成都,610031計(jì)算機(jī)應(yīng)用JOURNAL OF COMPUTER APPLICATIONS2008,28(5)

參考文獻(xiàn)(8條)

1. 李曉明;閆宏飛;王繼明 搜索引擎-原理、技術(shù)與系統(tǒng) 2004

2. BEHROUZ A F;謝希仁 TCP/IP Protocol Suite 2003

3. 陳杰 主題搜索引擎中網(wǎng)絡(luò)蜘蛛搜索策略研究[學(xué)位論文] 2006

4. 何世林 基于Java技術(shù)的搜索引擎研究與實(shí)現(xiàn)[學(xué)位論文] 2006

5. 朱玉麗 基于網(wǎng)格技術(shù)的主題爬蟲算法優(yōu)化的研究與實(shí)現(xiàn) 2007

6. 劉金紅;陸余良 主題網(wǎng)絡(luò)爬蟲研究綜述[期刊論文]-計(jì)算機(jī)應(yīng)用研究 2007(10)

7. 黃河燕 基于增量反饋和自適應(yīng)機(jī)制的主題爬蟲系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[學(xué)位論文] 2005

8. 苗長(zhǎng)芬;馮偉華 面向主題Crawler的設(shè)計(jì)與實(shí)現(xiàn)[期刊論文]-平原大學(xué)學(xué)報(bào) 2005(03)

本文鏈接：http://d.g.wanfangdata.com.cn/Periodical_jsjyy200805007.aspx