基于工人信譽(yù)度和距離的任務(wù)分配算法

王從文

摘要：時(shí)空眾包任務(wù)分配問(wèn)題大多涉及到工人和任務(wù)的位置信息，針對(duì)工人的信譽(yù)度的研究較少。本文首先對(duì)工人信譽(yù)度進(jìn)行定義，針對(duì)現(xiàn)有相關(guān)研究存在的問(wèn)題，提出基于信譽(yù)度的任務(wù)分配算法，目標(biāo)為最大化任務(wù)完成質(zhì)量。實(shí)驗(yàn)中將本文提出的算法與隨機(jī)算法進(jìn)行對(duì)比，結(jié)果表明本文提出的算法性能優(yōu)于隨機(jī)算法。

關(guān)鍵詞：時(shí)空眾包;任務(wù)分配;信譽(yù)度

Abstract： The problem of space-time crowdsourcing task assignment mostly involves the location information of workers and tasks， and there is little research on the credibility of workers. This paper firstly defines the credibility of the workers， and proposes a task assignment algorithm based on credibility in view of the existing research problems. The goal is to maximize the quality of task completion. In the experiment， the algorithm proposed in this paper is compared with the random algorithm. The results show that the performance of the algorithm proposed in this paper is superior to the random algorithm.

Key words： space-time crowdsourcing;task allocation;credibility

1? 研究背景

眾包會(huì)產(chǎn)生大量的數(shù)據(jù)，目標(biāo)是利用移動(dòng)設(shè)備來(lái)收集和共享數(shù)據(jù)，可以給移動(dòng)用戶(hù)分配特定的任務(wù)。數(shù)據(jù)經(jīng)由各種通訊設(shè)備獲取，自行車(chē)上的傳感器也可以收集數(shù)據(jù)，如圖1和圖2所示。

在眾包市場(chǎng)中需求者可在眾包網(wǎng)站上發(fā)布短期任務(wù)，工人通過(guò)完成此類(lèi)任務(wù)進(jìn)而獲得相應(yīng)的獎(jiǎng)勵(lì)。需求者利用眾包工人多樣性的特點(diǎn)，將任務(wù)分配給具備任務(wù)所需技能的工人。在技能未知的情況下，將任務(wù)隨機(jī)分配給可用的工人，通過(guò)重復(fù)的任務(wù)分配來(lái)提高任務(wù)完成的質(zhì)量，極大浪費(fèi)人力、物力和財(cái)力。

時(shí)空眾包領(lǐng)域中，工人大體可分為誠(chéng)實(shí)和不誠(chéng)實(shí)兩類(lèi)（按信譽(yù)度高低來(lái)確定）。不誠(chéng)實(shí)的工人通過(guò)快速給出看似合理的答案，最大化自身利益。然而一些算法并沒(méi)有考慮不誠(chéng)實(shí)的工人的問(wèn)題，這樣會(huì)導(dǎo)致低質(zhì)量的任務(wù)完成結(jié)果。其次工人的動(dòng)態(tài)性，不能保證可用工人一定是信譽(yù)度高的工人，低技能等級(jí)工人會(huì)被分配他們無(wú)法完成的任務(wù)，導(dǎo)致低質(zhì)量的任務(wù)完成結(jié)果。由于低技能工人和惡意工人的存在，會(huì)嚴(yán)重地影響任務(wù)完成質(zhì)量，所以合理的任務(wù)分配算法對(duì)于眾包系統(tǒng)的發(fā)展起到了關(guān)鍵的作用。本文針對(duì)工人信譽(yù)度的問(wèn)題，展開(kāi)相關(guān)研究。

2? 研究框架

眾包實(shí)現(xiàn)的完整過(guò)程為：任務(wù)請(qǐng)求者（發(fā)包商）首先在眾包平臺(tái)上發(fā)布任務(wù)，需要給出任務(wù)的詳細(xì)描述以及要求和工人完成任務(wù)后可獲得的獎(jiǎng)金。工人注冊(cè)或登錄平臺(tái)，即可決定是否參與到此任務(wù)中。如圖3所示。

已知任務(wù)和工人的經(jīng)緯度以及工人的信譽(yù)度（dlust），這時(shí)就需要我們跟據(jù)這些已知條件算出每個(gè)工人所對(duì)應(yīng)該任務(wù)的V值，V值越大也就意味著該工人越適合該任務(wù)。算法將根據(jù)V值為任務(wù)分配最合適的工人，為任務(wù)根據(jù)V值分配合適的一個(gè)工人或多個(gè)工人。

