Vehicular crowd-sensing: a parametric routing algorithm to increase spatio-temporal road network coverage

ABSTRACT

Current vehicles are equipped with a number of environmental sensors to improve safety and quality of life for passengers. Many researchers have shown that these sensors can also be exploited for opportunistic crowd-sensing. Useful new services can be developed on top of these data, like urban surveillance of Smart Cities. The spatio-temporal sensing coverage achievable with Vehicular Crowd-Sensing (VCS), however, is an open issue, since vehicles are not uniformly distributed over the road network, undermining the quality of potential services based on VCS data.

In this paper, we present an evolution of the standard A${ }^{\mathbf{\ast }}$ routing algorithm, meant to increase VCS coverage by selecting a route in a random way among all those satisfying a parametric constraint on the total cost of the path. The proposed solution is based on an edge-computing paradigm, not requiring a central coordination but rather leveraging the computational resources available on-board, significantly reducing the back-end infrastructure costs. The proposed solution has been empirically evaluated on two public datasets of 450,000 real taxi trajectories from two cities, San Francisco and Porto, characterized by a very different road network topology. Results show sensible improvements in terms of achievable spatio-temporal sensing coverage of probe vehicles.

KEYWORDS:

• Routing
• vehicular crowd-sensing
• intelligent transportation systems
• smart cities
• edge computing

Data and codes availability statement

The data and codes that support the findings of this study are available at the public DOI https://doi.org/10.6084/m9.figshare.12356492

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1. Edge computing is a distributed computing paradigm in which data and/or computation are moved as close as possible to the location where they are needed (the vehicles, in our case), with benefits in terms of latency, bandwidth and cost reduction for back-end infrastructure (Shi et al. 2016).

2. In the study of computational complexity, NP is a class of problems which can be solved by using a Nondeterministic Turing machine in Polynomial time. Problems belonging to this class are regarded as ‘difficult’, as they are often unsolvable by deterministic algorithms in a feasible time, hence justifying the adoption of approximation heuristics. A problem is said to be ‘NP-hard’ if it is at least as difficult as any problem belonging to NP (Papadimitriou 1994).

3. https://aws.amazon.com/ec2/instance-types/c5/

4. Let us note that, as the searchBoundedPath function expands at most as many nodes as A${ }_{\epsilon }^{\mathbf{\ast }}$, the worst-case complexity of these two algorithms is the same. We refer the interested reader to (Ebendt and Drechsler 2009), where a thorough worst-case complexity analysis of A${ }_{\epsilon }^{\mathbf{\ast }}$ is given.

5. https://nominatim.openstreetmap.org/

Additional information

Notes on contributors

Dario Asprone

Dario Asprone is a Ph.D. student in the SOLAR group, a subset of the CREST group in the department of Computer Science, UCL (University College London), United Kingdom. His research interests include automated software testing, smart contracts, routing algorithms and data structures, with a current focus on fuzzing.

Sergio Di Martino

Sergio Di Martino is Associate Professor at the Department of Electrical Engineering and Information Technology of the University of Naples Federico II, Italy, where he is also the co-chair of the Knowledge Management and Engineering (Knome) Lab. He has published more than 100 papers in journals, conference proceedings and books. His research interests focus on knowledge discovery and exploitation from complex spatio-temporal datasets, especially in the field of mobility.

Paola Festa

Paola Festa is Full Professor in Operations Research at the University of Naples Federico II, Italy. Since 1999, she has been frequently and regularly Research Scholar at several national and international research institutions, including CNRs, MIT Lab. for Information and Decision Systems (USA), AT&T Labs Research (USA), and Department of Industrial and Systems Engineering of the University of Florida (USA). She is Associate Editor of several international journals, including Journal of Global Optimization, Optimization Letters, ACM Journal on Experimental Algorithmics, and Journal of Biomedical Data Mining. She has been chair or member of the scientific committee of more than 60 international conferences and workshops and the organizer of more than 10 international scientific workshops/conferences. She is author/co-author of more than 90 publications appeared in international journals, books, and peer-reviewed conference proceedings.

Luigi Libero Lucio Starace

Luigi Libero Lucio Starace is a Ph.D. student in Information Technology and Electrical Engineering at the University of Naples Federico II, Italy, from which he also graduated cum laude with a M.Sc. degree in Computer Science in 2018. His research interests include software engineering, design and evaluation of end-to-end testing techniques, formal methods, and applications of computer science to intelligent transportation systems and smart cities.