An Ordered Submodularity-Based Budget-Feasible Mechanism for Opportunistic Mobile Crowdsensing Task Allocation and Pricing

Mobile crowdsensing services are divided into two categories: opportunistic and participatory. In opportunistic mobile crowdsensing services, users do not need to specify the crowdsensing tasks to be completed. Compared with participatory crowdsensing services, the application scope is wider and more user-friendly. In participatory crowdsensing, the service provider assumes that the user can successfully complete the data collection task. However, such an approach cannot work in an opportunistic crowdsensing service because in opportunistic crowdsensing, the user's execution of the task is uncertain, which brings great challenges to the quality of the crowdsensing service. This article is based on the assumption of the user coverage probability model and transforms the opportunistic mobile crowdsensing value maximization problem into an ordered submodularity value function model with budget constraints. This model is also good at representing participatory crowdsourcing problems. To the best of our knowledge, this is the first study to apply the ordered submodularity feature to a mobile crowdsensing service. Furthermore, we combine the properties of ordered submodular and auction models and propose an ordered submodularity-proportional share mechanism (O-PSM) to solve the allocation and payment problems in opportunistic mobile crowdsensing services. Specifically, in the allocation stage, the winning users are selected based on the proportional share threshold, and in the payment stage, the payment price for the winning users is designed based on critical value theory. We prove that the mechanism satisfies the economic characteristics of individual rationality, truthfulness, and budget feasibility. In the experimental section, the mechanism design based on ordered submodularity is shown to enable the service provider to obtain a higher value and a lower payment.