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

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

文章編號：１００１—９０８１（２００８）０５—１１１４—０３

計算機應用

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

Ｖ０１．２８Ｎｏ．５

Ｍａｙ２００８

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

尹江，尹治本，黃洪

（西南交通大學信息科學與技術學院，成都６１００３１）

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

‘

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

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

文獻標志碼：Ａ

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

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

Ｗｅｂ

ｃｒａｗｌｅｒ

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

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

Ｈｏｗ

ｔｏ

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

ｔｏ

ａ

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

ａ

ａ

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

ｉｔｓｕｓｅｒｓ．ｔｏ

ｄｅｓｉｇｎ

ａ

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

ａ

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

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

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

ｓｔｒｕｃｔｕｒｅ

ｓｔｒａｔｅｇｙｔｏ

ｎｅｅｄｓ．ｔｏ

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

ｔｏ

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

ａ

ａｌｓｏｎｅｅｄｓ

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

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

ｕｓｅｒ

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

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

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

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

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

快但針對性較差，不能提高搜索的查準率。１．２基于價值回報的爬行策略

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

網(wǎng)絡爬蟲簡介

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

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

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

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

。

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

２．１效率瓶頸分析

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

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

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

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

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

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

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

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

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

萬方數(shù)據(jù)　

第５期

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

１１１５

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

２．２

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

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

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

２．２．１

ＤＮＳ解析

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

Ｉｄｘ

＿＿一指引數(shù)組

＿＿一２３權值

＿＿一Ｐ１＼

域名池

＿＿一

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

?！褚?/p>

Ｃ

●●●

＿＿——

域名計數(shù)

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

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

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

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

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

萬　

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

ｆ

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

哥

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

ｌ

２

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

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

?

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

———１Ｐ—一

Ⅳ

（１）

、１

７

ｌ

其中ＥＸ。＝Ｐ

Ｘ

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

骨

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

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

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

２．２．２頁面采集

１１１６

計算機應用第２８卷

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

?

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

（２）

其中引入文檔結(jié)束標志檢測機制時，概率等于０，否則等于１。通過優(yōu)化設計，由于事件通知機制會使得砭ｉ逼近Ｌ。，使得方程右邊第一項遠小于普通設計方式下的結(jié)果，大大縮短單次頁面采集周期。

（ａ）普通設計

（ｂ）改進設計

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

圖４改進機制的效率提升示意

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

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

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

ｎ

瓦＝ａ

Ｉ－－１≯‘

Ｅ（Ｂｍ；ｔ。）

（３）

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

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

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

明顯。

萬　

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

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

Ｓｔｕｄｉｏ

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

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

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

存）；７２００

Ｒｐｍ８０

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

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

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

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

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

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

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

（ａ）緩存帶來的效率差異

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

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

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

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

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

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

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

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

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

Ｓ

娶參考文獻：

幫

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

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

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

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

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

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

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

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

黎—９３５．

蜒

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

《

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

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

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

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

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

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

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

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

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

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

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

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

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

（．ｖ＿ｇｇ１１１６頁）

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

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

【１１苗長芬，馮偉華．面向主題Ｃｒａｗｌｅｒ的設計與實現(xiàn)【Ｊ】．平原大學

學報，２００５，２２（３）：１１０—１１２．

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

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

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

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

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

大學，２００６．

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

北京：清華大學出版社，２００３．

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

京：科學出版社，２００４．

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

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

萬　方數(shù)據(jù)

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

作者：

作者單位：

刊名：

英文刊名：

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

參考文獻(8條)

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

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

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

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

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

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

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

8. 苗長芬;馮偉華 面向主題Crawler的設計與實現(xiàn)[期刊論文]-平原大學學報 2005(03)

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