時空眾包環(huán)境下基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法

劉　輝，李盛恩

(山東建筑大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，濟南 250101)(*通信作者電子郵箱megatron101@163.com)

0　引言

“眾包”這一概念是由Jeff Howe提出的，旨在幫助機構(gòu)把一些工作交給互聯(lián)網(wǎng)用戶。早期的眾包平臺包括Amazon’s Mechanical Turk、CrowdFlower，需要互聯(lián)網(wǎng)用戶利用個人計算機完成相應(yīng)的任務(wù)。近幾年，移動智能設(shè)備的快速普及極大地促進了移動互聯(lián)網(wǎng)的發(fā)展，眾包平臺也逐漸得到了業(yè)界和大眾的關(guān)注，例如滴滴打車、餓了么等應(yīng)用。因此，眾包平臺正式從傳統(tǒng)眾包發(fā)展成為時空眾包。與傳統(tǒng)眾包的研究類似，時空眾包同樣專注于任務(wù)分配。移動智能設(shè)備攜帶了用戶的個人信息如位置、手機號碼等，任務(wù)請求者將個人信息及具體任務(wù)提交到平臺，平臺在掌握任務(wù)及工人信息的情況下，選出合適工人去完成任務(wù)請求者的任務(wù)，并得到報酬。因此如何將隨機出現(xiàn)并帶有時間、位置信息的任務(wù)分配給最合適的工人并使報酬最大化成為時空眾包環(huán)境下要解決的問題。本文以一類新型時空眾包平臺應(yīng)用南瓜車為例，在分析貪心算法和隨機閾值算法的基礎(chǔ)上，設(shè)計一種基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法。

1　相關(guān)研究

1.1　問題定義

本章介紹任務(wù)分配算法中涉及到的實體對象及評價標(biāo)準，并舉例闡述實現(xiàn)任務(wù)分配的具體過程。

1)眾包任務(wù)t。t為任務(wù)請求者通過移動智能設(shè)備向平臺發(fā)出的任務(wù)請求，可定義為t={Pt,Rt,St,Et,Mt}。其中：Pt、Rt代表t出現(xiàn)的位置和活動范圍；St、Et代表t的上線時間和下線時間，若在此時間段內(nèi)t得不到分配，則用戶下線；Mt是任務(wù)t的回報。

2)眾包工作地點p。p為任務(wù)執(zhí)行的地點，可定義為p={Pp,Sp,Ep,Cp}。其中：Pp代表p出現(xiàn)的位置；Sp、Ep分別代表p的上線時間和下線時間；Cp是地點p的容量，即能夠容納Cp個任務(wù)在p執(zhí)行。

3)眾包工人w。w可定義為w={Pw,Rw,Sw,Ew,Qw}。其中：Pw、Rw是w出現(xiàn)的位置和活動范圍；Sw、Ew代表w的上線時間和下線時間；Qw是w的工作質(zhì)量。

4)效用。效用定義為U(t,w,p)=Mt*Qw，即若任務(wù)t和工人w得以分配，則效用為任務(wù)回報和工人工作質(zhì)量的乘積。

在線任務(wù)分配包括三類對象：任務(wù)t、工作地點p、工人w依時間次序出現(xiàn)，眾包平臺在任意時刻根據(jù)任務(wù)分配算法對此時刻已出現(xiàn)的t∈T，p∈P，w∈W進行匹配(T、P、W為已出現(xiàn)且未進行匹配的任務(wù)、地點和工人的集合)，最終使效用總和最大化。

圖1　任務(wù)、地點和工人分布示意圖Fig. 1　Task, position and worker distribution diagram

1.2　系統(tǒng)分配任務(wù)模式下的任務(wù)分配

