Recruitment Algorithms for Vehicular Crowdsensing Networks
Vehicular crowdsensing aims to utilize the plethora of onboard sensors and resources on smart vehicles to gather sensing data in a large coverage area. Due to vehicles’ predictable mobility, roadside service providers can use vehicles’ announced trajectories to recruit vehicles to provide sensing data for a coverage area. Existing works have utilized optimization models to obtain optimal solutions. Heuristic recruitment algorithms aim to obtain an approximate solution which runs in polynomial time. In this thesis, we propose several heuristic recruitment algorithms for a variety of vehicular crowdsensing problem formulations. We first explore the temporal vehicle recruitment problem where we recruit vehicles all travelling in the same direction on one road over time. We propose a heuristic recruitment algorithm to compare to an existing optimal framework and heuristic, and achieve better coverage at lower recruitment costs than the existing heuristic. We also prove that the existing heuristic can be arbitrarily bad in the worst case. We then consider the spatiotemporal vehicular recruitment problem where we recruit from vehicles moving freely in a two dimensional space. We propose a new optimal framework for obtaining optimal solutions, as well as a heuristic which we compare to an existing heuristic. Our performance evaluations show that we outperform the existing heuristic in terms of recruiter utility as well as recruitment cost. We also propose a new variation of the vehicular recruitment problem that considers a two dimensional coverage area with certain subsets of area having increased priority. We propose both an optimal model as well as a heuristic for obtaining approximate solutions, which in our performance evaluations on small numbers of vehicles, achieves coverage near optimal at only slightly more expensive recruitment costs. Finally, we consider the heterogeneous or multi sensor vehicular recruitment problem, where vehicles have multiple sensor types and areas of coverage require a certain sensor type to be covered. We propose an optimal model and heuristic for this problem, and again show in performance evaluations that the heuristic returns solutions close to optimal in scenarios with small numbers of vehicles.