A constrained Delaunay Triangulation based RSUs deployment strategy to cover a convex region with obstacles for maximizing communications probability between V2I

In context of competent communication in Vehicular Ad-hoc Networks (VANets), an efficient algorithm for roadside units (RSUs) placement is considered to be a challenging task mainly due to the obstacles like buildings, trees, water-bodies and other constructions. The existing solutions available for this problem come with several limitations. While some of them consider only vehicle density and intersection popularity for RSUs position calculation (bypassing the global coverage), some others are unable to consider the obstacles present in the map to validate the model. In case of the hotspot based RSUs placement method, if the hotspot areas are changed for some reasons, the method does not work properly and even fails for real complex traffic scenarios. This paper presents a novel scheme for placing a given number of RSUs in a convex map and assigning transmission range to each of the RSUs in such a way that each and every position in the map can be covered certainly by at least one RSU despite several obstacles. The proposed method at first initial RSUs position is determined based on a Constrained Delaunay Triangulation (CDT) method to deploy the RSUs in obstacle free area, followed by an optimization method to find out the more significant position for RSUs deployment based on RSUs cost and end-to-end delay. And finally a multi-criteria decision making strategy for RSU selection is introduced for efficient communication between vehicle to infrastructure (V2I) or infrastructure to vehicle (I2V). The simulations have been performed in a real complex road traffic scenario of Ottawas downtown area considering all the obstacles. The simulation results show that the proposed method outperforms the existing methods with the improvement of about 7.7% in packet delivery rate, about 9% reduction in packet loss and about 22% reduction in end-to-end delay. Further, the impact has been analyzed by varying the vehicle density, vehicle flow and RSU cost. The proposed method is tested in different scenarios like Manhattan: Simple map, Erlangen: Medium map and Rome: Complex map to get more precise results.