無論是有兩類對象的眾包平臺，還是有三類對象在線分配的新型眾包平臺，都涉及到了任務(wù)分配問題。根據(jù)時空眾包任務(wù)分配科技報告[1],時空眾包平臺的任務(wù)分配有兩種不同的模式：工人選擇任務(wù)(Worker Selected Tasks, WST)和系統(tǒng)分配任務(wù)(Server Assigned Tasks, SAT)。WST模式是在線工人不通過眾包平臺分配而自主選擇任務(wù)請求者發(fā)出的任務(wù)的工作模式，因此眾包平臺不能控制任務(wù)分配使總效用達到最優(yōu)，故WST模式不屬于本文研究的重點。以下將介紹SAT模式下兩種對實時性要求不同的任務(wù)分配問題：離線任務(wù)分配與在線任務(wù)分配。

1.2.1離線分配

離線任務(wù)分配問題是傳統(tǒng)眾包中的經(jīng)典問題，其中最具有代表性的微任務(wù)平臺如Amazon’s Mechanical Turk[2]，文獻[2]中闡述了傳統(tǒng)眾包平臺可以解決的圖像識別、信息檢索、自然語言處理及專家系統(tǒng)等，該平臺為最早的離線分配模型。

隨著傳統(tǒng)眾包的發(fā)展，離線分配問題可以根據(jù)待分配對象的數(shù)量分為兩類：離線二分匹配和離線三分匹配。長期以來，離線二分匹配一直都是組合優(yōu)化領(lǐng)域的經(jīng)典問題，可以看作對一個無向圖G=(U∪V,E)求E的子集M的過程。離線二分匹配可以根據(jù)邊是否有權(quán)重分為最大二分匹配和最大二分加權(quán)匹配[3]，分別對應(yīng)眾包領(lǐng)域中的兩個優(yōu)化目標(biāo)：最大化任務(wù)分配數(shù)和最大化效用值。針對這兩個不同的優(yōu)化目標(biāo)，文獻[3]分別介紹了Ford-Fulkerson算法和Hungarian算法。文獻[4-5]為了將二分圖匹配問題擴展到空間數(shù)據(jù)中，把離線分配問題看作等價于空間匹配問題的一個變種問題。針對空間數(shù)據(jù)的任務(wù)分配，文獻[4，6]針對移動距離進行了研究，文獻[4]的優(yōu)化目標(biāo)是基于有容量限制的條件下，最小化匹配的距離之和，而文獻[6]的優(yōu)化目標(biāo)為最小化最大匹配距離。文獻[7]均提出了兩段式分配策略，不同之處在于文獻[7]將整個分配過程平均為兩個部分，前后兩個部分分別采用貪心思想和Hungarian算法解決圖匹配問題，而文獻[8]則在得到初始分配后，在保持分配穩(wěn)定的基礎(chǔ)上維護分配的最優(yōu)性。與離線二分匹配問題不同，最大三分匹配為NP-hard問題[9]，可利用局部搜索的思想去嘗試獲得更好的結(jié)果。

1.2.2在線分配

在SAT模式中，在線分配問題不僅存在優(yōu)化目標(biāo)的不同，也存在待分配對象類別和數(shù)量的區(qū)別。文獻[8]認為對象的出現(xiàn)順序能夠影響分配算法的性能，已存在的研究中都在討論最壞情況下的算法性能，但研究發(fā)現(xiàn)最壞情況的出現(xiàn)概率非常低，如果參與對象的數(shù)量是n的話，則最壞情況出現(xiàn)的概率為1/n!，故研究在最壞情況下的算法性能意義并不大，應(yīng)討論算法在大多數(shù)情況下的平均性能，并提出了競爭比的概念。根據(jù)文獻[10]，在線任務(wù)分配可以規(guī)約為有權(quán)雙向圖匹配問題，文獻[11-12]分別利用貪心算法解決此問題，使競爭比達到了1/2。文獻[5]中先把任務(wù)分配問題規(guī)約為穩(wěn)定婚姻問題和最近點問題，然后提出了一種針對無權(quán)雙向圖匹配的Chain算法，并在有權(quán)圖上進行了改進。該算法首先隨機選取一個待分配的對象O作為初始點尋找可與之匹配且最近鄰的其他類對象Y，再尋找Y的其他最近鄰的對象，以此類推。文獻[6]提出了關(guān)于距離的閾值算法，只有移動距離小于d的對象才會得到匹配。文獻[13]針對兩類對象的在線分配，以最大化任務(wù)分配數(shù)為優(yōu)化目標(biāo)，但只允許一類對象動態(tài)出現(xiàn)，對解決在線的最大二分匹配問題提出了新的思路。文獻[8]改進了貪心算法加入閾值限制條件，并提出了兩段式全局在線分配算法，根據(jù)對問題規(guī)模的估計，在任務(wù)分配過程中，前半段采用貪心的策略為每個新出現(xiàn)的任務(wù)(工人)分配可能得到最高效用的工人(任務(wù))，后半段使用Hungarian算法對有權(quán)雙向圖進行匹配。文獻[14]改進了閾值算法，提出了自適應(yīng)閾值算法，該算法能夠根據(jù)任務(wù)分配情況自動調(diào)整閾值的大小。

