【摘要】：在互聯(lián)網(wǎng)技術(shù)迅速發(fā)展和人類社交需求日益增長的時代,分布式爬蟲已被成熟的應(yīng)用到各大搜索引擎和檢索領(lǐng)域。本文提出眾包協(xié)作模式的爬蟲架構(gòu)也是分布式系統(tǒng),但任務(wù)分配方式采用“能者多勞”思想,可用資源越多的爬蟲節(jié)點(diǎn),獲得更多任務(wù),從而提高資源利用率、任務(wù)執(zhí)行效率、節(jié)省執(zhí)行時間和費(fèi)用開銷等。因此,研究基于眾包協(xié)作模式的最優(yōu)化任務(wù)分配方法有重要的學(xué)術(shù)意義和應(yīng)用前景。本文將眾包模式下的爬行任務(wù)分配問題分為靜態(tài)爬行任務(wù)分配和動態(tài)爬行任務(wù)分配兩大部分。靜態(tài)爬行任務(wù)分配問題是指整個系統(tǒng)尚未執(zhí)行任務(wù),即任務(wù)序列沒有被執(zhí)行,爬蟲節(jié)點(diǎn)也沒有被分配任務(wù);動態(tài)爬行任務(wù)分配問題是指整個系統(tǒng)在運(yùn)行過程中,受外界環(huán)境和內(nèi)部資源條件限制,各個任務(wù)和爬蟲節(jié)點(diǎn)的狀態(tài)動態(tài)變化。那么,在整體開銷盡可能小時,如何考慮眾包模式下爬蟲任務(wù)的靜態(tài)和動態(tài)分配問題,從而提高爬蟲系統(tǒng)執(zhí)行效率和資源利用率等,成為本文的主要研究內(nèi)容。針對靜態(tài)爬行任務(wù)分配問題,本文提出一種基于眾包協(xié)作的靜態(tài)爬行任務(wù)分配算法。該算法建立了多維度計(jì)算機(jī)資源模型,將爬蟲節(jié)點(diǎn)自身資源進(jìn)行有效量化,采用優(yōu)先匹配啟發(fā)式爬行任務(wù)分配算法進(jìn)行任務(wù)分配,通過對費(fèi)用目標(biāo)函數(shù)的優(yōu)化求解,使得整個靜態(tài)爬行任務(wù)分配的費(fèi)用最小。通過Matlab仿真驗(yàn)證,該算法能在滿足系統(tǒng)需求的前提下,使得總費(fèi)用最小。針對動態(tài)爬行任務(wù)分配問題,本文在靜態(tài)爬行任務(wù)分配算法的基礎(chǔ)上進(jìn)行改進(jìn),提出基于時間模型的可信度定義,用來衡量每個爬蟲節(jié)點(diǎn)的時效性,設(shè)計(jì)了融合可信度的多維度計(jì)算機(jī)資源模型,采用變異的優(yōu)先匹配啟發(fā)式爬行任務(wù)分配算法進(jìn)行任務(wù)的動態(tài)分配,通過對具有多約束條件的費(fèi)用目標(biāo)函數(shù)進(jìn)行優(yōu)化求解,使得整個系統(tǒng)在動態(tài)變化的過程中,所用時間和費(fèi)用都盡可能最小。通過Matlab仿真驗(yàn)證,與傳統(tǒng)貪心算法相比,基于眾包協(xié)作的靜態(tài)爬行任務(wù)分配算法和動態(tài)爬行任務(wù)分配算法更符合使用規(guī)律,且總費(fèi)用開銷也更加合理,具有良好的可使用性。系統(tǒng)實(shí)驗(yàn)結(jié)果表明,眾包協(xié)作模式的分布式爬行任務(wù)分配算法表現(xiàn)良好。
[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.
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP393.092

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 聶明泓;楊麗英;聶義勇;;任務(wù)分配問題的建模與求解[J];小型微型計(jì)算機(jī)系統(tǒng);2009年04期

2 張雷;王崇駿;謝俊元;;分布式任務(wù)分配中的一種信譽(yù)重連策略[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2009年05期

3 高志軍,韋紅雨,顏國正,丁國清;網(wǎng)絡(luò)環(huán)境下多機(jī)器人的任務(wù)分配實(shí)現(xiàn)[J];計(jì)算機(jī)工程與應(yīng)用;2004年03期

4 李濟(jì)澤;李科杰;宋萍;;基于非合作博弈模型的多移動節(jié)點(diǎn)任務(wù)分配[J];福建工程學(xué)院學(xué)報(bào);2010年04期

5 孟海戰(zhàn);;一種優(yōu)化的任務(wù)分配方法研究[J];計(jì)算機(jī)與現(xiàn)代化;2011年04期

6 陶雪麗;鄭延斌;;多Agent層次任務(wù)分配方法[J];計(jì)算機(jī)工程與設(shè)計(jì);2013年05期

7 陶雪麗;鄭延斌;;基于適應(yīng)度的多Agent層次任務(wù)分配方法[J];微電子學(xué)與計(jì)算機(jī);2013年06期

8 黎亮,楊國緯;一種具有自適應(yīng)能力的任務(wù)分配系統(tǒng)的設(shè)計(jì)[J];電子科技大學(xué)學(xué)報(bào);1998年06期

9 陳夏冰;劉國棟;劉麗娟;;基于分區(qū)的多機(jī)器人任務(wù)分配[J];江南大學(xué)學(xué)報(bào)(自然科學(xué)版);2013年04期

10 袁偉;;基于拋棄 撿拾法的多機(jī)器人動態(tài)任務(wù)分配[J];福建電腦;2010年01期

相關(guān)會議論文 前10條

1 趙保學(xué);李戰(zhàn)懷;陳群;姜濤;潘巍;金健;;可擴(kuò)展Hadoop任務(wù)分配模塊的研究與實(shí)現(xiàn)[A];第29屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（B輯）（NDBC2012）[C];2012年

2 馮利偉;;EPON接入的DBA算法研究[A];經(jīng)濟(jì)發(fā)展方式轉(zhuǎn)變與自主創(chuàng)新——第十二屆中國科學(xué)技術(shù)協(xié)會年會（第四卷）[C];2010年

3 陳超;蔣建春;丁治明;;基于時序片段評價的數(shù)據(jù)分配算法[A];NDBC2010第27屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集(B輯)[C];2010年

4 周一青;王江舟;吳冬生;;OFCDM系統(tǒng)中的碼分配算法的研究與應(yīng)用[A];2007年中國通信學(xué)會“移動增值業(yè)務(wù)與應(yīng)用”學(xué)術(shù)年會論文集[C];2007年

5 郭淑明;唐曉梅;鄔江興;;一種OVSF碼的改進(jìn)型快速分配算法[A];通信理論與信號處理新進(jìn)展——2005年通信理論與信號處理年會論文集[C];2005年

6 何興;范紅;徐偉亮;季尹禹;;EPON上行接入帶寬分配算法的研究[A];全國第十一次光纖通信暨第十二屆集成光學(xué)學(xué)術(shù)會議（OFCIO’2003）論文集[C];2003年

7 石媛媛;周羅偉;王江柳;楊佩;陳春林;;適用于智能倉儲多機(jī)器人任務(wù)分配的一種平衡啟發(fā)式拍賣方法[A];系統(tǒng)仿真技術(shù)及其應(yīng)用學(xué)術(shù)論文集（第15卷）[C];2014年

8 魏安貴;許宗澤;;一種基于線性規(guī)劃無線網(wǎng)絡(luò)最大最小公平性帶寬分配算法[A];2008通信理論與技術(shù)新發(fā)展——第十三屆全國青年通信學(xué)術(shù)會議論文集（下）[C];2008年

9 鐘耕深;朱雅杰;;基于眾包的商業(yè)模式優(yōu)化[A];第五屆（2010）中國管理學(xué)年會——組織與戰(zhàn)略分會場論文集[C];2010年

10 陳欽山;;VTS分布式系統(tǒng)的動態(tài)負(fù)載分配算法[A];中國航海學(xué)會通信導(dǎo)航專業(yè)委員會2006年學(xué)術(shù)年會論文集[C];2006年

相關(guān)重要報(bào)紙文章 前10條

1 (美)杰夫·豪《連線》雜志著名資深編輯;眾包——化整為零的革命[N];中國聯(lián)合商報(bào);2009年

2 君尚;中介和渠道全面讓位眾包服務(wù)平臺[N];科技日報(bào);2014年

3 凌曼文;眾包：人人都來賣點(diǎn)子[N];中國計(jì)算機(jī)報(bào);2006年

4 夏劍;眾包革命：群眾創(chuàng)新[N];中國企業(yè)報(bào);2008年

5 本報(bào)記者 肖志飛;“眾包”的魅力[N];醫(yī)藥經(jīng)濟(jì)報(bào);2010年

6 張涵;建立有層級架構(gòu)的“眾包”模式[N];人民日報(bào);2012年

7 羽哲;“春晚”可以嘗試“眾包”[N];科技日報(bào);2013年

8 本報(bào)記者 王繼征;眾包模式能給纖維品牌帶來什么？[N];中國紡織報(bào);2014年

9 張鳳岐;眾包的價值[N];電腦商報(bào);2009年

10 本報(bào)記者 張潔云;“眾包”,多元化的解困路徑？[N];醫(yī)藥經(jīng)濟(jì)報(bào);2010年

相關(guān)博士學(xué)位論文 前10條

1 馬巧云;基于多Agent系統(tǒng)的動態(tài)任務(wù)分配研究[D];華中科技大學(xué);2006年

2 李勇;多Agent系統(tǒng)聯(lián)盟及任務(wù)分配的研究[D];合肥工業(yè)大學(xué);2008年

3 劉美;WSN多目標(biāo)跟蹤節(jié)點(diǎn)任務(wù)分配及跟蹤算法研究[D];華南理工大學(xué);2010年

4 梁曉雯;OFDM系統(tǒng)中自適應(yīng)分配算法及其計(jì)算量的研究[D];中國科學(xué)技術(shù)大學(xué);2006年

5 林素芬;基于眾包參與者網(wǎng)絡(luò)的眾包績效提升研究[D];華僑大學(xué);2015年

6 龐建剛;眾包社區(qū)創(chuàng)新的運(yùn)營機(jī)制設(shè)計(jì)[D];中國科學(xué)技術(shù)大學(xué);2014年

7 岳德君;眾包質(zhì)量評估與優(yōu)化策略的研究[D];東北大學(xué);2015年

8 向?yàn)?創(chuàng)意設(shè)計(jì)柔性眾包的方法與應(yīng)用[D];浙江大學(xué);2017年

9 臧潔;分布式制造企業(yè)中協(xié)同生產(chǎn)任務(wù)分配的若干優(yōu)化問題研究[D];東北大學(xué);2011年

10 彭玲;眾包平臺用戶接受與知識轉(zhuǎn)移研究[D];華中科技大學(xué);2012年

相關(guān)碩士學(xué)位論文 前10條

1 張寧;自治移動云中任務(wù)分配的設(shè)計(jì)與實(shí)現(xiàn)[D];內(nèi)蒙古大學(xué);2015年

2 張馳;無人機(jī)任務(wù)分配仿真平臺設(shè)計(jì)與研究[D];西安電子科技大學(xué);2014年

3 賈健;多平臺防空協(xié)同任務(wù)分配問題研究[D];北京理工大學(xué);2016年

4 程如洪;群智感知的任務(wù)分配和用戶調(diào)度算法[D];中國科學(xué)技術(shù)大學(xué);2016年

5 程靜;具有隨機(jī)屬性的多無人機(jī)任務(wù)分配問題研究[D];合肥工業(yè)大學(xué);2016年

6 李明;基于異構(gòu)MAS的AGV協(xié)作系統(tǒng)任務(wù)分配方法研究[D];武漢工程大學(xué);2016年

7 趙文衛(wèi);分布式爬蟲系統(tǒng)中任務(wù)分配問題的研究[D];南京大學(xué);2015年

8 陳永春;移動云計(jì)算的系統(tǒng)管理與優(yōu)化方法研究[D];吉林大學(xué);2017年

9 魯昊;Multi-agent系統(tǒng)中動態(tài)任務(wù)分配研究[D];湖北大學(xué);2012年

10 姚慧峰;移動云計(jì)算環(huán)境下任務(wù)分配問題的研究[D];南京郵電大學(xué);2014年

，

本文編號：2229354