Approximate Connectivity Graph Generation in Mobile Ad Hoc Radio Networks

Simulation is a widely used technique in the design andevaluation of mobile ad-hoc networks. However, time andspace constraints can often limit the extent of the size, complexityand detail of the networks that can be simulated. Approximationsin the system model can possibly alleviate thisproblem, but we need to be careful about how much accuracyis compromised when employing them.This paper specifically focuses on one aspect of simulationcost that is incurred in the computation of the connectivitygraph that is used to describe what mobile nodescan communicate with whom. Since such a graph is recomputedfrequently during the simulation, we explore alternativesto computing this graph exactly and their accuracyin capturing the actual graph properties.We investigate three approximation alternatives to computegraph connectivity, and propose metrics for expressingtheir deviations from the actual graph. In addition,the graphs generated by these approximations are comparedto the original by examining two previously proposedgraph measures - the degree and clustering coefficient distributions.Results indicate that these approximations canbe quite effective in avoiding repeated calculation of exactgraph connectivity.