毛鶯池，穆 超，包 威，李曉芳

(1.河海大學 計算機與信息學院，南京 211100； 2. 常州工學院 計算機信息工程學院，江蘇 常州 213032)(*通信作者電子郵箱1813487536@qq.com)

0 引言

眾包是指“一種把過去由專職員工執(zhí)行的工作任務公開的Web平臺以自愿的形式外包給非特定的解決方案提供者群體來完成的分布式問題求解模式”[1]。隨著智能手機的普及，形成了眾包新的發(fā)展方向——空間眾包(Spatial Crowdsourcing)[2]。在眾包中用戶只要在線執(zhí)行任務并提交任務的結果，而在空間眾包中用戶必須移動到任務指定的地點，才可以執(zhí)行任務?？臻g眾包被廣泛應用于O2O(Online To Offline)、災情監(jiān)控、交通管理、物流管理和社交媒體等領域[3-6]。在空間眾包領域中研究的核心問題[7]是空間任務分配與調(diào)度。現(xiàn)有的研究只是針對多類型任務的分配，并沒有對任務的執(zhí)行情況進行研究。本文以服務類O2O應用為例進行闡述，客人(任務發(fā)布者)發(fā)布需要的服務(任務)，如維修電器、洗車等，眾包平臺為客人分配合適的服務人員(用戶)，服務人員到客人指定的地點提供服務。本研究需要規(guī)劃路線，使得用戶盡可能多地完成任務。本文的主要工作如下：

1)研究的對象是空間眾包中的多類型任務，根據(jù)空間眾包中任務的時空特性，在服務器端推送(Servers Assigned Task, SAT)模式下對任務進行分配，對貪婪分配算法進行改進，提出基于距離ε值分配(Distanceεbased Assignment,ε-DA)算法，為每個用戶分配更多的專業(yè)匹配任務，并保持移動成本與其相差不大。

2)考慮任務的時空性，需要對執(zhí)行任務的路線進行規(guī)劃，以便在最短的時間內(nèi)完成最多的任務。在任務分配基礎上，采用分支定界思想(Branch and Bound Schedule, BBS)對任務進行調(diào)度，針對BBS運算速度較慢問題，提出最有前途分支啟發(fā)式(Most Promising Branch Heuristic, MPBH)算法。

3)實驗證明，提出的任務分配和調(diào)度方法能夠提高任務完成的質(zhì)量以及數(shù)量，并且在運行速度和精確性上有優(yōu)勢。

1 研究現(xiàn)狀

眾包中優(yōu)化目標，可分為空間任務分配與任務調(diào)度問題。

1)任務分配問題。空間任務匹配問題通常轉(zhuǎn)化為最大或最小加權二分圖匹配問題[8]，在靜態(tài)模式下等價于空間匹配問題[9-10]的一種變種問題，而在動態(tài)模式下只能獲取部分信息，利用部分二分圖信息來進行匹配決策[11-15]。在任務分配問題中，優(yōu)化目標是最大任務分配(Maximum Task Assignment, MTA)。在服務器推送(SAT)模式中，針對單一類型任務的任務分配[16-17]，首先采用貪婪算法，盡量分配給用戶maxT個任務；對Greedy算法改進，提出最小區(qū)域熵優(yōu)先級策略，優(yōu)先分配區(qū)域熵小的任務。然后，結合用戶移動到任務地點所需的成本，提出最近距離優(yōu)先級策略，優(yōu)先分配距離用戶最近的任務。針對復雜的任務[18]，復雜任務分配是指將其所有子任務成功分配，才算分配一個復雜任務。在任務分配完成后，產(chǎn)生一個最初的任務序列，這時需要對任務序列進一步優(yōu)化——任務調(diào)度。優(yōu)化任務序列問題在靜態(tài)情形下通常被規(guī)約為經(jīng)典的旅行商問題[19]或定向問題[20]，而在動態(tài)情形下每位眾包參與者需要實時地決定新任務加入到其當前的任務規(guī)劃之中[21]。通過合理規(guī)劃路徑，目標是實現(xiàn)最大任務調(diào)度(Maximum Task Scheduling, MTS)。在用戶選擇任務(Worker Selected Task, WST)模式中研究MTA[22]，針對少量任務情況時，本文基于分支定界的思想去分配。當任務規(guī)模較大時，不斷枚舉任務組合耗時較大，提出最有前途分支啟發(fā)式算法，根據(jù)節(jié)點的上界進行相應的修剪，提高分配的效率。

