Study On Data Delivery And Task Assignment For Applications Of Crowdsourcing In Internet Of Vehicles

With the advancement of communication technology and sensor technology,invehicle devices have dramatically improved in terms of data sensing,storage computing,and delivery capabilities.In recent years,urbanization has led to a rapid increase in vehicle ownership.Both factors make it possible for in-vehicle devices to perform applications of crowdsourcing in the Internet of Vehicles(IoV).The basic problem of applications of crowdsourcing in IoV is collecting various types of sensing data,which can be seen as the process of workers(vehicles)completing tasks,so it is necessary to adopt different collection strategies for different types of data.For delay-tolerant data(traffic flow,road condition monitoring of sparse pedestrian flow,point-of-interest locations,etc.),since its low requirements for data transmission delay and delivery,the opportunistic communication of IoV can reduce communication costs,and its core problem focuses on the data delivery strategy of selecting suitable forwarding nodes,aka opportunistic data collection strategy;for delay-sensitive data(urban traffic conditions,carpooling services,etc.),the collection of such data must rely on cellular communication due to its high requirements on data transmission delay and delivery,which results in higher communication costs that need to be compensated in the form of paid crowdsourcing,whose core problem focuses on the matching strategy between crowdsourced workers and tasks,aka participatory data collection strategy.In this thesis,we focus on the two core problems of data delivery and task assignment for applications of crowdsourcing in IoV and study efficient delivery methods,and task assignment mechanisms.Also,we analyze the problems and optimization strategies faced by data delivery and task assignment.The main contributions of this dissertation are as follows:1)Data delivery methods in the dynamic movement pattern of crowdsourcing in the Internet of Vehicles.Existing data delivery methods focus on opportunistic strategies or static sociality strategies,which are difficult to sense the dynamic changes of vehicular sociality in time.To this end,this dissertation designs a dynamic sociality prediction method based on k-order Markov chains to evaluate the node delivery performance.To capture the dynamic changes of vehicular sociality,this dissertation proposes to construct contact cliques by collecting contact,forwarding,and requesting data among vehicles and then mining the social cliques among vehicles using community discovery methods.To evaluate and predict the delivery performance of vehicles,this dissertation first defines the forwarding preferences of nodes to data.Then constructs the historical sequence of both contact cliques and social cliques using historical data.Next,we predict the forwarding preferences of vehicles in the next time slot using the Markov chain.To select the appropriate forwarding node,this dissertation proposes an algorithm based on a greedy strategy to ensure that once a node contacts other nodes,its data can forward to the node with the best forwarding preferences.Experimental results show that the proposed method can respond to the dynamic changes in vehicle sociability in time,improve adaptability and optimize the selection of forwarding nodes.2)One-sided online stable task assignment method for crowdsourcing in Internet of Vehicles.Existing one-sided task assignment methods mainly focus on online assignment(task vertices arrive online)and less on stable matching,which weakens the practical feasibility.To this end,this dissertation constructs a onesided online stable task assignment problem including a mathematical model of stable matching.To model the online stable model,we analyze the stable matching condition assuming that online vertices obey independent identical distribution and then design the corresponding linear programming.To evaluate and measure the task utility from a real dataset,we define the probability and expectation of the distance and time for the next order given the known current time and position of an order,and then adopt the ratio of the expectation of the expected distance and expected time to characterize the utility.In order to design an efficient algorithm,this dissertation proposes an algorithm based on the Two Suggested Matching(TSM)technique.It computes the offline solutions of linear programming and maximum weighted matching of the bipartite graph.Then,a constant-level suboptimal combination solution is constructed based on the results of the two solutions to TSM.Experimental results show that the proposed method considers both online matching and stable matching,further improving the competitive ratio of the algorithm and optimizing the matching stability.3)Two-sided online stable task assignment method for crowdsourcing in Internet of Vehicles.Existing two-sided task assignment methods are less concerned with stable matching scenarios.For this reason,this dissertation considers stable matching under the online arrival of two-sided vertices(worker vertices and task vertices).First,to maximize the task assignment cardinality,we analyze the stable matching condition of two-sided vertices online arrival and construct the two-sided online stable task assignment problem.Second,we propose two classical benchmark algorithms,Greedy and Random Threshold,and analyze the performance.To ensure the efficiency and effectiveness of the algorithm,we propose a new algorithm BiRanking with randomly assigned rank values to obtain the approximation solution.The proposed method provides a solution considering online and stable for the two-sided vertices random arrival scenario.4)Three-sided online stable task assignment method for crowdsourcing in Internet of Vehicles.Existing task assignment methods focus on one-sided or two-sided scenarios.The methods involving three-sided scenarios(worker vertices,task vertices,and workplace vertices)concentrate on three-sided online matching.To this end,this dissertation investigates the stable task assignment problem when three-sided online vertices arrive randomly.First,to maximize the task assignment utility,we analyze the matching conditions of three-sided vertices and construct our problem.Second,the performance of three benchmark algorithms,THS-GDY(Three-sided Greedy),THS-RT(Three-sided Random Threshold),and THS-AT(Three-sided Adaptive Threshold),is proposed and analyzed.Considering the influence of spatio-temporal factors of online vertices,this dissertation proposes a combinatorial algorithm THS-OSTA based on vertex arrival timing,which selects different matching methods for different arrival timing of vertices.This dissertation explores the online stable assignment in a three-sided scenario and proposes an effective solution to the problem.