  Unlike the well-studied models of growing networks, where the dominant
dynamics consist of insertions of new nodes and connections, and rewiring of
existing links, we study {\em ad hoc} networks, where one also has to contend
with rapid and random deletions of existing nodes (and, hence, the associated
links). We first show that dynamics based {\em only} on the well-known
preferential attachments of new nodes {\em do not} lead to a sufficiently
heavy-tailed degree distribution in {\em ad hoc} networks. In particular, the
magnitude of the power-law exponent increases rapidly (from 3) with the
deletion rate, becoming $\infty$ in the limit of equal insertion and deletion
rates. \iffalse ; thus, forcing the degree distribution to be essentially an
exponential one.\fi We then introduce a {\em local} and {\em universal} {\em
compensatory rewiring} dynamic, and show that even in the limit of equal
insertion and deletion rates true scale-free structures emerge, where the
degree distributions obey a power-law with a tunable exponent, which can be
made arbitrarily close to -2. These results provide the first-known evidence of
emergence of scale-free degree distributions purely due to dynamics, i.e., in
networks of almost constant average size. The dynamics discovered in this paper
can be used to craft protocols for designing highly dynamic Peer-to-Peer
networks, and also to account for the power-law exponents observed in existing
popular services.
