Approximating the connectivity between nodes when simulating large-scale mobile ad hoc radio networks

Simulation is a widely used technique in the design and evaluation of mobile ad hoc networks. However, time and space constraints can often limit the extent of the size, complexity and detail of the networks that can be simulated. Approximations in the system model can possibly alleviate this problem, but we need to be careful about how much accuracy is compromised when employing them. This paper specifically focuses on one aspect of simulation cost that is incurred in the computation of the connectivity graph that is used to describe what mobile nodes can communicate with whom. Since such a graph is re-computed frequently during the simulation, we explore alternatives to computing this graph exactly and their accuracy in capturing the actual graph properties. We investigate three approximation alternatives to compute graph connectivity, and propose metrics for expressing their deviations from the actual graph. In addition, the graphs generated by these approximations are compared to the original by examining several previously proposed graph measures - the degree distribution, clustering coefficient, shortest path distribution and eigenvalue distribution. Such comparisons are conducted not only with static graphs, but also with dynamically changing graphs that are a consequence of clients moving. Results indicate that these approximations can be quite effective in avoiding repeated calculation of exact graph connectivity.