Approximate connectivity graph generation in mobile ad hoc radio networks

C. L. Barrett, M. V. Marathe, D. C. Engelhart, A. Sivasubramaniam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


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 recomputed 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 two previously proposed graph measures - the degree and clustering coefficient distributions. Results indicate that these approximations can be quite effective in avoiding repeated calculation of exact graph connectivity.

Original languageEnglish (US)
Title of host publicationProceedings - 36th Annual Simulation Symposium, ANSS 2003
PublisherIEEE Computer Society
Number of pages8
ISBN (Electronic)0769519113
StatePublished - 2003
Event36th Annual Simulation Symposium, ANSS 2003 - Orlando, United States
Duration: Mar 30 2003Apr 2 2003

Publication series

NameProceedings - Simulation Symposium
ISSN (Print)1080-241X


Other36th Annual Simulation Symposium, ANSS 2003
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Approximate connectivity graph generation in mobile ad hoc radio networks'. Together they form a unique fingerprint.

Cite this