网络爬虫效率瓶颈的分析与解决方案

第２８卷第５期２００８年５月・文章编号：１００１—９０８１（２００８）０５—１１１４—０３计算机应用ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓＶ０１．２８Ｎｏ．５Ｍａｙ２００８网络爬虫效率瓶颈的分析与解

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

文章编号：１００１—９０８１（２００８）０５—１１１４—０３

计算机应用

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

Ｖ０１．２８Ｎｏ．５

Ｍａｙ２００８

网络爬虫效率瓶颈的分析与解决方案

尹江，尹治本，黄洪

（西南交通大学信息科学与技术学院，成都６１００３１）

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

‘

摘要：网络爬虫的效率，直接关系到搜索引擎系统为用户提的供服务质量。如何设计高效、快速的网络爬虫，成为目前网络爬虫研究的热点。要提高网络爬虫的爬行效率，除了需要改进网络爬虫的爬行策略之外，还需要优化网络爬自身的设计，改进网络爬虫自身的结构，消除效率瓶颈。通过对网络爬虫结构、应用环境以及用户要求的分析，提出一个通用网络爬虫的改进设计方案，并通过实验得到较好的测试结果。

关键词：爬行策略；套接字；多线程；网络爬虫中图分类号：ＴＰ３１１

文献标志码：Ａ

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

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

Ｗｅｂ

ｃｒａｗｌｅｒ

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

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

Ｈｏｗ

ｔｏ

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

ｔｏ

ａ

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

ａ

ａ

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

ｉｔｓｕｓｅｒｓ．ｔｏ

ｄｅｓｉｇｎ

ａ

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

ａ

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

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

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

ｓｔｒｕｃｔｕｒｅ

ｓｔｒａｔｅｇｙｔｏ

ｎｅｅｄｓ．ｔｏ

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

ｔｏ

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

ａ

ａｌｓｏｎｅｅｄｓ

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

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

ｕｓｅｒ

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

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

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

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

网络爬虫是搜索引擎的重要组成部分。目前爬虫系统的基本设计原则为：在遵循ＲＥＰ原则以及对服务器不造成致命冲击的前提下‘¨，尽可能使爬虫爬行速度快、数据下载量大及信息抓取准确。必须要消除制约爬虫自身爬行效率的瓶颈，使爬虫达到高效。１

快但针对性较差，不能提高搜索的查准率。１．２基于价值回报的爬行策略

网络爬虫理想的设计是高速、完整地遍历整个Ｉｎｔｅｍｅｔ。往往需要对单纯的图算法爬行策略进行改进，合理地对资源（网站、页面及ＵＲＬ）进行价值评价，优先处理值高的资源，滞后处理甚至忽略价值低的资源。目前实际应用的策略主要有：基于链接自身质量评价的ＰａｇｅＲａｎｋ算法以及ＨＩＴＳ算法、基于ＵＲＬ主题相关性评价的ＢｅｓｔＳｅａｒｃｈ算法及Ｆｉｓｈ算法等忙１。除此以外机器学习理论、人工神经网络算法、蚂蚁算法等方法也在不断地应用到网络爬虫寻路优化策略中＂１。

网络爬虫简介

通用网络爬虫爬行的基本策略是将Ｉｎｔｅｒｎｅｔ视为一幅复

杂的有向图。利用这样的模型，网络爬虫可以采用图的广度优先搜索算法或图的深度优先搜索算法爬行Ｉｎｔｅｒａｃｔ并下载数据。

１．１广度优先、深度优先爬行策略

一个网页即为一个节点，网页中指向其他页面的ＵＲＬ为该节点到其他节点的路径，整个Ｉｎｔｅｒｎｅｔ由大量这样的节点构成一幅庞大的有向图Ｇ（Ｅ，ｙ），如图１所示。

。

２爬虫的瓶颈分析与解决方案

２．１效率瓶颈分析

爬虫的效率主要受到以下因素的制约：网络延时和爬虫本地运行效率，如图２所示。

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

图２网络爬虫的效率瓶颈示意

