B-SUB: A Practical Bloom-Filter-Based Publish-Subscribe System for Human Networks

摘要

The adoption of portable wireless devices is rapidly rising. The demand for efficient communication protocols amongst these devices is pressing. In this paper, we present a content-based publish-subscribe system, called B-SUB (Bloom-filter-based pub-SUB system), for the networks formed by human-carried wireless devices, which are called human networks (HUNETs). A novel data structure, called Temporal Counting Bloom Filter (TCBF), is proposed to perform content-based networking tasks. The TCBF's novelty is that it is able to handle temporal operations, which are not supported in the classic Bloom filter (BF) and are crucial to the success of forwarding messages in HUNETs. B-SUB uses TCBFs to encode users' interests and embed routing information. Using the TCBF, B-SUB can propagate interests by transmitting at most two TCBFs of dozens of bytes, which makes B-SUB space-efficient. B-SUB makes forwarding decisions through querying the TCBFs, which is simple and fast. These designs make B-SUB pretty suitable for resource-constrained HUNETs. However, the TCBF has false positives, which will potentially cause useless messages to be injected into the network. The issue that arises here is how to handle its false positives in queries, and at the same time maintain its spacial efficiency as well. So, we analyze several methods for controlling the TCBF's false positive rate. B-SUB's viability and usefulness are verified through extensive simulation studies using real-world human contact traces.