Analysis of the Indexing Gain When Searching in Spontaneous Wireless Networks

Searching content in spontaneous wireless ad Hoc networks is a complex task due to the intermittent nature of the connections, energy constraints, the often present user mobility and most importantly the lack of centralized network administration. At the same time, the today's search engines (e.g., Google, Yahoo and Bing) are able to provide amazing results at the blink of an eye thanks to their sophisticated and extensive indexing of the content in the Web. Thereby, it is worthwhile to ask if searching content in (sometimes highly dynamic) spontaneous wireless networks could similarly benefit from indexing. In this paper, we provide an elementary analysis to this end. In particular, we compare the search performance without index to a system where full index is available (without taking into account the effort to build such an index). This allows us to characterize the premises under which indexing can be potentially useful, and vise versa. The concepts are illustrated with numerous examples and network topologies arising from different search strategies.