1.3　其他相關(guān)工作

為保持眾包平臺參與人員的數(shù)量,文獻[15]提出一套積分管理策略，在對眾包參與者的吸引及眾包工人的工作質(zhì)量上有一定的幫助。文獻[16]通過反轉(zhuǎn)競拍、游戲化、經(jīng)驗值更新等策略激勵眾包參與者和吸引更多的眾包參與者。文獻[17]提出一種基于多種任務(wù)的主題感知任務(wù)分配策略，根據(jù)任務(wù)的類型分配擅長該類型任務(wù)的眾包工人。

基于以上研究可以發(fā)現(xiàn)，在各類閾值算法中，雖然通過設(shè)置閾值可以過濾掉效用較小的分配對，但僅僅設(shè)置閾值往往還不能使結(jié)果接近最優(yōu)，必須有相應(yīng)的匹配策略來調(diào)度?；诖?，本文提出一種基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法和匹配策略。實驗表明，該算法能夠在真實情況下使總效用接近最優(yōu)，算法整體表現(xiàn)優(yōu)于貪心算法和隨機閾值算法。

2　閾值算法與匹配策略

2.1　貪心算法

文獻[14]中稱貪心算法為樸素隨機算法，意為對每一個新出現(xiàn)的對象，如果通過這個對象可以作出若干任務(wù)分配，則從任務(wù)分配集中隨機選擇一種分配。算法的輸入為新出現(xiàn)的對象，包括任務(wù)、工人、工作地點以及效用函數(shù)；算法的輸出為分配結(jié)果。當(dāng)新對象出現(xiàn)時，算法會在候選隊列中隨機選擇滿足約束條件的匹配對象。如果得到的匹配結(jié)果不為空，則把新出現(xiàn)的對象和匹配到的對象加入到分配結(jié)果，并把匹配對象從候選隊列中移除，停止查找；如果匹配對象為空，則把新出現(xiàn)的對象加入到候選隊列中。

算法1貪心算法。

輸入隨機出現(xiàn)的任務(wù)、工人、工作地點及效用函數(shù)。

對每一個新出現(xiàn)的任務(wù)、工人及工作地點v：

1)根據(jù)出現(xiàn)對象的類型，在候選隊列中選擇滿足約束的其他兩類對象:o1,o2←Cand。

2)若o1,o2不為空，則將v與o1,o2進行匹配，得到匹配結(jié)果:M←{v,o1,o2}。

3)若o1,o2為空，則將v加入候選隊列:Cand←v。輸出匹配結(jié)果M。

貪心算法雖時間消耗比較小，但是由于任務(wù)、地點、工人完全是按照出現(xiàn)順序進行分配，沒有考慮效用的大小，所以在不同回報的任務(wù)出現(xiàn)沖突時，貪心算法會按照出現(xiàn)順序選擇待分配對象。若回報較低的任務(wù)先出現(xiàn)并且滿足分配條件時，后出現(xiàn)的較高回報的任務(wù)將無法得到分配。

2.2　隨機閾值算法

隨機閾值算法是改進的貪心算法，對新出現(xiàn)的對象,除需要對象滿足基本的活動范圍條件外，還需滿足閾值條件即該分配產(chǎn)生的效用應(yīng)大于隨機閾值。如算法2所示，在算法第1)步，首先閾值設(shè)置為ek，k為隨機選擇0～θ的值，θ的取值為：

