Optimal Two-Lane Placement for Hybrid VANET-Sensor Networks

Vehicular ad hoc networks (VANETs) help improve traffic safety and lessen traffic congestion. Roadside units (RSUs) play a key role in serving as the event and data broker in the form of vehicle-to-infrastructure communication to supply wireless and mobile vehicle-to-vehicle communication. Recently, hybrid VANET-sensor networks have attracted much attention as events are detected by sensor nodes and are spread to a wider area via VANETs, in which the number of RSUs is restricted due to high cost. This paper investigates the problem of minimizing the total cost of deploying RSUs and sensor nodes along the two sides and the median island of a two-lane road to cover the whole road, represented as a grid, and to form a connected VANET-sensor network. This problem is NP-complete by reduction to the NP-complete placement problem for a single-lane road. Therefore, this paper formulates the problem as an integer linear program and then proposes a center particle swarm optimization approach, in which a center particle is adopted for increasing the convergence speed. Additionally, a theoretical analysis for the approach is provided. Experimental results show that the approach can perform well for moderate-sized problems.