Research On Theory And Methods Of Online Crowd Sensing For Privacy Preservation And Incentive Compatibility

With the proliferation of wireless communication technologies and smart devices equipped with multiple sensors,Mobile Crowd Sensing(MCS)has emerged as a new paradigm in the fields of Internet of Things and mobile computing,drawing extensive attention from academia and industry.MCS comprises an open platform,task requesters,and mobile users equipped with smart devices.By leveraging wireless communication technology,MCS uses mobile users as basic sensing units to perform large-scale complex sensing tasks,including task assignment,user recruitment,and data collection.Ultimately,MCS integrates the collective wisdom and power of the crowd to achieve these objectives efficiently.As MCS continues to gain popularity,numerous concerns have arisen.Among these concerns are: designing effective online task assignment and user recruitment algorithms,ensuring incentive compatibility,and protecting user and task privacy during online recruitment.To address these issues,this paper focuses on the design of online algorithms for MCS and presents a range of novel models and approaches with theoretical guarantees.Since online algorithms in MCS require a minimum number of users,our aim is to attract more participants to the platform.Accordingly,we propose an incentive mechanism and a privacy protection strategy that incentivize users to participate in MCS by offering payment and safeguard their privacy.These mechanisms ensure incentive and privacy protection guarantees for the proposed online algorithm.The main contributions of this paper are as follows:(1)Online task assignment: While existing MCS research has primarily focused on offline scenarios where prior knowledge about users and tasks is available,in real-world applications,users and tasks appear dynamically and randomly,making it difficult to obtain prior knowledge.This scenario is referred to as online MCS.To address this,we propose an online one-user-many-task assignment strategy.First,we construct a directed weight graph with users and tasks as vertices and set costs and capacities for each edge based on the real-world path between users and tasks.We then develop an offline task assignment algorithm that solves both the matching and path planning problems using the minimum cost and maximum flow problem.We extend this algorithm to the online scenario and propose an online task assignment algorithm based on a well-estimated threshold.Additionally,we provide the theoretical upper bound of the competitive ratio of the online assignment algorithm.Finally,we evaluate the effectiveness of our algorithm using a real-world taxi dataset.(2)Online incentive mechanism: The incentive mechanism remains a primary concern in MCS and has been extensively studied.However,most previous research has focused on offline MCS scenarios or incomplete online MCS scenes that require some prior knowledge,such as historical data.To address this gap,we propose a pricing-based incentive mechanism for complete online MCS scenes that do not require any prior knowledge.First,we propose a cold-start single-round user recruitment strategy based on a combinatorial multi-armed bandit model,aiming to maximize the cumulative utility of recruited users while controlling costs under budget constraints.We provide theoretical analysis that gives the upper bound of regret,representing the gap between achieved and optimal solutions.Furthermore,we design an online incentive mechanism that determines each user’s payment based on the utilities and costs of other users in the current round.Through our theoretical analysis,our proposed incentive mechanism is shown to be individually rational,computationally efficient,and truthful.(3)Privacy preservation strategy: MCS involves sensitive information like location and cost that users and task requesters must report during task assignment,user recruitment,and data collection,raising significant privacy concerns.Failure to address these concerns can discourage people from participating in MCS.Protecting privacy is thus critical in MCS,and previous privacy policies have mainly focused on protecting user privacy,neglecting the protection of task privacy and relying on trusted third parties for preservation,resulting in higher communication overhead and service costs.To address these issues,we propose a bilateral privacy-preserving framework that protects both task and user privacy.Specifically,we use random response strategies to protect user location and cost privacy,and a random matrix multiplication strategy to hide the true location of tasks.We prove that the user selection problem in this privacy framework is non-submodular and NP-hard,and present an efficient greedy algorithm with a provable approximation ratio.In conclusion,this paper proposes a range of MCS methods that address the challenges posed by dynamic online MCS scenes,ensuring incentive compatibility and preserving privacy during task assignment,user recruitment,and data collection processes.We validate the effectiveness of these proposed methods through theoretical analysis and extensive simulation experiments.Our contributions offer critical theoretical and technical support for the further implementation of MCS in various real-world fields.