θ=「ln(Umax+1)?

(1)

其中Umax是從任務(wù)分配過程中單個分配可能獲得的最大效用，可以從歷史分配數(shù)據(jù)中獲得。在候選隊列中隨機選擇一個滿足約束條件且滿足產(chǎn)生的效用大于閾值的匹配對象。如果匹配對象不為空，則加入分配結(jié)果，然后從候選隊列中移除匹配對象，停止查找；否則把新對象加入到候選隊列中。最后返回分配結(jié)果。

算法2隨機閾值算法。

輸入隨機出現(xiàn)的任務(wù)、工人、工作地點及效用函數(shù)。

對每一個新出現(xiàn)的任務(wù)、工人及工作地點v：

1)隨機設(shè)置閾值ek:k∈[0,θ]，θ=「ln(Umax+1)?。

2)根據(jù)出現(xiàn)對象的類型,在候選隊列中選擇滿足約束且產(chǎn)生效用大于閾值的其他兩類對象:o1,o2←Cand。

3)若o1,o2不為空，則將v與o1,o2進行匹配，得到匹配結(jié)果:M←{v,o1,o2}。

4)若o1,o2為空，則將v加入候選隊列:Cand←v。輸出匹配結(jié)果M。

盡管隨機閾值算法能夠在一定程度上過濾掉效用較低的任務(wù)分配，但是由于k值的選擇是隨機的，所以算法總效用差異較大，表現(xiàn)不穩(wěn)定。

2.3　基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法

在閾值算法中，三類對象可以分配的前提是滿足一定的閾值條件。閾值的設(shè)置關(guān)鍵之處在于：若閾值設(shè)置過低，無法起到過濾作用，使整個分配過程與貪心算法類似且計算量增多；若閾值設(shè)置過高，大部分對象無法正常參與分配，浪費平臺總效用。為解決閾值的設(shè)置問題，本文提出一種基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法，算法思想如下。

2.3.1閾值作用對象

在貪心算法和隨機閾值算法中，閾值通常是針對效用設(shè)置的，有如下缺點：1)閾值產(chǎn)生作用的前提是對任務(wù)進行預(yù)分配得到效用值，根據(jù)該效用值是否滿足閾值條件決定該分配是否有效，若未滿足閾值條件則考慮其他分配，這種局部搜索方法造成的時間消耗會使任務(wù)分配的等待時間變長；2)有一定的概率造成效用的浪費，例如高回報任務(wù)與低工作質(zhì)量工人結(jié)合或低回報任務(wù)與高工作質(zhì)量工人結(jié)合的分配方式，雖然效用值滿足閾值條件，但是以上兩種分配方式并不能得到理想的效用值。

為解決以上問題，本文將任務(wù)的回報值作為閾值的作用對象。當(dāng)任務(wù)出現(xiàn)時，考察該任務(wù)的回報值，若任務(wù)回報值滿足閾值條件則進入任務(wù)隊列，否則丟棄掉。為任務(wù)的回報設(shè)置閾值有以下優(yōu)勢：1)如圖2所示，在任務(wù)出現(xiàn)時，按照閾值大小可直接決定此任務(wù)是否可加入任務(wù)隊列，省去了局部搜索的過程，減少時間消耗并提高了分配效率；2)過濾掉回報較小的任務(wù)，能降低低回報任務(wù)與高工作質(zhì)量工人分配的概率，提高眾包平臺整體的效用值。

圖2　閾值算法示意圖Fig. 2　Threshold algorithm diagram

2.3.2閾值設(shè)置

基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法采用一種在線調(diào)整的策略，該算法的運行過程根據(jù)實時出現(xiàn)的任務(wù)、工人、工作地點和得到分配的對象以及超時的對象，實時統(tǒng)計當(dāng)前平臺中空閑任務(wù)(Free Task, FT)、空閑工人(Free Worker, FW)、空閑工作地點(Free Position, FP)的數(shù)量，以及最大回報值Rmax和最小回報值Rmin。根據(jù)前一時刻的閾值θ′，在調(diào)整基數(shù)?的基礎(chǔ)上計算出當(dāng)前時刻的閾值θ。

