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

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

0 引言

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

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

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

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

1 研究現(xiàn)狀

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

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

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

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

2 多類(lèi)型任務(wù)分配

2.1 問(wèn)題模式

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

圖1 空間眾包組成

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

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

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

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

圖2 一個(gè)用戶(hù)任務(wù)分布實(shí)例

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

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

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

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

2.2 解決問(wèn)題思路

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

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

2.3 多類(lèi)型任務(wù)分配轉(zhuǎn)化為最大權(quán)值問(wèn)題

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

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

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

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

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

圖4 q>1時(shí)二分圖Gi′

2.4 基于距離ε值分配算法

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

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

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

輸入：用戶(hù)集合Wi，任務(wù)集合Ti，ε值。

輸出：Wi和Ti匹配的任務(wù)分配實(shí)例集Ii。

1)

for eachsi

2)

Construct a weighted bipartite graphGi′ byWiandTi

3)

each weight given aScore(wj,tk)

//給每個(gè)邊賦予權(quán)值

4)

Calculate the maximum weighted bipartite matching based on KM algorithm

//利用KM算法計(jì)算最大權(quán)值匹配

5)

Find the assignmentIibetweenWiandTi

6)

for each workerwjinWi

7)

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

//計(jì)算每個(gè)匹配的移動(dòng)成本

8)

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

//選擇移動(dòng)成本小的ε個(gè)任務(wù)

9)

UpdateIiby addingεtasks

2.5 算法分析

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

定理1 當(dāng)專(zhuān)業(yè)匹配分?jǐn)?shù)大于非專(zhuān)業(yè)匹配分?jǐn)?shù)的兩倍時(shí)，最大分?jǐn)?shù)分配就是最大專(zhuān)業(yè)匹配。

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

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

3 任務(wù)調(diào)度

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

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

圖5 一個(gè)任務(wù)調(diào)度實(shí)例

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

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

3.1.1 候選任務(wù)集

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

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

輸入：當(dāng)前任務(wù)序列R，當(dāng)前候選集合cand_R，t∈cand_R是將被擴(kuò)展的任務(wù)。

輸出：任務(wù)節(jié)點(diǎn)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

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

5)

Returncand_Rt

3.1.2 修剪策略

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

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

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

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

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

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

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

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

輸出：任務(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é)點(diǎn)

10)

R←R∪{t}

11)

cand_R←cand_Rt

12)

end while

13)

returnR

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

4 實(shí)驗(yàn)驗(yàn)證與分析

4.1 實(shí)驗(yàn)環(huán)境

為了觀察多類(lèi)型任務(wù)分配與調(diào)度方法的執(zhí)行效率，本文通過(guò)Matlab仿真平臺(tái)進(jìn)行仿真實(shí)驗(yàn)。

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

表1 人工合成實(shí)驗(yàn)數(shù)據(jù)

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

表2 真實(shí)實(shí)驗(yàn)數(shù)據(jù)

4.2 空間任務(wù)分配算法的實(shí)驗(yàn)分析

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

4.2.1 關(guān)于ε值的討論

ε值對(duì)ε-DA算法的影響如圖7所示：隨著ε值的增加，總分?jǐn)?shù)和專(zhuān)業(yè)匹配任務(wù)數(shù)也增長(zhǎng)。在ε≤10時(shí)增長(zhǎng)較快，因?yàn)殡S著ε值增加，有一部分距離較近的專(zhuān)業(yè)匹配任務(wù)得到分配，使得分?jǐn)?shù)增加較快；在ε>10時(shí)增長(zhǎng)較緩慢，因?yàn)榇蟛糠秩蝿?wù)分配出去了，剩余的專(zhuān)業(yè)匹配任務(wù)越來(lái)越少。隨著ε值的增加，移動(dòng)成本也在增長(zhǎng)：在ε≤10時(shí)增長(zhǎng)緩慢，是由于多選擇的這部分任務(wù)距離用戶(hù)較近，所以對(duì)移動(dòng)成本影響不大；但是當(dāng)ε>10時(shí)，移動(dòng)成本增加較快，因?yàn)榫嚯x較遠(yuǎn)的任務(wù)也被分配了，使得總的移動(dòng)成本不斷增加，而且增速較快。由此看見(jiàn)，合適的ε值對(duì)總分?jǐn)?shù)、專(zhuān)業(yè)匹配任務(wù)數(shù)以及移動(dòng)成本影響較大，合理的ε取值很重要。

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

分別從任務(wù)規(guī)模W/T和用戶(hù)區(qū)域約束條件D，驗(yàn)證對(duì)算法性能的影響。實(shí)驗(yàn)中ε值默認(rèn)為10。

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

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

圖7 ε對(duì)3種約束條件的影響

圖8 W/T對(duì)3種約束條件的影響

圖9 D對(duì)兩種約束條件的影響

4.2.3 基于真實(shí)數(shù)據(jù)的實(shí)驗(yàn)

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

5 結(jié)語(yǔ)

本文對(duì)已有的工作深入研究，從空間眾包中任務(wù)的多樣性入手，根據(jù)空間任務(wù)的時(shí)空屬性，在貪婪分配算法基礎(chǔ)上進(jìn)行改進(jìn)，提出基于距離ε值分配算法，為任務(wù)調(diào)度提供合適的任務(wù)。采用分支定界思想對(duì)任務(wù)進(jìn)行路徑規(guī)劃，在此基礎(chǔ)上進(jìn)行改進(jìn)，提出最有前途分支啟發(fā)式算法。實(shí)驗(yàn)中對(duì)任務(wù)的分配進(jìn)行了驗(yàn)證，本文提出的任務(wù)分配和調(diào)度方法，能夠有效地提高尋找最佳任務(wù)序列的效率，并同時(shí)提高任務(wù)完成的質(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] 馮劍紅,李國(guó)良,馮建華.眾包技術(shù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào),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.