其中矩形代表页面，箭头线为ＵＲＬ，该图显示了网页间相互链接的关系。无论是广度优先还是深度优先策略，其时间渐近复杂度都为０（ｅ＋。），其中”，ｅ分别为图的节点与边的数量，即与Ｉｎｔｅｒｎｅｔ中的网页规模直接相关。上述爬行策略对各个网站、页面和ＵＲＬ的价值回报并不评估筛选，爬行速度

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

网络爬虫最主要的效率瓶颈在于网络带宽利用率低、适应性差；功能模块设计不良；各个功能模块协同工作效率低下等。

目前绝大多数爬虫系统都采用并发工作流的设计，以充分利用网络带宽。由于基于进程的并发代价较基于线程的并

作者简介：尹江（１９８１一）。男，四川成都人，硕士研究生，主要研究方向：计算机算法理论、软件工程；尹治本（１９５４一）．男，云南腾冲人。教

授，主要研究方向：计算机算法设计、软件工程；黄洪（１９５９一）。男，四川达州人，副教授，主要研究方向：数据库、办公自动化。

万方数据　

第５期

尹江等：网络爬虫效率瓶颈的分析与解决方案

１１１５

发而言相对较高，故大部分网络爬虫都是多线程架构设计＂’。然而这并不能完全疏通爬虫的效率瓶颈。

２．２

网络资源利用率的提升策略

基于Ｓｏｃｋｅｔ（以下统称套接字）的网络爬虫使用套接字，

通过发送ＨＥＡＤ、ＧＥＴ、ＰＯＳＴ等Ｈ１．ｒＰ方法，爬虫能在ＨｒｌｌＰ协议上通过指定的端口与服务器进行数据信息交换＂Ｊ。爬行过程中爬虫需要两次使用网络资源：域名解析与页面采集，致使网络延时占据绝大部分爬虫运行时间，形成爬虫运行效率的瓶颈ｊ在实际测试中，对１００个主机名通过查询ＤＮＳ服务器得到ＩＰ地址，平局时间为３２７毫秒／个。其中有少数域名的查询返回时间甚至超过数秒。同时，某些数据量大的网页的传输等待时间也会超过数秒。

２．２．１

ＤＮＳ解析

引入并优化ＤＮＳ缓存模块。ＵＲＬ中重复的域名使用频繁，ＤＮＳ本地缓存能大量减少因重复的域名解析造成的网络占用及等待时间。为提高域名缓存模块的效率，本文设计了一个使用哈希表为表头、以线性指针序列作为索引并以域名长度为跳跃单位的数据结构保存域名，暂命名为“域名跳检哈希表”，能够高效的写入域名、检索域名、为域名排序以及高效地按需求替换域名。其表结构的一个环节如图３所示。

Ｉｄｘ

＿＿一指引数组

＿＿一２３权值

＿＿一Ｐ１＼

域名池

＿＿一

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

。●一

Ｃ

●●●

＿＿——

域名计数

图３用于ＤＮＳ缓存的域名表结构

图３展示了域名表的构造与关键环节。改进后域名解析过程大致如下：使用域名首字符ＡＳＣＩＩ码值与域名长度散列域名到哈希表头。依照线性指针序列的下标索引，通过域名头指针依次检索已存在ＩＰ映射的域名，若该域名还未在表中则调用ＤＮＳ解析过程。解析成功便将域名写入域名表最后空位，ＩＰ则写入对应ＩＰ段内，并更新域名池信息（包括权信息、数量信息等）；失败则返回错误代码通知调用者。在写入时若发现域名池满则替换掉部分权值低的域名。若该域名已经过解析则使用对应ＩＰ，并对域名进行相应的加权（如使用频率、最近使用时间等）。为保证权值高的域名能够被快速地映射出ＩＰ，在若干次域名解析与写入过程后需要为域名排序。排序时以线性指针链索引遍历所有存在域名的权值，需要改变域名顺序时仅仅交换域名指针域与权值域。该结构兼有哈希表、链表与线性表的优点，下面是主要操作的算法时间效率分析：

插入域名：新域名ｈ到达时，计算其ＨＡＳＨ索引的时间为固定常数，计为Ｌ。由于域名池空位地址＝域名池基址十域名个数×域名长度，故寻址域名池空位时间为固定常数乃。另计域名的写入操作时间为乃＝Ｉ（ｚ），ｚ为域名长度。则可知一个新域名的插入时间复杂度为瓦＋疋＋瓦一Ｄ（ｃ）。

