時空眾包環境下時效均衡的在線任務分配算法

張興盛 余敦輝 張萬山 王晨旭

摘 要：針對時空眾包任務分配研究中單一考慮任務分配總效用或任務等待時間，導致總體分配效果不佳的問題，提出一種基于分配時間因子的動態閾值算法。首先，基于預估等待分配時間和已等待分配時間計算任務的分配時間因子;其次，綜合考慮任務的回報值和分配時間因子進行任務分配排序;然后，在初始值的基礎上增加動態調整項為每一項任務設置閾值;最后，根據閾值條件為每一項任務設置候選匹配集，并從候選匹配集中選擇匹配系數最大的候選匹配對加入結果集，完成任務分配。通過實驗證明，該算法在任務分配率達到95.8%的情況下，與貪心算法相比，在分配總效用方面提升20.4%;與隨機閾值算法相比，在分配總效用方面提升17.8%，在任務平均等待時間方面縮短13.2%;與基于兩階段框架模型的在線微任務分配改進（TGOAGreedy）算法相比，在分配總效用方面提升13.9%。實驗結果表明，該算法能夠在提升任務分配總效用的同時縮短任務的平均等待時間，實現分配總效用與任務等待時間兩者間的均衡。

關鍵詞：時空眾包;在線任務分配;任務分配總效用;任務等待時間;分配時間因子;動態閾值算法

中圖分類號：TP311

文獻標志碼：A

Abstract： Focusing on the poor overall allocation effect due to the total utility of task allocation or task waiting time being considered respectively in the study of task allocation under spatial crowdsourcing environment， a dynamic threshold algorithm based on allocation time factor was proposed. Firstly， the allocation time factor of task was calculated based on the estimated waiting time and the already waiting time. Secondly， the task allocation order was obtained by comprehensively considering the return value of task and the allocation time factor. Thirdly， the dynamic adjustment item was added based on the initial value to set the threshold for each task. Finally， candidate matching set was set for each task according to the threshold condition， and the candidate matching pair with the largest matching coefficient was selected from the candidate matching set to join the result set， and the task allocation was completed. When the task allocation rate was 95.8%， compared with greedy algorithm， the proposed algorithm increased total allocation utility by 20.4%; compared with random threshold algorithm， it increased total allocation utility by 17.8% and decreased task average waiting time by 13.2%; compared with Two phase based Global Online AllocationGreedy （TGOAGreedy） algorithm， it increased total allocation utility by 13.9%. The experimental results show that proposed algorithm can shorten the average waiting time of task while improving the total utility of task allocation， to achieve the balance between the total allocation utility and the task waiting time.

英文關鍵詞Key words： spatial crowdsourcing; online task assignment; total utility of task allocation; waiting time of task; allocation time factor; dynamic threshold algorithm

0 引言

眾包[1-3]這一概念由美國人Jeff Howe在美國《連線》雜志上于2006年首次提出，通常指一種把工作任務通過公開的 Web 平臺以自愿的形式外包給非特定的解決方案提供者群體來完成的分布式問題求解模式。隨著互聯網技術的發展，這種通過群體智慧求解問題的新模式也受到了工業界和學術界的廣泛關注，像AMT （Amazon Mechanical Turks）這類眾包平臺得到了迅速發展。近年來，伴隨移動互聯網技術和共享經濟的興起，以及移動智能設備的普及和應用，為眾包模式帶來更多的外延需求，不再滿足于傳統眾包模式下單一的任務類型，擴展了更多包含時空屬性，從而發展為時空眾包[4]，例如，滴滴出行、百度外賣等。

在時空眾包環境下，任務分配[5]依然是其核心問題之一。針對這一問題學術界展開了積極研究，文獻[6-8]重點考慮任務分配總效用： 文獻[6]提出一種基于兩階段框架模型的全球在線微任務分配改進算法（Two phase based Global Online AllocationGreedy， TGOAGreedy），確保分配速度的同時優化分配總效用，但算法以貪心算法作為基線算法，任務的分配總效用可進一步提升;文獻[7]基于當前的閾值機制，提出了一種根據任務分配情況自動調整閾值的自適應閾值算法，對比隨機閾值算法提升了分配總效用，但算法閾值是從確定集合中選擇，分配效用仍存在很大的提升空間;文獻[8]提出一種基于統計預測的自適應閾值算法，進一步優化了分配總效用，不足是任務分配率偏低。文獻[9-10]從縮短匹配距離，同時減小眾包工人差旅成本入手展開研究：文獻[9]提出了一種面向距離的閾值算法，旨在最小化最大的匹配距離，但實際應用中更多考慮的是平均匹配距離，因此算法缺乏實用性;文獻[10]針對最小化分配總距離問題進行了綜合性實驗，證明了貪心算法解決這類問題時的高效性，但缺乏穩定可靠性。文獻[11-12]綜合考慮了分配效用和差旅成本，進行雙目標優化：文獻[11]提出了一種將雙目標優化和多臂賭博機相結合的動態分配方法，旨在盡量減少差旅成本的前提下最大限度地提高任務的可靠性，同時提升分配效用，但沒有考慮任務和工人活躍范圍的限制;文獻[12]提出基于二分法框架模型來最大化任務分配的數量，同時最小化差旅成本，但與文獻[11]一樣，均沒有從任務發布者的角度出發，考慮任務等待分配這一過程的時間成本。