(2)

為防止閾值的波動過大導(dǎo)致的平臺運行狀態(tài)不穩(wěn)定，閾值的設(shè)置應(yīng)當(dāng)控制在一定的范圍內(nèi)，本文將閾值的調(diào)整范圍設(shè)置為當(dāng)前時刻出現(xiàn)任務(wù)回報的差值，每次調(diào)整的范圍為[-?,?]。當(dāng)某時刻未出現(xiàn)任務(wù)或出現(xiàn)單個任務(wù)時，調(diào)整范圍設(shè)置為1，只進行較小幅度的調(diào)整。CRmax與CRmin分別是當(dāng)前時刻出現(xiàn)的最大回報值和最小回報值。

(3)

算法3基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法。

輸入隨機出現(xiàn)的任務(wù)、工人、工作地點及效用函數(shù)。

1)對每一個新出現(xiàn)的任務(wù)、工人及工作地點v，根據(jù)式(2)計算當(dāng)前時刻的閾值。

2)根據(jù)出現(xiàn)對象的類型，在候選隊列中選擇滿足約束且產(chǎn)生效用大于閾值的其他兩類對象:o1,o2←Cand。

3)若o1,o2不為空，則將v與o1,o2進行匹配，得到匹配結(jié)果:M←{v,o1,o2}。

4)若o1,o2為空，則將v加入候選隊列:Cand←v。

輸出匹配結(jié)果M。

2.4　匹配策略

任務(wù)分配算法的性能及效果在很大程度上依賴數(shù)據(jù)的分布或?qū)ο蟪霈F(xiàn)的順序[8]，若數(shù)據(jù)分布不均勻則算法的效果無法保證。為消除這種不確定性，本文采用“一對一”的匹配策略，在滿足約束條件即待分配的對象在互相的活動范圍內(nèi)時，當(dāng)任務(wù)回報確定時，與之匹配的工人也將確定。通過匹配策略，使平臺的總效用值達到最優(yōu)或接近最優(yōu)。

“一對一”的匹配策略采用Min-max normalization方法為每個任務(wù)匹配工人。假設(shè)任務(wù)回報值的范圍為Mt∈[0,100]，工人的工作質(zhì)量Qw∈[0,1],若出現(xiàn)一個任務(wù)回報值為80的任務(wù)，則根據(jù)匹配策略將為其匹配一個工作質(zhì)量為0.8的眾包工人。匹配策略可以避免低回報任務(wù)與高工作質(zhì)量工人結(jié)合或高回報值任務(wù)與低工作質(zhì)量工人結(jié)合造成平臺效用的浪費。

在數(shù)據(jù)分布不均勻時，采用匹配策略能夠出現(xiàn)任務(wù)或工人的閑置問題。如圖3所示，對gMission[18]數(shù)據(jù)集進行統(tǒng)計發(fā)現(xiàn)，工人的工作質(zhì)量集中在0.5左右，而任務(wù)的回報值集中在80～90，回報值為90的任務(wù)與工作質(zhì)量為0.5的工人都不能完全匹配到合適的對象。為解決此問題，本文把任務(wù)與工人根據(jù)其數(shù)據(jù)分布分為兩個部分。通過對歷史數(shù)據(jù)的分析和估計得到任務(wù)回報值的中位數(shù)α和眾包工人工作質(zhì)量的中位數(shù)β。當(dāng)出現(xiàn)一個任務(wù)時，若任務(wù)的回報Mt∈[0,α]，則匹配的工人工作質(zhì)量也應(yīng)滿足Qw∈[0,β]；若任務(wù)的回報Mt∈[α,100]，則匹配的工人工作質(zhì)量也應(yīng)滿足Qw∈[β,1]。根據(jù)此規(guī)則，使用Min-max normalization方法尋找一個滿足匹配策略的其他對象。

圖3　gMission數(shù)據(jù)集任務(wù)回報及工人工作質(zhì)量分布Fig. 3　Task return and worker quality distribution of gMission data set

