Computer Science

Computer Science ›› 2019, Vol. 46 ›› Issue (6): 102-106.doi: 10.11896/j.issn.1002-137X.2019.06.014

Previous Articles     Next Articles

Location-related Online Multi-task Assignment Algorithm for Mobile Crowd Sensing

LI Zhuo1,2, XU Zhe2, CHEN Xin2, LI Shu-qin2,3   

  1. (Beijing Key Laboratory of Internet Culture and Digital Dissemination Research,Beijing Information Science & Technology University,Beijing 100101,China)1
    (School of Computer Science,Beijing Information Science & Technology University,Beijing 100101,China)2
    (Joint Lab of Sensing and Computational Intelligence,Beijing Information Science & Technology University,Beijing 100101,China)3
  • Received:2018-04-30 Published:2019-06-24

PDF (PC)

1009

Abstract: The higher data quality is required,the more sensing cost is needed.How to achieve the trade-off between the quality and cost is one of the hot topics in the current research on the problem of task assignment in mobile crowd sen-sing.In this paper,the location-related online multi-task assignment problem where the lower bound of the data quality is required to ensure was investigated.The optimization goal is to minimize the total sensing cost,and the data quality requirement is quantified as the number of different execution nodes.This paper proposed a greedy algorithmbased on partition.Its main idea is as follows.Firstly,a disk is generated,whose center is the initial position of the execution node and whose radius is the farthest expected move of the node.After that,a subset of proper tasks whose locations are in the disk are selected,and they are regarded as the tasks to be taken by the corresponding execution node.According to the experimental simulation,compared with the GGA-I algorithm,the proposed algorithm reduces the total sensing cost on the average of 12.7% in the same running time,and reduces the running time on an average of 51% in the similar sensing performance.

Key words: Data quality, Greedy algorithm, Location-related, Mobile crowd sensing, Online multi-task assignment

CLC Number: 

  • TP393
