林薈薈,黃 杰,李 玉,萬 健

(1.浙江科技學(xué)院 信息與電子工程學(xué)院,杭州 310023;2.杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院,杭州 310018)

隨著移動(dòng)網(wǎng)絡(luò)的發(fā)展和移動(dòng)設(shè)備的普及,空間眾包越來越受到人們的關(guān)注[1],任務(wù)分配問題是空間眾包的核心問題[2-4]。目前學(xué)術(shù)界主要討論如何將任務(wù)高效地分配給任務(wù)執(zhí)行者,同時(shí)對(duì)其分配的優(yōu)化目標(biāo)主要為最大化整體任務(wù)分配數(shù)量[5-6]。Hien等[7]擴(kuò)展了分配模型,為每個(gè)任務(wù)執(zhí)行者-任務(wù)對(duì)設(shè)置權(quán)重,并以最大化總?cè)蝿?wù)分配權(quán)重為目標(biāo)。但是現(xiàn)實(shí)中任務(wù)執(zhí)行者和任務(wù)是動(dòng)態(tài)變化的,該模型仍然無法實(shí)現(xiàn)在整個(gè)時(shí)間線上最大化任務(wù)分配數(shù)量的目標(biāo)。Chen等[8]提出一種基于預(yù)測的任務(wù)分配算法,然后用貪心算法最大化當(dāng)前與未來的任務(wù)分配數(shù)量。但通過采樣的方式進(jìn)行預(yù)測,在時(shí)間和空間上預(yù)測準(zhǔn)確度不高。

以上研究都是基于平臺(tái)分配任務(wù),任務(wù)執(zhí)行者保證執(zhí)行空間眾包任務(wù)。但現(xiàn)實(shí)中每個(gè)任務(wù)執(zhí)行者對(duì)任務(wù)的選擇具有主觀性,任務(wù)執(zhí)行者都希望能執(zhí)行符合他們意愿的任務(wù),比如在自己所處位置附近[9]、任務(wù)報(bào)酬高[10]的任務(wù),或是與自己的知識(shí)、技能相匹配的任務(wù)[11]。Zheng等[12]首次定義有拒絕的空間眾包問題,提出4種近似分配算法來提高分配的效率,但采用的是靜態(tài)分配的方法得到最優(yōu)分配。本研究基于平臺(tái)分配任務(wù)的方式(server assigned tasks,SAT)[13-14]探討空間眾包中任務(wù)執(zhí)行者可拒絕情況下的在線任務(wù)分配問題[15],實(shí)現(xiàn)提出動(dòng)態(tài)可拒絕的空間眾包處理方法:首先最大化任務(wù)分配數(shù)量,即實(shí)現(xiàn)最大匹配;然后,針對(duì)任務(wù)執(zhí)行者的主觀性,為減少任務(wù)執(zhí)行者拒絕的概率,尋找全局最大匹配下最高興趣度分配方案。

1 問題定義與處理方法

現(xiàn)有研究[16]已證明空間眾包全局最優(yōu)任務(wù)分配是非確定性多項(xiàng)式難題(non-deterministic polynomialhard,NP-hard)。利用批處理模式解決空間眾包中任務(wù)執(zhí)行者可拒絕情況下的在線任務(wù)分配問題,給定集合p={1,2,3,…}表示整個(gè)時(shí)間段,其中每個(gè)時(shí)間片p上存在不同的任務(wù)執(zhí)行者和任務(wù)集合,并且在每個(gè)時(shí)間片內(nèi)的任務(wù)執(zhí)行者和任務(wù)信息均為已知。

1.1 動(dòng)態(tài)移動(dòng)的任務(wù)執(zhí)行者