而真實情況中，在匹配確定工作質(zhì)量或回報的對象中，往往沒有完全吻合條件的確定對象，此時可匹配近似滿足條件的對象，近似對象與確定對象之間的差異不超過5%，此差異值的設(shè)置可參考眾包對象的密度。

2.5　基于統(tǒng)計的概率預(yù)測

在2.4節(jié)中介紹了當(dāng)出現(xiàn)一個任務(wù)t時，如何匹配滿足約束條件且使效用最大化的工人w。本節(jié)主要講述計算工人w會在任務(wù)t的活動時間內(nèi)出現(xiàn)的概率，按照概率決定任務(wù)t是否等待工人w。

在歷史數(shù)據(jù)中可以得到在整個眾包活動周期中可與任務(wù)t匹配的工人w的數(shù)量，通過對多組數(shù)據(jù)的學(xué)習(xí)可以得到一個估值。任務(wù)t的生命周期有時長限制，可計算出在任務(wù)t的生命周期內(nèi)可以出現(xiàn)的工人w的數(shù)量。由于眾包平臺任務(wù)及工人的出現(xiàn)受客觀因素影響較大，故在任務(wù)t的生命周期內(nèi)可以通過匹配策略匹配到工人w的概率是：

(4)

其中β是在不同環(huán)境下客觀因素對眾包平臺的影響指數(shù)，如天氣、節(jié)假日等。當(dāng)p(t,w)≥θ，即在任務(wù)t的生命周期內(nèi)匹配到工人w的概率大于θ時，任務(wù)t選擇等待工人w；反之，則不等待。

在估計任務(wù)t匹配到工人w的概率的同時，為該類工人W建立等待隊列Queue，工作質(zhì)量相同的工人可看作一類工人，該隊列中存儲正在等待該類工人W的任務(wù)。Queue的長度為σ-Eσ，即估計的將要出現(xiàn)的該類工人的數(shù)量σ與已經(jīng)出現(xiàn)的該類工人數(shù)量Eσ之差。查看W的等待隊列是否超過該類工人出現(xiàn)的個數(shù)，若超過，則t的匹配對象自動等待w的近似對象。根據(jù)以上規(guī)則，可定義損失函數(shù)：

(5)

2.6　運行實例

假設(shè)目前可以通過閾值算法加入到隊列的眾包對象有：任務(wù)t1、t2和t3、工作地點p1，工人w1和w2,且對所有對象都滿足p(t,w)≥θ。其中眾包任務(wù)的回報值為t1:40，t2:58和t3:100，眾包工人的工作質(zhì)量為w1:0.4和w2:0.96，眾包工作地點的容量為3，加入隊列的順序為t3、p1、w1、t1、w2、t2，眾包任務(wù)回報值的中位數(shù)為60，眾包工人工作質(zhì)量的中位數(shù)為0.4，且所有的對象都處在其他對象的活動范圍內(nèi),其分配過程如圖4所示。

圖4　匹配策略運行示意圖Fig. 4　Running diagram of matching strategy

如圖4所示，當(dāng)t3、p1、w1出現(xiàn)時，按照匹配策略的規(guī)則未進行匹配操作。t2出現(xiàn)后，根據(jù)Min-max normalization方法可求得應(yīng)為t2作出匹配的眾包工人的工作質(zhì)量為0.39，但此時隊列中不存在工作質(zhì)量為0.39的眾包工人，由于差異值設(shè)為5%,則其近似對象的工作質(zhì)量取值范圍為[0.34,0.44]，故t2與p1、w1進行匹配，得到的效用值為23.2。同理w2出現(xiàn)后與t3匹配，得到效用值為96，總效用為118.2。在不使用匹配策略的情況下，能夠進入待分配隊列的對象則會按照出現(xiàn)順序進行分配，得到的效用值為78.4。

3　實驗結(jié)果與分析

3.1　實驗環(huán)境

