Evaluating Multihop Mobile Wireless Networks with Controllable Node Sparsity or Density
Johnson, David B.
Doctor of Philosophy
Simulation is the most widely used tool for evaluating the performance of multihop mobile wireless networks, yet such simulation has so far been limited due to the lack of sufficient wireless mobility models for creating a wide range of different types of network scenarios of mobile nodes moving about for use in protocol simulation. For example, the very commonly used Random Waypoint mobility model can only effectively be used in scenarios with relatively high node density, as attempting to generate sparser scenarios (e.g., trying the same number of nodes in larger and larger spaces) results in scenarios in which the network is frequently or always partitioned, with no possible multihop wireless path between many different pairs of nodes. In this thesis, I present the design and evaluation of the Random Controlled Sparse (RCS) mobility model, a new dynamic, tunable mobility model that can be controlled to generate a wide range of mobile scenarios with varying levels of node sparsity or density while avoiding network partitions. The model requires only a small set of parameters to define the desired behavior of the scenarios being generated. In generating a scenario, RCS itself internally operates as a separate discrete event simulator, utilizing highly efficient graph and computational geometry algorithms to control the desired sparse behavior and manage the constraints between the motions of different nodes. To further improve the performance and scalability of the model, I have also parallelized certain key parts of the scenario generation in the model. To show the performance of the model in generating scenarios, I have evaluated the running time of the model across wide range of number of nodes and node densities. I also present an evaluation of the scenarios generated, in terms of metrics such as the average number of neighbors of a node and the average minimum possible path length (hop count) existing between each pair of nodes, demonstrating the range of scenarios that RCS is able to produce. To show the usefulness of the model in revealing protocol behavior, I show the performance of DSDV, a common multihop wireless ad hoc network routing protocol, across a wide range of sparse and dense network scenarios. These results demonstrate that different degrees of node sparsity or density sometimes have surprising effects on protocol performance. Simulations such as these, revealing these types of results, have not generally been possible before due to the lack of suitable mobility models. Finally, to more fully show the use of the RCS model in evaluating real protocols, I present the design and evaluation of LAMP, the Local-Approximation Multicast Protocol, a new on-demand multicast routing protocol I have designed for mobile wireless ad hoc networks that delivers high performance in both sparse as well as dense scenarios. LAMP maintains high performance by utilizing link-layer unicast transmissions, based on a new algorithm in which each node computes a local approximation of the globally optimal multicast forwarding tree to the receivers. LAMP also introduces a new distributed protocol optimization known as anticipatory forwarding, to further improve both overhead and packet delivery latency when this local approximation deviates from the globally optimal tree. I have evaluated LAMP through detailed ns-2 simulations using scenarios from the RCS model as well as the Random Waypoint model, and compared it with ODMRP and ADMR, two existing on-demand multicasting protocols that have previously been shown to perform well.