假設(shè)集合Wp={w1,w2,…,wm}是在某時(shí)間片上m個(gè)移動(dòng)任務(wù)執(zhí)行者的集合,wi∈Wp是其中一名任務(wù)執(zhí)行者,可形式化定義為wi=〈li,pij,ri〉(1

1.2 有約束的任務(wù)

假設(shè)集合Tp={t1,t2,…,tn}是在某時(shí)間片上n個(gè)有時(shí)間、位置約束的任務(wù)集合,tj∈Tp是其中一個(gè)任務(wù),可形式化定義為tj=〈sj,lj,dj,mj,bj〉(1

1.3 最大匹配下最高興趣度問題

給定任務(wù)執(zhí)行者集合W和任務(wù)集合T,在任意時(shí)間片上有m個(gè)任務(wù)執(zhí)行者,n個(gè)任務(wù)。滿足時(shí)間、空間約束條件下,任務(wù)執(zhí)行者wi對(duì)空間任務(wù)tj有興趣,興趣度權(quán)重為pij,任務(wù)執(zhí)行者-任務(wù)分布圖如圖1(a)所示。圖1(b)表示任務(wù)執(zhí)行者和任務(wù)的待分配情況,每個(gè)任務(wù)執(zhí)行者、每個(gè)任務(wù)表示為二分圖中的兩邊頂點(diǎn),其中任務(wù)執(zhí)行者和任務(wù)的頂點(diǎn)類型不同。任務(wù)執(zhí)行者頂點(diǎn)wi和空間任務(wù)頂點(diǎn)tj之間存在一條邊,如此,任務(wù)執(zhí)行者-任務(wù)對(duì)〈wi,tj〉是有效的。

圖1 任務(wù)執(zhí)行者-任務(wù)分布圖和二分圖Fig.1 Executor-task distribution and bipartite graph

定義1任務(wù)分配數(shù)量:在一個(gè)時(shí)間段內(nèi)有任務(wù)執(zhí)行者集合W和任務(wù)集合T,任務(wù)分配策略要求被分配執(zhí)行的任務(wù)數(shù)量最大。

定義2任務(wù)分配興趣度:假設(shè)任務(wù)tj分配給任務(wù)執(zhí)行者wi,則pij為有效分配興趣度,任務(wù)分配策略要求在任務(wù)最大化分配的情況下,分配興趣度最大。

1.4 動(dòng)態(tài)可拒絕的空間眾包處理方法

本研究提出的動(dòng)態(tài)可拒絕空間眾包處理方法如圖2所示。任務(wù)執(zhí)行者和任務(wù)動(dòng)態(tài)提交信息至空間眾包平臺(tái),平臺(tái)首先劃分時(shí)間片,查看時(shí)間片內(nèi)的任務(wù)與任務(wù)執(zhí)行者是否滿足時(shí)間和空間約束,為降低任務(wù)執(zhí)行者拒絕的可能性,計(jì)算任務(wù)執(zhí)行者-任務(wù)對(duì)興趣度,再使用分配算法進(jìn)行任務(wù)分配。若任務(wù)分配成功,則將分配策略發(fā)送給任務(wù)執(zhí)行者讓其執(zhí)行;若分配失敗,當(dāng)前時(shí)間片內(nèi)未分配任務(wù)的執(zhí)行者和未分配的任務(wù)將與下一時(shí)間片內(nèi)任務(wù)執(zhí)行者和任務(wù)一起等待下一次任務(wù)分配。

圖2 動(dòng)態(tài)可拒絕空間眾包處理方法Fig.2 Dynamic rejectable spatial crowdsourcing framework

2 動(dòng)態(tài)可拒絕的空間眾包分配方法

2.1 興趣度預(yù)測

利用主成分分析法(principal components analysis,PCA)[17]預(yù)測任務(wù)執(zhí)行者對(duì)任務(wù)的興趣度。首先構(gòu)建興趣度計(jì)算指標(biāo)體系,將任務(wù)執(zhí)行者和任務(wù)之間的距離[18]作為負(fù)向指標(biāo),將任務(wù)移動(dòng)距離[19]、任務(wù)時(shí)長[19]、任務(wù)價(jià)格[20]作為正向指標(biāo);然后構(gòu)建初始化矩陣,歸一化處理后得到標(biāo)準(zhǔn)化矩陣;繼而計(jì)算標(biāo)準(zhǔn)化矩陣得到相關(guān)系數(shù)矩陣,并計(jì)算對(duì)應(yīng)的特征值、特征向量;接著計(jì)算每個(gè)主成分的方差貢獻(xiàn)率,確定主成分個(gè)數(shù);最后確定主要評(píng)估指標(biāo)的權(quán)重,并進(jìn)行歸一化修正,得到任務(wù)執(zhí)行者對(duì)任務(wù)的興趣度。具體計(jì)算過程如下:

計(jì)算每個(gè)主成分的方差貢獻(xiàn)率v,va=λa/(λ1+λ2+…+λp),a為正整數(shù),1≤a≤p,va表示第a個(gè)主成分的方差貢獻(xiàn)率,λa表示第a個(gè)主成分對(duì)應(yīng)的特征值。

按照特征值大于1、累計(jì)方差貢獻(xiàn)率大于指定0.85的原則,提取滿足條件的特征值個(gè)數(shù)作為最終選擇的主成分個(gè)數(shù);如果滿足條件的特征值個(gè)數(shù)為b,選擇b個(gè)主成分,λ1,λ2,…,λb為b個(gè)主成分分別對(duì)應(yīng)的特征值,其分別對(duì)應(yīng)的特征向量e1,e2,…,eb為b個(gè)主成分的特征向量,特征向量和標(biāo)準(zhǔn)化后的數(shù)據(jù)相乘,得到主成分的線性表達(dá)式:

Yc=ec1Z1+ec2Z2+…+ecpZp。

(1)

式(1)中:Yc為第c個(gè)主成分,c為正整數(shù),1≤c≤b;ecp為某個(gè)指標(biāo)在第c個(gè)主成分線性表達(dá)式中的系數(shù),表示第c個(gè)特征向量中的第p個(gè)元素;Zp為第p個(gè)指標(biāo)經(jīng)過標(biāo)準(zhǔn)化處理后的值。

以主成分的方差貢獻(xiàn)率為權(quán)重,對(duì)主要評(píng)估指標(biāo)在各個(gè)主成分線性表達(dá)式中的系數(shù)進(jìn)行加權(quán)平均,計(jì)算每個(gè)主要評(píng)估指標(biāo)的綜合權(quán)重;將所有主要評(píng)估指標(biāo)的綜合權(quán)重進(jìn)行歸一化,得到每個(gè)主要評(píng)估指標(biāo)的權(quán)重值w′,w′j表示第j個(gè)主要評(píng)估指標(biāo)的綜合權(quán)重除以所有主要評(píng)估指標(biāo)的綜合權(quán)重之和,根據(jù)獲得的權(quán)重值進(jìn)行加權(quán)計(jì)算,得到每個(gè)任務(wù)執(zhí)行者的興趣度并映射到[0,1]之間。

2.2 動(dòng)態(tài)分配算法

Hamamda等[21]驗(yàn)證了批處理模式在任務(wù)分配上的有效性,故本研究采用批處理的模式解決動(dòng)態(tài)分配問題。

2.2.1 基于MaxFlow的排序算法

采用基于MaxFlow的排序算法(sequence algorithm base on MaxFlow,SMF)求解分配策略。建立一個(gè)額外的源點(diǎn)Start和一個(gè)額外的匯點(diǎn)End,源點(diǎn)與頂點(diǎn)連接一條容量c為1、權(quán)重為0的弧,匯點(diǎn)也執(zhí)行類似的操作;兩邊頂點(diǎn)任務(wù)執(zhí)行者wi和任務(wù)tj的弧容量c設(shè)置為1,權(quán)重設(shè)置為興趣度pi,j∈[0,1];完成網(wǎng)絡(luò)G=(V,E,C,p)構(gòu)建。

通過增廣路算法來求得該網(wǎng)絡(luò)的最大流量。該算法優(yōu)點(diǎn)是每次調(diào)整流量都遵循最短路徑的原則,直到找不到增廣路,此時(shí)的總流量和興趣度分?jǐn)?shù)即為所求答案。但是在尋找最大興趣度增廣路的時(shí)候需先求出最短路徑,已知增流到最后的流量n={min(|Wp|,|Tp|)},針對(duì)有多條弧的權(quán)重為0的特性,只需對(duì)二分圖中的權(quán)重按照從小到大的順序排列,再根據(jù)排序作為有向路徑增流[22]至n值或不存在可增廣路為止,如此就找到最小興趣差最大流路徑,轉(zhuǎn)換后也就是找到最大興趣度最大流路徑。

