Incentive Mechanism Design For Mobile Crowd Sensing

With the popularity of the Internet of Things,mobile crowd sensing becomes a typical method to make full use of intelligence and potential value of the crowd,leveraging a large number of smart devices with computing or sensing abilities in vast urban areas.A typical mobile crowd sensing network contains task publishers which generate task requests,smart devices which perform sensing tasks and a sensing platform which controls the interaction between task publishers and smart devices.Generally speaking,it is obvious that mobile crowd sensing networks have several advantages,such as low deployment cost,vast geographical coverage,various sensing abilities,a considerable number of available smart devices.Recently,mobile crowd sensing has been a very hot research topic,and motivates a lot of urban sensing applications,e.g.,environmental monitoring,traffic events detection.There is a wide range of research topics in mobile crowd sensing networks,such as incentive mechanism design,task allocation,quality management of sensing data,and incentive mechanism design is one of the hottest.Since a smart device must consume its own valuable resources and take the risk of privacy breach to perform sensing tasks,the smart device which is individually rational would not voluntarily participate in mobile crowd sensing networks.However,the number of participators is of paramount significance to the success of mobile crowd sensing networks.A small number of smart devices are not enough to satisfy sensing requests from task publishers and fail to support high-quality sensing services.Therefore,it is necessary to offer proper incentives in mobile crowd sensing networks.Incentive mechanism design is an effective method to stimulate participation of smart devices.It is not only useful to improve the service quality and system efficiency of mobile crowd sensing networks,but also helpful to reduce or avoid some selfish behavior(e.g.,misreporting)of participators.Main research problem in the dissertation is the mechanism design for mobile crowd sensing networks,aiming at optimizing system efficiency and satisfying individual rationality and selfishness.On the one hand the research problem is how to match sensing tasks and available smart devices in order to optimize system efficiency;on the other hand the problem is how to offer proper incentives to participators in order to motivate their participation and to avoid selfish behavior.However,there exist several technical challenges in designing incentive mechanisms for mobile crowd sensing networks,such as incomplete information,selfishness of task publishers and smart devices,dynamic properties of sensing tasks and smart devices,matching sensing tasks and smart devices with given constraints(e.g.,geographical proximity).Existing incentive mechanisms for mobile crowd sensing usually take monetary rewards,social relationship,sense of achievement or reputation as incentives and employ sealed-bid auctions,various games(e.g.,Stackelberg game,congestion game)or other non-game theoretical models todesign incentive mechanisms.The dissertation offers incentive mechanisms based on auctions and choose monetary rewards as incentives.The dissertation considers three different scenarios: static mobile crowd sensing networks with constraints of geographical locations,mobile crowd sensing networks with dynamic sensing tasks and dynamic smart devices,a distributed auction scenario with competition of multiple task publishers.The dissertation incorporates reverse auction,online auction and distributed auction to model interaction in mobile crowd sensing networks,proposes optimal or near-optimal algorithms to solve the smart device selection problem with the target of maximizing social profit or minimizing social cost,and determines payment based on the idea of critical payment or through trading price updating according to the relation between supply and demand.Theoretical analysis and extensive simulation results demonstrate good properties of the proposed incentive mechanisms,such as truthfulness,individual rationality,computation efficiency.Main contributions of the dissertation are summarized as follows.1.Incentive mechanism for location-aware collaborative sensing in mobile crowd sensing:A reverse auction framework is introduced to model the interaction between the sensing platform and smart devices.The proposed incentive mechanism aims to choose smart devices efficiently and to determine payment to chosen smart devices.It is rigorously proved that optimally determining winning bids is NP hard.In this dissertation a mechanism called TRAC which consists of two main components is designed.The first component is a near-optimal approximate algorithm for determining winning bids with polynomial-time computation complexity,which approximates the optimal solution with a factor of 1 + ln(n),where n is the maximum number of sensing tasks that a smart device can accommodate.The second component is a critical payment scheme which,despite the approximation of determining winning bids,guarantees that submitted bids of smart devices report their real costs of performing sensing tasks.2.Incentive mechanism for mobile crowd sensing with dynamic smart devices and random sens-ing tasks:Dynamic property of smart devices indicates that smart devices are not always available,while dynamic property of sensing tasks tells that tasks are generated randomly according to sensing requests of task publishers.Thus,the previous incentive mechanism designed for static mobile crowd sensing networks fails with these dynamic properties.Two truthful auction mechanisms are proposed for two different cases of mobile crowd sensing networks with dynamic smart devices and dynamic sensing tasks.For the offline case,an optimal truthful incentive mechanism is designed with an optimal task allocation algorithm of polynomial-time computation complexity.For the online case,a near-optimal truthful mechanism is designed with an online task allocation algorithm that achieves a constant competitive ratio of 1/2.Rigorous theoretical analysis and extensive simulations have been performed,and the results demonstrate the proposed auction mechanisms achieve truthfulness,individual rationality,computational efficiency,and low overpayment.3.Incentive mechanism for mobile crowd sensing with competition of task publishers:Both incentive mechanisms aforementioned ignore competition among task publishers,which is un-fair to smart devices.Modeling both competition of task publishers and competition of smart devices in mobile crowd sensing networks helps to improve the system efficiency.In the dissertation,a distributed auction framework is proposed to explicitly model the interaction between task publishers and smart devices,achieving the optimal social profit and providing proper incentive to entities without disclosing their privacy as well.It is demonstrated that the proposed distributed auction algorithm satisfies a lot of good properties,including optimality of social profit,computation efficiency,convergence,individual rationality through both solid theoretical analysis and extensive simulation results.To sum up,the dissertation offers multiple incentive mechanisms for practical mobile crowd sensing networks.The proposed approaches offer valuable theoretical foundation and technical support for implementation of mobile crowd sensing applications.