{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T02:38:46Z","timestamp":1776652726545,"version":"3.51.2"},"reference-count":40,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T00:00:00Z","timestamp":1648857600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Mobile crowdsensing utilizes the devices of a group of users to cooperatively perform some sensing tasks, where finding the perfect allocation from tasks to users is commonly crucial to guarantee task completion efficiency. However, existing works usually assume a static task allocation by sorting the cost of users to complete the tasks, where the cost is measured by the expense of time or distance. In this paper, we argue that the task allocation process is actually a dynamic combinational optimization problem because the previous allocated task will influence the initial state of the user to finish the next task, and the user\u2019s preference will also influence the actual cost. To this end, we propose a personalized task allocation strategy for minimizing total cost, where the cost for a user to finish a task is measured by both the moving distance and the user\u2019s preference for the task, then instead of statically allocating the tasks, the allocation problem is formulated as a heterogeneous, asymmetric, multiple traveling salesman problem (TSP). Furthermore, we transform the multiple-TSP to the single-TSP by proving the equivalency, and two solutions are presented to solve the single-TSP. One is a greedy algorithm, which is proved to have a bound to the optimal solution. The other is a genetic algorithm, which spends more calculation time while achieving a lower total cost. Finally, we have conducted a number of simulations based on three widely-used real-world traces: roma\/taxi, epfl, and geolife. The simulation results could match the results of theoretical analysis.<\/jats:p>","DOI":"10.3390\/s22072751","type":"journal-article","created":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T06:04:01Z","timestamp":1648965841000},"page":"2751","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["A Personalized Task Allocation Strategy in Mobile Crowdsensing for Minimizing Total Cost"],"prefix":"10.3390","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1715-7448","authenticated-orcid":false,"given":"Hengfei","family":"Gao","sequence":"first","affiliation":[{"name":"College of Computer Science and Technology, Jilin University, Changchun 130012, China"}]},{"given":"Hongwei","family":"Zhao","sequence":"additional","affiliation":[{"name":"College of Computer Science and Technology, Jilin University, Changchun 130012, China"}]}],"member":"1968","published-online":{"date-parts":[[2022,4,2]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1109\/MCOM.2011.6069707","article-title":"Mobile crowdsensing: Current state and future challenges","volume":"49","author":"Ganti","year":"2011","journal-title":"IEEE Commun. Mag."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Zhou, T., Xiao, B., Cai, Z., Xu, M., and Liu, X. (2018, January 16\u201319). From Uncertain Photos to Certain Coverage: A Novel Photo Selection Approach to Mobile Crowdsensing. Proceedings of the IEEE INFOCOM 2018\u2014IEEE Conference on Computer Communications, Honolulu, HI, USA.","DOI":"10.1109\/INFOCOM.2018.8485969"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Lin, J., Li, M., Yang, D., Xue, G., and Tang, J. (2017, January 1\u20134). Sybil-Proof Incentive Mechanisms for Crowdsensing. Proceedings of the IEEE INFOCOM 2017\u2014IEEE Conference on Computer Communications, Atlanta, GA, USA.","DOI":"10.1109\/INFOCOM.2017.8057175"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Xu, J., Guan, C., Wu, H., Yang, D., Xu, L., and Li, T. (2018, January 11\u201313). Online Incentive Mechanism for Mobile Crowdsourcing based on Two-tiered Social Crowdsourcing Architecture. Proceedings of the 2018 15th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), Hong Kong, China.","DOI":"10.1109\/SAHCN.2018.8397102"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Wang, B., Kong, L., He, L., Wu, F., Yu, J., and Chen, G. (2018, January 2\u20136). I (TS, CS): Detecting Faulty Location Data in Mobile Crowdsensing. Proceedings of the 2018 IEEE 38th International Conference on Distributed Computing Systems (ICDCS 2018), Vienna, Austria.","DOI":"10.1109\/ICDCS.2018.00083"},{"key":"ref_6","first-page":"1","article-title":"Social-Network-Assisted Worker Recruitment in Mobile Crowd Sensing","volume":"99","author":"Wang","year":"2018","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"750","DOI":"10.1109\/TNET.2020.2976927","article-title":"Crowdsensing for Spectrum Discovery: A Waze-Inspired Design via Smartphone Sensing","volume":"28","author":"Lin","year":"2020","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1924","DOI":"10.1109\/TMC.2020.2973980","article-title":"PACE: Privacy-Preserving and Quality-Aware Incentive Mechanism for Mobile Crowdsensing","volume":"20","author":"Zhao","year":"2020","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_9","first-page":"519","article-title":"Privacy-Preserving User Recruitment Protocol for Mobile Crowdsensing","volume":"28","author":"Xiao","year":"2020","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"2208","DOI":"10.1109\/TNET.2019.2938453","article-title":"Data-Driven Pricing for Sensing Effort Elicitation in Mobile Crowd Sensing Systems","volume":"27","author":"Jin","year":"2019","journal-title":"IEEE\/ACM Trans. Netw."},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Wang, X., Jia, R., Tian, X., and Gan, X. (2018, January 16\u201319). Dynamic Task Assignment in Crowdsensing with Location Awareness and Location Diversity. Proceedings of the IEEE INFOCOM 2018\u2014IEEE Conference on Computer Communications, Honolulu, HI, USA.","DOI":"10.1109\/INFOCOM.2018.8485914"},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Zhu, Q., Uddin, M.Y.S., Venkatasubramanian, N., and Hsu, C.H. (2018, January 16\u201319). Spatiotemporal Scheduling for Crowd Augmented Urban Sensing. Proceedings of the IEEE INFOCOM 2018\u2014IEEE Conference on Computer Communications, Honolulu, HI, USA.","DOI":"10.1109\/INFOCOM.2018.8485869"},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Yang, D., Xue, G., Fang, X., and Tang, J. (2012, January 22\u201326). Crowdsourcing to smartphones: Incentive mechanism design for mobile phone sensing. Proceedings of the 18th Annual International Conference on Mobile Computing and Networking, Istanbul, Turkey.","DOI":"10.1145\/2348543.2348567"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Jin, H., Su, L., Chen, D., Nahrstedt, K., and Xu, J. (2015, January 22\u201325). Quality of information aware incentive mechanisms for mobile crowd sensing systems. Proceedings of the Sixteenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Hangzhou, China.","DOI":"10.1145\/2746285.2746310"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"2172","DOI":"10.1109\/TMC.2020.2975569","article-title":"Distributed Time-Sensitive Task Selection in Mobile Crowdsensing","volume":"20","author":"Cheung","year":"2020","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"769","DOI":"10.1109\/TMC.2019.2900243","article-title":"ARETE: On Designing Joint Online Pricing and Reward Sharing Mechanisms for Mobile Data Markets","volume":"19","author":"Zheng","year":"2020","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1109\/TMC.2018.2878821","article-title":"Location-Aware Crowdsensing: Dynamic Task Assignment and Truth Inference","volume":"19","author":"Wang","year":"2020","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1016\/j.orl.2007.02.001","article-title":"An approximation algorithm for a symmetric Generalized Multiple Depot, Multiple Travelling Salesman Problem","volume":"6","author":"Malik","year":"2007","journal-title":"Oper. Res. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Oberlin, P., Rathinam, S., and Darbha, S. (2009, January 10\u201312). A Transformation for a Heterogeneous, Multiple Depot, Multiple Traveling Salesman Problem. Proceedings of the American Control Conference, St. Louis, MO, USA.","DOI":"10.1109\/ACC.2009.5160666"},{"key":"ref_20","first-page":"215","article-title":"The Traveling Salesman Problem: A Case Study in Local Optimization","volume":"1","author":"Johnson","year":"1997","journal-title":"Local Search Comb. Optim."},{"key":"ref_21","first-page":"237","article-title":"An 8\/13-approximation algorithm for the asymmetric maximum TSP","volume":"17","author":"Blaser","year":"2002","journal-title":"Siam J. Discret. Math."},{"key":"ref_22","first-page":"1","article-title":"The Traveling Salesman: Computational Solutions for TSP Applications","volume":"840","author":"Reinelt","year":"1994","journal-title":"Lect. Notes Comput. Sci."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1287\/ijoc.4.4.387","article-title":"Fast Algorithms for Geometric Traveling Salesman Problems","volume":"4","author":"Louis","year":"1992","journal-title":"Orsa J. Comput."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An Effective Heuristic Algorithm for the Traveling-Salesman Problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"key":"ref_25","unstructured":"Bracciale, L., Bonola, M., Loreti, P., Bianchi, G., Amici, R., and Rabuffi, A. (2022, January 20). CRAWDAD Dataset Roma\/Taxi (v. 2014-07-17). Available online: http:\/\/crawdad.org\/roma\/taxi\/20140717."},{"key":"ref_26","unstructured":"Piorkowski, M., Sarafijanovic-Djukic, N., and Grossglauser, M. (2022, January 20). CRAWDAD Dataset Epfl\/Mobility (v. 2009-02-24). Available online: http:\/\/crawdad.org\/epfl\/mobility\/20090224."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Zhang, L., Xie, X., and Ma, W.Y. (2009, January 20\u201324). Mining interesting locations and travel sequences from GPS trajectories. Proceedings of the 18th International World Wide Web Conference, Madrid, Spain.","DOI":"10.1145\/1526709.1526816"},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1109\/TMC.2017.2702613","article-title":"An Efficient Prediction-Based User Recruitment for Mobile Crowdsensing","volume":"17","author":"Wang","year":"2018","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"2982","DOI":"10.1109\/JIOT.2020.2964657","article-title":"An Online Incentive Mechanism for Crowdsensing With Random Task Arrivals","volume":"7","author":"Li","year":"2020","journal-title":"IEEE Internet Things J."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1979","DOI":"10.1109\/TMC.2018.2869387","article-title":"Allocating Heterogeneous Tasks in Participatory Sensing with Diverse Participant-Side Factors","volume":"18","author":"Wang","year":"2018","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1109\/THMS.2016.2599489","article-title":"ActiveCrowd: A Framework for Optimized Multitask Allocation in Mobile Crowdsensing Systems","volume":"47","author":"Guo","year":"2017","journal-title":"IEEE Trans. Hum. Mach. Syst."},{"key":"ref_32","unstructured":"Ding, Y., Chen, C., Zhang, S., Guo, B., Yu, Z., and Wang, Y. (2017, January 13\u201317). GreenPlanner: Planning personalized fuel-efficient driving routes using multi-sourced urban data. Proceedings of the 2017 IEEE International Conference on Pervasive Computing and Communications (PerCom), Kona, HI, USA."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"2779","DOI":"10.1109\/TMC.2020.2990221","article-title":"Differentially Private Unknown Worker Recruitment for Mobile Crowdsensing Using Multi-Armed Bandits","volume":"20","author":"Zhao","year":"2021","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Yang, S., Han, K., Zheng, Z., Tang, S., and Wu, F. (2018, January 16\u201319). Towards Personalized Task Matching in Mobile Crowdsensing via Fine-Grained User Profiling. Proceedings of the IEEE INFOCOM 2018\u2014IEEE Conference on Computer Communications, Honolulu, HI, USA.","DOI":"10.1109\/INFOCOM.2018.8486298"},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"1356","DOI":"10.1109\/TMC.2018.2861765","article-title":"Privacy-Preserving Crowd-Sourced Statistical Data Publishing with An Untrusted Server","volume":"18","author":"Wang","year":"2019","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"An, B., Xiao, M., Liu, A., Xu, Y., Zhang, X., and Li, Q. (2021). Secure Crowdsensed Data Trading Based on Blockchain. IEEE Trans. Mob. Comput.","DOI":"10.1109\/TMC.2021.3107187"},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"1330","DOI":"10.1109\/TMC.2018.2861393","article-title":"Personalized Privacy-preserving Task Allocation for Mobile Crowdsensing","volume":"18","author":"Wang","year":"2018","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"1275","DOI":"10.1109\/TMC.2017.2763956","article-title":"Data-Centric Mobile Crowdsensing","volume":"17","author":"Jiang","year":"2018","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3421506","article-title":"A Green Stackelberg-Game Incentive Mechanism for Multi-Service Exchange in Mobile Crowdsensing","volume":"22","author":"Lu","year":"2021","journal-title":"ACM Trans. Internet Technol."},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Karaliopoulos, M., Koutsopoulos, I., and Titsias, M. (2016, January 5\u20138). First learn then earn: Optimizing mobile crowdsensing campaigns through data-driven user profiling. Proceedings of the Seventeenth ACM International Symposium on Mobile Ad Hoc Networking and Computing, Paderborn, Germany.","DOI":"10.1145\/2942358.2942369"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/7\/2751\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:49:07Z","timestamp":1760136547000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/22\/7\/2751"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,2]]},"references-count":40,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,4]]}},"alternative-id":["s22072751"],"URL":"https:\/\/doi.org\/10.3390\/s22072751","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,2]]}}}