{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T06:40:45Z","timestamp":1778654445429,"version":"3.51.4"},"reference-count":26,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2019,5,23]],"date-time":"2019-05-23T00:00:00Z","timestamp":1558569600000},"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 crowd sensing (MCS) is a new computing paradigm for the internet of things, and it is widely accepted as a powerful means to achieve urban-scale sensing and data collection. In the MCS campaign, the smart mobilephone users can detect their surrounding environments with their on-phone sensors and return the sensing data to the MCS organizer. In this paper, we focus on the coverage-balancing user selection (CBUS) problem with a budget constraint. Solving the CBUS problem aims to select a proper subset of users such that their sensing coverage is as large and balancing as possible, yet without violating the budget specified by the MCS campaign. We first propose a novel coverage balance-based sensing utility model, which effectively captures the joint requirement of the MCS requester for coverage area and coverage balance. We then formally define the CBUS problem under the proposed sensing utility model. Because of the NP-hardness of the CBUS problem, we design a heuristic-based algorithm, called MIA, which tactfully employs the maximum independent set model to determine a preliminary subset of users from all the available users and then adjusts this user subset to improve the budget implementation. MIA also includes a fast approach to calculating the area of the union coverage with any complicated boundaries, which is also applicable to any MCS scenarios that are set up with the coverage area-based sensing utility. The extensive numeric experiments show the efficacy of our designs both in coverage balance and in the total coverage area.<\/jats:p>","DOI":"10.3390\/s19102371","type":"journal-article","created":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T02:22:00Z","timestamp":1558664520000},"page":"2371","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget Constraint"],"prefix":"10.3390","volume":"19","author":[{"given":"Yanan","family":"Wang","sequence":"first","affiliation":[{"name":"School of Information Science and Technology, Beijing Forestry University, Beijing 100083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3739-2792","authenticated-orcid":false,"given":"Guodong","family":"Sun","sequence":"additional","affiliation":[{"name":"School of Information Science and Technology, Beijing Forestry University, Beijing 100083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xingjian","family":"Ding","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Renmin University, Beijing 100072, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,5,23]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1145\/2794400","article-title":"Mobile Crowd Sensing and Computing: The Review of an Emerging Human-Powered Sensing Paradigm","volume":"48","author":"Guo","year":"2015","journal-title":"ACM Comput. Surv."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/j.future.2015.08.005","article-title":"A Mobile Crowd Sensing Ecosystem Enabled by CUPUS: Cloud-based Publish\/Subscribe Middleware for the Internet of Things","volume":"56","author":"Antonic","year":"2016","journal-title":"Future Gener. Comput. Syst."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"2020","DOI":"10.1109\/TMC.2014.2385097","article-title":"FlierMeet: A mobile crowdsensing system for cross-space public information sharing","volume":"14","author":"Guo","year":"2015","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1016\/j.jnca.2016.01.020","article-title":"Smartphone-based crowdsourcing for estimating the bottleneck capacity in wireless networks","volume":"64","author":"Gregoria","year":"2016","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Elhamshary, M., Youssef, M., Uchiyama, A., Yamaguchi, H., and Higshino, T. (2016, January 26\u201330). TransitLabel: A Crowd-Sensing System for Automatic Labeling of Transit Stations Semantics. Proceedings of the 14th ACM International Conference on Mobile Systems, Applications, and Services (MobiSys), Singapore.","DOI":"10.1145\/2906388.2906395"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"38","DOI":"10.1016\/j.jnca.2016.06.015","article-title":"GRS: A Group-Based Recruitment System for Mobile Crowd Sensing","volume":"72","author":"Azzam","year":"2016","journal-title":"J. Netw. Comput. Appl."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Wang, Z., Huang, D., Wu, H., Deng, Y., Aikebaier, A., and Teranishi, Y. (2014, January 8\u201312). QoS-Constrained Sensing Task Assignment for Mobile Crowd Sensing. Proceedings of the 2014 IEEE Global Communications Conference (Globecom), Austin, TX, USA.","DOI":"10.1109\/GLOCOM.2014.7036826"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"7698","DOI":"10.1109\/TVT.2015.2490679","article-title":"Quality-aware Sensing Coverage in Budget Constrained Mobile Crowdsensing Networks","volume":"65","author":"Zhang","year":"2015","journal-title":"IEEE Trans. Veh. Technol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"2010","DOI":"10.1109\/TMC.2015.2483505","article-title":"iCrowd: Near-Optimal Task Allocation for Piggyback Crowdsensing","volume":"15","author":"Xiong","year":"2016","journal-title":"IEEE Trans. Mob. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1007\/s11280-017-0481-x","article-title":"Participant selection for t-sweep k-coverage crowd sensing tasks","volume":"21","author":"Yu","year":"2018","journal-title":"World Wide Web"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Huang, P., Zhu, W., and Guo, L. (2019). Optimizing Movement for Maximizing Lifetime of Mobile Sensors for Covering Targets on a Line. Sensors, 19.","DOI":"10.3390\/s19020273"},{"key":"ref_12","first-page":"741","article-title":"A Mobile Agents Control Method for Sensor Data Gathering Based on Geographical Granularity in Dense Mobile Sensor Networks","volume":"53","author":"Goto","year":"2012","journal-title":"J. Inf. Process."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Wang, L., Zhang, D., Pathak, A., Chen, C., Xiong, H., Yang, D., and Wang, Y. (2015, January 7\u201311). CCS-TA: Quality-Guaranteed Online Task Allocation in Compressive Crowdsensing. Proceedings of the 2015 ACM International Joint Conference on Pervasive and Ubiquitous Computing, (Ubicomp), Osaka, Japan.","DOI":"10.1145\/2750858.2807513"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/3139256","article-title":"Quality of Information in Mobile Crowdsensing: Survey and Research Challenges","volume":"13","author":"Restuccia","year":"2017","journal-title":"ACM Trans. Sens. Netw."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1016\/j.pmcj.2017.01.005","article-title":"A QoS-sensitive task assignment algorithm for mobile crowdsensing","volume":"41","author":"Hu","year":"2017","journal-title":"Pervasive Mob. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Wang, H., Yao, K., Pottie, G., and Estrin, D. (2004, January 26\u201327). Entropy-based Sensor Selection Heuristic for Target Localization. Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks, Berkeley, CA, USA.","DOI":"10.1145\/984622.984628"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Zilan, R., and Erten, Y. (2007, January 7\u20139). Use of entropy to control coverage and energy dissipation in wireless sensor networks. Proceedings of the 22nd International Symposium on Computer and Information Sciences, Ankara, Turkey.","DOI":"10.1109\/ISCIS.2007.4456892"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","article-title":"A note on maximizing a submodular set function subject to a knapsack constraint","volume":"32","author":"Sviridenko","year":"2004","journal-title":"Oper. Res. Lett."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1007\/s10732-012-9196-4","article-title":"Fastlocal search for the maximum independent set problem","volume":"18","author":"Andrade","year":"2012","journal-title":"J. Heuristics"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Wan, P., Jia, X., Dai, G., Du, H., and Frieder, O. (May, January 27). Fast and simple approximation algorithms for maximum weighted independent set of links. Proceedings of the IEEE INFOCOM 2014\u2014IEEE Conference on Computer Communications Infocom, Toronto, ON, Canada.","DOI":"10.1109\/INFOCOM.2014.6848102"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1016\/j.ic.2017.06.001","article-title":"Exact algorithms for maximum independent set","volume":"225","author":"Xiao","year":"2017","journal-title":"Inf. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"2122","DOI":"10.14778\/2831360.2831366","article-title":"Towards Maximum Independent Sets on Massive Graphs","volume":"8","author":"Liu","year":"2015","journal-title":"Proc. VLDB Endow."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"1475","DOI":"10.1007\/s11277-014-2094-3","article-title":"Survey on Coverage Problems in Wireless Sensor Networks","volume":"80","author":"Sangwan","year":"2015","journal-title":"Wirel. Pers. Commun."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Xiong, H., Zhang, D., Chen, G., Wang, L., and Gauthier, V. (2015, January 23\u201327). CrowdTasker: Maximizing Coverage Quality in Piggyback Crowdsensing under Budget Constraint. Proceedings of the 2015 IEEE International Conference on Pervasive Computing and Communications (PerCom), Louis, MO, USA.","DOI":"10.1109\/PERCOM.2015.7146509"},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"1046","DOI":"10.1109\/JIOT.2017.2688366","article-title":"Queuing Algorithm for Effective Target Coverage in Mobile Crowd Sensing","volume":"4","author":"Obinikpo","year":"2017","journal-title":"IEEE Internet Things J."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Girolami, M., Chessa, S., Dragone, M., Bouroche, M., and Cahill, V. (2016, January 27\u201330). Using spatial interpolation in the design of a coverage metric for Mobile CrowdSensing systems. Proceedings of the IEEE Symposium on Computers and Communication (ISCC), Messina, Italy.","DOI":"10.1109\/ISCC.2016.7543730"}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/10\/2371\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:54:27Z","timestamp":1760187267000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/19\/10\/2371"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,23]]},"references-count":26,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2019,5]]}},"alternative-id":["s19102371"],"URL":"https:\/\/doi.org\/10.3390\/s19102371","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,23]]}}}