空間眾包中可拒絕情況下的在線任務分配

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

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

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

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

1 問題定義與處理方法

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

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

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

1.2 有約束的任務

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

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

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

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

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

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

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

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

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

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

2.1 興趣度預測

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

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

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

Yc=ec1Z1+ec2Z2+…+ecpZp。

(1)

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

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

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

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

2.2.1 基于MaxFlow的排序算法

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

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

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

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

本文提出基于KM的不重復構(gòu)造交替樹算法(non-repetitive construction of alternating tree algorithm based on KM,NR-KM),在原來樹的基礎上接著搜索新加入的邊。設頂點wi的頂標為lw[i],頂點tj的頂標為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ū)綄嶋H的道路信息。采用某一天滴滴快專車平臺的訂單司機軌跡數(shù)據(jù),有119 019個訂單,共涉及178 56個任務執(zhí)行者。在試驗研究中,由于任務執(zhí)行者和任務有屬性約束,需補充數(shù)據(jù)集屬性。通過原始真實數(shù)據(jù)集計算出任務時長(unix時間戳形式)、任務移動距離(換算成兩地之間的距離);根據(jù)滴滴快車訂單計價規(guī)則,計算任務價格。

試驗主要考慮時間片p和任務執(zhí)行者可達范圍r對任務分配算法的影響。時間片范圍的設定在一定程度上影響該時間片內(nèi)任務執(zhí)行者與任務的數(shù)量,間接影響分配結(jié)果;任務執(zhí)行者可達范圍直接影響任務能否被任務執(zhí)行者執(zhí)行,決定任務執(zhí)行者-任務有效對的數(shù)量,影響分配結(jié)果。本研究設置的試驗參數(shù)見表1(參數(shù)數(shù)值加粗的為默認值),對每個參數(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

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

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

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

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

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

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

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

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

4 結(jié) 語

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