2)任務調(diào)度問題。然而，在現(xiàn)實眾包應用中，對任務的調(diào)度往往不是單一地進行修剪，對于復雜的多類型任務，需要進行全局分配和局部調(diào)度[23]。文獻[16-17]主要是對任務的分配的研究，并沒有進一步對任務分配的質(zhì)量進行研究；文獻[18]研究的重點則是復雜任務的分解。文獻[22]在WST模式下研究任務調(diào)度問題，會出現(xiàn)多個用戶爭奪同一任務情形，這時本文根據(jù)用戶的移動成本和完成任務的質(zhì)量[24-28]來選擇最佳的用戶；完成任務后，根據(jù)用戶回答的準確性[29]，賦給每個用戶信譽分數(shù)，表示用戶正確完成任務的概率。

綜上，空間眾包中核心問題是空間任務分配與任務調(diào)度。本文綜合考慮這兩方面，針對多類型任務進行研究，優(yōu)化目標是最大化多類型任務完成的質(zhì)量和數(shù)量。

2 多類型任務分配

2.1 問題模式

在SAT模式下，服務器對用戶和任務信息有全局掌控，可以給每個用戶分配附近的任務，最大限度地提高總體任務分配數(shù)量。任務發(fā)布者將任務發(fā)送給SC-server(眾包服務器)，在線用戶將自己的信息報告給SC-server，SC-server根據(jù)這些用戶屬性和任務進行匹配，將任務分配給合適用戶，如圖1所示。

圖1 空間眾包組成

定義1 空間任務(Spatial Task)。一個空間任務t的形式為〈l,d,ei〉。其中：l表示該任務所在的位置；d表示任務t的截止時間；ei表示任務t的類型，下標表示任務的不同類型，多類型任務即所有任務的下標并不相同。本文忽略任務需要的執(zhí)行時間。

定義2 用戶(Worker)。一個用戶w的形式為〈l,q,D,E〉。其中：l表示用戶的當前位置，q表示用戶最多能接受任務的數(shù)量，D表示用戶區(qū)域，E表示用戶具有的專業(yè)能力集合。

定義3 專業(yè)匹配(Expertise Match)[30]。一個匹配的形式為〈w,t〉，其中任務t要在用戶的區(qū)域內(nèi)。當用戶具有完成任務t的專業(yè)能力，即ei∈E，稱為專業(yè)匹配；若ei?E，則稱為非專業(yè)匹配。

如圖2中，在用戶w1的區(qū)域D1內(nèi)，有任務t1、t2、t3、t4和t5，〈w1,t1〉匹配是專業(yè)匹配，因為用戶w1具有兩個專業(yè)能力{e1,e2}，任務t1的類型為e1，e1∈{e1,e2}。而〈w1,t4〉匹配是非專業(yè)匹配，因為任務t4的類型為e3，e3?{e1,e2}。

圖2 一個用戶任務分布實例

定義4 匹配分數(shù)(Score)[30]。對每個匹配〈w,t〉定義一個分數(shù)值Score(w,t)，用于表示用戶完成任務的質(zhì)量。

顯然將維修電器的任務分配給具有維修能力的用戶，完成質(zhì)量會比一般用戶高，因此，專業(yè)匹配分數(shù)高于非專業(yè)匹配分數(shù)。本文不妨假設專業(yè)匹配分數(shù)為3，非專業(yè)匹配分數(shù)為1，在定理1中給出具體證明。如圖2例中，Score(w1,t1)=3，Score(w1,t4)=1。

定義5 任務分配實例集(Task Assignment Instance Set)。在時間實例si時，在線用戶集合為Wi={w1,w2,…,wn}，可分配的任務集合為Ti={t1,t2,…,tm}，所有匹配〈w,t〉的集合為任務分配實例集Ii。|Ii|代表在si時分配任務的數(shù)量。

定義6 移動成本(Travel Cost)。用歐氏距離d(wj,tk)計算表示用戶wj和空間任務tk的移動成本。

2.2 解決問題思路