域名排序：为域名按权值排序时仅仅做指针交换操作，大大优于单纯的线性表结构。设某个域名池存放长度为ｎ的域名ｍ个，若单纯使用线性表结构操作则每次移动一个域名需要移动Ｉｔ个元素３次，若每个元素都需换位且仅需１次，则至少需要３ｎｍ次移动操作，而在本文所采用策略下ｍ—ｌ，即效率为普通线性结构的约ｍ倍。

域名映射：新域名ｈ到达时，根据其首字符编码以及ｈ的

万　

方数据长度ｆ计算ＨＡＳＨ索引，探测ｈ可能存在映射的域名池的时间计为固定常数正。现在分析ｈ在池中寻找匹配的平均时间疋。设域名池已有ｎ个域名，每个域名固定长度为２，ｈ中第ｉ个字符失配而前ｉ一１个字符匹配的概率为Ｐｉ，ｉ＝１，２…Ｚ，又设ｈ

ｆ

被某个域名完全匹配的概率为Ｐ，则有Ｐ＋乏：Ｐｌ，且第ｉ个字

哥

符匹配后已经比较过的字符数为厶。设Ｐ’；为ｈ与域名池中前ｉ—１个域名失配但与第ｉ个域名匹配的概率。现做Ｊ７＼『次域名映射操作，则可知：

ｌ

２

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

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

・

Ｎ×Ｐ’。×∑瓯（Ｌ）

———１Ｐ—一

Ⅳ

（１）

、１

７

ｌ

其中ＥＸ。＝Ｐ

Ｘ

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

骨

域名池中每个域名与ｈ失配所移动的字符数的数学期望。该结构的优势体现在当池中域名某个字符与ｈ中字符失配时，可以直接跳到下一个域名起始处比对，即每次映射操作比较字符数远小于厅×Ｚ，同时还可以加入模式匹配优化策略，域名越长，效果越好。

多线程、非阻塞套接字与ＷＳＡＥｖｅｎｔＳｅｌｅｃｔ（异步）模型的组合设计。核心思想是采用适应性更强的方法，最大限度利用网络资源埔Ｊ，同时缩短线程执行周期。在采集页面的过程中，爬虫需要长时间等待数据到达协议缓冲区。若采用多线程并发爬行的设计，应开启多个爬行线程并让等待中的线程阻塞，既能充分地利用闲置的网络资源，又尽可能地减少了同时占有ＣＰＵ的线程数量，缩短线程执行周期。虽然事件选择模型本身支持套接字组管理方式，但套接字组中的最大套节字数极为有限（６４个），且必须维护线程池使系统达到高效。此外，套接字组管理增加了套接字行为的管理难度。本文采用每个异步套接字绑定一个工作线程的创新设计，线程队列在爬虫开始爬行前创建，在爬行过程中不会被撤销，无需线程池且读写操作不分离，既提高了效率又方便管理。具体实施方案如下：１）将套接字设定为非阻塞方式，并绑定在一个ＷＳＡＥＶＥＮＴ对象上，通过探察这个对象的状态以获知发生了哪些需要处理的网络事件，如可读取、可发送、关闭连接等等。２）在没有相关的事件发生且不满足采集工作结束条件时，线程被阻塞一个超时。３）若在系统阻塞线程等待数据的过程中有数据到达，系统会唤醒线程继续读取所有到达数据，同时超时计数器复位。４）否则超时计数器加１，继续探察事件对象。同时每次阻塞前首先检查采集工作结束条件（如超时计数器为０、对方关闭连接等以及文件已结尾），判断是否中止数据读取操作，尽可能缩短线程执行周期。通过此种设计，一方面线程因等待数据阻塞时，ＣＰＵ得以尽可能多地执行有效运算；同时，通过事件机制，使得套接字工作能适应更加复杂的网络环境。

图４为爬行线程工作队列的时间片分布示意图，图中每组矩形表示一个爬行线程工作队列，其竖直方向的长度显示了一个页面采集过程的周期长度。矩形中的灰色部分为线程阻塞时间，白色部分为多个线程共享的ＣＰＵ时间，黑色部分为线程独占的ＣＰＵ时间，线程队列旁的箭头线长短表示线程

