On Different-Dimensional Deployment Problems of Hybrid VANET-Sensor Networks with QoS Considerations

Abstract

To enhance vehicular ad hoc networks (VANETs) with the ability to detect road conditions, hybrid VANET-sensor networks (HVSNs) additionally deploy a large number of wireless sensors on road sides, so as to provide a safer driving environment. Most of the previous works on network deployment problems considered too simplified problem settings, and few of them focused on deploying HVSNs. To meet more practical requirements, this paper investigates the problem of deploying roadside units (RSUs) to serve sensors on three different-dimensional road settings (i.e., a one-dimensional road, a road represented as grid points, and a dense network environment) in HVSNs with two objectives (i.e., to minimize the total distance and the total number of hops from sensors to their respective closest RSUs) and two QoS constraints (i.e., for maximal number of hops and capacity). Achieving the two objectives can effectively decrease the probability of transmission interference and lead to shorter transmission time to inform drivers of unexpected events. Since the optimal deployment problems for a grid road and a dense HVSN cannot be solved analytically, this paper creates mathematical programming models for the problems, and further proposes an improved harmony search algorithm. By simulation in different-size instances and statistical analysis, the proposed approaches show promising performance in solving the problems.