空間眾包中任務和用戶是動態(tài)的，用戶可以隨時在線或離線，任務也有時間限制，不能獲得全局的用戶和任務信息，在每個實例中，SC-server能夠獲得部分的任務和用戶信息，只能在每個實例分配時進行局部優(yōu)化，以達到最終的相對全局優(yōu)化。現(xiàn)有文獻[30]中貪婪算法思想是分配給每個用戶盡可能多的任務，而且這些任務都是用戶專業(yè)相匹配。若沒有專業(yè)匹配時，用戶只是選擇一般的非專業(yè)匹配任務，不僅導致任務完成質(zhì)量低，而且造成較高的移動成本。

本文首先將多類型任務分配轉(zhuǎn)化為最大權值問題，利用二分圖中的方法進行求解；然后，對基本的貪婪分配算法進行改進，結合空間任務的位置屬性，提出基于距離ε值分配算法(ε-DA)，盡可能多地分配專業(yè)匹配任務；其次，利用空間任務空間屬性，在距離用戶最近范圍內(nèi)選擇ε個任務分配給用戶，這樣在任務調(diào)度時，沒有合適的專業(yè)任務，可以選擇非專業(yè)匹配任務，提高任務的完成數(shù)量，而且保證用戶的移動成本在可接受范圍內(nèi)。

2.3 多類型任務分配轉(zhuǎn)化為最大權值問題

文獻[23]中將任務匹配轉(zhuǎn)化為最大權值問題，研究的是單一類型任務，二分圖的權值均為1。本文研究的是多類型任務分配問題，專業(yè)匹配分數(shù)為3，非專業(yè)匹配分數(shù)1，權值有所不同，將最大分數(shù)問題轉(zhuǎn)換為在二分圖中求最大權值問題。不妨先假設所有用戶最多只能接受一個任務，在時間實例si時，在線用戶集合為Wi={w1,w2,…,wn}，可分配的任務集合為Ti={t1,t2,…,tm}。在無向圖Gi=(V,E)中，如果任務tk在用戶wj的區(qū)域范圍內(nèi)，則有邊ej,k∈E連接這兩個頂點。將每個邊ej,k的權值賦予Score(wj,tk)，因此，q=1時最大分數(shù)實例問題就轉(zhuǎn)化為在帶權二分圖中求最大匹配問題了。

如圖3所示，當每個用戶的q=1時，圖2中的實例轉(zhuǎn)換的二分圖，其中專業(yè)匹配的權值為3，非專業(yè)匹配的權值為1。

當每個用戶至多能接受一個任務時，容易轉(zhuǎn)化為二分圖。當每個用戶q=1時，該如何將任務分配問題轉(zhuǎn)化為想要的二分圖問題。不妨用N個邏輯用戶來代替用戶wj，這些邏輯用戶只能接受一個任務，將q=1的二分圖Gi轉(zhuǎn)化Gi′。|Tj|表示在用戶wj區(qū)域的任務數(shù)，當1

如圖4所示，q=1時，用N個邏輯用戶來代替用戶wj，將Gi圖轉(zhuǎn)化為圖Gi′，用3個邏輯用戶表示用戶w1，2個邏輯用戶表示用戶w3。

將MSA實例問題轉(zhuǎn)化為在二分圖中求最大權的問題，可利用KM(Kuhn-Munkras)算法解決該問題。KM算法的輸入為一個矩陣|W|×|T|，矩陣中的值為對應的匹配分數(shù)。在每次實例分配時運用KM算法求出最大權值，得到每個用戶的任務。如上述例中，求出分配給每個用戶的任務為w1={t1,t2,t3}、w2={t7}、w3={t4,t6}，得到的最大權值為3×6=18。

圖4 q>1時二分圖Gi′

2.4 基于距離ε值分配算法

為了在用戶最近距離內(nèi)選擇ε個任務分配給用戶，這些任務與按照最大權值分配的任務不重合，在沒有專業(yè)匹配時，將距離用戶近的任務分配給用戶，既可以減少用戶的移動成本，又可以提高任務分配數(shù)量；在專業(yè)匹配距離較遠時，用戶通過調(diào)度執(zhí)行任務，無法在截止時間內(nèi)完成該專業(yè)匹配任務，此時可以選擇去完成一些非專業(yè)匹配任務。例如通過最大權值二分圖計算出w1={t1,t2,t3}，雖然可以得到最大分配分數(shù)，但是，任務t3距離很遠，若用戶不能在截止時間內(nèi)完成該任務，任務就失效。此時，不妨將距離較近的任務t5分配給用戶w1，雖然不是專業(yè)匹配，但是用戶也可以多完成一個任務，而且移動成本也較小，可以提高任務完成的數(shù)量。通過計算出每對匹配〈w,t〉的移動成本d(wj,tk)，將這些任務按照d(wj,tk)降序排序，從中選擇前ε個任務分配分配給用戶。