眾包平臺(tái)將根據(jù)V值對(duì)任務(wù)推薦工人，我們認(rèn)為V>0為推薦對(duì)象，當(dāng)前一個(gè)推薦對(duì)象被占用可依此降低V值。當(dāng)工人接收到平臺(tái)的推薦時(shí)參與到此任務(wù)中。參與者為了完成此任務(wù)將付出努力，并在任務(wù)截止時(shí)間前在平臺(tái)上提交一個(gè)質(zhì)量為q的方案，最后發(fā)包商在時(shí)間截止后，評(píng)審所參與者提交的方案并將獎(jiǎng)金通過(guò)眾包平臺(tái)發(fā)放給提交了質(zhì)量最高的方案的參與者。

我們假定所有工人的信譽(yù)參數(shù)為R（根據(jù)每個(gè)工人的信譽(yù)度dlust用歸一化方法為其算出一個(gè)0-1之間的R值）。同理我們假定所有參與者的距離參數(shù)為K（根據(jù)當(dāng)前工人與當(dāng)前任務(wù)計(jì)算出之間的距離（dist）、每個(gè)工人與每個(gè)任務(wù)之間的距離最大值max與最小值min，用歸一化方法為其算出一個(gè)0-1之間的K值），我們稱(chēng)R越大其參與者的可信度越強(qiáng)，反之可信度越弱;同理K越小其最佳距離則越近。而α、β則是其信譽(yù)參數(shù)與距離參數(shù)在空間眾包中的占比，多次實(shí)驗(yàn)與結(jié)果分析最終確定了α值為0.43、β值為0.57。

首先，當(dāng)dist與min都為0時(shí)，則不去判斷距離僅僅單方面判斷符合要求的工人的可信度。其次，當(dāng)可信度R達(dá)到可以忽略地理位置的高度時(shí)，那么推薦方案僅僅依靠工人的可信度。

3? 實(shí)驗(yàn)分析

數(shù)據(jù)集采用大學(xué)生數(shù)學(xué)建模競(jìng)賽中公開(kāi)的數(shù)據(jù)集，工人1-20信譽(yù)度從高至低且地理位置相對(duì)集中。根據(jù)圖4的數(shù)據(jù)，我們可以清晰地看到任務(wù)16-20與20個(gè)工人計(jì)算的V值的最大波動(dòng)有所體現(xiàn)，但總體來(lái)說(shuō)波動(dòng)在可接受范圍之內(nèi)。

圖5為20個(gè)任務(wù)中所推薦的工人（系列）V值均大于0，雖然會(huì)有其他元素影響V值，但是在每個(gè)系列中其V值的波動(dòng)同時(shí)也在可接受范圍內(nèi)。這體現(xiàn)出算法的穩(wěn)定性較好。

圖6和圖7中在與隨機(jī)算法進(jìn)行對(duì)比時(shí)，不難發(fā)現(xiàn)，在信譽(yù)度方面隨機(jī)值選取相對(duì)波動(dòng)較大，本文的算法計(jì)算值較平穩(wěn)。在距離方面本文算法距離控制在27-81這個(gè)穩(wěn)定的區(qū)間內(nèi)，而隨機(jī)匹配的工人任務(wù)間的距離值較大，綜上所述本文提出的算法較好。

4? 結(jié)論

本文提出基于工人信譽(yù)度和距離的任務(wù)分配算法，能夠有效地對(duì)問(wèn)題進(jìn)行求解。對(duì)工人進(jìn)行選擇時(shí)，需要對(duì)工人綜合得分進(jìn)行計(jì)算，根據(jù)工人的得分排序來(lái)選擇工人。實(shí)驗(yàn)表明，使用Kevin算法可以更好地處理帶工人信譽(yù)度的空間眾包任務(wù)分配問(wèn)題。

雖然Kevin算法綜合表現(xiàn)良好，但是也存在一定的不足之處，仍需要進(jìn)一步研究并改進(jìn)。比如每個(gè)系列與任務(wù)所對(duì)應(yīng)的位置波動(dòng)的限制數(shù)還是不夠明確，比如在距離的計(jì)算中，我們采用了經(jīng)緯度算法，而實(shí)際上應(yīng)該更為復(fù)雜，還要根據(jù)地理?xiàng)l件、時(shí)間以及交通狀況來(lái)定。本文在分配不成功的任務(wù)處理上不夠完善，還應(yīng)該具備反饋功能，通過(guò)反饋的方式動(dòng)態(tài)調(diào)整工人，將任務(wù)的等級(jí)包含進(jìn)來(lái)是下一步研究重點(diǎn)。

參考文獻(xiàn)：

[1]http：//www.crowdcloud.com/.

[2]http：//blog.csdn.net/yuanxing14/article/details/41948485.

[3]于德安.眾包任務(wù)分配算法的改進(jìn)與應(yīng)用[D].大連海事大學(xué)，2016.