２．２．２页面采集

１１１６

计算机应用第２８卷

的执行时间。图４（ｃ）显示了一种理想状态（规定线程必有一次阻塞）：每个线程的ＣＰＵ时间独享，且阻塞的时间最短并只阻塞一次。从图４（ｂ）中可以看出，由于事件机制能及时唤醒阻塞中的线程，减少了线程的不必要的阻塞时间。设ｎｉ为某页面分次传输的真实耗时，并且发生ｍ次。又设疋；为人工设定超时上限，超时等待次数为ｎ次。基于下面的事实：（１）超时等待总时间必须大于或等于页面传输真实耗时才可能正确的下载页面；（２）每次数据到达前人工的超时等待必至少发生一次；（３）探查到数据未到达后的等待超时应至少等于页面传输时间¨１。则有对任意的ｉ，ｎ≥ｍ，Ｔ２ｉ≥ＴＩ；，可知浪费的等待时间为：

・

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

（２）

其中引入文档结束标志检测机制时，概率等于０，否则等于１。通过优化设计，由于事件通知机制会使得砭ｉ逼近Ｌ。，使得方程右边第一项远小于普通设计方式下的结果，大大缩短单次页面采集周期。

（ａ）普通设计

（ｂ）改进设计

（ｃ）理想状态

图４改进机制的效率提升示意

２．３爬虫本地运行效率的优化方案

ｒ除网络资源外，爬虫自身各部分的运行效率也可能成为爬虫工作效率的瓶颈。

多线程工作同步是爬虫系统正常工作的必要前提悼Ｊ，但大量工作线程同步意味着排队等待时间增加，在共享数据操作频繁的环境下，系统工作效率甚至会因线程数量的增加而下降，同时还会带来大量的系统开销来实现Ｉ临界区操作，造成效率瓶颈。本文采用ＵＲＬ队列独享，ＵＲＬ散列结构共享的结构设计。实际测试发现，ＵＲＬ队列是整个爬虫中访问最频繁的部分，应尽量避免同步问题。现有线程工作队列Ｐ．…Ｐｎ，若其中有一半的线程在做ｍ（所有线程的平均值）个ＵＲＬ入队列操作，并且其中有２０％的操作重叠，另设平均一次人队列操作时间为ｔ。假定ＣＰＵ线程调度均匀（此时线程入队列操作排队等待时间平均分摊到每个线程上），则得到同步等待时间，如式（３）：

ｎ

瓦＝ａ

Ｉ－－１≯‘

Ｅ（Ｂｍ；ｔ。）

（３）

其中口为试图访问临界区线程的比例，卢为人队列操作的平均重叠率，／７／，。、ｔ１分别由平均值ｍ、ｔ取代。按上述条件粗略地计算出线程Ｐ；在ＵＲＬ人队列的过程中，由于同步浪费的等待时

间为Ｅ＝ｎｍｔ／１０。由此可看出每个线程包含胄己的ＵＲＬ队

列是非常合理的。另一方面，ＵＲＬ散列结构必须共享，原因是ＵＲＬ消重效果不能牺牲，若作为线程独立的结构，需要大量额外的时间、空间上的开销来为每个线程同步ＵＲＬ消重散列结构的数据。其次，ＵＲＬ消重操作较为分散（本文设计的爬虫消重工作只在页面采集过程前端进行），操作时间短且各线程的重叠操作很少，对整个工作队列的运行效率影响不

明显。

万　

方数据３测试与小结

综合以上论述，笔者在Ｖｉｓｕａｌ

Ｓｔｕｄｉｏ

６．０环境下用ｃ＋＋

语言开发了一个工作在Ｗｉｎｄｏｗｓ系统上采用广度优先策略的通用爬虫，主要目的在于测试在选定爬行策略的前提下，爬虫自身设计的改进以及主要瓶颈的消除所带来的爬行效率提升。测试环境如下：ＩｎｔｅｌＰ４２．８

ＧＨｚ（ＣＰＵ）；ＤＤＲ４００１ＧＢ（内

存）；７２００

Ｒｐｍ８０