基于距離ε值分配算法具體過程如算法1所示。

算法1 基于距離ε值分配(ε-DA)算法。

輸入：用戶集合Wi，任務集合Ti，ε值。

輸出：Wi和Ti匹配的任務分配實例集Ii。

1)

for eachsi

2)

Construct a weighted bipartite graphGi′ byWiandTi

3)

each weight given aScore(wj,tk)

//給每個邊賦予權值

4)

Calculate the maximum weighted bipartite matching based on KM algorithm

//利用KM算法計算最大權值匹配

5)

Find the assignmentIibetweenWiandTi

6)

for each workerwjinWi

7)

Calculated(wj,tk) of each matching inwjregion by Euclidean distance

//計算每個匹配的移動成本

8)

Select the first someεtasks whosed(wj,tk) is minimum

//選擇移動成本小的ε個任務

9)

UpdateIiby addingεtasks

2.5 算法分析

在定義4中，假設專業(yè)匹配分數(shù)為3，非專業(yè)匹配分數(shù)為1，以下給出定理1及具體證明過程。

定理1 當專業(yè)匹配分數(shù)大于非專業(yè)匹配分數(shù)的兩倍時，最大分數(shù)分配就是最大專業(yè)匹配。

可通過反證法證明。首先，假設每個用戶最多能接受任務的數(shù)量q=1，MSA問題的最優(yōu)解為Mmax。如果在Mmax中存在一個未分配的專業(yè)匹配〈w,t〉，并且w和t不在其他專業(yè)匹配中，為了提高總分數(shù)，最多可以用兩個非專業(yè)匹配替換〈w,t〉。相反，若在Mmax中不存在未分配的專業(yè)匹配，那么在Mmax中專業(yè)匹配數(shù)量已是最大化。所以，當q=1且專業(yè)匹配分數(shù)大于非專業(yè)匹配分數(shù)的兩倍時，最大分數(shù)匹配就是最大專業(yè)匹配。當量q>1時，可通過2.3節(jié)中原理分解為n個q=1的邏輯用戶，同理可證明。

基于距離ε值分配算法的復雜度主要在于計算二分圖中最大權值(第4)行)，利用KM算法計算最大權值，時間復雜度可降低到O(n3)。選擇距離最小的前ε個任務(第6)～9)行)，時間復雜度為O(n2)，因此基于距離ε值分配算法的復雜度為O(n3)。與貪婪分配算法相比，可忽略不計增加的時間代價O(n2)。

3 任務調(diào)度

在上述任務分配過程中，雖然任務分配完成，但并不一定是最優(yōu)序列，這時，需要對當前任務序列進行調(diào)度，使得任務序列中，用戶在截止時間前以最短距離完成最多的任務。本文假設用戶到達任務位置便完成該任務，不考慮任務的具體執(zhí)行時間。

如圖5所示，一個任務調(diào)度實例，將用戶和任務分布在網(wǎng)格中，用戶每移動1個網(wǎng)格耗費1個時間單位，用戶w位于(6，5)處，假設該用戶只具備美發(fā)專業(yè)能力，最大能接受數(shù)量為4。每個任務如定義1中給出的截止時間，例如任務t1的截止時間為9。分配給用戶5個任務，將按照任務的截止時間合理規(guī)劃任務執(zhí)行次序。除了任務t2不是美發(fā)類服務，即非專業(yè)匹配任務；其他4個任務都是美發(fā)類服務，即專業(yè)匹配任務。

圖5 一個任務調(diào)度實例

3.1 分支定界調(diào)度算法

圖6中展示了基于分支定界最大分數(shù)調(diào)度的主要思想：用戶節(jié)點是樹的根節(jié)點，在每一層中根據(jù)候選集合擴展分支，并依據(jù)上下界進行排序，不斷遞歸直到找到一個可行的解決方案。當回溯到上一級時，若一個分支的上界小于當前最好解決方案或其他分支的下界，則修剪掉該分支。

