Paper Info
Title
Compact Scheduling for Task Graph Oriented Mobile Crowdsourcing
Abstract
With the proliferation of increasingly powerful mobile devices and wireless networks, mobile crowdsourcing has emerged as a novel service paradigm. It enables crowd workers to take over outsourced location-dependent tasks, and has attracted much attention from both research communities and industries. In this paper, we consider a mobile crowdsourcing scenario, where a mobile crowdsourcing task is too complex (e.g., post-earthquake recovery, citywide package delivery) but can be divided into a number of easier subtasks, which have interdependency between them. Under this scenario, we investigate an important problem, namely <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">task graph scheduling in mobile crowdsourcing</i> (TGS-MC), which seeks to optimize a compact scheduling, such that the task completion time (i.e., makespan) and overall idle time are simultaneously minimized with the consideration of worker reliability. We analyze the complexity and NP-complete of the TGS-MC problem, and propose two heuristic approaches, including BFS-based dynamic priority scheduling <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">BFSPriD</i> algorithm, and an evolutionary multitasking-based <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EMTTSch</i> algorithm, to solve our problem from local and global optimization perspective, respectively. We conduct extensive evaluation using two real-world data sets, and demonstrate superiority of our proposed approaches.
Year
DOI
Venue
2022
10.1109/TMC.2020.3040007
IEEE Transactions on Mobile Computing
Keywords
DocType
Volume
Mobile crowdsourcing,task schedule,directed acyclic graph(DAG),makespan
Journal
21
Issue
ISSN
Citations 
7
1536-1233
0
PageRank 
References 
Authors
0.34
31
7
Name
Order
Citations
PageRank
Liang Wang101.01
Zhiwen Yu22753220.67
Qi Han300.34
Dingqi Yang454228.79
Shirui Pan582069.37
Yuan Yao659153.27
Daqing Zhang73619217.31