Research On The RSU Placement Problems In VANETs For Data Dissemination

In recent years, the studies on vehicular ad-hoc networks (VANETs) have become more and more important and have attracted much attention of researchers, along with the rapid development of auto industry and the popularity of private cars. VANET is a new paradigm of mobile ad-hoc network, including the mobile vehicle nodes with high speed and the static roadside units (RSUs). Moreover, the data is transmitted by using short-distance wireless communication connections, such as WiFi and Bluetooth. Currently, there are some problems in the field of traffic transportation, which are urgent to be solved. The studies on VANETs provide a totally new direction to solve these problems.Data dissemination is a basic and essential issue in VANETs. This dissertation considers to place some RSUs aiming to achieve the data dissemination to mobile vehicles, and detailed studies the RSU placement problems in VANETs. Differing from current studies, this dissertation studies the data dissemination problem from the perspective of mobile Social Networks (MSNs). In the other word, some social features of mobile vehicles are taken into account. This dissemination firstly introduce a new mobility model of nodes based on the social features of vehicles. Then, with this model, the dissemination considers to achieve the data dissemination by placing some RSUs in the selected locations. In order to adapt to more general environments, this dissertation extends above mobility model to a more general probabilistic model, and further studies the corresponding problems of RSU placement. In this dissertation, the RSU placement problems are defined as new type of combinatorial optimization problems, are proved to be meaningful extents of Set Cover problem and also NP-hard. Therefore, we propose three approximation algorithms by using greedy strategies for the problems, respectively. Finally, this dissertation analyzes the approximation ratios and conduct the simulations which verify the significant performance of our algorithms.The main contributions of this dissertation include:1) The dissertation proposes new mobility models of vehicles in VANETs by using the social features of the vehicles, and considers to conduct the data dissemination by reasonably placing some RSUs based on the models. These schemes utilize the social features of mobile vehicles, are available in different environments, and can achieve various levels effects of data dissemination.2) This dissertation focuses on the RSU placement problems in different environments of VANETs. In the dissertation, these problems are proved to be NP-hard, and three approximation algorithms by using greedy strategy are also proposed. Moreover, this dissertation proves the approximation ratios of these algorithms, and the simulations verify that these algorithms are better than the compared algorithms.