Scale-Free Topology for Pervasive Networks

Scale-free graphs and their properties have attracted considerable interest over the last 4–5 years, after it was discovered that many natural and artificial networks belong to this category. However, the so-called preferential attachment rule, whereby scale-free topology can most easily be obtained, relies on newcomers having a global knowledge of the existing connectivity profile. Moreover, the addition of new nodes is usually assumed to be sequential and monotonous (one new node joins the network between two consecutive updates of the global connectivity profile, throughout the growth process). This is incompatible with the requirements of pervasive, ad hoc systems, where it cannot be guaranteed that either of these conditions applies.In this paper, we investigate methods to overcome this difficulty by devising realistic connection protocols that would allow approximating scale-free topology on the sole basis of local information exchange. We argue that successful implementation of our findings could have important implications for pervasive computing environments, as scale-free topology has very desirable features in terms of efficiency and robustness.