2.2.2 基于KM的不重復(fù)構(gòu)造交替樹算法

實(shí)際構(gòu)建二分圖的時(shí)候,任務(wù)執(zhí)行者與任務(wù)數(shù)不一定相同。若兩邊頂點(diǎn)數(shù)不一致時(shí),補(bǔ)齊較少邊的集合,并將其權(quán)重設(shè)為0。傳統(tǒng)KM算法(Kuhn-Munkres,KM)可求解最大匹配最高興趣度問題,通過不斷修改可行頂標(biāo)得到相等子圖進(jìn)行增廣路探索,直到找到最大匹配為止。一般對(duì)其優(yōu)化都是給每個(gè)右頂點(diǎn)加一個(gè)“松弛量”函數(shù)s,每次開始尋找增廣路時(shí)初始化為無窮大。在尋找增廣路時(shí),檢查任務(wù)執(zhí)行者wi和任務(wù)tj的邊,如果不在相等子圖中,讓s[j]=min{s[j],lw[i]+lt[j]-p[i][j]}。這樣在修改頂標(biāo)時(shí),取所有不在交錯(cuò)樹中的任務(wù)集頂點(diǎn)的s值中的最小值作為d值即可。但是每輪匹配過的頂點(diǎn)會(huì)被清除,需要重新開始搜索建立交替樹。