從上不難看出，現有的研究更多是聚焦于單一考慮任務分配總效用或任務等待時間，從而導致效用高的算法任務等待時間可能過長，等待時間短的算法分配總效用有時又太低。綜合這兩方面要素的算法考慮又不夠完善，存在很大的提升空間。

為此，本文從眾包平臺和眾包任務發布者雙方的角度出發，綜合考慮了任務分配的總效用和任務等待時間，提出一種基于分配時間因子的動態閾值（Allocationtime Factor based Dynamic Threshold， AFDT）算法，旨在保證任務分配總效用的同時縮短任務平均等待時間。對比文獻[6-7]中的算法，AFDT算法進一步提高了分配總效用;對比文獻[8]中的算法，AFDT算法不僅提高了分配總效用，同時也確保了任務分配率;對比文獻[9-10]中的算法，AFDT算法更具實用性，算法性能也更加穩定可靠;對比文獻[11-12]中的算法，AFDT算法既考慮了任務和工人活躍范圍的限制，也增加了從任務等待分配角度的考慮。

本文的主要貢獻如下：1）提出一種用于衡量任務等待分配程度的計量因子——分配時間因子（Allocation Time Factor of mission，ATFm），作為任務等待程度的衡量指標。2）設計一種基于分配時間因子的動態閾值算法（AFDT算法），AFDT算法基于任務的分配時間因子ATFm動態調整閾值，實現任務等待時間與分配效用之間的均衡。

5 結語

本文研究了時空眾包環境下時效均衡的在線任務分配問題，利用分配時間因子衡量任務的等待分配程度，并采用面向工人任務成功率的動態閾值機制，設計了一種基于分配時間因子的動態閾值算法。本文通過基于真實數據的仿真實驗證明了所提算法在任務分配率、分配總效用、任務平均等待時間方面均具有較好的性能表現，能夠有效解決時效均衡的在線任務分配問題。未來的時空眾包研究可從以下兩個方面展開：1）引入機器學習的方法進一步提升任務分配總效用或縮短任務的等待時間。2）研究從眾包工人方面考慮工人成本的問題，進一步優化在線任務分配算法。

參考文獻 （References）

[1] HOWE J. The rise of crowdsourcing[J]. Wired Magazine， 2016， 14（6）： 1-4.

[2] 芮蘭蘭， 張攀， 黃豪球， 等. 一種面向眾包的基于信譽值的激勵機制[J]. 電子與信息學報， 2016， 38（7）： 1808-1815. （RUI L L， ZHANG P， HUANG H Q， et al. Reputationbased incentive mechanisms in crowdsourcing[J]. Journal of Electronics & Information Technology， 2016， 38（7）： 1808-1815.）

[3] 施戰， 辛煜， 孫玉娥， 等. 基于用戶可靠性的眾包系統任務分配機制[J]. 計算機應用， 2017， 37（9）： 2449-2453. （SHI Z， XIN Y， SUN Y E， et al. Task allocation mechanism for crowdsourcing system based on reliability of users[J]. Journal of Computer Applications， 2017， 37（9）： 2449-2453.）

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

[5] 童詠聽， 袁野， 成雨蓉，等. 時空眾包數據管理技術研究綜述[J].軟件學報， 2017， 28（1）： 35-58. （TONG Y X， YUAN Y， CHENG Y R， et al. Survey on spatiotemporal crowdsourced data management techniques[J]. Journal of Software， 2017， 28（1）： 35-58.）

[6] TONG Y X， SHE J， DING B， et al. Online mobile microtask allocation in spatial crowdsourcing[C]// Proceedings of the 2016 IEEE 32nd International Conference on Data Engineering， Piscataway， NJ： IEEE， 2016： 49-60.

[7] 宋天舒， 童詠昕， 王立斌， 等. 空間眾包環境下的3類對象在線任務分配[J]. 軟件學報， 2017， 28（3）： 611-630. （SONG T S， TONG Y X， WANG L B， et al. Online task assignment for three types of objects under spatial crowdsourcing environment[J]. Journal of Software， 2017， 28（3）： 611-630.）

[8] 劉輝， 李盛恩. 時空眾包環境下基于統計預測的自適應閾值算法[J]. 計算機應用， 2018， 38（2）： 415-420. （LIU H， LI S E. Adaptive threshold algorithm based on statistical prediction under spatial crowdsourcing environment[J]. Journal of Computer Applications， 2018， 38（2）： 415-420.）

[9] LONG C， WONG R CW， YU P S， et al. On optimal worstcase matching[C]// Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. New York： ACM， 2013： 845-856.

[10] TONG Y， SHE J， DING B， et al. Online minimum matching in realtime spatial data： experiments and analysis [J]. Proceedings of the VLDB Endowment， 2016， 9（12）： 1053-1064.

[11] HASSAN U U， CURRY E. Efficient task assignment for spatial crowdsourcing： a combinatorial fractional optimization approach with semibandit learning[J]. Expert Systems with Applications， 2016， 58（C）： 36-56.

[12] 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.

[13] CHEN Z， FU R， ZHAO Z， et al. gMission： a general spatial crowdsourcing platform[J]. Proceedings of the Very Large Data Base Endowment， 2014， 7（13）： 1629-1632.