Small worlds in wireless networks

In this study, the concept of small worlds is investigated in the context of wireless networks. Wireless networks are spatial graphs that tend to be much more clustered than random networks and have much higher path length characteristics. We observe that by adding a few short cut links, path length of wireless networks is reduced drastically. More interestingly, such short cut links need not be random but may be confined to a limited number of hops; a fraction of the network diameter. This facilitates the design of practical distributed algorithms, based on contacts, to improve performance of resource discovery in wireless networks.