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

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

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

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

1 問題定義與處理方法

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

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

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

1.2 有約束的任務(wù)

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

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

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

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

定義1任務(wù)分配數(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 動態(tài)可拒絕的空間眾包處理方法

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

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

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

2.1 興趣度預(yù)測

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

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

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

Yc=ec1Z1+ec2Z2+…+ecpZp。

(1)

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

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

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

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

2.2.1 基于MaxFlow的排序算法

采用基于MaxFlow的排序算法(sequence algorithm base on MaxFlow,SMF)求解分配策略。建立一個額外的源點Start和一個額外的匯點End,源點與頂點連接一條容量c為1、權(quán)重為0的弧,匯點也執(zhí)行類似的操作;兩邊頂點任務(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ào)整流量都遵循最短路徑的原則,直到找不到增廣路,此時的總流量和興趣度分?jǐn)?shù)即為所求答案。但是在尋找最大興趣度增廣路的時候需先求出最短路徑,已知增流到最后的流量n={min(|Wp|,|Tp|)},針對有多條弧的權(quán)重為0的特性,只需對二分圖中的權(quán)重按照從小到大的順序排列,再根據(jù)排序作為有向路徑增流[22]至n值或不存在可增廣路為止,如此就找到最小興趣差最大流路徑,轉(zhuǎn)換后也就是找到最大興趣度最大流路徑。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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