Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget Constraint
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-05-01
|
| Series: | Sensors |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1424-8220/19/10/2371 |
| _version_ | 1811305982227120128 |
|---|---|
| author | Yanan Wang Guodong Sun Xingjian Ding |
| author_facet | Yanan Wang Guodong Sun Xingjian Ding |
| author_sort | Yanan Wang |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-13T08:35:43Z |
| format | Article |
| id | doaj.art-978c3be1b6d0486e801e46c7d8e99cca |
| institution | Directory Open Access Journal |
| issn | 1424-8220 |
| language | English |
| last_indexed | 2024-04-13T08:35:43Z |
| publishDate | 2019-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Sensors |
| spelling | doaj.art-978c3be1b6d0486e801e46c7d8e99cca2022-12-22T02:54:05ZengMDPI AGSensors1424-82202019-05-011910237110.3390/s19102371s19102371Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget ConstraintYanan Wang0Guodong Sun1Xingjian Ding2School of Information Science and Technology, Beijing Forestry University, Beijing 100083, ChinaSchool of Information Science and Technology, Beijing Forestry University, Beijing 100083, ChinaDepartment of Computer Science, Renmin University, Beijing 100072, ChinaMobile 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.https://www.mdpi.com/1424-8220/19/10/2371mobile crowd sensingcoverage areacoverage balanceuser selection |
| spellingShingle | Yanan Wang Guodong Sun Xingjian Ding Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget Constraint Sensors mobile crowd sensing coverage area coverage balance user selection |
| title | Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget Constraint |
| title_full | Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget Constraint |
| title_fullStr | Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget Constraint |
| title_full_unstemmed | Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget Constraint |
| title_short | Coverage-Balancing User Selection in Mobile Crowd Sensing with Budget Constraint |
| title_sort | coverage balancing user selection in mobile crowd sensing with budget constraint |
| topic | mobile crowd sensing coverage area coverage balance user selection |
| url | https://www.mdpi.com/1424-8220/19/10/2371 |
| work_keys_str_mv | AT yananwang coveragebalancinguserselectioninmobilecrowdsensingwithbudgetconstraint AT guodongsun coveragebalancinguserselectioninmobilecrowdsensingwithbudgetconstraint AT xingjianding coveragebalancinguserselectioninmobilecrowdsensingwithbudgetconstraint |