Improving search efficiency using Bloom filters in partially connected ad hoc networks: A node-centric analysis

In a partially connected ad hoc network, two nodes communicate and share data when they are in proximity. For the query based (QB) scheme, a node retrieves data from another node by querying. Search efficiency deteriorates when the query success probability is small. We propose a Bloom filter based (BF) scheme to improve search efficiency. A data holder summarizes its content by a Bloom filter and broadcasts it to the data querier. The data querier then transmits a query only when the requested data is available. We first consider the single neighbor scenario, and derive the long run bandwidth utilization of a connection. More generally, a node may find multiple neighbors and neighbor relationship changes dynamically with time. Querying is more efficient due to the presence of multiple data holders. There may also be multiple Bloom filter transmissions over a busy period, reducing the effective data transmission time of the BF scheme. For a fair comparison of the QB and BF scheme, we characterize the search efficiency, as a function of node density. Numerical study shows that an optimal Bloom filter consumes negligible overhead, even in low bandwidth scenarios. We conclude that the BF scheme is superior for data retrieval. Our performance evaluation makes use of the M/M/∞ queue to model mobility, parametrized on node encounter rate and connection time. Moreover, the analysis is node-centric, avoiding the use of discrete locations, unrealistic mobility and interference models. This technique is novel and can be used for studying the impact of mobility in other mobile networks.