Analog Bloom Filter: Efficient simultaneous query for wireless networks

In this paper, we study the problem of supporting simultaneous query in wireless networks, where multiple nodes activate Orthogonal Frequency-Division Multiplexing (OFDM) subcarriers to announce the control information. Such simultaneous query can allow the Access Point (AP) to gather node state information in a single query and greatly improve the performance of wireless networks. We leverage the fact that the number of nodes that need to respond to the query is typically much smaller than the total number of associated nodes, such that nodes may be assigned with overlapping resources to reduce the query time. We propose a solution similar to the Bloom filer, called the Analog Bloom Filter (ABF), because it handles continuous analog signals. We propose an algorithm based on the idea of belief propagation which detects the binary states of the nodes according to the signal powers. We also propose to support multi-bit queries with error correction codes and a novel signaling scheme. We evaluate the proposed algorithms with simulations and the results show that they achieve similar or better performances than the existing query schemes while consuming much less resources.