本文提出基于KM的不重復(fù)構(gòu)造交替樹算法(non-repetitive construction of alternating tree algorithm based on KM,NR-KM),在原來樹的基礎(chǔ)上接著搜索新加入的邊。設(shè)頂點(diǎn)wi的頂標(biāo)為lw[i],頂點(diǎn)tj的頂標(biāo)為lt[j],頂點(diǎn)wi與tj之間的權(quán)重為p[i][j]。定義s[i]為原值和lw[i]+lt[j]-p[i][j]的較小值,取所有不在交錯(cuò)樹中的s[i]值作為d。每次減掉d后,s變?yōu)?的點(diǎn)肯定有新加入的邊,所以不重新搜索原來的樹,從這些點(diǎn)開始接著原樹搜索,直到交錯(cuò)樹擴(kuò)展到存在增廣路為止。

3 試驗(yàn)結(jié)果與分析

使用滴滴蓋亞數(shù)據(jù)計(jì)劃[23]中西安二環(huán)局部區(qū)域的滴滴快專車平臺(tái)的訂單司機(jī)軌跡數(shù)據(jù)。在數(shù)據(jù)中選取的事件發(fā)生在東經(jīng)108.921 859°～109.009 348°,北緯34.204 946°～34.279 936°,軌跡點(diǎn)的采集間隔是2～4 s,軌跡點(diǎn)經(jīng)過綁路處理,以保證數(shù)據(jù)都能夠?qū)?yīng)到實(shí)際的道路信息。采用某一天滴滴快專車平臺(tái)的訂單司機(jī)軌跡數(shù)據(jù),有119 019個(gè)訂單,共涉及178 56個(gè)任務(wù)執(zhí)行者。在試驗(yàn)研究中,由于任務(wù)執(zhí)行者和任務(wù)有屬性約束,需補(bǔ)充數(shù)據(jù)集屬性。通過原始真實(shí)數(shù)據(jù)集計(jì)算出任務(wù)時(shí)長(unix時(shí)間戳形式)、任務(wù)移動(dòng)距離(換算成兩地之間的距離);根據(jù)滴滴快車訂單計(jì)價(jià)規(guī)則,計(jì)算任務(wù)價(jià)格。

試驗(yàn)主要考慮時(shí)間片p和任務(wù)執(zhí)行者可達(dá)范圍r對(duì)任務(wù)分配算法的影響。時(shí)間片范圍的設(shè)定在一定程度上影響該時(shí)間片內(nèi)任務(wù)執(zhí)行者與任務(wù)的數(shù)量,間接影響分配結(jié)果;任務(wù)執(zhí)行者可達(dá)范圍直接影響任務(wù)能否被任務(wù)執(zhí)行者執(zhí)行,決定任務(wù)執(zhí)行者-任務(wù)有效對(duì)的數(shù)量,影響分配結(jié)果。本研究設(shè)置的試驗(yàn)參數(shù)見表1(參數(shù)數(shù)值加粗的為默認(rèn)值),對(duì)每個(gè)參數(shù)變化的結(jié)果都進(jìn)行50組的試驗(yàn),取50組試驗(yàn)結(jié)果的平均值。所有試驗(yàn)均在一臺(tái)處理器為Intel(R)Core(TM)i7-7700,CPU為3.60 GHz,內(nèi)存為16 GB的計(jì)算機(jī)上進(jìn)行。

表1 試驗(yàn)參數(shù)Table 1 Experimental parameters

為了評(píng)估任務(wù)分配算法的性能,用3個(gè)指標(biāo)來對(duì)比貪心算法(greedy algroithm,GA)、KM算法和我們提出的SMF和NR-KM算法。3個(gè)指標(biāo)為:1)CPU時(shí)間成本,即整個(gè)時(shí)間段內(nèi)任務(wù)分配的CPU時(shí)間成本;2)任務(wù)分配數(shù)量,即整個(gè)時(shí)間段內(nèi)任務(wù)分配的數(shù)量;3)任務(wù)分配興趣度,即在整個(gè)時(shí)間段內(nèi)任務(wù)分配興趣度之和。

