Routing on large scale mobile ad hoc networks using bloom filters

A bloom filter is a probabilistic data structure used to test whether an element is a member of a set. The bloom filter shares some similarities to a standard hash table but has a higher storage efficiency. As a drawback, bloom filters allow the existence of false positives. These properties make bloom filters a suitable candidate for storing topological information in large-scale mobile ad hoc networks, where there is a considerable amount of data to be exchanged. Bloom filters enable the transmission of reduced routing control messages to save available bandwidth, and they require fewer node resources than traditional data structures. Existing ad hoc routing protocols using bloom filters limit themselves to static sensor networks or small/medium-scale mobile networks. In this study, we propose and analyse a routing protocol suited for large scale mobile ad hoc networks (up to 3000 nodes) that stores and disseminates topological information through a specific type of bloom filter that is able to discard old elements. Logical overlays are then constructed with the proposed data structures to indicate the distance to the destination nodes. This process allows the routing protocol to reduce the number of control messages required to discover and maintain routes. The proposed algorithm is validated via simulation and compared with other well-known routing protocols developed for mobile ad hoc networks.