ＧＢ串口（硬盘）；ＷｉｎｄｏｗｓｘＰ（操作系统）；

校园网网通（网络）。该系统结构如图５所示。

图５ＳＰＩＤＥＲ爬虫系统结构

通过该系统对ＤＮＳ缓存模块的引入、网络交互模型选择、并发优化阈值以及ＵＲＬ队列构造策略等对爬虫效率的影响进行测试。

表ｌ三大门户网站首页下载测试数据（２００７年６月７日）

表１为对三大门户网站的首页的下载采用不同设计所得到的结果比较。可以看出，在Ｓｅｒｖｅｒ不与Ｃｌｉｅｎｔ保持长连接时，优化效果最为明显，采集周期缩短近７０％；而保持长连接的情况中，若引入文档结束检查机制，也有颇为明显的改善。

图６显示了ＤＮＳ缓存的引入及ＷＳＡ事件机制对爬虫效率的影响，其中横坐标表示爬虫的运行时间，以１５ｍｉｎ为单位间隔；纵坐标为爬虫的数据采集量，以千兆字节计。可以看到，引入ＤＮＳ缓存使爬虫效率提升了近两倍，而事件选择模型与套接字绑定工作线程的组合设计也大大提升爬虫的爬行效率，达到了设计目的。

（ａ）缓存带来的效率差异

Ｃｏ）网络１０模型选择带来的效率差异

图６测试数据比较

表２列出了不同结构的爬虫在本文所述测试环境下爬行可以看到ＵＲＬ队列共享对爬虫工作效率的负面影响也颇为明

（下转第１１１９页）

３０ｍｉｎ所测得的关键综合数据。从上面的数据中，还

第５期张磊等：一个新的基于能量和距离的传感器网络协议１１１９而不是如ＬＥＡＣＨ那样随机地轮循簇首。充分说明ＥＤＢＣＭ首选择时充分考虑了节点能量和到基站的距离，簇首质量较协议提高了网络的能量有效性，能提供更多数据来刻画传感高；数据发送采用了改进的多跳路由。仿真结果表明，与区域，更好地完成网络所担负的任务。ＬＥＡＣＨ协议相比，该算法提高了基站接收的数据量，明显延

长了网络的生存寿命。今后，可用ＭＡＴＬＡＢ／ＯＰＮＥＴ在大型

矗ｌ网络中做进一步的仿真测试。另外，数据转发过程中潜在的啦

瓤数据包丢失和时延问题，也是要研究的问题。

Ｓ

娶参考文献：

帮

磐【１】宋文，王兵．周应宾，等．无线传感器网络技术与应用【Ｍ】．北瑚京：电子工业出版社，２００７．

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

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

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

图４ＬＥＡＣＨ和ＥＤＢＣＭ基站数据量比较２００２，１（４）：６６０—６７０．

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

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

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

黎—９３５．

蜒

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

《

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

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

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

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

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

图５ＬＥＡＣＨ和ＥＤＢＣＭ节点存活数比较

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

从图５可以看出，ＥＤＢＣＭ中第一个节点死亡的时刻为ｏｎＳｅｎｓｉｎｇ。ＣｏｍｐｕｔｉｎｇａｎｄＡｕｔｏｍａｔｉｏｎ（ＩＣＳＣＡ２００６）．Ｃｈｏｎｇｑｉｎｇ：３７０ｓ，ＬＥＡＣＨ为３２０ｓ，比ＬＥＡＣＨ延后了１５．６％；第２０个节【Ｓ．ｎ．１，２００６：２８５６—２８５９．

