基于众包协作的分布式爬虫研究

发布时间：2018-09-07 20:38

【摘要】：在互联网技术迅速发展和人类社交需求日益增长的时代,分布式爬虫已被成熟的应用到各大搜索引擎和检索领域。本文提出众包协作模式的爬虫架构也是分布式系统,但任务分配方式采用“能者多劳”思想,可用资源越多的爬虫节点,获得更多任务,从而提高资源利用率、任务执行效率、节省执行时间和费用开销等。因此,研究基于众包协作模式的最优化任务分配方法有重要的学术意义和应用前景。本文将众包模式下的爬行任务分配问题分为静态爬行任务分配和动态爬行任务分配两大部分。静态爬行任务分配问题是指整个系统尚未执行任务,即任务序列没有被执行,爬虫节点也没有被分配任务;动态爬行任务分配问题是指整个系统在运行过程中,受外界环境和内部资源条件限制,各个任务和爬虫节点的状态动态变化。那么,在整体开销尽可能小时,如何考虑众包模式下爬虫任务的静态和动态分配问题,从而提高爬虫系统执行效率和资源利用率等,成为本文的主要研究内容。针对静态爬行任务分配问题,本文提出一种基于众包协作的静态爬行任务分配算法。该算法建立了多维度计算机资源模型,将爬虫节点自身资源进行有效量化,采用优先匹配启发式爬行任务分配算法进行任务分配,通过对费用目标函数的优化求解,使得整个静态爬行任务分配的费用最小。通过Matlab仿真验证,该算法能在满足系统需求的前提下,使得总费用最小。针对动态爬行任务分配问题,本文在静态爬行任务分配算法的基础上进行改进,提出基于时间模型的可信度定义,用来衡量每个爬虫节点的时效性,设计了融合可信度的多维度计算机资源模型,采用变异的优先匹配启发式爬行任务分配算法进行任务的动态分配,通过对具有多约束条件的费用目标函数进行优化求解,使得整个系统在动态变化的过程中,所用时间和费用都尽可能最小。通过Matlab仿真验证,与传统贪心算法相比,基于众包协作的静态爬行任务分配算法和动态爬行任务分配算法更符合使用规律,且总费用开销也更加合理,具有良好的可使用性。系统实验结果表明,众包协作模式的分布式爬行任务分配算法表现良好。
[Abstract]:With the rapid development of Internet technology and the increasing social needs of human beings, distributed crawlers have been applied to various search engines and retrieval fields. In this paper, the crawler architecture of crowdsourcing collaboration mode is also proposed as a distributed system. However, the idea of "the more skilled is employed" is adopted in the task allocation mode, and the more resources are available to the crawler nodes, the more tasks can be obtained, so as to improve the utilization of resources and the efficiency of task execution. Save execution time and expenses, etc. Therefore, it is of great academic significance and application prospect to study the optimal task allocation method based on crowdsourcing collaboration mode. In this paper, crawling task assignment in crowdsourcing mode is divided into static crawling task assignment and dynamic crawling task assignment. The static crawling task assignment problem refers to the whole system has not carried out the task, that is, the task sequence has not been executed, the crawler node has not been assigned the task, and the dynamic crawling task assignment problem refers to the whole system in the running process. Due to the external environment and internal resource constraints, the state of each task and crawler node changes dynamically. Therefore, how to consider the static and dynamic assignment of crawler tasks in crowdsourcing mode in order to improve the execution efficiency and resource utilization of crawler system becomes the main research content of this paper. A static crawling task assignment algorithm based on crowdsourcing collaboration is proposed for static crawling task assignment. The algorithm establishes a multi-dimensional computer resource model, quantifies the crawler node's own resources effectively, uses the priority matching heuristic crawling task assignment algorithm to allocate the task, and solves the cost objective function by optimization. The cost of the static crawling task is minimized. The results of Matlab simulation show that the algorithm can minimize the total cost on the premise of satisfying the system requirements. To solve the problem of dynamic crawling task assignment, this paper improves the static crawling task allocation algorithm, and proposes a time-model based credibility definition, which is used to measure the timeliness of each crawler node. A multi-dimensional computer resource model with fusion credibility is designed. The dynamic assignment of tasks is carried out by using the variant priority matching heuristic crawling task assignment algorithm. The cost objective function with multiple constraints is solved optimally. Make the whole system in the process of dynamic change, the minimum time and cost. Compared with the traditional greedy algorithm, the static crawling task assignment algorithm and the dynamic crawling task assignment algorithm based on crowdsourcing collaboration are verified by Matlab simulation. The experimental results show that the distributed crawling task allocation algorithm based on crowdsourcing collaboration mode performs well.
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP393.092

【相似文献】