Practical algorithms for allocating the roadside units in VANET

The vehicle-to-infrastructure communication is a kind of communication mode of the vehicular ad-hoc network (VANET). It is paramount to allocate roadside units (RSUs) appropriately to assure the quality of communication service. Sarubbi et al. have proposed a greedy heuristic allocation algorithm Delta-r. It examines the Δ ρ2 ρ1 -deployment constraint, a metric for evaluating the performance of VANET, with relative contact time. Unfortunately, the relative contact time of vehicles at urban cells may present `false high', which would play an opposite effect on making a decision. In order to solve the problem, a new allocation algorithm Delta-uc is presented, which examines the Δ ρ2 ρ1 -deployment constraint with a useful contribution. It gets rid of the negative effect of `extra' contact time by means of retaining merely the contributing relative duration of a vehicle at an urban cell. Furthermore, an effective recombination operator is introduced basing on algorithm Delta-uc, and a parthenogenetic algorithm UCPGA is presented to solve the allocation problem. Experimental comparisons were performed on the real mobility trace of Cologne, Germany. The experimental results demonstrate that in many Δ ρ2 ρ1 -deployments, the number of RSUs produced by the Delta-uc and UCPGA algorithms are, respectively, fewer than those produced by algorithms Delta-r and DeltaGA.