3.1.1 候選任務集

對搜索樹的每個節(jié)點，候選任務集是指在下一層中有希望被擴展節(jié)點的集合。例如，圖6中的搜索樹，在第一層的任務t5節(jié)點，初始時它有4個分支{t1,t3,t4,t2}，但是只有任務t4和t2節(jié)點是有希望被擴展的節(jié)點，因為在用戶完成t5后，已經(jīng)過了任務t1和t3的截止時間，即任務t1和t3已失效。如果能夠知道每個節(jié)點的候選任務集，那么只需要擴展這些較小的任務集合，不必盲目地搜索所有分支。為了計算每個節(jié)點的候選任務集，需要遍歷其父節(jié)點的候選任務集合，并要保證可以在截至時間內(nèi)完成任務。算法2是計算候選集的偽代碼。

算法2 計算候選任務集CalculateCand(R,cand_R,t)。

輸入：當前任務序列R，當前候選集合cand_R，t∈cand_R是將被擴展的任務。

輸出：任務節(jié)點t候選集合cand_Rt。

1)

GetcurTaskand its arriving timecurTimeofR

2)

cand_Rt← ?

3)

for each taskt′∈cand_R,t′≠tdo

4)

ifcurTime+c(t,t′)≤d(t′) then

//檢查候選集中任務能否在截止時間內(nèi)完成

5)

Returncand_Rt

3.1.2 修剪策略

可以從候選集合中獲取該節(jié)點的上界，上界代表在該分支下能夠獲得的最大調(diào)度分數(shù)，通過上界對搜索樹進行修剪。以下給出節(jié)點R的上界ub_R計算公式：

定理2 假設知道當前最優(yōu)解的分數(shù)為curMax和當前分支節(jié)點R,若R的上界小于最優(yōu)解分數(shù)，即ub_R≤curMax，則可以將分支R修剪掉。

通過這個定理可知，節(jié)點的curMax越大，則修剪能力越強。如果能事先知道最優(yōu)解的分數(shù)curMax，那么可修剪掉更多的分支，然后找出最優(yōu)解中的調(diào)度次序；但由于實際情況中，并不能提前預知最優(yōu)解分數(shù)，因此按照上界的降序排列，優(yōu)先訪問上界大的。

3.2 最有前途分支啟發(fā)式算法

雖然基于分定定界思想的調(diào)度策略能夠得到精確的任務執(zhí)行次序，但是其時間和空間復雜度按照指數(shù)增長，難以適應真實的空間眾包應用對實時性的要求。在本節(jié)提出基于距離最近的算法——最有前途分支啟發(fā)式(MPBH)算法，在規(guī)定時間內(nèi)完成指定任務。

最有前途分支啟發(fā)式算法是在分支定界法基礎上進行改進，通過不斷迭代選擇最有前途的分支(即在同一層中該分支節(jié)點具有最大的上限)，選擇一個最大上限的分支，并一直按照這個分支搜索下去，只需要找到一個候選任務序列即停止。具體步驟如算法3所示。

算法3 最有前途分支啟發(fā)式算法。

輸入：已分配的任務集合S和用戶w。

輸出：任務調(diào)度序列R。

1)

R← ?

2)

cand_Rt←S

3)

whilecand_Ris not empty do

4)

for each taskt∈cand_Rdo

5)

cand_Rt←CalculateCand(R,cand_R,t)

6)

Calculateub_Rt

7)

end for

8)

Sortcand_Rin descending order ofub_Rt, prune branches based onub

9)

t← task with the largestubincand_R

//選擇上限最大的分支節(jié)點

10)

R←R∪{t}

11)

cand_R←cand_Rt

12)

end while

13)

returnR

對于上面的算法分析：相對于精確的分支定界思想調(diào)度策略，最有前途分支近似算法的復雜度要小得多，只需要搜索一個最優(yōu)希望的分支即可，因此，空間復雜度為O(n)，在每次候選集的選擇中，都要選擇一個上界更大的，所以時間復雜度在最壞情況下為O(n2)。

4 實驗驗證與分析

4.1 實驗環(huán)境