点的死亡时刻为４６０ｓ，ＬＥＡＣＨ为３７５８，延后了２２．７％。与【６】ＨＥＩＮＺＥＬＭＡＮＷ，ＣＨＡＮＤＲＡＫＡＮＳＡＮＡ，ＢＡＬＡＫＲＩＳＨＮＡＮＨ．ＬＥＡＣＨ相比，ＥＤＢＣＭ中节点死亡的时刻明显延后。让剩余Ｅｎｅｒｇｙ—ｅｆｆｉｃｉｅｎｔｃｏｍｍｕｎｉｃａｔｉｏｎｐｒｏｔｏｃｏｌｆｏｒｗｉｒｅｌｅｓｓｍｉｒｅｒｎｓｅｎｓｏｒ能量较多、距离基站较近的节点担当簇首，有效地保护了能量ｎｅｔｗｏｒｋｓ［Ｃ１／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ３３ｒｄＨａｗａｉｉＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒ－较低的节点，使节点间的剩余能量差别不大。另外，多跳的数ｅｎｃｅｏｎＳｙｓｔｅｍＳｃｉｅｎｃｅｓ（ＨＩＣＳＳ＇００）．Ｗａｓｈｉｎｇｔｏｎ，ＤＣ：ＩＥＥＥＣｏｒｎ－据转发路由，减少了通信能耗，同样也延缓了节点的死亡时ｐｕｔｅｒＳｏｃｉｅｔｙ，２０００：３００５—３０１４．

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

间，有效提高了传感器网络的工作寿命。ｃｏｌｆｏｒｗｉｒｅｌｅｓｓ∞ｌｌｓｏｒｎｅｔｗｏｒｋ［Ｃ】／／Ｐｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅ２００７ＩＥＥＥ４结语ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅＯｉｌＮｅｔｗｏｒｋｉｎｇ，ｓｅ鹏ｉｎｇａｎｄＣｏｎｔｒｏｌ

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

本文提出一种基于能量和距离分簇的多跳路由协议。簇—２５．

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

显。另外，为了进一步提高爬虫在本地的运行效率，还需要找研究正在不断深入，许多针对爬虫爬行效率提升的改进方案出并发工作线程数量在某个确定运行环境下最优的阈值。也不断被提出并被广泛采用。

表２爬虫的测试数据比较参考文献：

【１１苗长芬，冯伟华．面向主题Ｃｒａｗｌｅｒ的设计与实现【Ｊ】．平原大学

学报，２００５，２２（３）：１１０—１１２．

㈦黄河燕．基于增量反馈和自适应机制的主题爬虫系统的设计与

实现【ＤＪ．南京：南京理工大学．２００５．

㈣刘金红，陆余良．主题网络爬虫研究综述【Ｊ】．计算机应用研究，

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

吲陈杰．主题搜索引擎中网络蜘蛛搜索策略研究（Ｄ】．杭州：浙江

大学，２００６．

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

北京：清华大学出版社，２００３．

４结语嘲李晓明，目宏飞，王继明．搜索引擎一原理、技术与系统【Ｍ】．北

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

网络爬虫的策略选择不当以及自身结构设计不良，都会Ⅲ朱玉丽．基于网格技术的主题爬虫算法优化的研究与实现【Ｄ１．给爬虫工作效率造成不良影响。通过改进模块本身设计及协沈阳：沈阳工业大学，２００７．

调各个模块的工作等方法，可以消除部分爬虫系统工作效率吲何世林．基于Ｊａｖａ技术的搜索引擎研究与实现【ＤＩ．成都：西南的瓶颈，提高爬虫系统的爬行效率。目前对网络爬虫系统的交通大学。２００６．

万　方数据

网络爬虫效率瓶颈的分析与解决方案

作者：

作者单位：

刊名：

英文刊名：

年，卷(期)：尹江， 尹治本， 黄洪， YIN Jiang， YIN Zhi-ben， HUANG Hong西南交通大学,信息科学与技术学院,成都,610031计算机应用JOURNAL OF COMPUTER APPLICATIONS2008,28(5)

参考文献(8条)

1. 李晓明;闫宏飞;王继明 搜索引擎-原理、技术与系统 2004

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

3. 陈杰 主题搜索引擎中网络蜘蛛搜索策略研究[学位论文] 2006

4. 何世林 基于Java技术的搜索引擎研究与实现[学位论文] 2006

5. 朱玉丽 基于网格技术的主题爬虫算法优化的研究与实现 2007

6. 刘金红;陆余良 主题网络爬虫研究综述[期刊论文]-计算机应用研究 2007(10)

7. 黄河燕 基于增量反馈和自适应机制的主题爬虫系统的设计与实现[学位论文] 2005

8. 苗长芬;冯伟华 面向主题Crawler的设计与实现[期刊论文]-平原大学学报 2005(03)

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