[1]ZHANG D Q,XIONG H Y,WANG L Y,et al.CrowdRecruiter Selecting participants for piggyback crowdsensing under probabilistic coverage constraint[C]∥Proceedings of the 2014 ACM International joint Conference on Pervasive and Ubiquitous Computing(UbiComp’14).ACM,2014:703-714.
[2]WANG J,TAN N,LUO J,et al.WOLoc:WiFi-only outdoor localization using crowdsensed hotspot labels[C]∥INFOCOM 2017-IEEE Conference on Computer Communications.IEEE,2017:1-9.
[3]JING Y,GUO B,LIU Y,et al.CrowdTracker:object tracking using mobile crowd sensing[C]∥Proceedings of the 2017 ACM International Joint Conference on Pervasive and Ubiquitous Computing and Proceedings of the 2017 ACM International Symposium on Wearable Computers.ACM,2017:85-88.
[4]ZHENG Y,LIU F,HSIEH H P.U-air:When urban air quality inference meets big data[C]∥Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining.ACM,2013:1436-1444.
[5]YANG D,XUE G,FANG X,et al.Crowdsourcing to smartphones:Incentive mechanism design for mobile phone sensing[C]∥Proceedings of the 18th Annual International Conference on Mobile Computing and Networking.ACM,2012:173-184.
[6]HAN K,HUANG H,LUO J.Posted pricing for robust crowdsensing[C]∥Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing.ACM,2016:261-270.
[7]HE S,SHIN D H,ZHANG J,et al.Toward optimal allocation of location dependent tasks in crowdsensing[C]∥2014 IEEE Conference on Computer Communications(INFOCOM).2014:745-753.
[8]WANG J,WANG Y,ZHANG D,et al.PSAllocator:multi-task allocation for participatory sensing with sensing capability constraints[C]∥Proceedings of the 2017 ACM Conference on Computer Supported Cooperative Work and Social Computing.2017:1139-1151.
[9]ESTRADA R,MIZOUNI R,OTROK H,et al.A crowd-sensing framework for allocation of time-constrained and location-based tasks[J/OL].IEEE Transactions on Services Computing,https://www.computer.org/csdl/trans/sc/preprint/07974784-abs.html.
[10]HU T,XIAO M,HU C,et al.A QoS-sensitive task assignment algorithm for mobile crowdsensing[J].Pervasive and Mobile Computing,2017,41:333-342.
[11]GAMBOSI G,PROTASI M,TALAMO M.Preserving approximation in the Min－Weighted Set Cover Problem[J].Discrete Applied Mathematics,1997,73(1):13-22.
[12]堵丁柱,葛可一,胡晓东,等.近似算法的设计与分析[M].北京:高等教育出版社,2011.
[13]BOWDEN J A.Foursquare-user-dataset[EB/OL].https:// github.com/jalbertbowden/foursquare-user-dataset.
[14]CHRISTOFIDES N.Worst-case analysis of a new heuristic for the travelling salesman problem[R].Carnegie-Mellon Univ Pittsburgh Pa Management Sciences Research Group,1976.
[1] ZHANG Chong-yu, CHEN Yan-ming, LI Wei. Task Offloading Online Algorithm for Data Stream Edge Computing [J]. Computer Science, 2022, 49(7): 263-270.
[2] LIU Zhang-hui, ZHENG Hong-qiang, ZHANG Jian-shan, CHEN Zhe-yi. Computation Offloading and Deployment Optimization in Multi-UAV-Enabled Mobile Edge Computing Systems [J]. Computer Science, 2022, 49(6A): 619-627.
[3] ZHENG Xiao-meng, GAO Meng, TENG Jun-yuan. Research on Construction Method of Defect Prediction Dataset for Spacecraft Software [J]. Computer Science, 2021, 48(6A): 575-580.
[4] LI Jian-Jun, WANG Xiao-ling, YANG Yu and FU Jia. Emergency Task Assignment Method Based on CQPSO Mobile Crowd Sensing [J]. Computer Science, 2020, 47(6A): 273-277.
[5] ZHANG Xin-ming, LI Shuang-qian, LIU Yan, MAO Wen-tao, LIU Shang-wang, LIU Guo-qi. Coyote Optimization Algorithm Based on Information Sharing and Static Greed Selection [J]. Computer Science, 2020, 47(5): 217-224.
[6] SUN Zhi-qiang, WAN Liang, DING Hong-wei. Android Malware Detection Method Based on Deep Autoencoder Network [J]. Computer Science, 2020, 47(4): 298-304.
[7] HU Jun-qin, ZHANG Jia-jun, HUANG Yin-hao, CHEN Xing, LIN Bing. Computation Offloading Scheduling Technology for DNN Applications in Edge Environment [J]. Computer Science, 2020, 47(10): 247-255.
[8] LIAO Yong, YANG Xin-yi, XIA Mao-han, WANG Bo, LI Shou-zhi, SHEN Xuan-fan. Improved Tomlinson-Harashima Precoding Based on Greedy Algorithm in High-speed Mobile Scenarios [J]. Computer Science, 2019, 46(8): 121-126.
[9] ZHENG Fei-feng, JIANG Juan, MEI Qi-huang. Study on Stowage Optimization in Minimum Container Transportation Cost [J]. Computer Science, 2019, 46(6): 239-245.
[10] WANG Yang, CAI Shu-qin, ZOU Xin-wen, CHEN Zi-tong. Quality-embedded Hypergraph Model for Big Data Product Manufacturing System and Decision for Production Lines [J]. Computer Science, 2019, 46(2): 11-17.
[11] YU Jian-jun, WU Chun-ming. Offline Static Virtual Network Mapping Algorithm Based on Tabu Search Genetic Optimization [J]. Computer Science, 2019, 46(12): 114-119.
[12] CHEN Jin-yin, HU Ke-ke,LI Yu-wei. Research on UAV Multi-point Navigation Algorithm Based on MB-RRT* [J]. Computer Science, 2018, 45(6A): 85-90.
[13] ZHU Rui-chao,QIAN Wen-hua,PU Yuan-yuan, XU Dan. Texture Synthesis Based on Self-similarity Matching [J]. Computer Science, 2018, 45(6A): 215-219.
[14] HU Qing-cheng, ZHANG Yong, XING Chun-xiao. K-clique Heuristic Algorithm for Influence Maximization in Social Network [J]. Computer Science, 2018, 45(6): 32-35.
[15] CAI Li, LIANG Yu, ZHU Yang-yong and HE Jing. History and Development Tendency of Data Quality [J]. Computer Science, 2018, 45(4): 1-10.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
Add:18# Honghu West Rd., Yubei ,Chongqing,China    Post Code: 401121
Tel: 023-63500828/023-67039612/023-67039623
E-mail: jsjkx12@163.com
Powered by Beijing Magtech Co., Ltd.