在默認(rèn)參數(shù)的情況下,4種分配策略的性能比較見表2。GA算法得到整個(gè)時(shí)間段內(nèi)分配近似解,沒能從全局考慮得到最優(yōu)解;SMF算法、KM算法和NR-KM算法得到的任務(wù)分配數(shù)量和興趣度分?jǐn)?shù)是相同的。NR-KM算法時(shí)間效率最優(yōu),相比SMF算法速度提高9%,由于重標(biāo)號(hào)每次對(duì)一個(gè)邊進(jìn)行掃描操作,而SMF算法需要維護(hù)標(biāo)號(hào)和隊(duì)列操作;NR-KM算法因不需要每次重新構(gòu)建交錯(cuò)樹,相比KM算法分配速度平均快11%。

表2 4種分配策略的性能比較Table 2 Performance comparison of four allocation strategies

時(shí)間片大小對(duì)算法分配時(shí)間效率的影響如圖3(a)所示,在任務(wù)執(zhí)行者可達(dá)范圍為默認(rèn)值的情況下,時(shí)間片的大小直接導(dǎo)致任務(wù)執(zhí)行者和任務(wù)數(shù)量的不同,當(dāng)時(shí)間片較小時(shí),4種算法的分配能力相差不大;但隨著時(shí)間片的增大,任務(wù)執(zhí)行者和任務(wù)數(shù)量在一定程度上增多,因此所有算法CPU時(shí)間成本增加。任務(wù)執(zhí)行者可達(dá)范圍對(duì)算法分配時(shí)間效率的影響如圖3(b)所示,在時(shí)間片以默認(rèn)值劃分的情況下,當(dāng)任務(wù)執(zhí)行者可達(dá)范圍較小時(shí),有效任務(wù)執(zhí)行者-任務(wù)對(duì)有限,不能體現(xiàn)本文算法的優(yōu)勢;但隨著任務(wù)執(zhí)行者可達(dá)范圍的增大,任務(wù)執(zhí)行者可分配的任務(wù)數(shù)量增加,相應(yīng)的所有算法的CPU時(shí)間成本都增加,相比之下,本文算法性能最優(yōu)。

圖3 時(shí)間片和任務(wù)執(zhí)行者可達(dá)范圍對(duì)算法分配時(shí)間效率的影響Fig.3 Effect of time slices and range of executor on allocated time efficiency of NR-KM

時(shí)間片和任務(wù)執(zhí)行者可達(dá)范圍對(duì)算法任務(wù)分配數(shù)量的影響如圖4所示,時(shí)間片和任務(wù)執(zhí)行者可達(dá)范圍對(duì)算法任務(wù)分配興趣度的影響如圖5所示。SMF、KM和NR-KM3種算法分配的結(jié)果是一致的,這從側(cè)面反映了算法尋找分配結(jié)果的正確性。在時(shí)間片比較小或任務(wù)執(zhí)行者可達(dá)范圍比較小的時(shí)候,可供選擇的任務(wù)-任務(wù)執(zhí)行者分配是有限的,故這3個(gè)算法與GA算法得到的任務(wù)分配數(shù)量與任務(wù)分配興趣度差別不大;但隨著時(shí)間片和可達(dá)范圍參數(shù)值的增大,逐漸顯現(xiàn)出GA算法的劣勢。

圖4 時(shí)間片和任務(wù)執(zhí)行者可達(dá)范圍對(duì)算法任務(wù)分配數(shù)量的影響Fig.4 Effect of time slices and range of executor on number of tasks assigned efficiency of NR-KM

圖5 時(shí)間片和任務(wù)執(zhí)行者可達(dá)范圍對(duì)算法任務(wù)分配興趣度的影響Fig.5 Effect of time slices and range of executor on interest of task assignment of NR-KM

4 結(jié) 語

本文研究可拒絕情況下空間眾包任務(wù)在線分配問題,提出動(dòng)態(tài)可拒絕的空間眾包處理方法,具有較強(qiáng)的擴(kuò)展性。為減少任務(wù)執(zhí)行者拒絕的概率,運(yùn)用PCA方法計(jì)算任務(wù)執(zhí)行者對(duì)任務(wù)的興趣度;為實(shí)現(xiàn)高效、準(zhǔn)確的任務(wù)分配,提出SMF算法和NR-KM算法尋找最優(yōu)任務(wù)分配方案,并通過試驗(yàn)比較GA、KM、SMF和NR-KM 4種算法的分配性能。試驗(yàn)結(jié)果驗(yàn)證了本文算法的有效性,它是一種在任務(wù)執(zhí)行者和任務(wù)動(dòng)態(tài)變化情況下的人性化分配。下一步我們將致力于研究不同分配思路和應(yīng)用場景的在線任務(wù)分配算法,以及不同場景下團(tuán)隊(duì)合作的空間眾包任務(wù)分配算法,以更有效地進(jìn)行任務(wù)分配。