Mobile ad-hoc networks can provide for information exchange between devices if a communication infrastructure is not available or cost-effective. Such a networks should organize and configure itself spontaneously and automatically. For that purpose, it is important that mobile devices can learn about the other devices in their environment, and the services they can provide.

We present a novel approach to perform service discovery in an ad-hoc network based on the use of attenuated Bloom filters. In this approach, neighboring devices exchange advertisements, which provide a highly compressed summary of services they know of up to a certain number of hops away. Neighbors use these advertisements to supplement their knowledge of the environment, and to direct query messages, if they are in need for a certain service. The use of attenuated Bloom filters to summarize service availability in advertisements minimizes the amount of data to be exchanged at the cost of a small probability of false positives. Results obtained using an analytical performance model and a simulation model show that the approach is effective and very resource efficient for discovery processes in networks with mobile, resource-constrained nodes and wireless links.