Probabilistic deployment of dissemination points in urban areas to support vehicular communication

Abstract

This work presents a probabilistic constructive heuristic to support the design of roadside infrastructure for information dissemination in vehicular networks. We formulate this as a Probabilistic Maximum Coverage Problem (PMCP) and we intend to maximize the number of vehicles that get in contact with the infrastructure. We compare our approach with non-probabilistic MCP in simulated urban areas following a Manhattan-style topology with variable traffic conditions. The main contributions of this work are (i) the formal definition of the Probabilistic Maximum Coverage Problem, (ii) the application of PMCP to solve one instance of the problem of facilities allocation and (iii) the application of a probabilistic approach to model the volume of vehicles along the urban area, where the position of each vehicle is no longer considered deterministic, but it is treated as a probability function distributed over all the intersections. The vehicles no longer have a position. Instead, vehicles have a probability of being in a given position at a given instant of time. The results reveal that PMCP requires less dissemination points (DPs) to achieve similar coverage ratio than non-probabilistic MCP, while preserving the same samples deviation.

Keywords: vehicular networks, maximum coverage problem, information dissemination.