Gradient-ascending routing via footprints in wireless sensor networks

A novel gradient-ascending stateless routing protocol, called GRASP (gradient ascending stateless protocol), is proposed for stationary wireless sensor networks. GRASP is built with a novel packet forwarding method called FBF (footprint-based forwarding), in which each node maintains a Bloom filter that holds a dejavu image for the nodes whose packets were relayed through the filter. Forwarding a packet through networked sensors is then just running a membership test of the packet´s destination against the networked Bloom filters, either dropping the packet before it reaches the destination or eventually delivering it to the destination. An extensive simulation study with various routing scenarios has shown the proposed method to achieve about 99% packet delivery while incurring only a small amount of overhead. It also achieves more than 86% packet delivery even for a lossy channel with up to 30% loss rate. Furthermore, our comparative evaluation against AODV or simple flooding shows that GRASP achieves a comparable, or even better, performance in terms of the packet delivery ratio and overhead under the simulation settings investigated. GRASP is shown to reduce the delivery overhead by a factor of 2.37 over AODV or 3.11 over the simple flooding, while providing more robustness to packet losses - this is a significant improvement for low-power sensors in a lossy wireless environment. Manipulating Bloom filters incurs a small space overhead and does not create any protocol conflict with the underlying gradient-descending protocols, thanks to its stateless routing