本文實驗均使用了處理器為Intel Core i7- 7500U CPU @ 2.70 GHz 2.90 GHz、內(nèi)存為8 GB(內(nèi)存頻率1 867 MHz)，操作系統(tǒng)為Windows 10的計算機完成。實驗使用的編程語言為Python2.7，使用的集成開發(fā)環(huán)境為PyCharm 2016。實驗數(shù)據(jù)保存在文本文件中，按行讀取以表示眾包參與者出現(xiàn)的時間和順序，同時借助了MongoDB存儲在文本文件中讀取到的實驗數(shù)據(jù)。

3.2　數(shù)據(jù)集

實驗使用gMission的數(shù)據(jù)集。為了保護隱私，gMission數(shù)據(jù)集在真實數(shù)據(jù)集的基礎(chǔ)上進行了部分模糊處理。gMission數(shù)據(jù)集共分為5個數(shù)據(jù)文件，分別對應(yīng)將眾包活動范圍設(shè)置為不同數(shù)值時所產(chǎn)生的數(shù)據(jù)，眾包活動范圍有：10、15、20、25、30。每份數(shù)據(jù)文件中包含的屬性包括眾包參與者的類型、出現(xiàn)時間、坐標(biāo)X、坐標(biāo)Y、活動范圍，這五個屬性是共有的。眾包任務(wù)還有回報值、截止時間兩個屬性，眾包工作地點有容量屬性，眾包工人有工作質(zhì)量屬性。每個部分的數(shù)據(jù)集共有6 300條數(shù)據(jù)，其中包括3 000個任務(wù)、3 000個工人、300個工作地點(每個工作地點容量為10)，圖5為活動范圍為10時的三類對象隨時間出現(xiàn)的累計數(shù)量。

圖5　三類對象依時間出現(xiàn)的個數(shù)Fig. 5　Numbers of three types of objects which appear in time

3.3　實驗設(shè)置

本文提出的基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法與貪心算法、隨機閾值算法進行對比，評價指標(biāo)為獲得的總效用值，即各個分配得到的效用和。同時本文使用的數(shù)據(jù)為五種眾包活動范圍的數(shù)據(jù)集，觀察改變活動范圍時效用的變化。在隨機閾值算法中，Umax設(shè)置為100。在基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法中，初始閾值θ設(shè)置為歷史數(shù)據(jù)中任務(wù)回報的均值，影響指數(shù)β設(shè)置為1。

3.4　實驗結(jié)果

實驗結(jié)果如圖6所示，可以觀察到隨著活動范圍的擴大，總效用也在增長，原因可以歸結(jié)為隨著活動范圍的擴大，任務(wù)能夠在更大的范圍內(nèi)匹配合理的工人。同時，在不同活動范圍的數(shù)據(jù)集上，基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法的總效用始終優(yōu)于貪心算法和隨機閾值算法，并且隨著活動范圍的不斷擴大，貪心算法和隨機閾值算法的總效用值趨于不變，而基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法依然可以獲得較高的總效用值。

圖6　gMission數(shù)據(jù)集實驗結(jié)果Fig. 6　Experimental results for gMission data set

3.5　實驗分析

通過在真實數(shù)據(jù)集上進行實驗，發(fā)現(xiàn)在不同活動范圍的條件下，基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法產(chǎn)生的總效用優(yōu)于貪心算法和隨機閾值算法，并且隨著活動范圍的擴大，總效用的增長不會出現(xiàn)衰減。這說明本文中提出的基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法具有較好的實際應(yīng)用價值。

4　結(jié)語

本文研究了時空眾包環(huán)境下三類對象的在線分配算法，并分析了貪心算法和隨機閾值算法無法獲得較高效用的原因，提出了一種基于統(tǒng)計預(yù)測的自適應(yīng)閾值算法。本文在充分理解閾值算法作用機制的前提下，改變了閾值算法的作用對象，提出了旨在最大限度利用可用資源的算法，通過對眾包參與者人數(shù)的分析，制定閾值的設(shè)置及調(diào)整策略。通過匹配策略，眾包平臺的任務(wù)分配不再是隨機分配，而是一種更具有確定性的分配方式。實驗表明，本文提出的任務(wù)分配方法能夠使眾包平臺獲得更高的總效用值。