為了觀察多類型任務分配與調(diào)度方法的執(zhí)行效率，本文通過Matlab仿真平臺進行仿真實驗。

實驗分別在真實數(shù)據(jù)和人工合成數(shù)據(jù)下進行。對于人工合成數(shù)據(jù)的生成，任務的截止時間d生成如下：從用戶的位置，貪婪地選擇下一個距離最近的一組任務組成一個任務序列，計算總的移動成本作為截止時間上界du(下界dl=du-0.1)。任務截止時間從均勻分布[dl,du]中產(chǎn)生，基本上范圍[dl,du]確定可以完成的任務的百分比，較小的范圍意味著任務的期限更緊。實驗中人工合成數(shù)據(jù)，如表1，其中W/T表示對于一個給定的任務，用戶區(qū)域包含該任務的平均用戶數(shù)量。

表1 人工合成實驗數(shù)據(jù)

對于真實數(shù)據(jù)，從現(xiàn)有的基于地理位置應用平臺Yelp[31]中導出一些數(shù)據(jù)，2014年10月的數(shù)據(jù)。假設商戶作為空間任務，Yelp中的用戶作為空間眾包參與者，用戶點評一個商戶就相當于在商戶位置完成一個空間任務。商戶的類別就是任務類型，用戶具有的專業(yè)技能從這些任務類型中隨機分配。任務最后期限是點評的完成時間，每個任務的處理時間是5 min。真實數(shù)據(jù)具體如表2所示。

表2 真實實驗數(shù)據(jù)

4.2 空間任務分配算法的實驗分析

實驗中將現(xiàn)有的貪婪分配(Greedy)算法、最小區(qū)域熵優(yōu)先(Least Location Entropy Priority, LLEP)算法與本文提出的基于距離ε值分配(ε-DA)算法進行比較，分別從三個維度比較分配算法的性能，包括總的分配分數(shù)、專業(yè)匹配任務數(shù)以及移動成本，對于每個實驗跑50例，并報告結果的平均值。

4.2.1 關于ε值的討論

ε值對ε-DA算法的影響如圖7所示：隨著ε值的增加，總分數(shù)和專業(yè)匹配任務數(shù)也增長。在ε≤10時增長較快，因為隨著ε值增加，有一部分距離較近的專業(yè)匹配任務得到分配，使得分數(shù)增加較快；在ε>10時增長較緩慢，因為大部分任務分配出去了，剩余的專業(yè)匹配任務越來越少。隨著ε值的增加，移動成本也在增長：在ε≤10時增長緩慢，是由于多選擇的這部分任務距離用戶較近，所以對移動成本影響不大；但是當ε>10時，移動成本增加較快，因為距離較遠的任務也被分配了，使得總的移動成本不斷增加，而且增速較快。由此看見，合適的ε值對總分數(shù)、專業(yè)匹配任務數(shù)以及移動成本影響較大，合理的ε取值很重要。

4.2.2 基于人工合成數(shù)據(jù)的實驗

分別從任務規(guī)模W/T和用戶區(qū)域約束條件D，驗證對算法性能的影響。實驗中ε值默認為10。

1)參數(shù)W/T的影響。實驗結果如圖8所示，圖8(a)、(b)中，隨著W/T變大，總分數(shù)和專業(yè)匹配分數(shù)都增加，因為隨著W/T變大，可以匹配任務的用戶越來越多。圖8(a)中，實驗結果表明，ε-DA算法比Greedy算法以及LLEP算法在總分配分數(shù)上表現(xiàn)得更好，其中比Greedy算法提升了接近30%，是由于ε-DA算法每次多選取部分任務，以獲得較高的總的匹配分數(shù)。圖8(b)中，ε-DA算法比Greedy算法以及LLEP算法獲得更多的專業(yè)匹配任務。圖8(c)中，雖然ε-DA算法每次多選取了部分任務，但是移動成本并沒有增加過多，原因是多選擇的這部分任務是距離用戶最近的。而LLEP算法優(yōu)先選擇處于稀疏區(qū)域的任務，每次移動成本均較大。由此可見，隨著W/T增加，ε-DA算法能夠提高總的匹配分數(shù)，即在最大分數(shù)分配上表現(xiàn)得最好，能夠獲得更多的專業(yè)匹配任務，并且維持移動成本較小幅度的增加。

