Bloom Filter for Fixed-Size Beacon in VANET

Most work in vehicular ad hoc network focuses on an efficient mechanism to deliver data. These mechanisms need a beacon to exchange all necessary information between neighbors. Although a beacon is a small packet that is periodically broadcast to maintain accuracy, too much information can cause a bulky beacon. This leads to a contention problem due to limited resources in wireless networks. Many approaches are proposed to avoid the problem by reducing the frequency of beacon broadcasting. However, bulky beacons still exist. In this paper, we propose a solution using a Bloom filter to create fixed-size beacons. A single Bloom filter can replace all variable size data structures. Our solution reduces the complexity of a connected dominating set algorithm from O(n^5) to O(n). The evaluation indicates that our proposed solution can significantly reduce the beacon overhead without decreasing the protocol performance.