參考文獻:

[1]CHENG P, JIAN X, CHEN L. Task assignment on spatial crowdsourcing [R/OL]. [2017- 05- 02]. http://arxiv.org/pdf/1605.09675.

[2]KITTUR A, CHI E H, SUH B. Crowdsourcing user studies with Mechanical Turk [C]// CHI ’08: Proceedings of the 2008 SIGCHI Conference on Human Factors in Computing Systems. New York: ACM, 2008: 453-456.

[3]CORMEN T H, LEISERSON C E, RIVEST R, et al. Introduction to Algorithms [M]. Cambridge, MA: MIT Press, 2009: 118.

[4]LEONG HOU U, MAN LUNG YIU, MOURATIDIS K, et al. Capacity constrained assignment in spatial databases [C]// SIGMOD ’08: Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 15-28.

[5]WONG R C-W, TAO Y, FU A W-C, et al. On efficient spatial matching [C]// VLDB ’07: Proceedings of the 33rd International Conference on Very large Data Bases. New York: ACM, 2007: 579-590.

[6]LONG C, WONG R C-W, YU P S, et al. On optimal worst-case matching [C]// SIGMOD ’13: Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 845-856.

[7]TONG Y, SHE J, DING B, et al. Online mobile micro-task allocation in spatial crowdsourcing [C]// ICDE 2016: Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering. Piscataway, NJ: IEEE, 2016: 49-60.

[8]LEONG HOU U, MOURATIDIS K, MAMOULIS N. Continuous spatial assignment of moving users [J]. The VLDB Journal — The International Journal on Very Large Data Bases, 2010, 19(2): 141-160.

[9]GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-completeness [M]. New York: W. H. Freeman, 1979: 90-91.

[10]MEHTA A. Online matching and ad allocation [J]. Foundations & Trends in Theoretical Computer Science, 2013, 8(4): 265-368.

[11]WANG Y, WONG S C-W. Two-sided online bipartite matching and vertex cover: beating the greedy algorithm [C]// ICALP 2015: Proceedings of the 2015 International Colloquium on Automata, Languages, and Programming, LNCS 9134. Berlin: Springer, 2015: 1070-1081.

[12]TING H F, XIANG X. Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching [J]. Theoretical Computer Science, 2015, 607(P2): 247-256.

[13]HASSAN U U, CURRY E. A multi-armed bandit approach to online spatial task assignment [C]// UIC-ATC-ScalCom ’14: Proceedings of the 2014 IEEE 11th International Conference on Ubiquitous Intelligence and Computing, and 2014 IEEE 11th International Conference on Autonomic and Trusted Computing, and 2014

IEEE 14th International Conference on Scalable Computing and Communications and Its Associated Workshops. Washington, DC: IEEE Computer Society, 2014: 212-219.

[14]宋天舒，童詠昕.空間眾包環(huán)境下的三類對象在線任務(wù)分配[J].軟件學(xué)報，2017,28(3):611-630. (SONG T S, TONG Y X. Three types of objects online task allocation space crowdsourcing environment.[J] Journal of Software, 2017, 28(3): 611-630.)

[15]REN J, ZHANG Y, ZHANG K, et al. SACRM: Social Aware Crowdsourcing with Reputation Management in mobile sensing [J]. Computer Communications, 2014, 65: 55-65.

[16]DAI W, WANG Y, JIN Q, et al. An integrated incentive framework for mobile crowdsourced sensing [J]. Tsinghua Science and Technology, 2016, 21(2): 146-156.

[17]張曉航,李國良,馮建華.大數(shù)據(jù)群體計算中用戶主題感知的任務(wù)分配[J].計算機研究與發(fā)展,2015,52(2):309-317. (ZHANG X H, LI G L, FENG J H. User topic aware task assignment in large data group computing [J]. Journal of Computer Research and Development, 2015, 52 (2): 309-317).

[18]CHEN Z, FU R, ZHAO Z, et al. gMission: a general spatial crowdsourcing platform [J]. Proceedings of the Very Large Data Base Endowment, 2014, 7(13): 1629-1632.