2)用戶區(qū)域約束條件D的影響。用戶有兩個約束條件：最大能接受任務數(shù)q和用戶區(qū)域范圍D，兩個約束條件相似，只列出約束條件D的影響。實驗結果如圖9中所示，在圖9(a)中，隨著用戶區(qū)域范圍D擴大，總的分配分數(shù)也增加，在圖9(b)中，隨著用戶區(qū)域范圍D擴大，移動成本也增加，是由于范圍D擴大，距離較遠的任務也能被分配出去，導致移動成本增加。由此可見，相對其他算法，隨著范圍D的擴大，ε-DA可以提高總的分配分數(shù)，同時移動成本并未劇烈增加。

圖7 ε對3種約束條件的影響

圖8 W/T對3種約束條件的影響

圖9 D對兩種約束條件的影響

4.2.3 基于真實數(shù)據(jù)的實驗

在真實數(shù)據(jù)中對算法的性能進行測試，將本文提出的ε-DA算法、Greedy算法與LLEP算法進行比較。如圖10所示，對比當W/T=50時3種算法的表現(xiàn)。從圖10(a)～(b)實驗結果表明，ε-DA算法在總分配分數(shù)上和專業(yè)匹配數(shù)上均比Greedy算法和LLEP算法表現(xiàn)得好，在專業(yè)匹配數(shù)上，ε-DA算法比Greedy算法提高了35%，比LLEP算法提高了11%。移動成本ε-DA算法比Greedy算法增加了9%，比LLEP算法減小7%。

5 結語

本文對已有的工作深入研究，從空間眾包中任務的多樣性入手，根據(jù)空間任務的時空屬性，在貪婪分配算法基礎上進行改進，提出基于距離ε值分配算法，為任務調(diào)度提供合適的任務。采用分支定界思想對任務進行路徑規(guī)劃，在此基礎上進行改進，提出最有前途分支啟發(fā)式算法。實驗中對任務的分配進行了驗證，本文提出的任務分配和調(diào)度方法，能夠有效地提高尋找最佳任務序列的效率，并同時提高任務完成的質(zhì)量及數(shù)量。

圖10 3種算法在不同約束條件下的比較(W/T=50)

References)

[1] SCHEE B A V. Crowdsourcing: why the power of the crowd is driving the future of business [J]. American Journal of Health-System Pharmacy, 2010, 67(4): 1565-1566.

[2] MUSTHAG M, GANESAN D. Labor dynamics in a mobile micro-task market [C]// Proceedings of the 2013 SIGCHI Conference on Human Factors in Computing Systems. New York: ACM, 2013: 641-650.

[3] DOAN A H, FRANKLIN M J, KOSSMANN D, et al. Crowdsourcing applications and platforms: a data management perspective [J]. Proceedings of the VLDB Endowment, 2011, 4(12): 1508-1509.

[4] DEUTCH D, MILO T. Mob data sourcing [C]// Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 581-584.

[5] KAZAI G, KAMPS J, MILIC-FRAYLING N. Worker types and personality traits in crowdsourcing relevance labels [C]// Proceedings of the 20th ACM Conference on Information and Knowledge Management. New York: ACM, 2011: 1941-1944.

[6] CHEN L, LEE D, MILO T. Data-driven crowdsourcing: management, mining, and applications [C]// Proceedings of the 2015 IEEE 31st International Conference on Data Engineering. Piscataway, NJ: IEEE, 2015: 1527-1529.

[7] HOWE J. The rise of crowdsourcing [J]. Wired Magazine, 2006, 14(6): 1-5.

[8] 馮劍紅,李國良,馮建華.眾包技術研究綜述[J].計算機學報,2015,38(9):1713-1726.(FENG J H, LI G L, FENG J H. Summary of crowdsourcing technology research [J]. Chinese Journal of Computers, 2015, 38(9): 1713-1726.)

[9] WONG C W, TAO Y, FU W C, et al. On efficient spatial matching [C]// Proceedings of the 33rd International Conference on Very Large Data Bases. [S.l.]: VLDB Endowment, 2007: 579-590.

[10] LEONG H U, MAN L Y, MOURATIDIS K, et al. Capacity constrained assignment in spatial databases [C]// Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2008: 15-28.

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

