The placement of roadside units (RSUs) is a difficultand yet important issue in vehicular networks. If too few RSUsare placed, the system performance would be very poor. However,with too many RSUs, it would incur high installation cost andmaintenance cost of these RSUs. In this paper, we study theproblem of delay bounded roadside unit placement (DRP) invehicular networks. For a given delay bound, our objective is toplace the minimal number of RSUs in the system such that amessage from any of RSUs in the region can be disseminated toall vehicles within the given delay bound. We consider two casesof RSUs, the case that all RSUs are interconnected through wiredlines (called DRP-L problem) and the case that RSUs connect toother RSUs through wireless link (called DRP-W problem). Wefirst prove that both DRP-L and DRP-W problems are NP-hard. Then, we propose several heuristic algorithms to solve DRP-L andDRP-W problems, respectively. Extensive simulations have beenconducted to show that the performance of our proposed methods issuperior to the other methods.
展开▼
