Efficient Data Dissemination Techniques For Multi-Hop Wireless Networks Applied to Vehicular Communications

Multi-Hop Wireless Networks (MHWN) are composed of devices called nodes, which communicate in an ad hoc fashion. Such networks allow the relaying of transmissions over multiple wireless hops to provide an extended service area. There are two main classes of MHWN. The first includes all networks that have a static network topology, e.g. Wireless Mesh Networks and Wireless Sensor Networks. The second specifies networks with a dynamic or mobile topology, e.g. Vehicular Networks. For both types, collaborative applications are of great importance. In such a scenario, information needs to be made available to multiple, or sometimes all nodes in the network. The trivial method, pure network flooding, is to retransmit the information at every hop exactly once. In previous studies it has been shown that such an approach considerably lowers the overall performance of the network by saturating the shared communication channel.

In this thesis, we present two different approaches that perform efficient data dissemination among collaborative nodes in MHWNs. The primarily objective is to reduce the number of redundant retransmissions by selecting only a subset of nodes to be responsible for relaying the information without compromising global delivery. We propose one approach for each of the two classes using different methodologies. For static network topologies, we present a novel heuristic based on the Minimum Connected Dominating Set problem. This approach allows the election of a near-optimal set of relays that are able to reach every other node in the network, thus minimizing the number of retransmissions. We theoretically and experimentally validate our approach and compare it to other state-of-the-art dissemination techniques.

For dynamic network topologies, we focus primarily on Vehicular Networks. We present a new routing protocol that makes use of an efficient dissemination technique to find robust communication paths between two vehicles. Strategic vehicles are elected as relays based on their position and on information about the local neighborhood. The protocol is evaluated using a novel simulation framework that takes into account specific characteristics of vehicular networks in urban environments, e.g. mobility of the vehicles and signal propagation. The performance evaluation shows that our protocol introduces only a low control overhead and provides robust communication paths that achieve high delivery ratios.