[12] TONG Y, SHE J, DING B, et al. Online minimum matching in real-time spatial data: experiments and analysis [J]. Proceedings of the VLDB Endowment, 2016, 9(12): 1053-1064.

[13] HO C J, VAUGHAN J W. Online task assignment in crowdsourcing markets [C]// Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. Menlo Park, CA: AAAI Press, 2013: 45-51.

[14] HO C J, JABBARI S, VAUGHAN A J W. Adaptive task assignment for crowdsourced classification [C]// Proceedings of the 30th International Conference on Machine Learning. Atlanta: ICML, 2013: 534-542.

[15] KARGER D R, OH S, SHAH D. Budget-optimal task allocation for reliable crowdsourcing systems [J]. Operations Research, 2011, 62(1): 1-24.

[16] KAZEMI L, SHAHABI C. GeoCrowd: enabling query answering with spatial crowdsourcing [C]// Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 189-198.

[17] TO H, FAN L, LUAN T, et al. Real-time task assignment in hyperlocal spatial crowdsourcing under budget constraints [C]// Proceedings of the 2016 IEEE International Conference on Pervasive Computing and Communications. Piscataway, NJ: IEEE, 2016: 1-8.

[18] DANG H, NGUYEN T, TO H. Maximum complex task assignment: towards tasks correlation in spatial crowdsourcing [C]// Proceedings of the 2013 International Conference on Information Integration and Web-based Applications & Services. New York: ACM, 2013: 77-81.

[19] GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness [M]. New York: W. H. Freeman, 1990: 11-13.

[20] VANSTEENWEGENAABA P. The orienteering problem: a survey [J]. European Journal of Operational Research, 2011, 209(1): 1-10.

[21] LI Y, YIU M L, XU W. Oriented online route recommendation for spatial crowdsourcing task workers [C]// Proceedings of the 14th International Conference on Advances in Spatial and Temporal Databases. New York: ACM, 2015: 137-156.

[22] DENG D, SHAHABI C, DEMIRYUREK U. Maximizing the number of worker’s self-selected tasks in spatial crowdsourcing [C]// Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2013: 324-333.

[23] DENG D, SHAHABI C, ZHU L. Task matching and scheduling for multiple workers in spatial crowdsourcing [C]// Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2015: Article No. 21.

[24] IPEIROTIS P G, PROVOST F, WANG J. Quality management on Amazon Mechanical Turk [C]// Proceedings of the 2010 ACM SIGKDD Workshop on Human Computation. New York: ACM, 2010: 64-67.

[25] LIU X, LU M, OOI B C, et al. CDAS: a crowdsourcing data analytics system [J]. Proceedings of the VLDB Endowment, 2012, 5(10): 1040-1051.

[26] CAO C C, SHE J, TONG Y, et al. Whom to ask?: jury selection for decision making tasks on micro-blog services [J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1495-1506.

[27] CAO C C, TONG Y, CHEN L, et al. WiseMarket: a new paradigm for managing wisdom of online social users [C]// Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2013: 455-463.

[28] GAO J, LIU X, OOI B C, et al. An online cost sensitive decision-making method in crowdsourcing systems [C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2013: 217-228.

[29] KAZEMI L, SHAHABI C, CHEN L. GeoTruCrowd: trustworthy query answering with spatial crowdsourcing [C]// Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2013: 314-323.

[30] TO H, SHAHABI C, KAZEMI L. A server-assigned spatial crowdsourcing framework [J]. ACM Transactions on Spatial Algorithms & Systems, 2015, 1(1): Article No. 2.

[31] Yelp Inc. Yelp dataset [EB/OL]. [2017- 03- 20]. http://www.yelp.com/dataset challenge/.

This work is partially supported by the National Natural Science Foundation of China (U1301252), the National Key Technology R&D Program (2013BAB06B04), the National Key R&D Program of China (2016YFC0400910), the National Science and Technology Major Project (2017ZX07104- 001), the Fundamental Research Funds for the Central Universities (2015B22214).

MAOYingchi, born in 1976, Ph. D., associate professor. Her research interests include distributed computing, parallel processing, distributed data management.

MUChao, born in 1993, M. S. candidate. His research interests include distributed computing.

BAOWei, born in 1990, M. S. candidate. His research interests include distributed computing.

LIXiaofang, born in 1972, Ph. D., associate professor. Her research interests include distributed computing.